Static Value-Flow Analysis
|
#include <VFG.h>
Public Member Functions | |
VFG (PTACallGraph *callgraph, VFGK k=FULLSVFG) | |
Constructor. More... | |
virtual | ~VFG () |
Destructor. More... | |
VFGK | getKind () const |
Get VFG kind. More... | |
bool | isPtrOnlySVFG () const |
Return true if this VFG only contains pointer related SVFGNodes for pointer analysis. More... | |
SVFIR * | getPAG () const |
Return SVFIR. More... | |
PTACallGraph * | getCallGraph () const |
Return PTACallGraph. More... | |
VFGNode * | getVFGNode (NodeID id) const |
Get a VFG node. More... | |
bool | hasVFGNode (NodeID id) const |
Whether has the VFGNode. More... | |
GlobalVFGNodeSet & | getGlobalVFGNodes () |
Return global stores. More... | |
VFGEdge * | getIntraVFGEdge (const VFGNode *src, const VFGNode *dst, VFGEdge::VFGEdgeK kind) |
Get a SVFG edge according to src and dst. More... | |
void | dump (const std::string &file, bool simple=false) |
Dump graph into dot file. More... | |
void | view () |
Dump graph into dot file. More... | |
void | updateCallGraph (PointerAnalysis *pta) |
Update VFG based on pointer analysis results. More... | |
virtual void | connectCallerAndCallee (const CallICFGNode *cs, const SVFFunction *callee, VFGEdgeSetTy &edges) |
Connect VFG nodes between caller and callee for indirect call site. More... | |
CallSiteID | getCallSiteID (const CallICFGNode *cs, const SVFFunction *func) const |
Get callsite given a callsiteID. More... | |
const CallICFGNode * | getCallSite (CallSiteID id) const |
const VFGNode * | getDefVFGNode (const PAGNode *pagNode) const |
Given a pagNode, return its definition site. More... | |
const PAGNode * | getLHSTopLevPtr (const VFGNode *node) const |
StmtVFGNode * | getStmtVFGNode (const PAGEdge *pagEdge) const |
Get an VFGNode. More... | |
IntraPHIVFGNode * | getIntraPHIVFGNode (const PAGNode *pagNode) const |
BinaryOPVFGNode * | getBinaryOPVFGNode (const PAGNode *pagNode) const |
UnaryOPVFGNode * | getUnaryOPVFGNode (const PAGNode *pagNode) const |
BranchVFGNode * | getBranchVFGNode (const PAGNode *pagNode) const |
CmpVFGNode * | getCmpVFGNode (const PAGNode *pagNode) const |
ActualParmVFGNode * | getActualParmVFGNode (const PAGNode *aparm, const CallICFGNode *cs) const |
ActualRetVFGNode * | getActualRetVFGNode (const PAGNode *aret) const |
FormalParmVFGNode * | getFormalParmVFGNode (const PAGNode *fparm) const |
FormalRetVFGNode * | getFormalRetVFGNode (const PAGNode *fret) const |
const SVFFunction * | isFunEntryVFGNode (const VFGNode *node) const |
Whether a node is function entry VFGNode. More... | |
bool | hasBlackHoleConstObjAddrAsDef (const PAGNode *pagNode) const |
Whether a PAGNode has a blackhole or const object as its definition. More... | |
VFGEdge * | addIntraDirectVFEdge (NodeID srcId, NodeID dstId) |
VFGEdge * | addCallEdge (NodeID srcId, NodeID dstId, CallSiteID csId) |
VFGEdge * | addRetEdge (NodeID srcId, NodeID dstId, CallSiteID csId) |
void | removeVFGEdge (VFGEdge *edge) |
Remove a SVFG edge. More... | |
void | removeVFGNode (VFGNode *node) |
Remove a VFGNode. More... | |
VFGEdge * | hasIntraVFGEdge (VFGNode *src, VFGNode *dst, VFGEdge::VFGEdgeK kind) |
Whether we has a SVFG edge. More... | |
VFGEdge * | hasInterVFGEdge (VFGNode *src, VFGNode *dst, VFGEdge::VFGEdgeK kind, CallSiteID csId) |
VFGEdge * | hasThreadVFGEdge (VFGNode *src, VFGNode *dst, VFGEdge::VFGEdgeK kind) |
bool | addVFGEdge (VFGEdge *edge) |
Add VFG edge. More... | |
VFGNodeSet & | getVFGNodes (const SVFFunction *fun) |
bool | hasVFGNodes (const SVFFunction *fun) const |
bool | VFGNodes (const SVFFunction *fun) const |
VFGNodeSet::const_iterator | getVFGNodeBegin (const SVFFunction *fun) const |
VFGNodeSet::const_iterator | getVFGNodeEnd (const SVFFunction *fun) const |
Public Member Functions inherited from SVF::GenericGraph< NodeTy, EdgeTy > | |
GenericGraph () | |
Constructor. More... | |
virtual | ~GenericGraph () |
Destructor. More... | |
void | destroy () |
Release memory. More... | |
iterator | begin () |
Iterators. More... | |
iterator | end () |
const_iterator | begin () const |
const_iterator | end () const |
void | addGNode (NodeID id, NodeType *node) |
Add a Node. More... | |
NodeType * | getGNode (NodeID id) const |
Get a node. More... | |
bool | hasGNode (NodeID id) const |
Has a node. More... | |
void | removeGNode (NodeType *node) |
Delete a node. More... | |
u32_t | getTotalNodeNum () const |
Get total number of node/edge. More... | |
u32_t | getTotalEdgeNum () const |
void | incNodeNum () |
Increase number of node/edge. More... | |
void | incEdgeNum () |
Protected Member Functions | |
void | destroy () |
Clean up memory. More... | |
void | checkIntraEdgeParents (const VFGNode *srcNode, const VFGNode *dstNode) |
sanitize Intra edges, verify that both nodes belong to the same function. More... | |
VFGEdge * | addInterEdgeFromAPToFP (ActualParmVFGNode *src, FormalParmVFGNode *dst, CallSiteID csId) |
Add inter VF edge from actual to formal parameters. More... | |
VFGEdge * | addInterEdgeFromFRToAR (FormalRetVFGNode *src, ActualRetVFGNode *dst, CallSiteID csId) |
Add inter VF edge from callee return to callsite receive parameter. More... | |
VFGEdge * | addInterEdgeFromAPToFP (NodeID src, NodeID dst, CallSiteID csId) |
Add inter VF edge from actual to formal parameters. More... | |
VFGEdge * | addInterEdgeFromFRToAR (NodeID src, NodeID dst, CallSiteID csId) |
Add inter VF edge from callee return to callsite receive parameter. More... | |
virtual void | connectAParamAndFParam (const PAGNode *csArg, const PAGNode *funArg, const CallICFGNode *cbn, CallSiteID csId, VFGEdgeSetTy &edges) |
Connect VFG nodes between caller and callee for indirect call site. More... | |
virtual void | connectFRetAndARet (const PAGNode *funReturn, const PAGNode *csReturn, CallSiteID csId, VFGEdgeSetTy &edges) |
Connect formal-ret and actual ret. More... | |
void | setDef (const PAGNode *pagNode, const VFGNode *node) |
Given a PAGNode, set/get its def VFG node (definition of top level pointers) More... | |
NodeID | getDef (const PAGNode *pagNode) const |
bool | hasDef (const PAGNode *pagNode) const |
void | addVFGNodes () |
Create VFG nodes. More... | |
virtual SVFStmt::SVFStmtSetTy & | getPAGEdgeSet (SVFStmt::PEDGEK kind) |
Get PAGEdge set. More... | |
virtual bool | isInterestedPAGNode (const SVFVar *node) const |
void | connectDirectVFGEdges () |
Create edges between VFG nodes within a function. More... | |
void | addVFGInterEdges (const CallICFGNode *cs, const SVFFunction *callee) |
Create edges between VFG nodes across functions. More... | |
bool | isPhiCopyEdge (const PAGEdge *copy) const |
virtual void | addVFGNode (VFGNode *vfgNode, ICFGNode *icfgNode) |
Add a VFG node. More... | |
void | addStmtVFGNode (StmtVFGNode *node, const PAGEdge *pagEdge) |
Add a VFG node for program statement. More... | |
void | addNullPtrVFGNode (const PAGNode *pagNode) |
void | addAddrVFGNode (const AddrStmt *addr) |
Add an Address VFG node. More... | |
void | addCopyVFGNode (const CopyStmt *copy) |
Add a Copy VFG node. More... | |
void | addGepVFGNode (const GepStmt *gep) |
Add a Gep VFG node. More... | |
void | addLoadVFGNode (const LoadStmt *load) |
Add a Load VFG node. More... | |
void | addStoreVFGNode (const StoreStmt *store) |
void | addActualParmVFGNode (const PAGNode *aparm, const CallICFGNode *cs) |
void | addFormalParmVFGNode (const PAGNode *fparm, const SVFFunction *fun, CallPESet &callPEs) |
Add a formal parameter VFG node. More... | |
void | addFormalRetVFGNode (const PAGNode *uniqueFunRet, const SVFFunction *fun, RetPESet &retPEs) |
void | addActualRetVFGNode (const PAGNode *ret, const CallICFGNode *cs) |
Add a callsite Receive VFG node. More... | |
void | addIntraPHIVFGNode (const MultiOpndStmt *edge) |
Add an llvm PHI VFG node. More... | |
void | addCmpVFGNode (const CmpStmt *edge) |
Add a Compare VFG node. More... | |
void | addBinaryOPVFGNode (const BinaryOPStmt *edge) |
Add a BinaryOperator VFG node. More... | |
void | addUnaryOPVFGNode (const UnaryOPStmt *edge) |
Add a UnaryOperator VFG node. More... | |
void | addBranchVFGNode (const BranchStmt *edge) |
Add a BranchVFGNode. More... | |
Additional Inherited Members | |
Public Attributes inherited from SVF::GenericGraph< NodeTy, EdgeTy > | |
u32_t | edgeNum |
total num of node More... | |
u32_t | nodeNum |
total num of edge More... | |
typedef VFGNodeIDToNodeMapTy::const_iterator SVF::VFG::const_iterator |
typedef Map<const SVFFunction*, VFGNodeSet > SVF::VFG::FunToVFGNodesMapTy |
typedef Set<const VFGNode*> SVF::VFG::GlobalVFGNodeSet |
typedef VFGNodeIDToNodeMapTy::iterator SVF::VFG::iterator |
typedef Map<const PAGEdge*, StmtVFGNode*> SVF::VFG::PAGEdgeToStmtVFGNodeMapTy |
typedef Set<const PAGNode*> SVF::VFG::PAGNodeSet |
typedef Map<std::pair<NodeID,const CallICFGNode*>, ActualParmVFGNode *> SVF::VFG::PAGNodeToActualParmMapTy |
typedef Map<const PAGNode*, ActualRetVFGNode *> SVF::VFG::PAGNodeToActualRetMapTy |
typedef Map<const PAGNode*, BinaryOPVFGNode*> SVF::VFG::PAGNodeToBinaryOPVFGNodeMapTy |
typedef Map<const PAGNode*, BranchVFGNode*> SVF::VFG::PAGNodeToBranchVFGNodeMapTy |
typedef Map<const PAGNode*, CmpVFGNode*> SVF::VFG::PAGNodeToCmpVFGNodeMapTy |
typedef Map<const PAGNode*, NodeID> SVF::VFG::PAGNodeToDefMapTy |
typedef Map<const PAGNode*, FormalParmVFGNode *> SVF::VFG::PAGNodeToFormalParmMapTy |
typedef Map<const PAGNode*, FormalRetVFGNode *> SVF::VFG::PAGNodeToFormalRetMapTy |
typedef Map<const PAGNode*, IntraPHIVFGNode*> SVF::VFG::PAGNodeToPHIVFGNodeMapTy |
typedef Map<const PAGNode*, UnaryOPVFGNode*> SVF::VFG::PAGNodeToUnaryOPVFGNodeMapTy |
typedef OrderedMap<NodeID, VFGNode *> SVF::VFG::VFGNodeIDToNodeMapTy |
typedef VFGEdge::VFGEdgeSetTy::iterator SVF::VFG::VFGNodeIter |
typedef Set<VFGNode*> SVF::VFG::VFGNodeSet |
enum SVF::VFG::VFGK |
VFG::VFG | ( | PTACallGraph * | cg, |
VFGK | k = FULLSVFG |
||
) |
Constructor.
Constructor
Definition at line 441 of file VFG.cpp.
|
inlinevirtual |
Destructor.
|
inlineprotected |
Add an actual parameter VFG node To be noted that multiple actual parameters may have same value (PAGNode) So we need to make a pair <PAGNodeID,CallSiteID> to find the right VFGParmNode
do not set def here, this node is not a variable definition
|
inlineprotected |
Add a callsite Receive VFG node.
|
inlineprotected |
|
inlineprotected |
|
inlineprotected |
Add a BranchVFGNode.
Definition at line 630 of file VFG.h.
VFGEdge * VFG::addCallEdge | ( | NodeID | srcId, |
NodeID | dstId, | ||
CallSiteID | csId | ||
) |
Add interprocedural call edges for top level pointers
Definition at line 701 of file VFG.cpp.
|
inlineprotected |
|
inlineprotected |
|
inlineprotected |
Add a formal parameter VFG node.
Definition at line 538 of file VFG.h.
|
inlineprotected |
Add a callee Return VFG node To be noted that here we assume returns of a procedure have already been unified into one Otherwise, we need to handle formalRet using <PAGNodeID,CallSiteID> pair to find FormalRetVFG node same as handling actual parameters
if this uniqueFunRet is a phi node, which means it will receive values from multiple return instructions of fun we will set this phi node's def later Ideally, every function uniqueFunRet should be a PhiNode (SVFIRBuilder.cpp), unless it does not have ret instruction
Definition at line 552 of file VFG.h.
|
inlineprotected |
|
inlineprotected |
Add inter VF edge from actual to formal parameters.
Definition at line 362 of file VFG.h.
|
inlineprotected |
Add inter VF edge from actual to formal parameters.
|
inlineprotected |
Add inter VF edge from callee return to callsite receive parameter.
Definition at line 367 of file VFG.h.
|
inlineprotected |
Add inter VF edge from callee return to callsite receive parameter.
Add control-flow edges for top level pointers
Add def-use edges for top level pointers
Definition at line 675 of file VFG.cpp.
|
inlineprotected |
|
inlineprotected |
|
inlineprotected |
VFGEdge * VFG::addRetEdge | ( | NodeID | srcId, |
NodeID | dstId, | ||
CallSiteID | csId | ||
) |
Add interprocedural return edges for top level pointers
Definition at line 721 of file VFG.cpp.
|
inlineprotected |
Add a VFG node for program statement.
Definition at line 477 of file VFG.h.
|
inlineprotected |
|
inlineprotected |
|
inline |
|
protected |
Create edges between VFG nodes across functions.
Add a VFG node.
Definition at line 464 of file VFG.h.
|
protected |
Create VFG nodes.
Create VFG nodes for top level pointers
for external function we do not create acutalRet VFGNode they are in the formal of AddrVFGNode if the external function returns an allocated memory if fun has body, it may also exist in isExtCall, e.g., xmalloc() in bzip2, spec2000.
Definition at line 463 of file VFG.cpp.
|
inlineprotected |
sanitize Intra edges, verify that both nodes belong to the same function.
|
inlineprotectedvirtual |
Connect VFG nodes between caller and callee for indirect call site.
Connect actual-param and formal param
Reimplemented in SVF::SVFGOPT.
Definition at line 386 of file VFG.h.
|
virtual |
Connect VFG nodes between caller and callee for indirect call site.
Connect actual params/return to formal params/return for top-level variables. Also connect indirect actual in/out and formal in/out.
Reimplemented in SVF::SVFG.
Definition at line 973 of file VFG.cpp.
|
protected |
Create edges between VFG nodes within a function.
Connect def-use chains for direct value-flow, (value-flow of top level pointers)
do not handle AddrSVFG node, as it is already the source of a definition
for all other cases, like copy/gep/load/ret, connect the RHS pointer to its def
for store, connect the RHS/LHS pointer to its def
connect formal ret to its definition node
connect formal ret to actual ret
Do not process FormalRetVFGNode, as they are connected by copy within callee We assume one procedure only has unique return
connect direct value-flow edges (parameter passing) for thread fork/join
add fork edge
add join edge
Definition at line 742 of file VFG.cpp.
|
inlineprotectedvirtual |
Connect formal-ret and actual ret.
Reimplemented in SVF::SVFGOPT.
Definition at line 395 of file VFG.h.
|
protected |
Clean up memory.
Memory has been cleaned up at GenericGraph
void VFG::dump | ( | const std::string & | file, |
bool | simple = false |
||
) |
Dump graph into dot file.
Dump VFG
Definition at line 937 of file VFG.cpp.
|
inline |
Definition at line 235 of file VFG.h.
|
inline |
|
inline |
|
inline |
|
inline |
|
inline |
Definition at line 182 of file VFG.h.
|
inline |
Get callsite given a callsiteID.
Definition at line 178 of file VFG.h.
|
inline |
Given a pagNode, return its definition site.
|
inline |
|
inline |
|
inline |
|
inline |
VFGEdge * VFG::getIntraVFGEdge | ( | const VFGNode * | src, |
const VFGNode * | dst, | ||
VFGEdge::VFGEdgeK | kind | ||
) |
|
inline |
Given a VFG node, return its left hand side top level pointer
Definition at line 1024 of file VFG.cpp.
|
inline |
|
inlineprotectedvirtual |
Get PAGEdge set.
Definition at line 436 of file VFG.h.
|
inline |
|
inline |
|
inline |
|
inline |
|
inline |
Return all the VFGNodes of a function
|
inline |
|
inlineprotected |
VFGEdge * VFG::hasInterVFGEdge | ( | VFGNode * | src, |
VFGNode * | dst, | ||
VFGEdge::VFGEdgeK | kind, | ||
CallSiteID | csId | ||
) |
Whether we has an inter VFG edge
Definition at line 910 of file VFG.cpp.
VFGEdge * VFG::hasIntraVFGEdge | ( | VFGNode * | src, |
VFGNode * | dst, | ||
VFGEdge::VFGEdgeK | kind | ||
) |
VFGEdge * VFG::hasThreadVFGEdge | ( | VFGNode * | src, |
VFGNode * | dst, | ||
VFGEdge::VFGEdgeK | kind | ||
) |
|
inline |
|
inline |
const SVFFunction * VFG::isFunEntryVFGNode | ( | const VFGNode * | node | ) | const |
Whether a node is function entry VFGNode.
Whether this is an function entry VFGNode (formal parameter, formal In)
Definition at line 1061 of file VFG.cpp.
|
inlineprotectedvirtual |
|
inlineprotected |
|
inline |
Return true if this VFG only contains pointer related SVFGNodes for pointer analysis.
|
inline |
|
inline |
Remove a VFGNode.
Definition at line 326 of file VFG.h.
void VFG::updateCallGraph | ( | PointerAnalysis * | pta | ) |
Update VFG based on pointer analysis results.
Definition at line 951 of file VFG.cpp.
|
inline |
void VFG::view | ( | ) |
Dump graph into dot file.
View VFG from the debugger.
Definition at line 945 of file VFG.cpp.
|
protected |
|
protected |
|
protected |
|
protected |
map a PAGEdge to its StmtVFGNode
|
protected |
|
protected |
|
protected |
map a PAGNode to its BinaryOPVFGNode
|
protected |
map a PAGNode to its BranchVFGNode
|
protected |
map a PAGNode to its CmpVFGNode
|
protected |
|
protected |
|
protected |
|
protected |
map a PAGNode to its PHIVFGNode
|
protected |
map a PAGNode to its UnaryOPVFGNode