dominatorTreesAndDominanceFrontiers/ControlFlowGraph.h

Go to the documentation of this file.

#ifndef _CONTROLFLOWGRAPH_H_
#define _CONTROLFLOWGRAPH_H_

#include "SimpleDirectedGraph.h"
#include "CFGImpl.h"
#include "GraphDotOutput.h"
#include "virtualCFG.h"

#include <map>
#include <queue>
#include <set>

// 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 ControlNode;

class ControlFlowGraph : public SimpleDirectedGraph {

public:

  enum ID_dir // NO_STRINGIFY
  {
    FORWARD,
    BACKWARD
  };

  ControlFlowGraph(SgNode * head);
  
  void createNode(CFGNodeImpl * node);

  int getSize() {return _numNodes;}

  ControlNode * getNode(int id, ID_dir dir) {return (dir == FORWARD)?_forIndex[id]:_backIndex[id];}

  void outputCFGImpl();

private:

  void _buildCFGImpl(SgNode * head);

  void _buildCFG();
  void _buildBranches(ControlNode * from, CFGNodeImpl * curr);
  void _setupIDs(ID_dir);

  virtual void _displayData(SimpleDirectedGraphNode * data, std::ostream & os);

  DefaultCFGImpl * _cfg;

  int _numNodes;
  ControlNode * _entry;
  ControlNode * _exit;

  std::map<CFGNodeImpl *, ControlNode *> _cfgnodemap;
  std::map<SgNode *, ControlNode *> _sgnodemap;
  
  ControlNode ** _forIndex;
  ControlNode ** _backIndex;
};

class ControlNode : public SimpleDirectedGraphNode {

public:

  enum Type // NO_STRINGIFY
  {
    SGNODE,
    EMPTY
  };

  ControlNode(SgNode * node = NULL) : _node(node) {
    if (_node)
      _type = SGNODE;
    else
      _type = EMPTY;
  }

  SgNode * getNode() {return _node;}
  Type getType() {return _type;}

  int getID(ControlFlowGraph::ID_dir dir) {
    if (dir == ControlFlowGraph::FORWARD) {
      return _forID;
    } else {
      return _backID;
    }
  }

  void setID(int id, ControlFlowGraph::ID_dir dir) {
    if (dir == ControlFlowGraph::FORWARD) {
      _forID = id;
    } else {
      _backID = id;
    }
  }

  virtual void writeOut(std::ostream & os) {
    char buf[sizeof(ControlNode *)*2 + 3];
    sprintf(buf, "%p", this);
    os << "(" << _forID << "/" << _backID << ": " << buf << ") ";
    if (_type == EMPTY) {
      os << "EMPTY";
    } else {
      char buf[sizeof(SgNode *) * 2 + 3];
      sprintf(buf, "%p", _node);
      os << buf << ":" << _node->sage_class_name() << " ";
      os << "[" << escapeString(_node->unparseToString()) << "]";
    }
  }

private:

  SgNode * _node;
  Type _type;

  int _forID;
  int _backID;

};

// end of namespace: DominatorTreesAndDominanceFrontiers
 }
 
#endif