\section{Utilities}
\label{sec-utilities}

This section lists a number of helper functions that don't fall into
the traditional class hierarchies.  These helper functions live in the
[[util.h]] header file.


\subsection{Enumeration}
\label{sec-enumeration-utilities}

\subsubsection{Depth-first walk}

The following utility walks a subgraph of the CFG in depth-first order,
performing a given action after all successors of a node have already
been visited.  It can walk either the forward or reverse graph.  Its
arguments are: the node at which to start; the graph orientation
([[true]] for forward); the set of nodes already visited; the node
action to be performed; and an optional flag that causes impossible edges
to be ignored.

<<node enumeration utilities>>=
extern void
    depth_first_walk(CfgNode *start, bool forward, NatSet *visited,
		     DepthFirstWalkAction&, bool not_impossible = false);
@

The action applied to each node in the walk is expressed using a
subclass of the following little class:

<<class [[DepthFirstWalkAction]]>>=
class DepthFirstWalkAction {
  public:
    virtual ~DepthFirstWalkAction() { }
    virtual void operator()(CfgNode*) { }
};
@

This class can be used as it is, if no action is needed at each node.
Otherwise you specialize it to perform whatever task is needed.  The
utility in the next section is implemented using a [[DepthFirstWalkAction]]
that accumulates a list of nodes in reverse postorder.


\subsubsection{Reverse postorder sequence}

The following class presents the nodes of a CFG in reverse
postorder \cite{bibmorgan}.

<<class [[CfgNodeListRpo]]>>=
class CfgNodeListRpo
{
  public:
    CfgNodeListRpo(Cfg *graph, bool forward = true);
    virtual ~CfgNodeListRpo();

    int size();
    CfgNodeHandle start();
    CfgNodeHandle end();

    void prepend(CfgNode*);
    void append(CfgNode*);
    void replace(CfgNodeHandle, CfgNode*);
    void insert_before(CfgNodeHandle, CfgNode*);
    void insert_after(CfgNodeHandle, CfgNode*);
    CfgNode* remove(CfgNodeHandle);

<<[[CfgNodeListRpo]] protected part>>
};
@

The interface of this class is exactly that of any other sequence in
Machine SUIF.  Its constructor takes a CFG and an optional boolean
indicator of graph orientation.  The constructor computes the node
sequence; you can inspect and even modify the sequence using the usual
set of sequence manipulation actions.  By default, or when its second
argument is [[true]], the constructor operates on the normal forward
graph; a [[false]] second argument causes it to use the reverse graph
instead.

Typically, you bind a reverse-postorder it to a local variable and use
the handle abstraction to scan it.  The sequence is automatically
reclaimed when the scope of the local variable ends.  For example:

{\small
\begin{verbatim}
    {
	CfgNodeListRpo rpo(the_cfg);
	for (CfgNodeHandle h = rpo.start(); h != rpo.end(); ++h) {
	    ...                 // use *h to access current node
	}
    }				// list rpo is reclaimed here
\end{verbatim}}

The implementation of class [[CfgNodeListRpo]] uses a C++ list of node
pointers:

<<[[CfgNodeListRpo]] protected part>>=
  protected:
    list<CfgNode*> nodes;
@



\subsection{Node Identification}

The [[cfg_node]] annotation connects a label symbol back to the
corresponding CFG node.  The following helper function uses that note to
return the node for a given label.

<<function [[label_cfg_node]]>>=
CfgNode *label_cfg_node(Sym *);
@

To reach the CFG node containing a given instruction, apply this function:

<<function [[get_parent_node]]>>=
CfgNode* get_parent_node(Instr*);
@

It returns the containing node, if there is one, or else [[NULL]].


\subsection{Node-Sequence Utilities}

Sometimes it is useful to inquire if a node [[pred]] precedes another
node in the CFG; [[has_pred]] provides this functionality.

<<node-sequence utilities>>=
extern bool has_pred(CfgNode *node, CfgNode *pred);
@


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

We declare module [[util]] with the following header file.

<<util.h>>=
/* file "cfg/util.h" -- Control Flow Graph Utilities */

<<Machine-SUIF copyright>>

#ifndef CFG_UTIL_H
#define CFG_UTIL_H

#include <machine/copyright.h>

#ifndef SUPPRESS_PRAGMA_INTERFACE
#pragma interface "cfg/util.h"
#endif

#include <machine/machine.h>

#include <cfg/cfg_ir.h>
#include <cfg/graph.h>

<<class [[DepthFirstWalkAction]]>>

<<node enumeration utilities>>

<<class [[CfgNodeListRpo]]>>

extern IdString k_cfg_node;

<<function [[label_cfg_node]]>>

<<function [[get_parent_node]]>>

<<node-sequence utilities>>

#endif /* CFG_UTIL_H */
@