Стек машина для вычислений содержит
Стек машина для вычислений содержит
Машинный код (байткод) всегда предназначен для исполнения каким-либо процессором, физическим либо виртуальным. Процессоры (машины) могут быть стековыми либо регистровыми:
В стековом байткоде виртуальной машины инструкции короче, а сам подход позволяет написать компилятор значительно легче. Регистровый позволяет проводить операции с памятью намного эффективнее, особенно с учётом современных процессоров, которые практически всегда являются регистровыми с программным стеком в оперативной памяти (более медленной, чем регистры).
Дерево выражений
После явной расстановки скобок можно нарисовать эквивалентное дерево, при обходе которого слева направо вычисления будут выполнены корректно.
В BNF нотации простейшая грамматика выражений выглядит так:
Трансляция дерева в инструкции стековой машины
Если у вас есть построенное дерево выражения, вы можете выполнить трансляцию с помощью обхода дерева слева направо в глубину:
Если теперь выполнить инструкции, то на стеке останется одно число — результат арифметической операции
Трансляция дерева в инструкции регистровой машины
Мы покажем способ на примере ассемблера виртуальной регистровой машины LLVM-IR, в котором можно использовать сколько угодно регистров — для этого нужно просто связывать каждое значение с новым имененем, а в остальном использовать те же самые принципы, что и для стековой (более того, в реализации кодогенератора вам наверняка пригодится структура данных “стек” либо рекурсия):
Если число регистров в процессоре ограничено, то придётся распределять свободные регистры по выражениям (хотя проще воспользоваться стековым методом). Хороший алгоритм распределения регистров выходит за рамки этой статьи, но в грубом виде он мог бы выглядеть так: у вас есть набор реальных регистров, имена которых служат ключом в ассоциативном массиве (например, в std::unordered_map ), а значение — это указатель на объект Value, временно занимающий регистр (например, shared_ptr ). Этот ассоциативный массив используется для учёта занятых регистров. Если регистры кончились, вы можете выдавить несколько значений на стек (добавив в промежуточный код соответствующие команды копирования), а освободившиеся регистры использовать.
Стек машина для вычислений содержит
Многостековые 0-операндные машины
Многостековые 0-операндные машины имеют ряд преимуществ перед иными архитектурами: 0-операндная адресация ведёт к малому размеру инструкции, несколько стеков позволяют одновременно использовать вызовы подпрограмм и манипулировать стеком данных. Это приводит к малому размеру программ и малой сложности системы.
Локальность обращений стеку даёт возможность уменьшить траффик «стек-память» на большинстве задач управления. Простота построения системы позволяет уменьшить время проектирования микросхем. Применение стековой модели позволяет уменьшить время обработки прерываний, так как не требуется сохранение контекста.
По сравнению с CISC-процессорами уменьшено время вызова подпрограмм, поэтому вызов даже маленького фрагмента кода является лучшей альтернативой, чем подстановка этого фрагмента без вызова.
Типичная стековая архитектура.
Рассмотрим архитектуру канонической стековой машины.
На рис. 1 показана структурная схема стековой машины. Основными компонентами являются: шина данных, стек данных (DS), стек возвратов (RS), арифметико-логическое устройство (ALU) с регистром вершины стека (TOS), счётчик инструкций (PC), память с регистром адреса памяти (MAR), логика управления с регистром инструкции (IR), и секция ввода/вывода (I/O).
Рис. 1. Каноническая стековая машина.
Для упрощения конструкции стековая машина имеет одну шину, соединяющую ресурсы системы. Реальные процессоры имеют более одной шины для параллеьной выборки данных и выполнения вычислений. В канонической стековой машине (КСМ) на шине может находится только один передающий блок, и только один принимающий блок в течении цикла.
АЛУ и регистр вершины стека
АЛУ поддерживает стандартные операции, используемые любой ЭВМ, как минимум сложение, вычитание, логические функции и тестирование на 0. Арифметика может быть целочисленной или плавающей.
Счётчик инструкций хранит адрес следующей выполняемой инструкции. Счётчик может быть загружен с шины данных для реализации переходов, или может быть инкрементирован для выборки следующей по порядку инструкции.
Блок содержит регситр адреса памяти (MAR) и некоторый объём памяти. Для доступа в память в MAR записывается адрес, откуда/куда будет производится чтение/запись. В следующий цикл память будет прочитана или записана (с помощью шины данных).
Некоторое устройство, «черный ящик», которое позволяет вести информационный обмен с внешними устройствами.
Таблица 1. Набор инструкций канонической стековой машины.
Обратная польская нотация
Стековые машины обрабатывают данные, «используя» постфиксную нотацию:
98 12 45 + * (эквивалентно (12+45)*98)
Каноническая стековая машина разработана для прямого исполнения обратной польской нотации (в компиляторе исчезает фаза распределения регистров).
При работе в режиме реального времени важно, каким образом обрабатываются прерывания. Обычно в этом случае необходимо сохранение контекста задачи. В данном случае контекст задачи сохранять вряд ли необходимо, исходяд из свойства стека.
Единственной неприятностью является переполнение стека, которое может возникать в случае вложенных прерываний. В ряде случаев возможно копированиечасти стека в основную память, или же это копирование вообще происходит автоматически.
Однако, идеи стековых машин очень популярны. На базе виртуальной стековой архитектуры построены виртуfльные машины Java и C#. В Беларуси выпускался стековый процессор-контроллер серии Дофин, 7 моделей, разрядность 16 и 32 бит, пригодный для задач цифовой обработки сигналов, за один такт он мог выполнить до 6 стандартных операций стековой машины. Сейчас выпускаются 4-битные стековые микроконтроллеры серии MARC фирмы Atmel.
Разработка стековой виртуальной машины и компилятора под неё (часть I)
В универе преподаватели, молодость которых приходилась на 70-80е годы, до объектно-ориентированного программирования убивались по теме разработке собственных языков (интерпретаторов, компиляторов) под предметные области. Всё это казалось невостребованным «старьём», но появление новых языков за последнее десятилетие (Go, Kotlin и множества других) повысили мой интерес к этой теме.
Решил в качестве хобби написать 32-bit стековую виртуальную машину и компилятор C подобного языка под неё, чтобы восстановить базовые навыки. Такая классическая Computer Science задачка для заполнения вечеров с пивом. Как предприниматель, я четко понимаю, что она никому не нужна, но такая практика нужна мне для эстетического инженерного удовольствия. Плюс когда об этом рассказываешь сам понимаешь глубже. С целью и мотивами определился. Начнём.
Так как это виртуальная машина, мне нужно определиться с её характеристиками:
CPU: 32-bitный набор команд, так как машина стековая, в основном операнды команд храним в стеке, из регистров только IP (Instruction Pointer) и SP (Stack Pointer), пока работаем с целыми числами со знаком (__int32), позже добавим остальные типы данных.
RAM: пусть памяти пока будет 65536 ячеек по 32-bit`а. Которую организуем просто. С нижних адресов в верх будут идти код (code/text) и данные (data, heap), а с верхних адресов вниз будет расти стек (stack). Дёшево и сердито.
Предусмотрим вот такие операции:
Пока первые 8 из 32 бит будут под команду (opcode), 1 бит зарезервируем под тип операнда (immediate или из стека), 3 бита под будущие типы данных (byte, short, int, long, char, float, double и что нибудь ещё), а остальные биты для чего нибудь применим. Пока не знаю.
В классе виртуальной машине сделаем такие методы, чтобы загружать исполняемый образ в память виртуальной машины (loadImage), запускать исполнение (run), позволять снаружи читать/писать память (readWord, writeWord), читать состояние регистров IP, SP. Из приватных методов сделаем вывод состояния машины printState (распечатка регистров и содержания стека), а также метод для системных вызовов systemCall, чтобы код виртуальной машины мог вызывать что-то снаружи (сделаем проброс какого-нибудь API).
В итоге получаем простенькую машину, которая умеет в арифметические и битовые операции, управлять ходом исполнения с условными переходами, вызывать функции (пока четкой конвенции по передачи аргументов через стек нет, но дальше доделаем).
Еще нам потребуется реализовать класс с помощью которого мы будем готовить исполняемый образ. Прикрутим к нему простые методы, которые будут записывать команды и данные, чтобы потом можно было этот образ «скормить» виртуальной машине.
И теперь можно попробовать сделать простенькую программу с циклом и вызовом функции, которая печатает «Hello, world from VM!» 10 раз, чтобы проверить, что виртуальная машина более менее работает. На ассемблере виртуальной машины (мнемоники пока будут очень условные, синтаксис до конца не придумал) это программа будет выглядеть примерно так:
Сейчас лень писать под эту задачу транслятор для ассемблера виртуальной машины, потому что делаем высокоуровневый язык, который будем сходу компилировать в команды виртуальной машины. Но чтобы это записать в исполняемый виртуальной машиной образ воспользуемся классом VMImage:
А затем запустим исполнение нашего образа на виртуальной машине, замерив время:
Получаем в консоли:
Ура! Классно! Работают операции со стеком, арифметика, команды условных переходов и вызов функций! Это воодушевляет. Видимо дальше буду развивать эту историю.
Пишем интерпретатор скрипта и стековую машину
Краткая предыстория
Господа, я раскрою вам страшную тайну. Я знаю, что признаться в таком грехе — очень стыдно, но тем не менее, признаюсь. Я — один-эсник. Да-да-да, я пишу большие и малые решения с помощью желтого фреймворка и совесть меня не мучает))).
Помимо 1С я знаю и другие языки, но я молодой, могу себе позволить. Мой знакомый, которого я упомянул во введении — наоборот — военный отставник, хороший инженер-электронщик, переучился в программисты, когда вышел на гражданку. Для грамотного технаря такая переквалификация — несложное дело, платят в сфере 1С неплохо, а хорошим спецам — так и вовсе хорошо. Однако, с возрастом все труднее становится гнаться за новыми технологиями, все сложнее следить за стремительно меняющимся миром IT. Когда состоялся упомянутый разговор, он сказал что-то вроде: «Да это долго, новый язык учить, вот если бы такой скрипт на 1С можно было написать, но чтоб в консоли выполнялся…» Тогда-то я и вспомнил свою старую идею с написанием интерпретатора, которая теперь из чисто исследовательской получала вполне прикладную направленность — выполнение скриптов, работающих с инфраструктурой WSH, но на языке 1С.
Немного о языке программирования
Про язык 1С говорят, что это Visual Basic, переведенный промтом. Это действительно так. По духу язык очень близок к VB — в нем нестрогая типизация, нет ООП, лямбда-выражений и замыканий. В нем «словесный», а не «сишный» синтаксис. Кроме того, поскольку все ключевые слова имеют английские аналоги, то код 1С, написанный в английских терминах отличить с первого взгляда от VB почти невозможно. Разве что символ комментария — две косые черты, а не апостроф, как в бейсике.
Язык различает процедуры и функции, имеет классические циклы «For» и «While», а также итераторный цикл «For Each … In». Обращение к свойствам и методам объектов выполняется «через точку», обращение к массивам — в квадратных скобках. Каждый оператор завершается точкой с запятой.
Что такое «стековая машина» и как она работает
Каждая инструкция представляет собой однобайтовый код операции от 0 до 255, за которым следуют такие параметры, как регистры или адреса памяти (википедия).
В нашей машине команда будет иметь фиксированную длину и состоять из двух чисел — кода операции и аргумента операции. Каждая команда подразумевает набор действий над данными в стеке.
Например, псевдокод операции сложения «1+2» может выглядеть следующим образом:
Первые две команды кладут в стек слагаемые, третья команда выполняет сложение и кладет результат в стек. В таком случае, операция присваивания «A = 1 + 2» может выглядеть так:
Видно, что команды Push и LoadVar имеют аргумент, команда Add в аргументе не нуждается.
Преимущество стековых вычислений в том, что операции выполняются в порядке их следования, не нужно обращать внимание на приоритеты операций. Что написано, то и выполняется. Перед выполнением операции ее операнды заталкиваются в стек. Такой способ описания выражений получил название «обратной польской записи»
Задача написания стековой машины сводится к «изобретению» необходимого набора команд, которые эта машина будет понимать.
Устройство компилятора
Синтаксический анализатор проверяет, что набор лексем, которые дал ему лексический анализатор является осмысленным, что перед нами программа, а не бессмысленный набор букв.
Анализатор строит абстрактное синтаксическое дерево (AST), которое затем подается на вход генератора кода.
Генератор кода создает байт-код, обходя узлы синтаксического дерева.
Я начал писать компилятор по такой же трехзвенной схеме, но потом мне это показалось излишне правильным и в рамках данной задачи — ненужным. Поэтому, я отказался от AST и объединил синтаксический анализ с генерацией кода.
Компилятор в цикле запрашивает у парсера очередную лексему и, глядя на нее, генерирует код. Попутно проверяет, что лексема является разрешенной в данном контексте. AST в этой схеме оказывается лишним.
Конечный автомат
Устройство виртуальной машины
Контексты видимости
Все переменные и методы всегда принадлежат к какому-либо контексту. Существует глобальный контекст, контекст модуля и локальный контекст внутри метода. Получается стек доступных (видимых) имен, к которому можно обращаться при выполнении. С этим стеком идет активная работа в момент компиляции и выполнения.
Более того, если развить идею и предположить, что можно создавать экземпляры контекстов, то естественным образом возникает модульность. Если у нас есть некий модуль, как набор методов и переменных, то мы имеем контекст, в котором весь код этого модуля работает. Теперь, если мы создадим два экземпляра одного и того же модуля, то фактически мы создадим два экземпляра одного класса. Каждый из них будет видеть свой собственный контекст и иметь собственное состояние.
Документация 1С этого прямо не говорит, но наблюдаемое поведение позволяет сделать вывод, что выполнение модулей в исполняющей среде 1С работает именно таким образом. Исполняющая среда работает не с экземплярами объектов, а с контекстами, которые «присоединяются» к виртуальной машине по мере необходимости.
Память
Условная «память» машины представляет собой список подключенных к ней контекстов. Каждый контекст имеет свой номер и состояние (конкретные значения переменных). Команды чтения/записи переменных имеют аргумент в виде номера ячейки в таблице контекстов. Каждая запись в таблице описывает номер контекста и номер переменной в этом контексте, над которой выполняется действие.
| Индекс | Номер контекста | Номер переменной |
|---|---|---|
| 0 | 0 | 0 |
| 1 | 0 | 1 |
| 2 | 1 | 3 |
Например, если поступила команда PushVar 1, то в таблице по индексу 1 выбирается запись, в которой сказано — взять из контекста 0 переменную номер 1.
Переменные — это простой массив, который каждый подключенный контекст сообщает машине. Машина пишет и читает данные из этого массива, изменяя таким образом состояние подключенных контекстов. При этом неважно, что за контекст подключен — экземпляр какого-то класса или глобальный контекст. Машина умеет менять переменные, а что за переменные — не имеет значения.
Стек вызовов
Выполнение кода организовано с помощью так называемых «кадров», каждый из которых представляет собой набор локальных переменных и указатель на текущую инструкцию. При вызове какого-либо метода текущий кадр помещается в стек. Таким образом сохраняется состояние машины на момент вызова.
Затем формируется новый кадр с пустым массивом локальных переменных и номером инструкции, равным началу вызываемого метода. Этот новый кадр становится текущим и цикл выполнения команд продолжается уже с него.
По достижении команды Return текущий кадр уничтожается (вместе со значениями локальных переменных, которые вышли из области видимости), из стека вызовов извлекается сохраненный кадр с предыдущим состоянием и цикл исполнения команд продолжается с точки вызова.
Фрагмент псевдокода с вызовом метода.
Предположим, что текущая инструкция имеет номер 6. Это вызов по адресу 0. Локальные переменные и номер текущей инструкции сохраняются в стеке вызовов. Далее, управление передается по адресу 0, а затем возвращается на адрес 6, где происходит переход далее, на очередную инструкцию.
Реализация команд
Устройство исполняемого модуля
Константы
Переменные
Методы
Методы разделяются на процедуры и функции. Последние могут возвращать значения. По умолчанию параметры в методы передаются по ссылке. Для передачи по значению параметр метода должен быть обозначен ключевым словом «Знач» (аналог ByVal в Бейсике).
В скомпилированном модуле содержится информация о параметрах метода, их обязательности, наличии возвращаемых значений и т.п. Каждый метод имеет свой номер. Кроме того, для каждого метода указывается количество локальных переменных этого метода.
Методы, как и переменные могут быть внешними, по отношению к модулю (т.е. объявленными где-то глобально). Обращение к методам организовано так же, как и в переменных — через таблицу соответствия, определяющую контекст, в котором находится вызываемый метод.
Конечная структура модуля
Работа со значениями
Интерфейс позволяет выяснить действительный тип значения, а также выполнить приведение к базовым типам. Такое приведение необходимо, например, для выполнения арифметических операций. Класс, реализующий конкретный тип значения сам пробует выполнить приведение своего значения к каждому из базовых типов.
При вычислении выражения тип конечного результата определяется по типу первого операнда. Так, выражение «12345» + 10 должно выдать строковый результат. При выполнении сложения второй аргумент будет приведен к строке и выполнена конкатенация.
Напротив, операция 10 + «12345» выполнит попытку приведения строки «12345» к числу. Если это приведение будет невозможным — возникает исключение «ошибка приведения к типу Число».
В приведенных примерах у класса, реализующего тип «Число» вызывается метод AsString(), а у класса, реализующего тип «Строка» — метод AsNumber().
Доступ к свойствам и методам объектов
Каждый объект может иметь свойства и методы, к которым можно обратиться «через точку». Обращение выполняется по имени. Механика обращения по имени представлена специальным интерфейсом, который позволяет выяснять наличие у объекта нужных членов и обращение к ним.
При обращении к свойству или методу у объекта запрашивается номер этого свойства/метода. Далее по этому номеру выполняется запрос о доступности чтения и записи свойства, количеству параметров метода, наличию возвращаемого значения и т.д. После выяснения этой информации выполняется вызов.
Для свойств это установка или чтение значения. Для методов — вызов как процедуры или вызов как функции. В последнем случае возвращенное значение кладется в стек виртуальной машины.
Работа с объектами как с контекстами и наоборот
Выше я упомянул о модульности и о создании объектов, как экземпляров контекстов. Давайте рассмотрим подробнее, что имелось в виду и как организовано обращение к объектам «через точку».
Представьте, что у нас есть некая библиотека функций. Мы можем вызывать функции из этой библиотеки и наслаждаться результатом. А теперь представьте, что библиотека — это экземпляр класса, с набором публичных методов и свойств. Этот экземпляр незаметно «встроен» в нашу область видимости так, что мы вызываем методы экземпляра напрямую, как если бы это были глобальные функции.
Если экземпляр класса » MathLibrary » подключить в стек областей видимости, то функции Sin, Cos и Sqrt можно вызывать прямым обращением. Они будут видны, как обычные методы, объявленные где-то на уровне библиотек.
А теперь сделаем обратную операцию. Если мы написали какой-то скрипт, то он сам по себе является контекстом. Он предоставляет область видимости в которой работает код. А что, если мы создадим экземпляр этого скрипта и запишем его в переменную? Получится, что наш скрипт является классом, со своими свойствами и методами и с ним можно работать, как с объектом. На этом принципе построена возможность подключать (импортировать) внешние файлы скриптов, и работать с ними, как с объектами — создавать экземпляры, вызывать методы и т.п.
При этом когда скрипт А вызывает скрипт Б, то скрипт Б подключается в память машины, как контекст и исполнение кода Б идет, как если бы Б был единственным скриптом. При возврате из модуля Б он отсоединяется и выполнение снова переходит к скрипту А.
Примеры байт-кода
Ниже приведены примеры того, как организовано исполнение некоторых операций в байт-коде.
Что там было про WSH?
Инфраструктура скриптов WSH представлена рядом COM объектов. К этим объектам можно обращаться из скриптовых языков, обращаясь к их членам по имени, с помощью IDispatch. Ничего не напоминает?
Достаточно сделать небольшую обертку над IDispatch, которая позволит машине работать с этими COM-объектами через упомянутый интерфейс IRuntimeContextInstance.
На рисунке представлено окно тестового приложения, которое я использовал для отладки скриптов. В нем выполнен скрипт, перечисляющий метки дисков с помощью объекта Scripting.FileSystemObject 
Конечно, на данный момент полностью все возможности WSH не реализованы и абсолютно полноценной заменой этот движок быть не может. Например, отсутствует возможность создания объектов WSH на удаленных машинах, а если покопать глубже, то и еще найдется много всего. Тем не менее, для большинства локальных задач, как мне кажется, этот движок вполне подойдет.
Исходники и прочее
Весь проект состоит из двух приложений и dll с движком машины.
Приложение TestApp — это вспомогательный GUI-based инструмент, в котором можно пробовать работу движка, писать тестовые скрипты и запускать их выполнение.
Консольное приложение oscript это основной инструмент работы в командной строке.
Поддерживаемые команды oscript показывает сам, если его запустить без параметров.
Есть также мысль сделать объединение скриптов и исполняющего приложения в один модуль, чтобы получался самостоятельный exe-файл. Но до этого пока руки не дошли.
Исходные коды доступны на bitbucket. Там же, коротенькое wiki о доступных языковых средствах.
Кому интересно посмотреть, как работает, но не хочется собирать из исходников — setup.exe
Короткое заключение
В рамках проекта разработан интерпретатор сценариев на языке 1С, включающий в себя стековую виртуальную машину, исполняющую сценарий и транслятор языка 1С в байт-код виртуальной машины.
Производительность получилась примерно сравнимой с оригиналом. Если учесть, что это любительский проект, сделанный «на коленке», то результат, полагаю, можно считать неплохим. Каких-то серьезных исследований по скорости я не проводил. Ради интереса можно посравнивать скорость математики и больших чисел, но это уже немного отдельная тема.
Надеюсь, данный опус был вам интересен. Форкайте проект, критикуйте, мне будет приятно. Удачи.
3.2 Классическая стековая машина
3.2.1 Блок-схема
Рис. 3.1 Классическая Стековая Машина
3.2.1.1 Шина данных
3.2.1.2 Стек данных
3.2.1.3 Стек адресов возврата
3.2.1.4 АЛУ и регистр вершины стека
АЛУ поддерживает стандартные элементарные операции, необходимые любому компьютеру. В иллюстративных целях этот набор состоит из сложения, вычитания, логических функций ( «И», «ИЛИ», «ИСКЛЮЧАЮЩЕЕ-ИЛИ» ) и операции проверки на нуль. В соответствии с целями разработки все вычисления идут над целыми числами, но в общем случае нет никаких причин, препятствующих добавлению в АЛУ арифметики с плавающей запятой.
3.2.1.5 Счётчик команд
3.2.1.6 Программная память и регистр адресации памяти
3.2.1.7 Ввод/вывод
3.2.2 Операции над данными
Табл. 3.1 Набор инструкций Классической Стековой Машины
3.2.2.1 Обратная польская запись
Стековые машины проводят действия с данными, используя постфиксные операции. Такие операции обычно называются «обратные польские» по аналогии с «обратной польской записью» ( RPN ), часто используемой для описания постфиксных операций. Их особенностью является то, что операнды идут впереди символа операции. Возьмём, например, выражение в обычной ( инфиксной ) записи:
В этом выражении скобки используются для того, чтобы операция сложения была выполнена перед умножением. В их отсутствие действует подразумеваемое старшинство операций. Например, без скобок умножение будет выполняться перед сложением. В постфиксной записи выражение из примера выше выглядело бы следующим образом:
Рис. 3.2 Пример стековой операции
Выражения в постфиксной записи получаются компактнее, по сравнению с инфиксной, так как не требуют ни правил старшинства операторов, ни скобок. Они гораздо лучше подходят под нужды компьютеров. На самом деле, компиляторы, естественно, переводят инфиксные выражения, написанные на языке подобном Си или FORTRAN, в постфиксные машинные коды, иногда используя явное распределение регистров вместо стека для вычисления выражений.
«Классическая Стековая Машина» спроектирована так, чтобы выполнять постфиксные операции непосредственно, не обременяя компилятор регистровой бухгалтерией.
3.2.2.2 Арифметические и логические операторы
В соответствии с требованиями по обеспечению базовых вычислений «Классической Стековой Машине» нужны арифметические и логические операторы. В этом и последующих разделах передача данных между регистрами для каждой инструкции будет поясняться псевдокодом. Например, первая операция «сложение».
| Операция: | + |
| Стек: | N1 N2 → N3 |
| Описание: | Складывает N1 и N2 и возвращает сумму N3 |
| Псевдокод: |
| Операция: | — |
| Стек: | N1 N2 → N3 |
| Описание: | Вычитает N2 из N1 и возвращает разность N3 |
| Псевдокод: |
| Операция: | AND |
| Стек: | N1 N2 → N3 |
| Описание: | Выполняет побитное логическое умножение N1 и N2 и возвращает результат N3 |
| Псевдокод: |
| Операция: | OR |
| Стек: | N1 N2 → N3 |
| Описание: | Выполняет побитное логическое сложение N1 и N2 и возвращает результат N3 |
| Псевдокод: |
| Операция: | XOR |
| Стек: | N1 N2 → N3 |
| Описание: | Выполняет «сложение по модулю 2» N1 и N2 и возвращает результат N3 |
| Псевдокод: |
Очевидно, что буферный регистр верхнего элемента стека экономит заметный объём работы при выполнении этих операций.
3.2.2.3 Операторы для работы со стеком
Одна из проблем машин классической стековой архитектуры состоит в том, что они могут проводить арифметические операции только с двумя верхними элементами стека. Таким образом, на подготовку операндов для вычисления приходится тратить дополнительные инструкции. Следует, естественно, отметить, что некоторые регистровые машины тоже тратят много дополнительных инструкций, перемещая данные между регистрами в процессе подготовки к вычислениям и, таким образом, вопрос о том какой подход лучше становится чуть более запутанным.
Нижеследующие инструкции предназначены для работы с элементами стека.
| Операция: | DROP |
| Стек: | N1 → |
| Описание: | Удаляет N1 из стека |
| Псевдокод: |
Здесь и далее в описаниях инструкций используется запись, подобная «TOSREG ← POP(DS)». В ходе выполнения этой операции данные из стека выставляются на шину данных, затем проходят через АЛУ, где над ними совершается какая-либо пустая операция ( например, сложение с нулём ), чтобы результат положить в регистр вершины стека.
| Операция: | DUP |
| Стек: | N1 → N1 N1 |
| Описание: | Делает копию N1 и помещает её в стек |
| Псевдокод: |
| Операция: | OVER |
| Стек: | N1 N2 → N1 N2 N1 |
| Описание: | Делает копию второго сверху элемента стека N1 и помещает её в стек |
| Псевдокод: |
| Операция: | SWAP |
| Стек: | N1 N2 → N2 N1 |
| Описание: | Меняет местами два верхних элемента стека |
| Псевдокод: |
| Операция: | >R ( Читается как «to R» ) |
| Стек: | N1 → |
| Описание: | Кладёт N1 в стек возврата |
| Псевдокод: |
Инструкция «>R» и её дополнение «R>» позволяет перемещать элементы данных между стеками данных и адресов возврата. Эти команды используются для временного перемещения верхних элементов в стек возврата для получения доступа к данным, лежащим глубже двух первых уровней стека.
| Операция: | R> ( Читается как «R from» ) |
| Стек: | → N1 |
| Описание: | Извлекает верхний элемент из стека возврата и кладёт его в качестве N1 в стек данных |
| Псевдокод: |
3.2.2.4 Чтение и запись памяти
Если все арифметические и логические операции проводятся только над элементами стека, то должен существовать способ загрузки в стек данных или выгрузки данных из стека для сохранения в памяти. «Классическая Стековая Машина» использует простую архитектуру вида «загрузить/сохранить» и поэтому использует одну инструкцию загрузки «@» и одну инструкцию сохранения «!».
У инструкций отсутствует поле операнда, а адрес памяти берётся из стека, что облегчает доступ к членам структуры данных, так как указатель в стеке можно индексировать поэлементно. Инструкции требуют двух циклов обращения к памяти: один для команды и один для данных.
| Операция: | ! ( Читается как «store» ) |
| Стек: | N1 ADDR → |
| Описание: | Сохраняет N1 по адресу ADDR в программной памяти |
| Псевдокод: |
| Операция: | @ ( Читается как «fetch» ) |
| Стек: | ADDR → N1 |
| Описание: | Считывает значение из программной памяти по адресу ADDR и возвращает его в N1 |
| Псевдокод: |
3.2.2.5 Символьные константы
| Операция: | [LIT] |
| Стек: | → N1 |
| Описание: | Рассматривает следующее программное слова как целое число и сохраняет его в стеке в качестве N1 |
| Псевдокод: |
Такая реализация предполагает, что PC указывает на адрес памяти, следующий после кода операции.
3.2.3 Выполнение инструкций
До настоящего момента механизм выборки команд из памяти не учитывался. Обычно под ним подразумевается стандартная последовательность из выборки, декодирования и исполнения инструкции.
3.2.3.1 Счётчик команд
Внутренняя последовательность действий, выполняемая при обработке каждой команды, выглядит так:
| Операция: | [Fetch next instruction] |
| Стек: | |
| Описание: | Выбирает следующую инструкцию |
| Псевдокод: |
3.2.3.2 Условные переходы
| Операция: | [IF] |
| Стек: | N1 → |
| Описание: | В том случае, когда значение N1 ложно ( равно нулю ) в PC загружается адрес из следующего программного слова, в противном случае в PC загружается адрес очередной команды |
| Псевдокод: |
3.2.3.3 Вызов подпрограмм
И, наконец, «Классическая Стековая Машина» должна иметь возможность вызова подпрограмм. Наличие специального стека, выделенного под адреса возврата, позволяет вызывать подпрограммы, просто сохраняя в стеке текущее состояние счётчика команд и загружая в него новое значение. Мы будем считать, что формат инструкции вызова подпрограммы позволяет указать полный адрес процедуры в одном машинном слове, и опустим реальный механизм извлечения из него поля адреса. Реальные процессоры, рассматриваемые в последующих частях книги, предлагают различные способы решения этой задачи при весьма умеренных аппаратных затратах.
Возврат из подпрограммы выполняется простым выталкиванием с вершины стека адреса возврата и помещения его в счётчик команд. Из-за того, что данные хранятся в отдельном стеке, никаких дополнительных действий с указателями или памятью при вызове подпрограмм не требуется.
| Операция: | [CALL] |
| Стек: | |
| Описание: | Выполняет вызов подпрограммы по адресу, расположенному в следующем программном слове |
| Псевдокод: |
| Операция: | [EXIT] |
| Стек: | |
| Описание: | Выполняет возврат из подпрограммы |
| Псевдокод: |
3.2.3.4 Постоянные и подгружаемые наборы инструкций
Для сохранения простоты, описание «Классической Стековой Машины» свободно от рекомендаций по разработке, но, всё же, следует рассмотреть основные сложности, возникающие при воплощении реальных конструкций. Одним из вопросов является выбор между постоянным и подгружаемым набором инструкций. Введение в технику реализации постоянных и подгружаемых наборов можно найти в Koopman ( 1987a ).
Конструкции с постоянным набором обычно быстрее и компактнее. Ценой повышения производительности является бОльшая сложность схемы декодирования и серьёзный риск полной переделки управляющей логики при изменении требований к набору команд ближе к концу срока разработки.
Дополнительным плюсом является тот факт, что в 16— и более разрядных машинах ширина слова заметно больше, чем несколько бит, необходимых для кодирования всех возможных операций. С учётом этого факта модели с постоянным набором используют частично декодированный формат инструкций, позволяющий упростить аппаратуру и увеличить её гибкость. Частично декодированные ( они же не полностью кодированные или «раскодированные» ) инструкции имеют формат, похожий на микрокод, в котором отдельные поля команды отведены под определённые задачи. Это позволяет комбинировать в одном машинном слове несколько независимых операций ( таких, как «DUP» и «[EXIT]» ).
Все эти преимущества жёсткого декодирования могут создать впечатление о бесперспективности применения подгружаемых наборов команд. Тем не менее, у микрокода есть некоторые полезные свойства.
Одним из изъянов микрокода является то, что часто в попытке избежать снижения скорости при обращении к памяти микрокодов приходится использовать конвейер выборки микроинструкций. Это может привести к необходимости увеличения времени исполнения инструкции до двух тактов и более, в то время как конструкции и постоянным набором оптимизированы на исполнение за один такт.
С практической точки зрения, микрокод обычно реализуют в разработках на дискретной логике, поэтому они доминируют в одноплатных решениях. Большинство однокристальных моделей имеет постоянный набор команд.
3.2.4 Изменение состояния
Для приложений реального времени очень важен способ обработки процессором прерываний и переключения задач. Набор команд «Классической Стековой Машины» обходит этот проблему, поэтому мы поговорим о стандартных путях решения, чтобы иметь в дальнейшем основу для сравнения конструкций.
3.2.4.1 Прерывания по переполнению и антипереполнению стека
Прерывания вызываются как исключительными событиями, например, переполнением стека, так и запросами на обслуживание ввода/вывода. Оба вида событий требуют быстрой реакции, не нарушающей логику работы текущего процесса.
Прерывания по переполнению/антипереполнению стека на данный момент самые частые исключительные ситуации в стековых машинах, и поэтому именно на них будет показано, как происходит обработка подобных событий.
Упомянутые исключения возникают в момент исчерпания всего объёма аппаратной стековой памяти. Реагировать можно по-разному: не предпринимать никаких действий и позволить программе завершиться аварийно ( самое простое в реализации, но и самое бесполезное решение [*] ), остановить программу с сообщением о фатальной ошибке и, наконец, переместить часть содержимого стека в системную память, чтобы продолжить исполнение. Понятно, что последний вариант даёт больше всего возможностей, но остановка по ошибке проще в исполнении и в некоторых случаях может быть допустима.
Кроме того, так же могут обрабатываться и другие исключения, например, ошибка чётности памяти.
Исключительные ситуации могут требовать для своей обработки много времени, но в ходе разрешения все они должны сохранять состояние прерванной задачи неизменным, чтобы её исполнение можно было восстановить, если это возможно. Таким образом, исключения не должны требовать от процессора иных действий, кроме аппаратного вызова подпрограммы-обработчика.
3.2.4.2 Прерывания от подсистемы ввода/вывода
Обслуживание ввода/вывода достаточно частое событие, требующее быстрой обработки в системах реального времени. К счастью, такие прерывания обычно требуют немного вычислительных ресурсов и почти не требуют памяти. По этим соображениям в стековых архитектурах прерывания рассматриваются как аппаратно сформированные вызовы подпрограмм.
Такие вызовы кладут параметры в стек, проводят необходимые вычисления, после чего возвращают управление прерванной программе. Есть только одно требование: программа-обработчик прерывания не должна оставлять после себя «мусор» в стеке.
Накладные расходы на обработку прерываний в стековых машинах много ниже, чем в обычных архитектурах. Тому есть несколько причин. Нет нужды сохранять регистры, так как рабочее место в стеке заводится по мере надобности. Нет флагов состояния, требующих сохранения, так как для ветвления программ используются содержимое стека данных. Наконец, конвейер данных в большинстве стековых процессоров или отсутствует вовсе, или очень короткий, и штраф при сохранении его состояния при входе в прерывание отсутствует.
3.2.4.3 Переключение задач
Переключение задач происходит, когда процессор заменяет одну программу на другую, чтобы создать видимость одновременного их исполнения. Состояние программы, останавливаемой при переключении, должно быть сохранено, чтобы она могла продолжить работу позднее. Состояние программы, активируемой в ходе переключения, должно быть полностью восстановлено до момента возобновления её работы.
Общепринятым способом достижения этой цели является использование таймера и переключение задач при каждом его отсчёте с возможным использованием алгоритмов приоритезации и планировки. В простых процессорах это может привести к заметному увеличению накладных расходов на сохранение и восстановление обоих стеков в памяти при каждом переключении контекста. В качестве решения проблемы можно предложить программную технику, использующую «легковесные» задачи, которые не требуют много места в стеке. Такие задачи могут класть свои параметры в стек поверх имеющегося содержимого и освобождать занятое место по завершении, исключая тем самым более дорогостоящее сохранение и восстановление стекового контекста более «тяжёлых» задач.
Другим решением может быть несколько наборов указателей стеков для нескольких задач, использующих общий блок стековой памяти.