4. 基本块与流图：基本块的划分、支配树、回边与自然循环、可归约流图

好，咱们今天聊点实在的。基本块和流图，这俩概念是编译优化的地基。你想想看，编译器要优化代码，总得先知道代码是怎么跑的，对吧？基本块就是给代码画地图的最小单元。我个人习惯，拿到一段中间代码，第一件事就是把它切成基本块，然后构建流图。这一步做扎实了，后面的优化才能站得住脚。

什么是基本块？说白了，就是一段只能从入口进，只能从出口出的代码序列。里面没有分支，没有跳转，执行起来一气呵成。

划分基本块的规则其实很简单，我总结为「找领头羊」：

找到所有领头羊之后，从每个领头羊开始，一直往下走，直到遇到下一个领头羊或者函数结束，中间这一段就是一个基本块。

核心要点：基本块内部不能有停下来的指令（除了最后一条），也不能有从中间跳进来的入口。这是保证局部优化正确性的前提。

举个例子，看下面这段三地址码：

1:  a = 0
2:  b = a * 2
3:  if b < 10 goto 6
4:  c = b + 1
5:  goto 7
6:  c = b - 1
7:  d = c * 2
8:  return d

按照规则，领头羊是：指令1（入口）、指令6（跳转目标）、指令4（跳转指令的下一条）、指令7（跳转指令的下一条）。所以基本块划分如下：

我的小技巧：在实际项目中，我习惯用「扫描法」来划分。从头扫到尾，遇到跳转指令就标记下一个指令为领头羊，遇到跳转目标就标记目标指令为领头羊。一遍扫描搞定，效率很高。

基本块划分好了，接下来就是把这些块连起来，形成流图。流图是个有向图，节点是基本块，边代表控制流。从B1到B2有一条边，意味着B1执行完后可能直接进入B2。

有了流图，我们就可以聊支配关系了。这个概念很重要，我当年做全局优化时，没少跟它打交道。

支配的定义：如果从入口节点到节点n的每一条路径都经过节点d，那么d支配n。注意，每个节点都支配自己。

支配树就是把这种支配关系用树的形式表达出来。根节点是入口节点，每个节点的父节点是直接支配者（即最接近它的那个支配者）。

怎么算支配树？经典算法是Lengauer-Tarjan算法，复杂度接近线性。不过我个人建议，先用手工方式理解一下：

嗯，这里要注意，手工算的时候，迭代顺序很重要。我一般按拓扑序来，能少算好几轮。

为什么支配树重要？ 因为很多优化，比如循环不变式外提、代码移动，都需要知道一个代码位置是否「支配」另一个位置。支配树就是回答这个问题的利器。

有了支配树，我们就可以识别循环了。编译器里说的循环，跟程序员写的循环不完全一样。它更底层，是基于控制流图的。

回边：一条从节点n到节点d的边，如果d支配n，那么这条边就是回边。回边意味着什么？意味着从d出发，绕了一圈又回到了d，这就是循环的雏形。

举个例子，假设我们有这样的流图：

B1 → B2 → B3 → B4
     ↑           ↓
     └───────────┘

如果B1支配B2、B3、B4，那么从B4到B2的边就是回边。因为B2支配B4（假设路径只有这一条），所以B4→B2满足条件。

自然循环：给定一条回边n→d，自然循环就是由d以及所有能到达n且不被d之外的节点支配的节点组成的集合。说白了，就是回边能「兜住」的那部分节点。

自然循环有两个重要性质：

我曾经踩过的坑：不是所有的循环都是自然循环。比如用goto语句乱跳出来的循环，可能就不满足自然循环的定义。这种非自然循环，很多优化做不了，处理起来特别头疼。所以编译器里，我们通常只处理自然循环。

最后聊聊可归约流图。这个概念听起来高大上，其实理解起来不难。

可归约流图，就是可以通过反复删除「无分支的节点」和「回边」来化简成一个单节点的流图。换句话说，它没有那种乱七八糟的、跨多个层次的跳转。

为什么可归约流图重要？因为：

判断一个流图是否可归约，有个简单方法：对它进行深度优先遍历，如果所有回边都满足「目标节点支配源节点」，那么它就是可归约的。你想想看，这不就是我们刚才说的回边定义吗？

我的经验：在实际工程中，99%的代码产生的流图都是可归约的。如果你遇到了不可归约的流图，别急着优化，先想想能不能通过代码变换把它变成可归约的。比如节点分裂技术，就能把一些不可归约的流图「掰」成可归约的。

下面这张图，是我梳理的本章知识体系。你可以把它当作一个思维导图来看：

这张图把本章的核心知识点串起来了。从基本块划分开始，到流图构建，再到支配树、回边与自然循环，最后落到可归约流图。每一步都是下一步的基础，环环相扣。

好了，关于基本块与流图的内容，我就讲到这里。这些概念是编译优化的基石，你理解得越透彻，后面做循环优化、全局优化就越顺手。记住，好的优化从好的流图开始。