---
GA: G-B8G2L9X80S
---
# Ch2 編譯和鏈接
[toc]
:::info
這章節主要在講編譯流程、編譯器、鏈接器的概念
:::
在日常開發過程中，我們很少需要關注編譯和鏈接過程，通常 IDE 都幫你搞定了，往往只需要按一下 Build，執行檔就建構出來了。但正是如此，才有很多的 compiler 或 linker error 讓我們無所適從，這些錯誤信息有時候晦澀難懂，讓我們難以迅速定位和解決問題。或是程式執行的效能瓶頸我們束手無策。
我們只看到問題的現象，而很難看清本質，這些問題的本質就是軟體運行背後的機制，和支撐軟體運行的平台和工具，唯有了解這些機制細節，才能在面對這些問題時得心應手。
## 2.1 被隱藏的過程
一個簡單的 `"Hello, World"` 可以透過編譯執行它，來測試開發環境
```c
#include <stdio.h>
int main()
{
printf("Hello, World\n");
return 0;
}
```
在 Linux 下使用 gcc 編譯我們的 `hello.c` 只需要一個指令，如下:
```
$ gcc hello.c
$ ./a.out
Hello, World
```
但其實整個過程可以分成四個步驟，如下所示
1. 預處理(Preprocessing)
2. 編譯(Compile)
3. 組譯(Assemble)
4. 鏈接(Linking)
這章會分別介紹這幾個步驟的細節
### 2.1.1 預處理(Preprocessing)
預處理如其名，就是在正式編譯前的處理，用於處理所有 `#` 開始的 macro 指令: 例如 `#include <stdio.h>` 等，被 `cpp` Preprocessor 給 preprocess 成 `.i` 檔案，C++ 叫 `.ii` 檔案，可以使用 gcc 的 `-E` 指令只進行預編譯:
```bash
$ gcc -E hello.c -o hello.i
# 或是
$ cpp hello.c > hello.i
```
Preprocessor 主要處理以下規則:
- 替換展開所有 `#define`
- 處理條件編譯 `#if`, `#ifdef`, `#elif`, `#else`, `#endif`
- 處理 `#include` 預編譯指令，將包含的檔案內容剪貼到該預編譯指令的位置
- 是 recursive 的，意思是被 include 的檔案可能 include 其他檔案
- 刪除註解 `//` 和 `/* */`
- 添加行號和檔案名標記，例如 `#2 "hello.c" 2`，方便 debugging 和 compiler error 時可以顯示行號
- 保留compiler 會用到的 `#pragma` compiler 指令
預編譯後的 `.i` 檔案都沒有 macro 了，包含的檔案也被複製進檔案中，當無法判斷是 `#define` 正確、或是 header file 是否有正確 include 時，可以檢查 preprocess 後的檔案。
### 2.1.2 編譯(Compile)
編譯就是將預處理完的檔案，經編譯器流程產生組語檔案的流程，是程式建構中最複雜的部份，可以使用 gcc 的 `-S` 指令只進行編譯步驟:
```bash
$ gcc -S hello.i -o hello.s
```
現在的 gcc 版本把 preprocess 和 compile 合成同一個步驟 `cc1`，在 `/usr/lib/gcc/x86_64-linux-gnu/9/cc1` 也可以使用這個指令
```
$ /usr/lib/gcc/x86_64-linux-gnu/9/cc1 hello.c
main
Analyzing compilation unit
Performing interprocedural optimizations
<*free_lang_data> <visibility> <build_ssa_passes> <opt_local_passes> <remove_symbols> <targetclone> <free-fnsummary>Streaming LTO
<whole-program> <hsa> <fnsummary> <inline> <free-fnsummary> <single-use> <comdats>Assembling functions:
<materialize-all-clones> <simdclone> main
Time variable usr sys wall GGC
phase setup : 0.00 ( 0%) 0.00 ( 0%) 0.01 ( 9%) 1222 kB ( 70%)
phase parsing : 0.01 (100%) 0.01 (100%) 0.05 ( 45%) 458 kB ( 26%)
phase opt and generate : 0.00 ( 0%) 0.00 ( 0%) 0.04 ( 36%) 56 kB ( 3%)
preprocessing : 0.00 ( 0%) 0.00 ( 0%) 0.04 ( 36%) 136 kB ( 8%)
lexical analysis : 0.00 ( 0%) 0.00 ( 0%) 0.01 ( 9%) 0 kB ( 0%)
parser (global) : 0.01 (100%) 0.01 (100%) 0.00 ( 0%) 307 kB ( 18%)
LRA non-specific : 0.00 ( 0%) 0.00 ( 0%) 0.01 ( 9%) 0 kB ( 0%)
initialize rtl : 0.00 ( 0%) 0.00 ( 0%) 0.02 ( 18%) 12 kB ( 1%)
rest of compilation : 0.00 ( 0%) 0.00 ( 0%) 0.01 ( 9%) 2 kB ( 0%)
TOTAL : 0.01 0.01 0.11 1746 kB
```
C 語言要用 `cc1` 編譯，C++ 用 `cc1plus`，ObjectiveC 是 `cc1obj` 等，gcc 只是包裝了這些命令列程式，實際上會去呼叫編譯 `cc1`, 組譯 `as`, 鏈接 `ld`。
### 2.1.3 組譯(Assemble)
組譯器(Assembler)是將組合語言變成機器碼的工具，每條 assembly 都對應一條機器指令，所以組譯器比較簡單，照翻就好。
可以使用 `as` 或是 `gcc -c` 來調用組譯器進行組譯產生 Object File:
```
$ as hello.s -o hello.o
# or
$ gcc -c hello.s -o hello.o
```
### 2.1.4 鏈接(Linking)
Linking 是將一個或多個 object file 和 library 組合成一個 executable 的過程。其目的是整合程序的各個部分，解決符號引用，最終產出 executable。
下面範例示範了如何使用 `ld` 指令列來鏈接剛才組譯出來的 `hello.o` 產生可執行的 `a.out`
```bash
$ ld -static \
/usr/lib/x86_64-linux-gnu/crt1.o \
/usr/lib/x86_64-linux-gnu/crti.o \
/usr/lib/gcc/x86_64-linux-gnu/9/crtbeginT.o \
-L/usr/lib/gcc/x86_64-linux-gnu/9/ \
-L/usr/lib \
-L/lib \
hello.o \
--start-group \
-lgcc -lgcc_eh -lc \
--end-group \
/usr/lib/gcc/x86_64-linux-gnu/9/crtend.o \
/usr/lib/x86_64-linux-gnu/crtn.o
```
至於上面範例 link 的 object file 各自代表什麼意思，ch11 會說明。
## 2.2 編譯器做了什麼
編譯器是將高階語言翻譯成機器語言的工具。例如，用 C/C++ 語言寫的程序使用編譯器翻譯成機器可以執行的指令和數據。
組合語語寫程式費時費力，開發效率低下，且不具可移植性，換 CPU 就得重寫。 高階語言使得開發者們能夠更專注於邏輯的本身，而減少了考慮計算機本身的限制，提高開發效率，具可移植性。
編譯器可以分成 6 大步驟，下圖展示了程式從 source code 到產出 object file 的流程
下面小節會以範例C程式說明各個步驟的細節
```c
array[index] = (index + 4) * (2 + 6)
```
### 2.2.1 詞法分析(Lexical Analysis)
程式碼被輸入到掃描器(Scanner)，用有限狀態機(Finite State Machine)的算法將字串分割成一連串的**記號(Token)**，如以下，掃描了 28 個字元，產生了 16 個 token:
| 記號 | 類型 |
|-------|--------|
| `array` | 標識符 |
| `[` | 左方括號 |
| `index` | 標識符 |
| `]` | 右方括號 |
| `=` | 賦值 |
| `(` | 左圓括號 |
| `index` | 標識符 |
| `+` | 加號 |
| `4` | 數字 |
| `)` | 右圓括號 |
| `*` | 乘號 |
| `(` | 左圓括號 |
| `2` | 數字 |
| `+` | 加號 |
| `6` | 數字 |
| `)` | 右圓括號 |
產生出的 Token 可以分成幾類: 關鍵字、識別碼(identifier)、常值(literal)和特殊符號(加號、等號)。掃描器在掃瞄也會做其他事: 將找到的 identifier 放到符號表，數字、字串記錄到文字表等。
有個叫 `lex` 的程式可以做詞法分析，開發者可以輸入詞法規則，產生詞法分析器(Lexer)，這樣編譯器開發者就不用自己寫一個 Lexer，而只要維護詞法規則就好。
預處理通常是獨立的預處理器負責，在編譯階段之前就會完成。
### 2.2.2 語法分析(Syntactic Analysis)
語法分析器(Grammar Parser)對 lexer 產出的 token 進行語法分析，產生語法樹(Syntax Tree)。分析過程使用了上下文無關語法(Context-free Grammar)的方法。
由 Parser 產生的語法樹是以表達式(Expression)為節點，範例中的 C 程式轉成語法樹後，就如下圖:
```graphviz
graph SyntaxTree {
node [shape=box];
Assign_Expression [label="Assign Expression\n="];
Subscript_Expression [label="Subscript Expression\n[]"];
Multiplicative_Expression [label="Multiplicative Expression\n*"];
Identifier_array [label="Identifier (Expression)\narray"];
Identifier_Index1 [label="Identifier (Expression)\nIndex"];
Identifier_Index3 [label="Identifier (Expression)\nIndex"];
Number_4 [label="Number (Expression)\n4"];
Number_2 [label="Number (Expression)\n2"];
Number_6 [label="Number (Expression)\n6"];
Additive_Expression1 [label="Additive Expression\n+"];
Additive_Expression2 [label="Additive Expression\n+"];
Assign_Expression -- Subscript_Expression;
Assign_Expression -- Multiplicative_Expression;
Subscript_Expression -- Identifier_array;
Subscript_Expression -- Identifier_Index1;
Multiplicative_Expression -- Additive_Expression1;
Multiplicative_Expression -- Additive_Expression2;
Additive_Expression1 -- Identifier_Index3;
Additive_Expression1 -- Number_4;
Additive_Expression2 -- Number_2;
Additive_Expression2 -- Number_6;
}
```
從上圖可以看出，整個語句式一個賦值表達式: 左邊是陣列表達式，右邊是乘法表達式。陣列表達式是兩個符號表達式組成的。符號和數字是最小的表達式，通常在 leaf node。
在語法分析的同時，運算符號的優先級和含義也確定了，乘法的優先級比加法高；括號的優先級比乘法高。另外，符號可能有多重含義，`*` 在 C 語言中可以表示乘法，也可以表示 pointer dereference。在語法分析時要區分這些東西，如果有表達式不合法 e.g. 括號不匹配、表達式缺少操作符，就會返回錯誤。
語法分析也有工具 `yacc` (Yet Another Compiler Compiler)，開發者可以輸入語法規則，就可以產生一個 parser，compiler 開發者只要維護與法規則，不用自己寫一個 parser。
### 2.2.3 語意分析(Semantic Analysis)
語意分析器(Semantic Analyzer)負責這一階段，語法分析只對表達式針對語法的分析，但它不了解語句是否真的具有意義。 例如 C 語言中兩個指標做乘法運算是沒有意義的，但在語法上是合法的。
編譯器能分析的語意是**靜態語義(Static Semantic)**，在 compile-time 可以確定的語義；對應的是**動態語義(Dynamic Semantic)**，只有 run-time 才能確定的語義。
靜態語義通常包含: 宣告、型別的匹配、型別的轉換。例如把一個浮點數的表達是賦值給整數表達式，會隱含一個轉型。或是把一個浮點數賦值給指標時，語意分析器會發現類型不匹配，導致噴錯。
動態語義通常是執行期出現的問題，例如把數字除以 0。
經過語意分析後，整個語法樹都被標上型別(Type)，如果需要轉型，會插入轉換節點，如下圖:
```graphviz
graph {
node [shape=box]
A [label=<Assign<br/>Expression =<br/><b>integer</b>>]
B [label=<Subscript<br/>Expression []<br/><b>integer</b>>]
C [label=<Multiplicative<br/>Expression *<br/><b>integer</b>>]
D [label=<Identifier<br/>array<br/><b>array of integer</b>>]
E [label=<Identifier<br/>index<br/><b>integer</b>>]
F [label=<Additive<br/>Expression +<br/><b>integer</b>>]
G [label=<Identifier<br/>index<br/><b>integer</b>>]
H [label=<Number<br/>4<br/><b>integer</b>>]
I [label=<Additive<br/>Expression +<br/><b>integer</b>>]
J [label=<Number<br/>2<br/><b>integer</b>>]
K [label=<Number<br/>6<br/><b>integer</b>>]
A -- B
A -- C
B -- D
B -- E
C -- F
C -- I
F -- G
F -- H
I -- J
I -- K
}
```
### 2.2.4 中間語言生成(Intermediate Code Generation)
現代的編譯器對程式有很多優化，在 source code 等級優化的 Source Code Optimizer。例如，範例的 `(2 + 6)` 這個表達式可以被優化掉，因為它的值在編譯期就可以確定了，如下圖:
```graphviz
graph {
node [shape=box]
A [label=<Assign<br/>Expression =<br/><b>integer</b>>]
B [label=<Subscript<br/>Expression []<br/><b>integer</b>>]
C [label=<Multiplicative<br/>Expression *<br/><b>integer</b>>]
D [label=<Identifier<br/>array<br/><b>array of integer</b>>]
E [label=<Identifier<br/>index<br/><b>integer</b>>]
F [label=<Additive<br/>Expression +<br/><b>integer</b>>]
G [label=<Identifier<br/>index<br/><b>integer</b>>]
H [label=<Number<br/>4<br/><b>integer</b>>]
J [label=<Number<br/>8<br/><b>integer</b>>]
A -- B
A -- C
B -- D
B -- E
C -- F
C -- J
F -- G
F -- H
}
```
優化直接做在語法樹上比較困難，所以通常會把語法樹轉成**中間碼(Intermediate Code)**。中間碼是和目標機器以及執行期環境是無關的，其不包含資料的大小、變數地址、暫存器名字等，不同的編譯器有不同的中間語言，常見的有: 三位址碼(Three-address Code) 和 P-code。
簡單的三位址碼如以下: 表示將變數 `y` 和變數 `z` 進行 `op` 操作後，賦值給 `x`，`op` 可以是算數運算、或其他可以應用到 `y` 和 `z` 的操作。
```
x = y op z
```
上面例子的語法樹可以轉成以下三位址碼: 所有操作都符合三位址碼的形式
```
t1 = 2 + 6
t2 = index + 4
t3 = t2 * t1
array[index] = t3
```
上面用到了三個暫時變數: `t1`, `t2`, `t3`，在優化後 `t1 = 8` 並可以重複利用 `t2` 省去一個暫時變數:
```
t2 = index + 4
t2 = t2 * 8
array[index] = t2
```
中間碼使得 compiler 可以被劃分成前端和後端: 前端負責產生中間碼，後端將中間碼轉換成目標機器碼，方便維護編譯器。
### 2.2.5 目標程式碼生成與優化(Code Generation & Optimization)
這個階段屬於編譯器後端，包含了程式碼生成器(Code Generator) 和目標程式碼優化器(Target Code Optimizer)。
程式碼生成器負責將中間碼轉換成目標機器碼，不同的機器有不同的 word size, reigster, int, float 等
例如上面例子的中間碼，經過轉換後會生成以下 x86 組語
```asm=
mov ecx, index ; ecx = index
add ecx, 4 ; ecx += 4
imul ecx, ecx, 8 ; ecx *= 8
mov eax, index ; eax = index
mov DWORD PTR array[eax*4], ecx ; *(eax*4) = ecx
```
接著目標程式碼優化器針對上面的組語進行優化，例如: 使用合適的尋址方式、使用 bit shift 來代替乘法、刪除多於指令等。
```
mov edx, index ; edx = index
lea eax, [edx*8 + 32] ; eax = edx*8 + 32
mov DWORD PTR array[edx*4], eax ; *(edx*4) = eax
```
上面的組語中，乘法是用 Base Index Scale Addressing 的 `lea` 指令完成，可以發現指令的數量變少了，仍然達成同樣功能。
現代編譯器非常複雜，因為語言本身就非常複雜: 例如 C++，世界上沒有一款編譯器是能夠完整支援 C++ 標準規定的所有特性。
現代計算機的 CPU 也非常複雜: 流水線(Pipeline)、多發射(Multiple Instruction Issue)、超純量(Superscalar)等特性，為了支援這些特性，編譯器的優化就變得非常複雜，如果編譯器支援不同架構平台，會讓 codegen 部分變得更複雜。
經過這麼多步驟產生了目標機器碼，但還有個未確定的東西，`index` 和 `array` 的地址還沒確定，如果這兩個變數的定義是寫同個編譯單元內，那 compiler 可以處理，但如果變數的定義是寫**不同**編譯單元內，就得在最後鏈接(Linking)時才能確定。
所以編譯器產生目標檔，鏈接器把目標檔鏈接成可執行檔案。
## 2.3 Linker 歷史比 Compiler 久遠
最早的電腦很原始，甚至連 assembly 都沒有，得直接寫機器碼，開發者在撰寫程式，往往會修改，此時就會遇到問題: 程式中有跳轉的目標位址，會因為程式修改(少掉 or 多出指令)導致目標位址產生變動。
開發者需要重新計算每個子程式或跳轉的目標地址，每次修改都需要重新計算，這種重新計算個個目標地址的過程就叫做 **重定位(Relocation)**。
人工修改肯定是沒有辦法的，後來就有人發明了 assembly，使用了文字符號來代表機器碼，例如 `jmp` 就是跳轉指令，而不是 `0001XXXX` 這種機器碼。而且 assembly 還可以用符號來標記位置，例如可以用 `divide` 表示除法 subroutine 的位址，而不是記從某某位置開始的 n 條指令是除法來得方便許多。
用符號標記位置，也使得開發者不用指定具體的指令位址，而是用符號來代替，例如 `jmp foo` 代表要跳轉到 `foo` 符號上。這樣不管 `foo` 的之前插入或刪除多少指令，使得它的位址受影響，但只要 assembler 在產生機器碼時，重新計算 `foo` 的地址，然後把所有引用 `foo` 符號的地方，都修正到新的地址，將整個過程自動化，解放了生產力。
**符號(Symbol)** 這個用來表示地址的概念迅速普及，它可以用來表示一個地址，可以是一個 subroutine 的起始位址、或是一個變數的位址。
隨著生產力的提高，軟體的規模也開始龐大了起來，開發者開始把程式碼以功能或性質劃分，形成不同的功能模塊，像 C 語言最小的單位是 variable 和 function，數個 variable 和 function 組成一個 module，放在一個 `.c` 檔裏頭，這些 `.c` 檔用目錄結構來整理。
現代的大型軟體擁有很多個模塊，各個模塊間相互依賴，好處是程式容易閱讀理解、重用，模塊可以單獨開發、編譯、測試，改變部分程式碼不用重新編譯整個程式。
程式在分割成模塊後，如何組合回去一個單一的程式? 怎麼組合其實就是模塊間如何通訊的問題。C/C++ 有兩種方式: 模塊間的 function 呼叫，以及模塊間的 variable 存取。 兩者都需要知道目標對象的地址，總結就是模塊間符號的引用，如下圖，拼圖的拼接就是 Linking 的過程。
## 2.4 Static Linking
開發者把各個模塊獨立編譯，然後把它們組裝起來，這個組裝的過程就是 **鏈接(Linking)**: 將各個模塊之間 Symbol 相互引用部分都處理好，使得各個模塊能夠正確合在一起，主要包含了 **地址和空間分配(Address and Storage Allocation)、符號決議(Symbol Resolution)、重定位(Rellocation)** 等。
## 2.5 Summary
Sign in with Wallet
Connect another wallet