第十二章代码生成

第12章代码生成代码生成:

中间代码作为输入

特定机器的机器语言或汇编语言作为输出，这样的转换程序称为代码生成器，1如果用‘op’表示运算符，用‘M’表示内存单元，用变量名表示该变量所在的单元，‘C’表示常量，‘*’表示间址方式存取，指令形式表(P278表12.2)。opRi,M

opRi,Rj

opRi,c(Rj)

opRi,*M

opRi,*Rj

opRi,*c(Rj)(Ri)op(M)

Ri

(Ri)op(Rj)

Ri

(Ri)op((Rj)+c)

Ri

(Ri)op((M))

Ri

(Ri)op((Rj))

Ri

(Ri)op(((Rj)+c))

Ri2指令意义指令意义LDRi,B

STRi,B

JX

CMPA,B把B单元的内容取到寄存器Ri，即(B)

Ri。

把寄存器Ri的内容存到B单元，即(Ri)

B。

无条件转向X单元。

把A单元和B单元的值进行比较，并根据比较情况把机器内部特征寄存器CT置成相应状态。CT占两个二进位。根据A<B或A=B或A>B分别置CT为0或1或2。J<X

J≤X

J=X

J≠X

J>X

J≥X如CT=0转X单元。

如CT=0或CT=1转X单元。

如CT=1转X单元。

如CT≠1转X单元。

如CT=2转X单元。

如CT=2或CT=1转X单元。

3一个简单的代码生成器

它以四元式的代码作为输入，将其转换成目标代码。它在基本块内如何充分利用寄存器提高目标代码的运行效率？

寄存器分配的原则（P276）①当生成某变量的目标代码时，尽量让变量的值或计算结果保留在寄存器中直到寄存器不够分配时为止，这样引用变量值时可减少对内存的存取次数，以提高运行速度。

②当到基本块出口时，将变量的值存放在内存中，这样从基本块外入口的变量值都在内存中。

③对于在一个基本块内后边不再被引用的变量所占用的寄存器应尽早释放，以提高寄存器的利用效率。

4例:设一高级语言的语句为：A:=(B+C)*D+E翻译成中间代码为:T1:=B+CT2:=T1*DA:=T2+E问目标代码是什么5目标代码:LDR,BADDR,CSTR,T1LDR,T1MULR,DSTR,T2LDR,T2ADDR,ESTR,A中间代码为:T1:=B+CT2:=T1*DA:=T2+E如果不考虑代码的效率，我们可以翻译为如下代码：6从正确性看,没有问题,但却有很多冗余,因为T1,T2为临时变量,出了基本快后将不会引用,因此,(3)(4)(6)(7)均可省掉,考虑到效率和充分利用寄存器的问题,目标代码变为:LDR,BADDR,CMULR,DADDR,ESTR,AA:=(B+C)*D+E为了能够这样做，代码生成器必须了解一些信息：在产生T2:=T1*D对应的目标代码时，为了省去STR,T1,就必须知道出了基本块后T1不会再利用。为了省去指令LDR,T1,就必须知道T1的值已经在R中。原目标代码:LDR,BADDR,CSTR,T1LDR,T1MULR,DSTR,T2LDR,T2ADDR,ESTR,A中间代码为:T1:=B+CT2:=T1*DA:=T2+E7在一个基本块内考虑如何充分利用寄存器：l尽可能地让该变量的值保留在寄存器中l尽可能引用变量在寄存器中的值待用信息：若在一个基本块中，变量A在四元式i中被定值，在i后面的四元式j中要引用A值，且从i到j之间没有其它对A的定值点，称j是四元式i中对变量A的待用信息或称下次引用信息，同时也称A是活跃的。若A被多处引用，则可构成待用信息链与活跃信息链。可从基本块的出口由后向前扫描，对每个变量建立相应的待用信息链和活跃变量信息链。

8对各基本块的符号表中的“待用信息”栏和“活跃信息”栏置初值，即把“待用信息”栏置“非待用”，对“活跃信息”栏按在基本块出口处是否为活跃而置成“活跃”或“非活跃”。这里假定变量都是活跃的，临时变量都是非活跃的。符号表中增加“待用信息”栏和“活跃信息”栏见P280

表12.4计算待用信息的算法：9

从基本块出口到入口由后向前依次处理每个四元式。对每个四元式i:A:=BopC，依次执行下述步骤：a)把符号表中变量A的待用信息和活跃信息附加到四元式上。b)把符号表中变量A的待用信息栏和活跃信息栏分别置为“非待用”和“非活跃”。（变量定义时为非活跃、非待用）由于在i中对A的定值只能在i以后的四元式才能引用，因而对i以前的四元式来说，A是不活跃也不可能是待用的。c)把符号表中变量B和C的待用信息和活跃信息附加到四元式i上。d)把符号表中变量B和C的待用信息栏置为“i”，活跃信息栏置为“活跃”。（使用时为待用、活跃）注意，以上a)和b)，c)和d)的次序不能颠倒。

10若用A，B，C和D表示变量，用T，U，V表示中间变量，有四元式如下：(1)T:=A-B(2)U:=A-C(3)V:=T+U(4)D:=V+U其名字表中的待用信息和活跃信息如下表，用“F”表示“非待用”或“非活跃”，用“L”表示活跃。(1)(2)(3)(4)表示四元式序号。例：1112

RVALUE[Ri]={A,C}表示Ri的现行值是变量A，C的值

AVALUE[A]={A}表示A的值在内存中

AVALUE[A]={Ri,A}表示A的值既在寄存器Ri中又在内存中

AVALUE[A]={Ri}表示变量A的值在寄存器Ri中代码生成算法

为了在代码生成中能有效地分配寄存器，还需随时掌握各寄存器的使用情况。用一个数组RVALUE来描述(记录)每个寄存器当前的状况，是处于空闲状态还是被某个或某几个变量占用（若程序中含有复写，就会出现最后一种情况）；用数组AVALUE[M]表示变量的存放情况。因此一个变量的值可能存放在寄存器中或存放在内存中，也可能既在寄存器中又在内存中。

13基本块的代码生成算法对每个四元式i:A:=BopC，依次执行下述步骤：（1）以四元式i:A:=BopC为参数，调用过程

getreg(i:A:=BopC)。从getreg返回时，得到一寄存器

R，用它作存放A现行值的寄存器；（2）利用AVALUE[B]和AVALUE[C]，确定出B和C现行值存放位置B`和C`，如果其现行值在寄存器中，则把寄存器取作B`和C`；（3）如果B`≠R，则生成目标代码：

LDR，B`OPR,C`

否则生成目标代码：OPR，C`,如果B`或C`为R，则删除AVALUE[B]或AVALUE[C]中的R。（4）令AVALUE[A]={R}，并令RVALUE[R]={A}，以表示变量A的现行值只在R中并且R中的值只代表A的现行值；（5）如B或C的现行值在基本块中不再被引用，它们也不是基本块出口之后的活跃变量（由四元式i上的附加信息知道），并且其现行值在某个寄存器Rk中，则删除RVALUE[Rk]中的B或C以及AVALUE[B]或

AVALUE[C]中的Rk，使该寄存器不再为B或C所占用。

14设GETREG是一个函数过程，它的参数是一个形如i:A:=BopC的四元式，每次调用GETREG(i:A:=BopC)则返回一个寄存器R，用以存放A的结果值。

对如何给出寄存器R，要用到四元式i上的待用信息，以使寄存器分配合理.

对每个四元式的代码生成都要调用函数GETREG。

GETREG分配寄存器的算法为：

①如果B的现行值在某寄存器Ri中，该寄存器只包含B的值，且为下列两种情况之一:或者B与A是同一标识符;或B在该四元式后不会再被引用，则可选取Ri作为所需的寄存器R，并转(4)。

②如果有尚未分配的寄存器，则从中选用一个Ri为所需的寄存器R，并转(4)。

③从已分配的寄存器中选取一个Ri作为所需寄存器R，其选择原则为：占用该寄存器的变量值同时在主存中，或在基本块中引用的位置最远，这样对寄存器Ri

所含的变量和变量在主存中的情况必须先做如下调整：即对RVALUE[Ri]中的每一变量M，

如果M不是A且AVALUE[M]不包含M，则需完成以下处理。

a)生成目标代码STRi,M;即把不是A的变量值由Ri中送入内存中。

b)如果M不是B，则令AVALUE[M]={M}，否则，令AVALUE[M]={M,Ri}。

c)删除RVALUE[Ri]中的M。

④给出R，返回。15PL/0编译程序的目标代码结构和代码生成

目标代码类pcode是一种假想栈式计算机的汇编语言。指令格式：flaf 功能码l 层次差（标识符引用层减去定义层）a 根据不同的指令有所区别目标指令见下页见P23页16指令功能表17代码生成代码生成是由过程GEN完成。P417GEN有3个参数，分别代表目标代码的功能码，层差和位移量。例如

gen(opr,0,16);从命令行读取值到栈顶

gen(sto,lev-level,adr)

将栈顶内容送到变量单元中，

lev：当前处理的过程层次

level：被引用变量或过程所在层次

CX：为目标代码code数组的下标指针18Code:array[0..cxmax]ofinstruction;p414fct=(lit,opr,lod,sto,cal,int,jmp,jpc)P413Instruction=packecrecordP413f:fct;l:0..levmax

a:0..amax;end;19CODE为一维数组，数组元素为记录型数据。每一个记录就是一条目标指令。CX为指令的指针，由0开始顺序增加。实际上目标代码的顺序是内层过程的排在前边，主程序的目标代码在最后。下面我们给出一个PL/0源程序和对应的目标程序的清单。20

consta=10;

varb,c;

procedurep;

begin

c:=b+a;

end;

begin

read(b);

whileb#0do

begin

callp;

write(2*c);

read(b);

end

end.

(0)jmp08转向主程序入口(1)jmp02转向过程p入口(2)int03过程p入口,为过程p开辟空间(3)lod13取变量b的值到栈顶(4)lit010取常数10到栈顶(5)opr02次栈顶与栈顶相加(6)sto14栈顶值送变量c中(7)opr00退栈并返回调用点(16)(8)

int05主程序入口开辟5个栈空间(9)opr016从命令行读入值置于栈顶(10)sto03将栈顶值存入变量b中(11)lod03将变量b的值取至栈顶(12)lit00将常数值0进栈(13)opr09次栈顶与栈顶是否不等(14)jpc024

等时转(24)（条件不满足转）(15)cal02调用过程p(16)lit02常数值2进栈(17)lod

04将变量c的值取至栈顶(18)opr04次栈顶与栈顶相乘(2*c)(19)opr014栈顶值输出至屏幕(20)opr015换行(21)opr016从命令行读取值到栈顶(22)sto

03栈顶值送变量b中(23)jmp011无条件转到循环入口(11)(24)opr00结束退栈21PL/0编译程序的目标代码生成是由GEN过程完成的，当语法分析正确则调用目标代码生成过程以生成与PL/0语句等价功能的目标代码，直到编译正常结束。除了过程说明部分外，变量和常量的说明都不产生目标代码。在block入口处生成一条(jmp,0,0)指令，作为过程体入口指令，该指令的第3区域的'0'需分析到过程体入口时才返填。对分程序体入口的处理（见程序文本P424页block的过程体）

begin(*block*)

dx:=3;

tx0:=tx;（*保留当前table表指针值,实际为过程名在table表中的位置*）

table[tx].adr:=cx;（*保留当前code指针值到过程名的adr域*）

gen(jmp,0,0);

22录过程在code的入口到table中的adr域如下表所示：

（*生成转向过程体入口的指令，该指令的地址为cx已保留在过程名的adr域，真正的过程体入口地址，等生成过程体入口的指令时，将过程体入口返填（jmp,0,0）的第3区域，同时填到table[tx0].adr中*)tx0tx0:=tx;table[tx].adr:=cx;tx23table表格管理

code[table[tx0].adr].a:=cx;tx0tx24过程体入口时的处理

table表格管理

code[table[tx0].adr].a:=cx;（cx为过程入口地址，填写在code中）

withtable[tx0]do

begin

adr:=cx;（table[tx0].adr=cx）

size:=dx;（table[tx0].size＝dx）

end;

请特别注意dx、tx、cx的作用和如何处理信息之间的连接关系。25

CASEWHILESYM: CX1=CX;GetSym();//保留L1的地址

CONDITION(SymSetAdd(DOSYM,FSYS),LEV,TX);//生成B的代码

CX2=CX;GEN(JPC,0,0);//条件跳转,L2待定,

if(SYM==DOSYM)GetSym(); elseError(18); STATEMENT(FSYS,LEV,TX);//生成S的代码

GEN(JMP,0,CX1)；//无条件跳转,转到L1 CODE[CX2].A=CX;//回填L2 break;switch(SYM){……WhileBDoSBFalseS转L1L1：L2:CX1CX226解释程序还定义了4个寄存器。

(1)I：指令寄存器。存放着当前正在解释的一条目标指令。

(2)P：程序地址寄存器。指向下一条要执行的目标程序的地址(相当目标程序CODE数组的下标)。

(3