diff options
Diffstat (limited to 'include/llvm/ADT')
| -rw-r--r-- | include/llvm/ADT/DAGDeltaAlgorithm.h | 75 | ||||
| -rw-r--r-- | include/llvm/ADT/DenseMap.h | 1 | ||||
| -rw-r--r-- | include/llvm/ADT/EquivalenceClasses.h | 2 | ||||
| -rw-r--r-- | include/llvm/ADT/FoldingSet.h | 83 | ||||
| -rw-r--r-- | include/llvm/ADT/ImmutableIntervalMap.h | 12 | ||||
| -rw-r--r-- | include/llvm/ADT/PostOrderIterator.h | 17 | ||||
| -rw-r--r-- | include/llvm/ADT/SetVector.h | 8 | ||||
| -rw-r--r-- | include/llvm/ADT/SmallPtrSet.h | 49 | ||||
| -rw-r--r-- | include/llvm/ADT/SmallVector.h | 160 | ||||
| -rw-r--r-- | include/llvm/ADT/Statistic.h | 4 | ||||
| -rw-r--r-- | include/llvm/ADT/Triple.h | 7 | ||||
| -rw-r--r-- | include/llvm/ADT/ValueMap.h | 6 | ||||
| -rw-r--r-- | include/llvm/ADT/ilist.h | 1 |
13 files changed, 303 insertions, 122 deletions
diff --git a/include/llvm/ADT/DAGDeltaAlgorithm.h b/include/llvm/ADT/DAGDeltaAlgorithm.h new file mode 100644 index 0000000..99ed15c --- /dev/null +++ b/include/llvm/ADT/DAGDeltaAlgorithm.h @@ -0,0 +1,75 @@ +//===--- DAGDeltaAlgorithm.h - A DAG Minimization Algorithm ----*- C++ -*--===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +//===----------------------------------------------------------------------===// + +#ifndef LLVM_ADT_DAGDELTAALGORITHM_H +#define LLVM_ADT_DAGDELTAALGORITHM_H + +#include <vector> +#include <set> + +namespace llvm { + +/// DAGDeltaAlgorithm - Implements a "delta debugging" algorithm for minimizing +/// directed acyclic graphs using a predicate function. +/// +/// The result of the algorithm is a subset of the input change set which is +/// guaranteed to satisfy the predicate, assuming that the input set did. For +/// well formed predicates, the result set is guaranteed to be such that +/// removing any single element not required by the dependencies on the other +/// elements would falsify the predicate. +/// +/// The DAG should be used to represent dependencies in the changes which are +/// likely to hold across the predicate function. That is, for a particular +/// changeset S and predicate P: +/// +/// P(S) => P(S union pred(S)) +/// +/// The minization algorithm uses this dependency information to attempt to +/// eagerly prune large subsets of changes. As with \see DeltaAlgorithm, the DAG +/// is not required to satisfy this property, but the algorithm will run +/// substantially fewer tests with appropriate dependencies. \see DeltaAlgorithm +/// for more information on the properties which the predicate function itself +/// should satisfy. +class DAGDeltaAlgorithm { +public: + typedef unsigned change_ty; + typedef std::pair<change_ty, change_ty> edge_ty; + + // FIXME: Use a decent data structure. + typedef std::set<change_ty> changeset_ty; + typedef std::vector<changeset_ty> changesetlist_ty; + +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 + /// changes and returning the smallest set which still satisfies the test + /// predicate and the input \arg 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. + changeset_ty Run(const changeset_ty &Changes, + const std::vector<edge_ty> &Dependencies); + + /// UpdatedSearchState - Callback used when the search state changes. + virtual void UpdatedSearchState(const changeset_ty &Changes, + const changesetlist_ty &Sets, + const changeset_ty &Required) {} + + /// ExecuteOneTest - Execute a single test predicate on the change set \arg S. + virtual bool ExecuteOneTest(const changeset_ty &S) = 0; +}; + +} // end namespace llvm + +#endif diff --git a/include/llvm/ADT/DenseMap.h b/include/llvm/ADT/DenseMap.h index 5c99473..c53e255 100644 --- a/include/llvm/ADT/DenseMap.h +++ b/include/llvm/ADT/DenseMap.h @@ -22,6 +22,7 @@ #include <new> #include <utility> #include <cassert> +#include <cstddef> #include <cstring> namespace llvm { diff --git a/include/llvm/ADT/EquivalenceClasses.h b/include/llvm/ADT/EquivalenceClasses.h index 91a1429..07a5edf 100644 --- a/include/llvm/ADT/EquivalenceClasses.h +++ b/include/llvm/ADT/EquivalenceClasses.h @@ -169,7 +169,7 @@ public: /// getOrInsertLeaderValue - Return the leader for the specified value that is /// in the set. If the member is not in the set, it is inserted, then /// returned. - const ElemTy &getOrInsertLeaderValue(const ElemTy &V) const { + const ElemTy &getOrInsertLeaderValue(const ElemTy &V) { member_iterator MI = findLeader(insert(V)); assert(MI != member_end() && "Value is not in the set!"); return *MI; diff --git a/include/llvm/ADT/FoldingSet.h b/include/llvm/ADT/FoldingSet.h index e8979bb..fc8490a 100644 --- a/include/llvm/ADT/FoldingSet.h +++ b/include/llvm/ADT/FoldingSet.h @@ -166,6 +166,14 @@ public: /// FindNodeOrInsertPos. void InsertNode(Node *N, void *InsertPos); + /// InsertNode - Insert the specified node into the folding set, knowing that + /// it is not already in the folding set. + void InsertNode(Node *N) { + Node *Inserted = GetOrInsertNode(N); + (void)Inserted; + assert(Inserted == N && "Node already inserted!"); + } + /// size - Returns the number of nodes in the folding set. unsigned size() const { return NumNodes; } @@ -196,6 +204,10 @@ protected: template<typename T> struct FoldingSetTrait { static inline void Profile(const T& X, FoldingSetNodeID& ID) { X.Profile(ID);} static inline void Profile(T& X, FoldingSetNodeID& ID) { X.Profile(ID); } + template <typename Ctx> + static inline void Profile(T &X, FoldingSetNodeID &ID, Ctx Context) { + X.Profile(ID, Context); + } }; //===--------------------------------------------------------------------===// @@ -322,6 +334,77 @@ public: }; //===----------------------------------------------------------------------===// +/// ContextualFoldingSet - This template class is a further refinement +/// of FoldingSet which provides a context argument when calling +/// Profile on its nodes. Currently, that argument is fixed at +/// initialization time. +/// +/// T must be a subclass of FoldingSetNode and implement a Profile +/// function with signature +/// void Profile(llvm::FoldingSetNodeID &, Ctx); +template <class T, class Ctx> +class ContextualFoldingSet : public FoldingSetImpl { + // Unfortunately, this can't derive from FoldingSet<T> because the + // construction vtable for FoldingSet<T> requires + // FoldingSet<T>::GetNodeProfile to be instantiated, which in turn + // requires a single-argument T::Profile(). + +private: + Ctx Context; + + /// GetNodeProfile - Each instantiatation of the FoldingSet needs to provide a + /// way to convert nodes into a unique specifier. + virtual void GetNodeProfile(FoldingSetNodeID &ID, + FoldingSetImpl::Node *N) const { + T *TN = static_cast<T *>(N); + + // We must use explicit template arguments in case Ctx is a + // reference type. + FoldingSetTrait<T>::template Profile<Ctx>(*TN, ID, Context); + } + +public: + explicit ContextualFoldingSet(Ctx Context, unsigned Log2InitSize = 6) + : FoldingSetImpl(Log2InitSize), Context(Context) + {} + + Ctx getContext() const { return Context; } + + + typedef FoldingSetIterator<T> iterator; + iterator begin() { return iterator(Buckets); } + iterator end() { return iterator(Buckets+NumBuckets); } + + typedef FoldingSetIterator<const T> const_iterator; + const_iterator begin() const { return const_iterator(Buckets); } + const_iterator end() const { return const_iterator(Buckets+NumBuckets); } + + typedef FoldingSetBucketIterator<T> bucket_iterator; + + bucket_iterator bucket_begin(unsigned hash) { + return bucket_iterator(Buckets + (hash & (NumBuckets-1))); + } + + bucket_iterator bucket_end(unsigned hash) { + return bucket_iterator(Buckets + (hash & (NumBuckets-1)), true); + } + + /// GetOrInsertNode - If there is an existing simple Node exactly + /// equal to the specified node, return it. Otherwise, insert 'N' + /// and return it instead. + T *GetOrInsertNode(Node *N) { + return static_cast<T *>(FoldingSetImpl::GetOrInsertNode(N)); + } + + /// FindNodeOrInsertPos - Look up the node specified by ID. If it + /// exists, return it. If not, return the insertion token that will + /// make insertion faster. + T *FindNodeOrInsertPos(const FoldingSetNodeID &ID, void *&InsertPos) { + return static_cast<T *>(FoldingSetImpl::FindNodeOrInsertPos(ID, InsertPos)); + } +}; + +//===----------------------------------------------------------------------===// /// FoldingSetIteratorImpl - This is the common iterator support shared by all /// folding sets, which knows how to walk the folding set hash table. class FoldingSetIteratorImpl { diff --git a/include/llvm/ADT/ImmutableIntervalMap.h b/include/llvm/ADT/ImmutableIntervalMap.h index f33fb1e..7aa3155 100644 --- a/include/llvm/ADT/ImmutableIntervalMap.h +++ b/include/llvm/ADT/ImmutableIntervalMap.h @@ -125,9 +125,11 @@ private: key_type_ref KCurrent = ImutInfo::KeyOfValue(this->Value(T)); if (ImutInfo::isLess(K, KCurrent)) - return this->Balance(Add_internal(V, this->Left(T)), this->Value(T), this->Right(T)); + return this->Balance(Add_internal(V, this->Left(T)), this->Value(T), + this->Right(T)); else - return this->Balance(this->Left(T), this->Value(T), Add_internal(V, this->Right(T))); + return this->Balance(this->Left(T), this->Value(T), + Add_internal(V, this->Right(T))); } // Remove all overlaps from T. @@ -150,9 +152,11 @@ private: // If current key does not overlap the inserted key. if (CurrentK.getStart() > K.getEnd()) - return this->Balance(RemoveOverlap(this->Left(T), K, Changed), this->Value(T), this->Right(T)); + return this->Balance(RemoveOverlap(this->Left(T), K, Changed), + this->Value(T), this->Right(T)); else if (CurrentK.getEnd() < K.getStart()) - return this->Balance(this->Left(T), this->Value(T), RemoveOverlap(this->Right(T), K, Changed)); + return this->Balance(this->Left(T), this->Value(T), + RemoveOverlap(this->Right(T), K, Changed)); // Current key overlaps with the inserted key. // Remove the current key. diff --git a/include/llvm/ADT/PostOrderIterator.h b/include/llvm/ADT/PostOrderIterator.h index 8315bc9..47e5b2b 100644 --- a/include/llvm/ADT/PostOrderIterator.h +++ b/include/llvm/ADT/PostOrderIterator.h @@ -19,7 +19,6 @@ #include "llvm/ADT/GraphTraits.h" #include "llvm/ADT/SmallPtrSet.h" #include <set> -#include <stack> #include <vector> namespace llvm { @@ -52,21 +51,21 @@ class po_iterator : public std::iterator<std::forward_iterator_tag, // VisitStack - Used to maintain the ordering. Top = current block // First element is basic block pointer, second is the 'next child' to visit - std::stack<std::pair<NodeType *, ChildItTy> > VisitStack; + std::vector<std::pair<NodeType *, ChildItTy> > VisitStack; void traverseChild() { - while (VisitStack.top().second != GT::child_end(VisitStack.top().first)) { - NodeType *BB = *VisitStack.top().second++; + while (VisitStack.back().second != GT::child_end(VisitStack.back().first)) { + NodeType *BB = *VisitStack.back().second++; if (!this->Visited.count(BB)) { // If the block is not visited... this->Visited.insert(BB); - VisitStack.push(std::make_pair(BB, GT::child_begin(BB))); + VisitStack.push_back(std::make_pair(BB, GT::child_begin(BB))); } } } inline po_iterator(NodeType *BB) { this->Visited.insert(BB); - VisitStack.push(std::make_pair(BB, GT::child_begin(BB))); + VisitStack.push_back(std::make_pair(BB, GT::child_begin(BB))); traverseChild(); } inline po_iterator() {} // End is when stack is empty. @@ -75,7 +74,7 @@ class po_iterator : public std::iterator<std::forward_iterator_tag, po_iterator_storage<SetType, ExtStorage>(S) { if(!S.count(BB)) { this->Visited.insert(BB); - VisitStack.push(std::make_pair(BB, GT::child_begin(BB))); + VisitStack.push_back(std::make_pair(BB, GT::child_begin(BB))); traverseChild(); } } @@ -102,7 +101,7 @@ public: inline bool operator!=(const _Self& x) const { return !operator==(x); } inline pointer operator*() const { - return VisitStack.top().first; + return VisitStack.back().first; } // This is a nonstandard operator-> that dereferences the pointer an extra @@ -112,7 +111,7 @@ public: inline NodeType *operator->() const { return operator*(); } inline _Self& operator++() { // Preincrement - VisitStack.pop(); + VisitStack.pop_back(); if (!VisitStack.empty()) traverseChild(); return *this; diff --git a/include/llvm/ADT/SetVector.h b/include/llvm/ADT/SetVector.h index fab133a..bf8286c 100644 --- a/include/llvm/ADT/SetVector.h +++ b/include/llvm/ADT/SetVector.h @@ -143,6 +143,14 @@ public: vector_.pop_back(); } + bool operator==(const SetVector &that) const { + return vector_ == that.vector_; + } + + bool operator!=(const SetVector &that) const { + return vector_ != that.vector_; + } + private: set_type set_; ///< The set. vector_type vector_; ///< The vector. diff --git a/include/llvm/ADT/SmallPtrSet.h b/include/llvm/ADT/SmallPtrSet.h index ef08125..424bdba 100644 --- a/include/llvm/ADT/SmallPtrSet.h +++ b/include/llvm/ADT/SmallPtrSet.h @@ -46,8 +46,10 @@ class SmallPtrSetIteratorImpl; class SmallPtrSetImpl { friend class SmallPtrSetIteratorImpl; protected: - /// CurArray - This is the current set of buckets. If it points to - /// SmallArray, then the set is in 'small mode'. + /// SmallArray - Points to a fixed size set of buckets, used in 'small mode'. + const void **SmallArray; + /// CurArray - This is the current set of buckets. If equal to SmallArray, + /// then the set is in 'small mode'. const void **CurArray; /// CurArraySize - The allocated size of CurArray, always a power of two. /// Note that CurArray points to an array that has CurArraySize+1 elements in @@ -57,15 +59,13 @@ protected: // If small, this is # elts allocated consequtively unsigned NumElements; unsigned NumTombstones; - const void *SmallArray[1]; // Must be last ivar. // Helper to copy construct a SmallPtrSet. - SmallPtrSetImpl(const SmallPtrSetImpl& that); - explicit SmallPtrSetImpl(unsigned SmallSize) { + SmallPtrSetImpl(const void **SmallStorage, const SmallPtrSetImpl& that); + explicit SmallPtrSetImpl(const void **SmallStorage, unsigned SmallSize) : + SmallArray(SmallStorage), CurArray(SmallStorage), CurArraySize(SmallSize) { assert(SmallSize && (SmallSize & (SmallSize-1)) == 0 && "Initial size must be a power of two!"); - CurArray = &SmallArray[0]; - CurArraySize = SmallSize; // The end pointer, always valid, is set to a valid element to help the // iterator. CurArray[SmallSize] = 0; @@ -123,7 +123,7 @@ protected: } private: - bool isSmall() const { return CurArray == &SmallArray[0]; } + bool isSmall() const { return CurArray == SmallArray; } unsigned Hash(const void *Ptr) const { return static_cast<unsigned>(((uintptr_t)Ptr >> 4) & (CurArraySize-1)); @@ -199,29 +199,29 @@ public: } }; -/// NextPowerOfTwo - This is a helper template that rounds N up to the next -/// power of two. +/// RoundUpToPowerOfTwo - This is a helper template that rounds N up to the next +/// power of two (which means N itself if N is already a power of two). template<unsigned N> -struct NextPowerOfTwo; +struct RoundUpToPowerOfTwo; -/// NextPowerOfTwoH - If N is not a power of two, increase it. This is a helper -/// template used to implement NextPowerOfTwo. +/// RoundUpToPowerOfTwoH - If N is not a power of two, increase it. This is a +/// helper template used to implement RoundUpToPowerOfTwo. template<unsigned N, bool isPowerTwo> -struct NextPowerOfTwoH { +struct RoundUpToPowerOfTwoH { enum { Val = N }; }; template<unsigned N> -struct NextPowerOfTwoH<N, false> { +struct RoundUpToPowerOfTwoH<N, false> { enum { // We could just use NextVal = N+1, but this converges faster. N|(N-1) sets // the right-most zero bits to one all at once, e.g. 0b0011000 -> 0b0011111. - Val = NextPowerOfTwo<(N|(N-1)) + 1>::Val + Val = RoundUpToPowerOfTwo<(N|(N-1)) + 1>::Val }; }; template<unsigned N> -struct NextPowerOfTwo { - enum { Val = NextPowerOfTwoH<N, (N&(N-1)) == 0>::Val }; +struct RoundUpToPowerOfTwo { + enum { Val = RoundUpToPowerOfTwoH<N, (N&(N-1)) == 0>::Val }; }; @@ -232,16 +232,17 @@ struct NextPowerOfTwo { template<class PtrType, unsigned SmallSize> class SmallPtrSet : public SmallPtrSetImpl { // Make sure that SmallSize is a power of two, round up if not. - enum { SmallSizePowTwo = NextPowerOfTwo<SmallSize>::Val }; - void *SmallArray[SmallSizePowTwo]; + enum { SmallSizePowTwo = RoundUpToPowerOfTwo<SmallSize>::Val }; + /// SmallStorage - Fixed size storage used in 'small mode'. The extra element + /// ensures that the end iterator actually points to valid memory. + const void *SmallStorage[SmallSizePowTwo+1]; typedef PointerLikeTypeTraits<PtrType> PtrTraits; public: - SmallPtrSet() : SmallPtrSetImpl(NextPowerOfTwo<SmallSizePowTwo>::Val) {} - SmallPtrSet(const SmallPtrSet &that) : SmallPtrSetImpl(that) {} + SmallPtrSet() : SmallPtrSetImpl(SmallStorage, SmallSizePowTwo) {} + SmallPtrSet(const SmallPtrSet &that) : SmallPtrSetImpl(SmallStorage, that) {} template<typename It> - SmallPtrSet(It I, It E) - : SmallPtrSetImpl(NextPowerOfTwo<SmallSizePowTwo>::Val) { + SmallPtrSet(It I, It E) : SmallPtrSetImpl(SmallStorage, SmallSizePowTwo) { insert(I, E); } diff --git a/include/llvm/ADT/SmallVector.h b/include/llvm/ADT/SmallVector.h index 18c8619..fa61d20 100644 --- a/include/llvm/ADT/SmallVector.h +++ b/include/llvm/ADT/SmallVector.h @@ -17,6 +17,8 @@ #include "llvm/Support/type_traits.h" #include <algorithm> #include <cassert> +#include <cstddef> +#include <cstdlib> #include <cstring> #include <memory> @@ -70,35 +72,35 @@ protected: #endif } FirstEl; // Space after 'FirstEl' is clobbered, do not add any instance vars after it. - + protected: SmallVectorBase(size_t Size) : BeginX(&FirstEl), EndX(&FirstEl), CapacityX((char*)&FirstEl+Size) {} - + /// isSmall - Return true if this is a smallvector which has not had dynamic /// memory allocated for it. bool isSmall() const { return BeginX == static_cast<const void*>(&FirstEl); } - + /// size_in_bytes - This returns size()*sizeof(T). size_t size_in_bytes() const { return size_t((char*)EndX - (char*)BeginX); } - + /// capacity_in_bytes - This returns capacity()*sizeof(T). size_t capacity_in_bytes() const { return size_t((char*)CapacityX - (char*)BeginX); } - + /// grow_pod - This is an implementation of the grow() method which only works /// on POD-like datatypes and is out of line to reduce code duplication. void grow_pod(size_t MinSizeInBytes, size_t TSize); - + public: bool empty() const { return BeginX == EndX; } }; - + template <typename T> class SmallVectorTemplateCommon : public SmallVectorBase { @@ -106,21 +108,21 @@ protected: void setEnd(T *P) { this->EndX = P; } public: SmallVectorTemplateCommon(size_t Size) : SmallVectorBase(Size) {} - + typedef size_t size_type; typedef ptrdiff_t difference_type; typedef T value_type; typedef T *iterator; typedef const T *const_iterator; - + typedef std::reverse_iterator<const_iterator> const_reverse_iterator; typedef std::reverse_iterator<iterator> reverse_iterator; - + typedef T &reference; typedef const T &const_reference; typedef T *pointer; typedef const T *const_pointer; - + // forward iterator creation methods. iterator begin() { return (iterator)this->BeginX; } const_iterator begin() const { return (const_iterator)this->BeginX; } @@ -130,7 +132,7 @@ protected: iterator capacity_ptr() { return (iterator)this->CapacityX; } const_iterator capacity_ptr() const { return (const_iterator)this->CapacityX;} public: - + // reverse iterator creation methods. reverse_iterator rbegin() { return reverse_iterator(end()); } const_reverse_iterator rbegin() const{ return const_reverse_iterator(end()); } @@ -139,16 +141,16 @@ public: size_type size() const { return end()-begin(); } size_type max_size() const { return size_type(-1) / sizeof(T); } - + /// capacity - Return the total number of elements in the currently allocated /// buffer. size_t capacity() const { return capacity_ptr() - begin(); } - + /// data - Return a pointer to the vector's buffer, even if empty(). pointer data() { return pointer(begin()); } /// data - Return a pointer to the vector's buffer, even if empty(). const_pointer data() const { return const_pointer(begin()); } - + reference operator[](unsigned idx) { assert(begin() + idx < end()); return begin()[idx]; @@ -172,7 +174,7 @@ public: return end()[-1]; } }; - + /// SmallVectorTemplateBase<isPodLike = false> - This is where we put method /// implementations that are designed to work with non-POD-like T's. template <typename T, bool isPodLike> @@ -186,14 +188,14 @@ public: E->~T(); } } - + /// uninitialized_copy - Copy the range [I, E) onto the uninitialized memory /// starting with "Dest", constructing elements into it as needed. template<typename It1, typename It2> static void uninitialized_copy(It1 I, It1 E, It2 Dest) { std::uninitialized_copy(I, E, Dest); } - + /// grow - double the size of the allocated memory, guaranteeing space for at /// least one more element or MinSize if specified. void grow(size_t MinSize = 0); @@ -207,34 +209,34 @@ void SmallVectorTemplateBase<T, isPodLike>::grow(size_t MinSize) { size_t NewCapacity = 2*CurCapacity; if (NewCapacity < MinSize) NewCapacity = MinSize; - T *NewElts = static_cast<T*>(operator new(NewCapacity*sizeof(T))); - + T *NewElts = static_cast<T*>(malloc(NewCapacity*sizeof(T))); + // Copy the elements over. this->uninitialized_copy(this->begin(), this->end(), NewElts); - + // Destroy the original elements. destroy_range(this->begin(), this->end()); - + // If this wasn't grown from the inline copy, deallocate the old space. if (!this->isSmall()) - operator delete(this->begin()); - + free(this->begin()); + this->setEnd(NewElts+CurSize); this->BeginX = NewElts; this->CapacityX = this->begin()+NewCapacity; } - - + + /// SmallVectorTemplateBase<isPodLike = true> - This is where we put method /// implementations that are designed to work with POD-like T's. template <typename T> class SmallVectorTemplateBase<T, true> : public SmallVectorTemplateCommon<T> { public: SmallVectorTemplateBase(size_t Size) : SmallVectorTemplateCommon<T>(Size) {} - + // No need to do a destroy loop for POD's. static void destroy_range(T *, T *) {} - + /// uninitialized_copy - Copy the range [I, E) onto the uninitialized memory /// starting with "Dest", constructing elements into it as needed. template<typename It1, typename It2> @@ -259,33 +261,35 @@ public: this->grow_pod(MinSize*sizeof(T), sizeof(T)); } }; - - + + /// SmallVectorImpl - This class consists of common code factored out of the /// SmallVector class to reduce code duplication based on the SmallVector 'N' /// template parameter. template <typename T> class SmallVectorImpl : public SmallVectorTemplateBase<T, isPodLike<T>::value> { typedef SmallVectorTemplateBase<T, isPodLike<T>::value > SuperClass; + + SmallVectorImpl(const SmallVectorImpl&); // DISABLED. public: typedef typename SuperClass::iterator iterator; typedef typename SuperClass::size_type size_type; - + // Default ctor - Initialize to empty. explicit SmallVectorImpl(unsigned N) : SmallVectorTemplateBase<T, isPodLike<T>::value>(N*sizeof(T)) { } - + ~SmallVectorImpl() { // Destroy the constructed elements in the vector. this->destroy_range(this->begin(), this->end()); - + // If this wasn't grown from the inline copy, deallocate the old space. if (!this->isSmall()) - operator delete(this->begin()); + free(this->begin()); } - - + + void clear() { this->destroy_range(this->begin(), this->end()); this->EndX = this->BeginX; @@ -319,7 +323,7 @@ public: if (this->capacity() < N) this->grow(N); } - + void push_back(const T &Elt) { if (this->EndX < this->CapacityX) { Retry: @@ -330,21 +334,21 @@ public: this->grow(); goto Retry; } - + void pop_back() { this->setEnd(this->end()-1); this->end()->~T(); } - + T pop_back_val() { T Result = this->back(); pop_back(); return Result; } - - + + void swap(SmallVectorImpl &RHS); - + /// append - Add the specified range to the end of the SmallVector. /// template<typename in_iter> @@ -353,26 +357,26 @@ public: // Grow allocated space if needed. if (NumInputs > size_type(this->capacity_ptr()-this->end())) this->grow(this->size()+NumInputs); - + // Copy the new elements over. // TODO: NEED To compile time dispatch on whether in_iter is a random access // iterator to use the fast uninitialized_copy. std::uninitialized_copy(in_start, in_end, this->end()); this->setEnd(this->end() + NumInputs); } - + /// append - Add the specified range to the end of the SmallVector. /// void append(size_type NumInputs, const T &Elt) { // Grow allocated space if needed. if (NumInputs > size_type(this->capacity_ptr()-this->end())) this->grow(this->size()+NumInputs); - + // Copy the new elements over. std::uninitialized_fill_n(this->end(), NumInputs, Elt); this->setEnd(this->end() + NumInputs); } - + void assign(unsigned NumElts, const T &Elt) { clear(); if (this->capacity() < NumElts) @@ -380,7 +384,7 @@ public: this->setEnd(this->begin()+NumElts); construct_range(this->begin(), this->end(), Elt); } - + iterator erase(iterator I) { iterator N = I; // Shift all elts down one. @@ -389,7 +393,7 @@ public: pop_back(); return(N); } - + iterator erase(iterator S, iterator E) { iterator N = S; // Shift all elts down. @@ -399,13 +403,13 @@ public: this->setEnd(I); return(N); } - + iterator insert(iterator I, const T &Elt) { if (I == this->end()) { // Important special case for empty vector. push_back(Elt); return this->end()-1; } - + if (this->EndX < this->CapacityX) { Retry: new (this->end()) T(this->back()); @@ -420,22 +424,22 @@ public: I = this->begin()+EltNo; goto Retry; } - + iterator insert(iterator I, size_type NumToInsert, const T &Elt) { if (I == this->end()) { // Important special case for empty vector. append(NumToInsert, Elt); return this->end()-1; } - + // Convert iterator to elt# to avoid invalidating iterator when we reserve() size_t InsertElt = I - this->begin(); - + // Ensure there is enough space. reserve(static_cast<unsigned>(this->size() + NumToInsert)); - + // Uninvalidate the iterator. I = this->begin()+InsertElt; - + // If there are more elements between the insertion point and the end of the // range than there are being inserted, we can use a simple approach to // insertion. Since we already reserved space, we know that this won't @@ -443,48 +447,48 @@ public: if (size_t(this->end()-I) >= NumToInsert) { T *OldEnd = this->end(); append(this->end()-NumToInsert, this->end()); - + // Copy the existing elements that get replaced. std::copy_backward(I, OldEnd-NumToInsert, OldEnd); - + std::fill_n(I, NumToInsert, Elt); return I; } - + // Otherwise, we're inserting more elements than exist already, and we're // not inserting at the end. - + // Copy over the elements that we're about to overwrite. T *OldEnd = this->end(); this->setEnd(this->end() + NumToInsert); size_t NumOverwritten = OldEnd-I; this->uninitialized_copy(I, OldEnd, this->end()-NumOverwritten); - + // Replace the overwritten part. std::fill_n(I, NumOverwritten, Elt); - + // Insert the non-overwritten middle part. std::uninitialized_fill_n(OldEnd, NumToInsert-NumOverwritten, Elt); return I; } - + template<typename ItTy> iterator insert(iterator I, ItTy From, ItTy To) { if (I == this->end()) { // Important special case for empty vector. append(From, To); return this->end()-1; } - + size_t NumToInsert = std::distance(From, To); // Convert iterator to elt# to avoid invalidating iterator when we reserve() size_t InsertElt = I - this->begin(); - + // Ensure there is enough space. reserve(static_cast<unsigned>(this->size() + NumToInsert)); - + // Uninvalidate the iterator. I = this->begin()+InsertElt; - + // If there are more elements between the insertion point and the end of the // range than there are being inserted, we can use a simple approach to // insertion. Since we already reserved space, we know that this won't @@ -492,37 +496,37 @@ public: if (size_t(this->end()-I) >= NumToInsert) { T *OldEnd = this->end(); append(this->end()-NumToInsert, this->end()); - + // Copy the existing elements that get replaced. std::copy_backward(I, OldEnd-NumToInsert, OldEnd); - + std::copy(From, To, I); return I; } - + // Otherwise, we're inserting more elements than exist already, and we're // not inserting at the end. - + // Copy over the elements that we're about to overwrite. T *OldEnd = this->end(); this->setEnd(this->end() + NumToInsert); size_t NumOverwritten = OldEnd-I; this->uninitialized_copy(I, OldEnd, this->end()-NumOverwritten); - + // Replace the overwritten part. for (; NumOverwritten > 0; --NumOverwritten) { *I = *From; ++I; ++From; } - + // Insert the non-overwritten middle part. this->uninitialized_copy(From, To, OldEnd); return I; } - + const SmallVectorImpl &operator=(const SmallVectorImpl &RHS); - + bool operator==(const SmallVectorImpl &RHS) const { if (this->size() != RHS.size()) return false; return std::equal(this->begin(), this->end(), RHS.begin()); @@ -530,12 +534,12 @@ public: bool operator!=(const SmallVectorImpl &RHS) const { return !(*this == RHS); } - + bool operator<(const SmallVectorImpl &RHS) const { return std::lexicographical_compare(this->begin(), this->end(), RHS.begin(), RHS.end()); } - + /// set_size - Set the array size to \arg N, which the current array must have /// enough capacity for. /// @@ -549,14 +553,14 @@ public: assert(N <= this->capacity()); this->setEnd(this->begin() + N); } - + private: static void construct_range(T *S, T *E, const T &Elt) { for (; S != E; ++S) new (S) T(Elt); } }; - + template <typename T> void SmallVectorImpl<T>::swap(SmallVectorImpl<T> &RHS) { diff --git a/include/llvm/ADT/Statistic.h b/include/llvm/ADT/Statistic.h index c593c58..3a1319f 100644 --- a/include/llvm/ADT/Statistic.h +++ b/include/llvm/ADT/Statistic.h @@ -56,6 +56,10 @@ public: } const Statistic &operator++() { + // FIXME: This function and all those that follow carefully use an + // atomic operation to update the value safely in the presence of + // concurrent accesses, but not to read the return value, so the + // return value is not thread safe. sys::AtomicIncrement(&Value); return init(); } diff --git a/include/llvm/ADT/Triple.h b/include/llvm/ADT/Triple.h index be31ea0..feade6a 100644 --- a/include/llvm/ADT/Triple.h +++ b/include/llvm/ADT/Triple.h @@ -100,7 +100,8 @@ public: Psp, Solaris, Win32, - Haiku + Haiku, + Minix }; private: @@ -242,8 +243,8 @@ public: /// environment components with a single string. void setOSAndEnvironmentName(StringRef Str); - /// getArchNameForAssembler - Get an architecture name that is understood by the - /// target assembler. + /// getArchNameForAssembler - Get an architecture name that is understood by + /// the target assembler. const char *getArchNameForAssembler(); /// @} diff --git a/include/llvm/ADT/ValueMap.h b/include/llvm/ADT/ValueMap.h index 6f57fe8..9e30bd4 100644 --- a/include/llvm/ADT/ValueMap.h +++ b/include/llvm/ADT/ValueMap.h @@ -59,16 +59,16 @@ struct ValueMapConfig { struct ExtraData {}; template<typename ExtraDataT> - static void onRAUW(const ExtraDataT &Data, KeyT Old, KeyT New) {} + static void onRAUW(const ExtraDataT & /*Data*/, KeyT /*Old*/, KeyT /*New*/) {} template<typename ExtraDataT> - static void onDelete(const ExtraDataT &Data, KeyT Old) {} + static void onDelete(const ExtraDataT &/*Data*/, KeyT /*Old*/) {} /// Returns a mutex that should be acquired around any changes to the map. /// This is only acquired from the CallbackVH (and held around calls to onRAUW /// and onDelete) and not inside other ValueMap methods. NULL means that no /// mutex is necessary. template<typename ExtraDataT> - static sys::Mutex *getMutex(const ExtraDataT &Data) { return NULL; } + static sys::Mutex *getMutex(const ExtraDataT &/*Data*/) { return NULL; } }; /// See the file comment. diff --git a/include/llvm/ADT/ilist.h b/include/llvm/ADT/ilist.h index e4d26dd..9479d00 100644 --- a/include/llvm/ADT/ilist.h +++ b/include/llvm/ADT/ilist.h @@ -39,6 +39,7 @@ #define LLVM_ADT_ILIST_H #include <cassert> +#include <cstddef> #include <iterator> namespace llvm { |
