1、编译原理第十章第十章 优化优化第十章第十章 优化优化n优化概述优化概述n局部优化局部优化n循环优化循环优化第十章第十章 优化优化n优化优化：对程序进行各种：对程序进行各种等价等价变换，使得从变换，使得从变换后的程序出发，能生成更变换后的程序出发，能生成更有效有效的目标的目标代码。代码。等价等价：指不改变程序的运行结果。：指不改变程序的运行结果。有效有效：指目标代码：指目标代码运行时间短运行时间短，占用的，占用的存储空存储空间小间小。10.1 10.1 概述概述n优化的目的优化的目的p产生更高效的代码。产生更高效的代码。n优化必须遵循一定的优化必须遵循一定的原则原则：等价等价原则：经过优化后不应
2、改变程序运行的原则：经过优化后不应改变程序运行的结果；结果；有效有效原则：使优化后所产生的目标代码运行原则：使优化后所产生的目标代码运行时间较短，占用的存储空间较小；时间较短，占用的存储空间较小；合算合算原则：应尽可能以较低的代价取得较好原则：应尽可能以较低的代价取得较好的优化效果。的优化效果。10.1 10.1 概述概述n优化的三个不同级别：优化的三个不同级别：局部优化局部优化循环优化循环优化全局优化全局优化n优化的种类：优化的种类：删除多余运算删除多余运算( (或称删除公用子表达式或称删除公用子表达式) )代码外提代码外提强度消弱强度消弱变换循环控制条件变换循环控制条件合并已知量合并已知量
3、复写传播复写传播删除无用赋值删除无用赋值void quicksort (m, n);int m, n;int i, j;int v, x;if (n=m) return;/* fragment begins here*/i=m-1; j=n; v=a n;while (1) do i=i+1; while (a iv);if (i=j) break;x=a i; ai=a j; aj=x; x=ai; ai=a n; a n=x; /*fragment ends here*/ quicksort (m, j); quicksort (i+1, n);q中间代码程序段中间代码程序段 i:=m-1
4、j:=nT1:=4*nv:=aT1B1i:=i+1T2:=4*i T3:=aT2if T3v goto B3B3if i=j goto B6B4T6:=4*ix:=a T6T7:=4*iT8:=4*jT9:=a T8a T7=T9T10:= 4*j a T10=xgoto B2B5T11:=4*ix:=a T11T12:=4*iT13:=4*nT14:=a T13a T12=T14T15:= 4*na T15=xB6q中间代码程序段中间代码程序段 i:=m-1j:=nT1:=4*nv:=aT1B1i:=i+1T2:=4*i T3:=aT2if T3v goto B3B3if i=j goto
5、B6B4T6:=4*ix:=a T6T7:=4*iT8:=4*jT9:=a T8a T7=T9T10:= 4*j a T10=xgoto B2B5T11:=4*ix:=a T11T12:=4*iT13:=4*nT14:=a T13a T12=T14T15:= 4*na T15=xB6q公共子表达式公共子表达式i:=m-1j:=nT1:=4*nv:=aT1B1i:=i+1T2:=4*i T3:=aT2if T3v goto B3B3if i=j goto B6B4T6:=4*ix:=a T6T7:=4*iT8:=4*jT9:=a T8a T7=T9T10:= 4*j a T10=xgoto B2
6、B5T11:=4*ix:=a T11T12:=4*iT13:=4*nT14:=a T13a T12=T14T15:= 4*na T15=xB6如果一个表达式如果一个表达式E在前面已经计算过，且在这之后在前面已经计算过，且在这之后E中变量的值没有改变，中变量的值没有改变，则称则称E为公共子表达式为公共子表达式q删除公用子表达式后删除公用子表达式后i:=m-1j:=nT1:=4*nv:=aT1B1i:=i+1T2:=4*i T3:=aT2if T3v goto B3B3if i=j goto B6B4T6:=4*ix:=a T6T7:=4*iT8:=4*jT9:=a T8a T7=T9T10:=
7、4*j a T10=xgoto B2B5T11:=4*ix:=a T11T12:=4*iT13:= T1T14:=a T13a T12=T14T15:= T13a T15=xB6i:=m-1j:=nT1:=4*nv:=aT1B1i:=i+1T2:=4*i T3:=aT2if T3v goto B3B3if i=j goto B6B4T6:=4*ix:=a T6T7:=4*iT8:=4*jT9:=a T8a T7=T9T10:= 4*j a T10=xgoto B2B5T11:=4*ix:=a T11T12:=4*iT13:= T1T14:=a T13a T12=T14T15:= T13a T1
8、5=xB6q公共子表达式公共子表达式q删除公用子表达式后删除公用子表达式后i:=m-1j:=nT1:=4*nv:=aT1B1i:=i+1T2:=4*i T3:=aT2if T3v goto B3B3if i=j goto B6B4T6:= T2x:=a T6T7:= T6T8:=4*jT9:=a T8a T7=T9T10:= 4*j a T10=xgoto B2B5T11:= T2x:=a T11T12:= T11T13:= T1T14:=a T13a T12=T14T15:= T13a T15=xB6i:=m-1j:=nT1:=4*nv:=aT1B1i:=i+1T2:=4*i T3:=aT2
9、if T3v goto B3B3if i=j goto B6B4T6:= T2x:=a T6T7:= T6T8:=4*jT9:=a T8a T7=T9T10:= 4*j a T10=xgoto B2B5T11:= T2x:=a T11T12:= T11T13:= T1T14:=a T13a T12=T14T15:= T13a T15=xB6q公共子表达式公共子表达式q删除公用子表达式后删除公用子表达式后i:=m-1j:=nT1:=4*nv:=aT1B1i:=i+1T2:=4*i T3:=aT2if T3v goto B3B3if i=j goto B6B4T6:= T2x:=a T6T7:=
10、T6T8:= T4T9:=a T8a T7=T9T10:= T8a T10=xgoto B2B5T11:= T2x:=a T11T12:= T11T13:= T1T14:=a T13a T12=T14T15:= T13a T15=xB6q复写传播复写传播i:=m-1j:=nT1:=4*nv:=aT1B1i:=i+1T2:=4*i T3:=aT2if T3v goto B3B3if i=j goto B6B4T6:= T2x:=a T6T7:= T6T8:= T4T9:=a T8a T7=T9T10:= T8a T10=xgoto B2B5T11:= T2x:=a T11T12:= T11T13
11、:= T1T14:=a T13a T12=T14T15:= T13a T15=xB6B5中，中，T6:= T2和和x:=a T6中间中间T6的值没变过，可把的值没变过，可把x:=a T6改写成改写成x:=a T2，这种变换称为复写传播。这种变换称为复写传播。q复写传播复写传播i:=m-1j:=nT1:=4*nv:=aT1B1i:=i+1T2:=4*i T3:=aT2if T3v goto B3B3if i=j goto B6B4T6:= T2x:=a T2T7:= T2T8:= T4T9:=a T8a T2=T9T10:= T8a T10=xgoto B2B5T11:= T2x:=a T11T
12、12:= T11T13:= T1T14:=a T13a T12=T14T15:= T13a T15=xB6q复写传播复写传播i:=m-1j:=nT1:=4*nv:=aT1B1i:=i+1T2:=4*i T3:=aT2if T3v goto B3B3if i=j goto B6B4T6:= T2x:=a T2T7:= T2T8:= T4T9:=a T8a T2=T9T10:= T8a T10=xgoto B2B5T11:= T2x:=a T11T12:= T11T13:= T1T14:=a T13a T12=T14T15:= T13a T15=xB6q复写传播复写传播i:=m-1j:=nT1:=
13、4*nv:=aT1B1i:=i+1T2:=4*i T3:=aT2if T3v goto B3B3if i=j goto B6B4T6:= T2x:=a T2T7:= T2T8:= T4T9:=a T8a T2=T9T10:= T8a T10=xgoto B2B5T11:= T2x:=a T2T12:= T2T13:= T1T14:=a T13a T2=T14T15:= T13a T15=xB6q复写传播复写传播i:=m-1j:=nT1:=4*nv:=aT1B1i:=i+1T2:=4*i T3:=aT2if T3v goto B3B3if i=j goto B6B4T6:= T2x:=a T2T
14、7:= T2T8:= T4T9:=a T8a T2=T9T10:= T8a T10=xgoto B2B5T11:= T2x:=a T2T12:= T2T13:= T1T14:=a T13a T2=T14T15:= T13a T15=xB6q复写传播复写传播i:=m-1j:=nT1:=4*nv:=aT1B1i:=i+1T2:=4*i T3:=aT2if T3v goto B3B3if i=j goto B6B4T6:= T2x:=a T2T7:= T2T8:= T4T9:=a T4a T2=T9T10:= T4a T4=xgoto B2B5T11:= T2x:=a T2T12:= T2T13:=
15、 T1T14:=a T13a T2=T14T15:= T13a T15=xB6q复写传播复写传播i:=m-1j:=nT1:=4*nv:=aT1B1i:=i+1T2:=4*i T3:=aT2if T3v goto B3B3if i=j goto B6B4T6:= T2x:=a T2T7:= T2T8:= T4T9:=a T4a T2=T9T10:= T4a T4=xgoto B2B5T11:= T2x:=a T2T12:= T2T13:= T1T14:=a T13a T2=T14T15:= T13a T15=xB6q复写传播复写传播i:=m-1j:=nT1:=4*nv:=aT1B1i:=i+1T
16、2:=4*i T3:=aT2if T3v goto B3B3if i=j goto B6B4T6:= T2x:=aT2T7:= T2T8:= T4T9:=a T4a T2=T9T10:= T4a T4=xgoto B2B5T11:= T2x:=a T2T12:= T2T13:= T1T14:=a T1a T2=T14T15:= T1a T1=xB6q复写传播复写传播i:=m-1j:=nT1:=4*nv:=aT1B1i:=i+1T2:=4*i T3:=aT2if T3v goto B3B3if i=j goto B6B4T6:= T2x:=aT2T7:= T2T8:= T4T9:=a T4a T
17、2=T9T10:= T4a T4=xgoto B2B5T11:= T2x:=a T2T12:= T2T13:= T1T14:=a T1a T2=T14T15:= T1a T1=xB6q复写传播复写传播i:=m-1j:=nT1:=4*nv:=aT1B1i:=i+1T2:=4*i T3:=aT2if T3v goto B3B3if i=j goto B6B4T6:= T2x:=aT2T7:= T2T8:= T4T9:=a T4a T2=T9T10:= T4a T4=xgoto B2B5T11:= T2x:=a T2T12:= T2T13:= T1T14:=va T2=vT15:= T1a T1=x
18、B6q复写传播复写传播i:=m-1j:=nT1:=4*nv:=aT1B1i:=i+1T2:=4*i T3:=aT2if T3v goto B3B3if i=j goto B6B4T6:= T2x:=aT2T7:= T2T8:= T4T9:=a T4a T2=T9T10:= T4a T4=xgoto B2B5T11:= T2x:=a T2T12:= T2T13:= T1T14:=va T2=vT15:= T1a T1=xB6q复写传播复写传播i:=m-1j:=nT1:=4*nv:=aT1B1i:=i+1T2:=4*i T3:=aT2if T3v goto B3B3if i=j goto B6B4
19、T6:= T2x:= T3T7:= T2T8:= T4T9:=a T4a T2=T9T10:= T4a T4= T3goto B2B5T11:= T2x:= T3T12:= T2T13:= T1T14:=va T2=vT15:= T1a T1= T3B6q复写传播复写传播i:=m-1j:=nT1:=4*nv:=aT1B1i:=i+1T2:=4*i T3:=aT2if T3v goto B3B3if i=j goto B6B4T6:= T2x:= T3T7:= T2T8:= T4T9:=a T4a T2=T9T10:= T4a T4= T3goto B2B5T11:= T2x:= T3T12:=
20、 T2T13:= T1T14:=va T2=vT15:= T1a T1= T3B6q复写传播复写传播i:=m-1j:=nT1:=4*nv:=aT1B1i:=i+1T2:=4*i T3:=aT2if T3v goto B3B3if i=j goto B6B4T6:= T2x:= T3T7:= T2T8:= T4T9:= T5a T2= T5T10:= T4a T4= T3goto B2B5T11:= T2x:= T3T12:= T2T13:= T1T14:=va T2=vT15:= T1a T1= T3B6q删除无用赋值删除无用赋值i:=m-1j:=nT1:=4*nv:=aT1B1i:=i+1T
21、2:=4*i T3:=aT2if T3v goto B3B3if i=j goto B6B4T6:= T2x:=T3T7:= T2T8:= T4T9:=T5a T2=T5T10:= T4a T4= T3goto B2B5T11:= T2x:=T3T12:= T2T13:= T1T14:= va T2=vT15:= T1a T1= T3B6q删除无用赋值后删除无用赋值后 i:=m-1j:=nT1:=4*nv:=aT1B1i:=i+1T2:=4*i T3:=aT2if T3v goto B3B3if i=j goto B6B4a T2=T5a T4= T3goto B2B5a T2=va T1=T
22、3B6q强度削弱强度削弱 i:=m-1j:=nT1:=4*nv:=aT1B1i:=i+1T2:=4*i T3:=aT2if T3v goto B3B3if i=j goto B6B4a T2=T5a T4= T3goto B2B5a T2=va T1=T3B6q强度削弱后强度削弱后 i:=m-1j:=nT1:=4*nv:=aT1T2:=4*iT4:=4*jB1i:=i+1T2:= T2+4 T3:=aT2if T3v goto B3B3if i=j goto B6B4a T2=T5a T4= T3goto B2B5a T2=va T1=T3B6q删除归纳变量删除归纳变量i:=m-1j:=nT1
23、:=4*nv:=aT1T2:=4*iT4:=4*jB1i:=i+1T2:= T2+4 T3:=aT2if T3v goto B3B3if i=j goto B6B4a T2=T5a T4= T3goto B2B5a T2=va T1=T3B6q删除归纳变量后删除归纳变量后i:=m-1j:=nT1:=4*nv:=aT1T2:=4*iT4:=4*jB1T2:= T2+4 T3:=aT2if T3v goto B3B3if T2=T4 goto B6B4a T2=T5a T4= T3goto B2B5a T2=va T1=T3B6q中间代码程序段中间代码程序段（优化前）（优化前） i:=m-1j:=
24、nT1:=4*nv:=aT1B1i:=i+1T2:=4*i T3:=aT2if T3v goto B3B3if i=j goto B6B4T6:=4*ix:=a T6T7:=4*iT8:=4*jT9:=a T8a T7=T9T10:= 4*j a T10=xgoto B2B5T11:=4*ix:=a T11T12:=4*iT13:=4*nT14:=a T13a T12=T14T15:= 4*na T15=xB6q中间代码程序段中间代码程序段（优化后）（优化后）i:=m-1j:=nT1:=4*nv:=aT1T2:=4*iT4:=4*jB1T2:= T2+4 T3:=aT2if T3v goto
25、B3B3if T2=T4 goto B6B4a T2=T5a T4= T3goto B2B5a T2=va T1=T3B610.2 10.2 局部优化局部优化n基本块基本块：指程序中一顺序执行语句序列，其中：指程序中一顺序执行语句序列，其中只有一个入口和一个出口。入口就是其中第一只有一个入口和一个出口。入口就是其中第一个语句，出口就是其中最后一个语句。个语句，出口就是其中最后一个语句。 例例:基本块基本块T1:=a*a T2:=a*b T3:=2*T2 T4:=T1+T2 T5:=b*b T6:=T4+T5q如果一条三地址语句为如果一条三地址语句为x:=y+z，则称对则称对x定值定值并并引用引
26、用y和和z。q在一个基本块中的一个在一个基本块中的一个名字名字，所谓在程序中的某个给定点是所谓在程序中的某个给定点是活跃的活跃的，是指如果在程序中，是指如果在程序中(包包括在本基本块或在其它基本块括在本基本块或在其它基本块中中)它的值它的值在该点以后被引用在该点以后被引用。10.2 10.2 局部优化局部优化n局限于基本块范围内的优化称为局限于基本块范围内的优化称为基本块内的基本块内的优化优化，或称，或称局部优化局部优化。n对一个给定的程序，我们可以把它划分成一对一个给定的程序，我们可以把它划分成一系列的基本块。在各个基本块范围内，分别系列的基本块。在各个基本块范围内，分别进行优化。进行优化。
27、n如何将四元式划分成基本块？如何将四元式划分成基本块？n划分四元式程序为基本块的算法划分四元式程序为基本块的算法: :1.1.求出四元式程序中各个基本块的入口语句求出四元式程序中各个基本块的入口语句: :1) 1) 程序第一个语句程序第一个语句，或，或2) 2) 能由条件转移语句或无条件转移语句转移到能由条件转移语句或无条件转移语句转移到的语句的语句，或，或3) 3) 紧跟在条件转移语句后面的语句紧跟在条件转移语句后面的语句。n划分四元式程序为基本块的算法划分四元式程序为基本块的算法: :2. 2. 对以上求出的每个入口语句，确定其所属对以上求出的每个入口语句，确定其所属的基本块。它是由该入口
28、语句到的基本块。它是由该入口语句到下一入口下一入口语句语句( (不包括该入口语句不包括该入口语句) ) 之间的语句序列之间的语句序列组成的。组成的。入口语句入口语句n入口语句入口语句mn划分四元式程序为基本块的算法划分四元式程序为基本块的算法: :2. 2. 对以上求出的每个入口语句，确定其所属对以上求出的每个入口语句，确定其所属的基本块。它是由该入口语句到的基本块。它是由该入口语句到下一入口下一入口语句语句( (不包括该入口语句不包括该入口语句) )、或到或到一转移语一转移语句句( (包括该转移语句包括该转移语句) ) 之间的语句序列组成之间的语句序列组成的。的。入口语句入口语句n入口语句入
29、口语句m入口语句入口语句n转移语句转移语句mn划分四元式程序为基本块的算法划分四元式程序为基本块的算法: :2. 2. 对以上求出的每个入口语句，确定其所属对以上求出的每个入口语句，确定其所属的基本块。它是由该入口语句到的基本块。它是由该入口语句到下一入口下一入口语句语句( (不包括该入口语句不包括该入口语句) )、或到、或到一转移语一转移语句句( (包括该转移语句包括该转移语句) ) 、或或一停语句一停语句( (包括包括该停语句该停语句) )之间的语句序列组成的。之间的语句序列组成的。入口语句入口语句n入口语句入口语句m入口语句入口语句n转移语句转移语句m入口语句入口语句n停语句停语句m3.
30、 3. 凡未被纳入某一基本块中的语句，可以从凡未被纳入某一基本块中的语句，可以从程序中删除。程序中删除。n例：划分基本块例：划分基本块(1)read X(2) read Y(3) R:=X mod Y(4) if R=0 goto (8)(5) X:=Y(6) Y:=R(7) goto (3)(8) write Y(9) halt1.求出四元式程序中各个基本块的入口求出四元式程序中各个基本块的入口语句语句:1) 程序第一个语句，或程序第一个语句，或2) 能由条件转移语句或无条件转移语能由条件转移语句或无条件转移语句转移到的语句，或句转移到的语句，或3) 紧跟在条件转移语句后面的语句。紧跟在条件
31、转移语句后面的语句。n例：划分基本块例：划分基本块(1)read X(2) read Y(3) R:=X mod Y(4) if R=0 goto (8)(5) X:=Y(6) Y:=R(7) goto (3)(8) write Y(9) halt1.求出四元式程序中各个基本块的入口语求出四元式程序中各个基本块的入口语句句:1) 程序第一个语句程序第一个语句，或，或2) 能由条件转移语句或无条件转移语能由条件转移语句或无条件转移语句转移到的语句，或句转移到的语句，或3) 紧跟在条件转移语句后面的语句。紧跟在条件转移语句后面的语句。n例：划分基本块例：划分基本块(1)read X(2) read
32、 Y(3) R:=X mod Y(4) if R=0 goto (8)(5) X:=Y(6) Y:=R(7) goto (3)(8) write Y(9) halt1.求出四元式程序中各个基本块的入口语求出四元式程序中各个基本块的入口语句句:1) 程序第一个语句，或程序第一个语句，或2) 能由条件转移语句或无条件转移语能由条件转移语句或无条件转移语句转移到的语句句转移到的语句，或，或3) 紧跟在条件转移语句后面的语句。紧跟在条件转移语句后面的语句。n例：划分基本块例：划分基本块(1)read X(2) read Y(3) R:=X mod Y(4) if R=0 goto (8)(5) X:=
33、Y(6) Y:=R(7) goto (3)(8) write Y(9) halt1.求出四元式程序中各个基本块的入口语求出四元式程序中各个基本块的入口语句句:1) 程序第一个语句，或程序第一个语句，或2) 能由条件转移语句或无条件转移语能由条件转移语句或无条件转移语句转移到的语句句转移到的语句，或，或3) 紧跟在条件转移语句后面的语句。紧跟在条件转移语句后面的语句。n例：划分基本块例：划分基本块(1)read X(2) read Y(3) R:=X mod Y(4) if R=0 goto (8)(5) X:=Y(6) Y:=R(7) goto (3)(8) write Y(9) halt1.
34、求出四元式程序中各个基本块的入口语求出四元式程序中各个基本块的入口语句句:1) 程序第一个语句，或程序第一个语句，或2) 能由条件转移语句或无条件转移语能由条件转移语句或无条件转移语句转移到的语句，或句转移到的语句，或3) 紧跟在条件转移语句后面的语句紧跟在条件转移语句后面的语句。n例：划分基本块例：划分基本块(1)read X(2) read Y(3) R:=X mod Y(4) if R=0 goto (8)(5) X:=Y(6) Y:=R(7) goto (3)(8) write Y(9) halt2. 对以上求出的对以上求出的每个入口语句，每个入口语句，确定其所属的基确定其所属的基本块
35、。它是由该本块。它是由该入口语句到入口语句到下一下一入口语句入口语句(不包括不包括该入口语句该入口语句)、或、或到到一转移语句一转移语句(包包括该转移语句括该转移语句)、或或一停语句一停语句(包括包括该停语句该停语句)之间的之间的语句序列组成的。语句序列组成的。流图流图n每个流图以基本块为每个流图以基本块为结点结点。如果一个结点的基。如果一个结点的基本块的入口语句是程序的第一条语句，则称此本块的入口语句是程序的第一条语句，则称此结点为结点为首结点首结点。如果在某个执行顺序中，基本。如果在某个执行顺序中，基本块块B2紧接在基本块紧接在基本块B1之后执行之后执行，则从，则从B1到到B2有一条有向边
36、。即，如果有一条有向边。即，如果有一个条件或无条件转移语句从有一个条件或无条件转移语句从B1的最后的最后一条语句转移到一条语句转移到B2的第一条语句；或者的第一条语句；或者在程序的序列中，在程序的序列中，B2紧接在紧接在B1的后面，并的后面，并且且B1的最后一条语句不是一个无条件转移的最后一条语句不是一个无条件转移语句。我们就说语句。我们就说B1是是B2的的前驱前驱，B2是是B1的的后继后继。(1)read X(2) read Y(3) R:=X mod Y(4) if R=0 goto (8)(5) X:=Y(6) Y:=R(7) goto (3)(8) write Y(9) halt(8)
37、 write Y(9) halt(5) X:=Y(6) Y:=R(7) goto (3)(3) R:=X mod Y(4) if R=0 goto (8)(1) read X(2) read YB1B2B3B410.210.2局部优化局部优化n局限于基本块范围内的优化称为局限于基本块范围内的优化称为基本块内的基本块内的优化优化，或称，或称局部优化局部优化。n在一个基本块内通常可以实行下面的优化在一个基本块内通常可以实行下面的优化: :删除公共子表达式删除公共子表达式删除无用赋值删除无用赋值合并已知量合并已知量临时变量改名临时变量改名交换语句的位置交换语句的位置代数变换代数变换优化措施优化措施n
38、合并已知量合并已知量 T T1 1:=2:=2 T T2 2:=4:=4* *T T1 1变换成变换成T T2 2:=8:=8n临时变量改名临时变量改名 T:=b+c其中其中T是一个临时变量名。把这个语句改成：是一个临时变量名。把这个语句改成： S:=b+c优化措施优化措施n交换语句的位置交换语句的位置 T1:=b+c T2:=x+y n代数变换代数变换 x:=x+0或或 x:=x*1 （可直接删掉）（可直接删掉） x:=y*2变换成变换成x:=y*y10.2.210.2.2 基本块的基本块的DAGDAG表示及其应用表示及其应用有向图有向图有向边有向边: ninj前驱：前驱：ni是是nj的前驱
39、的前驱后继：后继： nj是是ni的后继的后继通路通路: n1n2 , n2n3 ,. ,nk-1nk环路：环路： n1=nk DAG：无环路有向图无环路有向图(Directed Acyclic Graph)n1n2n3n4n1n2n3n47.1.2 图表示法图表示法n图表示法图表示法DAG抽象语法树抽象语法树 n无循环有向图无循环有向图(Directed Acyclic Graph，简称简称DAG)对表达式中的每个子表达式，对表达式中的每个子表达式，DAG中都有一个中都有一个结点结点一个内部结点代表一个操作符，它的孩子代表一个内部结点代表一个操作符，它的孩子代表操作数操作数在一个在一个DAG中
40、代表公共子表达式的结点具有多中代表公共子表达式的结点具有多个父结点个父结点 a:=b*(-c)+b*(-c)的图表示法 assigna+*buminuscDAGassigna+*buminusc抽象语法树抽象语法树*buminuscDAG对应的代码：对应的代码： T1:=-cT2:=b*T1T5:=T2+T2a:=T5assigna+*buminuscDAGn描述计算过程的描述计算过程的DAG是一种带有下述标记或附是一种带有下述标记或附加信息的加信息的DAG:n13.14n3n4Rrn5+T2, T4n图的图的叶结点叶结点以一以一标识符标识符或或常数常数作为标记，表示该作为标记，表示该结点代表
41、该变量或常数的值结点代表该变量或常数的值;n图的图的内部结点内部结点以一以一运算符运算符作为作为标记，表示该结点代表应用该标记，表示该结点代表应用该运算符对其后继结点所代表的运算符对其后继结点所代表的值进行运算的结果值进行运算的结果;n图中各个结点上可能图中各个结点上可能附加一个或多个标识附加一个或多个标识符符(称附加标识符称附加标识符)表表示这些变量具有该结示这些变量具有该结点所代表的值。点所代表的值。10.2.2 10.2.2 基本块的基本块的DAGDAG表示及应用表示及应用n一个基本块，可用一个一个基本块，可用一个DAG来表示来表示n与各四元式相对应的与各四元式相对应的DAG结点形式结点
42、形式: 四元式四元式 DAG 图图(0) 0型型: A:=B (:=，B，-，A) n1AB四元式四元式 DAG 图图(1) 1型型: A:=op B (op，B，-，A)n1ABn2op(2) 2型型: A:=B op C (op，B，C，A)n2ABn1opn3C四元式四元式 DAG 图图(3) 2型型: A:=BC (=，BC，-，A) n2ABn1=n3C(4) 2型型: if B rop C goto (s) (jrop，B，C，(s)n2(s)Bn1ropn3C四元式四元式 DAG 图图(5) 3型型: DC:=B (=，B，-，DC)(6) 0型型: goto (s) (j，-，
43、-，(s)(s)n1n2Bn1=n4Cn3Dn假设假设DAG各结点信息各结点信息将用某种适当的数将用某种适当的数据结构存放据结构存放(如链表如链表)。另设置一个标识符。另设置一个标识符与结点的对应函数与结点的对应函数:否则识符是其上的标记或附加标，如果存在一个结点 nullAnn)A(Noden0 0，1 1，2 2型四元式的基本块的型四元式的基本块的DAGDAG构造算法构造算法对基本块中每一四元式，依次执行以下步骤对基本块中每一四元式，依次执行以下步骤: :1. 1. 准备操作数的结点准备操作数的结点 2. 2. 合并已知量合并已知量3. 3. 删除公共子表达式删除公共子表达式4. 4. 删
44、除无用赋值删除无用赋值1.1.准备操作数的结点准备操作数的结点 n如果如果NODE(B)NODE(B)无定义，则构造一标记为无定义，则构造一标记为B B的叶的叶结点并定义结点并定义NODE(B)NODE(B)为这个结点为这个结点; ;如果当前四元式是如果当前四元式是0 0型，则记型，则记NODE(B)NODE(B)的值为的值为n n，转转4 4。如果当前四元式是如果当前四元式是1 1型，则转型，则转2(1)2(1)如果当前四元式是如果当前四元式是2 2型，则型，则( (i)i)如果如果NODE(C)NODE(C)无无定义，则构造一标记为定义，则构造一标记为C C的叶结点并定义的叶结点并定义NO
45、DE(C)NODE(C)为这个结点；为这个结点；( (ii)ii)转转2(2)2(2)。1. 1. 准备操作数的结点准备操作数的结点 2. 2. 合并已知量合并已知量3. 3. 删除公共子表达式删除公共子表达式4. 4. 删除无用赋值删除无用赋值 A:=op B A:=B op C A:= B2.2.合并已知量合并已知量(1) (1) 如果如果NODE(B)NODE(B)是标记为常数的叶结点，则转是标记为常数的叶结点，则转2(3)2(3)；否则，转否则，转3(1)3(1)。(2) (2) 如果如果NODE(B)NODE(B)和和NODE(C)NODE(C)都是标记为常数的叶结点，都是标记为常数
46、的叶结点，则转则转2(4)2(4)；否则，转；否则，转3(2)3(2)。(3) (3) 执行执行op B (op B (即合并已知量即合并已知量) )。令得到的新常数为。令得到的新常数为P P。如果如果NODE(B)NODE(B)是处理当前四元式时新构造出来的是处理当前四元式时新构造出来的结点，则删除它。如果结点，则删除它。如果NODE(P)NODE(P)无定义，则构造无定义，则构造一用一用P P作标记的叶结点作标记的叶结点n n。置置NODE(P)=nNODE(P)=n，转转4 4。(4)(4)执行执行B op C (B op C (即合并已知量即合并已知量) )。令得到的新常数为。令得到的
47、新常数为P P。如果如果NODE(B)NODE(B)或或NODE(C)NODE(C)是处理当前四元式时是处理当前四元式时新构造出来的结点，则删除它。如果新构造出来的结点，则删除它。如果NODE(P)NODE(P)无无定义，则构造一用定义，则构造一用P P作标记的叶结点作标记的叶结点n n。置置NODE(P)=nNODE(P)=n，转转4 4。1. 1. 准备操作数的结点准备操作数的结点 2. 2. 合并已知量合并已知量3. 3. 删除公共子表达式删除公共子表达式4. 4. 删除无用赋值删除无用赋值 A:=op B A:=B op C 3. 3. 寻找公共子表达式寻找公共子表达式(1) (1)
48、检查检查DAGDAG中是否已有一结点，其唯一后继为中是否已有一结点，其唯一后继为NODE(B)NODE(B)且标记为且标记为op(op(即公共子表达式即公共子表达式) )。如。如果没有，则构造该结点果没有，则构造该结点n n，否则，把已有的否则，把已有的结点作为它的结点并设该结点为结点作为它的结点并设该结点为n n。转转4 4。(2) (2) 检查检查DAGDAG中是否已有一结点，其左后继为中是否已有一结点，其左后继为NODE(B)NODE(B)，右后继为右后继为NODE(C)NODE(C)，且标记为且标记为op(op(即公共子表达式即公共子表达式) )。如果没有，则构造。如果没有，则构造该结
49、点该结点n n，否则，把已有的结点作为它的结否则，把已有的结点作为它的结点并设该结点为点并设该结点为n n。转转4 4。1. 1. 准备操作数的结点准备操作数的结点 2. 2. 合并已知量合并已知量3. 3. 删除公共子表达式删除公共子表达式4. 4. 删除无用赋值删除无用赋值 A:=B op C A:=B op C 4. 4. 删除无用赋值删除无用赋值 如果如果NODE(A)NODE(A)无定义，则把无定义，则把A A附加在结点附加在结点n n上并令上并令NODE(A)=n;NODE(A)=n;否则，先把否则，先把A A从从NODE(A)NODE(A)结点上的附加标识符集中删除结点上的附加标
50、识符集中删除( (注意，如果注意，如果NODE(A)NODE(A)是叶结点，则其是叶结点，则其A A标记不删除标记不删除) )。把。把A A附加到新结点附加到新结点n n上并置上并置NODE(A)=nNODE(A)=n。转处理下一四元式。转处理下一四元式。1. 1. 准备操作数的结点准备操作数的结点 2. 2. 合并已知量合并已知量3. 3. 删除公共子表达式删除公共子表达式4. 4. 删除无用赋值删除无用赋值n例例10.4 试构造以下基本块试构造以下基本块G的的DAG(1) T0:=3.14(2) T1:=2*T0(3) T2:=R+r(4) A:=T1*T2(5) B:=A(6) T3:=
