#include <MTASlicer.h>

Inheritance diagram for SVF::SlicedTCT:

Public Member Functions
	~SlicedTCT () override=default

Public Member Functions inherited from SVF::TCT
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< 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 ()

Static Public Member Functions
static std::unique_ptr< SlicedTCT >	create (PointerAnalysis &pointerAnalysis, const SlicedSVFIRView &slicedView, u32_t contextLimit)

Static Public Member Functions inherited from SVF::TCT
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
void	build () override
	Build TCT.

void	markRelProcs () override
	Mark relevant procedures that are backward reachable from any fork/join site.

void	markRelProcs (const FunObjVar *fun) override

void	collectLoopInfoForJoin () override
	Handle join site in loop.

void	handleCallRelation (CxtThreadProc &ctp, const CallGraphEdge cgEdge, const CallICFGNode cs) override
	Handle call relations.

Protected Member Functions inherited from SVF::TCT
	TCT (PointerAnalysis *p, u32_t contextLimit)

TCTNode *	addTCTNode (const CxtThread &ct)
	Add TCT node.

bool	addTCTEdge (TCTNode src, TCTNode dst)
	Add TCT edge.

void	collectMultiForkedThreads ()

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.

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

Private Member Functions
	SlicedTCT (PointerAnalysis &pointerAnalysis, const SlicedSVFIRView &slicedView, u32_t contextLimit)

void	collectEntryFunInCallGraph () override
	Get entry functions that are neither called by other functions nor extern functions.

bool	isKeptNode (const CallGraphNode *node) const

bool	isKeptEdge (const CallGraphEdge *edge) const

void	getKeptForkSites (std::vector< const ICFGNode * > &out) const

void	getKeptJoinSites (std::vector< const ICFGNode * > &out) const

Private Attributes
const SlicedThreadCallGraphView &	tcgView

Additional Inherited Members
Public Types inherited from SVF::TCT
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< 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 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::TCT
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< NodeTy, EdgeTy >
IDToNodeMapTy	IDToNodeMap
	node map

Detailed Description

Definition at line 82 of file MTASlicer.h.

Constructor & Destructor Documentation

◆ ~SlicedTCT()

SVF::SlicedTCT::~SlicedTCT ( )

overridedefault

◆ SlicedTCT()

SVF::SlicedTCT::SlicedTCT	(	PointerAnalysis &	pointerAnalysis,
		const SlicedSVFIRView &	slicedView,
		u32_t	contextLimit
	)

private

Definition at line 66 of file MTASlicer.cpp.

    : TCT(&pointerAnalysis, contextLimit),
      tcgView(*slicedView.getThreadCallGraph())
{
}

Member Function Documentation

◆ build()

void SVF::SlicedTCT::build ( )

overrideprotectedvirtual

Build TCT.

Start building TCT

Reimplemented from SVF::TCT.

Definition at line 73 of file MTASlicer.cpp.

{
    markRelProcs();
    collectLoopInfoForJoin();
    collectEntryFunInCallGraph();
 
    for (const FunObjVar* entry : entryFuncSet)
    {
        if (!isCandidateFun(entry))
            continue;
        CallStrCxt context;
        CxtThreadProc parent(-1, context, nullptr);
        TCTNode* root = getOrCreateTCTNode(
                            context, createDummyForkSite(), parent, entry);
        pushToCTPWorkList(CxtThreadProc(root->getId(), context, entry));
    }
 
    while (!ctpList.empty())
    {
        CxtThreadProc process = popFromCTPWorkList();
        CallGraphNode* node = tcg->getCallGraphNode(process.getProc());
        if (!isCandidateFun(node->getFunction()) || !isKeptNode(node))
            continue;
 
        std::vector<const CallGraphEdge*> outEdges;
        tcgView.getOutEdgesOf(node, outEdges);
        for (const CallGraphEdge* edge : outEdges)
        {
            std::vector<const CallICFGNode*> directCalls;
            std::vector<const CallICFGNode*> indirectCalls;
            tcgView.getDirectCallsOf(edge, directCalls);
            tcgView.getIndirectCallsOf(edge, indirectCalls);
            for (const CallICFGNode* call : directCalls)
                handleCallRelation(process, edge, call);
            for (const CallICFGNode* call : indirectCalls)
                handleCallRelation(process, edge, call);
        }
    }
 
    collectMultiForkedThreads();
 
    if (Options::TCTDotGraph())
    {
        print();
        dump("tct");
    }
}

◆ collectEntryFunInCallGraph()

void SVF::SlicedTCT::collectEntryFunInCallGraph ( )

overrideprivatevirtual

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 from SVF::TCT.

Definition at line 209 of file MTASlicer.cpp.

{
    // A removed caller must not turn its callee into a new program root.
    // Start only from original roots that remain in the sliced view.
    const OrderedSet<const CallGraphNode*>& keptNodes = tcgView.getKeptNodes();
 
    for (const CallGraphNode* node : keptNodes)
    {
        const FunObjVar* fun = node->getFunction();
        if (SVFUtil::isExtCall(fun))
            continue;
 
        if (!node->hasIncomingEdge())
        {
            entryFuncSet.insert(fun);
        }
    }
 
    assert(!getEntryProcs().empty() && "Can't find any function in module!");
}

◆ collectLoopInfoForJoin()

void SVF::SlicedTCT::collectLoopInfoForJoin ( )

overrideprotectedvirtual

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 from SVF::TCT.

Definition at line 182 of file MTASlicer.cpp.

{
    // Get kept join sites from sliced view
    std::vector<const ICFGNode*> keptJoinSites;
    getKeptJoinSites(keptJoinSites);
 
    for(const ICFGNode* join : keptJoinSites)
    {
        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);
        }
    }
}

◆ create()

std::unique_ptr< SlicedTCT > SVF::SlicedTCT::create	(	PointerAnalysis &	pointerAnalysis,
		const SlicedSVFIRView &	slicedView,
		u32_t	contextLimit
	)

static

Parameters

pointerAnalysis	the shared Andersen pre-analysis
slicedView	SlicedSVFIRView containing a SlicedThreadCallGraphView
contextLimit	maximum context length for the main analysis

Definition at line 56 of file MTASlicer.cpp.

{
    std::unique_ptr<SlicedTCT> tct(
        new SlicedTCT(pointerAnalysis, slicedView, contextLimit));
    tct->build();
    return tct;
}

◆ getKeptForkSites()

void SVF::SlicedTCT::getKeptForkSites ( std::vector< const ICFGNode * > & out ) const

private

Definition at line 254 of file MTASlicer.cpp.

{
    out.clear();
    // Get all fork sites from original ThreadCallGraph, but filter by:
    // 1. The function containing the fork site is kept
    // 2. There exists a kept fork edge from this fork site
    for (ThreadCallGraph::CallSiteSet::const_iterator it = tcg->forksitesBegin(), eit = tcg->forksitesEnd(); it != eit; ++it)
    {
        const ICFGNode* forkSite = *it;
        const CallICFGNode* callNode = SVFUtil::dyn_cast<CallICFGNode>(forkSite);
        if (callNode == nullptr)
            continue;
 
        std::vector<const CallGraphEdge*> forkEdges;
        GenericGraphTraits<const SlicedThreadCallGraphView*>::getForkEdges(
            &tcgView, callNode, forkEdges);
        if (!forkEdges.empty())
            out.push_back(forkSite);
    }
}

◆ getKeptJoinSites()

void SVF::SlicedTCT::getKeptJoinSites ( std::vector< const ICFGNode * > & out ) const

private

Definition at line 275 of file MTASlicer.cpp.

{
    out.clear();
    // Get all join sites from original ThreadCallGraph, but filter by:
    // 1. The function containing the join site is kept
    // 2. There exists a kept join edge to this join site
    for (ThreadCallGraph::CallSiteSet::const_iterator it = tcg->joinsitesBegin(), eit = tcg->joinsitesEnd(); it != eit; ++it)
    {
        const ICFGNode* joinSite = *it;
        const CallICFGNode* callNode = SVFUtil::dyn_cast<CallICFGNode>(joinSite);
        if (callNode == nullptr)
            continue;
 
        std::vector<const CallGraphEdge*> joinEdges;
        GenericGraphTraits<const SlicedThreadCallGraphView*>::getJoinEdges(
            &tcgView, callNode, joinEdges);
        if (!joinEdges.empty())
            out.push_back(joinSite);
    }
}

◆ handleCallRelation()

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

overrideprotectedvirtual

Handle call relations.

Handle call relations

handle calling context for candidate functions only

Create spawnee TCT node

Add TCT nodes and edge

Reimplemented from SVF::TCT.

Definition at line 230 of file MTASlicer.cpp.

{
    // Check if the call site and callee are kept in sliced view
    if (!isKeptEdge(cgEdge))
        return;
 
    const CallGraphNode* dstNode = cgEdge->getDstNode();
    if (!isKeptNode(dstNode))
        return;
 
    // Call base class implementation
    TCT::handleCallRelation(ctp, cgEdge, cs);
}

◆ isKeptEdge()

bool SVF::SlicedTCT::isKeptEdge ( const CallGraphEdge * edge ) const

private

Definition at line 249 of file MTASlicer.cpp.

{
    return tcgView.isKeptEdge(edge);
}

◆ isKeptNode()

bool SVF::SlicedTCT::isKeptNode ( const CallGraphNode * node ) const

private

Definition at line 244 of file MTASlicer.cpp.

{
    return tcgView.isKeptNode(node);
}

◆ markRelProcs() [1/2]

void SVF::SlicedTCT::markRelProcs ( )

overrideprotectedvirtual

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 from SVF::TCT.

Definition at line 121 of file MTASlicer.cpp.

{
    // Get kept fork sites from sliced view
    std::vector<const ICFGNode*> keptForkSites;
    getKeptForkSites(keptForkSites);
 
    for (const ICFGNode* forkSite : keptForkSites)
    {
        // Get function from fork site
        const FunObjVar* svfun = forkSite->getFun();
        markRelProcs(svfun);
 
        const CallICFGNode* callNode = SVFUtil::cast<CallICFGNode>(forkSite);
        std::vector<const CallGraphEdge*> forkEdges;
        GenericGraphTraits<const SlicedThreadCallGraphView*>::getForkEdges(
            &tcgView, callNode, forkEdges);
        for (const CallGraphEdge* edge : forkEdges)
        {
            candidateFuncSet.insert(edge->getDstNode()->getFunction());
        }
    }
 
    // Get kept join sites from sliced view
    std::vector<const ICFGNode*> keptJoinSites;
    getKeptJoinSites(keptJoinSites);
 
    for (const ICFGNode* joinSite : keptJoinSites)
    {
        const FunObjVar* svfun = joinSite->getFun();
        markRelProcs(svfun);
    }
 
    if(getMakredProcs().empty())
        SVFUtil::writeWrnMsg("We didn't recognize any fork site, this is single thread program?");
}

◆ markRelProcs() [2/2]

void SVF::SlicedTCT::markRelProcs ( const FunObjVar * svffun )

overrideprotectedvirtual

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

Reimplemented from SVF::TCT.

Definition at line 157 of file MTASlicer.cpp.

{
    const CallGraphNode* start = tcg->getCallGraphNode(fun);
    if (!isKeptNode(start))
        return;
 
    FIFOWorkList<const CallGraphNode*> worklist;
    PTACGNodeSet visited;
    worklist.push(start);
    visited.insert(start);
    while (!worklist.empty())
    {
        const CallGraphNode* node = worklist.pop();
        candidateFuncSet.insert(node->getFunction());
        std::vector<const CallGraphEdge*> inEdges;
        tcgView.getInEdgesOf(node, inEdges);
        for (const CallGraphEdge* edge : inEdges)
        {
            const CallGraphNode* caller = edge->getSrcNode();
            if (visited.insert(caller).second)
                worklist.push(caller);
        }
    }
}

Member Data Documentation

◆ tcgView

const SlicedThreadCallGraphView& SVF::SlicedTCT::tcgView

private

Definition at line 107 of file MTASlicer.h.

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

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

Public Member Functions

Static Public Member Functions

Protected Member Functions

Private Member Functions

Private Attributes

Additional Inherited Members

Detailed Description

Constructor & Destructor Documentation

◆ ~SlicedTCT()

◆ SlicedTCT()

Member Function Documentation

◆ build()

◆ collectEntryFunInCallGraph()

◆ collectLoopInfoForJoin()

◆ create()

◆ getKeptForkSites()

◆ getKeptJoinSites()

◆ handleCallRelation()

◆ isKeptEdge()

◆ isKeptNode()

◆ markRelProcs() [1/2]

◆ markRelProcs() [2/2]

Member Data Documentation

◆ tcgView