Static Value-Flow Analysis
|
#include <TypeAnalysis.h>
Public Member Functions | |
TypeAnalysis (SVFIR *pag) | |
Constructor. More... | |
virtual | ~TypeAnalysis () |
Destructor. More... | |
void | analyze () override |
Type analysis. More... | |
void | initialize () override |
Initialize analysis. More... | |
virtual void | finalize () override |
Finalize analysis. More... | |
bool | addCopyEdge (NodeID src, NodeID dst) override |
Add copy edge on constraint graph. More... | |
void | callGraphSolveBasedOnCHA (const CallSiteToFunPtrMap &callsites, CallEdgeMap &newEdges) |
Resolve callgraph based on CHA. More... | |
void | dumpCHAStats () |
Statistics of CHA and callgraph. More... | |
Public Member Functions inherited from SVF::AndersenBase | |
AndersenBase (SVFIR *_pag, PTATY type=Andersen_BASE, bool alias_check=true) | |
Constructor. More... | |
~AndersenBase () override | |
Destructor. More... | |
virtual void | solveAndwritePtsToFile (const std::string &filename) |
virtual void | readPtsFromFile (const std::string &filename) |
virtual void | solveConstraints () |
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) |
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 TypeAnalysis *) |
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::AndersenBase | |
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) |
Additional Inherited Members | |
Public Types inherited from SVF::AndersenBase | |
typedef OrderedMap< const CallICFGNode *, NodeID > | CallSite2DummyValPN |
Public Types inherited from SVF::WPASolver< GraphType > | |
typedef SVF::GenericGraphTraits< GraphType > | GTraits |
Define the GTraits and node iterator for printing. More... | |
typedef GTraits::NodeRef | GNODE |
typedef GTraits::EdgeType | GEDGE |
typedef GTraits::ChildIteratorType | child_iterator |
typedef SCCDetection< GraphType > | SCC |
typedef FIFOWorkList< NodeID > | WorkList |
Public Types inherited from SVF::BVDataPTAImpl | |
enum | PTBackingType { Mutable , Persistent } |
How the PTData used is implemented. More... | |
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 | |
enum | PTATY { Andersen_BASE , Andersen_WPA , AndersenSCD_WPA , AndersenSFR_WPA , AndersenWaveDiff_WPA , Steensgaard_WPA , CSCallString_WPA , CSSummary_WPA , FSDATAFLOW_WPA , FSSPARSE_WPA , VFS_WPA , FSCS_WPA , CFLFICI_WPA , CFLFSCI_WPA , CFLFSCS_WPA , TypeCPP_WPA , FieldS_DDA , FlowS_DDA , PathS_DDA , Cxt_DDA , Default_PTA } |
Pointer analysis type list. More... | |
enum | PTAImplTy { BaseImpl , BVDataImpl , CondImpl } |
Implementation type: BVDataPTAImpl or CondPTAImpl. More... | |
typedef Set< const CallICFGNode * > | CallSiteSet |
Indirect call edges type, map a callsite to a set of callees. More... | |
typedef SVFIR::CallSiteToFunPtrMap | CallSiteToFunPtrMap |
typedef Set< const SVFFunction * > | FunctionSet |
typedef OrderedMap< const CallICFGNode *, FunctionSet > | CallEdgeMap |
typedef SCCDetection< PTACallGraph * > | CallGraphSCC |
typedef Set< const SVFGlobalValue * > | VTableSet |
typedef Set< const SVFFunction * > | VFunSet |
Public Attributes inherited from SVF::AndersenBase | |
NodeBS | redundantGepNodes |
Public Attributes inherited from SVF::WPASolver< GraphType > | |
u32_t | numOfIteration |
num of iterations during constraint solving More... | |
Static Public Attributes inherited from SVF::AndersenBase | |
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 inherited from SVF::AndersenBase | |
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 inherited from SVF::AndersenBase | |
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... | |
Static Protected Attributes inherited from SVF::PointerAnalysis | |
static SVFIR * | pag = nullptr |
SVFIR. More... | |
Definition at line 38 of file TypeAnalysis.h.
|
inline |
Constructor.
Definition at line 43 of file TypeAnalysis.h.
|
inlinevirtual |
Add copy edge on constraint graph.
Implements SVF::AndersenBase.
Definition at line 63 of file TypeAnalysis.h.
|
overridevirtual |
Type analysis.
Reimplemented from SVF::AndersenBase.
Definition at line 67 of file TypeAnalysis.cpp.
void TypeAnalysis::callGraphSolveBasedOnCHA | ( | const CallSiteToFunPtrMap & | callsites, |
CallEdgeMap & | newEdges | ||
) |
Resolve callgraph based on CHA.
Definition at line 75 of file TypeAnalysis.cpp.
|
inlinestatic |
Definition at line 81 of file TypeAnalysis.h.
|
inlinestatic |
Methods for support type inquiry through isa, cast, and dyn_cast:
Definition at line 77 of file TypeAnalysis.h.
void TypeAnalysis::dumpCHAStats | ( | ) |
Statistics of CHA and callgraph.
Definition at line 93 of file TypeAnalysis.cpp.
|
inlineoverridevirtual |
Finalize analysis.
Reimplemented from SVF::AndersenBase.
Definition at line 60 of file TypeAnalysis.cpp.
|
overridevirtual |
Initialize analysis.
Reimplemented from SVF::AndersenBase.
Definition at line 43 of file TypeAnalysis.cpp.