diff options
Diffstat (limited to 'include/llvm/ADT')
30 files changed, 1250 insertions, 415 deletions
diff --git a/include/llvm/ADT/APFloat.h b/include/llvm/ADT/APFloat.h index 3fe04060fd591..3f6bd00a779ce 100644 --- a/include/llvm/ADT/APFloat.h +++ b/include/llvm/ADT/APFloat.h @@ -25,6 +25,8 @@ struct fltSemantics; class APSInt; class StringRef; +template <typename T> class SmallVectorImpl; + /// Enum that represents what fraction of the LSB truncated bits of an fp number /// represent. /// @@ -511,19 +513,12 @@ public: /// 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; - } + friend int ilogb(const APFloat &Arg); /// \brief Returns: X * 2^Exp for integral exponents. - friend APFloat scalbn(APFloat X, int Exp); + friend APFloat scalbn(APFloat X, int Exp, roundingMode); + + friend APFloat frexp(const APFloat &X, int &Exp, roundingMode); private: @@ -579,6 +574,7 @@ private: const APInt *fill); void makeInf(bool Neg = false); void makeZero(bool Neg = false); + void makeQuiet(); /// @} @@ -651,7 +647,14 @@ private: /// 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); +int ilogb(const APFloat &Arg); +APFloat scalbn(APFloat X, int Exp, APFloat::roundingMode); + +/// \brief Equivalent of C standard library function. +/// +/// While the C standard says Exp is an unspecified value for infinity and nan, +/// this returns INT_MAX for infinities, and INT_MIN for NaNs. +APFloat frexp(const APFloat &Val, int &Exp, APFloat::roundingMode RM); /// \brief Returns the absolute value of the argument. inline APFloat abs(APFloat X) { diff --git a/include/llvm/ADT/APInt.h b/include/llvm/ADT/APInt.h index e2a0cb5e69dc0..d77d1c7ca93f3 100644 --- a/include/llvm/ADT/APInt.h +++ b/include/llvm/ADT/APInt.h @@ -16,7 +16,6 @@ #ifndef LLVM_ADT_APINT_H #define LLVM_ADT_APINT_H -#include "llvm/ADT/ArrayRef.h" #include "llvm/Support/Compiler.h" #include "llvm/Support/MathExtras.h" #include <cassert> @@ -31,6 +30,7 @@ class hash_code; class raw_ostream; template <typename T> class SmallVectorImpl; +template <typename T> class ArrayRef; // An unsigned host type used as a single part of a multi-part // bignum. @@ -177,11 +177,11 @@ class APInt { /// provides a more convenient form of divide for internal use since KnuthDiv /// has specific constraints on its inputs. If those constraints are not met /// then it provides a simpler form of divide. - static void divide(const APInt LHS, unsigned lhsWords, const APInt &RHS, + static void divide(const APInt &LHS, unsigned lhsWords, const APInt &RHS, unsigned rhsWords, APInt *Quotient, APInt *Remainder); /// out-of-line slow case for inline constructor - void initSlowCase(unsigned numBits, uint64_t val, bool isSigned); + void initSlowCase(uint64_t val, bool isSigned); /// shared code between two array constructors void initFromArray(ArrayRef<uint64_t> array); @@ -239,7 +239,7 @@ public: if (isSingleWord()) VAL = val; else - initSlowCase(numBits, val, isSigned); + initSlowCase(val, isSigned); clearUnusedBits(); } @@ -625,7 +625,12 @@ public: /// Negates *this using two's complement logic. /// /// \returns An APInt value representing the negation of *this. - APInt operator-() const { return APInt(BitWidth, 0) - (*this); } + APInt operator-() const { + APInt Result(*this); + Result.flipAllBits(); + ++Result; + return Result; + } /// \brief Logical negation operator. /// @@ -835,13 +840,13 @@ public: /// /// Adds RHS to this APInt and returns the result. APInt operator+(const APInt &RHS) const; - APInt operator+(uint64_t RHS) const { return (*this) + APInt(BitWidth, RHS); } + APInt operator+(uint64_t RHS) const; /// \brief Subtraction operator. /// /// Subtracts RHS from this APInt and returns the result. APInt operator-(const APInt &RHS) const; - APInt operator-(uint64_t RHS) const { return (*this) - APInt(BitWidth, RHS); } + APInt operator-(uint64_t RHS) const; /// \brief Left logical shift operator. /// @@ -1451,6 +1456,10 @@ public: /// \returns a byte-swapped representation of this APInt Value. APInt LLVM_ATTRIBUTE_UNUSED_RESULT byteSwap() const; + /// \returns the value with the bit representation reversed of this APInt + /// Value. + APInt LLVM_ATTRIBUTE_UNUSED_RESULT reverseBits() const; + /// \brief Converts this APInt to a double value. double roundToDouble(bool isSigned) const; @@ -1744,16 +1753,24 @@ inline raw_ostream &operator<<(raw_ostream &OS, const APInt &I) { namespace APIntOps { /// \brief Determine the smaller of two APInts considered to be signed. -inline APInt smin(const APInt &A, const APInt &B) { return A.slt(B) ? A : B; } +inline const APInt &smin(const APInt &A, const APInt &B) { + return A.slt(B) ? A : B; +} /// \brief Determine the larger of two APInts considered to be signed. -inline APInt smax(const APInt &A, const APInt &B) { return A.sgt(B) ? A : B; } +inline const APInt &smax(const APInt &A, const APInt &B) { + return A.sgt(B) ? A : B; +} /// \brief Determine the smaller of two APInts considered to be signed. -inline APInt umin(const APInt &A, const APInt &B) { return A.ult(B) ? A : B; } +inline const APInt &umin(const APInt &A, const APInt &B) { + return A.ult(B) ? A : B; +} /// \brief Determine the larger of two APInts considered to be unsigned. -inline APInt umax(const APInt &A, const APInt &B) { return A.ugt(B) ? A : B; } +inline const APInt &umax(const APInt &A, const APInt &B) { + return A.ugt(B) ? A : B; +} /// \brief Check if the specified APInt has a N-bits unsigned integer value. inline bool isIntN(unsigned N, const APInt &APIVal) { return APIVal.isIntN(N); } @@ -1770,6 +1787,13 @@ inline bool isMask(unsigned numBits, const APInt &APIVal) { APIVal == APInt::getLowBitsSet(APIVal.getBitWidth(), numBits); } +/// \returns true if the argument is a non-empty sequence of ones starting at +/// the least significant bit with the remainder zero (32 bit version). +/// Ex. isMask(0x0000FFFFU) == true. +inline bool isMask(const APInt &Value) { + return (Value != 0) && ((Value + 1) & Value) == 0; +} + /// \brief Return true if the argument APInt value contains a sequence of ones /// with the remainder zero. inline bool isShiftedMask(unsigned numBits, const APInt &APIVal) { diff --git a/include/llvm/ADT/ArrayRef.h b/include/llvm/ADT/ArrayRef.h index 517ba39849e1d..95a1e62ef0057 100644 --- a/include/llvm/ADT/ArrayRef.h +++ b/include/llvm/ADT/ArrayRef.h @@ -16,7 +16,6 @@ #include <vector> namespace llvm { - /// ArrayRef - Represent a constant reference to an array (0 or more elements /// consecutively in memory), i.e. a start pointer and a length. It allows /// various APIs to take consecutive elements easily and conveniently. @@ -92,19 +91,20 @@ namespace llvm { /// 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) + ArrayRef( + const ArrayRef<U *> &A, + typename std::enable_if< + std::is_convertible<U *const *, T const *>::value>::type * = nullptr) : 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) + /*implicit*/ ArrayRef( + const SmallVectorTemplateCommon<U *, DummyT> &Vec, + typename std::enable_if< + std::is_convertible<U *const *, T const *>::value>::type * = nullptr) : Data(Vec.data()), Length(Vec.size()) { } @@ -161,20 +161,26 @@ namespace llvm { } /// slice(n) - Chop off the first N elements of the array. - ArrayRef<T> slice(unsigned N) const { + ArrayRef<T> slice(size_t N) const { assert(N <= size() && "Invalid specifier"); return ArrayRef<T>(data()+N, size()-N); } /// slice(n, m) - Chop off the first N elements of the array, and keep M /// elements in the array. - ArrayRef<T> slice(unsigned N, unsigned M) const { + ArrayRef<T> slice(size_t N, size_t M) const { assert(N+M <= size() && "Invalid specifier"); return ArrayRef<T>(data()+N, M); } - // \brief Drop the last \p N elements of the array. - ArrayRef<T> drop_back(unsigned N = 1) const { + /// \brief Drop the first \p N elements of the array. + ArrayRef<T> drop_front(size_t N = 1) const { + assert(size() >= N && "Dropping more elements than exist"); + return slice(N, size() - N); + } + + /// \brief Drop the last \p N elements of the array. + ArrayRef<T> drop_back(size_t N = 1) const { assert(size() >= N && "Dropping more elements than exist"); return slice(0, size() - N); } @@ -273,19 +279,25 @@ namespace llvm { } /// slice(n) - Chop off the first N elements of the array. - MutableArrayRef<T> slice(unsigned N) const { + MutableArrayRef<T> slice(size_t N) const { assert(N <= this->size() && "Invalid specifier"); return MutableArrayRef<T>(data()+N, this->size()-N); } /// slice(n, m) - Chop off the first N elements of the array, and keep M /// elements in the array. - MutableArrayRef<T> slice(unsigned N, unsigned M) const { + MutableArrayRef<T> slice(size_t N, size_t M) const { assert(N+M <= this->size() && "Invalid specifier"); return MutableArrayRef<T>(data()+N, M); } - MutableArrayRef<T> drop_back(unsigned N) const { + /// \brief Drop the first \p N elements of the array. + MutableArrayRef<T> drop_front(size_t N = 1) const { + assert(this->size() >= N && "Dropping more elements than exist"); + return slice(N, this->size() - N); + } + + MutableArrayRef<T> drop_back(size_t N = 1) const { assert(this->size() >= N && "Dropping more elements than exist"); return slice(0, this->size() - N); } @@ -379,6 +391,6 @@ namespace llvm { template <typename T> hash_code hash_value(ArrayRef<T> S) { return hash_combine_range(S.begin(), S.end()); } -} +} // end namespace llvm -#endif +#endif // LLVM_ADT_ARRAYREF_H diff --git a/include/llvm/ADT/BitVector.h b/include/llvm/ADT/BitVector.h index ad00d51f99e9f..661437126d488 100644 --- a/include/llvm/ADT/BitVector.h +++ b/include/llvm/ADT/BitVector.h @@ -14,13 +14,13 @@ #ifndef LLVM_ADT_BITVECTOR_H #define LLVM_ADT_BITVECTOR_H -#include "llvm/Support/Compiler.h" -#include "llvm/Support/ErrorHandling.h" #include "llvm/Support/MathExtras.h" #include <algorithm> #include <cassert> #include <climits> +#include <cstdint> #include <cstdlib> +#include <cstring> namespace llvm { @@ -69,7 +69,7 @@ public: } operator bool() const { - return ((*WordRef) & (BitWord(1) << BitPos)) ? true : false; + return ((*WordRef) & (BitWord(1) << BitPos)) != 0; } }; @@ -105,6 +105,7 @@ public: BitVector(BitVector &&RHS) : Bits(RHS.Bits), Size(RHS.Size), Capacity(RHS.Capacity) { RHS.Bits = nullptr; + RHS.Size = RHS.Capacity = 0; } ~BitVector() { @@ -244,7 +245,7 @@ public: BitWord PrefixMask = ~0UL << (I % BITWORD_SIZE); Bits[I / BITWORD_SIZE] |= PrefixMask; - I = RoundUpToAlignment(I, BITWORD_SIZE); + I = alignTo(I, BITWORD_SIZE); for (; I + BITWORD_SIZE <= E; I += BITWORD_SIZE) Bits[I / BITWORD_SIZE] = ~0UL; @@ -283,7 +284,7 @@ public: BitWord PrefixMask = ~0UL << (I % BITWORD_SIZE); Bits[I / BITWORD_SIZE] &= ~PrefixMask; - I = RoundUpToAlignment(I, BITWORD_SIZE); + I = alignTo(I, BITWORD_SIZE); for (; I + BITWORD_SIZE <= E; I += BITWORD_SIZE) Bits[I / BITWORD_SIZE] = 0UL; @@ -454,6 +455,7 @@ public: Capacity = RHS.Capacity; RHS.Bits = nullptr; + RHS.Size = RHS.Capacity = 0; return *this; } @@ -576,7 +578,7 @@ static inline size_t capacity_in_bytes(const BitVector &X) { return X.getMemorySize(); } -} // End llvm namespace +} // end namespace llvm namespace std { /// Implement std::swap in terms of BitVector swap. @@ -584,6 +586,6 @@ namespace std { swap(llvm::BitVector &LHS, llvm::BitVector &RHS) { LHS.swap(RHS); } -} +} // end namespace std -#endif +#endif // LLVM_ADT_BITVECTOR_H diff --git a/include/llvm/ADT/BitmaskEnum.h b/include/llvm/ADT/BitmaskEnum.h new file mode 100644 index 0000000000000..18c6ba5a3eb8b --- /dev/null +++ b/include/llvm/ADT/BitmaskEnum.h @@ -0,0 +1,153 @@ +//===-- llvm/ADT/BitmaskEnum.h ----------------------------------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_ADT_BITMASKENUM_H +#define LLVM_ADT_BITMASKENUM_H + +#include <cassert> +#include <type_traits> +#include <utility> + +#include "llvm/Support/MathExtras.h" + +/// LLVM_MARK_AS_BITMASK_ENUM lets you opt in an individual enum type so you can +/// perform bitwise operations on it without putting static_cast everywhere. +/// +/// \code +/// enum MyEnum { +/// E1 = 1, E2 = 2, E3 = 4, E4 = 8, +/// LLVM_MARK_AS_BITMASK_ENUM(/* LargestValue = */ E4) +/// }; +/// +/// void Foo() { +/// MyEnum A = (E1 | E2) & E3 ^ ~E4; // Look, ma: No static_cast! +/// } +/// \endcode +/// +/// Normally when you do a bitwise operation on an enum value, you get back an +/// instance of the underlying type (e.g. int). But using this macro, bitwise +/// ops on your enum will return you back instances of the enum. This is +/// particularly useful for enums which represent a combination of flags. +/// +/// The parameter to LLVM_MARK_AS_BITMASK_ENUM should be the largest individual +/// value in your enum. +/// +/// All of the enum's values must be non-negative. +#define LLVM_MARK_AS_BITMASK_ENUM(LargestValue) \ + LLVM_BITMASK_LARGEST_ENUMERATOR = LargestValue + +/// LLVM_ENABLE_BITMASK_ENUMS_IN_NAMESPACE() pulls the operator overloads used +/// by LLVM_MARK_AS_BITMASK_ENUM into the current namespace. +/// +/// Suppose you have an enum foo::bar::MyEnum. Before using +/// LLVM_MARK_AS_BITMASK_ENUM on MyEnum, you must put +/// LLVM_ENABLE_BITMASK_ENUMS_IN_NAMESPACE() somewhere inside namespace foo or +/// namespace foo::bar. This allows the relevant operator overloads to be found +/// by ADL. +/// +/// You don't need to use this macro in namespace llvm; it's done at the bottom +/// of this file. +#define LLVM_ENABLE_BITMASK_ENUMS_IN_NAMESPACE() \ + using ::llvm::BitmaskEnumDetail::operator~; \ + using ::llvm::BitmaskEnumDetail::operator|; \ + using ::llvm::BitmaskEnumDetail::operator&; \ + using ::llvm::BitmaskEnumDetail::operator^; \ + using ::llvm::BitmaskEnumDetail::operator|=; \ + using ::llvm::BitmaskEnumDetail::operator&=; \ + /* Force a semicolon at the end of this macro. */ \ + using ::llvm::BitmaskEnumDetail::operator^= + +namespace llvm { + +/// Traits class to determine whether an enum has a +/// LLVM_BITMASK_LARGEST_ENUMERATOR enumerator. +template <typename E, typename Enable = void> +struct is_bitmask_enum : std::false_type {}; + +template <typename E> +struct is_bitmask_enum< + E, typename std::enable_if<sizeof(E::LLVM_BITMASK_LARGEST_ENUMERATOR) >= + 0>::type> : std::true_type {}; +namespace BitmaskEnumDetail { + +/// Get a bitmask with 1s in all places up to the high-order bit of E's largest +/// value. +template <typename E> typename std::underlying_type<E>::type Mask() { + // On overflow, NextPowerOf2 returns zero with the type uint64_t, so + // subtracting 1 gives us the mask with all bits set, like we want. + return NextPowerOf2(static_cast<typename std::underlying_type<E>::type>( + E::LLVM_BITMASK_LARGEST_ENUMERATOR)) - + 1; +} + +/// Check that Val is in range for E, and return Val cast to E's underlying +/// type. +template <typename E> typename std::underlying_type<E>::type Underlying(E Val) { + auto U = static_cast<typename std::underlying_type<E>::type>(Val); + assert(U >= 0 && "Negative enum values are not allowed."); + assert(U <= Mask<E>() && "Enum value too large (or largest val too small?)"); + return U; +} + +template <typename E, + typename = typename std::enable_if<is_bitmask_enum<E>::value>::type> +E operator~(E Val) { + return static_cast<E>(~Underlying(Val) & Mask<E>()); +} + +template <typename E, + typename = typename std::enable_if<is_bitmask_enum<E>::value>::type> +E operator|(E LHS, E RHS) { + return static_cast<E>(Underlying(LHS) | Underlying(RHS)); +} + +template <typename E, + typename = typename std::enable_if<is_bitmask_enum<E>::value>::type> +E operator&(E LHS, E RHS) { + return static_cast<E>(Underlying(LHS) & Underlying(RHS)); +} + +template <typename E, + typename = typename std::enable_if<is_bitmask_enum<E>::value>::type> +E operator^(E LHS, E RHS) { + return static_cast<E>(Underlying(LHS) ^ Underlying(RHS)); +} + +// |=, &=, and ^= return a reference to LHS, to match the behavior of the +// operators on builtin types. + +template <typename E, + typename = typename std::enable_if<is_bitmask_enum<E>::value>::type> +E &operator|=(E &LHS, E RHS) { + LHS = LHS | RHS; + return LHS; +} + +template <typename E, + typename = typename std::enable_if<is_bitmask_enum<E>::value>::type> +E &operator&=(E &LHS, E RHS) { + LHS = LHS & RHS; + return LHS; +} + +template <typename E, + typename = typename std::enable_if<is_bitmask_enum<E>::value>::type> +E &operator^=(E &LHS, E RHS) { + LHS = LHS ^ RHS; + return LHS; +} + +} // namespace BitmaskEnumDetail + +// Enable bitmask enums in namespace ::llvm and all nested namespaces. +LLVM_ENABLE_BITMASK_ENUMS_IN_NAMESPACE(); + +} // namespace llvm + +#endif diff --git a/include/llvm/ADT/DenseMap.h b/include/llvm/ADT/DenseMap.h index 6ee1960b5c823..917c086beba34 100644 --- a/include/llvm/ADT/DenseMap.h +++ b/include/llvm/ADT/DenseMap.h @@ -81,11 +81,13 @@ public: } unsigned size() const { return getNumEntries(); } - /// Grow the densemap so that it has at least Size buckets. Does not shrink - void resize(size_type Size) { + /// Grow the densemap so that it can contain at least \p NumEntries items + /// before resizing again. + void reserve(size_type NumEntries) { + auto NumBuckets = getMinBucketToReserveForEntries(NumEntries); incrementEpoch(); - if (Size > getNumBuckets()) - grow(Size); + if (NumBuckets > getNumBuckets()) + grow(NumBuckets); } void clear() { @@ -195,6 +197,26 @@ public: true); } + /// Alternate version of insert() 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 <typename LookupKeyT> + std::pair<iterator, bool> insert_as(std::pair<KeyT, ValueT> &&KV, + const LookupKeyT &Val) { + BucketT *TheBucket; + if (LookupBucketFor(Val, TheBucket)) + 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), Val, + TheBucket); + return std::make_pair(iterator(TheBucket, getBucketsEnd(), *this, true), + true); + } + /// insert - Range insertion of pairs. template<typename InputIt> void insert(InputIt I, InputIt E) { @@ -285,6 +307,17 @@ protected: ::new (&B->getFirst()) KeyT(EmptyKey); } + /// Returns the number of buckets to allocate to ensure that the DenseMap can + /// accommodate \p NumEntries without need to grow(). + unsigned getMinBucketToReserveForEntries(unsigned NumEntries) { + // Ensure that "NumEntries * 4 < NumBuckets * 3" + if (NumEntries == 0) + return 0; + // +1 is required because of the strict equality. + // For example if NumEntries is 48, we need to return 401. + return NextPowerOf2(NumEntries * 4 / 3 + 1); + } + void moveFromOldBuckets(BucketT *OldBucketsBegin, BucketT *OldBucketsEnd) { initEmpty(); @@ -399,7 +432,7 @@ private: BucketT *InsertIntoBucket(const KeyT &Key, const ValueT &Value, BucketT *TheBucket) { - TheBucket = InsertIntoBucketImpl(Key, TheBucket); + TheBucket = InsertIntoBucketImpl(Key, Key, TheBucket); TheBucket->getFirst() = Key; ::new (&TheBucket->getSecond()) ValueT(Value); @@ -408,7 +441,7 @@ private: BucketT *InsertIntoBucket(const KeyT &Key, ValueT &&Value, BucketT *TheBucket) { - TheBucket = InsertIntoBucketImpl(Key, TheBucket); + TheBucket = InsertIntoBucketImpl(Key, Key, TheBucket); TheBucket->getFirst() = Key; ::new (&TheBucket->getSecond()) ValueT(std::move(Value)); @@ -416,14 +449,26 @@ private: } BucketT *InsertIntoBucket(KeyT &&Key, ValueT &&Value, BucketT *TheBucket) { - TheBucket = InsertIntoBucketImpl(Key, TheBucket); + TheBucket = InsertIntoBucketImpl(Key, Key, TheBucket); TheBucket->getFirst() = std::move(Key); ::new (&TheBucket->getSecond()) ValueT(std::move(Value)); return TheBucket; } - BucketT *InsertIntoBucketImpl(const KeyT &Key, BucketT *TheBucket) { + template <typename LookupKeyT> + BucketT *InsertIntoBucket(KeyT &&Key, ValueT &&Value, LookupKeyT &Lookup, + BucketT *TheBucket) { + TheBucket = InsertIntoBucketImpl(Key, Lookup, TheBucket); + + TheBucket->getFirst() = std::move(Key); + ::new (&TheBucket->getSecond()) ValueT(std::move(Value)); + return TheBucket; + } + + template <typename LookupKeyT> + BucketT *InsertIntoBucketImpl(const KeyT &Key, const LookupKeyT &Lookup, + BucketT *TheBucket) { incrementEpoch(); // If the load of the hash table is more than 3/4, or if fewer than 1/8 of @@ -439,12 +484,12 @@ private: unsigned NumBuckets = getNumBuckets(); if (LLVM_UNLIKELY(NewNumEntries * 4 >= NumBuckets * 3)) { this->grow(NumBuckets * 2); - LookupBucketFor(Key, TheBucket); + LookupBucketFor(Lookup, TheBucket); NumBuckets = getNumBuckets(); } else if (LLVM_UNLIKELY(NumBuckets-(NewNumEntries+getNumTombstones()) <= NumBuckets/8)) { this->grow(NumBuckets); - LookupBucketFor(Key, TheBucket); + LookupBucketFor(Lookup, TheBucket); } assert(TheBucket); @@ -550,9 +595,9 @@ class DenseMap : public DenseMapBase<DenseMap<KeyT, ValueT, KeyInfoT, BucketT>, unsigned NumBuckets; public: - explicit DenseMap(unsigned NumInitBuckets = 0) { - init(NumInitBuckets); - } + /// Create a DenseMap wth an optional \p InitialReserve that guarantee that + /// this number of elements can be inserted in the map without grow() + explicit DenseMap(unsigned InitialReserve = 0) { init(InitialReserve); } DenseMap(const DenseMap &other) : BaseT() { init(0); @@ -566,7 +611,7 @@ public: template<typename InputIt> DenseMap(const InputIt &I, const InputIt &E) { - init(NextPowerOf2(std::distance(I, E))); + init(std::distance(I, E)); this->insert(I, E); } @@ -609,7 +654,8 @@ public: } } - void init(unsigned InitBuckets) { + void init(unsigned InitNumEntries) { + auto InitBuckets = BaseT::getMinBucketToReserveForEntries(InitNumEntries); if (allocateBuckets(InitBuckets)) { this->BaseT::initEmpty(); } else { diff --git a/include/llvm/ADT/DenseMapInfo.h b/include/llvm/ADT/DenseMapInfo.h index a844ebcccf5b8..18c692e0cbccb 100644 --- a/include/llvm/ADT/DenseMapInfo.h +++ b/include/llvm/ADT/DenseMapInfo.h @@ -30,6 +30,36 @@ struct DenseMapInfo { //static bool isEqual(const T &LHS, const T &RHS); }; +template <typename T> struct CachedHash { + CachedHash(T Val) : Val(std::move(Val)) { + Hash = DenseMapInfo<T>::getHashValue(Val); + } + CachedHash(T Val, unsigned Hash) : Val(std::move(Val)), Hash(Hash) {} + T Val; + unsigned Hash; +}; + +// Provide DenseMapInfo for all CachedHash<T>. +template <typename T> struct DenseMapInfo<CachedHash<T>> { + static CachedHash<T> getEmptyKey() { + T N = DenseMapInfo<T>::getEmptyKey(); + return {N, 0}; + } + static CachedHash<T> getTombstoneKey() { + T N = DenseMapInfo<T>::getTombstoneKey(); + return {N, 0}; + } + static unsigned getHashValue(CachedHash<T> Val) { + assert(!isEqual(Val, getEmptyKey()) && "Cannot hash the empty key!"); + assert(!isEqual(Val, getTombstoneKey()) && + "Cannot hash the tombstone key!"); + return Val.Hash; + } + static bool isEqual(CachedHash<T> A, CachedHash<T> B) { + return DenseMapInfo<T>::isEqual(A.Val, B.Val); + } +}; + // Provide DenseMapInfo for all pointers. template<typename T> struct DenseMapInfo<T*> { diff --git a/include/llvm/ADT/DenseSet.h b/include/llvm/ADT/DenseSet.h index ef09dce379801..3724a09623f3e 100644 --- a/include/llvm/ADT/DenseSet.h +++ b/include/llvm/ADT/DenseSet.h @@ -94,6 +94,7 @@ public: ValueT *operator->() { return &I->getFirst(); } Iterator& operator++() { ++I; return *this; } + Iterator operator++(int) { auto T = *this; ++I; return T; } bool operator==(const Iterator& X) const { return I == X.I; } bool operator!=(const Iterator& X) const { return I != X.I; } }; @@ -115,6 +116,7 @@ public: const ValueT *operator->() { return &I->getFirst(); } ConstIterator& operator++() { ++I; return *this; } + ConstIterator operator++(int) { auto T = *this; ++I; return T; } bool operator==(const ConstIterator& X) const { return I == X.I; } bool operator!=(const ConstIterator& X) const { return I != X.I; } }; @@ -152,6 +154,19 @@ public: return TheMap.insert(std::make_pair(V, Empty)); } + /// Alternative version of insert that uses a different (and possibly less + /// expensive) key type. + template <typename LookupKeyT> + std::pair<iterator, bool> insert_as(const ValueT &V, + const LookupKeyT &LookupKey) { + return insert_as(ValueT(V), LookupKey); + } + template <typename LookupKeyT> + std::pair<iterator, bool> insert_as(ValueT &&V, const LookupKeyT &LookupKey) { + detail::DenseSetEmpty Empty; + return TheMap.insert_as(std::make_pair(std::move(V), Empty), LookupKey); + } + // Range insertion of values. template<typename InputIt> void insert(InputIt I, InputIt E) { diff --git a/include/llvm/ADT/FoldingSet.h b/include/llvm/ADT/FoldingSet.h index c9205396591b8..f16258af4ae29 100644 --- a/include/llvm/ADT/FoldingSet.h +++ b/include/llvm/ADT/FoldingSet.h @@ -17,10 +17,8 @@ #define LLVM_ADT_FOLDINGSET_H #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 { /// This folding set used for two purposes: @@ -98,6 +96,7 @@ namespace llvm { /// The result indicates whether the node existed in the folding set. class FoldingSetNodeID; +class StringRef; //===----------------------------------------------------------------------===// /// FoldingSetImpl - Implements the folding set functionality. The main @@ -181,11 +180,26 @@ public: /// empty - Returns true if there are no nodes in the folding set. bool empty() const { return NumNodes == 0; } + /// reserve - Increase the number of buckets such that adding the + /// EltCount-th node won't cause a rebucket operation. reserve is permitted + /// to allocate more space than requested by EltCount. + void reserve(unsigned EltCount); + /// capacity - Returns the number of nodes permitted in the folding set + /// before a rebucket operation is performed. + unsigned capacity() { + // We allow a load factor of up to 2.0, + // so that means our capacity is NumBuckets * 2 + return NumBuckets * 2; + } + private: /// GrowHashTable - Double the size of the hash table and rehash everything. - /// void GrowHashTable(); + /// GrowBucketCount - resize the hash table and rehash everything. + /// NewBucketCount must be a power of two, and must be greater than the old + /// bucket count. + void GrowBucketCount(unsigned NewBucketCount); protected: /// GetNodeProfile - Instantiations of the FoldingSet template implement /// this function to gather data bits for the given node. diff --git a/include/llvm/ADT/Hashing.h b/include/llvm/ADT/Hashing.h index de56f91eddb15..c3b574102f69d 100644 --- a/include/llvm/ADT/Hashing.h +++ b/include/llvm/ADT/Hashing.h @@ -52,7 +52,6 @@ #include <algorithm> #include <cassert> #include <cstring> -#include <iterator> #include <string> #include <utility> @@ -632,7 +631,8 @@ inline hash_code hash_integer_value(uint64_t value) { template <typename T> typename std::enable_if<is_integral_or_enum<T>::value, hash_code>::type hash_value(T value) { - return ::llvm::hashing::detail::hash_integer_value(value); + return ::llvm::hashing::detail::hash_integer_value( + static_cast<uint64_t>(value)); } // Declared and documented above, but defined here so that any of the hashing diff --git a/include/llvm/ADT/PointerEmbeddedInt.h b/include/llvm/ADT/PointerEmbeddedInt.h index 8781d1803ac74..2279d43405fa7 100644 --- a/include/llvm/ADT/PointerEmbeddedInt.h +++ b/include/llvm/ADT/PointerEmbeddedInt.h @@ -11,6 +11,7 @@ #define LLVM_ADT_POINTEREMBEDDEDINT_H #include "llvm/ADT/DenseMapInfo.h" +#include "llvm/Support/MathExtras.h" #include "llvm/Support/PointerLikeTypeTraits.h" #include <climits> @@ -30,6 +31,8 @@ template <typename IntT, int Bits = sizeof(IntT) * CHAR_BIT> class PointerEmbeddedInt { uintptr_t Value; + // Note: This '<' is correct; using '<=' would result in some shifts + // overflowing their storage types. static_assert(Bits < sizeof(uintptr_t) * CHAR_BIT, "Cannot embed more bits than we have in a pointer!"); @@ -42,25 +45,36 @@ class PointerEmbeddedInt { Mask = static_cast<uintptr_t>(-1) << Bits }; + struct RawValueTag { + explicit RawValueTag() = default; + }; + friend class PointerLikeTypeTraits<PointerEmbeddedInt>; - explicit PointerEmbeddedInt(uintptr_t Value) : Value(Value) {} + explicit PointerEmbeddedInt(uintptr_t Value, RawValueTag) : Value(Value) {} public: PointerEmbeddedInt() : Value(0) {} - PointerEmbeddedInt(IntT I) : Value(static_cast<uintptr_t>(I) << Shift) { - assert((I & Mask) == 0 && "Integer has bits outside those preserved!"); + PointerEmbeddedInt(IntT I) { + *this = I; } PointerEmbeddedInt &operator=(IntT I) { - assert((I & Mask) == 0 && "Integer has bits outside those preserved!"); + assert((std::is_signed<IntT>::value ? llvm::isInt<Bits>(I) + : llvm::isUInt<Bits>(I)) && + "Integer has bits outside those preserved!"); Value = static_cast<uintptr_t>(I) << Shift; + return *this; } - // Note that this imilict conversion additionally allows all of the basic + // Note that this implicit conversion additionally allows all of the basic // comparison operators to work transparently, etc. - operator IntT() const { return static_cast<IntT>(Value >> Shift); } + operator IntT() const { + if (std::is_signed<IntT>::value) + return static_cast<IntT>(static_cast<intptr_t>(Value) >> Shift); + return static_cast<IntT>(Value >> Shift); + } }; // Provide pointer like traits to support use with pointer unions and sum @@ -74,10 +88,10 @@ public: return reinterpret_cast<void *>(P.Value); } static inline T getFromVoidPointer(void *P) { - return T(reinterpret_cast<uintptr_t>(P)); + return T(reinterpret_cast<uintptr_t>(P), typename T::RawValueTag()); } static inline T getFromVoidPointer(const void *P) { - return T(reinterpret_cast<uintptr_t>(P)); + return T(reinterpret_cast<uintptr_t>(P), typename T::RawValueTag()); } enum { NumLowBitsAvailable = T::Shift }; diff --git a/include/llvm/ADT/PostOrderIterator.h b/include/llvm/ADT/PostOrderIterator.h index ce343a161b7b2..0cc504b5c39e6 100644 --- a/include/llvm/ADT/PostOrderIterator.h +++ b/include/llvm/ADT/PostOrderIterator.h @@ -28,7 +28,7 @@ namespace llvm { // visited nodes during the po_iterator's depth-first traversal. // // The default implementation simply contains a set of visited nodes, while -// the Extended=true version uses a reference to an external set. +// the External=true version uses a reference to an external set. // // It is possible to prune the depth-first traversal in several ways: // diff --git a/include/llvm/ADT/PriorityWorklist.h b/include/llvm/ADT/PriorityWorklist.h new file mode 100644 index 0000000000000..00549b88fd027 --- /dev/null +++ b/include/llvm/ADT/PriorityWorklist.h @@ -0,0 +1,224 @@ +//===- PriorityWorklist.h - Worklist with insertion priority ----*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +/// +/// \file +/// +/// This file provides a priority worklist. See the class comments for details. +/// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_ADT_PRIORITYWORKLIST_H +#define LLVM_ADT_PRIORITYWORKLIST_H + +#include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/SmallVector.h" +#include <algorithm> +#include <cassert> +#include <utility> +#include <vector> + +namespace llvm { + +/// A FILO worklist that prioritizes on re-insertion without duplication. +/// +/// This is very similar to a \c SetVector with the primary difference that +/// while re-insertion does not create a duplicate, it does adjust the +/// visitation order to respect the last insertion point. This can be useful +/// when the visit order needs to be prioritized based on insertion point +/// without actually having duplicate visits. +/// +/// Note that this doesn't prevent re-insertion of elements which have been +/// visited -- if you need to break cycles, a set will still be necessary. +/// +/// The type \c T must be default constructable to a null value that will be +/// ignored. It is an error to insert such a value, and popping elements will +/// never produce such a value. It is expected to be used with common nullable +/// types like pointers or optionals. +/// +/// Internally this uses a vector to store the worklist and a map to identify +/// existing elements in the worklist. Both of these may be customized, but the +/// map must support the basic DenseMap API for mapping from a T to an integer +/// index into the vector. +/// +/// A partial specialization is provided to automatically select a SmallVector +/// and a SmallDenseMap if custom data structures are not provided. +template <typename T, typename VectorT = std::vector<T>, + typename MapT = DenseMap<T, ptrdiff_t>> +class PriorityWorklist { +public: + typedef T value_type; + typedef T key_type; + typedef T& reference; + typedef const T& const_reference; + typedef typename MapT::size_type size_type; + + /// Construct an empty PriorityWorklist + PriorityWorklist() {} + + /// Determine if the PriorityWorklist is empty or not. + bool empty() const { + return V.empty(); + } + + /// Returns the number of elements in the worklist. + size_type size() const { + return M.size(); + } + + /// Count the number of elements of a given key in the PriorityWorklist. + /// \returns 0 if the element is not in the PriorityWorklist, 1 if it is. + size_type count(const key_type &key) const { + return M.count(key); + } + + /// Return the last element of the PriorityWorklist. + const T &back() const { + assert(!empty() && "Cannot call back() on empty PriorityWorklist!"); + return V.back(); + } + + /// Insert a new element into the PriorityWorklist. + /// \returns true if the element was inserted into the PriorityWorklist. + bool insert(const T &X) { + assert(X != T() && "Cannot insert a null (default constructed) value!"); + auto InsertResult = M.insert({X, V.size()}); + if (InsertResult.second) { + // Fresh value, just append it to the vector. + V.push_back(X); + return true; + } + + auto &Index = InsertResult.first->second; + assert(V[Index] == X && "Value not actually at index in map!"); + if (Index != (ptrdiff_t)(V.size() - 1)) { + // If the element isn't at the back, null it out and append a fresh one. + V[Index] = T(); + Index = (ptrdiff_t)V.size(); + V.push_back(X); + } + return false; + } + + /// Remove the last element of the PriorityWorklist. + void pop_back() { + assert(!empty() && "Cannot remove an element when empty!"); + assert(back() != T() && "Cannot have a null element at the back!"); + M.erase(back()); + do { + V.pop_back(); + } while (!V.empty() && V.back() == T()); + } + + T LLVM_ATTRIBUTE_UNUSED_RESULT pop_back_val() { + T Ret = back(); + pop_back(); + return Ret; + } + + /// Erase an item from the worklist. + /// + /// Note that this is constant time due to the nature of the worklist implementation. + bool erase(const T& X) { + auto I = M.find(X); + if (I == M.end()) + return false; + + assert(V[I->second] == X && "Value not actually at index in map!"); + if (I->second == (ptrdiff_t)(V.size() - 1)) { + do { + V.pop_back(); + } while (!V.empty() && V.back() == T()); + } else { + V[I->second] = T(); + } + M.erase(I); + return true; + } + + /// Erase items from the set vector based on a predicate function. + /// + /// This is intended to be equivalent to the following code, if we could + /// write it: + /// + /// \code + /// V.erase(std::remove_if(V.begin(), V.end(), P), V.end()); + /// \endcode + /// + /// However, PriorityWorklist doesn't expose non-const iterators, making any + /// algorithm like remove_if impossible to use. + /// + /// \returns true if any element is removed. + template <typename UnaryPredicate> + bool erase_if(UnaryPredicate P) { + typename VectorT::iterator E = std::remove_if( + V.begin(), V.end(), TestAndEraseFromMap<UnaryPredicate>(P, M)); + if (E == V.end()) + return false; + for (auto I = V.begin(); I != E; ++I) + if (*I != T()) + M[*I] = I - V.begin(); + V.erase(E, V.end()); + return true; + } + + /// Completely clear the PriorityWorklist + void clear() { + M.clear(); + V.clear(); + } + +private: + /// A wrapper predicate designed for use with std::remove_if. + /// + /// This predicate wraps a predicate suitable for use with std::remove_if to + /// call M.erase(x) on each element which is slated for removal. This just + /// allows the predicate to be move only which we can't do with lambdas + /// today. + template <typename UnaryPredicateT> + class TestAndEraseFromMap { + UnaryPredicateT P; + MapT &M; + + public: + TestAndEraseFromMap(UnaryPredicateT P, MapT &M) + : P(std::move(P)), M(M) {} + + bool operator()(const T &Arg) { + if (Arg == T()) + // Skip null values in the PriorityWorklist. + return false; + + if (P(Arg)) { + M.erase(Arg); + return true; + } + return false; + } + }; + + /// The map from value to index in the vector. + MapT M; + + /// The vector of elements in insertion order. + VectorT V; +}; + +/// A version of \c PriorityWorklist that selects small size optimized data +/// structures for the vector and map. +template <typename T, unsigned N> +class SmallPriorityWorklist + : public PriorityWorklist<T, SmallVector<T, N>, + SmallDenseMap<T, ptrdiff_t>> { +public: + SmallPriorityWorklist() {} +}; + +} + +#endif diff --git a/include/llvm/ADT/STLExtras.h b/include/llvm/ADT/STLExtras.h index d4360fa8d218d..abd39dacc6713 100644 --- a/include/llvm/ADT/STLExtras.h +++ b/include/llvm/ADT/STLExtras.h @@ -17,7 +17,6 @@ #ifndef LLVM_ADT_STLEXTRAS_H #define LLVM_ADT_STLEXTRAS_H -#include "llvm/Support/Compiler.h" #include <algorithm> // for std::all_of #include <cassert> #include <cstddef> // for std::size_t @@ -27,6 +26,9 @@ #include <memory> #include <utility> // for std::pair +#include "llvm/ADT/iterator_range.h" +#include "llvm/Support/Compiler.h" + namespace llvm { //===----------------------------------------------------------------------===// @@ -117,7 +119,9 @@ public: iterator_category; typedef typename std::iterator_traits<RootIt>::difference_type difference_type; - typedef typename UnaryFunc::result_type value_type; + typedef typename std::result_of< + UnaryFunc(decltype(*std::declval<RootIt>()))> + ::type value_type; typedef void pointer; //typedef typename UnaryFunc::result_type *pointer; @@ -379,6 +383,14 @@ bool any_of(R &&Range, UnaryPredicate &&P) { std::forward<UnaryPredicate>(P)); } +/// Provide wrappers to std::none_of which take ranges instead of having to pass +/// begin/end explicitly. +template <typename R, class UnaryPredicate> +bool none_of(R &&Range, UnaryPredicate &&P) { + return std::none_of(Range.begin(), Range.end(), + std::forward<UnaryPredicate>(P)); +} + /// Provide wrappers to std::find which take ranges instead of having to pass /// begin/end explicitly. template<typename R, class T> @@ -386,6 +398,43 @@ auto find(R &&Range, const T &val) -> decltype(Range.begin()) { return std::find(Range.begin(), Range.end(), val); } +/// Provide wrappers to std::find_if which take ranges instead of having to pass +/// begin/end explicitly. +template <typename R, class T> +auto find_if(R &&Range, const T &Pred) -> decltype(Range.begin()) { + return std::find_if(Range.begin(), Range.end(), Pred); +} + +/// Provide wrappers to std::remove_if which take ranges instead of having to +/// pass begin/end explicitly. +template<typename R, class UnaryPredicate> +auto remove_if(R &&Range, UnaryPredicate &&P) -> decltype(Range.begin()) { + return std::remove_if(Range.begin(), Range.end(), P); +} + +/// Wrapper function around std::find to detect if an element exists +/// in a container. +template <typename R, typename E> +bool is_contained(R &&Range, const E &Element) { + return std::find(Range.begin(), Range.end(), Element) != Range.end(); +} + +/// Wrapper function around std::count_if to count the number of times an +/// element satisfying a given predicate occurs in a range. +template <typename R, typename UnaryPredicate> +auto count_if(R &&Range, UnaryPredicate &&P) + -> typename std::iterator_traits<decltype(Range.begin())>::difference_type { + return std::count_if(Range.begin(), Range.end(), P); +} + +/// Wrapper function around std::transform to apply a function to a range and +/// store the result elsewhere. +template <typename R, class OutputIt, typename UnaryPredicate> +OutputIt transform(R &&Range, OutputIt d_first, UnaryPredicate &&P) { + return std::transform(Range.begin(), Range.end(), d_first, + std::forward<UnaryPredicate>(P)); +} + //===----------------------------------------------------------------------===// // Extra additions to <memory> //===----------------------------------------------------------------------===// diff --git a/include/llvm/ADT/Sequence.h b/include/llvm/ADT/Sequence.h new file mode 100644 index 0000000000000..5d36831cc128e --- /dev/null +++ b/include/llvm/ADT/Sequence.h @@ -0,0 +1,79 @@ +//===- Sequence.h - Utility for producing sequences of values ---*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +/// \file +/// This routine provides some synthesis utilities to produce sequences of +/// values. The names are intentionally kept very short as they tend to occur +/// in common and widely used contexts. +/// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_ADT_SEQ_H +#define LLVM_ADT_SEQ_H + +#include "llvm/ADT/iterator.h" +#include "llvm/ADT/iterator_range.h" + +namespace llvm { + +namespace detail { +template <typename ValueT> +class value_sequence_iterator + : public iterator_facade_base<value_sequence_iterator<ValueT>, + std::random_access_iterator_tag, + const ValueT> { + typedef typename value_sequence_iterator::iterator_facade_base BaseT; + + ValueT Value; + +public: + typedef typename BaseT::difference_type difference_type; + typedef typename BaseT::reference reference; + + value_sequence_iterator() = default; + value_sequence_iterator(const value_sequence_iterator &) = default; + value_sequence_iterator(value_sequence_iterator &&Arg) + : Value(std::move(Arg.Value)) {} + + template <typename U, typename Enabler = decltype(ValueT(std::declval<U>()))> + value_sequence_iterator(U &&Value) : Value(std::forward<U>(Value)) {} + + value_sequence_iterator &operator+=(difference_type N) { + Value += N; + return *this; + } + value_sequence_iterator &operator-=(difference_type N) { + Value -= N; + return *this; + } + using BaseT::operator-; + difference_type operator-(const value_sequence_iterator &RHS) const { + return Value - RHS.Value; + } + + bool operator==(const value_sequence_iterator &RHS) const { + return Value == RHS.Value; + } + bool operator<(const value_sequence_iterator &RHS) const { + return Value < RHS.Value; + } + + reference operator*() const { return Value; } +}; +} // End detail namespace. + +template <typename ValueT> +iterator_range<detail::value_sequence_iterator<ValueT>> seq(ValueT Begin, + ValueT End) { + return make_range(detail::value_sequence_iterator<ValueT>(Begin), + detail::value_sequence_iterator<ValueT>(End)); +} + +} + +#endif diff --git a/include/llvm/ADT/SetVector.h b/include/llvm/ADT/SetVector.h index bc563570c2030..2bb0fdbd33709 100644 --- a/include/llvm/ADT/SetVector.h +++ b/include/llvm/ADT/SetVector.h @@ -24,6 +24,7 @@ #include "llvm/ADT/SmallSet.h" #include <algorithm> #include <cassert> +#include <utility> #include <vector> namespace llvm { @@ -123,7 +124,7 @@ public: } /// \brief Insert a new element into the SetVector. - /// \returns true iff the element was inserted into the SetVector. + /// \returns true if the element was inserted into the SetVector. bool insert(const value_type &X) { bool result = set_.insert(X).second; if (result) @@ -151,6 +152,24 @@ public: return false; } + /// Erase a single element from the set vector. + /// \returns an iterator pointing to the next element that followed the + /// element erased. This is the end of the SetVector if the last element is + /// erased. + iterator erase(iterator I) { + const key_type &V = *I; + assert(set_.count(V) && "Corrupted SetVector instances!"); + set_.erase(V); + + // FIXME: No need to use the non-const iterator when built with + // std:vector.erase(const_iterator) as defined in C++11. This is for + // compatibility with non-standard libstdc++ up to 4.8 (fixed in 4.9). + auto NI = vector_.begin(); + std::advance(NI, std::distance<iterator>(NI, I)); + + return vector_.erase(NI); + } + /// \brief Remove items from the set vector based on a predicate function. /// /// This is intended to be equivalent to the following code, if we could @@ -207,6 +226,31 @@ public: bool operator!=(const SetVector &that) const { return vector_ != that.vector_; } + + /// \brief Compute This := This u S, return whether 'This' changed. + /// TODO: We should be able to use set_union from SetOperations.h, but + /// SetVector interface is inconsistent with DenseSet. + template <class STy> + bool set_union(const STy &S) { + bool Changed = false; + + for (typename STy::const_iterator SI = S.begin(), SE = S.end(); SI != SE; + ++SI) + if (insert(*SI)) + Changed = true; + + return Changed; + } + + /// \brief Compute This := This - B + /// TODO: We should be able to use set_subtract from SetOperations.h, but + /// SetVector interface is inconsistent with DenseSet. + template <class STy> + void set_subtract(const STy &S) { + for (typename STy::const_iterator SI = S.begin(), SE = S.end(); SI != SE; + ++SI) + remove(*SI); + } private: /// \brief A wrapper predicate designed for use with std::remove_if. @@ -219,7 +263,8 @@ private: set_type &set_; public: - TestAndEraseFromSet(UnaryPredicate P, set_type &set_) : P(P), set_(set_) {} + TestAndEraseFromSet(UnaryPredicate P, set_type &set_) + : P(std::move(P)), set_(set_) {} template <typename ArgumentT> bool operator()(const ArgumentT &Arg) { diff --git a/include/llvm/ADT/SmallBitVector.h b/include/llvm/ADT/SmallBitVector.h index 4aa3bc217f41b..bb99e0cf221f7 100644 --- a/include/llvm/ADT/SmallBitVector.h +++ b/include/llvm/ADT/SmallBitVector.h @@ -15,19 +15,16 @@ #define LLVM_ADT_SMALLBITVECTOR_H #include "llvm/ADT/BitVector.h" -#include "llvm/Support/Compiler.h" #include "llvm/Support/MathExtras.h" #include <cassert> namespace llvm { -/// SmallBitVector - This is a 'bitvector' (really, a variable-sized bit array), -/// optimized for the case when the array is small. It contains one -/// pointer-sized field, which is directly used as a plain collection of bits -/// when possible, or as a pointer to a larger heap-allocated array when -/// necessary. This allows normal "small" cases to be fast without losing -/// generality for large inputs. -/// +/// This is a 'bitvector' (really, a variable-sized bit array), optimized for +/// the case when the array is small. It contains one pointer-sized field, which +/// is directly used as a plain collection of bits when possible, or as a +/// pointer to a larger heap-allocated array when necessary. This allows normal +/// "small" cases to be fast without losing generality for large inputs. class SmallBitVector { // TODO: In "large" mode, a pointer to a BitVector is used, leading to an // unnecessary level of indirection. It would be more efficient to use a @@ -139,11 +136,11 @@ private: } public: - /// SmallBitVector default ctor - Creates an empty bitvector. + /// Creates an empty bitvector. SmallBitVector() : X(1) {} - /// SmallBitVector ctor - Creates a bitvector of specified number of bits. All - /// bits are initialized to the specified value. + /// Creates a bitvector of specified number of bits. All bits are initialized + /// to the specified value. explicit SmallBitVector(unsigned s, bool t = false) { if (s <= SmallNumDataBits) switchToSmall(t ? ~uintptr_t(0) : 0, s); @@ -168,17 +165,17 @@ public: delete getPointer(); } - /// empty - Tests whether there are no bits in this bitvector. + /// Tests whether there are no bits in this bitvector. bool empty() const { return isSmall() ? getSmallSize() == 0 : getPointer()->empty(); } - /// size - Returns the number of bits in this bitvector. + /// Returns the number of bits in this bitvector. size_t size() const { return isSmall() ? getSmallSize() : getPointer()->size(); } - /// count - Returns the number of bits which are set. + /// Returns the number of bits which are set. size_type count() const { if (isSmall()) { uintptr_t Bits = getSmallBits(); @@ -187,29 +184,28 @@ public: return getPointer()->count(); } - /// any - Returns true if any bit is set. + /// Returns true if any bit is set. bool any() const { if (isSmall()) return getSmallBits() != 0; return getPointer()->any(); } - /// all - Returns true if all bits are set. + /// Returns true if all bits are set. bool all() const { if (isSmall()) return getSmallBits() == (uintptr_t(1) << getSmallSize()) - 1; return getPointer()->all(); } - /// none - Returns true if none of the bits are set. + /// Returns true if none of the bits are set. bool none() const { if (isSmall()) return getSmallBits() == 0; return getPointer()->none(); } - /// find_first - Returns the index of the first set bit, -1 if none - /// of the bits are set. + /// Returns the index of the first set bit, -1 if none of the bits are set. int find_first() const { if (isSmall()) { uintptr_t Bits = getSmallBits(); @@ -220,8 +216,8 @@ public: return getPointer()->find_first(); } - /// find_next - Returns the index of the next set bit following the - /// "Prev" bit. Returns -1 if the next set bit is not found. + /// Returns the index of the next set bit following the "Prev" bit. + /// Returns -1 if the next set bit is not found. int find_next(unsigned Prev) const { if (isSmall()) { uintptr_t Bits = getSmallBits(); @@ -234,14 +230,14 @@ public: return getPointer()->find_next(Prev); } - /// clear - Clear all bits. + /// Clear all bits. void clear() { if (!isSmall()) delete getPointer(); switchToSmall(0, 0); } - /// resize - Grow or shrink the bitvector. + /// Grow or shrink the bitvector. void resize(unsigned N, bool t = false) { if (!isSmall()) { getPointer()->resize(N, t); @@ -296,7 +292,7 @@ public: return *this; } - /// set - Efficiently set a range of bits in [I, E) + /// Efficiently set a range of bits in [I, E) SmallBitVector &set(unsigned I, unsigned E) { assert(I <= E && "Attempted to set backwards range!"); assert(E <= size() && "Attempted to set out-of-bounds range!"); @@ -327,7 +323,7 @@ public: return *this; } - /// reset - Efficiently reset a range of bits in [I, E) + /// Efficiently reset a range of bits in [I, E) SmallBitVector &reset(unsigned I, unsigned E) { assert(I <= E && "Attempted to reset backwards range!"); assert(E <= size() && "Attempted to reset out-of-bounds range!"); @@ -422,7 +418,7 @@ public: return *this; } - /// reset - Reset bits that are set in RHS. Same as *this &= ~RHS. + /// Reset bits that are set in RHS. Same as *this &= ~RHS. SmallBitVector &reset(const SmallBitVector &RHS) { if (isSmall() && RHS.isSmall()) setSmallBits(getSmallBits() & ~RHS.getSmallBits()); @@ -436,8 +432,7 @@ public: return *this; } - /// test - Check if (This - RHS) is zero. - /// This is the same as reset(RHS) and any(). + /// Check if (This - RHS) is zero. This is the same as reset(RHS) and any(). bool test(const SmallBitVector &RHS) const { if (isSmall() && RHS.isSmall()) return (getSmallBits() & ~RHS.getSmallBits()) != 0; @@ -514,7 +509,7 @@ public: std::swap(X, RHS.X); } - /// setBitsInMask - Add '1' bits from Mask to this vector. Don't resize. + /// Add '1' bits from Mask to this vector. Don't resize. /// This computes "*this |= Mask". void setBitsInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) { if (isSmall()) @@ -523,8 +518,8 @@ public: getPointer()->setBitsInMask(Mask, MaskWords); } - /// clearBitsInMask - Clear any bits in this vector that are set in Mask. - /// Don't resize. This computes "*this &= ~Mask". + /// Clear any bits in this vector that are set in Mask. Don't resize. + /// This computes "*this &= ~Mask". void clearBitsInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) { if (isSmall()) applyMask<false, false>(Mask, MaskWords); @@ -532,8 +527,8 @@ public: getPointer()->clearBitsInMask(Mask, MaskWords); } - /// setBitsNotInMask - Add a bit to this vector for every '0' bit in Mask. - /// Don't resize. This computes "*this |= ~Mask". + /// Add a bit to this vector for every '0' bit in Mask. Don't resize. + /// This computes "*this |= ~Mask". void setBitsNotInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) { if (isSmall()) applyMask<true, true>(Mask, MaskWords); @@ -541,8 +536,8 @@ public: getPointer()->setBitsNotInMask(Mask, MaskWords); } - /// clearBitsNotInMask - Clear a bit in this vector for every '0' bit in Mask. - /// Don't resize. This computes "*this &= Mask". + /// Clear a bit in this vector for every '0' bit in Mask. Don't resize. + /// This computes "*this &= Mask". void clearBitsNotInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) { if (isSmall()) applyMask<false, true>(Mask, MaskWords); diff --git a/include/llvm/ADT/SmallPtrSet.h b/include/llvm/ADT/SmallPtrSet.h index 3d98e8fac43b6..eaed6aa05dcbc 100644 --- a/include/llvm/ADT/SmallPtrSet.h +++ b/include/llvm/ADT/SmallPtrSet.h @@ -21,6 +21,7 @@ #include <cassert> #include <cstddef> #include <cstring> +#include <cstdlib> #include <iterator> #include <utility> @@ -58,36 +59,45 @@ protected: /// CurArraySize - The allocated size of CurArray, always a power of two. unsigned CurArraySize; - // If small, this is # elts allocated consecutively - unsigned NumElements; + /// Number of elements in CurArray that contain a value or are a tombstone. + /// If small, all these elements are at the beginning of CurArray and the rest + /// is uninitialized. + unsigned NumNonEmpty; + /// Number of tombstones in CurArray. unsigned NumTombstones; // Helpers to copy and move construct a SmallPtrSet. - SmallPtrSetImplBase(const void **SmallStorage, const SmallPtrSetImplBase &that); + SmallPtrSetImplBase(const void **SmallStorage, + const SmallPtrSetImplBase &that); SmallPtrSetImplBase(const void **SmallStorage, unsigned SmallSize, - SmallPtrSetImplBase &&that); - explicit SmallPtrSetImplBase(const void **SmallStorage, unsigned SmallSize) : - SmallArray(SmallStorage), CurArray(SmallStorage), CurArraySize(SmallSize) { + SmallPtrSetImplBase &&that); + explicit SmallPtrSetImplBase(const void **SmallStorage, unsigned SmallSize) + : SmallArray(SmallStorage), CurArray(SmallStorage), + CurArraySize(SmallSize), NumNonEmpty(0), NumTombstones(0) { assert(SmallSize && (SmallSize & (SmallSize-1)) == 0 && "Initial size must be a power of two!"); - clear(); } - ~SmallPtrSetImplBase(); + ~SmallPtrSetImplBase() { + if (!isSmall()) + free(CurArray); + } public: typedef unsigned size_type; bool LLVM_ATTRIBUTE_UNUSED_RESULT empty() const { return size() == 0; } - size_type size() const { return NumElements; } + size_type size() const { return NumNonEmpty - NumTombstones; } void clear() { // If the capacity of the array is huge, and the # elements used is small, // shrink the array. - if (!isSmall() && NumElements*4 < CurArraySize && CurArraySize > 32) - return shrink_and_clear(); + if (!isSmall()) { + if (size() * 4 < CurArraySize && CurArraySize > 32) + return shrink_and_clear(); + // Fill the array with empty markers. + memset(CurArray, -1, CurArraySize * sizeof(void *)); + } - // Fill the array with empty markers. - memset(CurArray, -1, CurArraySize*sizeof(void*)); - NumElements = 0; + NumNonEmpty = 0; NumTombstones = 0; } @@ -99,10 +109,42 @@ protected: return reinterpret_cast<void*>(-1); } + const void **EndPointer() const { + return isSmall() ? CurArray + NumNonEmpty : CurArray + CurArraySize; + } + /// 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. - std::pair<const void *const *, bool> insert_imp(const void *Ptr); + std::pair<const void *const *, bool> insert_imp(const void *Ptr) { + if (isSmall()) { + // Check to see if it is already in the set. + const void **LastTombstone = nullptr; + for (const void **APtr = SmallArray, **E = SmallArray + NumNonEmpty; + APtr != E; ++APtr) { + const void *Value = *APtr; + if (Value == Ptr) + return std::make_pair(APtr, false); + if (Value == getTombstoneMarker()) + LastTombstone = APtr; + } + + // Did we find any tombstone marker? + if (LastTombstone != nullptr) { + *LastTombstone = Ptr; + --NumTombstones; + return std::make_pair(LastTombstone, true); + } + + // Nope, there isn't. If we stay small, just 'pushback' now. + if (NumNonEmpty < CurArraySize) { + SmallArray[NumNonEmpty++] = Ptr; + return std::make_pair(SmallArray + (NumNonEmpty - 1), true); + } + // Otherwise, hit the big set case, which will call grow. + } + return insert_imp_big(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 @@ -114,7 +156,7 @@ protected: if (isSmall()) { // Linear search for the item. for (const void *const *APtr = SmallArray, - *const *E = SmallArray+NumElements; APtr != E; ++APtr) + *const *E = SmallArray + NumNonEmpty; APtr != E; ++APtr) if (*APtr == Ptr) return true; return false; @@ -127,6 +169,8 @@ protected: private: bool isSmall() const { return CurArray == SmallArray; } + std::pair<const void *const *, bool> insert_imp_big(const void *Ptr); + const void * const *FindBucketFor(const void *Ptr) const; void shrink_and_clear(); @@ -142,6 +186,12 @@ protected: void CopyFrom(const SmallPtrSetImplBase &RHS); void MoveFrom(unsigned SmallSize, SmallPtrSetImplBase &&RHS); + +private: + /// Code shared by MoveFrom() and move constructor. + void MoveHelper(unsigned SmallSize, SmallPtrSetImplBase &&RHS); + /// Code shared by CopyFrom() and copy constructor. + void CopyHelper(const SmallPtrSetImplBase &RHS); }; /// SmallPtrSetIteratorImpl - This is the common base class shared between all @@ -154,7 +204,7 @@ protected: public: explicit SmallPtrSetIteratorImpl(const void *const *BP, const void*const *E) : Bucket(BP), End(E) { - AdvanceIfNotValid(); + AdvanceIfNotValid(); } bool operator==(const SmallPtrSetIteratorImpl &RHS) const { @@ -266,7 +316,7 @@ public: /// 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); + return std::make_pair(iterator(p.first, EndPointer()), p.second); } /// erase - If the set contains the specified pointer, remove it and return @@ -287,10 +337,11 @@ public: } inline iterator begin() const { - return iterator(CurArray, CurArray+CurArraySize); + return iterator(CurArray, EndPointer()); } inline iterator end() const { - return iterator(CurArray+CurArraySize, CurArray+CurArraySize); + const void *const *End = EndPointer(); + return iterator(End, End); } }; @@ -300,6 +351,11 @@ public: /// SmallPtrSetImplBase for details of the algorithm. template<class PtrType, unsigned SmallSize> class SmallPtrSet : public SmallPtrSetImpl<PtrType> { + // In small mode SmallPtrSet uses linear search for the elements, so it is + // not a good idea to choose this value too high. You may consider using a + // DenseSet<> instead if you expect many elements in the set. + static_assert(SmallSize <= 32, "SmallSize should be small"); + typedef SmallPtrSetImpl<PtrType> BaseT; // Make sure that SmallSize is a power of two, round up if not. diff --git a/include/llvm/ADT/SmallSet.h b/include/llvm/ADT/SmallSet.h index 39a57b87b2a71..aaa5ff0ae9395 100644 --- a/include/llvm/ADT/SmallSet.h +++ b/include/llvm/ADT/SmallSet.h @@ -38,6 +38,11 @@ class SmallSet { typedef typename SmallVector<T, N>::const_iterator VIterator; typedef typename SmallVector<T, N>::iterator mutable_iterator; + // In small mode SmallPtrSet uses linear search for the elements, so it is + // not a good idea to choose this value too high. You may consider using a + // DenseSet<> instead if you expect many elements in the set. + static_assert(N <= 32, "N should be small"); + public: typedef size_t size_type; SmallSet() {} diff --git a/include/llvm/ADT/SmallVector.h b/include/llvm/ADT/SmallVector.h index d1062acbbb615..42eedc63e0790 100644 --- a/include/llvm/ADT/SmallVector.h +++ b/include/llvm/ADT/SmallVector.h @@ -184,33 +184,12 @@ protected: } } - /// 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> - static It2 move(It1 I, It1 E, It2 Dest) { - for (; I != E; ++I, ++Dest) - *Dest = ::std::move(*I); - return Dest; - } - - /// 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. - template<typename It1, typename It2> - static It2 move_backward(It1 I, It1 E, It2 Dest) { - while (I != E) - *--Dest = ::std::move(*--E); - return Dest; - } - /// 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)); + std::uninitialized_copy(std::make_move_iterator(I), + std::make_move_iterator(E), Dest); } /// Copy the range [I, E) onto the uninitialized memory starting with "Dest", @@ -283,20 +262,6 @@ protected: // No need to do a destroy loop for POD's. static void destroy_range(T *, T *) {} - /// 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); - } - - /// 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); - } - /// Move the range [I, E) onto the uninitialized memory /// starting with "Dest", constructing elements into it as needed. template<typename It1, typename It2> @@ -356,6 +321,7 @@ class SmallVectorImpl : public SmallVectorTemplateBase<T, isPodLike<T>::value> { SmallVectorImpl(const SmallVectorImpl&) = delete; public: typedef typename SuperClass::iterator iterator; + typedef typename SuperClass::const_iterator const_iterator; typedef typename SuperClass::size_type size_type; protected: @@ -459,26 +425,33 @@ public: append(IL); } - iterator erase(iterator I) { + iterator erase(const_iterator CI) { + // Just cast away constness because this is a non-const member function. + iterator I = const_cast<iterator>(CI); + assert(I >= this->begin() && "Iterator to erase is out of bounds."); assert(I < this->end() && "Erasing at past-the-end iterator."); iterator N = I; // Shift all elts down one. - this->move(I+1, this->end(), I); + std::move(I+1, this->end(), I); // Drop the last elt. this->pop_back(); return(N); } - iterator erase(iterator S, iterator E) { + iterator erase(const_iterator CS, const_iterator CE) { + // Just cast away constness because this is a non-const member function. + iterator S = const_cast<iterator>(CS); + iterator E = const_cast<iterator>(CE); + assert(S >= this->begin() && "Range to erase is out of bounds."); assert(S <= E && "Trying to erase invalid range."); assert(E <= this->end() && "Trying to erase past the end."); iterator N = S; // Shift all elts down. - iterator I = this->move(E, this->end(), S); + iterator I = std::move(E, this->end(), S); // Drop the last elts. this->destroy_range(I, this->end()); this->setEnd(I); @@ -502,7 +475,7 @@ public: ::new ((void*) this->end()) T(::std::move(this->back())); // Push everything else over. - this->move_backward(I, this->end()-1, this->end()); + std::move_backward(I, this->end()-1, this->end()); this->setEnd(this->end()+1); // If we just moved the element we're inserting, be sure to update @@ -531,7 +504,7 @@ public: } ::new ((void*) this->end()) T(std::move(this->back())); // Push everything else over. - this->move_backward(I, this->end()-1, this->end()); + std::move_backward(I, this->end()-1, this->end()); this->setEnd(this->end()+1); // If we just moved the element we're inserting, be sure to update @@ -572,7 +545,7 @@ public: std::move_iterator<iterator>(this->end())); // Copy the existing elements that get replaced. - this->move_backward(I, OldEnd-NumToInsert, OldEnd); + std::move_backward(I, OldEnd-NumToInsert, OldEnd); std::fill_n(I, NumToInsert, Elt); return I; @@ -626,7 +599,7 @@ public: std::move_iterator<iterator>(this->end())); // Copy the existing elements that get replaced. - this->move_backward(I, OldEnd-NumToInsert, OldEnd); + std::move_backward(I, OldEnd-NumToInsert, OldEnd); std::copy(From, To, I); return I; @@ -807,7 +780,7 @@ SmallVectorImpl<T> &SmallVectorImpl<T>::operator=(SmallVectorImpl<T> &&RHS) { // Assign common elements. iterator NewEnd = this->begin(); if (RHSSize) - NewEnd = this->move(RHS.begin(), RHS.end(), NewEnd); + NewEnd = std::move(RHS.begin(), RHS.end(), NewEnd); // Destroy excess elements and trim the bounds. this->destroy_range(NewEnd, this->end()); @@ -831,7 +804,7 @@ SmallVectorImpl<T> &SmallVectorImpl<T>::operator=(SmallVectorImpl<T> &&RHS) { this->grow(RHSSize); } else if (CurSize) { // Otherwise, use assignment for the already-constructed elements. - this->move(RHS.begin(), RHS.begin()+CurSize, this->begin()); + std::move(RHS.begin(), RHS.begin()+CurSize, this->begin()); } // Move-construct the new elements in place. diff --git a/include/llvm/ADT/SparseSet.h b/include/llvm/ADT/SparseSet.h index a45d1c8d6b8ae..5b6494d171294 100644 --- a/include/llvm/ADT/SparseSet.h +++ b/include/llvm/ADT/SparseSet.h @@ -263,6 +263,11 @@ public: return *insert(ValueT(Key)).first; } + ValueT pop_back_val() { + // Sparse does not need to be cleared, see find(). + return Dense.pop_back_val(); + } + /// erase - Erases an existing element identified by a valid iterator. /// /// This invalidates all iterators, but erase() returns an iterator pointing diff --git a/include/llvm/ADT/Statistic.h b/include/llvm/ADT/Statistic.h index 7c84e3ef6b4dc..32175fdc7c5cc 100644 --- a/include/llvm/ADT/Statistic.h +++ b/include/llvm/ADT/Statistic.h @@ -27,7 +27,8 @@ #define LLVM_ADT_STATISTIC_H #include "llvm/Support/Atomic.h" -#include "llvm/Support/Valgrind.h" +#include "llvm/Support/Compiler.h" +#include <atomic> #include <memory> namespace llvm { @@ -36,77 +37,66 @@ class raw_fd_ostream; class Statistic { public: + const char *DebugType; const char *Name; const char *Desc; - volatile llvm::sys::cas_flag Value; + std::atomic<unsigned> Value; bool Initialized; - llvm::sys::cas_flag getValue() const { return Value; } + unsigned getValue() const { return Value.load(std::memory_order_relaxed); } + const char *getDebugType() const { return DebugType; } const char *getName() const { return Name; } const char *getDesc() const { return Desc; } /// construct - This should only be called for non-global statistics. - void construct(const char *name, const char *desc) { - Name = name; Desc = desc; - Value = 0; Initialized = false; + void construct(const char *debugtype, const char *name, const char *desc) { + DebugType = debugtype; + Name = name; + Desc = desc; + Value = 0; + Initialized = false; } // Allow use of this class as the value itself. - operator unsigned() const { return Value; } + operator unsigned() const { return getValue(); } #if !defined(NDEBUG) || defined(LLVM_ENABLE_STATS) const Statistic &operator=(unsigned Val) { - Value = Val; + Value.store(Val, std::memory_order_relaxed); return init(); } const Statistic &operator++() { - // FIXME: This function and all those that follow carefully use an - // atomic operation to update the value safely in the presence of - // concurrent accesses, but not to read the return value, so the - // return value is not thread safe. - sys::AtomicIncrement(&Value); + Value.fetch_add(1, std::memory_order_relaxed); return init(); } unsigned operator++(int) { init(); - unsigned OldValue = Value; - sys::AtomicIncrement(&Value); - return OldValue; + return Value.fetch_add(1, std::memory_order_relaxed); } const Statistic &operator--() { - sys::AtomicDecrement(&Value); + Value.fetch_sub(1, std::memory_order_relaxed); return init(); } unsigned operator--(int) { init(); - unsigned OldValue = Value; - sys::AtomicDecrement(&Value); - return OldValue; + return Value.fetch_sub(1, std::memory_order_relaxed); } - const Statistic &operator+=(const unsigned &V) { - if (!V) return *this; - sys::AtomicAdd(&Value, V); - return init(); - } - - const Statistic &operator-=(const unsigned &V) { - if (!V) return *this; - sys::AtomicAdd(&Value, -V); - return init(); - } - - const Statistic &operator*=(const unsigned &V) { - sys::AtomicMul(&Value, V); + const Statistic &operator+=(unsigned V) { + if (V == 0) + return *this; + Value.fetch_add(V, std::memory_order_relaxed); return init(); } - const Statistic &operator/=(const unsigned &V) { - sys::AtomicDiv(&Value, V); + const Statistic &operator-=(unsigned V) { + if (V == 0) + return *this; + Value.fetch_sub(V, std::memory_order_relaxed); return init(); } @@ -140,14 +130,6 @@ public: return *this; } - const Statistic &operator*=(const unsigned &V) { - return *this; - } - - const Statistic &operator/=(const unsigned &V) { - return *this; - } - #endif // !defined(NDEBUG) || defined(LLVM_ENABLE_STATS) protected: @@ -163,8 +145,8 @@ protected: // STATISTIC - A macro to make definition of statistics really simple. This // automatically passes the DEBUG_TYPE of the file into the statistic. -#define STATISTIC(VARNAME, DESC) \ - static llvm::Statistic VARNAME = { DEBUG_TYPE, DESC, 0, 0 } +#define STATISTIC(VARNAME, DESC) \ + static llvm::Statistic VARNAME = {DEBUG_TYPE, #VARNAME, DESC, {0}, 0} /// \brief Enable the collection and printing of statistics. void EnableStatistics(); @@ -181,6 +163,9 @@ void PrintStatistics(); /// \brief Print statistics to the given output stream. void PrintStatistics(raw_ostream &OS); -} // End llvm namespace +/// Print statistics in JSON format. +void PrintStatisticsJSON(raw_ostream &OS); + +} // end llvm namespace -#endif +#endif // LLVM_ADT_STATISTIC_H diff --git a/include/llvm/ADT/StringExtras.h b/include/llvm/ADT/StringExtras.h index 0992f5d4a5496..bdbb4d3f5932e 100644 --- a/include/llvm/ADT/StringExtras.h +++ b/include/llvm/ADT/StringExtras.h @@ -44,55 +44,40 @@ static inline unsigned hexDigitValue(char C) { return -1U; } -/// utohex_buffer - Emit the specified number into the buffer specified by -/// BufferEnd, returning a pointer to the start of the string. This can be used -/// like this: (note that the buffer must be large enough to handle any number): -/// char Buffer[40]; -/// printf("0x%s", utohex_buffer(X, Buffer+40)); -/// -/// This should only be used with unsigned types. -/// -template<typename IntTy> -static inline char *utohex_buffer(IntTy X, char *BufferEnd, bool LowerCase = false) { - char *BufPtr = BufferEnd; - *--BufPtr = 0; // Null terminate buffer. - if (X == 0) { - *--BufPtr = '0'; // Handle special case. - return BufPtr; - } +static inline std::string utohexstr(uint64_t X, bool LowerCase = false) { + char Buffer[17]; + char *BufPtr = std::end(Buffer); + + if (X == 0) *--BufPtr = '0'; while (X) { unsigned char Mod = static_cast<unsigned char>(X) & 15; *--BufPtr = hexdigit(Mod, LowerCase); X >>= 4; } - return BufPtr; -} -static inline std::string utohexstr(uint64_t X, bool LowerCase = false) { - char Buffer[17]; - return utohex_buffer(X, Buffer+17, LowerCase); + return std::string(BufPtr, std::end(Buffer)); } -static inline std::string utostr_32(uint32_t X, bool isNeg = false) { - char Buffer[11]; - char *BufPtr = Buffer+11; - - if (X == 0) *--BufPtr = '0'; // Handle special case... - - while (X) { - *--BufPtr = '0' + char(X % 10); - X /= 10; +/// Convert buffer \p Input to its hexadecimal representation. +/// The returned string is double the size of \p Input. +static inline std::string toHex(StringRef Input) { + static const char *const LUT = "0123456789ABCDEF"; + size_t Length = Input.size(); + + std::string Output; + Output.reserve(2 * Length); + for (size_t i = 0; i < Length; ++i) { + const unsigned char c = Input[i]; + Output.push_back(LUT[c >> 4]); + Output.push_back(LUT[c & 15]); } - - if (isNeg) *--BufPtr = '-'; // Add negative sign... - - return std::string(BufPtr, Buffer+11); + return Output; } static inline std::string utostr(uint64_t X, bool isNeg = false) { char Buffer[21]; - char *BufPtr = Buffer+21; + char *BufPtr = std::end(Buffer); if (X == 0) *--BufPtr = '0'; // Handle special case... @@ -102,7 +87,7 @@ static inline std::string utostr(uint64_t X, bool isNeg = false) { } if (isNeg) *--BufPtr = '-'; // Add negative sign... - return std::string(BufPtr, Buffer+21); + return std::string(BufPtr, std::end(Buffer)); } diff --git a/include/llvm/ADT/StringMap.h b/include/llvm/ADT/StringMap.h index 700bb9e10ef7b..260275295c993 100644 --- a/include/llvm/ADT/StringMap.h +++ b/include/llvm/ADT/StringMap.h @@ -16,6 +16,7 @@ #include "llvm/ADT/StringRef.h" #include "llvm/Support/Allocator.h" +#include "llvm/Support/PointerLikeTypeTraits.h" #include <cstring> #include <utility> @@ -88,12 +89,15 @@ protected: /// table, returning it. If the key is not in the table, this returns null. StringMapEntryBase *RemoveKey(StringRef Key); -private: + /// Allocate the table with the specified number of buckets and otherwise + /// setup the map as empty. void init(unsigned Size); public: static StringMapEntryBase *getTombstoneVal() { - return (StringMapEntryBase*)-1; + uintptr_t Val = static_cast<uintptr_t>(-1); + Val <<= PointerLikeTypeTraits<StringMapEntryBase *>::NumLowBitsAvailable; + return reinterpret_cast<StringMapEntryBase *>(Val); } unsigned getNumBuckets() const { return NumBuckets; } @@ -122,9 +126,9 @@ public: explicit StringMapEntry(unsigned strLen) : StringMapEntryBase(strLen), second() {} - template <class InitTy> - StringMapEntry(unsigned strLen, InitTy &&V) - : StringMapEntryBase(strLen), second(std::forward<InitTy>(V)) {} + template <typename... InitTy> + StringMapEntry(unsigned strLen, InitTy &&... InitVals) + : StringMapEntryBase(strLen), second(std::forward<InitTy>(InitVals)...) {} StringRef getKey() const { return StringRef(getKeyData(), getKeyLength()); @@ -142,11 +146,11 @@ public: StringRef first() const { return StringRef(getKeyData(), getKeyLength()); } - /// Create - Create a StringMapEntry for the specified key and default - /// construct the value. - template <typename AllocatorTy, typename InitType> + /// Create a StringMapEntry for the specified key construct the value using + /// \p InitiVals. + template <typename AllocatorTy, typename... InitTy> static StringMapEntry *Create(StringRef Key, AllocatorTy &Allocator, - InitType &&InitVal) { + InitTy &&... InitVals) { unsigned KeyLength = Key.size(); // Allocate a new item with space for the string at the end and a null @@ -158,8 +162,8 @@ public: StringMapEntry *NewItem = static_cast<StringMapEntry*>(Allocator.Allocate(AllocSize,Alignment)); - // Default construct the value. - new (NewItem) StringMapEntry(KeyLength, std::forward<InitType>(InitVal)); + // Construct the value. + new (NewItem) StringMapEntry(KeyLength, std::forward<InitTy>(InitVals)...); // Copy the string information. char *StrBuffer = const_cast<char*>(NewItem->getKeyData()); @@ -169,16 +173,11 @@ public: return NewItem; } - template<typename AllocatorTy> - static StringMapEntry *Create(StringRef Key, AllocatorTy &Allocator) { - return Create(Key, Allocator, ValueTy()); - } - /// Create - Create a StringMapEntry with normal malloc/free. - template<typename InitType> - static StringMapEntry *Create(StringRef Key, InitType &&InitVal) { + template <typename... InitType> + static StringMapEntry *Create(StringRef Key, InitType &&... InitVal) { MallocAllocator A; - return Create(Key, A, std::forward<InitType>(InitVal)); + return Create(Key, A, std::forward<InitType>(InitVal)...); } static StringMapEntry *Create(StringRef Key) { @@ -233,7 +232,7 @@ public: Allocator(A) {} StringMap(std::initializer_list<std::pair<StringRef, ValueTy>> List) - : StringMapImpl(static_cast<unsigned>(sizeof(MapEntryTy))) { + : StringMapImpl(List.size(), static_cast<unsigned>(sizeof(MapEntryTy))) { for (const auto &P : List) { insert(P); } @@ -248,7 +247,40 @@ public: return *this; } - // FIXME: Implement copy operations if/when they're needed. + StringMap(const StringMap &RHS) : + StringMapImpl(static_cast<unsigned>(sizeof(MapEntryTy))), + Allocator(RHS.Allocator) { + if (RHS.empty()) + return; + + // Allocate TheTable of the same size as RHS's TheTable, and set the + // sentinel appropriately (and NumBuckets). + init(RHS.NumBuckets); + unsigned *HashTable = (unsigned *)(TheTable + NumBuckets + 1), + *RHSHashTable = (unsigned *)(RHS.TheTable + NumBuckets + 1); + + NumItems = RHS.NumItems; + NumTombstones = RHS.NumTombstones; + for (unsigned I = 0, E = NumBuckets; I != E; ++I) { + StringMapEntryBase *Bucket = RHS.TheTable[I]; + if (!Bucket || Bucket == getTombstoneVal()) { + TheTable[I] = Bucket; + continue; + } + + TheTable[I] = MapEntryTy::Create( + static_cast<MapEntryTy *>(Bucket)->getKey(), Allocator, + static_cast<MapEntryTy *>(Bucket)->getValue()); + HashTable[I] = RHSHashTable[I]; + } + + // Note that here we've copied everything from the RHS into this object, + // tombstones included. We could, instead, have re-probed for each key to + // instantiate this new object without any tombstone buckets. The + // assumption here is that items are rarely deleted from most StringMaps, + // and so tombstones are rare, so the cost of re-probing for all inputs is + // not worthwhile. + } AllocatorTy &getAllocator() { return Allocator; } const AllocatorTy &getAllocator() const { return Allocator; } @@ -295,8 +327,10 @@ public: return ValueTy(); } + /// Lookup the ValueTy for the \p Key, or create a default constructed value + /// if the key is not in the map. ValueTy &operator[](StringRef Key) { - return insert(std::make_pair(Key, ValueTy())).first->second; + return emplace_second(Key).first->second; } /// count - Return 1 if the element is in the map, 0 otherwise. @@ -328,7 +362,16 @@ public: /// if and only if the insertion takes place, and the iterator component of /// the pair points to the element with key equivalent to the key of the pair. std::pair<iterator, bool> insert(std::pair<StringRef, ValueTy> KV) { - unsigned BucketNo = LookupBucketFor(KV.first); + return emplace_second(KV.first, std::move(KV.second)); + } + + /// Emplace a new element for the specified key into the map if the key isn't + /// already in the map. 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 with key equivalent to the key of the pair. + template <typename... ArgsTy> + std::pair<iterator, bool> emplace_second(StringRef Key, ArgsTy &&... Args) { + unsigned BucketNo = LookupBucketFor(Key); StringMapEntryBase *&Bucket = TheTable[BucketNo]; if (Bucket && Bucket != getTombstoneVal()) return std::make_pair(iterator(TheTable + BucketNo, false), @@ -336,8 +379,7 @@ public: if (Bucket == getTombstoneVal()) --NumTombstones; - Bucket = - MapEntryTy::Create(KV.first, Allocator, std::move(KV.second)); + Bucket = MapEntryTy::Create(Key, Allocator, std::forward<ArgsTy>(Args)...); ++NumItems; assert(NumItems + NumTombstones <= NumBuckets); diff --git a/include/llvm/ADT/StringRef.h b/include/llvm/ADT/StringRef.h index 350032b8c4e77..398ca69202493 100644 --- a/include/llvm/ADT/StringRef.h +++ b/include/llvm/ADT/StringRef.h @@ -10,6 +10,7 @@ #ifndef LLVM_ADT_STRINGREF_H #define LLVM_ADT_STRINGREF_H +#include "llvm/ADT/iterator_range.h" #include "llvm/Support/Compiler.h" #include <algorithm> #include <cassert> @@ -101,6 +102,9 @@ namespace llvm { const unsigned char *bytes_end() const { return reinterpret_cast<const unsigned char *>(end()); } + iterator_range<const unsigned char *> bytes() const { + return make_range(bytes_begin(), bytes_end()); + } /// @} /// @name String Operations @@ -133,6 +137,9 @@ namespace llvm { // copy - Allocate copy in Allocator and return StringRef to it. template <typename Allocator> StringRef copy(Allocator &A) const { + // Don't request a length 0 copy from the allocator. + if (empty()) + return StringRef(); char *S = A.template Allocate<char>(Length); std::copy(begin(), end(), S); return StringRef(S, Length); @@ -443,9 +450,10 @@ namespace llvm { /// empty substring will be returned. /// /// \param End The index following the last character to include in the - /// substring. If this is npos, or less than \p Start, or exceeds the - /// number of characters remaining in the string, the string suffix - /// (starting with \p Start) will be returned. + /// substring. If this is npos or exceeds the number of characters + /// remaining in the string, the string suffix (starting with \p Start) + /// will be returned. If this is less than \p Start, an empty string will + /// be returned. LLVM_ATTRIBUTE_ALWAYS_INLINE StringRef slice(size_t Start, size_t End) const { Start = std::min(Start, Length); @@ -539,18 +547,36 @@ namespace llvm { return std::make_pair(slice(0, Idx), slice(Idx+1, npos)); } + /// Return string with consecutive \p Char characters starting from the + /// the left removed. + StringRef ltrim(char Char) const { + return drop_front(std::min(Length, find_first_not_of(Char))); + } + /// Return string with consecutive characters in \p Chars starting from /// the left removed. StringRef ltrim(StringRef Chars = " \t\n\v\f\r") const { return drop_front(std::min(Length, find_first_not_of(Chars))); } + /// Return string with consecutive \p Char characters starting from the + /// right removed. + StringRef rtrim(char Char) const { + return drop_back(Length - std::min(Length, find_last_not_of(Char) + 1)); + } + /// Return string with consecutive characters in \p Chars starting from /// the right removed. StringRef rtrim(StringRef Chars = " \t\n\v\f\r") const { return drop_back(Length - std::min(Length, find_last_not_of(Chars) + 1)); } + /// Return string with consecutive \p Char characters starting from the + /// left and right removed. + StringRef trim(char Char) const { + return ltrim(Char).rtrim(Char); + } + /// Return string with consecutive characters in \p Chars starting from /// the left and right removed. StringRef trim(StringRef Chars = " \t\n\v\f\r") const { diff --git a/include/llvm/ADT/StringSet.h b/include/llvm/ADT/StringSet.h index 08626dc7af84c..c32c2a4974385 100644 --- a/include/llvm/ADT/StringSet.h +++ b/include/llvm/ADT/StringSet.h @@ -33,6 +33,12 @@ namespace llvm { assert(!Key.empty()); return base::insert(std::make_pair(Key, '\0')); } + + template <typename InputIt> + void insert(const InputIt &Begin, const InputIt &End) { + for (auto It = Begin; It != End; ++It) + base::insert(std::make_pair(*It, '\0')); + } }; } diff --git a/include/llvm/ADT/TinyPtrVector.h b/include/llvm/ADT/TinyPtrVector.h index 487aa46cf6420..605f0e70a8578 100644 --- a/include/llvm/ADT/TinyPtrVector.h +++ b/include/llvm/ADT/TinyPtrVector.h @@ -104,8 +104,16 @@ public: /// This also is a constructor for individual array elements due to the single /// element constructor for ArrayRef. explicit TinyPtrVector(ArrayRef<EltTy> Elts) - : Val(Elts.size() == 1 ? PtrUnion(Elts[0]) - : PtrUnion(new VecTy(Elts.begin(), Elts.end()))) {} + : Val(Elts.empty() + ? PtrUnion() + : Elts.size() == 1 + ? PtrUnion(Elts[0]) + : PtrUnion(new VecTy(Elts.begin(), Elts.end()))) {} + + TinyPtrVector(size_t Count, EltTy Value) + : Val(Count == 0 ? PtrUnion() + : Count == 1 ? PtrUnion(Value) + : PtrUnion(new VecTy(Count, Value))) {} // implicit conversion operator to ArrayRef. operator ArrayRef<EltTy>() const { @@ -125,6 +133,15 @@ public: return *Val.template get<VecTy*>(); } + // Implicit conversion to ArrayRef<U> if EltTy* implicitly converts to U*. + template<typename U, + typename std::enable_if< + std::is_convertible<ArrayRef<EltTy>, ArrayRef<U>>::value, + bool>::type = false> + operator ArrayRef<U>() const { + return operator ArrayRef<EltTy>(); + } + bool empty() const { // This vector can be empty if it contains no element, or if it // contains a pointer to an empty vector. @@ -142,8 +159,10 @@ public: return Val.template get<VecTy*>()->size(); } - typedef const EltTy *const_iterator; typedef EltTy *iterator; + typedef const EltTy *const_iterator; + typedef std::reverse_iterator<iterator> reverse_iterator; + typedef std::reverse_iterator<const_iterator> const_reverse_iterator; iterator begin() { if (Val.template is<EltTy>()) @@ -166,6 +185,15 @@ public: return (const_iterator)const_cast<TinyPtrVector*>(this)->end(); } + reverse_iterator rbegin() { return reverse_iterator(end()); } + reverse_iterator rend() { return reverse_iterator(begin()); } + const_reverse_iterator rbegin() const { + return const_reverse_iterator(end()); + } + const_reverse_iterator rend() const { + return const_reverse_iterator(begin()); + } + EltTy operator[](unsigned i) const { assert(!Val.isNull() && "can't index into an empty vector"); if (EltTy V = Val.template dyn_cast<EltTy>()) { diff --git a/include/llvm/ADT/Triple.h b/include/llvm/ADT/Triple.h index e01db0a61fd59..47813049d2f2c 100644 --- a/include/llvm/ADT/Triple.h +++ b/include/llvm/ADT/Triple.h @@ -46,49 +46,52 @@ public: enum ArchType { UnknownArch, - arm, // ARM (little endian): arm, armv.*, xscale - armeb, // ARM (big endian): armeb - aarch64, // AArch64 (little endian): aarch64 - aarch64_be, // AArch64 (big endian): aarch64_be - avr, // AVR: Atmel AVR microcontroller - bpfel, // eBPF or extended BPF or 64-bit BPF (little endian) - bpfeb, // eBPF or extended BPF or 64-bit BPF (big endian) - hexagon, // Hexagon: hexagon - mips, // MIPS: mips, mipsallegrex - mipsel, // MIPSEL: mipsel, mipsallegrexel - mips64, // MIPS64: mips64 - mips64el, // MIPS64EL: mips64el - msp430, // MSP430: msp430 - ppc, // PPC: powerpc - ppc64, // PPC64: powerpc64, ppu - ppc64le, // PPC64LE: powerpc64le - r600, // R600: AMD GPUs HD2XXX - HD6XXX - 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.* - thumbeb, // Thumb (big endian): thumbeb - x86, // X86: i[3-9]86 - x86_64, // X86-64: amd64, x86_64 - xcore, // XCore: xcore - nvptx, // NVPTX: 32-bit - nvptx64, // NVPTX: 64-bit - le32, // le32: generic little-endian 32-bit CPU (PNaCl) - le64, // le64: generic little-endian 64-bit CPU (PNaCl) - 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 - shave, // SHAVE: Movidius vector VLIW processors - wasm32, // WebAssembly with 32-bit pointers - wasm64, // WebAssembly with 64-bit pointers - LastArchType = wasm64 + arm, // ARM (little endian): arm, armv.*, xscale + armeb, // ARM (big endian): armeb + aarch64, // AArch64 (little endian): aarch64 + aarch64_be, // AArch64 (big endian): aarch64_be + avr, // AVR: Atmel AVR microcontroller + bpfel, // eBPF or extended BPF or 64-bit BPF (little endian) + bpfeb, // eBPF or extended BPF or 64-bit BPF (big endian) + hexagon, // Hexagon: hexagon + mips, // MIPS: mips, mipsallegrex + mipsel, // MIPSEL: mipsel, mipsallegrexel + mips64, // MIPS64: mips64 + mips64el, // MIPS64EL: mips64el + msp430, // MSP430: msp430 + ppc, // PPC: powerpc + ppc64, // PPC64: powerpc64, ppu + ppc64le, // PPC64LE: powerpc64le + r600, // R600: AMD GPUs HD2XXX - HD6XXX + 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.* + thumbeb, // Thumb (big endian): thumbeb + x86, // X86: i[3-9]86 + x86_64, // X86-64: amd64, x86_64 + xcore, // XCore: xcore + nvptx, // NVPTX: 32-bit + nvptx64, // NVPTX: 64-bit + le32, // le32: generic little-endian 32-bit CPU (PNaCl) + le64, // le64: generic little-endian 64-bit CPU (PNaCl) + 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 + shave, // SHAVE: Movidius vector VLIW processors + lanai, // Lanai: Lanai 32-bit + wasm32, // WebAssembly with 32-bit pointers + wasm64, // WebAssembly with 64-bit pointers + renderscript32, // 32-bit RenderScript + renderscript64, // 64-bit RenderScript + LastArchType = renderscript64 }; enum SubArchType { NoSubArch, @@ -96,6 +99,8 @@ public: ARMSubArch_v8_2a, ARMSubArch_v8_1a, ARMSubArch_v8, + ARMSubArch_v8m_baseline, + ARMSubArch_v8m_mainline, ARMSubArch_v7, ARMSubArch_v7em, ARMSubArch_v7m, @@ -128,7 +133,9 @@ public: NVIDIA, CSR, Myriad, - LastVendorType = Myriad + AMD, + Mesa, + LastVendorType = Mesa }; enum OSType { UnknownOS, @@ -160,7 +167,8 @@ public: ELFIAMCU, TvOS, // Apple tvOS WatchOS, // Apple watchOS - LastOSType = WatchOS + Mesa3D, + LastOSType = Mesa3D }; enum EnvironmentType { UnknownEnvironment, @@ -173,6 +181,9 @@ public: EABI, EABIHF, Android, + Musl, + MuslEABI, + MuslEABIHF, MSVC, Itanium, @@ -390,8 +401,8 @@ public: /// isMacOSXVersionLT - Comparison function for checking OS X version /// compatibility, which handles supporting skewed version numbering schemes /// used by the "darwin" triples. - unsigned isMacOSXVersionLT(unsigned Major, unsigned Minor = 0, - unsigned Micro = 0) const { + bool isMacOSXVersionLT(unsigned Major, unsigned Minor = 0, + unsigned Micro = 0) const { assert(isMacOSX() && "Not an OS X triple!"); // If this is OS X, expect a sane version number. @@ -428,6 +439,10 @@ public: return getOS() == Triple::WatchOS; } + bool isWatchABI() const { + return getSubArch() == Triple::ARMSubArch_v7k; + } + /// isOSDarwin - Is this a "Darwin" OS (OS X, iOS, or watchOS). bool isOSDarwin() const { return isMacOSX() || isiOS() || isWatchOS(); @@ -459,6 +474,12 @@ public: return getOS() == Triple::ELFIAMCU; } + bool isGNUEnvironment() const { + EnvironmentType Env = getEnvironment(); + return Env == Triple::GNU || Env == Triple::GNUEABI || + Env == Triple::GNUEABIHF || Env == Triple::GNUX32; + } + /// Checks if the environment could be MSVC. bool isWindowsMSVCEnvironment() const { return getOS() == Triple::Win32 && @@ -513,6 +534,16 @@ public: return getOS() == Triple::Linux; } + /// Tests whether the OS is kFreeBSD. + bool isOSKFreeBSD() const { + return getOS() == Triple::KFreeBSD; + } + + /// Tests whether the OS uses glibc. + bool isOSGlibc() const { + return getOS() == Triple::Linux || getOS() == Triple::KFreeBSD; + } + /// Tests whether the OS uses the ELF binary format. bool isOSBinFormatELF() const { return getObjectFormat() == Triple::ELF; @@ -544,6 +575,21 @@ public: /// Tests whether the target is Android bool isAndroid() const { return getEnvironment() == Triple::Android; } + /// Tests whether the environment is musl-libc + bool isMusl() const { + return getEnvironment() == Triple::Musl || + getEnvironment() == Triple::MuslEABI || + getEnvironment() == Triple::MuslEABIHF; + } + + /// Tests whether the target is NVPTX (32- or 64-bit). + bool isNVPTX() const { + return getArch() == Triple::nvptx || getArch() == Triple::nvptx64; + } + + /// Tests wether the target supports comdat + bool supportsCOMDAT() const { return !isOSBinFormatMachO(); } + /// @} /// @name Mutators /// @{ @@ -632,6 +678,11 @@ public: /// string then the triple's arch name is used. StringRef getARMCPUForArch(StringRef Arch = StringRef()) const; + /// Tests whether the target triple is little endian. + /// + /// \returns true if the triple is little endian, false otherwise. + bool isLittleEndian() const; + /// @} /// @name Static helpers for IDs. /// @{ diff --git a/include/llvm/ADT/ilist.h b/include/llvm/ADT/ilist.h index 3044a6c435f10..8e4d45dfef22a 100644 --- a/include/llvm/ADT/ilist.h +++ b/include/llvm/ADT/ilist.h @@ -186,53 +186,38 @@ template<typename Ty> struct ilist_traits<const Ty> : public ilist_traits<Ty> {}; //===----------------------------------------------------------------------===// -// ilist_iterator<Node> - Iterator for intrusive list. +// Iterator for intrusive list. // -template<typename NodeTy> +template <typename NodeTy> class ilist_iterator - : public std::iterator<std::bidirectional_iterator_tag, NodeTy, ptrdiff_t> { - + : public std::iterator<std::bidirectional_iterator_tag, NodeTy, ptrdiff_t> { public: typedef ilist_traits<NodeTy> Traits; - typedef std::iterator<std::bidirectional_iterator_tag, - NodeTy, ptrdiff_t> super; + typedef std::iterator<std::bidirectional_iterator_tag, NodeTy, ptrdiff_t> + super; typedef typename super::value_type value_type; typedef typename super::difference_type difference_type; typedef typename super::pointer pointer; typedef typename super::reference reference; + private: pointer NodePtr; - // ilist_iterator is not a random-access iterator, but it has an - // implicit conversion to pointer-type, which is. Declare (but - // don't define) these functions as private to help catch - // accidental misuse. - void operator[](difference_type) const; - void operator+(difference_type) const; - void operator-(difference_type) const; - void operator+=(difference_type) const; - void operator-=(difference_type) const; - template<class T> void operator<(T) const; - template<class T> void operator<=(T) const; - template<class T> void operator>(T) const; - template<class T> void operator>=(T) const; - template<class T> void operator-(T) const; public: - explicit ilist_iterator(pointer NP) : NodePtr(NP) {} explicit ilist_iterator(reference NR) : NodePtr(&NR) {} ilist_iterator() : NodePtr(nullptr) {} // This is templated so that we can allow constructing a const iterator from // a nonconst iterator... - template<class node_ty> + template <class node_ty> ilist_iterator(const ilist_iterator<node_ty> &RHS) - : NodePtr(RHS.getNodePtrUnchecked()) {} + : NodePtr(RHS.getNodePtrUnchecked()) {} // This is templated so that we can allow assigning to a const iterator from // a nonconst iterator... - template<class node_ty> + template <class node_ty> const ilist_iterator &operator=(const ilist_iterator<node_ty> &RHS) { NodePtr = RHS.getNodePtrUnchecked(); return *this; @@ -241,13 +226,8 @@ public: void reset(pointer NP) { NodePtr = NP; } // Accessors... - explicit operator pointer() const { - return NodePtr; - } - - reference operator*() const { - return *NodePtr; - } + explicit operator pointer() const { return NodePtr; } + reference operator*() const { return *NodePtr; } pointer operator->() const { return &operator*(); } // Comparison operators @@ -259,21 +239,21 @@ public: } // Increment and decrement operators... - ilist_iterator &operator--() { // predecrement - Back up + ilist_iterator &operator--() { NodePtr = Traits::getPrev(NodePtr); assert(NodePtr && "--'d off the beginning of an ilist!"); return *this; } - ilist_iterator &operator++() { // preincrement - Advance + ilist_iterator &operator++() { NodePtr = Traits::getNext(NodePtr); return *this; } - ilist_iterator operator--(int) { // postdecrement operators... + ilist_iterator operator--(int) { ilist_iterator tmp = *this; --*this; return tmp; } - ilist_iterator operator++(int) { // postincrement operators... + ilist_iterator operator++(int) { ilist_iterator tmp = *this; ++*this; return tmp; @@ -283,38 +263,6 @@ public: pointer getNodePtrUnchecked() const { return NodePtr; } }; -// These are to catch errors when people try to use them as random access -// iterators. -template<typename T> -void operator-(int, ilist_iterator<T>) = delete; -template<typename T> -void operator-(ilist_iterator<T>,int) = delete; - -template<typename T> -void operator+(int, ilist_iterator<T>) = delete; -template<typename T> -void operator+(ilist_iterator<T>,int) = delete; - -// operator!=/operator== - Allow mixed comparisons without dereferencing -// the iterator, which could very likely be pointing to end(). -template<typename T> -bool operator!=(const T* LHS, const ilist_iterator<const T> &RHS) { - return LHS != RHS.getNodePtrUnchecked(); -} -template<typename T> -bool operator==(const T* LHS, const ilist_iterator<const T> &RHS) { - return LHS == RHS.getNodePtrUnchecked(); -} -template<typename T> -bool operator!=(T* LHS, const ilist_iterator<T> &RHS) { - return LHS != RHS.getNodePtrUnchecked(); -} -template<typename T> -bool operator==(T* LHS, const ilist_iterator<T> &RHS) { - return LHS == RHS.getNodePtrUnchecked(); -} - - // Allow ilist_iterators to convert into pointers to a node automatically when // used by the dyn_cast, cast, isa mechanisms... @@ -474,6 +422,10 @@ public: return iterator(New); } + iterator insert(iterator where, const NodeTy &New) { + return this->insert(where, new NodeTy(New)); + } + iterator insertAfter(iterator where, NodeTy *New) { if (empty()) return insert(begin(), New); @@ -720,7 +672,7 @@ struct ilist : public iplist<NodeTy> { typedef typename iplist<NodeTy>::iterator iterator; ilist() {} - ilist(const ilist &right) { + ilist(const ilist &right) : iplist<NodeTy>() { insert(this->begin(), right.begin(), right.end()); } explicit ilist(size_type count) { diff --git a/include/llvm/ADT/iterator.h b/include/llvm/ADT/iterator.h index c307928927038..2898a677db371 100644 --- a/include/llvm/ADT/iterator.h +++ b/include/llvm/ADT/iterator.h @@ -46,6 +46,22 @@ protected: std::is_base_of<std::bidirectional_iterator_tag, IteratorCategoryT>::value, }; + /// A proxy object for computing a reference via indirecting a copy of an + /// iterator. This is used in APIs which need to produce a reference via + /// indirection but for which the iterator object might be a temporary. The + /// proxy preserves the iterator internally and exposes the indirected + /// reference via a conversion operator. + class ReferenceProxy { + friend iterator_facade_base; + + DerivedT I; + + ReferenceProxy(DerivedT I) : I(std::move(I)) {} + + public: + operator ReferenceT() const { return *I; } + }; + public: DerivedT operator+(DifferenceTypeT n) const { static_assert( @@ -120,10 +136,10 @@ public: PointerT operator->() const { return &static_cast<const DerivedT *>(this)->operator*(); } - ReferenceT operator[](DifferenceTypeT n) const { + ReferenceProxy operator[](DifferenceTypeT n) const { static_assert(IsRandomAccess, "Subscripting is only defined for random access iterators."); - return *static_cast<const DerivedT *>(this)->operator+(n); + return ReferenceProxy(static_cast<const DerivedT *>(this)->operator+(n)); } }; |