Static Value-Flow Analysis
Loading...
Searching...
No Matches
SVF::AndersenBase Class Referenceabstract

#include <Andersen.h>

Inheritance diagram for SVF::AndersenBase:
SVF::WPASolver< ConstraintGraph * > SVF::BVDataPTAImpl SVF::PointerAnalysis SVF::Andersen SVF::Steensgaard SVF::TypeAnalysis SVF::AndersenSCD SVF::AndersenWaveDiff SVF::AndersenSFR

Public Types

typedef OrderedMap< const CallICFGNode *, NodeID > CallSite2DummyValPN
Public Types inherited from SVF::WPASolver< ConstraintGraph * >
typedef SVF::GenericGraphTraits< ConstraintGraph * > GTraits
 Define the GTraits and node iterator for printing.
typedef GTraits::NodeRef GNODE
typedef GTraits::EdgeType GEDGE
typedef GTraits::ChildIteratorType child_iterator
typedef SCCDetection< ConstraintGraph * > SCC
typedef FIFOWorkList< NodeID > WorkList
Public Types inherited from SVF::BVDataPTAImpl
typedef PTData< NodeID, NodeSet, NodeID, PointsTo > PTDataTy
typedef DiffPTData< NodeID, NodeSet, NodeID, PointsTo > DiffPTDataTy
typedef DFPTData< NodeID, NodeSet, NodeID, PointsTo > DFPTDataTy
typedef VersionedPTData< NodeID, NodeSet, NodeID, PointsTo, VersionedVar, Set< VersionedVar > > VersionedPTDataTy
typedef MutablePTData< NodeID, NodeSet, NodeID, PointsTo > MutPTDataTy
typedef MutableDiffPTData< NodeID, NodeSet, NodeID, PointsTo > MutDiffPTDataTy
typedef MutableDFPTData< NodeID, NodeSet, NodeID, PointsTo > MutDFPTDataTy
typedef MutableIncDFPTData< NodeID, NodeSet, NodeID, PointsTo > MutIncDFPTDataTy
typedef MutableVersionedPTData< NodeID, NodeSet, NodeID, PointsTo, VersionedVar, Set< VersionedVar > > MutVersionedPTDataTy
typedef PersistentPTData< NodeID, NodeSet, NodeID, PointsTo > PersPTDataTy
typedef PersistentDiffPTData< NodeID, NodeSet, NodeID, PointsTo > PersDiffPTDataTy
typedef PersistentDFPTData< NodeID, NodeSet, NodeID, PointsTo > PersDFPTDataTy
typedef PersistentIncDFPTData< NodeID, NodeSet, NodeID, PointsTo > PersIncDFPTDataTy
typedef PersistentVersionedPTData< NodeID, NodeSet, NodeID, PointsTo, VersionedVar, Set< VersionedVar > > PersVersionedPTDataTy
Public Types inherited from SVF::PointerAnalysis
typedef Set< const CallICFGNode * > CallSiteSet
 Indirect call edges type, map a callsite to a set of callees.
typedef SVFIR::CallSiteToFunPtrMap CallSiteToFunPtrMap
typedef Set< const FunObjVar * > FunctionSet
typedef OrderedMap< const CallICFGNode *, FunctionSet > CallEdgeMap
typedef SCCDetection< CallGraph * > CallGraphSCC
typedef Set< const GlobalObjVar * > VTableSet
typedef Set< const FunObjVar * > VFunSet

Public Member Functions

 AndersenBase (SVFIR *_pag, PTATY type=PTATY::Andersen_BASE, bool alias_check=true)
 Constructor.
 ~AndersenBase () override
 Destructor.
virtual void analyze () override
 Andersen analysis.
virtual void solveAndwritePtsToFile (const std::string &filename)
virtual void readPtsFromFile (const std::string &filename)
virtual void solveConstraints ()
virtual void initialize () override
 Initialize analysis.
virtual void finalize () override
 Finalize analysis.
virtual bool updateCallGraph (const CallSiteToFunPtrMap &) override
 Update call graph.
virtual bool updateThreadCallGraph (const CallSiteToFunPtrMap &, NodePairSet &)
 Update thread call graph.
virtual void connectCaller2ForkedFunParams (const CallICFGNode *cs, const FunObjVar *F, NodePairSet &cpySrcNodes)
 Connect formal and actual parameters for indirect forksites.
virtual void connectCaller2CalleeParams (const CallICFGNode *cs, const FunObjVar *F, NodePairSet &cpySrcNodes)
 Connect formal and actual parameters for indirect callsites.
ConstraintGraph * getConstraintGraph ()
 Get constraint graph.
NodeID sccRepNode (NodeID id) const override
 SCC methods.
NodeBS & sccSubNodes (NodeID repId)
virtual bool addCopyEdge (NodeID src, NodeID dst)=0
 Add copy edge on constraint graph.
void printStat ()
 dump statistics
virtual void normalizePointsTo () override
void cleanConsCG (NodeID id)
 remove redundant gepnodes in constraint graph
Public Member Functions inherited from SVF::BVDataPTAImpl
 BVDataPTAImpl (SVFIR *pag, PTATY type, bool alias_check=true)
 Constructor.
 ~BVDataPTAImpl () override=default
 Destructor.
PersistentPointsToCache< PointsTo > & getPtCache ()
const PointsTo & getPts (NodeID id) override
const NodeSet & getRevPts (NodeID nodeId) override
virtual void clearPts (NodeID id, NodeID element)
 Remove element from the points-to set of id.
virtual void clearFullPts (NodeID id)
 Clear points-to set of id.
virtual bool unionPts (NodeID id, const PointsTo &target)
virtual bool unionPts (NodeID id, NodeID ptd)
virtual bool addPts (NodeID id, NodeID ptd)
virtual void clearAllPts ()
 Clear all data.
virtual void expandFIObjs (const PointsTo &pts, PointsTo &expandedPts)
 Expand FI objects.
virtual void expandFIObjs (const NodeBS &pts, NodeBS &expandedPts)
 TODO: remove repetition.
void remapPointsToSets (void)
 Remap all points-to sets to use the current mapping.
virtual void writeToFile (const std::string &filename)
 Interface for analysis result storage on filesystem.
virtual void writeObjVarToFile (const std::string &filename)
virtual void writePtsResultToFile (std::fstream &f)
virtual void writeGepObjVarMapToFile (std::fstream &f)
virtual bool readFromFile (const std::string &filename)
virtual void readPtsResultFromFile (std::ifstream &f)
virtual void readGepObjVarMapFromFile (std::ifstream &f)
virtual void readAndSetObjFieldSensitivity (std::ifstream &f, const std::string &delimiterStr)
AliasResult alias (const SVFVar *V1, const SVFVar *V2) override
 Interface expose to users of our pointer analysis, given Value infos.
AliasResult alias (NodeID node1, NodeID node2) override
 Interface expose to users of our pointer analysis, given PAGNodeID.
virtual AliasResult alias (const PointsTo &pts1, const PointsTo &pts2)
 Interface expose to users of our pointer analysis, given two pts.
bool mayAlias (const PointsTo &pts1, const PointsTo &pts2)
 Convenience bool wrappers: return true if the two operands may/must/partial alias.
void dumpCPts () override
 dump and debug, print out conditional pts
void dumpTopLevelPtsTo () override
void dumpAllPts () override
bool mayAlias (const SVFVar *V1, const SVFVar *V2)
bool mayAlias (NodeID node1, NodeID node2)
Public Member Functions inherited from SVF::PointerAnalysis
ICFG * getICFG () const
 Get ICFG.
u32_t getNumOfResolvedIndCallEdge () const
 Return number of resolved indirect call edges.
CallGraph * getCallGraph () const
 Return call graph.
CallGraphSCC * getCallGraphSCC () const
 Return call graph SCC.
 PointerAnalysis (SVFIR *pag, PTATY ty=PTATY::Default_PTA, bool alias_check=true)
 Constructor.
PTATY getAnalysisTy () const
 Type of pointer analysis.
PTAImplTy getImplTy () const
 Return implementation type of the pointer analysis.
bool printStat ()
 Whether print statistics.
void disablePrintStat ()
 Whether print statistics.
CallEdgeMap & getIndCallMap ()
 Get callees from an indirect callsite.
bool hasIndCSCallees (const CallICFGNode *cs) const
const FunctionSet & getIndCSCallees (const CallICFGNode *cs) const
virtual void resolveIndCalls (const CallICFGNode *cs, const PointsTo &target, CallEdgeMap &newEdges)
 Resolve indirect call edges.
void callGraphSCCDetection ()
 PTACallGraph SCC related methods.
NodeID getCallGraphSCCRepNode (NodeID id) const
 Get SCC rep node of a SVFG node.
bool inSameCallGraphSCC (const FunObjVar *fun1, const FunObjVar *fun2)
 Return TRUE if this edge is inside a PTACallGraph SCC, i.e., src node and dst node are in the same SCC on the SVFG.
bool isInRecursion (const FunObjVar *fun) const
bool isLocalVarInRecursiveFun (NodeID id) const
 Whether a local variable is in function recursions.
virtual const std::string PTAName () const
 Return PTA name.
CommonCHGraph * getCHGraph () const
 get CHGraph
void getVFnsFromCHA (const CallICFGNode *cs, VFunSet &vfns)
void getVFnsFromPts (const CallICFGNode *cs, const PointsTo &target, VFunSet &vfns)
void connectVCallToVFns (const CallICFGNode *cs, const VFunSet &vfns, CallEdgeMap &newEdges)
virtual void resolveCPPIndCalls (const CallICFGNode *cs, const PointsTo &target, CallEdgeMap &newEdges)
 Resolve cpp indirect call edges.
SVFIR * getPAG () const
PTAStat * getStat () const
 Get PTA stat.
OrderedNodeSet & getAllValidPtrs ()
 Get all Valid Pointers for resolution.
virtual ~PointerAnalysis ()
 Destructor.
virtual void computeDDAPts (NodeID)
 Compute points-to results on-demand, overridden by derived classes.
virtual NodeBS getMayAliases (NodeID node)
bool mayAlias (const SVFVar *V1, const SVFVar *V2)
 Convenience bool wrappers: return true if the two operands may/must/partial alias.
bool mayAlias (NodeID node1, NodeID node2)
void printIndCSTargets (const CallICFGNode *cs, const FunctionSet &targets)
 Print targets of a function pointer.
virtual void dumpPts (NodeID ptr, const PointsTo &pts)
void printIndCSTargets ()
void dumpAllTypes ()
void dumpStat ()
 Dump the statistics.
bool containBlackHoleNode (const PointsTo &pts)
 Determine whether a points-to contains a black hole or constant node.
bool containConstantNode (const PointsTo &pts)
virtual bool isBlkObjOrConstantObj (NodeID ptd) const
bool isHeapMemObj (NodeID id) const
 Whether this object is heap or array.
bool isArrayMemObj (NodeID id) const
bool isFIObjNode (NodeID id) const
NodeID getBaseObjVarID (NodeID id)
NodeID getFIObjVar (NodeID id)
NodeID getGepObjVar (NodeID id, const APOffset &ap)
virtual const NodeBS & getAllFieldsObjVars (NodeID id)
void setObjFieldInsensitive (NodeID id)
bool isFieldInsensitive (NodeID id) const

Static Public Member Functions

static bool classof (const AndersenBase *)
 Methods for support type inquiry through isa, cast, and dyn_cast:
static bool classof (const PointerAnalysis *pta)
Static Public Member Functions inherited from SVF::BVDataPTAImpl
static bool classof (const PointerAnalysis *pta)

Public Attributes

NodeBS redundantGepNodes
Public Attributes inherited from SVF::WPASolver< ConstraintGraph * >
u32_t numOfIteration
 num of iterations during constraint solving

Static Public Attributes

static u32_t numOfProcessedAddr = 0
 Statistics.
static u32_t numOfProcessedCopy = 0
 Number of processed Addr edge.
static u32_t numOfProcessedGep = 0
 Number of processed Copy edge.
static u32_t numOfProcessedLoad = 0
 Number of processed Gep edge.
static u32_t numOfProcessedStore = 0
 Number of processed Load edge.
static u32_t numOfSfrs = 0
 Number of processed Store edge.
static u32_t numOfFieldExpand = 0
static u32_t numOfSCCDetection = 0
static double timeOfSCCDetection = 0
static double timeOfSCCMerges = 0
static double timeOfCollapse = 0
static u32_t AveragePointsToSetSize = 0
static u32_t MaxPointsToSetSize = 0
static double timeOfProcessCopyGep = 0
static double timeOfProcessLoadStore = 0
static double timeOfUpdateCallGraph = 0
Static Public Attributes inherited from SVF::PointerAnalysis
static const std::string aliasTestMayAlias = "MAYALIAS"
static const std::string aliasTestMayAliasMangled = "_Z8MAYALIASPvS_"
static const std::string aliasTestNoAlias = "NOALIAS"
static const std::string aliasTestNoAliasMangled = "_Z7NOALIASPvS_"
static const std::string aliasTestPartialAlias = "PARTIALALIAS"
static const std::string aliasTestPartialAliasMangled = "_Z12PARTIALALIASPvS_"
static const std::string aliasTestMustAlias = "MUSTALIAS"
static const std::string aliasTestMustAliasMangled = "_Z9MUSTALIASPvS_"
static const std::string aliasTestFailMayAlias = "EXPECTEDFAIL_MAYALIAS"
static const std::string aliasTestFailMayAliasMangled = "_Z21EXPECTEDFAIL_MAYALIASPvS_"
static const std::string aliasTestFailNoAlias = "EXPECTEDFAIL_NOALIAS"
static const std::string aliasTestFailNoAliasMangled = "_Z20EXPECTEDFAIL_NOALIASPvS_"

Protected Member Functions

void heapAllocatorViaIndCall (const CallICFGNode *cs, NodePairSet &cpySrcNodes)
Protected Member Functions inherited from SVF::WPASolver< ConstraintGraph * >
 WPASolver ()
 Constructor.
virtual ~WPASolver ()=default
 Destructor.
SCC * getSCCDetector () const
 Get SCC detector.
const ConstraintGraph * graph ()
 Get/Set graph methods.
void setGraph (ConstraintGraph *g)
virtual NodeStack & SCCDetect ()
 SCC detection.
virtual NodeStack & SCCDetect (NodeSet &candidates)
virtual void initWorklist ()
virtual void solveWorklist ()
virtual void processNode (NodeID)
 Following methods are to be implemented in child class, in order to achieve a fully worked PTA.
virtual void collapseFields ()
 collapse positive weight cycles of a graph
virtual void propagate (GNODE *v)
virtual bool propFromSrcToDst (GEDGE *)
 Propagate information from source to destination node, to be implemented in the child class.
NodeID popFromWorklist ()
 Worklist operations.
virtual void pushIntoWorklist (NodeID id)
bool isWorklistEmpty ()
bool isInWorklist (NodeID id)
GNODE * Node (NodeID id)
 Get node on the graph.
NodeID Node_Index (GNODE node)
 Get node ID.
PTDataTy * getPTDataTy () const
 Get points-to data structure.
void finalize () override
 Finalization of pointer analysis, and normalize points-to information to Bit Vector representation.
DiffPTDataTy * getDiffPTDataTy () const
DFPTDataTy * getDFPTDataTy () const
MutDFPTDataTy * getMutDFPTDataTy () const
VersionedPTDataTy * getVersionedPTDataTy () const
virtual void onTheFlyCallGraphSolve (const CallSiteToFunPtrMap &callsites, CallEdgeMap &newEdges)
 On the fly call graph construction.
virtual void onTheFlyThreadCallGraphSolve (const CallSiteToFunPtrMap &callsites, CallEdgeMap &newForkEdges)
 On the fly thread call graph construction respecting forksite.
const CallSiteToFunPtrMap & getIndirectCallsites () const
 Return all indirect callsites.
NodeID getFunPtr (const CallICFGNode *cs) const
 Return function pointer PAGNode at a callsite cs.
virtual void validateTests ()
 Alias check functions to verify correctness of pointer analysis.
virtual void validateSuccessTests (std::string fun)
virtual void validateExpectedFailureTests (std::string fun)
void resetObjFieldSensitive ()
 Reset all object node as field-sensitive.

Protected Attributes

ConstraintGraph * consCG
 Constraint Graph.
CallSite2DummyValPN callsite2DummyValPN
Protected Attributes inherited from SVF::WPASolver< ConstraintGraph * >
bool reanalyze
 Reanalyze if any constraint value changed.
u32_t iterationForPrintStat
 print out statistics for i-th iteration
ConstraintGraph * _graph
 Graph.
std::unique_ptr< SCC > scc
 SCC.
WorkList worklist
 Worklist for resolution.
Protected Attributes inherited from SVF::PointerAnalysis
bool print_stat
 User input flags.
bool alias_validation
 Flag for validating points-to/alias results.
u32_t OnTheFlyIterBudgetForStat
 Flag for iteration budget for on-the-fly statistics.
PTATY ptaTy
 Pointer analysis Type.
PTAImplTy ptaImplTy
 PTA implementation type.
PTAStat * stat
 Statistics.
CallGraph * callgraph
 Call graph used for pointer analysis.
CallGraphSCC * callGraphSCC
 SCC for PTACallGraph.
ICFG * icfg
 Interprocedural control-flow graph.
CommonCHGraph * chgraph
 CHGraph.

Additional Inherited Members

Static Protected Attributes inherited from SVF::PointerAnalysis
static SVFIR * pag = nullptr
 SVFIR.

Detailed Description

Definition at line 60 of file Andersen.h.

Member Typedef Documentation

◆ CallSite2DummyValPN

Definition at line 63 of file Andersen.h.

Constructor & Destructor Documentation

◆ AndersenBase()

SVF::AndersenBase::AndersenBase ( SVFIR * _pag,
PTATY type = PTATY::Andersen_BASE,
bool alias_check = true )
inline

Constructor.

Definition at line 68 of file Andersen.h.

69 : BVDataPTAImpl(_pag, type, alias_check), consCG(nullptr)
70 {
72 }
newitem type
Definition cJSON.cpp:2739
ConstraintGraph * consCG
Constraint Graph.
Definition Andersen.h:181
BVDataPTAImpl(SVFIR *pag, PTATY type, bool alias_check=true)
Constructor.
u32_t OnTheFlyIterBudgetForStat
Flag for iteration budget for on-the-fly statistics.

◆ ~AndersenBase()

AndersenBase::~AndersenBase ( )
override

Destructor.

Destructor

Definition at line 73 of file Andersen.cpp.

74{
75 delete consCG;
76 consCG = nullptr;
77}

Member Function Documentation

◆ addCopyEdge()

virtual bool SVF::AndersenBase::addCopyEdge ( NodeID src,
NodeID dst )
pure virtual

Add copy edge on constraint graph.

Implemented in SVF::Andersen, SVF::AndersenSCD, SVF::Steensgaard, and SVF::TypeAnalysis.

◆ analyze()

void AndersenBase::analyze ( )
overridevirtual

Andersen analysis.

Andersen analysis

Implements SVF::PointerAnalysis.

Reimplemented in SVF::TypeAnalysis.

Definition at line 150 of file Andersen.cpp.

151{
152 if(!Options::ReadAnder().empty())
153 {
155 }
156 else
157 {
158 if(Options::WriteAnder().empty())
159 {
160 initialize();
162 finalize();
163 }
164 else
165 {
167 }
168 }
169}
virtual void finalize() override
Finalize analysis.
Definition Andersen.cpp:98
virtual void readPtsFromFile(const std::string &filename)
Definition Andersen.cpp:174
virtual void initialize() override
Initialize analysis.
Definition Andersen.cpp:82
virtual void solveConstraints()
Definition Andersen.cpp:109
virtual void solveAndwritePtsToFile(const std::string &filename)
Definition Andersen.cpp:185
static const Option< std::string > ReadAnder
Definition Options.h:206
static const Option< std::string > WriteAnder
Definition Options.h:204

◆ classof() [1/2]

bool SVF::AndersenBase::classof ( const AndersenBase * )
inlinestatic

Methods for support type inquiry through isa, cast, and dyn_cast:

Definition at line 108 of file Andersen.h.

109 {
110 return true;
111 }

◆ classof() [2/2]

bool SVF::AndersenBase::classof ( const PointerAnalysis * pta)
inlinestatic

Definition at line 112 of file Andersen.h.

113 {
114 return ( pta->getAnalysisTy() == PTATY::Andersen_BASE
115 || pta->getAnalysisTy() == PTATY::Andersen_WPA
116 || pta->getAnalysisTy() == PTATY::AndersenWaveDiff_WPA
117 || pta->getAnalysisTy() == PTATY::AndersenSCD_WPA
118 || pta->getAnalysisTy() == PTATY::AndersenSFR_WPA
119 || pta->getAnalysisTy() == PTATY::TypeCPP_WPA
120 || pta->getAnalysisTy() == PTATY::Steensgaard_WPA);
121 }
@ Andersen_WPA
Andersen PTA.
Definition PTATY.h:12
@ AndersenSFR_WPA
Stride-based field representation.
Definition PTATY.h:14
@ AndersenWaveDiff_WPA
Diff wave propagation andersen-style WPA.
Definition PTATY.h:15
@ TypeCPP_WPA
Type-based analysis for C++.
Definition PTATY.h:26
@ Steensgaard_WPA
Steensgaard PTA.
Definition PTATY.h:16
@ Andersen_BASE
Base Andersen PTA.
Definition PTATY.h:11
@ AndersenSCD_WPA
Selective cycle detection andersen-style WPA.
Definition PTATY.h:13

◆ cleanConsCG()

void AndersenBase::cleanConsCG ( NodeID id)

remove redundant gepnodes in constraint graph

Definition at line 197 of file Andersen.cpp.

198{
199 // Remove only this node from its representative's members. Erasing the whole
200 // member set would leave every other member mapped to a representative that no
201 // longer lists it, so sccSubNodes would stop being the inverse of sccRepNode.
202 consCG->getSubs(consCG->sccRepNode(id)).reset(id);
203 for (NodeID sub: consCG->getSubs(id))
204 consCG->resetRep(sub);
205 consCG->resetSubs(id);
206 consCG->resetRep(id);
207 assert(!consCG->hasGNode(id) && "this is either a rep nodeid or a sub nodeid should have already been merged to its field-insensitive base! ");
208}
u32_t NodeID
Definition GeneralType.h:76

◆ connectCaller2CalleeParams()

void AndersenBase::connectCaller2CalleeParams ( const CallICFGNode * cs,
const FunObjVar * F,
NodePairSet & cpySrcNodes )
virtual

Connect formal and actual parameters for indirect callsites.

Connect formal and actual parameters for indirect callsites

Definition at line 294 of file Andersen.cpp.

296{
297 assert(F);
298
299 DBOUT(DAndersen, outs() << "connect parameters from indirect callsite " << cs->valueOnlyToString() << " to callee " << *F << "\n");
300
301 const CallICFGNode* callBlockNode = cs;
302 const RetICFGNode* retBlockNode = cs->getRetICFGNode();
303
304 if(SVFUtil::isHeapAllocExtFunViaRet(F) && pag->callsiteHasRet(retBlockNode))
305 {
306 heapAllocatorViaIndCall(cs,cpySrcNodes);
307 }
308
309 if (pag->funHasRet(F) && pag->callsiteHasRet(retBlockNode))
310 {
311 const PAGNode* cs_return = pag->getCallSiteRet(retBlockNode);
312 const PAGNode* fun_return = pag->getFunRet(F);
313 if (cs_return->isPointer() && fun_return->isPointer())
314 {
315 NodeID dstrec = sccRepNode(cs_return->getId());
316 NodeID srcret = sccRepNode(fun_return->getId());
317 if(addCopyEdge(srcret, dstrec))
318 {
319 cpySrcNodes.insert(std::make_pair(srcret,dstrec));
320 }
321 }
322 else
323 {
324 DBOUT(DAndersen, outs() << "not a pointer ignored\n");
325 }
326 }
327
328 if (pag->hasCallSiteArgsMap(callBlockNode) && pag->hasFunArgsList(F))
329 {
330
331 // connect actual and formal param
332 const SVFIR::ValVarList& csArgList = pag->getCallSiteArgsList(callBlockNode);
333 const SVFIR::ValVarList& funArgList = pag->getFunArgsList(F);
334 //Go through the fixed parameters.
335 DBOUT(DPAGBuild, outs() << " args:");
336 SVFIR::ValVarList::const_iterator funArgIt = funArgList.begin(), funArgEit = funArgList.end();
337 SVFIR::ValVarList::const_iterator csArgIt = csArgList.begin(), csArgEit = csArgList.end();
338 for (; funArgIt != funArgEit; ++csArgIt, ++funArgIt)
339 {
340 //Some programs (e.g. Linux kernel) leave unneeded parameters empty.
341 if (csArgIt == csArgEit)
342 {
343 DBOUT(DAndersen, outs() << " !! not enough args\n");
344 break;
345 }
346 const PAGNode *cs_arg = *csArgIt ;
347 const PAGNode *fun_arg = *funArgIt;
348
349 if (cs_arg->isPointer() && fun_arg->isPointer())
350 {
351 DBOUT(DAndersen, outs() << "process actual parm " << cs_arg->toString() << " \n");
352 NodeID srcAA = sccRepNode(cs_arg->getId());
353 NodeID dstFA = sccRepNode(fun_arg->getId());
354 if(addCopyEdge(srcAA, dstFA))
355 {
356 cpySrcNodes.insert(std::make_pair(srcAA,dstFA));
357 }
358 }
359 }
360
361 //Any remaining actual args must be varargs.
362 if (F->isVarArg())
363 {
364 NodeID vaF = sccRepNode(pag->getVarargNode(F));
365 DBOUT(DPAGBuild, outs() << "\n varargs:");
366 for (; csArgIt != csArgEit; ++csArgIt)
367 {
368 const PAGNode *cs_arg = *csArgIt;
369 if (cs_arg->isPointer())
370 {
371 NodeID vnAA = sccRepNode(cs_arg->getId());
372 if (addCopyEdge(vnAA,vaF))
373 {
374 cpySrcNodes.insert(std::make_pair(vnAA,vaF));
375 }
376 }
377 }
378 }
379 if(csArgIt != csArgEit)
380 {
381 writeWrnMsg("too many args to non-vararg func.");
382 writeWrnMsg("(" + cs->getSourceLoc() + ")");
383 }
384 }
385}
#define DBOUT(TYPE, X)
LLVM debug macros, define type of your DBUG model of each pass.
Definition SVFType.h:576
#define DPAGBuild
Definition SVFType.h:584
#define DAndersen
Definition SVFType.h:595
void heapAllocatorViaIndCall(const CallICFGNode *cs, NodePairSet &cpySrcNodes)
Definition Andersen.cpp:387
virtual bool addCopyEdge(NodeID src, NodeID dst)=0
Add copy edge on constraint graph.
NodeID sccRepNode(NodeID id) const override
SCC methods.
Definition Andersen.h:132
const RetICFGNode * getRetICFGNode() const
Return callsite.
Definition ICFGNode.h:440
const std::string getSourceLoc() const override
Definition ICFGNode.h:571
bool isVarArg() const
static SVFIR * pag
SVFIR.
std::vector< const ValVar * > ValVarList
Definition SVFIR.h:60
NodeID getId() const
Get ID.
Definition SVFValue.h:158
const std::string valueOnlyToString() const
Definition LLVMUtil.cpp:747
virtual bool isPointer() const
Check if this variable represents a pointer.
virtual const std::string toString() const
Get string representation.
bool isHeapAllocExtFunViaRet(const FunObjVar *fun)
Return true if the call is a heap allocator/reallocator.
Definition SVFUtil.h:284
void writeWrnMsg(const std::string &msg)
Writes a message run through wrnMsg.
Definition SVFUtil.cpp:88
std::ostream & outs()
Overwrite llvm::outs().
Definition SVFUtil.h:58
SVFVar PAGNode
Definition IRGraph.h:40

◆ connectCaller2ForkedFunParams()

void AndersenBase::connectCaller2ForkedFunParams ( const CallICFGNode * cs,
const FunObjVar * F,
NodePairSet & cpySrcNodes )
virtual

Connect formal and actual parameters for indirect forksites.

Connect formal and actual parameters for indirect forksites

Definition at line 264 of file Andersen.cpp.

266{
267 assert(F);
268
269 DBOUT(DAndersen, outs() << "connect parameters from indirect forksite "
270 << cs->valueOnlyToString() << " to forked function "
271 << *F << "\n");
272
273 ThreadCallGraph *tdCallGraph = SVFUtil::dyn_cast<ThreadCallGraph>(callgraph);
274
275 const PAGNode *cs_arg = tdCallGraph->getThreadAPI()->getActualParmAtForkSite(cs);
276 const PAGNode *fun_arg = tdCallGraph->getThreadAPI()->getFormalParmOfForkedFun(F);
277
278 if(cs_arg->isPointer() && fun_arg->isPointer())
279 {
280 DBOUT(DAndersen, outs() << "process actual parm"
281 << cs_arg->toString() << "\n");
282 NodeID srcAA = sccRepNode(cs_arg->getId());
283 NodeID dstFA = sccRepNode(fun_arg->getId());
284 if (addCopyEdge(srcAA, dstFA))
285 {
286 cpySrcNodes.insert(std::make_pair(srcAA, dstFA));
287 }
288 }
289}
CallGraph * callgraph
Call graph used for pointer analysis.
const SVFVar * getFormalParmOfForkedFun(const FunObjVar *F) const
Return the formal parm of forked function (the first arg in pthread).
const ValVar * getActualParmAtForkSite(const CallICFGNode *inst) const
ThreadAPI * getThreadAPI() const
Thread API.
LLVM_NODISCARD std::enable_if_t<!is_simple_type< Y >::value, typename cast_retty< X, const Y >::ret_type > dyn_cast(const Y &Val)
Definition Casting.h:405

◆ finalize()

void AndersenBase::finalize ( )
overridevirtual

Finalize analysis.

Finalize analysis

dump constraint graph if PAGDotGraph flag is enabled

Reimplemented from SVF::PointerAnalysis.

Reimplemented in SVF::Andersen, SVF::AndersenWaveDiff, and SVF::TypeAnalysis.

Definition at line 98 of file Andersen.cpp.

99{
102 consCG->dump("consCG_final");
103
105 consCG->print();
107}
void finalize() override
Finalization of pointer analysis, and normalize points-to information to Bit Vector representation.
static const Option< bool > PrintCGGraph
Definition Options.h:202
static const Option< bool > ConsCGDotGraph
Definition Options.h:200

◆ getConstraintGraph()

ConstraintGraph * SVF::AndersenBase::getConstraintGraph ( )
inline

Get constraint graph.

Definition at line 125 of file Andersen.h.

126 {
127 return consCG;
128 }

◆ heapAllocatorViaIndCall()

void AndersenBase::heapAllocatorViaIndCall ( const CallICFGNode * cs,
NodePairSet & cpySrcNodes )
protected

Definition at line 387 of file Andersen.cpp.

388{
389 assert(cs->getCalledFunction() == nullptr && "not an indirect callsite?");
390 const RetICFGNode* retBlockNode = cs->getRetICFGNode();
391 const PAGNode* cs_return = pag->getCallSiteRet(retBlockNode);
392 NodeID srcret;
393 CallSite2DummyValPN::const_iterator it = callsite2DummyValPN.find(cs);
394 if(it != callsite2DummyValPN.end())
395 {
396 srcret = sccRepNode(it->second);
397 }
398 else
399 {
400 NodeID valNode = pag->addDummyValNode();
401 NodeID objNode = pag->addDummyObjNode(cs->getType());
402 addPts(valNode,objNode);
403 callsite2DummyValPN.insert(std::make_pair(cs,valNode));
404 consCG->addConstraintNode(new ConstraintNode(valNode),valNode);
405 consCG->addConstraintNode(new ConstraintNode(objNode),objNode);
406 srcret = valNode;
407 }
408
409 NodeID dstrec = sccRepNode(cs_return->getId());
410 if(addCopyEdge(srcret, dstrec))
411 cpySrcNodes.insert(std::make_pair(srcret,dstrec));
412}
CallSite2DummyValPN callsite2DummyValPN
Definition Andersen.h:183
virtual bool addPts(NodeID id, NodeID ptd)
const FunObjVar * getCalledFunction() const
Definition ICFGNode.h:501
virtual const SVFType * getType() const
Definition SVFValue.h:169

◆ initialize()

void AndersenBase::initialize ( )
overridevirtual

Initialize analysis.

Initialize analysis

Build SVFIR

Create statistic class

Build Constraint Graph

Reimplemented from SVF::PointerAnalysis.

Reimplemented in SVF::Andersen, SVF::AndersenSFR, SVF::AndersenWaveDiff, and SVF::TypeAnalysis.

Definition at line 82 of file Andersen.cpp.

83{
87 stat = new AndersenStat(this);
89 consCG = new ConstraintGraph(pag);
92 consCG->dump("consCG_initial");
93}
virtual void initialize()
Initialization of a pointer analysis, including building symbol table and SVFIR etc.
PTAStat * stat
Statistics.
void setGraph(ConstraintGraph *g)
Definition WPASolver.h:79

◆ normalizePointsTo()

void AndersenBase::normalizePointsTo ( )
overridevirtual

Normalize points-to information for field-sensitive analysis, i.e., replace fieldObj with baseObj if it is field-insensitive

Normalize points-to information for field-sensitive analysis

Reimplemented from SVF::BVDataPTAImpl.

Definition at line 414 of file Andersen.cpp.

415{
416 SVFIR::MemObjToFieldsMap &memToFieldsMap = pag->getMemToFieldsMap();
417 SVFIR::OffsetToGepVarMap &GepObjVarMap = pag->getGepObjNodeMap();
418
419 // clear GepObjVarMap/memToFieldsMap/nodeToSubsMap/nodeToRepMap
420 // for redundant gepnodes and remove those nodes from pag
422 {
423 NodeID base = pag->getBaseObjVarID(n);
424 const GepObjVar* gepNode = pag->getGepObjVar(n);
425 assert(gepNode && "Not a gep node in redundantGepNodes set");
426 const APOffset apOffset = gepNode->getConstantFieldIdx();
427 GepObjVarMap.erase(std::make_pair(base, apOffset));
428 memToFieldsMap[base].reset(n);
429 cleanConsCG(n);
430
431 pag->removeGNode(const_cast<GepObjVar*>(gepNode));
432 }
433}
cJSON * n
Definition cJSON.cpp:2558
NodeBS redundantGepNodes
Definition Andersen.h:156
void cleanConsCG(NodeID id)
remove redundant gepnodes in constraint graph
Definition Andersen.cpp:197
APOffset getConstantFieldIdx() const
offset of the mem object
Map< NodeID, NodeBS > MemObjToFieldsMap
Definition SVFIR.h:58
Map< GepOffset, NodeID > OffsetToGepVarMap
Definition SVFIR.h:72
s64_t APOffset
Definition GeneralType.h:80

◆ printStat()

void SVF::AndersenBase::printStat ( )
inline

dump statistics

Definition at line 146 of file Andersen.h.

147 {
149 }
void dumpStat()
Dump the statistics.

◆ readPtsFromFile()

void AndersenBase::readPtsFromFile ( const std::string & filename)
virtual

Andersen analysis: read pointer analysis result from file

Definition at line 174 of file Andersen.cpp.

175{
176 initialize();
177 if (!filename.empty())
178 this->readFromFile(filename);
179 finalize();
180}
virtual bool readFromFile(const std::string &filename)

◆ sccRepNode()

NodeID SVF::AndersenBase::sccRepNode ( NodeID id) const
inlineoverridevirtual

SCC methods.

Reimplemented from SVF::WPASolver< ConstraintGraph * >.

Reimplemented in SVF::Steensgaard.

Definition at line 132 of file Andersen.h.

133 {
134 return consCG->sccRepNode(id);
135 }

◆ sccSubNodes()

NodeBS & SVF::AndersenBase::sccSubNodes ( NodeID repId)
inline

Definition at line 136 of file Andersen.h.

137 {
138 return consCG->sccSubNodes(repId);
139 }

◆ solveAndwritePtsToFile()

void AndersenBase::solveAndwritePtsToFile ( const std::string & filename)
virtual

Andersen analysis: solve constraints and write pointer analysis result to file

Initialization for the Solver

Definition at line 185 of file Andersen.cpp.

186{
188 initialize();
189 if (!filename.empty())
190 this->writeObjVarToFile(filename);
192 if (!filename.empty())
193 this->writeToFile(filename);
194 finalize();
195}
virtual void writeToFile(const std::string &filename)
Interface for analysis result storage on filesystem.
virtual void writeObjVarToFile(const std::string &filename)

◆ solveConstraints()

void AndersenBase::solveConstraints ( )
virtual

Definition at line 109 of file Andersen.cpp.

110{
111 // Start solving constraints
112 DBOUT(DGENERAL, outs() << SVFUtil::pasMsg("Start Solving Constraints\n"));
113
114 bool timeLimited = Options::AnderTimeLimit() > 0;
115 if (timeLimited)
116 {
117 assert(Options::FsTimeLimit() == 0 && "both -ander-time-limit and -fs-time-limit set.");
119 }
120
121 initWorklist();
122 do
123 {
126 printStat();
127
128 reanalyze = false;
129
131
133 reanalyze = true;
134
135 }
136 while (reanalyze);
137
138 // Analysis is finished, reset the alarm if we set it.
139 if (timeLimited)
140 {
142 }
143
144 DBOUT(DGENERAL, outs() << SVFUtil::pasMsg("Finish Solving Constraints\n"));
145}
#define DGENERAL
Definition SVFType.h:582
virtual bool updateCallGraph(const CallSiteToFunPtrMap &) override
Update call graph.
Definition Andersen.cpp:210
void printStat()
dump statistics
Definition Andersen.h:146
static const Option< u32_t > AnderTimeLimit
Time limit for the Andersen's analyses.
Definition Options.h:71
static const Option< u32_t > FsTimeLimit
Time limit for the main phase (i.e., the actual solving) of FS analyses.
Definition Options.h:68
const CallSiteToFunPtrMap & getIndirectCallsites() const
Return all indirect callsites.
std::string pasMsg(const std::string &msg)
Print each pass/phase message by converting a string into blue string output.
Definition SVFUtil.cpp:121
void stopAnalysisLimitTimer(void)
Stops analysis timer.
Definition SVFUtil.cpp:383
void startAnalysisLimitTimer(unsigned timeLimit)
Starts analysis timer. timeLimit must be non-0. Timer must not be already set.
Definition SVFUtil.cpp:364

◆ updateCallGraph()

bool AndersenBase::updateCallGraph ( const CallSiteToFunPtrMap & callsites)
overridevirtual

Update call graph.

nodes as a src of a generated new copy edge

Reimplemented from SVF::BVDataPTAImpl.

Reimplemented in SVF::AndersenSCD.

Definition at line 210 of file Andersen.cpp.

211{
212
213 double cgUpdateStart = stat->getClk();
214
215 CallEdgeMap newEdges;
216 onTheFlyCallGraphSolve(callsites, newEdges);
217 NodePairSet cpySrcNodes;
218 for (CallEdgeMap::iterator it = newEdges.begin(), eit = newEdges.end();
219 it != eit; ++it)
220 {
221 for (FunctionSet::iterator cit = it->second.begin(),
222 ecit = it->second.end();
223 cit != ecit; ++cit)
224 {
225 connectCaller2CalleeParams(it->first, *cit, cpySrcNodes);
226 }
227 }
228
229 bool hasNewForkEdges = updateThreadCallGraph(callsites, cpySrcNodes);
230
231 for (NodePairSet::iterator it = cpySrcNodes.begin(),
232 eit = cpySrcNodes.end();
233 it != eit; ++it)
234 {
235 pushIntoWorklist(it->first);
236 }
237
238 double cgUpdateEnd = stat->getClk();
239 timeOfUpdateCallGraph += (cgUpdateEnd - cgUpdateStart) / TIMEINTERVAL;
240
241 return ((!newEdges.empty()) || hasNewForkEdges);
242}
#define TIMEINTERVAL
Definition SVFType.h:604
static double timeOfUpdateCallGraph
Definition Andersen.h:176
virtual void connectCaller2CalleeParams(const CallICFGNode *cs, const FunObjVar *F, NodePairSet &cpySrcNodes)
Connect formal and actual parameters for indirect callsites.
Definition Andersen.cpp:294
virtual bool updateThreadCallGraph(const CallSiteToFunPtrMap &, NodePairSet &)
Update thread call graph.
Definition Andersen.cpp:244
virtual void onTheFlyCallGraphSolve(const CallSiteToFunPtrMap &callsites, CallEdgeMap &newEdges)
On the fly call graph construction.
OrderedMap< const CallICFGNode *, FunctionSet > CallEdgeMap
virtual void pushIntoWorklist(NodeID id)
Definition WPASolver.h:157
Set< NodePair > NodePairSet
Definition GeneralType.h:88

◆ updateThreadCallGraph()

bool AndersenBase::updateThreadCallGraph ( const CallSiteToFunPtrMap & callsites,
NodePairSet & cpySrcNodes )
virtual

Update thread call graph.

Definition at line 244 of file Andersen.cpp.

246{
247 CallEdgeMap newForkEdges;
248 onTheFlyThreadCallGraphSolve(callsites, newForkEdges);
249 for (CallEdgeMap::iterator it = newForkEdges.begin(), eit = newForkEdges.end(); it != eit; it++)
250 {
251 for (FunctionSet::iterator cit = it->second.begin(),
252 ecit = it->second.end();
253 cit != ecit; ++cit)
254 {
255 connectCaller2ForkedFunParams(it->first, *cit, cpySrcNodes);
256 }
257 }
258 return !newForkEdges.empty();
259}
virtual void connectCaller2ForkedFunParams(const CallICFGNode *cs, const FunObjVar *F, NodePairSet &cpySrcNodes)
Connect formal and actual parameters for indirect forksites.
Definition Andersen.cpp:264
virtual void onTheFlyThreadCallGraphSolve(const CallSiteToFunPtrMap &callsites, CallEdgeMap &newForkEdges)
On the fly thread call graph construction respecting forksite.

Member Data Documentation

◆ AveragePointsToSetSize

u32_t AndersenBase::AveragePointsToSetSize = 0
static

Definition at line 172 of file Andersen.h.

◆ callsite2DummyValPN

CallSite2DummyValPN SVF::AndersenBase::callsite2DummyValPN
protected

Map an instruction to a dummy obj which created at an indirect callsite, which invokes a heap allocator

Definition at line 183 of file Andersen.h.

◆ consCG

ConstraintGraph* SVF::AndersenBase::consCG
protected

Constraint Graph.

Definition at line 181 of file Andersen.h.

◆ MaxPointsToSetSize

u32_t AndersenBase::MaxPointsToSetSize = 0
static

Definition at line 173 of file Andersen.h.

◆ numOfFieldExpand

u32_t AndersenBase::numOfFieldExpand = 0
static

Definition at line 166 of file Andersen.h.

◆ numOfProcessedAddr

u32_t AndersenBase::numOfProcessedAddr = 0
static

Statistics.

Definition at line 160 of file Andersen.h.

◆ numOfProcessedCopy

u32_t AndersenBase::numOfProcessedCopy = 0
static

Number of processed Addr edge.

Definition at line 161 of file Andersen.h.

◆ numOfProcessedGep

u32_t AndersenBase::numOfProcessedGep = 0
static

Number of processed Copy edge.

Definition at line 162 of file Andersen.h.

◆ numOfProcessedLoad

u32_t AndersenBase::numOfProcessedLoad = 0
static

Number of processed Gep edge.

Definition at line 163 of file Andersen.h.

◆ numOfProcessedStore

u32_t AndersenBase::numOfProcessedStore = 0
static

Number of processed Load edge.

Definition at line 164 of file Andersen.h.

◆ numOfSCCDetection

u32_t AndersenBase::numOfSCCDetection = 0
static

Definition at line 168 of file Andersen.h.

◆ numOfSfrs

u32_t AndersenBase::numOfSfrs = 0
static

Number of processed Store edge.

Definition at line 165 of file Andersen.h.

◆ redundantGepNodes

NodeBS SVF::AndersenBase::redundantGepNodes

Definition at line 156 of file Andersen.h.

◆ timeOfCollapse

double AndersenBase::timeOfCollapse = 0
static

Definition at line 171 of file Andersen.h.

◆ timeOfProcessCopyGep

double AndersenBase::timeOfProcessCopyGep = 0
static

Definition at line 174 of file Andersen.h.

◆ timeOfProcessLoadStore

double AndersenBase::timeOfProcessLoadStore = 0
static

Definition at line 175 of file Andersen.h.

◆ timeOfSCCDetection

double AndersenBase::timeOfSCCDetection = 0
static

Definition at line 169 of file Andersen.h.

◆ timeOfSCCMerges

double AndersenBase::timeOfSCCMerges = 0
static

Definition at line 170 of file Andersen.h.

◆ timeOfUpdateCallGraph

double AndersenBase::timeOfUpdateCallGraph = 0
static

Definition at line 176 of file Andersen.h.


The documentation for this class was generated from the following files: