#include <DomTree.hpp>

Inheritance diagram for OA::DomTree:

Collaboration diagram for OA::DomTree:

Classes
class	DomFrontIterator

class	Node

Public Member Functions
	DomTree (OA_ptr< DGraph::DGraphInterface > graph)

	~DomTree ()

OA_ptr< Node >	domtree_node (OA_ptr< DGraph::NodeInterface > n)

void	compute_dominance_frontiers ()

void	dump (std::ostream &os)

Public Member Functions inherited from OA::Tree
	Tree ()

	Tree (OA_ptr< Node > root)

virtual	~Tree ()

OA_ptr< Node >	getRoot ()

void	addEdge (OA_ptr< Edge >) throw (DuplicateEdge, EdgeInUse, EmptyEdge, SecondParent, EmptyEndPoint)

void	addNode (OA_ptr< Node >) throw (DuplicateNode, NodeInUse, EmptyNode)

void	add_empty_edge (OA_ptr< Node >) throw (EmptyNode)

void	removeEdge (OA_ptr< Edge >) throw (NonexistentEdge, EmptyEdge)

void	removeNode (OA_ptr< Node >) throw (NonexistentNode, DeletingRootOfNonSingletonTree, EmptyNode)

virtual void	output (IRHandlesIRInterface &ir)

OA_ptr< NodesIterator >	getNodesIterator () const

OA_ptr< EdgesIterator >	getEdgesIterator () const

OA_ptr< PreOrderIterator >	getPreOrderIterator ()

OA_ptr< PostOrderIterator >	getPostOrderIterator ()

OA_ptr< ReversePostOrderIterator >	getReversePostOrderIterator () const

Public Member Functions inherited from OA::Annotation
	Annotation ()

virtual	~Annotation ()

Private Attributes
OA_ptr< DGraph::DGraphInterface >	graph

std::map< OA_ptr < DGraph::NodeInterface > , OA_ptr< Node > >	dom_tree_node

Additional Inherited Members
Static Public Member Functions inherited from OA::Annotation
static void	configOutput (OA_ptr< OutputBuilder > ob)

Protected Attributes inherited from OA::Tree
OA_ptr< Node >	root_node

OA_ptr< Node >	mPostOrderStart

OA_ptr< std::set< OA_ptr< Edge > > >	edge_set

OA_ptr< std::set< OA_ptr< Node > > >	node_set

bool	preorder_needed

bool	postorder_needed

bool	rpostorder_needed

Static Protected Attributes inherited from OA::Annotation
static OA_ptr< OutputBuilder >	sOutBuild

Detailed Description

Definition at line 40 of file DomTree.hpp.

Constructor & Destructor Documentation

OA::DomTree::DomTree ( OA_ptr< DGraph::DGraphInterface > graph_)

Construct the dominator tree for the given directed graph. This is (currently) done in the most straight-forward manner by iteratively solving data-flow equations for dominator sets. While this dataflow framework is guaranteed rapid convergence, perhaps, a better (but more complicated) algorithm to implement would be Lengauer-Tarjan's that appears in "A Fast Algorithm for Finding Dominators in a Flowgraph", ACM Transactions on Programming Languages and Systems, Vol. 1, No. 1, July 1979, pages 121-141.

FIXME: Use RIFG instead of computing node ids in first step

Definition at line 50 of file DomTree.cpp.

References OA::Tree::addEdge(), OA::Tree::addNode(), dom_tree_node, end, OA::DGraph::DGraphInterface::getDFSIterator(), OA::DGraph::DGraphInterface::getNumNodes(), graph, OA::n, and val.

Here is the call graph for this function:

OA::DomTree::~DomTree ( )

inline

Definition at line 102 of file DomTree.hpp.

Member Function Documentation

void OA::DomTree::compute_dominance_frontiers ( )

Dominance frontier for the dominator tree is computed simply by looking at each branch point in the directed graph (a node that has more than one predecessor) and adding such a node to the dominance frontier of the chain of immediate dominators of each of its predecessors terminating at the node's immediate dominator. The function uses the following algorithm, from the book "Engineering a Compiler", by Keith D. Cooper and Linda Torczon, chapter "Data-flow Analysis".

for all nodes b
  if the number of predecessors of b > 1
      for all predecessors, p, of b
          runner <– p
             while runner != IMMEDIATE_DOMINATOR(b)
                   add b to DOMINANCE_FRONTIER(runner)
                   runner = IMMEDIATE_DOMINATOR(runner)

Definition at line 158 of file DomTree.cpp.

References OA::DomTree::Node::dom_front, dom_tree_node, OA::DGraph::DGraphInterface::getNodesIterator(), OA::DGraph::NodeInterface::getSourceNodesIterator(), graph, OA::DomTree::Node::graph_node_ptr, OA::n, OA::DGraph::NodeInterface::num_incoming(), and OA::DomTree::Node::parent().

Referenced by OA::SSA::SSAStandard::SSAStandard().

Here is the call graph for this function: