代码生成及优化.ppt

代码生成及优化 北京航空航天大学 计算机学院 史晓华 博士 副教授 计算机体系结构 代码生成方法 代码优化技术 参考书： Computer Architecture: A Quantitative Approach, 3rd version, By John L. Hennessy and David A. Patterson 中文版：计算机体系结构量化研究方法，清华郑维民等译 Compilers: Principles, Techniques, and Tools. By Alfred V. AHO, Ravi SETHI and Jeffrey D. ULLMAN 中文版：编译原理，李建中，姜守旭译，机械工业出版社 Advanced Compiler Design and Implementation. By Steven S. Muchnick. 中文版：高级编译器设计与实现，赵克佳，沈志宇译，机械工业出版社 现代计算机（微处理器）体系结构 指令集 Instruction Set 流水线和指令级并行 Pipeline and Instruction Level Parallelism 存储结构和I/O Memory Hierarchy and I/O Systems 多处理器和线程级并行 Multiprocessor and Thread Level Parallelism Accumulator-based Architecture UNIVAC-I, EDSAC, IAS, 1950s Stack Architecture B5000, B6500, 1960s ALGOL JVM (1990s), PL/0 High-Level Language Computer Architecture VAX-11/780, 1970s~1980s Complex Instruction Set Computer 80x86, 1980s~ Reduced Instruction Set Computer CRAY-1, MIPS, SPARC, Intel P6 core, 1980s~ 指令级并行 Multiple-issued processor Intel PIII/P4 Very Long Instruction Word (VLIW) i860 Explicitly Parallel Instruction Computers (EPIC) IA64 多核协处理器 GPU，GPGPU 中间代码 代码生成 代码优化 栈式中间代码 中间代码的图表示 三地址码 基本块和流图 栈式中间代码 基于虚拟机的中间代码 P-CODE Java字节码(Java Bytecode) Java虚拟机 Java语言特性 执行依赖于硬件和软件平台独立的虚拟机 内存垃圾收集技术Garbage collection (GC) 程序员只需要申请空间，不再需要主动释放空间 GC在程序运行过程中，自动收集内存垃圾 运行时进行安全性、可靠性的检验 .class载入时作数据流分析，判断字节码是否符合安全标准 运行时自动进行数组边界(Array Bounds Check)、类型转换等检查(Checkcast) Java字节码举例: z = x + 1 iload x iconst_1 iadd mov eax, esi add eax, 1 istore z mov z[esp], eax 中间代码的图表示 语法树 用树型图的方式表示中间代码 操作数出现在叶节点上，操作符出现在中间结点 DAG图 Directed Acyclic Graphs 有向无环图 语法树的一种归约表达方式 中间代码的图表示 赋值语句：a:=b*(-c) + b*(-c) 三地址码 适合目标代码生成和优化的一种表达形式 三地址码是语法树或者DAG图的线性表示 树的中间结点由临时变量表示 三地址码与语法树的对应关系 三地址码与DAG图的对应关系 基本块和流图 基本块 是一个连续的语句序列 控制流（在正常执行状态下）从它的开始进入，并从它的末尾离开 基本块中间不能够有中断或者分支（某些语言的异常处理除外） 基本块的例子：程序片断 (1) prod := 0 (2) i := 1 (3) t1 := 4 * i (4) t2 := a [ t1 ] (5) t3 := 4 * i (6) t4 := b [ t3 ] (7) t5 := t2 * t4 (8) t6 := prod + t5 (9) prod := t6 (10) t7 := i + 1 (11) i := t7 (12) if i = 2