如何写一个JIT(Just-In-Time)

[hello2dj]

为了兼具移植性和性能，聪明的工程师们发明了 JIT 这个东西，所谓的 JIT 就是说在解释型语言中，对于经常用到的或者说有较大性能提升的代码在解释的时候编译成机器码，其他一次性或者说没有太大性能提升的代码还是以字节码的方式执行

前提

大多数开发人员都是知道JIT编译器的(解释执行，比如ruby JIT, lua JIT- openresty就是集成lua JIT的nginx), JIT可以让我们的解释性语言(一般都比较慢)快如闪电，甚者可以和native code一较高下（当然这有写夸张），但JIT确实是可以让解释性语言跑的飞快。然后很少人知道JIT到底是如何运行的，甚着如何编写一个属于自己的JIT编译器。

掌握一些编译器的基本知识可以帮助我们更好的理解代码的运行原理。

在这篇文章里我们会去揭露一些JIT的原理，甚至实现一个我们自己的JIT编译器。

我们如何开始呢

先确定一个编译器的基本知识点，就是我们可以认为编译器就是把一定格式的输入（通常就是源代码）转换到其他格式或者是相同格式的输出（通常是机器码）。JIT 编译器也不例外。

那是什么让JIT编译器与众不同的呢？那就是JIT并不是提前进行编译的（就是再运行之前编译的，想想我们的golang你想运行golang就得先编译再运行，再比如gcc, clang 或者其他这些都是提前编译的），JIT是在运行时进行编译的（Just-In-Time, 当然也是在执行编译器的输出之前，这句话很怪吧)。

在开始开发我们的JIT compiler之前我们得先选择一个输入语言。我选择的是JavaScript, 他的语法很简单。甚至我会使用JavaScript本身来实现一个JavaScript的JIT。你可以叫他 META-META!

总结一下我们要做的JIT就是从 source code -> IR（AST）-> machine code

AST (抽象语法树)

我们的编译器可以接收JavaScript的源代码做为输入，然后生成X64架构的机器码（并且立即执行）。虽然人类更乐意使用文本表示，但是在生成机器码之前编译器的开发者则更倾向于使用多种IR(Intermediate Representations)来表示程序。

因为我们写的是一个简化版的编译器，所以我们只有一种IR, 当然这对我们来说足够了。我在这里会采用AST(Abstract Syntax Tree) 来作为我们唯一的IR。

从js的源代码中获取AST很简单，因为有很多现成的js parser他们都可以输出AST。 比如：esprima, acornjs等等。在本文中我推荐使用esprima, 因为他有很好的输出格式（MDN定义的一种AST格式）。

举个🌰， 我们看这句话： obj.method(42) 。 使用esprima.parse(...), 会生成如下的AST

{
  type: 'Program',
  body: [ {
    type: 'ExpressionStatement',
    expression: {
      type: 'CallExpression',
      callee: {
        type: 'MemberExpression',
        computed: false,
        object: { type: 'Identifier', name: 'obj' },
        property: { type: 'Identifier', name: 'method' }
      },
      arguments: [ { type: 'Literal', value: 42 } ]
    }
  }]
}

机器码（下面的汇编是x86-64的汇编，不同架构的汇编是各不相同的）

附赠x86-64汇编教程

我们先总结一下目前的情况：js源码（ok）, AST生成（ok），机器码（待完成）

接下来我们会将一些汇编的基础知识，当然如果你对汇编有所了解的话，就直接跳到下一章吧。

汇编语言其实就是机器或者说CPU能够执行的二进制代码的近文本表示, 考虑到处理器是一行一行的读取并且执行指令的，因此我们把汇编的每一行都看作是一条指令也是合理的，如下：

mov rax, 1    ; 把 ‘1’ 放到 rax寄存器中
mov rbx, 2    ; 把 ‘2’ 放到 rbx寄存器中
add rax, rbx  ; 计算rax和rbx的和然后放到rax中

这个段汇编代码的执行结果是3（你可以从寄存器rax中拿到结果）。通过这个也可以看出来处理器的工作方式：1.把数据放到CPU的(寄存器)里面 2.通知CPU进行计算

通常来说CPU有足够多的寄存器来存放中间结果, 但是在某些情况下你可能也需要使用计算机的内存来存储或读取数据（一股计算机组成原理的味道）：

mov rax, 1
mov [rbp-8], rbx  ; 把rbx的数据存到内存中(栈内存)
mov rbx, 2
add rax, rbx
mov rbx, [rbp-8]  ; 从内存读取数据到rbx中

寄存器使用名字来标识（rax, rbx）,内存使用地址来标识。地址的标识方式通常是[…]的形式。举个🌰，[rbp-8] 的意思是：从寄存器rbp中取出数据，然后减8，把这个结果作为内存的地址，通过这个值就可以对内存中[rbp-8]这个地址进行读写操作了。

rbp这个寄存器是用来存储当前栈的起始地址的，由于栈地址是从大到小，所以起始地址最大，依次相减就能获取可用的栈空间地址。

在往下讲就会牵扯更多的相关的知识了，我们就此打住。

机器码的生成

实现一个完整的js JIT太复杂了，我们先挑点儿简单的操作一下，就是实现简单的js的加减乘除。

实现js的加减乘除最简单也是最好的办法就是使用深度遍历遍历AST,然后给每个节点生成机器码。那么怎么使用js来生成机器码呢？毕竟使用js时没有办法直接操作内存。

给大家介绍一下jit.js。 这是一个node.js的包（实际上是一个C++的扩展）。这个包可以生成并且执行机器码：

var jit = require('jit.js');

var fn = jit.compile(function() {
  this.Proc(function() {
    this.mov('rax', 42); // ‘move rax, 42’
    this.Return();
  });
});
console.log(fn());  // 42

jit.js的原理

1. X86 机器码的转换 参见

   按照上面的方式书写汇编语言，然后转成x86对应机器码, 比如：mov => 0xb3 (这只是个例子映射对错不论)

   

2. mmap

   使用mmap在内存中开辟一段空间设置为 可执行 状态，然后把上面x86机器码数据写入（然后将起始地址强制转换为 函数指针，接着调用执行就好了）

   var jit = require('jit.js');
   
   var fn = jit.compile(function() {
     this.Proc(function() {
       this.mov('rax', 42);
       this.Return();
     });
   });
   console.log(fn.toString());  // function () { [native code] }

   这里fn调用toString显示的是native code，原因就是上述所描述的，这个fn的执行体并不是js写的，而是从汇编直接转换成机器码然后写入内存强制执行的。

动工实现吧

最后只剩下遍历AST tree的工作了，不过由于我们只是要实现加减乘除，因此遍历很容易实现。

我会支持一下几种：

1. 数字字面量（{ type: 'Literal', value: 123 }）

2. 二元操作符：+ - * % ({ type: 'BinaryExpression', operator: '+', left: ... , right: .... })

3. 一元操作符：- ({ type: 'UnaryExpression', operator: '-', argument: ... })

我们只支持整数暂不支持浮点数。

我们需要处理表达式时会遍历我们所支持的AST node, 生成能够返回rax中的结果的代码。听起来很简单？在动手之前有一件事需要我们谨记：在我们离开一个AST node时我们需要保证所有的寄存器都是干净的（不能污染其他程序），也就是说我们需要保存我们使用过的寄存并且在再次进入时能够恢复他们以前的数据（因为寄存器不是只有我们在使用，而是所有使用cpu的程序都有可能在使用，因此必须保存现场（即保存执行的上下文），否则再次进入就会丢失状态）。不过这个问题CPU已经替我们想好了就是 'pop'和 'push' 两个命令。

下面就是我们的最终的 js 加减乘除版 JIT了：

// main.js
var jit = require('jit.js'),
    esprima = require('esprima'),
    assert = require('assert');

var ast = esprima.parse(process.argv[2]);

// Compile
var fn = jit.compile(function() {
  // This will generate default entry boilerplate
  this.Proc(function() {
    visit.call(this, ast);

    // The result should be in 'rax' at this point

    // This will generate default exit boilerplate
    this.Return();
  });
});

// Execute
console.log(fn());

function visit(ast) {
  if (ast.type === 'Program')
    visitProgram.call(this, ast);
  else if (ast.type === 'Literal')
    visitLiteral.call(this, ast);
  else if (ast.type === 'UnaryExpression')
    visitUnary.call(this, ast);
  else if (ast.type === 'BinaryExpression')
    visitBinary.call(this, ast);
  else
    throw new Error('Unknown ast node: ' + ast.type);
}

function visitProgram(ast) {
  assert.equal(ast.body.length,
               1,
               'Only one statement programs are supported');
  assert.equal(ast.body[0].type, 'ExpressionStatement');
  visit.call(this, ast.body[0].expression);
}

function visitLiteral(ast) {
  assert.equal(typeof ast.value, 'number');
  assert.equal(ast.value | 0,
               ast.value,
               'Only integer numbers are supported');

  this.mov('rax', ast.value);
}

function visitBinary(ast) {
  // Preserve 'rbx' after leaving the AST node
  this.push('rbx');

  // Visit right side of expresion
  visit.call(this, ast.right);

  // Move it to 'rbx'
  this.mov('rbx', 'rax');

  // Visit left side of expression (the result is in 'rax')
  visit.call(this, ast.left);

  //
  // So, to conclude, we've left side in 'rax' and right in 'rbx'
  //

  // Execute binary operation
  if (ast.operator === '+') {
    this.add('rax', 'rbx');
  } else if (ast.operator === '-') {
    this.sub('rax', 'rbx');
  } else if (ast.operator === '*') {
    // Signed multiplication
    // rax = rax * rbx
    this.imul('rbx');
  } else if (ast.operator === '/') {
    // Preserve 'rdx'
    this.push('rdx');

    // idiv is dividing rdx:rax by rbx, therefore we need to clear rdx
    // before running it
    this.xor('rdx', 'rdx');

    // Signed division, rax = rax / rbx
    this.idiv('rbx');

    // Restore 'rdx'
    this.pop('rdx');
  } else if (ast.operator === '%') {
    // Preserve 'rdx'
    this.push('rdx');

    // Prepare to execute idiv
    this.xor('rdx', 'rdx');
    this.idiv('rbx');

    // idiv puts remainder in 'rdx'
    this.mov('rax', 'rdx');

    // Restore 'rdx'
    this.pop('rdx');
  } else {
    throw new Error('Unsupported binary operator: ' + ast.operator);
  }

  // Restore 'rbx'
  this.pop('rbx');

  // The result is in 'rax'
}

function visitUnary(ast) {
  // Visit argument and put result into 'rax'
  visit.call(this, ast.argument);

  if (ast.operator === '-') {
    // Negate argument
    this.neg('rax');
  } else {
    throw new Error('Unsupported unary operator: ' + ast.operator);
  }
}

好了，我们可以运行我们自己的JIT了，原版正装JIT(简陋版) voila(瞧)：

$ node ./main.js '1 + 2 * 3'
7

嗯，打完收工，往后出去可以吹牛了。接下来的文章我们会讲讲如何使用堆内存以及浮点数的支持！

[dougpuob]

Hi @hello2dj
謝謝你的文章，沒想到有 jit.js 這種東西的出現。其中，有一個地方想請教，jit.compile() 產生出的應該已經是 machine code，接著直接使用 fn() 執行 machine code？這部份 JavaScript 是如何直接執行 machine code 的呢？

// Execute
console.log(fn());

[hello2dj]

@dougpuob jit 这个库有个 native addon 里直接通过强制类型转换，把他变成了一个 可执行的 js function

[dougpuob]

@hello2dj
我看了一下 jit.js 檔案，應該是作者包裝了一些需要用系統資源的函式給 nodejs 使用，所以 fn() 最後交給 jit.cc!FunctionWrap::Exec() 執行opcodes。

((以上是推測，還沒實際執行過))

[hello2dj]

@dougpuob 是的