Project

General

Profile

Control Flow Graph representation » History » Revision 13

Revision 12 (Sergey Smolov, 07/15/2014 03:45 PM) → Revision 13/29 (Sergey Smolov, 07/16/2014 05:54 PM)

h1. Control Flow Graph representation 

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

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

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

 Классом верхнего уровня 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_SIGNAL@, выходной сигнал @OUT_SIGNAL@, сквозной сигнал @INOUT_SIGNAL@, внутренняя переменная @REGISTER@, константа @CONSTANT@). 
 
 Поддиапазон *@Range@* содержит два числа, задающих соответственно левую и правую границы подмассива. 

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

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

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

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

 базовый блок *@BasicBlock@*  
 Содержит ровно одну ссылку на родительский узел и список инструкций присваивания. Присваивания являются объектами класса @AssignStatement@. 
 Присваивания, находящиеся в одном базовом блоке, выполняются в том порядке, в котором они хранятся в списке. 
 *@AssignStatement@* - это набор элементарных присваиваний @AtomicAssignStatement@. Элементарные присваивания, находящиеся в одном присваивании, 
 выполняются одновременно. 
 В частности, в языке VHDL к одновременно выполняемым относятся присваивания значений сигналам. Такие присваивания в данном представлении называются 
 "конкурирующими". Если исходный код содержит последовательность конкурирующих присваиваний, то в данном представлении они буду объединены в одно присваивание. 
 Элементарное присваивание *@AtomicAssignStatement@* содержит переменную с указанным поддиапазоном @RangedVariable@ и присваиваемое ей выражение @Node@. 

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

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

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

 исключение *@Assertion@* 
 Содержит ровно одну ссылку на родительский узел, ровно одну ссылку на дочерний узел, а также уровень выбрасываемого исключения. Родительским узлом для узла @Assertion@ может быть только узел типа @Condition@. Дочерним узлом для узла @Assertion@ может быть только узел @Sink@. 

  

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

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

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

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

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

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

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

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

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

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