34 using namespace SVFUtil;
51 for (SVFStmt::SVFStmtSetTy::iterator iter = addrs.begin(), eiter =
52 addrs.end(); iter != eiter; ++iter)
54 const AddrStmt* edge = SVFUtil::cast<AddrStmt>(*iter);
59 for (SVFStmt::SVFStmtSetTy::iterator iter = copys.begin(), eiter =
60 copys.end(); iter != eiter; ++iter)
62 const CopyStmt* edge = SVFUtil::cast<CopyStmt>(*iter);
68 for (SVFStmt::SVFStmtSetTy::iterator iter = phis.begin(), eiter =
69 phis.end(); iter != eiter; ++iter)
71 const PhiStmt* edge = SVFUtil::cast<PhiStmt>(*iter);
73 addCopyCGEdge(opVar->getId(),edge->
getResID());
77 for (SVFStmt::SVFStmtSetTy::iterator iter = selects.begin(), eiter =
78 selects.end(); iter != eiter; ++iter)
80 const SelectStmt* edge = SVFUtil::cast<SelectStmt>(*iter);
82 addCopyCGEdge(opVar->getId(),edge->
getResID());
86 for (SVFStmt::SVFStmtSetTy::iterator iter = calls.begin(), eiter =
87 calls.end(); iter != eiter; ++iter)
89 const CallPE* edge = SVFUtil::cast<CallPE>(*iter);
94 for (SVFStmt::SVFStmtSetTy::iterator iter = rets.begin(), eiter =
95 rets.end(); iter != eiter; ++iter)
97 const RetPE* edge = SVFUtil::cast<RetPE>(*iter);
102 for (SVFStmt::SVFStmtSetTy::iterator iter = tdfks.begin(), eiter =
103 tdfks.end(); iter != eiter; ++iter)
105 const TDForkPE* edge = SVFUtil::cast<TDForkPE>(*iter);
110 for (SVFStmt::SVFStmtSetTy::iterator iter = tdjns.begin(), eiter =
111 tdjns.end(); iter != eiter; ++iter)
113 const TDJoinPE* edge = SVFUtil::cast<TDJoinPE>(*iter);
118 for (SVFStmt::SVFStmtSetTy::iterator iter = ngeps.begin(), eiter =
119 ngeps.end(); iter != eiter; ++iter)
121 GepStmt* edge = SVFUtil::cast<GepStmt>(*iter);
129 for (SVFStmt::SVFStmtSetTy::iterator iter = loads.begin(), eiter =
130 loads.end(); iter != eiter; ++iter)
132 LoadStmt* edge = SVFUtil::cast<LoadStmt>(*iter);
137 for (SVFStmt::SVFStmtSetTy::iterator iter = stores.begin(), eiter =
138 stores.end(); iter != eiter; ++iter)
140 StoreStmt* edge = SVFUtil::cast<StoreStmt>(*iter);
154 for(
auto cs_pair : pag->getIndirectCallsites())
156 const RetICFGNode* retBlockNode = cs_pair.first->getRetICFGNode();
157 if(pag->callsiteHasRet(retBlockNode))
158 retFromIndCalls.insert(pag->getCallSiteRet(retBlockNode)->getId());
162 for (
auto it = this->begin(); it != this->end(); ++it)
164 if (it->second->hasIncomingEdge() || it->second->hasOutgoingEdge())
166 if (pag->getGNode(it->first)->isPointer())
168 if (retFromIndCalls.find(it->first)!=retFromIndCalls.end())
170 nodesToRemove.insert(it->second);
173 for (
auto node : nodesToRemove)
174 removeConstraintNode(node);
195 assert(!SVFUtil::isa<DummyValVar>(node) &&
"a dummy node??");
212 assert(inserted &&
"new AddrCGEdge not added??");
234 assert(inserted &&
"new CopyCGEdge not added??");
257 assert(inserted &&
"new NormalGepCGEdge not added??");
278 assert(inserted &&
"new VariantGepCGEdge not added??");
299 assert(inserted &&
"new LoadCGEdge not added??");
320 assert(inserted &&
"new StoreCGEdge not added??");
339 if(
LoadCGEdge* load = SVFUtil::dyn_cast<LoadCGEdge>(edge))
344 else if(
StoreCGEdge* store = SVFUtil::dyn_cast<StoreCGEdge>(edge))
354 else if(
NormalGepCGEdge* gep = SVFUtil::dyn_cast<NormalGepCGEdge>(edge))
365 else if(
AddrCGEdge* addr = SVFUtil::dyn_cast<AddrCGEdge>(edge))
370 assert(
false &&
"no other edge type!!");
383 if(
LoadCGEdge* load = SVFUtil::dyn_cast<LoadCGEdge>(edge))
388 else if(
StoreCGEdge* store = SVFUtil::dyn_cast<StoreCGEdge>(edge))
398 else if(
NormalGepCGEdge* gep = SVFUtil::dyn_cast<NormalGepCGEdge>(edge))
409 else if(
AddrCGEdge* addr = SVFUtil::dyn_cast<AddrCGEdge>(edge))
414 assert(
false &&
"no other edge type!!");
426 assert(num &&
"edge not in the set, can not remove!!!");
439 assert(num &&
"edge not in the set, can not remove!!!");
452 assert(num &&
"edge not in the set, can not remove!!!");
466 assert(num &&
"edge not in the set, can not remove!!!");
476 std::vector<ConstraintEdge*> sccEdges;
477 std::vector<ConstraintEdge*> nonSccEdges;
483 nonSccEdges.push_back(subInEdge);
486 sccEdges.push_back(subInEdge);
490 while(!nonSccEdges.empty())
493 nonSccEdges.pop_back();
497 bool criticalGepInsideSCC =
false;
499 while(!sccEdges.empty())
504 if(SVFUtil::isa<CopyCGEdge>(edge))
506 else if (SVFUtil::isa<GepCGEdge>(edge))
512 criticalGepInsideSCC =
true;
516 else if(SVFUtil::isa<LoadCGEdge, StoreCGEdge>(edge))
518 else if(
AddrCGEdge* addr = SVFUtil::dyn_cast<AddrCGEdge>(edge))
523 assert(
false &&
"no such edge");
525 return criticalGepInsideSCC;
535 std::vector<ConstraintEdge*> sccEdges;
536 std::vector<ConstraintEdge*> nonSccEdges;
543 nonSccEdges.push_back(subOutEdge);
546 sccEdges.push_back(subOutEdge);
550 while(!nonSccEdges.empty())
553 nonSccEdges.pop_back();
556 bool criticalGepInsideSCC =
false;
558 while(!sccEdges.empty())
563 if(SVFUtil::isa<CopyCGEdge>(edge))
565 else if (SVFUtil::isa<GepCGEdge>(edge))
571 criticalGepInsideSCC =
true;
575 else if(SVFUtil::isa<LoadCGEdge, StoreCGEdge>(edge))
577 else if(
AddrCGEdge* addr = SVFUtil::dyn_cast<AddrCGEdge>(edge))
582 assert(
false &&
"no such edge");
584 return criticalGepInsideSCC;
602 outs() <<
"-----------------ConstraintGraph--------------------------------------\n";
605 for (ConstraintEdge::ConstraintEdgeSetTy::iterator iter = addrs.begin(),
606 eiter = addrs.end(); iter != eiter; ++iter)
608 outs() << (*iter)->getSrcID() <<
" -- Addr --> " << (*iter)->getDstID()
613 for (ConstraintEdge::ConstraintEdgeSetTy::iterator iter = directs.begin(),
614 eiter = directs.end(); iter != eiter; ++iter)
618 outs() <<
copy->getSrcID() <<
" -- Copy --> " <<
copy->getDstID()
621 else if (
NormalGepCGEdge* ngep = SVFUtil::dyn_cast<NormalGepCGEdge>(*iter))
623 outs() << ngep->getSrcID() <<
" -- NormalGep (" << ngep->getConstantFieldIdx()
624 <<
") --> " << ngep->getDstID() <<
"\n";
628 outs() <<
vgep->getSrcID() <<
" -- VarintGep --> "
629 <<
vgep->getDstID() <<
"\n";
632 assert(
false &&
"wrong constraint edge kind!");
636 for (ConstraintEdge::ConstraintEdgeSetTy::iterator iter = loads.begin(),
637 eiter = loads.end(); iter != eiter; ++iter)
639 outs() << (*iter)->getSrcID() <<
" -- Load --> " << (*iter)->getDstID()
644 for (ConstraintEdge::ConstraintEdgeSetTy::iterator iter = stores.begin(),
645 eiter = stores.end(); iter != eiter; ++iter)
647 outs() << (*iter)->getSrcID() <<
" -- Store --> " << (*iter)->getDstID()
652 <<
"--------------------------------------------------------------\n";
754 return "ConstraintG";
760 else return (
n->getInEdges().empty() &&
n->getOutEdges().empty());
769 bool nameDisplay =
true;
771 std::stringstream rawstr(str);
775 if (SVFUtil::isa<ValVar>(node))
780 rawstr << node->
getId();
783 rawstr << node->
getId();
788 if (!SVFUtil::isa<DummyValVar>(node) && !SVFUtil::isa<DummyObjVar>(node))
791 rawstr << node->
getId() <<
":";
801 if (SVFUtil::isa<ValVar>(node))
803 if(SVFUtil::isa<GepValVar>(node))
804 return "shape=hexagon";
805 else if (SVFUtil::isa<DummyValVar>(node))
806 return "shape=diamond";
810 else if (SVFUtil::isa<ObjVar>(node))
812 if(SVFUtil::isa<GepObjVar>(node))
813 return "shape=doubleoctagon";
814 else if(SVFUtil::isa<FIObjVar>(node))
815 return "shape=box3d";
816 else if (SVFUtil::isa<DummyObjVar>(node))
819 return "shape=component";
821 else if (SVFUtil::isa<RetPN>(node))
823 return "shape=Mrecord";
825 else if (SVFUtil::isa<VarArgPN>(node))
827 return "shape=octagon";
831 assert(0 &&
"no such kind!!");
836 template<
class EdgeIter>
840 assert(edge &&
"No edge found!!");
843 return "color=green";
847 return "color=black";
852 return "color=purple";
864 assert(0 &&
"No such kind edge!!");
869 template<
class EdgeIter>
NodeID getRHSVarID() const
NodeID getLHSVarID() const
GenericNode< ConstraintNode, ConstraintEdge >::GEdgeSetTy ConstraintEdgeSetTy
Constraint edge type.
bool moveInEdgesToRepNode(ConstraintNode *node, ConstraintNode *rep)
ConstraintEdge::ConstraintEdgeSetTy StoreCGEdgeSet
ConstraintEdge::ConstraintEdgeSetTy directEdgeSet
ConstraintEdge::ConstraintEdgeSetTy LoadCGEdgeSet
LoadCGEdge * addLoadCGEdge(NodeID src, NodeID dst)
Add Load edge.
ConstraintNode * getConstraintNode(NodeID id) const
Get/add/remove constraint node.
void view()
View graph from the debugger.
NodeID sccRepNode(NodeID id) const
SCC rep/sub nodes methods.
void reTargetDstOfEdge(ConstraintEdge *edge, ConstraintNode *newDstNode)
Used for cycle elimination.
AddrCGEdge * addAddrCGEdge(NodeID src, NodeID dst)
Add a SVFIR edge into Edge map.
ConstraintEdge::ConstraintEdgeSetTy AddrCGEdgeSet
bool hasEdge(ConstraintNode *src, ConstraintNode *dst, ConstraintEdge::ConstraintEdgeK kind)
CopyCGEdge * addCopyCGEdge(NodeID src, NodeID dst)
Add Copy edge.
ConstraintEdge::ConstraintEdgeSetTy & getStoreCGEdges()
Get Store edges.
StoreCGEdge * addStoreCGEdge(NodeID src, NodeID dst)
Add Store edge.
VariantGepCGEdge * addVariantGepCGEdge(NodeID src, NodeID dst)
void removeDirectEdge(ConstraintEdge *edge)
Remove direct edge from their src and dst edge sets.
bool moveOutEdgesToRepNode(ConstraintNode *node, ConstraintNode *rep)
void removeLoadEdge(LoadCGEdge *edge)
Remove load edge from their src and dst edge sets.
void print()
Print CG into terminal.
void reTargetSrcOfEdge(ConstraintEdge *edge, ConstraintNode *newSrcNode)
Remove edge from old src target, change edge dst id and add modified edge into new src.
void removeStoreEdge(StoreCGEdge *edge)
Remove store edge from their src and dst edge sets.
NormalGepCGEdge * addNormalGepCGEdge(NodeID src, NodeID dst, const AccessPath &ap)
Add Gep edge.
void removeAddrEdge(AddrCGEdge *edge)
Remove addr edge from their src and dst edge sets.
ConstraintEdge::ConstraintEdgeSetTy & getDirectCGEdges()
Get Copy/call/ret/gep edges.
ConstraintEdge::ConstraintEdgeSetTy & getAddrCGEdges()
Get SVFIR edge.
bool isZeroOffsettedGepCGEdge(ConstraintEdge *edge) const
Check if a given edge is a NormalGepCGEdge with 0 offset.
void dump(std::string name)
Dump graph into dot file.
ConstraintEdge::ConstraintEdgeSetTy & getLoadCGEdges()
Get Load edges.
ConstraintEdge::ConstraintEdgeSetTy copyOutEdges
bool addOutgoingStoreEdge(StoreCGEdge *outEdge)
ConstraintEdge::ConstraintEdgeSetTy::iterator iterator
iterator directInEdgeEnd()
void addIncomingStoreEdge(StoreCGEdge *inEdge)
void addOutgoingCopyEdge(CopyCGEdge *outEdge)
bool removeOutgoingStoreEdge(StoreCGEdge *outEdge)
bool removeIncomingStoreEdge(StoreCGEdge *inEdge)
ConstraintEdge::ConstraintEdgeSetTy copyInEdges
ConstraintEdge::ConstraintEdgeSetTy directInEdges
bool removeIncomingAddrEdge(AddrCGEdge *inEdge)
virtual const std::string toString() const
bool removeOutgoingDirectEdge(ConstraintEdge *outEdge)
bool removeIncomingDirectEdge(ConstraintEdge *inEdge)
bool removeOutgoingLoadEdge(LoadCGEdge *outEdge)
iterator directInEdgeBegin()
void addIncomingLoadEdge(LoadCGEdge *inEdge)
bool removeIncomingLoadEdge(LoadCGEdge *inEdge)
iterator directOutEdgeEnd()
bool addOutgoingLoadEdge(LoadCGEdge *outEdge)
void addIncomingGepEdge(GepCGEdge *inEdge)
ConstraintEdge::ConstraintEdgeSetTy::const_iterator const_iterator
bool removeOutgoingAddrEdge(AddrCGEdge *outEdge)
Remove constraint graph edges.
void addOutgoingGepEdge(GepCGEdge *outEdge)
void addIncomingCopyEdge(CopyCGEdge *inEdge)
Add constraint graph edges.
iterator directOutEdgeBegin()
Iterators.
void addIncomingAddrEdge(AddrCGEdge *inEdge)
void addOutgoingAddrEdge(AddrCGEdge *outEdge)
ConstraintEdge::ConstraintEdgeSetTy directOutEdges
GEdgeKind getEdgeKind() const
NodeID getSrcID() const
get methods of the components
NodeType * getGNode(NodeID id) const
Get a node.
IDToNodeMapTy::iterator iterator
Node Iterators.
iterator OutEdgeBegin()
iterators
bool isVariantFieldGep() const
Gep statement with a variant field index (pointer arithmetic) for struct field access.
const AccessPath & getAccessPath() const
static void WriteGraphToFile(SVF::OutStream &O, const std::string &GraphName, const GraphType >, bool simple=false)
const OPVars & getOpndVars() const
static const Option< bool > BriefConsCGDotGraph
static Option< bool > DetectPWC
static const Option< bool > ShowHiddenNode
NodeID getId() const
Get ID.
static SVFIR * getPAG(bool buildFromFile=false)
Singleton design here to make sure we only have one instance during any analysis.
static bool pagReadFromTXT()
GenericNode< SVFVar, SVFStmt >::GEdgeSetTy SVFStmtSetTy
std::string toString() const
Needs to be implemented by a SVF front end.
virtual const std::string getValueName() const =0
Get name of the LLVM value.
const SVFValue * getValue() const
Get/has methods of the components.
std::ostream & outs()
Overwrite llvm::outs()
void ViewGraph(const GraphType &G, const std::string &name, bool ShortNames=false, GraphProgram::Name Program=GraphProgram::DOT)
std::unordered_set< Key, Hash, KeyEqual, Allocator > Set
static std::string getNodeAttributes(NodeType *n, ConstraintGraph *)
static std::string getEdgeSourceLabel(NodeType *, EdgeIter)
static std::string getGraphName(ConstraintGraph *)
Return name of the graph.
static std::string getEdgeAttributes(NodeType *, EdgeIter EI, ConstraintGraph *)
static std::string getNodeLabel(NodeType *n, ConstraintGraph *)
static bool isNodeHidden(NodeType *n, ConstraintGraph *)
DOTGraphTraits(bool isSimple=false)