LLVM 之 IR 篇（6）：如何编写消除死代码 Pass
Author: stormQ
Created: Sunday, 22. August 2021 10:09AM
Last Modified: Tuesday, 24. August 2021 10:23PM
本文基于release/12.x版本的 LLVM 源码，介绍了如何编写用于消除死代码的 Pass——myadce。该 Pass 仅消除那些被判定为死代码的指令。这意味着该 Pass 不会更改控制流图，比如：增或删基本块、更改基本块之间的控制流向。通过实现这样一个简单的 Pass，从而初步了解 LLVM IR 的优化——消除死代码，以便更深入地研究相关内容，比如：ADCE、BDCE、DCE、DSE 等。
本节介绍了编写用于消除死代码的自定义 ADCE（Aggressive Dead Code Elimination）Pass 的前期准备工作（不涉及具体功能的实现）。
注： 本节涉及的代码是基于传统 Pass 框架在源码中进行扩展的，这里不再赘述源码解析。如有疑问，可参考笔者的另一篇文章：《LLVM 之 IR 篇（4）：如何基于传统 Pass 框架扩展 LLVM IR 优化器》。
step 1： 实现自定义的 Pass
1） 添加实现代码
在llvm/lib/Transforms/Scalar目录中新建MyADCE.cpp文件，内容如下：
1 #include "llvm/InitializePasses.h"
2 #include "llvm/Transforms/Scalar.h"
3 #include "llvm/IR/Function.h"
4 #include "llvm/Pass.h"
5 #include "llvm/Support/raw_ostream.h"
6
7 using namespace llvm;
8
9 #define DEBUG_TYPE "myadce"
10
11 namespace {
12
13 class MyADCELegacyPass : public FunctionPass {
14 public:
15 static char ID;
16
17 MyADCELegacyPass() : FunctionPass(ID) {
18 initializeMyADCELegacyPassPass(*PassRegistry::getPassRegistry());
19 }
20
21 bool runOnFunction(Function &F) override {
22 return false;
23 }
24 };
25
26 } // anonymous namespace
27
28 char MyADCELegacyPass::ID = 0;
29
30 INITIALIZE_PASS(MyADCELegacyPass, DEBUG_TYPE,
31 "My Aggressive Dead Code Elimination Legacy Pass", false, false)
32
33 FunctionPass *llvm::createMyADCELegacyPass() {
34 return new MyADCELegacyPass();
35 }
step 2： 修改 InitializePasses.h
在llvm/include/llvm/InitializePasses.h文件中添加如下内容：
void initializeMyADCELegacyPassPass(PassRegistry&);
修改后的内容为：
namespace llvm {
省略 ...
void initializeMyADCELegacyPassPass(PassRegistry&);
} // end namespace llvm
step 3： 修改 LinkAllPasses.h
在llvm/include/llvm/LinkAllPasses.h文件中添加如下内容：
(void) llvm::createMyADCELegacyPass();
修改后的内容为：
namespace {
struct ForcePassLinking {
ForcePassLinking() {
省略 ...
(void) llvm::createMyADCELegacyPass();
省略 ...
}
} ForcePassLinking; // Force link by creating a global definition.
}
step 4： 修改 Scalar.h
1） 在llvm/include/llvm/Transforms/Scalar.h文件中添加如下内容
FunctionPass *createMyADCELegacyPass();
修改后的内容为：
namespace llvm {
省略 ...
FunctionPass *createMyADCELegacyPass();
} // End llvm namespace
2） 在llvm/include/llvm-c/Transforms/Scalar.h文件中添加如下内容（optional）
/** See llvm::createMyADCELegacyPass function. */
void LLVMAddMYAggressiveDCELegacyPass(LLVMPassManagerRef PM);
step 5： 修改 Scalar.cpp
1） 在llvm/lib/Transforms/Scalar/Scalar.cpp文件中添加如下内容
initializeMyADCELegacyPassPass(Registry);
修改后的内容为：
void llvm::initializeScalarOpts(PassRegistry &Registry) {
省略 ...
initializeMyADCELegacyPassPass(Registry);
}
2） 在llvm/lib/Transforms/Scalar/Scalar.cpp文件中添加如下内容（optional）
void LLVMAddMYAggressiveDCELegacyPass(LLVMPassManagerRef PM) {
unwrap(PM)->add(createMyADCELegacyPass());
}
step 6： 修改 Scalar 目录中的 CMakeLists.txt
在llvm/lib/Transforms/Scalar/CMakeLists.txt文件中添加如下内容：
MyADCE.cpp
step 7： 编译安装
$ ninja -j8
$ sudo ninja install
安装完成后，查看默认的opt工具是否包含选项myadce：
$ opt --help | grep myadce
--myadce - My Aggressive Dead Code Elimination Legacy Pass - Function Argument Count Legacy Pass
本节介绍了自定义 ADCE Pass——myadce的实现过程，包括：如何判定指令是否 Live、如何消除 Dead 指令等。
step 1： 过滤 Pass 不处理的函数（optional）
我们可以决定 Pass 不会对哪些函数生效。比如：不处理带optnone属性的函数。
25 bool runOnFunction(Function &F) override {
26 if (skipFunction(F)) {
27 return false;
28 }
29 // 省略 ...
30 }
如果要分析的函数Function &F带optnone属性，那么函数llvm::FunctionPass::skipFunction()会返回true。也就是说，上述代码中的第 26~28 行表示该 Pass 会跳过带optnone属性的函数。
如果不添加上述代码，自定义 ADCE Pass 将允许对所有的函数进行优化。
step 2： 实现消除 Dead 指令的功能
我们在类MyADCELegacyPass中定义一个私有成员函数removeDeadInstructions，用于消除 Dead 指令。其函数声明如下：
bool removeDeadInstructions(Function &F);
1） 收集 Live 指令
42 bool MyADCELegacyPass::removeDeadInstructions(Function &F) {
43 SmallPtrSet<Instruction *, 32> Alive;
44 SmallVector<Instruction *, 128> Worklist;
45
46 for (Instruction &I : instructions(F)) {
47 if (I.isDebugOrPseudoInst() || !I.isSafeToRemove()) {
48 Alive.insert(&I);
49 Worklist.push_back(&I);
50 }
51 }
52
53 while (!Worklist.empty()) {
54 Instruction *LiveInst = Worklist.pop_back_val();
55 for (Use &OI : LiveInst->operands()) {
56 if (Instruction *Inst = dyn_cast<Instruction>(OI)) {
57 if (Alive.insert(Inst).second) {
58 Worklist.push_back(Inst);
59 }
60 }
61 }
62 }
63
64 // 省略 ...
76 }
其中，函数llvm::Instruction::isDebugOrPseudoInst()和llvm::Instruction::isSafeToRemove()的实现如下（定义在 llvm/lib/IR/Instruction.cpp 文件中）：
bool Instruction::isSafeToRemove() const {
return (!isa<CallInst>(this) || !this->mayHaveSideEffects()) &&
!this->isTerminator();
}
bool Instruction::isDebugOrPseudoInst() const {
return isa<DbgInfoIntrinsic>(this) || isa<PseudoProbeInst>(this);
}
函数llvm::Instruction::mayHaveSideEffects()的实现如下（定义在 llvm/include/llvm/IR/Instructions.h 文件中）：
bool mayHaveSideEffects() const { return mayWriteToMemory() || mayThrow(); }
上述代码的逻辑为：
第 43 行，定义一个数据类型为SmallPtrSet<Instruction *, 32>的局部变量Alive，其元素的数据类型为Instruction *，集合的初始大小为 32。该局部变量用于存储被判定为 Live 的 LLVM IR 指令。
第 44 行，定义一个数据类型为SmallVector<Instruction *, 128>的局部变量Worklist，其元素的数据类型为Instruction *，向量的初始大小为 128。该局部变量作为工作集，用于存储需要对哪些 LLVM IR 指令进行是否为 Live 的判定。当工作集为空时，表示已经完成了判定工作。
第 46~51 行，遍历函数F中的每条 LLVM IR 指令，初步收集 Live 指令并添加到工作集中。Live 指令需要满足如下条件之一：
该指令是调试相关的指令（用类llvm::DbgInfoIntrinsic表示）
该指令是伪代码指令（用类llvm::PseudoProbeInst表示）
该指令作为基本块的出口（即函数llvm::Instruction::isTerminator()的返回值为true），比如：br、ret等指令
该指令是函数调用（用类llvm::CallInst表示），并且该指令可能有副作用（即可能写入内存或者抛出异常）
第 53~62 行，从工作集中的最后一条指令开始，采用深度优先遍历算法收集与工作集中的 Live 指令相关的指令（即指令之间存在Use边），并将其也视作 Live 指令。重复这一过程直到工作集为空。
第 57 行，语句Alive.insert(Inst).second的行为：如果集合Alive中已存在指令Inst，那么不进行插入操作，并且将second字段的值设置为false；否则，将指令Inst插入到集合Alive中，并且将second字段的值设置为true。也就是说，该语句用于避免工作集中出现相同的 Live 指令。
接下来，分析如下示例中 Live 指令的收集过程，以便更直观地理解上述代码。
15 for.cond: ; preds = %for.inc, %entry
16 %0 = load i32, i32* %i, align 4
17 %cmp = icmp slt i32 %0, 10
18 br i1 %cmp, label %for.body, label %for.end
由于第 18 行的指令作为基本块的出口。因此，上述代码在执行第 46~51 行时，该指令将作为 Live 指令添加到工作集中。此时，工作集中只包含第 18 行的指令。
由于第 18 行的指令中使用了寄存器%cmp。因此，上述代码在执行第 53~62 行时，定义寄存器%cmp的指令（即第 17 行指令，与第 18 行指令之间存在Use边）将作为 Live 指令添加到工作集中。此时，工作集中只包含第 17 行的指令。
由于第 17 行的指令中使用了寄存器%0。因此，上述代码在执行第 53~62 行时，定义寄存器%0的指令（即第 16 行指令，与第 17 行指令之间存在Use边）将作为 Live 指令添加到工作集中。此时，工作集中只包含第 16 行的指令。
2） 消除 Dead 指令
42 bool MyADCELegacyPass::removeDeadInstructions(Function &F) {
43 // 省略 ...
63
64 for (Instruction &I : instructions(F)) {
65 if (!Alive.count(&I)) {
66 Worklist.push_back(&I);
67 I.dropAllReferences();
68 }
69 }
70
71 for (Instruction *&I : Worklist) {
72 I->eraseFromParent();
73 }
74
75 return !Worklist.empty();
76 }
上述代码的逻辑为：
第 64~69 行，遍历函数F中的每条 LLVM IR 指令，将 Dead 指令添加到工作集中，并删除与 Dead 指令相关的Use边。
第 65 行，语句Alive.count(&I)的行为：如果集合Alive中存在指令I，那么返回值为true。
第 71~73 行，删除工作集中所有的 Dead 指令。这些被删除的 Dead 指令不会再出现在基本块中。
第 75 行，返回值为true表示修改了函数F。
step 3： 显式说明未更改控制流图（optional）
32 void getAnalysisUsage(AnalysisUsage& AU) const override {
33 AU.setPreservesCFG();
34 }
函数setPreservesCFG用于说明该 Pass 未更改控制流图。
注： 去掉上述代码后，后面的测试程序也可以正常运行并得到相同的输出结果。
step 4： 完整的程序
MyADCE.cpp 的完整内容如下：
1 #include "llvm/InitializePasses.h"
2 #include "llvm/Transforms/Scalar.h"
3 #include "llvm/IR/Function.h"
4 #include "llvm/Pass.h"
5 #include "llvm/Support/raw_ostream.h"
6 #include "llvm/ADT/SmallVector.h"
7 #include "llvm/ADT/SmallPtrSet.h"
8 #include "llvm/IR/Instructions.h"
9 #include "llvm/IR/InstIterator.h"
10
11 using namespace llvm;
12
13 #define DEBUG_TYPE "myadce"
14
15 namespace {
16
17 class MyADCELegacyPass : public FunctionPass {
18 public:
19 static char ID;
20
21 MyADCELegacyPass() : FunctionPass(ID) {
22 initializeMyADCELegacyPassPass(*PassRegistry::getPassRegistry());
23 }
24
25 bool runOnFunction(Function &F) override {
26 if (skipFunction(F)) {
27 return false;
28 }
29 return removeDeadInstructions(F);
30 }
31
32 void getAnalysisUsage(AnalysisUsage& AU) const override {
33 AU.setPreservesCFG();
34 }
35
36 private:
37 bool removeDeadInstructions(Function &F);
38 };
39
40 } // anonymous namespace
41
42 bool MyADCELegacyPass::removeDeadInstructions(Function &F) {
43 SmallPtrSet<Instruction *, 32> Alive;
44 SmallVector<Instruction *, 128> Worklist;
45
46 for (Instruction &I : instructions(F)) {
47 if (I.isDebugOrPseudoInst() || !I.isSafeToRemove()) {
48 Alive.insert(&I);
49 Worklist.push_back(&I);
50 }
51 }
52
53 while (!Worklist.empty()) {
54 Instruction *LiveInst = Worklist.pop_back_val();
55 for (Use &OI : LiveInst->operands()) {
56 if (Instruction *Inst = dyn_cast<Instruction>(OI)) {
57 if (Alive.insert(Inst).second) {
58 Worklist.push_back(Inst);
59 }
60 }
61 }
62 }
63
64 for (Instruction &I : instructions(F)) {
65 if (!Alive.count(&I)) {
66 Worklist.push_back(&I);
67 I.dropAllReferences();
68 }
69 }
70
71 for (Instruction *&I : Worklist) {
72 I->eraseFromParent();
73 }
74
75 return !Worklist.empty();
76 }
77
78 char MyADCELegacyPass::ID = 0;
79
80 INITIALIZE_PASS(MyADCELegacyPass, DEBUG_TYPE,
81 "My Aggressive Dead Code Elimination Legacy Pass", false, false)
82
83 FunctionPass *llvm::createMyADCELegacyPass() {
84 return new MyADCELegacyPass();
85 }
在完成编译安装后，分别运行以下测试程序观察自定义 ADCE Pass——myadce的优化效果。
step 1： 运行测试程序 1
1） 测试程序 1
testcode.ll 的内容如下：
declare i32 @strlen(i8*) readonly nounwind
define void @test() {
call i32 @strlen( i8* null )
ret void
}
上述代码中调用了strlen()函数，但并未使用其返回值。因此，指令call i32 @strlen( i8* null )应该被视为死代码。
2） 运行
$ opt -S -myadce testcode.ll
输出结果如下：
; ModuleID = 'testcode.ll'
source_filename = "testcode.ll"
; Function Attrs: nounwind readonly
declare i32 @strlen(i8*) #0
define void @test() {
ret void
}
attributes #0 = { nounwind readonly }
从上面的结果可以看出，自定义 ADCE Pass——myadce按照预期消除了死代码——call i32 @strlen( i8* null )。
step 2： 运行测试程序 2
1） 测试程序 2
test2.c 的内容如下：
void foo(int *out) {
int x = *out;
for (int i = 0; i < 10; i++) {
if (x % 2 == 0) {
x += i;
}
else {
x -= i;
}
}
*out = x;
}
上述代码中，循环for可能会影响程序的执行结果。因此，函数foo中的所有语句都不应该被视为死代码。
2） 生成 LLVM IR 汇编文件
$ clang -S -emit-llvm test2.c -o test2.ll
生成 LLVM IR 汇编文件 test2.ll 后，手动删除函数foo的optnone属性，并保存为 test2_without_optnone.ll 文件。
test2_without_optnone.ll 的内容如下（部分）：
省略 ...
define dso_local void @foo(i32* %out) #0 {
entry:
%out.addr = alloca i32*, align 8
%x = alloca i32, align 4
%i = alloca i32, align 4
store i32* %out, i32** %out.addr, align 8
%0 = load i32*, i32** %out.addr, align 8
%1 = load i32, i32* %0, align 4
store i32 %1, i32* %x, align 4
store i32 0, i32* %i, align 4
br label %for.cond
for.cond: ; preds = %for.inc, %entry
%2 = load i32, i32* %i, align 4
%cmp = icmp slt i32 %2, 10
br i1 %cmp, label %for.body, label %for.end
for.body: ; preds = %for.cond
%3 = load i32, i32* %x, align 4
%rem = srem i32 %3, 2
%cmp1 = icmp eq i32 %rem, 0
br i1 %cmp1, label %if.then, label %if.else
if.then: ; preds = %for.body
%4 = load i32, i32* %i, align 4
%5 = load i32, i32* %x, align 4
%add = add nsw i32 %5, %4
store i32 %add, i32* %x, align 4
br label %if.end
if.else: ; preds = %for.body
%6 = load i32, i32* %i, align 4
%7 = load i32, i32* %x, align 4
%sub = sub nsw i32 %7, %6
store i32 %sub, i32* %x, align 4
br label %if.end
if.end: ; preds = %if.else, %if.then
br label %for.inc
for.inc: ; preds = %if.end
%8 = load i32, i32* %i, align 4
%inc = add nsw i32 %8, 1
store i32 %inc, i32* %i, align 4
br label %for.cond, !llvm.loop !2
for.end: ; preds = %for.cond
%9 = load i32, i32* %x, align 4
%10 = load i32*, i32** %out.addr, align 8
store i32 %9, i32* %10, align 4
ret void
}
省略 ...
3） 运行
$ opt -S -myadce test2_without_optnone.ll
输出结果如下（部分）：
省略 ...
define dso_local void @foo(i32* %out) #0 {
entry:
%x = alloca i32, align 4
%i = alloca i32, align 4
br label %for.cond
for.cond: ; preds = %for.inc, %entry
%0 = load i32, i32* %i, align 4
%cmp = icmp slt i32 %0, 10
br i1 %cmp, label %for.body, label %for.end
for.body: ; preds = %for.cond
%1 = load i32, i32* %x, align 4
%rem = srem i32 %1, 2
%cmp1 = icmp eq i32 %rem, 0
br i1 %cmp1, label %if.then, label %if.else
if.then: ; preds = %for.body
br label %if.end
if.else: ; preds = %for.body
br label %if.end
if.end: ; preds = %if.else, %if.then
br label %for.inc
for.inc: ; preds = %if.end
br label %for.cond, !llvm.loop !2
for.end: ; preds = %for.cond
ret void
}
省略 ...
从上面的结果可以看出，自定义 ADCE Pass——myadce删除了*out = x;等语句对应的 LLVM IR 指令。然而，这些指令不应该被删除。也就是说，对于测试程序 test2_without_optnone.ll 而言，自定义 ADCE Pass——myadce的优化结果是错误的。
正如其名，本文所实现的myadce是一种激进的用于消除死代码的 Pass。这意味着如果一条指令不能证明自己是 Live，那么将会被判定为 Dead。该 Pass 仅消除那些被判定为死代码的指令，但不会更改控制流图。
myadce判定一个指令是 Live，需要满足以下条件之一：
该指令是调试相关的指令
该指令是伪代码指令
该指令作为基本块的出口，比如：br、ret等指令
该指令是函数调用，并且该指令可能有副作用（即可能写入内存或者抛出异常）
以及与上述四种指令之间存在Use边的指令
然而，通过测试程序可以发现，即便满足了上述条件，优化结果也可能是错误的。
下一篇：LLVM 之 IR 篇（7）：如何编写内联 Pass