代码优化ppt课件.ppt
代码优化ppt课件 Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life,there is hope。有生命必有希望。有生命必有希望代码优化的目标提高最终目标代码的运行效率（性能）时间：运行的更快 空间：降低内存需求保持源程序的语义2022/11/11编译原理与技术之代码优化3代码优化（续）全局数据流分析技术2022/11/11编译原理与技术之代码优化4全局数据流分析基本块基本块INBOUTBKILLBGENB到达基本块入口处的相关数据流信息到达基本块出口处的相关数据流信息基本块“产生”的相关数据流信息基本块“注销”的相关数据流信息2022/11/11编译原理与技术之代码优化5全局数据流分析数据流的“方向”正向（向前）数据流：与控制流方向一致 OUTB由INB来计算 INB则由B的所有前驱结 点的OUT来决定控制流数据流前驱1前驱2基本块B表示数据流信息交汇（合流）处2022/11/11编译原理与技术之代码优化6全局数据流分析数据流的“方向”反向（向后）数据流：与控制流方向相逆 INB由OUTB 来计算 OUT B则由B的所有后继结 点的IN来决定控制流数据流基本块B后继1后继2表示数据流信息交汇（合流）处2022/11/11编译原理与技术之代码优化7全局数据流分析向前流向后流任意路径OUTB=GENB (INB-KILLB)INB=OUTP,PPred(B)INB=GENB(OUTB-KILLB)OUTB=INS,SSucc(B)全路径OUTB=GENB(INB-KILLB)INB=OUTP,PPred(B)INB=GENB(OUTB-KILLB)OUTB=INS,SSucc(B)表表1.数据流分析方程数据流分析方程2022/11/11编译原理与技术之代码优化8全局数据流方程求解迭代计算：直至某先后两次迭代计算结果一样迭代次序 向前流：流图深度优先次序 向后流：流图深度优先次序的逆序 流图深度优先次序：对流图进行深度优先遍历，得到流图深度 优先扩展树；对该树进行前序遍历时最后 访问结点的逆序迭代初始计算（值）2022/11/11编译原理与技术之代码优化912345678910e.g.一个流图一个流图12346781095e.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，102022/11/11编译原理与技术之代码优化10全局数据流方程求解向前流向后流问题初始值问题初始值任意路径到达-定值/ud链活跃变量未初始化变量所有变量du链全路径可用表达式非常忙表达式复写传播表表2.常用的数据流分析常用的数据流分析2022/11/11编译原理与技术之代码优化11到达定值数据流分析定值与引用d:x:=y+z /语句d 是变量x的一个定值点u:w:=x+v/语句u 是变量x的一个引用点变量x在d点的定值到达u点流图中有路径d-u，且该路径上没有x的其它（无二义）定值。2022/11/11编译原理与技术之代码优化12到达定值数据流分析解决的问题 定值“传播”数据流归属 任意路径、向前流的数据流分析 INB，到达基本块入口处定值集合 OUTB，到达基本块出口处定值集合 GENB，基本块产生且能到达基本块出口的定值集合 KILLB，由基本块注销的定值集合（这些定值不能传播或到达到块出口）数据流应用 ud链，即引用定值链。可以据此判断基本块内的某变量引用，其值来自何方（定值）。如应用于循环不变式的寻找。2022/11/11编译原理与技术之代码优化13OUT:dm:x:=OUT:dn:x:=前驱1前驱2 ds:s:=x dt:x:=du:x:=INBOUTB=?控制流2022/11/11编译原理与技术之代码优化14OUT:dm:x:=OUT:dn:x:=前驱1前驱2 ds:s:=x dt:x:=du:x:=INBOUTB=?英雄惜英雄，dm 和 dn相会在汇流点，共赴INB2022/11/11编译原理与技术之代码优化15OUT:dm:x:=OUT:dn:x:=前驱1前驱2 ds:s:=x dt:x:=du:x:=INBOUTB=?dm和dn：一路无险遇 ds2022/11/11编译原理与技术之代码优化16OUT:dm:x:=OUT:dn:x:=前驱1前驱2 ds:s:=x dt:x:=du:x:=INBOUTB=?dm和dn：再走一程见 dt，_2022/11/11编译原理与技术之代码优化17OUT:dm:x:=OUT:dn:x:=前驱1前驱2 ds:s:=x dt:x:=du:x:=INBOUTB=?dm和dn：我们被dt所“屏蔽”。不知何时上了“注销”榜？dt:你们歇着吧。我要 Go Go Go2022/11/11编译原理与技术之代码优化18OUT:dm:x:=OUT:dn:x:=前驱1前驱2 ds:s:=x dt:x:=du:x:=INBOUTB=?dt：等等，我咋也上榜了？唉，既生t，何生u?du：数“流”人，还看 2022/11/11编译原理与技术之代码优化19OUT:dm:x:=OUT:dn:x:=前驱1前驱2 ds:s:=x dt:x:=du:x:=INBOUTB=?du:顺利过关。嗯，要是没有我和dt的阻击，现在站在这里的就是dm和dn。只可惜了dt 2022/11/11编译原理与技术之代码优化20到达定值数据流分析d1:i:=m-1d2:j:=nd3:a:=u1d4:i:=i+1d5:j:=j-1d6:a:=u2d7:i:=u3B1B2B3B4GENB1=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.求解到达定值的数据流图2022/11/11编译原理与技术之代码优化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 2022/11/11编译原理与技术之代码优化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,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 不再变化。2022/11/11编译原理与技术之代码优化23ud链 考察流图中变量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链仅包含该变量的最后定值 2022/11/11编译原理与技术之代码优化24活跃变量分析活跃变量 d:x:=/语句d是变量x的定值点 /从d点开始的某条路径上/有该x值的引用，则称x在 /d点活跃u:=x 2022/11/11编译原理与技术之代码优化25活跃变量分析解决问题 在基本块出口处变量的活跃情况数据流归属 任意路径、向后流数据流分析数据流应用 无用赋值的删除 出口非活跃变量（无需存储、寄存器剥夺）2022/11/11编译原理与技术之代码优化26dm:=x dn:y:=后继1后继2x活跃y活跃OUTBINB2022/11/11编译原理与技术之代码优化27dm:=x dn:y:=后继1后继2x活跃y活跃OUTBINBx,y:原来这里也有我们的身影哦。2022/11/11编译原理与技术之代码优化28dm:=x dn:y:=后继1后继2x活跃y活跃OUTBINBy:我走不动了。逆“流”行船，累啊。x:坚持就是胜利。2022/11/11编译原理与技术之代码优化29dm:=x dn:y:=后继1后继2x活跃y活跃OUTBINBx:又觅“活”踪2022/11/11编译原理与技术之代码优化30dm:=x dn:y:=后继1后继2x活跃y活跃OUTBINBx:终于出头啦！2022/11/11编译原理与技术之代码优化31活跃变量分析(1)a:=1(2)b:=2B1(3)c:=a+b(4)d:=c a B2(8)b:=a+b(9)e:=c a B5(5)d:=b*dB3(6)d:=a+b(7)e:=e+1B4(10)a:=b*d(11)b:=a d B62022/11/11编译原理与技术之代码优化32基本块出口活跃变量迭代计算OUTB=INS,SSucc(B)INB =USEB (OUTB-DEFB)USEB基本块B中有引用且该引用前无定值的变量集合；DEFB基本块B中有定值且该定值前无引用的变量集合；计算次序 结点深度优先序的逆序（向后流）:B6 B5 B4 B3 B2 B1 2022/11/11编译原理与技术之代码优化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=/出口块2022/11/11编译原理与技术之代码优化34基本块出口活跃变量第一次迭代计算(1)a:=1(2)b:=2B1(3)c:=a+b(4)d:=c a B2(8)b:=a+b(9)e:=c a B5(5)d:=b*dB3(6)d:=a+b(7)e:=e+1B4(10)a:=b*d(11)b:=a d B6 b,d 2022/11/11编译原理与技术之代码优化35基本块出口活跃变量第一次迭代计算(1)a:=1(2)b:=2B1(3)c:=a+b(4)d:=c a B2(8)b:=a+b(9)e:=c a B5(5)d:=b*dB3(6)d:=a+b(7)e:=e+1B4(10)a:=b*d(11)b:=a d B6 b,d b,d a,b,c,d 2022/11/11编译原理与技术之代码优化36基本块出口活跃变量第一次迭代计算(1)a:=1(2)b:=2B1(3)c:=a+b(4)d:=c a B2(8)b:=a+b(9)e:=c a B5(5)d:=b*dB3(6)d:=a+b(7)e:=e+1B4(10)a:=b*d(11)b:=a d B6 b,d b,d a,b,c,d a,b,e 2022/11/11编译原理与技术之代码优化37基本块出口活跃变量第一次迭代计算(1)a:=1(2)b:=2B1(3)c:=a+b(4)d:=c a B2(8)b:=a+b(9)e:=c a B5(5)d:=b*dB3(6)d:=a+b(7)e:=e+1B4(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 2022/11/11编译原理与技术之代码优化38基本块出口活跃变量第一次迭代计算(1)a:=1(2)b:=2B1(3)c:=a+b(4)d:=c a B2(8)b:=a+b(9)e:=c a B5(5)d:=b*dB3(6)d:=a+b(7)e:=e+1B4(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 2022/11/11编译原理与技术之代码优化39基本块出口活跃变量第一次迭代计算(1)a:=1(2)b:=2B1(3)c:=a+b(4)d:=c a B2(8)b:=a+b(9)e:=c a B5(5)d:=b*dB3(6)d:=a+b(7)e:=e+1B4(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 2022/11/11编译原理与技术之代码优化40基本块出口活跃变量第二次迭代计算(1)a:=1(2)b:=2B1(3)c:=a+b(4)d:=c a B2(8)b:=a+b(9)e:=c a B5(5)d:=b*dB3(6)d:=a+b(7)e:=e+1B4(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 2022/11/11编译原理与技术之代码优化41基本块出口活跃变量第二次迭代计算(1)a:=1(2)b:=2B1(3)c:=a+b(4)d:=c a B2(8)b:=a+b(9)e:=c a B5(5)d:=b*dB3(6)d:=a+b(7)e:=e+1B4(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 2022/11/11编译原理与技术之代码优化42基本块出口活跃变量第二次迭代计算(1)a:=1(2)b:=2B1(3)c:=a+b(4)d:=c a B2(8)b:=a+b(9)e:=c a B5(5)d:=b*dB3(6)d:=a+b(7)e:=e+1B4(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 2022/11/11编译原理与技术之代码优化43基本块出口活跃变量第二次迭代计算(1)a:=1(2)b:=2B1(3)c:=a+b(4)d:=c a B2(8)b:=a+b(9)e:=c a B5(5)d:=b*dB3(6)d:=a+b(7)e:=e+1B4(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 2022/11/11编译原理与技术之代码优化44基本块出口活跃变量第二次迭代计算(1)a:=1(2)b:=2B1(3)c:=a+b(4)d:=c a B2(8)b:=a+b(9)e:=c a B5(5)d:=b*dB3(6)d:=a+b(7)e:=e+1B4(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 2022/11/11编译原理与技术之代码优化45基本块出口活跃变量第二次迭代计算(1)a:=1(2)b:=2B1(3)c:=a+b(4)d:=c a B2(8)b:=a+b(9)e:=c a B5(5)d:=b*dB3(6)d:=a+b(7)e:=e+1B4(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 2022/11/11编译原理与技术之代码优化46基本块出口活跃变量第三次迭代与前一次结果一样，计算结束(1)a:=1(2)b:=2B1(3)c:=a+b(4)d:=c a B2(8)b:=a+b(9)e:=c a B5(5)d:=b*dB3(6)d:=a+b(7)e:=e+1B4(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 2022/11/11编译原理与技术之代码优化4748可用表达式数据流分析如果从流图入口结点到达程序点p的每一条路径上均对表达式x+y求值，且每条路径上最后一个这样的求值之后到p点的路径上没有对x或y赋值，那么称x+y在点p可用（available）。显然，可用表达式分析属于 全路径数据流问题。ENTRYu=x+yu=x+yu=x+y p49可用表达式数据流分析数据流应用：寻找公共子表达式。如果在基本块中需要计算某个表达式，而此表达式恰好在其入口处可用，且这之间该表达式的值未被修改，则基本块中无需再计算此表达式。数据流值域：全体（右值）表达式集合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的每一个前驱块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示例：基本块生成的表达式语句可用表达式 a=b+c b+c b=a d a d /b+c被杀死c=b+c a d /b+c被杀死d=a d /a d 被杀死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-while54在可用表达式分析中，适宜将OUT的初值置为全体表达式集合U而不是空集。令G和K为基本块B2的生成与注销表达式集合，则：INB2=OUTB1 OUTB2OUTB2=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的出口处可用。这正是我们所希望的！B1B255示例：可用表达式示例：可用表达式(1)D=3(2)G=1(3)B D+D(4)C =D*D(5)A B C(8)C B+C(9)F =A*A(6)B B+C(7)F =A+G(10)G B+C(11)D =D*D EXIT ENTRYB1B2B3B4B556示例：可用表达式示例：可用表达式基本块前驱后继ENTRYB1B1ENRTYB2B2B1 B5B3 B4B3B2B5B4B2B5B5B3 B4B2 EXITEXITB557示例：可用表达式示例：可用表达式基本块e_gene_killENTRY B13 1 D+D,D*D,A+G B2 D+D,D*D,B+C A*A,A+G B3 A+G B+C B4 A*A B+C B5 B+C A+G,D*D,D+D EXIT全部表达式U=3,1,D+D,D*D,B+C,A+G,A*A 58可用表达式的迭代计算可用表达式的迭代计算 计算次序，深度优先序，计算次序，深度优先序，即即 B1-B2-B3-B4-B5-EXIT 边界值：边界值：OUTENTRY=;初始化：初始化：for all NON-ENTRY B:OUTB U U ；第一次迭代：第一次迭代：(all NON-ENTRY B)(1)INB1 =OUTENTRY=;/B1;/B1 前驱仅为前驱仅为ENTRYENTRY OUTB1=e OUTB1=e_GENB1 GENB1(INB1 e_KILLB1)=e_GENB1=3,1 /变化变化(2)INB2 =OUTB1 OUTB5 =3,1 U U =3,1 OUTB2=e_GENB2 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_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,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 OUTB1=e e_GENB1 GENB1(INB1 e_KILLB1)=e_GENB1=3,1 /不变不变(2)INB2 =OUTB1 OUTB5 =3,1 3,1,B+C =3,1 /不变不变 OUTB2=eOUTB2=e_GENB2 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 /不变不变
