前言

為何寫作本書

編譯器一端連接著高級編程語言，另一端連接著硬件，近年來這兩端的發展都極為迅猛，例如涌現不少新型編程語言（如Rust、Swift等高級語言），所以經常需要實現特定的編譯器。另外，由于摩爾定律失效，為了追求性能，領域專用的處理器也越來越流行，新型硬件也需要編譯器支持。

成熟的編譯器可能是最為復雜的軟件系統之一，例如最為流行的GCC、LLVM、JVM等產品的發展都超過了20年，它們的代碼量都達到了幾百萬甚至上千萬行。除了工程實現的復雜性，編譯器中涉及的數學理論、優化算法、代碼生成等知識的復雜性也是其他軟件系統無法比擬的。讀者熟知的很多高級算法都能在編譯器中找到。這些都導致開發和學習編譯器非常困難。

近年來，LLVM編譯器因有良好的結構（模塊化設計）、卓越的性能（和GCC相比，在一些場景中性能更高）和完善的功能（包含編譯、調試、運行時庫、鏈接等），應用越來越廣泛。不僅傳統的編譯器可以基于LLVM實現，而且由于LLVM提供了MLIR（多層中間表示），這使得它在AI編譯器等新型編譯器中的使用也越來越廣泛。因此，越來越多的從業人員正在使用LLVM或者期望使用LLVM進行編譯器相關工作。

由于LLVM被業界廣泛應用于編譯器開發，因此其發展迭代極為迅速，目前LLVM的代碼量極為龐大，其后端代碼量已超過200萬行。LLVM的代碼復雜度也極高，最新版本已經開始使用C++ 17語法，想要學習、用好LLVM必須對C++相關語法比較熟悉。這也導致編譯器初學者在剛開始接觸LLVM的時候會遇到不少困難，筆者希望通過本書幫助相關人員快速掌握和使用LLVM。

本書是《深入理解LLVM》系列圖書中的第一本，后續還會寫另外兩本，分別對MLIR和編譯優化進行介紹。

本書內容安排說明

本書以LLVM 15為例進行介紹，不同的LLVM版本對應算法的實現、提供的命令等都可能略有差異，讀者在試驗時應注意選擇正確的版本，否則得到的結果可能和本書中介紹的不一致。為了保證讀者和筆者使用相同的源碼，筆者維護了一個LLVM代碼倉的鏡像：https://github.com/inside-compiler/llvm-project，讀者可以從該代碼倉下載、編譯LLVM的代碼。同時，因為LLVM是用C++開發的，且使用了較多C++ 17語法，所以如果讀者對C++比較陌生，應先閱讀相關書籍，本書不對C++進行介紹。

LLVM代碼生成的輸入為LLVM IR（Intermediate Representation，中間表示），輸出為機器碼，所以LLVM IR是基礎知識。不熟悉LLVM IR的讀者建議先了解這部分內容，你可以寫一個簡單的C/C++代碼，使用Clang或者本書介紹的Compiler Explorer在線工具將其轉化為LLVM IR，通過與C/C++源碼對比來快速認識和了解LLVM IR。本書在附錄A中也對LLVM IR進行了介紹，但這里更多關注的是LLVM IR的設計與演化發展，并沒有詳細介紹每一條LLVM IR的具體用法，關于如何使用LLVM IR，讀者可以參考官方文檔https://llvm.org/docs/LangRef.html。

TableGen貫穿整個LLVM代碼生成過程，在學習LLVM代碼生成時需要對TableGen有所了解。限于篇幅，本書并沒有介紹TableGen中的一些高級語法，例如foreach、defvar等，讀者可以參考官方文檔（https://llvm.org/docs/TableGen/ProgRef.html）進行學習。

本書在介紹代碼生成時主要以BPF后端為例。BPF是一套虛擬指令集，指令數非常少，BPF后端代碼也較少，很多編譯優化工作都不涉及BPF，所以讀者只需要關注指令選擇、寄存器分配過程，這樣更容易把握代碼生成的脈絡，具體可參見附錄B。

本書主要基于Debug版本的LLVM介紹算法詳細執行過程，并使用GDB/LLDB以調試的方式獲取中間結果，之后對中間結果進行解釋。限于篇幅，書中并沒有直接給出中間結果，而是對中間結果重新進行描述。在閱讀時，建議讀者根據第1章介紹的方法構建自己的調試版本，并使用GDB/LLDB對相關代碼進行調試。如果僅依賴Compiler Explorer在線學習工具，讀者僅能得到最終的結果，很多中間步驟都將被忽略，這可能對算法的理解不利。

另外，本書提供了不少示例代碼，涉及C/C++代碼、LLVM IR、DAG IR、MIR、MC等。我們按照如下規則對這些代碼進行命名：以章節開頭，以“-”為分隔符，后面依次為不同的用例編號，同時為同一用例不同的IR表示書中會使用不同的后綴。例如，第1章中第一個代碼片段會被命名為代碼清單1-1，如果它是C代碼，則會命名為“1-1.c”，以此類推。為了便于讀者驗證，相關代碼和命令都上傳至代碼倉https://github.com/inside-compiler/Inside-LLVM-Code-Gen。

如何閱讀本書

本書包括13章和3個附錄。

第一部分（第1～6章）為“基礎知識”，介紹與體系結構無關的編譯基礎知識及TableGen工具，以幫助讀者更好地理解LLVM項目。

第1章主要對LLVM項目進行簡單介紹，同時介紹了如何使用Compiler Explorer在線工具學習LLVM的各種功能。

第2章主要介紹常見的IR，重點介紹了SSA（Static Single Assignment，靜態單賦值）形式的相關知識，包括SSA構造、析構等。

第3章主要介紹數據流分析的理論基礎、數據流方程。通過學習本章，讀者可以了解學習編譯優化所需的基礎數據流知識。

第4章主要介紹支配、逆支配、支配樹、逆支配樹等基礎知識。在編譯優化中通過支配、逆支配等獲取控制流信息，并完成相關優化。

第5章主要介紹循環、循環優化（即循環規范化）等基礎知識。循環優化是編譯優化中最為重要的優化，在代碼生成中主要涉及循環不變量外提等，除了針對循環自身的優化外，在一些優化中也需要使用循環信息來生成最優代碼。

第6章主要介紹目標描述語言的基本語法、工具的基本功能。LLVM作為通用的編譯器需要支持多種后端，雖然不同的后端設計各有不同，但是都會包含寄存器、指令等公共信息，通過設計目標描述語言統一描述后端信息，并通過輔助工具將描述信息生成代碼，配合LLVM代碼生成框架以供使用（完成指令選擇、調度和寄存器分配等工作），從而使得LLVM可以更加優雅地支持多種后端。

第二部分（第7～13章）為“代碼生成”，介紹與編譯器代碼生成相關的知識，幫助讀者了解編譯器后端所必備的處理環節。

第7章主要介紹LLVM中實現的3種指令選擇算法，分別是SelectionDAGISel、快速指令選擇和全局指令選擇。SelectionDAGISel算法演示了基于LLVM IR構造SDNode的過程，以及基于SDNode進行指令選擇和生成MIR的過程；全局指令選擇算法演示了從LLVM IR到GMIR，再到MIR指令選擇的過程。

第8章主要介紹LLVM中實現的兩類指令調度：局部調度和循環調度。局部調度是當前使用最廣泛的調度，本章詳細介紹了其中的Linearize、Fast、BURR List等調度器，并通過示例演示不同算法如何構造調度依賴圖，以及指令調度實現時的關注點和調度過程；最后介紹了循環調度。

第9章主要介紹LLVM代碼生成過程中基于SSA形式的編譯優化，涵蓋前期尾代碼重復、棧槽分配、If-Conversion、代碼下沉等多種優化算法。

第10章主要介紹LLVM中實現的4種寄存器分配算法——Fast、Basic、Greedy和PBQP。本章以Basic算法為例介紹了寄存器分配依賴的Pass，并介紹Fast、Basic、Greedy和PBQP的原理和實現，還通過示例演示了每種寄存器分配的過程。

第11章主要介紹在LLVM代碼生成過程中，函數棧幀生成以及基于非SSA形式的編譯優化。

第12章主要介紹LLVM機器碼生成過程，并簡單介紹了MC和機器碼生成。

第13章主要以BPF為例介紹如何為LLVM添加一個新后端，讓讀者了解在添加新后端時哪些工作是必需的。

附錄部分主要介紹閱讀本書需要了解的一些背景知識。

附錄A主要介紹LLVM的中間表示，如LLVM IR、DAG、MIR和MC。

附錄B主要介紹BPF指令集和在Linux系統上如何運行BPF應用。

附錄C主要介紹在LLVM中如何設計和實現Pass、PassManager，以在分析、變換過程中保證編譯過程性能最優。

作者貢獻說明

本書由彭成寒、李靈、戴賢澤、王志磊和俞佳嘉共同完成。第5章由戴賢澤負責，第6章由李靈負責，第7章由戴賢澤、李靈共同負責，第8章由俞佳嘉負責，第9章由所有作者合著，第12章和第13章由王志磊負責，第1～4章、第10章、第11章以及附錄部分由彭成寒負責，全書由彭成寒審讀定稿。

勘誤與支持

由于筆者水平有限，書中難免存在一些疏漏，懇請讀者批評指正。大家可以通過https://github.com/inside-compiler/Inside-LLVM-Code-Gen/issues提交issue。期待能夠得到讀者朋友們的誠摯反饋，在技術道路上與大家互勉共進。

由于本書篇幅有限，很多內容都未能囊括，為此筆者維護了網站：https://inside-compiler.github.io/，書中沒有討論到的內容將通過該網站呈現。

致謝

首先非常感謝本書其他作者的傾情付出，在過去一年多的時間里，所有作者每個周末都會花費半天時間在線分析和討論問題、分享源碼或相關論文閱讀的情況，大家花費了大量的業余時間撰寫相關內容，并不斷地修改和完善。

另外在寫作過程中，得到了很多朋友及同事的幫助和支持，彭成曉博士幫助筆者理解Hopfield網絡中能量函數的物理意義和求解方法，楊磊博士幫助筆者證明了Hopfield網絡能量函數的收斂。

還要感謝谷祖興博士、李堅松博士、董如振博士、王篁博士、王亞東、韋清福等，他們對本書提出了很多意見和建議。

最后還要感謝家人對筆者的理解和支持，讓筆者有更多時間和精力完成寫作。

彭成寒