三地址码 | Codeboy's Blog

形式陈述

三地址码（three-address code, TAC）是一类编译器中间表示。其核心指令通常形如

x:=y\mathbin{\mathrm{op}}z,\qquad x:=\mathrm{op}\ y,\qquad x:=y,\qquad \operatorname{goto}L,\qquad \operatorname{if}\ x\ \operatorname{goto}L,

每条计算指令至多显式写一个结果位置和两个输入位置，“地址”可以是变量、临时量、常量或抽象存储位置，并不要求是真实机器地址。调用、数组寻址、字段访问和返回常以扩展指令存在，但仍把嵌套计算拆成可命名步骤。

标签和跳转把线性指令序列分割成基本块；块内除末尾外顺序执行，块末产生控制流图边。TAC 的语义必须说明操作数求值、整数宽度、异常、内存与调用效果。指令“ $t:=a+b$ ”只有在这些约定固定后才是一条可比较的状态转移，而不仅是一行易读的伪代码。

实现可把同一 TAC 存成 quadruple $(op,arg_1,arg_2,result)$ ，或让结果由指令编号隐式确定的 triple。两者只是编码差异：移动或复制指令时，triple 的位置引用需要重定向，quadruple 的显式临时名需要维护定义表。数据结构是否含三个字段与“三地址”概念无关，合法操作与状态转移才是语义接口。

直觉

三地址码把一口气完成的表达式拆成流水线上的小工序。源式 $(a+b)\times(c-d)$ 可拆为

t_1:=a+b;\quad t_2:=c-d;\quad t_3:=t_1\times t_2.

中间结果有名字后，公共子表达式消除、常量传播和活跃性分析可以直接谈论哪次定义供哪次使用。复杂控制结构也被还原为标签和跳转，使路径而非语法缩进成为分析对象。

这种拆分没有规定每个源变量只能赋值一次。临时量可以复用，循环计数器也可反复更新；因此 TAC 不等于静态单赋值形式。SSA 常建立在类似 TAC 的指令集之上，再通过版本化名字与合流操作施加额外不变量。把二者混称会掩盖 SSA 构造和消解真正完成的工作。

例子与边界

对 “x:=f(a)+g(b*c)” 且求值顺序固定为从左到右，可得

t_1:=\operatorname{call}f(a);\quad t_2:=b\times c;\quad t_3:=\operatorname{call}g(t_2);\quad x:=t_1+t_3.

若 $f$ 或 $g$ 有副作用，先算 $b\times c$ 、甚至交换两次调用，都可能改变结果；TAC 的拆分不能凭借“表达式数学上相同”任意重排。手算时令初始 $a=2,b=3,c=4$ ， $f$ 把全局计数器加一并返回 $a$ ， $g$ 读取计数器再加到参数上，则不同调用顺序会产生不同 $t_3$ ，清楚展示语义边界。

“三地址”也不是严格要求每条指令文本出现三个词。一元负号只有一个输入，复制没有运算，条件跳转可能同时写比较两数。真正约束是把复杂运算分解为有限元的简单原语。相反，一条 “x:=sort(a)” 虽表面只有两个名字，却把任意复杂计算藏进原语；它是否属于所讨论 TAC 取决于指令集规范，而不是计数字符串中的操作数。

内存操作尤其需要分开。 $t:=\operatorname{load}(p)$ 读取当前存储， $\operatorname{store}(p,v)$ 改变存储；不能像纯临时量赋值那样仅靠名字版本判断依赖。未知别名使两个不同指针可能指向同一单元，TAC 本身不会消除这种不确定性。

推论与应用

TAC 的细粒度让局部优化能以短窗口描述。若连续出现 $t:=2\times3$ 与 $x:=t+4$ ，在无陷阱的整数语义下可折叠为 $x:=10$ ；若 $t$ 之后还有使用，则不能简单删除其定义。基本块内可用顺序扫描，跨块则必须结合 CFG 的到达定义与路径条件。

后端可把一条 TAC 指令扩成多条机器指令，也可把数条融合成一个寻址模式。这里没有一对一对应：目标机器可能只允许寄存器—寄存器运算，常量范围也有限。TAC 提供的是清楚的中间语义接口；指令选择仍需单独证明扩展或融合保持相同观察。

过程间 TAC 还必须决定调用如何表示。若 call 只写一个返回临时量，却省略可能读取和写入的内存、异常后继与被破坏状态，局部公共子表达式消除可能错误跨过调用复用旧 load。显式 effect token、调用摘要或保守 clobber 都可解决接口问题；单纯增加第四个“地址”字段并不能。

参考资料

Alfred V. Aho, Monica S. Lam, Ravi Sethi, and Jeffrey D. Ullman, Compilers: Principles, Techniques, and Tools, 2nd ed., Pearson, 2007, §6.2.
Steven S. Muchnick, Advanced Compiler Design and Implementation, Morgan Kaufmann, 1997, §§4.2–4.4.
Keith D. Cooper and Linda Torczon, Engineering a Compiler, 3rd ed., Morgan Kaufmann, 2023, Chapter 4.

形式陈述 ​

反向链接

形式陈述