30 #ifndef VALUEFLOWDDA_H_
31 #define VALUEFLOWDDA_H_
46 template<
class CVar,
class CPtSet,
class DPIm>
104 return (pts |= targetPts);
110 return pts |= targetPts;
131 for(
typename CPtSet::iterator it = cpts.begin(), eit = cpts.end(); it!=eit; ++it)
138 virtual const CPtSet&
findPT(
const DPIm& dpm)
175 const SVFGNode* node = dpm.getLoc();
176 if(SVFUtil::isa<AddrSVFGNode>(node))
178 handleAddr(pts,dpm,SVFUtil::cast<AddrSVFGNode>(node));
186 else if(SVFUtil::isa<GepSVFGNode>(node))
192 else if(
const LoadSVFGNode* load = SVFUtil::dyn_cast<LoadSVFGNode>(node))
194 if(load->getPAGDstNode()->isPointer() ==
false)
199 for(
typename CPtSet::iterator it = loadpts.begin(), eit = loadpts.end(); it!=eit; ++it)
204 else if(
const StoreSVFGNode* store = SVFUtil::dyn_cast<StoreSVFGNode>(node))
206 if(store->getPAGSrcNode()->isPointer() ==
false)
222 for(
typename CPtSet::iterator it = storepts.begin(), eit = storepts.end(); it!=eit; ++it)
246 else if(SVFUtil::isa<MRSVFGNode>(node))
251 assert(
false &&
"unexpected kind of SVFG nodes");
262 for(CallSiteSet::const_iterator it = csSet.begin(), eit = csSet.end(); it!=eit; ++it)
266 if(!newIndirectEdges.empty())
286 DPTItemSet dpmSet(locIt->second.begin(), locIt->second.end());
287 for(
typename DPTItemSet::const_iterator it = dpmSet.begin(),eit = dpmSet.end(); it!=eit; ++it)
289 const DPIm& dstDpm = *it;
290 if(!indirectCall && SVFUtil::isa<IndirectSVFGEdge>(edge) && !SVFUtil::isa<LoadSVFGNode>(edge->
getDstNode()))
292 if(dstDpm.getCurNodeID() == dpm.getCurNodeID())
340 DPTItemSet dpmSet(it->second.begin(), it->second.end());
341 for(
typename DPTItemSet::const_iterator dit = dpmSet.begin(),deit=dpmSet.end(); dit!=deit; ++dit)
354 const SVFGNode* node = oldDpm.getLoc();
355 NodeID obj = oldDpm.getCurNodeID();
361 if(
const IndirectSVFGEdge* indirEdge = SVFUtil::dyn_cast<IndirectSVFGEdge>(*it))
363 const NodeBS& guard = indirEdge->getPointsTo();
367 indirEdge->getDstID() <<
" --> " << indirEdge->getSrcID() <<
"\n");
376 const SVFGNode* node = oldDpm.getLoc();
380 if(
const DirectSVFGEdge* dirEdge = SVFUtil::dyn_cast<DirectSVFGEdge>(*it))
383 dirEdge->getDstID() <<
" --> " << dirEdge->getSrcID() <<
"\n");
384 const SVFGNode* srcNode = dirEdge->getSrcNode();
394 const LoadSVFGNode* load = SVFUtil::cast<LoadSVFGNode>(oldDpm.getLoc());
397 load->
getId() <<
" --> " << loadSrc->
getId() <<
"\n");
399 assert(edge &&
"Edge not found!!");
405 const StoreSVFGNode* store = SVFUtil::cast<StoreSVFGNode>(oldDpm.getLoc());
408 store->
getId() <<
" --> " << storeDst->
getId() <<
"\n");
410 assert(edge &&
"Edge not found!!");
415 const StoreSVFGNode* store = SVFUtil::cast<StoreSVFGNode>(oldDpm.getLoc());
418 store->
getId() <<
" to " << storeSrc->
getId() <<
"\n");
420 assert(edge &&
"Edge not found!!");
441 if(SVFUtil::isa<IndirectSVFGEdge>(edge))
456 if (dstCPSet.count() == 1)
459 typename CPtSet::iterator it = dstCPSet.begin();
460 const CVar& var = *it;
475 assert(obj &&
"object not found!!");
509 for(CallInstSet::const_iterator it = csSet.begin(), eit = csSet.end(); it!=eit; ++it)
585 return !SVFUtil::isa<StoreSVFGNode, MRSVFGNode>(stmt);
593 if(SVFUtil::isa<StoreSVFGNode>(loc))
596 if(SVFUtil::isa<LoadSVFGNode>(loc))
641 assert(mem &&
"memory object is null??");
648 assert(mem &&
"memory object is null??");
674 assert(dpm ==
locToDpmSetMap[dpm.getLoc()].back() &&
"dpm not match with the end of vector");
691 it->second = loadDpm;
705 it->second = loadVar;
765 if (dpmSet.erase(dpm))
#define DBOUT(TYPE, X)
LLVM debug macros, define type of your DBUG model of each pass.
static AndersenWaveDiff * createAndersenWaveDiff(SVFIR *_pag)
Create an singleton instance directly instead of invoking llvm pass manager.
u32_t _NumOfStrongUpdates
u32_t _NumOfInfeasiblePath
double _TotalTimeOfBKCondition
double _AnaTimeCyclePerQuery
NodeBS _StrongUpdateStores
void removeDpmFromLoc(const DPIm &dpm)
bool edgeInSVFGSCC(const SVFGEdge *edge)
Return TRUE if this edge is inside a SVFG SCC, i.e., src node and dst node are in the same SCC on the...
void backtraceAlongIndirectVF(CPtSet &pts, const DPIm &oldDpm)
Backward traverse along indirect value flows.
OrderedSet< DPIm > DPTItemSet
bool isOutOfBudgetDpm(const DPIm &dpm) const
SVFIR::CallSiteSet CallSiteSet
SVFGBuilder svfgBuilder
SVFG Builder.
NodeID getSVFGSCCRepNode(NodeID id)
Get SCC rep node of a SVFG node.
void addLoadDpmAndCVar(const DPIm &dpm, const DPIm &loadDpm, const CVar &loadVar)
LoadDpm for must-alias analysis.
SVFGSCC * getSVFGSCC() const
Return SVFGSCC.
virtual bool isLocalCVarInRecursion(const CVar &var) const
Whether a local variable is in function recursions.
virtual ~DDAVFSolver()
Destructor.
virtual void updateCachedPointsTo(const DPIm &dpm, const CPtSet &pts)
DPImToCPtSetMap dpmToADCPtSetMap
points-to caching map for address-taken vars
virtual const CPtSet & getCachedADPointsTo(const DPIm &dpm)
OrderedMap< DPIm, DPIm > DPMToDPMMap
DPImToCPtSetMap dpmToTLCPtSetMap
points-to caching map for top-level vars
virtual bool isMustAlias(const DPIm &, const DPIm &)
whether load and store are aliased
bool isFieldInsenCondMemObj(const CVar &var) const
virtual CPtSet getConservativeCPts(const DPIm &dpm)=0
Get conservative points-to results when the query is out of budget.
virtual NodeID getPtrNodeID(const CVar &var) const =0
Methods to be implemented in child class.
bool testOutOfBudget(const DPIm &dpm)
void addLoadDpm(const DPIm &dpm, const DPIm &loadDpm)
Note that simply use "dpmToloadDpmMap[dpm]=loadDpm", requires DPIm have a default constructor.
CallGraphSCC * _callGraphSCC
SCC for PTACallGraph.
SCCDetection< SVFG * > SVFGSCC
virtual const CPtSet & findPT(const DPIm &dpm)
Compute points-to.
SVFGSCC * _svfgSCC
SCC for SVFG.
const SVFGNode * getDefSVFGNode(const PAGNode *pagNode) const
GetDefinition SVFG.
virtual void addDDAPts(CPtSet &pts, const CVar &var)
Add pts.
virtual bool handleBKCondition(DPIm &, const SVFGEdge *)
Handle condition for context or path analysis (backward analysis)
const DPIm & getLoadDpm(const DPIm &dpm) const
virtual void updateCallGraphAndSVFG(const DPIm &, const CallICFGNode *, SVFGEdgeSet &)
Update call graph.
DPTItemSet backwardVisited
visited map during backward traversing
virtual bool isHeapCondMemObj(const CVar &var, const StoreSVFGNode *)
Check heap and array object.
SVFGEdge::SVFGEdgeSetTy SVFGEdgeSet
const DPTItemSet & getDpmSetAtLoc(const SVFGNode *loc)
DPMToCVarMap loadToPTCVarMap
map a load dpm to its cvar pointed by its pointer operand
void markbkVisited(const DPIm &dpm)
Visited flags to avoid cycles.
NodeBS & getCandidateQueries()
Return candidate pointers for DDA.
void addLoadCVar(const DPIm &dpm, const CVar &loadVar)
bool isOutOfBudgetQuery() const
void backtraceAlongDirectVF(CPtSet &pts, const DPIm &oldDpm)
Backward traverse along direct value flows.
bool isTopLevelPtrStmt(const SVFGNode *stmt)
Whether this is a top-level pointer statement.
void rmSUStat(const DPIm &dpm, const SVFGNode *node)
remove strong updates num if the dpm goes to weak updates branch
DDAVFSolver()
Constructor.
OrderedMap< DPIm, CPtSet > DPImToCPtSetMap
void reCompute(const DPIm &dpm)
recompute points-to for value-flow cycles and indirect calls
void handleOutOfBudgetDpm(const DPIm &dpm)
handle out-of-budget queries
virtual bool isStrongUpdate(const CPtSet &dstCPSet, const StoreSVFGNode *store)
Return TRUE if this is a strong update STORE statement.
virtual bool unionDDAPts(CPtSet &pts, const CPtSet &targetPts)
Union pts.
virtual void handleSingleStatement(const DPIm &dpm, CPtSet &pts)
Handle single statement.
bool isbkVisited(const DPIm &dpm)
bool isArrayCondMemObj(const CVar &var) const
DPMToDPMMap dpmToloadDpmMap
dpms at loads for may/must-alias analysis with stores
AndersenWaveDiff * _ander
Andersen's analysis.
void dumpCPtSet(const CPtSet &cpts) const
LocToDPMVecMap locToDpmSetMap
map location to its dpms
void clearbkVisited(const DPIm &dpm)
OrderedMap< NodeID, DPTItemSet > LocToDPMVecMap
virtual const CPtSet & getCachedTLPointsTo(const DPIm &dpm)
DPTItemSet outOfBudgetDpms
out of budget dpm set
virtual CPtSet processGepPts(const GepSVFGNode *gep, const CPtSet &srcPts)=0
ProcessGep node to generate field object nodes of a struct.
void OOBResetVisited()
Reset visited map if the current query is out-of-budget.
void SVFGSCCDetection()
SVFG SCC detection.
void setCallGraphSCC(CallGraphSCC *scc)
Set callgraphSCC.
PTACallGraph * _callGraph
PTACallGraph.
PTACallGraphEdge::CallInstSet CallInstSet
AndersenWaveDiff * getAndersenAnalysis() const
Return Andersen's analysis.
virtual DPIm getDPImWithOldCond(const DPIm &oldDpm, const CVar &var, const SVFGNode *loc)
Return dpm with old context and path conditions.
SVFG * getSVFG() const
Return SVFG.
OrderedMap< const SVFGNode *, DPTItemSet > StoreToPMSetMap
void startNewPTCompFromLoadSrc(CPtSet &pts, const DPIm &oldDpm)
void reComputeForEdges(const DPIm &dpm, const SVFGEdgeSet &edgeSet, bool indirectCall=false)
Traverse along out edges to find all nodes which may be affected by locDPM.
virtual bool propagateViaObj(const CVar &storeObj, const CVar &loadObj)
If the points-to contain the object obj, we could move forward along indirect value-flow edge.
virtual void handleAddr(CPtSet &pts, const DPIm &dpm, const AddrSVFGNode *addr)=0
Handle AddrSVFGNode to add proper points-to.
const CVar & getLoadCVar(const DPIm &dpm) const
virtual DPIm getDPIm(const CVar &var, const SVFGNode *loc) const
Given CVar and location (SVFGNode) return a new DPItem.
const LocToDPMVecMap & getLocToDPMVecMap() const
Map a SVFGNode to its dpms for handling value-flow cycles.
void backtraceToStoreSrc(CPtSet &pts, const DPIm &oldDpm)
DDAStat * setDDAStat(DDAStat *s)
Set DDAStat.
bool isSVFGNodeInCycle(const SVFGNode *node)
Return whether this SVFGNode is in cycle.
NodeBS candidateQueries
candidate pointers;
void addOutOfBudgetDpm(const DPIm &dpm)
virtual const CPtSet & getCachedPointsTo(const DPIm &dpm)
Points-to Caching for top-level pointers and address-taken objects.
DDAStat * ddaStat
DDA stat.
virtual bool unionDDAPts(DPIm dpm, const CPtSet &targetPts)
Union pts.
void addSUStat(const DPIm &dpm, const SVFGNode *node)
stat strong updates num
OrderedSet< const SVFGEdge * > ConstSVFGEdgeSet
OrderedMap< DPIm, CVar > DPMToCVarMap
virtual void buildSVFG(SVFIR *pag)
Build SVFG.
StoreToPMSetMap storeToDPMs
map store to set of DPM which have been stong updated there
virtual void backwardPropDpm(CPtSet &pts, NodeID ptr, const DPIm &oldDpm, const SVFGEdge *edge)
dpm transit during backward tracing
SCCDetection< PTACallGraph * > CallGraphSCC
void addDpmToLoc(const DPIm &dpm)
void setCallGraph(PTACallGraph *cg)
Set callgraph.
void resolveFunPtr(const DPIm &dpm)
resolve function pointer
bool outOfBudgetQuery
Whether the current query is out of step limits.
virtual void resetQuery()
Reset visited map for next points-to query.
void startNewPTCompFromStoreDst(CPtSet &pts, const DPIm &oldDpm)
NodeType * getSrcNode() const
NodeID getSrcID() const
get methods of the components
NodeType * getDstNode() const
NodeType * getGNode(NodeID id) const
Get a node.
const GEdgeSetTy & getInEdges() const
bool isFieldInsensitive() const
Return true if its field limit is 0.
Set< const CallICFGNode * > CallInstSet
void getIndCallSitesInvokingCallee(const SVFFunction *callee, PTACallGraphEdge::CallInstSet &csSet)
PTACallGraphNode * getCallGraphNode(NodeID id) const
Get call graph node.
PTACallGraph * getCallGraph() const
Return call graph.
NodeID repNode(NodeID n) const
get the rep node if not found return itself
bool isInCycle(NodeID n) const
whether the node is in a cycle
NodeID getId() const
Get ID.
SVFG * buildPTROnlySVFG(BVDataPTAImpl *pta)
const SVFGNode * getDefSVFGNode(const PAGNode *pagNode) const
Given a pagNode, return its definition site.
NodeID getFunPtr(const CallICFGNode *cs) const
Set< const CallICFGNode * > CallSiteSet
const MemObj * getObject(NodeID id) const
bool isIndirectCallSites(const CallICFGNode *cs) const
bool isConstantObj(NodeID id) const
bool isFunPtr(NodeID id) const
const CallSiteSet & getIndCallSites(NodeID funPtr) const
const MemObj * getBaseObj(NodeID id) const
static double getClk(bool mark=false)
virtual const SVFFunction * getFunction() const
Return the function that this SVFVar resides in. Return nullptr if it is a global or constantexpr nod...
bool test(unsigned Idx) const
NodeID getPAGDstNodeID() const
NodeID getPAGSrcNodeID() const
PAGNode * getPAGSrcNode() const
PAGNode * getPAGDstNode() const
VFGEdgeSetTy SVFGEdgeSetTy
VFGEdge::VFGEdgeSetTy::const_iterator const_iterator
SVFIR * getPAG() const
Return SVFIR.
VFGEdge * getIntraVFGEdge(const VFGNode *src, const VFGNode *dst, VFGEdge::VFGEdgeK kind)
Get a SVFG edge according to src and dst.
LLVM_NODISCARD bool isa(const Y &Val)
std::ostream & outs()
Overwrite llvm::outs()
std::set< Key, Compare, Allocator > OrderedSet
void dump(const SparseBitVector< ElementSize > &LHS, std::ostream &out)
std::map< Key, Value, Compare, Allocator > OrderedMap