4.3 控制流分析

4.3 控制流分析

本节摘要：控制流分析（Control-flow Analysis，CFA）从 CFG 里提取"控制怎么走"的结构性事实：哪些块构成循环、循环嵌套多深、图是否可约、函数体内有没有不可归约的怪图。这些事实决定优化能走多远——循环优化只对"结构良好的循环"全速工作，可约性是它的入场券。本节讲自然循环的正式定义（回边 + 支配关系）、循环树的构建、可约性的判定，以及不可约控制流的成因与处理。读完你应当能判断给定 CFG 的可约性，并说明为什么高级语言的循环几乎总是生成可约图。

数据流分析回答"值怎么流"，本节回答"控制怎么流"。乍看 4.2 已经把 CFG 用得团团转，其实它只用到了图的最基本信息（前驱/后继）；循环的结构、嵌套的层次这些更精细的事实，才是本节的主题。

一、为什么控制流需要"分析"而不只是"看图"

CFG 就摊在那里，块和边肉眼可见，似乎谈不上"分析"。但有两类问题肉眼给不了答案。其一，循环是个集合而非一条边：while 循环包含头块、体块、回边，还可能内嵌子循环——优化器需要把"这个循环的全部成员与出口"作为完整对象拿到手，才能整体改写（外提、展开、分块）。其二，形态决定可优化性：同样有环，for/while 生成的环结构规整（可约），goto 拼出来的怪环（不可约）会让循环识别失败，后续优化链全线下马。

控制流分析的经典产出是一棵循环树（loop forest）：叶是基本块，中间结点是循环，父循环包含子循环。每个优化 pass 拿着它定位"我要改的这段控制流"，第5章的循环优化全部运行在这棵树上。

二、回边与自然循环：从支配关系圈出循环

定义两步走。回边：边 t → h，其中 h 支配 t（h 是 t 的必经点）。直觉：要"绕回去"，回去的那个点必须不管走哪条路都躲不开——支配关系正是"必经"的形式化。自然循环：给定回边 t → h，循环体 = { h } ∪ { 所有能到达 t 且不经过 h 的块 }，h 是循环头。

算法实现是一次从 t 出发的反向遍历：

NaturalLoop(t, h):
    body = {h, t}
    stack = [t]
    while stack 非空:
        n = stack.pop()
        for p in preds(n):
            if p 不在 body:
                body.add(p); stack.push(p)
    return body            # 不越过 h，圈自然闭合
​

拿 4.2 的练习场验证：回边 B2 → B1（B1 支配 B2）。从 B2 反向爬：B2 ∈ body；B2 的前驱是 B1，已在 body。循环体 = {B1, B2}——与代码直觉一致。若 B2 与 B1 之间还隔着一条链（B2 → Bx → B1），反向遍历会把 Bx 也圈进来。

两条性质让自然循环特别适合做优化单元。一是同头合并：共用循环头的多条回边圈出的是同一个循环（把体取并集）；二是嵌套良构：两个自然循环要么不相交、要么一个含另一个（共享头时合并），所以循环树必然是树，不会出现"两个循环互相咬着尾巴"的病态。

图：回边、自然循环与循环树

三、可约性：循环优化的入场券

若 CFG 的全部回边圈出的自然循环都"首尾规整"（循环体只有一个入口，即循环头），图就是可约的（reducible）。等价的操作性说法：把回边删掉后剩下的是无环图，且每个环都能被"一个头 + 一条回边"完整捕获。结构化语言（只用 if/while/for/break）生成的 CFG 天然可约——这就是结构化控制流的工程红利：保证编译器总能把循环当循环看。

不可约从哪来？goto 跳进循环体中间、多线程代码展开后的交错跳转、以及某些手工汇编的翻译。看这个最小反例：两个块互相跳（B1→B2 且 B2→B1，谁也不支配谁），不存在"头"，没有回边，自然循环识别直接失灵。后果不是编译失败，而是降级：循环优化跳过它，只能靠通用优化收拾，性能差距可能拉到数倍。

工程上对不可约图有两条补救路：节点分裂（复制某个块，让环拥有支配头）把图改造回可约——代价是代码尺寸；区域分析（interval/T1-T2 分析）放弃"自然循环"改用更一般的可归约区域。现代编译器多走分裂这条路，因为分裂后的图反而给优化更多支点。

四、CFA 与 F：两个 CFA 的同名不同义

阅读文献时留意一个歧义：编译领域的 CFA 指本节的控制流分析（结构提取）；函数式程序分析文献里的 CFA（如 0CFA/1CFA）指控制流分析的高阶函数近似——分析"哪个闭包会流到哪个调用点"，本质是面向 lambda 的指针分析。两者共享"从源语言结构提取控制事实"的精神，但对象与技法不同。同理，第2章 2.2 出现过的支配树求法（Lengauer-Tarjan 近线性）属于本节主题的"怎么算"部分——支配、回边、循环，三者构成同一张结构网。

本节要点回顾：

• 回边定义：t → h 且 h 支配 t；自然循环 = 从 t 反向遍历收集、不越过 h 的块集；
• 循环树：自然循环两两不相交或嵌套，嵌套层数即循环深度，优化按内层优先；
• 可约性：所有环都被"单入口头 + 回边"捕获；结构化语言免费获得；
• 不可约的代价：循环优化整体跳过，补救靠节点分裂；
• 控制流分析喂饱下游：SSA 置放（支配边界）、循环优化（循环树）、寄存器分配（活跃范围）都从这里领任务。

回边定义依赖支配关系，而支配关系在 3.3 只是"用了一下"。下一节把它彻底讲完：支配树怎么算、支配边界公式怎么来、以及它们如何反过来解释 SSA。

一组快问快答

问：循环深度为什么值得单独计算？ 因为它是几乎所有代价模型里的"频度指数项"。4.2 的溢出权重、5.2 的展开决策、内联阈值（5.3），全都问同一个问题："这段代码在多深的循环里？"深度为 n 意味着执行频度可能是外层的迭代数之积——把深度算对，后面所有"值不值"的判断才有分母。

问：break 与 continue 会破坏自然循环吗？ 不会。break 多添一条出口边，continue 多添一条指向循环头的边——循环头不变、回边不变，自然循环照常识别。真正破坏结构的是 goto 跳进循环体中间（多入口循环，可约性破坏）与 goto 跳出多层嵌套后再跳回来（制造交叉的环）。结构化语言把最危险的两种跳转从语法上禁掉了，这是 4.3 说"结构化语言免费获得可约性"的准确含义。

问：函数调用怎么画进 CFG？ 直接调用视为一条普通指令（带一条"可能不返回"的出边——异常或长跳转），间接调用退化为"目标未知的出边"。函数内部的 CFG 就是本节的内容；函数之间的图是调用图，那是 5.3 过程间优化的地图。两个图层不要混——混了的典型症状是把调用开销错当成循环体开销参与优化决策。