Введение в эмуляцию: динамические рекомпиляторы

В качестве объяснения того, как работают рекомпиляторы, был выбран блог cottonvibes'a - одного из основных кодеров pcsx2 в недавнем прошлом. Именно благодаря ему pcsx2 получил новый рекомпилятор VU-юнитов - microVU и спидхак, позволяющий использовать третье ядро процессора для выполнения кода юнита VU1 в отдельном потоке - MTVU. Ниже будет приведен почти дословный перевод его трудов.

Этот блог посвящен введению в динамические рекомпиляторы. Надеюсь, он обеспечит хотя бы частичное понимание основных принципов работы рекомпиляторов и объяснит, почему pcsx2 использует их для увеличения скорости эмуляции. Для того, чтобы осознать пользу рекомпиляторов, вы должны ознакомиться с простейшей моделью интерпретатора.

Предположим, мы эмулируем очень простой процессор. Процессоры имеют наборы различных инструкций, которые они могут обрабатывать. Представим, что мы эмулируем некоторый процессор, назовем его SL3, имеющий только 3 инструкции (при этом ширина каждой инструкции – 4 байта): 

MOV dest_reg, src1_reg           // задает направление от исходного к конечному регистру.
ADD dest_reg, src1_reg, src2_reg // суммирует регистры source1 и source2 и сохраняет результат в конечный регистр
BR relative_address              // перейти к соответствующему адресу (PC+= relative_adress * 4)

Процессоры имеют то, что мы называем регистрами, которые могут хранить данные. В этих регистрах исполняются инструкции процессора. В нашем случае, мы предположим, что процессор SL3 имеет 8 регистров, при этом, размер каждого из них  - 32 бита (то есть каждый регистр хранит 32 бита информации).
Для программирования этого процессора мы можем использовать следующий код:

MOV reg1, reg0
ADD reg4, reg2, reg3
BR 5

Что делает этот код:
1) «перемещает» регистр 0 в регистр 1 (теперь регистр 1 содержит копию данных из регистра 0).
2) суммирует регистр 2 и регистр 3, а результат записывает в регистр 4.
3) разветвляет 5 инструкций, идущих далее.

Вот так мы можем программировать процессор SL3  на коде ассемблера. Но как его эмулировать?
В принципе, для эмуляции этого процессора мы можем использовать интерпретатор. Интерпретатор просто получает инструкции опкода (кода операции) и последовательно их исполняет (вызывая соответствующую функцию для каждой отдельно взятой инструкции). Остальные части системы (другие процессоры или периферия) могут быть сэмулированы позже: между инструкциями или после того, как блок инструкций выполнен. Интерпретация – простой и точный способ эмуляции системы.

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

Основная идея динамической рекомпиляции заключается в том, чтобы «перевести» эмулируемые инструкции лишь один раз, кешировать результат перевода и в дальнейшем запускать готовые блоки (для х86 процессора) каждый раз, когда возникнет необходимость.

Пока считанные инструкции не изменяются (в этом примере мы не учитываем самоизменяющийся код), мы можем переводить эмулируемые инструкции на родные для эмулирующего ЦП инструкции (в нашем случае, это х86 ассемблерные инструкции) и кешировать переведенные инструкции в «блоки» кода, а затем просто исполнять этот нативный код вместо того, чтобы делать перевод каждый раз, как только этот код нужно будет считать заново.
Давайте вспомним программу для нашего SL3, описанную выше:

MOV reg1, reg0
ADD reg4, reg2, reg3
BR 5

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

Сейчас, функция интерпретатораперевод каждой инструкции перед, собственно, ее исполнением. Вот почему необходимо получить опкод каждой инструкции, вызвать эмулируемую функцию, закрепленную за номером опкода,  а затем непосредственно исполнить инструкцию. Но динамические рекомпиляторы позволяют нам пропустить получение опкода и вызов эмулируемой функции, сделав это один раз и сохранив переведенный код в родные «блоки» ассемблера.

Чтобы сделать хороший рекомпилятор, нам для начала потребуется эмиттер кода. Эмиттер – серии вызываемых нами функций, которые записывают родной код ассемблера в присвоенные им блоки памяти. То есть, мы используем х86 эмиттер для записи родного х86 кода ассемблера в блоки памяти, и в дальнейшем мы сможем их исполнять как обычные, сгенерированные с помощью С++, функции!
PCSX2 имеет очень продвинутый эмиттер, очень похожий на х86 ассемблер, различие лишь в написании «х» перед названиями инструкций.

Например:
move eax, ecx;

выглядит как:
xMOV (eax, ecx);

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

// это наша эмулированная инструкция MOV
void MOV() 
{
    u8 dest = fetch(); // получить номер регистра назначения
    u8 reg1 = fetch(); // получить источник регистра 1

    xMOV(eax, ptr[&cpuRegs[reg1]]); // переместить данные reg1 в eax
    xMOV(ptr[&cpuRegs[dest]], eax); // переместить eax в регистр dest

    fetch(); // эта функция необходима, потому что каждая команда в нашем процессоре SL3 состоит из 4 байтов
}

// это эмуляция инструкции ADD
void ADD() 
{
    u8 dest = fetch(); // получить номер регистра назначения
    u8 reg1 = fetch(); // получить источник регистра 1
    u8 reg2 = fetch(); // получить источник регистра 2

    xMOV(eax, ptr[&cpuRegs[reg1]]); // переместить данные reg1 в eax
    xADD(eax, ptr[&cpuRegs[reg2]]); // добавить eax с данными reg2 
    xMOV(ptr[&cpuRegs[dest]], eax); // переместить eax в регистр dest
}

// это эмуляция инструкции BR
void BR() 
{
    s8 addr = fetch(); // получить число, которое мы будем увеличивать (уменьшать, если отрицательное) PC
    PC = (PC - 2) + (addr * 4);
    
    // получить указатель на блок перекомпилированного x86 кода,
    // который был перекомпилирован функцией recompileSL3()
    u8* block_pointer = getBlock(PC);
                        
    xJMP(block_pointer); //перейти по указателю, возвращаемому функцией getBlock()
}

// проходит через инструкции и перекомпилирует их,
// пока он не достигнет инструкции BR ().

u8* recompileSL3(u32 startPC) 
{
    u8* startPtr = xGetPtr(); // получаем указатель эмиттера, указываемый в данный момент (начальный указатель блока)
    PC = startPC; // устанавливаем PC на начало PC этого блока
    bool do_recompile = true;
    while (do_recompile) 
       {
        u8 opcode = fetch();
        switch (opcode) 
            {
            case 0: MOV(); break;
            case 1: ADD(); break;
            case 2: // останавливаем перекомпиляцию
                BR();
                do_recompile = false;
                break;
              }
         }
    return startPtr; // возвращает указатель туда, где начинается наш сгенерированный блок x86 кода
}

// получаем указатели на все  наши блоки, которые были перекомпилированы на основе
// начала адреса PC. Будем считать, что память для инструкций
// этого процессора равна 16 кБ, что означает, что она может содержать 1024 * 16 байт 
// имеющейся инструкции. Исходя из этого, имеем  указатель блока 1024 * 16
static u8* blockArray[1024*16];

// возвращает указатель на наш перекомпилированный блок
// если перекомпиляция еще не произошла, блок будет рекомпилироваться и возвратится указатель на него.
// используем __fastcall , потому что он позволяет нам пройти startPC параметр в регистре ecx
// вместо того, чтобы использовать x86 стек

u8* __fastcall getBlock(u32 startPC) 
{
    if (blockArray[startPC] == null
    {
        blockArray[startPC] = recompileSL3(startPC);
    }
    return blockArray[startPC];
}

// базовый эмулятор ЦП с использованием динамической рекомпиляции

void runCPU() 
    {
    // устанавливает эмиттер в начало "эммитирования" инструкций в  rec_cache,
    // который является большим блоком памяти, куда мы можем записать много
    // x86 ассемблерных инструкций
    x86setPtr(rec_cache);    
    
    __asm 
   {
        pushad; // сохраняем все наши регистры
        mov ecx, PC; // перемещаем параметр PC в регистр ecx  (для __fastcall)
        call getBlock; // вызываем функцию getBlock
        jmp eax; // блок, чтобы перейти к возвращаемому в eax
    }

Обратите внимание, что код, описанный выше, не имеет алгоритма для успешного завершения после того, как исполнение рекомпилируемого блока было запущено. Я опускаю этот момент, чтобы не усложнять ситуацию. Предположим, что исполнение кода завершено, и мы можем вернуться к работе с другими частями эмулятора. Также отмечу необходимость пересохранения регистров после завершения исполнения. Кроме того, надо настроить reg_cache на новый адрес х86 эмиттера (чтобы он мог продолжить запись с того места, где остановился, вместо того, чтобы записывать поверх уже рекомпилированных блоков памяти).

Теперь разберемся, как это работает:
- вызываем функцию runCPU(), которая вызывает функцию getBlock() с исходным значением PC. Затем getBlock() проверяет, рекомпилирован ли блок с этим исходным значением; 

- выяснив что рекомпиляция еще не выполнена, функция вызывает recompileSL3() и дает ей это исходное значение. recompileSL3() будет перебирать опкоды, извлекая их, а потом вызывая соответствующие эмулируемые инструкции, которые будут записаны в память х86 инструкций ассемблера; 

- получая правильные результаты, recompileSL3() будет продолжать перебор до тех пор, пока не наткнется на инструкцию BR() (которая будет рекурсивно вызывать getBlock() , пока все адреса не будут рекомпилированы).

После того, как рекомпиляция будет завершена, мы переходим на  начальный исполняемый адрес блока и, таким способом, запускаем исполнение. Код, который поступает на выполнение после перекомпиляции, будет иметь только функции с префиксом 'X' (xMOV, XADD, и т.д.).

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

Кроме того, во время рекомпиляции мы можем провести много оптимизаций, например: regalloc, constant propagation, оптимизированную asm-генерацию для некоторых опкодов, и т.п…( в нашем примере мы этого не делали, чтобы не усложнять процесс).

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

Также замечу, что рекомпилятор может использоваться не только для эмуляции процессора: в pcsx2 он также выполняет рутинную работу по кешированию оптимизированной asm-распаковки, которую в PS2 выполняет vif.

Также хочу заметить, что в настоящий момент pcsx2 обладает следующими рекомпиляторами:
EE рекомпилятор (для MIPS R5900 - ядра процессора)
IOP рекомпилятор (для MIPS R3000A - процессора ввода/вывода)
microVU рекомпилятор (для VU0/VU1, и СОР2 инструкций)
superVU рекомпилятор (может использоваться вместо microVU для VU0/VU1)
newVIF рекомпилятор распаковщика (рекомпилирует vif-распаковку)
r3000air (еще не готов, но вскоре должен заменить IOP рекомпилятор).

Большое спасибо пользователю frozenbit за предоставленную информацию - он перевел основную часть этой статьи.
+2

Комментарии 3

  1. DarteSS
    DarteSS от 6 декабря 2013 01:34
    Большое спасибо за публикацию статьи, многое стало понятнее.
  2. san4es
    san4es от 11 апреля 2014 13:03
    отлично!

    Вот только как тебе развитие идеи: что если pcsx2 с ее эмуляцией и динамической рекомпиляцией вообще не использовать, а использовать только почти-СТАТИЧЕСКУЮ РЕКОМПИЛЯЦИЮ. То есть функции MOV(), ADD() и BR() и остальные надо оформить как inline'овые с включенными на всю плешь настройками оптимизации нашего компилятора. Я бы использовал Visual Studio 2010/2012. И использовать парсер "SL3" кода с вызовами наших MOV(), ADD() и BR(). "почти-СТАТИЧЕСКУЮ" - потому что мы все таки все наши вызовы генерируем при запуске проекта-парсера, но только один раз.

    Кстати развитие идеи: сгенерировали все наши вызовы, потом всю эту последовательность вызовов записать на диск с заголовком MZ и другими блоками необходимыми для запуска win32 приложения.

    Короче в конечном счете в идеале хорошо бы получить некий перекомпилятор ps2 кода, который просто напросто будет генерировать обычный exe'шник.

    Т.к. я это всё не писал (pcsx2), а разбираться в исходниках pcsx2 мне счас лень, могу чего то напутать или недопонять. Но уверен, если бы я немного вник во всю эту кухню - появились бы неплохие идеи по оптимизации и ускорению запуска ps2 игр на PC.

    И вот что нужно для записи exeшника такого:
    1)нужно найти специальный компилятор C++ для x86-x64 с API для общения с ним, который может компилировать а) в память, b) любой блок исходного кода в любое место памяти, c) добавлять MZ заголовки, d) добавлять системные вызовы ОС - для выделения дескрипторов, инициализации исполняемого модуля в ОС и т.д., d) с хорошей оптимизацией, с набором инструкций sse, sse2, mmx и т.д. 
    Ну а далее готовый полный блок памяти просто записать на диск в виде *.exe и все.

    или

    2) изучить спецификацию x86 x64 самому, получить двоичное представление всех команд x86 методом эксперимента, записать их в словарь, самому добавлять MZ заголовок, самому в двоичном виде записывать блок выделяющий дескрипторы у ОС. Короче эксперименты с компилятором стандартным, дизассемблером и чтение книжек по Assembler'у x86 - x64 под Windows поможет.
  3. OilRush
    OilRush от 22 мая 2014 23:30
    Это всё конечно хорошо, вот только если игра использует самоизменяющийся код, все труды будут напрасны. А я почти уверен, что многие игры для ps2 это делают (поправьте, если я не прав), поэтому и используется JIT-компилятор.
    А если вызывать парсер при каждом изменении кода, и потом ждать, пока компилятор всё это хозяйство скомпилит с выкрученными на полную настройками оптимизации, не слишком ли это медленно будет?
Добавить комментарий

Оставить комментарий