春暖花开

LLVM Pass 与 APA 简介

前段时间学习了一些关于 LLVM Pass 和 APA 方面的知识,趁今天有空,做一些总结。

LLVM Pass

Pass 是 LLVM 中一个非常重要的框架,在 LLVM 后端的分析、转化、优化等过程中,通常是多个 Pass 一起作用来共同完成的。

每一个 LLVM Pass 都是 Pass 类的一个派生类,通过重写 Pass 类的虚方法来实现自身的功能。根据你想要实现的功能,你可以选择继承ModulePassFunctionPass 等等一系列Pass.

下面实现一个简单的Pass: 该 Pass 的功能就是在 main 函数的入口处添加一个打印 hello, world.\n 的语句。在这儿,我们选择继承 ModulePass 来实现:

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
#include <cstdio>
#include "llvm/ADT/Statistic.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/Module.h"
#include "llvm/IR/IRBuilder.h"
#include "llvm/IR/TypeBuilder.h"
#include "llvm/Pass.h"
#include "llvm/Support/raw_ostream.h"
using namespace llvm;
namespace {
struct PrintfAfterMain : public ModulePass {
static char ID; // Pass identification, replacement for typeid
PrintfAfterMain() : ModulePass(ID) {}
virtual bool runOnModule(Module &M) {
Function *F = M.getFunction("main");
if (!F){
errs() << "Not exist main function.\n";
return false;
}
Instruction *inst = &(*F->begin()->begin());
IRBuilder<> Builder(inst);
FunctionType *printf_type = TypeBuilder<int(char *, ...), false>::get(getGlobalContext());
Function *func = cast<Function>(M.getOrInsertFunction( "printf", printf_type,
AttributeSet().addAttribute(M.getContext(), 1U, Attribute::NoAlias)));
Value *helloWorld = Builder.CreateGlobalStringPtr("hello world!\n");
Builder.CreateCall(func, helloWorld);
return true;
}
};
}
char PrintfAfterMain::ID = 0;
static RegisterPass<PrintfAfterMain> X("PrintfAfterMain", "PrintfAfterMain World Pass", false, false);

我们可以看出,通过重写 ModulePass 的虚函数 runOnModule,只需要几行的代码,便可以实现该功能。简单说一些它的逻辑:在 LLVM 中,每一个 Module 可以看做就代表一个程序,ModulePass 就是对一个 Module 进行操作,一个 Module 维护着一个函数列表,一个 Function 维护有一个 BB 块列表,而一个 BB 块维护有一个指令列表,首先通过 Module 的 getFunction 方法找到 main ,如果没找到,说明模块中不存在 main 函数,这时候不需要对模块进行任何更改,直接返回 false 即可,如果存在 main 函数,那么便可以找到它的第一条指令:&(*F->begin()->begin()),然后,通过 IRBuilder.CreateCall 创建一个调用 printf 函数打印 hello, world!\n.

通过继承 FunctionPass 也可以实现该功能,FunctionPass 作用在每一个函数上,此时,重写 runOnFunction 方法,判断函数为 main 函数,如果不是,则返回,否则,同上进行指令插桩。

APA

APA 的全称是 automatic pool allocation,它是 LLVM 后端的一个优化框架,通过将分离的数据结构分配到不同的内存池中,从而控制数据结构在内存中布局。

编译原理研讨课上本人做了一个关于 APA 的调研,发现网上关于 APA 的资源很少,并且 APA 项目本身不稳定,甚至代码存在一些未修复的 bug,因此将编译安装/使用 APA 的一些步骤记录如下:

本次实验中使用的是 LLVM 3.3 和 poolalloc r192788

  • 下载 LLVM 3.3
1
svn co http://llvm.org/svn/llvm-project/llvm/branches/release_33/ llvm3.3
  • 下载 clang 3.3 到 llvm3.3/tools
1
2
cd llvm3.3/tools/
svn co http://llvm.org/svn/llvm-project/cfe/branches/release_33/ clang
  • 由于我在编译 Compiler RT 的时候发生错误,因此这儿不安装 Compiler RT

  • 下载 poolalloc 到 llvm3.3/projects

1
svn co http://llvm.org/svn/llvm-project/poolalloc/trunk/ poolalloc
  • 将 poolalloc 还原到版本 192788
1
svn update -r 192788
  • 修复 poolalloc 192788 中的一些bug, 调用 -poolalloc pass 时发生段错误:
1
2
cd /path/to/poolalloc
vi include/poolalloc/Heuristic.h

为 class Heuristic 添加成员方法 setGraphs:

1
2
3
void setGraphs(DataStructures ds){
Graph = ds;
}

PoolAllocate.cpp

1
vi lib/PoolAllocate/PoolAllocate.cpp

line 1252: CurHeuristic->getLocalPoolNodes (F, LocalNodes); 前插入CurHeuristic->setGraphs(Graphs);

  • 使用 ninja 进行编译安装

在 llvm3.3 同目录下:

1
2
3
4
mkdir build;
cd build;
cmake -G Ninja -DCMAKE_EXPORT_COMPILE_COMMANDS=ON -DCMAKE_INSTALL_PREFIX=/opt/llvm3.3 ../llvm3.3
ln -s ../build/compile_commands.json ..

编译:

1
ninja

安装:

1
sudo ninja install

  • 查看 poolalloc 是否安装成功:
1
2
cd /opt/llvm3.3/lib
find .|grep poolmalloc

如果能看到poolmalloc的库poolalloc.a、poolalloc.so, 则证明安装成功.

ninja 安装方法

1
2
3
4
git clone git://github.com/martine/ninja.git
cd ninja
./bootstrap.py
sudo cp ninja /usr/local/bin/

使用 DSA

1)查看与dsa相关的选项

1
opt -load /opt/llvm3.3/lib/LLVMDataStructure.so -load /opt/llvm3.3/lib/poolalloc.so --help|grep dsa

2)使用dsa(以dsa-local分析为例)

1
opt -load /opt/llvm3.3/lib/LLVMDataStructure.so -load /opt/llvm3.3/lib/poolalloc.so -analyze --dsa-local test.ll

使用poolalloc

1
2
3
4
5
6
7
clang -emit-llvm -c test.c;
/opt/llvm3.3/bin/opt -load /opt/llvm3.3/lib/LLVMDataStructure.so -load /opt/llvm3.3/lib/poolalloc.so -poolalloc test.o > test.o1;
/opt/llvm3.3/bin/llvm-dis test.o/test.o1;
//查看前后不同:diff test.o.ll test.o1.ll
//生成可执行文件:
llc test.o1.ll;
gcc /opt/llvm3.3/lib/libpoolalloc_rt.a test.o1.s;

Slide

下面,附上做报告时用的slide:

Automatic Pool Allocation

0%