llvm::SmallPtrSetImplBase Class Reference

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

#include "llvm/ADT/SmallPtrSet.h"

Inherits llvm::DebugEpochBase.

Inherited by llvm::SmallPtrSetImpl< BasicBlockT * >, llvm::SmallPtrSetImpl< BasicBlock * >, llvm::SmallPtrSetImpl< const BasicBlock * >, llvm::SmallPtrSetImpl< const BasicBlockT * >, llvm::SmallPtrSetImpl< const MachineBasicBlock * >, llvm::SmallPtrSetImpl< typename GraphTraits< std::conditional_t< IsConst, const BlockT, BlockT > * >::NodeRef >, llvm::SmallPtrSetImpl< PointeeType * >, llvm::SmallPtrSetImpl< typename GraphTraits< GraphT >::NodeRef >, llvm::SmallPtrSetImpl< typename GraphTraits< T >::NodeRef >, llvm::SmallPtrSetImpl< NodeRef >, llvm::SmallPtrSetImpl< const MDNode * >, llvm::SmallPtrSetImpl< Instruction * >, llvm::SmallPtrSetImpl< llvm::Value * >, llvm::SmallPtrSetImpl< DIScope * >, llvm::SmallPtrSetImpl< llvm::MachineBasicBlock * >, llvm::SmallPtrSetImpl< llvm::LiveRange * >, llvm::SmallPtrSetImpl< const llvm::AllocaInst * >, llvm::SmallPtrSetImpl< const Instruction * >, llvm::SmallPtrSetImpl< CallBase * >, llvm::SmallPtrSetImpl< AssumeInst * >, llvm::SmallPtrSetImpl< const MachineInstr * >, llvm::SmallPtrSetImpl< const llvm::GlobalVariable * >, llvm::SmallPtrSetImpl< llvm::BasicBlock * >, llvm::SmallPtrSetImpl< const llvm::Value * >, llvm::SmallPtrSetImpl< const llvm::MachineBasicBlock * >, llvm::SmallPtrSetImpl< llvm::LazyCallGraph::SCC * >, llvm::SmallPtrSetImpl< llvm::Function * >, llvm::SmallPtrSetImpl< llvm::GlobalObject * >, llvm::SmallPtrSetImpl< const llvm::MDNode * >, llvm::SmallPtrSetImpl< llvm::Instruction * >, llvm::SmallPtrSetImpl< llvm::Use * >, llvm::SmallPtrSetImpl< llvm::GlobalVariable * >, llvm::SmallPtrSetImpl< llvm::Constant * >, llvm::SmallPtrSetImpl< llvm::GlobalValue * >, llvm::SmallPtrSetImpl< const llvm::DbgVariableRecord * >, llvm::SmallPtrSetImpl< llvm::MachineInstr * >, llvm::SmallPtrSetImpl< const BlockT * >, llvm::SmallPtrSetImpl< const CycleT * >, llvm::SmallPtrSetImpl< const InstructionT * >, llvm::SmallPtrSetImpl< const llvm::GlobalValue * >, llvm::SmallPtrSetImpl< NodeTy * >, llvm::SmallPtrSetImpl< const Loop * >, llvm::SmallPtrSetImpl< const llvm::Function * >, llvm::SmallPtrSetImpl< llvm::InterleaveGroup< llvm::Instruction > * >, llvm::SmallPtrSetImpl< llvm::Module * >, llvm::SmallPtrSetImpl< const llvm::VNInfo * >, llvm::SmallPtrSetImpl< llvm::PHINode * >, llvm::SmallPtrSetImpl< llvm::Type * >, llvm::SmallPtrSetImpl< const PHINode * >, llvm::SmallPtrSetImpl< const llvm::Instruction * >, llvm::SmallPtrSetImpl< const llvm::MCSymbol * >, llvm::SmallPtrSetImpl< Module * >, llvm::SmallPtrSetImpl< const llvm::LazyCallGraph::Node * >, llvm::SmallPtrSetImpl< llvm::MachineRegisterInfo::Delegate * >, llvm::SmallPtrSetImpl< const llvm::BasicBlock * >, llvm::SmallPtrSetImpl< const Value * >, llvm::SmallPtrSetImpl< void * >, llvm::SmallPtrSetImpl< llvm::AnalysisKey * >, llvm::SmallPtrSetImpl< const llvm::SCEV * >, llvm::SmallPtrSetImpl< const llvm::Type * >, llvm::SmallPtrSetImpl< const llvm::PHINode * >, llvm::SmallPtrSetImpl< const llvm::SCEVAddRecExpr * >, llvm::SmallPtrSetImpl< llvm::cl::SubCommand * >, llvm::SmallPtrSetImpl< llvm::orc::JITDylib const * >, llvm::SmallPtrSetImpl< Value * >, and llvm::SmallPtrSetImpl< PtrType >.

Public Types
using	size_type = unsigned

Public Member Functions
SmallPtrSetImplBase &	operator= (const SmallPtrSetImplBase &)=delete
bool	empty () const
size_type	size () const
size_type	capacity () const
void	clear ()
void	reserve (size_type NewNumEntries)
Public Member Functions inherited from llvm::DebugEpochBase
void	incrementEpoch ()

Protected Member Functions
LLVM_ABI	SmallPtrSetImplBase (const void **SmallStorage, const SmallPtrSetImplBase &that)
LLVM_ABI	SmallPtrSetImplBase (const void **SmallStorage, unsigned SmallSize, const void **RHSSmallStorage, SmallPtrSetImplBase &&that)
	SmallPtrSetImplBase (const void **SmallStorage, unsigned SmallSize)
	~SmallPtrSetImplBase ()
const void **	EndPointer () const
iterator_range< const void ** >	small_buckets ()
iterator_range< const void *const * >	small_buckets () const
iterator_range< const void ** >	buckets ()
iterator_range< const void *const * >	buckets () 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.
bool	erase_imp (const void *Ptr)
	erase_imp - If the set contains the specified pointer, remove it and return true, otherwise return false.
const void *const *	find_imp (const void *Ptr) const
	Returns the raw pointer needed to construct an iterator.
bool	contains_imp (const void *Ptr) const
bool	isSmall () const
LLVM_ABI void	swap (const void **SmallStorage, const void **RHSSmallStorage, SmallPtrSetImplBase &RHS)
	swap - Swaps the elements of two sets.
LLVM_ABI void	copyFrom (const void **SmallStorage, const SmallPtrSetImplBase &RHS)
LLVM_ABI void	moveFrom (const void **SmallStorage, unsigned SmallSize, const void **RHSSmallStorage, SmallPtrSetImplBase &&RHS)

Static Protected Member Functions
static void *	getTombstoneMarker ()
static void *	getEmptyMarker ()

Protected Attributes
const void **	CurArray
	The current set of buckets, in either small or big representation.
unsigned	CurArraySize
	CurArraySize - The allocated size of CurArray, always a power of two.
unsigned	NumEntries
	Number of elements in CurArray that contain a value.
unsigned	NumTombstones
	Number of tombstones in CurArray.
bool	IsSmall
	Whether the set is in small representation.

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 quadratically-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 56 of file SmallPtrSet.h.

Member Typedef Documentation

size_type

using llvm::SmallPtrSetImplBase::size_type = unsigned

Definition at line 94 of file SmallPtrSet.h.

Constructor & Destructor Documentation

SmallPtrSetImplBase() [1/3]

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

protected

Definition at line 138 of file SmallPtrSet.cpp.

References CurArray, CurArraySize, IsSmall, isSmall(), and llvm::safe_malloc().

SmallPtrSetImplBase() [2/3]

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

protected

Definition at line 153 of file SmallPtrSet.cpp.

SmallPtrSetImplBase() [3/3]

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

inlineexplicitprotected

Definition at line 81 of file SmallPtrSet.h.

References assert(), and llvm::has_single_bit().

~SmallPtrSetImplBase()

llvm::SmallPtrSetImplBase::~SmallPtrSetImplBase ( )

inlineprotected

Definition at line 88 of file SmallPtrSet.h.

References CurArray, and isSmall().

Member Function Documentation

buckets() [1/2]

iterator_range< const void ** > llvm::SmallPtrSetImplBase::buckets ( )

inlineprotected

Definition at line 159 of file SmallPtrSet.h.

References CurArray, EndPointer(), and llvm::make_range().

Referenced by llvm::SmallPtrSetImpl< PtrType >::remove_if().

buckets() [2/2]

iterator_range< const void *const * > llvm::SmallPtrSetImplBase::buckets ( ) const

inlineprotected

Definition at line 163 of file SmallPtrSet.h.

References CurArray, EndPointer(), and llvm::make_range().

capacity()

size_type llvm::SmallPtrSetImplBase::capacity ( ) const

inline

Definition at line 100 of file SmallPtrSet.h.

References CurArraySize.

clear()

void llvm::SmallPtrSetImplBase::clear ( )

inline

Definition at line 102 of file SmallPtrSet.h.

References CurArray, CurArraySize, llvm::DebugEpochBase::incrementEpoch(), isSmall(), NumEntries, NumTombstones, and size().

Referenced by llvm::HexagonSubtarget::adjustSchedDependency(), buildClonedLoopBlocks(), llvm::SampleProfileLoaderBaseImpl< FT >::buildEdges(), canonicalizePHIOperands(), llvm::EphemeralValuesCache::clear(), llvm::SCEVExpander::clear(), llvm::AAExecutionDomain::ExecutionDomainTy::clearAssumeInstAndAlignedBarriers(), llvm::SCEVExpander::clearPostInc(), llvm::ObjectSizeOffsetEvaluator::compute(), ComputePostOrders(), llvm::SelectionDAG::copyExtraInfo(), llvm::slpvectorizer::BoUpSLP::deleteTree(), llvm::OpenMPIRBuilder::finalize(), findBBsToSinkInto(), findConsecutiveLoad(), llvm::LexicalScopes::getMachineBasicBlocks(), HandleMergeInputChains(), llvm::MergeBasicBlockIntoOnlyPred(), llvm::MergeBlockIntoPredecessor(), llvm::SmallPtrSet< PtrType, SmallSize >::operator=(), optimizeGlobalsInModule(), llvm::ReachingDefAnalysis::printAllReachingDefs(), llvm::slpvectorizer::BoUpSLP::reorderBottomToTop(), simplifyLoopInst(), stripDebugLocFromLoopID(), llvm::TryToSimplifyUncondBranchFromEmptyBlock(), updatePostorderSequenceForEdgeInsertion(), and llvm::LoopBase< BlockT, LoopT >::~LoopBase().

contains_imp()

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

inlineprotected

Definition at line 236 of file SmallPtrSet.h.

References isSmall(), Ptr, and small_buckets().

Referenced by llvm::SmallPtrSetImpl< PtrType >::contains(), and llvm::SmallPtrSetImpl< PtrType >::count().

copyFrom()

void SmallPtrSetImplBase::copyFrom ( const void **  SmallStorage, const SmallPtrSetImplBase &  RHS  )

protected

Definition at line 160 of file SmallPtrSet.cpp.

References assert(), CurArray, CurArraySize, IsSmall, isSmall(), RHS, llvm::safe_malloc(), and llvm::safe_realloc().

Referenced by llvm::SmallPtrSet< PtrType, SmallSize >::operator=().

empty()

bool llvm::SmallPtrSetImplBase::empty ( ) const

inline

Definition at line 98 of file SmallPtrSet.h.

References size().

Referenced by alwaysInlineImpl(), buildClonedLoops(), llvm::buildModuleSummaryIndex(), llvm::AArch64TargetMachine::clearLinkerOptimizationHints(), llvm::LoopVectorizationCostModel::collectInLoopReductions(), collectInstructionsInBetween(), llvm::ScopedNoAliasAAResult::collectScopedDomains(), collectTransitivePredecessors(), dominatesMergePoint(), getFSqrtDivOptPattern(), getGatherLanePattern(), llvm::LoopVectorizationCostModel::getReductionPatternCost(), llvm::GenericDomTreeUpdater< DerivedT, DomTreeT, PostDomTreeT >::hasPendingDeletedBB(), llvm::GenericDomTreeUpdater< DerivedT, DomTreeT, PostDomTreeT >::isBBPendingDeletion(), llvm::ScalarEvolution::isKnownViaInduction(), llvm::isPotentiallyReachable(), isReachableImpl(), IsValueFullyAvailableInBlock(), llvm::MergeBlockSuccessorsIntoGivenBlocks(), mergeReplicateRegionsIntoSuccessors(), llvm::SelectionDAG::MorphNodeTo(), producesFalseLanesZero(), ReachabilityQueryInfo< ToTy >::ReachabilityQueryInfo(), rebuildLoopAfterUnswitch(), recomputeLoopBlockSet(), rewriteDebugUsers(), runImpl(), simplifyLoopInst(), sink(), sinkInstruction(), llvm::MemorySSA::verifyDominationNumbers(), and llvm::LLVMContextImpl::~LLVMContextImpl().

EndPointer()

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

inlineprotected

Definition at line 147 of file SmallPtrSet.h.

References CurArray, CurArraySize, isSmall(), and NumEntries.

Referenced by llvm::SmallPtrSetImpl< PtrType >::begin(), buckets(), llvm::SmallPtrSetImpl< PtrType >::end(), 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 193 of file SmallPtrSet.h.

References CurArray, getTombstoneMarker(), llvm::DebugEpochBase::incrementEpoch(), isSmall(), NumEntries, NumTombstones, Ptr, and small_buckets().

Referenced by llvm::SmallPtrSetImpl< PtrType >::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 221 of file SmallPtrSet.h.

References EndPointer(), isSmall(), Ptr, and small_buckets().

Referenced by llvm::SmallPtrSetImpl< PtrType >::find().

getEmptyMarker()

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

inlinestaticprotected

Definition at line 141 of file SmallPtrSet.h.

Referenced by llvm::SmallPtrSetIteratorImpl::AdvanceIfNotValid(), llvm::SmallPtrSetImpl< PtrType >::remove_if(), and llvm::SmallPtrSetIteratorImpl::RetreatIfNotValid().

getTombstoneMarker()

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

inlinestaticprotected

Definition at line 139 of file SmallPtrSet.h.

Referenced by llvm::SmallPtrSetIteratorImpl::AdvanceIfNotValid(), erase_imp(), llvm::SmallPtrSetImpl< PtrType >::remove_if(), 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 170 of file SmallPtrSet.h.

References CurArray, CurArraySize, llvm::DebugEpochBase::incrementEpoch(), isSmall(), NumEntries, Ptr, and small_buckets().

Referenced by llvm::SmallPtrSetImpl< PtrType >::insert().

isSmall()

bool llvm::SmallPtrSetImplBase::isSmall ( ) const

inlineprotected

Definition at line 248 of file SmallPtrSet.h.

References IsSmall.

Referenced by clear(), contains_imp(), copyFrom(), EndPointer(), erase_imp(), find_imp(), insert_imp(), moveFrom(), llvm::SmallPtrSetImpl< PtrType >::remove_if(), reserve(), SmallPtrSetImplBase(), swap(), and ~SmallPtrSetImplBase().

moveFrom()

void SmallPtrSetImplBase::moveFrom ( const void **  SmallStorage, unsigned  SmallSize, const void **  RHSSmallStorage, SmallPtrSetImplBase &&  RHS  )

protected

Definition at line 200 of file SmallPtrSet.cpp.

References CurArray, isSmall(), and RHS.

Referenced by llvm::SmallPtrSet< PtrType, SmallSize >::operator=().

operator=()

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

delete

reserve()

void llvm::SmallPtrSetImplBase::reserve ( size_type  NewNumEntries )

inline

Definition at line 117 of file SmallPtrSet.h.

References llvm::bit_ceil(), CurArraySize, llvm::DebugEpochBase::incrementEpoch(), and isSmall().

Referenced by llvm::IDFCalculatorBase< NodeTy, IsPostDom >::calculate(), llvm::VETargetLowering::emitSjLjDispatchBlock(), and llvm::sandboxir::Type::isSized().

size()

size_type llvm::SmallPtrSetImplBase::size ( ) const

inline

Definition at line 99 of file SmallPtrSet.h.

References NumEntries.

Referenced by adjustedSumFreq(), llvm::SampleProfileInference< FT >::apply(), buildClonedLoops(), llvm::calculateRegisterUsageForPlan(), canFoldStoreIntoLibCallOutputPointers(), llvm::ScalarEvolution::canReuseInstruction(), llvm::sandboxir::LegalityAnalysis::canVectorize(), llvm::changeToUnreachable(), clear(), llvm::ConstantFoldTerminator(), empty(), feedsIntoVectorReduction(), findBBsToSinkInto(), findBestNonTrivialUnswitchCandidate(), findReaching(), llvm::objcarc::findSingleDependency(), llvm::InstCombinerImpl::foldDeadPhiWeb(), llvm::InstCombinerImpl::foldFreezeIntoRecurrence(), llvm::BasicTTIImplBase< T >::getEstimatedNumberOfCaseClusters(), llvm::LoopBase< BasicBlock, Loop >::getLoopLatch(), llvm::MemoryDependenceResults::getNonLocalCallDependency(), getOutliningPenalty(), llvm::getUnderlyingObjectAggressive(), llvm::hasPartialIVCondition(), llvm::SDNode::hasPredecessorHelper(), hasSameSuccessors(), isOnlyCopiedFromConstantMemory(), isPotentiallyReachable(), llvm::CombinerHelper::matchExtendThroughPhis(), optimizeLoopExitWithUnknownExitCount(), PHIsEqualValue(), llvm::PointerMayBeCaptured(), llvm::AArch64TTIImpl::preferPredicateOverEpilogue(), llvm::HashRecognize::recognizeCRC(), llvm::SCCPSolver::removeNonFeasibleEdges(), llvm::removeUnreachableBlocks(), llvm::slpvectorizer::BoUpSLP::VLOperands::reorder(), llvm::SSAUpdaterBulk::RewriteAllUses(), runImpl(), llvm::AbstractDependenceGraphBuilder< GraphType >::simplify(), simplifyBlends(), llvm::JumpThreadingPass::simplifyPartiallyRedundantLoad(), sinkInstruction(), llvm::SplitBlockAndInsertIfThenElse(), updateForAIXShLibTLSModelOpt(), usersDominator(), llvm::GenericCycle< ContextT >::verifyCycle(), and llvm::MemorySSAUpdater::wireOldPredecessorsToNewImmediatePredecessor().

small_buckets() [1/2]

iterator_range< const void ** > llvm::SmallPtrSetImplBase::small_buckets ( )

inlineprotected

Definition at line 151 of file SmallPtrSet.h.

References CurArray, llvm::make_range(), and NumEntries.

Referenced by contains_imp(), erase_imp(), find_imp(), insert_imp(), llvm::SmallPtrSetImpl< PtrType >::remove_if(), and swap().

small_buckets() [2/2]

iterator_range< const void *const * > llvm::SmallPtrSetImplBase::small_buckets ( ) const

inlineprotected

Definition at line 155 of file SmallPtrSet.h.

References CurArray, and NumEntries.

swap()

void SmallPtrSetImplBase::swap ( const void **  SmallStorage, const void **  RHSSmallStorage, 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 237 of file SmallPtrSet.cpp.

References assert(), llvm::copy(), CurArray, CurArraySize, IsSmall, isSmall(), NumEntries, NumTombstones, RHS, small_buckets(), and std::swap().

Referenced by llvm::SmallPtrSet< PtrType, SmallSize >::swap().

Friends And Related Function Documentation

SmallPtrSetIteratorImpl

friend class SmallPtrSetIteratorImpl

friend

Definition at line 57 of file SmallPtrSet.h.

Member Data Documentation

CurArray

const void** llvm::SmallPtrSetImplBase::CurArray

protected

The current set of buckets, in either small or big representation.

Definition at line 61 of file SmallPtrSet.h.

Referenced by llvm::SmallPtrSetImpl< PtrType >::begin(), buckets(), clear(), copyFrom(), EndPointer(), erase_imp(), insert_imp(), moveFrom(), small_buckets(), SmallPtrSetImplBase(), swap(), and ~SmallPtrSetImplBase().

CurArraySize

unsigned llvm::SmallPtrSetImplBase::CurArraySize

protected

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

Definition at line 63 of file SmallPtrSet.h.

Referenced by capacity(), clear(), copyFrom(), EndPointer(), insert_imp(), reserve(), SmallPtrSetImplBase(), and swap().

IsSmall

bool llvm::SmallPtrSetImplBase::IsSmall

protected

Whether the set is in small representation.

Definition at line 72 of file SmallPtrSet.h.

Referenced by copyFrom(), isSmall(), SmallPtrSetImplBase(), and swap().

NumEntries

unsigned llvm::SmallPtrSetImplBase::NumEntries

protected

Number of elements in CurArray that contain a value.

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

Definition at line 68 of file SmallPtrSet.h.

Referenced by clear(), EndPointer(), erase_imp(), insert_imp(), llvm::SmallPtrSetImpl< PtrType >::remove_if(), size(), small_buckets(), and swap().

NumTombstones

unsigned llvm::SmallPtrSetImplBase::NumTombstones

protected

Number of tombstones in CurArray.

Definition at line 70 of file SmallPtrSet.h.

Referenced by clear(), erase_imp(), llvm::SmallPtrSetImpl< PtrType >::remove_if(), and swap().

---

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

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