《《编译原理课程教案》第8章：代码生成》由会员分享，可在线阅读，更多相关《《编译原理课程教案》第8章：代码生成（47页珍藏版）》请在金锄头文库上搜索。
1、代码生成,第十一章,本章要求,主要内容：目标代码生成的任务，设计目标代码生成器需要考虑的主要问题，简单的代码生成器，Sample语言目标代码生成器的设计重点掌握：代码生成要考虑的主要问题，寄存器的分配，基本块的代码生成，以及从dag生成代码,代码生成所处的位置,8.1 概述,代码生成器的作用,各种代码的形式中间代码: 后缀式，三地址代码符号表中的项：名字，类型，嵌套深度，偏移量目标代码：绝对机器代码，可重定位代码，汇编代码生成器的输出必须是正确和高质量的产生最优化代码的问题是不可判定的,8.2 代码生成器设计中的问题,代码生成器依赖于目标机器和操作系统要充分发挥目标机器的能力：充分利用目标机器
2、的资源代码生成器固有的问题存储管理指令选择寄存器分配计算次序选择可移植的代码生成器机器描述,代码生成器的输入,符号表信息决定中间表示中名字所代表的数据对象的运行地址偏移量作用域可能在动态时刻作为调试信息存在中间表示代码生成的很多技术是可以用于不同的中间表示的代码生成前，中间表示记录了足够详细的程序信息名字的值可以表示为目标机器能够直接操作的数类型检查已经完成明显的语义错误已经发现,代码生成器的输出：目标程序,绝对机器语言可以放在内存中固定地方，并立即执行小程序、需要迅速编译和执行可重定位的机器语言程序可以分为多个目标模块，分别编译需要连接装配器将一组可重定位模块一起装入执行需要额外的开销，但灵
3、活：可分别编译子程序和从目标模块中调用其它先前编译好的程序模块如果目标机器不能自动处理重定位，则编译器必须提供显式的重定位信息给装配程序汇编语言代码生成的过程容易避免了重复汇编器的工作,存储管理,把程序中的名字映射到运行时的目标对象的地址是由前端和代码生成器共同完成的语言中过程的语义决定了运行时刻名字如何与存储空间相联系对名字的引用通过符号表记录了名字在过程数据区的相对地址所需要的存储空间运行时活动记录的管理运行时活动记录的分配和释放作为过程调用和返回序列的一部分call（调用），return（返回）halt（暂停），其它语句存储管理分静态、栈式和堆式存储分配,一个代码生成器的输入,其中，ar
4、r，i，j是过程s中定义的数据；buf和n是过程p定义的数据,指令地址的决定,通过一个计数器决定每个指令的地址标号的处理：j: goto i /*j是当前语句的号码*/如果i小于ji出现在j之前，目标地址是i对应的三地址代码的第一条指令地址如果i大于ji出现在j之后，目标地址此时不可知，可以利用回填的技术解决,指令选择,目标机器指令系统的性质决定了指令选择的难易程度指令系统的一致性和完整性是重要因素如果目标机器不能以一致的方式支持各种数据类型，则每种例外都要专门的处理指令的速度和机器的特点是另一些重要的因素如果不考虑目标程序的效率，则指令选择是直截了当的代码的质量取决于它的执行速度和长度可以从
5、多种指令中选择合适的：a=a+1MOVa , R0ADD#1 , R0INCaMOVR0 , a时间信息对代码序列是重要的，但不是任何时候都精确的,指令选择的例子,a := b + cd := a + e,MOVb , R0ADDc , R0MOVR0 , aMOVa , R0ADDe , R0MOVR0 , d,逐条语句地产生代码的方法常常产生低质量的代码,寄存器分配,利用寄存器放置运算对象的指令比运算对象在内存中的指令短些执行也快些充分利用寄存器对高质量的代码生成是重要的,寄存器分配（续）,寄存器使用的两个子问题寄存器分配：为程序的某一点选择驻留在寄存器中的一组变量寄存器指派：挑出变量将要
6、驻留的具体寄存器寄存器分配的最优化是NP完全的特定要求的满足,计算次序选择,计算执行的次序会影响目标代码的效率选择最佳次序是一个NP完全问题MOV R1 , &AMOV R1 , &AADD R1 , R0MUL R2 , R3MUL R2 , R3ADD R1 , R0ADD R1 , R2ADD R1 , R2,代码生成的途径,代码生成器的目的正确的代码：最重要的目标易于实现、调试和维护代码生成需要多方面的信息流信息依赖信息 代码生成的可移植性也是要考虑的一个问题将机器相关部分和不相关部分区分开,8.3 目标机器,熟悉目标机器和它的指令系统是设计一个好的代码生成器的先决条件但不存在通用的有
7、效的机器描述目标机器字节可寻址机器，4字节为一个字有n个通用寄存器R0 , R1 , , R(n-1)指令形式：,机器指令形式(op destination, source) ADD Rd,Rs / d+s SUB Rd,Rs /d-s MOV Rd,Rs /s d 机器指令开销 (cost)，不同的操作开销不同 MOV R,M 开销 2 ADD #1 ,R 开销 2 MOV R0,R1 开销 1,目标机器的地址方式,指令代价,如果把指令代价取成1，加上上述的地址模式的附加代价，就是对应指令的长度（以字计算）寄存器地址模式的代价为0含内存单元和常量的地址模式的代价是1，因为这种运算对象必须和指
8、令存在一起如果空间至关重要，则应使指令的长度极小化节省取指的开销，从而减少指令的执行时间提高指令cache的使用效率指令代价的例子MOV R0 , R1 代价是1，只占一个内存字MOV R5 , M 代价是2，M要独占一个内存字ADD #1 , R3 代价是2，常数1占一个内存字SUB 4(R0) , *12(R1) 代价是3，4和12各占一个内存字,例：a:=b+c 的实现方式：1. MOV R0 , b ADDR0 , c MOV a , R0 代价=62.MOV a , bADD a, c代价=6 假定R0, R1和R2中分别存放a, b和c的地址, 采用:3.MOV *R0, *R1A
9、DD *R0, *R2代价=2 假定R1和R2中分别包含b和c的值, 并且b的值在这个赋值以后不再需要, 则还可有4.ADDR1, R2MOV a, R1 代价=3,要产生好的代码，必须有效利用它的寻址能力，尽量把名字的左值或右值保存在寄存器中，以便在不久的将来使用,8.4 代码生成器的产生方法,解释型代码生成定义一个虚拟的目标机，编译器的前端直接把源语言映射到虚拟的目标机语言重用性差，代码生成器紧密地与汇编语言绑定在一起，对每一种机器要重新写后端代码生成模式匹配代码生成用机器描述语言描述了中间语言到汇编语言的映射，预处理器将它转换成相应的模式集代码生成器将中间语言与模式集作匹配，生成汇编代码
10、匹配算法与机器无关,代码生成器的产生方法（续）,表驱动代码生成把输入的表达式树看成是一个输入串通过构造状态转换表，用一系列语义动作完成代码生成 表驱动和模式匹配的差别模式匹配是自顶向下的推导，而表驱动可以是自顶向下的推导，也可以是自底向上的归约模式匹配依次匹配一个模版，模版集易于检查正确性，容易估计空间复杂性表驱动试图找出所有匹配的语法规则，代价高，语义动作表不容易检查正确性，大小也不容易估计,下次引用信息（1）,下次不再引用意味着优化的机会寄存器优化临时名字存储单元的指派计算下次引用信息三地址语句中名字的引用定义：假定三地址语句i把a的值赋给x，如果语句j用x作为运算对象，并且控制从i流到j
11、，这条路径中没有x的其它赋值，则称j引用x在I定的值在基本块内：下次引用信息对每个基本块反向扫描为每个名字x在符号表中登记它是否在本块中有下次引用如果在本块中没有下次引用，则登记它是否在本块的出口活跃。缺省认为所有的非临时变量在出口都是活跃的,下次引用信息（2）,对每一个三地址语句 i：x := y op z，依次执行下述步骤：把当前符号表中变量x的下次引用信息和活跃信息附加到语句i上；（如果x不活跃，则这个语句可以删掉）把符号表中x的下次引用信息和活跃信息分别置为“无下次引用”和“非活跃”；把当前符号表中变量y和z的下次引用信息和活跃信息附加到语句i上；把符号表中y和z的下次引用信息均置为i
12、，活跃信息均置为“活跃”。注意：上述次序不能颠倒，因为x可能是y或z例：t := a b u := a c v := t + u d := v + u,下次引用信息（3）,（1）t:=a+b（2）u:=a-c（3）v:=t+u（4）d:=v+u,名字 下次引用 活跃 t 无 非 a 无 活 b 无 活 c 无 活 d 无 活 u 无 活 v 无 活,d,u,v:无，活,无,非,4,4,活,活,u,v:4,活;t:无，非,无,非,3,活,活,3,u:3,活；a,c:无，活,无,非,2,2,活,活,a:2,活；b:无，活,无,非,1,1,活,活,t:3,活；,下次引用信息（4）,临时名字的存储分配
13、在需要临时变量时申请一个新的名字是简单有效的，但浪费空间如果两个临时变量不是同时活跃的，则可以压缩在同一单元中临时变量存储单元的分配：找到第一个不含活跃临时变量的单元，指派给待分配的临时变量如果没有合适的单元，则在活动记录的临时变量区域中增加一个单元,下次引用信息（5）,例子：t1 := a * at1 := a * at2 := a * bt2 := a * bt3 := 2 * t2t2 := 2 * t2t4 := t1 + t3t1 := t1 + t2t5 := b * bt2 := b * bt6 := t4 + t5t1 := t1 + t2,简单的代码生成器（1）,假设条件：三
14、地址语句的每种算符都有对应的目标机器算符计算结果留在寄存器中尽可能长的时间。只有在以下两种情况才把它存入主存此寄存器要用于其它计算正好在过程调用、转移或标号语句之前在基本块的结尾，所有的寄存器都将保存，使得代码生成算法简单,简单的代码生成器（2）,后续的代码尽可能引用变量在寄存器中的值，而不访问主存，如对a := b + c如果b在Ri中，c在Rj中，b在此语句后不活跃，则可以为它生成代价为1的代码ADD Ri, Rj ，结果a存在Ri中如果b在Ri中，c在内存单元中，b仍然不再活跃，则有：ADD Ri, c或：MOV Rj, cADD Ri,Rj如果c的值以后还要用，则第二种方式更好一些，因为可以直接从寄存器Rj中取得它的值由于语义的复杂性，上述代码生成可能要更为复杂,
