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. 良好的溝通和團隊協作能力，能夠熟練編寫各類技術文檔。
有興趣的同學，歡迎發送簡歷到 [email protected]， 也歡迎大家加入雲原生數據倉庫AnalyticDB PostgreSQL版交流釘釘群一起討論交流。
