Project

General

Profile

Control Flow Graph representation » History » Version 23

Sergey Smolov, 04/02/2015 07:01 PM

1 1 Mikhail Chupilko
h1. Control Flow Graph representation
2
3
В данном разделе содержится описание внутреннего представления HDL-описаний на основе графа потока управления (control flow graph, CFG). В дальнейшем представление будет именоваться CFG-моделью.
4
5
Классом верхнего уровня CFG-модели является *@CFGModel@*. @CFGModel@ содержит набор модулей @Module@, никак не связанных между собой.
6
7 9 Sergey Smolov
Модуль *@Module@* содержит строковое имя, строковое имя конкретного экземпляра (непустое при инстанцировании) модуля, набор вложенных модулей @Module@, набор процессов @Process@.
8 1 Mikhail Chupilko
9 22 Sergey Smolov
Процесс *@Process@* содержит список чувствительности @EventList@ и набор вершин @CfgNode@. Процесс может иметь "начальный" (initial) тип. Процессы начального типа имеют пустой список чувствительности.
10 12 Sergey Smolov
Если процесс "начального" типа, то он выполняется однократно, прочие процессы выполняются "вечно" - содержащиеся в них последовательности инструкций начинают выполняться каждый раз, когда возникает событие из соответствующих списков чувствительности. 
11 1 Mikhail Chupilko
12
Список чувствительности *@EventList@* содержит неупорядоченный набор событий @Event@ (возможно пустой). 
13
14
Событие *@Event@* описывается типом события @EventType@ и переменной @RangedVariable@, для которой и наступает событие.
15
Представлены следующие типы событий *@EventType@*: передний фронт @POSITIVE_EDGE@, задний фронт @NEGATIVE_EDGE@, произвольный фронт @ANY_EDGE@.
16
17 9 Sergey Smolov
Переменная с указанным поддиапазоном *@RangedVariable@* содержит переменную @NodeVariable@ (см. документацию к библиотеке Fortress) и её поддиапазон @Range@.
18
Поле пользовательских данных переменной @NodeVariable@ содержит дескриптор данных *@VariableData@*. 
19
20
Дескриптор данных содержит:
21
* указатель на местоположение переменной в памяти @ILocation@;
22 15 Sergey Smolov
* тип переменной *@VariableType@* (представлены следующие типы: входной сигнал @IN@, выходной сигнал @OUT@, сквозной сигнал @INOUT@, внутренняя переменная @REG@, константа @CONST@).
23 9 Sergey Smolov
 
24 1 Mikhail Chupilko
Поддиапазон *@Range@* содержит два числа, задающих соответственно левую и правую границы подмассива.
25
26
Процесс постоянно находится в состоянии ожидания до тех пор, пока не происходит событие, находящееся в списке чувствительности. 
27
Как только такое событие происходит, процесс осуществляет выполнение всех инструкций, которые содержатся в его графе потока управления.
28
29 22 Sergey Smolov
Между @CfgNode@ узлами, находящимися в @Process@ процессе, могут быть определены связи "родитель <-> ребенок". Если узел A является родителем узла B, то это означает, что поток управления сначала попадает в узел A, а потом в узел B.
30 1 Mikhail Chupilko
В общем случае допускается наличие нескольких родительских и нескольких дочерних узлов, но для каждого из типов узлов могут бть введены дополнительные ограничения.
31
Все типы узлов указаны в перечислимом типе *@CfgNodeType@*:
32 22 Sergey Smolov
@SOURCE@ - стартовый узел графа потока управления типа *@Source@*, содержит ссылку на родительский узел @Process@, содержит ровно одну ссылку на дочерний узел
33
@SINK@ - конечный узел графа потока управления типа *@Sink@*, не содержит ссылок на дочерние узлы, содержит ровно одну ссылку на родительский узел
34 23 Sergey Smolov
@BASIC_BLOCK@ - узел базового блока типа @BasicBlock@
35 1 Mikhail Chupilko
@CASE@ - узел условия типа @Case@
36
@SWITCH@ - узел ветвления типа @Switch@
37 19 Sergey Smolov
@MERGE@ - узел типа @Merge@
38 22 Sergey Smolov
@PROCESS@ - узел типа @Process@ (не может быть вершиной в @Process@, относится к типу @CfgModelNode@)
39
@MODULE@ - узел типа @Module@ (не может быть вершиной в @Process@, относится к типу @CfgModelNode@)
40 1 Mikhail Chupilko
41
Часть узлов уже была рассмотрена выше.
42
43
базовый блок *@BasicBlock@* 
44 22 Sergey Smolov
Может быть неблокирующим (concurrent) или блокирующим.
45 16 Sergey Smolov
Содержит ровно одну ссылку на родительский узел и список инструкций присваивания. Присваивания являются объектами класса @Assignment@.
46 18 Sergey Smolov
Присваивания, находящиеся в одном базовом блоке, выполняются в том порядке, в котором они хранятся в списке.
47 22 Sergey Smolov
*@Assignment@* - это переменная с указанным поддиапазоном (возможно пустым, что соответствует переменной целиком) @RangedVariable@ и присваиваемое ей выражение @Node@.
48 1 Mikhail Chupilko
49
ветвление *@Switch@* 
50 22 Sergey Smolov
Cодержит ровно одну ссылку на родительский узел и не менее одной ссылки на дочерние узлы. Дочерние узлы имеют тип @Case@.
51 20 Sergey Smolov
Ветвление содержит либо нетривиальное выражение типа @Node@, либо событие типа @Event@. Если ветвление является "событийным", то оно может иметь только один дочерний узел типа @Case@.
52 1 Mikhail Chupilko
53
условие *@Case@*
54 22 Sergey Smolov
Cодержит ровно одну ссылку на родительский узел типа @Switch@ и ровно одну ссылку на дочерний узел, а также набор допустимых значений. Каждое значение имеет тип @NodeValue@.
55 20 Sergey Smolov
Значения соответствуют выражению, хранящемуся в родительском узле ветвления. Подразумевается, что если выполнение пошло через данный @Case@-узел, то выражение из родительского @Switch@-узла приняло какое-то из допустимых значений дочернего узла.
56 1 Mikhail Chupilko
57 11 Sergey Smolov
оператор слияния *@Merge@*
58 13 Sergey Smolov
Является обратным к условному оператору. Cодержит не менее двух ссылок на родительские узлы и ровно одну ссылку на дочерний узел.