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