代码优化解析PPT学习教案

1、会计学1代码优化解析代码优化解析词法分析器词法分析器语法分析器语法分析器中间代码生成中间代码生成器器优化段优化段源程序源程序单词符号单词符号语法单位语法单位四元式四元式表表格格管管理理出出错错处处理理目标代码生成器目标代码生成器四元式四元式目标代码目标代码第1页/共59页编译前端编译前端代码优化器代码优化器编译后端编译后端控制流分析控制流分析数据流分析数据流分析代码变换代码变换第2页/共59页指令的优化等第3页/共59页第4页/共59页第5页/共59页第6页/共59页第7页/共59页删除公共子表达式删除公共子表达式(删除多删除多余运算余运算) 公共子表达式是指在一个基本程序块内计算结果相同的子

2、表达式公共子表达式是指在一个基本程序块内计算结果相同的子表达式代码外提代码外提是指把循环不变的运算提到循环体前面是指把循环不变的运算提到循环体前面优化前的中间代码优化前的中间代码第8页/共59页经删除公共子表达式和代经删除公共子表达式和代码外提后的中间代码码外提后的中间代码3.降低运算强度降低运算强度 主要指不改变运算结果的前提下主要指不改变运算结果的前提下,将程序执行时间长的运算替换成执行时间短的运算降低运算级别将程序执行时间长的运算替换成执行时间短的运算降低运算级别第9页/共59页经强度削弱后的中间代经强度削弱后的中间代码码4.变换循环控制变量(删除归纳变量)如果在循环体内存在一个变量(或

3、临时变量)T与循环控制变量 i保持线性关系,同时在循环后面不引用I,而除去i又不影响程序运行结果,则可由T取代循环控制变量变量 I, 这种方法称为变换循环控制变量(删除归纳变量)5.合并已知量合并已知量是指若参加运算的两个对象在编译时都是已知量,则可以在编译时直接计算出它们的运算结果6.复写传播是指尽量不引用那些在程序中仅仅只传递信息而不改变其值,也不影响其运行结果的变量.第10页/共59页经变换循环控制变量经变换循环控制变量, ,合合并已知量并已知量, ,复写传播后的复写传播后的中间代码中间代码7,删除无用赋值删除无用赋值减少无用的变量,使代码更简洁第11页/共59页假(1) S=0(4)

4、T2=addr(A)-4(7) T5=addr(B)-4(3) T1=4(5) T3= T2T1(8) T6= T5T1(9) T7= T3* T6(10) S=S+ T7(3) T1= T1+4(12)if T180 goto(5)B2B1真经删除无用赋值后的经删除无用赋值后的中间代码中间代码第12页/共59页第13页/共59页 第14页/共59页第15页/共59页第16页/共59页入口语句入口语句n入口语句入口语句m入口语句入口语句n转移语句转移语句m入口语句入口语句n停语句停语句m第17页/共59页第18页/共59页1.求出四元式程序中各个基本块的入口求出四元式程序中各个基本块的入口语句

5、语句:1) 程序第一个语句，或程序第一个语句，或2) 能由条件转移语句或无条件转移能由条件转移语句或无条件转移语句转移到的语句，或语句转移到的语句，或3) 紧跟在条件转移语句后面的语句紧跟在条件转移语句后面的语句。第19页/共59页1.求出四元式程序中各个基本块的入口求出四元式程序中各个基本块的入口语句语句:1) 程序第一个语句程序第一个语句，或，或2) 能由条件转移语句或无条件转移能由条件转移语句或无条件转移语句转移到的语句，或语句转移到的语句，或3) 紧跟在条件转移语句后面的语句紧跟在条件转移语句后面的语句。第20页/共59页1.求出四元式程序中各个基本块的入口求出四元式程序中各个基本块的

6、入口语句语句:1) 程序第一个语句，或程序第一个语句，或2) 能由条件转移语句或无条件转移能由条件转移语句或无条件转移语句转移到的语句语句转移到的语句，或，或3) 紧跟在条件转移语句后面的语句紧跟在条件转移语句后面的语句。第21页/共59页1.求出四元式程序中各个基本块的入口语求出四元式程序中各个基本块的入口语句句:1) 程序第一个语句，或程序第一个语句，或2) 能由条件转移语句或无条件转移语能由条件转移语句或无条件转移语句转移到的语句句转移到的语句，或，或3) 紧跟在条件转移语句后面的语句。紧跟在条件转移语句后面的语句。第22页/共59页1.求出四元式程序中各个基本块的入口求出四元式程序中各

7、个基本块的入口语句语句:1) 程序第一个语句，或程序第一个语句，或2) 能由条件转移语句或无条件转移能由条件转移语句或无条件转移语句转移到的语句，或语句转移到的语句，或3) 紧跟在条件转移语句后面的语句紧跟在条件转移语句后面的语句。第23页/共59页2. 对以上求出的对以上求出的每个入口语句，每个入口语句，确定其所属的基确定其所属的基本块。它是由该本块。它是由该入口语句到入口语句到下一下一入口语句入口语句(不包不包括该入口语句括该入口语句)、或到、或到一转移语一转移语句句(包括该转移包括该转移语句语句)、或、或一停一停语句语句(包括该停包括该停语句语句)之间的语之间的语句序列组成的。句序列组成

8、的。第24页/共59页(8) 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 YB1B2B3B4第25页/共59页第26页/共59页第27页/共59页(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) write Y(9) halt(5) X:=Y(6) Y:=R(7) goto (3)(3) R:=X

9、 mod Y(4) if R=0 goto (8)(1) read X(2) read YB1B2B3B4第28页/共59页块号bfirstbLastb sucbpredb1(1)(3)2_2(4)(5)3、41、33(6)(7)224(10)(11)_2第29页/共59页(1)read c 1(2) a:=0 (3)b:=1L1:(4)a:=a+b 2(5)if bc goto L2( 6 ) b : = b + 1 3(7) goto L1L2: (10) write A 4 (11) halt第30页/共59页第31页/共59页第32页/共59页assigna+*buminuscDAGa

10、ssigna+*buminusc抽象语法树抽象语法树*buminusc第33页/共59页assigna+*buminusc抽象语法树抽象语法树*buminusc第34页/共59页assigna+*buminuscDAG抽象语法树抽象语法树对应的代码：对应的代码： T1:=-c T2:=b*T1T3:=-c T4:=b*T3 T5:=T2+T4 a:=T5第35页/共59页n13.14n3n4Rrn5+T2, T4图的图的叶结点叶结点以一以一标识符标识符或或常数常数作为标记，表示作为标记，表示该结点代表该变量或常数的值该结点代表该变量或常数的值; ;图的图的内部结点内部结点以一以一运算符运算符作

11、为作为标记，表示该结点代表应用该标记，表示该结点代表应用该运算符对其后继结点所代表的运算符对其后继结点所代表的值进行运算的结果值进行运算的结果; ;图中各个结点上可能图中各个结点上可能附加一个或多个标识附加一个或多个标识符符( (称附加标识符称附加标识符) )表表示这些变量具有该结示这些变量具有该结点所代表的值。点所代表的值。第36页/共59页第37页/共59页(0) 0型型: A:=B (:=，B，-，A) n1AB第38页/共59页(1) 1型型: A:=op B (op，B，-，A)n1ABn2op(2) 2型型: A:=B op C (op，B，C，A)n2ABn1opn3C第39页/

12、共59页四元式四元式 DAG DAG 图图(3) 2型型: A:=BC (=，BC，-，A) n2ABn1=n3C(4) 2型型: if B rop C goto (s) (jrop，B，C，(s)n2(s)Bn1ropn3C第40页/共59页四元式四元式 DAG DAG 图图(5) 3型型: DC:=B (=，B，-，DC)(6) 0型型: goto (s) (j，-，-，(s)(s)n1n2Bn1=n4Cn3D第41页/共59页例：赋值语句例：赋值语句T T4 4:=A+B-:=A+B-（E-E-（C+DC+D）四元式序列GT1:=A+BT2:=C+DT3:=E-T2T4:=T1-T3 A

13、 B E C Dn9n3n8n1n2n7n6n4n5 T4 T1 T3 T2 + - - +DAG:第42页/共59页第43页/共59页 To 3.14 (a)n1(1) T(1) T0 0:=3.14:=3.14第44页/共59页 T0 T1 3.14 6.28 (b)n2n1(1)T(1)T0 0:=3.14:=3.14(2)T(2)T1 1:=2:=2* *T T0 0第45页/共59页(1)T(1)T0 0:=3.14:=3.14(2)T(2)T1 1:=2:=2* *T T0 0(3)T(3)T2 2:=R+r:=R+r第46页/共59页 A * T2 + T0 T1 3.14 6.

14、28 R r (d)n2n5n3n1n4n6(1)T(1)T0 0:=3.14:=3.14(2)T(2)T1 1:=2:=2* *T T0 0(3)T(3)T2 2:=R+r:=R+r(4)A:=T(4)A:=T1 1* *T T2 2第47页/共59页 A,B * T2 + T0 T1 3.14 6.28 R r (e)n2n5n3n1n4n6(1)T(1)T0 0:=3.14:=3.14(2)T(2)T1 1:=2:=2* *T T0 0(3)T(3)T2 2:=R+r:=R+r(4)A:=T(4)A:=T1 1* *T T2 2(5)B:=A(5)B:=A第48页/共59页 A,B *

15、T2 + T0 T1,T3 3.14 6.28 R r (f)n2n5n3n1n4n6(1)T(1)T0 0:=3.14:=3.14(2)T(2)T1 1:=2:=2* *T T0 0(3)T(3)T2 2:=R+r:=R+r(4)A:=T(4)A:=T1 1* *T T2 2(5)B:=A(5)B:=A(6)T(6)T3 3:=2:=2* *T T0 0第49页/共59页 A,B * T2,T4 + T0 T1,T3 3.14 6.28 R r (g)n2n5n3n1n4n6(1)T(1)T0 0:=3.14:=3.14(2)T(2)T1 1:=2:=2* *T T0 0(3)T(3)T2

16、2:=R+r:=R+r(4)A:=T(4)A:=T1 1* *T T2 2(5)B:=A(5)B:=A(6)T(6)T3 3:=2:=2* *T T0 0(7)T(7)T4 4:=R+r:=R+r第50页/共59页 A,B,T5 * T2,T4 + T0 T1,T3 3.14 6.28 R r (h)n2n5n3n1n4n6(1)T(1)T0 0:=3.14:=3.14(2)T(2)T1 1:=2:=2* *T T0 0(3)T(3)T2 2:=R+r:=R+r(4)A:=T(4)A:=T1 1* *T T2 2(5)B:=A(5)B:=A(6)T(6)T3 3:=2:=2* *T T0 0(

17、7)T(7)T4 4:=R+r:=R+r(8)T(8)T5 5:=T:=T3 3* *T T4 4第51页/共59页(1)T(1)T0 0:=3.14:=3.14(2)T(2)T1 1:=2:=2* *T T0 0(3)T(3)T2 2:=R+r:=R+r(4)A:=T(4)A:=T1 1* *T T2 2(5)B:=A(5)B:=A(6)T(6)T3 3:=2:=2* *T T0 0(7)T(7)T4 4:=R+r:=R+r(8)T(8)T5 5:=T:=T3 3* *T T4 4(9)T(9)T6 6:=R-r:=R-r第52页/共59页(1) T0:=3.14n13.14T0n26.28T1n3n4Rrn5+T2n6*A, B, T3, T4, T5n7T6-n8*B(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*T6T6第53页/共59页q优化后的四元式优化后的四元式(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*T6n13.14T0n26.28T