Разработка компилятора. Стековая виртуальная машина. Основы

Виртуальная машина, как некоторая идеализированная имитация процессора, является достаточно интересной темой для изучения. Стековая виртуальная машина проше для понимания процесса исполнения байт-кода.

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

В данной статье рассмотрим понятие виртуальной машины, ее функционал и возможности.

Теоретические основы виртуальной машины

Виртуальная машина (VM — virtual machine) — программное абстрактное представление центрального процессора. На вход виртуальная машина принимает байт-код для исполнения.

Байт-код (bytecode) — команды, несущие в себе определенный смысл, исполняемые определенной виртуальной машиной. Такая команда может быть представлена константой типа:

/*! команды виртуальной машины */
enum S4G_VM_COMMAND
{
	S4G_VM_COMMAND_FETCH,		//!< положить на вершину стека значение переменной, имя переменной берется из аргумента, поиск осуществляется во всех доступных контекстах
	S4G_VM_COMMAND_FETCH_IDX,	//!< ложит на вершину стека переменную из контекста, из аргумента извлеваются: номер контекста относительно верха ((UINT)arg) &amp; 0xFFFF, порядковый номер переменной в контексте (((UINT)arg) &amp; 0xFFFF) &gt;&gt; 16
	S4G_VM_COMMAND_ACCESS,		//!< получить значение из объекта (таблица, массив, объект класса, строка), который должен содержать другие переменные
	S4G_VM_COMMAND_STORE,		//!< сохранить в переменной -2 значение из -1, затем -1 выталкивает
	S4G_VM_COMMAND_PUSH,		//!< положить на вершину стека
	S4G_VM_COMMAND_POP,			//!< удалить значение с вершины стека
};

В s4g мы не стали ограничиваться только одним лишь числом, добавили еще аргумент в виде переменной и еще некоторые данные:

//! сформированная команда, готовая к выполнению, возможно содержит аргумент и дополнительную переменную
struct s4g_Command
{
	S4G_VM_COMMAND m_Command;	//!< команда виртуальной машины
	s4g_Variable* m_pArg;		//!< аргумент для команды (может быть NULL)
	ID m_numFile;				//!< номер файла с кодом
	ID m_numStr;				//!< номер строки с кодом которая сгенерировала данную команду
	int m_iExtraData;			//!< дополнительные переменная
};

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

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

Во-вторых удобно использовать аргумент. В аргументе можно задать все что угодно, и интерпретировать его можно по разному, у нас для некоторых команд m_pArg это (long)m_pArg. Это используется для того, чтобы не генерировать лишние команды (положить на стек строку, к примеру).

В-третьих есть такие команды, исполнение которых требует дополнительной информации от нее, этим может быть как m_pArg, а в некоторых случаях и m_iExtraData (как в случае с :[]).

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

Запуск виртуальной машины происходит при вызове функции запуска, и исполняет она переданный ей код, после чего исполнение останавливается (завершается функция запуска).

Теоретические основы стековой виртуальной машины

Стековая виртуальная машина имеет в своей основе стек исполнения.

Стек (stack) — это тип данных состоящий из элементов и работающий по принципу LIFO  (last in — first out) «последним пришёл — первым вышел». Иными словами это стопка данных, и первый элемент положенный в эту стопку возможно взять только тогда когда все элементы сверху убраны, а тот элемент который положен сверху будет убран первый.

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

Стек исполнения — это стек который служит местом хранения текущих данных исполнения.

В большинстве случаев стековые виртуальные машины работают по принципу обратной польской нотации, то есть выражение вида 10 + 5 стековая виртуальная машина исполнит:

push 10
push 5
add

что эквивалентно 10 5 +

Обратная польская нотация (по другому запись) — это форма записи математических и логических операций, при которой операнды расположены перед знаком операции.

Выражение типа 10 + 5 называется инфиксным.

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


В s4g 0.9.0 виртуальная машина имела чрезвычайно ужасный вид, мы боролись за производительность не обращая внимания на тот километровый код который невозможно было читать, в 0.9.1 мы все-таки причесали код, но он все также был некрасивым и непонятным, но как нам казалось быстрым. Но это плохо. Когда после полугода мы опять взялись за доработку языка … с трудом получилось понять что же там в машине происходит … после этого мы однозначно решили, такая производительность нам не нужна, ибо разработка машины замедляется. И как оказалось, в производительности то мы ничего и не потеряли, зато приобрели достаточно понятный код))

Поделиться:

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

*

*

code