#include <PersistentPointsToCache.h>

Public Types
typedef Map< Data, PointsToID >	PTSToIDMap

typedef std::function< Data(const Data &, const Data &)>	DataOp

typedef Map< std::pair< PointsToID, PointsToID >, PointsToID >	OpCache

Public Member Functions
	PersistentPointsToCache (void)

void	clear ()
	Clear the cache.

void	reset (void)
	Resets the cache removing everything except the emptyData it was initialised with.

void	remapAllPts (void)
	Remaps all points-to sets stored in the cache to the current mapping.

PointsToID	emplacePts (const Data &pts)

const Data &	getActualPts (PointsToID id) const
	Returns the points-to set which id represents. id must be stored in the cache.

PointsToID	unionPts (PointsToID lhs, PointsToID rhs)
	Unions lhs and rhs and returns their union's ID.

PointsToID	complementPts (PointsToID lhs, PointsToID rhs)
	Relatively complements lhs and rhs (lhs \ rhs) and returns it's ID.

PointsToID	intersectPts (PointsToID lhs, PointsToID rhs)
	Intersects lhs and rhs (lhs AND rhs) and returns the intersection's ID.

void	printStats (const std::string subtitle) const
	Print statistics on operations and points-to set numbers.

Map< Data, unsigned >	getAllPts (void)

Static Public Member Functions
static PointsToID	emptyPointsToId (void)

Private Member Functions
PointsToID	newPointsToId (void)

PointsToID	opPts (PointsToID lhs, PointsToID rhs, const DataOp &dataOp, OpCache &opCache, bool commutative, bool &opPerformed)

void	initStats (void)
	Initialises statistics variables to 0.

Private Attributes
std::vector< std::unique_ptr< Data > >	idToPts

PTSToIDMap	ptsToId
	Maps points-to sets to their corresponding ID.

OpCache	unionCache
	Maps two IDs to their union. Keys must be sorted.

OpCache	complementCache
	Maps two IDs to their relative complement.

OpCache	intersectionCache
	Maps two IDs to their intersection. Keys must be sorted.

PointsToID	idCounter
	Used to generate new PointsToIDs. Any non-zero is valid.

u64_t	totalUnions

u64_t	uniqueUnions

u64_t	propertyUnions

u64_t	lookupUnions

u64_t	preemptiveUnions

u64_t	totalComplements

u64_t	uniqueComplements

u64_t	propertyComplements

u64_t	lookupComplements

u64_t	preemptiveComplements

u64_t	totalIntersections

u64_t	uniqueIntersections

u64_t	propertyIntersections

u64_t	lookupIntersections

u64_t	preemptiveIntersections

Detailed Description

template<typename Data>
class SVF::PersistentPointsToCache< Data >

Persistent points-to set store. Can be used as a backing for points-to data structures like PointsToDS and PointsToDFDS. Hides points-to sets and union operations from users and hands out PointsToIDs. Points-to sets are interned, and union operations are lazy and hash-consed.

Definition at line 32 of file PersistentPointsToCache.h.

Member Typedef Documentation

◆ DataOp

template<typename Data >

typedef std::function<Data(const Data &, const Data &)> SVF::PersistentPointsToCache< Data >::DataOp

Definition at line 36 of file PersistentPointsToCache.h.

◆ OpCache

template<typename Data >

typedef Map<std::pair<PointsToID, PointsToID>, PointsToID> SVF::PersistentPointsToCache< Data >::OpCache

Definition at line 38 of file PersistentPointsToCache.h.

◆ PTSToIDMap

template<typename Data >

typedef Map<Data, PointsToID> SVF::PersistentPointsToCache< Data >::PTSToIDMap

Definition at line 35 of file PersistentPointsToCache.h.

Constructor & Destructor Documentation

◆ PersistentPointsToCache()

template<typename Data >

SVF::PersistentPointsToCache< Data >::PersistentPointsToCache ( void )

inline

Definition at line 46 of file PersistentPointsToCache.h.

                                  : idCounter(1)
    {
        idToPts.push_back(std::make_unique<Data>());
        ptsToId[Data()] = emptyPointsToId();
 
        initStats();
    }

Member Function Documentation

◆ clear()

template<typename Data >

void SVF::PersistentPointsToCache< Data >::clear ( )

inline

Clear the cache.

Definition at line 55 of file PersistentPointsToCache.h.

    {
        idToPts.clear();
        ptsToId.clear();
 
        unionCache.clear();
        complementCache.clear();
        intersectionCache.clear();
    }

◆ complementPts()

template<typename Data >

PointsToID SVF::PersistentPointsToCache< Data >::complementPts	(	PointsToID	lhs,
		PointsToID	rhs
	)

inline

Relatively complements lhs and rhs (lhs \ rhs) and returns it's ID.

Definition at line 173 of file PersistentPointsToCache.h.

    {
        static const DataOp complementOp = [](const Data &lhs, const Data &rhs)
        {
            return lhs - rhs;
        };
 
        ++totalComplements;
 
        // Property cases.
        // x - x
        if (lhs == rhs)
        {
            ++propertyComplements;
            return emptyPointsToId();
        }
 
        // x - EMPTY_SET
        if (rhs == emptyPointsToId())
        {
            ++propertyComplements;
            return lhs;
        }
 
        // EMPTY_SET - x
        if (lhs == emptyPointsToId())
        {
            ++propertyComplements;
            return emptyPointsToId();
        }
 
        bool opPerformed = false;
        const PointsToID result = opPts(lhs, rhs, complementOp, complementCache, false, opPerformed);
 
        if (opPerformed)
        {
            ++uniqueComplements;
 
            // We performed lhs - rhs = result, so...
            if (result != emptyPointsToId())
            {
                // result AND rhs = EMPTY_SET,
                intersectionCache[std::minmax(result, rhs)] = emptyPointsToId();
                ++preemptiveIntersections;
                ++totalIntersections;
 
                // and result AND lhs = result,
                intersectionCache[std::minmax(result, lhs)] = result;
                ++preemptiveIntersections;
                ++totalIntersections;
 
                // and result - rhs = result.
                complementCache[std::make_pair(result, rhs)] = result;
                ++preemptiveComplements;
                ++totalComplements;
            }
        }
        else ++lookupComplements;
 
        return result;
    }

◆ emplacePts()

template<typename Data >

PointsToID SVF::PersistentPointsToCache< Data >::emplacePts ( const Data & pts )

inline

If pts is not in the PersistentPointsToCache, inserts it, assigns an ID, and returns that ID. If it is, then the ID is returned.

Definition at line 91 of file PersistentPointsToCache.h.

    {
        // Is it already in the cache?
        typename PTSToIDMap::const_iterator foundId = ptsToId.find(pts);
        if (foundId != ptsToId.end()) return foundId->second;
 
        // Otherwise, insert it.
        PointsToID id = newPointsToId();
        idToPts.push_back(std::make_unique<Data>(pts));
        ptsToId[pts] = id;
 
        return id;
    }

◆ emptyPointsToId()

template<typename Data >

static PointsToID SVF::PersistentPointsToCache< Data >::emptyPointsToId ( void )

inlinestatic

Definition at line 40 of file PersistentPointsToCache.h.

    {
        return 0;
    };

◆ getActualPts()

template<typename Data >

const Data & SVF::PersistentPointsToCache< Data >::getActualPts ( PointsToID id ) const

inline

Returns the points-to set which id represents. id must be stored in the cache.

Definition at line 106 of file PersistentPointsToCache.h.

    {
        // Check if the points-to set for ID has already been stored.
        assert(idToPts.size() > id && "PPTC::getActualPts: points-to set not stored!");
        return *idToPts.at(id);
    }

◆ getAllPts()

template<typename Data >

Map< Data, unsigned > SVF::PersistentPointsToCache< Data >::getAllPts ( void )

inline

Returns all points-to sets stored by this cache as keys to a map. Values are all 1. We use the map to be more compatible with getAllPts in the various PTDatas. Performance is a non-issue (for now) since this is just used for evaluation's sake.

Definition at line 345 of file PersistentPointsToCache.h.

    {
        Map<Data, unsigned> allPts;
        for (const auto &d : idToPts) allPts[*d] = 1;
        return allPts;
    }

◆ initStats()

template<typename Data >

void SVF::PersistentPointsToCache< Data >::initStats ( void )

inlineprivate

Initialises statistics variables to 0.

Definition at line 403 of file PersistentPointsToCache.h.

    {
 
        totalUnions              = 0;
        uniqueUnions             = 0;
        propertyUnions           = 0;
        lookupUnions             = 0;
        preemptiveUnions         = 0;
        totalComplements         = 0;
        uniqueComplements        = 0;
        propertyComplements      = 0;
        lookupComplements        = 0;
        preemptiveComplements    = 0;
        totalIntersections       = 0;
        uniqueIntersections      = 0;
        propertyIntersections    = 0;
        lookupIntersections      = 0;
        preemptiveIntersections  = 0;
    }

◆ intersectPts()

template<typename Data >

PointsToID SVF::PersistentPointsToCache< Data >::intersectPts	(	PointsToID	lhs,
		PointsToID	rhs
	)

inline

Intersects lhs and rhs (lhs AND rhs) and returns the intersection's ID.

Definition at line 236 of file PersistentPointsToCache.h.

    {
        static const DataOp intersectionOp = [](const Data &lhs, const Data &rhs)
        {
            return lhs & rhs;
        };
 
        ++totalIntersections;
 
        // Order operands so we don't perform x U y and y U x separately.
        std::pair<PointsToID, PointsToID> operands = std::minmax(lhs, rhs);
 
        // Property cases.
        // EMPTY_SET & x
        if (operands.first == emptyPointsToId())
        {
            ++propertyIntersections;
            return emptyPointsToId();
        }
 
        // x & x
        if (operands.first == operands.second)
        {
            ++propertyIntersections;
            return operands.first;
        }
 
        bool opPerformed = false;
        const PointsToID result = opPts(lhs, rhs, intersectionOp, intersectionCache, true, opPerformed);
        if (opPerformed)
        {
            ++uniqueIntersections;
 
            // When the result is empty, we won't be adding anything of substance.
            if (result != emptyPointsToId())
            {
                // We performed lhs AND rhs = result, so...
                // result AND rhs = result,
                if (result != rhs)
                {
                    intersectionCache[std::minmax(result, rhs)] = result;
                    ++preemptiveIntersections;
                    ++totalIntersections;
                }
 
                // and result AND lhs = result,
                if (result != lhs)
                {
                    intersectionCache[std::minmax(result, lhs)] = result;
                    ++preemptiveIntersections;
                    ++totalIntersections;
                }
 
                // Also (thanks reviewer #2)
                // result U lhs = result,
                if (result != emptyPointsToId() && result != lhs)
                {
                    unionCache[std::minmax(lhs, result)] = lhs;
                    ++preemptiveUnions;
                    ++totalUnions;
                }
 
                // And result U rhs = rhs.
                if (result != emptyPointsToId() && result != rhs)
                {
                    unionCache[std::minmax(rhs, result)] = rhs;
                    ++preemptiveUnions;
                    ++totalUnions;
                }
            }
        }
        else ++lookupIntersections;
 
        return result;
    }

◆ newPointsToId()

template<typename Data >

PointsToID SVF::PersistentPointsToCache< Data >::newPointsToId ( void )

inlineprivate

Definition at line 355 of file PersistentPointsToCache.h.

    {
        // Make sure we don't overflow.
        assert(idCounter != emptyPointsToId() && "PPTC::newPointsToId: PointsToIDs exhausted! Try a larger type.");
        return idCounter++;
    }

◆ opPts()

template<typename Data >

PointsToID SVF::PersistentPointsToCache< Data >::opPts	(	PointsToID	lhs,
		PointsToID	rhs,
		const DataOp &	dataOp,
		OpCache &	opCache,
		bool	commutative,
		bool &	opPerformed
	)

inlineprivate

Performs dataOp on lhs and rhs, checking the opCache first and updating it afterwards. commutative indicates whether the operation in question is commutative or not. opPerformed is set to true if the operation was not cached and thus performed, false otherwise.

Definition at line 365 of file PersistentPointsToCache.h.

    {
        std::pair<PointsToID, PointsToID> operands;
        // If we're commutative, we want to always perform the same operation: x op y.
        // Performing x op y sometimes and y op x other times is a waste of time.
        if (commutative) operands = std::minmax(lhs, rhs);
        else operands = std::make_pair(lhs, rhs);
 
        // Check if we have performed this operation
        OpCache::const_iterator foundResult = opCache.find(operands);
        if (foundResult != opCache.end()) return foundResult->second;
 
        opPerformed = true;
 
        const Data &lhsPts = getActualPts(lhs);
        const Data &rhsPts = getActualPts(rhs);
 
        Data result = dataOp(lhsPts, rhsPts);
 
        PointsToID resultId;
        // Intern points-to set: check if result already exists.
        typename PTSToIDMap::const_iterator foundId = ptsToId.find(result);
        if (foundId != ptsToId.end()) resultId = foundId->second;
        else
        {
            resultId = newPointsToId();
            idToPts.push_back(std::make_unique<Data>(result));
            ptsToId[result] = resultId;
        }
 
        // Cache the result, for hash-consing.
        opCache[operands] = resultId;
 
        return resultId;
    }

◆ printStats()

template<typename Data >

void SVF::PersistentPointsToCache< Data >::printStats ( const std::string subtitle ) const

inline

Print statistics on operations and points-to set numbers.

Definition at line 313 of file PersistentPointsToCache.h.

    {
        static const unsigned fieldWidth = 25;
        SVFUtil::outs().flags(std::ios::left);
 
        SVFUtil::outs() << std::setw(fieldWidth) << "UniquePointsToSets"      << idToPts.size()          << "\n";
 
        SVFUtil::outs() << std::setw(fieldWidth) << "TotalUnions"             << totalUnions             << "\n";
        SVFUtil::outs() << std::setw(fieldWidth) << "PropertyUnions"          << propertyUnions          << "\n";
        SVFUtil::outs() << std::setw(fieldWidth) << "UniqueUnions"            << uniqueUnions            << "\n";
        SVFUtil::outs() << std::setw(fieldWidth) << "LookupUnions"            << lookupUnions            << "\n";
        SVFUtil::outs() << std::setw(fieldWidth) << "PreemptiveUnions"        << preemptiveUnions        << "\n";
 
        SVFUtil::outs() << std::setw(fieldWidth) << "TotalComplements"        << totalComplements        << "\n";
        SVFUtil::outs() << std::setw(fieldWidth) << "PropertyComplements"     << propertyComplements     << "\n";
        SVFUtil::outs() << std::setw(fieldWidth) << "UniqueComplements"       << uniqueComplements       << "\n";
        SVFUtil::outs() << std::setw(fieldWidth) << "LookupComplements"       << lookupComplements       << "\n";
        SVFUtil::outs() << std::setw(fieldWidth) << "PreemptiveComplements"   << preemptiveComplements   << "\n";
 
        SVFUtil::outs() << std::setw(fieldWidth) << "TotalIntersections"      << totalIntersections      << "\n";
        SVFUtil::outs() << std::setw(fieldWidth) << "PropertyIntersections"   << propertyIntersections   << "\n";
        SVFUtil::outs() << std::setw(fieldWidth) << "UniqueIntersections"     << uniqueIntersections     << "\n";
        SVFUtil::outs() << std::setw(fieldWidth) << "LookupIntersections"     << lookupIntersections     << "\n";
        SVFUtil::outs() << std::setw(fieldWidth) << "PreemptiveIntersections" << preemptiveIntersections << "\n";
 
        SVFUtil::outs().flush();
    }

◆ remapAllPts()

template<typename Data >

void SVF::PersistentPointsToCache< Data >::remapAllPts ( void )

inline

Remaps all points-to sets stored in the cache to the current mapping.

Definition at line 80 of file PersistentPointsToCache.h.

    {
        for (auto &d : idToPts) d->checkAndRemap();
 
        // Rebuild ptsToId from idToPts.
        ptsToId.clear();
        for (PointsToID i = 0; i < idToPts.size(); ++i) ptsToId[*idToPts[i]] = i;
    }

◆ reset()

template<typename Data >

void SVF::PersistentPointsToCache< Data >::reset ( void )

inline

Resets the cache removing everything except the emptyData it was initialised with.

Definition at line 66 of file PersistentPointsToCache.h.

    {
        clear();
 
        // Put the empty data back in.
        ptsToId[Data()] = emptyPointsToId();
        idToPts.push_back(std::make_unique<Data>());
 
        idCounter = 1;
        // Cache is empty...
        initStats();
    }

◆ unionPts()

template<typename Data >

PointsToID SVF::PersistentPointsToCache< Data >::unionPts	(	PointsToID	lhs,
		PointsToID	rhs
	)

inline

Unions lhs and rhs and returns their union's ID.

Definition at line 114 of file PersistentPointsToCache.h.

    {
        static const DataOp unionOp = [](const Data &lhs, const Data &rhs)
        {
            return lhs | rhs;
        };
 
        ++totalUnions;
 
        // Order operands so we don't perform x U y and y U x separately.
        std::pair<PointsToID, PointsToID> operands = std::minmax(lhs, rhs);
 
        // Property cases.
        // EMPTY_SET U x
        if (operands.first == emptyPointsToId())
        {
            ++propertyUnions;
            return operands.second;
        }
 
        // x U x
        if (operands.first == operands.second)
        {
            ++propertyUnions;
            return operands.first;
        }
 
        bool opPerformed = false;
        PointsToID result = opPts(lhs, rhs, unionOp, unionCache, true, opPerformed);
 
        if (opPerformed)
        {
            ++uniqueUnions;
 
            // We can use lhs/rhs here rather than our ordered operands,
            // because the operation was commutative.
 
            // if x U y = z, then x U z = z,
            if (lhs != result)
            {
                unionCache[std::minmax(lhs, result)] = result;
                ++preemptiveUnions;
                ++totalUnions;
            }
 
            // and y U z = z.
            if (rhs != result)
            {
                unionCache[std::minmax(rhs, result)] = result;
                ++preemptiveUnions;
                ++totalUnions;
            }
        }
        else ++lookupUnions;
 
        return result;
    }

Member Data Documentation

◆ complementCache

template<typename Data >

OpCache SVF::PersistentPointsToCache< Data >::complementCache

private

Maps two IDs to their relative complement.

Definition at line 436 of file PersistentPointsToCache.h.

◆ idCounter

template<typename Data >

PointsToID SVF::PersistentPointsToCache< Data >::idCounter

private

Used to generate new PointsToIDs. Any non-zero is valid.

Definition at line 441 of file PersistentPointsToCache.h.

◆ idToPts

template<typename Data >

std::vector<std::unique_ptr<Data> > SVF::PersistentPointsToCache< Data >::idToPts

private

Maps points-to IDs (indices) to their corresponding points-to set. Reverse of idToPts. Elements are only added through push_back, so the number of elements stored is the size of the vector. Not const so we can remap.

Definition at line 429 of file PersistentPointsToCache.h.

◆ intersectionCache

template<typename Data >

OpCache SVF::PersistentPointsToCache< Data >::intersectionCache

private

Maps two IDs to their intersection. Keys must be sorted.

Definition at line 438 of file PersistentPointsToCache.h.

◆ lookupComplements

template<typename Data >

u64_t SVF::PersistentPointsToCache< Data >::lookupComplements

private

Definition at line 452 of file PersistentPointsToCache.h.

◆ lookupIntersections

template<typename Data >

u64_t SVF::PersistentPointsToCache< Data >::lookupIntersections

private

Definition at line 457 of file PersistentPointsToCache.h.

◆ lookupUnions

template<typename Data >

u64_t SVF::PersistentPointsToCache< Data >::lookupUnions

private

Definition at line 447 of file PersistentPointsToCache.h.

◆ preemptiveComplements

template<typename Data >

u64_t SVF::PersistentPointsToCache< Data >::preemptiveComplements

private

Definition at line 453 of file PersistentPointsToCache.h.

◆ preemptiveIntersections

template<typename Data >

u64_t SVF::PersistentPointsToCache< Data >::preemptiveIntersections

private

Definition at line 458 of file PersistentPointsToCache.h.

◆ preemptiveUnions

template<typename Data >

u64_t SVF::PersistentPointsToCache< Data >::preemptiveUnions

private

Definition at line 448 of file PersistentPointsToCache.h.

◆ propertyComplements

template<typename Data >

u64_t SVF::PersistentPointsToCache< Data >::propertyComplements

private

Definition at line 451 of file PersistentPointsToCache.h.

◆ propertyIntersections

template<typename Data >

u64_t SVF::PersistentPointsToCache< Data >::propertyIntersections

private

Definition at line 456 of file PersistentPointsToCache.h.

◆ propertyUnions

template<typename Data >

u64_t SVF::PersistentPointsToCache< Data >::propertyUnions

private

Definition at line 446 of file PersistentPointsToCache.h.

◆ ptsToId

template<typename Data >

PTSToIDMap SVF::PersistentPointsToCache< Data >::ptsToId

private

Maps points-to sets to their corresponding ID.

Definition at line 431 of file PersistentPointsToCache.h.

◆ totalComplements

template<typename Data >

u64_t SVF::PersistentPointsToCache< Data >::totalComplements

private

Definition at line 449 of file PersistentPointsToCache.h.

◆ totalIntersections

template<typename Data >

u64_t SVF::PersistentPointsToCache< Data >::totalIntersections

private

Definition at line 454 of file PersistentPointsToCache.h.

◆ totalUnions

template<typename Data >

u64_t SVF::PersistentPointsToCache< Data >::totalUnions

private

Definition at line 444 of file PersistentPointsToCache.h.

◆ unionCache

template<typename Data >

OpCache SVF::PersistentPointsToCache< Data >::unionCache

private

Maps two IDs to their union. Keys must be sorted.

Definition at line 434 of file PersistentPointsToCache.h.

◆ uniqueComplements

template<typename Data >

u64_t SVF::PersistentPointsToCache< Data >::uniqueComplements

private

Definition at line 450 of file PersistentPointsToCache.h.

◆ uniqueIntersections

template<typename Data >

u64_t SVF::PersistentPointsToCache< Data >::uniqueIntersections

private

Definition at line 455 of file PersistentPointsToCache.h.

◆ uniqueUnions

template<typename Data >

u64_t SVF::PersistentPointsToCache< Data >::uniqueUnions

private

Definition at line 445 of file PersistentPointsToCache.h.

The documentation for this class was generated from the following file:

/home/runner/work/SVF/SVF/svf/include/MemoryModel/PersistentPointsToCache.h

Public Types

Public Member Functions

Static Public Member Functions

Private Member Functions

Private Attributes

Detailed Description

Member Typedef Documentation

◆ DataOp

◆ OpCache

◆ PTSToIDMap

Constructor & Destructor Documentation

◆ PersistentPointsToCache()

Member Function Documentation

◆ clear()

◆ complementPts()

◆ emplacePts()

◆ emptyPointsToId()

◆ getActualPts()

◆ getAllPts()

◆ initStats()

◆ intersectPts()

◆ newPointsToId()

◆ opPts()

◆ printStats()

◆ remapAllPts()

◆ reset()

◆ unionPts()

Member Data Documentation

◆ complementCache

◆ idCounter

◆ idToPts

◆ intersectionCache

◆ lookupComplements

◆ lookupIntersections

◆ lookupUnions

◆ preemptiveComplements

◆ preemptiveIntersections

◆ preemptiveUnions

◆ propertyComplements

◆ propertyIntersections

◆ propertyUnions

◆ ptsToId

◆ totalComplements

◆ totalIntersections

◆ totalUnions

◆ unionCache

◆ uniqueComplements

◆ uniqueIntersections

◆ uniqueUnions