#include <LockAnalysis.h>

Public Types
enum	ValDomain { Empty , TDLocked , TDUnlocked }
	semilattice Empty==>TDUnlocked==>TDLocked More...

typedef CxtStmt	CxtLock

typedef CxtProc	CxtLockProc

typedef NodeBS	LockSet

typedef TCT::InstVec	InstVec

typedef Set< const ICFGNode * >	InstSet

typedef InstSet	CISpan

typedef Map< const ICFGNode *, CISpan >	CILockToSpan

typedef Set< const SVFFunction * >	FunSet

typedef Map< const ICFGNode *, InstSet >	InstToInstSetMap

typedef Map< CxtStmt, ValDomain >	CxtStmtToLockFlagMap

typedef FIFOWorkList< CxtStmt >	CxtStmtWorkList

typedef Set< CxtStmt >	LockSpan

typedef Set< CxtStmt >	CxtStmtSet

typedef Set< CxtLock >	CxtLockSet

typedef Map< CxtLock, LockSpan >	CxtLockToSpan

typedef Map< CxtLock, NodeBS >	CxtLockToLockSet

typedef Map< const ICFGNode *, NodeBS >	LockSiteToLockSet

typedef Map< const ICFGNode *, LockSpan >	InstToCxtStmtSet

typedef Map< CxtStmt, CxtLockSet >	CxtStmtToCxtLockSet

typedef FIFOWorkList< CxtLockProc >	CxtLockProcVec

typedef Set< CxtLockProc >	CxtLockProcSet

typedef Map< const ICFGNode *, CxtStmtSet >	InstToCxtStmt

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

Detailed Description

Lock analysis

Definition at line 44 of file LockAnalysis.h.

Member Typedef Documentation

◆ CILockToSpan

typedef Map<const ICFGNode*, CISpan> SVF::LockAnalysis::CILockToSpan

Definition at line 63 of file LockAnalysis.h.

◆ CISpan

typedef InstSet SVF::LockAnalysis::CISpan

Definition at line 62 of file LockAnalysis.h.

◆ CxtLock

typedef CxtStmt SVF::LockAnalysis::CxtLock

Definition at line 56 of file LockAnalysis.h.

◆ CxtLockProc

typedef CxtProc SVF::LockAnalysis::CxtLockProc

Definition at line 57 of file LockAnalysis.h.

◆ CxtLockProcSet

typedef Set<CxtLockProc> SVF::LockAnalysis::CxtLockProcSet

Definition at line 78 of file LockAnalysis.h.

◆ CxtLockProcVec

typedef FIFOWorkList<CxtLockProc> SVF::LockAnalysis::CxtLockProcVec

Definition at line 77 of file LockAnalysis.h.

◆ CxtLockSet

typedef Set<CxtLock> SVF::LockAnalysis::CxtLockSet

Definition at line 70 of file LockAnalysis.h.

◆ CxtLockToLockSet

typedef Map<CxtLock, NodeBS> SVF::LockAnalysis::CxtLockToLockSet

Definition at line 73 of file LockAnalysis.h.

◆ CxtLockToSpan

typedef Map<CxtLock, LockSpan> SVF::LockAnalysis::CxtLockToSpan

Definition at line 72 of file LockAnalysis.h.

◆ CxtStmtSet

typedef Set<CxtStmt> SVF::LockAnalysis::CxtStmtSet

Definition at line 69 of file LockAnalysis.h.

◆ CxtStmtToCxtLockSet

typedef Map<CxtStmt, CxtLockSet> SVF::LockAnalysis::CxtStmtToCxtLockSet

Definition at line 76 of file LockAnalysis.h.

◆ CxtStmtToLockFlagMap

typedef Map<CxtStmt, ValDomain> SVF::LockAnalysis::CxtStmtToLockFlagMap

Definition at line 66 of file LockAnalysis.h.

◆ CxtStmtWorkList

typedef FIFOWorkList<CxtStmt> SVF::LockAnalysis::CxtStmtWorkList

Definition at line 67 of file LockAnalysis.h.

◆ FunSet

typedef Set<const SVFFunction*> SVF::LockAnalysis::FunSet

Definition at line 64 of file LockAnalysis.h.

◆ InstSet

typedef Set<const ICFGNode*> SVF::LockAnalysis::InstSet

Definition at line 61 of file LockAnalysis.h.

◆ InstToCxtStmt

typedef Map<const ICFGNode*, CxtStmtSet> SVF::LockAnalysis::InstToCxtStmt

Definition at line 80 of file LockAnalysis.h.

◆ InstToCxtStmtSet

typedef Map<const ICFGNode*, LockSpan> SVF::LockAnalysis::InstToCxtStmtSet

Definition at line 75 of file LockAnalysis.h.

◆ InstToInstSetMap

typedef Map<const ICFGNode*, InstSet> SVF::LockAnalysis::InstToInstSetMap

Definition at line 65 of file LockAnalysis.h.

◆ InstVec

typedef TCT::InstVec SVF::LockAnalysis::InstVec

Definition at line 60 of file LockAnalysis.h.

◆ LockSet

typedef NodeBS SVF::LockAnalysis::LockSet

Definition at line 59 of file LockAnalysis.h.

◆ LockSiteToLockSet

typedef Map<const ICFGNode*, NodeBS> SVF::LockAnalysis::LockSiteToLockSet

Definition at line 74 of file LockAnalysis.h.

◆ LockSpan

typedef Set<CxtStmt> SVF::LockAnalysis::LockSpan

Definition at line 68 of file LockAnalysis.h.

Member Enumeration Documentation

◆ ValDomain

enum SVF::LockAnalysis::ValDomain

semilattice Empty==>TDUnlocked==>TDLocked

Enumerator
Empty
TDLocked
TDUnlocked

Definition at line 49 of file LockAnalysis.h.

     {
         Empty,  // initial(dummy) state
         TDLocked,  // stmt is locked
         TDUnlocked,  //  stmt is unlocked
     };

Constructor & Destructor Documentation

◆ LockAnalysis()

SVF::LockAnalysis::LockAnalysis ( TCT * t )

inline

Definition at line 82 of file LockAnalysis.h.

                          : tct(t), lockTime(0),numOfTotalQueries(0), numOfLockedQueries(0), lockQueriesTime(0)
     {
     }

Member Function Documentation

◆ addCondIntraLock()

void SVF::LockAnalysis::addCondIntraLock	(	const ICFGNode *	lockSite,
		const InstSet &	stmts
	)

inline

Add intra-procedural lock.

Definition at line 120 of file LockAnalysis.h.

     {
         for(InstSet::const_iterator it = stmts.begin(), eit = stmts.end(); it!=eit; ++it)
         {
             instTocondCILocksMap[*it].insert(lockSite);
         }
     }

◆ addCxtLock()

void SVF::LockAnalysis::addCxtLock	(	const CallStrCxt &	cxt,
		const ICFGNode *	inst
	)

inline

Context-sensitive locks.

Add inter-procedural context-sensitive lock

Definition at line 151 of file LockAnalysis.h.

     {
         CxtLock cxtlock(cxt,inst);
         cxtLockset.insert(cxtlock);
         DBOUT(DMTA, SVFUtil::outs() << "LockAnalysis Process new lock "; cxtlock.dump());
     }

◆ addCxtStmtToSpan()

bool SVF::LockAnalysis::addCxtStmtToSpan	(	const CxtStmt &	cts,
		const CxtLock &	cl
	)

inline

Add context-sensitive statement.

Definition at line 232 of file LockAnalysis.h.

     {
         cxtLocktoSpan[cl].insert(cts);
         return cxtStmtToCxtLockSet[cts].insert(cl).second;
     }

◆ addIntraLock()

void SVF::LockAnalysis::addIntraLock	(	const ICFGNode *	lockSite,
		const InstSet &	stmts
	)

inline

Add intra-procedural lock.

Definition at line 110 of file LockAnalysis.h.

     {
         for(InstSet::const_iterator it = stmts.begin(), eit = stmts.end(); it!=eit; ++it)
         {
             instCILocksMap[*it].insert(lockSite);
             ciLocktoSpan[lockSite].insert(*it);
         }
     }

◆ alias()

bool SVF::LockAnalysis::alias	(	const CxtLockSet &	lockset1,
		const CxtLockSet &	lockset2
	)

inline

Return true if two locksets has at least one alias lock.

Definition at line 179 of file LockAnalysis.h.

     {
         for(CxtLockSet::const_iterator it = lockset1.begin(), eit = lockset1.end(); it!=eit; ++it)
         {
             const CxtLock& lock = *it;
             for(CxtLockSet::const_iterator lit = lockset2.begin(), elit = lockset2.end(); lit!=elit; ++lit)
             {
                 if(isAliasedLocks(lock,*lit))
                     return true;
             }
         }
         return false;
     }

◆ analyze()

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.

 {
  
     collectLockUnlocksites();
     buildCandidateFuncSetforLock();
  
     DOTIMESTAT(double lockStart = PTAStat::getClk(true));
  
     DBOUT(DGENERAL, outs() << "\tIntra-procedural LockAnalysis\n");
     DBOUT(DMTA, outs() << "\tIntra-procedural LockAnalysis\n");
     analyzeIntraProcedualLock();
  
     DBOUT(DGENERAL, outs() << "\tCollect context-sensitive locks\n");
     DBOUT(DMTA, outs() << "\tCollect context-sensitive locks\n");
     collectCxtLock();
  
     DBOUT(DGENERAL, outs() << "\tInter-procedural LockAnalysis\n");
     DBOUT(DMTA, outs() << "\tInter-procedural LockAnalysis\n");
     analyzeLockSpanCxtStmt();
  
     DOTIMESTAT(double lockEnd = PTAStat::getClk(true));
     DOTIMESTAT(lockTime += (lockEnd - lockStart) / TIMEINTERVAL);
 }

◆ analyzeIntraProcedualLock()

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.

 {
  
     // Identify the protected Instructions.
     for (InstSet::const_iterator it = locksites.begin(), ie = locksites.end(); it != ie; ++it)
     {
         const ICFGNode* lockSite = *it;
         assert(isCallSite(lockSite) && "Lock acquire instruction must be a CallSite");
  
         // Perform forward traversal
         InstSet forwardInsts;
         InstSet backwardInsts;
         InstSet unlockSet;
  
         bool forward = intraForwardTraverse(lockSite,unlockSet,forwardInsts);
         bool backward = intraBackwardTraverse(unlockSet,backwardInsts);
  
         if(forward && backward)
             addIntraLock(lockSite,forwardInsts);
         else if(forward && !backward)
             addCondIntraLock(lockSite,forwardInsts);
     }
 }

◆ analyzeLockSpanCxtStmt()

void LockAnalysis::analyzeLockSpanCxtStmt ( )

Definition at line 330 of file LockAnalysis.cpp.

 {
  
     FunSet entryFuncSet = tct->getEntryProcs();
     for (FunSet::const_iterator it = entryFuncSet.begin(), eit = entryFuncSet.end(); it != eit; ++it)
     {
         if (!isLockCandidateFun(*it))
             continue;
         CallStrCxt cxt;
         const ICFGNode* frontInst = (*it)->getEntryBlock()->front();
         CxtStmt cxtstmt(cxt, frontInst);
         pushToCTSWorkList(cxtstmt);
     }
  
     while (!cxtStmtList.empty())
     {
         CxtStmt cts = popFromCTSWorkList();
  
         touchCxtStmt(cts);
         const ICFGNode* curInst = cts.getStmt();
         instToCxtStmtSet[curInst].insert(cts);
  
         DBOUT(DMTA, outs() << "\nVisit cxtStmt: ");
         DBOUT(DMTA, cts.dump());
  
         DBOUT(DMTA, outs() << "\nIts cxt lock sets: ");
         DBOUT(DMTA, printLocks(cts));
  
         if (isTDFork(curInst))
         {
             handleFork(cts);
         }
         else if (isTDAcquire(curInst))
         {
             assert(hasCxtLock(cts) && "context-sensitive lock not found!!");
             if(addCxtStmtToSpan(cts,cts))
                 handleIntra(cts);
         }
         else if (isTDRelease(curInst))
         {
             if(removeCxtStmtToSpan(cts,cts))
                 handleIntra(cts);
         }
         else if (isCallSite(curInst) && !isExtCall(curInst))
         {
             handleCall(cts);
         }
         else if (isRetInstNode(curInst))
         {
             handleRet(cts);
         }
         else
         {
             handleIntra(cts);
         }
  
     }
  
 }

◆ buildCandidateFuncSetforLock()

void LockAnalysis::buildCandidateFuncSetforLock ( )

Collect candidate functions for context-sensitive lock analysis

Definition at line 95 of file LockAnalysis.cpp.

 {
  
     ThreadCallGraph* tcg=tct->getThreadCallGraph();
  
     TCT::PTACGNodeSet visited;
     FIFOWorkList<const PTACallGraphNode*> worklist;
  
     for (InstSet::iterator it = locksites.begin(), eit = locksites.end(); it != eit; ++it)
     {
         const SVFFunction* fun=(*it)->getFun();
         PTACallGraphNode* cgnode = tcg->getCallGraphNode(fun);
         if (visited.find(cgnode) == visited.end())
         {
             worklist.push(cgnode);
             visited.insert(cgnode);
         }
     }
     for (InstSet::iterator it = unlocksites.begin(), eit = unlocksites.end(); it != eit; ++it)
     {
         const SVFFunction* fun = (*it)->getFun();
         PTACallGraphNode* cgnode = tcg->getCallGraphNode(fun);
         if (visited.find(cgnode) == visited.end())
         {
             worklist.push(cgnode);
             visited.insert(cgnode);
         }
     }
     while (!worklist.empty())
     {
         const PTACallGraphNode* node = worklist.pop();
         lockcandidateFuncSet.insert(node->getFunction());
         for (PTACallGraphNode::const_iterator nit = node->InEdgeBegin(), neit = node->InEdgeEnd(); nit != neit; nit++)
         {
             const PTACallGraphNode* srcNode = (*nit)->getSrcNode();
             if (visited.find(srcNode) == visited.end())
             {
                 visited.insert(srcNode);
                 worklist.push(srcNode);
             }
         }
     }
 }

◆ clearFlagMap()

void SVF::LockAnalysis::clearFlagMap ( )

inlineprivate

Clear flags.

Definition at line 391 of file LockAnalysis.h.

     {
         cxtStmtList.clear();
     }

◆ collectCxtLock()

void LockAnalysis::collectCxtLock ( )

Definition at line 259 of file LockAnalysis.cpp.

 {
     FunSet entryFuncSet = tct->getEntryProcs();
     for (FunSet::const_iterator it = entryFuncSet.begin(), eit = entryFuncSet.end(); it != eit; ++it)
     {
         if (!isLockCandidateFun(*it))
             continue;
         CallStrCxt cxt;
         CxtLockProc t(cxt, *it);
         pushToCTPWorkList(t);
     }
  
     while (!clpList.empty())
     {
         CxtLockProc clp = popFromCTPWorkList();
         PTACallGraphNode* cgNode = getTCG()->getCallGraphNode(clp.getProc());
         // lzh TODO.
         if (!isLockCandidateFun(cgNode->getFunction()))
             continue;
  
         for (PTACallGraphNode::const_iterator nit = cgNode->OutEdgeBegin(), neit = cgNode->OutEdgeEnd(); nit != neit; nit++)
         {
             const PTACallGraphEdge* cgEdge = (*nit);
  
             for (PTACallGraphEdge::CallInstSet::const_iterator cit = cgEdge->directCallsBegin(), ecit = cgEdge->directCallsEnd();
                     cit != ecit; ++cit)
             {
                 DBOUT(DMTA,
                       outs() << "\nCollecting CxtLocks: handling direct call:" << **cit << "\t" << cgEdge->getSrcNode()->getFunction()->getName()
                       << "-->" << cgEdge->getDstNode()->getFunction()->getName() << "\n");
                 handleCallRelation(clp, cgEdge, *cit);
             }
             for (PTACallGraphEdge::CallInstSet::const_iterator ind = cgEdge->indirectCallsBegin(), eind = cgEdge->indirectCallsEnd();
                     ind != eind; ++ind)
             {
                 DBOUT(DMTA,
                       outs() << "\nCollecting CxtLocks: handling indirect call:" << **ind << "\t"
                       << cgEdge->getSrcNode()->getFunction()->getName() << "-->" << cgEdge->getDstNode()->getFunction()->getName()
                       << "\n");
                 handleCallRelation(clp, cgEdge, *ind);
             }
         }
     }
 }

◆ collectLockUnlocksites()

void LockAnalysis::collectLockUnlocksites ( )

Collect lock/unlock sites

Definition at line 69 of file LockAnalysis.cpp.

 {
     ThreadCallGraph* tcg=tct->getThreadCallGraph();
  
     for (const SVFFunction* F : tct->getSVFModule()->getFunctionSet())
     {
         for (const SVFBasicBlock* bb : F->getBasicBlockList())
         {
             for (const ICFGNode* icfgNode : bb->getICFGNodeList())
             {
                 if (isa<CallICFGNode>(icfgNode) && tcg->getThreadAPI()->isTDRelease(cast<CallICFGNode>(icfgNode)))
                 {
                     unlocksites.insert(icfgNode);
                 }
                 if (isa<CallICFGNode>(icfgNode) && tcg->getThreadAPI()->isTDAcquire(cast<CallICFGNode>(icfgNode)))
                 {
                     locksites.insert(icfgNode);
                 }
             }
         }
     }
 }

◆ getCSTCLS()

CxtStmtToCxtLockSet SVF::LockAnalysis::getCSTCLS ( )

inline

Definition at line 249 of file LockAnalysis.h.

     {
         return cxtStmtToCxtLockSet;
     }

◆ getCxtLockfromCxtStmt() [1/2]

CxtLockSet& SVF::LockAnalysis::getCxtLockfromCxtStmt ( const CxtStmt & cts )

inline

Definition at line 225 of file LockAnalysis.h.

     {
         CxtStmtToCxtLockSet::iterator it = cxtStmtToCxtLockSet.find(cts);
         assert(it != cxtStmtToCxtLockSet.end());
         return it->second;
     }

◆ getCxtLockfromCxtStmt() [2/2]

const CxtLockSet& SVF::LockAnalysis::getCxtLockfromCxtStmt ( const CxtStmt & cts ) const

inline

Definition at line 219 of file LockAnalysis.h.

     {
         CxtStmtToCxtLockSet::const_iterator it = cxtStmtToCxtLockSet.find(cts);
         assert(it != cxtStmtToCxtLockSet.end());
         return it->second;
     }

◆ getCxtStmtfromInst()

const CxtStmtSet& SVF::LockAnalysis::getCxtStmtfromInst ( const ICFGNode * inst ) const

inline

Definition at line 208 of file LockAnalysis.h.

     {
         InstToCxtStmtSet::const_iterator it = instToCxtStmtSet.find(inst);
         assert(it != instToCxtStmtSet.end());
         return it->second;
     }

◆ getIntraLockSet()

const InstSet& SVF::LockAnalysis::getIntraLockSet ( const ICFGNode * stmt ) const

inline

Definition at line 140 of file LockAnalysis.h.

     {
         InstToInstSetMap::const_iterator it = instCILocksMap.find(stmt);
         assert(it!=instCILocksMap.end() && "intralock not found!");
         return it->second;
     }

◆ getLockVal()

const SVFVar* SVF::LockAnalysis::getLockVal ( const ICFGNode * call )

inlineprivate

Get lock value.

Definition at line 469 of file LockAnalysis.h.

     {
         return getTCG()->getThreadAPI()->getLockVal(call);
     }

◆ getNumOfCxtLocks()

u32_t SVF::LockAnalysis::getNumOfCxtLocks ( )

inline

Definition at line 316 of file LockAnalysis.h.

     {
         return cxtLockset.size();
     }

◆ getSpanfromCxtLock()

LockSpan& SVF::LockAnalysis::getSpanfromCxtLock ( const CxtLock & cl )

inline

Definition at line 262 of file LockAnalysis.h.

     {
         assert(cxtLocktoSpan.find(cl) != cxtLocktoSpan.end());
         return cxtLocktoSpan[cl];
     }

◆ getTCG()

ThreadCallGraph* SVF::LockAnalysis::getTCG ( ) const

inlineprivate

ThreadCallGraph.

Definition at line 474 of file LockAnalysis.h.

     {
         return tct->getThreadCallGraph();
     }

◆ getTCT()

TCT* SVF::LockAnalysis::getTCT ( )

inline

Get tct.

Definition at line 324 of file LockAnalysis.h.

     {
         return tct;
     }

◆ handleCall()

void LockAnalysis::handleCall ( const CxtStmt & cts )

private

Handle call.

Definition at line 428 of file LockAnalysis.cpp.

 {
  
     const CallStrCxt& curCxt = cts.getContext();
     const CallICFGNode* call = SVFUtil::dyn_cast<CallICFGNode>(cts.getStmt());
     if (getTCG()->hasCallGraphEdge(call))
     {
         for (PTACallGraph::CallGraphEdgeSet::const_iterator cgIt = getTCG()->getCallEdgeBegin(call), ecgIt = getTCG()->getCallEdgeEnd(call);
                 cgIt != ecgIt; ++cgIt)
         {
             const SVFFunction* svfcallee = (*cgIt)->getDstNode()->getFunction();
             if (SVFUtil::isExtCall(svfcallee))
                 continue;
             CallStrCxt newCxt = curCxt;
             pushCxt(newCxt, call, svfcallee);
             const ICFGNode* svfInst = svfcallee->getEntryBlock()->front();
             CxtStmt newCts(newCxt, svfInst);
             markCxtStmtFlag(newCts, cts);
         }
     }
 }

◆ handleCallRelation()

void LockAnalysis::handleCallRelation	(	CxtLockProc &	clp,
		const PTACallGraphEdge *	cgEdge,
		const CallICFGNode *	cs
	)

private

Handle call relations.

Handling call relations when collecting context-sensitive locks

Definition at line 308 of file LockAnalysis.cpp.

 {
  
     CallStrCxt cxt(clp.getContext());
     const ICFGNode* curNode = cs;
     if (isTDAcquire(curNode))
     {
         addCxtLock(cxt,curNode);
         return;
     }
     const SVFFunction* svfcallee = cgEdge->getDstNode()->getFunction();
     pushCxt(cxt, SVFUtil::cast<CallICFGNode>(curNode), svfcallee);
  
     CxtLockProc newclp(cxt, svfcallee);
     if (pushToCTPWorkList(newclp))
     {
         DBOUT(DMTA, outs() << "LockAnalysis Process CallRet old clp --"; clp.dump());
         DBOUT(DMTA, outs() << "LockAnalysis Process CallRet new clp --"; newclp.dump());
     }
  
 }

◆ handleFork()

void LockAnalysis::handleFork ( const CxtStmt & cts )

private

Handle fork.

Definition at line 407 of file LockAnalysis.cpp.

 {
     const CallStrCxt& curCxt = cts.getContext();
     const CallICFGNode* call = SVFUtil::dyn_cast<CallICFGNode>(cts.getStmt());
     if(getTCG()->hasThreadForkEdge(call))
     {
         for (ThreadCallGraph::ForkEdgeSet::const_iterator cgIt = getTCG()->getForkEdgeBegin(call),
                 ecgIt = getTCG()->getForkEdgeEnd(call); cgIt != ecgIt; ++cgIt)
         {
             const SVFFunction* svfcallee = (*cgIt)->getDstNode()->getFunction();
             CallStrCxt newCxt = curCxt;
             pushCxt(newCxt,call,svfcallee);
             const ICFGNode* svfInst = svfcallee->getEntryBlock()->front();
             CxtStmt newCts(newCxt, svfInst);
             markCxtStmtFlag(newCts, cts);
         }
     }
     handleIntra(cts);
 }

◆ handleIntra()

void LockAnalysis::handleIntra ( const CxtStmt & cts )

private

Handle intra.

Definition at line 502 of file LockAnalysis.cpp.

 {
  
     const ICFGNode* curInst = cts.getStmt();
     const CallStrCxt& curCxt = cts.getContext();
  
     for(const ICFGEdge* outEdge : curInst->getOutEdges())
     {
         if(outEdge->getDstNode()->getFun() == curInst->getFun())
         {
             CxtStmt newCts(curCxt, outEdge->getDstNode());
             markCxtStmtFlag(newCts, cts);
         }
     }
 }

◆ handleRet()

void LockAnalysis::handleRet ( const CxtStmt & cts )

private

Handle return.

Definition at line 451 of file LockAnalysis.cpp.

 {
  
     const ICFGNode* curInst = cts.getStmt();
     const CallStrCxt& curCxt = cts.getContext();
     const SVFFunction* svffun = curInst->getFun();
     PTACallGraphNode* curFunNode = getTCG()->getCallGraphNode(svffun);
  
     for (PTACallGraphNode::const_iterator it = curFunNode->getInEdges().begin(), eit = curFunNode->getInEdges().end(); it != eit; ++it)
     {
         PTACallGraphEdge* edge = *it;
         if (SVFUtil::isa<ThreadForkEdge, ThreadJoinEdge>(edge))
             continue;
         for (PTACallGraphEdge::CallInstSet::const_iterator cit = (edge)->directCallsBegin(), ecit = (edge)->directCallsEnd(); cit != ecit;
                 ++cit)
         {
             CallStrCxt newCxt = curCxt;
             const ICFGNode* inst = *cit;
             if (matchCxt(newCxt, SVFUtil::cast<CallICFGNode>(inst), curFunNode->getFunction()))
             {
                 for(const ICFGEdge* outEdge : curInst->getOutEdges())
                 {
                     if(outEdge->getDstNode()->getFun() == curInst->getFun())
                     {
                         CxtStmt newCts(newCxt, outEdge->getDstNode());
                         markCxtStmtFlag(newCts, cts);
                     }
                 }
             }
         }
         for (PTACallGraphEdge::CallInstSet::const_iterator cit = (edge)->indirectCallsBegin(), ecit = (edge)->indirectCallsEnd();
                 cit != ecit; ++cit)
         {
             CallStrCxt newCxt = curCxt;
             const ICFGNode* inst = *cit;
             if (matchCxt(newCxt, SVFUtil::cast<CallICFGNode>(inst), curFunNode->getFunction()))
             {
                 for(const ICFGEdge* outEdge : curInst->getOutEdges())
                 {
                     if(outEdge->getDstNode()->getFun() == curInst->getFun())
                     {
                         CxtStmt newCts(newCxt, outEdge->getDstNode());
                         markCxtStmtFlag(newCts, cts);
                     }
                 }
             }
         }
     }
 }

◆ hasAllCxtInLockSpan()

bool SVF::LockAnalysis::hasAllCxtInLockSpan	(	const ICFGNode *	I,
		LockSpan	lspan
	)		const

inline

Definition at line 287 of file LockAnalysis.h.

     {
         if(!hasCxtStmtfromInst(I))
             return false;
         const LockSpan ctsset = getCxtStmtfromInst(I);
         for (LockSpan::const_iterator cts = ctsset.begin(), ects = ctsset.end(); cts != ects; cts++)
         {
             if (lspan.find(*cts) == lspan.end())
             {
                 return false;
             }
         }
         return true;
     }

◆ hasCxtLock()

bool SVF::LockAnalysis::hasCxtLock ( const CxtLock & cxtLock ) const

inline

Get context-sensitive lock.

Definition at line 159 of file LockAnalysis.h.

     {
         return cxtLockset.find(cxtLock)!=cxtLockset.end();
     }

◆ hasCxtLockfromCxtStmt()

bool SVF::LockAnalysis::hasCxtLockfromCxtStmt ( const CxtStmt & cts ) const

inline

Definition at line 214 of file LockAnalysis.h.

     {
         CxtStmtToCxtLockSet::const_iterator it = cxtStmtToCxtLockSet.find(cts);
         return (it != cxtStmtToCxtLockSet.end());
     }

◆ hasCxtStmtfromInst()

bool SVF::LockAnalysis::hasCxtStmtfromInst ( const ICFGNode * inst ) const

inline

Context-sensitive statement and lock spans.

Get LockSet and LockSpan

Definition at line 203 of file LockAnalysis.h.

     {
         InstToCxtStmtSet::const_iterator it = instToCxtStmtSet.find(inst);
         return (it != instToCxtStmtSet.end());
     }

◆ hasOneCxtInLockSpan()

bool SVF::LockAnalysis::hasOneCxtInLockSpan	(	const ICFGNode *	I,
		LockSpan	lspan
	)		const

inline

Check if one instruction's context stmt is in a lock span.

Definition at line 272 of file LockAnalysis.h.

     {
         if(!hasCxtStmtfromInst(I))
             return false;
         const LockSpan ctsset = getCxtStmtfromInst(I);
         for (LockSpan::const_iterator cts = ctsset.begin(), ects = ctsset.end(); cts != ects; cts++)
         {
             if(lspan.find(*cts) != lspan.end())
             {
                 return true;
             }
         }
         return false;
     }

◆ hasSpanfromCxtLock()

bool SVF::LockAnalysis::hasSpanfromCxtLock ( const CxtLock & cl )

inline

Definition at line 258 of file LockAnalysis.h.

     {
         return cxtLocktoSpan.find(cl) != cxtLocktoSpan.end();
     }

◆ intersect()

bool SVF::LockAnalysis::intersect	(	CxtLockSet &	tgrlockset,
		const CxtLockSet &	srclockset
	)

inlineprivate

Definition at line 375 of file LockAnalysis.h.

     {
         CxtLockSet toBeDeleted;
         for(CxtLockSet::const_iterator it = tgrlockset.begin(), eit = tgrlockset.end(); it!=eit; ++it)
         {
             if(srclockset.find(*it)==srclockset.end())
                 toBeDeleted.insert(*it);
         }
         for(CxtLockSet::const_iterator it = toBeDeleted.begin(), eit = toBeDeleted.end(); it!=eit; ++it)
         {
             tgrlockset.erase(*it);
         }
         return !toBeDeleted.empty();
     }

◆ intersects()

bool SVF::LockAnalysis::intersects	(	const CxtLockSet &	lockset1,
		const CxtLockSet &	lockset2
	)		const

inline

Return true if the intersection of two locksets is not empty.

Definition at line 165 of file LockAnalysis.h.

     {
         for(CxtLockSet::const_iterator it = lockset1.begin(), eit = lockset1.end(); it!=eit; ++it)
         {
             const CxtLock& lock = *it;
             for(CxtLockSet::const_iterator lit = lockset2.begin(), elit = lockset2.end(); lit!=elit; ++lit)
             {
                 if(lock==*lit)
                     return true;
             }
         }
         return false;
     }

◆ intraBackwardTraverse()

bool LockAnalysis::intraBackwardTraverse	(	const InstSet &	unlockSet,
		InstSet &	backwardInsts
	)

Intra-procedural backward traversal

Definition at line 215 of file LockAnalysis.cpp.

 {
  
     InstVec worklist;
     for(InstSet::const_iterator it = unlockSet.begin(), eit = unlockSet.end(); it!=eit; ++it)
     {
         const ICFGNode* unlockSite = *it;
         const ICFGNode* entryInst = unlockSite->getFun()->getEntryBlock()->back();
         worklist.push_back(*it);
  
         while (!worklist.empty())
         {
             const ICFGNode *I = worklist.back();
             worklist.pop_back();
  
             if(entryInst == I)
                 return false;
  
             // Skip the visited Instructions.
             if (backwardInsts.find(I)!=backwardInsts.end())
                 continue;
             backwardInsts.insert(I);
  
             if (isTDAcquire(I) && isAliasedLocks(unlockSite, I))
             {
                 DBOUT(DMTA, outs() << "LockAnalysis ci lock   -- " << I->getSourceLoc()<<"\n");
                 DBOUT(DMTA, outs() << "LockAnalysis ci unlock -- " << unlockSite->getSourceLoc()<<"\n");
                 continue;
             }
  
             for(const ICFGEdge* inEdge : I->getInEdges())
             {
                 if(inEdge->getSrcNode()->getFun() == I->getFun())
                 {
                     worklist.push_back(inEdge->getSrcNode());
                 }
             }
         }
     }
  
     return true;
 }

◆ intraForwardTraverse()

bool LockAnalysis::intraForwardTraverse	(	const ICFGNode *	lockSite,
		InstSet &	unlockSet,
		InstSet &	forwardInsts
	)

Intra-procedural forward traversal

Definition at line 171 of file LockAnalysis.cpp.

 {
  
     const SVFFunction* svfFun = lockSite->getFun();
  
     InstVec worklist;
     worklist.push_back(lockSite);
     while (!worklist.empty())
     {
         const ICFGNode *I = worklist.back();
         worklist.pop_back();
         const ICFGNode* exitInst = svfFun->getExitBB()->back();
         if(exitInst == I)
             return false;
  
         // Skip the visited Instructions.
         if (forwardInsts.find(I)!=forwardInsts.end())
             continue;
         forwardInsts.insert(I);
  
         if (isTDRelease(I) && isAliasedLocks(lockSite, I))
         {
             unlockSet.insert(I);
             DBOUT(DMTA, outs() << "LockAnalysis ci lock   -- " << lockSite->getSourceLoc()<<"\n");
             DBOUT(DMTA, outs() << "LockAnalysis ci unlock -- " << I->getSourceLoc()<<"\n");
             continue;
         }
  
         for(const ICFGEdge* outEdge : I->getOutEdges())
         {
             if(outEdge->getDstNode()->getFun() == I->getFun())
             {
                 worklist.push_back(outEdge->getDstNode());
             }
         }
     }
  
     return true;
 }

◆ isAliasedLocks() [1/2]

bool SVF::LockAnalysis::isAliasedLocks	(	const CxtLock &	cl1,
		const CxtLock &	cl2
	)

inlineprivate

Return true it a lock matches an unlock.

Definition at line 345 of file LockAnalysis.h.

     {
         return isAliasedLocks(cl1.getStmt(), cl2.getStmt());
     }

◆ isAliasedLocks() [2/2]

bool SVF::LockAnalysis::isAliasedLocks	(	const ICFGNode *	i1,
		const ICFGNode *	i2
	)

inlineprivate

todo: must alias

Definition at line 349 of file LockAnalysis.h.

     {
         return tct->getPTA()->alias(getLockVal(i1)->getId(), getLockVal(i2)->getId());
     }

◆ isCallSite()

bool SVF::LockAnalysis::isCallSite ( const ICFGNode * inst )

inlineprivate

Whether it is a callsite.

Definition at line 459 of file LockAnalysis.h.

     {
         return tct->isCallSite(inst);
     }

◆ isExtCall()

bool SVF::LockAnalysis::isExtCall ( const ICFGNode * inst )

inlineprivate

Whether it is calling an external function.

Definition at line 464 of file LockAnalysis.h.

     {
         return tct->isExtCall(inst);
     }

◆ isInSameCISpan()

bool LockAnalysis::isInSameCISpan	(	const ICFGNode *	i1,
		const ICFGNode *	i2
	)		const

Return true if two instructions are inside same context-insensitive lock span

Definition at line 656 of file LockAnalysis.cpp.

 {
     if(!isInsideCondIntraLock(i1) && !isInsideCondIntraLock(i2))
     {
         const InstSet& lockset1 = getIntraLockSet(i1);
         const InstSet& lockset2 = getIntraLockSet(i2);
         for (InstSet::const_iterator cil1 = lockset1.begin(), ecil1 = lockset1.end(); cil1!=ecil1; ++cil1)
         {
             for (InstSet::const_iterator cil2=lockset2.begin(), ecil2=lockset2.end(); cil2!=ecil2; ++cil2)
             {
                 if (*cil1==*cil2)
                     return true;
             }
         }
     }
     return false;
 }

◆ isInSameCSSpan() [1/2]

bool LockAnalysis::isInSameCSSpan	(	const CxtStmt &	cxtStmt1,
		const CxtStmt &	cxtStmt2
	)		const

Return true if two context-sensitive instructions are inside same context-insensitive lock spa

Definition at line 677 of file LockAnalysis.cpp.

 {
     if(!hasCxtLockfromCxtStmt(cxtStmt1) || !hasCxtLockfromCxtStmt(cxtStmt2))
         return true;
     const CxtLockSet& lockset1 = getCxtLockfromCxtStmt(cxtStmt1);
     const CxtLockSet& lockset2 = getCxtLockfromCxtStmt(cxtStmt2);
     return intersects(lockset1,lockset2);
 }

◆ isInSameCSSpan() [2/2]

bool LockAnalysis::isInSameCSSpan	(	const ICFGNode *	I1,
		const ICFGNode *	I2
	)		const

Return true if two instructions are inside at least one common context-sensitive lock span

Definition at line 688 of file LockAnalysis.cpp.

 {
     if(!hasCxtStmtfromInst(I1) || !hasCxtStmtfromInst(I2))
         return false;
     const CxtStmtSet& ctsset1 = getCxtStmtfromInst(I1);
     const CxtStmtSet& ctsset2 = getCxtStmtfromInst(I2);
  
     for (CxtStmtSet::const_iterator cts1 = ctsset1.begin(), ects1 = ctsset1.end(); cts1 != ects1; cts1++)
     {
         const CxtStmt& cxtStmt1 = *cts1;
         for (CxtStmtSet::const_iterator cts2 = ctsset2.begin(), ects2 = ctsset2.end(); cts2 != ects2; cts2++)
         {
             const CxtStmt& cxtStmt2 = *cts2;
             if(cxtStmt1==cxtStmt2) continue;
             if(isInSameCSSpan(cxtStmt1,cxtStmt2)==false)
                 return false;
         }
     }
     return true;
 }

◆ isInSameSpan()

bool LockAnalysis::isInSameSpan	(	const ICFGNode *	i1,
		const ICFGNode *	i2
	)

Return true if two instructions are inside at least one common lock span

Definition at line 638 of file LockAnalysis.cpp.

 {
     DOTIMESTAT(double queryStart = PTAStat::getClk(true));
  
     bool sameSpan = false;
     if (isInsideIntraLock(i1) && isInsideIntraLock(i2))
         sameSpan = isInSameCISpan(i1, i2);
     else
         sameSpan = isInSameCSSpan(i1, i2);
  
     DOTIMESTAT(double queryEnd = PTAStat::getClk(true));
     DOTIMESTAT(lockQueriesTime += (queryEnd - queryStart) / TIMEINTERVAL);
     return sameSpan;
 }

◆ isInsideCondIntraLock()

bool SVF::LockAnalysis::isInsideCondIntraLock ( const ICFGNode * stmt ) const

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.

     {
         return instTocondCILocksMap.find(stmt)!=instTocondCILocksMap.end();
     }

◆ isInsideIntraLock()

bool SVF::LockAnalysis::isInsideIntraLock ( const ICFGNode * stmt ) const

inline

Return true if a statement is inside an intra-procedural lock.

Definition at line 129 of file LockAnalysis.h.

     {
         return instCILocksMap.find(stmt)!=instCILocksMap.end() || isInsideCondIntraLock(stmt);
     }

◆ isIntraLock()

bool SVF::LockAnalysis::isIntraLock ( const ICFGNode * lock ) const

inline

Intraprocedural locks.

Return true if the lock is an intra-procedural lock

Definition at line 103 of file LockAnalysis.h.

     {
         assert(locksites.find(lock)!=locksites.end() && "not a lock site?");
         return ciLocktoSpan.find(lock)!=ciLocktoSpan.end();
     }

◆ isLockCandidateFun()

bool SVF::LockAnalysis::isLockCandidateFun ( const SVFFunction * fun ) const

inline

Return true if it is a candidate function.

Definition at line 195 of file LockAnalysis.h.

     {
         return lockcandidateFuncSet.find(fun)!=lockcandidateFuncSet.end();
     }

◆ isProtectedByCommonCILock()

bool LockAnalysis::isProtectedByCommonCILock	(	const ICFGNode *	i1,
		const ICFGNode *	i2
	)

Protected by at least one common context-insensitive lock

Definition at line 580 of file LockAnalysis.cpp.

 {
  
     if(!isInsideCondIntraLock(i1) && !isInsideCondIntraLock(i2))
     {
         const InstSet& lockset1 = getIntraLockSet(i1);
         const InstSet& lockset2 = getIntraLockSet(i2);
         for (InstSet::const_iterator cil1 = lockset1.begin(), ecil1 = lockset1.end(); cil1!=ecil1; ++cil1)
         {
             for (InstSet::const_iterator cil2=lockset2.begin(), ecil2=lockset2.end(); cil2!=ecil2; ++cil2)
             {
                 if (isAliasedLocks(*cil1, *cil2))
                     return true;
             }
         }
     }
     return false;
 }

◆ isProtectedByCommonCxtLock() [1/2]

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.

 {
     if(!hasCxtLockfromCxtStmt(cxtStmt1) || !hasCxtLockfromCxtStmt(cxtStmt2))
         return true;
     const CxtLockSet& lockset1 = getCxtLockfromCxtStmt(cxtStmt1);
     const CxtLockSet& lockset2 = getCxtLockfromCxtStmt(cxtStmt2);
     return alias(lockset1,lockset2);
 }

◆ isProtectedByCommonCxtLock() [2/2]

bool LockAnalysis::isProtectedByCommonCxtLock	(	const ICFGNode *	i1,
		const ICFGNode *	i2
	)

Protected by at least one common context-sensitive lock under each context

Definition at line 614 of file LockAnalysis.cpp.

 {
     if(!hasCxtStmtfromInst(i1) || !hasCxtStmtfromInst(i2))
         return false;
     const CxtStmtSet& ctsset1 = getCxtStmtfromInst(i1);
     const CxtStmtSet& ctsset2 = getCxtStmtfromInst(i2);
     for (CxtStmtSet::const_iterator cts1 = ctsset1.begin(), ects1 = ctsset1.end(); cts1 != ects1; cts1++)
     {
         const CxtStmt& cxtStmt1 = *cts1;
         for (CxtStmtSet::const_iterator cts2 = ctsset2.begin(), ects2 = ctsset2.end(); cts2 != ects2; cts2++)
         {
             const CxtStmt& cxtStmt2 = *cts2;
             if(cxtStmt1==cxtStmt2) continue;
             if(isProtectedByCommonCxtLock(cxtStmt1,cxtStmt2)==false)
                 return false;
         }
     }
     return true;
 }

◆ isProtectedByCommonLock()

bool LockAnalysis::isProtectedByCommonLock	(	const ICFGNode *	i1,
		const ICFGNode *	i2
	)

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.

 {
     numOfTotalQueries++;
     bool commonlock = false;
     DOTIMESTAT(double queryStart = PTAStat::getClk(true));
     if (isInsideIntraLock(i1) && isInsideIntraLock(i2))
         commonlock = isProtectedByCommonCILock(i1,i2) ;
     else
         commonlock = isProtectedByCommonCxtLock(i1,i2);
     DOTIMESTAT(double queryEnd = PTAStat::getClk(true));
     DOTIMESTAT(lockQueriesTime += (queryEnd - queryStart) / TIMEINTERVAL);
     return commonlock;
 }

◆ isTDAcquire()

bool SVF::LockAnalysis::isTDAcquire ( const ICFGNode * call )

inlineprivate

Whether it is a lock site.

Definition at line 445 of file LockAnalysis.h.

     {
         if(SVFUtil::isa<CallICFGNode>(call) == false)
             return false;
         return getTCG()->getThreadAPI()->isTDAcquire(SVFUtil::cast<CallICFGNode>(call));
     }

◆ isTDFork()

bool SVF::LockAnalysis::isTDFork ( const ICFGNode * call )

inlineprivate

Whether it is a lock site.

Definition at line 438 of file LockAnalysis.h.

     {
         if(SVFUtil::isa<CallICFGNode>(call) == false)
             return false;
         return getTCG()->getThreadAPI()->isTDFork(SVFUtil::cast<CallICFGNode>(call));
     }

◆ isTDRelease()

bool SVF::LockAnalysis::isTDRelease ( const ICFGNode * call )

inlineprivate

Whether it is a unlock site.

Definition at line 452 of file LockAnalysis.h.

     {
         if(SVFUtil::isa<CallICFGNode>(call) == false)
             return false;
         return getTCG()->getThreadAPI()->isTDRelease(SVFUtil::cast<CallICFGNode>(call));
     }

◆ isVisitedCTPs()

bool SVF::LockAnalysis::isVisitedCTPs ( const CxtLockProc & clp ) const

inlineprivate

Definition at line 413 of file LockAnalysis.h.

     {
         return visitedCTPs.find(clp) != visitedCTPs.end();
     }

◆ markCxtStmtFlag()

void SVF::LockAnalysis::markCxtStmtFlag	(	const CxtStmt &	tgr,
		const CxtStmt &	src
	)

inlineprivate

Mark thread flags for cxtStmt.

Transfer function for marking context-sensitive statement

Definition at line 358 of file LockAnalysis.h.

     {
         const CxtLockSet& srclockset = getCxtLockfromCxtStmt(src);
         if(hasCxtLockfromCxtStmt(tgr)== false)
         {
             for(CxtLockSet::const_iterator it = srclockset.begin(), eit = srclockset.end(); it!=eit; ++it)
             {
                 addCxtStmtToSpan(tgr,*it);
             }
             pushToCTSWorkList(tgr);
         }
         else
         {
             if(intersect(getCxtLockfromCxtStmt(tgr),srclockset))
                 pushToCTSWorkList(tgr);
         }
     }

◆ matchCxt()

bool LockAnalysis::matchCxt	(	CallStrCxt &	cxt,
		const CallICFGNode *	call,
		const SVFFunction *	callee
	)

private

Match context.

partial match

Definition at line 535 of file LockAnalysis.cpp.

 {
     const SVFFunction* svfcaller = call->getFun();
     CallSiteID csId = getTCG()->getCallSiteID(call, callee);
  
 //    /// handle calling context for candidate functions only
 //    if (isLockCandidateFun(caller) == false)
 //        return true;
  
     if (cxt.empty())
         return true;
  
     if (tct->inSameCallGraphSCC(getTCG()->getCallGraphNode(svfcaller), getTCG()->getCallGraphNode(callee)) == false)
     {
         if (cxt.back() == csId)
             cxt.pop_back();
         else
             return false;
         DBOUT(DMTA, tct->dumpCxt(cxt));
     }
     return true;
 }

◆ popFromCTPWorkList()

CxtLockProc SVF::LockAnalysis::popFromCTPWorkList ( )

inlineprivate

Definition at line 408 of file LockAnalysis.h.

     {
         CxtLockProc clp = clpList.pop();
         return clp;
     }

◆ popFromCTSWorkList()

CxtStmt SVF::LockAnalysis::popFromCTSWorkList ( )

inlineprivate

Definition at line 425 of file LockAnalysis.h.

     {
         CxtStmt clp = cxtStmtList.pop();
         return clp;
     }

◆ printLocks()

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.

 {
     const CxtLockSet & lockset = getCxtLockfromCxtStmt(cts);
     outs() << "\nlock sets size = " << lockset.size() << "\n";
     for (CxtLockSet::const_iterator it = lockset.begin(), eit = lockset.end(); it != eit; ++it)
     {
         (*it).dump();
     }
 }

◆ pushCxt()

void LockAnalysis::pushCxt	(	CallStrCxt &	cxt,
		const CallICFGNode *	call,
		const SVFFunction *	callee
	)

private

Push calling context.

Definition at line 519 of file LockAnalysis.cpp.

 {
     const SVFFunction* svfcaller = call->getFun();
     CallSiteID csId = getTCG()->getCallSiteID(call, callee);
  
 //    /// handle calling context for candidate functions only
 //    if (isLockCandidateFun(caller) == false)
 //        return;
  
     if (tct->inSameCallGraphSCC(getTCG()->getCallGraphNode(svfcaller), getTCG()->getCallGraphNode(callee)) == false)
     {
         tct->pushCxt(cxt,csId);
         DBOUT(DMTA, tct->dumpCxt(cxt));
     }
 }

◆ pushToCTPWorkList()

bool SVF::LockAnalysis::pushToCTPWorkList ( const CxtLockProc & clp )

inlineprivate

WorkList helper functions.

Definition at line 399 of file LockAnalysis.h.

     {
         if (isVisitedCTPs(clp) == false)
         {
             visitedCTPs.insert(clp);
             return clpList.push(clp);
         }
         return false;
     }

◆ pushToCTSWorkList()

bool SVF::LockAnalysis::pushToCTSWorkList ( const CxtStmt & cs )

inlineprivate

Worklist operations.

Definition at line 421 of file LockAnalysis.h.

     {
         return cxtStmtList.push(cs);
     }

◆ removeCxtStmtToSpan()

bool SVF::LockAnalysis::removeCxtStmtToSpan	(	CxtStmt &	cts,
		const CxtLock &	cl
	)

inline

Add context-sensitive statement.

Definition at line 238 of file LockAnalysis.h.

     {
         bool find = cxtStmtToCxtLockSet[cts].find(cl)!=cxtStmtToCxtLockSet[cts].end();
         if(find)
         {
             cxtStmtToCxtLockSet[cts].erase(cl);
             cxtLocktoSpan[cl].erase(cts);
         }
         return find;
     }

◆ touchCxtStmt()

void SVF::LockAnalysis::touchCxtStmt ( CxtStmt & cts )

inline

Touch this context statement.

Definition at line 254 of file LockAnalysis.h.

     {
         cxtStmtToCxtLockSet[cts];
     }

Member Data Documentation

◆ ciLocktoSpan

CILockToSpan SVF::LockAnalysis::ciLocktoSpan

private

Used for context-insensitive intra-procedural locks.

Definition at line 518 of file LockAnalysis.h.

◆ clpList

CxtLockProcVec SVF::LockAnalysis::clpList

private

Following data structures are used for collecting context-sensitive locks.

Definition at line 501 of file LockAnalysis.h.

◆ cxtLockset

CxtLockSet SVF::LockAnalysis::cxtLockset

private

Context-sensitive locks.

Definition at line 490 of file LockAnalysis.h.

◆ cxtLocktoSpan

CxtLockToSpan SVF::LockAnalysis::cxtLocktoSpan

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.

◆ cxtStmtList

CxtStmtWorkList SVF::LockAnalysis::cxtStmtList

private

context-sensitive statement worklist

Definition at line 483 of file LockAnalysis.h.

◆ cxtStmtToCxtLockSet

CxtStmtToCxtLockSet SVF::LockAnalysis::cxtStmtToCxtLockSet

private

Definition at line 496 of file LockAnalysis.h.

◆ instCILocksMap

InstToInstSetMap SVF::LockAnalysis::instCILocksMap

private

Definition at line 519 of file LockAnalysis.h.

◆ instTocondCILocksMap

InstToInstSetMap SVF::LockAnalysis::instTocondCILocksMap

private

Definition at line 520 of file LockAnalysis.h.

◆ instToCxtStmtSet

InstToCxtStmtSet SVF::LockAnalysis::instToCxtStmtSet

private

Map a statement to all its context-sensitive statements.

Definition at line 486 of file LockAnalysis.h.

◆ lockcandidateFuncSet

FunSet SVF::LockAnalysis::lockcandidateFuncSet

private

Candidate functions which relevant to locks/unlocks.

Definition at line 513 of file LockAnalysis.h.

◆ lockQueriesTime

double SVF::LockAnalysis::lockQueriesTime

Definition at line 528 of file LockAnalysis.h.

◆ locksites

InstSet SVF::LockAnalysis::locksites

private

Record all visited clps.

Collecting lock/unlock sites

Definition at line 507 of file LockAnalysis.h.

◆ lockTime

double SVF::LockAnalysis::lockTime

Definition at line 525 of file LockAnalysis.h.

◆ numOfLockedQueries

u32_t SVF::LockAnalysis::numOfLockedQueries

Definition at line 527 of file LockAnalysis.h.

◆ numOfTotalQueries

u32_t SVF::LockAnalysis::numOfTotalQueries

Definition at line 526 of file LockAnalysis.h.

◆ tct

TCT* SVF::LockAnalysis::tct

private

TCT.

Definition at line 480 of file LockAnalysis.h.

◆ unlocksites

InstSet SVF::LockAnalysis::unlocksites

private

Definition at line 508 of file LockAnalysis.h.

◆ visitedCTPs

CxtLockProcSet SVF::LockAnalysis::visitedCTPs

private

CxtLockProc List.

Definition at line 502 of file LockAnalysis.h.

The documentation for this class was generated from the following files:

/home/runner/work/SVF/SVF/svf/include/MTA/LockAnalysis.h
/home/runner/work/SVF/SVF/svf/lib/MTA/LockAnalysis.cpp

Public Types

Public Member Functions

Public Attributes

Private Member Functions

Private Attributes

Detailed Description

Member Typedef Documentation

◆ CILockToSpan

◆ CISpan

◆ CxtLock

◆ CxtLockProc

◆ CxtLockProcSet

◆ CxtLockProcVec

◆ CxtLockSet

◆ CxtLockToLockSet

◆ CxtLockToSpan

◆ CxtStmtSet

◆ CxtStmtToCxtLockSet

◆ CxtStmtToLockFlagMap

◆ CxtStmtWorkList

◆ FunSet

◆ InstSet

◆ InstToCxtStmt

◆ InstToCxtStmtSet

◆ InstToInstSetMap

◆ InstVec

◆ LockSet

◆ LockSiteToLockSet

◆ LockSpan

Member Enumeration Documentation

◆ ValDomain

Constructor & Destructor Documentation

◆ LockAnalysis()

Member Function Documentation

◆ addCondIntraLock()

◆ addCxtLock()

◆ addCxtStmtToSpan()

◆ addIntraLock()

◆ alias()

◆ analyze()

◆ analyzeIntraProcedualLock()

◆ analyzeLockSpanCxtStmt()

◆ buildCandidateFuncSetforLock()

◆ clearFlagMap()

◆ collectCxtLock()

◆ collectLockUnlocksites()

◆ getCSTCLS()

◆ getCxtLockfromCxtStmt() [1/2]

◆ getCxtLockfromCxtStmt() [2/2]

◆ getCxtStmtfromInst()

◆ getIntraLockSet()

◆ getLockVal()

◆ getNumOfCxtLocks()

◆ getSpanfromCxtLock()

◆ getTCG()

◆ getTCT()

◆ handleCall()

◆ handleCallRelation()

◆ handleFork()

◆ handleIntra()

◆ handleRet()

◆ hasAllCxtInLockSpan()

◆ hasCxtLock()

◆ hasCxtLockfromCxtStmt()

◆ hasCxtStmtfromInst()

◆ hasOneCxtInLockSpan()

◆ hasSpanfromCxtLock()

◆ intersect()

◆ intersects()

◆ intraBackwardTraverse()

◆ intraForwardTraverse()

◆ isAliasedLocks() [1/2]

◆ isAliasedLocks() [2/2]

◆ isCallSite()

◆ isExtCall()

◆ isInSameCISpan()

◆ isInSameCSSpan() [1/2]

◆ isInSameCSSpan() [2/2]

◆ isInSameSpan()

◆ isInsideCondIntraLock()