April 5, 2011

透過 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)

/* emit file the header */
static void emit_header(FILE *fp)
{
    // first, define @op_out which corresponds to output
    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");
    // next, define @op_in which corresponds to input
    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");
    // now, define the actual program body
    GEN("define void @program() nounwind\n"
        "{\n"
        "entry:\n");
    // allocate the index stack slot...
    GEN("    %%index = alloca i64, align 8\n");
    // and stack space for the registers
    GEN("    %%registers = alloca [%d x i64], align 8\n", REG_COUNT);
    // set the initial index to 0
    GEN("    store i64 0, i64* %%index\n");
    // get a pointer to the first element of the registers
    GEN("    %%regroot = getelementptr [%d x i64]* %%registers, i64 0, i64 0\n", REG_COUNT);
    // clear all the registers
    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);
}

/* an add is any arithmetic, so a sequence of +s and -s */
static void emit_add(FILE *fp, long amount)
{
    int opID = rv++;
    if (amount == 0) // if we're not actually modifying, short-circuit
        return;
    // load the index...
    GEN("    %%idx%d = load i64* %%index\n", opID);
    // load the actual register...
    GEN("    %%ptr%d = getelementptr i64* %%regroot, i64 %%idx%d\n", opID, opID);
    GEN("    %%tmp%d = load i64* %%ptr%d\n", opID, opID);
    // perform the arithmetic...
    GEN("    %%add%d = add i64 %%tmp%d, %ld\n", opID, opID, amount);
    // and store.
    GEN("    store i64 %%add%d, i64* %%ptr%d\n", opID, opID);
}
/* this generic function does operation emission, all fairly obvious */
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;
        ...
}

/* real compiler - read in as brainfuck, compile to out as LLVM IR */
static void bfp(FILE *in, FILE *out)
{
    long amount = 0;
    BF_State state = BF_STATE_NONE;
    // emit the header
    emit_header(out);
    // loop through everything
    while (!feof(in)) {
        // basically, a finite state machine
        char ch;
        fread(&ch, 1, 1, in);
        /* Do arithmetic */
        if (state == BF_STATE_ARITHMETIC) {
            // if it is a + or -, adjust the working value
            if (ch == '+')
                amount++;
            else if (ch == '-')
                amount--;
            else {
                /* emit the instruction, push it back to be read next loop */
                emit(out, &state, ch, amount);
                ungetc(ch, in);
                amount = 0;
            }
        }
        ...
}

int main()
{
    /* open up llvm-as | opt -std-compile-opts | lli as a pipe
     * so that we pipe everything to the LLVM toolchain */
    FILE *asOut;
    asOut = popen("llvm-as | opt -std-compile-opts | lli", "w");
    /* run on stdin */
    bfp(stdin, asOut);
    /* tidy up */
    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]
/*
 * Sample Brainfuck JIT compiler using LLVM 2.8
 */
#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)
{
  // Some useful types and constants
  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);
 
  // declare i32 @getchar()
  Function* getchar = cast<Function>(
     module->getOrInsertFunction("getchar", cellType, NULL));
  getchar->setCallingConv(CallingConv::C);

  // declare i32 @putchar(i32)
  Function* putchar = cast<Function>(
     module->getOrInsertFunction("putchar", voidType, cellType, NULL));
  putchar->setCallingConv(CallingConv::C);

  // Contruct void main(char* tape)
  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 '[': {
        // Construct loop info
        bfLoopInfo loop;
        loop.beforeBlock = block;
        loop.startBlock = BasicBlock::Create(getGlobalContext(), "", main);
        loop.afterBlock = BasicBlock::Create(getGlobalContext(), "", main);
        loop.beforeValue = head;

        // Create branching instructions
        Value* headValue = builder.CreateLoad(head);
        Value* condition = builder.CreateIsNotNull(headValue);
        builder.CreateCondBr(condition, loop.startBlock, loop.afterBlock);

        // Create a phi node
        IRBuilder<> sbuilder(loop.startBlock);
        loop.startValue = sbuilder.CreatePHI(tapeType);
        loop.startValue->addIncoming(loop.beforeValue, loop.beforeBlock);

        // Push the loop
        loops.push(loop);
        block = loop.startBlock;
        head = loop.startValue;
        break;
      }
      case ']': {
        // Retrieve the loop info
        bfLoopInfo loop = loops.top(); loops.pop();
        loop.endValue = head;
        loop.endBlock = block;

        // Create a conditional branch
        Value* headValue = builder.CreateLoad(head);
        Value* condition = builder.CreateIsNotNull(headValue);
        builder.CreateCondBr(condition, loop.startBlock, loop.afterBlock);
        // Augement loops phi node
        loop.startValue->addIncoming(loop.endValue, loop.endBlock);

        // Switch to the after block
        block = loop.afterBlock;

        // Create a phi node
        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;
    }
  }

  // Close the function
  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;

  // Setup a module and engine for JIT-ing
  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;
  }

  // Compile the Brainfuck to IR
  std::cout << "Parsing..." << std::flush;
  Function* func = makeFunc(module, source.c_str());
  std::cout << " done" << std::endl;
 
#if 1
  // Run optimization passes
  std::cout << "Optimizing..." << std::flush;
  FunctionPassManager pm(module);
  pm.add(new TargetData(*(engine->getTargetData())));
  pm.add(createVerifierPass());
 
  // Process
  pm.run(*func);
  std::cout << "done" << std::endl;
#endif

  // Compile
  std::cout << "Compiling..." << std::flush;
  void (*bf)() = (void (*)()) engine->getPointerToFunction(func);
  std::cout << " done" << std::endl;

  // and run!
  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 發表於 April 5, 2011 11:34 PM
迴響
發表迴響









記住我的資訊?