SVF::TCT Class Reference

#include <TCT.h>

Inheritance diagram for SVF::TCT:

Public Types
typedef SVFLoopAndDomInfo::LoopBBs	LoopBBs
typedef TCTEdge::ThreadCreateEdgeSet	ThreadCreateEdgeSet
typedef ThreadCreateEdgeSet::iterator	TCTNodeIter
typedef Set< const SVFFunction * >	FunSet
typedef std::vector< const ICFGNode * >	InstVec
typedef Set< const ICFGNode * >	InstSet
typedef Set< const PTACallGraphNode * >	PTACGNodeSet
typedef Map< CxtThread, TCTNode * >	CxtThreadToNodeMap
typedef Map< CxtThread, CallStrCxt >	CxtThreadToForkCxt
typedef Map< CxtThread, const SVFFunction * >	CxtThreadToFun
typedef Map< const ICFGNode *, LoopBBs >	InstToLoopMap
typedef FIFOWorkList< CxtThreadProc >	CxtThreadProcVec
typedef Set< CxtThreadProc >	CxtThreadProcSet
typedef SCCDetection< PTACallGraph * >	ThreadCallGraphSCC
Public Types inherited from SVF::GenericGraph< NodeTy, EdgeTy >
typedef NodeTy	NodeType
typedef EdgeTy	EdgeType
typedef OrderedMap< NodeID, NodeType * >	IDToNodeMapTy
	NodeID to GenericNode map. More...
typedef IDToNodeMapTy::iterator	iterator
	Node Iterators. More...
typedef IDToNodeMapTy::const_iterator	const_iterator

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

Private Member Functions
TCTNode *	addTCTNode (const CxtThread &ct)
	Add TCT node. More...
bool	addTCTEdge (TCTNode *src, TCTNode *dst)
	Add TCT edge. More...
void	build ()
	Build TCT. More...
void	markRelProcs ()
	Mark relevant procedures that are backward reachable from any fork/join site. More...
void	markRelProcs (const SVFFunction *fun)
void	collectEntryFunInCallGraph ()
	Get entry functions that are neither called by other functions nor extern functions. More...
void	collectMultiForkedThreads ()
void	collectLoopInfoForJoin ()
	Handle join site in loop. More...
bool	isLoopHeaderOfJoinLoop (const SVFBasicBlock *bb)
	Whether a given bb is a loop head of a inloop join site. More...
bool	isLoopExitOfJoinLoop (const SVFBasicBlock *bb)
	Whether a given bb is an exit of a inloop join site. More...
bool	isInLoopInstruction (const ICFGNode *inst)
	Multi-forked threads. More...
bool	isInRecursion (const ICFGNode *inst) const
	Whether an instruction is in a recursion. More...
void	handleCallRelation (CxtThreadProc &ctp, const PTACallGraphEdge *cgEdge, const CallICFGNode *call)
	Handle call relations. More...
TCTNode *	getOrCreateTCTNode (const CallStrCxt &cxt, const ICFGNode *fork, const CallStrCxt &oldCxt, const SVFFunction *routine)
	Get or create a tct node based on CxtThread. More...
void	setMultiForkedAttrs (CxtThread &ct)
	Set multi-forked thread attributes. More...
void	addCxtOfCxtThread (const CallStrCxt &cxt, const CxtThread &ct)
	Add context for a thread at its spawning site (fork site) More...
void	addStartRoutineOfCxtThread (const SVFFunction *fun, const CxtThread &ct)
	Add start routine function of a cxt thread. More...
bool	pushToCTPWorkList (const CxtThreadProc &ctp)
	WorkList helper functions. More...
CxtThreadProc	popFromCTPWorkList ()
bool	isVisitedCTPs (const CxtThreadProc &ctp) const
void	destroy ()
	Clean up memory. More...

Private Attributes
ThreadCallGraph *	tcg
PointerAnalysis *	pta
u32_t	TCTNodeNum
u32_t	TCTEdgeNum
u32_t	MaxCxtSize
FunSet	entryFuncSet
FunSet	candidateFuncSet
	Procedures that are neither called by other functions nor extern functions. More...
ThreadCallGraphSCC *	tcgSCC
	Procedures we care about during call graph traversing when creating TCT. More...
CxtThreadProcVec	ctpList
	Thread call graph SCC. More...
CxtThreadProcSet	visitedCTPs
	CxtThreadProc List. More...
CxtThreadToNodeMap	ctpToNodeMap
	Record all visited ctps. More...
CxtThreadToForkCxt	ctToForkCxtMap
	Map a ctp to its graph node. More...
CxtThreadToFun	ctToRoutineFunMap
	Map a CxtThread to the context at its spawning site (fork site). More...
InstToLoopMap	joinSiteToLoopMap
	Map a CxtThread to its start routine function. More...
Set< const ICFGNode * >	inRecurJoinSites
	Fork or Join sites in recursions. More...

Additional Inherited Members
Public Attributes inherited from SVF::GenericGraph< NodeTy, EdgeTy >
u32_t	edgeNum
	total num of node More...
u32_t	nodeNum
	total num of edge More...
Protected Attributes inherited from SVF::GenericGraph< NodeTy, EdgeTy >
IDToNodeMapTy	IDToNodeMap
	node map More...

Detailed Description

Definition at line 153 of file TCT.h.

Member Typedef Documentation

CxtThreadProcSet

typedef Set<CxtThreadProc> SVF::TCT::CxtThreadProcSet

Definition at line 169 of file TCT.h.

CxtThreadProcVec

typedef FIFOWorkList<CxtThreadProc> SVF::TCT::CxtThreadProcVec

Definition at line 168 of file TCT.h.

CxtThreadToForkCxt

typedef Map<CxtThread,CallStrCxt> SVF::TCT::CxtThreadToForkCxt

Definition at line 165 of file TCT.h.

CxtThreadToFun

typedef Map<CxtThread,const SVFFunction*> SVF::TCT::CxtThreadToFun

Definition at line 166 of file TCT.h.

CxtThreadToNodeMap

typedef Map<CxtThread,TCTNode*> SVF::TCT::CxtThreadToNodeMap

Definition at line 164 of file TCT.h.

FunSet

typedef Set<const SVFFunction*> SVF::TCT::FunSet

Definition at line 160 of file TCT.h.

InstSet

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

Definition at line 162 of file TCT.h.

InstToLoopMap

typedef Map<const ICFGNode*, LoopBBs> SVF::TCT::InstToLoopMap

Definition at line 167 of file TCT.h.

InstVec

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

Definition at line 161 of file TCT.h.

LoopBBs

typedef SVFLoopAndDomInfo::LoopBBs SVF::TCT::LoopBBs

Definition at line 157 of file TCT.h.

PTACGNodeSet

typedef Set<const PTACallGraphNode*> SVF::TCT::PTACGNodeSet

Definition at line 163 of file TCT.h.

TCTNodeIter

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

Definition at line 159 of file TCT.h.

ThreadCallGraphSCC

typedef SCCDetection<PTACallGraph*> SVF::TCT::ThreadCallGraphSCC

Definition at line 170 of file TCT.h.

ThreadCreateEdgeSet

typedef TCTEdge::ThreadCreateEdgeSet SVF::TCT::ThreadCreateEdgeSet

Definition at line 158 of file TCT.h.

Constructor & Destructor Documentation

TCT()

SVF::TCT::TCT ( PointerAnalysis *  p )

inline

Constructor.

Definition at line 173 of file TCT.h.

                            :pta(p),TCTNodeNum(0),TCTEdgeNum(0),MaxCxtSize(0)
    {
        tcg = SVFUtil::cast<ThreadCallGraph>(pta->getCallGraph());
        tcg->updateCallGraph(pta);
        //tcg->updateJoinEdge(pta);
        tcgSCC = pta->getCallGraphSCC();
        tcgSCC->find();
        build();
    }

~TCT()

virtual SVF::TCT::~TCT ( )

inlinevirtual

Destructor.

Definition at line 184 of file TCT.h.

    {
        destroy();
    }

Member Function Documentation

addCxtOfCxtThread()

void SVF::TCT::addCxtOfCxtThread ( const CallStrCxt &  cxt, const CxtThread &  ct  )

inlineprivate

Add context for a thread at its spawning site (fork site)

Definition at line 549 of file TCT.h.

    {
        ctToForkCxtMap[ct] = cxt;
    }

addStartRoutineOfCxtThread()

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

inlineprivate

Add start routine function of a cxt thread.

Definition at line 554 of file TCT.h.

    {
        ctToRoutineFunMap[ct] = fun;
    }

addTCTEdge()

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

inlineprivate

Add TCT edge.

Definition at line 461 of file TCT.h.

    {
        if (!hasGraphEdge(src, dst, TCTEdge::ThreadCreateEdge))
        {
            TCTEdge* edge = new TCTEdge(src, dst, TCTEdge::ThreadCreateEdge);
            dst->addIncomingEdge(edge);
            src->addOutgoingEdge(edge);
            TCTEdgeNum++;
            return true;
        }
        return false;
    }

addTCTNode()

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

inlineprivate

Add TCT node.

Definition at line 450 of file TCT.h.

    {
        assert(ctpToNodeMap.find(ct)==ctpToNodeMap.end() && "Already has this node!!");
        NodeID id = TCTNodeNum;
        TCTNode* node = new TCTNode(id, ct);
        addGNode(id, node);
        TCTNodeNum++;
        ctpToNodeMap[ct] = node;
        return node;
    }

build()

void TCT::build ( )

private

Build TCT.

Start building TCT

Definition at line 383 of file TCT.cpp.

{
 
    markRelProcs();
 
    collectLoopInfoForJoin();
 
    // the fork site of main function is initialized with nullptr.
    // the context of main is initialized with empty
    // start routine is empty
 
    collectEntryFunInCallGraph();
    for (FunSet::iterator it=entryFuncSet.begin(), eit=entryFuncSet.end(); it!=eit; ++it)
    {
        if (!isCandidateFun(*it))
            continue;
        CallStrCxt cxt;
        TCTNode* mainTCTNode = getOrCreateTCTNode(cxt, nullptr, cxt, *it);
        CxtThreadProc t(mainTCTNode->getId(), cxt, *it);
        pushToCTPWorkList(t);
    }
 
    while(!ctpList.empty())
    {
        CxtThreadProc ctp = popFromCTPWorkList();
        PTACallGraphNode* cgNode = tcg->getCallGraphNode(ctp.getProc());
        if(isCandidateFun(cgNode->getFunction()) == false)
            continue;
 
        for(PTACallGraphNode::const_iterator nit = cgNode->OutEdgeBegin(), neit = cgNode->OutEdgeEnd(); nit!=neit; nit++)
        {
            const PTACallGraphEdge* cgEdge = (*nit);
 
            for(PTACallGraphEdge::CallInstSet::const_iterator cit = cgEdge->directCallsBegin(),
                    ecit = cgEdge->directCallsEnd(); cit!=ecit; ++cit)
            {
                DBOUT(DMTA,outs() << "\nTCT handling direct call:" << **cit << "\t" << cgEdge->getSrcNode()->getFunction()->getName() << "-->" << cgEdge->getDstNode()->getFunction()->getName() << "\n");
                handleCallRelation(ctp,cgEdge,*cit);
            }
            for(PTACallGraphEdge::CallInstSet::const_iterator ind = cgEdge->indirectCallsBegin(),
                    eind = cgEdge->indirectCallsEnd(); ind!=eind; ++ind)
            {
                DBOUT(DMTA,outs() << "\nTCT handling indirect call:" << **ind << "\t" << cgEdge->getSrcNode()->getFunction()->getName() << "-->" << cgEdge->getDstNode()->getFunction()->getName() << "\n");
                handleCallRelation(ctp,cgEdge,*ind);
            }
        }
    }
 
    collectMultiForkedThreads();
 
    if (Options::TCTDotGraph())
    {
        print();
        dump("tct");
    }
 
}

collectEntryFunInCallGraph()

void TCT::collectEntryFunInCallGraph ( )

private

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

Get Main function

Definition at line 186 of file TCT.cpp.

{
    PTACallGraph* svfirCallGraph = PAG::getPAG()->getCallGraph();
    for (const auto& item: *svfirCallGraph)
    {
        const SVFFunction* fun = item.second->getFunction();
        if (SVFUtil::isExtCall(fun))
            continue;
        PTACallGraphNode* node = tcg->getCallGraphNode(fun);
        if (!node->hasIncomingEdge())
        {
            entryFuncSet.insert(fun);
        }
    }
    assert(!entryFuncSet.empty() && "Can't find any function in module!");
}

collectLoopInfoForJoin()

void TCT::collectLoopInfoForJoin ( )

private

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

Definition at line 314 of file TCT.cpp.

{
    for(ThreadCallGraph::CallSiteSet::const_iterator it = tcg->joinsitesBegin(), eit = tcg->joinsitesEnd(); it!=eit; ++it)
    {
        const ICFGNode* join = *it;
        const SVFFunction* svffun = join->getFun();
        const SVFBasicBlock* svfbb = join->getBB();
 
        if(svffun->hasLoopInfo(svfbb))
        {
            const LoopBBs& lp = svffun->getLoopInfo(svfbb);
            if(!lp.empty() && isJoinMustExecutedInLoop(lp,join))
            {
                joinSiteToLoopMap[join] = lp;
            }
        }
 
        if(isInRecursion(join))
            inRecurJoinSites.insert(join);
    }
}

collectMultiForkedThreads()

void TCT::collectMultiForkedThreads ( )

private

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 206 of file TCT.cpp.

{
    if (this->nodeNum == 0 )
        return;
 
    FIFOWorkList<TCTNode*> worklist;
    worklist.push(getTCTNode(0));
 
    while(!worklist.empty())
    {
        TCTNode* node = worklist.pop();
        const CxtThread &ct = node->getCxtThread();
 
        if(ct.isIncycle() || ct.isInloop())
        {
            node->setMultiforked(true);
        }
        else
        {
            for (TCT::ThreadCreateEdgeSet::const_iterator it = node->getInEdges().begin(), eit = node->getInEdges().end(); it != eit;
                    ++it)
            {
                if ((*it)->getSrcNode()->isMultiforked())
                    node->setMultiforked(true);
            }
        }
        for (TCT::ThreadCreateEdgeSet::const_iterator it = node->getOutEdges().begin(), eit = node->getOutEdges().end(); it != eit;
                ++it)
        {
            worklist.push((*it)->getDstNode());
        }
    }
}

destroy()

void SVF::TCT::destroy ( )

inlineprivate

Clean up memory.

Definition at line 581 of file TCT.h.

    {
        if(tcgSCC)
            delete tcgSCC;
        tcgSCC=nullptr;
    }

dump()

void TCT::dump

(

const std::string &

filename

)

Dump the graph.

Dump call graph into dot file

Definition at line 513 of file TCT.cpp.

{
    if (Options::TCTDotGraph())
        GraphPrinter::WriteGraphToFile(outs(), filename, this);
}

dumpCxt()

void TCT::dumpCxt

(

CallStrCxt &

cxt

)

Dump calling context.

Dump calling context information

Definition at line 495 of file TCT.cpp.

{
    std::string str;
    std::stringstream rawstr(str);
    rawstr << "[:";
    for(CallStrCxt::const_iterator it = cxt.begin(), eit = cxt.end(); it!=eit; ++it)
    {
        rawstr << " ' "<< *it << " ' ";
        rawstr << (tcg->getCallSite(*it))->valueOnlyToString();
        rawstr << "  call  " << tcg->getCallSite(*it)->getCaller()->getName() << "-->" << tcg->getCalleeOfCallSite(*it)->getName() << ", \n";
    }
    rawstr << " ]";
    outs() << "max cxt = " << cxt.size() << rawstr.str() << "\n";
}

getAncestorThread()

const NodeBS SVF::TCT::getAncestorThread ( NodeID  tid ) const

inline

Get all ancestor threads.

Definition at line 329 of file TCT.h.

    {
        NodeBS tds;
        if(hasParentThread(tid) == false)
            return tds;
 
        FIFOWorkList<NodeID> worklist;
        worklist.push(getParentThread(tid));
 
        while(!worklist.empty())
        {
            NodeID t = worklist.pop();
            if(tds.test_and_set(t))
            {
                if(hasParentThread(t))
                    worklist.push(getParentThread(t));
            }
        }
        return tds;
    }

getChildrenBegin()

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

inline

Get children and parent nodes.

Definition at line 217 of file TCT.h.

    {
        return node->OutEdgeBegin();
    }

getChildrenEnd()

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

inline

Definition at line 221 of file TCT.h.

    {
        return node->OutEdgeEnd();
    }

getCxtOfCxtThread()

const CallStrCxt& SVF::TCT::getCxtOfCxtThread ( const CxtThread &  ct ) const

inline

get the context of a thread at its spawning site (fork site)

Definition at line 369 of file TCT.h.

    {
        CxtThreadToForkCxt::const_iterator it = ctToForkCxtMap.find(ct);
        assert(it!=ctToForkCxtMap.end() && "Cxt Thread not found!!");
        return it->second;
    }

getEntryProcs()

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

inline

Get marked candidate functions.

Definition at line 242 of file TCT.h.

    {
        return entryFuncSet;
    }

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 551 of file TCT.cpp.

{
    for (TCTEdge::ThreadCreateEdgeSet::const_iterator iter = src->OutEdgeBegin(); iter != src->OutEdgeEnd(); ++iter)
    {
        TCTEdge* edge = (*iter);
        if (edge->getEdgeKind() == kind && edge->getDstID() == dst->getId())
            return edge;
    }
    return nullptr;
}

getJoinLoop()

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

inline

Get loop for join site.

Definition at line 385 of file TCT.h.

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

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 374 of file TCT.cpp.

{
    const SVFFunction* fun = bb->getParent();
    return fun->getLoopInfo(bb);
}

getMakredProcs()

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

inline

Get marked candidate functions.

Definition at line 236 of file TCT.h.

    {
        return candidateFuncSet;
    }

getMaxCxtSize()

u32_t SVF::TCT::getMaxCxtSize ( ) const

inline

Definition at line 257 of file TCT.h.

    {
        return MaxCxtSize;
    }

getOrCreateTCTNode()

TCTNode* SVF::TCT::getOrCreateTCTNode ( const CallStrCxt &  cxt, const ICFGNode *  fork, const CallStrCxt &  oldCxt, const SVFFunction *  routine  )

inlineprivate

Get or create a tct node based on CxtThread.

Definition at line 513 of file TCT.h.

    {
        CxtThread ct(cxt,fork);
        CxtThreadToNodeMap::const_iterator it = ctpToNodeMap.find(ct);
        if(it!=ctpToNodeMap.end())
        {
            return it->second;
        }
 
        addCxtOfCxtThread(oldCxt,ct);
        addStartRoutineOfCxtThread(routine,ct);
 
        setMultiForkedAttrs(ct);
        return addTCTNode(ct);
    }

getParentsBegin()

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

inline

Definition at line 225 of file TCT.h.

    {
        return node->InEdgeBegin();
    }

getParentsEnd()

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

inline

Definition at line 229 of file TCT.h.

    {
        return node->InEdgeEnd();
    }

getParentThread()

NodeID SVF::TCT::getParentThread ( NodeID  tid ) const

inline

Get parent thread.

Definition at line 320 of file TCT.h.

    {
        const TCTNode* node = getTCTNode(tid);
        assert(node->getInEdges().size()<=1 && "should have at most one parent thread");
        assert(node->getInEdges().size()==1 && "does not have a parent thread");
        const TCTEdge* edge = *(node->getInEdges().begin());
        return edge->getSrcID();
    }

getPTA()

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

inline

Get PTA.

Definition at line 201 of file TCT.h.

    {
        return pta;
    }

getSiblingThread()

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

inline

Get sibling threads.

Definition at line 350 of file TCT.h.

    {
        NodeBS tds;
        if(hasParentThread(tid) == false)
            return tds;
 
        const TCTNode* node = getTCTNode(getParentThread(tid));
        for(ThreadCreateEdgeSet::const_iterator it = getChildrenBegin(node), eit = getChildrenEnd(node); it!=eit; ++it)
        {
            NodeID child = (*it)->getDstNode()->getId();
            if(child!=tid)
                tds.set(child);
        }
 
        return tds;
    }

getStartRoutineOfCxtThread()

const SVFFunction* SVF::TCT::getStartRoutineOfCxtThread ( const CxtThread &  ct ) const

inline

get the start routine function of a thread

Definition at line 377 of file TCT.h.

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

getSVFModule()

SVFModule* SVF::TCT::getSVFModule ( ) const

inline

Get SVFFModule.

Definition at line 190 of file TCT.h.

    {
        return pta->getModule();
    }

getTCTEdgeNum()

u32_t SVF::TCT::getTCTEdgeNum ( ) const

inline

Definition at line 253 of file TCT.h.

    {
        return TCTEdgeNum;
    }

getTCTNode() [1/2]

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

inline

Definition at line 282 of file TCT.h.

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

getTCTNode() [2/2]

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

inline

Get TCT node.

Definition at line 206 of file TCT.h.

    {
        return getGNode(id);
    }

getTCTNodeNum()

u32_t SVF::TCT::getTCTNodeNum ( ) const

inline

Get Statistics.

Definition at line 249 of file TCT.h.

    {
        return TCTNodeNum;
    }

getThreadCallGraph()

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

inline

Get TCG.

Definition at line 196 of file TCT.h.

    {
        return tcg;
    }

handleCallRelation()

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

private

Handle call relations.

Handle call relations

Create spawnee TCT node

Add TCT nodes and edge

Definition at line 244 of file TCT.cpp.

{
    const SVFFunction* callee = cgEdge->getDstNode()->getFunction();
 
    CallStrCxt cxt(ctp.getContext());
    CallStrCxt oldCxt = cxt;
    const CallICFGNode* callNode = cs;
    pushCxt(cxt,callNode,callee);
 
    if(cgEdge->getEdgeKind() == PTACallGraphEdge::CallRetEdge)
    {
        CxtThreadProc newctp(ctp.getTid(),cxt,callee);
        if(pushToCTPWorkList(newctp))
        {
            DBOUT(DMTA,outs() << "TCT Process CallRet old ctp --"; ctp.dump());
            DBOUT(DMTA,outs() << "TCT Process CallRet new ctp --"; newctp.dump());
        }
    }
 
    else if(cgEdge->getEdgeKind() == PTACallGraphEdge::TDForkEdge)
    {
        TCTNode* spawneeNode = getOrCreateTCTNode(cxt,callNode, oldCxt, callee);
        CxtThreadProc newctp(spawneeNode->getId(),cxt,callee);
 
        if(pushToCTPWorkList(newctp))
        {
            if(addTCTEdge(this->getGNode(ctp.getTid()), spawneeNode))
            {
                DBOUT(DMTA,outs() << "Add TCT Edge from thread " << ctp.getTid() << "  ";
                      this->getGNode(ctp.getTid())->getCxtThread().dump();
                      outs() << " to thread " << spawneeNode->getId() << "  ";
                      spawneeNode->getCxtThread().dump();
                      outs() << "\n" );
            }
            DBOUT(DMTA,outs() << "TCT Process Fork old ctp --"; ctp.dump());
            DBOUT(DMTA,outs() << "TCT Process Fork new ctp --"; newctp.dump());
        }
    }
}

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 534 of file TCT.cpp.

{
    TCTEdge edge(src, dst, kind);
    TCTEdge* outEdge = src->hasOutgoingEdge(&edge);
    TCTEdge* inEdge = dst->hasIncomingEdge(&edge);
    if (outEdge && inEdge)
    {
        assert(outEdge == inEdge && "edges not match");
        return outEdge;
    }
    else
        return nullptr;
}

hasJoinLoop()

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

inline

Definition at line 393 of file TCT.h.

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

hasLoop() [1/2]

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

inline

Definition at line 405 of file TCT.h.

    {
        return hasLoop(inst->getBB());
    }

hasLoop() [2/2]

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

inline

Definition at line 400 of file TCT.h.

    {
        const SVFFunction* fun = bb->getFunction();
        return fun->hasLoopInfo(bb);
    }

hasParentThread()

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

inline

Get parent and sibling threads.

Has parent thread

Definition at line 314 of file TCT.h.

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

hasTCTNode()

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

inline

Find/Get TCT node.

Definition at line 278 of file TCT.h.

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

inSameCallGraphSCC()

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

inline

Whether two functions in the same callgraph scc.

Definition at line 306 of file TCT.h.

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

isCallSite()

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

inline

Whether it is a callsite.

Definition at line 271 of file TCT.h.

    {
        return SVFUtil::isa<CallICFGNode>(inst);
    }

isCandidateFun() [1/2]

bool SVF::TCT::isCandidateFun ( const PTACallGraph::FunctionSet &  callees ) const

inline

Whether it is a candidate function for indirect call.

Definition at line 291 of file TCT.h.

    {
        for(PTACallGraph::FunctionSet::const_iterator cit = callees.begin(),
                ecit = callees.end(); cit!=ecit; cit++)
        {
            if(candidateFuncSet.find((*cit))!=candidateFuncSet.end())
                return true;
        }
        return false;
    }

isCandidateFun() [2/2]

bool SVF::TCT::isCandidateFun ( const SVFFunction *  fun ) const

inline

Definition at line 301 of file TCT.h.

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

isExtCall()

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

inline

Whether it is calling an external function.

Definition at line 264 of file TCT.h.

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

isInLoopInstruction()

bool TCT::isInLoopInstruction ( const ICFGNode *  inst )

private

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 45 of file TCT.cpp.

{
    assert(inst && "null value instruction!!");
 
    Set<const ICFGNode*> insts;
    FIFOWorkList<const ICFGNode*> worklist;
    worklist.push(inst);
 
    while(!worklist.empty())
    {
        const ICFGNode* inst = worklist.pop();
        insts.insert(inst);
        PTACallGraphNode* cgnode = tcg->getCallGraphNode(inst->getFun());
        for(PTACallGraphNode::const_iterator nit = cgnode->InEdgeBegin(), neit = cgnode->InEdgeEnd(); nit!=neit; nit++)
        {
            for(PTACallGraphEdge::CallInstSet::const_iterator cit = (*nit)->directCallsBegin(),
                    ecit = (*nit)->directCallsEnd(); cit!=ecit; ++cit)
            {
                if(insts.insert(*cit).second)
                    worklist.push(*cit);
            }
            for(PTACallGraphEdge::CallInstSet::const_iterator cit = (*nit)->indirectCallsBegin(),
                    ecit = (*nit)->indirectCallsEnd(); cit!=ecit; ++cit)
            {
                if(insts.insert(*cit).second)
                    worklist.push(*cit);
            }
        }
    }
 
    for(const ICFGNode* i : insts)
    {
        if(i->getFun()->hasLoopInfo(i->getBB()))
            return true;
    }
 
 
    return false;
}

isInRecursion()

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

private

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 90 of file TCT.cpp.

{
    const SVFFunction* f = inst->getFun();
    FIFOWorkList<const SVFFunction*> worklist;
    Set<const SVFFunction*> visits;
    worklist.push(f);
 
    while(!worklist.empty())
    {
        const SVFFunction* svffun = worklist.pop();
        visits.insert(svffun);
        if(tcgSCC->isInCycle(tcg->getCallGraphNode(svffun)->getId()))
            return true;
 
        const PTACallGraphNode* cgnode = tcg->getCallGraphNode(svffun);
 
        for(PTACallGraphNode::const_iterator nit = cgnode->InEdgeBegin(), neit = cgnode->InEdgeEnd(); nit!=neit; nit++)
        {
            for(PTACallGraphEdge::CallInstSet::const_iterator cit = (*nit)->directCallsBegin(),
                    ecit = (*nit)->directCallsEnd(); cit!=ecit; ++cit)
            {
                const SVFFunction* caller = (*cit)->getFun();
                if(visits.find(caller)==visits.end())
                    worklist.push(caller);
            }
            for(PTACallGraphEdge::CallInstSet::const_iterator cit = (*nit)->indirectCallsBegin(),
                    ecit = (*nit)->indirectCallsEnd(); cit!=ecit; ++cit)
            {
                const SVFFunction* caller = (*cit)->getFun();
                if(visits.find(caller)==visits.end())
                    worklist.push(caller);
            }
        }
    }
 
    return false;
 
}

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 290 of file TCT.cpp.

{
    assert(!lp.empty() && "this is not a loop, empty basic block");
    const SVFFunction* svffun = join->getFun();
    const SVFBasicBlock* loopheadbb = svffun->getLoopHeader(lp);
    const SVFBasicBlock* joinbb = join->getBB();
    assert(loopheadbb->getParent()==joinbb->getParent() && "should inside same function");
 
    for (const SVFBasicBlock* svf_scc_bb : loopheadbb->getSuccessors())
    {
        if(svffun->loopContainsBB(lp,svf_scc_bb))
        {
            if(svffun->dominate(joinbb,svf_scc_bb)==false)
                return false;
        }
    }
 
    return true;
}

isJoinSiteInRecursion()

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

inline

Whether a join site is in recursion.

Definition at line 428 of file TCT.h.

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

isLoopExitOfJoinLoop()

bool TCT::isLoopExitOfJoinLoop ( const SVFBasicBlock *  bb )

private

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 353 of file TCT.cpp.

{
    for(InstToLoopMap::const_iterator it = joinSiteToLoopMap.begin(), eit = joinSiteToLoopMap.end(); it!=eit; ++it)
    {
        std::vector<const SVFBasicBlock*> exitbbs;
        it->first->getFun()->getExitBlocksOfLoop(it->first->getBB(),exitbbs);
        while(!exitbbs.empty())
        {
            const SVFBasicBlock* eb = exitbbs.back();
            exitbbs.pop_back();
            if(eb == bb)
                return true;
        }
    }
 
    return false;
}

isLoopHeaderOfJoinLoop()

bool TCT::isLoopHeaderOfJoinLoop ( const SVFBasicBlock *  bb )

private

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 339 of file TCT.cpp.

{
    for(InstToLoopMap::const_iterator it = joinSiteToLoopMap.begin(), eit = joinSiteToLoopMap.end(); it!=eit; ++it)
    {
        if(bb->getParent()->getLoopHeader(it->second) == bb)
            return true;
    }
 
    return false;
}

isVisitedCTPs()

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

inlineprivate

Definition at line 575 of file TCT.h.

    {
        return visitedCTPs.find(ctp)!=visitedCTPs.end();
    }

markRelProcs() [1/2]

void TCT::markRelProcs ( )

private

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

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

Definition at line 132 of file TCT.cpp.

{
    for (ThreadCallGraph::CallSiteSet::const_iterator it = tcg->forksitesBegin(), eit = tcg->forksitesEnd(); it != eit; ++it)
    {
        const SVFFunction* svfun = (*it)->getParent()->getParent();
        markRelProcs(svfun);
 
        for(ThreadCallGraph::ForkEdgeSet::const_iterator nit = tcg->getForkEdgeBegin(*it), neit = tcg->getForkEdgeEnd(*it); nit!=neit; nit++)
        {
            const PTACallGraphNode* forkeeNode = (*nit)->getDstNode();
            candidateFuncSet.insert(forkeeNode->getFunction());
        }
 
    }
 
    for (ThreadCallGraph::CallSiteSet::const_iterator it = tcg->joinsitesBegin(), eit = tcg->joinsitesEnd(); it != eit; ++it)
    {
        const SVFFunction* svfun = (*it)->getParent()->getParent();
        markRelProcs(svfun);
    }
 
    if(candidateFuncSet.empty())
        writeWrnMsg("We didn't recognize any fork site, this is single thread program?");
}

markRelProcs() [2/2]

void TCT::markRelProcs ( const SVFFunction *  fun )

private

Definition at line 160 of file TCT.cpp.

{
    PTACallGraphNode* cgnode = tcg->getCallGraphNode(svffun);
    FIFOWorkList<const PTACallGraphNode*> worklist;
    PTACGNodeSet visited;
    worklist.push(cgnode);
    visited.insert(cgnode);
    while(!worklist.empty())
    {
        const PTACallGraphNode* node = worklist.pop();
        candidateFuncSet.insert(node->getFunction());
        for(PTACallGraphNode::const_iterator nit = node->InEdgeBegin(), neit = node->InEdgeEnd(); nit!=neit; nit++)
        {
            const PTACallGraphNode* srcNode = (*nit)->getSrcNode();
            if(visited.find(srcNode)==visited.end())
            {
                visited.insert(srcNode);
                worklist.push(srcNode);
            }
        }
    }
}

matchCxt()

bool TCT::matchCxt	(	CallStrCxt &	cxt,
		const CallICFGNode *	call,
		const SVFFunction *	callee
	)

Match context.

Match calling context

handle calling context for candidate functions only

partial match

Definition at line 465 of file TCT.cpp.

{
 
    const SVFFunction* caller = call->getFun();
    CallSiteID csId = tcg->getCallSiteID(call, callee);
 
    if(isCandidateFun(caller) == false)
        return true;
 
    if(cxt.empty())
        return true;
 
    if(inSameCallGraphSCC(tcg->getCallGraphNode(caller),tcg->getCallGraphNode(callee))==false)
    {
        if(cxt.back() == csId)
            cxt.pop_back();
        else
            return false;
        DBOUT(DMTA,dumpCxt(cxt));
    }
 
    return true;
}

popFromCTPWorkList()

CxtThreadProc SVF::TCT::popFromCTPWorkList ( )

inlineprivate

Definition at line 570 of file TCT.h.

    {
        CxtThreadProc ctp = ctpList.pop();
        return ctp;
    }

print()

void TCT::print

(

void

)

const

Print TCT information.

Print TCT information

Definition at line 522 of file TCT.cpp.

{
    for(TCT::const_iterator it = this->begin(), eit = this->end(); it!=eit; ++it)
    {
        outs() << "TID " << it->first << "\t";
        it->second->getCxtThread().dump();
    }
}

pushCxt() [1/2]

void SVF::TCT::pushCxt ( CallStrCxt &  cxt, CallSiteID  csId  )

inline

Definition at line 421 of file TCT.h.

    {
        cxt.push_back(csId);
        if (cxt.size() > MaxCxtSize)
            MaxCxtSize = cxt.size();
    }

pushCxt() [2/2]

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

Push calling context.

Push calling context

handle calling context for candidate functions only

Definition at line 444 of file TCT.cpp.

{
 
    const SVFFunction* caller = call->getFun();
    CallSiteID csId = tcg->getCallSiteID(call, callee);
 
    if(isCandidateFun(caller) == false)
        return;
 
    if(inSameCallGraphSCC(tcg->getCallGraphNode(caller),tcg->getCallGraphNode(callee))==false)
    {
        pushCxt(cxt,csId);
        DBOUT(DMTA,dumpCxt(cxt));
    }
}

pushToCTPWorkList()

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

inlineprivate

WorkList helper functions.

Definition at line 561 of file TCT.h.

    {
        if(isVisitedCTPs(ctp)==false)
        {
            visitedCTPs.insert(ctp);
            return ctpList.push(ctp);
        }
        return false;
    }

setMultiForkedAttrs()

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

inlineprivate

Set multi-forked thread attributes.

non-main thread

main thread

Definition at line 531 of file TCT.h.

    {
        if(ct.getThread() != nullptr)
        {
            const ICFGNode* svfInst = ct.getThread();
            ct.setInloop(isInLoopInstruction(svfInst));
            ct.setIncycle(isInRecursion(svfInst));
        }
        else
        {
            ct.setInloop(false);
            ct.setIncycle(false);
        }
    }

Member Data Documentation

candidateFuncSet

FunSet SVF::TCT::candidateFuncSet

private

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

Definition at line 589 of file TCT.h.

ctpList

CxtThreadProcVec SVF::TCT::ctpList

private

Thread call graph SCC.

Definition at line 591 of file TCT.h.

ctpToNodeMap

CxtThreadToNodeMap SVF::TCT::ctpToNodeMap

private

Record all visited ctps.

Definition at line 593 of file TCT.h.

ctToForkCxtMap

CxtThreadToForkCxt SVF::TCT::ctToForkCxtMap

private

Map a ctp to its graph node.

Definition at line 594 of file TCT.h.

ctToRoutineFunMap

CxtThreadToFun SVF::TCT::ctToRoutineFunMap

private

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

Definition at line 595 of file TCT.h.

entryFuncSet

FunSet SVF::TCT::entryFuncSet

private

Definition at line 588 of file TCT.h.

inRecurJoinSites

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

private

Fork or Join sites in recursions.

Definition at line 597 of file TCT.h.

joinSiteToLoopMap

InstToLoopMap SVF::TCT::joinSiteToLoopMap

private

Map a CxtThread to its start routine function.

map an inloop join to its loop class

Definition at line 596 of file TCT.h.

MaxCxtSize

u32_t SVF::TCT::MaxCxtSize

private

Definition at line 447 of file TCT.h.

pta

PointerAnalysis* SVF::TCT::pta

private

Definition at line 444 of file TCT.h.

tcg

ThreadCallGraph* SVF::TCT::tcg

private

Definition at line 443 of file TCT.h.

tcgSCC

ThreadCallGraphSCC* SVF::TCT::tcgSCC

private

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

Definition at line 590 of file TCT.h.

TCTEdgeNum

u32_t SVF::TCT::TCTEdgeNum

private

Definition at line 446 of file TCT.h.

TCTNodeNum

u32_t SVF::TCT::TCTNodeNum

private

Definition at line 445 of file TCT.h.

visitedCTPs

CxtThreadProcSet SVF::TCT::visitedCTPs

private

CxtThreadProc List.

Definition at line 592 of file TCT.h.

---

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

• /home/runner/work/SVF/SVF/svf/include/MTA/TCT.h
• /home/runner/work/SVF/SVF/svf/lib/MTA/TCT.cpp