[Из песочницы] Модель разработки на примере Stack-based CPU19.11.2018 23:02

Возникал ли у вас когда-нибудь вопрос «как работает процессор?». Да-да, именно тот, который находится в вашем в ПК/ноутбуке/смартфоне. В этой статье я хочу привести пример самостоятельно придуманного процессора с дизайном на языке Verilog. Verilog — это не совсем тот язык программирования, на который он похож. Это — Hardware Description Language. Написанный код не выполняется чем-либо (если вы не запускаете его в симуляторе, конечно), а превращается в дизайн физической схемы, либо в вид, воспринимаемый FPGA (Field Programmable Gate Array).

Дисклеймер: эта статья — результат работы над проектом в университете, поэтому время на работу было ограничено и многие части проекта находятся еще только в начальной стадии разработки.

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

Чтобы по-настоящему понимать процесс программирования, надо представлять, как работает каждый из используемых инструментов: компилятор/интерпретатор языка, виртуальная машина, если она есть, промежуточный код, и, конечно же, сам процессор. Очень часто люди, изучающие программирование, долгое время находятся на первой стадии — они думают только о том, как работает язык и его компилятор. Это часто ведет к ошибкам, пути решения которых неизвестны начинающему программисту, потому что он не имеет понятия, откуда растут корни этих проблем. Я сам видел несколько живых примеров, где ситуация была примерно как в описании выше, поэтому я решил попробовать исправить данную ситуацию и создать набор вещей, которые помогут понять начинающим программистам все этапы.

Этот набор состоит из:


  • Собственно придуманного языка
  • Плагина подсветки для VS Code
  • Компилятора к нему
  • Набора инструкций
  • Простого процессора, способного выполнять этот набор инструкций (написан на Verilog)

Еще раз напоминаю, что данная статья НЕ ОПИСЫВАЕТ НИЧЕГО ПОХОЖЕГО НА СОВРЕМЕННЫЙ РЕАЛЬНЫЙ ПРОЦЕССОР, она описывает модель, которую легко понять без углубления в детали.

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

Чтобы запустить симуляцию CPU, необходим ModelSim, который вы можете скачать с сайта Intel.

Для запуска компилятора OurLang необходима Java версии >= 8.

Ссылки на проекты:
https://github.com/IamMaxim/OurCPU
https://github.com/IamMaxim/OurLang

Расширение:
https://github.com/IamMaxim/ourlang-vscode

Для сборки Verilog-части я обычно использую скрипт на bash: 

#/bin/bash

vlib work
vlog *.v

vsim -c testbench_1 -do "run; exit"

Но это же можно повторить через GUI.

Для работы с компилятором удобно использовать Intellij IDEA. Главное — следите за тем, какие модули имеет в зависимостях нужный вам модуль. Я не стал выкладывать в открытый доступ готовый .jar, потому что я рассчитываю на то, что читатель будет читать исходный код компилятора.

Запускаемые модули — Compiler и Interpreter. С компилятором все понятно, Interpreter — просто симулятор OurCPU на Java, но мы не будем рассматривать его в этой статье.


Instruction set

Думаю, начать лучше с Instruction Set«а.

Существует несколько архитектур наборов инструкций:


  • Stack-based — то, что описывается в статье. Отличительная особенность — все операнды помещаются в стак и достаются из стака, что сразу исключает возможность распараллеливать выполнение, но при этом является одним из самых простых подходов к работе с данными.
  • Accumulator-based — суть в том, что имеется лишь один регистр, который хранит значение, которое модифицируется инструкциями.
  • Register-based — то, что используется в современных процессорах, потому что позволяет достичь максимальной производительности за счет применения различных оптимизаций, в том числе распараллеливания выполнения, pipelining«а и т.д.

Набор инструкций нашего процессора содержит 30 инструкций

Далее предлагаю взглянуть на реализацию процессора:

Код состоит из нескольких модулей:


  • CPU
  • RAM
  • Модули для каждой инструкции

RAM — модуль, содержащий непосредственно саму память, а также способ получить доступ к данным в ней.

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

Практически все инструкции работают только со стаком, так что достаточно лишь выполнить их. Некоторые (например, putw, putb, jmp и jif) имеют дополнительный аргумент в самой инструкции. Им необходимо передать всю инструкцию, чтобы они могли считать необходимые данные.

Вот схема, в общих чертах описывающая ход работы процессора:

leeq-9mhht6o2lderrpxylbaldm.png

Общие принципы устройства программ на уровне инструкций

Думаю, пришло время познакомиться с устройством непосредственно самих программ. Как видно из схемы выше, после выполнения каждой инструкции адрес переходит к следующей. Это дает линейный ход программы. Когда же появляется необходимость нарушить эту линейность (условие, цикл, и т.д.), используются branch-инструкции (в нашем наборе инструкций это jmp и jif).

При вызове функций нам необходимо сохранить текущее состояние всего, и для этого имеются activation record«ы — записи, хранящие эту информацию. Они никак не привязаны к самому процессору или инструкциям, это просто концепт, который используется компилятором при генерации кода. Activation record в OurLang имеет следующую структуру:

8d1vdowiro_cx_7piaxjns-aqni.png

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

Для вызовов функции в нашем наборе инструкций предусмотрены способы работы с двумя регистрами, содержащимися в модуле CPU (operation pointer и activation address pointer) — putopa/popopa, putara/popara.


Компилятор

А теперь взглянем на самую близкую к конечному программисту часть — компилятор. В целом, компилятор как программа состоит из 3 частей:


  • Лексер
  • Парсер
  • Компилятор

Лексер отвечает за перевод исходного текста программы в лексические единицы, понятные парсеру.

Парсер строит из этих лексических единиц абстрактное синтаксическое дерево.

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

В компиляторе OurLang эти части представлены соответственно классами


  • Lexer.java
  • Parser.java
  • Compiler.java


Язык

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

Как пример программы для понимания синтаксиса предлагается этот фрагмент кода (он же используется для тестирования функционала): 

// single-line comments

/*
* Multi-line comments
*/ 

function print(int arg) {
    instr(putara, 0);
    instr(putw, 4);
    instr(add, 0);
    instr(lw, 0);
    instr(printword, 0);
}

function func1(int arg1, int arg2): int {
    print(arg1);
    print(arg2);

    if (arg1 == 0) {
        return arg2;
    } else {
        return func1(arg1 - 1, arg2);
    };
}

function main() {
    var i: int;

    i = func1(1, 10);

    if (i == 0) {
        i = 1;
    } else {
        i = 2;
    };

    print(i);
}

Акцентировать внимание на языке я не буду, оставлю это на ваше изучение. Через код компилятора, естественно ;).

При его написании я пытался сделать self-explaining код, который понятен без комментариев, так что с пониманием кода компилятора проблем возникнуть не должно.

Ну и естественно, самое интересное — писать код, а затем наблюдать за тем, во что он превращается. Благо, компилятор OurLang генерирует assembly-like код с комментариями,
что поможет не запутаться в том, что происходит внутри.

Также рекомендую установить расширение для Visual Studio Code, оно облегчит работу с языком.

Удачи в изучении проекта!

© Habrahabr.ru