第九章机器无关的优化 赵建华 南京大学计算机系
第九章 机器无关的优化 赵建华 南京大学计算机系
优化的主要来源 ·编译器只能通过一些相对低层的语义等价转换 来优化代码; ·冗余运算的原因 源程序中的冗余; 高级程序设计语言编程的副产品 比如A[f=0;A[]]k=1;中的冗余运算; 语义不变的优化 公共子表达式消除 复制传播 死代码消除 常量折叠
优化的主要来源 • 编译器只能通过一些相对低层的语义等价转换 来优化代码； • 冗余运算的原因 – 源程序中的冗余； – 高级程序设计语言编程的副产品 • 比如A[i][j].f = 0; A[i][j].k = 1;中的冗余运算； • 语义不变的优化 – 公共子表达式消除 – 复制传播 – 死代码消除 – 常量折叠
优化的例子(1) ·快速排序算法 void quicksort(int m, int n) /*递归地对a[m]和a[n]之间的元素排序*/ int 1, J int v. x: if (n v); if (i >=j) break; x=a[i;a[i=a[j;aj=x;/*对换a[i]和a[j*/ x=a[i;a[i]=a[n];a[n]=x;/*对换a[i]和a[n]* /*片断在此结束*/ quicksort (m,j); quicksort(i+1, n);
优化的例子（1） • 快速排序算法
优化的例子(2) 三地址代码 (1)i (16)t7=4*i (2)j (17)t8=4*j (3)t1=4*n (18)t9=a[t8] (4)y=a[t1] (19) [t7]=t9 (5)i=i+1 (20)t10=4*j (6)t2=4*i (21)a[t10]=x (7)t3=a[t2] (22) goto (5 (8) if t3v goto ( 9) (27)t14=a[t13] (13) if i>=j goto(23) (28)a[t12]=t14 (14)t6=4*i (29)t15=4*n (15)x=a[t6 (30)a[t15]=x
优化的例子（2） • 三地址代码
Quicksort的流图 t1=4 v a[tl] +1 循环 itt 23f 4*i t3v goto B 2、 B 3、D4 if i>=3 goto B B t6=4*i t11=4*i B [t6] [t11] t t12=4*i t8=4* t9=a[t8] [t13] a[t7]=t9 a[t12 t14 t10=4* t15=4*n a[t15 goto B
Quicksort的流图 • 循环： – B2 – B3 – B2、B3、B4、 B5
全局公共子表达式 如果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 t3v 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 t3v 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的使用