#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 FunObjVar * >	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 *, CxtStmtSet >	InstToCxtStmtSet

typedef Map< CxtStmt, CxtLockSet >	CxtStmtToCxtLockSet

typedef FIFOWorkList< CxtLockProc >	CxtLockProcVec

typedef Set< CxtLockProc >	CxtLockProcSet

Public Member Functions
	LockAnalysis (TCT *t)

	~LockAnalysis ()=default

template<class ICFGGraph , class CGGraph >
void	analyze (ICFGGraph icfg, CGGraph cg)

template<class ICFGGraph , class CGGraph >
void	analyzeIntraProcedualLock (ICFGGraph icfg, CGGraph cg)

template<class ICFGGraph , class CGGraph >
bool	intraForwardTraverse (ICFGGraph icfg, CGGraph cg, const ICFGNode *lock, InstSet &unlockset, InstSet &forwardInsts)

template<class ICFGGraph , class CGGraph >
bool	intraBackwardTraverse (ICFGGraph icfg, CGGraph cg, const InstSet &unlockset, InstSet &backwardInsts)

template<class ICFGGraph , class CGGraph >
void	collectCxtLock (ICFGGraph icfg, CGGraph cg)

template<class ICFGGraph , class CGGraph >
void	analyzeLockSpanCxtStmt (ICFGGraph icfg, CGGraph cg)

template<class ICFGGraph , class CGGraph >
void	collectLockUnlocksites (ICFGGraph icfg, CGGraph cg)

void	buildCandidateFuncSetforLock ()

bool	isIntraLock (const ICFGNode *lock) const
	Intraprocedural locks.

void	addIntraLock (const ICFGNode *lockSite, const InstSet &stmts)
	Add intra-procedural lock.

void	addCondIntraLock (const ICFGNode *lockSite, const InstSet &stmts)
	Add intra-procedural lock.

bool	isInsideIntraLock (const ICFGNode *stmt) const
	Return true if a statement is inside an intra-procedural lock.

bool	isInsideCondIntraLock (const ICFGNode *stmt) const
	Return true if a statement is inside a partial lock/unlock pair (conditional lock with unconditional unlock)

bool	hasIntraLockSet (const ICFGNode *stmt) const

const InstSet &	getIntraLockSet (const ICFGNode *stmt) const

void	addCxtLock (const CallStrCxt &cxt, const ICFGNode *inst)
	Context-sensitive locks.

bool	hasCxtLock (const CxtLock &cxtLock) const
	Get context-sensitive lock.

bool	intersects (const CxtLockSet &lockset1, const CxtLockSet &lockset2) const
	Return true if the intersection of two locksets is not empty.

bool	alias (const CxtLockSet &lockset1, const CxtLockSet &lockset2)
	Return true if two locksets has at least one alias lock.

bool	isLockCandidateFun (const FunObjVar *fun) const
	Return true if it is a candidate function.

bool	hasCxtStmtFromInst (const ICFGNode *inst) const
	Context-sensitive statement and lock spans.

const CxtStmtSet &	getCxtStmtsFromInst (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.

bool	removeCxtStmtToSpan (CxtStmt &cts, const CxtLock &cl)
	Add context-sensitive statement.

CxtStmtToCxtLockSet	getCSTCLS ()

void	touchCxtStmt (CxtStmt &cts)
	Touch this context statement.

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.

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.

TCT *	getTCT ()
	Get tct.

Public Attributes
double	lockTime

u32_t	numOfTotalQueries

u32_t	numOfLockedQueries

double	lockQueriesTime

Protected Member Functions
template<class ICFGGraph , class CGGraph >
void	handleFork (ICFGGraph icfg, CGGraph cg, const CxtStmt &cts)
	Handle fork.

template<class ICFGGraph , class CGGraph >
void	handleCall (ICFGGraph icfg, CGGraph cg, const CxtStmt &cts)
	Handle call.

template<class ICFGGraph , class CGGraph >
void	handleRet (ICFGGraph icfg, CGGraph cg, const CxtStmt &cts)
	Handle return.

template<class ICFGGraph , class CGGraph >
void	handleIntra (ICFGGraph icfg, CGGraph cg, const CxtStmt &cts)
	Handle intra.

template<class ICFGGraph , class CGGraph >
void	handleCallRelation (ICFGGraph icfg, CGGraph cg, CxtLockProc &clp, const CallGraphEdge cgEdge, const CallICFGNode call)
	Handle call relations.

bool	isAliasedLocks (const CxtLock &cl1, const CxtLock &cl2)
	Return true it a lock matches an unlock.

bool	isAliasedLocks (const ICFGNode i1, const ICFGNode i2)

void	markCxtStmtFlag (const CxtStmt &tgr, const CxtStmt &src)
	Mark thread flags for cxtStmt.

bool	intersect (CxtLockSet &tgrlockset, const CxtLockSet &srclockset)

void	clearFlagMap ()
	Clear flags.

bool	pushToCTPWorkList (const CxtLockProc &clp)
	WorkList helper functions.

CxtLockProc	popFromCTPWorkList ()

bool	isVisitedCTPs (const CxtLockProc &clp) const

bool	pushToCTSWorkList (const CxtStmt &cs)
	Worklist operations.

CxtStmt	popFromCTSWorkList ()

void	pushCxt (CallStrCxt &cxt, const CallICFGNode call, const FunObjVar callee)
	Context helper functions.

bool	matchCxt (CallStrCxt &cxt, const CallICFGNode call, const FunObjVar callee)
	Match context.

bool	isContextSuffix (const CallStrCxt &lhs, const CallStrCxt &call)
	If lhs is a suffix of rhs, including equal.

bool	isTDFork (const ICFGNode *call)
	Whether it is a lock site.

bool	isTDAcquire (const ICFGNode *call)
	Whether it is a lock site.

bool	isTDRelease (const ICFGNode *call)
	Whether it is a unlock site.

bool	isCallSite (const ICFGNode *inst)
	Whether it is a callsite.

bool	isExtCall (const ICFGNode *inst)
	Whether it is calling an external function.

const SVFVar *	getLockVal (const ICFGNode *call)
	Get lock value.

ThreadCallGraph *	getTCG () const
	ThreadCallGraph.

Protected Attributes
TCT *	tct
	TCT.

CxtStmtWorkList	cxtStmtList
	context-sensitive statement worklist

InstToCxtStmtSet	instToCxtStmtSet
	Map a statement to all its context-sensitive statements.

CxtLockSet	cxtLockset
	Context-sensitive locks.

CxtLockToSpan	cxtLocktoSpan

CxtStmtToCxtLockSet	cxtStmtToCxtLockSet

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

CxtLockProcSet	visitedCTPs
	CxtLockProc List.

InstSet	locksites
	Record all visited clps.

InstSet	unlocksites

FunSet	lockcandidateFuncSet
	Candidate functions which relevant to locks/unlocks.

CILockToSpan	ciLocktoSpan
	Used for context-insensitive intra-procedural locks.

InstToInstSetMap	instCILocksMap

InstToInstSetMap	instTocondCILocksMap

Detailed Description

Lock analysis

Definition at line 55 of file LockAnalysis.h.

Member Typedef Documentation

◆ CILockToSpan

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

Definition at line 74 of file LockAnalysis.h.

◆ CISpan

typedef InstSet SVF::LockAnalysis::CISpan

Definition at line 73 of file LockAnalysis.h.

◆ CxtLock

typedef CxtStmt SVF::LockAnalysis::CxtLock

Definition at line 67 of file LockAnalysis.h.

◆ CxtLockProc

typedef CxtProc SVF::LockAnalysis::CxtLockProc

Definition at line 68 of file LockAnalysis.h.

◆ CxtLockProcSet

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

Definition at line 89 of file LockAnalysis.h.

◆ CxtLockProcVec

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

Definition at line 88 of file LockAnalysis.h.

◆ CxtLockSet

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

Definition at line 81 of file LockAnalysis.h.

◆ CxtLockToLockSet

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

Definition at line 84 of file LockAnalysis.h.

◆ CxtLockToSpan

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

Definition at line 83 of file LockAnalysis.h.

◆ CxtStmtSet

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

Definition at line 80 of file LockAnalysis.h.

◆ CxtStmtToCxtLockSet

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

Definition at line 87 of file LockAnalysis.h.

◆ CxtStmtToLockFlagMap

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

Definition at line 77 of file LockAnalysis.h.

◆ CxtStmtWorkList

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

Definition at line 78 of file LockAnalysis.h.

◆ FunSet

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

Definition at line 75 of file LockAnalysis.h.

◆ InstSet

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

Definition at line 72 of file LockAnalysis.h.

◆ InstToCxtStmtSet

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

Definition at line 86 of file LockAnalysis.h.

◆ InstToInstSetMap

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

Definition at line 76 of file LockAnalysis.h.

◆ InstVec

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

Definition at line 71 of file LockAnalysis.h.

◆ LockSet

typedef NodeBS SVF::LockAnalysis::LockSet

Definition at line 70 of file LockAnalysis.h.

◆ LockSiteToLockSet

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

Definition at line 85 of file LockAnalysis.h.

◆ LockSpan

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

Definition at line 79 of file LockAnalysis.h.

Member Enumeration Documentation

◆ ValDomain

enum SVF::LockAnalysis::ValDomain

semilattice Empty==>TDUnlocked==>TDLocked

Enumerator
Empty
TDLocked
TDUnlocked

Definition at line 60 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 91 of file LockAnalysis.h.

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

◆ ~LockAnalysis()

SVF::LockAnalysis::~LockAnalysis ( )

default

Member Function Documentation

◆ addCondIntraLock()

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

inline

Add intra-procedural lock.

Definition at line 134 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 173 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 254 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 124 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 201 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()

template<class ICFGGraph , class CGGraph >

template void LockAnalysis::analyze< const SlicedICFGView , const SlicedThreadCallGraphView >	(	ICFGGraph	icfg,
		CGGraph	cg
	)

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. One implementation for the whole program and a slice: GraphT is SVFIR* (whole) or const SlicedSVFIRView* (sliced). Per-graph queries resolve at compile time via the graph* overloads in Graphs/SlicedGraphs.h.

Definition at line 52 of file LockAnalysis.cpp.

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

◆ analyzeIntraProcedualLock()

template<class ICFGGraph , class CGGraph >

void LockAnalysis::analyzeIntraProcedualLock	(	ICFGGraph	icfg,
		CGGraph	cg
	)

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 160 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(icfg, cg,lockSite,unlockSet,forwardInsts);
        bool backward = intraBackwardTraverse(icfg, cg,unlockSet,backwardInsts);
 
        if(forward && backward)
            addIntraLock(lockSite,forwardInsts);
        else if(forward && !backward)
            addCondIntraLock(lockSite,forwardInsts);
    }
}

◆ analyzeLockSpanCxtStmt()

template<class ICFGGraph , class CGGraph >

void LockAnalysis::analyzeLockSpanCxtStmt	(	ICFGGraph	icfg,
		CGGraph	cg
	)

Definition at line 364 of file LockAnalysis.cpp.

{
 
    const TCT::FunSet& entryFuncSet = tct->getEntryProcs();
    for (TCT::FunSet::const_iterator it = entryFuncSet.begin(), eit = entryFuncSet.end(); it != eit; ++it)
    {
        if (!isLockCandidateFun(*it))
            continue;
        CallStrCxt cxt;
        const ICFGNode* frontInst = GenericGraphTraits<ICFGGraph>::getFunEntry(icfg, *it);
        if (!GenericGraphTraits<ICFGGraph>::containsNode(icfg, frontInst))
            continue;
        CxtStmt cxtstmt(cxt, frontInst);
        pushToCTSWorkList(cxtstmt);
    }
 
    while (!cxtStmtList.empty())
    {
        CxtStmt cts = popFromCTSWorkList();
 
        touchCxtStmt(cts);
        const ICFGNode* curInst = cts.getStmt();
        if (!GenericGraphTraits<ICFGGraph>::containsNode(icfg, curInst))
            continue;
        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(icfg, cg, cts);
        }
        else if (isTDAcquire(curInst))
        {
            assert(hasCxtLock(cts) && "context-sensitive lock not found!!");
            if(addCxtStmtToSpan(cts,cts))
                handleIntra(icfg, cg, cts);
        }
        else if (isTDRelease(curInst))
        {
            if(removeCxtStmtToSpan(cts,cts))
                handleIntra(icfg, cg, cts);
        }
        else if (isCallSite(curInst) && !isExtCall(curInst))
        {
            handleCall(icfg, cg, cts);
        }
        else if (SVFUtil::dyn_cast<FunExitICFGNode>(curInst))
        {
            handleRet(icfg, cg, cts);
        }
        else
        {
            handleIntra(icfg, cg, cts);
        }
 
    }
 
}

◆ buildCandidateFuncSetforLock()

void LockAnalysis::buildCandidateFuncSetforLock ( )

Collect candidate functions for context-sensitive lock analysis

Definition at line 111 of file LockAnalysis.cpp.

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

◆ clearFlagMap()

void SVF::LockAnalysis::clearFlagMap ( )

inlineprotected

Clear flags.

Definition at line 406 of file LockAnalysis.h.

    {
        cxtStmtList.clear();
    }

◆ collectCxtLock()

template<class ICFGGraph , class CGGraph >

void LockAnalysis::collectCxtLock	(	ICFGGraph	icfg,
		CGGraph	cg
	)

Definition at line 283 of file LockAnalysis.cpp.

{
    const TCT::FunSet& entryFuncSet = tct->getEntryProcs();
    for (TCT::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();
        CallGraphNode* cgNode = getTCG()->getCallGraphNode(clp.getProc());
        // lzh TODO.
        if (!isLockCandidateFun(cgNode->getFunction()))
            continue;
 
        for (CallGraphNode::const_iterator nit = cgNode->OutEdgeBegin(), neit = cgNode->OutEdgeEnd(); nit != neit; nit++)
        {
            const CallGraphEdge* cgEdge = (*nit);
 
            for (CallGraphEdge::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(icfg, cg, clp, cgEdge, *cit);
            }
            for (CallGraphEdge::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(icfg, cg, clp, cgEdge, *ind);
            }
        }
    }
}

◆ collectLockUnlocksites()

template<class ICFGGraph , class CGGraph >

void LockAnalysis::collectLockUnlocksites	(	ICFGGraph	icfg,
		CGGraph	cg
	)

Collect lock/unlock sites

Definition at line 81 of file LockAnalysis.cpp.

{
    ThreadCallGraph* tcg=tct->getThreadCallGraph();
 
    for (const auto& item : *GenericGraphTraits<CGGraph>::getCallGraph(cg))
    {
        const FunObjVar* F = item.second->getFunction();
        for (auto it : *F)
        {
            const SVFBasicBlock* bb = it.second;
            for (const ICFGNode* icfgNode : bb->getICFGNodeList())
            {
                if (!GenericGraphTraits<ICFGGraph>::containsNode(icfg, icfgNode))
                    continue;
                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 271 of file LockAnalysis.h.

    {
        return cxtStmtToCxtLockSet;
    }

◆ getCxtLockfromCxtStmt() [1/2]

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

inline

Definition at line 247 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 241 of file LockAnalysis.h.

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

◆ getCxtStmtsFromInst()

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

inline

Definition at line 230 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 162 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 )

inlineprotected

Get lock value.

Definition at line 489 of file LockAnalysis.h.

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

◆ getNumOfCxtLocks()

u32_t SVF::LockAnalysis::getNumOfCxtLocks ( )

inline

Definition at line 335 of file LockAnalysis.h.

    {
        return cxtLockset.size();
    }

◆ getSpanfromCxtLock()

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

inline

Definition at line 284 of file LockAnalysis.h.

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

◆ getTCG()

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

inlineprotected

ThreadCallGraph.

Definition at line 494 of file LockAnalysis.h.

    {
        return tct->getThreadCallGraph();
    }

◆ getTCT()

TCT * SVF::LockAnalysis::getTCT ( )

inline

Get tct.

Definition at line 343 of file LockAnalysis.h.

    {
        return tct;
    }

◆ handleCall()

template<class ICFGGraph , class CGGraph >

void LockAnalysis::handleCall	(	ICFGGraph	icfg,
		CGGraph	cg,
		const CxtStmt &	cts
	)

protected

Handle call.

Definition at line 470 of file LockAnalysis.cpp.

{
 
    const CallStrCxt& curCxt = cts.getContext();
    const CallICFGNode* call = SVFUtil::dyn_cast<CallICFGNode>(cts.getStmt());
    if (getTCG()->hasCallGraphEdge(call))
    {
        for (CallGraph::CallGraphEdgeSet::const_iterator cgIt = getTCG()->getCallEdgeBegin(call), ecgIt = getTCG()->getCallEdgeEnd(call);
                cgIt != ecgIt; ++cgIt)
        {
            const FunObjVar* svfcallee = (*cgIt)->getDstNode()->getFunction();
            if (SVFUtil::isExtCall(svfcallee))
                continue;
            CallStrCxt newCxt = curCxt;
            pushCxt(newCxt, call, svfcallee);
            const ICFGNode* svfInst = GenericGraphTraits<ICFGGraph>::getFunEntry(icfg, svfcallee);
            if (!GenericGraphTraits<ICFGGraph>::containsNode(icfg, svfInst))
                continue;
            CxtStmt newCts(newCxt, svfInst);
            markCxtStmtFlag(newCts, cts);
 
            // Return-flow rendezvous (see MHP::handleCall): forward an already
            // computed callee-exit lockset to this callsite's return site.
            if (svfcallee->hasBasicBlock())
            {
                const ICFGNode* exitInst = svfcallee->getExitBB()->back();
                CxtStmt exitCts(newCxt, exitInst);
                if (GenericGraphTraits<ICFGGraph>::containsNode(icfg, exitInst) && hasCxtLockfromCxtStmt(exitCts))
                {
                    const ICFGNode* retNode = call->getRetICFGNode();
                    if (GenericGraphTraits<ICFGGraph>::containsNode(icfg, retNode))
                    {
                        CxtStmt retCts(curCxt, retNode);
                        markCxtStmtFlag(retCts, exitCts);
                    }
                }
            }
        }
    }
}

◆ handleCallRelation()

template<class ICFGGraph , class CGGraph >

void LockAnalysis::handleCallRelation	(	ICFGGraph	icfg,
		CGGraph	cg,
		CxtLockProc &	clp,
		const CallGraphEdge *	cgEdge,
		const CallICFGNode *	cs
	)

protected

Handle call relations.

Handling call relations when collecting context-sensitive locks

Definition at line 333 of file LockAnalysis.cpp.

{
 
    CallStrCxt cxt(clp.getContext());
    const ICFGNode* curNode = cs;
    if (!GenericGraphTraits<ICFGGraph>::containsNode(icfg, curNode))
        return;
    if (isTDAcquire(curNode))
    {
        addCxtLock(cxt,curNode);
        return;
    }
    const FunObjVar* 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()

template<class ICFGGraph , class CGGraph >

void LockAnalysis::handleFork	(	ICFGGraph	icfg,
		CGGraph	cg,
		const CxtStmt &	cts
	)

protected

Handle fork.

Definition at line 446 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 FunObjVar* svfcallee = (*cgIt)->getDstNode()->getFunction();
            CallStrCxt newCxt = curCxt;
            pushCxt(newCxt,call,svfcallee);
            const ICFGNode* svfInst = GenericGraphTraits<ICFGGraph>::getFunEntry(icfg, svfcallee);
            if (!GenericGraphTraits<ICFGGraph>::containsNode(icfg, svfInst))
                continue;
            CxtStmt newCts(newCxt, svfInst);
            markCxtStmtFlag(newCts, cts);
        }
    }
    handleIntra(icfg, cg, cts);
}

◆ handleIntra()

template<class ICFGGraph , class CGGraph >

void LockAnalysis::handleIntra	(	ICFGGraph	icfg,
		CGGraph	cg,
		const CxtStmt &	cts
	)

protected

Handle intra.

Definition at line 594 of file LockAnalysis.cpp.

{
 
    const ICFGNode* curInst = cts.getStmt();
    const CallStrCxt& curCxt = cts.getContext();
 
    std::vector<const ICFGNode*> succ;
    GenericGraphTraits<ICFGGraph>::getSuccNodes(icfg, curInst, succ);
    for (const ICFGNode* dst : succ)
    {
        if(dst->getFun() == curInst->getFun())
        {
            CxtStmt newCts(curCxt, dst);
            markCxtStmtFlag(newCts, cts);
        }
    }
}

◆ handleRet()

template<class ICFGGraph , class CGGraph >

void LockAnalysis::handleRet	(	ICFGGraph	icfg,
		CGGraph	cg,
		const CxtStmt &	cts
	)

protected

Handle return.

Definition at line 513 of file LockAnalysis.cpp.

{
 
    const ICFGNode* curInst = cts.getStmt();
    const CallStrCxt& curCxt = cts.getContext();
    const FunObjVar* svffun = curInst->getFun();
    CallGraphNode* curFunNode = getTCG()->getCallGraphNode(svffun);
 
    std::vector<const CallGraphEdge*> inEdges;
    GenericGraphTraits<CGGraph>::getInEdges(cg, curFunNode, inEdges);
    for (const CallGraphEdge* edgeConst : inEdges)
    {
        if (SVFUtil::isa<ThreadForkEdge, ThreadJoinEdge>(edgeConst))
            continue;
        // Need non-const for directCallsBegin/End
        CallGraphEdge* edge = const_cast<CallGraphEdge*>(edgeConst);
        for (CallGraphEdge::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()))
            {
                std::vector<const ICFGNode*> succ;
                GenericGraphTraits<ICFGGraph>::getSuccNodes(icfg, curInst, succ);
                for (const ICFGNode* dst : succ)
                {
                    if(dst->getFun() == inst->getFun())
                    {
                        // Iterate over callSite's call string context and use as the successor's context
                        if (!hasCxtStmtFromInst(*cit))
                            continue;
                        for (const CxtStmt& cxtStmt: getCxtStmtsFromInst(*cit))
                        {
                            CallStrCxt callSiteCxt = cxtStmt.getContext();
                            // If new context is a suffix of the call site context
                            if (isContextSuffix(newCxt, callSiteCxt))
                            {
                                CxtStmt newCts(callSiteCxt, dst);
                                markCxtStmtFlag(newCts, cts);
                            }
                        }
                    }
                }
            }
        }
        for (CallGraphEdge::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()))
            {
                std::vector<const ICFGNode*> succ;
                GenericGraphTraits<ICFGGraph>::getSuccNodes(icfg, curInst, succ);
                for (const ICFGNode* dst : succ)
                {
                    if(dst->getFun() == inst->getFun())
                    {
                        // Iterate over callSite's call string context and use as the successor's context
                        if (!hasCxtStmtFromInst(*cit))
                            continue;
                        for (const CxtStmt& cxtStmt: getCxtStmtsFromInst(*cit))
                        {
                            CallStrCxt callSiteCxt = cxtStmt.getContext();
                            // If new context is a suffix of the call site context
                            if (isContextSuffix(newCxt, callSiteCxt))
                            {
                                CxtStmt newCts(callSiteCxt, dst);
                                markCxtStmtFlag(newCts, cts);
                            }
                        }
                    }
                }
            }
        }
    }
}

◆ hasAllCxtInLockSpan()

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

inline

Definition at line 307 of file LockAnalysis.h.

    {
        if(!hasCxtStmtFromInst(I))
            return false;
        const LockSpan ctsset = getCxtStmtsFromInst(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 181 of file LockAnalysis.h.

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

◆ hasCxtLockfromCxtStmt()

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

inline

Definition at line 236 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 225 of file LockAnalysis.h.

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

◆ hasIntraLockSet()

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

inline

Whether a statement has an (unconditional) intra-procedural lock set, i.e. getIntraLockSet is valid for it. A statement can be locked (isInsideIntraLock) via a conditional intra lock or a context lock without being here.

Definition at line 157 of file LockAnalysis.h.

    {
        return instCILocksMap.find(stmt)!=instCILocksMap.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 292 of file LockAnalysis.h.

    {
        if(!hasCxtStmtFromInst(I))
            return false;
        const LockSpan ctsset = getCxtStmtsFromInst(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 280 of file LockAnalysis.h.

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

◆ intersect()

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

inlineprotected

Definition at line 390 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 187 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()

template<class ICFGGraph , class CGGraph >

bool LockAnalysis::intraBackwardTraverse	(	ICFGGraph	icfg,
		CGGraph	cg,
		const InstSet &	unlockSet,
		InstSet &	backwardInsts
	)

Intra-procedural backward traversal

Definition at line 236 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;
            }
 
            std::vector<const ICFGNode*> pred;
            GenericGraphTraits<ICFGGraph>::getPredNodes(icfg, I, pred);
            for (const ICFGNode* src : pred)
            {
                if(src->getFun() == I->getFun())
                {
                    worklist.push_back(src);
                }
            }
        }
    }
 
    return true;
}

◆ intraForwardTraverse()

template<class ICFGGraph , class CGGraph >

bool LockAnalysis::intraForwardTraverse	(	ICFGGraph	icfg,
		CGGraph	cg,
		const ICFGNode *	lockSite,
		InstSet &	unlockSet,
		InstSet &	forwardInsts
	)

Intra-procedural forward traversal

Definition at line 189 of file LockAnalysis.cpp.

{
 
    const FunObjVar* 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;
        }
 
        std::vector<const ICFGNode*> succ;
        GenericGraphTraits<ICFGGraph>::getSuccNodes(icfg, I, succ);
        for (const ICFGNode* dst : succ)
        {
            if(dst->getFun() == I->getFun())
            {
                worklist.push_back(dst);
            }
        }
    }
 
    return true;
}

◆ isAliasedLocks() [1/2]

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

inlineprotected

Return true it a lock matches an unlock.

Definition at line 364 of file LockAnalysis.h.

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

◆ isAliasedLocks() [2/2]

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

protected

todo: must alias

Definition at line 357 of file LockAnalysis.cpp.

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

◆ isCallSite()

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

inlineprotected

Whether it is a callsite.

Definition at line 479 of file LockAnalysis.h.

    {
        return tct->isCallSite(inst);
    }

◆ isContextSuffix()

bool LockAnalysis::isContextSuffix	(	const CallStrCxt &	lhs,
		const CallStrCxt &	call
	)

protected

If lhs is a suffix of rhs, including equal.

Definition at line 641 of file LockAnalysis.cpp.

{
    return tct->isContextSuffix(lhs,call);
}

◆ isExtCall()

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

inlineprotected

Whether it is calling an external function.

Definition at line 484 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 754 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 775 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 786 of file LockAnalysis.cpp.

{
    if(!hasCxtStmtFromInst(I1) || !hasCxtStmtFromInst(I2))
        return false;
    const CxtStmtSet& ctsset1 = getCxtStmtsFromInst(I1);
    const CxtStmtSet& ctsset2 = getCxtStmtsFromInst(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 736 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 149 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 143 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 117 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 FunObjVar * fun ) const

inline

Return true if it is a candidate function.

Definition at line 217 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 667 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 689 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 701 of file LockAnalysis.cpp.

{
    if(!hasCxtStmtFromInst(i1) || !hasCxtStmtFromInst(i2))
        return false;
    const CxtStmtSet& ctsset1 = getCxtStmtsFromInst(i1);
    const CxtStmtSet& ctsset2 = getCxtStmtsFromInst(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)
            {
                // i1==i2 under the same context: a self-race between two dynamic
                // instances of one statement (e.g. a thread forked in a loop).
                // This is the ONLY pair the loop produces for such a query, so
                // skipping it would fall through to the vacuous "protected" return
                // below and drop a real race. The two instances are mutually
                // excluded only if this context actually holds a (non-empty) lock.
                if(!hasCxtLockfromCxtStmt(cxtStmt1) || getCxtLockfromCxtStmt(cxtStmt1).empty())
                    return false;
                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 650 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 )

inlineprotected

Whether it is a lock site.

Definition at line 465 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 )

inlineprotected

Whether it is a lock site.

Definition at line 458 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 )

inlineprotected

Whether it is a unlock site.

Definition at line 472 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

inlineprotected

Definition at line 428 of file LockAnalysis.h.

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

◆ markCxtStmtFlag()

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

inlineprotected

Mark thread flags for cxtStmt.

Transfer function for marking context-sensitive statement

Definition at line 373 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 FunObjVar *	callee
	)

protected

Match context.

partial match

Definition at line 617 of file LockAnalysis.cpp.

{
    const FunObjVar* 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 ( )

inlineprotected

Definition at line 423 of file LockAnalysis.h.

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

◆ popFromCTSWorkList()

CxtStmt SVF::LockAnalysis::popFromCTSWorkList ( )

inlineprotected

Definition at line 440 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 432 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 FunObjVar *	callee
	)

protected

Context helper functions.

Push calling context

Definition at line 612 of file LockAnalysis.cpp.

{
    tct->pushCxt(cxt,call,callee);
}

◆ pushToCTPWorkList()

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

inlineprotected

WorkList helper functions.

Definition at line 414 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 )

inlineprotected

Worklist operations.

Definition at line 436 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 260 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 276 of file LockAnalysis.h.

    {
        cxtStmtToCxtLockSet[cts];
    }

Member Data Documentation

◆ ciLocktoSpan

CILockToSpan SVF::LockAnalysis::ciLocktoSpan

protected

Used for context-insensitive intra-procedural locks.

Definition at line 537 of file LockAnalysis.h.

◆ clpList

CxtLockProcVec SVF::LockAnalysis::clpList

protected

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

Definition at line 520 of file LockAnalysis.h.

◆ cxtLockset

CxtLockSet SVF::LockAnalysis::cxtLockset

protected

Context-sensitive locks.

Definition at line 509 of file LockAnalysis.h.

◆ cxtLocktoSpan

CxtLockToSpan SVF::LockAnalysis::cxtLocktoSpan

protected

Map a context-sensitive lock to its lock span statements Map a context-sensitive statement to its context-sensitive lock

Definition at line 514 of file LockAnalysis.h.

◆ cxtStmtList

CxtStmtWorkList SVF::LockAnalysis::cxtStmtList

protected

context-sensitive statement worklist

Definition at line 503 of file LockAnalysis.h.

◆ cxtStmtToCxtLockSet

CxtStmtToCxtLockSet SVF::LockAnalysis::cxtStmtToCxtLockSet

protected

Definition at line 515 of file LockAnalysis.h.

◆ instCILocksMap

InstToInstSetMap SVF::LockAnalysis::instCILocksMap

protected

Definition at line 538 of file LockAnalysis.h.

◆ instTocondCILocksMap

InstToInstSetMap SVF::LockAnalysis::instTocondCILocksMap

protected

Definition at line 539 of file LockAnalysis.h.

◆ instToCxtStmtSet

InstToCxtStmtSet SVF::LockAnalysis::instToCxtStmtSet

protected

Map a statement to all its context-sensitive statements.

Definition at line 506 of file LockAnalysis.h.

◆ lockcandidateFuncSet

FunSet SVF::LockAnalysis::lockcandidateFuncSet

protected

Candidate functions which relevant to locks/unlocks.

Definition at line 532 of file LockAnalysis.h.

◆ lockQueriesTime

double SVF::LockAnalysis::lockQueriesTime

Definition at line 546 of file LockAnalysis.h.

◆ locksites

InstSet SVF::LockAnalysis::locksites

protected

Record all visited clps.

Collecting lock/unlock sites

Definition at line 526 of file LockAnalysis.h.

◆ lockTime

double SVF::LockAnalysis::lockTime

Definition at line 543 of file LockAnalysis.h.

◆ numOfLockedQueries

u32_t SVF::LockAnalysis::numOfLockedQueries

Definition at line 545 of file LockAnalysis.h.

◆ numOfTotalQueries

u32_t SVF::LockAnalysis::numOfTotalQueries

Definition at line 544 of file LockAnalysis.h.

◆ tct

TCT* SVF::LockAnalysis::tct

protected

TCT.

Definition at line 500 of file LockAnalysis.h.

◆ unlocksites

InstSet SVF::LockAnalysis::unlocksites

protected

Definition at line 527 of file LockAnalysis.h.

◆ visitedCTPs

CxtLockProcSet SVF::LockAnalysis::visitedCTPs

protected

CxtLockProc List.

Definition at line 521 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

Protected Member Functions

Protected Attributes

Detailed Description

Member Typedef Documentation

◆ CILockToSpan

◆ CISpan

◆ CxtLock

◆ CxtLockProc

◆ CxtLockProcSet

◆ CxtLockProcVec

◆ CxtLockSet

◆ CxtLockToLockSet

◆ CxtLockToSpan

◆ CxtStmtSet

◆ CxtStmtToCxtLockSet

◆ CxtStmtToLockFlagMap

◆ CxtStmtWorkList

◆ FunSet

◆ InstSet

◆ InstToCxtStmtSet

◆ InstToInstSetMap

◆ InstVec

◆ LockSet

◆ LockSiteToLockSet

◆ LockSpan

Member Enumeration Documentation

◆ ValDomain

Constructor & Destructor Documentation

◆ LockAnalysis()

◆ ~LockAnalysis()

Member Function Documentation

◆ addCondIntraLock()

◆ addCxtLock()

◆ addCxtStmtToSpan()

◆ addIntraLock()

◆ alias()

◆ analyze()

◆ analyzeIntraProcedualLock()

◆ analyzeLockSpanCxtStmt()

◆ buildCandidateFuncSetforLock()

◆ clearFlagMap()

◆ collectCxtLock()

◆ collectLockUnlocksites()

◆ getCSTCLS()

◆ getCxtLockfromCxtStmt() [1/2]

◆ getCxtLockfromCxtStmt() [2/2]

◆ getCxtStmtsFromInst()

◆ getIntraLockSet()

◆ getLockVal()

◆ getNumOfCxtLocks()

◆ getSpanfromCxtLock()

◆ getTCG()

◆ getTCT()

◆ handleCall()

◆ handleCallRelation()

◆ handleFork()

◆ handleIntra()

◆ handleRet()

◆ hasAllCxtInLockSpan()

◆ hasCxtLock()

◆ hasCxtLockfromCxtStmt()

◆ hasCxtStmtFromInst()

◆ hasIntraLockSet()

◆ hasOneCxtInLockSpan()

◆ hasSpanfromCxtLock()

◆ intersect()

◆ intersects()

◆ intraBackwardTraverse()

◆ intraForwardTraverse()

◆ isAliasedLocks() [1/2]

◆ isAliasedLocks() [2/2]

◆ isCallSite()

◆ isContextSuffix()

◆ isExtCall()

◆ isInSameCISpan()

◆ isInSameCSSpan() [1/2]

◆ isInSameCSSpan() [2/2]