1.前言随着IT基础设施的发展，现代数据处理系统需要处理更多的数据，支持更复杂的算法。数据量的增长和算法的复杂性给数据分析系统带来了严峻的性能挑战。近年来，我们在数据库、大数据系统、AI平台等领域看到了很多性能优化技术，涵盖架构、编译技术、高性能计算等领域。作为编译优化技术的代表，本文主要介绍基于LLVM的代码生成技术（简称Codeden）。LLVM是一个非常流行的开源编译器框架，支持多种语言和底层硬件。开发者可以基于LLVM构建自己的编译框架并进行二次开发，将不同的语言或逻辑编译成运行在各种硬件上的可执行文件。对于Codegen技术，我们主要关注LLVMIR的格式和生成LLVMIR的API。本文后续部分首先介绍LLVMIR，然后介绍Codegen技术的原理和应用场景，最后介绍Codegen在阿里云自研的云原生数仓产品AnalyticDBPostgreSQL中的典型应用场景。2.LLVMIR介绍及上手教程在编译器理论和实践中，IR是一个非常重要的部分。IR的全称叫做IntermediateRepresentation，译为“中间表示”。对于一个编译器来说，从上层的抽象高级语言到下层的汇编语言，要经过很多环节（pass），经历不同的表现形式。编译优化技术有很多种，每种技术都有不同的编译环节。但IR是一个明显的分水岭。IR以上的编译优化不需要关心底层硬件的细节，比如硬件指令集、寄存器文件大小等，IR以下的编译优化需要和硬件打交道。LLVM最著名的是它的IR设计。得益于巧妙的IR设计，LLVM可以向上支持不同的语言，向下支持不同的硬件，不同的语言可以复用IR层的优化算法。上图是LLVM的一个框架图。LLVM将整个编译过程分为三个步骤：（1）前端将高级语言转换成IR。(2)在中端，在IR层进行优化。(3)后端将IR转换成对应硬件平台的汇编语言。所以LLVM可以很好地扩展。比如你要实现一个叫toyc的语言，希望在ARM平台上运行，只需要实现一个toyc->LLVMIR的前端，其他部分调整LLVM模块即可。或者你想创建一个新的硬件平台，只需要拿到LLVMIR->newhardware这个阶段，然后这个硬件就可以支持很多现有的语言了。所以IR是LLVM最有竞争力的地方，也是学习使用LLVMCodegen的核心地方。2.1LLVMIR基础知识LLVM的IR格式与汇编非常相似。对于学习过汇编语言的同学来说，学习使用LLVMIR进行编程是非常容易的。对于没学过汇编语言的同学，不用担心，汇编其实并不难。编译不难学，难的是实现工程。因为汇编语言的开发难度会随着工程复杂度的增加呈指数增长。接下来我们需要了解IR最重要的三个部分，instructionformat，BasicBlock&CFG，SSA。请参阅https://llvm.org/docs/LangRef.html以获取完整的LLVMIR信息。指令格式。LLVMIR提供了类似于汇编语言的三地址类代码指令格式。以下代码片段是在LLVMIR中实现的一个非常简单的函数。这个函数的输入是5个i32类型的整数（int32）。函数的作用是计算这5个数的和并返回。LLVMIR支持一些基本数据类型，如i8、i32、浮点数等。LLVMIR中的变量名以“%”开头。默认情况下，%0是函数的第一个参数，%1是第二个参数，依此类推。机器产生的变量一般用数字命名。如果是手写的，可以根据自己的喜好选择合适的命名方式。LLVMIR的指令格式包括运算符、类型、输入和返回值。例如“%6=addi32%0,%1”的运算符号为“add”，类型为“i32”，输入为“%0”和“%1”，返回值为“%6”。一般来说，IR支持一些基本指令，然后编译器使用这些基本指令来完成一些复杂的操作。比如我们在LLVMIR中通过一条乘法和一条加法指令在C中写出一个形式为“A*B+C”的表达式，还可能包含一些类型转换指令。定义i32@ir_add(i32,i32,i32,i32,i32){%6=添加i32%0,%1%7=添加i32%6,%2%8=添加i32%7,%3%9=添加i32%8,%4reti32%9}基本块和CFG。了解了IR的指令格式之后，我们需要了解两个概念：BasicBlock（基本块，简称BB）和ControlFlowGraph（控制流图，CFG）。下图（左）是一个简单的C语言函数，下图（中）是对应的使用clang编译的LLVMIR，下图（右）是使用graphviz绘制的CFG。结合这张图，我们来解释一下BasicBlock和CFG的概念。在我们平时接触的高级语言中，每种语言都会有很多分支跳转语句。比如在C语言中，有for、while、if等关键字，这些关键字都代表分支跳转。开发者通过分支和跳转实现不同的逻辑操作。汇编语言通常通过条件跳转和无条件跳转两种跳转指令来实现逻辑运算，LLVMIR也是如此。例如LLVMIR中的“brlabel%7”表示无论如何都要跳转到名为%7的标签，这是一条无条件跳转指令。"bri1%10,label%11,label%22"是条件跳转，意思是如果%10为真，则跳转到名为%11的标签，否则跳转到名为%22的标签。了解了跳转指令的概念后，我们引入BasicBlock的概念。BasicBlock是指一个串行执行的指令流，除了最后一句，不会有跳转指令。基本块入口处的第一条指令称为“前导指令”。除了第一个BasicBlock，每个BasicBlock都会有一个名字（label）。第一个基本块也可用，但有时不是必需的。例如，这段代码中有5个BasicBlock。BasicBlock的概念解决了控制逻辑的问题。通过BasicBlock，我们可以把代码分成不同的代码块。在编译优化中，有的优化是针对单个BasicBlock，有的是针对多个BasicBlock。CFG（ControlFlowGraph，控制流图）实际上是由BasicBlock组成的图以及BasicBlock之间的跳转关系。比如上图所示的代码，一共有5个BasicBlock，箭头列出了BasicBlock之间的跳转关系，它们共同构成了一个CFG。如果一个BasicBlock只有一个箭头指向另一个Block，则该跳转为无条件跳转，否则为有条件跳转。CFG是编译理论中一个比较简单和基础的概念。CFG进一步发展为DFG（数据流图）。许多高级编译优化算法都是基于DFG的。对于使用LLVM进行Codegen开发的同学，理解CFG的概念即可。SSA。SSA的全称是StaticSingleAssignment（静态单一赋值），这是编译技术中一个非常基础的概念。SSA是学习LLVMIR必须熟悉的概念，也是最难理解的概念。细心的读者会发现，观察上面列出的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节点通过判断这段代码从哪个BasicBlock跳转来选择合适的数据版本。LLVMIR自然需要开发者编写Phi节点。在循环和条件分支跳转的地方，往往需要手写很多phi节点。这是编写LLVMIR时逻辑上难以处理的地方。2.2学习使用LLVMIR编写程序熟悉LLVMIR的最佳方法是使用IR编写一些程序。在开始写之前，建议先花30分钟到1小时，然后粗读一下官方手册（https://llvm.org/docs/LangRef.html），熟悉一下指令的种类。接下来，我们将通过两个简单的案例来熟悉LLVMIR编程的整个过程。下面是循环加法的函数片段。这个函数一共包含三个BasicBlocks，loop、loop_body和final。其中loop是整个函数的开始，loop_body是函数的循环体，final是函数的结束。在第5行和第6行，我们使用phi节点来实现结果和循环变量。definei32@ir_loopadd_phi(i32*,i32){brlabel%looploop:%i=phii32[0,%2],[%newi,%loop_body]%res=phii32[0,%2],[%new_res,%loop_body]%break_flag=icmpsgei32%i,%1bri1%break_flag,label%final,label%loop_bodyloop_body:%addr=getelementptrinboundsi32,i32*%0,i32%i%val=loadi32,i32*%addr,align4%new_res=addi32%res,%val%newi=addi32%i,1brlabel%loopfinal:reti32%res;}下面是数组冒泡排序的函数片段。该函数包含两个循环体。循环本身的LLVMIR实现比较复杂，两个循环的嵌套会比较复杂。如果你能用LLVMIR实现一个冒泡算法，你就基本理解了LLVM的整个逻辑。definevoid@ir_bubble(i32*,i32){%r_flag_addr=allocai32,align4%j=allocai32,align4%r_flag_ini=addi32%1,-1storei32%r_flag_ini,i32*%r_flag_addr,align4brlabel%out_loop_headout_loop_head:;checkbreakstorei320,i32*%j,align4%tmp_r_flag=loadi32,i32*%r_flag_addr,align4%out_break_flag=icmpslei32%tmp_r_flag,0bri1%out_break_flag,label%final,label%in_loop_headin_loop_head:;checkbreak%tmpj_1=loadi32,i32*%j,align4%in_break_flag=icmpsgei32%tmpj_1,%tmp_r_flagbri1%in_break_flag,label%out_loop_tail,label%in_loop_bodyin_loop_body:;读取&swap%tmpj_left=loadi32,i32*%j,align4%tmpj_right=addi32%tmpj_left,1%left_addr=getelementptrinboundsi32,i32*%0,i32%tmpj_left%right_addr=getelementptrinboundsi32,i32*%0,i32%tmpj_right%left_val=loadi32,i32*%left_addr,align4%right_val=loadi32,i32*%right_addr,align4;swapcheck%swap_flag=icmpsgei32%left_val,%right_val%left_res=selecti1%swap_flag,i32%right_val,i32%left_val%right_res=selecti1%swap_flag,i32%left_val,i32%right_valstorei32%left_res,i32*%left_addr,align4storei32%right_res,i32*%right_addr,align4brlabel%in_loop_endin_loop_end:;updatej%tmpj_2=loadi32,i32*%j,align4%newj=addi32%tmpj_2,1storei32%newj,i32*%j,align4brlabel%in_loop_headout_loop_tail:;updater_flag%tmp_r_flag_1=loadi32,i32*%r_flag_addr,align4%new_r_flag=subi32%tmp_r_flag_1,1storei32%new_r_flag,i32*%r_flag_addr,align4brlabel%out_loop_headfinal我们用retvoidLL之类的编译器编译成retvoidVM，然后用C语言写的程序链接起来，然后正常调用。在上面提到的案例中，我们只使用了i32和i64等基本数据类型。LLVMIR支持struct等高级数据类型，可以实现更复杂的功能。2.3使用LLVMAPI实现Codegen编译器本质上是根据输入调用各种AP??I生成相应的代码，LLVMCodegen也不例外。在LLVM内部，一个函数是一个类，一个基本块是一个类，一条指令和一个变量是一个类。用LLVMAPI实现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");ValListVL;VL.push_back(条件);VL.push_back(Arg1);BasicBlock*ThenBB=createBB(fooFunc,"then");BasicBlock*ElseBB=createBB(fooFunc,"else");BasicBlock*MergeBB=createBB(fooFunc,"ifcont");BBListList;List.push_back(ThenBB);List.push_back(ElseBB);List.push_back(MergeBB);Value*v=createIfElse(Builder,List,VL);上面是一个用LLVMAPI实现codegen的例子。其实这是一个用C++写IR的过程。如果你会写IR，你只需要熟悉这个API就可以了。这套API提供了一些基本的数据结构，比如指令、函数、基本块、llvmbuilder等，然后我们只需要调用相应的函数就可以生成这些对象。一般来说，首先我们生成函数的原型，包括函数名、参数列表、返回类型等，然后我们根据函数的功能确定需要哪些BasicBlocks以及BasicBlocks之间的跳转关系，然后生成相应的Basic。最后，我们按照一定的顺序为每个BasicBlock填写说明。逻辑是这个流程类似于在LLVMIR中编写代码。3.Codegen技术分析如果我们用上面描述的方法生成一些简单的函数，用C写对应的版本进行性能对比，我们会发现LLVMIR的性能并不比C快。一方面，计算机底层执行的是汇编，C语言本身就非常接近汇编。了解底层的程序员往往能从C代码中猜出会生成什么样的汇编。另一方面，现代编译器往往会做很多优化，其中一些优化大大减轻了程序员的优化负担。因此，将LLVMIR用于Codegen不会比手写C获得更好的性能，并且使用LLVMCodegen有一些明显的缺点。要想真正用好LLVM，我们还需要熟悉LLVM的特性。3.1劣势分析劣势一：开发难度大。在实际开发中，几乎没有项目使用汇编作为主要开发语言，因为开发难度太大，有兴趣的朋友可以尝试写个快排感受一下。即使是数据库、操作系统等基础软件，也往往只在少数几个地方使用汇编。使用LLVMIR进行开发也有类似的问题。例如，上面显示的最复杂的示例是气泡算法。开发人员用C写一个bubble只需要几分钟，但用LLVMIR写一个bubble可能需要一个小时。此外，LLVMIR很难处理复杂的数据结构，例如结构和类。在LLVMIR中，除了那些基本的数据结构之外，很难再添加一个复杂的数据结构。因此，在实际开发中，使用Codegen会导致开发难度呈指数级增长。缺点二：调试困难。开发人员通常通过单步调试代码，但LLVMIR不支持它。一旦代码出现问题，就只能是人肉翻来覆去翻看LLVMIR。如果懂汇编的话，可以单步调试生成的汇编，但是汇编语言和IR之间并没有简单的映射关系，所以只能在一定程度上降低调试的难度，并不能彻底解决问题的调试。劣势三：运营成本。生成LLVMIR往往很快，但是生成的IR需要调用LLVM中的工具进行优化，编译成二进制文件。这个过程需要时间（请想想GCC编译的速度）。在数据库的开发过程中，我们的经验值是每个函数大约需要10ms-100ms的codegen成本。大部分时间花在优化IR和IR到装配步骤上。3.2适用场景在了解了LLVMCodegen的不足之后，我们可以分析其优势，选择合适的场景。以下部分是团队在开发过程中总结的适合使用LLVMCodegen的场景。场景一：Java/python等语言。上面说了，LLVMIR不会比C快，但是会比Java/python等语言快。比如在Java中，有时候为了提高性能，会通过JNI调用一些C函数来提高性能。同样，Java也可以调用LLVMIR生成的函数来提高性能。场景2：硬件和语言不兼容。LLVM支持X86、ARM、GPU等多种后端。对于一些硬件和语言不兼容的场景，可以使用LLVM来实现兼容。比如我们的系统是用Java语言开发的，要调用GPU，可以考虑使用LLVMIR生成GPU代码，然后通过JNI方式调用。该方案不仅支持NVIDIA的GPU，也支持AMD的GPU，相应生成的IR也可以在CPU上执行。场景3：逻辑简化。以数据库为例，数据库执行引擎在执行过程中需要做大量与数据类型、算法逻辑相关的判断。这主要是由于SQL中的数据类型和逻辑，很多在数据库开发时无法确定，只能在运行时确定。这部分过程也称为“解释和执行”。我们可以使用LLVM在运行时生成代码。由于此时数据类型和逻辑已经确定，我们可以删除LLVMIR中不需要的判断操作，从而提高性能。4.LLVM在数据库中的应用在数据库中，团队使用LLVM来处理表达式。下面我们将对比PostgreSQL数据库和云原生数仓AnalyticDBPostgreSQL来讲解LLVM的应用方法。为了实现表达式的解释和执行，PostgreSQL采用了一套“拼写函数”方案。PostgreSQL实现了大量的C函数，如加减法、大小比较等，而且种类繁多。在生成执行计划阶段，SQL会根据表达式符号的类型和数据类型选择相应的函数，保存指针，执行时调用。所以对于过滤条件“a>10andb<5”，假设a和b都是int32，PostgreSQL实际上调用了一个类似“Int8AndOp(Int32GT(a,10),Int32LT(b,5))”这样的函数组合是像积木一样。这样的方案有两个明显的性能问题。一方面，这种方案会带来更多的函数调用，而函数调用本身是有成本的。另一方面，这种方案必须实现统一的函数接口，需要在函数内外进行一些类型转换，这也是额外的性能开销。Odyssey使用LLVM进行代码生成，可以实现最少的代码。因为SQL发出后，数据库知道表达式的符号和输入数据的类型，所以只需要根据需要选择相应的IR命令即可。所以只需要3条IR指令就可以实现这个表达式，然后我们把这个表达式封装成一个函数，在执行的时候可以调用。此操作将多个函数调用简化为一个函数调用，大大减少了指令总数。//示例SQLselectcount(*)fromtablewherea>10andb<5;//PostgreSQL解释了执行计划：多个函数调用result=Int8AndOp(Int32GT(a,10),Int32LT(b,5));//AnalyticDBPostgreSQL解决方案：使用LLVMcodegen生成最小化底层代码%res1=icmpugti32%a,10;%res2=icmpulti32%b,5;%res=andi8%res1,%res2;在数据库中，表达式主要出现在几种场景中。一类是过滤条件，一般出现在where条件中。一种是输出列表，后面一般是select。一些操作符，如join、agg等，其判断条件中也可能有一些复杂的表达式。因此，表达式的处理会出现在数据库执行引擎的各个模块中。在AnalyticDBPostgreSQL版本中，开发团队抽象出一个表达式处理框架，通过LLVMCodegen对这些表达式进行处理，从而提升执行引擎的整体性能。5.总结作为流行的开源编译框架，LLVM近年来被用于加速数据库和AI等系统的性能。由于编译理论本身门槛高，学习LLVM难度大。而且在工程化方面，需要更加准确的了解LLVM的工程化特点和性能特点，才能找到合适的加速场景。AnalyticDBPostgreSQL是阿里云数据库团队的云原生数仓产品，实现了基于LLVM的运行时表达式处理框架，能够有效提升系统在进行复杂数据分析时的性能。
