编译原理优化

1、v代码优化指对代码进行等价变换代码优化指对代码进行等价变换, 使变换后的使变换后的代码具有更高的时间和空间效率。代码具有更高的时间和空间效率。v代码优化可在编译的不同阶段进行代码优化可在编译的不同阶段进行, 但最主要但最主要的优化在目标代码生成前进行的优化在目标代码生成前进行, 这类优化不依这类优化不依赖于具体计算机赖于具体计算机; 另一类优化在生成目标化码另一类优化在生成目标化码时进行时进行, 它依赖于具体计算机。它依赖于具体计算机。v根据优化对象涉及的程序范围根据优化对象涉及的程序范围, 优化可分为优化可分为: 局部优化、循环优化、全局优化。局部优化、循环优化、全局优化。局部优化局部优化v

2、局部优化指对代码的每个线性部分所进行的局部优化指对代码的每个线性部分所进行的优化。每个线性部分只有一个入口和一个出优化。每个线性部分只有一个入口和一个出口口, 称为基本块。称为基本块。v基本块基本块是程序中一段顺序执行的语句序列是程序中一段顺序执行的语句序列, 其其中只有一个入口和一个出口。基本块的执行中只有一个入口和一个出口。基本块的执行只能从入口进入、从出口退出。只能从入口进入、从出口退出。v一个给定的程序可划分为一系列基本块一个给定的程序可划分为一系列基本块,在基在基本块范围内进行的优化称为本块范围内进行的优化称为局部优化局部优化。基本块的划分方法基本块的划分方法关键是确定入口语句和出口

3、语句。关键是确定入口语句和出口语句。 (1) 满足下述条件的语句为满足下述条件的语句为入口语句入口语句: 三地址代码序列的第一个语句三地址代码序列的第一个语句; 由转移语句转移到的语句由转移语句转移到的语句; 紧跟在转移语句后面的语句。紧跟在转移语句后面的语句。 (2) 满足下述条件的语句为满足下述条件的语句为出口语句出口语句: 入口语句的前导语句入口语句的前导语句; 转移语句自身转移语句自身; 停语句停语句考虑求最大公因子的三地址代码程序考虑求最大公因子的三地址代码程序:(1) read X(2) read Y(3) R=X % Y(4) if R= 0 goto(8)(5) X=Y(6)

4、Y=R(7) goto(3)(8) write Y(9) halt基本块分别为基本块分别为: (1)(2), (3)(4), (5)(6)(7), (8)(9)基本块的基本块的DAG表示表示vDAG(Directed Acyclic Graph)主要用于对基本块主要用于对基本块进行优化。它是一种结点带有下述标记或附加信息进行优化。它是一种结点带有下述标记或附加信息的有向图的有向图(树树): (1)叶结点叶结点以标识符以标识符(变量名变量名)或常数作为标记或常数作为标记, 表示表示该变量或常数的该变量或常数的值值。若叶结点表示一变量。若叶结点表示一变量A的地址的地址, 则用则用addr(A)作为

5、标记。作为标记。(2)内部结点内部结点以运算符作为标记以运算符作为标记, 表示用该运算符表示用该运算符对其直接后继结点进行运算的结果。对其直接后继结点进行运算的结果。(3)各个各个结点可附加一个或多个标识符结点可附加一个或多个标识符, 表示这些表示这些变量具有该结点代表的值。变量具有该结点代表的值。通常把叶结点上的标识符加下标通常把叶结点上的标识符加下标0 (初值初值)不同的三地址代码与其对应的不同的三地址代码与其对应的DAG结点形式结点形式(1)A=B(2)A=op B(3)A=B op C(4)A=BC(5)if B rop C goto (S)(6)goto (S)(7)DC=B 上图中

6、上图中, 各结点圆圈中的各结点圆圈中的ni是构造是构造DAG过程中各结点的编号过程中各结点的编号, 各结点下面的符号各结点下面的符号(运运算符、标识符或常数算符、标识符或常数)是各结点的标记是各结点的标记,各结各结点右边的标识符点右边的标识符是结点的附加标识符。是结点的附加标识符。 注意注意: 转移语句结点的右边可附加一语转移语句结点的右边可附加一语句位置用于指示转移目标句位置用于指示转移目标, 其余结点的右边其余结点的右边只允许附加标识符只允许附加标识符; 数组元素赋值的结点有数组元素赋值的结点有三个后继三个后继, 其余结点最多只有两个后继。其余结点最多只有两个后继。利用利用DAG进行基本块

7、优化的基本思想进行基本块优化的基本思想 首先按基本块内三地址代码序列顺序把首先按基本块内三地址代码序列顺序把所有的三地址代码构造成一个所有的三地址代码构造成一个DAG, 然后按然后按构造结点的次序将构造结点的次序将DAG还原成三地址代码序还原成三地址代码序列。列。 由于在构造由于在构造DAG的同时作了局部优化的同时作了局部优化(合合并已知量、删除公共子表达式、删除无用赋并已知量、删除公共子表达式、删除无用赋值值), 故所得到的是优化的三地址代码序列。故所得到的是优化的三地址代码序列。 为了便于叙述为了便于叙述DAG构造算法构造算法, 把三地址代把三地址代码按其对应结点的后继结点个数分为四类码按

8、其对应结点的后继结点个数分为四类:(1) 0型型三地址代码三地址代码: 后继结点个数为后继结点个数为0(2) 1型型三地址代码三地址代码: 有一个后继结点有一个后继结点(3) 2型型三地址代码三地址代码: 有两个后继结点有两个后继结点(4) 3型型三地址代码三地址代码: 有三个后继结点有三个后继结点约定约定: 用大写字母表示三地址代码中的变用大写字母表示三地址代码中的变量名量名(或常数或常数); 用用Node(A)表示表示A在在DAG中的相中的相应结点。应结点。DAG构造算法的基本步骤构造算法的基本步骤(1) 构造叶结点构造叶结点(2) 合并已知量合并已知量(3) 构造构造op结点结点(删除公

9、共子表达式删除公共子表达式)(4) 添加附加信息添加附加信息(删除无用赋值删除无用赋值)基本块的基本块的DAG构造算法构造算法仅含仅含0,1,2型代码型代码: A=B, A= op B, A=B op C(1) 构造叶结点构造叶结点 若若Node(B)无定义无定义, 则则构造一标记为构造一标记为B的叶结的叶结点点, 并按下列情况做不同处理并按下列情况做不同处理: 若当前三地址代码是若当前三地址代码是0型型, 转转(4); 若当前三地址代码是若当前三地址代码是1型型, 转转(2); 若当前三地址代码是若当前三地址代码是2型型, 则则 若若Node(C)无定义无定义, 则构造一标记为则构造一标记为

10、C的叶的叶结点结点; 转转(2);(2)合并已知量合并已知量若若Node(B)为为常数常数, 转转(2), 否则转否则转(3);若若Node(B)和和Node(C)都为都为常数常数, 转转(2),否则转否则转(3);执行执行op B, 令新得常数为令新得常数为P。若。若Node(B)是处理当前是处理当前三地址代码时新建结点三地址代码时新建结点, 则删除它。则删除它。 若若Node(P)无定义无定义, 则构造一标记为则构造一标记为P的叶结点的叶结点; 转转(4);执行执行B op C, 令新得常数为令新得常数为P。若。若Node(B)或或Node(C)是处理当前三地址代码时新建结点是处理当前三地

11、址代码时新建结点,则删除则删除它。若它。若Node(P)无定义无定义, 则构造一标记为则构造一标记为P的叶结点的叶结点; 转转(4);(3)构造构造op结点结点构造构造A=op B对应的对应的op结点结点: 检查检查DAG中是中是否有标记为否有标记为op且以且以Node(B)为唯一后继的结为唯一后继的结点点(查找公共子表达式查找公共子表达式): 若没有若没有, 则构造一个则构造一个op结点结点; 转转(4);构造构造A=B op C对应的对应的op结点结点: 检查检查DAG中中是否有标记为是否有标记为op且其左后继为且其左后继为Node(B)、右、右后继为后继为Node(C)的结点的结点(查找

12、公共子表达式查找公共子表达式): 若没有若没有, 则构造一个则构造一个op结点结点; 转转(4);(4)添加附加信息添加附加信息 若若Node(A)无定义无定义, 则把则把A附加到相应结点附加到相应结点; 若若Node(A)有定义有定义, 则先从则先从Node(A)的附加标的附加标识符集中把识符集中把A删去删去, 再把再把A附加到相应结点上。附加到相应结点上。(若若Node(A)是叶结点是叶结点, 则不删则不删)例例:试构造以下基本块的试构造以下基本块的DAG:(1) T0 = 3.14(2) T1 = 2*T0(3) T2 = R+r(4) A = T1*T2(5) B = A(6) T3

13、= 2*T0(7) T4 = R+r(8) T5 = T3*T4(9) T6 = R-r(10) B = T5*T6解解: 按算法顺序处理每个三地址代码后构造按算法顺序处理每个三地址代码后构造出的出的DAG如图所示如图所示:A=B(1)T0 = 3.14A=B op C(2)T1 = 2*T0对于对于T1=2*T0, 先执行步骤先执行步骤( 1 ) : 因因Node(B)无定义无定义, 故构造一标记为故构造一标记为2的叶结点的叶结点;因当前三地因当前三地址代码是址代码是2型且型且Node(C)已有定义已有定义, 转步骤转步骤(2): 因因Node(B)和和Node(C)都为常数都为常数,执行执

14、行B op C 并构造新结点并构造新结点P(=6.28); 因因Node(B)是处理当前是处理当前四元式时新建结点四元式时新建结点, 故删除故删除n2。然后然后, 执行步骤执行步骤(4), 因因Node(A)无定义而将无定义而将T1附加在结点附加在结点n3上上; 因结点因结点n2被删而将被删而将n3改名改名为为n2。上述过程实际是。上述过程实际是合并已知量合并已知量。A=B op C(3)T2 = R+r(4)A = T1*T2(5)B = A (6) T3= 2*T0处理过程与处理过程与T1=2*T0类似类似, 但生成但生成P时因其已在时因其已在DAG中中, 故不生成新结点而直接将故不生成新

15、结点而直接将T3附加到结点附加到结点6.28上。上。 (7) T4= R+r该过程实质上是该过程实质上是删除公共子表达式删除公共子表达式。因。因DAG中中已有叶结点已有叶结点R与与r, 且执行且执行op后新得结点已在后新得结点已在DAG中中, 故执行步骤故执行步骤(4)时只需把时只需把T4附加到结点附加到结点n5上。上。(8) T5= T3*T4 (9) T6= R-r变量变量R和和r已在已在DAG中中, 执行执行操作后操作后, 新结点新结点P无无定义定义, 故生成一个新结点故生成一个新结点n7 并把并把T6 附加到附加到n7上。上。 (10) B=T5*T6 DAG中已有中已有T5和和T6,

16、执行步骤执行步骤(4)时时, 因结点因结点B已已定义且不是叶结点定义且不是叶结点, 故先将原故先将原B从从DAG中删除中删除,再生成再生成新结点新结点n8,并把并把B附加到附加到n8上。该过程实质上是上。该过程实质上是删除删除无用赋值无用赋值B=A。利用利用DAG进行基本块的优化进行基本块的优化基本思想基本思想: 按构造按构造DAG结点的顺序结点的顺序, 对每个结点分别写出对每个结点分别写出其相应的三地址代码。其相应的三地址代码。以例以例5.1为例为例, 其三地址代码序列其三地址代码序列G如下如下:(1) T0=3.14(2) T1=6.28(3) T3=6.28(4) T2=R+r(5) T

17、4=T2(6) A=6.28*T2(7) T5=A(8) T6= Rr(9) B=A*T6优化后：优化后：(1) T0=3.14(2) T1=6.28(3) T3=6.28(4) T2=R+r(5) T4=T2(6) A=6.28*T2(7) T5=A(8) T6= Rr(9) B=A*T6优化前：优化前：(1) T0 = 3.14(2) T1 = 2*T0(3) T2 = R+r(4) A = T1*T2(5) B = A(6) T3 = 2*T0(7) T4 = R+r(8) T5 = T3*T4(9) T6 = R-r(10) B = T5*T6将将G和原基本块和原基本块G相比相比, 可看出可看出:(1)G中代码中代码(2)和和(6)是是已知量运算已知量运算,G已合并已合并;(2)G中代码中代码(5)是是无用赋值无用赋值, G已把它删除已把它删除;(3)G中代码中代码(3)和和(7)的的R+r是是公共子表达式公共子表达式, G只对它计算了一次。只对它计算了一次。因此因此, G是对是对