Essentials of Compilation筆記
- 標題：Essentials of Compilation: An Incremental Approach in Racket
- 暫譯：編譯的要素——在Racket的遞增臨近法
- 作者：Jeremy G. Siek
- ISBN 9780262047760
- 書源 Repo：https://github.com/IUCompilerCourse/Essentials-of-Compilation/tree/master
概要
- 這基本上是印第安納大學的各編譯器老師的結晶
- 講述必要的觀念、演算法、如何利用映射的觀念將上層軟體對應到硬體
- JIT編譯、程式分析、編譯最佳化（那是閱後的進階課題）
- 編譯器是用許多關卡（pass）轉換而來的。
- nanopass：避免各環節過度耦合
- 另有Python版
- Racket 子集編譯成 x86_64 組語，使用 Linux/Mac OS 的表示法
各章主題
- ch1,2 抽象語法樹、遞迴函數
- ch3 圖着色 graph coloring 問題，以分配記憶體暫存器。
- ch4 條件表達式，將遞迴函數轉換成goto
- ch5 加迴圈與可變量：
- 資訊流分析與暫存器分析
- ch6 加於「堆積」heap分配的tuple（元組）和垃圾回收
- Ch7 加沒有 lexical scoping 的函數（類似 C語言函數）
- 提到呼叫堆疊 stack 和
- 介紹記憶體分配和GC
- Ch8 lexical scoping：閉包如何轉換成 C 語言的 function 和 tuple
- Ch9：動態型別，引入 Any
- Ch10：Gradual Typing
- Ch11：Generics（泛型）
第一章
提到以下名詞：
- 遞迴函數
- 模式比對
- 抽象語法樹
- 程式語言語法
1.1抽象語法樹 AST
- 表示整數：
(struct Int (value)) - 表示primitive operator 基礎操作子：
(struct Prim (op args))args是list，可為空，或是任意長度- 也可以表示為：
(struct Read ())(struct Add (left right))(struct Neg (value))
- 也可以表示為：
等。
應宜以抽象語法數思考
1.2文法 grammar
- 分成非終端符號（如下方 exp）和終端(terminal)符號如 int。
exp ::= (Prim '+ (exp exp)) | (Prim '- (exp exp)) | (Prim '- (exp))| (Prim read_int ()) |
(Int int)
- int 為在此區間的整數：[-2^62, 2^62-1]，可以表示2^63個整數
第三章
stack 堆疊速度比較慢 register 暫存器速度比較快
變數無限，寄存器有限，該怎辦？
所以我們要找到那些變數使用（其間牽涉）的起訖時間，然後引用關係做成無向圖，成為圖著色問題（也就是如何讓相鄰的頂點色彩（暫存器）相異，在使用最少的顏色（暫存器）下）。
如果暫存器太少怎辦，就只能spill（灑）到stack堆疊上面。
3-1
組合語言的calling conventions
Lvar
main function （作業系統的call）
內有read_int
我們用SystemV表示法來表示x86_64的組合語言 <- GNU CC 與 Mac OS 使用
caller-saved register（存於caller呼叫者的暫存器）
rax, rcx, rdx, rsi, rdi, r8, r9, r10, r11
其中，call 其他函數的暫存器的引數對應順序：
rdi, rsi, rdx, rcx, r8, r9 (個人註：記憶術disdxc 8 9)
引數太多的話，就用caller frame 的空間
callee-saved register（存於callee被呼叫者的暫存器）
rbx, rsp, rbp, r12, r13, r14, r15
- call-live variable（會被用的變數）
我們要找到同時使用的變數和不同時使用的變數，來節省暫存器的使用，這是一種圖著色問題。
附錄：指令集摘
| 指令名 | 操作說明 | 註 |
|---|---|---|
addq A B
|
A + B -> B | |
negq A
|
-A | |
subq A B
|
B - A -> B | |
imulq A B
|
A * B -> B | |
popq A
|
*rsp -> A; rsp + 8 -> rsp | 跳出(pop)，rsp再往大移 |
push q
|
rsp - 8 -> rsp; A -> *rsp | rsp往小移，再壓入(push) |