三地址代码

三地址代码中，一条指令的右侧最多有一个运算符。也就是说，不允许出现组合的运算符。

形如下面的源语言表达式： x + y * z
要翻译为如下的三地址指令序列
t1 = y * z
t2 = x + t1
其中t1和t2是编译器产生的临时名字。因为三地址代码拆分了多运算符算术表达式以及流程控制语句的嵌套结构，所以适用于目标代码的生成和优化。

三地址代码是一抽象语法树或者DAG的线性表示形式。三地址代码中的临时名字对应于图中的内部节点。

地址和指令

三地址代码基于两个基本概念：地址和指令。

• 地址可以具有如下形式之一：

1. 名字。在实现中源程序名字被替换为符号表条目的指针。关于该名字的所有信息均存放在该条目中。
2. 常量。在实践中编译器往往要处理不同类型的变量和常量。
3. 编译器生成的临时变量。当为变量分配寄存器的时候，我们可以尽可能合并这些临时变量。

• 常见的三地址指令形式：

1. 形如x = y op z的赋值指令。(op是一个双目运算符或逻辑运算符，x、y、z是地址)
2. 形如x = op y的赋值指令。(op是一个单目运算符)
3. 形如x = y op z的赋值指令。(op是一个双目运算符或逻辑运算符，x、y、z是地址)
4. 形如x = y的指令。
5. 形如goto L的无条件转移指令。（下一步执行标号为L的三地址指令）
6. 形如if x goto L或者if False x goto L的条件转移指令。(op是一个双目运算符或逻辑运算符，x、y、z是地址)
7. 形如if x relop y goto L的条件转移指令。

• 过程调用通过下列指令实现：

1. param x进行参数传递。
2. call p, n和y = call p, n分别进行过程调用和函数调用。
3. return y是返回指令。

//示例  
param x1
param x2
...
param xn
call p, n  

• 带下标的复制指令：

1. x = y[i]把距离位置y处i个内存单元的位置中存放的值赋给x。
2. x[i] = y将距离位置x处i个内存单元位置中的内容设为y。

• 地址及指针赋值指令：

1. x = &y取地址。
2. x = *y解指针。
3. *x = y将y的内容赋给x指向的目标的内容。

四元式表示

这些三地址指令在某个数据结构中的表示/描述方法，有四元式、三元式、间接三元式这些。

一个四元式(quadruple)有四个字段op、arg1、arg2、result。op字段存放运算符的编码。

• 一些特例：

1. 单目运算符例如x = minus y和赋值指令例如x = y不使用arg2。
2. 像param这样的，不需要arg2和result。
3. 条件或非条件转移将目标标号放入result字段。

• 示例：

a = b * -c的四元式表示
|op|arg1|arg2|result| |-|-|-|-| |minus|c||t1| |*|b|t1|t2| |*|t2||a|

三元式表示

一个三元式(triple)只有三个字段，分别称为op、arg1、arg2。

CRE：三元式使用它的位置来表示它的结果，而不是临时变量。

• 示例：

a = b * -c的三元式表示
|op|arg1|arg2| |-|-|-| |minus|c|| |*|b|(0)| |=|a|(1)|

静态单赋值

静态单赋值形式(SSA)是另一种中间表示形式，它利于实现某些类型的代码优化。SSA和三地址码的区别主要体现在两个方面。

CRE：特点是所有变量都只能被赋值一次，去除了动态赋值的不确定性。

一是SSA中所有的赋值都是针对具有不同名字变量的，这也是“静态单赋值”这个名字的由来。
二是SSA使用一种称为φ函数的表示规则将同一个变量在不同流程分支的定值合并起来。

if(flag) x1 = -1;
else x2 = 1;
x3 = φ(x1, x2);

（END）