---
# System prepended metadata

title: 編譯器_最佳化
tags: [C 語言筆記]

---

---
title: 編譯器_最佳化
tags: C 語言筆記
---
## 編譯器_最佳化

### GUN/Linux 程式執行流程
![](https://i.imgur.com/1mjhEuO.png)
* Shell 執行 ./hello 時會先呼叫 fork + execve 來讓核心準備建立程序
* 當 kernel 準備好執行檔的空間後，就會依據執行檔載入對應的動態連結器並載入對應的動態函式庫 (以上圖為例就是 libc.so)
* libc.so 中的 libc_start_main 會在執行檔中找尋 C 語言程式的進入點 (main) ，並由此開始執行程式
* 如果是靜態連結則配置好程序的空間後就會直接去找進入點
* 程式結束時再呼叫 exit 

### 編譯程式的流程
![](https://i.imgur.com/8htOxJN.png)

* 預處理 (pre-processing)
    * 刪除所有的 #define 並展開所有 macro
    * 處理所有的預編譯條件，例如 #ifdef 、 #include
    * 刪除所有 註解
    * 增加行號以及文件識別名，讓編譯器在編譯失敗時可以顯示錯誤的行數
    ![](https://i.imgur.com/dwGTfzx.png)
* 編譯 (compilation)
    * Lexical Analyzer(scan):
        * 目的為將程式碼的序列分割成一連串的 token，並將這些 token 分類
        * 舉例來說， ```a = 3 + 5``` 這段程式碼是由六個  token 所組成
        * ```a``` 為標示符，```=``` ```+``` ```;``` 為特殊符號，```3``` ```5``` 為常量
    * Syntax Analyzer(parsing)
        * 有了這些 token 之後，就可以組出對應的文法樹 (syntax tree)
        ![](https://i.imgur.com/Sy2XezU.png)
    * Semantic Analysis
        * syntax-directed translation
        * 接下來要判斷語意的正確性，比如說我們允許兩個常量相乘，但不允許對兩個指標做相乘。而語意又可分成```靜態語意```以及```動態語意```，靜態語意是編譯器可以在```編譯期```分析的，並且回報錯誤，例如：型態的轉換否正確。而動態語意則是在```執行期```相關的，例如：以零當作除數是一個執行期的語意錯誤
        * 文法樹上加上語意型別
        ![](https://i.imgur.com/KKp2wGH.png)
    * 代碼優化 (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) 透過目標文件內的資訊來分配空間以及確定符號的確切位址
    ![](https://i.imgur.com/ALcVNZM.png)
    * 重點複習: [Re-introduction to Compiler](http://slide.logan.tw/compiler-intro/#/2)

* 編譯器術語
    * Basic Block: 單一進入點、單一出口點的程式區段
    ![](https://i.imgur.com/103CICi.png)
    * CFG(Control Flow Graph): BB組成的程式流程圖
    ![](https://i.imgur.com/KZ9zdEJ.png)
    
* IR(Intermediate Representation)
    * 引入 IR 可以更容易支援前端(ex: C++、python等語言)、後段(不同arm、mips、intel架構)
    ![](https://i.imgur.com/OcogaId.png)
### 最佳化技巧
* Code Motion(程式碼搬移)
    * 有些運算可提前執行，加速運算
    ![](https://i.imgur.com/znxEnxO.png)
    * Pointer Aliasing: 程式碼搬移可能會再成的問題，當兩個指標指到同一個記憶體位置時，下圖的a、b、y若只到同一個位址便會出錯
    ![](https://i.imgur.com/u4thKdm.png)
    * 可以用
* 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，用讓每個程式邏輯轉成明確的路徑
    ![](https://i.imgur.com/dfR4du4.png)
    * 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
![](https://i.imgur.com/pZMvv9w.png)

* 前端: 辨識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: 三行變成兩行
            ![](https://i.imgur.com/IuJwUFm.png)
        * 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)
        ![](https://i.imgur.com/s0Sk2JY.png)
    * Auto Vectorization
    * Auto Parallelization
    * 由數個 c 程式原始檔構成專案
        * 可讓事情變簡單好管理
        * 編譯器在編譯每個.c檔時視為獨立個體，彼此之間沒有相依性
        * 用編譯器的術語來講，每個個體稱為 Compilation Unit
        * Static Global Variable vs Non-Static Global Variable
            * static Global: 只有這個 CU 都可看到這個變數，沒人用時編譯器會砍掉他
            * non-static Global: 所有 CU 都可看到這個變數，編譯器部會砍他，因為不知道別的 CU 會不會用
            * 盡量使用區域變數
            ![](https://i.imgur.com/J605eRu.png)
        

### LLVM

* 由來: 起初是拿 GCC 來做為前端，但後來因為授權問題改用 Clang 作為前端
* 架構
![](https://i.imgur.com/DAeq2kH.png)
* 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