На основе курса Nand2Tetris и книги The Elements of Computing Systems

У нас есть компьютер, у нас есть ассемблер. Следующий шаг - своя виртуальная машина (VM), которая будет промежуточным звеном между высокоуровневым языком программирования и машинным кодом. Набор инструкций для этой виртуальной машины должен быть достаточно объемным, чтобы было относительно просто выполнить трансляцию с языка высокого уровня в ее команды, и достаточно маленьким, чтобы не было сложно ее команды переводить в ассемблер. Такой подход может облегчить портирование: если процессор поддерживает другой ассемблер, то нам нужно будет портировать не высокоуровневый язык, а ограниченное количество команд. C# и Java придерживаются как раз такого подхода. Виртуальная машина для C# называется Common Language Runtime, а для Java - Java Virtual Machine. Работа нашей виртуальной машины будет основана на стеке.

Память и команды доступа к ней

Адрес начала стека будет лежать прямо в самом начале памяти, в RAM[0] и иметь специальную зарезервированную переменную: SP.

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

  • argument - хранит значения аргументов функции
  • local - хранит локальные переменные функции
  • static - хранит статические переменные
  • constant - псевдо-пространство, «хранит» константы 0..32767
  • this - хранит поля текущего объекта
  • that - хранит значения текущего массива
  • pointer - пространство из двух значений, хранит адреса this и that
  • temp - пространство из 8 значений, может хранить любые данные, которые могут понадобиться другим командам

Доступ к памяти

Для работы со стеком и с дополнительными пространствами будут использоваться следующие команды:

  • pop space index - берет переменную из стека и кладет в пространство space с отступом index.
  • push space index - берет переменную из пространства space с отступом index и кладет в стек.

space - одно из вышеперечисленных пространств.

index - откуда будет взято (или куда положено, в случае pop) значение для основного стека.

Когда будет выполняться pop, значение в SP будет уменьшаться на единицу, при push, соответственно, увеличиваться на единицу.

Расположение в памяти

RAM[0..4] выделены под указатели на стек и виртуальные пространства:

  • RAM[0] - указатель на общий стек, указывает на следующую свободную позицию в стеке. Инициализируется всегда адресом 256. Имеет зарезервированное имя в ассемблере SP
  • RAM[1] - указатель на local. Имеет зарезервированное имя в ассемблере LCL
  • RAM[2] - указатель на argument. Имеет зарезервированное имя в ассемблере ARG
  • RAM[3] - указатель this. Имеет зарезервированное имя в ассемблере THIS
  • RAM[4] - указатель на that. Имеет зарезервированное имя в ассемблере THAT
  • RAM[5..12] - фиксированное пространство, выделено под temp
  • RAM[16..255] - фиксированное пространство, выделенное под static
  • Для pointer не выделено специального пространства, pointer 0 всегда ссылается на THIS, а pointer 1 на THAT. Другого индекса у pointer быть не может.

Стоит обратить внимание, что RAM[0..4] работают как указатели, то есть, если будет вызвано pop local 2, то VM возьмет за базовый адрес значение, на которое ссылается RAM[1] (переменная LCL), а если будет вызвано pop temp 2, то VM возьмет за базовый адрес непосредственно 5, потому что для temp область фиксирована.

Арифметические команды

  • add
  • sub
  • neg
  • eq
  • gt
  • lt
  • and
  • or
  • not

Для арифметических операций мы всегда сначала достаем аргументы из стека, а затем кладем обратно результат вычисления. То есть для add мы сначала сделаем два раза pop, чтобы достать аргументы, а затем push с результатом сложения.

Для логических команд стоит отметить, что для VM -1 представляет TRUE, а 0 - FALSE.

Для большинства арифметических команд есть практически прямое соответствие в языке ассемблера. Команды сравнения можно реализовать с помощью команд условного перехода (JEQ, JLT, JGT и прочие).

Ветвление

Для ветвления будут реализованы следующие команды:

  • label label - поставить метку
  • goto label - перейти к метке
  • if-goto label - перейти к метке, если выполняется условие

Как и для большей части арифметических команд, для команд ветвления есть практически прямое соответствие к командам ассемблера.

Функции

Самый сложный в реализации раздел. Здесь будет 3 команды:

  • function name n - описание функции name, у которой есть n локальных аргументов
  • call name n - вызов функции с n аргументами
  • return - выход из текущего вызова

Общая схема вызова функции

  • Положить n аргументов функции в стек
  • Вызвать функцию с помощью команды call
  • Обновить указатели SP, LCL, ARG для вызванной функции. THIS, THAT, POINTER не определены на момент вызова.
  • Перед завершением вызова вызываемая функция должна положить результат работы функции (он есть всегда) в стек.
  • После завершения вызова вызвавшая функция восстанавливает SP, LCL, ARG, THIS, THAT, POINTER на значения, бывшие перед вызовом функции

function

Самая простая команда из списка, объявление функции. Все, что нужно сделать - создать метку и сбросить в 0 n локальных аргументов

call

Команда создает “фрейм”, в котором будут храниться LCL, ARG, THIS, THAT, SP вызывающей функции, чтобы после работы вызываемой она могла их восстановить, создает метку возврата и подготавливает LCL и ARG для вызываемой функции. Порядок действий будет такой:

  • кладем в стек адрес метки возврата
  • кладем в стек адрес LCL
  • кладем в стек адрес ARG
  • кладем в стек адрес THIS
  • кладем в стек адрес THAT
  • подготавливаем ARG для вызываемой функции, ARG должен указывать на *SP - n (символ * означает переход по адресу, лежащему в SP)
  • подготавливаем LCL для вызываемой функции, LCL должен указывать на *SP
  • безусловный переход по метке функции
  • создание метки возврата

return

Команда делает обратные call действия: восстанавливает указатели памяти для “фрейма” прошлой функции:

  • Положим в переменную R14 начало фрейма функции, из которой происходит возврат (R13-15 не используются HACK ассемблером, поэтому мы можем использовать их как захотим). Начало фрейма совпадает с адресом начала LCL.
  • Положим в переменную R13 адрес возврата (он находится по адресу *(R14-5))
  • Положим в *ARG результат работы функции (он хранится в стеке)
  • Ставим адрес стека в ARG+1 (как описано выше, стек должен указывать на результат работы функции)
  • Восстанавливаем адрес THAT = (R14 - 1)
  • Восстанавливаем адрес THIS = (R14 - 2)
  • Восстанавливаем адрес ARG = (R14 - 3)
  • Восстанавливаем адрес LCL = (R14 - 4)
  • Безусловный переход по метке адреса возврата в R13

Реализация

Один из вариантов реализации можно посмотреть в репозитории: https://github.com/ngrishaev/HackVM