AST、IR 与 SSA：同一个表达式的三种表示

编译器先保留结构，再改变表示

表达式二加三再乘四得到二十。源代码中的括号告诉我们先做加法，抽象语法树AST把这种结构表示成节点：根是乘法，左孩子是加法，右孩子是常量四。AST不需要保留每个空格，却需要保留影响语义的运算关系。例一用一个很小的树求值器展示这个过程，不是完整C++解析器。

词法分析把字符变成token，语法分析按语言规则建立结构，语义分析还要检查名字、类型和操作是否合法。认识括号并不够：如果一个名字未声明，或某种类型不支持相加，编译器需要在适合的阶段拒绝程序。真实前端还处理作用域、模板、重载等复杂规则，本章只保留最小核心。

IR把分析需要的关系显式写出来

本节在 IR-45 I1的记号与SSA规则上应用树与名称表；以下保留片段是本章示意，不替代桥内的真实验证文件。

中间表示IR位于源语言和机器代码之间，可以让优化不必直接操作原始文本。一个表达式可以写成“t0=2+3；t1=t0*4；返回t1”。高层IR可能保留tensor操作和shape，低层IR更接近load、store、分支和机器相关类型。不存在一个对所有优化都最佳的唯一表示。

LLVM IR中的SSA要求一个SSA值名称只定义一次。源代码里反复赋值的x可以对应x0、x1、x2，每个新名字表示一个新的计算结果。分析者沿use-def关系追溯“这个值是谁算出来的”，不用把所有文本赋值逐行重新猜一遍。

; LLVM IR语法示意，未用LLVM工具链验证。
define i32 @twice_next(i32 %x) {
entry:
  %next = add i32 %x, 1
  %result = mul i32 %next, 2
  ret i32 %result
}

先备见 IR-45 I4的位宽、移位和额外承诺；以下在已授规则上讨论本片段的边界。

这个片段选择普通i32整数操作，没有添加nsw等额外承诺。具体溢出与poison规则属于IR语义，不能凭C++直觉擅自附加优化标记。输入五时结果十二；边界输入的语义需要按该IR操作合同解释。

多条控制路径怎样汇合

以下汇合与支配路径图是 IR-45 I2的phi与全路径规则在抽象名称表上的应用；正式首授与非法LLVM例子均在I2。

若条件为真时得到a，假时得到b，汇合点需要表达“来自哪条前驱边就选择哪份值”。LLVM通常用phi表达这种关系，不能理解成先无条件执行两边再随便选一个。某条路径包含无效访问时，擅自提前执行它可能改变程序行为。

例二不是LLVM verifier，而是原创SSA名称表：定义x0=5、x1=6、x2=12后，重复定义x1被拒绝。它检查最小的一次赋值规则；真实IR还必须满足类型、控制流、支配关系和操作语义。名称唯一只是必要条件。

一份定义必须覆盖哪些执行路径

只有一个定义，为什么有时仍不能使用它？先把连续执行、直到分支或返回的一段指令称为基本块；把可能跳转的方向画成箭头，得到控制流图。从函数入口沿箭头走到某个使用位置，每一种可能走法都是一条路径。对一个普通指令的操作数，定义必须在每条到达该使用的路径上先执行：这就是“定义支配使用”的直观判据。同一个基本块里，定义也必须排在使用之前。

下面是路径图，名字代表块和计算结果，不是可编译的LLVM语法：

             入口（选择一条分支）
              /             \
       左块：定义x=5       右块：未定义x
              \             /
                汇合：使用x

沿“入口→左块→汇合”走，读得到5；沿“入口→右块→汇合”走，却没有执行x的定义。因此左块不支配汇合块，汇合中的普通指令不能直接使用左块定义的x。虽然文本里x只定义了一次，这张图仍不满足要求；不能用“我这次恰好走左边”证明它合法。

第一种修法是在入口分支之前定义x，再让两条路径使用它。这样两条到达汇合的路径都经过定义。第二种情形是两边本来就要产生不同的结果：左边定义a=5，右边定义b=9，在汇合处用phi选择对应前驱的值。phi的每个输入被视为在对应的前驱边上使用：a需要沿左边的进入边有效，b需要沿右边的进入边有效；不能要求a也在右路径先算过，更不能把phi的边选择规则套到普通指令上。

自己检查：如果仍然只在左块定义x，把汇合中的普通使用移到左块定义之后，是否还会遇到右路径没有x的问题？不会：那次使用只在左路径执行，且在定义之后。这个结论只检查支配条件，类型和指令自身的其他条件仍要分别检查。定义与phi输入边的要求可核对 LLVM Language Reference 的良构性与phi规则。真实IR的符号逐项读法另由IR-45补授，本节没有用未解释的IR代码代替路径推演。

内存仍然可以变化

以下应用 IR-45 I3的alloca/load/store与SSA值、内存双表，继续讨论优化需要保留的内存关系。

SSA值一次定义，不意味着通过指针访问的内存只写一次。一个指针值可以保持不变，它指向的元素却被store修改；另一个指针可能指向同一位置。于是编译器仍需分析内存依赖和别名，才能安全删除load或重排写入。把SSA当“没有副作用的世界”会直接导致下一章中的错误优化。

怎样开始读编译器输出

先完成 IR-45 I5的真实属性与完整产物读法，再进 编译实验执行、改写与记录。

先找函数参数、基本块、返回值以及一条清楚的use-def链，再追踪load/store与分支。用一个小函数比较不同优化级别的输出，询问哪些操作消失、为什么等价。不要从看到较短IR就判断更快；最终机器代码、目标资源和实际输入仍会影响性能。

本章让你能够解释一段简单IR并识别关键约束。它没有实现编译器前端，也没有验证设备code object；原创C++例子只帮助把结构、值与名字这些抽象变成可以运行和检查的对象。

// Original CPU teaching model; not a device simulator or benchmark.
#include <iostream>
#include <vector>
#include <stdexcept>

void require(bool ok) { if (!ok) throw std::runtime_error("model check failed"); }

struct Node { char op; int value; int left; int right; };
int eval(const std::vector<Node>& nodes,int id) {
 const auto& n=nodes.at(static_cast<std::size_t>(id));
 if(n.op=='c') return n.value;
 const int a=eval(nodes,n.left),b=eval(nodes,n.right);
 if(n.op=='+') return a+b;
 require(n.op=='*');return a*b;
}
int main() {
 const std::vector<Node> tree{{'c',2,-1,-1},{'c',3,-1,-1},{'+',0,0,1},{'c',4,-1,-1},{'*',0,2,3}};
 const int result=eval(tree,4);require(result==20);std::cout<<"value="<<result<<'\n';
}

clang++ -std=c++20 -Wall -Wextra -Wpedantic -Werror -pthread 45-a.cpp -o example && ./example

value=20

// Original CPU teaching model; not a device simulator or benchmark.
#include <iostream>
#include <map>
#include <string>
#include <stdexcept>

void require(bool ok) { if (!ok) throw std::runtime_error("model check failed"); }

int main() {
 std::map<std::string,int> values;
 require(values.emplace("x0",5).second);
 require(values.emplace("x1",values.at("x0")+1).second);
 require(values.emplace("x2",values.at("x1")*2).second);
 const bool duplicate=values.emplace("x1",99).second;
 require(!duplicate && values.at("x2")==12);
 std::cout<<"result="<<values.at("x2")<<" redefinition=rejected\n";
}

clang++ -std=c++20 -Wall -Wextra -Wpedantic -Werror -pthread 45-b.cpp -o example && ./example

result=12 redefinition=rejected