适用于电子科技大学编译原理期末考试复习。

1. 目标代码

是目标机器的汇编代码或机器码，在本课程中指的是类似于汇编代码的一种形式，由一条条的指令构成目标代码。

抽象机指令格式：OP  目的操作数，源操作数。

我们要做的，就是将三地址码翻译为等价的一条条的指令。

考试时主要涉及三种指令：

• MOV：将原操作数赋值给目的操作数。

• ADD：将原操作数的值加给目的操作数。

• SUB：目的操作数减去原操作数的值。

按照寻址方式，又有如下分类：

• 寄存器型(R代表寄存器)

  OP   Ri , Rj		　/* (Ri) OP (Rj) => Ri */

• 直接地址型

  OP   Ri , M			/* (Ri) OP (M) => Ri */

• 变址型

  OP   Ri , C(Rj)		/* (Ri) OP ((Rj) + C) => Ri */

• 间接型

  OP   Ri , *Rj	   /* (Ri) OP ((Rj)) => Ri */
  OP   Ri , *M	   /* (Ri) OP ((M)) => Ri */
  OP   Ri , *C(Rj)	 /* (Ri) OP (((Rj) + C)) => Ri */
  

• 转移型

  J	X		       /* goto X */

2. 目标代码的生成方法

三地址码: x = y OP z
目标代码: MOV  Ri , yOP   Ri , zMOV  x , Ri

• ADD和SUB的目的操作数一定是寄存器。

• 条指令中都至少要有一个寄存器。

记住上面这两条就可以根据中间代码的含义，用三种指令来翻译了。

3. 循环中的寄存器分配

对于循环中频繁使用的变量，引用时需要从内存读入寄存器，修改后需要从寄存器保存回内存。

为这些频繁使用的寄存器分配固定的寄存器可以使访问内存的次数减少，进而提高效率。

但寄存器的数量是有限的，我们希望尽可能多的提高效率，就需要讨论寄存器分配的策略。

3.1 指令执行的代价

指一条指令访问内存的次数。

寄存器型    	op Ri, Rj  		  执行代价为1
直接地址型    op Ri, M		  执行代价为2
变址型      	op Ri, C(Rj)  	  执行代价为2
间接型      	op Ri, *Rj        执行代价为2op Ri, *M         执行代价为3op Ri, *C(Rj)     执行代价为3

 下面假设循环中的目标代码指令全部采用寄存器型。

3.2 被引用的变量

没有为变量 x 固定分配寄存器时，变量 x 每被引用一次，就需要访问内存一次。

• USE(x, B)：x在基本块B中的引用次数。

• USE(x, B)：在循环各基本块中的引用次数之和。

• 寄存器固定分配给 x 后，可节省USE(x, B)。

3.3 被赋值的变量

没有为变量 x 固定分配寄存器时，变量 x 每被赋值依次，就需要先从内存中读出来，运算之后保存回内存，共需访问两次内存。

• LIVE(x, B)：x在基本块B中的被赋值次数。

• LIVE(x, B)：在循环各基本块中的被赋值次数之和。

• 寄存器固定分配给 x 后，可节省2*LIVE(x, B)。

3.4 固定分配寄存器共可节省的效率