dominatorTreesAndDominanceFrontiers/DominatorTree.h

Go to the documentation of this file.

#ifndef _DOMINATORTREE_H_
#define _DOMINATORTREE_H_

#include "ControlFlowGraph.h"
#include <GraphDotOutput.h>
#include <map>

// DQ (12/30/2005): This is a Bad Bad thing to do (I can explain)
// it hides names in the global namespace and causes errors in 
// otherwise valid and useful code. Where it is needed it should
// appear only in *.C files (and only ones not included for template 
// instantiation reasons) else they effect user who use ROSE unexpectedly.
// using namespace std;

// DQ (3/21/2006): Namespace introduced to hide redundent use of 
// ControlFlowGraph class also found in:
//      src/midend/programTransformation/partialRedundancyElimination
namespace DominatorTreesAndDominanceFrontiers {

class DominatorTree {

public:

  enum Direction 
  {
    PRE,  
    POST  
  };

  DominatorTree(SgNode * head, Direction d = PRE);

  ControlFlowGraph * getCFG() {return _cfg;}
  Direction getDirection() {return _dir;}
  ControlFlowGraph::ID_dir getCFGDirection() {return _iddir;}
  int getSize() {return _size;}

  int getDom(ControlNode * node) {return doms[node->getID(_iddir)];}
  int getDom(int id) {return doms[id];}
                                          
  void printCFG();
  void printDominators();


private:

  void _buildCFG(SgNode * head);
  void _setupStructures();

  void _findDominators();
  int _intersect(int f1, int f2);
  bool _processNode(int i);

  ControlFlowGraph * _cfg;

  Direction _dir;

  ControlFlowGraph::ID_dir _iddir;

  int _size;

  int * doms;

};

// end of namespace: DominatorTreesAndDominanceFrontiers
 }
 
#endif