LLVM & Rubinius

LLVM 是 Low Level Virtual Machine,
最早聽到他，是透過 Rubinius, 一個完整 Ruby VM 實作計畫。
剛開始我對這個計畫不感任何興趣，因為實際測試他的效能，真的是慢到很恐怖的境界。
記得也在哪裡看到作者說，如果他們推出一個 Ruby VM 1.0, 結果效能是 MRI
(Matz's Ruby Implementation) 的十倍慢，應該沒有人能接受這種結果吧？
因此這個計畫乍看之下進展非常緩慢，做了很久也才 0.9 alpha 而已。

記得我上次測試，rubinius 真的慢到很恐怖，比 1.8 還要慢很多倍。
不過他可以產生像是 python pyc 的 rbc, 讓我覺得應該多少還可以期待吧？
畢竟，每個人都說這個 project is very promising.

同時，如果有跟著他們的進度在跑，觀察 commit 狀況，就會發現 rubinius
活躍度其實非常非常高，commit 量相當驚人。我第一次聽到 git 也是透過這個計畫，
那時覺得 git 一點都不快啊，svk 可能都還比他快很多吧？後來才發覺，根本就不是
git 慢，而是 rubinius 整個 repository 實在是太大了！這個情況下，
如果用 svn 去跑的話，大概會慢到瘋掉吧？

所以我想如果他們聲稱用到了各種先進技術，確實是不為過。想想 MRI 現在在用什麼？
svn + autotools. 而 rubinius 則是用 git + rake + cmake (branch) +
llvm (branch), 除此之外還有 MRI 一直沒做的 RubySpec, 衍生出的 MSpec,
等等一堆東西..... 也需要 bootstrap! 因為 compiler 是用 ruby 寫成的。

這麼龐大的計畫，用到了各種不同的東西，中間也換了好幾次所用的工具，
能寫到這種程度，真的是很厲害。就算效能比起 1.9 的 YARV 差了一截，
仍然覺得也許全部寫完，真正開始做 optimize 時，能夠超越 YARV?

不過他們的目標其實是高擴充性、高維護性的 VM. 這點 MRI 應該完全比不上...
ruby core developer 的功力應該是不弱，這沒問題。但感覺對於開發大型
open source 專案，還有非常多的不足。


*


扯遠了，回到 llvm. 原本 rubinius 用的 vm 叫 shotgun, 是用 c 寫成的。
後來整個 vm 用 c++ 重寫，再過一陣子之後，則又引入 llvm. 我不是很確定原本的
c++ vm 跟 llvm 之間有什麼關係，因為到現在我還是不太確定 llvm 的範圍大概在哪？
可以參考日前在 iis mailing list 上所寫的：

from godfat 真常
to Shin-Cheng Mu
cc IIS Mu's Research Group
date Thu, Oct 2, 2008 at 3:18 PM
subject Re: Meeting.. postpone?
mailed-by godfat.org

On Thu, Oct 2, 2008 at 2:34 PM, Shin-Cheng Mu wrote:
> Do any of you have some proposed topic? If not, let's
> postpone the meeting.

I have taken a look at:
http://blog.fallingsnow.net/2008/05/23/simple-vm-jit-with-llvm/
yesterday, thinking if this was interesting to investigate.

I've heard LLVM ( http://llvm.org ) times ago,
but never taken a look at it. There's an issue in Ruby's issue tracker:
http://redmine.ruby-lang.org/issues/show/340
talking about compiling Ruby via llvm-gcc4.

This catches my eyes, and I wish I could spend some time
taking some experiment on LLVM.

Have anyone heard LLVM before?
I think it's interesting why Rubinius ( http://rubini.us/ )
decide to reimplement their VM with LLVM though
many works has been put on the old VM Shotgun (which is written in C).


No, I can't say anything about LLVM right now (or in recent days?). XD
I was just wondering if anyone heard this before or was interested about.

--
cheers,
飽和脂肪星 http://godfat.org/

godfat 真常

於是我終於開始找時間試試這個 llvm, 主要是用 10-10 那天，上禮拜浪費掉了，
希望這個三天週末可以有比較理想的運用。讓我感到很困擾的則是，上面那 blog post,
應該就是 runinius 主要作者 evanphx. 剛閱讀時，認為這篇文章淺顯易懂，
是個拿來測試 llvm 不錯的開始。無奈真正開始閱讀程式碼時，就認為他應該不太熟悉
c++, 很多地方都寫得很不好，感覺有非常多 c 的影子在裡面... 導致我看不太懂。

先跳過那些寫得怪怪的地方，程式運作看半天，總覺得他所說的 optimization,
其實根本就是用手打出來的嘛？？裡面的 our program, 根本就沒有任何 parse 的動作，
是直接忽略那個 0, 1, 2. 如果把那 0, 1, 2 改成 9, 9, 9 也不會有任何影響。
這樣又到底是在做什麼？？？跟他所說希望能做到的事，好像沒什麼關係啊？

不過個人在還沒真的動手前，理解能力似乎很低。所以還是決定改寫他的程式，
希望能從中搞懂他到底在幹什麼？因此第一步就是把很 c 的寫法改掉...
還有他那個 MemoryBuffer 的 check 根本沒任何意義，成功的話沒差，
失敗的話 jit->getFunction 就 null pointer access...

算了，也許他只寫了五分鐘，因此很多小細節都沒處理好，就不管他了。
我一樣可以改寫他的程式來測試。從這邊出發會比較容易，因為 llvm 的文件，
實在太多太雜了，基於我欠缺太多基礎知識，看那些文件恐怕要看很久很久...
想找個輸出 bytecode 到檔案的方法都找不到 @_@
還有各種 machine code emitter...


*


大抵上而言，改寫是很順利。儘管很久沒寫 c++ 了，有些命名都忘記了...
下一步則是把他改寫成能夠針對任何 bytecode, 而不是完全暴力寫下去，
根本忽略 source program 長啥樣子...

因此我仍然會需要一個 switch, 在裡面根據 0, 1, 2 產生 set, add, show.
也要把 std::vector<Value*> params3; 抽到迴圈裡面。

在這邊，我撞壁撞到非常不爽。不知道為什麼，不管我怎麼寫都怪怪的？
例如由於要丟給 CallInst::Create 的 params 會是 [ops, register],
而 ops 會改變，我就把 vector 反轉，接著丟給他 rbegin 和 rend.
因此我的 vector 會是 [register, ops], 丟給他的則是 [ops, register]
這樣我就能夠用 pop_back + push_back 改變 ops 的值。

結果光改這樣居然就會 segfault @@

我甚至想乾脆用 deque push_front 和 pop_front, 但沒道理啊？？
於是改變策略，我倒轉 register 和 ops, 讓 register 成為第一個參數。
這邊也讓我卡很久，因為最後的：

fp(registers, ops);

忘記翻轉，結果不斷 segfault 找不到原因 orz
這樣 cast 真的太暴力了，不過一時三刻我也沒辦法找 type safe 的方式，
畢竟這就要比較深入去看 llvm 才會知道了。現在要先會跑比較重要...

接著 register 和 ops 反轉成功後，就開始改寫 source program 了。
無奈的是，只有他的範例能跑！如果我中間插入一些無關的操作，
整個程式不會 segfault, 但是會跑出很奇怪的數字出來...

我研究了好幾個小時，仔細比對他輸出的 assembly 和我輸出的 assembly,
都已經做到完全一樣了，為什麼我只要稍微一改就會怪掉？？

同時，我也非常不明白，為什麼他會有這行：

%tmp31 = getelementptr i32* %ops, i32 4

我不懂 assembly, 從來沒看過也從來沒寫過。但是還是覺得這行有點怪，
畢竟，我們現在就是要讓 ops 會往前移動不是嗎？但是這裡又跳回 ops 的頭？
但是作者畢竟是 evanphx, 我又對 assembly 沒有任何經驗，就不疑有他，
只是不斷測試其他部份...

同時，由於現在 program 是寫死在 .cpp 裡面，重新 compile 很慢，
就順手改寫成輸入 byte array, 想把 ops 改成 byte array.
不過一跑就 type error XD

  Function* main = cast<Function>(jit->getOrInsertFunction("main",
      Type::VoidTy,
      PointerType::getUnqual(Type::Int32Ty),
      PointerType::getUnqual(Type::Int32Ty),
      static_cast<Type*>(0)));

這裡兩個型別都是 int 32, 我改成 char* 的話，llvm 就會抱怨 type 不合。
一時三刻我也找不到 llvm 使用 char* 的方式，只好還是用 int array,
把 input byte array 轉型成 int array:

    std::string program;
    getline(std::cin, program);
    std::vector<int> ops(program.begin(), program.end());

然後由 ruby 輸入 source program:

puts(
"\000\000\003"     + # res[0] = 3
"\001\000\000\004" + # res[0] = res[0] + 4
"\002\000"           # puts res[0]
)

執行就是：

> ruby program.rb | ./vm

果然可以如期輸出 7.

接著又在無數奇怪輸出之後，我開始懷疑根本就是 evanphx 寫錯了！
上面值得懷疑的那行：

%tmp31 = getelementptr i32* %ops, i32 4

根本就應該是：

%tmp31 = getelementptr i32* %tmp3, i32 4

吧？？？這樣 ops 才會向前 step 啊。而且這樣我程式還能簡化，
不用一直保留 ops. 就可以很單純 pop_back + push_back.
一試之後，還真的這樣就完全正常了...... 就可以任意寫 source program,
不會再吐出奇怪的結果了！不然原本連跑 show 都會改到 register, 超怪的...

我還一度懷疑 register 該不會是只能存一次，然後資料就會不見？？
請原諒我有這麼愚蠢的懷疑，畢竟從來沒學過這麼低階的東西，我也不知道
register 實際上是指什麼？只是當成 memory 來用...


*


總之，寫到這裡，大概就可以確定一些事。

1. evanphx 的範例寫錯了，能跑只是正好而已...（虧我相信你，浪費一堆時間 =_=）

2. llvm 就如同其名，是 low level virtual machine,
所以他提供了一套 llvm assembly, 可以直接用手寫 assembly,
或是用他提供的 api 將你的程式 compile 成 llvm assembly.
此外可以做最佳化，然後生出各種不同的 machine code.

3. 所以 llvm 用在 rubinius 上，推測應該是先用 ruby compiler
把 source program compile 成 rubinius bytecode,
然後再用 llvm 把 rubinius bytecode compile 成 llvm assembly,
接著就可以在 llvm 這個 virtual machine 上運作了。

4. 由於 llvm-gcc, 大部份 gcc 支援的語言，應該都可以 compile 成
llvm bytecode, 就能夠讓 llvm 動態讀入並執行。因此，要擴充就變得相當容易！

5. 如此執行架構就會變得非常龐大，我還需要仔細想想這樣的優勢在哪裡？

6. evanphx 的範例沒有提到任何 header file 和 compile option,
害我一開始 compile 時搞得非常痛苦，一個個去試要 link 哪些東西？
所有的 .a 都 link 完還是不對！要連 .o 都一起 link...
header file 則是靠閱讀 include path 推測和 global search 找出來的。

幾個小時後，總算 compile 成功，但一跑居然會 segfault...
於是我開始懷疑是不是該到 linux 上去試？
亂翻之下，才發現有 llvm-config 這東西，
但 fish 上的 () 和 bash 上的 `` 執行結果好像不太一樣，
不管我怎麼試都失敗！改用 bash 才成功了 @@


*


以下附上程式碼，同樣是 Apache License 2.0

// bash -c "g++-mp-4.3 vm.cpp -o vm -std=c++98 `llvm-config --cxxflags --ldflags --libs`"

// ruby program.rb | ./vm

#include <llvm/Type.h> // for Type
#include <llvm/Function.h> // for Function
#include <llvm/Module.h> // for Module
#include <llvm/PassManager.h> // for PassManager
#include <llvm/Support/MemoryBuffer.h> // for MemoryBuffer

#include <llvm/Bitcode/ReaderWriter.h> // for ParseBitcodeFile
#include <llvm/DerivedTypes.h> // for PointerType
#include <llvm/Instructions.h> // for CallInst
#include <llvm/Constants.h> // for ConstantInt
#include <llvm/ModuleProvider.h> // for ExistingModuleProvider
#include <llvm/ExecutionEngine/JIT.h> // for ExecutionEngine

// #include <llvm/Target/TargetData.h> // for TargetData
// #include <llvm/Analysis/Verifier.h> // for createVerifierPass
// #include <llvm/Transforms/IPO.h> // for createLowerSetJmpPass
// #include <llvm/Transforms/Scalar.h> // for createCFGSimplificationPass

#include <boost/lexical_cast.hpp>

#include <string>
#include <vector>
#include <iostream>

using namespace llvm;

Module* load(){
    std::string error;
    Module* jit = 0;

    // Load in the bitcode file containing the functions for each
    // bytecode operation.
    if(MemoryBuffer* buffer = MemoryBuffer::getFile("ops.o", &error)){
        jit = ParseBitcodeFile(buffer, &error);
        delete buffer;
    }
    return jit;
}

Function* init_main(Module* jit, std::vector<Value*>& params){
    // Now, begin building our new function, which calls the
    // above functions.
    Function* main = cast<Function>(jit->getOrInsertFunction("main",
        Type::VoidTy,
        PointerType::getUnqual(Type::Int32Ty),
        PointerType::getUnqual(Type::Int32Ty),
        static_cast<Type*>(0)));

    // Our function will be passed the ops pointer and the
    // registers pointer, just like before.
    Function::arg_iterator args = main->arg_begin();
    Value* registers = args++;
    registers->setName("registers");
    Value* ops = args++;
    ops->setName("ops");

    // Set up our arguments to be passed to set.
    params.push_back(registers);
    params.push_back(ops);

    return main;
}

Module* compile(std::vector<int> ops){
    using boost::lexical_cast;

    Module* jit = load();
    if( !jit ) return 0;

    // Pull out references to them.
    Function* set  = jit->getFunction("set");
    Function* add  = jit->getFunction("add");
    Function* show = jit->getFunction("show");

    std::vector<Value*> params;
    Function* main = init_main(jit, params);

    BasicBlock* bb = BasicBlock::Create("entry", main);

    for(int i = 0, step = 0; i < ops.size(); i += step){
        // Setup and call add, notice we pass down the updated ops pointer
        // rather than the original, so that we've moved down.
        GetElementPtrInst* ptr;
        CallInst* call;
        ConstantInt* const_n;

        if(step != 0){
            const_n = ConstantInt::get(APInt(32, lexical_cast<std::string>(step), 10));
            ptr = GetElementPtrInst::Create(params.back(), const_n, "tmp", bb);
            params.pop_back(); params.push_back(ptr);
        }

        switch(ops[i]){
            case 0:
                // Call out to set, passing ops and registers down
                call = CallInst::Create(set, params.begin(), params.end(), "", bb);
                // add 3 to the ops pointer.
                step = 3;
                break;

            case 1:
                call = CallInst::Create(add, params.begin(), params.end(), "", bb);
                // Push the ops pointer down another 4.
                step = 4;
                break;

            case 2:
                call = CallInst::Create(show, params.begin(), params.end(), "", bb);
                step = 2;
                break;
        }
    }

    // And we're done!
    ReturnInst::Create(bb);

    return jit;
}



int main(int argc, char* argv[]){
    // The registers.
    int registers[] = {0, 0};

    // Our program.
    // int program[] = { 0, 0, 5,
    //                   1, 0, 0, 4,
    //                   2, 0 };

    std::string program;
    getline(std::cin, program);
    std::vector<int> ops(program.begin(), program.end());

    // Create our function and give us the Module and Function back.
    Module* jit = compile(ops);

    // Add in optimizations. These were taken from a list that 'opt', LLVMs optimization tool, uses.
    PassManager p;

    // Comment out optimize
    // p.add(new TargetData(jit));
    // p.add(createVerifierPass());
    // p.add(createLowerSetJmpPass());
    // p.add(createRaiseAllocationsPass());
    // p.add(createCFGSimplificationPass());
    // p.add(createPromoteMemoryToRegisterPass());
    // p.add(createGlobalOptimizerPass());
    // p.add(createGlobalDCEPass());
    // p.add(createFunctionInliningPass());

    // Run these optimizations on our Module
    p.run(*jit);

    // Setup for JIT
    ExistingModuleProvider* mp = new ExistingModuleProvider(jit);
    ExecutionEngine* engine = ExecutionEngine::create(mp);

    // Show us what we've created!
    std::cout << "Created\n" << *(jit->getFunction("main"));

    // Have our function JIT'd into machine code and return. We cast it to a particular C function pointer signature so we can call in nicely.
    Function* func = jit->getFunction("main");
    void (*fp)(int*, int const*) =
        reinterpret_cast<void (*)(int*, int const*)>(engine->getPointerToFunction(func));

    // Call what we've created!
    fp(registers, &*ops.begin());
}