1
// 优化前
2
int x = 3 + 4;       // 运行时计算
3
int y = 2 * 3.14;    // 运行时计算
4
int z = "hello"[1];  // 运行时索引
5

6
// 优化后
7
int x = 7;           // 编译期计算
8
int y = 6.28;        // 编译期计算
9
int z = 'e';         // 编译期计算

1
class ConstantFolder:
2
    """常量折叠器"""
3

4
    def fold(self, op, *operands):
5
        """尝试折叠一个操作"""
6
        # 所有操作数必须是常量
7
        if not all(isinstance(op, Constant) for op in operands):
8
            return None
9

10
        values = [op.value for op in operands]
11

12
        # 整数运算
13
        if all(isinstance(v, int) for v in values):
14
            return self._fold_int_op(op, values)
15

16
        # 浮点运算
17
        if all(isinstance(v, (int, float)) for v in values):
18
            return self._fold_float_op(op, values)
19

20
        return None
21

22
    def _fold_int_op(self, op, values):
23
        ops = {
24
            '+': lambda a, b: a + b,
25
            '-': lambda a, b: a - b,
26
            '*': lambda a, b: a * b,
27
            '/': lambda a, b: a // b if b != 0 else None,
28
            '%': lambda a, b: a % b if b != 0 else None,
29
            '&': lambda a, b: a & b,
30
            '|': lambda a, b: a | b,
31
            '^': lambda a, b: a ^ b,
32
            '<<': lambda a, b: a << b,
33
            '>>': lambda a, b: a >> b,
34
        }
35
        if op in ops and len(values) == 2:
36
            result = ops[op](values[0], values[1])
37
            if result is not None:
38
                return Constant(result)
39
        return None
40

41
    def _fold_float_op(self, op, values):
42
        ops = {
43
            '+': lambda a, b: a + b,
44
            '-': lambda a, b: a - b,
45
            '*': lambda a, b: a * b,
46
            '/': lambda a, b: a / b if b != 0 else None,
47
        }
48
        if op in ops and len(values) == 2:
49
            result = ops[op](float(values[0]), float(values[1]))
50
            if result is not None:
51
                return Constant(result)
52
        return None

1
// 优化前
2
int x = 10;        // x 是常量
3
int y = x + 5;     // x 可以被替换为 10
4
int z = y * 2;     // y 可以被替换为 15
5

6
// 常量传播后
7
int x = 10;
8
int y = 10 + 5;    // x → 10
9
int z = 15 * 2;    // y → 15
10

11
// 常量折叠后
12
int x = 10;
13
int y = 15;
14
int z = 30;
15

16
// 死代码消除后（如果 x, y, z 不再使用）
17
// （空）

1
class ConstantPropagator:
2
    """常量传播器"""
3

4
    def __init__(self, cfg):
5
        self.cfg = cfg
6
        self.lattice = {}  # 变量 → 格值
7

8
    def propagate(self):
9
        """执行常量传播"""
10
        # 初始化：所有变量为 ⊤（未知）
11
        for block in self.cfg.blocks:
12
            for inst in block.instructions:
13
                if inst.result:
14
                    self.lattice[inst.result] = 'TOP'
15

16
        # 工作表算法
17
        worklist = list(self.cfg.blocks)
18
        while worklist:
19
            block = worklist.pop(0)
20
            changed = self._process_block(block)
21
            if changed:
22
                for succ in block.successors:
23
                    if succ not in worklist:
24
                        worklist.append(succ)
25

26
    def _process_block(self, block):
27
        changed = False
28
        for inst in block.instructions:
29
            if inst.op == 'const':
30
                # 常量定义
31
                old = self.lattice.get(inst.result, 'TOP')
32
                new = Constant(inst.operands[0])
33
                if old != new:
34
                    self.lattice[inst.result] = new
35
                    changed = True
36
            elif inst.op in ('add', 'sub', 'mul', 'div'):
37
                # 尝试传播和折叠
38
                operands = []
39
                for op in inst.operands:
40
                    if isinstance(op, str) and op in self.lattice:
41
                        val = self.lattice[op]
42
                        if isinstance(val, Constant):
43
                            operands.append(val)
44
                        else:
45
                            operands.append('TOP')
46
                    else:
47
                        operands.append(Constant(op) if isinstance(op, (int, float)) else 'TOP')
48

49
                if all(isinstance(o, Constant) for o in operands):
50
                    result = ConstantFolder().fold(inst.op, *operands)
51
                    if result:
52
                        old = self.lattice.get(inst.result, 'TOP')
53
                        if old != result:
54
                            self.lattice[inst.result] = result
55
                            changed = True
56
        return changed

1
// 优化前
2
int foo(int x) {
3
    int a = x * x;     // a 未使用 → 死代码
4
    int b = x + 1;     // b 未使用 → 死代码
5
    return x;           // 只有 x 被使用
6
}
7

8
// 优化后
9
int foo(int x) {
10
    return x;
11
}

1
class DeadCodeEliminator:
2
    """死代码消除器"""
3

4
    def eliminate(self, cfg):
5
        """删除所有死代码"""
6
        changed = True
7
        while changed:
8
            changed = False
9
            for block in cfg.blocks:
10
                new_insts = []
11
                for inst in block.instructions:
12
                    if self._is_dead(inst, cfg):
13
                        changed = True
14
                    else:
15
                        new_insts.append(inst)
16
                block.instructions = new_insts
17
        return cfg
18

19
    def _is_dead(self, inst, cfg):
20
        """判断指令是否是死代码"""
21
        # 终止指令永远不是死代码
22
        if inst.op in ('br', 'ret', 'jmp', 'label', 'phi'):
23
            return False
24

25
        # 有副作用的指令不是死代码
26
        if inst.op in ('store', 'call', 'invoke'):
27
            return False
28

29
        # 结果未被使用 → 死代码
30
        if inst.result and not self._is_used(inst.result, cfg):
31
            return True
32

33
        return False
34

35
    def _is_used(self, var, cfg):
36
        """检查变量是否被使用"""
37
        for block in cfg.blocks:
38
            for inst in block.instructions:
39
                if var in inst.operands:
40
                    return True
41
        return False

1
// 普通DCE无法删除（a 被使用）
2
int a = compute_something();  // 有副作用但结果不影响输出
3
int b = a;                    // b 也不影响输出
4
printf("hello");              // 这才是关键副作用
5

6
// ADCE 可以删除 a 和 b 的计算
7
// 因为它们不影响程序的可观察行为

1
// 优化前
2
int a = b + c;
3
int d = b + c;    // 与 a 相同的计算
4

5
// 优化后
6
int a = b + c;
7
int d = a;         // 复用 a 的值

1
class CSEEliminator:
2
    """公共子表达式消除器"""
3

4
    def eliminate(self, cfg):
5
        for block in cfg.blocks:
6
            available = {}  # 表达式 → 结果变量
7

8
            new_insts = []
9
            for inst in block.instructions:
10
                if inst.op in ('add', 'sub', 'mul', 'div'):
11
                    # 构造表达式键
12
                    key = (inst.op, tuple(sorted(inst.operands)))
13

14
                    if key in available:
15
                        # 找到公共子表达式，替换为已有结果
16
                        inst = IRInst('copy', inst.result, available[key])
17
                    else:
18
                        # 记录新表达式
19
                        available[key] = inst.result
20

21
                new_insts.append(inst)
22
            block.instructions = new_insts

1
class ValueNumberer:
2
    """值编号器"""
3

4
    def __init__(self):
5
        self.value_map = {}   # 表达式 → 值编号
6
        self.number = 0
7

8
    def get_value_number(self, op, operands):
9
        """获取表达式的值编号"""
10
        # 规范化操作数（交换律）
11
        if op in ('+', '*'):
12
            operands = tuple(sorted(operands))
13
        else:
14
            operands = tuple(operands)
15

16
        key = (op, operands)
17

18
        if key not in self.value_map:
19
            self.number += 1
20
            self.value_map[key] = self.number
21

22
        return self.value_map[key]
23

24
    def number_block(self, block):
25
        """对基本块进行值编号"""
26
        var_to_vn = {}  # 变量 → 值编号
27
        vn_to_var = {}  # 值编号 → 代表变量
28

29
        for inst in block.instructions:
30
            if inst.op in ('add', 'sub', 'mul', 'div'):
31
                # 将操作数从变量名转换为值编号
32
                vn_operands = tuple(
33
                    var_to_vn.get(op, op) for op in inst.operands
34
                )
35
                vn = self.get_value_number(inst.op, vn_operands)
36

37
                if vn in vn_to_var:
38
                    # 已有相同值的变量，可以替换
39
                    inst = IRInst('copy', inst.result, vn_to_var[vn])
40
                else:
41
                    vn_to_var[vn] = inst.result
42

43
                var_to_vn[inst.result] = vn

1
// 优化前
2
int foo(int x) {
3
    if (false) {           // 条件为假
4
        return 42;         // 不可达代码
5
    }
6
    return x + 1;
7
}
8

9
// SCCP 后
10
int foo(int x) {
11
    return x + 1;          // 不可达分支被删除
12
}

1
// 初始代码
2
int foo(int x) {
3
    int a = 10;
4
    int b = 20;
5
    int c = a + b;     // 常量折叠 → c = 30
6
    int d = x * 0;     // 乘零消除 → d = 0
7
    int e = d + c;     // 常量传播 → e = 0 + 30 = 30
8
    if (d != 0) {       // 条件常量传播 → d = 0 → 条件为假
9
        e = 100;        // 死代码
10
    }
11
    return e;           // 常量传播 → return 30
12
}
13

14
// 优化后
15
int foo(int x) {
16
    return 30;
17
}

1
# 查看 LLVM 的优化流水线
2
opt -passes='default<O2>' -debug-pass-manager input.ll -o /dev/null 2>&1 | head -50
3

4
# 典型的优化顺序
5
# 1. mem2reg（SSA 提升）
6
# 2. sccp（稀疏条件常量传播）
7
# 3. dce（死代码消除）
8
# 4. cse（公共子表达式消除）
9
# 5. instcombine（指令合并）
10
# 6. gvn（全局值编号）
11
# 7. licm（循环不变量外提）
12
# 8. indvars（归纳变量简化）
13
# 9. loop-unroll（循环展开）
14
# 10. tailcallelim（尾调用消除）

1
# 使用上面的 ConstantPropagator 和 DeadCodeEliminator
2
source = """
3
int main() {
4
    int a = 10;
5
    int b = 20;
6
    int c = a + b;
7
    int d = c * 0;
8
    return c;
9
}
10
"""
11

12
# 编译到 IR
13
# ... (使用前面章节的词法分析、语法分析、IR 生成)
14

15
# 优化
16
propagator = ConstantPropagator(cfg)
17
propagator.propagate()
18

19
eliminator = DeadCodeEliminator()
20
optimized_cfg = eliminator.eliminate(cfg)
21

22
# 查看优化后的 IR
23
for block in optimized_cfg.blocks:
24
    for inst in block.instructions:
25
        print(inst)

1
# 创建测试文件
2
cat > opt_test.c << 'EOF'
3
int foo(int x) {
4
    int a = 10;
5
    int b = 20;
6
    int c = a + b;
7
    int d = x * 0;
8
    int e = d + c;
9
    return e;
10
}
11
EOF
12

13
# 生成未优化的 IR
14
clang -emit-llvm -S -O0 opt_test.c -o opt_test_O0.ll
15

16
# 逐步优化
17
opt -passes=instcombine opt_test_O0.ll -S -o step1.ll    # 指令合并
18
opt -passes=sccp step1.ll -S -o step2.ll                  # 常量传播
19
opt -passes=dce step2.ll -S -o step3.ll                   # 死代码消除
20

21
# 对比每一步
22
diff opt_test_O0.ll step1.ll
23
diff step1.ll step2.ll
24
diff step2.ll step3.ll
25

26
# 一步到位
27
clang -emit-llvm -S -O2 opt_test.c -o opt_test_O2.ll
28
diff step3.ll opt_test_O2.ll

1
int compute(int x) {
2
    int a = 100;
3
    int b = 200;
4
    int c = a + b;
5
    int d = x * 0;
6
    int e = d + c;
7
    if (d > 0) {
8
        e = 999;
9
    }
10
    return e;
11
}