\section{Dominator Analysis}
\label{sec-dominance-info}

\subsection{Class [[DominanceInfo]]}

Class [[DominanceInfo]] can compute and cache dominance information
about a CFG.  For each node $n$, it can produce:

\begin{itemize}
\item the immediate dominator of $n$;
\item the set of dominators of $n$; and
\item the dominance frontier of $n$.
\end{itemize}

It can analyze the CFG either in the forward or the reverse direction.
Forward analysis views each edge as oriented ``normally'', i.e., in the
direction of control flow, and it starts from the entry node.  Reverse
analysis views each edge as reversed, and it starts from the exit node.
By using the reverse graph, methods of [[DominanceInfo]] can produce
for each node $n$:

\begin{itemize}
\item the immediate postdominator of $n$;
\item the set of postdominators of $n$; and
\item the reverse dominance frontier of $n$.
\end{itemize}

Because only some of the possible information is needed in a typical
application, everything is computed on demand.  You call a
[[find_]]\ldots method to perform each analysis, then use other methods
to access the results.

<<class [[DominanceInfo]]>>=
class DominanceInfo {
  public:
    DominanceInfo(Cfg *graph);
    virtual ~DominanceInfo();

    Cfg *graph() const { return _graph; }

    // Perform control-flow analysis
    void find_dominators();
    void find_postdominators();
    void find_dom_frontier();
    void find_reverse_dom_frontier();

    // Access analysis results
    bool dominates(int n_dominator, int n_dominatee) const;
    bool dominates(CfgNode *dominator, CfgNode *dominatee) const;
    bool postdominates(int n_dominator, int n_dominatee) const;
    bool postdominates(CfgNode *dominator, CfgNode *dominatee) const;
    const NatSet *dominators(int n) const;
    const NatSet *dominators(CfgNode *n) const;
    const NatSet *postdominators(int n) const;
    const NatSet *postdominators(CfgNode *n) const;
    CfgNode *immed_dom(int n) const;
    CfgNode *immed_dom(CfgNode *n) const;
    CfgNode *immed_postdom(int n) const;
    CfgNode *immed_postdom(CfgNode *n) const;
    const NatSet *dom_frontier(int n) const;
    const NatSet *dom_frontier(CfgNode *n) const;
    const NatSet *reverse_dom_frontier(int n) const;
    const NatSet *reverse_dom_frontier(CfgNode *n) const;

    void print(FILE * = stdout) const;

<<[[DominanceInfo]] protected parts>>
};
@

When constructing a [[DominanceInfo]] object, supply a pointer to the
CFG to be analyzed.  To recover this underlying CFG, use method
[[graph]].

To see the state of a [[DominanceInfo]] object during debugging, use
the [[print]] method.  The information is indexed by the CFG node
numbers.  Use the [[print]] method of the CFG to learn more about the nodes.

The remaining [[DominanceInfo]] methods are for generating or accessing
analysis results.

Call [[find_dominators]] to compute the dominator relation in the
forward graph.  Then access this information through the following
methods.

\begin{center}
\begin{tabular}{p{.3\linewidth}@{\hspace*{2em}}p{.5\linewidth}}
[[immed_dom(]]$n$[[)]]		& Returns [[NULL]] if $n$ is the entry
				  node.  Otherwise, returns the
				  immediate dominator of node $n$, i.e.,
				  its parent in the dominator tree. \\
[[immed_dom(]]$i$[[)]]		& Returns [[immed_dom(]]$n_i$[[)]],
				  where $n_i$ is the node with number
				  $i$. \\
{\tt dominates($n1$, $n2$)}	& Returns [[true]] when node $n1$
				  dominates node $n2$. \\
{\tt dominates($i1$, $i2$)}	& Returns {\tt dominates($n_{i1}$, $n_{i2}$)},
				  where $n_{i1}$ ($n_{i2}$) is the node with
				  number $i1$ ($i2$). \\
[[dominators(]]$n$[[)]]		& Returns a set of node numbers
				  representing the dominators of node
				  $n$. \\
[[dominators(]]$i$[[)]]		& Returns [[dominators(]]$n_i$[[)]],
				  where $n_i$ is the node with number
				  $i$.
\end{tabular}
\end{center}

Call [[find_postdominators]] to compute the dominator relation in the
reverse graph.  The results are available through methods exactly
analogous to those just described:

\begin{center}
\begin{tabular}{p{.3\linewidth}@{\hspace*{2em}}p{.5\linewidth}}
[[immed_postdom(]]$n$[[)]]	& Returns [[NULL]] if $n$ is the exit
				  node.  Otherwise, returns the
				  immediate postdominator of node
				  $n$. \\
[[immed_postdom(]]$i$[[)]]	& Returns [[immed_postdom(]]$n_i$[[)]],
				  where $n_i$ is the node with number
				  $i$. \\
{\tt postdominates($n1$, $n2$)}	& Returns [[true]] when node $n1$
				  postdominates node $n2$. \\
{\tt postdominates($i1$, $i2$)}	& Returns {\tt postdominates($n_{i1}$, $n_{i2}$)},
				  where $n_{i1}$ ($n_{i2}$) is the node with
				  number $i1$ ($i2$). \\
[[postdominators(]]$n$[[)]]	& Returns a set of node numbers
				  representing the postdominators of node
				  $n$. \\
[[postdominators(]]$i$[[)]]	& Returns [[postdominators(]]$n_i$[[)]],
				  where $n_i$ is the node with number
				  $i$.
\end{tabular}
\end{center}

The [[find_dom_frontier]] and [[find_reverse_dom_frontier]] methods
compute the dominance frontiers and postdominance frontiers of each node
in the graph.  Access the results of the former through:

\begin{center}
\begin{tabular}{p{.3\linewidth}@{\hspace*{2em}}p{.5\linewidth}}
[[dom_frontier(]]$n$[[)]]	& Returns a set of node numbers
				  representing the dominance frontier of
				  node $n$ in the forward flow graph. \\
[[dom_frontier(]]$i$[[)]]	& Returns [[dom_frontier(]]$n_i$[[)]],
				  where $n_i$ is the node with number
				  $i$.
\end{tabular}
\end{center}

Access the results of calling [[find_reverse_dom_frontier]] through the
methods:

\begin{center}
\begin{tabular}{p{.3\linewidth}@{\hspace*{2em}}p{.5\linewidth}}
[[reverse_dom_frontier(]]$n$[[)]] & Returns a set of node numbers
				  representing the dominance frontier of
				  node $n$ in the reverse flow graph. \\
[[reverse_dom_frontier(]]$i$[[)]] & Returns
				  [[reverse_dom_frontier(]]$n_i$[[)]],
				  where $n_i$ is the node with number
				  $i$.
\end{tabular}
\end{center}


\subsection{Implementation}

For finding dominator sets, we use an iterative algorithm similar to
Algorithm 10.16 in Aho, Sethi, and Ullman \cite{bibdragon}.  In a future
release, we expect to switch to the algorithm of Lengauer and Tarjan
\cite{biblengauer}, which should be more efficient on most flow graphs.

The immediate dominator of a node $n$ is obtained by choosing the strict
dominator of $n$ whose dominator set differs from that of $n$ only by
removal of $n$.

We compute dominance frontiers using the algorithm of Cytron {\it et al}
\cite{bibcytron}.

The privy parts of class [[DominanceInfo]] include methods that
produce: dominator sets for each node, immediate dominators for each
node, and the dominance-frontier set for each node.  These methods each
take a flag indicating whether to operate on the forward or the reverse
graph ([[true]] means forward).

An instance of the class holds a pointer to the underlying CFG, as well
as pointers that are either [[NULL]] (before the corresponding analysis
has been performed) or point to an array of analysis results, with one
entry per CFG node, in order of the node number.

<<[[DominanceInfo]] protected parts>>=
  protected:
    NatSetDense *do_dominators(bool forward) const;
    CfgNode **do_immed_dominators(bool forward) const;
    void do_dom_frontiers(CfgNode *, bool forward);

  private:
    Cfg *_graph;

    NatSetDense *_doms;		// bit vector per node
    NatSetDense *_pdoms;	// bit vector per node
    CfgNode **_idom;		// node per node
    CfgNode **_ipdom;		// node per node
    NatSetDense *_df;		// bit vector per node
    NatSetDense *_rdf;		// bit vector per node
@



\subsection{Header file for module [[dom.h]]}

The [[DominanceInfo]] class is defined in module [[dom]], which has
the following header file.

<<dom.h>>=
/* file "cfa/dom.h" -- Dominance Analysis */

<<Machine-SUIF copyright>>

#ifndef CFA_DOM_H
#define CFA_DOM_H

#include <machine/copyright.h>

#ifndef SUPPRESS_PRAGMA_INTERFACE
#pragma interface "cfa/dom.h"
#endif

#include <machine/machine.h>
#include <cfg/cfg.h>

<<class [[DominanceInfo]]>>

#endif /* CFA_DOM_H */
@