14#ifndef LLVM_ADT_DENSEMAP_H
15#define LLVM_ADT_DENSEMAP_H
32#include <initializer_list>
44template <
typename KeyT,
typename ValueT>
46 using std::pair<
KeyT, ValueT>::pair;
49 const KeyT &
getFirst()
const {
return std::pair<KeyT, ValueT>::first; }
50 ValueT &
getSecond() {
return std::pair<KeyT, ValueT>::second; }
51 const ValueT &
getSecond()
const {
return std::pair<KeyT, ValueT>::second; }
56template <
typename KeyT,
typename ValueT,
57 typename KeyInfoT = DenseMapInfo<KeyT>,
60class DenseMapIterator;
62template <
typename DerivedT,
typename KeyT,
typename ValueT,
typename KeyInfoT,
92 [[nodiscard]]
inline auto keys() {
93 return map_range(*
this, [](
const BucketT &
P) {
return P.getFirst(); });
98 return map_range(*
this, [](
const BucketT &
P) {
return P.getSecond(); });
101 [[nodiscard]]
inline auto keys()
const {
102 return map_range(*
this, [](
const BucketT &
P) {
return P.getFirst(); });
105 [[nodiscard]]
inline auto values()
const {
106 return map_range(*
this, [](
const BucketT &
P) {
return P.getSecond(); });
109 [[nodiscard]]
bool empty()
const {
return getNumEntries() == 0; }
110 [[nodiscard]]
unsigned size()
const {
return getNumEntries(); }
117 if (NumBuckets > getNumBuckets())
123 if (getNumEntries() == 0 && getNumTombstones() == 0)
128 if (getNumEntries() * 4 < getNumBuckets() && getNumBuckets() > 64) {
134 if constexpr (std::is_trivially_destructible_v<ValueT>) {
136 for (BucketT &
B : buckets())
137 B.getFirst() = EmptyKey;
140 unsigned NumEntries = getNumEntries();
141 for (BucketT &
B : buckets()) {
142 if (!KeyInfoT::isEqual(
B.getFirst(), EmptyKey)) {
143 if (!KeyInfoT::isEqual(
B.getFirst(), TombstoneKey)) {
144 B.getSecond().~ValueT();
147 B.getFirst() = EmptyKey;
150 assert(NumEntries == 0 &&
"Node count imbalance!");
158 [[nodiscard]]
bool contains(const_arg_type_t<KeyT> Val)
const {
159 return doFind(Val) !=
nullptr;
179 template <
class LookupKeyT>
181 if (BucketT *Bucket = doFind(Val))
182 return makeIterator(Bucket);
185 template <
class LookupKeyT>
187 if (
const BucketT *Bucket = doFind(Val))
188 return makeConstIterator(Bucket);
194 [[nodiscard]] ValueT
lookup(const_arg_type_t<KeyT> Val)
const {
195 if (
const BucketT *Bucket = doFind(Val))
196 return Bucket->getSecond();
203 template <
typename U = std::remove_cv_t<ValueT>>
204 [[nodiscard]] ValueT
lookup_or(const_arg_type_t<KeyT> Val,
206 if (
const BucketT *Bucket = doFind(Val))
207 return Bucket->getSecond();
213 [[nodiscard]]
const ValueT &
at(const_arg_type_t<KeyT> Val)
const {
214 auto Iter = this->
find(std::move(Val));
215 assert(Iter != this->
end() &&
"DenseMap::at failed due to a missing key");
222 std::pair<iterator, bool>
insert(
const std::pair<KeyT, ValueT> &KV) {
223 return try_emplace_impl(KV.first, KV.second);
229 std::pair<iterator, bool>
insert(std::pair<KeyT, ValueT> &&KV) {
230 return try_emplace_impl(std::move(KV.first), std::move(KV.second));
236 template <
typename... Ts>
238 return try_emplace_impl(std::move(
Key), std::forward<Ts>(Args)...);
244 template <
typename... Ts>
246 return try_emplace_impl(
Key, std::forward<Ts>(Args)...);
254 template <
typename LookupKeyT>
255 std::pair<iterator, bool>
insert_as(std::pair<KeyT, ValueT> &&KV,
256 const LookupKeyT &Val) {
258 if (LookupBucketFor(Val, TheBucket))
259 return {makeIterator(TheBucket),
false};
262 TheBucket = findBucketForInsertion(Val, TheBucket);
263 TheBucket->getFirst() = std::move(KV.first);
264 ::new (&TheBucket->getSecond()) ValueT(std::move(KV.second));
265 return {makeIterator(TheBucket),
true};
269 template <
typename InputIt>
void insert(InputIt
I, InputIt
E) {
279 template <
typename V>
283 Ret.first->second = std::forward<V>(Val);
287 template <
typename V>
291 Ret.first->second = std::forward<V>(Val);
295 template <
typename... Ts>
299 Ret.first->second = ValueT(std::forward<Ts>(Args)...);
303 template <
typename... Ts>
305 auto Ret =
try_emplace(std::move(
Key), std::forward<Ts>(Args)...);
307 Ret.first->second = ValueT(std::forward<Ts>(Args)...);
312 BucketT *TheBucket = doFind(Val);
316 TheBucket->getSecond().~ValueT();
318 decrementNumEntries();
319 incrementNumTombstones();
323 BucketT *TheBucket = &*
I;
324 TheBucket->getSecond().~ValueT();
326 decrementNumEntries();
327 incrementNumTombstones();
331 return lookupOrInsertIntoBucket(
Key).first->second;
335 return lookupOrInsertIntoBucket(std::move(
Key)).first->second;
342 return Ptr >= getBuckets() &&
Ptr < getBucketsEnd();
356 if (getNumBuckets() == 0)
360 for (BucketT &
B : buckets()) {
361 if (!KeyInfoT::isEqual(
B.getFirst(), EmptyKey) &&
362 !KeyInfoT::isEqual(
B.getFirst(), TombstoneKey))
363 B.getSecond().~ValueT();
364 B.getFirst().~KeyT();
372 assert((getNumBuckets() & (getNumBuckets() - 1)) == 0 &&
373 "# initial buckets must be a power of two!");
375 for (BucketT &
B : buckets())
376 ::new (&
B.getFirst())
KeyT(EmptyKey);
396 for (BucketT &
B : OldBuckets) {
397 if (!KeyInfoT::isEqual(
B.getFirst(), EmptyKey) &&
398 !KeyInfoT::isEqual(
B.getFirst(), TombstoneKey)) {
401 bool FoundVal = LookupBucketFor(
B.getFirst(), DestBucket);
403 assert(!FoundVal &&
"Key already in new map?");
404 DestBucket->getFirst() = std::move(
B.getFirst());
405 ::new (&DestBucket->getSecond()) ValueT(std::move(
B.getSecond()));
406 incrementNumEntries();
409 B.getSecond().~ValueT();
411 B.getFirst().~KeyT();
415 template <
typename OtherBaseT>
419 assert(getNumBuckets() == other.getNumBuckets());
421 setNumEntries(other.getNumEntries());
422 setNumTombstones(other.getNumTombstones());
424 BucketT *Buckets = getBuckets();
425 const BucketT *OtherBuckets = other.getBuckets();
426 const size_t NumBuckets = getNumBuckets();
427 if constexpr (std::is_trivially_copyable_v<KeyT> &&
428 std::is_trivially_copyable_v<ValueT>) {
429 memcpy(
reinterpret_cast<void *
>(Buckets), OtherBuckets,
430 NumBuckets *
sizeof(BucketT));
434 for (
size_t I = 0;
I < NumBuckets; ++
I) {
435 ::new (&Buckets[
I].getFirst())
KeyT(OtherBuckets[
I].getFirst());
436 if (!KeyInfoT::isEqual(Buckets[
I].getFirst(), EmptyKey) &&
437 !KeyInfoT::isEqual(Buckets[
I].getFirst(), TombstoneKey))
438 ::new (&Buckets[
I].getSecond()) ValueT(OtherBuckets[
I].getSecond());
444 return KeyInfoT::getHashValue(Val);
447 template <
typename LookupKeyT>
449 return KeyInfoT::getHashValue(Val);
453 static_assert(std::is_base_of_v<DenseMapBase, DerivedT>,
454 "Must pass the derived type to this template!");
455 return KeyInfoT::getEmptyKey();
461 DerivedT &derived() {
return *
static_cast<DerivedT *
>(
this); }
462 const DerivedT &derived()
const {
463 return *
static_cast<const DerivedT *
>(
this);
466 template <
typename KeyArgT,
typename... Ts>
467 std::pair<BucketT *, bool> lookupOrInsertIntoBucket(KeyArgT &&
Key,
469 BucketT *TheBucket =
nullptr;
470 if (LookupBucketFor(
Key, TheBucket))
471 return {TheBucket,
false};
474 TheBucket = findBucketForInsertion(
Key, TheBucket);
475 TheBucket->getFirst() = std::forward<KeyArgT>(
Key);
476 ::new (&TheBucket->getSecond()) ValueT(std::forward<Ts>(Args)...);
477 return {TheBucket,
true};
480 template <
typename KeyArgT,
typename... Ts>
481 std::pair<iterator, bool> try_emplace_impl(KeyArgT &&
Key, Ts &&...Args) {
482 auto [Bucket,
Inserted] = lookupOrInsertIntoBucket(
483 std::forward<KeyArgT>(
Key), std::forward<Ts>(Args)...);
484 return {makeIterator(Bucket),
Inserted};
487 iterator makeIterator(BucketT *TheBucket) {
491 const_iterator makeConstIterator(
const BucketT *TheBucket)
const {
495 unsigned getNumEntries()
const {
return derived().getNumEntries(); }
497 void setNumEntries(
unsigned Num) { derived().setNumEntries(Num); }
499 void incrementNumEntries() { setNumEntries(getNumEntries() + 1); }
501 void decrementNumEntries() { setNumEntries(getNumEntries() - 1); }
503 unsigned getNumTombstones()
const {
return derived().getNumTombstones(); }
505 void setNumTombstones(
unsigned Num) { derived().setNumTombstones(Num); }
507 void incrementNumTombstones() { setNumTombstones(getNumTombstones() + 1); }
509 void decrementNumTombstones() { setNumTombstones(getNumTombstones() - 1); }
511 const BucketT *getBuckets()
const {
return derived().getBuckets(); }
513 BucketT *getBuckets() {
return derived().getBuckets(); }
515 unsigned getNumBuckets()
const {
return derived().getNumBuckets(); }
517 BucketT *getBucketsEnd() {
return getBuckets() + getNumBuckets(); }
519 const BucketT *getBucketsEnd()
const {
520 return getBuckets() + getNumBuckets();
531 void grow(
unsigned AtLeast) { derived().grow(AtLeast); }
533 void shrink_and_clear() { derived().shrink_and_clear(); }
535 template <
typename LookupKeyT>
536 BucketT *findBucketForInsertion(
const LookupKeyT &
Lookup,
537 BucketT *TheBucket) {
549 unsigned NewNumEntries = getNumEntries() + 1;
550 unsigned NumBuckets = getNumBuckets();
552 this->grow(NumBuckets * 2);
553 LookupBucketFor(
Lookup, TheBucket);
555 (NewNumEntries + getNumTombstones()) <=
557 this->grow(NumBuckets);
558 LookupBucketFor(
Lookup, TheBucket);
564 incrementNumEntries();
568 if (!KeyInfoT::isEqual(TheBucket->getFirst(), EmptyKey))
569 decrementNumTombstones();
574 template <
typename LookupKeyT>
575 const BucketT *doFind(
const LookupKeyT &Val)
const {
576 const BucketT *BucketsPtr = getBuckets();
577 const unsigned NumBuckets = getNumBuckets();
582 unsigned BucketNo =
getHashValue(Val) & (NumBuckets - 1);
583 unsigned ProbeAmt = 1;
585 const BucketT *Bucket = BucketsPtr + BucketNo;
586 if (
LLVM_LIKELY(KeyInfoT::isEqual(Val, Bucket->getFirst())))
588 if (
LLVM_LIKELY(KeyInfoT::isEqual(Bucket->getFirst(), EmptyKey)))
593 BucketNo += ProbeAmt++;
594 BucketNo &= NumBuckets - 1;
598 template <
typename LookupKeyT> BucketT *doFind(
const LookupKeyT &Val) {
599 return const_cast<BucketT *
>(
607 template <
typename LookupKeyT>
608 bool LookupBucketFor(
const LookupKeyT &Val, BucketT *&FoundBucket) {
609 BucketT *BucketsPtr = getBuckets();
610 const unsigned NumBuckets = getNumBuckets();
612 if (NumBuckets == 0) {
613 FoundBucket =
nullptr;
618 BucketT *FoundTombstone =
nullptr;
621 assert(!KeyInfoT::isEqual(Val, EmptyKey) &&
622 !KeyInfoT::isEqual(Val, TombstoneKey) &&
623 "Empty/Tombstone value shouldn't be inserted into map!");
625 unsigned BucketNo =
getHashValue(Val) & (NumBuckets - 1);
626 unsigned ProbeAmt = 1;
628 BucketT *ThisBucket = BucketsPtr + BucketNo;
630 if (
LLVM_LIKELY(KeyInfoT::isEqual(Val, ThisBucket->getFirst()))) {
631 FoundBucket = ThisBucket;
637 if (
LLVM_LIKELY(KeyInfoT::isEqual(ThisBucket->getFirst(), EmptyKey))) {
640 FoundBucket = FoundTombstone ? FoundTombstone : ThisBucket;
646 if (KeyInfoT::isEqual(ThisBucket->getFirst(), TombstoneKey) &&
648 FoundTombstone = ThisBucket;
652 BucketNo += ProbeAmt++;
653 BucketNo &= (NumBuckets - 1);
663 return getNumBuckets() *
sizeof(BucketT);
673template <
typename DerivedT,
typename KeyT,
typename ValueT,
typename KeyInfoT,
678 if (
LHS.size() !=
RHS.size())
681 for (
auto &KV :
LHS) {
682 auto I =
RHS.find(KV.first);
683 if (
I ==
RHS.end() ||
I->second != KV.second)
693template <
typename DerivedT,
typename KeyT,
typename ValueT,
typename KeyInfoT,
701template <
typename KeyT,
typename ValueT,
702 typename KeyInfoT = DenseMapInfo<KeyT>,
705 KeyT, ValueT, KeyInfoT, BucketT> {
714 unsigned NumTombstones;
720 explicit DenseMap(
unsigned NumElementsToReserve = 0) {
721 init(NumElementsToReserve);
734 template <
typename InputIt>
DenseMap(
const InputIt &
I,
const InputIt &
E) {
735 init(std::distance(
I,
E));
739 template <
typename RangeT>
743 DenseMap(std::initializer_list<typename BaseT::value_type> Vals)
777 if (allocateBuckets(other.NumBuckets)) {
786 unsigned OldNumBuckets = NumBuckets;
787 BucketT *OldBuckets = Buckets;
789 allocateBuckets(std::max<unsigned>(
806 unsigned OldNumBuckets = NumBuckets;
807 unsigned OldNumEntries = NumEntries;
811 unsigned NewNumBuckets = 0;
813 NewNumBuckets = std::max(64, 1 << (
Log2_32_Ceil(OldNumEntries) + 1));
814 if (NewNumBuckets == NumBuckets) {
825 unsigned getNumEntries()
const {
return NumEntries; }
827 void setNumEntries(
unsigned Num) { NumEntries = Num; }
829 unsigned getNumTombstones()
const {
return NumTombstones; }
831 void setNumTombstones(
unsigned Num) { NumTombstones = Num; }
833 BucketT *getBuckets()
const {
return Buckets; }
835 unsigned getNumBuckets()
const {
return NumBuckets; }
837 void deallocateBuckets() {
841 bool allocateBuckets(
unsigned Num) {
843 if (NumBuckets == 0) {
848 Buckets =
static_cast<BucketT *
>(
853 void init(
unsigned InitNumEntries) {
855 if (allocateBuckets(InitBuckets)) {
864template <
typename KeyT,
typename ValueT,
unsigned InlineBuckets = 4,
865 typename KeyInfoT = DenseMapInfo<KeyT>,
869 SmallDenseMap<KeyT, ValueT, InlineBuckets, KeyInfoT, BucketT>, KeyT,
870 ValueT, KeyInfoT, BucketT> {
878 "InlineBuckets must be a power of 2.");
881 unsigned NumEntries : 31;
882 unsigned NumTombstones;
894 AlignedCharArrayUnion<BucketT[InlineBuckets], LargeRep> storage;
898 init(NumElementsToReserve);
911 template <
typename InputIt>
913 init(std::distance(
I,
E));
917 template <
typename RangeT>
930 unsigned TmpNumEntries =
RHS.NumEntries;
931 RHS.NumEntries = NumEntries;
932 NumEntries = TmpNumEntries;
937 if (Small &&
RHS.Small) {
942 for (
unsigned i = 0, e = InlineBuckets; i != e; ++i) {
943 BucketT *LHSB = &getInlineBuckets()[i],
944 *RHSB = &
RHS.getInlineBuckets()[i];
945 bool hasLHSValue = (!KeyInfoT::isEqual(LHSB->getFirst(), EmptyKey) &&
946 !KeyInfoT::isEqual(LHSB->getFirst(), TombstoneKey));
947 bool hasRHSValue = (!KeyInfoT::isEqual(RHSB->getFirst(), EmptyKey) &&
948 !KeyInfoT::isEqual(RHSB->getFirst(), TombstoneKey));
949 if (hasLHSValue && hasRHSValue) {
955 std::swap(LHSB->getFirst(), RHSB->getFirst());
957 ::new (&RHSB->getSecond()) ValueT(std::move(LHSB->getSecond()));
958 LHSB->getSecond().~ValueT();
959 }
else if (hasRHSValue) {
960 ::new (&LHSB->getSecond()) ValueT(std::move(RHSB->getSecond()));
961 RHSB->getSecond().~ValueT();
966 if (!Small && !
RHS.Small) {
975 LargeRep TmpRep = std::move(*LargeSide.getLargeRep());
976 LargeSide.getLargeRep()->~LargeRep();
977 LargeSide.Small =
true;
982 for (
unsigned i = 0, e = InlineBuckets; i != e; ++i) {
983 BucketT *NewB = &LargeSide.getInlineBuckets()[i],
984 *OldB = &SmallSide.getInlineBuckets()[i];
985 ::new (&NewB->getFirst())
KeyT(std::move(OldB->getFirst()));
986 OldB->getFirst().~KeyT();
987 if (!KeyInfoT::isEqual(NewB->getFirst(), EmptyKey) &&
988 !KeyInfoT::isEqual(NewB->getFirst(), TombstoneKey)) {
989 ::new (&NewB->getSecond()) ValueT(std::move(OldB->getSecond()));
990 OldB->getSecond().~ValueT();
996 SmallSide.Small =
false;
997 new (SmallSide.getLargeRep()) LargeRep(std::move(TmpRep));
1008 deallocateBuckets();
1016 deallocateBuckets();
1017 allocateBuckets(other.getNumBuckets());
1021 void init(
unsigned InitNumEntries) {
1023 allocateBuckets(InitBuckets);
1028 if (AtLeast > InlineBuckets)
1029 AtLeast = std::max<unsigned>(64,
NextPowerOf2(AtLeast - 1));
1034 BucketT *TmpBegin =
reinterpret_cast<BucketT *
>(&TmpStorage);
1035 BucketT *TmpEnd = TmpBegin;
1041 for (BucketT &
B : inlineBuckets()) {
1042 if (!KeyInfoT::isEqual(
B.getFirst(), EmptyKey) &&
1043 !KeyInfoT::isEqual(
B.getFirst(), TombstoneKey)) {
1044 assert(
size_t(TmpEnd - TmpBegin) < InlineBuckets &&
1045 "Too many inline buckets!");
1046 ::new (&TmpEnd->getFirst())
KeyT(std::move(
B.getFirst()));
1047 ::new (&TmpEnd->getSecond()) ValueT(std::move(
B.getSecond()));
1049 B.getSecond().~ValueT();
1051 B.getFirst().~KeyT();
1057 allocateBuckets(AtLeast);
1062 LargeRep OldRep = std::move(*getLargeRep());
1063 getLargeRep()->~LargeRep();
1064 allocateBuckets(AtLeast);
1074 unsigned OldSize = this->
size();
1078 unsigned NewNumBuckets = 0;
1081 if (NewNumBuckets > InlineBuckets && NewNumBuckets < 64u)
1084 if ((Small && NewNumBuckets <= InlineBuckets) ||
1085 (!Small && NewNumBuckets == getLargeRep()->NumBuckets)) {
1090 deallocateBuckets();
1091 init(NewNumBuckets);
1095 unsigned getNumEntries()
const {
return NumEntries; }
1097 void setNumEntries(
unsigned Num) {
1099 assert(Num < (1U << 31) &&
"Cannot support more than 1<<31 entries");
1103 unsigned getNumTombstones()
const {
return NumTombstones; }
1105 void setNumTombstones(
unsigned Num) { NumTombstones = Num; }
1107 const BucketT *getInlineBuckets()
const {
1112 return reinterpret_cast<const BucketT *
>(&storage);
1115 BucketT *getInlineBuckets() {
1116 return const_cast<BucketT *
>(
1117 const_cast<const SmallDenseMap *
>(
this)->getInlineBuckets());
1120 const LargeRep *getLargeRep()
const {
1123 return reinterpret_cast<const LargeRep *
>(&storage);
1126 LargeRep *getLargeRep() {
1127 return const_cast<LargeRep *
>(
1131 const BucketT *getBuckets()
const {
1132 return Small ? getInlineBuckets() : getLargeRep()->Buckets;
1135 BucketT *getBuckets() {
1136 return const_cast<BucketT *
>(
1140 unsigned getNumBuckets()
const {
1141 return Small ? InlineBuckets : getLargeRep()->NumBuckets;
1145 BucketT *Begin = getInlineBuckets();
1149 void deallocateBuckets() {
1154 sizeof(BucketT) * getLargeRep()->NumBuckets,
1156 getLargeRep()->~LargeRep();
1159 void allocateBuckets(
unsigned Num) {
1160 if (Num <= InlineBuckets) {
1164 BucketT *NewBuckets =
static_cast<BucketT *
>(
1166 new (getLargeRep()) LargeRep{NewBuckets, Num};
1171template <
typename KeyT,
typename ValueT,
typename KeyInfoT,
typename Bucket,
1174 friend class DenseMapIterator<
KeyT, ValueT, KeyInfoT, Bucket,
true>;
1175 friend class DenseMapIterator<
KeyT, ValueT, KeyInfoT, Bucket,
false>;
1179 using value_type = std::conditional_t<IsConst, const Bucket, Bucket>;
1186 std::conditional_t<shouldReverseIterate<KeyT>(),
1187 std::reverse_iterator<pointer>,
pointer>;
1189 BucketItTy Ptr = {};
1190 BucketItTy End = {};
1205 return makeEnd(Buckets, Epoch);
1206 auto R = maybeReverse(Buckets);
1207 DenseMapIterator Iter(R.begin(), R.end(), Epoch);
1208 Iter.AdvancePastEmptyBuckets();
1214 auto R = maybeReverse(Buckets);
1221 auto R = maybeReverse(Buckets);
1229 template <
bool IsConstSrc,
1230 typename = std::enable_if_t<!IsConstSrc && IsConst>>
1232 const DenseMapIterator<KeyT, ValueT, KeyInfoT, Bucket, IsConstSrc> &
I)
1237 assert(Ptr != End &&
"dereferencing end() iterator");
1243 const DenseMapIterator &
RHS) {
1244 assert((!
LHS.getEpochAddress() ||
LHS.isHandleInSync()) &&
1245 "handle not in sync!");
1246 assert((!
RHS.getEpochAddress() ||
RHS.isHandleInSync()) &&
1247 "handle not in sync!");
1248 assert(
LHS.getEpochAddress() ==
RHS.getEpochAddress() &&
1249 "comparing incomparable iterators!");
1250 return LHS.Ptr ==
RHS.Ptr;
1254 const DenseMapIterator &
RHS) {
1260 assert(Ptr != End &&
"incrementing end() iterator");
1262 AdvancePastEmptyBuckets();
1267 DenseMapIterator tmp = *
this;
1273 void AdvancePastEmptyBuckets() {
1275 const KeyT Empty = KeyInfoT::getEmptyKey();
1278 while (
Ptr != End && (KeyInfoT::isEqual(
Ptr->getFirst(),
Empty) ||
1291template <
typename KeyT,
typename ValueT,
typename KeyInfoT>
1292[[nodiscard]]
inline size_t
1294 return X.getMemorySize();
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
#define LLVM_UNLIKELY(EXPR)
#define LLVM_LIKELY(EXPR)
This file defines DenseMapInfo traits for DenseMap.
This file defines the DebugEpochBase and DebugEpochBase::HandleBase classes.
This file defines counterparts of C library allocation functions defined in the namespace 'std'.
ConstantRange Range(APInt(BitWidth, Low), APInt(BitWidth, High))
This file contains library features backported from future STL versions.
static TableGen::Emitter::OptClass< SkeletonEmitter > X("gen-skeleton-class", "Generate example skeleton class")
LocallyHashedType DenseMapInfo< LocallyHashedType >::Empty
LocallyHashedType DenseMapInfo< LocallyHashedType >::Tombstone
static int Lookup(ArrayRef< TableEntry > Table, unsigned Opcode)
bool isHandleInSync() const
ValueT lookup(const_arg_type_t< KeyT > Val) const
lookup - Return the entry for the specified key, or a default constructed value if no such entry exis...
iterator find(const_arg_type_t< KeyT > Val)
static unsigned getHashValue(const KeyT &Val)
static const KeyT getEmptyKey()
std::pair< iterator, bool > try_emplace(KeyT &&Key, Ts &&...Args)
std::pair< iterator, bool > insert(std::pair< KeyT, ValueT > &&KV)
bool erase(const KeyT &Val)
DenseMapIterator< KeyT, ValueT, KeyInfoT, BucketT > iterator
std::pair< iterator, bool > insert_as(std::pair< KeyT, ValueT > &&KV, const LookupKeyT &Val)
Alternate version of insert() which allows a different, and possibly less expensive,...
const_iterator find_as(const LookupKeyT &Val) const
const_iterator end() const
void moveFromOldBuckets(iterator_range< BucketT * > OldBuckets)
iterator find_as(const LookupKeyT &Val)
Alternate version of find() which allows a different, and possibly less expensive,...
const_iterator find(const_arg_type_t< KeyT > Val) const
std::pair< iterator, bool > emplace_or_assign(const KeyT &Key, Ts &&...Args)
void insert(InputIt I, InputIt E)
insert - Range insertion of pairs.
size_type count(const_arg_type_t< KeyT > Val) const
Return 1 if the specified key is in the map, 0 otherwise.
DenseMapIterator< KeyT, ValueT, KeyInfoT, BucketT, true > const_iterator
static const KeyT getTombstoneKey()
const ValueT & at(const_arg_type_t< KeyT > Val) const
at - Return the entry for the specified key, or abort if no such entry exists.
bool isPointerIntoBucketsArray(const void *Ptr) const
isPointerIntoBucketsArray - Return true if the specified pointer points somewhere into the DenseMap's...
void copyFrom(const DenseMapBase< OtherBaseT, KeyT, ValueT, KeyInfoT, BucketT > &other)
bool contains(const_arg_type_t< KeyT > Val) const
Return true if the specified key is in the map, false otherwise.
std::pair< iterator, bool > try_emplace(const KeyT &Key, Ts &&...Args)
const_iterator begin() const
std::pair< iterator, bool > emplace_or_assign(KeyT &&Key, Ts &&...Args)
void insert_range(Range &&R)
Inserts range of 'std::pair<KeyT, ValueT>' values into the map.
const void * getPointerIntoBucketsArray() const
getPointerIntoBucketsArray() - Return an opaque pointer into the buckets array.
std::pair< iterator, bool > insert_or_assign(KeyT &&Key, V &&Val)
ValueT lookup_or(const_arg_type_t< KeyT > Val, U &&Default) const
unsigned getMinBucketToReserveForEntries(unsigned NumEntries)
Returns the number of buckets to allocate to ensure that the DenseMap can accommodate NumEntries with...
static unsigned getHashValue(const LookupKeyT &Val)
ValueT & operator[](const KeyT &Key)
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
std::pair< iterator, bool > insert_or_assign(const KeyT &Key, V &&Val)
void reserve(size_type NumEntries)
Grow the densemap so that it can contain at least NumEntries items before resizing again.
ValueT & operator[](KeyT &&Key)
size_t getMemorySize() const
Return the approximate size (in bytes) of the actual map.
std::conditional_t< IsConst, const BucketT, BucketT > value_type
static DenseMapIterator makeIterator(pointer P, iterator_range< pointer > Buckets, const DebugEpochBase &Epoch)
friend bool operator!=(const DenseMapIterator &LHS, const DenseMapIterator &RHS)
DenseMapIterator & operator++()
pointer operator->() const
reference operator*() const
DenseMapIterator()=default
static DenseMapIterator makeBegin(iterator_range< pointer > Buckets, bool IsEmpty, const DebugEpochBase &Epoch)
DenseMapIterator operator++(int)
DenseMapIterator(const DenseMapIterator< KeyT, ValueT, KeyInfoT, Bucket, IsConstSrc > &I)
ptrdiff_t difference_type
friend bool operator==(const DenseMapIterator &LHS, const DenseMapIterator &RHS)
static DenseMapIterator makeEnd(iterator_range< pointer > Buckets, const DebugEpochBase &Epoch)
std::forward_iterator_tag iterator_category
DenseMap(std::initializer_list< typename BaseT::value_type > Vals)
DenseMap(unsigned NumElementsToReserve=0)
Create a DenseMap with an optional NumElementsToReserve to guarantee that this number of elements can...
void copyFrom(const DenseMap &other)
DenseMap & operator=(DenseMap &&other)
void grow(unsigned AtLeast)
DenseMap(llvm::from_range_t, const RangeT &Range)
DenseMap(const DenseMap &other)
DenseMap(const InputIt &I, const InputIt &E)
DenseMap(DenseMap &&other)
DenseMap & operator=(const DenseMap &other)
void grow(unsigned AtLeast)
SmallDenseMap(const InputIt &I, const InputIt &E)
void swap(SmallDenseMap &RHS)
SmallDenseMap & operator=(SmallDenseMap &&other)
SmallDenseMap & operator=(const SmallDenseMap &other)
SmallDenseMap(unsigned NumElementsToReserve=0)
void init(unsigned InitNumEntries)
SmallDenseMap(std::initializer_list< typename BaseT::value_type > Vals)
SmallDenseMap(SmallDenseMap &&other)
SmallDenseMap(const SmallDenseMap &other)
void copyFrom(const SmallDenseMap &other)
SmallDenseMap(llvm::from_range_t, const RangeT &Range)
A range adaptor for a pair of iterators.
constexpr char IsConst[]
Key for Kernel::Arg::Metadata::mIsConst.
These are wrappers over isa* function that allow them to be used in generic algorithms such as llvm:a...
This is an optimization pass for GlobalISel generic memory operations.
unsigned Log2_32_Ceil(uint32_t Value)
Return the ceil log base 2 of the specified value, 32 if the value is zero.
constexpr auto adl_begin(RangeT &&range) -> decltype(adl_detail::begin_impl(std::forward< RangeT >(range)))
Returns the begin iterator to range using std::begin and function found through Argument-Dependent Lo...
BitVector::size_type capacity_in_bytes(const BitVector &X)
bool operator!=(uint64_t V1, const APInt &V2)
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
constexpr bool isPowerOf2_64(uint64_t Value)
Return true if the argument is a power of two > 0 (64 bit edition.)
constexpr auto adl_end(RangeT &&range) -> decltype(adl_detail::end_impl(std::forward< RangeT >(range)))
Returns the end iterator to range using std::end and functions found through Argument-Dependent Looku...
bool operator==(const AddressRangeValuePair &LHS, const AddressRangeValuePair &RHS)
auto map_range(ContainerTy &&C, FuncTy F)
LLVM_ABI LLVM_ATTRIBUTE_RETURNS_NONNULL LLVM_ATTRIBUTE_RETURNS_NOALIAS void * allocate_buffer(size_t Size, size_t Alignment)
Allocate a buffer of memory with the given size and alignment.
auto reverse(ContainerTy &&C)
LLVM_ABI void deallocate_buffer(void *Ptr, size_t Size, size_t Alignment)
Deallocate a buffer of memory with the given size and alignment.
constexpr bool shouldReverseIterate()
LLVM_ATTRIBUTE_VISIBILITY_DEFAULT AnalysisKey InnerAnalysisManagerProxy< AnalysisManagerT, IRUnitT, ExtraArgTs... >::Key
iterator_range(Container &&) -> iterator_range< llvm::detail::IterOfRange< Container > >
@ Default
The result values are uniform if and only if all operands are uniform.
constexpr uint64_t NextPowerOf2(uint64_t A)
Returns the next power of two (in 64-bits) that is strictly greater than A.
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
A suitably aligned and sized character array member which can hold elements of any type.
std::conditional_t< std::is_pointer_v< T >, typename add_const_past_pointer< T >::type, const T & > type
const ValueT & getSecond() const
const KeyT & getFirst() const