Pass简介——constraint-elimination

这个 pass 的主要作用是利用先前支配的条件中收集到的约束信息，来简化或消除后续基本块中的条件判断。换句话说，它会分析控制流图，识别那些由于前置条件已经确定了某些变量的取值，从而使得后续条件表达式恒为真或恒为假的情况，然后用常量替换或直接消除这些冗余的分支判断。
有关资料：

OK，回归正题，这个 Pass 约 2000 行，是一个偏简单的 Pass，从其用途来看，就是需要通过“记忆”推导一些常量。

前置依赖

想要运行这个 pass，需要：

auto &DT = AM.getResult<DominatorTreeAnalysis>(F);  
auto &LI = AM.getResult<LoopAnalysis>(F);  
auto &SE = AM.getResult<ScalarEvolutionAnalysis>(F);  
auto &ORE = AM.getResult<OptimizationRemarkEmitterAnalysis>(F);

即：

支配树分析：分析哪些基本块控制其他基本块执行（龙书有一章讲的很全）
循环分析：尤其是循环层次树（LoopNest）
标量演化分析（SCEV）：==推导标量的变化过程==

优化备注分析（可能没怎么接触过）：像 LLVM 诊断引擎发送优化信息，便于调试和分析优化效果。

选项分析

static cl::opt<unsigned>  
    MaxRows("constraint-elimination-max-rows", cl::init(500), cl::Hidden,  
            cl::desc("Maximum number of rows to keep in constraint system"));  
  
static cl::opt<bool> DumpReproducers(  
    "constraint-elimination-dump-reproducers", cl::init(false), cl::Hidden,  
    cl::desc("Dump IR to reproduce successful transformations."));

显然也是一个有复杂度的算法，毕竟要限制分析的范围。

主流程

在主函数中，第一步会收集函数里的所有基本块的所有条件信息：

整数比较：icmp
llvm.assume 语句
abs() 绝对值函数
min/max 计算
第二步：实现一个约束待处理队列，Pass 需要按照控制流执行顺序处理这些约束。stable排序规则：
支配关系强的在前
常量比较条件优先

保证同一个基本块的条件顺序
第三步：遍历 WorkList，进行约束传播：例如如下情况

if (x > 10) {
  if (x > 5) { ... }  // `x > 5` 恒成立，删除
}

__builtin_assume(x > 10);
if (x > 5) { ... }  // `x > 5` 恒成立，删除

int y = abs(x);
if (y < 0) { ... }  // `y < 0` 永远不可能成立，删除

第四步：处理 icmp、min/max、overflow：

int a = min(x, y);
if (a > x) { ... }  // `a` 不可能大于 `x`，删除

第五步：删除已优化的命令