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 <memory>
#include <vector>
 
#include "MemoryModel/PointerAnalysis.h"
#include "Graphs/SCC.h"
#include "Graphs/ThreadCallGraph.h"
#include "Util/CxtStmt.h"
#include "Util/GeneralType.h"
#include "Util/SVFUtil.h"
 
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 SVFValue*node)
    {
        return node->getNodeKind() == TCTNodeKd;
    }

 
 
protected:
    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;
    struct FunObjVarIdCmp
    {
        bool operator()(const FunObjVar* lhs, const FunObjVar* rhs) const
        {
            if (lhs == nullptr || rhs == nullptr)
                return lhs == nullptr && rhs != nullptr;
            return lhs->getId() < rhs->getId();
        }
    };
    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;

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

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

    virtual ~TCT();

    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 CallGraph::FunctionSet& callees) const
    {
        for(CallGraph::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 FunObjVar* fun) const
    {
        return candidateFuncSet.find(fun)!=candidateFuncSet.end();
    }

    inline bool inSameCallGraphSCC(const CallGraphNode* src,const CallGraphNode* 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 NodeBS getParentThreads(NodeID tid) const
    {
        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;
    }

    const NodeBS getAncestorThreads(NodeID tid) const
    {
        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;
    }

    inline const NodeBS getSiblingThread(NodeID tid) const
    {
        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;
    }


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

    const FunObjVar* 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 FunObjVar* 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);



    virtual void pushCxt(CallStrCxt& cxt, const CallICFGNode* call, const FunObjVar* callee);
    bool matchAndPopCxt(CallStrCxt& cxt, const CallICFGNode* call, const FunObjVar* callee);
    bool isContextSuffix(const CallStrCxt& lhs, const CallStrCxt& call);

    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;
 
protected:
    TCT(PointerAnalysis* p, u32_t contextLimit);
 
    ThreadCallGraph* tcg;
    PointerAnalysis* pta;
    const u32_t contextLimit;
    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;
    }

    virtual void build();


    virtual void markRelProcs();
    virtual void markRelProcs(const FunObjVar* fun);

    virtual void collectEntryFunInCallGraph();

    void collectMultiForkedThreads();



    virtual void collectLoopInfoForJoin();
    bool isLoopHeaderOfJoinLoop(const SVFBasicBlock* bb);
    bool isLoopExitOfJoinLoop(const SVFBasicBlock* bb);



    bool isInLoopInstruction(const ICFGNode* inst);
    bool isInRecursion(const ICFGNode* inst) const;

    virtual void handleCallRelation(CxtThreadProc& ctp, const CallGraphEdge* cgEdge, const CallICFGNode* call);


    inline TCTNode* getOrCreateTCTNode(const CallStrCxt& cxt, const ICFGNode* fork, const CxtThreadProc& forkSiteCtp, const FunObjVar* routine)
    {
        CxtThread ct(cxt,fork);
        CxtThreadToNodeMap::const_iterator it = ctpToNodeMap.find(ct);
        if(it!=ctpToNodeMap.end())
        {
            // A second spawn context merged onto this truncated CxtThread: the
            // node stands for multiple dynamic instances, so mark it multiforked.
            if (addCxtOfCxtThread(forkSiteCtp.getTid(), forkSiteCtp.getContext(), ct))
                it->second->setMultiforked(true);
            return it->second;
        }
 
        addCxtOfCxtThread(forkSiteCtp.getTid(), forkSiteCtp.getContext(), ct);
        addStartRoutineOfCxtThread(routine,ct);
 
        setMultiForkedAttrs(ct);
        return addTCTNode(ct);
    }


    void setMultiForkedAttrs(CxtThread& ct)
    {
        if(ct.getThread() != nullptr &&
                dummyForkSites.find(ct.getThread()) == dummyForkSites.end())
        {
            const ICFGNode* svfInst = ct.getThread();
            ct.setInloop(isInLoopInstruction(svfInst));
            ct.setIncycle(isInRecursion(svfInst));
        }
        else
        {
            ct.setInloop(false);
            ct.setIncycle(false);
        }
    }

    bool addCxtOfCxtThread(NodeID pTid, const CallStrCxt& cxt, const CxtThread& ct)
    {
        return ctToForkCxtsMap[ct].insert(std::make_pair(pTid, cxt)).second;
    }

    void addStartRoutineOfCxtThread(const FunObjVar* fun, const CxtThread& ct)
    {
        ctToRoutineFunMap[ct] = fun;
    }

    ICFGNode* createDummyForkSite()
    {
        ICFGNode* dummyForkSite = new ICFGNode(dummyForkICFGNodeID--, SVFValue::GlobalBlock);
        dummyForkSites.insert(dummyForkSite);
        return dummyForkSite;
    }


    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();
    }

 
    FunSet entryFuncSet; 
    FunSet candidateFuncSet; 
    ThreadCallGraphSCC* tcgSCC; 
    CxtThreadProcVec ctpList;   
    CxtThreadProcSet visitedCTPs; 
    CxtThreadToNodeMap ctpToNodeMap; 
    CxtThreadToForkCxtSet ctToForkCxtsMap; 
    CxtThreadToFun ctToRoutineFunMap; 
    InstToLoopMap joinSiteToLoopMap; 
    Set<const ICFGNode*>  inRecurJoinSites; 
    DummyForkSiteSet dummyForkSites;  
    NodeID dummyForkICFGNodeID = UINT32_MAX;  
};
 
} // 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_ */