代码优化.ppt

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

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

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

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

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

5、原理与技术之代码优化,13,OUT:dm:x:=,OUT:dn:x:=,前驱1,前驱2,ds:s:=x dt:x:=du:x:=,INB,OUTB=?,控制流,2023/8/18,编译原理与技术之代码优化,14,OUT:dm:x:=,OUT:dn:x:=,前驱1,前驱2,ds:s:=x dt:x:=du:x:=,INB,OUTB=?,英雄惜英雄，dm 和 dn相会在汇流点，共赴INB,2023/8/18,编译原理与技术之代码优化,15,OUT:dm:x:=,OUT:dn:x:=,前驱1,前驱2,ds:s:=x dt:x:=du:x:=,INB,OUTB=?,dm和dn：一路无险遇 ds,202

6、3/8/18,编译原理与技术之代码优化,16,OUT:dm:x:=,OUT:dn:x:=,前驱1,前驱2,ds:s:=x dt:x:=du:x:=,INB,OUTB=?,dm和dn：再走一程见 dt，_,2023/8/18,编译原理与技术之代码优化,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,2023/8/18,编译原理与技术之代码优化,18,OUT:dm:x:=,OUT:dn:x:=,前驱1,前驱2,ds:s

7、:=x dt:x:=du:x:=,INB,OUTB=?,dt：等等，我咋也上榜了？唉，既生t，何生u?du：数“流”人，还看,2023/8/18,编译原理与技术之代码优化,19,OUT:dm:x:=,OUT:dn:x:=,前驱1,前驱2,ds:s:=x dt:x:=du:x:=,INB,OUTB=?,du:顺利过关。嗯，要是没有我和dt的阻击，现在站在这里的就是dm和dn。只可惜了dt,2023/8/18,编译原理与技术之代码优化,20,到达定值数据流分析,d1:i:=m-1d2:j:=nd3:a:=u1,d4:i:=i+1d5:j:=j-1,d6:a:=u2,d7:i:=u3,B1,B2,B

8、3,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.求解到达定值的数据流图,2023/8/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,

9、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,2023/8/18,编译原理与技术之代码优化,22,第二次迭代INB1=;/B1 无前驱结点 OUTB1=GENB1(INB1-KILLB1)=GENB1=d1,d2,d3 INB2=OUTB1 OUTB4=d1,d2,d3 d3,d5,d6,d7=d1,

10、d2,d3,d5,d6,d7OUTB2=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 不再变化。,2023/8/18,编译原理与技术之代码优化,23,ud链 考察流图中变量i，j的引用定值情况 在基本块B2中有相应的引用 d4:i:=i+1 i+1 中的i 在引用前

11、无定值，该引用的ud链仅来自于 INB2中 i 的有关定值集合，即 d1:i:=m 1;d7:i:=u3 类似地，d5:j:=j 1 中的 j 引用-定值链为 d2:j:=n;d5:j:=j 1 如果某变量引用前有定值，则该引用的ud链仅包含该变量的最后定值,2023/8/18,编译原理与技术之代码优化,24,活跃变量分析,活跃变量 d:x:=/语句d是变量x的定值点/从d点开始的某条路径上/有该x值的引用，则称x在/d点活跃u:=x,2023/8/18,编译原理与技术之代码优化,25,活跃变量分析,解决问题 在基本块出口处变量的活跃情况数据流归属 任意路径、向后流数据流分析数据流应用 无用赋

12、值的删除 出口非活跃变量（无需存储、寄存器剥夺）,2023/8/18,编译原理与技术之代码优化,26,2023/8/18,编译原理与技术之代码优化,27,x,y:原来这里也有我们的身影哦。,2023/8/18,编译原理与技术之代码优化,28,y:我走不动了。逆“流”行船，累啊。x:坚持就是胜利。,2023/8/18,编译原理与技术之代码优化,29,x:又觅“活”踪,2023/8/18,编译原理与技术之代码优化,30,x:终于出头啦！,2023/8/18,编译原理与技术之代码优化,31,活跃变量分析,(1)a:=1(2)b:=2,B1,(3)c:=a+b(4)d:=c a,B2,(8)b:=a+

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

14、B1=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=/出口块,2023/8/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+1,B4,(10)a:=b*d(11)b:=a d,B6,b,d,2023

15、/8/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,2023/8/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

16、:=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,2023/8/18,编译原理与技术之代码优化,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,2023/8/18,编译原理与技术之代码优化,38,基本块

17、出口活跃变量,第一次迭代计算,(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,2023/8/18,编译原理与技术之代码优化,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,

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

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

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

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

22、,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,2023/8/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

23、,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,2023/8/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,b,e,2

24、023/8/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,可用表达式数据流分析,数据流应用：寻找公共子表达式。如果在基本块中需要计算某个表达式，而此表达式恰好在其入口处可用，且这之间该表达式的值未被修改，则基本块中无需再计算此表达式。数据流值域：全体（右值）表达式集合U的幂集数据流方向：全路径、前

25、向数据流分析传递函数：语义约束与控制流约束首先，考察基本块中单个语句的语义约束，其次，推广到整个基本块（所有语句），最后考察基本块之间的约束关系。,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的每一个前驱块P的出口点处可用的表达式也将在B的入口点处可用。OUT

26、B：基本块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,示例：基本块生成的表达式,53,可用表达式数据流分析,传递方程：INB=P是B的前驱基本块

27、(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-while,54,在可用表达式分析中，适宜将OUT的初值置为全体表达式集合U而不是空集。令G和K为基本块B2的生成与注销表达式集合，则：INB2=OUTB1 OUTB2OUT

28、B2=G(INB2 K)令Ij和Oj分别为B2在第j次迭代中IN和OUT值；则：I j+1=OUTB1 O jO 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,示例：可用表达式,(1)D=3(2)G=1,(3)B D+DC=D*DA B C,C B+CF=A*A,B B+CF=A+G,G B+C D=D*D,EXIT,ENTRY,B1,B2,B3,B4,B5,56,示例：可用表达式,57,示例：可

29、用表达式,58,可用表达式的迭代计算 计算次序，深度优先序，即 B1-B2-B3-B4-B5-EXIT 边界值：OUTENTRY=;初始化：for all NON-ENTRY B:OUTB U；第一次迭代：(all NON-ENTRY B)(1)INB1=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,第

30、一次迭代：(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 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,D*D

31、,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)=e_GENB1=3,1/不变(2)INB2=OUTB1 OUTB5=3,1 3,1,B+C=3,1/不变 OUTB2=e

32、_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 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/不变,