透過 LLVM 打造 Brainfuck JIT compiler
本文是補充今年在 [
OSDC.tw] 演講〈Build Programming Language Runtime with LLVM〉的實做部份，並且透過逐步使用 [
LLVM] 的方式，分析 LLVM 的應用途徑。
首先，回顧 Chris Lattner 與 Vikram Adve 在 2004 年提出經典論文 [
LLVM: A Compilation Framework for Lifelong Program Analysis & Transformation] 的結論，LLVM 是如何進行多階段的優化呢？
- 編譯時期優化：語言前端 (如 llvm-gcc 與 clang) 將原始程式碼轉為 LLVA (Low-level Virtual Instruction Set Architecture)，這是一個 RISC 形式的虛擬指令集，儘管是低層次的表示法，但允許保留部份高階資訊，本身甚至考慮到 OOPL 的需求
- 連結時期 (Link-Time) 優化：顧名思義，將若干 object code 進行 relocation 等一系列複雜的操作，成為執行檔或者動態函式庫。傳統來說，這階段應該是目的硬體架構的 native code，但 LLVM 提供其特有的 bitcode，又因為上一個階段保留了若干高階資訊，所以可進行 LTO (Link-Time Optimization)
- 執行時期 (Runtime) 優化：對進階的編譯的系統來說，產生可執行的程式檔 (廣義包含可透過 VM/interpreter 執行的 P-code) 並非最終的階段，因為我們仍可透過執行時期產生的 profile 資訊，繼續作優化，也就是所謂的 FDO (Feedback-Directed Optimization)。在 LLVM 中，這部份可以是直接執行生成的執行檔，或者是執行 bitcode，而這兩者都與 CFG (Call-Flow Graph) 與 (動態) 型態資訊有關，這允許施行更激進的優化演算法
- Offline 優化：在實務上，要對整個程式作執行時期的完整 FDO，可能太耗費資源，甚至在標的環境中也不允許生成 / 分析龐大的 profile 資訊，那該怎麼辦呢？系統可先將 profile 資訊保存起來，然後再適合的時機才 offline 取出，進行優化的程序。這種方式跟 LTO 有點相似，不過後者並沒有 profile 資訊，而前者則具備，因此可更精確，而且也不需要變更編譯程式的流程
本文實驗的環境為 Ubuntu Linux 11.04 (natty) x86 32-bit，系統安裝了 LLVM 2.8 與對應版本的 [
clang]，目標設定為，透過 LLVM 重寫之前的實驗 [
打造 Brainfuck 的 JIT compiler]，關於 Brainfuck 語言及相關資訊，已在前文解釋，不贅述。具體來說，以下是本文的探討方向：
- 觀察 LLVM IR (中間表示式)
- 觀察 LLVM 宣稱的「多階段優化」，並且使用相關工具
- 使用 libLLVM API 來打造 Brainfuck JIT compiler
Brainfuck 語言雖然僅有八道指令 (instructions)，但其中兩項就是進行 I/O 動作，對應於 C 語言則是：
- '.' -> putchar()
- ',' -> getchar()
我們先寫一個簡單的 C 語言測試程式，呼叫到 putchar() 函式： (test-output.c)
#include <stdio.h>
int main() {
putchar('J');
return 0;
}
假設 $PATH 已正確指定 LLVM 與 clang 的路徑，先編譯 LLVM 的 bitcode 來觀察：
$ clang -emit-llvm test-output.c -c -o test-output.bc
我們也可驗證生成的 test-output.bc 檔案：
$ file test-output.bc
test-output.bc: LLVM bitcode
的確是貨真價實的 LLVM bitcode，而 LLVM 也提供了一個特製的 interpreter，在設計之初，即考量到 JIT compiler 的整合，簡單的執行方式如下：
$ lli test-output.bc
J
正如預期，透過呼叫系統 libc 的 putchar() 函式，輸出了 'J' 字元。而 LLVM IR 就是整個 LLVM 設計的關鍵，我們當然不容忽略，來觀察反組譯的結果：
$ llvm-dis < test-output.bc
這時候應該會見到如下的輸出：(省略 target 描述)
define i32 @main() nounwind {
%1 = alloca i32, align 4
store i32 0, i32* %1
%2 = call i32 @putchar(i32 74)
ret i32 0
}
declare i32 @putchar(i32)
LLVA / LLVM IR 的組合語言非常高階，我們可對照之前的 C 語言程式碼，會發現有顯然的對應，初步觀察如下：
- C 語言的 int 型態被 clang 語言前端轉為 "i32"
- main() 與 putchar() 前冠以 '@' 符號，表示函式呼叫
- 'J' 字元在 ASCII 的序號為 74，此數值被帶入 putchar() 函式，也就是 putchar('J')
- LLVM IR 本身是 register based 的操作，load-store 架構
驗證觀察最好的方式，就是實地寫程式。官方手冊 [
LLVM Language Reference Manual ] 有非常詳盡的說明，那我們先來延伸上面的 LLVM 組合語言輸出，嘗試作以下修改：
- 將 putchar('J') 改為 puts("Hello, World!")
- 縮減 unwind 一類屬性 (attribute) 的使用，這與例外處理機制有關，但並非本文的重點，略過
建立一個名為 hello.ll 的檔案，其內容為：
@str = internal constant [14 x i8] c"Hello, World\00"
define i32 @main() {
call i32 @puts(i8* getelementptr ([14 x i8]* @str, i32 0, i32 0))
ret i32 0
}
declare i32 @puts(i8*)
C-style 字串 "Hello, World!" 長度為 14 bytes，單位型態為 char，也就是對應於 LLVM 的 "i8"。值得注意的是，"getelementptr" 這道指令的使用方式。由於 putchar() 與 puts() 兩個函式最大的差異，就在於後者接受的參數為 const char * 型態指標，我們就得先透過 getelementptr 這道指令，取出保存常數 (即 "Hello, World!" 字串) 的位址。組譯並執行看看：
$ llvm-as hello.ll
$ lli hello.bc
Hello, World!
如我們預期，正確的顯示字串 "Hello, World!"。此外，LLVM 編譯器系統的特色就是提供豐富的優化與便利的擴充，可使用 opt 工具來對 LLVM bitcode 作複雜的優化與分析：
$ opt --help
OVERVIEW: llvm .bc -> .bc modular optimizer and analysis printer
...
參考的使用方式：
$ opt -std-compile-opts test-output.bc test-output-opt.bc
$ wc -c test-output.bc test-output-opt.bc
484 test-output.bc
472 test-output-opt.bc
顯然經由 opt 優化的 bitcode，其空間使用已被調整，詳情可參考 [
opt - LLVM optimizer]。
Brainfuck 語言最大的貢獻，就是證明符合 Turing complete 的程式語言，可藉由極少的指令來實現 (不過比 Brainfuck 更「精簡」的語言也存在，如 Whitespace)。對於如此洗練的語言，我們的策略就是將 Brainfuck 語意 / 指令集先轉為 LLVM IR，然後透過 LLVM 豐富的機制來作 code generation 與 optimization。本文的重點就是讓讀者體驗到，「外包」(outsource) JIT compiler 的高度便利。
為了符合這個策略，我們得先把 Brainfuck 轉成 LLVM IR，最簡單的方式，就是作字串處理，也就是「窮人 JIT compiler」，可參考 [
bfc.c]，以下是重點程式碼：
#define GEN( ...) \
do { \
fprintf(fp, __VA_ARGS__); \
} while (0)
static void emit_header(FILE *fp)
{
GEN("define internal void @op_out(i64 %%val) nounwind\n"
"{\n"
"entry:\n"
" %%conv = trunc i64 %%val to i32\n"
" %%call = tail call i32 @putchar ( i32 %%conv ) nounwind\n"
" ret void\n"
"}\n\n"
"declare i32 @putchar(i32) nounwind\n\n");
GEN("define internal i64 @op_in() nounwind\n"
"{\n"
"entry:\n"
" %%call = tail call i32 @getchar() nounwind\n"
" %%conv = sext i32 %%call to i64\n"
" ret i64 %%conv\n"
"}\n\n"
"declare i32 @getchar() nounwind\n\n");
GEN("define void @program() nounwind\n"
"{\n"
"entry:\n");
GEN(" %%index = alloca i64, align 8\n");
GEN(" %%registers = alloca [%d x i64], align 8\n", REG_COUNT);
GEN(" store i64 0, i64* %%index\n");
GEN(" %%regroot = getelementptr [%d x i64]* %%registers, i64 0, i64 0\n", REG_COUNT);
GEN(" %%ptrconv = bitcast i64* %%regroot to i8*\n");
GEN(" call void @llvm.memset.i64(i8* %%ptrconv, i8 0, i64 %d, i32 8)\n", REG_COUNT * 8);
}
static void emit_add(FILE *fp, long amount)
{
int opID = rv++;
if (amount == 0) return;
GEN(" %%idx%d = load i64* %%index\n", opID);
GEN(" %%ptr%d = getelementptr i64* %%regroot, i64 %%idx%d\n", opID, opID);
GEN(" %%tmp%d = load i64* %%ptr%d\n", opID, opID);
GEN(" %%add%d = add i64 %%tmp%d, %ld\n", opID, opID, amount);
GEN(" store i64 %%add%d, i64* %%ptr%d\n", opID, opID);
}
static void emit(FILE *out, BF_State *state, char lastChar, long amount)
{
switch (*state) {
case BF_STATE_ARITHMETIC:
emit_add(out, amount);
*state = BF_STATE_NONE;
break;
...
}
static void bfp(FILE *in, FILE *out)
{
long amount = 0;
BF_State state = BF_STATE_NONE;
emit_header(out);
while (!feof(in)) {
char ch;
fread(&ch, 1, 1, in);
if (state == BF_STATE_ARITHMETIC) {
if (ch == '+')
amount++;
else if (ch == '-')
amount--;
else {
emit(out, &state, ch, amount);
ungetc(ch, in);
amount = 0;
}
}
...
}
int main()
{
FILE *asOut;
asOut = popen("llvm-as | opt -std-compile-opts | lli", "w");
bfp(stdin, asOut);
pclose(asOut);
return 0;
}
編譯並執行：
$ clang -o bfc bfc.c
$ ./bfc < hello.bf
Hello World!
初步驗證我們的想法，當然這段程式碼用 Ruby 一類的語言撰寫，可能更合適些，但至少先掌握 LLVM IR 的表現，有助於日後改進 Brainfuck JIT compiler 的設計。LLVM IR 以 SSA (Static Single Assignment) form 為主軸，也就是說，除了 Brainfuck 程式的流程控制外，我們的重心會在 SSA form 的 Phi node，可參照 LLVM 官方的文件 [
LLVM Tutorial]。
以下是透過呼叫 LLVM API 來實現 Brainfuck JIT compiler 的執行引擎實做，且包含 Optimizer： [
bf-llvm.cpp]
#include <stack>
#include <fstream>
#include <iostream>
#include <llvm/Module.h>
#include <llvm/Function.h>
#include <llvm/PassManager.h>
#include <llvm/CallingConv.h>
#include <llvm/Analysis/Verifier.h>
#include <llvm/Support/IRBuilder.h>
#include <llvm/ExecutionEngine/ExecutionEngine.h>
#include <llvm/Target/TargetData.h>
#include <llvm/LinkAllPasses.h>
#include <llvm/ExecutionEngine/JIT.h>
#include <llvm/Target/TargetSelect.h>
#include <llvm/LLVMContext.h>
using namespace llvm;
struct bfLoopInfo {
Value* beforeValue;
PHINode* startValue;
Value* endValue;
Value* afterValue;
BasicBlock* beforeBlock;
BasicBlock* startBlock;
BasicBlock* endBlock;
BasicBlock* afterBlock;
};
Function* makeFunc(Module* module, const char* source, int tapeSize = 400)
{
const Type* voidType = Type::getVoidTy(getGlobalContext());
const IntegerType* cellType = IntegerType::get(getGlobalContext(), 8);
const IntegerType* indexType = IntegerType::get(getGlobalContext(), 32);
const PointerType* tapeType = PointerType::get(cellType, 0);
Value* zero = ConstantInt::get(cellType, 0);
Value* one = ConstantInt::get(cellType, 1);
Value* minOne = ConstantInt::get(cellType, -1);
Function* getchar = cast<Function>(
module->getOrInsertFunction("getchar", cellType, NULL));
getchar->setCallingConv(CallingConv::C);
Function* putchar = cast<Function>(
module->getOrInsertFunction("putchar", voidType, cellType, NULL));
putchar->setCallingConv(CallingConv::C);
Function* main = cast<Function>(
module->getOrInsertFunction("main", voidType, NULL));
main->setCallingConv(CallingConv::C);
BasicBlock* block = BasicBlock::Create(getGlobalContext(), "code", main);
std::stack<bfLoopInfo> loops;
IRBuilder<> codeIR(block);
Value* head = codeIR.CreateAlloca(cellType, ConstantInt::get(indexType, tapeSize));
Value* it = head;
for (int i = 0; i < tapeSize; i++) {
codeIR.CreateStore(zero, it);
it = codeIR.CreateGEP(it, one);
}
while(*source) {
IRBuilder<> builder(block);
switch(*source++) {
case '>': head = builder.CreateGEP(head, one); break;
case '<': head = builder.CreateGEP(head, minOne); break;
case '+': {
Value* headValue = builder.CreateLoad(head);
Value* result = builder.CreateAdd(headValue, one);
builder.CreateStore(result, head);
break;
}
case '-': {
Value* headValue = builder.CreateLoad(head);
Value* result = builder.CreateSub(headValue, one);
builder.CreateStore(result, head);
break;
}
case '.': {
Value* output = builder.CreateLoad(head);
builder.CreateCall(putchar, output);
break;
}
case ',': {
Value* input = builder.CreateCall(getchar);
builder.CreateStore(input, head);
break;
}
case '[': {
bfLoopInfo loop;
loop.beforeBlock = block;
loop.startBlock = BasicBlock::Create(getGlobalContext(), "", main);
loop.afterBlock = BasicBlock::Create(getGlobalContext(), "", main);
loop.beforeValue = head;
Value* headValue = builder.CreateLoad(head);
Value* condition = builder.CreateIsNotNull(headValue);
builder.CreateCondBr(condition, loop.startBlock, loop.afterBlock);
IRBuilder<> sbuilder(loop.startBlock);
loop.startValue = sbuilder.CreatePHI(tapeType);
loop.startValue->addIncoming(loop.beforeValue, loop.beforeBlock);
loops.push(loop);
block = loop.startBlock;
head = loop.startValue;
break;
}
case ']': {
bfLoopInfo loop = loops.top(); loops.pop();
loop.endValue = head;
loop.endBlock = block;
Value* headValue = builder.CreateLoad(head);
Value* condition = builder.CreateIsNotNull(headValue);
builder.CreateCondBr(condition, loop.startBlock, loop.afterBlock);
loop.startValue->addIncoming(loop.endValue, loop.endBlock);
block = loop.afterBlock;
IRBuilder<> abuilder(block);
PHINode* headPhi = abuilder.CreatePHI(tapeType);
headPhi->addIncoming(loop.beforeValue, loop.beforeBlock);
headPhi->addIncoming(loop.endValue, loop.endBlock);
head = headPhi;
break;
}
default:
break;
}
}
IRBuilder<> builder(block);
builder.CreateRetVoid();
return main;
}
int main(int argc, char* argv[])
{
if (argc < 2) {
std::cerr << "Usage: " << argv[0] << " bf_file" << std::endl;
return -1;
}
std::ifstream sourceFile(argv[1]);
std::string line, source;
while (getline(sourceFile, line)) source += line;
std::string error;
InitializeNativeTarget();
Module* module = new Module("bfcode", getGlobalContext());
ExecutionEngine *engine = EngineBuilder(module)
.setErrorStr(&error)
.setOptLevel(CodeGenOpt::Aggressive)
.create();
if (!engine) {
std::cout << "No engine created: " << error << std::endl;
return -1;
}
std::cout << "Parsing..." << std::flush;
Function* func = makeFunc(module, source.c_str());
std::cout << " done" << std::endl;
#if 1
std::cout << "Optimizing..." << std::flush;
FunctionPassManager pm(module);
pm.add(new TargetData(*(engine->getTargetData())));
pm.add(createVerifierPass());
pm.run(*func);
std::cout << "done" << std::endl;
#endif
std::cout << "Compiling..." << std::flush;
void (*bf)() = (void (*)()) engine->getPointerToFunction(func);
std::cout << " done" << std::endl;
bf();
return 0;
}
在 LLVM CodeGen 後，我們設定了 OptLevel 為 CodeGenOpt::Aggressive 等級，這樣在 optimization pass 時，會 Just-In-Time 產生特定的機械碼。編譯並執行驗證：
$ clang++ bf-llvm.cpp \
`llvm-config --cppflags --ldflags --libs core jit native all` \
-o bf-llvm
$ ./bf-llvm hello.bf
Parsing... done
Optimizing...done
Compiling... done
Hello World!
充分準備後，關於 JIT 與 CodeGen 的議題，都交給 LLVM 去處理即可。
由 jserv 發表於
11:34 PM
|
迴響 (0)