TCT.h

Go to the documentation of this file.

//===- TCT.h -- Thread creation tree-------------//
//
//                     SVF: Static Value-Flow Analysis
//
// Copyright (C) <2013->  <Yulei Sui>
//
 
// This program is free software: you can redistribute it and/or modify
// it under the terms of the GNU Affero General Public License as published by
// the Free Software Foundation, either version 3 of the License, or
// (at your option) any later version.
 
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU Affero General Public License for more details.
 
// You should have received a copy of the GNU Affero General Public License
// along with this program.  If not, see <http://www.gnu.org/licenses/>.
//
//===----------------------------------------------------------------------===//
 
/*
 * TCT.h
 *
 *  Created on: Jun 24, 2015
 *      Author: Yulei Sui, Peng Di
 */
 
#ifndef TCTNodeDetector_H_
#define TCTNodeDetector_H_
 
#include "Graphs/SCC.h"
#include "Graphs/ThreadCallGraph.h"
#include "Util/CxtStmt.h"
#include "Util/SVFUtil.h"
#include <set>
#include <vector>
 
namespace SVF
{
 
class TCTNode;
 
 
/*
 * Thread creation edge represents a spawning relation between two context sensitive threads
 */
typedef GenericEdge<TCTNode> GenericTCTEdgeTy;
class TCTEdge: public GenericTCTEdgeTy
{
public:
    enum CEDGEK
    {
        ThreadCreateEdge
    };
    TCTEdge(TCTNode* s, TCTNode* d, CEDGEK kind) :
        GenericTCTEdgeTy(s, d, kind)
    {
    }
    virtual ~TCTEdge()
    {
    }
 
    static inline bool classof(const TCTEdge*)
    {
        return true;
    }
    static inline bool classof(const GenericTCTEdgeTy *edge)
    {
        return edge->getEdgeKind() == TCTEdge::ThreadCreateEdge;
    }
    typedef GenericNode<TCTNode, TCTEdge>::GEdgeSetTy ThreadCreateEdgeSet;
 
};
 
/*
 * Each node represents a context-sensitive thread
 */
typedef GenericNode<TCTNode, TCTEdge> GenericTCTNodeTy;
class TCTNode: public GenericTCTNodeTy
{
 
public:
    TCTNode(NodeID i, const CxtThread& cctx) :
        GenericTCTNodeTy(i, TCTNodeKd), ctx(cctx), multiforked(false)
    {
    }
 
    void dump()
    {
        SVFUtil::outs() << "---\ntid: " << this->getId() << "  inloop:" << ctx.isInloop() << "  incycle:" << ctx.isIncycle() << " multiforked:"<< isMultiforked();
    }
 
    inline const CxtThread& getCxtThread() const
    {
        return ctx;
    }
 
 
    inline bool isInloop() const
    {
        return ctx.isInloop();
    }
    inline bool isIncycle() const
    {
        return ctx.isIncycle();
    }
    inline void setMultiforked(bool value)
    {
        multiforked = value;
    }
    inline bool isMultiforked() const
    {
        return multiforked;
    }
 
 
    static inline bool classof(const TCTNode *)
    {
        return true;
    }
 
    static inline bool classof(const GenericTCTNodeTy *node)
    {
        return node->getNodeKind() == TCTNodeKd;
    }
    static inline bool classof(const SVFBaseNode*node)
    {
        return node->getNodeKind() == TCTNodeKd;
    }
 
 
private:
    const CxtThread ctx;
    bool multiforked;
};
 
typedef GenericGraph<TCTNode, TCTEdge> GenericThreadCreateTreeTy;
class TCT: public GenericThreadCreateTreeTy
{
 
public:
    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;
 
    TCT(PointerAnalysis* p) :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();
    }
 
    virtual ~TCT()
    {
        destroy();
    }
 
    SVFModule* getSVFModule() const
    {
        return pta->getModule();
    }
 
    inline ThreadCallGraph* getThreadCallGraph() const
    {
        return tcg;
    }
    inline PointerAnalysis* getPTA() const
    {
        return pta;
    }
    inline TCTNode* getTCTNode(NodeID id) const
    {
        return getGNode(id);
    }
    TCTEdge* hasGraphEdge(TCTNode* src, TCTNode* dst, TCTEdge::CEDGEK kind) const;
    TCTEdge* getGraphEdge(TCTNode* src, TCTNode* dst, TCTEdge::CEDGEK kind);
 
 
    inline ThreadCreateEdgeSet::const_iterator getChildrenBegin(const TCTNode* node) const
    {
        return node->OutEdgeBegin();
    }
    inline ThreadCreateEdgeSet::const_iterator getChildrenEnd(const TCTNode* node) const
    {
        return node->OutEdgeEnd();
    }
    inline ThreadCreateEdgeSet::const_iterator getParentsBegin(const TCTNode* node) const
    {
        return node->InEdgeBegin();
    }
    inline ThreadCreateEdgeSet::const_iterator getParentsEnd(const TCTNode* node) const
    {
        return node->InEdgeEnd();
    }
 
    inline const FunSet& getMakredProcs() const
    {
        return candidateFuncSet;
    }
 
    inline const FunSet& getEntryProcs() const
    {
        return entryFuncSet;
    }
 
 
    inline u32_t getTCTNodeNum() const
    {
        return TCTNodeNum;
    }
    inline u32_t getTCTEdgeNum() const
    {
        return TCTEdgeNum;
    }
    inline u32_t getMaxCxtSize() const
    {
        return MaxCxtSize;
    }
 
    inline bool isExtCall(const ICFGNode* inst)
    {
        if(const CallICFGNode* call = SVFUtil::dyn_cast<CallICFGNode>(inst))
            return SVFUtil::isExtCall(call);
        return false;
    }
    inline bool isCallSite(const ICFGNode* inst)
    {
        return SVFUtil::isa<CallICFGNode>(inst);
    }
 
 
    inline bool hasTCTNode(const CxtThread& ct) const
    {
        return ctpToNodeMap.find(ct)!=ctpToNodeMap.end();
    }
    inline TCTNode* getTCTNode(const CxtThread& ct) const
    {
        CxtThreadToNodeMap::const_iterator it = ctpToNodeMap.find(ct);
        assert(it!=ctpToNodeMap.end() && "TCT node not found??");
        return it->second;
    }
 
    inline bool isCandidateFun(const PTACallGraph::FunctionSet& callees) const
    {
        for(PTACallGraph::FunctionSet::const_iterator cit = callees.begin(),
                ecit = callees.end(); cit!=ecit; cit++)
        {
            if(candidateFuncSet.find((*cit))!=candidateFuncSet.end())
                return true;
        }
        return false;
    }
    inline bool isCandidateFun(const SVFFunction* fun) const
    {
        return candidateFuncSet.find(fun)!=candidateFuncSet.end();
    }
    inline bool inSameCallGraphSCC(const PTACallGraphNode* src,const PTACallGraphNode* dst)
    {
        return (tcgSCC->repNode(src->getId()) == tcgSCC->repNode(dst->getId()));
    }
 
 
    inline bool hasParentThread(NodeID tid) const
    {
        const TCTNode* node = getTCTNode(tid);
        return node->getInEdges().size()==1;
    }
    inline NodeID getParentThread(NodeID tid) const
    {
        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();
    }
    const NodeBS getAncestorThread(NodeID tid) const
    {
        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;
    }
    inline const NodeBS getSiblingThread(NodeID tid) const
    {
        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;
    }
 
    const CallStrCxt& getCxtOfCxtThread(const CxtThread& ct) const
    {
        CxtThreadToForkCxt::const_iterator it = ctToForkCxtMap.find(ct);
        assert(it!=ctToForkCxtMap.end() && "Cxt Thread not found!!");
        return it->second;
    }
 
    const SVFFunction* getStartRoutineOfCxtThread(const CxtThread& ct) const
    {
        CxtThreadToFun::const_iterator it = ctToRoutineFunMap.find(ct);
        assert(it!=ctToRoutineFunMap.end() && "Cxt Thread not found!!");
        return it->second;
    }
 
    inline LoopBBs& getJoinLoop(const CallICFGNode* join)
    {
        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;
    }
 
    inline bool hasJoinLoop(const CallICFGNode* join) const
    {
        assert(tcg->getThreadAPI()->isTDJoin(join) && "not a join site");
        InstToLoopMap::const_iterator it = joinSiteToLoopMap.find(join);
        return it!=joinSiteToLoopMap.end();
    }
 
    bool hasLoop(const SVFBasicBlock* bb) const
    {
        const SVFFunction* fun = bb->getFunction();
        return fun->hasLoopInfo(bb);
    }
    bool hasLoop(const ICFGNode* inst) const
    {
        return hasLoop(inst->getBB());
    }
    bool isJoinMustExecutedInLoop(const LoopBBs& lp,const ICFGNode* join);
    const LoopBBs& getLoop(const ICFGNode* inst);
    const LoopBBs& getLoop(const SVFBasicBlock* bb);
 
    void pushCxt(CallStrCxt& cxt, const CallICFGNode* call, const SVFFunction* callee);
    bool matchCxt(CallStrCxt& cxt, const CallICFGNode* call, const SVFFunction* callee);
 
    inline void pushCxt(CallStrCxt& cxt, CallSiteID csId)
    {
        cxt.push_back(csId);
        if (cxt.size() > MaxCxtSize)
            MaxCxtSize = cxt.size();
    }
    inline bool isJoinSiteInRecursion(const CallICFGNode* join) const
    {
        assert(tcg->getThreadAPI()->isTDJoin(join) && "not a join site");
        return inRecurJoinSites.find(join)!=inRecurJoinSites.end();
    }
    void dumpCxt(CallStrCxt& cxt);
 
    void dump(const std::string& filename);
 
    void print() const;
 
private:
    ThreadCallGraph* tcg;
    PointerAnalysis* pta;
    u32_t TCTNodeNum;
    u32_t TCTEdgeNum;
    u32_t MaxCxtSize;
 
    inline TCTNode* addTCTNode(const CxtThread& ct)
    {
        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;
    }
    inline bool addTCTEdge(TCTNode* src, TCTNode* dst)
    {
        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;
    }
 
    void build();
 
 
    void markRelProcs();
    void markRelProcs(const SVFFunction* fun);
 
    void collectEntryFunInCallGraph();
 
    void collectMultiForkedThreads();
 
 
    void collectLoopInfoForJoin();
    bool isLoopHeaderOfJoinLoop(const SVFBasicBlock* bb);
    bool isLoopExitOfJoinLoop(const SVFBasicBlock* bb);
 
 
    bool isInLoopInstruction(const ICFGNode* inst);
    bool isInRecursion(const ICFGNode* inst) const;
 
    void handleCallRelation(CxtThreadProc& ctp, const PTACallGraphEdge* cgEdge, const CallICFGNode* call);
 
 
    inline TCTNode* getOrCreateTCTNode(const CallStrCxt& cxt, const ICFGNode* fork,const CallStrCxt& oldCxt, const SVFFunction* routine)
    {
        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);
    }
 
    void setMultiForkedAttrs(CxtThread& ct)
    {
        if(ct.getThread() != nullptr)
        {
            const ICFGNode* svfInst = ct.getThread();
            ct.setInloop(isInLoopInstruction(svfInst));
            ct.setIncycle(isInRecursion(svfInst));
        }
        else
        {
            ct.setInloop(false);
            ct.setIncycle(false);
        }
    }
 
    void addCxtOfCxtThread(const CallStrCxt& cxt, const CxtThread& ct)
    {
        ctToForkCxtMap[ct] = cxt;
    }
    void addStartRoutineOfCxtThread(const SVFFunction* fun, const CxtThread& ct)
    {
        ctToRoutineFunMap[ct] = fun;
    }
 
 
    inline bool pushToCTPWorkList(const CxtThreadProc& ctp)
    {
        if(isVisitedCTPs(ctp)==false)
        {
            visitedCTPs.insert(ctp);
            return ctpList.push(ctp);
        }
        return false;
    }
    inline CxtThreadProc popFromCTPWorkList()
    {
        CxtThreadProc ctp = ctpList.pop();
        return ctp;
    }
    inline bool isVisitedCTPs(const CxtThreadProc& ctp) const
    {
        return visitedCTPs.find(ctp)!=visitedCTPs.end();
    }
    inline void destroy()
    {
        if(tcgSCC)
            delete tcgSCC;
        tcgSCC=nullptr;
    }
 
    FunSet entryFuncSet; 
    FunSet candidateFuncSet; 
    ThreadCallGraphSCC* tcgSCC; 
    CxtThreadProcVec ctpList;   
    CxtThreadProcSet visitedCTPs; 
    CxtThreadToNodeMap ctpToNodeMap; 
    CxtThreadToForkCxt ctToForkCxtMap; 
    CxtThreadToFun ctToRoutineFunMap; 
    InstToLoopMap joinSiteToLoopMap; 
    Set<const ICFGNode*>  inRecurJoinSites; 
};
 
} // End namespace SVF
 
namespace SVF
{
/* !
 * GenericGraphTraits specializations for constraint graph so that they can be treated as
 * graphs by the generic graph algorithms.
 * Provide graph traits for traversing from a constraint node using standard graph traversals.
 */
template<> struct GenericGraphTraits<SVF::TCTNode*> : public GenericGraphTraits<SVF::GenericNode<SVF::TCTNode,SVF::TCTEdge>*  >
{
};
 
template<>
struct GenericGraphTraits<Inverse<SVF::TCTNode *> > : public GenericGraphTraits<Inverse<SVF::GenericNode<SVF::TCTNode,SVF::TCTEdge>* > >
{
};
 
template<> struct GenericGraphTraits<SVF::TCT*> : public GenericGraphTraits<SVF::GenericGraph<SVF::TCTNode,SVF::TCTEdge>* >
{
    typedef SVF::TCTNode *NodeRef;
};
 
} // End namespace llvm
 
#endif /* TCTNodeDetector_H_ */