编译原理Ch11

第十一章 目标代码生成

一、目标代码生成器

1.任务

• 把分析、翻译、优化后的中间代码变换成目标代码

2.输入

• 源程序的中间表示，以及符号表中的信息
• 类型检查（已经在中间代码生成完成）

3.输出

(1)绝对指令代码

• 能够立即执行的机器语言代码，所有地址已经定位

(2)可重新定位指令代码

• 待装配的机器语言模块，执行时，由连接装配程序把它们和某些运行程序连接起来，转换成能执行的机器语言代码

(3)汇编语言代码

• 需要经过汇编程序转换成可执行的机器语言代码

4.目标代码生成需要考虑的问题

• 如何充分利用计算机的指令系统的特点
  
• 如何充分利用计算机的寄存器，减少目标代码中访问贮存单元的次数
  • 在寄存器分配期间，为程序的某一点选择驻留在寄存器中的一组变量
  • 在随后的寄存器指派阶段，挑出变量将要驻留的具体寄存器

5.计算机模型

• 具有多个通用寄存器，可用作累加器和变址器
• 运算必须在某个寄存器中进行
• 含有四种类型的指令形式
  
• op可以是常见的二目运算符：加减乘除
• 也可以是一目运算符：op(M)→Ri
  

6.最简单的代码生成

7.带寄存器分配优化的代码生成

• 以基本块为单位生成目标代码
  • 依次把四元式的中间代码变换成目标代码
  • 在基本块的范围内考虑如何充分利用寄存器
  • 进入基本块时，所有寄存器空闲
  • 离开基本块时，把存在寄存器中的现行的值存回主存中，释放所有寄存器
  • 不特别说明，所有说明变量在基本块出口之后均为非活跃变量
• 在一个基本块的范围内考虑充分利用寄存器
  • 要做到：
  • 尽可能留：在生成计算某变量值的目标代码时，尽可能让该变量保留在寄存器中
  • 尽可能用：后续的目标代码尽可能利用变量在寄存器中的值，而不访问主存
  • 及时腾空：在离开基本块时，把存在寄存器中的现行的值放到主存中
  • 要知道：
  • 四元式指令：每条指令中各变量在将来会被使用的情况
  • 变量：每个变量现行值的存放位置
  • 寄存器：每个寄存器当前的使用情况

二、待用信息和活跃信息

1.待用信息

• 如果在一个基本块内，四元式i对A定值，四元式j要引用A值，而从i到j之间没有其他对A的定值，我们称j是四元式i的变量A的待用信息，即下一个引用点
  • i：A:=B op C……j：D:=A op E
• 变量的符号表登记项中含有记录待用信息和活跃信息的栏

2.待用信息和活跃信息的表示

• 二元组（x，x）表示变量的待用信息和活跃信息
  • 第一元：i表示待用信息，^表示非待用
  • 第二元：y表示活跃，^表示非活跃
• 待用信息和活跃信息的变化
  • (x, x)→(x, x)，用后者更新前者
    

3.待用信息和活跃信息的计算

• 正向计算每次都需要向后扫描，效率低，所以从后向前计算
• 算法：
  

二、变量地址描述和寄存器描述

1.变量地址描述数组AVALUE

• 动态记录各变量现行值得存放位置
• AVALUE[A]={$R_1, R_2, A$}

2.寄存器描述数组RVALUE

• 动态记录各寄存器的使用信息
• RVALUE[R]={A, B}

3.使用

• 对于四元式A:=B
  • 如果B的现行值在某寄存器$R_i$中，则无需生成目标代码
  • 只需在RVALUE(Ri)中增加A，即把Ri同时分配给B和A，并把AVALUE(A)改为Ri

三、代码生成算法

1.具体算法

2.寄存器分配算法

• 寄存器分配：GETREG(i：A:=B op C)返回一个用于存放A的值的寄存器
  • 尽可能用B独占的寄存器
  • 尽可能用空闲寄存器
  • 抢占非空闲寄存器
• 算法：
  

3.生成存数指令算法

4.为基本块生成代码示例

点击跳转