Cloudera?Impala是一種為Hadoop生態系統打造的開源MPP(massive parallel processing)數據庫，它主要為分析型查詢負載而設計，而非OLTP。Impala能最大限度地利用現代硬件和高效查詢執行的最新技術。LLVM下的運行時代碼生成就是用來提升執行性能的技術之一。 ### LLVM簡介 LLVM是一個編譯器及相關工具的庫(toolchain)，它不同于獨立應用式(stand-alone)的傳統編譯器，LLVM是模塊化且可重用的。它允許Impala這樣的應用在運行的進程內執行JIT(just-in-time)編譯。盡管LLVM因一些特殊的能力以及著名的工具，如比GCC更優的Clang編譯器，但真正使LLVM區別于其他編譯器的是它的內部架構。 經典靜態編譯器(像多數C編譯器)中，最流行的設計是前端、優化器、后端組成的三階段設計。前端解析源碼并生成抽象語法樹(AST，Abstract Syntax Tree)。優化器會做很多優化來提升代碼性能。后端(或稱代碼生成器)將代碼轉換成目標平臺的指令集。這種模型對解釋器、JIT編譯器。JVM也是這種模型的一種實現，它使用字節碼作為前端和優化器之間的接口。  這種經典設計對于多語言(包括源語言和目標語言)支持非常重要。只要優化器內部使用一種公共代碼表示，前端和后端就能夠編譯任意的語言。當需要移植(porting)編譯器來支持一種新語言時，只需實現一個新前端，而優化器和后端都可以重用。否則就要重新實現整個編譯器，支持M種源語言*N種目標語言。  盡管各種編譯器教科書中都講到三階段設計的種種優點，但實際上它從未被實現過。像Perl、Python、Ruby和Java的編譯器實現并沒有共享任何代碼。此外，還有各種各樣的特殊用途的編譯器，例如圖像處理、正則表達式等CPU密集型的子領域的JIT編譯器。GCC由于混亂的代碼結構而無法提取出可重用的組件，例如前端和后端重用了某些全局變量等，所以我們無法將GCC嵌入到應用程序中。下圖是LLVM對三階段設計的實現。  ### Impala中的LLVM Impala使用LLVM在運行時產生完全優化并且查詢特定的函數，這比通用的預編譯函數有更好的性能。**尤其是會在一次查詢中執行許多次的內層循環(inner loop)的函數**。例如，一個用來解析文件記錄并裝載進Impala內存元組的函數，在每個文件的每一條記錄被掃描時都會被調用。對于這種函數，即使只是簡單的移除一些指令也會得到速度上的巨大提升。 如果沒有運行時的代碼生成，為了處理編譯時未知的運行時數據，函數中總是會包含低效的代碼。例如，僅僅處理整數的記錄解析函數，在處理只有整數的文件時，會比處理各種數據類型的通用函數要快得多。然而要掃描的文件schema在編譯時是未知的，所以這種通用的函數盡管低效，卻也是必要的。 下圖1中的代碼示例。編譯時記錄個數和類型都是未知的，所以**處理函數要寫的盡可能通用，避免發生未考慮到的情況。但JIT與這種思路完全相反**，函數在運行時被完全編譯成對當前數據最高效的寫法。這在我們平時看來甚至都不能算作函數，因為完全不通用，邏輯都用常量固定寫死了，但這正是JIT的策略！所以像下面的動態生成的MaterializeTuple對于不同的運行時信息(如不同的查詢)會有完全不同的生成版本。  代碼生成中的常用優化技術： ???**移除條件分支**：因為已知運行時信息，所以可以優化if/switch語句。這是最簡單有效的方式，因為最終機器碼中的分支指令會阻止指令的管道化(instruction pipelining)和并行執行(instruction-level parallelism)。同時，通過展開for循環(因為我們已經知道循環次數)和解析數據類型，分支指令能被一起移除。 ???**移除內存加載**：從內存加載數據是開銷很大而且阻止管道化的操作。如果每次加載的結果都一樣的話，我們就可以使用代碼生成來替代數據加載。例如，之前圖1中的數組offsets_和types_在每次查詢開始時創建而不會改變，于是在代碼生成的函數版本中，展開for循環后，這些數組中的值可以直接內聯化。 ???**內聯虛函數調用**：虛函數對性能的影響很大，尤其是函數很小很簡單，因為它無法內聯化。因此當對象實例的類型在運行時可知時，我們可以使用代碼生成來取代虛函數的調用，并做內聯化。這對于表達式樹的求值尤為有價值。在Impala中，表達式由操作和函數的樹組成，例如下圖2。樹中出現的每種表達式都是覆蓋(override)表達式基類的函數來實現的，基類會遞歸地調用各個子表達式。許多表達式函數都是非常簡單的，例如兩數相加，于是**虛函數調用的開銷甚至大過表達式求值的開銷**。通過代碼生成移除虛函數并內聯化，表達式可以無需函數調用而直接求值。此外，內聯后的函數使編譯器做進一步的優化，例如子表達式消除等。  ### 用LLVM生成代碼 當Impala受到查詢計劃(query plan，由Impala的Java前端負責生成)時，LLVM會被用來**在查詢執行開始前**，生成并編譯對性能至關重要的函數的查詢特定版本。LLVM主要使用IR(intermediate representation)來生成代碼，例如LLVM的前端Clang C++編譯器生成IR，LLVM優化IR并將其編譯成機器碼。IR類似于匯編語言，由一些簡單的、能夠直接映射成機器碼的指令組成。在Impala中有兩種技術來生成IR函數：使用LLVM的IRBuilder?API來編程式地生成IR指令；使用CLang將C++函數交叉編譯成IR。 下圖是IR的例子。可以看出，IR是一種類RISC的虛擬指令集。它支持加減、比較、分支等指令。此外，IR還支持標簽。但與多數RISC不同的是： ???LLVM是強類型的，它有一套簡單的類型系統，例如i32, i32**，add i32。 ???LLVM IR支持無限的臨時寄存器，以%開頭。 **因為優化器不受源語言和目標平臺限制，所以IR的設計也要遵守這個原則。**  在LLVM中，優化器被組織成優化pass的管道，常見的pass有內聯化、表達式重組、循環不變量移動等。每個pass都作為繼承Pass類的C++類，并定義在一個私有的匿名namespace中，同時提供一個讓外界獲得到pass的函數。  我們可以決定pass的執行順序甚至是否執行。當我們實現一種圖像處理語言的JIT編譯器時，我們可以去掉沒用的pass。例如，如果通常都是大函數的話，就沒必要浪費時間內聯。如果指針很少的話，那么別名分析和內存優化就變得可有可無。但是LLVM不是萬能的，PassManager本身也并不知道每個pass內部的邏輯，所以這還是由我們實現者來確定的。  ### 參考資料 1 Runtime Code Generation in?Cloudera?Impala 2 The Architecture of Open Source Application [http://www.aosabook.org/en/llvm.html](http://www.aosabook.org/en/llvm.html)