前言

為何寫作本書

編譯器一端連接著高級(jí)編程語(yǔ)言，另一端連接著硬件，近年來(lái)這兩端的發(fā)展都極為迅猛，例如涌現(xiàn)不少新型編程語(yǔ)言（如Rust、Swift等高級(jí)語(yǔ)言），所以經(jīng)常需要實(shí)現(xiàn)特定的編譯器。另外，由于摩爾定律失效，為了追求性能，領(lǐng)域?qū)Ｓ玫奶幚砥饕苍絹?lái)越流行，新型硬件也需要編譯器支持。

成熟的編譯器可能是最為復(fù)雜的軟件系統(tǒng)之一，例如最為流行的GCC、LLVM、JVM等產(chǎn)品的發(fā)展都超過(guò)了20年，它們的代碼量都達(dá)到了幾百萬(wàn)甚至上千萬(wàn)行。除了工程實(shí)現(xiàn)的復(fù)雜性，編譯器中涉及的數(shù)學(xué)理論、優(yōu)化算法、代碼生成等知識(shí)的復(fù)雜性也是其他軟件系統(tǒng)無(wú)法比擬的。讀者熟知的很多高級(jí)算法都能在編譯器中找到。這些都導(dǎo)致開(kāi)發(fā)和學(xué)習(xí)編譯器非常困難。

近年來(lái)，LLVM編譯器因有良好的結(jié)構(gòu)（模塊化設(shè)計(jì)）、卓越的性能（和GCC相比，在一些場(chǎng)景中性能更高）和完善的功能（包含編譯、調(diào)試、運(yùn)行時(shí)庫(kù)、鏈接等），應(yīng)用越來(lái)越廣泛。不僅傳統(tǒng)的編譯器可以基于LLVM實(shí)現(xiàn)，而且由于LLVM提供了MLIR（多層中間表示），這使得它在AI編譯器等新型編譯器中的使用也越來(lái)越廣泛。因此，越來(lái)越多的從業(yè)人員正在使用LLVM或者期望使用LLVM進(jìn)行編譯器相關(guān)工作。

由于LLVM被業(yè)界廣泛應(yīng)用于編譯器開(kāi)發(fā)，因此其發(fā)展迭代極為迅速，目前LLVM的代碼量極為龐大，其后端代碼量已超過(guò)200萬(wàn)行。LLVM的代碼復(fù)雜度也極高，最新版本已經(jīng)開(kāi)始使用C++ 17語(yǔ)法，想要學(xué)習(xí)、用好LLVM必須對(duì)C++相關(guān)語(yǔ)法比較熟悉。這也導(dǎo)致編譯器初學(xué)者在剛開(kāi)始接觸LLVM的時(shí)候會(huì)遇到不少困難，筆者希望通過(guò)本書幫助相關(guān)人員快速掌握和使用LLVM。

本書是《深入理解LLVM》系列圖書中的第一本，后續(xù)還會(huì)寫另外兩本，分別對(duì)MLIR和編譯優(yōu)化進(jìn)行介紹。

本書內(nèi)容安排說(shuō)明

本書以LLVM 15為例進(jìn)行介紹，不同的LLVM版本對(duì)應(yīng)算法的實(shí)現(xiàn)、提供的命令等都可能略有差異，讀者在試驗(yàn)時(shí)應(yīng)注意選擇正確的版本，否則得到的結(jié)果可能和本書中介紹的不一致。為了保證讀者和筆者使用相同的源碼，筆者維護(hù)了一個(gè)LLVM代碼倉(cāng)的鏡像：https://github.com/inside-compiler/llvm-project，讀者可以從該代碼倉(cāng)下載、編譯LLVM的代碼。同時(shí)，因?yàn)長(zhǎng)LVM是用C++開(kāi)發(fā)的，且使用了較多C++ 17語(yǔ)法，所以如果讀者對(duì)C++比較陌生，應(yīng)先閱讀相關(guān)書籍，本書不對(duì)C++進(jìn)行介紹。

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

TableGen貫穿整個(gè)LLVM代碼生成過(guò)程，在學(xué)習(xí)LLVM代碼生成時(shí)需要對(duì)TableGen有所了解。限于篇幅，本書并沒(méi)有介紹TableGen中的一些高級(jí)語(yǔ)法，例如foreach、defvar等，讀者可以參考官方文檔（https://llvm.org/docs/TableGen/ProgRef.html）進(jìn)行學(xué)習(xí)。

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

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

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

如何閱讀本書

本書包括13章和3個(gè)附錄。

第一部分（第1～6章）為“基礎(chǔ)知識(shí)”，介紹與體系結(jié)構(gòu)無(wú)關(guān)的編譯基礎(chǔ)知識(shí)及TableGen工具，以幫助讀者更好地理解LLVM項(xiàng)目。

第1章主要對(duì)LLVM項(xiàng)目進(jìn)行簡(jiǎn)單介紹，同時(shí)介紹了如何使用Compiler Explorer在線工具學(xué)習(xí)LLVM的各種功能。

第2章主要介紹常見(jiàn)的IR，重點(diǎn)介紹了SSA（Static Single Assignment，靜態(tài)單賦值）形式的相關(guān)知識(shí)，包括SSA構(gòu)造、析構(gòu)等。

第3章主要介紹數(shù)據(jù)流分析的理論基礎(chǔ)、數(shù)據(jù)流方程。通過(guò)學(xué)習(xí)本章，讀者可以了解學(xué)習(xí)編譯優(yōu)化所需的基礎(chǔ)數(shù)據(jù)流知識(shí)。

第4章主要介紹支配、逆支配、支配樹(shù)、逆支配樹(shù)等基礎(chǔ)知識(shí)。在編譯優(yōu)化中通過(guò)支配、逆支配等獲取控制流信息，并完成相關(guān)優(yōu)化。

第5章主要介紹循環(huán)、循環(huán)優(yōu)化（即循環(huán)規(guī)范化）等基礎(chǔ)知識(shí)。循環(huán)優(yōu)化是編譯優(yōu)化中最為重要的優(yōu)化，在代碼生成中主要涉及循環(huán)不變量外提等，除了針對(duì)循環(huán)自身的優(yōu)化外，在一些優(yōu)化中也需要使用循環(huán)信息來(lái)生成最優(yōu)代碼。

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

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

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

第8章主要介紹LLVM中實(shí)現(xiàn)的兩類指令調(diào)度：局部調(diào)度和循環(huán)調(diào)度。局部調(diào)度是當(dāng)前使用最廣泛的調(diào)度，本章詳細(xì)介紹了其中的Linearize、Fast、BURR List等調(diào)度器，并通過(guò)示例演示不同算法如何構(gòu)造調(diào)度依賴圖，以及指令調(diào)度實(shí)現(xiàn)時(shí)的關(guān)注點(diǎn)和調(diào)度過(guò)程；最后介紹了循環(huán)調(diào)度。

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

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

第11章主要介紹在LLVM代碼生成過(guò)程中，函數(shù)棧幀生成以及基于非SSA形式的編譯優(yōu)化。

第12章主要介紹LLVM機(jī)器碼生成過(guò)程，并簡(jiǎn)單介紹了MC和機(jī)器碼生成。

第13章主要以BPF為例介紹如何為L(zhǎng)LVM添加一個(gè)新后端，讓讀者了解在添加新后端時(shí)哪些工作是必需的。

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

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

附錄B主要介紹BPF指令集和在Linux系統(tǒng)上如何運(yùn)行BPF應(yīng)用。

附錄C主要介紹在LLVM中如何設(shè)計(jì)和實(shí)現(xiàn)Pass、PassManager，以在分析、變換過(guò)程中保證編譯過(guò)程性能最優(yōu)。

作者貢獻(xiàn)說(shuō)明

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

勘誤與支持

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

由于本書篇幅有限，很多內(nèi)容都未能囊括，為此筆者維護(hù)了網(wǎng)站：https://inside-compiler.github.io/，書中沒(méi)有討論到的內(nèi)容將通過(guò)該網(wǎng)站呈現(xiàn)。

致謝

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

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

還要感謝谷祖興博士、李堅(jiān)松博士、董如振博士、王篁博士、王亞?wèn)|、韋清福等，他們對(duì)本書提出了很多意見(jiàn)和建議。

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

彭成寒