高級(jí)編譯器設(shè)計(jì)與實(shí)現(xiàn)

第1章  高級(jí)主題介紹        1
1.1  編譯器結(jié)構(gòu)回顧        1
1.2  基本問(wèn)題中的高級(jí)論題        2
1.3  代碼優(yōu)化的重要性        4
1.4  優(yōu)化編譯器的結(jié)構(gòu)        5
1.5  激進(jìn)型優(yōu)化編譯器中各種優(yōu)化的位置        7
1.6  本書(shū)各章的閱讀流程        10
1.7  本書(shū)沒(méi)有涉及的相關(guān)主題        10
1.8  例子中所用的目標(biāo)機(jī)        11
1.9  數(shù)的表示與數(shù)據(jù)的大小        11
1.10  小結(jié)        11
1.11  進(jìn)一步閱讀        12
1.12  練習(xí)        12
第2章  非形式化編譯算法表示        13
2.1  擴(kuò)展的巴科斯-諾爾范式語(yǔ)法表示        13
2.2  ICAN簡(jiǎn)介        14
2.3  ICAN概貌        16
2.4  完整的程序        17
2.5  類(lèi)型定義        18
2.6  聲明        18
2.7  數(shù)據(jù)類(lèi)型和表達(dá)式        19
2.7.1  一般簡(jiǎn)單類(lèi)型        20
2.7.2  枚舉類(lèi)型        20
2.7.3  數(shù)組        21
2.7.4  集合        21
2.7.5  序列        22
2.7.6  元組        23
2.7.7  記錄        23
2.7.8  聯(lián)合        24
2.7.9  函數(shù)        24
2.7.10  編譯專(zhuān)用的類(lèi)型        24
2.7.11  值nil        25
2.7.12  size運(yùn)算符        25
2.8  語(yǔ)句        25
2.8.1  賦值語(yǔ)句        26
2.8.2  過(guò)程調(diào)用語(yǔ)句        27
2.8.3  返回語(yǔ)句        27
2.8.4  goto語(yǔ)句        27
2.8.5  if語(yǔ)句        27
2.8.6  case語(yǔ)句        27
2.8.7  while語(yǔ)句        28
2.8.8  for語(yǔ)句        28
2.8.9  repeat語(yǔ)句        28
2.8.10  ICAN的關(guān)鍵字        28
2.9  小結(jié)        29
2.10  進(jìn)一步閱讀        29
2.11  練習(xí)        29
第3章  符號(hào)表結(jié)構(gòu)        31
3.1  存儲(chǔ)類(lèi)、可見(jiàn)性和生命期        31
3.2  符號(hào)屬性和符號(hào)表項(xiàng)        32
3.3  局部符號(hào)表管理        34
3.4  全局符號(hào)表結(jié)構(gòu)        35
3.5  存儲(chǔ)綁定和符號(hào)寄存器        38
3.6  生成取數(shù)和存數(shù)指令的方法        42
3.7  小結(jié)        46
3.8  進(jìn)一步閱讀        46
3.9  練習(xí)        47
第4章  中間表示        49
4.1  與中間語(yǔ)言設(shè)計(jì)有關(guān)的問(wèn)題        49
4.2  高級(jí)中間語(yǔ)言        50
4.3  中級(jí)中間語(yǔ)言        51
4.4  低級(jí)中間語(yǔ)言        52
4.5  多級(jí)中間語(yǔ)言        52
4.6  我們的中間語(yǔ)言：MIR、HIR和LIR        53
4.6.1  中級(jí)中間表示（MIR）        53
4.6.2  高級(jí)中間表示（HIR）        56
4.6.3  低級(jí)中間表示（LIR）        57
4.7  用ICAN表示MIR、HIR和LIR        58
4.7.1  用ICAN表示MIR        59
4.7.2  用ICAN表示HIR        62
4.7.3  用ICAN表示LIR        64
4.8  管理中間代碼的若干數(shù)據(jù)結(jié)構(gòu)和例程的ICAN命名        67
4.9  其他中間語(yǔ)言形式        70
4.9.1  三元式        70
4.9.2  樹(shù)        71
4.9.3  無(wú)環(huán)有向圖（DAG）        72
4.9.4  前綴波蘭表示        73
4.10  小結(jié)        74
4.11  進(jìn)一步閱讀        74
4.12  練習(xí)        74
第5章  運(yùn)行時(shí)支持        77
5.1  數(shù)據(jù)表示和指令        77
5.2  寄存器用法        80
5.3  局部棧幀        81
5.4  運(yùn)行時(shí)棧        83
5.5  參數(shù)傳遞規(guī)則        84
5.6  過(guò)程的入口處理、出口處理、調(diào)用和返回        86
5.6.1  用寄存器傳遞參數(shù)：平面寄存器文件        87
5.6.2  用運(yùn)行時(shí)棧傳遞參數(shù)        88
5.6.3  用具有寄存器窗口的寄存器傳遞參數(shù)        89
5.6.4  過(guò)程值變量        91
5.7  代碼共享與位置無(wú)關(guān)代碼        91
5.8  符號(hào)和多態(tài)語(yǔ)言支持        94
5.9  小結(jié)        96
5.10  進(jìn)一步閱讀        96
5.11  練習(xí)        97
第6章  自動(dòng)產(chǎn)生代碼生成器        99
6.1  簡(jiǎn)介代碼生成器的自動(dòng)生成        100
6.2  語(yǔ)法制導(dǎo)技術(shù)        100
6.2.1  代碼生成器        102
6.2.2  代碼生成器的產(chǎn)生器        103
6.2.3  刪除鏈循環(huán)        110
6.2.4  刪除句法阻滯        112
6.2.5  最后的考慮        115
6.3  語(yǔ)義制導(dǎo)的分析介紹        115
6.4  樹(shù)模式匹配和動(dòng)態(tài)規(guī)劃        116
6.5  小結(jié)        120
6.6  進(jìn)一步閱讀        120
6.7  練習(xí)        121
第7章  控制流分析        123
7.1  控制流分析的方法        125
7.2  深度為主查找、前序遍歷、后序遍歷和寬度為主查找        128
7.3  必經(jīng)結(jié)點(diǎn)和后必經(jīng)結(jié)點(diǎn)        132
7.4  循環(huán)和強(qiáng)連通分量        139
7.5  可歸約性        143
7.6  區(qū)間分析和控制樹(shù)        144
7.7  結(jié)構(gòu)分析        147
7.8  小結(jié)        156
7.9  進(jìn)一步閱讀        157
7.10  練習(xí)        157
第8章  數(shù)據(jù)流分析        159
8.1  一個(gè)例子：到達(dá)-定值        159
8.2  基本概念：格、流函數(shù)和不動(dòng)點(diǎn)        163
8.3  數(shù)據(jù)流問(wèn)題及其解決方法的分類(lèi)        166
8.4  迭代數(shù)據(jù)流分析        168
8.5  流函數(shù)的格        171
8.6  基于控制樹(shù)的數(shù)據(jù)流分析        172
8.7  結(jié)構(gòu)分析        172
8.7.1  結(jié)構(gòu)分析：向前問(wèn)題        172
8.7.2  結(jié)構(gòu)分析：向后問(wèn)題        178
8.7.3  結(jié)構(gòu)分析方程的表示        180
8.8  區(qū)間分析        181
8.9  其他方法        182
8.10  du鏈、ud鏈和網(wǎng)        183
8.11  靜態(tài)單賦值形式        184
8.12  數(shù)組、結(jié)構(gòu)和指針的處理        188
8.13  數(shù)據(jù)流分析器的自動(dòng)構(gòu)造        188
8.14  更貪婪的分析        189
8.15  小結(jié)        191
8.16  進(jìn)一步閱讀        192
8.17  練習(xí)        192
第9章  依賴(lài)關(guān)系分析和依賴(lài)圖        195
9.1  依賴(lài)關(guān)系        195
9.2  基本塊依賴(lài)DAG        196
9.3  循環(huán)中的依賴(lài)關(guān)系        200
9.4  依賴(lài)關(guān)系測(cè)試        204
9.5  程序依賴(lài)圖        207
9.6  動(dòng)態(tài)分配的對(duì)象之間的依賴(lài)關(guān)系        209
9.7  小結(jié)        210
9.8  進(jìn)一步閱讀        211
9.9  練習(xí)        211
第10章  別名分析        213
10.1  各種現(xiàn)實(shí)程序設(shè)計(jì)語(yǔ)言中的別名        215
10.1.1  Fortran 77中的別名        216
10.1.2  Pascal中的別名        216
10.1.3  C中的別名        217
10.1.4  Fortran 90中的別名        218
10.2  別名收集器        218
10.3  別名傳播器        222
10.4  小結(jié)        227
10.5  進(jìn)一步閱讀        227
10.6  練習(xí)        228
第11章  優(yōu)化簡(jiǎn)介        229
11.1  第12~18章討論的全局優(yōu)化        230
11.2  流敏感性和可能與一定信息        231
11.3  各種優(yōu)化的重要性        231
11.4  優(yōu)化的順序與重復(fù)        232
11.5  進(jìn)一步閱讀        235
11.6  練習(xí)        235
第12章  前期優(yōu)化        237
12.1  常數(shù)表達(dá)式計(jì)算（常數(shù)折疊）        237
12.2  聚合量標(biāo)量替代        238
12.3  代數(shù)化簡(jiǎn)和重結(jié)合        240
12.3.1  地址表達(dá)式的代數(shù)化簡(jiǎn)和重結(jié)合        241
12.3.2  對(duì)浮點(diǎn)表達(dá)式應(yīng)用代數(shù)化簡(jiǎn)        246
12.4  值編號(hào)        247
12.4.1  作用于基本塊的值編號(hào)        247
12.4.2  全局值編號(hào)        251
12.5  復(fù)寫(xiě)傳播        256
12.6  稀有條件常數(shù)傳播        261
12.7  小結(jié)        267
12.8  進(jìn)一步閱讀        269
12.9  練習(xí)        269
第13章  冗余刪除        271
13.1  公共子表達(dá)式刪除        271
13.1.1  局部公共子表達(dá)式刪除        272
13.1.2  全局公共子表達(dá)式刪除        276
13.1.3  向前替代        284
13.2  循環(huán)不變代碼外提        284
13.3  部分冗余刪除        292
13.4  冗余刪除和重結(jié)合        298
13.5  代碼提升        299
13.6  小結(jié)        302
13.7  進(jìn)一步閱讀        302
13.8  練習(xí)        304
第14章  循環(huán)優(yōu)化        305
14.1  歸納變量?jī)?yōu)化        305
14.1.1  識(shí)別歸納變量        306
14.1.2  強(qiáng)度削弱        312
14.1.3  活躍變量分析        319
14.1.4  歸納變量刪除和線(xiàn)性函數(shù)測(cè)試替換        320
14.2  不必要邊界檢查的消除        325
14.3  小結(jié)        327
14.4  進(jìn)一步閱讀        329
14.5  練習(xí)        329
第15章  過(guò)程優(yōu)化        331
15.1  尾調(diào)用優(yōu)化和尾遞歸刪除        331
15.2  過(guò)程集成        334
15.3  內(nèi)嵌擴(kuò)展        337
15.4  葉例程優(yōu)化和收縮包裝        338
15.4.1  葉例程優(yōu)化        338
15.4.2  收縮包裝        339
15.5  小結(jié)        341
15.6  進(jìn)一步閱讀        343
15.7  練習(xí)        343
第16章  寄存器分配        345
16.1  寄存器分配和指派        345
16.2  局部方法        346
16.3  圖著色        347
16.3.1  圖著色寄存器分配概述        347
16.3.2  頂層結(jié)構(gòu)        349
16.3.3  網(wǎng)，可分配對(duì)象        350
16.3.4  沖突圖        354
16.3.5  沖突圖的表示        355
16.3.6  寄存器合并        358
16.3.7  計(jì)算溢出代價(jià)        359
16.3.8  修剪沖突圖        361
16.3.9  指派寄存器        363
16.3.10  溢出符號(hào)寄存器        365
16.3.11  圖著色寄存器分配的兩個(gè)例子        367
16.3.12  其他問(wèn)題        375
16.4  基于優(yōu)先級(jí)的圖著色        376
16.5  其他寄存器分配方法        377
16.6  小結(jié)        377
16.7  進(jìn)一步閱讀        378
16.8  練習(xí)        380
第17章  代碼調(diào)度        381
17.1  指令調(diào)度        381
17.1.1  分支調(diào)度        382
17.1.2  表調(diào)度        385
17.1.3  自動(dòng)生成指令調(diào)度器        390
17.1.4  超標(biāo)量實(shí)現(xiàn)有關(guān)的調(diào)度        390
17.1.5  基本塊調(diào)度中的其他問(wèn)題        390
17.1.6  跨基本塊邊界的調(diào)度        392
17.2  前瞻取和上推        392
17.3  前瞻調(diào)度        393
17.4  軟流水        393
17.4.1  窗口調(diào)度        395
17.4.2  展開(kāi)-壓實(shí)軟流水        397
17.4.3  循環(huán)展開(kāi)        400
17.4.4  變量擴(kuò)張        403
17.4.5  寄存器重命名        404
17.4.6  軟流水的其他方法        407
17.4.7  層次歸約        407
17.5  蹤跡調(diào)度        408
17.6  滲透調(diào)度        409
17.7  小結(jié)        411
17.8  進(jìn)一步閱讀        413
17.9  練習(xí)        413
第18章  控制流和低級(jí)優(yōu)化        415
18.1  不可到達(dá)代碼的刪除        415
18.2  伸直化        417
18.3  if化簡(jiǎn)        419
18.4  循環(huán)化簡(jiǎn)        420
18.5  循環(huán)倒置        421
18.6  無(wú)開(kāi)關(guān)化        422
18.7  分支優(yōu)化        422
18.8  尾融合或交叉轉(zhuǎn)移        423
18.9  條件傳送        424
18.10  死代碼刪除        425
18.11  分支預(yù)測(cè)        429
18.12  機(jī)器方言和指令歸并        430
18.13  小結(jié)        433
18.14  進(jìn)一步閱讀        433
18.15  練習(xí)        435
第19章  過(guò)程間分析與優(yōu)化        437
19.1  過(guò)程間控制流分析：調(diào)用圖        438
19.2  過(guò)程間數(shù)據(jù)流分析        445
19.2.1  流不敏感副作用分析        445
19.2.2  流敏感副作用：程序概要圖        455
19.2.3  副作用計(jì)算中的其他問(wèn)題        458
19.3  過(guò)程間常數(shù)傳播        458
19.4  過(guò)程間別名分析        461
19.4.1  流不敏感別名分析        462
19.4.2  傳值和傳指針語(yǔ)言的過(guò)程間別名分析        471
19.5  過(guò)程間優(yōu)化        473
19.6  過(guò)程間寄存器分配        475
19.6.1  連接時(shí)的寄存器分配        475
19.6.2  編譯時(shí)的過(guò)程間寄存器分配        477
19.7  全局引用的聚合        477
19.8  過(guò)程間程序管理中的其他主題        478
19.9  小結(jié)        478
19.10  進(jìn)一步閱讀        480
19.11  練習(xí)        480
第20章  存儲(chǔ)層次優(yōu)化        483
20.1  數(shù)據(jù)和指令高速緩存的影響        484
20.2  指令高速緩存優(yōu)化        485
20.2.1  利用硬件輔助：指令預(yù)取        485
20.2.2  過(guò)程排序        485
20.2.3  過(guò)程和基本塊的放置        489
20.2.4  過(guò)程內(nèi)的代碼安置        489
20.2.5  過(guò)程分裂        492
20.2.6  過(guò)程內(nèi)和過(guò)程間方法的結(jié)合        492
20.3  數(shù)組元素的標(biāo)量替換        493
20.4  數(shù)據(jù)高速緩存優(yōu)化        496
20.4.1  過(guò)程間的數(shù)據(jù)安排        497
20.4.2  循環(huán)轉(zhuǎn)換        498
20.4.3  局部性與循環(huán)鋪砌        502
20.4.4  利用硬件輔助：數(shù)據(jù)預(yù)取        504
20.5  標(biāo)量?jī)?yōu)化與面向存儲(chǔ)器的優(yōu)化        505
20.6  小結(jié)        506
20.7  進(jìn)一步閱讀        508
20.8  練習(xí)        508
第21章  編譯器實(shí)例分析與未來(lái)的發(fā)展趨勢(shì)        509
21.1  Sun用于SPARC的編譯器        510
21.1.1  SPARC體系結(jié)構(gòu)        510
21.1.2  Sun SPARC編譯器        511
21.2  IBM POWER和PowerPC體系結(jié)構(gòu)的XL編譯器        517
21.2.1  POWER和PowerPC體系結(jié)構(gòu)        517
21.2.2  XL編譯器        518
21.3  DEC用于Alpha的編譯器        524
21.3.1  Alpha體系結(jié)構(gòu)        524
21.3.2  Alpha的GEM編譯器        525
21.4  Intel 386體系結(jié)構(gòu)上的Intel參考編譯器        530
21.4.1  Intel 386體系結(jié)構(gòu)        530
21.4.2  Intel編譯器        531
21.5  小結(jié)        538
21.6  編譯器設(shè)計(jì)和實(shí)現(xiàn)未來(lái)的趨勢(shì)        539
21.7  進(jìn)一步閱讀        539
附錄A  本書(shū)使用的匯編語(yǔ)言指南        541
附錄B  集合、序列、樹(shù)、DAG和函數(shù)的表示        549
附錄C  軟件資源        557
參考文獻(xiàn)        561
索引        579