1.前言

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

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

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

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

2. 編譯原理基礎

2.1 編譯原理的重要性

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

學習編譯原理好處：

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

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

2.2 編譯原理理論

源程序到目標代碼的過程要經歷如下四個步驟：

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

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

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

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

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

中間代碼生成：中間代碼是與體系結構無關的一種中間表示，形式接近于匯編代碼，中間代碼的目的是為了能生成各種體系結構相關的目標代碼但是只需要一套前端代碼。

目標代碼生成：中間代碼到目標代碼會經過大量的代碼優化，例如死代碼刪除、指令調度等。這個過程稱為編譯器后端。

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

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

3.GCC實踐

3.1 源碼閱讀心得

程序 = 數據結構 + 算法

相信很多關心程序效率的同學都有這樣的體驗：

算法和數據結構密不可分，一個高效的算法必然有合適的數據結構作為支撐。高效的算法與合理的數據結構同樣重要。

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

那是因為我們剛接觸開源代碼的時候并不清楚它的數據結構是如何設計的。

本文從GCC的數據結構開始入手，為想要快速上手GCC的同學提供一個捷徑。

即使不關心GCC源碼，也可以從數據結構設計中獲得啟發，畢竟合理的數據結構和高效的算法一樣重要。

3.2 GCC整體結構

我們通常認為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是一個編譯器集合，支持多種語言和多種硬件架構。

下圖是GCC的一個整體結構圖

GCC整體結構圖

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

3.3 GCC中的Generic

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

從GCC整體結構圖中我們可以看到，在Generic前面已經生成了AST，為啥這兒的Generic也是一種AST呢？

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

有了統一的AST后，就不用針對多種語言的AST寫多份code去生成目標代碼。只需要針對統一的AST寫一份code去生成目標代碼。

GCC中的AST用聯合體（union）來表示即union tree_node。這是一個非常龐大的數據結構，因為要表示各種各樣的樹節點（例如聲明、標識符、整型常量）。

將每一種節點統一到一個聯合體中的好處就是便于代碼閱讀和代碼的編寫與維護。

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

上面的代碼是GCC中表示AST的樹節點。只列舉了部分，實際上是一個非常龐大的數據結構。

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

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

struct tree_var_decl var_decl;

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

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

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

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

3.4 GCC中的GIMPLE

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

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

gimplify_function_tree是生成GIMPLE的入口函數。

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

gimplify_body函數,對函數的內容進行GIMPLE轉換。

gimplify_parameters對函數的參數列表進行GIMPLE轉換。

gimplify_stmt,函數體的GIMPLE生成是通過調用gimplify_stmt完成的。

gimplify_expr 函數是GIMPLE生成的核心函數，由gimplify_stmt調用。

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

對與GIMPLE的介紹僅列出了相關的函數，是為了能夠快速的定位到GIMPLE生成的具體位置。想要了解更多細節，可以參考源碼。

3.5 GCC中的RTL

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

剛接觸RTL的時候對其含義并不是太了解，導致代碼難理解，因此在這兒對RTL的含義進行簡要介紹，方便初學者能夠快速入門GCC。

RTL是下面這樣子的：

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

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

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

用一張圖表示就是：

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

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

4 總結

首先列舉了學習編譯原理的重要性以及編譯原理理論。

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

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