|
Static Value-Flow Analysis
|
#include <AndersenPWC.h>
Public Member Functions | |
| AndersenSFR (SVFIR *_pag, PTATY type=PTATY::AndersenSFR_WPA) | |
| ~AndersenSFR () | |
| Public Member Functions inherited from SVF::AndersenSCD | |
| AndersenSCD (SVFIR *_pag, PTATY type=PTATY::AndersenSCD_WPA) | |
| Public Member Functions inherited from SVF::Andersen | |
| Andersen (SVFIR *_pag, PTATY type=PTATY::Andersen_WPA, bool alias_check=true) | |
| Constructor. | |
| virtual | ~Andersen () |
| Destructor. | |
| virtual void | finalize () |
| Finalize analysis. | |
| void | resetData () |
| Reset data. | |
| virtual const PointsTo & | getPts (NodeID id) |
| Operation of points-to set. | |
| virtual bool | unionPts (NodeID id, const PointsTo &target) |
| virtual bool | unionPts (NodeID id, NodeID ptd) |
| virtual NodeBS | getMayAliases (NodeID node) |
| Collect exactly the SVFIR nodes q for which mayAlias(node, q) holds. | |
| std::vector< NodeBS > | getMayAliasesBatch (const std::vector< NodeID > &nodes) |
| void | dumpTopLevelPtsTo () |
| void | setDetectPWC (bool flag) |
| Public Member Functions inherited from SVF::AndersenBase | |
| 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 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) |
| 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 | 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. | |
| 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. | |
| 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 AndersenSFR * | createAndersenSFR (SVFIR *_pag) |
| Create an singleton instance directly instead of invoking llvm pass manager. | |
| static void | releaseAndersenSFR () |
| Static Public Member Functions inherited from SVF::AndersenSCD | |
| static AndersenSCD * | createAndersenSCD (SVFIR *_pag) |
| Create an singleton instance directly instead of invoking llvm pass manager. | |
| static void | releaseAndersenSCD () |
| Static Public Member Functions inherited from SVF::Andersen | |
| static bool | classof (const Andersen *) |
| Methods for support type inquiry through isa, cast, and dyn_cast: | |
| static bool | classof (const PointerAnalysis *pta) |
| Static Public Member Functions inherited from SVF::AndersenBase | |
| 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) |
Protected Member Functions | |
| void | initialize () |
| Initialize analysis. | |
| void | PWCDetect () |
| void | fieldExpand (NodeSet &initials, APOffset offset, NodeBS &strides, PointsTo &expandPts) |
| bool | processGepPts (const PointsTo &pts, const GepCGEdge *edge) |
| bool | mergeSrcToTgt (NodeID nodeId, NodeID newRepId) |
| Protected Member Functions inherited from SVF::AndersenSCD | |
| void | addSccCandidate (NodeID nodeId) |
| virtual NodeStack & | SCCDetect () |
| virtual void | solveWorklist () |
| virtual void | handleLoadStore (ConstraintNode *node) |
| virtual void | processAddr (const AddrCGEdge *addr) |
| virtual bool | addCopyEdge (NodeID src, NodeID dst) |
| virtual bool | updateCallGraph (const CallSiteToFunPtrMap &callsites) |
| virtual void | processPWC (ConstraintNode *rep) |
| virtual void | handleCopyGep (ConstraintNode *node) |
| Protected Member Functions inherited from SVF::Andersen | |
| virtual void | computeDiffPts (NodeID id) |
| Handle diff points-to set. | |
| virtual const PointsTo & | getDiffPts (NodeID id) |
| void | updatePropaPts (NodeID dstId, NodeID srcId) |
| Handle propagated points-to set. | |
| void | clearPropaPts (NodeID src) |
| virtual void | initWorklist () |
| virtual void | processNode (NodeID nodeId) |
| Override WPASolver function in order to use the default solver. | |
| void | processAllAddr () |
| handling various constraints | |
| virtual bool | processLoad (NodeID node, const ConstraintEdge *load) |
| virtual bool | processStore (NodeID node, const ConstraintEdge *load) |
| virtual bool | processCopy (NodeID node, const ConstraintEdge *edge) |
| virtual bool | processGep (NodeID node, const GepCGEdge *edge) |
| virtual void | mergeNodeToRep (NodeID nodeId, NodeID newRepId) |
| Merge sub node to its rep. | |
| void | mergeSccNodes (NodeID repNodeId, const NodeBS &subNodes) |
| Merge sub node in a SCC cycle to their rep node. | |
| void | mergeSccCycle () |
| virtual void | collapsePWCNode (NodeID nodeId) |
| Collapse a field object into its base for field insensitive analysis. | |
| void | collapseFields () |
| collapse positive weight cycles of a graph | |
| bool | collapseNodePts (NodeID nodeId) |
| bool | collapseField (NodeID nodeId) |
| void | updateNodeRepAndSubs (NodeID nodeId, NodeID newRepId) |
| Updates subnodes of its rep, and rep node of its subs. | |
| std::optional< NodeBS > | collectMayAliasesFromIndex (const PointsTo &expandedPts) |
| virtual void | validateSuccessTests (std::string fun) |
| Also check getMayAliases on the pointers that the alias tests use. | |
| void | sanitizePts () |
| Sanitize pts for field insensitive objects. | |
| virtual const std::string | PTAName () const |
| Get PTA name. | |
| virtual void | cluster (void) const |
| Protected Member Functions inherited from SVF::AndersenBase | |
| 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 (NodeSet &candidates) |
| 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 | validateExpectedFailureTests (std::string fun) |
| void | resetObjFieldSensitive () |
| Reset all object node as field-sensitive. | |
Private Attributes | |
| CSC * | csc |
| NodeSet | sfrObjNodes |
| FieldReps | fieldReps |
Static Private Attributes | |
| static AndersenSFR * | sfrAndersen = nullptr |
Additional Inherited Members | |
| Public Attributes inherited from SVF::AndersenBase | |
| NodeBS | redundantGepNodes |
| Public Attributes inherited from SVF::WPASolver< ConstraintGraph * > | |
| u32_t | numOfIteration |
| num of iterations during constraint solving | |
| Static Public Attributes inherited from SVF::AndersenBase | |
| 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 Attributes inherited from SVF::AndersenSCD | |
| NodeSet | sccCandidates |
| NodeToNodeMap | pwcReps |
| Protected Attributes inherited from SVF::Andersen | |
| CallSite2DummyValPN | callsite2DummyValPN |
| Map an instruction to a dummy obj which created at an indirect callsite, which invokes a heap allocator. | |
| Protected Attributes inherited from SVF::AndersenBase | |
| 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. | |
| Static Protected Attributes inherited from SVF::AndersenSCD | |
| static AndersenSCD * | scdAndersen = nullptr |
| Static Protected Attributes inherited from SVF::PointerAnalysis | |
| static SVFIR * | pag = nullptr |
| SVFIR. | |
Selective Cycle Detection with Stride-based Field Representation
Definition at line 104 of file AndersenPWC.h.
| typedef Map<NodeID, NodeSet> SVF::AndersenSFR::FieldReps |
Definition at line 108 of file AndersenPWC.h.
| typedef Map<NodeID, NodeBS> SVF::AndersenSFR::NodeStrides |
Definition at line 107 of file AndersenPWC.h.
| typedef Map<NodeID, std::pair<NodeID, NodeSet> > SVF::AndersenSFR::SFRTrait |
Definition at line 109 of file AndersenPWC.h.
|
inline |
Definition at line 119 of file AndersenPWC.h.
|
inline |
Definition at line 142 of file AndersenPWC.h.
|
inlinestatic |
Create an singleton instance directly instead of invoking llvm pass manager.
Definition at line 125 of file AndersenPWC.h.
|
protected |
Expand field IDs in target pts based on the initials and offsets
Definition at line 120 of file AndersenSFR.cpp.
|
protectedvirtual |
Initialize analysis.
Initialize analysis
Detect and collapse cycles consisting of only copy edges
Initialize worklist
Reimplemented from SVF::Andersen.
Definition at line 42 of file AndersenSFR.cpp.
merge nodeId to newRepId. Return true if the newRepId is a PWC node
union pts of node to rep
move the edges from node to rep, and remove the node
set rep and sub relations
Reimplemented from SVF::Andersen.
Definition at line 69 of file AndersenSFR.cpp.
Propagate point-to set via a gep edge, using SFR
Reimplemented from SVF::Andersen.
Definition at line 84 of file AndersenSFR.cpp.
|
protectedvirtual |
Call the PWC stride calculation method of class CSC.
Reimplemented from SVF::AndersenSCD.
Definition at line 59 of file AndersenSFR.cpp.
|
inlinestatic |
Definition at line 136 of file AndersenPWC.h.
|
private |
Definition at line 114 of file AndersenPWC.h.
|
private |
Definition at line 116 of file AndersenPWC.h.
|
staticprivate |
Definition at line 112 of file AndersenPWC.h.
|
private |
Definition at line 115 of file AndersenPWC.h.