diff options
Diffstat (limited to 'include/llvm/ADT')
46 files changed, 1090 insertions, 274 deletions
diff --git a/include/llvm/ADT/APFloat.h b/include/llvm/ADT/APFloat.h index 31c6e6a..14bcaef 100644 --- a/include/llvm/ADT/APFloat.h +++ b/include/llvm/ADT/APFloat.h @@ -97,8 +97,8 @@ nexttoward. */ -#ifndef LLVM_FLOAT_H -#define LLVM_FLOAT_H +#ifndef LLVM_ADT_APFLOAT_H +#define LLVM_ADT_APFLOAT_H // APInt contains static functions implementing bignum arithmetic. #include "llvm/ADT/APInt.h" @@ -184,9 +184,9 @@ namespace llvm { APFloat(const fltSemantics &, integerPart); APFloat(const fltSemantics &, fltCategory, bool negative); APFloat(const fltSemantics &, uninitializedTag); + APFloat(const fltSemantics &, const APInt &); explicit APFloat(double d); explicit APFloat(float f); - explicit APFloat(const APInt &, bool isIEEE = false); APFloat(const APFloat &); ~APFloat(); @@ -300,7 +300,7 @@ namespace llvm { /* The definition of equality is not straightforward for floating point, so we won't use operator==. Use one of the following, or write whatever it is you really mean. */ - // bool operator==(const APFloat &) const; // DO NOT IMPLEMENT + bool operator==(const APFloat &) const LLVM_DELETED_FUNCTION; /* IEEE comparison with another floating point number (NaNs compare unordered, 0==-0). */ @@ -327,6 +327,7 @@ namespace llvm { bool isNegative() const { return sign; } bool isPosZero() const { return isZero() && !isNegative(); } bool isNegZero() const { return isZero() && isNegative(); } + bool isDenormal() const; APFloat& operator=(const APFloat &); @@ -422,7 +423,7 @@ namespace llvm { APInt convertQuadrupleAPFloatToAPInt() const; APInt convertF80LongDoubleAPFloatToAPInt() const; APInt convertPPCDoubleDoubleAPFloatToAPInt() const; - void initFromAPInt(const APInt& api, bool isIEEE = false); + void initFromAPInt(const fltSemantics *Sem, const APInt& api); void initFromHalfAPInt(const APInt& api); void initFromFloatAPInt(const APInt& api); void initFromDoubleAPInt(const APInt& api); @@ -462,4 +463,4 @@ namespace llvm { hash_code hash_value(const APFloat &Arg); } /* namespace llvm */ -#endif /* LLVM_FLOAT_H */ +#endif /* LLVM_ADT_APFLOAT_H */ diff --git a/include/llvm/ADT/APInt.h b/include/llvm/ADT/APInt.h index c7c8016b..3d8b72d 100644 --- a/include/llvm/ADT/APInt.h +++ b/include/llvm/ADT/APInt.h @@ -12,8 +12,8 @@ // //===----------------------------------------------------------------------===// -#ifndef LLVM_APINT_H -#define LLVM_APINT_H +#ifndef LLVM_ADT_APINT_H +#define LLVM_ADT_APINT_H #include "llvm/ADT/ArrayRef.h" #include "llvm/Support/Compiler.h" @@ -274,7 +274,7 @@ public: initSlowCase(that); } -#if LLVM_USE_RVALUE_REFERENCES +#if LLVM_HAS_RVALUE_REFERENCES /// @brief Move Constructor. APInt(APInt&& that) : BitWidth(that.BitWidth), VAL(that.VAL) { that.BitWidth = 0; @@ -427,7 +427,7 @@ public: /// @returns the all-ones value for an APInt of the specified bit-width. /// @brief Get the all-ones value. static APInt getAllOnesValue(unsigned numBits) { - return APInt(numBits, -1ULL, true); + return APInt(numBits, UINT64_MAX, true); } /// @returns the '0' value for an APInt of the specified bit-width. @@ -498,13 +498,24 @@ public: if (loBitsSet == 0) return APInt(numBits, 0); if (loBitsSet == APINT_BITS_PER_WORD) - return APInt(numBits, -1ULL); + return APInt(numBits, UINT64_MAX); // For small values, return quickly. if (loBitsSet <= APINT_BITS_PER_WORD) - return APInt(numBits, -1ULL >> (APINT_BITS_PER_WORD - loBitsSet)); + return APInt(numBits, UINT64_MAX >> (APINT_BITS_PER_WORD - loBitsSet)); return getAllOnesValue(numBits).lshr(numBits - loBitsSet); } + /// \brief Return a value containing V broadcasted over NewLen bits. + static APInt getSplat(unsigned NewLen, const APInt &V) { + assert(NewLen >= V.getBitWidth() && "Can't splat to smaller bit width!"); + + APInt Val = V.zextOrSelf(NewLen); + for (unsigned I = V.getBitWidth(); I < NewLen; I <<= 1) + Val |= Val << I; + + return Val; + } + /// \brief Determine if two APInts have the same value, after zero-extending /// one of them (if needed!) to ensure that the bit-widths match. static bool isSameValue(const APInt &I1, const APInt &I2) { @@ -601,7 +612,7 @@ public: return AssignSlowCase(RHS); } -#if LLVM_USE_RVALUE_REFERENCES +#if LLVM_HAS_RVALUE_REFERENCES /// @brief Move assignment operator. APInt& operator=(APInt&& that) { if (!isSingleWord()) @@ -799,16 +810,7 @@ public: /// Signed divide this APInt by APInt RHS. /// @brief Signed division function for APInt. - APInt sdiv(const APInt &RHS) const { - if (isNegative()) - if (RHS.isNegative()) - return (-(*this)).udiv(-RHS); - else - return -((-(*this)).udiv(RHS)); - else if (RHS.isNegative()) - return -(this->udiv(-RHS)); - return this->udiv(RHS); - } + APInt sdiv(const APInt &RHS) const; /// Perform an unsigned remainder operation on this APInt with RHS being the /// divisor. Both this and RHS are treated as unsigned quantities for purposes @@ -821,16 +823,7 @@ public: /// Signed remainder operation on APInt. /// @brief Function for signed remainder operation. - APInt srem(const APInt &RHS) const { - if (isNegative()) - if (RHS.isNegative()) - return -((-(*this)).urem(-RHS)); - else - return -((-(*this)).urem(RHS)); - else if (RHS.isNegative()) - return this->urem(-RHS); - return this->urem(RHS); - } + APInt srem(const APInt &RHS) const; /// Sometimes it is convenient to divide two APInt values and obtain both the /// quotient and remainder. This function does both operations in the same @@ -842,24 +835,9 @@ public: APInt &Quotient, APInt &Remainder); static void sdivrem(const APInt &LHS, const APInt &RHS, - APInt &Quotient, APInt &Remainder) { - if (LHS.isNegative()) { - if (RHS.isNegative()) - APInt::udivrem(-LHS, -RHS, Quotient, Remainder); - else { - APInt::udivrem(-LHS, RHS, Quotient, Remainder); - Quotient = -Quotient; - } - Remainder = -Remainder; - } else if (RHS.isNegative()) { - APInt::udivrem(LHS, -RHS, Quotient, Remainder); - Quotient = -Quotient; - } else { - APInt::udivrem(LHS, RHS, Quotient, Remainder); - } - } - - + APInt &Quotient, APInt &Remainder); + + // Operations that return overflow indicators. APInt sadd_ov(const APInt &RHS, bool &Overflow) const; APInt uadd_ov(const APInt &RHS, bool &Overflow) const; @@ -1113,11 +1091,11 @@ public: /// @brief Set every bit to 1. void setAllBits() { if (isSingleWord()) - VAL = -1ULL; + VAL = UINT64_MAX; else { // Set all the bits in all the words. for (unsigned i = 0; i < getNumWords(); ++i) - pVal[i] = -1ULL; + pVal[i] = UINT64_MAX; } // Clear the unused ones clearUnusedBits(); @@ -1142,10 +1120,10 @@ public: /// @brief Toggle every bit to its opposite value. void flipAllBits() { if (isSingleWord()) - VAL ^= -1ULL; + VAL ^= UINT64_MAX; else { for (unsigned i = 0; i < getNumWords(); ++i) - pVal[i] ^= -1ULL; + pVal[i] ^= UINT64_MAX; } clearUnusedBits(); } @@ -1191,7 +1169,8 @@ public: /// APInt. This is used in conjunction with getActiveData to extract the raw /// value of the APInt. unsigned getActiveWords() const { - return whichWord(getActiveBits()-1) + 1; + unsigned numActiveBits = getActiveBits(); + return numActiveBits ? whichWord(numActiveBits - 1) + 1 : 1; } /// Computes the minimum bit width for this APInt while considering it to be diff --git a/include/llvm/ADT/APSInt.h b/include/llvm/ADT/APSInt.h index 048c65c..11be4c5 100644 --- a/include/llvm/ADT/APSInt.h +++ b/include/llvm/ADT/APSInt.h @@ -12,8 +12,8 @@ // //===----------------------------------------------------------------------===// -#ifndef LLVM_APSINT_H -#define LLVM_APSINT_H +#ifndef LLVM_ADT_APSINT_H +#define LLVM_ADT_APSINT_H #include "llvm/ADT/APInt.h" @@ -23,7 +23,7 @@ class APSInt : public APInt { bool IsUnsigned; public: /// Default constructor that creates an uninitialized APInt. - explicit APSInt() {} + explicit APSInt() : IsUnsigned(false) {} /// APSInt ctor - Create an APSInt with the specified width, default to /// unsigned. @@ -161,11 +161,11 @@ public: } APSInt& operator++() { - static_cast<APInt&>(*this)++; + ++(static_cast<APInt&>(*this)); return *this; } APSInt& operator--() { - static_cast<APInt&>(*this)--; + --(static_cast<APInt&>(*this)); return *this; } APSInt operator++(int) { diff --git a/include/llvm/ADT/ArrayRef.h b/include/llvm/ADT/ArrayRef.h index 1e35d62..c555c1c 100644 --- a/include/llvm/ADT/ArrayRef.h +++ b/include/llvm/ADT/ArrayRef.h @@ -33,6 +33,8 @@ namespace llvm { typedef const T *const_iterator; typedef size_t size_type; + typedef std::reverse_iterator<iterator> reverse_iterator; + private: /// The start of the array, in an external buffer. const T *Data; @@ -84,6 +86,9 @@ namespace llvm { iterator begin() const { return Data; } iterator end() const { return Data + Length; } + reverse_iterator rbegin() const { return reverse_iterator(end()); } + reverse_iterator rend() const { return reverse_iterator(begin()); } + /// empty - Check if the array is empty. bool empty() const { return Length == 0; } @@ -171,41 +176,41 @@ namespace llvm { /// 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()); @@ -217,14 +222,14 @@ namespace llvm { 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 /// @{ @@ -301,5 +306,5 @@ namespace llvm { static const bool value = true; }; } - + #endif diff --git a/include/llvm/ADT/BitVector.h b/include/llvm/ADT/BitVector.h index 9d6388f..82cfdf4 100644 --- a/include/llvm/ADT/BitVector.h +++ b/include/llvm/ADT/BitVector.h @@ -98,7 +98,7 @@ public: std::memcpy(Bits, RHS.Bits, Capacity * sizeof(BitWord)); } -#if LLVM_USE_RVALUE_REFERENCES +#if LLVM_HAS_RVALUE_REFERENCES BitVector(BitVector &&RHS) : Bits(RHS.Bits), Size(RHS.Size), Capacity(RHS.Capacity) { RHS.Bits = 0; @@ -452,7 +452,7 @@ public: return *this; } -#if LLVM_USE_RVALUE_REFERENCES +#if LLVM_HAS_RVALUE_REFERENCES const BitVector &operator=(BitVector &&RHS) { if (this == &RHS) return *this; diff --git a/include/llvm/ADT/DAGDeltaAlgorithm.h b/include/llvm/ADT/DAGDeltaAlgorithm.h index 2dfed07..3dd862c 100644 --- a/include/llvm/ADT/DAGDeltaAlgorithm.h +++ b/include/llvm/ADT/DAGDeltaAlgorithm.h @@ -9,8 +9,8 @@ #ifndef LLVM_ADT_DAGDELTAALGORITHM_H #define LLVM_ADT_DAGDELTAALGORITHM_H -#include <vector> #include <set> +#include <vector> namespace llvm { diff --git a/include/llvm/ADT/DeltaAlgorithm.h b/include/llvm/ADT/DeltaAlgorithm.h index 7bf7960..4d07e04 100644 --- a/include/llvm/ADT/DeltaAlgorithm.h +++ b/include/llvm/ADT/DeltaAlgorithm.h @@ -9,8 +9,8 @@ #ifndef LLVM_ADT_DELTAALGORITHM_H #define LLVM_ADT_DELTAALGORITHM_H -#include <vector> #include <set> +#include <vector> namespace llvm { diff --git a/include/llvm/ADT/DenseMap.h b/include/llvm/ADT/DenseMap.h index ac4bdbd..d410619 100644 --- a/include/llvm/ADT/DenseMap.h +++ b/include/llvm/ADT/DenseMap.h @@ -14,20 +14,20 @@ #ifndef LLVM_ADT_DENSEMAP_H #define LLVM_ADT_DENSEMAP_H -#include "llvm/Support/Compiler.h" +#include "llvm/ADT/DenseMapInfo.h" #include "llvm/Support/AlignOf.h" +#include "llvm/Support/Compiler.h" #include "llvm/Support/MathExtras.h" #include "llvm/Support/PointerLikeTypeTraits.h" #include "llvm/Support/type_traits.h" -#include "llvm/ADT/DenseMapInfo.h" #include <algorithm> -#include <iterator> -#include <new> -#include <utility> #include <cassert> #include <climits> #include <cstddef> #include <cstring> +#include <iterator> +#include <new> +#include <utility> namespace llvm { @@ -75,7 +75,7 @@ public: void clear() { if (getNumEntries() == 0 && getNumTombstones() == 0) return; - + // If the capacity of the array is huge, and the # elements used is small, // shrink the array. if (getNumEntries() * 4 < getNumBuckets() && getNumBuckets() > 64) { @@ -159,6 +159,24 @@ public: return std::make_pair(iterator(TheBucket, getBucketsEnd(), true), true); } +#if LLVM_HAS_RVALUE_REFERENCES + // Inserts key,value pair into the map if the key isn't already in the map. + // If the key is already in the map, it returns false and doesn't update the + // value. + std::pair<iterator, bool> insert(std::pair<KeyT, ValueT> &&KV) { + BucketT *TheBucket; + if (LookupBucketFor(KV.first, TheBucket)) + return std::make_pair(iterator(TheBucket, getBucketsEnd(), true), + false); // Already in map. + + // Otherwise, insert the new element. + TheBucket = InsertIntoBucket(std::move(KV.first), + std::move(KV.second), + TheBucket); + return std::make_pair(iterator(TheBucket, getBucketsEnd(), true), true); + } +#endif + /// insert - Range insertion of pairs. template<typename InputIt> void insert(InputIt I, InputIt E) { @@ -198,7 +216,7 @@ public: return FindAndConstruct(Key).second; } -#if LLVM_USE_RVALUE_REFERENCES +#if LLVM_HAS_RVALUE_REFERENCES value_type& FindAndConstruct(KeyT &&Key) { BucketT *TheBucket; if (LookupBucketFor(Key, TheBucket)) @@ -383,7 +401,7 @@ private: return TheBucket; } -#if LLVM_USE_RVALUE_REFERENCES +#if LLVM_HAS_RVALUE_REFERENCES BucketT *InsertIntoBucket(const KeyT &Key, ValueT &&Value, BucketT *TheBucket) { TheBucket = InsertIntoBucketImpl(Key, TheBucket); @@ -430,7 +448,8 @@ private: incrementNumEntries(); // If we are writing over a tombstone, remember this. - if (!KeyInfoT::isEqual(TheBucket->first, getEmptyKey())) + const KeyT EmptyKey = getEmptyKey(); + if (!KeyInfoT::isEqual(TheBucket->first, EmptyKey)) decrementNumTombstones(); return TheBucket; @@ -474,7 +493,6 @@ private: if (KeyInfoT::isEqual(ThisBucket->first, EmptyKey)) { // If we've already seen a tombstone while probing, fill it in instead // of the empty bucket we eventually probed to. - if (FoundTombstone) ThisBucket = FoundTombstone; FoundBucket = FoundTombstone ? FoundTombstone : ThisBucket; return false; } @@ -531,13 +549,13 @@ public: init(NumInitBuckets); } - DenseMap(const DenseMap &other) { + DenseMap(const DenseMap &other) : BaseT() { init(0); copyFrom(other); } -#if LLVM_USE_RVALUE_REFERENCES - DenseMap(DenseMap &&other) { +#if LLVM_HAS_RVALUE_REFERENCES + DenseMap(DenseMap &&other) : BaseT() { init(0); swap(other); } @@ -566,7 +584,7 @@ public: return *this; } -#if LLVM_USE_RVALUE_REFERENCES +#if LLVM_HAS_RVALUE_REFERENCES DenseMap& operator=(DenseMap &&other) { this->destroyAll(); operator delete(Buckets); @@ -700,7 +718,7 @@ public: copyFrom(other); } -#if LLVM_USE_RVALUE_REFERENCES +#if LLVM_HAS_RVALUE_REFERENCES SmallDenseMap(SmallDenseMap &&other) { init(0); swap(other); @@ -795,7 +813,7 @@ public: return *this; } -#if LLVM_USE_RVALUE_REFERENCES +#if LLVM_HAS_RVALUE_REFERENCES SmallDenseMap& operator=(SmallDenseMap &&other) { this->destroyAll(); deallocateBuckets(); @@ -1027,7 +1045,7 @@ private: ++Ptr; } }; - + template<typename KeyT, typename ValueT, typename KeyInfoT> static inline size_t capacity_in_bytes(const DenseMap<KeyT, ValueT, KeyInfoT> &X) { diff --git a/include/llvm/ADT/DenseSet.h b/include/llvm/ADT/DenseSet.h index 8ab9a33..d699ad5 100644 --- a/include/llvm/ADT/DenseSet.h +++ b/include/llvm/ADT/DenseSet.h @@ -32,8 +32,10 @@ public: bool empty() const { return TheMap.empty(); } unsigned size() const { return TheMap.size(); } + size_t getMemorySize() const { return TheMap.getMemorySize(); } - /// Grow the denseset so that it has at least Size buckets. Does not shrink + /// Grow the DenseSet so that it has at least Size buckets. Will not shrink + /// the Size of the set. void resize(size_t Size) { TheMap.resize(Size); } void clear() { diff --git a/include/llvm/ADT/DepthFirstIterator.h b/include/llvm/ADT/DepthFirstIterator.h index 519b180..6445442 100644 --- a/include/llvm/ADT/DepthFirstIterator.h +++ b/include/llvm/ADT/DepthFirstIterator.h @@ -34,8 +34,8 @@ #define LLVM_ADT_DEPTHFIRSTITERATOR_H #include "llvm/ADT/GraphTraits.h" -#include "llvm/ADT/SmallPtrSet.h" #include "llvm/ADT/PointerIntPair.h" +#include "llvm/ADT/SmallPtrSet.h" #include <set> #include <vector> diff --git a/include/llvm/ADT/FoldingSet.h b/include/llvm/ADT/FoldingSet.h index 375d84a..91794de 100644 --- a/include/llvm/ADT/FoldingSet.h +++ b/include/llvm/ADT/FoldingSet.h @@ -16,9 +16,9 @@ #ifndef LLVM_ADT_FOLDINGSET_H #define LLVM_ADT_FOLDINGSET_H -#include "llvm/Support/DataTypes.h" #include "llvm/ADT/SmallVector.h" #include "llvm/ADT/StringRef.h" +#include "llvm/Support/DataTypes.h" namespace llvm { class APFloat; diff --git a/include/llvm/ADT/ImmutableIntervalMap.h b/include/llvm/ADT/ImmutableIntervalMap.h index fa7ccb9..6793c6b 100644 --- a/include/llvm/ADT/ImmutableIntervalMap.h +++ b/include/llvm/ADT/ImmutableIntervalMap.h @@ -11,8 +11,8 @@ // //===----------------------------------------------------------------------===// -#ifndef LLVM_ADT_IMMUTABLE_INTERVAL_MAP_H -#define LLVM_ADT_IMMUTABLE_INTERVAL_MAP_H +#ifndef LLVM_ADT_IMMUTABLEINTERVALMAP_H +#define LLVM_ADT_IMMUTABLEINTERVALMAP_H #include "llvm/ADT/ImmutableMap.h" diff --git a/include/llvm/ADT/ImmutableList.h b/include/llvm/ADT/ImmutableList.h index 20bdd90..7f0c239 100644 --- a/include/llvm/ADT/ImmutableList.h +++ b/include/llvm/ADT/ImmutableList.h @@ -11,11 +11,11 @@ // //===----------------------------------------------------------------------===// -#ifndef LLVM_ADT_IMLIST_H -#define LLVM_ADT_IMLIST_H +#ifndef LLVM_ADT_IMMUTABLELIST_H +#define LLVM_ADT_IMMUTABLELIST_H -#include "llvm/Support/Allocator.h" #include "llvm/ADT/FoldingSet.h" +#include "llvm/Support/Allocator.h" #include "llvm/Support/DataTypes.h" #include <cassert> diff --git a/include/llvm/ADT/ImmutableMap.h b/include/llvm/ADT/ImmutableMap.h index 4883c5b..a667479 100644 --- a/include/llvm/ADT/ImmutableMap.h +++ b/include/llvm/ADT/ImmutableMap.h @@ -11,8 +11,8 @@ // //===----------------------------------------------------------------------===// -#ifndef LLVM_ADT_IMMAP_H -#define LLVM_ADT_IMMAP_H +#ifndef LLVM_ADT_IMMUTABLEMAP_H +#define LLVM_ADT_IMMUTABLEMAP_H #include "llvm/ADT/ImmutableSet.h" @@ -211,17 +211,22 @@ public: friend class ImmutableMap; public: - value_type_ref operator*() const { return itr->getValue(); } - value_type* operator->() const { return &itr->getValue(); } + typedef typename ImmutableMap<KeyT,ValT,ValInfo>::value_type value_type; + typedef typename ImmutableMap<KeyT,ValT,ValInfo>::value_type_ref reference; + typedef typename iterator::value_type *pointer; + typedef std::bidirectional_iterator_tag iterator_category; + + typename iterator::reference operator*() const { return itr->getValue(); } + typename iterator::pointer operator->() const { return &itr->getValue(); } key_type_ref getKey() const { return itr->getValue().first; } data_type_ref getData() const { return itr->getValue().second; } - iterator& operator++() { ++itr; return *this; } iterator operator++(int) { iterator tmp(*this); ++itr; return tmp; } iterator& operator--() { --itr; return *this; } iterator operator--(int) { iterator tmp(*this); --itr; return tmp; } + bool operator==(const iterator& RHS) const { return RHS.itr == itr; } bool operator!=(const iterator& RHS) const { return RHS.itr != itr; } }; @@ -288,6 +293,13 @@ public: Factory(F) { if (Root) { Root->retain(); } } + + explicit ImmutableMapRef(const ImmutableMap<KeyT, ValT> &X, + typename ImmutableMap<KeyT, ValT>::Factory &F) + : Root(X.getRootWithoutRetain()), + Factory(F.getTreeFactory()) { + if (Root) { Root->retain(); } + } ImmutableMapRef(const ImmutableMapRef &X) : Root(X.Root), @@ -318,12 +330,20 @@ public: return ImmutableMapRef(0, F); } - ImmutableMapRef add(key_type_ref K, data_type_ref D) { + void manualRetain() { + if (Root) Root->retain(); + } + + void manualRelease() { + if (Root) Root->release(); + } + + ImmutableMapRef add(key_type_ref K, data_type_ref D) const { TreeTy *NewT = Factory->add(Root, std::pair<key_type, data_type>(K, D)); return ImmutableMapRef(NewT, Factory); } - ImmutableMapRef remove(key_type_ref K) { + ImmutableMapRef remove(key_type_ref K) const { TreeTy *NewT = Factory->remove(Root, K); return ImmutableMapRef(NewT, Factory); } diff --git a/include/llvm/ADT/ImmutableSet.h b/include/llvm/ADT/ImmutableSet.h index 3900f96..fbdf066 100644 --- a/include/llvm/ADT/ImmutableSet.h +++ b/include/llvm/ADT/ImmutableSet.h @@ -11,12 +11,12 @@ // //===----------------------------------------------------------------------===// -#ifndef LLVM_ADT_IMSET_H -#define LLVM_ADT_IMSET_H +#ifndef LLVM_ADT_IMMUTABLESET_H +#define LLVM_ADT_IMMUTABLESET_H -#include "llvm/Support/Allocator.h" #include "llvm/ADT/DenseMap.h" #include "llvm/ADT/FoldingSet.h" +#include "llvm/Support/Allocator.h" #include "llvm/Support/DataTypes.h" #include "llvm/Support/ErrorHandling.h" #include <cassert> @@ -1054,18 +1054,27 @@ public: class iterator { typename TreeTy::iterator itr; + + iterator() {} iterator(TreeTy* t) : itr(t) {} friend class ImmutableSet<ValT,ValInfo>; + public: - iterator() {} - inline value_type_ref operator*() const { return itr->getValue(); } - inline iterator& operator++() { ++itr; return *this; } - inline iterator operator++(int) { iterator tmp(*this); ++itr; return tmp; } - inline iterator& operator--() { --itr; return *this; } - inline iterator operator--(int) { iterator tmp(*this); --itr; return tmp; } - inline bool operator==(const iterator& RHS) const { return RHS.itr == itr; } - inline bool operator!=(const iterator& RHS) const { return RHS.itr != itr; } - inline value_type *operator->() const { return &(operator*()); } + typedef typename ImmutableSet<ValT,ValInfo>::value_type value_type; + typedef typename ImmutableSet<ValT,ValInfo>::value_type_ref reference; + typedef typename iterator::value_type *pointer; + typedef std::bidirectional_iterator_tag iterator_category; + + typename iterator::reference operator*() const { return itr->getValue(); } + typename iterator::pointer operator->() const { return &(operator*()); } + + iterator& operator++() { ++itr; return *this; } + iterator operator++(int) { iterator tmp(*this); ++itr; return tmp; } + iterator& operator--() { --itr; return *this; } + iterator operator--(int) { iterator tmp(*this); --itr; return tmp; } + + bool operator==(const iterator& RHS) const { return RHS.itr == itr; } + bool operator!=(const iterator& RHS) const { return RHS.itr != itr; } }; iterator begin() const { return iterator(Root); } diff --git a/include/llvm/ADT/IntervalMap.h b/include/llvm/ADT/IntervalMap.h index 931b67e..c4083ee 100644 --- a/include/llvm/ADT/IntervalMap.h +++ b/include/llvm/ADT/IntervalMap.h @@ -99,8 +99,8 @@ #ifndef LLVM_ADT_INTERVALMAP_H #define LLVM_ADT_INTERVALMAP_H -#include "llvm/ADT/SmallVector.h" #include "llvm/ADT/PointerIntPair.h" +#include "llvm/ADT/SmallVector.h" #include "llvm/Support/Allocator.h" #include "llvm/Support/RecyclingAllocator.h" #include <iterator> @@ -151,6 +151,26 @@ struct IntervalMapInfo { }; +template <typename T> +struct IntervalMapHalfOpenInfo { + + /// startLess - Return true if x is not in [a;b). + static inline bool startLess(const T &x, const T &a) { + return x < a; + } + + /// stopLess - Return true if x is not in [a;b). + static inline bool stopLess(const T &b, const T &x) { + return b <= x; + } + + /// adjacent - Return true when the intervals [x;a) and [b;y) can coalesce. + static inline bool adjacent(const T &a, const T &b) { + return a == b; + } + +}; + /// IntervalMapImpl - Namespace used for IntervalMap implementation details. /// It should be considered private to the implementation. namespace IntervalMapImpl { diff --git a/include/llvm/ADT/IntrusiveRefCntPtr.h b/include/llvm/ADT/IntrusiveRefCntPtr.h index a9724ee..b8b8861 100644 --- a/include/llvm/ADT/IntrusiveRefCntPtr.h +++ b/include/llvm/ADT/IntrusiveRefCntPtr.h @@ -18,8 +18,8 @@ // //===----------------------------------------------------------------------===// -#ifndef LLVM_ADT_INTRUSIVE_REF_CNT_PTR -#define LLVM_ADT_INTRUSIVE_REF_CNT_PTR +#ifndef LLVM_ADT_INTRUSIVEREFCNTPTR_H +#define LLVM_ADT_INTRUSIVEREFCNTPTR_H #include "llvm/Support/Casting.h" #include "llvm/Support/Compiler.h" @@ -123,7 +123,7 @@ namespace llvm { retain(); } -#if LLVM_USE_RVALUE_REFERENCES +#if LLVM_HAS_RVALUE_REFERENCES IntrusiveRefCntPtr(IntrusiveRefCntPtr&& S) : Obj(S.Obj) { S.Obj = 0; } @@ -226,13 +226,13 @@ namespace llvm { template<class T> struct simplify_type<IntrusiveRefCntPtr<T> > { typedef T* SimpleType; - static SimpleType getSimplifiedValue(const IntrusiveRefCntPtr<T>& Val) { + static SimpleType getSimplifiedValue(IntrusiveRefCntPtr<T>& Val) { return Val.getPtr(); } }; template<class T> struct simplify_type<const IntrusiveRefCntPtr<T> > { - typedef T* SimpleType; + typedef /*const*/ T* SimpleType; static SimpleType getSimplifiedValue(const IntrusiveRefCntPtr<T>& Val) { return Val.getPtr(); } @@ -240,4 +240,4 @@ namespace llvm { } // end namespace llvm -#endif // LLVM_ADT_INTRUSIVE_REF_CNT_PTR +#endif // LLVM_ADT_INTRUSIVEREFCNTPTR_H diff --git a/include/llvm/ADT/MapVector.h b/include/llvm/ADT/MapVector.h index 6aacca5..f6fcb08 100644 --- a/include/llvm/ADT/MapVector.h +++ b/include/llvm/ADT/MapVector.h @@ -19,6 +19,7 @@ #include "llvm/ADT/ArrayRef.h" #include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/STLExtras.h" #include <vector> namespace llvm { @@ -63,6 +64,11 @@ public: return Vector.empty(); } + std::pair<KeyT, ValueT> &front() { return Vector.front(); } + const std::pair<KeyT, ValueT> &front() const { return Vector.front(); } + std::pair<KeyT, ValueT> &back() { return Vector.back(); } + const std::pair<KeyT, ValueT> &back() const { return Vector.back(); } + void clear() { Map.clear(); Vector.clear(); @@ -79,10 +85,46 @@ public: return Vector[I].second; } + ValueT lookup(const KeyT &Key) const { + typename MapType::const_iterator Pos = Map.find(Key); + return Pos == Map.end()? ValueT() : Vector[Pos->second].second; + } + + std::pair<iterator, bool> insert(const std::pair<KeyT, ValueT> &KV) { + std::pair<KeyT, unsigned> Pair = std::make_pair(KV.first, 0); + std::pair<typename MapType::iterator, bool> Result = Map.insert(Pair); + unsigned &I = Result.first->second; + if (Result.second) { + Vector.push_back(std::make_pair(KV.first, KV.second)); + I = Vector.size() - 1; + return std::make_pair(llvm::prior(end()), true); + } + return std::make_pair(begin() + I, false); + } + unsigned count(const KeyT &Key) const { typename MapType::const_iterator Pos = Map.find(Key); return Pos == Map.end()? 0 : 1; } + + iterator find(const KeyT &Key) { + typename MapType::const_iterator Pos = Map.find(Key); + return Pos == Map.end()? Vector.end() : + (Vector.begin() + Pos->second); + } + + const_iterator find(const KeyT &Key) const { + typename MapType::const_iterator Pos = Map.find(Key); + return Pos == Map.end()? Vector.end() : + (Vector.begin() + Pos->second); + } + + /// \brief Remove the last element from the vector. + void pop_back() { + typename MapType::iterator Pos = Map.find(Vector.back().first); + Map.erase(Pos); + Vector.pop_back(); + } }; } diff --git a/include/llvm/ADT/None.h b/include/llvm/ADT/None.h new file mode 100644 index 0000000..5793bd2 --- /dev/null +++ b/include/llvm/ADT/None.h @@ -0,0 +1,27 @@ +//===-- None.h - Simple null value for implicit construction ------*- C++ -*-=// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file provides None, an enumerator for use in implicit constructors +// of various (usually templated) types to make such construction more +// terse. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_ADT_NONE_H +#define LLVM_ADT_NONE_H + +namespace llvm { +/// \brief A simple null object to allow implicit construction of Optional<T> +/// and similar types without having to spell out the specialization's name. +enum NoneType { + None +}; +} + +#endif diff --git a/include/llvm/ADT/NullablePtr.h b/include/llvm/ADT/NullablePtr.h index a9c47a1..8ddfd5d 100644 --- a/include/llvm/ADT/NullablePtr.h +++ b/include/llvm/ADT/NullablePtr.h @@ -11,8 +11,8 @@ // //===----------------------------------------------------------------------===// -#ifndef LLVM_ADT_NULLABLE_PTR_H -#define LLVM_ADT_NULLABLE_PTR_H +#ifndef LLVM_ADT_NULLABLEPTR_H +#define LLVM_ADT_NULLABLEPTR_H #include <cassert> #include <cstddef> diff --git a/include/llvm/ADT/Optional.h b/include/llvm/ADT/Optional.h index f43aeb1..194e53f 100644 --- a/include/llvm/ADT/Optional.h +++ b/include/llvm/ADT/Optional.h @@ -13,13 +13,15 @@ // //===----------------------------------------------------------------------===// -#ifndef LLVM_ADT_OPTIONAL -#define LLVM_ADT_OPTIONAL +#ifndef LLVM_ADT_OPTIONAL_H +#define LLVM_ADT_OPTIONAL_H +#include "llvm/ADT/None.h" #include "llvm/Support/Compiler.h" +#include "llvm/Support/AlignOf.h" #include <cassert> -#if LLVM_USE_RVALUE_REFERENCES +#if LLVM_HAS_RVALUE_REFERENCES #include <utility> #endif @@ -27,54 +29,116 @@ namespace llvm { template<typename T> class Optional { - T x; - unsigned hasVal : 1; + AlignedCharArrayUnion<T> storage; + bool hasVal; public: - explicit Optional() : x(), hasVal(false) {} - Optional(const T &y) : x(y), hasVal(true) {} + Optional(NoneType) : hasVal(false) {} + explicit Optional() : hasVal(false) {} + Optional(const T &y) : hasVal(true) { + new (storage.buffer) T(y); + } + Optional(const Optional &O) : hasVal(O.hasVal) { + if (hasVal) + new (storage.buffer) T(*O); + } -#if LLVM_USE_RVALUE_REFERENCES - Optional(T &&y) : x(std::forward<T>(y)), hasVal(true) {} +#if LLVM_HAS_RVALUE_REFERENCES + Optional(T &&y) : hasVal(true) { + new (storage.buffer) T(std::forward<T>(y)); + } + Optional(Optional<T> &&O) : hasVal(O) { + if (O) { + new (storage.buffer) T(std::move(*O)); + O.reset(); + } + } + Optional &operator=(T &&y) { + if (hasVal) + **this = std::move(y); + else { + new (storage.buffer) T(std::move(y)); + hasVal = true; + } + return *this; + } + Optional &operator=(Optional &&O) { + if (!O) + reset(); + else { + *this = std::move(*O); + O.reset(); + } + return *this; + } #endif static inline Optional create(const T* y) { return y ? Optional(*y) : Optional(); } + // FIXME: these assignments (& the equivalent const T&/const Optional& ctors) + // could be made more efficient by passing by value, possibly unifying them + // with the rvalue versions above - but this could place a different set of + // requirements (notably: the existence of a default ctor) when implemented + // in that way. Careful SFINAE to avoid such pitfalls would be required. Optional &operator=(const T &y) { - x = y; - hasVal = true; + if (hasVal) + **this = y; + else { + new (storage.buffer) T(y); + hasVal = true; + } return *this; } - - const T* getPointer() const { assert(hasVal); return &x; } - const T& getValue() const { assert(hasVal); return x; } - operator bool() const { return hasVal; } - bool hasValue() const { return hasVal; } - const T* operator->() const { return getPointer(); } - const T& operator*() const { assert(hasVal); return x; } -}; + Optional &operator=(const Optional &O) { + if (!O) + reset(); + else + *this = *O; + return *this; + } -template<typename T> struct simplify_type; + void reset() { + if (hasVal) { + (**this).~T(); + hasVal = false; + } + } -template <typename T> -struct simplify_type<const Optional<T> > { - typedef const T* SimpleType; - static SimpleType getSimplifiedValue(const Optional<T> &Val) { - return Val.getPointer(); + ~Optional() { + reset(); } + + const T* getPointer() const { assert(hasVal); return reinterpret_cast<const T*>(storage.buffer); } + T* getPointer() { assert(hasVal); return reinterpret_cast<T*>(storage.buffer); } + const T& getValue() const LLVM_LVALUE_FUNCTION { assert(hasVal); return *getPointer(); } + T& getValue() LLVM_LVALUE_FUNCTION { assert(hasVal); return *getPointer(); } + + LLVM_EXPLICIT operator bool() const { return hasVal; } + bool hasValue() const { return hasVal; } + const T* operator->() const { return getPointer(); } + T* operator->() { return getPointer(); } + const T& operator*() const LLVM_LVALUE_FUNCTION { assert(hasVal); return *getPointer(); } + T& operator*() LLVM_LVALUE_FUNCTION { assert(hasVal); return *getPointer(); } + +#if LLVM_HAS_RVALUE_REFERENCE_THIS + T&& getValue() && { assert(hasVal); return std::move(*getPointer()); } + T&& operator*() && { assert(hasVal); return std::move(*getPointer()); } +#endif }; -template <typename T> -struct simplify_type<Optional<T> > - : public simplify_type<const Optional<T> > {}; +template <typename T> struct isPodLike; +template <typename T> struct isPodLike<Optional<T> > { + // An Optional<T> is pod-like if T is. + static const bool value = isPodLike<T>::value; +}; /// \brief Poison comparison between two \c Optional objects. Clients needs to /// explicitly compare the underlying values and account for empty \c Optional /// objects. /// -/// This routine will never be defined. It returns \c void to help diagnose +/// This routine will never be defined. It returns \c void to help diagnose /// errors at compile time. template<typename T, typename U> void operator==(const Optional<T> &X, const Optional<U> &Y); @@ -83,7 +147,7 @@ void operator==(const Optional<T> &X, const Optional<U> &Y); /// explicitly compare the underlying values and account for empty \c Optional /// objects. /// -/// This routine will never be defined. It returns \c void to help diagnose +/// This routine will never be defined. It returns \c void to help diagnose /// errors at compile time. template<typename T, typename U> void operator!=(const Optional<T> &X, const Optional<U> &Y); @@ -92,7 +156,7 @@ void operator!=(const Optional<T> &X, const Optional<U> &Y); /// explicitly compare the underlying values and account for empty \c Optional /// objects. /// -/// This routine will never be defined. It returns \c void to help diagnose +/// This routine will never be defined. It returns \c void to help diagnose /// errors at compile time. template<typename T, typename U> void operator<(const Optional<T> &X, const Optional<U> &Y); @@ -101,7 +165,7 @@ void operator<(const Optional<T> &X, const Optional<U> &Y); /// explicitly compare the underlying values and account for empty \c Optional /// objects. /// -/// This routine will never be defined. It returns \c void to help diagnose +/// This routine will never be defined. It returns \c void to help diagnose /// errors at compile time. template<typename T, typename U> void operator<=(const Optional<T> &X, const Optional<U> &Y); @@ -110,7 +174,7 @@ void operator<=(const Optional<T> &X, const Optional<U> &Y); /// explicitly compare the underlying values and account for empty \c Optional /// objects. /// -/// This routine will never be defined. It returns \c void to help diagnose +/// This routine will never be defined. It returns \c void to help diagnose /// errors at compile time. template<typename T, typename U> void operator>=(const Optional<T> &X, const Optional<U> &Y); @@ -119,7 +183,7 @@ void operator>=(const Optional<T> &X, const Optional<U> &Y); /// explicitly compare the underlying values and account for empty \c Optional /// objects. /// -/// This routine will never be defined. It returns \c void to help diagnose +/// This routine will never be defined. It returns \c void to help diagnose /// errors at compile time. template<typename T, typename U> void operator>(const Optional<T> &X, const Optional<U> &Y); diff --git a/include/llvm/ADT/OwningPtr.h b/include/llvm/ADT/OwningPtr.h index 05bcd40..86f9fee 100644 --- a/include/llvm/ADT/OwningPtr.h +++ b/include/llvm/ADT/OwningPtr.h @@ -11,8 +11,8 @@ // //===----------------------------------------------------------------------===// -#ifndef LLVM_ADT_OWNING_PTR_H -#define LLVM_ADT_OWNING_PTR_H +#ifndef LLVM_ADT_OWNINGPTR_H +#define LLVM_ADT_OWNINGPTR_H #include "llvm/Support/Compiler.h" #include <cassert> @@ -32,7 +32,7 @@ class OwningPtr { public: explicit OwningPtr(T *P = 0) : Ptr(P) {} -#if LLVM_USE_RVALUE_REFERENCES +#if LLVM_HAS_RVALUE_REFERENCES OwningPtr(OwningPtr &&Other) : Ptr(Other.take()) {} OwningPtr &operator=(OwningPtr &&Other) { @@ -95,7 +95,7 @@ class OwningArrayPtr { public: explicit OwningArrayPtr(T *P = 0) : Ptr(P) {} -#if LLVM_USE_RVALUE_REFERENCES +#if LLVM_HAS_RVALUE_REFERENCES OwningArrayPtr(OwningArrayPtr &&Other) : Ptr(Other.take()) {} OwningArrayPtr &operator=(OwningArrayPtr &&Other) { diff --git a/include/llvm/ADT/PointerIntPair.h b/include/llvm/ADT/PointerIntPair.h index 71c379b..cce2efb 100644 --- a/include/llvm/ADT/PointerIntPair.h +++ b/include/llvm/ADT/PointerIntPair.h @@ -57,11 +57,13 @@ class PointerIntPair { }; public: PointerIntPair() : Value(0) {} - PointerIntPair(PointerTy Ptr, IntType Int) : Value(0) { + PointerIntPair(PointerTy Ptr, IntType Int) { assert(IntBits <= PtrTraits::NumLowBitsAvailable && "PointerIntPair formed with integer size too large for pointer"); - setPointer(Ptr); - setInt(Int); + setPointerAndInt(Ptr, Int); + } + explicit PointerIntPair(PointerTy Ptr) { + initWithPointer(Ptr); } PointerTy getPointer() const { @@ -91,6 +93,25 @@ public: Value |= IntVal << IntShift; // Set new integer. } + void initWithPointer(PointerTy Ptr) { + intptr_t PtrVal + = reinterpret_cast<intptr_t>(PtrTraits::getAsVoidPointer(Ptr)); + assert((PtrVal & ((1 << PtrTraits::NumLowBitsAvailable)-1)) == 0 && + "Pointer is not sufficiently aligned"); + Value = PtrVal; + } + + void setPointerAndInt(PointerTy Ptr, IntType Int) { + intptr_t PtrVal + = reinterpret_cast<intptr_t>(PtrTraits::getAsVoidPointer(Ptr)); + assert((PtrVal & ((1 << PtrTraits::NumLowBitsAvailable)-1)) == 0 && + "Pointer is not sufficiently aligned"); + intptr_t IntVal = Int; + assert(IntVal < (1 << IntBits) && "Integer too large for field"); + + Value = PtrVal | (IntVal << IntShift); + } + PointerTy const *getAddrOfPointer() const { return const_cast<PointerIntPair *>(this)->getAddrOfPointer(); } diff --git a/include/llvm/ADT/PointerUnion.h b/include/llvm/ADT/PointerUnion.h index a9e86d2..f42515a 100644 --- a/include/llvm/ADT/PointerUnion.h +++ b/include/llvm/ADT/PointerUnion.h @@ -95,15 +95,11 @@ namespace llvm { public: PointerUnion() {} - PointerUnion(PT1 V) { - Val.setPointer( - const_cast<void *>(PointerLikeTypeTraits<PT1>::getAsVoidPointer(V))); - Val.setInt(0); + PointerUnion(PT1 V) : Val( + const_cast<void *>(PointerLikeTypeTraits<PT1>::getAsVoidPointer(V))) { } - PointerUnion(PT2 V) { - Val.setPointer( - const_cast<void *>(PointerLikeTypeTraits<PT2>::getAsVoidPointer(V))); - Val.setInt(1); + PointerUnion(PT2 V) : Val( + const_cast<void *>(PointerLikeTypeTraits<PT2>::getAsVoidPointer(V)), 1) { } /// isNull - Return true if the pointer held in the union is null, @@ -160,15 +156,14 @@ namespace llvm { /// Assignment operators - Allow assigning into this union from either /// pointer type, setting the discriminator to remember what it came from. const PointerUnion &operator=(const PT1 &RHS) { - Val.setPointer( + Val.initWithPointer( const_cast<void *>(PointerLikeTypeTraits<PT1>::getAsVoidPointer(RHS))); - Val.setInt(0); return *this; } const PointerUnion &operator=(const PT2 &RHS) { - Val.setPointer( - const_cast<void *>(PointerLikeTypeTraits<PT2>::getAsVoidPointer(RHS))); - Val.setInt(1); + Val.setPointerAndInt( + const_cast<void *>(PointerLikeTypeTraits<PT2>::getAsVoidPointer(RHS)), + 1); return *this; } diff --git a/include/llvm/ADT/PostOrderIterator.h b/include/llvm/ADT/PostOrderIterator.h index 7f6350e..59fa3f3 100644 --- a/include/llvm/ADT/PostOrderIterator.h +++ b/include/llvm/ADT/PostOrderIterator.h @@ -260,7 +260,7 @@ class ReversePostOrderTraversal { typedef typename GT::NodeType NodeType; std::vector<NodeType*> Blocks; // Block list in normal PO order inline void Initialize(NodeType *BB) { - copy(po_begin(BB), po_end(BB), back_inserter(Blocks)); + std::copy(po_begin(BB), po_end(BB), std::back_inserter(Blocks)); } public: typedef typename std::vector<NodeType*>::reverse_iterator rpo_iterator; diff --git a/include/llvm/ADT/PriorityQueue.h b/include/llvm/ADT/PriorityQueue.h index bf8a687..827d0b3 100644 --- a/include/llvm/ADT/PriorityQueue.h +++ b/include/llvm/ADT/PriorityQueue.h @@ -11,8 +11,8 @@ // //===----------------------------------------------------------------------===// -#ifndef LLVM_ADT_PRIORITY_QUEUE_H -#define LLVM_ADT_PRIORITY_QUEUE_H +#ifndef LLVM_ADT_PRIORITYQUEUE_H +#define LLVM_ADT_PRIORITYQUEUE_H #include <algorithm> #include <queue> diff --git a/include/llvm/ADT/SCCIterator.h b/include/llvm/ADT/SCCIterator.h index 48436c6..8ce4fd5 100644 --- a/include/llvm/ADT/SCCIterator.h +++ b/include/llvm/ADT/SCCIterator.h @@ -21,8 +21,8 @@ #ifndef LLVM_ADT_SCCITERATOR_H #define LLVM_ADT_SCCITERATOR_H -#include "llvm/ADT/GraphTraits.h" #include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/GraphTraits.h" #include <vector> namespace llvm { diff --git a/include/llvm/ADT/STLExtras.h b/include/llvm/ADT/STLExtras.h index aee500d..dacda36 100644 --- a/include/llvm/ADT/STLExtras.h +++ b/include/llvm/ADT/STLExtras.h @@ -246,10 +246,10 @@ inline int array_pod_sort_comparator(const void *P1, const void *P2) { return 0; } -/// get_array_pad_sort_comparator - This is an internal helper function used to +/// get_array_pod_sort_comparator - This is an internal helper function used to /// get type deduction of T right. template<typename T> -inline int (*get_array_pad_sort_comparator(const T &)) +inline int (*get_array_pod_sort_comparator(const T &)) (const void*, const void*) { return array_pod_sort_comparator<T>; } @@ -274,7 +274,7 @@ inline void array_pod_sort(IteratorTy Start, IteratorTy End) { // Don't dereference start iterator of empty sequence. if (Start == End) return; qsort(&*Start, End-Start, sizeof(*Start), - get_array_pad_sort_comparator(*Start)); + get_array_pod_sort_comparator(*Start)); } template<class IteratorTy> diff --git a/include/llvm/ADT/SmallBitVector.h b/include/llvm/ADT/SmallBitVector.h index a9cd54e..652492a 100644 --- a/include/llvm/ADT/SmallBitVector.h +++ b/include/llvm/ADT/SmallBitVector.h @@ -153,7 +153,7 @@ public: switchToLarge(new BitVector(*RHS.getPointer())); } -#if LLVM_USE_RVALUE_REFERENCES +#if LLVM_HAS_RVALUE_REFERENCES SmallBitVector(SmallBitVector &&RHS) : X(RHS.X) { RHS.X = 1; } @@ -178,9 +178,9 @@ public: unsigned count() const { if (isSmall()) { uintptr_t Bits = getSmallBits(); - if (sizeof(uintptr_t) * CHAR_BIT == 32) + if (NumBaseBits == 32) return CountPopulation_32(Bits); - if (sizeof(uintptr_t) * CHAR_BIT == 64) + if (NumBaseBits == 64) return CountPopulation_64(Bits); llvm_unreachable("Unsupported!"); } @@ -215,9 +215,9 @@ public: uintptr_t Bits = getSmallBits(); if (Bits == 0) return -1; - if (sizeof(uintptr_t) * CHAR_BIT == 32) + if (NumBaseBits == 32) return CountTrailingZeros_32(Bits); - if (sizeof(uintptr_t) * CHAR_BIT == 64) + if (NumBaseBits == 64) return CountTrailingZeros_64(Bits); llvm_unreachable("Unsupported!"); } @@ -233,9 +233,9 @@ public: Bits &= ~uintptr_t(0) << (Prev + 1); if (Bits == 0 || Prev + 1 >= getSmallSize()) return -1; - if (sizeof(uintptr_t) * CHAR_BIT == 32) + if (NumBaseBits == 32) return CountTrailingZeros_32(Bits); - if (sizeof(uintptr_t) * CHAR_BIT == 64) + if (NumBaseBits == 64) return CountTrailingZeros_64(Bits); llvm_unreachable("Unsupported!"); } @@ -472,7 +472,7 @@ public: return *this; } -#if LLVM_USE_RVALUE_REFERENCES +#if LLVM_HAS_RVALUE_REFERENCES const SmallBitVector &operator=(SmallBitVector &&RHS) { if (this != &RHS) { clear(); diff --git a/include/llvm/ADT/SmallPtrSet.h b/include/llvm/ADT/SmallPtrSet.h index 3bb8830..8c73041 100644 --- a/include/llvm/ADT/SmallPtrSet.h +++ b/include/llvm/ADT/SmallPtrSet.h @@ -54,8 +54,6 @@ protected: /// then the set is in 'small mode'. const void **CurArray; /// CurArraySize - The allocated size of CurArray, always a power of two. - /// Note that CurArray points to an array that has CurArraySize+1 elements in - /// it, so that the end iterator actually points to valid memory. unsigned CurArraySize; // If small, this is # elts allocated consecutively @@ -68,9 +66,6 @@ protected: SmallArray(SmallStorage), CurArray(SmallStorage), CurArraySize(SmallSize) { assert(SmallSize && (SmallSize & (SmallSize-1)) == 0 && "Initial size must be a power of two!"); - // The end pointer, always valid, is set to a valid element to help the - // iterator. - CurArray[SmallSize] = 0; clear(); } ~SmallPtrSetImpl(); @@ -147,9 +142,11 @@ protected: class SmallPtrSetIteratorImpl { protected: const void *const *Bucket; + const void *const *End; public: - explicit SmallPtrSetIteratorImpl(const void *const *BP) : Bucket(BP) { - AdvanceIfNotValid(); + explicit SmallPtrSetIteratorImpl(const void *const *BP, const void*const *E) + : Bucket(BP), End(E) { + AdvanceIfNotValid(); } bool operator==(const SmallPtrSetIteratorImpl &RHS) const { @@ -164,8 +161,10 @@ protected: /// that is. This is guaranteed to stop because the end() bucket is marked /// valid. void AdvanceIfNotValid() { - while (*Bucket == SmallPtrSetImpl::getEmptyMarker() || - *Bucket == SmallPtrSetImpl::getTombstoneMarker()) + assert(Bucket <= End); + while (Bucket != End && + (*Bucket == SmallPtrSetImpl::getEmptyMarker() || + *Bucket == SmallPtrSetImpl::getTombstoneMarker())) ++Bucket; } }; @@ -182,12 +181,13 @@ public: typedef std::ptrdiff_t difference_type; typedef std::forward_iterator_tag iterator_category; - explicit SmallPtrSetIterator(const void *const *BP) - : SmallPtrSetIteratorImpl(BP) {} + explicit SmallPtrSetIterator(const void *const *BP, const void *const *E) + : SmallPtrSetIteratorImpl(BP, E) {} // Most methods provided by baseclass. const PtrTy operator*() const { + assert(Bucket < End); return PtrTraits::getFromVoidPointer(const_cast<void*>(*Bucket)); } @@ -236,9 +236,8 @@ template<class PtrType, unsigned SmallSize> class SmallPtrSet : public SmallPtrSetImpl { // Make sure that SmallSize is a power of two, round up if not. enum { SmallSizePowTwo = RoundUpToPowerOfTwo<SmallSize>::Val }; - /// SmallStorage - Fixed size storage used in 'small mode'. The extra element - /// ensures that the end iterator actually points to valid memory. - const void *SmallStorage[SmallSizePowTwo+1]; + /// SmallStorage - Fixed size storage used in 'small mode'. + const void *SmallStorage[SmallSizePowTwo]; typedef PointerLikeTypeTraits<PtrType> PtrTraits; public: SmallPtrSet() : SmallPtrSetImpl(SmallStorage, SmallSizePowTwo) {} @@ -275,10 +274,10 @@ public: typedef SmallPtrSetIterator<PtrType> iterator; typedef SmallPtrSetIterator<PtrType> const_iterator; inline iterator begin() const { - return iterator(CurArray); + return iterator(CurArray, CurArray+CurArraySize); } inline iterator end() const { - return iterator(CurArray+CurArraySize); + return iterator(CurArray+CurArraySize, CurArray+CurArraySize); } // Allow assignment from any smallptrset with the same element type even if it diff --git a/include/llvm/ADT/SmallSet.h b/include/llvm/ADT/SmallSet.h index cd117f5..5dfe924 100644 --- a/include/llvm/ADT/SmallSet.h +++ b/include/llvm/ADT/SmallSet.h @@ -14,8 +14,8 @@ #ifndef LLVM_ADT_SMALLSET_H #define LLVM_ADT_SMALLSET_H -#include "llvm/ADT/SmallVector.h" #include "llvm/ADT/SmallPtrSet.h" +#include "llvm/ADT/SmallVector.h" #include <set> namespace llvm { @@ -55,6 +55,7 @@ public: } /// insert - Insert an element into the set if it isn't already there. + /// Returns true if the element is inserted (it was not in the set before). bool insert(const T &V) { if (!isSmall()) return Set.insert(V).second; diff --git a/include/llvm/ADT/SmallString.h b/include/llvm/ADT/SmallString.h index 8da99d1..2cfb5b9 100644 --- a/include/llvm/ADT/SmallString.h +++ b/include/llvm/ADT/SmallString.h @@ -77,7 +77,7 @@ public: void append(in_iter S, in_iter E) { SmallVectorImpl<char>::append(S, E); } - + void append(size_t NumInputs, char Elt) { SmallVectorImpl<char>::append(NumInputs, Elt); } diff --git a/include/llvm/ADT/SmallVector.h b/include/llvm/ADT/SmallVector.h index 6e0fd94..7ba0a71 100644 --- a/include/llvm/ADT/SmallVector.h +++ b/include/llvm/ADT/SmallVector.h @@ -16,6 +16,7 @@ #include "llvm/Support/AlignOf.h" #include "llvm/Support/Compiler.h" +#include "llvm/Support/MathExtras.h" #include "llvm/Support/type_traits.h" #include <algorithm> #include <cassert> @@ -145,16 +146,20 @@ public: } reference front() { + assert(!empty()); return begin()[0]; } const_reference front() const { + assert(!empty()); return begin()[0]; } reference back() { + assert(!empty()); return end()[-1]; } const_reference back() const { + assert(!empty()); return end()[-1]; } }; @@ -178,7 +183,7 @@ protected: /// std::move, but not all stdlibs actually provide that. template<typename It1, typename It2> static It2 move(It1 I, It1 E, It2 Dest) { -#if LLVM_USE_RVALUE_REFERENCES +#if LLVM_HAS_RVALUE_REFERENCES for (; I != E; ++I, ++Dest) *Dest = ::std::move(*I); return Dest; @@ -193,7 +198,7 @@ protected: /// std::move_backward, but not all stdlibs actually provide that. template<typename It1, typename It2> static It2 move_backward(It1 I, It1 E, It2 Dest) { -#if LLVM_USE_RVALUE_REFERENCES +#if LLVM_HAS_RVALUE_REFERENCES while (I != E) *--Dest = ::std::move(*--E); return Dest; @@ -206,7 +211,7 @@ protected: /// memory starting with "Dest", constructing elements as needed. template<typename It1, typename It2> static void uninitialized_move(It1 I, It1 E, It2 Dest) { -#if LLVM_USE_RVALUE_REFERENCES +#if LLVM_HAS_RVALUE_REFERENCES for (; I != E; ++I, ++Dest) ::new ((void*) &*Dest) T(::std::move(*I)); #else @@ -239,7 +244,7 @@ public: goto Retry; } -#if LLVM_USE_RVALUE_REFERENCES +#if LLVM_HAS_RVALUE_REFERENCES void push_back(T &&Elt) { if (this->EndX < this->CapacityX) { Retry: @@ -263,7 +268,8 @@ template <typename T, bool isPodLike> void SmallVectorTemplateBase<T, isPodLike>::grow(size_t MinSize) { size_t CurCapacity = this->capacity(); size_t CurSize = this->size(); - size_t NewCapacity = 2*CurCapacity + 1; // Always grow, even from zero. + // Always grow, even from zero. + size_t NewCapacity = size_t(NextPowerOf2(CurCapacity+2)); if (NewCapacity < MinSize) NewCapacity = MinSize; T *NewElts = static_cast<T*>(malloc(NewCapacity*sizeof(T))); @@ -365,7 +371,7 @@ template <typename T> class SmallVectorImpl : public SmallVectorTemplateBase<T, isPodLike<T>::value> { typedef SmallVectorTemplateBase<T, isPodLike<T>::value > SuperClass; - SmallVectorImpl(const SmallVectorImpl&); // DISABLED. + SmallVectorImpl(const SmallVectorImpl&) LLVM_DELETED_FUNCTION; public: typedef typename SuperClass::iterator iterator; typedef typename SuperClass::size_type size_type; @@ -422,7 +428,7 @@ public: } T pop_back_val() { -#if LLVM_USE_RVALUE_REFERENCES +#if LLVM_HAS_RVALUE_REFERENCES T Result = ::std::move(this->back()); #else T Result = this->back(); @@ -495,7 +501,7 @@ public: return(N); } -#if LLVM_USE_RVALUE_REFERENCES +#if LLVM_HAS_RVALUE_REFERENCES iterator insert(iterator I, T &&Elt) { if (I == this->end()) { // Important special case for empty vector. this->push_back(::std::move(Elt)); @@ -667,7 +673,7 @@ public: SmallVectorImpl &operator=(const SmallVectorImpl &RHS); -#if LLVM_USE_RVALUE_REFERENCES +#if LLVM_HAS_RVALUE_REFERENCES SmallVectorImpl &operator=(SmallVectorImpl &&RHS); #endif @@ -787,7 +793,7 @@ SmallVectorImpl<T> &SmallVectorImpl<T>:: return *this; } -#if LLVM_USE_RVALUE_REFERENCES +#if LLVM_HAS_RVALUE_REFERENCES template <typename T> SmallVectorImpl<T> &SmallVectorImpl<T>::operator=(SmallVectorImpl<T> &&RHS) { // Avoid self-assignment. @@ -898,7 +904,7 @@ public: return *this; } -#if LLVM_USE_RVALUE_REFERENCES +#if LLVM_HAS_RVALUE_REFERENCES SmallVector(SmallVector &&RHS) : SmallVectorImpl<T>(N) { if (!RHS.empty()) SmallVectorImpl<T>::operator=(::std::move(RHS)); diff --git a/include/llvm/ADT/SparseMultiSet.h b/include/llvm/ADT/SparseMultiSet.h new file mode 100644 index 0000000..7f2a6f7 --- /dev/null +++ b/include/llvm/ADT/SparseMultiSet.h @@ -0,0 +1,526 @@ +//===--- llvm/ADT/SparseMultiSet.h - Sparse multiset ------------*- 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 SparseMultiSet class, which adds multiset behavior to +// the SparseSet. +// +// A sparse multiset holds a small number of objects identified by integer keys +// from a moderately sized universe. The sparse multiset uses more memory than +// other containers in order to provide faster operations. Any key can map to +// multiple values. A SparseMultiSetNode class is provided, which serves as a +// convenient base class for the contents of a SparseMultiSet. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_ADT_SPARSEMULTISET_H +#define LLVM_ADT_SPARSEMULTISET_H + +#include "llvm/ADT/SparseSet.h" + +namespace llvm { + +/// Fast multiset implementation for objects that can be identified by small +/// unsigned keys. +/// +/// SparseMultiSet 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, SparseMultiSet provides constant-time +/// fast clear() 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. Iteration order is the +/// insertion order. Iteration is only provided over elements of equivalent +/// keys, but iterators are bidirectional. +/// +/// Compared to BitVector, SparseMultiSet<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. +/// +/// SparseMultiSet 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 up to 3 cache lines, but the +/// sparse array uses 4 x Universe bytes. +/// +/// When SparseT is uint8_t (the default), find() touches up to 3+[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. +/// +/// Multiset behavior is provided by providing doubly linked lists for values +/// that are inlined in the dense vector. SparseMultiSet is a good choice when +/// one desires a growable number of entries per key, as it will retain the +/// SparseSet algorithmic properties despite being growable. Thus, it is often a +/// better choice than a SparseSet of growable containers or a vector of +/// vectors. SparseMultiSet also keeps iterators valid after erasure (provided +/// the iterators don't point to the element erased), allowing for more +/// intuitive and fast removal. +/// +/// @tparam ValueT The type of objects in the set. +/// @tparam KeyFunctorT A functor that computes an unsigned index from KeyT. +/// @tparam SparseT An unsigned integer type. See above. +/// +template<typename ValueT, + typename KeyFunctorT = llvm::identity<unsigned>, + typename SparseT = uint8_t> +class SparseMultiSet { + /// The actual data that's stored, as a doubly-linked list implemented via + /// indices into the DenseVector. The doubly linked list is implemented + /// circular in Prev indices, and INVALID-terminated in Next indices. This + /// provides efficient access to list tails. These nodes can also be + /// tombstones, in which case they are actually nodes in a single-linked + /// freelist of recyclable slots. + struct SMSNode { + static const unsigned INVALID = ~0U; + + ValueT Data; + unsigned Prev; + unsigned Next; + + SMSNode(ValueT D, unsigned P, unsigned N) : Data(D), Prev(P), Next(N) { } + + /// List tails have invalid Nexts. + bool isTail() const { + return Next == INVALID; + } + + /// Whether this node is a tombstone node, and thus is in our freelist. + bool isTombstone() const { + return Prev == INVALID; + } + + /// Since the list is circular in Prev, all non-tombstone nodes have a valid + /// Prev. + bool isValid() const { return Prev != INVALID; } + }; + + typedef typename KeyFunctorT::argument_type KeyT; + typedef SmallVector<SMSNode, 8> DenseT; + DenseT Dense; + SparseT *Sparse; + unsigned Universe; + KeyFunctorT KeyIndexOf; + SparseSetValFunctor<KeyT, ValueT, KeyFunctorT> ValIndexOf; + + /// We have a built-in recycler for reusing tombstone slots. This recycler + /// puts a singly-linked free list into tombstone slots, allowing us quick + /// erasure, iterator preservation, and dense size. + unsigned FreelistIdx; + unsigned NumFree; + + unsigned sparseIndex(const ValueT &Val) const { + assert(ValIndexOf(Val) < Universe && + "Invalid key in set. Did object mutate?"); + return ValIndexOf(Val); + } + unsigned sparseIndex(const SMSNode &N) const { return sparseIndex(N.Data); } + + // Disable copy construction and assignment. + // This data structure is not meant to be used that way. + SparseMultiSet(const SparseMultiSet&) LLVM_DELETED_FUNCTION; + SparseMultiSet &operator=(const SparseMultiSet&) LLVM_DELETED_FUNCTION; + + /// Whether the given entry is the head of the list. List heads's previous + /// pointers are to the tail of the list, allowing for efficient access to the + /// list tail. D must be a valid entry node. + bool isHead(const SMSNode &D) const { + assert(D.isValid() && "Invalid node for head"); + return Dense[D.Prev].isTail(); + } + + /// Whether the given entry is a singleton entry, i.e. the only entry with + /// that key. + bool isSingleton(const SMSNode &N) const { + assert(N.isValid() && "Invalid node for singleton"); + // Is N its own predecessor? + return &Dense[N.Prev] == &N; + } + + /// Add in the given SMSNode. Uses a free entry in our freelist if + /// available. Returns the index of the added node. + unsigned addValue(const ValueT& V, unsigned Prev, unsigned Next) { + if (NumFree == 0) { + Dense.push_back(SMSNode(V, Prev, Next)); + return Dense.size() - 1; + } + + // Peel off a free slot + unsigned Idx = FreelistIdx; + unsigned NextFree = Dense[Idx].Next; + assert(Dense[Idx].isTombstone() && "Non-tombstone free?"); + + Dense[Idx] = SMSNode(V, Prev, Next); + FreelistIdx = NextFree; + --NumFree; + return Idx; + } + + /// Make the current index a new tombstone. Pushes it onto the freelist. + void makeTombstone(unsigned Idx) { + Dense[Idx].Prev = SMSNode::INVALID; + Dense[Idx].Next = FreelistIdx; + FreelistIdx = Idx; + ++NumFree; + } + +public: + typedef ValueT value_type; + typedef ValueT &reference; + typedef const ValueT &const_reference; + typedef ValueT *pointer; + typedef const ValueT *const_pointer; + + SparseMultiSet() + : Sparse(0), Universe(0), FreelistIdx(SMSNode::INVALID), NumFree(0) { } + + ~SparseMultiSet() { free(Sparse); } + + /// 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; + } + + /// Our iterators are iterators over the collection of objects that share a + /// key. + template<typename SMSPtrTy> + class iterator_base : public std::iterator<std::bidirectional_iterator_tag, + ValueT> { + friend class SparseMultiSet; + SMSPtrTy SMS; + unsigned Idx; + unsigned SparseIdx; + + iterator_base(SMSPtrTy P, unsigned I, unsigned SI) + : SMS(P), Idx(I), SparseIdx(SI) { } + + /// Whether our iterator has fallen outside our dense vector. + bool isEnd() const { + if (Idx == SMSNode::INVALID) + return true; + + assert(Idx < SMS->Dense.size() && "Out of range, non-INVALID Idx?"); + return false; + } + + /// Whether our iterator is properly keyed, i.e. the SparseIdx is valid + bool isKeyed() const { return SparseIdx < SMS->Universe; } + + unsigned Prev() const { return SMS->Dense[Idx].Prev; } + unsigned Next() const { return SMS->Dense[Idx].Next; } + + void setPrev(unsigned P) { SMS->Dense[Idx].Prev = P; } + void setNext(unsigned N) { SMS->Dense[Idx].Next = N; } + + public: + typedef std::iterator<std::bidirectional_iterator_tag, ValueT> super; + typedef typename super::value_type value_type; + typedef typename super::difference_type difference_type; + typedef typename super::pointer pointer; + typedef typename super::reference reference; + + iterator_base(const iterator_base &RHS) + : SMS(RHS.SMS), Idx(RHS.Idx), SparseIdx(RHS.SparseIdx) { } + + const iterator_base &operator=(const iterator_base &RHS) { + SMS = RHS.SMS; + Idx = RHS.Idx; + SparseIdx = RHS.SparseIdx; + return *this; + } + + reference operator*() const { + assert(isKeyed() && SMS->sparseIndex(SMS->Dense[Idx].Data) == SparseIdx && + "Dereferencing iterator of invalid key or index"); + + return SMS->Dense[Idx].Data; + } + pointer operator->() const { return &operator*(); } + + /// Comparison operators + bool operator==(const iterator_base &RHS) const { + // end compares equal + if (SMS == RHS.SMS && Idx == RHS.Idx) { + assert((isEnd() || SparseIdx == RHS.SparseIdx) && + "Same dense entry, but different keys?"); + return true; + } + + return false; + } + + bool operator!=(const iterator_base &RHS) const { + return !operator==(RHS); + } + + /// Increment and decrement operators + iterator_base &operator--() { // predecrement - Back up + assert(isKeyed() && "Decrementing an invalid iterator"); + assert((isEnd() || !SMS->isHead(SMS->Dense[Idx])) && + "Decrementing head of list"); + + // If we're at the end, then issue a new find() + if (isEnd()) + Idx = SMS->findIndex(SparseIdx).Prev(); + else + Idx = Prev(); + + return *this; + } + iterator_base &operator++() { // preincrement - Advance + assert(!isEnd() && isKeyed() && "Incrementing an invalid/end iterator"); + Idx = Next(); + return *this; + } + iterator_base operator--(int) { // postdecrement + iterator_base I(*this); + --*this; + return I; + } + iterator_base operator++(int) { // postincrement + iterator_base I(*this); + ++*this; + return I; + } + }; + typedef iterator_base<SparseMultiSet *> iterator; + typedef iterator_base<const SparseMultiSet *> const_iterator; + + // Convenience types + typedef std::pair<iterator, iterator> RangePair; + + /// Returns an iterator past this container. Note that such an iterator cannot + /// be decremented, but will compare equal to other end iterators. + iterator end() { return iterator(this, SMSNode::INVALID, SMSNode::INVALID); } + const_iterator end() const { + return const_iterator(this, SMSNode::INVALID, SMSNode::INVALID); + } + + /// Returns true if the set is empty. + /// + /// This is not the same as BitVector::empty(). + /// + bool empty() const { return size() == 0; } + + /// 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 { + assert(NumFree <= Dense.size() && "Out-of-bounds free entries"); + return Dense.size() - NumFree; + } + + /// Clears the set. This is a very fast constant time operation. + /// + void clear() { + // Sparse does not need to be cleared, see find(). + Dense.clear(); + NumFree = 0; + FreelistIdx = SMSNode::INVALID; + } + + /// Find an element by its index. + /// + /// @param Idx A valid index to find. + /// @returns An iterator to the element identified by key, or end(). + /// + iterator findIndex(unsigned Idx) { + assert(Idx < 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[Idx], e = Dense.size(); i < e; i += Stride) { + const unsigned FoundIdx = sparseIndex(Dense[i]); + // Check that we're pointing at the correct entry and that it is the head + // of a valid list. + if (Idx == FoundIdx && Dense[i].isValid() && isHead(Dense[i])) + return iterator(this, i, Idx); + // Stride is 0 when SparseT >= unsigned. We don't need to loop. + if (!Stride) + break; + } + return end(); + } + + /// 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(const KeyT &Key) { + return findIndex(KeyIndexOf(Key)); + } + + const_iterator find(const KeyT &Key) const { + iterator I = const_cast<SparseMultiSet*>(this)->findIndex(KeyIndexOf(Key)); + return const_iterator(I.SMS, I.Idx, KeyIndexOf(Key)); + } + + /// Returns the number of elements identified by Key. This will be linear in + /// the number of elements of that key. + unsigned count(const KeyT &Key) const { + unsigned Ret = 0; + for (const_iterator It = find(Key); It != end(); ++It) + ++Ret; + + return Ret; + } + + /// Returns true if this set contains an element identified by Key. + bool contains(const KeyT &Key) const { + return find(Key) != end(); + } + + /// Return the head and tail of the subset's list, otherwise returns end(). + iterator getHead(const KeyT &Key) { return find(Key); } + iterator getTail(const KeyT &Key) { + iterator I = find(Key); + if (I != end()) + I = iterator(this, I.Prev(), KeyIndexOf(Key)); + return I; + } + + /// The bounds of the range of items sharing Key K. First member is the head + /// of the list, and the second member is a decrementable end iterator for + /// that key. + RangePair equal_range(const KeyT &K) { + iterator B = find(K); + iterator E = iterator(this, SMSNode::INVALID, B.SparseIdx); + return make_pair(B, E); + } + + /// Insert a new element at the tail of the subset list. Returns an iterator + /// to the newly added entry. + iterator insert(const ValueT &Val) { + unsigned Idx = sparseIndex(Val); + iterator I = findIndex(Idx); + + unsigned NodeIdx = addValue(Val, SMSNode::INVALID, SMSNode::INVALID); + + if (I == end()) { + // Make a singleton list + Sparse[Idx] = NodeIdx; + Dense[NodeIdx].Prev = NodeIdx; + return iterator(this, NodeIdx, Idx); + } + + // Stick it at the end. + unsigned HeadIdx = I.Idx; + unsigned TailIdx = I.Prev(); + Dense[TailIdx].Next = NodeIdx; + Dense[HeadIdx].Prev = NodeIdx; + Dense[NodeIdx].Prev = TailIdx; + + return iterator(this, NodeIdx, Idx); + } + + /// Erases an existing element identified by a valid iterator. + /// + /// This invalidates iterators pointing at the same entry, but erase() returns + /// an iterator pointing to the next element in the subset's list. This makes + /// it possible to erase selected elements while iterating over the subset: + /// + /// tie(I, E) = Set.equal_range(Key); + /// while (I != E) + /// if (test(*I)) + /// I = Set.erase(I); + /// else + /// ++I; + /// + /// Note that if the last element in the subset list is erased, this will + /// return an end iterator which can be decremented to get the new tail (if it + /// exists): + /// + /// tie(B, I) = Set.equal_range(Key); + /// for (bool isBegin = B == I; !isBegin; /* empty */) { + /// isBegin = (--I) == B; + /// if (test(I)) + /// break; + /// I = erase(I); + /// } + iterator erase(iterator I) { + assert(I.isKeyed() && !I.isEnd() && !Dense[I.Idx].isTombstone() && + "erasing invalid/end/tombstone iterator"); + + // First, unlink the node from its list. Then swap the node out with the + // dense vector's last entry + iterator NextI = unlink(Dense[I.Idx]); + + // Put in a tombstone. + makeTombstone(I.Idx); + + return NextI; + } + + /// Erase all elements with the given key. This invalidates all + /// iterators of that key. + void eraseAll(const KeyT &K) { + for (iterator I = find(K); I != end(); /* empty */) + I = erase(I); + } + +private: + /// Unlink the node from its list. Returns the next node in the list. + iterator unlink(const SMSNode &N) { + if (isSingleton(N)) { + // Singleton is already unlinked + assert(N.Next == SMSNode::INVALID && "Singleton has next?"); + return iterator(this, SMSNode::INVALID, ValIndexOf(N.Data)); + } + + if (isHead(N)) { + // If we're the head, then update the sparse array and our next. + Sparse[sparseIndex(N)] = N.Next; + Dense[N.Next].Prev = N.Prev; + return iterator(this, N.Next, ValIndexOf(N.Data)); + } + + if (N.isTail()) { + // If we're the tail, then update our head and our previous. + findIndex(sparseIndex(N)).setPrev(N.Prev); + Dense[N.Prev].Next = N.Next; + + // Give back an end iterator that can be decremented + iterator I(this, N.Prev, ValIndexOf(N.Data)); + return ++I; + } + + // Otherwise, just drop us + Dense[N.Next].Prev = N.Prev; + Dense[N.Prev].Next = N.Next; + return iterator(this, N.Next, ValIndexOf(N.Data)); + } +}; + +} // end namespace llvm + +#endif diff --git a/include/llvm/ADT/SparseSet.h b/include/llvm/ADT/SparseSet.h index 063c675..267a340 100644 --- a/include/llvm/ADT/SparseSet.h +++ b/include/llvm/ADT/SparseSet.h @@ -20,8 +20,8 @@ #ifndef LLVM_ADT_SPARSESET_H #define LLVM_ADT_SPARSESET_H -#include "llvm/ADT/SmallVector.h" #include "llvm/ADT/STLExtras.h" +#include "llvm/ADT/SmallVector.h" #include "llvm/Support/DataTypes.h" #include <limits> diff --git a/include/llvm/ADT/Statistic.h b/include/llvm/ADT/Statistic.h index b54d10b..26aac7b 100644 --- a/include/llvm/ADT/Statistic.h +++ b/include/llvm/ADT/Statistic.h @@ -51,7 +51,9 @@ public: // Allow use of this class as the value itself. operator unsigned() const { return Value; } - const Statistic &operator=(unsigned Val) { + +#if !defined(NDEBUG) || defined(LLVM_ENABLE_STATS) + const Statistic &operator=(unsigned Val) { Value = Val; return init(); } @@ -106,6 +108,46 @@ public: return init(); } +#else // Statistics are disabled in release builds. + + const Statistic &operator=(unsigned Val) { + return *this; + } + + const Statistic &operator++() { + return *this; + } + + unsigned operator++(int) { + return 0; + } + + const Statistic &operator--() { + return *this; + } + + unsigned operator--(int) { + return 0; + } + + const Statistic &operator+=(const unsigned &V) { + return *this; + } + + const Statistic &operator-=(const unsigned &V) { + return *this; + } + + const Statistic &operator*=(const unsigned &V) { + return *this; + } + + const Statistic &operator/=(const unsigned &V) { + return *this; + } + +#endif // !defined(NDEBUG) || defined(LLVM_ENABLE_STATS) + protected: Statistic &init() { bool tmp = Initialized; diff --git a/include/llvm/ADT/StringExtras.h b/include/llvm/ADT/StringExtras.h index bf27c43..d2887c5 100644 --- a/include/llvm/ADT/StringExtras.h +++ b/include/llvm/ADT/StringExtras.h @@ -14,8 +14,8 @@ #ifndef LLVM_ADT_STRINGEXTRAS_H #define LLVM_ADT_STRINGEXTRAS_H -#include "llvm/Support/DataTypes.h" #include "llvm/ADT/StringRef.h" +#include "llvm/Support/DataTypes.h" namespace llvm { template<typename T> class SmallVectorImpl; @@ -27,6 +27,17 @@ static inline char hexdigit(unsigned X, bool LowerCase = false) { return X < 10 ? '0' + X : HexChar + X - 10; } +/// Interpret the given character \p C as a hexadecimal digit and return its +/// value. +/// +/// If \p C is not a valid hex digit, -1U is returned. +static inline unsigned hexDigitValue(char C) { + if (C >= '0' && C <= '9') return C-'0'; + if (C >= 'a' && C <= 'f') return C-'a'+10U; + if (C >= 'A' && C <= 'F') return C-'A'+10U; + return -1U; +} + /// utohex_buffer - Emit the specified number into the buffer specified by /// BufferEnd, returning a pointer to the start of the string. This can be used /// like this: (note that the buffer must be large enough to handle any number): diff --git a/include/llvm/ADT/StringMap.h b/include/llvm/ADT/StringMap.h index b4497a2..d01437b 100644 --- a/include/llvm/ADT/StringMap.h +++ b/include/llvm/ADT/StringMap.h @@ -53,7 +53,7 @@ public: class StringMapImpl { protected: // Array of NumBuckets pointers to entries, null pointers are holes. - // TheTable[NumBuckets] contains a sentinel value for easy iteration. Follwed + // TheTable[NumBuckets] contains a sentinel value for easy iteration. Followed // by an array of the actual hash values as unsigned integers. StringMapEntryBase **TheTable; unsigned NumBuckets; @@ -171,7 +171,6 @@ public: return Create(KeyStart, KeyEnd, Allocator, 0); } - /// Create - Create a StringMapEntry with normal malloc/free. template<typename InitType> static StringMapEntry *Create(const char *KeyStart, const char *KeyEnd, @@ -204,7 +203,6 @@ public: return *reinterpret_cast<StringMapEntry*>(Ptr); } - /// Destroy - Destroy this StringMapEntry, releasing memory back to the /// specified allocator. template<typename AllocatorTy> @@ -239,6 +237,10 @@ public: explicit StringMap(AllocatorTy A) : StringMapImpl(static_cast<unsigned>(sizeof(MapEntryTy))), Allocator(A) {} + StringMap(unsigned InitialSize, AllocatorTy A) + : StringMapImpl(InitialSize, static_cast<unsigned>(sizeof(MapEntryTy))), + Allocator(A) {} + StringMap(const StringMap &RHS) : StringMapImpl(static_cast<unsigned>(sizeof(MapEntryTy))) { assert(RHS.empty() && @@ -290,7 +292,7 @@ public: return const_iterator(TheTable+Bucket, true); } - /// lookup - Return the entry for the specified key, or a default + /// lookup - Return the entry for the specified key, or a default /// constructed value if no such entry exists. ValueTy lookup(StringRef Key) const { const_iterator it = find(Key); @@ -336,8 +338,8 @@ public: StringMapEntryBase *&Bucket = TheTable[I]; if (Bucket && Bucket != getTombstoneVal()) { static_cast<MapEntryTy*>(Bucket)->Destroy(Allocator); - Bucket = 0; } + Bucket = 0; } NumItems = 0; @@ -427,7 +429,7 @@ public: return Ptr != RHS.Ptr; } - inline StringMapConstIterator& operator++() { // Preincrement + inline StringMapConstIterator& operator++() { // Preincrement ++Ptr; AdvancePastEmptyBuckets(); return *this; diff --git a/include/llvm/ADT/StringRef.h b/include/llvm/ADT/StringRef.h index 292bde0..224855e 100644 --- a/include/llvm/ADT/StringRef.h +++ b/include/llvm/ADT/StringRef.h @@ -11,7 +11,6 @@ #define LLVM_ADT_STRINGREF_H #include "llvm/Support/type_traits.h" - #include <algorithm> #include <cassert> #include <cstring> @@ -58,14 +57,14 @@ namespace llvm { // integer works around this bug. static size_t min(size_t a, size_t b) { return a < b ? a : b; } static size_t max(size_t a, size_t b) { return a > b ? a : b; } - + // Workaround memcmp issue with null pointers (undefined behavior) // by providing a specialized version static int compareMemory(const char *Lhs, const char *Rhs, size_t Length) { if (Length == 0) { return 0; } return ::memcmp(Lhs,Rhs,Length); } - + public: /// @name Constructors /// @{ @@ -388,7 +387,7 @@ namespace llvm { Start = min(Start, Length); return StringRef(Data + Start, min(N, Length - Start)); } - + /// Return a StringRef equal to 'this' but with the first \p N elements /// dropped. StringRef drop_front(unsigned N = 1) const { @@ -536,7 +535,7 @@ namespace llvm { return LHS.compare(RHS) != -1; } - inline std::string &operator+=(std::string &buffer, llvm::StringRef string) { + inline std::string &operator+=(std::string &buffer, StringRef string) { return buffer.append(string.data(), string.size()); } diff --git a/include/llvm/ADT/StringSet.h b/include/llvm/ADT/StringSet.h index b69a964..7bea577 100644 --- a/include/llvm/ADT/StringSet.h +++ b/include/llvm/ADT/StringSet.h @@ -18,23 +18,25 @@ namespace llvm { - /// StringSet - A wrapper for StringMap that provides set-like - /// functionality. Only insert() and count() methods are used by my - /// code. + /// StringSet - A wrapper for StringMap that provides set-like functionality. template <class AllocatorTy = llvm::MallocAllocator> class StringSet : public llvm::StringMap<char, AllocatorTy> { typedef llvm::StringMap<char, AllocatorTy> base; public: - bool insert(StringRef InLang) { - assert(!InLang.empty()); - const char *KeyStart = InLang.data(); - const char *KeyEnd = KeyStart + InLang.size(); - llvm::StringMapEntry<char> *Entry = llvm::StringMapEntry<char>:: - Create(KeyStart, KeyEnd, base::getAllocator(), '+'); - if (!base::insert(Entry)) { - Entry->Destroy(base::getAllocator()); + + /// insert - Insert the specified key into the set. If the key already + /// exists in the set, return false and ignore the request, otherwise insert + /// it and return true. + bool insert(StringRef Key) { + // Get or create the map entry for the key; if it doesn't exist the value + // type will be default constructed which we use to detect insert. + // + // We use '+' as the sentinel value in the map. + assert(!Key.empty()); + StringMapEntry<char> &Entry = this->GetOrCreateValue(Key); + if (Entry.getValue() == '+') return false; - } + Entry.setValue('+'); return true; } }; diff --git a/include/llvm/ADT/TinyPtrVector.h b/include/llvm/ADT/TinyPtrVector.h index d3d33b8..cc0e7b6 100644 --- a/include/llvm/ADT/TinyPtrVector.h +++ b/include/llvm/ADT/TinyPtrVector.h @@ -70,7 +70,7 @@ public: return *this; } -#if LLVM_USE_RVALUE_REFERENCES +#if LLVM_HAS_RVALUE_REFERENCES TinyPtrVector(TinyPtrVector &&RHS) : Val(RHS.Val) { RHS.Val = (EltTy)0; } diff --git a/include/llvm/ADT/Triple.h b/include/llvm/ADT/Triple.h index 408d70c..8fac222 100644 --- a/include/llvm/ADT/Triple.h +++ b/include/llvm/ADT/Triple.h @@ -44,7 +44,7 @@ public: UnknownArch, arm, // ARM; arm, armv.*, xscale - cellspu, // CellSPU: spu, cellspu + aarch64, // AArch64: aarch64 hexagon, // Hexagon: hexagon mips, // MIPS: mips, mipsallegrex mipsel, // MIPSEL: mipsel, mipsallegrexel @@ -101,8 +101,8 @@ public: Haiku, Minix, RTEMS, - NativeClient, - CNK, // BG/P Compute-Node Kernel + NaCl, // Native Client + CNK, // BG/P Compute-Node Kernel Bitrig, AIX }; @@ -112,6 +112,7 @@ public: GNU, GNUEABI, GNUEABIHF, + GNUX32, EABI, MachO, Android, @@ -296,9 +297,14 @@ public: return getOS() == Triple::Darwin || getOS() == Triple::MacOSX; } + /// Is this an iOS triple. + bool isiOS() const { + return getOS() == Triple::IOS; + } + /// isOSDarwin - Is this a "Darwin" OS (OS X or iOS). bool isOSDarwin() const { - return isMacOSX() || getOS() == Triple::IOS; + return isMacOSX() || isiOS(); } /// \brief Tests for either Cygwin or MinGW OS @@ -311,6 +317,11 @@ public: return getOS() == Triple::Win32 || isOSCygMing(); } + /// \brief Tests whether the OS is NaCl (Native Client) + bool isOSNaCl() const { + return getOS() == Triple::NaCl; + } + /// \brief Tests whether the OS uses the ELF binary format. bool isOSBinFormatELF() const { return !isOSDarwin() && !isOSWindows(); diff --git a/include/llvm/ADT/ValueMap.h b/include/llvm/ADT/ValueMap.h index d23fccf..b4fed7a 100644 --- a/include/llvm/ADT/ValueMap.h +++ b/include/llvm/ADT/ValueMap.h @@ -27,10 +27,9 @@ #define LLVM_ADT_VALUEMAP_H #include "llvm/ADT/DenseMap.h" +#include "llvm/Support/Mutex.h" #include "llvm/Support/ValueHandle.h" #include "llvm/Support/type_traits.h" -#include "llvm/Support/Mutex.h" - #include <iterator> namespace llvm { diff --git a/include/llvm/ADT/VariadicFunction.h b/include/llvm/ADT/VariadicFunction.h index a7f83a6..0497aa7 100644 --- a/include/llvm/ADT/VariadicFunction.h +++ b/include/llvm/ADT/VariadicFunction.h @@ -11,8 +11,8 @@ // //===----------------------------------------------------------------------===// -#ifndef LLVM_ADT_VARIADIC_FUNCTION_H -#define LLVM_ADT_VARIADIC_FUNCTION_H +#ifndef LLVM_ADT_VARIADICFUNCTION_H +#define LLVM_ADT_VARIADICFUNCTION_H #include "llvm/ADT/ArrayRef.h" @@ -328,4 +328,4 @@ struct VariadicFunction3 { } // end namespace llvm -#endif // LLVM_ADT_VARIADIC_FUNCTION_H +#endif // LLVM_ADT_VARIADICFUNCTION_H diff --git a/include/llvm/ADT/ilist.h b/include/llvm/ADT/ilist.h index 7f5cd17..71dab2e 100644 --- a/include/llvm/ADT/ilist.h +++ b/include/llvm/ADT/ilist.h @@ -234,17 +234,17 @@ public: pointer getNodePtrUnchecked() const { return NodePtr; } }; -// do not implement. this is to catch errors when people try to use -// them as random access iterators +// These are to catch errors when people try to use them as random access +// iterators. template<typename T> -void operator-(int, ilist_iterator<T>); +void operator-(int, ilist_iterator<T>) LLVM_DELETED_FUNCTION; template<typename T> -void operator-(ilist_iterator<T>,int); +void operator-(ilist_iterator<T>,int) LLVM_DELETED_FUNCTION; template<typename T> -void operator+(int, ilist_iterator<T>); +void operator+(int, ilist_iterator<T>) LLVM_DELETED_FUNCTION; template<typename T> -void operator+(ilist_iterator<T>,int); +void operator+(ilist_iterator<T>,int) LLVM_DELETED_FUNCTION; // operator!=/operator== - Allow mixed comparisons without dereferencing // the iterator, which could very likely be pointing to end(). @@ -274,12 +274,12 @@ template<typename From> struct simplify_type; template<typename NodeTy> struct simplify_type<ilist_iterator<NodeTy> > { typedef NodeTy* SimpleType; - static SimpleType getSimplifiedValue(const ilist_iterator<NodeTy> &Node) { + static SimpleType getSimplifiedValue(ilist_iterator<NodeTy> &Node) { return &*Node; } }; template<typename NodeTy> struct simplify_type<const ilist_iterator<NodeTy> > { - typedef NodeTy* SimpleType; + typedef /*const*/ NodeTy* SimpleType; static SimpleType getSimplifiedValue(const ilist_iterator<NodeTy> &Node) { return &*Node; @@ -465,6 +465,17 @@ public: return where; } + /// Remove all nodes from the list like clear(), but do not call + /// removeNodeFromList() or deleteNode(). + /// + /// This should only be used immediately before freeing nodes in bulk to + /// avoid traversing the list and bringing all the nodes into cache. + void clearAndLeakNodesUnsafely() { + if (Head) { + Head = getTail(); + this->setPrev(Head, Head); + } + } private: // transfer - The heart of the splice function. Move linked list nodes from @@ -472,6 +483,10 @@ private: // void transfer(iterator position, iplist &L2, iterator first, iterator last) { assert(first != last && "Should be checked by callers"); + // Position cannot be contained in the range to be transferred. + // Check for the most common mistake. + assert(position != first && + "Insertion point can't be one of the transferred nodes"); if (position != last) { // Note: we have to be careful about the case when we move the first node diff --git a/include/llvm/ADT/ilist_node.h b/include/llvm/ADT/ilist_node.h index f008003..0361244 100644 --- a/include/llvm/ADT/ilist_node.h +++ b/include/llvm/ADT/ilist_node.h @@ -12,8 +12,8 @@ // //===----------------------------------------------------------------------===// -#ifndef LLVM_ADT_ILIST_NODE_H -#define LLVM_ADT_ILIST_NODE_H +#ifndef LLVM_ADT_ILISTNODE_H +#define LLVM_ADT_ILISTNODE_H namespace llvm { |
