Static Value-Flow Analysis
|
#include <MHP.h>
Public Types | |
enum | ValDomain { Empty , TDAlive , TDDead } |
semilattice Empty==>TDDead==>TDAlive More... | |
typedef SVFLoopAndDomInfo::LoopBBs | LoopBBs |
typedef TCT::InstVec | InstVec |
typedef Map< CxtStmt, ValDomain > | CxtStmtToAliveFlagMap |
typedef Map< CxtStmt, NodeBS > | CxtStmtToTIDMap |
typedef Set< NodePair > | ThreadPairSet |
typedef Map< CxtStmt, LoopBBs > | CxtStmtToLoopMap |
typedef FIFOWorkList< CxtStmt > | CxtStmtWorkList |
Public Member Functions | |
ForkJoinAnalysis (TCT *t) | |
void | collectSCEVInfo () |
functions More... | |
void | analyzeForkJoinPair () |
NodeBS & | getDirectlyJoinedTid (const CxtStmt &cs) |
Get directly joined threadIDs based on a context-sensitive join site. More... | |
NodeBS | getDirAndIndJoinedTid (const CxtStmt &cs) |
Get directly and indirectly joined threadIDs based on a context-sensitive join site. More... | |
const LoopBBs & | getJoinInSymmetricLoop (const CxtStmt &cs) const |
Whether a context-sensitive join satisfies symmetric loop pattern. More... | |
bool | hasJoinInSymmetricLoop (const CxtStmt &cs) const |
bool | isHBPair (NodeID tid1, NodeID tid2) |
Whether thread t1 happens-before thread t2. More... | |
bool | isFullJoin (NodeID tid1, NodeID tid2) |
Whether t1 fully joins t2. More... | |
const ICFGNode * | getExitInstOfParentRoutineFun (NodeID tid) const |
Get exit instruction of the start routine function of tid's parent thread. More... | |
LoopBBs & | getJoinLoop (const CallICFGNode *inst) |
Get loop for join site. More... | |
bool | hasJoinLoop (const CallICFGNode *inst) |
Private Member Functions | |
void | handleFork (const CxtStmt &cts, NodeID rootTid) |
Handle fork. More... | |
void | handleJoin (const CxtStmt &cts, NodeID rootTid) |
Handle join. More... | |
void | handleCall (const CxtStmt &cts, NodeID rootTid) |
Handle call. More... | |
void | handleRet (const CxtStmt &cts) |
Handle return. More... | |
void | handleIntra (const CxtStmt &cts) |
Handle intra. More... | |
bool | isSameSCEV (const ICFGNode *forkSite, const ICFGNode *joinSite) |
Return true if the fork and join have the same SCEV. More... | |
bool | sameLoopTripCount (const ICFGNode *forkSite, const ICFGNode *joinSite) |
Same loop trip count. More... | |
bool | isAliasedForkJoin (const CallICFGNode *forkSite, const CallICFGNode *joinSite) |
Whether it is a matched fork join pair. More... | |
ValDomain | getMarkedFlag (const CxtStmt &cs) |
Mark thread flags for cxtStmt. More... | |
void | markCxtStmtFlag (const CxtStmt &tgr, ValDomain flag) |
Initialize TDAlive and TDDead flags. More... | |
void | markCxtStmtFlag (const CxtStmt &tgr, const CxtStmt &src) |
Transfer function for marking context-sensitive statement. More... | |
void | clearFlagMap () |
Clear flags. More... | |
bool | pushToCTSWorkList (const CxtStmt &cs) |
Worklist operations. More... | |
CxtStmt | popFromCTSWorkList () |
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 | isTDFork (const ICFGNode *call) |
Whether it is a fork site. More... | |
bool | isTDJoin (const ICFGNode *call) |
Whether it is a join site. More... | |
const SVFVar * | getForkedThread (const CallICFGNode *call) |
Get forked thread. More... | |
const SVFVar * | getJoinedThread (const CallICFGNode *call) |
Get joined thread. More... | |
const PTACallGraph::FunctionSet & | getCallee (const ICFGNode *inst, PTACallGraph::FunctionSet &callees) |
ThreadCallGraph * | getTCG () const |
ThreadCallGraph. More... | |
void | addDirectlyJoinTID (const CxtStmt &cs, NodeID tid) |
maps a context-sensitive join site to a thread id More... | |
void | addToHPPair (NodeID tid1, NodeID tid2) |
void | addToHBPair (NodeID tid1, NodeID tid2) |
void | addToFullJoin (NodeID tid1, NodeID tid2) |
full join and partial join More... | |
void | addToPartial (NodeID tid1, NodeID tid2) |
void | addSymmetricLoopJoin (const CxtStmt &cs, LoopBBs &lp) |
Add inloop join. More... | |
Private Attributes | |
TCT * | tct |
CxtStmtToAliveFlagMap | cxtStmtToAliveFlagMap |
flags for context-sensitive statements More... | |
CxtStmtWorkList | cxtStmtList |
context-sensitive statement worklist More... | |
CxtStmtToTIDMap | directJoinMap |
maps a context-sensitive join site to directly joined thread ids More... | |
CxtStmtToTIDMap | dirAndIndJoinMap |
maps a context-sensitive join site to directly and indirectly joined thread ids More... | |
CxtStmtToLoopMap | cxtJoinInLoop |
a set of context-sensitive join inside loop More... | |
ThreadPairSet | HBPair |
thread happens-before pair More... | |
ThreadPairSet | HPPair |
threads happen-in-parallel More... | |
ThreadPairSet | fullJoin |
t1 fully joins t2 along all program path More... | |
ThreadPairSet | partialJoin |
t1 partially joins t2 along some program path(s) More... | |
void ForkJoinAnalysis::analyzeForkJoinPair | ( | ) |
context-sensitive forward traversal from each fork site. Generate following results (1) fork join pair, maps a context-sensitive join site to its corresponding thread ids (2) never happen-in-parallel thread pairs
Context-sensitive forward traversal from each fork site
Definition at line 721 of file MHP.cpp.
|
inlineprivate |
void ForkJoinAnalysis::collectSCEVInfo | ( | ) |
functions
Collect SCEV pass information for pointers at fork/join sites Because ScalarEvolution is a function pass, previous knowledge of a function may be overwritten when analyzing a new function. We use a internal wrapper class PTASCEV to record all the necessary information for determining symmetric fork/join inside loops
Definition at line 667 of file MHP.cpp.
|
inlineprivate |
Definition at line 485 of file MHP.h.
Get directly and indirectly joined threadIDs based on a context-sensitive join site.
Return thread id(s) which are joined at this join site (1) thread t1 directly joins thread t2 (2) thread t1 indirectly joins thread t3 via directly joining t2 (t2 fully joins its child thread t3)
Definition at line 974 of file MHP.cpp.
Get directly joined threadIDs based on a context-sensitive join site.
|
inlineprivate |
Get forked thread.
Definition at line 476 of file MHP.h.
|
inlineprivate |
Get joined thread.
Definition at line 481 of file MHP.h.
|
inline |
|
inlineprivate |
Handle call.
Definition at line 877 of file MHP.cpp.
|
private |
Handle intra.
Definition at line 953 of file MHP.cpp.
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 812 of file MHP.cpp.
|
private |
Handle return.
Definition at line 902 of file MHP.cpp.
|
inline |
|
inline |
|
inlineprivate |
Whether it is a matched fork join pair.
Definition at line 382 of file MHP.h.
Return true if the fork and join have the same SCEV.
We assume a pair of fork and join sites are must-alias if they have same PTASCEV (1) SCEV not inside loop (2) SCEV inside two symmetric loops, then pointers of fork thread and join thread should have same scev start and step. and should have same loop trip count
Definition at line 1049 of file MHP.cpp.
|
inlineprivate |
Whether it is a fork site.
Definition at line 464 of file MHP.h.
|
inlineprivate |
Whether it is a join site.
Definition at line 470 of file MHP.h.
|
inlineprivate |
|
inlineprivate |
Match context.
Definition at line 458 of file MHP.h.
|
inlineprivate |
|
inlineprivate |
Push calling context.
Definition at line 453 of file MHP.h.
|
inlineprivate |
Worklist operations.
|
private |
|
private |
|
private |
|
private |
|
private |
|
private |
|
private |
|
private |
|
private |
|
private |