llvm进阶（2）LowerSwitch（Switch 到 Branch 的奥秘）

在编译器的优化过程中，Switch`指令的处理是一个既经典又充满挑战的问题。Switch`作为一种高效的多路分支结构，广泛存在于高级语言的代码中，但在底层实现中，不同硬件平台对 Switch`指令的支持程度却大相径庭。为了兼容性和性能优化，LLVM 引入了 LowerSwitch 这一重要转换：它将 Switch 指令重写为一系列 Branch指令，从而让目标平台可以暂时规避对 Switch指令的直接支持，直到更方便时再实现。

本文将简要解读 LowerSwitch 的部分源码，和看一下实现后的结果。

# 1.runOnfunction

```c

bool LowerSwitchLegacyPass::runOnFunction(Function &F) {

//获取 LazyValueInfo 对象，用于值推断和优化

LazyValueInfo *LVI = &getAnalysis<LazyValueInfoWrapperPass>().getLVI();

//尝试获取 AssumptionCacheTracker 对象，用于管理 AssumptionCache

auto *ACT = getAnalysisIfAvailable<AssumptionCacheTracker>();

//获取与函数 F 相关的 AssumptionCache 对象，如果 AssumptionCacheTracker 不存在，则设置为 nullptr

AssumptionCache *AC = ACT ? &ACT->getAssumptionCache(F) : nullptr;

return LowerSwitch(F, LVI, AC);

}

```

开篇中已经描述lowerSwitch的作用，在runOnfunction函数中，看到传入了LazyValueInfo、AssumptionCache，在这里由于篇幅原因，介绍下这两个类的用途，和在swithtobranch的作用。

## 1.1LazyValueInfo 的作用

`LazyValueInfo` 是 LLVM 中的一个分析工具，用于“惰性”地计算某些值的信息。在 `LowerSwitch` 中，`LazyValueInfo` 的作用主要体现在以下方面：1.值范围分析:LowerSwitch 需要分析 Switch 指令中每个 case 的值范围，以确定如何将 Switch 转换为 Branch。LazyValueInfo 提供了高效的值范围分析能力，帮助 LowerSwitch 快速判断哪些 case 可以被合并或优化。2.条件优:在某些情况下，Switch 的条件可能可以被简化。例如，如果某个 case 的值范围已经被 LazyValueInfo 确定为不可能，LowerSwitch 可以直接跳过该分支，从而减少生成的 Branch 指令数量。

## 1.2AssumptionCache的作用

`AssumptionCache` 是 LLVM 中用于管理“假设”的工具。在 `LowerSwitch` 中，`AssumptionCache` 的作用主要体现在以下方面：1.假设利用LowerSwitch 可以利用 AssumptionCache 中记录的假设，例如“某个变量的值范围已经被限定”，从而优化 Switch 的转换过程。例如，如果 AssumptionCache 中记录了某个变量的值不可能为负数，LowerSwitch 可以忽略所有负数的 case，从而简化生成的代码。2.代码安全性AssumptionCache 还可以帮助 LowerSwitch 确保转换后的代码在语义上是安全的。例如，如果某个假设被违反，LowerSwitch 可以生成额外的检查代码，避免运行时错误。

# 2.LowerSwitch

2.1遍历函数的基本块

LowerSwitch 会遍历函数的所有基本块（BasicBlock），检查每个基本块的终止指令是否是 SwitchInst。如果是，则对其进行处理。

2.2处理 Switch 指令

对于每个 SwitchInst，LowerSwitch 会调用 ProcessSwitchInst 函数，将其转换为更简单的分支结构。同时，可能会将一些基本块标记为待删除。

2.3清理待删除的基本块

在处理完所有 SwitchInst 后，LowerSwitch 会遍历待删除的基本块列表，调用 DeleteDeadBlock 函数将其删除，并更新 LazyValueInfo 中的相关数据。

```c

bool LowerSwitch(Function &F, LazyValueInfo *LVI, AssumptionCache *AC) {

// 用于记录函数 F 是否被修改过

bool Changed = false;

// 用于存储需要删除的基本块（BasicBlock）的集合

// SmallPtrSet 是一个优化过的集合类，适用于存储少量元素（这里容量为 8）

SmallPtrSet<BasicBlock *, 8> DeleteList;

// 遍历函数 F 的所有基本块

// Function::iterator I 是当前迭代器，E 是结束迭代器

for (Function::iterator I = F.begin(), E = F.end(); I != E;) {

// 获取当前基本块 Cur，并将迭代器 I 向前移动

// 这样可以在处理过程中跳过新添加的基本块

BasicBlock *Cur =

&*I++; // Advance over block so we don't traverse new blocks

// 如果当前基本块 Cur 在 DeleteList 中，表示它已经被标记为待删除

// 跳过处理，避免重复操作

if (DeleteList.count(Cur))

continue;

// 检查当前基本块 Cur 的终止指令是否是 SwitchInst

// 如果是，则进行处理

if (SwitchInst *SI = dyn_cast<SwitchInst>(Cur->getTerminator())) {

// 标记函数 F 被修改过

Changed = true;

// 处理 SwitchInst，可能会将 SwitchInst 转换为更简单的分支结构

// 同时，可能会将一些基本块标记为待删除，并加入 DeleteList

ProcessSwitchInst(SI, DeleteList, AC, LVI);

}

}

for (BasicBlock *BB : DeleteList) {

LVI->eraseBlock(BB);

DeleteDeadBlock(BB);

}

return Changed;

}

```

接下来着重分析ProcessSwitchInst

# 3.ProcessSwitchInst

将指定的 `switch` 指令替换为一系列通过平衡二叉搜索链接的 `if-then` 指令。

`ProcessSwitchInst` 函数有 **4 个参数**，具体如下

SwitchInst *SI：这是一个指向 SwitchInst 类型对象的指针，表示当前正在处理的 switch 指令。

SmallPtrSetImpl<BasicBlock *> &DeleteList：这是一个引用，指向一个存储 BasicBlock 指针的集合（SmallPtrSet），用于记录需要删除的基本块。

AssumptionCache *AC：这是一个指向 AssumptionCache 类型对象的指针，用于缓存和查询假设信息，帮助优化过程。

LazyValueInfo *LVI：这是一个指向 LazyValueInfo 类型对象的指针，用于延迟计算和查询值的信息，辅助优化决策。

## 3.1标记并删除不可达或自循环的基本块

内容和标题说的一样

```c

// 获取 switch 指令所在的基本块

BasicBlock *OrigBlock = SI->getParent();

//获取该基本块所属的函数

Function *F = OrigBlock->getParent();

//获取 switch 指令的条件值（即 switch 中用于比较的值）

Value *Val = SI->getCondition(); // The value we are switching on...

// 获取 switch 指令的默认目标基本块（即 default 分支）

BasicBlock* Default = SI->getDefaultDest();

// 不处理不可达的基本块。如果这些基本块的后继中有 PHI 节点，

// 直接删除会导致这些 PHI 节点缺少前驱。

if ((OrigBlock != &F->getEntryBlock() && pred_empty(OrigBlock)) ||

OrigBlock->getSinglePredecessor() == OrigBlock) {

DeleteList.insert(OrigBlock);

return;

}

```

OrigBlock != &F->getEntryBlock()

检查 OrigBlock 是否是函数的入口块（Entry Block）。入口块是函数的起始块，不能被删除。

pred_empty(OrigBlock)

检查 OrigBlock 是否有前驱块。如果没有前驱块，说明 OrigBlock 无法被访问到。

OrigBlock->getSinglePredecessor() == OrigBlock

检查 OrigBlock 的唯一前驱块是否是它自己。如果是，说明 OrigBlock 形成了一个自循环。

DeleteList.insert(OrigBlock)

如果 OrigBlock 满足上述任一条件，则将其插入到 DeleteList 中，后续会统一删除这些基本块。

## 3.2  Switch 分支聚类与默认分支排除(对switch进行一个case值的优化)

```c

// Prepare cases vector.

//// 准备 cases 向量，用于存储 switch 的所有分支信息

CaseVector Cases;

// 调用 Clusterify 函数，将 switch 的分支聚类并填充到 Cases 向量中，

// 同时返回简单分支的数量（即非默认分支的数量）

const unsigned NumSimpleCases = Clusterify(Cases, SI);

```

标题名，可能有些唬人，其实CaseVector Cases里面是存储是，switch指令里面case所对应的CaseRange信息

## 1.3实际应用场景

假设我们有以下 `Switch` 代码：

```c

switch (x) {

    case 1: ... break;

    case 2: ... break;

    case 100: ... break;

    default: ... break;

}

```

在 LowerSwitch 的转换过程中：

LazyValueInfo 会分析 x 的值范围，发现 x 的可能值为 1、2 或 100。

AssumptionCache 会检查是否有关于 x 的假设，例如“x 不可能为负数”。

基于这些信息，LowerSwitch 将 Switch 转换为一系列 Branch 指令，同时省略不必要的分支，例如负数的 case。

这里说明下这个CaseRange是什么东西？

举个例子：

这种情况下对应的CaseRange结构可能如下：

```

CaseRange(ConstantInt::get(/* value = */ 1), ConstantInt::get(/* value = */ 1), BB1);

CaseRange(ConstantInt::get(/* value = */ 2), ConstantInt::get(/* value = */ 4), BB2);

CaseRange(ConstantInt::get(/* value = */ 5), ConstantInt::get(/* value = */ 5), BB3);

```

### 3.2.1Clusterify 函数做了什么

将 `switch` 分支按连续值合并为簇，排除默认分支，并统计非默认分支数量。

```c

unsigned Clusterify(CaseVector &Cases, SwitchInst *SI) {

//初始化计数器，用于统计不引用默认分支的分支数量

unsigned NumSimpleCases = 0;

// 开始处理 "简单" 分支（即不引用默认分支的分支）

for (auto Case : SI->cases()) {

// 如果当前分支的目标基本块是默认分支，则跳过该分支

if (Case.getCaseSuccessor() == SI->getDefaultDest())

continue;

// 将当前分支转换为 CaseRange 并加入 Cases 列表

// CaseRange 的 Low 和 High 值初始化为当前分支的值（因为这是一个单一值的分支）

Cases.push_back(CaseRange(Case.getCaseValue(), Case.getCaseValue(),

Case.getCaseSuccessor()));

// 增加不引用默认分支的分支数量

++NumSimpleCases;

}

//对case进行排序

llvm::sort(Cases, CaseCmp());

// Merge case into clusters

// 如果 Cases 列表中有两个或更多分支，尝试将相邻的分支合并为簇

if (Cases.size() >= 2) {

// 定义迭代器 I，指向 Cases 列表的第一个分支

CaseItr I = Cases.begin();

// 定义迭代器 J，指向 Cases 列表的第二个分支，E 指向 Cases 列表的末尾

for (CaseItr J = std::next(I), E = Cases.end(); J != E; ++J) {

// 获取 J 分支的最小值（下界）

int64_t nextValue = J->Low->getSExtValue();

// 获取 I 分支的最大值（上界）

int64_t currentValue = I->High->getSExtValue();

// 获取 J 分支的目标基本块

BasicBlock* nextBB = J->BB;

BasicBlock* currentBB = I->BB;

// If the two neighboring cases go to the same destination, merge them

// into a single case.

// 如果相邻的两个分支满足以下条件：

// 1. J 分支的最小值等于 I 分支的最大值加 1（即连续的值）

// 2. 两个分支的目标基本块相同

// 则将这两个分支合并为一个簇

assert(nextValue > currentValue && "Cases should be strictly ascending");

if ((nextValue == currentValue + 1) && (currentBB == nextBB)) {

// 将 I 分支的上界更新为 J 分支的上界

I->High = J->High;

// FIXME: Combine branch weights.

// FIXME: 这里可以合并分支权重（未实现）

} else if (++I != J) {

// 如果分支不能合并，且 I 和 J 不指向同一个分支

// 则将 J 分支的值复制到 I 分支

*I = *J;

}

}

// 删除 Cases 列表中 I 之后的所有分支，因为它们已经被合并或复制

Cases.erase(std::next(I), Cases.end());

}

return NumSimpleCases;

}

```

接下来详细举例两个例子理解

根据Clusterify函数的处理逻辑

①遍历case 1-case4，并且增加到Cases vector中。

②根据case里面值进行排序。

③因为case的值有4个，那么开始遍历，因为case1的值为1，case2的值为2，但是他们的里面的block 分别为printf("%d",score)和printf("%d",score+1)，所以并不能合成一个簇，换句话说 如果

case1，和case2共同拥有printf，且前一个数值是后者的一个值+1，那么就会把这两个case合并成一个。

本质上clusterify完成了一个合并case节点的功能，这个是编译器优化的一个步骤。

3.3 所有分支都跳转到默认分支的处理

根据3.2获得的case，如果case为空，说明switch的指令都跳转的default了。

代码完成的目的：判断switch指令所在的块没有case值，那么直接创建一个无条件跳转指令，从switch块直接跳转到default，由于变更了块与块之前的前置关系，所以要修复下phi指令。

```c

if (Cases.empty()) {

//创建一个无条件跳转到默认分支的指令

BranchInst::Create(Default, OrigBlock);

// Remove all the references from Default's PHIs to OrigBlock, but one.

// 修复默认分支的PHI节点，移除所有对OrigBlock的引用，但是要保留一个

FixPhis(Default, OrigBlock, OrigBlock);

//删除原始的SwitchInst指令

SI->eraseFromParent();

//返回结束处理

return;

}

```

## 3.4判断默认分支可达还是不可达

### 3.4.1默认分支不可达的定义

这里有两种

1.默认分支block块内，除phi或者调试指令的后续指令是UnreachableInst，那么这个就默认不可达。

2.根据case值的范围，判断默认分支可不可达。

第1种很容易看懂，这里着重分析第二种

```

const DataLayout &DL = F->getParent()->getDataLayout();

KnownBits Known = computeKnownBits(Val, DL, /*Depth=*/0, AC, SI);

ConstantRange KnownBitsRange =

ConstantRange::fromKnownBits(Known, /*IsSigned=*/false);

const ConstantRange LVIRange = LVI->getConstantRange(Val, SI);

ConstantRange ValRange = KnownBitsRange.intersectWith(LVIRange);

APInt Low = Cases.front().Low->getValue();

APInt High = Cases.back().High->getValue();

//计算 ValRange 的最小值、最大值与 Low、High 的最小值和最大值

APInt Min = APIntOps::smin(ValRange.getSignedMin(), Low);

APInt Max = APIntOps::smax(ValRange.getSignedMax(), High);

```

通过结合 已知位信息（KnownBits）和 Lazy Value Info（LVI）的范围分析，推断出变量 `Val` 的可能取值范围（`ValRange`），然后与给定的 `Cases` 中的 `Low` 和 `High` 值进行比较，计算出一个更精确的最小值（`Min`）和最大值（`Max`），最终目的是优化 `Val` 的范围。

得到范围之后

```

DefaultIsUnreachableFromSwitch = (Min + (NumSimpleCases - 1) == Max);

```

来判断默认分支是否可达，

举个例子好理解这句话：

```

// switch (val) {

// case 1: ... break;

// case 2: ... break;

// case 3: ... break;

// }

```

假如在上面的代码中得到的min是1，max是3，numsimpleCase是3，那么 1+3-1equal3，就判断出来 默认分支不可达，否则就存在可达的可能性。

## 3.5处理默认分支不可达的情形

## 3.6处理默认分支可达的情形

下方代码，首先创建了一个NewDefault的快，将新创建的块放到default之前，并且将newDefault直接指向她

```

BasicBlock *NewDefault = BasicBlock::Create(SI->getContext(), "NewDefault");

F->getBasicBlockList().insert(Default->getIterator(), NewDefault);

BranchInst::Create(Default, NewDefault);

```

## 3.7 将switch2if-then

创建将switch语句转换为if-then的层次结构

```

// 调用 SwitchConvert 函数，将 switch 语句转换为 if-then 语句的层次结构

// 参数说明：

// - Cases.begin(), Cases.end(): 所有 case 范围的迭代器

// - LowerBound, UpperBound: switch 语句的值范围

// - Val: switch 语句的条件值

// - OrigBlock: 原始的 switch 语句所在的基本块

// - NewDefault: 新的默认块

// - UnreachableRanges: 不可达范围列表

BasicBlock *SwitchBlock =

SwitchConvert(Cases.begin(), Cases.end(), LowerBound, UpperBound, Val,

OrigBlock, OrigBlock, NewDefault, UnreachableRanges);

```

### 3.7.1switchConver函数解析

#### 37.1.1size为1时

首先计算需要处理case的size大小，如果为1的情况下，检查case 范围是否正好被 LowerBound 和UpperBound 完全包围，如果被包围，确定当前 `case` 范围包含多少个值,然后去修复phi指令

```c

if (Size == 1) {

// 检查当前 case 范围是否正好被 LowerBound 和 UpperBound 完全包围

if (Begin->Low == LowerBound && Begin->High == UpperBound) {

// 计算当前 case 范围的大小

unsigned NumMergedCases = 0;

NumMergedCases = UpperBound->getSExtValue() - LowerBound->getSExtValue();

// 修复 PHI 节点，确保控制流正确

FixPhis(Begin->BB, OrigBlock, Predecessor, NumMergedCases);

// 返回当前 case 范围的目标基本块

return Begin->BB;

}

return NewLeafBlock(*Begin, Val, LowerBound, UpperBound, OrigBlock,

Default);

}

```

首先看(Begin->Low == LowerBound && Begin->High == UpperBound)条件满足情况下，算出NumMergedCases（有几个节点被合并了） 的值，然后FixPhis(Begin->BB, OrigBlock, Predecessor, NumMergedCases)

首先为什么会产生修复phis，

重点看

```

NumMergedCases = UpperBound->getSExtValue() - LowerBound->getSExtValue();

// 修复 PHI 节点，确保控制流正确

FixPhis(Begin->BB, OrigBlock, Predecessor, NumMergedCases);

```

这里我画出来图（着重讲fixPhis，这个其他的函数也会使用fixPhis）：

```

1.功能：将在succBB第一次出现phi节点且输入值是origBB的节点的phi指令中的Incoming替换为newBB

1.1如果Switch语句都具有相同的值，则它们可能有多个输出边进入同一BB。转换switch语句时，这些传入边现在来自多个BB。

1.2如果后续传入值现在共享相同的情况，即多个结果边被压缩为一个，则删除,这对于保持phi值的数量等于SuccBB的分支数量是必要的。

```

大概操作如图所示：把在succBB中的phi指令，如果这个phi是orginB作为输入的，替换为newBB，同时后续除第一条来自orginBB的条指令都removeIncomingValue掉。

#### 3.7.1.2当size大于2时

按照查找二叉树的方式构建switch的case作为一个查找二叉树的方式进行构建。

```

if (Leaf.Low == Leaf.High)

{

// Make the seteq instruction...

Comp =

new ICmpInst(*NewLeaf, ICmpInst::ICMP_EQ, Val, Leaf.Low, "SwitchLeaf");

}

else

{

// Make range comparison

if (Leaf.Low == LowerBound)

{

// Val >= Min && Val <= Hi --> Val <= Hi

Comp = new ICmpInst(*NewLeaf, ICmpInst::ICMP_SLE, Val, Leaf.High,

"SwitchLeaf");

}

else if (Leaf.High == UpperBound)

{

// Val <= Max && Val >= Lo --> Val >= Lo

Comp = new ICmpInst(*NewLeaf, ICmpInst::ICMP_SGE, Val, Leaf.Low,

"SwitchLeaf");

}

else if (Leaf.Low->isZero())

{

// Val >= 0 && Val <= Hi --> Val <=u Hi

Comp = new ICmpInst(*NewLeaf, ICmpInst::ICMP_ULE, Val, Leaf.High,

"SwitchLeaf");

}

else

{

// Emit V-Lo <=u Hi-Lo

Constant *NegLo = ConstantExpr::getNeg(Leaf.Low);

Instruction *Add = BinaryOperator::CreateAdd(

Val, NegLo, Val->getName() + ".off", NewLeaf);

Constant *UpperBound = ConstantExpr::getAdd(NegLo, Leaf.High);

Comp = new ICmpInst(*NewLeaf, ICmpInst::ICMP_ULE, Add, UpperBound,

"SwitchLeaf");

}

}

```

通过一些跳转替换了switch语句，从而达到了目的。

例如代码如图所示，则处理为

详见如图所示。

这篇文章总结：swtich转化为其他的branch指令进行实现。

代码太多了，光看这篇文章展现不出来奥妙，后面录一个视频。

下面两幅图为switch转化为branch的对比图

学习逆向与爬虫，可以关注我朋友：

原文始发于微信公众号（二进制科学）：llvm进阶（2）LowerSwitch（Switch 到 Branch 的奥秘）