第127集：三地址码

核心知识点讲解

三地址码形式

三地址码（Three-Address Code，简称 TAC）是一种线性的中间表示，每条指令最多有三个操作数，通常是形如 x = y op z 的形式。它是编译器中最常用的中间表示之一，特别适合进行代码优化和目标代码生成。

三地址码的基本形式：

二元操作：x = y op z
- 其中 op 是二元运算符（+、-、*、/ 等）
- x、y、z 是变量、常量或临时变量
一元操作：x = op y
- 其中 op 是一元运算符（-、! 等）
- x、y 是变量、常量或临时变量
赋值操作：x = y
- 将 y 的值赋给 x
跳转操作：
- 无条件跳转：goto L
- 条件跳转：if x goto L 或 if x op y goto L
函数调用：
- 函数调用：call f, n
- 参数传递：param x
- 返回语句：return x
地址操作：
- 取地址：x = &y
- 间接寻址：x = *y 或 *x = y

指令类型

三地址码的指令类型主要包括：

1. 算术指令

加法：x = y + z
减法：x = y - z
乘法：x = y * z
除法：x = y / z
取模：x = y % z

2. 逻辑指令

与：x = y && z
或：x = y || z
非：x = !y
相等：x = y == z
不等：x = y != z
大于：x = y > z
小于：x = y < z
大于等于：x = y >= z
小于等于：x = y <= z

3. 赋值指令

直接赋值：x = y
复合赋值：x = x + y（可以优化为 x += y）

4. 控制流指令

无条件跳转：goto L
条件跳转：if x goto L
比较跳转：if x < y goto L
标签：L:（表示跳转目标）

5. 函数相关指令

参数传递：param x
函数调用：call f, n（n 是参数个数）
返回值：return x
函数入口：function f
函数出口：end function

6. 内存访问指令

取地址：x = &y
间接寻址：x = *y
存储：*x = y
数组访问：x = y[i]
数组存储：y[i] = x

7. 特殊指令

空指令：nop
注释：# comment
调试信息：line n（表示对应源代码的行号）

示例

基本示例

对于算术表达式 a + b * c，生成的三地址码如下：

t1 = b * c
t2 = a + t1

控制流示例

对于 if-else 语句：

if (x > y) {
    z = x;
} else {
    z = y;
}

生成的三地址码如下：

if x > y goto L1
z = y
goto L2
L1:
z = x
L2:

循环示例

对于 while 循环：

while (x < 10) {
    x = x + 1;
}

生成的三地址码如下：

L1:
if x >= 10 goto L2
x = x + 1
goto L1
L2:

函数示例

对于函数调用：

int add(int a, int b) {
    return a + b;
}

int main() {
    int x = 1;
    int y = 2;
    int z = add(x, y);
    return 0;
}

生成的三地址码如下：

function add(a, b)
    t1 = a + b
    return t1
end function

function main()
    x = 1
    y = 2
    param x
    param y
    call add, 2
    z = t2  # 假设 call 指令将返回值放在 t2 中
    return 0
end function

表示方法

三地址码可以用多种方式表示，常见的表示方法包括：

1. 四元式表示

四元式（Quadruple）是三地址码的一种表示方法，使用一个四元组 (op, arg1, arg2, result) 来表示一条指令。

示例：

op	arg1	arg2	result
*	b	c	t1
+	a	t1	t2

2. 三元式表示

三元式（Triple）是三地址码的另一种表示方法，使用指令的位置来引用结果，使用一个三元组 (op, arg1, arg2) 来表示一条指令。

示例：

位置	op	arg1	arg2
(1)	*	b	c
(2)	+	a	(1)

3. 间接三元式表示

间接三元式（Indirect Triple）是三元式的一种改进形式，它使用一个指针数组来引用三元式，便于进行代码优化。

示例：

三元式表：

位置	op	arg1	arg2
(1)	*	b	c
(2)	+	a	(1)

指针数组：[1, 2]

4. 记录表示

在内存中，三地址码通常使用记录结构来表示，每个记录包含操作码和操作数字段。

示例（C 语言结构体）：

typedef enum {
    ADD, SUB, MUL, DIV, ASSIGN, GOTO, IF_GOTO, PARAM, CALL, RETURN
} OpCode;

typedef struct {
    OpCode op;
    union {
        struct { char *arg1, *arg2, *result; } binop;
        struct { char *arg, *result; } unop;
        struct { char *target; } jump;
        struct { char *cond, *target; } if_jump;
        struct { char *func, *nargs; } call;
        struct { char *value; } ret;
    } data;
} TACInstruction;

临时变量管理

在生成三地址码时，需要大量使用临时变量来存储中间计算结果。临时变量的管理是三地址码生成的重要部分。

临时变量的命名

临时变量通常使用前缀加数字的形式命名，例如：

t1, t2, t3, ...
temp1, temp2, temp3, ...

临时变量的分配

临时变量的分配策略：

顺序分配：
- 从 t1 开始，每次需要临时变量时递增编号
- 简单直接，但可能会使用过多的临时变量
重用策略：
- 当临时变量不再被使用时，重用其编号
- 需要进行活跃变量分析
- 可以减少临时变量的数量

临时变量的优化

通过代码优化，可以减少临时变量的使用：

公共子表达式消除：
- 避免重复计算相同的表达式
- 减少临时变量的产生
复写传播：
- 当 x = y 时，后续使用 x 的地方可以直接使用 y
- 减少临时变量的使用
死代码消除：
- 删除计算结果不被使用的代码
- 减少临时变量的产生

实用案例分析

三地址码生成

表达式的三地址码生成

生成表达式的三地址码是编译器前端的重要任务之一。下面是一个简单的表达式三地址码生成器的实现：

算法：

递归遍历 AST：
- 对于二元表达式，先递归处理左右操作数
- 生成二元操作指令，使用临时变量存储结果
- 返回临时变量名
处理常量和变量：
- 对于常量，直接返回其值
- 对于变量，直接返回其名称

示例代码（Python）：

class TACGenerator:
    def __init__(self):
        self.temp_count = 0
        self.instructions = []
    
    def new_temp(self):
        temp = f't{self.temp_count}'
        self.temp_count += 1
        return temp
    
    def generate(self, ast):
        if ast['type'] == 'BinaryOp':
            left = self.generate(ast['left'])
            right = self.generate(ast['right'])
            temp = self.new_temp()
            self.instructions.append(f'{temp} = {left} {ast["op"]} {right}')
            return temp
        elif ast['type'] == 'UnaryOp':
            operand = self.generate(ast['operand'])
            temp = self.new_temp()
            self.instructions.append(f'{temp} = {ast["op"]}{operand}')
            return temp
        elif ast['type'] == 'Identifier':
            return ast['name']
        elif ast['type'] == 'Number':
            return str(ast['value'])
        else:
            return None
    
    def __str__(self):
        return '\n'.join(self.instructions)

# 示例 AST
ast = {
    'type': 'BinaryOp',
    'op': '+',
    'left': {'type': 'Identifier', 'name': 'a'},
    'right': {
        'type': 'BinaryOp',
        'op': '*',
        'left': {'type': 'Identifier', 'name': 'b'},
        'right': {'type': 'Identifier', 'name': 'c'}
    }
}

# 生成三地址码
gen = TACGenerator()
gen.generate(ast)
print(gen)

输出：

t0 = b * c
t1 = a + t0

语句的三地址码生成

生成语句的三地址码需要处理控制流，下面是一个简单的语句三地址码生成器的实现：

算法：

处理赋值语句：
- 生成表达式的三地址码
- 生成赋值指令
处理 if-else 语句：
- 生成条件表达式的三地址码
- 生成条件跳转指令
- 生成 then 部分的三地址码
- 生成无条件跳转指令跳过 else 部分
- 生成 else 部分的三地址码
处理 while 语句：
- 生成循环开始标签
- 生成条件表达式的三地址码
- 生成条件跳转指令跳出循环
- 生成循环体的三地址码
- 生成无条件跳转指令回到循环开始
- 生成循环结束标签

示例代码（Python）：

class TACGenerator:
    def __init__(self):
        self.temp_count = 0
        self.label_count = 0
        self.instructions = []
    
    def new_temp(self):
        temp = f't{self.temp_count}'
        self.temp_count += 1
        return temp
    
    def new_label(self):
        label = f'L{self.label_count}'
        self.label_count += 1
        return label
    
    def generate_expr(self, ast):
        # 表达式生成代码（略）
        pass
    
    def generate_stmt(self, ast):
        if ast['type'] == 'Assignment':
            expr = self.generate_expr(ast['expr'])
            self.instructions.append(f'{ast["var"]} = {expr}')
        elif ast['type'] == 'IfStmt':
            cond = self.generate_expr(ast['cond'])
            then_label = self.new_label()
            else_label = self.new_label()
            end_label = self.new_label()
            
            self.instructions.append(f'if {cond} goto {then_label}')
            self.instructions.append(f'goto {else_label}')
            self.instructions.append(f'{then_label}:')
            self.generate_stmt(ast['then_stmt'])
            self.instructions.append(f'goto {end_label}')
            self.instructions.append(f'{else_label}:')
            if 'else_stmt' in ast:
                self.generate_stmt(ast['else_stmt'])
            self.instructions.append(f'{end_label}:')
        elif ast['type'] == 'WhileStmt':
            start_label = self.new_label()
            end_label = self.new_label()
            
            self.instructions.append(f'{start_label}:')
            cond = self.generate_expr(ast['cond'])
            self.instructions.append(f'if not {cond} goto {end_label}')
            self.generate_stmt(ast['body'])
            self.instructions.append(f'goto {start_label}')
            self.instructions.append(f'{end_label}:')
    
    def __str__(self):
        return '\n'.join(self.instructions)

# 示例 AST
ast = {
    'type': 'IfStmt',
    'cond': {
        'type': 'BinaryOp',
        'op': '>',
        'left': {'type': 'Identifier', 'name': 'x'},
        'right': {'type': 'Identifier', 'name': 'y'}
    },
    'then_stmt': {
        'type': 'Assignment',
        'var': 'z',
        'expr': {'type': 'Identifier', 'name': 'x'}
    },
    'else_stmt': {
        'type': 'Assignment',
        'var': 'z',
        'expr': {'type': 'Identifier', 'name': 'y'}
    }
}

# 生成三地址码
gen = TACGenerator()
gen.generate_stmt(ast)
print(gen)

输出：

if x > y goto L0
goto L1
L0:
z = x
goto L2
L1:
z = y
L2:

三地址码优化

三地址码是代码优化的重要阶段，下面介绍几种常见的三地址码优化技术：

1. 常量折叠

常量折叠是在编译时计算常量表达式的值，减少运行时的计算开销。

优化前：

t1 = 2 + 3
t2 = x * t1
t3 = 5 * 6
t4 = y + t3

优化后：

t1 = 5
t2 = x * t1
t3 = 30
t4 = y + t3

2. 公共子表达式消除

公共子表达式消除是避免重复计算相同的表达式，减少计算开销。

优化前：

t1 = a + b
t2 = c * d
t3 = a + b
t4 = t3 + t2

优化后：

t1 = a + b
t2 = c * d
t4 = t1 + t2

3. 死代码消除

死代码消除是删除计算结果不被使用的代码，减少代码体积和运行时开销。

优化前：

t1 = a + b
if (false) {
    t2 = t1 * 2
}
t3 = c + d

优化后：

t3 = c + d

4. 复写传播

复写传播是当 x = y 时，后续使用 x 的地方可以直接使用 y，减少变量的使用。

优化前：

t1 = a + b
x = t1
t2 = x * c

优化后：

t1 = a + b
t2 = t1 * c

5. 窥孔优化

窥孔优化是在一个小的指令窗口内进行局部优化，包括：

冗余指令消除：删除不必要的指令
代数简化：简化代数表达式
跳转优化：优化跳转指令

优化前：

t1 = x + 0
t2 = x * 1
t3 = x * 0
goto L1
L1:
goto L2

优化后：

t1 = x
t2 = x
t3 = 0
goto L2

三地址码到目标代码的转换

三地址码需要转换为目标机器的代码，下面是一个简单的 x86 汇编代码生成器的实现：

算法：

指令选择：
- 为每条三地址码指令选择对应的机器指令
寄存器分配：
- 为变量分配寄存器
- 处理寄存器溢出
指令调度：
- 优化指令执行顺序
- 减少流水线停顿

示例代码（Python）：

class AsmGenerator:
    def __init__(self):
        self.instructions = []
        self.registers = ['eax', 'ebx', 'ecx', 'edx']
        self.var_map = {}  # 变量到寄存器的映射
    
    def generate(self, tac):
        for line in tac.split('\n'):
            if '=' in line:
                parts = line.split('=')
                dest = parts[0].strip()
                expr = parts[1].strip()
                
                if '+' in expr:
                    op1, op2 = expr.split('+')
                    op1 = op1.strip()
                    op2 = op2.strip()
                    self.instructions.append(f'mov {self.get_reg(op1)}, {self.registers[0]}')
                    self.instructions.append(f'add {self.get_reg(op2)}, {self.registers[0]}')
                    self.var_map[dest] = self.registers[0]
                elif '*' in expr:
                    op1, op2 = expr.split('*')
                    op1 = op1.strip()
                    op2 = op2.strip()
                    self.instructions.append(f'mov {self.get_reg(op1)}, {self.registers[0]}')
                    self.instructions.append(f'imul {self.get_reg(op2)}, {self.registers[0]}')
                    self.var_map[dest] = self.registers[0]
                else:
                    # 简单赋值
                    self.instructions.append(f'mov {expr}, {self.registers[0]}')
                    self.var_map[dest] = self.registers[0]
            elif 'goto' in line:
                label = line.split('goto')[1].strip()
                self.instructions.append(f'jmp {label}')
            elif 'if' in line:
                parts = line.split('goto')
                cond = parts[0].strip()[2:].strip()
                label = parts[1].strip()
                if '>' in cond:
                    op1, op2 = cond.split('>')
                    op1 = op1.strip()
                    op2 = op2.strip()
                    self.instructions.append(f'mov {self.get_reg(op1)}, {self.registers[0]}')
                    self.instructions.append(f'cmp {self.get_reg(op2)}, {self.registers[0]}')
                    self.instructions.append(f'jg {label}')
            elif line.endswith(':'):
                self.instructions.append(line)
    
    def get_reg(self, var):
        if var in self.var_map:
            return self.var_map[var]
        return var
    
    def __str__(self):
        return '\n'.join(self.instructions)

# 示例三地址码
tac = '''
if x > y goto L0
goto L1
L0:
z = x
goto L2
L1:
z = y
L2:
''' 

# 生成汇编代码
gen = AsmGenerator()
gen.generate(tac)
print(gen)

输出：

mov x, eax
cmp y, eax
jg L0
jmp L1
L0:
mov x, eax
L2:
jmp L2
L1:
mov y, eax
L2:

三地址码的优缺点

优点

结构简单：
- 每条指令最多有三个操作数
- 易于理解和实现
- 适合进行代码优化
表达能力强：
- 可以表示各种语言特性
- 支持控制流、数据流和副作用
- 适合各种优化技术
与机器无关：
- 独立于目标机器架构
- 可以生成不同机器的代码
- 提高编译器的可移植性
适合优化：
- 中间表示更适合进行代码优化
- 可以在三地址码上进行多轮优化
- 优化后的代码质量更高
广泛应用：
- 是编译器中最常用的中间表示之一
- 被许多编译器采用，如 GCC、LLVM
- 有丰富的工具和技术支持

缺点

临时变量：
- 需要使用大量的临时变量
- 增加了存储空间的使用
- 需要进行临时变量优化
控制流复杂：
- 跳转指令使控制流变得复杂
- 不利于某些类型的分析和优化
- 需要进行控制流分析
内存访问：
- 内存访问指令的表示可能不够直观
- 需要处理复杂的地址计算
- 不利于某些类型的内存优化
表达能力限制：
- 对于某些高级语言特性，可能需要复杂的表示
- 可能无法充分表达某些语言的语义
- 需要额外的信息来表示某些特性
实现复杂度：
- 生成和优化三地址码需要复杂的算法
- 需要处理各种边界情况
- 实现难度较高

小结

三地址码是一种线性的中间表示，每条指令最多有三个操作数，通常是形如 x = y op z 的形式。它是编译器中最常用的中间表示之一，特别适合进行代码优化和目标代码生成。

三地址码的主要特点：

结构简单：每条指令最多有三个操作数，易于理解和实现
表达能力强：可以表示各种语言特性，支持控制流、数据流和副作用
与机器无关：独立于目标机器架构，可以生成不同机器的代码
适合优化：中间表示更适合进行代码优化，可以在三地址码上进行多轮优化
广泛应用：被许多编译器采用，如 GCC、LLVM

三地址码的指令类型包括：

算术指令：加法、减法、乘法、除法等
逻辑指令：与、或、非、比较等
赋值指令：直接赋值、复合赋值等
控制流指令：跳转、条件跳转等
函数相关指令：函数调用、参数传递、返回等
内存访问指令：取地址、间接寻址、数组访问等

三地址码的表示方法包括：

四元式表示：使用四元组 (op, arg1, arg2, result) 表示
三元式表示：使用三元组 (op, arg1, arg2) 表示，使用位置引用结果
间接三元式表示：使用指针数组引用三元式，便于优化
记录表示：在内存中使用记录结构表示

三地址码是编译器中连接前端和后端的重要桥梁，它的设计和实现直接影响编译器的性能和代码质量。通过合理的三地址码设计和优化，可以生成高效、正确的目标代码。