Перевод статьи Фёдора Индутного: Allocating numbers. Распространяется по лицензии MIT.
Это вторая заметка о JIT-компиляции в моём блоге. Предыдущий пост был введением в Just-In-Time генерацию кода и, в частности, в использование jit.js. Я рекомендую вам сначала ознакомиться с ним, прежде, чем идти дальше.
Ранее мы создали JIT-компилятор, поддерживающий очень ограниченное подмножество JavaScript: целые числа, математические бинарные операторы (+, -, *, /) и унарный оператор -. На этот раз мы расширим его, добавив поддержку чисел с плавающей запятой и, чтобы сделать процесс более интересным, мы научимся выделять память для хранения этих числе в куче.
Так как мы двигаемся постепенно, шаг за шагом, у нашей кучи не будет сборщика мусора, и она будет жить внутри фиксированного объема памяти (скажем «ура!» простоте).
Зная, что мы хотим сделать, теперь мы можем создать внутренние структуры для этой функциональности. По сути, нам нужна процедура выделения памяти, которая генерирует и возвращает адреса памяти, подходящие для наших целей.
Этот код выделения памяти может быть сгенерирован для каждого узла AST с помощью серии ассемблерных инструкций, такой код работает отлично и (что более важно) невероятно быстро для компактных операций. Но из-за относительно большого размера кода этой процедуры итоговый размер машинного кода может стать слишком большим и перестать помещаться в кеш процессора, что создает потенциальные проблемы с производительностью для всей системы.
Как правило, это считается плохой практикой. Лучшим подходом было бы вынос таких кодовых блоков в общие процедуры, называемых заглушками (stubs). Я взял это имя из исходников v8 и, возможно, это то, как эти вещи называются и в других виртуальных машинах. Для ещё большей оптимизации к этим процедурам можно применить ленивую компиляцию, то есть мы не должны компилировать те процедуры, которые не используются сгенерированным кодом. Этот метод хорош как для сокращения времени компиляции, так и для уменьшения размера исполняемого кода (и, соответственно, хорош для кэша процессора).
К счастью, jit.js позволяет легко создавать заглушки:
var stubs = jit.stubs();
stubs.define('Allocate', function() {
// Наш код лежит здесь
// ....
// Возвращаемся назад к коду, откуда
// была вызвана заглушка
this.Return();
});Просто, не так ли? Теперь, чтобы использовать эту заглушку в нашем JIT-компиляторе, нам нужно передать её имя в качестве аргумента:
jit.compile(function() {
// В этом контексте происходит
// генерация кода компилятором
// Объяснение:
// Получить адрес заглушки 'Allocate',
// положить его в регистр 'rax'
// и вызвать.
this.stub('rax', 'Allocate');
this.Return();
}, { stubs: stubs });Как упоминалось выше, только те заглушки, которые использовались во время процесса компиляции, будут фактически сгенерированы и переиспользованы между всеми их вызовами. (Скорее всего автор говорит о том, что заглушки, которые не были вызваны на этапе компиляции, будут сгенерированы позднее, непосредственно в момент вызова, это и есть ленивая компиляция, — прим. пер.)
С этими знаниями мы можем перейти к фазе выделения памяти. Но сначала давайте кратко рассмотрим структуру и организацию кучи.
Куча - это место, где JavaScript (и многие другие) виртуальные машины создают и хранят объекты (как правило, те, которые не могут быть помещены в регистры процессора). Некоторые объекты кучи могут содержать ссылки на другие объекты (другими словами, могут ссылаться на них). Все живые объекты и их ссылки создают ориентированный граф, начиная с так называемых корней (которые обычно являются глобальными переменными и указателями).
Хотя в виртуальных машинах с JIT-компиляцией обычно используется сборщик мусора, он не является обязательным при работе с кучей. Действительно, многие виртуальные машины и языки предпочитают вместо этого использовать управляемую память (C/C++, как банальный пример). В таких случаях вы (как пользователь языка) обычно должны явно освобождать неиспользуемые ресурсы, чтобы не выходить за пределы имеющейся памяти.
Но, по очевидным причинам, компилятор подмножества JavaScript, который мы реализуем, должен поддерживать как управляемую память, так и сборку мусора (которая будет реализована позже).
Существует множество книг, дающих расширенное представление о распределении памяти в куче и сборке мусора (моя рекомендация - «The Garbage Collection Handbook»), и множество способов выделить и собрать память в куче.
Обычно вам нужно выбирать между скоростью выделения и фрагментацией памяти. Но, поскольку мы не очень глубоко это затрагиваем, я бы рекомендовал придерживаться метода, называемого «выталкивающее выделение (bump allocation)».
Я никогда не сталкивался с этим термином на русском языке и не смог подобрать более адекватного перевода. Если вам он известен, напишите мне :), — прим. пер.
Выталкивающее выделение с фиксированной страницей работает следующим образом.
- Возьмите блок памяти фиксированного размера (страница).
- Отдайте последующие фрагменты из него как возвращаемое значение процедуры выделения.
- При нехватке памяти выполните сборку мусора и освободите все неиспользуемое пространство, либо сжимая живые объекты, либо перенося их в новую область памяти (заменяя ссылки на живые объекты в обоих случаях).
В терминах jit.js и API заглушек эта процедура может выглядеть следующим образом:
// Создаём блок памяти фиксированного размера
var page = new Buffer(1024);
// Устанавливаем указатели начала и конца страницы
var offset = jit.ptr(page);
var end = jit.ptr(page, page.length);
stubs.define('Alloc', function() {
// Сохраняем регистры 'rbx' и 'rcx'
this.spill(['rbx', 'rcx'], function() {
// Загружаем `offset`
//
// ПРИМЕЧАНИЕ: Мы будем использовать
// указатель на переменную `offset`,
// чтобы иметь возможноть обновить её ниже
this.mov('rax', this.ptr(offset));
this.mov('rax', ['rax']);
// Загружаем `end`
//
// ПРИМЕЧАНИЕ: То же самое относится и к
// `end`, хотя мы не обновляем эту
// переменную прямо сейчас
this.mov('rbx', this.ptr(end));
this.mov('rbx', ['rbx']);
// Вычисляем новый `offset`
this.mov('rcx', 'rax');
// Предположим, что все выделения
// требуют 16 байтов = два 64-битных
// указателя
this.add('rcx', 16);
// Проверяем что мы не вышли за пределы
// нашего фиксированного буфера
this.cmp('rcx', 'rbx');
// this.j() выполняет условный переход к
// указанной метке.
// 'g' означает 'больший'
// 'overflow' это имя ярлыка
this.j('g', 'overflow');
// Хорошо, мы готовы обновить смещение
this.mov('rbx', this.ptr(offset));
this.mov(['rbx'], 'rcx');
// Первый 64-битный указатель
// зарезервирован для «тега»,
// второй — значение типа `double`
this.mov(['rax'], 1);
// Возвращаем 'rax'
this.Return();
// Переполнение :(
this.bind('overflow')
// Вызов функции на javascript!
// ПРИМЕЧАНИЕ: Это выглядит забавно, но
// прямо сейчас я не собираюсь погружаться глубже
this.runtime(function() {
console.log('GC is needed, but not implemented');
});
// Поломка
this.int3();
this.Return();
});
});То, что надо! Не совсем прямолинейно, но и не очень сложно!
Эта процедура выдаст последовательные фрагменты страницы и даже тегирует их! (Я расскажу о тегах в одной из следующих статей. В основном, они используются, чтобы различать различные типы объектов кучи).
Здесь следует отметить несколько вещей:
Jit.ptr(buf, offset)возвращает экземплярBuffer, содержащий адрес в памяти для переданногоbufсо смещениемoffset.this.spill()- это процедура для сохранения и восстановления регистров в/из памяти (этот процесс обычно называется вытеснением (spilling)). Он принимает список регистров и замыкание. Эти регистры будут сохранены до входа в замыкание и восстановлены сразу после выхода. ПРИМЕЧАНИЕ: Код восстановления будет генерироваться каждымthis.Return().this.mov(['rbx'], 'rcx')- сохраняет регистрrcxв ячейке памяти, обозначенной значением регистраrbx. ПРИМЕЧАНИЕ: Здесь вы также можете указать смещение:this.mov(['rbx', 8], 'rcx').jit.jsподдерживает примитивы ветвления:this.cmp(a, b),this.j(condition, labelName),this.j(labelName),this.bind(labelName).
Теперь, когда у нас есть предположительно рабочая процедура выделения памяти, давайте вспомним, что должно храниться внутри этих кусочков кучи. В процедуре выделения мы создаём блоки с 8-байтовым значением тега и 8-байтовым содержимым. Этого достаточно для хранения чисел типа double с плавающей запятой (аналогично системе типов в C).
Существует множество ассемблерных инструкций для загрузки/хранения/работы с такими числами. Но обратите внимание, что для работы с ними вам нужно будет хранить их в разных наборах регистров: xmm0, xmm1, ...xmm15. Хотя 64-битные плавающие числа могут быть сохранены в регистрах общего назначения: rax, rbx, и так далее, но выполнение математических операций возможно только с набором регистров xmm. Вот несколько инструкций, которые присутствуют в jit.js и должны быть полезны для нашего компилятора:
movq('xmm', 'gp')илиmovq('gp', 'xmm')для перемещения 64 бит из регистра общего назначения (или указанного в нём адреса памяти) вxmmили наоборот.movsd('xmm', 'xmm')для перемещения значения из одногоxmmв другой.addsd,mulsd,subsd,divsd— сложение, умножение, вычитание, деление.cvtsi2sd('xmm', 'gp'),cvts2si('gp', 'xmm')— конвертируемintegerвdoubleи обратно.roundsd('mode', 'xmm', 'xmm')— округление регистраsrcс использованием указанного режима (который является одним из следующих: ближайшее, вниз, вверх, ноль) и помещение результата в регистрdst.
Используя это святое знание, мы можем исправить наш существующий код, чтобы он работал с числами с плавающей запятой (да, мы сейчас удалим поддержку целых чисел):
// Компиляция
var fn = jit.compile(function() {
// Это создаст стандартный шаблон входа
this.Proc(function() {
visit.call(this, ast);
// Результат должен быть в 'rax' в этот момент
//
// Это создаст стандартный шаблон выхода
this.Return();
});
}, { stubs: stubs });
// Выполнение
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);
// У нас есть указатель в 'rax', получим из него integer
// Получаем число с плавающей точкой из кучи по адресу
this.movq('xmm1', ['rax', 8]);
// Округяем его к нулю
this.roundsd('zero', 'xmm1', 'xmm1');
// Конвертируем double в integer
this.cvtsd2si('rax', 'xmm1');
}
function visitLiteral(ast) {
assert.equal(typeof ast.value, 'number');
// Выделение памяти из кучи
this.stub('rax', 'Alloc');
// Сохраняем регистр 'rbx'
this.spill('rbx', function() {
this.loadDouble('rbx', ast.value);
this.mov(['rax', 8], 'rbx');
});
}
function visitBinary(ast) {
// Сохраняем начальное состояние 'rbx' до выхода из узла AST
this.spill('rbx', function() {
// Проверяем правую часть выражения
visit.call(this, ast.right);
// Помещаем её в 'rbx'
this.mov('rbx', 'rax');
// Проверяем левую часть выражения (результат в 'rax')
visit.call(this, ast.left);
//
// Итак, левая часть в 'rax' и правая в 'rbx'
//
// Давайте загрузим double значения
this.movq('xmm1', ['rax', 8]);
this.movq('xmm2', ['rbx', 8]);
// Исполняем бинарную операцию
if (ast.operator === '+') {
this.addsd('xmm1', 'xmm2');
} else if (ast.operator === '-') {
this.subsd('xmm1', 'xmm2');
} else if (ast.operator === '*') {
this.mulsd('xmm1', 'xmm2');
} else if (ast.operator === '/') {
this.divsd('xmm1', 'xmm2');
} else {
throw new Error('Unsupported binary operator: ' + ast.operator);
}
// Выделение памяти под новое число, и отправка туда значения
this.stub('rax', 'Alloc');
this.movq(['rax', 8], 'xmm1');
});
}
function visitUnary(ast) {
if (ast.operator === '-') {
// Отрицательный аргумент через эмуляцию бинарного выражения
visit.call(this, {
type: 'BinaryExpression',
operator: '*',
left: ast.argument,
right: { type: 'Literal', value: -1 }
})
} else {
throw new Error('Unsupported unary operator: ' + ast.operator);
}
}Итак, это все, что я хотел сказать сейчас. Не пропустите следующий пост!
Слушайте наш подкаст в iTunes и SoundCloud, читайте нас на Medium, контрибьютьте на GitHub, общайтесь в группе Telegram, следите в Twitter и канале Telegram, рекомендуйте в VK и Facebook.