SVF::PointsTo Class Reference

#include <PointsTo.h>

Classes
class	PointsToIterator

Public Types
enum	Type { SBV , CBV , BV }
typedef PointsToIterator	const_iterator
typedef const_iterator	iterator
typedef std::shared_ptr< std::vector< NodeID > >	MappingPtr

Public Member Functions
	PointsTo ()
	Construct empty points-to set.
	PointsTo (const PointsTo &pt)
	Copy constructor.
	PointsTo (PointsTo &&pt) noexcept
	Move constructor.
	~PointsTo ()
PointsTo &	operator= (const PointsTo &rhs)
	Copy assignment.
PointsTo &	operator= (PointsTo &&rhs) noexcept
	Move assignment.
bool	empty () const
	Returns true if set is empty.
u32_t	count () const
	Returns number of elements.
void	clear ()
	Empty the set.
bool	test (u32_t n) const
	Returns true if n is in this set.
bool	test_and_set (u32_t n)
void	set (u32_t n)
	Inserts n in the set.
void	reset (u32_t n)
	Removes n from the set.
bool	contains (const PointsTo &rhs) const
	Returns true if this set is a superset of rhs.
bool	intersects (const PointsTo &rhs) const
	Returns true if this set and rhs share any elements.
int	find_first ()
bool	operator== (const PointsTo &rhs) const
	Returns true if this set and rhs contain exactly the same elements.
bool	operator!= (const PointsTo &rhs) const
	Returns true if either this set or rhs has an element not in the other.
bool	operator|= (const PointsTo &rhs)
bool	operator|= (const NodeBS &rhs)
bool	operator&= (const PointsTo &rhs)
bool	operator-= (const PointsTo &rhs)
bool	intersectWithComplement (const PointsTo &rhs)
void	intersectWithComplement (const PointsTo &lhs, const PointsTo &rhs)
	Put intersection of lhs with complement of rhs into this set (overwrites).
NodeBS	toNodeBS () const
	Returns this points-to set as a NodeBS.
size_t	hash () const
	Return a hash of this set.
void	checkAndRemap ()
const_iterator	begin () const
const_iterator	end () const
MappingPtr	getNodeMapping () const

Static Public Member Functions
static MappingPtr	getCurrentBestNodeMapping ()
static MappingPtr	getCurrentBestReverseNodeMapping ()
static void	setCurrentBestNodeMapping (MappingPtr newCurrentBestNodeMapping, MappingPtr newCurrentBestReverseNodeMapping)

Private Member Functions
NodeID	getInternalNode (NodeID n) const
	Returns nodeMapping[n], checking for nullptr and size.
NodeID	getExternalNode (NodeID n) const
	Returns reverseNodeMapping[n], checking for nullptr and size.
bool	metaSame (const PointsTo &pt) const
void	destroyBacking ()

Private Attributes
union {
SparseBitVector   sbv
	Sparse bit vector backing. More...
CoreBitVector   cbv
	Core bit vector backing. More...
BitVector   bv
	Bit vector backing. More...
};
enum Type	type
	Type of this points-to set.
MappingPtr	nodeMapping
	External nodes -> internal nodes.
MappingPtr	reverseNodeMapping
	Internal nodes -> external nodes.

Static Private Attributes
static MappingPtr	currentBestNodeMapping = nullptr
	Best node mapping we know of the for the analyses at hand.
static MappingPtr	currentBestReverseNodeMapping = nullptr
	Likewise, but reversed.

Detailed Description

Wraps data structures to provide a points-to set. Underlying data structure can be changed globally. Includes support for mapping nodes for better internal representation.

Definition at line 29 of file PointsTo.h.

Member Typedef Documentation

const_iterator

typedef PointsToIterator SVF::PointsTo::const_iterator

Definition at line 40 of file PointsTo.h.

iterator

typedef const_iterator SVF::PointsTo::iterator

Definition at line 41 of file PointsTo.h.

MappingPtr

typedef std::shared_ptr<std::vector<NodeID> > SVF::PointsTo::MappingPtr

Definition at line 43 of file PointsTo.h.

Member Enumeration Documentation

Type

enum SVF::PointsTo::Type

Enumerator
SBV
CBV
BV

Definition at line 32 of file PointsTo.h.

    {
        SBV,
        CBV,
        BV,
    };

Constructor & Destructor Documentation

PointsTo() [1/3]

SVF::PointsTo::PointsTo

(

)

Construct empty points-to set.

Definition at line 25 of file PointsTo.cpp.

    : type(Options::PtType()), nodeMapping(currentBestNodeMapping),
      reverseNodeMapping(currentBestReverseNodeMapping)
{
    if (type == SBV) new (&sbv) SparseBitVector<>();
    else if (type == CBV) new (&cbv) CoreBitVector();
    else if (type == BV) new (&bv) BitVector();
    else assert(false && "PointsTo::PointsTo: unknown type");
}

PointsTo() [2/3]

SVF::PointsTo::PointsTo

(

const PointsTo &

pt

)

Copy constructor.

Definition at line 35 of file PointsTo.cpp.

    : type(pt.type), nodeMapping(pt.nodeMapping),
      reverseNodeMapping(pt.reverseNodeMapping)
{
    if (type == SBV) new (&sbv) SparseBitVector<>(pt.sbv);
    else if (type == CBV) new (&cbv) CoreBitVector(pt.cbv);
    else if (type == BV) new (&bv) BitVector(pt.bv);
    else assert(false && "PointsTo::PointsTo&: unknown type");
}

PointsTo() [3/3]

SVF::PointsTo::PointsTo ( PointsTo &&  pt )

noexcept

Move constructor.

Definition at line 45 of file PointsTo.cpp.

             : type(pt.type), nodeMapping(std::move(pt.nodeMapping)),
    reverseNodeMapping(std::move(pt.reverseNodeMapping))
{
    if (type == SBV) new (&sbv) SparseBitVector<>(std::move(pt.sbv));
    else if (type == CBV) new (&cbv) CoreBitVector(std::move(pt.cbv));
    else if (type == BV) new (&bv) BitVector(std::move(pt.bv));
    else assert(false && "PointsTo::PointsTo&&: unknown type");
}

~PointsTo()

SVF::PointsTo::~PointsTo

(

)

Definition at line 63 of file PointsTo.cpp.

{
    destroyBacking();
 
    nodeMapping = nullptr;
    reverseNodeMapping = nullptr;
}

Member Function Documentation

begin()

const_iterator SVF::PointsTo::begin ( ) const

inline

Definition at line 129 of file PointsTo.h.

    {
        return PointsToIterator(this);
    }

checkAndRemap()

void SVF::PointsTo::checkAndRemap

(

)

Checks if this points-to set is using the current best mapping. If not, remaps.

Definition at line 390 of file PointsTo.cpp.

{
    if (nodeMapping != currentBestNodeMapping)
    {
        // newPt constructed with correct node mapping.
        PointsTo newPt;
        for (const NodeID o : *this) newPt.set(o);
        *this = std::move(newPt);
    }
}

clear()

void SVF::PointsTo::clear

(

)

Empty the set.

Definition at line 135 of file PointsTo.cpp.

{
    if (type == CBV) cbv.clear();
    else if (type == SBV) sbv.clear();
    else if (type == BV) bv.clear();
    else assert(false && "PointsTo::clear: unknown type");
}

contains()

bool SVF::PointsTo::contains

(

const PointsTo &

rhs

)

const

Returns true if this set is a superset of rhs.

Definition at line 187 of file PointsTo.cpp.

{
    assert(metaSame(rhs) && "PointsTo::contains: mappings of operands do not match!");
 
    if (type == CBV) return cbv.contains(rhs.cbv);
    else if (type == SBV) return sbv.contains(rhs.sbv);
    else if (type == BV) return bv.contains(rhs.bv);
    else
    {
        assert(false && "PointsTo::contains: unknown type");
        abort();
    }
}

count()

u32_t SVF::PointsTo::count

(

void

)

const

Returns number of elements.

Definition at line 123 of file PointsTo.cpp.

{
    if (type == CBV) return cbv.count();
    else if (type == SBV) return sbv.count();
    else if (type == BV) return bv.count();
    else
    {
        assert(false && "PointsTo::count: unknown type");
        abort();
    }
}

destroyBacking()

void SVF::PointsTo::destroyBacking ( )

private

Ends the lifetime of the backing this set currently holds, through the type currently stored in type. Callers that then placement new a new backing must call this first, or whatever the old backing owned is lost.

Definition at line 55 of file PointsTo.cpp.

{
    if (type == SBV) sbv.~SparseBitVector<>();
    else if (type == CBV) cbv.~CoreBitVector();
    else if (type == BV) bv.~BitVector();
    else assert(false && "PointsTo::destroyBacking: unknown type");
}

empty()

bool SVF::PointsTo::empty

(

)

const

Returns true if set is empty.

Definition at line 110 of file PointsTo.cpp.

{
    if (type == CBV) return cbv.empty();
    else if (type == SBV) return sbv.empty();
    else if (type == BV) return bv.empty();
    else
    {
        assert(false && "PointsTo::empty: unknown type");
        abort();
    }
}

end()

const_iterator SVF::PointsTo::end ( ) const

inline

Definition at line 133 of file PointsTo.h.

    {
        return PointsToIterator(this, true);
    }

find_first()

int SVF::PointsTo::find_first

(

)

Returns the first element the set. Returns -1 when the set is empty. TODO: should we diverge from LLVM about the int return?

Definition at line 215 of file PointsTo.cpp.

{
    if (count() == 0) return -1;
    return *begin();
}

getCurrentBestNodeMapping()

PointsTo::MappingPtr SVF::PointsTo::getCurrentBestNodeMapping ( )

static

Definition at line 373 of file PointsTo.cpp.

{
    return currentBestNodeMapping;
}

getCurrentBestReverseNodeMapping()

PointsTo::MappingPtr SVF::PointsTo::getCurrentBestReverseNodeMapping ( )

static

Definition at line 378 of file PointsTo.cpp.

{
    return currentBestReverseNodeMapping;
}

getExternalNode()

NodeID SVF::PointsTo::getExternalNode ( NodeID  n ) const

private

Returns reverseNodeMapping[n], checking for nullptr and size.

Definition at line 361 of file PointsTo.cpp.

{
    if (reverseNodeMapping == nullptr) return n;
    assert(n < reverseNodeMapping->size());
    return reverseNodeMapping->at(n);
}

getInternalNode()

NodeID SVF::PointsTo::getInternalNode ( NodeID  n ) const

private

Returns nodeMapping[n], checking for nullptr and size.

Definition at line 354 of file PointsTo.cpp.

{
    if (nodeMapping == nullptr) return n;
    assert(n < nodeMapping->size());
    return nodeMapping->at(n);
}

getNodeMapping()

PointsTo::MappingPtr SVF::PointsTo::getNodeMapping

(

)

const

Definition at line 349 of file PointsTo.cpp.

{
    return nodeMapping;
}

hash()

size_t SVF::PointsTo::hash

(

)

const

Return a hash of this set.

Definition at line 332 of file PointsTo.cpp.

{
    if (type == CBV) return cbv.hash();
    else if (type == SBV)
    {
        std::hash<SparseBitVector<>> h;
        return h(sbv);
    }
    else if (type == BV) return bv.hash();
 
    else
    {
        assert(false && "PointsTo::hash: unknown type");
        abort();
    }
}

intersects()

bool SVF::PointsTo::intersects

(

const PointsTo &

rhs

)

const

Returns true if this set and rhs share any elements.

Definition at line 201 of file PointsTo.cpp.

{
    assert(metaSame(rhs) && "PointsTo::intersects: mappings of operands do not match!");
 
    if (type == CBV) return cbv.intersects(rhs.cbv);
    else if (type == SBV) return sbv.intersects(rhs.sbv);
    else if (type == BV) return bv.intersects(rhs.bv);
    else
    {
        assert(false && "PointsTo::intersects: unknown type");
        abort();
    }
}

intersectWithComplement() [1/2]

void SVF::PointsTo::intersectWithComplement	(	const PointsTo &	lhs,
		const PointsTo &	rhs
	)

Put intersection of lhs with complement of rhs into this set (overwrites).

Definition at line 310 of file PointsTo.cpp.

{
    assert(metaSame(rhs) && "PointsTo::intersectWithComplement: mappings of operands do not match!");
    assert(metaSame(lhs) && "PointsTo::intersectWithComplement: mappings of operands do not match!");
 
    if (type == CBV) cbv.intersectWithComplement(lhs.cbv, rhs.cbv);
    else if (type == SBV) sbv.intersectWithComplement(lhs.sbv, rhs.sbv);
    else if (type == BV) bv.intersectWithComplement(lhs.bv, rhs.bv);
    else
    {
        assert(false && "PointsTo::intersectWithComplement(PT, PT): unknown type");
        abort();
    }
}

intersectWithComplement() [2/2]

bool SVF::PointsTo::intersectWithComplement

(

const PointsTo &

rhs

)

Put intersection of this set with complement of rhs into this set. Returns true if this set changed.

Definition at line 298 of file PointsTo.cpp.

{
    assert(metaSame(rhs) && "PointsTo::intersectWithComplement: mappings of operands do not match!");
 
    if (type == CBV) return cbv.intersectWithComplement(rhs.cbv);
    else if (type == SBV) return sbv.intersectWithComplement(rhs.sbv);
    else if (type == BV) return bv.intersectWithComplement(rhs.bv);
 
    assert(false && "PointsTo::intersectWithComplement(PT): unknown type");
    abort();
}

metaSame()

bool SVF::PointsTo::metaSame ( const PointsTo &  pt ) const

private

Returns true if this points-to set and pt have the same type, nodeMapping, and reverseNodeMapping

Definition at line 368 of file PointsTo.cpp.

{
    return nodeMapping == pt.nodeMapping && reverseNodeMapping == pt.reverseNodeMapping;
}

operator!=()

bool SVF::PointsTo::operator!=

(

const PointsTo &

rhs

)

const

Returns true if either this set or rhs has an element not in the other.

Definition at line 235 of file PointsTo.cpp.

{
    // TODO: we're asserting and checking twice... should be okay...
    assert(metaSame(rhs) && "PointsTo::!=: mappings of operands do not match!");
 
    return !(*this == rhs);
}

operator&=()

bool SVF::PointsTo::operator&=

(

const PointsTo &

rhs

)

Put intersection of this set and rhs into this set. Returns true if this set changed.

Definition at line 270 of file PointsTo.cpp.

{
    assert(metaSame(rhs) && "PointsTo::&=: mappings of operands do not match!");
 
    if (type == CBV) return cbv &= rhs.cbv;
    else if (type == SBV) return sbv &= rhs.sbv;
    else if (type == BV) return bv &= rhs.bv;
    else
    {
        assert(false && "PointsTo::&=: unknown type");
        abort();
    }
}

operator-=()

bool SVF::PointsTo::operator-=

(

const PointsTo &

rhs

)

Remove elements in rhs from this set. Returns true if this set changed.

Definition at line 284 of file PointsTo.cpp.

{
    assert(metaSame(rhs) && "PointsTo::-=: mappings of operands do not match!");
 
    if (type == CBV) return cbv.intersectWithComplement(rhs.cbv);
    else if (type == SBV) return sbv.intersectWithComplement(rhs.sbv);
    else if (type == BV) return bv.intersectWithComplement(rhs.bv);
    else
    {
        assert(false && "PointsTo::-=: unknown type");
        abort();
    }
}

operator=() [1/2]

PointsTo & SVF::PointsTo::operator=

(

const PointsTo &

rhs

)

Copy assignment.

Definition at line 71 of file PointsTo.cpp.

{
    if (this == &rhs)
        return *this;
    // End the lifetime of the backing held now before placement new builds the
    // new one over it. Destroy through the type stored now, which may differ
    // from rhs's. Without this the old backing's storage is never freed.
    destroyBacking();
    this->type = rhs.type;
    this->nodeMapping = rhs.nodeMapping;
    this->reverseNodeMapping = rhs.reverseNodeMapping;
    // Placement new because if type has changed, we have
    // not constructed the new type yet.
    if (type == SBV) new (&sbv) SparseBitVector<>(rhs.sbv);
    else if (type == CBV) new (&cbv) CoreBitVector(rhs.cbv);
    else if (type == BV) new (&bv) BitVector(rhs.bv);
    else assert(false && "PointsTo::PointsTo=&: unknown type");
 
    return *this;
}

operator=() [2/2]

PointsTo & SVF::PointsTo::operator= ( PointsTo &&  rhs )

noexcept

Move assignment.

Definition at line 92 of file PointsTo.cpp.

{
    if (this == &rhs)
        return *this;
    // See comment in copy assignment.
    destroyBacking();
    this->type = rhs.type;
    this->nodeMapping = rhs.nodeMapping;
    this->reverseNodeMapping = rhs.reverseNodeMapping;
    if (type == SBV) new (&sbv) SparseBitVector<>(std::move(rhs.sbv));
    else if (type == CBV) new (&cbv) CoreBitVector(std::move(rhs.cbv));
    else if (type == BV) new (&bv) BitVector(std::move(rhs.bv));
    else assert(false && "PointsTo::PointsTo=&&: unknown type");
 
    return *this;
}

operator==()

bool SVF::PointsTo::operator==

(

const PointsTo &

rhs

)

const

Returns true if this set and rhs contain exactly the same elements.

Definition at line 221 of file PointsTo.cpp.

{
    assert(metaSame(rhs) && "PointsTo::==: mappings of operands do not match!");
 
    if (type == CBV) return cbv == rhs.cbv;
    else if (type == SBV) return sbv == rhs.sbv;
    else if (type == BV) return bv == rhs.bv;
    else
    {
        assert(false && "PointsTo::==: unknown type");
        abort();
    }
}

operator|=() [1/2]

bool SVF::PointsTo::operator|=

(

const NodeBS &

rhs

)

Definition at line 257 of file PointsTo.cpp.

{
    // TODO:
    bool changed = false;
    for (NodeID n : rhs)
    {
        if (changed) set(n);
        else changed = test_and_set(n);
    }
 
    return changed;
}

operator|=() [2/2]

bool SVF::PointsTo::operator|=

(

const PointsTo &

rhs

)

Put union of this set and rhs into this set. Returns true if this set changed.

Definition at line 243 of file PointsTo.cpp.

{
    assert(metaSame(rhs) && "PointsTo::|=: mappings of operands do not match!");
 
    if (type == CBV) return cbv |= rhs.cbv;
    else if (type == SBV) return sbv |= rhs.sbv;
    else if (type == BV) return bv |= rhs.bv;
    else
    {
        assert(false && "PointsTo::|=: unknown type");
        abort();
    }
}

reset()

void SVF::PointsTo::reset

(

u32_t

n

)

Removes n from the set.

Definition at line 178 of file PointsTo.cpp.

{
    n = getInternalNode(n);
    if (type == CBV) cbv.reset(n);
    else if (type == SBV) sbv.reset(n);
    else if (type == BV) bv.reset(n);
    else assert(false && "PointsTo::reset: unknown type");
}

set()

void SVF::PointsTo::set

(

u32_t

n

)

Inserts n in the set.

Definition at line 169 of file PointsTo.cpp.

{
    n = getInternalNode(n);
    if (type == CBV) cbv.set(n);
    else if (type == SBV) sbv.set(n);
    else if (type == BV) bv.set(n);
    else assert(false && "PointsTo::set: unknown type");
}

setCurrentBestNodeMapping()

void SVF::PointsTo::setCurrentBestNodeMapping ( MappingPtr  newCurrentBestNodeMapping, MappingPtr  newCurrentBestReverseNodeMapping  )

static

Definition at line 383 of file PointsTo.cpp.

{
    currentBestNodeMapping = std::move(newCurrentBestNodeMapping);
    currentBestReverseNodeMapping = std::move(newCurrentBestReverseNodeMapping);
}

test()

bool SVF::PointsTo::test

(

u32_t

n

)

const

Returns true if n is in this set.

Definition at line 143 of file PointsTo.cpp.

{
    n = getInternalNode(n);
    if (type == CBV) return cbv.test(n);
    else if (type == SBV) return sbv.test(n);
    else if (type == BV) return bv.test(n);
    else
    {
        assert(false && "PointsTo::test: unknown type");
        abort();
    }
}

test_and_set()

bool SVF::PointsTo::test_and_set

(

u32_t

n

)

Check if n is in set. If it is, returns false. Otherwise, inserts n and returns true.

Definition at line 156 of file PointsTo.cpp.

{
    n = getInternalNode(n);
    if (type == CBV) return cbv.test_and_set(n);
    else if (type == SBV) return sbv.test_and_set(n);
    else if (type == BV) return bv.test_and_set(n);
    else
    {
        assert(false && "PointsTo::test_and_set: unknown type");
        abort();
    }
}

toNodeBS()

NodeBS SVF::PointsTo::toNodeBS

(

)

const

Returns this points-to set as a NodeBS.

Definition at line 325 of file PointsTo.cpp.

{
    NodeBS nbs;
    for (const NodeID o : *this) nbs.set(o);
    return nbs;
}

Member Data Documentation

[union]

union { ... } SVF::PointsTo

Holds backing data structure. TODO: std::variant when we move to C++17.

bv

BitVector SVF::PointsTo::bv

Bit vector backing.

Definition at line 176 of file PointsTo.h.

cbv

CoreBitVector SVF::PointsTo::cbv

Core bit vector backing.

Definition at line 174 of file PointsTo.h.

currentBestNodeMapping

PointsTo::MappingPtr SVF::PointsTo::currentBestNodeMapping = nullptr

staticprivate

Best node mapping we know of the for the analyses at hand.

Definition at line 163 of file PointsTo.h.

currentBestReverseNodeMapping

PointsTo::MappingPtr SVF::PointsTo::currentBestReverseNodeMapping = nullptr

staticprivate

Likewise, but reversed.

Definition at line 165 of file PointsTo.h.

nodeMapping

MappingPtr SVF::PointsTo::nodeMapping

private

External nodes -> internal nodes.

Definition at line 182 of file PointsTo.h.

reverseNodeMapping

MappingPtr SVF::PointsTo::reverseNodeMapping

private

Internal nodes -> external nodes.

Definition at line 184 of file PointsTo.h.

sbv

SparseBitVector SVF::PointsTo::sbv

Sparse bit vector backing.

Definition at line 172 of file PointsTo.h.

type

enum Type SVF::PointsTo::type

private

Type of this points-to set.

Definition at line 180 of file PointsTo.h.

---

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

• /home/runner/work/SVF/SVF/svf/include/MemoryModel/PointsTo.h
• /home/runner/work/SVF/SVF/svf/lib/MemoryModel/PointsTo.cpp