назначаем числа [перевод]

Вольный перевод статьи Fedor Indutny "Allocating numbers"

Назначаем числа

Цели

В прошлой статье мы создали JIT компилятор, поддерживающий очень ограниченное количесвто подномежств JavaScript: целые числа, бинарные математические операции операторы (+, -, *, /), и унарный оператор -. В этот раз мы расширим его добавлением поддержки чисел с плавающей точкой, а, чтобы процесс стал живее и веселее, мы будем выделять и хранить эти числа в куче.

Поскольку мы внедряем функциональность небольшими шагами, на этом этапе наша куча не будет иметь сборщика мусора и будет жить внутри чанка памяти фиксированного размера (скажи "ура" простоте!).

Stubs

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

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

Как правило, это считается плохой практикой. Более лучшим подходом будет будет параметризация таких блоков кода в общие процедуры, называемые stubs (я взял это название из кода v8 и, похоже, они имеют такое же название и в других VM). Для еще большей оптимизации эти процедуры можно компилировать лениво, т.е. мы не должны компилировать участки, которые не используются генерируемым кодом. Эта техника хорошо сказывается на времени компиляции и размере выполняемого кода (и, соответснвенно, кэше CPU).

К счастью, jit.js позволяет достаточно легко генерировать stubs:

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 (и многие другие) VM создает и хранит обхекты (обычно те которые не могут уместиться в регистрах CPU). Некоторые объекты кучи могут содержать ссылки на другие объекты (другими словами, могут ссылаться на них). Все живущие объекты и их ссылки создают ориентированный граф начиная с так называех корней (который обычно являются глобальными переменными и указателями в стеке).

И хоть она обычно используется для VM, сборка мусора не обязательна для кучи. Многие виртуальные машины и языки выбирают неуправляемую память вместо того (C/C++ как пример). В таких случаях (как пользователь языка) будет необзодимо явно очищать неиспользуемые ресурсы чтобы не исчерпать память.

Но по очевидным причинам компилятор подмножеств JavaScript который мы реализуем должен поддерживать как управляемую память так и сборку мусора (что сделаем позже).

Есть тонны кнги котоыре могут дать вам продвинутое представление о распределении кучи и сборке мусора (я порекомендую The Garbage Collection Handbook) и и значительно много способов выделения и сборки памяти в куче.

Обычно вам понадобится выбрать между скоростью выделения и фрагментацией памяти. Но поскольку мы не углубляемся в тему я порекомендую остановиться на методе "bump allocation".

Bump allocation

bump allocation для фиксированных страниц работает следующим образом.

1. Взять чанк памяти фиксированного значения (страница)
2. Отдать последующие фрагменты в виде возвращаемого значение процедуры выделения.
3. Сжимая или перемещая живущие объекты в новый чанк памяти, запускать сборку мусора и очищать неиспользуемое пространство,когда кончается память, (заменяя ссылки на живущие обхекты).

Используя jit.js и стабы, эта процедура может выглядеть следующим образом:

// Создаем чанки памяти фиксированного размера
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']);

    // Конец заргрузки
    //
    // ПРИМЕЧАНИЕ: То же самое относится и к концу страницы, но мы не обновляем его прямо сейчас
    this.mov('rbx', this.ptr(end));
    this.mov('rbx', ['rbx']);

    // Вычисляем новый `offset`
    this.mov('rcx', 'rax');

    this.add('rcx', 16);

    // Проверяем, не переполняется ли буффер фиксированного размера
    this.cmp('rcx', 'rbx');

    // this.j() выполняет условный переход к указанной метке.
    // 'g' означает 'greater'
    // 'overflow' - это имя метки, связанной ниже
    this.j('g', 'overflow');

    // Окей, может двигаться дальше и обновить offset
    this.mov('rbx', this.ptr(offset));
    this.mov(['rbx'], 'rcx');

    // Первый 64-х битный указатель зарезервирован для 'tag',
    // второй имеет значенеи `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();
  });
});

Это все! Не совсем просто, но не так уж и сложно!

Эта процедура будет выдавать последующие куски страницы и даже помечать их (про это поговорим в одном из будующих постов. По сути, они используются определения разных типов объектов кучи. )!

Стоит отметить пару моментов:

1. jit.ptr(buf, offset) возвращает Buffer, содержащий указатель на данный  buf с добавленным к нему offset.
2. this.spill() - это процедура для сохранения и восстановления регистров памяти (обычно называется spilling). Принимает список регистров и коллбэк. Эти регистры будут сохранены перед входом в коллбэк и восстановлены после выхода из него. ПРИМЕЧАНИЕ: ВОсстановленный код будет сгенерирован перед каждым this.Return().
3. this.mov(['rbx'], 'rcx') сохраняет регистр rcx в ячейку памяти, на которую указывает значение регистра rbx. ПРИМЕЧАНИЕ: offset также можно указать здесь: this.mov(['rbx', 8], 'rcx').
4. jit.js поддерживает ветвления примитивов: this.cmp(a, b), this.j(condition, labelName), this.j(labelName), this.bind(labelName).

Плавающая запятая

Теперь, когда у нас есть предположительно работающая процедура, давайте вспомним что должно храниться внутри чанков нашей кучи. Мы создали чанки со значением тега 8 байт и содержимым 8 байт. Этого достаточно чтобы хранить double (как C тип) числа с плавающей запятой.

Есть множество assembly инструкций для загрузки/хранения и работы с такими числами. Но заметьте что для работы с ними их нужно хранить в разных наборах регистров: xmm0, xmm1, ... xmm15. Хотя, 64-х битные числа с плавающей запятой могут храниться и в регистрах общего назначения: rax, rbx, ... Математические операции возможны только с набором регистров xmm. Ниже несколько инструкций которые присутстввуют в jit.js и могут быть полезными нашему компилятору:

1. movq('xmm', 'gp') или movq('gp', 'xmm') для перемещения 64-х битных значений из регистра общего назначения в xmm, или наоборот.
2. movsd('xmm', 'xmm') для перемещения значения из одного xmm к другому.
3. addsd, mulsd, subsd, divsd - сложение, умножение, вычитание, деление.
4. cvtsi2sd('xmm', 'gp'), cvts2si('gp', 'xmm') для концертации целых чисел в double, и наоборот.
5. roundsd('mode', 'xmm', 'xmm') для округления значения регистра src с помощью указанного режима mode (одного из: nearest, down, up, zero) и помещения результата в регистр dst.

Используя это священное знание, мы можем исправить наш код, чтобы он работал с числами с плавающей запятой (да, мы пока удалим целочисленную поддержку).:

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

function visitProgram(ast) {
  assert.equal(ast.body.length,
               1,
               'Поддерживается только один оператор');
  assert.equal(ast.body[0].type, 'ExpressionStatement');

  // Конвертируем в целое число имеющийся в 'rax' указатель
  visit.call(this, ast.body[0].expression);

  // Получаем число с плавающей запятой из числа кучи
  this.movq('xmm1', ['rax', 8]);

  // Округляем до нуля
  this.roundsd('zero', 'xmm1', 'xmm1');

  // Конвертируем double в целое число
  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('Неподдерживаемый бинарный оператор: ' + 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);
  }
}