跳转至

1 中间语言

中间表示 IR，Intermediate Representation

LLVM，Low Level Virtual Mechine

后缀表示（逆波兰式）

比如 ( 8 - 5 ) + 2 的后缀表示是 8 5 - 2 +，不需要括号，前提：算符无二义

优点：便于计算机处理表达式，如求值，代码生成等

表达能力：可以拓广到表示赋值语句和控制语句，适合底层实现；但是很难用栈来描述控制语句的计算

前缀表示（波兰式）

一种逻辑、算数和代数的表示方法，如 op (a, b, c)，用于简化命题逻辑，适合上层表达

图形表示

  • 语法树是一种图形化的中间表示
  • 有向无环图 DAG 也是一种中间表示

image-20221127172124558

构造赋值语句语法树的语法制导定义

mkUNode (op, child) 是构造一元运算节点的函数

这里用的是二义文法，比如 + 和 * 没有在文法中规定优先级，但是看成和平凡情况一样

产生式 语义规则
S → id = E S.nptr = mkNode ( 'assign', mkLeaf (id, id.entry), E.nptr )
E → E~1~ + E~2~ E.nptr = mkNode ( '+', E~1~.nptr, E~2~.nptr )
E → E~1~ * E~2~ E.nptr = mkNode ( '*', E~1~.nptr, E~2~.nptr )
E → －E~1~ E.nptr = mkUNode ( 'uminus', E~1~.nptr )
E → (E~1~) E.nptr = E~1~.nptr
F → id E.nptr = mkLeaf (id, id.entry)

三地址代码

一般形式：x=y\ \textbf{op}\ z，最多 1 个算符，最多 3 个计算分量（均为运算对象的地址）

例如，表达式 x+y*z 翻译成三地址语句序列是

  • t_1=y*z
  • t_2=x+t_1

三地址代码是语法树或者 DAG 的一种线性表示

  • 对语法树进行后序遍历产生后缀式，后缀式可以容易地转化成三地址代码
  • 编译器实现中会建立后序线索树，方便代码生成、求值等

image-20221127192642299

常用的三地址语句

  • 赋值语句 x=y\textbf{ op }z\quad\quad x=\textbf{op }y
  • 复写语句 x=y
  • 无条件转移 \textbf{goto}\ L
  • 条件转移 \textbf{if }x\textbf{ relop }y\ \textbf{goto}\ L
  • 过程调用 \textbf{param}\ x（参数设置）\textbf{call }p,n（调用含 n 个参数的子过程 p）

过程调用的典型使用是

param x1
param x2
...
param xn
call p, n

这些指令是过程调用 p(x_1,...,x_n) 的中间代码

  • 过程返回 \textbf{return }y
  • 索引赋值 x=y[i]\quad x[i]=y
  • 地址和指针赋值 x=\&y\quad x=*y\quad *x=y

静态单赋值

static single-assignment, SSA

  • 一种便于某些代码优化的中间表示
  • 和三地址代码有一些区别：所有赋值指令都是对不同名字的变量的赋值

image-20221127194641481

  • 新问题：有一些变量可能在不同的控制流路径上都被定值，如：
if (flag) x = -1;
else x = 1;
y = x * a;

改成：（Phi 算子：汇合对多个可能定值的引用）

if (flag) x1 = -1;
else x2 = 1;
x3 = φ(x1, x2); // 由flag的值决定用x1还是x2
y = x3 * a;

例子

prod = 0;
i = 1;
do {
    prod = prod + a[i];
    i = i + 1;
} while (i <= 20);

三地址码：

1  prod = 0
2  i = 1
3  t1 = 4 * i
4  t2 = a[t1]    // 元素地址要转换成按字节寻址
5  t3 = prod + t2
6  prod = t3    // 可以重复定值，上面的Phi只是用于面对在多个控制流中
7  t4 = i + 1
8  i = t7
9  if i <= 20 goto 3.
本文阅读量