第九章机器无关的优化 赵建华 南京大学计算机系
第九章 机器无关的优化 赵建华 南京大学计算机系
优化的主要来源 ·编译器只能通过一些相对低层的语义等价转换 来优化代码; ·冗余运算的原因 源程序中的冗余; 高级程序设计语言编程的副产品 比如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 <=m) return; /*片断由此开始*/ 1;j=n;v=a[n] while(1) i do i =1+1; while (a[i< v) do j=j-1; while (a[j]>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 t3<v goto(5) (23)t11=4*i (9) (24)x=a[t11] (10)t4=4*j (25)t12=4*i (11)t5=a[t4] (26 t13=4*n (12) if t5>v 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 t3<v goto B B B B tti 45至 [t4] B t5>v 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