系列文章目录

LLVM系列第一章：编译LLVM源码
LLVM系列第二章：模块Module
LLVM系列第三章：函数Function
LLVM系列第四章：逻辑代码块Block
LLVM系列第五章：全局变量Global Variable
LLVM系列第六章：函数返回值Return
LLVM系列第七章：函数参数Function Arguments
LLVM系列第八章：算术运算语句Arithmetic Statement
LLVM系列第九章：控制流语句if-else
LLVM系列第十章：控制流语句if-else-phi
LLVM系列第十一章：写一个Hello World
LLVM系列第十二章：写一个简单的词法分析器Lexer
LLVM系列第十三章：写一个简单的语法分析器Parser
LLVM系列第十四章：写一个简单的语义分析器Semantic Analyzer
LLVM系列第十五章：写一个简单的中间代码生成器IR Generator
LLVM系列第十六章：写一个简单的编译器
LLVM系列第十七章：for循环
LLVM系列第十八章：写一个简单的IR处理流程Pass
LLVM系列第十九章：写一个简单的Module Pass
LLVM系列第二十章：写一个简单的Function Pass
LLVM系列第二十一章：写一个简单的Loop Pass
LLVM系列第二十二章：写一个简单的编译时函数调用统计器(Pass)
LLVM系列第二十三章：写一个简单的运行时函数调用统计器(Pass)
LLVM系列第二十四章：用Xcode编译调试LLVM源码
LLVM系列第二十五章：简单统计一下LLVM源码行数
LLVM系列第二十六章：理解LLVMContext
LLVM系列第二十七章：理解IRBuilder
LLVM系列第二十八章：写一个JIT Hello World
LLVM系列第二十九章：写一个简单的常量加法“消除”工具(Pass)

---

---

前言

在此，记录下基于LLVM写一个简单的常量加法“消除”工具(Pass)的过程，以备查阅。

开发环境的配置请参考第一章 《LLVM系列第一章：编译LLVM源码》。

今天，我们来玩一个简单的“消除游戏”。“游戏”中，我们要“消除”的对象是数值常量的加法指令，也就是两个已知整数或小数的加法。既然两个数都是已知了，那它们相加的结果也是已知的。

如果要“消除”掉加法指令中的两个数值常量，那么首先得找到它们。我们可以写一个简单的Analysis，专门用来寻找数值常量的加法指令。其逻辑也很简单，首先，要判断该指令的操作符是否为加法；第二，要判断该指令的操作数是否均为常量。

我们可以再写一个Pass。它利用Analysis找到所有的常量加法指令，把每个指令的最终结果计算出来，再把所有用到该指令的地方改为直接使用其结果即可。

本章我们就来写一个简单的Analysis和一个Pass，用来“消除”掉常量的加法指令。

一、项目结构

我们把这个简单的项目命名为RunTimeFunctionCallCounter。可以参考LLVM源码中的其它Pass的组织结构，来组织我们自己的代码（示例）：

llvm-project/llvm
├── ...
├── lib
│   └── Transforms
│       ├── CMakeLists.txt
│       └── ConstantAdditionCombiner
│           ├── CMakeLists.txt
│           └── ConstantAdditionCombiner.cpp
└── ...
1
2
3
4
5
6
7
8
9

二、项目细节

1. 程序模块

这个简单的项目只包含了一个模块：

1. ConstantAdditionCombiner，一个简单的模块，包含了ConstantAdditionAnalysis和ConstantAdditionPass等Analysis和Pass，用来寻找和“消除”掉常量的加法指令。

如上所述，ConstantAdditionAnalysis接收一个函数作为输入数据，遍历函数中的代码块，再遍历代码块中的每条指令，判断该指令是否为数值常量的加法指令，并收集所有的符合要求的指令。

而ConstantAdditionPass则利用ConstantAdditionAnalysis收集所有的数值常量加法指令，把每个指令的最终结果计算出来，再把所有用到该指令的地方替换为直接使用其结果。

注意，我们需要把ConstantAdditionCombiner项目加入到LLVM Transforms父项目中，即指示CMake在编译LLVM源码的同时，也要编译ConstantAdditionCombiner项目。

以下是跟项目组织结构相关的部分CMake脚本。

(1) lib/Transforms/ConstantAdditionCombiner/CMakeLists.txt文件（示例）：

# CMakeLists.txt

add_llvm_library(ConstantAdditionCombiner MODULE BUILDTREE_ONLY
    ConstantAdditionCombiner.cpp

    PLUGIN_TOOL
    opt
)
1
2
3
4
5
6
7
8

(2) lib/Transforms/CMakeLists.txt文件（示例）：

...
add_subdirectory(ConstantAdditionCombiner)
...
1
2
3

2. Constant Addition Analysis and Combiner

Constant Addition Analysis and Combiner的实现在文件lib/Transforms/ConstantAdditionCombiner/ConstantAdditionCombiner.cpp中（示例）：

// ConstantAdditionCombiner.cpp

#include "llvm/IR/PassManager.h"
#include "llvm/Passes/PassBuilder.h"
#include "llvm/Passes/PassPlugin.h"
#include "llvm/Support/raw_ostream.h"

using namespace llvm;

namespace
{
    /**
     * An analysis to collect all the "add" instructions with constant operands from a function
     */
    struct ConstantAdditionAnalysis : public llvm::AnalysisInfoMixin<ConstantAdditionAnalysis>
    {
        using Result = llvm::SmallVector<llvm::BinaryOperator*, 0>;

        Result run(llvm::Function& function, llvm::FunctionAnalysisManager& analysisManager);

        // A special type used by analysis passes to provide an address that
        // identifies that particular analysis pass type
        static llvm::AnalysisKey Key;
    };

    AnalysisKey ConstantAdditionAnalysis::Key;

    bool IsConstantIntOnly(Instruction& instruction)
    {
        for (Use& operand : instruction.operands())
        {
            if (!isa<ConstantInt>(operand))
                return false;
        }

        return true;
    }

    ConstantAdditionAnalysis::Result ConstantAdditionAnalysis::run(Function& function,
                                                                   FunctionAnalysisManager& analysisManager)
    {
        SmallVector<BinaryOperator*, 0> addInstructions;
        for (BasicBlock& block : function)
        {
            for (Instruction& instruction : block)
            {
                if (!instruction.isBinaryOp())
                    continue;

                if (instruction.getOpcode() != Instruction::BinaryOps::Add)
                    continue;

                if (!IsConstantIntOnly(instruction))
                    continue;

                addInstructions.push_back(&cast<BinaryOperator>(instruction));
            }
        }

        return addInstructions;
    }

    /**
     * An pass to print all the "add" instructions with constant operands from a function
     */
    struct ConstantAdditionPrinterPass : public llvm::PassInfoMixin<ConstantAdditionPrinterPass>
    {
        explicit ConstantAdditionPrinterPass(llvm::raw_ostream& outStream) :
            out(outStream)
        {
        }

        llvm::PreservedAnalyses run(llvm::Function& function, llvm::FunctionAnalysisManager& analysisManager)
        {
            auto& addInstructions = analysisManager.getResult<ConstantAdditionAnalysis>(function);

            out << "Function: " << function.getName() << "\n";
            for (auto& instruction : addInstructions)
            {
                out << *instruction << "\n";
            }

            return PreservedAnalyses::all();
        }

    private:

        llvm::raw_ostream& out;
    };

    struct ConstantAdditionCombinerPass : public llvm::PassInfoMixin<ConstantAdditionCombinerPass>
    {
        llvm::PreservedAnalyses run(llvm::Function& function, llvm::FunctionAnalysisManager& analysisManager);
    };

    void ReplaceAddInstructionWithConstant(BinaryOperator* binaryOperator)
    {
        auto first = cast<ConstantInt>(binaryOperator->getOperand(0));
        auto second = cast<ConstantInt>(binaryOperator->getOperand(1));

        // Get the final value from the "add" instruction
        auto sum = ConstantExpr::getAdd(first, second);

        binaryOperator->replaceAllUsesWith(sum);
        binaryOperator->eraseFromParent();
    }

    PreservedAnalyses ConstantAdditionCombinerPass::run(Function& function, FunctionAnalysisManager& analysisManager)
    {
        auto& addInstructions = analysisManager.getResult<ConstantAdditionAnalysis>(function);
        for (auto binaryOperator : addInstructions)
        {
            ReplaceAddInstructionWithConstant(binaryOperator);
        }

        auto preservedAnalyses = PreservedAnalyses::all();
        preservedAnalyses.abandon<ConstantAdditionAnalysis>();
        return preservedAnalyses;
    }
} // namespace

// Register the passes
extern "C" PassPluginLibraryInfo LLVM_ATTRIBUTE_WEAK llvmGetPassPluginInfo()
{
    return {LLVM_PLUGIN_API_VERSION, "ConstantAdditionCombiner", "v0.1", [](PassBuilder& passBuilder) {
                passBuilder.registerAnalysisRegistrationCallback([](FunctionAnalysisManager& analysisManager) {
                    analysisManager.registerPass([] {
                        return ConstantAdditionAnalysis();
                    });
                });

                passBuilder.registerPipelineParsingCallback(
                    [](StringRef name, FunctionPassManager& passManager, ArrayRef<PassBuilder::PipelineElement>) {
                        if (name == "constant-addition-printer")
                        {
                            passManager.addPass(ConstantAdditionPrinterPass(outs()));
                            return true;
                        }

                        if (name == "constant-addition-combiner")
                        {
                            passManager.addPass(ConstantAdditionCombinerPass());
                            return true;
                        }

                        return false;
                    });
            }};
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149

三、编译

1. 生成项目文件

用CMake工具生成项目文件（示例）：

cd /path/to/llvm-project/llvm
mkdir build
cd build

# Format the source code
clang-format -i ../lib/Transforms/ConstantAdditionCombiner/*.cpp

# Set up C++ standard library and header path
export SDKROOT=$(xcrun --sdk macosx --show-sdk-path)

cmake -G Ninja -DCMAKE_BUILD_TYPE=Debug ..
1
2
3
4
5
6
7
8
9
10
11

输出log如下（示例）：

-- clang project is enabled
-- clang-tools-extra project is disabled
-- ...
-- Ninja version: 1.10.2
-- Found ld64 - /Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin/ld
-- ...
-- LLVM host triple: x86_64-apple-darwin20.6.0
-- LLVM default target triple: x86_64-apple-darwin20.6.0
-- ...
-- Configuring done
-- Generating done
-- Build files have been written to: .../llvm-project/llvm/build
1
2
3
4
5
6
7
8
9
10
11
12

2. 编译

用ninja进行编译（示例）：

ninja
1

如果我们是在参考第一章的步骤，编译了LLVM源码之后，再编译此项目，则只需编译ConstantAdditionCombiner项目即可。当然，这是ninja自动就能识别出来的，即所谓的增量编译技术。输出log如下（示例）：

[4/4] Linking CXX shared module lib/ConstantAdditionCombiner.dylib
1

3. 运行

为了简单起见，我们就用以下Test.ll文件中IR代码来测试一下（示例）：

; ModuleID = 'Test.ll'
source_filename = "Test.ll"

define i32 @Test(i32 %a, i32 %b) {
  %c = add i32 1, 2
  %d = add i32 5, 6
  %e = add i32 %a, %c
  %f = add i32 %b, %d
  %g = add i32 %e, %f
  ret i32 %g
}
1
2
3
4
5
6
7
8
9
10
11

运行constant-addition-printer (Analysis)（示例）：

./bin/opt -load-pass-plugin=lib/ConstantAdditionCombiner.dylib -passes="constant-addition-printer" -disable-output ../lib/Transforms/ConstantAdditionCombiner/Test.ll
1

输出log如下（示例）：

Function: Test
  %c = add i32 1, 2
  %d = add i32 5, 6
1
2
3

可以看到它能正确的识别出常量加法指令。

再运行constant-addition-combiner (Pass)（示例）：

./bin/opt -load-pass-plugin=lib/ConstantAdditionCombiner.dylib -passes="constant-addition-combiner" -S ../lib/Transforms/ConstantAdditionCombiner/Test.ll
1

输出log如下（示例）：

; ModuleID = '../lib/Transforms/ConstantAdditionCombiner/Test.ll'
source_filename = "Test.ll"

define i32 @Test(i32 %a, i32 %b) {
  %e = add i32 %a, 3
  %f = add i32 %b, 11
  %g = add i32 %e, %f
  ret i32 %g
}
1
2
3
4
5
6
7
8
9

注意到跟原来的IR代码相比，以下两条指令被合并了：

  %c = add i32 1, 2
  ...
  %e = add i32 %a, %c
1
2
3

它们被合并成了一条指令：

  %e = add i32 %a, 3
1

四、总结

我们用LLVM提供的C++ API，写了简单的Analysis和Pass，用来寻找并“消除”掉常量加法指令。完整源码示例请参看：
https://github.com/wuzhanglin/llvm-pass-examples