PostgreSQL JIT(Just-In-Time Compilation）With LLVM 的实现原理

前言

最近在解决一个postgresql on JIT 上的内存问题，刚好能够有机会深入了解学习这个技术，以及 PG 如何利用 LLVM 来实现这个技术。

JIT (Just-In-Time Compilation) 动态编译技术，能够在程序运行过程中 生成优化后的程序执行逻辑，能够减少不必要的CPU分支跳转，达到提升性能的目的。比如在 PostgreSQL 这样的数据库内部有非常多的通用逻辑，对于一个表达式算子 WHERE a.col = 3 在正常的执行过程中需要经过一系列的分支判断，而JIT 能够优化这一些分支判断，生成具体的执行函数来执行这个表达式。所以 JIT 在PG 内部实际生效的位置肯定是优化器之后，拿到了具体的执行计划，就可以通过JIT 优化执行逻辑，填充具体的执行函数。

在PostgreSQL 中有非常多的通用逻辑，比如像 元组解析(heap_tuple_deforming) 有很多针对attr 类型的判断，通过JIT 能够极大得简化这样的逻辑，这种性能方面的提升对PG来说是巨大的。PG 是通过 LLVM（Low-Level-Virtual-Machine）实现JIT的，之所以选择 LLVM 主要的原因如下：

1. 技术成熟且社区稳定度足够高。因为 LLVM 背后有apple 公司的支持，资金链不会断，又拥有GNU社区 以及 其他庞大的贡献者群体，整个社区能够最大可能得延续下去。
2. LLVM 社区 和 PostgreSQL 开源协议(llvm是 apache 2.0)兼容度较高，都允许个人/公司 二次开发。
3. LLVM 的前端编译器 clang 支持C代码生成 IR 过程需要的bitcode。

本篇在介绍 PG 的JIT 实现之前会先用个人浅薄的学习历程介绍一下LLVM ，其作为编译器工具集实在是过于庞大（社区已经有超过 44w commits了），这个方向的知识体系之庞大相比于数据库内核来说甚至犹有过之，所以只能是入门级别的一些介绍了（实现源码还都没有怎么看过）。

LLVM

llvm 推出的背景也是受GCC的影响：

1. 学术方面，GCC 20-30年前作为极少数开源的编译器，被用作教学。但是当时软件工程理论还没有那么完善的情况下，GCC 用 C语言编写出来的编译器各个组件耦合度极高，很难让学生们将其中的某一个组件单独拿出来学习研究。GCC的内核越来越庞大的情况下，新加入的开发者也很难对整体的架构有大的改动，整个项目的开发难度也会越来越难，新特性的开发成本也会极高。不利于学习，不利于有热情的新的开发者们参与。
2. 工业界方面则受限于 GPL 的协议，无法自由开发。很多编译器的研究人员也担心自己开发的代码只会使用一次就被丢弃，很有挫败感。

主要 基于以上原因，Chris Lattner 带领他的团队重新设计了 各个编译器组件完全解耦的编译器架构，而且在开源协议上更为自由，各个公司可以用作商业用途且只需要保留copyright 就好，这应该也是 乔布斯 欣赏LLVM 并收购这个项目及其团队的原因（传奇依旧在为未来做贡献）。

最开始的时候 LLVM 是将GCC 仅作为自己的前端，用来将高级语言转换为 LLVM IR需要的中间语言 bitcodes file。这也就导致用户想要用 llvm 的时候还需要配置GCC环境，而且 llvm 想要将很多工作放在 前端来做的话（代码静态分析，代码格式化，其他优化）需要对GCC有较大的改造，成本极高。所以 llvm 直接 重写前端部分，这也是 Clang 出现的原因，而且 Clang兼容 GCC，也提供了极为丰富的工具集合。

LLVM 编译

因为 llvm 代码仓库过于庞大，直接拉整个代码仓库的所有版本信息会超过github的大小限制。这里如果要从github 拉代码，建议只拉对应版本的最新commit即可（考虑到可能github有限速，这里贴的是清华源的链接）。
git clone -b release/13.x --depth 1 https://mirrors.tuna.tsinghua.edu.cn/git/llvm-project.git llvm-project-13
编译过程如下(主要编译的是 项目目录下的 llvm目录，这是其库的核心)：

cd llvm-project-13
mkdir build && cd build
cmake -G Ninja -DCMAKE_BUILD_TYPE=debug ../llvm
ninja -j5 && make install
1
2
3
4

如果想要编译其他的组件，比如clang，也可以用同样的方式，cmake 最后指定的目录变成clang就好了。
大多数情况如果是使用的话完全不需要自己编译，比如ubuntu ，直接 sudo apt-get install llvm-10这种就可以了，编译安装可能适用于 高版本的llvm 以及 增加debug 信息，或者想要了解/学习 llvm工具集合 以及实现原理的自己编译会更方便一些。

LLVM 基本架构

LLVM 基本架构如下（图片来自 《Getting started with LLVM core libraries》）：

各个组件各司其职：

• clang – 词法分析/语法（语义）分析
• LLVM IR linker – 中间代码生成
• LLVM IR optimizer – 代码优化
• LLVM backend – 生成目标代码（对接不同的平台 – X86, XCore, ARM, AArch64等），能够支持跨平台编译
• LLVM integrated assembler 用于生成binary

hh宏观上主要有这几个部分：

• Frontend 前端（以clang/gcc 为主），主要工作是将计算机高级语言（C/C++/Objective-C等）转换为 LLVM 编译器 IR。包括了前面说的clang 的工作。
• IR 中间语言（Intermediate Representation）。包括 人可读(ll文件)的/字节编码(bitcode文件) 的两种方式。提供非常多的工具和调用库来构造 和 解析 两种文件。能够解析 clang编译好的 bitcode文件到内存中，可以做非常多的代码优化。JIT 的核心就是利用 IR 达成代码优化的目的。
• Backend 后端。将生成的IR 转换为汇编代码 或者 二进制机器码。像是 寄存器分配，循环转换，特定对象的优化 都会在后端来做，最靠近CPU的部分。

整个架构内部的各个组件都可以单独拿出来和其他的项目使用，或者说禁止其中的某一个组件。
比如 不想使用LLVM IR linker，就可以禁止掉；想要使用clang作为前端的编译器 以及 代码检查分析工具，不想要使用 LLVM-IR，clang就可以单独拿出去用；opt 作为llvm的一个命令集成 libLLVMipa库，也可以单独对代码进行 IR优化。

从前面编译的结果也能够看到，llvm 提供的内部工具极多：

因为本篇主要关注的是 LLVM 的 IR ，所以接下来会浅浅得介绍一下IR。

LLVM IR

IR(Intermediate Representation) – 中间语言 作为LLVM的核心，连接了 LLVM 的前端和后端。前端负责生成IR，后端负责消费IR。
LLVM IR的设计按照官方的描述 是考虑在支持更多更通用的平台以及前端语言的情况下 保障性能，可能相比于某一些专有优化器只针对特定的平台来做的IR 功能来说性能差一些，但LLVM 目的是通用性（不是每一个公司都有足够的人力和财力投入在自己平台的编译器设计和开发中的）。
LLVM IR 的基本形态如下：

IR 有三种等价的形态：

1. 内存形态的中间语言表示（主要是原始代码的 指令抽象，通过Instruction 类 以及其他 Module,Function 这种表示）

2. 磁盘上的语言表示，用空间利用率较高的编码方式形成的 bitcode files，后面会介绍一下这个文件的格式。IR 实现的时候会解析这一些格式到内存中，形成内存形态的中间语言表示。

   在postgresql 中，一般处于编译之后的lib目录下 ：$libdir/postgresql/bitcode

3. 另一种磁盘上的语言表示(ll文件)，人可读的一种格式。

LLVM IR两种磁盘文件的生成方式

对于如下代码 sum.c：

int sum(int a, int b)
{
  return a+b;
}
1
2
3
4

通过如下命令可以将sum.c 转为 bitcode形态，.bc 文件的内容就都是字节序的形态了：

clang sum.c -emit-llvm -c -o sum.bc
1

想要看的话只能vim打开，:%!xxd来看具体字节内容了，而且bitcode文件的大小相比于原始代码文件小很多，在PostgreSQL 编译的bitcode文件相比于原始文件空间占用甚至小了两倍，但其表示的代码内容可一点也没少（转为字节数组形态压缩率还是比较好控制）。

将 sum.c 转为 人可读的另一种 ll 文件:

clang sum.c -emit-llvm -S -c -o sum.ll
1

其内容如下：

对于 sum.ll 文件，可以通过 llvm-as sum.ll -o sum.bc转为 bc文件，也能通过 llvm-dis sum.bc -o sum.ll 将bc文件转位ll文件，这一些文件内部主要保存的是具体的函数 以及 各种变量/参数信息，所以llvm 也提供了从bc 文件直接提取 函数/变量的 工具:

llvm-extract -func=sum sum.bc -o sum-fn.bc
1

LLVM IR .ll 文件 语法形态

之所以介绍这个，首先bc文件 内容是字节序，不太好看懂，其次 .ll 文件和bc 文件 在 IR 看来是等价的，只是表示的方式不一样，最后解析到内存中生成内存的 IR 表示的时候也是按照这个 ll 文件里面的关键模块来解析的，可以方便理解后续要说的 PostgreSQL-JIT 的代码。

还是用上面的 sum.ll 文件举例:

; ModuleID = 'sum.c'
source_filename = "sum.c"
target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
target triple = "x86_64-pc-linux-gnu"

; Function Attrs: noinline nounwind optnone uwtable
define dso_local i32 @sum(i32 %0, i32 %1) #0 {
  %3 = alloca i32, align 4
  %4 = alloca i32, align 4
  store i32 %0, i32* %3, align 4
  store i32 %1, i32* %4, align 4
  %5 = load i32, i32* %3, align 4
  %6 = load i32, i32* %4, align 4
  %7 = add nsw i32 %5, %6
  ret i32 %7
}

attributes #0 = { noinline nounwind optnone uwtable "correctly-rounded-divide-..."}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

整个LLVM 文件不论是 ll 文件 还是 bc 文件，在LLVM 内部都会被整体抽象为 LLVM Module。它是整个 IR 的最顶层数据结构，在其内部会划分一系列 函数(Function)/基础块（Basic Block实际是函数的作用域），以及抽象的执行指令(Instruction)。
LLVM IR的基础特性主要有三个：

1. 使用了 SSA（Static Single Assignment ），每一个值只有唯一定义它的赋值。这个特性对于生成 use-define 关系图有很大的帮助，而依赖use-def 对 常量传播 以及 消除公共表达式的分支 有巨大的优化作用。可以说 SSA 方式极大得简化了这个过程，从文件格式就定义了这个特性。
2. 三地址指令 组织代码。两个源操作数将操作的结果放在不同的目标操作数中（没有太明白这个特性的优势）。
3. 拥有无穷的寄存器，可以随意通过 % 符号标识后续的符号 是一个寄存器，比如 %1, %0，数字没有最大值的限制。

接下来看看具体的文件内容(; 是注释)：

• ModuleID,当前整个 ll 文件可以看作是一个module，ModuleID 唯一标识这个文件，直接用的是文件名。source_filename 同理。
• target datalayout ，保存的是端序，当前系统的类型大小等，不同的type 之前使用的是 -符号来分割，其各个字段表示的内容如下。
  
  datalayout 的详细解释可以参考 https://llvm.org/docs/LangRef.html#data-layout。
• target triple 表示当前所属平台的架构。x86_64-pc-linux-gnu显然 linux 86架构，如果在mac上，则显示的是arm64-apple-macosx12.0.0。
• define dso_local i32 @sum(i32 %0, i32 %1) #0 表示函数声明，基本还是遵循 C 的语法。i32 表示函数返回值为 32bits的整数类型，(i32 %0, i32 %1) 有两个 i32 类型的参数； #0定义了一堆函数属性（像是C++的 inline/noexcept 等），在后续的attributes #0 体现，比如 nounwind – 标识一个函数不会 抛异常。
• 函数内部的则为 basic block部分，主要是一些基础指令，% + 数字，就像前面说的是寄存器，临时保存变量；其他的像是 alloca 属于通用的指令，alloca为当前函数分配栈帧空间。 %3 = alloca i32, align 4 分配一个4bytes 的栈空间，且4bytes对齐，并用寄存器%3指向这个空间。

更多的语法细节 （全局变量、数组、链表 等）可以参考 官方文档 https://llvm.org/docs/LangRef.html.

LLVM IR in-memory 表示形式

前面描述了 ll 文件的详细格式 以及与其等价的其他两种表示方式，除了bc 文件之外就是 内存表示方式了。
下面提到的是重要的几种数据结构：

• Module 类。前面描述 ll 文件的时候简单说过，其是最顶层的IR 数据结构的表示方式，内存中的 Module class 则会保存所有转换单元的数据。（在 PostgreSQL 实现的jit 中，一个表达式执行单元是一个module，包含了这个表达式执行过程中所有的function/bb/instructions等）。
  这个 Module 类提供了 Module::iterator 类型 通过 begin() 和 end() 函数可以非常便捷得迭代 module对象内部所有的 functions。
• Function 类。包含了原始高级语言代码中对函数的声明或者及定义。而且 Function类中提供了isDeclaration() 这样的接口来判断代码中函数是定义还是声明。通过 getArgumentList()函数能拿到实际的函数参数 或者 arg_begin()/arg_end()能够遍历函数参数。
• BasicBlock 类则包含了一系列 LLVM 指令，同样可以通过其提供的 begin()/end() 函数来访问。
• Instruction 类，每一个instruction 对象代表了一个 LLVM IR 的原子计算单元。

这四者之间的关系，按照前面 sum.c 生成的 sum.ll 来看，如下：

BasicBlock 在函数内部会有多个，比如有分支 跳转/循环 这种执行逻辑，每一个分支都算是一个BasicBlock，它们构成了函数的控制流。PostgreSQL 的分支裁剪就是减少尽可能多的 BasicBlock（每一个BasicBlock都需要执行一批instructions，会破坏CPU的流水线）。

LLVM IR Optimization

前面已经按照 module构造好 了IR 的内存表示，接下来就是进行优化了，当然也可以直接通过 llvm 提供的 opt 工具从磁盘文件进行优化，只是因为要实现JIT 的话，肯定是调用接口，就需要调用对应的优化接口了。
再看看前面的架构图 就对 optimization 所处的位置清晰很多了：

llvm 同样提供了几种优化驱动（clang 也会做，man clang中能够看到如下信息）

• -O0 什么优化也不做，包含了最多的可调式信息。
• -O1 优化程度介于 O0-O1，具体优化了什么内容（官方没有提太多，估计就是小幅度得提升）
• -O2 更高级一些的优化层级，开启大多数优化（具体什么还不太清楚）
• -O3 和 O2 类似，不过为了性能，代码更多
• -Os 和O2类似，不过代码大小会更小
• -Oz, 和O2 以及 Os 类似，不过是更进一步得减少了代码大小
• -O4 开启了链接时优化

这一些优化驱动可以通过 opt 工具单独执行：
opt -O3 sum.bc -o sum-O3.bc
每执行一次 这个指令，可以理解为进行了一次 Pass，Pass 是IR 优化中 一轮的表示。而 mem2reg 则是 pass 过程非常重要的一部分，关于 mem2reg 的描述我没有看的特别明白：

This file promotes memory references to be register references. It promotes alloca instructions which only have loads and stores as uses. An alloca is transformed by using dominator frontiers to place phi nodes, then traversing the function in depth-first order to rewrite loads and stores as appropriate. This is just the standard SSA construction algorithm to construct “pruned” SSA form.

感觉还是得看 R大 的文章：https://www.zhihu.com/question/41999500/answer/93243408，还是需要花费更多的精力来研究，总之mem2reg 是IR优化过程中至关重要的一部分