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"?？偟膩碚f，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（靜態單賦值），這是編譯技術中非?；A的一個理念。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 %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實現了一套運行時的表達式處理框架，能夠有效地提高系統在進行復雜數據分析時地性能。