#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	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 ()

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.

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

Friends
class	SVFIRWriter

class	SVFIRReader

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 27 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 46 of file NodeIDAllocator.cpp.

47 : numObjects(4), numValues(4), numSymbols(4), numNodes(4), strategy(Options::NodeAllocStrat())

48{ }

SVF::NodeIDAllocator::numValues

NodeID numValues

Number of values allocated, including specials.

Definition NodeIDAllocator.h:101

SVF::NodeIDAllocator::numObjects

NodeID numObjects

Definition NodeIDAllocator.h:99

SVF::NodeIDAllocator::numSymbols

NodeID numSymbols

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

Definition NodeIDAllocator.h:103

SVF::NodeIDAllocator::strategy

enum Strategy strategy

Strategy to allocate with.

Definition NodeIDAllocator.h:109

SVF::NodeIDAllocator::numNodes

NodeID numNodes

Total number of objects and values allocated.

Definition NodeIDAllocator.h:105

SVF::Options::NodeAllocStrat

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

Definition Options.h:35

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 86 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 50 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;
}

◆ allocateValueId()

NodeID SVF::NodeIDAllocator::allocateValueId ( void )

Allocate a value ID as determined by the strategy.

Definition at line 128 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 163 of file NodeIDAllocator.cpp.

{
    numSymbols = numNodes;
    return numSymbols;
}

◆ get()

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

static

Return (singleton) allocator.

Definition at line 26 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 80 of file NodeIDAllocator.h.

    {
        return numObjects;
    }

◆ increaseNumOfObjAndNodes()

void SVF::NodeIDAllocator::increaseNumOfObjAndNodes ( )

inline

Definition at line 85 of file NodeIDAllocator.h.

    {
        ++numObjects;
        ++numNodes;
    }

◆ unset()

void SVF::NodeIDAllocator::unset ( void )

static

Deletes the (singleton) allocator.

Definition at line 36 of file NodeIDAllocator.cpp.

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

Friends And Related Symbol Documentation

◆ SVFIRReader

friend class SVFIRReader

friend

Definition at line 23 of file NodeIDAllocator.h.

◆ SVFIRWriter

friend class SVFIRWriter

friend

Definition at line 22 of file NodeIDAllocator.h.

Member Data Documentation

◆ allocator

NodeIDAllocator * SVF::NodeIDAllocator::allocator = nullptr

staticprivate

Single allocator.

Definition at line 112 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 50 of file NodeIDAllocator.h.

◆ blackHolePointerId

const NodeID SVF::NodeIDAllocator::blackHolePointerId = 2

static

Definition at line 52 of file NodeIDAllocator.h.

◆ constantObjectId

const NodeID SVF::NodeIDAllocator::constantObjectId = 1

static

Definition at line 51 of file NodeIDAllocator.h.

◆ nullPointerId

const NodeID SVF::NodeIDAllocator::nullPointerId = 3

static

Definition at line 53 of file NodeIDAllocator.h.

◆ numNodes

NodeID SVF::NodeIDAllocator::numNodes

private

Total number of objects and values allocated.

Definition at line 105 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 99 of file NodeIDAllocator.h.

◆ numSymbols

NodeID SVF::NodeIDAllocator::numSymbols

private

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

Definition at line 103 of file NodeIDAllocator.h.

◆ numValues

NodeID SVF::NodeIDAllocator::numValues

private

Number of values allocated, including specials.

Definition at line 101 of file NodeIDAllocator.h.

◆ strategy

enum Strategy SVF::NodeIDAllocator::strategy

private

Strategy to allocate with.

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

Friends

Detailed Description

Member Enumeration Documentation

◆ Strategy

Constructor & Destructor Documentation

◆ NodeIDAllocator()

Member Function Documentation

◆ allocateGepObjectId()

◆ allocateObjectId()

◆ allocateValueId()

◆ endSymbolAllocation()

◆ get()

◆ getNumObjects()

◆ increaseNumOfObjAndNodes()

◆ unset()

Friends And Related Symbol Documentation

◆ SVFIRReader

◆ SVFIRWriter

Member Data Documentation

◆ allocator

◆ blackHoleObjectId

◆ blackHolePointerId

◆ constantObjectId

◆ nullPointerId

◆ numNodes

◆ numObjects

◆ numSymbols

◆ numValues

◆ strategy