写给入门者的LLVM介绍

翻译自: LLVM for Grad Students

本文是针对 LLVM 这个编译器基础设施的介绍, 无论是对编译器毫无兴趣的同学, 或是期待使用它做很多有趣工作的同学, 都应有所得.

LLVM 是什么?

LLVM 是一个编译器 (确切的说是一套框架+基于框架的一些编译器实现, 如 clang), 是当下很先进的一套编译系统. 特别对于 C/C++/Objective-C 等语言而言, 更是如此.

当然它也不止于此, 它也支持 JIT, 以及很多非 C 家族的语言.

LLVM 之所以优秀, 在于以下几点:

LLVM 的中间表达 (IR) 是可以 dump 出来成为可阅读的文本形式的 (语法有点像汇编), 看起来微不足道, 但是其他很多编译器却只有内存中的数据结构, 使得学习调试难度大增.
模块化的设计比较好, 这一方面是后发优势, 吸收了很多前人经验, 也和设计者的架构功力息息相关.
虽然始于学术项目, 但 LLVM 一直受到工业界的支持 (Apple), 所以不仅好用, 而且开源可定制. 避免了在 Java 中类似面临选择 HotSpot 和 Jikes 的困境.

为什么关心 LLVM?

LLVM 是很好, 可如果不做编译器研究, 了解它有什么用呢?

了解编译器, 可以帮助我们分析程序的行为, 针对系统做程序的转译 (transform) 优化. 诸如数据处理框架中, 当使用高阶 API 甚至是 SQL 编写的程序, 如何用编译的思路提升它们的运行效率等等. 如果未来有可能从事下面的工作, 提前了解 LLVM 对后续的学习会很有帮助:

模拟器
类似于 Pin 的动态二进制检测工具
源码级转换 (从简单的东西 sed 到涉及 AST 解析和序列化的更完整的工具)
破解内核以拦截系统调用
任何类似于管理程序的东西

有时候一项工作看起来并不完全是个完整的编译行为, 但只要涉及到源码到源码的转换, 了解 LLVM 通常会有所帮助.

以下是一些使用 LLVM 完成并非所有编译操作的研究项目的示例:

UIUC 的 Virtual Ghost 展示了您以使用编译器通道来保护进程免受受损操作系统内核的影响.
UW 的 CoreDet 使多线程程序具有确定性.
在近似计算工作中, 使用 LLVM pass 将错误注入程序以模拟容易出错的硬件.

再次强调: LLVM 不只是用于实现新的编译器及编译优化!

基本架构

这张图片显示了 LLVM 架构的主要部件:

实际上是任何现代编译器的架构有:

前端, 获取源代码并将其转换为中间表示或 IR. 这种翻译简化了编译器其余部分的工作, 它不想处理 C++ 源代码的全部复杂性. 比如 Clang
将 IR 转换为 IR 的 Pass. 在一般情况下, pass 通常会优化代码: 生成一个 IR 程序作为输出, 它与作为输入的 IR 执行相同的操作, 只是它更快更优. 这是需要拓展定制的地方. 使用相关工具可以通过在编译过程中查看和更改 IR 来进行.
后端, 生成实际的机器码. 很多时候不需要接触这部分.

尽管这种架构描述了当今大多数编译器, 但这里值得注意的是 LLVM 的一个新颖之处: 整个编译过程中使用相同的 IR. 在其他编译器中, 每次传递都可能以独特的形式生成代码.

上手实操

安装 LLVM

Linux 发行版通常有现成的 LLVM 和 Clang 包. 但是需要确保您获得的版本包含破解它所需的所有头文件 (headers). 例如, Xcode 附带的 OS X 不够完整. 幸运的是, 使用 CMake 从源代码构建 LLVM 并不难. 通常只需要自己构建 LLVM: 只要版本匹配, 系统提供的 Clang 就可以正常工作 (尽管也有构建 Clang 的说明).

在 macOS 上, 参考 Brandon Holt 的教程.

RTFM

API 文档非常重要, 但这些页面可能很难导航, 因此建议通过 Google: LLVM + 任何函数或类名来寻找对应的页面.
如果对 IR dump 出来的语法不熟悉, 这有 IR 语法参考手册.
程序员手册介绍了 LLVM 特有的数据结构的工具箱. 包括高效的字符串, maps 和 vectors 的 STL 替代方案等. 它还概述了将在任何地方遇到的快速类型自省 (fast type introspection) 工具.
阅读编写 LLVM Pass 的教程 .
GitHub 镜像便于在线浏览 LLVM 源码 .

写一个 Pass

骨架代码

这里有一个模板, 其中包含一个待实现的 LLVM Pass. 之所以从模板开始: 是因为如果一切从头开始, 设置构建配置可能会很痛苦.

使用下面的命令克隆 llvm-pass-skeletion 这个仓库:

$ git clone https://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 pass 有几种, 我们使用一种称为 function pass (这是一个很好的学习起点). LLVM 使用它在我们编译的程序中找到的每个函数调用上述方法. 现在, 它所做的只是打印出名称.

errs() 是 LLVM 提供的 C++ 输出流, 我们可以使用它来打印到控制台. 函数返回 false 表明它没有修改函数 F. 稍后, 当我们真正转换程序时, 我们需要 return true.

构建它

使用 CMake 来构建这个 Pass:

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

如果 LLVM 没有进行全局安装, 你需要告诉 CMake 在哪里可以找到它. 此时需要置环境变量 LLVM_DIR 为 llvm 的对应目录. 这是 Homebrew 的路径示例:

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

构建会生成一个共享库. 可以是 build/skeleton/libSkeletonPass.so 或类似名称, 具体取决于平台.

运行它

调用 clang 编译执行 C 程序并使用一些 flag 来指向刚刚编译的共享库:

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

如果需要处理更大的项目, 可以将这些参数添加到 Makefile CFLAGS 或构建系统的等效文件中.

了解 LLVM IR

需要了解一些关于 IR 的基本组织结构.

Module 包含 Function, 其中包含 BasicBlock, 其中包含 Instruction. 除了 Module 之外的所有东西都来自 Value.

容器层次

以下是 LLVM 程序中最重要组件的概述:

一个模块 (Module) 代表一个源文件 (粗略地) 或一个翻译单元. 其他所有内容都包含在模块中.
最值得注意的是, Modules 包含 Function: 命名的可执行代码块. 在 C++ 中, 函数和方法都对应于 LLVM 函数.
除了声明其名称和参数外, Function 主要是 BasicBlock (BB) 的容器. 基本块 (BB) 是编译器的概念, 但就我们的目的而言, 它只是一段连续的指令.
反过来, 指令是单个代码操作. 抽象级别与类似 RISC 的机器代码中的抽象级别大致相同: 例如, 指令可能是整数加法, 浮点除法或存储到内存.

LLVM 中的大多数东西 (包括 Function, BasicBlock 和 Instruction) 都是从名为 Value 的基类继承而来. Value 是可以在计算中使用的任何数据: 例如, 数字或某些代码的地址. 全局变量和常量 (又名 literals 或 immediates, 如 5) 也是 Value.

IR 指令举例

以下是 LLVM IR 的人类可读文本形式的指令示例:

%5 = add i32 %4, 2

该指令将两个 32 位整数值相加 (由 type 表示 i32). 它将寄存器 4 中的数字 (写入%4) 和文字数字 2(写入 2) 相加, 并将其结果放入寄存器 5. 这就是 LLVM IR 看起来像 RISC 机器代码的意思: 我们甚至使用相同的术语, 像 register, 但有无限多的寄存器.

同一条指令在编译器内部表示为指令 C++ 类的实例. 该对象有一个操作码, 表明它是一个加法, 一个类型和一个操作数列表, 这些操作数是指向其他 Value 对象的指针. 在我们的例子中, 它指向一个表示数字 2 的常量对象和对应于寄存器 %4 的另一个指令. (由于 LLVM IR 是静态单一赋值 (SSA) 形式, 寄存器和指令实际上是一个且相同的. 寄存器编号是文本表示的产物.)

如果想查看你的程序的 LLVM IR, 可以用 Clang 这样做:

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

查看 IR

回到正在处理的 LLVM Pass. 可以通过将所有重要的 IR 对象发送到 ostream 带有<<. 打印出 IR 中对象的人类可读表示. 由于 pass 被传递给 Functions, 让我们用它来遍历每个 Function 的 BasicBlocks, 然后遍历每个 BasicBlock 的指令集.

这里有一些代码可以做到这一点, 可以通过查看这个骨架代码仓库的这个分支来获取它们.

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

使用 C++11 的 auto 类型和 foreach 语法可以轻松导航 LLVM IR 中的层次结构.

如果再次构建 pass 并通过它运行程序, 现在应该看到 IR 的各个部分在我们遍历它们时被拆分出来.

让 Pass 做点有趣的事情

当在程序中寻找模式时, 真正的魔力就会出现, 可以选择在找到它们时更改代码.

一个非常简单的示例: 假设我们想用乘法替换每个函数中的第一个二元运算符 (+, -等). 听起来虽然很没用, 但却是很有趣呀, 对吧?

这是执行此操作的代码. 这个版本, 连同一个示例程序, 可以在代码库 mutate 分支中找到.

for (auto& B : F) {
  for (auto& I : B) {
    if (auto* op = dyn_cast<BinaryOperator>(&I)) {
      // 指定 `op` 出现的位置进行代码改写.
      IRBuilder<> builder(op);

      // 创建相同操作数的乘法 op`.
      Value* lhs = op->getOperand(0);
      Value* rhs = op->getOperand(1);
      Value* mul = builder.CreateMul(lhs, rhs);

      // 在 op 所有使用到的地方, 插入新生成的乘法指令.
      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 自省的一个方法, 它用于提高动态类型测试的效率. I 如果不是一个二元操作符 (BinaryOperator), 这个特殊的方法会返回一个空指针, 所以它非常适合我们现在要做的事情 (替换每个函数中的第一个二元运算符).
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

像变戏法一样!

与运行时库链接

如果任何复杂的改写行为都直接用 Builder 来完成, 就太痛苦了, 能不能在 Builder 调用提前写好的运行时库呢?

示例代码位于 rtlib 分支中.

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

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, 类似于 void logop(int i). 最终与运行时库 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 可以帮助我们实现这一点.

传递信息给 pass

当我们需要将额外信息传递到 Pass 过程中时, 有一些常用的手段:

实用和 hacky 的方法是使用魔法函数 (magic function), 找到 CallInstinstructions 来获取调用这些函数的地方并触发对应的操作. 例如, 调用__enable_instrumentation(), __disable_instrumentation() 让限制代码的修改区域.
如果在函数或变量声明中添加标记, Clang 的__attribute__((annotate("foo"))) 语法将发出带有任意字符串的元数据, 可以在 pass 中处理该元数据. 如果需要标记表达式, 没有记录到文档中的__builtin_annotation(e, "foo") 原语可能有用.
可以修改 Clang 本身以解释新语法. 不推荐这个.