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
 *
 * Builds a *thread-aware* Sparse Value-Flow Graph (SVFG) for the FSAM
 * flow-sensitive multithreaded pointer analysis (Sui, Di, Xue, CGO'16).
 *
 * On top of the stock thread-oblivious SVFG, it adds inter-thread (interference)
 * indirect value-flow edges between store/load and store/store statements that
 *   (1) may-happen-in-parallel (MHP), and
 *   (2) may-alias on the address-taken object, and
 *   (3) are not excluded by a common lock (non-interference lock-pair pruning).
 */
 
#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 <map>
#include <set>
#include <utility>
 
namespace SVF
{
 
class SlicedICFGView;
 
class MTASVFGBuilder : public SVFGBuilder
{
public:
    typedef Set<const StmtSVFGNode*> SVFGNodeSet;
    typedef NodeBS SVFGNodeIDSet;
 
    MTASVFGBuilder(MHP* m, LockAnalysis* la) : SVFGBuilder(), mhp(m), lockana(la) {}
    ~MTASVFGBuilder() override = default;
 
    static u32_t numOfNewSVFGEdges;
 
    void configureForMainSolve(const SlicedICFGView* slice)
    {
        icfgSlice = slice;
        recordThreadVF = false;
    }
 
    typedef std::pair<const StmtSVFGNode*, const StmtSVFGNode*> ThreadVFEdge;
 
    const std::map<ThreadVFEdge, std::set<const ICFGNode*>>& getThreadVFQueryMap() const
    {
        return threadVFQueryMap;
    }
 
protected:
    void buildSVFG() override;
 
    std::unique_ptr<MRGenerator> createMRGenerator(BVDataPTAImpl* pta, bool ptrOnlyMSSA) override;
 
private:
    const SlicedICFGView* icfgSlice = nullptr; 
    bool recordThreadVF = true;                
 
    void collectLoadStoreSVFGNodes();
 
    void connectThreadJoinEdges();
 
    void addJoinRetEdge(const FormalOUTSVFGNode* formalOut,
                        const ActualOUTSVFGNode* actualOut, CallSiteID csId);
 
    void connectMHPEdges(PointerAnalysis* pta);
 
    void handleStoreLoad(const StmtSVFGNode* n1, const StmtSVFGNode* n2, PointerAnalysis* pta);
    void handleStoreStore(const StmtSVFGNode* n1, const StmtSVFGNode* n2, PointerAnalysis* pta);
 
    void recordThreadVFSource(const StmtSVFGNode* s, const StmtSVFGNode* sp, bool commonLock);
 
    SVFGEdge* addTDEdge(NodeID srcId, NodeID dstId, const PointsTo& pts);
 
 
    SVFGNodeIDSet getPrevNodes(const StmtSVFGNode* n);
    SVFGNodeIDSet getSuccNodes(const StmtSVFGNode* n);
    bool isHeadOfSpan(const StmtSVFGNode* n);
    bool isTailOfSpan(const StmtSVFGNode* n);
 
    SVFGNodeSet stnodeSet;  
    SVFGNodeSet ldnodeSet;  
 
    std::map<ThreadVFEdge, std::set<const ICFGNode*>> threadVFQueryMap;
 
    MHP* mhp;
    LockAnalysis* lockana;
 
    Map<const StmtSVFGNode*, SVFGNodeIDSet> prevset;
    Map<const StmtSVFGNode*, SVFGNodeIDSet> succset;
    Map<const StmtSVFGNode*, bool> headmap;
    Map<const StmtSVFGNode*, bool> tailmap;
};
 
} // End namespace SVF
 
#endif /* INCLUDE_MTA_MTASVFGBUILDER_H_ */