编译原理 代码优化2.ppt

代码优化,代码优化的目标,提高最终目标代码的运行效率（性能）时间：运行的更快 空间：降低内存需求保持源程序的语义,2023/4/26,编译原理与技术之代码优化,3,代码优化（续）,全局数据流分析技术,2023/4/26,编译原理与技术之代码优化,4,全局数据流分析,基本块,INB,OUTB,KILLB,GENB,到达基本块入口处的相关数据流信息,到达基本块出口处的相关数据流信息,基本块“产生”的相关数据流信息,基本块“注销”的相关数据流信息,2023/4/26,编译原理与技术之代码优化,5,全局数据流分析,数据流的“方向”正向（向前）数据流：与控制流方向一致 OUTB由INB来计算 INB则由B的所有前驱结 点的OUT来决定,控制流,数据流,前驱1,前驱2,基本块B,表示数据流信息交汇（合流）处,2023/4/26,编译原理与技术之代码优化,6,全局数据流分析,数据流的“方向”反向（向后）数据流：与控制流方向相逆 INB由OUTB 来计算 OUT B则由B的所有后继结 点的IN来决定,控制流,数据流,基本块B,后继1,后继2,表示数据流信息交汇（合流）处,2023/4/26,编译原理与技术之代码优化,7,全局数据流分析,表1.数据流分析方程,2023/4/26,编译原理与技术之代码优化,8,全局数据流方程求解,迭代计算：直至某先后两次迭代计算结果一样迭代次序 向前流：流图深度优先次序 向后流：流图深度优先次序的逆序 流图深度优先次序：对流图进行深度优先遍历，得到流图深度 优先扩展树；对该树进行前序遍历时最后 访问结点的逆序迭代初始计算（值）,2023/4/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,2023/4/26,编译原理与技术之代码优化,10,全局数据流方程求解,表2.常用的数据流分析,2023/4/26,编译原理与技术之代码优化,11,到达定值数据流分析,定值与引用d:x:=y+z/语句d 是变量x的一个定值点u:w:=x+v/语句u 是变量x的一个引用点变量x在d点的定值到达u点,流图中有路径d-u，且该路径上没有x的其它（无二义）定值。,2023/4/26,编译原理与技术之代码优化,12,到达定值数据流分析,解决的问题 定值“传播”数据流归属 任意路径、向前流的数据流分析 INB，到达基本块入口处定值集合 OUTB，到达基本块出口处定值集合 GENB，基本块产生且能到达基本块出口的定值集合 KILLB，由基本块注销的定值集合（这些定值不能传播或到达到块出口）数据流应用 ud链，即引用定值链。可以据此判断基本块内的某变量引用，其值来自何方（定值）。如应用于循环不变式的寻找。,2023/4/26,编译原理与技术之代码优化,13,OUT:dm:x:=,OUT:dn:x:=,前驱1,前驱2,ds:s:=x dt:x:=du:x:=,INB,OUTB=?,控制流,2023/4/26,编译原理与技术之代码优化,14,OUT:dm:x:=,OUT:dn:x:=,前驱1,前驱2,ds:s:=x dt:x:=du:x:=,INB,OUTB=?,英雄惜英雄，dm 和 dn相会在汇流点，共赴INB,2023/4/26,编译原理与技术之代码优化,15,OUT:dm:x:=,OUT:dn:x:=,前驱1,前驱2,ds:s:=x dt:x:=du:x:=,INB,OUTB=?,dm和dn：一路无险遇 ds,2023/4/26,编译原理与技术之代码优化,16,OUT:dm:x:=,OUT:dn:x:=,前驱1,前驱2,ds:s:=x dt:x:=du:x:=,INB,OUTB=?,dm和dn：再走一程见 dt，_,2023/4/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,2023/4/26,编译原理与技术之代码优化,18,OUT:dm:x:=,OUT:dn:x:=,前驱1,前驱2,ds:s:=x dt:x:=du:x:=,INB,OUTB=?,dt：等等，我咋也上榜了？唉，既生t，何生u?du：数“流”人，还看,2023/4/26,编译原理与技术之代码优化,19,OUT:dm:x:=,OUT:dn:x:=,前驱1,前驱2,ds:s:=x dt:x:=du:x:=,INB,OUTB=?,du:顺利过关。嗯，要是没有我和dt的阻击，现在站在这里的就是dm和dn。只可惜了dt,2023/4/26,编译原理与技术之代码优化,20,到达定值数据流分析,d1:i:=m-1d2:j:=nd3:a:=u1,d4:i:=i+1d5: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.求解到达定值的数据流图,2023/4/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,2023/4/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,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/4/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链仅包含该变量的最后定值,2023/4/26,编译原理与技术之代码优化,24,活跃变量分析,活跃变量 d:x:=/语句d是变量x的定值点/从d点开始的某条路径上/有该x值的引用，则称x在/d点活跃u:=x,2023/4/26,编译原理与技术之代码优化,25,活跃变量分析,解决问题 在基本块出口处变量的活跃情况数据流归属 任意路径、向后流数据流分析数据流应用 无用赋值的删除 出口非活跃变量（无需存储、寄存器剥夺）,2023/4/26,编译原理与技术之代码优化,26,2023/4/26,编译原理与技术之代码优化,27,x,y:原来这里也有我们的身影哦。,2023/4/26,编译原理与技术之代码优化,28,y:我走不动了。逆“流”行船，累啊。x:坚持就是胜利。,2023/4/26,编译原理与技术之代码优化,29,x:又觅“活”踪,2023/4/26,编译原理与技术之代码优化,30,x:终于出头啦！,2023/4/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,2023/4/26,编译原理与技术之代码优化,32,基本块出口活跃变量,迭代计算OUTB=INS,SSucc(B)INB=USEB(OUTB-DEFB)USEB基本块B中有引用且该引用前无定值的变量集合；DEFB基本块B中有定值且该定值前无引用的变量集合；计算次序 结点深度优先序的逆序（向后流）:B6 B5 B4 B3 B2 B1,2023/4/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=/出口块,2023/4/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,2023/4/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,2023/4/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,2023/4/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,2023/4/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,2023/4/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,2023/4/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,2023/4/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,2023/4/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,2023/4/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,2023/4/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,2023/4/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,2023/4/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,