CFG.hpp

Go to the documentation of this file.

#ifndef CFG_H
#define CFG_H

//--------------------------------------------------------------------
// standard headers
#ifdef NO_STD_CHEADERS
# include <string.h>
#else
# include <cstring>
#endif

// STL headers
#include <list>
#include <set>
#include <map>

// OpenAnalysis headers
#include <OpenAnalysis/Utils/OA_ptr.hpp>
#include <OpenAnalysis/Utils/DGraph/DGraphImplement.hpp>
#include <OpenAnalysis/IRInterface/CFGIRInterface.hpp>
#include <OpenAnalysis/CFG/CFGInterface.hpp>

namespace OA {
  namespace CFG {


//--------------------------------------------------------------------
//--------------------------------------------------------------------

  class Node;
  class Edge;
  class CFG;
  //------------------------------------------------------------------
  class NodeStatementsIterator;
  class NodeStatementsRevIterator;
  class NodesIterator;
  class EdgesIterator;

  //------------------------------------------------------------------
  class NodesIterator : 
                       public DGraph::NodesIteratorImplement, 
                       public virtual NodesIteratorInterface 
  {
     public:
        NodesIterator(OA_ptr<DGraph::NodesIteratorInterface> ni);
    
        OA_ptr<NodeInterface> currentCFGNode() const;
    
  };

  //------------------------------------------------------------------
  class EdgesIterator : 
                       public DGraph::EdgesIteratorImplement, 
                       public virtual EdgesIteratorInterface 
  {
     public:
        EdgesIterator(OA_ptr<DGraph::EdgesIteratorInterface> ni)
            : DGraph::EdgesIteratorImplement(ni) {}

        OA_ptr<EdgeInterface> currentCFGEdge() const;

  };
   
  //--------------------------------------------------------------------
  //--------------------------------------------------------------------
  class Node : public virtual NodeInterface, 
               public virtual DGraph::NodeImplement
  {
  public:
      
        Node();
        Node(StmtHandle n);
       ~Node();
    
       //=========================================================
       // Information
       //=========================================================
    
       //from DGraph::NodeImplement
   
        /*
        unsigned int getId() const;

        int num_incoming () const ; 
        int num_outgoing () const ;

        bool isAnEntry() const;

        bool isAnExit() const;
        */
        
        unsigned int size() const;

         bool empty() const;

        /* 
        //========================================================
        // Comparison operators
        //========================================================
        bool operator== (DGraph::NodeInterface& other);

        bool operator< (DGraph::NodeInterface& other);


        //========================================================
        // Construction
        //========================================================
        void addIncomingEdge(OA_ptr<DGraph::EdgeInterface> e);
        
        void addOutgoingEdge(OA_ptr<DGraph::EdgeInterface> e);

        void removeIncomingEdge(OA_ptr<DGraph::EdgeInterface> e);

        void removeOutgoingEdge(OA_ptr<DGraph::EdgeInterface> e);
        */

        void add(StmtHandle h);

        void add_front(StmtHandle h);

        StmtHandle erase(StmtHandle h); 

        void split(StmtHandle splitPoint, OA_ptr<Node> newBlock);

        //=======================================================
        // Output
        //=======================================================

        void dump(std::ostream& os);

        void dump(std::ostream& os, OA_ptr<IRHandlesIRInterface> ir);
       
       void dumpdot(CFG &currcfg, std::ostream& os, 
                 OA_ptr<IRHandlesIRInterface> ir);

       virtual void output(OA::IRHandlesIRInterface& ir);

       //================================================================
       // Iterators
       //================================================================ 
        
       friend class CFG;
       friend class NodeStatementsIterator;
       friend class NodeStatementsRevIterator;

       OA_ptr<NodeStatementsIteratorInterface> 
          getNodeStatementsIterator() const;

       OA_ptr<NodeStatementsRevIteratorInterface> 
        getNodeStatementsRevIterator()  const;

  
       /*
       OA_ptr<DGraph::EdgesIteratorInterface> 
           getIncomingEdgesIterator() const;

       OA_ptr<DGraph::EdgesIteratorInterface> 
           getOutgoingEdgesIterator() const;

       OA_ptr<DGraph::NodesIteratorInterface> 
           getSourceNodesIterator() const;

       OA_ptr<DGraph::NodesIteratorInterface> 
           getPredNodesIterator() const;

       OA_ptr<DGraph::NodesIteratorInterface> 
           getSinkNodesIterator() const;

       OA_ptr<DGraph::NodesIteratorInterface> 
           getSuccNodesIterator() const;
       */    

       OA_ptr<EdgesIteratorInterface> 
           getCFGIncomingEdgesIterator() const;


       OA_ptr<EdgesIteratorInterface> 
           getCFGOutgoingEdgesIterator() const;

       OA_ptr<NodesIteratorInterface> 
           getCFGSourceNodesIterator() const;

       OA_ptr<NodesIteratorInterface> 
           getCFGPredNodesIterator() const;

       OA_ptr<NodesIteratorInterface> 
           getCFGSinkNodesIterator() const;

       OA_ptr<NodesIteratorInterface> 
           getCFGSuccNodesIterator() const;

  protected:
       std::list<StmtHandle>::iterator getStmtListBegin ();
    
       std::list<StmtHandle>::iterator getStmtListEnd ();
    
       std::list<StmtHandle>::reverse_iterator getStmtListRBegin ();

       std::list<StmtHandle>::reverse_iterator getStmtListREnd ();


  private:
    
        void Ctor();
    
        // OA_ptr because want a reference to it in NodeStatementsIterator
        OA_ptr<std::list<StmtHandle> > mStmt_list;
    
        //std::list<StmtHandle> mStmt_list;
        ExprHandle mEnd;
    
        //DGraph::NodeImplement mdgNode;
 
  };

  //--------------------------------------------------------------------
  //--------------------------------------------------------------------
  class Edge : public virtual EdgeInterface,
               public virtual DGraph::EdgeImplement
  {
  public:
  
         Edge(OA_ptr<DGraph::NodeInterface> source,
             OA_ptr<DGraph::NodeInterface> sink, EdgeType _type, 
             OA::ExprHandle _expr);

         ~Edge();
    
         friend class CFG;

         //========================================================
         // Iterators
         //=======================================================

         /*

         OA_ptr<DGraph::NodeInterface> getSource() const;

         OA_ptr<DGraph::NodeInterface> getSink() const;
         */


         OA_ptr<NodeInterface> getCFGSource() const; 

         OA_ptr<NodeInterface> getCFGSink() const; 

         /*
         //========================================================
         // Comparison operators
         //========================================================

         bool operator== (DGraph::EdgeInterface& other);

         bool operator< (DGraph::EdgeInterface& other);
         */
         
         //=============================================================
         // Output   
         //==============================================================
         void dumpdot(std::ostream &os, OA_ptr<IRHandlesIRInterface> ir);

          void dump(std::ostream& os);
         //void dump () { dump(std::cout); }

         void output(IRHandlesIRInterface& ir);

         //=================================================================
         // Information
         //=================================================================

        // virtual unsigned int getId() const;
    
         EdgeType getType() const;


         ExprHandle getExpr() const;
    

         const char* edgeTypeToString(EdgeType et) const;


  protected:

         void setType(EdgeType type);

         void setExpr(ExprHandle expr);

    
  private:
         EdgeType mType;
         ExprHandle mExpr;
         static const char* sEdgeTypeToString[];
         //DGraph::EdgeImplement mdgEdge;
  };  

//-------------------------------------------------------------------
// CFG methods
//-------------------------------------------------------------------

class CFG : public virtual CFGInterface,
            public virtual DGraph::DGraphImplement  
{
public:
        CFG();
        ~CFG();

        //-------------------------------------
        // CFG information access
        //-------------------------------------
       OA_ptr<NodeInterface> getEntry() const;

       OA_ptr<NodeInterface> getExit() const;

       SymHandle getName() const;

       /*
       int getNumNodes();
       int getNumEdges();
       */
  

       //========================================================
       // Output
       //========================================================
       //void output(IRHandlesIRInterface& ir);
 
       void dump(std::ostream&, OA_ptr<IRHandlesIRInterface> ); 

       void dumpdot(std::ostream& os, OA_ptr<IRHandlesIRInterface> ir);

       //void output() const; 
  
       //-------------------------------------
       // Iterators
       // Calling functions from DGraphImplement.hpp
       //-------------------------------------
       

       /*
       OA_ptr<DGraph::NodesIteratorInterface> 
           getNodesIterator() const;

       OA_ptr<DGraph::EdgesIteratorInterface> 
           getEdgesIterator() const;

       OA_ptr<DGraph::NodesIteratorInterface> 
           getEntryNodesIterator() const;

       OA_ptr<DGraph::NodesIteratorInterface> 
           getExitNodesIterator() const;
  
       OA_ptr<DGraph::NodesIteratorInterface> 
           getReversePostDFSIterator(DGraph::DGraphEdgeDirection pOrient);

       OA_ptr<DGraph::NodesIteratorInterface> 
           getDFSIterator(OA_ptr<DGraph::NodeInterface> n);
       */    

       OA_ptr<NodesIteratorInterface> 
           getCFGNodesIterator() const;

       // method to get a more specific iterator
       OA_ptr<EdgesIteratorInterface>
           getCFGEdgesIterator() const;

       OA_ptr<NodesIteratorInterface>
           getCFGEntryNodesIterator() const;

       OA_ptr<NodesIteratorInterface>
           getCFGExitNodesIterator() const;

       OA_ptr<NodesIteratorInterface>
         getCFGReversePostDFSIterator(DGraph::DGraphEdgeDirection pOrient);

       OA_ptr<NodesIteratorInterface> 
           getCFGDFSIterator(OA_ptr<NodeInterface> n);

       
       /*
       //========================================================
       // Construction
       //========================================================
       void addNode(OA_ptr<DGraph::NodeInterface> n);
   
       void addEdge(OA_ptr<DGraph::EdgeInterface> e);

       void removeEdge(OA_ptr<DGraph::EdgeInterface> e)
       {

          mDG.removeEdge(e);
       }

      void removeNode(OA_ptr<DGraph::NodeInterface> n)
      {

        mDG.removeNode(n);
      }
      */
 
public: 
      //-------------------------------------
      // CFG building methods
      //-------------------------------------
      void setEntry(OA_ptr<Node> n);
      void setExit(OA_ptr<Node> n);

      OA_ptr<Node> splitBlock(OA_ptr<Node>, StmtHandle);

      OA_ptr<Edge> connect(OA_ptr<NodeInterface> src,
                       OA_ptr<NodeInterface> dst,
                       EdgeType type);

  
      OA_ptr<Edge> connect(OA_ptr<NodeInterface> src,
                       OA_ptr<NodeInterface> dst,
                       EdgeType type, ExprHandle expr) ;


      class NodeLabel;
      typedef std::list<NodeLabel> NodeLabelList;
      void connect(OA_ptr<NodeInterface>, NodeLabelList&);
      void connect(NodeLabelList&, OA_ptr<NodeInterface>);
     
      void disconnect(OA_ptr<EdgeInterface> e); 
      void disconnect(OA_ptr<NodeInterface> n);
  
      //-------------------------------------
      // CFG attaching labels to nodes
      //-------------------------------------
      OA_ptr<Node> node_from_label(OA::StmtLabel);
      OA_ptr<Node> getLabelBlock(StmtLabel lab); 
      void mapLabelToNode(OA::StmtLabel lab, OA_ptr<Node> n);
      bool isLabelMappedToNode(StmtLabel lab);

      // members for CFG
private:
      //static const char* sEdgeTypeToString[]; //moved to edge class
      SymHandle mName;
      OA_ptr<Node> mEntry;
      OA_ptr<Node> mExit;
      std::map<OA::StmtLabel, OA_ptr<Node> > mlabel_to_node_map;

//      DGraph::DGraphImplement mDG;

public: 

      class NodeLabelListIterator;
      friend class NodeLabelListIterator;
      /*----------------------------------------------------------------*//*-------------------------------------------------------------*/
      class NodeLabel {
        public:
          NodeLabel(OA_ptr<Node> _n, EdgeType _et, ExprHandle _eh = 0) :
                    mN(_n), mEh(_eh), mEt(_et) {}
          OA_ptr<Node> getNode();
          EdgeType getEdgeType();
          OA::ExprHandle getExpr();

        private:
          OA_ptr<Node> mN;
          OA::ExprHandle mEh;
          EdgeType mEt;
       };

       /*----------------------------------------------------------------*//*-------------------------------------------------------------*/
       class NodeLabelListIterator {
         public:
            NodeLabelListIterator(NodeLabelList& nl)  
               : mList(nl), mIter(mList.begin()) {}
           ~NodeLabelListIterator() {}
           void operator++();
           void operator++(int);
           bool isValid() const;
           NodeLabel current() const;
         private:
           NodeLabelList& mList;
           std::list<NodeLabel>::iterator mIter;
        };
};

 //--------------------------------------------------------------------
  //--------------------------------------------------------------------
  class NodeStatementsIterator : public virtual
      NodeStatementsIteratorInterface {
  public:
    NodeStatementsIterator(const Node& node)
        { mList = node.mStmt_list;
          mIter = mList->begin();
        }
    ~NodeStatementsIterator() {}
    void operator++();
    void operator++(int);
    bool isValid() const;
    StmtHandle current() const;
    void reset();
  private:
    OA_ptr<std::list<StmtHandle> > mList;
    std::list<StmtHandle>::iterator mIter;
  };

  //--------------------------------------------------------------------
  //--------------------------------------------------------------------
  class NodeStatementsRevIterator : public virtual
      NodeStatementsRevIteratorInterface {
  public:
    NodeStatementsRevIterator(const Node& node)
        { mList = node.mStmt_list;
          mRevIter = mList->rbegin();
        }
    ~NodeStatementsRevIterator() {}
    void operator++();
    void operator++(int);
    bool isValid() const;
    StmtHandle current() const;
    void reset();
  private:
    OA_ptr<std::list<StmtHandle> > mList;
    std::list<StmtHandle>::reverse_iterator mRevIter;
  };


  } // end of CFG namespace
} // end of OA namespace

#endif