123,123

內(nèi)容簡(jiǎn)介

　　全書(shū)分為3篇。第1篇介紹編譯器基礎(chǔ)知識(shí)，包括中間表示，重點(diǎn)介紹SSA、數(shù)據(jù)流分析、支配、循環(huán)等知識(shí)，此外還介紹了LLVM的后端描述語(yǔ)言TableGen。第二篇剖析分LLVM代碼生成，其中對(duì)代碼生成的每一步驟都有提及，著重介紹指令選擇、指令調(diào)度、寄存器分配和編譯優(yōu)化。同時(shí)還以BPF后端為例總結(jié)了如何基于LLVM開(kāi)發(fā)一款新后端的編譯器。第三篇附錄主要總結(jié)了LLVM代碼生成過(guò)程中使用的IR、BPF指令集以及如何在Linux運(yùn)行BPF應(yīng)用，Pass和PassManager的運(yùn)行機(jī)制等知識(shí)。通過(guò)閱讀本書(shū)，讀者理解和掌握LLVM代碼生成過(guò)程，可以根據(jù)本書(shū)指導(dǎo)為基于LLVM開(kāi)發(fā)一款新后端的編譯器。同時(shí)本書(shū)還介紹了各種編譯過(guò)程中使用到的算法，讀者可以根據(jù)場(chǎng)景對(duì)算法進(jìn)行增強(qiáng)從而達(dá)到性能優(yōu)化目的。

作者簡(jiǎn)介

　　彭成寒：AI編譯器與虛擬機(jī)技術(shù)專家，目前主要專注于LLVM、MLIR相關(guān)的AI編譯器研究，并在JVM、V8和WebAssembly等虛擬機(jī)技術(shù)方面有著豐富的研發(fā)經(jīng)驗(yàn)。他深耕IT領(lǐng)域近20年，曾涉足應(yīng)用軟件和大數(shù)據(jù)開(kāi)發(fā)等多個(gè)領(lǐng)域，并著有《JVM G1源碼分析和調(diào)優(yōu)》《新一代垃圾回收器ZGC設(shè)計(jì)與實(shí)現(xiàn)》《深入探索JVM垃圾回收：ARM服務(wù)器垃圾回收的挑戰(zhàn)和優(yōu)化》等重要領(lǐng)域?qū)Ｖ?。李靈：畢業(yè)于上海交通大學(xué)，擁有6年編譯器和虛擬機(jī)相關(guān)的研發(fā)工作經(jīng)驗(yàn)，深度參與了多項(xiàng)LLVM編譯器及V8、WebAssembly虛擬機(jī)等開(kāi)源項(xiàng)目的研發(fā)工作，目前正在從事AI編譯器研發(fā)工作。戴賢澤：畢業(yè)于南京理工大學(xué)，擁有7年編譯器和虛擬機(jī)相關(guān)工作經(jīng)驗(yàn)，深入?yún)⑴c了方舟編譯器及V8、WebAssembly虛擬機(jī)等開(kāi)源項(xiàng)目的研發(fā)工作，目前正在從事編譯器和虛擬機(jī)的設(shè)計(jì)與研發(fā)工作。王志磊：畢業(yè)于浙江大學(xué)，擁有6年編譯器和虛擬機(jī)相關(guān)的研發(fā)工作經(jīng)驗(yàn)，參與了多項(xiàng)編譯器及虛擬機(jī)的開(kāi)發(fā)項(xiàng)目，并為llvm-bolt、V8、WebAssembly等開(kāi)源項(xiàng)目貢獻(xiàn)代碼，目前專注于虛擬機(jī)相關(guān)的研發(fā)，精通AOT和JIT技術(shù)。俞佳嘉：南京大學(xué)碩士研究生，現(xiàn)任華為編譯器與編程語(yǔ)言實(shí)驗(yàn)室鴻蒙開(kāi)發(fā)者生態(tài)構(gòu)建技術(shù)首席專家。他擁有10余年的豐富工作經(jīng)驗(yàn)，在Intel、Microsoft、華為等世界知名公司從事過(guò)編譯器、虛擬機(jī)、指令翻譯等技術(shù)的相關(guān)研發(fā)工作，并深入?yún)⑴c了Intel Houdini、華為方舟編譯器等產(chǎn)品的核心研發(fā)工作。

圖書(shū)目錄

目　　錄　　Contents
前言
第一部分　基礎(chǔ)知識(shí)
第1章　緒論2
1.1　LLVM設(shè)計(jì)思路分析3
1.2　LLVM主要子項(xiàng)目4
1.3　LLVM構(gòu)建與調(diào)試5
1.4　LLVM在線工具7
1.5　本章小結(jié)9
第2章　IR基礎(chǔ)知識(shí)10
2.1　IR分類11
2.1.1　樹(shù)IR11
2.1.2　線性IR11
2.1.3　圖IR12
2.2　CFG的基本塊與構(gòu)建14
2.2.1　基本塊14
2.2.2　構(gòu)建CFG15
2.3　靜態(tài)單賦值15
2.3.1　基本概念16
2.3.2　SSA構(gòu)造19
2.3.3　SSA析構(gòu)19
2.3.4　SSA分類28
2.3.5　基本塊參數(shù)和Phi節(jié)點(diǎn)29
2.4　本章小結(jié)30
第3章　數(shù)據(jù)流分析基礎(chǔ)知識(shí)31
3.1　半格、格與不動(dòng)點(diǎn)31
3.1.1　半格和偏序集31
3.1.2　格33
3.1.3　不動(dòng)點(diǎn)34
3.2　數(shù)據(jù)流分析原理及描述35
3.2.1　數(shù)據(jù)流方程形式化描述36
3.2.2　數(shù)據(jù)流分析的理論描述40
3.3　數(shù)據(jù)流方程示例43
3.3.1　活躍變量43
3.3.2　到達(dá)定值45
3.3.3　常量傳播46
3.4　擴(kuò)展閱讀：數(shù)據(jù)流的遍歷性能分析49
3.5　本章小結(jié)50
第4章　支配分析51
4.1　支配和逆支配51
4.1.1　支配和逆支配相關(guān)定義51
4.1.2　支配和逆支配含義解析53
4.2　支配樹(shù)和支配邊界的實(shí)現(xiàn)55
4.2.1　半支配節(jié)點(diǎn)及相關(guān)概念56
4.2.2　LT算法和Semi-NCA的差異57
4.2.3　支配邊界的實(shí)現(xiàn)58
4.3　擴(kuò)展閱讀：支配樹(shù)相關(guān)小課堂58
4.3.1　支配樹(shù)構(gòu)造算法及比較59
4.3.2　如何快速判斷任意兩個(gè)節(jié)點(diǎn)的支配關(guān)系60
4.4　本章小結(jié)62
第5章　循環(huán)基本知識(shí)63
5.1　自然循環(huán)64
5.2　LLVM的循環(huán)實(shí)現(xiàn)65
5.2.1　循環(huán)識(shí)別66
5.2.2　循環(huán)規(guī)范化67
5.3　本章小結(jié)71
第6章　TableGen介紹72
6.1　目標(biāo)描述語(yǔ)言72
6.1.1　詞法72
6.1.2　語(yǔ)法74
6.2　TableGen工具鏈77
6.2.1　從TD定義到記錄78
6.2.2　從記錄到C 代碼81
6.3　擴(kuò)展閱讀：如何在TD文件中定義匹配83
6.3.1　隱式定義匹配模板83
6.3.2　復(fù)雜匹配模板84
6.3.3　匹配規(guī)則支撐類86
6.4　本章小結(jié)86
第二部分　代碼生成
第7章　指令選擇91
7.1　指令選擇的處理流程92
7.2　SelectionDAGISel算法分析94
7.2.1　SDNode分類96
7.2.2　LLVM IR到SDNode的轉(zhuǎn)換98
7.2.3　SDNode合法化108
7.2.4　機(jī)器指令選擇117
7.2.5　從DAG輸出MIR123
7.3　快速指令選擇算法分析126
7.4　全局指令選擇算法原理與實(shí)現(xiàn)128
7.4.1　全局指令選擇的階段128
7.4.2　GMIR生成129
7.4.3　指令合法化133
7.4.4　寄存器類型選擇137
7.4.5　機(jī)器指令選擇141
7.4.6　合并優(yōu)化143
7.5　本章小結(jié)146
第8章　指令調(diào)度147
8.1　LLVM指令調(diào)度149
8.1.1　指令調(diào)度算法150
8.1.2　拓?fù)渑判蛩惴?51
8.2　Linearize調(diào)度器152
8.2.1　構(gòu)造依賴圖153
8.2.2　對(duì)依賴圖進(jìn)行調(diào)度153
8.3　Fast調(diào)度器156
8.3.1　Fast調(diào)度器實(shí)現(xiàn)157
8.3.2　物理寄存器依賴場(chǎng)景的處理158
8.3.3　示例分析162
8.4　BURR List調(diào)度器166
8.4.1　影響指令調(diào)度的關(guān)鍵因素166
8.4.2　指令優(yōu)先級(jí)計(jì)算方法168
8.4.3　示例分析170
8.5　Source List調(diào)度器173
8.6　Hybrid List調(diào)度器174
8.7　Pre-RA-MISched調(diào)度器174
8.7.1　Pre-RA-MISched調(diào)度器實(shí)現(xiàn)174
8.7.2　調(diào)度區(qū)域的劃分175
8.7.3　影響Pre-RA-MISched調(diào)度器的關(guān)鍵因素175
8.7.4　MIR指令時(shí)延的計(jì)算175
8.7.5　寄存器壓力的計(jì)算177
8.7.6　示例分析181
8.8　Post-RA-TDList調(diào)度器186
8.8.1　Post-RA-TDList調(diào)度器實(shí)現(xiàn)186
8.8.2　示例分析186
8.9　Post-RA-MISched調(diào)度器189
8.10　循環(huán)調(diào)度190
8.10.1　循環(huán)調(diào)度算法實(shí)現(xiàn)190
8.10.2　示例分析194
8.11　擴(kuò)展閱讀：調(diào)度算法的影響因素200
8.12　本章小結(jié)203
第9章　基于SSA形式的編譯優(yōu)化204
9.1　前期尾代碼重復(fù)205
9.1.1　尾代碼重復(fù)原理205
9.1.2　尾代碼收益判斷207
9.1.3　執(zhí)行尾代碼重復(fù)優(yōu)化209
9.2　Phi優(yōu)化212
9.3　棧著色213
9.4　棧槽分配217
9.5　死指令消除218
9.6　IPL優(yōu)化之If-Conversion219
9.7　循環(huán)不變量外提224
9.8　公共子表達(dá)式消除224
9.9　代碼下沉227
9.10　窺孔優(yōu)化228
9.11　本章小結(jié)231
第10章　寄存器分配232
10.1　寄存器分配流程解析233
10.1.1　Fast算法執(zhí)行流程233
10.1.2　Basic算法執(zhí)行流程233
10.2　寄存器分配涉及的Pass241
10.2.1　死亡和未定義子寄存器檢測(cè)241
10.2.2　隱式定義指令處理243
10.2.3　不可達(dá)MBB消除243
10.2.4　活躍變量分析244
10.2.5　Phi消除246
10.2.6　二地址指令變換249
10.2.7　指令編號(hào)255
10.2.8　變量活躍區(qū)間分析256
10.2.9　寄存器合并256
10.2.10　MBB的頻率分析259
10.2.11　寄存器分配：直接分配與間接分配265
10.2.12　將虛擬寄存器映射到物理寄存器266
10.2.13　棧槽著色266
10.2.14　復(fù)制傳播267
10.2.15　循環(huán)不變量外提269
10.3　Fast算法實(shí)現(xiàn)269
10.3.1　Fast算法實(shí)現(xiàn)思路269
10.3.2　示例分析270
10.4　Basic算法實(shí)現(xiàn)276
10.4.1　算法實(shí)現(xiàn)思路276
10.4.2　示例分析277
10.5　Greedy算法實(shí)現(xiàn)289
10.5.1　Greedy算法實(shí)現(xiàn)思路290
10.5.2　算法實(shí)現(xiàn)的核心：拆分291
10.5.3　區(qū)域拆分之Hopfield網(wǎng)絡(luò)詳解293
10.5.4　使用Hopfield網(wǎng)絡(luò)求解拆分296
10.5.5　示例分析300
10.6　PBQP算法實(shí)現(xiàn)313
10.6.1　PBQP介紹313
10.6.2　寄存器分配和PBQP的關(guān)系314
10.6.3　PBQP問(wèn)題求解314
10.6.4　寄存器分配問(wèn)題建模示例317
10.6.5　PBQP實(shí)現(xiàn)原理以及示例分析318
10.7　擴(kuò)展閱讀：圖著色分配324
10.8　4種算法對(duì)比326
10.9　本章小結(jié)329
第11章　函數(shù)棧幀生成和非SSA形式的編譯優(yōu)化330
11.1　函數(shù)棧幀生成以及相關(guān)優(yōu)化331
11.1.1　棧幀生成331
11.1.2　代碼下沉332
11.1.3　棧幀范圍收縮335
11.2　MIR優(yōu)化337
11.2.1　分支折疊337
11.2.2　尾代碼重復(fù)347
11.2.3　復(fù)制傳播347
11.3　MIR指令變換和調(diào)度347
11.4　MIR信息收集及布局優(yōu)化348
11.4.1　基本塊布局優(yōu)化349
11.4.2　公共代碼提取355
11.4.3　函數(shù)冷熱代碼分離359
11.4.4　代碼布局優(yōu)化比較363
11.5　擴(kuò)展閱讀：后綴樹(shù)構(gòu)造和應(yīng)用365
11.5.1　后綴樹(shù)的構(gòu)造365
11.5.2　后綴樹(shù)的應(yīng)用372
11.6　本章小結(jié)372
第12章　生成機(jī)器碼373
12.1　MC374
12.2　機(jī)器碼生成過(guò)程375
12.2.1　匯編代碼生成376
12.2.2　二進(jìn)制代碼生成378
12.3　本章小結(jié)381
第13章　添加一個(gè)新后端382
13.1　適配新后端的各個(gè)階段382
13.1.1　指令選擇階段的適配383
13.1.2　寄存器分配相關(guān)的適配383
13.1.3　插入前言/后序384
13.1.4　機(jī)器碼生成相關(guān)的適配384
13.2　添加新后端所需要的適配385
13.2.1　定義TD文件386
13.2.2　指令選擇處理386
13.2.3　棧幀處理387
13.2.4　機(jī)器碼生成處理388
13.2.5　添加新后端到LLVM框架中388
13.3　本章小結(jié)389
附錄
附錄A　LLVM的中間表示392
附錄B　BPF介紹407
附錄C　Pass的分類與管理413