Control Flow Graph representation¶

В данном разделе содержится описание внутреннего представления HDL-описаний на основе графа потока управления (control flow graph, CFG). В дальнейшем представление будет именоваться CFG-моделью.

CFG-модель состоит из трех подсистем:

• представления конструкций исходного кода
• компонентов связывания с исходным кодом
• модели памяти

Представление конструкций исходного кода¶

Классом верхнего уровня CFG-модели является CFGModel. CFGModel содержит набор модулей Module, никак не связанных между собой.

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

Процесс Process содержит список чувствительности EventList и граф потока управления Cfg. Процесс может иметь "начальный" (initial) тип. Процессы начального типа имеют пустой список чувствительности.
Если процесс "начального" типа, то он выполняется однократно, прочие процессы выполняются "вечно" - содержащиеся в них последовательности инструкций начинают выполняться каждый раз, когда возникает событие из соответствующих списков чувствительности.

Список чувствительности EventList содержит неупорядоченный набор событий Event (возможно пустой).

Событие Event описывается типом события EventType и переменной RangedVariable, для которой и наступает событие.
Представлены следующие типы событий EventType: передний фронт POSITIVE_EDGE, задний фронт NEGATIVE_EDGE, произвольный фронт ANY_EDGE.

Переменная с указанным поддиапазоном RangedVariable содержит переменную NodeVariable (см. документацию к библиотеке Fortress) и её поддиапазон Range.
Поле пользовательских данных переменной NodeVariable содержит дескриптор данных VariableData.

Дескриптор данных содержит:

• указатель на местоположение переменной в памяти ILocation;
• тип переменной VariableType (представлены следующие типы: входной сигнал IN, выходной сигнал OUT, сквозной сигнал INOUT, внутренняя переменная REG, константа CONST).

Поддиапазон Range содержит два числа, задающих соответственно левую и правую границы подмассива.

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

На множестве процессов задается отношение частичного порядка вида "happens before".
Отношение задает порядок выполнения разных процессов при возникновении общего события в их списках чувствительности.
Отношение задается только в том случае, когда процессы (теоретически) имеют зависимость по данным.
В CFG-модели данное отношение реализовано как множества ссылок на входящие и исходящие зависимости для каждого процесса.
С помощью методов getParentProcesses() и getChildProcesses() для фиксированного процесса можно определить предшествующие ему и последующие процессы соответственно.

Граф потока управления Cfg - это набор узлов CfgNode. Между узлами могут быть определены связи "родитель <-> ребенок". Если узел A является родителем узла B, то это означает, что поток управления сначала попадает в узел A, а потом в узел B.
В общем случае допускается наличие нескольких родительских и нескольких дочерних узлов, но для каждого из типов узлов могут бть введены дополнительные ограничения.
Все типы узлов указаны в перечислимом типе CfgNodeType:
CFG - граф потока управления
SOURCE - стартовый узел графа потока управления типа Source, не содержит ссылок на родительские узлы, содержит ровно одну ссылку на дочерний узел
SINK - конечный узел графа потока управления типа Sink, не содержит ссылок на дочерние узлы, может иметь несколько ссылок на родительский узел
NODE - узел неопределенного типа
BASIC_BLOCK - узел базового блока типа BasicBlock,
CASE - узел условия типа Case
SWITCH - узел ветвления типа Switch
MERGE - узел типа Merge
INSTANCE - узел типа Instance
PROCESS - узел типа Process
MODULE - узел типа Module

Часть узлов уже была рассмотрена выше.

базовый блок BasicBlock
Содержит ровно одну ссылку на родительский узел и список инструкций присваивания. Присваивания являются объектами класса Assignment.
Присваивания, находящиеся в одном базовом блоке, выполняются в том порядке, в котором они хранятся в списке.
Assignment - это набор переменных с указанным поддиапазоном (возможно пустым, что соответствует переменной целиком) RangedVariable и присваиваемое их конкатенации выражение Node.
Присваивание может быть неблокирующим (concurrent) или блокирующим.

ветвление Switch
Cодержит ровно одну ссылку на родительский узел и не менее двух ссылок на дочерние узлы. Дочерние узлы имеют тип Case.
Ветвление содержит выражение, значение которого проверяется в данном блоке.

условие Case
Cодержит ровно одну ссылку на родительский узел и ровно одну ссылку на дочерний узел, а также набор допустимых значений. Каждое значение имеет тип NodeValue.
Значения соответствуют выражению, хранящемуся в родительском узле ветвления. Подразумевается, что если выполнение пошло через данный Case-узел, то выражение из родительского Switch-узла приняло какое-то из допустимых значений.

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

Подсистема компонентов связывания с исходным кодом¶

Важно: подсистема не реализована, присутствует в проекте в виде заготовки.

Описание расположения CodeLocation содержит полное имя QFileName файла, где расположена соответствующая структура исходного кода (инструкция, модуль или что-то иное); также содержит отображение диапазонов номеров строк в сами строки CodeLineMap.

Полное имя QFileName является оберткой вокруг строкового имени, содержащего абсолютный путь к файлу.

Отображение CodeLineMap содержит набор пар вида <диапазон строк CodeLineRegion, контейнер соответствующих строк CodeLineContainer>.

Диапазон строк CodeLineRegion содержит два номера, называемых левым и правым индексами.

Контейнер строк CodeLineContainer содержит набор строк кода.

Подсистема модели памяти¶

Важно: подсистема не реализована, присутствует в проекте в виде заготовки.

Цель создания модели памяти заключается в необходимости имитировать исполнение ВП на конкретных данных (например, для исполнения тестовых последовательностей). Основным компонентом здесь является память Memory, которая представляет собой массив ячеек типа Bit. Каждая ячейка имеет номер и содержимое. Для заполнения ячеек памятью используется механизм извлечения подмассива ячеек, такой подмассив имеет тип Location. Предполагается, что у каждой переменной ВП MVariable имеется свой подмассив ячеек памяти Location.