为什么优化是编译原理的核心价值
编译器不仅要生成正确的代码，还要生成高效的代码。优化阶段通过分析程序行为并重写中间表示（IR）或目标代码，显著提升执行速度、减少内存占用。理解这些技术能帮助你在手写高性能代码时避开编译器陷阱，也能为开发DSL或JIT编译器打下基础。
基础优化：数据流分析
数据流分析是许多优化的基础，它通过静态分析程序路径上数据的定义与使用。以常量传播为例：若变量x被赋值为常量5，且之后未被修改，则所有使用x处可替换为5。实现需要构建控制流图（CFG）并计算每个基本块的到达定值。
死代码消除（DCE）则移除对结果无影响的代码。例如：int a = 1; int b = 2; int c = a+b; return c;中a和b的计算可被折叠为return 3。DCE常与常量传播联动，形成“简化-传播-删除”的迭代循环。
循环优化：程序性能的放大器
循环占据程序大部分执行时间，因此循环优化收益最大。核心技术包括：
- 循环不变式外提：将循环内不随迭代变化的计算移到循环前，如
for(i=0;ix*y。 - 强度削减：将乘法替换为加法，如将
i*10改为累加器j+=10。 - 循环展开：减少循环控制开销，但需权衡代码膨胀与缓存友好性。
实现这些优化需要识别循环结构（自然循环、支配节点）并维护循环信息。现代编译器（如GCC的-03）会自动应用，但了解原理有助于编写可向量化的代码。
寄存器分配：图着色算法
寄存器分配将虚拟寄存器映射到物理寄存器，当寄存器不足时需溢出到内存。经典方法是图着色：每个变量作为图节点，若两个变量在同一时刻活跃则连边，用K种颜色（寄存器数）着色，无法着色则溢出。例如LLVM的寄存器分配器采用线性扫描（linear scan）算法，更适合JIT场景。
实际工程中，还需考虑调用约定（哪些寄存器为调用者保存）、指令约束（某些指令要求特定寄存器）和变量生命周期。错误的分配会导致额外的内存访问，性能下降可达数倍。
指令级优化与调度
现代CPU采用流水线，指令顺序影响执行效率。指令调度通过重排指令减少停顿（如加载延迟）。此外，公共子表达式消除（CSE）可避免重复计算，例如a = b*c; d = b*c;可只计算一次。
一个实例：int x = arr[i] + arr[i];优化后变为int temp = arr[i]; int x = temp + temp;，避免两次内存访问。这类优化需要分析内存别名（两个指针是否可能指向同一地址），若无法确定则保守处理。
基于LLVM的优化实践
LLVM提供模块化的Pass基础设施。你可以编写一个自定义Pass来执行特定优化。以下是一个简单的常量折叠Pass框架：
// 伪代码
bool runOnFunction(Function &F) override {
for (auto &BB : F) for (auto &I : BB) {
if (auto *BO = dyn_cast<BinaryOperator>(&I)) {
if (auto *L = dyn_cast<ConstantInt>(BO->getOperand(0)))
if (auto *R = dyn_cast<ConstantInt>(BO->getOperand(1))) {
Constant *C = ConstantExpr::get(BO->getOpcode(), L, R);
BO->replaceAllUsesWith(C); return true;
}
}
}
return false;
}运行opt -passes=my-pass即可测试。建议从简单Pass开始，逐步理解Pass管理器如何调度分析结果。
设计可优化的IR
要获得良好优化效果，IR必须满足静态单赋值（SSA）形式，即每个变量只被赋值一次。SSA使数据流分析更高效，且便于实现稀疏条件常量传播。LLVM IR天然是SSA形式，而GIMPLE（GCC）也采用类似设计。
在自定义编译器中，建议采用三地址码并维护def-use链。避免使用复杂的内存操作，尽量使用临时变量，这样优化器能更自由地变换。
优化不是一次性的魔法，而是多个小变换的组合。理解每个优化的前提条件与收益，才能在正确场景下应用。
学习与实验建议
使用clang -O2 -S -emit-llvm查看优化后的IR，对比不同优化级别。尝试禁用某个优化（如-fno-tree-loop-optimize）观察性能变化。阅读《编译器设计》（Cooper & Torczon）的优化章节，并用LLVM的opt工具逐步调试你的Pass。最终目标是能识别哪些代码模式会阻碍优化（如过多指针别名），从而写出更易被优化的源码。