知识结构12.1代码生成概述一.代码生成程序在编译系统中的位置代码生成程序在编译系统中的位置如图12.1所示：目标代码一般有3种形式：（1）能够立即执行的机器语言代码，所有地址均已定位（2）待装配的机器语言模块，当需要执行时，由连接装入程序把它们和某些运行程序连接起来，转换成能执行的机器语言代码（3）汇编语言代码，尚需经过汇编程序汇编，转换成可执行的机器语言代码二.设计代码生成程序的基本问题1.代码生成程序的输入：代码生成程序的输入由前端所产生的中间表示和符号表中的信息组成代码生成程序可以利用符号表中的信息来决定中间代码中的名字所指示的数据对象的运行时地址2.指令选择：所谓指令选择，是指寻找一个合适的目标机指令序列以实现给定的中间表示例如，对中间代码x:=y+z，其中x,y,z均为静态分配的变量，可以翻译成下述代码序列：LDR0,y/*将y放入寄存器R0*/ADDR0,z/*将z与R0相加*/STR0,x/*将R0的值存入x*/生成代码的质量取决于它的执行速度和代码序列的长度例如，如果目标机器有“加1”指令（INC），那么代码a:=a+1用INCa实现是最有效的，而不是用以下的指令序列实现：LDR0,aADDR0,#1STR0,a指令选择的基本原则：（1）减少产生代码的尺寸（2）减少目标代码的执行时间（3）降低目标代码的能耗这三者在某些情况下有可能会出现冲突，在具体选择的过程中应做折中考虑3.寄存器分配：寄存器分配的工作是确定在程序的哪个点将哪些变量或中间量的值放在寄存器中比较有益将经常使用的操作数保存在寄存器中是比较有利的一些目标机可能具有不同类型的寄存器，对寄存器使用的一致性方面也存在一定的约束寄存器的使用可以分成：（1）分配阶段：为程序的某一点选择驻留在寄存器中的一组变量（2）指派阶段：挑出变量将要驻留的具体寄存器，即寄存器赋值寄存器分配原则：（1）生成某变量的目标对象值时，尽量让变量的值或计算结果保留在寄存器中直到寄存器不够分配为止（2）当到基本块出口时，将变量的值存放在内存中（3）在同一基本块内后面不再被引用的变量所占用的寄存器应迟早释放，以提高寄存器的利用率例如，考虑图12.2的两个三地址代码序列，它们仅有的区别是第2个语句的算符不同，其最短代码序列在图12.3中给出：4.指令调度：指令调度是指确定程序指令的执行顺序例如，若在MIPS4KC上计算表示式(a+b)+c，可用表12.1中两个不同的指令序列，它们的主要不同在于指令顺序和寄存器的赋值：12.2一个简单的代码生成程序指令形式可包含以下四种类型，见表12.2：若op是一目运算符，则opRi,M的意义为：op(M)Ri以上指令中的op包括一般计算机上常见的一些运算符某些指令的意义说明如表12.3：二.待用信息链表法若在一个基本块中，变量A在四元式i中被定值，在i后面的四元式j中要引用A值，且从i到j之间没有其他对A的定值点，这时称j是四元式i中对变量A的待用信息或称下次引用信息，同时也称A是活跃的，若A被多处引用则可构成待用信息链与活跃信息链为了得到在一个基本块内每个变量的待用信息和活跃信息，可以从基本块出口的四元式开始由后向前扫描，为每个变量名建立相应的待用信息链和活跃变量信息链考虑到处理的方便，假定对基本块中的变量在出口处都是活跃的，而对基本块内的临时变量可分为两种情况处理：①对于没有经过数据流分析，且中间代码生成的算法中不允许在基本块外引用的临时变量，则这些临时变量在基本块出口处都认为是不活跃的②如果中间代码生成时的算法允许某些临时变量在基本块外引用时，则假定这些临时变量被认为是活跃的在变量的符号表的记录项中设定了待用信息和活跃信息的栏目，其算法步骤如下：（1）对各基本块的符号表中的“待用信息”栏置“非待用”，对“活跃信息”栏，按在基本块出中处是否为活跃而置成“活跃”或“非活跃”，假定外部变量都是活跃的，临时变量都是非活跃的（2）从后向前依次处理每个四元式i：A:=BopC，在符号表中依次执行下述步骤：①A的待用信息和活跃信息附加到i上②把A置成非待用F和非活跃F③B和C的待用信息和活跃信息附加到i上④把B和C待用信息置为i，活跃信息置成活跃L例如，四元式如下：(A,B,C,D是变量，T,U,V是中间变量)(1)T:=A-B(2)U:=A-C(3)V:=T+U(4)D:=V+U变量表12.4中“待用信息链”与“活跃信息链”的每列，从左至右为每当从后向前扫描一个四元式时相应变量的信息变化情况，空白处为没变化三.代码生成算法寄存器和内存地址的描述：RVALUE[Ri]={A,C}表示Ri的现行值