---
title: 編譯器_最佳化
tags: C 語言筆記
---
## 編譯器_最佳化
### GUN/Linux 程式執行流程
* Shell 執行 ./hello 時會先呼叫 fork + execve 來讓核心準備建立程序
* 當 kernel 準備好執行檔的空間後，就會依據執行檔載入對應的動態連結器並載入對應的動態函式庫 (以上圖為例就是 libc.so)
* libc.so 中的 libc_start_main 會在執行檔中找尋 C 語言程式的進入點 (main) ，並由此開始執行程式
* 如果是靜態連結則配置好程序的空間後就會直接去找進入點
* 程式結束時再呼叫 exit
### 編譯程式的流程
* 預處理 (pre-processing)
* 刪除所有的 #define 並展開所有 macro
* 處理所有的預編譯條件，例如 #ifdef 、 #include
* 刪除所有 註解
* 增加行號以及文件識別名，讓編譯器在編譯失敗時可以顯示錯誤的行數
* 編譯 (compilation)
* Lexical Analyzer(scan):
* 目的為將程式碼的序列分割成一連串的 token，並將這些 token 分類
* 舉例來說， ```a = 3 + 5``` 這段程式碼是由六個 token 所組成
* ```a``` 為標示符，```=``` ```+``` ```;``` 為特殊符號，```3``` ```5``` 為常量
* Syntax Analyzer(parsing)
* 有了這些 token 之後，就可以組出對應的文法樹 (syntax tree)
* Semantic Analysis
* syntax-directed translation
* 接下來要判斷語意的正確性，比如說我們允許兩個常量相乘，但不允許對兩個指標做相乘。而語意又可分成```靜態語意```以及```動態語意```，靜態語意是編譯器可以在```編譯期```分析的，並且回報錯誤，例如：型態的轉換否正確。而動態語意則是在```執行期```相關的，例如：以零當作除數是一個執行期的語意錯誤
* 文法樹上加上語意型別
* 代碼優化 (source code optimization)
* 代碼生成與優化 (code generation and optimization)
* 產生組合語言
* 最佳化下面會提到
* 彙編 (assembly)
* 組合語言轉換成對應的機器語言，只要根據對照表翻譯即可
* 產生目標文件檔(.o/.obj)，目標文件檔遵循可執行文件格式 (ELF) 來儲存
* 鏈接 (linking)
* 使編譯器能夠知道代碼中外部函數或是外部變數明確的位址
* 每個被定義的變量都應該要有一個獨一無二的名稱，引用的時候才不會跟其他變量混淆。我們將變量或函數通稱為符號 (symbol)，而他們的名稱則稱為符號名 (symbol name)，記錄在符號表 (symbol table) 中
* 在編譯期轉成組合語言時，用 symbol 來代替變數，但是我們並不知道這些 symbol 真正的位址。當最後將代碼轉成機器語言時，我們會先賦予這些符號一個假的位址，並且用一個重定位表(relocation table)去記錄有哪些符號的位址是假的，之後需要再次修改
* 統整:
* 預編譯 (pre-processing) 展開文件內的定義與預編譯，並刪除不必要的部份
* 編譯 (compilation) 將代碼編譯並優化成組合語言
* 彙編 (assembly) 將組合語言轉成機器語言，轉成目標文件
* 鏈結 (linking) 透過目標文件內的資訊來分配空間以及確定符號的確切位址
* 重點複習: [Re-introduction to Compiler](http://slide.logan.tw/compiler-intro/#/2)
* 編譯器術語
* Basic Block: 單一進入點、單一出口點的程式區段
* CFG(Control Flow Graph): BB組成的程式流程圖
* IR(Intermediate Representation)
* 引入 IR 可以更容易支援前端(ex: C++、python等語言)、後段(不同arm、mips、intel架構)
### 最佳化技巧
* Code Motion(程式碼搬移)
* 有些運算可提前執行，加速運算
* Pointer Aliasing: 程式碼搬移可能會再成的問題，當兩個指標指到同一個記憶體位置時，下圖的a、b、y若只到同一個位址便會出錯
* 可以用
* Data-flow analysis(程式資料流分析)
* 用來判斷兩個指令是否可以交換位置(是否有相依性)
* 判斷轉型是否會有問題
* 判斷迴圈正常運作
* Control-flow analysis(控制流分析)
* 寫了function沒被用到
* 迴圈無窮循環
* function 相依性
* Memory dependence analysis
* 例如前面提到的指標問題
* Static Single Assignment(SSA form)
* 每個被 Assign 的變數只會出現一次
* 將被 Assign 的變數給一個版本號碼，再使用 $\Phi$ function 例如: $ret3=\Phi(ret1, ret2)$ 去判斷從何而來
* SSA 把原本複雜的條件和程式邏輯轉化為 Graph，用讓每個程式邏輯轉成明確的路徑
* SSA 最佳化實例：
```c=
int main()
{
int a = 11, b = 13, c = 5566;
int i, result;
for (i = 0; i < 1000; i++)
result = (a*b + i) / (a*c);
return result;
}
```
* 步驟(p36~p47)
1. 先拆成 basic blocks (單行的指令, 沒有jump or label)
2. 合併 basic blocks
3. 最佳化 CFG (減少 goto ) & 轉成 3-address code
4. 轉成 SSA form (變數加版本號以及 runtime decided 時, 用函數表示, 並給新的版本號) . 例: $i1=\Phi(i0,i2)$
5. constant propagation (變數換成常數)
6. dead code elimination (remove 不需要的變數)
7. value range propagation (變數用一個範圍的常數來代替，測試一些極端數值)
8. dead code elimination (結果步驟7發現輸出都是為0: 直接 return 0)
### GCC
* 流程
* 前端: 1. Source -> 2. AST(Abstract Syntax Tree)
* 中端: 3. Gimple IR -> 4. Tree SSA form
* 後端: 5. RTL(Register Transfer Language) IR(用 S-expression 表達) -> 6. Final ASM
* 前端: 辨識C/C++ 原始程式碼，並轉成 parsing tree
* 中端:
* Gimple 來自 Generic Gimplify
* 限制每個運算只能有兩個運算元(3-Address IR, ex: t1 = A op B)
* Gimple 再經過 SSA Optimizer
* 後端:
* RTL(Register Transfer Language): 依照目的端架構分配暫存器
* RTL 使用 virtual Register(有無限多個)
* Register Allocation: 轉換到目的端的有限暫存器
* Register Allocation 因為維護上的困難而發展成 IRA(Integrated Register Allocator, 整合 Coalescing、Live range splitting 以及挑選較好的 Hard register 的作法)
* 暫存器分配 是一個 著色問題: 對於不同的平台都會有特殊的指令或情況導致暫存器的使用限制(可以查banked register來看)
* Instruction scheduling:
* 考慮到 pipeline scheduling: 如何排列指令，使程式在最短時間內可以執行作多道指令
* Peephole optimization
* 以管窺天最佳化法
* 一次看一小部分IR(中間表示程式碼)，並做最佳化
ex: 三行變成兩行
* GCC built-in operation & architecture-defined operation
* GCC 為了最佳化，會辨識一些常用的標準函式改成 built-in function，比如:
* 字串處理，ex: strcpy -> 改用 x86 字串處理指令
* printf -> 改成 puts, putc
* memcpy -> Block Transfer Instruction
* likely and unlikely macro: 用來將 branch 的相關資訊提供給 compiler，告訴 compiler 設計者期望的比較結果，以便對程式碼改變分支順序來進行優化
* 但也有缺點，若系統中剛好缺少實作，可以關閉該功能
* 針對 C 語言編譯最佳化的常見策略:
* Loop Optimizations: 雖然有分支預測，但還是會有預測錯的時候，導致大幅度的額外花費，因此可以將迴圈展開，減少迴圈次數
```c=
for (int i = 0; i < 100; i++) {
g();
}
```
改成
```c=
for (int i = 0; i < 100; i += 2) {
g();
g();
}
```
* Inter Procedure Optimization
* 考慮到再將專案化為許多個 CU 時，在執行上可能會變得費時
* 尤其是若呼叫的函示要做的事基本上只有一兩個指令而已，這樣與呼叫函式(stack操作)這件事本身所花費的時間相比差太多
* 所以可考慮將函式展開到呼叫端函式裡頭，像是巨集展開一般
* Function inlining
```c=
int add(int x, int y) {
return x + y;
}
int sub(int x, int y) {
return add (x, -y);
}
```
改成
```c=
int sub (int x, int y) {
return x - y;
}
```
* 但是 CU 是獨立編譯的，無法做 inline，所以可以用 Link Time Optimization(LTO)
* Auto Vectorization
* Auto Parallelization
* 由數個 c 程式原始檔構成專案
* 可讓事情變簡單好管理
* 編譯器在編譯每個.c檔時視為獨立個體，彼此之間沒有相依性
* 用編譯器的術語來講，每個個體稱為 Compilation Unit
* Static Global Variable vs Non-Static Global Variable
* static Global: 只有這個 CU 都可看到這個變數，沒人用時編譯器會砍掉他
* non-static Global: 所有 CU 都可看到這個變數，編譯器部會砍他，因為不知道別的 CU 會不會用
* 盡量使用區域變數
### LLVM
* 由來: 起初是拿 GCC 來做為前端，但後來因為授權問題改用 Clang 作為前端
* 架構
* LLVM Optimize
* BitCode Passes: 坐前面講到的如 SSA 最佳化
* DAG: 利用 DAG 資料結構來最佳化處理 pipeline 的排程(解決 data hazard、降低 data dependence 等)
* Machine: 輸出 Machine code 的最佳化策略
* LVM 相較於 早期的 GCC 他可以每個階段單獨執行( API 化)，比如說可以輸出每個階段的輸出或某階段呼叫某 API(ex: clang LVM auto-complete，在編輯器裡面呼叫 clang)，對於 GCC 更具彈性
### 參考資料
http://shihyu.github.io/books/ch18s05.html
https://www.slideshare.net/jserv/how-a-compiler-works-gnu-toolchain
https://hackmd.io/@ofAlpaca/ryNNXAuoQ/https%3A%2F%2Fhackmd.io%2Fs%2FB1aGFRW6Q?type=book
http://ccckmit.wikidot.com/lk:dynamiclinking
https://medium.com/@alastor0325/https-medium-com-alastor0325-compilation-to-linking-c07121e2803
https://www.zhihu.com/question/20039402
Sign in with Wallet
Connect another wallet