代码优化

概念

代码优化是在中间代码上做保持语义不变的等价变换，让程序跑得更快、体积更小、或者更省电。

两个词必须先分清：

说法	含义	例
保语义变换	结果逐位不变，只是执行方式变了	3 * 4 编译期算成 12
换算法	结果近似或按新语义定义	把 x/2 改成 x*0.5（浮点下不等价）

编译器只做前者。-O2 下的程序必须和 -O0 下的程序结果完全一致（除非程序本身有未定义行为），否则编译器就是错的——这是优化最硬的一条红线。

优化的对象是 IR，不是源文件，也不是最终汇编。这一点承接 lang/20-steps.md 里六小步的第 ⑤ 步：优化发生在中间代码上，与目标机器无关。

原理

一、基本块与流图

优化的最小单位不是"整个函数"，而是基本块（basic block）：只有一个入口、一个出口，中间没有跳转进出的连续指令序列。

概念	定义
基本块入口	第一条指令，或是跳转的目标
基本块出口	最后一条指令，或是跳转指令本身
控制流图（CFG）	结点 = 基本块，边 = 可能的跳转方向

为什么要分块：块内没有跳转，指令顺序执行，所以可以放心地做"往前看、往后看"的分析——两侧都安全。

二、局部优化：一个基本块之内能做的七件事

动作	做什么	例
常量折叠	编译期把常量运算算完	3 * 4 → 12
常量传播	把已知常量的变量替换成常量	t1 = 12; t2 = t1 + 1 → t2 = 13
代数恒等	用代数规律化简	x * 0 → 0；x + 0 → x
强度削减	贵运算换便宜运算	x * 2 → x << 1；x / 4 → x >> 2
公共子表达式消除	重复计算只算一次	(a+b)*(a+b) → t=a+b; t*t
复制传播	跟进 t = x 这类复制	t = x; y = t + 1 → y = x + 1
死代码消除	删掉结果永不被使用、又无副作用的指令	折叠完留下的空壳

DAG 是局部优化的通用工具：把基本块里所有语句建成一张有向无环图，每个结点表示"一个值"。同一个值只建一个结点——于是公共子表达式自动被合并；图中的孤立结点就是死代码，直接删。

三、循环优化：收益最大的一块

程序的时间几乎都花在循环里，所以循环优化的性价比最高。

动作	做什么
循环不变量外提	值不随循环变的计算，挪到循环外算一次
强度削减	归纳表达式的乘法换成加法（i*4 → 每次 +4）
归纳变量消除	删掉只用来算另一个归纳变量的变量
循环展开	把循环体复制几份，减少循环控制开销
循环合并 / 分裂	两个同界循环合成一个；一个大循环拆成两个便于并行

循环不变量外提的例子：

优化前：                         优化后：
  for i = 0 to n-1:                t = x * y            ← 挪到循环外
      t = x * y                    for i = 0 to n-1:
      a[i] = a[i] + t                  a[i] = a[i] + t

x * y 与 i 无关，n 次循环里算了 n 遍。外提之后只算一遍：n = 1000 时就省下 999 次乘法。

四、全局优化：靠数据流分析

跨基本块的信息，只能用数据流分析算出来。四种最常用的：

分析	问的问题	用在
到达定值	这条指令处，某个变量的值可能来自哪儿	常量传播、定值-使用链
活跃变量	某点之后，这个变量的值还会被用吗	寄存器分配、死代码消除
可用表达式	某点处，某个表达式的值已经算过了吗	全局公共子表达式消除
定值-使用链	每个定值被哪些指令使用	几乎所有优化

方向是两类的：到达定值、可用表达式是前向分析（顺着控制流走）；活跃变量是后向分析（逆着控制流走）。"活跃变量"是后向分析这一点最常被记反。

五、三条不能碰的红线

情形	想做的变换	为什么不行
浮点结合律	(a+b)+c → a+(b+c)	浮点加法不满足结合律，低位结果会变
有副作用的表达式	f() + g() → g() + f()	两个函数的调用顺序可以被观察到（打印、写文件）
除零	x / 0 在编译期算成什么	编译期报错可以，但不能变成任意值

还有一类是语言级别禁止的：volatile 变量不许做常量传播、不许被消除，因为它的语义就是"每次都真的读写内存"。

示例

例 1：常量折叠与常量传播（C）

#include <stdio.h>
#include <string.h>

#define N 7

static char dst[N][8], op[N][4], a1[N][10], a2[N][10];

static int is_num(const char *s) {          /* 是不是十进制常量 */
    if (*s == '\0') return 0;
    for (const char *p = s; *p; p++)
        if (*p < '0' || *p > '9') return 0;
    return 1;
}
static int val(const char *s) {
    int v = 0;
    while (*s) v = v * 10 + (*s++ - '0');
    return v;
}

/* 变量名 -> 已知常量值；-1 表示不是常量 */
static char vname[16][8];
static int  vval[16], vcnt = 0;

static int find(const char *s) {
    for (int i = 0; i < vcnt; i++)
        if (strcmp(vname[i], s) == 0) return i;
    return -1;
}
static int value_of(const char *s) {
    if (is_num(s)) return val(s);
    int i = find(s);
    return (i >= 0) ? vval[i] : -1;
}
static void set_const(const char *s, int v) {
    int i = find(s);
    if (i < 0) { i = vcnt++; strcpy(vname[i], s); }
    vval[i] = v;
}

int main(void) {
    /* int f(int x, int y) { int a = 3 * 4 + 1; return a + x * 2 + y * 2; } */
    const char *D[N] = {"t1", "t2", "t3", "t4", "t5", "t6", "ret"};
    const char *O[N] = {"*", "+", "*", "*", "+", "+", "="};
    const char *A[N] = {"3", "t1", "x", "y", "t3", "t2", "t6"};
    const char *B[N] = {"4", "1", "2", "2", "t4", "t5", ""};
    for (int i = 0; i < N; i++) {
        strcpy(dst[i], D[i]); strcpy(op[i], O[i]);
        strcpy(a1[i], A[i]);  strcpy(a2[i], B[i]);
    }

    int folded = 0;
    for (int i = 0; i < N; i++) {
        if (strcmp(op[i], "=") == 0) continue;
        int x = value_of(a1[i]), y = value_of(a2[i]);
        if (x < 0 || y < 0) continue;                 /* 有一个不是常量，跳 */
        int v = 0;
        if (strcmp(op[i], "*") == 0) v = x * y;       /* 只有 * 和 + 两种 */
        if (strcmp(op[i], "+") == 0) v = x + y;
        sprintf(a1[i], "%d", v);
        a2[i][0] = '\0';
        strcpy(op[i], "c");
        set_const(dst[i], v);                         /* 记进常量表，供后面传播 */
        folded++;
    }

    printf("常量折叠：%d 条 IR 折成常量\n", folded);
    printf("=== 折叠后的 IR ===\n");
    for (int i = 0; i < N; i++) {
        if (op[i][0] == 'c' || strcmp(op[i], "=") == 0)
            printf("  %-5s = %s\n", dst[i], a1[i]);
        else
            printf("  %-5s = %s %s %s\n", dst[i], a1[i], op[i], a2[i]);
    }
    printf("=== 已知常量表 ===\n");
    for (int i = 0; i < vcnt; i++)
        printf("  %s = %d\n", vname[i], vval[i]);
    return 0;
}

c 本站为静态站，不提供在线运行；可复制到本地用 gcc / python 执行

预期输出：

常量折叠：2 条 IR 折成常量
=== 折叠后的 IR ===
  t1    = 12
  t2    = 13
  t3    = x * 2
  t4    = y * 2
  t5    = t3 + t4
  t6    = t2 + t5
  ret   = t6
=== 已知常量表 ===
  t1 = 12
  t2 = 13

例 2：一趟优化省下多少（Python 对照）

def pad(s, w):
    """按显示宽度补空格：中文算 2 列"""
    return s + " " * max(0, w - sum(2 if ord(c) > 0x2000 else 1 for c in s))


# 同一段源码：
#   int f(int x, int y) { int a = 3 * 4 + 1; return a + x * 2 + y * 2; }
IR0 = [
    ("t1", "3 * 4"),
    ("t2", "t1 + 1"),
    ("t3", "x * 2"),
    ("t4", "y * 2"),
    ("t5", "t3 + t4"),
    ("t6", "t2 + t5"),
    ("ret", "t6"),
]

print("=== 优化前：基本块共 %d 条 IR ===" % len(IR0))
for d, e in IR0:
    print("  " + pad(d, 6) + ("<- " if d == "ret" else "= ") + e)

STEPS = [
    ("第 1 遍 常量折叠", "3 * 4", "12", "编译期就把乘法算完"),
    ("第 1 遍 常量折叠", "t1 + 1", "13", "t1 已是常量，接着折"),
    ("第 2 遍 代数化简", "x*2 + y*2", "(x + y) * 2", "分配律：两次乘 2 合成一次"),
    ("第 3 遍 强度削减", "(x + y) * 2", "(x + y) << 1", "乘 2 换成左移 1 位"),
    ("第 4 遍 死代码消除", "t1 t2", "删除", "折成常量后没人再引用"),
]
print()
print("=== 逐遍优化 ===")
print("  " + pad("遍次", 24) + pad("优化前", 14) + pad("优化后", 14) + "规则")
for a, b, c, d in STEPS:
    print("  " + pad(a, 24) + pad(b, 14) + pad(c, 14) + d)

IR1 = [
    ("c", "13"),
    ("t", "x + y"),
    ("t2", "t << 1"),
    ("ret", "c + t2"),
]
print()
print("=== 优化后：基本块共 %d 条 IR ===" % len(IR1))
for d, e in IR1:
    print("  " + pad(d, 6) + ("<- " if d == "ret" else "= ") + e)
pct = 100.0 * (len(IR0) - len(IR1)) / len(IR0)
print("  -> IR 条数 %d -> %d，减少 %.1f%%" % (len(IR0), len(IR1), pct))

# ---- 公共子表达式消除单练 ----
print()
print("=== 公共子表达式消除：d = (a + b) * (a + b) ===")
CSE0 = ["t1 = a + b", "t2 = a + b        <- 算了两次", "t3 = t1 * t2", "d  = t3"]
CSE1 = ["t1 = a + b", "t2 = t1 * t1", "d  = t2"]
print("  优化前 %d 条：" % len(CSE0))
for s in CSE0:
    print("    " + s)
print("  优化后 %d 条：" % len(CSE1))
for s in CSE1:
    print("    " + s)
print("  -> %d 条 -> %d 条，省掉一次加法和一个临时量" % (len(CSE0), len(CSE1)))

# ---- 循环强度削减 ----
print()
print("=== 循环优化：a[i] = i * 4 的强度削减 ===")
BEFORE = ["t1 = i * 4", "t2 = base + t1", "store a[t2] = t1", "i = i + 1"]
AFTER = ["t1 = t1 + 4        # 归纳变量，循环外初始化 t1 = 0",
         "t2 = base + t1",
         "store a[t2] = t1"]
print("  优化前（每轮 %d 条 IR，含一条乘法）：" % len(BEFORE))
for s in BEFORE:
    print("    " + s)
print("  优化后（每轮 %d 条 IR，乘法变成加法）：" % len(AFTER))
for s in AFTER:
    print("    " + s)
n, mul_cyc, add_cyc = 1000, 4, 1
print("  假设 mul 4 周期、addu 1 周期：n = %d 时" % n)
print("    " + pad("优化前", 10) + "%d 条 IR/轮，%d x %d = %d 周期"
      % (len(BEFORE), n, mul_cyc, n * mul_cyc))
print("    " + pad("优化后", 10) + "%d 条 IR/轮，%d x %d = %d 周期"
      % (len(AFTER), n, add_cyc, n * add_cyc))
print("    -> 省 %d 周期（每轮 %d 周期）" % (n * (mul_cyc - add_cyc), mul_cyc - add_cyc))

# ---- 不能随便做的优化 ----
print()
print("=== 三条不能随便做的优化 ===")
CASES = [
    ("浮点结合律", "(a + b) + c", "a + (b + c)",
     "浮点加法不满足结合律，改了结果会变"),
    ("有副作用的表达式", "f() + g()", "g() + f()",
     "两个函数的调用顺序可以被观察到"),
    ("除零", "x / 0", "编译期报错",
     "编译期报错比运行期崩溃好，但不能变成任意值"),
]
print("  " + pad("情形", 20) + pad("原式", 18) + pad("想改成", 16) + "为什么不行")
for a, b, c, d in CASES:
    print("  " + pad(a, 20) + pad(b, 18) + pad(c, 16) + d)

print()
print("=== 优化级别与生成代码量（示意） ===")
print("  " + pad("级别", 8) + "汇编行数（相对 -O0）")
for lvl, ratio in [("-O0", 100), ("-O1", 72), ("-O2", 61), ("-Os", 48)]:
    print("  " + pad(lvl, 8) + "%d%%" % ratio)
print("  编译原理里的“优化”是“等价变换”，不是“猜一个更快的写法”")

python 本站为静态站，不提供在线运行；可复制到本地用 gcc / python 执行

预期输出：

=== 优化前：基本块共 7 条 IR ===
  t1    = 3 * 4
  t2    = t1 + 1
  t3    = x * 2
  t4    = y * 2
  t5    = t3 + t4
  t6    = t2 + t5
  ret   <- t6

=== 逐遍优化 ===
  遍次                    优化前        优化后        规则
  第 1 遍 常量折叠        3 * 4         12            编译期就把乘法算完
  第 1 遍 常量折叠        t1 + 1        13            t1 已是常量，接着折
  第 2 遍 代数化简        x*2 + y*2     (x + y) * 2   分配律：两次乘 2 合成一次
  第 3 遍 强度削减        (x + y) * 2   (x + y) << 1  乘 2 换成左移 1 位
  第 4 遍 死代码消除      t1 t2         删除          折成常量后没人再引用

=== 优化后：基本块共 4 条 IR ===
  c     = 13
  t     = x + y
  t2    = t << 1
  ret   <- c + t2
  -> IR 条数 7 -> 4，减少 42.9%

=== 公共子表达式消除：d = (a + b) * (a + b) ===
  优化前 4 条：
    t1 = a + b
    t2 = a + b        <- 算了两次
    t3 = t1 * t2
    d  = t3
  优化后 3 条：
    t1 = a + b
    t2 = t1 * t1
    d  = t2
  -> 4 条 -> 3 条，省掉一次加法和一个临时量

=== 循环优化：a[i] = i * 4 的强度削减 ===
  优化前（每轮 4 条 IR，含一条乘法）：
    t1 = i * 4
    t2 = base + t1
    store a[t2] = t1
    i = i + 1
  优化后（每轮 3 条 IR，乘法变成加法）：
    t1 = t1 + 4        # 归纳变量，循环外初始化 t1 = 0
    t2 = base + t1
    store a[t2] = t1
  假设 mul 4 周期、addu 1 周期：n = 1000 时
    优化前    4 条 IR/轮，1000 x 4 = 4000 周期
    优化后    3 条 IR/轮，1000 x 1 = 1000 周期
    -> 省 3000 周期（每轮 3 周期）

=== 三条不能随便做的优化 ===
  情形                原式              想改成          为什么不行
  浮点结合律          (a + b) + c       a + (b + c)     浮点加法不满足结合律，改了结果会变
  有副作用的表达式    f() + g()         g() + f()       两个函数的调用顺序可以被观察到
  除零                x / 0             编译期报错      编译期报错比运行期崩溃好，但不能变成任意值

=== 优化级别与生成代码量（示意） ===
  级别    汇编行数（相对 -O0）
  -O0     100%
  -O1     72%
  -O2     61%
  -Os     48%
  编译原理里的“优化”是“等价变换”，不是“猜一个更快的写法”

三条结论：

1. 7 条 IR 变 4 条，减少 42.9%；而 C 那段只做了常量折叠（2 条折成常量），没做代数化简与死代码消除——所以优化是一遍一遍跑的一串 pass，不是一步到位。
2. 常量折叠与常量传播是连锁的：3 * 4 折成 12 之后，t1 才进了常量表，t1 + 1 才可能被折成 13。先把结果记进常量表，后面才有的可传播。
3. 强度削减在循环里最值钱：每轮把一条乘法换成加法，n = 1000 时省 3000 个周期（假设乘 4 拍、加 1 拍），而代价只是一个额外的寄存器。

考点

考点

1. 基本块怎么划分

• 入口：函数第一条指令；任何跳转的目标；跳转指令的下一条。
• 出口：跳转指令；紧跟在条件跳转之后的指令之前。
• 判定口诀：凡是"别人能跳进来"或"自己能跳出去"的地方，都是块的边界。

2. 七个局部优化动作（能对着例子认出来）

常量折叠 / 常量传播 / 代数恒等 / 强度削减 / 公共子表达式消除 / 复制传播 / 死代码消除。

3. 循环优化的高频结论

• 循环不变量外提：前提是"这个计算在循环里每次结果都一样，且循环体每次都会执行到它"。
• 强度削减：i*c 换成加法需要引入归纳变量，代价是多占一个寄存器、并且要注意循环次数为 0 时不能进循环体。
• 循环展开的收益是减少判断与跳转次数，代价是代码体积变大、指令 Cache 可能不命中。

4. 四种数据流分析的方向（易错）

分析	方向
到达定值	前向
可用表达式	前向
活跃变量	后向
定值-使用链	双向（两条链）

5. 三条红线（几乎必考）

• 浮点不满足结合律 → 不许重排浮点加减。
• 函数调用顺序可观察 → 不许随意交换两侧都有副作用的表达式。
• volatile 不许优化 → 它存在的意义就是"每次真的读写内存"。

6. 常见陷阱

• x * 2 → x << 1 只对有符号非负或有位运算语义的类型成立；对有符号负数左移是未定义行为，现代编译器不会再这么改。
• 死代码消除必须先做"活跃变量"分析：一个赋值"看起来没用"，但它可能在被跳转到的别处被读。
• 优化级别越高不一定越快：-O2 会让代码变大，指令 Cache 反而可能变差；这时该用 -Os。
• "优化"不等于"改写算法"：O(n²) 冒泡不会因为 -O2 变成 O(n log n)。

小结

• 优化的铁律是保持语义：只做等价变换，红线是浮点结合律、副作用顺序、volatile。
• 战场是基本块 + 流图：块内靠 DAG，块间靠数据流分析。
• 最划算的是循环优化，而强度削减与不变量外提是其中最常用的两招。
• 观察口径：3*4+1 会在编译期消失，x*2+y*2 会被合成一次乘法再降成移位——"你写的 C"和"跑的码"不是一对一。

回到主线：上一章把语法树翻译成了三地址码，本章把这批三地址码改少了、改便宜了。但 IR 还不是机器能跑的东西——最后一章要把剩下的这 4 条 IR 落成真正的汇编：选指令、分寄存器、排顺序。

下一篇：目标代码生成