第十章 代码优化,学习内容,优化种类 循环 全局数据流分析 利用数据流信息进行全局优化,概述,目标机器无关的优化 找出程序中执行最频繁的部分 内层循环 数据流分析,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); quicksort(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 := 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 * 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 := 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） if语句被删除,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 强度削弱,例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表示,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 = 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”，它应支配循环中所有节点，否则就不是唯一入口点 至少有一条路径返回首节点 找出回边back 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; 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可约的充要条件 所有边可划分为两个不相交的集合前向边和回边，且满足： 前向边构成一个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，还可能outSinS 数据流分析依赖于程序的控制流语句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 := 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 的开始点 若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