北京航空航天大学《编译原理》第11章 代码优化(2)

《北京航空航天大学《编译原理》第11章 代码优化(2)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、代码生成及优化北京航空航天大学计算机学院史晓华主要内容¢中间代码（补充）¢代码生成¢代码优化¢现代编译技术综述¢参考书：ßCompilers:Principles,Techniques,andTools.ByAlfredV.AHO,RaviSETHIandJeffreyD.ULLMANß中文版：编译原理，李建中，姜守旭译，机械工业出版社ßAdvancedCompilerDesignandImplementation.ByStevenS.Muchnick.ß中文版：高级编译器设计与实现，赵克佳，沈志宇译

2、，机械工业出版社中间代码（补充）¢栈式中间代码¢中间代码的图表示¢三地址码¢基本块和流图栈式中间代码¢基于虚拟机的中间代码ßP-CODEßJava字节码(JavaBytecode)Java虚拟机和字节码简介--JAVAVIRTUALMACHINE--JavaClassloaderJavaclass源程序(Bytecode(*.java)librariesverification)Java字节码JavaJust-in-timeJava(下载到本地)Interpretercompiler编译器Run-ti

3、meSystemJava字节码(*.class)LinuxWin32/NTSolarisHardwareJava语言特性¢执行依赖于硬件和软件平台独立的虚拟机¢内存垃圾收集技术Garbagecollection(GC)ß程序员只需要申请空间，不再需要主动释放空间ßGC在程序运行过程中，自动收集内存垃圾¢运行时进行安全性、可靠性的检验ß.class载入时作数据流分析，判断字节码是否符合安全标准ß运行时自动进行数组边界(ArrayBoundsCheck)、类型转换等检查(Checkcast)¢丰富的运行库

4、支持ßJ2ME：CLDC1.1,MIDP2.0,etc.ßJ2SE：SWING,AWT,etc.Java字节码举例:z=x+1iloadxxesiiconst_111xesiiaddmoveax,esix+1eaxaddeax,1istorezmovz[esp],eax中间代码的图表示¢语法树ß用树型图的方式表示中间代码ß操作数出现在叶节点上，操作符出现在中间结点¢DAG图ßDirectedAcyclicGraphs有向无环图ß语法树的一种归约表达方式中间代码的图表示¢赋值语句：a:=b*(-c)+b

5、*(-c)==a+a+***b-b-b-ccc语法树DAG图中间代码：三地址码¢适合目标代码生成和优化的一种表达形式¢三地址码是语法树或者DAG图的线性表示¢树的中间结点由临时变量表示三地址码与语法树的对应关系=t1:=-ct2:=b*t1+at3:=-ct4:=b*t3**t5:=t2+t4a:=t5b-b-cc语法树三地址码与DAG图的对应关系=t1:=-ca+t2:=b*t1t3:=-ct4:=b*t3*t5:=t2+t2(t4)a:=t5b-cDAG图基本块和流图¢基本块ß是一个连续的语句序列

6、ß控制流（在正常执行状态下）从它的开始进入，并从它的末尾离开ß基本块中间不能够有中断或者分支（某些语言的异常处理除外）基本块的例子：程序片断(1)prod:=0voidfoo(int*a,int*b)(2)i:=1{(3)t1:=4*iintprod=0;(4)t2:=a[t1](5)t3:=4*iinti;(6)t4:=b[t3](7)t5:=t2*t4for(i=1;i<=20;i++){(8)t6:=prod+t5prod=prod+a[i]*b[i];(9)prod:=t6(10)t7:=i+

7、1}(11)i:=t7…(12)ifi<=20goto(3)}(13)…基本块的例子：划分基本块(1)prod:=0下列语句序列，哪些(2)i:=1属于同一个基本块，(3)t1:=4*i哪些不属于？(4)t2:=a[t1]（1）~（6）(5)t3:=4*i（3）~（8）(6)t4:=b[t3]（7）~（13）(7)t5:=t2*t4(8)t6:=prod+t5(9)prod:=t6(10)t7:=i+1(11)i:=t7(12)ifi<=20goto(3)(13)…划分基本块算法¢输入：一个三地址语句

8、序列¢输出：一个基本块列表，每个三地址语句仅出现在一个基本块中¢方法：ß1、首先确定入口语句（每个基本块的第一条语句）的集合¢1.1整个语句序列的第一条语句属于入口语句¢1.2任何能由条件/无条件跳转语句转移到的第一条语句属于入口语句¢1.3紧跟在跳转语句之后的第一条语句属于入口语句ß2、每个入口语句直到下一个入口语句，或者程序结束，之间的所有语句都属于同一个基本块划分基本块：例子(1)prod:=0¢1、首先确定入口语句（每个基本块的第一条语句）的集合