Static Value-Flow Analysis
Loading...
Searching...
No Matches
SVF::TCT Class Reference

#include <TCT.h>

Inheritance diagram for SVF::TCT:
SVF::GenericGraph< TCTNode, TCTEdge > SVF::SlicedTCT

Classes

struct  FunObjVarIdCmp

Public Types

typedef SVFLoopAndDomInfo::LoopBBs LoopBBs
typedef TCTEdge::ThreadCreateEdgeSet ThreadCreateEdgeSet
typedef ThreadCreateEdgeSet::iterator TCTNodeIter
typedef OrderedSet< const FunObjVar *, FunObjVarIdCmp > FunSet
typedef std::vector< const ICFGNode * > InstVec
typedef Set< const ICFGNode * > InstSet
typedef Set< const CallGraphNode * > PTACGNodeSet
typedef Map< CxtThread, TCTNode * > CxtThreadToNodeMap
typedef Set< std::pair< NodeID, CallStrCxt > > CallStrCxtSet
typedef Map< CxtThread, CallStrCxtSet > CxtThreadToForkCxtSet
typedef Map< CxtThread, const FunObjVar * > CxtThreadToFun
typedef Map< const ICFGNode *, LoopBBs > InstToLoopMap
typedef FIFOWorkList< CxtThreadProc > CxtThreadProcVec
typedef Set< CxtThreadProc > CxtThreadProcSet
typedef SCCDetection< CallGraph * > ThreadCallGraphSCC
typedef Set< const ICFGNode * > DummyForkSiteSet
Public Types inherited from SVF::GenericGraph< TCTNode, TCTEdge >
typedef TCTNode NodeType
typedef TCTEdge EdgeType
typedef OrderedMap< NodeID, NodeType * > IDToNodeMapTy
 NodeID to GenericNode map.
typedef IDToNodeMapTy::iterator iterator
 Node Iterators.
typedef IDToNodeMapTy::const_iterator const_iterator

Public Member Functions

virtual ~TCT ()
 Destructor.
ThreadCallGraph * getThreadCallGraph () const
 Get TCG.
PointerAnalysis * getPTA () const
 Get PTA.
TCTNode * getTCTNode (NodeID id) const
 Get TCT node.
TCTEdge * hasGraphEdge (TCTNode *src, TCTNode *dst, TCTEdge::CEDGEK kind) const
 Whether we have already created this call graph edge.
TCTEdge * getGraphEdge (TCTNode *src, TCTNode *dst, TCTEdge::CEDGEK kind)
 Get call graph edge via nodes.
ThreadCreateEdgeSet::const_iterator getChildrenBegin (const TCTNode *node) const
 Get children and parent nodes.
ThreadCreateEdgeSet::const_iterator getChildrenEnd (const TCTNode *node) const
ThreadCreateEdgeSet::const_iterator getParentsBegin (const TCTNode *node) const
ThreadCreateEdgeSet::const_iterator getParentsEnd (const TCTNode *node) const
const FunSet & getMakredProcs () const
 Get marked candidate functions.
const FunSet & getEntryProcs () const
 Get marked candidate functions.
u32_t getTCTNodeNum () const
 Get Statistics.
u32_t getTCTEdgeNum () const
u32_t getMaxCxtSize () const
bool isExtCall (const ICFGNode *inst)
 Whether it is calling an external function.
bool isCallSite (const ICFGNode *inst)
 Whether it is a callsite.
bool hasTCTNode (const CxtThread &ct) const
 Find/Get TCT node.
TCTNode * getTCTNode (const CxtThread &ct) const
bool isCandidateFun (const CallGraph::FunctionSet &callees) const
 Whether it is a candidate function for indirect call.
bool isCandidateFun (const FunObjVar *fun) const
bool inSameCallGraphSCC (const CallGraphNode *src, const CallGraphNode *dst)
 Whether two functions in the same callgraph scc.
bool hasParentThread (NodeID tid) const
 Get parent and sibling threads.
NodeBS getParentThreads (NodeID tid) const
 Get parent threads.
const NodeBS getAncestorThreads (NodeID tid) const
 Get all ancestor threads.
const NodeBS getSiblingThread (NodeID tid) const
 Get sibling threads.
const CallStrCxtSet & getCxtOfCxtThread (const CxtThread &ct) const
 get the contexts of a thread at its spawning sites (fork sites)
const FunObjVar * getStartRoutineOfCxtThread (const CxtThread &ct) const
 get the start routine function of a thread
LoopBBs & getJoinLoop (const CallICFGNode *join)
 Get loop for join site.
bool hasJoinLoop (const CallICFGNode *join) const
bool hasLoop (const SVFBasicBlock *bb) const
bool hasLoop (const ICFGNode *inst) const
bool isJoinMustExecutedInLoop (const LoopBBs &lp, const ICFGNode *join)
 Return true if a join instruction must be executed inside a loop.
const LoopBBs & getLoop (const ICFGNode *inst)
 Get loop for an instruction.
const LoopBBs & getLoop (const SVFBasicBlock *bb)
 Get loop for fork/join site.
virtual void pushCxt (CallStrCxt &cxt, const CallICFGNode *call, const FunObjVar *callee)
 Context helper functions.
bool matchAndPopCxt (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 isJoinSiteInRecursion (const CallICFGNode *join) const
 Whether a join site is in recursion.
void dumpCxt (CallStrCxt &cxt)
 Dump calling context.
void dump (const std::string &filename)
 Dump the graph.
void print () const
 Print TCT information.
Public Member Functions inherited from SVF::GenericGraph< TCTNode, TCTEdge >
 GenericGraph ()
 Constructor.
virtual ~GenericGraph ()
 Destructor.
void destroy ()
 Release memory.
iterator begin ()
 Iterators.
iterator end ()
const_iterator begin () const
const_iterator end () const
void addGNode (NodeID id, NodeType *node)
 Add a Node.
NodeType * getGNode (NodeID id) const
 Get a node.
bool hasGNode (NodeID id) const
 Has a node.
void removeGNode (NodeType *node)
 Delete a node.
u32_t getTotalNodeNum () const
 Get total number of node/edge.
u32_t getTotalEdgeNum () const
void incNodeNum ()
 Increase number of node/edge.
void incEdgeNum ()

Static Public Member Functions

static std::unique_ptr< TCT > create (PointerAnalysis *p)
 Construct and build a TCT with the command-line context bound.
static std::unique_ptr< TCT > create (PointerAnalysis *p, u32_t contextLimit)

Protected Member Functions

 TCT (PointerAnalysis *p, u32_t contextLimit)
TCTNode * addTCTNode (const CxtThread &ct)
 Add TCT node.
bool addTCTEdge (TCTNode *src, TCTNode *dst)
 Add TCT edge.
virtual void build ()
 Build TCT.
virtual void markRelProcs ()
 Mark relevant procedures that are backward reachable from any fork/join site.
virtual void markRelProcs (const FunObjVar *fun)
virtual void collectEntryFunInCallGraph ()
 Get entry functions that are neither called by other functions nor extern functions.
void collectMultiForkedThreads ()
virtual void collectLoopInfoForJoin ()
 Handle join site in loop.
bool isLoopHeaderOfJoinLoop (const SVFBasicBlock *bb)
 Whether a given bb is a loop head of a inloop join site.
bool isLoopExitOfJoinLoop (const SVFBasicBlock *bb)
 Whether a given bb is an exit of a inloop join site.
bool isInLoopInstruction (const ICFGNode *inst)
 Multi-forked threads.
bool isInRecursion (const ICFGNode *inst) const
 Whether an instruction is in a recursion.
virtual void handleCallRelation (CxtThreadProc &ctp, const CallGraphEdge *cgEdge, const CallICFGNode *call)
 Handle call relations.
TCTNode * getOrCreateTCTNode (const CallStrCxt &cxt, const ICFGNode *fork, const CxtThreadProc &forkSiteCtp, const FunObjVar *routine)
 Get or create a tct node based on CxtThread.
void setMultiForkedAttrs (CxtThread &ct)
 Set multi-forked thread attributes.
bool addCxtOfCxtThread (NodeID pTid, const CallStrCxt &cxt, const CxtThread &ct)
void addStartRoutineOfCxtThread (const FunObjVar *fun, const CxtThread &ct)
 Add start routine function of a cxt thread.
ICFGNode * createDummyForkSite ()
 Create and get a new dummy fork site for starter routines.
bool pushToCTPWorkList (const CxtThreadProc &ctp)
 WorkList helper functions.
CxtThreadProc popFromCTPWorkList ()
bool isVisitedCTPs (const CxtThreadProc &ctp) const

Protected Attributes

ThreadCallGraph * tcg
PointerAnalysis * pta
const u32_t contextLimit
u32_t TCTNodeNum
u32_t TCTEdgeNum
u32_t MaxCxtSize
FunSet entryFuncSet
FunSet candidateFuncSet
 Procedures that are neither called by other functions nor extern functions.
ThreadCallGraphSCC * tcgSCC
 Procedures we care about during call graph traversing when creating TCT.
CxtThreadProcVec ctpList
 Thread call graph SCC.
CxtThreadProcSet visitedCTPs
 CxtThreadProc List.
CxtThreadToNodeMap ctpToNodeMap
 Record all visited ctps.
CxtThreadToForkCxtSet ctToForkCxtsMap
 Map a ctp to its graph node.
CxtThreadToFun ctToRoutineFunMap
 Map a CxtThread to the context at its spawning site (fork site).
InstToLoopMap joinSiteToLoopMap
 Map a CxtThread to its start routine function.
Set< const ICFGNode * > inRecurJoinSites
 Fork or Join sites in recursions.
DummyForkSiteSet dummyForkSites
 set of dummy fork sites for starter routines
NodeID dummyForkICFGNodeID = UINT32_MAX
 unique ID generator for dummy
Protected Attributes inherited from SVF::GenericGraph< TCTNode, TCTEdge >
IDToNodeMapTy IDToNodeMap
 node map

Additional Inherited Members

Public Attributes inherited from SVF::GenericGraph< TCTNode, TCTEdge >
u32_t edgeNum
 total num of node
u32_t nodeNum
 total num of edge

Detailed Description

Definition at line 155 of file TCT.h.

Member Typedef Documentation

◆ CallStrCxtSet

Definition at line 178 of file TCT.h.

◆ CxtThreadProcSet

Definition at line 183 of file TCT.h.

◆ CxtThreadProcVec

Definition at line 182 of file TCT.h.

◆ CxtThreadToForkCxtSet

Definition at line 179 of file TCT.h.

◆ CxtThreadToFun

Definition at line 180 of file TCT.h.

◆ CxtThreadToNodeMap

Definition at line 177 of file TCT.h.

◆ DummyForkSiteSet

Definition at line 185 of file TCT.h.

◆ FunSet

Definition at line 173 of file TCT.h.

◆ InstSet

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

Definition at line 175 of file TCT.h.

◆ InstToLoopMap

Definition at line 181 of file TCT.h.

◆ InstVec

typedef std::vector<const ICFGNode*> SVF::TCT::InstVec

Definition at line 174 of file TCT.h.

◆ LoopBBs

Definition at line 159 of file TCT.h.

◆ PTACGNodeSet

Definition at line 176 of file TCT.h.

◆ TCTNodeIter

typedef ThreadCreateEdgeSet::iterator SVF::TCT::TCTNodeIter

Definition at line 161 of file TCT.h.

◆ ThreadCallGraphSCC

Definition at line 184 of file TCT.h.

◆ ThreadCreateEdgeSet

Constructor & Destructor Documentation

◆ ~TCT()

TCT::~TCT ( )
virtual

Destructor.

Definition at line 65 of file TCT.cpp.

66{
67 for (const ICFGNode* dummyForkSite: dummyForkSites)
68 {
69 delete dummyForkSite;
70 }
71}
DummyForkSiteSet dummyForkSites
set of dummy fork sites for starter routines
Definition TCT.h:625

◆ TCT()

TCT::TCT ( PointerAnalysis * p,
u32_t contextLimit )
protected

Initialize common TCT state. Factory functions invoke build() only after the complete concrete object has been constructed.

Definition at line 53 of file TCT.cpp.

54 : tcg(nullptr), pta(p), contextLimit(contextLimit), TCTNodeNum(0),
55 TCTEdgeNum(0), MaxCxtSize(0), tcgSCC(nullptr)
56{
58 assert(tcg != nullptr && "TCT::TCT: call graph is not a ThreadCallGraph!");
59 tcg->updateCallGraph(pta);
60 //tcg->updateJoinEdge(pta);
61 tcgSCC = pta->getCallGraphSCC();
62 tcgSCC->find();
63}
cJSON * p
Definition cJSON.cpp:2559
ThreadCallGraphSCC * tcgSCC
Procedures we care about during call graph traversing when creating TCT.
Definition TCT.h:617
u32_t TCTNodeNum
Definition TCT.h:460
const u32_t contextLimit
Definition TCT.h:459
u32_t TCTEdgeNum
Definition TCT.h:461
PointerAnalysis * pta
Definition TCT.h:458
u32_t MaxCxtSize
Definition TCT.h:462
ThreadCallGraph * tcg
Definition TCT.h:457
LLVM_NODISCARD std::enable_if_t<!is_simple_type< Y >::value, typename cast_retty< X, const Y >::ret_type > dyn_cast(const Y &Val)
Definition Casting.h:405

Member Function Documentation

◆ addCxtOfCxtThread()

bool SVF::TCT::addCxtOfCxtThread ( NodeID pTid,
const CallStrCxt & cxt,
const CxtThread & ct )
inlineprotected

Add context for a thread at its spawning site (fork site). Returns true if this (parent tid, context) pair was not recorded before.

Definition at line 574 of file TCT.h.

575 {
576 return ctToForkCxtsMap[ct].insert(std::make_pair(pTid, cxt)).second;
577 }
CxtThreadToForkCxtSet ctToForkCxtsMap
Map a ctp to its graph node.
Definition TCT.h:621

◆ addStartRoutineOfCxtThread()

void SVF::TCT::addStartRoutineOfCxtThread ( const FunObjVar * fun,
const CxtThread & ct )
inlineprotected

Add start routine function of a cxt thread.

Definition at line 580 of file TCT.h.

581 {
582 ctToRoutineFunMap[ct] = fun;
583 }
CxtThreadToFun ctToRoutineFunMap
Map a CxtThread to the context at its spawning site (fork site).
Definition TCT.h:622

◆ addTCTEdge()

bool SVF::TCT::addTCTEdge ( TCTNode * src,
TCTNode * dst )
inlineprotected

Add TCT edge.

Definition at line 476 of file TCT.h.

477 {
479 {
480 TCTEdge* edge = new TCTEdge(src, dst, TCTEdge::ThreadCreateEdge);
481 dst->addIncomingEdge(edge);
482 src->addOutgoingEdge(edge);
483 TCTEdgeNum++;
484 return true;
485 }
486 return false;
487 }
@ ThreadCreateEdge
Definition TCT.h:57
TCTEdge * hasGraphEdge(TCTNode *src, TCTNode *dst, TCTEdge::CEDGEK kind) const
Whether we have already created this call graph edge.
Definition TCT.cpp:588

◆ addTCTNode()

TCTNode * SVF::TCT::addTCTNode ( const CxtThread & ct)
inlineprotected

Add TCT node.

Definition at line 465 of file TCT.h.

466 {
467 assert(ctpToNodeMap.find(ct)==ctpToNodeMap.end() && "Already has this node!!");
468 NodeID id = TCTNodeNum;
469 TCTNode* node = new TCTNode(id, ct);
470 addGNode(id, node);
471 TCTNodeNum++;
472 ctpToNodeMap[ct] = node;
473 return node;
474 }
void addGNode(NodeID id, NodeType *node)
CxtThreadToNodeMap ctpToNodeMap
Record all visited ctps.
Definition TCT.h:620
u32_t NodeID
Definition GeneralType.h:76

◆ build()

void TCT::build ( )
protectedvirtual

Build TCT.

Start building TCT

Reimplemented in SVF::SlicedTCT.

Definition at line 418 of file TCT.cpp.

419{
420
421 markRelProcs();
422
424
425 // the fork site of main function is initialized with nullptr.
426 // the context of main is initialized with empty
427 // start routine is empty
428
430
431 for (FunSet::iterator it=entryFuncSet.begin(), eit=entryFuncSet.end(); it!=eit; ++it)
432 {
433 if (!isCandidateFun(*it))
434 continue;
435 CallStrCxt cxt;
436 CxtThreadProc dummyCtp(-1, cxt, nullptr);
437 const ICFGNode* dummyForkSite = createDummyForkSite();
438 TCTNode* mainTCTNode = getOrCreateTCTNode(cxt, dummyForkSite, dummyCtp, *it);
439 CxtThreadProc t(mainTCTNode->getId(), cxt, *it);
441 }
442
443 while(!ctpList.empty())
444 {
445 CxtThreadProc ctp = popFromCTPWorkList();
446 CallGraphNode* cgNode = tcg->getCallGraphNode(ctp.getProc());
447 if(isCandidateFun(cgNode->getFunction()) == false)
448 continue;
449
450 for(CallGraphNode::const_iterator nit = cgNode->OutEdgeBegin(), neit = cgNode->OutEdgeEnd(); nit!=neit; nit++)
451 {
452 const CallGraphEdge* cgEdge = (*nit);
453
454 for(CallGraphEdge::CallInstSet::const_iterator cit = cgEdge->directCallsBegin(),
455 ecit = cgEdge->directCallsEnd(); cit!=ecit; ++cit)
456 {
457 DBOUT(DMTA,outs() << "\nTCT handling direct call:" << **cit << "\t" << cgEdge->getSrcNode()->getFunction()->getName() << "-->" << cgEdge->getDstNode()->getFunction()->getName() << "\n");
458 handleCallRelation(ctp,cgEdge,*cit);
459 }
460 for(CallGraphEdge::CallInstSet::const_iterator ind = cgEdge->indirectCallsBegin(),
461 eind = cgEdge->indirectCallsEnd(); ind!=eind; ++ind)
462 {
463 DBOUT(DMTA,outs() << "\nTCT handling indirect call:" << **ind << "\t" << cgEdge->getSrcNode()->getFunction()->getName() << "-->" << cgEdge->getDstNode()->getFunction()->getName() << "\n");
464 handleCallRelation(ctp,cgEdge,*ind);
465 }
466 }
467 }
468
470
472 {
473 print();
474 dump("tct");
475 }
476
477}
#define DBOUT(TYPE, X)
LLVM debug macros, define type of your DBUG model of each pass.
Definition SVFType.h:576
#define DMTA
Definition SVFType.h:597
CallInstSet::const_iterator indirectCallsBegin() const
Definition CallGraph.h:131
CallInstSet::const_iterator directCallsEnd() const
Definition CallGraph.h:126
CallInstSet::const_iterator indirectCallsEnd() const
Definition CallGraph.h:135
CallInstSet::const_iterator directCallsBegin() const
Iterators for direct and indirect callsites.
Definition CallGraph.h:122
const FunObjVar * getFunction() const
Get function of this call node.
Definition CallGraph.h:191
const FunObjVar * getProc() const
Return current procedure.
Definition CxtStmt.h:325
NodeType * getSrcNode() const
NodeType * getDstNode() const
iterator OutEdgeEnd()
iterator OutEdgeBegin()
iterators
static const Option< bool > TCTDotGraph
Definition Options.h:161
NodeID getId() const
Get ID.
Definition SVFValue.h:158
virtual const std::string & getName() const
Definition SVFValue.h:184
bool pushToCTPWorkList(const CxtThreadProc &ctp)
WorkList helper functions.
Definition TCT.h:595
FunSet entryFuncSet
Definition TCT.h:615
TCTNode * getOrCreateTCTNode(const CallStrCxt &cxt, const ICFGNode *fork, const CxtThreadProc &forkSiteCtp, const FunObjVar *routine)
Get or create a tct node based on CxtThread.
Definition TCT.h:528
virtual void collectLoopInfoForJoin()
Handle join site in loop.
Definition TCT.cpp:349
virtual void collectEntryFunInCallGraph()
Get entry functions that are neither called by other functions nor extern functions.
Definition TCT.cpp:219
ICFGNode * createDummyForkSite()
Create and get a new dummy fork site for starter routines.
Definition TCT.h:586
void dump(const std::string &filename)
Dump the graph.
Definition TCT.cpp:568
bool isCandidateFun(const CallGraph::FunctionSet &callees) const
Whether it is a candidate function for indirect call.
Definition TCT.h:294
CxtThreadProcVec ctpList
Thread call graph SCC.
Definition TCT.h:618
virtual void markRelProcs()
Mark relevant procedures that are backward reachable from any fork/join site.
Definition TCT.cpp:165
void print() const
Print TCT information.
Definition TCT.cpp:576
virtual void handleCallRelation(CxtThreadProc &ctp, const CallGraphEdge *cgEdge, const CallICFGNode *call)
Handle call relations.
Definition TCT.cpp:276
void collectMultiForkedThreads()
Definition TCT.cpp:238
CxtThreadProc popFromCTPWorkList()
Definition TCT.h:604
std::ostream & outs()
Overwrite llvm::outs().
Definition SVFUtil.h:58
std::vector< u32_t > CallStrCxt
Definition GeneralType.h:96

◆ collectEntryFunInCallGraph()

void TCT::collectEntryFunInCallGraph ( )
protectedvirtual

Get entry functions that are neither called by other functions nor extern functions.

Get entry function, i.e., functions without callers, e.g., main function

Reimplemented in SVF::SlicedTCT.

Definition at line 219 of file TCT.cpp.

220{
221 for (const auto& item: *(PAG::getPAG()->getCallGraph()))
222 {
223 const FunObjVar* fun = item.second->getFunction();
224 if (SVFUtil::isExtCall(fun))
225 continue;
226 CallGraphNode* node = tcg->getCallGraphNode(fun);
227 if (!node->hasIncomingEdge())
228 {
229 entryFuncSet.insert(fun);
230 }
231 }
232 assert(!entryFuncSet.empty() && "Can't find any function in module!");
233}
cJSON * item
Definition cJSON.h:222
bool hasIncomingEdge() const
Has incoming/outgoing edge set.
static PAG * getPAG(bool buildFromFile=false)
Singleton design here to make sure we only have one instance during any analysis.
Definition PAG.h:121
bool isExtCall(const FunObjVar *fun)
Definition SVFUtil.cpp:524

◆ collectLoopInfoForJoin()

void TCT::collectLoopInfoForJoin ( )
protectedvirtual

Handle join site in loop.

collect loop info for join sites

Collect loop info for join sites the in-loop join site must be joined if the loop is executed

Reimplemented in SVF::SlicedTCT.

Definition at line 349 of file TCT.cpp.

350{
351 for(ThreadCallGraph::CallSiteSet::const_iterator it = tcg->joinsitesBegin(), eit = tcg->joinsitesEnd(); it!=eit; ++it)
352 {
353 const ICFGNode* join = *it;
354 const FunObjVar* svffun = join->getFun();
355 const SVFBasicBlock* svfbb = join->getBB();
356
357 if(svffun->hasLoopInfo(svfbb))
358 {
359 const LoopBBs& lp = svffun->getLoopInfo(svfbb);
360 if(!lp.empty() && isJoinMustExecutedInLoop(lp,join))
361 {
362 joinSiteToLoopMap[join] = lp;
363 }
364 }
365
366 if(isInRecursion(join))
367 inRecurJoinSites.insert(join);
368 }
369}
const LoopBBs & getLoopInfo(const SVFBasicBlock *bb) const
bool hasLoopInfo(const SVFBasicBlock *bb) const
virtual const FunObjVar * getFun() const
Return the function of this ICFGNode.
Definition ICFGNode.h:75
virtual const SVFBasicBlock * getBB() const
Return the basic block of this ICFGNode.
Definition ICFGNode.h:81
bool isInRecursion(const ICFGNode *inst) const
Whether an instruction is in a recursion.
Definition TCT.cpp:123
InstToLoopMap joinSiteToLoopMap
Map a CxtThread to its start routine function.
Definition TCT.h:623
bool isJoinMustExecutedInLoop(const LoopBBs &lp, const ICFGNode *join)
Return true if a join instruction must be executed inside a loop.
Definition TCT.cpp:325
Set< const ICFGNode * > inRecurJoinSites
Fork or Join sites in recursions.
Definition TCT.h:624
SVFLoopAndDomInfo::LoopBBs LoopBBs
Definition TCT.h:159

◆ collectMultiForkedThreads()

void TCT::collectMultiForkedThreads ( )
protected

Collect multi-forked threads whose 1, cxt is in loop or recursion; 2, parent thread is a multi-forked thread.

Collect all multi-forked threads

Definition at line 238 of file TCT.cpp.

239{
240 if (this->nodeNum == 0 )
241 return;
242
243 FIFOWorkList<TCTNode*> worklist;
244 worklist.push(getTCTNode(0));
245
246 while(!worklist.empty())
247 {
248 TCTNode* node = worklist.pop();
249 const CxtThread &ct = node->getCxtThread();
250
251 if(ct.isIncycle() || ct.isInloop())
252 {
253 node->setMultiforked(true);
254 }
255 else
256 {
257 for (TCT::ThreadCreateEdgeSet::const_iterator it = node->getInEdges().begin(), eit = node->getInEdges().end(); it != eit;
258 ++it)
259 {
260 if ((*it)->getSrcNode()->isMultiforked())
261 node->setMultiforked(true);
262 }
263 }
264 for (TCT::ThreadCreateEdgeSet::const_iterator it = node->getOutEdges().begin(), eit = node->getOutEdges().end(); it != eit;
265 ++it)
266 {
267 worklist.push((*it)->getDstNode());
268 }
269 }
270}
bool isInloop() const
Definition CxtStmt.h:262
bool isIncycle() const
Definition CxtStmt.h:270
bool push(const Data &data)
Definition WorkList.h:180
bool empty() const
Definition WorkList.h:161
const GEdgeSetTy & getOutEdges() const
const GEdgeSetTy & getInEdges() const
const CxtThread & getCxtThread() const
Get thread creation context, <fork site, call string context>.
Definition TCT.h:103
void setMultiforked(bool value)
Definition TCT.h:118
TCTNode * getTCTNode(NodeID id) const
Get TCT node.
Definition TCT.h:209

◆ create() [1/2]

std::unique_ptr< TCT > TCT::create ( PointerAnalysis * p)
static

Construct and build a TCT with the command-line context bound.

Definition at line 41 of file TCT.cpp.

42{
44}
static Option< u32_t > MaxContextLen
Definition Options.h:81
static std::unique_ptr< TCT > create(PointerAnalysis *p)
Construct and build a TCT with the command-line context bound.
Definition TCT.cpp:41

◆ create() [2/2]

std::unique_ptr< TCT > TCT::create ( PointerAnalysis * p,
u32_t contextLimit )
static

Construct and build a TCT with an explicit context bound. Analyses that require a phase-specific bound must pass it here rather than mutating the process-global option.

Definition at line 46 of file TCT.cpp.

47{
48 std::unique_ptr<TCT> tct(new TCT(p, contextLimit));
49 tct->build();
50 return tct;
51}
TCT(PointerAnalysis *p, u32_t contextLimit)
Definition TCT.cpp:53

◆ createDummyForkSite()

ICFGNode * SVF::TCT::createDummyForkSite ( )
inlineprotected

Create and get a new dummy fork site for starter routines.

Definition at line 586 of file TCT.h.

587 {
588 ICFGNode* dummyForkSite = new ICFGNode(dummyForkICFGNodeID--, SVFValue::GlobalBlock);
589 dummyForkSites.insert(dummyForkSite);
590 return dummyForkSite;
591 }
NodeID dummyForkICFGNodeID
unique ID generator for dummy
Definition TCT.h:626

◆ dump()

void TCT::dump ( const std::string & filename)

Dump the graph.

Dump call graph into dot file

Definition at line 568 of file TCT.cpp.

569{
570 GraphPrinter::WriteGraphToFile(outs(), filename, this);
571}
static void WriteGraphToFile(SVF::OutStream &O, const std::string &GraphName, const GraphType &GT, bool simple=false)

◆ dumpCxt()

void TCT::dumpCxt ( CallStrCxt & cxt)

Dump calling context.

Dump calling context information

Definition at line 550 of file TCT.cpp.

551{
552 std::string str;
553 std::stringstream rawstr(str);
554 rawstr << "[:";
555 for(CallStrCxt::const_iterator it = cxt.begin(), eit = cxt.end(); it!=eit; ++it)
556 {
557 rawstr << " ' "<< *it << " ' ";
558 rawstr << (tcg->getCallSite(*it))->valueOnlyToString();
559 rawstr << " call " << tcg->getCallSite(*it)->getCaller()->getName() << "-->" << tcg->getCalleeOfCallSite(*it)->getName() << ", \n";
560 }
561 rawstr << " ]";
562 outs() << "max cxt = " << cxt.size() << rawstr.str() << "\n";
563}

◆ getAncestorThreads()

const NodeBS SVF::TCT::getAncestorThreads ( NodeID tid) const
inline

Get all ancestor threads.

Definition at line 336 of file TCT.h.

337 {
338 NodeBS tds;
339 if(hasParentThread(tid) == false)
340 return tds;
341
342 FIFOWorkList<NodeID> worklist;
343 for(NodeID parentTid : getParentThreads(tid))
344 worklist.push(parentTid);
345
346 while(!worklist.empty())
347 {
348 NodeID t = worklist.pop();
349 if(tds.test_and_set(t))
350 {
351 if(hasParentThread(t))
352 for(NodeID parentTid : getParentThreads(t))
353 worklist.push(parentTid);
354 }
355 }
356 return tds;
357 }
NodeBS getParentThreads(NodeID tid) const
Get parent threads.
Definition TCT.h:323
bool hasParentThread(NodeID tid) const
Get parent and sibling threads.
Definition TCT.h:317
SparseBitVector NodeBS
Definition GeneralType.h:82

◆ getChildrenBegin()

ThreadCreateEdgeSet::const_iterator SVF::TCT::getChildrenBegin ( const TCTNode * node) const
inline

Get children and parent nodes.

Definition at line 220 of file TCT.h.

221 {
222 return node->OutEdgeBegin();
223 }

◆ getChildrenEnd()

ThreadCreateEdgeSet::const_iterator SVF::TCT::getChildrenEnd ( const TCTNode * node) const
inline

Definition at line 224 of file TCT.h.

225 {
226 return node->OutEdgeEnd();
227 }

◆ getCxtOfCxtThread()

const CallStrCxtSet & SVF::TCT::getCxtOfCxtThread ( const CxtThread & ct) const
inline

get the contexts of a thread at its spawning sites (fork sites)

Definition at line 380 of file TCT.h.

381 {
382 CxtThreadToForkCxtSet::const_iterator it = ctToForkCxtsMap.find(ct);
383 assert(it!=ctToForkCxtsMap.end() && "Cxt Thread not found!!");
384 return it->second;
385 }

◆ getEntryProcs()

const FunSet & SVF::TCT::getEntryProcs ( ) const
inline

Get marked candidate functions.

Definition at line 245 of file TCT.h.

246 {
247 return entryFuncSet;
248 }

◆ getGraphEdge()

TCTEdge * TCT::getGraphEdge ( TCTNode * src,
TCTNode * dst,
TCTEdge::CEDGEK kind )

Get call graph edge via nodes.

get PTACallGraph edge via nodes

Definition at line 605 of file TCT.cpp.

606{
607 for (TCTEdge::ThreadCreateEdgeSet::const_iterator iter = src->OutEdgeBegin(); iter != src->OutEdgeEnd(); ++iter)
608 {
609 TCTEdge* edge = (*iter);
610 if (edge->getEdgeKind() == kind && edge->getDstID() == dst->getId())
611 return edge;
612 }
613 return nullptr;
614}
GEdgeKind getEdgeKind() const
NodeID getDstID() const

◆ getJoinLoop()

LoopBBs & SVF::TCT::getJoinLoop ( const CallICFGNode * join)
inline

Get loop for join site.

Definition at line 396 of file TCT.h.

397 {
398 assert(tcg->getThreadAPI()->isTDJoin(join) && "not a join site");
399 InstToLoopMap::iterator it = joinSiteToLoopMap.find(join);
400 assert(it!=joinSiteToLoopMap.end() && "loop not found");
401 return it->second;
402 }

◆ getLoop() [1/2]

const LoopBBs & SVF::TCT::getLoop ( const ICFGNode * inst)

Get loop for an instruction.

◆ getLoop() [2/2]

const TCT::LoopBBs & TCT::getLoop ( const SVFBasicBlock * bb)

Get loop for fork/join site.

Get loop for fork/join site

Definition at line 409 of file TCT.cpp.

410{
411 const FunObjVar* fun = bb->getParent();
412 return fun->getLoopInfo(bb);
413}
const FunObjVar * getParent() const

◆ getMakredProcs()

const FunSet & SVF::TCT::getMakredProcs ( ) const
inline

Get marked candidate functions.

Definition at line 239 of file TCT.h.

240 {
241 return candidateFuncSet;
242 }
FunSet candidateFuncSet
Procedures that are neither called by other functions nor extern functions.
Definition TCT.h:616

◆ getMaxCxtSize()

u32_t SVF::TCT::getMaxCxtSize ( ) const
inline

Definition at line 260 of file TCT.h.

261 {
262 return MaxCxtSize;
263 }

◆ getOrCreateTCTNode()

TCTNode * SVF::TCT::getOrCreateTCTNode ( const CallStrCxt & cxt,
const ICFGNode * fork,
const CxtThreadProc & forkSiteCtp,
const FunObjVar * routine )
inlineprotected

Get or create a tct node based on CxtThread.

Definition at line 528 of file TCT.h.

529 {
530 CxtThread ct(cxt,fork);
531 CxtThreadToNodeMap::const_iterator it = ctpToNodeMap.find(ct);
532 if(it!=ctpToNodeMap.end())
533 {
534 // A second spawn context merged onto this truncated CxtThread: the
535 // node stands for multiple dynamic instances, so mark it multiforked.
536 if (addCxtOfCxtThread(forkSiteCtp.getTid(), forkSiteCtp.getContext(), ct))
537 it->second->setMultiforked(true);
538 return it->second;
539 }
540
541 addCxtOfCxtThread(forkSiteCtp.getTid(), forkSiteCtp.getContext(), ct);
542 addStartRoutineOfCxtThread(routine,ct);
543
545 return addTCTNode(ct);
546 }
void setMultiForkedAttrs(CxtThread &ct)
Set multi-forked thread attributes.
Definition TCT.h:550
bool addCxtOfCxtThread(NodeID pTid, const CallStrCxt &cxt, const CxtThread &ct)
Definition TCT.h:574
void addStartRoutineOfCxtThread(const FunObjVar *fun, const CxtThread &ct)
Add start routine function of a cxt thread.
Definition TCT.h:580
TCTNode * addTCTNode(const CxtThread &ct)
Add TCT node.
Definition TCT.h:465

◆ getParentsBegin()

ThreadCreateEdgeSet::const_iterator SVF::TCT::getParentsBegin ( const TCTNode * node) const
inline

Definition at line 228 of file TCT.h.

229 {
230 return node->InEdgeBegin();
231 }

◆ getParentsEnd()

ThreadCreateEdgeSet::const_iterator SVF::TCT::getParentsEnd ( const TCTNode * node) const
inline

Definition at line 232 of file TCT.h.

233 {
234 return node->InEdgeEnd();
235 }

◆ getParentThreads()

NodeBS SVF::TCT::getParentThreads ( NodeID tid) const
inline

Get parent threads.

Definition at line 323 of file TCT.h.

324 {
325 NodeBS parentTds;
326 const TCTNode* node = getTCTNode(tid);
327 assert(node->getInEdges().size()>=1 && "does not have a parent thread");
328
329 for (const TCTEdge* edge : node->getInEdges())
330 {
331 parentTds.set(edge->getSrcID());
332 }
333 return parentTds;
334 }

◆ getPTA()

PointerAnalysis * SVF::TCT::getPTA ( ) const
inline

Get PTA.

Definition at line 204 of file TCT.h.

205 {
206 return pta;
207 }

◆ getSiblingThread()

const NodeBS SVF::TCT::getSiblingThread ( NodeID tid) const
inline

Get sibling threads.

Definition at line 359 of file TCT.h.

360 {
361 NodeBS tds;
362 if(hasParentThread(tid) == false)
363 return tds;
364 for (NodeID parentTid : getParentThreads(tid))
365 {
366 const TCTNode* parentNode = getTCTNode(parentTid);
367 for(ThreadCreateEdgeSet::const_iterator it = getChildrenBegin(parentNode),
368 eit = getChildrenEnd(parentNode); it!=eit; ++it)
369 {
370 NodeID child = (*it)->getDstNode()->getId();
371 if(child!=tid)
372 tds.set(child);
373 }
374 }
375 return tds;
376 }
cJSON * child
Definition cJSON.cpp:2723
ThreadCreateEdgeSet::const_iterator getChildrenBegin(const TCTNode *node) const
Get children and parent nodes.
Definition TCT.h:220
ThreadCreateEdgeSet::const_iterator getChildrenEnd(const TCTNode *node) const
Definition TCT.h:224

◆ getStartRoutineOfCxtThread()

const FunObjVar * SVF::TCT::getStartRoutineOfCxtThread ( const CxtThread & ct) const
inline

get the start routine function of a thread

Definition at line 388 of file TCT.h.

389 {
390 CxtThreadToFun::const_iterator it = ctToRoutineFunMap.find(ct);
391 assert(it!=ctToRoutineFunMap.end() && "Cxt Thread not found!!");
392 return it->second;
393 }

◆ getTCTEdgeNum()

u32_t SVF::TCT::getTCTEdgeNum ( ) const
inline

Definition at line 256 of file TCT.h.

257 {
258 return TCTEdgeNum;
259 }

◆ getTCTNode() [1/2]

TCTNode * SVF::TCT::getTCTNode ( const CxtThread & ct) const
inline

Definition at line 285 of file TCT.h.

286 {
287 CxtThreadToNodeMap::const_iterator it = ctpToNodeMap.find(ct);
288 assert(it!=ctpToNodeMap.end() && "TCT node not found??");
289 return it->second;
290 }

◆ getTCTNode() [2/2]

TCTNode * SVF::TCT::getTCTNode ( NodeID id) const
inline

Get TCT node.

Definition at line 209 of file TCT.h.

210 {
211 return getGNode(id);
212 }
NodeType * getGNode(NodeID id) const

◆ getTCTNodeNum()

u32_t SVF::TCT::getTCTNodeNum ( ) const
inline

Get Statistics.

Definition at line 252 of file TCT.h.

253 {
254 return TCTNodeNum;
255 }

◆ getThreadCallGraph()

ThreadCallGraph * SVF::TCT::getThreadCallGraph ( ) const
inline

Get TCG.

Definition at line 199 of file TCT.h.

200 {
201 return tcg;
202 }

◆ handleCallRelation()

void TCT::handleCallRelation ( CxtThreadProc & ctp,
const CallGraphEdge * cgEdge,
const CallICFGNode * cs )
protectedvirtual

Handle call relations.

Handle call relations

handle calling context for candidate functions only

Create spawnee TCT node

Add TCT nodes and edge

Reimplemented in SVF::SlicedTCT.

Definition at line 276 of file TCT.cpp.

277{
278 const FunObjVar* callee = cgEdge->getDstNode()->getFunction();
279
280 CallStrCxt cxt(ctp.getContext());
281 CallStrCxt oldCxt = cxt;
282 const CallICFGNode* callNode = cs;
283
285 if(isCandidateFun(callNode->getFun()) == true)
286 pushCxt(cxt,callNode,callee);
287
289 {
290 CxtThreadProc newctp(ctp.getTid(),cxt,callee);
291 if(pushToCTPWorkList(newctp))
292 {
293 DBOUT(DMTA,outs() << "TCT Process CallRet old ctp --"; ctp.dump());
294 DBOUT(DMTA,outs() << "TCT Process CallRet new ctp --"; newctp.dump());
295 }
296 }
297
298 else if(cgEdge->getEdgeKind() == CallGraphEdge::TDForkEdge)
299 {
301 TCTNode* spawneeNode = getOrCreateTCTNode(cxt,callNode, ctp, callee);
302 CxtThreadProc newctp(spawneeNode->getId(),cxt,callee);
303
304 if(pushToCTPWorkList(newctp))
305 {
307 if(addTCTEdge(this->getTCTNode(ctp.getTid()), spawneeNode))
308 {
309 DBOUT(DMTA,outs() << "Add TCT Edge from thread " << ctp.getTid() << " ";
310 this->getTCTNode(ctp.getTid())->getCxtThread().dump();
311 outs() << " to thread " << spawneeNode->getId() << " ";
312 spawneeNode->getCxtThread().dump();
313 outs() << "\n" );
314 }
315 DBOUT(DMTA,outs() << "TCT Process Fork old ctp --"; ctp.dump());
316 DBOUT(DMTA,outs() << "TCT Process Fork new ctp --"; newctp.dump());
317 }
318 }
319}
const CallStrCxt & getContext() const
Return current context.
Definition CxtStmt.h:330
NodeID getTid() const
Return current thread id.
Definition CxtStmt.h:410
void dump() const
Dump CxtThreadProc.
Definition CxtStmt.h:447
void dump() const
Dump CxtThread.
Definition CxtStmt.h:277
bool addTCTEdge(TCTNode *src, TCTNode *dst)
Add TCT edge.
Definition TCT.h:476
virtual void pushCxt(CallStrCxt &cxt, const CallICFGNode *call, const FunObjVar *callee)
Context helper functions.
Definition TCT.cpp:482

◆ hasGraphEdge()

TCTEdge * TCT::hasGraphEdge ( TCTNode * src,
TCTNode * dst,
TCTEdge::CEDGEK kind ) const

Whether we have already created this call graph edge.

Whether we have already created this call graph edge

Definition at line 588 of file TCT.cpp.

589{
590 TCTEdge edge(src, dst, kind);
591 TCTEdge* outEdge = src->hasOutgoingEdge(&edge);
592 TCTEdge* inEdge = dst->hasIncomingEdge(&edge);
593 if (outEdge && inEdge)
594 {
595 assert(outEdge == inEdge && "edges not match");
596 return outEdge;
597 }
598 else
599 return nullptr;
600}
bool hasOutgoingEdge() const

◆ hasJoinLoop()

bool SVF::TCT::hasJoinLoop ( const CallICFGNode * join) const
inline

Definition at line 404 of file TCT.h.

405 {
406 assert(tcg->getThreadAPI()->isTDJoin(join) && "not a join site");
407 InstToLoopMap::const_iterator it = joinSiteToLoopMap.find(join);
408 return it!=joinSiteToLoopMap.end();
409 }

◆ hasLoop() [1/2]

bool SVF::TCT::hasLoop ( const ICFGNode * inst) const
inline

Definition at line 416 of file TCT.h.

417 {
418 return hasLoop(inst->getBB());
419 }
bool hasLoop(const SVFBasicBlock *bb) const
Definition TCT.h:411

◆ hasLoop() [2/2]

bool SVF::TCT::hasLoop ( const SVFBasicBlock * bb) const
inline

Definition at line 411 of file TCT.h.

412 {
413 const FunObjVar* fun = bb->getFunction();
414 return fun->hasLoopInfo(bb);
415 }

◆ hasParentThread()

bool SVF::TCT::hasParentThread ( NodeID tid) const
inline

Get parent and sibling threads.

Has parent thread

Definition at line 317 of file TCT.h.

318 {
319 const TCTNode* node = getTCTNode(tid);
320 return node->getInEdges().size()==1;
321 }

◆ hasTCTNode()

bool SVF::TCT::hasTCTNode ( const CxtThread & ct) const
inline

Find/Get TCT node.

Definition at line 281 of file TCT.h.

282 {
283 return ctpToNodeMap.find(ct)!=ctpToNodeMap.end();
284 }

◆ inSameCallGraphSCC()

bool SVF::TCT::inSameCallGraphSCC ( const CallGraphNode * src,
const CallGraphNode * dst )
inline

Whether two functions in the same callgraph scc.

Definition at line 309 of file TCT.h.

310 {
311 return (tcgSCC->repNode(src->getId()) == tcgSCC->repNode(dst->getId()));
312 }

◆ isCallSite()

bool SVF::TCT::isCallSite ( const ICFGNode * inst)
inline

Whether it is a callsite.

Definition at line 274 of file TCT.h.

275 {
276 return SVFUtil::isa<CallICFGNode>(inst);
277 }
LLVM_NODISCARD bool isa(const Y &Val)
Definition Casting.h:241

◆ isCandidateFun() [1/2]

bool SVF::TCT::isCandidateFun ( const CallGraph::FunctionSet & callees) const
inline

Whether it is a candidate function for indirect call.

Definition at line 294 of file TCT.h.

295 {
296 for(CallGraph::FunctionSet::const_iterator cit = callees.begin(),
297 ecit = callees.end(); cit!=ecit; cit++)
298 {
299 if(candidateFuncSet.find((*cit))!=candidateFuncSet.end())
300 return true;
301 }
302 return false;
303 }

◆ isCandidateFun() [2/2]

bool SVF::TCT::isCandidateFun ( const FunObjVar * fun) const
inline

Definition at line 304 of file TCT.h.

305 {
306 return candidateFuncSet.find(fun)!=candidateFuncSet.end();
307 }

◆ isContextSuffix()

bool TCT::isContextSuffix ( const CallStrCxt & lhs,
const CallStrCxt & call )

If lhs is a suffix of rhs, including equal.

If lhs is a suffix of rhs, including equal

Definition at line 530 of file TCT.cpp.

531{
532 if (lhs.size() > call.size())
533 return false;
534 bool isSuffix = true;
535 for (size_t i = 0; i < lhs.size(); ++i)
536 {
537 if (lhs[lhs.size() - 1 - i] != call[call.size() - 1 - i])
538 {
539 isSuffix = false;
540 break;
541 }
542 }
543 return isSuffix;
544}

◆ isExtCall()

bool SVF::TCT::isExtCall ( const ICFGNode * inst)
inline

Whether it is calling an external function.

Definition at line 267 of file TCT.h.

268 {
269 if(const CallICFGNode* call = SVFUtil::dyn_cast<CallICFGNode>(inst))
270 return SVFUtil::isExtCall(call);
271 return false;
272 }

◆ isInLoopInstruction()

bool TCT::isInLoopInstruction ( const ICFGNode * inst)
protected

Multi-forked threads.

Whether an instruction is in a loop

An instruction i is in loop (1) the instruction i itself (2) all the callsites invoke the function where i resides in

Definition at line 78 of file TCT.cpp.

79{
80 assert(inst && "null value instruction!!");
81
83 FIFOWorkList<const ICFGNode*> worklist;
84 worklist.push(inst);
85
86 while(!worklist.empty())
87 {
88 const ICFGNode* inst = worklist.pop();
89 insts.insert(inst);
90 CallGraphNode* cgnode = tcg->getCallGraphNode(inst->getFun());
91 for(CallGraphNode::const_iterator nit = cgnode->InEdgeBegin(), neit = cgnode->InEdgeEnd(); nit!=neit; nit++)
92 {
93 for(CallGraphEdge::CallInstSet::const_iterator cit = (*nit)->directCallsBegin(),
94 ecit = (*nit)->directCallsEnd(); cit!=ecit; ++cit)
95 {
96 if(insts.insert(*cit).second)
97 worklist.push(*cit);
98 }
99 for(CallGraphEdge::CallInstSet::const_iterator cit = (*nit)->indirectCallsBegin(),
100 ecit = (*nit)->indirectCallsEnd(); cit!=ecit; ++cit)
101 {
102 if(insts.insert(*cit).second)
103 worklist.push(*cit);
104 }
105 }
106 }
107
108 for(const ICFGNode* i : insts)
109 {
110 if(i->getFun()->hasLoopInfo(i->getBB()))
111 return true;
112 }
113
114
115 return false;
116}
iterator InEdgeBegin()
iterator InEdgeEnd()
std::unordered_set< Key, Hash, KeyEqual, Allocator > Set
Definition GeneralType.h:51

◆ isInRecursion()

bool TCT::isInRecursion ( const ICFGNode * inst) const
protected

Whether an instruction is in a recursion.

An instruction i is in a recursion (1) the function f where i resides in is in a recursion (2) any caller function starting from the function f in is in a recursion

Definition at line 123 of file TCT.cpp.

124{
125 const FunObjVar* f = inst->getFun();
126 FIFOWorkList<const FunObjVar*> worklist;
128 worklist.push(f);
129
130 while(!worklist.empty())
131 {
132 const FunObjVar* svffun = worklist.pop();
133 visits.insert(svffun);
134 if(tcgSCC->isInCycle(tcg->getCallGraphNode(svffun)->getId()))
135 return true;
136
137 const CallGraphNode* cgnode = tcg->getCallGraphNode(svffun);
138
139 for(CallGraphNode::const_iterator nit = cgnode->InEdgeBegin(), neit = cgnode->InEdgeEnd(); nit!=neit; nit++)
140 {
141 for(CallGraphEdge::CallInstSet::const_iterator cit = (*nit)->directCallsBegin(),
142 ecit = (*nit)->directCallsEnd(); cit!=ecit; ++cit)
143 {
144 const FunObjVar* caller = (*cit)->getFun();
145 if(visits.find(caller)==visits.end())
146 worklist.push(caller);
147 }
148 for(CallGraphEdge::CallInstSet::const_iterator cit = (*nit)->indirectCallsBegin(),
149 ecit = (*nit)->indirectCallsEnd(); cit!=ecit; ++cit)
150 {
151 const FunObjVar* caller = (*cit)->getFun();
152 if(visits.find(caller)==visits.end())
153 worklist.push(caller);
154 }
155 }
156 }
157
158 return false;
159
160}

◆ isJoinMustExecutedInLoop()

bool TCT::isJoinMustExecutedInLoop ( const LoopBBs & lp,
const ICFGNode * join )

Return true if a join instruction must be executed inside a loop.

Return true if a join instruction must be executed inside a loop joinbb should post dominate the successive basic block of a loop header

Definition at line 325 of file TCT.cpp.

326{
327 assert(!lp.empty() && "this is not a loop, empty basic block");
328 const FunObjVar* svffun = join->getFun();
329 const SVFBasicBlock* loopheadbb = svffun->getLoopHeader(lp);
330 const SVFBasicBlock* joinbb = join->getBB();
331 assert(loopheadbb->getParent()==joinbb->getParent() && "should inside same function");
332
333 for (const SVFBasicBlock* svf_scc_bb : loopheadbb->getSuccessors())
334 {
335 if(svffun->loopContainsBB(lp,svf_scc_bb))
336 {
337 if(svffun->dominate(joinbb,svf_scc_bb)==false)
338 return false;
339 }
340 }
341
342 return true;
343}
const SVFBasicBlock * getLoopHeader(const BBList &lp) const
bool dominate(const SVFBasicBlock *bbKey, const SVFBasicBlock *bbValue) const
bool loopContainsBB(const BBList &lp, const SVFBasicBlock *bb) const
std::vector< const SVFBasicBlock * > getSuccessors() const

◆ isJoinSiteInRecursion()

bool SVF::TCT::isJoinSiteInRecursion ( const CallICFGNode * join) const
inline

Whether a join site is in recursion.

Definition at line 438 of file TCT.h.

439 {
440 assert(tcg->getThreadAPI()->isTDJoin(join) && "not a join site");
441 return inRecurJoinSites.find(join)!=inRecurJoinSites.end();
442 }

◆ isLoopExitOfJoinLoop()

bool TCT::isLoopExitOfJoinLoop ( const SVFBasicBlock * bb)
protected

Whether a given bb is an exit of a inloop join site.

Whether a given bb is an exit of a inloop join site

Definition at line 388 of file TCT.cpp.

389{
390 for(InstToLoopMap::const_iterator it = joinSiteToLoopMap.begin(), eit = joinSiteToLoopMap.end(); it!=eit; ++it)
391 {
392 std::vector<const SVFBasicBlock*> exitbbs;
393 it->first->getFun()->getExitBlocksOfLoop(it->first->getBB(),exitbbs);
394 while(!exitbbs.empty())
395 {
396 const SVFBasicBlock* eb = exitbbs.back();
397 exitbbs.pop_back();
398 if(eb == bb)
399 return true;
400 }
401 }
402
403 return false;
404}

◆ isLoopHeaderOfJoinLoop()

bool TCT::isLoopHeaderOfJoinLoop ( const SVFBasicBlock * bb)
protected

Whether a given bb is a loop head of a inloop join site.

Return true if a given bb is a loop head of a inloop join site

Definition at line 374 of file TCT.cpp.

375{
376 for(InstToLoopMap::const_iterator it = joinSiteToLoopMap.begin(), eit = joinSiteToLoopMap.end(); it!=eit; ++it)
377 {
378 if(bb->getParent()->getLoopHeader(it->second) == bb)
379 return true;
380 }
381
382 return false;
383}

◆ isVisitedCTPs()

bool SVF::TCT::isVisitedCTPs ( const CxtThreadProc & ctp) const
inlineprotected

Definition at line 609 of file TCT.h.

610 {
611 return visitedCTPs.find(ctp)!=visitedCTPs.end();
612 }
CxtThreadProcSet visitedCTPs
CxtThreadProc List.
Definition TCT.h:619

◆ markRelProcs() [1/2]

void TCT::markRelProcs ( )
protectedvirtual

Mark relevant procedures that are backward reachable from any fork/join site.

Mark relevant procedures that are backward reachable from any fork/join site

Reimplemented in SVF::SlicedTCT.

Definition at line 165 of file TCT.cpp.

166{
167 for (ThreadCallGraph::CallSiteSet::const_iterator it = tcg->forksitesBegin(), eit = tcg->forksitesEnd(); it != eit; ++it)
168 {
169 const FunObjVar* svfun = (*it)->getParent()->getParent();
170 markRelProcs(svfun);
171
172 for(ThreadCallGraph::ForkEdgeSet::const_iterator nit = tcg->getForkEdgeBegin(*it), neit = tcg->getForkEdgeEnd(*it); nit!=neit; nit++)
173 {
174 const CallGraphNode* forkeeNode = (*nit)->getDstNode();
175 candidateFuncSet.insert(forkeeNode->getFunction());
176 }
177
178 }
179
180 for (ThreadCallGraph::CallSiteSet::const_iterator it = tcg->joinsitesBegin(), eit = tcg->joinsitesEnd(); it != eit; ++it)
181 {
182 const FunObjVar* svfun = (*it)->getParent()->getParent();
183 markRelProcs(svfun);
184 }
185
186 if(candidateFuncSet.empty())
187 writeWrnMsg("We didn't recognize any fork site, this is single thread program?");
188}
void writeWrnMsg(const std::string &msg)
Writes a message run through wrnMsg.
Definition SVFUtil.cpp:88

◆ markRelProcs() [2/2]

void TCT::markRelProcs ( const FunObjVar * svffun)
protectedvirtual

Add relevant procedures that are backward reachable from svffun on Thread Call Graph

Reimplemented in SVF::SlicedTCT.

Definition at line 193 of file TCT.cpp.

194{
195 CallGraphNode* cgnode = tcg->getCallGraphNode(svffun);
196 FIFOWorkList<const CallGraphNode*> worklist;
197 PTACGNodeSet visited;
198 worklist.push(cgnode);
199 visited.insert(cgnode);
200 while(!worklist.empty())
201 {
202 const CallGraphNode* node = worklist.pop();
203 candidateFuncSet.insert(node->getFunction());
204 for(CallGraphNode::const_iterator nit = node->InEdgeBegin(), neit = node->InEdgeEnd(); nit!=neit; nit++)
205 {
206 const CallGraphNode* srcNode = (*nit)->getSrcNode();
207 if(visited.find(srcNode)==visited.end())
208 {
209 visited.insert(srcNode);
210 worklist.push(srcNode);
211 }
212 }
213 }
214}
Set< const CallGraphNode * > PTACGNodeSet
Definition TCT.h:176

◆ matchAndPopCxt()

bool TCT::matchAndPopCxt ( CallStrCxt & cxt,
const CallICFGNode * call,
const FunObjVar * callee )

Match context.

Match calling context

handle calling context for candidate functions only

partial match

Definition at line 502 of file TCT.cpp.

503{
504 const FunObjVar* caller = call->getFun();
505 CallSiteID csId = tcg->getCallSiteID(call, callee);
506
508 if(isCandidateFun(caller) == false)
509 return true;
510
512 if(cxt.empty())
513 return true;
514
515 if(inSameCallGraphSCC(tcg->getCallGraphNode(caller),tcg->getCallGraphNode(callee))==false)
516 {
517 if(cxt.back() == csId)
518 cxt.pop_back();
519 else
520 return false;
521 DBOUT(DMTA,dumpCxt(cxt));
522 }
523
524 return true;
525}
bool inSameCallGraphSCC(const CallGraphNode *src, const CallGraphNode *dst)
Whether two functions in the same callgraph scc.
Definition TCT.h:309
void dumpCxt(CallStrCxt &cxt)
Dump calling context.
Definition TCT.cpp:550
unsigned CallSiteID
Definition GeneralType.h:78

◆ popFromCTPWorkList()

CxtThreadProc SVF::TCT::popFromCTPWorkList ( )
inlineprotected

Definition at line 604 of file TCT.h.

605 {
606 CxtThreadProc ctp = ctpList.pop();
607 return ctp;
608 }

◆ print()

void TCT::print ( ) const

Print TCT information.

Print TCT information

Definition at line 576 of file TCT.cpp.

577{
578 for(TCT::const_iterator it = this->begin(), eit = this->end(); it!=eit; ++it)
579 {
580 outs() << "TID " << it->first << "\t";
581 it->second->getCxtThread().dump();
582 }
583}
IDToNodeMapTy::const_iterator const_iterator

◆ pushCxt()

void TCT::pushCxt ( CallStrCxt & cxt,
const CallICFGNode * call,
const FunObjVar * callee )
virtual

Context helper functions.

Push calling context

Push calling context, with k limiting

Definition at line 482 of file TCT.cpp.

483{
484 const FunObjVar* caller = call->getFun();
485 CallSiteID csId = tcg->getCallSiteID(call, callee);
486
487 if(inSameCallGraphSCC(tcg->getCallGraphNode(caller),tcg->getCallGraphNode(callee))==false)
488 {
489 cxt.push_back(csId);
490 if (cxt.size() > contextLimit)
491 cxt.erase(cxt.begin());
492 if (cxt.size() > MaxCxtSize)
493 MaxCxtSize = cxt.size();
494 DBOUT(DMTA,dumpCxt(cxt));
495 }
496}

◆ pushToCTPWorkList()

bool SVF::TCT::pushToCTPWorkList ( const CxtThreadProc & ctp)
inlineprotected

WorkList helper functions.

Definition at line 595 of file TCT.h.

596 {
597 if(isVisitedCTPs(ctp)==false)
598 {
599 visitedCTPs.insert(ctp);
600 return ctpList.push(ctp);
601 }
602 return false;
603 }
bool isVisitedCTPs(const CxtThreadProc &ctp) const
Definition TCT.h:609

◆ setMultiForkedAttrs()

void SVF::TCT::setMultiForkedAttrs ( CxtThread & ct)
inlineprotected

Set multi-forked thread attributes.

non-main thread spawned at a real fork site. The main thread uses a synthetic dummy fork site (see createDummyForkSite); it has no real function/call-graph node, is never in a loop or recursion, and must be treated like the null (main) case – otherwise isInLoopInstruction would look up a call-graph node that does not exist.

main thread (null or dummy fork site)

Definition at line 550 of file TCT.h.

551 {
557 if(ct.getThread() != nullptr &&
558 dummyForkSites.find(ct.getThread()) == dummyForkSites.end())
559 {
560 const ICFGNode* svfInst = ct.getThread();
561 ct.setInloop(isInLoopInstruction(svfInst));
562 ct.setIncycle(isInRecursion(svfInst));
563 }
565 else
566 {
567 ct.setInloop(false);
568 ct.setIncycle(false);
569 }
570 }
bool isInLoopInstruction(const ICFGNode *inst)
Multi-forked threads.
Definition TCT.cpp:78

Member Data Documentation

◆ candidateFuncSet

FunSet SVF::TCT::candidateFuncSet
protected

Procedures that are neither called by other functions nor extern functions.

Definition at line 616 of file TCT.h.

◆ contextLimit

const u32_t SVF::TCT::contextLimit
protected

Definition at line 459 of file TCT.h.

◆ ctpList

CxtThreadProcVec SVF::TCT::ctpList
protected

Thread call graph SCC.

Definition at line 618 of file TCT.h.

◆ ctpToNodeMap

CxtThreadToNodeMap SVF::TCT::ctpToNodeMap
protected

Record all visited ctps.

Definition at line 620 of file TCT.h.

◆ ctToForkCxtsMap

CxtThreadToForkCxtSet SVF::TCT::ctToForkCxtsMap
protected

Map a ctp to its graph node.

Definition at line 621 of file TCT.h.

◆ ctToRoutineFunMap

CxtThreadToFun SVF::TCT::ctToRoutineFunMap
protected

Map a CxtThread to the context at its spawning site (fork site).

Definition at line 622 of file TCT.h.

◆ dummyForkICFGNodeID

NodeID SVF::TCT::dummyForkICFGNodeID = UINT32_MAX
protected

unique ID generator for dummy

Definition at line 626 of file TCT.h.

◆ dummyForkSites

DummyForkSiteSet SVF::TCT::dummyForkSites
protected

set of dummy fork sites for starter routines

Definition at line 625 of file TCT.h.

◆ entryFuncSet

FunSet SVF::TCT::entryFuncSet
protected

Definition at line 615 of file TCT.h.

◆ inRecurJoinSites

Set<const ICFGNode*> SVF::TCT::inRecurJoinSites
protected

Fork or Join sites in recursions.

Definition at line 624 of file TCT.h.

◆ joinSiteToLoopMap

InstToLoopMap SVF::TCT::joinSiteToLoopMap
protected

Map a CxtThread to its start routine function.

map an inloop join to its loop class

Definition at line 623 of file TCT.h.

◆ MaxCxtSize

u32_t SVF::TCT::MaxCxtSize
protected

Definition at line 462 of file TCT.h.

◆ pta

PointerAnalysis* SVF::TCT::pta
protected

Definition at line 458 of file TCT.h.

◆ tcg

ThreadCallGraph* SVF::TCT::tcg
protected

Definition at line 457 of file TCT.h.

◆ tcgSCC

ThreadCallGraphSCC* SVF::TCT::tcgSCC
protected

Procedures we care about during call graph traversing when creating TCT.

Definition at line 617 of file TCT.h.

◆ TCTEdgeNum

u32_t SVF::TCT::TCTEdgeNum
protected

Definition at line 461 of file TCT.h.

◆ TCTNodeNum

u32_t SVF::TCT::TCTNodeNum
protected

Definition at line 460 of file TCT.h.

◆ visitedCTPs

CxtThreadProcSet SVF::TCT::visitedCTPs
protected

CxtThreadProc List.

Definition at line 619 of file TCT.h.


The documentation for this class was generated from the following files: