DAG (Directed Acyclic Graph)
DAG (Directed Acyclic Graph) --- бесконтурный орграф.
A directed acyclic graph, also called a DAG, is a directed graphwithout 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.
