CSFIActivity/DUGStandard.hpp

Go to the documentation of this file.

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

#ifndef DUGStandard_H
#define DUGStandard_H

//--------------------------------------------------------------------
#define CONTEXT_SENSITIVITY
// #define DEBUG_DUAA
// #define DEBUG_PATH // to get a path for marking 'varied' or 'useful'

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

// OpenAnalysis headers
#include <OpenAnalysis/CallGraph/ManagerCallGraph.hpp>
#include <OpenAnalysis/Utils/OA_ptr.hpp>
#include <OpenAnalysis/Utils/DGraph/DGraphInterface.hpp>
#include <OpenAnalysis/CFG/CFG.hpp>
#include <OpenAnalysis/Location/Locations.hpp>
#include <OpenAnalysis/DataFlow/LocDFSet.hpp>
#include <OpenAnalysis/IRInterface/ActivityIRInterface.hpp>
#include <OpenAnalysis/IRInterface/DUGIRInterface.hpp>
#include <OpenAnalysis/CSFIActivity/DUGInterface.hpp>
#include <OpenAnalysis/Utils/DGraph/DGraphImplement.hpp>
#include <OpenAnalysis/Activity/ActiveStandard.hpp>
//--------------------------------------------------------------------


namespace OA {
  namespace DUG {
      
class Node;
class Edge;
class NodesIterator;
class EdgesIterator;
class DUGStandard;
 
//--------------------------------------------------------
class Node : public virtual NodeInterface {
public:
    Node (OA_ptr<DUGStandard> pDUG, ProcHandle proc, NodeType pType)
        : mDUG(pDUG), mProc(proc), mType(pType) { Ctor(); }
    Node (OA_ptr<DUGStandard> pDUG, ProcHandle proc, NodeType pType,
          OA_ptr<CFG::NodeInterface> cNode)
        : mDUG(pDUG), mProc(proc), mType(pType) { Ctor(); }
    Node (OA_ptr<DUGStandard> pDUG, ProcHandle pProc, SymHandle pSym)
        : mDUG(pDUG), mProc(pProc), mType(NONEFORMAL_NODE), mSym(pSym) 
        { Ctor(); }

    ~Node () { }
 
    //========================================================
    // Info specific to DUG
    //========================================================
    
    NodeType getType() const { return mType; }
    bool isFormalParamNode() { return mType == FORMALPARAM_NODE;}

    ProcHandle getProc() const { return mProc; }
    OA_ptr<Location> getLoc() const { return mLoc; }
    SymHandle getSym() const { return mSym; }
    
    void markVaried(std::list<CallHandle>&, 
                    OA_ptr<Activity::ActivityIRInterface>,
                    std::set<OA_ptr<EdgeInterface> >&,
                    std::set<std::pair<unsigned,unsigned> >&,
                    ProcHandle, unsigned,
                    OA_ptr<EdgeInterface>,
                    bool activeWithVariedOnly);
    void markUseful(std::list<CallHandle>&, 
                    OA_ptr<Activity::ActivityIRInterface>,
                    std::set<OA_ptr<EdgeInterface> >&,
                    std::set<std::pair<unsigned,unsigned> >&,
                    ProcHandle, unsigned,
                    OA_ptr<EdgeInterface>);

    bool isVaried(){ return mVaried;}
    void setVaried()
        {
            mVaried = true;
        }
    void unsetVaried()
        { 
            mVaried = false;
        }
    bool isVariedContext(CallHandle context) const { 
        return mVariedContexts.find(context) != mVariedContexts.end(); }
    void insertVariedContext(CallHandle context) { 
        mVariedContexts.insert(context); }

    bool isUseful(){ return mUseful;}
    void setUseful(){ mUseful = true;};
    void unsetUseful(){ mUseful = false;};

    void setActive();
    void setActive(SymHandle);

    bool isSelfDependent(){ return mSelfDependent;}
    void setSelfDependent(){ mSelfDependent = true;};

    bool isPathFrom(OA_ptr<NodeInterface>,
                    std::set<OA_ptr<NodeInterface> >&);
    bool hasEdgesToOtherProc(ProcHandle, std::set<SymHandle>&);
    bool hasEdgesFromOtherProc(ProcHandle, std::set<SymHandle>&);
    void findOutgoingNodes(ProcHandle, std::set<SymHandle>&, std::set<SymHandle>&);
//     void findIncomingNodes(ProcHandle, std::set<SymHandle>&, std::set<SymHandle>&);


    unsigned int size () const {
        assert(0);  //yet to be implemented PLM 09/19/06
        return 0; 
    }


    //========================================================
    // DGraph::Interface::Node interface
    //========================================================
    
    unsigned int getId() const 
        { 
            return mDGNode->getId();
            //return mId; 
        }
    
    int num_incoming () const { return mDGNode->num_incoming(); }
    
    int num_outgoing () const { return mDGNode->num_outgoing(); }

    bool isAnEntry() const { return mDGNode->isAnEntry(); }

    bool isAnExit() const { return mDGNode->isAnExit(); }

    bool operator==(DGraph::NodeInterface& other);
    bool operator<(DGraph::NodeInterface& other);
   
    //========================================================
    // Output
    //========================================================
    void dump(std::ostream& os) { }  // for full override
    void dumpbase(std::ostream& os) {}
    void dump(std::ostream& os, OA_ptr<IRHandlesIRInterface> ir);
    void dumpdot(std::ostream& os, OA_ptr<DUGIRInterface> ir);
    void longdump(std::ostream& os, OA_ptr<IRHandlesIRInterface> ir);
    void output(OA::IRHandlesIRInterface& ir) { 
        
        mDGNode->output(ir);

    }
    
public:
    //========================================================
    // These methods shadow the same named methods in
    // the DGraph::Interface class and allow us to return
    // the more specific subclass
    //========================================================
    OA_ptr<DGraph::EdgesIteratorInterface> getIncomingEdgesIterator() const;

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

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

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

    OA_ptr<EdgesIteratorInterface> getDUGIncomingEdgesIterator() const;

    OA_ptr<EdgesIteratorInterface> getDUGOutgoingEdgesIterator() const;

    OA_ptr<NodesIteratorInterface> getDUGSourceNodesIterator() const;

    OA_ptr<NodesIteratorInterface> getDUGSinkNodesIterator() const;

    //========================================================
    // Construction
    //========================================================
    void addIncomingEdge(OA_ptr<DGraph::EdgeInterface> e)
        {
            return mDGNode->addIncomingEdge(e);  
        }

    void addOutgoingEdge(OA_ptr<DGraph::EdgeInterface> e)
        {
            return mDGNode->addOutgoingEdge(e); 
        }

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

            return mDGNode->removeIncomingEdge(e); 
        }

    void removeOutgoingEdge(OA_ptr<DGraph::EdgeInterface> e)
        {
            return mDGNode->removeOutgoingEdge(e);
        }  

private:
    void Ctor();
   

    unsigned int mId;               // 0 is reserved; first instance is 1
    OA_ptr<DUGStandard> mDUG;       // enclosing DUG
    ProcHandle mProc;               // enclosing procedure
    NodeType mType;                 // node type

    OA_ptr<DGraph::NodeImplement> mDGNode;  // corresponding DGraph node
    // in DGraph that keeps 
    // structure

    OA_ptr<Location> mLoc;
    SymHandle mSym;                  // node key
    bool mVaried;                    // 'true' if varied
    bool mUseful;                    // 'true' if useful
    bool mSelfDependent;             // 'true' if the variable has a self dependence.
    // - for context sensitivity between 'varied' and 'useful' analyses
    // - For each actual parameter node, the contexts of RETURN edges along which
    //   'varied' analysis has propagated are stored.
    std::set<CallHandle> mVariedContexts; 
                                    
    friend class DUGStandard;
    friend class Edge;
};
  
 
 
 
//--------------------------------------------------------
class Edge : public virtual EdgeInterface {
public:
    Edge (OA_ptr<DUGStandard> pDUG,
          OA_ptr<Node> pNode1, OA_ptr<Node> pNode2, EdgeType pType,
          CallHandle call, ProcHandle p); 
    ~Edge () {}
    
    //========================================================
    // Info specific to DUG
    //========================================================
    
    EdgeType getType() const { return mType; }

    ProcHandle getSourceProc() const { return mNode1->getProc(); }
    ProcHandle getSinkProc() const { return mNode2->getProc(); }
    CallHandle getCall() const { return mCall; }
    ProcHandle getProc() const { return mProc; }

    // 090801: explore PARAM_EDGEs just once for each call context
    bool isExplored4Varied(CallHandle context) const { 
        return mExplored4Varied.find(context) != mExplored4Varied.end(); }
    void setExplored4Varied(CallHandle context) { 
        mExplored4Varied.insert(context); }
    bool isExplored4Useful(CallHandle context) const { 
        return mExplored4Useful.find(context) != mExplored4Useful.end(); }
    void setExplored4Useful(CallHandle context) { 
        mExplored4Useful.insert(context); }

    //========================================================
    // DGraph::Interface::Edge interface
    //========================================================
    
    unsigned int getId() const 
        {
            return mDGEdge->getId();
        }

    OA_ptr<DGraph::NodeInterface> getSource () const { return mNode1; }
    // FIXME: tail and head should be done like source and sink
    // in DGraph::Interface and here
    OA_ptr<DGraph::NodeInterface> tail () const { return mNode1; }
    
    OA_ptr<DGraph::NodeInterface> getSink () const { return mNode2; }
    OA_ptr<DGraph::NodeInterface> head () const { return mNode2; }

    OA_ptr<NodeInterface> getDUGSource() const
        {
            return getSource().convert<Node>();
        }

    OA_ptr<NodeInterface> getDUGSink() const
        {
            return getSink().convert<Node>();
        }


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

    void dump (std::ostream& os);
    void dumpdot (std::ostream& os, OA_ptr<DUGIRInterface> ir);
    void dumpdot_label (std::ostream& os, OA_ptr<DUGIRInterface> ir);
    void dumpbase (std::ostream& os) {}
    void output(OA::IRHandlesIRInterface& ir) { mDGEdge->output(ir); }

private:

    OA_ptr<DUGStandard> mDUG;
    OA_ptr<Node> mNode1, mNode2;
    OA_ptr<DGraph::EdgeImplement> mDGEdge;

    EdgeType mType;
    CallHandle mCall; // for CALL and RETURN edges
    unsigned int mId; // 0 is reserved; first instance is 1
    ProcHandle mProc; // proc where this edge is used

    friend class DUGStandard;
    friend class Node;

    // 090801: store visit information to remove exponential growth 
    //         in number of PARAM_EDGEs
    std::set<CallHandle> mExplored4Varied;  
    std::set<CallHandle> mExplored4Useful;  
}; 
  
//------------------------------------------------------------------
class NodesIterator : public DGraph::NodesIteratorImplement,
                      public virtual NodesIteratorInterface
{
public:
    NodesIterator(OA_ptr<DGraph::NodesIteratorInterface> ni) 
        : DGraph::NodesIteratorImplement(ni) { }

    ~NodesIterator () {}

    OA_ptr<NodeInterface> currentDUGNode() const ;

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

    ~EdgesIterator () {}

    OA_ptr<EdgeInterface> currentDUGEdge() const;

};
  

//------------------------------------------------------------------
class DUGStandard : public virtual DUGInterface  
{
public:

    friend class Node;  
    
    DUGStandard (
        OA_ptr<DUGIRInterface>,
        OA_ptr<DataFlow::ParamBindings>);
    virtual ~DUGStandard ();
  
    //-------------------------------------
    // DUG information access
    //-------------------------------------

    OA_ptr<Edge> getDUGEdge(OA_ptr<DGraph::EdgeInterface> dgEdge) const;

    OA_ptr<Node> getDUGNode(OA_ptr<DGraph::NodeInterface> dgNode) const;
  
    std::list<std::pair<SymHandle, ProcHandle> >& getIndepSyms(){
        return mIndepSymList;
    }
    std::list<std::pair<SymHandle, ProcHandle> >& getDepSyms(){
        return mDepSymList;
    }

    void insertIndepSymList(SymHandle sym, ProcHandle proc){
        mIndepSymList.push_back(std::pair<SymHandle, ProcHandle>(sym, proc));
        mIndepSymSet.insert(sym);
    }

    void insertDepSymList(SymHandle sym, ProcHandle proc){
        mDepSymList.push_back(std::pair<SymHandle, ProcHandle>(sym, proc));
        mDepSymSet.insert(sym);
    }

    void mapSymToProc(SymHandle sym, ProcHandle proc){
      
        mSymToProc[sym] = proc;
    }

    void insertActiveSymSet(SymHandle sym){
#ifdef DEBUG_DUAA
        std::cout << "DUGStandard::insertActiveSymSet:(sym: "; 
        std::cout << sym << " )" << std::endl;
#endif 
        mActiveSymSet->insert(sym);
    }

    std::map<ProcHandle,OA_ptr<OA::Activity::ActiveStandard> >& getActiveMap(){
        return mActiveMap;
    }

    OA_ptr<std::set<SymHandle> > getActiveSymSet(){
        return mActiveSymSet;
    }
    void insertActiveSymSet(OA_ptr<Location>);

    bool isIndependent(ProcHandle proc, SymHandle sym){
        if (mIndepSymSet.find(sym) != mIndepSymSet.end()) return true;

        OA_ptr<Location> loc = mIR->getLocation(proc, sym);
        if (loc.ptrEqual(0)) return false;
        OA_ptr<NamedLoc> nloc = loc.convert<NamedLoc>();
        OA_ptr<SymHandleIterator> symIter = nloc->getFullOverlapIter();
        for ( ; symIter->isValid(); (*symIter)++) {
            SymHandle temp = symIter->current();
            if (mIndepSymSet.find(temp) != mIndepSymSet.end()) return true;
        }
        return false;
    }

    bool isDependent(ProcHandle proc, SymHandle sym){
        if (mDepSymSet.find(sym) != mDepSymSet.end()) return true;

        OA_ptr<Location> loc = mIR->getLocation(proc, sym);
        if (loc.ptrEqual(0)) return false;
        OA_ptr<NamedLoc> nloc = loc.convert<NamedLoc>();
        OA_ptr<SymHandleIterator> symIter = nloc->getFullOverlapIter();
        for ( ; symIter->isValid(); (*symIter)++) {
            SymHandle temp = symIter->current();
            if (mDepSymSet.find(temp) != mDepSymSet.end()) return true;
        }
        return false;
    }

    bool isActive(SymHandle sym);

    bool isActive(StmtHandle stmt);

    bool isActive(MemRefHandle memref);

    void insertActiveStmtSet(StmtHandle stmt, ProcHandle proc){
        mActiveStmtSet->insert(stmt);
        mActiveMap[proc]->insertStmt(stmt);
    }


    void insertActiveMemRefSet(MemRefHandle mref, ProcHandle proc){
        mActiveMemRefSet->insert(mref);
        mActiveMap[proc]->insertMemRef(mref);
    }

    void assignActiveStandard(ProcHandle proc) {
    
        if (mActiveMap[proc].ptrEqual(0)) {
            mActiveMap[proc] = new OA::Activity::ActiveStandard(proc);
        }
    }
    
    //========================================================
    // Construction
    //========================================================
  
  
    void addNode(OA_ptr<DGraph::NodeInterface> pNode);
    void addEdge(OA_ptr<DGraph::EdgeInterface> pEdge);
  

    //========================================================
    // DGraph::Interface::Edge interface
    //========================================================
 
    int getNumNodes () { return mDGraph->getNumNodes(); }
    int getNumEdges () { return mDGraph->getNumEdges(); }

  
    // Output Functionalities 
    void dump (std::ostream& os, OA_ptr<IRHandlesIRInterface> ir);
    void dumpdot (std::ostream& os, OA_ptr<DUGIRInterface> ir);
    void dumpbase(std::ostream& os) {}
    void output(OA::IRHandlesIRInterface& ir) { mDGraph->output(ir); }

  
    //------------------------------------------------------------------
    // Using trick of imitating covariance when getting all iterators
    // so that get an iterator specific to actual subclass
    // This is why have these getBlahIterator methods that shadow those
    // in DGraph::Interface and also have the protected ones
    // that must be defined here which override implementation in 
    // DGraph::Interface
    //------------------------------------------------------------------
  
    OA_ptr<DGraph::NodesIteratorInterface> getNodesIterator() const;

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

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

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

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

    OA_ptr<DGraph::NodesIteratorInterface> getBFSIterator();

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

    OA_ptr<DGraph::NodesIteratorInterface>
    getReversePostDFSIterator(OA_ptr<DGraph::NodeInterface> root, 
                              DGraph::DGraphEdgeDirection pOrient);

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

    OA_ptr<DGraph::NodesIteratorInterface>
    getPostDFSIterator(OA_ptr<DGraph::NodeInterface> root, 
                       DGraph::DGraphEdgeDirection pOrient);


    //==================================================================
  
    OA_ptr<NodesIteratorInterface>
    getDUGNodesIterator() const;

    OA_ptr<EdgesIteratorInterface>
    getDUGEdgesIterator() const;

    OA_ptr<NodesIteratorInterface>
    getDUGEntryNodesIterator() const;

    OA_ptr<NodesIteratorInterface>
    getDUGExitNodesIterator() const;

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

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

    void mapSymToMemRefSet(SymHandle sym, MemRefHandle mref) {
        mSymToMemRefSet[sym].insert(mref);
    }

    void mapSymToStmtSet(SymHandle sym, StmtHandle stmt) {
        mSymToStmtSet[sym].insert(stmt);
    }

    std::set<MemRefHandle> getMemRefSet(SymHandle sym) {
        return mSymToMemRefSet[sym];
    }

    std::set<StmtHandle> getStmtSet(SymHandle sym) {
        return mSymToStmtSet[sym];
    }
 
    //==================================================================

    OA_ptr<Node> getNode(SymHandle, ProcHandle);
    bool isNode(SymHandle, ProcHandle);

private:
    OA_ptr<Node> mEntry; 
    OA_ptr<Node> mExit;

    // dgraph that will store underlying graph structure
    //  OA_ptr<DGraph::DGraphImplement> mDGraph;
  
    OA_ptr<DGraph::DGraphImplement> mDGraph;

    // using lists instead of sets because some of the iterators
    // need an ordered list of things and only want to have one
    // NodeIterator and EdgesIterator implementation
    OA_ptr<std::list<OA_ptr<Node> > > mCallNodes;
    OA_ptr<std::list<OA_ptr<Node> > > mReturnNodes;

    // map from SymHandle to Node
    std::map<SymHandle, OA_ptr<Node> > mSymToNode;

    // map from SymHandle to Location
    std::map<SymHandle, OA_ptr<Location> > mSymToLoc;
    std::map<SymHandle, ProcHandle> mSymToProc;

    // DUAA specific
    OA_ptr<DUGIRInterface>            mIR;
    //OA_ptr<IRHandlesIRInterface>      mIR;
    OA_ptr<DataFlow::ParamBindings>   mParamBind;


    std::list<std::pair<SymHandle, ProcHandle> > mIndepSymList;
    std::list<std::pair<SymHandle, ProcHandle> > mDepSymList;
    std::set<SymHandle>             mIndepSymSet;
    std::set<SymHandle>             mDepSymSet;

    OA_ptr<std::set<StmtHandle> > mActiveStmtSet;
    OA_ptr<std::set<MemRefHandle> > mActiveMemRefSet;
    OA_ptr<std::set<SymHandle> >    mActiveSymSet;
    std::map<ProcHandle,OA_ptr<OA::Activity::ActiveStandard> > mActiveMap;

    bool mUnknownLocActive;



    std::map<SymHandle, std::set<MemRefHandle> > mSymToMemRefSet;

    std::map<SymHandle, std::set<StmtHandle> > mSymToStmtSet;

    std::map<OA_ptr<Location>, OA_ptr<std::set<MemRefHandle> > > mLocToMemRefSet;

    std::map<OA_ptr<Location>, OA_ptr<std::set<StmtHandle> > > mLocToStmtSet;

};
//--------------------------------------------------------------------

  } // end of DUG namespace
} // end of OA namespace

#endif