PointerAnalysis.h

Go to the documentation of this file.

//===- PointerAnalysis.h -- Base class of pointer analyses--------------------//
//
//                     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/>.
//
//===----------------------------------------------------------------------===//
 
/*
 * PointerAnalysis.h
 *
 *  Created on: Nov 12, 2013
 *      Author: Yulei Sui
 */
 
#ifndef POINTERANALYSIS_H_
#define POINTERANALYSIS_H_
 
#include <unistd.h>
#include <signal.h>
 
#include "Graphs/CHG.h"
#include "Graphs/ThreadCallGraph.h"
#include "Graphs/SCC.h"
#include "MemoryModel/AbstractPointsToDS.h"
#include "MemoryModel/ConditionalPT.h"
#include "MemoryModel/MutablePointsToDS.h"
#include "MemoryModel/PersistentPointsToDS.h"
#include "MemoryModel/PointsTo.h"
#include "SVFIR/SVFIR.h"
 
namespace SVF
{
 
class CommonCHGraph;
 
class ICFG;
class PTAStat;
/*
 * Pointer Analysis Base Class
 */
class PointerAnalysis
{
 
public:
    enum PTATY
    {
        // Whole program analysis
        Andersen_BASE,      
        Andersen_WPA,       
        AndersenSCD_WPA,    
        AndersenSFR_WPA,    
        AndersenWaveDiff_WPA,   
        Steensgaard_WPA,      
        CSCallString_WPA,   
        CSSummary_WPA,      
        FSDATAFLOW_WPA, 
        FSSPARSE_WPA,       
        VFS_WPA,        
        FSCS_WPA,           
        CFLFICI_WPA,        
        CFLFSCI_WPA,        
        CFLFSCS_WPA,    
        TypeCPP_WPA, 
 
        // Demand driven analysis
        FieldS_DDA,     
        FlowS_DDA,      
        PathS_DDA,      
        Cxt_DDA,        
 
 
        Default_PTA     
    };
 
    enum PTAImplTy
    {
        BaseImpl,   
        BVDataImpl, 
        CondImpl,   
    };
 
 
    typedef Set<const CallICFGNode*> CallSiteSet;
    typedef SVFIR::CallSiteToFunPtrMap CallSiteToFunPtrMap;
    typedef Set<const FunObjVar*> FunctionSet;
    typedef OrderedMap<const CallICFGNode*, FunctionSet> CallEdgeMap;
    typedef SCCDetection<CallGraph*> CallGraphSCC;
    typedef Set<const GlobalObjVar*> VTableSet;
    typedef Set<const FunObjVar*> VFunSet;
 
    static const std::string aliasTestMayAlias;
    static const std::string aliasTestMayAliasMangled;
    static const std::string aliasTestNoAlias;
    static const std::string aliasTestNoAliasMangled;
    static const std::string aliasTestPartialAlias;
    static const std::string aliasTestPartialAliasMangled;
    static const std::string aliasTestMustAlias;
    static const std::string aliasTestMustAliasMangled;
    static const std::string aliasTestFailMayAlias;
    static const std::string aliasTestFailMayAliasMangled;
    static const std::string aliasTestFailNoAlias;
    static const std::string aliasTestFailNoAliasMangled;
 
private:
    void destroy();
 
protected:
 
 
 
    bool print_stat;
    bool alias_validation;
    u32_t OnTheFlyIterBudgetForStat;
 
    static SVFIR* pag;
    PTATY ptaTy;
    PTAImplTy ptaImplTy;
    PTAStat* stat;
    CallGraph* callgraph;
    CallGraphSCC* callGraphSCC;
    ICFG* icfg;
    CommonCHGraph *chgraph;
 
public:
    inline ICFG* getICFG() const
    {
        return pag->getICFG();
    }
    inline u32_t getNumOfResolvedIndCallEdge() const
    {
        return getCallGraph()->getNumOfResolvedIndCallEdge();
    }
    inline CallGraph* getCallGraph() const
    {
        return callgraph;
    }
    inline CallGraphSCC* getCallGraphSCC() const
    {
        return callGraphSCC;
    }
 
    PointerAnalysis(SVFIR* pag, PTATY ty = Default_PTA, bool alias_check = true);
 
    inline PTATY getAnalysisTy() const
    {
        return ptaTy;
    }
 
    inline PTAImplTy getImplTy() const
    {
        return ptaImplTy;
    }
 
    inline SVFIR* getPAG() const
    {
        return pag;
    }
 
    inline PTAStat* getStat() const
    {
        return stat;
    }
 
    inline OrderedNodeSet& getAllValidPtrs()
    {
        return pag->getAllValidPtrs();
    }
 
    virtual ~PointerAnalysis();
 
    virtual void initialize();
 
    virtual void finalize();
 
    virtual void analyze() = 0;
 
    virtual void computeDDAPts(NodeID) {}
 
    virtual AliasResult alias(const SVFVar* V1,
                              const SVFVar* V2) = 0;
 
    virtual AliasResult alias(NodeID node1, NodeID node2) = 0;
 
    virtual const PointsTo& getPts(NodeID ptr) = 0;
 
    virtual const NodeSet& getRevPts(NodeID nodeId) = 0;
 
    void printIndCSTargets(const CallICFGNode* cs, const FunctionSet& targets);
 
    // Debug purpose
    virtual void dumpTopLevelPtsTo() {}
    virtual void dumpAllPts() {}
    virtual void dumpCPts() {}
    virtual void dumpPts(NodeID ptr, const PointsTo& pts);
    void printIndCSTargets();
    void dumpAllTypes();
 
protected:
    inline const CallSiteToFunPtrMap& getIndirectCallsites() const
    {
        return pag->getIndirectCallsites();
    }
    inline NodeID getFunPtr(const CallICFGNode* cs) const
    {
        return pag->getFunPtr(cs);
    }
 
    virtual void validateTests();
    virtual void validateSuccessTests(std::string fun);
    virtual void validateExpectedFailureTests(std::string fun);
 
    void resetObjFieldSensitive();
 
public:
    void dumpStat();
 
 
    inline bool containBlackHoleNode(const PointsTo& pts)
    {
        return pts.test(pag->getBlackHoleNode());
    }
    inline bool containConstantNode(const PointsTo& pts)
    {
        return pts.test(pag->getConstantNode());
    }
    virtual inline bool isBlkObjOrConstantObj(NodeID ptd) const
    {
        return pag->isBlkObjOrConstantObj(ptd);
    }
 
 
    inline bool isHeapMemObj(NodeID id) const
    {
        return pag->getBaseObject(id) && SVFUtil::isa<HeapObjVar, DummyObjVar>(pag->getBaseObject(id));
    }
 
    inline bool isArrayMemObj(NodeID id) const
    {
        const BaseObjVar* obj = pag->getBaseObject(id);
        assert(obj && "base object is null??");
        return obj->isArray();
    }
 
    inline bool isFIObjNode(NodeID id) const
    {
        return (SVFUtil::isa<BaseObjVar>(pag->getGNode(id)));
    }
    inline NodeID getBaseObjVar(NodeID id)
    {
        return pag->getBaseObjVar(id);
    }
    inline NodeID getFIObjVar(NodeID id)
    {
        return pag->getFIObjVar(id);
    }
    inline NodeID getGepObjVar(NodeID id, const APOffset& ap)
    {
        return pag->getGepObjVar(id, ap);
    }
    virtual inline const NodeBS& getAllFieldsObjVars(NodeID id)
    {
        return pag->getAllFieldsObjVars(id);
    }
    inline void setObjFieldInsensitive(NodeID id)
    {
        BaseObjVar* baseObj = const_cast<BaseObjVar*>(pag->getBaseObject(id));
        baseObj->setFieldInsensitive();
    }
    inline bool isFieldInsensitive(NodeID id) const
    {
        const BaseObjVar* baseObj = pag->getBaseObject(id);
        return baseObj->isFieldInsensitive();
    }
 
    inline bool printStat()
    {
        return print_stat;
    }
 
    inline void disablePrintStat()
    {
        print_stat = false;
    }
 
 
    inline CallEdgeMap& getIndCallMap()
    {
        return getCallGraph()->getIndCallMap();
    }
    inline bool hasIndCSCallees(const CallICFGNode* cs) const
    {
        return getCallGraph()->hasIndCSCallees(cs);
    }
    inline const FunctionSet& getIndCSCallees(const CallICFGNode* cs) const
    {
        return getCallGraph()->getIndCSCallees(cs);
    }
 
    virtual void resolveIndCalls(const CallICFGNode* cs, const PointsTo& target, CallEdgeMap& newEdges);
 
 
 
    inline void callGraphSCCDetection()
    {
        if(callGraphSCC==nullptr)
            callGraphSCC = new CallGraphSCC(callgraph);
 
        callGraphSCC->find();
    }
    inline NodeID getCallGraphSCCRepNode(NodeID id) const
    {
        return callGraphSCC->repNode(id);
    }
    inline bool inSameCallGraphSCC(const FunObjVar* fun1,const FunObjVar* fun2)
    {
        const CallGraphNode* src = callgraph->getCallGraphNode(fun1);
        const CallGraphNode* dst = callgraph->getCallGraphNode(fun2);
        return (getCallGraphSCCRepNode(src->getId()) == getCallGraphSCCRepNode(dst->getId()));
    }
    inline bool isInRecursion(const FunObjVar* fun) const
    {
        return callGraphSCC->isInCycle(callgraph->getCallGraphNode(fun)->getId());
    }
    bool isLocalVarInRecursiveFun(NodeID id) const;
 
    virtual const std::string PTAName() const
    {
        return "Pointer Analysis";
    }
 
    CommonCHGraph *getCHGraph() const
    {
        return chgraph;
    }
 
    void getVFnsFromCHA(const CallICFGNode* cs, VFunSet &vfns);
    void getVFnsFromPts(const CallICFGNode* cs, const PointsTo &target, VFunSet &vfns);
    void connectVCallToVFns(const CallICFGNode* cs, const VFunSet &vfns, CallEdgeMap& newEdges);
    virtual void resolveCPPIndCalls(const CallICFGNode* cs,
                                    const PointsTo& target,
                                    CallEdgeMap& newEdges);
};
 
} // End namespace SVF
 
#endif /* POINTERANALYSIS_H_ */