3.14 3.14 6.28 3.14 6.28 R (a) 3.14 6.28 3.14 A t5 n5)t2,4 t2,t4 t1.t3 pI 3.14 6.28 R 3.14 6.28 R 6)A,5 t1.t3 3.14 6.28 R 16
16 n1 n1 n2 n1 n2 n3 n4 n5 + t1 t2 pi pi t1 pi 3.14 3.14 6.28 3.14 6.28 R r (a) (b) (c) n1 n2 n3 n4 n5 + t1 t2 pi 3.14 6.28 R r (d) n6 A * n1 n2 n3 n4 n5 + t1,t3 t2 pi 3.14 6.28 R r (e) n6 A * n1 n2 n3 n4 n5 + t1,t3 t2,t4 pi 3.14 6.28 R r (f) n6 A * n1 n2 n3 n4 n5 + t1,t3 t2,t4 pi 3.14 6.28 R r (g) n6 A,t5 * n1 n2 n3 n4 n5 + t1,t3 t2,t4 pi 3.14 6.28 R r (h) n6 A,t5 * n7 t6 -
A n8 ne A t5 n5,14(n7y6 n5+4(m7y6 nI n2)t1,t3 n4 n 3.146.28 R r3.146.28 R 图7dag的构造过程
17 n1 n2 n3 n4 n5 + t1,t3 t2,t4 pi 3.14 6.28 R r (h) n6 A,t5 * n7 t6 - n8 * t7 n1 n2 n3 n4 n5 + t1,t3 t2,t4 pi 3.14 6.28 R r (g) n6 A,t5 * n7 t6 - n8 * t7 n9 - A 图7.6 dag的构造过程
四、dag实现的优化 从上述构造dag的步骤及例73中不难发现 dag构造时已实现了如下优化: 1.合并已知量 步骤(2)对公共子表达式并不生成标记该运算 的内部结点,而是执行运算,由结果常数参与 构造dag,实现了编译时合并已知量的优化 2.删除多余运算 步骤(3)对公共子表达式并不生成重复的结点, 只是在结点的附加标记集中增加被赋值变量名 18
18 四、dag实现的优化 从上述构造dag的步骤及例7.3中不难发现： dag构造时已实现了如下优化： 1. 合并已知量 步骤(2)对公共子表达式并不生成标记该运算 的内部结点，而是执行运算，由结果常数参与 构造dag，实现了编译时合并已知量的优化。 2. 删除多余运算 步骤(3)对公共子表达式并不生成重复的结点， 只是在结点的附加标记集中增加被赋值变量名
3.删除死代码 步骤(4),在将x附加到结点n上之前,删除已出现在 某个结点的附加标记集中的x,那些定值后未被引用 即被重新定值的x,因x的删除而成为死代码,其前 次的定值被删除 此外,从dag还可知道: (1)作为dag叶结点标记的标识符,是在此之前的基 本块内被定值并在本基本块内被引用的变量名 (2)作为dag各结点附加标记的标识符是在基本块内 定值并可以在基本块内和基本块后被引用的变量名 如果确认某结点的一个附加标记在基本块后不会被引 用(称为不活跃),则该标识符的定值语句可作为死代 码被删除
19 3. 删除死代码 步骤(4)，在将x附加到结点n上之前，删除已出现在 某个结点的附加标记集中的x，那些定值后未被引用 即被重新定值的x，因x的删除而成为死代码，其前一 次的定值被删除。 此外，从dag还可知道： (1) 作为dag叶结点标记的标识符，是在此之前的基 本块内被定值并在本基本块内被引用的变量名。 (2) 作为dag各结点附加标记的标识符是在基本块内 定值并可以在基本块内和基本块后被引用的变量名， 如果确认某结点的一个附加标记在基本块后不会被引 用(称为不活跃)，则该标识符的定值语句可作为死代 码被删除
例74如果例73的dag按结点建立次序重构基本块,则可得 到经上述优化后的基本块。 ①pi:=3.14 ②t1:=6.28 ③t3:=6.28 ④t2:=R+r ⑤t4:=t2 ⑥t5:=6.28*t2 ⑦t6:=R-r ⑧t7:=t5*t6 ⑨A:=t7-t5 如果pi及t1-t7出基本块不活跃(它们只是在计算表达式时使 用的临时变量),则重构的基本块可进一步优化为 ①S1:=R+r ②S2:=6.28*S1 ③S3:=R-r ④S4:=S2*s3 ⑤A:=S4-S2 20
20 [例7.4] 如果例7.3的dag按结点建立次序重构基本块，则可得 到经上述优化后的基本块。 pi:=3.14 t1:=6.28 t3:=6.28 t2:=R+r t4:=t2 t5:=6.28*t2 t6:=R-r t7:=t5*t6 A:=t7-t5 如果pi及t1-t7出基本块不活跃(它们只是在计算表达式时使 用的临时变量)，则重构的基本块可进一步优化为： S1:=R+r S2:=6.28*S1 S3:=R-r S4:=S2*S3 A:=S4-S2