gcc 的中間碼

編譯器gcc是GNU 工具的核心程式,除了可以編譯 C 語言之外,也提供將 C 語言轉換為組合語言的功能,甚至可以直接組譯組合語言,這些功能對學習系統程式有很大的幫助,因為gcc讓我們可以將編譯、組譯、連結等動作合併或分開進行,讓我們得以觀察許多中間過程,以便理解系統程式的編譯、組譯、連結等觀念。

在本節中,我們將示範如何使用 gcc 將 C 語言程式轉換成中間碼 ,如何利用進行跨平台的編譯,以及如何進行最佳化等動作。透過這樣的實作,讀者應該會對編譯器的實務有更進一步的理解。

中間碼與最佳化
在 2004 年之前,gcc 原本只採用了一層稱為 RTL 的中間碼,但是在 gcc 4.0 版之後,則將中間碼增加到三層,這三層的中間碼分別是Generic、Gimple 與 RTL中間碼,其中的 Generic代表剖析樹,Gimple 是高階中間碼,而 RTL 則是低階中間碼。因此,整個 gcc 的編譯過程大致上如圖 8.20所示。

圖 8.20 GNU 編譯器的流程

在圖 8.20當中,我們看到 GNU 用了『Generic、Gimple、RTL』等結構,這些結構通常儲存在編譯器當中而沒有被輸出,但是概念上這些結構都可以表示為某種中間碼,其中的 RTL 結構較為複雜,所以我們先將焦點集中在 Generic 與 Gimple 上。

範例 8.4顯示了 GNU 的 Generic 與 Gimple 結構的表示法,讀者可以看到Generic 結構其實是一種剖析樹的輸出格式,而 Gimple 則是某種四元組的中間碼格式。

範例 8.4 GNU 的Generic與 Gimple中間碼
(a) C (b) Generic (c) Gimple
if (foo(a+b, c)) {
c = b++ / a;
}
return c; if (foo (a + b,c))
c = b++ / a
endif
return c t1 = a + b
t2 = foo (t1, c)
if (t2 != 0) <L1,L2>
L1:
t3 = b
b = b + 1
c = t3 / a
goto L3
L2:
L3:
return c

當剖析動作完成之後,GNU 的剖析器會將剖析後的結果表達為 Generic 格式,Generic是一種和語言無關的剖析樹結構,舉例而言, GNU 工具當中其實包含了 C/C++/Obj C/Java 等編譯器,這些編譯器在剖析動作完成後,都會將成式轉換成 Generic 結構,然後再交由後續的程式碼產生器處理,因此 Generic 可以說是一種標準的語法樹結構。

當 GNU 的程式產生器接收到 Generic 語法樹之後,就會將語法樹轉換為 Gimple 中間碼,這個過程被 GNU 稱為 Gimplify。在 Gimplify 的過程當中,主要是將 for, while 等區塊結構,轉換為 if 與 goto 所組成的指令序列,接著,就可以進入最佳化的動作了。

Gcc 的最佳化動作有兩段,第一段是在將 Gimple 轉為 RTL 前,先用 Tree SSA optimizer 進行最佳化,第二段是在RTL轉回組合語言前,使用 RTL optimizer 進
行最佳化的動作。

Tree SSA optimizer 當中的 SSA 是靜態單一賦值 (Static Single Assignment) 的意思,其意義是將一個變數分為很多的版本,每個版本只能被指定一次,舉例而言,假如將 x 變數分為 x1, x2, ….xn,那麼每個變數 xi 就可以只被用 xi=y 指定一次。

當一個 Gimple 中間碼被轉換成 SSA 形式,也就是為每個變數加上版本時,只要能利用最佳化程式,降低變數的版本數量,就能達到減少載入指令的功能,達到最佳化的效果。

接著,RTL generator 會將轉換成 SSA 形式的 Gimple 中間碼,進一步轉換為 RTL 中間碼,然後再利用 RTL optimizer 進行最佳化動作。RTL 是一種形式較為複雜的中間碼,主要的功能是為每個變數加上型態的描述,舉例而言,當範例 8.5 (a)的 Gimple 指令 b = a-1 被轉換成 RTL 時,會轉換成範例 8.5 (b) 中的形式,這個形式看起來複雜了許多,但實際上並沒有那麼難懂,讓我們稍做說明,您就可以輕易的看懂 RTL 中間碼了。

範例 8.5 中間碼Gimple 與 RTL 之對照範例
(a) Gimple (b) RTL (c) 簡化後的 RTL
b = a – 1 (set (reg/v:SI 59 [ b ])
(plus:SI (reg/v:SI 60 [ a ]
(const_int -1 [0xffffffff])))) b (59,reg/v:SI) =
a (60, reg/v:SI) +
-1 (const_int)

RTL 當中的 set 代表指令陳述 =,plus 代表加法運算,reg/v 代表該變數可以存在暫存器 (register) 或記憶體 (variable) 中,而 SI 則代表常度為 4bytes 的整數 (Single Integer)。因此範例 8.5 (b) 的整個段落,可以轉換為範例 8.5 (c) 的 Gimple 式寫法如下。

b (59,reg/v:SI) = a (60, reg/v:SI) + -1 (const_int)

這種寫法應該簡單多了,也就是將 b, a, 與 -1 等符號,加上代號與類型限制,舉例而言,b (59,reg/v:SI) 這個句子,代表 b 是編號 59 號的變數,可以被儲存在暫存器或記憶體當中,而且其形態為 4bytes 的整數。

我們可以利用 –dr 參數,要求 gcc 編譯器輸出 rtl 中間碼,以下是筆者的操作過程,您可以看到其中的 sum.c.01.rtl 檔案被產生出來,該檔案就是 RTL 中間碼。

指令與操作過程 說明
C:\ch08>gcc -c -dr sum.c -o sum.o

C:\ch08>dir

2010/03/12 上午 09:00 105 sum.c
2010/04/09 上午 09:29 3,784 sum.c.01.rtl
2010/04/09 上午 09:29 372 sum.o
3 個檔案 4,261 位元組
3 個目錄 9,196,593,152 位元組可用

RTL 中間碼檔案
由於RTL 的中間碼很冗長,在此我們只列出其中的一小段片段,我們並不嘗試解讀這個 RTL 檔案,請有興趣的讀者使用 gcc 指令產生 RTL 檔後自行研究其內容。

(a) C 語言程式 (b) 對應的RTL 檔案
int sum(int n) {
int s=0;
int i;
for (i=1; i<=n;i++) {
s = s + i;
}
return s;
} (note 2 0 3 NOTE_INSN_DELETED)

(insn 8 6 11 (set (mem/f:SI (plus:SI (reg/f:SI 54 virtual-stack-vars)
(const_int -4 [0xfffffffc])) [0 s+0 S4 A32])
(const_int 0 [0x0])) -1 (nil)
(nil))

(jump_insn 16 15 17 (set (pc)
(if_then_else (gt (reg:CCGC 17 flags)
(const_int 0 [0x0]))
(label_ref 30)
(pc))) -1 (nil)
(nil))

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License