9. 代码生成

2023-12-20 18:25:57

9. 代码生成

代码生成的核心问题；

  • 指令选择
  • 寄存器分配
  • 指令调度

指令选择

为每条中间语言语句选择恰当的目标机指令或指令序列

首先原则是保证语义的一致性

直接为中间语言语句找到语义一致的指令序列模板：

a=b+c

MOV b, R0 // 将b装入R0
ADD R0, c // 将c加到R0
MOV R0, a // 存R0的内容到a

其次要考虑所生成代码的效率

一个丰富目标指令集的机器可以为一个给定的操作提供几种实现方法

假设每条指令在操作数准备好后执行其操作的代价为1

每访问一次内存则增加代价1

上述代码执行代价为6

若假设R1和R2中已经分别包含了b和c的值，那么代码如下：

MOV R1, R0 // 将寄存器R1的内容装入寄存器R0
ADD R0, R2 // R2的内容加到R0
MOV R0, a // 存R0的内容到a

代价为4

假设R1和R2中已经包含了b和c的值，并且b的值以后不再需要

ADD R1, R2 // R2的内容加到R1
MOV R1, a // 存R1的内容到a

代价为3

寄存器分配

再分配期间，为程序的某一点选择驻留在寄存器中的一组变量

在随后的指派阶段，挑出变量将要驻留的具体寄存器，即寄存器赋值

  • 分配原则
    • 尽量让变量的值或计算结果保留在寄存器中
    • 不再被引用的变量所占用的寄存器应尽早释放
  • 局部 / 全局寄存器分配
    • 局部：在基本块范围内的寄存器分配
    • 全局：在过程范围内的寄存器分配

指令调度

  • 对指令的执行顺序进行适当的调整，从而使得整个程序得到优化的执行效果
  • RISC体系结构中，从内存中取入寄存器中的值在随后的某几个周期中是不能用的，在这几个周期中，调出不依赖于该取入值的指令来执行是很重要的
  • 调度算法可局限于基本块内，也可以是更大范围的全局指令调度；
  • 可以是静态完成指令执行顺序的调整，也可以实现动态指令调度

代码生成过程

寄存器计算机：

  • 典型的有16、32或更多个寄存器
    • 所有操作都在寄存器中进行
  • 访存都通过load / store进行
    • 内存不能直接运算

结构：

内存：存放溢出的变量

寄存器：进行运算的空间，假设有无限多个

执行引擎：指令的执行

初始时x、y等变量都放到内存中

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-FpgnaM13-1642042259498)(…/picture/74.png)]

寄存器机器只支持一种数据类型int

在代码生成的阶段，假设寄存器机器上会有无限多个寄存器

  • 因此每个声明变量和临时变量都会占用一个（虚拟）寄存器
  • 有时把虚拟寄存器分配到物理寄存器的过程称为寄存器分配

以基本块为单位的一种简单代码生成算法

  • 假设基本块中只有形成a:=b op c和a:=b的TAC语句序列
  • 假设目标语言仅含两类指令
    • MOV x, y
    • x和y是变量或寄存器，但至少有一个是寄存器，该指令的执行是将x的值传给y
    • OP x, y
    • OP是对应二元运算op的操作符，x是寄存器，y是变量或者是寄存 ，该指令是使x和y的内容做OP对应的运算，结果保存于寄存器x

指令选择是可以通过直接对应完成的，所以这个代码生成算法的核心是处理好在基本块范围内如何充分利用寄存器的问题

原则：

  • 生成某变量的目标对象值时，尽量让变量的值或计算结果保留在寄存器中
  • 尽可能引用变量在寄存器中的值
  • 在同一基本块内，后面不再被引用的变量所占用的寄存器应尽早释放
  • 当到基本块出口时，需要将变量的值存放在内存中，这样从基本块外进入的变量值都在内存中

直接采用语法树的后序遍历，暴力进行罗列

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-ENAiPauM-1642042259501)(…/picture/80.png)]

启发式算法

寄存器描述数组RVALUE，RVALUE[R]描述寄存器R当前存放哪些变量

变量描述数组AVALUE，AVALUE[a]表示变量a的值存放在哪个寄存器中（或不在任何寄存器中）

函数getreg的描述

▪ getreg功能：以 i: x := y op z 或 i: x := y为参数，返回一个伪寄存器

(1) 对于i: x := y op z

若y∈RVALUE[R]，且在语句i之后y在基本块中不再被引用，同时也不是基本块出口之后的活跃变量，则返回R；否则，返回一个新的伪寄存器R’

(2) 对于i: x := y

若y∈RVALUE[R]，则返回R；否则，返回一个新的伪寄存器R’

(1) 对每个TAC语句 i: x := y op z 或 i: x := y，依次执行下述步骤：

以i为参数，调用getreg(i)，返回一个寄存器R，作为存放x现行值的寄存器

利用AVALUE[y]和AVALUE[z]，确定出y和z现行值的存放位置

▪ 如果其现行值在寄存器中，则把寄存器取做Ry和Rz；

▪ 如果其现行值不在寄存器中，则在相应指令中仍用y和z表示

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-iPL1jnRS-1642042259502)(…/picture/75.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-uNxsbEpW-1642042259503)(…/picture/76.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-8yZ7izzL-1642042259504)(…/picture/77.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-3QzFEM3A-1642042259505)(…/picture/78.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-hvTzfKBw-1642042259506)(…/picture/79.png)]

设有以下TAC语句序列组成的基本块，假设在出口处，b和d是活跃的

语句 代码 寄存器描述 变量地址描述
t := a – b MOV a R0; sub R0 b R0包含t t在R0中(a不再在R0)
a := b MOV b R1; R0包含t R1包含a, b t在R0中 a, b在R1中
u := a – c MOV R1 b; sub R1 c R0包含t R1包含u t在R0中 u在R1中
v := t + u add R0 R1 R0包含v R1包含u u在R1中 v在R0中
d := v + u add R0 R1; MOV R0 d R0包含d d在R0中和内存中

u := a – c | MOV R1 b; sub R1 c | R0包含t R1包含u | t在R0中 u在R1中 |
| v := t + u | add R0 R1 | R0包含v R1包含u | u在R1中 v在R0中 |
| d := v + u | add R0 R1; MOV R0 d | R0包含d | d在R0中和内存中 |

都假定寄存器数目没有上限(采用简易的寄存器分配算法)

上一篇：freertos临界段保护


下一篇：A\D接口技术