Static Value-Flow Analysis
|
#include <VersionedFlowSensitive.h>
Classes | |
class | SCC |
Public Member Functions | |
VersionedFlowSensitive (SVFIR *_pag, PTATY type=VFS_WPA) | |
Constructor. More... | |
virtual void | initialize () override |
Initialize analysis. More... | |
virtual void | finalize () override |
Finalize analysis. More... | |
virtual const std::string | PTAName () const override |
Get PTA name. More... | |
Public Member Functions inherited from SVF::FlowSensitive | |
FlowSensitive (SVFIR *_pag, PTATY type=FSSPARSE_WPA) | |
Constructor. More... | |
~FlowSensitive () override=default | |
Destructor. More... | |
virtual bool | runOnModule (SVFModule *) |
We start from here. More... | |
void | analyze () override |
Flow sensitive analysis. More... | |
virtual void | solveConstraints () |
SVFG * | getSVFG () const |
Return SVFG. More... | |
Public Member Functions inherited from SVF::WPAFSSolver< GraphType > | |
WPAFSSolver () | |
Constructor. More... | |
virtual | ~WPAFSSolver () |
Destructor. More... | |
virtual NodeID | sccRepNode (NodeID id) const |
SCC methods. 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... | |
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 VersionedVar | atKey (NodeID, Version) |
Return key into vPtD for address-taken var of a specific version. More... | |
static bool | classof (const VersionedFlowSensitive *) |
Methods to support type inquiry through isa, cast, and dyn_cast. More... | |
static bool | classof (const PointerAnalysis *pta) |
static VersionedFlowSensitive * | createVFSWPA (SVFIR *_pag) |
Create single instance of versioned flow-sensitive points-to analysis. More... | |
static void | releaseVFSWPA () |
Release flow-sensitive pointer analysis. More... | |
Static Public Member Functions inherited from SVF::FlowSensitive | |
static FlowSensitive * | createFSWPA (SVFIR *_pag) |
Create single instance of flow-sensitive pointer analysis. More... | |
static void | releaseFSWPA () |
Release flow-sensitive pointer analysis. More... | |
static bool | classof (const FlowSensitive *) |
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) |
Static Public Attributes | |
static const Version | invalidVersion = 0 |
If this version appears, there has been an error. More... | |
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 | |
virtual bool | processLoad (const LoadSVFGNode *load) override |
virtual bool | processStore (const StoreSVFGNode *store) override |
virtual void | processNode (NodeID n) override |
Handle various constraints. More... | |
virtual void | updateConnectedNodes (const SVFGEdgeSetTy &newEdges) override |
Update nodes connected during updating call graph. More... | |
virtual bool | propAlongIndirectEdge (const IndirectSVFGEdge *) override |
Override to do nothing. Instead, we will use propagateVersion when necessary. More... | |
virtual void | cluster (void) override |
Override since we want to assign different weights based on versioning. More... | |
Protected Member Functions inherited from SVF::FlowSensitive | |
NodeStack & | SCCDetect () override |
SCC detection. More... | |
bool | propFromSrcToDst (SVFGEdge *edge) override |
Propagation. More... | |
virtual bool | propAlongDirectEdge (const DirectSVFGEdge *edge) |
Propagate points-to information along a DIRECT SVFG edge. More... | |
virtual bool | propVarPtsFromSrcToDst (NodeID var, const SVFGNode *src, const SVFGNode *dst) |
Propagate points-to information of a certain variable from src to dst. More... | |
virtual bool | propagateFromAPToFP (const ActualParmSVFGNode *ap, const SVFGNode *dst) |
virtual bool | propagateFromFRToAR (const FormalRetSVFGNode *fr, const SVFGNode *dst) |
virtual bool | weakUpdateOutFromIn (const SVFGNode *node) |
Handle weak updates. More... | |
virtual bool | strongUpdateOutFromIn (const SVFGNode *node, NodeID singleton) |
Handle strong updates. More... | |
bool | propVarPtsAfterCGUpdated (NodeID var, const SVFGNode *src, const SVFGNode *dst) |
virtual bool | propDFOutToIn (const SVFGNode *srcStmt, NodeID srcVar, const SVFGNode *dstStmt, NodeID dstVar) |
virtual bool | propDFInToIn (const SVFGNode *srcStmt, NodeID srcVar, const SVFGNode *dstStmt, NodeID dstVar) |
bool | updateOutFromIn (const SVFGNode *srcStmt, NodeID srcVar, const SVFGNode *dstStmt, NodeID dstVar) |
Update data-flow points-to data. More... | |
virtual bool | updateInFromIn (const SVFGNode *srcStmt, NodeID srcVar, const SVFGNode *dstStmt, NodeID dstVar) |
virtual bool | updateInFromOut (const SVFGNode *srcStmt, NodeID srcVar, const SVFGNode *dstStmt, NodeID dstVar) |
virtual bool | unionPtsFromIn (const SVFGNode *stmt, NodeID srcVar, NodeID dstVar) |
virtual bool | unionPtsFromTop (const SVFGNode *stmt, NodeID srcVar, NodeID dstVar) |
void | clearAllDFOutVarFlag (const SVFGNode *stmt) |
bool | processSVFGNode (SVFGNode *node) |
virtual bool | processAddr (const AddrSVFGNode *addr) |
virtual bool | processCopy (const CopySVFGNode *copy) |
virtual bool | processPhi (const PHISVFGNode *phi) |
virtual bool | processGep (const GepSVFGNode *edge) |
bool | updateCallGraph (const CallSiteToFunPtrMap &callsites) override |
Update call graph. More... | |
void | connectCallerAndCallee (const CallEdgeMap &newEdges, SVFGEdgeSetTy &edges) |
Connect nodes in SVFG. More... | |
bool | isStrongUpdate (const SVFGNode *node, NodeID &singleton) |
Return TRUE if this is a strong update STORE statement. More... | |
virtual void | countAliases (Set< std::pair< NodeID, NodeID >> cmp, unsigned *mayAliases, unsigned *noAliases) |
Fills may/noAliases for the location/pointer pairs in cmp. More... | |
const PointsTo & | getDFInPtsSet (const SVFGNode *stmt, const NodeID node) |
Get points-to set for a node from data flow IN/OUT set at a statement. More... | |
const PointsTo & | getDFOutPtsSet (const SVFGNode *stmt, const NodeID node) |
virtual void | plainMap (void) const |
Sets the global best mapping as a plain mapping, i.e. n -> n. More... | |
void | svfgStat () |
const DFInOutMap & | getDFInputMap () const |
const DFInOutMap & | getDFOutputMap () const |
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 (NodeSet &candidates) |
virtual void | initWorklist () |
virtual void | solveWorklist () |
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... | |
virtual void | normalizePointsTo () |
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... | |
Private Types | |
typedef CoreBitVector | MeldVersion |
Private Member Functions | |
void | prelabel (void) |
Prelabel the SVFG: set y(o) for stores and c(o) for delta nodes to a new version. More... | |
void | meldLabel (void) |
Meld label the prelabeled SVFG. More... | |
void | removeAllIndirectSVFGEdges (void) |
Removes all indirect edges in the SVFG. More... | |
void | propagateVersion (NodeID o, Version v) |
void | propagateVersion (const NodeID o, const Version v, const Version vp, bool time=true) |
virtual void | buildIsStoreLoadMaps (void) |
Fills in isStoreMap and isLoadMap. More... | |
virtual bool | isStore (const NodeID l) const |
Returns true if l is a store node. More... | |
virtual bool | isLoad (const NodeID l) const |
Returns true if l is a load node. More... | |
virtual void | buildDeltaMaps (void) |
Fills in deltaMap and deltaSourceMap for the SVFG. More... | |
virtual bool | delta (const NodeID l) const |
virtual bool | deltaSource (const NodeID l) const |
Version | getVersion (const NodeID l, const NodeID o, const LocVersionMap &lvm) const |
Shared code for getConsume and getYield. They wrap this function. More... | |
Version | getConsume (const NodeID l, const NodeID o) const |
Returns the consumed version of o at l. If no such version exists, returns invalidVersion. More... | |
Version | getYield (const NodeID l, const NodeID o) const |
Returns the yielded version of o at l. If no such version exists, returns invalidVersion. More... | |
void | setVersion (const NodeID l, const NodeID o, const Version v, LocVersionMap &lvm) |
Shared code for setConsume and setYield. They wrap this function. More... | |
void | setConsume (const NodeID l, const NodeID o, const Version v) |
Sets the consumed version of o at l to v. More... | |
void | setYield (const NodeID l, const NodeID o, const Version v) |
Sets the yielded version of o at l to v. More... | |
std::vector< Version > & | getReliantVersions (const NodeID o, const Version v) |
Returns the versions of o which rely on o:v. More... | |
NodeBS & | getStmtReliance (const NodeID o, const Version v) |
Returns the statements which rely on o:v. More... | |
void | dumpReliances (void) const |
Dumps versionReliance and stmtReliance. More... | |
void | dumpLocVersionMaps (void) const |
Dumps maps consume and yield. More... | |
void | solveAndwritePtsToFile (const std::string &filename) override |
void | writeVersionedAnalysisResultToFile (const std::string &filename) |
void | readVersionedAnalysisResultFromFile (std::ifstream &F) |
void | readPtsFromFile (const std::string &filename) override |
Static Private Member Functions | |
static bool | meld (MeldVersion &mv1, const MeldVersion &mv2) |
Melds v2 into v1 (in place), returns whether a change occurred. More... | |
static void | dumpMeldVersion (MeldVersion &v) |
Dumps a MeldVersion to stdout. More... | |
Private Attributes | |
LocVersionMap | consume |
LocVersionMap | yield |
Actual yield map. Yield analogue to consume. More... | |
VersionRelianceMap | versionReliance |
o -> (version -> versions which rely on it). More... | |
Map< NodeID, Map< Version, NodeBS > > | stmtReliance |
o x version -> statement nodes which rely on that o/version. More... | |
VarToPropNodeMap | versionedVarToPropNode |
Map< NodeID, NodeID > | equivalentObject |
FIFOWorkList< NodeID > | vWorklist |
Set< NodeID > | prelabeledObjects |
BVDataPTAImpl::VersionedPTDataTy * | vPtD |
Points-to DS for working with versions. More... | |
std::vector< bool > | deltaMap |
std::vector< bool > | deltaSourceMap |
std::vector< bool > | isStoreMap |
isStoreMap[l] means SVFG node l is a store node. More... | |
std::vector< bool > | isLoadMap |
isLoadMap[l] means SVFG node l is a load node. More... | |
u32_t | numPrelabeledNodes |
Additional statistics. More... | |
u32_t | numPrelabelVersions |
Number of versions created during prelabeling. More... | |
double | prelabelingTime |
Time to prelabel SVFG. More... | |
double | meldLabelingTime |
Time to meld label SVFG. More... | |
double | versionPropTime |
Time to propagate versions to versions which rely on them. More... | |
Static Private Attributes | |
static VersionedFlowSensitive * | vfspta = nullptr |
Friends | |
class | VersionedFlowSensitiveStat |
Additional Inherited Members | |
Public Attributes inherited from SVF::WPASolver< GraphType > | |
u32_t | numOfIteration |
num of iterations during constraint solving More... | |
Protected Types inherited from SVF::FlowSensitive | |
typedef SVFG::SVFGEdgeSetTy | SVFGEdgeSetTy |
Protected Attributes inherited from SVF::FlowSensitive | |
SVFG * | svfg |
SVFGBuilder | memSSA |
AndersenWaveDiff * | ander |
std::vector< std::pair< hclust_fast_methods, std::vector< NodeID > > > | candidateMappings |
Save candidate mappings for evaluation's sake. More... | |
u32_t | numOfProcessedAddr |
Statistics. More... | |
u32_t | numOfProcessedCopy |
Number of processed Addr node. More... | |
u32_t | numOfProcessedGep |
Number of processed Copy node. More... | |
u32_t | numOfProcessedPhi |
Number of processed Gep node. More... | |
u32_t | numOfProcessedLoad |
Number of processed Phi node. More... | |
u32_t | numOfProcessedStore |
Number of processed Load node. More... | |
u32_t | numOfProcessedActualParam |
Number of processed Store node. More... | |
u32_t | numOfProcessedFormalRet |
Number of processed actual param node. More... | |
u32_t | numOfProcessedMSSANode |
Number of processed formal ret node. More... | |
u32_t | maxSCCSize |
Number of processed mssa node. More... | |
u32_t | numOfSCC |
u32_t | numOfNodesInSCC |
double | solveTime |
time of solve. More... | |
double | sccTime |
time of SCC detection. More... | |
double | processTime |
time of processNode. More... | |
double | propagationTime |
time of points-to propagation. More... | |
double | directPropaTime |
time of points-to propagation of address-taken objects More... | |
double | indirectPropaTime |
time of points-to propagation of top-level pointers More... | |
double | updateTime |
time of strong/weak updates. More... | |
double | addrTime |
time of handling address edges More... | |
double | copyTime |
time of handling copy edges More... | |
double | gepTime |
time of handling gep edges More... | |
double | loadTime |
time of load edges More... | |
double | storeTime |
time of store edges More... | |
double | phiTime |
time of phi nodes. More... | |
double | updateCallGraphTime |
time of updating call graph More... | |
NodeBS | svfgHasSU |
Protected Attributes inherited from SVF::WPAFSSolver< GraphType > | |
NodeStack | nodeStack |
stack used for processing nodes. More... | |
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... | |
Static Protected Attributes inherited from SVF::FlowSensitive | |
static std::unique_ptr< FlowSensitive > | fspta |
Static Protected Attributes inherited from SVF::PointerAnalysis | |
static SVFIR * | pag = nullptr |
SVFIR. More... | |
Versioned flow sensitive whole program pointer analysis
Definition at line 32 of file VersionedFlowSensitive.h.
typedef std::vector<ObjToVersionMap> SVF::VersionedFlowSensitive::LocVersionMap |
Definition at line 43 of file VersionedFlowSensitive.h.
|
private |
Definition at line 37 of file VersionedFlowSensitive.h.
Definition at line 40 of file VersionedFlowSensitive.h.
typedef Map<VersionedVar, const DummyVersionPropSVFGNode *> SVF::VersionedFlowSensitive::VarToPropNodeMap |
Definition at line 41 of file VersionedFlowSensitive.h.
typedef Map<NodeID, Map<Version, std::vector<Version> > > SVF::VersionedFlowSensitive::VersionRelianceMap |
(o -> (v -> versions with rely on o:v).
Definition at line 45 of file VersionedFlowSensitive.h.
Constructor.
Definition at line 30 of file VersionedFlowSensitive.cpp.
|
static |
Return key into vPtD for address-taken var of a specific version.
Definition at line 24 of file VersionedFlowSensitive.cpp.
|
privatevirtual |
Fills in deltaMap and deltaSourceMap for the SVFG.
use pre-analysis call graph to approximate all potential callsites
Definition at line 467 of file VersionedFlowSensitive.cpp.
|
privatevirtual |
Fills in isStoreMap and isLoadMap.
Definition at line 444 of file VersionedFlowSensitive.cpp.
|
inlinestatic |
Definition at line 74 of file VersionedFlowSensitive.h.
|
inlinestatic |
Methods to support type inquiry through isa, cast, and dyn_cast.
Definition at line 70 of file VersionedFlowSensitive.h.
|
overrideprotectedvirtual |
Override since we want to assign different weights based on versioning.
Reimplemented from SVF::FlowSensitive.
Definition at line 780 of file VersionedFlowSensitive.cpp.
|
inlinestatic |
Create single instance of versioned flow-sensitive points-to analysis.
Definition at line 81 of file VersionedFlowSensitive.h.
|
privatevirtual |
Returns true if l is a delta node, i.e., may get a new incoming indirect edge due to on-the-fly callgraph construction.
Definition at line 432 of file VersionedFlowSensitive.cpp.
|
privatevirtual |
Returns true if l is a delta-source node, i.e., may get a new outgoing indirect edge to a delta node due to on-the-fly callgraph construction.
Definition at line 438 of file VersionedFlowSensitive.cpp.
|
private |
Dumps maps consume and yield.
Definition at line 907 of file VersionedFlowSensitive.cpp.
|
staticprivate |
|
private |
Dumps versionReliance and stmtReliance.
Definition at line 850 of file VersionedFlowSensitive.cpp.
|
overridevirtual |
Finalize analysis.
Reimplemented from SVF::FlowSensitive.
Definition at line 65 of file VersionedFlowSensitive.cpp.
Returns the consumed version of o at l. If no such version exists, returns invalidVersion.
Definition at line 810 of file VersionedFlowSensitive.cpp.
|
private |
Returns the versions of o which rely on o:v.
Definition at line 840 of file VersionedFlowSensitive.cpp.
Returns the statements which rely on o:v.
Definition at line 845 of file VersionedFlowSensitive.cpp.
|
private |
Shared code for getConsume and getYield. They wrap this function.
Definition at line 800 of file VersionedFlowSensitive.cpp.
Returns the yielded version of o at l. If no such version exists, returns invalidVersion.
Definition at line 815 of file VersionedFlowSensitive.cpp.
|
overridevirtual |
Initialize analysis.
Reimplemented from SVF::FlowSensitive.
Definition at line 45 of file VersionedFlowSensitive.cpp.
|
privatevirtual |
Returns true if l is a load node.
Definition at line 461 of file VersionedFlowSensitive.cpp.
|
privatevirtual |
|
staticprivate |
Melds v2 into v1 (in place), returns whether a change occurred.
Definition at line 426 of file VersionedFlowSensitive.cpp.
|
private |
Meld label the prelabeled SVFG.
Definition at line 120 of file VersionedFlowSensitive.cpp.
|
private |
Prelabel the SVFG: set y(o) for stores and c(o) for delta nodes to a new version.
Definition at line 73 of file VersionedFlowSensitive.cpp.
|
overrideprotectedvirtual |
Process load node
Foreach node \in src pts(dst) = union pts(node)
If o is a field-insensitive object, we should also get all field nodes' points-to sets and pass them to p.
If the ptd is a field-insensitive node, we should also get all field nodes' points-to sets and pass them to pagDst.
Reimplemented from SVF::FlowSensitive.
Definition at line 647 of file VersionedFlowSensitive.cpp.
|
overrideprotectedvirtual |
Handle various constraints.
Process each SVFG node
Reimplemented from SVF::FlowSensitive.
Definition at line 590 of file VersionedFlowSensitive.cpp.
|
overrideprotectedvirtual |
Process store node
foreach node \in dst pts(node) = union pts(src)
STORE statement can only be processed if the pointer on the LHS points to something. If we handle STORE with an empty points-to set, the OUT set will be updated from IN set. Then if LHS pointer points-to one target and it has been identified as a strong update, we can't remove those points-to information computed before this strong update from the OUT set.
check if this is a strong updates store
Reimplemented from SVF::FlowSensitive.
Definition at line 693 of file VersionedFlowSensitive.cpp.
|
private |
Propagates version v of o to version vp of o. time indicates whether it should record time taken itself.
Definition at line 560 of file VersionedFlowSensitive.cpp.
Propagates version v of o to any version of o which relies on v when o/v is changed. Recursively applies to reliant versions till no new changes are made. Adds any statements which rely on any changes made to the worklist.
Definition at line 546 of file VersionedFlowSensitive.cpp.
|
inlineoverrideprotectedvirtual |
Override to do nothing. Instead, we will use propagateVersion when necessary.
Reimplemented from SVF::FlowSensitive.
Definition at line 106 of file VersionedFlowSensitive.h.
|
inlineoverridevirtual |
Get PTA name.
Reimplemented from SVF::FlowSensitive.
Definition at line 63 of file VersionedFlowSensitive.h.
|
overrideprivatevirtual |
Initialization for the Solver
Load the pts from file
finalize the analysis
Reimplemented from SVF::FlowSensitive.
Definition at line 961 of file VersionedFlowSensitive.cpp.
|
private |
Definition at line 1065 of file VersionedFlowSensitive.cpp.
|
inlinestatic |
Release flow-sensitive pointer analysis.
Definition at line 93 of file VersionedFlowSensitive.h.
|
private |
Removes all indirect edges in the SVFG.
Definition at line 524 of file VersionedFlowSensitive.cpp.
Sets the consumed version of o at l to v.
Definition at line 828 of file VersionedFlowSensitive.cpp.
|
private |
Shared code for setConsume and setYield. They wrap this function.
Definition at line 822 of file VersionedFlowSensitive.cpp.
|
overrideprivatevirtual |
Start analysis
Initialization for the Solver
finalize the analysis
Initialization for the Solver
finalize the analysis
Reimplemented from SVF::FlowSensitive.
Definition at line 997 of file VersionedFlowSensitive.cpp.
|
overrideprotectedvirtual |
Update nodes connected during updating call graph.
Push nodes connected during update call graph into worklist so they will be solved during next iteration.
If this is a formal-param or actual-ret node, we need to solve this phi node in next iteration
If this is a formal-in or actual-out node, we need to propagate points-to information from its predecessor node.
If this is a field-insensitive obj, propagate all field node's pts
Reimplemented from SVF::FlowSensitive.
Definition at line 605 of file VersionedFlowSensitive.cpp.
|
private |
Definition at line 1013 of file VersionedFlowSensitive.cpp.
|
friend |
Definition at line 34 of file VersionedFlowSensitive.h.
|
private |
Maps locations to objects to a version. The object version is what is consumed at that location.
Definition at line 197 of file VersionedFlowSensitive.h.
|
private |
deltaMap[l] means SVFG node l is a delta node, i.e., may get new incoming edges due to OTF callgraph construction.
Definition at line 226 of file VersionedFlowSensitive.h.
|
private |
deltaSourceMap[l] means SVFG node l may be a source to a delta node through an dge added as a result of on-the-fly callgraph construction.
Definition at line 231 of file VersionedFlowSensitive.h.
Definition at line 213 of file VersionedFlowSensitive.h.
|
static |
If this version appears, there has been an error.
Definition at line 48 of file VersionedFlowSensitive.h.
|
private |
isLoadMap[l] means SVFG node l is a load node.
Definition at line 237 of file VersionedFlowSensitive.h.
|
private |
isStoreMap[l] means SVFG node l is a store node.
Definition at line 234 of file VersionedFlowSensitive.h.
|
private |
Time to meld label SVFG.
Definition at line 245 of file VersionedFlowSensitive.h.
|
private |
Additional statistics.
Number of prelabeled nodes.
Definition at line 241 of file VersionedFlowSensitive.h.
|
private |
Number of versions created during prelabeling.
Definition at line 242 of file VersionedFlowSensitive.h.
Definition at line 219 of file VersionedFlowSensitive.h.
|
private |
Time to prelabel SVFG.
Definition at line 244 of file VersionedFlowSensitive.h.
o x version -> statement nodes which rely on that o/version.
Definition at line 204 of file VersionedFlowSensitive.h.
|
private |
Maps an <object, version> pair to the SVFG node indicating that pair needs to be propagated.
Definition at line 208 of file VersionedFlowSensitive.h.
|
private |
Time to propagate versions to versions which rely on them.
Definition at line 246 of file VersionedFlowSensitive.h.
|
private |
o -> (version -> versions which rely on it).
Definition at line 202 of file VersionedFlowSensitive.h.
|
staticprivate |
Definition at line 249 of file VersionedFlowSensitive.h.
|
private |
Points-to DS for working with versions.
Definition at line 222 of file VersionedFlowSensitive.h.
|
private |
Worklist for performing meld labeling, takes SVFG node l. Nodes are added when the version they yield is changed.
Definition at line 217 of file VersionedFlowSensitive.h.
|
private |
Actual yield map. Yield analogue to consume.
Definition at line 199 of file VersionedFlowSensitive.h.