Water's blog

深色模式

中间代码生成 ​

中间代码表示 ​

AST表示

形式

  • 多种中间表示(Intermediate Representations, IRs), 不同层次
  • 抽象语法树
  • 三地址代码

好处

  • 可复用

为新的机器建编译器, 只需要做中间代码到新的目标代码的翻译器(前端独立)

  • 高层次的优化

优化与源语言和目标机器都无关

三地址代码 ​

目标

  • 接近大多数目标机器的执行模型(机器码)
  • 支持大多数目标及其提供的数据类型和操作
  • 提供有限度的, 高于机器码的抽象表达能力, 更容易表达出大多数(命令式)高级语言的特性

特征

  • 以指令为单位
  • 每条指令只有有限数量的运算分量(通常<=3)
  • 支持基本数据类型及其运算
  • 支持复合数据类型(数组, 结构体等)及其操作
  • 支持函数

每条指令右侧最多有一个运算符

一般情况可写成x = y op z的形式

允许的运算分量

  • 变量
  • 常量
  • 临时变量

指令集合 ​

指令集合

指令集合2

eg:

c
do {
    i = i + 1;
} while (a[i] < v);

<=>

L:
t1 = i + 1
i = t1
t2 = i * 8
t3 = a[t2]
if t3 < v goto L

四元式表示方法 ​

可以用四元式/三元式/间接三元式/静态单赋值来表示三地址指令

四元式

  • 格式: (op, arg1, arg2, result)
  • op: 操作符的内部编码
  • arg1, arg2, result是地址

eg: x = y + z

(+, y, z, x)
  • 单目运算不使用arg2
  • param运算不使用arg2和result
  • 条件转移/非条件转移将目标标号放在result字段

eg: a = b * -c + b * -c

(1) (-, c, , t1)
(2) (*, b, t1, t2)
(3) (-, c, , t3)
(4) (*, b, t3, t4)
(5) (+, t2, t4, t5)
(6) (=, t5, , a)

数组操作的四元式表示 ​

  • 读: x = y[i] => (=[] , y, i, x)
  • 写: y[i] = x => ([]= , x, i, y)

静态单赋值(SSA) ​

一种特殊的三地址代码, 其所有变量在代码中只被赋值一次

基本构造思路

  • 为每个变量维护一个计数器
  • 从函数入口开始遍历函数体
  • 遇到变量赋值时, 为其生成新名字, 并替换

通常只针对函数内的变量计算SSA

SSA对分支的处理

SSA对循环的处理

SSA的作用:

  • 简化数据流分析和某些优化
  • 使得定义-使用链易于计算

控制流 ​

生成的代码执行时跳转到两个标号之一:

  • 条件为真, B.true
  • 条件为假, B.false

B.true和B.false是两个继承属性, 根据B所在上下文指向不同位置

  • 如果B是if语句, 分别指向then和else分支, 如果没有else分支, 则B.false指向if语句的下一条指令
  • 如果B是while语句, 分别指向循环体的开头和循环出口处

回填 ​

基本思想:

  • 遇到跳转目标未知时, 先生成跳转指令胚

goto __/ if ... goto __

  • 将指令胚想父结点传递
  • 翻译过程中, 若遇到某条指令是跳转目标, 记录其索引
  • 当父结点收集齐跳转指令胚和跳转目标时, 将索引填入指令胚中.

回填需要维护一些列表:

  • truelist: 存储true分支的跳转指令索引
  • falselist: 存储false分支的跳转指令索引
  • nextlist: 存储下一条指令的跳转指令索引

eg:

101: if a < b goto __ 102: goto __

存储为

  • truelist = [101]
  • falselist = [102]

当收集到跳转目标后, 回填 101: if a < b goto 103

102: goto 104

辅助函数: backpatch(p, i), 将i作为跳转目标插入到p的所有指令中.

回填

Break, Continue的处理

跟踪外围循环语句S, 生成一个跳转指令胚, 将这个指令胚的索引加入到S的nextlist中.

Copyright © 2024-present Water