#include <NodeIDAllocator.h>

Classes
class	Clusterer

Public Types
enum	Strategy { DENSE , REVERSE_DENSE , SEQ , DBUG }
	Allocation strategy to use. More...

Public Member Functions
NodeID	allocateObjectId (void)
	Allocate an object ID as determined by the strategy.

NodeID	allocateTypeId (void)
	Allocate an type ID as determined by the strategy.

NodeID	allocateGepObjectId (NodeID base, u32_t offset, u32_t maxFieldLimit)

NodeID	allocateValueId (void)
	Allocate a value ID as determined by the strategy.

NodeID	endSymbolAllocation (void)
	Notify the allocator that all symbols have had IDs allocated.

NodeID	getNumObjects (void) const
	Returns the total number of memory objects.

void	increaseNumOfObjAndNodes ()

void	increaseNumOfValues ()

int	getNumOfNodes ()

Static Public Member Functions
static NodeIDAllocator *	get (void)
	Return (singleton) allocator.

static void	unset (void)
	Deletes the (singleton) allocator.

Static Public Attributes

static const NodeID	blackHoleObjectId = 0

static const NodeID	constantObjectId = 1

static const NodeID	blackHolePointerId = 2

static const NodeID	nullPointerId = 3

Private Member Functions
	NodeIDAllocator (void)
	Builds a node ID allocator with the strategy specified on the command line.

Private Attributes
enum Strategy	strategy
	Strategy to allocate with.


NodeID	numObjects

NodeID	numValues
	Number of values allocated, including specials.

NodeID	numSymbols
	Number of explicit symbols allocated (e.g., llvm::Values), including specials.

NodeID	numNodes
	Total number of objects and values allocated.

NodeID	numType
	Total number of svftypes.

Static Private Attributes
static NodeIDAllocator *	allocator = nullptr
	Single allocator.

Detailed Description

Allocates node IDs for objects and values, upon request, according to some strategy which can be user-defined. It is the job of SymbolTableInfo to tell the NodeIDAllocator when all symbols have been allocated through endSymbolAllocation.

Definition at line 20 of file NodeIDAllocator.h.

Member Enumeration Documentation

◆ Strategy

enum SVF::NodeIDAllocator::Strategy

Allocation strategy to use.

Enumerator
DENSE	Allocate objects contiguously, separate from values, and vice versa. If [**...***] is the space of unsigned integers, we allocate as, [ssssooooooo...vvvvvvv] (o = object, v = value, s = special).
REVERSE_DENSE	Like dense, but with order flipped: [ssssvvvvvvv...ooooooo]
SEQ	Allocate objects objects and values sequentially, intermixed.
DBUG	Allocate values and objects as they come in with a single counter. GEP objects are allocated as an offset from their base (see implementation of allocateGepObjectId). The purpose of this allocation strategy is human readability.

Definition at line 25 of file NodeIDAllocator.h.

    {
        DENSE,
        REVERSE_DENSE,
        SEQ,
        DBUG,
    };

Constructor & Destructor Documentation

◆ NodeIDAllocator()

SVF::NodeIDAllocator::NodeIDAllocator ( void )

private

Builds a node ID allocator with the strategy specified on the command line.

Definition at line 44 of file NodeIDAllocator.cpp.

45 : numObjects(4), numValues(4), numSymbols(4), numNodes(4), numType(0), strategy(Options::NodeAllocStrat())

46{ }

SVF::NodeIDAllocator::numValues

NodeID numValues

Number of values allocated, including specials.

Definition NodeIDAllocator.h:113

SVF::NodeIDAllocator::numObjects

NodeID numObjects

Definition NodeIDAllocator.h:111

SVF::NodeIDAllocator::numSymbols

NodeID numSymbols

Number of explicit symbols allocated (e.g., llvm::Values), including specials.

Definition NodeIDAllocator.h:115

SVF::NodeIDAllocator::strategy

enum Strategy strategy

Strategy to allocate with.

Definition NodeIDAllocator.h:123

SVF::NodeIDAllocator::numType

NodeID numType

Total number of svftypes.

Definition NodeIDAllocator.h:119

SVF::NodeIDAllocator::numNodes

NodeID numNodes

Total number of objects and values allocated.

Definition NodeIDAllocator.h:117

SVF::Options::NodeAllocStrat

static const OptionMap< SVF::NodeIDAllocator::Strategy > NodeAllocStrat

Definition Options.h:31

Member Function Documentation

◆ allocateGepObjectId()

NodeID SVF::NodeIDAllocator::allocateGepObjectId	(	NodeID	base,
		u32_t	offset,
		u32_t	maxFieldLimit
	)

Allocate a GEP object ID as determined by the strategy. allocateObjectId is still fine for GEP objects, but for some strategies (DBUG, namely), GEP objects can be allocated differently (more readable, for DBUG). Regardless, numObjects is shared; there is no special numGepObjects.

Definition at line 90 of file NodeIDAllocator.cpp.

{
    NodeID id = 0;
    if (strategy == Strategy::DENSE)
    {
        // Nothing different to the other case.
        id =  numObjects;
    }
    else if (strategy == Strategy::REVERSE_DENSE)
    {
        id = UINT_MAX - numObjects;
    }
    else if (strategy == Strategy::SEQ)
    {
        // Everything is sequential and intermixed.
        id = numNodes;
    }
    else if (strategy == Strategy::DBUG)
    {
        // For a gep id, base id is set at lower bits, and offset is set at higher bits
        // e.g., 1100050 denotes base=50 and offset=10
        // The offset is 10, not 11, because we add 1 to the offset to ensure that the
        // high bits are never 0. For example, we do not want the gep id to be 50 when
        // the base is 50 and the offset is 0.
        NodeID gepMultiplier = pow(10, ceil(log10(
                                                numSymbols > maxFieldLimit ?
                                                numSymbols : maxFieldLimit
                                            )));
        id = (offset + 1) * gepMultiplier + base;
        assert(id > numSymbols && "NodeIDAllocator::allocateGepObjectId: GEP allocation clashing with other nodes");
    }
    else
    {
        assert(false && "NodeIDAllocator::allocateGepObjectId: unimplemented node allocation strategy");
    }
 
    increaseNumOfObjAndNodes();
 
    assert(id != 0 && "NodeIDAllocator::allocateGepObjectId: ID not allocated");
    return id;
}

◆ allocateObjectId()

NodeID SVF::NodeIDAllocator::allocateObjectId ( void )

Allocate an object ID as determined by the strategy.

Definition at line 48 of file NodeIDAllocator.cpp.

{
    NodeID id = 0;
    if (strategy == Strategy::DENSE)
    {
        // We allocate objects from 0(-ish, considering the special nodes) to # of objects.
        id = numObjects;
    }
    else if (strategy == Strategy::REVERSE_DENSE)
    {
        id = UINT_MAX - numObjects;
    }
    else if (strategy == Strategy::SEQ)
    {
        // Everything is sequential and intermixed.
        id = numNodes;
    }
    else if (strategy == Strategy::DBUG)
    {
        // Non-GEPs just grab the next available ID.
        // We may have "holes" because GEPs increment the total
        // but allocate far away. This is not a problem because
        // we don't care about the relative distances between nodes.
        id = numNodes;
    }
    else
    {
        assert(false && "NodeIDAllocator::allocateObjectId: unimplemented node allocation strategy.");
    }
 
    increaseNumOfObjAndNodes();
 
    assert(id != 0 && "NodeIDAllocator::allocateObjectId: ID not allocated");
    return id;
}

◆ allocateTypeId()

NodeID SVF::NodeIDAllocator::allocateTypeId ( void )

Allocate an type ID as determined by the strategy.

Definition at line 85 of file NodeIDAllocator.cpp.

{
    return numType++;
}

◆ allocateValueId()

NodeID SVF::NodeIDAllocator::allocateValueId ( void )

Allocate a value ID as determined by the strategy.

Definition at line 132 of file NodeIDAllocator.cpp.

{
    NodeID id = 0;
    if (strategy == Strategy::DENSE)
    {
        // We allocate values from UINT_MAX to UINT_MAX - # of values.
        // TODO: UINT_MAX does not allow for an easily changeable type
        //       of NodeID (though it is already in use elsewhere).
        id = UINT_MAX - numValues;
    }
    else if (strategy == Strategy::REVERSE_DENSE)
    {
        id = numValues;
    }
    else if (strategy == Strategy::SEQ)
    {
        // Everything is sequential and intermixed.
        id = numNodes;
    }
    else if (strategy == Strategy::DBUG)
    {
        id = numNodes;
    }
    else
    {
        assert(false && "NodeIDAllocator::allocateValueId: unimplemented node allocation strategy");
    }
 
    ++numValues;
    ++numNodes;
 
    assert(id != 0 && "NodeIDAllocator::allocateValueId: ID not allocated");
    return id;
}

◆ endSymbolAllocation()

NodeID SVF::NodeIDAllocator::endSymbolAllocation ( void )

Notify the allocator that all symbols have had IDs allocated.

Definition at line 167 of file NodeIDAllocator.cpp.

{
    numSymbols = numNodes;
    return numSymbols;
}

◆ get()

NodeIDAllocator * SVF::NodeIDAllocator::get ( void )

static

Return (singleton) allocator.

Definition at line 24 of file NodeIDAllocator.cpp.

{
    if (allocator == nullptr)
    {
        allocator = new NodeIDAllocator();
    }
 
    return allocator;
}

◆ getNumObjects()

NodeID SVF::NodeIDAllocator::getNumObjects ( void ) const

inline

Returns the total number of memory objects.

Definition at line 81 of file NodeIDAllocator.h.

    {
        return numObjects;
    }

◆ getNumOfNodes()

int SVF::NodeIDAllocator::getNumOfNodes ( )

inline

Definition at line 98 of file NodeIDAllocator.h.

    {
        return numNodes;
    }

◆ increaseNumOfObjAndNodes()

void SVF::NodeIDAllocator::increaseNumOfObjAndNodes ( )

inline

Definition at line 86 of file NodeIDAllocator.h.

    {
        ++numObjects;
        ++numNodes;
    }

◆ increaseNumOfValues()

void SVF::NodeIDAllocator::increaseNumOfValues ( )

inline

Definition at line 92 of file NodeIDAllocator.h.

    {
        ++numValues;
        ++numNodes;
    }

◆ unset()

void SVF::NodeIDAllocator::unset ( void )

static

Deletes the (singleton) allocator.

Definition at line 34 of file NodeIDAllocator.cpp.

{
    if (allocator != nullptr)
    {
        delete allocator;
        allocator = nullptr;
    }
}

Member Data Documentation

◆ allocator

NodeIDAllocator * SVF::NodeIDAllocator::allocator = nullptr

staticprivate

Single allocator.

Definition at line 126 of file NodeIDAllocator.h.

◆ blackHoleObjectId

const NodeID SVF::NodeIDAllocator::blackHoleObjectId = 0

static

These nodes, and any nodes before them are assumed allocated as objects and values. For simplicity's sake, numObjects and numVals thus start at 4 (and the other counters are set appropriately).

Definition at line 48 of file NodeIDAllocator.h.

◆ blackHolePointerId

const NodeID SVF::NodeIDAllocator::blackHolePointerId = 2

static

Definition at line 50 of file NodeIDAllocator.h.

◆ constantObjectId

const NodeID SVF::NodeIDAllocator::constantObjectId = 1

static

Definition at line 49 of file NodeIDAllocator.h.

◆ nullPointerId

const NodeID SVF::NodeIDAllocator::nullPointerId = 3

static

Definition at line 51 of file NodeIDAllocator.h.

◆ numNodes

NodeID SVF::NodeIDAllocator::numNodes

private

Total number of objects and values allocated.

Definition at line 117 of file NodeIDAllocator.h.

◆ numObjects

NodeID SVF::NodeIDAllocator::numObjects

private

These are moreso counters than amounts.

Number of memory objects allocated, including specials.

Definition at line 111 of file NodeIDAllocator.h.

◆ numSymbols

NodeID SVF::NodeIDAllocator::numSymbols

private

Number of explicit symbols allocated (e.g., llvm::Values), including specials.

Definition at line 115 of file NodeIDAllocator.h.

◆ numType

NodeID SVF::NodeIDAllocator::numType

private

Total number of svftypes.

Definition at line 119 of file NodeIDAllocator.h.

◆ numValues

NodeID SVF::NodeIDAllocator::numValues

private

Number of values allocated, including specials.

Definition at line 113 of file NodeIDAllocator.h.

◆ strategy

enum Strategy SVF::NodeIDAllocator::strategy

private

Strategy to allocate with.

Definition at line 123 of file NodeIDAllocator.h.

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

/home/runner/work/SVF/SVF/svf/include/Util/NodeIDAllocator.h
/home/runner/work/SVF/SVF/svf/lib/Util/NodeIDAllocator.cpp

Classes

Public Types

Public Member Functions

Static Public Member Functions

Static Public Attributes

Private Member Functions

Private Attributes

Static Private Attributes

Detailed Description

Member Enumeration Documentation

◆ Strategy

Constructor & Destructor Documentation

◆ NodeIDAllocator()

Member Function Documentation

◆ allocateGepObjectId()

◆ allocateObjectId()

◆ allocateTypeId()

◆ allocateValueId()

◆ endSymbolAllocation()

◆ get()

◆ getNumObjects()

◆ getNumOfNodes()

◆ increaseNumOfObjAndNodes()

◆ increaseNumOfValues()

◆ unset()

Member Data Documentation

◆ allocator

◆ blackHoleObjectId

◆ blackHolePointerId

◆ constantObjectId

◆ nullPointerId

◆ numNodes

◆ numObjects

◆ numSymbols

◆ numType

◆ numValues

◆ strategy