MTASVFGBuilder.h

Go to the documentation of this file.

//===- MTASVFGBuilder.h -- Thread-aware SVFG builder for FSAM -----------===//
//
//                     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/>.
//
//===----------------------------------------------------------------------===//
 
/*
 * MTASVFGBuilder.h
 *
 *      Author: Jiawei Yang
 */
 
#ifndef INCLUDE_MTA_MTASVFGBUILDER_H_
#define INCLUDE_MTA_MTASVFGBUILDER_H_
 
#include "MSSA/SVFGBuilder.h"
#include "Graphs/SVFG.h"
#include "Graphs/SVFGEdge.h"
#include "MTA/MHP.h"
#include "MTA/LockAnalysis.h"
#include "MemoryModel/PointsTo.h"
#include <utility>
#include <vector>
 
namespace SVF
{
 
class SlicedSVFGView;
 
class MTASVFGBuilder : public SVFGBuilder
{
public:
    typedef Set<const StmtSVFGNode*> SVFGNodeSet;
    typedef NodeBS SVFGNodeIDSet;
 
    enum class InterferenceEdgeMode
    {
        Analysis,   
        SlicingOnly 
    };
 
    MTASVFGBuilder(MHP* mhp, LockAnalysis* lockAnalysis,
                   InterferenceEdgeMode edgeMode = InterferenceEdgeMode::Analysis)
        : SVFGBuilder(),
          labelInterferenceEdges(edgeMode == InterferenceEdgeMode::Analysis),
          mhp(mhp), lockAnalysis(lockAnalysis)
    {
    }
    ~MTASVFGBuilder() override = default;
 
    typedef std::pair<const StmtSVFGNode*, const StmtSVFGNode*> ThreadVFEdge;
 
    using ThreadVFQueryMap = Map<ThreadVFEdge, Set<const ICFGNode*>>;
    const ThreadVFQueryMap& getThreadVFQueryMap() const
    {
        return threadVFQueryMap;
    }
 
    struct ThreadVFCandidate
    {
        ThreadVFCandidate(NodeID sourceNodeId, NodeID destinationNodeId)
            : sourceNodeId(sourceNodeId), destinationNodeId(destinationNodeId)
        {
        }
 
        bool operator<(const ThreadVFCandidate& other) const
        {
            return sourceNodeId < other.sourceNodeId ||
                   (sourceNodeId == other.sourceNodeId &&
                    destinationNodeId < other.destinationNodeId);
        }
 
        bool operator==(const ThreadVFCandidate& other) const
        {
            return sourceNodeId == other.sourceNodeId &&
                   destinationNodeId == other.destinationNodeId;
        }
 
        NodeID sourceNodeId;
        NodeID destinationNodeId;
    };
    using ThreadVFCandidateList = std::vector<ThreadVFCandidate>;
 
    class ThreadVFBuildConfig
    {
    public:
        static ThreadVFBuildConfig mainPhase(
            const SlicedSVFGView& scope,
            const ThreadVFCandidateList* candidates = nullptr)
        {
            return ThreadVFBuildConfig(&scope, candidates);
        }
 
        static ThreadVFBuildConfig wholeProgram()
        {
            return ThreadVFBuildConfig(nullptr, nullptr);
        }
 
    private:
        friend class MTASVFGBuilder;
        ThreadVFBuildConfig(const SlicedSVFGView* scope,
                            const ThreadVFCandidateList* candidates)
            : scope(scope), candidates(candidates)
        {
        }
 
        const SlicedSVFGView* scope = nullptr; 
        const ThreadVFCandidateList* candidates = nullptr;
    };
 
    void replaceThreadAwareOverlay(MHP* mhp, LockAnalysis* lockAnalysis,
                                   const ThreadVFBuildConfig& config);
 
    void clearThreadAwareOverlay();
 
    size_t getThreadAwareEdgeCount() const
    {
        return threadAwareEdges.size();
    }
 
protected:
    void buildSVFG() override;
 
    std::unique_ptr<MRGenerator> createMRGenerator(BVDataPTAImpl* pta, bool ptrOnlyMSSA) override;
 
private:
    const SlicedSVFGView* overlayScope = nullptr; 
    const ThreadVFCandidateList* overlayCandidates = nullptr;
    bool recordThreadVFQueries = true;         
    bool labelInterferenceEdges = true;        
 
    void collectLoadStoreSVFGNodes();
    bool isInOverlayScope(const SVFGNode* node) const;
 
    void connectThreadJoinEdges();
 
    void addJoinRetEdge(const FormalOUTSVFGNode* formalOut,
                        const ActualOUTSVFGNode* actualOut,
                        CallSiteID callSiteId);
 
    void connectMHPEdges(PointerAnalysis* pta);
 
    void handleStoreLoad(const StmtSVFGNode* store,
                         const StmtSVFGNode* load, PointerAnalysis* pta);
    void handleStoreStore(const StmtSVFGNode* firstStore,
                          const StmtSVFGNode* secondStore,
                          PointerAnalysis* pta);
 
    void recordThreadVFSource(const StmtSVFGNode* source,
                              const StmtSVFGNode* destination,
                              bool commonLock);
 
    SVFGEdge* addTDEdge(NodeID srcId, NodeID dstId, const PointsTo& pts);
 
 
    SVFGNodeIDSet getPredecessorNodes(const StmtSVFGNode* node);
    SVFGNodeIDSet getSuccessorNodes(const StmtSVFGNode* node);
    bool isHeadOfSpan(const StmtSVFGNode* node);
    bool isTailOfSpan(const StmtSVFGNode* node);
 
    SVFGNodeSet storeNodes;
    SVFGNodeSet loadNodes;
 
    ThreadVFQueryMap threadVFQueryMap;
    MHP* mhp;
    LockAnalysis* lockAnalysis;
 
    Map<const StmtSVFGNode*, SVFGNodeIDSet> predecessorCache;
    Map<const StmtSVFGNode*, SVFGNodeIDSet> successorCache;
    Map<const StmtSVFGNode*, bool> spanHeadCache;
    Map<const StmtSVFGNode*, bool> spanTailCache;
    SVFGEdgeSet threadAwareEdges;
};
 
} // End namespace SVF
 
#endif /* INCLUDE_MTA_MTASVFGBUILDER_H_ */