代码优化ppt课件.ppt

《代码优化ppt课件.ppt》由会员分享，可在线阅读，更多相关《代码优化ppt课件.ppt（63页珍藏版）》请在三一文库上搜索。

1、代码优化,代码优化的目标,提高最终目标代码的运行效率（性能） 时间：运行的更快 空间：降低内存需求 保持源程序的语义,2019/3/18,编译原理与技术之代码优化,3,代码优化（续）, 全局数据流分析技术,2019/3/18,编译原理与技术之代码优化,4,全局数据流分析,基本块,INB,OUTB,KILLB,GENB,到达基本块入口处的相关数据流信息,到达基本块出口处的相关数据流信息,基本块“产生”的相关数据流信息,基本块“注销”的相关数据流信息,2019/3/18,编译原理与技术之代码优化,5,全局数据流分析,数据流的“方向” 正向（向前）数据流：与控制流方向一致 OUTB由INB来计算 I

2、NB则由B的所有前驱结 点的OUT来决定,控制流,数据流,前驱1,前驱2,基本块B,表示数据流信息交汇（合流）处,2019/3/18,编译原理与技术之代码优化,6,全局数据流分析,数据流的“方向” 反向（向后）数据流：与控制流方向相逆 INB由OUTB 来计算 OUT B则由B的所有后继结 点的IN来决定,控制流,数据流,基本块B,后继1,后继2,表示数据流信息交汇（合流）处,2019/3/18,编译原理与技术之代码优化,7,全局数据流分析,表1. 数据流分析方程,2019/3/18,编译原理与技术之代码优化,8,全局数据流方程求解,迭代计算：直至某先后两次迭代计算结果一样 迭代次序 向前流：

3、流图深度优先次序 向后流：流图深度优先次序的逆序 流图深度优先次序： 对流图进行深度优先遍历，得到流图深度 优先扩展树；对该树进行前序遍历时最后 访问结点的逆序 迭代初始计算（值）,2019/3/18,编译原理与技术之代码优化,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/3/18,编译原理与技术之代码优化,10,全局数据流方程求解,表2. 常用的数据流分析,2019/3/18,编译原理与技术之代码优化,11,到达定值数据流分析,定值与引用 d : x := y

4、+ z / 语句d 是变量x的一个定值点 u : w := x + v / 语句u 是变量x的一个引用点 变量x在d点的定值到达u点,流图中有路径d-u，且该路径上没有x的其它（无二义）定值。,2019/3/18,编译原理与技术之代码优化,12,到达定值数据流分析,解决的问题 定值“传播” 数据流归属 任意路径、向前流的数据流分析 INB，到达基本块入口处定值集合 OUTB，到达基本块出口处定值集合 GENB，基本块产生且能到达基本块出口的定值集合 KILLB，由基本块注销的定值集合（这些定值不能传播或到达到块出口） 数据流应用 ud链，即引用定值链。可以据此判断基本块内的某变量引用，其值来自

5、何方（定值）。如应用于循环不变式的寻找。,2019/3/18,编译原理与技术之代码优化,13,OUT: dm : x:= ,OUT: dn : x:= ,前驱1,前驱2, ds : s := x dt : x := du : x := ,INB,OUTB = ?,控制流,2019/3/18,编译原理与技术之代码优化,14,OUT: dm : x:= ,OUT: dn : x:= ,前驱1,前驱2, ds : s := x dt : x := du : x := ,INB,OUTB = ?,英雄惜英雄，dm 和 dn相会在汇流点，共赴INB,2019/3/18,编译原理与技术之代码优化,15,O

6、UT: dm : x:= ,OUT: dn : x:= ,前驱1,前驱2, ds : s := x dt : x := du : x := ,INB,OUTB = ?,dm和dn ：一路无险遇 ds,2019/3/18,编译原理与技术之代码优化,16,OUT: dm : x:= ,OUT: dn : x:= ,前驱1,前驱2, ds : s := x dt : x := du : x := ,INB,OUTB = ?,dm和dn ：再走一程见 dt， _,2019/3/18,编译原理与技术之代码优化,17,OUT: dm : x:= ,OUT: dn : x:= ,前驱1,前驱2, ds :

7、s := x dt : x := du : x := ,INB,OUTB = ?,dm和dn ：我们被dt所“屏蔽”。不知何时上了“注销”榜？ dt : 你们歇着吧。我要 Go Go Go,2019/3/18,编译原理与技术之代码优化,18,OUT: dm : x:= ,OUT: dn : x:= ,前驱1,前驱2, ds : s := x dt : x := du : x := ,INB,OUTB = ?,dt：等等，我咋也上榜了？唉，既生t，何生u? du：数“流”人，还看,2019/3/18,编译原理与技术之代码优化,19,OUT: dm : x:= ,OUT: dn : x:= ,前驱

8、1,前驱2, ds : s := x dt : x := du : x := ,INB,OUTB = ?,du : 顺利过关。嗯，要是没有我和dt的阻击，现在站在这里的就是dm和dn。 只可惜了dt ,2019/3/18,编译原理与技术之代码优化,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

9、= d1,d2,d7 GENB3 = d6 KILLB3 = d3 GENB4 = d7 KILLB5 = d1,d4 ,例1. 求解到达定值的数据流图,2019/3/18,编译原理与技术之代码优化,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

10、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/3/18,编译原理与技术之代码优化,22,第二次迭代 INB1 = ; / B1 无前驱结点 OUTB1 = GENB1 (INB1-KILLB1) = GENB1

11、= 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 ) = d

12、3, d5, d6, d7 经过第二次迭代后，INB和OUTB 不再变化。,2019/3/18,编译原理与技术之代码优化,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/3/18,编译原理与技

13、术之代码优化,24,活跃变量分析,活跃变量 d : x := / 语句d是变量x的定值点 / 从d点开始的某条路径上 / 有该x值的引用，则称x在 / d点活跃 u : := x ,2019/3/18,编译原理与技术之代码优化,25,活跃变量分析,解决问题 在基本块出口处变量的活跃情况 数据流归属 任意路径、向后流数据流分析 数据流应用 无用赋值的删除 出口非活跃变量（无需存储、寄存器剥夺）,2019/3/18,编译原理与技术之代码优化,26,2019/3/18,编译原理与技术之代码优化,27,x, y : 原来这里也有我们的身影哦。,2019/3/18,编译原理与技术之代码优化,28,y :

14、 我走不动了。逆“流”行船，累啊。 x : 坚持就是胜利。,2019/3/18,编译原理与技术之代码优化,29,x : 又觅“活”踪,2019/3/18,编译原理与技术之代码优化,30,x : 终于出头啦！,2019/3/18,编译原理与技术之代码优化,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 :=

15、 a d,B6,2019/3/18,编译原理与技术之代码优化,32,基本块出口活跃变量,迭代计算 OUTB = INS, SSucc(B) INB = USEB (OUTB-DEFB) USEB基本块B中有引用且该引用前无定值的变量集合； DEFB基本块B中有定值且该定值前无引用的变量集合； 计算次序 结点深度优先序的逆序（向后流）: B6 B5 B4 B3 B2 B1,2019/3/18,编译原理与技术之代码优化,33,基本块出口活跃变量,各基本块USE和DEF如下， USEB1 = ; DEFB1 = a, b USEB2 = a, b ; DEFB2 = c, d USEB3 = b,

16、d ; DEFB3 = USEB4 = a, b, e ; DEFB4 = d USEB5 = a, b, c ; DEFB5 = e USEB6 = b, d ; DEFB6 = a 初始值，all B, INB = , OUTB6= /出口块,2019/3/18,编译原理与技术之代码优化,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 +

17、 1,B4,(10) a := b * d (11) b := a d,B6, , b, d ,2019/3/18,编译原理与技术之代码优化,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/3/18,编

18、译原理与技术之代码优化,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/3/18,编译原理与技术之代码优化,37,基本块出口活跃变量,第一次迭代计算,(1) a := 1 (2) b

19、 := 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/3/18,编译原理与技术之代码优化,38,基本块出口活跃变量,第一次迭代计算,(1) a := 1 (2) b := 2,B1,(3) c := a + b (

20、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/3/18,编译原理与技术之代码优化,39,基本块出口活跃变量,第一次迭代计算,(1) a := 1 (2) b := 2,B1,(3) c := a + b (4) d

21、:= 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/3/18,编译原理与技术之代码优化,40,基本块出口活跃变量,第二次迭代计算,(1) a := 1 (2) b := 2,B1,(3) c := a + b

22、 (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/3/18,编译原理与技术之代码优化,41,基本块出口活跃变量,第二次迭代计算,(1) a := 1 (2) b := 2,B1,(3) c :

23、= 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/3/18,编译原理与技术之代码优化,42,基本块出口活跃变量,第二次迭代计算,(1) a := 1 (2) b := 2,

24、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/3/18,编译原理与技术之代码优化,43,基本块出口活跃变量,第二次迭代计算,

25、(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/3/18,编译原理与技术之代码优化

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 ,

27、2019/3/18,编译原理与技术之代码优化,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

28、 , a,b,e , a,b,e , e ,2019/3/18,编译原理与技术之代码优化,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,

29、b,e ,2019/3/18,编译原理与技术之代码优化,47,48,可用表达式数据流分析,如果从流图入口结点到达程序点p的每一条路径上均对表达式x+y求值，且每条路径上最后一个这样的求值之后到p点的路径上没有对x或y赋值，那么称x+y在点p可用（available）。 显然，可用表达式分析属于 全路径数据流问题。,ENTRY,u = x + y,u = x + y,u = x + y,p,49,可用表达式数据流分析,数据流应用：寻找公共子表达式。如果在基本块中需要计算某个表达式，而此表达式恰好在其入口处可用，且这之间该表达式的值未被修改，则基本块中无需再计算此表达式。 数据流值域：全体（右值）

30、表达式集合U的幂集 数据流方向： 全路径、前向数据流分析 传递函数： 语义约束与控制流约束 首先，考察基本块中单个语句的语义约束，其次，推广到整个基本块（所有语句），最后考察基本块之间的约束关系。,50,可用表达式数据流分析,基本块语义传递函数 e_genB：基本块B生成的表达式集合；如果基本块B对表达式x+y求值，且之后未对变量x或y重新定值，那么称基本块B生成表达式x+y。 e_killB：被基本块B注销的表达式集合；如果基本块B中对变量x或y进行定值，且之后没有重新计算x+y，那么称基本块B杀死（或注销）了表达式x+y。 INB：基本块B入口点处可用表达式集。显然，在基本块B的每一个前驱

31、块P的出口点处可用的表达式也将在B的入口点处可用。 OUTB：基本块B出口点处可用表达式集。,51,基本块生成的表达式： 基本块中语句d：x = y + z的前、后点分别为点p与点q。设在点p处可用表达式集合为S（基本块入口点处S为空集），那么经过语句d之后，在点q处可用表达式集合如下构成： (1) S = S y+z (2) S = S S 中所有涉及变量x的表达式 注意，步骤(1)和(2)不可颠倒，x可能就是y或z。 如此处理完基本块中所有语句后，可以得到基本块生成的可用表达式集合S； 基本块杀死的表达式：所有其他类似y+z的表达式，基本块中对y或z定值，但基本块没有生成y+z。,52,示

32、例：基本块生成的表达式,53,可用表达式数据流分析,传递方程： INB = P是B的前驱基本块(OUTP) OUTB = e_genB ( INB e_killB ) 边界值：OUTENTRY = ；程序开始，无可用表达式！ 迭代算法： (1) OUTENTRY = (2) for( 除ENTRY之外的每个基本块B) OUTB= U (3) while(某个OUT值发生变化) (4) for(除ENTRY之外的每个基本块B ) (5) INB = P是B的前驱基本块(OUTP) (6) OUTB = e_genB ( INB e_killB ) / end-of-for / end-of-wh

33、ile,54,在可用表达式分析中，适宜将OUT的初值置为全体 表达式集合U而不是空集。令G和K为基本块B2 的生成与注销表达式集合，则： INB2 = OUTB1 OUTB2 OUTB2 = G(INB2 K ) 令Ij和Oj分别为B2在第j次迭代中 IN和OUT值；则： I j+1 = OUTB1 O j O j+1 = G ( I j+1 K ) 如果由O0 = 开始，I1 = OUTB1 O 0 = 。 但从O0 = U开始，则I1 = OUTB1 O 0 = OUTB1， 事实上，如果OUTB1中某个表达式没有被B2注销， 则它在B2的出口处可用。这正是我们所希望的！,B1,B2,55

34、,示例：可用表达式,(1) D = 3 (2) G = 1,(3) B D + D C = D * D A B C,C B + C F = A * A,B B + C F = A + G,G B + C D = D * D,EXIT,ENTRY,B1,B2,B3,B4,B5,56,示例：可用表达式,57,示例：可用表达式,58,可用表达式的迭代计算 计算次序，深度优先序， 即 B1 - B2 - B3 - B4 - B5 - EXIT 边界值：OUTENTRY = ; 初始化：for all NON-ENTRY B: OUTB U ； 第一次迭代：(all NON-ENTRY B) (1) I

35、NB1 = OUTENTRY = ; / B1 前驱仅为ENTRY OUTB1 = e_GENB1 ( INB1 e_KILLB1 ) = e_GENB1 = 3, 1 /变化 (2) INB2 = OUTB1 OUTB5 = 3, 1 U = 3, 1 OUTB2 = e_GENB2 ( INB2 KILLB2 ) = D+D, D*D, B+C ( 3, 1 A*A, A+G ) = 3, 1, D+D, D*D, B+C /变化,59,第一次迭代：(all NON-ENTRY B) (3) INB3 = OUTB2 = 3, 1, D+D, D*D, B+C OUTB3 = e_genB

36、3 ( INB3 e_killB3 ) = A+G ( 3, 1, D+D, D*D, B+C B+C ) = 3, 1, D+D, D*D, A+G /变化 (4) INB4 = OUTB2 = 3, 1, D+D, D*D, B+C OUTB4 = e_genB4 ( INB4 e_killB4 ) = A * A ( 3, 1, D+D, D*D, B+C B+C ) = 3, 1, D+D, D*D, A * A /变化,60,第一次迭代：(all NON-ENTRY B) (5) INB5 = OUTB3 OUTB4 = 3, 1, D+D, D*D, A+G 3, 1, D+D,

37、D*D, A * A = 3, 1, D+D, D*D OUTB5 = e_genB5 ( INB5 e_killB5 ) = B+C(3,1,D+D, D*D A+G, D*D, D+D) = 3, 1, B+C /变化 (6) INEXIT = OUTB5 = 3, 1, B+C OUTEXIT = e_GENEXIT (INEXIT e_KILLEXIT) = ( 3, 1, B+C ） = 3, 1, B+C /变化,61,第二次迭代：(all NON-ENTRY B) (1) INB1 = OUTENTRY = ; OUTB1 = e_GENB1 ( INB1 e_KILLB1 )

38、= e_GENB1 = 3, 1 / 不变 (2) INB2 = OUTB1 OUTB5 = 3, 1 3, 1, B+C = 3, 1 / 不变 OUTB2 = e_GENB2 ( INB2 e_KILLB2 ) = D+D, D*D, B+C ( 3, 1 A*A, A+G ) = 3, 1, D+D, D*D, B+C / 不变,62,第二次迭代：(all NON-ENTRY B) (3) INB3 = OUTB2 = 3, 1, D+D, D*D, B+C /不变 OUTB3 = e_genB3 ( INB3 e_killB3 ) = A+G ( 3, 1, D+D, D*D, B+C

39、 B+C ) = 3, 1, D+D, D*D, A+G /不变 (4) INB4 = OUTB2 = 3, 1, D+D, D*D, B+C /不变 OUTB4 = e_genB4 ( INB4 e_killB4 ) = A * A ( 3, 1, D+D, D*D, B+C B+C ) = 3, 1, D+D, D*D, A * A /不变,63,第二次迭代：(all NON-ENTRY B) (5) INB5 = OUTB3 OUTB4 = 3, 1, D+D, D*D, A+G 3, 1, D+D, D*D, A * A = 3, 1, D+D, D*D /不变 OUTB5 = e_genB5 ( INB5 e_killB5 ) = B+C(3,1,D+D, D*D A+G, D*D, D+D) = 3, 1, B+C /不变 (6) INEXIT = OUTB5 = 3, 1, B+C /不变 OUTEXIT = e_GENEXIT (INEXIT e_KILLEXIT) = ( 3, 1, B+C ） = 3, 1, B+C /不变,