後端不得不打破的那個承諾
在整個中端裡，IR 一直活在一個舒服的謊言中。在 SSA 形式裡，它替每個值都鑄造一個全新的名字——x1、x2、t37，要多少有多少——而最佳化器推理起來，就彷彿儲存空間是免費且無限的。正是這個虛構，讓前幾篇導引裡的那些最佳化如此乾淨俐落。但真實的 CPU 並沒有無限多個具名的格子。一顆 x86-64 核心大約有十六個通用暫存器（rax、rbx、rcx、rdx、rsi、rdi、rsp、rbp，以及 r8 到 r15），而其中 rsp 已被指定為堆疊指標。後端正是那個舒服的謊言撞上硬體之處，而它的工作之一，就是把那一大群數量無界的虛擬值，擠進晶片那一小組固定的暫存器檔案裡。
為什麼要這麼拚命地把值留在暫存器裡？因為那道落差是巨大的。一個住在暫存器裡的值，能在遠少於一奈秒的時間內供算術單元取用；一個得從記憶體擷取的值，若在快取裡會花上幾個週期，若不在則可能要遠超一百個週期。前面幾級教過你記憶體階層——暫存器在最頂端，接著是快取，再來是主記憶體，每一層都比上一層慢上一大截。暫存器配置就是編譯器一刻接一刻地決定，你那些存活的值之中，哪些有資格坐在那座階層的最頂端。做得好，一個熱迴圈就能跑得接近晶片的尖峰；做得差，同一個迴圈就會淹沒在不必要的記憶體流量裡。
把暫存器配置看成替一張圖著色
暫存器配置的核心，是一個乾淨的觀察：兩個值能安全地共用同一個實體暫存器，當且僅當它們從不在同一刻被需要。為了把這點講精確，編譯器會算出每個值的存活範圍——從這個值被定義之處，到它最後一次被使用之處的那一段程式碼。當兩個值的存活範圍重疊時，它們就互相干涉，因為在某條指令上兩者都必須能同時被讀取，所以它們不能佔用同一個暫存器。整個問題化約成：替每個值指派一個暫存器，使得任兩個互相干涉的值都不會拿到同一個。那些存活範圍從不接觸的值，可以自由地重用一個暫存器——正是這一點，讓十六個暫存器得以容納一個函式在其生命週期裡所拋接的數十個具名值。
這樣一講，這個問題其實是一個著名問題的化身：圖著色。把每個值當成一個節點；在任兩個互相干涉的值之間畫一條邊；然後用你擁有的暫存器數量那麼多種顏色去替節點著色，使得沒有任何一條邊連接兩個同色的節點。一個有效的著色就是一個有效的暫存器指派。圖著色在一般情況下計算上是困難的，所以真實的編譯器並不精確地求解它——它們使用聰明的啟發法（一個經典做法是反覆移除任何鄰居數少於暫存器數的節點，因為這樣的節點總是能最後著色，並把它推上一個堆疊，在回程時著色）。即時（JIT）編譯器因為必須編譯得快，往往完全跳過著色，改用線性掃描：依存活範圍起始的位置順序掃過去，貪婪地發放暫存器，用一點點程式碼品質換取大量的編譯速度。
live ranges (| marks where each value is live): a: |====| b: |=======| c: |====| a interferes with b (ranges overlap) b interferes with c (ranges overlap) a does NOT touch c -> a and c may share one register interference graph: a --- b --- c 2-coloring: a=R1 b=R2 c=R1 (only 2 registers needed)
當暫存器用光時：溢出
有時候那張圖就是無法用你擁有的暫存器著色——在某條指令上，同時存活的值比晶片能容納的暫存器還多。這個函式有著高暫存器壓力，而配置器別無選擇，只能溢出。想像一張只放得下幾樣工具的工作檯：當一項工作需要的工具超過放得下的量，你就把一些放到身後的架子上，需要時再取回來。暫存器是那張工作檯，堆疊是那個架子。要溢出一個值，配置器把它存到堆疊上的一個格子裡、釋出它的暫存器給別的值用，並在它下次被使用之前插入一條載入指令把它取回。因此，每個被溢出的值都要付出兩次額外的記憶體操作——一次儲存與稍後一次重新載入——而這些是它若留在暫存器裡就絕不需要的。
配置器對於要溢出什麼並不隨便：它偏好溢出那些最少被使用、或存活範圍最長的值，好讓多出來的記憶體流量落在最不痛的地方。讀反組譯時，溢出有一個洩漏天機的特徵——一些你從沒寫過、把值搬進搬出像 [rsp-8] 或 [rsp-0x10] 這類堆疊偏移量的意外 mov 指令，包覆在你真正的計算四周。對自己誠實一點，弄清楚這意味著什麼：溢出不是臭蟲，而且常常無可避免；在固定數量的暫存器之下，編譯器做的是對的事。沒有任何設定能賜給你更多的實體暫存器——指令集架構固定了它們的數量。
選擇與排程那些指令
暫存器配置是三件後端工作之一，另外兩件把它夾在中間。配置之前是指令選擇：IR 講的是抽象的操作——加、乘、載入、比較——不屬於任何特定晶片，而選擇器把一塊塊 IR 對著目標的實際指令選單做樣式比對，挑出能產生相同效果的最便宜的真實指令。它常常把好幾個抽象操作融合成一個：在 x86-64 上，位址樣式 base + index * 4 + offset 塌縮成一條使用複雜定址模式的單一載入，而「先乘再加」能變成一條融合乘加（FMA）。這正是為什麼同一份 C 在 x86 與 ARM 上會編譯成真正不同的組合語言的一大原因——後端之所以是針對目標的，正因為指令選單就是。
配置之後是指令排程：現代 CPU 把指令重疊在一條管線上，還能一次發射好幾條，但前提是下一條指令沒在等一個尚未抵達的結果。經典的停頓是載入——一個來自記憶體的值可能要好幾個週期才現身，而立刻使用它的指令會凍住管線等待。排程器建起一張相依圖，重排互相獨立的指令，用有用的工作填滿那段等待，且絕不把一條指令移到它所需結果的來源之前。兩條誠實的但書。第一，大型的亂序核心無論如何都會在執行時用硬體重排，所以靜態排程在較簡單的順序執行晶片上最重要，並作為給硬體的好原料；別誇大它對一顆大型桌機核心的效果。第二，排程器之所以能重排，只因為這麼做保留了單一執行緒的可觀察行為——而正是這同一份自由，使得其他執行緒所看見的記憶體寫入可能顯得被重排了，那屬於記憶體模型的領域，不是單一執行緒排程承諾要保留的東西。
那份授權——以及那個陷阱：由 UB 驅動的程式碼產生
這一級裡的每一個變換——摺疊、內聯、刪除、重排、重用一個暫存器——都立基於你在第一篇導引裡碰過的一個法律基礎：彷彿規則（as-if rule）。標準把你的程式描述成在一台抽象機器上執行，而編譯器唯一必須保留的，是它的可觀察行為：I/O 的內容與順序、對 volatile 物件的讀寫，以及程式的終止。其餘的一切都任憑處置。這就是為什麼一個迴圈可以消失、一個變數可以沒有記憶體位置、各條敘述可以被重排——沒有一樣是可觀察的，所以彷彿規則允許。但那份契約裡有一條長著利齒的條款，而對它誠實，比任何單一最佳化都來得重要。
在此小心地把它陳述出來。彷彿規則保留行為，只對那些有良好定義的程式成立。如果你的程式執行了未定義行為，那台抽象機器就沒有已定義的行為可以保留——於是彷彿規則什麼都不約束，最佳化器簡直可以做任何事。最佳化器把這件事反過來變成一個假設：它假設你的程式從不發生未定義行為，並用這個假設去正當化那些它否則無法做的改寫。這就是由 UB 驅動的最佳化，是這個領域裡後果最重大的一個想法。先把三件事分開，因為它們不斷被混淆：未指定行為指標準允許數種結果而編譯器挑一個（引數的求值順序）；實作定義行為指它必須挑一個有文件記載的（一個 int 有幾個位元）；只有未定義行為授權最佳化器去假設它從不發生。
看它如何咬人，因為這些例子才是全部的重點。因為有號整數溢位是未定義的，編譯器可以假設對一個 signed int x 而言 x + 1 > x 永遠為真，並刪除你所寫、倚賴回繞的那道溢位檢查。因為對空指標解參考是未定義的，如果你的程式碼做了 p->field，卻只在稍後才測試 if (p != NULL)，編譯器可以推論 p 一定自始至終都非空（否則那次解參考就是 UB），並把你那道空指標檢查當成多餘的刪掉——你的安全網被悄悄移除了。而嚴格別名規則讓編譯器假設一個 int * 與一個 float * 從不指向同一批位元組，所以把一個指標轉型成另一個再解參考的型別雙關是 UB，其結果可以看起來不可能。這就是為什麼一個有缺陷的程式能在 -O0「正常」、在 -O2 卻造成破壞：多出來的那些 pass 倚靠著一個你的程式碼所違反的假設。編譯器並非心懷惡意——它是從一個你所打破的前提出發，做著健全的推理。