三地址码(3AC/TAC)是什么

MartinLwx 收录于类别 Program-Analysis

2025-02-18 2025-02-21 约 961 字预计阅读 2 分钟

信息

进一步阅读

从 Basic Block 到 Control Flow graph

什么是三地址码

三地址码（Three-Address Code，也简记为 3AC/TAC）是一种程序的中间表示（Intermediate Representation，IR），通常用在编译器、程序分析当中。顾名思义，三地址码的每一条指令最多只有三个“地址”，这里的“地址”包括变量、常量。常见的形式包括下面几种 ¹

// assignment with binary operator(bop)
x = y bop z

// assignment with binary operator(uop)
x = uop y

// copy
x = y

// unconditional jump
goto label

// conditional jump 1
if x goto L

// conditional jump 2
// rop = relation operator
// e.g. >, <, >=, …
if x rop y goto L

// procedure call
call p

// return
return val

三地址码实现（四元组）

根据三地址码的特点，可以用一个四元组存储三地址码的指令：(destination, operator, operand1, operand2)，那么代码就可以表示为一个四元组数组，或者是四元组链表²

四元组链表的好处是不用提前计算要开辟多大的空间存储三地址码。如果是四元组数组的话，一开始数组开辟过大会导致内存浪费，开辟得太小又会引入额外的性能开销 ²

Practical Example. LLVM IR

前面本文提到的三地址码的常见形式是抽象的表示，具体实现的时候写法上会有所差异。以 LLVM IR 为例，它就是典型的三地址码，比如对于下面这一段 C/C++ 程序（main.cpp）

c++

int main() {
    int sum = 0;
    for (int i = 0; i < 10; i++) {
        sum += i;
    }
    return 0;
}

用 clang 导出 LLVM IR，命令如下

$ clang -S -emit-llvm main.cpp

在同目录下可以看到 main.ll 文件。我删去了部分代码并加上了注释来帮助你理解，内容如下

llvm

define noundef i32 @main() #0 {
  %1 = alloca i32
  %2 = alloca i32  ; %2 is sum
  %3 = alloca i32  ; %3 is i
  store i32 0, ptr %1
  store i32 0, ptr %2       ; sum = 0
  store i32 0, ptr %3       ; i = 0
  br label %4               ; jump to %4

4:                                                ; preds = %11, %0
  %5 = load i32, ptr %3           ; load i
  %6 = icmp slt i32 %5, 10        ; %6 = check if i < 10
  br i1 %6, label %7, label %14   ; conditional jump based on if %6 is true

7:                                                ; preds = %4
  %8 = load i32, ptr %3     ; i
  %9 = load i32, ptr %2     ; sum
  %10 = add nsw i32 %9, %8  ; temp = sum + i
  store i32 %10, ptr %2     ; sum = temp
  br label %11              ; jump to %11

11:                                               ; preds = %7
  %12 = load i32, ptr %3     ; i
  %13 = add nsw i32 %12, 1   ; temp = i++
  store i32 %13, ptr %3      ; i = temp
  br label %4                ; jump to %4

14:                                               ; preds = %4
  ret i32 0                  ; return 0
}

总结

三地址码很好理解，作为程序 IR 的一种，它是很多程序分析工具的基础 ¹（比如我最近正在看的 ArkAnalyzer³）。三地址码和 AST 相比，它的优势是：更加紧凑，并且带有控制流的信息（你能够通过阅读代码知道程序的运行逻辑），而且通常是编程语言无关的。这个给后续的程序分析和处理带来了很大的方便

Refs

南京大学.软件分析.02.Intermediate Representation ↩︎ ↩︎
Engineering a Compiler 5.3.3 Representing Linear Codes ↩︎ ↩︎
Chen, Haonan, et al. “ArkAnalyzer: The Static Analysis Framework for OpenHarmony.” arXiv preprint arXiv:2501.05798 (2025). ↩︎