C編譯器剖析

在計算機中，CPU的速度比內存的速度快得多，編譯器應盡量有效地利用寄存器資源，減少對內存的不必要訪問，從而提高由編譯器生成的匯編代碼的運行速度。在中間代碼生成階段，UCC編譯器用臨時變量t來存放形如“t: a+b;”的公共子表達式的值；到了匯編代碼生成時，UCC編譯器會盡可能地把這些公共子表達式的值存放在寄存器，當需要再次重用時，就可以直接由相應的寄存器中得到。不過，CPU中寄存器的資源是很有限的，在32位的x86 芯片上，匯編程序員可用的寄存器有{eax,ebx, ecx,edx, esi,edi,esp,ebp}，不過寄存器esp一般用於指向棧頂，而ebp一般用於指向活動記錄的底部。真正可供選擇的寄存器就只有{eax,ebx,ecx,edx,esi,edi}這6個，當公共子表達式的個數比可用寄存器更多時，我們就要把某些寄存器的值回寫(WriteBack)到“臨時變量對應的內存單元”中，以便騰出可用寄存器來存放其他值。當然如果待回寫的寄存器中的值已經不再需要，或者從內存載入CPU後並沒有發生變化，我們就不必浪費時間去做回寫操作了。這有點類似操作系統請求分頁中的頁面置換算法。為了簡化寄存器的分配算法，UCC編譯器只為臨時變量分配寄存器，這意味著我們希望盡可能地重用形如“t: a+b;”這樣的公共子表達式。我們還是用一個簡單的例子來說明一下UCC編譯器的寄存器分配，如圖6.2.1所示，第2至8行為函數f的代碼，第9至13行為函數g的代碼，在函數f第5行完成對s3的賦值後，我們有意在第6和第7行再次使用公共子表達式(a+b)和(c+d)。第32至46行是函數f對應的匯編代碼，而第48至58行是函數g對應的匯編代碼。

圖6.2.1 寄存器分配的例子

由圖6.2.1第15至23行的中間代碼，我們可以發現函數f中有3個臨時變量，每個都用於存放整數，共占用12字節的棧空間，第34行的“subl $12, %esp”用於在棧中開辟12字節內存來存放這3個臨時變量。雖然我們通過第36行的“movl a,%eax”指令，把全局變量a從內存載入寄存器eax中，但在執行第37行的“addl b,%eax”指令後，寄存器eax中保存的就是臨時變量“t0: a+b”的值，之後寄存器eax就一直分配給t0 ，直到t0不再被使用，或者寄存器不夠用時。可以發現，在第42行和第45行，我們都重用了保存於寄存器eax中的公共子表達式(a+b)，在第44行我們把“(a+b)+(c+d)”的值保存在寄存器edx中。與之形成對比的是在函數g的第57行，我們把“(a+b)+(c+d)”的值存於寄存器eax，其原因是在第57行後，基本塊BB1中不再使用第25行的臨時變量“t0: a+b”。

還需要注意的是，一條中間代碼可能對應若干條的匯編指令，例如圖6.2.1第16行的“t0:a+b;”就對應圖6.2.1第36和37這兩條匯編指令。

如果把寄存器分配的范圍擴大到有名的變量（即C程序員命名的全局、靜態和局部變量），還可進一步地減少內存的訪問次數。例如，當我們把全局變量a讀入某個寄存器R1後，之後再次需要a的值時，可直接由寄存器R1得到，不必再去訪問內存。但是由於C程序員既可通過變量名來訪問“有名的變量”，也可以通過變量的地址addr來間接訪問，其訪問方式比較靈活。如果通過*addr的形式來訪問全局變量a，我們可能會把a的值加載到另一個寄存器R2中，對全局變量a再進行寫操作時，就可能出現寄存器R1和R2中的內容不一致的問題。為了避免這樣的問題，編譯器需要做較復雜的分析。而臨時變量只由編譯器產生，對C程序員不可見，通常情況下，UCC編譯器只對臨時變量賦值一次，例如圖6.2.1第15至29行的臨時變量。不過有個例外，UCC編譯器在處理形如“a>0?b:c”的條件表達式時，確實會對臨時變量進行多次賦值，稍後我們會對此進行討論。

為了簡單起見，避免復雜的數據流分析，UCC編譯器只為臨時變量分配寄存器。接下來，我們來看一下用於分配寄存器的函數GetRegInternal，如圖6.2.2第2至18行所示，第2行的參數width代表所需要寄存器的寬度，可以是1字節（對應寄存器al、cl和dl），也可以2字節（對應寄存器ax,cx,dx,bx,si和di），還可以是4字節的寄存器（對應eax,ecx,edx,ebx,esi和edi）。第12行調用FindEmptyReg函數來獲取還未被分配的寄存器，如果不存在空寄存器，我們就要在第14行通過SelectSpillReg函數選擇一個要回寫的寄存器，再通過第15行的SpillReg函數將該寄存器中保存的值寫回內存，這樣該寄存器又可再次被分配。第17行在變量UsedRegs中設置相應的標志位，表示第i個寄存器已經被已經被使用。UCC編譯器在為一條中間代碼生成匯編指令前，都會先把變量UsedRegs清0，在稍後分析函數EmitBlock時，可以看到這一點。第1行的變量UsedRegs用於記錄“已經分配給當前中間代碼”的各個寄存器。

圖6.2.2 GetRegInternal()

圖6.2.2第19至28行的函數FindEmptyReg用於查找未被分配的寄存器，第22行的條件“X86Regs[i] !=NULL”會排除esp和ebp這兩個棧寄存器，第23行的條件表示寄存器中沒有保存臨時變量的值（空寄存器EmptyRegister），第24行的條件表示該寄存器還沒有分配給當前中間指令。若找不到空寄存器，則在第27行返回NO_REG。當所有寄存器都被分配完了，我們需要通過第29至48行的函數SelectSpillReg選擇一個要淘汰的寄存器。這很像請求分頁系統中的頁面置換算法，我們需要按FIFO或LRU等算法來淘汰一些頁面。UCC編譯器會根據“寄存器對應臨時變量的引用次數總和”來做選擇，回寫引用次數最少的寄存器，第32至45行對此進行處理。第48至58行的函數SpillReg會把保存在寄存器中的各臨時變量的值寫回內存，這個動作常被稱為“寄存器溢出”。圖6.2.2第52行的“p->needwb”不為0時，表示臨時變量p在寄存器和內存中的值已經不一致，而“p->ref > 0”表示臨時變量p還需要再次被使用，當這兩個條件都符合時，我們才會調用53行的StoreVar函數來產生寫內存的指令。當然，在目前版本的UCC編譯器中，一個寄存器通常只保存一個臨時變量的值，因此第38行和第50行這兩個while語句的循環體只執行一次。換言之，第37行的鏈表X86Regs[i]->link和第49行的鏈表reg->link上的元素個數都不會超過1個。第51行設置p->reg為NULL，表示臨時變量p的值不再保存在寄存器中。

為了加快浮點數的運算，Intel還提供了一個浮點協處理器X87，X87提供了由多個浮點寄存器構成的棧，但為了簡單起見，UCC編譯器實際上只使用位於棧頂的浮點數寄存器，來保存某個浮點數臨時變量。UCC編譯器中的指針變量X87Top用於指向該臨時變量，當X87Top不為NULL時，表示相應臨時變量的值保存在協處理器X87的棧頂。

static Symbol X87Top;

在此基礎上，我們來看一下“為基本塊產生匯編代碼”的函數EmitBlock，如圖6.2.3所示第1至24行所示，第3行的while循環會遍歷基本塊中的所有中間代碼，第10行調用的EmitIRInst函數實現了為中間代碼inst產生匯編指令的操作。由圖6.2.3第25至29行可發現，這是通過查表來實現相應函數的調用，第27行的表格Emitter中存放了形如第33行的EmitJump的函數名。第33至38行的EmitJump函數用於為無條件跳轉指令產生匯編代碼。

圖6.2.3 EmitBBlock()

雖然我們在中間代碼生成階段，只對同一基本塊內的公共子表達式進行重用，但在遇到條件表達式“(a>0?b:c)”時，確實存在“一個基本塊內的臨時變量，可能會在其他基本塊中被使用”的情況，如下所示，臨時變量t0會在多個基本塊中被賦值，當我們通過“gotoBB5”離開基本塊BB3時，我們需要回寫臨時變量t0的值。

d = (a>0?b:c)+1;

///////////////對應的中間代碼/////////////////

if (a <= 0) goto BB4;

BB3:

t0 = b; //對臨時變量t0的賦值

goto BB5;

BB4:

t0 = c; //對臨時變量t0的賦值

BB5:

t1 : t0 + 1;

d= t1;

因此，當控制流要通過跳轉語句離開基本塊，或者遇到函數調用時，我們要對寄存器進行回寫操作，圖6.2.3第8行調用的SaveX87Top用於回寫X87的棧頂寄存器，而對X86寄存器的回寫操作，我們將推遲到EmitJump、EmitBranch、EmitIndirectJump和EmitCall等函數中執行，分別對應“無條件跳轉”，“有條件跳轉”，“通過跳轉表進行跳轉”和“函數調用”。按C標准的規定，在函數調用時，主調函數只要回寫eax、ecx和edx這3個寄存器即可。而在遇到跳轉語句時，我們通過調用ClearRegs函數來回寫“eax、ebx、ecx、edx、esp和ebp”這6個寄存器，如圖6.2.3第37行所示。

函數SaveX87Top的代碼在圖6.2.3第48至57行，第53行調用的PutASMCode函數會產生浮點數的回寫指令，我們會在後續章節對PutASMCode函數進行分析，第56行置X87Top為NULL，表示已不存在需要回寫的臨時變量。

我們還發現，在控制流離開上述基本塊BB4時，我們也要把臨時變量t0的值寫回內存，這可通過圖6.2.3第22行調用的ClearRegs和第23行調用的SaveX87Top函數來實現。當我們在圖6.2.3第10行為一條中間代碼產生匯編指令後，可在第14至18行把各操作數的引用計數減1，這會對前文所述選擇溢出寄存器的SelectSpillReg函數產生影響。