LLVM: llvm::SmallPtrSetImplBase Class Reference (original) (raw)

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

#include "[llvm/ADT/SmallPtrSet.h](SmallPtrSet%5F8h%5Fsource.html)"

Inherits llvm::DebugEpochBase.

Inherited by llvm::SmallPtrSetImpl< MachineInstr * >, llvm::SmallPtrSetImpl< MachineBasicBlock * >, llvm::SmallPtrSetImpl< BasicBlock * >, llvm::SmallPtrSetImpl< const BasicBlockT * >, llvm::SmallPtrSetImpl< PointeeType * >, llvm::SmallPtrSetImpl< NodeRef >, llvm::SmallPtrSetImpl< typename GraphTraits< GraphT >::NodeRef >, llvm::SmallPtrSetImpl< const llvm::MDNode * >, llvm::SmallPtrSetImpl< llvm::Instruction * >, llvm::SmallPtrSetImpl< Value * >, llvm::SmallPtrSetImpl< llvm::DIScope * >, llvm::SmallPtrSetImpl< llvm::MachineBasicBlock * >, llvm::SmallPtrSetImpl< llvm::LiveRange * >, llvm::SmallPtrSetImpl< const llvm::AllocaInst * >, 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< llvm::Value * >, llvm::SmallPtrSetImpl< llvm::Use * >, llvm::SmallPtrSetImpl< const llvm::DISubprogram * >, llvm::SmallPtrSetImpl< llvm::GlobalVariable * >, llvm::SmallPtrSetImpl< llvm::Constant * >, llvm::SmallPtrSetImpl< llvm::GlobalValue * >, llvm::SmallPtrSetImpl< const llvm::DbgVariableRecord * >, llvm::SmallPtrSetImpl< llvm::MachineInstr * >, llvm::SmallPtrSetImpl< BasicBlockT * >, llvm::SmallPtrSetImpl< const BlockT * >, llvm::SmallPtrSetImpl< const CycleT * >, llvm::SmallPtrSetImpl< const InstructionT * >, llvm::SmallPtrSetImpl< const llvm::GlobalValue * >, llvm::SmallPtrSetImpl< NodeTy * >, 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 llvm::Instruction * >, llvm::SmallPtrSetImpl< const llvm::MCSymbol * >, llvm::SmallPtrSetImpl< const llvm::LazyCallGraph::Node * >, llvm::SmallPtrSetImpl< llvm::MachineRegisterInfo::Delegate * >, llvm::SmallPtrSetImpl< const llvm::BasicBlock * >, 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:🆑:SubCommand * >, llvm::SmallPtrSetImpl< llvm::orc::JITDylib const * >, llvm::SmallPtrSetImpl< Instruction * >, llvm::SmallPtrSetImpl< const Value * >, and llvm::SmallPtrSetImpl< PtrType >.

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

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.

â—† size_type

Definition at line 138 of file SmallPtrSet.cpp.

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

Referenced by copyFrom(), moveFrom(), operator=(), SmallPtrSetImplBase(), SmallPtrSetImplBase(), and swap().

â—† SmallPtrSetImplBase() [2/3]

â—† SmallPtrSetImplBase() [3/3]

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

â—† ~SmallPtrSetImplBase()

llvm::SmallPtrSetImplBase::~SmallPtrSetImplBase ( ) inlineprotected

â—† buckets() [1/2]

â—† buckets() [2/2]

â—† capacity()

size_type llvm::SmallPtrSetImplBase::capacity ( ) const inlinenodiscard

â—† 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::SCEVExpanderCleaner::cleanup(), ComputePostOrders(), llvm::SelectionDAG::copyExtraInfo(), llvm::detachDeadBlocks(), findBBsToSinkInto(), findConsecutiveLoad(), llvm::LexicalScopes::getMachineBasicBlocks(), HandleMergeInputChains(), llvm::MergeBasicBlockIntoOnlyPred(), llvm::MergeBlockIntoPredecessor(), llvm::SmallPtrSet< NodeRef, SmallSize >::operator=(), slpvectorizer::BoUpSLP::optimizeGatherSequence(), optimizeGlobalsInModule(), llvm::ReachingDefInfo::print(), slpvectorizer::BoUpSLP::reorderBottomToTop(), simplifyLoopInst(), stripDebugLocFromLoopID(), llvm::TryToSimplifyUncondBranchFromEmptyBlock(), and updatePostorderSequenceForEdgeInsertion().

â—† contains_imp()

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

â—† copyFrom()

â—† empty()

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

Definition at line 98 of file SmallPtrSet.h.

References size().

Referenced by alwaysInlineImpl(), buildClonedLoops(), llvm::buildModuleSummaryIndex(), llvm::AArch64TargetMachine::clearLinkerOptimizationHints(), collectInstructionsInBetween(), llvm::ScopedNoAliasAAResult::collectScopedDomains(), collectTransitivePredecessors(), dominatesMergePoint(), expandProtectedFieldPtr(), getFSqrtDivOptPattern(), getGatherLanePattern(), handleByValParam(), llvm::ScalarEvolution::isKnownViaInduction(), llvm::isPotentiallyReachable(), isReachableImpl(), IsValueFullyAvailableInBlock(), llvm::ScopedNoAliasAAResult::mayAliasInScopes(), llvm::MergeBlockSuccessorsIntoGivenBlocks(), mergeReplicateRegionsIntoSuccessors(), llvm::SelectionDAG::MorphNodeTo(), producesFalseLanesZero(), ReachabilityQueryInfo< ToTy >::ReachabilityQueryInfo(), rebuildLoopAfterUnswitch(), recomputeLoopBlockSet(), rewriteDebugUsers(), runImpl(), simplifyLoopInst(), sink(), sinkInstruction(), and llvm::MemorySSA::verifyDominationNumbers().

â—† EndPointer()

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

â—† erase_imp()

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

â—† find_imp()

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

â—† getEmptyMarker()

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

â—† getTombstoneMarker()

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

â—† insert_imp()

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

â—† 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< MachineInstr * >::remove_if(), reserve(), SmallPtrSetImplBase(), swap(), and ~SmallPtrSetImplBase().

â—† moveFrom()

â—† operator=()

â—† reserve()

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

â—† size()

size_type llvm::SmallPtrSetImplBase::size ( ) const inlinenodiscard

Definition at line 99 of file SmallPtrSet.h.

References NumEntries.

Referenced by adjustedSumFreq(), buildClonedLoops(), llvm::calculateRegisterUsageForPlan(), canFoldStoreIntoLibCallOutputPointers(), llvm::ScalarEvolution::canReuseInstruction(), llvm::sandboxir::LegalityAnalysis::canVectorize(), llvm::changeToUnreachable(), checkIVUsers(), clear(), llvm::ConstantFoldTerminator(), containsUnreachable(), empty(), feedsIntoVectorReduction(), findBBsToSinkInto(), findBestNonTrivialUnswitchCandidate(), findReaching(), llvm::objcarc::findSingleDependency(), llvm::InstCombinerImpl::foldDeadPhiWeb(), llvm::InstCombinerImpl::foldFreezeIntoRecurrence(), 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::SCCPSolver::removeNonFeasibleEdges(), slpvectorizer::BoUpSLP::VLOperands::reorder(), llvm::SSAUpdaterBulk::RewriteAllUses(), runImpl(), llvm::AbstractDependenceGraphBuilder< GraphType >::simplify(), simplifyBlends(), llvm::JumpThreadingPass::simplifyPartiallyRedundantLoad(), sinkInstruction(), llvm::SplitBlockAndInsertIfThenElse(), updateForAIXShLibTLSModelOpt(), usersDominator(), llvm::LoopInfoBase< MachineBasicBlock, MachineLoop >::verify(), llvm::GenericCycle< ContextT >::verifyCycle(), and llvm::MemorySSAUpdater::wireOldPredecessorsToNewImmediatePredecessor().

â—† small_buckets() [1/2]

â—† small_buckets() [2/2]

â—† swap()

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, small_buckets(), SmallPtrSetImplBase(), and std::swap().

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

â—† SmallPtrSetIteratorImpl

â—† 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< MachineInstr * >::begin(), buckets(), buckets(), clear(), copyFrom(), EndPointer(), erase_imp(), insert_imp(), moveFrom(), small_buckets(), small_buckets(), SmallPtrSetImplBase(), 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(), llvm::SmallPtrSetImpl< PtrType >::SmallPtrSetImplBase(), SmallPtrSetImplBase(), SmallPtrSetImplBase(), and swap().

â—† IsSmall

bool llvm::SmallPtrSetImplBase::IsSmall protected

â—† 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< MachineInstr * >::remove_if(), size(), small_buckets(), small_buckets(), SmallPtrSetImplBase(), and swap().

â—† NumTombstones

unsigned llvm::SmallPtrSetImplBase::NumTombstones protected

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