38 using namespace SVFUtil;
47 assert(inst &&
"null value instruction!!");
53 while(!worklist.
empty())
60 for(PTACallGraphEdge::CallInstSet::const_iterator cit = (*nit)->directCallsBegin(),
61 ecit = (*nit)->directCallsEnd(); cit!=ecit; ++cit)
63 if(insts.insert(*cit).second)
66 for(PTACallGraphEdge::CallInstSet::const_iterator cit = (*nit)->indirectCallsBegin(),
67 ecit = (*nit)->indirectCallsEnd(); cit!=ecit; ++cit)
69 if(insts.insert(*cit).second)
77 if(i->getFun()->hasLoopInfo(i->getBB()))
97 while(!worklist.
empty())
100 visits.insert(svffun);
101 if(tcgSCC->isInCycle(tcg->getCallGraphNode(svffun)->getId()))
108 for(PTACallGraphEdge::CallInstSet::const_iterator cit = (*nit)->directCallsBegin(),
109 ecit = (*nit)->directCallsEnd(); cit!=ecit; ++cit)
112 if(visits.find(caller)==visits.end())
113 worklist.
push(caller);
115 for(PTACallGraphEdge::CallInstSet::const_iterator cit = (*nit)->indirectCallsBegin(),
116 ecit = (*nit)->indirectCallsEnd(); cit!=ecit; ++cit)
119 if(visits.find(caller)==visits.end())
120 worklist.
push(caller);
134 for (ThreadCallGraph::CallSiteSet::const_iterator it = tcg->forksitesBegin(), eit = tcg->forksitesEnd(); it != eit; ++it)
136 const SVFFunction* svfun = (*it)->getParent()->getParent();
139 for(ThreadCallGraph::ForkEdgeSet::const_iterator nit = tcg->getForkEdgeBegin(*it), neit = tcg->getForkEdgeEnd(*it); nit!=neit; nit++)
142 candidateFuncSet.insert(forkeeNode->
getFunction());
147 for (ThreadCallGraph::CallSiteSet::const_iterator it = tcg->joinsitesBegin(), eit = tcg->joinsitesEnd(); it != eit; ++it)
149 const SVFFunction* svfun = (*it)->getParent()->getParent();
153 if(candidateFuncSet.empty())
154 writeWrnMsg(
"We didn't recognize any fork site, this is single thread program?");
165 worklist.
push(cgnode);
166 visited.insert(cgnode);
167 while(!worklist.
empty())
174 if(visited.find(srcNode)==visited.end())
176 visited.insert(srcNode);
177 worklist.
push(srcNode);
189 for (
const auto&
item: *svfirCallGraph)
197 entryFuncSet.insert(fun);
200 assert(!entryFuncSet.empty() &&
"Can't find any function in module!");
208 if (this->nodeNum == 0 )
212 worklist.
push(getTCTNode(0));
214 while(!worklist.
empty())
225 for (TCT::ThreadCreateEdgeSet::const_iterator it = node->
getInEdges().begin(), eit = node->
getInEdges().end(); it != eit;
228 if ((*it)->getSrcNode()->isMultiforked())
232 for (TCT::ThreadCreateEdgeSet::const_iterator it = node->
getOutEdges().begin(), eit = node->
getOutEdges().end(); it != eit;
235 worklist.
push((*it)->getDstNode());
251 pushCxt(cxt,callNode,callee);
256 if(pushToCTPWorkList(newctp))
266 TCTNode* spawneeNode = getOrCreateTCTNode(cxt,callNode, oldCxt, callee);
269 if(pushToCTPWorkList(newctp))
272 if(addTCTEdge(this->getGNode(ctp.
getTid()), spawneeNode))
275 this->getGNode(ctp.
getTid())->getCxtThread().dump();
276 outs() <<
" to thread " << spawneeNode->
getId() <<
" ";
292 assert(!lp.empty() &&
"this is not a loop, empty basic block");
296 assert(loopheadbb->
getParent()==joinbb->
getParent() &&
"should inside same function");
302 if(svffun->
dominate(joinbb,svf_scc_bb)==
false)
316 for(ThreadCallGraph::CallSiteSet::const_iterator it = tcg->joinsitesBegin(), eit = tcg->joinsitesEnd(); it!=eit; ++it)
325 if(!lp.empty() && isJoinMustExecutedInLoop(lp,join))
327 joinSiteToLoopMap[join] = lp;
331 if(isInRecursion(join))
332 inRecurJoinSites.insert(join);
341 for(InstToLoopMap::const_iterator it = joinSiteToLoopMap.begin(), eit = joinSiteToLoopMap.end(); it!=eit; ++it)
355 for(InstToLoopMap::const_iterator it = joinSiteToLoopMap.begin(), eit = joinSiteToLoopMap.end(); it!=eit; ++it)
357 std::vector<const SVFBasicBlock*> exitbbs;
358 it->first->getFun()->getExitBlocksOfLoop(it->first->getBB(),exitbbs);
359 while(!exitbbs.empty())
388 collectLoopInfoForJoin();
394 collectEntryFunInCallGraph();
395 for (FunSet::iterator it=entryFuncSet.begin(), eit=entryFuncSet.end(); it!=eit; ++it)
397 if (!isCandidateFun(*it))
400 TCTNode* mainTCTNode = getOrCreateTCTNode(cxt,
nullptr, cxt, *it);
402 pushToCTPWorkList(t);
405 while(!ctpList.empty())
416 for(PTACallGraphEdge::CallInstSet::const_iterator cit = cgEdge->
directCallsBegin(),
419 DBOUT(
DMTA,
outs() <<
"\nTCT handling direct call:" << **cit <<
"\t" << cgEdge->
getSrcNode()->getFunction()->getName() <<
"-->" << cgEdge->
getDstNode()->getFunction()->getName() <<
"\n");
420 handleCallRelation(ctp,cgEdge,*cit);
425 DBOUT(
DMTA,
outs() <<
"\nTCT handling indirect call:" << **ind <<
"\t" << cgEdge->
getSrcNode()->getFunction()->getName() <<
"-->" << cgEdge->
getDstNode()->getFunction()->getName() <<
"\n");
426 handleCallRelation(ctp,cgEdge,*ind);
431 collectMultiForkedThreads();
448 CallSiteID csId = tcg->getCallSiteID(call, callee);
451 if(isCandidateFun(caller) ==
false)
454 if(inSameCallGraphSCC(tcg->getCallGraphNode(caller),tcg->getCallGraphNode(callee))==
false)
469 CallSiteID csId = tcg->getCallSiteID(call, callee);
472 if(isCandidateFun(caller) ==
false)
479 if(inSameCallGraphSCC(tcg->getCallGraphNode(caller),tcg->getCallGraphNode(callee))==
false)
481 if(cxt.back() == csId)
498 std::stringstream rawstr(str);
500 for(CallStrCxt::const_iterator it = cxt.begin(), eit = cxt.end(); it!=eit; ++it)
502 rawstr <<
" ' "<< *it <<
" ' ";
503 rawstr << (tcg->getCallSite(*it))->valueOnlyToString();
504 rawstr <<
" call " << tcg->getCallSite(*it)->getCaller()->getName() <<
"-->" << tcg->getCalleeOfCallSite(*it)->getName() <<
", \n";
507 outs() <<
"max cxt = " << cxt.size() << rawstr.str() <<
"\n";
526 outs() <<
"TID " << it->first <<
"\t";
527 it->second->getCxtThread().dump();
539 if (outEdge && inEdge)
541 assert(outEdge == inEdge &&
"edges not match");
553 for (TCTEdge::ThreadCreateEdgeSet::const_iterator iter = src->
OutEdgeBegin(); iter != src->
OutEdgeEnd(); ++iter)
581 return "Thread Create Tree";
586 return std::to_string(node->
getId());
594 attr.append(
" style=filled fillcolor=red");
598 attr.append(
" style=filled fillcolor=yellow");
603 template<
class EdgeIter>
609 assert(edge &&
"No edge found!!");
611 return "color=black";
#define DBOUT(TYPE, X)
LLVM debug macros, define type of your DBUG model of each pass.
static unsigned char * print(const cJSON *const item, cJSON_bool format, const internal_hooks *const hooks)
const CallStrCxt & getContext() const
Return current context.
const SVFFunction * getProc() const
Return current procedure.
NodeID getTid() const
Return current thread id.
void dump() const
Dump CxtThreadProc.
void dump() const
Dump CxtThread.
bool push(const Data &data)
NodeType * getSrcNode() const
GEdgeKind getEdgeKind() const
NodeType * getDstNode() const
IDToNodeMapTy::const_iterator const_iterator
bool hasIncomingEdge() const
Has incoming/outgoing edge set.
bool hasOutgoingEdge() const
const GEdgeSetTy & getOutEdges() const
GEdgeSetTy::iterator iterator
iterator OutEdgeBegin()
iterators
const GEdgeSetTy & getInEdges() const
static void WriteGraphToFile(SVF::OutStream &O, const std::string &GraphName, const GraphType >, bool simple=false)
virtual const SVFFunction * getFun() const
Return the function of this ICFGNode.
virtual const SVFBasicBlock * getBB() const
Return the basic block of this ICFGNode.
static const Option< bool > TCTDotGraph
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
NodeID getId() const
Get ID.
const std::vector< const SVFBasicBlock * > & getSuccessors() const
const ICFGNode * back() const
const SVFFunction * getParent() const
bool dominate(const SVFBasicBlock *bbKey, const SVFBasicBlock *bbValue) const
bool loopContainsBB(const BBList &lp, const SVFBasicBlock *bb) const
const SVFBasicBlock * getLoopHeader(const BBList &lp) const
bool hasLoopInfo(const SVFBasicBlock *bb) const
const LoopBBs & getLoopInfo(const SVFBasicBlock *bb) const
PTACallGraph * getCallGraph()
static SVFIR * getPAG(bool buildFromFile=false)
Singleton design here to make sure we only have one instance during any analysis.
void setMultiforked(bool value)
const CxtThread & getCxtThread() const
Get CxtThread.
bool isInloop() const
inloop, incycle attributes
bool isInRecursion(const ICFGNode *inst) const
Whether an instruction is in a recursion.
void collectLoopInfoForJoin()
Handle join site in loop.
void collectEntryFunInCallGraph()
Get entry functions that are neither called by other functions nor extern functions.
void pushCxt(CallStrCxt &cxt, const CallICFGNode *call, const SVFFunction *callee)
Push calling context.
const LoopBBs & getLoop(const ICFGNode *inst)
Get loop for an instruction.
void dump(const std::string &filename)
Dump the graph.
TCTEdge * getGraphEdge(TCTNode *src, TCTNode *dst, TCTEdge::CEDGEK kind)
Get call graph edge via nodes.
bool isInLoopInstruction(const ICFGNode *inst)
Multi-forked threads.
bool isJoinMustExecutedInLoop(const LoopBBs &lp, const ICFGNode *join)
Return true if a join instruction must be executed inside a loop.
void markRelProcs()
Mark relevant procedures that are backward reachable from any fork/join site.
void handleCallRelation(CxtThreadProc &ctp, const PTACallGraphEdge *cgEdge, const CallICFGNode *call)
Handle call relations.
bool matchCxt(CallStrCxt &cxt, const CallICFGNode *call, const SVFFunction *callee)
Match context.
void dumpCxt(CallStrCxt &cxt)
Dump calling context.
bool isLoopHeaderOfJoinLoop(const SVFBasicBlock *bb)
Whether a given bb is a loop head of a inloop join site.
void print() const
Print TCT information.
void collectMultiForkedThreads()
TCTEdge * hasGraphEdge(TCTNode *src, TCTNode *dst, TCTEdge::CEDGEK kind) const
Whether we have already created this call graph edge.
bool isLoopExitOfJoinLoop(const SVFBasicBlock *bb)
Whether a given bb is an exit of a inloop join site.
SVFLoopAndDomInfo::LoopBBs LoopBBs
Set< const PTACallGraphNode * > PTACGNodeSet
bool isExtCall(const SVFFunction *fun)
void writeWrnMsg(const std::string &msg)
Writes a message run through wrnMsg.
std::ostream & outs()
Overwrite llvm::outs()
void dump(const SparseBitVector< ElementSize > &LHS, std::ostream &out)
std::vector< u32_t > CallStrCxt
std::unordered_set< Key, Hash, KeyEqual, Allocator > Set
static std::string getEdgeAttributes(TCTNode *node, EdgeIter EI, TCT *csThreadTree)
NodeType::iterator ChildIteratorType
static std::string getGraphName(TCT *graph)
Return name of the graph.
static std::string getNodeAttributes(TCTNode *node, TCT *tct)
static std::string getNodeLabel(TCTNode *node, TCT *graph)
Return function name;.
DOTGraphTraits(bool isSimple=false)