1
class LivenessAnalyzer:
2
    """活跃变量分析"""
3

4
    def analyze(self, cfg):
5
        """计算每个程序点的活跃变量集合"""
6
        # 后向数据流分析
7
        live_in = {block: set() for block in cfg.blocks}
8
        live_out = {block: set() for block in cfg.blocks}
9

10
        changed = True
11
        while changed:
12
            changed = False
13
            for block in reversed(cfg.blocks):
14
                # live_out(B) = ∪ live_in(S) for all successors S
15
                new_out = set()
16
                for succ in block.successors:
17
                    new_out |= live_in[succ]
18

19
                # live_in(B) = use(B) ∪ (live_out(B) - def(B))
20
                use = self._compute_use(block)
21
                defn = self._compute_def(block)
22
                new_in = use | (new_out - defn)
23

24
                if new_in != live_in[block] or new_out != live_out[block]:
25
                    changed = True
26
                    live_in[block] = new_in
27
                    live_out[block] = new_out
28

29
        return live_in, live_out

1
class InterferenceGraph:
2
    """干涉图"""
3

4
    def __init__(self):
5
        self.nodes = set()       # 虚拟寄存器集合
6
        self.edges = set()       # 干涉边集合
7
        self.move_edges = set()  # 移动指令边（用于合并）
8

9
    def add_node(self, v):
10
        self.nodes.add(v)
11

12
    def add_interference(self, v1, v2):
13
        if v1 != v2:
14
            self.edges.add((min(v1, v2), max(v1, v2)))
15

16
    def add_move(self, v1, v2):
17
        self.move_edges.add((v1, v2))
18

19
    def neighbors(self, v):
20
        return {u for u in self.nodes if (min(v, u), max(v, u)) in self.edges}
21

22
    def degree(self, v):
23
        return len(self.neighbors(v))
24

25
def build_interference_graph(cfg, live_ranges):
26
    """从活跃范围构建干涉图"""
27
    ig = InterferenceGraph()
28

29
    for block in cfg.blocks:
30
        live = set(live_ranges[block].live_out)
31

32
        for inst in reversed(block.instructions):
33
            # 定义点：变量开始不活跃
34
            if inst.result:
35
                ig.add_node(inst.result)
36
                # 与当前活跃的所有变量干涉
37
                for v in live:
38
                    if v != inst.result:
39
                        ig.add_interference(inst.result, v)
40

41
            # 使用点：变量开始活跃
42
            for operand in inst.operands:
43
                if isinstance(operand, str) and operand.startswith('%'):
44
                    ig.add_node(operand)
45
                    live.add(operand)
46

47
            # 从活跃集合中移除定义点
48
            if inst.result:
49
                live.discard(inst.result)
50

51
            # 记录移动指令
52
            if inst.op == 'copy' or inst.op == 'mov':
53
                ig.add_move(inst.result, inst.operands[0])
54

55
    return ig

1
class GraphColoringAllocator:
2
    """图着色寄存器分配器"""
3

4
    def __init__(self, num_registers):
5
        self.K = num_registers  # 可用物理寄存器数
6

7
    def allocate(self, ig):
8
        """使用简化-选择算法进行图着色"""
9
        stack = []
10
        graph = ig  # 工作副本
11

12
        # 阶段 1：简化（Simplify）
13
        while graph.nodes:
14
            # 选择度数 < K 的节点
15
            low_degree = [v for v in graph.nodes if graph.degree(v) < self.K]
16

17
            if low_degree:
18
                # 移除度数最低的节点
19
                node = min(low_degree, key=lambda v: graph.degree(v))
20
                graph.nodes.remove(node)
21
                neighbors = graph.neighbors(node)
22
                # 保存邻居信息用于后续恢复
23
                stack.append((node, neighbors, graph.edges))
24
                # 移除相关边
25
                graph.edges = {(a, b) for a, b in graph.edges
26
                              if a != node and b != node}
27
            else:
28
                # 所有节点度数 >= K，需要溢出
29
                # 选择溢出代价最低的节点
30
                spill_node = self._select_spill(graph)
31
                graph.nodes.remove(spill_node)
32
                neighbors = graph.neighbors(spill_node)
33
                stack.append((spill_node, neighbors, graph.edges))
34
                graph.edges = {(a, b) for a, b in graph.edges
35
                              if a != spill_node and b != spill_node}
36

37
        # 阶段 2：选择（Select）
38
        coloring = {}
39
        while stack:
40
            node, neighbors, old_edges = stack.pop()
41
            # 找到邻居未使用的颜色
42
            used_colors = {coloring[n] for n in neighbors if n in coloring}
43
            available = set(range(self.K)) - used_colors
44

45
            if available:
46
                coloring[node] = min(available)
47
            else:
48
                # 溢出（需要重新分配）
49
                coloring[node] = -1  # 标记为溢出
50

51
        return coloring
52

53
    def _select_spill(self, graph):
54
        """选择溢出代价最低的节点"""
55
        # 启发式：选择度数最高但使用频率最低的节点
56
        return max(graph.nodes, key=lambda v: graph.degree(v))

1
class LinearScanAllocator:
2
    """线性扫描寄存器分配器"""
3

4
    def __init__(self, num_registers):
5
        self.K = num_registers
6

7
    def allocate(self, intervals):
8
        """
9
        intervals: 活跃区间列表，每个区间 (start, end, var_name)
10
        """
11
        # 按起始点排序
12
        intervals.sort(key=lambda x: x[0])
13

14
        active = []       # 当前活跃的区间（按结束点排序）
15
        allocation = {}   # 变量 → 物理寄存器
16
        free_regs = list(range(self.K))  # 空闲寄存器池
17

18
        for interval in intervals:
19
            # 过期：移除已结束的活跃区间
20
            active = [a for a in active if a[1] > interval[0]]
21
            for a in active:
22
                if a[1] <= interval[0]:
23
                    free_regs.append(allocation[a[2]])
24

25
            if len(active) == self.K:
26
                # 溢出：溢出结束点最远的区间
27
                spill = max(active, key=lambda x: x[1])
28
                if spill[1] > interval[1]:
29
                    # 溢出 spill，将 interval 分配到 spill 的寄存器
30
                    allocation[interval[2]] = allocation[spill[2]]
31
                    allocation[spill[2]] = -1  # 标记溢出
32
                    active.remove(spill)
33
                    active.append(interval)
34
                else:
35
                    # 溢出当前区间
36
                    allocation[interval[2]] = -1
37
            else:
38
                # 分配空闲寄存器
39
                reg = free_regs.pop(0)
40
                allocation[interval[2]] = reg
41
                active.append(interval)
42

43
        return allocation

1
// 无溢出：全部在寄存器中
2
add rax, rbx     ; 寄存器加法，1 周期
3

4
// 有溢出：需要 load/store
5
mov [rsp+8], rax  ; 保存 rax 到栈
6
mov rax, [rsp+16] ; 从栈加载溢出变量
7
add rax, rbx      ; 执行加法
8
mov rax, [rsp+8]  ; 恢复 rax

1
def estimate_spill_cost(var, loop_depth, use_count, def_count):
2
    """估计溢出一个变量的代价"""
3
    # 循环内的溢出代价更高
4
    loop_weight = 10 ** loop_depth
5

6
    # 每次 use/def 需要 load/store
7
    cost = (use_count + def_count) * loop_weight
8

9
    return cost

1
// 优化前
2
mov rax, rbx    ; copy 指令
3
add rax, rcx
4

5
// 合并后（rbx 和 rax 分配同一物理寄存器）
6
add rbx, rcx    ; copy 被消除

1
class Coalescer:
2
    """寄存器合并器"""
3

4
    def coalesce(self, ig, allocation):
5
        """合并 copy 相关的虚拟寄存器"""
6
        changed = True
7
        while changed:
8
            changed = False
9
            for v1, v2 in list(ig.move_edges):
10
                # 检查是否可以合并
11
                if not self._interferes(ig, v1, v2):
12
                    # 合并 v2 到 v1
13
                    self._merge(ig, v1, v2)
14
                    allocation[v2] = allocation[v1]
15
                    changed = True
16

17
        return allocation
18

19
    def _interferes(self, ig, v1, v2):
20
        """检查两个变量是否干涉"""
21
        return (min(v1, v2), max(v1, v2)) in ig.edges
22

23
    def _merge(self, ig, v1, v2):
24
        """合并两个节点"""
25
        # 将 v2 的所有边转移到 v1
26
        for neighbor in ig.neighbors(v2):
27
            ig.add_interference(v1, neighbor)
28

29
        # 移除 v2
30
        ig.nodes.discard(v2)
31
        ig.edges = {(a, b) for a, b in ig.edges if a != v2 and b != v2}
32
        ig.move_edges.discard((v1, v2))
33
        ig.move_edges.discard((v2, v1))

1
// 除法指令固定使用 RDX:RAX
2
idiv rbx    ; RAX = RDX:RAX / rbx, RDX = RDX:RAX % rbx
3

4
// 系统调用固定使用 RAX（调用号）
5
mov rax, 1  ; sys_write
6
syscall
7

8
// 移位指令固定使用 CL
9
shl rax, cl ; 移位量必须在 CL 中

1
// 低寄存器压力：3 个变量，6 个寄存器足够
2
void low_pressure(int* a, int* b, int* c, int n) {
3
    for (int i = 0; i < n; i++) {
4
        c[i] = a[i] + b[i];  // i, a[i], b[i], c[i] → 4 个寄存器
5
    }
6
}
7

8
// 高寄存器压力：8 个变量，6 个寄存器不够
9
void high_pressure(int* a, int* b, int* c, int* d,
10
                   int* e, int* f, int* g, int* h, int n) {
11
    for (int i = 0; i < n; i++) {
12
        h[i] = a[i]*b[i] + c[i]*d[i] + e[i]*f[i] + g[i];
13
        // 需要 a,b,c,d,e,f,g,h,i → 9 个寄存器
14
    }
15
}

1
cat > reg_alloc.c << 'EOF'
2
int add(int a, int b) { return a + b; }
3
int complex(int a, int b, int c, int d, int e, int f) {
4
    return a*b + c*d + e*f;
5
}
6
EOF
7

8
clang -O0 -S reg_alloc.c -o reg_O0.s
9
clang -O2 -S reg_alloc.c -o reg_O2.s
10

11
# 对比：-O0 大量使用栈，-O2 全部在寄存器中
12
grep -c "mov.*rsp" reg_O0.s reg_O2.s

1
cat > spill.c << 'EOF'
2
// 故意制造高寄存器压力
3
int spill_test(int a, int b, int c, int d,
4
               int e, int f, int g, int h) {
5
    return a + b + c + d + e + f + g + h;
6
}
7
EOF
8

9
clang -O2 -S spill.c -o spill.s
10
# 查看是否有 spill/reload 指令
11
grep -E "(spill|reload|mov.*rsp)" spill.s

1
# 查看 LLVM 的寄存器分配过程
2
clang -O2 -emit-llvm -S spill.c -o spill.ll
3
llc -debug spill.ll -o spill.s 2>&1 | grep -i "regalloc\|spill\|assign"