JOVANA
Explore Library Glossary Getting Started Three Levels Fields How it works Mission
Join the mission
All guides

深入編譯器管線

你早已不假思索地敲下 gcc -O2 main.c。這一級要打開那個盒子:在你的原始碼與機器碼之間,橫著一條由各個分明階段組成的管線,而一旦你能叫出每一個的名字,你終於就能讀懂最佳化器對你的程式做了什麼——以及為什麼。

從一道命令到許多階段

在前面一級你學到,編譯器把一個翻譯單元變成一個目的檔,而前置處理器最先跑、組譯器連結器最後跑。那給了你工具鏈的形狀:原始碼進去,一個可執行檔出來。這一級要放大你叫做「編譯器」的那一步,發現它本身就是一條管線——一連串的階段,每一個都吃掉上一階段的輸出,產出一個更乾淨、更低層的形式。為這些階段命名的全部用意,就是讓你不再把編譯器看成一個不透明的動詞,而開始把它看成一個地方,那裡發生著各種具體、可理解的變換。

把它切開最乾淨的方式是分成三大區域,而這一級其餘的全部內容都住在它們裡面。前端講的是你的原始語言:它做詞法分析、語法分析與型別檢查,它的工作要嘛是用一條診斷訊息拒絕你的程式,要嘛是把一個乾淨的內部形式交給下一個區域。中端不講任何特定語言——它在一個中立的中間表示法上工作,跑各種最佳化。後端講的是機器:它把那份最佳化過的 IR 降階成某顆特定 CPU 的指令。前端進、機器出,中端在兩者之間做那件聰明事。

前端:從文字到一棵檢查過的樹

讓一行小小的程式走過前端:int n = a + b * 2;。首先,詞法分析器掃過字元,把它們分組成記號(token)——int、n、=、a、+、b、、2、;——把一條扁平的位元組流變成一個個有標籤的詞。詞法分析器不在乎這些詞意味*什麼;它只知道哪些形狀是合法的詞。接著,語法分析器拿這些記號對照 C 的文法,建起一棵捕捉結構的樹:它知道 b * 2 比 + 結合得更緊,所以樹裡乘法是加法的子節點。那棵樹就是抽象語法樹(AST),而它是你的程式以結構而非文字之姿存在的第一個內部形式。

一棵能通過語法分析的樹,還不是一棵有意義的樹,這就是語意分析登場之處。這個階段走過樹,問那些文法無法回答的問題:n 宣告了嗎?a 與 b 的型別在 + 與 * 之下合法地結合嗎?有沒有整數提升要套用?它在每個節點上填上型別、把每個名字解析到它的宣告,而它正是發出你實際撞上的大多數錯誤的階段——「未宣告的識別字」、「不相容的型別」。只有撐過語意分析的程式才被允許繼續往下;下游的一切都得以假設這個程式型別正確、結構良好,正是這一點讓後面的階段變得可處理。

中端:最佳化一個語言中立的形式

一旦前端有了一棵檢查過的樹,它就把樹降階成中間表示法——也就是 IR——交給中端。IR 刻意比你的原始碼更簡單、更一致:巢狀的運算式被攤平成一連串微小的操作,每一個把一件事算進一個暫時值。這大致就是下一篇導引所稱的三位址碼的樣子,而後面一篇導引會把它再磨利成SSA 形式。要一個中立 IR 的理由與三區域切分相同:在 IR 上只寫一次的最佳化,能為每一個前端工作、讓每一個後端受益,於是那份聰明只在恰好一個地方建起來。

source:        int n = a + b * 2;

front end  ->  IR (three operations, two temporaries):
                 t1 = b * 2
                 t2 = a + t1
                 n  = t2

middle end ->  optimize on the IR (constant folding, etc.)
back end   ->  pick real instructions for this CPU:
                 imul  r8, rbx, 2
                 add   r8, rax
                 mov   [n], r8
一道原始碼敘述,降階成扁平的 IR,再降成指令。每個 IR 操作把一個值算進一個暫時值——正是這種一致的形狀,讓中端的最佳化好寫、讓後端的工作機械化。

中端跑的就是你會花上整整兩篇導引去談的那些最佳化:內聯常數傳播死碼消除、迴圈變換等等。它不是一掃而過地做完;它跑一長串小小的pass,每一個都是一個聚焦的變換,讀進 IR 再把它改寫。這些 pass 經過排序,好讓每一個為下一個清理場地——傳播一個常數會暴露出死碼、刪掉死碼又會暴露出一個如今空了的迴圈,如此這般。哪些 pass 會跑、跑得多激進,由最佳化等級掌管:-O0 幾乎一個都不跑,把 IR 留得貼近你的原始碼以便除錯,而 -O2 則把整條管線放開。

後端:挑選真實的指令

最佳化過的 IR 仍然是抽象的——它有無限多的暫時值與通用的操作,而非任何真實晶片的暫存器與運算碼。後端用三件經典工作把那道落差補上,每一件都會在這一級最後一篇導引裡得到專門處理。指令選擇把 IR 操作對映到真正的機器指令,常常把好幾個 IR 操作融合成 CPU 提供的某一條聰明指令。暫存器配置把無限多的暫時值指派到 CPU 那一小組固定的實體暫存器(rax、rbx 之類),不夠用時就溢出到堆疊。指令排程接著重排選好的指令,讓管線化的 CPU 保持忙碌,因為一種排序可以比另一種跑得明顯更快。

後端發出組合語言文字之後,管線就接回你已經認識的工具鏈:組譯器把那段文字變成一個目的檔的位元組,而連結器把各個目的檔與函式庫縫合成最終的可執行檔。所以那道著名的一行命令 gcc -O2 -Wall main.c,其實是在驅動這一整條鏈——前置處理、詞法分析、語法分析、型別檢查、降階成 IR、跨許多 pass 最佳化、選擇與排程指令、配置暫存器、組譯、連結——並在任一階段察覺到什麼不對勁時,往你的終端機印出一條警告。

授權整個最佳化器的那條規則

你大可合理地問:中端究竟憑什麼被允許改寫你的程式碼?這份授權就是彷彿規則(as-if rule)。標準不是用暫存器或指令來描述你的程式;它用一台抽象機器以及一組可觀察行為來描述——對 volatile 物件讀寫了什麼、程式輸出了什麼、I/O 的副作用是什麼。彷彿規則說,編譯器可以用任何方式改寫你的程式,只要改寫後程式的可觀察行為與抽象機器的相符即可。其餘的一切——內部計算的順序、某個變數是否曾經存在於記憶體裡、某個迴圈是否真的跑過——全都任憑它處置。

這就是為什麼你的 -O2 建置可以在編譯期算出 b * 2、刪掉一個你「明明」寫過的變數、或用完全不同的指令順序跑你的迴圈,卻仍然是一次正確的編譯:那些都不可觀察,所以彷彿規則允許。但這條規則有一個你先前見過的黑暗孿生兄弟。編譯器是對著C 抽象機器推理的,而一旦你觸發未定義行為,那台機器就沒有已定義的行為——於是最佳化器有權假設 UB 從不發生,並在這個假設上做最佳化。這正是一個臭蟲如何能在 -O0 隱形、在 -O2 卻造成破壞:多出來的那些 pass 倚靠著一個你那有缺陷的程式碼所違反的假設。這一級最後一篇導引會完整地回到這件事,談由 UB 驅動的最佳化;眼下,你只要記住:彷彿規則既讓最佳化器強大,又在有 UB 在場時讓它冷酷無情。