DAG (Directed Acyclic Graph): различия между версиями

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

A '''[[directed acyclic graph]]''', also called a '''DAG''', is a ''[[directed graph]]'' without ''[[cycle|cycles]]''

The reachability relation in a DAG forms a partial order, and any finite partial order may be represented by a DAG using reachability.

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

A '''[[dag for basic block|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>\,l</math>-value or <math>\,r</math>-value of a name is needed; most leaves represent <math>\,r</math>-values. The leaves represent the initial values of names, and we subscript them with <math>\,0</math> to avoid confusion with labels denoting ''current'' values of names as in (3) below.

(3) Nodes are also optionally given a sequence of identifiers for a label. The intention is that interior nodes represent computed values,

(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

It is important not to confuse dags with ''[[flow graph|flow graphs]]''. Each node of a flow graph can be represented by a dag, since each node of the