MHP.h

Go to the documentation of this file.

//===- MHP.h -- May-happen-in-parallel analysis-------------//
//
//                     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/>.
//
//===----------------------------------------------------------------------===//
 
/*
 * MHP.h
 *
 *  Created on: Jan 21, 2014
 *      Author: Yulei Sui, Peng Di
 *
 * May-happen-in-parallel analysis. One implementation runs on the whole program
 * or a slice: analyze() is templated on the ICFG and CallGraph it traverses
 * (whole graphs or their sliced views), as used by "Multi-Stage On-Demand Program Slicing for
 * Modular Analysis of Multi-Threaded Programs" (ISSTA 2026).
 */
 
#ifndef MHP_H_
#define MHP_H_
 
#include "MTA/TCT.h"
#include "Util/SVFUtil.h"
 
#include <memory>
#include <vector>
 
namespace SVF
{
 
class ForkJoinAnalysis;
class LockAnalysis;
// Forward declaration for the sliced-graph handle analyze() can run on.
class SlicedSVFIRView;
 
class MHP
{
 
public:
    typedef Set<const FunObjVar*> FunSet;
    typedef FIFOWorkList<CxtThreadStmt> CxtThreadStmtWorkList;
    typedef Set<CxtThreadStmt> CxtThreadStmtSet;
    typedef Map<CxtThreadStmt,NodeBS> ThreadStmtToThreadInterleav;
    typedef Map<const ICFGNode*,CxtThreadStmtSet> InstToThreadStmtSetMap;
    typedef SVFLoopAndDomInfo::LoopBBs LoopBBs;
 
    typedef Set<CxtStmt> LockSpan;
 
    typedef std::pair<const FunObjVar*,const FunObjVar*> FuncPair;
    typedef Map<FuncPair, bool> FuncPairToBool;
 
    MHP(TCT* t);
 
    virtual ~MHP();
 
    template<class ICFGGraph, class CGGraph> void analyze(ICFGGraph icfg, CGGraph cg);
 
    template<class ICFGGraph, class CGGraph> void analyzeInterleaving(ICFGGraph icfg, CGGraph cg);
 
    inline ThreadCallGraph* getThreadCallGraph() const
    {
        return tcg;
    }
 
    inline TCT* getTCT() const
    {
        return tct;
    }
 
    bool isConnectedfromMain(const FunObjVar* fun);
 
//    LockSpan getSpanfromCxtLock(NodeID l);
    virtual bool mayHappenInParallel(const ICFGNode* i1, const ICFGNode* i2);
    virtual bool mayHappenInParallelCache(const ICFGNode* i1, const ICFGNode* i2);
    virtual bool mayHappenInParallelInst(const ICFGNode* i1, const ICFGNode* i2);
    virtual bool executedByTheSameThread(const ICFGNode* i1, const ICFGNode* i2);
 
 
    inline const NodeBS& getInterleavingThreads(const CxtThreadStmt& cts)
    {
        return threadStmtToThreadInterLeav[cts];
    }
    inline bool hasInterleavingThreads(const CxtThreadStmt& cts) const
    {
        return threadStmtToThreadInterLeav.find(cts)!=threadStmtToThreadInterLeav.end();
    }
 
 
    inline const CxtThreadStmtSet& getThreadStmtSet(const ICFGNode* inst) const
    {
        InstToThreadStmtSetMap::const_iterator it = instToTSMap.find(inst);
        assert(it!=instToTSMap.end() && "no thread access the instruction?");
        return it->second;
    }
    inline bool hasThreadStmtSet(const ICFGNode* inst) const
    {
        return instToTSMap.find(inst)!=instToTSMap.end();
    }
 
    void printInterleaving();
 
protected:
 
    inline const CallGraph::FunctionSet& getCallee(const CallICFGNode* inst, CallGraph::FunctionSet& callees)
    {
        tcg->getCallees(inst, callees);
        return callees;
    }
    template<class ICFGGraph, class CGGraph> void updateNonCandidateFunInterleaving(ICFGGraph icfg, CGGraph cg);
 
    template<class ICFGGraph, class CGGraph> void handleNonCandidateFun(ICFGGraph icfg, CGGraph cg, const CxtThreadStmt& cts);
 
    template<class ICFGGraph, class CGGraph> void handleFork(ICFGGraph icfg, CGGraph cg, const CxtThreadStmt& cts, NodeID rootTid);
 
    template<class ICFGGraph, class CGGraph> void handleJoin(ICFGGraph icfg, CGGraph cg, const CxtThreadStmt& cts, NodeID rootTid);
 
    template<class ICFGGraph, class CGGraph> void handleCall(ICFGGraph icfg, CGGraph cg, const CxtThreadStmt& cts, NodeID rootTid);
 
    template<class ICFGGraph, class CGGraph> void handleRet(ICFGGraph icfg, CGGraph cg, const CxtThreadStmt& cts);
 
    template<class ICFGGraph, class CGGraph> void handleIntra(ICFGGraph icfg, CGGraph cg, const CxtThreadStmt& cts);
 
 
    typedef Map<const SVFBasicBlock*, std::vector<CxtStmt>> BBToSymJoinsMap;
    typedef Map<CxtStmt, Set<const SVFBasicBlock*>> SymJoinToLoopMap;
    void buildSymJoinKillTables();
    NodeBS edgeFlow(const CxtThreadStmt& cts, const ICFGNode* dst);
 
 
    inline void addInterleavingThread(const CxtThreadStmt& tgr, NodeID tid)
    {
        if(threadStmtToThreadInterLeav[tgr].test_and_set(tid))
        {
            instToTSMap[tgr.getStmt()].insert(tgr);
            pushToCTSWorkList(tgr);
        }
    }
    inline void addInterleavingThread(const CxtThreadStmt& tgr, const CxtThreadStmt& src)
    {
        bool changed = threadStmtToThreadInterLeav[tgr] |= threadStmtToThreadInterLeav[src];
        if(changed)
        {
            instToTSMap[tgr.getStmt()].insert(tgr);
            pushToCTSWorkList(tgr);
        }
    }
    inline void addInterleavingBits(const CxtThreadStmt& tgr, const NodeBS& bits)
    {
        bool changed = threadStmtToThreadInterLeav[tgr] |= bits;
        if(changed)
        {
            instToTSMap[tgr.getStmt()].insert(tgr);
            pushToCTSWorkList(tgr);
        }
    }
    inline void rmInterleavingThread(const CxtThreadStmt& tgr, const NodeBS& tids, const ICFGNode* joinsite)
    {
        NodeBS joinedTids;
        for(NodeBS::iterator it = tids.begin(), eit = tids.end(); it!=eit; ++it)
        {
            if(isMustJoin(tgr.getTid(),joinsite))
                joinedTids.set(*it);
        }
        if(threadStmtToThreadInterLeav[tgr].intersectWithComplement(joinedTids))
        {
            pushToCTSWorkList(tgr);
        }
    }
 
 
    template<class ICFGGraph, class CGGraph> void updateAncestorThreads(ICFGGraph icfg, CGGraph cg, NodeID tid);
    template<class ICFGGraph, class CGGraph> void updateSiblingThreads(ICFGGraph icfg, CGGraph cg, NodeID tid);
 
    bool isRecurFullJoin(NodeID parentTid, NodeID curTid);
 
    bool isMustJoin(const NodeID curTid, const ICFGNode* joinsite);
 
    inline bool isMultiForkedThread(NodeID curTid)
    {
        return tct->getTCTNode(curTid)->isMultiforked();
    }
 
 
 
    inline void pushCxt(CallStrCxt& cxt, const CallICFGNode* call, const FunObjVar* callee)
    {
        if(tct->isCandidateFun(call->getFun()) == false)
            return;
        tct->pushCxt(cxt,call,callee);
    }
    inline bool matchAndPopCxt(CallStrCxt& cxt, const CallICFGNode* call, const FunObjVar* callee)
    {
        return tct->matchAndPopCxt(cxt,call,callee);
    }
    inline bool isContextSuffix(const CallStrCxt& lhs, const CallStrCxt call)
    {
        return tct->isContextSuffix(lhs,call);
    }
 
 
    inline bool pushToCTSWorkList(const CxtThreadStmt& cs)
    {
        return cxtStmtList.push(cs);
    }
    inline CxtThreadStmt popFromCTSWorkList()
    {
        CxtThreadStmt ctp = cxtStmtList.pop();
        return ctp;
    }
 
    inline bool isTDFork(const ICFGNode* call)
    {
        const CallICFGNode* fork = SVFUtil::dyn_cast<CallICFGNode>(call);
        return fork && tcg->getThreadAPI()->isTDFork(fork);
    }
    inline bool isTDJoin(const ICFGNode* call)
    {
        const CallICFGNode* join = SVFUtil::dyn_cast<CallICFGNode>(call);
        return join && tcg->getThreadAPI()->isTDJoin(join);
    }
 
    NodeBS getDirAndIndJoinedTid(const CallStrCxt& cxt, const ICFGNode* call);
 
    bool hasJoinInSymmetricLoop(const CallStrCxt& cxt, const ICFGNode* call) const;
 
    const LoopBBs& getJoinInSymmetricLoop(const CallStrCxt& cxt, const ICFGNode* call) const;
 
    bool isHBPair(NodeID tid1, NodeID tid2);
 
    ThreadCallGraph* tcg;               
    TCT* tct;                           
    ForkJoinAnalysis* fja;              
    CxtThreadStmtWorkList cxtStmtList;  
    ThreadStmtToThreadInterleav threadStmtToThreadInterLeav; 
    BBToSymJoinsMap bbToSymJoins;   
    SymJoinToLoopMap symJoinLoop;   
    InstToThreadStmtSetMap instToTSMap; 
    FuncPairToBool nonCandidateFuncMHPRelMap;
 
public:
    u32_t numOfTotalQueries;        
    u32_t numOfMHPQueries;          
    double interleavingTime;
    double interleavingQueriesTime;
};
 
class ForkJoinAnalysis
{
 
public:
    enum ValDomain
    {
        Empty,  // initial(dummy) state
        TDAlive,  // thread is alive
        TDDead,  //  thread is dead
    };
 
    typedef SVFLoopAndDomInfo::LoopBBs LoopBBs;
    typedef TCT::InstVec InstVec;
    typedef Map<CxtStmt,ValDomain> CxtStmtToAliveFlagMap;
    typedef Map<CxtStmt,NodeBS> CxtStmtToTIDMap;
    typedef Set<NodePair> ThreadPairSet;
    typedef Map<CxtStmt, LoopBBs> CxtStmtToLoopMap;
    typedef FIFOWorkList<CxtStmt> CxtStmtWorkList;
 
    typedef Set<CxtStmt> CxtStmtSet;
    typedef Map<const ICFGNode*, CxtStmtSet> InstToCxtStmt;
 
    ForkJoinAnalysis(TCT* t) : tct(t)
    {
        collectSCEVInfo();
    }
    void collectSCEVInfo();
 
    void analyzeForkJoinPair();
 
    inline NodeBS& getDirectlyJoinedTid(const CxtStmt& cs)
    {
        return directJoinMap[cs];
    }
    NodeBS getDirAndIndJoinedTid(const CxtStmt& cs);
 
    inline const LoopBBs& getJoinInSymmetricLoop(const CxtStmt& cs) const
    {
        CxtStmtToLoopMap::const_iterator it = cxtJoinInLoop.find(cs);
        assert(it!=cxtJoinInLoop.end() && "does not have the loop");
        return it->second;
    }
    inline bool hasJoinInSymmetricLoop(const CxtStmt& cs) const
    {
        CxtStmtToLoopMap::const_iterator it = cxtJoinInLoop.find(cs);
        return it!=cxtJoinInLoop.end();
    }
    inline bool isHBPair(NodeID tid1, NodeID tid2)
    {
        bool nonhp = HBPair.find(std::make_pair(tid1,tid2))!=HBPair.end();
        bool hp = HPPair.find(std::make_pair(tid1,tid2))!=HPPair.end();
        return nonhp && !hp;
    }
    inline bool isFullJoin(NodeID tid1, NodeID tid2)
    {
        bool full = fullJoin.find(std::make_pair(tid1,tid2))!=fullJoin.end();
        bool partial = partialJoin.find(std::make_pair(tid1,tid2))!=partialJoin.end();
        return full && !partial;
    }
 
    inline LoopBBs& getJoinLoop(const CallICFGNode* inst)
    {
        return tct->getJoinLoop(inst);
    }
    inline bool hasJoinLoop(const CallICFGNode* inst)
    {
        return tct->hasJoinLoop(inst);
    }
    inline const CxtStmtToLoopMap& getSymmetricLoopJoins() const
    {
        return cxtJoinInLoop;
    }
private:
 
    void handleFork(const CxtStmt& cts,NodeID rootTid);
 
    void handleJoin(const CxtStmt& cts,NodeID rootTid);
 
    void handleCall(const CxtStmt& cts,NodeID rootTid);
 
    void handleRet(const CxtStmt& cts);
 
    void handleIntra(const CxtStmt& cts);
 
    bool isSameSCEV(const ICFGNode* forkSite, const ICFGNode* joinSite);
 
    bool sameLoopTripCount(const ICFGNode* forkSite, const ICFGNode* joinSite);
 
    bool isAliasedForkJoin(const CallICFGNode* forkSite, const CallICFGNode* joinSite);
    ThreadAPI::ForkJoinAliasCache forkJoinAliasCache;
 
 
    inline ValDomain getMarkedFlag(const CxtStmt& cs)
    {
        CxtStmtToAliveFlagMap::const_iterator it = cxtStmtToAliveFlagMap.find(cs);
        if(it==cxtStmtToAliveFlagMap.end())
        {
            cxtStmtToAliveFlagMap[cs] = Empty;
            return Empty;
        }
        else
            return it->second;
    }
    void markCxtStmtFlag(const CxtStmt& tgr, ValDomain flag)
    {
        ValDomain flag_tgr = getMarkedFlag(tgr);
        cxtStmtToAliveFlagMap[tgr] = flag;
        if(flag_tgr!=getMarkedFlag(tgr))
        {
            instToCxtStmt[tgr.getStmt()].insert(tgr);
            pushToCTSWorkList(tgr);
        }
 
    }
    void markCxtStmtFlag(const CxtStmt& tgr, const CxtStmt& src)
    {
        ValDomain flag_tgr = getMarkedFlag(tgr);
        ValDomain flag_src = getMarkedFlag(src);
        if(flag_tgr == Empty)
        {
            cxtStmtToAliveFlagMap[tgr] = flag_src;
        }
        else if(flag_tgr == TDDead)
        {
            if(flag_src==TDAlive)
                cxtStmtToAliveFlagMap[tgr] = TDAlive;
        }
        else
        {
        }
        if(flag_tgr!=getMarkedFlag(tgr))
        {
            instToCxtStmt[tgr.getStmt()].insert(tgr);
            pushToCTSWorkList(tgr);
        }
    }
    inline void clearFlagMap()
    {
        cxtStmtToAliveFlagMap.clear();
        cxtStmtList.clear();
    }
 
 
    inline bool pushToCTSWorkList(const CxtStmt& cs)
    {
        return cxtStmtList.push(cs);
    }
    inline CxtStmt popFromCTSWorkList()
    {
        CxtStmt ctp = cxtStmtList.pop();
        return ctp;
    }
 
 
 
    inline void pushCxt(CallStrCxt& cxt, const CallICFGNode* call, const FunObjVar* callee)
    {
        if(tct->isCandidateFun(call->getFun()) == false)
            return;
        tct->pushCxt(cxt,call,callee);
    }
    inline bool matchAndPopCxt(CallStrCxt& cxt, const CallICFGNode* call, const FunObjVar* callee)
    {
        return tct->matchAndPopCxt(cxt,call,callee);
    }
    inline bool isContextSuffix(const CallStrCxt& lhs, const CallStrCxt call)
    {
        return tct->isContextSuffix(lhs,call);
    }
 
    inline bool isTDFork(const ICFGNode* call)
    {
        const CallICFGNode* fork = SVFUtil::dyn_cast<CallICFGNode>(call);
        return fork && getTCG()->getThreadAPI()->isTDFork(fork);
    }
    inline bool isTDJoin(const ICFGNode* call)
    {
        const CallICFGNode* join = SVFUtil::dyn_cast<CallICFGNode>(call);
        return join && getTCG()->getThreadAPI()->isTDJoin(join);
    }
    inline const SVFVar* getForkedThread(const CallICFGNode* call)
    {
        return getTCG()->getThreadAPI()->getForkedThread(call);
    }
    inline const SVFVar* getJoinedThread(const CallICFGNode* call)
    {
        return getTCG()->getThreadAPI()->getJoinedThread(call);
    }
    inline const CallGraph::FunctionSet& getCallee(const ICFGNode* inst, CallGraph::FunctionSet& callees)
    {
        getTCG()->getCallees(SVFUtil::cast<CallICFGNode>(inst), callees);
        return callees;
    }
    inline ThreadCallGraph* getTCG() const
    {
        return tct->getThreadCallGraph();
    }
    inline void addDirectlyJoinTID(const CxtStmt& cs, NodeID tid)
    {
        directJoinMap[cs].set(tid);
    }
 
 
    inline void addToHPPair(NodeID tid1, NodeID tid2)
    {
        HPPair.insert(std::make_pair(tid1,tid2));
        HPPair.insert(std::make_pair(tid2,tid1));
    }
    inline void addToHBPair(NodeID tid1, NodeID tid2)
    {
        HBPair.insert(std::make_pair(tid1,tid2));
    }
 
 
    inline void addToFullJoin(NodeID tid1, NodeID tid2)
    {
        fullJoin.insert(std::make_pair(tid1,tid2));
    }
    inline void addToPartial(NodeID tid1, NodeID tid2)
    {
        partialJoin.insert(std::make_pair(tid1,tid2));
    }
 
    inline const CxtStmtSet& getCxtStmtsFromInst(const ICFGNode* inst) const
    {
        InstToCxtStmt::const_iterator it = instToCxtStmt.find(inst);
        assert(it!=instToCxtStmt.end() && "no CxtStmt for the instruction?");
        return it->second;
    }
    inline bool hasCxtStmtsFromInst(const ICFGNode* inst) const
    {
        return instToCxtStmt.find(inst)!=instToCxtStmt.end();
    }
 
    inline void addSymmetricLoopJoin(const CxtStmt& cs, LoopBBs& lp)
    {
        cxtJoinInLoop[cs] = lp;
    }
    TCT* tct;
    CxtStmtToAliveFlagMap cxtStmtToAliveFlagMap;    
    CxtStmtWorkList cxtStmtList;     
    CxtStmtToTIDMap directJoinMap; 
    CxtStmtToTIDMap dirAndIndJoinMap; 
    CxtStmtToLoopMap cxtJoinInLoop;     
    ThreadPairSet HBPair;       
    ThreadPairSet HPPair;       
    ThreadPairSet fullJoin;     
    ThreadPairSet partialJoin;      
    InstToCxtStmt instToCxtStmt;    
};
 
} // End namespace SVF
 
#endif /* MHP_H_ */