This is a 'bitvector' (really, a variable-sized bit array), optimized for the case when the array is small. More...

#include "llvm/ADT/SmallBitVector.h"

Classes
class	reference

Public Types
using	size_type = uintptr_t
using	const_set_bits_iterator = const_set_bits_iterator_impl<SmallBitVector>
using	set_iterator = const_set_bits_iterator

Public Member Functions
	SmallBitVector ()=default
	Creates an empty bitvector.
	SmallBitVector (unsigned s, bool t=false)
	Creates a bitvector of specified number of bits.
	SmallBitVector (const SmallBitVector &RHS)
	SmallBitVector copy ctor.
	SmallBitVector (SmallBitVector &&RHS)
	~SmallBitVector ()
const_set_bits_iterator	set_bits_begin () const
const_set_bits_iterator	set_bits_end () const
iterator_range< const_set_bits_iterator >	set_bits () const
bool	isSmall () const
bool	empty () const
	Tests whether there are no bits in this bitvector.
size_type	size () const
	Returns the number of bits in this bitvector.
size_type	count () const
	Returns the number of bits which are set.
bool	any () const
	Returns true if any bit is set.
bool	all () const
	Returns true if all bits are set.
bool	none () const
	Returns true if none of the bits are set.
int	find_first () const
	Returns the index of the first set bit, -1 if none of the bits are set.
int	find_last () const
int	find_first_unset () const
	Returns the index of the first unset bit, -1 if all of the bits are set.
int	find_last_unset () const
int	find_next (unsigned Prev) const
	Returns the index of the next set bit following the "Prev" bit.
int	find_next_unset (unsigned Prev) const
	Returns the index of the next unset bit following the "Prev" bit.
int	find_prev (unsigned PriorTo) const
	find_prev - Returns the index of the first set bit that precedes the the bit at `PriorTo`.
void	clear ()
	Clear all bits.
void	resize (unsigned N, bool t=false)
	Grow or shrink the bitvector.
void	reserve (unsigned N)
SmallBitVector &	set ()
SmallBitVector &	set (unsigned Idx)
SmallBitVector &	set (unsigned I, unsigned E)
	Efficiently set a range of bits in [I, E)
SmallBitVector &	reset ()
SmallBitVector &	reset (unsigned Idx)
SmallBitVector &	reset (unsigned I, unsigned E)
	Efficiently reset a range of bits in [I, E)
SmallBitVector &	flip ()
SmallBitVector &	flip (unsigned Idx)
SmallBitVector	operator~ () const
reference	operator[] (unsigned Idx)
bool	operator[] (unsigned Idx) const
bool	back () const
	Return the last element in the vector.
bool	test (unsigned Idx) const
void	push_back (bool Val)
void	pop_back ()
	Pop one bit from the end of the vector.
bool	anyCommon (const SmallBitVector &RHS) const
	Test if any common bits are set.
bool	operator== (const SmallBitVector &RHS) const
bool	operator!= (const SmallBitVector &RHS) const
SmallBitVector &	operator&= (const SmallBitVector &RHS)
SmallBitVector &	reset (const SmallBitVector &RHS)
	Reset bits that are set in RHS. Same as *this &= ~RHS.
bool	test (const SmallBitVector &RHS) const
	Check if (This - RHS) is zero. This is the same as reset(RHS) and any().
SmallBitVector &	operator\|= (const SmallBitVector &RHS)
SmallBitVector &	operator^= (const SmallBitVector &RHS)
SmallBitVector &	operator<<= (unsigned N)
SmallBitVector &	operator>>= (unsigned N)
const SmallBitVector &	operator= (const SmallBitVector &RHS)
const SmallBitVector &	operator= (SmallBitVector &&RHS)
void	swap (SmallBitVector &RHS)
void	setBitsInMask (const uint32_t *Mask, unsigned MaskWords=~0u)
	Add '1' bits from Mask to this vector.
void	clearBitsInMask (const uint32_t *Mask, unsigned MaskWords=~0u)
	Clear any bits in this vector that are set in Mask.
void	setBitsNotInMask (const uint32_t *Mask, unsigned MaskWords=~0u)
	Add a bit to this vector for every '0' bit in Mask.
void	clearBitsNotInMask (const uint32_t *Mask, unsigned MaskWords=~0u)
	Clear a bit in this vector for every '0' bit in Mask.
void	invalid ()
bool	isInvalid () const
ArrayRef< uintptr_t >	getData (uintptr_t &Store) const

Detailed Description

This is a 'bitvector' (really, a variable-sized bit array), optimized for the case when the array is small.

It contains one pointer-sized field, which is directly used as a plain collection of bits when possible, or as a pointer to a larger heap-allocated array when necessary. This allows normal "small" cases to be fast without losing generality for large inputs.

Definition at line 35 of file SmallBitVector.h.

Member Typedef Documentation

◆ const_set_bits_iterator

using llvm::SmallBitVector::const_set_bits_iterator = const_set_bits_iterator_impl<SmallBitVector>

Definition at line 172 of file SmallBitVector.h.

◆ set_iterator

using llvm::SmallBitVector::set_iterator = const_set_bits_iterator

Definition at line 173 of file SmallBitVector.h.

◆ size_type

using llvm::SmallBitVector::size_type = uintptr_t

Definition at line 64 of file SmallBitVector.h.

Constructor & Destructor Documentation

◆ SmallBitVector() [1/4]

llvm::SmallBitVector::SmallBitVector ( )

default

Creates an empty bitvector.

Referenced by anyCommon(), flip(), flip(), llvm::SmallBitVector::reference::operator bool(), operator!=(), operator&=(), operator<<=(), operator=(), operator=(), operator==(), operator>>=(), operator^=(), operator|=(), operator~(), llvm::SmallBitVector::reference::reference(), reset(), reset(), reset(), reset(), set(), set(), set(), SmallBitVector(), SmallBitVector(), swap(), and test().

◆ SmallBitVector() [2/4]

llvm::SmallBitVector::SmallBitVector	(	unsigned	s,
		bool	t = false )

inlineexplicit

Creates a bitvector of specified number of bits.

All bits are initialized to the specified value.

Definition at line 148 of file SmallBitVector.h.

◆ SmallBitVector() [3/4]

llvm::SmallBitVector::SmallBitVector ( const SmallBitVector & RHS )

inline

SmallBitVector copy ctor.

Definition at line 156 of file SmallBitVector.h.

References RHS, and SmallBitVector().

◆ SmallBitVector() [4/4]

llvm::SmallBitVector::SmallBitVector ( SmallBitVector && RHS )

inline

Definition at line 163 of file SmallBitVector.h.

References RHS, and SmallBitVector().

◆ ~SmallBitVector()

llvm::SmallBitVector::~SmallBitVector ( )

inline

Definition at line 167 of file SmallBitVector.h.

References isSmall().

Member Function Documentation

◆ all()

bool llvm::SmallBitVector::all ( ) const

inline

Returns true if all bits are set.

Definition at line 216 of file SmallBitVector.h.

References isSmall().

Referenced by llvm::slpvectorizer::BoUpSLP::findReusedOrderedScalars(), foldInsSequenceIntoSplat(), generateKeySubkey(), getShufflevectorNumGroups(), llvm::CombinerHelper::matchExtractAllEltsFromBuildVector(), performExtractsShuffleAction(), simplifyReductionOperand(), and llvm::LegalizationArtifactCombiner::ArtifactValueFinder::tryCombineUnmergeDefs().

◆ any()

bool llvm::SmallBitVector::any ( ) const

inline

Returns true if any bit is set.

Definition at line 209 of file SmallBitVector.h.

References isSmall().

Referenced by llvm::DependenceInfo::depends(), llvm::slpvectorizer::BoUpSLP::findReusedOrderedScalars(), and llvm::DependenceInfo::getSplitIteration().

◆ anyCommon()

bool llvm::SmallBitVector::anyCommon ( const SmallBitVector & RHS ) const

inline

Test if any common bits are set.

Definition at line 490 of file SmallBitVector.h.

References isSmall(), RHS, size(), SmallBitVector(), and test.

◆ back()

bool llvm::SmallBitVector::back ( ) const

inline

Return the last element in the vector.

Definition at line 469 of file SmallBitVector.h.

References assert(), empty(), and size().

◆ clear()

void llvm::SmallBitVector::clear ( )

inline

Clear all bits.

Definition at line 325 of file SmallBitVector.h.

References isSmall().

Referenced by operator=().

◆ clearBitsInMask()

void llvm::SmallBitVector::clearBitsInMask	(	const uint32_t *	Mask,
		unsigned	MaskWords = ~0u )

inline

Clear any bits in this vector that are set in Mask.

Don't resize. This computes "*this &= ~Mask".

Definition at line 657 of file SmallBitVector.h.

References isSmall().

◆ clearBitsNotInMask()

void llvm::SmallBitVector::clearBitsNotInMask	(	const uint32_t *	Mask,
		unsigned	MaskWords = ~0u )

inline

Clear a bit in this vector for every '0' bit in Mask.

Don't resize. This computes "*this &= Mask".

Definition at line 675 of file SmallBitVector.h.

References isSmall().

◆ count()

size_type llvm::SmallBitVector::count ( ) const

inline

Returns the number of bits which are set.

Definition at line 200 of file SmallBitVector.h.

References isSmall(), and llvm::popcount().

Referenced by llvm::DependenceInfo::depends(), find_first_unset(), find_last_unset(), and fixupOrderingIndices().

◆ empty()

bool llvm::SmallBitVector::empty ( ) const

inline

Tests whether there are no bits in this bitvector.

Definition at line 190 of file SmallBitVector.h.

References isSmall().

Referenced by back(), llvm::DependenceInfo::getSplitIteration(), invalid(), and pop_back().

◆ find_first()

int llvm::SmallBitVector::find_first ( ) const

inline

Returns the index of the first set bit, -1 if none of the bits are set.

Definition at line 230 of file SmallBitVector.h.

References llvm::countr_zero(), and isSmall().

Referenced by findMainViewFileID(), and fixupOrderingIndices().

◆ find_first_unset()

int llvm::SmallBitVector::find_first_unset ( ) const

inline

Returns the index of the first unset bit, -1 if all of the bits are set.

Definition at line 251 of file SmallBitVector.h.

References count(), llvm::countr_one(), and isSmall().

◆ find_last()

int llvm::SmallBitVector::find_last ( ) const

inline

Definition at line 240 of file SmallBitVector.h.

References llvm::countl_zero(), and isSmall().

◆ find_last_unset()

int llvm::SmallBitVector::find_last_unset ( ) const

inline

Definition at line 262 of file SmallBitVector.h.

References count(), llvm::countl_one(), and isSmall().

◆ find_next()

int llvm::SmallBitVector::find_next ( unsigned Prev ) const

inline

Returns the index of the next set bit following the "Prev" bit.

Returns -1 if the next set bit is not found.

Definition at line 277 of file SmallBitVector.h.

References llvm::countr_zero(), and isSmall().

Referenced by dumpSmallBitVector(), and fixupOrderingIndices().

◆ find_next_unset()

int llvm::SmallBitVector::find_next_unset ( unsigned Prev ) const

inline

Returns the index of the next unset bit following the "Prev" bit.

Returns -1 if the next unset bit is not found.

Definition at line 291 of file SmallBitVector.h.

References llvm::countr_one(), and isSmall().

◆ find_prev()

int llvm::SmallBitVector::find_prev ( unsigned PriorTo ) const

inline

find_prev - Returns the index of the first set bit that precedes the the bit at PriorTo.

Returns -1 if all previous bits are unset.

Definition at line 308 of file SmallBitVector.h.

References llvm::countl_zero(), isSmall(), and llvm::maskTrailingOnes().

◆ flip() [1/2]

SmallBitVector & llvm::SmallBitVector::flip ( )

inline

Definition at line 434 of file SmallBitVector.h.

References isSmall(), and SmallBitVector().

Referenced by operator~().

◆ flip() [2/2]

SmallBitVector & llvm::SmallBitVector::flip ( unsigned Idx )

inline

Definition at line 442 of file SmallBitVector.h.

References isSmall(), and SmallBitVector().

◆ getData()

ArrayRef< uintptr_t > llvm::SmallBitVector::getData ( uintptr_t & Store ) const

inline

Definition at line 688 of file SmallBitVector.h.

References isSmall().

◆ invalid()

void llvm::SmallBitVector::invalid ( )

inline

Definition at line 682 of file SmallBitVector.h.

References assert(), and empty().

Referenced by llvm::DenseMapInfo< SmallBitVector >::getTombstoneKey().

◆ isInvalid()

bool llvm::SmallBitVector::isInvalid ( ) const

inline

Definition at line 686 of file SmallBitVector.h.

◆ isSmall()

bool llvm::SmallBitVector::isSmall ( ) const

inline

Definition at line 187 of file SmallBitVector.h.

Referenced by all(), any(), anyCommon(), clear(), clearBitsInMask(), clearBitsNotInMask(), count(), empty(), find_first(), find_first_unset(), find_last(), find_last_unset(), find_next(), find_next_unset(), find_prev(), flip(), flip(), getData(), none(), operator&=(), operator<<=(), operator=(), operator==(), operator>>=(), operator[](), operator^=(), operator|=(), reserve(), reset(), reset(), reset(), reset(), resize(), set(), set(), set(), setBitsInMask(), setBitsNotInMask(), size(), test(), and ~SmallBitVector().

◆ none()

bool llvm::SmallBitVector::none ( ) const

inline

Returns true if none of the bits are set.

Definition at line 223 of file SmallBitVector.h.

References isSmall().

Referenced by fixupOrderingIndices().

◆ operator!=()

bool llvm::SmallBitVector::operator!= ( const SmallBitVector & RHS ) const

inline

Definition at line 519 of file SmallBitVector.h.

References RHS, and SmallBitVector().

◆ operator&=()

SmallBitVector & llvm::SmallBitVector::operator&= ( const SmallBitVector & RHS )

inline

Definition at line 525 of file SmallBitVector.h.

References E(), I, isSmall(), reset(), resize(), RHS, size(), SmallBitVector(), and test.

◆ operator<<=()

SmallBitVector & llvm::SmallBitVector::operator<<= ( unsigned N )

inline

Definition at line 600 of file SmallBitVector.h.

References isSmall(), N, and SmallBitVector().

◆ operator=() [1/2]

const SmallBitVector & llvm::SmallBitVector::operator= ( const SmallBitVector & RHS )

inline

Definition at line 617 of file SmallBitVector.h.

References isSmall(), RHS, and SmallBitVector().

◆ operator=() [2/2]

const SmallBitVector & llvm::SmallBitVector::operator= ( SmallBitVector && RHS )

inline

Definition at line 634 of file SmallBitVector.h.

References clear(), RHS, SmallBitVector(), and swap().

◆ operator==()

bool llvm::SmallBitVector::operator== ( const SmallBitVector & RHS ) const

inline

Definition at line 503 of file SmallBitVector.h.

References E(), I, isSmall(), RHS, size(), and SmallBitVector().

◆ operator>>=()

SmallBitVector & llvm::SmallBitVector::operator>>= ( unsigned N )

inline

Definition at line 608 of file SmallBitVector.h.

References isSmall(), N, and SmallBitVector().

◆ operator[]() [1/2]

reference llvm::SmallBitVector::operator[] ( unsigned Idx )

inline

Definition at line 456 of file SmallBitVector.h.

References assert(), and size().

◆ operator[]() [2/2]

bool llvm::SmallBitVector::operator[] ( unsigned Idx ) const

inline

Definition at line 461 of file SmallBitVector.h.

References assert(), isSmall(), and size().

◆ operator^=()

SmallBitVector & llvm::SmallBitVector::operator^= ( const SmallBitVector & RHS )

inline

Definition at line 587 of file SmallBitVector.h.

References E(), I, isSmall(), resize(), RHS, size(), SmallBitVector(), and test.

◆ operator|=()

SmallBitVector & llvm::SmallBitVector::operator|= ( const SmallBitVector & RHS )

inline

Definition at line 574 of file SmallBitVector.h.

References E(), I, isSmall(), resize(), RHS, size(), SmallBitVector(), and test.

◆ operator~()

SmallBitVector llvm::SmallBitVector::operator~ ( ) const

inline

Definition at line 451 of file SmallBitVector.h.

References flip(), and SmallBitVector().

◆ pop_back()

void llvm::SmallBitVector::pop_back ( )

inline

Pop one bit from the end of the vector.

Definition at line 484 of file SmallBitVector.h.

References assert(), empty(), resize(), and size().

◆ push_back()

void llvm::SmallBitVector::push_back ( bool Val )

inline

Definition at line 479 of file SmallBitVector.h.

References resize(), and size().

◆ reserve()

void llvm::SmallBitVector::reserve ( unsigned N )

inline

Definition at line 348 of file SmallBitVector.h.

References I, isSmall(), N, llvm::BitVector::reserve(), and llvm::BitVector::set().

◆ reset() [1/4]

SmallBitVector & llvm::SmallBitVector::reset ( )

inline

Definition at line 402 of file SmallBitVector.h.

References isSmall(), and SmallBitVector().

Referenced by llvm::DependenceInfo::depends(), fixupOrderingIndices(), llvm::DependenceInfo::getSplitIteration(), operator&=(), and reset().

◆ reset() [2/4]

SmallBitVector & llvm::SmallBitVector::reset ( const SmallBitVector & RHS )

inline

Reset bits that are set in RHS. Same as *this &= ~RHS.

Definition at line 542 of file SmallBitVector.h.

References isSmall(), reset(), RHS, size(), and SmallBitVector().

◆ reset() [3/4]

SmallBitVector & llvm::SmallBitVector::reset	(	unsigned	I,
		unsigned	E )

inline

Efficiently reset a range of bits in [I, E)

Definition at line 419 of file SmallBitVector.h.

References assert(), E(), I, isSmall(), size(), and SmallBitVector().

◆ reset() [4/4]

SmallBitVector & llvm::SmallBitVector::reset ( unsigned Idx )

inline

Definition at line 410 of file SmallBitVector.h.

References isSmall(), and SmallBitVector().

◆ resize()

void llvm::SmallBitVector::resize	(	unsigned	N,
		bool	t = false )

inline

Grow or shrink the bitvector.

Definition at line 332 of file SmallBitVector.h.

References E(), I, isSmall(), and N.

Referenced by lowerShuffleAsSplitOrBlend(), operator&=(), operator^=(), operator|=(), pop_back(), and push_back().

◆ set() [1/3]

◆ set() [2/3]

SmallBitVector & llvm::SmallBitVector::set	(	unsigned	I,
		unsigned	E )

inline

Efficiently set a range of bits in [I, E)

Definition at line 387 of file SmallBitVector.h.

References assert(), E(), I, isSmall(), size(), and SmallBitVector().

◆ set() [3/3]

SmallBitVector & llvm::SmallBitVector::set ( unsigned Idx )

inline

Definition at line 374 of file SmallBitVector.h.

References assert(), isSmall(), set(), and SmallBitVector().

◆ set_bits()

iterator_range< const_set_bits_iterator > llvm::SmallBitVector::set_bits ( ) const

inline

Definition at line 183 of file SmallBitVector.h.

References llvm::make_range(), set_bits_begin(), and set_bits_end().

Referenced by llvm::DependenceInfo::depends(), dumpSmallBitVector(), and llvm::DependenceInfo::getSplitIteration().

◆ set_bits_begin()

const_set_bits_iterator llvm::SmallBitVector::set_bits_begin ( ) const

inline

Definition at line 175 of file SmallBitVector.h.

Referenced by set_bits().

◆ set_bits_end()

const_set_bits_iterator llvm::SmallBitVector::set_bits_end ( ) const

inline

Definition at line 179 of file SmallBitVector.h.

Referenced by set_bits().

◆ setBitsInMask()

void llvm::SmallBitVector::setBitsInMask	(	const uint32_t *	Mask,
		unsigned	MaskWords = ~0u )

inline

Add '1' bits from Mask to this vector.

Don't resize. This computes "*this |= Mask".

Definition at line 648 of file SmallBitVector.h.

References isSmall().

◆ setBitsNotInMask()

void llvm::SmallBitVector::setBitsNotInMask	(	const uint32_t *	Mask,
		unsigned	MaskWords = ~0u )

inline

Add a bit to this vector for every '0' bit in Mask.

Don't resize. This computes "*this |= ~Mask".

Definition at line 666 of file SmallBitVector.h.

References isSmall().

◆ size()

size_type llvm::SmallBitVector::size ( ) const

inline

Returns the number of bits in this bitvector.

Definition at line 195 of file SmallBitVector.h.

References isSmall().

Referenced by anyCommon(), back(), llvm::X86TTIImpl::isLegalAltInstr(), operator&=(), operator==(), operator[](), operator[](), operator^=(), operator|=(), pop_back(), push_back(), reset(), reset(), set(), and test().

◆ swap()

void llvm::SmallBitVector::swap ( SmallBitVector & RHS )

inline

Definition at line 642 of file SmallBitVector.h.

References RHS, SmallBitVector(), and std::swap().

Referenced by operator=().

◆ test() [1/2]

bool llvm::SmallBitVector::test ( const SmallBitVector & RHS ) const

inline

Check if (This - RHS) is zero. This is the same as reset(RHS) and any().

Definition at line 556 of file SmallBitVector.h.

References isSmall(), RHS, size(), SmallBitVector(), and test.

◆ test() [2/2]

bool llvm::SmallBitVector::test ( unsigned Idx ) const

inline

Definition at line 474 of file SmallBitVector.h.

Referenced by llvm::DwarfExpression::addMachineReg(), areTwoInsertFromSameBuildVector(), combineOrders(), llvm::slpvectorizer::BoUpSLP::findReusedOrderedScalars(), llvm::slpvectorizer::BoUpSLP::getReorderingData(), llvm::X86TTIImpl::isLegalAltInstr(), performExtractsShuffleAction(), and simplifyReductionOperand().

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

include/llvm/ADT/SmallBitVector.h

Classes

Public Types

Public Member Functions

Detailed Description

Member Typedef Documentation

◆ const_set_bits_iterator

◆ set_iterator

◆ size_type

Constructor & Destructor Documentation

◆ SmallBitVector() [1/4]

◆ SmallBitVector() [2/4]

◆ SmallBitVector() [3/4]

◆ SmallBitVector() [4/4]

◆ ~SmallBitVector()

Member Function Documentation

◆ all()

◆ any()

◆ anyCommon()

◆ back()

◆ clear()

◆ clearBitsInMask()

◆ clearBitsNotInMask()

◆ count()

◆ empty()

◆ find_first()

◆ find_first_unset()

◆ find_last()

◆ find_last_unset()

◆ find_next()

◆ find_next_unset()

◆ find_prev()

◆ flip() [1/2]

◆ flip() [2/2]

◆ getData()

◆ invalid()

◆ isInvalid()

◆ isSmall()

◆ none()

◆ operator!=()

◆ operator&=()

◆ operator<<=()

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ operator==()

◆ operator>>=()

◆ operator[]() [1/2]

◆ operator[]() [2/2]

◆ operator^=()

◆ operator|=()

◆ operator~()

◆ pop_back()

◆ push_back()

◆ reserve()

◆ reset() [1/4]

◆ reset() [2/4]

◆ reset() [3/4]

◆ reset() [4/4]

◆ resize()

◆ set() [1/3]

◆ set() [2/3]

◆ set() [3/3]

◆ set_bits()

◆ set_bits_begin()

◆ set_bits_end()

◆ setBitsInMask()

◆ setBitsNotInMask()

◆ size()

◆ swap()

◆ test() [1/2]

◆ test() [2/2]