简介：作者：长别
1. 前言
随着 IT 基础设施的倒退，古代的数据处理系统须要解决更多的数据、反对更为简单的算法。数据量的增长和算法的复杂化，为数据分析系统带来了严厉的性能挑战。近年来，咱们能够在数据库、大数据系统和 AI 平台等畛域看到很多性能优化的技术，技术涵盖体系结构、编译技术和高性能计算等畛域。作为编译优化技术的代表，本文次要介绍基于 LLVM 的代码生成技术（简称 Codeden）。
LLVM 是一款十分风行的开源编译器框架，反对多种语言和底层硬件。开发者能够基于 LLVM 搭建本人的编译框架并进行二次开发，将不同的语言或者逻辑编译成运行在多种硬件上的可执行文件。对于 Codegen 技术来说，咱们次要关注 LLVM IR 的格局以及生成 LLVM IR 的 API。在本文的如下局部，咱们首先对 LLVM IR 进行介绍，而后介绍 Codegen 技术的原理和应用场景，最初咱们介绍在阿里云自研的云原生数据仓库产品 AnalyticDB PostgreSQL 中，Codegen 的典型利用场景。
2. LLVM IR 简介及上手教程
在编译器实践与实际中，IR 是十分重要的一环。IR 的全称叫做 Intermediate Representation，翻译过去叫“两头示意”。对于一个编译器来说，从下层形象的高级语言到底层的汇编语言，要经验很多个环节(pass)，经验不同的表现形式。而编译优化技术有很多种，每种技术作用的编译环节不同。然而 IR 是一个显著的分水岭。IR 以上的编译优化，不须要关怀底层硬件的细节，比方硬件的指令集、寄存器文件大小等。IR 以下的编译优化，须要和硬件打交道。LLVM 最为驰名是它的 IR 的设计。得益于奇妙地 IR 设计，LLVM 向上能够反对不同的语言，向下能够反对不同的硬件，而且不同的语言能够复用 IR 层的优化算法。
上图展现了 LLVM 的一个框架图。LLVM 把整个编译过程分为三步：（1）前端，把高级语言转换为 IR。(2）中端，在 IR 层做优化。(3) 后端，把 IR 转化为对应的硬件平台的汇编语言。因而 LLVM 的扩展性很好。比方你要实现一个名为 toyc 的语言、心愿运行在 ARM 平台上，你只须要实现一个 toyc->LLVM IR 的前端，其余局部调 LLVM 的模块就能够了。或者你要搞一个新的硬件平台，那么只须要搞定 LLVM IR-> 新硬件这一阶段，而后该硬件就能够反对很多种现存的语言。因而，IR 是 LLVM 最有竞争力的中央，同时也是学习应用 LLVM Codegen 的最外围的中央。
2.1 LLVM IR 基本知识
LLVM 的 IR 格局十分像汇编，对于学习过汇编语言的同学来说，学会应用 LLVM IR 进行编程非常容易。对于没学过汇编语言的同学，也不必放心，汇编其实并不难。汇编难的不是学会，而是工程实现。因为汇编语言的开发难度，会随着工程复杂度的晋升呈指数级回升。接下来咱们须要理解 IR 中最重要的三局部，指令格局、Basic Block & CFG，还有 SSA。残缺的 LLVM IR 信息请参考 https://llvm.org/docs/LangRef.html。
指令格局 。LLVM IR 提供了一种相似于汇编语言的三地址码式的指令格局。上面的代码片段是一个非常简单的用 LLVM IR 实现的函数，该函数的输出是 5 个 i32 类型(int32) 的整数，函数的性能是计算这 5 个数的和并返回。LLVM IR 是反对一些根本的数据类型的，比方 i8、i32、浮点数等。LLVM IR 中得变量的命名是以 “%” 结尾，默认 %0 是函数的第一个参数、%1 是第二个参数，顺次类推。机器生成的变量个别是以数字进行命名，如果是手写的话，能够依据本人的爱好抉择适合的命名办法。LLVM IR 的指令格局包含操作符、类型、输出、返回值。例如 “%6 = add i32 %0, %1″ 的操作符号是 ”add”、类型是 ”i32″、输出是 ”%0″ 和“%1”、返回值是 ”%6″。总的来说，IR 反对一些根本的指令，而后编译器通过这些根本指令的来实现一些简单的运算。例如，咱们在 C 中写一个形如“A * B + C”的表达式在 LLVM IR 中是通过一条乘法和一条加法指令来实现的，另外可能也包含一些类型转换指令。
define i32 @ir_add(i32, i32, i32, i32, i32){
%6 = add i32 %0, %1
%7 = add i32 %6, %2
%8 = add i32 %7, %3
%9 = add i32 %8, %4
ret i32 %9
}Basic Block & CFG。理解了 IR 的指令格局当前，接下来咱们须要理解两个概念：Basic Block(基本块，简称 BB)和 Control Flow Graph(控制流图，CFG)。下图 (左) 展现了一个简略的 C 语言函数，下图（中）是应用 clang 编译进去的对应的 LLVM IR，下图（右）是应用 graphviz 画进去的 CFG。联合这张图，咱们解释下 Basic Block 和 CFG 的概念。
在咱们平时接触到的高级语言中，每种语言都会有很多分支跳转语句，比方 C 语言中有 for, while, if 等关键字，这些关键字都代表着分支跳转。开发者通过分支跳转来实现不同的逻辑运算。汇编语言通常通过有条件跳转和无条件跳转两种跳转指令来实现逻辑运算，LLVM IR 同理。比方在 LLVM IR 中 ”br label %7″ 意味着无论如何都跳转到名为 %7 的 label 那里，这是一条无条件跳转指令。”br i1 %10, label %11, label %22″ 是有条件跳转，意味着这如果 %10 是 true 则跳转到名为 %11 的 label，否则跳转到名为 %22 的 label。
在理解了跳转指令这个概念后，咱们介绍 Basic Block 的概念。一个 Basic Block 是指一段串行执行的指令流，除了最初一句之外不会有跳转指令，Basic Block 入口的第一条指令叫做“Leading instruction”。除了第一个 Basic Block 之外，每个 Basic Block 都会有一个名字(label)。第一个 Basic Block 也能够有，只是有时候没必要。例如在这段代码当中一共有 5 个 Basic Block。Basic Block 的概念，解决了管制逻辑的问题。通过 Basic Block, 咱们能够把代码划分成不同的代码块，在编译优化中，有的优化是针对单个 Basic Block 的，有些是针对多个 Basic Block 的。
CFG(Control Flow Graph，控制流图)其实就是由 Basic Block 以及 Basic Block 之间的跳转关系组成的一个图。例如上图所示的代码，一共有 5 个 Basic Block，箭头列出了 Basic Block 之间的跳转关系，独特组成了一个 CFG。如果一个 Basic Block 只有一个箭头指向别的 Block，那么这个跳转就是无条件跳转，否则是有条件跳转。CFG 是编译实践中一个比较简单而且很根底的概念，CFG 更进一步是 DFG（Data Flow Graph，数据流图），很多进阶的编译优化算法都是基于 DFG 的。对于应用 LLVM 进行 Codegen 开发的同学，了解 CFG 的概念即可。
SSA。SSA 的全称是 Static Single Assignment（动态单赋值），这是编译技术中十分根底的一个理念。SSA 是学习 LLVM IR 必须相熟的概念，同时也是最难了解的一个概念。仔细的读者在察看下面列出的 IR 代码时会发现，每个“变量”只会被赋值一次，这就是 SSA 的核心思想。因为从编译器的角度来看，编译器不关怀“变量”，编译器是以“数据”为核心进行设计的。每个“变量”的每次写入，都生成了一个新的数据版本，编译器的优化是围绕数据版本开展的。接下来咱们用如下的 C 语言代码来解释这一思维。
上图（左）展现了一段简略的 C 代码，上图（右）是这短代码的 SSA 版本，也就是“编译器眼中的代码”。在 C 语言中，咱们晓得数据都是用变量来存储的，因而数据操作的外围是变量，开发者须要关怀变量的生存工夫、何时被赋值、何时被应用。然而编译器只关怀数据的流向，因而每次赋值操作都会生成一个新的左值。例如右边代码只有一个 a, 然而在左边的代码有 4 个变量，因为 a 外面的数据一共有 4 个版本。除了每次赋值操作会生成一个新的变量，最初的一个 phi 节点会生成一个新的变量。在 SSA 中，每个变量都代表数据的一个版本。也就是说，高级语言以变量为外围，而 SSA 格局以数据为外围。SSA 中每次赋值操作都会生成一个版本的数据，因而在写 IR 的时候，时刻牢记 IR 的变量和高层语言不同，一个 IR 的变量代表数据的一个版本。Phi 节点是 SSA 中的一个重要概念。在这个例子当中，a\_4 的取值取决于之前执行了哪个分支，如果执行了第一个分支，那么 a\_4 = a\_1, 顺次类推。Phi 节点通过判断这段代码是从哪个 Basic Block 跳转而来，抉择适合的数据版本。LLVM IR 天然也是须要开发者写 Phi 节点的，在循环、条件分支跳转的中央，往往须要手写很多 phi 节点，这是写 LLVM IR 时逻辑上比拟难解决的中央。
2.2 学会应用 LLVM IR 写程序
相熟 LLVM IR 最好的方法就是应用 IR 写几个程序。在开始写之前，倡议先花 30 分钟 - 1 个小时再粗略浏览下官网手册（https://llvm.org/docs/LangRef.html），相熟下都有哪些指令的类型。接下来咱们通过两个简略的 case 相熟下 LLVM IR 编程的全副流程。
上面是一个循环加法的函数片段。这个函数一共蕴含三个 Basic Block，loop、loop\_body 和 final。其中 loop 是整个函数的开始，loop\_body 是函数的循环体，final 是函数的结尾。在第 5 行和第 6 行，咱们应用 phi 节点来实现后果和循环变量。
define i32 @ir_loopadd_phi(i32*, i32){
br label %loop
loop:
%i = phi i32 [0,%2], [%newi,%loop_body]
%res = phi i32[0,%2], [%new_res, %loop_body]
%break_flag = icmp sge i32 %i, %1
br i1 %break_flag, label %final, label %loop_body
loop_body:
%addr = getelementptr inbounds i32, i32* %0, i32 %i
%val = load i32, i32* %addr, align 4
%new_res = add i32 %res, %val
%newi = add i32 %i, 1
br label %loop
final:
ret i32 %res;
}上面是一个数组冒泡排序的函数片段。这个函数蕴含两个循环体。LLVM IR 实现循环自身就比较复杂，两个循环嵌套会更加简单。如果可能用 LLVM IR 实现一个冒泡算法，基本上就了解了 LLVM 的整个逻辑了。
define void @ir_bubble(i32*, i32) {
%r_flag_addr = alloca i32, align 4
%j = alloca i32, align 4
%r_flag_ini = add i32 %1, -1
store i32 %r_flag_ini, i32* %r_flag_addr, align 4
br label %out_loop_head
out_loop_head:
;check break
store i32 0, i32* %j, align 4
%tmp_r_flag = load i32, i32* %r_flag_addr, align 4
%out_break_flag = icmp sle i32 %tmp_r_flag, 0
br i1 %out_break_flag, label %final, label %in_loop_head
in_loop_head:
;check break
%tmpj_1 = load i32, i32* %j, align 4
%in_break_flag = icmp sge i32 %tmpj_1, %tmp_r_flag
br i1 %in_break_flag, label %out_loop_tail, label %in_loop_body
in_loop_body:
;read & swap
%tmpj_left = load i32, i32* %j, align 4
%tmpj_right = add i32 %tmpj_left, 1
%left_addr = getelementptr inbounds i32, i32* %0, i32 %tmpj_left
%right_addr = getelementptr inbounds i32, i32* %0, i32 %tmpj_right
%left_val = load i32, i32* %left_addr, align 4
%right_val = load i32, i32* %right_addr, align 4
;swap check
%swap_flag = icmp sge i32 %left_val, %right_val
%left_res = select i1 %swap_flag, i32 %right_val, i32 %left_val
%right_res = select i1 %swap_flag, i32 %left_val, i32 %right_val
store i32 %left_res, i32* %left_addr, align 4
store i32 %right_res, i32* %right_addr, align 4
br label %in_loop_end
in_loop_end:
;update j
%tmpj_2 = load i32, i32* %j, align 4
%newj = add i32 %tmpj_2, 1
store i32 %newj, i32* %j, align 4
br label %in_loop_head
out_loop_tail:
;update r_flag
%tmp_r_flag_1 = load i32, i32* %r_flag_addr, align 4
%new_r_flag = sub i32 %tmp_r_flag_1, 1
store i32 %new_r_flag, i32* %r_flag_addr, align 4
br label %out_loop_head
final:
ret void
}咱们把如上的 LLVM IR 用 clang 编译器编译成 object 文件，而后和 C 语言写的程序链接到一起，即可失常调用。在下面提到的 case 中，咱们只应用了 i32、i64 等根本数据类型，LLVM IR 中反对 struct 等高级数据类型，能够实现更为简单的性能。
2.3 应用 LLVM API 实现 Codegen
编译器实质上就是调用各种各样的 API，依据输出去生成对应的代码，LLVM Codegen 也不例外。在 LLVM 外部，一个函数是一个 class，一个 Basic Block 试一个 class, 一条指令、一个变量都是一个 class。用 LLVM API 实现 codegen 就是依据需要，用 LLVM 外部的数据结构去实现相应的 IR。
Value *constant = Builder.getInt32(16);
Value *Arg1 = fooFunc->arg_begin();
Value *val = createArith(Builder, Arg1, constant);
Value *val2 = Builder.getInt32(100);
Value *Compare = Builder.CreateICmpULT(val, val2, "cmptmp");
Value *Condition = Builder.CreateICmpNE(Compare, Builder.getInt1(0), "ifcond");
ValList VL;
VL.push_back(Condition);
VL.push_back(Arg1);
BasicBlock *ThenBB = createBB(fooFunc, "then");
BasicBlock *ElseBB = createBB(fooFunc, "else");
BasicBlock *MergeBB = createBB(fooFunc, "ifcont");
BBList List;
List.push_back(ThenBB);
List.push_back(ElseBB);
List.push_back(MergeBB);
Value *v = createIfElse(Builder, List, VL);如上是一个用 LLVM API 实现 codegen 的例子。其实这就是个用 C ++ 写 IR 的过程，如果晓得如何写 IR 的话，只须要相熟下这套 API 就能够了。这套 API 提供了一些根本的数据结构，比方指令、函数、基本块、llvm builder 等，而后咱们只须要调用相应的函数去生成这些对象即可。一般来说，首先咱们学生成函数的原型，包含函数名字、参数列表、返回类型等。而后咱们在依据函数的性能，确定都须要有哪些 Basic Block 以及 Basic Block 之间的跳转关系，而后生成相应的 Basic。最初咱们再依照肯定的程序去给每个 Basic Block 填充指令。逻辑是，这个流程和用 LLVM IR 写代码是相仿的。
3. Codegen 技术剖析
如果咱们用上文所形容的办法，生成一些简略的函数，并且用 C 写出对应的版本进行性能比照，咱们就会发现，LLVM IR 的性能并不会比 C 快。一方面，计算机底层执行的是汇编，C 语言自身和汇编是十分靠近的，理解底层的程序员往往可能从 C 代码中揣测出大略会生成什么样的汇编。另一方面，古代编译器往往做了很多优化，一些大大加重了程序员的优化累赘。因而，应用 LLVM IR 进行 Codegen 并不会取得比手写 C 更好的性能，而且应用 LLVM Codegen 有一些显著的毛病。想要真正用好 LLVM，咱们还须要相熟 LLVM 的特点。
3.1 毛病剖析
毛病 1：开发难。理论开发中简直不会有工程应用汇编作为次要开发语言，因为开发难度太大了，有趣味的小伙伴能够试着写个快排感受一下。即便是数据库、操作系统这样的根底软件，往往也只是在多数的中央会用到汇编。应用 LLVM IR 开发会有相似的问题。比方上文展现的最简单例子是冒泡算法。开发者用 C 写个冒泡只须要几分钟，然而用 LLVM IR 写个冒泡可能要一个小时。另外，LLVM IR 很难解决简单的数据结构，比方构造体、类。除了 LLVM IR 中的那些根本数据结构外，新增一个简单的数据结构十分难。因而在理论的开发当中，采纳 Codegen 会导致开发难度指数级回升。
毛病 2：调试难。开发者通常通过单步跟踪的形式去调试代码，然而 LLVM IR 是不反对的。一旦代码出问题，只能是人肉一遍一遍看 LLVM IR。如果懂汇编的话，能够通过单步跟踪生成的汇编进行调试，然而汇编语言和 IR 之间并不是简略的映射关系，因而只能肯定水平上升高调试难度，并不齐全解决调试的问题。
毛病 3: 运行老本。生成 LLVM IR 往往很快，然而生成的 IR 须要调用 LLVM 中的工具进行优化、以及编译成二进制文件，这个过程是须要工夫的（请联想一下 GCC 编译的速度）。在数据库的开发过程中，咱们的经验值是每个函数大概须要 10ms-100ms 的 codegen 老本。大部分的工夫花在了优化 IR 和 IR 到汇编这两步。
3.2 实用场景
理解了 LLVM Codegen 的毛病，咱们能力去剖析其长处、抉择适合场景。上面这部分是团队在开发过程中总结的适宜应用 LLVM Codegen 的场景。
场景 1：Java/python 等语言。上文中提到过 LLVM IR 并不会比 C 快，然而会比 Java/python 等语言快啊。例如在 Java 中，有时候为了晋升性能，会通过 JNI 调用一些 C 的函数晋升性能。同理，Java 也能够调用 LLVM IR 生成的函数晋升性能。
场景 2：硬件和语言不兼容。LLVM 反对多种后端，比方 X86、ARM 和 GPU。对于一些硬件与语言不兼容的场景，能够利用 LLVM 实现兼容。例如如果咱们的零碎是用 Java 语言开发、想要调用 GPU，能够思考用 LLVM IR 生成 GPU 代码，而后通过 JNI 的办法进行调用。这套计划不仅反对 NVIDIA 的 GPU，也反对 AMD 的 GPU，而且对应生成的 IR 也能够在 CPU 上执行。
场景 3：逻辑简化。以数据库为例，数据库执行引擎在执行过程中须要做大量的数据类型、算法逻辑相干的判断。这次要是因为 SQL 中的数据类型和逻辑，很多是在数据库开发时无奈确定的，只能在运行时决定。这一部分过程，也被称为“解释执行”。咱们能够利用 LLVM 在运行时生成代码，因为这个时候数据类型和逻辑曾经确定，咱们能够在 LLVM IR 中删除那些不必要的判断操作，从而实现性能的晋升。
4. LLVM 在数据库中的利用
在数据库当中，团队是用 LLVM 来进行表达式的解决，接下来咱们以 PostgreSQL 数据库和云原生数据仓库 AnalyticDB PostgreSQL 为比照，解释 LLVM 的利用办法。
PostgreSQL 为了实现表达式的解释执行，采纳了一套“拼函数”的计划。PostgreSQL 中实现了大量 C 函数，比方加减法、大小比拟等，不同类型的都有。SQL 在生成执行打算阶段会依据表达式符号的类型和数据类型抉择相应的函数、把指针存下来，等执行的时候再调用。因而对于 “a > 10 and b < 5″ 这样的过滤条件，假如 a 和 b 都是 int32，PostgreSQL 实际上调用了“Int8AndOp(Int32GT(a, 10), Int32LT(b, 5))”这样一个函数组合，就像搭积木一样。这样的计划有两个显著的性能问题。一方面这种计划会带来比拟多次数的函数调用，函数调用自身是有老本的。另一方面，这种计划必须要实现一个对立的函数接口，函数外部和内部都须要做一些类型转换，这也是额定的性能开销。Odyssey 应用 LLVM 进行 codegen，能够实现最小化的代码。因为在 SQL 下发当前，数据库是晓得表达式的符号和输出数据的类型的，因而只须要依据需要选取相应的 IR 指令就能够了。因而只须要三条 IR 指令，就能够实现这个表达式，而后咱们把表达式封装成一个函数，就能够在执行的时候调用了。这次操作，把屡次函数调用简化成了一次函数调用，大大减少了指令的总数量。
// 样例 SQL
select count(*) from table where a > 10 and b < 5;
// PostgreSQL 解释执行计划：屡次函数调用
result = Int8AndOp(Int32GT(a, 10), Int32LT(b, 5));
// AnalyticDB PostgreSQL 计划：应用 LLVM codegen 生成最小化底层代码
%res1 = icmp ugt i32 %a, 10;
%res2 = icmp ult i32 %b, 5;
%res = and i8 %res1, %res2;在数据库中，表达式次要呈现在几个场景。一类是过滤条件，通常呈现在 where 条件中。一类是输入列表，个别跟在 select 之后。有些算子，比方 join、agg 等，它的判断条件中也可能会呈现一些比较复杂的表达式。因而表达式的解决是会呈现在数据库执行引擎的各个模块的。在 AnalyticDB PostgreSQL 版中，开发团队形象出了一个表达式解决框架，通过 LLVM Codegen 来解决这些表达式，从而进步了执行引擎的整体性能。
5. 总结
LLVM 作为一个风行的开源编译框架，近年来被用于数据库、AI 等零碎的性能减速。因为编译器实践自身门槛较高，因而 LLVM 的学习有肯定的难度。而且从工程上，还须要对 LLVM 的工程特点和性能特色有比拟精确的了解，能力找到适合的减速场景。阿里云数据库团队的云原生数据仓库产品 AnalyticDB PostgreSQL 版基于 LLVM 实现了一套运行时的表达式解决框架，可能无效地进步零碎在进行简单数据分析时地性能。
【对于咱们】
阿里云数据库事业部 OLAP 平台团队，专一于提供寰球当先的全栈式大规模 OLAP 数据库产品，包含剖析型数据库 AnalyticDB、数据湖剖析 Data Lake Analytics 等，产品服务于阿里巴巴私有云、专有云的泛滥客户要害业务，同时服务于阿里巴巴团体外部泛滥数据分析类业务。
【岗位职责】
1. 对数据库接入性能、产品稳定性、产品技术等云原生技术进行优化和开发。
2. 数据库 SQL 引擎研发，SQL 优化器开发，SQL 执行外围算法的优化及 Code Generation 框架开发。
3. 数据库前沿技术的调研剖析与落地，包含分布式计算架构、智能诊断与剖析，HTAP 数据库架构等。
4. 工作地能够蕴含北京，杭州，深圳。
【岗位要求】
1. 相熟 linux 平台下的 C /C++ 或者 Java 编程，相熟过程间通信，内存治理，网。
2. 善于高性能服务端编程，精通分布式计算和支流大数据系统架构，相熟 raft 或 paxos 等分布式一致性协定算法。
3. 有 PostgreSQL/MySQL/Impala/Presto/Greenplum 等数据库内核开发教训者优先，有数据库 SQL 引擎、存储、事务等内核开发教训者优先。
4. 在 VLDB，SIGMOD, ICDE 等数据库顶级会议发表过论文者优先。
5. 良好的沟通和团队合作能力，可能纯熟编写各类技术文档。
版权申明：本文内容由阿里云实名注册用户自发奉献，版权归原作者所有，阿里云开发者社区不领有其著作权，亦不承当相应法律责任。具体规定请查看《阿里云开发者社区用户服务协定》和《阿里云开发者社区知识产权爱护指引》。如果您发现本社区中有涉嫌剽窃的内容，填写侵权投诉表单进行举报，一经查实，本社区将立即删除涉嫌侵权内容。