Static Value-Flow Analysis
|
#include <MHP.h>
Public Types | |
typedef Set< const SVFFunction * > | FunSet |
typedef FIFOWorkList< CxtThreadStmt > | CxtThreadStmtWorkList |
typedef Set< CxtThreadStmt > | CxtThreadStmtSet |
typedef Map< CxtThreadStmt, NodeBS > | ThreadStmtToThreadInterleav |
typedef Map< const ICFGNode *, CxtThreadStmtSet > | InstToThreadStmtSetMap |
typedef SVFLoopAndDomInfo::LoopBBs | LoopBBs |
typedef Set< CxtStmt > | LockSpan |
typedef std::pair< const SVFFunction *, const SVFFunction * > | FuncPair |
typedef Map< FuncPair, bool > | FuncPairToBool |
Public Member Functions | |
MHP (TCT *t) | |
Constructor. More... | |
virtual | ~MHP () |
Destructor. More... | |
void | analyze () |
Start analysis here. More... | |
void | analyzeInterleaving () |
Analyze thread interleaving. More... | |
ThreadCallGraph * | getThreadCallGraph () const |
Get ThreadCallGraph. More... | |
TCT * | getTCT () const |
Get Thread Creation Tree. More... | |
bool | isConnectedfromMain (const SVFFunction *fun) |
Whether the function is connected from main function in thread call graph. More... | |
virtual bool | mayHappenInParallel (const ICFGNode *i1, const ICFGNode *i2) |
Interface to query whether two instructions may happen-in-parallel. More... | |
virtual bool | mayHappenInParallelCache (const ICFGNode *i1, const ICFGNode *i2) |
virtual bool | mayHappenInParallelInst (const ICFGNode *i1, const ICFGNode *i2) |
virtual bool | executedByTheSameThread (const ICFGNode *i1, const ICFGNode *i2) |
const NodeBS & | getInterleavingThreads (const CxtThreadStmt &cts) |
Get interleaving thread for statement inst. More... | |
bool | hasInterleavingThreads (const CxtThreadStmt &cts) const |
const CxtThreadStmtSet & | getThreadStmtSet (const ICFGNode *inst) const |
Get/has ThreadStmt. More... | |
bool | hasThreadStmtSet (const ICFGNode *inst) const |
void | printInterleaving () |
Print interleaving results. More... | |
Public Attributes | |
u32_t | numOfTotalQueries |
Total number of queries. More... | |
u32_t | numOfMHPQueries |
Number of queries are answered as may-happen-in-parallel. More... | |
double | interleavingTime |
double | interleavingQueriesTime |
Private Member Functions | |
const PTACallGraph::FunctionSet & | getCallee (const CallICFGNode *inst, PTACallGraph::FunctionSet &callees) |
void | updateNonCandidateFunInterleaving () |
void | handleNonCandidateFun (const CxtThreadStmt &cts) |
Handle non-candidate function. More... | |
void | handleFork (const CxtThreadStmt &cts, NodeID rootTid) |
Handle fork. More... | |
void | handleJoin (const CxtThreadStmt &cts, NodeID rootTid) |
Handle join. More... | |
void | handleCall (const CxtThreadStmt &cts, NodeID rootTid) |
Handle call. More... | |
void | handleRet (const CxtThreadStmt &cts) |
Handle return. More... | |
void | handleIntra (const CxtThreadStmt &cts) |
Handle intra. More... | |
void | addInterleavingThread (const CxtThreadStmt &tgr, NodeID tid) |
Add/Remove interleaving thread for statement inst. More... | |
void | addInterleavingThread (const CxtThreadStmt &tgr, const CxtThreadStmt &src) |
void | rmInterleavingThread (const CxtThreadStmt &tgr, const NodeBS &tids, const ICFGNode *joinsite) |
void | updateAncestorThreads (NodeID tid) |
Update Ancestor and sibling threads. More... | |
void | updateSiblingThreads (NodeID tid) |
bool | isRecurFullJoin (NodeID parentTid, NodeID curTid) |
Thread curTid can be fully joined by parentTid recursively. More... | |
bool | isMustJoin (const NodeID curTid, const ICFGNode *joinsite) |
Whether a join site must join a thread t. More... | |
bool | isMultiForkedThread (NodeID curTid) |
A thread is a multiForked thread if it is in a loop or recursion. 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... | |
bool | pushToCTSWorkList (const CxtThreadStmt &cs) |
WorkList helper functions. More... | |
CxtThreadStmt | popFromCTSWorkList () |
bool | isTDFork (const ICFGNode *call) |
Whether it is a fork site. More... | |
bool | isTDJoin (const ICFGNode *call) |
Whether it is a join site. More... | |
NodeBS | getDirAndIndJoinedTid (const CallStrCxt &cxt, const ICFGNode *call) |
Return thread id(s) which are directly or indirectly joined at this join site. More... | |
bool | hasJoinInSymmetricLoop (const CallStrCxt &cxt, const ICFGNode *call) const |
Whether a context-sensitive join satisfies symmetric loop pattern. More... | |
const LoopBBs & | getJoinInSymmetricLoop (const CallStrCxt &cxt, const ICFGNode *call) const |
Whether a context-sensitive join satisfies symmetric loop pattern. More... | |
bool | isHBPair (NodeID tid1, NodeID tid2) |
Whether thread t1 happens before t2 based on ForkJoin Analysis. More... | |
Private Attributes | |
ThreadCallGraph * | tcg |
TCG. More... | |
TCT * | tct |
TCT. More... | |
ForkJoinAnalysis * | fja |
ForJoin Analysis. More... | |
CxtThreadStmtWorkList | cxtStmtList |
CxtThreadStmt worklist. More... | |
ThreadStmtToThreadInterleav | threadStmtToTheadInterLeav |
InstToThreadStmtSetMap | instToTSMap |
Map a statement to its thread interleavings. More... | |
FuncPairToBool | nonCandidateFuncMHPRelMap |
This class serves as a base may-happen in parallel analysis for multithreaded program Given a statement under an abstract thread, it tells which abstract threads may be alive at the same time (May-happen-in-parallel).
typedef Set<CxtThreadStmt> SVF::MHP::CxtThreadStmtSet |
typedef std::pair<const SVFFunction*,const SVFFunction*> SVF::MHP::FuncPair |
typedef Map<FuncPair, bool> SVF::MHP::FuncPairToBool |
typedef Set<const SVFFunction*> SVF::MHP::FunSet |
typedef Map<const ICFGNode*,CxtThreadStmtSet> SVF::MHP::InstToThreadStmtSetMap |
typedef Set<CxtStmt> SVF::MHP::LockSpan |
MHP::MHP | ( | TCT * | t | ) |
|
virtual |
|
inlineprivate |
|
inlineprivate |
void MHP::analyze | ( | ) |
Start analysis here.
Start analysis here
Definition at line 62 of file MHP.cpp.
void MHP::analyzeInterleaving | ( | ) |
Analyze thread interleaving.
Analyze thread interleaving
handle non-candidate function
handle candidate function
update non-candidate functions' interleaving
Definition at line 75 of file MHP.cpp.
|
inlineprivate |
Definition at line 126 of file MHP.h.
|
private |
Return thread id(s) which are directly or indirectly joined at this join site.
Return thread id(s) which are directly or indirectly joined at this join site
Definition at line 491 of file MHP.cpp.
|
inline |
Get interleaving thread for statement inst.
|
private |
|
inline |
|
inline |
|
inline |
|
private |
Handle call.
Handle call instruction in the current thread scope (excluding any fork site)
Definition at line 290 of file MHP.cpp.
|
private |
Handle fork.
Handle fork
Definition at line 203 of file MHP.cpp.
|
private |
Handle intra.
Handling intraprocedural statements (successive statements on the CFG )
Definition at line 366 of file MHP.cpp.
|
private |
Handle join.
Handle join
for the join site in a loop loop which does not join the current thread we process the loop exit
Definition at line 233 of file MHP.cpp.
|
private |
Handle non-candidate function.
Handle call instruction in the current thread scope (excluding any fork site)
Definition at line 181 of file MHP.cpp.
|
private |
Handle return.
Handle return instruction in the current thread scope (excluding any join site)
Definition at line 319 of file MHP.cpp.
|
inline |
|
private |
|
inline |
bool MHP::isConnectedfromMain | ( | const SVFFunction * | fun | ) |
Whether the function is connected from main function in thread call graph.
Definition at line 521 of file MHP.cpp.
|
inlineprivate |
Whether a join site must join a thread t.
A join site must join t if (1) t is not a multiforked thread (2) the join site of t is not in recursion
Definition at line 481 of file MHP.cpp.
|
inlineprivate |
Whether it is a fork site.
Definition at line 228 of file MHP.h.
|
inlineprivate |
Whether it is a join site.
Definition at line 234 of file MHP.h.
|
inlineprivate |
Match context.
Definition at line 210 of file MHP.h.
Interface to query whether two instructions may happen-in-parallel.
Definition at line 614 of file MHP.cpp.
Definition at line 592 of file MHP.cpp.
|
inlineprivate |
void MHP::printInterleaving | ( | ) |
|
inlineprivate |
Push calling context.
Definition at line 205 of file MHP.h.
|
inlineprivate |
WorkList helper functions.
|
inlineprivate |
Definition at line 172 of file MHP.h.
|
private |
Update Ancestor and sibling threads.
Update interleavings of ancestor threads according to TCT
Definition at line 382 of file MHP.cpp.
|
private |
Update non-candidate functions' interleaving. Copy interleaving threads of the entry inst to other insts.
Update non-candidate functions' interleaving
Definition at line 144 of file MHP.cpp.
|
private |
Update interleavings of sibling threads according to TCT
Exclude sibling thread that never happen in parallel based on ForkJoinAnalysis
The interleaving of a thread t is not unnecessary to be updated if (1) t HB Sibling and t fully joins curTid recursively or (2) Sibling HB t
Definition at line 418 of file MHP.cpp.
|
private |
CxtThreadStmt worklist.
|
private |
|
private |
|
private |
u32_t SVF::MHP::numOfMHPQueries |
|
private |
|
private |