简介：作者：长别

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 %looploop:  %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 %loopfinal:  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_headout_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_headout_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_headfinal:  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指令，就能够实现这个表达式，而后咱们把表达式封装成一个函数，就能够在执行的时候调用了。这次操作，把屡次函数调用简化成了一次函数调用，大大减少了指令的总数量。

// 样例SQLselect 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. 良好的沟通和团队合作能力，可能纯熟编写各类技术文档。

版权申明：本文内容由阿里云实名注册用户自发奉献，版权归原作者所有，阿里云开发者社区不领有其著作权，亦不承当相应法律责任。具体规定请查看《阿里云开发者社区用户服务协定》和《阿里云开发者社区知识产权爱护指引》。如果您发现本社区中有涉嫌剽窃的内容，填写侵权投诉表单进行举报，一经查实，本社区将立即删除涉嫌侵权内容。