In computer science

Computer science

Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...

, in control flow graph

Control flow graph

A control flow graph in computer science is a representation, using graph notation, of all paths that might be traversed through a program during its execution.- Overview :...

s, a node

Node (computer science)

A node is a record consisting of one or more fields that are links to other nodes, and a data field. The link and data fields are often implemented by pointers or references although it is also quite common for the data to be embedded directly in the node. Nodes are used to build linked, often...

 d dominates a node n if every path from the start node to n must go through d. Notationally, this is written as d dom n (or sometimes d n). By definition, every node dominates itself.

There are a number of related concepts:

• A node d strictly dominates a node n if d dominates n and d does not equal n.
• The immediate dominator or idom of a node n is the unique node that strictly dominates n but does not strictly dominate any other node that strictly dominates n. Not all nodes have immediate dominators (e.g. entry nodes).
• The dominance frontier of a node d is the set of all nodes n such that d dominates an immediate predecessor of n, but d does not strictly dominate n. It is the set of nodes where d's dominance stops.
• A dominator tree is a tree
  Tree (graph theory)
  In mathematics, more specifically graph theory, a tree is an undirected graph in which any two vertices are connected by exactly one simple path. In other words, any connected graph without cycles is a tree...
  
   where each node's children are those nodes it immediately dominates. Because the immediate dominator is unique, it is a tree. The start node is the root of the tree.

History

Dominance was first introduced by Reese T. Prosser in a 1959 paper on analysis of flow diagrams. Prosser did not present an algorithm for computing dominance, which had to wait ten years for Edward S. Lowry and C. W. Medlock. Ron Cytron et al. rekindled interest in dominance in 1989 when they applied it to efficient computation of φ functions, which are used in static single assignment form

Static single assignment form

In compiler design, static single assignment form is a property of an intermediate representation , which says that each variable is assigned exactly once...

.

Applications

Dominators, and dominance frontiers particularly, have applications in compiler

Compiler

A compiler is a computer program that transforms source code written in a programming language into another computer language...

s for computing static single assignment form

Static single assignment form

In compiler design, static single assignment form is a property of an intermediate representation , which says that each variable is assigned exactly once...

. A number of compiler optimizations can also benefit from dominators. The flow graph in this case comprises basic block

Basic block

In computing, a basic block is a portion of the code within a program with certain desirable properties that make it highly amenable to analysis. Compilers usually decompose programs into their basic blocks as a first step in the analysis process...

s.

Automatic parallelization benefits from postdominance frontiers. This is an efficient method of computing control dependence, which is critical to the analysis.

Memory usage analysis can benefit from the dominator tree to easily find leaks and identify high memory usage (http://www.eclipse.org/mat/).

Algorithms

The dominators of a node n are given by the maximal solution to the following data-flow equations:

where is the start node.

The dominator of the start node is the start node itself. The set of dominators for any other node n is the intersection of the set of dominators for all predecessors p of n. The node n is also in the set of dominators for n.

An algorithm for direct solution is:

// dominator of the start node is the start itself
Dom(n₀) = {n₀}
// for all other nodes, set all nodes as the dominators
for each n in N - {n₀}
Dom(n) = N;
// iteratively eliminate nodes that are not dominators
while changes in any Dom(n)
for each n in N - {n₀}:
Dom(n) = {n} union with intersection over all p in pred(n) of Dom(p)

Direct solution is quadratic

Quadratic growth

In mathematics, a function or sequence is said to exhibit quadratic growth when its values are proportional to the square of the function argument or sequence position, in the limit as the argument or sequence position goes to infinity...

 in the number of nodes, or O(n²). Lengauer and Tarjan developed an algorithm which is almost linear, but its implementation tends to be complex and time consuming for a graph of several hundred nodes or fewer.

Keith D. Cooper, Timothy J. Harvey, and Ken Kennedy of Rice University

Rice University

William Marsh Rice University, commonly referred to as Rice University or Rice, is a private research university located on a heavily wooded campus in Houston, Texas, United States...

describe an algorithm that essentially solves the above data flow equations but uses well engineered data structures to improve performance.

Postdominance

Analogous to the definition of dominance above, a node z is said to post-dominate a node n if all paths to the exit node of the graph starting at n must go through z. Similarly, the immediate post-dominator of a node n is the postdominator of n that doesn't strictly postdominate any other strict postdominators of n.

External links

• The Machine-SUIF Control Flow Analysis Library