#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 Set< CallStrCxt >	CallStrCxtSet

typedef Map< CallStrCxt, CallStrCxtSet >	ContextSuffixToContexts

typedef Map< const ICFGNode *, ContextSuffixToContexts >	InstToContextSuffixMap

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 >
void	analyzeIntraProceduralLock (ICFGGraph icfg)

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

template<class ICFGGraph >
bool	intraBackwardTraverse (ICFGGraph icfg, 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)

template<class CGGraph >
void	buildCandidateFuncSetForLock (CGGraph cg)

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

const InstSet &	getCondIntraLockSet (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

void	indexCallsiteContext (const ICFGNode *inst, const CallStrCxt &cxt)

const CallStrCxtSet *	getCallsiteContextsWithSuffix (const ICFGNode *inst, const CallStrCxt &suffix) 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.

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.

void	handleReturnAtCallsite (const CxtStmt &exitCxtStmt, const FunObjVar callee, const ICFGNode callsite, const std::vector< const ICFGNode * > &successors)
	Propagate a callee-exit lock state to one matching callsite context.

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.

InstToContextSuffixMap	callsiteContextSuffixIndex
	Incremental exact suffix index for contexts observed at callsites.

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 50 of file LockAnalysis.h.

Member Typedef Documentation

◆ CallStrCxtSet

typedef Set<CallStrCxt> SVF::LockAnalysis::CallStrCxtSet

Definition at line 77 of file LockAnalysis.h.

◆ CILockToSpan

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

Definition at line 69 of file LockAnalysis.h.

◆ CISpan

typedef InstSet SVF::LockAnalysis::CISpan

Definition at line 68 of file LockAnalysis.h.

◆ ContextSuffixToContexts

typedef Map<CallStrCxt, CallStrCxtSet> SVF::LockAnalysis::ContextSuffixToContexts

Definition at line 78 of file LockAnalysis.h.

◆ CxtLock

typedef CxtStmt SVF::LockAnalysis::CxtLock

Definition at line 62 of file LockAnalysis.h.

◆ CxtLockProc

typedef CxtProc SVF::LockAnalysis::CxtLockProc

Definition at line 63 of file LockAnalysis.h.

◆ CxtLockProcSet

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

Definition at line 87 of file LockAnalysis.h.

◆ CxtLockProcVec

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

Definition at line 86 of file LockAnalysis.h.

◆ CxtLockSet

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

Definition at line 76 of file LockAnalysis.h.

◆ CxtLockToLockSet

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

Definition at line 82 of file LockAnalysis.h.

◆ CxtLockToSpan

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

Definition at line 81 of file LockAnalysis.h.

◆ CxtStmtSet

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

Definition at line 75 of file LockAnalysis.h.

◆ CxtStmtToCxtLockSet

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

Definition at line 85 of file LockAnalysis.h.

◆ CxtStmtToLockFlagMap

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

Definition at line 72 of file LockAnalysis.h.

◆ CxtStmtWorkList

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

Definition at line 73 of file LockAnalysis.h.

◆ FunSet

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

Definition at line 70 of file LockAnalysis.h.

◆ InstSet

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

Definition at line 67 of file LockAnalysis.h.

◆ InstToContextSuffixMap

typedef Map<const ICFGNode*, ContextSuffixToContexts> SVF::LockAnalysis::InstToContextSuffixMap

Definition at line 79 of file LockAnalysis.h.

◆ InstToCxtStmtSet

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

Definition at line 84 of file LockAnalysis.h.

◆ InstToInstSetMap

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

Definition at line 71 of file LockAnalysis.h.

◆ InstVec

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

Definition at line 66 of file LockAnalysis.h.

◆ LockSet

typedef NodeBS SVF::LockAnalysis::LockSet

Definition at line 65 of file LockAnalysis.h.

◆ LockSiteToLockSet

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

Definition at line 83 of file LockAnalysis.h.

◆ LockSpan

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

Definition at line 74 of file LockAnalysis.h.

Member Enumeration Documentation

◆ ValDomain

enum SVF::LockAnalysis::ValDomain

semilattice Empty==>TDUnlocked==>TDLocked

Enumerator
Empty
TDLocked
TDUnlocked

Definition at line 55 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 89 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 136 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 185 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 287 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 126 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 213 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. The same implementation runs over full and sliced ICFG/CallGraph traits.

Definition at line 46 of file LockAnalysis.cpp.

{
    collectLockUnlockSites(icfg, cg);
    buildCandidateFuncSetForLock(cg);
 
    DOTIMESTAT(double lockStart = PTAStat::getClk(true));
 
    DBOUT(DGENERAL, outs() << "\tIntra-procedural LockAnalysis\n");
    DBOUT(DMTA, outs() << "\tIntra-procedural LockAnalysis\n");
    analyzeIntraProceduralLock(icfg);
 
    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);
}

◆ analyzeIntraProceduralLock()

template<class ICFGGraph >

void LockAnalysis::analyzeIntraProceduralLock ( ICFGGraph icfg )

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 158 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, lockSite, unlockSet, forwardInsts);
        bool backward = intraBackwardTraverse(
                            icfg, 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 374 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;
        const bool firstContextVisit = instToCxtStmtSet[curInst].insert(cts).second;
        if (firstContextVisit && isCallSite(curInst))
            indexCallsiteContext(curInst, cts.getContext());
        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))
        {
            // Context truncation can merge a path into a lock context that the
            // call-graph pre-collection did not enumerate. The propagation is
            // authoritative: register that reachable lock before constructing
            // its span. Release builds already constructed the same span; this
            // keeps the canonical lock registry consistent as well.
            if (!hasCxtLock(cts))
                addCxtLock(cts.getContext(), curInst);
            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()

template<class CGGraph >

void LockAnalysis::buildCandidateFuncSetForLock ( CGGraph cg )

Collect candidate functions for context-sensitive lock analysis

Definition at line 107 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());
        std::vector<const CallGraphEdge*> inEdges;
        GenericGraphTraits<CGGraph>::getInEdges(cg, node, inEdges);
        for (const CallGraphEdge* edge : inEdges)
        {
            const CallGraphNode* srcNode = edge->getSrcNode();
            if (visited.find(srcNode) == visited.end())
            {
                visited.insert(srcNode);
                worklist.push(srcNode);
            }
        }
    }
}

◆ clearFlagMap()

void SVF::LockAnalysis::clearFlagMap ( )

inlineprotected

Clear flags.

Definition at line 443 of file LockAnalysis.h.

    {
        cxtStmtList.clear();
    }

◆ collectCxtLock()

template<class ICFGGraph , class CGGraph >

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

Definition at line 289 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());
        if (!isLockCandidateFun(cgNode->getFunction()))
            continue;
 
        std::vector<const CallGraphEdge*> outEdges;
        GenericGraphTraits<CGGraph>::getOutEdges(cg, cgNode, outEdges);
        for (const CallGraphEdge* cgEdge : outEdges)
        {
            std::vector<const CallICFGNode*> directCalls;
            GenericGraphTraits<CGGraph>::getDirectCalls(
                cg, cgEdge, directCalls);
            for (const CallICFGNode* callSite : directCalls)
            {
                DBOUT(DMTA,
                      outs() << "\nCollecting CxtLocks: handling direct call:" << *callSite << "\t" << cgEdge->getSrcNode()->getFunction()->getName()
                      << "-->" << cgEdge->getDstNode()->getFunction()->getName() << "\n");
                handleCallRelation(icfg, cg, clp, cgEdge, callSite);
            }
            std::vector<const CallICFGNode*> indirectCalls;
            GenericGraphTraits<CGGraph>::getIndirectCalls(
                cg, cgEdge, indirectCalls);
            for (const CallICFGNode* callSite : indirectCalls)
            {
                DBOUT(DMTA,
                      outs() << "\nCollecting CxtLocks: handling indirect call:" << *callSite << "\t"
                      << cgEdge->getSrcNode()->getFunction()->getName() << "-->" << cgEdge->getDstNode()->getFunction()->getName()
                      << "\n");
                handleCallRelation(icfg, cg, clp, cgEdge, callSite);
            }
        }
    }
}

◆ collectLockUnlockSites()

template<class ICFGGraph , class CGGraph >

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

Collect lock/unlock sites

Definition at line 74 of file LockAnalysis.cpp.

{
    ThreadCallGraph* tcg=tct->getThreadCallGraph();
 
    using CGTraits = GenericGraphTraits<CGGraph>;
    for (auto nodeIt = CGTraits::nodes_begin(cg),
            nodeEnd = CGTraits::nodes_end(cg); nodeIt != nodeEnd; ++nodeIt)
    {
        const FunObjVar* F = CGTraits::getRawNode(*nodeIt)->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);
                }
            }
        }
    }
}

◆ getCallsiteContextsWithSuffix()

const CallStrCxtSet * SVF::LockAnalysis::getCallsiteContextsWithSuffix	(	const ICFGNode *	inst,
		const CallStrCxt &	suffix
	)		const

inline

Definition at line 260 of file LockAnalysis.h.

    {
        InstToContextSuffixMap::const_iterator instIt = callsiteContextSuffixIndex.find(inst);
        if (instIt == callsiteContextSuffixIndex.end())
            return nullptr;
        ContextSuffixToContexts::const_iterator suffixIt = instIt->second.find(suffix);
        return suffixIt == instIt->second.end() ? nullptr : &suffixIt->second;
    }

◆ getCondIntraLockSet()

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

inline

Return the conditional intra-procedural locks whose may-spans contain stmt. Slicing needs these witnesses even though a conditional lock is not strong enough to prove mutual exclusion at the client query.

Definition at line 174 of file LockAnalysis.h.

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

◆ getCxtLockFromCxtStmt() [1/2]

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

inline

Definition at line 280 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 274 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 242 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 164 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 526 of file LockAnalysis.h.

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

◆ getNumOfCxtLocks()

u32_t SVF::LockAnalysis::getNumOfCxtLocks ( )

inline

Definition at line 364 of file LockAnalysis.h.

    {
        return cxtLockSet.size();
    }

◆ getSpanFromCxtLock()

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

inline

Definition at line 313 of file LockAnalysis.h.

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

◆ getTCG()

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

inlineprotected

ThreadCallGraph.

Definition at line 531 of file LockAnalysis.h.

    {
        return tct->getThreadCallGraph();
    }

◆ getTCT()

TCT * SVF::LockAnalysis::getTCT ( )

inline

Get tct.

Definition at line 372 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 490 of file LockAnalysis.cpp.

{
 
    const CallStrCxt& curCxt = cts.getContext();
    const CallICFGNode* call = SVFUtil::dyn_cast<CallICFGNode>(cts.getStmt());
    const CallGraphNode* callerNode = getTCG()->getCallGraphNode(call->getFun());
    std::vector<const CallGraphEdge*> outEdges;
    GenericGraphTraits<CGGraph>::getOutEdges(cg, callerNode, outEdges);
    for (const CallGraphEdge* edge : outEdges)
    {
        if (edge->getEdgeKind() != CallGraphEdge::CallRetEdge ||
                !GenericGraphTraits<CGGraph>::containsCallSite(cg, edge, call))
            continue;
        const FunObjVar* svfcallee = edge->getDstNode()->getFunction();
        if (SVFUtil::isExtCall(svfcallee))
            continue;
        CallStrCxt newCxt = curCxt;
        pushCxt(newCxt, call, svfcallee);
        const ICFGNode* svfInst =
            GenericGraphTraits<ICFGGraph>::getFunEntry(icfg, svfcallee);
        if (svfInst == nullptr)
            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 =
                GenericGraphTraits<ICFGGraph>::getFunExit(icfg, svfcallee);
            if (exitInst == nullptr)
                continue;
            CxtStmt exitCts(newCxt, exitInst);
            if (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 342 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 463 of file LockAnalysis.cpp.

{
    const CallStrCxt& curCxt = cts.getContext();
    const CallICFGNode* call = SVFUtil::dyn_cast<CallICFGNode>(cts.getStmt());
    const CallGraphNode* callerNode = getTCG()->getCallGraphNode(call->getFun());
    std::vector<const CallGraphEdge*> outEdges;
    GenericGraphTraits<CGGraph>::getOutEdges(cg, callerNode, outEdges);
    for (const CallGraphEdge* edge : outEdges)
    {
        if (!SVFUtil::isa<ThreadForkEdge>(edge) ||
                !GenericGraphTraits<CGGraph>::containsCallSite(cg, edge, call))
            continue;
        const FunObjVar* svfcallee = edge->getDstNode()->getFunction();
        CallStrCxt newCxt = curCxt;
        pushCxt(newCxt, call, svfcallee);
        const ICFGNode* svfInst =
            GenericGraphTraits<ICFGGraph>::getFunEntry(icfg, svfcallee);
        if (svfInst == nullptr)
            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 600 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 566 of file LockAnalysis.cpp.

{
 
    const ICFGNode* curInst = cts.getStmt();
    const FunObjVar* svffun = curInst->getFun();
    CallGraphNode* curFunNode = getTCG()->getCallGraphNode(svffun);
 
    std::vector<const ICFGNode*> succ;
    GenericGraphTraits<ICFGGraph>::getSuccNodes(icfg, curInst, succ);
 
    std::vector<const CallGraphEdge*> inEdges;
    GenericGraphTraits<CGGraph>::getInEdges(cg, curFunNode, inEdges);
    for (const CallGraphEdge* edgeConst : inEdges)
    {
        if (SVFUtil::isa<ThreadForkEdge, ThreadJoinEdge>(edgeConst))
            continue;
        std::vector<const CallICFGNode*> directCalls;
        GenericGraphTraits<CGGraph>::getDirectCalls(
            cg, edgeConst, directCalls);
        for (const CallICFGNode* callSite : directCalls)
            handleReturnAtCallsite(
                cts, curFunNode->getFunction(), callSite, succ);
 
        std::vector<const CallICFGNode*> indirectCalls;
        GenericGraphTraits<CGGraph>::getIndirectCalls(
            cg, edgeConst, indirectCalls);
        for (const CallICFGNode* callSite : indirectCalls)
            handleReturnAtCallsite(
                cts, curFunNode->getFunction(), callSite, succ);
    }
}

◆ handleReturnAtCallsite()

void LockAnalysis::handleReturnAtCallsite	(	const CxtStmt &	exitCxtStmt,
		const FunObjVar *	callee,
		const ICFGNode *	callsite,
		const std::vector< const ICFGNode * > &	successors
	)

protected

Propagate a callee-exit lock state to one matching callsite context.

Definition at line 537 of file LockAnalysis.cpp.

{
    CallStrCxt callerCxt = exitCxtStmt.getContext();
    const CallICFGNode* call = SVFUtil::cast<CallICFGNode>(callsite);
    if (!matchCxt(callerCxt, call, callee))
        return;
 
    for (const ICFGNode* successor : successors)
    {
        if (successor->getFun() != callsite->getFun())
            continue;
 
        const CallStrCxtSet* matchingContexts =
            getCallsiteContextsWithSuffix(callsite, callerCxt);
        if (matchingContexts == nullptr)
            continue;
 
        for (const CallStrCxt& callsiteCxt : *matchingContexts)
        {
            CxtStmt returnCxtStmt(callsiteCxt, successor);
            markCxtStmtFlag(returnCxtStmt, exitCxtStmt);
        }
    }
}

◆ hasAllCxtInLockSpan()

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

inline

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

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

◆ hasCxtLockFromCxtStmt()

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

inline

Definition at line 269 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 237 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 159 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 321 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 309 of file LockAnalysis.h.

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

◆ indexCallsiteContext()

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

inline

Index a callsite context by each of its suffixes (including itself and the empty suffix). handleRet can then retrieve exactly the contexts accepted by TCT::isContextSuffix without scanning every callsite state.

Definition at line 251 of file LockAnalysis.h.

    {
        ContextSuffixToContexts& suffixIndex = callsiteContextSuffixIndex[inst];
        for (size_t begin = 0; begin <= cxt.size(); ++begin)
        {
            CallStrCxt suffix(cxt.begin() + begin, cxt.end());
            suffixIndex[suffix].insert(cxt);
        }
    }

◆ intersect()

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

inlineprotected

Definition at line 426 of file LockAnalysis.h.

    {
        bool changed = false;
        for (CxtLockSet::iterator it = tgrlockset.begin(); it != tgrlockset.end(); )
        {
            if (srclockset.find(*it) == srclockset.end())
            {
                it = tgrlockset.erase(it);
                changed = true;
            }
            else
                ++it;
        }
        return changed;
    }

◆ 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 199 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 >

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

Intra-procedural backward traversal

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

bool LockAnalysis::intraForwardTraverse	(	ICFGGraph	icfg,
		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 =
            GenericGraphTraits<ICFGGraph>::getFunExit(icfg, svfFun);
        if (exitInst == nullptr)
            return false;
        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 398 of file LockAnalysis.h.

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

◆ isAliasedLocks() [2/2]

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

protected

Definition at line 366 of file LockAnalysis.cpp.

{
    // Lock matching is conservative: may-alias lock objects are treated as the
    // same lock, consistent with the existing MTA lock semantics.
    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 516 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 647 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 521 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 760 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 781 of file LockAnalysis.cpp.

{
    if(!hasCxtLockFromCxtStmt(cxtStmt1) || !hasCxtLockFromCxtStmt(cxtStmt2))
        return false;
    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 792 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 742 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 151 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 145 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 119 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 229 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 673 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 695 of file LockAnalysis.cpp.

{
    if(!hasCxtLockFromCxtStmt(cxtStmt1) || !hasCxtLockFromCxtStmt(cxtStmt2))
        return false;
    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 707 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 656 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 502 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 495 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 509 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 465 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 407 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 623 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 460 of file LockAnalysis.h.

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

◆ popFromCTSWorkList()

CxtStmt SVF::LockAnalysis::popFromCTSWorkList ( )

inlineprotected

Definition at line 477 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 449 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 618 of file LockAnalysis.cpp.

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

◆ pushToCTPWorkList()

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

inlineprotected

WorkList helper functions.

Definition at line 451 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 473 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 293 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 305 of file LockAnalysis.h.

    {
        cxtStmtToCxtLockSet[cts];
    }

Member Data Documentation

◆ callsiteContextSuffixIndex

InstToContextSuffixMap SVF::LockAnalysis::callsiteContextSuffixIndex

protected

Incremental exact suffix index for contexts observed at callsites.

Definition at line 546 of file LockAnalysis.h.

◆ ciLockToSpan

CILockToSpan SVF::LockAnalysis::ciLockToSpan

protected

Used for context-insensitive intra-procedural locks.

Definition at line 577 of file LockAnalysis.h.

◆ clpList

CxtLockProcVec SVF::LockAnalysis::clpList

protected

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

Definition at line 560 of file LockAnalysis.h.

◆ cxtLockSet

CxtLockSet SVF::LockAnalysis::cxtLockSet

protected

Context-sensitive locks.

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

◆ cxtStmtList

CxtStmtWorkList SVF::LockAnalysis::cxtStmtList

protected

context-sensitive statement worklist

Definition at line 540 of file LockAnalysis.h.

◆ cxtStmtToCxtLockSet

CxtStmtToCxtLockSet SVF::LockAnalysis::cxtStmtToCxtLockSet

protected

Definition at line 555 of file LockAnalysis.h.

◆ instCILocksMap

InstToInstSetMap SVF::LockAnalysis::instCILocksMap

protected

Definition at line 578 of file LockAnalysis.h.

◆ instToCondCILocksMap

InstToInstSetMap SVF::LockAnalysis::instToCondCILocksMap

protected

Definition at line 579 of file LockAnalysis.h.

◆ instToCxtStmtSet

InstToCxtStmtSet SVF::LockAnalysis::instToCxtStmtSet

protected

Map a statement to all its context-sensitive statements.

Definition at line 543 of file LockAnalysis.h.

◆ lockCandidateFuncSet

FunSet SVF::LockAnalysis::lockCandidateFuncSet

protected

Candidate functions which relevant to locks/unlocks.

Definition at line 572 of file LockAnalysis.h.

◆ lockQueriesTime

double SVF::LockAnalysis::lockQueriesTime

Definition at line 586 of file LockAnalysis.h.

◆ lockSites

InstSet SVF::LockAnalysis::lockSites

protected

Record all visited clps.

Collecting lock/unlock sites

Definition at line 566 of file LockAnalysis.h.

◆ lockTime

double SVF::LockAnalysis::lockTime

Definition at line 583 of file LockAnalysis.h.

◆ numOfLockedQueries

u32_t SVF::LockAnalysis::numOfLockedQueries

Definition at line 585 of file LockAnalysis.h.

◆ numOfTotalQueries

u32_t SVF::LockAnalysis::numOfTotalQueries

Definition at line 584 of file LockAnalysis.h.

◆ tct

TCT* SVF::LockAnalysis::tct

protected

TCT.

Definition at line 537 of file LockAnalysis.h.

◆ unlockSites

InstSet SVF::LockAnalysis::unlockSites

protected

Definition at line 567 of file LockAnalysis.h.

◆ visitedCTPs

CxtLockProcSet SVF::LockAnalysis::visitedCTPs

protected

CxtLockProc List.

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

◆ CallStrCxtSet

◆ CILockToSpan

◆ CISpan

◆ ContextSuffixToContexts

◆ CxtLock

◆ CxtLockProc

◆ CxtLockProcSet

◆ CxtLockProcVec

◆ CxtLockSet

◆ CxtLockToLockSet

◆ CxtLockToSpan

◆ CxtStmtSet

◆ CxtStmtToCxtLockSet

◆ CxtStmtToLockFlagMap

◆ CxtStmtWorkList

◆ FunSet

◆ InstSet

◆ InstToContextSuffixMap

◆ InstToCxtStmtSet

◆ InstToInstSetMap

◆ InstVec

◆ LockSet

◆ LockSiteToLockSet

◆ LockSpan

Member Enumeration Documentation

◆ ValDomain

Constructor & Destructor Documentation

◆ LockAnalysis()

◆ ~LockAnalysis()

Member Function Documentation

◆ addCondIntraLock()

◆ addCxtLock()

◆ addCxtStmtToSpan()

◆ addIntraLock()

◆ alias()

◆ analyze()

◆ analyzeIntraProceduralLock()

◆ analyzeLockSpanCxtStmt()

◆ buildCandidateFuncSetForLock()

◆ clearFlagMap()

◆ collectCxtLock()

◆ collectLockUnlockSites()

◆ getCallsiteContextsWithSuffix()

◆ getCondIntraLockSet()

◆ getCxtLockFromCxtStmt() [1/2]

◆ getCxtLockFromCxtStmt() [2/2]

◆ getCxtStmtsFromInst()

◆ getIntraLockSet()

◆ getLockVal()

◆ getNumOfCxtLocks()

◆ getSpanFromCxtLock()

◆ getTCG()

◆ getTCT()

◆ handleCall()

◆ handleCallRelation()

◆ handleFork()

◆ handleIntra()

◆ handleRet()

◆ handleReturnAtCallsite()

◆ hasAllCxtInLockSpan()

◆ hasCxtLock()

◆ hasCxtLockFromCxtStmt()

◆ hasCxtStmtFromInst()

◆ hasIntraLockSet()

◆ hasOneCxtInLockSpan()

◆ hasSpanFromCxtLock()

◆ indexCallsiteContext()

◆ intersect()

◆ intersects()

◆ intraBackwardTraverse()

◆ intraForwardTraverse()

◆ isAliasedLocks() [1/2]

◆ isAliasedLocks() [2/2]