用一段分支程序理解 BasicBlock、CFG 与 SSA

作者：lihao技术文章发布：2026-10-07LLVM 与异构编译器 · 第 08 期

从一段 if/else 程序生成并检查 LLVM IR，跟踪基本块、控制流边和 phi 的取值，再对照六组运行结果理解 SSA。

两条路径上的y，怎样合到一起

上一期的函数只有一条计算路径。现在加一个 if/else：两个分支给同一个变量 y 赋不同的值，函数出口应该返回哪一个？C++ 的写法很熟悉，但编译器还需要把“走了哪条路”和“值从哪里来”表示清楚。

extern "C" unsigned choose(unsigned x, bool take_left) {
  unsigned y;
  if (take_left) y = x + 1u;
  else y = x + 2u;
  return y;
}

这份代码没有循环，也没有复杂指针，正好用来分开理解三个概念：BasicBlock组织直线代码，CFG记录路径，SSA记录值的定义与使用。

生成适合观察分支的IR

实验环境：Ubuntu 24.04.4（WSL2，x86-64），Clang/LLVM 18.1.3，GNU binutils 2.42。

clang++-18 -std=c++17 -O0 -Xclang -disable-O0-optnone   -fno-discard-value-names -S -emit-llvm choose.cpp -o raw.ll
opt-18 -passes=mem2reg -verify-each -S raw.ll -o ssa.ll

这里先让 Clang 保留容易辨认的分支，再运行 mem2reg，把适合提升的栈槽读写整理成 SSA 值。-disable-O0-optnone是本次 Clang18 教学实验使用的内部选项，用来避免默认 O0 属性阻止后续优化，不作为跨版本稳定接口。

raw.ll 本来就使用 SSA 值。mem2reg 的作用不是让一个“完全没有 SSA 的语言”突然变成 SSA，而是把符合条件的内存读写提升到值层面。不是每一个 alloca 都能提升。

四个基本块，四个清楚的出口

本次 ssa.ll 的函数主体如下；省略函数属性、模块头和元数据，保留实际块名与指令：

entry:
  %frombool = zext i1 %take_left to i8
  %tobool = trunc i8 %frombool to i1
  br i1 %tobool, label %if.then, label %if.else

if.then:
  %add = add i32 %x, 1
  br label %if.end

if.else:
  %add1 = add i32 %x, 2
  br label %if.end

if.end:
  %y.0 = phi i32 [ %add, %if.then ], [ %add1, %if.else ]
  ret i32 %y.0

从每个标签往下读，到终结指令为止，就是这里的一个基本块。entry 的条件分支决定去哪个后继；if.then 和 if.else 各做一次加法，再跳到 if.end；最后一个块返回。终结指令不只有分支，ret 也会结束基本块。

CFG只保留控制流关系

             entry
          true / \ false
              /   \
        if.then   if.else
              \   /
              if.end
                ret

把基本块作为节点，把可能的控制转移作为边，就得到控制流图 CFG。图上的两条分支边表示可选路径，不表示一次调用会同时执行两边。这个函数在每次调用中只经过一个加法分支。

如果需要工具输出，本次也执行了下面的命令，生成 DOT 文件供检查。它不会自动完成图片渲染；本文的文字图依据实际块关系整理。

opt-18 -passes=dot-cfg -disable-output ssa.ll

SSA中的单次赋值，约束的是值名

源码里的 y 可以在两个分支中赋值。整理后的 IR 不再让同一个值名被反复赋值：%add、%add1 和 %y.0 各有自己的定义，后面的使用可以追溯到定义处。这里的“单次”说的是 IR 中的定义形式，不意味着一条指令在带循环的程序里只会动态执行一次。

内存也没有因此变成只读。store 仍可改变内存；指针、别名和副作用需要额外分析。不能把 SSA 理解成“整个程序中所有变量都不可变”。本例中的栈槽被提升，是因为这些特定用法满足提升条件。

phi根据刚才经过的边取值

%y.0 = phi i32 [ %add, %if.then ], [ %add1, %if.else ]

这行要和进入 if.end 的路径一起读：刚从 if.then 过来，就取 %add；刚从 if.else 过来，就取 %add1。方括号里是值和前驱块的配对，不是把两个结果相加，也不是重新计算两个分支。

phi 位于块开头；理解它时，先确认前驱边，再看对应值。本例没有多重边和循环回边，这两个复杂情况留给后续专门处理。

把IR重新编译，再检查结果

保存下面的 main.cpp：

#include <cstdio>
#include <climits>
#include <initializer_list>
extern "C" unsigned choose(unsigned, bool);
int main() {
  for (unsigned x : {0u, 7u, UINT_MAX}) {
    for (bool left : {false, true}) {
      unsigned want = x + (left ? 1u : 2u);
      unsigned got = choose(x, left);
      std::printf("x=%u left=%d got=%u expected=%u\n", x, left, got, want);
      if (got != want) return 1;
    }
  }
}

clang++-18 ssa.ll main.cpp -o demo
./demo
printf 'exit=%s\n' "$?"

本次六组输入全部符合预期，程序退出 0。UINT_MAX 分别加一、加二得到 0 和 1，这与本例无符号回绕一致。六组测试不是全输入证明，但能检查两条路径和一个明确的边界输入；类型与结构检查则由前面的验证器负责。

优化以后，分支为什么可能消失

clang++-18 -O1 -S -emit-llvm choose.cpp -o optimized.ll

本次 O1 输出的核心变成：

%3 = select i1 %1, i32 1, i32 2
%4 = add i32 %3, %0
ret i32 %4

现在先按条件选择 1 或 2，再做加法。这说明源代码的 if/else 不保证最终 IR 一定保留相同的 CFG。这里的表达式没有需要保留的分支副作用；不能把这个结果推广成任何含函数调用或内存副作用的分支都可以无条件合并。

select 是 IR 的值选择指令，也不保证最后一定生成某一条硬件条件选择指令。想知道机器怎么执行，还要继续观察目标代码。本期只建立从路径到值的对应关系，没有测量分支预测或运行性能。

支配关系怎样解释SSA中的“定义在使用之前”

直线代码中，定义排在使用前面比较直观；有分支时，文本位置在前并不保证每条路径都执行过定义。若从入口到某个使用点的每条路径都经过定义点，我们说定义点支配该使用点。SSA需要这种路径意义上的可用性。

在本例里，if.then中的%add不支配if.end中的普通指令，因为从if.else也可到达出口。phi把使用关联到对应前驱边：只有从if.then进入时才选%add，从另一条边进入时选%add1。它不是允许任意读取未执行分支的结果。

循环会让静态单一定义与动态多次执行同时出现。某个phi可以接收入口初值与回边更新值，表示每轮的新状态；名字在IR里只定义一次，并不意味着运行时只产生一次值。循环SSA需要同时追踪回边与支配关系，不能按文本从上到下解释全部执行。

为什么把分支改成select，不等于无条件执行两边

select选择已经可用的值，不是控制流指令。把含除法、可能陷阱的操作或有副作用的调用从分支搬到公共位置，可能让原本不会执行的运算被执行，因而改变行为。是否合法取决于被移动操作与IR语义，不能只看最终返回值相似。

本例两个分支只是无符号加法，O1把选择增量与加法组合起来，证据范围很清楚。若换成读写设备、volatile访问或不满足前提的除法，就不能照抄这一变换。poison在不同使用位置的传播也需要按具体指令规则检查。

后端还会把phi降低为适当的拷贝与寄存器约束，而不必生成一条叫phi的机器指令。CFG的语义、IR的值关系与硬件实现是相连的三个层次。可参照LLVM控制流教程继续核对phi与前驱的关系；本文六组运行不扩写为全输入或硬件分支性能证明。

2026-10-18内容修订：补支配、循环动态执行与投机执行边界。本次为文献与语义审校，未新增实验；首次发布日期、原网址及历史运行版本保持。

来源、验证范围与阅读路线

本期实测采用18.1.3；下列版本化文档来自18.1系列的18.1.8文档站，命令输出以本文实测为准。持续更新的官方页面用于补充原理，不据此改写旧版运行结果。

• LLVM语言参考：phi与select
• LLVM教程：控制流与phi
• LLVM教程：可变变量与mem2reg

实际四块CFG与phi已读取；六组运行（0、7、UINT_MAX各两条路径）全部通过。O1实际输出select再add。AArch64无关，不添加性能或硬件分支结论。

上一篇 · 下一篇：LLVM Pass 是什么？优化流水线如何组织 · 文章归档 · 知识体系

勘误：2026-10-07，初版。发现问题时请附工具版本、命令与关键输出；确认后在此记录修改。