在研究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)是個不錯的開始。

作者簡介


Advertisement

更多 iThome相關內容