代码生成及优化北京航空航天大学计算机学院史晓华主要内容„中间代码（补充）„代码生成„代码优化„现代编译技术综述„参考书：‰Compilers:Principles,Techniques,andTools.ByAlfredV.AHO,RaviSETHIandJeffreyD.ULLMAN‰中文版：编译原理，李建中，姜守旭译，机械工业出版社‰AdvancedCompilerDesignandImplementation.ByStevenS.Muchnick.‰中文版：高级编译器设计与实现，赵克佳，沈志宇译，机械工业出版社中间代码（补充）„栈式中间代码„中间代码的图表示„三地址码„基本块和流图栈式中间代码„基于虚拟机的中间代码‰P-CODE‰Java字节码(JavaBytecode)Java虚拟机和字节码简介--JAVAVIRTUALMACHINE--JavaClassloader源程序Javaclass(Bytecodelibraries(*.java)verification)Java字节码JavaJust-in-timeJava(下载到本地)Interpretercompiler编译器Run-timeSystemJava字节码(*.class)LinuxWin32/NTSolarisHardwareJava语言特性„执行依赖于硬件和软件平台独立的虚拟机„内存垃圾收集技术Garbagecollection(GC)‰程序员只需要申请空间，不再需要主动释放空间‰GC在程序运行过程中，自动收集内存垃圾„运行时进行安全性、可靠性的检验‰.class载入时作数据流分析，判断字节码是否符合安全标准‰运行时自动进行数组边界(ArrayBoundsCheck)、类型转换等检查(Checkcast)„丰富的运行库支持‰J2ME：CLDC1.1,MIDP2.0,etc.‰J2SE：SWING,AWT,etc.Java字节码举例:z=x+1iloadxxesiiconst_111xesiiaddmoveax,esiaddeax,1x+1eaxistorezmovz[esp],eax中间代码的图表示„语法树‰用树型图的方式表示中间代码‰操作数出现在叶节点上，操作符出现在中间结点„DAG图‰DirectedAcyclicGraphs有向无环图‰语法树的一种归约表达方式中间代码的图表示„赋值语句：a:=b*(-c)+b*(-c)==a+a+***-b-bb-ccc语法树DAG图中间代码：三地址码„适合目标代码生成和优化的一种表达形式„三地址码是语法树或者DAG图的线性表示„树的中间结点由临时变量表示三地址码与语法树的对应关系=t1:=-ct2:=b*t1+at3:=-ct4:=b*t3**t5:=t2+t4-a:=t5b-bcc语法树三地址码与DAG图的对应关系=t1:=-ca+t2:=b*t1t3:=-ct4:=b*t3*t5:=t2+t2(t4)b-a:=t5cDAG图基本块和流图„基本块‰是一个连续的语句序列‰控制流（在正常执行状态下）从它的开始进入，并从它的末尾离开‰基本块中间不能够有中断或者分支（某些语言的异常处理除外）基本块的例子：程序片断(1)prod:=0voidfoo(int*a,int*b)(2)i:=1{(3)t1:=4*i(4)t2:=a[t1]intprod=0;(5)t3:=4*iinti;(6)t4:=b[t3](7)t5:=t2*t4for(i=1;i<=20;i++){(8)t6:=prod+t5(9)prod:=t6prod=prod+a[i]*b[i];(10)t7:=i+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)…划分基本块算法„输入：一个三地址语句序列