DAG (Directed Acyclic Graph)

DAG (Directed Acyclic Graph) — бесконтурный орграф.

A directed acyclic graph, also called a DAG, is a directed graph without cycles

The reachability relation in a DAG forms a partial order, and any finite partial order may be represented by a DAG using reachability. DAGs may also be used to model expressions and basic blocks.

A DAG presentation for an expression identifies the common subexpression of the expression. Like a syntax tree, an expression dag has a node for every subexpression of the expression; an interior node represents an operator and its children represent its operands. The difference is that a node in a dag representing a common subexpression has more than one parent, in a syntax tree, the common subexpression would be represented as a duplicated subtree.

DAG is a useful data structure for implementing transformations on basic blocks. A DAG representation for a basic block gives a picture of how the value computed by each statement in a basic block is used in subsequent statements of a block. A dag for a basic block is a directed acyclic graph with the following labels on nodes.

(1) Leaves are labeled by unique identifiers, either variable names or constants. From the operator applied to a name, we determine whether the [math]\displaystyle{ \,l }[/math]-value or [math]\displaystyle{ \,r }[/math]-value of a name is needed; most leaves represent [math]\displaystyle{ \,r }[/math]-values. The leaves represent the initial values of names, and we subscript them with [math]\displaystyle{ \,0 }[/math] to avoid confusion with labels denoting current values of names as in (3) below.

(2) Interior nodes are labeled by an operator symbol.

(3) Nodes are also optionally given a sequence of identifiers for a label. The intention is that interior nodes represent computed values, and the identifiers labeling a node are deemed to have that value.

(4) Certain nodes are designated output nodes. These are the nodes whose variables are live on exit from the block; that is, their values may be used later, in another block of the flow graph.

It is important not to confuse dags with flow graphs. Each node of a flow graph can be represented by a dag, since each node of the flow graph stands for a basic block.

Литература

• Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009.