第九章独立于机器的优化 源程序 符号表 词法分析器 独立于机器的代码优化器 语法分析器 代码生成器 语义分析器 依赖于机器的代码优化器 中间代码生成器 目标机器代码
第九章 独立于机器的优化 词法分析器 语法分析器 语义分析器 源程序 中间代码生成器 独立于机器的代码优化器 代码生成器 依赖于机器的代码优化器 目标机器代码 符号表
第九章独立于机器的优化 代码优化 通过程序变换(局部变换和全局变换)来改进程 序,称为优化 代码改进变换的标准 代码变换必须保程序的含义 采取安全稳妥的策略 变换减少程序的运行时间平均达到一个可度量的 值 变换所作的努力是值得的
第九章 独立于机器的优化 • 代码优化 –通过程序变换（局部变换和全局变换）来改进程 序，称为优化 • 代码改进变换的标准 –代码变换必须保程序的含义 –采取安全稳妥的策略 –变换减少程序的运行时间平均达到一个可度量的 值 –变换所作的努力是值得的
第九章独立于机器的优化 本章介绍独立于机器的优化,即不考虑任何 依赖目标机器性质的优化变换 通过实例来介绍代码改进的主要机会 数据流分析包括的几类重要的全局收集的信息 数据流分析的一般框架 和一般框架有区别的常量传播 部分冗余删除的优化技术 循环的识别和分析
第九章 独立于机器的优化 • 本章介绍独立于机器的优化，即不考虑任何 依赖目标机器性质的优化变换 – 通过实例来介绍代码改进的主要机会 – 数据流分析包括的几类重要的全局收集的信息 – 数据流分析的一般框架 – 和一般框架有区别的常量传播 – 部分冗余删除的优化技术 – 循环的识别和分析
91优化的主要种类 911优化的主要源头 程序中存在许多程序员无法避免的冗余运算 对于A[j]和X这样访问数组元素和结构体的 域的操作(例如,A[il[jl=A[iji+10) 随着程序被编译,这些访问操作展开成多步低级 算术运算 对同一个数据结构的多次访问导致许多公共的低 级运算 程序员没有办法删除这些冗余
9.1 优化的主要种类 9.1.1 优化的主要源头 • 程序中存在许多程序员无法避免的冗余运算 – 对于A[i][j]和X.f1这样访问数组元素和结构体的 域的操作（例如， A[i][j] = A[i][j] + 10） – 随着程序被编译，这些访问操作展开成多步低级 算术运算 – 对同一个数据结构的多次访问导致许多公共的低 级运算 – 程序员没有办法删除这些冗余
91优化的主要种类 912一个实例 m-1;j=n;v=an; (1)i=m-1 while (1)i n do i=i+l; while(aiv); 3)t,=4 *n do j=j-1; while(alr>v); (4)v=at, if(i>=j break (5)i=i+1 X=all: al=ali: alllEx (6)t2=4* t3=atl x=ali; ali=aInI; an=x;(8)if t3<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)
91优化的主要种类 912一个实例 m-1;j=n;v=an; (9)j=j-1 while (1)i 10)t4=4*j do i=i+l; while(ai]v) do j=j-l; while(ail>);(12)if ts>v goto(9) if(i>=j break (13)if i>=j goto(23) X=all: al=ali: alllEx (15)x=a|t6l x=ai; aian: an=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优化的主要种类 m B n 4*n 程序流图 atI B 4* v goto B B 3 ts>v goto B j goto B B4 B B
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 • 程序流图
91优化的主要种类 913公共子表达式删除 Bs x=ai;a=ajl; ajl=x; t=4*i at6 * 4 a at,l= to 10=4*j atol 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
91优化的主要种类 局部公共子表达式删除,复写传播,删除死代码 Bs x=ai;a=ajl; ajl=x; t=4*i at6 X=a[t6 44a ** a t6 =tg at,l= to at=x 10=4*j goto B2 atol 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优化的主要种类 m B n 事n atul t2=4*i t3 v goto B 团ii>= j goto B|B B
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