第九章机器无关的优化 许畅 南京大学计算机系 2022年春季 版权所有南京大学计算机科学与技术系许畅2022春季版
许畅 南京大学计算机系 2022年春季 第九章 机器无关的优化 版权所有 南京大学计算机科学与技术系 许畅 2022春季版 南大编译许畅
主要内容 引言 ·优化的来源 ·数据流分析 许畅 。 部分冗余消除 0 循环的识别、分析和优化 2
主要内容 • 引言 • 优化的来源 • 数据流分析 • 部分冗余消除 • 循环的识别、分析和优化 2 南大编译许畅
引言 。代码优化或者代码改进 在目标代码中消除不必要的指令 把一个指令序列替换为一个完成相同功能的更快的指 令序列 。全局优化 具体的优化实现基于数据流分析技术 用以收集程序相关信息的算法 3
引言 • 代码优化或者代码改进 – 在目标代码中消除不必要的指令 – 把一个指令序列替换为一个完成相同功能的更快的指 令序列 • 全局优化 – 具体的优化实现基于数据流分析技术 – 用以收集程序相关信息的算法 3 南大编译许畅
优化的主要来源 编译器只能通过一些相对低层的语义等价转换来 优化代码 冗余运算的原因 源程序中的冗余 高级程序设计语言编程的副产品，如A[][].f=0;A[][1k=1; 语义不变的优化 公共子表达式消除 。 复制传播 死代码消除 常量折叠 4
优化的主要来源 • 编译器只能通过一些相对低层的语义等价转换来 优化代码 – 冗余运算的原因 • 源程序中的冗余 • 高级程序设计语言编程的副产品，如A[i][j].f = 0; A[i][j].k = 1; – 语义不变的优化 • 公共子表达式消除 • 复制传播 • 死代码消除 • 常量折叠 4 南大编译许畅
优化的例子(1) 快速排序算法 void quicksort(int m,int n) /*递归地对a[m]和a[n]之间的元素排序*/ { int i,j; int v,x; if (n =j)break; x=a[i];a[i]=a[j门；a[j]=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); 5
优化的例子 (1) • 快速排序算法 5 南大编译许畅
优化的例子(2) 三地址代码 1) i=m-1 (16) t7=4*1 984 j=n (17) t8=4*j t1=4*n (18) t9 =a[t8] =a[t1] (19) a[t7]=t9 (5) i=i+1 (20) t10=4*j t2=4*1 (21) a[t10]=x 6789 t3 =a[t2] (22) goto (5) if t3v goto (9) (27) t14 =a[t13] (13) if i>=j goto (23) (28) a[t12] =t14 (14) t6 =4*1 (29) t15= 4*n (15) X =a[t6] (30) a[t15] X 6
优化的例子 (2) • 三地址代码 6 南大编译许畅
i=m-1 流图 Bv j=n t1=4*n v=a[t1】 循环 i=i+1 B2 t2-4*i1 B2 t3 a[t2] if t3v goto B3 if i>=j goto B6 B4 t6=4*1 B5 t11=4*1 B6 x a[t6] x a[tll] t7=4*1 t12=4*i t8=4*j t13=4*n t9=a[t8] t14=a[t13] a[t7]=t9 a[t12】=t14 t10=4*j t15=4*n a[t10]=x a[t15]=x goto B2 7
• 循环– B2 – B3 – B2 , B 3 , B 4 , B 5 7 流图 南大编译许畅
全局公共子表达式 t6=4*1 X a[t6] t7=4*1 t8=4*j t9=a[t8] 如果E a[t7]=t9 t10=4*j 在某次出现之前必然已被计 a[t10]=x 算过，且 goto B2 a)消除之前 E的运算分量在该次计算之 t6= 后没有被改变 4*i =a[t6] t8= 那么，E的本次出现就是一 4*j t9 a[t8] 个公共子表达式 t7=>t6 a[t61=t9 t10=>t8 a[t8] X 。如果上次E值赋给了x,且x goto B2 值没有被修改过，那么我 b)消除之后 例子： 们可使用x,而无需计算E t7=4*i t10=4*j 不需要重新计算 8
全局公共子表达式 • 如果E – 在某次出现之前必然已被计 算过，且 – E的运算分量在该次计算之 后没有被改变 – 那么，E的本次出现就是一 个公共子表达式 • 如果上次E值赋给了x，且x 值没有被修改过，那么我 们可使用x，而无需计算E 8 例子： t7 = 4 * i t10 = 4 * j 不需要重新计算 t7 => t6 t10 => t8 南大编译许畅
例子 i=m-1 B j=n t1=4*n v a[tl] B2,B3中计算了4*i,4* j,且到达B之前必然 1=i+1 B2 t2=4*1 经过B2,B3 t3=a[t2] if t3v goto B B中赋给x的值(a[t6) 和B2中赋给3的值 if i>=j gotoB6 Ba (a[t2])相同 t4替换t8后，B中a[t8] t6=4*1 6夕 t11=4*1 Bo x a[t6] t6,t7 x=a[t11] 和B3中a[t4]又相同 t7=4*1 t12=4*i t8=4*j =>t2 t13=4*n B。中的a[t13]和B1中的 t9=a[t8] t14=a[t13j a[t7】=t9 a[t12]=t14 a[t1]不同，因为B5可 t10=4*1 a[t10]=x t8,t10 t15=4*n a[t15]=x 能改变a的值 goto B2 =>4 9
9 例子 t6, t7 => t2 t8, t10 => t4 – B 2 , B 3中计算了4 * i, 4 * j，且到达 B 5之前必然 经过 B 2 , B 3 – t2, t4在赋值后没有被 改变过，因此 B 5中可 直接使用它们 – B 5中赋给 x的值 (a[t6]) 和 B 2中赋给t3的值 (a[t2]) 相同 – t4替换t8后， B 5 中a[t8] 和 B 3 中a[t4]又相同 – B 6中的a[t13] 和 B 1中的 a[t1]不同，因为 B 5 可 能改变 a的值 南大编译许畅
消除以后 i=m-1 B j=n t1=4*n v a[t1] i=i+1 B2 t2=4*1 t3=a[t2 if t3v goto B3 if i>=j goto B BA x t3 B5 x t3 B6 a[t2]=t5 t14=a[t1] a[t4]x a[t2] =t14 goto B2 a[t1】=x 图9-5经过公共子表达式消除之后的B,和B。 10
10 消除以后 南大编译许畅