diff options
Diffstat (limited to 'include/llvm/ADT')
33 files changed, 720 insertions, 380 deletions
diff --git a/include/llvm/ADT/APFloat.h b/include/llvm/ADT/APFloat.h index 50f1463d7eaa..26aae773624c 100644 --- a/include/llvm/ADT/APFloat.h +++ b/include/llvm/ADT/APFloat.h @@ -304,6 +304,38 @@ public: /// IEEE-754R 5.3.1: nextUp/nextDown. opStatus next(bool nextDown); + /// \brief Operator+ overload which provides the default + /// \c nmNearestTiesToEven rounding mode and *no* error checking. + APFloat operator+(const APFloat &RHS) const { + APFloat Result = *this; + Result.add(RHS, rmNearestTiesToEven); + return Result; + } + + /// \brief Operator- overload which provides the default + /// \c nmNearestTiesToEven rounding mode and *no* error checking. + APFloat operator-(const APFloat &RHS) const { + APFloat Result = *this; + Result.subtract(RHS, rmNearestTiesToEven); + return Result; + } + + /// \brief Operator* overload which provides the default + /// \c nmNearestTiesToEven rounding mode and *no* error checking. + APFloat operator*(const APFloat &RHS) const { + APFloat Result = *this; + Result.multiply(RHS, rmNearestTiesToEven); + return Result; + } + + /// \brief Operator/ overload which provides the default + /// \c nmNearestTiesToEven rounding mode and *no* error checking. + APFloat operator/(const APFloat &RHS) const { + APFloat Result = *this; + Result.divide(RHS, rmNearestTiesToEven); + return Result; + } + /// @} /// \name Sign operations. @@ -313,6 +345,13 @@ public: void clearSign(); void copySign(const APFloat &); + /// \brief A static helper to produce a copy of an APFloat value with its sign + /// copied from some other APFloat. + static APFloat copySign(APFloat Value, const APFloat &Sign) { + Value.copySign(Sign); + return std::move(Value); + } + /// @} /// \name Conversions @@ -452,6 +491,36 @@ public: /// return true. bool getExactInverse(APFloat *inv) const; + /// \brief Enumeration of \c ilogb error results. + enum IlogbErrorKinds { + IEK_Zero = INT_MIN+1, + IEK_NaN = INT_MIN, + IEK_Inf = INT_MAX + }; + + /// \brief Returns the exponent of the internal representation of the APFloat. + /// + /// Because the radix of APFloat is 2, this is equivalent to floor(log2(x)). + /// For special APFloat values, this returns special error codes: + /// + /// NaN -> \c IEK_NaN + /// 0 -> \c IEK_Zero + /// Inf -> \c IEK_Inf + /// + friend int ilogb(const APFloat &Arg) { + if (Arg.isNaN()) + return IEK_NaN; + if (Arg.isZero()) + return IEK_Zero; + if (Arg.isInfinity()) + return IEK_Inf; + + return Arg.exponent; + } + + /// \brief Returns: X * 2^Exp for integral exponents. + friend APFloat scalbn(APFloat X, int Exp); + private: /// \name Simple Queries @@ -573,11 +642,41 @@ private: unsigned int sign : 1; }; -/// See friend declaration above. +/// See friend declarations above. /// -/// This additional declaration is required in order to compile LLVM with IBM +/// These additional declarations are required in order to compile LLVM with IBM /// xlC compiler. hash_code hash_value(const APFloat &Arg); +APFloat scalbn(APFloat X, int Exp); + +/// \brief Returns the absolute value of the argument. +inline APFloat abs(APFloat X) { + X.clearSign(); + return X; +} + +/// Implements IEEE minNum semantics. Returns the smaller of the 2 arguments if +/// both are not NaN. If either argument is a NaN, returns the other argument. +LLVM_READONLY +inline APFloat minnum(const APFloat &A, const APFloat &B) { + if (A.isNaN()) + return B; + if (B.isNaN()) + return A; + return (B.compare(A) == APFloat::cmpLessThan) ? B : A; +} + +/// Implements IEEE maxNum semantics. Returns the larger of the 2 arguments if +/// both are not NaN. If either argument is a NaN, returns the other argument. +LLVM_READONLY +inline APFloat maxnum(const APFloat &A, const APFloat &B) { + if (A.isNaN()) + return B; + if (B.isNaN()) + return A; + return (A.compare(B) == APFloat::cmpLessThan) ? B : A; +} + } // namespace llvm #endif // LLVM_ADT_APFLOAT_H diff --git a/include/llvm/ADT/APInt.h b/include/llvm/ADT/APInt.h index aa3c3f67ec10..025397d9ce45 100644 --- a/include/llvm/ADT/APInt.h +++ b/include/llvm/ADT/APInt.h @@ -91,6 +91,8 @@ class APInt { APINT_WORD_SIZE = static_cast<unsigned int>(sizeof(uint64_t)) }; + friend struct DenseMapAPIntKeyInfo; + /// \brief Fast internal constructor /// /// This constructor is used only internally for speed of construction of @@ -277,7 +279,6 @@ public: /// Simply makes *this a copy of that. /// @brief Copy Constructor. APInt(const APInt &that) : BitWidth(that.BitWidth), VAL(0) { - assert(BitWidth && "bitwidth too small"); if (isSingleWord()) VAL = that.VAL; else @@ -656,13 +657,24 @@ public: /// @brief Move assignment operator. APInt &operator=(APInt &&that) { - if (!isSingleWord()) + if (!isSingleWord()) { + // The MSVC STL shipped in 2013 requires that self move assignment be a + // no-op. Otherwise algorithms like stable_sort will produce answers + // where half of the output is left in a moved-from state. + if (this == &that) + return *this; delete[] pVal; + } - BitWidth = that.BitWidth; - VAL = that.VAL; + // Use memcpy so that type based alias analysis sees both VAL and pVal + // as modified. + memcpy(&VAL, &that.VAL, sizeof(uint64_t)); + // If 'this == &that', avoid zeroing our own bitwidth by storing to 'that' + // first. + unsigned ThatBitWidth = that.BitWidth; that.BitWidth = 0; + BitWidth = ThatBitWidth; return *this; } @@ -936,7 +948,8 @@ public: APInt sdiv_ov(const APInt &RHS, bool &Overflow) const; APInt smul_ov(const APInt &RHS, bool &Overflow) const; APInt umul_ov(const APInt &RHS, bool &Overflow) const; - APInt sshl_ov(unsigned Amt, bool &Overflow) const; + APInt sshl_ov(const APInt &Amt, bool &Overflow) const; + APInt ushl_ov(const APInt &Amt, bool &Overflow) const; /// \brief Array-indexing support. /// diff --git a/include/llvm/ADT/APSInt.h b/include/llvm/ADT/APSInt.h index ee34e9b53088..a6693f7992cd 100644 --- a/include/llvm/ADT/APSInt.h +++ b/include/llvm/ADT/APSInt.h @@ -269,19 +269,15 @@ public: else if (I2.getBitWidth() > I1.getBitWidth()) return isSameValue(I1.extend(I2.getBitWidth()), I2); - // We have a signedness mismatch. Turn the signed value into an unsigned - // value. - if (I1.isSigned()) { - if (I1.isNegative()) - return false; + assert(I1.isSigned() != I2.isSigned()); - return APSInt(I1, true) == I2; - } - - if (I2.isNegative()) + // 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; - return I1 == APSInt(I2, true); + return I1.eq(I2); } /// Profile - Used to insert APSInt objects, or objects that contain APSInt diff --git a/include/llvm/ADT/ArrayRef.h b/include/llvm/ADT/ArrayRef.h index 0fff505d8d01..8c14a423c8f5 100644 --- a/include/llvm/ADT/ArrayRef.h +++ b/include/llvm/ADT/ArrayRef.h @@ -11,6 +11,7 @@ #define LLVM_ADT_ARRAYREF_H #include "llvm/ADT/None.h" +#include "llvm/ADT/STLExtras.h" #include "llvm/ADT/SmallVector.h" #include <vector> @@ -43,6 +44,19 @@ 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 /// @{ @@ -90,6 +104,14 @@ namespace llvm { 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. + template <typename U> + ArrayRef(const ArrayRef<U *> &A, + typename std::enable_if< + std::is_convertible<U *const *, T const *>::value>::type* = 0) + : Data(A.data()), Length(A.size()) {} + /// @} /// @name Simple Operations /// @{ @@ -131,7 +153,13 @@ namespace llvm { bool equals(ArrayRef RHS) const { if (Length != RHS.Length) return false; - return std::equal(begin(), end(), RHS.begin()); + // 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; } /// slice(n) - Chop off the first N elements of the array. @@ -176,6 +204,47 @@ 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 34e2284311b3..a40f694485bf 100644 --- a/include/llvm/ADT/BitVector.h +++ b/include/llvm/ADT/BitVector.h @@ -239,6 +239,7 @@ public: } BitVector &set(unsigned Idx) { + assert(Bits && "Bits never allocated"); Bits[Idx / BITWORD_SIZE] |= BitWord(1) << (Idx % BITWORD_SIZE); return *this; } @@ -450,6 +451,7 @@ public: // Grow the bitvector to have enough elements. Capacity = RHSWords; + assert(Capacity > 0 && "negative capacity?"); BitWord *NewBits = (BitWord *)std::malloc(Capacity * sizeof(BitWord)); std::memcpy(NewBits, RHS.Bits, Capacity * sizeof(BitWord)); @@ -545,6 +547,7 @@ private: void grow(unsigned NewSize) { Capacity = std::max(NumBitWords(NewSize), Capacity * 2); + assert(Capacity > 0 && "realloc-ing zero space"); Bits = (BitWord *)std::realloc(Bits, Capacity * sizeof(BitWord)); clear_unused_bits(); diff --git a/include/llvm/ADT/DenseMap.h b/include/llvm/ADT/DenseMap.h index 85f37b9051b1..050f8ac150dd 100644 --- a/include/llvm/ADT/DenseMap.h +++ b/include/llvm/ADT/DenseMap.h @@ -31,26 +31,35 @@ namespace llvm { -template<typename KeyT, typename ValueT, - typename KeyInfoT = DenseMapInfo<KeyT>, - bool IsConst = false> +namespace detail { +// We extend a pair to allow users to override the bucket type with their own +// implementation without requiring two members. +template <typename KeyT, typename ValueT> +struct DenseMapPair : public std::pair<KeyT, ValueT> { + KeyT &getFirst() { return std::pair<KeyT, ValueT>::first; } + const KeyT &getFirst() const { return std::pair<KeyT, ValueT>::first; } + ValueT &getSecond() { return std::pair<KeyT, ValueT>::second; } + const ValueT &getSecond() const { return std::pair<KeyT, ValueT>::second; } +}; +} + +template < + typename KeyT, typename ValueT, typename KeyInfoT = DenseMapInfo<KeyT>, + typename Bucket = detail::DenseMapPair<KeyT, ValueT>, bool IsConst = false> class DenseMapIterator; -template<typename DerivedT, - typename KeyT, typename ValueT, typename KeyInfoT> +template <typename DerivedT, typename KeyT, typename ValueT, typename KeyInfoT, + typename BucketT> class DenseMapBase { -protected: - typedef std::pair<KeyT, ValueT> BucketT; - public: typedef unsigned size_type; typedef KeyT key_type; typedef ValueT mapped_type; typedef BucketT value_type; - typedef DenseMapIterator<KeyT, ValueT, KeyInfoT> iterator; - typedef DenseMapIterator<KeyT, ValueT, - KeyInfoT, true> const_iterator; + typedef DenseMapIterator<KeyT, ValueT, KeyInfoT, BucketT> iterator; + typedef DenseMapIterator<KeyT, ValueT, KeyInfoT, BucketT, true> + const_iterator; inline iterator begin() { // When the map is empty, avoid the overhead of AdvancePastEmptyBuckets(). return empty() ? end() : iterator(getBuckets(), getBucketsEnd()); @@ -88,12 +97,12 @@ public: const KeyT EmptyKey = getEmptyKey(), TombstoneKey = getTombstoneKey(); for (BucketT *P = getBuckets(), *E = getBucketsEnd(); P != E; ++P) { - if (!KeyInfoT::isEqual(P->first, EmptyKey)) { - if (!KeyInfoT::isEqual(P->first, TombstoneKey)) { - P->second.~ValueT(); + if (!KeyInfoT::isEqual(P->getFirst(), EmptyKey)) { + if (!KeyInfoT::isEqual(P->getFirst(), TombstoneKey)) { + P->getSecond().~ValueT(); decrementNumEntries(); } - P->first = EmptyKey; + P->getFirst() = EmptyKey; } } assert(getNumEntries() == 0 && "Node count imbalance!"); @@ -144,7 +153,7 @@ public: ValueT lookup(const KeyT &Val) const { const BucketT *TheBucket; if (LookupBucketFor(Val, TheBucket)) - return TheBucket->second; + return TheBucket->getSecond(); return ValueT(); } @@ -191,16 +200,16 @@ public: if (!LookupBucketFor(Val, TheBucket)) return false; // not in map. - TheBucket->second.~ValueT(); - TheBucket->first = getTombstoneKey(); + TheBucket->getSecond().~ValueT(); + TheBucket->getFirst() = getTombstoneKey(); decrementNumEntries(); incrementNumTombstones(); return true; } void erase(iterator I) { BucketT *TheBucket = &*I; - TheBucket->second.~ValueT(); - TheBucket->first = getTombstoneKey(); + TheBucket->getSecond().~ValueT(); + TheBucket->getFirst() = getTombstoneKey(); decrementNumEntries(); incrementNumTombstones(); } @@ -250,10 +259,10 @@ protected: const KeyT EmptyKey = getEmptyKey(), TombstoneKey = getTombstoneKey(); for (BucketT *P = getBuckets(), *E = getBucketsEnd(); P != E; ++P) { - if (!KeyInfoT::isEqual(P->first, EmptyKey) && - !KeyInfoT::isEqual(P->first, TombstoneKey)) - P->second.~ValueT(); - P->first.~KeyT(); + if (!KeyInfoT::isEqual(P->getFirst(), EmptyKey) && + !KeyInfoT::isEqual(P->getFirst(), TombstoneKey)) + P->getSecond().~ValueT(); + P->getFirst().~KeyT(); } #ifndef NDEBUG @@ -269,7 +278,7 @@ protected: "# initial buckets must be a power of two!"); const KeyT EmptyKey = getEmptyKey(); for (BucketT *B = getBuckets(), *E = getBucketsEnd(); B != E; ++B) - new (&B->first) KeyT(EmptyKey); + new (&B->getFirst()) KeyT(EmptyKey); } void moveFromOldBuckets(BucketT *OldBucketsBegin, BucketT *OldBucketsEnd) { @@ -279,21 +288,21 @@ protected: const KeyT EmptyKey = getEmptyKey(); const KeyT TombstoneKey = getTombstoneKey(); for (BucketT *B = OldBucketsBegin, *E = OldBucketsEnd; B != E; ++B) { - if (!KeyInfoT::isEqual(B->first, EmptyKey) && - !KeyInfoT::isEqual(B->first, TombstoneKey)) { + if (!KeyInfoT::isEqual(B->getFirst(), EmptyKey) && + !KeyInfoT::isEqual(B->getFirst(), TombstoneKey)) { // Insert the key/value into the new table. BucketT *DestBucket; - bool FoundVal = LookupBucketFor(B->first, DestBucket); + bool FoundVal = LookupBucketFor(B->getFirst(), DestBucket); (void)FoundVal; // silence warning. assert(!FoundVal && "Key already in new map?"); - DestBucket->first = std::move(B->first); - new (&DestBucket->second) ValueT(std::move(B->second)); + DestBucket->getFirst() = std::move(B->getFirst()); + new (&DestBucket->getSecond()) ValueT(std::move(B->getSecond())); incrementNumEntries(); // Free the value. - B->second.~ValueT(); + B->getSecond().~ValueT(); } - B->first.~KeyT(); + B->getFirst().~KeyT(); } #ifndef NDEBUG @@ -304,7 +313,9 @@ protected: } template <typename OtherBaseT> - void copyFrom(const DenseMapBase<OtherBaseT, KeyT, ValueT, KeyInfoT>& other) { + void copyFrom( + const DenseMapBase<OtherBaseT, KeyT, ValueT, KeyInfoT, BucketT> &other) { + assert(&other != this); assert(getNumBuckets() == other.getNumBuckets()); setNumEntries(other.getNumEntries()); @@ -315,10 +326,12 @@ protected: getNumBuckets() * sizeof(BucketT)); else for (size_t i = 0; i < getNumBuckets(); ++i) { - new (&getBuckets()[i].first) KeyT(other.getBuckets()[i].first); - if (!KeyInfoT::isEqual(getBuckets()[i].first, getEmptyKey()) && - !KeyInfoT::isEqual(getBuckets()[i].first, getTombstoneKey())) - new (&getBuckets()[i].second) ValueT(other.getBuckets()[i].second); + new (&getBuckets()[i].getFirst()) + KeyT(other.getBuckets()[i].getFirst()); + if (!KeyInfoT::isEqual(getBuckets()[i].getFirst(), getEmptyKey()) && + !KeyInfoT::isEqual(getBuckets()[i].getFirst(), getTombstoneKey())) + new (&getBuckets()[i].getSecond()) + ValueT(other.getBuckets()[i].getSecond()); } } @@ -395,8 +408,8 @@ private: BucketT *TheBucket) { TheBucket = InsertIntoBucketImpl(Key, TheBucket); - TheBucket->first = Key; - new (&TheBucket->second) ValueT(Value); + TheBucket->getFirst() = Key; + new (&TheBucket->getSecond()) ValueT(Value); return TheBucket; } @@ -404,16 +417,16 @@ private: BucketT *TheBucket) { TheBucket = InsertIntoBucketImpl(Key, TheBucket); - TheBucket->first = Key; - new (&TheBucket->second) ValueT(std::move(Value)); + TheBucket->getFirst() = Key; + new (&TheBucket->getSecond()) ValueT(std::move(Value)); return TheBucket; } BucketT *InsertIntoBucket(KeyT &&Key, ValueT &&Value, BucketT *TheBucket) { TheBucket = InsertIntoBucketImpl(Key, TheBucket); - TheBucket->first = std::move(Key); - new (&TheBucket->second) ValueT(std::move(Value)); + TheBucket->getFirst() = std::move(Key); + new (&TheBucket->getSecond()) ValueT(std::move(Value)); return TheBucket; } @@ -445,7 +458,7 @@ private: // If we are writing over a tombstone, remember this. const KeyT EmptyKey = getEmptyKey(); - if (!KeyInfoT::isEqual(TheBucket->first, EmptyKey)) + if (!KeyInfoT::isEqual(TheBucket->getFirst(), EmptyKey)) decrementNumTombstones(); return TheBucket; @@ -479,14 +492,14 @@ private: while (1) { const BucketT *ThisBucket = BucketsPtr + BucketNo; // Found Val's bucket? If so, return it. - if (KeyInfoT::isEqual(Val, ThisBucket->first)) { + if (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->first, EmptyKey)) { + if (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; @@ -495,7 +508,8 @@ private: // If this is a tombstone, remember it. If Val ends up not in the map, we // prefer to return it than something that would require more probing. - if (KeyInfoT::isEqual(ThisBucket->first, TombstoneKey) && !FoundTombstone) + if (KeyInfoT::isEqual(ThisBucket->getFirst(), TombstoneKey) && + !FoundTombstone) FoundTombstone = ThisBucket; // Remember the first tombstone found. // Otherwise, it's a hash collision or a tombstone, continue quadratic @@ -524,16 +538,15 @@ public: } }; -template<typename KeyT, typename ValueT, - typename KeyInfoT = DenseMapInfo<KeyT> > -class DenseMap - : public DenseMapBase<DenseMap<KeyT, ValueT, KeyInfoT>, - KeyT, ValueT, KeyInfoT> { +template <typename KeyT, typename ValueT, + typename KeyInfoT = DenseMapInfo<KeyT>, + typename BucketT = detail::DenseMapPair<KeyT, ValueT>> +class DenseMap : public DenseMapBase<DenseMap<KeyT, ValueT, KeyInfoT, BucketT>, + KeyT, ValueT, KeyInfoT, BucketT> { // Lift some types from the dependent base class into this class for // simplicity of referring to them. - typedef DenseMapBase<DenseMap, KeyT, ValueT, KeyInfoT> BaseT; - typedef typename BaseT::BucketT BucketT; - friend class DenseMapBase<DenseMap, KeyT, ValueT, KeyInfoT>; + typedef DenseMapBase<DenseMap, KeyT, ValueT, KeyInfoT, BucketT> BaseT; + friend class DenseMapBase<DenseMap, KeyT, ValueT, KeyInfoT, BucketT>; BucketT *Buckets; unsigned NumEntries; @@ -574,7 +587,8 @@ public: } DenseMap& operator=(const DenseMap& other) { - copyFrom(other); + if (&other != this) + copyFrom(other); return *this; } @@ -675,17 +689,17 @@ private: } }; -template<typename KeyT, typename ValueT, - unsigned InlineBuckets = 4, - typename KeyInfoT = DenseMapInfo<KeyT> > +template <typename KeyT, typename ValueT, unsigned InlineBuckets = 4, + typename KeyInfoT = DenseMapInfo<KeyT>, + typename BucketT = detail::DenseMapPair<KeyT, ValueT>> class SmallDenseMap - : public DenseMapBase<SmallDenseMap<KeyT, ValueT, InlineBuckets, KeyInfoT>, - KeyT, ValueT, KeyInfoT> { + : public DenseMapBase< + SmallDenseMap<KeyT, ValueT, InlineBuckets, KeyInfoT, BucketT>, KeyT, + ValueT, KeyInfoT, BucketT> { // Lift some types from the dependent base class into this class for // simplicity of referring to them. - typedef DenseMapBase<SmallDenseMap, KeyT, ValueT, KeyInfoT> BaseT; - typedef typename BaseT::BucketT BucketT; - friend class DenseMapBase<SmallDenseMap, KeyT, ValueT, KeyInfoT>; + typedef DenseMapBase<SmallDenseMap, KeyT, ValueT, KeyInfoT, BucketT> BaseT; + friend class DenseMapBase<SmallDenseMap, KeyT, ValueT, KeyInfoT, BucketT>; unsigned Small : 1; unsigned NumEntries : 31; @@ -742,23 +756,23 @@ public: for (unsigned i = 0, e = InlineBuckets; i != e; ++i) { BucketT *LHSB = &getInlineBuckets()[i], *RHSB = &RHS.getInlineBuckets()[i]; - bool hasLHSValue = (!KeyInfoT::isEqual(LHSB->first, EmptyKey) && - !KeyInfoT::isEqual(LHSB->first, TombstoneKey)); - bool hasRHSValue = (!KeyInfoT::isEqual(RHSB->first, EmptyKey) && - !KeyInfoT::isEqual(RHSB->first, TombstoneKey)); + bool hasLHSValue = (!KeyInfoT::isEqual(LHSB->getFirst(), EmptyKey) && + !KeyInfoT::isEqual(LHSB->getFirst(), TombstoneKey)); + bool hasRHSValue = (!KeyInfoT::isEqual(RHSB->getFirst(), EmptyKey) && + !KeyInfoT::isEqual(RHSB->getFirst(), TombstoneKey)); if (hasLHSValue && hasRHSValue) { // Swap together if we can... std::swap(*LHSB, *RHSB); continue; } // Swap separately and handle any assymetry. - std::swap(LHSB->first, RHSB->first); + std::swap(LHSB->getFirst(), RHSB->getFirst()); if (hasLHSValue) { - new (&RHSB->second) ValueT(std::move(LHSB->second)); - LHSB->second.~ValueT(); + new (&RHSB->getSecond()) ValueT(std::move(LHSB->getSecond())); + LHSB->getSecond().~ValueT(); } else if (hasRHSValue) { - new (&LHSB->second) ValueT(std::move(RHSB->second)); - RHSB->second.~ValueT(); + new (&LHSB->getSecond()) ValueT(std::move(RHSB->getSecond())); + RHSB->getSecond().~ValueT(); } } return; @@ -783,12 +797,12 @@ public: for (unsigned i = 0, e = InlineBuckets; i != e; ++i) { BucketT *NewB = &LargeSide.getInlineBuckets()[i], *OldB = &SmallSide.getInlineBuckets()[i]; - new (&NewB->first) KeyT(std::move(OldB->first)); - OldB->first.~KeyT(); - if (!KeyInfoT::isEqual(NewB->first, EmptyKey) && - !KeyInfoT::isEqual(NewB->first, TombstoneKey)) { - new (&NewB->second) ValueT(std::move(OldB->second)); - OldB->second.~ValueT(); + new (&NewB->getFirst()) KeyT(std::move(OldB->getFirst())); + OldB->getFirst().~KeyT(); + if (!KeyInfoT::isEqual(NewB->getFirst(), EmptyKey) && + !KeyInfoT::isEqual(NewB->getFirst(), TombstoneKey)) { + new (&NewB->getSecond()) ValueT(std::move(OldB->getSecond())); + OldB->getSecond().~ValueT(); } } @@ -799,7 +813,8 @@ public: } SmallDenseMap& operator=(const SmallDenseMap& other) { - copyFrom(other); + if (&other != this) + copyFrom(other); return *this; } @@ -849,16 +864,16 @@ public: const KeyT EmptyKey = this->getEmptyKey(); const KeyT TombstoneKey = this->getTombstoneKey(); for (BucketT *P = getBuckets(), *E = P + InlineBuckets; P != E; ++P) { - if (!KeyInfoT::isEqual(P->first, EmptyKey) && - !KeyInfoT::isEqual(P->first, TombstoneKey)) { + if (!KeyInfoT::isEqual(P->getFirst(), EmptyKey) && + !KeyInfoT::isEqual(P->getFirst(), TombstoneKey)) { assert(size_t(TmpEnd - TmpBegin) < InlineBuckets && "Too many inline buckets!"); - new (&TmpEnd->first) KeyT(std::move(P->first)); - new (&TmpEnd->second) ValueT(std::move(P->second)); + new (&TmpEnd->getFirst()) KeyT(std::move(P->getFirst())); + new (&TmpEnd->getSecond()) ValueT(std::move(P->getSecond())); ++TmpEnd; - P->second.~ValueT(); + P->getSecond().~ValueT(); } - P->first.~KeyT(); + P->getFirst().~KeyT(); } // Now make this map use the large rep, and move all the entries back @@ -969,13 +984,12 @@ private: } }; -template<typename KeyT, typename ValueT, - typename KeyInfoT, bool IsConst> +template <typename KeyT, typename ValueT, typename KeyInfoT, typename Bucket, + bool IsConst> class DenseMapIterator { - typedef std::pair<KeyT, ValueT> Bucket; - typedef DenseMapIterator<KeyT, ValueT, - KeyInfoT, true> ConstIterator; - friend class DenseMapIterator<KeyT, ValueT, KeyInfoT, true>; + typedef DenseMapIterator<KeyT, ValueT, KeyInfoT, Bucket, true> ConstIterator; + friend class DenseMapIterator<KeyT, ValueT, KeyInfoT, Bucket, true>; + public: typedef ptrdiff_t difference_type; typedef typename std::conditional<IsConst, const Bucket, Bucket>::type @@ -996,9 +1010,9 @@ public: // 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. - DenseMapIterator(const DenseMapIterator<KeyT, ValueT, - KeyInfoT, false>& I) - : Ptr(I.Ptr), End(I.End) {} + DenseMapIterator( + const DenseMapIterator<KeyT, ValueT, KeyInfoT, Bucket, false> &I) + : Ptr(I.Ptr), End(I.End) {} reference operator*() const { return *Ptr; @@ -1028,9 +1042,8 @@ private: const KeyT Empty = KeyInfoT::getEmptyKey(); const KeyT Tombstone = KeyInfoT::getTombstoneKey(); - while (Ptr != End && - (KeyInfoT::isEqual(Ptr->first, Empty) || - KeyInfoT::isEqual(Ptr->first, Tombstone))) + while (Ptr != End && (KeyInfoT::isEqual(Ptr->getFirst(), Empty) || + KeyInfoT::isEqual(Ptr->getFirst(), Tombstone))) ++Ptr; } }; diff --git a/include/llvm/ADT/DenseSet.h b/include/llvm/ADT/DenseSet.h index 37a81b0c7ee2..d34024005dfe 100644 --- a/include/llvm/ADT/DenseSet.h +++ b/include/llvm/ADT/DenseSet.h @@ -18,18 +18,34 @@ namespace llvm { +namespace detail { +struct DenseSetEmpty {}; + +// Use the empty base class trick so we can create a DenseMap where the buckets +// contain only a single item. +template <typename KeyT> class DenseSetPair : public DenseSetEmpty { + KeyT key; + +public: + KeyT &getFirst() { return key; } + const KeyT &getFirst() const { return key; } + DenseSetEmpty &getSecond() { return *this; } + const DenseSetEmpty &getSecond() const { return *this; } +}; +} + /// DenseSet - This implements a dense probed hash-table based set. -/// -/// FIXME: This is currently implemented directly in terms of DenseMap, this -/// should be optimized later if there is a need. template<typename ValueT, typename ValueInfoT = DenseMapInfo<ValueT> > class DenseSet { - typedef DenseMap<ValueT, char, ValueInfoT> MapTy; + typedef DenseMap<ValueT, detail::DenseSetEmpty, ValueInfoT, + detail::DenseSetPair<ValueT>> MapTy; + static_assert(sizeof(typename MapTy::value_type) == sizeof(ValueT), + "DenseMap buckets unexpectedly large!"); MapTy TheMap; public: typedef ValueT key_type; typedef ValueT value_type; - typedef unsigned size_type;
+ typedef unsigned size_type; explicit DenseSet(unsigned NumInitBuckets = 0) : TheMap(NumInitBuckets) {} @@ -45,7 +61,7 @@ public: TheMap.clear(); } - /// Return 1 if the specified key is in the set, 0 otherwise.
+ /// Return 1 if the specified key is in the set, 0 otherwise. size_type count(const ValueT &V) const { return TheMap.count(V); } @@ -72,8 +88,8 @@ public: Iterator(const typename MapTy::iterator &i) : I(i) {} - ValueT& operator*() { return I->first; } - ValueT* operator->() { return &I->first; } + ValueT &operator*() { return I->getFirst(); } + ValueT *operator->() { return &I->getFirst(); } Iterator& operator++() { ++I; return *this; } bool operator==(const Iterator& X) const { return I == X.I; } @@ -92,8 +108,8 @@ public: ConstIterator(const typename MapTy::const_iterator &i) : I(i) {} - const ValueT& operator*() { return I->first; } - const ValueT* operator->() { return &I->first; } + const ValueT &operator*() { return I->getFirst(); } + const ValueT *operator->() { return &I->getFirst(); } ConstIterator& operator++() { ++I; return *this; } bool operator==(const ConstIterator& X) const { return I == X.I; } @@ -110,11 +126,27 @@ public: const_iterator end() const { return ConstIterator(TheMap.end()); } iterator find(const ValueT &V) { return Iterator(TheMap.find(V)); } + + /// Alternative version of find() which allows a different, and possibly less + /// expensive, key type. + /// The DenseMapInfo is responsible for supplying methods + /// getHashValue(LookupKeyT) and isEqual(LookupKeyT, KeyT) for each key type + /// used. + template <class LookupKeyT> + iterator find_as(const LookupKeyT &Val) { + return Iterator(TheMap.find_as(Val)); + } + template <class LookupKeyT> + const_iterator find_as(const LookupKeyT &Val) const { + return ConstIterator(TheMap.find_as(Val)); + } + void erase(Iterator I) { return TheMap.erase(I.I); } void erase(ConstIterator CI) { return TheMap.erase(CI.I); } std::pair<iterator, bool> insert(const ValueT &V) { - return TheMap.insert(std::make_pair(V, 0)); + detail::DenseSetEmpty Empty; + return TheMap.insert(std::make_pair(V, Empty)); } // Range insertion of values. diff --git a/include/llvm/ADT/DepthFirstIterator.h b/include/llvm/ADT/DepthFirstIterator.h index dfba43f3ac85..6cd9e68aea56 100644 --- a/include/llvm/ADT/DepthFirstIterator.h +++ b/include/llvm/ADT/DepthFirstIterator.h @@ -33,10 +33,10 @@ #ifndef LLVM_ADT_DEPTHFIRSTITERATOR_H #define LLVM_ADT_DEPTHFIRSTITERATOR_H -#include "llvm/ADT/iterator_range.h" #include "llvm/ADT/GraphTraits.h" #include "llvm/ADT/PointerIntPair.h" #include "llvm/ADT/SmallPtrSet.h" +#include "llvm/ADT/iterator_range.h" #include <set> #include <vector> @@ -231,6 +231,13 @@ df_ext_iterator<T, SetTy> df_ext_end(const T& G, SetTy &S) { return df_ext_iterator<T, SetTy>::end(G, 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)); +} + // Provide global definitions of inverse depth first iterators... template <class T, @@ -276,6 +283,13 @@ idf_ext_iterator<T, SetTy> idf_ext_end(const T& G, SetTy &S) { return idf_ext_iterator<T, SetTy>::end(Inverse<T>(G), 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)); +} + } // End llvm namespace #endif diff --git a/include/llvm/ADT/IntrusiveRefCntPtr.h b/include/llvm/ADT/IntrusiveRefCntPtr.h index f9df3781257e..c859c98d06b2 100644 --- a/include/llvm/ADT/IntrusiveRefCntPtr.h +++ b/include/llvm/ADT/IntrusiveRefCntPtr.h @@ -197,6 +197,9 @@ public: private: void retain() { if (Obj) IntrusiveRefCntPtrInfo<T>::retain(Obj); } void release() { if (Obj) IntrusiveRefCntPtrInfo<T>::release(Obj); } + + template <typename X> + friend class IntrusiveRefCntPtr; }; template<class T, class U> diff --git a/include/llvm/ADT/MapVector.h b/include/llvm/ADT/MapVector.h index 4e1fc1527270..1331b15b2d29 100644 --- a/include/llvm/ADT/MapVector.h +++ b/include/llvm/ADT/MapVector.h @@ -18,6 +18,7 @@ #define LLVM_ADT_MAPVECTOR_H #include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/SmallVector.h" #include <vector> namespace llvm { @@ -37,26 +38,20 @@ class MapVector { public: typedef typename VectorType::iterator iterator; typedef typename VectorType::const_iterator const_iterator; + typedef typename VectorType::reverse_iterator reverse_iterator; + typedef typename VectorType::const_reverse_iterator const_reverse_iterator; - size_type size() const { - return Vector.size(); - } - - iterator begin() { - return Vector.begin(); - } + size_type size() const { return Vector.size(); } - const_iterator begin() const { - return Vector.begin(); - } - - iterator end() { - return Vector.end(); - } + iterator begin() { return Vector.begin(); } + const_iterator begin() const { return Vector.begin(); } + iterator end() { return Vector.end(); } + const_iterator end() const { return Vector.end(); } - const_iterator end() const { - return Vector.end(); - } + reverse_iterator rbegin() { return Vector.rbegin(); } + const_reverse_iterator rbegin() const { return Vector.rbegin(); } + reverse_iterator rend() { return Vector.rend(); } + const_reverse_iterator rend() const { return Vector.rend(); } bool empty() const { return Vector.empty(); @@ -147,6 +142,17 @@ public: return Next; } + /// \brief Remove all elements with the key value Key. + /// + /// Returns the number of elements removed. + size_type erase(const KeyT &Key) { + auto Iterator = find(Key); + if (Iterator == end()) + return 0; + erase(Iterator); + return 1; + } + /// \brief Remove the elements that match the predicate. /// /// Erase all elements that match \c Pred in a single pass. Takes linear @@ -176,6 +182,14 @@ void MapVector<KeyT, ValueT, MapType, VectorType>::remove_if(Function Pred) { Vector.erase(O, Vector.end()); } +/// \brief A MapVector that performs no allocations if smaller than a certain +/// size. +template <typename KeyT, typename ValueT, unsigned N> +struct SmallMapVector + : MapVector<KeyT, ValueT, SmallDenseMap<KeyT, unsigned, N>, + SmallVector<std::pair<KeyT, ValueT>, N>> { +}; + } // end namespace llvm #endif diff --git a/include/llvm/ADT/Optional.h b/include/llvm/ADT/Optional.h index ae8344da76a6..591872e6591a 100644 --- a/include/llvm/ADT/Optional.h +++ b/include/llvm/ADT/Optional.h @@ -20,6 +20,7 @@ #include "llvm/Support/AlignOf.h" #include "llvm/Support/Compiler.h" #include <cassert> +#include <new> #include <utility> namespace llvm { @@ -29,6 +30,8 @@ class Optional { AlignedCharArrayUnion<T> storage; bool hasVal; public: + typedef T value_type; + Optional(NoneType) : hasVal(false) {} explicit Optional() : hasVal(false) {} Optional(const T &y) : hasVal(true) { @@ -67,6 +70,61 @@ 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) { + reset(); + hasVal = true; + 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(); } @@ -117,9 +175,19 @@ public: const T& operator*() const LLVM_LVALUE_FUNCTION { assert(hasVal); return *getPointer(); } T& operator*() LLVM_LVALUE_FUNCTION { assert(hasVal); return *getPointer(); } + template <typename U> + LLVM_CONSTEXPR T getValueOr(U &&value) const LLVM_LVALUE_FUNCTION { + return hasValue() ? getValue() : std::forward<U>(value); + } + #if LLVM_HAS_RVALUE_REFERENCE_THIS T&& getValue() && { assert(hasVal); return std::move(*getPointer()); } T&& operator*() && { assert(hasVal); return std::move(*getPointer()); } + + template <typename U> + T getValueOr(U &&value) && { + return hasValue() ? std::move(getValue()) : std::forward<U>(value); + } #endif }; diff --git a/include/llvm/ADT/PostOrderIterator.h b/include/llvm/ADT/PostOrderIterator.h index dd8cc74b714e..dfadc3b85db6 100644 --- a/include/llvm/ADT/PostOrderIterator.h +++ b/include/llvm/ADT/PostOrderIterator.h @@ -57,7 +57,7 @@ public: // Return true if edge destination should be visited. template<typename NodeType> bool insertEdge(NodeType *From, NodeType *To) { - return Visited.insert(To); + return Visited.insert(To).second; } // Called after all children of BB have been visited. @@ -76,8 +76,9 @@ public: // Return true if edge destination should be visited, called with From = 0 for // the root node. // Graph edges can be pruned by specializing this function. - template<class NodeType> - bool insertEdge(NodeType *From, NodeType *To) { return Visited.insert(To); } + template <class NodeType> bool insertEdge(NodeType *From, NodeType *To) { + return Visited.insert(To).second; + } // Called after all children of BB have been visited. template<class NodeType> diff --git a/include/llvm/ADT/STLExtras.h b/include/llvm/ADT/STLExtras.h index 1cef3933b5d6..4e56e4d74470 100644 --- a/include/llvm/ADT/STLExtras.h +++ b/include/llvm/ADT/STLExtras.h @@ -77,8 +77,11 @@ class function_ref<Ret(Params...)> { } public: - template<typename Callable> - function_ref(Callable &&callable) + 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()(Params ...params) const { @@ -100,7 +103,10 @@ class function_ref<Ret()> { public: template<typename Callable> - function_ref(Callable &&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); } @@ -119,7 +125,10 @@ class function_ref<Ret(Param1)> { public: template<typename Callable> - function_ref(Callable &&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) { @@ -141,7 +150,10 @@ class function_ref<Ret(Param1, Param2)> { public: template<typename Callable> - function_ref(Callable &&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) { @@ -167,7 +179,10 @@ class function_ref<Ret(Param1, Param2, Param3)> { public: template<typename Callable> - function_ref(Callable &&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) { @@ -530,6 +545,12 @@ make_unique(size_t n) { #endif +struct FreeDeleter { + void operator()(void* v) { + ::free(v); + } +}; + template<typename First, typename Second> struct pair_hash { size_t operator()(const std::pair<First, Second> &P) const { diff --git a/include/llvm/ADT/ScopedHashTable.h b/include/llvm/ADT/ScopedHashTable.h index 02a6ea345834..2f60ecc92043 100644 --- a/include/llvm/ADT/ScopedHashTable.h +++ b/include/llvm/ADT/ScopedHashTable.h @@ -148,7 +148,7 @@ public: /// ScopeTy - This is a helpful typedef that allows clients to get easy access /// to the name of the scope for this hash table. typedef ScopedHashTableScope<K, V, KInfo, AllocatorTy> ScopeTy; - typedef unsigned size_type;
+ typedef unsigned size_type; private: typedef ScopedHashTableVal<K, V> ValTy; DenseMap<K, ValTy*, KInfo> TopLevelMap; @@ -171,7 +171,7 @@ public: AllocatorTy &getAllocator() { return Allocator; } const AllocatorTy &getAllocator() const { return Allocator; } - /// Return 1 if the specified key is in the table, 0 otherwise.
+ /// Return 1 if the specified key is in the table, 0 otherwise. size_type count(const K &Key) const { return TopLevelMap.count(Key); } diff --git a/include/llvm/ADT/SetVector.h b/include/llvm/ADT/SetVector.h index 1e7d237045aa..a7fd408c854a 100644 --- a/include/llvm/ADT/SetVector.h +++ b/include/llvm/ADT/SetVector.h @@ -100,7 +100,7 @@ public: /// \brief Insert a new element into the SetVector. /// \returns true iff the element was inserted into the SetVector. bool insert(const value_type &X) { - bool result = set_.insert(X); + bool result = set_.insert(X).second; if (result) vector_.push_back(X); return result; @@ -110,7 +110,7 @@ public: template<typename It> void insert(It Start, It End) { for (; Start != End; ++Start) - if (set_.insert(*Start)) + if (set_.insert(*Start).second) vector_.push_back(*Start); } diff --git a/include/llvm/ADT/SmallBitVector.h b/include/llvm/ADT/SmallBitVector.h index 0922017ea61a..1e2f365b1040 100644 --- a/include/llvm/ADT/SmallBitVector.h +++ b/include/llvm/ADT/SmallBitVector.h @@ -54,7 +54,7 @@ class SmallBitVector { }; public: - typedef unsigned size_type;
+ typedef unsigned size_type; // Encapsulation of a single bit. class reference { SmallBitVector &TheVector; @@ -292,8 +292,12 @@ public: } SmallBitVector &set(unsigned Idx) { - if (isSmall()) + if (isSmall()) { + assert(Idx <= static_cast<unsigned>( + std::numeric_limits<uintptr_t>::digits) && + "undefined behavior"); setSmallBits(getSmallBits() | (uintptr_t(1) << Idx)); + } else getPointer()->set(Idx); return *this; diff --git a/include/llvm/ADT/SmallPtrSet.h b/include/llvm/ADT/SmallPtrSet.h index 74f3fd43cec4..cb1c5e1fa96a 100644 --- a/include/llvm/ADT/SmallPtrSet.h +++ b/include/llvm/ADT/SmallPtrSet.h @@ -22,6 +22,7 @@ #include <cstddef> #include <cstring> #include <iterator> +#include <utility> namespace llvm { @@ -100,7 +101,7 @@ protected: /// insert_imp - This returns true if the pointer was new to the set, false if /// it was already in the set. This is hidden from the client so that the /// derived class can check that the right type of pointer is passed in. - bool insert_imp(const void * Ptr); + std::pair<const void *const *, bool> insert_imp(const void *Ptr); /// erase_imp - If the set contains the specified pointer, remove it and /// return true, otherwise return false. This is hidden from the client so @@ -240,6 +241,8 @@ struct RoundUpToPowerOfTwo { template <typename PtrType> class SmallPtrSetImpl : public SmallPtrSetImplBase { typedef PointerLikeTypeTraits<PtrType> PtrTraits; + + SmallPtrSetImpl(const SmallPtrSetImpl&) LLVM_DELETED_FUNCTION; protected: // Constructors that forward to the base. SmallPtrSetImpl(const void **SmallStorage, const SmallPtrSetImpl &that) @@ -251,10 +254,16 @@ protected: : SmallPtrSetImplBase(SmallStorage, SmallSize) {} public: - /// insert - This returns true if the pointer was new to the set, false if it - /// was already in the set. - bool insert(PtrType Ptr) { - return insert_imp(PtrTraits::getAsVoidPointer(Ptr)); + typedef SmallPtrSetIterator<PtrType> iterator; + typedef SmallPtrSetIterator<PtrType> const_iterator; + + /// Inserts Ptr if and only if there is no element in the container equal to + /// Ptr. The bool component of the returned pair is true if and only if the + /// insertion takes place, and the iterator component of the pair points to + /// the element equal to Ptr. + std::pair<iterator, bool> insert(PtrType Ptr) { + auto p = insert_imp(PtrTraits::getAsVoidPointer(Ptr)); + return std::make_pair(iterator(p.first, CurArray + CurArraySize), p.second); } /// erase - If the set contains the specified pointer, remove it and return @@ -274,8 +283,6 @@ public: insert(*I); } - typedef SmallPtrSetIterator<PtrType> iterator; - typedef SmallPtrSetIterator<PtrType> const_iterator; inline iterator begin() const { return iterator(CurArray, CurArray+CurArraySize); } diff --git a/include/llvm/ADT/SmallSet.h b/include/llvm/ADT/SmallSet.h index bb1971eb7c5d..bc6493554c8b 100644 --- a/include/llvm/ADT/SmallSet.h +++ b/include/llvm/ADT/SmallSet.h @@ -14,6 +14,7 @@ #ifndef LLVM_ADT_SMALLSET_H #define LLVM_ADT_SMALLSET_H +#include "llvm/ADT/None.h" #include "llvm/ADT/SmallPtrSet.h" #include "llvm/ADT/SmallVector.h" #include <set> @@ -60,16 +61,21 @@ public: /// insert - Insert an element into the set if it isn't already there. /// Returns true if the element is inserted (it was not in the set before). - bool insert(const T &V) { + /// The first value of the returned pair is unused and provided for + /// partial compatibility with the standard library self-associative container + /// concept. + // FIXME: Add iterators that abstract over the small and large form, and then + // return those here. + std::pair<NoneType, bool> insert(const T &V) { if (!isSmall()) - return Set.insert(V).second; + return std::make_pair(None, Set.insert(V).second); VIterator I = vfind(V); if (I != Vector.end()) // Don't reinsert if it already exists. - return false; + return std::make_pair(None, false); if (Vector.size() < N) { Vector.push_back(V); - return true; + return std::make_pair(None, true); } // Otherwise, grow from vector to set. @@ -78,7 +84,7 @@ public: Vector.pop_back(); } Set.insert(V); - return true; + return std::make_pair(None, true); } template <typename IterT> diff --git a/include/llvm/ADT/SmallVector.h b/include/llvm/ADT/SmallVector.h index 82538e9bd108..44a352119b09 100644 --- a/include/llvm/ADT/SmallVector.h +++ b/include/llvm/ADT/SmallVector.h @@ -29,8 +29,7 @@ namespace llvm { -/// SmallVectorBase - This is all the non-templated stuff common to all -/// SmallVectors. +/// This is all the non-templated stuff common to all SmallVectors. class SmallVectorBase { protected: void *BeginX, *EndX, *CapacityX; @@ -39,12 +38,12 @@ protected: SmallVectorBase(void *FirstEl, size_t Size) : BeginX(FirstEl), EndX(FirstEl), CapacityX((char*)FirstEl+Size) {} - /// grow_pod - This is an implementation of the grow() method which only works + /// This is an implementation of the grow() method which only works /// on POD-like data types and is out of line to reduce code duplication. void grow_pod(void *FirstEl, size_t MinSizeInBytes, size_t TSize); public: - /// size_in_bytes - This returns size()*sizeof(T). + /// This returns size()*sizeof(T). size_t size_in_bytes() const { return size_t((char*)EndX - (char*)BeginX); } @@ -59,10 +58,9 @@ public: template <typename T, unsigned N> struct SmallVectorStorage; -/// SmallVectorTemplateCommon - This is the part of SmallVectorTemplateBase -/// which does not depend on whether the type T is a POD. The extra dummy -/// template argument is used by ArrayRef to avoid unnecessarily requiring T -/// to be complete. +/// This is the part of SmallVectorTemplateBase which does not depend on whether +/// the type T is a POD. The extra dummy template argument is used by ArrayRef +/// to avoid unnecessarily requiring T to be complete. template <typename T, typename = void> class SmallVectorTemplateCommon : public SmallVectorBase { private: @@ -82,13 +80,13 @@ protected: SmallVectorBase::grow_pod(&FirstEl, MinSizeInBytes, TSize); } - /// isSmall - Return true if this is a smallvector which has not had dynamic + /// Return true if this is a smallvector which has not had dynamic /// memory allocated for it. bool isSmall() const { return BeginX == static_cast<const void*>(&FirstEl); } - /// resetToSmall - Put this vector in a state of being small. + /// Put this vector in a state of being small. void resetToSmall() { BeginX = EndX = CapacityX = &FirstEl; } @@ -128,21 +126,20 @@ public: size_type size() const { return end()-begin(); } size_type max_size() const { return size_type(-1) / sizeof(T); } - /// capacity - Return the total number of elements in the currently allocated - /// buffer. + /// Return the total number of elements in the currently allocated buffer. size_t capacity() const { return capacity_ptr() - begin(); } - /// data - Return a pointer to the vector's buffer, even if empty(). + /// Return a pointer to the vector's buffer, even if empty(). pointer data() { return pointer(begin()); } - /// data - Return a pointer to the vector's buffer, even if empty(). + /// Return a pointer to the vector's buffer, even if empty(). const_pointer data() const { return const_pointer(begin()); } - reference operator[](unsigned idx) { - assert(begin() + idx < end()); + reference operator[](size_type idx) { + assert(idx < size()); return begin()[idx]; } - const_reference operator[](unsigned idx) const { - assert(begin() + idx < end()); + const_reference operator[](size_type idx) const { + assert(idx < size()); return begin()[idx]; } @@ -179,7 +176,7 @@ protected: } } - /// move - Use move-assignment to move the range [I, E) onto the + /// Use move-assignment to move the range [I, E) onto the /// objects starting with "Dest". This is just <memory>'s /// std::move, but not all stdlibs actually provide that. template<typename It1, typename It2> @@ -189,7 +186,7 @@ protected: return Dest; } - /// move_backward - Use move-assignment to move the range + /// Use move-assignment to move the range /// [I, E) onto the objects ending at "Dest", moving objects /// in reverse order. This is just <algorithm>'s /// std::move_backward, but not all stdlibs actually provide that. @@ -200,25 +197,24 @@ protected: return Dest; } - /// uninitialized_move - Move the range [I, E) into the uninitialized - /// memory starting with "Dest", constructing elements as needed. + /// Move the range [I, E) into the uninitialized memory starting with "Dest", + /// constructing elements as needed. template<typename It1, typename It2> static void uninitialized_move(It1 I, It1 E, It2 Dest) { for (; I != E; ++I, ++Dest) ::new ((void*) &*Dest) T(::std::move(*I)); } - /// uninitialized_copy - Copy the range [I, E) onto the uninitialized - /// memory starting with "Dest", constructing elements as needed. + /// Copy the range [I, E) onto the uninitialized memory starting with "Dest", + /// constructing elements as needed. template<typename It1, typename It2> static void uninitialized_copy(It1 I, It1 E, It2 Dest) { std::uninitialized_copy(I, E, Dest); } - /// grow - Grow the allocated memory (without initializing new - /// elements), doubling the size of the allocated memory. - /// Guarantees space for at least one more element, or MinSize more - /// elements if specified. + /// Grow the allocated memory (without initializing new elements), doubling + /// the size of the allocated memory. Guarantees space for at least one more + /// element, or MinSize more elements if specified. void grow(size_t MinSize = 0); public: @@ -240,6 +236,51 @@ 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. @@ -279,22 +320,21 @@ protected: // No need to do a destroy loop for POD's. static void destroy_range(T *, T *) {} - /// move - Use move-assignment to move the range [I, E) onto the + /// Use move-assignment to move the range [I, E) onto the /// objects starting with "Dest". For PODs, this is just memcpy. template<typename It1, typename It2> static It2 move(It1 I, It1 E, It2 Dest) { return ::std::copy(I, E, Dest); } - /// move_backward - Use move-assignment to move the range - /// [I, E) onto the objects ending at "Dest", moving objects - /// in reverse order. + /// Use move-assignment to move the range [I, E) onto the objects ending at + /// "Dest", moving objects in reverse order. template<typename It1, typename It2> static It2 move_backward(It1 I, It1 E, It2 Dest) { return ::std::copy_backward(I, E, Dest); } - /// uninitialized_move - Move the range [I, E) onto the uninitialized memory + /// Move the range [I, E) onto the uninitialized memory /// starting with "Dest", constructing elements into it as needed. template<typename It1, typename It2> static void uninitialized_move(It1 I, It1 E, It2 Dest) { @@ -302,7 +342,7 @@ protected: uninitialized_copy(I, E, Dest); } - /// uninitialized_copy - Copy the range [I, E) onto the uninitialized memory + /// Copy the range [I, E) onto the uninitialized memory /// starting with "Dest", constructing elements into it as needed. template<typename It1, typename It2> static void uninitialized_copy(It1 I, It1 E, It2 Dest) { @@ -310,7 +350,7 @@ protected: std::uninitialized_copy(I, E, Dest); } - /// uninitialized_copy - Copy the range [I, E) onto the uninitialized memory + /// 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) { @@ -320,7 +360,7 @@ protected: memcpy(Dest, I, (E-I)*sizeof(T)); } - /// grow - double the size of the allocated memory, guaranteeing space for at + /// Double the size of the allocated memory, guaranteeing space for at /// least one more element or MinSize if specified. void grow(size_t MinSize = 0) { this->grow_pod(MinSize*sizeof(T), sizeof(T)); @@ -339,9 +379,8 @@ public: }; -/// SmallVectorImpl - This class consists of common code factored out of the -/// SmallVector class to reduce code duplication based on the SmallVector 'N' -/// template parameter. +/// This class consists of common code factored out of the SmallVector class to +/// reduce code duplication based on the SmallVector 'N' template parameter. template <typename T> class SmallVectorImpl : public SmallVectorTemplateBase<T, isPodLike<T>::value> { typedef SmallVectorTemplateBase<T, isPodLike<T>::value > SuperClass; @@ -373,7 +412,7 @@ public: this->EndX = this->BeginX; } - void resize(unsigned N) { + void resize(size_type N) { if (N < this->size()) { this->destroy_range(this->begin()+N, this->end()); this->setEnd(this->begin()+N); @@ -386,7 +425,7 @@ public: } } - void resize(unsigned N, const T &NV) { + void resize(size_type N, const T &NV) { if (N < this->size()) { this->destroy_range(this->begin()+N, this->end()); this->setEnd(this->begin()+N); @@ -398,7 +437,7 @@ public: } } - void reserve(unsigned N) { + void reserve(size_type N) { if (this->capacity() < N) this->grow(N); } @@ -411,8 +450,7 @@ public: void swap(SmallVectorImpl &RHS); - /// append - Add the specified range to the end of the SmallVector. - /// + /// Add the specified range to the end of the SmallVector. template<typename in_iter> void append(in_iter in_start, in_iter in_end) { size_type NumInputs = std::distance(in_start, in_end); @@ -427,8 +465,7 @@ public: this->setEnd(this->end() + NumInputs); } - /// append - Add the specified range to the end of the SmallVector. - /// + /// Add the specified range to the end of the SmallVector. void append(size_type NumInputs, const T &Elt) { // Grow allocated space if needed. if (NumInputs > size_type(this->capacity_ptr()-this->end())) @@ -439,7 +476,7 @@ public: this->setEnd(this->end() + NumInputs); } - void assign(unsigned NumElts, const T &Elt) { + void assign(size_type NumElts, const T &Elt) { clear(); if (this->capacity() < NumElts) this->grow(NumElts); @@ -545,7 +582,7 @@ public: assert(I <= this->end() && "Inserting past the end of the vector."); // Ensure there is enough space. - reserve(static_cast<unsigned>(this->size() + NumToInsert)); + reserve(this->size() + NumToInsert); // Uninvalidate the iterator. I = this->begin()+InsertElt; @@ -599,7 +636,7 @@ public: size_t NumToInsert = std::distance(From, To); // Ensure there is enough space. - reserve(static_cast<unsigned>(this->size() + NumToInsert)); + reserve(this->size() + NumToInsert); // Uninvalidate the iterator. I = this->begin()+InsertElt; @@ -666,7 +703,7 @@ public: /// of the buffer when they know that more elements are available, and only /// update the size later. This avoids the cost of value initializing elements /// which will only be overwritten. - void set_size(unsigned N) { + void set_size(size_type N) { assert(N <= this->capacity()); this->setEnd(this->begin() + N); } @@ -692,7 +729,7 @@ void SmallVectorImpl<T>::swap(SmallVectorImpl<T> &RHS) { // Swap the shared elements. size_t NumShared = this->size(); if (NumShared > RHS.size()) NumShared = RHS.size(); - for (unsigned i = 0; i != static_cast<unsigned>(NumShared); ++i) + for (size_type i = 0; i != NumShared; ++i) std::swap((*this)[i], RHS[i]); // Copy over the extra elts. @@ -833,7 +870,7 @@ struct SmallVectorStorage { template <typename T> struct SmallVectorStorage<T, 1> {}; template <typename T> struct SmallVectorStorage<T, 0> {}; -/// SmallVector - This is a 'vector' (really, a variable-sized array), optimized +/// This is a 'vector' (really, a variable-sized array), optimized /// for the case when the array is small. It contains some number of elements /// in-place, which allows it to avoid heap allocation when the actual number of /// elements is below that threshold. This allows normal "small" cases to be @@ -843,13 +880,13 @@ template <typename T> struct SmallVectorStorage<T, 0> {}; /// template <typename T, unsigned N> class SmallVector : public SmallVectorImpl<T> { - /// Storage - Inline space for elements which aren't stored in the base class. + /// Inline space for elements which aren't stored in the base class. SmallVectorStorage<T, N> Storage; public: SmallVector() : SmallVectorImpl<T>(N) { } - explicit SmallVector(unsigned Size, const T &Value = T()) + explicit SmallVector(size_t Size, const T &Value = T()) : SmallVectorImpl<T>(N) { this->assign(Size, Value); } diff --git a/include/llvm/ADT/SparseBitVector.h b/include/llvm/ADT/SparseBitVector.h index 36754d682355..d5bde2963fbd 100644 --- a/include/llvm/ADT/SparseBitVector.h +++ b/include/llvm/ADT/SparseBitVector.h @@ -45,7 +45,7 @@ struct SparseBitVectorElement : public ilist_node<SparseBitVectorElement<ElementSize> > { public: typedef unsigned long BitWord; - typedef unsigned size_type;
+ typedef unsigned size_type; enum { BITWORD_SIZE = sizeof(BitWord) * CHAR_BIT, BITWORDS_PER_ELEMENT = (ElementSize + BITWORD_SIZE - 1) / BITWORD_SIZE, diff --git a/include/llvm/ADT/SparseMultiSet.h b/include/llvm/ADT/SparseMultiSet.h index dc1273eb7ff6..f858536b6ed8 100644 --- a/include/llvm/ADT/SparseMultiSet.h +++ b/include/llvm/ADT/SparseMultiSet.h @@ -185,7 +185,7 @@ public: typedef const ValueT &const_reference; typedef ValueT *pointer; typedef const ValueT *const_pointer; - typedef unsigned size_type;
+ typedef unsigned size_type; SparseMultiSet() : Sparse(nullptr), Universe(0), FreelistIdx(SMSNode::INVALID), NumFree(0) {} diff --git a/include/llvm/ADT/SparseSet.h b/include/llvm/ADT/SparseSet.h index 632d52ad9d82..9a13440000ac 100644 --- a/include/llvm/ADT/SparseSet.h +++ b/include/llvm/ADT/SparseSet.h @@ -124,7 +124,7 @@ class SparseSet { typedef typename KeyFunctorT::argument_type KeyT; typedef SmallVector<ValueT, 8> DenseT; - typedef unsigned size_type;
+ typedef unsigned size_type; DenseT Dense; SparseT *Sparse; unsigned Universe; diff --git a/include/llvm/ADT/StringMap.h b/include/llvm/ADT/StringMap.h index c40e5e2b3d87..3437607a0bd0 100644 --- a/include/llvm/ADT/StringMap.h +++ b/include/llvm/ADT/StringMap.h @@ -117,8 +117,9 @@ public: explicit StringMapEntry(unsigned strLen) : StringMapEntryBase(strLen), second() {} - StringMapEntry(unsigned strLen, ValueTy V) - : StringMapEntryBase(strLen), second(std::move(V)) {} + template <class InitTy> + StringMapEntry(unsigned strLen, InitTy &&V) + : StringMapEntryBase(strLen), second(std::forward<InitTy>(V)) {} StringRef getKey() const { return StringRef(getKeyData(), getKeyLength()); @@ -138,10 +139,9 @@ public: /// Create - Create a StringMapEntry for the specified key and default /// construct the value. - template<typename AllocatorTy, typename InitType> - static StringMapEntry *Create(StringRef Key, - AllocatorTy &Allocator, - InitType InitVal) { + template <typename AllocatorTy, typename InitType> + static StringMapEntry *Create(StringRef Key, AllocatorTy &Allocator, + InitType &&InitVal) { unsigned KeyLength = Key.size(); // Allocate a new item with space for the string at the end and a null @@ -154,7 +154,7 @@ public: static_cast<StringMapEntry*>(Allocator.Allocate(AllocSize,Alignment)); // Default construct the value. - new (NewItem) StringMapEntry(KeyLength, std::move(InitVal)); + new (NewItem) StringMapEntry(KeyLength, std::forward<InitType>(InitVal)); // Copy the string information. char *StrBuffer = const_cast<char*>(NewItem->getKeyData()); @@ -170,28 +170,15 @@ public: /// Create - Create a StringMapEntry with normal malloc/free. template<typename InitType> - static StringMapEntry *Create(StringRef Key, InitType InitVal) { + static StringMapEntry *Create(StringRef Key, InitType &&InitVal) { MallocAllocator A; - return Create(Key, A, std::move(InitVal)); + return Create(Key, A, std::forward<InitType>(InitVal)); } static StringMapEntry *Create(StringRef Key) { return Create(Key, ValueTy()); } - /// GetStringMapEntryFromValue - Given a value that is known to be embedded - /// into a StringMapEntry, return the StringMapEntry itself. - static StringMapEntry &GetStringMapEntryFromValue(ValueTy &V) { - StringMapEntry *EPtr = 0; - char *Ptr = reinterpret_cast<char*>(&V) - - (reinterpret_cast<char*>(&EPtr->second) - - reinterpret_cast<char*>(EPtr)); - return *reinterpret_cast<StringMapEntry*>(Ptr); - } - static const StringMapEntry &GetStringMapEntryFromValue(const ValueTy &V) { - return GetStringMapEntryFromValue(const_cast<ValueTy&>(V)); - } - /// GetStringMapEntryFromKeyData - Given key data that is known to be embedded /// into a StringMapEntry, return the StringMapEntry itself. static StringMapEntry &GetStringMapEntryFromKeyData(const char *KeyData) { @@ -296,7 +283,7 @@ public: } ValueTy &operator[](StringRef Key) { - return GetOrCreateValue(Key).getValue(); + return insert(std::make_pair(Key, ValueTy())).first->second; } /// count - Return 1 if the element is in the map, 0 otherwise. @@ -363,18 +350,6 @@ public: NumTombstones = 0; } - /// GetOrCreateValue - Look up the specified key in the table. If a value - /// exists, return it. Otherwise, default construct a value, insert it, and - /// return. - template <typename InitTy> - MapEntryTy &GetOrCreateValue(StringRef Key, InitTy Val) { - return *insert(std::make_pair(Key, std::move(Val))).first; - } - - MapEntryTy &GetOrCreateValue(StringRef Key) { - return GetOrCreateValue(Key, ValueTy()); - } - /// remove - Remove the specified key/value pair from the map, but do not /// erase it. This aborts if the key is not in the map. void remove(MapEntryTy *KeyValue) { diff --git a/include/llvm/ADT/StringRef.h b/include/llvm/ADT/StringRef.h index 1f413e80553f..6111c42da9dc 100644 --- a/include/llvm/ADT/StringRef.h +++ b/include/llvm/ADT/StringRef.h @@ -51,12 +51,6 @@ namespace llvm { /// The length of the string. size_t Length; - // Workaround PR5482: nearly all gcc 4.x miscompile StringRef and std::min() - // Changing the arg of min to be an integer, instead of a reference to an - // integer works around this bug. - static size_t min(size_t a, size_t b) { return a < b ? a : b; } - static size_t max(size_t a, size_t b) { return a > b ? a : b; } - // Workaround memcmp issue with null pointers (undefined behavior) // by providing a specialized version static int compareMemory(const char *Lhs, const char *Rhs, size_t Length) { @@ -97,6 +91,13 @@ namespace llvm { iterator end() const { return Data + Length; } + const unsigned char *bytes_begin() const { + return reinterpret_cast<const unsigned char *>(begin()); + } + const unsigned char *bytes_end() const { + return reinterpret_cast<const unsigned char *>(end()); + } + /// @} /// @name String Operations /// @{ @@ -124,7 +125,7 @@ namespace llvm { } // copy - Allocate copy in Allocator and return StringRef to it. - template <typename Allocator> StringRef copy(Allocator &A) { + template <typename Allocator> StringRef copy(Allocator &A) const { char *S = A.template Allocate<char>(Length); std::copy(begin(), end(), S); return StringRef(S, Length); @@ -146,7 +147,7 @@ namespace llvm { /// is lexicographically less than, equal to, or greater than the \p RHS. int compare(StringRef RHS) const { // Check the prefix for a mismatch. - if (int Res = compareMemory(Data, RHS.Data, min(Length, RHS.Length))) + if (int Res = compareMemory(Data, RHS.Data, std::min(Length, RHS.Length))) return Res < 0 ? -1 : 1; // Otherwise the prefixes match, so we only need to check the lengths. @@ -237,7 +238,7 @@ 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 = min(From, Length), e = Length; i != e; ++i) + for (size_t i = std::min(From, Length), e = Length; i != e; ++i) if (Data[i] == C) return i; return npos; @@ -254,7 +255,7 @@ namespace llvm { /// \returns The index of the last occurrence of \p C, or npos if not /// found. size_t rfind(char C, size_t From = npos) const { - From = min(From, Length); + From = std::min(From, Length); size_t i = From; while (i != 0) { --i; @@ -353,8 +354,11 @@ namespace llvm { typename std::enable_if<!std::numeric_limits<T>::is_signed, bool>::type getAsInteger(unsigned Radix, T &Result) const { unsigned long long ULLVal; + // The additional cast to unsigned long long is required to avoid the + // Visual C++ warning C4805: '!=' : unsafe mix of type 'bool' and type + // 'unsigned __int64' when instantiating getAsInteger with T = bool. if (getAsUnsignedInteger(*this, Radix, ULLVal) || - static_cast<T>(ULLVal) != ULLVal) + static_cast<unsigned long long>(static_cast<T>(ULLVal)) != ULLVal) return true; Result = ULLVal; return false; @@ -396,8 +400,8 @@ namespace llvm { /// exceeds the number of characters remaining in the string, the string /// suffix (starting with \p Start) will be returned. StringRef substr(size_t Start, size_t N = npos) const { - Start = min(Start, Length); - return StringRef(Data + Start, min(N, Length - Start)); + Start = std::min(Start, Length); + return StringRef(Data + Start, std::min(N, Length - Start)); } /// Return a StringRef equal to 'this' but with the first \p N elements @@ -425,8 +429,8 @@ namespace llvm { /// number of characters remaining in the string, the string suffix /// (starting with \p Start) will be returned. StringRef slice(size_t Start, size_t End) const { - Start = min(Start, Length); - End = min(max(Start, End), Length); + Start = std::min(Start, Length); + End = std::min(std::max(Start, End), Length); return StringRef(Data + Start, End - Start); } diff --git a/include/llvm/ADT/StringSet.h b/include/llvm/ADT/StringSet.h index 7bea577f34d3..3e0cc200b6dd 100644 --- a/include/llvm/ADT/StringSet.h +++ b/include/llvm/ADT/StringSet.h @@ -24,20 +24,9 @@ namespace llvm { typedef llvm::StringMap<char, AllocatorTy> base; public: - /// insert - Insert the specified key into the set. If the key already - /// exists in the set, return false and ignore the request, otherwise insert - /// it and return true. - bool insert(StringRef Key) { - // Get or create the map entry for the key; if it doesn't exist the value - // type will be default constructed which we use to detect insert. - // - // We use '+' as the sentinel value in the map. + std::pair<typename base::iterator, bool> insert(StringRef Key) { assert(!Key.empty()); - StringMapEntry<char> &Entry = this->GetOrCreateValue(Key); - if (Entry.getValue() == '+') - return false; - Entry.setValue('+'); - return true; + return base::insert(std::make_pair(Key, '\0')); } }; } diff --git a/include/llvm/ADT/TinyPtrVector.h b/include/llvm/ADT/TinyPtrVector.h index 5669b2a81a40..15137f5ebf8c 100644 --- a/include/llvm/ADT/TinyPtrVector.h +++ b/include/llvm/ADT/TinyPtrVector.h @@ -96,10 +96,17 @@ public: return *this; } + /// Constructor from a single element. + explicit TinyPtrVector(EltTy Elt) : Val(Elt) {} + + /// Constructor from an ArrayRef. + explicit TinyPtrVector(ArrayRef<EltTy> Elts) + : Val(new VecTy(Elts.begin(), Elts.end())) {} + // implicit conversion operator to ArrayRef. operator ArrayRef<EltTy>() const { if (Val.isNull()) - return ArrayRef<EltTy>(); + return None; if (Val.template is<EltTy>()) return *Val.getAddrOfPtr1(); return *Val.template get<VecTy*>(); diff --git a/include/llvm/ADT/Triple.h b/include/llvm/ADT/Triple.h index b96f11435520..8a685995256b 100644 --- a/include/llvm/ADT/Triple.h +++ b/include/llvm/ADT/Triple.h @@ -48,8 +48,6 @@ public: arm, // ARM (little endian): arm, armv.*, xscale armeb, // ARM (big endian): armeb - arm64, // ARM64 (little endian): arm64 - arm64_be, // ARM64 (big endian): arm64_be aarch64, // AArch64 (little endian): aarch64 aarch64_be, // AArch64 (big endian): aarch64_be hexagon, // Hexagon: hexagon @@ -62,6 +60,7 @@ public: ppc64, // PPC64: powerpc64, ppu ppc64le, // PPC64LE: powerpc64le r600, // R600: AMD GPUs HD2XXX - HD6XXX + amdgcn, // AMDGCN: AMD GCN GPUs sparc, // Sparc: sparc sparcv9, // Sparcv9: Sparcv9 systemz, // SystemZ: s390x @@ -74,7 +73,11 @@ public: nvptx, // NVPTX: 32-bit nvptx64, // NVPTX: 64-bit le32, // le32: generic little-endian 32-bit CPU (PNaCl / Emscripten) - amdil, // amdil: amd IL + le64, // le64: generic little-endian 64-bit CPU (PNaCl / Emscripten) + amdil, // AMDIL + amdil64, // AMDIL with 64-bit pointers + hsail, // AMD HSAIL + 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 @@ -92,7 +95,11 @@ public: ARMSubArch_v6t2, ARMSubArch_v5, ARMSubArch_v5te, - ARMSubArch_v4t + ARMSubArch_v4t, + + KalimbaSubArch_v3, + KalimbaSubArch_v4, + KalimbaSubArch_v5 }; enum VendorType { UnknownVendor, @@ -112,8 +119,6 @@ public: enum OSType { UnknownOS, - AuroraUX, - Cygwin, Darwin, DragonFly, FreeBSD, @@ -122,7 +127,6 @@ public: Linux, Lv2, // PS3 MacOSX, - MinGW32, // i*86-pc-mingw32, *-w64-mingw32 NetBSD, OpenBSD, Solaris, @@ -135,7 +139,8 @@ public: Bitrig, AIX, CUDA, // NVIDIA CUDA - NVCL // NVIDIA OpenCL + NVCL, // NVIDIA OpenCL + AMDHSA // AMD HSA Runtime }; enum EnvironmentType { UnknownEnvironment, @@ -361,10 +366,28 @@ public: return isMacOSX() || isiOS(); } + bool isOSNetBSD() const { + return getOS() == Triple::NetBSD; + } + + bool isOSOpenBSD() const { + return getOS() == Triple::OpenBSD; + } + bool isOSFreeBSD() const { return getOS() == Triple::FreeBSD; } + bool isOSDragonFly() const { return getOS() == Triple::DragonFly; } + + bool isOSSolaris() const { + return getOS() == Triple::Solaris; + } + + bool isOSBitrig() const { + return getOS() == Triple::Bitrig; + } + bool isWindowsMSVCEnvironment() const { return getOS() == Triple::Win32 && (getEnvironment() == Triple::UnknownEnvironment || @@ -380,13 +403,11 @@ public: } bool isWindowsCygwinEnvironment() const { - return getOS() == Triple::Cygwin || - (getOS() == Triple::Win32 && getEnvironment() == Triple::Cygnus); + return getOS() == Triple::Win32 && getEnvironment() == Triple::Cygnus; } bool isWindowsGNUEnvironment() const { - return getOS() == Triple::MinGW32 || - (getOS() == Triple::Win32 && getEnvironment() == Triple::GNU); + return getOS() == Triple::Win32 && getEnvironment() == Triple::GNU; } /// \brief Tests for either Cygwin or MinGW OS @@ -396,7 +417,8 @@ public: /// \brief Is this a "Windows" OS targeting a "MSVCRT.dll" environment. bool isOSMSVCRT() const { - return isWindowsMSVCEnvironment() || isWindowsGNUEnvironment(); + return isWindowsMSVCEnvironment() || isWindowsGNUEnvironment() || + isWindowsItaniumEnvironment(); } /// \brief Tests whether the OS is Windows. @@ -475,10 +497,6 @@ public: /// environment components with a single string. void setOSAndEnvironmentName(StringRef Str); - /// getArchNameForAssembler - Get an architecture name that is understood by - /// the target assembler. - const char *getArchNameForAssembler(); - /// @} /// @name Helpers to build variants of a particular triple. /// @{ diff --git a/include/llvm/ADT/Twine.h b/include/llvm/ADT/Twine.h index 4be3ee6f82db..05d2fea117cf 100644 --- a/include/llvm/ADT/Twine.h +++ b/include/llvm/ADT/Twine.h @@ -80,7 +80,7 @@ namespace llvm { /// StringRef) codegen as desired. class Twine { /// NodeKind - Represent the type of an argument. - enum NodeKind { + enum NodeKind : unsigned char { /// An empty string; the result of concatenating anything with it is also /// empty. NullKind, @@ -153,12 +153,10 @@ namespace llvm { /// RHS - The suffix in the concatenation, which may be uninitialized for /// Null or Empty kinds. Child RHS; - // enums stored as unsigned chars to save on space while some compilers - // don't support specifying the backing type for an enum /// LHSKind - The NodeKind of the left hand side, \see getLHSKind(). - unsigned char LHSKind; - /// RHSKind - The NodeKind of the left hand side, \see getLHSKind(). - unsigned char RHSKind; + NodeKind LHSKind; + /// RHSKind - The NodeKind of the right hand side, \see getRHSKind(). + NodeKind RHSKind; private: /// Construct a nullary twine; the kind must be NullKind or EmptyKind. @@ -238,10 +236,10 @@ namespace llvm { } /// getLHSKind - Get the NodeKind of the left-hand side. - NodeKind getLHSKind() const { return (NodeKind) LHSKind; } + NodeKind getLHSKind() const { return LHSKind; } /// getRHSKind - Get the NodeKind of the right-hand side. - NodeKind getRHSKind() const { return (NodeKind) RHSKind; } + NodeKind getRHSKind() const { return RHSKind; } /// printOneChild - Print one child from a twine. void printOneChild(raw_ostream &OS, Child Ptr, NodeKind Kind) const; diff --git a/include/llvm/ADT/VariadicFunction.h b/include/llvm/ADT/VariadicFunction.h index 0497aa70887c..403130c623eb 100644 --- a/include/llvm/ADT/VariadicFunction.h +++ b/include/llvm/ADT/VariadicFunction.h @@ -105,7 +105,7 @@ template <typename ResultT, typename ArgT, ResultT (*Func)(ArrayRef<const ArgT *>)> struct VariadicFunction { ResultT operator()() const { - return Func(ArrayRef<const ArgT *>()); + return Func(None); } #define LLVM_DEFINE_OVERLOAD(N) \ @@ -152,7 +152,7 @@ template <typename ResultT, typename Param0T, typename ArgT, ResultT (*Func)(Param0T, ArrayRef<const ArgT *>)> struct VariadicFunction1 { ResultT operator()(Param0T P0) const { - return Func(P0, ArrayRef<const ArgT *>()); + return Func(P0, None); } #define LLVM_DEFINE_OVERLOAD(N) \ @@ -199,7 +199,7 @@ template <typename ResultT, typename Param0T, typename Param1T, typename ArgT, ResultT (*Func)(Param0T, Param1T, ArrayRef<const ArgT *>)> struct VariadicFunction2 { ResultT operator()(Param0T P0, Param1T P1) const { - return Func(P0, P1, ArrayRef<const ArgT *>()); + return Func(P0, P1, None); } #define LLVM_DEFINE_OVERLOAD(N) \ @@ -248,7 +248,7 @@ template <typename ResultT, typename Param0T, typename Param1T, ResultT (*Func)(Param0T, Param1T, Param2T, ArrayRef<const ArgT *>)> struct VariadicFunction3 { ResultT operator()(Param0T P0, Param1T P1, Param2T P2) const { - return Func(P0, P1, P2, ArrayRef<const ArgT *>()); + return Func(P0, P1, P2, None); } #define LLVM_DEFINE_OVERLOAD(N) \ diff --git a/include/llvm/ADT/ilist.h b/include/llvm/ADT/ilist.h index bc148452f217..8c19a6f4547a 100644 --- a/include/llvm/ADT/ilist.h +++ b/include/llvm/ADT/ilist.h @@ -579,60 +579,6 @@ public: void splice(iterator where, iplist &L2, iterator first, iterator last) { if (first != last) transfer(where, L2, first, last); } - - - - //===----------------------------------------------------------------------=== - // High-Level Functionality that shouldn't really be here, but is part of list - // - - // These two functions are actually called remove/remove_if in list<>, but - // they actually do the job of erase, rename them accordingly. - // - void erase(const NodeTy &val) { - for (iterator I = begin(), E = end(); I != E; ) { - iterator next = I; ++next; - if (*I == val) erase(I); - I = next; - } - } - template<class Pr1> void erase_if(Pr1 pred) { - for (iterator I = begin(), E = end(); I != E; ) { - iterator next = I; ++next; - if (pred(*I)) erase(I); - I = next; - } - } - - template<class Pr2> void unique(Pr2 pred) { - if (empty()) return; - for (iterator I = begin(), E = end(), Next = begin(); ++Next != E;) { - if (pred(*I)) - erase(Next); - else - I = Next; - Next = I; - } - } - void unique() { unique(op_equal); } - - template<class Pr3> void merge(iplist &right, Pr3 pred) { - iterator first1 = begin(), last1 = end(); - iterator first2 = right.begin(), last2 = right.end(); - while (first1 != last1 && first2 != last2) - if (pred(*first2, *first1)) { - iterator next = first2; - transfer(first1, right, first2, ++next); - first2 = next; - } else { - ++first1; - } - if (first2 != last2) transfer(last1, right, first2, last2); - } - void merge(iplist &right) { return merge(right, op_less); } - - template<class Pr3> void sort(Pr3 pred); - void sort() { sort(op_less); } }; diff --git a/include/llvm/ADT/ilist_node.h b/include/llvm/ADT/ilist_node.h index 85aa7a4b1f7f..26d0b55e4093 100644 --- a/include/llvm/ADT/ilist_node.h +++ b/include/llvm/ADT/ilist_node.h @@ -12,8 +12,8 @@ // //===----------------------------------------------------------------------===// -#ifndef LLVM_ADT_ILISTNODE_H -#define LLVM_ADT_ILISTNODE_H +#ifndef LLVM_ADT_ILIST_NODE_H +#define LLVM_ADT_ILIST_NODE_H namespace llvm { diff --git a/include/llvm/ADT/iterator.h b/include/llvm/ADT/iterator.h index 56041dbb106c..e2c9e5ea6bda 100644 --- a/include/llvm/ADT/iterator.h +++ b/include/llvm/ADT/iterator.h @@ -10,8 +10,8 @@ #ifndef LLVM_ADT_ITERATOR_H #define LLVM_ADT_ITERATOR_H -#include <iterator> #include <cstddef> +#include <iterator> namespace llvm { diff --git a/include/llvm/ADT/iterator_range.h b/include/llvm/ADT/iterator_range.h index dd17d6c8f7b4..523a86f02e08 100644 --- a/include/llvm/ADT/iterator_range.h +++ b/include/llvm/ADT/iterator_range.h @@ -32,7 +32,6 @@ class iterator_range { IteratorT begin_iterator, end_iterator; public: - iterator_range() {} iterator_range(IteratorT begin_iterator, IteratorT end_iterator) : begin_iterator(std::move(begin_iterator)), end_iterator(std::move(end_iterator)) {} @@ -48,6 +47,10 @@ public: template <class T> iterator_range<T> make_range(T x, T y) { return iterator_range<T>(std::move(x), std::move(y)); } + +template <typename T> iterator_range<T> make_range(std::pair<T, T> p) { + return iterator_range<T>(std::move(p.first), std::move(p.second)); +} } #endif |