《最新川师编译原理课件11PPT课件》由会员分享，可在线阅读，更多相关《最新川师编译原理课件11PPT课件（44页珍藏版）》请在金锄头文库上搜索。
1、川师编译原理课件川师编译原理课件111111.1 优化技术简介优化技术简介一、代码优化分类一、代码优化分类编译前端编译前端中间代码优化中间代码优化目标代码目标代码中间代码中间代码目标代码优化目标代码优化7/28/20242吉首大学：莫礼平3 3）变换循环控制条件变换循环控制条件(T1=80) T1=80) 、合并已知量、合并已知量(T1:=4)T1:=4)和复写传播和复写传播(T6:=T5T1)(T6:=T5T1)(5)T3:=T2T1(5)T3:=T2T1(6)T4:=T1(6)T4:=T1(8)T6:=T5(8)T6:=T5T1T1 (9)T7:=T3*T6(9)T7:=T3*T6(10)
2、P:=P+T7(10)P:=P+T7(11)i:=i+1 (11)i:=i+1 (3)T1:=T1+4 (3)T1:=T1+4 (12)IF (12)IF T1=80T1=80 GOTO GOTO (5)(5)(1)P(1)P：=0=0(2)i:=1(2)i:=1(4)T2:=addr(A)-4(4)T2:=addr(A)-4(7)T5:=addr(A)-4(7)T5:=addr(A)-4(3)T1:=(3)T1:=4 4B1：B2：7/28/20249吉首大学：莫礼平4 4）删除无用赋值）删除无用赋值(2)(2)、(6)(6)、(11)(11)(5)T3:=T2T1(5)T3:=T2T1(8
3、)T6:=T5(8)T6:=T5T1T1 (9)T7:=T3*T6(9)T7:=T3*T6(10)P:=P+T7(10)P:=P+T7(3)T1:=T1+4 (3)T1:=T1+4 (12)IF (12)IF T1=80T1y（如取（如取x=20,y=15）时，）时，j值应为值应为1。7/28/202436吉首大学：莫礼平i:=1B1if xy then goto B3i=2; x:=x+1B2B3y:=y-1;if y=20 then goto B5B4j:=iB57/28/202437吉首大学：莫礼平2、代码外提规则、代码外提规则将循环不变运算将循环不变运算s: A:=B op C 外提时
4、，必须外提时，必须满足下列条件满足下列条件(a)(b)之一：之一：(a)： 1) S所在的结点是所在的结点是L的所有出口点的必经点；的所有出口点的必经点； 2) A在在L中其它地方未定值；中其它地方未定值； 3) L中所有中所有A的引用点，只有的引用点，只有s中中A的定值才的定值才能到达。能到达。(b) ：A在离开在离开L之后不再是活跃之后不再是活跃(即不再被引用即不再被引用)的。的。7/28/202438吉首大学：莫礼平3、强度削弱和删除归纳变量、强度削弱和删除归纳变量1）强度削弱强度削弱 指将程序中执行时间较长的运算替换为执指将程序中执行时间较长的运算替换为执行时间较短的运算。如将乘方换乘
5、法，乘法换行时间较短的运算。如将乘方换乘法，乘法换加法等；加法等；2）删除归纳变量删除归纳变量 如果循环中有如果循环中有I:=I+C;J=C1*I+C2，则对于，则对于基本归纳变量基本归纳变量I 的线性增长关系（的线性增长关系（C为循环不为循环不变量）可转换成为与变量）可转换成为与I同族的归纳变量同族的归纳变量J的线性的线性增长关系，从而可删除增长关系，从而可删除I的递归定值四元式。的递归定值四元式。3）删除归纳变量在强度削弱之后进行。删除归纳变量在强度削弱之后进行。7/28/202439吉首大学：莫礼平11.4 数据流的分析与全局优化数据流的分析与全局优化一、基本概念一、基本概念1、到达、到
6、达-定值定值： 定值点定值点d到达到达p是指流图中从是指流图中从d有一条路有一条路径到达径到达p且该通路上没有且该通路上没有A 的其它定值。的其它定值。2、引用、引用-定值链定值链(u-d)链：链： 到达到达u的所有的所有A的定值点的全体。的定值点的全体。3、定值、定值-引用链引用链(d-u)链：链： d能到达的所有引用点的全体。能到达的所有引用点的全体。7/28/202440吉首大学：莫礼平二、到达二、到达-定值方程定值方程1 1、方程：、方程： outs=(ins-kills)gensgens inB: inB:到达基本块入口前的变量定值点；到达基本块入口前的变量定值点； killB ki
7、llB：在基本块中被在基本块中被“注销注销”的定值点；的定值点； genB genB：在：在B B中定值并到达中定值并到达B B出口之后的所出口之后的所有定值点集。有定值点集。2 2、例子：、例子：7/28/202441吉首大学：莫礼平d1: i=2; d2: j:=i+1d3: i:=1d4: j:=j+1d5: j:=j-4d6: a:=i; d7: b:=jB1B2B3B4B5genBgenB位向量位向量位向量位向量killBkillB 位向量位向量位向量位向量B1B1 d1,d2d1,d2 11000001100000 d3,d4,d3,d4,d5d500111000011100B2B
8、2d3d300100000010000d1d110000001000000B3B3d4d400010000001000 d2d5d2d5 01001000100100B4B4d5d500001000000100 d2,d4d2,d4 01010000101000B5B5 00000000000000 000000000000007/28/202442吉首大学：莫礼平n n求求ud链的迭代过程链的迭代过程(in初值为初值为,out,out,out,out初值为初值为初值为初值为gengengengen )一一一一二二二二三三三三四四四四inoutinoutinoutinoutB1(2B1(2)
9、)0010001000000011001100000000011001100000001100110000000001110111100100110011000000000111011110010011001100000000B2(1,B2(1,5)5)1100110000000001100110000000111111111001000111011110010011111111100100011101111001001111111110010001110111100100B3(2B3(2) )01100110000000001100110000000111011110010000110011
10、00000001110111100100011101111001000111011110010000100010100100B4(3B4(3) )0011001100000000100010100100001100110000000010001010010000110011000000001000101001000011001100000000100010100100B5(3,B5(3,4)4)00110011100100001100111001000011001110010000110011100100001100111001000011001110010000110011100100001100111001007/28/202443吉首大学：莫礼平结束语结束语谢谢大家聆听！谢谢大家聆听！44
