Essentials of Compilation筆記

出自Tan Kian-ting的維基
跳至導覽 跳至搜尋

概要

  • 這基本上是印第安納大學的各編譯器老師的結晶
  • 講述必要的觀念、演算法、如何利用映射的觀念將上層軟體對應到硬體
  • 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（泛型）

Ch1

提到以下名詞：

  • 遞迴函數
  • 模式比對
  • 抽象語法樹
  • 程式語言語法


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的頭和尾）

Ch3

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


相關說明：

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

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

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

相關說明

  • rbx 基底暫存
  • rsp堆疊頂端
  • rbp堆疊底端
  • call-live variable（會被用的變數）

我們要找到同時使用的變數和不同時使用的變數，來節省暫存器的使用，這是一種圖著色問題。


  • 第三章（記憶體分配的「頂點著色問題」跳過）。
    • 註：Danny說頂點著色是用最多邊頂點先著色的啟發法，如果寄存器不夠多，就spill放置於記憶體內。

Ch4 加入布林值和if

  • (not 1) -> 返回#f
  • (car 1) -> 返回error
  • 本書用Typed Racket的作法，並且拒絕 (not 1)

Ch 4.1 布林運算

加入布林型別，還有二元運算，還有p.63的type checker 相關語法如下：

(cmp atom atom) (not atm) (goto label) 

if (cmp atm atm)
goto label
else goto label


(if::= (label tail) ... x86程式也添加bytereg 

instr : xorq, cmpq, set, movzbq, jmpif, ...
  • (and e1 e2) = (if e1 e2 #f)
  • (or e1 e2) = (if e1 #t e2)

type check class 

operate_types = function( ){
{"+", ((int int) -> int)},
{"-", ((int int) -> int)},
...
}


List 要逐項確認型別 map(型別 list)

Ch5 迴圈和資料流分析

  • #<void>也是value，是副作用的set!傳回結果
  • set!方能動態更改值 * 用資料流分析，來分析各變數的生存長度！
  • “Kleene fixed-point analyzation”
  • (begin! (set! x 40) x)變成
    • (begin (set! x 40) (get! x))
  • uncover-get!

ch6 tuple(類似陣列)和垃圾回收

  • tuple(類似array)，用compluter的heap -> tuple 的生命週期為定義
  • 可是要清掉，不然會out of memory，所以需要垃圾回收
  • 相關程式碼：
    • (vector x1 x2 x3) vector-ref vector-set! (vector-length exp) type ::= (vector type*)
  • vector 沒有動態的scope
  • garbage collection ->
    • 保留活變數
    • 釋放垃圾
  • p.102 垃圾回收
    • 本書未另外教學如何寫垃圾回收
    • 本書使用Cheney’s algorithm來辦理垃圾回收
    • Heap有tuple等object
    • 分兩區，runtime時互換：
      • FromSpace
      • ToSpace
    • 拷貝自heap有連結的stack，至另一個tospace
    • 不連結引用的，不拷貝。
  • p.104 cheney’s algorithm看不太懂
  • Ch 6.2.3 資料代表：本書選用1,2兼用：
    1. 物件加上tag表示指標與否
    2. 存在不同資料分區
    3. 用型別資訊來處理
    • 指標遮罩 (pointer mask)
    • 垃圾回收器在runtime.c實作
  • 6.3 展示分配 (expose allocation) exp :== (collect int) | (allocate int type) | (global-value name)

Ch 7 函數

  • p.127 講函數實作： (apply exp exp*)
type ::= (type ... -> type)
exp ::= (exp exp...)
def ::= (define (var [var : type] [var : type] ...) : type exp)
L_fun ::= def .... exp
(def (inc [x : integer]): integer (+ x 1))
  • 呼叫函數：
leaq    inc(%rip)  %rbx
callq   *%rbx
  • rax放置return value
  • 參數置放區：rdi rsi rdx rcx r8 r9
    • 參數小於6個，超過6個，多出來的放進去向量：f(x1, x2, x3, x4, x5, [x6, x7, ....])
  • 尾遞迴最佳化

ch8 lexical function scoping

(define (f [x : int]) : (int -> int)
let y = 4
return lambda (z : int) : int => {x + y + z})

上面的式子裡，lambda 是 lexical scoping 相關的匿名函數，其實是閉包。

本章講到flat closure的實作，以及conversion 

exp ::= (lambda [(var : type)...]) : type exp)
(procedyre-arity exp) ; 求exp (function) 的參數數量
L_lambda = def ... exp

fv variable要放在heap上面，但需要boxing變數

  • p.151 實作兩個函數
  • free_variable
  • fv_in_lambda
  • let 的被代入變數以及是 lambda的自由變數，方需要boxing
  • convert_assignment 來提到這個問題：(box <-> unbox)
  • 把 free_variable 轉成vector (heap 上)
  • (Var x)
  • p.153
    • (lambda parameters return_type body) -> (closure 參數數量 (cons (FunRef name 參數) free_variables))
  • closure conversion 看不太懂
def f6(x7):
    y8 = 4
    return lambda(z9){x7 + y8 + z9}

let x = 3
let f = lambda (y){x + y + 3};

lambda (ps){body} // ps 指參數
=> lambda (ps, fv) => {body} // fv 指自由變數

let fv = [x]//

這裡的fv 可以用

fv = malloc(x);
fv[0] = x;
...
這樣的

f3(x, b, c)=> f3(fv[3], b, c)

Ch9 dynamic typing

動態型別 + polymorphism 

exp ::= (exp ...) |
| (lambda (var ...) exp)
| (boolean? exp)
| (integer? exp)
| (vector? exp)
| (procedure? exp)
| (void? exp)

def ::= (define (var var...) exp)
L_dyn ::= def ... exp
tagged_value = structTagged {value, tag(type)} #: transparent
tagof(integer) = (001)_2
tagof(boolean) = (002)_2
...
用數字表示型別tag（型別編號）
(Inject exp type) # 轉為tagged
(Project exp type) # 取消轉為tegged

any-vector-length | any-vector-ref | any-vector-set!

Ch10 gradual typing

  • p.179 L_? : 混合靜態、動態型別 -> type_annotation，有無gradual typing
parameter ::= var | [var : type]
ret ::= ε|type

* (cast val type1 type2) ; 改變型別
* 看不太懂gradual type
  • 經過ChatGPT的說明，這是混合不標型別和強制標型別的方式。但是對我來說沒什麼用，不如全部強制指定型別，一來提昇執行速度，二來讓使用者不會誤解一個物件的型別

Ch 11 多型實作方法

map 可為 (forall (T) (T->T) -> (vector T) -> (vector T))

這需要型別推論設計

要轉成函數，可以用

  1. uniform intersection: tagged box化的物件，設計函數於執行時偵測型別，再依標籤決定處理型別，但效率慢
  2. 轉成多個處理單型別的函數，但是code生成會很多，而且沒有擴展性

附錄：指令集摘

指令名 操作說明 註
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)
取自「https://kianting.info/wiki/index.php?title=Essentials_of_Compilation筆記&oldid=2982」