Introduction to LLVM Pass and APA

LLVM Pass

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

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

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

#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

svn co http://llvm.org/svn/llvm-project/llvm/branches/release_33/ llvm3.3

• 下载 clang 3.3 到 llvm3.3/tools

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

svn co http://llvm.org/svn/llvm-project/poolalloc/trunk/ poolalloc

• 将 poolalloc 还原到版本 192788

svn update -r 192788

• 修复 poolalloc 192788 中的一些bug, 调用 -poolalloc pass 时发生段错误：

cd /path/to/poolalloc
vi include/poolalloc/Heuristic.h

为 class Heuristic 添加成员方法 setGraphs:

void setGraphs(DataStructures ds){
	Graph = ds;
}

PoolAllocate.cpp

vi lib/PoolAllocate/PoolAllocate.cpp

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

• 使用 ninja 进行编译安装

在 llvm3.3 同目录下：

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 ..

编译：

ninja

安装：

sudo ninja install

• 查看 poolalloc 是否安装成功：

cd /opt/llvm3.3/lib
find .|grep poolmalloc

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

ninja 安装方法

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

使用 DSA

1)查看与dsa相关的选项

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

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

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

使用poolalloc

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