Project

General

Profile

Actions

Control flow graph representation

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

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

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

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

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

Процесс Process содержит список чувствительности EventList и граф потока управления Cfg.

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

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

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

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

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

Экземпляр модуля Instance содержит сам модуль Module, строковое имя данного экземпляра модуля, а также набор связей типа Binding.

Связь Binding - это способ присваивания переменным модуля определенных выражений.
Связь содержит внутреннюю переменную MVariable и сопоставляемое ей выражение типа Node.
Node - базовый класс для выражений, переменных и значений ( см. документацию к библиотеке Fortress).

Переменная MVariable содержит строковое имя, тип данных (в настоящее время поддерживаются типы integer, real, boolean и битовые векторы фиксированной длины) и ассоциированные с ней данные MVariableData.
Имя и тип переменной помещены в объекте Variable (см. документацию к библиотеке Fortress).
Ассоциированные с переменной данные MVariableData содержат:
  • указатель на местоположение переменной в памяти ILocation;
  • тип переменной EVariableType (представлены следующие типы: входной сигнал IN_SIGNAL, выходной сигнал OUT_SIGNAL, сквозной сигнал INOUT_SIGNAL, внутренняя переменная REGISTER, константа CONSTANT);
  • флаг isDefined - булевская переменная (если TRUE, то в данной конструкции переменная используется, иначе читается)

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

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

базовый блок BasicBlock
Содержит ровно одну ссылку на родительский узел и ровно одну ссылку на дочерний узел, а также множественное присваивание Assignment.
Множественное присваивание Assignment - это набор утверждений Statement. Наследниками класса Statement являются присваивание AssignStatement и задержка WaitStatement.
Присваивание содержит набор элементарных присваиваний Substitution.
Элементарное присваивание Substitution содержит переменную с указанным поддиапазоном RangedVariable и присваиваемое ей выражение Node.
Задержка WaitStatement содержит событие Event, при наступлении которого продолжается выполнение.

ветвление Switch
Cодержит ровно одну ссылку на родительский узел и не менее двух ссылок на дочерние узлы. Дочерние узлы имеют тип Condition.

условие Condition
Cодержит ровно одну ссылку на родительский узел и ровно одну ссылку на дочерний узел, а также условие типа Node.

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

исключение Assert
Содержит ровно одну ссылку на родительский узел, а также условие, по выполнении которого выбрасывается исключение. Условие имеет тип Node (см. документацию к библиотеке Fortress).

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

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

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

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

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

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

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

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

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

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

Updated by Sergey Smolov almost 6 years ago · 11 revisions