编译原理 代码优化2.ppt

代码优化,代码优化的目标,提高最终目标代码的运行效率（性能） 时间：运行的更快 空间：降低内存需求 保持源程序的语义,2019/10/26,编译原理与技术之代码优化,3,代码优化（续）, 全局数据流分析技术,2019/10/26,编译原理与技术之代码优化,4,全局数据流分析,基本块,INB,OUTB,KILLB,GENB,到达基本块入口处的相关数据流信息,到达基本块出口处的相关数据流信息,基本块“产生”的相关数据流信息,基本块“注销”的相关数据流信息,2019/10/26,编译原理与技术之代码优化,5,全局数据流分析,数据流的“方向” 正向（向前）数据流：与控制流方向一致 OUTB由INB来计算 INB则由B的所有前驱结 点的OUT来决定,控制流,数据流,前驱1,前驱2,基本块B,表示数据流信息交汇（合流）处,2019/10/26,编译原理与技术之代码优化,6,全局数据流分析,数据流的“方向” 反向（向后）数据流：与控制流方向相逆 INB由OUTB 来计算 OUT B则由B的所有后继结 点的IN来决定,控制流,数据流,基本块B,后继1,后继2,表示数据流信息交汇（合流）处,2019/10/26,编译原理与技术之代码优化,7,全局数据流分析,表1. 数据流分析方程,2019/10/26,编译原理与技术之代码优化,8,全局数据流方程求解,迭代计算：直至某先后两次迭代计算结果一样 迭代次序 向前流：流图深度优先次序 向后流：流图深度优先次序的逆序 流图深度优先次序： 对流图进行深度优先遍历，得到流图深度 优先扩展树；对该树进行前序遍历时最后 访问结点的逆序 迭代初始计算（值）,2019/10/26,编译原理与技术之代码优化,9,e.g. 一个流图,前序遍历：1-2-3-4-6-7-8-10-8-9-8-7-6-4-5-4-3-2-1 深度优先次序：1，2，3，4，5，6，7，8，9，10,2019/10/26,编译原理与技术之代码优化,10,全局数据流方程求解,表2. 常用的数据流分析,2019/10/26,编译原理与技术之代码优化,11,到达定值数据流分析,定值与引用 d : x := y + z / 语句d 是变量x的一个定值点 u : w := x + v / 语句u 是变量x的一个引用点 变量x在d点的定值到达u点,流图中有路径d-u，且该路径上没有x的其它（无二义）定值。,2019/10/26,编译原理与技术之代码优化,12,到达定值数据流分析,解决的问题 定值“传播” 数据流归属 任意路径、向前流的数据流分析 INB，到达基本块入口处定值集合 OUTB，到达基本块出口处定值集合 GENB，基本块产生且能到达基本块出口的定值集合 KILLB，由基本块注销的定值集合（这些定值不能传播或到达到块出口） 数据流应用 ud链，即引用定值链。可以据此判断基本块内的某变量引用，其值来自何方（定值）。如应用于循环不变式的寻找。,2019/10/26,编译原理与技术之代码优化,13,OUT: dm : x:= ,OUT: dn : x:= ,前驱1,前驱2, ds : s := x dt : x := du : x := ,INB,OUTB = ?,控制流,2019/10/26,编译原理与技术之代码优化,14,OUT: dm : x:= ,OUT: dn : x:= ,前驱1,前驱2, ds : s := x dt : x := du : x := ,INB,OUTB = ?,英雄惜英雄，dm 和 dn相会在汇流点，共赴INB,2019/10/26,编译原理与技术之代码优化,15,OUT: dm : x:= ,OUT: dn : x:= ,前驱1,前驱2, ds : s := x dt : x := du : x := ,INB,OUTB = ?,dm和dn ：一路无险遇 ds,2019/10/26,编译原理与技术之代码优化,16,OUT: dm : x:= ,OUT: dn : x:= ,前驱1,前驱2, ds : s := x dt : x := du : x := ,INB,OUTB = ?,dm和dn ：再走一程见 dt， _,2019/10/26,编译原理与技术之代码优化,17,OUT: dm : x:= ,OUT: dn : x:= ,前驱1,前驱2, ds : s := x dt : x := du : x := ,INB,OUTB = ?,dm和dn ：我们被dt所“屏蔽”。不知何时上了“注销”榜？ dt : 你们歇着吧。我要 Go Go Go,2019/10/26,编译原理与技术之代码优化,18,OUT: dm : x:= ,OUT: dn : x:= ,前驱1,前驱2, ds : s := x dt : x := du : x := ,INB,OUTB = ?,dt：等等，我咋也上榜了？唉，既生t，何生u? du：数“流”人，还看,2019/10/26,编译原理与技术之代码优化,19,OUT: dm : x:= ,OUT: dn : x:= ,前驱1,前驱2, ds : s := x dt : x := du : x := ,INB,OUTB = ?,du : 顺利过关。嗯，要是没有我和dt的阻击，现在站在这里的就是dm和dn。 只可惜了dt ,2019/10/26,编译原理与技术之代码优化,20,到达定值数据流分析,d1: i := m-1 d2: j := n d3: a := u1,d4: i := i +1 d5: j := j - 1,d6: a := u2,d7: i := u3,B1,B2,B3,B4,GENB1 = d1, d2, d3 KILLB1 = d4,d5,d6,d7 GENB2 = d4, d5 KILLB2 = d1,d2,d7 GENB3 = d6 KILLB3 = d3 GENB4 = d7 KILLB5 = d1,d4 ,例1. 求解到达定值的数据流图,2019/10/26,编译原理与技术之代码优化,21,迭代计算 计算次序，深度优先序，即 B1 - B2 - B3 - B4 初始值：for all B: INB ; OUTB = GENB 第一次迭代： INB1 = ; / B1 无前驱结点 OUTB1 = GENB1 (INB1-KILLB1) = GENB1 = d1, d2, d3 INB2 = OUTB1 OUTB4 = d1, d2, d3 d7 = d1, d2, d3, d7 OUTB2 = GENB2 (INB2-KILLB2) = d4, d5 d3 = d3, d4, d5 INB3 = OUTB2 = d3, d4, d5 OUTB3 = d6 ( d3, d4, d5 d3 ) = d4, d5, d6 INB4 = OUTB3 OUTB2 = d3, d4, d5, d6 OUTB4 = d7 ( d3, d4, d5, d6 d1, d4 ) = d3, d5, d6, d7 ,2019/10/26,编译原理与技术之代码优化,22,第二次迭代 INB1 = ; / B1 无前驱结点 OUTB1 = GENB1 (INB1-KILLB1) = GENB1 = d1, d2, d3 INB2 = OUTB1 OUTB4 = d1,d2,d3 d3, d5, d6, d7 = d1, d2, d3, d5, d6, d7 OUTB2 = GENB2 (INB2-KILLB2) = d4, d5 d3, d5, d6 = d3, d4, d5, d6 INB3 = OUTB2 = d3, d4, d5, d6 OUTB3 = d6 ( d3, d4, d5, d6 d3 ) = d4, d5, d6 INB4 = OUTB3 OUTB2 = d3, d4, d5, d6 OUTB4 = d7 ( d3, d4, d5, d6 d1, d4 ) = d3, d5, d6, d7 经过第二次迭代后，INB和OUTB 不再变化。,2019/10/26,编译原理与技术之代码优化,23,ud链 考察流图中变量i，j的引用定值情况 在基本块B2中有相应的引用 d4 : i := i + 1 i + 1 中的i 在引用前无定值，该引用的ud链仅来自于 INB2中 i 的有关定值集合，即 d1 : i := m 1 ; d7 : i := u3 类似地，d5 : j := j 1 中的 j 引用-定值链为 d2 : j := n ; d5 : j := j 1 如果某变量引用前有定值，则该引用的ud链仅包含该变量的最后定值,2019/10/26,编译原理与技术之代码优化,24,活跃变量分析,活跃变量 d : x := / 语句d是变量x的定值点 / 从d点开始的某条路径上 / 有该x值的引用，则称x在 / d点活跃 u : := x ,2019/10/26,编译原理与技术之代码优化,25,活跃变量分析,解决问题 在基本块出口处变量的活跃情况 数据流归属 任意路径、向后流数据流分析 数据流应用 无用赋值的删除 出口非活跃变量（无需存储、寄存器剥夺）,2019/10/26,编译原理与技术之代码优化,26,2019/10/26,编译原理与技术之代码优化,27,x, y : 原来这里也有我们的身影哦。,2019/10/26,编译原理与技术之代码优化,28,y : 我走不动了。逆“流”行船，累啊。 x : 坚持就是胜利。,2019/10/26,编译原理与技术之代码优化,29,x : 又觅“活”踪,2019/10/26,编译原理与技术之代码优化,30,x : 终于出头啦！,2019/10/26,编译原理与技术之代码优化,31,活跃变量分析,(1) a := 1 (2) b := 2,B1,(3) c := a + b (4) d := c a,B2,(8) b := a + b (9) e := c a,B5,(5) d := b * d,B3,(6) d := a + b (7) e := e + 1,B4,(10) a := b * d (11) b := a d,B6,2019/10/26,编译原理与技术之代码优化,32,基本块出口活跃变量,迭代计算 OUTB = INS, SSucc(B) INB = USEB (OUTB-DEFB) USEB基本块B中有引用且该引用前无定值的变量集合； DEFB基本块B中有定值且该定值前无引用的变量集合； 计算次序 结点深度优先序的逆序（向后流）: B6 B5 B4 B3 B2 B1,2019/10/26,编译原理与技术之代码优化,33,基本块出口活跃变量,各基本块USE和DEF如下， USEB1 = ; DEFB1 = a, b USEB2 = a, b ; DEFB2 = c, d USEB3 = b, d ; DEFB3 = USEB4 = a, b, e ; DEFB4 = d USEB5 = a, b, c ; DEFB5 = e USEB6 = b, d ; DEFB6 = a 初始值，all B, INB = , OUTB6= /出口块,2019/10/26,编译原理与技术之代码优化,34,基本块出口活跃变量,第一次迭代计算,(1) a := 1 (2) b := 2,B1,(3) c := a + b (4) d := c a,B2,(8) b := a + b (9) e := c a,B5,(5) d := b * d,B3,(6) d := a + b (7) e := e + 1,B4,(10) a := b * d (11) b := a d,B6, , b, d ,2019/10/26,编译原理与技术之代码优化,35,基本块出口活跃变量,第一次迭代计算,(1) a := 1 (2) b := 2,B1,(3) c := a + b (4) d := c a,B2,(8) b := a + b (9) e := c a,B5,(5) d := b * d,B3,(6) d := a + b (7) e := e + 1,B4,(10) a := b * d (11) b := a d,B6, , b, d , b, d , a,b,c,d ,2019/10/26,编译原理与技术之代码优化,36,基本块出口活跃变量,第一次迭代计算,(1) a := 1 (2) b := 2,B1,(3) c := a + b (4) d := c a,B2,(8) b := a + b (9) e := c a,B5,(5) d := b * d,B3,(6) d := a + b (7) e := e + 1,B4,(10) a := b * d (11) b := a d,B6, , b, d , b, d , a,b,c,d , , a,b,e ,2019/10/26,编译原理与技术之代码优化,37,基本块出口活跃变量,第一次迭代计算,(1) a := 1 (2) b := 2,B1,(3) c := a + b (4) d := c a,B2,(8) b := a + b (9) e := c a,B5,(5) d := b * d,B3,(6) d := a + b (7) e := e + 1,B4,(10) a := b * d (11) b := a d,B6, , b, d , b, d , a,b,c,d , , a,b,e , a,b,c,d,e , a,b,c,d,e ,2019/10/26,编译原理与技术之代码优化,38,基本块出口活跃变量,第一次迭代计算,(1) a := 1 (2) b := 2,B1,(3) c := a + b (4) d := c a,B2,(8) b := a + b (9) e := c a,B5,(5) d := b * d,B3,(6) d := a + b (7) e := e + 1,B4,(10) a := b * d (11) b := a d,B6, , b, d , b, d , a,b,c,d , , a,b,e , a,b,c,d,e , a,b,c,d,e , a,b,c,d,e , a,b,e ,2019/10/26,编译原理与技术之代码优化,39,基本块出口活跃变量,第一次迭代计算,(1) a := 1 (2) b := 2,B1,(3) c := a + b (4) d := c a,B2,(8) b := a + b (9) e := c a,B5,(5) d := b * d,B3,(6) d := a + b (7) e := e + 1,B4,(10) a := b * d (11) b := a d,B6, , b, d , b, d , a,b,c,d , , a,b,e , a,b,c,d,e , a,b,c,d,e , a,b,c,d,e , a,b,e , a,b,e , e ,2019/10/26,编译原理与技术之代码优化,40,基本块出口活跃变量,第二次迭代计算,(1) a := 1 (2) b := 2,B1,(3) c := a + b (4) d := c a,B2,(8) b := a + b (9) e := c a,B5,(5) d := b * d,B3,(6) d := a + b (7) e := e + 1,B4,(10) a := b * d (11) b := a d,B6, , b, d , b, d , a,b,c,d , , a,b,e , a,b,c,d,e , a,b,c,d,e , a,b,c,d,e , a,b,e , a,b,e , e ,2019/10/26,编译原理与技术之代码优化,41,基本块出口活跃变量,第二次迭代计算,(1) a := 1 (2) b := 2,B1,(3) c := a + b (4) d := c a,B2,(8) b := a + b (9) e := c a,B5,(5) d := b * d,B3,(6) d := a + b (7) e := e + 1,B4,(10) a := b * d (11) b := a d,B6, , b, d , a,b,d,e , a,b,c,d , , a,b,e , a,b,c,d,e , a,b,c,d,e , a,b,c,d,e , a,b,e , a,b,e , e ,2019/10/26,编译原理与技术之代码优化,42,基本块出口活跃变量,第二次迭代计算,(1) a := 1 (2) b := 2,B1,(3) c := a + b (4) d := c a,B2,(8) b := a + b (9) e := c a,B5,(5) d := b * d,B3,(6) d := a + b (7) e := e + 1,B4,(10) a := b * d (11) b := a d,B6, , b, d , a,b,d,e , a,b,c,d , a,b,c,d,e , a,b,c,e , a,b,c,d,e , a,b,c,d,e , a,b,c,d,e , a,b,e , a,b,e , e ,2019/10/26,编译原理与技术之代码优化,43,基本块出口活跃变量,第二次迭代计算,(1) a := 1 (2) b := 2,B1,(3) c := a + b (4) d := c a,B2,(8) b := a + b (9) e := c a,B5,(5) d := b * d,B3,(6) d := a + b (7) e := e + 1,B4,(10) a := b * d (11) b := a d,B6, , b, d , a,b,d,e , a,b,c,d , a,b,c,d,e , a,b,c,e , a,b,c,d,e , a,b,c,d,e , a,b,c,d,e , a,b,e , a,b,e , e ,2019/10/26,编译原理与技术之代码优化,44,基本块出口活跃变量,第二次迭代计算,(1) a := 1 (2) b := 2,B1,(3) c := a + b (4) d := c a,B2,(8) b := a + b (9) e := c a,B5,(5) d := b * d,B3,(6) d := a + b (7) e := e + 1,B4,(10) a := b * d (11) b := a d,B6, , b, d , a,b,d,e , a,b,c,d , a,b,c,d,e , a,b,c,e , a,b,c,d,e , a,b,c,d,e , a,b,c,d,e , a,b,e , a,b,e , e ,2019/10/26,编译原理与技术之代码优化,45,基本块出口活跃变量,第二次迭代计算,(1) a := 1 (2) b := 2,B1,(3) c := a + b (4) d := c a,B2,(8) b := a + b (9) e := c a,B5,(5) d := b * d,B3,(6) d := a + b (7) e := e + 1,B4,(10) a := b * d (11) b := a d,B6, , b, d , a,b,d,e , a,b,c,d , a,b,c,d,e , a,b,c,e , a,b,c,d,e , a,b,c,d,e , a,b,c,d,e , a,b,e , a,b,e , e ,2019/10/26,编译原理与技术之代码优化,46,基本块出口活跃变量,第三次迭代与前一次 结果一样，计算结束,(1) a := 1 (2) b := 2,B1,(3) c := a + b (4) d := c a,B2,(8) b := a + b (9) e := c a,B5,(5) d := b * d,B3,(6) d := a + b (7) e := e + 1,B4,(10) a := b * d (11) b := a d,B6, , a,b,d,e , a,b,c,d,e , a,b,c,d,e , a,b,c,d,e , a,b,e ,