控制流图可归约性

结构化的 while 循环有一道门：第一次进入和以后回跳都经过循环头。可归约 CFG 允许嵌套、多个回边和复杂分支，但每个循环仍能围绕这样一个唯一入口组织。编译器因此可以把循环区域像括号一样嵌套，很多循环优化也能把 header 当作统一的检查与 φ 合流位置。

不可归约图的困难不是“存在环”，而是一个强连通区域有多个彼此不能支配的入口。执行可以从不同门直接钻进环中部，找不到单一 header 覆盖所有入口路径。这个性质属于控制结构，不直接断言程序语义错误或无法编译。

图 $r\to h,h\to a,a\to b,b\to h,h\to e$ 可归约：删去回边 $b\to h$ 后无环，且 $h$ 支配 $b$。其 natural loop 是 $\{h,a,b\}$，所有外部进入路径先到 $h$。即使再加 $a\to h$，仍可有多个回边共享同一 header，而不会破坏唯一入口。

不可归约的最小图可取 $r\to a,r\to b,a\to b,b\to a$。$\{a,b\}$ 强连通，却有从 $r$ 分别进入 $a,b$ 的两条边；$a$ 不支配 $b$，$b$ 也不支配 $a$。任选其中一条环边当“回边”，其头都不支配尾，故不能按上述方式分解。复制节点或插入调度变量可以把它结构化，但会改变图规模并需要单独证明语义。

不可归约不意味着 SSA 不存在。支配关系、支配边界和 φ 放置仍可在任意单入口可达 CFG 上定义；只是某些只按自然循环层次处理 φ、代码外提或循环退出的算法不能直接套用。类似地，可归约也不保证所有代码移动安全，副作用、陷阱与活跃性仍是额外条件。

结构化源语言在没有任意跳转、异常边扭曲或低层变换复制控制时通常产生可归约 CFG，但“通常”不是证明。间接跳转、异常处理、状态机生成器和优化后的低层控制流都可能形成多入口 SCC，分析器应检测性质后选择算法，而非依据源语言标签假定。

对可归约图，循环嵌套森林、自然循环和若干数据流求解顺序更容易建立；对不可归约图，可用 SCC 算法保守处理或先做 node splitting。选择结构化变换时要计入代码膨胀，并保持每个原路径的观察。可归约性是算法适用条件，不是编译正确性的替代品。

node splitting 的正确性也不能只看新图已经可归约。若复制 $a$ 为 $a_1,a_2$ 来分开两条入口，状态关系应把两个副本都解码回原控制点 $a$，并证明每条新边投影为原边、每个原执行至少有合适的新执行。复制含副作用的块若让同一次路径多执行一份指令，就改变了语义；正确变换复制的是控制位置与代码表示，不是把两个副本串行执行。