diff options
Diffstat (limited to 'include/llvm/ADT')
39 files changed, 839 insertions, 1098 deletions
diff --git a/include/llvm/ADT/APFloat.h b/include/llvm/ADT/APFloat.h index 26aae773624c..958e3fdaea14 100644 --- a/include/llvm/ADT/APFloat.h +++ b/include/llvm/ADT/APFloat.h @@ -282,12 +282,6 @@ public: /// into FoldingSets. void Profile(FoldingSetNodeID &NID) const; - /// \brief Used by the Bitcode serializer to emit APInts to Bitcode. - void Emit(Serializer &S) const; - - /// \brief Used by the Bitcode deserializer to deserialize APInts. - static APFloat ReadVal(Deserializer &D); - /// \name Arithmetic /// @{ @@ -349,7 +343,7 @@ public: /// copied from some other APFloat. static APFloat copySign(APFloat Value, const APFloat &Sign) { Value.copySign(Sign); - return std::move(Value); + return Value; } /// @} @@ -376,7 +370,7 @@ public: /// The definition of equality is not straightforward for floating point, so /// we won't use operator==. Use one of the following, or write whatever it /// is you really mean. - bool operator==(const APFloat &) const LLVM_DELETED_FUNCTION; + bool operator==(const APFloat &) const = delete; /// IEEE comparison with another floating point number (NaNs compare /// unordered, 0==-0). diff --git a/include/llvm/ADT/APInt.h b/include/llvm/ADT/APInt.h index 025397d9ce45..36d8159d21ba 100644 --- a/include/llvm/ADT/APInt.h +++ b/include/llvm/ADT/APInt.h @@ -25,9 +25,7 @@ #include <string> namespace llvm { -class Deserializer; class FoldingSetNodeID; -class Serializer; class StringRef; class hash_code; class raw_ostream; @@ -409,6 +407,13 @@ public: : getZExtValue(); } + /// \brief Check if the APInt consists of a repeated bit pattern. + /// + /// e.g. 0x01010101 satisfies isSplat(8). + /// \param SplatSizeInBits The size of the pattern in bits. Must divide bit + /// width without remainder. + bool isSplat(unsigned SplatSizeInBits) const; + /// @} /// \name Value Generators /// @{ @@ -1356,7 +1361,7 @@ public: /// \brief Count the number of leading one bits. /// - /// This function is an APInt version of the countLeadingOnes_{32,64} + /// This function is an APInt version of the countLeadingOnes /// functions in MathExtras.h. It counts the number of ones from the most /// significant bit to the first zero bit. /// @@ -1372,7 +1377,7 @@ public: /// \brief Count the number of trailing zero bits. /// - /// This function is an APInt version of the countTrailingZeros_{32,64} + /// This function is an APInt version of the countTrailingZeros /// functions in MathExtras.h. It counts the number of zeros from the least /// significant bit to the first set bit. /// @@ -1382,7 +1387,7 @@ public: /// \brief Count the number of trailing one bits. /// - /// This function is an APInt version of the countTrailingOnes_{32,64} + /// This function is an APInt version of the countTrailingOnes /// functions in MathExtras.h. It counts the number of ones from the least /// significant bit to the first zero bit. /// @@ -1390,19 +1395,19 @@ public: /// of ones from the least significant bit to the first zero bit. unsigned countTrailingOnes() const { if (isSingleWord()) - return CountTrailingOnes_64(VAL); + return llvm::countTrailingOnes(VAL); return countTrailingOnesSlowCase(); } /// \brief Count the number of bits set. /// - /// This function is an APInt version of the countPopulation_{32,64} functions + /// This function is an APInt version of the countPopulation functions /// in MathExtras.h. It counts the number of 1 bits in the APInt value. /// /// \returns 0 if the value is zero, otherwise returns the number of set bits. unsigned countPopulation() const { if (isSingleWord()) - return CountPopulation_64(VAL); + return llvm::countPopulation(VAL); return countPopulationSlowCase(); } diff --git a/include/llvm/ADT/APSInt.h b/include/llvm/ADT/APSInt.h index a6693f7992cd..91ccda22f2f0 100644 --- a/include/llvm/ADT/APSInt.h +++ b/include/llvm/ADT/APSInt.h @@ -62,6 +62,12 @@ public: } using APInt::toString; + /// \brief Get the correctly-extended \c int64_t value. + int64_t getExtValue() const { + assert(getMinSignedBits() <= 64 && "Too many bits for int64_t"); + return isSigned() ? getSExtValue() : getZExtValue(); + } + APSInt LLVM_ATTRIBUTE_UNUSED_RESULT trunc(uint32_t width) const { return APSInt(APInt::trunc(width), IsUnsigned); } @@ -133,14 +139,27 @@ public: assert(IsUnsigned == RHS.IsUnsigned && "Signedness mismatch!"); return eq(RHS); } - inline bool operator==(int64_t RHS) const { - return isSameValue(*this, APSInt(APInt(64, RHS), true)); - } inline bool operator!=(const APSInt& RHS) const { return !((*this) == RHS); } - inline bool operator!=(int64_t RHS) const { - return !((*this) == RHS); + + bool operator==(int64_t RHS) const { + return compareValues(*this, get(RHS)) == 0; + } + bool operator!=(int64_t RHS) const { + return compareValues(*this, get(RHS)) != 0; + } + bool operator<=(int64_t RHS) const { + return compareValues(*this, get(RHS)) <= 0; + } + bool operator>=(int64_t RHS) const { + return compareValues(*this, get(RHS)) >= 0; + } + bool operator<(int64_t RHS) const { + return compareValues(*this, get(RHS)) < 0; + } + bool operator>(int64_t RHS) const { + return compareValues(*this, get(RHS)) > 0; } // The remaining operators just wrap the logic of APInt, but retain the @@ -260,37 +279,49 @@ public: /// \brief Determine if two APSInts have the same value, zero- or /// sign-extending as needed. static bool isSameValue(const APSInt &I1, const APSInt &I2) { + return !compareValues(I1, I2); + } + + /// \brief Compare underlying values of two numbers. + static int compareValues(const APSInt &I1, const APSInt &I2) { if (I1.getBitWidth() == I2.getBitWidth() && I1.isSigned() == I2.isSigned()) - return I1 == I2; + return I1 == I2 ? 0 : I1 > I2 ? 1 : -1; // Check for a bit-width mismatch. if (I1.getBitWidth() > I2.getBitWidth()) - return isSameValue(I1, I2.extend(I1.getBitWidth())); + return compareValues(I1, I2.extend(I1.getBitWidth())); else if (I2.getBitWidth() > I1.getBitWidth()) - return isSameValue(I1.extend(I2.getBitWidth()), I2); - - assert(I1.isSigned() != I2.isSigned()); + return compareValues(I1.extend(I2.getBitWidth()), I2); // We have a signedness mismatch. Check for negative values and do an - // unsigned compare if signs match. - if ((I1.isSigned() && I1.isNegative()) || - (!I1.isSigned() && I2.isNegative())) - return false; + // unsigned compare if both are positive. + if (I1.isSigned()) { + assert(!I2.isSigned() && "Expected signed mismatch"); + if (I1.isNegative()) + return -1; + } else { + assert(I2.isSigned() && "Expected signed mismatch"); + if (I2.isNegative()) + return 1; + } - return I1.eq(I2); + return I1.eq(I2) ? 0 : I1.ugt(I2) ? 1 : -1; } + static APSInt get(int64_t X) { return APSInt(APInt(64, X), false); } + static APSInt getUnsigned(uint64_t X) { return APSInt(APInt(64, X), true); } + /// Profile - Used to insert APSInt objects, or objects that contain APSInt /// objects, into FoldingSets. void Profile(FoldingSetNodeID& ID) const; }; -inline bool operator==(int64_t V1, const APSInt& V2) { - return V2 == V1; -} -inline bool operator!=(int64_t V1, const APSInt& V2) { - return V2 != V1; -} +inline bool operator==(int64_t V1, const APSInt &V2) { return V2 == V1; } +inline bool operator!=(int64_t V1, const APSInt &V2) { return V2 != V1; } +inline bool operator<=(int64_t V1, const APSInt &V2) { return V2 >= V1; } +inline bool operator>=(int64_t V1, const APSInt &V2) { return V2 <= V1; } +inline bool operator<(int64_t V1, const APSInt &V2) { return V2 > V1; } +inline bool operator>(int64_t V1, const APSInt &V2) { return V2 < V1; } inline raw_ostream &operator<<(raw_ostream &OS, const APSInt &I) { I.print(OS, I.isSigned()); diff --git a/include/llvm/ADT/ArrayRef.h b/include/llvm/ADT/ArrayRef.h index 8c14a423c8f5..1b2bdffc8335 100644 --- a/include/llvm/ADT/ArrayRef.h +++ b/include/llvm/ADT/ArrayRef.h @@ -11,7 +11,6 @@ #define LLVM_ADT_ARRAYREF_H #include "llvm/ADT/None.h" -#include "llvm/ADT/STLExtras.h" #include "llvm/ADT/SmallVector.h" #include <vector> @@ -44,19 +43,6 @@ namespace llvm { /// The number of elements. size_type Length; - /// \brief A dummy "optional" type that is only created by implicit - /// conversion from a reference to T. - /// - /// This type must *only* be used in a function argument or as a copy of - /// a function argument, as otherwise it will hold a pointer to a temporary - /// past that temporaries' lifetime. - struct TRefOrNothing { - const T *TPtr; - - TRefOrNothing() : TPtr(nullptr) {} - TRefOrNothing(const T &TRef) : TPtr(&TRef) {} - }; - public: /// @name Constructors /// @{ @@ -97,12 +83,10 @@ namespace llvm { /*implicit*/ LLVM_CONSTEXPR ArrayRef(const T (&Arr)[N]) : Data(Arr), Length(N) {} -#if LLVM_HAS_INITIALIZER_LISTS /// Construct an ArrayRef from a std::initializer_list. /*implicit*/ ArrayRef(const std::initializer_list<T> &Vec) : Data(Vec.begin() == Vec.end() ? (T*)0 : Vec.begin()), Length(Vec.size()) {} -#endif /// Construct an ArrayRef<const T*> from ArrayRef<T*>. This uses SFINAE to /// ensure that only ArrayRefs of pointers can be converted. @@ -112,6 +96,25 @@ namespace llvm { std::is_convertible<U *const *, T const *>::value>::type* = 0) : Data(A.data()), Length(A.size()) {} + /// Construct an ArrayRef<const T*> from a SmallVector<T*>. This is + /// templated in order to avoid instantiating SmallVectorTemplateCommon<T> + /// whenever we copy-construct an ArrayRef. + template<typename U, typename DummyT> + /*implicit*/ ArrayRef(const SmallVectorTemplateCommon<U*, DummyT> &Vec, + typename std::enable_if< + std::is_convertible<U *const *, + T const *>::value>::type* = 0) + : Data(Vec.data()), Length(Vec.size()) { + } + + /// Construct an ArrayRef<const T*> from std::vector<T*>. This uses SFINAE + /// to ensure that only vectors of pointers can be converted. + template<typename U, typename A> + ArrayRef(const std::vector<U *, A> &Vec, + typename std::enable_if< + std::is_convertible<U *const *, T const *>::value>::type* = 0) + : Data(Vec.data()), Length(Vec.size()) {} + /// @} /// @name Simple Operations /// @{ @@ -153,13 +156,9 @@ namespace llvm { bool equals(ArrayRef RHS) const { if (Length != RHS.Length) return false; - // Don't use std::equal(), since it asserts in MSVC on nullptr iterators. - for (auto L = begin(), LE = end(), R = RHS.begin(); L != LE; ++L, ++R) - // Match std::equal() in using == (instead of !=) to minimize API - // requirements of ArrayRef'ed types. - if (!(*L == *R)) - return false; - return true; + if (Length == 0) + return true; + return std::equal(begin(), end(), RHS.begin()); } /// slice(n) - Chop off the first N elements of the array. @@ -204,47 +203,6 @@ namespace llvm { } /// @} - /// @{ - /// @name Convenience methods - - /// @brief Predicate for testing that the array equals the exact sequence of - /// arguments. - /// - /// Will return false if the size is not equal to the exact number of - /// arguments given or if the array elements don't equal the argument - /// elements in order. Currently supports up to 16 arguments, but can - /// easily be extended. - bool equals(TRefOrNothing Arg0 = TRefOrNothing(), - TRefOrNothing Arg1 = TRefOrNothing(), - TRefOrNothing Arg2 = TRefOrNothing(), - TRefOrNothing Arg3 = TRefOrNothing(), - TRefOrNothing Arg4 = TRefOrNothing(), - TRefOrNothing Arg5 = TRefOrNothing(), - TRefOrNothing Arg6 = TRefOrNothing(), - TRefOrNothing Arg7 = TRefOrNothing(), - TRefOrNothing Arg8 = TRefOrNothing(), - TRefOrNothing Arg9 = TRefOrNothing(), - TRefOrNothing Arg10 = TRefOrNothing(), - TRefOrNothing Arg11 = TRefOrNothing(), - TRefOrNothing Arg12 = TRefOrNothing(), - TRefOrNothing Arg13 = TRefOrNothing(), - TRefOrNothing Arg14 = TRefOrNothing(), - TRefOrNothing Arg15 = TRefOrNothing()) { - TRefOrNothing Args[] = {Arg0, Arg1, Arg2, Arg3, Arg4, Arg5, - Arg6, Arg7, Arg8, Arg9, Arg10, Arg11, - Arg12, Arg13, Arg14, Arg15}; - if (size() > array_lengthof(Args)) - return false; - - for (unsigned i = 0, e = size(); i != e; ++i) - if (Args[i].TPtr == nullptr || (*this)[i] != *Args[i].TPtr) - return false; - - // Either the size is exactly as many args, or the next arg must be null. - return size() == array_lengthof(Args) || Args[size()].TPtr == nullptr; - } - - /// @} }; /// MutableArrayRef - Represent a mutable reference to an array (0 or more diff --git a/include/llvm/ADT/BitVector.h b/include/llvm/ADT/BitVector.h index a40f694485bf..f58dd7356c7d 100644 --- a/include/llvm/ADT/BitVector.h +++ b/include/llvm/ADT/BitVector.h @@ -29,6 +29,9 @@ class BitVector { enum { BITWORD_SIZE = (unsigned)sizeof(BitWord) * CHAR_BIT }; + static_assert(BITWORD_SIZE == 64 || BITWORD_SIZE == 32, + "Unsupported word size"); + BitWord *Bits; // Actual bits. unsigned Size; // Size of bitvector in bits. unsigned Capacity; // Size of allocated memory in BitWord. @@ -50,7 +53,7 @@ public: BitPos = Idx % BITWORD_SIZE; } - ~reference() {} + reference(const reference&) = default; reference &operator=(reference t) { *this = bool(t); @@ -118,12 +121,7 @@ public: size_type count() const { unsigned NumBits = 0; for (unsigned i = 0; i < NumBitWords(size()); ++i) - if (sizeof(BitWord) == 4) - NumBits += CountPopulation_32((uint32_t)Bits[i]); - else if (sizeof(BitWord) == 8) - NumBits += CountPopulation_64(Bits[i]); - else - llvm_unreachable("Unsupported!"); + NumBits += countPopulation(Bits[i]); return NumBits; } @@ -157,13 +155,8 @@ public: /// of the bits are set. int find_first() const { for (unsigned i = 0; i < NumBitWords(size()); ++i) - if (Bits[i] != 0) { - if (sizeof(BitWord) == 4) - return i * BITWORD_SIZE + countTrailingZeros((uint32_t)Bits[i]); - if (sizeof(BitWord) == 8) - return i * BITWORD_SIZE + countTrailingZeros(Bits[i]); - llvm_unreachable("Unsupported!"); - } + if (Bits[i] != 0) + return i * BITWORD_SIZE + countTrailingZeros(Bits[i]); return -1; } @@ -180,23 +173,13 @@ public: // Mask off previous bits. Copy &= ~0UL << BitPos; - if (Copy != 0) { - if (sizeof(BitWord) == 4) - return WordPos * BITWORD_SIZE + countTrailingZeros((uint32_t)Copy); - if (sizeof(BitWord) == 8) - return WordPos * BITWORD_SIZE + countTrailingZeros(Copy); - llvm_unreachable("Unsupported!"); - } + if (Copy != 0) + return WordPos * BITWORD_SIZE + countTrailingZeros(Copy); // Check subsequent words. for (unsigned i = WordPos+1; i < NumBitWords(size()); ++i) - if (Bits[i] != 0) { - if (sizeof(BitWord) == 4) - return i * BITWORD_SIZE + countTrailingZeros((uint32_t)Bits[i]); - if (sizeof(BitWord) == 8) - return i * BITWORD_SIZE + countTrailingZeros(Bits[i]); - llvm_unreachable("Unsupported!"); - } + if (Bits[i] != 0) + return i * BITWORD_SIZE + countTrailingZeros(Bits[i]); return -1; } @@ -559,7 +542,7 @@ private: template<bool AddBits, bool InvertMask> void applyMask(const uint32_t *Mask, unsigned MaskWords) { - assert(BITWORD_SIZE % 32 == 0 && "Unsupported BitWord size."); + static_assert(BITWORD_SIZE % 32 == 0, "Unsupported BitWord size."); MaskWords = std::min(MaskWords, (size() + 31) / 32); const unsigned Scale = BITWORD_SIZE / 32; unsigned i; diff --git a/include/llvm/ADT/DeltaAlgorithm.h b/include/llvm/ADT/DeltaAlgorithm.h index 4d07e044781f..21bc1e80c9d8 100644 --- a/include/llvm/ADT/DeltaAlgorithm.h +++ b/include/llvm/ADT/DeltaAlgorithm.h @@ -77,6 +77,8 @@ protected: /// ExecuteOneTest - Execute a single test predicate on the change set \p S. virtual bool ExecuteOneTest(const changeset_ty &S) = 0; + DeltaAlgorithm& operator=(const DeltaAlgorithm&) = default; + public: virtual ~DeltaAlgorithm(); diff --git a/include/llvm/ADT/DenseMap.h b/include/llvm/ADT/DenseMap.h index 050f8ac150dd..27f73157a29f 100644 --- a/include/llvm/ADT/DenseMap.h +++ b/include/llvm/ADT/DenseMap.h @@ -15,6 +15,7 @@ #define LLVM_ADT_DENSEMAP_H #include "llvm/ADT/DenseMapInfo.h" +#include "llvm/ADT/EpochTracker.h" #include "llvm/Support/AlignOf.h" #include "llvm/Support/Compiler.h" #include "llvm/Support/MathExtras.h" @@ -50,7 +51,7 @@ class DenseMapIterator; template <typename DerivedT, typename KeyT, typename ValueT, typename KeyInfoT, typename BucketT> -class DenseMapBase { +class DenseMapBase : public DebugEpochBase { public: typedef unsigned size_type; typedef KeyT key_type; @@ -62,16 +63,17 @@ public: const_iterator; inline iterator begin() { // When the map is empty, avoid the overhead of AdvancePastEmptyBuckets(). - return empty() ? end() : iterator(getBuckets(), getBucketsEnd()); + return empty() ? end() : iterator(getBuckets(), getBucketsEnd(), *this); } inline iterator end() { - return iterator(getBucketsEnd(), getBucketsEnd(), true); + return iterator(getBucketsEnd(), getBucketsEnd(), *this, true); } inline const_iterator begin() const { - return empty() ? end() : const_iterator(getBuckets(), getBucketsEnd()); + return empty() ? end() + : const_iterator(getBuckets(), getBucketsEnd(), *this); } inline const_iterator end() const { - return const_iterator(getBucketsEnd(), getBucketsEnd(), true); + return const_iterator(getBucketsEnd(), getBucketsEnd(), *this, true); } bool LLVM_ATTRIBUTE_UNUSED_RESULT empty() const { @@ -81,11 +83,13 @@ public: /// Grow the densemap so that it has at least Size buckets. Does not shrink void resize(size_type Size) { + incrementEpoch(); if (Size > getNumBuckets()) grow(Size); } void clear() { + incrementEpoch(); if (getNumEntries() == 0 && getNumTombstones() == 0) return; // If the capacity of the array is huge, and the # elements used is small, @@ -96,16 +100,18 @@ public: } const KeyT EmptyKey = getEmptyKey(), TombstoneKey = getTombstoneKey(); + unsigned NumEntries = getNumEntries(); for (BucketT *P = getBuckets(), *E = getBucketsEnd(); P != E; ++P) { if (!KeyInfoT::isEqual(P->getFirst(), EmptyKey)) { if (!KeyInfoT::isEqual(P->getFirst(), TombstoneKey)) { P->getSecond().~ValueT(); - decrementNumEntries(); + --NumEntries; } P->getFirst() = EmptyKey; } } - assert(getNumEntries() == 0 && "Node count imbalance!"); + assert(NumEntries == 0 && "Node count imbalance!"); + setNumEntries(0); setNumTombstones(0); } @@ -118,13 +124,13 @@ public: iterator find(const KeyT &Val) { BucketT *TheBucket; if (LookupBucketFor(Val, TheBucket)) - return iterator(TheBucket, getBucketsEnd(), true); + return iterator(TheBucket, getBucketsEnd(), *this, true); return end(); } const_iterator find(const KeyT &Val) const { const BucketT *TheBucket; if (LookupBucketFor(Val, TheBucket)) - return const_iterator(TheBucket, getBucketsEnd(), true); + return const_iterator(TheBucket, getBucketsEnd(), *this, true); return end(); } @@ -137,14 +143,14 @@ public: iterator find_as(const LookupKeyT &Val) { BucketT *TheBucket; if (LookupBucketFor(Val, TheBucket)) - return iterator(TheBucket, getBucketsEnd(), true); + return iterator(TheBucket, getBucketsEnd(), *this, true); return end(); } template<class LookupKeyT> const_iterator find_as(const LookupKeyT &Val) const { const BucketT *TheBucket; if (LookupBucketFor(Val, TheBucket)) - return const_iterator(TheBucket, getBucketsEnd(), true); + return const_iterator(TheBucket, getBucketsEnd(), *this, true); return end(); } @@ -163,12 +169,13 @@ public: std::pair<iterator, bool> insert(const std::pair<KeyT, ValueT> &KV) { BucketT *TheBucket; if (LookupBucketFor(KV.first, TheBucket)) - return std::make_pair(iterator(TheBucket, getBucketsEnd(), true), + return std::make_pair(iterator(TheBucket, getBucketsEnd(), *this, true), false); // Already in map. // Otherwise, insert the new element. TheBucket = InsertIntoBucket(KV.first, KV.second, TheBucket); - return std::make_pair(iterator(TheBucket, getBucketsEnd(), true), true); + return std::make_pair(iterator(TheBucket, getBucketsEnd(), *this, true), + true); } // Inserts key,value pair into the map if the key isn't already in the map. @@ -177,14 +184,15 @@ public: std::pair<iterator, bool> insert(std::pair<KeyT, ValueT> &&KV) { BucketT *TheBucket; if (LookupBucketFor(KV.first, TheBucket)) - return std::make_pair(iterator(TheBucket, getBucketsEnd(), true), + return std::make_pair(iterator(TheBucket, getBucketsEnd(), *this, true), false); // Already in map. - + // Otherwise, insert the new element. TheBucket = InsertIntoBucket(std::move(KV.first), std::move(KV.second), TheBucket); - return std::make_pair(iterator(TheBucket, getBucketsEnd(), true), true); + return std::make_pair(iterator(TheBucket, getBucketsEnd(), *this, true), + true); } /// insert - Range insertion of pairs. @@ -251,7 +259,7 @@ public: const void *getPointerIntoBucketsArray() const { return getBuckets(); } protected: - DenseMapBase() {} + DenseMapBase() = default; void destroyAll() { if (getNumBuckets() == 0) // Nothing to do. @@ -264,10 +272,6 @@ protected: P->getSecond().~ValueT(); P->getFirst().~KeyT(); } - -#ifndef NDEBUG - memset((void*)getBuckets(), 0x5a, sizeof(BucketT)*getNumBuckets()); -#endif } void initEmpty() { @@ -304,12 +308,6 @@ protected: } B->getFirst().~KeyT(); } - -#ifndef NDEBUG - if (OldBucketsBegin != OldBucketsEnd) - memset((void*)OldBucketsBegin, 0x5a, - sizeof(BucketT) * (OldBucketsEnd - OldBucketsBegin)); -#endif } template <typename OtherBaseT> @@ -335,11 +333,6 @@ protected: } } - void swap(DenseMapBase& RHS) { - std::swap(getNumEntries(), RHS.getNumEntries()); - std::swap(getNumTombstones(), RHS.getNumTombstones()); - } - static unsigned getHashValue(const KeyT &Val) { return KeyInfoT::getHashValue(Val); } @@ -431,6 +424,8 @@ private: } BucketT *InsertIntoBucketImpl(const KeyT &Key, BucketT *TheBucket) { + incrementEpoch(); + // If the load of the hash table is more than 3/4, or if fewer than 1/8 of // the buckets are empty (meaning that many are filled with tombstones), // grow the table. @@ -442,11 +437,12 @@ private: // causing infinite loops in lookup. unsigned NewNumEntries = getNumEntries() + 1; unsigned NumBuckets = getNumBuckets(); - if (NewNumEntries*4 >= NumBuckets*3) { + if (LLVM_UNLIKELY(NewNumEntries * 4 >= NumBuckets * 3)) { this->grow(NumBuckets * 2); LookupBucketFor(Key, TheBucket); NumBuckets = getNumBuckets(); - } else if (NumBuckets-(NewNumEntries+getNumTombstones()) <= NumBuckets/8) { + } else if (LLVM_UNLIKELY(NumBuckets-(NewNumEntries+getNumTombstones()) <= + NumBuckets/8)) { this->grow(NumBuckets); LookupBucketFor(Key, TheBucket); } @@ -492,14 +488,14 @@ private: while (1) { const BucketT *ThisBucket = BucketsPtr + BucketNo; // Found Val's bucket? If so, return it. - if (KeyInfoT::isEqual(Val, ThisBucket->getFirst())) { + if (LLVM_LIKELY(KeyInfoT::isEqual(Val, ThisBucket->getFirst()))) { FoundBucket = ThisBucket; return true; } // If we found an empty bucket, the key doesn't exist in the set. // Insert it and return the default value. - if (KeyInfoT::isEqual(ThisBucket->getFirst(), EmptyKey)) { + if (LLVM_LIKELY(KeyInfoT::isEqual(ThisBucket->getFirst(), EmptyKey))) { // If we've already seen a tombstone while probing, fill it in instead // of the empty bucket we eventually probed to. FoundBucket = FoundTombstone ? FoundTombstone : ThisBucket; @@ -580,6 +576,8 @@ public: } void swap(DenseMap& RHS) { + this->incrementEpoch(); + RHS.incrementEpoch(); std::swap(Buckets, RHS.Buckets); std::swap(NumEntries, RHS.NumEntries); std::swap(NumTombstones, RHS.NumTombstones); @@ -986,9 +984,10 @@ private: template <typename KeyT, typename ValueT, typename KeyInfoT, typename Bucket, bool IsConst> -class DenseMapIterator { +class DenseMapIterator : DebugEpochBase::HandleBase { typedef DenseMapIterator<KeyT, ValueT, KeyInfoT, Bucket, true> ConstIterator; friend class DenseMapIterator<KeyT, ValueT, KeyInfoT, Bucket, true>; + friend class DenseMapIterator<KeyT, ValueT, KeyInfoT, Bucket, false>; public: typedef ptrdiff_t difference_type; @@ -1002,38 +1001,54 @@ private: public: DenseMapIterator() : Ptr(nullptr), End(nullptr) {} - DenseMapIterator(pointer Pos, pointer E, bool NoAdvance = false) - : Ptr(Pos), End(E) { + DenseMapIterator(pointer Pos, pointer E, const DebugEpochBase &Epoch, + bool NoAdvance = false) + : DebugEpochBase::HandleBase(&Epoch), Ptr(Pos), End(E) { + assert(isHandleInSync() && "invalid construction!"); if (!NoAdvance) AdvancePastEmptyBuckets(); } - // If IsConst is true this is a converting constructor from iterator to - // const_iterator and the default copy constructor is used. - // Otherwise this is a copy constructor for iterator. + // Converting ctor from non-const iterators to const iterators. SFINAE'd out + // for const iterator destinations so it doesn't end up as a user defined copy + // constructor. + template <bool IsConstSrc, + typename = typename std::enable_if<!IsConstSrc && IsConst>::type> DenseMapIterator( - const DenseMapIterator<KeyT, ValueT, KeyInfoT, Bucket, false> &I) - : Ptr(I.Ptr), End(I.End) {} + const DenseMapIterator<KeyT, ValueT, KeyInfoT, Bucket, IsConstSrc> &I) + : DebugEpochBase::HandleBase(I), Ptr(I.Ptr), End(I.End) {} reference operator*() const { + assert(isHandleInSync() && "invalid iterator access!"); return *Ptr; } pointer operator->() const { + assert(isHandleInSync() && "invalid iterator access!"); return Ptr; } bool operator==(const ConstIterator &RHS) const { - return Ptr == RHS.operator->(); + assert((!Ptr || isHandleInSync()) && "handle not in sync!"); + assert((!RHS.Ptr || RHS.isHandleInSync()) && "handle not in sync!"); + assert(getEpochAddress() == RHS.getEpochAddress() && + "comparing incomparable iterators!"); + return Ptr == RHS.Ptr; } bool operator!=(const ConstIterator &RHS) const { - return Ptr != RHS.operator->(); + assert((!Ptr || isHandleInSync()) && "handle not in sync!"); + assert((!RHS.Ptr || RHS.isHandleInSync()) && "handle not in sync!"); + assert(getEpochAddress() == RHS.getEpochAddress() && + "comparing incomparable iterators!"); + return Ptr != RHS.Ptr; } inline DenseMapIterator& operator++() { // Preincrement + assert(isHandleInSync() && "invalid iterator access!"); ++Ptr; AdvancePastEmptyBuckets(); return *this; } DenseMapIterator operator++(int) { // Postincrement + assert(isHandleInSync() && "invalid iterator access!"); DenseMapIterator tmp = *this; ++*this; return tmp; } diff --git a/include/llvm/ADT/DepthFirstIterator.h b/include/llvm/ADT/DepthFirstIterator.h index 6cd9e68aea56..d79b9acacfa9 100644 --- a/include/llvm/ADT/DepthFirstIterator.h +++ b/include/llvm/ADT/DepthFirstIterator.h @@ -113,9 +113,8 @@ private: while (It != GT::child_end(Node)) { NodeType *Next = *It++; // Has our next sibling been visited? - if (Next && !this->Visited.count(Next)) { + if (Next && this->Visited.insert(Next).second) { // No, do it now. - this->Visited.insert(Next); VisitStack.push_back(std::make_pair(PointerIntTy(Next, 0), GT::child_begin(Next))); return; @@ -129,58 +128,59 @@ private: public: typedef typename super::pointer pointer; - typedef df_iterator<GraphT, SetType, ExtStorage, GT> _Self; // Provide static begin and end methods as our public "constructors" - static inline _Self begin(const GraphT& G) { - return _Self(GT::getEntryNode(G)); + static df_iterator begin(const GraphT &G) { + return df_iterator(GT::getEntryNode(G)); } - static inline _Self end(const GraphT& G) { return _Self(); } + static df_iterator end(const GraphT &G) { return df_iterator(); } // Static begin and end methods as our public ctors for external iterators - static inline _Self begin(const GraphT& G, SetType &S) { - return _Self(GT::getEntryNode(G), S); + static df_iterator begin(const GraphT &G, SetType &S) { + return df_iterator(GT::getEntryNode(G), S); } - static inline _Self end(const GraphT& G, SetType &S) { return _Self(S); } + static df_iterator end(const GraphT &G, SetType &S) { return df_iterator(S); } - inline bool operator==(const _Self& x) const { + bool operator==(const df_iterator &x) const { return VisitStack == x.VisitStack; } - inline bool operator!=(const _Self& x) const { return !operator==(x); } + bool operator!=(const df_iterator &x) const { return !(*this == x); } - inline pointer operator*() const { - return VisitStack.back().first.getPointer(); - } + pointer operator*() const { return VisitStack.back().first.getPointer(); } // This is a nonstandard operator-> that dereferences the pointer an extra // time... so that you can actually call methods ON the Node, because // the contained type is a pointer. This allows BBIt->getTerminator() f.e. // - inline NodeType *operator->() const { return operator*(); } + NodeType *operator->() const { return **this; } - inline _Self& operator++() { // Preincrement + df_iterator &operator++() { // Preincrement toNext(); return *this; } - // skips all children of the current node and traverses to next node - // - inline _Self& skipChildren() { + /// \brief Skips all children of the current node and traverses to next node + /// + /// Note: This function takes care of incrementing the iterator. If you + /// always increment and call this function, you risk walking off the end. + df_iterator &skipChildren() { VisitStack.pop_back(); if (!VisitStack.empty()) toNext(); return *this; } - inline _Self operator++(int) { // Postincrement - _Self tmp = *this; ++*this; return tmp; + df_iterator operator++(int) { // Postincrement + df_iterator tmp = *this; + ++*this; + return tmp; } // nodeVisited - return true if this iterator has already visited the // specified node. This is public, and will probably be used to iterate over // nodes that a depth first iteration did not find: ie unreachable nodes. // - inline bool nodeVisited(NodeType *Node) const { + bool nodeVisited(NodeType *Node) const { return this->Visited.count(Node) != 0; } @@ -211,7 +211,7 @@ df_iterator<T> df_end(const T& G) { // Provide an accessor method to use them in range-based patterns. template <class T> iterator_range<df_iterator<T>> depth_first(const T& G) { - return iterator_range<df_iterator<T>>(df_begin(G), df_end(G)); + return make_range(df_begin(G), df_end(G)); } // Provide global definitions of external depth first iterators... @@ -234,8 +234,7 @@ df_ext_iterator<T, SetTy> df_ext_end(const T& G, SetTy &S) { template <class T, class SetTy> iterator_range<df_ext_iterator<T, SetTy>> depth_first_ext(const T& G, SetTy &S) { - return iterator_range<df_ext_iterator<T, SetTy>>(df_ext_begin(G, S), - df_ext_end(G, S)); + return make_range(df_ext_begin(G, S), df_ext_end(G, S)); } @@ -261,7 +260,7 @@ idf_iterator<T> idf_end(const T& G){ // Provide an accessor method to use them in range-based patterns. template <class T> iterator_range<idf_iterator<T>> inverse_depth_first(const T& G) { - return iterator_range<idf_iterator<T>>(idf_begin(G), idf_end(G)); + return make_range(idf_begin(G), idf_end(G)); } // Provide global definitions of external inverse depth first iterators... @@ -286,8 +285,7 @@ idf_ext_iterator<T, SetTy> idf_ext_end(const T& G, SetTy &S) { template <class T, class SetTy> iterator_range<idf_ext_iterator<T, SetTy>> inverse_depth_first_ext(const T& G, SetTy &S) { - return iterator_range<idf_ext_iterator<T, SetTy>>(idf_ext_begin(G, S), - idf_ext_end(G, S)); + return make_range(idf_ext_begin(G, S), idf_ext_end(G, S)); } } // End llvm namespace diff --git a/include/llvm/ADT/EpochTracker.h b/include/llvm/ADT/EpochTracker.h new file mode 100644 index 000000000000..582d58179d13 --- /dev/null +++ b/include/llvm/ADT/EpochTracker.h @@ -0,0 +1,99 @@ +//===- llvm/ADT/EpochTracker.h - ADT epoch tracking --------------*- C++ -*-==// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file defines the DebugEpochBase and DebugEpochBase::HandleBase classes. +// These can be used to write iterators that are fail-fast when LLVM is built +// with asserts enabled. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_ADT_EPOCH_TRACKER_H +#define LLVM_ADT_EPOCH_TRACKER_H + +#include "llvm/Config/llvm-config.h" + +#include <cstdint> + +namespace llvm { + +#ifndef LLVM_ENABLE_ABI_BREAKING_CHECKS + +class DebugEpochBase { +public: + void incrementEpoch() {} + + class HandleBase { + public: + HandleBase() = default; + explicit HandleBase(const DebugEpochBase *) {} + bool isHandleInSync() const { return true; } + const void *getEpochAddress() const { return nullptr; } + }; +}; + +#else + +/// \brief A base class for data structure classes wishing to make iterators +/// ("handles") pointing into themselves fail-fast. When building without +/// asserts, this class is empty and does nothing. +/// +/// DebugEpochBase does not by itself track handles pointing into itself. The +/// expectation is that routines touching the handles will poll on +/// isHandleInSync at appropriate points to assert that the handle they're using +/// is still valid. +/// +class DebugEpochBase { + uint64_t Epoch; + +public: + DebugEpochBase() : Epoch(0) {} + + /// \brief Calling incrementEpoch invalidates all handles pointing into the + /// calling instance. + void incrementEpoch() { ++Epoch; } + + /// \brief The destructor calls incrementEpoch to make use-after-free bugs + /// more likely to crash deterministically. + ~DebugEpochBase() { incrementEpoch(); } + + /// \brief A base class for iterator classes ("handles") that wish to poll for + /// iterator invalidating modifications in the underlying data structure. + /// When LLVM is built without asserts, this class is empty and does nothing. + /// + /// HandleBase does not track the parent data structure by itself. It expects + /// the routines modifying the data structure to call incrementEpoch when they + /// make an iterator-invalidating modification. + /// + class HandleBase { + const uint64_t *EpochAddress; + uint64_t EpochAtCreation; + + public: + HandleBase() : EpochAddress(nullptr), EpochAtCreation(UINT64_MAX) {} + + explicit HandleBase(const DebugEpochBase *Parent) + : EpochAddress(&Parent->Epoch), EpochAtCreation(Parent->Epoch) {} + + /// \brief Returns true if the DebugEpochBase this Handle is linked to has + /// not called incrementEpoch on itself since the creation of this + /// HandleBase instance. + bool isHandleInSync() const { return *EpochAddress == EpochAtCreation; } + + /// \brief Returns a pointer to the epoch word stored in the data structure + /// this handle points into. Can be used to check if two iterators point + /// into the same data structure. + const void *getEpochAddress() const { return EpochAddress; } + }; +}; + +#endif // LLVM_ENABLE_ABI_BREAKING_CHECKS + +} // namespace llvm + +#endif diff --git a/include/llvm/ADT/EquivalenceClasses.h b/include/llvm/ADT/EquivalenceClasses.h index e0396c7e7914..d6a26f88e67d 100644 --- a/include/llvm/ADT/EquivalenceClasses.h +++ b/include/llvm/ADT/EquivalenceClasses.h @@ -17,6 +17,7 @@ #include "llvm/Support/DataTypes.h" #include <cassert> +#include <cstddef> #include <set> namespace llvm { @@ -254,7 +255,7 @@ public: assert(Node != nullptr && "Dereferencing end()!"); return Node->getData(); } - reference operator->() const { return operator*(); } + pointer operator->() const { return &operator*(); } member_iterator &operator++() { assert(Node != nullptr && "++'d off the end of the list!"); diff --git a/include/llvm/ADT/FoldingSet.h b/include/llvm/ADT/FoldingSet.h index 14c5933d388a..52d10c1c1245 100644 --- a/include/llvm/ADT/FoldingSet.h +++ b/include/llvm/ADT/FoldingSet.h @@ -18,13 +18,11 @@ #include "llvm/ADT/SmallVector.h" #include "llvm/ADT/StringRef.h" +#include "llvm/ADT/iterator.h" #include "llvm/Support/Allocator.h" #include "llvm/Support/DataTypes.h" namespace llvm { - class APFloat; - class APInt; - /// This folding set used for two purposes: /// 1. Given information about a node we want to create, look up the unique /// instance of the node in the set. If the node already exists, return @@ -109,6 +107,8 @@ class FoldingSetNodeID; /// back to the bucket to facilitate node removal. /// class FoldingSetImpl { + virtual void anchor(); // Out of line virtual method. + protected: /// Buckets - Array of bucket chains. /// @@ -122,10 +122,11 @@ protected: /// is greater than twice the number of buckets. unsigned NumNodes; -public: + ~FoldingSetImpl(); + explicit FoldingSetImpl(unsigned Log2InitSize = 6); - virtual ~FoldingSetImpl(); +public: //===--------------------------------------------------------------------===// /// Node - This class is used to maintain the singly linked bucket list in /// a folding set. @@ -392,7 +393,7 @@ DefaultContextualFoldingSetTrait<T, Ctx>::ComputeHash(T &X, /// implementation of the folding set to the node class T. T must be a /// subclass of FoldingSetNode and implement a Profile function. /// -template<class T> class FoldingSet : public FoldingSetImpl { +template <class T> class FoldingSet final : public FoldingSetImpl { private: /// GetNodeProfile - Each instantiatation of the FoldingSet needs to provide a /// way to convert nodes into a unique specifier. @@ -462,7 +463,7 @@ public: /// function with signature /// void Profile(llvm::FoldingSetNodeID &, Ctx); template <class T, class Ctx> -class ContextualFoldingSet : public FoldingSetImpl { +class ContextualFoldingSet final : public FoldingSetImpl { // Unfortunately, this can't derive from FoldingSet<T> because the // construction vtable for FoldingSet<T> requires // FoldingSet<T>::GetNodeProfile to be instantiated, which in turn @@ -532,46 +533,6 @@ public: }; //===----------------------------------------------------------------------===// -/// FoldingSetVectorIterator - This implements an iterator for -/// FoldingSetVector. It is only necessary because FoldingSetIterator provides -/// a value_type of T, while the vector in FoldingSetVector exposes -/// a value_type of T*. Fortunately, FoldingSetIterator doesn't expose very -/// much besides operator* and operator->, so we just wrap the inner vector -/// iterator and perform the extra dereference. -template <class T, class VectorIteratorT> -class FoldingSetVectorIterator { - // Provide a typedef to workaround the lack of correct injected class name - // support in older GCCs. - typedef FoldingSetVectorIterator<T, VectorIteratorT> SelfT; - - VectorIteratorT Iterator; - -public: - FoldingSetVectorIterator(VectorIteratorT I) : Iterator(I) {} - - bool operator==(const SelfT &RHS) const { - return Iterator == RHS.Iterator; - } - bool operator!=(const SelfT &RHS) const { - return Iterator != RHS.Iterator; - } - - T &operator*() const { return **Iterator; } - - T *operator->() const { return *Iterator; } - - inline SelfT &operator++() { - ++Iterator; - return *this; - } - SelfT operator++(int) { - SelfT tmp = *this; - ++*this; - return tmp; - } -}; - -//===----------------------------------------------------------------------===// /// FoldingSetVector - This template class combines a FoldingSet and a vector /// to provide the interface of FoldingSet but with deterministic iteration /// order based on the insertion order. T must be a subclass of FoldingSetNode @@ -586,12 +547,11 @@ public: : Set(Log2InitSize) { } - typedef FoldingSetVectorIterator<T, typename VectorT::iterator> iterator; + typedef pointee_iterator<typename VectorT::iterator> iterator; iterator begin() { return Vector.begin(); } iterator end() { return Vector.end(); } - typedef FoldingSetVectorIterator<const T, typename VectorT::const_iterator> - const_iterator; + typedef pointee_iterator<typename VectorT::const_iterator> const_iterator; const_iterator begin() const { return Vector.begin(); } const_iterator end() const { return Vector.end(); } @@ -735,31 +695,9 @@ template <typename T> class FoldingSetNodeWrapper : public FoldingSetNode { T data; public: - explicit FoldingSetNodeWrapper(const T &x) : data(x) {} - virtual ~FoldingSetNodeWrapper() {} - - template<typename A1> - explicit FoldingSetNodeWrapper(const A1 &a1) - : data(a1) {} - - template <typename A1, typename A2> - explicit FoldingSetNodeWrapper(const A1 &a1, const A2 &a2) - : data(a1,a2) {} - - template <typename A1, typename A2, typename A3> - explicit FoldingSetNodeWrapper(const A1 &a1, const A2 &a2, const A3 &a3) - : data(a1,a2,a3) {} - - template <typename A1, typename A2, typename A3, typename A4> - explicit FoldingSetNodeWrapper(const A1 &a1, const A2 &a2, const A3 &a3, - const A4 &a4) - : data(a1,a2,a3,a4) {} - - template <typename A1, typename A2, typename A3, typename A4, typename A5> - explicit FoldingSetNodeWrapper(const A1 &a1, const A2 &a2, const A3 &a3, - const A4 &a4, const A5 &a5) - : data(a1,a2,a3,a4,a5) {} - + template <typename... Ts> + explicit FoldingSetNodeWrapper(Ts &&... Args) + : data(std::forward<Ts>(Args)...) {} void Profile(FoldingSetNodeID &ID) { FoldingSetTrait<T>::Profile(data, ID); } diff --git a/include/llvm/ADT/Hashing.h b/include/llvm/ADT/Hashing.h index abf02b8cc9d5..77e6d77b1b8e 100644 --- a/include/llvm/ADT/Hashing.h +++ b/include/llvm/ADT/Hashing.h @@ -55,12 +55,6 @@ #include <iterator> #include <utility> -// Allow detecting C++11 feature availability when building with Clang without -// breaking other compilers. -#ifndef __has_feature -# define __has_feature(x) 0 -#endif - namespace llvm { /// \brief An opaque object representing a hash code. @@ -81,7 +75,7 @@ class hash_code { public: /// \brief Default construct a hash_code. /// Note that this leaves the value uninitialized. - hash_code() {} + hash_code() = default; /// \brief Form a hash code directly from a numerical value. hash_code(size_t value) : value(value) {} @@ -553,8 +547,6 @@ public: return buffer_ptr; } -#if defined(__has_feature) && __has_feature(__cxx_variadic_templates__) - /// \brief Recursive, variadic combining method. /// /// This function recurses through each argument, combining that argument @@ -568,53 +560,6 @@ public: return combine(length, buffer_ptr, buffer_end, args...); } -#else - // Manually expanded recursive combining methods. See variadic above for - // documentation. - - template <typename T1, typename T2, typename T3, typename T4, typename T5, - typename T6> - hash_code combine(size_t length, char *buffer_ptr, char *buffer_end, - const T1 &arg1, const T2 &arg2, const T3 &arg3, - const T4 &arg4, const T5 &arg5, const T6 &arg6) { - buffer_ptr = combine_data(length, buffer_ptr, buffer_end, get_hashable_data(arg1)); - return combine(length, buffer_ptr, buffer_end, arg2, arg3, arg4, arg5, arg6); - } - template <typename T1, typename T2, typename T3, typename T4, typename T5> - hash_code combine(size_t length, char *buffer_ptr, char *buffer_end, - const T1 &arg1, const T2 &arg2, const T3 &arg3, - const T4 &arg4, const T5 &arg5) { - buffer_ptr = combine_data(length, buffer_ptr, buffer_end, get_hashable_data(arg1)); - return combine(length, buffer_ptr, buffer_end, arg2, arg3, arg4, arg5); - } - template <typename T1, typename T2, typename T3, typename T4> - hash_code combine(size_t length, char *buffer_ptr, char *buffer_end, - const T1 &arg1, const T2 &arg2, const T3 &arg3, - const T4 &arg4) { - buffer_ptr = combine_data(length, buffer_ptr, buffer_end, get_hashable_data(arg1)); - return combine(length, buffer_ptr, buffer_end, arg2, arg3, arg4); - } - template <typename T1, typename T2, typename T3> - hash_code combine(size_t length, char *buffer_ptr, char *buffer_end, - const T1 &arg1, const T2 &arg2, const T3 &arg3) { - buffer_ptr = combine_data(length, buffer_ptr, buffer_end, get_hashable_data(arg1)); - return combine(length, buffer_ptr, buffer_end, arg2, arg3); - } - template <typename T1, typename T2> - hash_code combine(size_t length, char *buffer_ptr, char *buffer_end, - const T1 &arg1, const T2 &arg2) { - buffer_ptr = combine_data(length, buffer_ptr, buffer_end, get_hashable_data(arg1)); - return combine(length, buffer_ptr, buffer_end, arg2); - } - template <typename T1> - hash_code combine(size_t length, char *buffer_ptr, char *buffer_end, - const T1 &arg1) { - buffer_ptr = combine_data(length, buffer_ptr, buffer_end, get_hashable_data(arg1)); - return combine(length, buffer_ptr, buffer_end); - } - -#endif - /// \brief Base case for recursive, variadic combining. /// /// The base case when combining arguments recursively is reached when all @@ -643,9 +588,6 @@ public: } // namespace detail } // namespace hashing - -#if __has_feature(__cxx_variadic_templates__) - /// \brief Combine values into a single hash_code. /// /// This routine accepts a varying number of arguments of any type. It will @@ -663,52 +605,6 @@ template <typename ...Ts> hash_code hash_combine(const Ts &...args) { return helper.combine(0, helper.buffer, helper.buffer + 64, args...); } -#else - -// What follows are manually exploded overloads for each argument width. See -// the above variadic definition for documentation and specification. - -template <typename T1, typename T2, typename T3, typename T4, typename T5, - typename T6> -hash_code hash_combine(const T1 &arg1, const T2 &arg2, const T3 &arg3, - const T4 &arg4, const T5 &arg5, const T6 &arg6) { - ::llvm::hashing::detail::hash_combine_recursive_helper helper; - return helper.combine(0, helper.buffer, helper.buffer + 64, - arg1, arg2, arg3, arg4, arg5, arg6); -} -template <typename T1, typename T2, typename T3, typename T4, typename T5> -hash_code hash_combine(const T1 &arg1, const T2 &arg2, const T3 &arg3, - const T4 &arg4, const T5 &arg5) { - ::llvm::hashing::detail::hash_combine_recursive_helper helper; - return helper.combine(0, helper.buffer, helper.buffer + 64, - arg1, arg2, arg3, arg4, arg5); -} -template <typename T1, typename T2, typename T3, typename T4> -hash_code hash_combine(const T1 &arg1, const T2 &arg2, const T3 &arg3, - const T4 &arg4) { - ::llvm::hashing::detail::hash_combine_recursive_helper helper; - return helper.combine(0, helper.buffer, helper.buffer + 64, - arg1, arg2, arg3, arg4); -} -template <typename T1, typename T2, typename T3> -hash_code hash_combine(const T1 &arg1, const T2 &arg2, const T3 &arg3) { - ::llvm::hashing::detail::hash_combine_recursive_helper helper; - return helper.combine(0, helper.buffer, helper.buffer + 64, arg1, arg2, arg3); -} -template <typename T1, typename T2> -hash_code hash_combine(const T1 &arg1, const T2 &arg2) { - ::llvm::hashing::detail::hash_combine_recursive_helper helper; - return helper.combine(0, helper.buffer, helper.buffer + 64, arg1, arg2); -} -template <typename T1> -hash_code hash_combine(const T1 &arg1) { - ::llvm::hashing::detail::hash_combine_recursive_helper helper; - return helper.combine(0, helper.buffer, helper.buffer + 64, arg1); -} - -#endif - - // Implementation details for implementations of hash_value overloads provided // here. namespace hashing { diff --git a/include/llvm/ADT/ImmutableList.h b/include/llvm/ADT/ImmutableList.h index 7f0c239423bd..748d3e4bf9ff 100644 --- a/include/llvm/ADT/ImmutableList.h +++ b/include/llvm/ADT/ImmutableList.h @@ -33,8 +33,8 @@ class ImmutableListImpl : public FoldingSetNode { friend class ImmutableListFactory<T>; - void operator=(const ImmutableListImpl&) LLVM_DELETED_FUNCTION; - ImmutableListImpl(const ImmutableListImpl&) LLVM_DELETED_FUNCTION; + void operator=(const ImmutableListImpl&) = delete; + ImmutableListImpl(const ImmutableListImpl&) = delete; public: const T& getHead() const { return Head; } diff --git a/include/llvm/ADT/ImmutableMap.h b/include/llvm/ADT/ImmutableMap.h index 11f281be3d23..438dec2333c5 100644 --- a/include/llvm/ADT/ImmutableMap.h +++ b/include/llvm/ADT/ImmutableMap.h @@ -122,8 +122,8 @@ public: } private: - Factory(const Factory& RHS) LLVM_DELETED_FUNCTION; - void operator=(const Factory& RHS) LLVM_DELETED_FUNCTION; + Factory(const Factory& RHS) = delete; + void operator=(const Factory& RHS) = delete; }; bool contains(key_type_ref K) const { @@ -203,33 +203,14 @@ public: // Iterators. //===--------------------------------------------------===// - class iterator { - typename TreeTy::iterator itr; - - iterator() {} - iterator(TreeTy* t) : itr(t) {} + class iterator : public ImutAVLValueIterator<ImmutableMap> { + iterator() = default; + explicit iterator(TreeTy *Tree) : iterator::ImutAVLValueIterator(Tree) {} friend class ImmutableMap; public: - typedef ptrdiff_t difference_type; - typedef typename ImmutableMap<KeyT,ValT,ValInfo>::value_type value_type; - typedef typename ImmutableMap<KeyT,ValT,ValInfo>::value_type_ref reference; - typedef typename iterator::value_type *pointer; - typedef std::bidirectional_iterator_tag iterator_category; - - typename iterator::reference operator*() const { return itr->getValue(); } - typename iterator::pointer operator->() const { return &itr->getValue(); } - - key_type_ref getKey() const { return itr->getValue().first; } - data_type_ref getData() const { return itr->getValue().second; } - - iterator& operator++() { ++itr; return *this; } - iterator operator++(int) { iterator tmp(*this); ++itr; return tmp; } - iterator& operator--() { --itr; return *this; } - iterator operator--(int) { iterator tmp(*this); --itr; return tmp; } - - bool operator==(const iterator& RHS) const { return RHS.itr == itr; } - bool operator!=(const iterator& RHS) const { return RHS.itr != itr; } + key_type_ref getKey() const { return (*this)->first; } + data_type_ref getData() const { return (*this)->second; } }; iterator begin() const { return iterator(Root); } @@ -376,30 +357,17 @@ public: //===--------------------------------------------------===// // Iterators. //===--------------------------------------------------===// - - class iterator { - typename TreeTy::iterator itr; - - iterator() {} - iterator(TreeTy* t) : itr(t) {} + + class iterator : public ImutAVLValueIterator<ImmutableMapRef> { + iterator() = default; + explicit iterator(TreeTy *Tree) : iterator::ImutAVLValueIterator(Tree) {} friend class ImmutableMapRef; - + public: - value_type_ref operator*() const { return itr->getValue(); } - value_type* operator->() const { return &itr->getValue(); } - - key_type_ref getKey() const { return itr->getValue().first; } - data_type_ref getData() const { return itr->getValue().second; } - - - iterator& operator++() { ++itr; return *this; } - iterator operator++(int) { iterator tmp(*this); ++itr; return tmp; } - iterator& operator--() { --itr; return *this; } - iterator operator--(int) { iterator tmp(*this); --itr; return tmp; } - bool operator==(const iterator& RHS) const { return RHS.itr == itr; } - bool operator!=(const iterator& RHS) const { return RHS.itr != itr; } + key_type_ref getKey() const { return (*this)->first; } + data_type_ref getData() const { return (*this)->second; } }; - + iterator begin() const { return iterator(Root); } iterator end() const { return iterator(); } diff --git a/include/llvm/ADT/ImmutableSet.h b/include/llvm/ADT/ImmutableSet.h index 5a3d8ad21f92..87026f019fec 100644 --- a/include/llvm/ADT/ImmutableSet.h +++ b/include/llvm/ADT/ImmutableSet.h @@ -142,13 +142,13 @@ public: iterator RItr = RHS.begin(), REnd = RHS.end(); while (LItr != LEnd && RItr != REnd) { - if (*LItr == *RItr) { + if (&*LItr == &*RItr) { LItr.skipSubTree(); RItr.skipSubTree(); continue; } - if (!LItr->isElementEqual(*RItr)) + if (!LItr->isElementEqual(&*RItr)) return false; ++LItr; @@ -293,8 +293,8 @@ private: height = h; } - static inline - uint32_t computeDigest(ImutAVLTree* L, ImutAVLTree* R, value_type_ref V) { + static uint32_t computeDigest(ImutAVLTree *L, ImutAVLTree *R, + value_type_ref V) { uint32_t digest = 0; if (L) @@ -311,7 +311,7 @@ private: return digest; } - inline uint32_t computeDigest() { + uint32_t computeDigest() { // Check the lowest bit to determine if digest has actually been // pre-computed. if (hasCachedDigest()) @@ -429,9 +429,7 @@ protected: value_type_ref getValue(TreeTy* T) const { return T->value; } // Make sure the index is not the Tombstone or Entry key of the DenseMap. - static inline unsigned maskCacheIndex(unsigned I) { - return (I & ~0x02); - } + static unsigned maskCacheIndex(unsigned I) { return (I & ~0x02); } unsigned incrementHeight(TreeTy* L, TreeTy* R) const { unsigned hl = getHeight(L); @@ -444,7 +442,7 @@ protected: typename TreeTy::iterator& TE) { typename TreeTy::iterator I = T->begin(), E = T->end(); for ( ; I!=E ; ++I, ++TI) { - if (TI == TE || !I->isElementEqual(*TI)) + if (TI == TE || !I->isElementEqual(&*TI)) return false; } return true; @@ -647,24 +645,26 @@ public: //===----------------------------------------------------------------------===// template <typename ImutInfo> -class ImutAVLTreeGenericIterator { +class ImutAVLTreeGenericIterator + : public std::iterator<std::bidirectional_iterator_tag, + ImutAVLTree<ImutInfo>> { SmallVector<uintptr_t,20> stack; public: enum VisitFlag { VisitedNone=0x0, VisitedLeft=0x1, VisitedRight=0x3, Flags=0x3 }; typedef ImutAVLTree<ImutInfo> TreeTy; - typedef ImutAVLTreeGenericIterator<ImutInfo> _Self; - inline ImutAVLTreeGenericIterator() {} - inline ImutAVLTreeGenericIterator(const TreeTy* Root) { + ImutAVLTreeGenericIterator() {} + ImutAVLTreeGenericIterator(const TreeTy *Root) { if (Root) stack.push_back(reinterpret_cast<uintptr_t>(Root)); } - TreeTy* operator*() const { + TreeTy &operator*() const { assert(!stack.empty()); - return reinterpret_cast<TreeTy*>(stack.back() & ~Flags); + return *reinterpret_cast<TreeTy *>(stack.back() & ~Flags); } + TreeTy *operator->() const { return &*this; } uintptr_t getVisitState() const { assert(!stack.empty()); @@ -695,13 +695,15 @@ public: } } - inline bool operator==(const _Self& x) const { + bool operator==(const ImutAVLTreeGenericIterator &x) const { return stack == x.stack; } - inline bool operator!=(const _Self& x) const { return !operator==(x); } + bool operator!=(const ImutAVLTreeGenericIterator &x) const { + return !(*this == x); + } - _Self& operator++() { + ImutAVLTreeGenericIterator &operator++() { assert(!stack.empty()); TreeTy* Current = reinterpret_cast<TreeTy*>(stack.back() & ~Flags); assert(Current); @@ -727,7 +729,7 @@ public: return *this; } - _Self& operator--() { + ImutAVLTreeGenericIterator &operator--() { assert(!stack.empty()); TreeTy* Current = reinterpret_cast<TreeTy*>(stack.back() & ~Flags); assert(Current); @@ -754,30 +756,34 @@ public: }; template <typename ImutInfo> -class ImutAVLTreeInOrderIterator { +class ImutAVLTreeInOrderIterator + : public std::iterator<std::bidirectional_iterator_tag, + ImutAVLTree<ImutInfo>> { typedef ImutAVLTreeGenericIterator<ImutInfo> InternalIteratorTy; InternalIteratorTy InternalItr; public: typedef ImutAVLTree<ImutInfo> TreeTy; - typedef ImutAVLTreeInOrderIterator<ImutInfo> _Self; ImutAVLTreeInOrderIterator(const TreeTy* Root) : InternalItr(Root) { - if (Root) operator++(); // Advance to first element. + if (Root) + ++*this; // Advance to first element. } ImutAVLTreeInOrderIterator() : InternalItr() {} - inline bool operator==(const _Self& x) const { + bool operator==(const ImutAVLTreeInOrderIterator &x) const { return InternalItr == x.InternalItr; } - inline bool operator!=(const _Self& x) const { return !operator==(x); } + bool operator!=(const ImutAVLTreeInOrderIterator &x) const { + return !(*this == x); + } - inline TreeTy* operator*() const { return *InternalItr; } - inline TreeTy* operator->() const { return *InternalItr; } + TreeTy &operator*() const { return *InternalItr; } + TreeTy *operator->() const { return &*InternalItr; } - inline _Self& operator++() { + ImutAVLTreeInOrderIterator &operator++() { do ++InternalItr; while (!InternalItr.atEnd() && InternalItr.getVisitState() != InternalIteratorTy::VisitedLeft); @@ -785,7 +791,7 @@ public: return *this; } - inline _Self& operator--() { + ImutAVLTreeInOrderIterator &operator--() { do --InternalItr; while (!InternalItr.atBeginning() && InternalItr.getVisitState() != InternalIteratorTy::VisitedLeft); @@ -793,7 +799,7 @@ public: return *this; } - inline void skipSubTree() { + void skipSubTree() { InternalItr.skipToParent(); while (!InternalItr.atEnd() && @@ -802,6 +808,24 @@ public: } }; +/// Generic iterator that wraps a T::TreeTy::iterator and exposes +/// iterator::getValue() on dereference. +template <typename T> +struct ImutAVLValueIterator + : iterator_adaptor_base< + ImutAVLValueIterator<T>, typename T::TreeTy::iterator, + typename std::iterator_traits< + typename T::TreeTy::iterator>::iterator_category, + const typename T::value_type> { + ImutAVLValueIterator() = default; + explicit ImutAVLValueIterator(typename T::TreeTy *Tree) + : ImutAVLValueIterator::iterator_adaptor_base(Tree) {} + + typename ImutAVLValueIterator::reference operator*() const { + return this->I->getValue(); + } +}; + //===----------------------------------------------------------------------===// // Trait classes for Profile information. //===----------------------------------------------------------------------===// @@ -814,7 +838,7 @@ struct ImutProfileInfo { typedef const T value_type; typedef const T& value_type_ref; - static inline void Profile(FoldingSetNodeID& ID, value_type_ref X) { + static void Profile(FoldingSetNodeID &ID, value_type_ref X) { FoldingSetTrait<T>::Profile(X,ID); } }; @@ -825,7 +849,7 @@ struct ImutProfileInteger { typedef const T value_type; typedef const T& value_type_ref; - static inline void Profile(FoldingSetNodeID& ID, value_type_ref X) { + static void Profile(FoldingSetNodeID &ID, value_type_ref X) { ID.AddInteger(X); } }; @@ -852,7 +876,7 @@ struct ImutProfileInfo<bool> { typedef const bool value_type; typedef const bool& value_type_ref; - static inline void Profile(FoldingSetNodeID& ID, value_type_ref X) { + static void Profile(FoldingSetNodeID &ID, value_type_ref X) { ID.AddBoolean(X); } }; @@ -865,7 +889,7 @@ struct ImutProfileInfo<T*> { typedef const T* value_type; typedef value_type value_type_ref; - static inline void Profile(FoldingSetNodeID &ID, value_type_ref X) { + static void Profile(FoldingSetNodeID &ID, value_type_ref X) { ID.AddPointer(X); } }; @@ -890,18 +914,18 @@ struct ImutContainerInfo : public ImutProfileInfo<T> { typedef bool data_type; typedef bool data_type_ref; - static inline key_type_ref KeyOfValue(value_type_ref D) { return D; } - static inline data_type_ref DataOfValue(value_type_ref) { return true; } + static key_type_ref KeyOfValue(value_type_ref D) { return D; } + static data_type_ref DataOfValue(value_type_ref) { return true; } - static inline bool isEqual(key_type_ref LHS, key_type_ref RHS) { + static bool isEqual(key_type_ref LHS, key_type_ref RHS) { return std::equal_to<key_type>()(LHS,RHS); } - static inline bool isLess(key_type_ref LHS, key_type_ref RHS) { + static bool isLess(key_type_ref LHS, key_type_ref RHS) { return std::less<key_type>()(LHS,RHS); } - static inline bool isDataEqual(data_type_ref,data_type_ref) { return true; } + static bool isDataEqual(data_type_ref, data_type_ref) { return true; } }; /// ImutContainerInfo - Specialization for pointer values to treat pointers @@ -916,18 +940,14 @@ struct ImutContainerInfo<T*> : public ImutProfileInfo<T*> { typedef bool data_type; typedef bool data_type_ref; - static inline key_type_ref KeyOfValue(value_type_ref D) { return D; } - static inline data_type_ref DataOfValue(value_type_ref) { return true; } + static key_type_ref KeyOfValue(value_type_ref D) { return D; } + static data_type_ref DataOfValue(value_type_ref) { return true; } - static inline bool isEqual(key_type_ref LHS, key_type_ref RHS) { - return LHS == RHS; - } + static bool isEqual(key_type_ref LHS, key_type_ref RHS) { return LHS == RHS; } - static inline bool isLess(key_type_ref LHS, key_type_ref RHS) { - return LHS < RHS; - } + static bool isLess(key_type_ref LHS, key_type_ref RHS) { return LHS < RHS; } - static inline bool isDataEqual(data_type_ref,data_type_ref) { return true; } + static bool isDataEqual(data_type_ref, data_type_ref) { return true; } }; //===----------------------------------------------------------------------===// @@ -1014,8 +1034,8 @@ public: } private: - Factory(const Factory& RHS) LLVM_DELETED_FUNCTION; - void operator=(const Factory& RHS) LLVM_DELETED_FUNCTION; + Factory(const Factory& RHS) = delete; + void operator=(const Factory& RHS) = delete; }; friend class Factory; @@ -1059,31 +1079,7 @@ public: // Iterators. //===--------------------------------------------------===// - class iterator { - typename TreeTy::iterator itr; - - iterator() {} - iterator(TreeTy* t) : itr(t) {} - friend class ImmutableSet<ValT,ValInfo>; - - public: - typedef ptrdiff_t difference_type; - typedef typename ImmutableSet<ValT,ValInfo>::value_type value_type; - typedef typename ImmutableSet<ValT,ValInfo>::value_type_ref reference; - typedef typename iterator::value_type *pointer; - typedef std::bidirectional_iterator_tag iterator_category; - - typename iterator::reference operator*() const { return itr->getValue(); } - typename iterator::pointer operator->() const { return &(operator*()); } - - iterator& operator++() { ++itr; return *this; } - iterator operator++(int) { iterator tmp(*this); ++itr; return tmp; } - iterator& operator--() { --itr; return *this; } - iterator operator--(int) { iterator tmp(*this); --itr; return tmp; } - - bool operator==(const iterator& RHS) const { return RHS.itr == itr; } - bool operator!=(const iterator& RHS) const { return RHS.itr != itr; } - }; + typedef ImutAVLValueIterator<ImmutableSet> iterator; iterator begin() const { return iterator(Root); } iterator end() const { return iterator(); } @@ -1094,13 +1090,11 @@ public: unsigned getHeight() const { return Root ? Root->getHeight() : 0; } - static inline void Profile(FoldingSetNodeID& ID, const ImmutableSet& S) { + static void Profile(FoldingSetNodeID &ID, const ImmutableSet &S) { ID.AddPointer(S.Root); } - inline void Profile(FoldingSetNodeID& ID) const { - return Profile(ID,*this); - } + void Profile(FoldingSetNodeID &ID) const { return Profile(ID, *this); } //===--------------------------------------------------===// // For testing. @@ -1150,7 +1144,7 @@ public: if (Root) { Root->release(); } } - static inline ImmutableSetRef getEmptySet(FactoryTy *F) { + static ImmutableSetRef getEmptySet(FactoryTy *F) { return ImmutableSetRef(0, F); } @@ -1195,21 +1189,7 @@ public: // Iterators. //===--------------------------------------------------===// - class iterator { - typename TreeTy::iterator itr; - iterator(TreeTy* t) : itr(t) {} - friend class ImmutableSetRef<ValT,ValInfo>; - public: - iterator() {} - inline value_type_ref operator*() const { return itr->getValue(); } - inline iterator& operator++() { ++itr; return *this; } - inline iterator operator++(int) { iterator tmp(*this); ++itr; return tmp; } - inline iterator& operator--() { --itr; return *this; } - inline iterator operator--(int) { iterator tmp(*this); --itr; return tmp; } - inline bool operator==(const iterator& RHS) const { return RHS.itr == itr; } - inline bool operator!=(const iterator& RHS) const { return RHS.itr != itr; } - inline value_type *operator->() const { return &(operator*()); } - }; + typedef ImutAVLValueIterator<ImmutableSetRef> iterator; iterator begin() const { return iterator(Root); } iterator end() const { return iterator(); } @@ -1220,13 +1200,11 @@ public: unsigned getHeight() const { return Root ? Root->getHeight() : 0; } - static inline void Profile(FoldingSetNodeID& ID, const ImmutableSetRef& S) { + static void Profile(FoldingSetNodeID &ID, const ImmutableSetRef &S) { ID.AddPointer(S.Root); } - inline void Profile(FoldingSetNodeID& ID) const { - return Profile(ID,*this); - } + void Profile(FoldingSetNodeID &ID) const { return Profile(ID, *this); } //===--------------------------------------------------===// // For testing. diff --git a/include/llvm/ADT/IndexedMap.h b/include/llvm/ADT/IndexedMap.h index 2ffb5058e5bb..5ba85c027920 100644 --- a/include/llvm/ADT/IndexedMap.h +++ b/include/llvm/ADT/IndexedMap.h @@ -21,16 +21,19 @@ #define LLVM_ADT_INDEXEDMAP_H #include "llvm/ADT/STLExtras.h" +#include "llvm/ADT/SmallVector.h" #include <cassert> #include <functional> -#include <vector> namespace llvm { template <typename T, typename ToIndexT = llvm::identity<unsigned> > class IndexedMap { typedef typename ToIndexT::argument_type IndexT; - typedef std::vector<T> StorageT; + // Prefer SmallVector with zero inline storage over std::vector. IndexedMaps + // can grow very large and SmallVector grows more efficiently as long as T + // is trivially copyable. + typedef SmallVector<T, 0> StorageT; StorageT storage_; T nullVal_; ToIndexT toIndex_; diff --git a/include/llvm/ADT/IntervalMap.h b/include/llvm/ADT/IntervalMap.h index 46549eed9939..f8843b2a4e50 100644 --- a/include/llvm/ADT/IntervalMap.h +++ b/include/llvm/ADT/IntervalMap.h @@ -101,6 +101,7 @@ #include "llvm/ADT/PointerIntPair.h" #include "llvm/ADT/SmallVector.h" +#include "llvm/Support/AlignOf.h" #include "llvm/Support/Allocator.h" #include "llvm/Support/RecyclingAllocator.h" #include <iterator> @@ -496,7 +497,7 @@ public: NodeRef() {} /// operator bool - Detect a null ref. - LLVM_EXPLICIT operator bool() const { return pip.getOpaqueValue(); } + explicit operator bool() const { return pip.getOpaqueValue(); } /// NodeRef - Create a reference to the node p with n elements. template <typename NodeT> @@ -953,11 +954,6 @@ class IntervalMap { RootBranch node; }; - enum { - RootDataSize = sizeof(RootBranchData) > sizeof(RootLeaf) ? - sizeof(RootBranchData) : sizeof(RootLeaf) - }; - public: typedef typename Sizer::Allocator Allocator; typedef KeyT KeyType; @@ -966,13 +962,7 @@ public: private: // The root data is either a RootLeaf or a RootBranchData instance. - // We can't put them in a union since C++03 doesn't allow non-trivial - // constructors in unions. - // Instead, we use a char array with pointer alignment. The alignment is - // ensured by the allocator member in the class, but still verified in the - // constructor. We don't support keys or values that are more aligned than a - // pointer. - char data[RootDataSize]; + AlignedCharArrayUnion<RootLeaf, RootBranchData> data; // Tree height. // 0: Leaves in root. @@ -993,7 +983,7 @@ private: const char *d; T *t; } u; - u.d = data; + u.d = data.buffer; return *u.t; } @@ -1051,7 +1041,7 @@ private: public: explicit IntervalMap(Allocator &a) : height(0), rootSize(0), allocator(a) { - assert((uintptr_t(data) & (alignOf<RootLeaf>() - 1)) == 0 && + assert((uintptr_t(data.buffer) & (alignOf<RootLeaf>() - 1)) == 0 && "Insufficient alignment"); new(&rootLeaf()) RootLeaf(); } diff --git a/include/llvm/ADT/IntrusiveRefCntPtr.h b/include/llvm/ADT/IntrusiveRefCntPtr.h index c859c98d06b2..65b2da793d7c 100644 --- a/include/llvm/ADT/IntrusiveRefCntPtr.h +++ b/include/llvm/ADT/IntrusiveRefCntPtr.h @@ -21,10 +21,9 @@ #ifndef LLVM_ADT_INTRUSIVEREFCNTPTR_H #define LLVM_ADT_INTRUSIVEREFCNTPTR_H -#include "llvm/Support/Casting.h" -#include "llvm/Support/Compiler.h" #include <atomic> -#include <memory> +#include <cassert> +#include <cstddef> namespace llvm { @@ -84,7 +83,7 @@ namespace llvm { friend struct IntrusiveRefCntPtrInfo; }; - + template <typename T> struct IntrusiveRefCntPtrInfo { static void retain(T *obj) { obj->Retain(); } static void release(T *obj) { obj->Release(); } @@ -114,7 +113,7 @@ public: delete static_cast<const Derived*>(this); } }; - + //===----------------------------------------------------------------------===// /// IntrusiveRefCntPtr - A template class that implements a "smart pointer" /// that assumes the wrapped object has a reference count associated @@ -177,7 +176,7 @@ public: T* get() const { return Obj; } - LLVM_EXPLICIT operator bool() const { return Obj; } + explicit operator bool() const { return Obj; } void swap(IntrusiveRefCntPtr& other) { T* tmp = other.Obj; @@ -268,6 +267,8 @@ public: // LLVM-style downcasting support for IntrusiveRefCntPtr objects //===----------------------------------------------------------------------===// + template <typename From> struct simplify_type; + template<class T> struct simplify_type<IntrusiveRefCntPtr<T> > { typedef T* SimpleType; static SimpleType getSimplifiedValue(IntrusiveRefCntPtr<T>& Val) { diff --git a/include/llvm/ADT/MapVector.h b/include/llvm/ADT/MapVector.h index 1331b15b2d29..f19a50b7ba84 100644 --- a/include/llvm/ADT/MapVector.h +++ b/include/llvm/ADT/MapVector.h @@ -67,6 +67,11 @@ public: Vector.clear(); } + void swap(MapVector &RHS) { + std::swap(Map, RHS.Map); + std::swap(Vector, RHS.Vector); + } + ValueT &operator[](const KeyT &Key) { std::pair<KeyT, unsigned> Pair = std::make_pair(Key, 0); std::pair<typename MapType::iterator, bool> Result = Map.insert(Pair); diff --git a/include/llvm/ADT/None.h b/include/llvm/ADT/None.h index 5793bd2faef4..d69ec17c15f9 100644 --- a/include/llvm/ADT/None.h +++ b/include/llvm/ADT/None.h @@ -19,9 +19,8 @@ namespace llvm { /// \brief A simple null object to allow implicit construction of Optional<T> /// and similar types without having to spell out the specialization's name. -enum NoneType { - None -}; +enum class NoneType { None }; +const NoneType None = None; } #endif diff --git a/include/llvm/ADT/Optional.h b/include/llvm/ADT/Optional.h index 591872e6591a..855ab890392e 100644 --- a/include/llvm/ADT/Optional.h +++ b/include/llvm/ADT/Optional.h @@ -70,8 +70,6 @@ public: return *this; } -#if LLVM_HAS_VARIADIC_TEMPLATES - /// Create a new object by constructing it in place with the given arguments. template<typename ...ArgTypes> void emplace(ArgTypes &&...Args) { @@ -80,51 +78,6 @@ public: new (storage.buffer) T(std::forward<ArgTypes>(Args)...); } -#else - - /// Create a new object by default-constructing it in place. - void emplace() { - reset(); - hasVal = true; - new (storage.buffer) T(); - } - - /// Create a new object by constructing it in place with the given arguments. - template<typename T1> - void emplace(T1 &&A1) { - reset(); - hasVal = true; - new (storage.buffer) T(std::forward<T1>(A1)); - } - - /// Create a new object by constructing it in place with the given arguments. - template<typename T1, typename T2> - void emplace(T1 &&A1, T2 &&A2) { - reset(); - hasVal = true; - new (storage.buffer) T(std::forward<T1>(A1), std::forward<T2>(A2)); - } - - /// Create a new object by constructing it in place with the given arguments. - template<typename T1, typename T2, typename T3> - void emplace(T1 &&A1, T2 &&A2, T3 &&A3) { - reset(); - hasVal = true; - new (storage.buffer) T(std::forward<T1>(A1), std::forward<T2>(A2), - std::forward<T3>(A3)); - } - - /// Create a new object by constructing it in place with the given arguments. - template<typename T1, typename T2, typename T3, typename T4> - void emplace(T1 &&A1, T2 &&A2, T3 &&A3, T4 &&A4) { - reset(); - hasVal = true; - new (storage.buffer) T(std::forward<T1>(A1), std::forward<T2>(A2), - std::forward<T3>(A3), std::forward<T4>(A4)); - } - -#endif // LLVM_HAS_VARIADIC_TEMPLATES - static inline Optional create(const T* y) { return y ? Optional(*y) : Optional(); } @@ -168,7 +121,7 @@ public: const T& getValue() const LLVM_LVALUE_FUNCTION { assert(hasVal); return *getPointer(); } T& getValue() LLVM_LVALUE_FUNCTION { assert(hasVal); return *getPointer(); } - LLVM_EXPLICIT operator bool() const { return hasVal; } + explicit operator bool() const { return hasVal; } bool hasValue() const { return hasVal; } const T* operator->() const { return getPointer(); } T* operator->() { return getPointer(); } diff --git a/include/llvm/ADT/PointerUnion.h b/include/llvm/ADT/PointerUnion.h index a6dddd277621..f27b81113ec5 100644 --- a/include/llvm/ADT/PointerUnion.h +++ b/include/llvm/ADT/PointerUnion.h @@ -61,7 +61,7 @@ namespace llvm { NumLowBitsAvailable = PT1BitsAv < PT2BitsAv ? PT1BitsAv : PT2BitsAv }; }; - + /// PointerUnion - This implements a discriminated union of two pointer types, /// and keeps the discriminator bit-mangled into the low bits of the pointer. /// This allows the implementation to be extremely efficient in space, but @@ -80,7 +80,7 @@ namespace llvm { template <typename PT1, typename PT2> class PointerUnion { public: - typedef PointerIntPair<void*, 1, bool, + typedef PointerIntPair<void*, 1, bool, PointerUnionUIntTraits<PT1,PT2> > ValTy; private: ValTy Val; @@ -96,14 +96,14 @@ namespace llvm { public: PointerUnion() {} - + PointerUnion(PT1 V) : Val( const_cast<void *>(PointerLikeTypeTraits<PT1>::getAsVoidPointer(V))) { } PointerUnion(PT2 V) : Val( const_cast<void *>(PointerLikeTypeTraits<PT2>::getAsVoidPointer(V)), 1) { } - + /// isNull - Return true if the pointer held in the union is null, /// regardless of which type it is. bool isNull() const { @@ -111,7 +111,7 @@ namespace llvm { // we recursively strip off low bits if we have a nested PointerUnion. return !PointerLikeTypeTraits<PT1>::getFromVoidPointer(Val.getPointer()); } - LLVM_EXPLICIT operator bool() const { return !isNull(); } + explicit operator bool() const { return !isNull(); } /// is<T>() return true if the Union currently holds the type matching T. template<typename T> @@ -123,7 +123,7 @@ namespace llvm { int TyNo = Ty::Num; return static_cast<int>(Val.getInt()) == TyNo; } - + /// get<T>() - Return the value of the specified pointer type. If the /// specified pointer type is incorrect, assert. template<typename T> @@ -131,7 +131,7 @@ namespace llvm { assert(is<T>() && "Invalid accessor called"); return PointerLikeTypeTraits<T>::getFromVoidPointer(Val.getPointer()); } - + /// dyn_cast<T>() - If the current value is of the specified pointer type, /// return it, otherwise return null. template<typename T> @@ -160,7 +160,7 @@ namespace llvm { Val.initWithPointer(nullptr); return *this; } - + /// Assignment operators - Allow assigning into this union from either /// pointer type, setting the discriminator to remember what it came from. const PointerUnion &operator=(const PT1 &RHS) { @@ -174,7 +174,7 @@ namespace llvm { 1); return *this; } - + void *getOpaqueValue() const { return Val.getOpaqueValue(); } static inline PointerUnion getFromOpaqueValue(void *VP) { PointerUnion V; @@ -195,6 +195,12 @@ namespace llvm { return lhs.getOpaqueValue() != rhs.getOpaqueValue(); } + template<typename PT1, typename PT2> + static bool operator<(PointerUnion<PT1, PT2> lhs, + PointerUnion<PT1, PT2> rhs) { + return lhs.getOpaqueValue() < rhs.getOpaqueValue(); + } + // Teach SmallPtrSet that PointerUnion is "basically a pointer", that has // # low bits available = min(PT1bits,PT2bits)-1. template<typename PT1, typename PT2> @@ -208,16 +214,16 @@ namespace llvm { getFromVoidPointer(void *P) { return PointerUnion<PT1, PT2>::getFromOpaqueValue(P); } - + // The number of bits available are the min of the two pointer types. enum { - NumLowBitsAvailable = + NumLowBitsAvailable = PointerLikeTypeTraits<typename PointerUnion<PT1,PT2>::ValTy> ::NumLowBitsAvailable }; }; - - + + /// PointerUnion3 - This is a pointer union of three pointer types. See /// documentation for PointerUnion for usage. template <typename PT1, typename PT2, typename PT3> @@ -233,7 +239,7 @@ namespace llvm { IsInnerUnion(ValTy val) : Val(val) { } template<typename T> int is() const { - return Val.template is<InnerUnion>() && + return Val.template is<InnerUnion>() && Val.template get<InnerUnion>().template is<T>(); } template<typename T> @@ -257,7 +263,7 @@ namespace llvm { public: PointerUnion3() {} - + PointerUnion3(PT1 V) { Val = InnerUnion(V); } @@ -267,12 +273,12 @@ namespace llvm { PointerUnion3(PT3 V) { Val = V; } - + /// isNull - Return true if the pointer held in the union is null, /// regardless of which type it is. bool isNull() const { return Val.isNull(); } - LLVM_EXPLICIT operator bool() const { return !isNull(); } - + explicit operator bool() const { return !isNull(); } + /// is<T>() return true if the Union currently holds the type matching T. template<typename T> int is() const { @@ -283,7 +289,7 @@ namespace llvm { >::Return Ty; return Ty(Val).template is<T>(); } - + /// get<T>() - Return the value of the specified pointer type. If the /// specified pointer type is incorrect, assert. template<typename T> @@ -296,7 +302,7 @@ namespace llvm { >::Return Ty; return Ty(Val).template get<T>(); } - + /// dyn_cast<T>() - If the current value is of the specified pointer type, /// return it, otherwise return null. template<typename T> @@ -310,7 +316,7 @@ namespace llvm { Val = nullptr; return *this; } - + /// Assignment operators - Allow assigning into this union from either /// pointer type, setting the discriminator to remember what it came from. const PointerUnion3 &operator=(const PT1 &RHS) { @@ -325,7 +331,7 @@ namespace llvm { Val = RHS; return *this; } - + void *getOpaqueValue() const { return Val.getOpaqueValue(); } static inline PointerUnion3 getFromOpaqueValue(void *VP) { PointerUnion3 V; @@ -333,7 +339,7 @@ namespace llvm { return V; } }; - + // Teach SmallPtrSet that PointerUnion3 is "basically a pointer", that has // # low bits available = min(PT1bits,PT2bits,PT2bits)-2. template<typename PT1, typename PT2, typename PT3> @@ -347,10 +353,10 @@ namespace llvm { getFromVoidPointer(void *P) { return PointerUnion3<PT1, PT2, PT3>::getFromOpaqueValue(P); } - + // The number of bits available are the min of the two pointer types. enum { - NumLowBitsAvailable = + NumLowBitsAvailable = PointerLikeTypeTraits<typename PointerUnion3<PT1, PT2, PT3>::ValTy> ::NumLowBitsAvailable }; @@ -368,7 +374,7 @@ namespace llvm { ValTy Val; public: PointerUnion4() {} - + PointerUnion4(PT1 V) { Val = InnerUnion1(V); } @@ -381,12 +387,12 @@ namespace llvm { PointerUnion4(PT4 V) { Val = InnerUnion2(V); } - + /// isNull - Return true if the pointer held in the union is null, /// regardless of which type it is. bool isNull() const { return Val.isNull(); } - LLVM_EXPLICIT operator bool() const { return !isNull(); } - + explicit operator bool() const { return !isNull(); } + /// is<T>() return true if the Union currently holds the type matching T. template<typename T> int is() const { @@ -395,10 +401,10 @@ namespace llvm { ::llvm::PointerUnionTypeSelector<PT1, T, InnerUnion1, ::llvm::PointerUnionTypeSelector<PT2, T, InnerUnion1, InnerUnion2 > >::Return Ty; - return Val.template is<Ty>() && + return Val.template is<Ty>() && Val.template get<Ty>().template is<T>(); } - + /// get<T>() - Return the value of the specified pointer type. If the /// specified pointer type is incorrect, assert. template<typename T> @@ -411,7 +417,7 @@ namespace llvm { >::Return Ty; return Val.template get<Ty>().template get<T>(); } - + /// dyn_cast<T>() - If the current value is of the specified pointer type, /// return it, otherwise return null. template<typename T> @@ -425,7 +431,7 @@ namespace llvm { Val = nullptr; return *this; } - + /// Assignment operators - Allow assigning into this union from either /// pointer type, setting the discriminator to remember what it came from. const PointerUnion4 &operator=(const PT1 &RHS) { @@ -444,7 +450,7 @@ namespace llvm { Val = InnerUnion2(RHS); return *this; } - + void *getOpaqueValue() const { return Val.getOpaqueValue(); } static inline PointerUnion4 getFromOpaqueValue(void *VP) { PointerUnion4 V; @@ -452,7 +458,7 @@ namespace llvm { return V; } }; - + // Teach SmallPtrSet that PointerUnion4 is "basically a pointer", that has // # low bits available = min(PT1bits,PT2bits,PT2bits)-2. template<typename PT1, typename PT2, typename PT3, typename PT4> @@ -466,10 +472,10 @@ namespace llvm { getFromVoidPointer(void *P) { return PointerUnion4<PT1, PT2, PT3, PT4>::getFromOpaqueValue(P); } - + // The number of bits available are the min of the two pointer types. enum { - NumLowBitsAvailable = + NumLowBitsAvailable = PointerLikeTypeTraits<typename PointerUnion4<PT1, PT2, PT3, PT4>::ValTy> ::NumLowBitsAvailable }; diff --git a/include/llvm/ADT/PostOrderIterator.h b/include/llvm/ADT/PostOrderIterator.h index dfadc3b85db6..759a2db24f2a 100644 --- a/include/llvm/ADT/PostOrderIterator.h +++ b/include/llvm/ADT/PostOrderIterator.h @@ -18,6 +18,7 @@ #include "llvm/ADT/GraphTraits.h" #include "llvm/ADT/SmallPtrSet.h" +#include "llvm/ADT/iterator_range.h" #include <set> #include <vector> @@ -111,53 +112,52 @@ class po_iterator : public std::iterator<std::forward_iterator_tag, } } - inline po_iterator(NodeType *BB) { + po_iterator(NodeType *BB) { this->insertEdge((NodeType*)nullptr, BB); VisitStack.push_back(std::make_pair(BB, GT::child_begin(BB))); traverseChild(); } - inline po_iterator() {} // End is when stack is empty. + po_iterator() {} // End is when stack is empty. - inline po_iterator(NodeType *BB, SetType &S) : - po_iterator_storage<SetType, ExtStorage>(S) { + po_iterator(NodeType *BB, SetType &S) + : po_iterator_storage<SetType, ExtStorage>(S) { if (this->insertEdge((NodeType*)nullptr, BB)) { VisitStack.push_back(std::make_pair(BB, GT::child_begin(BB))); traverseChild(); } } - inline po_iterator(SetType &S) : - po_iterator_storage<SetType, ExtStorage>(S) { + po_iterator(SetType &S) + : po_iterator_storage<SetType, ExtStorage>(S) { } // End is when stack is empty. public: typedef typename super::pointer pointer; - typedef po_iterator<GraphT, SetType, ExtStorage, GT> _Self; // Provide static "constructors"... - static inline _Self begin(GraphT G) { return _Self(GT::getEntryNode(G)); } - static inline _Self end (GraphT G) { return _Self(); } + static po_iterator begin(GraphT G) { + return po_iterator(GT::getEntryNode(G)); + } + static po_iterator end(GraphT G) { return po_iterator(); } - static inline _Self begin(GraphT G, SetType &S) { - return _Self(GT::getEntryNode(G), S); + static po_iterator begin(GraphT G, SetType &S) { + return po_iterator(GT::getEntryNode(G), S); } - static inline _Self end (GraphT G, SetType &S) { return _Self(S); } + static po_iterator end(GraphT G, SetType &S) { return po_iterator(S); } - inline bool operator==(const _Self& x) const { + bool operator==(const po_iterator &x) const { return VisitStack == x.VisitStack; } - inline bool operator!=(const _Self& x) const { return !operator==(x); } + bool operator!=(const po_iterator &x) const { return !(*this == x); } - inline pointer operator*() const { - return VisitStack.back().first; - } + pointer operator*() const { return VisitStack.back().first; } // This is a nonstandard operator-> that dereferences the pointer an extra // time... so that you can actually call methods ON the BasicBlock, because // the contained type is a pointer. This allows BBIt->getTerminator() f.e. // - inline NodeType *operator->() const { return operator*(); } + NodeType *operator->() const { return **this; } - inline _Self& operator++() { // Preincrement + po_iterator &operator++() { // Preincrement this->finishPostorder(VisitStack.back().first); VisitStack.pop_back(); if (!VisitStack.empty()) @@ -165,17 +165,23 @@ public: return *this; } - inline _Self operator++(int) { // Postincrement - _Self tmp = *this; ++*this; return tmp; + po_iterator operator++(int) { // Postincrement + po_iterator tmp = *this; + ++*this; + return tmp; } }; // Provide global constructors that automatically figure out correct types... // template <class T> -po_iterator<T> po_begin(T G) { return po_iterator<T>::begin(G); } +po_iterator<T> po_begin(const T &G) { return po_iterator<T>::begin(G); } template <class T> -po_iterator<T> po_end (T G) { return po_iterator<T>::end(G); } +po_iterator<T> po_end (const T &G) { return po_iterator<T>::end(G); } + +template <class T> iterator_range<po_iterator<T>> post_order(const T &G) { + return make_range(po_begin(G), po_end(G)); +} // Provide global definitions of external postorder iterators... template<class T, class SetType=std::set<typename GraphTraits<T>::NodeType*> > @@ -194,6 +200,11 @@ po_ext_iterator<T, SetType> po_ext_end(T G, SetType &S) { return po_ext_iterator<T, SetType>::end(G, S); } +template <class T, class SetType> +iterator_range<po_ext_iterator<T, SetType>> post_order_ext(const T &G, SetType &S) { + return make_range(po_ext_begin(G, S), po_ext_end(G, S)); +} + // Provide global definitions of inverse post order iterators... template <class T, class SetType = std::set<typename GraphTraits<T>::NodeType*>, @@ -204,15 +215,20 @@ struct ipo_iterator : public po_iterator<Inverse<T>, SetType, External > { }; template <class T> -ipo_iterator<T> ipo_begin(T G, bool Reverse = false) { +ipo_iterator<T> ipo_begin(const T &G, bool Reverse = false) { return ipo_iterator<T>::begin(G, Reverse); } template <class T> -ipo_iterator<T> ipo_end(T G){ +ipo_iterator<T> ipo_end(const T &G){ return ipo_iterator<T>::end(G); } +template <class T> +iterator_range<ipo_iterator<T>> inverse_post_order(const T &G, bool Reverse = false) { + return make_range(ipo_begin(G, Reverse), ipo_end(G)); +} + // Provide global definitions of external inverse postorder iterators... template <class T, class SetType = std::set<typename GraphTraits<T>::NodeType*> > @@ -224,15 +240,21 @@ struct ipo_ext_iterator : public ipo_iterator<T, SetType, true> { }; template <class T, class SetType> -ipo_ext_iterator<T, SetType> ipo_ext_begin(T G, SetType &S) { +ipo_ext_iterator<T, SetType> ipo_ext_begin(const T &G, SetType &S) { return ipo_ext_iterator<T, SetType>::begin(G, S); } template <class T, class SetType> -ipo_ext_iterator<T, SetType> ipo_ext_end(T G, SetType &S) { +ipo_ext_iterator<T, SetType> ipo_ext_end(const T &G, SetType &S) { return ipo_ext_iterator<T, SetType>::end(G, S); } +template <class T, class SetType> +iterator_range<ipo_ext_iterator<T, SetType>> +inverse_post_order_ext(const T &G, SetType &S) { + return make_range(ipo_ext_begin(G, S), ipo_ext_end(G, S)); +} + //===--------------------------------------------------------------------===// // Reverse Post Order CFG iterator code //===--------------------------------------------------------------------===// @@ -260,19 +282,17 @@ template<class GraphT, class GT = GraphTraits<GraphT> > class ReversePostOrderTraversal { typedef typename GT::NodeType NodeType; std::vector<NodeType*> Blocks; // Block list in normal PO order - inline void Initialize(NodeType *BB) { + void Initialize(NodeType *BB) { std::copy(po_begin(BB), po_end(BB), std::back_inserter(Blocks)); } public: typedef typename std::vector<NodeType*>::reverse_iterator rpo_iterator; - inline ReversePostOrderTraversal(GraphT G) { - Initialize(GT::getEntryNode(G)); - } + ReversePostOrderTraversal(GraphT G) { Initialize(GT::getEntryNode(G)); } // Because we want a reverse post order, use reverse iterators from the vector - inline rpo_iterator begin() { return Blocks.rbegin(); } - inline rpo_iterator end() { return Blocks.rend(); } + rpo_iterator begin() { return Blocks.rbegin(); } + rpo_iterator end() { return Blocks.rend(); } }; } // End llvm namespace diff --git a/include/llvm/ADT/STLExtras.h b/include/llvm/ADT/STLExtras.h index 4e56e4d74470..b68345a1dcf6 100644 --- a/include/llvm/ADT/STLExtras.h +++ b/include/llvm/ADT/STLExtras.h @@ -18,6 +18,8 @@ #define LLVM_ADT_STLEXTRAS_H #include "llvm/Support/Compiler.h" +#include <algorithm> // for std::all_of +#include <cassert> #include <cstddef> // for std::size_t #include <cstdlib> // for qsort #include <functional> @@ -63,8 +65,6 @@ struct greater_ptr : public std::binary_function<Ty, Ty, bool> { /// a function_ref. template<typename Fn> class function_ref; -#if LLVM_HAS_VARIADIC_TEMPLATES - template<typename Ret, typename ...Params> class function_ref<Ret(Params...)> { Ret (*callback)(intptr_t callable, Params ...params); @@ -89,112 +89,6 @@ public: } }; -#else - -template<typename Ret> -class function_ref<Ret()> { - Ret (*callback)(intptr_t callable); - intptr_t callable; - - template<typename Callable> - static Ret callback_fn(intptr_t callable) { - return (*reinterpret_cast<Callable*>(callable))(); - } - -public: - template<typename Callable> - function_ref(Callable &&callable, - typename std::enable_if< - !std::is_same<typename std::remove_reference<Callable>::type, - function_ref>::value>::type * = nullptr) - : callback(callback_fn<typename std::remove_reference<Callable>::type>), - callable(reinterpret_cast<intptr_t>(&callable)) {} - Ret operator()() const { return callback(callable); } -}; - -template<typename Ret, typename Param1> -class function_ref<Ret(Param1)> { - Ret (*callback)(intptr_t callable, Param1 param1); - intptr_t callable; - - template<typename Callable> - static Ret callback_fn(intptr_t callable, Param1 param1) { - return (*reinterpret_cast<Callable*>(callable))( - std::forward<Param1>(param1)); - } - -public: - template<typename Callable> - function_ref(Callable &&callable, - typename std::enable_if< - !std::is_same<typename std::remove_reference<Callable>::type, - function_ref>::value>::type * = nullptr) - : callback(callback_fn<typename std::remove_reference<Callable>::type>), - callable(reinterpret_cast<intptr_t>(&callable)) {} - Ret operator()(Param1 param1) { - return callback(callable, std::forward<Param1>(param1)); - } -}; - -template<typename Ret, typename Param1, typename Param2> -class function_ref<Ret(Param1, Param2)> { - Ret (*callback)(intptr_t callable, Param1 param1, Param2 param2); - intptr_t callable; - - template<typename Callable> - static Ret callback_fn(intptr_t callable, Param1 param1, Param2 param2) { - return (*reinterpret_cast<Callable*>(callable))( - std::forward<Param1>(param1), - std::forward<Param2>(param2)); - } - -public: - template<typename Callable> - function_ref(Callable &&callable, - typename std::enable_if< - !std::is_same<typename std::remove_reference<Callable>::type, - function_ref>::value>::type * = nullptr) - : callback(callback_fn<typename std::remove_reference<Callable>::type>), - callable(reinterpret_cast<intptr_t>(&callable)) {} - Ret operator()(Param1 param1, Param2 param2) { - return callback(callable, - std::forward<Param1>(param1), - std::forward<Param2>(param2)); - } -}; - -template<typename Ret, typename Param1, typename Param2, typename Param3> -class function_ref<Ret(Param1, Param2, Param3)> { - Ret (*callback)(intptr_t callable, Param1 param1, Param2 param2, Param3 param3); - intptr_t callable; - - template<typename Callable> - static Ret callback_fn(intptr_t callable, Param1 param1, Param2 param2, - Param3 param3) { - return (*reinterpret_cast<Callable*>(callable))( - std::forward<Param1>(param1), - std::forward<Param2>(param2), - std::forward<Param3>(param3)); - } - -public: - template<typename Callable> - function_ref(Callable &&callable, - typename std::enable_if< - !std::is_same<typename std::remove_reference<Callable>::type, - function_ref>::value>::type * = nullptr) - : callback(callback_fn<typename std::remove_reference<Callable>::type>), - callable(reinterpret_cast<intptr_t>(&callable)) {} - Ret operator()(Param1 param1, Param2 param2, Param3 param3) { - return callback(callable, - std::forward<Param1>(param1), - std::forward<Param2>(param2), - std::forward<Param3>(param3)); - } -}; - -#endif - // deleter - Very very very simple method that is used to invoke operator // delete on something. It is used like this: // @@ -230,7 +124,6 @@ public: typedef void reference; // Can't modify value returned by fn typedef RootIt iterator_type; - typedef mapped_iterator<RootIt, UnaryFunc> _Self; inline const RootIt &getCurrent() const { return current; } inline const UnaryFunc &getFunc() const { return Fn; } @@ -242,34 +135,56 @@ public: return Fn(*current); // little change } - _Self& operator++() { ++current; return *this; } - _Self& operator--() { --current; return *this; } - _Self operator++(int) { _Self __tmp = *this; ++current; return __tmp; } - _Self operator--(int) { _Self __tmp = *this; --current; return __tmp; } - _Self operator+ (difference_type n) const { - return _Self(current + n, Fn); + mapped_iterator &operator++() { + ++current; + return *this; } - _Self& operator+= (difference_type n) { current += n; return *this; } - _Self operator- (difference_type n) const { - return _Self(current - n, Fn); + mapped_iterator &operator--() { + --current; + return *this; + } + mapped_iterator operator++(int) { + mapped_iterator __tmp = *this; + ++current; + return __tmp; + } + mapped_iterator operator--(int) { + mapped_iterator __tmp = *this; + --current; + return __tmp; + } + mapped_iterator operator+(difference_type n) const { + return mapped_iterator(current + n, Fn); + } + mapped_iterator &operator+=(difference_type n) { + current += n; + return *this; + } + mapped_iterator operator-(difference_type n) const { + return mapped_iterator(current - n, Fn); + } + mapped_iterator &operator-=(difference_type n) { + current -= n; + return *this; } - _Self& operator-= (difference_type n) { current -= n; return *this; } reference operator[](difference_type n) const { return *(*this + n); } - inline bool operator!=(const _Self &X) const { return !operator==(X); } - inline bool operator==(const _Self &X) const { return current == X.current; } - inline bool operator< (const _Self &X) const { return current < X.current; } + bool operator!=(const mapped_iterator &X) const { return !operator==(X); } + bool operator==(const mapped_iterator &X) const { + return current == X.current; + } + bool operator<(const mapped_iterator &X) const { return current < X.current; } - inline difference_type operator-(const _Self &X) const { + difference_type operator-(const mapped_iterator &X) const { return current - X.current; } }; -template <class _Iterator, class Func> -inline mapped_iterator<_Iterator, Func> -operator+(typename mapped_iterator<_Iterator, Func>::difference_type N, - const mapped_iterator<_Iterator, Func>& X) { - return mapped_iterator<_Iterator, Func>(X.getCurrent() - N, X.getFunc()); +template <class Iterator, class Func> +inline mapped_iterator<Iterator, Func> +operator+(typename mapped_iterator<Iterator, Func>::difference_type N, + const mapped_iterator<Iterator, Func> &X) { + return mapped_iterator<Iterator, Func>(X.getCurrent() - N, X.getFunc()); } @@ -301,6 +216,28 @@ struct less_second { } }; +// A subset of N3658. More stuff can be added as-needed. + +/// \brief Represents a compile-time sequence of integers. +template <class T, T... I> struct integer_sequence { + typedef T value_type; + + static LLVM_CONSTEXPR size_t size() { return sizeof...(I); } +}; + +/// \brief Alias for the common case of a sequence of size_ts. +template <size_t... I> +struct index_sequence : integer_sequence<std::size_t, I...> {}; + +template <std::size_t N, std::size_t... I> +struct build_index_impl : build_index_impl<N - 1, N - 1, I...> {}; +template <std::size_t... I> +struct build_index_impl<0, I...> : index_sequence<I...> {}; + +/// \brief Creates a compile-time integer sequence for a parameter pack. +template <class... Ts> +struct index_sequence_for : build_index_impl<sizeof...(Ts)> {}; + //===----------------------------------------------------------------------===// // Extra additions for arrays //===----------------------------------------------------------------------===// @@ -348,10 +285,11 @@ inline int (*get_array_pod_sort_comparator(const T &)) /// default to std::less. template<class IteratorTy> inline void array_pod_sort(IteratorTy Start, IteratorTy End) { - // Don't dereference start iterator of empty sequence. - if (Start == End) return; - qsort(&*Start, End-Start, sizeof(*Start), - get_array_pod_sort_comparator(*Start)); + // Don't inefficiently call qsort with one element or trigger undefined + // behavior with an empty sequence. + auto NElts = End - Start; + if (NElts <= 1) return; + qsort(&*Start, NElts, sizeof(*Start), get_array_pod_sort_comparator(*Start)); } template <class IteratorTy> @@ -360,9 +298,11 @@ inline void array_pod_sort( int (*Compare)( const typename std::iterator_traits<IteratorTy>::value_type *, const typename std::iterator_traits<IteratorTy>::value_type *)) { - // Don't dereference start iterator of empty sequence. - if (Start == End) return; - qsort(&*Start, End - Start, sizeof(*Start), + // Don't inefficiently call qsort with one element or trigger undefined + // behavior with an empty sequence. + auto NElts = End - Start; + if (NElts <= 1) return; + qsort(&*Start, NElts, sizeof(*Start), reinterpret_cast<int (*)(const void *, const void *)>(Compare)); } @@ -388,12 +328,18 @@ void DeleteContainerSeconds(Container &C) { C.clear(); } +/// Provide wrappers to std::all_of which take ranges instead of having to pass +/// being/end explicitly. +template<typename R, class UnaryPredicate> +bool all_of(R &&Range, UnaryPredicate &&P) { + return std::all_of(Range.begin(), Range.end(), + std::forward<UnaryPredicate>(P)); +} + //===----------------------------------------------------------------------===// // Extra additions to <memory> //===----------------------------------------------------------------------===// -#if LLVM_HAS_VARIADIC_TEMPLATES - // Implement make_unique according to N3656. /// \brief Constructs a `new T()` with the given args and returns a @@ -427,123 +373,7 @@ make_unique(size_t n) { /// This function isn't used and is only here to provide better compile errors. template <class T, class... Args> typename std::enable_if<std::extent<T>::value != 0>::type -make_unique(Args &&...) LLVM_DELETED_FUNCTION; - -#else - -template <class T> -typename std::enable_if<!std::is_array<T>::value, std::unique_ptr<T>>::type -make_unique() { - return std::unique_ptr<T>(new T()); -} - -template <class T, class Arg1> -typename std::enable_if<!std::is_array<T>::value, std::unique_ptr<T>>::type -make_unique(Arg1 &&arg1) { - return std::unique_ptr<T>(new T(std::forward<Arg1>(arg1))); -} - -template <class T, class Arg1, class Arg2> -typename std::enable_if<!std::is_array<T>::value, std::unique_ptr<T>>::type -make_unique(Arg1 &&arg1, Arg2 &&arg2) { - return std::unique_ptr<T>( - new T(std::forward<Arg1>(arg1), std::forward<Arg2>(arg2))); -} - -template <class T, class Arg1, class Arg2, class Arg3> -typename std::enable_if<!std::is_array<T>::value, std::unique_ptr<T>>::type -make_unique(Arg1 &&arg1, Arg2 &&arg2, Arg3 &&arg3) { - return std::unique_ptr<T>(new T(std::forward<Arg1>(arg1), - std::forward<Arg2>(arg2), - std::forward<Arg3>(arg3))); -} - -template <class T, class Arg1, class Arg2, class Arg3, class Arg4> -typename std::enable_if<!std::is_array<T>::value, std::unique_ptr<T>>::type -make_unique(Arg1 &&arg1, Arg2 &&arg2, Arg3 &&arg3, Arg4 &&arg4) { - return std::unique_ptr<T>( - new T(std::forward<Arg1>(arg1), std::forward<Arg2>(arg2), - std::forward<Arg3>(arg3), std::forward<Arg4>(arg4))); -} - -template <class T, class Arg1, class Arg2, class Arg3, class Arg4, class Arg5> -typename std::enable_if<!std::is_array<T>::value, std::unique_ptr<T>>::type -make_unique(Arg1 &&arg1, Arg2 &&arg2, Arg3 &&arg3, Arg4 &&arg4, Arg5 &&arg5) { - return std::unique_ptr<T>( - new T(std::forward<Arg1>(arg1), std::forward<Arg2>(arg2), - std::forward<Arg3>(arg3), std::forward<Arg4>(arg4), - std::forward<Arg5>(arg5))); -} - -template <class T, class Arg1, class Arg2, class Arg3, class Arg4, class Arg5, - class Arg6> -typename std::enable_if<!std::is_array<T>::value, std::unique_ptr<T>>::type -make_unique(Arg1 &&arg1, Arg2 &&arg2, Arg3 &&arg3, Arg4 &&arg4, Arg5 &&arg5, - Arg6 &&arg6) { - return std::unique_ptr<T>( - new T(std::forward<Arg1>(arg1), std::forward<Arg2>(arg2), - std::forward<Arg3>(arg3), std::forward<Arg4>(arg4), - std::forward<Arg5>(arg5), std::forward<Arg6>(arg6))); -} - -template <class T, class Arg1, class Arg2, class Arg3, class Arg4, class Arg5, - class Arg6, class Arg7> -typename std::enable_if<!std::is_array<T>::value, std::unique_ptr<T>>::type -make_unique(Arg1 &&arg1, Arg2 &&arg2, Arg3 &&arg3, Arg4 &&arg4, Arg5 &&arg5, - Arg6 &&arg6, Arg7 &&arg7) { - return std::unique_ptr<T>( - new T(std::forward<Arg1>(arg1), std::forward<Arg2>(arg2), - std::forward<Arg3>(arg3), std::forward<Arg4>(arg4), - std::forward<Arg5>(arg5), std::forward<Arg6>(arg6), - std::forward<Arg7>(arg7))); -} - -template <class T, class Arg1, class Arg2, class Arg3, class Arg4, class Arg5, - class Arg6, class Arg7, class Arg8> -typename std::enable_if<!std::is_array<T>::value, std::unique_ptr<T>>::type -make_unique(Arg1 &&arg1, Arg2 &&arg2, Arg3 &&arg3, Arg4 &&arg4, Arg5 &&arg5, - Arg6 &&arg6, Arg7 &&arg7, Arg8 &&arg8) { - return std::unique_ptr<T>( - new T(std::forward<Arg1>(arg1), std::forward<Arg2>(arg2), - std::forward<Arg3>(arg3), std::forward<Arg4>(arg4), - std::forward<Arg5>(arg5), std::forward<Arg6>(arg6), - std::forward<Arg7>(arg7), std::forward<Arg8>(arg8))); -} - -template <class T, class Arg1, class Arg2, class Arg3, class Arg4, class Arg5, - class Arg6, class Arg7, class Arg8, class Arg9> -typename std::enable_if<!std::is_array<T>::value, std::unique_ptr<T>>::type -make_unique(Arg1 &&arg1, Arg2 &&arg2, Arg3 &&arg3, Arg4 &&arg4, Arg5 &&arg5, - Arg6 &&arg6, Arg7 &&arg7, Arg8 &&arg8, Arg9 &&arg9) { - return std::unique_ptr<T>( - new T(std::forward<Arg1>(arg1), std::forward<Arg2>(arg2), - std::forward<Arg3>(arg3), std::forward<Arg4>(arg4), - std::forward<Arg5>(arg5), std::forward<Arg6>(arg6), - std::forward<Arg7>(arg7), std::forward<Arg8>(arg8), - std::forward<Arg9>(arg9))); -} - -template <class T, class Arg1, class Arg2, class Arg3, class Arg4, class Arg5, - class Arg6, class Arg7, class Arg8, class Arg9, class Arg10> -typename std::enable_if<!std::is_array<T>::value, std::unique_ptr<T>>::type -make_unique(Arg1 &&arg1, Arg2 &&arg2, Arg3 &&arg3, Arg4 &&arg4, Arg5 &&arg5, - Arg6 &&arg6, Arg7 &&arg7, Arg8 &&arg8, Arg9 &&arg9, Arg10 &&arg10) { - return std::unique_ptr<T>( - new T(std::forward<Arg1>(arg1), std::forward<Arg2>(arg2), - std::forward<Arg3>(arg3), std::forward<Arg4>(arg4), - std::forward<Arg5>(arg5), std::forward<Arg6>(arg6), - std::forward<Arg7>(arg7), std::forward<Arg8>(arg8), - std::forward<Arg9>(arg9), std::forward<Arg10>(arg10))); -} - -template <class T> -typename std::enable_if<std::is_array<T>::value &&std::extent<T>::value == 0, - std::unique_ptr<T>>::type -make_unique(size_t n) { - return std::unique_ptr<T>(new typename std::remove_extent<T>::type[n]()); -} - -#endif +make_unique(Args &&...) = delete; struct FreeDeleter { void operator()(void* v) { @@ -558,6 +388,35 @@ struct pair_hash { } }; +/// A functor like C++14's std::less<void> in its absence. +struct less { + template <typename A, typename B> bool operator()(A &&a, B &&b) const { + return std::forward<A>(a) < std::forward<B>(b); + } +}; + +/// A functor like C++14's std::equal<void> in its absence. +struct equal { + template <typename A, typename B> bool operator()(A &&a, B &&b) const { + return std::forward<A>(a) == std::forward<B>(b); + } +}; + +/// Binary functor that adapts to any other binary functor after dereferencing +/// operands. +template <typename T> struct deref { + T func; + // Could be further improved to cope with non-derivable functors and + // non-binary functors (should be a variadic template member function + // operator()). + template <typename A, typename B> + auto operator()(A &lhs, B &rhs) const -> decltype(func(*lhs, *rhs)) { + assert(lhs); + assert(rhs); + return func(*lhs, *rhs); + } +}; + } // End llvm namespace #endif diff --git a/include/llvm/ADT/ScopedHashTable.h b/include/llvm/ADT/ScopedHashTable.h index 2f60ecc92043..5abe76c12259 100644 --- a/include/llvm/ADT/ScopedHashTable.h +++ b/include/llvm/ADT/ScopedHashTable.h @@ -90,8 +90,8 @@ class ScopedHashTableScope { /// LastValInScope - This is the last value that was inserted for this scope /// or null if none have been inserted yet. ScopedHashTableVal<K, V> *LastValInScope; - void operator=(ScopedHashTableScope&) LLVM_DELETED_FUNCTION; - ScopedHashTableScope(ScopedHashTableScope&) LLVM_DELETED_FUNCTION; + void operator=(ScopedHashTableScope&) = delete; + ScopedHashTableScope(ScopedHashTableScope&) = delete; public: ScopedHashTableScope(ScopedHashTable<K, V, KInfo, AllocatorTy> &HT); ~ScopedHashTableScope(); diff --git a/include/llvm/ADT/SmallBitVector.h b/include/llvm/ADT/SmallBitVector.h index 1e2f365b1040..ae3d645396fd 100644 --- a/include/llvm/ADT/SmallBitVector.h +++ b/include/llvm/ADT/SmallBitVector.h @@ -53,6 +53,9 @@ class SmallBitVector { SmallNumDataBits = SmallNumRawBits - SmallNumSizeBits }; + static_assert(NumBaseBits == 64 || NumBaseBits == 32, + "Unsupported word size"); + public: typedef unsigned size_type; // Encapsulation of a single bit. @@ -63,6 +66,8 @@ public: public: reference(SmallBitVector &b, unsigned Idx) : TheVector(b), BitPos(Idx) {} + reference(const reference&) = default; + reference& operator=(reference t) { *this = bool(t); return *this; @@ -177,11 +182,7 @@ public: size_type count() const { if (isSmall()) { uintptr_t Bits = getSmallBits(); - if (NumBaseBits == 32) - return CountPopulation_32(Bits); - if (NumBaseBits == 64) - return CountPopulation_64(Bits); - llvm_unreachable("Unsupported!"); + return countPopulation(Bits); } return getPointer()->count(); } @@ -214,11 +215,7 @@ public: uintptr_t Bits = getSmallBits(); if (Bits == 0) return -1; - if (NumBaseBits == 32) - return countTrailingZeros(Bits); - if (NumBaseBits == 64) - return countTrailingZeros(Bits); - llvm_unreachable("Unsupported!"); + return countTrailingZeros(Bits); } return getPointer()->find_first(); } @@ -232,11 +229,7 @@ public: Bits &= ~uintptr_t(0) << (Prev + 1); if (Bits == 0 || Prev + 1 >= getSmallSize()) return -1; - if (NumBaseBits == 32) - return countTrailingZeros(Bits); - if (NumBaseBits == 64) - return countTrailingZeros(Bits); - llvm_unreachable("Unsupported!"); + return countTrailingZeros(Bits); } return getPointer()->find_next(Prev); } @@ -560,7 +553,6 @@ public: private: template<bool AddBits, bool InvertMask> void applyMask(const uint32_t *Mask, unsigned MaskWords) { - assert((NumBaseBits == 64 || NumBaseBits == 32) && "Unsupported word size"); if (NumBaseBits == 64 && MaskWords >= 2) { uint64_t M = Mask[0] | (uint64_t(Mask[1]) << 32); if (InvertMask) M = ~M; diff --git a/include/llvm/ADT/SmallPtrSet.h b/include/llvm/ADT/SmallPtrSet.h index cb1c5e1fa96a..3e3c9c154ef4 100644 --- a/include/llvm/ADT/SmallPtrSet.h +++ b/include/llvm/ADT/SmallPtrSet.h @@ -132,7 +132,7 @@ private: /// Grow - Allocate a larger backing store for the buckets and move it over. void Grow(unsigned NewSize); - void operator=(const SmallPtrSetImplBase &RHS) LLVM_DELETED_FUNCTION; + void operator=(const SmallPtrSetImplBase &RHS) = delete; protected: /// swap - Swaps the elements of two sets. /// Note: This method assumes that both sets have the same small size. @@ -242,7 +242,7 @@ template <typename PtrType> class SmallPtrSetImpl : public SmallPtrSetImplBase { typedef PointerLikeTypeTraits<PtrType> PtrTraits; - SmallPtrSetImpl(const SmallPtrSetImpl&) LLVM_DELETED_FUNCTION; + SmallPtrSetImpl(const SmallPtrSetImpl&) = delete; protected: // Constructors that forward to the base. SmallPtrSetImpl(const void **SmallStorage, const SmallPtrSetImpl &that) diff --git a/include/llvm/ADT/SmallVector.h b/include/llvm/ADT/SmallVector.h index 44a352119b09..5b208b76a21f 100644 --- a/include/llvm/ADT/SmallVector.h +++ b/include/llvm/ADT/SmallVector.h @@ -24,6 +24,7 @@ #include <cstddef> #include <cstdlib> #include <cstring> +#include <initializer_list> #include <iterator> #include <memory> @@ -236,51 +237,6 @@ public: this->setEnd(this->end()-1); this->end()->~T(); } - -#if LLVM_HAS_VARIADIC_TEMPLATES - template <typename... ArgTypes> void emplace_back(ArgTypes &&... Args) { - if (LLVM_UNLIKELY(this->EndX >= this->CapacityX)) - this->grow(); - ::new ((void *)this->end()) T(std::forward<ArgTypes>(Args)...); - this->setEnd(this->end() + 1); - } -#else -private: - template <typename Constructor> void emplace_back_impl(Constructor construct) { - if (LLVM_UNLIKELY(this->EndX >= this->CapacityX)) - this->grow(); - construct((void *)this->end()); - this->setEnd(this->end() + 1); - } - -public: - void emplace_back() { - emplace_back_impl([](void *Mem) { ::new (Mem) T(); }); - } - template <typename T1> void emplace_back(T1 &&A1) { - emplace_back_impl([&](void *Mem) { ::new (Mem) T(std::forward<T1>(A1)); }); - } - template <typename T1, typename T2> void emplace_back(T1 &&A1, T2 &&A2) { - emplace_back_impl([&](void *Mem) { - ::new (Mem) T(std::forward<T1>(A1), std::forward<T2>(A2)); - }); - } - template <typename T1, typename T2, typename T3> - void emplace_back(T1 &&A1, T2 &&A2, T3 &&A3) { - T(std::forward<T1>(A1), std::forward<T2>(A2), std::forward<T3>(A3)); - emplace_back_impl([&](void *Mem) { - ::new (Mem) - T(std::forward<T1>(A1), std::forward<T2>(A2), std::forward<T3>(A3)); - }); - } - template <typename T1, typename T2, typename T3, typename T4> - void emplace_back(T1 &&A1, T2 &&A2, T3 &&A3, T4 &&A4) { - emplace_back_impl([&](void *Mem) { - ::new (Mem) T(std::forward<T1>(A1), std::forward<T2>(A2), - std::forward<T3>(A3), std::forward<T4>(A4)); - }); - } -#endif // LLVM_HAS_VARIADIC_TEMPLATES }; // Define this out-of-line to dissuade the C++ compiler from inlining it. @@ -352,8 +308,11 @@ protected: /// Copy the range [I, E) onto the uninitialized memory /// starting with "Dest", constructing elements into it as needed. - template<typename T1, typename T2> - static void uninitialized_copy(T1 *I, T1 *E, T2 *Dest) { + template <typename T1, typename T2> + static void uninitialized_copy( + T1 *I, T1 *E, T2 *Dest, + typename std::enable_if<std::is_same<typename std::remove_const<T1>::type, + T2>::value>::type * = nullptr) { // Use memcpy for PODs iterated by pointers (which includes SmallVector // iterators): std::uninitialized_copy optimizes to memmove, but we can // use memcpy here. @@ -385,7 +344,7 @@ template <typename T> class SmallVectorImpl : public SmallVectorTemplateBase<T, isPodLike<T>::value> { typedef SmallVectorTemplateBase<T, isPodLike<T>::value > SuperClass; - SmallVectorImpl(const SmallVectorImpl&) LLVM_DELETED_FUNCTION; + SmallVectorImpl(const SmallVectorImpl&) = delete; public: typedef typename SuperClass::iterator iterator; typedef typename SuperClass::size_type size_type; @@ -459,9 +418,7 @@ public: this->grow(this->size()+NumInputs); // Copy the new elements over. - // TODO: NEED To compile time dispatch on whether in_iter is a random access - // iterator to use the fast uninitialized_copy. - std::uninitialized_copy(in_start, in_end, this->end()); + this->uninitialized_copy(in_start, in_end, this->end()); this->setEnd(this->end() + NumInputs); } @@ -476,6 +433,10 @@ public: this->setEnd(this->end() + NumInputs); } + void append(std::initializer_list<T> IL) { + append(IL.begin(), IL.end()); + } + void assign(size_type NumElts, const T &Elt) { clear(); if (this->capacity() < NumElts) @@ -484,6 +445,11 @@ public: std::uninitialized_fill(this->begin(), this->end(), Elt); } + void assign(std::initializer_list<T> IL) { + clear(); + append(IL); + } + iterator erase(iterator I) { assert(I >= this->begin() && "Iterator to erase is out of bounds."); assert(I < this->end() && "Erasing at past-the-end iterator."); @@ -677,6 +643,17 @@ public: return I; } + void insert(iterator I, std::initializer_list<T> IL) { + insert(I, IL.begin(), IL.end()); + } + + template <typename... ArgTypes> void emplace_back(ArgTypes &&... Args) { + if (LLVM_UNLIKELY(this->EndX >= this->CapacityX)) + this->grow(); + ::new ((void *)this->end()) T(std::forward<ArgTypes>(Args)...); + this->setEnd(this->end() + 1); + } + SmallVectorImpl &operator=(const SmallVectorImpl &RHS); SmallVectorImpl &operator=(SmallVectorImpl &&RHS); @@ -902,6 +879,10 @@ public: this->append(R.begin(), R.end()); } + SmallVector(std::initializer_list<T> IL) : SmallVectorImpl<T>(N) { + this->assign(IL); + } + SmallVector(const SmallVector &RHS) : SmallVectorImpl<T>(N) { if (!RHS.empty()) SmallVectorImpl<T>::operator=(RHS); @@ -921,6 +902,21 @@ public: SmallVectorImpl<T>::operator=(::std::move(RHS)); return *this; } + + SmallVector(SmallVectorImpl<T> &&RHS) : SmallVectorImpl<T>(N) { + if (!RHS.empty()) + SmallVectorImpl<T>::operator=(::std::move(RHS)); + } + + const SmallVector &operator=(SmallVectorImpl<T> &&RHS) { + SmallVectorImpl<T>::operator=(::std::move(RHS)); + return *this; + } + + const SmallVector &operator=(std::initializer_list<T> IL) { + this->assign(IL); + return *this; + } }; template<typename T, unsigned N> diff --git a/include/llvm/ADT/SparseBitVector.h b/include/llvm/ADT/SparseBitVector.h index d5bde2963fbd..20cbe2cddfc2 100644 --- a/include/llvm/ADT/SparseBitVector.h +++ b/include/llvm/ADT/SparseBitVector.h @@ -124,25 +124,15 @@ public: size_type count() const { unsigned NumBits = 0; for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i) - if (sizeof(BitWord) == 4) - NumBits += CountPopulation_32(Bits[i]); - else if (sizeof(BitWord) == 8) - NumBits += CountPopulation_64(Bits[i]); - else - llvm_unreachable("Unsupported!"); + NumBits += countPopulation(Bits[i]); return NumBits; } /// find_first - Returns the index of the first set bit. int find_first() const { for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i) - if (Bits[i] != 0) { - if (sizeof(BitWord) == 4) - return i * BITWORD_SIZE + countTrailingZeros(Bits[i]); - if (sizeof(BitWord) == 8) - return i * BITWORD_SIZE + countTrailingZeros(Bits[i]); - llvm_unreachable("Unsupported!"); - } + if (Bits[i] != 0) + return i * BITWORD_SIZE + countTrailingZeros(Bits[i]); llvm_unreachable("Illegal empty element"); } @@ -161,23 +151,13 @@ public: // Mask off previous bits. Copy &= ~0UL << BitPos; - if (Copy != 0) { - if (sizeof(BitWord) == 4) - return WordPos * BITWORD_SIZE + countTrailingZeros(Copy); - if (sizeof(BitWord) == 8) - return WordPos * BITWORD_SIZE + countTrailingZeros(Copy); - llvm_unreachable("Unsupported!"); - } + if (Copy != 0) + return WordPos * BITWORD_SIZE + countTrailingZeros(Copy); // Check subsequent words. for (unsigned i = WordPos+1; i < BITWORDS_PER_ELEMENT; ++i) - if (Bits[i] != 0) { - if (sizeof(BitWord) == 4) - return i * BITWORD_SIZE + countTrailingZeros(Bits[i]); - if (sizeof(BitWord) == 8) - return i * BITWORD_SIZE + countTrailingZeros(Bits[i]); - llvm_unreachable("Unsupported!"); - } + if (Bits[i] != 0) + return i * BITWORD_SIZE + countTrailingZeros(Bits[i]); return -1; } diff --git a/include/llvm/ADT/SparseMultiSet.h b/include/llvm/ADT/SparseMultiSet.h index f858536b6ed8..e3aa2589b79f 100644 --- a/include/llvm/ADT/SparseMultiSet.h +++ b/include/llvm/ADT/SparseMultiSet.h @@ -133,8 +133,8 @@ class SparseMultiSet { // Disable copy construction and assignment. // This data structure is not meant to be used that way. - SparseMultiSet(const SparseMultiSet&) LLVM_DELETED_FUNCTION; - SparseMultiSet &operator=(const SparseMultiSet&) LLVM_DELETED_FUNCTION; + SparseMultiSet(const SparseMultiSet&) = delete; + SparseMultiSet &operator=(const SparseMultiSet&) = delete; /// Whether the given entry is the head of the list. List heads's previous /// pointers are to the tail of the list, allowing for efficient access to the diff --git a/include/llvm/ADT/SparseSet.h b/include/llvm/ADT/SparseSet.h index 9a13440000ac..a45d1c8d6b8a 100644 --- a/include/llvm/ADT/SparseSet.h +++ b/include/llvm/ADT/SparseSet.h @@ -133,8 +133,8 @@ class SparseSet { // Disable copy construction and assignment. // This data structure is not meant to be used that way. - SparseSet(const SparseSet&) LLVM_DELETED_FUNCTION; - SparseSet &operator=(const SparseSet&) LLVM_DELETED_FUNCTION; + SparseSet(const SparseSet&) = delete; + SparseSet &operator=(const SparseSet&) = delete; public: typedef ValueT value_type; diff --git a/include/llvm/ADT/StringMap.h b/include/llvm/ADT/StringMap.h index 3437607a0bd0..8721c73b95b1 100644 --- a/include/llvm/ADT/StringMap.h +++ b/include/llvm/ADT/StringMap.h @@ -111,7 +111,7 @@ public: /// and data. template<typename ValueTy> class StringMapEntry : public StringMapEntryBase { - StringMapEntry(StringMapEntry &E) LLVM_DELETED_FUNCTION; + StringMapEntry(StringMapEntry &E) = delete; public: ValueTy second; diff --git a/include/llvm/ADT/StringRef.h b/include/llvm/ADT/StringRef.h index 6111c42da9dc..95660a49f1f1 100644 --- a/include/llvm/ADT/StringRef.h +++ b/include/llvm/ADT/StringRef.h @@ -238,9 +238,12 @@ namespace llvm { /// \returns The index of the first occurrence of \p C, or npos if not /// found. size_t find(char C, size_t From = 0) const { - for (size_t i = std::min(From, Length), e = Length; i != e; ++i) - if (Data[i] == C) - return i; + size_t FindBegin = std::min(From, Length); + if (FindBegin < Length) { // Avoid calling memchr with nullptr. + // Just forward to memchr, which is faster than a hand-rolled loop. + if (const void *P = ::memchr(Data + FindBegin, C, Length - FindBegin)) + return static_cast<const char *>(P) - Data; + } return npos; } diff --git a/include/llvm/ADT/TinyPtrVector.h b/include/llvm/ADT/TinyPtrVector.h index 15137f5ebf8c..f29608f3d3d1 100644 --- a/include/llvm/ADT/TinyPtrVector.h +++ b/include/llvm/ADT/TinyPtrVector.h @@ -27,9 +27,12 @@ class TinyPtrVector { public: typedef llvm::SmallVector<EltTy, 4> VecTy; typedef typename VecTy::value_type value_type; + typedef llvm::PointerUnion<EltTy, VecTy *> PtrUnion; - llvm::PointerUnion<EltTy, VecTy*> Val; +private: + PtrUnion Val; +public: TinyPtrVector() {} ~TinyPtrVector() { if (VecTy *V = Val.template dyn_cast<VecTy*>()) @@ -96,12 +99,13 @@ public: return *this; } - /// Constructor from a single element. - explicit TinyPtrVector(EltTy Elt) : Val(Elt) {} - /// Constructor from an ArrayRef. + /// + /// This also is a constructor for individual array elements due to the single + /// element constructor for ArrayRef. explicit TinyPtrVector(ArrayRef<EltTy> Elts) - : Val(new VecTy(Elts.begin(), Elts.end())) {} + : Val(Elts.size() == 1 ? PtrUnion(Elts[0]) + : PtrUnion(new VecTy(Elts.begin(), Elts.end()))) {} // implicit conversion operator to ArrayRef. operator ArrayRef<EltTy>() const { @@ -112,6 +116,15 @@ public: return *Val.template get<VecTy*>(); } + // implicit conversion operator to MutableArrayRef. + operator MutableArrayRef<EltTy>() { + if (Val.isNull()) + return None; + if (Val.template is<EltTy>()) + return *Val.getAddrOfPtr1(); + return *Val.template get<VecTy*>(); + } + bool empty() const { // This vector can be empty if it contains no element, or if it // contains a pointer to an empty vector. diff --git a/include/llvm/ADT/Triple.h b/include/llvm/ADT/Triple.h index 8a685995256b..2416ce342c9b 100644 --- a/include/llvm/ADT/Triple.h +++ b/include/llvm/ADT/Triple.h @@ -50,6 +50,7 @@ public: armeb, // ARM (big endian): armeb aarch64, // AArch64 (little endian): aarch64 aarch64_be, // AArch64 (big endian): aarch64_be + bpf, // eBPF or extended BPF or 64-bit BPF (little endian) hexagon, // Hexagon: hexagon mips, // MIPS: mips, mipsallegrex mipsel, // MIPSEL: mipsel, mipsallegrexel @@ -63,6 +64,7 @@ public: amdgcn, // AMDGCN: AMD GCN GPUs sparc, // Sparc: sparc sparcv9, // Sparcv9: Sparcv9 + sparcel, // Sparc: (endianness = little). NB: 'Sparcle' is a CPU variant systemz, // SystemZ: s390x tce, // TCE (http://tce.cs.tut.fi/): tce thumb, // Thumb (little endian): thumb, thumbv.* @@ -80,11 +82,13 @@ public: hsail64, // AMD HSAIL with 64-bit pointers spir, // SPIR: standard portable IR for OpenCL 32-bit version spir64, // SPIR: standard portable IR for OpenCL 64-bit version - kalimba // Kalimba: generic kalimba + kalimba, // Kalimba: generic kalimba + LastArchType = kalimba }; enum SubArchType { NoSubArch, + ARMSubArch_v8_1a, ARMSubArch_v8, ARMSubArch_v7, ARMSubArch_v7em, @@ -92,6 +96,7 @@ public: ARMSubArch_v7s, ARMSubArch_v6, ARMSubArch_v6m, + ARMSubArch_v6k, ARMSubArch_v6t2, ARMSubArch_v5, ARMSubArch_v5te, @@ -114,11 +119,13 @@ public: ImaginationTechnologies, MipsTechnologies, NVIDIA, - CSR + CSR, + LastVendorType = CSR }; enum OSType { UnknownOS, + CloudABI, Darwin, DragonFly, FreeBSD, @@ -140,7 +147,9 @@ public: AIX, CUDA, // NVIDIA CUDA NVCL, // NVIDIA OpenCL - AMDHSA // AMD HSA Runtime + AMDHSA, // AMD HSA Runtime + PS4, + LastOSType = PS4 }; enum EnvironmentType { UnknownEnvironment, @@ -157,6 +166,7 @@ public: MSVC, Itanium, Cygnus, + LastEnvironmentType = Cygnus }; enum ObjectFormatType { UnknownObjectFormat, @@ -200,6 +210,13 @@ public: Triple(const Twine &ArchStr, const Twine &VendorStr, const Twine &OSStr, const Twine &EnvironmentStr); + bool operator==(const Triple &Other) const { + return Arch == Other.Arch && SubArch == Other.SubArch && + Vendor == Other.Vendor && OS == Other.OS && + Environment == Other.Environment && + ObjectFormat == Other.ObjectFormat; + } + /// @} /// @name Normalization /// @{ @@ -210,6 +227,9 @@ public: /// common case in which otherwise valid components are in the wrong order. static std::string normalize(StringRef Str); + /// \brief Return the normalized form of this triple's string. + std::string normalize() const { return normalize(Data); } + /// @} /// @name Typed Component Access /// @{ @@ -334,6 +354,12 @@ public: return false; } + bool isOSVersionLT(const Triple &Other) const { + unsigned RHS[3]; + Other.getOSVersion(RHS[0], RHS[1], RHS[2]); + return isOSVersionLT(RHS[0], RHS[1], RHS[2]); + } + /// isMacOSXVersionLT - Comparison function for checking OS X version /// compatibility, which handles supporting skewed version numbering schemes /// used by the "darwin" triples. @@ -423,7 +449,7 @@ public: /// \brief Tests whether the OS is Windows. bool isOSWindows() const { - return getOS() == Triple::Win32 || isOSCygMing(); + return getOS() == Triple::Win32; } /// \brief Tests whether the OS is NaCl (Native Client) @@ -451,6 +477,19 @@ public: return getObjectFormat() == Triple::MachO; } + /// \brief Tests whether the target is the PS4 CPU + bool isPS4CPU() const { + return getArch() == Triple::x86_64 && + getVendor() == Triple::SCEI && + getOS() == Triple::PS4; + } + + /// \brief Tests whether the target is the PS4 platform + bool isPS4() const { + return getVendor() == Triple::SCEI && + getOS() == Triple::PS4; + } + /// @} /// @name Mutators /// @{ diff --git a/include/llvm/ADT/Twine.h b/include/llvm/ADT/Twine.h index 05d2fea117cf..db0bf4b68de8 100644 --- a/include/llvm/ADT/Twine.h +++ b/include/llvm/ADT/Twine.h @@ -10,6 +10,7 @@ #ifndef LLVM_ADT_TWINE_H #define LLVM_ADT_TWINE_H +#include "llvm/ADT/SmallVector.h" #include "llvm/ADT/StringRef.h" #include "llvm/Support/DataTypes.h" #include "llvm/Support/ErrorHandling.h" @@ -17,9 +18,6 @@ #include <string> namespace llvm { - template <typename T> - class SmallVectorImpl; - class StringRef; class raw_ostream; /// Twine - A lightweight data structure for efficiently representing the @@ -100,6 +98,9 @@ namespace llvm { /// A pointer to a StringRef instance. StringRefKind, + /// A pointer to a SmallString instance. + SmallStringKind, + /// A char value reinterpreted as a pointer, to render as a character. CharKind, @@ -136,6 +137,7 @@ namespace llvm { const char *cString; const std::string *stdString; const StringRef *stringRef; + const SmallVectorImpl<char> *smallString; char character; unsigned int decUI; int decI; @@ -166,50 +168,49 @@ namespace llvm { } /// Construct a binary twine. - explicit Twine(const Twine &_LHS, const Twine &_RHS) - : LHSKind(TwineKind), RHSKind(TwineKind) { - LHS.twine = &_LHS; - RHS.twine = &_RHS; + explicit Twine(const Twine &LHS, const Twine &RHS) + : LHSKind(TwineKind), RHSKind(TwineKind) { + this->LHS.twine = &LHS; + this->RHS.twine = &RHS; assert(isValid() && "Invalid twine!"); } /// Construct a twine from explicit values. - explicit Twine(Child _LHS, NodeKind _LHSKind, - Child _RHS, NodeKind _RHSKind) - : LHS(_LHS), RHS(_RHS), LHSKind(_LHSKind), RHSKind(_RHSKind) { + explicit Twine(Child LHS, NodeKind LHSKind, Child RHS, NodeKind RHSKind) + : LHS(LHS), RHS(RHS), LHSKind(LHSKind), RHSKind(RHSKind) { assert(isValid() && "Invalid twine!"); } /// Since the intended use of twines is as temporary objects, assignments /// when concatenating might cause undefined behavior or stack corruptions - Twine &operator=(const Twine &Other) LLVM_DELETED_FUNCTION; + Twine &operator=(const Twine &Other) = delete; - /// isNull - Check for the null twine. + /// Check for the null twine. bool isNull() const { return getLHSKind() == NullKind; } - /// isEmpty - Check for the empty twine. + /// Check for the empty twine. bool isEmpty() const { return getLHSKind() == EmptyKind; } - /// isNullary - Check if this is a nullary twine (null or empty). + /// Check if this is a nullary twine (null or empty). bool isNullary() const { return isNull() || isEmpty(); } - /// isUnary - Check if this is a unary twine. + /// Check if this is a unary twine. bool isUnary() const { return getRHSKind() == EmptyKind && !isNullary(); } - /// isBinary - Check if this is a binary twine. + /// Check if this is a binary twine. bool isBinary() const { return getLHSKind() != NullKind && getRHSKind() != EmptyKind; } - /// isValid - Check if this is a valid twine (satisfying the invariants on + /// Check if this is a valid twine (satisfying the invariants on /// order and number of arguments). bool isValid() const { // Nullary twines always have Empty on the RHS. @@ -235,16 +236,16 @@ namespace llvm { return true; } - /// getLHSKind - Get the NodeKind of the left-hand side. + /// Get the NodeKind of the left-hand side. NodeKind getLHSKind() const { return LHSKind; } - /// getRHSKind - Get the NodeKind of the right-hand side. + /// Get the NodeKind of the right-hand side. NodeKind getRHSKind() const { return RHSKind; } - /// printOneChild - Print one child from a twine. + /// Print one child from a twine. void printOneChild(raw_ostream &OS, Child Ptr, NodeKind Kind) const; - /// printOneChildRepr - Print the representation of one child from a twine. + /// Print the representation of one child from a twine. void printOneChildRepr(raw_ostream &OS, Child Ptr, NodeKind Kind) const; @@ -257,6 +258,8 @@ namespace llvm { assert(isValid() && "Invalid twine!"); } + Twine(const Twine &) = default; + /// Construct from a C string. /// /// We take care here to optimize "" into the empty twine -- this will be @@ -287,6 +290,13 @@ namespace llvm { assert(isValid() && "Invalid twine!"); } + /// Construct from a SmallString. + /*implicit*/ Twine(const SmallVectorImpl<char> &Str) + : LHSKind(SmallStringKind), RHSKind(EmptyKind) { + LHS.smallString = &Str; + assert(isValid() && "Invalid twine!"); + } + /// Construct from a char. explicit Twine(char Val) : LHSKind(CharKind), RHSKind(EmptyKind) { @@ -347,18 +357,18 @@ namespace llvm { // right thing. Yet. /// Construct as the concatenation of a C string and a StringRef. - /*implicit*/ Twine(const char *_LHS, const StringRef &_RHS) - : LHSKind(CStringKind), RHSKind(StringRefKind) { - LHS.cString = _LHS; - RHS.stringRef = &_RHS; + /*implicit*/ Twine(const char *LHS, const StringRef &RHS) + : LHSKind(CStringKind), RHSKind(StringRefKind) { + this->LHS.cString = LHS; + this->RHS.stringRef = &RHS; assert(isValid() && "Invalid twine!"); } /// Construct as the concatenation of a StringRef and a C string. - /*implicit*/ Twine(const StringRef &_LHS, const char *_RHS) - : LHSKind(StringRefKind), RHSKind(CStringKind) { - LHS.stringRef = &_LHS; - RHS.cString = _RHS; + /*implicit*/ Twine(const StringRef &LHS, const char *RHS) + : LHSKind(StringRefKind), RHSKind(CStringKind) { + this->LHS.stringRef = &LHS; + this->RHS.cString = RHS; assert(isValid() && "Invalid twine!"); } @@ -384,14 +394,14 @@ namespace llvm { /// @name Predicate Operations /// @{ - /// isTriviallyEmpty - Check if this twine is trivially empty; a false - /// return value does not necessarily mean the twine is empty. + /// Check if this twine is trivially empty; a false return value does not + /// necessarily mean the twine is empty. bool isTriviallyEmpty() const { return isNullary(); } - /// isSingleStringRef - Return true if this twine can be dynamically - /// accessed as a single StringRef value with getSingleStringRef(). + /// Return true if this twine can be dynamically accessed as a single + /// StringRef value with getSingleStringRef(). bool isSingleStringRef() const { if (getRHSKind() != EmptyKind) return false; @@ -400,6 +410,7 @@ namespace llvm { case CStringKind: case StdStringKind: case StringRefKind: + case SmallStringKind: return true; default: return false; @@ -416,15 +427,14 @@ namespace llvm { /// @name Output & Conversion. /// @{ - /// str - Return the twine contents as a std::string. + /// Return the twine contents as a std::string. std::string str() const; - /// toVector - Write the concatenated string into the given SmallString or - /// SmallVector. + /// Append the concatenated string into the given SmallString or SmallVector. void toVector(SmallVectorImpl<char> &Out) const; - /// getSingleStringRef - This returns the twine as a single StringRef. This - /// method is only valid if isSingleStringRef() is true. + /// This returns the twine as a single StringRef. This method is only valid + /// if isSingleStringRef() is true. StringRef getSingleStringRef() const { assert(isSingleStringRef() &&"This cannot be had as a single stringref!"); switch (getLHSKind()) { @@ -433,18 +443,24 @@ namespace llvm { case CStringKind: return StringRef(LHS.cString); case StdStringKind: return StringRef(*LHS.stdString); case StringRefKind: return *LHS.stringRef; + case SmallStringKind: + return StringRef(LHS.smallString->data(), LHS.smallString->size()); } } - /// toStringRef - This returns the twine as a single StringRef if it can be + /// This returns the twine as a single StringRef if it can be /// represented as such. Otherwise the twine is written into the given /// SmallVector and a StringRef to the SmallVector's data is returned. - StringRef toStringRef(SmallVectorImpl<char> &Out) const; + StringRef toStringRef(SmallVectorImpl<char> &Out) const { + if (isSingleStringRef()) + return getSingleStringRef(); + toVector(Out); + return StringRef(Out.data(), Out.size()); + } - /// toNullTerminatedStringRef - This returns the twine as a single null - /// terminated StringRef if it can be represented as such. Otherwise the - /// twine is written into the given SmallVector and a StringRef to the - /// SmallVector's data is returned. + /// This returns the twine as a single null terminated StringRef if it + /// can be represented as such. Otherwise the twine is written into the + /// given SmallVector and a StringRef to the SmallVector's data is returned. /// /// The returned StringRef's size does not include the null terminator. StringRef toNullTerminatedStringRef(SmallVectorImpl<char> &Out) const; diff --git a/include/llvm/ADT/edit_distance.h b/include/llvm/ADT/edit_distance.h index 9ee1edc54e05..c2b2041242aa 100644 --- a/include/llvm/ADT/edit_distance.h +++ b/include/llvm/ADT/edit_distance.h @@ -50,7 +50,7 @@ unsigned ComputeEditDistance(ArrayRef<T> FromArray, ArrayRef<T> ToArray, // http://en.wikipedia.org/wiki/Levenshtein_distance // // Although the algorithm is typically described using an m x n - // array, only two rows are used at a time, so this implemenation + // array, only two rows are used at a time, so this implementation // just keeps two separate vectors for those two rows. typename ArrayRef<T>::size_type m = FromArray.size(); typename ArrayRef<T>::size_type n = ToArray.size(); diff --git a/include/llvm/ADT/ilist.h b/include/llvm/ADT/ilist.h index 8c19a6f4547a..a7b9306b3a73 100644 --- a/include/llvm/ADT/ilist.h +++ b/include/llvm/ADT/ilist.h @@ -237,14 +237,14 @@ public: // These are to catch errors when people try to use them as random access // iterators. template<typename T> -void operator-(int, ilist_iterator<T>) LLVM_DELETED_FUNCTION; +void operator-(int, ilist_iterator<T>) = delete; template<typename T> -void operator-(ilist_iterator<T>,int) LLVM_DELETED_FUNCTION; +void operator-(ilist_iterator<T>,int) = delete; template<typename T> -void operator+(int, ilist_iterator<T>) LLVM_DELETED_FUNCTION; +void operator+(int, ilist_iterator<T>) = delete; template<typename T> -void operator+(ilist_iterator<T>,int) LLVM_DELETED_FUNCTION; +void operator+(ilist_iterator<T>,int) = delete; // operator!=/operator== - Allow mixed comparisons without dereferencing // the iterator, which could very likely be pointing to end(). @@ -332,8 +332,8 @@ class iplist : public Traits { // No fundamental reason why iplist can't be copyable, but the default // copy/copy-assign won't do. - iplist(const iplist &) LLVM_DELETED_FUNCTION; - void operator=(const iplist &) LLVM_DELETED_FUNCTION; + iplist(const iplist &) = delete; + void operator=(const iplist &) = delete; public: typedef NodeTy *pointer; diff --git a/include/llvm/ADT/iterator.h b/include/llvm/ADT/iterator.h index e2c9e5ea6bda..54a288df0173 100644 --- a/include/llvm/ADT/iterator.h +++ b/include/llvm/ADT/iterator.h @@ -150,7 +150,7 @@ class iterator_adaptor_base protected: WrappedIteratorT I; - iterator_adaptor_base() {} + iterator_adaptor_base() = default; template <typename U> explicit iterator_adaptor_base( @@ -231,7 +231,7 @@ struct pointee_iterator pointee_iterator<WrappedIteratorT>, WrappedIteratorT, typename std::iterator_traits<WrappedIteratorT>::iterator_category, T> { - pointee_iterator() {} + pointee_iterator() = default; template <typename U> pointee_iterator(U &&u) : pointee_iterator::iterator_adaptor_base(std::forward<U &&>(u)) {} |