为什么人人都该懂点 LLVM

Question

只要你和程序打交道，了解编译器架构就会令你受益无穷——无论是分析程序效率，还是模拟新的处理器和操作系统。通过本文介绍，即使你对编译器原本一知半解，也能开始用 LLVM，来完成有意思的工作。

LLVM 是什么？

LLVM 是一个好用、好玩，而且超前的系统语言（比如 C 和 C++语言）编译器。

当然，因为 LLVM 实在太强大，你会听到许多其他特性（它可以是个 JIT；支持了一大批非类 C 语言；还是 App Store 上的一种新的发布方式等等）。这些都是真的，不过就这篇文章而言，还是上面的定义更重要。

下面是一些让 LLVM 与众不同的原因：

• LLVM 的“中间表示”（IR）是一项大创新。LLVM 的程序表示方法真的“可读”（如果你会读汇编）。虽然看上去这没什么要紧，但要知道，其他编译器的中间表示大多是种内存中的复杂数据结构，以至于很难写出来，这让其他编译器既难懂又难以实现。
• 然而 LLVM 并非如此。其架构远比其他编译器要模块化得多。这种优点可能部分来自于它的最初实现者。
• 尽管 LLVM 给我们这些狂热的学术黑客提供了一种研究工具的选择，它还是一款有大公司做后台的工业级编译器。这意味着你不需要去在“强大的编译器”和“可玩的编译器”之间做妥协——不像你在 Java 世界中必须在 HotSpot 和 Jikes 之间权衡那样。

为什么人人需要懂点儿 LLVM？

是，LLVM 是一款酷炫的编译器，但是如果不做编译器研究，还有什么理由要管它？

答：只要你和程序打交道，了解编译器架构就会令你受益，而且从我个人经验来看，非常有用。利用它，可以分析程序要多久一次来完成某项工作；改造程序，使其更适用于你的系统，或者模拟一个新的处理器架构或操作系统——只需稍加改动，而不需要自己烧个芯片，或者写个内核。对于计算机科学研究者来说，编译器远比他们想象中重要。建议你先试试 LLVM，而不用 hack 下面这些工具（除非你真有重要的理由）：

• 架构模拟器；
• 动态二进制分析工具，比如 Pin；
• 源代码变换（简单的比如 sed，复杂一些的比如抽象语法树的分析和序列化）；
• 修改内核来干预系统调用；
• 任何和虚拟机管理程序相似的东西。

就算一个编译器不能完美地适合你的任务，相比于从源码到源码的翻译工作，它可以节省你九成精力。

下面是一些巧妙利用了 LLVM，而又不是在做编译器的研究项目：

• UIUC 的 Virtual Ghost，展示了你可以用编译器来保护挂掉的系统内核中的进程。
• UW 的 CoreDet 利用 LLVM 实现了多线程程序的确定性。
• 在我们的近似计算工作中，我们使用 LLVM 流程来给程序注入错误信息，以模仿一些易出错的硬件。

重要的话说三遍：LLVM 不是只用来实现编译优化的！LLVM 不是只用来实现编译优化的！LLVM 不是只用来实现编译优化的！

组成部分

LLVM 架构的主要组成部分如下（事实上也是所有现代编译器架构）：

前端，流程（Pass），后端

下面分别来解释：

• 前端获取你的源代码然后将它转变为某种中间表示。这种翻译简化了编译器其他部分的工作，这样它们就不需要面对比如 C++源码的所有复杂性了。作为一个豪迈人，你很可能不想再做这部分工作；可以不加改动地使用 Clang 来完成。
• “流程”将程序在中间表示之间互相变换。一般情况下，流程也用来优化代码：流程输出的（中间表示）程序和它输入的（中间表示）程序相比在功能上完全相同，只是在性能上得到改进。这部分通常是给你发挥的地方。你的研究工具可以通过观察和修改编译过程流中的 IR 来完成任务。
• 后端部分可以生成实际运行的机器码。你几乎肯定不想动这部分了。

虽然当今大多数编译器都使用了这种架构，但是 LLVM 有一点值得注意而与众不同：整个过程中，程序都使用了同一种中间表示。在其他编译器中，可能每一个流程产出的代码都有一种独特的格式。LLVM 在这一点上对 hackers 大为有利。我们不需要担心我们的改动该插在哪个位置，只要放在前后端之间某个地方就足够了。

开始

让我们开干吧。

获取 LLVM

首先需要安装 LLVM。Linux 的诸发行版中一般已经装好了 LLVM 和 Clang 的包，你直接用便是。但你还是需要确认一下机子里的版本，是不是有所有你要用到的头文件。在 OS X 系统中，和 XCode 一起安装的 LLVM 就不是那么完整。还好，用 CMake 从源码构建 LLVM 也没有多难。通常你只需要构建 LLVM 本身，因为你的系统提供的 Clang 已经够用（只要版本是匹配的，如果不是，你也可以自己构建 Clang）。

具体在 OS X 上，Brandon Holt 有一个不错的指导文章。用 Homebrew 也可以安装 LLVM。

去读手册

你需要对文档有所了解。我找到了一些值得一看的链接：

• 自动生成的 Doxygen 文档页 非常重要。要想搞定 LLVM，你必须要以这些 API 的文档维生。这些页面可能不太好找，所以我推荐你直接用 Google 搜索。只要你在搜索的函数或者类名后面加上“LLVM”，你一般就可以用 Google 找到正确的文档页面了。（如果你够勤奋，你甚至可以“训练”你的 Google，使得在不输入 LLVM 的情况下它也可以把 LLVM 的相关结果推到最前面）虽然听上去有点逗，不过你真的需要这样找 LLVM 的 API 文档——反正我没找到其他的好方法。
• 《语言参考手册》 也非常有用，如果你曾被 LLVM IR dump 里面的语法搞糊涂的话。
• 《开发者手册》 描述了一些 LLVM 特有的数据结构的工具，比如高效字符串，vector 和 map 的替代品等等。它还描述了一些快速类型检查工具 isa 、 cast 和 dyn_cast ），这些你不管在哪都要跑。
  ◾如果你不知道你的流程可以做什么，读 《编写 LLVM 流程》 。不过因为你只是个研究人员而不是浸淫于编译器的大牛，本文的观点可能和这篇教程在一些细节上有所不同。（最紧急的是，别再用基于 Makefile 的构建系统了。直接开始用 CMake 构建你的程序吧，读读 《“源代码外”指令》 ）尽管上面这些是解决流程问题的官方材料，
• 不过在在线浏览 LLVM 代码时，这个 GitHub 镜像 有时会更方便。

写一个流程

使用 LLVM 来完成高产研究通常意味着你要写一些自定义流程。这一节会指导你构建和运行一个简单的流程来变换你的程序。

框架

我已经准备好了 模板仓库 ，里面有些没用的 LLVM 流程。我推荐先用这个模板。因为如果完全从头开始，配好构建的配置文件可是相当痛苦的事。

首先从 GitHub 上下载 llvm-pass-skeleton 仓库 ：

$ git clone git@github.com:sampsyo/llvm-pass-skeleton.git

主要的工作都是在 skeleton/Skeleton.cpp 中完成的。把它打开。这里是我们的业务逻辑：

virtual bool runOnFunction(Function &F) { 
  errs() << "I saw a function called " << F.getName() << "!\n";
  return false; 
}

LLVM 流程有很多种，我们现在用的这一种叫 函数流程（function pass） （这是一个不错的入手点）。正如你所期望的，LLVM 会在编译每个函数的时候先唤起这个方法。现在它所做的只是打印了一下函数名。

细节：

• errs() 是一个 LLVM 提供的 C++输出流，我们可以用它来输出到控制台。
• 函数返回 false 说明它没有改动函数 F。之后，如果我们真的变换了程序，我们需要返回一个 true。

构建

通过 CMake 来构建这个流程：

$ cd llvm-pass-skeleton 
$ mkdir build 
$ cd build 
$ cmake ..  # Generate the Makefile. 
$ make  # Actually build the pass.

如果 LLVM 没有全局安装,你需要告诉 CMake LLVM 的位置.你可以把环境变量 LLVM_DIR 的值修改为通往 share/llvm/cmake/ 的路径。比如这是一个使用 Homebrew 安装 LLVM 的例子：

$ LLVM_DIR=/usr/local/opt/llvm/share/llvm/cmake cmake ..

构建流程之后会产生一个库文件，你可以在 build/skeleton/libSkeletonPass.so 或者类似的地方找到它，具体取决于你的平台。下一步我们载入这个库来在真实的代码中运行这个流程。

运行

想要运行你的新流程，用 clang 编译你的 C 代码，同时加上一些奇怪的 flag 来指明你刚刚编译好的库文件：

$ clang -Xclang -load -Xclang build/skeleton/libSkeletonPass.* something.c 
I saw a function called main!

-Xclang -load -Xclang path/to/lib.so 这是你在 Clang 中载入并激活你的流程所用的所有代码。所以当你处理较大的项目的时候，你可以直接把这些参数加到 Makefile 的 CFLAGS 里或者你构建系统的对应的地方。

（通过单独调用 clang ，你也可以每次只跑一个流程。这样需要用 LLVM 的 opt 命令。这是 官方文档里的合法方式 ，但在这里我就不赘述了。）

恭喜你，你成功 hack 了一个编译器！接下来，我们要扩展这个 hello world 水平的流程，来做一些好玩的事情。

理解 LLVM 的中间表示

想要使用 LLVM 里的程序，你需要知道一点中间表示的组织方法。

模块（Module），函数（Function），代码块（BasicBlock），指令（Instruction）
模块 包含了 函数 ，函数又包含了 代码块 ，后者又是由 指令 组成。除了模块以外，所有结构都是从 值 产生而来的。

容器

首先了解一下 LLVM 程序中最重要的组件：

• 粗略地说，模块表示了一个源文件，或者学术一点讲叫翻译单元。其他所有东西都被包含在模块之中。
• 最值得注意的是，模块容纳了函数，顾名思义，后者就是一段段被命名的可执行代码。（在 C++中，函数 function 和方法 method 都相应于 LLVM 中的函数。）
• 除了声明名字和参数之外，函数主要会做为代码块的容器。代码块和它在编译器中的概念差不多，不过目前我们把它看做是一段连续的指令。
• 而说到指令，就是一条单独的代码命令。这一种抽象基本上和 RISC 机器码是类似的：比如一个指令可能是一次整数加法，可能是一次浮点数除法，也可能是向内存写入。

大部分 LLVM 中的内容——包括函数，代码块，指令——都是继承了一个名为值的基类的 C++类。值是可以用于计算的任何类型的数据，比如数或者内存地址。全局变量和常数（或者说字面值，立即数，比如 5）都是值。

指令

这是一个写成人类可读文本的 LLVM 中间表示的指令的例子。

%5 = add i32 %4, 2

这个指令将两个 32 位整数相加（可以通过类型 i32 推断出来）。它将 4 号寄存器（写作 %4 ）中的数和字面值 2（写作 2 ）求和，然后放到 5 号寄存器中。这就是为什么我说 LLVM IR 读起来像是 RISC 机器码：我们甚至连术语都是一样的，比如寄存器，不过我们在 LLVM 里有无限多个寄存器。

在编译器内，这条指令被表示为 指令 C++类的一个实例。这个对象有一个操作码表示这是一次加法，一个类型，以及一个操作数的列表，其中每个元素都指向另外一个值（Value）对象。在我们的例子中，它指向了一个代表整数 2 的 常量 对象和一个代表 5 号寄存器的 指令 对象。（因为 LLVM IR 使用了 静态单次分配格式 ，寄存器和指令事实上是一个而且是相同的，寄存器号是人为的字面表示。）

另外，如果你想看你自己程序的 LLVM IR，你可以直接使用 Clang：

$ clang -emit-llvm -S -o - something.c

查看流程中的 IR

让我们回到我们正在做的 LLVM 流程。我们可以查看所有重要的 IR 对象，只需要用一个普适而方便的方法： dump() 。它会打印出人可读的 IR 对象的表示。因为我们的流程是处理函数的，所以我们用它来迭代函数里所有的代码块，然后是每个代码块的指令集。

下面是代码。你可以通过在 llvm-pass-skeleton 代码库中切换到 containers 分支 来获得代码。

errs() << "Function body:\n";
F.dump(); 
for (auto& B : F) { 
  errs() << "Basic block:\n";
  B.dump(); 
  for (auto& I : B) { 
    errs() << "Instruction: "; 
    I.dump();  
  } 
}

使用 C++ 11 里的 auto 类型和 foreach 语法可以方便地在 LLVM IR 的继承结构里探索。

如果你重新构建流程并通过它再跑程序，你可以看到很多 IR 被切分开输出，正如我们遍历它那样。

做些更有趣的事

当你在找寻程序中的一些模式，并有选择地修改它们时，LLVM 的魔力真正展现了出来。这里是一个简单的例子：把函数里第一个二元操作符（比如+，-）改成乘号。听上去很有用对吧？

下面是代码。这个版本的代码，和一个可以试着跑的示例程序一起，放在了 llvm-pass-skeleton 仓库的 mutate 分支 。

for (auto& B : F) {
  for (auto& I : B) {
    if (auto* op = dyn_cast<BinaryOperator>(&I)) {
      // Insert at the point where the instruction `op` appears.
      IRBuilder<> builder(op);

      // Make a multiply with the same operands as `op`.
      Value* lhs = op->getOperand(0);
      Value* rhs = op->getOperand(1);
      Value* mul = builder.CreateMul(lhs, rhs);

      // Everywhere the old instruction was used as an operand, use our
      // new multiply instruction instead.
      for (auto& U : op->uses()) {
        User* user = U.getUser();  // A User is anything with operands.
        user->setOperand(U.getOperandNo(), mul);
      }

      // We modified the code.
      return true;
    }
  }
}

细节如下：

• dyn_cast<T>(p) 构造函数是 LLVM 类型检查工具 的应用。使用了 LLVM 代码的一些惯例,使得动态类型检查更高效，因为编译器总要用它们。具体来说，如果 I 不是“二元操作符”，这个构造函数返回一个空指针，就可以完美应付很多特殊情况（比如这个）。
• IRBuilder 用于构造代码。它有一百万种方法来创建任何你可能想要的指令。
• 为把新指令缝进代码里，我们需要找到所有它被使用的地方，然后当做一个参数换进我们的指令里。回忆一下，每个指令都是一个值：在这里，乘法指令被当做另一条指令里的操作数，意味着乘积会成为被传进来的参数。
• 我们其实应该移除旧的指令，不过简明起见我把它略去了。

现在我们编译一个这样的程序（代码库中的 example.c ）：

#include <stdio.h>
int main(int argc, const char** argv) {
    int num;
    scanf("%i", &num);
    printf("%i\n", num + 2);
    return 0;
}

如果用普通的编译器，这个程序的行为和代码并没有什么差别；但我们的插件会让它将输入翻倍而不是加 2。

$ cc example.c
$ ./a.out
10
12
$ clang -Xclang -load -Xclang build/skeleton/libSkeletonPass.so example.c
$ ./a.out
10
20

很神奇吧！

链接动态库

如果你想调整代码做一些大动作，用 IRBuilder 来生成 LLVM 指令可能就比较痛苦了。你可能需要写一个 C 语言的运行时行为，然后把它链接到你正在编译的程序上。这一节将会给你展示如何写一个运行时库，它可以将所有二元操作的结果记录下来，而不仅仅是闷声修改值。

这里是 LLVM 流程的代码，也可以在 llvm-pass-skeleton 代码库的 rtlib 分支 找到它。

// Get the function to call from our runtime library.
LLVMContext& Ctx = F.getContext();
Constant* logFunc = F.getParent()->getOrInsertFunction(
  "logop", Type::getVoidTy(Ctx), Type::getInt32Ty(Ctx), NULL
);

for (auto& B : F) {
  for (auto& I : B) {
    if (auto* op = dyn_cast<BinaryOperator>(&I)) {
      // Insert *after* `op`.
      IRBuilder<> builder(op);
      builder.SetInsertPoint(&B, ++builder.GetInsertPoint());

      // Insert a call to our function.
      Value* args[] = {op};
      builder.CreateCall(logFunc, args);

      return true;
    }
  }
}

你需要的工具包括 Module::getOrInsertFunction 和 IRBuilder::CreateCall 。前者给你的运行时函数 logop 增加了一个声明（类似于在 C 程序中声明 void logop(int i); 而不提供实现）。相应的函数体可以在定义了 logop 函数的运行时库（代码库中的 rtlib.c ）找到。

#include <stdio.h>
void logop(int i) {
  printf("computed: %i\n", i);
}

要运行这个程序，你需要链接你的运行时库：

$ cc -c rtlib.c
$ clang -Xclang -load -Xclang build/skeleton/libSkeletonPass.so -c example.c
$ cc example.o rtlib.o
$ ./a.out
12
computed: 14
14

如果你希望的话，你也可以在编译成机器码之前就缝合程序和运行时库。llvm-link 工具——你可以把它简单看做 IR 层面的 ld 的等价工具，可以帮助你完成这项工作。

注记（Annotation）

大部分工程最终是要和开发者进行交互的。你会希望有一套注记（annotations），来帮助你从程序里传递信息给 LLVM 流程。这里有一些构造注记系统的方法：

• 一个实用而取巧的方法是使用魔法函数。先在一个头文件里声明一些空函数，用一些奇怪的、基本是独特的名字命名。在源代码中引入这个头文件，然后调用这些什么都没有做的函数。然后，在你的流程里，查找唤起了函数的 CallInst 指令 ，然后利用它们去触发你真正要做的“魔法”。比如说，你可能想调用 __enable_instrumentation() 和 __disable_instrumentation() ，让程序将代码改写限制在某些具体的区域。
• 如果想让程序员给函数或者变量声明加记号，Clang 的 __attribute__((annotate("foo"))) 语法会发射一个 元数据 和任意字符串，可以在流程中处理它。Brandon Holt（又是他）有篇 文章 讲解了这个技术的背景。如果你想标记一些表达式，而非声明，一个没有文档，同时很不幸受限了的 __builtin_annotation(e, "foo")内建方法 可能会有用。
• 可以自由修改 Clang 使它可以翻译你的新语法。不过我不推荐这个。
• 如果你需要标记类型——我相信大家经常没意识到就这么做了——我开发了一个名为 Quala 的系统。它给 Clang 打了补丁，以支持自定义的类型检查和可插拔的类型系统，到 Java 的 JSR-308 。如果你对这个项目感兴趣，并且想合作，请联系我。

我希望能在以后的文章里展开讨论这些技术。

其他

LLVM 非常庞大。下面是一些我没讲到的话题：

• 使用 LLVM 中的一大批古典编译器分析；
• 通过 hack 后端来生成任意的特殊机器指令（架构师们经常想这么干）；
• 利用 debug info 连接源代码中的行和列到 IR 中的每一处；
• 开发[Clang 前端插件]。( http://clang.llvm.org/docs/ClangPlugins.html )

我希望我给你讲了足够的背景来支持你完成一个好项目了。探索构建去吧！如果这篇文章对你帮助，也请 让我知道 。

---

感谢 UW 的架构与系统组，围观了我的这篇文章并且提了很多很赞的问题。

以及感谢以下的读者：

• Emery Berger 指出了动态二进制分析工具，比如 Pin，仍然是你在观察系统结构中具体内容（比如寄存器，内存继承和指令编码等）的好帮手；
• Brandon Holt 发了一篇 《LLVM debug 技巧》 ，包括如何用 GraphViz 绘制控制流图；
• John Regehr 在评论中提到把软件搭在 LLVM 上的缺点：API 不稳定性。LLVM 内部几乎每版都要大换，所以你需要不断维护你的项目。 Alex Bradbury 的 LLVM 周报 是个跟进 LLVM 生态圈的好资源。