编译技术课件-代码生成及优化.pptxVIP

第十二章 代码优化参考书：Computer Architecture: A Quantitative Approach, 3rd version, By John L. Hennessy and David A. Patterson中文版：计算机体系结构量化研究方法，清华郑维民等译Compilers: Principles, Techniques, and Tools. By Alfred V. AHO, Monica S. Lam, Ravi Sethi and Jeffrey D. ULLMAN中文版：（龙3）编译原理，赵建华等译，机械工业出版社Advanced Compiler Design and Implementation. By Steven S. Muchnick.中文版：高级编译器设计与实现，赵克佳，沈志宇译，机械工业出版社针对 SPEC2000中lucas和mcf 施加不同级别的编译优化后的运行结果（编译器Alpha Compiler）全局寄存器分配指令调度局部子表达式删除代码内联有保护的代码内联消除数组边界检查消除空指针检查下面的优化合理吗？int foo(int a){ int count = 0 ; for(int i = 1 ; i<=100 ; i++){ count += i ; } return a + count ; }int foo(int a){ return a + 5050 ; }优化方法的分类1：与机器相关的优化技术面向超标量超流水线架构、VLIW或者EPIC架构的指令调度方法 面向SMP架构的同步负载优化方法 面向SIMD、MIMD或者SPMD架构的数据级并行优化方法等 与机器无关的优化技术 数据流分析 常量传播 公共子表达式删除 死代码删除 循环交换 代码内联等等 优化方法的分类2：局部优化技术 基本块内例如，局部公共子表达式删除 全局优化技术 函数/过程内跨越基本块例如，全局数据流分析跨函数优化技术 整个程序例如，跨函数别名分析 ，逃逸分析 等12.3基本块和流图基本块基本块中的代码是连续的语句序列 程序的执行（控制流）只能从基本块的第一条语句进入 程序的执行只能从基本块的最后一条语句离开 基本块的例子：程序片断(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 <= 20 goto (3)(13) …void foo(int* a, int* b){ int prod = 0 ; int i ; for(i = 1 ; i<=20; i++){ prod = prod + a[i] * b[i] ; } …}基本块的例子：划分基本块下列语句序列，哪些属于同一个基本块，哪些不属于？(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 <= 20 goto (3)(13) …（1）~（6）（3）~（8）（7）~（13）算法12.1 划分基本块输入：四元式序列输出：基本块列表，每个四元式仅出现在一个基本块中方法：1、首先确定入口语句（每个基本块的第一条语句）的集合1.1 整个语句序列的第一条语句属于入口语句1.2 任何能由条件/无条件跳转语句转移到的第一条语句属于入口语句1.3 紧跟在跳转语句之后的第一条语句属于入口语句2、每个入口语句直到下一个入口语句，或者程序结束，它们之间的所有语句都属于同一个基本块(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 <= 20 goto (3)(13) …1、首先确定入口语句（每个基本块的第一条语句）的集合1.1 整个语句序列的第一条语句属于入口语句（1）1.2 任何能由条件/无条件跳转语句转移到的第一条语句属于入口语句（3）1.3