全局公共子表达式 如果E t6=4*i B a[t6] 在某次出现之前必然己经t7=4*1 被计算过,且 t8=4★ t9=a[t8] E的分量在该次计算之后 a[t7]=t9 t10=4*j 直没有被改变, a[t10]=x goto B 那么E的本次出现就是 a)消除之前 个公共子表达式 t6=4*i B [t6 如果上一次E的值赋给了x,|h例子见左 且x的值至今没有被修改a81x 7=4*1 过,那么我们就可以使用 goto B, t10=4*1 X,而不需要计算E; b)消除之后 不需要重新计算 ·基本块内的 共子表达式
全局公共子表达式 • 如果E – 在某次出现之前必然已经 被计算过，且 – E的分量在该次计算之后 一直没有被改变， • 那么E的本次出现就是一 个公共子表达式 • 如果上一次E的值赋给了x， 且x的值至今没有被修改 过，那么我们就可以使用 x，而不需要计算E； 例子见左边 t7=4*i t10 =4*j 不需要重新计算； • 基本块内的公 共子表达式
全局公共子表达 式的倒子 v= a[tll ·右图 i=i+1 B 在B、B3中计算了4*和4* t2=4*i t3 =a[t2 if t3<v goto B 到达B之前必然经过B2、 B t2、t4在赋值之后没有被改 t4=4 变过,因此B5中可直接使 t5 a[t4 if t5>v goto B 用它们 一t4在替换t8之后,Bs:a[t8 if i> 同李,3:a4又相; 和B t11=4*i B中赋给x的值和B中赋给 x a[t61 x= a[tlll t12=4*i t3的值相同; t13=4*n t9 =a[t81 t14=a[t13 B中的at13]和B1中的alt1l a[t7]=t9 a[t12]=t14 不同,因为B中可能改变a t15=4*n a[t10]=x a[t15]=x 的值 goto B
全局公共子表达 式的例子 • 右图 – 在B2、B3中计算了4*i和4*j – 到达B5之前必然经过B2、 B3； – t2、t4在赋值之后没有被改 变过，因此B5中可直接使 用它们； – t4在替换t8之后，B5：a[t8] 和B3：a[t4]又相同； • 同样： – B5中赋给x的值和B2中赋给 t3的值相同； – B6中的a[t13]和B1中的a[t1] 不同，因为B5中可能改变a 的值；
消除公共子表达 i=m-1 式后的结果 jtv 1=4n a[tll itti t2=4*1 3 t2 f t3<v goto B t5=a[t4] if t5>v goto B f i>=] goto B x = t3 B t3 a[t2]=t5 a[t4]=x a[t2]=t14 to B a[tI]=X 图95经过公共子表达式消除之后的B5和B
消除公共子表达 式后的结果
复制传播 °形如u=V的复制语旬使得语旬后a-alb-ac 面的程序点上,u的值等于V的值 c= d+e 如果在某个位置上u定等于V,那 么可以把u替换为V; d+e d+e t b t 有时可以彻底消除对u的使用。从 而消除对u的赋值语句; t 右图所示,消除公共子表达式时 引入了复制语句 如果尽可能用t来替换C,可能就 不需要C=这个语句了
复制传播 • 形如u=v的复制语句使得语句后 面的程序点上，u的值等于v的值； – 如果在某个位置上u一定等于v，那 么可以把u替换为v； – 有时可以彻底消除对u的使用，从 而消除对u的赋值语句； • 右图所示，消除公共子表达式时 引入了复制语句； • 如果尽可能用t来替换c，可能就 不需要c=t这个语句了
复制传播的倒子 右图显示了对B进行复 x= t3 B a[t2]=t5 制传播处理的情况 a[t4]= goto B 可能消除所有对X的使用 x t3 [t2] [t4]=t3 goto B
复制传播的例子 • 右图显示了对B5进行复 制传播处理的情况 – 可能消除所有对x的使用