Перевод статьи Фёдора Индутного: How to start JIT-ting. Распространяется по лицензии MIT.
Большинство разработчиков слышали о компиляторах JIT и о том, как они могут заставить медленные интерпретируемые языки работать со скоростью, сравнимой с нативным кодом. Однако мало кто понимает, как работает JIT, и ещё меньше людей могут писать свои собственные компиляторы.
Я думаю, что, по крайней мере, базовые знания о внутренних компонентах компилятора могут значительно улучшить понимание кода, работающего на этом программном обеспечении.
В этой статье мы посетим некоторые вершины JIT-острова и, возможно, даже реализуем компилятор самостоятельно!
Зная некоторые основы, мы можем предположить, что каждый компилятор преобразует входные данные в каком-то формате (обычно, исходный код) в выходные данные в другом или таком же формате (как правило, машинный код). JIT-компиляторы не исключение.
Их делает особенными то, что они работают не до запуска кода (как, например, gcc, clang и другие), а «Just-In-Time» (то есть прямо перед выполнением скомпилированного кода).
Чтобы начать разработку собственного JIT-компилятора, нам нужно выбрать язык ввода для него. Учитывая Top Github Languages for 2013 (статья написана в 2013 году, - прим. пер.), JavaScript кажется хорошим кандидатом для реализации его ограниченного подмножества с упрощенной семантикой. Более того, мы будем реализовывать JIT-компилятор в самом JavaScript. Вы можете назвать его META-META!
Наш компилятор будет принимать исходный код JavaScript в качестве входных данных и производить (и сразу же запускать) машинный код для очень популярной платформы X64. Хотя для людей работать с текстовым представлением довольно удобно, разработчики компилятора обычно стремятся создавать несколько промежуточных представлений (Intermediate Representations или сокращённо IR) до создания окончательного машинного кода.
Поскольку мы пишем упрощенный компилятор, для нас достаточно одного IR, и для этого я выбрал абстрактное синтаксическое дерево (AST).
Получить AST из кода JavaScript сейчас очень легко, и мы можем выбрать любую из множества доступных нам библиотек: esprima, uglify-js и так далее. Чтобы оставаться на одной волне со мной, я рекомендую вам выбрать esprima. У этого парсера есть хорошо определенный выходной формат.
Например, этот код: obj.method(42) будет производить следующий AST (используя 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 } ] } } ] }
Подведем итог: у нас есть исходный код JavaScript (сделано), его AST (сделано), и мы хотим получить машинный код для него.
Если вы уже знакомы с ассемблером, вы можете пропустить эту главу, так как она содержит только базовые материалы по этой теме. Однако, если вы новичок в этом, чтение следующей главы может быть тяжелым, если не изучить сначала некоторые основы. Поэтому, пожалуйста, оставайтесь с нами, это не займет слишком много времени!
Ассемблер является ближайшим текстовым представлением двоичного кода, который ваш процессор понимает и с которым может работать. Учитывая, что процессор выполняет код путём чтения и запуска инструкций одной за другой, вам может показаться логичным, что почти каждая строка в программе на ассемблере представляет собой отдельную инструкцию:
mov rax, 1 ; Поместить 1 в регистр с именем `rax`
mov rbx, 2 ; Поместить 2 в регистр с именем `rbx`
add rax, rbx ; Посчитать сумму `rax` и `rbx` и положить результат в `rax`Результат работы этой программы (при условии, что вы получите его из регистра rax) - 3. И, как вы, наверное, уже поняли, она помещает данные в некие слоты процессора (регистры) и просит центральный процессор рассчитать их сумму.
Обычно у процессоров достаточно регистров для хранения результатов промежуточных операций, но в некоторых ситуациях вы можете использовать оперативную память для хранения/загрузки данных (и работы с ним):
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), а так как стек растёт вверх, нам нужно вычесть 8 из rbp, чтобы получить свободный адресный слот для наших целей.
Есть ещё много нюансов программирования на таком низком уровне, и, к сожалению, я не буду описывать их здесь. Кроме того, пожалуйста, имейте в виду, что я дал вам очень поверхностное описание, и иногда то, что на самом деле происходит, может быть намного сложнее.
Знания, упомянутые выше, должны быть достаточными для того, чтобы перейти к генерации кода.
Полная реализация JavaScript - довольно сложная задача, поэтому на данный момент мы реализуем только упрощенный арифметический движок (который должен быть таким же забавным, как добраться до полной реализации позже!).
Самый лучший и самый простой способ сделать это: обойти AST с помощью поиска в глубину, создавая машинный код для каждого узла. Вы могли бы задаться вопросом, как вы можете генерировать машинный код в таком ограниченном в прямой работе с памятью языке, как JavaScript. Вот где я собираюсь познакомить вас с jit.js.
Это модуль для node.js (фактически, дополнение на C++), способный генерировать и выполнять машинный код, используя сходный с ассемблером синтаксис:
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. К счастью, учитывая его структуру и наш минималистичный дизайн компилятора, это должно быть довольно легко.
Мы будем поддерживать:
- Литералы типа Number -
({ type: 'Literal', value: 123 }) - Бинарные выражения с использованием операторов:
+,-,*,/,%-({ type: 'BinaryExpression', operator: '+', left: ... , right: .... }) - Унарные выражения с использованием оператора -
({ type: 'UnaryExpression', operator: '-', argument: ... })
Все эти операции выполняются для целых чисел, поэтому не ожидайте, что наше решение будет работать с такими значениями, как 0.5, 0.66666 и так далее.
При обработке выражения мы будем посещать каждый поддерживаемый узел AST, генерируя код, возвращающий его результат в регистре rax. Звучит просто, не так ли? Единственное правило заключается в том, что мы должны сохранять все остальные регистры чистыми после выхода из узла AST. Другими словами, это означает, что мы должны сохранять все использующиеся регистры и восстанавливать их после того, как они больше не нужны. К счастью, у процессоров есть две волшебные инструкции push и pop, которые могут помочь нам в этой задаче.
Вот результирующий код с комментариями, описывающими, что в нём происходит:
var jit = require('jit.js'),
esprima = require('esprima'),
assert = require('assert');
var ast = esprima.parse(process.argv[2]);
// Компиляция
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('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) {
// Сохраняем начальное состояние '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('Unsupported binary operator: ' + 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('Unsupported unary operator: ' + ast.operator);
}
}Вы можете опробовать этот код: клонируем из github, запускаем в папке npm install, и вуаля!
$ node ./main.js '1 + 2 * 3'
7Спасибо, что дочитали до этого момента! В следующий раз я расскажу о куче и операциях с плавающей точкой!
Слушайте наш подкаст в iTunes и SoundCloud, читайте нас на Medium, контрибьютьте на GitHub, общайтесь в группе Telegram, следите в Twitter и канале Telegram, рекомендуйте в VK и Facebook.