38 using namespace SVFUtil;
44 MHP::MHP(
TCT* t) : tcg(t->getThreadCallGraph()), tct(t), numOfTotalQueries(0), numOfMHPQueries(0),
45 interleavingTime(0), interleavingQueriesTime(0)
77 for (
const std::pair<const NodeID, TCTNode*>& tpair : *
tct)
79 const CxtThread& ct = tpair.second->getCxtThread();
80 NodeID rootTid = tpair.first;
93 DBOUT(
DMTA,
outs() <<
"-----\nMHP analysis root thread: " << rootTid <<
" ");
151 const ICFGNode* entryNode = fun->getEntryBlock()->front();
164 for (
const ICFGNode* curNode : svfbb->getICFGNodeList())
166 if (curNode == entryNode)
185 assert((curInst == curfun->
getEntryBlock()->
front()) &&
"curInst is not the entry of non candidate function.");
190 const SVFFunction* callee = (*nit)->getDstNode()->getFunction();
216 cgIt != ecgIt; ++cgIt)
218 const SVFFunction* svfroutine = (*cgIt)->getDstNode()->getFunction();
220 pushCxt(newCxt, cbn, svfroutine);
243 if (!joinedTids.
empty())
247 std::vector<const SVFBasicBlock*> exitbbs;
249 while (!exitbbs.empty())
263 DBOUT(
DMTA,
outs() <<
"\n\t match join site " << call->
toString() <<
" for thread " << rootTid <<
"\n");
272 std::vector<const SVFBasicBlock*> exitbbs;
274 while (!exitbbs.empty())
300 cgIt != ecgIt; ++cgIt)
303 const SVFFunction* svfcallee = (*cgIt)->getDstNode()->getFunction();
307 const CallICFGNode* callicfgnode = SVFUtil::cast<CallICFGNode>(call);
308 pushCxt(newCxt, callicfgnode, svfcallee);
324 if (SVFUtil::isa<ThreadForkEdge, ThreadJoinEdge>(edge))
326 for (PTACallGraphEdge::CallInstSet::const_iterator cit = (edge)->directCallsBegin(),
327 ecit = (edge)->directCallsEnd();
335 if(outEdge->getDstNode()->getFun() == cts.
getStmt()->
getFun())
343 for (PTACallGraphEdge::CallInstSet::const_iterator cit = (edge)->indirectCallsBegin(),
344 ecit = (edge)->indirectCallsEnd();
352 if(outEdge->getDstNode()->getFun() == cts.
getStmt()->
getFun())
371 if(outEdge->getDstNode()->getFun() == cts.
getStmt()->
getFun())
385 DBOUT(
DMTA,
outs() <<
"##Ancestor thread of " << curTid <<
" is : ");
390 for (
const unsigned i : tds)
396 for(
const ICFGEdge* outEdge : forkInst->getOutEdges())
398 if(outEdge->getDstNode()->getFun() == forkInst->getFun())
422 for (
const unsigned tid : tds)
425 for (
const unsigned stid : siblingTds)
437 DBOUT(
DMTA,
outs() <<
"##Sibling thread of " << curTid <<
" is : ");
448 if (parentTid == curTid)
453 worklist.
push(curNode);
454 while (!worklist.
empty())
459 NodeID srcID = edge->getSrcID();
462 if (srcID == parentTid)
465 worklist.
push(edge->getSrcNode());
483 const CallICFGNode* call = SVFUtil::dyn_cast<CallICFGNode>(joinsite);
484 assert(call &&
isTDJoin(call) &&
"not a join site!");
526 worklist.
push(cgnode);
527 visited.insert(cgnode);
528 while (!worklist.
empty())
536 if (visited.find(srcNode) == visited.end())
538 visited.insert(srcNode);
539 worklist.
push(srcNode);
571 if (ts1.getTid() != ts2.getTid())
573 if (l1.
test(ts2.getTid()) && l2.
test(ts1.getTid()))
651 outs() <<
"( t" << pair.first.getTid()
652 << pair.first.getStmt()->toString() <<
" ) ==> [";
653 for (
unsigned i : pair.second)
655 outs() <<
" " << i <<
" ";
723 for (
const std::pair<const NodeID, TCTNode*>& tpair : *
tct)
725 const CxtThread& ct = tpair.second->getCxtThread();
726 const NodeID rootTid = tpair.first;
733 for(
const ICFGEdge* outEdge : forkInst->getOutEdges())
735 if(outEdge->getDstNode()->getFun() == forkInst->getFun())
737 CxtStmt newCts(forkSiteCxt, outEdge->getDstNode());
746 DBOUT(
DMTA,
outs() <<
"-----\nForkJoinAnalysis root thread: " << tpair.first <<
" ");
772 if (curInst == exitInst)
792 if (
getTCG()->hasThreadForkEdge(cbn))
794 for (ThreadCallGraph::ForkEdgeSet::const_iterator cgIt =
getTCG()->getForkEdgeBegin(cbn),
795 ecgIt =
getTCG()->getForkEdgeEnd(cbn);
796 cgIt != ecgIt; ++cgIt)
798 const SVFFunction* callee = (*cgIt)->getDstNode()->getFunction();
819 if (
getTCG()->hasCallGraphEdge(cbn))
824 if (
isAliasedForkJoin(SVFUtil::cast<CallICFGNode>(forkSite), SVFUtil::cast<CallICFGNode>(joinSite)))
826 if (
hasJoinLoop(SVFUtil::cast<CallICFGNode>(forkSite)))
829 std::vector<const SVFBasicBlock *> exitbbs;
831 while (!exitbbs.empty())
836 CxtStmt newCts(curCxt, svfEntryInst);
851 DBOUT(
DMTA,
outs() <<
"\n\t match join site " << call->
toString() <<
"for thread " << rootTid <<
"\n");
858 if (
hasJoinLoop(SVFUtil::cast<CallICFGNode>(forkSite)))
860 std::vector<const SVFBasicBlock*> exitbbs;
862 while (!exitbbs.empty())
867 CxtStmt newCts(curCxt, svfEntryInst);
882 const CallICFGNode* cbn = SVFUtil::cast<CallICFGNode>(call);
883 if (
getTCG()->hasCallGraphEdge(cbn))
885 for (PTACallGraph::CallGraphEdgeSet::const_iterator cgIt =
getTCG()->getCallEdgeBegin(cbn),
886 ecgIt =
getTCG()->getCallEdgeEnd(cbn);
887 cgIt != ecgIt; ++cgIt)
889 const SVFFunction* svfcallee = (*cgIt)->getDstNode()->getFunction();
893 pushCxt(newCxt, cbn, svfcallee);
895 CxtStmt newCts(newCxt, svfEntryInst);
910 if (SVFUtil::isa<ThreadForkEdge, ThreadJoinEdge>(edge))
912 for (PTACallGraphEdge::CallInstSet::const_iterator cit = edge->directCallsBegin(),
913 ecit = edge->directCallsEnd();
922 if(outEdge->getDstNode()->getFun() == curNode->
getFun())
924 CxtStmt newCts(newCxt, outEdge->getDstNode());
930 for (PTACallGraphEdge::CallInstSet::const_iterator cit = edge->indirectCallsBegin(),
931 ecit = edge->indirectCallsEnd();
941 if(outEdge->getDstNode()->getFun() == curNode->
getFun())
943 CxtStmt newCts(newCxt, outEdge->getDstNode());
961 if(outEdge->getDstNode()->getFun() == curInst->
getFun())
963 CxtStmt newCts(curCxt, outEdge->getDstNode());
982 NodeBS allJoinTids = directJoinTids;
985 for (
unsigned id : directJoinTids)
990 while (!worklist.
empty())
996 NodeID childTid = (*it)->getDstID();
999 allJoinTids.
set(childTid);
1000 worklist.
push(childTid);
#define DBOUT(TYPE, X)
LLVM debug macros, define type of your DBUG model of each pass.
const std::string toString() const override
const CallStrCxt & getContext() const
Return current context.
void dump() const
Dump CxtStmt.
const ICFGNode * getStmt() const
Return current statement.
NodeID getTid() const
Return current context.
void dump() const
Dump CxtThreadStmt.
const ICFGNode * getThread() const
Return forksite.
const CallStrCxt & getContext() const
Return context of the thread.
bool push(const Data &data)
void addToFullJoin(NodeID tid1, NodeID tid2)
full join and partial join
ValDomain getMarkedFlag(const CxtStmt &cs)
Mark thread flags for cxtStmt.
void addToHPPair(NodeID tid1, NodeID tid2)
SVFLoopAndDomInfo::LoopBBs LoopBBs
void analyzeForkJoinPair()
bool hasJoinLoop(const CallICFGNode *inst)
void addSymmetricLoopJoin(const CxtStmt &cs, LoopBBs &lp)
Add inloop join.
void handleRet(const CxtStmt &cts)
Handle return.
NodeBS getDirAndIndJoinedTid(const CxtStmt &cs)
Get directly and indirectly joined threadIDs based on a context-sensitive join site.
bool matchCxt(CallStrCxt &cxt, const CallICFGNode *call, const SVFFunction *callee)
Match context.
LoopBBs & getJoinLoop(const CallICFGNode *inst)
Get loop for join site.
CxtStmt popFromCTSWorkList()
void addToHBPair(NodeID tid1, NodeID tid2)
const ICFGNode * getExitInstOfParentRoutineFun(NodeID tid) const
Get exit instruction of the start routine function of tid's parent thread.
void addToPartial(NodeID tid1, NodeID tid2)
void collectSCEVInfo()
functions
void clearFlagMap()
Clear flags.
void pushCxt(CallStrCxt &cxt, const CallICFGNode *call, const SVFFunction *callee)
Push calling context.
NodeBS & getDirectlyJoinedTid(const CxtStmt &cs)
Get directly joined threadIDs based on a context-sensitive join site.
bool isHBPair(NodeID tid1, NodeID tid2)
Whether thread t1 happens-before thread t2.
void addDirectlyJoinTID(const CxtStmt &cs, NodeID tid)
maps a context-sensitive join site to a thread id
ThreadCallGraph * getTCG() const
ThreadCallGraph.
const LoopBBs & getJoinInSymmetricLoop(const CxtStmt &cs) const
Whether a context-sensitive join satisfies symmetric loop pattern.
bool isTDFork(const ICFGNode *call)
Whether it is a fork site.
bool isFullJoin(NodeID tid1, NodeID tid2)
Whether t1 fully joins t2.
CxtStmtToTIDMap dirAndIndJoinMap
maps a context-sensitive join site to directly and indirectly joined thread ids
void handleCall(const CxtStmt &cts, NodeID rootTid)
Handle call.
bool hasJoinInSymmetricLoop(const CxtStmt &cs) const
bool sameLoopTripCount(const ICFGNode *forkSite, const ICFGNode *joinSite)
Same loop trip count.
bool isTDJoin(const ICFGNode *call)
Whether it is a join site.
void markCxtStmtFlag(const CxtStmt &tgr, ValDomain flag)
Initialize TDAlive and TDDead flags.
CxtStmtWorkList cxtStmtList
context-sensitive statement worklist
bool isAliasedForkJoin(const CallICFGNode *forkSite, const CallICFGNode *joinSite)
Whether it is a matched fork join pair.
void handleIntra(const CxtStmt &cts)
Handle intra.
void handleFork(const CxtStmt &cts, NodeID rootTid)
Handle fork.
const PTACallGraph::FunctionSet & getCallee(const ICFGNode *inst, PTACallGraph::FunctionSet &callees)
void handleJoin(const CxtStmt &cts, NodeID rootTid)
Handle join.
bool isSameSCEV(const ICFGNode *forkSite, const ICFGNode *joinSite)
Return true if the fork and join have the same SCEV.
const GEdgeSetTy & getOutEdges() const
iterator OutEdgeBegin()
iterators
const GEdgeSetTy & getInEdges() const
virtual const SVFFunction * getFun() const
Return the function of this ICFGNode.
virtual const SVFBasicBlock * getBB() const
Return the basic block of this ICFGNode.
virtual const std::string toString() const
void analyze()
Start analysis here.
CxtThreadStmtWorkList cxtStmtList
CxtThreadStmt worklist.
bool isRecurFullJoin(NodeID parentTid, NodeID curTid)
Thread curTid can be fully joined by parentTid recursively.
bool isMultiForkedThread(NodeID curTid)
A thread is a multiForked thread if it is in a loop or recursion.
void rmInterleavingThread(const CxtThreadStmt &tgr, const NodeBS &tids, const ICFGNode *joinsite)
virtual bool mayHappenInParallelCache(const ICFGNode *i1, const ICFGNode *i2)
FuncPairToBool nonCandidateFuncMHPRelMap
void printInterleaving()
Print interleaving results.
void updateSiblingThreads(NodeID tid)
const CxtThreadStmtSet & getThreadStmtSet(const ICFGNode *inst) const
Get/has ThreadStmt.
u32_t numOfTotalQueries
Total number of queries.
Set< CxtThreadStmt > CxtThreadStmtSet
void handleNonCandidateFun(const CxtThreadStmt &cts)
Handle non-candidate function.
SVFLoopAndDomInfo::LoopBBs LoopBBs
void handleJoin(const CxtThreadStmt &cts, NodeID rootTid)
Handle join.
void pushCxt(CallStrCxt &cxt, const CallICFGNode *call, const SVFFunction *callee)
Push calling context.
ThreadCallGraph * tcg
TCG.
void addInterleavingThread(const CxtThreadStmt &tgr, NodeID tid)
Add/Remove interleaving thread for statement inst.
const NodeBS & getInterleavingThreads(const CxtThreadStmt &cts)
Get interleaving thread for statement inst.
InstToThreadStmtSetMap instToTSMap
Map a statement to its thread interleavings.
virtual ~MHP()
Destructor.
bool isHBPair(NodeID tid1, NodeID tid2)
Whether thread t1 happens before t2 based on ForkJoin Analysis.
bool isTDFork(const ICFGNode *call)
Whether it is a fork site.
void handleRet(const CxtThreadStmt &cts)
Handle return.
virtual bool executedByTheSameThread(const ICFGNode *i1, const ICFGNode *i2)
bool matchCxt(CallStrCxt &cxt, const CallICFGNode *call, const SVFFunction *callee)
Match context.
virtual bool mayHappenInParallel(const ICFGNode *i1, const ICFGNode *i2)
Interface to query whether two instructions may happen-in-parallel.
void handleFork(const CxtThreadStmt &cts, NodeID rootTid)
Handle fork.
const LoopBBs & getJoinInSymmetricLoop(const CallStrCxt &cxt, const ICFGNode *call) const
Whether a context-sensitive join satisfies symmetric loop pattern.
bool isConnectedfromMain(const SVFFunction *fun)
Whether the function is connected from main function in thread call graph.
ForkJoinAnalysis * fja
ForJoin Analysis.
bool hasJoinInSymmetricLoop(const CallStrCxt &cxt, const ICFGNode *call) const
Whether a context-sensitive join satisfies symmetric loop pattern.
bool hasThreadStmtSet(const ICFGNode *inst) const
double interleavingQueriesTime
u32_t numOfMHPQueries
Number of queries are answered as may-happen-in-parallel.
void updateNonCandidateFunInterleaving()
bool isMustJoin(const NodeID curTid, const ICFGNode *joinsite)
Whether a join site must join a thread t.
std::pair< const SVFFunction *, const SVFFunction * > FuncPair
CxtThreadStmt popFromCTSWorkList()
void analyzeInterleaving()
Analyze thread interleaving.
NodeBS getDirAndIndJoinedTid(const CallStrCxt &cxt, const ICFGNode *call)
Return thread id(s) which are directly or indirectly joined at this join site.
void updateAncestorThreads(NodeID tid)
Update Ancestor and sibling threads.
virtual bool mayHappenInParallelInst(const ICFGNode *i1, const ICFGNode *i2)
void handleIntra(const CxtThreadStmt &cts)
Handle intra.
void handleCall(const CxtThreadStmt &cts, NodeID rootTid)
Handle call.
ThreadStmtToThreadInterleav threadStmtToTheadInterLeav
bool isTDJoin(const ICFGNode *call)
Whether it is a join site.
const PTACallGraph::FunctionSet & getCallee(const CallICFGNode *inst, PTACallGraph::FunctionSet &callees)
static const Option< bool > PrintInterLev
const SVFFunction * getFunction() const
Get function of this call node.
PTACallGraphEdge::CallGraphEdgeSet::const_iterator const_iterator
CallGraphEdgeSet::const_iterator getCallEdgeEnd(const CallICFGNode *inst) const
CallGraphEdgeSet::const_iterator getCallEdgeBegin(const CallICFGNode *inst) const
Set< const SVFFunction * > FunctionSet
PTACallGraphNode * getCallGraphNode(NodeID id) const
Get call graph node.
bool hasCallGraphEdge(const CallICFGNode *inst) const
Get call graph edge via call instruction.
NodeID getId() const
Get ID.
const ICFGNode * front() const
const ICFGNode * back() const
void getExitBlocksOfLoop(const SVFBasicBlock *bb, BBList &exitbbs) const
const SVFBasicBlock * getEntryBlock() const
const FunctionSetType & getFunctionSet() const
static double getClk(bool mark=false)
const std::string & getName() const
bool test(unsigned Idx) const
const CxtThread & getCxtThread() const
Get CxtThread.
ThreadCallGraph * getThreadCallGraph() const
Get TCG.
bool isJoinSiteInRecursion(const CallICFGNode *join) const
Whether a join site is in recursion.
bool isCallSite(const ICFGNode *inst)
Whether it is a callsite.
ThreadCreateEdgeSet::const_iterator getChildrenBegin(const TCTNode *node) const
Get children and parent nodes.
NodeID getParentThread(NodeID tid) const
Get parent thread.
const NodeBS getSiblingThread(NodeID tid) const
Get sibling threads.
TCTNode * getTCTNode(NodeID id) const
Get TCT node.
bool isCandidateFun(const PTACallGraph::FunctionSet &callees) const
Whether it is a candidate function for indirect call.
SVFModule * getSVFModule() const
Get SVFFModule.
const CallStrCxt & getCxtOfCxtThread(const CxtThread &ct) const
get the context of a thread at its spawning site (fork site)
const SVFFunction * getStartRoutineOfCxtThread(const CxtThread &ct) const
get the start routine function of a thread
const NodeBS getAncestorThread(NodeID tid) const
Get all ancestor threads.
bool isExtCall(const ICFGNode *inst)
Whether it is calling an external function.
ThreadCreateEdgeSet::const_iterator getChildrenEnd(const TCTNode *node) const
Set< const PTACallGraphNode * > PTACGNodeSet
ForkEdgeSet::const_iterator getForkEdgeEnd(const CallICFGNode *cs) const
ForkEdgeSet::const_iterator getForkEdgeBegin(const CallICFGNode *cs) const
bool isExtCall(const SVFFunction *fun)
std::string pasMsg(const std::string &msg)
Print each pass/phase message by converting a string into blue string output.
bool isRetInstNode(const ICFGNode *node)
void dumpSet(NodeBS To, OutStream &O=SVFUtil::outs())
Dump sparse bitvector set.
std::ostream & outs()
Overwrite llvm::outs()
std::vector< u32_t > CallStrCxt