Essentials of Compilation筆記

導航：首頁 > 程式語言、邏輯學> 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
  • 備份PDF檔：檔案:Essentials of Compilation- An Incremental Approach in Racket 2023 Edition.pdf、簡報載點

概要

• 這基本上是印第安納大學的各編譯器老師的結晶
• 講述必要的觀念、演算法、如何利用映射的觀念將上層軟體對應到硬體
• JIT編譯、程式分析、編譯最佳化（那是閱後的進階課題）
• 編譯器是用許多關卡（pass）轉換而來的。
• nanopass：避免各環節過度耦合
• 另有Python版
• Racket 子集編譯成 x86_64 組語，使用 Linux/Mac OS 的表示法

各章主題

1. ch1,2 抽象語法樹、遞迴函數
2. ch3 圖着色 graph coloring 問題，以分配記憶體暫存器。
3. ch4 條件表達式，將遞迴函數轉換成goto
4. ch5 加迴圈與可變量：
   • 資訊流分析與暫存器分析
5. ch6 加於「堆積」heap分配的tuple（元組）和垃圾回收
6. Ch7 加沒有 lexical scoping 的函數（類似 C語言函數）
   • 提到呼叫堆疊 stack 和
   • 介紹記憶體分配和GC
7. Ch8 lexical scoping：閉包如何轉換成 C 語言的 function 和 tuple
8. Ch9：動態型別，引入 Any
9. Ch10：Gradual Typing
10. 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)
L_int ::= (Program '() exp)
#對應L_int ::= (Program (info body)) 

• int 為在此區間的整數：[-2^62, 2^62-1]，可以表示2^63個整數
• info 以後會用到，現在不用管

Ch2

• L_var 要漸次變成 x86語言

• L_var 擴展 L_int，就是加上Let綁定

• 加上規則

 exp :== Name(var)
 stmt :==(let(var, exp))
 L_var = Module (stmt*)

• 註：要由少漸多的設計

• 要有open recusrion
• 就是要用子型別Lvar繼承Lint，然後必要的時候呼叫super.interp()，其餘時候調用interp()

P.16：我們編譯從P1語言轉成P2語言，再用x86語言編譯就得到想要的結果。 但是也可以用P1的直譯得到同樣的結果。

• global：令主程式空間在外界使用。
• 64bit：計算機記憶體的使用，
• counter：指下一個執行指令的地址

.global main ;x86
main: 
    movq $10,%rax ; $指整數常量，引數還可以用記憶體位置，寄存器名稱。
    addq $32, %rax
retq

寄存器有16個 movq s, d, $n, callq, retq, jmp label [

• rsp stack堆疊之指標，向下增長
• 減掉其值，則增加stack堆疊之大小。

總之這一段不會組合語言就很難懂。

要定義子語言，建議創立一個instr系列的records，儲存指令，以利模式比對。

使用pass各自解決一個子問題求解

要明確知道選擇，以及我們循序漸進編譯：

• uniqify ：唯一化變數名稱
• remove complex operands：primitive處理的運算元變成var or integer
• explicate control：明確化執行順序
• select instruction：轉換L_var到x86
• assign_homes：變數轉換至暫存器或堆疊位置。
• patch instruction
• prelude and conclusion（x86的頭和尾）

第三章

stack 堆疊速度比較慢 register 暫存器速度比較快

變數無限，寄存器有限，該怎辦？

所以我們要找到那些變數使用（其間牽涉）的起訖時間，然後引用關係做成無向圖，成為圖著色問題（也就是如何讓相鄰的頂點色彩（暫存器）相異，在使用最少的顏色（暫存器）下）。

如果暫存器太少怎辦，就只能spill（灑）到stack堆疊上面。

3-1

組合語言的calling conventions

L_var

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 的空間

相關說明：

• rax存運算結果
• rcx loop暫存
• rdx 資料暫存
• rsi rdi 索引指位

callee-saved register（存於callee被呼叫者的暫存器）

rbx, rsp, rbp, r12, r13, r14, r15

相關說明

• rbx 基底暫存
• rsp堆疊頂端
• rbp堆疊底端

• 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 A	rsp - 8 -> rsp; A -> *rsp	rsp往小移，再壓入(push)