第十章 代码优化学习内容m优化种类m循环m全局数据流分析m利用数据流信息进行全局优化概述m目标机器无关的优化m找出程序中执行最频繁的部分q内层循环m数据流分析10.1 引言m10.1.1 代码改进变换的标准q意义保持不变q提高速度，减小大小q代价适中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); quicksort(i + 1, n); 10.1.3 优化编译器的组织结构m优点q中间代码展现细节，便于优化q与目的机器无关例10.1i := m 1 j := n t1 := 4 * n v := at1i := i + 1 t2 := 4 * i t3 := at2 if t3 v goto B3if i = j goto B6t6 := 4 * i x := at6 t7 := 4 * i t8 := 4 * j t9 := at8 at7 := t9 t10 := 4 *j at10 := x goto B2t11 := 4 * i x := at11 t12 := 4 * i t13 := 4 * n t14 := at13 at12 := t14 t15 := 4 * n at15 := xB1B2B3B4B5B610.2 主要优化种类m局部（local）优化：局限基本块内m全局（global）优化m10.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 B2t6 := 4 * i x := at6 t8 := 4 * j t9 := at8 at6 := t9 at8 := x goto B2B5B5例10.2i := m 1 j := n t1 := 4 * n v := at1i := i + 1 t2 := 4 * i t3 := at2 if t3 v goto B3if i = j goto B6x := t3 at2 := t5 at4 := x goto B2x := t3 t14 := at1 at2 := t14 at1 := xB1B2B3B4 B5B610.2.3 复制传播mf := g在随后语句中，用g替换fa := d + eb := d + ec := d + et := d + e a := tt := d + e b := tc := tx := t3 at2 := t5 at4 := x goto B2B5x := t3 at2 := t5 at4 := t3 goto B2B510.2.4 无用代码删除debug := false if (debug) print .m利用复制传播，debug替换为false（常量合并 ，constant folding） if语句被删除x := t3 at2 := t5 at4 := x goto B2B5 at2 := t5 at4 := t3 goto B2B510.2.5 循环的优化m程序中运行最频繁的部分m代码外提，code motionm删除归纳变量， induction-variable eliminationm强度削弱，reduction strength10.2.6 代码外提m表达式计算与循环次数无关（循环不变计算 ，loop-invariant computation） 循环内循环入口前while (i v goto B3if i = j goto B6B1B2B3B4B5B6i := m 1 j := n t1 := 4 * n v := at1j := j - 1 t4 := t4 - 4 t5 := at4 if t5 v goto B3if i = j goto B6B1B2B3B4B5B6t4 := 4 * jj和t4的改变 是“同步”的 归纳变量例10.5 删除归纳变量i := m 1 j := n t1 := 4 * n v := at1 t2 := 4 * i t4 := 4 * jt2 := t2 + 4 t3 := at2 if t3 v goto B3if t2 = t4 goto B6at2 := t5 at4 := t3 goto B2t14 := at1 at2 := t14 at1 := t3B1B2B3B4 B5B6t2 = t4与 i = j等价10.3 基本块的优化m例10.5：基本块的dag表示a := b + c b := a d c := b + c d : = a - da := b + c d := a d c := d + c若b不活跃dag的局限m语句1和语句4的等价性无法发现 a := b + c b := b d c := c + d d := b + c利用代数恒等进行优化m代数恒等 x + 0 = 0 + x = xx 0 = x x * 1 = 1 * x = xx / 1 = xm降低强度 x * 2 = x * x2.0 * x = x + x x / 2 = x * 0.5m常量合并 2 * 3.14 6.28dag辅助代数优化mx * y = y * x：在dag节点创建中进行额 外检查mx y x y 结合 标志寄存器检测m结合率 a := b + ce := c + d + b a := b + c t := c + d e := t + b 优化 a := b + c e := a + d10.4 流图中的循环md支配（dominate）n：从流图的开始节点到n 的任何路径都经过d，d dom nm直接支配者， immediate dominator 任何路径上都是最后 一个支配者10.4.2 循环的判定m具有唯一入口点，“header”，它应支配 循环中所有节点，否则就不是唯一入口 点m至少有一条路径返回首节点m找出回边back edge 边ab，b支配am例10.7：上例流图中的回边 74，107，43，83，91循环的判定（续）m自然循环，natural loopq回边nd，d及不经过d可 到达n的节点集合，d首节 点m例10.8：q107的自然循环：7、8、 10q91的自然循环：所有节 点算法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; for (m的每个前驱p) insert(p); 10.4.3 内层循环（inner loop）m两个循环若无相同首节点，则：或者不相交 ，或者嵌套m内层循环：不包含其他循环的循环m相同首节点情况：可看作一个循环B0B1B3B210.4.4 Pre-Headerm循环L，创建前置节点，preheaderq只有一个后继L的首节点q所有L外指向首节点的边指向前置节点q代码外提headerloop Lpreheaderheaderloop L10.4.5 可约流图m循环外到循环内的转移m流图G可约的充要条件 所有边可划分为两个不相交的集合 前向边和回边，且满足：q前向边构成一个dag，且从G的开始节 点，可到达其他任何节点q回边：前面定义例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 全局数据流分析m数据流信息解方程组m数据流方程 outS = genS(inS killS) 含义：语句结束处的信息q或者是语句生成的信息q或者是语句开始时的信息去除语句执 行中注销的信息数据流方程创建求解的因素m“生成”、“注销”的概念依赖于求解问题 一般inSoutS，还可能outSinSm数据流分析依赖于程序的控制流语句 outS语句有唯一出口 方程基本块层次m过程调用、通过指针变量的赋值以及数 组变量的赋值等语句较为微妙10.5.1 点和路径m点（point）q相邻两条语句间的位置q第一条之前和最后一条语句之后的位置m路径（path）qp1pn的路径点序列p1, p2, , pn，且对所 有1 oldout then change := true; end end例10.15genB1 = d1, d2, d3 killB1 = d4, d5, d6, d7 genB2 = d4, d5 killB2 = d1, d2, d7 genB3 = d6 killB3 = d3 genB4 = d7 killB4 = d1, d4 d1: i := m 1 d2: j := n d3: a := u1d4: i := i + 1 d5: j := j - 1d6: a := u2B1B2B3B4d7: i := u3例10.15（续）块B初始第1遍第2遍inBout BinBout BinBout BB1000 0000111 0000 000 0000 111 0000 000 0000111 0000B2000 0000000 1100 111 0011 001 1110 111 1111001 1110B3000 0000000 0010 001 1110 000 1110 001 1110000 1110B4000 0000000 0001 001 1110 001 0111 001 1110001 011110.6.2 可用表达式m表达式x+y在p点可用（available）q开始节点到p的每条路径都计算x+yq最后一次计算后，再无对x、y的赋值m注销（kill）q块对x、y赋值后没有重新计算表达式m生成（generate）q块计算表达式后，没有重新定义x、ym与到达定义概念相似，可类似计算可用表达式m用途：检测公共表达式m块生成的表达式集合的计算q假定块前的点没有可用表达式q点p处表达式集合A是可用的qq是p之后的点，之间有语句x := y + zq点p处可用表达式的计算 将表达式y+z添加到A中 从A中删除任何含有x的表达式q注销表达式集合的计算 y+z：y、z在块中定义，y+z不由该块生成例10.16语句可用表达式 .无a := b + c.仅b+cb := a d.仅a-dc := b + c.仅a-dd := a d.无可用表达式的计算minB, outB, e_genB, e_killBm聚合操作为交集q所有前驱末尾都可用，表达式才在块的开始可 用m到达定义计算“最小解”，空集