NodeIDAllocator.h

Go to the documentation of this file.

//===- NodeIDAllocator.h -- Allocates node IDs on request ------------------------//
 
#ifndef NODEIDALLOCATOR_H_
#define NODEIDALLOCATOR_H_
 
#include "FastCluster/fastcluster.h"
#include "SVFIR/SVFType.h"
#include "MemoryModel/PointsTo.h"
 
namespace SVF
{
 
// Forward declare for the Clusterer.
class BVDataPTAImpl;
 
class NodeIDAllocator
{
 
public:
    enum Strategy
    {
        DENSE,
        REVERSE_DENSE,
        SEQ,
        DBUG,
    };
 
    static const NodeID blackHoleObjectId;
    static const NodeID constantObjectId;
    static const NodeID blackHolePointerId;
    static const NodeID nullPointerId;
 
    static NodeIDAllocator *get(void);
 
    static void unset(void);
 
    NodeID allocateObjectId(void);
 
    NodeID allocateTypeId(void);
 
    NodeID allocateGepObjectId(NodeID base, u32_t offset, u32_t maxFieldLimit);
 
    NodeID allocateValueId(void);
 
    NodeID endSymbolAllocation(void);
 
    NodeID getNumObjects(void) const
    {
        return numObjects;
    }
 
    inline void increaseNumOfObjAndNodes()
    {
        ++numObjects;
        ++numNodes;
    }
 
    inline void increaseNumOfValues()
    {
        ++numValues;
        ++numNodes;
    }
 
    inline int getNumOfNodes()
    {
        return numNodes;
    }
 
private:
    NodeIDAllocator(void);
 
private:
    NodeID numObjects;
    NodeID numValues;
    NodeID numSymbols;
    NodeID numNodes;
    NodeID numType;
 
    enum Strategy strategy;
 
    static NodeIDAllocator *allocator;
 
public:
    class Clusterer
    {
    private:
        typedef Map<NodePair, std::pair<unsigned, unsigned>> DistOccMap;
 
        static const std::string NumObjects;
        static const std::string RegioningTime;
        static const std::string DistanceMatrixTime;
        static const std::string FastClusterTime;
        static const std::string DendrogramTraversalTime;
        static const std::string EvalTime;
        static const std::string TotalTime;
        static const std::string TheoreticalNumWords;
        static const std::string OriginalBvNumWords;
        static const std::string OriginalSbvNumWords;
        static const std::string NewBvNumWords;
        static const std::string NewSbvNumWords;
        static const std::string NumRegions;
        static const std::string NumGtIntRegions;
        static const std::string LargestRegion;
        static const std::string BestCandidate;
        static const std::string NumNonTrivialRegionObjects;
 
    public:
        static std::vector<NodeID> cluster(BVDataPTAImpl *pta, const std::vector<std::pair<NodeID, unsigned>> keys, std::vector<std::pair<hclust_fast_methods, std::vector<NodeID>>> &candidates, std::string evalSubtitle="");
 
        // Returns a reverse node mapping for mapping generated by cluster().
        static std::vector<NodeID> getReverseNodeMapping(const std::vector<NodeID> &nodeMapping);
 
        static void evaluate(const std::vector<NodeID> &nodeMap, const Map<PointsTo, unsigned> pointsToSets, Map<std::string, std::string> &stats, bool accountForOcc);
 
        static void printStats(std::string title, Map<std::string, std::string> &stats);
 
    private:
        static inline size_t condensedIndex(size_t n, size_t i, size_t j);
 
        static inline unsigned requiredBits(const PointsTo &pts);
 
        static inline unsigned requiredBits(const size_t n);
 
        static inline double *getDistanceMatrix(const std::vector<std::pair<const PointsTo *, unsigned>> pointsToSets,
                                                const size_t numObjects, const Map<NodeID, unsigned> &nodeMap,
                                                double &distanceMatrixTime);
 
        static inline void traverseDendrogram(std::vector<NodeID> &nodeMap, const int *dendrogram, const size_t numObjects, unsigned &allocCounter, Set<int> &visited, const int index, const std::vector<NodeID> &regionNodeMap);
 
        static inline std::vector<unsigned> regionObjects(const Map<NodeID, Set<NodeID>> &graph, size_t numObjects, size_t &numLabels);
 
        // From all the candidates, returns the best mapping for pointsToSets (points-to set -> # occurrences).
        static inline std::pair<hclust_fast_methods, std::vector<NodeID>> determineBestMapping(
                    const std::vector<std::pair<hclust_fast_methods, std::vector<NodeID>>> &candidates,
                    Map<PointsTo, unsigned> pointsToSets, const std::string &evalSubtitle, double &evalTime);
 
    };
};
 
}  // namespace SVF
 
#endif  // ifdef NODEIDALLOCATOR_H_