编译原理与实践：基于基本块DAG

在局部优化中，可以将一个基本块以DAG（有向无环图）的形式予以描述。DAG与流图不同，流图中的任何一个结点（基本块）都可以用一个DAG表示。DAG的组成要素说明如下：

（1）叶结点。DAG中没有后继的结点称为叶结点，它对应于表达式中的标识符（变量名）或常数，表示该变量或常数的值。叶结点代表名字的初始值，根据作用到一个名字上的算符，可以知道需要的是一个名字的左值还是右值。大多数叶结点代表右值。

（2）内部结点。DAG中有后继的结点被称为内部结点，它对应于运算符，代表计算出来的值。

（3）各个结点上可附加若干个标识符，表示这些标识符具有该结点所代表的值。

要构造基本块的DAG，需要先构造每一条语句的DAG。假设中间代码的形式包括如下3种：

(1)X:=Y

(2)X:=op Y

（3）X：=Y op Z或X：=Y[Z]

其中，X、Y、Z为标识符或常数，op为操作符。

使用如下的算法构造基本块的DAG。开始时，DAG为空。对基本块中的每一条语句依次执行下述步骤：

（1）对于形如X：=Y的中间代码语句，查找是否存在一个结点Y，若不存在，则创建结点Y，并在附加标识符表中增加标识符X；

（2）对于形如X：=op Y的中间代码语句，查找是否存在结点Y，若不存在，则创建结点Y；接着查找是否存在一个结点op，其子结点为Y，若不存在，则创建结点op，并将op和Y连接，同时，在附加标识符表中增加标识符X；

（3）对于形如X：=Y op Z的中间代码语句，查找是否存在结点Y和Z，若不存在，则创建结点Y和（或）Z；接着查找是否存在一个结点op，其左子结点为Y，右子结点为Z（目的是为了发现公共子表达式），若不存在，则创建结点op，并将op和Y、Z连接，同时，在附加标识符表中增加标识符X；

（4）由于X的当前值是刚刚新建立或已找到的结点的值，因此，对于事先附加在其他某个结点上的X，则需将其删除掉。

例8.3 给定如下的基本块：

(1)T0:=3.14 (6)T3:=2*T0

(2)T1:=2*T0 (7)T4:=R+r(www.xing528.com)

(3)T2:=R+r (8)T5:=T3*T4

(4)A:=T1*T2 (9)T6:=R-r

(5)B:=A (10)B:=T5*T6

处理每一条语句后所构造出的DAG如图8-3所示。其中，图（a）～（j）分别对应于语句（1）～（10）。

图8-3　例8.3中基本块所对应的DAG

利用基本块的DAG图，在保持其结构的同时，可以对代码进行优化。主要的优化技术包括：合并已知量、删除公共子表达式、删除无用代码等。

在建立基本块的DAG时，当某个叶结点是已知量时，在后续建立其他结点时若引用了该结点的附加标识符，则可以直接使用其值。例如，在建立图8-3的DAG时，T0是已知量，那么在计算T1时，就可以直接将T1的值计算出来。此时，T1也就成了已知量。

检测公共子表达式可以在新结点加入DAG时进行，检查是否存在和新结点具有同样的运算符和同样顺序的相同子结点。如果存在，则不必建立新结点，只需标注即可。在图8-3中，代码（3）T2：=R+r和（7）T4：=R+r的运算符相同，左、右子结点也相同，表示同一个计算，因此，就不必建立新的T4结点。

删除无用代码可以在DAG完成后，删除所有没有附加活跃变量的根结点。重复此过程，就可以删除所有对应死代码的结点。就图8-3的DAG来说，假定任何临时变量Ti在基本块外都是无用的。首先，考虑结点n1，由于该结点的附加标识符T0的值后来不再引用，因此其代码为无用代码，可以删除；其次，在建立DAG时，结点n2的值已经计算了出来，属已知量，它有两个附加标识符T1和T3，均可以直接引用其值，因此，其代码可以删除；接着，结点n5对T2和T4求值，这里用T2保存其值；结点n6对A和T5求值，用A保存其值，由于A引用的T1为已知量，故可以直接引用；最后，结点n7对T6求值，结点n8对B求值。按照上述过程，例8.3的10条语句可优化为如下的4条语句：

(1)T2:=R+r

(2)A:=6.28*T2

(3)T6:=R-r

(4)B:=A*T6

DAG重构基本块时，要注意使用变量来存放DAG的结点的值，注意计算不同结点值的指令的顺序。指令的顺序必须和DAG中结点的顺序一致，计算某结点的值必须先完成子结点值的计算。

DAG不仅可用于优化操作，而且蕴含着一些十分有用的信息。一方面，利用DAG可以确定哪些标识符的值在该基本块中被引用，它们是DAG中叶结点对应的标识符；另一方面，可以确定在基本块内被定值且该值能在基本块外被引用的标识符，它们是DAG中各结点上的附加标识符。这些信息可用于中间代码的进一步优化。优化时，由于很可能要用到有关变量在该基本块之后的引用情况，因此，需要对数据流进行一定的分析。