38 using namespace SVFUtil;
44 collectLockUnlocksites();
45 buildCandidateFuncSetforLock();
51 analyzeIntraProcedualLock();
59 analyzeLockSpanCxtStmt();
73 for (
const SVFFunction*
F : tct->getSVFModule()->getFunctionSet())
77 for (
const ICFGNode* icfgNode : bb->getICFGNodeList())
81 unlocksites.insert(icfgNode);
85 locksites.insert(icfgNode);
103 for (InstSet::iterator it = locksites.begin(), eit = locksites.end(); it != eit; ++it)
107 if (visited.find(cgnode) == visited.end())
109 worklist.
push(cgnode);
110 visited.insert(cgnode);
113 for (InstSet::iterator it = unlocksites.begin(), eit = unlocksites.end(); it != eit; ++it)
117 if (visited.find(cgnode) == visited.end())
119 worklist.
push(cgnode);
120 visited.insert(cgnode);
123 while (!worklist.
empty())
130 if (visited.find(srcNode) == visited.end())
132 visited.insert(srcNode);
133 worklist.
push(srcNode);
147 for (InstSet::const_iterator it = locksites.begin(), ie = locksites.end(); it != ie; ++it)
150 assert(
isCallSite(lockSite) &&
"Lock acquire instruction must be a CallSite");
157 bool forward = intraForwardTraverse(lockSite,unlockSet,forwardInsts);
158 bool backward = intraBackwardTraverse(unlockSet,backwardInsts);
161 if(forward && backward)
162 addIntraLock(lockSite,forwardInsts);
163 else if(forward && !backward)
164 addCondIntraLock(lockSite,forwardInsts);
177 worklist.push_back(lockSite);
178 while (!worklist.empty())
180 const ICFGNode *I = worklist.back();
187 if (forwardInsts.find(I)!=forwardInsts.end())
189 forwardInsts.insert(I);
191 if (isTDRelease(I) && isAliasedLocks(lockSite, I))
201 if(outEdge->getDstNode()->getFun() == I->
getFun())
203 worklist.push_back(outEdge->getDstNode());
219 for(InstSet::const_iterator it = unlockSet.begin(), eit = unlockSet.end(); it!=eit; ++it)
223 worklist.push_back(*it);
225 while (!worklist.empty())
227 const ICFGNode *I = worklist.back();
234 if (backwardInsts.find(I)!=backwardInsts.end())
236 backwardInsts.insert(I);
238 if (isTDAcquire(I) && isAliasedLocks(unlockSite, I))
247 if(inEdge->getSrcNode()->getFun() == I->
getFun())
249 worklist.push_back(inEdge->getSrcNode());
261 FunSet entryFuncSet = tct->getEntryProcs();
262 for (FunSet::const_iterator it = entryFuncSet.begin(), eit = entryFuncSet.end(); it != eit; ++it)
264 if (!isLockCandidateFun(*it))
268 pushToCTPWorkList(t);
271 while (!clpList.empty())
287 outs() <<
"\nCollecting CxtLocks: handling direct call:" << **cit <<
"\t" << cgEdge->
getSrcNode()->getFunction()->getName()
288 <<
"-->" << cgEdge->
getDstNode()->getFunction()->getName() <<
"\n");
289 handleCallRelation(clp, cgEdge, *cit);
295 outs() <<
"\nCollecting CxtLocks: handling indirect call:" << **ind <<
"\t"
296 << cgEdge->
getSrcNode()->getFunction()->getName() <<
"-->" << cgEdge->
getDstNode()->getFunction()->getName()
298 handleCallRelation(clp, cgEdge, *ind);
313 if (isTDAcquire(curNode))
315 addCxtLock(cxt,curNode);
319 pushCxt(cxt, SVFUtil::cast<CallICFGNode>(curNode), svfcallee);
322 if (pushToCTPWorkList(newclp))
333 FunSet entryFuncSet = tct->getEntryProcs();
334 for (FunSet::const_iterator it = entryFuncSet.begin(), eit = entryFuncSet.end(); it != eit; ++it)
336 if (!isLockCandidateFun(*it))
339 const ICFGNode* frontInst = (*it)->getEntryBlock()->front();
340 CxtStmt cxtstmt(cxt, frontInst);
341 pushToCTSWorkList(cxtstmt);
344 while (!cxtStmtList.empty())
346 CxtStmt cts = popFromCTSWorkList();
350 instToCxtStmtSet[curInst].insert(cts);
358 if (isTDFork(curInst))
362 else if (isTDAcquire(curInst))
364 assert(hasCxtLock(cts) &&
"context-sensitive lock not found!!");
365 if(addCxtStmtToSpan(cts,cts))
368 else if (isTDRelease(curInst))
370 if(removeCxtStmtToSpan(cts,cts))
396 const CxtLockSet & lockset = getCxtLockfromCxtStmt(cts);
397 outs() <<
"\nlock sets size = " << lockset.size() <<
"\n";
398 for (CxtLockSet::const_iterator it = lockset.begin(), eit = lockset.end(); it != eit; ++it)
411 if(getTCG()->hasThreadForkEdge(call))
413 for (ThreadCallGraph::ForkEdgeSet::const_iterator cgIt = getTCG()->getForkEdgeBegin(call),
414 ecgIt = getTCG()->getForkEdgeEnd(call); cgIt != ecgIt; ++cgIt)
416 const SVFFunction* svfcallee = (*cgIt)->getDstNode()->getFunction();
418 pushCxt(newCxt,call,svfcallee);
420 CxtStmt newCts(newCxt, svfInst);
421 markCxtStmtFlag(newCts, cts);
433 if (getTCG()->hasCallGraphEdge(call))
435 for (PTACallGraph::CallGraphEdgeSet::const_iterator cgIt = getTCG()->getCallEdgeBegin(call), ecgIt = getTCG()->getCallEdgeEnd(call);
436 cgIt != ecgIt; ++cgIt)
438 const SVFFunction* svfcallee = (*cgIt)->getDstNode()->getFunction();
442 pushCxt(newCxt, call, svfcallee);
444 CxtStmt newCts(newCxt, svfInst);
445 markCxtStmtFlag(newCts, cts);
462 if (SVFUtil::isa<ThreadForkEdge, ThreadJoinEdge>(edge))
464 for (PTACallGraphEdge::CallInstSet::const_iterator cit = (edge)->directCallsBegin(), ecit = (edge)->directCallsEnd(); cit != ecit;
469 if (matchCxt(newCxt, SVFUtil::cast<CallICFGNode>(inst), curFunNode->
getFunction()))
473 if(outEdge->getDstNode()->getFun() == curInst->
getFun())
475 CxtStmt newCts(newCxt, outEdge->getDstNode());
476 markCxtStmtFlag(newCts, cts);
481 for (PTACallGraphEdge::CallInstSet::const_iterator cit = (edge)->indirectCallsBegin(), ecit = (edge)->indirectCallsEnd();
486 if (matchCxt(newCxt, SVFUtil::cast<CallICFGNode>(inst), curFunNode->
getFunction()))
490 if(outEdge->getDstNode()->getFun() == curInst->
getFun())
492 CxtStmt newCts(newCxt, outEdge->getDstNode());
493 markCxtStmtFlag(newCts, cts);
510 if(outEdge->getDstNode()->getFun() == curInst->
getFun())
512 CxtStmt newCts(curCxt, outEdge->getDstNode());
513 markCxtStmtFlag(newCts, cts);
522 CallSiteID csId = getTCG()->getCallSiteID(call, callee);
528 if (tct->inSameCallGraphSCC(getTCG()->getCallGraphNode(svfcaller), getTCG()->getCallGraphNode(callee)) ==
false)
530 tct->pushCxt(cxt,csId);
538 CallSiteID csId = getTCG()->getCallSiteID(call, callee);
548 if (tct->inSameCallGraphSCC(getTCG()->getCallGraphNode(svfcaller), getTCG()->getCallGraphNode(callee)) ==
false)
550 if (cxt.back() == csId)
566 bool commonlock =
false;
568 if (isInsideIntraLock(i1) && isInsideIntraLock(i2))
569 commonlock = isProtectedByCommonCILock(i1,i2) ;
571 commonlock = isProtectedByCommonCxtLock(i1,i2);
583 if(!isInsideCondIntraLock(i1) && !isInsideCondIntraLock(i2))
585 const InstSet& lockset1 = getIntraLockSet(i1);
586 const InstSet& lockset2 = getIntraLockSet(i2);
587 for (InstSet::const_iterator cil1 = lockset1.begin(), ecil1 = lockset1.end(); cil1!=ecil1; ++cil1)
589 for (InstSet::const_iterator cil2=lockset2.begin(), ecil2=lockset2.end(); cil2!=ecil2; ++cil2)
591 if (isAliasedLocks(*cil1, *cil2))
604 if(!hasCxtLockfromCxtStmt(cxtStmt1) || !hasCxtLockfromCxtStmt(cxtStmt2))
606 const CxtLockSet& lockset1 = getCxtLockfromCxtStmt(cxtStmt1);
607 const CxtLockSet& lockset2 = getCxtLockfromCxtStmt(cxtStmt2);
608 return alias(lockset1,lockset2);
616 if(!hasCxtStmtfromInst(i1) || !hasCxtStmtfromInst(i2))
618 const CxtStmtSet& ctsset1 = getCxtStmtfromInst(i1);
619 const CxtStmtSet& ctsset2 = getCxtStmtfromInst(i2);
620 for (CxtStmtSet::const_iterator cts1 = ctsset1.begin(), ects1 = ctsset1.end(); cts1 != ects1; cts1++)
622 const CxtStmt& cxtStmt1 = *cts1;
623 for (CxtStmtSet::const_iterator cts2 = ctsset2.begin(), ects2 = ctsset2.end(); cts2 != ects2; cts2++)
625 const CxtStmt& cxtStmt2 = *cts2;
626 if(cxtStmt1==cxtStmt2)
continue;
627 if(isProtectedByCommonCxtLock(cxtStmt1,cxtStmt2)==
false)
642 bool sameSpan =
false;
643 if (isInsideIntraLock(i1) && isInsideIntraLock(i2))
644 sameSpan = isInSameCISpan(i1, i2);
646 sameSpan = isInSameCSSpan(i1, i2);
658 if(!isInsideCondIntraLock(i1) && !isInsideCondIntraLock(i2))
660 const InstSet& lockset1 = getIntraLockSet(i1);
661 const InstSet& lockset2 = getIntraLockSet(i2);
662 for (InstSet::const_iterator cil1 = lockset1.begin(), ecil1 = lockset1.end(); cil1!=ecil1; ++cil1)
664 for (InstSet::const_iterator cil2=lockset2.begin(), ecil2=lockset2.end(); cil2!=ecil2; ++cil2)
679 if(!hasCxtLockfromCxtStmt(cxtStmt1) || !hasCxtLockfromCxtStmt(cxtStmt2))
681 const CxtLockSet& lockset1 = getCxtLockfromCxtStmt(cxtStmt1);
682 const CxtLockSet& lockset2 = getCxtLockfromCxtStmt(cxtStmt2);
683 return intersects(lockset1,lockset2);
690 if(!hasCxtStmtfromInst(I1) || !hasCxtStmtfromInst(I2))
692 const CxtStmtSet& ctsset1 = getCxtStmtfromInst(I1);
693 const CxtStmtSet& ctsset2 = getCxtStmtfromInst(I2);
695 for (CxtStmtSet::const_iterator cts1 = ctsset1.begin(), ects1 = ctsset1.end(); cts1 != ects1; cts1++)
697 const CxtStmt& cxtStmt1 = *cts1;
698 for (CxtStmtSet::const_iterator cts2 = ctsset2.begin(), ects2 = ctsset2.end(); cts2 != ects2; cts2++)
700 const CxtStmt& cxtStmt2 = *cts2;
701 if(cxtStmt1==cxtStmt2)
continue;
702 if(isInSameCSSpan(cxtStmt1,cxtStmt2)==
false)
#define DBOUT(TYPE, X)
LLVM debug macros, define type of your DBUG model of each pass.
void dump() const
Dump CxtProc.
const CallStrCxt & getContext() const
Return current context.
const SVFFunction * getProc() const
Return current procedure.
const CallStrCxt & getContext() const
Return current context.
void dump() const
Dump CxtStmt.
const ICFGNode * getStmt() const
Return current statement.
bool push(const Data &data)
NodeType * getSrcNode() const
NodeType * getDstNode() const
const GEdgeSetTy & getOutEdges() const
iterator OutEdgeBegin()
iterators
const GEdgeSetTy & getInEdges() const
virtual const SVFFunction * getFun() const
Return the function of this ICFGNode.
void analyzeLockSpanCxtStmt()
Set< CxtLock > CxtLockSet
bool isProtectedByCommonCILock(const ICFGNode *i1, const ICFGNode *i2)
bool isInSameCSSpan(const ICFGNode *i1, const ICFGNode *i2) const
bool isProtectedByCommonLock(const ICFGNode *i1, const ICFGNode *i2)
bool isInSameSpan(const ICFGNode *I1, const ICFGNode *I2)
void buildCandidateFuncSetforLock()
Set< CxtStmt > CxtStmtSet
void pushCxt(CallStrCxt &cxt, const CallICFGNode *call, const SVFFunction *callee)
Push calling context.
void handleFork(const CxtStmt &cts)
Handle fork.
bool intraBackwardTraverse(const InstSet &unlockset, InstSet &backwardInsts)
void handleIntra(const CxtStmt &cts)
Handle intra.
bool isProtectedByCommonCxtLock(const ICFGNode *i1, const ICFGNode *i2)
void analyzeIntraProcedualLock()
void handleCall(const CxtStmt &cts)
Handle call.
void collectLockUnlocksites()
Set< const ICFGNode * > InstSet
Set< const SVFFunction * > FunSet
bool intraForwardTraverse(const ICFGNode *lock, InstSet &unlockset, InstSet &forwardInsts)
bool matchCxt(CallStrCxt &cxt, const CallICFGNode *call, const SVFFunction *callee)
Match context.
void printLocks(const CxtStmt &cts)
Print locks and spans.
void handleRet(const CxtStmt &cts)
Handle return.
void handleCallRelation(CxtLockProc &clp, const PTACallGraphEdge *cgEdge, const CallICFGNode *call)
Handle call relations.
bool isInSameCISpan(const ICFGNode *i1, const ICFGNode *i2) const
CallInstSet::const_iterator indirectCallsEnd() const
CallInstSet::const_iterator directCallsBegin() const
Iterators for direct and indirect callsites.
CallInstSet::const_iterator directCallsEnd() const
CallInstSet::const_iterator indirectCallsBegin() const
const SVFFunction * getFunction() const
Get function of this call node.
PTACallGraphEdge::CallGraphEdgeSet::const_iterator const_iterator
PTACallGraphNode * getCallGraphNode(NodeID id) const
Get call graph node.
virtual const std::string getSourceLoc() const
const ICFGNode * front() const
const ICFGNode * back() const
const SVFBasicBlock * getEntryBlock() const
const SVFBasicBlock * getExitBB() const
static double getClk(bool mark=false)
Set< const PTACallGraphNode * > PTACGNodeSet
bool isTDRelease(const CallICFGNode *inst) const
Return true if this call release a lock.
bool isTDAcquire(const CallICFGNode *inst) const
Return true if this call acquire a lock.
ThreadAPI * getThreadAPI() const
Thread API.
bool isExtCall(const SVFFunction *fun)
bool isCallSite(const SVFValue *val)
Whether an instruction is a call or invoke instruction.
bool isRetInstNode(const ICFGNode *node)
std::ostream & outs()
Overwrite llvm::outs()
std::vector< u32_t > CallStrCxt