Retrascope

h1. Control Flow Graph representation

В данном разделе содержится описание внутреннего представления HDL-описаний на основе графа потока управления (control flow graph, 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@.

Ветвление содержит либо нетривиальное выражение типа @Node@, либо событие типа @Event@. Если ветвление является "событийным", то оно может иметь только один дочерний узел типа @Case@.

условие *@Case@*

Cодержит ровно одну ссылку на родительский узел и ровно одну ссылку на дочерний узел, а также набор допустимых значений. Каждое значение имеет тип @NodeValue@.

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

оператор слияния *@Merge@*

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