diff options
Diffstat (limited to 'include/llvm/ADT')
43 files changed, 761 insertions, 378 deletions
diff --git a/include/llvm/ADT/APFloat.h b/include/llvm/ADT/APFloat.h index 5a625a4..93d343a 100644 --- a/include/llvm/ADT/APFloat.h +++ b/include/llvm/ADT/APFloat.h @@ -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 &); @@ -455,14 +456,11 @@ namespace llvm { /* The sign bit of this number. */ unsigned int sign: 1; - - /* For PPCDoubleDouble, we have a second exponent and sign (the second - significand is appended to the first one, although it would be wrong to - regard these as a single number for arithmetic purposes). These fields - are not meaningful for any other type. */ - exponent_t exponent2 : 11; - unsigned int sign2: 1; }; + + // See friend declaration above. This additional declaration is required in + // order to compile LLVM with IBM xlC compiler. + hash_code hash_value(const APFloat &Arg); } /* namespace llvm */ #endif /* LLVM_FLOAT_H */ diff --git a/include/llvm/ADT/APInt.h b/include/llvm/ADT/APInt.h index 7f20e33..95cd23d 100644 --- a/include/llvm/ADT/APInt.h +++ b/include/llvm/ADT/APInt.h @@ -251,7 +251,7 @@ public: /// constructor. APInt(unsigned numBits, unsigned numWords, const uint64_t bigVal[]); - /// This constructor interprets the string \arg str in the given radix. The + /// This constructor interprets the string \p str in the given radix. The /// interpretation stops when the first character that is not suitable for the /// radix is encountered, or the end of the string. Acceptable radix values /// are 2, 8, 10, 16, and 36. It is an error for the value implied by the @@ -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; @@ -601,7 +601,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()) @@ -760,7 +760,7 @@ public: APInt shl(unsigned shiftAmt) const { assert(shiftAmt <= BitWidth && "Invalid shift amount"); if (isSingleWord()) { - if (shiftAmt == BitWidth) + if (shiftAmt >= BitWidth) return APInt(BitWidth, 0); // avoid undefined shift results return APInt(BitWidth, VAL << shiftAmt); } @@ -1231,7 +1231,7 @@ public: } /// This method determines how many bits are required to hold the APInt - /// equivalent of the string given by \arg str. + /// equivalent of the string given by \p str. /// @brief Get bits required for string value. static unsigned getBitsNeeded(StringRef str, uint8_t radix); @@ -1780,6 +1780,9 @@ inline APInt Not(const APInt& APIVal) { } // End of APIntOps namespace + // See friend declaration above. This additional declaration is required in + // order to compile LLVM with IBM xlC compiler. + hash_code hash_value(const APInt &Arg); } // End of llvm namespace #endif diff --git a/include/llvm/ADT/APSInt.h b/include/llvm/ADT/APSInt.h index 048c65c..4a5e7a3 100644 --- a/include/llvm/ADT/APSInt.h +++ b/include/llvm/ADT/APSInt.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. diff --git a/include/llvm/ADT/BitVector.h b/include/llvm/ADT/BitVector.h index 26ec346..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; @@ -237,6 +237,34 @@ public: return *this; } + /// set - Efficiently set a range of bits in [I, E) + BitVector &set(unsigned I, unsigned E) { + assert(I <= E && "Attempted to set backwards range!"); + assert(E <= size() && "Attempted to set out-of-bounds range!"); + + if (I == E) return *this; + + if (I / BITWORD_SIZE == E / BITWORD_SIZE) { + BitWord EMask = 1UL << (E % BITWORD_SIZE); + BitWord IMask = 1UL << (I % BITWORD_SIZE); + BitWord Mask = EMask - IMask; + Bits[I / BITWORD_SIZE] |= Mask; + return *this; + } + + BitWord PrefixMask = ~0UL << (I % BITWORD_SIZE); + Bits[I / BITWORD_SIZE] |= PrefixMask; + I = RoundUpToAlignment(I, BITWORD_SIZE); + + for (; I + BITWORD_SIZE <= E; I += BITWORD_SIZE) + Bits[I / BITWORD_SIZE] = ~0UL; + + BitWord PostfixMask = (1UL << (E % BITWORD_SIZE)) - 1; + Bits[I / BITWORD_SIZE] |= PostfixMask; + + return *this; + } + BitVector &reset() { init_words(Bits, Capacity, false); return *this; @@ -247,6 +275,34 @@ public: return *this; } + /// reset - Efficiently reset a range of bits in [I, E) + BitVector &reset(unsigned I, unsigned E) { + assert(I <= E && "Attempted to reset backwards range!"); + assert(E <= size() && "Attempted to reset out-of-bounds range!"); + + if (I == E) return *this; + + if (I / BITWORD_SIZE == E / BITWORD_SIZE) { + BitWord EMask = 1UL << (E % BITWORD_SIZE); + BitWord IMask = 1UL << (I % BITWORD_SIZE); + BitWord Mask = EMask - IMask; + Bits[I / BITWORD_SIZE] &= ~Mask; + return *this; + } + + BitWord PrefixMask = ~0UL << (I % BITWORD_SIZE); + Bits[I / BITWORD_SIZE] &= ~PrefixMask; + I = RoundUpToAlignment(I, BITWORD_SIZE); + + for (; I + BITWORD_SIZE <= E; I += BITWORD_SIZE) + Bits[I / BITWORD_SIZE] = 0UL; + + BitWord PostfixMask = (1UL << (E % BITWORD_SIZE)) - 1; + Bits[I / BITWORD_SIZE] &= ~PostfixMask; + + return *this; + } + BitVector &flip() { for (unsigned i = 0; i < NumBitWords(size()); ++i) Bits[i] = ~Bits[i]; @@ -396,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 e502ac4..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 { @@ -48,17 +48,18 @@ public: public: virtual ~DAGDeltaAlgorithm() {} - /// Run - Minimize the DAG formed by the \arg Changes vertices and the \arg - /// Dependencies edges by executing \see ExecuteOneTest() on subsets of + /// Run - Minimize the DAG formed by the \p Changes vertices and the + /// \p Dependencies edges by executing \see ExecuteOneTest() on subsets of /// changes and returning the smallest set which still satisfies the test - /// predicate and the input \arg Dependencies. + /// predicate and the input \p Dependencies. /// /// \param Changes The list of changes. /// /// \param Dependencies The list of dependencies amongst changes. For each - /// (x,y) in \arg Dependencies, both x and y must be in \arg Changes. The - /// minimization algorithm guarantees that for each tested changed set S, x - /// \in S implies y \in S. It is an error to have cyclic dependencies. + /// (x,y) in \p Dependencies, both x and y must be in \p Changes. The + /// minimization algorithm guarantees that for each tested changed set S, + /// \f$ x \in S \f$ implies \f$ y \in S \f$. It is an error to have cyclic + /// dependencies. changeset_ty Run(const changeset_ty &Changes, const std::vector<edge_ty> &Dependencies); @@ -67,7 +68,7 @@ public: const changesetlist_ty &Sets, const changeset_ty &Required) {} - /// ExecuteOneTest - Execute a single test predicate on the change set \arg S. + /// ExecuteOneTest - Execute a single test predicate on the change set \p S. virtual bool ExecuteOneTest(const changeset_ty &S) = 0; }; diff --git a/include/llvm/ADT/DeltaAlgorithm.h b/include/llvm/ADT/DeltaAlgorithm.h index 45ba198..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 { @@ -45,23 +45,23 @@ private: /// since we always reduce following a success. std::set<changeset_ty> FailedTestsCache; - /// GetTestResult - Get the test result for the \arg Changes from the + /// GetTestResult - Get the test result for the \p Changes from the /// cache, executing the test if necessary. /// /// \param Changes - The change set to test. /// \return - The test result. bool GetTestResult(const changeset_ty &Changes); - /// Split - Partition a set of changes \arg S into one or two subsets. + /// Split - Partition a set of changes \p S into one or two subsets. void Split(const changeset_ty &S, changesetlist_ty &Res); - /// Delta - Minimize a set of \arg Changes which has been partioned into + /// Delta - Minimize a set of \p Changes which has been partioned into /// smaller sets, by attempting to remove individual subsets. changeset_ty Delta(const changeset_ty &Changes, const changesetlist_ty &Sets); - /// Search - Search for a subset (or subsets) in \arg Sets which can be - /// removed from \arg Changes while still satisfying the predicate. + /// Search - Search for a subset (or subsets) in \p Sets which can be + /// removed from \p Changes while still satisfying the predicate. /// /// \param Res - On success, a subset of Changes which satisfies the /// predicate. @@ -74,13 +74,13 @@ protected: virtual void UpdatedSearchState(const changeset_ty &Changes, const changesetlist_ty &Sets) {} - /// ExecuteOneTest - Execute a single test predicate on the change set \arg S. + /// ExecuteOneTest - Execute a single test predicate on the change set \p S. virtual bool ExecuteOneTest(const changeset_ty &S) = 0; public: virtual ~DeltaAlgorithm(); - /// Run - Minimize the set \arg Changes by executing \see ExecuteOneTest() on + /// Run - Minimize the set \p Changes by executing \see ExecuteOneTest() on /// subsets of changes and returning the smallest set which still satisfies /// the test predicate. changeset_ty Run(const changeset_ty &Changes); diff --git a/include/llvm/ADT/DenseMap.h b/include/llvm/ADT/DenseMap.h index f60d688..01f7e90 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) { @@ -198,7 +198,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 +383,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); @@ -420,16 +420,18 @@ private: NumBuckets = getNumBuckets(); } if (NumBuckets-(NewNumEntries+getNumTombstones()) <= NumBuckets/8) { - this->grow(NumBuckets); + this->grow(NumBuckets * 2); LookupBucketFor(Key, TheBucket); } + assert(TheBucket); // Only update the state after we've grown our bucket space appropriately // so that when growing buckets we have self-consistent entry count. 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; @@ -530,13 +532,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); } @@ -565,7 +567,7 @@ public: return *this; } -#if LLVM_USE_RVALUE_REFERENCES +#if LLVM_HAS_RVALUE_REFERENCES DenseMap& operator=(DenseMap &&other) { this->destroyAll(); operator delete(Buckets); @@ -599,7 +601,7 @@ public: unsigned OldNumBuckets = NumBuckets; BucketT *OldBuckets = Buckets; - allocateBuckets(std::max<unsigned>(64, NextPowerOf2(AtLeast))); + allocateBuckets(std::max<unsigned>(64, NextPowerOf2(AtLeast-1))); assert(Buckets); if (!OldBuckets) { this->BaseT::initEmpty(); @@ -699,7 +701,7 @@ public: copyFrom(other); } -#if LLVM_USE_RVALUE_REFERENCES +#if LLVM_HAS_RVALUE_REFERENCES SmallDenseMap(SmallDenseMap &&other) { init(0); swap(other); @@ -794,7 +796,7 @@ public: return *this; } -#if LLVM_USE_RVALUE_REFERENCES +#if LLVM_HAS_RVALUE_REFERENCES SmallDenseMap& operator=(SmallDenseMap &&other) { this->destroyAll(); deallocateBuckets(); @@ -825,11 +827,11 @@ public: } void grow(unsigned AtLeast) { - if (AtLeast > InlineBuckets) - AtLeast = std::max<unsigned>(64, NextPowerOf2(AtLeast)); + if (AtLeast >= InlineBuckets) + AtLeast = std::max<unsigned>(64, NextPowerOf2(AtLeast-1)); if (Small) { - if (AtLeast <= InlineBuckets) + if (AtLeast < InlineBuckets) return; // Nothing to do. // First move the inline buckets into a temporary storage. @@ -1026,7 +1028,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/EquivalenceClasses.h b/include/llvm/ADT/EquivalenceClasses.h index 771476c..1d81772 100644 --- a/include/llvm/ADT/EquivalenceClasses.h +++ b/include/llvm/ADT/EquivalenceClasses.h @@ -33,6 +33,7 @@ namespace llvm { /// /// Here is a simple example using integers: /// +/// \code /// EquivalenceClasses<int> EC; /// EC.unionSets(1, 2); // insert 1, 2 into the same set /// EC.insert(4); EC.insert(5); // insert 4, 5 into own sets @@ -46,6 +47,7 @@ namespace llvm { /// cerr << *MI << " "; // Print member. /// cerr << "\n"; // Finish set. /// } +/// \endcode /// /// This example prints: /// 4 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/Hashing.h b/include/llvm/ADT/Hashing.h index 2363304..cda31a2 100644 --- a/include/llvm/ADT/Hashing.h +++ b/include/llvm/ADT/Hashing.h @@ -710,7 +710,7 @@ hash_code hash_combine(const T1 &arg1) { #endif -// Implementation details for implementatinos of hash_value overloads provided +// Implementation details for implementations of hash_value overloads provided // here. namespace hashing { namespace detail { diff --git a/include/llvm/ADT/ImmutableList.h b/include/llvm/ADT/ImmutableList.h index d7c0074..998d785 100644 --- a/include/llvm/ADT/ImmutableList.h +++ b/include/llvm/ADT/ImmutableList.h @@ -14,8 +14,8 @@ #ifndef LLVM_ADT_IMLIST_H #define LLVM_ADT_IMLIST_H -#include "llvm/Support/Allocator.h" #include "llvm/ADT/FoldingSet.h" +#include "llvm/Support/Allocator.h" #include "llvm/Support/DataTypes.h" #include <cassert> @@ -33,9 +33,8 @@ class ImmutableListImpl : public FoldingSetNode { friend class ImmutableListFactory<T>; - // Do not implement. - void operator=(const ImmutableListImpl&); - ImmutableListImpl(const ImmutableListImpl&); + void operator=(const ImmutableListImpl&) LLVM_DELETED_FUNCTION; + ImmutableListImpl(const ImmutableListImpl&) LLVM_DELETED_FUNCTION; public: const T& getHead() const { return Head; } diff --git a/include/llvm/ADT/ImmutableMap.h b/include/llvm/ADT/ImmutableMap.h index 8346ffa..f9baec2 100644 --- a/include/llvm/ADT/ImmutableMap.h +++ b/include/llvm/ADT/ImmutableMap.h @@ -122,8 +122,8 @@ public: } private: - Factory(const Factory& RHS); // DO NOT IMPLEMENT - void operator=(const Factory& RHS); // DO NOT IMPLEMENT + Factory(const Factory& RHS) LLVM_DELETED_FUNCTION; + void operator=(const Factory& RHS) LLVM_DELETED_FUNCTION; }; bool contains(key_type_ref K) const { @@ -288,6 +288,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 +325,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 949dc44..0982657 100644 --- a/include/llvm/ADT/ImmutableSet.h +++ b/include/llvm/ADT/ImmutableSet.h @@ -14,15 +14,14 @@ #ifndef LLVM_ADT_IMSET_H #define LLVM_ADT_IMSET_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> #include <functional> #include <vector> -#include <stdio.h> namespace llvm { @@ -84,13 +83,13 @@ public: } return NULL; } - + /// getMaxElement - Find the subtree associated with the highest ranged /// key value. ImutAVLTree* getMaxElement() { ImutAVLTree *T = this; - ImutAVLTree *Right = T->getRight(); - while (Right) { T = right; right = T->getRight(); } + ImutAVLTree *Right = T->getRight(); + while (Right) { T = Right; Right = T->getRight(); } return T; } @@ -258,7 +257,7 @@ private: /// method returns false for an instance of ImutAVLTree, all subtrees /// will also have this method return false. The converse is not true. bool isMutable() const { return IsMutable; } - + /// hasCachedDigest - Returns true if the digest for this tree is cached. /// This can only be true if the tree is immutable. bool hasCachedDigest() const { return IsDigestCached; } @@ -280,7 +279,7 @@ private: assert(isMutable() && "Mutable flag already removed."); IsMutable = false; } - + /// markedCachedDigest - Clears the NoCachedDigest flag for a tree. void markedCachedDigest() { assert(!hasCachedDigest() && "NoCachedDigest flag already removed."); @@ -349,7 +348,7 @@ public: else factory->Cache[factory->maskCacheIndex(computeDigest())] = next; } - + // We need to clear the mutability bit in case we are // destroying the node as part of a sweep in ImutAVLFactory::recoverNodes(). IsMutable = false; @@ -415,7 +414,7 @@ public: TreeTy* getEmptyTree() const { return NULL; } protected: - + //===--------------------------------------------------===// // A bunch of quick helper functions used for reasoning // about the properties of trees and their children. @@ -461,7 +460,7 @@ protected: // returned to the caller. //===--------------------------------------------------===// - TreeTy* createNode(TreeTy* L, value_type_ref V, TreeTy* R) { + TreeTy* createNode(TreeTy* L, value_type_ref V, TreeTy* R) { BumpPtrAllocator& A = getAllocator(); TreeTy* T; if (!freeNodes.empty()) { @@ -469,8 +468,7 @@ protected: freeNodes.pop_back(); assert(T != L); assert(T != R); - } - else { + } else { T = (TreeTy*) A.Allocate<TreeTy>(); } new (T) TreeTy(this, L, R, V, incrementHeight(L,R)); @@ -513,7 +511,8 @@ protected: return createNode(createNode(LL,L,LRL), LR, createNode(LRR,V,R)); } - else if (hr > hl + 2) { + + if (hr > hl + 2) { assert(!isEmpty(R) && "Right tree cannot be empty to have a height >= 2"); TreeTy *RL = getLeft(R); @@ -529,8 +528,8 @@ protected: return createNode(createNode(L,V,RLL), RL, createNode(RLR,R,RR)); } - else - return createNode(L,V,R); + + return createNode(L,V,R); } /// add_internal - Creates a new tree that includes the specified @@ -604,7 +603,7 @@ protected: markImmutable(getLeft(T)); markImmutable(getRight(T)); } - + public: TreeTy *getCanonicalTree(TreeTy *TNew) { if (!TNew) @@ -937,7 +936,7 @@ public: private: TreeTy *Root; - + public: /// Constructs a set from a pointer to a tree root. In general one /// should use a Factory object to create sets instead of directly @@ -1006,10 +1005,10 @@ public: typename TreeTy::Factory *getTreeFactory() const { return const_cast<typename TreeTy::Factory *>(&F); } - + private: - Factory(const Factory& RHS); // DO NOT IMPLEMENT - void operator=(const Factory& RHS); // DO NOT IMPLEMENT + Factory(const Factory& RHS) LLVM_DELETED_FUNCTION; + void operator=(const Factory& RHS) LLVM_DELETED_FUNCTION; }; friend class Factory; @@ -1027,11 +1026,11 @@ public: return Root && RHS.Root ? Root->isNotEqual(*RHS.Root) : Root != RHS.Root; } - TreeTy *getRoot() { + TreeTy *getRoot() { if (Root) { Root->retain(); } return Root; } - + TreeTy *getRootWithoutRetain() const { return Root; } @@ -1092,7 +1091,7 @@ public: void validateTree() const { if (Root) Root->validateTree(); } }; - + // NOTE: This may some day replace the current ImmutableSet. template <typename ValT, typename ValInfo = ImutContainerInfo<ValT> > class ImmutableSetRef { @@ -1101,11 +1100,11 @@ public: typedef typename ValInfo::value_type_ref value_type_ref; typedef ImutAVLTree<ValInfo> TreeTy; typedef typename TreeTy::Factory FactoryTy; - + private: TreeTy *Root; FactoryTy *Factory; - + public: /// Constructs a set from a pointer to a tree root. In general one /// should use a Factory object to create sets instead of directly @@ -1133,44 +1132,44 @@ public: ~ImmutableSetRef() { if (Root) { Root->release(); } } - + static inline ImmutableSetRef getEmptySet(FactoryTy *F) { return ImmutableSetRef(0, F); } - + ImmutableSetRef add(value_type_ref V) { return ImmutableSetRef(Factory->add(Root, V), Factory); } - + ImmutableSetRef remove(value_type_ref V) { return ImmutableSetRef(Factory->remove(Root, V), Factory); } - + /// Returns true if the set contains the specified value. bool contains(value_type_ref V) const { return Root ? Root->contains(V) : false; } - + ImmutableSet<ValT> asImmutableSet(bool canonicalize = true) const { return ImmutableSet<ValT>(canonicalize ? Factory->getCanonicalTree(Root) : Root); } - + TreeTy *getRootWithoutRetain() const { return Root; } - + bool operator==(const ImmutableSetRef &RHS) const { return Root && RHS.Root ? Root->isEqual(*RHS.Root) : Root == RHS.Root; } - + bool operator!=(const ImmutableSetRef &RHS) const { return Root && RHS.Root ? Root->isNotEqual(*RHS.Root) : Root != RHS.Root; } /// isEmpty - Return true if the set contains no elements. bool isEmpty() const { return !Root; } - + /// isSingleton - Return true if the set contains exactly one element. /// This method runs in constant time. bool isSingleton() const { return getHeight() == 1; } @@ -1178,7 +1177,7 @@ public: //===--------------------------------------------------===// // Iterators. //===--------------------------------------------------===// - + class iterator { typename TreeTy::iterator itr; iterator(TreeTy* t) : itr(t) {} @@ -1194,28 +1193,28 @@ public: inline bool operator!=(const iterator& RHS) const { return RHS.itr != itr; } inline value_type *operator->() const { return &(operator*()); } }; - + iterator begin() const { return iterator(Root); } iterator end() const { return iterator(); } - + //===--------------------------------------------------===// // Utility methods. //===--------------------------------------------------===// - + unsigned getHeight() const { return Root ? Root->getHeight() : 0; } - + static inline void Profile(FoldingSetNodeID& ID, const ImmutableSetRef& S) { ID.AddPointer(S.Root); } - + inline void Profile(FoldingSetNodeID& ID) const { return Profile(ID,*this); } - + //===--------------------------------------------------===// // For testing. //===--------------------------------------------------===// - + void validateTree() const { if (Root) Root->validateTree(); } }; 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..5849503 100644 --- a/include/llvm/ADT/IntrusiveRefCntPtr.h +++ b/include/llvm/ADT/IntrusiveRefCntPtr.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; } diff --git a/include/llvm/ADT/MapVector.h b/include/llvm/ADT/MapVector.h new file mode 100644 index 0000000..c34e32a --- /dev/null +++ b/include/llvm/ADT/MapVector.h @@ -0,0 +1,107 @@ +//===- llvm/ADT/MapVector.h - Map with deterministic value order *- 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 a map that provides insertion order iteration. The +// interface is purposefully minimal. The key is assumed to be cheap to copy +// and 2 copies are kept, one for indexing in a DenseMap, one for iteration in +// a std::vector. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_ADT_MAPVECTOR_H +#define LLVM_ADT_MAPVECTOR_H + +#include "llvm/ADT/ArrayRef.h" +#include "llvm/ADT/DenseMap.h" +#include <vector> + +namespace llvm { + +/// This class implements a map that also provides access to all stored values +/// in a deterministic order. The values are kept in a std::vector and the +/// mapping is done with DenseMap from Keys to indexes in that vector. +template<typename KeyT, typename ValueT, + typename MapType = llvm::DenseMap<KeyT, unsigned>, + typename VectorType = std::vector<std::pair<KeyT, ValueT> > > +class MapVector { + typedef typename VectorType::size_type SizeType; + + MapType Map; + VectorType Vector; + +public: + typedef typename VectorType::iterator iterator; + typedef typename VectorType::const_iterator const_iterator; + + SizeType size() const { + return Vector.size(); + } + + iterator begin() { + return Vector.begin(); + } + + const_iterator begin() const { + return Vector.begin(); + } + + iterator end() { + return Vector.end(); + } + + const_iterator end() const { + return Vector.end(); + } + + bool empty() const { + return Vector.empty(); + } + + void clear() { + Map.clear(); + Vector.clear(); + } + + ValueT &operator[](const KeyT &Key) { + std::pair<KeyT, unsigned> Pair = std::make_pair(Key, 0); + std::pair<typename MapType::iterator, bool> Result = Map.insert(Pair); + unsigned &I = Result.first->second; + if (Result.second) { + Vector.push_back(std::make_pair(Key, ValueT())); + I = Vector.size() - 1; + } + 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; + } + + 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); + } +}; + +} + +#endif diff --git a/include/llvm/ADT/Optional.h b/include/llvm/ADT/Optional.h index ee8b69f..06e5af0 100644 --- a/include/llvm/ADT/Optional.h +++ b/include/llvm/ADT/Optional.h @@ -16,18 +16,27 @@ #ifndef LLVM_ADT_OPTIONAL #define LLVM_ADT_OPTIONAL +#include "llvm/Support/Compiler.h" #include <cassert> +#if LLVM_HAS_RVALUE_REFERENCES +#include <utility> +#endif + namespace llvm { template<typename T> class Optional { T x; - unsigned hasVal : 1; + bool hasVal; public: explicit Optional() : x(), hasVal(false) {} Optional(const T &y) : x(y), hasVal(true) {} +#if LLVM_HAS_RVALUE_REFERENCES + Optional(T &&y) : x(std::forward<T>(y)), hasVal(true) {} +#endif + static inline Optional create(const T* y) { return y ? Optional(*y) : Optional(); } @@ -39,12 +48,17 @@ public: } const T* getPointer() const { assert(hasVal); return &x; } - const T& getValue() const { assert(hasVal); return x; } + const T& getValue() const LLVM_LVALUE_FUNCTION { 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; } + const T& operator*() const LLVM_LVALUE_FUNCTION { assert(hasVal); return x; } + +#if LLVM_HAS_RVALUE_REFERENCE_THIS + T&& getValue() && { assert(hasVal); return std::move(x); } + T&& operator*() && { assert(hasVal); return std::move(x); } +#endif }; template<typename T> struct simplify_type; diff --git a/include/llvm/ADT/OwningPtr.h b/include/llvm/ADT/OwningPtr.h index 6d9c305..ea22991 100644 --- a/include/llvm/ADT/OwningPtr.h +++ b/include/llvm/ADT/OwningPtr.h @@ -14,6 +14,7 @@ #ifndef LLVM_ADT_OWNING_PTR_H #define LLVM_ADT_OWNING_PTR_H +#include "llvm/Support/Compiler.h" #include <cassert> #include <cstddef> @@ -25,12 +26,21 @@ namespace llvm { /// pointee object can be taken away from OwningPtr by using the take method. template<class T> class OwningPtr { - OwningPtr(OwningPtr const &); // DO NOT IMPLEMENT - OwningPtr &operator=(OwningPtr const &); // DO NOT IMPLEMENT + OwningPtr(OwningPtr const &) LLVM_DELETED_FUNCTION; + OwningPtr &operator=(OwningPtr const &) LLVM_DELETED_FUNCTION; T *Ptr; public: explicit OwningPtr(T *P = 0) : Ptr(P) {} +#if LLVM_HAS_RVALUE_REFERENCES + OwningPtr(OwningPtr &&Other) : Ptr(Other.take()) {} + + OwningPtr &operator=(OwningPtr &&Other) { + reset(Other.take()); + return *this; + } +#endif + ~OwningPtr() { delete Ptr; } @@ -79,12 +89,21 @@ inline void swap(OwningPtr<T> &a, OwningPtr<T> &b) { /// functionality as OwningPtr, except that it works for array types. template<class T> class OwningArrayPtr { - OwningArrayPtr(OwningArrayPtr const &); // DO NOT IMPLEMENT - OwningArrayPtr &operator=(OwningArrayPtr const &); // DO NOT IMPLEMENT + OwningArrayPtr(OwningArrayPtr const &) LLVM_DELETED_FUNCTION; + OwningArrayPtr &operator=(OwningArrayPtr const &) LLVM_DELETED_FUNCTION; T *Ptr; public: explicit OwningArrayPtr(T *P = 0) : Ptr(P) {} +#if LLVM_HAS_RVALUE_REFERENCES + OwningArrayPtr(OwningArrayPtr &&Other) : Ptr(Other.take()) {} + + OwningArrayPtr &operator=(OwningArrayPtr &&Other) { + reset(Other.take()); + return *this; + } +#endif + ~OwningArrayPtr() { delete [] Ptr; } diff --git a/include/llvm/ADT/PackedVector.h b/include/llvm/ADT/PackedVector.h index 2eaddc2..1ae2a77 100644 --- a/include/llvm/ADT/PackedVector.h +++ b/include/llvm/ADT/PackedVector.h @@ -19,32 +19,32 @@ namespace llvm { -template <typename T, unsigned BitNum, bool isSigned> +template <typename T, unsigned BitNum, typename BitVectorTy, bool isSigned> class PackedVectorBase; // This won't be necessary if we can specialize members without specializing // the parent template. -template <typename T, unsigned BitNum> -class PackedVectorBase<T, BitNum, false> { +template <typename T, unsigned BitNum, typename BitVectorTy> +class PackedVectorBase<T, BitNum, BitVectorTy, false> { protected: - static T getValue(const llvm::BitVector &Bits, unsigned Idx) { + static T getValue(const BitVectorTy &Bits, unsigned Idx) { T val = T(); for (unsigned i = 0; i != BitNum; ++i) val = T(val | ((Bits[(Idx << (BitNum-1)) + i] ? 1UL : 0UL) << i)); return val; } - static void setValue(llvm::BitVector &Bits, unsigned Idx, T val) { + static void setValue(BitVectorTy &Bits, unsigned Idx, T val) { assert((val >> BitNum) == 0 && "value is too big"); for (unsigned i = 0; i != BitNum; ++i) Bits[(Idx << (BitNum-1)) + i] = val & (T(1) << i); } }; -template <typename T, unsigned BitNum> -class PackedVectorBase<T, BitNum, true> { +template <typename T, unsigned BitNum, typename BitVectorTy> +class PackedVectorBase<T, BitNum, BitVectorTy, true> { protected: - static T getValue(const llvm::BitVector &Bits, unsigned Idx) { + static T getValue(const BitVectorTy &Bits, unsigned Idx) { T val = T(); for (unsigned i = 0; i != BitNum-1; ++i) val = T(val | ((Bits[(Idx << (BitNum-1)) + i] ? 1UL : 0UL) << i)); @@ -53,7 +53,7 @@ protected: return val; } - static void setValue(llvm::BitVector &Bits, unsigned Idx, T val) { + static void setValue(BitVectorTy &Bits, unsigned Idx, T val) { if (val < 0) { val = ~val; Bits.set((Idx << (BitNum-1)) + BitNum-1); @@ -71,11 +71,12 @@ protected: /// @endcode /// will create a vector accepting values -2, -1, 0, 1. Any other value will hit /// an assertion. -template <typename T, unsigned BitNum> -class PackedVector : public PackedVectorBase<T, BitNum, +template <typename T, unsigned BitNum, typename BitVectorTy = BitVector> +class PackedVector : public PackedVectorBase<T, BitNum, BitVectorTy, std::numeric_limits<T>::is_signed> { - llvm::BitVector Bits; - typedef PackedVectorBase<T, BitNum, std::numeric_limits<T>::is_signed> base; + BitVectorTy Bits; + typedef PackedVectorBase<T, BitNum, BitVectorTy, + std::numeric_limits<T>::is_signed> base; public: class reference { 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/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/ScopedHashTable.h b/include/llvm/ADT/ScopedHashTable.h index a6803ee..efddd9f 100644 --- a/include/llvm/ADT/ScopedHashTable.h +++ b/include/llvm/ADT/ScopedHashTable.h @@ -90,8 +90,8 @@ class ScopedHashTableScope { /// LastValInScope - This is the last value that was inserted for this scope /// or null if none have been inserted yet. ScopedHashTableVal<K, V> *LastValInScope; - void operator=(ScopedHashTableScope&); // DO NOT IMPLEMENT - ScopedHashTableScope(ScopedHashTableScope&); // DO NOT IMPLEMENT + void operator=(ScopedHashTableScope&) LLVM_DELETED_FUNCTION; + ScopedHashTableScope(ScopedHashTableScope&) LLVM_DELETED_FUNCTION; public: ScopedHashTableScope(ScopedHashTable<K, V, KInfo, AllocatorTy> &HT); ~ScopedHashTableScope(); diff --git a/include/llvm/ADT/SetVector.h b/include/llvm/ADT/SetVector.h index 965f0de..d2f7286 100644 --- a/include/llvm/ADT/SetVector.h +++ b/include/llvm/ADT/SetVector.h @@ -27,10 +27,11 @@ namespace llvm { +/// \brief A vector that has set insertion semantics. +/// /// This adapter class provides a way to keep a set of things that also has the /// property of a deterministic iteration order. The order of iteration is the /// order of insertion. -/// @brief A vector that has set insertion semantics. template <typename T, typename Vector = std::vector<T>, typename Set = SmallSet<T, 16> > class SetVector { @@ -45,59 +46,59 @@ public: typedef typename vector_type::const_iterator const_iterator; typedef typename vector_type::size_type size_type; - /// @brief Construct an empty SetVector + /// \brief Construct an empty SetVector SetVector() {} - /// @brief Initialize a SetVector with a range of elements + /// \brief Initialize a SetVector with a range of elements template<typename It> SetVector(It Start, It End) { insert(Start, End); } - /// @brief Determine if the SetVector is empty or not. + /// \brief Determine if the SetVector is empty or not. bool empty() const { return vector_.empty(); } - /// @brief Determine the number of elements in the SetVector. + /// \brief Determine the number of elements in the SetVector. size_type size() const { return vector_.size(); } - /// @brief Get an iterator to the beginning of the SetVector. + /// \brief Get an iterator to the beginning of the SetVector. iterator begin() { return vector_.begin(); } - /// @brief Get a const_iterator to the beginning of the SetVector. + /// \brief Get a const_iterator to the beginning of the SetVector. const_iterator begin() const { return vector_.begin(); } - /// @brief Get an iterator to the end of the SetVector. + /// \brief Get an iterator to the end of the SetVector. iterator end() { return vector_.end(); } - /// @brief Get a const_iterator to the end of the SetVector. + /// \brief Get a const_iterator to the end of the SetVector. const_iterator end() const { return vector_.end(); } - /// @brief Return the last element of the SetVector. + /// \brief Return the last element of the SetVector. const T &back() const { assert(!empty() && "Cannot call back() on empty SetVector!"); return vector_.back(); } - /// @brief Index into the SetVector. + /// \brief Index into the SetVector. const_reference operator[](size_type n) const { assert(n < vector_.size() && "SetVector access out of range!"); return vector_[n]; } - /// @returns true iff the element was inserted into the SetVector. - /// @brief Insert a new element into the SetVector. + /// \brief Insert a new element into the SetVector. + /// \returns true iff the element was inserted into the SetVector. bool insert(const value_type &X) { bool result = set_.insert(X); if (result) @@ -105,7 +106,7 @@ public: return result; } - /// @brief Insert a range of elements into the SetVector. + /// \brief Insert a range of elements into the SetVector. template<typename It> void insert(It Start, It End) { for (; Start != End; ++Start) @@ -113,7 +114,7 @@ public: vector_.push_back(*Start); } - /// @brief Remove an item from the set vector. + /// \brief Remove an item from the set vector. bool remove(const value_type& X) { if (set_.erase(X)) { typename vector_type::iterator I = @@ -125,20 +126,44 @@ public: return false; } - - /// @returns 0 if the element is not in the SetVector, 1 if it is. - /// @brief Count the number of elements of a given key in the SetVector. + /// \brief Remove items from the set vector based on a predicate function. + /// + /// This is intended to be equivalent to the following code, if we could + /// write it: + /// + /// \code + /// V.erase(std::remove_if(V.begin(), V.end(), P), V.end()); + /// \endcode + /// + /// However, SetVector doesn't expose non-const iterators, making any + /// algorithm like remove_if impossible to use. + /// + /// \returns true if any element is removed. + template <typename UnaryPredicate> + bool remove_if(UnaryPredicate P) { + typename vector_type::iterator I + = std::remove_if(vector_.begin(), vector_.end(), + TestAndEraseFromSet<UnaryPredicate>(P, set_)); + if (I == vector_.end()) + return false; + vector_.erase(I, vector_.end()); + return true; + } + + + /// \brief Count the number of elements of a given key in the SetVector. + /// \returns 0 if the element is not in the SetVector, 1 if it is. size_type count(const key_type &key) const { return set_.count(key); } - /// @brief Completely clear the SetVector + /// \brief Completely clear the SetVector void clear() { set_.clear(); vector_.clear(); } - /// @brief Remove the last element of the SetVector. + /// \brief Remove the last element of the SetVector. void pop_back() { assert(!empty() && "Cannot remove an element from an empty SetVector!"); set_.erase(back()); @@ -160,18 +185,41 @@ public: } private: + /// \brief A wrapper predicate designed for use with std::remove_if. + /// + /// This predicate wraps a predicate suitable for use with std::remove_if to + /// call set_.erase(x) on each element which is slated for removal. + template <typename UnaryPredicate> + class TestAndEraseFromSet { + UnaryPredicate P; + set_type &set_; + + public: + typedef typename UnaryPredicate::argument_type argument_type; + + TestAndEraseFromSet(UnaryPredicate P, set_type &set_) : P(P), set_(set_) {} + + bool operator()(argument_type Arg) { + if (P(Arg)) { + set_.erase(Arg); + return true; + } + return false; + } + }; + set_type set_; ///< The set. vector_type vector_; ///< The vector. }; -/// SmallSetVector - A SetVector that performs no allocations if smaller than +/// \brief A SetVector that performs no allocations if smaller than /// a certain size. template <typename T, unsigned N> class SmallSetVector : public SetVector<T, SmallVector<T, N>, SmallSet<T, N> > { public: SmallSetVector() {} - /// @brief Initialize a SmallSetVector with a range of elements + /// \brief Initialize a SmallSetVector with a range of elements template<typename It> SmallSetVector(It Start, It End) { this->insert(Start, End); diff --git a/include/llvm/ADT/SmallBitVector.h b/include/llvm/ADT/SmallBitVector.h index 7a645e0..62620fa 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; } @@ -300,6 +300,21 @@ public: return *this; } + /// set - Efficiently set a range of bits in [I, E) + SmallBitVector &set(unsigned I, unsigned E) { + assert(I <= E && "Attempted to set backwards range!"); + assert(E <= size() && "Attempted to set out-of-bounds range!"); + if (I == E) return *this; + if (isSmall()) { + uintptr_t EMask = ((uintptr_t)1) << E; + uintptr_t IMask = ((uintptr_t)1) << I; + uintptr_t Mask = EMask - IMask; + setSmallBits(getSmallBits() | Mask); + } else + getPointer()->set(I, E); + return *this; + } + SmallBitVector &reset() { if (isSmall()) setSmallBits(0); @@ -316,6 +331,21 @@ public: return *this; } + /// reset - Efficiently reset a range of bits in [I, E) + SmallBitVector &reset(unsigned I, unsigned E) { + assert(I <= E && "Attempted to reset backwards range!"); + assert(E <= size() && "Attempted to reset out-of-bounds range!"); + if (I == E) return *this; + if (isSmall()) { + uintptr_t EMask = ((uintptr_t)1) << E; + uintptr_t IMask = ((uintptr_t)1) << I; + uintptr_t Mask = EMask - IMask; + setSmallBits(getSmallBits() & ~Mask); + } else + getPointer()->reset(I, E); + return *this; + } + SmallBitVector &flip() { if (isSmall()) setSmallBits(~getSmallBits()); @@ -442,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 498a034..3bb8830 100644 --- a/include/llvm/ADT/SmallPtrSet.h +++ b/include/llvm/ADT/SmallPtrSet.h @@ -15,12 +15,13 @@ #ifndef LLVM_ADT_SMALLPTRSET_H #define LLVM_ADT_SMALLPTRSET_H +#include "llvm/Support/Compiler.h" +#include "llvm/Support/DataTypes.h" +#include "llvm/Support/PointerLikeTypeTraits.h" #include <cassert> #include <cstddef> #include <cstring> #include <iterator> -#include "llvm/Support/DataTypes.h" -#include "llvm/Support/PointerLikeTypeTraits.h" namespace llvm { @@ -132,7 +133,7 @@ private: /// Grow - Allocate a larger backing store for the buckets and move it over. void Grow(unsigned NewSize); - void operator=(const SmallPtrSetImpl &RHS); // DO NOT IMPLEMENT. + void operator=(const SmallPtrSetImpl &RHS) LLVM_DELETED_FUNCTION; protected: /// swap - Swaps the elements of two sets. /// Note: This method assumes that both sets have the same small size. diff --git a/include/llvm/ADT/SmallSet.h b/include/llvm/ADT/SmallSet.h index cd117f5..4eb7de8 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 { diff --git a/include/llvm/ADT/SmallString.h b/include/llvm/ADT/SmallString.h index c6f0a5b..8da99d1 100644 --- a/include/llvm/ADT/SmallString.h +++ b/include/llvm/ADT/SmallString.h @@ -44,25 +44,25 @@ public: /// @name String Assignment /// @{ - /// Assign from a repeated element + /// Assign from a repeated element. void assign(size_t NumElts, char Elt) { this->SmallVectorImpl<char>::assign(NumElts, Elt); } - /// Assign from an iterator pair + /// 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 + /// Assign from a StringRef. void assign(StringRef RHS) { this->clear(); SmallVectorImpl<char>::append(RHS.begin(), RHS.end()); } - /// Assign from a SmallVector + /// Assign from a SmallVector. void assign(const SmallVectorImpl<char> &RHS) { this->clear(); SmallVectorImpl<char>::append(RHS.begin(), RHS.end()); @@ -72,7 +72,7 @@ public: /// @name String Concatenation /// @{ - /// Append from an iterator pair + /// Append from an iterator pair. template<typename in_iter> void append(in_iter S, in_iter E) { SmallVectorImpl<char>::append(S, E); @@ -83,12 +83,12 @@ public: } - /// Append from a StringRef + /// Append from a StringRef. void append(StringRef RHS) { SmallVectorImpl<char>::append(RHS.begin(), RHS.end()); } - /// Append from a SmallVector + /// Append from a SmallVector. void append(const SmallVectorImpl<char> &RHS) { SmallVectorImpl<char>::append(RHS.begin(), RHS.end()); } @@ -97,19 +97,19 @@ public: /// @name String Comparison /// @{ - /// equals - Check for string equality, this is more efficient than - /// compare() when the relative ordering of inequal strings isn't needed. + /// 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. + /// 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. + /// Compare two strings; the result is -1, 0, or 1 if this string is + /// lexicographically less than, equal to, or greater than the \p RHS. int compare(StringRef RHS) const { return str().compare(RHS); } @@ -129,12 +129,12 @@ public: /// @name String Predicates /// @{ - /// startswith - Check if this string starts with the given \arg Prefix. + /// startswith - Check if this string starts with the given \p Prefix. bool startswith(StringRef Prefix) const { return str().startswith(Prefix); } - /// endswith - Check if this string ends with the given \arg Suffix. + /// endswith - Check if this string ends with the given \p Suffix. bool endswith(StringRef Suffix) const { return str().endswith(Suffix); } @@ -143,76 +143,76 @@ public: /// @name String Searching /// @{ - /// find - Search for the first character \arg C in the string. + /// find - Search for the first character \p C in the string. /// - /// \return - The index of the first occurrence of \arg C, or npos if not + /// \return - The index of the first occurrence of \p 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. + /// Search for the first string \p Str in the string. /// - /// \return - The index of the first occurrence of \arg Str, or npos if not + /// \returns The index of the first occurrence of \p 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. + /// Search for the last character \p C in the string. /// - /// \return - The index of the last occurrence of \arg C, or npos if not + /// \returns The index of the last occurrence of \p 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. + /// Search for the last string \p Str in the string. /// - /// \return - The index of the last occurrence of \arg Str, or npos if not + /// \returns The index of the last occurrence of \p 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. + /// Find the first character in the string that is \p 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. + /// Find the first character in the string that is in \p Chars, or npos if + /// not found. /// - /// Note: O(size() + Chars.size()) + /// Complexity: 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. + /// Find the first character in the string that is not \p 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. + /// Find the first character in the string that is not in the string + /// \p Chars, or npos if not found. /// - /// Note: O(size() + Chars.size()) + /// Complexity: 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. + /// Find the last character in the string that is \p 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. + /// Find the last character in the string that is in \p C, or npos if not + /// found. /// - /// Note: O(size() + Chars.size()) + /// Complexity: O(size() + Chars.size()) size_t find_last_of( StringRef Chars, size_t From = StringRef::npos) const { return str().find_last_of(Chars, From); @@ -222,13 +222,13 @@ public: /// @name Helpful Algorithms /// @{ - /// count - Return the number of occurrences of \arg C in the string. + /// Return the number of occurrences of \p 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. + /// Return the number of non-overlapped occurrences of \p Str in the + /// string. size_t count(StringRef Str) const { return str().count(Str); } @@ -237,36 +237,36 @@ public: /// @name Substring Operations /// @{ - /// substr - Return a reference to the substring from [Start, Start + N). + /// Return a reference to the substring from [Start, Start + N). /// - /// \param Start - The index of the starting character in the substring; if + /// \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 + /// \param N The number of characters to included in the substring. If \p N /// exceeds the number of characters remaining in the string, the string - /// suffix (starting with \arg Start) will be returned. + /// suffix (starting with \p 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). + /// Return a reference to the substring from [Start, End). /// - /// \param Start - The index of the starting character in the substring; if + /// \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 + /// \param End The index following the last character to include in the + /// substring. If this is npos, or less than \p Start, or exceeds the /// number of characters remaining in the string, the string suffix - /// (starting with \arg Start) will be returned. + /// (starting with \p Start) will be returned. StringRef slice(size_t Start, size_t End) const { return str().slice(Start, End); } // Extra methods. - /// Explicit conversion to StringRef + /// Explicit conversion to StringRef. StringRef str() const { return StringRef(this->begin(), this->size()); } // TODO: Make this const, if it's safe... diff --git a/include/llvm/ADT/SmallVector.h b/include/llvm/ADT/SmallVector.h index 769b7dc..951e574 100644 --- a/include/llvm/ADT/SmallVector.h +++ b/include/llvm/ADT/SmallVector.h @@ -178,7 +178,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 +193,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 +206,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 +239,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: @@ -365,7 +365,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 +422,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 +495,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 +667,7 @@ public: SmallVectorImpl &operator=(const SmallVectorImpl &RHS); -#if LLVM_USE_RVALUE_REFERENCES +#if LLVM_HAS_RVALUE_REFERENCES SmallVectorImpl &operator=(SmallVectorImpl &&RHS); #endif @@ -684,8 +684,8 @@ public: RHS.begin(), RHS.end()); } - /// set_size - Set the array size to \arg N, which the current array must have - /// enough capacity for. + /// Set the array size to \p N, which the current array must have enough + /// capacity for. /// /// This does not construct or destroy any elements in the vector. /// @@ -787,7 +787,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 +898,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/SparseBitVector.h b/include/llvm/ADT/SparseBitVector.h index 791f108..306e928 100644 --- a/include/llvm/ADT/SparseBitVector.h +++ b/include/llvm/ADT/SparseBitVector.h @@ -262,6 +262,22 @@ public: } }; +template <unsigned ElementSize> +struct ilist_traits<SparseBitVectorElement<ElementSize> > + : public ilist_default_traits<SparseBitVectorElement<ElementSize> > { + typedef SparseBitVectorElement<ElementSize> Element; + + Element *createSentinel() const { return static_cast<Element *>(&Sentinel); } + static void destroySentinel(Element *) {} + + Element *provideInitialHead() const { return createSentinel(); } + Element *ensureHead(Element *) const { return createSentinel(); } + static void noteHead(Element *, Element *) {} + +private: + mutable ilist_half_node<Element> Sentinel; +}; + template <unsigned ElementSize = 128> class SparseBitVector { typedef ilist<SparseBitVectorElement<ElementSize> > ElementList; diff --git a/include/llvm/ADT/SparseSet.h b/include/llvm/ADT/SparseSet.h index dc3db4c..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> @@ -128,8 +128,8 @@ class SparseSet { // 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. + SparseSet(const SparseSet&) LLVM_DELETED_FUNCTION; + SparseSet &operator=(const SparseSet&) LLVM_DELETED_FUNCTION; public: typedef ValueT value_type; diff --git a/include/llvm/ADT/StringExtras.h b/include/llvm/ADT/StringExtras.h index 36df5ac..9503e0f 100644 --- a/include/llvm/ADT/StringExtras.h +++ b/include/llvm/ADT/StringExtras.h @@ -14,14 +14,14 @@ #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; /// hexdigit - Return the hexadecimal character for the -/// given number \arg X (which should be less than 16). +/// given number \p X (which should be less than 16). static inline char hexdigit(unsigned X, bool LowerCase = false) { const char HexChar = LowerCase ? 'a' : 'A'; return X < 10 ? '0' + X : HexChar + X - 10; @@ -129,6 +129,25 @@ static inline unsigned HashString(StringRef Str, unsigned Result = 0) { return Result; } +/// Returns the English suffix for an ordinal integer (-st, -nd, -rd, -th). +static inline StringRef getOrdinalSuffix(unsigned Val) { + // It is critically important that we do this perfectly for + // user-written sequences with over 100 elements. + switch (Val % 100) { + case 11: + case 12: + case 13: + return "th"; + default: + switch (Val % 10) { + case 1: return "st"; + case 2: return "nd"; + case 3: return "rd"; + default: return "th"; + } + } +} + } // End llvm namespace #endif diff --git a/include/llvm/ADT/StringMap.h b/include/llvm/ADT/StringMap.h index b4497a2..0d68d11 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> @@ -290,7 +288,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); @@ -427,7 +425,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 cd84603..0e93f51 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> @@ -138,7 +137,7 @@ namespace llvm { } /// 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. + /// is lexicographically less than, equal to, or greater than the \p RHS. int compare(StringRef RHS) const { // Check the prefix for a mismatch. if (int Res = compareMemory(Data, RHS.Data, min(Length, RHS.Length))) @@ -205,13 +204,13 @@ namespace llvm { /// @name String Predicates /// @{ - /// startswith - Check if this string starts with the given \arg Prefix. + /// Check if this string starts with the given \p Prefix. bool startswith(StringRef Prefix) const { return Length >= Prefix.Length && compareMemory(Data, Prefix.Data, Prefix.Length) == 0; } - /// endswith - Check if this string ends with the given \arg Suffix. + /// Check if this string ends with the given \p Suffix. bool endswith(StringRef Suffix) const { return Length >= Suffix.Length && compareMemory(end() - Suffix.Length, Suffix.Data, Suffix.Length) == 0; @@ -221,9 +220,9 @@ namespace llvm { /// @name String Searching /// @{ - /// find - Search for the first character \arg C in the string. + /// Search for the first character \p C in the string. /// - /// \return - The index of the first occurrence of \arg C, or npos if not + /// \returns The index of the first occurrence of \p C, or npos if not /// found. size_t find(char C, size_t From = 0) const { for (size_t i = min(From, Length), e = Length; i != e; ++i) @@ -232,15 +231,15 @@ namespace llvm { return npos; } - /// find - Search for the first string \arg Str in the string. + /// Search for the first string \p Str in the string. /// - /// \return - The index of the first occurrence of \arg Str, or npos if not + /// \returns The index of the first occurrence of \p Str, or npos if not /// found. size_t find(StringRef Str, size_t From = 0) const; - /// rfind - Search for the last character \arg C in the string. + /// Search for the last character \p C in the string. /// - /// \return - The index of the last occurrence of \arg C, or npos if not + /// \returns The index of the last occurrence of \p C, or npos if not /// found. size_t rfind(char C, size_t From = npos) const { From = min(From, Length); @@ -253,61 +252,61 @@ namespace llvm { return npos; } - /// rfind - Search for the last string \arg Str in the string. + /// Search for the last string \p Str in the string. /// - /// \return - The index of the last occurrence of \arg Str, or npos if not + /// \returns The index of the last occurrence of \p Str, or npos if not /// found. size_t rfind(StringRef Str) const; - /// find_first_of - Find the first character in the string that is \arg C, - /// or npos if not found. Same as find. + /// Find the first character in the string that is \p C, or npos if not + /// found. Same as find. size_type find_first_of(char C, size_t From = 0) const { return find(C, From); } - /// find_first_of - Find the first character in the string that is in \arg - /// Chars, or npos if not found. + /// Find the first character in the string that is in \p Chars, or npos if + /// not found. /// - /// Note: O(size() + Chars.size()) + /// Complexity: O(size() + Chars.size()) size_type find_first_of(StringRef Chars, size_t From = 0) const; - /// find_first_not_of - Find the first character in the string that is not - /// \arg C or npos if not found. + /// Find the first character in the string that is not \p C or npos if not + /// found. size_type find_first_not_of(char C, size_t From = 0) const; - /// find_first_not_of - Find the first character in the string that is not - /// in the string \arg Chars, or npos if not found. + /// Find the first character in the string that is not in the string + /// \p Chars, or npos if not found. /// - /// Note: O(size() + Chars.size()) + /// Complexity: O(size() + Chars.size()) size_type find_first_not_of(StringRef Chars, size_t From = 0) const; - /// find_last_of - Find the last character in the string that is \arg C, or - /// npos if not found. + /// Find the last character in the string that is \p C, or npos if not + /// found. size_type find_last_of(char C, size_t From = npos) const { return rfind(C, From); } - /// find_last_of - Find the last character in the string that is in \arg C, - /// or npos if not found. + /// Find the last character in the string that is in \p C, or npos if not + /// found. /// - /// Note: O(size() + Chars.size()) + /// Complexity: O(size() + Chars.size()) size_type find_last_of(StringRef Chars, size_t From = npos) const; - /// find_last_not_of - Find the last character in the string that is not - /// \arg C, or npos if not found. + /// Find the last character in the string that is not \p C, or npos if not + /// found. size_type find_last_not_of(char C, size_t From = npos) const; - /// find_last_not_of - Find the last character in the string that is not in - /// \arg Chars, or npos if not found. + /// Find the last character in the string that is not in \p Chars, or + /// npos if not found. /// - /// Note: O(size() + Chars.size()) + /// Complexity: O(size() + Chars.size()) size_type find_last_not_of(StringRef Chars, size_t From = npos) const; /// @} /// @name Helpful Algorithms /// @{ - /// count - Return the number of occurrences of \arg C in the string. + /// Return the number of occurrences of \p C in the string. size_t count(char C) const { size_t Count = 0; for (size_t i = 0, e = Length; i != e; ++i) @@ -316,18 +315,17 @@ namespace llvm { return Count; } - /// count - Return the number of non-overlapped occurrences of \arg Str in + /// Return the number of non-overlapped occurrences of \p Str in /// the string. size_t count(StringRef Str) const; - /// getAsInteger - Parse the current string as an integer of the specified - /// radix. If Radix is specified as zero, this does radix autosensing using + /// Parse the current string as an integer of the specified radix. If + /// \p Radix is specified as zero, this does radix autosensing using /// extended C rules: 0 is octal, 0x is hex, 0b is binary. /// /// 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 or if it overflows T. - /// template <typename T> typename enable_if_c<std::numeric_limits<T>::is_signed, bool>::type getAsInteger(unsigned Radix, T &Result) const { @@ -350,13 +348,12 @@ namespace llvm { return false; } - /// getAsInteger - Parse the current string as an integer of the - /// specified radix, or of an autosensed radix if the radix given - /// is 0. The current value in Result is discarded, and the - /// storage is changed to be wide enough to store the parsed - /// integer. + /// Parse the current string as an integer of the specified \p Radix, or of + /// an autosensed radix if the \p Radix given is 0. The current value in + /// \p Result is discarded, and the storage is changed to be wide enough to + /// store the parsed integer. /// - /// Returns true if the string does not solely consist of a valid + /// \returns true if the string does not solely consist of a valid /// non-empty number in the appropriate base. /// /// APInt::fromString is superficially similar but assumes the @@ -367,70 +364,70 @@ namespace llvm { /// @name String Operations /// @{ - // lower - Convert the given ASCII string to lowercase. + // Convert the given ASCII string to lowercase. std::string lower() const; - /// upper - Convert the given ASCII string to uppercase. + /// Convert the given ASCII string to uppercase. std::string upper() const; /// @} /// @name Substring Operations /// @{ - /// substr - Return a reference to the substring from [Start, Start + N). + /// Return a reference to the substring from [Start, Start + N). /// - /// \param Start - The index of the starting character in the substring; if + /// \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 + /// \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. + /// suffix (starting with \p Start) will be returned. StringRef substr(size_t Start, size_t N = npos) const { Start = min(Start, Length); return StringRef(Data + Start, min(N, Length - Start)); } - /// drop_front - Return a StringRef equal to 'this' but with the first - /// elements dropped. + /// Return a StringRef equal to 'this' but with the first \p N 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. + /// Return a StringRef equal to 'this' but with the last \p N 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). + /// Return a reference to the substring from [Start, End). /// - /// \param Start - The index of the starting character in the substring; if + /// \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 + /// \param End The index following the last character to include in the + /// substring. If this is npos, or less than \p Start, or exceeds the /// number of characters remaining in the string, the string suffix - /// (starting with \arg Start) will be returned. + /// (starting with \p Start) will be returned. StringRef slice(size_t Start, size_t End) const { Start = min(Start, Length); End = min(max(Start, End), Length); return StringRef(Data + Start, End - Start); } - /// split - Split into two substrings around the first occurrence of a - /// separator character. + /// Split into two substrings around the first occurrence of a separator + /// character. /// - /// If \arg Separator is in the string, then the result is a pair (LHS, RHS) + /// If \p Separator is in the string, then the result is a pair (LHS, RHS) /// such that (*this == LHS + Separator + RHS) is true and RHS is - /// maximal. If \arg Separator is not in the string, then the result is a + /// maximal. If \p Separator is not in the string, then the result is a /// pair (LHS, RHS) where (*this == LHS) and (RHS == ""). /// - /// \param Separator - The character to split on. - /// \return - The split substrings. + /// \param Separator The character to split on. + /// \returns The split substrings. std::pair<StringRef, StringRef> split(char Separator) const { size_t Idx = find(Separator); if (Idx == npos) @@ -438,12 +435,12 @@ namespace llvm { return std::make_pair(slice(0, Idx), slice(Idx+1, npos)); } - /// split - Split into two substrings around the first occurrence of a - /// separator string. + /// Split into two substrings around the first occurrence of a separator + /// string. /// - /// If \arg Separator is in the string, then the result is a pair (LHS, RHS) + /// If \p Separator is in the string, then the result is a pair (LHS, RHS) /// such that (*this == LHS + Separator + RHS) is true and RHS is - /// maximal. If \arg Separator is not in the string, then the result is a + /// maximal. If \p Separator is not in the string, then the result is a /// pair (LHS, RHS) where (*this == LHS) and (RHS == ""). /// /// \param Separator - The string to split on. @@ -455,14 +452,13 @@ namespace llvm { return std::make_pair(slice(0, Idx), slice(Idx + Separator.size(), npos)); } - /// split - Split into substrings around the occurrences of a separator - /// string. + /// Split into substrings around the occurrences of a separator string. /// - /// Each substring is stored in \arg A. If \arg MaxSplit is >= 0, at most - /// \arg MaxSplit splits are done and consequently <= \arg MaxSplit + /// Each substring is stored in \p A. If \p MaxSplit is >= 0, at most + /// \p MaxSplit splits are done and consequently <= \p MaxSplit /// elements are added to A. - /// If \arg KeepEmpty is false, empty strings are not added to \arg A. They - /// still count when considering \arg MaxSplit + /// If \p KeepEmpty is false, empty strings are not added to \p A. They + /// still count when considering \p MaxSplit /// An useful invariant is that /// Separator.join(A) == *this if MaxSplit == -1 and KeepEmpty == true /// @@ -474,12 +470,12 @@ namespace llvm { StringRef Separator, int MaxSplit = -1, bool KeepEmpty = true) const; - /// rsplit - Split into two substrings around the last occurrence of a - /// separator character. + /// Split into two substrings around the last occurrence of a separator + /// character. /// - /// If \arg Separator is in the string, then the result is a pair (LHS, RHS) + /// If \p Separator is in the string, then the result is a pair (LHS, RHS) /// such that (*this == LHS + Separator + RHS) is true and RHS is - /// minimal. If \arg Separator is not in the string, then the result is a + /// minimal. If \p Separator is not in the string, then the result is a /// pair (LHS, RHS) where (*this == LHS) and (RHS == ""). /// /// \param Separator - The character to split on. @@ -491,20 +487,20 @@ namespace llvm { return std::make_pair(slice(0, Idx), slice(Idx+1, npos)); } - /// ltrim - Return string with consecutive characters in \arg Chars starting - /// from the left removed. + /// Return string with consecutive characters in \p Chars starting from + /// the left removed. StringRef ltrim(StringRef Chars = " \t\n\v\f\r") const { return drop_front(std::min(Length, find_first_not_of(Chars))); } - /// rtrim - Return string with consecutive characters in \arg Chars starting - /// from the right removed. + /// Return string with consecutive characters in \p Chars starting from + /// the right removed. StringRef rtrim(StringRef Chars = " \t\n\v\f\r") const { return drop_back(Length - std::min(Length, find_last_not_of(Chars) + 1)); } - /// trim - Return string with consecutive characters in \arg Chars starting - /// from the left and right removed. + /// Return string with consecutive characters in \p Chars starting from + /// the left and right removed. StringRef trim(StringRef Chars = " \t\n\v\f\r") const { return ltrim(Chars).rtrim(Chars); } diff --git a/include/llvm/ADT/StringSet.h b/include/llvm/ADT/StringSet.h index 9c55f6b..b69a964 100644 --- a/include/llvm/ADT/StringSet.h +++ b/include/llvm/ADT/StringSet.h @@ -29,8 +29,13 @@ namespace llvm { assert(!InLang.empty()); const char *KeyStart = InLang.data(); const char *KeyEnd = KeyStart + InLang.size(); - return base::insert(llvm::StringMapEntry<char>:: - Create(KeyStart, KeyEnd, base::getAllocator(), '+')); + llvm::StringMapEntry<char> *Entry = llvm::StringMapEntry<char>:: + Create(KeyStart, KeyEnd, base::getAllocator(), '+'); + if (!base::insert(Entry)) { + Entry->Destroy(base::getAllocator()); + return false; + } + 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 ab1f0da..49d9f68 100644 --- a/include/llvm/ADT/Triple.h +++ b/include/llvm/ADT/Triple.h @@ -44,7 +44,6 @@ public: UnknownArch, arm, // ARM; arm, armv.*, xscale - cellspu, // CellSPU: spu, cellspu hexagon, // Hexagon: hexagon mips, // MIPS: mips, mipsallegrex mipsel, // MIPSEL: mipsel, mipsallegrexel @@ -65,7 +64,9 @@ public: nvptx, // NVPTX: 32-bit nvptx64, // NVPTX: 64-bit le32, // le32: generic little-endian 32-bit CPU (PNaCl / Emscripten) - amdil // amdil: amd IL + amdil, // amdil: amd IL + spir, // SPIR: standard portable IR for OpenCL 32-bit version + spir64 // SPIR: standard portable IR for OpenCL 64-bit version }; enum VendorType { UnknownVendor, @@ -75,7 +76,8 @@ public: SCEI, BGP, BGQ, - Freescale + Freescale, + IBM }; enum OSType { UnknownOS, @@ -98,9 +100,10 @@ public: Haiku, Minix, RTEMS, - NativeClient, - CNK, // BG/P Compute-Node Kernel - Bitrig + NaCl, // Native Client + CNK, // BG/P Compute-Node Kernel + Bitrig, + AIX }; enum EnvironmentType { UnknownEnvironment, @@ -110,7 +113,8 @@ public: GNUEABIHF, EABI, MachO, - Android + Android, + ELF }; private: @@ -306,6 +310,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(); @@ -342,7 +351,7 @@ public: /// to a known type. void setEnvironment(EnvironmentType Kind); - /// setTriple - Set all components to the new triple \arg Str. + /// setTriple - Set all components to the new triple \p Str. void setTriple(const Twine &Str); /// setArchName - Set the architecture (first) component of the @@ -393,11 +402,10 @@ public: /// @name Static helpers for IDs. /// @{ - /// getArchTypeName - Get the canonical name for the \arg Kind - /// architecture. + /// getArchTypeName - Get the canonical name for the \p Kind architecture. static const char *getArchTypeName(ArchType Kind); - /// getArchTypePrefix - Get the "prefix" canonical name for the \arg Kind + /// getArchTypePrefix - Get the "prefix" canonical name for the \p Kind /// architecture. This is the prefix used by the architecture specific /// builtins, and is suitable for passing to \see /// Intrinsic::getIntrinsicForGCCBuiltin(). @@ -405,15 +413,13 @@ public: /// \return - The architecture prefix, or 0 if none is defined. static const char *getArchTypePrefix(ArchType Kind); - /// getVendorTypeName - Get the canonical name for the \arg Kind - /// vendor. + /// getVendorTypeName - Get the canonical name for the \p Kind vendor. static const char *getVendorTypeName(VendorType Kind); - /// getOSTypeName - Get the canonical name for the \arg Kind operating - /// system. + /// getOSTypeName - Get the canonical name for the \p Kind operating system. static const char *getOSTypeName(OSType Kind); - /// getEnvironmentTypeName - Get the canonical name for the \arg Kind + /// getEnvironmentTypeName - Get the canonical name for the \p Kind /// environment. static const char *getEnvironmentTypeName(EnvironmentType Kind); @@ -425,11 +431,6 @@ public: /// architecture name (e.g., "x86"). static ArchType getArchTypeForLLVMName(StringRef Str); - /// getArchTypeForDarwinArchName - Get the architecture type for a "Darwin" - /// architecture name, for example as accepted by "gcc -arch" (see also - /// arch(3)). - static ArchType getArchTypeForDarwinArchName(StringRef Str); - /// @} }; diff --git a/include/llvm/ADT/Twine.h b/include/llvm/ADT/Twine.h index 9101df8..cc290d5 100644 --- a/include/llvm/ADT/Twine.h +++ b/include/llvm/ADT/Twine.h @@ -44,7 +44,7 @@ namespace llvm { /// itself, and renders as an empty string. This can be returned from APIs to /// effectively nullify any concatenations performed on the result. /// - /// \b Implementation \n + /// \b Implementation /// /// Given the nature of a Twine, it is not possible for the Twine's /// concatenation method to construct interior nodes; the result must be @@ -67,7 +67,7 @@ namespace llvm { /// /// These invariants are check by \see isValid(). /// - /// \b Efficiency Considerations \n + /// \b Efficiency Considerations /// /// The Twine is designed to yield efficient and small code for common /// situations. For this reason, the concat() method is inlined so that @@ -303,37 +303,37 @@ namespace llvm { LHS.character = static_cast<char>(Val); } - /// Construct a twine to print \arg Val as an unsigned decimal integer. + /// Construct a twine to print \p Val as an unsigned decimal integer. explicit Twine(unsigned Val) : LHSKind(DecUIKind), RHSKind(EmptyKind) { LHS.decUI = Val; } - /// Construct a twine to print \arg Val as a signed decimal integer. + /// Construct a twine to print \p Val as a signed decimal integer. explicit Twine(int Val) : LHSKind(DecIKind), RHSKind(EmptyKind) { LHS.decI = Val; } - /// Construct a twine to print \arg Val as an unsigned decimal integer. + /// Construct a twine to print \p Val as an unsigned decimal integer. explicit Twine(const unsigned long &Val) : LHSKind(DecULKind), RHSKind(EmptyKind) { LHS.decUL = &Val; } - /// Construct a twine to print \arg Val as a signed decimal integer. + /// Construct a twine to print \p Val as a signed decimal integer. explicit Twine(const long &Val) : LHSKind(DecLKind), RHSKind(EmptyKind) { LHS.decL = &Val; } - /// Construct a twine to print \arg Val as an unsigned decimal integer. + /// Construct a twine to print \p Val as an unsigned decimal integer. explicit Twine(const unsigned long long &Val) : LHSKind(DecULLKind), RHSKind(EmptyKind) { LHS.decULL = &Val; } - /// Construct a twine to print \arg Val as a signed decimal integer. + /// Construct a twine to print \p Val as a signed decimal integer. explicit Twine(const long long &Val) : LHSKind(DecLLKind), RHSKind(EmptyKind) { LHS.decLL = &Val; @@ -370,7 +370,7 @@ namespace llvm { /// @name Numeric Conversions /// @{ - // Construct a twine to print \arg Val as an unsigned hexadecimal integer. + // Construct a twine to print \p Val as an unsigned hexadecimal integer. static Twine utohexstr(const uint64_t &Val) { Child LHS, RHS; LHS.uHex = &Val; @@ -447,17 +447,17 @@ namespace llvm { /// The returned StringRef's size does not include the null terminator. StringRef toNullTerminatedStringRef(SmallVectorImpl<char> &Out) const; - /// print - Write the concatenated string represented by this twine to the - /// stream \arg OS. + /// Write the concatenated string represented by this twine to the + /// stream \p OS. void print(raw_ostream &OS) const; - /// dump - Dump the concatenated string represented by this twine to stderr. + /// Dump the concatenated string represented by this twine to stderr. void dump() const; - /// print - Write the representation of this twine to the stream \arg OS. + /// Write the representation of this twine to the stream \p OS. void printRepr(raw_ostream &OS) const; - /// dumpRepr - Dump the representation of this twine to stderr. + /// Dump the representation of this twine to stderr. void dumpRepr() const; /// @} diff --git a/include/llvm/ADT/ValueMap.h b/include/llvm/ADT/ValueMap.h index f7e2551..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 { @@ -80,8 +79,8 @@ class ValueMap { typedef typename Config::ExtraData ExtraData; MapT Map; ExtraData Data; - ValueMap(const ValueMap&); // DO NOT IMPLEMENT - ValueMap& operator=(const ValueMap&); // DO NOT IMPLEMENT + ValueMap(const ValueMap&) LLVM_DELETED_FUNCTION; + ValueMap& operator=(const ValueMap&) LLVM_DELETED_FUNCTION; public: typedef KeyT key_type; typedef ValueT mapped_type; diff --git a/include/llvm/ADT/ilist.h b/include/llvm/ADT/ilist.h index ba9864a..20cdae3 100644 --- a/include/llvm/ADT/ilist.h +++ b/include/llvm/ADT/ilist.h @@ -38,6 +38,7 @@ #ifndef LLVM_ADT_ILIST_H #define LLVM_ADT_ILIST_H +#include "llvm/Support/Compiler.h" #include <algorithm> #include <cassert> #include <cstddef> @@ -331,8 +332,8 @@ class iplist : public Traits { // No fundamental reason why iplist can't be copyable, but the default // copy/copy-assign won't do. - iplist(const iplist &); // do not implement - void operator=(const iplist &); // do not implement + iplist(const iplist &) LLVM_DELETED_FUNCTION; + void operator=(const iplist &) LLVM_DELETED_FUNCTION; public: typedef NodeTy *pointer; @@ -464,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 @@ -471,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 |