40 using namespace SVFUtil;
52 dump(
"SVFG_before_opt");
59 handleInterValueFlow();
61 handleIntraValueFlow();
71 return addIntraIndirectVFEdge(srcId, dstId, cpts);
73 return addCallIndirectVFEdge(srcId, dstId, cpts, csid);
82 return addIntraIndirectVFEdge(srcId, dstId, cpts);
84 return addRetIndirectVFEdge(srcId, dstId, cpts, csid);
100 candidates.insert(node);
104 for (SVFGNodeSet::const_iterator it = candidates.begin(), eit = candidates.end();
110 replaceFParamARetWithPHI(addInterPHIForFP(fp), fp);
111 nodesToBeDeleted.insert(fp);
115 replaceFParamARetWithPHI(addInterPHIForAR(ar), ar);
116 nodesToBeDeleted.insert(ar);
118 else if (SVFUtil::isa<ActualParmSVFGNode, FormalRetSVFGNode>(node))
120 nodesToBeDeleted.insert(node);
122 else if (SVFUtil::isa<ActualINSVFGNode, FormalOUTSVFGNode>(node))
124 retargetEdgesOfAInFOut(node);
125 nodesToBeDeleted.insert(node);
127 else if (SVFUtil::isa<ActualOUTSVFGNode, FormalINSVFGNode>(node))
129 if(keepActualOutFormalIn ==
false)
130 nodesToBeDeleted.insert(node);
134 for (SVFGNodeSet::iterator it = nodesToBeDeleted.begin(), eit = nodesToBeDeleted.end(); it != eit; ++it)
137 if (canBeRemoved(node))
139 if (SVFUtil::isa<ActualOUTSVFGNode, FormalINSVFGNode>(node))
140 retargetEdgesOfAOutFIn(node);
142 removeAllEdges(node);
143 removeSVFGNode(node);
153 assert((SVFUtil::isa<FormalParmSVFGNode, ActualRetSVFGNode>(svfgNode))
154 &&
"expecting a formal param or actual ret svfg node");
165 if (
const CallDirSVFGEdge* callEdge = SVFUtil::dyn_cast<CallDirSVFGEdge>(outEdge))
166 addCallEdge(phiId, dstId, callEdge->getCallSiteId());
167 else if (
const RetDirSVFGEdge* retEdge = SVFUtil::dyn_cast<RetDirSVFGEdge>(outEdge))
168 addRetEdge(phiId, dstId, retEdge->getCallSiteId());
170 addIntraDirectVFEdge(phiId, dstId);
180 addInterPHIOperands(phi, ap->
getParam());
191 addInterPHIOperands(phi, fr->
getRet());
193 addRetEdge(getDef(fr->
getRet()), phiId, getCallSiteID(ar->getCallSite(), fr->
getFun()));
197 removeAllEdges(svfgNode);
206 assert(node->
getInEdges().size() == 1 &&
"actual-in/formal-out can only have one incoming edge as its def size");
213 for (; it != eit; ++it)
219 if (SVFUtil::isa<ActualINSVFGNode>(node))
221 else if (SVFUtil::isa<FormalOUTSVFGNode>(node))
226 for (; it != eit; ++it)
229 NodeBS intersection = inPointsTo;
232 if (intersection.
empty())
236 if (
const CallIndSVFGEdge* callEdge = SVFUtil::dyn_cast<CallIndSVFGEdge>(outEdge))
237 addCallIndirectSVFGEdge(def->
getId(), dstNode->
getId(), callEdge->getCallSiteId(), intersection);
238 else if (
const RetIndSVFGEdge* retEdge = SVFUtil::dyn_cast<RetIndSVFGEdge>(outEdge))
239 addRetIndirectSVFGEdge(def->
getId(), dstNode->
getId(), retEdge->getCallSiteId(), intersection);
241 assert(
false &&
"expecting an inter-procedural SVFG edge");
244 removeAllEdges(node);
254 for (; inIt != inEit; ++inIt)
261 for (; outIt != outEit; ++outIt)
267 if (intersection.
empty())
271 if (
const RetIndSVFGEdge* retEdge = SVFUtil::dyn_cast<RetIndSVFGEdge>(inEdge))
273 addRetIndirectSVFGEdge(srcId, dstId, retEdge->getCallSiteId(), intersection);
275 else if (
const CallIndSVFGEdge* callEdge = SVFUtil::dyn_cast<CallIndSVFGEdge>(inEdge))
277 addCallIndirectSVFGEdge(srcId, dstId, callEdge->getCallSiteId(), intersection);
281 addIntraIndirectVFEdge(srcId, dstId, intersection);
286 removeAllEdges(node);
294 bool hasInCallRet =
false;
295 bool hasOutCallRet =
false;
299 for (; edgeIt != edgeEit; ++edgeIt)
301 if (SVFUtil::isa<CallIndSVFGEdge, RetIndSVFGEdge>(*edgeIt))
310 for (; edgeIt != edgeEit; ++edgeIt)
312 if (SVFUtil::isa<CallIndSVFGEdge, RetIndSVFGEdge>(*edgeIt))
314 hasOutCallRet =
true;
319 if (hasInCallRet && hasOutCallRet)
345 if (isConnectingTwoCallSites(node))
350 return (actualInOfIndCS(ai) ==
false);
352 else if (
const ActualOUTSVFGNode* ao = SVFUtil::dyn_cast<ActualOUTSVFGNode>(node))
354 return (actualOutOfIndCS(ao) ==
false && isDefOfAInFOut(node) ==
false);
356 else if (
const FormalINSVFGNode* fi = SVFUtil::dyn_cast<FormalINSVFGNode>(node))
358 return (formalInOfAddressTakenFunc(fi) ==
false && isDefOfAInFOut(node) ==
false);
360 else if (
const FormalOUTSVFGNode* fo = SVFUtil::dyn_cast<FormalOUTSVFGNode>(node))
362 return (formalOutOfAddressTakenFunc(fo) ==
false);
376 keepAllSelfCycle =
true;
378 keepContextSelfCycle =
true;
380 keepAllSelfCycle = keepContextSelfCycle =
false;
384 keepAllSelfCycle =
true;
393 parseSelfCycleHandleOption();
397 while (!worklist.empty())
402 if (checkSelfCycleEdges(node))
406 bypassMSSAPHINode(node);
414 for (; edgeIt != edgeEit; ++edgeIt)
415 addIntoWorklist((*edgeIt)->getSrcNode());
424 for (; edgeIt != edgeEit; ++edgeIt)
425 addIntoWorklist((*edgeIt)->getDstNode());
427 removeOutEdges(node);
444 bool hasSelfCycle =
false;
449 for (; inEdgeIt != inEdgeEit; ++inEdgeIt)
455 if (keepAllSelfCycle)
460 else if (keepContextSelfCycle &&
461 SVFUtil::isa<CallIndSVFGEdge, RetIndSVFGEdge>(preEdge))
468 assert(SVFUtil::isa<IndirectSVFGEdge>(preEdge) &&
"can only remove indirect SVFG edge");
469 removeSVFGEdge(preEdge);
484 for (; inEdgeIt != inEdgeEit; ++inEdgeIt)
486 const SVFGEdge* preEdge = *inEdgeIt;
493 for (; outEdgeIt != outEdgeEit; ++outEdgeIt)
495 const SVFGEdge* succEdge = *outEdgeIt;
496 const SVFGNode* dstNode = (*outEdgeIt)->getDstNode();
498 && addNewSVFGEdge(srcNode->
getId(), dstNode->
getId(), preEdge, succEdge))
504 addIntoWorklist(dstNode);
512 addIntoWorklist(srcNode);
516 removeAllEdges(node);
525 assert(SVFUtil::isa<IndirectSVFGEdge>(preEdge) && SVFUtil::isa<IndirectSVFGEdge>(succEdge)
526 &&
"either pre or succ edge is not indirect SVFG edge");
528 const IndirectSVFGEdge* preIndEdge = SVFUtil::cast<IndirectSVFGEdge>(preEdge);
529 const IndirectSVFGEdge* succIndEdge = SVFUtil::cast<IndirectSVFGEdge>(succEdge);
534 if (intersection.
empty())
537 assert(bothInterEdges(preEdge, succEdge) ==
false &&
"both edges are inter edges");
539 if (
const CallIndSVFGEdge* preCallEdge = SVFUtil::dyn_cast<CallIndSVFGEdge>(preEdge))
541 return addCallIndirectSVFGEdge(srcId, dstId, preCallEdge->getCallSiteId(), intersection);
543 else if (
const CallIndSVFGEdge* succCallEdge = SVFUtil::dyn_cast<CallIndSVFGEdge>(succEdge))
545 return addCallIndirectSVFGEdge(srcId, dstId, succCallEdge->getCallSiteId(), intersection);
547 else if (
const RetIndSVFGEdge* preRetEdge = SVFUtil::dyn_cast<RetIndSVFGEdge>(preEdge))
549 return addRetIndirectSVFGEdge(srcId, dstId, preRetEdge->getCallSiteId(), intersection);
551 else if (
const RetIndSVFGEdge* succRetEdge = SVFUtil::dyn_cast<RetIndSVFGEdge>(succEdge))
553 return addRetIndirectSVFGEdge(srcId, dstId, succRetEdge->getCallSiteId(), intersection);
557 return addIntraIndirectVFEdge(srcId, dstId, intersection);
static std::string KeepNoneSelfCycle
static std::string KeepContextSelfCycle
static std::string KeepAllSelfCycle
#define DBOUT(TYPE, X)
LLVM debug macros, define type of your DBUG model of each pass.
const PAGNode * getParam() const
Return parameter.
const CallICFGNode * getCallSite() const
Return callsite.
NodeType * getSrcNode() const
NodeID getSrcID() const
get methods of the components
NodeType * getDstNode() const
iterator begin()
Iterators.
bool hasIncomingEdge() const
Has incoming/outgoing edge set.
bool hasOutgoingEdge() const
iterator OutEdgeBegin()
iterators
const GEdgeSetTy & getInEdges() const
virtual const SVFFunction * getFun() const
Return the function of this ICFGNode.
const NodeBS & getPointsTo() const
static const Option< bool > KeepAOFI
static const Option< std::string > SelfCycle
static const Option< bool > DumpVFG
static const Option< bool > ContextInsensitive
NodeID getId() const
Get ID.
Set< SVFGNode * > SVFGNodeSet
SVFGEdge * addCallIndirectSVFGEdge(NodeID srcId, NodeID dstId, CallSiteID csid, const NodeBS &cpts)
Add inter-procedural value flow edge.
void replaceFParamARetWithPHI(PHISVFGNode *phi, SVFGNode *svfgNode)
Replace FormalParam/ActualRet node with PHI node.
void handleIntraValueFlow()
Remove MSSAPHI SVFG nodes.
void retargetEdgesOfAOutFIn(SVFGNode *node)
Connect actual-out/formal-in's predecessors to their successors directly.
void handleInterValueFlow()
void bypassMSSAPHINode(const MSSAPHISVFGNode *node)
Remove MSSAPHI node if possible.
bool addNewSVFGEdge(NodeID srcId, NodeID dstId, const SVFGEdge *preEdge, const SVFGEdge *succEdge)
Add new SVFG edge from src to dst.
void buildSVFG() override
Start building SVFG.
bool isConnectingTwoCallSites(const SVFGNode *node) const
Return TRUE if this node has both incoming call/ret and outgoing call/ret edges.
bool canBeRemoved(const SVFGNode *node)
void retargetEdgesOfAInFOut(SVFGNode *node)
Retarget edges related to actual-in/-out and formal-in/-out.
void parseSelfCycleHandleOption()
SVFGEdge * addRetIndirectSVFGEdge(NodeID srcId, NodeID dstId, CallSiteID csid, const NodeBS &cpts)
Add indirect ret edge from src to dst with one call site ID.
bool checkSelfCycleEdges(const MSSAPHISVFGNode *node)
Remove self cycle edges if needed. Return TRUE if some self cycle edges remained.
virtual void buildSVFG()
Start building SVFG.
VFGEdgeSetTy SVFGEdgeSetTy
VFGEdge::VFGEdgeSetTy::const_iterator const_iterator
VFGEdge::VFGEdgeSetTy::iterator iterator
std::string pasMsg(const std::string &msg)
Print each pass/phase message by converting a string into blue string output.
LLVM_NODISCARD bool isa(const Y &Val)
void writeWrnMsg(const std::string &msg)
Writes a message run through wrnMsg.
std::ostream & outs()
Overwrite llvm::outs()
void dump(const SparseBitVector< ElementSize > &LHS, std::ostream &out)