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 FunObjVar * >	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
Public Types inherited from SVF::GenericGraph< NodeTy, EdgeTy >
typedef NodeTy	NodeType
typedef EdgeTy	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
	TCT (PointerAnalysis *p)
	Constructor.
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.
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< NodeTy, EdgeTy >
	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 ()

Private Member Functions
TCTNode *	addTCTNode (const CxtThread &ct)
	Add TCT node.
bool	addTCTEdge (TCTNode *src, TCTNode *dst)
	Add TCT edge.
void	build ()
	Build TCT.
void	markRelProcs ()
	Mark relevant procedures that are backward reachable from any fork/join site.
void	markRelProcs (const FunObjVar *fun)
void	collectEntryFunInCallGraph ()
	Get entry functions that are neither called by other functions nor extern functions.
void	collectMultiForkedThreads ()
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.
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.
void	addCxtOfCxtThread (NodeID pTid, const CallStrCxt &cxt, const CxtThread &ct)
	Add context for a thread at its spawning site (fork site)
void	addStartRoutineOfCxtThread (const FunObjVar *fun, const CxtThread &ct)
	Add start routine function of a cxt thread.
bool	pushToCTPWorkList (const CxtThreadProc &ctp)
	WorkList helper functions.
CxtThreadProc	popFromCTPWorkList ()
bool	isVisitedCTPs (const CxtThreadProc &ctp) const

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.
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.

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

Detailed Description

Definition at line 155 of file TCT.h.

Member Typedef Documentation

CallStrCxtSet

typedef Set<std::pair<NodeID, CallStrCxt> > SVF::TCT::CallStrCxtSet

Definition at line 167 of file TCT.h.

CxtThreadProcSet

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

Definition at line 172 of file TCT.h.

CxtThreadProcVec

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

Definition at line 171 of file TCT.h.

CxtThreadToForkCxtSet

typedef Map<CxtThread,CallStrCxtSet> SVF::TCT::CxtThreadToForkCxtSet

Definition at line 168 of file TCT.h.

CxtThreadToFun

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

Definition at line 169 of file TCT.h.

CxtThreadToNodeMap

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

Definition at line 166 of file TCT.h.

FunSet

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

Definition at line 162 of file TCT.h.

InstSet

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

Definition at line 164 of file TCT.h.

InstToLoopMap

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

Definition at line 170 of file TCT.h.

InstVec

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

Definition at line 163 of file TCT.h.

LoopBBs

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

Definition at line 159 of file TCT.h.

PTACGNodeSet

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

Definition at line 165 of file TCT.h.

TCTNodeIter

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

Definition at line 161 of file TCT.h.

ThreadCallGraphSCC

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

Definition at line 173 of file TCT.h.

ThreadCreateEdgeSet

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

Definition at line 160 of file TCT.h.

Constructor & Destructor Documentation

TCT()

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

inline

Constructor.

Definition at line 176 of file TCT.h.

                            :pta(p),TCTNodeNum(0),TCTEdgeNum(0),MaxCxtSize(0)
    {
        tcg = SVFUtil::dyn_cast<ThreadCallGraph>(pta->getCallGraph());
        assert(tcg != nullptr && "TCT::TCT: call graph is not a ThreadCallGraph!");
        tcg->updateCallGraph(pta);
        //tcg->updateJoinEdge(pta);
        tcgSCC = pta->getCallGraphSCC();
        tcgSCC->find();
        build();
    }

~TCT()

virtual SVF::TCT::~TCT ( )

inlinevirtual

Destructor.

Definition at line 188 of file TCT.h.

    {  }

Member Function Documentation

addCxtOfCxtThread()

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

inlineprivate

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

Definition at line 552 of file TCT.h.

    {
        ctToForkCxtsMap[ct].insert(std::make_pair(pTid, cxt));
    }

addStartRoutineOfCxtThread()

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

inlineprivate

Add start routine function of a cxt thread.

Definition at line 558 of file TCT.h.

    {
        ctToRoutineFunMap[ct] = fun;
    }

addTCTEdge()

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

inlineprivate

Add TCT edge.

Definition at line 464 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 453 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 387 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;
        CxtThreadProc dummyCtp(-1, cxt, nullptr);
        TCTNode* mainTCTNode = getOrCreateTCTNode(cxt, nullptr, dummyCtp, *it);
        CxtThreadProc t(mainTCTNode->getId(), cxt, *it);
        pushToCTPWorkList(t);
    }
 
    while(!ctpList.empty())
    {
        CxtThreadProc ctp = popFromCTPWorkList();
        CallGraphNode* cgNode = tcg->getCallGraphNode(ctp.getProc());
        if(isCandidateFun(cgNode->getFunction()) == false)
            continue;
 
        for(CallGraphNode::const_iterator nit = cgNode->OutEdgeBegin(), neit = cgNode->OutEdgeEnd(); nit!=neit; nit++)
        {
            const CallGraphEdge* cgEdge = (*nit);
 
            for(CallGraphEdge::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(CallGraphEdge::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 entry function, i.e., functions without callers, e.g., main function

Definition at line 187 of file TCT.cpp.

{
    const CallGraph* svfirCallGraph = PAG::getPAG()->getCallGraph();
    for (const auto& item: *svfirCallGraph)
    {
        const FunObjVar* fun = item.second->getFunction();
        if (SVFUtil::isExtCall(fun))
            continue;
        CallGraphNode* 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 318 of file TCT.cpp.

{
    for(ThreadCallGraph::CallSiteSet::const_iterator it = tcg->joinsitesBegin(), eit = tcg->joinsitesEnd(); it!=eit; ++it)
    {
        const ICFGNode* join = *it;
        const FunObjVar* 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 207 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());
        }
    }
}

dump()

void TCT::dump

(

const std::string &

filename

)

Dump the graph.

Dump call graph into dot file

Definition at line 535 of file TCT.cpp.

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

dumpCxt()

void TCT::dumpCxt

(

CallStrCxt &

cxt

)

Dump calling context.

Dump calling context information

Definition at line 517 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";
}

getAncestorThreads()

const NodeBS SVF::TCT::getAncestorThreads ( 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;
        for(NodeID parentTid : getParentThreads(tid))
            worklist.push(parentTid);
 
        while(!worklist.empty())
        {
            NodeID t = worklist.pop();
            if(tds.test_and_set(t))
            {
                if(hasParentThread(t))
                    for(NodeID parentTid : getParentThreads(t))
                        worklist.push(parentTid);
            }
        }
        return tds;
    }

getChildrenBegin()

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

inline

Get children and parent nodes.

Definition at line 213 of file TCT.h.

    {
        return node->OutEdgeBegin();
    }

getChildrenEnd()

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

inline

Definition at line 217 of file TCT.h.

    {
        return node->OutEdgeEnd();
    }

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 373 of file TCT.h.

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

getEntryProcs()

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

inline

Get marked candidate functions.

Definition at line 238 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 572 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 389 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 378 of file TCT.cpp.

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

getMakredProcs()

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

inline

Get marked candidate functions.

Definition at line 232 of file TCT.h.

    {
        return candidateFuncSet;
    }

getMaxCxtSize()

u32_t SVF::TCT::getMaxCxtSize ( ) const

inline

Definition at line 253 of file TCT.h.

    {
        return MaxCxtSize;
    }

getOrCreateTCTNode()

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

inlineprivate

Get or create a tct node based on CxtThread.

Definition at line 516 of file TCT.h.

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

getParentsBegin()

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

inline

Definition at line 221 of file TCT.h.

    {
        return node->InEdgeBegin();
    }

getParentsEnd()

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

inline

Definition at line 225 of file TCT.h.

    {
        return node->InEdgeEnd();
    }

getParentThreads()

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

inline

Get parent threads.

Definition at line 316 of file TCT.h.

    {
        NodeBS parentTds;
        const TCTNode* node = getTCTNode(tid);
        assert(node->getInEdges().size()>=1 && "does not have a parent thread");
 
        for (const TCTEdge* edge : node->getInEdges())
        {
            parentTds.set(edge->getSrcID());
        }
        return parentTds;
    }

getPTA()

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

inline

Get PTA.

Definition at line 197 of file TCT.h.

    {
        return pta;
    }

getSiblingThread()

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

inline

Get sibling threads.

Definition at line 352 of file TCT.h.

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

getStartRoutineOfCxtThread()

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

inline

get the start routine function of a thread

Definition at line 381 of file TCT.h.

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

getTCTEdgeNum()

u32_t SVF::TCT::getTCTEdgeNum ( ) const

inline

Definition at line 249 of file TCT.h.

    {
        return TCTEdgeNum;
    }

getTCTNode() [1/2]

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

inline

Definition at line 278 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 202 of file TCT.h.

    {
        return getGNode(id);
    }

getTCTNodeNum()

u32_t SVF::TCT::getTCTNodeNum ( ) const

inline

Get Statistics.

Definition at line 245 of file TCT.h.

    {
        return TCTNodeNum;
    }

getThreadCallGraph()

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

inline

Get TCG.

Definition at line 192 of file TCT.h.

    {
        return tcg;
    }

handleCallRelation()

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

private

Handle call relations.

Handle call relations

handle calling context for candidate functions only

Create spawnee TCT node

Add TCT nodes and edge

Definition at line 245 of file TCT.cpp.

{
    const FunObjVar* callee = cgEdge->getDstNode()->getFunction();
 
    CallStrCxt cxt(ctp.getContext());
    CallStrCxt oldCxt = cxt;
    const CallICFGNode* callNode = cs;
 
    if(isCandidateFun(callNode->getFun()) == true)
        pushCxt(cxt,callNode,callee);
 
    if(cgEdge->getEdgeKind() == CallGraphEdge::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() == CallGraphEdge::TDForkEdge)
    {
        TCTNode* spawneeNode = getOrCreateTCTNode(cxt,callNode, ctp, callee);
        CxtThreadProc newctp(spawneeNode->getId(),cxt,callee);
 
        if(pushToCTPWorkList(newctp))
        {
            if(addTCTEdge(this->getTCTNode(ctp.getTid()), spawneeNode))
            {
                DBOUT(DMTA,outs() << "Add TCT Edge from thread " << ctp.getTid() << "  ";
                      this->getTCTNode(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 555 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 397 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 409 of file TCT.h.

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

hasLoop() [2/2]

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

inline

Definition at line 404 of file TCT.h.

    {
        const FunObjVar* 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 310 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 274 of file TCT.h.

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

inSameCallGraphSCC()

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

inline

Whether two functions in the same callgraph scc.

Definition at line 302 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 267 of file TCT.h.

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

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 287 of file TCT.h.

    {
        for(CallGraph::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 FunObjVar *  fun ) const

inline

Definition at line 297 of file TCT.h.

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

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

{
    if (lhs.size() > call.size())
        return false;
    bool isSuffix = true;
    for (size_t i = 0; i < lhs.size(); ++i)
    {
        if (lhs[lhs.size() - 1 - i] != call[call.size() - 1 - i])
        {
            isSuffix = false;
            break;
        }
    }
    return isSuffix;
}

isExtCall()

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

inline

Whether it is calling an external function.

Definition at line 260 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 46 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);
        CallGraphNode* cgnode = tcg->getCallGraphNode(inst->getFun());
        for(CallGraphNode::const_iterator nit = cgnode->InEdgeBegin(), neit = cgnode->InEdgeEnd(); nit!=neit; nit++)
        {
            for(CallGraphEdge::CallInstSet::const_iterator cit = (*nit)->directCallsBegin(),
                    ecit = (*nit)->directCallsEnd(); cit!=ecit; ++cit)
            {
                if(insts.insert(*cit).second)
                    worklist.push(*cit);
            }
            for(CallGraphEdge::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 91 of file TCT.cpp.

{
    const FunObjVar* f = inst->getFun();
    FIFOWorkList<const FunObjVar*> worklist;
    Set<const FunObjVar*> visits;
    worklist.push(f);
 
    while(!worklist.empty())
    {
        const FunObjVar* svffun = worklist.pop();
        visits.insert(svffun);
        if(tcgSCC->isInCycle(tcg->getCallGraphNode(svffun)->getId()))
            return true;
 
        const CallGraphNode* cgnode = tcg->getCallGraphNode(svffun);
 
        for(CallGraphNode::const_iterator nit = cgnode->InEdgeBegin(), neit = cgnode->InEdgeEnd(); nit!=neit; nit++)
        {
            for(CallGraphEdge::CallInstSet::const_iterator cit = (*nit)->directCallsBegin(),
                    ecit = (*nit)->directCallsEnd(); cit!=ecit; ++cit)
            {
                const FunObjVar* caller = (*cit)->getFun();
                if(visits.find(caller)==visits.end())
                    worklist.push(caller);
            }
            for(CallGraphEdge::CallInstSet::const_iterator cit = (*nit)->indirectCallsBegin(),
                    ecit = (*nit)->indirectCallsEnd(); cit!=ecit; ++cit)
            {
                const FunObjVar* 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 294 of file TCT.cpp.

{
    assert(!lp.empty() && "this is not a loop, empty basic block");
    const FunObjVar* 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 431 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 357 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 343 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 579 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 133 of file TCT.cpp.

{
    for (ThreadCallGraph::CallSiteSet::const_iterator it = tcg->forksitesBegin(), eit = tcg->forksitesEnd(); it != eit; ++it)
    {
        const FunObjVar* svfun = (*it)->getParent()->getParent();
        markRelProcs(svfun);
 
        for(ThreadCallGraph::ForkEdgeSet::const_iterator nit = tcg->getForkEdgeBegin(*it), neit = tcg->getForkEdgeEnd(*it); nit!=neit; nit++)
        {
            const CallGraphNode* forkeeNode = (*nit)->getDstNode();
            candidateFuncSet.insert(forkeeNode->getFunction());
        }
 
    }
 
    for (ThreadCallGraph::CallSiteSet::const_iterator it = tcg->joinsitesBegin(), eit = tcg->joinsitesEnd(); it != eit; ++it)
    {
        const FunObjVar* 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 FunObjVar *  svffun )

private

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

Definition at line 161 of file TCT.cpp.

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

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

{
    const FunObjVar* 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 574 of file TCT.h.

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

print()

void TCT::print

(

)

const

Print TCT information.

Print TCT information

Definition at line 543 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()

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

Context helper functions.

Push calling context

Push calling context, with k limiting

Definition at line 449 of file TCT.cpp.

{
    const FunObjVar* caller = call->getFun();
    CallSiteID csId = tcg->getCallSiteID(call, callee);
 
    if(inSameCallGraphSCC(tcg->getCallGraphNode(caller),tcg->getCallGraphNode(callee))==false)
    {
        cxt.push_back(csId);
        if (cxt.size() > Options::MaxContextLen())
            cxt.erase(cxt.begin());
        if (cxt.size() > MaxCxtSize)
            MaxCxtSize = cxt.size();
        DBOUT(DMTA,dumpCxt(cxt));
    }
}

pushToCTPWorkList()

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

inlineprivate

WorkList helper functions.

Definition at line 565 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 534 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 586 of file TCT.h.

ctpList

CxtThreadProcVec SVF::TCT::ctpList

private

Thread call graph SCC.

Definition at line 588 of file TCT.h.

ctpToNodeMap

CxtThreadToNodeMap SVF::TCT::ctpToNodeMap

private

Record all visited ctps.

Definition at line 590 of file TCT.h.

ctToForkCxtsMap

CxtThreadToForkCxtSet SVF::TCT::ctToForkCxtsMap

private

Map a ctp to its graph node.

Definition at line 591 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 592 of file TCT.h.

entryFuncSet

FunSet SVF::TCT::entryFuncSet

private

Definition at line 585 of file TCT.h.

inRecurJoinSites

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

private

Fork or Join sites in recursions.

Definition at line 594 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 593 of file TCT.h.

MaxCxtSize

u32_t SVF::TCT::MaxCxtSize

private

Definition at line 450 of file TCT.h.

pta

PointerAnalysis* SVF::TCT::pta

private

Definition at line 447 of file TCT.h.

tcg

ThreadCallGraph* SVF::TCT::tcg

private

Definition at line 446 of file TCT.h.

tcgSCC

ThreadCallGraphSCC* SVF::TCT::tcgSCC

private

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

Definition at line 587 of file TCT.h.

TCTEdgeNum

u32_t SVF::TCT::TCTEdgeNum

private

Definition at line 449 of file TCT.h.

TCTNodeNum

u32_t SVF::TCT::TCTNodeNum

private

Definition at line 448 of file TCT.h.

visitedCTPs

CxtThreadProcSet SVF::TCT::visitedCTPs

private

CxtThreadProc List.

Definition at line 589 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