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

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

Версия архитектуры, использованная в этой статье очень близка к той, что была описана в ранее. Есть всё же некоторые изменения:

• Опкоды инструкций пронумерованы заново, их можно увидеть в файле instr.h

• Добавлена инструкция NOP, декодер игнорирует ее при распаковке кода.
  
  Потребность в такой инструкции возникает из-за Vluint7, при упаковке инструкций GOTO и CALL адрес перехода может быть еще неизвестен, так что резервируем место под максимальный адрес (в данном случае 2 байта) с помощью. инструкций NOP. В дальнейшем, когда адрес перехода определится, запишем его в зарезервированное место и если он окажется короче, то остаток будет проигнорирован декодером.

• Зарезервировано еще несколько инструкций - для вычисления логических выражений (OR, AND, NOT, PREOR, PREAND) и битовых операций (BAND, BOR, XOR, BNOT)

• Вместо набора инструкций сравнения (eq, gt, ne, …) предложена единая инструкция cmp с аргументом - типом сравнения. Аргумент это битовая маска из трёх разрядов. Первый (младший) разряд отвечает за “меньше”, средний за “равенство” и третий за “больше”. Так, старая инструкция ge эквивалентна cmp 6.
  
  Такой набор инструкций упрощает внутреннее устройство процессора, хотя и ценой распухшего кода, ведь инструкции из однобайтовых стали двухбайтовыми. Впрочем, сейчас важнее простота, возможно, в дальнейшем еще вернёмся к этому вопросу.

• Адреса начала стека, начала первого фрейма и стартовая позиция кода теперь не зашиты жестко, а определяются при компиляции/сборке программы

Ассемблер

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

Исходный код ассемблера находится по адресу zasm.

Ассемблер написан с использованием генераторов синтаксического (bison) и лексического (flex) анализаторов, что может показаться избыточным для такой, в общем-то, несложной задачи. Но в дальнейшем это сэкономит кучу времени и сил.

Использованная грамматика:

Рассмотрим как это выглядит на практике.

Возьмем уже использовавшийся ранее пример вычисления факториала:

На языке ассемблера это будет выглядит так:

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

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

Секции типа CCODE содержат код потока управления. В них могут быть инструкции потока управления и именованные метки. На метку можно перейти инструкцией goto или попасть через вызов функции. Если блок не заканчивается инструкцией stop, она добавляется автоматически.

Некоторые метки служебные (@endif1, @initial), поэтому начинаются со специального символа @. Кроме него в имени метки могут быть буквы латинского алфавита, цифры и символ ‘_’. Символ @ невозможен в идентификаторах языка С, так что такие метки можно использовать в служебных целях без риска пересечься с пользовательскими именами.

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

Собираем zasm, запускаем (zasm -f test.asm), на выходе получаем два файла с образами памяти: данных (data_segment.mem) и кода (rom_image.mem), аналогичных тем, что мы использовали в предыдущей статье (совместимых с ModelSim от Altera).

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

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

Компилятор 

За основу возьмём доступную грамматику C11 (bison(yacc), flex), не из-за каких-либо особенностей стандарта, а исключительно по причине доступности под рукой. Если при построении ассемблера говорилось об избыточности использования генераторов лексического и синтаксического анализаторов, то здесь они очень даже к месту.

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

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

1. Традиционно, компилятор C пишут на C. Когда требуется портировать компилятор на новую платформу, можно взять какой-то очень простой компилятор, тот же  pcc, и портировать сначала его. Далее с помощью pcc компилируется нужный компилятор, который в конце концов способен скомпилировать сам себя (bootstrapping). Наша цель - демонстрация возможностей, поэтому там где это экономит время и силы, будет использоваться C++.

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

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

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

В нашем случае пул памяти выделяет тегированную память. Каждый аллоцированный кусок предваряет пара (размер-тег). Размер блока в байтах, так можно узнать, например, длину строки. А тег памяти - один из вариантов box_type. Зная тип каждого элемента можно рекурсивно обходить дерево разбора. Это тоже довольно популярная техника. Автор почерпнул её в проекте Virtuoso OpenSource.

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

Ноды устроены однотипно, это массив из элементов размером в указатель, в данном случае 8 байт: Это соответствует структуре c_tree_t, в начале которой стоит тег ноды (не путаем с тегом памяти), описывающий что будет дальше, потом данные - union, каждый элемент которого соответствует тегу. Создаются они функцией драйвера пула памяти box_mp_t::mk_node.

Например, правило грамматики some_identifier описывается так:

Здесь вызывается функция mk_node, первый аргумент указывает на размер ноды в 8-байтных элементах, далее идёт тег STMT_IDENTIFIER и вторым элементом будет указатель на копию строки, полученной при лексическом разборе. Тегу STMT_IDENTIFIER соответствует элемент union’а identifier_, который описан так:

Как видим, в структуре единственный член - указатель на строку.

Еще пример - операция логического И:

В данном случае тег - STMT_BOP_AND соответствует элементу

Т.е. в структуре два указателя на аргументы операции + тег.

Еще стоит упомянуть списки, например, у функции может быть произвольное количество аргументов, грамматика описывает это рекурсивно:

Случай пустого списка описан в правиле более высокого уровня, хотя, вполне можно было описать его и здесь третьим вариантом. Функция driver->mp_.cons_set создаёт элемент списка, в первом случае это список из одного элемента, во втором случае списки объединяются. Таким образом на выходе из правила parameter_list получим список надлежащей длины. При необходимости список нетрудно преобразовать в массив.

В конце концов по окончании синтаксического разбора получим вершину AST как результат разбора правила самого верхнего уровня translation_unit.

4. Разбор дерева AST с генерацией инструкций ассемблера. Тегированная память позволяет заметно упростить разбор синтаксического дерева. Тег конкретного указателя указывает либо на список, либо на массив, либо на литерал (строка, число,...).

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

Массив может оказаться только в случае элемента типа c_tree_t. В этом случае следует продолжить разбор, опираясь та тип/тег этого c_tree_t. Например, в случае тега STMT_BOP_AND, мы понимаем, что это логическое И, которое содержит две ветви, каждая из которых должна закончиться вычислением логического (целочисленного) значения. Результатом разбора этого элемента дерева должно быть вычисление значение логического И от этих двух значений.

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

Как это делается? Для стековой машины генерация инструкций проста и красива.

1. Если нам встретилась константа, добавляем инструкцию imdpush

2. Переменная - varpushd

3. Lvalue (присвоение) - varpush (в отличие от varpushd записывает в стек адрес переменной, а не её значение)

4. операция - добавляем инструкцию, соответствующую этой операции

5. вызов функции - инструкцию call

5. Набор инструкций описан в файлах common/instr.*
Там есть и мнемоники инструкций и их опкоды (идентификаторы).
Инструкции бывают двух типов - из потока управления или потока исполнения.
По коду инструкции и типу потока можно получить описатель инструкции (instr_def_t). Описатель содержит число и типы параметров инструкции, например, у инструкции imdpush один параметр - целое число. Следовательно, при добавлении такой инструкции следует добавить и аргумент.

Здесь:

1. get_asm_instr(ioCXimdpush, false) - получаем описатель инструкции

2. code - создаваемый список (поток) инструкций

3. new_inst добавляет новую инструкцию к потоку

4. new_inst(NULL, code) добавляет в поток пустое место под аргумент

5. box_mp_t::unbox_int преобразует тегированный указатель из дерева разбора в целое. Тег BT_INT говорит нам что там именно оно.

6. tpush(ftInteger32) - записывает в стек типов тип текущего значение. Для корректного преобразования типов требуется знать типы значений в стеке, с этой целью присутствует стек типов, за которым приходится тщательно следить. При использовании бинарных операций в стеке могут оказаться операнды разных типов (int & double, например), так что необходим механизм автоматического приведения типов. Такой механизм, на основании типов на вершине стека, приведёт аргументы к одному типу и вставит инструкцию операции правильного типа.
   
   В данный момент это не требуется, но в дальнейшем обязательно пригодится.

6. После обхода  синтаксического дерева имеем список глобальных переменных, список компилируемых функций. Для каждой функции в наличии поток инструкций, который следует преобразовать в вид, пригодный для ассемблера. У нас есть всё, что нужно для этого - мы знаем к какому потоку относится каждая инструкция, требуется разбить на потоки, кое-где, добавить инструкции exec/stop для переключения с потока на поток

Эмулятор

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

Исходные коды эмулятора можно найти здесь.

Эмулятор принимает файлы, созданные ассемблером zasm: mem_rom image.mem (бинарное представление исполняемого кода) и data_segment.mem (сегмент глобальных данных). А также начальный адрес исполнения, который можно взять в .map файле, подготовленном zasm.

Пример

Компилировать станем вот такой текст:

Функция a, кстати, несмотря на кажущуюся простоту совершенно нетривиальна. Это т.н. функция Аккермана (1928).

В теории вычислимости определяются примитивно-рекурсивные функций,(ПРФ) - это всё, что можно получит из примитивных функций (0, 1, выбор из списка (проекция)) с помощью итераций. Например, операторы сложения, умножения, возведения в степень являются ПРФ.

Также существуют частично рекурсивные функции (ЧРФ) - всё, что можно вычислить с помощью λ-исчисления и/или машины Тьюринга.

Так вот, функция Аккермана не примитивно рекурсивна, она относится к ЧРФ, оставаясь при этом определённой для любых своих аргументов (т.е. математическим языком, тотальна).

Функция Аккермана - частный случай т.н. гипероператора. Чуть выше упоминались три привычных математических оператора: сложение, умножение и возведение в степень. С точки зрения математики, заманчиво иметь один универсальный оператор, который в зависимости от своего дополнительного аргумента может работать как любой из упомянутой троицы. Функция Аккермана предоставляет нам частный случай такого оператора. Более общий случай даёт теорема/последовательность Гудстейна, но это совсем другая история.

Итак:

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

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

Итог

Собираем компилятор zz1, компилируем выше приведённый текст и получаем

Пропускаем этот код через ассемблер

вот карта памяти и собственно код:

Задаём стартовый адрес (main: 0x54, определяется как первый аргумент программы эмулятора), запускаем и получаем:

Итак, результат равен 2045.
Сверимся с предсказанием. a(3, x) => 2 ^{x + 3} - 3
для x=8 ответ должен быть 2 ^{8 + 3} - 3 => 2 ¹¹ - 3 => 2048 - 3 => 2045
Сходится.

Небольшой бонус (в эмуляторе можно позволить себе всё что угодно):

“Пилоты молчат, смотрят на звёзды.
Задание выполнено … успешно.
Все улыбаются.”