---
title: 「你所不知道的 C 語言：編譯器和最佳化原理篇」 筆記
tags: Computer Science,System Software
description: 2019.08.13
---
「你所不知道的 C 語言：編譯器和最佳化原理篇」 筆記
===
###### 2019.08.13 *Copyright © 2019 by srhuang*


[影片上](https://youtu.be/XY4YkuX_a3k)
[影片下](https://youtu.be/J2lZmh4PXTc)
[講義](http://hackfoldr.org/dykc/https%253A%252F%252Fhackmd.io%252Fs%252FHy72937Me)
Original by [jserv](http://wiki.csie.ncku.edu.tw/User/jserv)

---

## 編譯器無所不在
* 編譯器的多元應用：https://youtu.be/XY4YkuX_a3k?t=16
* Where can we find compiler：https://youtu.be/XY4YkuX_a3k?t=318
* 理解編譯器的限制：https://youtu.be/XY4YkuX_a3k?t=451
* Missed optimizations in C compilers：https://youtu.be/XY4YkuX_a3k?t=529
* Don’t Overflow the Stack：https://youtu.be/XY4YkuX_a3k?t=637
* Basics of Compiler Design：https://youtu.be/XY4YkuX_a3k?t=771

## From Source to Binary
* 介紹：https://youtu.be/XY4YkuX_a3k?t=1152
* 執行程式流程：https://youtu.be/XY4YkuX_a3k?t=1204
* 執行 execve 系統呼叫：https://youtu.be/XY4YkuX_a3k?t=1403
* 動態連結：https://youtu.be/XY4YkuX_a3k?t=1442
* 跳入程式進入點：https://youtu.be/XY4YkuX_a3k?t=1500
* 常見的誤解：https://youtu.be/XY4YkuX_a3k?t=1538
* 編譯流程：https://youtu.be/XY4YkuX_a3k?t=1724
* 介紹 AMaCC。
* 為何要分成編譯、組譯、連結：為了除錯以及專業分工。
* Hello World 編譯流程：https://youtu.be/XY4YkuX_a3k?t=1972
* GCC 是個 Compiler Driver：https://youtu.be/XY4YkuX_a3k?t=2442
* 編譯器簡史：https://youtu.be/XY4YkuX_a3k?t=2713
* 先有雞還是先有蛋？：https://youtu.be/XY4YkuX_a3k?t=2992
* Bootstrapping：https://youtu.be/XY4YkuX_a3k?t=3198
* 編譯器教科書：https://youtu.be/XY4YkuX_a3k?t=3439
* 電腦所有的行為基本上就是字串處理。
* 龍書的編譯流程：https://youtu.be/XY4YkuX_a3k?t=3476
* Compiler 最引人入勝的地方是最佳化。
* 快速複習：
* [Page 5]：https://youtu.be/XY4YkuX_a3k?t=3729
* atexit 一類的函式，需要 C runtime 的介入才能實現。
* exception handling，透過 setjmp 和 longjmp 函式。
* 算術操作，特別在硬體沒有 FPU 時，需要 libgcc 來提供浮點運算協助。
* [Page 16]：https://youtu.be/XY4YkuX_a3k?t=3867
* Self-hosting。
* 人們一直都希望電腦可以理解人類的語言。
* 工業革命後，人們有機會從繁瑣的工作解放，電腦的出現又更加速發展。
* 維根斯坦。
* Re-introduction to Compiler：https://youtu.be/XY4YkuX_a3k?t=4257
* Compiler are tools for programmers to translate programmer'sthought into computer runnable programs.
* Lexer：tokens.
* Parser：AST (Abstract Syntax Tree), S-expression.
* Code Generator：machine code, SDT (Syntax Directed Translation).
* 編譯器術語：https://youtu.be/XY4YkuX_a3k?t=4760
* Basic Block：單一進入點，單一出口點。
* CFG (Control Flow Graph)：程式流程圖。
* Syntax Sugar (語法糖)：語法糖讓程式更加簡潔，有更高的可讀性。
* 教科書回顧：https://youtu.be/XY4YkuX_a3k?t=5087
* 分析 Tokens。
* 語法分析。(Context-free Grammar)
* 語意分析。(Type checking)
* IR。
* 目標語言。
* PROGRAMMING LANGUAGE THEORY：https://youtu.be/XY4YkuX_a3k?t=5528
* Type Theory.
* Dynamic Scoping in Bash.
* NON-LEXICAL SCOPING IN JAVASCRIPT.
* IR (Intermediate Representation)：https://youtu.be/XY4YkuX_a3k?t=5916
* Front-end Language to Back-end Language.
* 從教科書到真實世界：https://youtu.be/XY4YkuX_a3k?t=6082
* 程式的語法樹無法與處理器架構脫鉤。
* Function call 參數傳遞順序、堆疊處理。(與ABI有關)
* GCC 支援多種語言和處理器。
* 有些最佳化與硬體無關。(Dead Code Elimination)
* GCC 的解決之道：https://youtu.be/XY4YkuX_a3k?t=6728
* GCC 的 IR：Gimple.
* Code Motion：https://youtu.be/XY4YkuX_a3k?t=7150
* Data-flow analysis：https://youtu.be/XY4YkuX_a3k?t=7175
* Code Motion and Pointer Aliasing：https://youtu.be/XY4YkuX_a3k?t=7207
* restrict 關鍵字告知編譯器指標不會有 pointer aliasing。
* 快速複習：https://youtu.be/XY4YkuX_a3k?t=7558
* Pointer Aliasing會讓編譯器最佳化功能無用武之地。
* Compiler Analysis：https://youtu.be/XY4YkuX_a3k?t=7651
* Data-flow analysis.
* Control-flow analysis.
* Memory dependency analysis.
* Alias Analysis：https://youtu.be/XY4YkuX_a3k?t=7864
* SSA (Static Single Assignment)：https://youtu.be/XY4YkuX_a3k?t=7956
* 每個被 assign 的變數只會出現一次，每個被 assign 的變數給一個 version number。
* Φ (Phi) function：不確定分支。
* 使用 SSA 的最佳化：https://youtu.be/XY4YkuX_a3k?t=8236
* Constant Propagation.
* Dead Code Elimination.
* Register Allocation.
* SSA Constant Propagation：https://youtu.be/XY4YkuX_a3k?t=8278
* 切割 Basic Block —> 合併 Basic Block —> 最佳化 CFG —> 轉成 3-address code —> 轉成 SSA form。
* Constant Propagation：https://youtu.be/XY4YkuX_a3k?t=8932
* Value Range Propagation：https://youtu.be/XY4YkuX_a3k?t=9151
* GCC 結構：https://youtu.be/XY4YkuX_a3k?t=9358
* 快速複習：https://youtu.be/XY4YkuX_a3k?t=9438
* SSA 把原本複雜的條件和程式邏輯轉化為 Graph，用讓每個程式邏輯轉成明確的路徑。
* Graph Theory。
* [形式化驗證](https://hackmd.io/@sysprog/H1xxp3pF0?type=view)。

## 總結：https://youtu.be/XY4YkuX_a3k?t=9877

---

## From Source to Binary
* 複習 SSA：https://youtu.be/J2lZmh4PXTc?t=12
* GCC 結構：https://youtu.be/J2lZmh4PXTc?t=275
* Parser —> Gimply —>Tree SSA —>RTL Generator —> Code Generator.
* 語言間轉換：https://youtu.be/J2lZmh4PXTc?t=591
* Gimple —> RTL —> ASM.
* GCC 前端：https://youtu.be/J2lZmh4PXTc?t=642
* Source —> AST —> Generic
* cc1 真正的 C 編譯器：https://youtu.be/J2lZmh4PXTc?t=720
* 所有的Lisp程式碼都寫為 S-expression 或以括號表示的列表。
* GCC 中端：https://youtu.be/J2lZmh4PXTc?t=1073
* Gimple and Tree SSA Optimizer。
* GCC 是 1985 年由 Richard Matthew Stallman 所開發的。
* GNU Emacs 同時也是 Richard Stallman 所開發的。
* Gimple 是 GCC 的 IR。(3-address IR)
* Gimple 可以簡化成 SSA form。
* 可以使用 [fdump-tree](https://gcc.gnu.org/onlinedocs/gcc/Developer-Options.html#Developer-Options) 來觀察其結構。
* GCC 後端：https://youtu.be/J2lZmh4PXTc?t=1388
* Register Transfer Language (RTL).
* 類似 LISP 的表示法，S-expression。
* Register Allocation.
* Peephole Optimization.
* RTL Pattern Match Engine：https://youtu.be/J2lZmh4PXTc?t=1610
* MIPS.md：machine description.
* [GNU Machine Description](https://gnu.huihoo.org/gcc/gcc-4.4.5/gccint/Machine-Desc.html)
* Register Allocation：https://youtu.be/J2lZmh4PXTc?t=2063
* 著色問題 (NP-Complete)。
* GCC 暫存器在特權模式，有些並不能使用。
* 後來又重寫 IRA (Integrated Register Allocation)。
* [Design and Implementation of GCC Register Allocation](https://www.slideshare.net/kitocheng/register-allocation-in-gcc-public)。
* 管線排程：https://youtu.be/J2lZmh4PXTc?t=2649
* 以 5-stage pipeline 為例。
* Peephole Optimization：https://youtu.be/J2lZmh4PXTc?t=3148
* performed on a small set of compiler-generated instructions.
* peeping Tom 的典故。
* 進階編譯器最佳化技術：https://youtu.be/J2lZmh4PXTc?t=3723
* 回顧 code motion and pointer aliasing。
* Loop Optimization：ILP (Instruction-level parallelism), branch prediction, loop unrolling。
* Inter Procedural Optimization
* Auto Vectorization：processes a single pair of operands at a time, to a vector implementation, which processes one operation on multiple pairs of operands at once, for SIMD (Single Instruction Multiple Data) hardware.
* Auto Parallelization：程式平行化 openMP, C++ AMP。
* C 專案：https://youtu.be/J2lZmh4PXTc?t=4410
* Compilation Unit.
* 程式模組化。
* Compilation Unit：https://youtu.be/J2lZmh4PXTc?t=4879
* static function/variable 只會在該 compilation unit 看得到。
* non-static global variable 會阻礙 compiler 的最佳化，因為不確定其他的 compilation unit 是否會使用。
* Compilation Unit 盡量使用區域變數：全域變數會 load/store memory，區域變數直接對 register 操作。
* Built-in Function：https://youtu.be/J2lZmh4PXTc?t=5732
* Linux likely unlikely 使用 builtin function。
* builtin function 通常都是兩個底線開頭，兩個底線開頭的是保留給編譯器或作業系統。
* 為了最佳化，會辨認標準函式 (builtin function)，以處理器最適合的方式執行。
* Intel SSE 4.2 intrinsic：function call 對應特定組合語言。
* 可以使用 -fno-builtin 來關閉最佳化。
* IPO (Inter-Procedural Optimization)：https://youtu.be/J2lZmh4PXTc?t=6642
* Function call 是有成本的。
* 最簡單的 IPO 就是 Function inlining，把整個 function body 複製到 caller 程式碼中。
* 如何 inline 外部函式：https://youtu.be/J2lZmh4PXTc?t=7159
* 基本上 compiler 無法做到，因為無法看到其他 compilation unit。
* LTO (Link Time Optimization)。
* Linker and LTO：https://youtu.be/J2lZmh4PXTc?t=7653
* Linker 的命令列本身就是一種語言。
* GNU Linker v.s. Google Gold Linker：https://youtu.be/J2lZmh4PXTc?t=7841
* Linker 往往是效能的瓶頸。
* GNU ld 仰賴 BFD，慢且難以維護。
* Google Gold 效率比 GNU ld 快兩倍，但僅支援 ELF。
* MTK 也有參與 Google Gold Linker 的開發。
* 台灣自主研發的 CPU 架構，Sunplus core (S+ core)。
* LLVM：https://youtu.be/J2lZmh4PXTc?t=8658
* 使用 C++ 撰寫的編譯器。
* 一開始仰賴 GCC 做前端輸出 IR。
* GCC 4.2 與 LLVM 的關係：https://www.zhihu.com/question/20039402
* LLVM 的核心觀念：https://youtu.be/J2lZmh4PXTc?t=9116
* LLVM is a Compiler IR.
* 有三種形式：in-memory form (JIT)、ASM form、Object code (Bitcode) form。
* LLVM 架構：https://youtu.be/J2lZmh4PXTc?t=9299
* Clang 為 compiler 前端。
* LLVM lli : LLVM 的直譯器，可以執行由 LLVM 產生的 bitcode。
* LLVM Optimization：Selection DAG。
* LLVM 偉大的地方就是他切割每個部分，而且可以利用 API 單獨使用。
* clang autocomplete for IDE。
* LLVM 總是打開你的心：從電玩模擬器看編譯器應用實例。
* LLVM Toolchain：https://youtu.be/J2lZmh4PXTc?t=10126
* open source 讓最沒有產值的地方，很快地淘汰。
* Clang 取代 GCC 的 frontend。
* Clang Expressive Diagnostics：https://youtu.be/J2lZmh4PXTc?t=10438
* Clang/LLVM Toolchain：https://youtu.be/J2lZmh4PXTc?t=10464
* cross compiler != cross compiler toolchain.
* cross compiler toolchain 包含 cross compiler.
* LLVM TableGen：https://youtu.be/J2lZmh4PXTc?t=10665
* Target Description.
* 編譯器進化論：https://youtu.be/J2lZmh4PXTc?t=10766
* LLVM 的發展。

## 總結：https://youtu.be/J2lZmh4PXTc?t=10885