《南开大学编译原理第十章》由会员分享，可在线阅读，更多相关《南开大学编译原理第十章（189页珍藏版）》请在金锄头文库上搜索。
1、第十章 代码优化,学习内容,优化种类 循环 全局数据流分析 利用数据流信息进行全局优化,概述,目标机器无关的优化 找出程序中执行最频繁的部分 内层循环 数据流分析,10.1 引言,10.1.1 代码改进变换的标准 意义保持不变 提高速度，减小大小 代价适中,10.1.2 获得最佳性能,贯穿本章的例子,void quicksort(int m, int n) int i, j; int v, x; if (n v); if (i = j) break; x = ai; ai = aj; aj = x; x = ai; ai = an; an = x; quicksort(m, j); quick
2、sort(i + 1, n); ,10.1.3 优化编译器的组织结构,优点 中间代码展现细节，便于优化 与目的机器无关,例10.1,i := m 1 j := n t1 := 4 * n v := at1,i := i + 1 t2 := 4 * i t3 := at2 if t3 v goto B2,j := j - 1 t4 := 4 * j t5 := at4 if t5 v goto B3,if i = j goto B6,t6 := 4 * i x := at6 t7 := 4 * i t8 := 4 * j t9 := at8 at7 := t9 t10 := 4 *j at10
3、:= x goto B2,t11 := 4 * i x := at11 t12 := 4 * i t13 := 4 * n t14 := at13 at12 := t14 t15 := 4 * n at15 := x,B1,B2,B3,B4,B5,B6,10.2 主要优化种类,局部（local）优化：局限基本块内 全局（global）优化 10.2.1 保持功能的变换,10.2.2 消去公共子表达式,t6 := 4 * i x := at6 t7 := 4 * i t8 := 4 * j t9 := at8 at7 := t9 t10 := 4 *j at10 := x goto B2,t6
4、:= 4 * i x := at6 t8 := 4 * j t9 := at8 at6 := t9 at8 := x goto B2,B5,B5,例10.2,i := m 1 j := n t1 := 4 * n v := at1,i := i + 1 t2 := 4 * i t3 := at2 if t3 v goto B2,j := j - 1 t4 := 4 * j t5 := at4 if t5 v goto B3,if i = j goto B6,x := t3 at2 := t5 at4 := x goto B2,x := t3 t14 := at1 at2 := t14 at1
5、:= x,B1,B2,B3,B4,B5,B6,10.2.3 复制传播,f := g在随后语句中，用g替换f,a := d + e,b := d + e,c := d + e,t := d + e a := t,t := d + e b := t,c := t,x := t3 at2 := t5 at4 := x goto B2,B5,x := t3 at2 := t5 at4 := t3 goto B2,B5,10.2.4 无用代码删除,debug := false if (debug) print . 利用复制传播，debug替换为false（常量合并，constant folding） i
6、f语句被删除,x := t3 at2 := t5 at4 := x goto B2,B5,at2 := t5 at4 := t3 goto B2,B5,10.2.5 循环的优化,程序中运行最频繁的部分 代码外提，code motion 删除归纳变量， induction-variable elimination 强度削弱，reduction strength,10.2.6 代码外提,表达式计算与循环次数无关（循环不变计算，loop-invariant computation） 循环内循环入口前 while (i = limit 2) t = limit 2; while (i t),例10.4
7、 强度削弱,例10.5 删除归纳变量,i := m 1 j := n t1 := 4 * n v := at1 t2 := 4 * i t4 := 4 * j,t2 := t2 + 4 t3 := at2 if t3 v goto B2,t4 := t4 - 4 t5 := at4 if t5 v goto B3,if t2 = t4 goto B6,at2 := t5 at4 := t3 goto B2,t14 := at1 at2 := t14 at1 := t3,B1,B2,B3,B4,B5,B6,t2 = t4与 i = j等价,10.3 基本块的优化,例10.5：基本块的dag表示,
8、a := b + c b := a d c := b + c d : = a - d,a := b + c d := a d c := d + c,若b不活跃,dag的局限,语句1和语句4的等价性无法发现 a := b + c b := b d c := c + d d := b + c,利用代数恒等进行优化,代数恒等 x + 0 = 0 + x = x x 0 = x x * 1 = 1 * x = x x / 1 = x 降低强度 x * 2 = x * x 2.0 * x = x + x x / 2 = x * 0.5 常量合并 2 * 3.14 6.28,dag辅助代数优化,x * y
9、 = y * x：在dag节点创建中进行额外检查 x y x y 结合 标志寄存器检测 结合率 a := b + c e := c + d + b a := b + c t := c + d e := t + b 优化 a := b + c e := a + d,10.4 流图中的循环,d支配（dominate）n：从流图的开始节点到n的任何路径都经过d，d dom n,直接支配者， immediate dominator 任何路径上都是最后一个支配者,10.4.2 循环的判定,具有唯一入口点，“header”，它应支配循环中所有节点，否则就不是唯一入口点 至少有一条路径返回首节点 找出回边b
10、ack edge 边ab，b支配a 例10.7：上例流图中的回边 74，107，43，83，91,循环的判定（续）,自然循环，natural loop 回边nd，d及不经过d可到达n的节点集合，d首节点 例10.8： 107的自然循环：7、8、10 91的自然循环：所有节点,算法10.1 构造自然循环,输入：流图G和一条回边 nd 输出：nd对应的自然循环的节点集合,void insert(m) if (m不在loop中) loop = loop m; m压栈到stack; ,主程序 stack设置为空; loop := d; insert(n); while (stack不空) pop m;
11、 for (m的每个前驱p) insert(p); ,10.4.3 内层循环（inner loop）,两个循环若无相同首节点，则：或者不相交，或者嵌套 内层循环：不包含其他循环的循环 相同首节点情况：可看作一个循环,B0,B1,B3,B2,10.4.4 Pre-Header,循环L，创建前置节点，preheader 只有一个后继L的首节点 所有L外指向首节点的边指向前置节点 代码外提,header,loop L,preheader,header,loop L,10.4.5 可约流图,循环外到循环内的转移 流图G可约的充要条件 所有边可划分为两个不相交的集合前向边和回边，且满足： 前向边构成一个
12、dag，且从G的开始节点，可到达其他任何节点 回边：前面定义,例10.9,虚线：回边 其他：前向边,例10.10 不可约的流图,例10.11,内层循环：7, 8, 10 4, 5, 6, 7不是循环 外层循环：4, 5, 6, 7, 8, 10 更外层循环：3,4,5,6,7,8,10 更外层循环：整个流图,10.5 全局数据流分析,数据流信息解方程组 数据流方程 outS = genS(inS killS) 含义：语句结束处的信息 或者是语句生成的信息 或者是语句开始时的信息去除语句执行中注销的信息,数据流方程创建求解的因素,“生成”、“注销”的概念依赖于求解问题一般inSoutS，还可能o
13、utSinS 数据流分析依赖于程序的控制流语句outS语句有唯一出口 方程基本块层次 过程调用、通过指针变量的赋值以及数组变量的赋值等语句较为微妙,10.5.1 点和路径,点（point） 相邻两条语句间的位置 第一条之前和最后一条语句之后的位置 路径（path） p1pn的路径点序列p1, p2, , pn，且对所有1=in满足下面两个条件之一： pi是紧挨在一条语句之前的点，pi+1是同一基本块中紧接在该语句之后的点 pi是某基本块的结束点，pi+1是后继块的开始点,例10.12,B5B6的路径： B5的结束点B2、B3、B4的所有点B6的开始点,d1: i := m 1 d2: j :=
14、 n d3: a := u1,d4: i := i + 1,d6: a := u2,B1,B2,B3,B4,B5,B6,d5: j := j - 1,10.5.2 到达定义,变量x的定义（definition） 明确（unambiguous）定义：赋值、I/O输入 模糊（ambiguous）定义 x作为过程的参数（非传值方式） x在过程的作用域中 “别名”x本身不是上两种情况，但与x等价的另一个变量是上两种情况 通过可能指向x的指针进行赋值，*q=yq指向x,到达,定义d到达（reach） p 存在从紧跟d的点到p的路径 在路径上d没有被注销 i := m 1, j := n到达B2 的开始点
15、 若B4、B5不对j赋值 B3中j := j 1后面部分 也是如此，则定义 j := j 1到达B2开始点 j := j - 1注销了j := n， 因此它不能到达B4、B5、B6,d1: i := m 1 d2: j := n d3: a := u1,d4: i := i + 1,d6: a := u2,B1,B2,B3,B4,B5,B6,d5: j := j - 1,10.5.3 结构化程序数据流分析,唯一的入口和出口 区域 包含首节点的一组节点，首节点支配其他所有节点 除了进入首节点的边，其他边都在区域内,集中常见的语句结构,数据流方程,d定义了a所有a的定义（除了b）全部被注销,数据流方程（续）,S生成的定义：S1和S2生成的定义，但S1生成的应去掉S2中注销的,数据流方程（续）,任何一个分支生成的定义，都会到达S末尾 而在两个分支都被注销，才认为是注销,数据流方程（续）,循环可运行多次S1生成的定义也应认为是其入口定义,10.5.4 数据流信息的保守估计,c)中S2永远不被选中 genS = genS1 killS
