Andersen.h

Go to the documentation of this file.

//===- Andersen.h -- Field-sensitive Andersen's pointer analysis-------------//
//
//                     SVF: Static Value-Flow Analysis
//
// Copyright (C) <2013-2017>  <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/>.
//
//===----------------------------------------------------------------------===//
 
/*
 * Andersen.h
 *
 *  Created on: Nov 12, 2013
 *      Author: Yulei Sui
 *
 * The field-sensitive implementation is improved based on
 *
 * Yuxiang Lei and Yulei Sui. "Fast and Precise Handling of Positive Weight Cycles for Field-sensitive Pointer Analysis".
 * 26th International Static Analysis Symposium (SAS'19)
 */
 
#ifndef INCLUDE_WPA_ANDERSEN_H_
#define INCLUDE_WPA_ANDERSEN_H_
 
#include "MemoryModel/PTATY.h"
#include "MemoryModel/PointerAnalysisImpl.h"
#include "MemoryModel/PointsTo.h"
#include "WPA/WPASolver.h"
#include "Graphs/ConsG.h"
#include "Util/GeneralType.h"
#include "Util/Options.h"
 
#include <optional>
#include <vector>
 
namespace SVF
{
 
class ThreadCallGraph;
class SVFIR;
 
typedef WPASolver<ConstraintGraph*> WPAConstraintSolver;
 
class AndersenBase:  public WPAConstraintSolver, public BVDataPTAImpl
{
public:
    typedef OrderedMap<const CallICFGNode*, NodeID> CallSite2DummyValPN;
 
public:
 
    AndersenBase(SVFIR* _pag, PTATY type = PTATY::Andersen_BASE, bool alias_check = true)
        :  BVDataPTAImpl(_pag, type, alias_check), consCG(nullptr)
    {
        iterationForPrintStat = OnTheFlyIterBudgetForStat;
    }
 
    ~AndersenBase() override;
 
    virtual void analyze() override;
 
    virtual void solveAndwritePtsToFile(const std::string& filename);
 
    virtual void readPtsFromFile(const std::string& filename);
 
    virtual void solveConstraints();
 
    virtual void initialize() override;
 
    virtual void finalize() override;
 
    virtual bool updateCallGraph(const CallSiteToFunPtrMap&) override;
 
    virtual bool updateThreadCallGraph(const CallSiteToFunPtrMap&, NodePairSet&);
 
    virtual void connectCaller2ForkedFunParams(const CallICFGNode* cs, const FunObjVar* F,
            NodePairSet& cpySrcNodes);
 
    virtual void connectCaller2CalleeParams(const CallICFGNode* cs, const FunObjVar* F,
                                            NodePairSet& cpySrcNodes);
 
 
    static inline bool classof(const AndersenBase *)
    {
        return true;
    }
    static inline bool classof(const PointerAnalysis *pta)
    {
        return ( pta->getAnalysisTy() == PTATY::Andersen_BASE
                 || pta->getAnalysisTy() == PTATY::Andersen_WPA
                 || pta->getAnalysisTy() == PTATY::AndersenWaveDiff_WPA
                 || pta->getAnalysisTy() == PTATY::AndersenSCD_WPA
                 || pta->getAnalysisTy() == PTATY::AndersenSFR_WPA
                 || pta->getAnalysisTy() == PTATY::TypeCPP_WPA
                 || pta->getAnalysisTy() == PTATY::Steensgaard_WPA);
    }
 
    ConstraintGraph* getConstraintGraph()
    {
        return consCG;
    }
 
 
    inline NodeID sccRepNode(NodeID id) const override
    {
        return consCG->sccRepNode(id);
    }
    inline NodeBS& sccSubNodes(NodeID repId)
    {
        return consCG->sccSubNodes(repId);
    }
 
    virtual bool addCopyEdge(NodeID src, NodeID dst) = 0;
 
    inline void printStat()
    {
        PointerAnalysis::dumpStat();
    }
 
    virtual void normalizePointsTo() override;
 
    void cleanConsCG(NodeID id);
 
    NodeBS redundantGepNodes;
 
 
    static u32_t numOfProcessedAddr;   
    static u32_t numOfProcessedCopy;   
    static u32_t numOfProcessedGep;    
    static u32_t numOfProcessedLoad;   
    static u32_t numOfProcessedStore;  
    static u32_t numOfSfrs;
    static u32_t numOfFieldExpand;
 
    static u32_t numOfSCCDetection;
    static double timeOfSCCDetection;
    static double timeOfSCCMerges;
    static double timeOfCollapse;
    static u32_t AveragePointsToSetSize;
    static u32_t MaxPointsToSetSize;
    static double timeOfProcessCopyGep;
    static double timeOfProcessLoadStore;
    static double timeOfUpdateCallGraph;
 
protected:
    ConstraintGraph* consCG;
    CallSite2DummyValPN
    callsite2DummyValPN; 
    void heapAllocatorViaIndCall(const CallICFGNode* cs, NodePairSet& cpySrcNodes);
};
 
class Andersen:  public AndersenBase
{
 
 
public:
    typedef SCCDetection<ConstraintGraph*> CGSCC;
 
    Andersen(SVFIR* _pag, PTATY type = PTATY::Andersen_WPA, bool alias_check = true)
        :  AndersenBase(_pag, type, alias_check)
    {
    }
 
    virtual ~Andersen()
    {
 
    }
 
    virtual void initialize();
 
    virtual void finalize();
 
    inline void resetData()
    {
        AveragePointsToSetSize = 0;
        MaxPointsToSetSize = 0;
        timeOfProcessCopyGep = 0;
        timeOfProcessLoadStore = 0;
    }
 
 
    static inline bool classof(const Andersen *)
    {
        return true;
    }
    static inline bool classof(const PointerAnalysis *pta)
    {
        return (pta->getAnalysisTy() == PTATY::Andersen_WPA
                || pta->getAnalysisTy() == PTATY::AndersenWaveDiff_WPA
                || pta->getAnalysisTy() == PTATY::AndersenSCD_WPA
                || pta->getAnalysisTy() == PTATY::AndersenSFR_WPA);
    }
 
    virtual inline const PointsTo& getPts(NodeID id)
    {
        return getPTDataTy()->getPts(sccRepNode(id));
    }
    virtual inline bool unionPts(NodeID id, const PointsTo& target)
    {
        id = sccRepNode(id);
        return getPTDataTy()->unionPts(id, target);
    }
    virtual inline bool unionPts(NodeID id, NodeID ptd)
    {
        id = sccRepNode(id);
        ptd = sccRepNode(ptd);
        return getPTDataTy()->unionPts(id,ptd);
    }
 
    virtual NodeBS getMayAliases(NodeID node);
 
    std::vector<NodeBS> getMayAliasesBatch(const std::vector<NodeID>& nodes);
 
 
    void dumpTopLevelPtsTo();
 
    void setDetectPWC(bool flag)
    {
        Options::DetectPWC.setValue(flag);
    }
 
protected:
 
    CallSite2DummyValPN callsite2DummyValPN;        
 
    virtual inline void computeDiffPts(NodeID id)
    {
        if (Options::DiffPts())
        {
            NodeID rep = sccRepNode(id);
            getDiffPTDataTy()->computeDiffPts(rep, getDiffPTDataTy()->getPts(rep));
        }
    }
    virtual inline const PointsTo& getDiffPts(NodeID id)
    {
        NodeID rep = sccRepNode(id);
        if (Options::DiffPts())
            return getDiffPTDataTy()->getDiffPts(rep);
        else
            return getPTDataTy()->getPts(rep);
    }
 
    inline void updatePropaPts(NodeID dstId, NodeID srcId)
    {
        if (!Options::DiffPts())
            return;
        NodeID srcRep = sccRepNode(srcId);
        NodeID dstRep = sccRepNode(dstId);
        getDiffPTDataTy()->updatePropaPtsMap(srcRep, dstRep);
    }
    inline void clearPropaPts(NodeID src)
    {
        if (Options::DiffPts())
        {
            NodeID rep = sccRepNode(src);
            getDiffPTDataTy()->clearPropaPts(rep);
        }
    }
 
    virtual void initWorklist() {}
 
    virtual void processNode(NodeID nodeId);
 
 
    void processAllAddr();
 
    virtual bool processLoad(NodeID node, const ConstraintEdge* load);
    virtual bool processStore(NodeID node, const ConstraintEdge* load);
    virtual bool processCopy(NodeID node, const ConstraintEdge* edge);
    virtual bool processGep(NodeID node, const GepCGEdge* edge);
    virtual void handleCopyGep(ConstraintNode* node);
    virtual void handleLoadStore(ConstraintNode* node);
    virtual void processAddr(const AddrCGEdge* addr);
    virtual bool processGepPts(const PointsTo& pts, const GepCGEdge* edge);
 
    virtual inline bool addCopyEdge(NodeID src, NodeID dst)
    {
        if (consCG->addCopyCGEdge(src, dst))
        {
            updatePropaPts(src, dst);
            return true;
        }
        return false;
    }
 
    virtual void mergeNodeToRep(NodeID nodeId,NodeID newRepId);
 
    virtual bool mergeSrcToTgt(NodeID srcId,NodeID tgtId);
 
 
    void mergeSccNodes(NodeID repNodeId, const NodeBS& subNodes);
    void mergeSccCycle();
 
    virtual void collapsePWCNode(NodeID nodeId);
    void collapseFields();
    bool collapseNodePts(NodeID nodeId);
    bool collapseField(NodeID nodeId);
 
    void updateNodeRepAndSubs(NodeID nodeId,NodeID newRepId);
 
    virtual NodeStack& SCCDetect();
 
    std::optional<NodeBS> collectMayAliasesFromIndex(const PointsTo& expandedPts);
 
    virtual void validateSuccessTests(std::string fun);
 
 
 
    void sanitizePts()
    {
        for(ConstraintGraph::iterator it = consCG->begin(), eit = consCG->end(); it!=eit; ++it)
        {
            const PointsTo& pts = getPts(it->first);
            NodeBS fldInsenObjs;
 
            for (NodeID o : pts)
            {
                if(isFieldInsensitive(o))
                    fldInsenObjs.set(o);
            }
 
            for (NodeID o : fldInsenObjs)
            {
                const NodeBS &allFields = consCG->getAllFieldsObjVars(o);
                for (NodeID f : allFields) addPts(it->first, f);
            }
        }
    }
 
    virtual const std::string PTAName() const
    {
        return "AndersenWPA";
    }
 
    virtual void cluster(void) const;
};
 
 
 
class AndersenWaveDiff : public Andersen
{
 
private:
 
    static AndersenWaveDiff* diffWave; // static instance
 
public:
    AndersenWaveDiff(SVFIR* _pag, PTATY type = PTATY::AndersenWaveDiff_WPA, bool alias_check = true): Andersen(_pag, type, alias_check) {}
 
    static AndersenWaveDiff* createAndersenWaveDiff(SVFIR* _pag)
    {
        if(diffWave==nullptr)
        {
            diffWave = new AndersenWaveDiff(_pag, PTATY::AndersenWaveDiff_WPA, false);
            diffWave->analyze();
            return diffWave;
        }
        return diffWave;
    }
    static void releaseAndersenWaveDiff()
    {
        if (diffWave)
            delete diffWave;
        diffWave = nullptr;
    }
 
    virtual void initialize();
    virtual void finalize();
    virtual void solveWorklist();
    virtual void processNode(NodeID nodeId);
    virtual void postProcessNode(NodeID nodeId);
    virtual bool handleLoad(const PointsTo& objs, const ConstraintEdge* load);
    virtual bool handleStore(const PointsTo& objs, const ConstraintEdge* store);
 
private:
    struct LoadStoreState
    {
        PointsTo pts;
        NodeBS loadDsts;
        NodeBS storeSrcs;
    };
    Map<NodeID, LoadStoreState> loadStoreStates;
};
 
} // End namespace SVF
 
#endif /* INCLUDE_WPA_ANDERSEN_H_ */