如何評價只有 LLVM 10% 代碼的 QBE？

01-12

QBE - Compiler Backend

QBE…先抖個機靈再進正題。

作者眼中的QBE：

（圖片引用自QBE官網：QBE - Compiler Backend）

我眼中的QBE：

（圖片引用自：http://ringoon.jp/2011/02/26/-wqhd-ngp.html）

罠だ！騙されるな！

抖完機靈回到正題。最初看到這問題還以為是跟Android Runtime（ART）的Quick BackEnd相關的問題，進來點了鏈接才發現是另一個編譯器名字撞車了。

本回答未經許可請勿轉載喔。要轉載請在評論區或者私信與我聯繫。

============================================

如何評價X？

2016-04-24

QBE官方網站：QBE - Compiler Backend

作者在Hacker News上發的討論帖：Show HN: QBE - a new compiler back end

作者在Suckless社區郵件列表上發的討論帖：[dev] QBE - A Compiler Backend

看了作者Quentin Carbonneaux在QBE官網對項目的描述，也快速瀏覽了一下代碼，感覺這還是個很早期的項目，其實還無法對它做出什麼有用的評價。

所以下面全都是我的自言自語/廢話了。

作者拿QBE跟LLVM相比，強調重點是QBE追求簡單高效，以LLVM的10%的代碼達到其70%的性能水平。然而就其現有代碼和開發想法來看，它要麼得大幅增加代碼量，要麼是達不到「LLVM的70%性能水平」的…要比的話別拿人家的-O1來比70%啊，至少得來個-O2吧？

作者是為Suckless社區開發了QBE。這也就奠定了QBE的一些開發思路的基調：代碼簡潔，依賴最小，短小精悍。這個社區的精神有些可取的地方，但也有不少很教條的思維。例如說對C++的無條件憎惡，要寫底層代碼就要用C（或者彙編？）…

於是就有了這麼一個用純C實現的、簡單的、為了生成兼容C ABI的代碼而服務的編譯器後端。

如果大家沒聽說過的話，Suckless社區還有個自己的C語言編譯器，叫做SCC（Suckless C Compiler）：scc - suckless C compiler。QBE的設計目標之一就是作為SCC的後端使用。

初步評價：我對QBE還挺有好感，但覺得它未必能達到其聲稱的目標。

QBE代表了新一代練手用編譯器後端的一般水平。SSA形式IR、SCCP、簡單的指令選擇、SSA形式上的線性掃描寄存器分配（Linear-Scan Register Allocator over SSA form），最後簡單的手工代碼生成——集合了大部分直接依賴SSA形式的常用實用技術。

一個2010年後新寫的練手用編譯器後端，不做到上面這些都不好意思拿出來說。

（是的所以我都不好意思拿我自己的練手編譯器出來說，因為時髦值太低了…）

作者還想做但還沒實現的有全局值標號（GVN）和全局代碼調度（GCM）。我覺得要在當前的QBE上做簡單的GVN還挺容易，但是做GCM就不那麼方便了。

QBE目前基本上沒有針對循環的優化，而要加上循環優化就要加很多代碼了：描述循環嵌套結構的循環樹（loop tree）、基於依賴的分析（dependence-based analysis），然後配套的各種循環轉換（loop transformation）。

然後在別名分析（alias analysis） / 指針分析（pointer analysis）方面，QBE當前的設計都無法支持。不過原本C語言層面的類型就不可靠，QBE IR的精簡類型系統倒也不算是很大的損失吧orz

話說，QBE提及的優化里，隻字未提「函數內聯」（function inlining）這個有趣的點。當然，是否實現內聯對不同的編譯器的影響不一樣，做了越多過程內優化的編譯器越能得益於有效的函數內聯。

QBE至少實現了SCCP，如果能加上函數內聯的話SCCP就會更加有效——某些值可能在被函數里是參數，但在調用函數一側是個常量，如果調用方可以內聯被調用方，常量就可以傳播下去了。

這麼說作者是指望讓編譯器前端做好內聯么？

這些在當前的QBE里都無法直接支持而需要加新代碼。不做就不可能達到LLVM 70%性能，做了就代碼爆炸，作者會如何選擇呢？

希望這不是「新代碼是乾淨的」假象的又一例子——功能少的時候代碼當然乾淨，功能一多起來又會怎樣呢？

HN討論帖中有人提到的之前一個關於編譯器優化的討論值得大家思考：Compilers in OpenBSD。大家都不想要有bug的編譯器；但是大家同時也想要生成代碼質量好——也就是更加優化——的編譯器。魚與熊掌難以兼得啊。

IR設計

這話題讓我想起了另一個回答：如何設計三地址中間代碼的數據結構，以便於基本塊分析和代碼優化？ - RednaxelaFX 的回答

QBE IR設計文檔在這裡：QBE Intermediate Language

與LLVM IR有三種形式（內存形式、文本形式、bitcode形式）類似，QBE的IR也有內存和文本形式，不過構造內存形式的API暫時沒有公開給外部使用，外部必須用文本形式傳遞IR給QBE。

QBE IR是一種簡單的CFG+SSA形式的三地址IR。它允許輸入的IR是非SSA形式的，在內部它會把非SSA形式的IR構造為SSA形式。它支持兩種風格的非SSA形式輸入：

使用內存stack slot的alloca/load/store風格：跟LLVM的mem2reg做法類似，QBE也有memopt可以把這種風格的局部變數從內存形式提升為臨時變數形式；
非SSA的臨時變數風格：QBE支持輸入IR的臨時變數是非SSA形式的（可以有多次定義），在輸入到QBE內部之後會做SSA構造——插入Phi以及臨時變數重命名。

其中，後者是QBE作者自豪的賣點之一。實際看起來也挺好的。但這其實會影響到IR在內存中的表現形式——必須有分離的結構表示（臨時）變數和指令。

而相比之下，LLVM IR的指令就是值，沒有單獨的「變數」結構。LLVM的做法更加「一致」，不過前端要生成的IR指令條數確實會多那麼一些…是個見仁見智的地方。

QBE IR使用的類型系統是最簡的，跟常見於LIR（low-level IR）的相似，基本上只關心數據寬度以及是整數還是浮點，其它都不關心（指針也當作整數對待）。IR的正確性要由輸入的一側（編譯器前端）保證。

如果要做值域分析（range analysis）的話，這個類型系統還是太簡單了一些。也罷。

基於SSA形式的優化

前面提到了，QBE做的優化都是直接跟SSA形式相關的：

SSA形式的構造就隱含了複寫傳播（copy propagation）；
Sparse Conditional Constant Propagation（SCCP）：SSA形式上最經典的數據流分析/優化之一；
SSA形式上的線性掃描寄存器分配（Linear-Scan Register Allocator over SSA form）：利用SSA形式的干涉圖（interference graph）是chordal graph的性質，可以在不顯式計算干涉圖的條件下做出較好的寄存器分配。

這些都是SSA Book覆蓋了的知識點。為了時髦值，我推薦的編譯優化書單里也必須有這本書 &>_&<

作者在構造SSA形式時就對CFG使用了RPO（逆後序）的遍歷順序，基於同樣的遍歷順序做一個簡單的GVN也是很容易的。要不要幫它加一個呢…還是留給作者自己做好了。

其它好玩的編譯器後端？

其實最初了解QBE的設計時我就覺得這就像是LibJIT的現代版一樣——假如libjit誕生於今天的話，其設計與實現恐怕會跟QBE有更多相似之處吧。

（雖說QBE的主要使用場景是用於靜態編譯器的後端，而libjit是用於JIT編譯器的後端，但這個差別對這兩者來說並不重要。libjit其實也支持把編譯後的代碼存到硬碟上，也就是說其實也支持靜態編譯的場景）

Android Runtime（ART）的「Optimizing」編譯器後端也是一個現代的簡單的基於SSA形式的實現。它跟QBE一樣，一層SSA形式的IR貫穿於整個編譯流程，做得相當精巧；而與QBE不同的是，這個Optimizing編譯器的類型系統是比較高層的，更貼近Java源程序層面——Java語言的強類型系統可以讓這個編譯器做更多基於類型的優化。

ART Optimizing編譯器我之前在另一個回答里提到過：ART和JIT的除了編譯的時機區別以外，對於編譯的方式有什麼區別嗎？ - RednaxelaFX 的回答

要說跟LLVM比更輕量的編譯器後端，最近搞出了大新聞的Apple WebKit B3（Bare Bones Backend）也可以看看。採用純SSA形式的HIR，精簡的類型系統，這些都與QBE有相似之處。

B3與QBE簡單對比如下，反映了它們的應用場景和設計思路的異同：

（異）B3有2層IR，作為高層IR（HIR）的B3 IR，和作為低層IR（LIR）的Assembly IR（「Air」）；QBE目前則只有一層比較低層的IR。B3 IR包含一些帶有JavaScript語義的opcode，以便在它的應用場景中減少IR的大小。
（同）B3 IR與QBE IR都是以SSA形式為主，但同時也提供非SSA形式方便前端的中間代碼生成；兩者都同樣會在自己內部對非SSA形式的IR做一次SSA構造。不過B3更傾向於前端直接輸入SSA形式的IR，畢竟在JavaScriptCore中跟它搭配使用的DFG前端自身就是用SSA形式的IR。
（同）B3與QBE都採用精簡的類型系統。
（異）B3採用圖著色寄存器分配演算法（graph-coloring register allocator），而QBE採用SSA形式上的線性掃描。前者更重量級一些，不過以後B3或許也會嘗試使用線性掃描的變種。
（異）B3更注重作為JIT的場景，包含一些與運行時交互的功能，例如patchpoint。QBE只注重作為靜態編譯器後端的場景。

傳送門：[新聞][JavaScript引擎] WebKit JavaScriptCore用新的B3編譯器後端替代FTL JIT中的LLVM - 編程語言與高級語言虛擬機雜談（仮） - 知乎專欄

比起傳統的CFG+SSA形式的IR，我對Sea-of-Nodes形式的IR還是更有好感一些。Cliff大神萬歲！用了Sea-of-Nodes的話，要做GVN和GCM簡直易如反掌——不，應該說想不做都不行（逃

採用了Sea-of-Nodes形式的用C寫的編譯器後端有一個不錯的先例了，libFirm是也。libFirm也有配套的C99前端，可以構成一個完整的C編譯器，比起QBE我對libFirm要有愛得多。

libFirm雖然現在的代碼量看起來很可觀，但其實其核心代碼也可以控制得很小，現有的很多代碼是各個基於libFirm寫論文的學生給加進去的，很多都可以剝離出來而不影響libFirm的核心功能。如果剝離出一個跟目前的QBE功能（優化程度）相似的核心的話，代碼量和編譯速度說不定都比目前的QBE要更好。

我平時工作的主要內容是HotSpot Server Compiler（C2），同樣是採用Sea-of-Nodes形式的IR。C2是我的摯愛。跟LLVM相比，C2也算是個「簡單」的編譯器了，其IR形式和實現思路都是在盡量優化的前提下少付出開銷。要是C2在代碼層面能現代化一下就完美了…

或許Graal編譯器算是C2的完美形態的Java版吧。

許多人（包括QBE的作者）對Sea-of-Nodes IR有很深的誤解，覺得它作為一種基於圖的IR，一定要用某種graphical visualizer才可以看IR，而不能用文本形式。

其實這完全是多慮了。想想看，LLVM IR和QBE IR都是帶有CFG（控制流圖）的，這圖在文本形式的IR上有體現成「圖」么？沒有吧？只是用label和jump就足以表達出圖的邊了。

Sea-of-Node IR的文本表現也是一樣，其實完全可以「寫成」像線性代碼一樣的形式，在讀入內存的時候才把其「圖」的一面表現出來。沒有控制依賴的節點（floating node）可以在文本形式中先隨便找個基本塊先放著，反正載入進內存之後它就又浮動起來了。

最後，大家有興趣看看 @stevenknown大大主導設計實現的XOC編譯器不？

GitHub - stevenknown/xoc: XOC is a compiler infrastructure that provides multi-level operations, flexibility, and the capability of representing almost all popular languages.

我去看了作者與大家在Show HN: QBE a€「 a new compiler back end的討論（推薦大家也看看），裡面透露了很多信息，我也不重複了。而諸如允許SSA Form和非SSA Form的兩種形式也都討論的差不多了， @RednaxelaFX 也補充了很多知識，而我卻也和帖子一位回復的一樣，若給予的是非SSA，內部卻依然通過插入Phi來轉為SSA的話，我想我其實不喜歡這樣的IR語法糖。

文中提到了編譯速度以及執行速度的比較，提到了編譯速度很快，但是執行速度比GCC慢。然而我比較務實，若談論到C ／ C++的性能測試，我想至少應該上C ／ C++ 編譯器比較通用的測試集SPEC 2006 和 SPEC V6，然而再來看編譯時間和性能時間，因為大家做C ／ C++編譯器都會跑這些性能測試集，這樣也會讓他的QBE比較有說服力。但是，我目前對基於QBE的C前端質量有疑問，我認為可能很難跑起來SPEC 2006 和 SPEC V6，所以我期待著作者以後可以上這樣的數據。

看了Hack News的相關討論，我暫時就想到這麼多吧，我會持續關注這個項目的。

你說只有llvm80%的代碼量那值得去看看

只有10%…… 那就只說明一點：這東西還遠未完成唄

編譯器那麼多功能都得一行行代碼來實現，同樣的功能你的代碼比別人短小精悍是可能的，少到這種程度是不可能的，又不是玄學。

何況llvm本身很多部分都還很弱。

正確的提問應該是拿QBE完成的某部分和llvm來比較

初步看了下代碼，比較輕量級，但代碼風格不是很喜歡啊。並且作者提供的文檔也較少，倒是參考資料很喜歡。

滿滿的民科味。LLVM是站在巨人肩上的項目，QBE是站在地上就想干翻巨人。

* 70%的性能怎麼測？用什麼測？還不是自說自話，搞不好最後是hello world達到了70%的性能；別的平均50%都不到。

* 當前只對簡單的語言環境，搞不好是只支持個hello world之類的吧？來個指向指針的指針數組指針估計就掛了

* 對C有多少兼容？搞不好就支持個hello world之類的兼容吧。

* IEEE浮點數，long double支持嗎？

* 基於SSA也好意思說？還不是學LLVM。

* Copy elimination不清楚指啥

* 常數傳播，隨便一個解釋器都能做到，有啥好說的？

* 死代碼消除，這個LLVM前端都做了，有啥好說的？

* 簡單棧寄存器分配一下，多大事？

。。。太多了，吐槽不過來

關於idea，

* 把a[0]+a[1] 變成scalar數相加么？應用場景都沒想清楚

* 找相同運算（GVN）？處理個a+b這種難度的吧。

* 循環代碼遷移（GCM）？把個a+b這種難度的移出來吧。

* undef ？還不是學LLVM？

* 控制流簡化？還不是學LLVM吧？

好像也沒有更多的idea了。

這種東西有啥好評價的？渣渣一樣的項目，作者對編譯也就理解個皮毛。還想和LLVM相比？扯！