Static Value-Flow Analysis
|
#include <Steensgaard.h>
Public Member Functions | |
Steensgaard (SVFIR *_pag) | |
Constructor. More... | |
virtual void | solveWorklist () override |
void | processAllAddr () |
void | ecUnion (NodeID id, NodeID ec) |
merge node into equiv class and merge node's pts into ec's pts More... | |
virtual const PointsTo & | getPts (NodeID id) override |
Operation of points-to set. More... | |
virtual bool | unionPts (NodeID id, const PointsTo &target) override |
pts(id) = pts(id) U target More... | |
virtual bool | unionPts (NodeID id, NodeID ptd) override |
pts(id) = pts(id) U pts(ptd) More... | |
NodeID | getEC (NodeID id) const |
NodeID | sccRepNode (NodeID id) const override |
Return getEC(id) More... | |
void | setEC (NodeID node, NodeID rep) |
Set< NodeID > & | getSubNodes (NodeID id) |
void | addSubNode (NodeID node, NodeID sub) |
virtual bool | addCopyEdge (NodeID src, NodeID dst) override |
Add copy edge on constraint graph. 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 | 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... | |
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 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 | 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 Steensgaard * | createSteensgaard (SVFIR *_pag) |
Create an singleton instance. More... | |
static void | releaseSteensgaard () |
static bool | classof (const Steensgaard *) |
Methods for support type inquiry through isa, cast, and dyn_cast: More... | |
static bool | classof (const AndersenBase *pta) |
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) |
Private Attributes | |
NodeToEquivClassMap | nodeToECMap |
NodeToSubsMap | nodeToSubsMap |
Static Private Attributes | |
static Steensgaard * | steens = nullptr |
Additional Inherited Members | |
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 | 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 20 of file Steensgaard.h.
typedef Map<NodeID, NodeID> SVF::Steensgaard::NodeToEquivClassMap |
Definition at line 24 of file Steensgaard.h.
typedef Map<NodeID, Set<NodeID> > SVF::Steensgaard::NodeToSubsMap |
Definition at line 25 of file Steensgaard.h.
|
inline |
Constructor.
Definition at line 28 of file Steensgaard.h.
Add copy edge on constraint graph.
Implements SVF::AndersenBase.
Definition at line 118 of file Steensgaard.h.
Definition at line 112 of file Steensgaard.h.
|
inlinestatic |
Definition at line 60 of file Steensgaard.h.
|
inlinestatic |
Definition at line 64 of file Steensgaard.h.
|
inlinestatic |
Methods for support type inquiry through isa, cast, and dyn_cast:
Definition at line 56 of file Steensgaard.h.
|
inlinestatic |
Create an singleton instance.
Definition at line 31 of file Steensgaard.h.
merge node into equiv class and merge node's pts into ec's pts
Definition at line 95 of file Steensgaard.cpp.
API for equivalence class operations Every constraint node maps to an unique equivalence class EC An equivalence class has a set of sub constraint nodes.
Definition at line 92 of file Steensgaard.h.
Operation of points-to set.
Reimplemented from SVF::BVDataPTAImpl.
Definition at line 71 of file Steensgaard.h.
Definition at line 107 of file Steensgaard.h.
void Steensgaard::processAllAddr | ( | ) |
Process address edges
Definition at line 105 of file Steensgaard.cpp.
|
inlinestatic |
Definition at line 41 of file Steensgaard.h.
Return getEC(id)
Reimplemented from SVF::AndersenBase.
Definition at line 101 of file Steensgaard.h.
Definition at line 82 of file Steensgaard.cpp.
|
overridevirtual |
Steensgaard analysis
foreach o \in pts(p)
*p = q : EC(o) == EC(q)
q = p : EC(q) == EC(p)
q = &p->f : EC(q) == EC(p)
Reimplemented from SVF::WPASolver< GraphType >.
Definition at line 42 of file Steensgaard.cpp.
|
inlineoverridevirtual |
pts(id) = pts(id) U target
Reimplemented from SVF::BVDataPTAImpl.
Definition at line 76 of file Steensgaard.h.
pts(id) = pts(id) U pts(ptd)
Reimplemented from SVF::BVDataPTAImpl.
Definition at line 82 of file Steensgaard.h.
|
private |
Definition at line 125 of file Steensgaard.h.
|
private |
Definition at line 126 of file Steensgaard.h.
|
staticprivate |
Definition at line 124 of file Steensgaard.h.