Project

General

Profile

Control Flow Graph representation » History » Version 24

Sergey Smolov, 04/02/2015 07:02 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 24 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 24 Sergey Smolov
* тип переменной *@VariableType@* (представлены следующие типы: входной сигнал @IN@, выходной сигнал @OUT@, сквозной сигнал @INOUT@, внутренняя переменная @REG@).
22 9 Sergey Smolov
 
23 1 Mikhail Chupilko
Поддиапазон *@Range@* содержит два числа, задающих соответственно левую и правую границы подмассива.
24
25
Процесс постоянно находится в состоянии ожидания до тех пор, пока не происходит событие, находящееся в списке чувствительности. 
26 24 Sergey Smolov
Как только такое событие происходит, процесс осуществляет выполнение инструкций, которые содержатся в его графе потока управления.
27 1 Mikhail Chupilko
28 22 Sergey Smolov
Между @CfgNode@ узлами, находящимися в @Process@ процессе, могут быть определены связи "родитель <-> ребенок". Если узел A является родителем узла B, то это означает, что поток управления сначала попадает в узел A, а потом в узел B.
29 1 Mikhail Chupilko
В общем случае допускается наличие нескольких родительских и нескольких дочерних узлов, но для каждого из типов узлов могут бть введены дополнительные ограничения.
30
Все типы узлов указаны в перечислимом типе *@CfgNodeType@*:
31 22 Sergey Smolov
@SOURCE@ - стартовый узел графа потока управления типа *@Source@*, содержит ссылку на родительский узел @Process@, содержит ровно одну ссылку на дочерний узел
32
@SINK@ - конечный узел графа потока управления типа *@Sink@*, не содержит ссылок на дочерние узлы, содержит ровно одну ссылку на родительский узел
33 23 Sergey Smolov
@BASIC_BLOCK@ - узел базового блока типа @BasicBlock@
34 1 Mikhail Chupilko
@CASE@ - узел условия типа @Case@
35
@SWITCH@ - узел ветвления типа @Switch@
36 19 Sergey Smolov
@MERGE@ - узел типа @Merge@
37 22 Sergey Smolov
@PROCESS@ - узел типа @Process@ (не может быть вершиной в @Process@, относится к типу @CfgModelNode@)
38
@MODULE@ - узел типа @Module@ (не может быть вершиной в @Process@, относится к типу @CfgModelNode@)
39 1 Mikhail Chupilko
40
Часть узлов уже была рассмотрена выше.
41
42
базовый блок *@BasicBlock@* 
43 22 Sergey Smolov
Может быть неблокирующим (concurrent) или блокирующим.
44 16 Sergey Smolov
Содержит ровно одну ссылку на родительский узел и список инструкций присваивания. Присваивания являются объектами класса @Assignment@.
45 18 Sergey Smolov
Присваивания, находящиеся в одном базовом блоке, выполняются в том порядке, в котором они хранятся в списке.
46 22 Sergey Smolov
*@Assignment@* - это переменная с указанным поддиапазоном (возможно пустым, что соответствует переменной целиком) @RangedVariable@ и присваиваемое ей выражение @Node@.
47 1 Mikhail Chupilko
48
ветвление *@Switch@* 
49 22 Sergey Smolov
Cодержит ровно одну ссылку на родительский узел и не менее одной ссылки на дочерние узлы. Дочерние узлы имеют тип @Case@.
50 20 Sergey Smolov
Ветвление содержит либо нетривиальное выражение типа @Node@, либо событие типа @Event@. Если ветвление является "событийным", то оно может иметь только один дочерний узел типа @Case@.
51 1 Mikhail Chupilko
52
условие *@Case@*
53 22 Sergey Smolov
Cодержит ровно одну ссылку на родительский узел типа @Switch@ и ровно одну ссылку на дочерний узел, а также набор допустимых значений. Каждое значение имеет тип @NodeValue@.
54 20 Sergey Smolov
Значения соответствуют выражению, хранящемуся в родительском узле ветвления. Подразумевается, что если выполнение пошло через данный @Case@-узел, то выражение из родительского @Switch@-узла приняло какое-то из допустимых значений дочернего узла.
55 1 Mikhail Chupilko
56 11 Sergey Smolov
оператор слияния *@Merge@*
57 13 Sergey Smolov
Является обратным к условному оператору. Cодержит не менее двух ссылок на родительские узлы и ровно одну ссылку на дочерний узел.