编译原理[清华]第十二章代码生成.pptVIP

第12章 代码生成;;12.1 代码生成概述;目标代码生成的一些共同的问题，而不讨论某个特定机器的代码生成问题 寄存器分配算法 目标代码的执行效率很大程度依赖于寄存器的使用； 基本块的代码生成算法 寄存器分配算法仅限定在一个基本块的范围内，以四元式的中间代码作为输入，以一个称作M的模型机的汇编语言作为输出。 ;12.2 一个计算机模型;寻址类 型 ;特殊指令 除了上述的寻址方式和一般的运算指令之外，计算机模型的指令系统中还包括如下特殊指令 主要有两大类： 内存与寄存器交换类：包括LD与ST； 比较与转移类：如CMP与J X;等于零转X单元;例：条件语句 if AB goto X 中间代码：（ J, A, B, X ） 目标代码： CMP A, B J X ;12.3 一个简单的代码生成器;12.3.1 寄存器分配原则;基于基本块的寄存器分配的一般原则： 当生成某变量的目标代码时，尽量让变量的值或中间结果保留在寄存器中，直到寄存器不够分配为止，这样引用变量值时可减少对内存的存取次数，提高运行速度 进入基本块时所有寄存器是空闲的，当到基本块出口时，将变量的有用值存回内存，释放所有寄存器 在基本块内，后边不再被引用的变量占用的寄存器应尽早释放，以提高寄存器的利用效率;12.3.2 待用信息链表法;基本定义： 定值、引用、活跃 在形如 i: A:=B+C 的代码中，出现在“:=”左边和右边的变量，分别被称为对变量的定值和引用，i被称为变量的定值点或引用点。若变量的值在i之后的代码序列中被引用，则称变量在i点是活跃的。 待用信息 在基本块中，变量A在四元式i中被定值，在i后面的四元式j中引用A值，且从i到j之间没有其他对A的定值点，称j是i中对变量A的待用信息（下次引用信息）。所有这样的待用信息jk（k=1,2,…）构成待用信息链。;只在基本块内考虑待用信息，一个变量在基本块的后继中是否被引用，可从活跃变量信息得知（出基本块后，变量是否活跃需要进行全局的数据流分析才能确定）;在基本块B2内：R在(3)处定值，在(4)处被引用，所以(4)是(3)中R的待用信息 流程B3-B2：X在(5)处被定值，在(3)处被引用，所以X在(5)处是活跃的;基本块内求待用信息的算法 假设符号表中含有变量的待用信息和活跃信息栏；四元式表上也有关于结果变量、左右操作数变量的待用和活跃信息栏。 把基本块中各变量在符号表的登记项中的待用信息栏置为“非待用”，活跃信息栏按变量在基本块出口是否活跃而置为“活跃”或“非活跃”（假定用户变量都是活跃的，临时变量都是非活跃的）。;从基本块出口的四元式开始由后向前依次处理各个四元式 i: A:=B op C ，直到处理完为止： 把符号表中结果变量A的待用信息和活跃信息附加到四元式i上。 把符号表中变量A的待用信息栏和活跃信息栏分别置为“非待用”和“非活跃”。（由于在i中对A的定值只能在i以后引用，而对i以前的四元式来说A是非活跃和非待用的。） 把符号表中变量B和C的待用信息和活跃信息附加到四元式i上。 把符号表中变量B和C的待用信息栏置为“i”，活跃信息栏置为“活跃”。 注意：i，ii，iii，iv的次序不能颠倒，因为B和C也可能是A;求待用信息的实例;(F,F);12.3.3 代码生成算法;变量地址描述数组AVALUE 生成目标代码要用到变量的地址，它可能是某寄存器Ri，也可能是内存单元（仍用变量名表示）。若变量值同时在寄存器Ri和内存，则取Ri为其地址。 AVALUE[A]={Ri} 表示变量A的值在Ri中，不在内存。 AVALUE[B]={Rj, B} 表示变量B的值在Rj中，又在内存。 AVALUE[C]={C} 表示变量C的值只在内存。 ;寄存器分配函数GETREG 以形如 i: A:＝B op C 的四元式为输入，返回一个寄存器R，用以存放A的结果值 其算法为： 如果B独占Ri，且B与A是同一标识符或B值不再引用，则选Ri为R并转（4） 如果有空闲Ri，则选Ri为R并转（4）。;释放一个Ri作为R，最好占用Ri的变量值同时在主存中，或在基本块中引用的位置最远。对Ri中不是A(结果变量)的变量M，且其值不在内存，则做如下处理： 生成目标代码 ST Ri , M，把变量M的值送入内存 修改变量地址描述：如M不是B（左操作数）则AVALUE[M]＝{M}，否则AVALUE[M]＝{Ri，M}。 修改寄存器描述：删除RVALUE{Ri}中的M。 给出R，返回 通过GETREG（i: A:=B op C ）返回的寄存器R用于进行B op C的运算，并把结果（A值）保存在R中。;4. 基本块的代码生成算法;分配寄存器 R=GET