1
class DAGISel:
2
    """基于 DAG 的指令选择"""
3

4
    def select(self, dag):
5
        """对 DAG 进行指令选择"""
6
        result = []
7

8
        for node in dag.topological_order():
9
            # 尝试匹配模式
10
            matched = self._match_patterns(node)
11

12
            if matched:
13
                # 选择代价最小的匹配
14
                best = min(matched, key=lambda m: m.cost)
15
                result.append(best.instruction)
16
            else:
17
                # 无匹配，使用默认选择
18
                result.append(self._default_select(node))
19

20
        return result
21

22
    def _match_patterns(self, node):
23
        """尝试所有模式匹配"""
24
        matches = []
25
        for pattern in self.patterns:
26
            if pattern.match(node):
27
                matches.append(pattern)
28
        return matches

1
// LLVM TableGen 中的指令模式
2
// 匹配：add %reg, imm → ADDri 指令
3
def : Pat<(add GPR:$src, imm:$imm), (ADDri GPR:$src, imm:$imm)>;
4

5
// 匹配：add %reg, %reg → LEA 指令（x86 特有优化）
6
def : Pat<(add GPR:$a, GPR:$b), (LEA32r GPR:$a, 1, GPR:$b, 0)>;
7

8
// 匹配：mul %reg, 2^k → shift 指令
9
def : Pat<(mul GPR:$src, PowerOf2Imm:$imm),
10
          (SHLri GPR:$src, (Log2 Imm:$imm))>;

1
// x86 寄存器定义
2
def RAX : X86Reg<"rax", 0>;
3
def RBX : X86Reg<"rbx", 3>;
4
def RCX : X86Reg<"rcx", 1>;
5
def RDX : X86Reg<"rdx", 2>;
6

7
// 寄存器类
8
def GR64 : RegisterClass<"X86", [i64], 64,
9
                          (add RAX, RCX, RDX, RBX, RSI, RDI,
10
                               R8, R9, R10, R11, R12, R13, R14, R15)>;
11

12
// 指令定义
13
def ADD64rr : I<0x01, MRMDestReg, (outs GR64:$dst),
14
                                     (ins GR64:$src1, GR64:$src2),
15
                "add{q}\t{$src2, $dst|$dst, $src2}",
16
                [(set GR64:$dst, (add GR64:$src1, GR64:$src2))]>;
17

18
// 指令模式（用于指令选择）
19
def : Pat<(add GR64:$src1, i64immSExt32:$imm),
20
          (ADD64ri32 GR64:$src1, i64immSExt32:$imm)>;

1
class ListScheduler:
2
    """列表调度算法"""
3

4
    def __init__(self, latency_table):
5
        self.latency = latency_table
6

7
    def schedule(self, dag):
8
        """对指令 DAG 进行调度"""
9
        ready = []       # 就绪指令（所有前驱已完成）
10
        scheduled = []   # 已调度指令
11
        remaining = set(dag.nodes)
12

13
        # 计算每个节点的优先级（关键路径长度）
14
        priority = self._compute_priority(dag)
15

16
        # 初始化就绪列表
17
        for node in dag.nodes:
18
            if not dag.predecessors(node):
19
                ready.append(node)
20

21
        cycle = 0
22
        while ready or remaining:
23
            # 按优先级排序就绪列表
24
            ready.sort(key=lambda n: priority[n], reverse=True)
25

26
            # 选择最高优先级的指令
27
            if ready:
28
                node = ready.pop(0)
29
                scheduled.append((cycle, node))
30
                remaining.remove(node)
31

32
                # 更新后继的就绪状态
33
                for succ in dag.successors(node):
34
                    if all(pred in [n for _, n in scheduled]
35
                           for pred in dag.predecessors(succ)):
36
                        ready.append(succ)
37

38
            cycle += 1
39

40
        return scheduled
41

42
    def _compute_priority(self, dag):
43
        """计算每个节点的关键路径长度"""
44
        priority = {}
45
        for node in reversed(list(dag.topological_order())):
46
            if not dag.successors(node):
47
                priority[node] = self.latency.get(node.op, 1)
48
            else:
49
                priority[node] = max(
50
                    priority[s] + self.latency.get(node.op, 1)
51
                    for s in dag.successors(node)
52
                )
53
        return priority

1
// 原始循环
2
for (int i = 0; i < n; i++) {
3
    a[i] = b[i] * c[i];  // load b, load c, mul, store a
4
}
5

6
// 软件流水后
7
// 预热阶段
8
load b[0]; load c[0];
9
// 内核阶段（每次迭代完成一个完整的操作）
10
for (int i = 0; i < n-1; i++) {
11
    mul b[i]*c[i];        // 当前迭代的乘法
12
    store a[i];           // 前一次迭代的存储
13
    load b[i+1];          // 下一次迭代的加载
14
    load c[i+1];          // 下一次迭代的加载
15
}
16
// 排空阶段
17
mul b[n-1]*c[n-1]; store a[n-1];

1
// LEA (Load Effective Address) 本来用于地址计算
2
// 但编译器经常用它做算术运算——它不设置标志位，可以与算术指令并行
3

4
// a + b → LEA rax, [rdi + rsi]
5
// a + b + 1 → LEA rax, [rdi + rsi + 1]
6
// a * 2 + b → LEA rax, [rdi + rsi*2]
7
// a * 4 + b + 10 → LEA rax, [rdi + rsi*4 + 10]

1
cat > isel_test.c << 'EOF'
2
int add_imm(int x) { return x + 10; }
3
int add_reg(int x, int y) { return x + y; }
4
int mul_shift(int x) { return x * 8; }
5
int complex_addr(int* p, int i) { return p[i + 1]; }
6
EOF
7

8
clang -O2 -S isel_test.c -o isel_test.s
9
cat isel_test.s | grep -E "(add|lea|shl|mov)" | head -20

1
clang -O2 -emit-llvm -S isel_test.c -o isel_test.ll
2
llc -debug-only=isel isel_test.ll -o isel_test.s 2>&1 | head -50

1
# x86-64
2
clang -O2 -S --target=x86_64 isel_test.c -o x86.s
3

4
# AArch64
5
clang -O2 -S --target=aarch64 isel_test.c -o arm.s
6

7
# RISC-V
8
clang -O2 -S --target=riscv64 isel_test.c -o riscv.s
9

10
# 对比
11
diff x86.s arm.s

1
// GlobalISel 的 GMIR 示例
2
// LLVM IR: %result = add i32 %a, %b
3
//
4
// GMIR (IRTranslator 输出):
5
// %1:_(s32) = COPY $w0      ; 参数 a
6
// %2:_(s32) = COPY $w1      ; 参数 b
7
// %3:_(s32) = G_ADD %1, %2  ; 通用加法
8
// $w0 = COPY %3             ; 返回值
9
//
10
// 目标 MIR (InstructionSelect 输出):
11
// %1:gpr32 = COPY $w0
12
// %2:gpr32 = COPY $w1
13
// %3:gpr32 = ADDWrr %1, %2
14
// $w0 = COPY %3

1
# ILP 利用示例
2
# 原始代码（串行依赖）
3
a = b + c      # 指令 1
4
d = a + e      # 指令 2（依赖指令 1 的结果）
5
f = g + h      # 指令 3（与指令 1/2 无关）
6

7
# 调度后（利用 ILP）
8
a = b + c      # 周期 0 发射
9
f = g + h      # 周期 0 发射（与指令 1 无关，可并行）
10
d = a + e      # 周期 1 发射（等指令 1 结果）