編譯器設計（第3版）

基思?D. 庫珀（Keith D. Cooper），萊斯大學計算機科學系計算工程專業Doerr特聘教授，曾任該系系主任。庫珀博士的研究課題涵蓋過程間數據流分析、標量指令優化、寄存器分配以及指令調度等方面。 琳達?托克森（Linda Torczon），萊斯大學計算機科學系*研究員，其研究內容主要包括代碼生成、過程間數據流分析和優化，以及編程環境

第 1章 編譯概述 1
1.1 引言 1
1.2 編譯器結構 5
1.3 翻譯過程概述 8
1.3.1 前端 9
1.3.2 優化器 11
1.3.3 後端 12
1.4 工程實踐 17
1.5 總結與展望 18
本章註釋 18
練習題 19
第 2章 掃描器 20
2.1 引言 20
2.2 識別單詞 22
2.2.1 識別器的形式化表述 24
2.2.2 識別更覆雜的單詞 25
2.3 正則表達式 27
2.3.1 形式化表示法 28
2.3.2 正則表達式樣例 29
2.3.3 正則表達式的閉包性質 32
2.4 從正則表達式到掃描器 34
2.4.1 非確定有限自動機 35
2.4.2 從正則表達式到NFA：Thompson構造法 37
2.4.3 從NFA到DFA：子集構造法 38
2.4.4 *小化DFA 41
2.4.5 將DFA用作掃描器 45
2.5 實現掃描器 49
2.5.1 表驅動掃描器 49
2.5.2 直接編碼掃描器 52
2.5.3 手動編寫掃描器 54
2.5.4 實踐中的問題 54
2.6 進階內容 58
2.6.1 從DFA到正則表達式 58
2.6.2 無閉包正則表達式 59
2.6.3 DFA*小化的一種替代算法 60
2.7 總結與展望 62
本章註釋 63
練習題 63
第3章 解析器 66
3.1 引言 66
3.2 語法的表示 67
3.2.1 為什麼不使用正則表達式 68
3.2.2 上下文無關文法 69
3.2.3 更覆雜的例子 71
3.2.4 將含義嵌入結構中 74
3.2.5 找出輸入串的推導過程 76
3.3 自頂向下解析 77
3.3.1 文法轉換 78
3.3.2 自頂向下的遞歸下降解析器 88
3.3.3 表驅動LL(1) 解析器 89
3.4 自底向上解析 93
3.4.1 LR(1) 解析算法 95
3.4.2 建立LR(1) 解析表 100
3.4.3 表構造中的錯誤 108
3.5 實踐中的問題 111
3.5.1 錯誤恢覆 111
3.5.2 一元運算符 112
3.5.3 上下文相關二義性的處理 113
3.6 進階內容 114
3.6.1 優化文法 115
3.6.2 縮小LR(1) 解析表的體積 116
3.7 總結與展望 120
本章註釋 121
練習題 121
第4章 中間表示 124
4.1 引言 124
4.2 IR的分類體系 126
4.3 圖IR 129
4.3.1 與語法相關的樹 129
4.3.2 圖 132
4.4 線性IR 136
4.4.1 棧機器代碼 137
4.4.2 三地址代碼 138
4.4.3 線性代碼的表示 139
4.4.4 從線性代碼構造CFG 140
4.5 符號表 143
4.5.1 名稱解析 144
4.5.2 表的實現 146
4.6 命名空間 148
4.6.1 IR中的命名空間 148
4.6.2 靜態單賦值形式 151
4.7 內存中值的放置 153
4.7.1 內存模型 154
4.7.2 在寄存器中保留值 156
4.7.3 將值分配到數據區 156
4.8 總結與展望 159
本章註釋 159
練習題 160
第5章 語法驅動翻譯 163
5.1 引言 163
5.2 背景 165
5.3 語法驅動翻譯概述 166
5.3.1 第 一個例子 166
5.3.2 翻譯表達式 168
5.3.3 控制流語句的翻譯 173
5.4 建立命名環境的模型 176
5.4.1 詞法層級 177
5.4.2 繼承層級 181
5.4.3 可見性 184
5.4.4 執行編譯時名稱解析 185
5.5 類型信息 186
5.5.1 類型在翻譯中的作用 186
5.5.2 類型系統的組成部分 188
5.5.3 表達式的類型推導 191
5.6 存儲布局 194
5.6.1 存儲類和數據區 195
5.6.2 虛擬地址空間中的布局 196
5.6.3 存儲分配 198
5.6.4 在翻譯過程中安排存儲分配 202
5.6.5 對齊限制和填充 202
5.7 進階內容 204
5.7.1 文法結構與結合性 204
5.7.2 類型推導中的難題 206
5.7.3 相對偏移與緩存性能 207
5.8 總結與展望 208
本章註釋 209
練習題 209
第6章 過程的實現 212
6.1 引言 212
6.2 背景 215
6.3 命名的運行時支持 217
6.3.1 類Algol語言的運行時支持 218
6.3.2 面向對象語言的運行時支持 222
6.4 過程間值傳遞 226
6.4.1 參數傳遞 227
6.4.2 返回值 229
6.4.3 為非局部變量建立可尋址性 230
6.5 標準化鏈接 234
6.6 進階內容 238
6.6.1 顯式堆管理 238
6.6.2 隱式釋放 241
6.7 總結與展望 244
本章註釋 245
練習題 245
第7章 代碼形式 250
7.1 引言 250
7.2 算術運算符 252
7.2.1 表達式中的函數調用 254
7.2.2 混合類型表達式 254
7.2.3 減少對寄存器的需求 256
7.3 值的訪問方法 258
7.3.1 標量變量的訪問方法 258
7.3.2 聚合對象的訪問方法 260
7.3.3 範圍檢查 266
7.4 布爾運算符和關系運算符 267
7.4.1 關系表達式的硬件支持 268
7.4.2 硬件支持的變化形式 270
7.5 控制流結構 272
7.5.1 條件執行 273
7.5.2 循環與疊代 274
7.5.3 case語句 277
7.6 字符串的處理 281
7.6.1 字符串的長度 281
7.6.2 字符串的賦值 281
7.6.3 字符串的連接 282
7.6.4 字符串操作的優化 282
7.7 過程調用 283
7.7.1 實參求值 284
7.7.2 保存與恢覆寄存器 285
7.8 總結與展望 286
本章註釋 287
練習題 287
第8章 優化簡介 291
8.1 引言 291
8.2 背景 292
8.2.1 例子 293
8.2.2 對優化的考慮 297
8.2.3 優化的機會 299
8.3 優化的範圍 300
8.4 局部優化 303
8.4.1 局部值編號 303
8.4.2 樹高平衡 309
8.5 區域優化 316
8.5.1 *局部值編號 317
8.5.2 循環展開 319
8.6 全局優化 322
8.6.1 使用活躍集合查找未初始化變量 322
8.6.2 全局代碼置放 327
8.7 過程間優化 332
8.7.1 內聯替換 333
8.7.2 過程置放 336
8.7.3 針對過程間優化的編譯器組織結構 340
8.8 總結與展望 341
本章註釋 342
練習題 343
第9章 數據流分析 347
9.1 引言 347
9.2 疊代數據流分析 349
9.2.1 支配 349
9.2.2 活躍變量分析 353
9.2.3 數據流分析的局限 357
9.2.4 其他數據流問題 359
9.3 SSA 形式 363
9.3.1 構建SSA的簡單方法 365
9.3.2 支配邊界 366
9.3.3 放置 函數 369
9.3.4 重命名 372
9.3.5 從SSA形式轉出為常規形式 377
9.3.6 使用SSA形式 383
9.4 過程間分析 387
9.4.1 構造調用圖 387
9.4.2 過程間常量傳播 389
9.5 進階內容 393
9.5.1 結構化的數據流分析和可歸約性 393
9.5.2 加速支配計算所用疊代框架的算法 396
9.6 總結與展望 398
本章註釋 398
練習題 399
第 10章 標量優化 402
10.1 引言 402
10.2 死代碼* 405
10.2.1 *無用代碼 406
10.2.2 *無用控制流 408
10.2.3 *不可達代碼 410
10.3 代碼移動 411
10.3.1 惰性代碼移動 412
10.3.2 代碼提升 419
10.4 特化 420
10.4.1 尾調用優化 420
10.4.2 葉調用優化 421
10.4.3 參數提升 422
10.5 冗餘* 423
10.5.1 值相同與名稱相同 423
10.5.2 基於支配者的值編號 424
10.6 為其他變換創造機會 427
10.6.1 *塊克隆 427
10.6.2 過程克隆 429
10.6.3 循環判斷外提 429
10.6.4 重命名 430
10.7 進階內容 431
10.7.1 組合優化 431
10.7.2 強度削弱 435
10.7.3 優化序列的選擇 443
10.8 總結與展望 444
本章註釋 445
練習題 446
第 11章 指令選擇 448
11.1 引言 448
11.2 背景 451
11.2.1 ISA設計對指令選擇的影響 452
11.2.2 一個示意性的例子 454
11.2.3 特定的匹配 456
11.3 基於窺孔優化的指令選擇 457
11.3.1 窺孔優化 457
11.3.2 簡化器 459
11.3.3 匹配器 462
11.4 基於樹模式匹配的指令選擇 463
11.4.1 樹的表示方法 464
11.4.2 重寫規則 464
11.4.3 計算覆蓋方案 468
11.4.4 工具 474
11.5 進階內容 476
11.5.1 學習窺孔模式 476
11.5.2 生成指令序列 477
11.6 總結與展望 477
本章註釋 478
練習題 479
第 12章 指令調度 480
12.1 引言 480
12.2 背景 482
12.2.1 影響性能的體系結構特性 483
12.2.2 指令調度問題 485
12.3 局部調度 488
12.3.1 算法 489
12.3.2 重命名 489
12.3.3 構建依賴圖 491
12.3.4 計算優先級 493
12.3.5 列表調度 493
12.3.6 前向列表調度與後向列表調度 496
12.4 區域調度 499
12.4.1 *局部調度 499
12.4.2 蹤跡調度 500
12.4.3 *塊克隆 502
12.5 進階內容 504
12.5.1 軟件流水線背後的策略 504
12.5.2 軟件流水線化算法 507
12.5.3 *一個例子 511
12.6 總結與展望 512
本章註釋 512
練習題 513
第 13章 寄存器分配 516
13.1 引言 516
13.2 背景 518
13.2.1 適於寄存器分配的命名空間：活躍範圍 518
13.2.2 幹涉 520
13.2.3 溢出代碼 522
13.2.4 寄存器類別 523
13.3 局部寄存器分配 525
13.3.1 局部分配器中的重命名 527
13.3.2 分配和指派 528
13.4 基於圖著色的全局分配 532
13.4.1 尋找全局LR 534
13.4.2 構建幹涉圖 535
13.4.3 合並覆制操作 537
13.4.4 估算全局溢出開銷 538
13.4.5 對圖進行著色 539
13.4.6 插入溢出和恢覆代碼 542
13.4.7 處理有重疊的寄存器類別 542
13.5 進階內容 546
13.5.1 保守的合並算法 546
13.5.2 改進的溢出策略 547
13.5.3 其他形式的LR 549
13.6 總結與展望 552
本章註釋 552
練習題 553
第 14章 運行時優化 556
14.1 引言 556
14.2 背景 559
14.2.1 執行模型 560
14.2.2 編譯觸發程序 562
14.2.3 優化的粒度 563
14.2.4 改進的來源 564
14.2.5 構建運行時優化器 567
14.3 熱蹤跡優化 567
14.3.1 執行流程 568
14.3.2 蹤跡的鏈接 572
14.4 熱方法優化 574
14.4.1 混合模式環境中的熱方法 575
14.4.2 本地代碼環境中的熱方法 579
14.5 進階內容 582
14.5.1 優化級別 582
14.5.2 棧上替換 583
14.5.3 代碼緩存管理 584
14.5.4 管理對源代碼的更改 585
14.6 總結與展望 587
本章註釋 587
練習題 588
附錄A ILOC 590
附錄B 數據結構 601
參考文獻 619