Update prebuilt Clang to r416183b from Android.
https://android.googlesource.com/platform/prebuilts/clang/host/
linux-x86/+/06a71ddac05c22edb2d10b590e1769b3f8619bef
clang 12.0.5 (based on r416183b) from build 7284624.
Change-Id: I277a316abcf47307562d8b748b84870f31a72866
Signed-off-by: Olivier Deprez <olivier.deprez@arm.com>
diff --git a/linux-x64/clang/include/llvm/ADT/BitVector.h b/linux-x64/clang/include/llvm/ADT/BitVector.h
index fabf5d9..2a85778 100644
--- a/linux-x64/clang/include/llvm/ADT/BitVector.h
+++ b/linux-x64/clang/include/llvm/ADT/BitVector.h
@@ -14,6 +14,7 @@
#define LLVM_ADT_BITVECTOR_H
#include "llvm/ADT/ArrayRef.h"
+#include "llvm/ADT/DenseMapInfo.h"
#include "llvm/ADT/iterator_range.h"
#include "llvm/Support/MathExtras.h"
#include <algorithm>
@@ -71,7 +72,7 @@
};
class BitVector {
- typedef unsigned long BitWord;
+ typedef uintptr_t BitWord;
enum { BITWORD_SIZE = (unsigned)sizeof(BitWord) * CHAR_BIT };
@@ -187,12 +188,12 @@
/// all - Returns true if all bits are set.
bool all() const {
for (unsigned i = 0; i < Size / BITWORD_SIZE; ++i)
- if (Bits[i] != ~0UL)
+ if (Bits[i] != ~BitWord(0))
return false;
// If bits remain check that they are ones. The unused bits are always zero.
if (unsigned Remainder = Size % BITWORD_SIZE)
- return Bits[Size / BITWORD_SIZE] == (1UL << Remainder) - 1;
+ return Bits[Size / BITWORD_SIZE] == (BitWord(1) << Remainder) - 1;
return true;
}
@@ -202,9 +203,10 @@
return !any();
}
- /// find_first_in - Returns the index of the first set bit in the range
- /// [Begin, End). Returns -1 if all bits in the range are unset.
- int find_first_in(unsigned Begin, unsigned End) const {
+ /// find_first_in - Returns the index of the first set / unset bit,
+ /// depending on \p Set, in the range [Begin, End).
+ /// Returns -1 if all bits in the range are unset / set.
+ int find_first_in(unsigned Begin, unsigned End, bool Set = true) const {
assert(Begin <= End && End <= Size);
if (Begin == End)
return -1;
@@ -213,8 +215,14 @@
unsigned LastWord = (End - 1) / BITWORD_SIZE;
// Check subsequent words.
+ // The code below is based on search for the first _set_ bit. If
+ // we're searching for the first _unset_, we just take the
+ // complement of each word before we use it and apply
+ // the same method.
for (unsigned i = FirstWord; i <= LastWord; ++i) {
BitWord Copy = Bits[i];
+ if (!Set)
+ Copy = ~Copy;
if (i == FirstWord) {
unsigned FirstBit = Begin % BITWORD_SIZE;
@@ -265,32 +273,7 @@
/// find_first_unset_in - Returns the index of the first unset bit in the
/// range [Begin, End). Returns -1 if all bits in the range are set.
int find_first_unset_in(unsigned Begin, unsigned End) const {
- assert(Begin <= End && End <= Size);
- if (Begin == End)
- return -1;
-
- unsigned FirstWord = Begin / BITWORD_SIZE;
- unsigned LastWord = (End - 1) / BITWORD_SIZE;
-
- // Check subsequent words.
- for (unsigned i = FirstWord; i <= LastWord; ++i) {
- BitWord Copy = Bits[i];
-
- if (i == FirstWord) {
- unsigned FirstBit = Begin % BITWORD_SIZE;
- Copy |= maskTrailingOnes<BitWord>(FirstBit);
- }
-
- if (i == LastWord) {
- unsigned LastBit = (End - 1) % BITWORD_SIZE;
- Copy |= maskTrailingZeros<BitWord>(LastBit + 1);
- }
- if (Copy != ~0UL) {
- unsigned Result = i * BITWORD_SIZE + countTrailingOnes(Copy);
- return Result < size() ? Result : -1;
- }
- }
- return -1;
+ return find_first_in(Begin, End, /* Set = */ false);
}
/// find_last_unset_in - Returns the index of the last unset bit in the
@@ -317,7 +300,7 @@
Copy |= maskTrailingOnes<BitWord>(FirstBit);
}
- if (Copy != ~0UL) {
+ if (Copy != ~BitWord(0)) {
unsigned Result =
(CurrentWord + 1) * BITWORD_SIZE - countLeadingOnes(Copy) - 1;
return Result < Size ? Result : -1;
@@ -414,21 +397,21 @@
if (I == E) return *this;
if (I / BITWORD_SIZE == E / BITWORD_SIZE) {
- BitWord EMask = 1UL << (E % BITWORD_SIZE);
- BitWord IMask = 1UL << (I % BITWORD_SIZE);
+ BitWord EMask = BitWord(1) << (E % BITWORD_SIZE);
+ BitWord IMask = BitWord(1) << (I % BITWORD_SIZE);
BitWord Mask = EMask - IMask;
Bits[I / BITWORD_SIZE] |= Mask;
return *this;
}
- BitWord PrefixMask = ~0UL << (I % BITWORD_SIZE);
+ BitWord PrefixMask = ~BitWord(0) << (I % BITWORD_SIZE);
Bits[I / BITWORD_SIZE] |= PrefixMask;
I = alignTo(I, BITWORD_SIZE);
for (; I + BITWORD_SIZE <= E; I += BITWORD_SIZE)
- Bits[I / BITWORD_SIZE] = ~0UL;
+ Bits[I / BITWORD_SIZE] = ~BitWord(0);
- BitWord PostfixMask = (1UL << (E % BITWORD_SIZE)) - 1;
+ BitWord PostfixMask = (BitWord(1) << (E % BITWORD_SIZE)) - 1;
if (I < E)
Bits[I / BITWORD_SIZE] |= PostfixMask;
@@ -453,21 +436,21 @@
if (I == E) return *this;
if (I / BITWORD_SIZE == E / BITWORD_SIZE) {
- BitWord EMask = 1UL << (E % BITWORD_SIZE);
- BitWord IMask = 1UL << (I % BITWORD_SIZE);
+ BitWord EMask = BitWord(1) << (E % BITWORD_SIZE);
+ BitWord IMask = BitWord(1) << (I % BITWORD_SIZE);
BitWord Mask = EMask - IMask;
Bits[I / BITWORD_SIZE] &= ~Mask;
return *this;
}
- BitWord PrefixMask = ~0UL << (I % BITWORD_SIZE);
+ BitWord PrefixMask = ~BitWord(0) << (I % BITWORD_SIZE);
Bits[I / BITWORD_SIZE] &= ~PrefixMask;
I = alignTo(I, BITWORD_SIZE);
for (; I + BITWORD_SIZE <= E; I += BITWORD_SIZE)
- Bits[I / BITWORD_SIZE] = 0UL;
+ Bits[I / BITWORD_SIZE] = BitWord(0);
- BitWord PostfixMask = (1UL << (E % BITWORD_SIZE)) - 1;
+ BitWord PostfixMask = (BitWord(1) << (E % BITWORD_SIZE)) - 1;
if (I < E)
Bits[I / BITWORD_SIZE] &= ~PostfixMask;
@@ -531,24 +514,10 @@
// Comparison operators.
bool operator==(const BitVector &RHS) const {
- unsigned ThisWords = NumBitWords(size());
- unsigned RHSWords = NumBitWords(RHS.size());
- unsigned i;
- for (i = 0; i != std::min(ThisWords, RHSWords); ++i)
- if (Bits[i] != RHS.Bits[i])
- return false;
-
- // Verify that any extra words are all zeros.
- if (i != ThisWords) {
- for (; i != ThisWords; ++i)
- if (Bits[i])
- return false;
- } else if (i != RHSWords) {
- for (; i != RHSWords; ++i)
- if (RHS.Bits[i])
- return false;
- }
- return true;
+ if (size() != RHS.size())
+ return false;
+ unsigned NumWords = NumBitWords(size());
+ return Bits.take_front(NumWords) == RHS.Bits.take_front(NumWords);
}
bool operator!=(const BitVector &RHS) const {
@@ -719,6 +688,14 @@
if (this == &RHS) return *this;
Size = RHS.size();
+
+ // Handle tombstone when the BitVector is a key of a DenseHash.
+ if (RHS.isInvalid()) {
+ std::free(Bits.data());
+ Bits = None;
+ return *this;
+ }
+
unsigned RHSWords = NumBitWords(Size);
if (Size <= getBitCapacity()) {
if (Size)
@@ -758,6 +735,16 @@
std::swap(Size, RHS.Size);
}
+ void invalid() {
+ assert(!Size && Bits.empty());
+ Size = (unsigned)-1;
+ }
+ bool isInvalid() const { return Size == (unsigned)-1; }
+
+ ArrayRef<BitWord> getData() const {
+ return Bits.take_front(NumBitWords(size()));
+ }
+
//===--------------------------------------------------------------------===//
// Portable bit mask operations.
//===--------------------------------------------------------------------===//
@@ -868,7 +855,7 @@
// Then set any stray high bits of the last used word.
unsigned ExtraBits = Size % BITWORD_SIZE;
if (ExtraBits) {
- BitWord ExtraBitMask = ~0UL << ExtraBits;
+ BitWord ExtraBitMask = ~BitWord(0) << ExtraBits;
if (t)
Bits[UsedWords-1] |= ExtraBitMask;
else
@@ -932,6 +919,23 @@
return X.getMemorySize();
}
+template <> struct DenseMapInfo<BitVector> {
+ static inline BitVector getEmptyKey() { return BitVector(); }
+ static inline BitVector getTombstoneKey() {
+ BitVector V;
+ V.invalid();
+ return V;
+ }
+ static unsigned getHashValue(const BitVector &V) {
+ return DenseMapInfo<std::pair<unsigned, ArrayRef<uintptr_t>>>::getHashValue(
+ std::make_pair(V.size(), V.getData()));
+ }
+ static bool isEqual(const BitVector &LHS, const BitVector &RHS) {
+ if (LHS.isInvalid() || RHS.isInvalid())
+ return LHS.isInvalid() == RHS.isInvalid();
+ return LHS == RHS;
+ }
+};
} // end namespace llvm
namespace std {