Static Value-Flow Analysis
|
#include <Andersen.h>
Public Member Functions | |
AndersenBase (SVFIR *_pag, PTATY type=Andersen_BASE, bool alias_check=true) | |
Constructor. More... | |
~AndersenBase () override | |
Destructor. More... | |
virtual void | analyze () override |
Andersen analysis. More... | |
virtual void | solveAndwritePtsToFile (const std::string &filename) |
virtual void | readPtsFromFile (const std::string &filename) |
virtual void | solveConstraints () |
virtual void | initialize () override |
Initialize analysis. More... | |
virtual void | finalize () override |
Finalize analysis. More... | |
virtual bool | updateCallGraph (const CallSiteToFunPtrMap &) override |
Update call graph. More... | |
virtual bool | updateThreadCallGraph (const CallSiteToFunPtrMap &, NodePairSet &) |
Update thread call graph. More... | |
virtual void | connectCaller2ForkedFunParams (const CallICFGNode *cs, const SVFFunction *F, NodePairSet &cpySrcNodes) |
Connect formal and actual parameters for indirect forksites. More... | |
virtual void | connectCaller2CalleeParams (const CallICFGNode *cs, const SVFFunction *F, NodePairSet &cpySrcNodes) |
Connect formal and actual parameters for indirect callsites. More... | |
ConstraintGraph * | getConstraintGraph () |
Get constraint graph. More... | |
NodeID | sccRepNode (NodeID id) const override |
SCC methods. More... | |
NodeBS & | sccSubNodes (NodeID repId) |
virtual bool | addCopyEdge (NodeID src, NodeID dst)=0 |
Add copy edge on constraint graph. More... | |
void | printStat () |
dump statistics More... | |
virtual void | normalizePointsTo () override |
void | cleanConsCG (NodeID id) |
remove redundant gepnodes in constraint graph More... | |
Public Member Functions inherited from SVF::BVDataPTAImpl | |
BVDataPTAImpl (SVFIR *pag, PointerAnalysis::PTATY type, bool alias_check=true) | |
Constructor. More... | |
~BVDataPTAImpl () override=default | |
Destructor. More... | |
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. More... | |
virtual void | clearFullPts (NodeID id) |
Clear points-to set of id. More... | |
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. More... | |
virtual void | expandFIObjs (const PointsTo &pts, PointsTo &expandedPts) |
Expand FI objects. More... | |
virtual void | expandFIObjs (const NodeBS &pts, NodeBS &expandedPts) |
TODO: remove repetition. More... | |
void | remapPointsToSets (void) |
Remap all points-to sets to use the current mapping. More... | |
virtual void | writeToFile (const std::string &filename) |
Interface for analysis result storage on filesystem. More... | |
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 SVFValue *V1, const SVFValue *V2) override |
Interface expose to users of our pointer analysis, given Value infos. More... | |
AliasResult | alias (NodeID node1, NodeID node2) override |
Interface expose to users of our pointer analysis, given PAGNodeID. More... | |
virtual AliasResult | alias (const PointsTo &pts1, const PointsTo &pts2) |
Interface expose to users of our pointer analysis, given two pts. More... | |
void | dumpCPts () override |
dump and debug, print out conditional pts More... | |
void | dumpTopLevelPtsTo () override |
void | dumpAllPts () override |
Public Member Functions inherited from SVF::PointerAnalysis | |
ICFG * | getICFG () const |
Get ICFG. More... | |
u32_t | getNumOfResolvedIndCallEdge () const |
Return number of resolved indirect call edges. More... | |
PTACallGraph * | getCallGraph () const |
Return call graph. More... | |
CallGraphSCC * | getCallGraphSCC () const |
Return call graph SCC. More... | |
PointerAnalysis (SVFIR *pag, PTATY ty=Default_PTA, bool alias_check=true) | |
Constructor. More... | |
PTATY | getAnalysisTy () const |
Type of pointer analysis. More... | |
PTAImplTy | getImplTy () const |
Return implementation type of the pointer analysis. More... | |
bool | printStat () |
Whether print statistics. More... | |
void | disablePrintStat () |
Whether print statistics. More... | |
CallEdgeMap & | getIndCallMap () |
Get callees from an indirect callsite. More... | |
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. More... | |
void | callGraphSCCDetection () |
PTACallGraph SCC related methods. More... | |
NodeID | getCallGraphSCCRepNode (NodeID id) const |
Get SCC rep node of a SVFG node. More... | |
bool | inSameCallGraphSCC (const SVFFunction *fun1, const SVFFunction *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. More... | |
bool | isInRecursion (const SVFFunction *fun) const |
bool | isLocalVarInRecursiveFun (NodeID id) const |
Whether a local variable is in function recursions. More... | |
virtual const std::string | PTAName () const |
Return PTA name. More... | |
CommonCHGraph * | getCHGraph () const |
get CHGraph More... | |
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. More... | |
SVFIR * | getPAG () const |
PTAStat * | getStat () const |
Get PTA stat. More... | |
SVFModule * | getModule () const |
Module. More... | |
OrderedNodeSet & | getAllValidPtrs () |
Get all Valid Pointers for resolution. More... | |
virtual | ~PointerAnalysis () |
Destructor. More... | |
virtual void | computeDDAPts (NodeID) |
Compute points-to results on-demand, overridden by derived classes. More... | |
void | printIndCSTargets (const CallICFGNode *cs, const FunctionSet &targets) |
Print targets of a function pointer. More... | |
virtual void | dumpPts (NodeID ptr, const PointsTo &pts) |
void | printIndCSTargets () |
void | dumpAllTypes () |
void | dumpStat () |
Dump the statistics. More... | |
bool | containBlackHoleNode (const PointsTo &pts) |
Determine whether a points-to contains a black hole or constant node. More... | |
bool | containConstantNode (const PointsTo &pts) |
virtual bool | isBlkObjOrConstantObj (NodeID ptd) const |
bool | isHeapMemObj (NodeID id) const |
Whether this object is heap or array. More... | |
bool | isArrayMemObj (NodeID id) const |
bool | isFIObjNode (NodeID id) const |
NodeID | getBaseObjVar (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: More... | |
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< GraphType > | |
u32_t | numOfIteration |
num of iterations during constraint solving More... | |
Static Public Attributes | |
static u32_t | numOfProcessedAddr = 0 |
Statistics. More... | |
static u32_t | numOfProcessedCopy = 0 |
Number of processed Addr edge. More... | |
static u32_t | numOfProcessedGep = 0 |
Number of processed Copy edge. More... | |
static u32_t | numOfProcessedLoad = 0 |
Number of processed Gep edge. More... | |
static u32_t | numOfProcessedStore = 0 |
Number of processed Load edge. More... | |
static u32_t | numOfSfrs = 0 |
Number of processed Store edge. More... | |
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< GraphType > | |
WPASolver () | |
Constructor. More... | |
virtual | ~WPASolver ()=default |
Destructor. More... | |
SCC * | getSCCDetector () const |
Get SCC detector. More... | |
const GraphType | graph () |
Get/Set graph methods. More... | |
void | setGraph (GraphType g) |
virtual NodeStack & | SCCDetect () |
SCC detection. More... | |
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. More... | |
virtual void | collapseFields () |
collapse positive weight cycles of a graph More... | |
virtual void | propagate (GNODE *v) |
virtual bool | propFromSrcToDst (GEDGE *) |
Propagate information from source to destination node, to be implemented in the child class. More... | |
NodeID | popFromWorklist () |
Worklist operations. More... | |
virtual void | pushIntoWorklist (NodeID id) |
bool | isWorklistEmpty () |
bool | isInWorklist (NodeID id) |
GNODE * | Node (NodeID id) |
Get node on the graph. More... | |
NodeID | Node_Index (GNODE node) |
Get node ID. More... | |
Protected Member Functions inherited from SVF::BVDataPTAImpl | |
PTDataTy * | getPTDataTy () const |
Get points-to data structure. More... | |
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. More... | |
virtual void | onTheFlyThreadCallGraphSolve (const CallSiteToFunPtrMap &callsites, CallEdgeMap &newForkEdges) |
On the fly thread call graph construction respecting forksite. More... | |
Protected Member Functions inherited from SVF::PointerAnalysis | |
const CallSiteToFunPtrMap & | getIndirectCallsites () const |
Return all indirect callsites. More... | |
NodeID | getFunPtr (const CallICFGNode *cs) const |
Return function pointer PAGNode at a callsite cs. More... | |
virtual void | validateTests () |
Alias check functions to verify correctness of pointer analysis. More... | |
virtual void | validateSuccessTests (std::string fun) |
virtual void | validateExpectedFailureTests (std::string fun) |
void | resetObjFieldSensitive () |
Reset all object node as field-sensitive. More... | |
Protected Attributes | |
ConstraintGraph * | consCG |
Constraint Graph. More... | |
CallSite2DummyValPN | callsite2DummyValPN |
Protected Attributes inherited from SVF::WPASolver< GraphType > | |
bool | reanalyze |
Reanalyze if any constraint value changed. More... | |
u32_t | iterationForPrintStat |
print out statistics for i-th iteration More... | |
GraphType | _graph |
Graph. More... | |
std::unique_ptr< SCC > | scc |
SCC. More... | |
WorkList | worklist |
Worklist for resolution. More... | |
Protected Attributes inherited from SVF::PointerAnalysis | |
bool | print_stat |
User input flags. More... | |
bool | alias_validation |
Flag for validating points-to/alias results. More... | |
u32_t | OnTheFlyIterBudgetForStat |
Flag for iteration budget for on-the-fly statistics. More... | |
SVFModule * | svfMod |
Module. More... | |
PTATY | ptaTy |
Pointer analysis Type. More... | |
PTAImplTy | ptaImplTy |
PTA implementation type. More... | |
PTAStat * | stat |
Statistics. More... | |
PTACallGraph * | callgraph |
Call graph used for pointer analysis. More... | |
CallGraphSCC * | callGraphSCC |
SCC for PTACallGraph. More... | |
ICFG * | icfg |
Interprocedural control-flow graph. More... | |
CommonCHGraph * | chgraph |
CHGraph. More... | |
Additional Inherited Members | |
Static Protected Attributes inherited from SVF::PointerAnalysis | |
static SVFIR * | pag = nullptr |
SVFIR. More... | |
Definition at line 57 of file Andersen.h.
typedef OrderedMap<const CallICFGNode*, NodeID> SVF::AndersenBase::CallSite2DummyValPN |
Definition at line 60 of file Andersen.h.
|
inline |
Constructor.
Definition at line 65 of file Andersen.h.
|
override |
Add copy edge on constraint graph.
Implemented in SVF::TypeAnalysis, SVF::Steensgaard, SVF::AndersenSCD, and SVF::Andersen.
|
overridevirtual |
Andersen analysis.
Andersen analysis
Implements SVF::PointerAnalysis.
Reimplemented in SVF::TypeAnalysis.
Definition at line 133 of file Andersen.cpp.
|
inlinestatic |
Methods for support type inquiry through isa, cast, and dyn_cast:
Definition at line 105 of file Andersen.h.
|
inlinestatic |
Definition at line 109 of file Andersen.h.
void AndersenBase::cleanConsCG | ( | NodeID | id | ) |
remove redundant gepnodes in constraint graph
Definition at line 180 of file Andersen.cpp.
|
virtual |
Connect formal and actual parameters for indirect callsites.
|
virtual |
Connect formal and actual parameters for indirect forksites.
Connect formal and actual parameters for indirect forksites
Definition at line 244 of file Andersen.cpp.
|
overridevirtual |
Finalize analysis.
Finalize analysis
dump constraint graph if PAGDotGraph flag is enabled
Reimplemented from SVF::BVDataPTAImpl.
Reimplemented in SVF::TypeAnalysis, and SVF::Andersen.
Definition at line 89 of file Andersen.cpp.
|
inline |
|
protected |
|
overridevirtual |
Initialize analysis.
Initialize analysis
Build SVFIR
Create statistic class
Build Constraint Graph
Reimplemented from SVF::PointerAnalysis.
Reimplemented in SVF::TypeAnalysis, SVF::AndersenSFR, SVF::AndersenWaveDiff, and SVF::Andersen.
Definition at line 73 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.
|
inline |
dump statistics
Definition at line 143 of file Andersen.h.
|
virtual |
Andersen analysis: read pointer analysis result from file
Definition at line 157 of file Andersen.cpp.
SCC methods.
Reimplemented from SVF::WPASolver< GraphType >.
Reimplemented in SVF::Steensgaard.
Definition at line 129 of file Andersen.h.
Definition at line 133 of file Andersen.h.
|
virtual |
Andersen analysis: solve constraints and write pointer analysis result to file
Initialization for the Solver
Definition at line 168 of file Andersen.cpp.
|
virtual |
Definition at line 100 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 190 of file Andersen.cpp.
|
virtual |
Update thread call graph.
Definition at line 224 of file Andersen.cpp.
|
static |
Definition at line 169 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 180 of file Andersen.h.
|
protected |
Constraint Graph.
Definition at line 178 of file Andersen.h.
|
static |
Definition at line 170 of file Andersen.h.
|
static |
Definition at line 163 of file Andersen.h.
|
static |
Statistics.
Definition at line 157 of file Andersen.h.
|
static |
Number of processed Addr edge.
Definition at line 158 of file Andersen.h.
|
static |
Number of processed Copy edge.
Definition at line 159 of file Andersen.h.
|
static |
Number of processed Gep edge.
Definition at line 160 of file Andersen.h.
|
static |
Number of processed Load edge.
Definition at line 161 of file Andersen.h.
|
static |
Definition at line 165 of file Andersen.h.
|
static |
Number of processed Store edge.
Definition at line 162 of file Andersen.h.
NodeBS SVF::AndersenBase::redundantGepNodes |
Definition at line 153 of file Andersen.h.
|
static |
Definition at line 168 of file Andersen.h.
|
static |
Definition at line 171 of file Andersen.h.
|
static |
Definition at line 172 of file Andersen.h.
|
static |
Definition at line 166 of file Andersen.h.
|
static |
Definition at line 167 of file Andersen.h.
|
static |
Definition at line 173 of file Andersen.h.