《编译原理》课程简介 (59).pdf
编译原理C O M P I L A T I O N P RIN C IP LE第八章 代码优化8.3 基本块的DAG表示及应用8.3 基本块的DAG表示及应用v 基本块的DAG一个节点带有下述标记或附加信息的DAG。类型标记含义叶结点标识符（变量名）,常数，addr（变量名）变量（常数）的值，变量地址内部结点运算符对其后继结点所代表的值进行该运算的结果各个结点附加一个或多个标识符这些变量具有该结点代表的值利用DAG可以进行基本块的优化8.3 基本块的DAG表示及应用(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例8.3 基本块的DAG表示及应用n基本块的DAG构造算法2 2型型:A:=B op C(op,B,C:A:=B op C(op,B,C,A),A)0 0型：型：A:=B(:=,B,A:=B(:=,B,A),A)1 1型型:A:=op B(op,B,:A:=op B(op,B,A),A)NODE（A）：标识符或常数A与节点n的对应函数8.3 基本块的DAG表示及应用n 仅含0，1，2型中间代码的基本块的DAG构造算法:首先，DAG为空。（2）如果当前四元式是1型，则转2(1)。（3）如果当前四元式是2型，则：w(I)如果NODE(C)无定义，则构造一标记为C的叶结点并定义NODE(C)为这个结点；w(II)转2(2)如果NODE（B）无定义，则构造一标记为B的叶结点并定义NODE（B）为这个结点；（1）如果当前四元式是0型，则记NODE(B)的值为n，转4。1对基本块的每一四元式，依次执行：8.3 基本块的DAG表示及应用如果NODE(B)是标记为常数的叶结点，则转2(3)，否则转3(1)。2执行B op C（即合并已知量），令得到的新常数为p。如果NODE(B)或NODE(C)是处理当前四元式时新构造出来的结点，则删除它。如果NODE(p)无定义，则构造一用p做标记的叶结点n。置NODE(p)=n，转4。执行op B（即合并已知量），令得到的新常数为p。如果NODE(B)是处理当前四元式时新构造出来的结点，则删除它。如果NODE(p)无定义，则构造一用p做标记的叶结点n。置NODE(p)=n，转4。如果NODE(B)和NODE(C)都是标记为常数的叶结点，则转2(4)，否则转3(2)。8.3 基本块的DAG表示及应用检查DAG中是否已有一结点，其唯一后继为NODE(B)，且标记为op（即找公共子表达式）。如果没有，则构造该结点n，否则就把已有的结点作为它的结点并设该结点为n，转4。3检查中DAG中是否已有一结点，其左后继为NODE(B)，其右后继为NODE(C)，且标记为op（即找公共子表达式）。如果没有，则构造该结点n，否则就把已有的结点作为它的结点并设该结点为n，转4。8.3 基本块的DAG表示及应用如果NODE(A)无定义，则把A附加在结点n上并令NODE(A)=n；否则先把A从NODE(A)结点上附加标识符集中删除（注意，如果NODE(A)是叶结点，则其标记A不删除），把A附加到新结点n上并令NODE(A)=n。转处理下一四元式。48.3 基本块的DAG表示及应用步骤1：如果NODE（B）无定义，则构造一标记为B的叶结点并定义NODE（B）为这个结点；(1)如果当前四元式是0型，则记NODE(B)的值为n，转4。步骤4：如果NODE(A)无定义，则把A附加在结点n上并令NODE(A)=n；例(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*T68.3 基本块的DAG表示及应用例(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步骤1：如果NODE（B）无定义，则构造一标记为B的叶结点并定义NODE（B）为这个结点；（1）如果当前四元式是2型，则：(I)如果NODE(C)无定义，则构造一标记为C的叶结点并定义NODE(C)为这个结点；(II)转2(2)。步骤2(2)：如果NODE(B)和NODE(C)都是标记为常数的叶结点，则转2(4)，否则转3(2)步骤2(4)：执行B op C（即合并已知量），令得到的新常数为p。如果NODE(B)或NODE(C)是处理当前四元式时新构造出来的结点，则删除它。如果NODE(p)无定义，则构造一用P做标记的叶结点n。置NODE(p)=n，转4步骤4：如果NODE(A)无定义，则把A附加在结点n上并令NODE(A)=n；8.3 基本块的DAG表示及应用例(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步骤1：如果NODE（B）无定义，则构造一标记为B的叶结点并定义NODE（B）为这个结点；（1）如果当前四元式是2型，则：(I)如果NODE(C)无定义，则构造一标记为C的叶结点并定义NODE(C)为这个结点；(II)转2(2)。步骤2（2）：如果NODE(B)和NODE(C)都是标记为常数的叶结点，则转2(4)，否则转3(2)步骤3（2）：检查中DAG中是否已有一结点，其左后继为NODE(B)，其右后继为NODE(C)，且标记为op（即找公共子表达式）。如果没有，则构造该结点n，否则就把已有的结点作为它的结点并设该结点为n，转4步骤4：如果NODE(A)无定义，则把A附加在结点n上并令NODE(A)=n；8.3 基本块的DAG表示及应用例(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*T68.3 基本块的DAG表示及应用例(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*T68.3 基本块的DAG表示及应用例(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*T68.3 基本块的DAG表示及应用例(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*T68.3 基本块的DAG表示及应用例(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*T68.3 基本块的DAG表示及应用例(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*T68.3 基本块的DAG表示及应用例(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*T68.3 基本块的DAG表示及应用对任何一个代码，如果其中参与运算的对象都是编译时的已知量，那么算法的步骤（2）并不生成计算该结点值的内部结点，而是执行该运算，用计算出的常数生成一个叶子结点。（合并已知量）如果某变量被赋值后，在它被引用前又重新赋值，那么算法的步骤（4）已把该变量从具有前一个值的结点上删除。（删除无用赋值）n 根据DAG构造算法和上述例子，可以看到：算法的步骤（3）的作用是检查公共子表达式，对具有公共子表达式的所有代码，它只产生一个计算该表达式值的内部结点，而把那些被复制的变量标识符附加到该结点上。（删除公共子表达式）8.3 基本块的DAG表示及应用(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优化前(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:=R-r(9)B:=A*T6优化后|编译原理谢 谢Thanks
