---
tags: 你所不知道的 C 語言, 進階電腦系統理論與實作, NCKU Linux Kernel Internals, 作業系統
---

# 編譯器與最佳化原理、案例分析
contributed by <`RusselCK` >

###### tags: `RusselCK`

## [編譯器與最佳化原理](https://hackmd.io/@sysprog/c-compiler-optimization?type=view) ( 上 )

* WebAssembly
* 理解編譯器的限制:
* [gcc can’t handle too much #if macro](http://peter.kingofcoders.com/?p=1799)
* [Missed optimizations in C compilers](https://github.com/gergo-/missed-optimizations)
* [Don’t Overflow the Stack](http://betterembsw.blogspot.tw/2014/07/dont-overflow-stack.html)
* [MISRA C](https://en.wikipedia.org/wiki/MISRA_C) (Motor Industry Software Reliability Association)
( 車用的 C 語言 )
* [Basics of Compiler Design](http://www.diku.dk/~torbenm/Basics/basics_lulu2.pdf) ( 編譯器教材 )
* Lexical analysis ( 程式碼的運作 )
* Regular expression, NFA (Nondeterministic finite automata)
( 自動狀態機 )
* NFA -> DFA (Deterministic finite automata)
( 是否能在有限的步數內解析出來 )
* lexer
( 程式如何轉換成狀態機? 狀態機如何轉換? )
* Syntax analysis ( 語法 )
* context-free grammar, syntax tree and ambiguity, operator precedence, predictive parsing
( 運算元優先權、括號 )
* LL(1) parsing: recursive descent
* SLR parsing
* LR-parser generator
* Scopes & Symbol Tables
* Interpretation ( 行為 )
* Type checking ( 型態: 整數、浮點數 的表示方式 )
* Code generation: register allocation ( 暫存器分配 )

### [From Source to Binary: How A Compiler Works: GNU Toolchain](http://www.slideshare.net/jserv/how-a-compiler-works-gnu-toolchain)


1. 在 shell 中執行 執行檔`hello`
* shell 呼叫 `fork` + `execve` System call
* 讓 kernel 準備建立 new process
2. 驗證 執行檔 並 呼叫 動態連結器
* 當 kernel 驗證完畢 且 准許配置 process 空間後
* 根據 執行檔的資訊 載入對應的 Dynamic Linker (e.g. `ld-linux.so`) 與 對應的 動態函式庫 (e.g. `libc.so`)
* 包含 C Runtime 支援
* `ld-linux.so` `libc.so` 在 GNU/Linux 上，由 glibc 提供
3. 由 C Runtime 跳入 真正的程式進入點
* `libc.so` 的函式 `libc_start_main` 嘗試在 執行檔 中 尋找 C 語言進入點 ( i.e. `main` 所在位置 )，並進入執行
4. C 語言結束 並 呼叫 exit System call
* C 程式執行完畢 ( i.e. `return` ) 或 呼叫 `exit` System call
* kenel 會處理 棄置 process 善後
:::warning
* 這邊提到驗證執行檔後並載入動態函式庫，為何要有 C Runtime?

先想想以下程式的執行: (hello.c)

int main() { return 1; }

當你在 GNU/Linux 下編譯和執行後 (`gcc -o hello hello.c ; ./hello`)，可用 `echo $?` 來取得程式返回值，也就是 `1`，可是這個返回值總有機制來處理吧？所以你需要一套小程式來作，這就是 C runtime (簡稱 crt)。此外，還有 `atexit` 一類的函式，也需要 C runtime 的介入才能實現。

* C 語言和一般的程式語言有個很重要的差異，就是 C 語言設計來滿足系統程式的需求，首先是作業系統核心，再來是一系列的工具程式，像是 ls, find, grep 等等，而我們如果忽略指標操作這類幾乎可以直接對應於組合語言的指令的特色，C 語言之所以需要 runtime，有以下幾個地方：

1. `int main() { return 1; }` 也就是 `main()` 結束後，要將 exit code 傳遞給作業系統的程式，這部份會放在 `crt0`
2. exception handling，不要懷疑，C 語言當然有這個特徵，只是透過 `setjmp` 和 `longjmp` 函式來存取，這需要額外的函式庫 (如 libgcc) 來協助處理 stack
3. 算術操作，==特別在硬體沒有 FPU 時，需要 libgcc 來提供浮點運算協助==
:::


* tool-chain
* 編譯->組譯->連結 ( 建議的分工，非制式 )
* 方便除錯


1. `gcc -o hello hello.c`
2. Pre-process
* C preprocessor 參照 標頭檔 `stdio.h` 的內容
* 展開 macro、驗證 prototype
* 因此，輸出結果不會見到 `#include`
3. Compile
* C compiler 輸出 對應組合語言
* `BAL`: ARM 架構 的 跳躍指令
* ==編譯階段不知道 `printf` 的位址==，所以暫時填入 printf 符號名稱
4. Assemble
* ARM assembler 將 組合語言 組譯 為 對應的 ARM machine code
* ==組譯階段不知道 `printf` 的位址==，所以暫時不填入
5. Linking
* `printf` 實作於 `libc.a` ( C 語言標準函式庫 的 靜態版本 )
* 為只為 0x1000
* Linker relocate


* 先有程式語言，還是先有編譯器?
* 能夠自己編譯自己原始程式碼的程式: [Self-hosting](https://en.wikipedia.org/wiki/Self-hosting)：作為 toolchain 的一部分，可以產生新版同一程式的程式
* 由於早期硬體限制很多，其實是不可能直接實做出高階語言的編譯器，相反的，早期的工程人員必須漸進地開發相關的工具的程式，所以你可以想像最早人們用機械碼拼湊出簡單的 assembler，然後在這之上發展了簡單的 C compiler，之後再用這個 C compiler 開發出更完整的 C compiler，後者可以編譯更完整的 C 語言程式，然後逐步延展下去

* 所有的電腦流程，都是字串處理

* 程式語言 發明來 解決問題，世上仍有人在開發編譯器，因為還有事情需要被解決
* 由於電腦發展最初是解決軍事需求，後來則應用到人口普查系統，人們一直都希望電腦可以理解人類的語言，這也是為何早期 (1950 年代) 的程式語言其實很高階的緣故，有透過數學表達的風格 (如 LISP)，也有類似英文書寫風格 (如 COBOL)
* 就算電腦發展還在真空管的時代，人們就著手研究解析語言學和數學的關聯，這也是為何你在計算理論和編譯器課程 (這兩者是資訊工程系和電機系極少沒有重疊的科目) 會發現一些語言學的跡象
* [路德維希·維根斯坦](https://zh.wikipedia.org/wiki/路德维希·维特根斯坦)

### [Re-introduction to Compiler](http://slide.logan.tw/compiler-intro/#/2)

- AST ( Abstract [S-expression](https://zh.wikipedia.org/wiki/S-表达式) Tree )
- ARMv8-A 組合語言
- Syntax-Directed Translation
- Progamming Language Theory, PLT
* type theory
* 了解 ==程式語言本身的行為== 比 讀多少程式語言更重要

* Compiler Analysis


### 編譯器術語

* Basic Block


* Control Flow Graph, CFG


* BB vs. CFG

* for 迴圈 是一種 Syntatic sugar
* 非必要存在，但方便使用

* 中間表示法 ( Intermediat Representation, IR )


* 編譯器的心臟
* Front End -> Back End

### 教課書回顧




* int、float ...等型態分辨
* 議題: 型態可能會改變
* 除以 0、浮點數的型態


* 中間語言
* 將 Syntatic sugar 去掉


* Application Binary Interface, ABI
* [GCC](https://gcc.gnu.org)

* Simple -> Gimple

### 最佳化技巧
1. Code Motion


* Data-Flow Analysis, DFA


* Pointer Aliasing



* 若考慮到有人這樣寫 `foo(&var, &var, &var)` 來呼叫 `foo()`
* 很明顯就會發生問題了
* `*res` 值的改變影響 `*i1`、`*i2`。
* 所以 Compiler 不會這樣最佳化，因為不知道 caller 會怎麼傳遞數值。

* [C語言關鍵字淺析-restrict](https://www.itread01.com/content/1542973983.html)

2. ==Static Single Assignment, SSA==
* SSA 把原本複雜的條件和程式邏輯轉化為 Graph，讓每個程式邏輯轉成明確的路徑
* 各種方法的集大成
* Graph Theory
* [形式化驗證](https://hackmd.io/@sysprog/H1xxp3pF0?type=view)


1. 變數 + Version
2. $c=\phi(a,b)$ : $c$ 可能 為 $a$ 或 為 $b$



* 例子 ( in GCC-4.x ( Tree SSA ) )


* 切割 Basic Block



* for -> bb~i~

* 最佳化 CFG


* 改變順序，減少程式碼
* 轉化為 3-Address code


* 3-Address code: 2 個輸入 + 1 個輸出

* 轉成 SSA form


* Constant Propagation ( 數值代換 )


* 確定之後不會用到的變數，可以安心地用數值替換

* Constant Folding ( 數值疊合 )


* 若兩個輸入都已換成數值，則可以進行計算
* 前提是要為 合法運算


* 計算完後，可以再檢查是否能進行數值代換

* Dead Code Elimination


* 把沒用的 code 去掉

* Value Range Propagation


* 變數皆有**形態** ( i.e. 能夠用幾個 bits，具體表示數值範圍、特性 )
* 帶入所有變數的 Domain，可推導出目標變數的範圍


:::info
* 人們的腦袋一在做最佳化，沒用到的知識都會忘記
* 為何要鑽研這些知識?
希望有天能寫出專業的程式碼，對周遭的人有所貢獻，讓這個世界持續進步
* 21世紀的標準 : HTC 並非不會作手機，而是跟不上時代
:::

## 編譯器與最佳化原理 ( 下 )

### GCC 結構


* Gimplifier : Front End -> IR


* RTL ( GCC 特有 )

### GCC 前端


* 程式語言輸入 並 解析
* AST


0. macro 已展開
3. 語法糖 -> goto
5. S-expression

### GCC 中端


* 3-Address IR

### GCC 後端 ( Register Transfer Language, RTL )


* RTL Patten Match Engine


* [LISP](https://zh.wikipedia.org/wiki/LISP)
* S-Expression
* `*.md` : Machine Definition
* 描述處理器後端與機器有關的部分
* `addsi3` : 有 3 個暫存器
* `a` + `-56` 是 暫存器 + 數值
* 對應到 match_operand:GPR 2 "srith_operand" "d,Q"
* addiu\t%0,%1,%2

* Register Allocation


* 著色問題、四色問題
* ARM Banked Register
* 某些情況下，暫存器能使用的數量會被限制
* Integrated Register Allocation

* Pipeline


* Data dependency、Hazard

* [Peephole Optimization](https://en.wikipedia.org/wiki/Peephole_optimization)
* [peeping Tom 的典故](https://zh.wikipedia.org/wiki/%E6%88%88%E9%BB%9B%E5%A8%83%E5%A4%AB%E4%BA%BA)


* 觀察整個過程 ( e.g. 醉漢亂走_前 2 後 3 )
* 用相同結果的行為代替 ( e.g. 退後 1 步 )

* 其他:


* Loop Unrolling
* SIMD
* 聲音、影像、網路封包
* OpenMP
* C++ AMP

### [Compilation Unit, CU](https://www.cs.auckland.ac.nz/references/unix/digital/AQTLTBTE/DOCU_015.HTM) ( `static`、`extern` )
* [【紀錄片】登月機具（全六集）](https://www.youtube.com/playlist?list=PL02EC0F91B167515C)
* [從登月計劃看電腦軟體發展](https://hackmd.io/@sysprog/SJEe2g837)
* ARRC

編譯器如何處裡資料?



:::info
* `extern` global : 所有檔案都能看得到
* `static` global : 只有所在檔案能看到
:::
:::warning
* Compiler可以砍掉沒人使用的 static global variable 來節省空間，但是不能砍掉沒人使用的 non-static global variable
* 因為無法確定別的 [Compilation Unit](https://www.cs.auckland.ac.nz/references/unix/digital/AQTLTBTE/DOCU_015.HTM) 會不會用到此變數
* 這是為何==建議 local function 要宣告成 static== 的用意！
:::


* `i` = r4
* 使用 `static` global ，會使 `i` 儲存在固定的記憶體位置
* 組合語言需要多做 load & store

:::warning
* 盡量使用 local variable，可使編譯器更好最佳化
:::

* Programming Language Theory - [Scoping](https://www.geeksforgeeks.org/static-and-dynamic-scoping/)
* Scoping 的範圍越小，編譯器能最佳化的空間越大

### GCC 內部的實作 (IPO、LTO)

1. Built-in Function


* [Linux 內核中的 likely與unlikely](https://coctec.com/docs/linux/show-post-184401.html)
* `__` : 保留給 編譯器 及 作業系統 使用
* [Intel intrinsics](https://software.intel.com/sites/landingpage/IntrinsicsGuide/)
* Function call 與 組合語言 同名
* SSE 4.1 strlen - https://github.com/WojciechMula/simd-string
* glibc/zlib intel see optimization

2. **Inter-Procedural Optimization, IPO**


* **Function call 會有成本** ( 操作 stack )
* 將一個檔案的 `IsOdd(num)` 換成 `num & 0x1`，只會最佳化一個 CU
* 若有多個檔案，可能有點麻煩...
* Hint: 在下個階段( i.e. Linker )動手腳

3. Link Time Optimization, LTO


* Full IR : ==整合Linker 前的所有 IR ，之後再編譯一次==
* 彙整所有 Symbol 後再編譯一次
* [Linux kernel LTO](https://lwn.net/Articles/512548/)
* runs of the "hackbench" benchmark gain about 5%, while kernel builds don't change much at all.
* 自動化效能提升 : 不用修改程式碼，升級編譯器就能有效能提升
* 「編譯器無法 inline 一個外部函式，解法為 LTO (Link Time Optimization)」什麼意思？
* 投影片: [Optimizing large applications](http://www.ucw.cz/~hubicka/slides/labs2013.pdf)
* 延伸閱讀: [Linktime optimization in GCC](http://hubicka.blogspot.tw/2014/04/linktime-optimization-in-gcc-1-brief.html)
* LTO 帶來的提昇，可參考 [gcc-5 的釋出說明](https://gcc.gnu.org/gcc-5/changes.html) ：(和 Firefox 有關)
* During link-time optimization of Firefox, this pass unifies about 31000 functions, that is 14% overall.

:::warning
* 若 **將函式本身視為 Macro** 的前置處理成本 比 **函式呼叫**的成本 還低的話，在 Link Time 改用前者 (function inlining)，可以使效能提升
* function folding
:::
==無論是 clang/LLVM 抑或 gcc，都支援了 LTO，對應的命令列選項是 `-flto`==

### LTO 的效能
不修改程式碼，只改變編譯器行為，就能使效能提升

* [Firefox is now built with clang LTO on all* platforms](https://glandium.org/blog/?p=3888)
> on Linux, where we’re getting more than 5% performance improvements on most Talos tests (up to 18% (!) on some tests) compared to GCC 6.4 with PGO
* [Shrinking the kernel with link-time optimization](https://lwn.net/Articles/744507/)
> Let's pick the STM32 target which represents the kind of tiny systems we're aiming for. The advantage here is that mainline Linux already runs on most STM32 microcontrollers ... This is a 22% size reduction right there.

### Linker




- Binary File Descriptor, DFB
* 可以操作二進位檔案的函式庫
- Stage 1 : 檢查 Object，沒用的部分丟掉
- Stage 2 : 支援 多執行緒
- 搜尋 : Mediatek gold linker

* Windows Portable Executable, PE
* Windows New Executable, NE
* Linux Executable and Linkable Format, ELF
* ELF DWARF (矮人) : 除錯器

### LLVM
* [LLVM与GCC之间的关系](https://www.zhihu.com/question/20039402)
* [LLVM 總是打開你的心：從電玩模擬器看編譯器應用實例](https://www.slideshare.net/jserv/nes-llvm)


* 原始論文內容 : LLVM Bitcode + LLVM Optimize + LLVM Back-End



* LLVM lli : 直譯器
* 可以直接執行 LLVM 的 Bitcode
* Selection DAG
* Directed Asyclic Graph, DAG
* Pipeline 資料重排

- 小故事:


* apple gcc-4.2

### Clang


* Android RenderScript 是由 Clang 改寫而成


* Clang 編譯速度快，提示精簡


* Cross Compiler
* 在 x86 下可以產生 ARM 的執行檔
* Cross Compiler Toolchain
* C runtime + C library + Linker Script

### LLVM TableGen ( Back-End )
* GCC RTL


### 編譯器的演化


* OpenCL SPIR

## [編譯器原理和案例分析](https://hackmd.io/@sysprog/c-compiler-construction?type=view)