第九章 独立于机器的优化 源程序 符号表 词法分析器 独立于机器的代码优化器 语法分析器 代码生成器 语义分析器 依赖于机器的代码优化器 中间代码生成器 目标机器代码
第九章 独立于机器的优化 词法分析器 语法分析器 语义分析器 源程序 中间代码生成器 独立于机器的代码优化器 代码生成器 依赖于机器的代码优化器 目标机器代码 符号表
第九章 独立于机器的优化 代码优化 1 通过程序变换 (局部变换和全局变换)来改进程 序，称为优化 ·代码改进变换的标准 代码变换必须保程序的含义 采取安全稳妥的策略 变换减少程序的运行时间平均达到一个可度量的 值 变换所作的努力是值得的
第九章 独立于机器的优化 • 代码优化 –通过程序变换（局部变换和全局变换）来改进程 序，称为优化 • 代码改进变换的标准 –代码变换必须保程序的含义 –采取安全稳妥的策略 –变换减少程序的运行时间平均达到一个可度量的 值 –变换所作的努力是值得的
第九章 独立于机器的优化 本章介绍独立于机器的优化，即不考虑任何 依赖目标机器性质的优化变换 通过实例来介绍代码改进的主要机会 数据流分析包括的几类重要的全局收集的信息 数据流分析的一般框架 和一般框架有区别的常量传播 部分冗余删除的优化技术 循环的识别和分析
第九章 独立于机器的优化 • 本章介绍独立于机器的优化，即不考虑任何 依赖目标机器性质的优化变换 – 通过实例来介绍代码改进的主要机会 – 数据流分析包括的几类重要的全局收集的信息 – 数据流分析的一般框架 – 和一般框架有区别的常量传播 – 部分冗余删除的优化技术 – 循环的识别和分析
9.1优化的主要种类 9.1.1优化的主要源头 程序中存在许多程序员无法避免的冗余运算 对于A[和X.f1这样访问数组元素和结构体的 域的操作（例如，A]=A][]+10) 随着程序被编译，这些访问操作展开成多步低级 算术运算 对同一个数据结构的多次访问导致许多公共的低 级运算 -程序员没有办法删除这些冗余
9.1 优化的主要种类 9.1.1 优化的主要源头 • 程序中存在许多程序员无法避免的冗余运算 – 对于A[i][j]和X.f1这样访问数组元素和结构体的 域的操作（例如， A[i][j] = A[i][j] + 10） – 随着程序被编译，这些访问操作展开成多步低级 算术运算 – 对同一个数据结构的多次访问导致许多公共的低 级运算 – 程序员没有办法删除这些冗余
9.1优化的主要种类 9.1.2一个实例 i=m-1;j=n;v=an]; (1)i=m-1 while (1) (2)j=n do i=i+1;while(ali]v); (4)v=alt] if (i >j)break; (5)i=i+1 x=ai];ai=alil;all=x; (6)t2=4*i (7)t3=alt] x=ai;a i=a n a n=x; (⑧)ift<v goto(5)
9.1 优化的主要种类 9.1.2 一个实例 i = m −1; j = n; v = a[n]; (1) i = m −1 while (1) { (2) j = n do i = i +1; while(a[i]v); (4) v = a[t1 ] if (i >= j) break; (5) i = i + 1 x=a[i]; a[i]=a[j]; a[j]=x; (6) t2 = 4 i } (7) t3 = a[t2 ] x=a[i]; a[i]=a[n]; a[n]=x; (8) if t3 < v goto (5)
9.1优化的主要种类 9.1.2一个实例 i=m-1;j=n;v=an]; (9)j=j-1 while (1) (10)t4=4*j do i=i+1;while(ali]v); (12)if ts>v goto (9) if (i >j)break; (13)ifi>=j goto (23) x=ai];ai=alil;all=x; (14)t6=4*i (15)x=at6 x=ai;a i=a n a n=x;
9.1 优化的主要种类 9.1.2 一个实例 i = m −1; j = n; v = a[n]; (9) j = j −1 while (1) { (10) t4 = 4 j do i = i +1; while(a[i]v); (12) if t5>v goto (9) if (i >= j) break; (13) if i >=j goto (23) x=a[i]; a[i]=a[j]; a[j]=x; (14) t6 = 4 i } (15 ) x = a[t6 ] x=a[i]; a[i]=a[n]; a[n]=x; . .
9.1优化的主要种类 三m一 B n =4*n ·程序流图 V= a[ti] B goto B2 B: 4* alt goto B3 ifi>=j goto B Bs B6
9.1 优化的主要种类 i = m −1 j = n t1 = 4 n v = a[t1 ] i = i + 1 t2 = 4 i t3 = a[t2 ] if t3 v goto B3 if i >= j goto B6 B4 B3 B5 B6 • 程序流图
9.1优化的主要种类 9.1.3公共子表达式删除 B x=ali];ali=aljl;alj=x; to =4*i X= alt] t7=4*i ts 4*j t,a[ts] a[t] t10=4*j a[tio] =x goto B2
9.1 优化的主要种类 9.1.3 公共子表达式删除 B5 x=a[i]; a[i]=a[j]; a[j]=x; t6 = 4 i x = a[t6 ] t7 = 4 i t8 = 4 j t9 = a[t8 ] a[t7 ] = t9 t10 = 4 j a[t10] = x goto B2
9.1优化的主要种类 局部公共子表达式删除，复写传播，删除死代码 B5 x=ali];alialjl;a=x; =4*1 =4*1 alt] X= altol t7=4*i t8=4*j 4*j a[ts] a[tsl alt a[t] to ats] =X t10=4*j goto B2 a[tio]x goto B2
9.1 优化的主要种类 局部公共子表达式删除, 复写传播, 删除死代码 B5 x=a[i]; a[i]=a[j]; a[j]=x; t6 = 4 i x = a[t6 ] t7 = 4 i t8 = 4 j t9 = a[t8 ] a[t7 ] = t9 t10 = 4 j a[t10] = x goto B2 t6 = 4 i x = a[t6 ] t8 = 4 j t9 = a[t8 ] a[t6 ] = t9 a[t8 ] = x goto B2
9.1优化的主要种类 m一 B n *n V= a[ti 4*i at V goto B2 4* alt goto B3 ifi>=j goto B Bs B6
9.1 优化的主要种类 i = m −1 j = n t1 = 4 n v = a[t1] i = i + 1 t2 = 4 i t3 = a[t2] if t 3 v goto B 3 if i >= j goto B 6 B 4 B 3 B 5 B 6