Нежное введение в JIT и динамическую компиляцию / генерацию кода

Question

Обманчиво простая основа генерации динамического кода в среде C / C ++ уже описана в другом вопросе . Есть ли какие-нибудь нежные введения в тему с примерами кода?

Мои глаза начинают кровоточить, глядя на очень сложные JIT-компиляторы с открытым исходным кодом, когда мои потребности намного скромнее.

Есть хорошие тексты по этому предмету, которые не предполагают докторскую степень в области компьютерных наук? Я ищу хорошо изношенные шаблоны, на которые следует обратить внимание, соображения производительности и т. Д. Электронные или древовидные ресурсы могут быть одинаково ценными. Вы можете иметь практическое знание (не только x86) ассемблера.

Answer 1

Хорошо, шаблон, который я использовал в эмуляторах, выглядит примерно так:

typedef void (*code_ptr)();
unsigned long instruction_pointer = entry_point;
std::map<unsigned long, code_ptr> code_map;


void execute_block() {
    code_ptr f;
    std::map<unsigned long, void *>::iterator it = code_map.find(instruction_pointer);
    if(it != code_map.end()) {
        f = it->second
    } else {
        f = generate_code_block();
        code_map[instruction_pointer] = f;
    }
    f();
    instruction_pointer = update_instruction_pointer();
}

void execute() {
    while(true) {
        execute_block();
    }
}

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

промыть, повторить :)

Что касается генерации кода, это немного усложняется, но идея состоит в том, чтобы создать правильную " функцию " который выполняет работу вашего основного блока в контексте вашей виртуальной машины.

РЕДАКТИРОВАТЬ: обратите внимание, что я тоже не демонстрировал никаких оптимизаций, но вы попросили "осторожное введение"

РЕДАКТИРОВАТЬ 2: Я забыл упомянуть одно из самых быстрых ускорений, которое вы можете реализовать с помощью этого шаблона. По сути, если вы никогда не удаляете блок из своего дерева (вы можете обойти его, если это так, но это гораздо проще, если вы никогда этого не сделаете), тогда вы можете " chain " блоки вместе, чтобы избежать поиска. Вот концепция. Всякий раз, когда вы возвращаетесь из функции f () и собираетесь выполнить операцию «update_instruction_pointer», если только что выполненный вами блок завершился либо вызовом, либо безусловным переходом, либо вообще не заканчивался управлением потоком, то вы можете «исправить» ; свою команду ret с прямым jmp к следующему блоку, который он выполнит (потому что он всегда будет таким же) , если вы уже выполнили его. Это позволяет вам выполнять все чаще и чаще на виртуальной машине, а все меньше и меньше - в «execute_block». функция.

Answer 2

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

Самый простой способ - начать с интерпретатора виртуальной машины. Затем для каждой инструкции VM сгенерируйте код сборки, который выполнил бы интерпретатор.

Чтобы пойти дальше, я представляю, что вы должны проанализировать байтовые коды VM и преобразовать их в какую-то подходящую промежуточную форму (трехадресный код? SSA?), а затем оптимизировать и сгенерировать код, как в любом другом компиляторе.

Для виртуальной машины, основанной на стеке, это может помочь отслеживать текущее состояние " глубина стека при переводе байтовых кодов в промежуточную форму и обработке каждого местоположения стека как переменной. Например, если вы думаете, что текущая глубина стека равна 4, и вы видите «push» В инструкции вы можете создать назначение для " stack_variable_5 " и увеличить счетчик времени компиляции или что-то в этом роде. & Quot; добавить " когда глубина стека равна 5, можно сгенерировать код "stack_variable_4 = stack_variable_4 + stack_variable_5" quot; и уменьшите счетчик стека времени компиляции.

Также возможно преобразовать основанный на стеке код в синтаксические деревья. Поддерживать стек во время компиляции. Каждый "толчок" инструкция приводит к тому, что представляемая вещь будет сохранена в стеке. Операторы создают узлы синтаксического дерева, которые включают их операнды. Например, «X Y +» может привести к тому, что стек будет содержать «var (X)», затем «var (X) var (Y)»; а затем плюс отключает обе ссылки на var и толкает "plus (var (X), var (Y))".

Answer 3

Получите копию книги Джоэла Побара о Rotor (когда она выйдет) и изучите источник в SSCLI . Осторожно, безумие лежит внутри:)