38 class ForkJoinAnalysis;
58 typedef std::pair<const SVFFunction*,const SVFFunction*>
FuncPair;
111 InstToThreadStmtSetMap::const_iterator it =
instToTSMap.find(inst);
112 assert(it!=
instToTSMap.end() &&
"no thread access the instruction?");
230 const CallICFGNode* fork = SVFUtil::dyn_cast<CallICFGNode>(call);
236 const CallICFGNode* join = SVFUtil::dyn_cast<CallICFGNode>(call);
316 CxtStmtToLoopMap::const_iterator it =
cxtJoinInLoop.find(cs);
322 CxtStmtToLoopMap::const_iterator it =
cxtJoinInLoop.find(cs);
328 bool nonhp =
HBPair.find(std::make_pair(tid1,tid2))!=
HBPair.end();
329 bool hp =
HPPair.find(std::make_pair(tid1,tid2))!=
HPPair.end();
337 return full && !partial;
413 if(flag_tgr ==
Empty)
417 else if(flag_tgr ==
TDDead)
466 const CallICFGNode* fork = SVFUtil::dyn_cast<CallICFGNode>(call);
472 const CallICFGNode* join = SVFUtil::dyn_cast<CallICFGNode>(call);
506 HPPair.insert(std::make_pair(tid1,tid2));
507 HPPair.insert(std::make_pair(tid2,tid1));
511 HBPair.insert(std::make_pair(tid1,tid2));
519 fullJoin.insert(std::make_pair(tid1,tid2));
const ICFGNode * getStmt() const
Return current statement.
NodeID getTid() const
Return current context.
bool push(const Data &data)
void addToFullJoin(NodeID tid1, NodeID tid2)
full join and partial join
void markCxtStmtFlag(const CxtStmt &tgr, const CxtStmt &src)
Transfer function for marking context-sensitive statement.
Map< CxtStmt, LoopBBs > CxtStmtToLoopMap
FIFOWorkList< CxtStmt > CxtStmtWorkList
ValDomain getMarkedFlag(const CxtStmt &cs)
Mark thread flags for cxtStmt.
void addToHPPair(NodeID tid1, NodeID tid2)
SVFLoopAndDomInfo::LoopBBs LoopBBs
void analyzeForkJoinPair()
const SVFVar * getJoinedThread(const CallICFGNode *call)
Get joined thread.
const SVFVar * getForkedThread(const CallICFGNode *call)
Get forked thread.
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.
ThreadPairSet partialJoin
t1 partially joins t2 along some program path(s)
bool matchCxt(CallStrCxt &cxt, const CallICFGNode *call, const SVFFunction *callee)
Match context.
ThreadPairSet fullJoin
t1 fully joins t2 along all program path
LoopBBs & getJoinLoop(const CallICFGNode *inst)
Get loop for join site.
ThreadPairSet HPPair
threads happen-in-parallel
CxtStmt popFromCTSWorkList()
CxtStmtToLoopMap cxtJoinInLoop
a set of context-sensitive join inside loop
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.
bool pushToCTSWorkList(const CxtStmt &cs)
Worklist operations.
Set< NodePair > ThreadPairSet
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.
ValDomain
semilattice Empty==>TDDead==>TDAlive
Map< CxtStmt, NodeBS > CxtStmtToTIDMap
CxtStmtToAliveFlagMap cxtStmtToAliveFlagMap
flags for context-sensitive statements
bool isTDFork(const ICFGNode *call)
Whether it is a fork site.
ThreadPairSet HBPair
thread happens-before pair
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
CxtStmtToTIDMap directJoinMap
maps a context-sensitive join site to directly joined thread ids
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
Map< CxtStmt, ValDomain > CxtStmtToAliveFlagMap
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.
void analyze()
Start analysis here.
CxtThreadStmtWorkList cxtStmtList
CxtThreadStmt worklist.
TCT * getTCT() const
Get Thread Creation Tree.
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
ThreadCallGraph * getThreadCallGraph() const
Get ThreadCallGraph.
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.
bool hasInterleavingThreads(const CxtThreadStmt &cts) const
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.
void addInterleavingThread(const CxtThreadStmt &tgr, const CxtThreadStmt &src)
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.
Set< const SVFFunction * > FunSet
bool isConnectedfromMain(const SVFFunction *fun)
Whether the function is connected from main function in thread call graph.
Map< const ICFGNode *, CxtThreadStmtSet > InstToThreadStmtSetMap
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()
Map< CxtThreadStmt, NodeBS > ThreadStmtToThreadInterleav
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.
Map< FuncPair, bool > FuncPairToBool
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)
FIFOWorkList< CxtThreadStmt > CxtThreadStmtWorkList
bool pushToCTSWorkList(const CxtThreadStmt &cs)
WorkList helper functions.
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)
void getCallees(const CallICFGNode *cs, FunctionSet &callees)
Get all callees for a callsite.
Set< const SVFFunction * > FunctionSet
virtual AliasResult alias(const SVFValue *V1, const SVFValue *V2)=0
Interface exposed to users of our pointer analysis, given Value infos.
const ICFGNode * back() const
const SVFBasicBlock * getExitBB() const
const CxtThread & getCxtThread() const
Get CxtThread.
bool isMultiforked() const
ThreadCallGraph * getThreadCallGraph() const
Get TCG.
void pushCxt(CallStrCxt &cxt, const CallICFGNode *call, const SVFFunction *callee)
Push calling context.
bool hasJoinLoop(const CallICFGNode *join) const
NodeID getParentThread(NodeID tid) const
Get parent thread.
PointerAnalysis * getPTA() const
Get PTA.
LoopBBs & getJoinLoop(const CallICFGNode *join)
Get loop for join site.
TCTNode * getTCTNode(NodeID id) const
Get TCT node.
std::vector< const ICFGNode * > InstVec
bool matchCxt(CallStrCxt &cxt, const CallICFGNode *call, const SVFFunction *callee)
Match context.
const SVFFunction * getStartRoutineOfCxtThread(const CxtThread &ct) const
get the start routine function of a thread
bool isTDFork(const CallICFGNode *inst) const
Return true if this call create a new thread.
bool isTDJoin(const CallICFGNode *inst) const
Return true if this call wait for a worker thread.
const SVFVar * getJoinedThread(const CallICFGNode *inst) const
Return arguments/attributes of pthread_join.
const SVFVar * getForkedThread(const CallICFGNode *inst) const
Return arguments/attributes of pthread_create / hare_parallel_for.
ThreadAPI * getThreadAPI() const
Thread API.
std::unordered_map< Key, Value, Hash, KeyEqual, Allocator > Map
std::vector< u32_t > CallStrCxt
std::unordered_set< Key, Hash, KeyEqual, Allocator > Set