05-目标代码生成¶
重要性：⭐⭐⭐⭐ 实用度：⭐⭐⭐⭐ 学习时间：2天 必须掌握：是
为什么学这一章？¶
目标代码生成是编译器后端的核心工作：将中间表示（IR）转换为特定硬件平台的机器码。这个阶段涉及指令选择、寄存器分配和指令调度等关键技术。
学完这一章，你将能够： - ✅ 理解从IR到汇编代码的转换过程 - ✅ 掌握寄存器分配的基本原理 - ✅ 理解指令选择和指令调度 - ✅ 能用工具查看和分析编译器生成的汇编代码
📖 核心概念¶
1. 代码生成的整体流程¶
Text Only
┌─────────────────────────────────────────────────────────────┐
│ 代码生成阶段 │
├─────────────────────────────────────────────────────────────┤
│ │
│ IR（中间表示） │
│ │ │
│ ├── 指令选择 → 选择具体机器指令 │
│ │ IR操作 → 机器指令（可能一对多/多对一） │
│ │ │
│ ├── 寄存器分配 → 将虚拟寄存器映射到物理寄存器 │
│ │ 无限虚拟寄存器 → 有限物理寄存器（溢出到栈） │
│ │ │
│ ├── 指令调度 → 重排指令减少流水线停顿 │
│ │ 考虑数据依赖和资源冲突 │
│ │ │
│ └── 目标代码输出 → 生成汇编或机器码 │
│ │
│ 输出：汇编文件 (.s) 或 目标文件 (.o) │
│ │
└─────────────────────────────────────────────────────────────┘
2. 指令选择¶
指令选择将IR操作映射到目标平台的机器指令：
Text Only
┌─────────────────────────────────────────────────────────────┐
│ IR → x86-64 指令选择示例 │
├─────────────────────────────────────────────────────────────┤
│ │
│ IR指令 x86-64汇编 │
│ ───────────── ───────────── │
│ t1 = a + b → mov eax, [a] │
│ add eax, [b] │
│ │
│ t2 = t1 * 4 → shl eax, 2 (强度削减：乘4变左移2) │
│ │
│ t3 = arr[t2] → mov ebx, [arr + eax] (寻址模式) │
│ │
│ x86的LEA指令可以一条实现复杂地址计算： │
│ t4 = a*4 + b → lea eax, [rdi*4 + rsi] │
│ │
└─────────────────────────────────────────────────────────────┘
3. 寄存器分配¶
寄存器分配是代码生成中最关键也最复杂的问题：
Text Only
┌─────────────────────────────────────────────────────────────┐
│ x86-64 通用寄存器 │
├─────────────────────────────────────────────────────────────┤
│ │
│ 调用者保存（Caller-saved）： │
│ rax - 返回值 rcx - 第4参数(Linux)/第1参数(Windows) │
│ rdx - 第3参数 rsi - 第2参数(Linux) │
│ rdi - 第1参数(Linux) r8-r11 - 临时寄存器 │
│ │
│ 被调用者保存（Callee-saved）： │
│ rbx, rbp, r12-r15 - 函数调用后值不变 │
│ │
│ 特殊寄存器： │
│ rsp - 栈指针 rbp - 帧指针 │
│ rip - 指令指针 │
│ │
│ 当变量数超过寄存器数时 → 寄存器溢出（Spill）到栈 │
│ │
└─────────────────────────────────────────────────────────────┘
图着色寄存器分配算法¶
C
// 寄存器分配的图着色方法（概念演示）
// register_alloc.c
#include <stdio.h>
#include <stdbool.h>
#define MAX_VARS 8
#define NUM_REGS 4 // 假设只有4个物理寄存器
// 干涉图：interference[i][j]=1 表示变量i和j同时活跃
int interference[MAX_VARS][MAX_VARS];
int color[MAX_VARS]; // 分配的寄存器编号，-1表示溢出
int num_vars;
// 初始化干涉图示例
void build_interference_graph() {
num_vars = 5;
// 假设变量 a,b,c,d,e 的活跃区间有重叠
// a与b同时活跃
interference[0][1] = interference[1][0] = 1;
// a与c同时活跃
interference[0][2] = interference[2][0] = 1;
// b与c同时活跃
interference[1][2] = interference[2][1] = 1;
// c与d同时活跃
interference[2][3] = interference[3][2] = 1;
// d与e同时活跃
interference[3][4] = interference[4][3] = 1;
}
// 贪心着色
bool greedy_coloring() {
for (int i = 0; i < num_vars; i++) color[i] = -1;
for (int v = 0; v < num_vars; v++) {
bool used[NUM_REGS];
for (int r = 0; r < NUM_REGS; r++) used[r] = false;
// 标记邻居已用的颜色
for (int u = 0; u < num_vars; u++) {
if (interference[v][u] && color[u] >= 0) {
used[color[u]] = true;
}
}
// 分配最小可用颜色
for (int r = 0; r < NUM_REGS; r++) {
if (!used[r]) {
color[v] = r;
break;
}
}
if (color[v] == -1) {
printf("变量 %c 需要溢出到栈\n", 'a' + v);
}
}
return true;
}
int main() {
const char *reg_names[] = {"eax", "ebx", "ecx", "edx"};
build_interference_graph();
greedy_coloring();
printf("\n寄存器分配结果：\n");
for (int i = 0; i < num_vars; i++) {
if (color[i] >= 0)
printf("变量 %c → %s\n", 'a' + i, reg_names[color[i]]);
else
printf("变量 %c → [栈溢出]\n", 'a' + i);
}
return 0;
}
4. 指令调度¶
指令调度通过重排指令减少CPU流水线停顿：
C
// 指令调度示例
// 未调度（存在数据依赖停顿）：
// load r1, [addr1] ← 内存加载，延迟3-4周期
// add r2, r1, 1 ← 依赖r1，必须等待load完成！
// load r3, [addr2]
// add r4, r3, 1
// 调度后（隐藏延迟）：
// load r1, [addr1] ← 发起第一次加载
// load r3, [addr2] ← 立即发起第二次加载（不依赖r1）
// add r2, r1, 1 ← 此时r1已就绪
// add r4, r3, 1 ← 此时r3已就绪
5. 实验：观察生成的汇编代码¶
C
// codegen_example.c
int add(int a, int b) {
return a + b;
}
int array_sum(int *arr, int n) { // 指针：存储变量的内存地址
int sum = 0;
for (int i = 0; i < n; i++) {
sum += arr[i];
}
return sum;
}
// 条件表达式
int abs_val(int x) {
return x >= 0 ? x : -x;
}
// 函数调用
int caller(int x) {
return add(x, x + 1);
}
Bash
# 生成汇编代码
gcc -S -O2 -masm=intel codegen_example.c -o codegen.s
# 查看汇编
cat codegen.s
# 使用objdump查看带地址的反汇编
gcc -c -O2 codegen_example.c -o codegen.o
objdump -d -M intel codegen.o
# Compiler Explorer (godbolt.org) 可以在线对比
预期汇编输出（x86-64, System V ABI）：
GAS
; add函数：a在edi, b在esi, 返回值在eax
add:
lea eax, [rdi + rsi] ; 一条LEA搞定加法
ret
; abs_val函数：可能使用条件移动指令
abs_val:
mov eax, edi
neg edi ; edi = -x
cmovs eax, edi ; 如果原x为负，选择-x
ret
6. 调用约定¶
Text Only
┌─────────────────────────────────────────────────────────────┐
│ System V AMD64 ABI 调用约定（Linux） │
├─────────────────────────────────────────────────────────────┤
│ │
│ 参数传递： │
│ 整数/指针：rdi, rsi, rdx, rcx, r8, r9（前6个） │
│ 浮点数： xmm0-xmm7（前8个） │
│ 更多参数：通过栈传递（从右到左压栈） │
│ │
│ 返回值： │
│ 整数/指针：rax（128位用rax:rdx） │
│ 浮点数： xmm0 │
│ │
│ 栈对齐：调用前rsp必须16字节对齐 │
│ │
│ 红区（Red Zone）：rsp下方128字节可自由使用 │
│ （叶函数可以不调整rsp直接使用红区） │
│ │
└─────────────────────────────────────────────────────────────┘
C
// 观察调用约定
// calling_convention.c
#include <stdio.h> // 引入头文件
long func_6args(long a, long b, long c, long d, long e, long f) {
return a + b + c + d + e + f;
// a→rdi, b→rsi, c→rdx, d→rcx, e→r8, f→r9
}
long func_8args(long a, long b, long c, long d,
long e, long f, long g, long h) {
return a + b + c + d + e + f + g + h;
// 前6个用寄存器，g和h通过栈传递
}
int main() {
printf("6参数: %ld\n", func_6args(1, 2, 3, 4, 5, 6));
printf("8参数: %ld\n", func_8args(1, 2, 3, 4, 5, 6, 7, 8));
return 0;
}
💡 面试常见问题¶
Q1：什么是寄存器分配？为什么它是NP完全问题？¶
答：寄存器分配将程序中的变量映射到有限的物理寄存器。它等价于图着色问题（给干涉图的节点着色，相邻节点不同色），图着色在k≥3时是NP完全的。实际编译器使用启发式算法（线性扫描、图着色近似等）。
Q2：什么是指令调度？它和寄存器分配的关系？¶
答：指令调度重排指令以减少流水线停顿，提高ILP（指令级并行度）。两者存在"相位排序问题"：先调度再分配可能增加寄存器压力，先分配再调度可能限制调度空间。现代编译器通常交替进行，或使用集成方法。
Q3：x86-64 的 LEA 指令为什么经常被编译器使用？¶
答：LEA（Load Effective Address）可以在一条指令内完成加法和移位操作（如 lea rax, [rdi + rsi*4 + 8]），且不影响标志位，执行在ALU而非AGU，延迟低。编译器常用它做算术计算（不仅仅是地址计算）。
Q4：解释caller-saved和callee-saved寄存器的区别。¶
答：Caller-saved（如rax, rcx, rdx）在函数调用前由调用者保存（如果之后还需要）；callee-saved（如rbx, rbp, r12-r15）由被调用函数负责保存和恢复。这种约定让编译器能安全生成跨函数的代码。
Q5：什么是"寄存器溢出"（Register Spill）？如何减少？¶
答：当同时活跃的变量超过物理寄存器数量时，需将部分变量存到栈上（溢出）。减少方法：①减少变量活跃范围；②循环内减少临时变量；③编译器用启发式选择溢出开销最小的变量。内联和展开可能增加寄存器压力。
📝 本章小结¶
Text Only
┌─────────────────────────────────────────────┐
│ 本章核心知识点 │
├─────────────────────────────────────────────┤
│ │
│ 1. 代码生成 = 指令选择+寄存器分配+调度 │
│ 2. 指令选择将IR操作映射到机器指令 │
│ 3. 寄存器分配 ≈ 图着色（NP完全） │
│ 4. 指令调度重排指令以提高流水线效率 │
│ 5. 调用约定定义了函数间的接口契约 │
│ 6. 用gcc -S和objdump观察生成代码 │
│ │
└─────────────────────────────────────────────┘
下一章：06-链接器与可执行文件 - 从目标文件到可执行程序