Displaying articles with tag

Rubinius与LLVM

Posted by leeseon, Sun Oct 05 07:25:00 UTC 2008

一直对Rubinius所宣称的“Ruby In Ruby”很以为然,而且龙书中之也提到一个语言成熟的标志之一就是能“自举”--即使用自已来实现自己。以此为标准,Fortran、Basic、Javascript、Perl、PHP之类应该都算是不举,而LISP、C/C++、Smalltalk早就是很举的,Python、Java与Ruby现在是半举,并在让自己摆脱ED的印象之中,而Rubinius自然是Rubyist的春药罗

这两天读到Simple VM JIT with LLVM 觉得很是有趣,不过奇怪的是居然这个网站也被盾了,如果你从来没有tor过,或者gladder过,建议你赶紧找一个翻过墙去看看。不过顺便也谈谈我的读后感吧,算是学习笔记了。

Rubinius与YARV一样是一个虚拟机(VM),它如同Python一样,先将源代码编译成Bytecode文件,在执行时优先执行Bytecode。这样能提高ruby的执行效率。说到VM自然不能不说它的bc了,一个VM无非就是拿一些bc来执行了事而已,其实PC也是这样的,只是一个实一个虚而已。

Evan为了举例说明,首先杜撰了一个足够tiny的VM:

  • 只操作整数
  • 被编号的寄存器
  • 只有三条指令
    1. 0 - set(reg, val) 将第reg号寄存器设为整数值val
    2. 1 - add(result, reg, val)  将第reg寄存器与val相加,并将结果放入result寄存器
    3. 2 - show(reg) 将寄存器reg中的内容打印出来

因此下面这字节

  [ 0, 0, 3,
    1, 0, 0, 4,
    2, 0 ]

就表明将3与4相加并打印出来这样一个简单的功能,结果嘛如果不出意思自然是7

用C实现这个VM最平铺直叙的方法就是直接写就好了,如下

void add(int* ops, int* registers) {
  registers[ops[1]] = registers[ops[2]] + ops[3];
}

void set(int* ops, int* registers) {
  registers[ops[1]] = ops[2];
}

void show(int* ops, int* registers) {
  printf("=> %d\n", registers[ops[1]]);
}

void run(int* ops, int* registers) {
  switch(*ops) {
  case 0:
	set(ops, registers);
	ops += 3;
    break;
  case 1:
	add(ops, registers);
	ops += 4;
    break;
  case 2:
	show(ops, registers);
    return;
  }
}

随后Evan还另给出一个去除switch的直接的不能再直接的版本:

void my_program() {
  int registers[2] = {0, 0};
  int program[10] = [ 0, 0, 3,
                      1, 0, 0, 4,
                      2, 0 ]

  int* ops = (int*)program;

  set(ops, registers);
  ops += 3;
  add(ops, registers);
  ops += 4;
  show(ops, registers);
  ops += 2;
}

其实两者的功能是一样的,唯一的区别是前者更通用一点,可以在运行时执行,而后者比较象使用Bytecode直接翻译过来的样子。

而且的确是这样,处理这样将Bytecode执行的一种最最静态的方法,就是写一个bc的C代码生成器(C code emitter),将bc一次解析并产生一个类似第二段代码后几句的c代码文件,然后编译执行即可。

不过这种方法最大的缺点就是太静态了,所以的东西已经在编译时就定了,这当然不是Rubinius可以使用的方式,至于如第一段代码那样,一个更动态一点的方法,就是写一个解释器,在运行时解析代码并动态执行。其实这就有点类似YARV的方式。
除此之外有没有别的什么方法还执行bc呢?自然是有的,而且早就有很多人使用过了,那就是JIT(Just-in-time compilation)嘛: JIT是一个不那么纯编译也不那么纯解释的方法,bc在被执行前,先被转成目标机器上的原生指令,然后再执行,因为这一过程是即时的生成的,因此可以在其中增加一个优化的环节。而且因为代码是即时生成的,因此它可以对生成的代码做一些caching,所以它要比一句一句“忠实”执行的解释器快,而且因为JIT能获得更多的运行时信息,如CPU的架构及代码执行统计信息,因此能够生成一些CPU“特化”的代码及运行时的优化工作,所以JIT也是很有可能比静态编译要快的。

其实说了这么多也不过是为了引入今天所要谈的主角-----LLVM: LLVM并不是一个编译器,而仅仅只是一个编译器的基础设施(infrastructure),这个比较绕,其实它最有趣是提供了一套语言无关的中间层的优化与分析工具集。晕,其实这样说依然很绕:( 不过如果看一看Evan的例子之后可能会明白一些

首先就算是JIT也是需要将Bytecode的语义,即set/add/show指令提供给LLVM滴,先将这三个函数放入一个ops.c文件中,再用到llvm-gcc工具了,它利用gcc的前端,将C代码转换成LLVM的bc文件

命令如下

llvm-gcc -emit-llvm -O3 -c ops.c

这会生成一个ops.o的bc文件

使用llvm-dis < ops.o 命令查看,会看到与bc文件相对应的LLVM汇编指令

 

@.str = internal constant [7 x i8] c"=> %dA0"		;  [#uses=1]

define void @add(i32* %ops, i32* %registers) nounwind  {
entry:
	%tmp1 = getelementptr i32* %ops, i32 1		;  [#uses=1]
	%tmp2 = load i32* %tmp1, align 4		;  [#uses=1]
	%tmp4 = getelementptr i32* %ops, i32 2		;  [#uses=1]
	%tmp5 = load i32* %tmp4, align 4		;  [#uses=1]
	%tmp7 = getelementptr i32* %registers, i32 %tmp5		;  [#uses=1]
	%tmp8 = load i32* %tmp7, align 4		;  [#uses=1]
	%tmp10 = getelementptr i32* %ops, i32 3		;  [#uses=1]
	%tmp11 = load i32* %tmp10, align 4		;  [#uses=1]
	%tmp12 = add i32 %tmp11, %tmp8		;  [#uses=1]
	%tmp14 = getelementptr i32* %registers, i32 %tmp2		;  [#uses=1]
	store i32 %tmp12, i32* %tmp14, align 4
	ret void
}

define void @set(i32* %ops, i32* %registers) nounwind  {
entry:
	%tmp1 = getelementptr i32* %ops, i32 1		;  [#uses=1]
	%tmp2 = load i32* %tmp1, align 4		;  [#uses=1]
	%tmp4 = getelementptr i32* %ops, i32 2		;  [#uses=1]
	%tmp5 = load i32* %tmp4, align 4		;  [#uses=1]
	%tmp7 = getelementptr i32* %registers, i32 %tmp2		;  [#uses=1]
	store i32 %tmp5, i32* %tmp7, align 4
	ret void
}

declare i32 @printf(i8*, ...) nounwind 

define void @show(i32* %ops, i32* %registers) nounwind  {
entry:
	%tmp1 = getelementptr i32* %ops, i32 1		;  [#uses=1]
	%tmp2 = load i32* %tmp1, align 4		;  [#uses=1]
	%tmp4 = getelementptr i32* %registers, i32 %tmp2		;  [#uses=1]
	%tmp5 = load i32* %tmp4, align 4		;  [#uses=1]
	%tmp7 = tail call i32 (i8*, ...)* @printf( i8* getelementptr ([7 x i8]* @.str, i32 0, i32 0), i32 %tmp5 ) nounwind 		;  [#uses=0]
	ret void
}

无它,这个ops.o主要是拿来给LLVM使用的,在运行时生成相应的语义调用

然后使用LLVM的C++ API来生成一段与第二段代码相应的LLVM代码

 

Function* create(Module** out) {
  std::string error;
  Module* jit;

  // 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;
  }

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

  // Now, begin building our new function, which calls the
  // above functions.
  Function* body = cast<Function>(jit->getOrInsertFunction("body",
        Type::VoidTy,
        PointerType::getUnqual(Type::Int32Ty),
        PointerType::getUnqual(Type::Int32Ty), (Type*)0));

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

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

  // Set up our arguments to be passed to set.
  std::vector<Value*> params;
  params.push_back(ops);
  params.push_back(registers);

  // Call out to set, passing ops and registers down
  CallInst* call = CallInst::Create(set, params.begin(), params.end(), "", bb);
  ConstantInt* const_3 = ConstantInt::get(APInt(32,  "3", 10));
  ConstantInt* const_4 = ConstantInt::get(APInt(32,  "4", 10));

  // add 3 to the ops pointer.
  GetElementPtrInst* ptr1 = GetElementPtrInst::Create(ops, const_3, "tmp3", bb);

  // Setup and call add, notice we pass down the updated ops pointer
  // rather than the original, so that we've moved down.
  std::vector<Value*> params2;
  params2.push_back(ptr1);
  params2.push_back(registers);
  CallInst* call2 = CallInst::Create(add, params2.begin(), params2.end(), "", bb);

  // Push the ops pointer down another 4.
  GetElementPtrInst* ptr2 = GetElementPtrInst::Create(ops, const_4, "tmp3", bb);

  // Setup and call show.
  std::vector<Value*> params3;
  params3.push_back(ptr2);
  params3.push_back(registers);
  CallInst* call3 = CallInst::Create(show, params3.begin(), params3.end(), "", bb);

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

  *out = jit;
  return body;
}

然后调用之

int main() {
  // The registers.
  int registers[2] = {0, 0};

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

  int* ops = (int*)program;

  // Create our function and give us the Module and Function back.
  Module* jit;
  Function* func = create(&jit);

  // 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
" << *jit;

  // 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.
  void (*fp)(int*, int*) = (void (*)(int*, int*))engine->getPointerToFunction(func);

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

最后的结果会是这样

<snip same LLVM as before>

define void @body(i32* %ops, i32* %registers) {
entry:
call void @set( i32* %ops, i32* %registers )
%tmp3 = getelementptr i32* %ops, i32 3 ;  [#uses=1]
call void @add( i32* %tmp3, i32* %registers )
%tmp31 = getelementptr i32* %ops, i32 4 ;  [#uses=1]
call void @show( i32* %tmp31, i32* %registers )
ret void
}
=> 7

bc被执行了,不是吗?而且上面的那个boby就如同是my_program最后几行代码最直白的翻译,不同这处只是它是用API来产生的而已。

不过等等,最有趣的在后面,如果将LLVM的优化功能全部打开了之后,我们能得到什么?

 

define void @body(i32* %ops, i32* %registers) {
entry:
	%tmp1.i = getelementptr i32* %ops, i32 1		;  [#uses=1]
	%tmp2.i = load i32* %tmp1.i, align 4		;  [#uses=1]
	%tmp4.i = getelementptr i32* %ops, i32 2		;  [#uses=1]
	%tmp5.i = load i32* %tmp4.i, align 4		;  [#uses=1]
	%tmp7.i = getelementptr i32* %registers, i32 %tmp2.i		;  [#uses=1]
	store i32 %tmp5.i, i32* %tmp7.i, align 4
	%tmp3 = getelementptr i32* %ops, i32 3		;  [#uses=3]
	%tmp1.i7 = getelementptr i32* %tmp3, i32 1		;  [#uses=1]
	%tmp2.i8 = load i32* %tmp1.i7, align 4		;  [#uses=1]
	%tmp4.i9 = getelementptr i32* %tmp3, i32 2		;  [#uses=1]
	%tmp5.i10 = load i32* %tmp4.i9, align 4		;  [#uses=1]
	%tmp7.i11 = getelementptr i32* %registers, i32 %tmp5.i10		;  [#uses=1]
	%tmp8.i = load i32* %tmp7.i11, align 4		;  [#uses=1]
	%tmp10.i = getelementptr i32* %tmp3, i32 3		;  [#uses=1]
	%tmp11.i = load i32* %tmp10.i, align 4		;  [#uses=1]
	%tmp12.i = add i32 %tmp11.i, %tmp8.i		;  [#uses=1]
	%tmp14.i = getelementptr i32* %registers, i32 %tmp2.i8		;  [#uses=1]
	store i32 %tmp12.i, i32* %tmp14.i, align 4
	%tmp31 = getelementptr i32* %ops, i32 4		;  [#uses=1]
	%tmp1.i2 = getelementptr i32* %tmp31, i32 1		;  [#uses=1]
	%tmp2.i3 = load i32* %tmp1.i2, align 4		;  [#uses=1]
	%tmp4.i4 = getelementptr i32* %registers, i32 %tmp2.i3		;  [#uses=1]
	%tmp5.i5 = load i32* %tmp4.i4, align 4		;  [#uses=1]
	%tmp7.i6 = call i32 (i8*, ...)* @printf( i8* getelementptr ([7 x i8]* @.str, i32 0, i32 0), i32 %tmp5.i5 ) nounwind 		;  [#uses=0]
	ret void
}
=> 7

 

对,函数被LLVM给Inline化了,强吧!Evan称之为使用核能做饭,呵呵。

嗯,的确是很趣,那么我们从中又能学到什么呢?使用LLVM强大的中间层基础设施,可以为rubinius的bc执行带来强大的JIT功能。至于rubinius真的是怎样做到,让我读读rubinius的代码之后再接着谈吧:)

0 comments | Filed Under: | Tags: