[分享] gross: 一個實驗性的編譯器作業
有版友建議可以多分享一些簡單、有趣的編譯器專案
本魯就來拋磚引玉一下 來分享一下去年我修的一門課做的作業
https://github.com/mshockwave/gross
當時花了大概花了10個星期做這個專案 不算長也不算太短
雖然裡面有很大一部分是實驗性質、不太常見的設計，但就是因為實驗性質所以沒有做的
很複雜（掩面）因此只要修過研究所編譯器課程 在理解上應該都沒什麼太大問題
這邊挑幾個重點來講一下：
- src/Frontend
很普通的 Lexer, Parser。由於我們的輸入語言是一個簡單的教學用程式語言（好像就
叫做PL241 XDD)，用非常簡單的top-down parser就能做完。唯一跟一般 parser 不一樣
的是 parser 會直接生成 IR 而不是 AST。會這樣做到也不是沒時間做，而是等下會提到
的實驗性 IR 其中一個設計哲學就是「整個編譯的流程、都盡量用同一種資料結構」
更具體來說的話就是整個流程都用 Graph 來代表
換句話說，就是不再有
Source Code -> AST -> IR -> Native Code
而是：
Source Code -> Graph IR -> Native Code
雖說如此，整個編譯器依然是階段性地慢慢把輸入的高階程式碼 一步一步的轉化為低階
機器碼。其中關鍵就是雖然整個流程裡面都是用 Graph，但其中的 vertex 在每一個階段
的抽象程度不一樣。
例如剛從 Parser 出來的 Graph 每個節點都是非常高階的結構像是 "While" "If-Else"
但是之後就會慢慢降成 "jump", "branch" 等等較為低階的概念
- src/Graph
這邊放的就是前述 Graph IR 的實作。我這個資料夾的 README 花了非常多篇幅在描述
三種不同的 edge ... 有點複雜所以這邊就不提了。用最簡單的說法的話就是每個
edge 都代表一個dependency，而設計來能夠表示三種不同的dependency的原因在於
希望能讓某些優化比較好做。例如最惡名昭彰(笑)的 memory side effect，如果我們
能夠在一開始就把這些 side effect 明確地表示出來(因為或許能從一些高階資訊中
獲得)、而不是等到要用的時候才在那邊分析，在優化上可能會比較輕鬆
- src/Graph/Reductions
雖然這個資料夾有一個酷炫的名字，但其實就是普通的優化而已XD 會取名為 reduction
單純只是因為如果你在 Graph IR 上做優化，大部分時候都是逐漸把 Graph 簡化。這邊
放的優化也只有最簡單的那幾個：CSE, Peephole, ValuePromotion(mem2reg)
- src/CodeGen
謝天謝地這個作業只要生成一個超簡單、教學用的指令集(DLX)。所以雖然這個資料夾有
一堆檔案，但真的只是一些必要的東西像是 scheduling, RA, instruction selector
值得一提的是在之前用的 Graph IR 沒有 basic block 的概念(一個函式就是
一個完整的Graph)，一直到最終在 scheduling 、要把這個 Graph 做 "linearlize"
轉成一串instruction序列的時候才有 basic block 的概念出現
以上就是幾個有趣的部分，希望大家能從這個實驗性的專案裡面得到一些靈感:)
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 169.234.228.227 (美國)
※ 文章網址: https://www.ptt.cc/bbs/CompilerDev/M.1596602334.A.CDD.html
推
08/05 18:43,
3年前
, 1F
08/05 18:43, 1F