Static Value-Flow Analysis
|
#include <TCT.h>
Public Member Functions | |
TCT (PointerAnalysis *p) | |
Constructor. More... | |
virtual | ~TCT () |
Destructor. More... | |
SVFModule * | getSVFModule () const |
Get SVFFModule. More... | |
ThreadCallGraph * | getThreadCallGraph () const |
Get TCG. More... | |
PointerAnalysis * | getPTA () const |
Get PTA. More... | |
TCTNode * | getTCTNode (NodeID id) const |
Get TCT node. More... | |
TCTEdge * | hasGraphEdge (TCTNode *src, TCTNode *dst, TCTEdge::CEDGEK kind) const |
Whether we have already created this call graph edge. More... | |
TCTEdge * | getGraphEdge (TCTNode *src, TCTNode *dst, TCTEdge::CEDGEK kind) |
Get call graph edge via nodes. More... | |
ThreadCreateEdgeSet::const_iterator | getChildrenBegin (const TCTNode *node) const |
Get children and parent nodes. More... | |
ThreadCreateEdgeSet::const_iterator | getChildrenEnd (const TCTNode *node) const |
ThreadCreateEdgeSet::const_iterator | getParentsBegin (const TCTNode *node) const |
ThreadCreateEdgeSet::const_iterator | getParentsEnd (const TCTNode *node) const |
const FunSet & | getMakredProcs () const |
Get marked candidate functions. More... | |
const FunSet & | getEntryProcs () const |
Get marked candidate functions. More... | |
u32_t | getTCTNodeNum () const |
Get Statistics. More... | |
u32_t | getTCTEdgeNum () const |
u32_t | getMaxCxtSize () const |
bool | isExtCall (const ICFGNode *inst) |
Whether it is calling an external function. More... | |
bool | isCallSite (const ICFGNode *inst) |
Whether it is a callsite. More... | |
bool | hasTCTNode (const CxtThread &ct) const |
Find/Get TCT node. More... | |
TCTNode * | getTCTNode (const CxtThread &ct) const |
bool | isCandidateFun (const PTACallGraph::FunctionSet &callees) const |
Whether it is a candidate function for indirect call. More... | |
bool | isCandidateFun (const SVFFunction *fun) const |
bool | inSameCallGraphSCC (const PTACallGraphNode *src, const PTACallGraphNode *dst) |
Whether two functions in the same callgraph scc. More... | |
bool | hasParentThread (NodeID tid) const |
Get parent and sibling threads. More... | |
NodeID | getParentThread (NodeID tid) const |
Get parent thread. More... | |
const NodeBS | getAncestorThread (NodeID tid) const |
Get all ancestor threads. More... | |
const NodeBS | getSiblingThread (NodeID tid) const |
Get sibling threads. More... | |
const CallStrCxt & | getCxtOfCxtThread (const CxtThread &ct) const |
get the context of a thread at its spawning site (fork site) More... | |
const SVFFunction * | getStartRoutineOfCxtThread (const CxtThread &ct) const |
get the start routine function of a thread More... | |
LoopBBs & | getJoinLoop (const CallICFGNode *join) |
Get loop for join site. More... | |
bool | hasJoinLoop (const CallICFGNode *join) const |
bool | hasLoop (const SVFBasicBlock *bb) const |
bool | hasLoop (const ICFGNode *inst) const |
bool | isJoinMustExecutedInLoop (const LoopBBs &lp, const ICFGNode *join) |
Return true if a join instruction must be executed inside a loop. More... | |
const LoopBBs & | getLoop (const ICFGNode *inst) |
Get loop for an instruction. More... | |
const LoopBBs & | getLoop (const SVFBasicBlock *bb) |
Get loop for fork/join site. More... | |
void | pushCxt (CallStrCxt &cxt, const CallICFGNode *call, const SVFFunction *callee) |
Push calling context. More... | |
bool | matchCxt (CallStrCxt &cxt, const CallICFGNode *call, const SVFFunction *callee) |
Match context. More... | |
void | pushCxt (CallStrCxt &cxt, CallSiteID csId) |
bool | isJoinSiteInRecursion (const CallICFGNode *join) const |
Whether a join site is in recursion. More... | |
void | dumpCxt (CallStrCxt &cxt) |
Dump calling context. More... | |
void | dump (const std::string &filename) |
Dump the graph. More... | |
void | print () const |
Print TCT information. More... | |
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 () |
Private Member Functions | |
TCTNode * | addTCTNode (const CxtThread &ct) |
Add TCT node. More... | |
bool | addTCTEdge (TCTNode *src, TCTNode *dst) |
Add TCT edge. More... | |
void | build () |
Build TCT. More... | |
void | markRelProcs () |
Mark relevant procedures that are backward reachable from any fork/join site. More... | |
void | markRelProcs (const SVFFunction *fun) |
void | collectEntryFunInCallGraph () |
Get entry functions that are neither called by other functions nor extern functions. More... | |
void | collectMultiForkedThreads () |
void | collectLoopInfoForJoin () |
Handle join site in loop. More... | |
bool | isLoopHeaderOfJoinLoop (const SVFBasicBlock *bb) |
Whether a given bb is a loop head of a inloop join site. More... | |
bool | isLoopExitOfJoinLoop (const SVFBasicBlock *bb) |
Whether a given bb is an exit of a inloop join site. More... | |
bool | isInLoopInstruction (const ICFGNode *inst) |
Multi-forked threads. More... | |
bool | isInRecursion (const ICFGNode *inst) const |
Whether an instruction is in a recursion. More... | |
void | handleCallRelation (CxtThreadProc &ctp, const PTACallGraphEdge *cgEdge, const CallICFGNode *call) |
Handle call relations. More... | |
TCTNode * | getOrCreateTCTNode (const CallStrCxt &cxt, const ICFGNode *fork, const CallStrCxt &oldCxt, const SVFFunction *routine) |
Get or create a tct node based on CxtThread. More... | |
void | setMultiForkedAttrs (CxtThread &ct) |
Set multi-forked thread attributes. More... | |
void | addCxtOfCxtThread (const CallStrCxt &cxt, const CxtThread &ct) |
Add context for a thread at its spawning site (fork site) More... | |
void | addStartRoutineOfCxtThread (const SVFFunction *fun, const CxtThread &ct) |
Add start routine function of a cxt thread. More... | |
bool | pushToCTPWorkList (const CxtThreadProc &ctp) |
WorkList helper functions. More... | |
CxtThreadProc | popFromCTPWorkList () |
bool | isVisitedCTPs (const CxtThreadProc &ctp) const |
void | destroy () |
Clean up memory. More... | |
Private Attributes | |
ThreadCallGraph * | tcg |
PointerAnalysis * | pta |
u32_t | TCTNodeNum |
u32_t | TCTEdgeNum |
u32_t | MaxCxtSize |
FunSet | entryFuncSet |
FunSet | candidateFuncSet |
Procedures that are neither called by other functions nor extern functions. More... | |
ThreadCallGraphSCC * | tcgSCC |
Procedures we care about during call graph traversing when creating TCT. More... | |
CxtThreadProcVec | ctpList |
Thread call graph SCC. More... | |
CxtThreadProcSet | visitedCTPs |
CxtThreadProc List. More... | |
CxtThreadToNodeMap | ctpToNodeMap |
Record all visited ctps. More... | |
CxtThreadToForkCxt | ctToForkCxtMap |
Map a ctp to its graph node. More... | |
CxtThreadToFun | ctToRoutineFunMap |
Map a CxtThread to the context at its spawning site (fork site). More... | |
InstToLoopMap | joinSiteToLoopMap |
Map a CxtThread to its start routine function. More... | |
Set< const ICFGNode * > | inRecurJoinSites |
Fork or Join sites in recursions. 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... | |
Protected Attributes inherited from SVF::GenericGraph< NodeTy, EdgeTy > | |
IDToNodeMapTy | IDToNodeMap |
node map More... | |
typedef Set<CxtThreadProc> SVF::TCT::CxtThreadProcSet |
typedef Map<CxtThread,const SVFFunction*> SVF::TCT::CxtThreadToFun |
typedef Set<const SVFFunction*> SVF::TCT::FunSet |
typedef Set<const ICFGNode*> SVF::TCT::InstSet |
typedef std::vector<const ICFGNode*> SVF::TCT::InstVec |
typedef Set<const PTACallGraphNode*> SVF::TCT::PTACGNodeSet |
typedef ThreadCreateEdgeSet::iterator SVF::TCT::TCTNodeIter |
|
inline |
Constructor.
Definition at line 173 of file TCT.h.
|
inlinevirtual |
Destructor.
|
inlineprivate |
|
inlineprivate |
Add TCT edge.
Definition at line 461 of file TCT.h.
Add TCT node.
Definition at line 450 of file TCT.h.
|
private |
Build TCT.
Start building TCT
Definition at line 383 of file TCT.cpp.
|
private |
Get entry functions that are neither called by other functions nor extern functions.
Get Main function
Definition at line 186 of file TCT.cpp.
|
private |
Handle join site in loop.
collect loop info for join sites
Collect loop info for join sites the in-loop join site must be joined if the loop is executed
Definition at line 314 of file TCT.cpp.
|
private |
Collect multi-forked threads whose 1, cxt is in loop or recursion; 2, parent thread is a multi-forked thread.
Collect all multi-forked threads
Definition at line 206 of file TCT.cpp.
|
inlineprivate |
void TCT::dump | ( | const std::string & | filename | ) |
Dump the graph.
Dump call graph into dot file
Definition at line 513 of file TCT.cpp.
void TCT::dumpCxt | ( | CallStrCxt & | cxt | ) |
Dump calling context.
Dump calling context information
Definition at line 495 of file TCT.cpp.
|
inline |
|
inline |
|
inline |
|
inline |
Get marked candidate functions.
TCTEdge * TCT::getGraphEdge | ( | TCTNode * | src, |
TCTNode * | dst, | ||
TCTEdge::CEDGEK | kind | ||
) |
Get call graph edge via nodes.
get PTACallGraph edge via nodes
Definition at line 551 of file TCT.cpp.
|
inline |
Get loop for join site.
Definition at line 385 of file TCT.h.
const TCT::LoopBBs & TCT::getLoop | ( | const SVFBasicBlock * | bb | ) |
|
inline |
|
inline |
|
inlineprivate |
Get or create a tct node based on CxtThread.
Definition at line 513 of file TCT.h.
|
inline |
|
inline |
|
inline |
Get sibling threads.
Definition at line 350 of file TCT.h.
|
inline |
|
inline |
Get SVFFModule.
Definition at line 190 of file TCT.h.
|
inline |
Get TCT node.
Definition at line 206 of file TCT.h.
|
inline |
|
inline |
|
private |
Handle call relations.
Handle call relations
Create spawnee TCT node
Add TCT nodes and edge
Definition at line 244 of file TCT.cpp.
TCTEdge * TCT::hasGraphEdge | ( | TCTNode * | src, |
TCTNode * | dst, | ||
TCTEdge::CEDGEK | kind | ||
) | const |
|
inline |
|
inline |
|
inline |
Get parent and sibling threads.
Has parent thread
|
inline |
|
inline |
|
inline |
|
inline |
|
inline |
|
private |
Multi-forked threads.
Whether an instruction is in a loop
An instruction i is in loop (1) the instruction i itself (2) all the callsites invoke the function where i resides in
Definition at line 45 of file TCT.cpp.
|
private |
Whether an instruction is in a recursion.
An instruction i is in a recursion (1) the function f where i resides in is in a recursion (2) any caller function starting from the function f in is in a recursion
Definition at line 90 of file TCT.cpp.
Return true if a join instruction must be executed inside a loop.
Return true if a join instruction must be executed inside a loop joinbb should post dominate the successive basic block of a loop header
Definition at line 290 of file TCT.cpp.
|
inline |
|
private |
Whether a given bb is an exit of a inloop join site.
Whether a given bb is an exit of a inloop join site
Definition at line 353 of file TCT.cpp.
|
private |
Whether a given bb is a loop head of a inloop join site.
Return true if a given bb is a loop head of a inloop join site
Definition at line 339 of file TCT.cpp.
|
inlineprivate |
|
private |
Mark relevant procedures that are backward reachable from any fork/join site.
Mark relevant procedures that are backward reachable from any fork/join site
Definition at line 132 of file TCT.cpp.
|
private |
Definition at line 160 of file TCT.cpp.
bool TCT::matchCxt | ( | CallStrCxt & | cxt, |
const CallICFGNode * | call, | ||
const SVFFunction * | callee | ||
) |
Match context.
Match calling context
handle calling context for candidate functions only
partial match
Definition at line 465 of file TCT.cpp.
|
inlineprivate |
void TCT::print | ( | void | ) | const |
Print TCT information.
Print TCT information
Definition at line 522 of file TCT.cpp.
|
inline |
void TCT::pushCxt | ( | CallStrCxt & | cxt, |
const CallICFGNode * | call, | ||
const SVFFunction * | callee | ||
) |
|
inlineprivate |
|
inlineprivate |
Set multi-forked thread attributes.
non-main thread
main thread
Definition at line 531 of file TCT.h.
|
private |
|
private |
|
private |
|
private |
|
private |
|
private |
|
private |
|
private |
|
private |
|
private |