【编译原理实战】第 3 篇：手写 x86-64 后端——从图着色寄存器分配到 AT&T 汇编输出

发表于 更新于 分类于 系列 📑 compiler
手写 x86-64 后端：图着色寄存器分配（Chaitin）、活跃性分析、System V AMD64 调用约定、栈帧管理、ModR/M + SIB + REX 指令编码，输出可在 gcc 编译运行的 AT&T 汇编

为什么 mov 指令有 1500 种变体？寄存器不够用时编译器怎么办？一篇打通 x86-64 后端六大子任务。

系列导航

#文章状态
14 阶段全打通✅ 已发布
28 大优化 Pass 全打通✅ 已发布
3本文：手写 x86-64 后端✅ 已发布
4LLVM 实战：用 LLVM API 重写 mini 编译器🔜 计划中
5JIT 编译：运行时编译与 HotSpot🔜 计划中

前言

#2 我们把 IR 优化到了”接近最优”。但优化得再漂亮的 IR，最终都得落地成 CPU 能执行的机器码。

这一篇解决编译器最脏、最硬核的一段——后端（Backend）。把 TAC（三地址码）翻译成 x86-64 汇编，让 fib(10) 在 Linux 上真的能跑出 55。

读完你能得到：

  • 寄存器分配的图着色算法完整 C++ 实现
  • 活跃性分析（Dataflow Analysis）原理与代码
  • System V AMD64 调用约定的每个细节
  • x86-64 指令编码（ModR/M + SIB + REX）的位级解析
  • 一个能 gcc fib.S -o fib 跑通的完整 mini 编译器后端

一、后端全景：六大子任务

把 IR 变成汇编，要过六道关：

graph TB
    A["📋 IR<br/>三地址码"] --> B["1️⃣ 指令选择<br/>TAC → x86 操作"]
    B --> C["2️⃣ 活跃性分析<br/>哪些变量同时活"]
    C --> D["3️⃣ 寄存器分配<br/>虚拟 → 物理"]
    D --> E["4️⃣ 栈帧布局<br/>prologue/epilogue"]
    E --> F["5️⃣ 调用约定<br/>参数/返回值"]
    F --> G["6️⃣ 指令编码<br/>AT&T 文本输出"]
    G --> H["📦 fib.S<br/>gcc 编译运行"]

    style A fill:#C7CEEA,stroke:#9FA8DA,color:#333
    style B fill:#E8D5F5,stroke:#CE93D8,color:#333
    style C fill:#FFDAB9,stroke:#FFAB76,color:#333
    style D fill:#FFB3C6,stroke:#F48FB1,color:#333
    style E fill:#B5EAD7,stroke:#80CBC4,color:#333
    style F fill:#FFF9C4,stroke:#F9A825,color:#333
    style G fill:#E8D5F5,stroke:#CE93D8,color:#333
    style H fill:#B5EAD7,stroke:#80CBC4,color:#333

1.1 六大子任务清单

序号子任务核心问题算法/技术
1指令选择TAC 操作映射到目标指令模式匹配 / SelectionDAG
2数据流分析变量活跃区间工作列表算法
3寄存器分配无限虚拟 → 有限物理图着色 / 线性扫描
4调用约定函数间参数/返回值传递System V ABI / MS x64
5栈帧管理局部变量与溢出prologue / epilogue
6指令编码汇编文本生成ModR/M + SIB + REX

1.2 为什么”mov”有 1500 种变体

x86-64 是 CISC（Complex Instruction Set Computer）祖师爷。一条 mov 可以是 8/16/32/64 位、寄存器/立即数/内存、8 种寻址模式。光组合就有：
$$ 4(\text{位宽}) \times 3(\text{源类型}) \times 3(\text{目标类型}) \times 8(\text{寻址}) = 288 \text{ 种} $$

再加上 REX 前缀、ModR/M、SIB 字节的组合优化空间，mov 的合法编码超过 1500 种。

二、指令选择（Instruction Selection）

2.1 原理

把 IR 的 t1 = t2 + t3 翻译成 addl %esi, %edi 这种目标指令。

两种主流方法：

方法原理优点缺点
Burs 自动机树模式匹配，状态机查找速度快，最优覆盖难维护，难扩展
SelectionDAG降序把 DAG 匹配到指令LLVM 主流，灵活性高实现复杂
简单展开每条 IR 一对一映射易实现难做窥孔优化

2.2 实战：TAC → x86-64 指令

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
// instruction_selector.h
#pragma once
#include "tac.h"
#include "x86_instr.h"

class InstructionSelector {
public:
    std::vector<X86Instr> select(const std::vector<TAC>& tacs) {
        std::vector<X86Instr> asm_code;
        for (const auto& tac : tacs) {
            X86Instr instr = lower(tac);
            asm_code.push_back(instr);
        }
        return asm_code;
    }

private:
    // 模式匹配：TAC 操作 -> x86-64 指令
    X86Instr lower(const TAC& t) {
        switch (t.op) {
            case TAC::ADD:
                return {X86Instr::Add, t.lhs, t.rhs, t.dst,
                       "t1 = t2 + t3"};
            case TAC::SUB:
                return {X86Instr::Sub, t.lhs, t.rhs, t.dst, ""};
            case TAC::MUL:
                return {X86Instr::Imul, t.lhs, t.rhs, t.dst, ""};
            case TAC::DIV:
                // idiv 用 rax/rdx，特殊处理
                return emit_div(t);
            case TAC::CMP_LT:
                return {X86Instr::Cmp, t.lhs, t.rhs, "", ""};
            case TAC::JMP:
                return {X86Instr::Jmp, t.target, "", "", ""};
            case TAC::JE:
                return {X86Instr::Je, t.target, "", "", ""};
            // ... 更多操作
            default:
                return {X86Instr::Mov, t.lhs, "", t.dst, "unknown"};
        }
    }
};

TAC（Three-Address Code，三地址码） 是后端的通用中间表示，最多 3 个操作数：x = y op z。

三、活跃性分析（Liveness Analysis）

3.1 为什么需要活跃性

寄存器只有 16 个（GP）。变量可能有 1000 个。哪两个变量可以共用一个寄存器？

答案：活跃区间不重叠的两个变量。

graph LR
    A["b = 1"] --> B["c = 2"]
    B --> C["a = b + c"]
    C --> D["d = a * 2"]
    D --> E["return d"]

    style A fill:#C7CEEA,stroke:#9FA8DA,color:#333
    style B fill:#C7CEEA,stroke:#9FA8DA,color:#333
    style C fill:#FFDAB9,stroke:#FFAB76,color:#333
    style D fill:#E8D5F5,stroke:#CE93D8,color:#333
    style E fill:#B5EAD7,stroke:#80CBC4,color:#333

例子分析：

变量活跃区间注释
b第 1-3 行第 1 行定义，第 3 行最后使用
c第 2-3 行第 2 行定义，第 3 行最后使用
a第 3-4 行第 3 行定义，第 4 行最后使用
d第 4-5 行第 4 行定义，第 5 行最后使用

b 和 d 活跃区间不重叠，可以共用同一寄存器。

3.2 数据流方程

活跃性是一个典型的反向数据流问题：

$$ \text{LIVE}{\text{out}}[B] = \bigcup{S \in \text{succ}[B]} \text{LIVE}_{\text{in}}[S] $$

$$ \text{LIVE}{\text{in}}[B] = \text{USE}[B] \cup (\text{LIVE}{\text{out}}[B] - \text{DEF}[B]) $$

  • USE[B]：B 中使用但在 B 中没定义的变量
  • DEF[B]：B 中定义的变量
  • 反复迭代直到不再变化（不动点）

3.3 实战：工作列表算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
// liveness_analyzer.h
#pragma once
#include "cfg.h"
#include <set>
#include <map>
#include <queue>

class LivenessAnalyzer {
public:
    // 计算每个基本块的 live_in / live_out
    void analyze(const CFG& cfg) {
        initialize(cfg);
        // 反向后序遍历（更高效）
        std::vector<Block*> rpo = reverse_post_order(cfg);
        bool changed = true;
        while (changed) {
            changed = false;
            for (auto* block : rpo) {
                std::set<std::string> new_in, new_out;
                // live_out = ∪ live_in[successor]
                for (auto* succ : block->successors) {
                    new_out.insert(live_in[succ].begin(),
                                   live_in[succ].end());
                }
                // live_in = use ∪ (live_out - def)
                std::set<std::string> diff;
                std::set_difference(new_out.begin(), new_out.end(),
                    def[block].begin(), def[block].end(),
                    std::inserter(diff, diff.end()));
                new_in = use[block];
                new_in.insert(diff.begin(), diff.end());
                if (new_in != live_in[block] ||
                    new_out != live_out[block]) {
                    live_in[block] = new_in;
                    live_out[block] = new_out;
                    changed = true;
                }
            }
        }
    }

    // 关键接口：变量 v 在位置 p 是否活跃？
    bool is_live_at(const std::string& v, Block* b) {
        return live_out[b].count(v) > 0;
    }

    // 构造冲突图（interference graph）
    InterferenceGraph build_interference(const Function& fn) {
        InterferenceGraph ig;
        for (auto& [block, vars] : live_out) {
            // 同一个 live_out 集合里的所有变量互相冲突
            for (const auto& v1 : vars) {
                for (const auto& v2 : vars) {
                    if (v1 != v2) ig.add_edge(v1, v2);
                }
            }
        }
        return ig;
    }

private:
    std::map<Block*, std::set<std::string>> live_in, live_out;
    std::map<Block*, std::set<std::string>> use, def;
};

关键洞察：live_out 集合里的变量，两两都需要不同寄存器——这就是冲突图的来源。

四、寄存器分配：图着色算法

4.1 核心思想

把寄存器分配转化为图着色问题：

给定无向图 G 和 k 种颜色，给每个节点涂一种颜色，相邻节点颜色不同。

  • 节点：变量
  • 边：两变量活跃区间重叠（冲突）
  • 颜色：物理寄存器
  • k = 16：x86-64 通用寄存器数量

Chaitin 定理（1981）：如果 k 色图着色存在，简化（Simplify）算法能找到。

4.2 完整算法流程

graph TB
    A["📊 构建冲突图"] --> B["🔢 重复简化<br/>degree < k"]
    B --> C{"栈空?"}
    C -->|"否"| B
    C -->|"是"| D["🎨 选颜色<br/>从栈顶弹回"]
    D --> E{"有可用颜色?"}
    E -->|"是"| F["✅ 分配寄存器"]
    E -->|"否"| G["💥 Spill<br/>溢出到栈"]
    G --> F
    F --> H["📦 完整分配"]

    style A fill:#C7CEEA,stroke:#9FA8DA,color:#333
    style B fill:#FFDAB9,stroke:#FFAB76,color:#333
    style C fill:#FFF9C4,stroke:#F9A825,color:#333
    style D fill:#E8D5F5,stroke:#CE93D8,color:#333
    style E fill:#FFF9C4,stroke:#F9A825,color:#333
    style F fill:#B5EAD7,stroke:#80CBC4,color:#333
    style G fill:#FFB3C6,stroke:#F48FB1,color:#333
    style H fill:#B5EAD7,stroke:#80CBC4,color:#333

4.3 实战：Chaitin 图着色分配器

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
// register_allocator.h
#pragma once
#include "interference_graph.h"
#include <stack>
#include <vector>
#include <string>
#include <map>
#include <algorithm>

class ChaitinRegisterAllocator {
public:
    // k = 16 通用寄存器
    static constexpr int K = 16;
    const std::vector<std::string> regs = {
        "rax", "rbx", "rcx", "rdx", "rsi", "rdi", "rbp", "rsp",
        "r8", "r9", "r10", "r11", "r12", "r13", "r14", "r15"
    };

    // 排除 rbp（帧指针）和 rsp（栈指针）
    const std::vector<std::string> alloc_regs = {
        "rax", "rbx", "rcx", "rdx", "rsi", "rdi",
        "r8", "r9", "r10", "r11", "r12", "r13", "r14", "r15"
    };

    struct Allocation {
        std::map<std::string, std::string> var_to_reg;  // t1 -> rax
        std::map<std::string, int> spilled_vars;         // t1 -> 栈偏移
        int frame_size = 0;
    };

    Allocation allocate(const InterferenceGraph& ig,
                        const LivenessAnalyzer& la) {
        Allocation result;
        InterferenceGraph work = ig;
        std::stack<std::string> simplify_stack;
        std::set<std::string> spilled;

        // === Step 1: Simplify 阶段 ===
        // 反复移除 degree < K 的节点
        bool progress = true;
        while (progress) {
            progress = false;
            for (const auto& node : work.nodes()) {
                if (work.degree(node) < K &&
                    !work.is_on_stack(node) &&
                    !work.is_spilled(node)) {
                    simplify_stack.push(node);
                    work.remove_node(node);
                    progress = true;
                    break;
                }
            }
        }

        // === Step 2: Spill 候选 ===
        // 剩余的都是 degree >= K（高冲突）
        std::vector<std::string> spill_candidates;
        for (const auto& node : work.nodes()) {
            if (!work.is_on_stack(node)) {
                spill_candidates.push_back(node);
            }
        }

        // 启发式：选 cost/degree 最大的（最不"热"的变量溢出）
        // cost = 估计使用次数 / degree
        std::sort(spill_candidates.begin(), spill_candidates.end(),
            [&](const std::string& a, const std::string& b) {
                double ca = estimate_cost(a) / (ig.degree(a) + 1);
                double cb = estimate_cost(b) / (ig.degree(b) + 1);
                return ca < cb;  // 代价小的优先溢出
            });

        for (const auto& v : spill_candidates) {
            result.spilled_vars[v] = result.frame_size;
            result.frame_size += 8;  // 64 位 = 8 字节
        }

        // === Step 3: Select 阶段 ===
        // 从栈顶弹出，分配颜色
        std::set<std::string> used_colors;
        while (!simplify_stack.empty()) {
            std::string node = simplify_stack.top();
            simplify_stack.pop();
            // 收集邻居已用颜色
            std::set<std::string> neighbor_colors;
            for (const auto& nb : ig.neighbors(node)) {
                auto it = result.var_to_reg.find(nb);
                if (it != result.var_to_reg.end()) {
                    neighbor_colors.insert(it->second);
                }
            }
            // 找第一个未用的
            std::string chosen;
            for (const auto& r : alloc_regs) {
                if (!neighbor_colors.count(r)) {
                    chosen = r;
                    break;
                }
            }
            result.var_to_reg[node] = chosen;
        }

        return result;
    }

private:
    // 简化版 cost 估算：实际应该用 profile / loop nesting
    double estimate_cost(const std::string& v) {
        return 1.0;  // 简化处理
    }
};

4.4 图着色 vs 线性扫描

维度图着色（Chaitin）线性扫描（Wimmer）
质量✅ 接近最优⚠️ 略差
速度⚠️ O(n²) 以上✅ O(n) 线性
实现❌ 复杂✅ 简单
生产使用GCC（老版本）HotSpot、Go、V8
溢出智能选择简单策略

LLVM 用了第四种——Greedy + Live Range Splitting，工业级最优解。

4.5 溢出处理（Spilling）

寄存器不够用时，把变量存到栈：

1
2
3
# t1 溢出到栈帧 [rbp-8]
movq    %rax, -8(%rbp)        # store t1
movq    -8(%rbp), %rcx        # load t1

代价：每次访问都是一次内存读写。优化方向：把溢出变量的活跃区间拆短（Live Range Splitting），让部分区间能进入寄存器。

五、调用约定（Calling Convention）

5.1 为什么需要约定

函数 A 调用函数 B，参数怎么传？返回值怎么拿？寄存器谁保护？

ABI（Application Binary Interface，应用二进制接口）就是答案。

5.2 System V AMD64 ABI（Linux/macOS）

位置用途寄存器
参数 1-6整数/指针rdi, rsi, rdx, rcx, r8, r9
参数 7+栈传递从右向左压栈
返回值整数/指针rax（64 位）/ rax:rdx（128 位）
被调用者保存函数内部保护rbx, rbp, r12-r15
调用者保存调用方保护rax, rcx, rdx, rsi, rdi, r8-r11
graph LR
    A["调用方"] -->|"rdi=arg1<br/>rsi=arg2<br/>..."| B["被调用方"]
    B -->|"rax=ret"| A

    A -.->|"保存<br/>caller-saved"| C["🗄️ 栈"]
    B -.->|"保存<br/>callee-saved"| C

    style A fill:#C7CEEA,stroke:#9FA8DA,color:#333
    style B fill:#E8D5F5,stroke:#CE93D8,color:#333
    style C fill:#FFDAB9,stroke:#FFAB76,color:#333

5.3 Microsoft x64 ABI（Windows）

差异点System V (Linux)Microsoft x64 (Windows)
前 4 参数rdi, rsi, rdx, rcxrcx, rdx, r8, r9
被调用者保存rbx, rbp, r12-r15rbx, rbp, rdi, rsi, r12-r15
栈对齐16 字节16 字节
影子空间❌ 无✅ 4 个 slot（32 字节）
可变参数rax 存向量个数rax 保留

为什么不同？ 历史包袱。Windows 早期对 RCX/RDX/DX/AX 有特殊语义；Linux 走 UNIX 传统。每个 ABI 都有几十万行代码依赖，改不动。

5.4 实战：调用约定发射器

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
// call_conv_emitter.h
#pragma once
#include "x86_instr.h"
#include <vector>
#include <string>

class CallConvEmitter {
public:
    // System V AMD64
    const std::vector<std::string> arg_regs = {
        "rdi", "rsi", "rdx", "rcx", "r8", "r9"
    };
    const std::string ret_reg = "rax";

    // 发出函数调用：把参数放到正确位置 + call 指令
    std::vector<X86Instr> emit_call(
        const std::string& func_name,
        const std::vector<std::string>& args) {
        std::vector<X86Instr> code;
        // 1. 前 6 个参数走寄存器
        for (size_t i = 0; i < args.size() && i < 6; ++i) {
            code.push_back({X86Instr::Mov, args[i], "",
                            arg_regs[i], "arg " + std::to_string(i)});
        }
        // 2. 超过 6 个走栈（从右到左）
        for (int i = args.size() - 1; i >= 6; --i) {
            code.push_back({X86Instr::Push, args[i], "", "",
                            "stack arg " + std::to_string(i)});
        }
        // 3. 16 字节栈对齐（call 之前 rsp 必须对齐）
        // 4. 实际调用
        code.push_back({X86Instr::Call, func_name, "", "", ""});
        return code;
    }

    // 函数序言：保存 callee-saved 寄存器
    std::vector<X86Instr> emit_prologue(int frame_size) {
        std::vector<X86Instr> code;
        code.push_back({X86Instr::Push, "rbp", "", "", "save rbp"});
        code.push_back({X86Instr::Mov, "rsp", "", "rbp",
                       "set frame ptr"});
        if (frame_size > 0) {
            code.push_back({X86Instr::Sub, "rsp", std::to_string(frame_size),
                            "rsp", "alloc locals"});
        }
        // 保存 callee-saved：rbx, r12-r15
        // (简化：实际由寄存器分配器告知)
        return code;
    }

    // 函数尾声：恢复 + 返回
    std::vector<X86Instr> emit_epilogue() {
        std::vector<X86Instr> code;
        code.push_back({X86Instr::Leave, "", "", "",
                       "mov rsp, rbp; pop rbp"});
        code.push_back({X86Instr::Ret, "", "", "", ""});
        return code;
    }
};

5.5 一个完整的 fib(10) 调用序列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# main 调用 fib(10)
main:
    pushq   %rbp
    movq    %rsp, %rbp
    movl    $10, %edi          # arg1 = 10 -> rdi
    call    fib                # 调用 fib
    # rax = 55
    movl    $1, %eax           # syscall: exit
    xorl    %edi, %edi
    syscall

fib:
    pushq   %rbp
    movq    %rsp, %rbp
    subq    $16, %rsp          # 局部变量空间
    # ... fib 的实现
    leave
    ret

六、栈帧管理（Stack Frame）

6.1 栈帧布局

graph TB
    subgraph "调用方栈帧"
        A1["返回地址"]
    end
    subgraph "当前函数栈帧"
        B1["保存的 rbp<br/>📍 帧基址"]
        B2["溢出槽 1<br/>（spill slot）"]
        B3["溢出槽 2"]
        B4["局部变量"]
        B5["..."]
        B6["rsp 当前栈顶"]
    end
    A1 --> B1 --> B2 --> B3 --> B4 --> B5 --> B6

    style A1 fill:#C7CEEA,stroke:#9FA8DA,color:#333
    style B1 fill:#FFB3C6,stroke:#F48FB1,color:#333
    style B2 fill:#FFDAB9,stroke:#FFAB76,color:#333
    style B3 fill:#FFDAB9,stroke:#FFAB76,color:#333
    style B4 fill:#B5EAD7,stroke:#80CBC4,color:#333
    style B5 fill:#B5EAD7,stroke:#80CBC4,color:#333
    style B6 fill:#E8D5F5,stroke:#CE93D8,color:#333

6.2 Prologue / Epilogue 模板

部分指令序列作用
Prologuepush rbp; mov rsp, rbp; sub rsp, N保存帧指针、分配局部空间
Epilogueleave; ret恢复栈、返回

leave 是 mov rsp, rbp; pop rbp 的合并指令。

6.3 栈帧布局实战

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
// frame_layout.h
#pragma once
#include <string>
#include <map>
#include <vector>

class FrameLayout {
public:
    struct Slot {
        std::string name;
        int offset;          // 相对 rbp 的偏移（负数）
        int size;            // 字节数
        bool is_spill;       // 是否溢出变量
    };

    void add_local(const std::string& name, int size = 8) {
        current_offset -= size;
        slots[name] = {name, current_offset, size, false};
    }

    void add_spill(const std::string& name) {
        current_offset -= 8;
        slots[name] = {name, current_offset, 8, true};
    }

    // 生成访问局部变量的汇编（用 rbp 寻址）
    std::string access(const std::string& name,
                       const std::string& reg) {
        auto& s = slots.at(name);
        return "movq " + std::to_string(s.offset) + "(%rbp), %" + reg;
    }

    int frame_size() const { return -current_offset; }

    // DWARF 调试信息（用于 gdb 调试）
    std::string emit_dwarf_debug_info() {
        std::string dwarf = ".section .debug_info\n";
        dwarf += ".Ldebug_info0:\n";
        // ... 实际 DWARF 生成
        return dwarf;
    }

private:
    std::map<std::string, Slot> slots;
    int current_offset = 0;  // 从 0 向下增长
};

6.4 调试信息：DWARF

没有 DWARF，gdb 看到的变量全是寄存器名或栈偏移。DWARF 是编译器告诉调试器”哪个偏移对应哪个变量”的格式。

关键段：

DWARF 段作用
.debug_info函数、变量、类型定义
.debug_abbrev缩写表
.debug_line行号映射（源代码 ↔ 机器码）
.debug_frame栈帧信息（恢复寄存器）
.debug_loc变量位置（哪个 PC 在哪个寄存器/栈）

七、x86-64 指令编码

7.1 指令格式总览

x86-64 指令的二进制布局：

graph LR
    A["🔧 指令前缀<br/>（可选）"] --> B["📋 REX 前缀<br/>（可选）"]
    B --> C["🎯 操作码<br/>1-3 字节"]
    C --> D["📦 ModR/M<br/>（可选）"]
    D --> E["📐 SIB<br/>（可选）"]
    E --> F["🔢 立即数<br/>（可选）"]
    F --> G["📍 偏移<br/>（可选）"]

    style A fill:#C7CEEA,stroke:#9FA8DA,color:#333
    style B fill:#E8D5F5,stroke:#CE93D8,color:#333
    style C fill:#FFB3C6,stroke:#F48FB1,color:#333
    style D fill:#FFDAB9,stroke:#FFAB76,color:#333
    style E fill:#B5EAD7,stroke:#80CBC4,color:#333
    style F fill:#FFF9C4,stroke:#F9A825,color:#333
    style G fill:#FFF9C4,stroke:#F9A825,color:#333

7.2 ModR/M 字节

ModR/M 决定操作数类型和寄存器/内存：

位7-65-32-0
字段ModReg/OpcodeR/M
含义寻址模式寄存器或操作码扩展寄存器或内存

Mod 字段：

Mod含义示例
00寄存器间接（无偏移）[rax]
018 位偏移[rax+8]
1032 位偏移[rax+0x12345678]
11寄存器-寄存器rax, rbx

7.3 SIB 字节

当 ModR/M 的 R/M = 100（[rSP]/[r12]）或 101（[RIP]），需要 SIB 字节：

位7-65-32-0
字段ScaleIndexBase
值1/2/4/8索引寄存器基址寄存器

SIB 编码复杂址：[base + index*scale + disp]

7.4 REX 前缀

x86-64 新增的字节（0100 WRXB）：

位作用
W1 = 64 位操作数
R扩展 ModR/M 的 Reg 字段（访问 r8-r15）
X扩展 SIB 的 Index 字段
B扩展 ModR/M 的 R/M 或 SIB 的 Base

7.5 实战：最小指令编码器

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
// x86_encoder.h
#pragma once
#include <cstdint>
#include <string>
#include <vector>
#include <sstream>
#include <iomanip>

class X86Encoder {
public:
    // 编码 mov reg, imm  (REX.W + mov r/m64, imm64)
    // 例: movq $10, %rax -> 48 c7 c0 0a 00 00 00
    std::vector<uint8_t> encode_mov_imm64(int reg, int64_t imm) {
        std::vector<uint8_t> code;
        // 1. REX.W 前缀 (0100 1000 = 0x48)
        code.push_back(0x48 | (reg > 7 ? 0x01 : 0x00));
        // 2. 操作码 0xC7 /0 (mov r/m64, imm32, sign-extended)
        code.push_back(0xC7);
        // 3. ModR/M: mod=11, reg=000, r/m=reg
        code.push_back(0xC0 | (reg & 0x07));
        // 4. 立即数（32 位，符号扩展）
        code.push_back(imm & 0xFF);
        code.push_back((imm >> 8) & 0xFF);
        code.push_back((imm >> 16) & 0xFF);
        code.push_back((imm >> 24) & 0xFF);
        return code;
    }

    // 编码 mov reg, reg  (REX.W + 89 /r)
    std::vector<uint8_t> encode_mov_reg(int dst, int src) {
        std::vector<uint8_t> code;
        // REX.WR
        code.push_back(0x48 |
                      ((src > 7) ? 0x04 : 0) |
                      ((dst > 7) ? 0x01 : 0));
        // Opcode: 89 (mov r/m64, r64)
        code.push_back(0x89);
        // ModR/M: mod=11, reg=src, r/m=dst
        code.push_back(0xC0 | ((src & 0x07) << 3) | (dst & 0x07));
        return code;
    }

    // 编码 mov [reg+disp], reg  (内存写)
    std::vector<uint8_t> encode_mov_mem(int base_reg, int disp,
                                        int src_reg) {
        std::vector<uint8_t> code;
        // REX.WR
        code.push_back(0x48 |
                      ((src_reg > 7) ? 0x04 : 0) |
                      ((base_reg > 7) ? 0x01 : 0));
        code.push_back(0x89);  // mov r/m64, r64
        // ModR/M: mod=10, reg=src, r/m=base
        code.push_back(0x80 | ((src_reg & 0x07) << 3) | (base_reg & 0x07));
        // 32 位偏移
        for (int i = 0; i < 4; ++i) {
            code.push_back((disp >> (i*8)) & 0xFF);
        }
        return code;
    }

    // 编码 ret
    std::vector<uint8_t> encode_ret() { return {0xC3}; }

    // 编码 add reg, reg
    std::vector<uint8_t> encode_add_reg(int dst, int src) {
        std::vector<uint8_t> code;
        code.push_back(0x48 |
                      ((src > 7) ? 0x04 : 0) |
                      ((dst > 7) ? 0x01 : 0));
        code.push_back(0x01);  // add r/m64, r64
        code.push_back(0xC0 | ((src & 0x07) << 3) | (dst & 0x07));
        return code;
    }

    // 工具：字节数组转 hex 字符串
    std::string to_hex(const std::vector<uint8_t>& bytes) {
        std::ostringstream oss;
        for (auto b : bytes) {
            oss << std::hex << std::setw(2) << std::setfill('0')
                << (int)b << " ";
        }
        return oss.str();
    }
};

测试：

1
2
3
4
5
6
int main() {
    X86Encoder enc;
    auto bytes = enc.encode_mov_imm64(0, 10);  // mov $10, %rax
    std::cout << enc.to_hex(bytes) << "\n";
    // 输出: 48 c7 c0 0a 00 00 00
}

7.6 完整指令编码表（精简版）

指令操作码ModR/M用途
mov r64, imm320xC7/0加载立即数
mov r64, r640x89/r寄存器间传送
add r64, r640x01/r寄存器加
sub r64, r640x29/r寄存器减
imul r64, r640x0F 0xAF/r整数乘
cmp r64, r640x39/r比较
jmp rel320xE9—无条件跳转
je rel320x0F 0x84—相等跳转
call rel320xE8—函数调用
ret0xC3—函数返回
push r640x50+r—压栈
pop r640x58+r—出栈
leave0xC9—恢复栈帧
syscall0x0F 0x05—系统调用

/r 表示 ModR/M 的 Reg 字段是源寄存器。

八、AT&T 汇编输出

8.1 AT&T vs Intel 语法

维度AT&T（gcc 默认）Intel（MASM/NASM）
操作数顺序mov src, dstmov dst, src
立即数前缀$1010
寄存器前缀%raxrax
内存寻址8(%rbp)[rbp+8]
位宽后缀q/l/w/bQWORD PTR

我们用 AT&T——和 gcc 输出的格式一致。

8.2 完整 fib(10) 汇编输出

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
# Generated by minilang compiler v0.1
# Source: fib(10)

        .section .text
        .globl  main
        .type   main, @function

main:
        pushq   %rbp
        movq    %rsp, %rbp
        subq    $16, %rsp
        movl    $10, %edi              # arg0 = 10
        call    fib
        movq    %rax, -8(%rbp)         # save result
        movl    $60, %eax              # syscall exit
        xorl    %edi, %edi
        syscall
        leave
        ret

        .globl  fib
        .type   fib, @function

fib:
        pushq   %rbp
        movq    %rsp, %rbp
        subq    $32, %rsp
        movq    %rdi, -8(%rbp)         # n -> local
        cmpl    $1, -8(%rbp)           # n <= 1?
        jle     .L_base_case
        movl    -8(%rbp), %eax
        subl    $1, %eax
        movl    %eax, %edi
        call    fib
        movq    %rax, -16(%rbp)        # fib(n-1)
        movl    -8(%rbp), %eax
        subl    $2, %eax
        movl    %eax, %edi
        call    fib
        movq    -16(%rbp), %rdx
        addq    %rax, %rdx             # fib(n-1) + fib(n-2)
        movq    %rdx, %rax
        jmp     .L_end
.L_base_case:
        movl    $1, %eax               # return 1
.L_end:
        leave
        ret

8.3 编译运行

1
2
3
4
5
6
# 编译汇编为可执行文件
gcc -no-pie fib.S -o fib

# 运行
./fib
echo $?  # 应该输出 55

实际结果：exit(55)，shell $? 打印 55。✅

九、完整后端：组合六大子任务

9.1 Backend 主类

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
// backend.h
#pragma once
#include "tac.h"
#include "liveness_analyzer.h"
#include "register_allocator.h"
#include "call_conv_emitter.h"
#include "frame_layout.h"
#include "x86_encoder.h"
#include <sstream>

class Backend {
public:
    std::string generate_assembly(const Program& prog) {
        std::ostringstream out;
        out << "        .section .text\n";
        for (const auto& func : prog.functions) {
            emit_function(out, func);
        }
        return out.str();
    }

private:
    LivenessAnalyzer liveness;
    CallConvEmitter call_conv;
    X86Encoder encoder;

    void emit_function(std::ostringstream& out, const Function& fn) {
        // 1. 活跃性分析
        liveness.analyze(fn.cfg);
        // 2. 构建冲突图
        auto ig = liveness.build_interference(fn);
        // 3. 寄存器分配
        ChaitinRegisterAllocator alloc;
        auto allocation = alloc.allocate(ig, liveness);
        // 4. 栈帧布局
        FrameLayout frame;
        for (const auto& [var, off] : allocation.spilled_vars) {
            frame.add_spill(var);
        }
        // 5. 发射汇编
        out << "\n        .globl  " << fn.name << "\n";
        out << "        .type   " << fn.name << ", @function\n";
        out << fn.name << ":\n";
        // Prologue
        for (auto& instr : call_conv.emit_prologue(frame.frame_size())) {
            out << "        " << to_asm(instr) << "\n";
        }
        // Body（已分配寄存器）
        for (const auto& tac : fn.tacs) {
            out << "        " << lower_tac(tac, allocation) << "\n";
        }
        // Epilogue
        for (auto& instr : call_conv.emit_epilogue()) {
            out << "        " << to_asm(instr) << "\n";
        }
    }

    std::string lower_tac(const TAC& t,
                          const ChaitinRegisterAllocator::Allocation& a) {
        // 把虚拟寄存器替换为物理寄存器
        std::string lhs = get_reg(t.lhs, a);
        std::string rhs = get_reg(t.rhs, a);
        std::string dst = get_reg(t.dst, a);
        switch (t.op) {
            case TAC::ADD: return "addq    " + rhs + ", " + dst;
            case TAC::SUB: return "subq    " + rhs + ", " + dst;
            case TAC::MUL: return "imulq   " + rhs + ", " + dst;
            case TAC::MOV: return "movq    " + lhs + ", " + dst;
            case TAC::CMP_LT: return "cmpq    " + rhs + ", " + dst;
            case TAC::JMP: return "jmp     " + t.target;
            case TAC::RET: return "movq    " + lhs + ", %rax";
            default: return "# unknown";
        }
    }

    std::string get_reg(const std::string& v,
                        const ChaitinRegisterAllocator::Allocation& a) {
        if (a.var_to_reg.count(v)) {
            return "%" + a.var_to_reg[v];
        }
        if (a.spilled_vars.count(v)) {
            return std::to_string(a.spilled_vars[v]) + "(%rbp)";
        }
        return v;  // 常量
    }

    std::string to_asm(const X86Instr& i) {
        // 简化版：直接拼字符串
        std::ostringstream os;
        os << mnemonic_name(i.op);
        if (!i.arg1.empty()) os << " " << i.arg1;
        if (!i.arg2.empty()) os << ", " << i.arg2;
        if (!i.arg3.empty()) os << ", " << i.arg3;
        if (!i.comment.empty()) os << "  # " << i.comment;
        return os.str();
    }

    std::string mnemonic_name(X86Instr::Op op) {
        switch (op) {
            case X86Instr::Mov: return "movq";
            case X86Instr::Add: return "addq";
            case X86Instr::Sub: return "subq";
            case X86Instr::Imul: return "imulq";
            case X86Instr::Call: return "call";
            case X86Instr::Ret: return "ret";
            case X86Instr::Push: return "pushq";
            case X86Instr::Pop: return "popq";
            case X86Instr::Leave: return "leave";
            default: return "nop";
        }
    }
};

9.2 后端数据流

graph TB
    A["TAC 函数"] --> B["活跃性分析"]
    B --> C["冲突图 IG"]
    C --> D["Chaitin 分配器"]
    D --> E["分配结果<br/>reg + spill"]
    E --> F["栈帧布局"]
    F --> G["指令发射"]
    G --> H["AT&T 汇编"]

    H --> I["gcc fib.S"]
    I --> J["可执行文件"]
    J --> K["./fib = 55"]

    style A fill:#C7CEEA,stroke:#9FA8DA,color:#333
    style B fill:#E8D5F5,stroke:#CE93D8,color:#333
    style C fill:#FFDAB9,stroke:#FFAB76,color:#333
    style D fill:#FFB3C6,stroke:#F48FB1,color:#333
    style E fill:#FFF9C4,stroke:#F9A825,color:#333
    style F fill:#B5EAD7,stroke:#80CBC4,color:#333
    style G fill:#E8D5F5,stroke:#CE93D8,color:#333
    style H fill:#B5EAD7,stroke:#80CBC4,color:#333
    style I fill:#FFDAB9,stroke:#FFAB76,color:#333
    style J fill:#FFB3C6,stroke:#F48FB1,color:#333
    style K fill:#B5EAD7,stroke:#80CBC4,color:#333

十、进阶话题

10.1 窥孔优化（Peephole Optimization）

指令选择之后、汇编输出之前，扫描相邻几条指令做局部优化：

优化前优化后收益
mov rax, rbx; mov rbx, rcxmov rax, rcx省一条指令
add rax, 0（删除）省一条指令
push rax; pop rax（删除）省两条
mul x; mul ymul x*y常量合并

10.2 指令调度（Instruction Scheduling）

乱序执行的 CPU 喜欢无依赖的指令串排在一起：

1
2
3
4
5
6
7
8
9
# 优化前（有数据依赖）
movl  $10, %eax
addl  %ebx, %eax
movl  %ecx, %edx       # 等 add 完成

# 优化后（重排）
movl  $10, %eax
movl  %ecx, %edx       # 和 add 无依赖，并行执行
addl  %ebx, %eax

收益：现代 CPU IPC（Instructions Per Cycle）能到 4-5，调度得当可提升 20%。

10.3 全局寄存器分配

Chaitin 经典算法每次只考虑一个函数。**跨函数分配（Global Allocation Across Functions）**是 LLVM/SSA 形式下的扩展：把整个程序看作一个大函数，做全局活跃性分析。

10.4 SSA 在后端的优势

优势说明
def-use 显式每个 use 知道来自哪个 def
活跃性精准phi 节点精确处理控制流汇合
寄存器分配简化SSA 形式下，活跃区间是嵌套的
优化友好GVN、CSE 几乎免费

LLVM 的 IR 是 SSA 形式，到汇编前才通过 Register Coalescing + phi 消除 降级回非 SSA。

十一、常见坑 & 调试技巧

11.1 后端十大经典 Bug

排名Bug 现象根因修复
1段错误（segfault）没保存 callee-savedprologue 补 push
2栈不对齐call 前 rsp % 16 != 0插入 sub rsp, 8
3参数位置错误用 rcx 而非 rdi按 ABI 顺序传参
4返回值丢失没把结果放 raxret 前 mov rax
5浮点参数错用整数寄存器传 xmm区分 GP 和 XMM
6溢出变量错位偏移计算 off-by-one仔细算 frame_size
7跳转目标错标签名打错用符号表查
8长跳转超 32 位jmp rel32 不够用 jmp [rip+mem]
9调试无符号没生成 DWARF加 -g 等价物
10性能慢没用 rip 寻址用 lea 代替 mov

11.2 调试工具链

1
2
3
4
5
6
7
8
9
10
11
12
# 查看汇编
objdump -d fib

# 查看符号 + 调试信息
objdump -d -S fib       # 混合显示源码

# 单步调试
gdb ./fib
(gdb) disas main
(gdb) break fib
(gdb) run
(gdb) info registers

十二、与生产编译器的对比

12.1 mini 后端 vs LLVM

维度本文 mini 后端LLVM 后端
代码量~1000 行~50 万行
优化图着色 + 简单窥孔13+ 个 Pass
SSA❌✅
架构支持x86-64x86/ARM/RISC-V/…
指令编码手写TableGen 自动生成
性能差距比 clang -O0 略好clang -O3 极致

12.2 我们学到了什么

graph LR
    A["🧠 理解原理"] --> B["📝 简化实现"]
    B --> C["🛠️ 调试排错"]
    C --> D["🚀 工业级"]

    style A fill:#C7CEEA,stroke:#9FA8DA,color:#333
    style B fill:#E8D5F5,stroke:#CE93D8,color:#333
    style C fill:#FFDAB9,stroke:#FFAB76,color:#333
    style D fill:#B5EAD7,stroke:#80CBC4,color:#333

手写后端 ≠ 实际工作会用。但手写过才知道：

  • 为什么 -O2 比 -O0 快 10 倍
  • 为什么 register 关键字在 C++17 被废弃
  • 为什么 inline 关键字不只是建议
  • 为什么现代语言（JVM、V8）都用 JIT 而非 AOT

十三、给读者的建议

13.1 怎么练手

水平任务预计时间
入门跑通 fib.S，能 gcc 编译运行1 天
进阶实现 if/else 编译，加 jmp 指令3 天
高级实现 while 循环，支持 backpatch1 周
挑战实现 struct，加 16 字节对齐2 周
极客加窥孔优化 + 指令调度1 个月

13.2 推荐资源

必读书：

书名作者重点
《编译原理》（龙书）Aho, Lam, Sethi, Ullman教科书标准答案
《Engineering a Compiler》Cooper, Torczon实战派
《Modern Compiler Implementation in C》AppelC 实现细节

论文：

论文年份核心贡献
Chaitin “Register Allocation & Spilling via Graph Coloring”1982图着色算法
Wimmer “Linear Scan Register Allocation”2010线性扫描
Briggs “Practical Improvements to the Construction and Destruction of Static Single Assignment Form”1998SSA 构造

开源代码：

13.3 系列下一步

#文章核心内容
14 阶段前端✅ 已完成
28 大优化 Pass✅ 已完成
3本文：x86-64 后端✅ 已完成
4LLVM 实战用 LLVM API 重写 mini 编译器
5JIT 编译HotSpot、Cranelift、运行时编译

总结

子任务核心算法工程难点
指令选择模式匹配 / DAG覆盖最优模式
活跃性分析反向数据流收敛性
寄存器分配图着色溢出策略
调用约定ABI 文档跨平台兼容
栈帧管理prologue / epilogue调试信息
指令编码ModR/M + SIB + REX位级操作

写一个能跑的 mini 编译器后端——这件事没有想象的难。1000 行 C++ 就能让 fib(10) 跑出 55。

难的是：

  • ABI 的细节（栈对齐、callee-saved、影子空间）
  • 寄存器分配的最优性
  • 指令编码的位级操作
  • 调试信息（DWARF）的正确性

这四点任何一个单独拿出来都是一本 500 页的书。我们这一篇做了”能跑”的最小集，剩下的交给 LLVM/Clang。

编译器后端是「程序员的最终边界」——你把 IR 给它，它给你机器码。理解这层，你才真正理解程序是怎么跑起来的。

下一篇预告（#4）：放弃手写后端，用 LLVM API 重写 mini 编译器——看工业级 SSA、MachinePass、Register Coalescer 怎么工作。预计 2026-07-01 发布。