編譯器設(shè)計

前言

　　構(gòu)建編譯器的實踐方法一直在不斷變化，部分是因為處理器和系統(tǒng)的設(shè)計會發(fā)生變化。例如，當我們在1998年開始寫作本書初版時，一些同事對書中指令調(diào)度方面的內(nèi)容頗感疑惑，因為亂序執(zhí)行威脅到了指令調(diào)度，很有可能會使其變得不再重要。現(xiàn)在第2版已經(jīng)付印，隨著多核處理器的崛起和爭取更多核心的推動，順序執(zhí)行流水線再次展現(xiàn)吸引力，因為這種流水線占地較少，設(shè)計者能夠?qū)⒏嗪诵姆胖迷谝粔K芯片上。短期內(nèi)，指令調(diào)度仍然很重要。　　同時，編譯器構(gòu)建社區(qū)還將繼續(xù)產(chǎn)生新的思路和算法，并重新發(fā)現(xiàn)原本有效但在很大程度上卻被遺忘的舊技術(shù)。圍繞著寄存器分配中弦圖（chordal graph）使用（參見13.5.2節(jié)）的最新研究頗為令人振奮。該項工作承諾可以簡化圖著色分配器（graph-coloring allocator）的某些方面。Brzozowski的算法是一種DFA最小化技術(shù)，可以追溯到20世紀60年代早期，但卻已有數(shù)十年未在編譯器課程中講授了（參見2.6.2節(jié)）。 該算法提供了一種容易的路徑，可以從子集構(gòu)造（subset construction）的實現(xiàn)得到一個最小化DFA的實現(xiàn)。編譯器構(gòu)建方面的現(xiàn)代課程本該同時包括這兩種思想?！　∧敲?，為了讓學習者準備好進入這個不斷變化的領(lǐng)域，我們該如何設(shè)計編譯器構(gòu)建課程的結(jié)構(gòu)呢？我們相信，這門課應該使每個學生學會建立新編譯器組件和修改現(xiàn)存編譯器所需的各項基本技能。學生既需要理解籠統(tǒng)的概念，如鏈接約定中隱含的編譯器、鏈接器、裝載器和操作系統(tǒng)之間的協(xié)作，也需要理解微小的細節(jié)，如編譯器編寫者如何減少每個過程調(diào)用時保存寄存器的代碼總共所占的空間。　　第2版中的改變　　本書提供了兩種視角：編譯器構(gòu)建領(lǐng)域中各問題的整體圖景，以及各種可選算法方案的詳細討論。在構(gòu)思本書的過程中，我們專注于該書的可用性，使其既可作為教科書，又可用做專業(yè)人士的參考書。為此，我們特別進行了下述改動?！　「倪M了闡述思想的流程，以幫助按順序閱讀本書的學生。每章章首簡介會解釋該章的目的，列出主要的概念，并概述主題相關(guān)內(nèi)容。書中的示例已經(jīng)重寫過，使得章與章之間的內(nèi)容具有連續(xù)性。此外，每章都從摘要和一組關(guān)鍵詞開始，以幫助那些會將本書用做參考書的讀者?！　≡诿抗?jié)末尾都增加了本節(jié)回顧和復習題。復習題用于快速檢查讀者是否理解了該節(jié)的要點。　　關(guān)鍵術(shù)語的定義放在了它們被首次定義和討論的段落之后?！　〈罅啃抻喠擞嘘P(guān)優(yōu)化的內(nèi)容，使其能夠更廣泛地涵蓋優(yōu)化編譯器的各種可能性?！　‖F(xiàn)在的編譯器開發(fā)專注于優(yōu)化和代碼生成。對于新雇用的編譯器編寫者來說，他們往往會被指派去將代碼生成器移植到新處理器，或去修改優(yōu)化趟，而不會去編寫詞法分析器或語法分析器。成功的編譯器編寫者必須熟悉優(yōu)化（如靜態(tài)單賦值形式的構(gòu)建）和代碼生成領(lǐng)域當前最好的實踐技術(shù)（如軟件流水線）。他們還必須擁有相關(guān)的背景和洞察力，能理解未來可能出現(xiàn)的新技術(shù)。最后，他們必須深刻理解詞法分析、語法分析和語義推敲（semantic elaboration）技術(shù)，能構(gòu)建或修改編譯器前端?！　”緯且槐窘炭茣?、一門教程，幫助學生接觸到現(xiàn)代編譯器領(lǐng)域中的各種關(guān)鍵問題，并向?qū)W生提供解決這些問題所需的背景知識。從第1版開始，我們就維持了各主題之間的基本均衡。前端是實用組件，可以從可靠的廠商購買或由某個開源系統(tǒng)改編而得。但是，優(yōu)化器和代碼生成器通常是對特定處理器定制的，有時甚至針對單個處理器型號定制，因為性能嚴重依賴于所生成代碼的底層細節(jié)。這些事實影響到了當今構(gòu)建編譯器的方法，它們也應該影響我們講授編譯器構(gòu)建課程的方法?！　”緯Y(jié)構(gòu)　　本書內(nèi)容劃分為篇幅大致相等的四個部分?！　〉谝徊糠郑ǖ?章～第4章）涵蓋編譯器前端及建立前端所用工具的設(shè)計和構(gòu)建?！　〉诙糠郑ǖ?章～第7章）探討從源代碼到編譯器的中間形式的映射，這些章考查前端為優(yōu)化器和后端所生成代碼的種類?！　〉谌糠郑ǖ?章～第10章）介紹代碼優(yōu)化。第8章提供對優(yōu)化的概述。第9章和第10章包含了對分析和轉(zhuǎn)換的更深入的處理，本科課程通常略去這兩章?！　〉谒牟糠郑ǖ?1章～第13章）專注于編譯器的后端所使用的算法。　　編譯的藝術(shù)性與科學性　　編譯器構(gòu)建的內(nèi)容有兩部分，一是將理論應用到實踐方面所取得的驚人成就，一是對我們能力受限之處的探討。這些成就包括：現(xiàn)代詞法分析器是通過應用正則語言的理論自動構(gòu)建識別器而建立的；LR語法分析器使用同樣的技術(shù)執(zhí)行句柄識別，進而驅(qū)動了一個移進歸約語法分析器；數(shù)據(jù)流分析巧妙有效地將格理論應用到程序分析中；代碼生成中使用的近似算法為許多真正困難的問題提供了較好的解?！　×硪环矫妫幾g器構(gòu)建也揭示了一些難以解決的復雜問題。用于現(xiàn)代處理器的編譯器后端對兩個以上的NP完全問題（指令調(diào)度、寄存器分配，也許還包括指令和數(shù)據(jù)安排）采用了近似算法來獲取答案。這些NP完全問題，雖然看起來與諸如表達式的代數(shù)重新關(guān)聯(lián)這種問題相近（示例見圖7-1）。但后者有著大量的解決方案，更糟的是，對于這些NP完全問題來說，所要的解往往取決于編譯器和應用程序代碼中的上下文信息。在編譯器對此類問題近似求解時，會面臨編譯時間和可用內(nèi)存上的限制。好的編譯器會巧妙地混合理論、實踐知識、技術(shù)和經(jīng)驗?！　〈蜷_一個現(xiàn)代優(yōu)化編譯器，你會發(fā)現(xiàn)各式各樣的技術(shù)。編譯器使用貪婪啟發(fā)式搜索來探索很大的解空間，使用確定性有限自動機來識別輸入中的單詞。不動點算法被用于推斷程序行為，通過定理證明程序和代數(shù)化簡器來預測表達式的值。編譯器利用快速模式匹配算法將抽象計算映射到機器層次上的操作。它們使用線性丟番圖方程和普瑞斯伯格算術(shù)（Pressburger arithmetic）來分析數(shù)組下標。最后，編譯器使用了大量經(jīng)典的算法和數(shù)據(jù)結(jié)構(gòu)，如散列表、圖算法和稀疏集實現(xiàn)方法等?！　”緯鴩L試同時闡釋編譯器構(gòu)建的藝術(shù)和科學這兩方面內(nèi)容。通過選取足夠廣泛的題材，向讀者表明，確實存在一些折中的解決方案，而設(shè)計決策的影響可能是微妙而深遠的。另一方面，本書也省去了某些長期以來都列入本科編譯器構(gòu)建課程的技術(shù)，隨著市場、語言和編譯器技術(shù)或工具可用性方面的改變，這些技術(shù)已變得不那么重要了。　　講述方法　　編譯器構(gòu)建是一種工程設(shè)計實踐。每個方案的成本、優(yōu)點和復雜程度各異，編譯器編寫者必須在多種備選方案中做出抉擇。每個決策都會影響到最終的編譯器。最終產(chǎn)品的質(zhì)量，取決于抉擇過程中所做的每一個理性決斷?！　∫蚨?，對于編譯器中的許多設(shè)計決策來說，并不存在唯一的正確答案。即使在“理解透徹”和“已解決”的問題中，設(shè)計和實現(xiàn)中的細微差別都會影響到編譯器的行為及其產(chǎn)生的代碼的質(zhì)量。每個決策都涉及許多方面。舉例來說，中間表示的選擇對于編譯器中其余部分有著深刻的影響，無論是時間和空間需求，還是應用不同算法的難易程度。但實際上確定該決策時，通?？晒┰O(shè)計者考慮的時間并不多。第5章考察了中間表示的空間需求，以及其他一些應該在選擇中間表示時考慮的問題。在本書中其他地方，我們會再次提出該問題，既會在正文中直接提出，也會在習題里間接提出?！　”緯剿髁司幾g器的設(shè)計空間，既從深度上闡釋問題，也從廣度上探討可能的答案。它給出了這些問題的某些解決方法，并說明了使用這些方案的約束條件。編譯器編寫者需要理解這些問題及其答案，以及所作決策對編譯器設(shè)計的其他方面的影響。只有這樣，編寫者才能作出理性和明智的選擇。　　思想觀念　　本書闡釋了我們在構(gòu)建編譯器方面的思想觀念，這是在各自超過25年的研究、授課和實踐過程中發(fā)展起來的。例如，中間表示應該展示最終代碼所關(guān)注的那些細節(jié)，這種理念導致了對底層表示的偏愛。又比如，值應該駐留在寄存器中，直至分配器發(fā)現(xiàn)無法繼續(xù)保留它為止，這種做法產(chǎn)生了使用虛擬寄存器的例子，以及僅在無可避免時才將值存儲到內(nèi)存的例子。每個編譯器都應該包括優(yōu)化，它簡化了編譯器其余的部分。多年以來的經(jīng)驗，使得我們能夠理性地選擇書的主題和展現(xiàn)方式?！　￡P(guān)于編程習題的選擇　　編譯器構(gòu)建方面的課程，提供了在一個具體應用程序（編譯器）環(huán)境中探索軟件設(shè)計問題的機會，任何具備編譯器構(gòu)建課程背景的學生，都已經(jīng)透徹理解了該應用程序的基本功能。在多數(shù)編譯器設(shè)計課程中，編程習題發(fā)揮了很大的作用。　　我們以這樣的方式講授過這門課：學生從頭到尾構(gòu)建一個簡單的編譯器，從生成的詞法分析器和語法分析器開始，結(jié)束于針對某個簡化的RISC指令集的代碼生成器。我們也以另一種方式講授過這門課程，學生編寫程序來解決各個良好自包含的問題，諸如寄存器分配或指令調(diào)度。編程習題的選擇實際上非常依賴于本課程在相關(guān)課程中所扮演的角色?！　≡谀承W校，編譯器課程充當高年級的頂級課程，將來自許多其他課程的概念匯集到一個大型的實際設(shè)計和實現(xiàn)項目中。在這樣的課程中，學生應該為一門簡單的語言編寫一個完整的編譯器，或者修改一個開源的編譯器，以支持新的語言或體系結(jié)構(gòu)特性。這門課程可以按本書的內(nèi)容組織，從頭到尾講授本書的內(nèi)容?！　≡诹硗庖恍W校，編譯器設(shè)計出現(xiàn)在其他課程中，或以其他方式呈現(xiàn)在教學中。此時，編譯器設(shè)計教師應該專注于算法及其實現(xiàn)，比如局部寄存器分配器或樹高重新平衡趟這樣的編程習題。在這種情況下，可以選擇性講解本書中的內(nèi)容，也可以調(diào)整講述的順序，以滿足編程習題的需求。例如，在萊斯大學，我們通常使用簡單的局部寄存器分配器作為第一個編程習題，任何具有匯編語言編程經(jīng)驗的學生，都可以理解該問題的基本要素。但這種策略，需要讓學生在學習第2章之前，首先接觸第13章的內(nèi)容。　　不管采用哪種方案，本課程都應該從其他課程取材。在計算機組織結(jié)構(gòu)、匯編語言編程、操作系統(tǒng)、計算機體系結(jié)構(gòu)、算法和形式語言之間，存在著明顯的關(guān)聯(lián)。盡管編譯器構(gòu)建與其他課程的關(guān)聯(lián)不那么明顯，但這種關(guān)聯(lián)同等重要。第7章中討論的字符復制，對于網(wǎng)絡協(xié)議、文件服務器和Web服務器等應用程序的性能而言，都發(fā)揮著關(guān)鍵的作用。第2章中用于詞法分析的技術(shù)可以應用到文本編輯和URL過濾等領(lǐng)域。第13章中自底向上的局部寄存器分配器是最優(yōu)離線頁面替換算法MIN的“近親”?！　⊙a充材料　　還有一些補充的資源可用，可幫助讀者改編本書的內(nèi)容，使之適用于自己的課程。這包括作者在萊斯大學講授這門課程的一套完整的講義以及習題答案。讀者可以聯(lián)系本地的Elsevier業(yè)務代表，詢問如何獲取這些補充材料 ?！　≈轮x　　許多人參與了第1版的出版工作，他們的貢獻也體現(xiàn)在第2版中。許多人指出了第1版中的問題，包括Amit Saha、Andrew Waters、Anna Youssefi、Ayal Zachs、Daniel Salce、David Peixotto、Fengmei Zhao、Greg Malecha、Hwansoo Han、Jason Eckhardt、Jeffrey Sandoval、John Elliot、Kamal Sharma、Kim Hazelwood、Max Hailperin、Peter Froehlich、Ryan Stinnett、Sachin Rehki、Sa·nak Ta··rlar、Timothy Harvey和Xipeng Shen，在此向他們致謝。我們還要感謝第2版的審閱者，包括Jeffery von Ronne、Carl Offner、David Orleans、K. Stuart Smith、John Mallozzi、Elizabeth White和Paul C. Anagnostopoulos。Elsevier的產(chǎn)品團隊，特別是Alisa Andreola、Andre Cuello和Megan Guiney，在將草稿轉(zhuǎn)換成書的過程中發(fā)揮了關(guān)鍵作用。所有這些人都以其深刻的洞察力和無私的幫助，從各個重要方面提升了本書的質(zhì)量。　　最后，在過去5年中，無論是從精神方面，還是從知識方面，許多人都為我們提供了莫大的支持。首先，我們的家庭和萊斯大學的同事都在不斷地鼓勵我們。特別感謝小女Christine和Carolyn，她們耐心容忍了無數(shù)次關(guān)于編譯器構(gòu)建方面各種主題的長時間討論。Nate McFadden以其耐心和出色的幽默感，從開始到出版，一直指導著本書的工作。Penny Anderson對于日常行政事務管理方面的幫助對于本書的完成至關(guān)重要。對所有這些人，我們表示衷心的感謝。

內(nèi)容概要

　　《編譯器設(shè)計(第2版)》是編譯器設(shè)計領(lǐng)域的經(jīng)典著作，主要從以下四部分詳解了編譯器的設(shè)計過程。第一部分涵蓋編譯器前端設(shè)計和建立前端所用工具的設(shè)計和構(gòu)建；第二部分探討從源代碼到編譯器中間形式的映射，考察前端為優(yōu)化器和后端所生成代碼的種類；第三部分介紹代碼優(yōu)化，同時包含對分析和轉(zhuǎn)換的進一步處理；第四部分專門講解編譯器后端使用的算法。
　　《編譯器設(shè)計(第2版)》適合作為高等院校計算機專業(yè)本科生和研究生編譯課程的教材和參考書，也可供相關(guān)技術(shù)人員參考。

作者簡介

　　Keith D.
Cooper是萊斯大學的計算工程Doerr講席教授。他研究過編譯后代碼優(yōu)化領(lǐng)域的大量問題，包括過程間數(shù)據(jù)流分析及其應用、值編號、代數(shù)重新關(guān)聯(lián)、寄存器分配和指令調(diào)度等。他近期的工作專注于從根本上重新考察傳統(tǒng)編譯器的結(jié)構(gòu)和行為。他講授過各種本科生水平的課程，從程序設(shè)計入門到研究生水平的代碼優(yōu)化等。他還是ACM院士。
Linda
Torczon是萊斯大學計算機科學系的高級研究科學家，她是PACE（平臺可感知編譯環(huán)境）項目的首席研究員，該項目由DARPA（國防高級研究計劃局）贊助，意在開發(fā)一種優(yōu)化編譯器環(huán)境，能夠針對新平臺自動地調(diào)整其優(yōu)化機制和策略。從1990年到2000年，Torczon擔任并行計算研究中心的執(zhí)行總監(jiān)，該中心是美國國家科學基金會下屬的一個科技中心。她還擔任過HiPerSoft、洛斯阿拉莫斯計算機科學研究所和虛擬網(wǎng)格應用開發(fā)軟件項目的執(zhí)行總監(jiān)。

書籍目錄

第1章 　編譯概觀
1.1 　簡介
1.2 　編譯器結(jié)構(gòu)
1.3 　轉(zhuǎn)換概述
1.3.1 　前端
1.3.2 　優(yōu)化器
1.3.3 　后端
1.4 　小結(jié)和展望
第2章 　詞法分析器
2.1 　簡介
2.2 　識別單詞
2.2.1 　識別器的形式化
2.2.2 　識別更復雜的單詞
2.3 　正則表達式
2.3.1 　符號表示法的形式化
2.3.2 　示例
2.3.3 　RE的閉包性質(zhì)
2.4 　從正則表達式到詞法分析器
2.4.1 　非確定性有限自動機
2.4.2 　從正則表達式到NFA：Thompson構(gòu)造法
2.4.3 　從NFA到DFA：子集構(gòu)造法
2.4.4 　從DFA到最小DFA：Hopcroft算法
2.4.5 　將DFA用做識別器
2.5 　實現(xiàn)詞法分析器
2.5.1 　表驅(qū)動詞法分析器
2.5.2 　直接編碼的詞法分析器
2.5.3 　手工編碼的詞法分析器
2.5.4 　處理關(guān)鍵字
2.6 　高級主題
2.6.1 　從DFA到正則表達式
2.6.2 　DFA最小化的另一種方法：Brzozowski算法
2.6.3 　無閉包的正則表達式
2.7 　小結(jié)和展望
第3章 　語法分析器
3.1 　簡介
3.2 　語法的表示
3.2.1 　為什么不使用正則表達式
3.2.2 　上下文無關(guān)語法
3.2.3 　更復雜的例子
3.2.4 　將語義編碼到結(jié)構(gòu)中
3.2.5 　為輸入符號串找到推導
3.3 　自頂向下語法分析
3.3.1 　為進行自頂向下語法分析而轉(zhuǎn)換語法
3.3.2 　自頂向下的遞歸下降語法分析器
3.3.3 　表驅(qū)動的LL(1)語法分析器
3.4 　自底向上語法分析
3.4.1 　LR(1)語法分析算法
3.4.2 　構(gòu)建LR(1)表
3.4.3 　表構(gòu)造過程中的錯誤
3.5 　實際問題
3.5.1 　出錯恢復
3.5.2 　一元運算符
3.5.3 　處理上下文相關(guān)的二義性
3.5.4 　左遞歸與右遞歸
3.6 　高級主題
3.6.1 　優(yōu)化語法
3.6.2 　減小LR(1)表的規(guī)模
3.7 　小結(jié)和展望
第4章 　上下文相關(guān)分析
4.1 　簡介
4.2 　類型系統(tǒng)簡介
4.2.1 　類型系統(tǒng)的目標
4.2.2 　類型系統(tǒng)的組件
4.3 　屬性語法框架
4.3.1 　求值的方法
4.3.2 　環(huán)
4.3.3 　擴展實例
4.3.4 　屬性語法方法的問題
4.4 　特設(shè)語法制導轉(zhuǎn)換
4.4.1 　特設(shè)語法制導轉(zhuǎn)換的實現(xiàn)
4.4.2 　例子
4.5 　高級主題
4.5.1 　類型推斷中更困難的問題
4.5.2 　改變結(jié)合性
4.6 　小結(jié)和展望
第5章 　中間表示
5.1 　簡介
5.2 　圖IR
5.2.1 　與語法相關(guān)的樹
5.2.2 　圖
5.3 　線性IR
5.3.1 　堆棧機代碼
5.3.2 　三地址代碼
5.3.3 　線性代碼的表示
5.3.4 　根據(jù)線性代碼建立控制流圖
5.4 　將值映射到名字
5.4.1 　臨時值的命名
5.4.2 　靜態(tài)單賦值形式
5.4.3 　內(nèi)存模型
5.5 　符號表
5.5.1 　散列表
5.5.2 　建立符號表
5.5.3 　處理嵌套的作用域
5.5.4 　符號表的許多用途
5.5.5 　符號表技術(shù)的其他用途
5.6 　小結(jié)和展望
第6章 　過程抽象
6.1 　簡介
6.2 　過程調(diào)用
6.3 　命名空間
6.3.1 　類Algol語言的命名空間
6.3.2 　用于支持類Algol語言的運行時結(jié)構(gòu)
6.3.3 　面向?qū)ο笳Z言的命名空間
6.3.4 　支持面向?qū)ο笳Z言的運行時結(jié)構(gòu)
6.4 　過程之間值的傳遞
6.4.1 　傳遞參數(shù)
6.4.2 　返回值
6.4.3 　確定可尋址性
6.5 　標準化鏈接
6.6 　高級主題
6.6.1 　堆的顯式管理
6.6.2 　隱式釋放
6.7 　小結(jié)和展望
第7章 　代碼形式
7.1 　簡介
7.2 　分配存儲位置
7.2.1 　設(shè)定運行時數(shù)據(jù)結(jié)構(gòu)的位置
7.2.2 　數(shù)據(jù)區(qū)的布局
7.2.3 　將值保持在寄存器中
7.3 　算術(shù)運算符
7.3.1 　減少對寄存器的需求
7.3.2 　訪問參數(shù)值
7.3.3 　表達式中的函數(shù)調(diào)用
7.3.4 　其他算術(shù)運算符
7.3.5 　混合類型表達式
7.3.6 　作為運算符的賦值操作
7.4 　布爾運算符和關(guān)系運算符
7.4.1 　表示
7.4.2 　對關(guān)系操作的硬件支持
7.5 　數(shù)組的存儲和訪問
7.5.1 　引用向量元素
7.5.2 　數(shù)組存儲布局
7.5.3 　引用數(shù)組元素
7.5.4 　范圍檢查
7.6 　字符串
7.6.1 　字符串表示
7.6.2 　字符串賦值
7.6.3 　字符串連接
7.6.4 　字符串長度
7.7 　結(jié)構(gòu)引用
7.7.1 　理解結(jié)構(gòu)布局
7.7.2 　結(jié)構(gòu)數(shù)組
7.7.3 　聯(lián)合和運行時標記
7.7.4 　指針和匿名值
7.8 　控制流結(jié)構(gòu)
7.8.1 　條件執(zhí)行
7.8.2 　循環(huán)和迭代
7.8.3 　case語句
7.9 　過程調(diào)用
7.9.1 　實參求值
7.9.2 　保存和恢復寄存器
7.10 　小結(jié)和展望
第8章 　優(yōu)化簡介
8.1 　簡介
8.2 　背景
8.2.1 　例子
8.2.2 　對優(yōu)化的考慮
8.2.3 　優(yōu)化的時機
8.3 　優(yōu)化的范圍
8.4 　局部優(yōu)化
8.4.1 　局部值編號
8.4.2 　樹高平衡
8.5 　區(qū)域優(yōu)化
8.5.1 　超局部值編號
8.5.2 　循環(huán)展開
8.6 　全局優(yōu)化
8.6.1 　利用活動信息查找未初始化變量
8.6.2 　全局代碼置放
8.7 　過程間優(yōu)化
8.7.1 　內(nèi)聯(lián)替換
8.7.2 　過程置放
8.7.3 　針對過程間優(yōu)化的編譯器組織結(jié)構(gòu)
8.8 　小結(jié)和展望
第9章 　數(shù)據(jù)流分析
9.1 　簡介
9.2 　迭代數(shù)據(jù)流分析
9.2.1 　支配性
9.2.2 　活動變量分析
9.2.3 　數(shù)據(jù)流分析的局限性
9.2.4 　其他數(shù)據(jù)流問題
9.3 　靜態(tài)單賦值形式
9.3.1 　構(gòu)造靜態(tài)單賦值形式的簡單方法
9.3.2 　支配邊界
9.3.3 　放置 函數(shù)
9.3.4 　重命名
9.3.5 　從靜態(tài)單賦值形式到其他形式的轉(zhuǎn)換
9.3.6 　使用靜態(tài)單賦值形式
9.4 　過程間分析
9.4.1 　構(gòu)建調(diào)用圖
9.4.2 　過程間常量傳播
9.5 　高級主題
9.5.1 　結(jié)構(gòu)性數(shù)據(jù)流算法和可歸約性
9.5.2 　加速計算支配性的迭代框架算法的執(zhí)行
9.6 　小結(jié)和展望
第10章 　標量優(yōu)化
10.1 　簡介
10.2 　消除無用和不可達代碼
10.2.1 　消除無用代碼
10.2.2 　消除無用控制流
10.2.3 　消除不可達代碼
10.3 　代碼移動
10.3.1 　緩式代碼移動
10.3.2 　代碼提升
10.4 　特化
10.4.1 　尾調(diào)用優(yōu)化
10.4.2 　葉調(diào)用優(yōu)化
10.4.3 　參數(shù)提升
10.5 　冗余消除
10.5.1 　值相同與名字相同
10.5.2 　基于支配者的值編號算法
10.6 　為其他變換制造時機
10.6.1 　超級塊復制
10.6.2 　過程復制
10.6.3 　循環(huán)外提
10.6.4 　重命名
10.7 　高級主題
10.7.1 　合并優(yōu)化
10.7.2 　強度削減
10.7.3 　選擇一種優(yōu)化序列
10.8 　小結(jié)和展望
第11章 　指令選擇
11.1 　簡介
11.2 　代碼生成
11.3 　擴展簡單的樹遍歷方案
11.4 　通過樹模式匹配進行指令選擇
11.4.1 　重寫規(guī)則
11.4.2 　找到平鋪方案
11.4.3 　工具
11.5 　通過窺孔優(yōu)化進行指令選擇
11.5.1 　窺孔優(yōu)化
11.5.2 　窺孔變換程序
11.6 　高級主題
11.6.1 　學習窺孔模式
11.6.2 　生成指令序列
11.7 　小結(jié)和展望
第12章 　指令調(diào)度
12.1 　簡介
12.2 　指令調(diào)度問題
12.2.1 　度量調(diào)度質(zhì)量的其他方式
12.2.2 　是什么使調(diào)度這樣難
12.3 　局部表調(diào)度
12.3.1 　算法
12.3.2 　調(diào)度具有可變延遲的操作
12.3.3 　擴展算法
12.3.4 　在表調(diào)度算法中打破平局
12.3.5 　前向表調(diào)度與后向表調(diào)度
12.3.6 　提高表調(diào)度的效率
12.4 　區(qū)域性調(diào)度
12.4.1 　調(diào)度擴展基本程序塊
12.4.2 　跟蹤調(diào)度
12.4.3 　通過復制構(gòu)建適當?shù)纳舷挛沫h(huán)境
12.5 　高級主題
12.5.1 　軟件流水線的策略
12.5.2 　用于實現(xiàn)軟件流水線的算法
12.6 　小結(jié)和展望
第13章 　寄存器分配
13.1 　簡介
13.2 　背景問題
13.2.1 　內(nèi)存與寄存器
13.2.2 　分配與指派
13.2.3 　寄存器類別
13.3 　局部寄存器分配和指派
13.3.1 　自頂向下的局部寄存器分配
13.3.2 　自底向上的局部寄存器分配
13.3.3 　超越單個程序塊
13.4 　全局寄存器分配和指派
13.4.1 　找到全局活動范圍
13.4.2 　估算全局逐出代價
13.4.3 　沖突和沖突圖
13.4.4 　自頂向下著色
13.4.5 　自底向上著色
13.4.6 　合并副本以減小度數(shù)
13.4.7 　比較自頂向下和自底向上全局分配器
13.4.8 　將機器的約束條件編碼到?jīng)_突圖中
13.5 　高級主題
13.5.1 　圖著色寄存器分配方法的變體
13.5.2 　靜態(tài)單賦值形式上的全局寄存器分配
13.6 　小結(jié)和展望
附錄A 　ILOC
附錄B 　數(shù)據(jù)結(jié)構(gòu)
參考文獻
索引

媒體關(guān)注與評論

“編譯器是一個內(nèi)容豐富的研究領(lǐng)域，將整個計算機科學融匯在一個優(yōu)雅的構(gòu)造中。Cooper和Torczon的這本書很受歡迎，可以指導讀者輕松學習編譯器這種軟件系統(tǒng)，新版增加了兩位作者的一些設(shè)計經(jīng)驗，并明確指出了許多必須注意的細節(jié)，同時又不忘強調(diào)設(shè)計的大局觀。對任何不熟悉編譯器的人來說，本書都是不可多得的參考手冊。”                   ——Michael D. Smith，哈佛大學文理學院院長，工程與應用科學John H. Finley Jr.講席教授“本書是構(gòu)建現(xiàn)代優(yōu)化編譯器的最佳指南。作者汲取了編譯器構(gòu)建領(lǐng)域大量的經(jīng)驗，以幫助學生掌握整體設(shè)計思路，同時引導學生了解構(gòu)建有效的優(yōu)化編譯器所必需的許多重要而微妙的細節(jié)。尤其值得一提的是，在我讀過的書中，本書對靜態(tài)單賦值形式的闡述最為清晰?！薄狫effery von Ronne，得克薩斯大學圣安東尼奧分校計算機科學系助理教授“本書采用了更常規(guī)且一致的結(jié)構(gòu)，還包含大量輔助教學的內(nèi)容，如復習題、附加示例、術(shù)語解釋和文本框說明等，這提升了它作為教科書的價值。本書還包括大量技術(shù)上的更新，包括非傳統(tǒng)語言、實際編譯器和編譯器技術(shù)非傳統(tǒng)用途方面的更多內(nèi)容。優(yōu)化方面的內(nèi)容是第1版的特色，這一版中變得更為清晰易讀?！薄狹ichael L. Sccot，羅徹斯特大學計算機科學系教授，Programming Language Pragmatics的作者“Keith Cooper和Linda Torczon不僅很好地講述了編譯器的歷史，也從實踐者的角度闡述了如何開發(fā)編譯器。書中包括了大量頗具實用價值的討論和說明，既涉及理論，也涉及眾多現(xiàn)存編譯器的實例（如Lisp、FORTRAN等）。對入門和高級“分配”與“優(yōu)化”概念的全面討論，實際上涵蓋了編譯器設(shè)計的整個生命周期。對于計算機科學專業(yè)的學生以及編譯器設(shè)計和開發(fā)人員來說，本書都是必備參考書?！薄狣avid Orleans，諾瓦東南大學“這本書寫得實在是棒極了，內(nèi)容翔實，輔以大量圖表和示例說明，作為大學編譯器課程的教科書和從業(yè)人員的參考書再合適不過了。代碼優(yōu)化是其重點?！?                                                            ——Reviews.com

編輯推薦

深入剖析現(xiàn)代編譯器運用的算法和技術(shù)。強調(diào)代碼優(yōu)化和代碼生成。體現(xiàn)編譯原理教學的最新理念

圖書封面

圖書標簽Tags

無

評論、評分、閱讀與下載

---

    編譯器設(shè)計 PDF格式下載

---