как начать just-in-time-ить [перевод]

Вольный перевод статьи Fedor Indutny "How to start JIT-ting"

Как начать Just-In-Time-ить

Предпосылки

Большинство разработчиков что-то слышало об JIT компиляторах и как они могут замедлять интерпретируемые языки в сравнении с нативным кодом. Однако, не так много их них понимает как именно эта JIT штука работает, и еще меньше из них писали свои собственные компиляторы.

Как мне кажется, хотя бы базовые знания о внутренностях компилятора могут мощно прокачать понимание запускаемого обеспечением кода.

В этой статье мы посетим несколько вершин на JIT-острове, и возможно даже реализуем компилятор сами!

С чего начнем

Зная основы компилятора, мы можем вв что каждый компилятор трансформирует входные данные какого-то формата (обычно, исходный код) в выходные такого же или другого формата (обычно, в машинный код). JIT комплияторы не исключение.

Что делает их исключительными, так это то, что они запускаются не раньше времени (как gcc, clang и другие), а Just-In-Time (вовремя) (т.е. прямо перед выполнением выходных данных комплиятора).

чтобы начать разрабатывать наш собственный JIT компилятор, понадобится выбрать язык для входных данных. Принимая во внимание ТОП ЯЗЫКОВ 2013 ГОДА НА GITHUB, JavaScript выглядит подходяще для реализации некоторого ограниченного подмножества с упрощенной семантикой. Более того, мы реализуем JIT компилятор на самом JavaScript. Это можно назвать МЕТА-МЕТА!

Абстрактное Синтаксическое Дерево (AST)

На вход наш компилятор будет принимать JavaScript и возвращать (и немедленно выполнять) машинный код для очень популярной X64 платформы. Но, посокльку люддям удобнее работать с текстовым представлением, разработчики компиляторов обычно стремятся создать несколько Промежуточных Представлений (Intermediate Representations) перед генерацией окончательного машинного кода.

Поскольку мы пишем упрощенную версию, одного промежуточного представления будет достаточно, и для этого я выбрал представление в виде Абстрактное Синтаксическое Дерево (Abstract Syntax Tree).

Получить AST из JavaScript кода достаточно просто и мы можем выбрать несколько (из десятков) библиотек вроде esprima, uglify-js и т.д. . Чтобы не отходит далеко от туториала, я порекомендую вам выбрать esprima. Он имеет неплохой и четко определенный формат выходных данных.

Например, такой код obj.method(42) создаст (с помощью esprima.parse("...")) дерево следующего вида:

{ 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 } ] } } ] }

Машинный код

Давайте обобщим: у нас есть исходный код (check), его Абстрактное Синтаксическое Дерево (check), осталось только получить машинный код.

Если вы уже знакомы с assembly то можете пропустить эту главу поскольку она содержит только базовое введение в тему. ОДнако, если нет, последующая глава, без этих основ, может показаться вам сложной для понимания. Потому оставайтесь здесь, много времени не займет!

Язык Assembly - это ближайшее текстовое представление бинарного кода который понимает и(или) может запустить ваш CPU. Учитывая, что процессоры выполнябт код читая и запускаю иснтрукции по одной, может показаться логичным, что одна строка asse,bly программы представляет собой одну инструкцию:

mov rax, 1    ; Положить 1 в регистр `rax`
mov rbx, 2    ; Положить 2 в регистр `rbx`
add rax, rbx  ; Вычислить сумму `rax` и `rbx` и положить ее в регистр `rax`

Выходными данными этой прграммы будет являться 3 (при условии, что вы получите их из  rax регистра). И, как вы уже наверно догадались, программа будет ложить данные в CPU слоты (регистры) и просить CPU вычислить их сумму.

Обычно процессоры имеют достаточное количество регистров для хранения результата промежуточных операций, но в некоторых случаях вам понадобится хранить/загружать данные из памяти кмопьютера:

mov rax, 1
mov [rbp-8], rbx  ; Сохранить rbx регистр в слот стека
mov rbx, 2
add rax, rbx
mov rbx, [rbp-8]  ; Восстановить rbx регистр из слота стека

Регистры имеют имена, слоты памяти имеют адреса. Эти ардеа обычно используют [...] синтаксис. Например, [rbp-8] означает: возьми значение регистра rbp , вычти из него 8, и достучись до слота памяти, используя значение результата в качестве адреса.

Как вы можете видеть мы используем rbp регистр. rbp обычно содержит адреса по которым переменные из стека (т.е. переменные, которые хранятся в текущем процедурной стеке) запускаются; 8 это размер  rbx регистра (и всех остальынх регистров, название которые начинается на r), и поскольку стек растет снизу вверх, нам нужно вычесть его из  rbp чтобы получить адрес свободного слота.

Есть много нюансов в программировании на низком уровне и к сожалению я не собираюсь обо всех них здесь рассказывать. Также имейте ввиду что я предоставляю очень поверхностное описание и то что происходит здесь на самом деле может быть гораздо более сложным.

Понятий поясненных выше должны быть достаточно чтобы приступить к генерации кода.

Генерация кода

Реализовать полностью JavaScript будет довольно сложно, потому сейчас мы реализуем только упрощенную версию арифметического движка.

Лучшим и простейшим способом сделать это будет с помощью прохода по AST с помощью поиска в глубину, генерирую машинный код для каждого узла. Вы можете подумать как можно генерирвоать машинный код для такого memory-safe языка как JavaScript. Здесь я представлю вам jit.js.

Это node.js модуль (и C++ аддон, по сути) способный генерировать и выполнять машинны код используя assembly-подобный JavaScript синтаксис:

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

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

Давайте уже напишем это

Таким образом нам осталось сделать только одну вещь - модуль для прохода по AST, сгенерированному с помозью esprima. К счастью, учитывая его структуру и наш минималистичный дизайн компилятора это должно быть довольно просто.

Мы внедрим поддержку:

1. Числовых литералов ({ type: 'Literal', value: 123 })
2. Бинарных выражений с операторами: +, -, *, /, % ({ type: 'BinaryExpression', operator: '+', left: ... , right: .... })
3. Унарных выражений с оператором - ({ type: 'UnaryExpression', operator: '-', argument: ... })

Все эти операции выполняются на целых числах, потому не ожидайте что они сработают со значениями вроде 0.5, 0.66666 и т.д. .

Во время обработки выражения мы будем посещать каждый поддерживаемый узел AST и генерировать код, который вернет результат в rax регистр. Звучить легко, да? Здесь есть одно правило: мы должны сохранять все остальные регистры чистыми после выхода из узла дерева. Другими словами, это значит что мы должны сохранять все использованные регистры и восстанавливать их состояние после того как они не нужны. К счастью, CPU имеет две волшебные операцииpush и pop которые помогут нам с этой задачей.

Таким получится код (с комментариями):

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.Proc(function() {
    visit.call(this, ast);

    // Результат должен быть в 'rax'

    // Создаем шаблон для выходных данных
    this.Return();
  });
});

// Выполнение
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('Неизвестный AST узел: ' + ast.type);
}

function visitProgram(ast) {
  assert.equal(ast.body.length,
               1,
               'Поддерживается только один оператор');
  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,
               'Поддерживаются только целочисленные значения');

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

function visitBinary(ast) {
  // Сохраняем 'rbx' после того, как вышли из AST узла
  this.push('rbx');

  // Посещаем правую стороно выражения
  visit.call(this, ast.right);

  // Перемещаем в 'rbx'
  this.mov('rbx', 'rax');

  // Посещаем левую сторну выражения (результат в 'rax')
  visit.call(this, ast.left);

  //
  // Обобщяя, левая сторона хранится в 'rax', правая - в 'rbx'
  //

  // Выполняем бинарную операцию
  if (ast.operator === '+') {
    this.add('rax', 'rbx');
  } else if (ast.operator === '-') {
    this.sub('rax', 'rbx');
  } else if (ast.operator === '*') {
    // Умножение со знаком
    // rax = rax * rbx
    this.imul('rbx');
  } else if (ast.operator === '/') {
    // Сохраняем 'rdx'
    this.push('rdx');

    // idiv выполняет деление rdx:rax на rbx, следовательно, нам нужно очистить rdx
    // перед запуском
    this.xor('rdx', 'rdx');

    // Деление со знаком, rax = rax / rbx
    this.idiv('rbx');

    // Восстанавливаем 'rdx'
    this.pop('rdx');
  } else if (ast.operator === '%') {
    // Сохраняем 'rdx'
    this.push('rdx');

    // Готовимся выполнить idiv
    this.xor('rdx', 'rdx');
    this.idiv('rbx');

    // idiv помещает остаток в 'rdx'
    this.mov('rax', 'rdx');

    // Восстанавливаем 'rdx'
    this.pop('rdx');
  } else {
    throw new Error('Неподдерживаемый бинарный оператор: ' + ast.operator);
  }

  // Восстанавливаем 'rbx'
  this.pop('rbx');

  // Результат в 'rax'
}

function visitUnary(ast) {
  // Посещаем аргумент и складываем результат в 'rax'
  visit.call(this, ast.argument);

  if (ast.operator === '-') {
    // Делаем аргумент отрицательным
    this.neg('rax');
  } else {
    throw new Error('Неподдерживаемый унарный оператор: ' + ast.operator);
  }
}

Вы можете попробоать сами склонировав исходный код с github, запустив npm install и вуаля!

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