Форум Эму-Россия
http://forum.emu-russia.net/

[АРХИВ] Динамическая рекомпиляция
http://forum.emu-russia.net/viewtopic.php?f=13&t=67		 Страница 1 из 1
Автор:  Keyman [ 15 авг 2007, 22:39 ]
Заголовок сообщения:  [АРХИВ] Динамическая рекомпиляция
Автор: Wind - 26 Dec 2004.

Динамическая рекомпиляция – в конечном счете, делает тоже самое, что и интерпретатор. Но делается это более «умно».

Теперь вместо того чтобы, по завершении декодирования мы не сразу исполняем инструкцию, а записываем в память только то, что не обходимо для исполнения.
Пример:
Все та же команда MOVI ее код 0хЕ000:

Напомню, она загружает в регистр «некое» значение. Вот и «запишем в память команды».

mov reg[0], 0х00000000

То же самое со следующей встреченной командой и так до тех пор пока не встретим какую-либо команду перехода или не кончится выделенный кусок памяти в конце блока поставим ret.
В итоге: по окончание мы имеем указатель на начало блока содержащий уже код «понятный» процессору для которого пишется эмулятор.
Исполнив этот блок, мы вернемся к началу цикла и повторим цикл сначала и так…

Но, что нам даст тупое переписывание кода, да вообще-то ничего (впрочем, PCSX делает именно так).

Представим ситуацию, встречаются в коде последовательность команд
MOVI 0х01, R0
SHLL8 R0
SHLL16 R0
MOV R0, R1

Проанализируем этот блок :
Номер цифры соответствует команде.
1) запишет 1 в reg[0]
2) сдвинет на 8 reg[0]
3) сдвинет на 16 reg[0]

В итоге reg[0] окажется в памяти окажется 0x01000000 это можно посчитать на этапе компиляции и итоге сразу записать, одну команду вместо трех
mov reg[0] , 0x01000000

Продолжим анализировать код следующая команда обращает должна записать reg[0] в
reg[1], в итоге код должен был получится таким:

mov reg[0] , 0x01000000
mov eax, reg[0]
mov reg[1], eax

Но ведь можно так

mov eax, 0x01000000
mov reg[1], eax

или даже так
mov reg[1], 0x01000000
Первый случай используют если дальше по коду встретится например такой код
MOV R0, R2

mov eax, 0x01000000
mov reg[1], eax
mov reg[2], eax

Итог мы храним значение в регистре так долго, как долго это возможно т.е. если будет последовательность команд такого вида
MOV R0, R1
MOV R1, R2
MOV R2, R3
MOV R3, R4
MOV R4, R5
MOV R5, R6
MOV R6, R7

То
R0 мы держать в eax
R1 – ecx
R2 – edx
R3 – ebx
R4 – ebp
R5 – esi
R6 - edi

и только после команды MOV R6, R7 мы сохраним eax в reg[0] и загрузим в него новое значение в данном случае R6. Такой подход позволяет минимизировать кол-во обращений к памяти (чтение и запись в память происходят медленней чем та же операция с регистрами)

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

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

И правильно зачем.
Разбиваем память на участки по 4кб и создаем битовую карту, в которой каждый бит соответствует очередным 4кб. Для SEGA DREAMCAST это карта будет иметь 4096 бит
(у этой системы 16мб памяти).
И во время компиляции создаем блоки по 4кб (если по окончании блока не встретилась ни одной инструкции перехода, то ставим ret) и устанавливаем в карте бит.
И во время выполнения компиляции проверяем, а не скомпилировали ли мы этот блок уже если да то просто выполняем его.
Во время какой-либо модификации этого блока мы сбрасываем соответствующий бит в карте.


Небольшое исправление:
Я не совсем прав в отношении битовой карты. Если уж использовать карту то размер ее должен быть 8Мб (16/2), где каждый бит описывает одну команду он устанавливается в случае если команда уже скомпилирована и сброшена в обратном случае. А вообще реализация этой проверки дело фантазии разработчика. Главное она должна быть точна. Часто можно встретить, когда делают проверку на соответствие битов первой и последней команды блока, если они не изменились значит блок «не разрушен». Так вот это яркий пример того, как делать не нужно. Пример «ЧАНКА», не правдами она весьма стабильна.
Автор:  Keyman [ 15 авг 2007, 22:44 ]
Заголовок сообщения:  Re: Динамическая рекомпиляция
RomikB
Добавлю:

Излишняя оптимизация иногда бывает совсем не полезна, особенно когда в исходном коде есть инструкции эквивалентные jmp.
Код:
mov reg[0], 0
label:
add reg[0], 1
...
jmp label


замена на Код:
mov reg[0], 1


может приведет к нерешаемой проблемме "куда же делать jmp?"

Получить наилучшую оптимизацию и избежать проблем можно используя 2-х проходный рекомпилятор. К сожалению для меня он пока лишь теория...
Маленький светловолосый Зайка...

Wind
Не могу не согласится, в два прохода будет правильней, но для меня это также теория и я не стал поэтому об этом упоминать

simplexe
парни раскажите про двухпроходную плз хоть теорию...
АМ2 FX 62/2x2048 Mb DDR2 800/nF-590SLI/2xn7950GTX 512 Mb/2x250 Gb SATA-2 16Mb хехе...

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

Organic
Вот моя версия как может быть устроен рекомпилятор (Recompiler, DynaRec, JITC). В качестве примера был выбран эмулятор Gamecube, где рекомпилятор преобразует инструкции PowerPC в инструкции x86 (чтобы не писать везде "Процессор A" и "Процессор B").

Самый главный показатель для рекомпилятора - это объём памяти, где может находится эмулируемая программа. В большинстве случаев - это один большой буфер для оперативной памяти (RAM) и более меньший по размеру буфер для ROM/BIOS. Дело в том, что для рекомпилятора необходимо на порядок больший объём памяти, для хранения рекомпилированного кода, который напрямую зависит от размера RAM/ROM. Однако моя схема позволяет кроме динамической рекомпиляции ещё и поддерживать динамическое распределение памяти, что значительно снижает нагрузку на память.

В разных системах применяются разные способы адресации. Например программы CPU работают с виртуальными адресами, тогда как ОС прозрачно для них транслирует виртуалный адрес в адрес физический. Любое железо (на сегодня) работает только с физическим адресами. Принципы виртуальной адресации - это отдельный разговор, в данном случае нам достаточно знать что виртуальное адресное пространство используется для распределения в нем различных аппаратных устройств. Так как рекомпилятор работает с буфером RAM/ROM, которые по-сути тоже аппаратные устройства, то и и термин "адресация" в рекомпиляторе применяется только к физическому адресу.

С чем работает рекомпилер мы разобрались (RAM, ROM), как он использует доступ к RAM и ROM - тоже (физический адрес в RAM или ROM). Осталось разобраться, как рекомпилер преобразует инструкции PowerPC в x86.

Первое понятие - это "группа". Группой может быть одна или несколько инструкций PowerPC. Важно - группа всегда исполняется целиком. Так что если частным случаем группы в интерпретаторе является одна инструкция, и выполняются инструкции одна за другой, то в рекомпиляторе выполняются группы - также одна за другой. Критерием к выбору размера группы может быть что угодно - например поток инструкци до инструкции перехода, или скажем N инструкций, или количество инструкций в одной странице памяти (4096 байт кода). Я выбираю последний случай, так как это более удобно для меня (и PowerPC).

Вот как выглядит алгоритм рекомпиляции:
Код:
НАЧАЛО:
ФИЗИЧЕСКИЙ АДРЕС = ТРАНСЛИРОВАТЬ(PC)
ОШИБКА ТРАНСЛЯЦИИ ? ИСКЛЮЧЕНИЕ(ОТКАЗ ВИРТУАЛЬНОГО АДРЕСА)
ВЫПОЛНИТЬ ГРУППУ('ФИЗИЧЕСКИЙ АДРЕС')
ПЕРЕЙТИ НА НАЧАЛО



На первом этапе производится трансляция виртуального адреса текущего счетчика команд (PC) в адрес физический. Как видно размер группы в страницу выбран не зря. Вместо того, чтобы транслировать все адреса в районе PC...PC+размер группы и проверять их на отказ (page fault), достаточно проверить транслируется ли адрес всей страницы, где находится группа (это особенность PowerPC). Для других систем критерий выбора гранулярности группы может быть иным, но это не важно. Главное получить физический адрес группы в оперативной памяти (или ROM).

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

Кэш рекомпилятора - это область памяти (буфер) где храняться уже рекомпилированные куски кода (группы). Кэш может быть статическим (когда место для него выделяется один раз - большим массивом) или динамическим (когда место для новой группы выделяется по мере необходимости её добавления в кэш). В статическом виде кэш выглядит так : GROUP JITC_CACHE[MAX_GROUPS]. Как видно, может произойти ситуация переполнения кэша. Это лечится либо путём увеличения MAX_GROUPS, либо заворачиванием кэша на нулевую позицию (естественно старый код уничтожается). Динамический кэш выглядит почти как статический, но он предусматривает место для всех групп. Например размер оперативной памяти - 24 MB, размер группы - 4096 байт, значит всего может быть 24MB/4096 = 6144 групп. Вот так будет выглядеть динамический кэш на Си: GROUP *JITC_CACHE[6144]. Термин "динамический" используется потому, что мы вызываем функцию Си malloc() не сразу для всех групп (что требует много памяти), а только тогда, когда группу необходимо рекомпилировать. Изначально весь динамический кэш заполнен значением NULL, это означает что там нет групп.

Очистка кэша рекомпилятора ("flush", "invalidate") - такая ситуация может возникнуть, когда эмулируемая программа использует само-модифицирующийся код. Т.е. новые инструкции PowerPC, записанные в RAM уже не соответствуют старому рекомпилированному коду. Поэтому необходимо указать рекомпилеру, что группа "устарела" и нуждается в повторной рекомпиляции.

Вот алгоритм исполнения одиночной группы (Примечание: все параметры удобно передавать через регистры x86, используя специальный вызов в Си - FASTCALL).
Код:
НАЧАЛО ПОДПРОГРАММЫ 'CALL GROUP' ('ФИЗИЧЕСКИЙ АДРЕС'):
Группа находится в кэше ? Если нет - INIT_GROUP('ФИЗИЧЕСКИЙ АДРЕС')

Получить указатель на рекомпилированный x86 код:
void (*GroupPtr)(void) = LOCATE_GROUP('ФИЗИЧЕСКИЙ АДРЕС')

Выполнить группу :
GroupPtr();

ВЫХОД

НАЧАЛО ПОДПРОГРАММЫ 'LOCATE GROUP' ('ФИЗИЧЕСКИЙ АДРЕС'):
RETURN (GROUP *)JITC_CACHE['ФИЗИЧЕСКИЙ АДРЕС' / 4096]



Так как мы используем динамический кэш для рекомпилятора, то первым делом нужно проверить существует-ли там группа, соотвествующая физическому адресу. Если в кэше присутствует значение NULL, то мы вызываем malloc и помещаем полученный указатель в кэш.

Подпрограмма LOCATE_GROUP возвращает начало группы, на которую передается управление путем вызова.

Теперь наступает самый главный момент - эмулятор попадает на начало группы. Что-же там находится, после добавления группы в кэш путём вызова malloc() ? Очевидно мусор. На самом деле функция INIT_GROUP выполняет ещё одно важное действие - вместо того, чтобы добавлять в кэш указатель на только что созданную группу, INIT_GROUP помещает туда указатель на небольшой кусочек кода:
Код:
НАЧАЛО STUB ('ФИЗИЧЕСКИЙ АДРЕС'):
RECOMPILE_GROUP('ФИЗИЧЕСКИЙ АДРЕС')
ВЫХОД



Этот код передаёт управление непосредственно генератору x86-кода, который преобразует 4096 байт кода PowerPC в код Intel/AMD x86.
Код:
НАЧАЛО ПОДПРОГРАММЫ 'RECOMPILER GROUP' ('ФИЗИЧЕСКИЙ АДРЕС'):

FOR(I=0; I<1024; I++)
СЧИТАТЬ ИЗ ПАМЯТИ СЛЕДУЮЩУЮ ИНСТРУКЦИЮ PowerPC (4 байта).
РЕКОМПИЛИРОВАТЬ ЭТУ ИНСТРУКЦИЮ И СГЕНЕРИРОВАТЬ КОД x86.

ВЫХОД



После того, как группа рекомпилируется, вместо указателя на STUB, в кэш попадает адрес только что сгенерированного кода. Таким образом реализуется динамическая рекомпиляция.

А что делать, если нам необходимо повторно рекомпилировать какую-нибудь группу (см. Очистка кэша) ? Для этого достаточно заменить указатель в кэше на STUB, и при вызове группы она будет повторно рекомпилирована.

Но качественный рекомпилятор отличается от некачественного не тем, как он управляет процессом рекомпиляции, а тем как он оптимизирует генерацию кода. Об этом я постараюсь рассказать в следующий раз.
0 error(s), 0 warning(s)

Последний раз редактировалось: Organic (13 Июн 2005 23:50), всего редактировалось 1 раз

Wind
Хорошо написал, один момент я не понял, ты пишешь, что компилируешь блоки целиком по 4кб, а зачем продолжать компиляцию если ты встретил инструкцию перехода, ведь следом за ней очень вероятно может находится «не код»?
И еще, а если так случилось, что переход внутрь этого самого блока, что ты тут делаешь?

Organic
Цитата:
Цитата:
ведь следом за ней очень вероятно может находится «не код»?


Ну если там вероятно находится "не код", значит он вероятно и не будет исполняться. Но это - вероятно, тем более, что откомпилить несколько лишних инструкций не займет много времени. Ты больше потратишь времени, на вычисление переходов внутри группы, чтобы выяснить действительно-ли вот этот переход - последний.
Цитата:
Цитата:
И еще, а если так случилось, что переход внутрь этого самого блока, что ты тут делаешь?


Блин вначале не допер.. Можно завести доп. таблицу переходов внутри группы, а можно сделать ещё одну look-up таблицу для сопоставления физического адреса и отрекомпиленного кода. Если переход локальный - внутри группы, то юзать локальную таблицу и пропатчить переходы после рекомпиляции всей группы. В общем случае - ссылка на глобальную таблицу, где также стоят STUB по умолчанию. Но я в деталях не стал рассматривать :) Это уже у кого как получится спрограммировать..
0 error(s), 0 warning(s)

Wind
Цитата:
Цитата:
Ну если там вероятно находится "не код", значит он вероятно и не будет исполняться.


Зато вероятно компилятор будет впустую пытаться компилировать ненужный код, и выдавать кучу исключений "неизвестная команда".
Цитата:
То же самое, что и сделает интерпретатор - попытается выролнить его. А это уже ошибки программы а не эмулятора.

Выровнит, кого куда? Ты о чем? Почему не может быть переход внутрь блока? Простая ситуаци переход по значению регистра, на этапе компиляции ты никогда не сможешь вычислить куда будет сделан переход.

Organic
Цитата:
Цитата:
Зато вероятно компилятор будет впустую пытаться компилировать ненужный код, и выдавать кучу исключений "неизвестная команда".


Так в рекомпиляторе эти сообщения выводятся не на этапе генерации кода, а во время исполнения этого кода (по крайней мере у меня).

А можно сделать размер группы равную одной инструкции, тогда вообще отпадет надобность в проверке переходов. Например размер оперативной памяти 24МБ, размер группы - 1 инструкции (4 байт), количество групп - 6291456.
Юзаем GROUP *JITC_CACHE[6291456]. Ресурсоемко, зато проще.
0 error(s), 0 warning(s)

Wind
Оригинально, и как такой код можно сгенерировать, а главное зачем такой генерировать? Собщения должны выводится на этапе компиляции, если неизвестная команда значит все ошибка.

Цитата:
Цитата:
А можно сделать размер группы равную одной инструкции, тогда вообще отпадет надобность в проверке переходов. Например размер оперативной памяти 24МБ, размер группы - 1 инструкции (4 байт), количество групп - 6291456.
Юзаем GROUP *JITC_CACHE[6291456]. Ресурсоемко, зато проще.


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

Organic
Цитата:
Цитата:
Оригинально, и как такой код можно сгенерировать, а главное зачем такой генерировать? Собщения должны выводится на этапе компиляции, если неизвестная команда значит все ошибка.


Нет - это не совсем правильно. У меня в эмуляторе вообще не выводятся какие-либо сообщения, о том что инструкция неправильная. В документации четко написано, что процессор делает когда встречает неверную инструкцию - он вызывает исключение "invalid opcode".
Цитата:
Цитата:
если неизвестная команда значит все ошибка


Угу, а в интерпретаторе тоже так ? Если за return находится мусор - он тоже ошибку выводит?
Цитата:
Цитата:
единственое, как определить, что блок разрушен, для меня самая большая проблема.


А для меня нет :) В PowePC используется write-back кэш и инструкция "Invalidate I-Cache". Процессор сам указывает какой код нужно обновить :)

В отношении систем с write-through кэшем самым вероятным признаком наличия само-мод. кода является CD/DVD DMA.
0 error(s), 0 warning(s)

Wind

Цитата:
Цитата:
Нет - это не совсем правильно. У меня в эмуляторе вообще не выводятся какие-либо сообщения, о том что инструкция неправильная. В документации четко написано, что процессор делает когда встречает неверную инструкцию - он вызывает исключение "invalid opcode"..


Насчет не совсем правильно я бы не согласился, верноясть того, что закуручен некий алгоритм на исключениях "invalid opcode" ничтожно мал, но все же если попалась подобная программа то я рекомендую ее отложить в сторону и до тех пор пока процессор не будет отлажен к ней не возвращаться.
Цитата:
Цитата:
Угу, а в интерпретаторе тоже так ? Если за return находится мусор - он тоже ошибку выводит?


Определено так по выше описаной причине. Например в случае c Sh4 в документации нет описания двух инструкций, а представь если б я не выводил сообщений, а вызывал исключения, тогда бы я по сей день пытался понять почему же не работает.
Цитата:
Цитата:
А для меня нет :) В PowePC используется write-back кэш и инструкция "Invalidate I-Cache". Процессор сам указывает какой код нужно обновить :)

Процессор был сделан для того, чтобы его заэмулировали :)
Цитата:
Цитата:
В отношении систем с write-through кэшем самым вероятным признаком наличия само-мод. кода является CD/DVD DMA.


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

NovaStorm
Ну для самомодифицирующегося кода нужно держать таблицы отражающие изменения блоков. ТЕ если блок менялся, и мы в него входим при выполнении - нужно перекомпилить заново... Я так понимаю?
Автор:  Keyman [ 15 авг 2007, 22:50 ]
Заголовок сообщения:  Re: Динамическая рекомпиляция
Wind
Цитата:
Цитата:
Ну если там вероятно находится "не код", значит он вероятно и не будет исполняться. Но это - вероятно, тем более, что откомпилить несколько лишних инструкций не займет много времени. Ты больше потратишь времени, на вычисление переходов внутри группы, чтобы выяснить действительно-ли вот этот переход - последний.


Цитата:
Цитата:
Блин вначале не допер.. Можно завести доп. таблицу переходов внутри группы, а можно сделать ещё одну look-up таблицу для сопоставления физического адреса и отрекомпиленного кода. Если переход локальный - внутри группы, то юзать локальную таблицу и пропатчить переходы после рекомпиляции всей группы. В общем случае - ссылка на глобальную таблицу, где также стоят STUB по умолчанию. Но я в деталях не стал рассматривать :) Это уже у кого как получится спрограммировать..


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

RomikB
Давно не был на форуме, так что начну своё возвращение с описания своего динамического рекомпилятора SonyPSX. R3000A(MIPS) в x86.

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

Главная мысль: Каждой 4-х байтной инструкции MIPS ставится в соответствии 16 байтная последовательность иструкций х86.

Таким образом любому физическому адресу в MIPS (mips_addr) соответствует адрес в x86 x86_addr = x86_base + mips_addr * 4.

Памяти в PSX 2Мб, таким образом рекомпилятор занимает 2Мб данные PSX плюс 2*4=8Мб, плюс 2, 4 или 8 Мб (память переходов в зависимости от реализации), всего 12, 14 или 18Мб.

План:
1) Переход на выполнение следующей инструкции.
а) если декодирована, то выполняеться (1)
б) если не декодирована то запускаеться "заглушка" код которой записан по этому адресу(2)
2) декодирование иструкции в 16 байтную последовательность
а) если простая инструкция то декодирование следующей инструкции(2)
б) если инструкция перехода то декодирование перехода(3)
3) декодирование инструкции перехода и следующий за ней инструкции (т.к. в MIPS инструкция перехода выполняеться вместе со следующей инструкцией.)
4) К пункту 1.

Рассмотрим пункт основной пункт 3:
У нас есть 2 инструкции. Мы получаем после декодирования 32 байта в памяти рекомпилятора (на 1 инструкцию 16 байт) и ещё 32, 40 или 48 байт в памяти переходов которые распределяються следующим образом.
Память рекомпилятора:
(16)Необходимые динамические вычисления (расчет адресов, проверка условия) и переход в память переходов (если надо).
(16)Декодированная спареная к переходу инструкция.
Память переходов:
(8,16)Сохранение адреса возврата(опционально)
(16)Декодированная спареная к переходу инструкция.
(8) вызов функции тайминга
(8) переход.

Я понимаю что всё муторно и непонятно, поэтому рассмотрим теперь всё по порядку.

Инициализируем регистры, память.
Заполняем память рекомпилятора заглушками (вызовами функции рекомпиляции)
Загружаем в память PSX исполняемый файл.
Определяем точку входа mips_start_addr и передаем управление x86_start_addr = x86_base + mips_start_addr * 4
Инструкция не декодирована, поэтому вызываеться "заглушка" и декодируеться блок инструкций до первого перехода.
Выполняеться блок инструкций.
Если переход без условный или условный с выполнением условия то запускаеться фунция тайминга и затем перезход
Декодировани или выполнение следующего блока.

Я думаю всё равно не понятно так что жду вопросов, если смогу - отвечу.
Маленький светловолосый Зайка...

Wind
В ближайщее время тоже распишу свой вариант динамческой рекомпиляции.

RomikB

Цитата:
Wind писал:
В ближайщее время тоже распишу свой вариант динамческой рекомпиляции.


С сорцами? ;-)

Wind
Цитата:
RomikB писал:
С сорцами? ;-)


Да мне жалко могу и сырцами.

RomikB

Цитата:
Wind писал:
RomikB писал:
С сорцами? ;-)

Да мне жалко могу и сырцами.

Ну раз не жалко то давай. (Буду воровать твои идеи). =)))

Wind
Итак, предлагаю свой вариант построения динамической рекомпиляции.(Из sh4 в х86).
Сразу хочу предупредить эта статья, требует серьезных знаний в области программирования.

Перед запуском компилятора необходимо произвести некоторые подготовительные действия, они сведены в следующую функцию:
Код:

u8 *Rptr;
u8 *RMem;
u8 *RRom;
u8 *RRam;
u32 *RGetAddr;

typedef struct
{
u32 x86reg;
u32 sh4reg;
u32 old;
} _x86regs;

_x86regs x86regs[6];

void RInit()
{
u32 i, r;

/*
Выделяем память.

RRom – в этот участок памяти в последующем будут записываться адреса рекомпилированых кусков кода, находящихся в БИОСе.

RRam – в этот участок памяти в последующем будут записываться адреса рекомпилированых кусков кода, находящихся в оперативной памяти.

RMem – в этот участок памяти в последующем будут записываться рекомпилированый код.

RGetAddr – этот участок необходим для построения LOOK-UP таблиц.

*/

RRom = (u8*) calloc(0x00200000, 2);
RRam = (u8*) calloc(0x01000000, 2);
RMem = (u8*) calloc(0x01000000, 1);
RGetAddr= (u32*)calloc(0x00400000, 1);


/*
Строятся LOOK-UP таблицы.
*/
for (i=0; i<0x00200; i++) RGetAddr[i + 0x00000] = (u32)&RRom[i << 13];
for (i=0; i<0x00200; i++) RGetAddr[i + 0x80000] = (u32)&RRom[i << 13];
for (i=0; i<0x00200; i++) RGetAddr[i + 0xA0000] = (u32)&RRom[i << 13];

for (i=0; i<0x01000; i++) RGetAddr[i + 0x0c000] = (u32)&RRam[i << 13];
for (i=0; i<0x01000; i++) RGetAddr[i + 0x8c000] = (u32)&RRam[i << 13];
for (i=0; i<0x01000; i++) RGetAddr[i + 0xAc000] = (u32)&RRam[i << 13];

Rptr = RMem;

/*
Инициализируем структуру x86regs, необходимо для работы «регкешинга»

x86reg – это поле содержит номер регистра х86
sh4reg – это поле содержит номер регистра sh4
old - это поле содержит «время» последнего обращения к регистру

Регистры EAX и ESP в «регкешинге» не участвуют, первый используется для хранения временных данных, а второй должен указывать на стек.

*/
for(i = 0, r = 7; i < 6; i++, r--)
{
if(r == 4) r--;
x86regs[i].x86reg = r;
x86regs[i].sh4reg = -1;
x86regs[i].old = 0;
}
}



Работа компилятора начинается с вызова следующей функции:
Код:

typedef void (*RECFUNC)();

void RExecute()
{
for(;;)
{
/*
В переменную p записываем адрес начала 4кб сегмента.
«Зануляем» переменную recExecute.

*/
RECFUNC *p = (RECFUNC*)RGetAddr[sh4.pc >> 12];
RECFUNC recExecute = NULL;

/*
Если p не равно нулю, то в recExecute записываем адрес начала рекомпилированого кода, адрес считывается по смещению внутри 4кб сегмента.

Если p равно нулю, то значит произошла ошибка и необходимо завершить работу эмулятора.
*/

if(p)
{
recExecute = *(RECFUNC*)&p[(sh4.pc >> 1) & 0x07ff];
}
else
{
RErorr();
}

/*
Если recExecute содержит NULL, то значит этот участок еще не скомпилирован, вызывается функция компиляции, ее работа будет рассмотрена ниже. По окончании компиляции в recExecute будет записан адрес начала скомпилированного кода.

*/
if(recExecute == NULL)
{
Rcompile();
recExecute = *(RECFUNC*)&p[(sh4.pc >> 1) & 0x07ff];
}

/*
Исполняем скомпилированный код.
*/

recExecute();
}
}



Рассмотрим работу компилятора:
Код:

void Rcompile()
{
u32 i;

/*
В переменную p = записываем адрес начала 4кб сегмента.
*/

RECFUNC *p = (RECFUNC*)RGetAddr[sh4.pc >> 12];

/*
Если памяти для компиляции осталось мало, то «зануляем» всю память и заворачиваем указатель на код на начало.
*/

if(((u32)Rptr - (u32)RMem) >= (0x01000000 - 0x8000))
{
memset(RRom, 0, 0x00200000 * sizeof(u32));
memset(RRam, 0, 0x01000000 * sizeof(u32));
memset(RMem, 0, 0x01000000 * sizeof(u8 ));
Rptr = RMem;
}

/*
Выравниваем указатель на 32-ную границу и записываем его значение по смещению внутри 4кб сегмента.
*/

x86ptr = Rptr;
align(x86ptr, 32);

p[(sh4.pc >> 1) & 0x07ff] = (RECFUNC)x86ptr;

pc = sh4.pc;
time = 0;
loadcw = 0;
sh4.branch = 0;
cycle = 0;

/*
Компилируем блок размером не более 4кб(одна инструкция sh4 это 2 байта).
*/

for(i = 0; i < 2048; i++)
{
sh4.code = memRead16(pc);
ROpcodeTableAll[(sh4.code >> 12) & 0xf]();
pc += 2;

if(sh4.branch) break;
}

if(!sh4.branch)
MOV32ItoM((u32)&sh4.pc, pc + 2);

FlushAll();
LoadCW();
ADD32ItoM((u32)&sh4.cycle, cycle);
CALL32((u32)&CpuTest);
RET();

Rptr = x86ptr;
}



Рассмотрим пример компиляции инструкции:
Код:

void RMOVI()
{
/*
Функция GetX86reg возвращает номер свободного регистра х86 или регистра который уже сопоставлен значению _Rn_.
*/
x86Reg32Type Rn = GetX86reg(_Rn_, ModeWrite);

/*
В зависимости от значения _ImmS_ компилируем необходимый код.
*/

switch(_ImmS_)
{
case 0:
XOR32RtoR(Rn, Rn);
break;

case 1:
XOR32RtoR(Rn, Rn);
INC32R(Rn);
break;

case -1:
XOR32RtoR(Rn, Rn);
DEC32R(Rn);
break;

default:
XOR32RtoR(Rn, Rn);
OR32I8toR(Rn, _ImmS_);
break;
}

/*
Увеличиваем счетчик тактов
*/
cycle++;
}



На этом пока все, задавайте ваши вопросы.

RomikB
1) Что то не видно как ты используешь кэширование регистров
2) Поразительное сходство с исходниками PCSX. :)
Маленький светловолосый Зайка...

Wind
Цитата:
RomikB писал:
1) Что то не видно как ты используешь кэширование регистров
2) Поразительное сходство с исходниками PCSX. :)


Я же написал GetX86reg возвращает регистр, его номер это и есть регкешинг. На счет сходства это ты зря, им до меня как...

RomikB
Угу, ты один переплюнул, группу разроботчиков =)

В связи с тем что я не знаком с устройством sh4, то вопросов нету.

Давай выпускай эмуль рулезный!

Wind
Я сейсас не в состоянии над ним работать, времени нет вообще хочешь могу передать все сырцы, биос пускающие и ты можешь продолжить работу над ним

RomikB
Цитата:
Wind писал:
Я сейсас не в состоянии над ним работать, времени нет вообще хочешь могу передать все сырцы, биос пускающие и ты можешь продолжить работу над ним


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

Wind
Вот и я не могу сейчас никак продолжить работу, мне лично необходимо добавить работу с CD-ROM(там некое подобие ATAPI протокола), а дальше видно будет. Ты же над playstation работаешь у тебя хоть плугины есть а мне и графику приходится самому. Вообщем один я буду еще долго заканчивать.

RomikB
Динамический Рекомпилер с предварительным анализом.

Допущения:
1) Каждая функция имеет только одну точку входа.
2) Адрес точки входа - нижняя граница всех адресов функции.
3) Каждая функция имеет конечное число точек выхода.
4) Каждая функция не являеться самомодифицируемой.
5) Точка выхода не может быть условной.

Идея:
Рекомпиляция проходит по функциям.
Рекомпиляция функции включает рекомпияцию всех адресов начиная от точки входа до всех точек выхода, включая локальные переходы, но исключая внешние вызовы.
Код функции при помощи точки входа, точек выхода, точек локального перехода, и точек куда ведут локальные переходы, делиться на блоки - минимальные единицы рекомпиляции.

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

Реализация:
Начиная с точки входа проходим по всей функции и создаем список адресов обычных адресов, адресов локального перехода и адресов куда ведут локальные переходы. Таким образом мы получаем блоки. Затем рекомпилируем их начиная с первого. Каждый блок отдельно оптимизируеться (N-проходный рекомпилер), и в конце ставиться прирост тайминга.
Как вариант возможна рекомпиляция блоков на лету ( а не вся функция ), с предварительным анализом всей функции.

Отличия:
Максимальльная оптимизация при минимальном обьеме.

Колинг:
Большинство аспектов знаю как реализовать легко и изящьно, другие муторно, а часть пока не обдумал.

RomikB
Вопросы коментарии будут? А то начну реализовывать и окажеться что я ошибся :(
Автор:  Keyman [ 15 авг 2007, 22:53 ]
Заголовок сообщения:  Re: Динамическая рекомпиляция
Wind
Да так реализовать-то это все можно, но все же я не поклоник такого подхода, я свой вариант описал выше, для меня он единственно верный.

RomikB
Что именно тебе не нравиться в этом подходе?

Или я опять написал так что никто не понял? :(

PS: Единственно верного варианта не бывает.

Wind
Мне все нравится, кроме этого запутаного анализа переходов, и еще введение N-проходного компилятора

RomikB
почему запутанный?

N кстати может быть равен 1 (специально для тебя) ;-)

Wind
Цитата:
RomikB писал:
почему запутанный?


Ну может потому, что я его не очень понял :)
Цитата:
RomikB писал:
N кстати может быть равен 1 (специально для тебя) ;-)


С математикой я знаком, но ты явно подразумеваешь N > 1.

RomikB
Вот, набросал на досуге один из вариантов (один - так как пока набрасывал придумал ещё один).

table - таблица соответствия адресов.
Код:
void* GetAddr(long addr)
{
if( addr in table ) return table[addr];
return RecompileFunction( addr );
}

void* RecompileFunction( long addr )
{
GetBlocks();
RecompileBlocks();
}

void GetBlocks(void)
{
next_addr = addr;
end_addr = addr;
while(1)
{
add_addr_status( next_addr, STATUS_CHECK );
if( jmp_instruction(next_addr) )
{
if( local_jmp(next_addr) )
{
add( next_addr_table, jmp_target(next_addr) );
add_addr_status( next_addr, STATUS_LOCALJMP );
add_addr_status( jmp_target(next_addr), STATUS_JMPTARGET );
}
else
{
add_addr_status( next_addr, STATUS_EXTERNJMP );
}

if( !conditional_jmp(next_addr) )
{
if( next_addr > end_addr ) end_addr = next_addr;
do
{
if( next_addr_table.isempty() ) break;
next_addr = next_addr_table.last();
}
while( check_addr_status( next_addr, STATUS_CHECK ) );
continue;
}
}
next_addr++;
}
}

void RecompileBlocks()
{
next_addr = addr;
start_block();

while(1)
{
if( check_addr_status( next_addr, STATUS_JMPTARGET ) )
{
end_block();
start_block();
}

if( check_addr_status( next_addr, STATUS_LOCALJMP ) ||
check_addr_status( next_addr, STATUS_EXTERNJMP ) )
{
recompile_instruction();
end_block();
if( next_addr == end_addr ) break;
else
{
do
{
next_addr++;
}
while( !check_addr_status( next_addr, STATUS_EXTERNJMP ) );
start_block();
continue;
}
}

recompile_instruction();
next_addr++;
}
}
Автор:  romanich [ 06 окт 2009, 05:37 ]
Заголовок сообщения:  Re: [АРХИВ] Динамическая рекомпиляция
возникло несколько вопросов в ходе разбирательств с динамической рекомпиляцией:

1)

Цитата:
Представим ситуацию, встречаются в коде последовательность команд
MOVI 0х01, R0
SHLL8 R0
SHLL16 R0
MOV R0, R1

В итоге reg[0] окажется в памяти окажется 0x01000000 это можно посчитать на этапе компиляции и итоге сразу записать, одну команду вместо трех
mov reg[0] , 0x01000000


Что нужно делать в случае если в середине этого фрагмента кода будет выполнен переход?
Тоесть:

Код:
MOVI 0х01, R0
JumpLabel:
SHLL8 R0
SHLL16 R0
MOV R0, R1
...
JMP JumpLabel
...


2) Как реализовать переходы типа:

Код:
JMP EAX
...
JMP [ECX]


3) иногда может случиться, что нельзя будет задаться фиксированным количеством набора команд (объём в байтах) - нужно брать максимальные, а свободные замещать NOP-ами. Не ведёт ли это к сильному понижению производительности?

4) обращения к памяти и регистрам периферии - как? Приёдется делать дополнительные вызовы, например:

Код:
MOV EAX,[EDI+0x8]
INC EAX
MOV [EDI+0x10],EAX


после рекомпиляции будет (пишу в си-макросах):

Код:
EAX=ReadMemoryDword(EDI+8);
EAX++;
WriteMemoryDword(EDI+0x10,EAX);
CalculateFlags();


где ReadMemory и WriteMemory - макросы обращения к памяти или регистрам аппаратуры (switch case ?)

как можно быстрее?

5) Можно ли заставить ПЕРЕХОДИТЬ на сишные функции вместо ВЫЗОВА? (jump вместо call) без применения адресов меток (такое только в GCC) ?

6) Не совсем понятно как вычислить адрес перехода уже на скомпилированный участок кода, если инструкции эмулируемого процессора реализуются разной длиной рекомпилированного кода?

7) Некоторые процессоры требуют принудительные flush'и кэша. Например, если память закэширована по коду и по данным (кэши разные), то перед исполнением программы в памяти, необходимо про-flush'ить кэш данных на всём диапазоне адресов (чтобы с кэша данных гарантировано упало в память - случай кэша с обратной записью, кешируется не только чтение , но и запись) - не понизит ли это производительность?

8) Если организовать рекомпиляцию через Assembler, то прийдётся каждому регистру эмулируемого процессора сопоставить регистр процессора целевой платформы. Требуется создавать прологи и эпилоги, чтобы Си- компилятор не разрушил содержимое этих регистров (он сам может их пользовать). Не понизит ли это производительность?

9) Ну и совсем экзотика. :) Некоторые архитектуры (BlackFin например) не имеет "традиционной записи" кодов на языке Ассемблер (более похоже на Си). Например:

Код:
{
register u32 p;
p=7;
*(u32*)p=8;
}


он сделает как:

Код:
R0=0x00000007;
R1=0x00000008;
[R0]=R1


тоесть никаких традиционных mov'ов нет. Затруднит ли это написание динамического рекомпилятора?


P.S. прошу не пинать, так как пытаюсь разобраться (:
Автор:  Wind [ 06 окт 2009, 15:06 ]
Заголовок сообщения:  Re: [АРХИВ] Динамическая рекомпиляция
Код:
Код: Выделить всё
MOVI 0х01, R0
JumpLabel:
SHLL8 R0
SHLL16 R0
MOV R0, R1
...
JMP JumpLabel
...

Это разобьеться на два отдельный ни чем не связаных блока.
Это первый блок:
Код:
MOVI 0х01, R0
SHLL8 R0
SHLL16 R0
MOV R0, R1
...
JMP JumpLabe


После перехода второй новый:
Код:
SHLL8 R0
SHLL16 R0
MOV R0, R1
...
JMP JumpLabe

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

Цитата:
3) иногда может случиться, что нельзя будет задаться фиксированным количеством набора команд (объём в байтах) - нужно брать максимальные, а свободные замещать NOP-ами. Не ведёт ли это к сильному понижению производительности?

Читай отовет выше, никаких NOP нет.

Цитата:
4) обращения к памяти и регистрам периферии - как? Приёдется делать дополнительные вызовы, например:

Да, обычно удобно делать на доступ к оперативке если да то быстро ее читать, иначе переход в ф-ию для дальнейших разбирательств что и зачем. CALL интсрукция на большинстве платформ дорогая инструкция, а вот коротки переход с проверкой достаточно быстро работает. Поэтому имеет смысл проверять первоначально доступ к оперативке ибо большая часть доступа к ней, процентов 98.

Цитата:
где ReadMemory и WriteMemory - макросы обращения к памяти или регистрам аппаратуры (switch case ?)
как можно быстрее?

Заранее сгенерированые переходы LookUp таблички, но требуеться опертивка.

Цитата:
5) Можно ли заставить ПЕРЕХОДИТЬ на сишные функции вместо ВЫЗОВА? (jump вместо call) без применения адресов меток (такое только в GCC) ?

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

Цитата:
6) Не совсем понятно как вычислить адрес перехода уже на скомпилированный участок кода, если инструкции эмулируемого процессора реализуются разной длиной рекомпилированного кода?

Транслируешь текущий указатель на код. Проверяешь если у тебя блок с таким входом если да то идешь на него иначе новый комилишь.

Цитата:
7) Некоторые процессоры требуют принудительные flush'и кэша. Например, если память закэширована по коду и по данным (кэши разные), то перед исполнением программы в памяти, необходимо про-flush'ить кэш данных на всём диапазоне адресов (чтобы с кэша данных гарантировано упало в память - случай кэша с обратной записью, кешируется не только чтение , но и запись) - не понизит ли это производительность?

Это вещь сложная, падение производительности гарантировано.

Цитата:
Если организовать рекомпиляцию через Assembler, то прийдётся каждому регистру эмулируемого процессора сопоставить регистр процессора целевой платформы. Требуется создавать прологи и эпилоги, чтобы Си- компилятор не разрушил содержимое этих регистров (он сам может их пользовать). Не понизит ли это производительность?

Если с умом подойти то это даже не проблема.

Цитата:
9) Ну и совсем экзотика. Некоторые архитектуры (BlackFin например) не имеет "традиционной записи" кодов на языке Ассемблер (более похоже на Си). Например:

Хм, не представляю себе архитектур где в конечном итоге все не сводиться к ассемблеру.
Автор:  HardWareMan [ 06 окт 2009, 20:20 ]
Заголовок сообщения:  Re: [АРХИВ] Динамическая рекомпиляция
Wind писал(а):
Цитата:
9) Ну и совсем экзотика. Некоторые архитектуры (BlackFin например) не имеет "традиционной записи" кодов на языке Ассемблер (более похоже на Си). Например:

Хм, не представляю себе архитектур где в конечном итоге все не сводиться к ассемблеру.

Есть опкоды, ассемблер - это ярлычки к опкодам для удобного понимания и запоминания человеком. Так что не вижу проблемы. Например, какая разница будет, если эти оба кода:
Код:
void* SomeProc(byte a,b)
{
}
SomeProc(3,6)

или

MVI A,3
MVI B,6
CALL SomeProc

В конечном итоге дадут такой код на платформе i8080:
Код:
3EH, 03H
06H, 06H
CDH, xxH, xxH (xxxxx - адрес процедуры SomeProc)
Автор:  romanich [ 07 окт 2009, 12:34 ]
Заголовок сообщения:  Re: [АРХИВ] Динамическая рекомпиляция
Это всё хорошо, но BlackFin - процессор НЕ для программирования на ассемблере!
Там 10-ступенчатый конвеер и при ручном кодировании эффективности не будет.
Мало того, имеется небольшая тележка с глюками - силиконовые аномалии.
Одна из них - вкрапления "лишних" NOP-ов в код. Если этого в определённых местах не сделать - будут глюки.
Эта тема называется - обход аппаратных ошибок компилятором.

Вот фрагмент на "ассемблере" BlackFin:
Код:
//-------------------------------------------------------------------
// line ".\cpu.c":3848
   LINK 0;
   [--SP] = (R7:7, P5:5);
   SP += -12;
   [FP + 8] = R0;
// line 3851
   P1.L = _io_registers+514;
   P1.H = _io_registers+514;
   R1 = W[P1] (Z);
   R1 = R0 | R1;
   W[P1] = R1.L;
// line 3853
   P1.L = _io_registers+512;
   P1.H = _io_registers+512;
   R1 = W[P1] (Z);
   R0 = R0 & R1;
   CC = R0 == 0;
   if CC jump .P57L2 ;

.P57L5:
   P1.L = _io_registers+520;
   P1.H = _io_registers+520;
   NOP;                                    // Inserted 2 instrs to fix anomaly w05_00_0245_with_boundaries.
   NOP;
   R0 = W[P1] (Z);
   CC = R0 == 0;
   if CC jump .P57L2 ;

.P57L4:
   P5.L = .epcdata+8;
   P5.H = .epcdata+8;
   NOP;                                    // Inserted 2 instrs to fix anomaly w05_00_0245_with_boundaries.
   NOP;
   P1 = [P5];
   R0 = [P1 + 80];
   CC = BITTST(R0, 7);
   if CC jump .P57L2 ;

.P57L1:
// line 3856
   P0.L = _bios_read_protect;
   P0.H = _bios_read_protect;
   R0 = -16382 /* -446775294 */;
   R0.H = -6818 /* -446775294 */;
   [P0] = R0;
// line 3859
   R0 = [P1 + 60];
   R0 += 4;
   P0.L = _reg_mode+52;
   P0.H = _reg_mode+52;
   [P0] = R0;
// line 3860
   R0 = [P1 + 80];
   P0.L = _spsr+4;
   P0.H = _spsr+4;
   [P0] = R0;
// line 3861
   R0 = 210;
   [P1 + 80] = R0;
// line 3862
   P1 = [P5];
   R0 = 24;
   [P1 + 60] = R0;
// line 3864
   CALL.X (_bios_region_read_allow);
// line 3866
   R7 = 1;
   R0 = 1;
   CALL.X (_set_cpu_mode);
// line 3867
   P1 = [P5];
   R0 = 0;
   [P1 + 120] = R0;
// line 3868
   P1 = [P5];
   [P1 + 124] = R7;
// line 3869
   jump .P57L3;

.P57L2:

.P57L3:
// line 3870
   SP += 12;
   (R7:7, P5:5) = [SP++];
   UNLINK;
   RTS;


Обратите внимание на комментарии, которые написал ассемблер.

Так что идею написания динамического рекомпилятора я похоронил :agressive:

P.S. прикрепил сюда исходный сишный файл и его ассемблирование.

Вложения:
cpu.rar [69.22 КБ]
Скачиваний: 464
Автор:  Wind [ 07 окт 2009, 15:41 ]
Заголовок сообщения:  Re: [АРХИВ] Динамическая рекомпиляция
Любой процессор имеет ассемблер и на этом можно закончить разговор.
Страница 1 из 1 Часовой пояс: UTC + 3 часа [ Летнее время ]
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
http://www.phpbb.com/