1.前言

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

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

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

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

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

2.1 編譯原理的重要性

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

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

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

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

2.2 編譯原理理論

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

首先是源程序到抽象語(yǔ)法樹(shù)：

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

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

接下來(lái)是語(yǔ)義分析，語(yǔ)義分析是審查源程序有無(wú)語(yǔ)義錯(cuò)誤，為代碼生成階段收集類型信息。

從源程序到抽象語(yǔ)法樹(shù)的過(guò)程稱為編譯器前端。

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

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

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

下面是一條語(yǔ)句 i = j + k*10 編譯過(guò)程的具體實(shí)例：

3.GCC實(shí)踐

3.1 源碼閱讀心得

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

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

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

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

那是因?yàn)槲覀儎偨佑|開(kāi)源代碼的時(shí)候并不清楚它的數(shù)據(jù)結(jié)構(gòu)是如何設(shè)計(jì)的。

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

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

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

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

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.

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

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

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

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

3.3 GCC中的Generic

GCC中的Generic其實(shí)也是一種抽象語(yǔ)法樹(shù)（AST）。

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

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

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

GCC中的AST用聯(lián)合體（union）來(lái)表示即union tree_node。這是一個(gè)非常龐大的數(shù)據(jù)結(jié)構(gòu)，因?yàn)橐硎靖鞣N各樣的樹(shù)節(jié)點(diǎn)（例如聲明、標(biāo)識(shí)符、整型常量）。

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

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

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

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

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

struct tree_var_decl var_decl;

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

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

兩者交叉的部分為變量的類型，因?yàn)閍與b都是int類型，所以用指針指向同一個(gè)int類型節(jié)點(diǎn)。

變量a與變量b通過(guò)var_decl的chan字段以鏈的方式連接起來(lái)。

3.4 GCC中的GIMPLE

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

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

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

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

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

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

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

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

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

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

3.5 GCC中的RTL

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

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

RTL是下面這樣子的：

別以為是亂碼，剛開(kāi)始見(jiàn)的時(shí)候確實(shí)非常奇怪，但弄清楚之后非常簡(jiǎn)單。

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

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

用一張圖表示就是：

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

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

4 總結(jié)

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

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

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