Часть 2. Иллюзорный автомобиль
Jan. 11th, 2010 12:27 am![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
thedeemonЧуть менее, чем все виртуальные машины, которые я встречал и делал, были стековыми или регистровыми. В первом случае у нас есть некий стек значений, в него можно складывать всякие константы, а разные операции берут из него значения, проводят над ними какие-то действия, и результат кладут вместо взятых. При этом большинство команд в байткоде не имеют аргументов, т.к. их аргументы уже лежат на стеке, будучи положены туда другими командами. Соответственно, даже простые действия представляются целой серией операций (положить в стек один аргумент, положить другой, совершить действие...), и все время туда-сюда изменяется stack pointer, в простейшем случае - индекс в массиве. В случае регистровых ВМ у нас есть массив регистров, а у команд есть аргументы, указывающие из каких регистров брать исходные значения и куда сохранять результат операции. Количество операций, необходимых для совершения тех же действий, у регистровой ВМ меньше, но если мы хотим иметь вызовы функций, особенно рекурсивных, то возникают отдельные сложности - нужно или сохранять нужные регистры на стеке, или иметь целый стек регистровых массивов.
Виртуальная машина, которая использовалась у меня до этого момента, и в код которой компилился тот DSEL на Руби, была регистровой, причем вообще без стека. Все функции там инлайнились, а рекурсивные функции не поддерживались. Выделением памяти она тоже не занималась - все необходимые буферы должны были быть выделены вызывающей программой и переданы через регистры. Такие ограничения создавали ряд неудобств, поэтому было решено, что в LeoVM нужен какой-то стек и какое-то управление памятью. В стеке будут аргументы функций. Если из функции А вызывается Б, то локальные переменные А должны пережить этот вызов, значит их тоже стоит хранить в стеке. Что осталось? Временные значения при вычислении сложных выражений. Стек у нас резиновый, почему бы не поместить их туда же. В итоге отдельный набор регистров уже не нужен. Но хочется сохранить хорошую скорость регистровой ВМ, поэтому будем к значениям на стеке относиться как к регистрам: пусть команды берут исходные значения не с верхушки стека, а с произвольных позиций во фрейме, и результат пусть пишут в произвольное место. Каждое значение на стеке будет адресоваться смещением относительно frame pointer'a - специального регистра, хранящего абсолютный адрес некоторого места в стеке. Количество локальных переменных в каждой функции компилятору известно. При компиляции сложных выражений смещения для временных значений тоже можно вычислить заранее. Т.е. тот процесс распределения адресов, который в стековой ВМ происходит динамически путем изменения SP, можно один раз проделать статически при компиляции. При вызове функций мы сохраняем стековую семантику: аргументы кладутся на верхушку стека, а после отработки вызванной функции вместо них на стеке должен быть результат. В LeoVM никакого Stack Pointer'a нет, и "верхушка стека" определяется статически как минимальное смещение от FP, которое больше всех смещений переменных и временных значений. Количество аргументов и возвращаемых значений тоже компилятору известно, поэтому он просто вычисляет "верхушку стека", кладет аргументы туда, и при вызове функции увеличивает Frame Pointer на величину ("верхушка стека" + место для аргументов и результата). Соответственно, команда Call имеет два аргумента - адрес кода функции и величину, на которую нужно увеличить FP (команд прямого изменения FP нету, он меняется только командами Call и Ret). Вызванная функция знает, что аргументы надо искать слева от FP, туда же нужно положить результат, а справа от FP - свободное место для локальных переменных и пр.
Команд в LeoVM изначально было всего 15: арифметика, копирование интов и байтов, вызов/возврат, выделение памяти, условные и безусловный переходы. Арифметические команды трехадресные - имеют три аргумента: два источника и результат. У других команд может быть меньше источников, или нет результата, зато есть адрес кода для перехода или вызова. Каждый источник и результат задается числом, а у команд есть модификаторы, которые говорят как это число понимать - как регистр с заданным смещением от FP, как значение, на которое такой регистр указывает, или как просто число. Команды условного перехода имеют два аргумента-источника и адрес. Они сравнивают аргументы, и если условие выполнено, то управление переходит по указанному адресу.
Про память.
В программах, которые будут писаться для LeoVM, динамическое выделение памяти нужно довольно редко и в основном для выделения временных краткоживущих буферов для расшифрованных строк и посчитанных матриц. Делать ручное освобождение или сложный механизм отслеживания мусора не хотелось, поэтому была реализована очень простая схема. В набор команд вошла команда New с аргументом-назначением, получающим адрес выделенной памяти, и аргументом-источником, задающим требуемый размер. У ВМ есть большой заранее выделенный кусок памяти, от которого просто отщипывается очередная часть, и указатель на свободную зону (HP - Heap Pointer) смещается. Когда командой Call вызывается какая-нибудь функция, этот указатель, вместе с Frame Pointer и Instruction Pointer сохраняется в отдельном стеке контекстов (в стек данных они не пишутся, чтобы нельзя было испортить), а при возврате по команде Ret они все восстанавливаются, таким образом, вся выделенная внутри функции динамическая память автоматически освобождается одним махом. При этом компилятор гарантирует, что указатели на нее не будут переданы из функции наверх. Спросите, как же работал map из первого примера? Об этом позже, но краткий ответ: без Call'ов.
Оптимизация.
Когда работающий вариант ВМ был получен и проверен, я стал снизу-вверх строить компилятор, постепенно повышая уровень конструкций, о чем будет рассказано в других частях. Когда компилятор был готов, пришло время заняться оптимизацией. Для этого команды ВМ были разделены на комбинации более мелких команд, реализующих элементарные действия. Например, команда ADD Dest Src1 Src2 была представлена последовательностью из четырех команды: LOAD Src2, LOAD Dest, LOAD Src1, ADD. Получилась новая МикроВМ с той же семантикой, но другим набором инструкций, более атомарным. Компилятор был модифицирован на выдачу кода этой МикроВМ. После этого в МикроВМ была добавлена запись трасс: во время исполнения программы каждая исполняемая команда записывалась в трассу в виде одного символа. На более-менее типичной программе была получена трасса - файл размером около 100 мегабайт. После этого был написан специальный компрессор: он считал число вхождений каждой пары подряд идущих символов, брал самую часто встречающуюся пару и заменял ее на новый символ. Т.е. определялось, какие действия чаще всего идут подряд, чтобы можно было их объединить в одну команду. После каждой такой итерации размер трассы сокращался, и после примерно 20 итераций он сократился в 10 раз. Дальше полученные супер-команды были проанализированы, и стало ясно, какие комбинации стоит сделать отдельными командами ВМ. Например, оказалось, что в командах условного перехода чаще всего сравниваются регистры. А из арифметики чаще всего используется сложение, причем либо с только регистровыми операндами, либо с регистрами и константой. И еще, что тоже логично, часто встречается увеличение регистра на 1 или 4 (размер инта). В итоге к первоначальному набору из 15 команд были добавлены еще 7, являющиеся частными случаями предыдущих команд, когда жестко заданы модификаторы и/или значения. Так, например, появились команды INC и INC4. Частота появления этих новоиспеченных инструкций весьма велика, а поскольку при их исполнении не нужно разбирать модификаторы аргументов и ветвиться по ним, то скорость исполнения заметно возрастает. Такая оптимизация (плюс перенос разбора модификаторов из главного цикла внутрь веток отдельных команд) увеличила скорость работы в 2 раза по сравнению с оригинальной LeoVM.
Дальше уже в новую ВМ была добавлена запись трассы и был проведен аналогичный анализ. Он показал, что очень часто за безусловным переходом сразу идет сравнение и условный переход. Это было вызвано устройством циклов, которые компилировались так:
Т.е. из конца цикла делался прыжок на условие, вот и получалась такая частая комбинация. Но ее можно сократить, если компилировать циклы иначе:
Так у нас цикл на одну инструкцию короче - нет безусловного перехода. Эта оптимизация дала около 5%, т.к. безусловный переход был довольно простой командой, и много времени на него не уходило.
Сама ВМ сделана как простой цикл
Дальше: Часть 3. Первые шаги
Виртуальная машина, которая использовалась у меня до этого момента, и в код которой компилился тот DSEL на Руби, была регистровой, причем вообще без стека. Все функции там инлайнились, а рекурсивные функции не поддерживались. Выделением памяти она тоже не занималась - все необходимые буферы должны были быть выделены вызывающей программой и переданы через регистры. Такие ограничения создавали ряд неудобств, поэтому было решено, что в LeoVM нужен какой-то стек и какое-то управление памятью. В стеке будут аргументы функций. Если из функции А вызывается Б, то локальные переменные А должны пережить этот вызов, значит их тоже стоит хранить в стеке. Что осталось? Временные значения при вычислении сложных выражений. Стек у нас резиновый, почему бы не поместить их туда же. В итоге отдельный набор регистров уже не нужен. Но хочется сохранить хорошую скорость регистровой ВМ, поэтому будем к значениям на стеке относиться как к регистрам: пусть команды берут исходные значения не с верхушки стека, а с произвольных позиций во фрейме, и результат пусть пишут в произвольное место. Каждое значение на стеке будет адресоваться смещением относительно frame pointer'a - специального регистра, хранящего абсолютный адрес некоторого места в стеке. Количество локальных переменных в каждой функции компилятору известно. При компиляции сложных выражений смещения для временных значений тоже можно вычислить заранее. Т.е. тот процесс распределения адресов, который в стековой ВМ происходит динамически путем изменения SP, можно один раз проделать статически при компиляции. При вызове функций мы сохраняем стековую семантику: аргументы кладутся на верхушку стека, а после отработки вызванной функции вместо них на стеке должен быть результат. В LeoVM никакого Stack Pointer'a нет, и "верхушка стека" определяется статически как минимальное смещение от FP, которое больше всех смещений переменных и временных значений. Количество аргументов и возвращаемых значений тоже компилятору известно, поэтому он просто вычисляет "верхушку стека", кладет аргументы туда, и при вызове функции увеличивает Frame Pointer на величину ("верхушка стека" + место для аргументов и результата). Соответственно, команда Call имеет два аргумента - адрес кода функции и величину, на которую нужно увеличить FP (команд прямого изменения FP нету, он меняется только командами Call и Ret). Вызванная функция знает, что аргументы надо искать слева от FP, туда же нужно положить результат, а справа от FP - свободное место для локальных переменных и пр.
Команд в LeoVM изначально было всего 15: арифметика, копирование интов и байтов, вызов/возврат, выделение памяти, условные и безусловный переходы. Арифметические команды трехадресные - имеют три аргумента: два источника и результат. У других команд может быть меньше источников, или нет результата, зато есть адрес кода для перехода или вызова. Каждый источник и результат задается числом, а у команд есть модификаторы, которые говорят как это число понимать - как регистр с заданным смещением от FP, как значение, на которое такой регистр указывает, или как просто число. Команды условного перехода имеют два аргумента-источника и адрес. Они сравнивают аргументы, и если условие выполнено, то управление переходит по указанному адресу.
Про память.
В программах, которые будут писаться для LeoVM, динамическое выделение памяти нужно довольно редко и в основном для выделения временных краткоживущих буферов для расшифрованных строк и посчитанных матриц. Делать ручное освобождение или сложный механизм отслеживания мусора не хотелось, поэтому была реализована очень простая схема. В набор команд вошла команда New с аргументом-назначением, получающим адрес выделенной памяти, и аргументом-источником, задающим требуемый размер. У ВМ есть большой заранее выделенный кусок памяти, от которого просто отщипывается очередная часть, и указатель на свободную зону (HP - Heap Pointer) смещается. Когда командой Call вызывается какая-нибудь функция, этот указатель, вместе с Frame Pointer и Instruction Pointer сохраняется в отдельном стеке контекстов (в стек данных они не пишутся, чтобы нельзя было испортить), а при возврате по команде Ret они все восстанавливаются, таким образом, вся выделенная внутри функции динамическая память автоматически освобождается одним махом. При этом компилятор гарантирует, что указатели на нее не будут переданы из функции наверх. Спросите, как же работал map из первого примера? Об этом позже, но краткий ответ: без Call'ов.
Оптимизация.
Когда работающий вариант ВМ был получен и проверен, я стал снизу-вверх строить компилятор, постепенно повышая уровень конструкций, о чем будет рассказано в других частях. Когда компилятор был готов, пришло время заняться оптимизацией. Для этого команды ВМ были разделены на комбинации более мелких команд, реализующих элементарные действия. Например, команда ADD Dest Src1 Src2 была представлена последовательностью из четырех команды: LOAD Src2, LOAD Dest, LOAD Src1, ADD. Получилась новая МикроВМ с той же семантикой, но другим набором инструкций, более атомарным. Компилятор был модифицирован на выдачу кода этой МикроВМ. После этого в МикроВМ была добавлена запись трасс: во время исполнения программы каждая исполняемая команда записывалась в трассу в виде одного символа. На более-менее типичной программе была получена трасса - файл размером около 100 мегабайт. После этого был написан специальный компрессор: он считал число вхождений каждой пары подряд идущих символов, брал самую часто встречающуюся пару и заменял ее на новый символ. Т.е. определялось, какие действия чаще всего идут подряд, чтобы можно было их объединить в одну команду. После каждой такой итерации размер трассы сокращался, и после примерно 20 итераций он сократился в 10 раз. Дальше полученные супер-команды были проанализированы, и стало ясно, какие комбинации стоит сделать отдельными командами ВМ. Например, оказалось, что в командах условного перехода чаще всего сравниваются регистры. А из арифметики чаще всего используется сложение, причем либо с только регистровыми операндами, либо с регистрами и константой. И еще, что тоже логично, часто встречается увеличение регистра на 1 или 4 (размер инта). В итоге к первоначальному набору из 15 команд были добавлены еще 7, являющиеся частными случаями предыдущих команд, когда жестко заданы модификаторы и/или значения. Так, например, появились команды INC и INC4. Частота появления этих новоиспеченных инструкций весьма велика, а поскольку при их исполнении не нужно разбирать модификаторы аргументов и ветвиться по ним, то скорость исполнения заметно возрастает. Такая оптимизация (плюс перенос разбора модификаторов из главного цикла внутрь веток отдельных команд) увеличила скорость работы в 2 раза по сравнению с оригинальной LeoVM.
Дальше уже в новую ВМ была добавлена запись трассы и был проведен аналогичный анализ. Он показал, что очень часто за безусловным переходом сразу идет сравнение и условный переход. Это было вызвано устройством циклов, которые компилировались так:
while (condition) { body } превращался в
Label:
if (condition) {
body;
goto Label;
}Т.е. из конца цикла делался прыжок на условие, вот и получалась такая частая комбинация. Но ее можно сократить, если компилировать циклы иначе:
goto Cond_Label; Body_Label: body; Cond_Label: if (condition) goto Body_Label;
Так у нас цикл на одну инструкцию короче - нет безусловного перехода. Эта оптимизация дала около 5%, т.к. безусловный переход был довольно простой командой, и много времени на него не уходило.
Сама ВМ сделана как простой цикл
while(ip < codelen) { switch(code[ip] & CMD_MASK) { ... т.е. без всякого шитого кода и computed gotos. Что занятно, интеловский компилятор 7.1 ее компилирует в менее эффективный код, чем MSVC6.Дальше: Часть 3. Первые шаги
