編譯器 LLVM 淺淺玩

以動手實作來認識 The LLVM Compiler Infrastructure

Pokai Chang
Jun 14, 2017 · 12 min read
The LLVM logo is a stylized wyvern (a kind of dragon). Dragons have connotations of power, speed and intelligence, and can also be sleek, elegant, and modular (err, maybe not). In addition, there is a series of influential compiler books going back to 1977 which featured dragons on the cover. (http://llvm.org/Logo.html)

因為在學校修了編譯器設計,加上最近幾個月在研究 GraphQL、不久的未來想寫 Babel Plugin 的關係,就開始自學相關的編譯器(主要是 parser)知識,當然不惜繞點路,也要一窺以往 LLVM 只聞其聲、不見其型的神秘本體。

編譯 React Native iOS 的時候總會看到 LLVM 的字跡一閃而過,那時候只知道 LLVM 是某種編譯工具包,可能跟 HHVM 是一樣的東東(並不是)。

本文分為以下部分:

LLVM 簡介

由 Swift 之父 Chris Lattner 創造,並由 Apple 大力贊助,LLVM 最初是 Low Level Virtual Machine 四個字的縮寫,不過隨著專案的發展,LLVM 已經成為了一整套編譯器工具組合,官方也已經放棄 LLVM 四個字的縮寫意義,將專案的簡述訂為「The LLVM Compiler Infrastructure」。

就像官方給的副標一樣,我們可以將 LLVM 視為一個非常模組化的編譯器,對打造語言、研究編譯技術的開發者來說,其強大的地方在於可以將任一個部分抽換掉或插入新的模組,就可以做出一個新的語言、或是將現有程式移植到新硬體平台、或是為特定目的做最佳化後的編譯器。

典型的編譯器架構,分成 Frontend (Parser)、Optimizer、Backend (Code Generator) 三部分。Frontend 負責將原始碼解析成語法樹 (或其他適合的資料結構),Optimizer 負責尋找程式邏輯中有沒有可以簡化來提升執行速度的可能,並改良邏輯 (例如刪除 a = a + 0 這種無意義的指令),Backend 負責把低階的機器碼寫出來。(http://www.aosabook.org/en/llvm.html)

典型的編譯器可以分成 Frontend、Optimizer、Backend 三個部分。理論上我們可以拿 A、B 兩個語言的編譯器,把 B 的頭(Frontend)接到 A 的身體(Optimizer、Backend)上,就能獲的一個將 B 語言編譯到 A 所支援的平台上的新編譯器。

但一般編譯器即使架構上遵循 Frontend、Optimizer、Backend 分工,三者之間通常會做得密不可分,在互相交換資料時都走內部私有 API,這使得要修改現有編譯器來做出自己的編譯器相當困難,不同編譯器之間也無法共用已經實作完成的程式碼。

理論上我們只要把典型的編譯器架構的 Frontend 或 Backend 抽換掉,就可以變成不同程式語言到不同平台架構的編譯器。(http://www.aosabook.org/en/llvm.html)

而 LLVM 就是實現了這個理想狀況的編譯器工具包。

LLVM 編譯器架構。(http://www.aosabook.org/en/llvm.html)

LLVM 定義了一個通用的程式中介表示法,LLVM IR。LLVM IR 是一種類似機器語言,但為了通用性以及給編譯器設計者方便而簡化的版本。在 LLVM 的世界裡,大家都講 LLVM IR:Frontend 把原始語言的邏輯翻譯成 LLVM IR、Optimizer 把 LLVM IR 整理成效率更好的 LLVM IR、Backend 拿到 LLVM IR 來生成機器目標平台的機器語言。如此一來,無論是語言設計者想要創造一個新語言、演算法設計師想改進程式的效能、或是硬體或虛擬機製造者要做一個新的平台,都能得益於 LLVM 的世界,新語言只要設計好 frontend parser 就能使用現有的 optimizer 技術並編譯到各種不同平台、新的 optimizer 可以套用在各種語言和平台的編譯器上、新硬體或虛擬機只要支援 LLVM IR 就可以在上面跑各種主流語言。

LLVM 還有幾個我特別感到優良的特色,例如它的 optimizer 其實是由許多 pass 組成:

(https://www.cs.cornell.edu/~asampson/blog/llvm.html)

一個 LLVM Pass 的 input 是 LLVM IR,output 是經過特定改良的 LLVM IR。每個 LLVM Pass 都只會做一項改良(例如直接使用 register 中的值來做計算,而省下 memory 存取次數),而實際要編譯語言的時候,我們就可以依照語言與用途的特性,挑選適合的 LLVM Pass 來裝載。So functional, such pure function!

還有一點是,LLVM 包含了主流平台的 LLVM IR interpreter(或 JIT Compiler),也就是說,任何 LLVM 上的語言,可以是編譯語言(整份原始程式碼翻成 LLVM IR 並最佳化後,再編譯出機器語言執行),又同時也能用直譯的方式執行(一句一句把原始程式碼翻成 LLVM IR 並馬上拿來跑)!
Cling 就是基於這個架構做出來的 Interactive C++ Interpreter(類似 Ruby 的 、Python 的 Python Shell,是個在開發時測試 C++ 語法的方便工具)。

詳細可以參考 The Architecture of Open Source Applications: LLVM,有更詳盡的介紹。


LLVM 動手玩

本節分為以下幾個部分:

安裝

Linux 可以參考 http://apt.llvm.org/

在有安裝 Homebrew 的 Mac 上,可以 。但因為 Mac 系統已經有內建自己的 LLVM,為了避免新安裝的 LLVM 與系統工具衝突,Homebrew 並不會幫我們 link LLVM,所以在使用 LLVM 相關指令時,需要輸入絕對路徑,例如


C/C++ 編譯成 LLVM IR —

這裡我們使用 C 以及 LLVM 自帶的 C/C++ frontend — ,首先準備一份 C 原始碼,

main.c

然後下指令:

我們就會獲得一個 ,內容如下:

這就是由原始碼 編譯出來的 LLVM IR。


LLVM IR 直譯器 —

得到 之後,我們可以直接用 執行它,檢查執行結果是否符合預期:

的執行結果。

🎉 It works!


最佳化 LLVM IR — opt

讓我們觀察一下剛剛編譯出來的

看看這落落長的 function!這個編譯出來的函式,一共用了 8 個指令來計算兩個整數相加:

  1. :申請用來存放第一個整數的記憶體空間,並把記憶體位址放到 這個 register。(後面的 參數我還不太懂它的意義)
  2. :申請用來存放第二個整數的記憶體空間,並把記憶體位址放到 這個 register(註:在 LLVM IR 中,我們有無限個虛擬 register 可以用,LLVM 有辦法可以管理它們)。
  3. :將 ,也就是 function 的第一個參數值,放到 所指的記憶體空間(註:一般機器語言中,呼叫 function 時傳遞參數的原理,是將參數們依序放到 register 中,再將執行位置交給 function,所以在這裡的 ,就會是 )。
  4. :將 ,也就是 function 的第二個參數值,放到 所指的記憶體空間(註:所以 就相當於 C 原始碼的 相當於 )。
  5. :將 () 的值讀到
  6. :將 () 的值讀到
  7. :計算 + 並將結果放到
  8. :回傳

如果照原始語意,「先創造出 a、b 兩個變數,然後計算 a+b 的結果並回傳」,這樣的 IR 是合理的,但如果以目的來看,這樣的執行方式就顯得相當傻(看看那多此一舉的步驟 1~6)。

還好 frontend 傻瓜,optimizer 聰明。透過 這個工具,我們可以對現有的 LLVM IR code 執行指定的 optimizer pass:

參數表示印出 LLVM IR (而不是 bitcode), 意思是使用 Mem2Reg 這個 pass。比較一下原來的 function:

和 optimize 後的結果:

Mem2Reg 的作用就是分析 IR 中可以省略的記憶體操作,並且用 register 取代之。這裡它發現了原本指令 1~6 的記憶體存取是多餘的,於是將其省略,直接用 來做計算。

實際上在使用 opt 的時候,也可以一次選用多個 pass,例如:


LLVM IR 編譯成機器語言

最後,我們可以用 llc 把 LLVM IR 編譯成機器語言:

可以獲得

main.s

我們也可以進一步把 編譯成可執行檔:


結語

(期末爆炸中,略)(希望之後有時間補上 Lexical Analysis/lex、Syntax Analysis/yacc 的筆記)(前提是要先弄懂)

延伸資料

相關專案

  • Cling — The Interactive C++ Interpreter
  • The Rubinius Language Platform
    作者也正在寫一本關於編譯器設計和 Rubinius 設計哲學的書:The Rubinius Book。其實我還沒弄清楚這個專案的理念,目前感覺其目的是做一個 Ruby 版、類似 LLVM 的工具包,讓創造新語言的入門門檻變低,然後大家就能照自己的目的客製出適合的語言。 #回歸LCL之海不再戰語言
    “When confronted with A or B, consider why not A and B. In mathematics, there is the concept of a dual. For example, in Euclidean geometry, lines are dual to points. Take a theorem and swap lines for points and vice versa and the theorem is still true.” —
    The Rubinius Book: Preface

Pokai Chang

Written by

All-round developer. Tech stuff I studied & talked about: http://bit.ly/2DdA4wo . (Git, ReasonML, GraphQL, NixOS & stuff).

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade