#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)
Private Attributes
OA_ptr< DGraph::DGraphInterface >	graph
std::map< OA_ptr < DGraph::NodeInterface > , OA_ptr< Node > >	dom_tree_node

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, graph, and OA::n.

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 dom_tree_node, graph, and OA::n.

OA_ptr<Node> OA::DomTree::domtree_node ( OA_ptr< DGraph::NodeInterface > n ) [inline]