编译原理优化和目标代码生成（2h）.pptVIP

编译原理优化和目标代码生成(2h) 主讲：蒋伟进 教授 2007.03-05 ７.2 执行时的内存分配 编译程序需要为源程序中的数据分配执行时的存储空间，编译程序从操作系统中申请编译程序计算出的所需的内存，或编译程序生成在运行时需申请内存的指令。 （１）　确定用来表示某一数据项的内存大小。 （２）　使用适当的内存分配策略，实现具体数　据的作用域和生存期。 （３）　确定以适当的算法访问生存期内的数据，包括基本型数据结构构造类型。 为目标程序分配执行时所需的存储空间： 　　　一种是在目标程序运行前，由编译程序为数据结构分配存储空间，在程序的执行期间不再分配和解除这种内存分配。叫做静态存储分配。 　　　一种在程序运行期间均可以对内存实现分配或解除分配，一旦存储分配解除该存储空间内的数据便失去意义。叫做动态存储分配。 例： int arr[10000]; void Binky() { int i; for (i=0; i 10000; i++) arr[i] = 1; } int arr[10000]; void Winky() { register int *p; for (p = arr; p arr + 10000; p++) *p = 1; } 目标：　作为一个高级语言的使用者很希望编译程序所产生的代码能够和直接用机器语言编写的程序效果一样好。　 代码优化是指对原代码进行的变换，从而获得在时间和空间上效率相对高的程序，且一般也不是在时间和空间上最省的程序，在进行优化时应该做到： １　代码的变换必须保持原程序的语义。 ２　从理论上，变换加快了程序的速度。 ３　这种变换是值得的 优化分类 按阶段分: 与机器无关的优化---对中间代码进行 依赖于机器的优化---对目标代码进行 根据优化所涉及的程序范围分成: (1)局部优化:(基本块)应用于仅包含少量语句的小程序的优化变换。 (2)循环优化:对循环中的代码进行优化 (3)全局优化:大范围的优化应用于一个程序单元，如一个函数或一个过程的优化变换。 程序的执行效率是可以通过在编译期间进行优化变换，不改变语义重写程序段以提高程序的工作效率。虽然变换的方法很多，但是常用的大致有以下几种： １　编译求值 ２　合并预算 ３　删除死码 ４　减少频率 ５　强度削弱和变换循环条件 ６　减少重写传播 局部优化：　所需要的开销相对较低，因此从优化所得到的收益也相对较低。　局部优化只是在较小的　程序段中进行优化，从而到达优化的目的。　这种程序段称为基本段。 全局优化：　要产生高效的代码，编译程序仅在基本块内优化是不够的，编译程序应把程序作为一个整体来考虑，对各个基本块的信息进行数据流的分析从而达到优化的目的。全局优化同局部优化相比，全局优化需要更多的分析，以便确定优化的可行性。 优化的原则 等价原则 有效原则 时间 空间 合算原则 优化的代价 效果 优化的基本方法 去处冗余 削减强度 使用更快的指令 局部优化 方法 合并已知量 临时变量改名 交换语句位置 代数变换 循环优化 代码外提 强度削弱 A=A+1 A++ 删除归纳变量 例如循环中加法变为，循环外乘法 窥孔优化 窥孔 目标程序中的一个可以移动的窗口 优化方法 冗余存取 不可到达代码 控制流优化 强度削弱 删除无用操作 目标机器的地址方式 例1：a:=b+c 1. MOV 　b, R0 ADD 　c, R0 cost=6 MOV 　R0, a 2. MOV 　b, a ADD 　c, a cost=6 假定R0, R1和R2中分别存放了a, b和c的地址, 采用: 3. MOV *R1, *R0 ADD *R2, *R0 cost=2 假定R1和R2中分别包含b和c的值, 并且b的值在这个赋值以后不再需要, 则还可有 4. ADD R2, R1 MOV R1, a cost=3 输入 中间代码 三元式 四元式 输出 可执行代码 待装配的代码 汇编代码 其他考虑 指令选择 RISC CISC 寄存器分配 通用寄存器方案 专用寄存器方案 大寄存器方案 介绍 懒编译策略 JIT编译技术 .net Java * 第七章 编译程序 ７ ． 1 编译程序考虑的因素 ７ ． 2 执行时的内存分配 ７ ． 3 代码优化 7.1 编译程序考虑的因素 　　编译程序设计时，除了需要用到前面介绍的分析技术和制导翻译外，还要考虑如何从源程序数据空间映射到具体物理存储空间，也就是运行时的数据表示。 　　在运行的时候如何组织或存放数据、在源程序中同名标识符是怎么样描述不同的对象、运行时的程序控制权是如何转移的，参数是如何传递以及如何生成质量较高的目