第九章 独立于机器的优化 源程序 符号表 词法分析器 独立于机器的代码优化器 语法分析器 代码生成器 语义分析器 依赖于机器的代码优化器 中间代码生成器 目标机器代码
第九章 独立于机器的优化 词法分析器 语法分析器 语义分析器 源程序 中间代码生成器 独立于机器的代码优化器 代码生成器 依赖于机器的代码优化器 目标机器代码 符号表
第九章 独立于机器的优化 代码优化 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); (3)t1=4*n do j =j-1;while (aljl>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); (3) t1 = 4 n do j =j −1;while (a[j]>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)