Project

General

Profile

Control Flow Graph representation » History » Version 14

Sergey Smolov, 07/17/2014 05:44 PM

1 1 Mikhail Chupilko
h1. Control Flow Graph representation
2
3
В данном разделе содержится описание внутреннего представления HDL-описаний на основе графа потока управления (control flow graph, CFG). В дальнейшем представление будет именоваться CFG-моделью.
4
5
CFG-модель состоит из трех подсистем:
6
* представления конструкций исходного кода
7
* компонентов связывания с исходным кодом
8
* модели памяти
9
10
h2. Представление конструкций исходного кода
11
12
Классом верхнего уровня CFG-модели является *@CFGModel@*. @CFGModel@ содержит набор модулей @Module@, никак не связанных между собой.
13
14 9 Sergey Smolov
Модуль *@Module@* содержит строковое имя, строковое имя конкретного экземпляра (непустое при инстанцировании) модуля, набор вложенных модулей @Module@, набор процессов @Process@.
15 1 Mikhail Chupilko
16 12 Sergey Smolov
Процесс *@Process@* содержит список чувствительности @EventList@ и граф потока управления @Cfg@. Процесс может иметь "начальный" (initial) тип. Процессы начального типа имеют пустой список чувствительности.
17
Если процесс "начального" типа, то он выполняется однократно, прочие процессы выполняются "вечно" - содержащиеся в них последовательности инструкций начинают выполняться каждый раз, когда возникает событие из соответствующих списков чувствительности. 
18 1 Mikhail Chupilko
19
Список чувствительности *@EventList@* содержит неупорядоченный набор событий @Event@ (возможно пустой). 
20
21
Событие *@Event@* описывается типом события @EventType@ и переменной @RangedVariable@, для которой и наступает событие.
22
Представлены следующие типы событий *@EventType@*: передний фронт @POSITIVE_EDGE@, задний фронт @NEGATIVE_EDGE@, произвольный фронт @ANY_EDGE@.
23
24 9 Sergey Smolov
Переменная с указанным поддиапазоном *@RangedVariable@* содержит переменную @NodeVariable@ (см. документацию к библиотеке Fortress) и её поддиапазон @Range@.
25
Поле пользовательских данных переменной @NodeVariable@ содержит дескриптор данных *@VariableData@*. 
26
27
Дескриптор данных содержит:
28
* указатель на местоположение переменной в памяти @ILocation@;
29
* тип переменной *@VariableType@* (представлены следующие типы: входной сигнал @IN_SIGNAL@, выходной сигнал @OUT_SIGNAL@, сквозной сигнал @INOUT_SIGNAL@, внутренняя переменная @REGISTER@, константа @CONSTANT@).
30
 
31 1 Mikhail Chupilko
Поддиапазон *@Range@* содержит два числа, задающих соответственно левую и правую границы подмассива.
32
33
Процесс постоянно находится в состоянии ожидания до тех пор, пока не происходит событие, находящееся в списке чувствительности. 
34
Как только такое событие происходит, процесс осуществляет выполнение всех инструкций, которые содержатся в его графе потока управления.
35
36 7 Sergey Smolov
На множестве процессов задается отношение частичного порядка вида "happens before". 
37 1 Mikhail Chupilko
Отношение задает порядок выполнения разных процессов при возникновении общего события в их списках чувствительности. 
38 7 Sergey Smolov
Отношение задается только в том случае, когда процессы (теоретически) имеют зависимость по данным.
39 1 Mikhail Chupilko
В CFG-модели данное отношение реализовано как множества ссылок на входящие и исходящие зависимости для каждого процесса.
40 6 Sergey Smolov
С помощью методов @getParentProcesses()@ и @getChildProcesses()@ для фиксированного процесса можно определить предшествующие ему и последующие процессы соответственно.
41 1 Mikhail Chupilko
42
Граф потока управления *@Cfg@* - это набор узлов *@CfgNode@*. Между узлами могут быть определены связи "родитель <-> ребенок". Если узел A является родителем узла B, то это означает, что поток управления сначала попадает в узел A, а потом в узел B.
43
В общем случае допускается наличие нескольких родительских и нескольких дочерних узлов, но для каждого из типов узлов могут бть введены дополнительные ограничения.
44
Все типы узлов указаны в перечислимом типе *@CfgNodeType@*:
45
@CFG@ - граф потока управления
46 4 Sergey Smolov
@SOURCE@ - стартовый узел графа потока управления типа *@Source@*, не содержит ссылок на родительские узлы, содержит ровно одну ссылку на дочерний узел
47 13 Sergey Smolov
@SINK@ - конечный узел графа потока управления типа *@Sink@*, не содержит ссылок на дочерние узлы, может иметь несколько ссылок на родительский узел
48 1 Mikhail Chupilko
@NODE@ - узел неопределенного типа
49
@ASSERT@ - узел типа @Assertion@, не содержит ссылок на дочерние узлы, содержит ровно одну ссылку на родительский узел
50
@BASIC_BLOCK@ - узел базового блока типа @BasicBlock@, 
51
@CONDITION@ - узел условия типа @Condition@
52
@SWITCH@ - узел ветвления типа @Switch@
53
@MERGE@ - узел типа @Merge@
54
@INSTANCE@ - узел типа @Instance@
55
@PROCESS@ - узел типа @Process@
56
@MODULE@ - узел типа @Module@
57
58
Часть узлов уже была рассмотрена выше.
59
60
базовый блок *@BasicBlock@* 
61 5 Sergey Smolov
Содержит ровно одну ссылку на родительский узел и список инструкций присваивания. Присваивания являются объектами класса @AssignStatement@.
62 10 Sergey Smolov
Присваивания, находящиеся в одном базовом блоке, выполняются в том порядке, в котором они хранятся в списке.
63
*@AssignStatement@* - это набор элементарных присваиваний @AtomicAssignStatement@. Элементарные присваивания, находящиеся в одном присваивании,
64
выполняются одновременно.
65
В частности, в языке VHDL к одновременно выполняемым относятся присваивания значений сигналам. Такие присваивания в данном представлении называются
66
"конкурирующими". Если исходный код содержит последовательность конкурирующих присваиваний, то в данном представлении они буду объединены в одно присваивание.
67 8 Sergey Smolov
Элементарное присваивание *@AtomicAssignStatement@* содержит переменную с указанным поддиапазоном @RangedVariable@ и присваиваемое ей выражение @Node@.
68 1 Mikhail Chupilko
69
ветвление *@Switch@* 
70 14 Sergey Smolov
Cодержит ровно одну ссылку на родительский узел и не менее двух ссылок на дочерние узлы. Дочерние узлы имеют тип @Case@ (допускается также добавление не более чем одного дочернего узла типа @Merge@).
71
Ветвление содержит выражение, значение которого проверяется в данном блоке.
72 1 Mikhail Chupilko
73 14 Sergey Smolov
условие *@Case@*
74
Cодержит ровно одну ссылку на родительский узел и ровно одну ссылку на дочерний узел, а также набор допустимых значений. Каждое значение имеет тип @NodeValue@.
75
Значения соответствуют выражению, хранящемуся в родительском узле ветвления.
76 1 Mikhail Chupilko
77
оператор слияния *@Merge@*
78
Является обратным к условному оператору. Cодержит не менее двух ссылок на родительские узлы и ровно одну ссылку на дочерний узел.
79
80 11 Sergey Smolov
исключение *@Assertion@*
81 13 Sergey Smolov
Содержит ровно одну ссылку на родительский узел, ровно одну ссылку на дочерний узел, а также уровень выбрасываемого исключения. Родительским узлом для узла @Assertion@ может быть только узел @Condition@. Дочерним узлом для узла @Assertion@ может быть только узел @Sink@.
82 1 Mikhail Chupilko
83
h2. Подсистема компонентов связывания с исходным кодом
84
85
*Важно*: подсистема не реализована, присутствует в проекте в виде заготовки.
86
87
Описание расположения *@CodeLocation@* содержит полное имя @QFileName@ файла, где расположена соответствующая структура исходного кода (инструкция, модуль или что-то иное); также содержит отображение диапазонов номеров строк в сами строки @CodeLineMap@.
88
89
Полное имя *@QFileName@* является оберткой вокруг строкового имени, содержащего абсолютный путь к файлу.
90
91
Отображение *@CodeLineMap@* содержит набор пар вида <диапазон строк @CodeLineRegion@, контейнер соответствующих строк @CodeLineContainer@>.
92
93
Диапазон строк *@CodeLineRegion@* содержит два номера, называемых левым и правым индексами.
94
95
Контейнер строк *@CodeLineContainer@* содержит набор строк кода.
96
97
h2. Подсистема модели памяти
98
99
*Важно*: подсистема не реализована, присутствует в проекте в виде заготовки.
100
101
Цель создания модели памяти заключается в необходимости имитировать исполнение ВП на конкретных данных (например, для исполнения тестовых последовательностей). Основным компонентом здесь является память *@Memory@*, которая представляет собой массив ячеек типа *@Bit@*. Каждая ячейка имеет номер и содержимое. Для заполнения ячеек памятью используется механизм извлечения подмассива ячеек, такой подмассив имеет тип *@Location@*. Предполагается, что у каждой переменной ВП @MVariable@ имеется свой подмассив ячеек памяти @Location@.