第11章 代码优化精.ppt

《第11章 代码优化精.ppt》由会员分享，可在线阅读，更多相关《第11章 代码优化精.ppt（59页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第11章 代码优化第1页，本讲稿共59页11.1 11.1 代码优化种类代码优化种类从范围上分为:局部优化全局优化 主要的局部优化有基本块上的优化和循环上的优化。基本块上的优化主要有常表达式节省(合并常数)、公共表达式节省(消除多余运算)。第2页，本讲稿共59页 循环上的优化主要有不变表达式外提和削减运算强度。除了这些较典型的优化外还有:1.消除无用赋值。2.删除无用的0和1：A*1 处理为A A*0 处理为0第3页，本讲稿共59页 A0 处理为A A/1 处理为A 0/A 处理为0 等等。3.合并符号:(-X)*(-Y)处理为X*Y 4.用乘法代替指数运算:A*2 处理为A*A A*3 处理

2、为A*A*A 等。第4页，本讲稿共59页11.2 11.2 基本块基本块基本块可定义于原代码,中间代码,也可定义于目标代码。关于目标代码的基本块的定义是：说一个目标代码是基本块,当且仅当该段只有一个入口和一个出口。定义于原代码,中间代码的基本块定义类似。第5页，本讲稿共59页基本块的特点是其中的代码要么全执行,要么全不执行,不能在中途转出,也不能从中间转入。基本块类似程序中的函数，软件工程中的模块。第6页，本讲稿共59页基本块的划分方法：1.把第一个四元式作为第一个基本块的入口四元式。第一个四元式第一个四元式2.当遇标号性四元式时，结束当前块，并作为新块的入口四元式。标号性四元式标号性四元式第

3、一个四元式第一个四元式第7页，本讲稿共59页3.当遇转移性四元式时，结束当前块，并作为当前块的出口四元式。他们的后继四元式作为新的入口四元式。转移性四元式转移性四元式4.当遇形如(=:,A,X)的赋值四元式(其中X为引用形参)时，结束当前块，并作为该块的出口四元式。含引用形参含引用形参赋值四元式赋值四元式第8页，本讲稿共59页 标号性的四元式有：(label，l )(while，)(proc，q，Noff，Moff)(func，f，Noff，Moff)(ifend，)等。第9页，本讲稿共59页(goto，l)(then，B，)(else，)(whend，)(call，g，)(call，f，T)

4、等。转移性的四元式有：第10页，本讲稿共59页例子：设有一程序段 Y:=1；100：if AB then X:=0 else Y:=0;X:=X+1；Y:=Y-1；if A，A，B，T1)AB (then，T1，)(=：，0，X)X:=0 (else，)(=：，0，Y)Y:=0 第12页，本讲稿共59页 (ifend，)(+,X，1，T2)X+1 (=:,T2，X )X:=X+1 (,Y，1，T3)Y-1 (=:,T3,Y)Y:=Y-1 (,A,B,T4)A，A，B，T1)AB (then，T1，)转移性四元式 B3:(=：，0，X)X:=0 (else，)转移性四元式 B4:(=：，0，Y)

5、Y:=0 第14页，本讲稿共59页B5:(ifend，)标号性四元式 (+,X，1，T2)X+1 (=:,T2，X )X:=X+1 (,Y，1，T3)Y-1 (=:,T3,Y)Y:=Y-1 (,A,B,T4)AB (then,T4,)转移性四元式B6:(goto,，100)转移性四元式B7:(ifend,)标号性四元式 (=:0，Z)Z:=0第15页，本讲稿共59页 B1 B2 B3 B4 B5 B6 B7 程序图如下:第16页，本讲稿共59页11.3 11.3 常表达式节省常表达式节省常表达式节省也叫合并常数。它的优化范围通常取基本块。优化工作可在生成四元式的同时进行，也可在生成四元式后进行

6、。前一种方法叫单遍扫描法，而后一种叫多遍扫描法。第17页，本讲稿共59页例：程序代码a:=10；b:=2*a；c:=a*b；可以转化为：a:=10；b:=20；c:=200；优化后的四元式：1)(=:，10，-,a)2)(=:，20，-,b)3)(=:，200，-,c)第18页，本讲稿共59页下面介绍独立进行的多遍扫描法，用到变量值表VVL，其结构如下：VVLk：NAME VALU 变量名部分值部分第19页，本讲稿共59页多遍扫描常表达式节省算法1.VVL表置空，令i指向本块的第一个四元式.2.若对j=1,2,存在k:QTi.OPRj=VVLk.NAME,则做QTi.OPRj:=VVLk.VA

7、LU (从表中取值)3.若OTi.不是运算符,则转向5.(进一步判别该四元式是否为赋值语句)4.如果QTi.OPRj(j=1,2)都是常数,则计算结果,填VVL表,并删除四元式QTi:ENTRY(QTi.RESU,cons)(填写表中值)QTi:=(,)(四元式节省)第20页，本讲稿共59页 转向6.其中ENTRY是填写VVL表的子程序,cons表示计算结果的CONSL表地址.若有同名项,则只改内容.5.若QTi.“:=”则转向6;否则 (赋值语句)(a)若QTi.OPR1是常数,则填VVL表:ENTRY(QTi.RESU,QTi.OPR1)(b)若QTi.OPR1是非常数,则删VVL表:DE

8、LET(QTi.RESU)其中DELET(X)表示从VVL表删去包含X名字的项,如果没有那种项,则什么也不做.第21页，本讲稿共59页6.i:=i+1;若QTi不是出口型四元式,则转向2,否则结束.例：合并常数 i:=2+5;j:=i+3;k:=2*i+j;i:=i*j+k+m;第22页，本讲稿共59页(=,T7,-,l)11.(=:,T7,-,l)(+,94,m,T7)10.(+,T6,m,T6)9.(T6,94)($,-,-,-)9.(+,T5,k,T6)8.(T5,70)($,-,-,-)8.(*,i,j,T5)i:=i*j+k+m;7.(k,24)(=:,24,-,k)7.(=:,T4

9、,-,k)6.(T4,24)($,-,-,-)6.(+,T3,j,T4)5.(T3,14)($,-,-,-)5.(*,2,i,T3)k:=2*i+j;4.(j,10)(=:,10,-,j)4.(=:,T2,-,j)3.(T2,10)($,-,-,-)3.(+,i,3,T2)j:=i+3;2.(i,7)(=:,7,-,i)2.(=:,T1,-,i)1.(T1,7)($,-,-,-)1.(+,2,5,T1)i:=2+5;VVL表 合并后的合并前的源代码 第23页，本讲稿共59页11.4 11.4 公共表达式节省公共表达式节省 公共表达式节省的范围是一个基本块。如果两个四元式的和OPR1及OPR2的

10、值分别相同,则称这两个四元式等价。如果在基本块中出现多个等价四元式,则除了第一个外其他的均可节省。公共表达式节省工作是通过四元式的节省来实现的。实现四元式节省的关键是判别两个四元式是否等价。第24页，本讲稿共59页例:设有程序段：D:=D+C*B;A:=D+C*B;C:=D+C*B;问:是否可以写成下面的程序?T:=D+C*B;D:=T;A:=T;C:=T;第25页，本讲稿共59页它的四元式所构成的基本块为：1(*，C,B,T1)C*B 2(+,D,T1,T2)D+C*B 3(=:,T2,D)D:=D+C*B 4(*,C,B,T3)C*B 5(+,D,T3,T4)D+C*B 6(=:,T4,A

11、)A:=D+C*B 7(*,C,B,T5)C*B 8(+,D,T5,T6)D+C*B 9(=:T6,C)C:=D+C*B第26页，本讲稿共59页其中四元式1，4，7的运算符、OPR1、OPR2均相等，所以可以用T1代替T3、T5。1(*，C,B,T1)C*B 2(+,D,T1,T2)D+C*B 3(=:,T2,D)D:=D+C*B 4()被省略 5(+,D,T T1 1,T4)D+C*B 6(=:,T4,A)A:=D+C*B 7()被省略 8(+,D,T T1 1,T6)D+C*B 9(=:T6,C)C:=D+C*B第27页，本讲稿共59页 其中四元式2,5,8的运算符、OPR1、OPR2均相

12、等但5、8中的D与2中的不同所以不可以用T2代替T4、T6。四元式5和8相同因此四元式8对5是多余的。第28页，本讲稿共59页经优化后可得到下列四元式代码：1(*,C,B，T1)2(+,D,T1，T2)3(=:,T2,，D)4()被省略 5(+,D,T1，T3)6(=,T3,A)7()被省略 8()被省略 9(=:,T3,C)第29页，本讲稿共59页公共表达式节省是通过四元式的节省来实现的。目前已提出多种实现方法，其中包括：值编码法，依赖数法，逻辑尺法，DAG法等。值编码方法：按一定规则给四元式中的每个变量进行编码,使得具有相同编码的变量具有相同值。判定两个四元式是否等价的方法是看其分量的编码

13、是否分别相同。第30页，本讲稿共59页判断四元式等价的关键是判断两个变量的值是否等价。使问题复杂化的主要因素是间接变量的存在。间接变量:引用型形参变量 存复合变量地址的临时变量为了判断一个变量是否依赖于间接变量,引进编码#,首先使间接变量取编码#;其次,假设(,A,B,C)且A,B 中有一个编码取#,则令C的编码取#。如果四元式有一分量的编码为#,则该四元式就不可节省。第31页，本讲稿共59页 设当前四元式为(,A,B,C)，且用newn表示新的编码值。值编码规则：1.开始对一切X,令n(X)=0,以表示未编过码。2.若操作数A是未编过码的并且是非间接变量，则给新的编码（否则给老的编码）IF

14、indirect(A)THEN N(A):=#ELSE IF n(A)=0 THEN n(A)=newn第32页，本讲稿共59页 3.对操作数B类似步骤2。4.对于C的处理过程是：a)(=:,A,-,C)情况 IF direct(C)THEN n(C):=n(A)ELSE n(C):=#b)(,A,B,C),(,A,B,C)情况 n(C):=#c)其他情况：IF n(A)=#n(B)=#THEN n(C):=#ELSE n(C):=newn第33页，本讲稿共59页例：(下边四元式中没有间接变量)X:=1 Z:=X*Y X:=1 W:=X*Y 得到的四元式如下：第34页，本讲稿共59页 4 4

15、6.(=:,T2,-,W)1 2 4 5.(*,X,Y,T2)1 1 4.(=:,1，-,X)3 3 3.(=:,T1,-,Z)1 2 3 2.(*,X，Y,T1)1 1 1.(=：,1,-,X)编 码 四 元 式 第35页，本讲稿共59页 多边扫描公共表达式节省算法：设新老变量名表为ML,每当一个四元式被节省时要填写ML表。1.置ML表为空,令所有量均无编码,i:=i0.2.若QTi的OPR1或OPR2ML,则用ML中的 老名代替OPR1或OPR2.（使用新老变量名表ML）3.若QTi为非考虑类,则转8.（处理下一四元式）4.对QTi中的三个变量进行编码.5.若QTi.=“=:”,则转8.第

16、36页，本讲稿共59页例：A:=3*X+Y B:=(3*X+Y)*A得到的四元式如下：6.若QTi的OPR1或OPR2的编码为#,则转8.7.若存在i使QTiQTi(等价),则 a.QTi:=($,-，-，-)b.MLm:=(QTi.RESU,QTi.RESU)（填写新老变量名表ML）8.i:=i+1;若本块未完转,否则结束.第37页，本讲稿共59页(=:,T5,-,B)8 8 7.(=:,T5,-,B)(*,T2,A,T5)5(7)5 8 6.(*,T4,A,T5)($,-,-,-)3(6)4 7 5.(+,T3,Y,T4)($,-,-,-)1 2 6 4.(*,3,X,T3)(=:,T2,

17、-,A)5 5 3.(=:,T2,-,A)(+,T1,Y,T2)3 4 5 2.(+,T1,Y,T2)(*,3,X,T1)1 2 3 1.(*,3,X,T1)优 化 后 编 码 优 化 前 第38页，本讲稿共59页例：设有语句列 X:=X*Y+Z;Y:=X*Y+Z;Z:=X*Y-Z 试用值编码法写出优化和优化后的四元式中间代码。第39页，本讲稿共59页 优化前1.(*,X,Y,T1)2.(+,T1,Z,T2)3.(:=,T2,-,X)4.(*,X,Y,T3)5.(+,T3,Z,T4)6.(:=,T4,-,Y)7.(*,X,Y,T5)8.(-,T5,Z,T6)9.(:=,T6,-,Z)第40页，

18、本讲稿共59页 优化前 编码1.(*,X,Y,T1)(1,2,3)2.(+,T1,Z,T2)(3,4,5)3.(:=,T2,-,X)(5,5)4.(*,X,Y,T3)(5,2,6)5.(+,T3,Z,T4)(6,4,7)6.(:=,T4,-,Y)(7,7)7.(*,X,Y,T5)(5,7,8)8.(-,T5,Z,T6)(8,4,9)9.(:=,T6,-,Z)(9,9)第41页，本讲稿共59页 优化前 编码 优化后 1.(*,X,Y,T1)(1,2,3)(*,X,Y,T1)2.(+,T1,Z,T2)(3,4,5)(+,T1,Z,T2)3.(:=,T2,-,X)(5,5)(:=,T2,-,X)4.

19、(*,X,Y,T3)(5,2,6)(*,X,Y,T3)5.(+,T3,Z,T4)(6,4,7)(+,T3,Z,T4)6.(:=,T4,-,Y)(7,7)(:=,T4,-,Y)7.(*,X,Y,T5)(5,7,8)(*,X,Y,T5)8.(-,T5,Z,T6)(8,4,9)(-,T5,Z,T6)9.(:=,T6,-,Z)(9,9)(:=,T6,-,Z)第42页，本讲稿共59页 基本块上的优化算法（同时进行常表达式和公共表达式节省。例：设有 VAR a:ARRAY110 OF 110 OF integer 和 aij:=aij-1(-,j,1，T4)7 2 8 4.(-,j,1,T4)(,a,T2

20、,T3)6 5#3.(,a,T2,T3)(*,T1,10,T2)3 4 5 2.(*,T1,10,T2)(-,i,1,T1)1 2 3 1.(-,i,1,T1)优 化 后 编 码 优 化 前 第43页，本讲稿共59页(=:,T11,-,T5)#12.(=:,T11,-,T5)(,a,T10,T11)#12#11.(,T6,T10,T11)(-,T4,1,T10)8 2 12 10.(-,T9,1,T10)($,-，-，-)7 2 11 9.(-,j,1,T9)($,-，-，-)6 5#8.(,a,T7,T8)($,-，-，-)3 4 10 7.(*,T6,10,T7)($,-，-，-)1 2

21、9 6.(-,i,1,T6)(,T3,T4,T5)#8#5.(,T3,T4,T5)第44页，本讲稿共59页11.5 11.5 不变表达式外提不变表达式外提 如果一个表达式E在一个循环中不改变值，则称它为该循环的不变表达式.不变表达式外提的意思是把循环中的不变表达式提到循环外边去。例：设有 i:=1;WHILE i=1000 DO Ai:=X*Y则从编译程序角度看它就等价于 第45页，本讲稿共59页 由于X*Y在循环体中始终不改变值，它是循环中的不变表达式。把它提到外边得:i:=1;T:=X*Y;WHILE i=1000 DO Ai:=T例：设有 j:=1;WHILE j=1000 DO Aij

22、:=0则从编译程序角度看它就等价于 第46页，本讲稿共59页 j:=1;WHILE j=1000 DO BEGIN T1:=i-1;T2:=T1*10;T3:=AT2;T4:=j-1;T5:=T3T4;T5:=0 END 把循环的不变表达式提到循环外边，则得到如下的程序段：第47页，本讲稿共59页 j:=1;T1:=i-1;T2:=T1*10 T3:=AT2 WHILE j=1000 DO BEGIN T4=j-1;T5:=T3T4;T5:=0 END 外提优化通常只考虑加、减、乘等算法以及关系运算和逻辑运算等，称它们为可外提运算。一般不考虑除法运算。第48页，本讲稿共59页变量也可分为可外提

23、量与不可外提量。T:=a/Y;WHILE B DO IF Y=0 THEN X:=Y ELSE X:=a/YWHILE B DO IF Y=0 THEN X:=Y ELSE X:=T 第49页，本讲稿共59页 为了识别哪些变量是循环不变量,对每个循环构造一个变量定义表VDL。该表记录循环中被定义的变量。外提时首先把被提的四元式提到外提区YTL中,最后再把它插到四元式区中。当进行循环上的优化时，基本块上的优化已结束。第50页，本讲稿共59页 外提算法:1.求本层QT和VDL区的始地址.2.若当前QTi是不可外提类,则转向5.3.若QTi的OPR1或OPR2VDL.则转向5.4.（QTi可外提时）

24、a)把QTi提到外提表YTL中.b)把QTi.RESU从本层VDL提到外层VDL c)删除四元式QTi.5.准备读下一四元式,若未读完则转向2.6.把外提表的内容插入到表的相应位置中.第51页，本讲稿共59页VDL表的设计形式:t NAME VDLd:其中t取0或1。1表示该变量已经被外提。开始时t取0，每当相应变量被外提时把t的位置置成1。在查VDL表时只查t=0的元素。第52页，本讲稿共59页例：设有循环语句 i:=1;WHILE i 100 DO BEGIN Z:=i*K*5;A:=2*K+2*K*2;i:=i+1 END 则当扫描完循环部分时生成的四元式和VDL表如下图所示。第53页，

25、本讲稿共59页 i:=1;WHILE:T1:=i100;TEST:T1?DO:T2:=i*K;Z:=T2*5;T3:=2*K;T4:=T3*2;T5:=T3+T4;A:=T5;i:=i+1WHENDi 0A 0T5 0T4 0T3 0Z 0T2 0T1 0外层 NAME tVDL表 第54页，本讲稿共59页现在要回头扫描本层四元式并进行外提。i:=1;T3:=2*K;T4:=T3*2;T5:=T3+T4;WHILE:T1:=i=100;TEST:T1?DO:T2:=i*K;Z:=T2*5;A:=T5;i:=i+1WHENDi 0A 0T5 1T4 1T3 1Z 0T2 0T1 0外层 NAME

26、 tDVL表 第55页，本讲稿共59页11.6 11.6 消减运算强度消减运算强度消减运算强度是把强度大的运算换成强度小的运算。主要的研究对象是形如i*K或K*i的运算，其中K是循环不变量，i是循环变量。循环变量的特点是,每重复一次循环体,其值增加一个常数值.设a是i的出始值,b是i的增量,则i和i*K的取值过程是:a,a+b,a+2b,a*K,a*K+b*K,a*K+2(b*K),即开始取a*K,以后每次增加b*K。第56页，本讲稿共59页例如有下列语句：for i:=E1 step E2 until E3 do S可不妨假设E1,E2和E3的值大于0。它的语义解释如下：INIT i:=E1

27、;b:=E2;TEST:i=E3?DO:S (D:=i*K)INCR:i:=i+b;GOTO TEST第57页，本讲稿共59页设S为D:=i*K，则显然K是上述循环的不变量，i是循环变量，则有：INIT i:=E1 T1:=i*K T2:=E2*K TEST:i=E3?DO:D:=T1 INCR:T1:=T1+T2 i:=i+T2 GOTO TEST 虽然增加了运算,但是减少了运算强度。第58页，本讲稿共59页消减运算强度算法：1.如果QTk不是T:=i*K或T:=K*i的四元式。则转出口。其中i是本层循环变量，K是本层循环不变量。2.在INIT块中插入四元式：T:=A*K T:=B*K其中A是eres(E1)，B是eres(E2)，T是新的临时变量名。3.删除DO块中的当前四元式：T:=i*K4.在INCR中插入四元式：T:=T+T第59页，本讲稿共59页