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. More...
	PointsTo (const PointsTo &pt)
	Copy constructor. More...
	PointsTo (PointsTo &&pt) noexcept
	Move constructor. More...
	~PointsTo ()
PointsTo &	operator= (const PointsTo &rhs)
	Copy assignment. More...
PointsTo &	operator= (PointsTo &&rhs) noexcept
	Move assignment. More...
bool	empty () const
	Returns true if set is empty. More...
u32_t	count () const
	Returns number of elements. More...
void	clear ()
	Empty the set. More...
bool	test (u32_t n) const
	Returns true if n is in this set. More...
bool	test_and_set (u32_t n)
void	set (u32_t n)
	Inserts n in the set. More...
void	reset (u32_t n)
	Removes n from the set. More...
bool	contains (const PointsTo &rhs) const
	Returns true if this set is a superset of rhs. More...
bool	intersects (const PointsTo &rhs) const
	Returns true if this set and rhs share any elements. More...
int	find_first ()
bool	operator== (const PointsTo &rhs) const
	Returns true if this set and rhs contain exactly the same elements. More...
bool	operator!= (const PointsTo &rhs) const
	Returns true if either this set or rhs has an element not in the other. More...
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). More...
NodeBS	toNodeBS () const
	Returns this points-to set as a NodeBS. More...
size_t	hash () const
	Return a hash of this set. More...
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. More...
NodeID	getExternalNode (NodeID n) const
	Returns reverseNodeMapping[n], checking for nullptr and size. More...
bool	metaSame (const PointsTo &pt) const

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. More...
MappingPtr	nodeMapping
	External nodes -> internal nodes. More...
MappingPtr	reverseNodeMapping
	Internal nodes -> external nodes. More...

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

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 28 of file PointsTo.h.

Member Typedef Documentation

const_iterator

typedef PointsToIterator SVF::PointsTo::const_iterator

Definition at line 39 of file PointsTo.h.

iterator

typedef const_iterator SVF::PointsTo::iterator

Definition at line 40 of file PointsTo.h.

MappingPtr

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

Definition at line 42 of file PointsTo.h.

Member Enumeration Documentation

Type

enum SVF::PointsTo::Type

Enumerator
SBV
CBV
BV

Definition at line 31 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 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::~PointsTo: unknown type");
 
    nodeMapping = nullptr;
    reverseNodeMapping = nullptr;
}

Member Function Documentation

begin()

const_iterator SVF::PointsTo::begin ( ) const

inline

Definition at line 128 of file PointsTo.h.

    {
        return PointsToIterator(this);
    }

checkAndRemap()

void SVF::PointsTo::checkAndRemap

(

void

)

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

Definition at line 378 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 123 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 175 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 111 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();
    }
}

empty()

bool SVF::PointsTo::empty

(

)

const

Returns true if set is empty.

Definition at line 98 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 132 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 203 of file PointsTo.cpp.

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

getCurrentBestNodeMapping()

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

static

Definition at line 361 of file PointsTo.cpp.

{
    return currentBestNodeMapping;
}

getCurrentBestReverseNodeMapping()

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

static

Definition at line 366 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 349 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 342 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 337 of file PointsTo.cpp.

{
    return nodeMapping;
}

hash()

size_t SVF::PointsTo::hash

(

)

const

Return a hash of this set.

Definition at line 320 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 189 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 298 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 286 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 356 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 223 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 258 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 272 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 66 of file PointsTo.cpp.

{
    if (this == &rhs)
        return *this;
    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 83 of file PointsTo.cpp.

{
    this->type = rhs.type;
    this->nodeMapping = rhs.nodeMapping;
    this->reverseNodeMapping = rhs.reverseNodeMapping;
    // See comment in copy assignment.
    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 209 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 245 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 231 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 166 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 157 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 371 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 131 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 144 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 313 of file PointsTo.cpp.

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

Member Data Documentation

union { ... }

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

bv

BitVector SVF::PointsTo::bv

Bit vector backing.

Definition at line 170 of file PointsTo.h.

cbv

CoreBitVector SVF::PointsTo::cbv

Core bit vector backing.

Definition at line 168 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 157 of file PointsTo.h.

currentBestReverseNodeMapping

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

staticprivate

Likewise, but reversed.

Definition at line 159 of file PointsTo.h.

nodeMapping

MappingPtr SVF::PointsTo::nodeMapping

private

External nodes -> internal nodes.

Definition at line 176 of file PointsTo.h.

reverseNodeMapping

MappingPtr SVF::PointsTo::reverseNodeMapping

private

Internal nodes -> external nodes.

Definition at line 178 of file PointsTo.h.

sbv

SparseBitVector SVF::PointsTo::sbv

Sparse bit vector backing.

Definition at line 166 of file PointsTo.h.

type

enum Type SVF::PointsTo::type

private

Type of this points-to set.

Definition at line 159 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