SmallPtrSetImplBase - This is the common code shared among all the SmallPtrSet<>'s, which is almost everything. More...

#include "llvm/ADT/SmallPtrSet.h"

Inheritance diagram for llvm::SmallPtrSetImplBase:

[legend]

Collaboration diagram for llvm::SmallPtrSetImplBase:

Public Types
using	size_type = unsigned

Public Member Functions
SmallPtrSetImplBase &	operator= (const SmallPtrSetImplBase &)=delete

LLVM_NODISCARD bool	empty () const

size_type	size () const

void	clear ()

Public Member Functions inherited from llvm::DebugEpochBase
	DebugEpochBase ()

void	incrementEpoch ()
	Calling incrementEpoch invalidates all handles pointing into the calling instance. More...

	~DebugEpochBase ()
	The destructor calls incrementEpoch to make use-after-free bugs more likely to crash deterministically. More...

Protected Member Functions
	SmallPtrSetImplBase (const void **SmallStorage, const SmallPtrSetImplBase &that)

	SmallPtrSetImplBase (const void **SmallStorage, unsigned SmallSize, SmallPtrSetImplBase &&that)

	SmallPtrSetImplBase (const void **SmallStorage, unsigned SmallSize)

	~SmallPtrSetImplBase ()

const void **	EndPointer () const

std::pair< const void const , bool >	insert_imp (const void *Ptr)
	insert_imp - This returns true if the pointer was new to the set, false if it was already in the set. More...

bool	erase_imp (const void *Ptr)
	erase_imp - If the set contains the specified pointer, remove it and return true, otherwise return false. More...

const void const	find_imp (const void *Ptr) const
	Returns the raw pointer needed to construct an iterator. More...

void	swap (SmallPtrSetImplBase &RHS)
	swap - Swaps the elements of two sets. More...

void	CopyFrom (const SmallPtrSetImplBase &RHS)

void	MoveFrom (unsigned SmallSize, SmallPtrSetImplBase &&RHS)

Static Protected Member Functions
static void *	getTombstoneMarker ()

static void *	getEmptyMarker ()

Protected Attributes
const void **	SmallArray
	SmallArray - Points to a fixed size set of buckets, used in 'small mode'. More...

const void **	CurArray
	CurArray - This is the current set of buckets. More...

unsigned	CurArraySize
	CurArraySize - The allocated size of CurArray, always a power of two. More...

unsigned	NumNonEmpty
	Number of elements in CurArray that contain a value or are a tombstone. More...

unsigned	NumTombstones
	Number of tombstones in CurArray. More...

Friends
class	SmallPtrSetIteratorImpl

Detailed Description

SmallPtrSetImplBase - This is the common code shared among all the SmallPtrSet<>'s, which is almost everything.

SmallPtrSet has two modes, one for small and one for large sets.

Small sets use an array of pointers allocated in the SmallPtrSet object, which is treated as a simple array of pointers. When a pointer is added to the set, the array is scanned to see if the element already exists, if not the element is 'pushed back' onto the array. If we run out of space in the array, we grow into the 'large set' case. SmallSet should be used when the sets are often small. In this case, no memory allocation is used, and only light-weight and cache-efficient scanning is used.

Large sets use a classic exponentially-probed hash table. Empty buckets are represented with an illegal pointer value (-1) to allow null pointers to be inserted. Tombstones are represented with another illegal pointer value (-2), to allow deletion. The hash table is resized when the table is 3/4 or more. When this happens, the table is doubled in size.

Definition at line 50 of file SmallPtrSet.h.

Member Typedef Documentation

◆ size_type

using llvm::SmallPtrSetImplBase::size_type = unsigned

Definition at line 88 of file SmallPtrSet.h.

Constructor & Destructor Documentation

◆ SmallPtrSetImplBase() [1/3]

SmallPtrSetImplBase::SmallPtrSetImplBase	(	const void **	SmallStorage,
		const SmallPtrSetImplBase &	that
	)

protected

Definition at line 122 of file SmallPtrSet.cpp.

References CurArray, CurArraySize, llvm::safe_malloc(), and SmallArray.

◆ SmallPtrSetImplBase() [2/3]

SmallPtrSetImplBase::SmallPtrSetImplBase	(	const void **	SmallStorage,
		unsigned	SmallSize,
		SmallPtrSetImplBase &&	that
	)

protected

Definition at line 138 of file SmallPtrSet.cpp.

References SmallArray.

◆ SmallPtrSetImplBase() [3/3]

llvm::SmallPtrSetImplBase::SmallPtrSetImplBase	(	const void **	SmallStorage,
		unsigned	SmallSize
	)

inlineexplicitprotected

Definition at line 75 of file SmallPtrSet.h.

References assert().

◆ ~SmallPtrSetImplBase()

llvm::SmallPtrSetImplBase::~SmallPtrSetImplBase ( )

inlineprotected

Definition at line 82 of file SmallPtrSet.h.

Member Function Documentation

◆ clear()

void llvm::SmallPtrSetImplBase::clear ( )

inline

Definition at line 95 of file SmallPtrSet.h.

References llvm::DebugEpochBase::incrementEpoch(), llvm::Intrinsic::memset, and size().

Referenced by llvm::BasicAAResult::alias(), AllGlobalLoadUsesSimpleEnoughForHeapSRA(), llvm::cl::basic_parser_impl::anchor(), buildClonedLoopBlocks(), callsiteIsHot(), canonicalizePHIOperands(), llvm::SCEVExpander::clearPostInc(), llvm::ObjectSizeOffsetEvaluator::compute(), computeLiveOuts(), ComputePostOrders(), llvm::VerifierSupport::DebugInfoCheckFailed(), DeleteTriviallyDeadInstructions(), llvm::GVNExpression::Expression::dump(), findBBsToSinkInto(), findBestInsertionSet(), FindPredecessorAutoreleaseWithSafePath(), llvm::LexicalScopes::getMachineBasicBlocks(), llvm::GlobalsAAResult::getModRefBehavior(), getNarrowIntrinsic(), getSuccPad(), HandleMergeInputChains(), instrumentMaskedLoadOrStore(), isEFLAGSLive(), IsIncrementNUW(), isProfitableChain(), isTerminalReg(), matchPair(), mayUsePostIncMode(), okayForPHIOfOps(), llvm::SmallPtrSet< llvm::Constant *, 8 >::operator=(), optimizeGlobalsInModule(), llvm::LiveRange::RenumberValues(), llvm::Float2IntPass::runImpl(), simplifyLoopInst(), tryToVectorizeHorReductionOrInstOperands(), updatePostorderSequenceForEdgeInsertion(), and llvm::LoopBase< BasicBlock, Loop >::~LoopBase().

◆ CopyFrom()

void SmallPtrSetImplBase::CopyFrom ( const SmallPtrSetImplBase & RHS )

protected

Definition at line 145 of file SmallPtrSet.cpp.

References assert(), llvm::copy(), CurArray, CurArraySize, EndPointer(), NumNonEmpty, NumTombstones, llvm::safe_malloc(), llvm::safe_realloc(), SmallArray, and T.

Referenced by find_imp(), and llvm::SmallPtrSet< llvm::Constant *, 8 >::operator=().

◆ empty()

LLVM_NODISCARD bool llvm::SmallPtrSetImplBase::empty ( ) const

inline

Definition at line 92 of file SmallPtrSet.h.

References size().

Referenced by buildClonedLoops(), llvm::buildModuleSummaryIndex(), calculateByteProvider(), collectMDInDomain(), collectTransitivePredecessors(), llvm::DivergencePropagator::computeJoinPoints(), llvm::createConstantPropagationPass(), DominatesMergePoint(), llvm::findPHICopyInsertPoint(), findProfitablePHIs(), getLayoutSuccessorProbThreshold(), getRegClassForUnfoldedLoad(), hasRegisterDependency(), hasSameExtUse(), intersect(), isDbgValueDescribedByReg(), llvm::ScalarEvolution::isKnownViaInduction(), isLoadConditional(), isProfitableChain(), MarkBlocksLiveIn(), matchPair(), MergeAliasResults(), llvm::SelectionDAG::MorphNodeTo(), promoteArguments(), recomputeLoopBlockSet(), rewriteDebugUsers(), runImpl(), setUsedInitializer(), simplifyLoopInst(), sink(), sinkInstruction(), llvm::sinkRegion(), swapAntiDependences(), llvm::UnrollAndJamLoop(), updateOperand(), llvm::MemorySSA::verifyDominationNumbers(), and llvm::LLVMContextImpl::~LLVMContextImpl().

◆ EndPointer()

const void** llvm::SmallPtrSetImplBase::EndPointer ( ) const

inlineprotected

Definition at line 119 of file SmallPtrSet.h.

References CurArraySize, and NumNonEmpty.

Referenced by llvm::SmallPtrSetImpl< const llvm::SCEV * >::begin(), CopyFrom(), llvm::SmallPtrSetImpl< const llvm::SCEV * >::end(), erase_imp(), and find_imp().

◆ erase_imp()

bool llvm::SmallPtrSetImplBase::erase_imp ( const void * Ptr )

inlineprotected

erase_imp - If the set contains the specified pointer, remove it and return true, otherwise return false.

This is hidden from the client so that the derived class can check that the right type of pointer is passed in.

Definition at line 162 of file SmallPtrSet.h.

References assert(), EndPointer(), find_imp(), getTombstoneMarker(), and P.

Referenced by llvm::SmallPtrSetImpl< const llvm::SCEV * >::erase().

◆ find_imp()

const void* const* llvm::SmallPtrSetImplBase::find_imp ( const void * Ptr ) const

inlineprotected

Returns the raw pointer needed to construct an iterator.

If element not found, this will be EndPointer. Otherwise, it will be a pointer to the slot which stores Ptr;

Definition at line 177 of file SmallPtrSet.h.

References CopyFrom(), E, EndPointer(), MoveFrom(), SmallArray, and swap().

Referenced by erase_imp(), and llvm::SmallPtrSetImpl< const llvm::SCEV * >::find().

◆ getEmptyMarker()

static void* llvm::SmallPtrSetImplBase::getEmptyMarker ( )

inlinestaticprotected

Definition at line 113 of file SmallPtrSet.h.

Referenced by llvm::SmallPtrSetIteratorImpl::AdvanceIfNotValid(), and llvm::SmallPtrSetIteratorImpl::RetreatIfNotValid().

◆ getTombstoneMarker()

static void* llvm::SmallPtrSetImplBase::getTombstoneMarker ( )

inlinestaticprotected

Definition at line 111 of file SmallPtrSet.h.

Referenced by llvm::SmallPtrSetIteratorImpl::AdvanceIfNotValid(), erase_imp(), insert_imp(), and llvm::SmallPtrSetIteratorImpl::RetreatIfNotValid().

◆ insert_imp()

std::pair<const void *const *, bool> llvm::SmallPtrSetImplBase::insert_imp ( const void * Ptr )

inlineprotected

insert_imp - This returns true if the pointer was new to the set, false if it was already in the set.

This is hidden from the client so that the derived class can check that the right type of pointer is passed in.

Definition at line 126 of file SmallPtrSet.h.

References E, getTombstoneMarker(), llvm::DebugEpochBase::incrementEpoch(), and NumTombstones.

Referenced by llvm::SmallPtrSetImpl< const llvm::SCEV * >::insert().

◆ MoveFrom()

void SmallPtrSetImplBase::MoveFrom	(	unsigned	SmallSize,
		SmallPtrSetImplBase &&	RHS
	)

protected

Definition at line 182 of file SmallPtrSet.cpp.

References assert(), llvm::copy(), CurArray, CurArraySize, NumNonEmpty, NumTombstones, and SmallArray.

Referenced by find_imp(), and llvm::SmallPtrSet< llvm::Constant *, 8 >::operator=().

◆ operator=()

SmallPtrSetImplBase& llvm::SmallPtrSetImplBase::operator= ( const SmallPtrSetImplBase & )

delete

◆ size()

size_type llvm::SmallPtrSetImplBase::size ( ) const

inline

Definition at line 93 of file SmallPtrSet.h.

References NumTombstones.

Referenced by buildClonedLoops(), llvm::LoopVectorizationCostModel::calculateRegisterUsage(), clear(), llvm::compareLoops(), llvm::ComputeSpeculationCost(), llvm::createObjCARCOptPass(), DeadPHICycle(), empty(), llvm::CodeExtractor::extractCodeRegion(), findBBsToSinkInto(), llvm::findPHICopyInsertPoint(), FindPredecessorAutoreleaseWithSafePath(), FindPredecessorRetainWithSafePath(), findProfitablePHIs(), llvm::BasicTTIImplBase< AMDGPUTTIImpl >::getEstimatedNumberOfCaseClusters(), getFirstNonAllocaInTheEntryBlock(), getFPReg(), llvm::MemoryDependenceResults::getNonLocalCallDependency(), getOnlyLiveSuccessor(), llvm::slpvectorizer::BoUpSLP::getSpillCost(), llvm::SDNode::hasPredecessorHelper(), hasSameSuccessors(), llvm::isSafeToUnrollAndJam(), isSimpleIVUser(), LowerInterruptReturn(), matchPair(), MergeAliasResults(), PHIsEqualValue(), llvm::removeUnreachableBlocks(), ShrinkLoadReplaceStoreWithStore(), llvm::JumpThreadingPass::SimplifyPartiallyRedundantLoad(), sinkInstruction(), llvm::sinkRegion(), unswitchBestCondition(), and llvm::LoopBase< BasicBlock, Loop >::verifyLoop().

◆ swap()

void SmallPtrSetImplBase::swap ( SmallPtrSetImplBase & RHS )

protected

swap - Swaps the elements of two sets.

Note: This method assumes that both sets have the same small size.

Definition at line 214 of file SmallPtrSet.cpp.

References assert(), llvm::copy(), CurArray, CurArraySize, NumNonEmpty, NumTombstones, SmallArray, and std::swap().

Referenced by find_imp(), and llvm::SmallPtrSet< llvm::Constant *, 8 >::swap().

Friends And Related Function Documentation

◆ SmallPtrSetIteratorImpl

friend class SmallPtrSetIteratorImpl

friend

Definition at line 51 of file SmallPtrSet.h.

Member Data Documentation

◆ CurArray

const void** llvm::SmallPtrSetImplBase::CurArray

protected

CurArray - This is the current set of buckets.

If equal to SmallArray, then the set is in 'small mode'.

Definition at line 58 of file SmallPtrSet.h.

Referenced by llvm::SmallPtrSetImpl< const llvm::SCEV * >::begin(), CopyFrom(), llvm::SmallPtrSetImpl< const llvm::SCEV * >::end(), MoveFrom(), SmallPtrSetImplBase(), and swap().

◆ CurArraySize

unsigned llvm::SmallPtrSetImplBase::CurArraySize

protected

CurArraySize - The allocated size of CurArray, always a power of two.

Definition at line 60 of file SmallPtrSet.h.

Referenced by CopyFrom(), EndPointer(), MoveFrom(), SmallPtrSetImplBase(), and swap().

◆ NumNonEmpty

unsigned llvm::SmallPtrSetImplBase::NumNonEmpty

protected

Number of elements in CurArray that contain a value or are a tombstone.

If small, all these elements are at the beginning of CurArray and the rest is uninitialized.

Definition at line 65 of file SmallPtrSet.h.

Referenced by CopyFrom(), EndPointer(), MoveFrom(), and swap().

◆ NumTombstones

unsigned llvm::SmallPtrSetImplBase::NumTombstones

protected

Number of tombstones in CurArray.

Definition at line 67 of file SmallPtrSet.h.

Referenced by CopyFrom(), insert_imp(), MoveFrom(), size(), and swap().

◆ SmallArray

const void** llvm::SmallPtrSetImplBase::SmallArray

protected

SmallArray - Points to a fixed size set of buckets, used in 'small mode'.

Definition at line 55 of file SmallPtrSet.h.

Referenced by CopyFrom(), find_imp(), MoveFrom(), SmallPtrSetImplBase(), and swap().

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

include/llvm/ADT/SmallPtrSet.h
lib/Support/SmallPtrSet.cpp

Public Types

Public Member Functions

Protected Member Functions

Static Protected Member Functions

Protected Attributes

Friends

Detailed Description

Member Typedef Documentation

◆ size_type

Constructor & Destructor Documentation

◆ SmallPtrSetImplBase() [1/3]

◆ SmallPtrSetImplBase() [2/3]

◆ SmallPtrSetImplBase() [3/3]

◆ ~SmallPtrSetImplBase()

Member Function Documentation

◆ clear()

◆ CopyFrom()

◆ empty()

◆ EndPointer()

◆ erase_imp()

◆ find_imp()

◆ getEmptyMarker()

◆ getTombstoneMarker()

◆ insert_imp()

◆ MoveFrom()

◆ operator=()

◆ size()

◆ swap()

Friends And Related Function Documentation

◆ SmallPtrSetIteratorImpl

Member Data Documentation

◆ CurArray

◆ CurArraySize

◆ NumNonEmpty

◆ NumTombstones

◆ SmallArray