LLVM Introduction – How to use LLVM JIT 3/3

Copyright (c) 2011 陳韋任 (Chen Wei-Ren)

2. 實驗 2/2 – 使用 LLVM JIT

ExecutionEngine 是一個關鍵的類別。它能把 Module 中的特定 Function 動態編譯成 host binary。此外,它還提供介面供使用者提取 JIT-ted function (host binary) 的資訊。

本實驗補上前篇實驗的後半部。附件是完整的代碼。

#include "llvm/LLVMContext.h"
#include "llvm/Module.h"
#include "llvm/Function.h"
#include "llvm/PassManager.h"
#include "llvm/Analysis/Verifier.h"
#include "llvm/Assembly/PrintModulePass.h"
#include "llvm/Support/FormattedStream.h"
#include "llvm/Support/IRBuilder.h"
 
// LLVM JIT 所需的頭文件
#include "llvm/ExecutionEngine/JIT.h"
#include "llvm/ExecutionEngine/GenericValue.h"
#include "llvm/Target/TargetSelect.h"
#include "llvm/Support/ManagedStatic.h"
 
using namespace llvm;
 
Module* makeLLVMModule(LLVMContext& ctx);
 
int main(int argc, char**argv) {
 
  // 根據 host 初始化 LLVM target,即針對哪一個 target 生成 binary。
  InitializeNativeTarget();
 
  LLVMContext Context;
 
  Module* Mod = makeLLVMModule(Context);
 
  verifyModule(*Mod, PrintMessageAction);
 
  PassManager PM;
 
  PM.add(createPrintModulePass(&outs()));
  PM.run(*Mod);
 
  // 根據給定的 Module 生成 ExecutionEngine。
  ExecutionEngine* EE = EngineBuilder(Mod).create();
 
  // 在 Module 中插入新的函式 (Function)。若該函式已存在,返回該函式。
  // 因此這邊取回 makeLLVMModule 所插入的 gcd 函式。
  Function *GCD =
      cast(Mod->getOrInsertFunction("gcd",
      /* 返回型別 */                        Type::getInt32Ty(Context),
      /* 參數 */                            Type::getInt32Ty(Context),
      /* 參數 */                            Type::getInt32Ty(Context),
      /* 結尾 */                            (Type *)0));
 
  // 準備傳給 GCD 的參數。
  std::vector Args(2);
  Args[0].IntVal = APInt(32, 17);
  Args[1].IntVal = APInt(32, 4);
 
  // 將參數傳給 gcd。將其 JIT 成 host binary 並執行。取得執行後的結果。 
  GenericValue GV = EE->runFunction(GCD, Args);
 
  outs() << "---------\nstarting GCD(17, 4) with JIT...\n";
  outs() << "Result: " << GV.IntVal <freeMachineCodeForFunction(GCD);
  delete EE;
  llvm_shutdown(); // 釋放用於 LLVM 內部的資料結構。
  return 0;
}

眼尖的你應該會發現我似乎忘了 delete Mod。很好! 但是你一但加上 delete Mod,執行之後會出現 segmentation fault。試試看! 😉

答案在 EngineBuilder 的註解裡 “the created engine takes ownership of the module”。

  /// EngineBuilder - Constructor for EngineBuilder.  If create() is called and
  /// is successful, the created engine takes ownership of the module.
  EngineBuilder(Module *m) : M(m) {
    InitEngine();
  }

我還漏了底下這一行沒講清楚。

  verifyModule(*Mod, PrintMessageAction);

什麼時候 Module 是非法的? 舉例來說,假設 Module 裡面有底下這樣一條 LLVM 指令。

  %x = add i32 1, %x ; x = 1 + x

直覺上來看很正常。但是 LLVM IR 滿足 SSA (Static Single Assignment) 的形式,亦即每條賦值指令都會生成一個新的變數。所以上面這條指令應該是底下這樣:

  %x1 = add i32 1, %x ; x1 = 1 + x

SSA 能夠簡化資料流 (data flow) 的分析,有助於後續的優化。大部分的編譯器 (我只確定 GCC 和 LLVM) 的 IR 主要都是採 SSA 的形式。

最後,各位要注意 LLVM API 不穩定。看各位是要緊跟 svn 版本進行開發,又或是只跟 release 版本開發。這其中各有利弊,但是別忘了 LLVM 算是很熱心的一個 community, 我想有問題都可以到郵件列表或聊天室詢問。[1][2]

[1] http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
[2] http://llvm.org/docs/#irc

LLVM Introduction – How to use LLVM JIT 2/3

Copyright (c) 2011 陳韋任 (Chen Wei-Ren)

2. 實驗 1/2 – 建立 LLVM Module

我們來動手一試吧! 本實驗參考LLVM Tutorial 2: A More Complicated Function,但使用的是 LLVM 2.9 Release。注意! LLVM API 較不穩定,請根據 LLVM 實際版本參照相對應的文件。

本實驗是要用 LLVM IR 實現一個 Greatest Common Divisor (GCD) 演算法,最後使用 LLVM JIT 生成 binary 並執行。GCD 演算法的 C 代碼如下:

unsigned gcd(unsigned x, unsigned y) {
 
    if ( x == y ) {
        return x;
    } else if ( x < y ) {
        return gcd( x, y - x );
    } else {
        return gcd( x - y, y);
    }
 
}

上述代碼的 control flow graph (CFG) 請見 LLVM Tutorial 2: A More Complicated Function。好! 我們開始吧。:-) 使用 LLVM JIT 基本上有底下幾個步驟:

  • 創建或是讀入 LLVM Module。Module 是 LLVM IR 的容器。先在 Module 中建立函式,再於函式中建立基本塊,最後在基本塊中填入 LLVM IR。[1][2][3]
  • 於我們所建立的 LLVM IR 上施行優化 (可選)。在 LLVM 中,優化的過程稱為 pass。pass 也可以是僅將 LLVM IR 做些轉換而非優化。[4]
  • 呼叫 LLVM JIT,將 LLVM IR 編譯成 host binary。
  • 取得被編譯成 host binary 的 function pointer。透過呼叫該 function pointer 執行並取得結果。

本實驗做到步驟 2,下一個實驗會補上 3 和 4。因為 LLVM API 較不穩定,請善用 LLVM API Documentation 查詢 API 使用方法。

/*
 *  $ g++ tut2.cpp `llvm-config --cxxflags --ldflags --libs all` -o tut2
 *  $ ./tut2
 */
 
#include "llvm/LLVMContext.h"
#include "llvm/Module.h"
#include "llvm/Function.h"
#include "llvm/PassManager.h"
#include "llvm/Analysis/Verifier.h"
#include "llvm/Assembly/PrintModulePass.h"
#include "llvm/Support/FormattedStream.h"
#include "llvm/Support/IRBuilder.h"
 
using namespace llvm;
 
Module* makeLLVMModule(LLVMContext& ctx); // 負責創建 LLVM Module。
 
int main(int argc, char**argv) {
 
  // LLVMContext 是較晚期才加入 LLVM 的類別。
  // 其作用是管理 LLVM core infrastructure 中的 global data。
  // 多執行緒的情況下,每個執行緒都應該要有自己的 LLVMContext。
  // 請見 llvm/LLVMContext.h。 
  LLVMContext Context;
 
  Module* Mod = makeLLVMModule(Context); // 呼叫 makeLLVMModule 取得 LLVM Module。
 
  verifyModule(*Mod, PrintMessageAction); // 驗證此 Module 是否合法。
 
  PassManager PM; // 所有的轉換或是優化均被視為 pass,由 PassManager 進行調度。
 
  PM.add(createPrintModulePass(&outs())); // 加入打印 LLVM Module 內容的 pass。
  PM.run(*Mod); // 於該 Module 運行 pass。
 
  delete Mod;
  return 0;
}
 
Module* makeLLVMModule(LLVMContext& ctx) {
  /* 尚未實作 */
}

現在我們知道大致的架構,接著我們來看怎麼實現 makeLLVMModule。這裡做點弊,我們先來看最後 LLVM IR 的輸出,先有個感覺。;-)

; ModuleID = 'tut2'

define i32 @gcd(i32 %x, i32 %y) {
entry:
  %tmp = icmp eq i32 %x, %y
  br i1 %tmp, label %return, label %cond_false

return:                                           ; preds = %entry
  ret i32 %x

cond_false:                                       ; preds = %entry
  %tmp2 = icmp ult i32 %x, %y
  br i1 %tmp2, label %cond_true, label %cond_false1

cond_true:                                        ; preds = %cond_false
  %tmp3 = sub i32 %y, %x
  %tmp4 = call i32 @gcd(i32 %x, i32 %tmp3)
  ret i32 %tmp4

cond_false1:                                      ; preds = %cond_false
  %tmp5 = sub i32 %x, %y
  %tmp6 = call i32 @gcd(i32 %tmp5, i32 %y)
  ret i32 %tmp6
}

開始囉!

Module* makeLLVMModule(LLVMContext& Context) {
 
  Module* M = new Module("tut2", Context);
 
  // 在 Module 中插入新的函式 (Function)。若該函式已存在,返回該函式。
  Function *gcd =
      cast(M->getOrInsertFunction("gcd",
      /* 返回型別 */                        Type::getInt32Ty(Context),
      /* 參數 */                            Type::getInt32Ty(Context),
      /* 參數 */                            Type::getInt32Ty(Context),
      /* 結尾 */                            (Type *)0));
 
  // 分別將 gcd 的參數命名為 x 和 y。使將來的輸出較易懂。
  Function::arg_iterator args = gcd->arg_begin();
  Value* x = args++;
  x->setName("x");
  Value* y = args++;
  y->setName("y");
 
  // 在函式中插入基本塊 (BasicBlock)。基本塊內含 LLVM IR,並以
  // terminator instruction 結尾,請見
  // http://llvm.org/docs/LangRef.html#terminators
  //
  // 底下建立的基本塊,請參照
  // http://llvm.org/releases/2.6/docs/tutorial/JITTutorial2.html
  // 中的 CFG。
  //
  BasicBlock* entry = BasicBlock::Create(Context, "entry", gcd);
  BasicBlock* ret = BasicBlock::Create(Context, "return", gcd);
  BasicBlock* cond_false = BasicBlock::Create(Context, "cond_false", gcd);
  BasicBlock* cond_true = BasicBlock::Create(Context, "cond_true", gcd);
  //  
  // 即使我們賦予 cond_false 和 cond_false_2 相同的名稱,LLVM 會將
  // 之替換成不同名稱。如此可省去我們命名的麻煩。
  //
  BasicBlock* cond_false_2 = BasicBlock::Create(Context, "cond_false", gcd);
 
  /* 開始填入 LLVM IR */
 
  // IRBuilder 提供一組一致的介面生成 LLVM IR。
  IRBuilder builder(entry); // 於基本塊 entry 填入 LLVM IR。
  //
  //  %tmp = icmp eq i32 %x, %y
  //  br i1 %tmp, label %return, label %cond_false
  //
  Value* xEqualsY = builder.CreateICmpEQ(x, y, "tmp");
  builder.CreateCondBr(xEqualsY, ret, cond_false);
  builder.SetInsertPoint(ret); // 於基本塊 ret 填入 LLVM IR。
  //
  // ret i32 %x
  //
  builder.CreateRet(x);
 
  builder.SetInsertPoint(cond_false); // 於基本塊 cond_false 填入 LLVM IR。
  //
  //  注意! LLVM 中的 integer type 不帶有 signed 或是 unsigned 的資訊。
  //  icmp 需要顯式的對其 integer type 運算元做 signed 或是 unsigned
  //  的解釋。請見 http://llvm.org/docs/LangRef.html#i_icmp
  //
  //  %tmp2 = icmp ult i32 %x, %y
  //  br i1 %tmp2, label %cond_true, label %cond_false1
  //
  Value* xLessThanY = builder.CreateICmpULT(x, y, "tmp");
  builder.CreateCondBr(xLessThanY, cond_true, cond_false_2);
 
  builder.SetInsertPoint(cond_true); // 於基本塊 cond_true 填入 LLVM IR。
  //
  //  %tmp3 = sub i32 %y, %x
  //  %tmp4 = call i32 @gcd(i32 %x, i32 %tmp3)
  //  ret i32 %tmp4
  //
  Value* yMinusX = builder.CreateSub(y, x, "tmp");
  std::vector args1;
  args1.push_back(x);
  args1.push_back(yMinusX);
  Value* recur_1 = builder.CreateCall(gcd, args1.begin(), args1.end(), "tmp");
  builder.CreateRet(recur_1);
 
  builder.SetInsertPoint(cond_false_2); // 於基本塊 cond_false_2 填入 LLVM IR。
  //
  //  %tmp5 = sub i32 %x, %y
  //  %tmp6 = call i32 @gcd(i32 %tmp5, i32 %y)
  //  ret i32 %tmp6
  //
  Value* xMinusY = builder.CreateSub(x, y, "tmp");
  std::vector args2;
  args2.push_back(xMinusY);
  args2.push_back(y);
  Value* recur_2 = builder.CreateCall(gcd, args2.begin(), args2.end(), "tmp");
  builder.CreateRet(recur_2);
 
  return M;
}

請注意! 生成 LLVM IR 時,請遵守 LLVM Language Reference Manual 上的規範。某些情況被 LLVM 視為未定義 (undefined),這代表 LLVM 想怎麼做都可以。千萬不要憑直覺解讀運算後的結果,否則你怎麼死的都不知道。

舉例: shl 將第一個運算元往左移位指定的位數。你先想想底下的結果為何。

    shl i32 1, 32 ; 把長度為 32-bit 的 1 往左移 32 位

是 0 嗎? 我們來看規格怎麼說。:-)

Semantics:

  The value produced is ... . If op2 is (statically or dynamically) negative or
equal to or larger than the number of bits in op1, the result is undefined.

是的,shl i32 1, 32 所得結果是 undef。這代表你的程序可能能正確執行、當機或是任何事都可能發生。請嚴格遵守 LLVM Language Reference Manual 上的規範。不要自作聰明。

[1] http://llvm.org/docs/ProgrammersManual.html#Module
[2] http://llvm.org/docs/ProgrammersManual.html#Function
[3] http://llvm.org/docs/ProgrammersManual.html#BasicBlock
[4] http://llvm.org/docs/WritingAnLLVMPass.html

LLVM Introduction – How to use LLVM JIT 1/3

Copyright (c) 2011 陳韋任 (Chen Wei-Ren)

前言

LLVM 全名為 Low Level Virtual Machine。各位千萬不可被它的名稱所誤導,它跟虛擬機器 (virtual machine) 基本上沒有關係。它是一個編譯器基礎設施。換句話說,它可以用來建立一個編譯器。雖然有些計畫,如 VMKit,使用 LLVM 建立類似於 JVM 的虛擬機器,但是 LLVM 跟虛擬機器沒有關係。在研究所時代,我就有接觸過 LLVM。畢業後做的工作仍與 LLVM 有關。由於我本身有點編譯器的背景,在介紹 LLVM 的同時,我希望能盡可能的將編譯器相關的知識融入進去。希望各位不吝指教。

0. 建置環境

我先介紹如何建置 LLVM。

1. 使用 llvm-top。llvm-top 是一個鮮為人知的小工具。注意! 它抓取的是 svn 版本,而非 release 版本。詳細的使用方法請見 llvm-top/README.txt。底下是使用範例:

$ svn co http://llvm.org/svn/llvm-project/llvm-top/trunk/ llvm-top
$ cd llvm-top
$ ./build OPTIMIZED=1 PREFIX=$INSTALL llvm

2. 使用 configure。

$ wget http://llvm.org/releases/2.9/llvm-2.9.tgz; tar xvf llvm-2.9.tgz
$ mkdir build; cd build
$ ../llvm-2.9/configure --prefix=$INSTALL --enable-optimized
$ make install
$ export PATH=$INSTALL/bin:$PATH

3. 使用 CMake。

$ wget http://llvm.org/releases/2.9/llvm-2.9.tgz; tar xvf llvm-2.9.tgz
$ mkdir build; cd build
$ CFLAGS=-fno-strict-aliasing CXXFLAGS=-fno-strict-aliasing cmake -i ../llvm-2.9
 
  ... 設定 ...
 
$ make intall
$ export PATH=$INSTALL/bin:$PATH

對於一般平台,LLVM 提供預編譯好的執行檔,抓下來直接使用亦可。

1. LLVM IR

這邊簡單複習一下編譯器的流程。前端 (front end) 將代碼轉成中介碼 (intermediate representation,簡稱 IR),後端將 (back end) 將中介碼轉成二進制碼 (binary)。LLVM 做為一個編譯器基礎設施,基本上只等同 2/3 個編譯器。它還需要前端 (算 1/3 個編譯器) 將代碼轉成 LLVM IR,之後再進行跟底層架構無關/相關的優化,最後生成二進制碼。

LLVM IR 有底下三種形式:

  • In-memory compiler IR
  • On-disk bitcode representation
  • Human readable assembly language representation

這樣說太模糊了,我們馬上編譯一個小程式來看看。:-)

$ cd llvm-2.9/example/ModuleMaker
$ g++ ModuleMaker.cpp `llvm-config --cxxflags --ldflags --libs all` -o ModuleMaker
$ ModuleMaker > module.bc
# 將 bitcode 反匯編成 LLVM human readable assembly
$ llvm-dis module.bc
# 讓 vim 能夠高亮顯示 LLVM IR
$ cp llvm-2.9/utils/vim/llvm.vim $HOME/.vim/syntax/
$ vim module.ll
; ModuleID = 'module.bc'
 
define i32 @main() {
EntryBlock:
  %addresult = add i32 2, 3
  ret i32 %addresult
}

一般來說,*.bc 存放的是 “on-disk bitcode representation”; *.ll 存放的是 “human readable assembly language representation”。在 LLVM 內部處理的就是 “in-memory compiler IR”。

就我所知,LLVM 最被廣為使用的方式,就是生成 LLVM IR,再交由其後端生成二進制碼。Module 是裝載 LLVM IR 的容器 (container),其中包含函式 (function)、全域變數 (global variable) 和符號表項 (symbol table entry)。一般會在 Module 中建立數個函式,函式中有數個基本塊 (basic block),最後在基本塊中填入 LLVM IR。ModuleMaker.cpp 中的註解寫得很完整,基本上就是前述的流程。

LLVM 一個常被宣傳的特色就是 JIT (Just In Time)。我們還是來看個例子。

$ cd llvm-2.9/examples/HowToUseJIT
$ g++ HowToUseJIT.cpp `llvm-config --cxxflags --ldflags --libs all` -o HowToUseJIT
$ ./HowToUseJIT

HowToUseJIT.cpp 的前半部就是在建立一個 Module,內含兩個函式: foo 和 add1。建立好 Module 之後,再針對這個 Module 生成 ExecutionEngine,即是 JIT。透過 ExecutionEngine 將該 Module 的某個函式動態編譯成 binary 並執行,最後傳回執行後的結果。

最後簡單介紹一下 example 目錄底下其它的範例。

  • Fibonacci: 展示如何於 Module 中生成遞迴函式計算 fibonacci。
  • BrainF: 實現程式語言 Brainfuck。[1][2][3]
  • Kaleidoscope: [4] 教程上所展示的範例語言。
  • OCaml-Kaleidoscope: [4] 教程上所展示的範例語言。
  • ParallelJIT: 展示多個執行緒可同時執行 JIT。
  • ExceptionDemo: 展示 LLVM 如何處理 C++ 的例外 (exception) 。

[1] http://www.profibing.de/lisp/brainfuck/Llvm.pdf
[2] http://blog.linux.org.tw/~jserv/archives/2011/04/build_programmi_1.html
[3] http://blog.linux.org.tw/~jserv/archives/2011/04/_llvm_brainfuck.html
[4] http://llvm.org/docs/tutorial/
[5] http://llvm.org/docs/ExceptionHandling.html
[6] http://llvm.org/devmtg/2011-09-16/EuroLLVM2011-ExceptionHandling.pdf

给GDB换一个版本控制工具

最近Phil Muldoon在gdb maillist挖了一个大坑 “GIT and CVS”,我当时看了以后,觉得这样的话题每过一段时间就会有人提起,每次都因为各种各样的问题,就不了了之了。RedHat他们有自己的一个gdb git branch,叫archer,估计他们每次把git上的patch,commit到cvs上都很郁闷,那个thread里边,Jan (GDB global maintainer)说了,他把git上的12 patch commit到cvs,花了他一个半小时,结果还有两个文件忘记添加了。

我个人觉得git很好,要是能换到git,我也高兴。我现在就之用cvs commit,其他的都不用。谁知道,Eli (GDB global maintainer)说git不好用,而且git不是gnu的项目,她在用bzr,还说“如果我们使用git,这很可能让我gdb里边不活跃了”。后来,楼就歪了,成了比较git和bzr了。里边讨论了很多git bzr很有意思的用法。

git和bzr我都用,感觉bzr就是比git慢一点,其他好像没有什么区别。bzr和launchpad集成很好,不过这些gnu都用不上。

大名鼎鼎的Mark K. (GDB global maintainer)会回复了一次,老外果然说话很直接,也是他的风格 “I am a git hater.”  还列出了他的workflow,他那个workflow是最基本的workflow,就是 update/modify/commit。这样的workflow根本不适合,多个patch的改动,而且在网速慢的地方,就更不合适了。

后来,讨论就没有什么实质进展了,因为没有任何的行动。我觉得这个话题就这样结束了,结果,无意中,在昨天晚上的irc上,看到一些更有意思的讨论。贴在这里:

<tromey> nobody wants to do the work, just argue about DVCs
<brobecke> It's OK, though. I think there are disadvantages that are immediately visible as soon as you review a diff, but it's not important enough that I want to pick a fight.
<brobecke> yeah, me too, sometimes.
<tromey> ok
<tromey> it is mostly stop-energy too
<brobecke> case in point, the latest discussion about git and bzr...
<tromey> sometimes I wonder why we put up with it
* brobecke sighs....
<tromey> I still haven't read the latest git thread
* antgreen (~user@c74-230.rim.net) has joined #gdb
<tromey> I didn't want the aggravation
<brobecke> nothing much there, I wouldn't bother.
<brobecke> there were two threads, really:
<brobecke> (1): what are the problems that need fixing for us to switch to a different VCS
<brobecke> (2): what is the best DVCS?
<brobecke> (1) was a useful reminder, but (2) was a waste of time
<SamB> shouldn't there be a "for us" in #2?
<brobecke> SamB: Yes, actually there was (a bit)
<SamB> of course, there's the fact that you are *already using* git...
<brobecke> someone even suggested that people who do the most commits should be the ones deciding 🙂
<dmalcolm> in case it's useful: http://www.python.org/dev/peps/pep-0374/
<SamB> brobecke: as someone who has made few or no commits, I am very much in favour of that plan!

这里没有什么好说的,就是他们开始讨论这个话题。第一句是亮点。介绍一下人物吧, brobecke, GDB global maintainer, Release Manager. tromey, GDB global maintainer。好,接着看他么还说什么了。

<tromey> yeah; but gdb, being a GNU project, has a uniquely bad political atmosphere
<SamB> indeed
<tromey> it is something I contemplate quite frequently these days
<tromey> other fields seem fairer
<SamB> you guys do *very* well, considering
<tromey> several GNU projects make progress according to the rule of "don't tell RMS"
<tromey> this works, but really it ought to be beneath us
<brobecke> If it was just about GDB, I think it would be doable to reach a consensus and just go ahead and do it. But we are intermingled with other projects, and it's costing us big time right now.
<SamB> RMS ought to be saner

不知道这里怎么就开始谴责 GNU和RMS了。

<brobecke> SamB: the problem is that GDB is part of a larger "project" called src.
<brobecke> when you checkout gdb, you actually checkout parts of src.
<SamB> the stupidest name ever
<SamB> but, yeah, I'm vaguely aware of the CVS repository arrangements
<tromey> binutils guys ought to be on board, since one or two threads ago was on the  binutils list
<tromey> this comes up like every 8 months 🙂
* brobecke is setting an alarm, then 🙂
<tromey> anyway all the commit scripts need to be converted
<tromey> and everything tested
<tromey> and all src communities notified or whatever
<tromey> Joseph posted a bullet list in one of the threads, which was, as usual for him, extremely comprehensive
<tromey> definitive one might say
<brobecke> there are also the "nightly" scripts that create the tarballs, which could use a good rewrite anyway

brobecke解释了为啥把gdb从cvs转换到别的vcs那么困难,说的挺有道理的。

<SamB> I still don't understand how bzr even qualifies as a GNU project
<tromey> me neither
<SamB> it doesn't seem to have any of the disadvantages usually associated with that status
<brobecke> why not? (just curious, I never looked at it before)
* brobecke is reading the PEP document dmalcolm pasted
<SamB> they'll take my commits without papers, for example
<andre> would a completely separate repo like archer and nightly sync to cvs be an option?
<SamB> It mainly seems to be used to annoy those working on *actual* GNU projects by suggesting that they should use bzr
<tromey> I thought bzr required copyright assignment to Canonical
<SamB> for purely political reasons
<SamB> tromey: maybe they do!
<tromey> that for me is a critical flaw
<tromey> I can't imagine what RMS was thinking
<brobecke> so, to be part of the GNU project, all it takes is RMS accepting it?
<SamB> anyway, as someone who actually *likes* bzr, I'm glad it is not a *real* GNU project
<tromey> yes, RMS just has to bless it; but one of the good things about RMS is that he is unusually consistent and principled, so you can be assured it has to be free software at least
<tromey> anyway the bzr decision is one of the things that has really soured me on GNU

这里就有一些有意思的事情了。我以前知道bzr是gnu dVCS,但是不知道参与bzr需要给Canonical 签 copyright assignment。这个是一个很奇怪的事情。community的工作,给一个公司签 assignment,的确很奇怪。

<brobecke> did he have any alternative, though?
<brobecke> how does git compare in terms of GNU-dness, do you think?
<tromey> this is the thing for me
<tromey> why does GNU need to bless *any* DVC?
<tromey> choosing bzr does not notably advance the cause of software freedom
<tromey> there are already many free DVCs
<tromey> free by every measure that matters to the FSF
<brobecke> ah, I see.
* dmalcolm mutters incoherent something about "free-as-in-requiring-copyright-assignment-to-a-for-profit-company"
<tromey> what also matters to me is (1) the random authoritarianism of RMS -- it isn't like this was some kind of process like the one Python went to -- and (2) bzr sucks IME; I think GNU should stand for *both* software freedom and technical excellence
<tromey> yes, requiring assignment to a company is amazingly bad, especially considering the crap Shuttleworth says about this sort of thing
<tromey> it has been extremely upsetting to me
<tromey> 🙁
<brobecke> wow, sorry that it's affected you so much. FWIW, I agree that it should strive for excellence as well.
<SamB> dmalcolm: hey, it's trivial to fork if at some point they do something evil...
<dmalcolm> one other point about that PEP document: yes, Python does have a "benevolent dictator for life", but the point of the PEP system is to encourage gathering the expert opinion to bear on a subject, so that a decision can be transparently made, and the BDFL is effectively just rubber-stamping it.  It turns the debate from a mailing list thread-of-doom into a deliverable/artefact
<dmalcolm> (sorry to weigh in; waiting on an upgrade here)
<tromey> I would be ok with it if GNU worked this way
<tromey> but RMS is not that open
<tromey> I suppose even if GNU were like this, it would still be dominated by the Eli Zs and Tom Lords of the world and I would still end up looking for something else
<tromey> Apache is perhaps a better model
<tromey> or Fedora or Debian
<pmuldoon> brobecke, did I suggest that? I can't remember what I said ;)
<brobecke> someone did, not sure who it was.
<pmuldoon> I think I said my experience was not unique in that the only time I use CVS is when I check-in
<pmuldoon> I am sorry about the thread, if it caused problems.  But I feel speaking up is the right thing to do, occasionally, even if it causes headaches ;)
<pmuldoon> brobecke, and I still think there should some bias to the release maintainer, because that maintainer deals with it
<brobecke> pmuldoon: thanks! :-). The releases take 2-3h max twice a year, so the bias should go to heavy contributors.

最后,这样一个讨论也没有什么结论。但是,看上去,换一个vcs,还不是那么简单的事情。我还是不明白,GNU为啥选择bzr,我倒不是说bzr不好,就是觉得那样一中copy right assignment的形式,让别的公司很难接受的。我想这个决定应该RMS做的,不知道他老人家怎么想的。

QEMU Internal – Block Chaining 3/3

Copyright (c) 2011 陳韋任 (Chen Wei-Ren)

2. Block Chaining

由 guest binary -> TCG IR 的過程中,gen_goto_tb 會做 block chaining 的準備。 我們先來看何時會呼叫到 gen_goto_tb。以 i386 為例,遇到 guest binary 中的條件分支和直接跳轉都會呼叫 gen_goto_tb (target-i386/translate.c)。這邊以條件分支當例子:

static inline void gen_jcc(DisasContext *s, int b,
                           target_ulong val, target_ulong next_eip)
{
    int l1, l2, cc_op;
 
    cc_op = s->cc_op;
    gen_update_cc_op(s);
    if (s->jmp_opt) { // use direct block chaining for direct jumps
        l1 = gen_new_label();
        gen_jcc1(s, cc_op, b, l1);
 
        gen_goto_tb(s, 0, next_eip); // 我猜是 taken
 
        gen_set_label(l1);
        gen_goto_tb(s, 1, val); // 我猜是 not taken
        s->is_jmp = DISAS_TB_JUMP;
    } else {
 
      /* 忽略不提 */
 
    }
}
  • gen_goto_tb。強烈建議閱讀 Porting QEMU to Plan 9: QEMU Internals and Port Strategy 2.2.3 和 2.2.4 節,也別忘了 SOURCEARCHIVE.com
  • // tb_num 代表目前 tb block linking 分支情況。eip 代表跳轉目標。
    static inline void gen_goto_tb(DisasContext *s, int tb_num, target_ulong eip)
    {
        TranslationBlock *tb;
        target_ulong pc;
     
        // s->pc 代表翻譯至目前 guest binary 的所在位址。tb->pc 表示 guest binary 的起始位址。
        // 注意! 這裡 s->cs_base + eip 代表跳轉位址; s->pc 代表目前翻譯到的 guest pc。
        pc = s->cs_base + eip; // 計算跳轉目標的 pc
        tb = s->tb; // 目前 tb
        // http://lists.nongnu.org/archive/html/qemu-devel/2011-08/msg02249.html
        // http://lists.gnu.org/archive/html/qemu-devel/2011-09/msg03065.html
        // 滿足底下兩個條件之一,則可以做 direct block linking
        // 第一,跳轉目標和目前 tb 起始的 pc 同屬一個 guest page。
        // 第二,跳轉目標和目前翻譯到的 pc 同屬一個 guest page。
        if ((pc & TARGET_PAGE_MASK) == (tb->pc & TARGET_PAGE_MASK) ||
            (pc & TARGET_PAGE_MASK) == ((s->pc - 1) & TARGET_PAGE_MASK))  {
            // 如果 guest jump 指令和其跳轉位址同屬一個 guest page,則做 direct block linking。
     
            tcg_gen_goto_tb(tb_num); // 生成準備做 block linking 的 TCG IR。詳情請見之後描述。
     
            // 更新 env 的 eip,使其指向此 tb 之後欲執行指令的位址。
            // tb_find_fast 會用 eip 查找該 TB 是否已被翻譯過。
            gen_jmp_im(eip);
     
            // 最終回到 QEMU tcg_qemu_tb_exec,賦值給 next_tb。
            // 注意! tb_num 會被 next_tb & 3 取出,由此可以得知 block chaining 的方向。
            tcg_gen_exit_tb((tcg_target_long)tb + tb_num);
        } else {
            /* jump to another page: currently not optimized */
            gen_jmp_im(eip);
            gen_eob(s);
        }
    }
    • tcg_gen_goto_tb 生成 TCG IR。
    • static inline void tcg_gen_goto_tb(int idx)
      {
          tcg_gen_op1i(INDEX_op_goto_tb, idx);
      }
    • tcg_out_op (tcg/i386/tcg-target.c) 將 TCG IR 翻成 host binary。注意! 這邊利用 patch jmp 跳轉位址達成 block linking。
    • static inline void tcg_out_op(TCGContext *s, TCGOpcode opc,
                                    const TCGArg *args, const int *const_args)
      {
          case INDEX_op_goto_tb:
              if (s->tb_jmp_offset) {
                  /* direct jump method */
                  tcg_out8(s, OPC_JMP_long); /* jmp im */
                  // 紀錄將來要 patch 的地方。
                  s->tb_jmp_offset[args[0]] = s->code_ptr - s->code_buf;
                  // jmp 的參數為 jmp 下一個指令與目標的偏移量。
                  // 如果還沒做 block chaining,則 jmp 0 代表 fall through。
                  tcg_out32(s, 0);
              } else {
       
                  /* 在此忽略 */
       
              }
              // 留待將來 "reset" direct jump 之用。
              s->tb_next_offset[args[0]] = s->code_ptr - s->code_buf;
              break;
      }

回答上一篇最後留下的問題。在還未 patch code cache 中的分支跳轉指令的跳轉位址,它會 fall through,還記得 jmp 0 嗎? 我這邊在列出 gen_goto_tb 的部分內容:

tcg_gen_goto_tb(tb_num);
 
// Fall through
 
// 更新 env 的 eip,使其指向此 tb 之後欲執行指令的位址。
// tb_find_fast 會用 eip 查找該 TB 是否已被翻譯過。
gen_jmp_im(eip);
 
// 最終回到 QEMU tcg_qemu_tb_exec,賦值給 next_tb。
// 注意! tb_num 會被 next_tb & 3 取出,由此可以得知 block chaining 的方向。
tcg_gen_exit_tb((tcg_target_long)tb + tb_num);

目前執行的 tb 會賦值給 next_tb (末兩位編碼 block chaining 的方向)。等待下一次迴圈,tb_find_fast 回傳 next_tb 的下一個 tb。

if (next_tb != 0 && tb->page_addr[1] == -1) {
    // 這邊利用 TranlationBlock 指針的最低有效位後兩位指引 block chaining 的方向。
    // next_tb -> tb
    tb_add_jump((TranslationBlock *)(next_tb & ~3), next_tb & 3, tb);
}

That’s it! That’s how direct block chaining is done in QEMU, I think… 🙂