как начать just-in-time-ить [перевод]
Published: 2020-04-29 19:29:33

Вольный перевод статьи Fedor Indutny "[How to start JIT-ting](https://darksi.de/4.how-to-start-jitting/)"

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

## Предпосылки

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

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

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

## С чего начнем

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

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

чтобы начать разрабатывать наш собственный JIT компилятор, понадобится выбрать язык для входных данных. Принимая во внимание [ТОП ЯЗЫКОВ 2013 ГОДА НА GITHUB](http://adambard.com/blog/top-github-languages-for-2013-so-far/), JavaScript выглядит подходяще для реализации некоторого ограниченного подмножества с упрощенной семантикой. Более того, мы реализуем JIT компилятор на самом JavaScript. Это можно назвать МЕТА-МЕТА!

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

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

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

Получить  AST из JavaScript кода достаточно просто и мы можем выбрать несколько (из десятков) библиотек вроде [esprima](https://github.com/ariya/esprima), [uglify-js](https://github.com/ariya/esprima) и т.д. . Чтобы не отходит далеко от туториала, я порекомендую вам выбрать [esprima](https://github.com/ariya/esprima). Он имеет неплохой и четко определенный [формат выходных данных](https://developer.mozilla.org/en-US/docs/SpiderMonkey/Parser_API).

Например, такой код `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 слоты ([регистры](http://en.wikipedia.org/wiki/Processor_register)) и просить 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` обычно содержит адреса по которым переменные из стека (т.е. переменные, которые хранятся в текущем процедурной [стеке](http://en.wikipedia.org/wiki/Stack_(abstract_data_type))) запускаются; `8` это размер  `rbx` регистра (и всех остальынх регистров, название которые начинается на `r`), и поскольку [стек](http://en.wikipedia.org/wiki/Stack_(abstract_data_type)) растет снизу вверх, нам нужно вычесть его из  `rbp` чтобы получить адрес свободного слота.

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

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

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

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

Лучшим и простейшим способом сделать это будет с помощью прохода по AST с помощью [поиска в глубину](http://en.wikipedia.org/wiki/Depth-first_search), генерирую машинный код для каждого узла. Вы можете подумать как можно генерирвоать машинный код для такого memory-safe языка как JavaScript. Здесь я представлю вам [jit.js](https://github.com/indutny/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](https://github.com/ariya/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](https://github.com/indutny/jit.js/tree/master/example/basic), запустив `npm install` и вуаля!

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