第3章基本块优化

3、基本块优化：基本块划分、局部值编号、死代码消除、代数化简

好，咱们今天聊聊基本块优化。说实话，这是编译器图优化里最基础、也最实在的一块。我早年刚接触编译器时，觉得这玩意儿太简单了，不就是把代码切几段嘛。后来真正做项目才发现，这里面的门道还真不少。

基本块优化，说白了就是在一个没有分支的直线代码段里，把能省的省掉，能合并的合并。你想想看，如果一段代码从头到尾没有跳转、没有分支，那它的执行路径是确定的。这种确定性，就是我们做优化的底气。

先说说基本块怎么划分。我个人习惯用「领头语句法」，简单粗暴：

嗯，这里要注意：一个基本块就是从一条领头语句开始，到下一条领头语句之前结束。中间不能有跳转指令，也不能被跳转指令指向。

我在项目中遇到过一种情况：有些同学把条件跳转的目标和跳转后的下一条语句搞混了。举个例子：

1:  a = b + c
2:  if a < 10 goto 4
3:  d = e + f
4:  g = h + i

这里，语句1是领头语句，语句4是跳转目标也是领头语句，语句3是跳转指令的下一条也是领头语句。所以基本块划分结果是：{1,2}、{3}、{4}。注意语句2和语句3不在同一个基本块里，因为语句2是跳转指令。

核心要点：基本块划分是后续所有优化的基础。划分错了，后面的优化全白做。

局部值编号（Local Value Numbering，LVN）是我个人非常喜欢的一个优化。它解决什么问题呢？就是在一个基本块内，避免重复计算相同的表达式。

举个例子：

a = x + y
b = x + y
c = a + b

你看，x+y被算了两次。用LVN的话，我们会给每个计算出来的值分配一个编号。第一次算x+y，编号为1。第二次遇到x+y，查一下发现已经算过了，直接复用编号1的值就行。

优化后变成：

a = x + y
b = a
c = a + a

我曾经在做一个AI推理引擎时，发现模型中有大量重复的子表达式计算。用LVN一跑，光这一个优化就省了将近15%的计算量。你想想看，这还只是基本块级别的优化。

小技巧：实现LVN时，可以用哈希表来维护表达式到编号的映射。键是操作符加操作数，值是编号。这样查找效率很高。

死代码消除，说白了就是删掉那些「写了等于没写」的代码。什么叫写了等于没写？就是计算结果后面再也没有被用到。

我刚开始做编译器时，总觉得死代码消除可有可无。直到有一次，我调试一个性能问题，发现生成的代码里有一大堆没用的赋值语句。一问才知道，是前端生成的中间表示里带了很多临时变量，后面优化没做干净。

死代码消除的规则其实很简单：

举个例子：

a = x + y
b = a * 2
c = b - 1
d = c + 3
// 后面再也没有用到 a, b, c, d

这段代码整个都是死的，可以直接删掉。但要注意：如果中间有函数调用或者写内存的操作，那就不能随便删了。

注意：死代码消除不能删除有副作用的语句。比如函数调用、写全局变量、写内存等。我曾经见过有人把printf给优化掉了，结果调试信息全没了，那叫一个惨。

代数化简，说白了就是利用数学上的恒等式来简化表达式。比如：

这些看起来简单，但在实际代码中出现的频率非常高。我做过一个统计，在典型的神经网络计算图中，大约有5%-10%的运算属于这种「恒等运算」。去掉它们，不仅省计算，还能让后续的优化更顺畅。

举个例子：

a = b + 0
c = a * 1
d = c - c
e = d + f

优化后：

a = b
c = a
d = 0
e = f

你看，一条链下来，最后就剩一个赋值了。这种优化在神经网络编译器中特别有用，因为很多模型在导出时会产生大量这种冗余运算。

实战经验：代数化简和局部值编号经常配合使用。先做代数化简，把表达式标准化，再做LVN，效果会更好。我习惯把代数化简放在LVN之前。

下面这张图展示了基本块优化的核心逻辑和流程：

这张图展示了基本块优化的完整流程。从中间表示开始，先做基本块划分，然后依次做代数化简、局部值编号、死代码消除。这三个优化可以反复迭代，直到没有新的优化机会为止。

我的建议：在实际工程中，不要只跑一遍优化。我习惯把这三步打包成一个pass，然后循环执行，直到收敛。通常3-5轮就能达到稳定状态。

好了，基本块优化就聊到这儿。这些技术看起来简单，但它们是整个编译器优化的基石。你想想看，如果连基本块级别的优化都做不好，那后面的全局优化、循环优化就更别谈了。记住：基础不牢，地动山摇。

公众号:蓝海资料掘金营，微信deep3321