編譯最佳化｜LLVM程式碼生成技術詳解及在資料庫中的應用
編譯是指什麼
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 %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實現了一套執行時的表示式處理框架，能夠有效地提高系統在進行復雜資料分析時地效能。
作者：長別
本文為阿里雲原創內容，未經允許不得轉載。
