diff options
Diffstat (limited to 'include/llvm/ADT')
36 files changed, 2392 insertions, 437 deletions
diff --git a/include/llvm/ADT/APFloat.h b/include/llvm/ADT/APFloat.h index d2566a4..2b466f9 100644 --- a/include/llvm/ADT/APFloat.h +++ b/include/llvm/ADT/APFloat.h @@ -320,6 +320,7 @@ namespace llvm { const fltSemantics &getSemantics() const { return *semantics; } bool isZero() const { return category == fcZero; } bool isNonZero() const { return category != fcZero; } + bool isNormal() const { return category == fcNormal; } bool isNaN() const { return category == fcNaN; } bool isInfinity() const { return category == fcInfinity; } bool isNegative() const { return sign; } @@ -328,8 +329,16 @@ namespace llvm { APFloat& operator=(const APFloat &); - /* Return an arbitrary integer value usable for hashing. */ - uint32_t getHashValue() const; + /// \brief Overload to compute a hash code for an APFloat value. + /// + /// Note that the use of hash codes for floating point values is in general + /// frought with peril. Equality is hard to define for these values. For + /// example, should negative and positive zero hash to different codes? Are + /// they equal or not? This hash value implementation specifically + /// emphasizes producing different codes for different inputs in order to + /// be used in canonicalization and memoization. As such, equality is + /// bitwiseIsEqual, and 0 != -0. + friend hash_code hash_value(const APFloat &Arg); /// Converts this value into a decimal string. /// diff --git a/include/llvm/ADT/APInt.h b/include/llvm/ADT/APInt.h index 707e0db..4101989 100644 --- a/include/llvm/ADT/APInt.h +++ b/include/llvm/ADT/APInt.h @@ -23,11 +23,12 @@ #include <string> namespace llvm { - class Serializer; class Deserializer; class FoldingSetNodeID; - class raw_ostream; + class Serializer; class StringRef; + class hash_code; + class raw_ostream; template<typename T> class SmallVectorImpl; @@ -497,15 +498,13 @@ public: if (loBitsSet == APINT_BITS_PER_WORD) return APInt(numBits, -1ULL); // For small values, return quickly. - if (numBits < APINT_BITS_PER_WORD) - return APInt(numBits, (1ULL << loBitsSet) - 1); + if (loBitsSet <= APINT_BITS_PER_WORD) + return APInt(numBits, -1ULL >> (APINT_BITS_PER_WORD - loBitsSet)); return getAllOnesValue(numBits).lshr(numBits - loBitsSet); } - /// The hash value is computed as the sum of the words and the bit width. - /// @returns A hash value computed from the sum of the APInt words. - /// @brief Get a hash value based on this APInt - uint64_t getHashValue() const; + /// \brief Overload to compute a hash_code for an APInt value. + friend hash_code hash_value(const APInt &Arg); /// This function returns a pointer to the internal storage of the APInt. /// This is useful for writing out the APInt in binary form without any @@ -562,7 +561,15 @@ public: /// Performs logical negation operation on this APInt. /// @returns true if *this is zero, false otherwise. /// @brief Logical negation operator. - bool operator!() const; + bool operator!() const { + if (isSingleWord()) + return !VAL; + + for (unsigned i = 0; i != getNumWords(); ++i) + if (pVal[i]) + return false; + return true; + } /// @} /// @name Assignment Operators @@ -835,7 +842,11 @@ public: /// @returns the bit value at bitPosition /// @brief Array-indexing support. - bool operator[](unsigned bitPosition) const; + bool operator[](unsigned bitPosition) const { + assert(bitPosition < getBitWidth() && "Bit position out of bounds!"); + return (maskBit(bitPosition) & + (isSingleWord() ? VAL : pVal[whichWord(bitPosition)])) != 0; + } /// @} /// @name Comparison Operators @@ -1056,6 +1067,16 @@ public: /// @brief Zero extend or truncate to width APInt zextOrTrunc(unsigned width) const; + /// Make this APInt have the bit width given by \p width. The value is sign + /// extended, or left alone to make it that width. + /// @brief Sign extend or truncate to width + APInt sextOrSelf(unsigned width) const; + + /// Make this APInt have the bit width given by \p width. The value is zero + /// extended, or left alone to make it that width. + /// @brief Zero extend or truncate to width + APInt zextOrSelf(unsigned width) const; + /// @} /// @name Bit Manipulation Operators /// @{ diff --git a/include/llvm/ADT/ArrayRef.h b/include/llvm/ADT/ArrayRef.h index 33a8c65..f4c8e55 100644 --- a/include/llvm/ADT/ArrayRef.h +++ b/include/llvm/ADT/ArrayRef.h @@ -14,8 +14,7 @@ #include <vector> namespace llvm { - class APInt; - + /// 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. @@ -33,33 +32,33 @@ namespace llvm { typedef const T *iterator; typedef const T *const_iterator; typedef size_t size_type; - + private: /// The start of the array, in an external buffer. const T *Data; - + /// The number of elements. size_type Length; - + public: /// @name Constructors /// @{ - + /// Construct an empty ArrayRef. /*implicit*/ ArrayRef() : Data(0), Length(0) {} - + /// Construct an ArrayRef from a single element. /*implicit*/ ArrayRef(const T &OneElt) : Data(&OneElt), Length(1) {} - + /// Construct an ArrayRef from a pointer and length. /*implicit*/ ArrayRef(const T *data, size_t length) : Data(data), Length(length) {} - + /// Construct an ArrayRef from a range. ArrayRef(const T *begin, const T *end) : Data(begin), Length(end - begin) {} - + /// Construct an ArrayRef from a SmallVector. /*implicit*/ ArrayRef(const SmallVectorImpl<T> &Vec) : Data(Vec.data()), Length(Vec.size()) {} @@ -67,39 +66,39 @@ namespace llvm { /// Construct an ArrayRef from a std::vector. /*implicit*/ ArrayRef(const std::vector<T> &Vec) : Data(Vec.empty() ? (T*)0 : &Vec[0]), Length(Vec.size()) {} - + /// Construct an ArrayRef from a C array. template <size_t N> /*implicit*/ ArrayRef(const T (&Arr)[N]) : Data(Arr), Length(N) {} - + /// @} /// @name Simple Operations /// @{ iterator begin() const { return Data; } iterator end() const { return Data + Length; } - + /// empty - Check if the array is empty. bool empty() const { return Length == 0; } - + const T *data() const { return Data; } - + /// size - Get the array size. size_t size() const { return Length; } - + /// front - Get the first element. const T &front() const { assert(!empty()); return Data[0]; } - + /// back - Get the last element. const T &back() const { assert(!empty()); return Data[Length-1]; } - + /// equals - Check for element-wise equality. bool equals(ArrayRef RHS) const { if (Length != RHS.Length) @@ -111,18 +110,18 @@ namespace llvm { } /// slice(n) - Chop off the first N elements of the array. - ArrayRef<T> slice(unsigned N) { + ArrayRef<T> slice(unsigned 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) { + ArrayRef<T> slice(unsigned N, unsigned M) const { assert(N+M <= size() && "Invalid specifier"); return ArrayRef<T>(data()+N, M); } - + /// @} /// @name Operator Overloads /// @{ @@ -130,22 +129,104 @@ namespace llvm { assert(Index < Length && "Invalid index!"); return Data[Index]; } - + /// @} /// @name Expensive Operations /// @{ std::vector<T> vec() const { return std::vector<T>(Data, Data+Length); } - + /// @} /// @name Conversion operators /// @{ operator std::vector<T>() const { return std::vector<T>(Data, Data+Length); } + + /// @} + }; + + /// MutableArrayRef - Represent a mutable 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 and modify consecutive elements easily and + /// conveniently. + /// + /// This class does not own the underlying data, it is expected to be used in + /// situations where the data resides in some other buffer, whose lifetime + /// extends past that of the MutableArrayRef. For this reason, it is not in + /// general safe to store a MutableArrayRef. + /// + /// This is intended to be trivially copyable, so it should be passed by + /// value. + template<typename T> + class MutableArrayRef : public ArrayRef<T> { + public: + typedef T *iterator; + + /// Construct an empty ArrayRef. + /*implicit*/ MutableArrayRef() : ArrayRef<T>() {} + + /// Construct an MutableArrayRef from a single element. + /*implicit*/ MutableArrayRef(T &OneElt) : ArrayRef<T>(OneElt) {} + + /// Construct an MutableArrayRef from a pointer and length. + /*implicit*/ MutableArrayRef(T *data, size_t length) + : ArrayRef<T>(data, length) {} + + /// Construct an MutableArrayRef from a range. + MutableArrayRef(T *begin, T *end) : ArrayRef<T>(begin, end) {} + + /// Construct an MutableArrayRef from a SmallVector. + /*implicit*/ MutableArrayRef(SmallVectorImpl<T> &Vec) + : ArrayRef<T>(Vec) {} + + /// Construct a MutableArrayRef from a std::vector. + /*implicit*/ MutableArrayRef(std::vector<T> &Vec) + : ArrayRef<T>(Vec) {} + + /// Construct an MutableArrayRef from a C array. + template <size_t N> + /*implicit*/ MutableArrayRef(T (&Arr)[N]) + : ArrayRef<T>(Arr) {} + + T *data() const { return const_cast<T*>(ArrayRef<T>::data()); } + + iterator begin() const { return data(); } + iterator end() const { return data() + this->size(); } + + /// front - Get the first element. + T &front() const { + assert(!this->empty()); + return data()[0]; + } + + /// back - Get the last element. + T &back() const { + assert(!this->empty()); + return data()[this->size()-1]; + } + + /// slice(n) - Chop off the first N elements of the array. + MutableArrayRef<T> slice(unsigned 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 { + assert(N+M <= this->size() && "Invalid specifier"); + return MutableArrayRef<T>(data()+N, M); + } /// @} + /// @name Operator Overloads + /// @{ + T &operator[](size_t Index) const { + assert(Index < this->size() && "Invalid index!"); + return data()[Index]; + } }; /// @name ArrayRef Convenience constructors @@ -215,5 +296,5 @@ namespace llvm { static const bool value = true; }; } - + #endif diff --git a/include/llvm/ADT/BitVector.h b/include/llvm/ADT/BitVector.h index ac1cf0c..7e0b5ba 100644 --- a/include/llvm/ADT/BitVector.h +++ b/include/llvm/ADT/BitVector.h @@ -14,12 +14,12 @@ #ifndef LLVM_ADT_BITVECTOR_H #define LLVM_ADT_BITVECTOR_H +#include "llvm/Support/ErrorHandling.h" #include "llvm/Support/MathExtras.h" #include <algorithm> #include <cassert> #include <climits> #include <cstdlib> -#include <cstring> namespace llvm { @@ -116,7 +116,7 @@ public: else if (sizeof(BitWord) == 8) NumBits += CountPopulation_64(Bits[i]); else - assert(0 && "Unsupported!"); + llvm_unreachable("Unsupported!"); return NumBits; } @@ -146,10 +146,9 @@ public: if (Bits[i] != 0) { if (sizeof(BitWord) == 4) return i * BITWORD_SIZE + CountTrailingZeros_32((uint32_t)Bits[i]); - else if (sizeof(BitWord) == 8) + if (sizeof(BitWord) == 8) return i * BITWORD_SIZE + CountTrailingZeros_64(Bits[i]); - else - assert(0 && "Unsupported!"); + llvm_unreachable("Unsupported!"); } return -1; } @@ -170,10 +169,9 @@ public: if (Copy != 0) { if (sizeof(BitWord) == 4) return WordPos * BITWORD_SIZE + CountTrailingZeros_32((uint32_t)Copy); - else if (sizeof(BitWord) == 8) + if (sizeof(BitWord) == 8) return WordPos * BITWORD_SIZE + CountTrailingZeros_64(Copy); - else - assert(0 && "Unsupported!"); + llvm_unreachable("Unsupported!"); } // Check subsequent words. @@ -181,10 +179,9 @@ public: if (Bits[i] != 0) { if (sizeof(BitWord) == 4) return i * BITWORD_SIZE + CountTrailingZeros_32((uint32_t)Bits[i]); - else if (sizeof(BitWord) == 8) + if (sizeof(BitWord) == 8) return i * BITWORD_SIZE + CountTrailingZeros_64(Bits[i]); - else - assert(0 && "Unsupported!"); + llvm_unreachable("Unsupported!"); } return -1; } @@ -318,6 +315,16 @@ public: return *this; } + // reset - Reset bits that are set in RHS. Same as *this &= ~RHS. + BitVector &reset(const BitVector &RHS) { + unsigned ThisWords = NumBitWords(size()); + unsigned RHSWords = NumBitWords(RHS.size()); + unsigned i; + for (i = 0; i != std::min(ThisWords, RHSWords); ++i) + Bits[i] &= ~RHS.Bits[i]; + return *this; + } + BitVector &operator|=(const BitVector &RHS) { if (size() < RHS.size()) resize(RHS.size()); @@ -365,6 +372,42 @@ public: std::swap(Capacity, RHS.Capacity); } + //===--------------------------------------------------------------------===// + // Portable bit mask operations. + //===--------------------------------------------------------------------===// + // + // These methods all operate on arrays of uint32_t, each holding 32 bits. The + // fixed word size makes it easier to work with literal bit vector constants + // in portable code. + // + // The LSB in each word is the lowest numbered bit. The size of a portable + // bit mask is always a whole multiple of 32 bits. If no bit mask size is + // given, the bit mask is assumed to cover the entire BitVector. + + /// setBitsInMask - Add '1' bits from Mask to this vector. Don't resize. + /// This computes "*this |= Mask". + void setBitsInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) { + applyMask<true, false>(Mask, MaskWords); + } + + /// clearBitsInMask - 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) { + applyMask<false, false>(Mask, MaskWords); + } + + /// setBitsNotInMask - 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) { + applyMask<true, true>(Mask, MaskWords); + } + + /// clearBitsNotInMask - 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) { + applyMask<false, true>(Mask, MaskWords); + } + private: unsigned NumBitWords(unsigned S) const { return (S + BITWORD_SIZE-1) / BITWORD_SIZE; @@ -400,6 +443,33 @@ private: void init_words(BitWord *B, unsigned NumWords, bool t) { memset(B, 0 - (int)t, NumWords*sizeof(BitWord)); } + + template<bool AddBits, bool InvertMask> + void applyMask(const uint32_t *Mask, unsigned MaskWords) { + assert(BITWORD_SIZE % 32 == 0 && "Unsupported BitWord size."); + MaskWords = std::min(MaskWords, (size() + 31) / 32); + const unsigned Scale = BITWORD_SIZE / 32; + unsigned i; + for (i = 0; MaskWords >= Scale; ++i, MaskWords -= Scale) { + BitWord BW = Bits[i]; + // This inner loop should unroll completely when BITWORD_SIZE > 32. + for (unsigned b = 0; b != BITWORD_SIZE; b += 32) { + uint32_t M = *Mask++; + if (InvertMask) M = ~M; + if (AddBits) BW |= BitWord(M) << b; + else BW &= ~(BitWord(M) << b); + } + Bits[i] = BW; + } + for (unsigned b = 0; MaskWords; b += 32, --MaskWords) { + uint32_t M = *Mask++; + if (InvertMask) M = ~M; + if (AddBits) Bits[i] |= BitWord(M) << b; + else Bits[i] &= ~(BitWord(M) << b); + } + if (AddBits) + clear_unused_bits(); + } }; inline BitVector operator&(const BitVector &LHS, const BitVector &RHS) { diff --git a/include/llvm/ADT/DAGDeltaAlgorithm.h b/include/llvm/ADT/DAGDeltaAlgorithm.h index 99ed15c..e502ac4 100644 --- a/include/llvm/ADT/DAGDeltaAlgorithm.h +++ b/include/llvm/ADT/DAGDeltaAlgorithm.h @@ -36,6 +36,7 @@ namespace llvm { /// for more information on the properties which the predicate function itself /// should satisfy. class DAGDeltaAlgorithm { + virtual void anchor(); public: typedef unsigned change_ty; typedef std::pair<change_ty, change_ty> edge_ty; diff --git a/include/llvm/ADT/DenseMap.h b/include/llvm/ADT/DenseMap.h index e70cacf..8d4a19d 100644 --- a/include/llvm/ADT/DenseMap.h +++ b/include/llvm/ADT/DenseMap.h @@ -30,12 +30,11 @@ namespace llvm { template<typename KeyT, typename ValueT, typename KeyInfoT = DenseMapInfo<KeyT>, - typename ValueInfoT = DenseMapInfo<ValueT>, bool IsConst = false> + bool IsConst = false> class DenseMapIterator; template<typename KeyT, typename ValueT, - typename KeyInfoT = DenseMapInfo<KeyT>, - typename ValueInfoT = DenseMapInfo<ValueT> > + typename KeyInfoT = DenseMapInfo<KeyT> > class DenseMap { typedef std::pair<KeyT, ValueT> BucketT; unsigned NumBuckets; @@ -80,19 +79,19 @@ public: typedef DenseMapIterator<KeyT, ValueT, KeyInfoT> iterator; typedef DenseMapIterator<KeyT, ValueT, - KeyInfoT, ValueInfoT, true> const_iterator; + KeyInfoT, true> const_iterator; inline iterator begin() { // When the map is empty, avoid the overhead of AdvancePastEmptyBuckets(). return empty() ? end() : iterator(Buckets, Buckets+NumBuckets); } inline iterator end() { - return iterator(Buckets+NumBuckets, Buckets+NumBuckets); + return iterator(Buckets+NumBuckets, Buckets+NumBuckets, true); } inline const_iterator begin() const { return empty() ? end() : const_iterator(Buckets, Buckets+NumBuckets); } inline const_iterator end() const { - return const_iterator(Buckets+NumBuckets, Buckets+NumBuckets); + return const_iterator(Buckets+NumBuckets, Buckets+NumBuckets, true); } bool empty() const { return NumEntries == 0; } @@ -137,13 +136,33 @@ public: iterator find(const KeyT &Val) { BucketT *TheBucket; if (LookupBucketFor(Val, TheBucket)) - return iterator(TheBucket, Buckets+NumBuckets); + return iterator(TheBucket, Buckets+NumBuckets, true); return end(); } const_iterator find(const KeyT &Val) const { BucketT *TheBucket; if (LookupBucketFor(Val, TheBucket)) - return const_iterator(TheBucket, Buckets+NumBuckets); + return const_iterator(TheBucket, Buckets+NumBuckets, true); + return end(); + } + + /// Alternate version of find() which allows a different, and possibly + /// less expensive, key type. + /// The DenseMapInfo is responsible for supplying methods + /// getHashValue(LookupKeyT) and isEqual(LookupKeyT, KeyT) for each key + /// type used. + template<class LookupKeyT> + iterator find_as(const LookupKeyT &Val) { + BucketT *TheBucket; + if (LookupBucketFor(Val, TheBucket)) + return iterator(TheBucket, Buckets+NumBuckets, true); + return end(); + } + template<class LookupKeyT> + const_iterator find_as(const LookupKeyT &Val) const { + BucketT *TheBucket; + if (LookupBucketFor(Val, TheBucket)) + return const_iterator(TheBucket, Buckets+NumBuckets, true); return end(); } @@ -162,13 +181,12 @@ public: std::pair<iterator, bool> insert(const std::pair<KeyT, ValueT> &KV) { BucketT *TheBucket; if (LookupBucketFor(KV.first, TheBucket)) - return std::make_pair(iterator(TheBucket, Buckets+NumBuckets), + return std::make_pair(iterator(TheBucket, Buckets+NumBuckets, true), false); // Already in map. // Otherwise, insert the new element. TheBucket = InsertIntoBucket(KV.first, KV.second, TheBucket); - return std::make_pair(iterator(TheBucket, Buckets+NumBuckets), - true); + return std::make_pair(iterator(TheBucket, Buckets+NumBuckets, true), true); } /// insert - Range insertion of pairs. @@ -237,7 +255,7 @@ public: private: void CopyFrom(const DenseMap& other) { if (NumBuckets != 0 && - (!isPodLike<KeyInfoT>::value || !isPodLike<ValueInfoT>::value)) { + (!isPodLike<KeyT>::value || !isPodLike<ValueT>::value)) { const KeyT EmptyKey = getEmptyKey(), TombstoneKey = getTombstoneKey(); for (BucketT *P = Buckets, *E = Buckets+NumBuckets; P != E; ++P) { if (!KeyInfoT::isEqual(P->first, EmptyKey) && @@ -266,7 +284,7 @@ private: Buckets = static_cast<BucketT*>(operator new(sizeof(BucketT) * NumBuckets)); - if (isPodLike<KeyInfoT>::value && isPodLike<ValueInfoT>::value) + if (isPodLike<KeyT>::value && isPodLike<ValueT>::value) memcpy(Buckets, other.Buckets, NumBuckets * sizeof(BucketT)); else for (size_t i = 0; i < NumBuckets; ++i) { @@ -310,6 +328,10 @@ private: static unsigned getHashValue(const KeyT &Val) { return KeyInfoT::getHashValue(Val); } + template<typename LookupKeyT> + static unsigned getHashValue(const LookupKeyT &Val) { + return KeyInfoT::getHashValue(Val); + } static const KeyT getEmptyKey() { return KeyInfoT::getEmptyKey(); } @@ -321,7 +343,8 @@ private: /// FoundBucket. If the bucket contains the key and a value, this returns /// true, otherwise it returns a bucket with an empty marker or tombstone and /// returns false. - bool LookupBucketFor(const KeyT &Val, BucketT *&FoundBucket) const { + template<typename LookupKeyT> + bool LookupBucketFor(const LookupKeyT &Val, BucketT *&FoundBucket) const { unsigned BucketNo = getHashValue(Val); unsigned ProbeAmt = 1; BucketT *BucketsPtr = Buckets; @@ -342,7 +365,7 @@ private: while (1) { BucketT *ThisBucket = BucketsPtr + (BucketNo & (NumBuckets-1)); // Found Val's bucket? If so, return it. - if (KeyInfoT::isEqual(ThisBucket->first, Val)) { + if (KeyInfoT::isEqual(Val, ThisBucket->first)) { FoundBucket = ThisBucket; return true; } @@ -478,12 +501,12 @@ public: }; template<typename KeyT, typename ValueT, - typename KeyInfoT, typename ValueInfoT, bool IsConst> + typename KeyInfoT, bool IsConst> class DenseMapIterator { typedef std::pair<KeyT, ValueT> Bucket; typedef DenseMapIterator<KeyT, ValueT, - KeyInfoT, ValueInfoT, true> ConstIterator; - friend class DenseMapIterator<KeyT, ValueT, KeyInfoT, ValueInfoT, true>; + KeyInfoT, true> ConstIterator; + friend class DenseMapIterator<KeyT, ValueT, KeyInfoT, true>; public: typedef ptrdiff_t difference_type; typedef typename conditional<IsConst, const Bucket, Bucket>::type value_type; @@ -495,15 +518,16 @@ private: public: DenseMapIterator() : Ptr(0), End(0) {} - DenseMapIterator(pointer Pos, pointer E) : Ptr(Pos), End(E) { - AdvancePastEmptyBuckets(); + DenseMapIterator(pointer Pos, pointer E, bool NoAdvance = false) + : Ptr(Pos), End(E) { + if (!NoAdvance) AdvancePastEmptyBuckets(); } // If IsConst is true this is a converting constructor from iterator to // const_iterator and the default copy constructor is used. // Otherwise this is a copy constructor for iterator. DenseMapIterator(const DenseMapIterator<KeyT, ValueT, - KeyInfoT, ValueInfoT, false>& I) + KeyInfoT, false>& I) : Ptr(I.Ptr), End(I.End) {} reference operator*() const { @@ -541,9 +565,9 @@ private: } }; -template<typename KeyT, typename ValueT, typename KeyInfoT, typename ValueInfoT> +template<typename KeyT, typename ValueT, typename KeyInfoT> static inline size_t -capacity_in_bytes(const DenseMap<KeyT, ValueT, KeyInfoT, ValueInfoT> &X) { +capacity_in_bytes(const DenseMap<KeyT, ValueT, KeyInfoT> &X) { return X.getMemorySize(); } diff --git a/include/llvm/ADT/DenseMapInfo.h b/include/llvm/ADT/DenseMapInfo.h index df4084e..1559a35 100644 --- a/include/llvm/ADT/DenseMapInfo.h +++ b/include/llvm/ADT/DenseMapInfo.h @@ -59,7 +59,7 @@ template<> struct DenseMapInfo<char> { // Provide DenseMapInfo for unsigned ints. template<> struct DenseMapInfo<unsigned> { - static inline unsigned getEmptyKey() { return ~0; } + static inline unsigned getEmptyKey() { return ~0U; } static inline unsigned getTombstoneKey() { return ~0U - 1; } static unsigned getHashValue(const unsigned& Val) { return Val * 37U; } static bool isEqual(const unsigned& LHS, const unsigned& RHS) { diff --git a/include/llvm/ADT/FoldingSet.h b/include/llvm/ADT/FoldingSet.h index d2e0b8f..7d7c777 100644 --- a/include/llvm/ADT/FoldingSet.h +++ b/include/llvm/ADT/FoldingSet.h @@ -193,12 +193,11 @@ protected: virtual void GetNodeProfile(Node *N, FoldingSetNodeID &ID) const = 0; /// NodeEquals - Instantiations of the FoldingSet template implement /// this function to compare the given node with the given ID. - virtual bool NodeEquals(Node *N, const FoldingSetNodeID &ID, + virtual bool NodeEquals(Node *N, const FoldingSetNodeID &ID, unsigned IDHash, FoldingSetNodeID &TempID) const=0; - /// NodeEquals - Instantiations of the FoldingSet template implement + /// ComputeNodeHash - Instantiations of the FoldingSet template implement /// this function to compute a hash value for the given node. - virtual unsigned ComputeNodeHash(Node *N, - FoldingSetNodeID &TempID) const = 0; + virtual unsigned ComputeNodeHash(Node *N, FoldingSetNodeID &TempID) const = 0; }; //===----------------------------------------------------------------------===// @@ -220,7 +219,7 @@ template<typename T> struct DefaultFoldingSetTrait { // to compute a temporary ID if necessary. The default implementation // just calls Profile and does a regular comparison. Implementations // can override this to provide more efficient implementations. - static inline bool Equals(T &X, const FoldingSetNodeID &ID, + static inline bool Equals(T &X, const FoldingSetNodeID &ID, unsigned IDHash, FoldingSetNodeID &TempID); // ComputeHash - Compute a hash value for X, using TempID to @@ -249,7 +248,7 @@ struct DefaultContextualFoldingSetTrait { static void Profile(T &X, FoldingSetNodeID &ID, Ctx Context) { X.Profile(ID, Context); } - static inline bool Equals(T &X, const FoldingSetNodeID &ID, + static inline bool Equals(T &X, const FoldingSetNodeID &ID, unsigned IDHash, FoldingSetNodeID &TempID, Ctx Context); static inline unsigned ComputeHash(T &X, FoldingSetNodeID &TempID, Ctx Context); @@ -344,7 +343,7 @@ template<class T> class FoldingSetBucketIterator; template<typename T> inline bool DefaultFoldingSetTrait<T>::Equals(T &X, const FoldingSetNodeID &ID, - FoldingSetNodeID &TempID) { + unsigned IDHash, FoldingSetNodeID &TempID) { FoldingSetTrait<T>::Profile(X, TempID); return TempID == ID; } @@ -358,6 +357,7 @@ template<typename T, typename Ctx> inline bool DefaultContextualFoldingSetTrait<T, Ctx>::Equals(T &X, const FoldingSetNodeID &ID, + unsigned IDHash, FoldingSetNodeID &TempID, Ctx Context) { ContextualFoldingSetTrait<T, Ctx>::Profile(X, TempID, Context); @@ -387,15 +387,14 @@ private: } /// NodeEquals - Instantiations may optionally provide a way to compare a /// node with a specified ID. - virtual bool NodeEquals(Node *N, const FoldingSetNodeID &ID, + virtual bool NodeEquals(Node *N, const FoldingSetNodeID &ID, unsigned IDHash, FoldingSetNodeID &TempID) const { T *TN = static_cast<T *>(N); - return FoldingSetTrait<T>::Equals(*TN, ID, TempID); + return FoldingSetTrait<T>::Equals(*TN, ID, IDHash, TempID); } - /// NodeEquals - Instantiations may optionally provide a way to compute a + /// ComputeNodeHash - Instantiations may optionally provide a way to compute a /// hash value directly from a node. - virtual unsigned ComputeNodeHash(Node *N, - FoldingSetNodeID &TempID) const { + virtual unsigned ComputeNodeHash(Node *N, FoldingSetNodeID &TempID) const { T *TN = static_cast<T *>(N); return FoldingSetTrait<T>::ComputeHash(*TN, TempID); } @@ -465,10 +464,11 @@ private: ContextualFoldingSetTrait<T, Ctx>::Profile(*TN, ID, Context); } virtual bool NodeEquals(FoldingSetImpl::Node *N, - const FoldingSetNodeID &ID, + const FoldingSetNodeID &ID, unsigned IDHash, FoldingSetNodeID &TempID) const { T *TN = static_cast<T *>(N); - return ContextualFoldingSetTrait<T, Ctx>::Equals(*TN, ID, TempID, Context); + return ContextualFoldingSetTrait<T, Ctx>::Equals(*TN, ID, IDHash, TempID, + Context); } virtual unsigned ComputeNodeHash(FoldingSetImpl::Node *N, FoldingSetNodeID &TempID) const { diff --git a/include/llvm/ADT/GraphTraits.h b/include/llvm/ADT/GraphTraits.h index 0fd1f50..823caef 100644 --- a/include/llvm/ADT/GraphTraits.h +++ b/include/llvm/ADT/GraphTraits.h @@ -43,9 +43,12 @@ struct GraphTraits { // typedef ...iterator nodes_iterator; // static nodes_iterator nodes_begin(GraphType *G) // static nodes_iterator nodes_end (GraphType *G) - // // nodes_iterator/begin/end - Allow iteration over all nodes in the graph + // static unsigned size (GraphType *G) + // Return total number of nodes in the graph + // + // If anyone tries to use this class without having an appropriate // specialization, make an error. If you get this error, it's because you diff --git a/include/llvm/ADT/Hashing.h b/include/llvm/ADT/Hashing.h new file mode 100644 index 0000000..53032ee --- /dev/null +++ b/include/llvm/ADT/Hashing.h @@ -0,0 +1,770 @@ +//===-- llvm/ADT/Hashing.h - Utilities for hashing --------------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file implements the newly proposed standard C++ interfaces for hashing +// arbitrary data and building hash functions for user-defined types. This +// interface was originally proposed in N3333[1] and is currently under review +// for inclusion in a future TR and/or standard. +// +// The primary interfaces provide are comprised of one type and three functions: +// +// -- 'hash_code' class is an opaque type representing the hash code for some +// data. It is the intended product of hashing, and can be used to implement +// hash tables, checksumming, and other common uses of hashes. It is not an +// integer type (although it can be converted to one) because it is risky +// to assume much about the internals of a hash_code. In particular, each +// execution of the program has a high probability of producing a different +// hash_code for a given input. Thus their values are not stable to save or +// persist, and should only be used during the execution for the +// construction of hashing datastructures. +// +// -- 'hash_value' is a function designed to be overloaded for each +// user-defined type which wishes to be used within a hashing context. It +// should be overloaded within the user-defined type's namespace and found +// via ADL. Overloads for primitive types are provided by this library. +// +// -- 'hash_combine' and 'hash_combine_range' are functions designed to aid +// programmers in easily and intuitively combining a set of data into +// a single hash_code for their object. They should only logically be used +// within the implementation of a 'hash_value' routine or similar context. +// +// Note that 'hash_combine_range' contains very special logic for hashing +// a contiguous array of integers or pointers. This logic is *extremely* fast, +// on a modern Intel "Gainestown" Xeon (Nehalem uarch) @2.2 GHz, these were +// benchmarked at over 6.5 GiB/s for large keys, and <20 cycles/hash for keys +// under 32-bytes. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_ADT_HASHING_H +#define LLVM_ADT_HASHING_H + +#include "llvm/ADT/STLExtras.h" +#include "llvm/Support/DataTypes.h" +#include "llvm/Support/Host.h" +#include "llvm/Support/SwapByteOrder.h" +#include "llvm/Support/type_traits.h" +#include <algorithm> +#include <cassert> +#include <cstring> +#include <iterator> +#include <utility> + +// Allow detecting C++11 feature availability when building with Clang without +// breaking other compilers. +#ifndef __has_feature +# define __has_feature(x) 0 +#endif + +namespace llvm { + +/// \brief An opaque object representing a hash code. +/// +/// This object represents the result of hashing some entity. It is intended to +/// be used to implement hashtables or other hashing-based data structures. +/// While it wraps and exposes a numeric value, this value should not be +/// trusted to be stable or predictable across processes or executions. +/// +/// In order to obtain the hash_code for an object 'x': +/// \code +/// using llvm::hash_value; +/// llvm::hash_code code = hash_value(x); +/// \endcode +/// +/// Also note that there are two numerical values which are reserved, and the +/// implementation ensures will never be produced for real hash_codes. These +/// can be used as sentinels within hashing data structures. +class hash_code { + size_t value; + +public: + /// \brief Default construct a hash_code. + /// Note that this leaves the value uninitialized. + hash_code() {} + + /// \brief Form a hash code directly from a numerical value. + hash_code(size_t value) : value(value) {} + + /// \brief Convert the hash code to its numerical value for use. + /*explicit*/ operator size_t() const { return value; } + + friend bool operator==(const hash_code &lhs, const hash_code &rhs) { + return lhs.value == rhs.value; + } + friend bool operator!=(const hash_code &lhs, const hash_code &rhs) { + return lhs.value != rhs.value; + } + + /// \brief Allow a hash_code to be directly run through hash_value. + friend size_t hash_value(const hash_code &code) { return code.value; } +}; + +/// \brief Compute a hash_code for any integer value. +/// +/// Note that this function is intended to compute the same hash_code for +/// a particular value without regard to the pre-promotion type. This is in +/// contrast to hash_combine which may produce different hash_codes for +/// differing argument types even if they would implicit promote to a common +/// type without changing the value. +template <typename T> +typename enable_if<is_integral_or_enum<T>, hash_code>::type hash_value(T value); + +/// \brief Compute a hash_code for a pointer's address. +/// +/// N.B.: This hashes the *address*. Not the value and not the type. +template <typename T> hash_code hash_value(const T *ptr); + +/// \brief Compute a hash_code for a pair of objects. +template <typename T, typename U> +hash_code hash_value(const std::pair<T, U> &arg); + +/// \brief Compute a hash_code for a standard string. +template <typename T> +hash_code hash_value(const std::basic_string<T> &arg); + + +/// \brief Override the execution seed with a fixed value. +/// +/// This hashing library uses a per-execution seed designed to change on each +/// run with high probability in order to ensure that the hash codes are not +/// attackable and to ensure that output which is intended to be stable does +/// not rely on the particulars of the hash codes produced. +/// +/// That said, there are use cases where it is important to be able to +/// reproduce *exactly* a specific behavior. To that end, we provide a function +/// which will forcibly set the seed to a fixed value. This must be done at the +/// start of the program, before any hashes are computed. Also, it cannot be +/// undone. This makes it thread-hostile and very hard to use outside of +/// immediately on start of a simple program designed for reproducible +/// behavior. +void set_fixed_execution_hash_seed(size_t fixed_value); + + +// All of the implementation details of actually computing the various hash +// code values are held within this namespace. These routines are included in +// the header file mainly to allow inlining and constant propagation. +namespace hashing { +namespace detail { + +inline uint64_t fetch64(const char *p) { + uint64_t result; + memcpy(&result, p, sizeof(result)); + if (sys::isBigEndianHost()) + return sys::SwapByteOrder(result); + return result; +} + +inline uint32_t fetch32(const char *p) { + uint32_t result; + memcpy(&result, p, sizeof(result)); + if (sys::isBigEndianHost()) + return sys::SwapByteOrder(result); + return result; +} + +/// Some primes between 2^63 and 2^64 for various uses. +static const uint64_t k0 = 0xc3a5c85c97cb3127ULL; +static const uint64_t k1 = 0xb492b66fbe98f273ULL; +static const uint64_t k2 = 0x9ae16a3b2f90404fULL; +static const uint64_t k3 = 0xc949d7c7509e6557ULL; + +/// \brief Bitwise right rotate. +/// Normally this will compile to a single instruction, especially if the +/// shift is a manifest constant. +inline uint64_t rotate(uint64_t val, size_t shift) { + // Avoid shifting by 64: doing so yields an undefined result. + return shift == 0 ? val : ((val >> shift) | (val << (64 - shift))); +} + +inline uint64_t shift_mix(uint64_t val) { + return val ^ (val >> 47); +} + +inline uint64_t hash_16_bytes(uint64_t low, uint64_t high) { + // Murmur-inspired hashing. + const uint64_t kMul = 0x9ddfea08eb382d69ULL; + uint64_t a = (low ^ high) * kMul; + a ^= (a >> 47); + uint64_t b = (high ^ a) * kMul; + b ^= (b >> 47); + b *= kMul; + return b; +} + +inline uint64_t hash_1to3_bytes(const char *s, size_t len, uint64_t seed) { + uint8_t a = s[0]; + uint8_t b = s[len >> 1]; + uint8_t c = s[len - 1]; + uint32_t y = static_cast<uint32_t>(a) + (static_cast<uint32_t>(b) << 8); + uint32_t z = len + (static_cast<uint32_t>(c) << 2); + return shift_mix(y * k2 ^ z * k3 ^ seed) * k2; +} + +inline uint64_t hash_4to8_bytes(const char *s, size_t len, uint64_t seed) { + uint64_t a = fetch32(s); + return hash_16_bytes(len + (a << 3), seed ^ fetch32(s + len - 4)); +} + +inline uint64_t hash_9to16_bytes(const char *s, size_t len, uint64_t seed) { + uint64_t a = fetch64(s); + uint64_t b = fetch64(s + len - 8); + return hash_16_bytes(seed ^ a, rotate(b + len, len)) ^ b; +} + +inline uint64_t hash_17to32_bytes(const char *s, size_t len, uint64_t seed) { + uint64_t a = fetch64(s) * k1; + uint64_t b = fetch64(s + 8); + uint64_t c = fetch64(s + len - 8) * k2; + uint64_t d = fetch64(s + len - 16) * k0; + return hash_16_bytes(rotate(a - b, 43) + rotate(c ^ seed, 30) + d, + a + rotate(b ^ k3, 20) - c + len + seed); +} + +inline uint64_t hash_33to64_bytes(const char *s, size_t len, uint64_t seed) { + uint64_t z = fetch64(s + 24); + uint64_t a = fetch64(s) + (len + fetch64(s + len - 16)) * k0; + uint64_t b = rotate(a + z, 52); + uint64_t c = rotate(a, 37); + a += fetch64(s + 8); + c += rotate(a, 7); + a += fetch64(s + 16); + uint64_t vf = a + z; + uint64_t vs = b + rotate(a, 31) + c; + a = fetch64(s + 16) + fetch64(s + len - 32); + z = fetch64(s + len - 8); + b = rotate(a + z, 52); + c = rotate(a, 37); + a += fetch64(s + len - 24); + c += rotate(a, 7); + a += fetch64(s + len - 16); + uint64_t wf = a + z; + uint64_t ws = b + rotate(a, 31) + c; + uint64_t r = shift_mix((vf + ws) * k2 + (wf + vs) * k0); + return shift_mix((seed ^ (r * k0)) + vs) * k2; +} + +inline uint64_t hash_short(const char *s, size_t length, uint64_t seed) { + if (length >= 4 && length <= 8) + return hash_4to8_bytes(s, length, seed); + if (length > 8 && length <= 16) + return hash_9to16_bytes(s, length, seed); + if (length > 16 && length <= 32) + return hash_17to32_bytes(s, length, seed); + if (length > 32) + return hash_33to64_bytes(s, length, seed); + if (length != 0) + return hash_1to3_bytes(s, length, seed); + + return k2 ^ seed; +} + +/// \brief The intermediate state used during hashing. +/// Currently, the algorithm for computing hash codes is based on CityHash and +/// keeps 56 bytes of arbitrary state. +struct hash_state { + uint64_t h0, h1, h2, h3, h4, h5, h6; + uint64_t seed; + + /// \brief Create a new hash_state structure and initialize it based on the + /// seed and the first 64-byte chunk. + /// This effectively performs the initial mix. + static hash_state create(const char *s, uint64_t seed) { + hash_state state = { + 0, seed, hash_16_bytes(seed, k1), rotate(seed ^ k1, 49), + seed * k1, shift_mix(seed), 0, seed }; + state.h6 = hash_16_bytes(state.h4, state.h5); + state.mix(s); + return state; + } + + /// \brief Mix 32-bytes from the input sequence into the 16-bytes of 'a' + /// and 'b', including whatever is already in 'a' and 'b'. + static void mix_32_bytes(const char *s, uint64_t &a, uint64_t &b) { + a += fetch64(s); + uint64_t c = fetch64(s + 24); + b = rotate(b + a + c, 21); + uint64_t d = a; + a += fetch64(s + 8) + fetch64(s + 16); + b += rotate(a, 44) + d; + a += c; + } + + /// \brief Mix in a 64-byte buffer of data. + /// We mix all 64 bytes even when the chunk length is smaller, but we + /// record the actual length. + void mix(const char *s) { + h0 = rotate(h0 + h1 + h3 + fetch64(s + 8), 37) * k1; + h1 = rotate(h1 + h4 + fetch64(s + 48), 42) * k1; + h0 ^= h6; + h1 += h3 + fetch64(s + 40); + h2 = rotate(h2 + h5, 33) * k1; + h3 = h4 * k1; + h4 = h0 + h5; + mix_32_bytes(s, h3, h4); + h5 = h2 + h6; + h6 = h1 + fetch64(s + 16); + mix_32_bytes(s + 32, h5, h6); + std::swap(h2, h0); + } + + /// \brief Compute the final 64-bit hash code value based on the current + /// state and the length of bytes hashed. + uint64_t finalize(size_t length) { + return hash_16_bytes(hash_16_bytes(h3, h5) + shift_mix(h1) * k1 + h2, + hash_16_bytes(h4, h6) + shift_mix(length) * k1 + h0); + } +}; + + +/// \brief A global, fixed seed-override variable. +/// +/// This variable can be set using the \see llvm::set_fixed_execution_seed +/// function. See that function for details. Do not, under any circumstances, +/// set or read this variable. +extern size_t fixed_seed_override; + +inline size_t get_execution_seed() { + // FIXME: This needs to be a per-execution seed. This is just a placeholder + // implementation. Switching to a per-execution seed is likely to flush out + // instability bugs and so will happen as its own commit. + // + // However, if there is a fixed seed override set the first time this is + // called, return that instead of the per-execution seed. + const uint64_t seed_prime = 0xff51afd7ed558ccdULL; + static size_t seed = fixed_seed_override ? fixed_seed_override + : (size_t)seed_prime; + return seed; +} + + +/// \brief Trait to indicate whether a type's bits can be hashed directly. +/// +/// A type trait which is true if we want to combine values for hashing by +/// reading the underlying data. It is false if values of this type must +/// first be passed to hash_value, and the resulting hash_codes combined. +// +// FIXME: We want to replace is_integral_or_enum and is_pointer here with +// a predicate which asserts that comparing the underlying storage of two +// values of the type for equality is equivalent to comparing the two values +// for equality. For all the platforms we care about, this holds for integers +// and pointers, but there are platforms where it doesn't and we would like to +// support user-defined types which happen to satisfy this property. +template <typename T> struct is_hashable_data + : integral_constant<bool, ((is_integral_or_enum<T>::value || + is_pointer<T>::value) && + 64 % sizeof(T) == 0)> {}; + +// Special case std::pair to detect when both types are viable and when there +// is no alignment-derived padding in the pair. This is a bit of a lie because +// std::pair isn't truly POD, but it's close enough in all reasonable +// implementations for our use case of hashing the underlying data. +template <typename T, typename U> struct is_hashable_data<std::pair<T, U> > + : integral_constant<bool, (is_hashable_data<T>::value && + is_hashable_data<U>::value && + (sizeof(T) + sizeof(U)) == + sizeof(std::pair<T, U>))> {}; + +/// \brief Helper to get the hashable data representation for a type. +/// This variant is enabled when the type itself can be used. +template <typename T> +typename enable_if<is_hashable_data<T>, T>::type +get_hashable_data(const T &value) { + return value; +} +/// \brief Helper to get the hashable data representation for a type. +/// This variant is enabled when we must first call hash_value and use the +/// result as our data. +template <typename T> +typename enable_if_c<!is_hashable_data<T>::value, size_t>::type +get_hashable_data(const T &value) { + using ::llvm::hash_value; + return hash_value(value); +} + +/// \brief Helper to store data from a value into a buffer and advance the +/// pointer into that buffer. +/// +/// This routine first checks whether there is enough space in the provided +/// buffer, and if not immediately returns false. If there is space, it +/// copies the underlying bytes of value into the buffer, advances the +/// buffer_ptr past the copied bytes, and returns true. +template <typename T> +bool store_and_advance(char *&buffer_ptr, char *buffer_end, const T& value, + size_t offset = 0) { + size_t store_size = sizeof(value) - offset; + if (buffer_ptr + store_size > buffer_end) + return false; + const char *value_data = reinterpret_cast<const char *>(&value); + memcpy(buffer_ptr, value_data + offset, store_size); + buffer_ptr += store_size; + return true; +} + +/// \brief Implement the combining of integral values into a hash_code. +/// +/// This overload is selected when the value type of the iterator is +/// integral. Rather than computing a hash_code for each object and then +/// combining them, this (as an optimization) directly combines the integers. +template <typename InputIteratorT> +hash_code hash_combine_range_impl(InputIteratorT first, InputIteratorT last) { + typedef typename std::iterator_traits<InputIteratorT>::value_type ValueT; + const size_t seed = get_execution_seed(); + char buffer[64], *buffer_ptr = buffer; + char *const buffer_end = buffer_ptr + array_lengthof(buffer); + while (first != last && store_and_advance(buffer_ptr, buffer_end, + get_hashable_data(*first))) + ++first; + if (first == last) + return hash_short(buffer, buffer_ptr - buffer, seed); + assert(buffer_ptr == buffer_end); + + hash_state state = state.create(buffer, seed); + size_t length = 64; + while (first != last) { + // Fill up the buffer. We don't clear it, which re-mixes the last round + // when only a partial 64-byte chunk is left. + buffer_ptr = buffer; + while (first != last && store_and_advance(buffer_ptr, buffer_end, + get_hashable_data(*first))) + ++first; + + // Rotate the buffer if we did a partial fill in order to simulate doing + // a mix of the last 64-bytes. That is how the algorithm works when we + // have a contiguous byte sequence, and we want to emulate that here. + std::rotate(buffer, buffer_ptr, buffer_end); + + // Mix this chunk into the current state. + state.mix(buffer); + length += buffer_ptr - buffer; + }; + + return state.finalize(length); +} + +/// \brief Implement the combining of integral values into a hash_code. +/// +/// This overload is selected when the value type of the iterator is integral +/// and when the input iterator is actually a pointer. Rather than computing +/// a hash_code for each object and then combining them, this (as an +/// optimization) directly combines the integers. Also, because the integers +/// are stored in contiguous memory, this routine avoids copying each value +/// and directly reads from the underlying memory. +template <typename ValueT> +typename enable_if<is_hashable_data<ValueT>, hash_code>::type +hash_combine_range_impl(ValueT *first, ValueT *last) { + const size_t seed = get_execution_seed(); + const char *s_begin = reinterpret_cast<const char *>(first); + const char *s_end = reinterpret_cast<const char *>(last); + const size_t length = std::distance(s_begin, s_end); + if (length <= 64) + return hash_short(s_begin, length, seed); + + const char *s_aligned_end = s_begin + (length & ~63); + hash_state state = state.create(s_begin, seed); + s_begin += 64; + while (s_begin != s_aligned_end) { + state.mix(s_begin); + s_begin += 64; + } + if (length & 63) + state.mix(s_end - 64); + + return state.finalize(length); +} + +} // namespace detail +} // namespace hashing + + +/// \brief Compute a hash_code for a sequence of values. +/// +/// This hashes a sequence of values. It produces the same hash_code as +/// 'hash_combine(a, b, c, ...)', but can run over arbitrary sized sequences +/// and is significantly faster given pointers and types which can be hashed as +/// a sequence of bytes. +template <typename InputIteratorT> +hash_code hash_combine_range(InputIteratorT first, InputIteratorT last) { + return ::llvm::hashing::detail::hash_combine_range_impl(first, last); +} + + +// Implementation details for hash_combine. +namespace hashing { +namespace detail { + +/// \brief Helper class to manage the recursive combining of hash_combine +/// arguments. +/// +/// This class exists to manage the state and various calls involved in the +/// recursive combining of arguments used in hash_combine. It is particularly +/// useful at minimizing the code in the recursive calls to ease the pain +/// caused by a lack of variadic functions. +struct hash_combine_recursive_helper { + char buffer[64]; + hash_state state; + const size_t seed; + +public: + /// \brief Construct a recursive hash combining helper. + /// + /// This sets up the state for a recursive hash combine, including getting + /// the seed and buffer setup. + hash_combine_recursive_helper() + : seed(get_execution_seed()) {} + + /// \brief Combine one chunk of data into the current in-flight hash. + /// + /// This merges one chunk of data into the hash. First it tries to buffer + /// the data. If the buffer is full, it hashes the buffer into its + /// hash_state, empties it, and then merges the new chunk in. This also + /// handles cases where the data straddles the end of the buffer. + template <typename T> + char *combine_data(size_t &length, char *buffer_ptr, char *buffer_end, T data) { + if (!store_and_advance(buffer_ptr, buffer_end, data)) { + // Check for skew which prevents the buffer from being packed, and do + // a partial store into the buffer to fill it. This is only a concern + // with the variadic combine because that formation can have varying + // argument types. + size_t partial_store_size = buffer_end - buffer_ptr; + memcpy(buffer_ptr, &data, partial_store_size); + + // If the store fails, our buffer is full and ready to hash. We have to + // either initialize the hash state (on the first full buffer) or mix + // this buffer into the existing hash state. Length tracks the *hashed* + // length, not the buffered length. + if (length == 0) { + state = state.create(buffer, seed); + length = 64; + } else { + // Mix this chunk into the current state and bump length up by 64. + state.mix(buffer); + length += 64; + } + // Reset the buffer_ptr to the head of the buffer for the next chunk of + // data. + buffer_ptr = buffer; + + // Try again to store into the buffer -- this cannot fail as we only + // store types smaller than the buffer. + if (!store_and_advance(buffer_ptr, buffer_end, data, + partial_store_size)) + abort(); + } + return buffer_ptr; + } + +#if defined(__has_feature) && __has_feature(__cxx_variadic_templates__) + + /// \brief Recursive, variadic combining method. + /// + /// This function recurses through each argument, combining that argument + /// into a single hash. + template <typename T, typename ...Ts> + hash_code combine(size_t length, char *buffer_ptr, char *buffer_end, + const T &arg, const Ts &...args) { + buffer_ptr = combine_data(length, buffer_ptr, buffer_end, get_hashable_data(arg)); + + // Recurse to the next argument. + return combine(length, buffer_ptr, buffer_end, args...); + } + +#else + // Manually expanded recursive combining methods. See variadic above for + // documentation. + + template <typename T1, typename T2, typename T3, typename T4, typename T5, + typename T6> + hash_code combine(size_t length, char *buffer_ptr, char *buffer_end, + const T1 &arg1, const T2 &arg2, const T3 &arg3, + const T4 &arg4, const T5 &arg5, const T6 &arg6) { + buffer_ptr = combine_data(length, buffer_ptr, buffer_end, get_hashable_data(arg1)); + return combine(length, buffer_ptr, buffer_end, arg2, arg3, arg4, arg5, arg6); + } + template <typename T1, typename T2, typename T3, typename T4, typename T5> + hash_code combine(size_t length, char *buffer_ptr, char *buffer_end, + const T1 &arg1, const T2 &arg2, const T3 &arg3, + const T4 &arg4, const T5 &arg5) { + buffer_ptr = combine_data(length, buffer_ptr, buffer_end, get_hashable_data(arg1)); + return combine(length, buffer_ptr, buffer_end, arg2, arg3, arg4, arg5); + } + template <typename T1, typename T2, typename T3, typename T4> + hash_code combine(size_t length, char *buffer_ptr, char *buffer_end, + const T1 &arg1, const T2 &arg2, const T3 &arg3, + const T4 &arg4) { + buffer_ptr = combine_data(length, buffer_ptr, buffer_end, get_hashable_data(arg1)); + return combine(length, buffer_ptr, buffer_end, arg2, arg3, arg4); + } + template <typename T1, typename T2, typename T3> + hash_code combine(size_t length, char *buffer_ptr, char *buffer_end, + const T1 &arg1, const T2 &arg2, const T3 &arg3) { + buffer_ptr = combine_data(length, buffer_ptr, buffer_end, get_hashable_data(arg1)); + return combine(length, buffer_ptr, buffer_end, arg2, arg3); + } + template <typename T1, typename T2> + hash_code combine(size_t length, char *buffer_ptr, char *buffer_end, + const T1 &arg1, const T2 &arg2) { + buffer_ptr = combine_data(length, buffer_ptr, buffer_end, get_hashable_data(arg1)); + return combine(length, buffer_ptr, buffer_end, arg2); + } + template <typename T1> + hash_code combine(size_t length, char *buffer_ptr, char *buffer_end, + const T1 &arg1) { + buffer_ptr = combine_data(length, buffer_ptr, buffer_end, get_hashable_data(arg1)); + return combine(length, buffer_ptr, buffer_end); + } + +#endif + + /// \brief Base case for recursive, variadic combining. + /// + /// The base case when combining arguments recursively is reached when all + /// arguments have been handled. It flushes the remaining buffer and + /// constructs a hash_code. + hash_code combine(size_t length, char *buffer_ptr, char *buffer_end) { + // Check whether the entire set of values fit in the buffer. If so, we'll + // use the optimized short hashing routine and skip state entirely. + if (length == 0) + return hash_short(buffer, buffer_ptr - buffer, seed); + + // Mix the final buffer, rotating it if we did a partial fill in order to + // simulate doing a mix of the last 64-bytes. That is how the algorithm + // works when we have a contiguous byte sequence, and we want to emulate + // that here. + std::rotate(buffer, buffer_ptr, buffer_end); + + // Mix this chunk into the current state. + state.mix(buffer); + length += buffer_ptr - buffer; + + return state.finalize(length); + } +}; + +} // namespace detail +} // namespace hashing + + +#if __has_feature(__cxx_variadic_templates__) + +/// \brief Combine values into a single hash_code. +/// +/// This routine accepts a varying number of arguments of any type. It will +/// attempt to combine them into a single hash_code. For user-defined types it +/// attempts to call a \see hash_value overload (via ADL) for the type. For +/// integer and pointer types it directly combines their data into the +/// resulting hash_code. +/// +/// The result is suitable for returning from a user's hash_value +/// *implementation* for their user-defined type. Consumers of a type should +/// *not* call this routine, they should instead call 'hash_value'. +template <typename ...Ts> hash_code hash_combine(const Ts &...args) { + // Recursively hash each argument using a helper class. + ::llvm::hashing::detail::hash_combine_recursive_helper helper; + return helper.combine(0, helper.buffer, helper.buffer + 64, args...); +} + +#else + +// What follows are manually exploded overloads for each argument width. See +// the above variadic definition for documentation and specification. + +template <typename T1, typename T2, typename T3, typename T4, typename T5, + typename T6> +hash_code hash_combine(const T1 &arg1, const T2 &arg2, const T3 &arg3, + const T4 &arg4, const T5 &arg5, const T6 &arg6) { + ::llvm::hashing::detail::hash_combine_recursive_helper helper; + return helper.combine(0, helper.buffer, helper.buffer + 64, + arg1, arg2, arg3, arg4, arg5, arg6); +} +template <typename T1, typename T2, typename T3, typename T4, typename T5> +hash_code hash_combine(const T1 &arg1, const T2 &arg2, const T3 &arg3, + const T4 &arg4, const T5 &arg5) { + ::llvm::hashing::detail::hash_combine_recursive_helper helper; + return helper.combine(0, helper.buffer, helper.buffer + 64, + arg1, arg2, arg3, arg4, arg5); +} +template <typename T1, typename T2, typename T3, typename T4> +hash_code hash_combine(const T1 &arg1, const T2 &arg2, const T3 &arg3, + const T4 &arg4) { + ::llvm::hashing::detail::hash_combine_recursive_helper helper; + return helper.combine(0, helper.buffer, helper.buffer + 64, + arg1, arg2, arg3, arg4); +} +template <typename T1, typename T2, typename T3> +hash_code hash_combine(const T1 &arg1, const T2 &arg2, const T3 &arg3) { + ::llvm::hashing::detail::hash_combine_recursive_helper helper; + return helper.combine(0, helper.buffer, helper.buffer + 64, arg1, arg2, arg3); +} +template <typename T1, typename T2> +hash_code hash_combine(const T1 &arg1, const T2 &arg2) { + ::llvm::hashing::detail::hash_combine_recursive_helper helper; + return helper.combine(0, helper.buffer, helper.buffer + 64, arg1, arg2); +} +template <typename T1> +hash_code hash_combine(const T1 &arg1) { + ::llvm::hashing::detail::hash_combine_recursive_helper helper; + return helper.combine(0, helper.buffer, helper.buffer + 64, arg1); +} + +#endif + + +// Implementation details for implementatinos of hash_value overloads provided +// here. +namespace hashing { +namespace detail { + +/// \brief Helper to hash the value of a single integer. +/// +/// Overloads for smaller integer types are not provided to ensure consistent +/// behavior in the presence of integral promotions. Essentially, +/// "hash_value('4')" and "hash_value('0' + 4)" should be the same. +inline hash_code hash_integer_value(uint64_t value) { + // Similar to hash_4to8_bytes but using a seed instead of length. + const uint64_t seed = get_execution_seed(); + const char *s = reinterpret_cast<const char *>(&value); + const uint64_t a = fetch32(s); + return hash_16_bytes(seed + (a << 3), fetch32(s + 4)); +} + +} // namespace detail +} // namespace hashing + +// Declared and documented above, but defined here so that any of the hashing +// infrastructure is available. +template <typename T> +typename enable_if<is_integral_or_enum<T>, hash_code>::type +hash_value(T value) { + return ::llvm::hashing::detail::hash_integer_value(value); +} + +// Declared and documented above, but defined here so that any of the hashing +// infrastructure is available. +template <typename T> hash_code hash_value(const T *ptr) { + return ::llvm::hashing::detail::hash_integer_value( + reinterpret_cast<uintptr_t>(ptr)); +} + +// Declared and documented above, but defined here so that any of the hashing +// infrastructure is available. +template <typename T, typename U> +hash_code hash_value(const std::pair<T, U> &arg) { + return hash_combine(arg.first, arg.second); +} + +// Declared and documented above, but defined here so that any of the hashing +// infrastructure is available. +template <typename T> +hash_code hash_value(const std::basic_string<T> &arg) { + return hash_combine_range(arg.begin(), arg.end()); +} + +} // namespace llvm + +#endif diff --git a/include/llvm/ADT/ImmutableSet.h b/include/llvm/ADT/ImmutableSet.h index d597a7c..89b1648 100644 --- a/include/llvm/ADT/ImmutableSet.h +++ b/include/llvm/ADT/ImmutableSet.h @@ -18,6 +18,7 @@ #include "llvm/ADT/DenseMap.h" #include "llvm/ADT/FoldingSet.h" #include "llvm/Support/DataTypes.h" +#include "llvm/Support/ErrorHandling.h" #include <cassert> #include <functional> #include <vector> @@ -346,7 +347,7 @@ public: if (prev) prev->next = next; else - factory->Cache[computeDigest()] = next; + factory->Cache[factory->maskCacheIndex(computeDigest())] = next; } // We need to clear the mutability bit in case we are @@ -428,6 +429,11 @@ protected: TreeTy* getRight(TreeTy* T) const { return T->getRight(); } value_type_ref getValue(TreeTy* T) const { return T->value; } + // Make sure the index is not the Tombstone or Entry key of the DenseMap. + static inline unsigned maskCacheIndex(unsigned I) { + return (I & ~0x02); + } + unsigned incrementHeight(TreeTy* L, TreeTy* R) const { unsigned hl = getHeight(L); unsigned hr = getHeight(R); @@ -610,7 +616,7 @@ public: // Search the hashtable for another tree with the same digest, and // if find a collision compare those trees by their contents. unsigned digest = TNew->computeDigest(); - TreeTy *&entry = Cache[digest]; + TreeTy *&entry = Cache[maskCacheIndex(digest)]; do { if (!entry) break; @@ -686,7 +692,7 @@ public: stack.back() |= VisitedRight; break; default: - assert(false && "Unreachable."); + llvm_unreachable("Unreachable."); } } @@ -722,7 +728,7 @@ public: skipToParent(); break; default: - assert(false && "Unreachable."); + llvm_unreachable("Unreachable."); } return *this; } @@ -747,7 +753,7 @@ public: stack.push_back(reinterpret_cast<uintptr_t>(R) | VisitedRight); break; default: - assert(false && "Unreachable."); + llvm_unreachable("Unreachable."); } return *this; } diff --git a/include/llvm/ADT/IntervalMap.h b/include/llvm/ADT/IntervalMap.h index 1230e8f..931b67e 100644 --- a/include/llvm/ADT/IntervalMap.h +++ b/include/llvm/ADT/IntervalMap.h @@ -739,7 +739,7 @@ public: // A Path is used by iterators to represent a position in a B+-tree, and the // path to get there from the root. // -// The Path class also constains the tree navigation code that doesn't have to +// The Path class also contains the tree navigation code that doesn't have to // be templatized. // //===----------------------------------------------------------------------===// @@ -1977,7 +1977,7 @@ iterator::overflow(unsigned Level) { CurSize[Nodes] = CurSize[NewNode]; Node[Nodes] = Node[NewNode]; CurSize[NewNode] = 0; - Node[NewNode] = this->map->newNode<NodeT>(); + Node[NewNode] = this->map->template newNode<NodeT>(); ++Nodes; } diff --git a/include/llvm/ADT/IntrusiveRefCntPtr.h b/include/llvm/ADT/IntrusiveRefCntPtr.h index 2f6fd2b..3a1a3f4 100644 --- a/include/llvm/ADT/IntrusiveRefCntPtr.h +++ b/include/llvm/ADT/IntrusiveRefCntPtr.h @@ -46,6 +46,7 @@ namespace llvm { public: RefCountedBase() : ref_cnt(0) {} + RefCountedBase(const RefCountedBase &) : ref_cnt(0) {} void Retain() const { ++ref_cnt; } void Release() const { @@ -64,9 +65,12 @@ namespace llvm { //===----------------------------------------------------------------------===// class RefCountedBaseVPTR { mutable unsigned ref_cnt; + virtual void anchor(); protected: RefCountedBaseVPTR() : ref_cnt(0) {} + RefCountedBaseVPTR(const RefCountedBaseVPTR &) : ref_cnt(0) {} + virtual ~RefCountedBaseVPTR() {} void Retain() const { ++ref_cnt; } @@ -76,9 +80,15 @@ namespace llvm { } template <typename T> - friend class IntrusiveRefCntPtr; + friend struct IntrusiveRefCntPtrInfo; }; + + template <typename T> struct IntrusiveRefCntPtrInfo { + static void retain(T *obj) { obj->Retain(); } + static void release(T *obj) { obj->Release(); } + }; + //===----------------------------------------------------------------------===// /// IntrusiveRefCntPtr - A template class that implements a "smart pointer" /// that assumes the wrapped object has a reference count associated @@ -105,7 +115,7 @@ namespace llvm { explicit IntrusiveRefCntPtr() : Obj(0) {} - explicit IntrusiveRefCntPtr(T* obj) : Obj(obj) { + IntrusiveRefCntPtr(T* obj) : Obj(obj) { retain(); } @@ -153,14 +163,19 @@ namespace llvm { other.Obj = Obj; Obj = tmp; } - + + void reset() { + release(); + Obj = 0; + } + void resetWithoutRelease() { Obj = 0; } private: - void retain() { if (Obj) Obj->Retain(); } - void release() { if (Obj) Obj->Release(); } + void retain() { if (Obj) IntrusiveRefCntPtrInfo<T>::retain(Obj); } + void release() { if (Obj) IntrusiveRefCntPtrInfo<T>::release(Obj); } void replace(T* S) { this_type(S).swap(*this); diff --git a/include/llvm/ADT/PointerIntPair.h b/include/llvm/ADT/PointerIntPair.h index 85dbba2..ccdcd1a 100644 --- a/include/llvm/ADT/PointerIntPair.h +++ b/include/llvm/ADT/PointerIntPair.h @@ -92,10 +92,14 @@ public: } PointerTy const *getAddrOfPointer() const { + return const_cast<PointerIntPair *>(this)->getAddrOfPointer(); + } + + PointerTy *getAddrOfPointer() { assert(Value == reinterpret_cast<intptr_t>(getPointer()) && "Can only return the address if IntBits is cleared and " "PtrTraits doesn't change the pointer"); - return reinterpret_cast<PointerTy const *>(&Value); + return reinterpret_cast<PointerTy *>(&Value); } void *getOpaqueValue() const { return reinterpret_cast<void*>(Value); } diff --git a/include/llvm/ADT/PointerUnion.h b/include/llvm/ADT/PointerUnion.h index 487096a..614b59c 100644 --- a/include/llvm/ADT/PointerUnion.h +++ b/include/llvm/ADT/PointerUnion.h @@ -142,16 +142,19 @@ namespace llvm { return T(); } - /// \brief If the union is set to the first pointer type we can get an - /// address pointing to it. - template <typename T> - PT1 const *getAddrOf() const { + /// \brief If the union is set to the first pointer type get an address + /// pointing to it. + PT1 const *getAddrOfPtr1() const { + return const_cast<PointerUnion *>(this)->getAddrOfPtr1(); + } + + /// \brief If the union is set to the first pointer type get an address + /// pointing to it. + PT1 *getAddrOfPtr1() { assert(is<PT1>() && "Val is not the first pointer"); assert(get<PT1>() == Val.getPointer() && "Can't get the address because PointerLikeTypeTraits changes the ptr"); - T const *can_only_get_address_of_first_pointer_type - = reinterpret_cast<PT1 const *>(Val.getAddrOfPointer()); - return can_only_get_address_of_first_pointer_type; + return (PT1 *)Val.getAddrOfPointer(); } /// Assignment operators - Allow assigning into this union from either @@ -263,7 +266,7 @@ namespace llvm { ::llvm::PointerUnionTypeSelector<PT1, T, IsInnerUnion, ::llvm::PointerUnionTypeSelector<PT2, T, IsInnerUnion, IsPT3 > >::Return Ty; - return Ty(Val).is<T>(); + return Ty(Val).template is<T>(); } /// get<T>() - Return the value of the specified pointer type. If the @@ -276,7 +279,7 @@ namespace llvm { ::llvm::PointerUnionTypeSelector<PT1, T, IsInnerUnion, ::llvm::PointerUnionTypeSelector<PT2, T, IsInnerUnion, IsPT3 > >::Return Ty; - return Ty(Val).get<T>(); + return Ty(Val).template get<T>(); } /// dyn_cast<T>() - If the current value is of the specified pointer type, diff --git a/include/llvm/ADT/SetVector.h b/include/llvm/ADT/SetVector.h index abe2067..965f0de 100644 --- a/include/llvm/ADT/SetVector.h +++ b/include/llvm/ADT/SetVector.h @@ -144,6 +144,12 @@ public: set_.erase(back()); vector_.pop_back(); } + + T pop_back_val() { + T Ret = back(); + pop_back(); + return Ret; + } bool operator==(const SetVector &that) const { return vector_ == that.vector_; diff --git a/include/llvm/ADT/SmallBitVector.h b/include/llvm/ADT/SmallBitVector.h index b15b3ee..a3469a1 100644 --- a/include/llvm/ADT/SmallBitVector.h +++ b/include/llvm/ADT/SmallBitVector.h @@ -175,7 +175,7 @@ public: return CountPopulation_32(Bits); if (sizeof(uintptr_t) * CHAR_BIT == 64) return CountPopulation_64(Bits); - assert(0 && "Unsupported!"); + llvm_unreachable("Unsupported!"); } return getPointer()->count(); } @@ -212,7 +212,7 @@ public: return CountTrailingZeros_32(Bits); if (sizeof(uintptr_t) * CHAR_BIT == 64) return CountTrailingZeros_64(Bits); - assert(0 && "Unsupported!"); + llvm_unreachable("Unsupported!"); } return getPointer()->find_first(); } @@ -230,7 +230,7 @@ public: return CountTrailingZeros_32(Bits); if (sizeof(uintptr_t) * CHAR_BIT == 64) return CountTrailingZeros_64(Bits); - assert(0 && "Unsupported!"); + llvm_unreachable("Unsupported!"); } return getPointer()->find_next(Prev); } diff --git a/include/llvm/ADT/SmallPtrSet.h b/include/llvm/ADT/SmallPtrSet.h index 9992858..70693d5 100644 --- a/include/llvm/ADT/SmallPtrSet.h +++ b/include/llvm/ADT/SmallPtrSet.h @@ -137,6 +137,10 @@ private: void operator=(const SmallPtrSetImpl &RHS); // DO NOT IMPLEMENT. protected: + /// swap - Swaps the elements of two sets. + /// Note: This method assumes that both sets have the same small size. + void swap(SmallPtrSetImpl &RHS); + void CopyFrom(const SmallPtrSetImpl &RHS); }; @@ -287,8 +291,20 @@ public: return *this; } + /// swap - Swaps the elements of two sets. + void swap(SmallPtrSet<PtrType, SmallSize> &RHS) { + SmallPtrSetImpl::swap(RHS); + } }; } +namespace std { + /// Implement std::swap in terms of SmallPtrSet swap. + template<class T, unsigned N> + inline void swap(llvm::SmallPtrSet<T, N> &LHS, llvm::SmallPtrSet<T, N> &RHS) { + LHS.swap(RHS); + } +} + #endif diff --git a/include/llvm/ADT/SmallSet.h b/include/llvm/ADT/SmallSet.h index d03f1be..cd117f5 100644 --- a/include/llvm/ADT/SmallSet.h +++ b/include/llvm/ADT/SmallSet.h @@ -27,13 +27,13 @@ namespace llvm { /// /// Note that this set does not provide a way to iterate over members in the /// set. -template <typename T, unsigned N> +template <typename T, unsigned N, typename C = std::less<T> > class SmallSet { /// Use a SmallVector to hold the elements here (even though it will never /// reach its 'large' stage) to avoid calling the default ctors of elements /// we will never use. SmallVector<T, N> Vector; - std::set<T> Set; + std::set<T, C> Set; typedef typename SmallVector<T, N>::const_iterator VIterator; typedef typename SmallVector<T, N>::iterator mutable_iterator; public: diff --git a/include/llvm/ADT/SmallString.h b/include/llvm/ADT/SmallString.h index da26416..199783b 100644 --- a/include/llvm/ADT/SmallString.h +++ b/include/llvm/ADT/SmallString.h @@ -24,21 +24,244 @@ namespace llvm { template<unsigned InternalLen> class SmallString : public SmallVector<char, InternalLen> { public: - // Default ctor - Initialize to empty. + /// Default ctor - Initialize to empty. SmallString() {} - // Initialize from a StringRef. + /// Initialize from a StringRef. SmallString(StringRef S) : SmallVector<char, InternalLen>(S.begin(), S.end()) {} - // Initialize with a range. + /// Initialize with a range. template<typename ItTy> SmallString(ItTy S, ItTy E) : SmallVector<char, InternalLen>(S, E) {} - // Copy ctor. + /// Copy ctor. SmallString(const SmallString &RHS) : SmallVector<char, InternalLen>(RHS) {} + // Note that in order to add new overloads for append & assign, we have to + // duplicate the inherited versions so as not to inadvertently hide them. + + /// @} + /// @name String Assignment + /// @{ + + /// Assign from a repeated element + void assign(unsigned NumElts, char Elt) { + this->SmallVectorImpl<char>::assign(NumElts, Elt); + } + + /// Assign from an iterator pair + template<typename in_iter> + void assign(in_iter S, in_iter E) { + this->clear(); + SmallVectorImpl<char>::append(S, E); + } + + /// Assign from a StringRef + void assign(StringRef RHS) { + this->clear(); + SmallVectorImpl<char>::append(RHS.begin(), RHS.end()); + } + + /// Assign from a SmallVector + void assign(const SmallVectorImpl<char> &RHS) { + this->clear(); + SmallVectorImpl<char>::append(RHS.begin(), RHS.end()); + } + + /// @} + /// @name String Concatenation + /// @{ + + /// Append from an iterator pair + template<typename in_iter> + void append(in_iter S, in_iter E) { + SmallVectorImpl<char>::append(S, E); + } + + /// Append from a StringRef + void append(StringRef RHS) { + SmallVectorImpl<char>::append(RHS.begin(), RHS.end()); + } + + /// Append from a SmallVector + void append(const SmallVectorImpl<char> &RHS) { + SmallVectorImpl<char>::append(RHS.begin(), RHS.end()); + } + + /// @} + /// @name String Comparison + /// @{ + + /// equals - Check for string equality, this is more efficient than + /// compare() when the relative ordering of inequal strings isn't needed. + bool equals(StringRef RHS) const { + return str().equals(RHS); + } + + /// equals_lower - Check for string equality, ignoring case. + bool equals_lower(StringRef RHS) const { + return str().equals_lower(RHS); + } + + /// compare - Compare two strings; the result is -1, 0, or 1 if this string + /// is lexicographically less than, equal to, or greater than the \arg RHS. + int compare(StringRef RHS) const { + return str().compare(RHS); + } + + /// compare_lower - Compare two strings, ignoring case. + int compare_lower(StringRef RHS) const { + return str().compare_lower(RHS); + } + + /// compare_numeric - Compare two strings, treating sequences of digits as + /// numbers. + int compare_numeric(StringRef RHS) const { + return str().compare_numeric(RHS); + } + + /// @} + /// @name String Predicates + /// @{ + + /// startswith - Check if this string starts with the given \arg Prefix. + bool startswith(StringRef Prefix) const { + return str().startswith(Prefix); + } + + /// endswith - Check if this string ends with the given \arg Suffix. + bool endswith(StringRef Suffix) const { + return str().endswith(Suffix); + } + + /// @} + /// @name String Searching + /// @{ + + /// find - Search for the first character \arg C in the string. + /// + /// \return - The index of the first occurrence of \arg C, or npos if not + /// found. + size_t find(char C, size_t From = 0) const { + return str().find(C, From); + } + + /// find - Search for the first string \arg Str in the string. + /// + /// \return - The index of the first occurrence of \arg Str, or npos if not + /// found. + size_t find(StringRef Str, size_t From = 0) const { + return str().find(Str, From); + } + + /// rfind - Search for the last character \arg C in the string. + /// + /// \return - The index of the last occurrence of \arg C, or npos if not + /// found. + size_t rfind(char C, size_t From = StringRef::npos) const { + return str().rfind(C, From); + } + + /// rfind - Search for the last string \arg Str in the string. + /// + /// \return - The index of the last occurrence of \arg Str, or npos if not + /// found. + size_t rfind(StringRef Str) const { + return str().rfind(Str); + } + + /// find_first_of - Find the first character in the string that is \arg C, + /// or npos if not found. Same as find. + size_t find_first_of(char C, size_t From = 0) const { + return str().find_first_of(C, From); + } + + /// find_first_of - Find the first character in the string that is in \arg + /// Chars, or npos if not found. + /// + /// Note: O(size() + Chars.size()) + size_t find_first_of(StringRef Chars, size_t From = 0) const { + return str().find_first_of(Chars, From); + } + + /// find_first_not_of - Find the first character in the string that is not + /// \arg C or npos if not found. + size_t find_first_not_of(char C, size_t From = 0) const { + return str().find_first_not_of(C, From); + } + + /// find_first_not_of - Find the first character in the string that is not + /// in the string \arg Chars, or npos if not found. + /// + /// Note: O(size() + Chars.size()) + size_t find_first_not_of(StringRef Chars, size_t From = 0) const { + return str().find_first_not_of(Chars, From); + } + + /// find_last_of - Find the last character in the string that is \arg C, or + /// npos if not found. + size_t find_last_of(char C, size_t From = StringRef::npos) const { + return str().find_last_of(C, From); + } + + /// find_last_of - Find the last character in the string that is in \arg C, + /// or npos if not found. + /// + /// Note: O(size() + Chars.size()) + size_t find_last_of( + StringRef Chars, size_t From = StringRef::npos) const { + return str().find_last_of(Chars, From); + } + + /// @} + /// @name Helpful Algorithms + /// @{ + + /// count - Return the number of occurrences of \arg C in the string. + size_t count(char C) const { + return str().count(C); + } + + /// count - Return the number of non-overlapped occurrences of \arg Str in + /// the string. + size_t count(StringRef Str) const { + return str().count(Str); + } + + /// @} + /// @name Substring Operations + /// @{ + + /// substr - Return a reference to the substring from [Start, Start + N). + /// + /// \param Start - The index of the starting character in the substring; if + /// the index is npos or greater than the length of the string then the + /// empty substring will be returned. + /// + /// \param N - The number of characters to included in the substring. If N + /// exceeds the number of characters remaining in the string, the string + /// suffix (starting with \arg Start) will be returned. + StringRef substr(size_t Start, size_t N = StringRef::npos) const { + return str().substr(Start, N); + } + + /// slice - Return a reference to the substring from [Start, End). + /// + /// \param Start - The index of the starting character in the substring; if + /// the index is npos or greater than the length of the string then the + /// 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 \arg Start, or exceeds the + /// number of characters remaining in the string, the string suffix + /// (starting with \arg Start) will be returned. + StringRef slice(size_t Start, size_t End) const { + return str().slice(Start, End); + } // Extra methods. + + /// Explicit conversion to StringRef StringRef str() const { return StringRef(this->begin(), this->size()); } // TODO: Make this const, if it's safe... @@ -48,7 +271,7 @@ public: return this->data(); } - // Implicit conversion to StringRef. + /// Implicit conversion to StringRef. operator StringRef() const { return str(); } // Extra operators. diff --git a/include/llvm/ADT/SmallVector.h b/include/llvm/ADT/SmallVector.h index 1c42f29..0d9d0d1 100644 --- a/include/llvm/ADT/SmallVector.h +++ b/include/llvm/ADT/SmallVector.h @@ -23,30 +23,6 @@ #include <iterator> #include <memory> -#ifdef _MSC_VER -namespace std { -#if _MSC_VER <= 1310 - // Work around flawed VC++ implementation of std::uninitialized_copy. Define - // additional overloads so that elements with pointer types are recognized as - // scalars and not objects, causing bizarre type conversion errors. - template<class T1, class T2> - inline _Scalar_ptr_iterator_tag _Ptr_cat(T1 **, T2 **) { - _Scalar_ptr_iterator_tag _Cat; - return _Cat; - } - - template<class T1, class T2> - inline _Scalar_ptr_iterator_tag _Ptr_cat(T1* const *, T2 **) { - _Scalar_ptr_iterator_tag _Cat; - return _Cat; - } -#else -// FIXME: It is not clear if the problem is fixed in VS 2005. What is clear -// is that the above hack won't work if it wasn't fixed. -#endif -} -#endif - namespace llvm { /// SmallVectorBase - This is all the non-templated stuff common to all @@ -100,10 +76,10 @@ public: template <typename T> class SmallVectorTemplateCommon : public SmallVectorBase { protected: - void setEnd(T *P) { this->EndX = P; } -public: SmallVectorTemplateCommon(size_t Size) : SmallVectorBase(Size) {} + void setEnd(T *P) { this->EndX = P; } +public: typedef size_t size_type; typedef ptrdiff_t difference_type; typedef T value_type; @@ -174,7 +150,7 @@ public: /// implementations that are designed to work with non-POD-like T's. template <typename T, bool isPodLike> class SmallVectorTemplateBase : public SmallVectorTemplateCommon<T> { -public: +protected: SmallVectorTemplateBase(size_t Size) : SmallVectorTemplateCommon<T>(Size) {} static void destroy_range(T *S, T *E) { @@ -194,6 +170,23 @@ public: /// grow - double the size of the allocated memory, guaranteeing space for at /// least one more element or MinSize if specified. void grow(size_t MinSize = 0); + +public: + void push_back(const T &Elt) { + if (this->EndX < this->CapacityX) { + Retry: + new (this->end()) T(Elt); + this->setEnd(this->end()+1); + return; + } + this->grow(); + goto Retry; + } + + void pop_back() { + this->setEnd(this->end()-1); + this->end()->~T(); + } }; // Define this out-of-line to dissuade the C++ compiler from inlining it. @@ -226,7 +219,7 @@ void SmallVectorTemplateBase<T, isPodLike>::grow(size_t MinSize) { /// implementations that are designed to work with POD-like T's. template <typename T> class SmallVectorTemplateBase<T, true> : public SmallVectorTemplateCommon<T> { -public: +protected: SmallVectorTemplateBase(size_t Size) : SmallVectorTemplateCommon<T>(Size) {} // No need to do a destroy loop for POD's. @@ -255,6 +248,21 @@ public: void grow(size_t MinSize = 0) { this->grow_pod(MinSize*sizeof(T), sizeof(T)); } +public: + void push_back(const T &Elt) { + if (this->EndX < this->CapacityX) { + Retry: + *this->end() = Elt; + this->setEnd(this->end()+1); + return; + } + this->grow(); + goto Retry; + } + + void pop_back() { + this->setEnd(this->end()-1); + } }; @@ -270,11 +278,13 @@ public: typedef typename SuperClass::iterator iterator; typedef typename SuperClass::size_type size_type; +protected: // Default ctor - Initialize to empty. explicit SmallVectorImpl(unsigned N) : SmallVectorTemplateBase<T, isPodLike<T>::value>(N*sizeof(T)) { } +public: ~SmallVectorImpl() { // Destroy the constructed elements in the vector. this->destroy_range(this->begin(), this->end()); @@ -297,7 +307,7 @@ public: } else if (N > this->size()) { if (this->capacity() < N) this->grow(N); - this->construct_range(this->end(), this->begin()+N, T()); + std::uninitialized_fill(this->end(), this->begin()+N, T()); this->setEnd(this->begin()+N); } } @@ -309,7 +319,7 @@ public: } else if (N > this->size()) { if (this->capacity() < N) this->grow(N); - construct_range(this->end(), this->begin()+N, NV); + std::uninitialized_fill(this->end(), this->begin()+N, NV); this->setEnd(this->begin()+N); } } @@ -319,25 +329,9 @@ public: this->grow(N); } - void push_back(const T &Elt) { - if (this->EndX < this->CapacityX) { - Retry: - new (this->end()) T(Elt); - this->setEnd(this->end()+1); - return; - } - this->grow(); - goto Retry; - } - - void pop_back() { - this->setEnd(this->end()-1); - this->end()->~T(); - } - T pop_back_val() { T Result = this->back(); - pop_back(); + this->pop_back(); return Result; } @@ -376,7 +370,7 @@ public: if (this->capacity() < NumElts) this->grow(NumElts); this->setEnd(this->begin()+NumElts); - construct_range(this->begin(), this->end(), Elt); + std::uninitialized_fill(this->begin(), this->end(), Elt); } iterator erase(iterator I) { @@ -384,7 +378,7 @@ public: // Shift all elts down one. std::copy(I+1, this->end(), I); // Drop the last elt. - pop_back(); + this->pop_back(); return(N); } @@ -400,7 +394,7 @@ public: iterator insert(iterator I, const T &Elt) { if (I == this->end()) { // Important special case for empty vector. - push_back(Elt); + this->push_back(Elt); return this->end()-1; } @@ -554,12 +548,6 @@ public: assert(N <= this->capacity()); this->setEnd(this->begin() + N); } - -private: - static void construct_range(T *S, T *E, const T &Elt) { - for (; S != E; ++S) - new (S) T(Elt); - } }; @@ -686,9 +674,7 @@ public: explicit SmallVector(unsigned Size, const T &Value = T()) : SmallVectorImpl<T>(NumTsAvailable) { - this->reserve(Size); - while (Size--) - this->push_back(Value); + this->assign(Size, Value); } template<typename ItTy> @@ -718,9 +704,7 @@ public: explicit SmallVector(unsigned Size, const T &Value = T()) : SmallVectorImpl<T>(0) { - this->reserve(Size); - while (Size--) - this->push_back(Value); + this->assign(Size, Value); } template<typename ItTy> diff --git a/include/llvm/ADT/SparseBitVector.h b/include/llvm/ADT/SparseBitVector.h index d977136..89774c3 100644 --- a/include/llvm/ADT/SparseBitVector.h +++ b/include/llvm/ADT/SparseBitVector.h @@ -18,11 +18,11 @@ #include "llvm/ADT/ilist.h" #include "llvm/ADT/ilist_node.h" #include "llvm/Support/DataTypes.h" +#include "llvm/Support/ErrorHandling.h" #include "llvm/Support/MathExtras.h" #include "llvm/Support/raw_ostream.h" #include <cassert> #include <climits> -#include <cstring> namespace llvm { @@ -128,7 +128,7 @@ public: else if (sizeof(BitWord) == 8) NumBits += CountPopulation_64(Bits[i]); else - assert(0 && "Unsupported!"); + llvm_unreachable("Unsupported!"); return NumBits; } @@ -138,13 +138,11 @@ public: if (Bits[i] != 0) { if (sizeof(BitWord) == 4) return i * BITWORD_SIZE + CountTrailingZeros_32(Bits[i]); - else if (sizeof(BitWord) == 8) + if (sizeof(BitWord) == 8) return i * BITWORD_SIZE + CountTrailingZeros_64(Bits[i]); - else - assert(0 && "Unsupported!"); + llvm_unreachable("Unsupported!"); } - assert(0 && "Illegal empty element"); - return 0; // Not reached + llvm_unreachable("Illegal empty element"); } /// find_next - Returns the index of the next set bit starting from the @@ -165,10 +163,9 @@ public: if (Copy != 0) { if (sizeof(BitWord) == 4) return WordPos * BITWORD_SIZE + CountTrailingZeros_32(Copy); - else if (sizeof(BitWord) == 8) + if (sizeof(BitWord) == 8) return WordPos * BITWORD_SIZE + CountTrailingZeros_64(Copy); - else - assert(0 && "Unsupported!"); + llvm_unreachable("Unsupported!"); } // Check subsequent words. @@ -176,10 +173,9 @@ public: if (Bits[i] != 0) { if (sizeof(BitWord) == 4) return i * BITWORD_SIZE + CountTrailingZeros_32(Bits[i]); - else if (sizeof(BitWord) == 8) + if (sizeof(BitWord) == 8) return i * BITWORD_SIZE + CountTrailingZeros_64(Bits[i]); - else - assert(0 && "Unsupported!"); + llvm_unreachable("Unsupported!"); } return -1; } @@ -264,15 +260,6 @@ public: } BecameZero = allzero; } - - // Get a hash value for this element; - uint64_t getHashValue() const { - uint64_t HashVal = 0; - for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i) { - HashVal ^= Bits[i]; - } - return HashVal; - } }; template <unsigned ElementSize = 128> @@ -813,18 +800,6 @@ public: iterator end() const { return iterator(this, true); } - - // Get a hash value for this bitmap. - uint64_t getHashValue() const { - uint64_t HashVal = 0; - for (ElementListConstIter Iter = Elements.begin(); - Iter != Elements.end(); - ++Iter) { - HashVal ^= Iter->index(); - HashVal ^= Iter->getHashValue(); - } - return HashVal; - } }; // Convenience functions to allow Or and And without dereferencing in the user diff --git a/include/llvm/ADT/SparseSet.h b/include/llvm/ADT/SparseSet.h new file mode 100644 index 0000000..923c6a5 --- /dev/null +++ b/include/llvm/ADT/SparseSet.h @@ -0,0 +1,268 @@ +//===--- llvm/ADT/SparseSet.h - Sparse set ----------------------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file defines the SparseSet class derived from the version described in +// Briggs, Torczon, "An efficient representation for sparse sets", ACM Letters +// on Programming Languages and Systems, Volume 2 Issue 1-4, March-Dec. 1993. +// +// A sparse set holds a small number of objects identified by integer keys from +// a moderately sized universe. The sparse set uses more memory than other +// containers in order to provide faster operations. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_ADT_SPARSESET_H +#define LLVM_ADT_SPARSESET_H + +#include "llvm/ADT/SmallVector.h" +#include "llvm/Support/DataTypes.h" +#include <limits> + +namespace llvm { + +/// SparseSetFunctor - Objects in a SparseSet are identified by small integer +/// keys. A functor object is used to compute the key of an object. The +/// functor's operator() must return an unsigned smaller than the universe. +/// +/// The default functor implementation forwards to a getSparseSetKey() method +/// on the object. It is intended for sparse sets holding ad-hoc structs. +/// +template<typename ValueT> +struct SparseSetFunctor { + unsigned operator()(const ValueT &Val) { + return Val.getSparseSetKey(); + } +}; + +/// SparseSetFunctor<unsigned> - Provide a trivial identity functor for +/// SparseSet<unsigned>. +/// +template<> struct SparseSetFunctor<unsigned> { + unsigned operator()(unsigned Val) { return Val; } +}; + +/// SparseSet - Fast set implementation for objects that can be identified by +/// small unsigned keys. +/// +/// SparseSet allocates memory proportional to the size of the key universe, so +/// it is not recommended for building composite data structures. It is useful +/// for algorithms that require a single set with fast operations. +/// +/// Compared to DenseSet and DenseMap, SparseSet provides constant-time fast +/// clear() and iteration as fast as a vector. The find(), insert(), and +/// erase() operations are all constant time, and typically faster than a hash +/// table. The iteration order doesn't depend on numerical key values, it only +/// depends on the order of insert() and erase() operations. When no elements +/// have been erased, the iteration order is the insertion order. +/// +/// Compared to BitVector, SparseSet<unsigned> uses 8x-40x more memory, but +/// offers constant-time clear() and size() operations as well as fast +/// iteration independent on the size of the universe. +/// +/// SparseSet contains a dense vector holding all the objects and a sparse +/// array holding indexes into the dense vector. Most of the memory is used by +/// the sparse array which is the size of the key universe. The SparseT +/// template parameter provides a space/speed tradeoff for sets holding many +/// elements. +/// +/// When SparseT is uint32_t, find() only touches 2 cache lines, but the sparse +/// array uses 4 x Universe bytes. +/// +/// When SparseT is uint8_t (the default), find() touches up to 2+[N/256] cache +/// lines, but the sparse array is 4x smaller. N is the number of elements in +/// the set. +/// +/// For sets that may grow to thousands of elements, SparseT should be set to +/// uint16_t or uint32_t. +/// +/// @param ValueT The type of objects in the set. +/// @param SparseT An unsigned integer type. See above. +/// @param KeyFunctorT A functor that computes the unsigned key of a ValueT. +/// +template<typename ValueT, + typename SparseT = uint8_t, + typename KeyFunctorT = SparseSetFunctor<ValueT> > +class SparseSet { + typedef SmallVector<ValueT, 8> DenseT; + DenseT Dense; + SparseT *Sparse; + unsigned Universe; + KeyFunctorT KeyOf; + + // Disable copy construction and assignment. + // This data structure is not meant to be used that way. + SparseSet(const SparseSet&); // DO NOT IMPLEMENT. + SparseSet &operator=(const SparseSet&); // DO NOT IMPLEMENT. + +public: + typedef ValueT value_type; + typedef ValueT &reference; + typedef const ValueT &const_reference; + typedef ValueT *pointer; + typedef const ValueT *const_pointer; + + SparseSet() : Sparse(0), Universe(0) {} + ~SparseSet() { free(Sparse); } + + /// setUniverse - Set the universe size which determines the largest key the + /// set can hold. The universe must be sized before any elements can be + /// added. + /// + /// @param U Universe size. All object keys must be less than U. + /// + void setUniverse(unsigned U) { + // It's not hard to resize the universe on a non-empty set, but it doesn't + // seem like a likely use case, so we can add that code when we need it. + assert(empty() && "Can only resize universe on an empty map"); + // Hysteresis prevents needless reallocations. + if (U >= Universe/4 && U <= Universe) + return; + free(Sparse); + // The Sparse array doesn't actually need to be initialized, so malloc + // would be enough here, but that will cause tools like valgrind to + // complain about branching on uninitialized data. + Sparse = reinterpret_cast<SparseT*>(calloc(U, sizeof(SparseT))); + Universe = U; + } + + // Import trivial vector stuff from DenseT. + typedef typename DenseT::iterator iterator; + typedef typename DenseT::const_iterator const_iterator; + + const_iterator begin() const { return Dense.begin(); } + const_iterator end() const { return Dense.end(); } + iterator begin() { return Dense.begin(); } + iterator end() { return Dense.end(); } + + /// empty - Returns true if the set is empty. + /// + /// This is not the same as BitVector::empty(). + /// + bool empty() const { return Dense.empty(); } + + /// size - Returns the number of elements in the set. + /// + /// This is not the same as BitVector::size() which returns the size of the + /// universe. + /// + unsigned size() const { return Dense.size(); } + + /// clear - Clears the set. This is a very fast constant time operation. + /// + void clear() { + // Sparse does not need to be cleared, see find(). + Dense.clear(); + } + + /// find - Find an element by its key. + /// + /// @param Key A valid key to find. + /// @returns An iterator to the element identified by key, or end(). + /// + iterator find(unsigned Key) { + assert(Key < Universe && "Key out of range"); + assert(std::numeric_limits<SparseT>::is_integer && + !std::numeric_limits<SparseT>::is_signed && + "SparseT must be an unsigned integer type"); + const unsigned Stride = std::numeric_limits<SparseT>::max() + 1u; + for (unsigned i = Sparse[Key], e = size(); i < e; i += Stride) { + const unsigned FoundKey = KeyOf(Dense[i]); + assert(FoundKey < Universe && "Invalid key in set. Did object mutate?"); + if (Key == FoundKey) + return begin() + i; + // Stride is 0 when SparseT >= unsigned. We don't need to loop. + if (!Stride) + break; + } + return end(); + } + + const_iterator find(unsigned Key) const { + return const_cast<SparseSet*>(this)->find(Key); + } + + /// count - Returns true if this set contains an element identified by Key. + /// + bool count(unsigned Key) const { + return find(Key) != end(); + } + + /// insert - Attempts to insert a new element. + /// + /// If Val is successfully inserted, return (I, true), where I is an iterator + /// pointing to the newly inserted element. + /// + /// If the set already contains an element with the same key as Val, return + /// (I, false), where I is an iterator pointing to the existing element. + /// + /// Insertion invalidates all iterators. + /// + std::pair<iterator, bool> insert(const ValueT &Val) { + unsigned Key = KeyOf(Val); + iterator I = find(Key); + if (I != end()) + return std::make_pair(I, false); + Sparse[Key] = size(); + Dense.push_back(Val); + return std::make_pair(end() - 1, true); + } + + /// array subscript - If an element already exists with this key, return it. + /// Otherwise, automatically construct a new value from Key, insert it, + /// and return the newly inserted element. + ValueT &operator[](unsigned Key) { + return *insert(ValueT(Key)).first; + } + + /// erase - Erases an existing element identified by a valid iterator. + /// + /// This invalidates all iterators, but erase() returns an iterator pointing + /// to the next element. This makes it possible to erase selected elements + /// while iterating over the set: + /// + /// for (SparseSet::iterator I = Set.begin(); I != Set.end();) + /// if (test(*I)) + /// I = Set.erase(I); + /// else + /// ++I; + /// + /// Note that end() changes when elements are erased, unlike std::list. + /// + iterator erase(iterator I) { + assert(unsigned(I - begin()) < size() && "Invalid iterator"); + if (I != end() - 1) { + *I = Dense.back(); + unsigned BackKey = KeyOf(Dense.back()); + assert(BackKey < Universe && "Invalid key in set. Did object mutate?"); + Sparse[BackKey] = I - begin(); + } + // This depends on SmallVector::pop_back() not invalidating iterators. + // std::vector::pop_back() doesn't give that guarantee. + Dense.pop_back(); + return I; + } + + /// erase - Erases an element identified by Key, if it exists. + /// + /// @param Key The key identifying the element to erase. + /// @returns True when an element was erased, false if no element was found. + /// + bool erase(unsigned Key) { + iterator I = find(Key); + if (I == end()) + return false; + erase(I); + return true; + } + +}; + +} // end namespace llvm + +#endif diff --git a/include/llvm/ADT/Statistic.h b/include/llvm/ADT/Statistic.h index b8a1a2f..b54d10b 100644 --- a/include/llvm/ADT/Statistic.h +++ b/include/llvm/ADT/Statistic.h @@ -27,6 +27,7 @@ #define LLVM_ADT_STATISTIC_H #include "llvm/Support/Atomic.h" +#include "llvm/Support/Valgrind.h" namespace llvm { class raw_ostream; @@ -110,6 +111,7 @@ protected: bool tmp = Initialized; sys::MemoryFence(); if (!tmp) RegisterStatistic(); + TsanHappensAfter(this); return *this; } void RegisterStatistic(); diff --git a/include/llvm/ADT/StringExtras.h b/include/llvm/ADT/StringExtras.h index d01d3e1..655d884 100644 --- a/include/llvm/ADT/StringExtras.h +++ b/include/llvm/ADT/StringExtras.h @@ -15,12 +15,7 @@ #define LLVM_ADT_STRINGEXTRAS_H #include "llvm/Support/DataTypes.h" -#include "llvm/ADT/APFloat.h" -#include "llvm/ADT/DenseMapInfo.h" #include "llvm/ADT/StringRef.h" -#include <cctype> -#include <cstdio> -#include <string> namespace llvm { template<typename T> class SmallVectorImpl; @@ -101,38 +96,6 @@ static inline std::string itostr(int64_t X) { return utostr(static_cast<uint64_t>(X)); } -static inline std::string ftostr(double V) { - char Buffer[200]; - sprintf(Buffer, "%20.6e", V); - char *B = Buffer; - while (*B == ' ') ++B; - return B; -} - -static inline std::string ftostr(const APFloat& V) { - if (&V.getSemantics() == &APFloat::IEEEdouble) - return ftostr(V.convertToDouble()); - else if (&V.getSemantics() == &APFloat::IEEEsingle) - return ftostr((double)V.convertToFloat()); - return "<unknown format in ftostr>"; // error -} - -static inline std::string LowercaseString(const std::string &S) { - std::string result(S); - for (unsigned i = 0; i < S.length(); ++i) - if (isupper(result[i])) - result[i] = char(tolower(result[i])); - return result; -} - -static inline std::string UppercaseString(const std::string &S) { - std::string result(S); - for (unsigned i = 0; i < S.length(); ++i) - if (islower(result[i])) - result[i] = char(toupper(result[i])); - return result; -} - /// StrInStrNoCase - Portable version of strcasestr. Locates the first /// occurrence of string 's1' in string 's2', ignoring case. Returns /// the offset of s2 in s1 or npos if s2 cannot be found. diff --git a/include/llvm/ADT/StringMap.h b/include/llvm/ADT/StringMap.h index 3507787..097418e 100644 --- a/include/llvm/ADT/StringMap.h +++ b/include/llvm/ADT/StringMap.h @@ -51,20 +51,11 @@ public: /// StringMapImpl - This is the base class of StringMap that is shared among /// all of its instantiations. class StringMapImpl { -public: - /// ItemBucket - The hash table consists of an array of these. If Item is - /// non-null, this is an extant entry, otherwise, it is a hole. - struct ItemBucket { - /// FullHashValue - This remembers the full hash value of the key for - /// easy scanning. - unsigned FullHashValue; - - /// Item - This is a pointer to the actual item object. - StringMapEntryBase *Item; - }; - protected: - ItemBucket *TheTable; + // Array of NumBuckets pointers to entries, null pointers are holes. + // TheTable[NumBuckets] contains a sentinel value for easy iteration. Follwed + // by an array of the actual hash values as unsigned integers. + StringMapEntryBase **TheTable; unsigned NumBuckets; unsigned NumItems; unsigned NumTombstones; @@ -238,8 +229,9 @@ public: template<typename ValueTy, typename AllocatorTy = MallocAllocator> class StringMap : public StringMapImpl { AllocatorTy Allocator; - typedef StringMapEntry<ValueTy> MapEntryTy; public: + typedef StringMapEntry<ValueTy> MapEntryTy; + StringMap() : StringMapImpl(static_cast<unsigned>(sizeof(MapEntryTy))) {} explicit StringMap(unsigned InitialSize) : StringMapImpl(InitialSize, static_cast<unsigned>(sizeof(MapEntryTy))) {} @@ -289,13 +281,13 @@ public: iterator find(StringRef Key) { int Bucket = FindKey(Key); if (Bucket == -1) return end(); - return iterator(TheTable+Bucket); + return iterator(TheTable+Bucket, true); } const_iterator find(StringRef Key) const { int Bucket = FindKey(Key); if (Bucket == -1) return end(); - return const_iterator(TheTable+Bucket); + return const_iterator(TheTable+Bucket, true); } /// lookup - Return the entry for the specified key, or a default @@ -320,13 +312,13 @@ public: /// insert it and return true. bool insert(MapEntryTy *KeyValue) { unsigned BucketNo = LookupBucketFor(KeyValue->getKey()); - ItemBucket &Bucket = TheTable[BucketNo]; - if (Bucket.Item && Bucket.Item != getTombstoneVal()) + StringMapEntryBase *&Bucket = TheTable[BucketNo]; + if (Bucket && Bucket != getTombstoneVal()) return false; // Already exists in map. - if (Bucket.Item == getTombstoneVal()) + if (Bucket == getTombstoneVal()) --NumTombstones; - Bucket.Item = KeyValue; + Bucket = KeyValue; ++NumItems; assert(NumItems + NumTombstones <= NumBuckets); @@ -340,10 +332,11 @@ public: // Zap all values, resetting the keys back to non-present (not tombstone), // which is safe because we're removing all elements. - for (ItemBucket *I = TheTable, *E = TheTable+NumBuckets; I != E; ++I) { - if (I->Item && I->Item != getTombstoneVal()) { - static_cast<MapEntryTy*>(I->Item)->Destroy(Allocator); - I->Item = 0; + for (unsigned I = 0, E = NumBuckets; I != E; ++I) { + StringMapEntryBase *&Bucket = TheTable[I]; + if (Bucket && Bucket != getTombstoneVal()) { + static_cast<MapEntryTy*>(Bucket)->Destroy(Allocator); + Bucket = 0; } } @@ -357,21 +350,21 @@ public: template <typename InitTy> MapEntryTy &GetOrCreateValue(StringRef Key, InitTy Val) { unsigned BucketNo = LookupBucketFor(Key); - ItemBucket &Bucket = TheTable[BucketNo]; - if (Bucket.Item && Bucket.Item != getTombstoneVal()) - return *static_cast<MapEntryTy*>(Bucket.Item); + StringMapEntryBase *&Bucket = TheTable[BucketNo]; + if (Bucket && Bucket != getTombstoneVal()) + return *static_cast<MapEntryTy*>(Bucket); MapEntryTy *NewItem = MapEntryTy::Create(Key.begin(), Key.end(), Allocator, Val); - if (Bucket.Item == getTombstoneVal()) + if (Bucket == getTombstoneVal()) --NumTombstones; ++NumItems; assert(NumItems + NumTombstones <= NumBuckets); // Fill in the bucket for the hash table. The FullHashValue was already // filled in by LookupBucketFor. - Bucket.Item = NewItem; + Bucket = NewItem; RehashTable(); return *NewItem; @@ -410,21 +403,21 @@ public: template<typename ValueTy> class StringMapConstIterator { protected: - StringMapImpl::ItemBucket *Ptr; + StringMapEntryBase **Ptr; public: typedef StringMapEntry<ValueTy> value_type; - explicit StringMapConstIterator(StringMapImpl::ItemBucket *Bucket, + explicit StringMapConstIterator(StringMapEntryBase **Bucket, bool NoAdvance = false) : Ptr(Bucket) { if (!NoAdvance) AdvancePastEmptyBuckets(); } const value_type &operator*() const { - return *static_cast<StringMapEntry<ValueTy>*>(Ptr->Item); + return *static_cast<StringMapEntry<ValueTy>*>(*Ptr); } const value_type *operator->() const { - return static_cast<StringMapEntry<ValueTy>*>(Ptr->Item); + return static_cast<StringMapEntry<ValueTy>*>(*Ptr); } bool operator==(const StringMapConstIterator &RHS) const { @@ -445,7 +438,7 @@ public: private: void AdvancePastEmptyBuckets() { - while (Ptr->Item == 0 || Ptr->Item == StringMapImpl::getTombstoneVal()) + while (*Ptr == 0 || *Ptr == StringMapImpl::getTombstoneVal()) ++Ptr; } }; @@ -453,15 +446,15 @@ private: template<typename ValueTy> class StringMapIterator : public StringMapConstIterator<ValueTy> { public: - explicit StringMapIterator(StringMapImpl::ItemBucket *Bucket, + explicit StringMapIterator(StringMapEntryBase **Bucket, bool NoAdvance = false) : StringMapConstIterator<ValueTy>(Bucket, NoAdvance) { } StringMapEntry<ValueTy> &operator*() const { - return *static_cast<StringMapEntry<ValueTy>*>(this->Ptr->Item); + return *static_cast<StringMapEntry<ValueTy>*>(*this->Ptr); } StringMapEntry<ValueTy> *operator->() const { - return static_cast<StringMapEntry<ValueTy>*>(this->Ptr->Item); + return static_cast<StringMapEntry<ValueTy>*>(*this->Ptr); } }; diff --git a/include/llvm/ADT/StringRef.h b/include/llvm/ADT/StringRef.h index 8396921..76ba66e 100644 --- a/include/llvm/ADT/StringRef.h +++ b/include/llvm/ADT/StringRef.h @@ -10,15 +10,26 @@ #ifndef LLVM_ADT_STRINGREF_H #define LLVM_ADT_STRINGREF_H +#include "llvm/Support/type_traits.h" + #include <cassert> #include <cstring> -#include <utility> +#include <limits> #include <string> +#include <utility> namespace llvm { template<typename T> class SmallVectorImpl; class APInt; + class hash_code; + class StringRef; + + /// Helper functions for StringRef::getAsInteger. + bool getAsUnsignedInteger(StringRef Str, unsigned Radix, + unsigned long long &Result); + + bool getAsSignedInteger(StringRef Str, unsigned Radix, long long &Result); /// StringRef - Represent a constant reference to a string, i.e. a character /// array and a length, which need not be null terminated. @@ -304,14 +315,29 @@ namespace llvm { /// /// If the string is invalid or if only a subset of the string is valid, /// this returns true to signify the error. The string is considered - /// erroneous if empty. + /// erroneous if empty or if it overflows T. /// - bool getAsInteger(unsigned Radix, long long &Result) const; - bool getAsInteger(unsigned Radix, unsigned long long &Result) const; - bool getAsInteger(unsigned Radix, int &Result) const; - bool getAsInteger(unsigned Radix, unsigned &Result) const; + template <typename T> + typename enable_if_c<std::numeric_limits<T>::is_signed, bool>::type + getAsInteger(unsigned Radix, T &Result) const { + long long LLVal; + if (getAsSignedInteger(*this, Radix, LLVal) || + static_cast<T>(LLVal) != LLVal) + return true; + Result = LLVal; + return false; + } - // TODO: Provide overloads for int/unsigned that check for overflow. + template <typename T> + typename enable_if_c<!std::numeric_limits<T>::is_signed, bool>::type + getAsInteger(unsigned Radix, T &Result) const { + unsigned long long ULLVal; + if (getAsUnsignedInteger(*this, Radix, ULLVal) || + static_cast<T>(ULLVal) != ULLVal) + return true; + Result = ULLVal; + return false; + } /// getAsInteger - Parse the current string as an integer of the /// specified radix, or of an autosensed radix if the radix given @@ -327,6 +353,16 @@ namespace llvm { bool getAsInteger(unsigned Radix, APInt &Result) const; /// @} + /// @name String Operations + /// @{ + + // lower - Convert the given ASCII string to lowercase. + std::string lower() const; + + /// upper - Convert the given ASCII string to uppercase. + std::string upper() const; + + /// @} /// @name Substring Operations /// @{ @@ -343,6 +379,20 @@ namespace llvm { Start = min(Start, Length); return StringRef(Data + Start, min(N, Length - Start)); } + + /// drop_front - Return a StringRef equal to 'this' but with the first + /// elements dropped. + StringRef drop_front(unsigned N = 1) const { + assert(size() >= N && "Dropping more elements than exist"); + return substr(N); + } + + /// drop_back - Return a StringRef equal to 'this' but with the last + /// elements dropped. + StringRef drop_back(unsigned N = 1) const { + assert(size() >= N && "Dropping more elements than exist"); + return substr(0, size()-N); + } /// slice - Return a reference to the substring from [Start, End). /// @@ -466,6 +516,9 @@ namespace llvm { /// @} + /// \brief Compute a hash_code for a StringRef. + hash_code hash_value(StringRef S); + // StringRefs can be treated like a POD type. template <typename T> struct isPodLike; template <> struct isPodLike<StringRef> { static const bool value = true; }; diff --git a/include/llvm/ADT/TinyPtrVector.h b/include/llvm/ADT/TinyPtrVector.h index ee86d8b..5014517 100644 --- a/include/llvm/ADT/TinyPtrVector.h +++ b/include/llvm/ADT/TinyPtrVector.h @@ -37,6 +37,15 @@ public: delete V; } + // implicit conversion operator to ArrayRef. + operator ArrayRef<EltTy>() const { + if (Val.isNull()) + return ArrayRef<EltTy>(); + if (Val.template is<EltTy>()) + return *Val.getAddrOfPtr1(); + return *Val.template get<VecTy*>(); + } + bool empty() const { // This vector can be empty if it contains no element, or if it // contains a pointer to an empty vector. @@ -54,18 +63,20 @@ public: return Val.template get<VecTy*>()->size(); } - typedef const EltTy *iterator; - iterator begin() const { + typedef const EltTy *const_iterator; + typedef EltTy *iterator; + + iterator begin() { if (empty()) return 0; if (Val.template is<EltTy>()) - return Val.template getAddrOf<EltTy>(); + return Val.getAddrOfPtr1(); return Val.template get<VecTy *>()->begin(); } - iterator end() const { + iterator end() { if (empty()) return 0; @@ -75,7 +86,14 @@ public: return Val.template get<VecTy *>()->end(); } - + const_iterator begin() const { + return (const_iterator)const_cast<TinyPtrVector*>(this)->begin(); + } + + const_iterator end() const { + return (const_iterator)const_cast<TinyPtrVector*>(this)->end(); + } + EltTy operator[](unsigned i) const { assert(!Val.isNull() && "can't index into an empty vector"); if (EltTy V = Val.template dyn_cast<EltTy>()) { @@ -124,6 +142,20 @@ public: } // Otherwise, we're already empty. } + + iterator erase(iterator I) { + // If we have a single value, convert to empty. + if (Val.template is<EltTy>()) { + if (I == begin()) + Val = (EltTy)0; + } else if (VecTy *Vec = Val.template dyn_cast<VecTy*>()) { + // multiple items in a vector; just do the erase, there is no + // benefit to collapsing back to a pointer + return Vec->erase(I); + } + + return 0; + } private: void operator=(const TinyPtrVector&); // NOT IMPLEMENTED YET. diff --git a/include/llvm/ADT/Trie.h b/include/llvm/ADT/Trie.h index 6b150c8f..845af01 100644 --- a/include/llvm/ADT/Trie.h +++ b/include/llvm/ADT/Trie.h @@ -220,8 +220,7 @@ bool Trie<Payload>::addString(const std::string& s, const Payload& data) { assert(0 && "FIXME!"); return false; case Node::DontMatch: - assert(0 && "Impossible!"); - return false; + llvm_unreachable("Impossible!"); case Node::LabelIsPrefix: s1 = s1.substr(nNode->label().length()); cNode = nNode; @@ -258,8 +257,7 @@ const Payload& Trie<Payload>::lookup(const std::string& s) const { case Node::StringIsPrefix: return Empty; case Node::DontMatch: - assert(0 && "Impossible!"); - return Empty; + llvm_unreachable("Impossible!"); case Node::LabelIsPrefix: s1 = s1.substr(nNode->label().length()); cNode = nNode; diff --git a/include/llvm/ADT/Triple.h b/include/llvm/ADT/Triple.h index 3503c0f..f5f99d0 100644 --- a/include/llvm/ADT/Triple.h +++ b/include/llvm/ADT/Triple.h @@ -43,20 +43,19 @@ public: enum ArchType { UnknownArch, - alpha, // Alpha: alpha arm, // ARM; arm, armv.*, xscale - bfin, // Blackfin: bfin cellspu, // CellSPU: spu, cellspu + hexagon, // Hexagon: hexagon mips, // MIPS: mips, mipsallegrex - mipsel, // MIPSEL: mipsel, mipsallegrexel, psp + mipsel, // MIPSEL: mipsel, mipsallegrexel mips64, // MIPS64: mips64 mips64el,// MIPS64EL: mips64el msp430, // MSP430: msp430 ppc, // PPC: powerpc ppc64, // PPC64: powerpc64, ppu + r600, // R600: AMD GPUs HD2XXX - HD6XXX sparc, // Sparc: sparc sparcv9, // Sparcv9: Sparcv9 - systemz, // SystemZ: s390x tce, // TCE (http://tce.cs.tut.fi/): tce thumb, // Thumb: thumb, thumbv.* x86, // X86: i[3-9]86 @@ -66,16 +65,16 @@ public: ptx32, // PTX: ptx (32-bit) ptx64, // PTX: ptx (64-bit) le32, // le32: generic little-endian 32-bit CPU (PNaCl / Emscripten) - amdil, // amdil: amd IL - - InvalidArch + amdil // amdil: amd IL }; enum VendorType { UnknownVendor, Apple, PC, - SCEI + SCEI, + BGP, + BGQ }; enum OSType { UnknownOS, @@ -93,61 +92,52 @@ public: MinGW32, // i*86-pc-mingw32, *-w64-mingw32 NetBSD, OpenBSD, - Psp, Solaris, Win32, Haiku, Minix, RTEMS, - NativeClient + NativeClient, + CNK // BG/P Compute-Node Kernel }; enum EnvironmentType { UnknownEnvironment, GNU, GNUEABI, + GNUEABIHF, EABI, - MachO + MachO, + ANDROIDEABI }; private: std::string Data; - /// The parsed arch type (or InvalidArch if uninitialized). - mutable ArchType Arch; + /// The parsed arch type. + ArchType Arch; /// The parsed vendor type. - mutable VendorType Vendor; + VendorType Vendor; /// The parsed OS type. - mutable OSType OS; + OSType OS; /// The parsed Environment type. - mutable EnvironmentType Environment; - - bool isInitialized() const { return Arch != InvalidArch; } - static ArchType ParseArch(StringRef ArchName); - static VendorType ParseVendor(StringRef VendorName); - static OSType ParseOS(StringRef OSName); - static EnvironmentType ParseEnvironment(StringRef EnvironmentName); - void Parse() const; + EnvironmentType Environment; public: /// @name Constructors /// @{ - Triple() : Data(), Arch(InvalidArch) {} - explicit Triple(const Twine &Str) : Data(Str.str()), Arch(InvalidArch) {} - Triple(const Twine &ArchStr, const Twine &VendorStr, const Twine &OSStr) - : Data((ArchStr + Twine('-') + VendorStr + Twine('-') + OSStr).str()), - Arch(InvalidArch) { - } + /// \brief Default constructor is the same as an empty string and leaves all + /// triple fields unknown. + Triple() : Data(), Arch(), Vendor(), OS(), Environment() {} + explicit Triple(const Twine &Str); + Triple(const Twine &ArchStr, const Twine &VendorStr, const Twine &OSStr); Triple(const Twine &ArchStr, const Twine &VendorStr, const Twine &OSStr, - const Twine &EnvironmentStr) - : Data((ArchStr + Twine('-') + VendorStr + Twine('-') + OSStr + Twine('-') + - EnvironmentStr).str()), Arch(InvalidArch) { - } + const Twine &EnvironmentStr); /// @} /// @name Normalization @@ -164,22 +154,13 @@ public: /// @{ /// getArch - Get the parsed architecture type of this triple. - ArchType getArch() const { - if (!isInitialized()) Parse(); - return Arch; - } + ArchType getArch() const { return Arch; } /// getVendor - Get the parsed vendor type of this triple. - VendorType getVendor() const { - if (!isInitialized()) Parse(); - return Vendor; - } + VendorType getVendor() const { return Vendor; } /// getOS - Get the parsed operating system type of this triple. - OSType getOS() const { - if (!isInitialized()) Parse(); - return OS; - } + OSType getOS() const { return OS; } /// hasEnvironment - Does this triple have the optional environment /// (fourth) component? @@ -188,11 +169,31 @@ public: } /// getEnvironment - Get the parsed environment type of this triple. - EnvironmentType getEnvironment() const { - if (!isInitialized()) Parse(); - return Environment; + EnvironmentType getEnvironment() const { return Environment; } + + /// getOSVersion - Parse the version number from the OS name component of the + /// triple, if present. + /// + /// For example, "fooos1.2.3" would return (1, 2, 3). + /// + /// If an entry is not defined, it will be returned as 0. + void getOSVersion(unsigned &Major, unsigned &Minor, unsigned &Micro) const; + + /// getOSMajorVersion - Return just the major version number, this is + /// specialized because it is a common query. + unsigned getOSMajorVersion() const { + unsigned Maj, Min, Micro; + getOSVersion(Maj, Min, Micro); + return Maj; } + /// getMacOSXVersion - Parse the version number as with getOSVersion and then + /// translate generic "darwin" versions to the corresponding OS X versions. + /// This may also be called with IOS triples but the OS X version number is + /// just set to a constant 10.4.0 in that case. Returns true if successful. + bool getMacOSXVersion(unsigned &Major, unsigned &Minor, + unsigned &Micro) const; + /// @} /// @name Direct Component Access /// @{ @@ -221,21 +222,28 @@ public: /// if the environment component is present). StringRef getOSAndEnvironmentName() const; - /// getOSVersion - Parse the version number from the OS name component of the - /// triple, if present. + /// @} + /// @name Convenience Predicates + /// @{ + + /// \brief Test whether the architecture is 64-bit /// - /// For example, "fooos1.2.3" would return (1, 2, 3). + /// Note that this tests for 64-bit pointer width, and nothing else. Note + /// that we intentionally expose only three predicates, 64-bit, 32-bit, and + /// 16-bit. The inner details of pointer width for particular architectures + /// is not summed up in the triple, and so only a coarse grained predicate + /// system is provided. + bool isArch64Bit() const; + + /// \brief Test whether the architecture is 32-bit /// - /// If an entry is not defined, it will be returned as 0. - void getOSVersion(unsigned &Major, unsigned &Minor, unsigned &Micro) const; + /// Note that this tests for 32-bit pointer width, and nothing else. + bool isArch32Bit() const; - /// getOSMajorVersion - Return just the major version number, this is - /// specialized because it is a common query. - unsigned getOSMajorVersion() const { - unsigned Maj, Min, Micro; - getOSVersion(Maj, Min, Micro); - return Maj; - } + /// \brief Test whether the architecture is 16-bit + /// + /// Note that this tests for 16-bit pointer width, and nothing else. + bool isArch16Bit() const; /// isOSVersionLT - Helper function for doing comparisons against version /// numbers included in the target triple. @@ -254,6 +262,22 @@ public: return false; } + /// 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 { + assert(isMacOSX() && "Not an OS X triple!"); + + // If this is OS X, expect a sane version number. + if (getOS() == Triple::MacOSX) + return isOSVersionLT(Major, Minor, Micro); + + // Otherwise, compare to the "Darwin" number. + assert(Major == 10 && "Unexpected major version"); + return isOSVersionLT(Minor + 4, Micro, 0); + } + /// isMacOSX - Is this a Mac OS X triple. For legacy reasons, we support both /// "darwin" and "osx" as OS X triples. bool isMacOSX() const { @@ -265,26 +289,30 @@ public: return isMacOSX() || getOS() == Triple::IOS; } + /// \brief Tests for either Cygwin or MinGW OS + bool isOSCygMing() const { + return getOS() == Triple::Cygwin || getOS() == Triple::MinGW32; + } + /// isOSWindows - Is this a "Windows" OS. bool isOSWindows() const { - return getOS() == Triple::Win32 || getOS() == Triple::Cygwin || - getOS() == Triple::MinGW32; + return getOS() == Triple::Win32 || isOSCygMing(); } - /// 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 { - assert(isMacOSX() && "Not an OS X triple!"); + /// \brief Tests whether the OS uses the ELF binary format. + bool isOSBinFormatELF() const { + return !isOSDarwin() && !isOSWindows(); + } - // If this is OS X, expect a sane version number. - if (getOS() == Triple::MacOSX) - return isOSVersionLT(Major, Minor, Micro); + /// \brief Tests whether the OS uses the COFF binary format. + bool isOSBinFormatCOFF() const { + return isOSWindows(); + } - // Otherwise, compare to the "Darwin" number. - assert(Major == 10 && "Unexpected major version"); - return isOSVersionLT(Minor + 4, Micro, 0); + /// \brief Tests whether the environment is MachO. + // FIXME: Should this be an OSBinFormat predicate? + bool isEnvironmentMachO() const { + return getEnvironment() == Triple::MachO || isOSDarwin(); } /// @} @@ -335,6 +363,26 @@ public: const char *getArchNameForAssembler(); /// @} + /// @name Helpers to build variants of a particular triple. + /// @{ + + /// \brief Form a triple with a 32-bit variant of the current architecture. + /// + /// This can be used to move across "families" of architectures where useful. + /// + /// \returns A new triple with a 32-bit architecture or an unknown + /// architecture if no such variant can be found. + llvm::Triple get32BitArchVariant() const; + + /// \brief Form a triple with a 64-bit variant of the current architecture. + /// + /// This can be used to move across "families" of architectures where useful. + /// + /// \returns A new triple with a 64-bit architecture or an unknown + /// architecture if no such variant can be found. + llvm::Triple get64BitArchVariant() const; + + /// @} /// @name Static helpers for IDs. /// @{ diff --git a/include/llvm/ADT/Twine.h b/include/llvm/ADT/Twine.h index 3a60cab..9101df8 100644 --- a/include/llvm/ADT/Twine.h +++ b/include/llvm/ADT/Twine.h @@ -12,6 +12,7 @@ #include "llvm/ADT/StringRef.h" #include "llvm/Support/DataTypes.h" +#include "llvm/Support/ErrorHandling.h" #include <cassert> #include <string> @@ -425,7 +426,7 @@ namespace llvm { StringRef getSingleStringRef() const { assert(isSingleStringRef() &&"This cannot be had as a single stringref!"); switch (getLHSKind()) { - default: assert(0 && "Out of sync with isSingleStringRef"); + default: llvm_unreachable("Out of sync with isSingleStringRef"); case EmptyKind: return StringRef(); case CStringKind: return StringRef(LHS.cString); case StdStringKind: return StringRef(*LHS.stdString); diff --git a/include/llvm/ADT/ValueMap.h b/include/llvm/ADT/ValueMap.h index d1f4e5a..707d07d 100644 --- a/include/llvm/ADT/ValueMap.h +++ b/include/llvm/ADT/ValueMap.h @@ -35,7 +35,7 @@ namespace llvm { -template<typename KeyT, typename ValueT, typename Config, typename ValueInfoT> +template<typename KeyT, typename ValueT, typename Config> class ValueMapCallbackVH; template<typename DenseMapT, typename KeyT> @@ -72,13 +72,11 @@ struct ValueMapConfig { }; /// See the file comment. -template<typename KeyT, typename ValueT, typename Config = ValueMapConfig<KeyT>, - typename ValueInfoT = DenseMapInfo<ValueT> > +template<typename KeyT, typename ValueT, typename Config =ValueMapConfig<KeyT> > class ValueMap { - friend class ValueMapCallbackVH<KeyT, ValueT, Config, ValueInfoT>; - typedef ValueMapCallbackVH<KeyT, ValueT, Config, ValueInfoT> ValueMapCVH; - typedef DenseMap<ValueMapCVH, ValueT, DenseMapInfo<ValueMapCVH>, - ValueInfoT> MapT; + friend class ValueMapCallbackVH<KeyT, ValueT, Config>; + typedef ValueMapCallbackVH<KeyT, ValueT, Config> ValueMapCVH; + typedef DenseMap<ValueMapCVH, ValueT, DenseMapInfo<ValueMapCVH> > MapT; typedef typename Config::ExtraData ExtraData; MapT Map; ExtraData Data; @@ -190,11 +188,11 @@ private: // This CallbackVH updates its ValueMap when the contained Value changes, // according to the user's preferences expressed through the Config object. -template<typename KeyT, typename ValueT, typename Config, typename ValueInfoT> +template<typename KeyT, typename ValueT, typename Config> class ValueMapCallbackVH : public CallbackVH { - friend class ValueMap<KeyT, ValueT, Config, ValueInfoT>; + friend class ValueMap<KeyT, ValueT, Config>; friend struct DenseMapInfo<ValueMapCallbackVH>; - typedef ValueMap<KeyT, ValueT, Config, ValueInfoT> ValueMapT; + typedef ValueMap<KeyT, ValueT, Config> ValueMapT; typedef typename llvm::remove_pointer<KeyT>::type KeySansPointerT; ValueMapT *Map; @@ -244,9 +242,9 @@ public: } }; -template<typename KeyT, typename ValueT, typename Config, typename ValueInfoT> -struct DenseMapInfo<ValueMapCallbackVH<KeyT, ValueT, Config, ValueInfoT> > { - typedef ValueMapCallbackVH<KeyT, ValueT, Config, ValueInfoT> VH; +template<typename KeyT, typename ValueT, typename Config> +struct DenseMapInfo<ValueMapCallbackVH<KeyT, ValueT, Config> > { + typedef ValueMapCallbackVH<KeyT, ValueT, Config> VH; typedef DenseMapInfo<KeyT> PointerInfo; static inline VH getEmptyKey() { diff --git a/include/llvm/ADT/VariadicFunction.h b/include/llvm/ADT/VariadicFunction.h new file mode 100644 index 0000000..a9a0dc6 --- /dev/null +++ b/include/llvm/ADT/VariadicFunction.h @@ -0,0 +1,331 @@ +//===--- VariadicFunctions.h - Variadic Functions ---------------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file implements compile-time type-safe variadic functions. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_ADT_VARIADIC_FUNCTION_H +#define LLVM_ADT_VARIADIC_FUNCTION_H + +#include "llvm/ADT/ArrayRef.h" + +namespace llvm { + +// Define macros to aid in expanding a comma separated series with the index of +// the series pasted onto the last token. +#define LLVM_COMMA_JOIN1(x) x ## 0 +#define LLVM_COMMA_JOIN2(x) LLVM_COMMA_JOIN1(x), x ## 1 +#define LLVM_COMMA_JOIN3(x) LLVM_COMMA_JOIN2(x), x ## 2 +#define LLVM_COMMA_JOIN4(x) LLVM_COMMA_JOIN3(x), x ## 3 +#define LLVM_COMMA_JOIN5(x) LLVM_COMMA_JOIN4(x), x ## 4 +#define LLVM_COMMA_JOIN6(x) LLVM_COMMA_JOIN5(x), x ## 5 +#define LLVM_COMMA_JOIN7(x) LLVM_COMMA_JOIN6(x), x ## 6 +#define LLVM_COMMA_JOIN8(x) LLVM_COMMA_JOIN7(x), x ## 7 +#define LLVM_COMMA_JOIN9(x) LLVM_COMMA_JOIN8(x), x ## 8 +#define LLVM_COMMA_JOIN10(x) LLVM_COMMA_JOIN9(x), x ## 9 +#define LLVM_COMMA_JOIN11(x) LLVM_COMMA_JOIN10(x), x ## 10 +#define LLVM_COMMA_JOIN12(x) LLVM_COMMA_JOIN11(x), x ## 11 +#define LLVM_COMMA_JOIN13(x) LLVM_COMMA_JOIN12(x), x ## 12 +#define LLVM_COMMA_JOIN14(x) LLVM_COMMA_JOIN13(x), x ## 13 +#define LLVM_COMMA_JOIN15(x) LLVM_COMMA_JOIN14(x), x ## 14 +#define LLVM_COMMA_JOIN16(x) LLVM_COMMA_JOIN15(x), x ## 15 +#define LLVM_COMMA_JOIN17(x) LLVM_COMMA_JOIN16(x), x ## 16 +#define LLVM_COMMA_JOIN18(x) LLVM_COMMA_JOIN17(x), x ## 17 +#define LLVM_COMMA_JOIN19(x) LLVM_COMMA_JOIN18(x), x ## 18 +#define LLVM_COMMA_JOIN20(x) LLVM_COMMA_JOIN19(x), x ## 19 +#define LLVM_COMMA_JOIN21(x) LLVM_COMMA_JOIN20(x), x ## 20 +#define LLVM_COMMA_JOIN22(x) LLVM_COMMA_JOIN21(x), x ## 21 +#define LLVM_COMMA_JOIN23(x) LLVM_COMMA_JOIN22(x), x ## 22 +#define LLVM_COMMA_JOIN24(x) LLVM_COMMA_JOIN23(x), x ## 23 +#define LLVM_COMMA_JOIN25(x) LLVM_COMMA_JOIN24(x), x ## 24 +#define LLVM_COMMA_JOIN26(x) LLVM_COMMA_JOIN25(x), x ## 25 +#define LLVM_COMMA_JOIN27(x) LLVM_COMMA_JOIN26(x), x ## 26 +#define LLVM_COMMA_JOIN28(x) LLVM_COMMA_JOIN27(x), x ## 27 +#define LLVM_COMMA_JOIN29(x) LLVM_COMMA_JOIN28(x), x ## 28 +#define LLVM_COMMA_JOIN30(x) LLVM_COMMA_JOIN29(x), x ## 29 +#define LLVM_COMMA_JOIN31(x) LLVM_COMMA_JOIN30(x), x ## 30 +#define LLVM_COMMA_JOIN32(x) LLVM_COMMA_JOIN31(x), x ## 31 + +/// \brief Class which can simulate a type-safe variadic function. +/// +/// The VariadicFunction class template makes it easy to define +/// type-safe variadic functions where all arguments have the same +/// type. +/// +/// Suppose we need a variadic function like this: +/// +/// ResultT Foo(const ArgT &A_0, const ArgT &A_1, ..., const ArgT &A_N); +/// +/// Instead of many overloads of Foo(), we only need to define a helper +/// function that takes an array of arguments: +/// +/// ResultT FooImpl(ArrayRef<const ArgT *> Args) { +/// // 'Args[i]' is a pointer to the i-th argument passed to Foo(). +/// ... +/// } +/// +/// and then define Foo() like this: +/// +/// const VariadicFunction<ResultT, ArgT, FooImpl> Foo; +/// +/// VariadicFunction takes care of defining the overloads of Foo(). +/// +/// Actually, Foo is a function object (i.e. functor) instead of a plain +/// function. This object is stateless and its constructor/destructor +/// does nothing, so it's safe to create global objects and call Foo(...) at +/// any time. +/// +/// Sometimes we need a variadic function to have some fixed leading +/// arguments whose types may be different from that of the optional +/// arguments. For example: +/// +/// bool FullMatch(const StringRef &S, const RE &Regex, +/// const ArgT &A_0, ..., const ArgT &A_N); +/// +/// VariadicFunctionN is for such cases, where N is the number of fixed +/// arguments. It is like VariadicFunction, except that it takes N more +/// template arguments for the types of the fixed arguments: +/// +/// bool FullMatchImpl(const StringRef &S, const RE &Regex, +/// ArrayRef<const ArgT *> Args) { ... } +/// const VariadicFunction2<bool, const StringRef&, +/// const RE&, ArgT, FullMatchImpl> +/// FullMatch; +/// +/// Currently VariadicFunction and friends support up-to 3 +/// fixed leading arguments and up-to 32 optional arguments. +template <typename ResultT, typename ArgT, + ResultT (*Func)(ArrayRef<const ArgT *>)> +struct VariadicFunction { + ResultT operator()() const { + return Func(ArrayRef<const ArgT *>()); + } + +#define LLVM_DEFINE_OVERLOAD(N) \ + ResultT operator()(LLVM_COMMA_JOIN ## N(const ArgT &A)) const { \ + const ArgT *const Args[] = { LLVM_COMMA_JOIN ## N(&A) }; \ + return Func(makeArrayRef(Args)); \ + } + LLVM_DEFINE_OVERLOAD(1) + LLVM_DEFINE_OVERLOAD(2) + LLVM_DEFINE_OVERLOAD(3) + LLVM_DEFINE_OVERLOAD(4) + LLVM_DEFINE_OVERLOAD(5) + LLVM_DEFINE_OVERLOAD(6) + LLVM_DEFINE_OVERLOAD(7) + LLVM_DEFINE_OVERLOAD(8) + LLVM_DEFINE_OVERLOAD(9) + LLVM_DEFINE_OVERLOAD(10) + LLVM_DEFINE_OVERLOAD(11) + LLVM_DEFINE_OVERLOAD(12) + LLVM_DEFINE_OVERLOAD(13) + LLVM_DEFINE_OVERLOAD(14) + LLVM_DEFINE_OVERLOAD(15) + LLVM_DEFINE_OVERLOAD(16) + LLVM_DEFINE_OVERLOAD(17) + LLVM_DEFINE_OVERLOAD(18) + LLVM_DEFINE_OVERLOAD(19) + LLVM_DEFINE_OVERLOAD(20) + LLVM_DEFINE_OVERLOAD(21) + LLVM_DEFINE_OVERLOAD(22) + LLVM_DEFINE_OVERLOAD(23) + LLVM_DEFINE_OVERLOAD(24) + LLVM_DEFINE_OVERLOAD(25) + LLVM_DEFINE_OVERLOAD(26) + LLVM_DEFINE_OVERLOAD(27) + LLVM_DEFINE_OVERLOAD(28) + LLVM_DEFINE_OVERLOAD(29) + LLVM_DEFINE_OVERLOAD(30) + LLVM_DEFINE_OVERLOAD(31) + LLVM_DEFINE_OVERLOAD(32) +#undef LLVM_DEFINE_OVERLOAD +}; + +template <typename ResultT, typename Param0T, typename ArgT, + ResultT (*Func)(Param0T, ArrayRef<const ArgT *>)> +struct VariadicFunction1 { + ResultT operator()(Param0T P0) const { + return Func(P0, ArrayRef<const ArgT *>()); + } + +#define LLVM_DEFINE_OVERLOAD(N) \ + ResultT operator()(Param0T P0, LLVM_COMMA_JOIN ## N(const ArgT &A)) const { \ + const ArgT *const Args[] = { LLVM_COMMA_JOIN ## N(&A) }; \ + return Func(P0, makeArrayRef(Args)); \ + } + LLVM_DEFINE_OVERLOAD(1) + LLVM_DEFINE_OVERLOAD(2) + LLVM_DEFINE_OVERLOAD(3) + LLVM_DEFINE_OVERLOAD(4) + LLVM_DEFINE_OVERLOAD(5) + LLVM_DEFINE_OVERLOAD(6) + LLVM_DEFINE_OVERLOAD(7) + LLVM_DEFINE_OVERLOAD(8) + LLVM_DEFINE_OVERLOAD(9) + LLVM_DEFINE_OVERLOAD(10) + LLVM_DEFINE_OVERLOAD(11) + LLVM_DEFINE_OVERLOAD(12) + LLVM_DEFINE_OVERLOAD(13) + LLVM_DEFINE_OVERLOAD(14) + LLVM_DEFINE_OVERLOAD(15) + LLVM_DEFINE_OVERLOAD(16) + LLVM_DEFINE_OVERLOAD(17) + LLVM_DEFINE_OVERLOAD(18) + LLVM_DEFINE_OVERLOAD(19) + LLVM_DEFINE_OVERLOAD(20) + LLVM_DEFINE_OVERLOAD(21) + LLVM_DEFINE_OVERLOAD(22) + LLVM_DEFINE_OVERLOAD(23) + LLVM_DEFINE_OVERLOAD(24) + LLVM_DEFINE_OVERLOAD(25) + LLVM_DEFINE_OVERLOAD(26) + LLVM_DEFINE_OVERLOAD(27) + LLVM_DEFINE_OVERLOAD(28) + LLVM_DEFINE_OVERLOAD(29) + LLVM_DEFINE_OVERLOAD(30) + LLVM_DEFINE_OVERLOAD(31) + LLVM_DEFINE_OVERLOAD(32) +#undef LLVM_DEFINE_OVERLOAD +}; + +template <typename ResultT, typename Param0T, typename Param1T, typename ArgT, + ResultT (*Func)(Param0T, Param1T, ArrayRef<const ArgT *>)> +struct VariadicFunction2 { + ResultT operator()(Param0T P0, Param1T P1) const { + return Func(P0, P1, ArrayRef<const ArgT *>()); + } + +#define LLVM_DEFINE_OVERLOAD(N) \ + ResultT operator()(Param0T P0, Param1T P1, \ + LLVM_COMMA_JOIN ## N(const ArgT &A)) const { \ + const ArgT *const Args[] = { LLVM_COMMA_JOIN ## N(&A) }; \ + return Func(P0, P1, makeAraryRef(Args)); \ + } + LLVM_DEFINE_OVERLOAD(1) + LLVM_DEFINE_OVERLOAD(2) + LLVM_DEFINE_OVERLOAD(3) + LLVM_DEFINE_OVERLOAD(4) + LLVM_DEFINE_OVERLOAD(5) + LLVM_DEFINE_OVERLOAD(6) + LLVM_DEFINE_OVERLOAD(7) + LLVM_DEFINE_OVERLOAD(8) + LLVM_DEFINE_OVERLOAD(9) + LLVM_DEFINE_OVERLOAD(10) + LLVM_DEFINE_OVERLOAD(11) + LLVM_DEFINE_OVERLOAD(12) + LLVM_DEFINE_OVERLOAD(13) + LLVM_DEFINE_OVERLOAD(14) + LLVM_DEFINE_OVERLOAD(15) + LLVM_DEFINE_OVERLOAD(16) + LLVM_DEFINE_OVERLOAD(17) + LLVM_DEFINE_OVERLOAD(18) + LLVM_DEFINE_OVERLOAD(19) + LLVM_DEFINE_OVERLOAD(20) + LLVM_DEFINE_OVERLOAD(21) + LLVM_DEFINE_OVERLOAD(22) + LLVM_DEFINE_OVERLOAD(23) + LLVM_DEFINE_OVERLOAD(24) + LLVM_DEFINE_OVERLOAD(25) + LLVM_DEFINE_OVERLOAD(26) + LLVM_DEFINE_OVERLOAD(27) + LLVM_DEFINE_OVERLOAD(28) + LLVM_DEFINE_OVERLOAD(29) + LLVM_DEFINE_OVERLOAD(30) + LLVM_DEFINE_OVERLOAD(31) + LLVM_DEFINE_OVERLOAD(32) +#undef LLVM_DEFINE_OVERLOAD +}; + +template <typename ResultT, typename Param0T, typename Param1T, + typename Param2T, typename ArgT, + ResultT (*Func)(Param0T, Param1T, Param2T, ArrayRef<const ArgT *>)> +struct VariadicFunction3 { + ResultT operator()(Param0T P0, Param1T P1, Param2T P2) const { + return Func(P0, P1, P2, ArrayRef<const ArgT *>()); + } + +#define LLVM_DEFINE_OVERLOAD(N) \ + ResultT operator()(Param0T P0, Param1T P1, Param2T P2, \ + LLVM_COMMA_JOIN ## N(const ArgT &A)) const { \ + const ArgT *const Args[] = { LLVM_COMMA_JOIN ## N(&A) }; \ + return Func(P0, P1, P2, makeArrayRef(Args)); \ + } + LLVM_DEFINE_OVERLOAD(1) + LLVM_DEFINE_OVERLOAD(2) + LLVM_DEFINE_OVERLOAD(3) + LLVM_DEFINE_OVERLOAD(4) + LLVM_DEFINE_OVERLOAD(5) + LLVM_DEFINE_OVERLOAD(6) + LLVM_DEFINE_OVERLOAD(7) + LLVM_DEFINE_OVERLOAD(8) + LLVM_DEFINE_OVERLOAD(9) + LLVM_DEFINE_OVERLOAD(10) + LLVM_DEFINE_OVERLOAD(11) + LLVM_DEFINE_OVERLOAD(12) + LLVM_DEFINE_OVERLOAD(13) + LLVM_DEFINE_OVERLOAD(14) + LLVM_DEFINE_OVERLOAD(15) + LLVM_DEFINE_OVERLOAD(16) + LLVM_DEFINE_OVERLOAD(17) + LLVM_DEFINE_OVERLOAD(18) + LLVM_DEFINE_OVERLOAD(19) + LLVM_DEFINE_OVERLOAD(20) + LLVM_DEFINE_OVERLOAD(21) + LLVM_DEFINE_OVERLOAD(22) + LLVM_DEFINE_OVERLOAD(23) + LLVM_DEFINE_OVERLOAD(24) + LLVM_DEFINE_OVERLOAD(25) + LLVM_DEFINE_OVERLOAD(26) + LLVM_DEFINE_OVERLOAD(27) + LLVM_DEFINE_OVERLOAD(28) + LLVM_DEFINE_OVERLOAD(29) + LLVM_DEFINE_OVERLOAD(30) + LLVM_DEFINE_OVERLOAD(31) + LLVM_DEFINE_OVERLOAD(32) +#undef LLVM_DEFINE_OVERLOAD +}; + +// Cleanup the macro namespace. +#undef LLVM_COMMA_JOIN1 +#undef LLVM_COMMA_JOIN2 +#undef LLVM_COMMA_JOIN3 +#undef LLVM_COMMA_JOIN4 +#undef LLVM_COMMA_JOIN5 +#undef LLVM_COMMA_JOIN6 +#undef LLVM_COMMA_JOIN7 +#undef LLVM_COMMA_JOIN8 +#undef LLVM_COMMA_JOIN9 +#undef LLVM_COMMA_JOIN10 +#undef LLVM_COMMA_JOIN11 +#undef LLVM_COMMA_JOIN12 +#undef LLVM_COMMA_JOIN13 +#undef LLVM_COMMA_JOIN14 +#undef LLVM_COMMA_JOIN15 +#undef LLVM_COMMA_JOIN16 +#undef LLVM_COMMA_JOIN17 +#undef LLVM_COMMA_JOIN18 +#undef LLVM_COMMA_JOIN19 +#undef LLVM_COMMA_JOIN20 +#undef LLVM_COMMA_JOIN21 +#undef LLVM_COMMA_JOIN22 +#undef LLVM_COMMA_JOIN23 +#undef LLVM_COMMA_JOIN24 +#undef LLVM_COMMA_JOIN25 +#undef LLVM_COMMA_JOIN26 +#undef LLVM_COMMA_JOIN27 +#undef LLVM_COMMA_JOIN28 +#undef LLVM_COMMA_JOIN29 +#undef LLVM_COMMA_JOIN30 +#undef LLVM_COMMA_JOIN31 +#undef LLVM_COMMA_JOIN32 + +} // end namespace llvm + +#endif // LLVM_ADT_VARIADIC_FUNCTION_H diff --git a/include/llvm/ADT/VectorExtras.h b/include/llvm/ADT/VectorExtras.h deleted file mode 100644 index e05f585..0000000 --- a/include/llvm/ADT/VectorExtras.h +++ /dev/null @@ -1,41 +0,0 @@ -//===-- llvm/ADT/VectorExtras.h - Helpers for std::vector -------*- C++ -*-===// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -// -// This file contains helper functions which are useful for working with the -// std::vector class. -// -//===----------------------------------------------------------------------===// - -#ifndef LLVM_ADT_VECTOREXTRAS_H -#define LLVM_ADT_VECTOREXTRAS_H - -#include <cstdarg> -#include <vector> - -namespace llvm { - -/// make_vector - Helper function which is useful for building temporary vectors -/// to pass into type construction of CallInst ctors. This turns a null -/// terminated list of pointers (or other value types) into a real live vector. -/// -template<typename T> -inline std::vector<T> make_vector(T A, ...) { - va_list Args; - va_start(Args, A); - std::vector<T> Result; - Result.push_back(A); - while (T Val = va_arg(Args, T)) - Result.push_back(Val); - va_end(Args); - return Result; -} - -} // End llvm namespace - -#endif diff --git a/include/llvm/ADT/edit_distance.h b/include/llvm/ADT/edit_distance.h new file mode 100644 index 0000000..f77ef13 --- /dev/null +++ b/include/llvm/ADT/edit_distance.h @@ -0,0 +1,102 @@ +//===-- llvm/ADT/edit_distance.h - Array edit distance function --- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file defines a Levenshtein distance function that works for any two +// sequences, with each element of each sequence being analogous to a character +// in a string. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_ADT_EDIT_DISTANCE_H +#define LLVM_ADT_EDIT_DISTANCE_H + +#include "llvm/ADT/ArrayRef.h" +#include "llvm/ADT/OwningPtr.h" +#include <algorithm> + +namespace llvm { + +/// \brief Determine the edit distance between two sequences. +/// +/// \param FromArray the first sequence to compare. +/// +/// \param ToArray the second sequence to compare. +/// +/// \param AllowReplacements whether to allow element replacements (change one +/// element into another) as a single operation, rather than as two operations +/// (an insertion and a removal). +/// +/// \param MaxEditDistance If non-zero, the maximum edit distance that this +/// routine is allowed to compute. If the edit distance will exceed that +/// maximum, returns \c MaxEditDistance+1. +/// +/// \returns the minimum number of element insertions, removals, or (if +/// \p AllowReplacements is \c true) replacements needed to transform one of +/// the given sequences into the other. If zero, the sequences are identical. +template<typename T> +unsigned ComputeEditDistance(ArrayRef<T> FromArray, ArrayRef<T> ToArray, + bool AllowReplacements = true, + unsigned MaxEditDistance = 0) { + // The algorithm implemented below is the "classic" + // dynamic-programming algorithm for computing the Levenshtein + // distance, which is described here: + // + // http://en.wikipedia.org/wiki/Levenshtein_distance + // + // Although the algorithm is typically described using an m x n + // array, only two rows are used at a time, so this implemenation + // just keeps two separate vectors for those two rows. + typename ArrayRef<T>::size_type m = FromArray.size(); + typename ArrayRef<T>::size_type n = ToArray.size(); + + const unsigned SmallBufferSize = 64; + unsigned SmallBuffer[SmallBufferSize]; + llvm::OwningArrayPtr<unsigned> Allocated; + unsigned *Previous = SmallBuffer; + if (2*(n + 1) > SmallBufferSize) { + Previous = new unsigned [2*(n+1)]; + Allocated.reset(Previous); + } + unsigned *Current = Previous + (n + 1); + + for (unsigned i = 0; i <= n; ++i) + Previous[i] = i; + + for (typename ArrayRef<T>::size_type y = 1; y <= m; ++y) { + Current[0] = y; + unsigned BestThisRow = Current[0]; + + for (typename ArrayRef<T>::size_type x = 1; x <= n; ++x) { + if (AllowReplacements) { + Current[x] = std::min( + Previous[x-1] + (FromArray[y-1] == ToArray[x-1] ? 0u : 1u), + std::min(Current[x-1], Previous[x])+1); + } + else { + if (FromArray[y-1] == ToArray[x-1]) Current[x] = Previous[x-1]; + else Current[x] = std::min(Current[x-1], Previous[x]) + 1; + } + BestThisRow = std::min(BestThisRow, Current[x]); + } + + if (MaxEditDistance && BestThisRow > MaxEditDistance) + return MaxEditDistance + 1; + + unsigned *tmp = Current; + Current = Previous; + Previous = tmp; + } + + unsigned Result = Previous[n]; + return Result; +} + +} // End llvm namespace + +#endif diff --git a/include/llvm/ADT/ilist.h b/include/llvm/ADT/ilist.h index bcacfd9..ba9864a 100644 --- a/include/llvm/ADT/ilist.h +++ b/include/llvm/ADT/ilist.h @@ -652,10 +652,6 @@ struct ilist : public iplist<NodeTy> { void push_front(const NodeTy &val) { insert(this->begin(), val); } void push_back(const NodeTy &val) { insert(this->end(), val); } - // Special forms of insert... - template<class InIt> void insert(iterator where, InIt first, InIt last) { - for (; first != last; ++first) insert(where, *first); - } void insert(iterator where, size_type count, const NodeTy &val) { for (; count != 0; --count) insert(where, val); } |
