DUGStandard.cpp

Go to the documentation of this file.

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

// standard headers

#include <string.h>
#include <stdlib.h>
#include <iostream>
using std::ostream;
using std::endl;
using std::cout;
using std::cerr;

#include "DUGStandard.hpp"

namespace OA {
 namespace DUG {

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

//--------------------------------------------------------------------
// must be updated any time DUG::Interface::EdgeType changes
static const char *sEdgeTypeToString[] = { 
 "F",
 "C",
 "R",
 "P"
// "CFLOW",
// "CALL",
// "RETURN",
// "PARAM"
};
static const char *sNodeTypeToString[] = { 
 "FORMALPARAM_NODE",
 "NONEFORMAL_NODE",
};

//--------------------------------------------------------------------
void Node::Ctor() { 

 mDGNode = new DGraph::NodeImplement;

 mVaried = false;
 mUseful = false;
 mSelfDependent = false;
#ifdef DEBUG_DUAA
 static unsigned nodeCnt=0;
 nodeCnt++;
 std::cout << "getId(" << getId() << ")" << std::endl;
 std::cout << "nodeCnt(" << nodeCnt << ")" << std::endl;
#endif
}


OA_ptr<EdgeInterface> EdgesIterator::currentDUGEdge() const
{
 return current().convert<Edge>();
}



OA_ptr<NodeInterface> NodesIterator::currentDUGNode() const
{
 return current().convert<Node>();
}




//--------------------------------------------------------------------
void
Node::dump (ostream& os, OA_ptr<IRHandlesIRInterface> ir)
{
 os << sNodeTypeToString[mType] << std::endl;
}

bool Node::operator==(DGraph::NodeInterface& other) 
{
 
 return mDGNode->operator==(other);
}

bool Node::operator<(DGraph::NodeInterface& other) 
{
 return mDGNode->operator<(other);
}



void
Node::longdump (ostream& os, OA_ptr<IRHandlesIRInterface> ir)
{
 // print the node ID
 os << "DUGStandard Node: ";
 dump(os,ir);
 
 if (isAnEntry()) {
 os << " (ENTRY)";
 } else if (isAnExit()) {
 os << " (EXIT)"; 
 }
 os << endl;
 
 // print the source(s)
 unsigned int count = 0;
 OA_ptr<NodesIteratorInterface> srcIter = getDUGSourceNodesIterator();
 for ( ; srcIter->isValid(); ++(*srcIter), ++count) {
 OA_ptr<NodeInterface> node = srcIter->currentDUGNode();
 if (count == 0) { os << " <-- ("; }
 else { os << ", "; }

 node->dump(os,ir);
 }
 if (count > 0) { os << ")" << endl; }
 
 // print the sink(s)
 count = 0;
 OA_ptr<NodesIteratorInterface> outIter = getDUGSinkNodesIterator();
 for ( ; outIter->isValid(); ++(*outIter), ++count) {
 OA_ptr<NodeInterface> node = outIter->currentDUGNode();
 if (count == 0) { os << " --> ("; } 
 else { os << ", "; }
 
 node->dump(os,ir);
 }
 if (count > 0) { os << ")" << endl; }
}

void
Node::dumpdot (ostream& os, OA_ptr<DUGIRInterface> ir)
{
 SymHandle sym = getSym();
 IRHandle ih = getDef(); 
 std::string str = ir->toString(sym);

 char buf1[20], buf2[20];
 sprintf(buf1, "(%u)\\n", getId());
 sprintf(buf2, "@%u", ih.hval());

 std::string::size_type loc = str.find( "::", 0);
 if( loc != std::string::npos ) str.erase(loc, 2);

 str.insert(loc, std::string(buf1));
 str.append(std::string(buf2));

 OA_ptr<Location> memLoc = mDUG->mIR->getLocation(mProc, sym);
 if (memLoc.ptrEqual(0)){
#ifdef DEBUG_DUAA
 std::cout << "^^^^^ NULL LOCATION ^^^^^" << std::endl;
 std::cout << "\tmProc(" << mDUG->mIR->toString(mProc);
 std::cout << "), sym(" << mDUG->mIR->toString(sym) 
 << ")" << std::endl;
 if (mDef == IRHandle(0) || mDef == IRHandle(1) || mDef == IRHandle(2))
 std::cout << "stmt(012)" << std::endl;
 else
 std::cout << "stmt(" << mDUG->mIR->toString((StmtHandle)mDef)
 << ")" << std::endl;
#endif
 }
 else if (!memLoc->isLocal()) {
 str.erase(0, loc);
 str.insert(0, std::string("JWGLOBAL"));
 }

 os << "\"" << str << "\"";
}

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

OA_ptr<DGraph::EdgesIteratorInterface> 
Node::getIncomingEdgesIterator() const
{
 return mDGNode->getIncomingEdgesIterator();
}

OA_ptr<DGraph::EdgesIteratorInterface> 
Node::getOutgoingEdgesIterator() const
{
 return mDGNode->getOutgoingEdgesIterator();
}

OA_ptr<DGraph::NodesIteratorInterface> 
Node::getSourceNodesIterator() const
{
 return mDGNode->getSourceNodesIterator();
}

OA_ptr<DGraph::NodesIteratorInterface> 
Node::getSinkNodesIterator() const
{
 return mDGNode->getSourceNodesIterator();
}

OA_ptr<EdgesIteratorInterface>
Node::getDUGIncomingEdgesIterator() const
{
 OA_ptr<EdgesIterator> retval;
 retval = new EdgesIterator(getIncomingEdgesIterator());
 return retval;

}

OA_ptr<EdgesIteratorInterface>
Node::getDUGOutgoingEdgesIterator() const
{
 OA_ptr<EdgesIterator> retval;
 retval = new EdgesIterator(getOutgoingEdgesIterator());
 return retval;

}

OA_ptr<NodesIteratorInterface>
Node::getDUGSourceNodesIterator() const
{
 OA_ptr<NodesIterator> retval;
 retval = new NodesIterator(getSourceNodesIterator());
 return retval;

}

OA_ptr<NodesIteratorInterface>
Node::getDUGSinkNodesIterator() const
{
 OA_ptr<NodesIterator> retval;
 retval = new NodesIterator(getSinkNodesIterator());
 return retval;

}



//--------------------------------------------------------------------
//--------------------------------------------------------------------
Edge::Edge (OA_ptr<DUGStandard> pDUG,
 OA_ptr<Node> pNode1, 
 OA_ptr<Node> pNode2, 
 EdgeType pType, CallHandle call,
 ProcHandle proc)
 : mDUG(pDUG), mNode1(pNode1), mNode2(pNode2), mType(pType), 
 mCall(call), mProc(proc)
{

 // create DGraphEdge for associated DGraph
 mDGEdge = new DGraph::EdgeImplement(pNode1->mDGNode,
 pNode2->mDGNode);

}


//--------------------------------------------------------------------
bool Edge::operator==(DGraph::EdgeInterface& other) 
{
 
 return mDGEdge->operator==(other);
}

bool Edge::operator<(DGraph::EdgeInterface& other) 
{
 return mDGEdge->operator<(other);
}



void Edge::dump(ostream& os)
{
 os << sEdgeTypeToString[mType];
}

void filterStr(std::string& s)
{
 std::string::size_type loc = s.find( "::", 0);
 if( loc != std::string::npos ) s.erase(0, loc+2);
}


void Edge::dumpdot(ostream& os, OA_ptr<DUGIRInterface> ir)
{
 OA_ptr<NodeInterface> srcNode = getDUGSource();
 OA_ptr<NodeInterface> sinkNode = getDUGSink();

 srcNode->dumpdot(os, ir);
 os << "->";
 sinkNode->dumpdot(os, ir);
 dumpdot_label(os, ir);
}



void Edge::dumpdot_label(ostream& os, OA_ptr<DUGIRInterface> ir)
{
 CallHandle call = getCall();
 EdgeType etype = getType();
 os << "[label=\"" << sEdgeTypeToString[etype];
 if (call != CallHandle(0)) os << "(" << call.hval() << ")";
 os << "\\n";

 ProcHandle proc = getProc();
 std::string procStr = ir->toString(proc);
 filterStr(procStr);
 os << procStr;

 if (call != CallHandle(0)){
 if (etype == CALL_EDGE)
 os << "\\n-> ";
 else{
 assert(etype == RETURN_EDGE);
 os << "\\n<- ";
 }
 SymHandle calleeSym = ir->getSymHandle(call);
 procStr = ir->toString(calleeSym);
 filterStr(procStr);
 os << procStr;
 os << "\", style=dashed];" << endl;
 }
 else
 os << "\"];" << endl;
}


//--------------------------------------------------------------------
//--------------------------------------------------------------------
DUGStandard::DUGStandard(
 OA_ptr<DUGIRInterface> pIR,
 OA_ptr<DataFlow::ParamBindings> pParamBind)
 : mIR(pIR), mParamBind(pParamBind)
{
 mEntry = mExit = NULL;
 mDGraph = new DGraph::DGraphImplement;
 mCallNodes = new std::list<OA_ptr<Node> >;
 mReturnNodes = new std::list<OA_ptr<Node> >;
 mActiveSymSet = new std::set<SymHandle>;
 mActiveMemRefSet = new std::set<MemRefHandle>;
 mActiveStmtSet = new std::set<StmtHandle>;
 mUnknownLocActive = false;
}


DUGStandard::~DUGStandard()
{
 mEntry = NULL;
 mExit = NULL;
}

//--------------------------------------------------------------------
// DUGStandard Methods
//--------------------------------------------------------------------

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

 
 assert (0); 
 OA_ptr<Edge> retval;
 return retval;
}

OA_ptr<Node> 
DUGStandard::getDUGNode(
 const OA_ptr<DGraph::NodeInterface> dgNode) const
{
 assert(0); 
 OA_ptr<Node> retval;
 return retval; 
}

void DUGStandard::addEdge(OA_ptr<DGraph::EdgeInterface> pEdge)
{
 mDGraph->addEdge(pEdge);
}

void DUGStandard::addNode(OA_ptr<DGraph::NodeInterface> pNode)
{
 
 mDGraph->addNode(pNode);
}


OA_ptr<DGraph::NodesIteratorInterface> DUGStandard::getNodesIterator() const
{
 return mDGraph->getNodesIterator();
}

OA_ptr<DGraph::NodesIteratorInterface>
DUGStandard::getEntryNodesIterator( ) const
{
 
 return mDGraph->getEntryNodesIterator();
}

OA_ptr<DGraph::NodesIteratorInterface>
DUGStandard::getExitNodesIterator( ) const
{
 return mDGraph->getExitNodesIterator();
}


OA_ptr<DGraph::EdgesIteratorInterface> DUGStandard::getEdgesIterator() const
{
 
 return mDGraph->getEdgesIterator();
}

OA_ptr<DGraph::NodesIteratorInterface> DUGStandard::getDFSIterator(OA_ptr<DGraph::NodeInterface> n) 
{
 
 
 return mDGraph->getDFSIterator(n);
}

OA_ptr<DGraph::NodesIteratorInterface> DUGStandard::getBFSIterator() 
{ 
 assert(0); 
 OA_ptr<DGraph::NodesIteratorInterface> retval; 
 return retval;
}


OA_ptr<DGraph::NodesIteratorInterface>
DUGStandard::getReversePostDFSIterator( DGraph::DGraphEdgeDirection pOrient)
{
 return mDGraph->getReversePostDFSIterator(pOrient);
}

OA_ptr<DGraph::NodesIteratorInterface>
DUGStandard::getReversePostDFSIterator(OA_ptr<DGraph::NodeInterface> root, 
 DGraph::DGraphEdgeDirection pOrient)
{
 assert(0);
}

OA_ptr<DGraph::NodesIteratorInterface> 
DUGStandard::getPostDFSIterator(DGraph::DGraphEdgeDirection pOrient)
{
 assert(0);
}

OA_ptr<DGraph::NodesIteratorInterface>
DUGStandard::getPostDFSIterator(OA_ptr<DGraph::NodeInterface> root, 
 DGraph::DGraphEdgeDirection pOrient)
{
 assert(0);
}


OA_ptr<NodesIteratorInterface> DUGStandard::getDUGNodesIterator() const
{
 OA_ptr<NodesIterator> retval;
 retval = new NodesIterator(getNodesIterator());
 return retval;

}


OA_ptr<NodesIteratorInterface>
DUGStandard::getDUGEntryNodesIterator( ) const
{
 OA_ptr<NodesIterator> retval;
 retval = new NodesIterator(getEntryNodesIterator());
 return retval;


}

OA_ptr<NodesIteratorInterface>
DUGStandard::getDUGExitNodesIterator( ) const
{
 OA_ptr<NodesIterator> retval;
 retval = new NodesIterator(getExitNodesIterator());
 return retval;


}

OA_ptr<EdgesIteratorInterface> DUGStandard::getDUGEdgesIterator() const
{
 OA_ptr<EdgesIterator> retval;
 retval = new EdgesIterator(getEdgesIterator());
 return retval;


}


OA_ptr<NodesIteratorInterface>
DUGStandard::getDUGReversePostDFSIterator( DGraph::DGraphEdgeDirection pOrient)
{
 OA_ptr<NodesIterator> retval;
 retval = new NodesIterator(getReversePostDFSIterator(pOrient));
 return retval;
}

OA_ptr<NodesIteratorInterface>
DUGStandard::getDUGDFSIterator(OA_ptr<NodeInterface> n)
{
 OA_ptr<NodesIterator> retval;
 retval = new NodesIterator(getDFSIterator(n));
 return retval;


}

void
DUGStandard::dump (ostream& os, OA_ptr<IRHandlesIRInterface> ir)
{
 os << "===== DUGStandard: =====\n"
 << endl;
 
 // print the contents of all the nodes
 OA_ptr<NodesIteratorInterface> nodeIter = getDUGNodesIterator();
 for ( ; nodeIter->isValid(); ++(*nodeIter)) {
 OA_ptr<NodeInterface> node = nodeIter->currentDUGNode();
 node->longdump(os, ir);
 os << endl;
 }
 
 os << "====================" << endl;

}



void
DUGStandard::dumpdot(ostream& os, OA_ptr<DUGIRInterface> ir)
{

 os << "digraph OA_DUG {" << endl;
 os << "node [shape=rectangle];" << endl;

 // then output nodes and edges by procedure
 OA_ptr<EdgesIteratorInterface> iter;
 iter = getDUGEdgesIterator();
 for (; iter->isValid(); (*iter)++ ) {
 OA_ptr<EdgeInterface> edge = iter->currentDUGEdge();
 edge->dumpdot(os, ir);
 }

 os << "}" << endl;
 os.flush();
}

OA_ptr<Node> 
DUGStandard::getNode(IRSymHandle ish, ProcHandle proc){
 
 IRHandle ih = ish.first;
 SymHandle sym = ish.second;
 assert(sym);
#ifdef DEBUG_DUAA
 std::cout << "getNode: " << mIR->toString(sym) << "("
 << sym.hval() << ")@" << mIR->toString(proc) << "("
 << proc.hval() << ") --- ";
#endif
 IRSymHandle key(ih, sym);

 OA_ptr<Node> retval = mSymToNode[key];
 if (!retval.ptrEqual(0)) {
#ifdef DEBUG_DUAA
 std::cout << "found itself" << std::endl;
#endif
 return retval;
 }
 OA_ptr<Location> loc = mIR->getLocation(proc, sym);
 assert (!loc.ptrEqual(0));
 OA_ptr<NamedLoc> nloc = loc.convert<NamedLoc>();
 OA_ptr<SymHandleIterator> symIter = nloc->getFullOverlapIter();
 for ( ; symIter->isValid(); (*symIter)++) {
 retval = mSymToNode[IRSymHandle(ih,symIter->current())];
 if (!retval.ptrEqual(0)) {
#ifdef DEBUG_DUAA
 std::cout << "found FullOverlap" << std::endl;
#endif
 return retval;
 }
 }
#if 0
 symIter = nloc->getPartOverlapIter();
 for ( ; symIter->isValid(); (*symIter)++) {
 retval = mSymToNode[IRSymHandle(ih,symIter->current())];
 if (!retval.ptrEqual(0)) {
#ifdef DEBUG_DUAA
 std::cout << "found PartOverlap" << std::endl;
#endif
 return retval;
 }
 }
#endif

 assert (retval.ptrEqual(0));
 OA_ptr<DUGStandard> temp; temp = this;
 retval = new Node(temp, proc, ih, sym);
 assert(!retval.ptrEqual(0));
 mSymToNode[key] = retval;
 addNode(retval);
#ifdef DEBUG_DUAA
 std::cout << "added" << std::endl;
#endif
 if (isIndependent(proc, sym) || isDependent(proc, sym))
 mInDepSymToNodes[sym].insert(retval);

 return retval;
}

// true if a node exists for 'loc'
bool
DUGStandard::isNode(IRSymHandle ish, ProcHandle proc){
 IRHandle ih = ish.first;
 SymHandle sym = ish.second;
 assert(sym);
#ifdef DEBUG_DUAA
 std::cout << "isNode: " << mIR->toString(sym) << "("
 << sym.hval() << ")@" << mIR->toString(proc) << "("
 << proc.hval() << ") --- ";
#endif
 std::pair<IRHandle, SymHandle> key(ih, sym);
 OA_ptr<Node> retval = mSymToNode[key];

 if (!retval.ptrEqual(0)) {
#ifdef DEBUG_DUAA
 std::cout << "found itself" << std::endl;
#endif
 return true;
 }

 OA_ptr<Location> loc = mIR->getLocation(proc, sym);
 if (loc.ptrEqual(0)) {
#ifdef DEBUG_DUAA
 std::cout << "NULL location" << std::endl;
#endif
 return false;
 }
 OA_ptr<NamedLoc> nloc = loc.convert<NamedLoc>();
 OA_ptr<SymHandleIterator> symIter = nloc->getFullOverlapIter();
 for ( ; symIter->isValid(); (*symIter)++) {
 retval = mSymToNode[IRSymHandle(ih,symIter->current())];
 if (!retval.ptrEqual(0)) {
#ifdef DEBUG_DUAA
 std::cout << "found FullOverlap" << std::endl;
#endif
 return true;
 }
 }
#if 0
 symIter = nloc->getPartOverlapIter();
 for ( ; symIter->isValid(); (*symIter)++) {
 retval = mSymToNode[IRSymHandle(ih,symIter->current())];
 if (!retval.ptrEqual(0)) {
#ifdef DEBUG_DUAA
 std::cout << "found PartOverlap" << std::endl;
#endif
 return true;
 }
 }
#endif
#ifdef DEBUG_DUAA
 std::cout << "not found" << std::endl;
#endif
 return false;
}

void 
DUGStandard::insertActiveSymSet(OA_ptr<Location> loc)
{
 // Unknown
 if (loc->isaUnknown()) {

 mUnknownLocActive = true;

 // Named
 } else if (loc->isaNamed()) {
 
 OA_ptr<NamedLoc> nloc = loc.convert<NamedLoc>();
#ifdef DEBUG_DUAA
 std::cout << "DUGStandard::insertActiveSymSet:(loc)"; 
 loc->dump(std::cout, mIR);
 std::cout << std::endl;
#endif 
 insertActiveSymSet( nloc->getSymHandle() );

 OA_ptr<SymHandleIterator> symIter = nloc->getFullOverlapIter();
 for ( ; symIter->isValid(); (*symIter)++) {
#ifdef DEBUG_DUAA
 std::cout << "\tFullOverlap: " << mIR->toString(symIter->current()); 
 std::cout << std::endl;
#endif 
 insertActiveSymSet( symIter->current());
 }
 symIter = nloc->getPartOverlapIter();
 for ( ; symIter->isValid(); (*symIter)++) {
#ifdef DEBUG_DUAA
 std::cout << "\tPartialOverlap: "; 
 std::cout << std::endl;
#endif 
 insertActiveSymSet(symIter->current());
 }
 
 // Unnamed
 } else if (loc->isaUnnamed()) {
 
 //assert(0);
 // not handling this yet

 // Invisible
 } else if (loc->isaInvisible()) {

 OA_ptr<InvisibleLoc> invLoc 
 = loc.convert<InvisibleLoc>();
 OA_ptr<MemRefExpr> mre = invLoc->getMemRefExpr();

 // get symbol from memory reference expression if no derefs
 // FIXME: here need another visitor for MemRefExpr, for now assuming
 // only named ones
 if (mre->isaNamed()) {
 OA_ptr<NamedRef> namedRef 
 = namedRef.convert<NamedRef>();
 insertActiveSymSet( namedRef->getSymHandle() );
 } else {
 assert(0);
 }

 // LocSubSet
 } else if (loc->isaSubSet()) {

 OA_ptr<Location> baseLoc = loc->getBaseLoc();
 // FIXME: now really want to call visitor on this guy but instead will just
 // call this function recursively
 insertActiveSymSet(baseLoc);

 } else {

 assert(0);
 }
}


void 
Node::setActive(SymHandle sym)
{
 assert(mProc);
 // will be storing activity results for stmt and memrefs in
 // ActiveStandard for current procedure
 if (mDUG->mActiveMap[mProc].ptrEqual(0)) {
 mDUG->mActiveMap[mProc] = new OA::Activity::ActiveStandard(mProc);
 }

 mDUG->insertActiveSymSet(sym);

 std::set<MemRefHandle> mrefSet;
 mrefSet = mDUG->getMemRefSet(sym);
 if (!mrefSet.empty()){
 std::set<MemRefHandle>::iterator i = mrefSet.begin();
 for(; i != mrefSet.end(); i++) {
 mDUG->insertActiveMemRefSet(*i, mProc);
 }
 }


 std::set<StmtHandle> stmtSet;
 stmtSet = mDUG->getStmtSet(sym);
 if (!stmtSet.empty()){
 std::set<StmtHandle>::iterator i = stmtSet.begin();
 for(; i != stmtSet.end(); i++)
 mDUG->insertActiveStmtSet(*i, mProc);
 }

}


void 
Node::setActive()
{
 setActive(mSym);

 OA_ptr<Location> loc = mDUG->mIR->getLocation(getProc(), mSym);
 OA_ptr<NamedLoc> nmloc = loc.convert<NamedLoc>();
 assert(!nmloc.ptrEqual(0));
 OA_ptr<SymHandleIterator> overlapIter = nmloc->getFullOverlapIter();
 for ( ; overlapIter->isValid(); (*overlapIter)++ ) {
 SymHandle sym = overlapIter->current();
 setActive(sym);
 }

 overlapIter = nmloc->getPartOverlapIter();
 for ( ; overlapIter->isValid(); (*overlapIter)++ ) {
 SymHandle sym = overlapIter->current();
 setActive(sym);
 }
}


void 
Node::markVaried(std::list<CallHandle>& callStack,
 OA_ptr<Activity::ActivityIRInterface> ir,
 std::set<OA_ptr<EdgeInterface> >& visited,
 std::set<std::pair<unsigned,unsigned> >& onPath,
 ProcHandle proc,
 SymHandle prevSym, 
 OA_ptr<EdgeInterface> parenEdge)
{ 
 SymHandle currSym = getSym();

 EdgeType parenEType = CFLOW_EDGE;
 CallHandle parenCall = CallHandle(0);
 if (!parenEdge.ptrEqual(0)) {
 parenEType = parenEdge->getType();
 parenCall = parenEdge->getCall();
 }


#ifdef DEBUG_DUAA
 std::cout << "-v->"; 
 if (parenEdge.ptrEqual(0)) {
 std::cout << "NULL edge";
 }else
 parenEdge->dumpdot(std::cout, mDUG->mIR);
 std::cout << std::endl;
#endif 
 bool isVariedBefore = isVaried();
 int nonParentSuccessors = 0;
 setVaried();

 bool valueThroughGlobals = false;
 if (callStack.front() == CallHandle(1)) valueThroughGlobals = true;

 // set up iterator for successor edges
 OA_ptr<EdgesIteratorInterface> succIterPtr;
 succIterPtr = getDUGOutgoingEdgesIterator();
 // iterate over the successors
 for (; succIterPtr->isValid(); ++(*succIterPtr)) {

 OA_ptr<EdgeInterface> succEdge = succIterPtr->currentDUGEdge();
 OA_ptr<NodeInterface> succNode = succEdge->getDUGSink();

 SymHandle succSym = succNode->getSym();
 unsigned succId = succNode->getId();
 EdgeType etype = succEdge->getType();

 std::pair<unsigned, unsigned> pathNode;
 switch(etype) {
 case CALL_EDGE: 
 pathNode = std::pair<unsigned,unsigned>
 (succEdge->getCall().hval(),succId); break;
 case PARAM_EDGE:
 if (callStack.empty())
 pathNode = std::pair<unsigned,unsigned>(1,succId); 
 else
 pathNode = std::pair<unsigned,unsigned>
 (callStack.front().hval(),succId); break;
 case RETURN_EDGE:
 case CFLOW_EDGE:
 pathNode = std::pair<unsigned,unsigned>(1,succId); break;
 default: assert(0);
 }

 if (succSym != prevSym || parenCall != succEdge->getCall()) nonParentSuccessors++;

 if (visited.find(succEdge) != visited.end() ||
 onPath.find(pathNode) != onPath.end() ) 
 {
 continue;
 }

 onPath.insert(pathNode);

 switch(etype) {
 case (CALL_EDGE):
 {
 // to deal with value passing through global variables between procedures
 ProcHandle callerProc = succEdge->getSourceProc();
 if (proc != callerProc){ 
#ifdef DEBUG_DUAA
 std::cout << "valthruglobals: begin" << std::endl;
#endif 
 callStack.push_front(CallHandle(1));
 }
 
 callStack.push_front(succEdge->getCall());
 visited.insert(succEdge);
 
 succNode->markVaried(callStack, ir, visited, onPath, 
 succEdge->getSinkProc(), currSym, 
 succEdge);
 callStack.pop_front();
 if (proc != callerProc){ 
#ifdef DEBUG_DUAA
 std::cout << "valthruglobals: end" << std::endl;
#endif 
 callStack.pop_front();
 }
 break;
 }
 case (RETURN_EDGE):
 if (callStack.front() == succEdge->getCall() || valueThroughGlobals){
 if (!valueThroughGlobals) callStack.pop_front();
 visited.insert(succEdge);

 succNode->markVaried(callStack, ir, visited, onPath, 
 succEdge->getProc(), currSym, 
 succEdge);
 if (!valueThroughGlobals) callStack.push_front(succEdge->getCall());
 }
#ifdef DEBUG_DUAA
 else{
 std::cout << "markVaried: stackTop(" << (unsigned)callStack.front().hval() 
 << ") <-> edgeCallExp("
 << (unsigned)succEdge->getCall().hval() << ")" << std::endl;
 }
#endif 
 break;
 default: // for both CFLOW_EDGE and PARAM_EDGE
 if (succEdge->getType() != PARAM_EDGE) 
 visited.insert(succEdge);
 // value passing through global variables between procedures
 ProcHandle succProc = succEdge->getProc();
 if (proc != succProc) {
 callStack.push_front(CallHandle(1));
 
 succNode->markVaried(callStack, ir, visited, onPath, 
 succProc, currSym, succEdge);
 callStack.pop_front();
 }
 else{
 succNode->markVaried(callStack, ir, visited, onPath, 
 proc, currSym, succEdge);
 }
 break;
 }

 onPath.erase(pathNode);
 }
 // Actual or formal parameters without any outgoing edges shouldn't be
 // activated.
 if (nonParentSuccessors == 0 && !isVariedBefore && !isSelfDependent() && 
 ( parenEType == CALL_EDGE || parenEType == RETURN_EDGE) && 
 !mDUG->isDependent(getProc(), getSym()) ){
 unsetVaried();
#ifdef DEBUG_DUAA
 std::cout << "unsetVaried("; dumpdot(std::cout, mDUG->mIR); 
 std::cout << ")" << std::endl;
#endif 
 }
#ifdef DEBUG_DUAA
 std::cout << "<-" << std::endl;
#endif 
}

void
Node::markUseful(std::list<CallHandle>& callStack,
 OA_ptr<Activity::ActivityIRInterface> ir,
 std::set<OA_ptr<EdgeInterface> >& visited,
 std::set<std::pair<unsigned,unsigned> >& onPath,
 ProcHandle proc,
 SymHandle prevSym, 
 OA_ptr<EdgeInterface> parenEdge)
{
 if (!isVaried()) {
 return;
 }
 SymHandle currSym = getSym();

 EdgeType parenEType = CFLOW_EDGE;
 CallHandle parenCall = CallHandle(0);
 if (!parenEdge.ptrEqual(0)) {
 parenEType = parenEdge->getType();
 parenCall = parenEdge->getCall();
 }

#ifdef DEBUG_DUAA
 std::cout << "-u->"; 
 if (parenEdge.ptrEqual(0)) {
 std::cout << "NULL edge";
 }else
 parenEdge->dumpdot(std::cout, mDUG->mIR);
 std::cout << "(call:" << parenCall.hval() << ")" << std::endl; 
#endif 
 bool isUsefulBefore = isUseful();
 setUseful();
 int nonChildAncestors = 0;

 bool valueThroughGlobals = false;
 if (callStack.front() == CallHandle(1)) valueThroughGlobals = true;

 // set up iterator for predecessor edges
 OA_ptr<EdgesIteratorInterface> predIterPtr;
 predIterPtr = getDUGIncomingEdgesIterator();
 // iterate over the predecessors unless 'this' node is for indenepdent variable
 // we assume no independent variables are dependent on another independent variables
 for (; predIterPtr->isValid(); ++(*predIterPtr)) {
 
 OA_ptr<EdgeInterface> predEdge = predIterPtr->currentDUGEdge();
 OA_ptr<NodeInterface> predNode = predEdge->getDUGSource();

 SymHandle predSym = predNode->getSym();
 unsigned predId = predNode->getId();
 EdgeType etype = predEdge->getType();

 std::pair<unsigned, unsigned> pathNode;
 switch(etype) {
 case RETURN_EDGE:
 pathNode = std::pair<unsigned,unsigned>
 (predEdge->getCall().hval(),predId); break;
 case PARAM_EDGE:
 if (callStack.empty())
 pathNode = std::pair<unsigned,unsigned>(1,predId); 
 else
 pathNode = std::pair<unsigned,unsigned>
 (callStack.front().hval(),predId); break;
 case CALL_EDGE: 
 case CFLOW_EDGE:
 pathNode = std::pair<unsigned,unsigned>
 (1,predId); break;
 default: assert(0);
 }
 if (predSym != prevSym || parenCall != predEdge->getCall()) nonChildAncestors++;
 if (visited.find(predEdge) != visited.end() ||
 onPath.find(pathNode) != onPath.end() ) continue;
 onPath.insert(pathNode);

 switch(etype) {
 case (CALL_EDGE):
 if (callStack.front() == predEdge->getCall() || valueThroughGlobals ){
 if (!valueThroughGlobals) callStack.pop_front();
 visited.insert(predEdge);
 predNode->markUseful(callStack, ir, visited, onPath, 
 predEdge->getProc(), currSym, predEdge);
 if (!valueThroughGlobals) callStack.push_front(predEdge->getCall());
 }
 break;
 case (RETURN_EDGE):
 {
 ProcHandle callerProc = predEdge->getSinkProc();
 if (proc != callerProc){ 
 callStack.push_front(CallHandle(1));
#ifdef DEBUG_DUAA
 std::cout << "valthruglobals: begin" << std::endl;
#endif 
 }

 callStack.push_front(predEdge->getCall());
 visited.insert(predEdge);
 predNode->markUseful(callStack, ir, visited, onPath, 
 predEdge->getSourceProc(), 
 currSym, predEdge);
 callStack.pop_front();
 if (proc != callerProc){ 
 callStack.pop_front();
#ifdef DEBUG_DUAA
 std::cout << "valthruglobals: end" << std::endl;
#endif 
 }
 break;
 }
 default: // for both CFLOW_EDGE and PARAM_EDGE
 if (predEdge->getType() != PARAM_EDGE) visited.insert(predEdge);
 ProcHandle predProc = predEdge->getProc();
 if (proc != predProc) {
 callStack.push_front(CallHandle(1));
#ifdef DEBUG_DUAA
 std::cout << "valthruglobals: begin" << std::endl;
#endif 
 predNode->markUseful(callStack, ir, visited, onPath, 
 predProc, currSym, predEdge);
 callStack.pop_front();
#ifdef DEBUG_DUAA
 std::cout << "valthruglobals: end" << std::endl;
#endif 
 }
 else
 {
 predNode->markUseful(callStack, ir, visited, onPath, 
 proc, currSym, predEdge);
 }
 break;
 }

 onPath.erase(pathNode);
 }

 unsigned currId = getId();
 // Formal parameters without any outgoing edges shouldn't be
 // activated.
 if (nonChildAncestors == 0 && !isUsefulBefore && !isSelfDependent() && 
 ( parenEType == RETURN_EDGE || parenEType == CALL_EDGE) &&
 !mDUG->isIndependent(getProc(), getSym()) ){
#ifdef DEBUG_DUAA
 std::cout << "unsetUseful(" << currId << ")" << std::endl;
#endif 
 unsetUseful();
 }else{
#ifdef DEBUG_DUAA
 std::cout << "setActive(" << currId << ")" << std::endl;
#endif 
 setActive();
 }

#ifdef DEBUG_DUAA
 std::cout << "<-" << std::endl;
#endif 
}

bool DUGStandard::isActive(SymHandle sym)
{
 // an unknown location is active, therefore all symbols are active
 if (mUnknownLocActive) {
 return true;
 } else if (mActiveSymSet->find(sym) != mActiveSymSet->end()) {
 return true;
 } else {
 return false;
 } 
}



bool DUGStandard::isActive(MemRefHandle memref)
{
 if (mActiveMemRefSet->find(memref) != mActiveMemRefSet->end()) {
 return true;
 } else {
 return false;
 }
}



// 'true' if there is a path from 'useNode' to 'this'
bool
Node::isPathFrom(OA_ptr<NodeInterface> useNode,
 std::set<OA_ptr<NodeInterface> >& visited)
{ 
 if (useNode.ptrEqual(this)) return true;

 // traverse backward from this nodes
 OA_ptr<EdgesIteratorInterface> predIterPtr
 = getDUGIncomingEdgesIterator();
 for (; predIterPtr->isValid(); ++(*predIterPtr)) {
 OA_ptr<EdgeInterface> predEdge = predIterPtr->currentDUGEdge();
 OA_ptr<NodeInterface> predNode = predEdge->getDUGSource();
 
 if (visited.find(predNode) != visited.end()) continue;
 visited.insert(predNode);
 if (predNode->isPathFrom(useNode, visited)) return true;
 }

 return false;
}



// true if this has an outgoing edge to other procedures
bool
Node::hasOutgoingEdgesToOtherProcs(ProcHandle proc)
{ 
 OA_ptr<EdgesIteratorInterface> succIterPtr
 = getDUGOutgoingEdgesIterator();
 for (; succIterPtr->isValid(); ++(*succIterPtr)) {
 OA_ptr<EdgeInterface> succEdge = succIterPtr->currentDUGEdge();
 if (succEdge->getType() != CFLOW_EDGE) continue;
 if (succEdge->getProc() != proc) return true;
 }

 return false;
}



// returns a set of outgoing nodes of this proc
void
Node::findOutgoingNodes(ProcHandle proc, 
 std::set<IRSymHandle>& OutGoingNodeSet,
 std::set<IRSymHandle>& visited)
{ 
 IRSymHandle nodeKey = getIRSymHandle();
 if (visited.find(nodeKey) != visited.end()) return;
 visited.insert(nodeKey);

 if (hasOutgoingEdgesToOtherProcs(proc)) 
 OutGoingNodeSet.insert(nodeKey);

 // traverse foreward from this nodes
 OA_ptr<EdgesIteratorInterface> succIterPtr
 = getDUGOutgoingEdgesIterator();
 for (; succIterPtr->isValid(); ++(*succIterPtr)) {
 OA_ptr<EdgeInterface> succEdge = succIterPtr->currentDUGEdge();
 OA_ptr<NodeInterface> succNode = succEdge->getDUGSink();

 if (succEdge->getType() != CFLOW_EDGE) continue;
 if (succEdge->getProc() != proc) continue;
 
 succNode->findOutgoingNodes(proc, OutGoingNodeSet, visited);
 }
}



// true if this has an incoming edge to other procedures
bool
Node::hasIncomingEdgesFromOtherProcs(ProcHandle proc)
{ 
 OA_ptr<EdgesIteratorInterface> predIterPtr
 = getDUGIncomingEdgesIterator();
 for (; predIterPtr->isValid(); ++(*predIterPtr)) {
 OA_ptr<EdgeInterface> predEdge = predIterPtr->currentDUGEdge();
 if (predEdge->getType() != CFLOW_EDGE) continue;
 if (predEdge->getProc() != proc) return true;
 }
 return false;
}



// returns a set of incoming nodes of this proc
void
Node::findIncomingNodes(ProcHandle proc, 
 std::set<IRSymHandle>& InComingNodeSet,
 std::set<IRSymHandle>& visited)
{ 
 IRSymHandle nodeKey = getIRSymHandle();
 if (visited.find(nodeKey) != visited.end()) return;
 visited.insert(nodeKey);

 if (hasIncomingEdgesFromOtherProcs(proc)) 
 InComingNodeSet.insert(nodeKey);

 // traverse backward from this nodes
 OA_ptr<EdgesIteratorInterface> predIterPtr = getDUGIncomingEdgesIterator();
 for (; predIterPtr->isValid(); ++(*predIterPtr)) {
 OA_ptr<EdgeInterface> predEdge = predIterPtr->currentDUGEdge();
 OA_ptr<NodeInterface> predNode = predEdge->getDUGSource();
 
 if (predEdge->getType() != CFLOW_EDGE) continue;
 if (predEdge->getProc() != proc) continue;

 predNode->findIncomingNodes(proc, InComingNodeSet, visited);
 }
}



bool
Node::hasEdgesToOtherProc(ProcHandle proc, std::set<IRSymHandle>& visited)
{ 
 IRSymHandle ish = getIRSymHandle();
 if (visited.find(ish) != visited.end()) return false;
 visited.insert(ish);

 // traverse foreward from this nodes
 OA_ptr<EdgesIteratorInterface> succIterPtr = getDUGOutgoingEdgesIterator();
 for (; succIterPtr->isValid(); ++(*succIterPtr)) {
 OA_ptr<EdgeInterface> succEdge = succIterPtr->currentDUGEdge();
 OA_ptr<NodeInterface> succNode = succEdge->getDUGSink();
 
 EdgeType etype = succEdge->getType();
 if (etype != CFLOW_EDGE && etype != CALL_EDGE) continue;
 if (succEdge->getProc() != proc) return true;
 if (etype == CFLOW_EDGE && succNode->hasEdgesToOtherProc(proc, visited)) 
 return true;
 }
 return false;
}



// true if this has an incoming edge to other procedures
bool
Node::hasEdgesFromOtherProc(ProcHandle proc, std::set<IRSymHandle>& visited)
{ 
 IRSymHandle ish = getIRSymHandle();
 if (visited.find(ish) != visited.end()) return false;
 visited.insert(ish);

 // traverse backward from this nodes
 OA_ptr<EdgesIteratorInterface> predIterPtr = getDUGIncomingEdgesIterator();
 for (; predIterPtr->isValid(); ++(*predIterPtr)) {
 OA_ptr<EdgeInterface> predEdge = predIterPtr->currentDUGEdge();
 OA_ptr<NodeInterface> predNode = predEdge->getDUGSource();
 
 EdgeType etype = predEdge->getType();
 if (etype != CFLOW_EDGE) continue;
 if (predEdge->getProc() != proc) return true;
 if (predNode->hasEdgesFromOtherProc(proc, visited)) 
 return true;
 }
 return false;
}



 } // end namespace DUGStandard
} // end namespace OA