|
Static Value-Flow Analysis
|
#include <Andersen.h>
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. | |
Definition at line 60 of file Andersen.h.
| typedef OrderedMap<const CallICFGNode*, NodeID> SVF::AndersenBase::CallSite2DummyValPN |
Definition at line 63 of file Andersen.h.
|
inline |
Constructor.
Definition at line 68 of file Andersen.h.
|
override |
Add copy edge on constraint graph.
Implemented in SVF::Andersen, SVF::AndersenSCD, SVF::Steensgaard, and SVF::TypeAnalysis.
|
overridevirtual |
Andersen analysis.
Andersen analysis
Implements SVF::PointerAnalysis.
Reimplemented in SVF::TypeAnalysis.
Definition at line 150 of file Andersen.cpp.
|
inlinestatic |
Methods for support type inquiry through isa, cast, and dyn_cast:
Definition at line 108 of file Andersen.h.
|
inlinestatic |
Definition at line 112 of file Andersen.h.
| void AndersenBase::cleanConsCG | ( | NodeID | id | ) |
remove redundant gepnodes in constraint graph
Definition at line 197 of file Andersen.cpp.
|
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.
|
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.
|
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.
|
inline |
|
protected |
Definition at line 387 of file Andersen.cpp.
|
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.
|
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.
|
inline |
dump statistics
Definition at line 146 of file Andersen.h.
|
virtual |
Andersen analysis: read pointer analysis result from file
Definition at line 174 of file Andersen.cpp.
SCC methods.
Reimplemented from SVF::WPASolver< ConstraintGraph * >.
Reimplemented in SVF::Steensgaard.
Definition at line 132 of file Andersen.h.
Definition at line 136 of file Andersen.h.
|
virtual |
Andersen analysis: solve constraints and write pointer analysis result to file
Initialization for the Solver
Definition at line 185 of file Andersen.cpp.
|
virtual |
Definition at line 109 of file Andersen.cpp.
|
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.
|
virtual |
Update thread call graph.
Definition at line 244 of file Andersen.cpp.
|
static |
Definition at line 172 of file Andersen.h.
|
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.
|
protected |
Constraint Graph.
Definition at line 181 of file Andersen.h.
|
static |
Definition at line 173 of file Andersen.h.
|
static |
Definition at line 166 of file Andersen.h.
|
static |
Statistics.
Definition at line 160 of file Andersen.h.
|
static |
Number of processed Addr edge.
Definition at line 161 of file Andersen.h.
|
static |
Number of processed Copy edge.
Definition at line 162 of file Andersen.h.
|
static |
Number of processed Gep edge.
Definition at line 163 of file Andersen.h.
|
static |
Number of processed Load edge.
Definition at line 164 of file Andersen.h.
|
static |
Definition at line 168 of file Andersen.h.
|
static |
Number of processed Store edge.
Definition at line 165 of file Andersen.h.
| NodeBS SVF::AndersenBase::redundantGepNodes |
Definition at line 156 of file Andersen.h.
|
static |
Definition at line 171 of file Andersen.h.
|
static |
Definition at line 174 of file Andersen.h.
|
static |
Definition at line 175 of file Andersen.h.
|
static |
Definition at line 169 of file Andersen.h.
|
static |
Definition at line 170 of file Andersen.h.
|
static |
Definition at line 176 of file Andersen.h.