编译器笔记51-代码优化-可用表达式分析

可用表达式分析

• 可用表达式

如果从流图的首节点到达程序点p的每条路径都对表达式x op y进行计算，并且从最后一个这样的计算到点p之间没有再次对x或y定值，那么表达式x op y在点p是可用的(available)。

• 表达式可用的直观意义

在点p上，x op y已经在之前被计算过，不需要重新计算。

可用表达式信息的主要用途

• 消除全局公共子表达式

例.png

若在B3的入口处，4*i是可用表达式的话，那么B3中的4*i就是全局公共子表达式，就可以将其删除。

问：B2中的代码满足什么条件在B3的入口处才能被使用呢？
答：根据可以表达式的定义从流图的首节点到达B3入口处的每条路径上都计算了表达式4*i的值。并且从最后一次计算到B3入口处之间没有对i重新定值，在此种情况下表达式4*i在B3入口处才可用。因此要求B2中的代码没有对i重新定值或者即使重新定值以后又重新计算了4*i的值。

• 进行复制传播

例.png

可用表达式的传递函数

对于可用表达式数据流模式而言，如果基本块B对x或者y进行了(或可能进行) 定值，且 以后没有重新计算x op y，则称B杀死表达式x op y 。如果基本块B对x op y进行计算，并且之后没有重新定值x或y，则称B生成表达式x op y。

传递函数.png e_gen计算.png

注1：x op y对z进行了定值，因此它杀手了与z相关或以z作为运算分量的表达式。

注2：初始时可用表达式为空集，那么扫描完第一条语句以后把b+c加入到可用表达式集合中，同时把跟a相关的可用表达式删除掉，生成b+c。扫描到第二条语句后，把a-d加入到集合中，同时把所用跟b相关的表达式删除，因此b+c删除添加了a-d。在扫描第三条语句时，添加表示式b+c，然后把跟c相关的表达式b+c删除，因此集合中什么都没有添加还是a-d。在扫描到第四条语句时我们将跟d相关的语句删除掉，最后集合变为空集。

e_kill.png

可用表达式的数据流方程

可用表达式的数据流方程.png

计算可用表达式的迭代算法

计算可用表达式的迭代算法.png

为什么将OUT[B]集合初始化为U？

OUT集合初始化为Φ局限性.png

注：第一次迭代时，首先计算的是B1的IN值和OUT值，接下来计算B2的IN值，此值是根据其前驱节点的OUT值来计算的。B2有两个前驱节点一个是B1一个是B2自己，那么B1的OUT值在第一次迭代时已经计算出，B2的OUT值使用的是初始化的值，若该值为空，那么任何集合与其进行交运算得到的都是空集。这样我们就把OUT[B1]中本来可以在B2入口处可用的表达式屏蔽掉了，这样是不合理的。若定义为全集U则没有该问题。