Control Flow Graph representation » History » Revision 2
Revision 1 (Mikhail Chupilko, 05/13/2014 05:23 PM) → Revision 2/29 (Sergey Smolov, 05/14/2014 05:09 PM)
h1. Control Flow Graph representation
В данном разделе содержится описание внутреннего представления HDL-описаний на основе графа потока управления (control flow graph, CFG). В дальнейшем представление будет именоваться CFG-моделью.
CFG-модель состоит из трех подсистем:
* представления конструкций исходного кода
* компонентов связывания с исходным кодом
* модели памяти
h2. Представление конструкций исходного кода
Классом верхнего уровня 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).
h2. Подсистема компонентов связывания с исходным кодом
*Важно*: подсистема не реализована, присутствует в проекте в виде заготовки.
Описание расположения *@CodeLocation@* содержит полное имя @QFileName@ файла, где расположена соответствующая структура исходного кода (инструкция, модуль или что-то иное); также содержит отображение диапазонов номеров строк в сами строки @CodeLineMap@.
Полное имя *@QFileName@* является оберткой вокруг строкового имени, содержащего абсолютный путь к файлу.
Отображение *@CodeLineMap@* содержит набор пар вида <диапазон строк @CodeLineRegion@, контейнер соответствующих строк @CodeLineContainer@>.
Диапазон строк *@CodeLineRegion@* содержит два номера, называемых левым и правым индексами.
Контейнер строк *@CodeLineContainer@* содержит набор строк кода.
h2. Подсистема модели памяти
*Важно*: подсистема не реализована, присутствует в проекте в виде заготовки.
Цель создания модели памяти заключается в необходимости имитировать исполнение ВП на конкретных данных (например, для исполнения тестовых последовательностей). Основным компонентом здесь является память *@Memory@*, которая представляет собой массив ячеек типа *@Bit@*. Каждая ячейка имеет номер и содержимое. Для заполнения ячеек памятью используется механизм извлечения подмассива ячеек, такой подмассив имеет тип *@Location@*. Предполагается, что у каждой переменной ВП @MVariable@ имеется свой подмассив ячеек памяти @Location@.