1.前言

公司的一款編譯器是基于GCC寫的，最近測試發(fā)現(xiàn)了一個小bug。為了解決這個bug不得不對GCC源碼進行Debug，因此有了這篇文章。

本文結(jié)合編譯原理理論和GCC實踐做了一個總結(jié)，希望能給需要了解編譯原理和底層知識的同學(xué)一個更快的學(xué)習(xí)路徑。

除了GCC的文章之外，后續(xù)也會寫一些LLVM的文章，如果再有時間的話爭取將GCC中的編譯器算法和LLVM中的編譯器算法做一個對比總結(jié)。

希望看到這篇文章的朋友能持續(xù)關(guān)注本公眾號，如果沒有更新，肯定是研究代碼去了，研究完之后的心得會第一時間在公眾號分享出來，也希望能和更多的朋友一起交流，共同進步。

2. 編譯原理基礎(chǔ)

2.1 編譯原理的重要性

了解事物的本質(zhì)，是一件非常愉快的事情。

學(xué)習(xí)編譯原理好處：

• 可以更加容易理解在一個語言中哪些寫法是等價的，哪些是有差異的。
• 可以更加客觀的比較不同語言的差異
• 不容易被某個特定語言的宣揚者忽悠
• 學(xué)習(xí)更新的語言效率更高
• 從語言a到語言b是一個通用的需求，學(xué)好編譯原理會更加游刃有余
• 用編譯原理的眼光看自己的代碼，能夠?qū)懗鰞?yōu)秀的單元測試。
• 自己寫的程序更優(yōu)效率跟高
• 自創(chuàng)一門新的語言

編譯原理可以說是一個計算機科學(xué)的縮影，在學(xué)習(xí)寄存器分配中會使用到貪心算法，死代碼消除中會用到圖論算法，數(shù)據(jù)流分析中使用到Fixed-Point Algorithm，詞法分析和語法分析中會使用到有限狀態(tài)機和遞歸下降等重要思想?？梢娋幾g原理是值得學(xué)習(xí)的。

2.2 編譯原理理論

源程序到目標(biāo)代碼的過程要經(jīng)歷如下四個步驟：

首先是源程序到抽象語法樹：

需要經(jīng)歷詞法分析，也就是將程序中的一個一個字符按照單詞識別出來。

然后是語法分析，將詞法分析階段的單詞構(gòu)成短語，將短語以抽象語法樹的形式存儲起來。

接下來是語義分析，語義分析是審查源程序有無語義錯誤，為代碼生成階段收集類型信息。

從源程序到抽象語法樹的過程稱為編譯器前端。

中間代碼生成：中間代碼是與體系結(jié)構(gòu)無關(guān)的一種中間表示，形式接近于匯編代碼，中間代碼的目的是為了能生成各種體系結(jié)構(gòu)相關(guān)的目標(biāo)代碼但是只需要一套前端代碼。

目標(biāo)代碼生成：中間代碼到目標(biāo)代碼會經(jīng)過大量的代碼優(yōu)化，例如死代碼刪除、指令調(diào)度等。這個過程稱為編譯器后端。

編譯器后端是整個編譯器中最精華的地方，如果想要提升程序性能，研究編譯器后端算法絕對會讓你受益良多。

下面是一條語句 i = j + k*10 編譯過程的具體實例：

3.GCC實踐

3.1 源碼閱讀心得

程序 = 數(shù)據(jù)結(jié)構(gòu) + 算法

相信很多關(guān)心程序效率的同學(xué)都有這樣的體驗：

算法和數(shù)據(jù)結(jié)構(gòu)密不可分，一個高效的算法必然有合適的數(shù)據(jù)結(jié)構(gòu)作為支撐。高效的算法與合理的數(shù)據(jù)結(jié)構(gòu)同樣重要。

對于算法，通常仔細(xì)讀一讀論文就可以弄清楚原理，但是去看一些開源代碼具體實現(xiàn)的時候往往又一頭霧水。

那是因為我們剛接觸開源代碼的時候并不清楚它的數(shù)據(jù)結(jié)構(gòu)是如何設(shè)計的。

本文從GCC的數(shù)據(jù)結(jié)構(gòu)開始入手，為想要快速上手GCC的同學(xué)提供一個捷徑。

即使不關(guān)心GCC源碼，也可以從數(shù)據(jù)結(jié)構(gòu)設(shè)計中獲得啟發(fā)，畢竟合理的數(shù)據(jù)結(jié)構(gòu)和高效的算法一樣重要。

3.2 GCC整體結(jié)構(gòu)

我們通常認(rèn)為GCC是一個編譯器，然而官方的解釋是這樣的：

GCC is not a compiler.

GCC is a compiler collection that consists of three components.

A front end for each programming language, a middle end, and a back end for each architecture.

也就是說GCC是一個編譯器集合，支持多種語言和多種硬件架構(gòu)。

下圖是GCC的一個整體結(jié)構(gòu)圖

GCC整體結(jié)構(gòu)圖

圖中的綠色的部分Generic、GIMPLE、RTL是本文要介紹的，看懂這三個數(shù)據(jù)結(jié)構(gòu)之后離看懂GCC源碼基本就成功了一半。

3.3 GCC中的Generic

GCC中的Generic其實也是一種抽象語法樹（AST）。

從GCC整體結(jié)構(gòu)圖中我們可以看到，在Generic前面已經(jīng)生成了AST，為啥這兒的Generic也是一種AST呢？

原因是這樣的，從GCC整體結(jié)構(gòu)圖中我們可以看到，C語言會生成一種AST，C++也會生成一種AST，Java還會生成一種AST。這三種AST其實還是會有一些細(xì)微的差別，因此設(shè)計了一種通用的AST去統(tǒng)一所有的語言生成的AST，這個通用的AST就是Generic。

有了統(tǒng)一的AST后，就不用針對多種語言的AST寫多份code去生成目標(biāo)代碼。只需要針對統(tǒng)一的AST寫一份code去生成目標(biāo)代碼。

GCC中的AST用聯(lián)合體（union）來表示即union tree_node。這是一個非常龐大的數(shù)據(jù)結(jié)構(gòu)，因為要表示各種各樣的樹節(jié)點（例如聲明、標(biāo)識符、整型常量）。

將每一種節(jié)點統(tǒng)一到一個聯(lián)合體中的好處就是便于代碼閱讀和代碼的編寫與維護。

union tree_node
{
  struct tree_base base;
  struct tree_common common;
  ....
  //用于變量聲明，后面的例子中會用到
  struct tree_var_decl var_decl;
  //整形常量節(jié)點
  struct tree_int_cst int_cst;
  //標(biāo)志符節(jié)點
  struct tree_identifier identifier
  ....
}

上面的代碼是GCC中表示AST的樹節(jié)點。只列舉了部分，實際上是一個非常龐大的數(shù)據(jù)結(jié)構(gòu)。

int main()
{
  int a;
  int b;
}

以上面僅有兩個聲明的代碼為例，在GCC中使用

struct tree_var_decl var_decl;

表示變量a和變量b兩個聲明。其具體的表示如下：

如上圖所示對變量a的聲明為綠色方框部分，對變量b的部分為紅色方框部分。

兩者交叉的部分為變量的類型，因為a與b都是int類型，所以用指針指向同一個int類型節(jié)點。

變量a與變量b通過var_decl的chan字段以鏈的方式連接起來。

3.4 GCC中的GIMPLE

在GCC中很多前端處理并不包含AST到GENERIC的轉(zhuǎn)換，而是直接將AST轉(zhuǎn)換成與語言無關(guān)的另外一種中間表示，即GIMPLE。

從GCC整體框架圖可以看到，AST轉(zhuǎn)換成GIMPLE之后首先進行靜態(tài)單賦值(SSA), 然后進行各種優(yōu)化pass。

gimplify_function_tree是生成GIMPLE的入口函數(shù)。

其作用是通過掃描函數(shù)的AST，分別對函數(shù)的返回值、函數(shù)參數(shù)、函數(shù)中的變量以及函數(shù)體的語句序列進行處理，并將其轉(zhuǎn)換成對應(yīng)的GIMPLE序列。

gimplify_body函數(shù),對函數(shù)的內(nèi)容進行GIMPLE轉(zhuǎn)換。

gimplify_parameters對函數(shù)的參數(shù)列表進行GIMPLE轉(zhuǎn)換。

gimplify_stmt,函數(shù)體的GIMPLE生成是通過調(diào)用gimplify_stmt完成的。

gimplify_expr 函數(shù)是GIMPLE生成的核心函數(shù)，由gimplify_stmt調(diào)用。

另外一個需要注意的是，對于帶有操作數(shù)的GIMPLE語句，這些操作數(shù)的節(jié)點指針（類型為tree）將被連續(xù)存放在從該結(jié)構(gòu)體最后一個成員tree op[1]開始的連續(xù)地址中。

對與GIMPLE的介紹僅列出了相關(guān)的函數(shù)，是為了能夠快速的定位到GIMPLE生成的具體位置。想要了解更多細(xì)節(jié)，可以參考源碼。

3.5 GCC中的RTL

RTL 中文叫做寄存器傳輸語言（Register Transfer Language）。RTL是一種非常接近匯編指令的中間表示。RTL采用了類似LISP語言的列表形式，描述了每一條指令的語義動作。

剛接觸RTL的時候?qū)ζ浜x并不是太了解，導(dǎo)致代碼難理解，因此在這兒對RTL的含義進行簡要介紹，方便初學(xué)者能夠快速入門GCC。

RTL是下面這樣子的：

別以為是亂碼，剛開始見的時候確實非常奇怪，但弄清楚之后非常簡單。

其中set表示等號或者說是賦值，plus表示加法。SI表示寄存器存取的模式，SI表示該寄存器以32位整形的模式存取。

整個RTL的意思是：將寄存器139與寄存器138相加的值賦給寄存器140.

用一張圖表示就是：

其中的XEXP(x,0)是GCC源碼中用來取第一個操作數(shù)的代碼。

知道了RTL表示后閱讀源碼就會輕松許多，當(dāng)然還有一些細(xì)節(jié)沒有介紹，需要了解的可以后臺回復(fù)GCC，下載我收集的幾份比較好的國外PPT，再配合源碼看起來會方便很多。

4 總結(jié)

首先列舉了學(xué)習(xí)編譯原理的重要性以及編譯原理理論。

然后分享了源碼閱讀心得。程序等于數(shù)據(jù)結(jié)構(gòu)加算法，弄清楚數(shù)據(jù)結(jié)構(gòu)基本上成功了一半。因此本文對GCC的整體架構(gòu)和一些數(shù)據(jù)結(jié)構(gòu)做了簡要介紹，方便源碼閱讀。

最后介紹了開源編譯器GCC從抽象語法樹（AST）到匯編（ASM）的過程。主要是GCC用來表示抽象語法樹的Generic以及兩個中間表示GIMPLE和RTL。這個過程是逐漸從目標(biāo)硬件無關(guān)到目標(biāo)相關(guān)的過程。