VersionedFlowSensitive.h

Go to the documentation of this file.

//===- VersionedFlowSensitive.h -- Versioned flow-sensitive pointer analysis --------//
 
/*
 * VersionedFlowSensitiveAnalysis.h
 *
 *  Created on: Jun 26, 2020
 *      Author: Mohamad Barbar
 *
 * The implementation is based on
 * Mohamad Barbar, Yulei Sui and Shiping Chen. "Object Versioning for Flow-Sensitive Pointer Analysis".
 * International Symposium on Code Generation and Optimization (CGO'21)
 */
 
#ifndef VFS_H_
#define VFS_H_
 
#include "Graphs/SVFGOPT.h"
#include "MSSA/SVFGBuilder.h"
#include "WPA/FlowSensitive.h"
#include "WPA/WPAFSSolver.h"
#include "MemoryModel/PTATY.h"
#include "MemoryModel/PointsTo.h"
 
namespace SVF
{
 
class AndersenWaveDiff;
 
class VersionedFlowSensitive : public FlowSensitive
{
    friend class VersionedFlowSensitiveStat;
 
private:
    typedef CoreBitVector MeldVersion;
 
public:
    typedef Map<NodeID, Version> ObjToVersionMap;
    typedef Map<VersionedVar, const DummyVersionPropSVFGNode *> VarToPropNodeMap;
 
    typedef std::vector<ObjToVersionMap> LocVersionMap;
    typedef Map<NodeID, Map<Version, std::vector<Version>>> VersionRelianceMap;
 
    static const Version invalidVersion;
 
    static VersionedVar atKey(NodeID, Version);
 
    VersionedFlowSensitive(SVFIR *_pag, PTATY type = PTATY::VFS_WPA);
 
    virtual void initialize() override;
 
    virtual void finalize() override;
 
    virtual const std::string PTAName() const override
    {
        return "VersionedFlowSensitive";
    }
 
 
    static inline bool classof(const VersionedFlowSensitive *)
    {
        return true;
    }
    static inline bool classof(const PointerAnalysis *pta)
    {
        return pta->getAnalysisTy() == PTATY::VFS_WPA;
    }
 
    static VersionedFlowSensitive *createVFSWPA(SVFIR *_pag)
    {
        if (vfspta == nullptr)
        {
            vfspta = new VersionedFlowSensitive(_pag);
            vfspta->analyze();
        }
 
        return vfspta;
    }
 
    static void releaseVFSWPA()
    {
        if (vfspta) delete vfspta;
        vfspta = nullptr;
    }
 
protected:
    virtual bool processLoad(const LoadSVFGNode* load) override;
    virtual bool processStore(const StoreSVFGNode* store) override;
    virtual void processNode(NodeID n) override;
    virtual void updateConnectedNodes(const SVFGEdgeSetTy& newEdges) override;
 
    virtual bool propAlongIndirectEdge(const IndirectSVFGEdge*) override
    {
        return false;
    }
 
    virtual void cluster(void) override;
 
public:
    virtual bool isStore(const NodeID l) const;
 
    virtual bool isLoad(const NodeID l) const;
 
    Version getVersion(const NodeID l, const NodeID o, const LocVersionMap &lvm) const;
 
    Version getConsume(const NodeID l, const NodeID o) const;
 
    Version getYield(const NodeID l, const NodeID o) const;
 
    std::vector<Version> &getReliantVersions(const NodeID o, const Version v);
 
    NodeBS &getStmtReliance(const NodeID o, const Version v);
 
    void dumpReliances(void) const;
 
    void dumpLocVersionMaps(void) const;
 
    void solveAndwritePtsToFile(const std::string& filename) override;
 
    void writeVersionedAnalysisResultToFile(const std::string& filename);
 
    void readVersionedAnalysisResultFromFile(std::ifstream& F);
 
    void readPtsFromFile(const std::string& filename) override;
 
    static void dumpMeldVersion(MeldVersion &v);
 
private:
    void prelabel(void);
    void meldLabel(void);
    static bool meld(MeldVersion &mv1, const MeldVersion &mv2);
 
    void removeAllIndirectSVFGEdges(void);
 
    void propagateVersion(NodeID o, Version v);
 
    void propagateVersion(const NodeID o, const Version v, const Version vp, bool time=true);
 
    virtual void buildIsStoreLoadMaps(void);
 
    virtual void buildDeltaMaps(void);
 
    virtual bool delta(const NodeID l) const;
 
    virtual bool deltaSource(const NodeID l) const;
 
    void setVersion(const NodeID l, const NodeID o, const Version v, LocVersionMap &lvm);
 
    void setConsume(const NodeID l, const NodeID o, const Version v);
 
    void setYield(const NodeID l, const NodeID o, const Version v);
 
    LocVersionMap consume;
    LocVersionMap yield;
 
    VersionRelianceMap versionReliance;
    Map<NodeID, Map<Version, NodeBS>> stmtReliance;
 
    VarToPropNodeMap versionedVarToPropNode;
 
    // Maps an object o to o' if o is equivalent to o' with respect to
    // versioning. Thus, we don't need to store the versions of o and look
    // up those for o' instead.
    Map<NodeID, NodeID> equivalentObject;
 
    FIFOWorkList<NodeID> vWorklist;
 
    Set<NodeID> prelabeledObjects;
 
    BVDataPTAImpl::VersionedPTDataTy *vPtD;
 
    std::vector<bool> deltaMap;
 
    std::vector<bool> deltaSourceMap;
 
    std::vector<bool> isStoreMap;
 
    std::vector<bool> isLoadMap;
 
 
    u32_t numPrelabeledNodes;  
    u32_t numPrelabelVersions; 
 
    double prelabelingTime;  
    double meldLabelingTime; 
    double versionPropTime;  
 
    static VersionedFlowSensitive *vfspta;
 
    class SCC
    {
    private:
        typedef struct NodeData
        {
            int index;
            int lowlink;
            bool onStack;
        } NodeData;
 
    public:
        static unsigned detectSCCs(VersionedFlowSensitive *vfs,
                                   const SVFG *svfg, const NodeID object,
                                   const std::vector<const SVFGNode *> &startingNodes,
                                   std::vector<int> &partOf,
                                   std::vector<const IndirectSVFGEdge *> &footprint);
 
    private:
        static void visit(VersionedFlowSensitive *vfs,
                          const NodeID object,
                          std::vector<int> &partOf,
                          std::vector<const IndirectSVFGEdge *> &footprint,
                          std::vector<NodeData> &nodeData,
                          std::stack<const SVFGNode *> &stack,
                          int &index,
                          int &currentSCC,
                          const SVFGNode *v);
    };
};
 
} // End namespace SVF
 
#endif /* VFS_H_ */