Static Value-Flow Analysis
|
#include <LockAnalysis.h>
Public Member Functions | |
LockAnalysis (TCT *t) | |
void | analyze () |
void | analyzeIntraProcedualLock () |
bool | intraForwardTraverse (const ICFGNode *lock, InstSet &unlockset, InstSet &forwardInsts) |
bool | intraBackwardTraverse (const InstSet &unlockset, InstSet &backwardInsts) |
void | collectCxtLock () |
void | analyzeLockSpanCxtStmt () |
void | collectLockUnlocksites () |
void | buildCandidateFuncSetforLock () |
bool | isIntraLock (const ICFGNode *lock) const |
Intraprocedural locks. More... | |
void | addIntraLock (const ICFGNode *lockSite, const InstSet &stmts) |
Add intra-procedural lock. More... | |
void | addCondIntraLock (const ICFGNode *lockSite, const InstSet &stmts) |
Add intra-procedural lock. More... | |
bool | isInsideIntraLock (const ICFGNode *stmt) const |
Return true if a statement is inside an intra-procedural lock. More... | |
bool | isInsideCondIntraLock (const ICFGNode *stmt) const |
Return true if a statement is inside a partial lock/unlock pair (conditional lock with unconditional unlock) More... | |
const InstSet & | getIntraLockSet (const ICFGNode *stmt) const |
void | addCxtLock (const CallStrCxt &cxt, const ICFGNode *inst) |
Context-sensitive locks. More... | |
bool | hasCxtLock (const CxtLock &cxtLock) const |
Get context-sensitive lock. More... | |
bool | intersects (const CxtLockSet &lockset1, const CxtLockSet &lockset2) const |
Return true if the intersection of two locksets is not empty. More... | |
bool | alias (const CxtLockSet &lockset1, const CxtLockSet &lockset2) |
Return true if two locksets has at least one alias lock. More... | |
bool | isLockCandidateFun (const SVFFunction *fun) const |
Return true if it is a candidate function. More... | |
bool | hasCxtStmtfromInst (const ICFGNode *inst) const |
Context-sensitive statement and lock spans. More... | |
const CxtStmtSet & | getCxtStmtfromInst (const ICFGNode *inst) const |
bool | hasCxtLockfromCxtStmt (const CxtStmt &cts) const |
const CxtLockSet & | getCxtLockfromCxtStmt (const CxtStmt &cts) const |
CxtLockSet & | getCxtLockfromCxtStmt (const CxtStmt &cts) |
bool | addCxtStmtToSpan (const CxtStmt &cts, const CxtLock &cl) |
Add context-sensitive statement. More... | |
bool | removeCxtStmtToSpan (CxtStmt &cts, const CxtLock &cl) |
Add context-sensitive statement. More... | |
CxtStmtToCxtLockSet | getCSTCLS () |
void | touchCxtStmt (CxtStmt &cts) |
Touch this context statement. More... | |
bool | hasSpanfromCxtLock (const CxtLock &cl) |
LockSpan & | getSpanfromCxtLock (const CxtLock &cl) |
bool | hasOneCxtInLockSpan (const ICFGNode *I, LockSpan lspan) const |
Check if one instruction's context stmt is in a lock span. More... | |
bool | hasAllCxtInLockSpan (const ICFGNode *I, LockSpan lspan) const |
bool | isProtectedByCommonLock (const ICFGNode *i1, const ICFGNode *i2) |
bool | isProtectedByCommonCxtLock (const ICFGNode *i1, const ICFGNode *i2) |
bool | isProtectedByCommonCxtLock (const CxtStmt &cxtStmt1, const CxtStmt &cxtStmt2) |
bool | isProtectedByCommonCILock (const ICFGNode *i1, const ICFGNode *i2) |
bool | isInSameSpan (const ICFGNode *I1, const ICFGNode *I2) |
bool | isInSameCSSpan (const ICFGNode *i1, const ICFGNode *i2) const |
bool | isInSameCSSpan (const CxtStmt &cxtStmt1, const CxtStmt &cxtStmt2) const |
bool | isInSameCISpan (const ICFGNode *i1, const ICFGNode *i2) const |
u32_t | getNumOfCxtLocks () |
void | printLocks (const CxtStmt &cts) |
Print locks and spans. More... | |
TCT * | getTCT () |
Get tct. More... | |
Public Attributes | |
double | lockTime |
u32_t | numOfTotalQueries |
u32_t | numOfLockedQueries |
double | lockQueriesTime |
Private Member Functions | |
void | handleFork (const CxtStmt &cts) |
Handle fork. More... | |
void | handleCall (const CxtStmt &cts) |
Handle call. More... | |
void | handleRet (const CxtStmt &cts) |
Handle return. More... | |
void | handleIntra (const CxtStmt &cts) |
Handle intra. More... | |
void | handleCallRelation (CxtLockProc &clp, const PTACallGraphEdge *cgEdge, const CallICFGNode *call) |
Handle call relations. More... | |
bool | isAliasedLocks (const CxtLock &cl1, const CxtLock &cl2) |
Return true it a lock matches an unlock. More... | |
bool | isAliasedLocks (const ICFGNode *i1, const ICFGNode *i2) |
void | markCxtStmtFlag (const CxtStmt &tgr, const CxtStmt &src) |
Mark thread flags for cxtStmt. More... | |
bool | intersect (CxtLockSet &tgrlockset, const CxtLockSet &srclockset) |
void | clearFlagMap () |
Clear flags. More... | |
bool | pushToCTPWorkList (const CxtLockProc &clp) |
WorkList helper functions. More... | |
CxtLockProc | popFromCTPWorkList () |
bool | isVisitedCTPs (const CxtLockProc &clp) const |
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 lock site. More... | |
bool | isTDAcquire (const ICFGNode *call) |
Whether it is a lock site. More... | |
bool | isTDRelease (const ICFGNode *call) |
Whether it is a unlock site. More... | |
bool | isCallSite (const ICFGNode *inst) |
Whether it is a callsite. More... | |
bool | isExtCall (const ICFGNode *inst) |
Whether it is calling an external function. More... | |
const SVFVar * | getLockVal (const ICFGNode *call) |
Get lock value. More... | |
ThreadCallGraph * | getTCG () const |
ThreadCallGraph. More... | |
Private Attributes | |
TCT * | tct |
TCT. More... | |
CxtStmtWorkList | cxtStmtList |
context-sensitive statement worklist More... | |
InstToCxtStmtSet | instToCxtStmtSet |
Map a statement to all its context-sensitive statements. More... | |
CxtLockSet | cxtLockset |
Context-sensitive locks. More... | |
CxtLockToSpan | cxtLocktoSpan |
CxtStmtToCxtLockSet | cxtStmtToCxtLockSet |
CxtLockProcVec | clpList |
Following data structures are used for collecting context-sensitive locks. More... | |
CxtLockProcSet | visitedCTPs |
CxtLockProc List. More... | |
InstSet | locksites |
Record all visited clps. More... | |
InstSet | unlocksites |
FunSet | lockcandidateFuncSet |
Candidate functions which relevant to locks/unlocks. More... | |
CILockToSpan | ciLocktoSpan |
Used for context-insensitive intra-procedural locks. More... | |
InstToInstSetMap | instCILocksMap |
InstToInstSetMap | instTocondCILocksMap |
Lock analysis
Definition at line 44 of file LockAnalysis.h.
typedef Map<const ICFGNode*, CISpan> SVF::LockAnalysis::CILockToSpan |
Definition at line 63 of file LockAnalysis.h.
typedef InstSet SVF::LockAnalysis::CISpan |
Definition at line 62 of file LockAnalysis.h.
typedef CxtStmt SVF::LockAnalysis::CxtLock |
Definition at line 56 of file LockAnalysis.h.
Definition at line 57 of file LockAnalysis.h.
Definition at line 78 of file LockAnalysis.h.
Definition at line 77 of file LockAnalysis.h.
typedef Set<CxtLock> SVF::LockAnalysis::CxtLockSet |
Definition at line 70 of file LockAnalysis.h.
typedef Map<CxtLock, NodeBS> SVF::LockAnalysis::CxtLockToLockSet |
Definition at line 73 of file LockAnalysis.h.
typedef Map<CxtLock, LockSpan> SVF::LockAnalysis::CxtLockToSpan |
Definition at line 72 of file LockAnalysis.h.
typedef Set<CxtStmt> SVF::LockAnalysis::CxtStmtSet |
Definition at line 69 of file LockAnalysis.h.
Definition at line 76 of file LockAnalysis.h.
Definition at line 66 of file LockAnalysis.h.
Definition at line 67 of file LockAnalysis.h.
typedef Set<const SVFFunction*> SVF::LockAnalysis::FunSet |
Definition at line 64 of file LockAnalysis.h.
typedef Set<const ICFGNode*> SVF::LockAnalysis::InstSet |
Definition at line 61 of file LockAnalysis.h.
typedef Map<const ICFGNode*, CxtStmtSet> SVF::LockAnalysis::InstToCxtStmt |
Definition at line 80 of file LockAnalysis.h.
typedef Map<const ICFGNode*, LockSpan> SVF::LockAnalysis::InstToCxtStmtSet |
Definition at line 75 of file LockAnalysis.h.
typedef Map<const ICFGNode*, InstSet> SVF::LockAnalysis::InstToInstSetMap |
Definition at line 65 of file LockAnalysis.h.
Definition at line 60 of file LockAnalysis.h.
typedef NodeBS SVF::LockAnalysis::LockSet |
Definition at line 59 of file LockAnalysis.h.
typedef Map<const ICFGNode*, NodeBS> SVF::LockAnalysis::LockSiteToLockSet |
Definition at line 74 of file LockAnalysis.h.
typedef Set<CxtStmt> SVF::LockAnalysis::LockSpan |
Definition at line 68 of file LockAnalysis.h.
semilattice Empty==>TDUnlocked==>TDLocked
Enumerator | |
---|---|
Empty | |
TDLocked | |
TDUnlocked |
Definition at line 49 of file LockAnalysis.h.
|
inline |
Definition at line 82 of file LockAnalysis.h.
|
inline |
Add intra-procedural lock.
Definition at line 120 of file LockAnalysis.h.
|
inline |
Context-sensitive locks.
Add inter-procedural context-sensitive lock
Definition at line 151 of file LockAnalysis.h.
Add context-sensitive statement.
Definition at line 232 of file LockAnalysis.h.
Add intra-procedural lock.
Definition at line 110 of file LockAnalysis.h.
|
inline |
Return true if two locksets has at least one alias lock.
Definition at line 179 of file LockAnalysis.h.
void LockAnalysis::analyze | ( | ) |
context-sensitive forward traversal from each lock site. Generate following results (1) context-sensitive lock site, (2) maps a context-sensitive lock site to its corresponding lock span.
Definition at line 41 of file LockAnalysis.cpp.
void LockAnalysis::analyzeIntraProcedualLock | ( | ) |
Analyze intraprocedural locks A lock is intraprocedural if its lock span is within a procedural
FIXME:Should we intersect forwardInsts and backwardInsts?
Definition at line 143 of file LockAnalysis.cpp.
void LockAnalysis::analyzeLockSpanCxtStmt | ( | ) |
Definition at line 330 of file LockAnalysis.cpp.
void LockAnalysis::buildCandidateFuncSetforLock | ( | ) |
Collect candidate functions for context-sensitive lock analysis
Definition at line 95 of file LockAnalysis.cpp.
|
inlineprivate |
Clear flags.
Definition at line 391 of file LockAnalysis.h.
void LockAnalysis::collectCxtLock | ( | ) |
Definition at line 259 of file LockAnalysis.cpp.
void LockAnalysis::collectLockUnlocksites | ( | ) |
Collect lock/unlock sites
Definition at line 69 of file LockAnalysis.cpp.
|
inline |
Definition at line 249 of file LockAnalysis.h.
|
inline |
Definition at line 225 of file LockAnalysis.h.
|
inline |
Definition at line 219 of file LockAnalysis.h.
|
inline |
Definition at line 208 of file LockAnalysis.h.
Definition at line 140 of file LockAnalysis.h.
Get lock value.
Definition at line 469 of file LockAnalysis.h.
|
inline |
Definition at line 316 of file LockAnalysis.h.
Definition at line 262 of file LockAnalysis.h.
|
inlineprivate |
Definition at line 474 of file LockAnalysis.h.
|
inline |
|
private |
Handle call.
Definition at line 428 of file LockAnalysis.cpp.
|
private |
Handle call relations.
Handling call relations when collecting context-sensitive locks
Definition at line 308 of file LockAnalysis.cpp.
|
private |
|
private |
Handle intra.
Definition at line 502 of file LockAnalysis.cpp.
|
private |
Handle return.
Definition at line 451 of file LockAnalysis.cpp.
Definition at line 287 of file LockAnalysis.h.
|
inline |
Get context-sensitive lock.
Definition at line 159 of file LockAnalysis.h.
|
inline |
Definition at line 214 of file LockAnalysis.h.
|
inline |
Context-sensitive statement and lock spans.
Get LockSet and LockSpan
Definition at line 203 of file LockAnalysis.h.
Check if one instruction's context stmt is in a lock span.
Definition at line 272 of file LockAnalysis.h.
|
inline |
Definition at line 258 of file LockAnalysis.h.
|
inlineprivate |
Definition at line 375 of file LockAnalysis.h.
|
inline |
Return true if the intersection of two locksets is not empty.
Definition at line 165 of file LockAnalysis.h.
Intra-procedural backward traversal
Definition at line 215 of file LockAnalysis.cpp.
bool LockAnalysis::intraForwardTraverse | ( | const ICFGNode * | lockSite, |
InstSet & | unlockSet, | ||
InstSet & | forwardInsts | ||
) |
Return true it a lock matches an unlock.
Definition at line 345 of file LockAnalysis.h.
todo: must alias
Definition at line 349 of file LockAnalysis.h.
|
inlineprivate |
Whether it is a callsite.
Definition at line 459 of file LockAnalysis.h.
|
inlineprivate |
Whether it is calling an external function.
Definition at line 464 of file LockAnalysis.h.
Return true if two instructions are inside same context-insensitive lock span
Definition at line 656 of file LockAnalysis.cpp.
Return true if two context-sensitive instructions are inside same context-insensitive lock spa
Definition at line 677 of file LockAnalysis.cpp.
Return true if two instructions are inside at least one common context-sensitive lock span
Definition at line 688 of file LockAnalysis.cpp.
Return true if two instructions are inside at least one common lock span
Definition at line 638 of file LockAnalysis.cpp.
|
inline |
Return true if a statement is inside a partial lock/unlock pair (conditional lock with unconditional unlock)
Definition at line 135 of file LockAnalysis.h.
|
inline |
Return true if a statement is inside an intra-procedural lock.
Definition at line 129 of file LockAnalysis.h.
|
inline |
Intraprocedural locks.
Return true if the lock is an intra-procedural lock
Definition at line 103 of file LockAnalysis.h.
|
inline |
Return true if it is a candidate function.
Definition at line 195 of file LockAnalysis.h.
Protected by at least one common context-insensitive lock
Definition at line 580 of file LockAnalysis.cpp.
bool LockAnalysis::isProtectedByCommonCxtLock | ( | const CxtStmt & | cxtStmt1, |
const CxtStmt & | cxtStmt2 | ||
) |
Protected by at least one common context-sensitive lock
Definition at line 602 of file LockAnalysis.cpp.
Protected by at least one common context-sensitive lock under each context
Definition at line 614 of file LockAnalysis.cpp.
Check if two Instructions are protected by common locks echo inst may have multiple cxt stmt we check whether every cxt stmt of instructions is protected by a common lock.
Protected by at least one common lock under every context
Definition at line 563 of file LockAnalysis.cpp.
|
inlineprivate |
|
inlineprivate |
Whether it is a lock site.
Definition at line 438 of file LockAnalysis.h.
|
inlineprivate |
|
inlineprivate |
Definition at line 413 of file LockAnalysis.h.
Mark thread flags for cxtStmt.
Transfer function for marking context-sensitive statement
Definition at line 358 of file LockAnalysis.h.
|
private |
Match context.
partial match
Definition at line 535 of file LockAnalysis.cpp.
|
inlineprivate |
Definition at line 408 of file LockAnalysis.h.
|
inlineprivate |
Definition at line 425 of file LockAnalysis.h.
void LockAnalysis::printLocks | ( | const CxtStmt & | cts | ) |
Print locks and spans.
Print context-insensitive and context-sensitive locks
Definition at line 394 of file LockAnalysis.cpp.
|
private |
Push calling context.
Definition at line 519 of file LockAnalysis.cpp.
|
inlineprivate |
WorkList helper functions.
Definition at line 399 of file LockAnalysis.h.
|
inlineprivate |
Worklist operations.
Definition at line 421 of file LockAnalysis.h.
|
inline |
Touch this context statement.
Definition at line 254 of file LockAnalysis.h.
|
private |
Used for context-insensitive intra-procedural locks.
Definition at line 518 of file LockAnalysis.h.
|
private |
Following data structures are used for collecting context-sensitive locks.
Definition at line 501 of file LockAnalysis.h.
|
private |
Context-sensitive locks.
Definition at line 490 of file LockAnalysis.h.
|
private |
Map a context-sensitive lock to its lock span statements Map a context-sensitive statement to its context-sensitive lock
Definition at line 495 of file LockAnalysis.h.
|
private |
context-sensitive statement worklist
Definition at line 483 of file LockAnalysis.h.
|
private |
Definition at line 496 of file LockAnalysis.h.
|
private |
Definition at line 519 of file LockAnalysis.h.
|
private |
Definition at line 520 of file LockAnalysis.h.
|
private |
Map a statement to all its context-sensitive statements.
Definition at line 486 of file LockAnalysis.h.
|
private |
Candidate functions which relevant to locks/unlocks.
Definition at line 513 of file LockAnalysis.h.
double SVF::LockAnalysis::lockQueriesTime |
Definition at line 528 of file LockAnalysis.h.
|
private |
Record all visited clps.
Collecting lock/unlock sites
Definition at line 507 of file LockAnalysis.h.
double SVF::LockAnalysis::lockTime |
Definition at line 525 of file LockAnalysis.h.
u32_t SVF::LockAnalysis::numOfLockedQueries |
Definition at line 527 of file LockAnalysis.h.
u32_t SVF::LockAnalysis::numOfTotalQueries |
Definition at line 526 of file LockAnalysis.h.
|
private |
TCT.
Definition at line 480 of file LockAnalysis.h.
|
private |
Definition at line 508 of file LockAnalysis.h.
|
private |
CxtLockProc List.
Definition at line 502 of file LockAnalysis.h.