编译原理独立于机器的优化9.ppt
《编译原理独立于机器的优化9.ppt》由会员分享,可在线阅读,更多相关《编译原理独立于机器的优化9.ppt(134页珍藏版)》请在三一文库上搜索。
1、第九章 独立于机器的优化,通过程序变换(局部变换和全局变换)来改 进程序,称为优化 代码改进变换的标准 代码变换必须保程序的含义 采取安全稳妥的策略 变换减少程序的运行时间平均达到一个可度量的值 变换所作的努力是值得的,第九章 独立于机器的优化,本章介绍独立于机器的优化,即不考虑任何依赖目标机器性质的优化变换 通过实例来介绍代码改进的主要机会 数据流分析包括的几类重要的全局收集的信息 数据流分析的一般框架 和一般框架有区别的常量传播 部分冗余删除的优化技术 循环的识别和分析,9.1 优化的主要种类,9.1.1 优化的主要源头 程序中存在许多程序员无法避免的冗余运算 通过像Aij和X.f1的方式
2、引用数组元素和结构的域 随着程序被编译,对这样高级数据结构的访问展开成多步低级算术运算 对同一个数据结构的多次访问导致许多公共的低级运算 程序员没有办法删除这些冗余,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(aiv); (4) v = at1 if (i = j) break; (5) i = i + 1 x=ai; ai=aj; aj=x; (6) t2 = 4 i (7) t3 = at2 x=ai; ai=an; an=x; (8) i
3、f 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(aiv); (12) if t5v goto (9) if (i = j) break; (13) if i =j goto (23) x=ai; ai=aj; aj=x; (14) t6 = 4 i (15 ) x = at6 x=ai; ai=an; an=x; . . .,9.1 优化的主要种类,9.1 优化的主要种类,9.1.3 公共子表达式删除 B5
4、x=ai; ai=aj; aj=x;,t6 = 4 i x = at6 t7 = 4 i t8 = 4 j t9 = at8 at7 = t9 t10 = 4 j at10 = x goto B2,9.1 优化的主要种类,B5 x=ai; ai=aj; aj=x;,t6 = 4 i x = at6 t7 = 4 i t8 = 4 j t9 = at8 at7 = t9 t10 = 4 j at10 = x goto B2,t6 = 4 i x = at6 t8 = 4 j t9 = at8 at6 = t9 at8 = x goto B2,9.1 优化的主要种类,9.1 优化的主要种类,B5
5、x=ai; ai=aj; aj=x;,t6 = 4 i x = at6 t7 = 4 i t8 = 4 j t9 = at8 at7 = t9 t10 = 4 j at10 = x goto B2,t6 = 4 i x = at6 t8 = 4 j t9 = at8 at6 = t9 at8 = x goto B2,9.1 优化的主要种类,B5 x=ai; ai=aj; aj=x;,t6 = 4 i x = at6 t7 = 4 i t8 = 4 j t9 = at8 at7 = t9 t10 = 4 j at10 = x goto B2,t6 = 4 i x = at6 t8 = 4 j t
6、9 = at8 at6 = t9 at8 = x goto B2,x = at2 t9 = at4 at2 = t9 at4 = x goto B2,9.1 优化的主要种类,9.1 优化的主要种类,B5 x=ai; ai=aj; aj=x;,t6 = 4 i x = at6 t7 = 4 i t8 = 4 j t9 = at8 at7 = t9 t10 = 4 j at10 = x goto B2,t6 = 4 i x = at6 t8 = 4 j t9 = at8 at6 = t9 at8 = x goto B2,x = at2 t9 = at4 at2 = t9 at4 = x goto
7、B2,9.1 优化的主要种类,B5 x=ai; ai=aj; aj=x;,t6 = 4 i x = at6 t7 = 4 i t8 = 4 j t9 = at8 at7 = t9 t10 = 4 j at10 = x goto B2,t6 = 4 i x = at6 t8 = 4 j t9 = at8 at6 = t9 at8 = x goto B2,x = at2 t9 = at4 at2 = t9 at4 = x goto B2,x = t3 at2 = t5 at4 = x goto B2,9.1 优化的主要种类,B6 x = ai; ai = an; an = x;,t11 = 4 i
8、 x = at11 t12 = 4 i t13 = 4 n t14 = at13 at12 = t14 t15 = 4 n at15 = x,x = t3 t14 = at1 at2 = t14 at1 = x,9.1 优化的主要种类,B6 x = ai; ai = an; an = x; at1能否作为公共子表达式?,t11 = 4 i x = at11 t12 = 4 i t13 = 4 n t14 = at13 at12 = t14 t15 = 4 n at15 = x,x = t3 t14 = at1 at2 = t14 at1 = x,9.1 优化的主要种类,9.1 优化的主要种类,
9、9.1.4 复写传播 形成为f = g的赋值叫做复写语句 优化过程中会大量引入复写,9.1 优化的主要种类,9.1.4 复写传播 形成为f = g的赋值叫做复写语句 优化过程中会大量引入复写 复写传播变换的做法是在复写语句f = g后,尽可能用g代表f,x = t3 at2 = t5 at4 = t3 goto B2,x = t3 at2 = t5 at4 = x goto B2,9.1 优化的主要种类,9.1.4 复写传播 形成为f = g的赋值叫做复写语句 优化过程中会大量引入复写 复写传播变换的做法是在复写语句f = g后,尽可能用g代表f 复写传播变换本身并不是优化,但它给其它优化带来
10、机会 常量合并 死代码删除,9.1 优化的主要种类,9.1.5 死代码删除 死代码是指计算的结果决不被引用的语句 一些优化变换可能会引起死代码 例: debug = true; debug = false; . . . 测试后改成 . . . if (debug) print if (debug) print ,9.1 优化的主要种类,9.1.5 死代码删除 死代码是指计算的结果决不被引用的语句 一些优化变换可能会引起死代码 例:复写传播可能会引起死代码删除,x = t3 at2 = t5 at4 = t3 goto B2,at2 = t5 at4 = t3 goto B2,9.1 优化的主要
11、种类,9.1.6 代码外提 代码外提是循环优化的一种 循环优化的其它重要技术 归纳变量删除 强度削弱 例:while (i = limit 2 ) 变换成 t = limit 2; while (i = t ) ,9.1 优化的主要种类,9.1.7 强度削弱和归纳变量删除 j和t4的值步伐一致地变化 这样的变量叫做归纳变量 在循环中有多个归纳变量时, 也许只需要留下一个 这个操作由归纳变量删除 过程来完成 对本例可以先做强度削弱 它给删除归纳变量创造机会,9.1 优化的主要种类,j = j 1 t4 = 4 j t5 = at4 if t5 v goto B3,B3,除第一次外, t4 = 4
12、 j在B3的入口一定保持 在j = j 1后, 关系t4 = 4 j + 4也 保持,9.1 优化的主要种类,9.1 优化的主要种类,9.2 数据流分析介绍,9.2.1 数据流抽象 点 基本块中,两个相邻的语句之间为程序的一个点 基本块的开始点和结束点 路径 点序列p1, p2, , pn,对1和n - 1间的每个i,满足 pi是先于一个语句的点,pi1是同一块中位于该语句后的点,或者 pi是某块的结束点,pi1是后继块的开始点,9.2 数据流分析介绍,9.2.1 数据流抽象 路径实例 -(1, 2, 3, 4, 9) -(1, 2, 3, 4, 5, 6, 7, 8, 3, 4, 9),9.
13、2 数据流分析介绍,9.2.1 数据流抽象 分析程序的行为时,必须在其流图上考虑所有的执行路径(在调用或返回语句被执行时,还需要考虑路径在多个流图之间的跳转) 然后从每个程序点的所有可能状态中抽取解决特定数据流分析所需信息 通常,从流图得到的程序执行路径数无限,且执行路径长度没有有限的上界 程序分析从程序点的所有可能状态中为该点总结出一组有限的事实,9.2 数据流分析介绍,9.2.1 数据流抽象 明了所有路径上所有程序状态是不可能的 数据流分析不打算区分到达一个程序点的不同路径,也不试图掌握完整的状态 它抽取出某些细节,以获取用于分析目的的数据 从同样的状态,根据程序分析的不同目的,可以提炼出
14、不同的信息,9.2 数据流分析介绍,9.2.1 数据流抽象 点(5)所有程序状态: - a 1, 243 - 由d1, d3定值 1、到达定值 - d1, d3的定值 到达点(5) 2、常量合并 - a在点(5)不是 常量,9.2 数据流分析介绍,9.2.2 数据流分析模式 数据流值 数据流分析总把程序点和数据流值联系起来 数据流值代表在程序点能观测到的所有可能程序状态集合的一个抽象 语句s前后两点数据流值用INs和OUTs来表示 数据流问题就是通过基于语句语义的约束(迁移函数)和基于控制流的约束来寻找所有语句s的INs和OUTs 的一个解,9.2 数据流分析介绍,9.2.2 数据流分析模式
15、迁移函数 f 语句前后两点的数据流值受该语句的语义约束 沿执行路径正向传播 OUTs = fs(INs) 沿执行路径逆向传播 INs = fs(OUTs) 基本块B由语句s1, s2, , sn依次组成 INsi+1 = OUTsi, i = 1, 2, , n1 fB = fn . . . f2 f1 (逆向 fB = f1 . . . fn - 1 fn ) OUTB = fB (INB) (逆向 INB = fB (OUTB) ),9.2 数据流分析介绍,9.2.2 数据流分析模式 控制流约束 正向传播 INB = P是B的前驱OUTP 逆向转播 OUTB = S是B的后继INS 约束方
16、程组通常不是唯一解 求解的目标是要找到满足这两组约束(控制流约束和迁移约束)的最“精确”解,9.2 数据流分析介绍,9.2.3 到达-定值 到达程序点的所有定值 可用来判断一个变量在某程序点是否为常量 可用来判断一个变量在某程序点是否无初值 别名给到达-定值的计算带来困难 过程参数、数组访问、间接引用等都可能引起别名 如何判断对p-next的赋值没有改变q-next 程序分析必须是稳妥的 本章其余部分仅考虑变量无别名的情况,9.2 数据流分析介绍,9.2.3 到达-定值 到达程序点的所有定值 可用来判断一个变量在某程序点是否为常量 可用来判断一个变量在某程序点是否无初值 别名给到达-定值的计算
17、带来困难 注销 在一条路径上,先前对x的赋值被后面对x的赋值所注销,9.2 数据流分析介绍,gen和kill分别表示基本块生成和注销的定值,9.2 数据流分析介绍,基本块的gen和kill是怎样计算的 对三地址指令 d: u = v + w,它的迁移函数是 fd(x) = gend (x killd) 若f1(x) = gen1 (x kill1), f2(x) = gen2 (x kill2) f2(f1(x) = gen2 (gen1 (x kill1) kill2) = (gen2 (gen1 kill2) (x (kill1 kill2) 若基本块B有n条三地址指令 killB = k
18、ill1 kill2 killn genB = genn (genn1 killn) (genn2 killn1 killn) (gen1 kill2 kill3 killn),9.2 数据流分析介绍,到达-定值的数据流等式 genB:B中能到达B的结束点的定值语句 killB:整个程序中决不会到达B结束点的定值 inB:能到达B的开始点的定值集合 outB:能到达B的结束点的定值集合 两组等式(根据gen和kill定义in和out) inB = P是B的前驱 outP outB = genB (inB killB) outENTRY = 到达-定值方程组的迭代求解,9.2 数据流分析介绍,i
19、n B out B B1 000 0000 000 0000 B2 000 0000 000 0000 B3 000 0000 000 0000 B4 000 0000 000 0000,gen B1 = d1, d2, d3 kill B1=d4, d5, d6, d7,gen B2 = d4, d5 kill B2 = d1, d2, d7,gen B3 = d6 kill B3 = d3,gen B4 = d7 kill B4 = d1, d4,9.2 数据流分析介绍,in B out B B1 000 0000 000 0000 B2 000 0000 000 0000 B3 000
20、0000 000 0000 B4 000 0000 000 0000,gen B1 = d1, d2, d3 kill B1=d4, d5, d6, d7,gen B2 = d4, d5 kill B2 = d1, d2, d7,gen B3 = d6 kill B3 = d3,gen B4 = d7 kill B4 = d1, d4,9.2 数据流分析介绍,in B out B B1 000 0000 111 0000 B2 000 0000 000 0000 B3 000 0000 000 0000 B4 000 0000 000 0000,gen B1 = d1, d2, d3 kill
21、 B1=d4, d5, d6, d7,gen B2 = d4, d5 kill B2 = d1, d2, d7,gen B3 = d6 kill B3 = d3,gen B4 = d7 kill B4 = d1, d4,9.2 数据流分析介绍,in B out B B1 000 0000 111 0000 B2 111 0000 000 0000 B3 000 0000 000 0000 B4 000 0000 000 0000,gen B1 = d1, d2, d3 kill B1=d4, d5, d6, d7,gen B2 = d4, d5 kill B2 = d1, d2, d7,gen
22、 B3 = d6 kill B3 = d3,gen B4 = d7 kill B4 = d1, d4,9.2 数据流分析介绍,in B out B B1 000 0000 111 0000 B2 111 0000 001 1100 B3 000 0000 000 0000 B4 000 0000 000 0000,gen B1 = d1, d2, d3 kill B1=d4, d5, d6, d7,gen B2 = d4, d5 kill B2 = d1, d2, d7,gen B3 = d6 kill B3 = d3,gen B4 = d7 kill B4 = d1, d4,9.2 数据流分
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 编译 原理 立于 机器 优化
链接地址:https://www.31doc.com/p-4142464.html