不只是虛擬機的LLVM

在研究WebAssembly的過程中，經常會發現LLVM一詞相伴在旁，在程式語言的支援方面，只要能產生LLVM IR，就能編譯為WebAssembly。

我不禁好奇了，什麼是LLVM？IR是位元組碼嗎？LLVM是又一個虛擬機嗎？

什麼是LLVM？

能將C/C++編譯為asm.js的Emscripten專案，源自Mozilla工程師Alon Zakai在研究LLVM的時候，產生了將C/C++編譯為JavaScript的想法，他將C/C++編譯為LLVM IR，然後透過一個LLVM後端（back end）產生asm.js，現在，也可以將asm.js轉換為WebAssembly。

如果進一步查詢LLVM的資料，我們就會發現，Clang、Swift、Rust等語言，在編譯器的實現上，都以LLVM做為後盾。

根據維基百科〈LLVM〉目前的記載，其命名最早源自於Low Level Virtual Machine，起源於2000年Vikram Adve與Chris Lattner的研究，到了2005年，蘋果電腦雇用了Chris Lattner及其研究團隊，開發應用程式系統，而使得LLVM為現今Mac OS X及iOS開發工具的一部分。

雖然一開始VM代表著虛擬機的縮寫，實際上LLVM專案在後續不斷成長的過程中，發展出一整套的編譯器工具鏈，不再限於虛擬機器，LLVM這個詞後來像是個商標，代表著一套龐大的編譯器基礎設施。同時，LLVM官方網站也使用The LLVM Compiler Infrastructure，作為標題描述，突顯其作為編譯器基礎設施的目標。

〈WebAssembly現狀與實戰〉（https://goo.gl/anFbRf）談到：「每個高級語言都去實現源碼到不同平臺機器碼的轉換工具是重複的」，這適當點出了LLVM的目標，可以基於LLVM實現一個前端（front end），將某個語言轉換為LLVM IR（Intermediate Representation），中間的最佳化與轉換目標，可交由LLVM Optimizer及後端來處理。

對於語言的實作者來說，這無疑是個福音，因為他們可以專注在詞法與語法分析（LLVM不處理詞法與語法分析，這些是Lexer、Yacc等工具處理的範疇），將語言轉換為LLVM IR，接著善加利用LLVM的生態，就可以令語言執行於不同平臺，而LLVM官方網站〈LLVM Tutorial〉（https://goo.gl/dkLFQH）也談到，如何在建立語法樹之後，透過程式碼產生器來生成IR，以及進一步添加JIT及Optimizer最佳化支援。

LLVM的架構

在〈Intro to LLVM〉（https://goo.gl/eLevbN）中，清楚解釋了LLVM的架構。

當中提到：傳統編譯器在設計時，基本上，也是區分前端、Optimizer與後端等三個階段──在前端產生語法樹之後，會選擇性地產生位元碼之類的中介表示；Optimizer的部份，負責最佳化等事務；而後端運行程式，以JVM為例，Java位元組碼就是前端與Optimizer之間的介面。

理論上，這樣的模型，只要適當替換前端、後端，例如，將一個ToyLang的前端接到ARM的後端，就可以讓ToyLang編譯到ARM上運行，然而，不同編譯器之間，在彼此的溝通上，往往採用了不同的方式，像是不同的內部API實現，或者不同的中介表示方式，因此，使得替換前端、後端的想法難以實現。

LLVM的架構得以實現如此想法，關鍵在於LLVM IR，前端將語言轉為IR，Optimizer接受IR，進行最佳化後產生更有效率的IR，後端接受IR並產生目標平臺需要的（機器）語言，因為溝通都採用同一種表示方式，這就使得每個階段，都可以有各自實作、改進的可能性。

在LLVM中，Optimizer是由一連串個別的pass組織而成，具體來說，是衍生自Pass類別的C++類別，基本上，每個Pass只做一項改善，根據〈LLVM for Grad Students〉（https://goo.gl/RAxtSh），Pass之間也是接受IR產出IR，不太需要擔心改善要放在哪，只要安插在前、後端之間的某處就可以了，正如文中提到的「這就是你可以Hack的地方」（This is where you want to hack）。

這也是LLVM IR有別於Java之類位元組碼的地方，因為，LLVM IR有三種定義形式，其中之一，就是二進位形式的位元碼（bitcode），儘管兩者的名稱看來類似，然而，前述的位元組碼是虛擬機器的執行指令形式，位元碼是編譯器多個階段間溝通用的表現形式。

小試LLVM

如果想要體驗一下LLVM，我們可以透過Clang來達成目的。就像在Ubuntu 18.04中，我們可以使用apt-get install安裝clang與llvm-runtime，前者可以在編譯時產生LLVM IR，後者提供了lli等指令。例如將簡單的Hello

例如，在簡單的Hello World的main.c，我們可以使用指令clang -S -emit-llvm main.c，當中的-S，表示只做前置處理與編譯步驟，這就會得到一個main.ll，其內容是人類可讀的文字格式，為LLVM IR三種定義形式之一（第三種是記憶體中的資料結構），可參考〈LLVM Language Reference Manual〉（https://goo.gl/D5UYub）瞭解相關指令之作用，接著，我們可使用llvm-as指令，轉換為二進位形式的位元碼，這會產生main.bs檔案。

如果用clang時，想直接生成.bs，可用clang -c -emit-llvm main.c -o main.bc、llvm-dis，則能將二進位形式的位元碼，轉換回文字格式的IR；若使用llc指令，則可以將IR編譯為機器碼。

無論是main.ll或main.bs，都可以透過lli載入執行，如果想要最佳化IR，可以使用opt指令，指定要最佳化的Pass，也能在輸入opt -help後，查看Optimizations available，瞭解有哪些最佳化的選項，像是-constprop（constant propagation）、-die（Dead Instruction Elimination）等。

對於這些指令有進一步興趣，可參考〈Getting Started with the LLVM System〉（https://goo.gl/DV5wxW），其中的〈Example with clang〉就包含了以上指令的示範。

用於實作語言

說了這麼多，我對LLVM感興趣的原因，當然是希望未來可以用於實作語言。

就像先前提過的〈LLVM Tutorial〉，大致上示範了一些步驟，若想實作一門圖靈等價的語言，我認為，Brainfuck是個不錯的對象，實際上，LLVM本身的範例，就包含了BrainF（https://goo.gl/RPyKCe）的實現。

〈My First LLVM Compiler〉（https://goo.gl/XY3wLr）中，說明了如何使用LLVM來實作Brainfuck，在臺灣，黃敬群（jserv）也於〈透過LLVM 打造Brainfuck JIT compiler〉（https://goo.gl/R4RWQu）探討過實作，並有不少LLVM的影片、文件等資源分享。

實際上，也不一定要用於實作語言，整個LLVM生態是龐大的，可以依開發者的需求或興趣，來切入不同的部份，例如，個別的IR最佳化、後端目標的生成等。

若從沒接觸LLVM，想要對LLVM有個快速的認識，COSCUP 2016的〈LLVM框架,由淺入淺〉場次影片（https://goo.gl/UUMB5E）是個不錯的開始。