编译优化 | LLVM代码生成技术详解及在数据库中的应用

时间:2021-10-07  来源:未知   作者:admin

 

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.h tml 。

指令格式 。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 , label , label ""是有条件跳转,意味着这如果是true则跳转到名为的label,否则跳转到名为"的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.h tml ),熟悉下都有哪些指令的类型。接下来我们通过两个简单的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: