《编译原理》画 DAG 图与求优化后的 4 元式代码- 例题解析 (2)

(1)试用 DAG 进行优化并重写基本块
(2)假定只有 R,H 在基本块出口是活跃的,试写出优化后的 4 元式序列
(只需要还原活跃变量)

解析:

(1)画出 DAG 图如下:

画图的步骤就是:根据基本块,一部一部组装

《编译原理》画 DAG 图与求优化后的 4 元式代码- 例题解析

(2)假定只有 R,H 在基本块出口是活跃的,试写出优化后的 4 元式序列
(只需要还原活跃变量)

优化后的 4 元式代码可以写为:
(1)S2 := T-C
(2)S3 := T+C
(3)R := 2/S3
(4)H := R*S2

解释:

与原来的基本块相比较可以看出:

原基本块中的 (2) 和 (7) 中的已知量都已经合并。因为 (2) 中 S4 := 2,(7) 中用 2,所以合并。

(5) 和 (8) 中的公共子表达式 T+C 只在 (5) 中计算一次,在 (8) 中 直接引用其结果,所以删除了多余运算。

(6) 中的无用赋值已被删除。S5 := S3,S5 后面没有再用,所以就和 S3 一起表示。

除了可以应用 DAG 进行上述的优化外,还可以从基本块的 DAG 中得到一些其他信息:

DAG 叶结点上标记的标识符是在该基本块之前的基本块内被定值,并在该基本块内被引用的标识符。

DAG 各结点上的附加标识符是在基本块内被定值,并可以在基本块后被引用的标识符。

如果确认某结点的一个附加标记在基本块后不会被引用,则该标识符的定值语句可以作为死代码被删除。

假设上面例子中 S0~S6。在基本块后面都不会被引用只有 R, H 在基本块出口是活跃的则优化后的四元式序列可以写为:
(1)S2 := T-C
(2)S3 := T+C
(3)R := 2/S3
(4)H := R*S2

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/zgfgyg.html