---
title: 「你所不知道的 C 語言：編譯器原理和案例分析」 筆記
tags: Computer Science,System Software
description: 2019.08.10
---
「你所不知道的 C 語言：編譯器原理和案例分析」 筆記
===
###### 2019.08.10 *Copyright © 2019 by srhuang*


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

---

## 如何打造一個具體而微的 C 語言編譯器？
* 700 行系列：https://youtu.be/Cf9kXtLuQZ8?t=65
* AMaCC：https://youtu.be/Cf9kXtLuQZ8?t=363
* 是由台灣國立成功大學師生開發的 self-compiling 的 C 語言編譯器。
* 支援 just-in-time (JIT) 編譯和執行。
* 原始程式碼還不到 1500 行。
* IR (Intermediate representation), dynamic linking, relocation, symbol table, parsing tree, language frontend, Arm 指令編碼和 ABI。
* AMaCC 產生出來的執行檔：https://youtu.be/Cf9kXtLuQZ8?t=623

## 編譯器和軟體工業強度息息相關
* IBM 簡報：https://youtu.be/Cf9kXtLuQZ8?t=666
* 軟體驗證環境相當重要。
* 形式化驗證：https://youtu.be/Cf9kXtLuQZ8?t=848

## 用1500 行建構可自我編譯的 C 編譯器：
* 自我編譯才能讓整個系統自我演化：https://youtu.be/Cf9kXtLuQZ8?t=1090
* Self-host：https://youtu.be/Cf9kXtLuQZ8?t=1356
* 如果無法 self-host (自我編譯)，就需要 bootstrapping，有三種方法：
* 徒手把 machine code 寫出來。
* 用另一個語言寫出來的 compiler 來 compile。
* 透過 interpreter 建立 translator。
* Clang (LLVM) 花了三年才能夠達到 self-host。
* 當編譯器能夠 self-host，才能說是 fully-functional。
* 支援 JIT (just-in-time) compiler：https://youtu.be/Cf9kXtLuQZ8?t=1834
* 輸出 ELF 檔案格式。
* How AMacc works?：https://youtu.be/Cf9kXtLuQZ8?t=2000
* parse code 轉成 IR。
* 直接透過 codegen 轉成 machine code。
* relocation。
* IR (Intermediate Representation)：https://youtu.be/Cf9kXtLuQZ8?t=2187
* 沒有 IR，會無法有效率的重用最佳化技術。
* 「電腦科學所有的問題，都可以引入中間層去解決。」
* 把 token 轉成 IR 的 opcode。
* 在 codegen 裡把 opcode 轉成 machine code。
* opcode 會透過載入系統函式庫 libc，來使用系統呼叫。
* ELF format：https://youtu.be/Cf9kXtLuQZ8?t=3075
* Executable and Linkable Format。
* ELF Header：Program header, Section header。
* Section and Segment。
* Interpreter 代表與 dynamic linker 有關。

## 背景知識
* 編譯器和最佳化原理篇：https://youtu.be/Cf9kXtLuQZ8?t=3616
* Skymizer (台灣發展軟體公司) 的 onnc。
* 編譯器最佳化的範例。
* SSA (Static Single Assignment)：SSA 把原本複雜的條件和程式邏輯轉化為 Graph
* 編譯器的最佳化背後都是數學。
* Compilation Flow。
* Procedures：argument 傳遞的形式 / parameter 接收的數值。
* 動態連結器和執行時期篇：https://youtu.be/Cf9kXtLuQZ8?t=4560
* 實作跨越程式語言的交流。
* LD_PRELOAD 環境變數，可以替換掉 malloc。
* Compilation Unit：建議 local function 要宣告成 static。
* Modern C：必讀的教材。
* 動態連結支援：GOT and PLT。
* Relocation。
* Browser Linker。
* [虛擬機器設計與實作](https://hackmd.io/@jserv/SkBsZoReb?type=view)：https://youtu.be/Cf9kXtLuQZ8?t=5807
* 主要分成 process virtual machine and system virtual machine。
* RTMux：無人機。

## C 程式的解析和語意
* descent 點評幾本編譯器設計書籍：https://youtu.be/Cf9kXtLuQZ8?t=6345
* OGC (Ordinary Garbage Collector)：https://youtu.be/Cf9kXtLuQZ8?t=6550
* 手把手教你建構 C 語言編譯器：https://youtu.be/Cf9kXtLuQZ8?t=6853
* c4：用四個 function 實作出 C語言的直譯器。
* 編譯器雜談。編譯器是電腦科學的第一個正式有系統的學科。
* 設計：https://youtu.be/Cf9kXtLuQZ8?t=7217
* token。
* Compilers and Virtual Machine。
* 虛擬機：https://youtu.be/Cf9kXtLuQZ8?t=7482
* 建構 opcode。
* 中間的 IR 不要離 machine code 太遠。
* 指令集以 [stack-based](https://en.wikipedia.org/wiki/Stack_machine) 為主。[相對於 register-based]
* 詞法分析器：https://youtu.be/Cf9kXtLuQZ8?t=7932
* compiler lex yacc
* GCC 為了效能考量，捨棄 lex/yacc 直接用手刻，會大幅提升效率。
* 不支援 struct，但是 AMaCC 有支援。
* 遞歸下降：https://youtu.be/Cf9kXtLuQZ8?t=8303
* 語法分析器從上而下分析，稱為遞歸下降。
* 設計編譯器，其實也在探索語法表達式的限制。
* 變量定義：https://youtu.be/Cf9kXtLuQZ8?t=8621
* 表達式：https://youtu.be/Cf9kXtLuQZ8?t=8654
* postfix, infix：要把中序轉成前序或是後序才能使用 stack-based machine。
* 自增自減：p++, p--。
* 逐步開發編譯器：https://youtu.be/Cf9kXtLuQZ8?t=8973

## IR (Intermediate representation)
* interpreter：https://youtu.be/Cf9kXtLuQZ8?t=9062
* AMaCC interpreter branch。
* 可以執行 Bytecode，解讀 opcode。
* JIT，Interpreter, Compiler, JIT from scratch：https://youtu.be/Cf9kXtLuQZ8?t=9179
* Brainf*ck language Interpreter。
* JIT compiler：https://youtu.be/Cf9kXtLuQZ8?t=9321
* 在執行階段動態輸出 machine code，並且執行。
* 利用 mmap 讓原本是 data 的 machine code 可以執行。
* AMaCC IR：https://youtu.be/Cf9kXtLuQZ8?t=9621
* AMaCC JIT 執行：https://youtu.be/Cf9kXtLuQZ8?t=9665
* test/jit.c
* 使用 bsearch 跳過去執行，因為 AMaCC 沒有支援 function type。
* How to JIT - an introduction：https://youtu.be/Cf9kXtLuQZ8?t=9954
* __clear_cache：AMaCC 的 CLCA。
* How to write a very simple JIT compiler：https://youtu.be/Cf9kXtLuQZ8?t=10338
* 跳躍是影響效能很重要的議題，太多的跳躍會影響 cache。

## 總結：https://youtu.be/Cf9kXtLuQZ8?t=10550