diff options
Diffstat (limited to 'include/llvm/ADT')
28 files changed, 1500 insertions, 478 deletions
diff --git a/include/llvm/ADT/APFloat.h b/include/llvm/ADT/APFloat.h index 928ecc0..4d7e7ae 100644 --- a/include/llvm/ADT/APFloat.h +++ b/include/llvm/ADT/APFloat.h @@ -109,6 +109,7 @@ namespace llvm { typedef signed short exponent_t; struct fltSemantics; + class StringRef; /* When bits of a floating point number are truncated, this enum is used to indicate what fraction of the LSB those bits represented. @@ -172,7 +173,8 @@ namespace llvm { }; // Constructors. - APFloat(const fltSemantics &, const char *); + APFloat(const fltSemantics &); // Default construct to 0.0 + APFloat(const fltSemantics &, const StringRef &); APFloat(const fltSemantics &, integerPart); APFloat(const fltSemantics &, fltCategory, bool negative, unsigned type=0); explicit APFloat(double d); @@ -234,7 +236,7 @@ namespace llvm { bool, roundingMode); opStatus convertFromZeroExtendedInteger(const integerPart *, unsigned int, bool, roundingMode); - opStatus convertFromString(const char *, roundingMode); + opStatus convertFromString(const StringRef&, roundingMode); APInt bitcastToAPInt() const; double convertToDouble() const; float convertToFloat() const; @@ -312,8 +314,8 @@ namespace llvm { roundingMode, bool *) const; opStatus convertFromUnsignedParts(const integerPart *, unsigned int, roundingMode); - opStatus convertFromHexadecimalString(const char *, roundingMode); - opStatus convertFromDecimalString (const char *, roundingMode); + opStatus convertFromHexadecimalString(const StringRef&, roundingMode); + opStatus convertFromDecimalString (const StringRef&, roundingMode); char *convertNormalToHexString(char *, unsigned int, bool, roundingMode) const; opStatus roundSignificandWithExponent(const integerPart *, unsigned int, @@ -321,11 +323,13 @@ namespace llvm { APInt convertFloatAPFloatToAPInt() const; APInt convertDoubleAPFloatToAPInt() const; + APInt convertQuadrupleAPFloatToAPInt() const; APInt convertF80LongDoubleAPFloatToAPInt() const; APInt convertPPCDoubleDoubleAPFloatToAPInt() const; void initFromAPInt(const APInt& api, bool isIEEE = false); void initFromFloatAPInt(const APInt& api); void initFromDoubleAPInt(const APInt& api); + void initFromQuadrupleAPInt(const APInt &api); void initFromF80LongDoubleAPInt(const APInt& api); void initFromPPCDoubleDoubleAPInt(const APInt& api); diff --git a/include/llvm/ADT/APInt.h b/include/llvm/ADT/APInt.h index 56cd3cc..88aa995 100644 --- a/include/llvm/ADT/APInt.h +++ b/include/llvm/ADT/APInt.h @@ -15,7 +15,6 @@ #ifndef LLVM_APINT_H #define LLVM_APINT_H -#include "llvm/Support/DataTypes.h" #include "llvm/Support/MathExtras.h" #include <cassert> #include <climits> @@ -27,12 +26,13 @@ namespace llvm { class Deserializer; class FoldingSetNodeID; class raw_ostream; + class StringRef; template<typename T> class SmallVectorImpl; - /* An unsigned host type used as a single part of a multi-part - bignum. */ + // An unsigned host type used as a single part of a multi-part + // bignum. typedef uint64_t integerPart; const unsigned int host_char_bit = 8; @@ -152,8 +152,7 @@ class APInt { /// This is used by the constructors that take string arguments. /// @brief Convert a char array into an APInt - void fromString(unsigned numBits, const char *strStart, unsigned slen, - uint8_t radix); + void fromString(unsigned numBits, const StringRef &str, uint8_t radix); /// This is used by the toString method to divide by the radix. It simply /// provides a more convenient form of divide for internal use since KnuthDiv @@ -229,17 +228,17 @@ public: /// @brief Construct an APInt of numBits width, initialized as bigVal[]. APInt(unsigned numBits, unsigned numWords, const uint64_t bigVal[]); - /// This constructor interprets the slen characters starting at StrStart as - /// a string in the given radix. The interpretation stops when the first - /// character that is not suitable for the radix is encountered. Acceptable - /// radix values are 2, 8, 10 and 16. It is an error for the value implied by - /// the string to require more bits than numBits. + /// This constructor interprets the string \arg 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 and 16. It is an error for the value implied by the string to + /// require more bits than numBits. + /// /// @param numBits the bit width of the constructed APInt - /// @param strStart the start of the string to be interpreted - /// @param slen the maximum number of characters to interpret - /// @param radix the radix to use for the conversion + /// @param str the string to be interpreted + /// @param radix the radix to use for the conversion /// @brief Construct an APInt from a string representation. - APInt(unsigned numBits, const char strStart[], unsigned slen, uint8_t radix); + APInt(unsigned numBits, const StringRef &str, uint8_t radix); /// Simply makes *this a copy of that. /// @brief Copy Constructor. @@ -1063,9 +1062,9 @@ public: } /// This method determines how many bits are required to hold the APInt - /// equivalent of the string given by \p str of length \p slen. + /// equivalent of the string given by \arg str. /// @brief Get bits required for string value. - static unsigned getBitsNeeded(const char* str, unsigned slen, uint8_t radix); + static unsigned getBitsNeeded(const StringRef& str, uint8_t radix); /// countLeadingZeros - This function is an APInt version of the /// countLeadingZeros_{32,64} functions in MathExtras.h. It counts the number @@ -1235,6 +1234,11 @@ public: return BitWidth - 1 - countLeadingZeros(); } + /// @returns the ceil log base 2 of this APInt. + unsigned ceilLogBase2() const { + return BitWidth - (*this - 1).countLeadingZeros(); + } + /// @returns the log base 2 of this APInt if its an exact power of two, -1 /// otherwise int32_t exactLogBase2() const { @@ -1426,8 +1430,6 @@ inline raw_ostream &operator<<(raw_ostream &OS, const APInt &I) { return OS; } -std::ostream &operator<<(std::ostream &o, const APInt &I); - namespace APIntOps { /// @brief Determine the smaller of two APInts considered to be signed. diff --git a/include/llvm/ADT/DenseMap.h b/include/llvm/ADT/DenseMap.h index e18be89..0ed2d5a 100644 --- a/include/llvm/ADT/DenseMap.h +++ b/include/llvm/ADT/DenseMap.h @@ -16,109 +16,15 @@ #include "llvm/Support/PointerLikeTypeTraits.h" #include "llvm/Support/MathExtras.h" -#include <cassert> -#include <utility> +#include "llvm/ADT/DenseMapInfo.h" +#include <iterator> #include <new> +#include <utility> +#include <cassert> +#include <cstring> namespace llvm { -template<typename T> -struct DenseMapInfo { - //static inline T getEmptyKey(); - //static inline T getTombstoneKey(); - //static unsigned getHashValue(const T &Val); - //static bool isEqual(const T &LHS, const T &RHS); - //static bool isPod() -}; - -// Provide DenseMapInfo for all pointers. -template<typename T> -struct DenseMapInfo<T*> { - static inline T* getEmptyKey() { - intptr_t Val = -1; - Val <<= PointerLikeTypeTraits<T*>::NumLowBitsAvailable; - return reinterpret_cast<T*>(Val); - } - static inline T* getTombstoneKey() { - intptr_t Val = -2; - Val <<= PointerLikeTypeTraits<T*>::NumLowBitsAvailable; - return reinterpret_cast<T*>(Val); - } - static unsigned getHashValue(const T *PtrVal) { - return (unsigned((uintptr_t)PtrVal) >> 4) ^ - (unsigned((uintptr_t)PtrVal) >> 9); - } - static bool isEqual(const T *LHS, const T *RHS) { return LHS == RHS; } - static bool isPod() { return true; } -}; - -// Provide DenseMapInfo for chars. -template<> struct DenseMapInfo<char> { - static inline char getEmptyKey() { return ~0; } - static inline char getTombstoneKey() { return ~0 - 1; } - static unsigned getHashValue(const char& Val) { return Val * 37; } - static bool isPod() { return true; } - static bool isEqual(const char &LHS, const char &RHS) { - return LHS == RHS; - } -}; - -// Provide DenseMapInfo for unsigned ints. -template<> struct DenseMapInfo<unsigned> { - static inline unsigned getEmptyKey() { return ~0; } - static inline unsigned getTombstoneKey() { return ~0 - 1; } - static unsigned getHashValue(const unsigned& Val) { return Val * 37; } - static bool isPod() { return true; } - static bool isEqual(const unsigned& LHS, const unsigned& RHS) { - return LHS == RHS; - } -}; - -// Provide DenseMapInfo for unsigned longs. -template<> struct DenseMapInfo<unsigned long> { - static inline unsigned long getEmptyKey() { return ~0L; } - static inline unsigned long getTombstoneKey() { return ~0L - 1L; } - static unsigned getHashValue(const unsigned long& Val) { - return (unsigned)(Val * 37L); - } - static bool isPod() { return true; } - static bool isEqual(const unsigned long& LHS, const unsigned long& RHS) { - return LHS == RHS; - } -}; - -// Provide DenseMapInfo for all pairs whose members have info. -template<typename T, typename U> -struct DenseMapInfo<std::pair<T, U> > { - typedef std::pair<T, U> Pair; - typedef DenseMapInfo<T> FirstInfo; - typedef DenseMapInfo<U> SecondInfo; - - static inline Pair getEmptyKey() { - return std::make_pair(FirstInfo::getEmptyKey(), - SecondInfo::getEmptyKey()); - } - static inline Pair getTombstoneKey() { - return std::make_pair(FirstInfo::getTombstoneKey(), - SecondInfo::getEmptyKey()); - } - static unsigned getHashValue(const Pair& PairVal) { - uint64_t key = (uint64_t)FirstInfo::getHashValue(PairVal.first) << 32 - | (uint64_t)SecondInfo::getHashValue(PairVal.second); - key += ~(key << 32); - key ^= (key >> 22); - key += ~(key << 13); - key ^= (key >> 8); - key += (key << 3); - key ^= (key >> 15); - key += ~(key << 27); - key ^= (key >> 31); - return (unsigned)key; - } - static bool isEqual(const Pair& LHS, const Pair& RHS) { return LHS == RHS; } - static bool isPod() { return FirstInfo::isPod() && SecondInfo::isPod(); } -}; - template<typename KeyT, typename ValueT, typename KeyInfoT = DenseMapInfo<KeyT>, typename ValueInfoT = DenseMapInfo<ValueT> > @@ -160,6 +66,9 @@ public: P->second.~ValueT(); P->first.~KeyT(); } +#ifndef NDEBUG + memset(Buckets, 0x5a, sizeof(BucketT)*NumBuckets); +#endif operator delete(Buckets); } @@ -185,6 +94,8 @@ public: void resize(size_t Size) { grow(Size); } void clear() { + if (NumEntries == 0 && NumTombstones == 0) return; + // If the capacity of the array is huge, and the # elements used is small, // shrink the array. if (NumEntries * 4 < NumBuckets && NumBuckets > 64) { @@ -234,6 +145,9 @@ public: return ValueT(); } + // Inserts key,value pair into the map if the key isn't already in the map. + // If the key is already in the map, it returns false and doesn't update the + // value. std::pair<iterator, bool> insert(const std::pair<KeyT, ValueT> &KV) { BucketT *TheBucket; if (LookupBucketFor(KV.first, TheBucket)) @@ -318,8 +232,12 @@ private: NumEntries = other.NumEntries; NumTombstones = other.NumTombstones; - if (NumBuckets) + if (NumBuckets) { +#ifndef NDEBUG + memset(Buckets, 0x5a, sizeof(BucketT)*NumBuckets); +#endif operator delete(Buckets); + } Buckets = static_cast<BucketT*>(operator new(sizeof(BucketT) * other.NumBuckets)); @@ -465,6 +383,9 @@ private: B->first.~KeyT(); } +#ifndef NDEBUG + memset(OldBuckets, 0x5a, sizeof(BucketT)*OldNumBuckets); +#endif // Free the old table. operator delete(OldBuckets); } @@ -495,6 +416,9 @@ private: B->first.~KeyT(); } +#ifndef NDEBUG + memset(OldBuckets, 0x5a, sizeof(BucketT)*OldNumBuckets); +#endif // Free the old table. operator delete(OldBuckets); @@ -503,12 +427,14 @@ private: }; template<typename KeyT, typename ValueT, typename KeyInfoT, typename ValueInfoT> -class DenseMapIterator { +class DenseMapIterator : + public std::iterator<std::forward_iterator_tag, std::pair<KeyT, ValueT>, + ptrdiff_t> { typedef std::pair<KeyT, ValueT> BucketT; protected: const BucketT *Ptr, *End; public: - DenseMapIterator(void) : Ptr(0), End(0) {} + DenseMapIterator() : Ptr(0), End(0) {} DenseMapIterator(const BucketT *Pos, const BucketT *E) : Ptr(Pos), End(E) { AdvancePastEmptyBuckets(); @@ -552,7 +478,7 @@ private: template<typename KeyT, typename ValueT, typename KeyInfoT, typename ValueInfoT> class DenseMapConstIterator : public DenseMapIterator<KeyT, ValueT, KeyInfoT> { public: - DenseMapConstIterator(void) : DenseMapIterator<KeyT, ValueT, KeyInfoT>() {} + DenseMapConstIterator() : DenseMapIterator<KeyT, ValueT, KeyInfoT>() {} DenseMapConstIterator(const std::pair<KeyT, ValueT> *Pos, const std::pair<KeyT, ValueT> *E) : DenseMapIterator<KeyT, ValueT, KeyInfoT>(Pos, E) { diff --git a/include/llvm/ADT/DenseMapInfo.h b/include/llvm/ADT/DenseMapInfo.h new file mode 100644 index 0000000..632728b --- /dev/null +++ b/include/llvm/ADT/DenseMapInfo.h @@ -0,0 +1,135 @@ +//===- llvm/ADT/DenseMapInfo.h - Type traits for DenseMap -------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file defines DenseMapInfo traits for DenseMap. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_ADT_DENSEMAPINFO_H +#define LLVM_ADT_DENSEMAPINFO_H + +#include "llvm/Support/PointerLikeTypeTraits.h" +#include <utility> + +namespace llvm { + +template<typename T> +struct DenseMapInfo { + //static inline T getEmptyKey(); + //static inline T getTombstoneKey(); + //static unsigned getHashValue(const T &Val); + //static bool isEqual(const T &LHS, const T &RHS); + //static bool isPod() +}; + +// Provide DenseMapInfo for all pointers. +template<typename T> +struct DenseMapInfo<T*> { + static inline T* getEmptyKey() { + intptr_t Val = -1; + Val <<= PointerLikeTypeTraits<T*>::NumLowBitsAvailable; + return reinterpret_cast<T*>(Val); + } + static inline T* getTombstoneKey() { + intptr_t Val = -2; + Val <<= PointerLikeTypeTraits<T*>::NumLowBitsAvailable; + return reinterpret_cast<T*>(Val); + } + static unsigned getHashValue(const T *PtrVal) { + return (unsigned((uintptr_t)PtrVal) >> 4) ^ + (unsigned((uintptr_t)PtrVal) >> 9); + } + static bool isEqual(const T *LHS, const T *RHS) { return LHS == RHS; } + static bool isPod() { return true; } +}; + +// Provide DenseMapInfo for chars. +template<> struct DenseMapInfo<char> { + static inline char getEmptyKey() { return ~0; } + static inline char getTombstoneKey() { return ~0 - 1; } + static unsigned getHashValue(const char& Val) { return Val * 37; } + static bool isPod() { return true; } + static bool isEqual(const char &LHS, const char &RHS) { + return LHS == RHS; + } +}; + +// Provide DenseMapInfo for unsigned ints. +template<> struct DenseMapInfo<unsigned> { + static inline unsigned getEmptyKey() { return ~0; } + static inline unsigned getTombstoneKey() { return ~0U - 1; } + static unsigned getHashValue(const unsigned& Val) { return Val * 37; } + static bool isPod() { return true; } + static bool isEqual(const unsigned& LHS, const unsigned& RHS) { + return LHS == RHS; + } +}; + +// Provide DenseMapInfo for unsigned longs. +template<> struct DenseMapInfo<unsigned long> { + static inline unsigned long getEmptyKey() { return ~0UL; } + static inline unsigned long getTombstoneKey() { return ~0UL - 1L; } + static unsigned getHashValue(const unsigned long& Val) { + return Val * 37UL; + } + static bool isPod() { return true; } + static bool isEqual(const unsigned long& LHS, const unsigned long& RHS) { + return LHS == RHS; + } +}; + +// Provide DenseMapInfo for unsigned long longs. +template<> struct DenseMapInfo<unsigned long long> { + static inline unsigned long long getEmptyKey() { return ~0ULL; } + static inline unsigned long long getTombstoneKey() { return ~0ULL - 1ULL; } + static unsigned getHashValue(const unsigned long long& Val) { + return Val * 37ULL; + } + static bool isPod() { return true; } + static bool isEqual(const unsigned long long& LHS, + const unsigned long long& RHS) { + return LHS == RHS; + } +}; + +// Provide DenseMapInfo for all pairs whose members have info. +template<typename T, typename U> +struct DenseMapInfo<std::pair<T, U> > { + typedef std::pair<T, U> Pair; + typedef DenseMapInfo<T> FirstInfo; + typedef DenseMapInfo<U> SecondInfo; + + static inline Pair getEmptyKey() { + return std::make_pair(FirstInfo::getEmptyKey(), + SecondInfo::getEmptyKey()); + } + static inline Pair getTombstoneKey() { + return std::make_pair(FirstInfo::getTombstoneKey(), + SecondInfo::getEmptyKey()); + } + static unsigned getHashValue(const Pair& PairVal) { + uint64_t key = (uint64_t)FirstInfo::getHashValue(PairVal.first) << 32 + | (uint64_t)SecondInfo::getHashValue(PairVal.second); + key += ~(key << 32); + key ^= (key >> 22); + key += ~(key << 13); + key ^= (key >> 8); + key += (key << 3); + key ^= (key >> 15); + key += ~(key << 27); + key ^= (key >> 31); + return (unsigned)key; + } + static bool isEqual(const Pair& LHS, const Pair& RHS) { return LHS == RHS; } + static bool isPod() { return FirstInfo::isPod() && SecondInfo::isPod(); } +}; + +} // end namespace llvm + +#endif diff --git a/include/llvm/ADT/DepthFirstIterator.h b/include/llvm/ADT/DepthFirstIterator.h index 517768f..5f2df2a 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/iterator.h" #include "llvm/ADT/SmallPtrSet.h" +#include "llvm/ADT/PointerIntPair.h" #include <set> #include <vector> @@ -62,28 +62,35 @@ public: template<class GraphT, class SetType = llvm::SmallPtrSet<typename GraphTraits<GraphT>::NodeType*, 8>, bool ExtStorage = false, class GT = GraphTraits<GraphT> > -class df_iterator : public forward_iterator<typename GT::NodeType, ptrdiff_t>, +class df_iterator : public std::iterator<std::forward_iterator_tag, + typename GT::NodeType, ptrdiff_t>, public df_iterator_storage<SetType, ExtStorage> { - typedef forward_iterator<typename GT::NodeType, ptrdiff_t> super; + typedef std::iterator<std::forward_iterator_tag, + typename GT::NodeType, ptrdiff_t> super; typedef typename GT::NodeType NodeType; typedef typename GT::ChildIteratorType ChildItTy; + typedef PointerIntPair<NodeType*, 1> PointerIntTy; // VisitStack - Used to maintain the ordering. Top = current block // First element is node pointer, second is the 'next child' to visit - std::vector<std::pair<NodeType *, ChildItTy> > VisitStack; + // if the int in PointerIntTy is 0, the 'next child' to visit is invalid + std::vector<std::pair<PointerIntTy, ChildItTy> > VisitStack; private: inline df_iterator(NodeType *Node) { this->Visited.insert(Node); - VisitStack.push_back(std::make_pair(Node, GT::child_begin(Node))); + VisitStack.push_back(std::make_pair(PointerIntTy(Node, 0), + GT::child_begin(Node))); + } + inline df_iterator() { + // End is when stack is empty } - inline df_iterator() { /* End is when stack is empty */ } - inline df_iterator(NodeType *Node, SetType &S) : df_iterator_storage<SetType, ExtStorage>(S) { if (!S.count(Node)) { + VisitStack.push_back(std::make_pair(PointerIntTy(Node, 0), + GT::child_begin(Node))); this->Visited.insert(Node); - VisitStack.push_back(std::make_pair(Node, GT::child_begin(Node))); } } inline df_iterator(SetType &S) @@ -91,6 +98,34 @@ private: // End is when stack is empty } + inline void toNext() { + do { + std::pair<PointerIntTy, ChildItTy> &Top = VisitStack.back(); + NodeType *Node = Top.first.getPointer(); + ChildItTy &It = Top.second; + if (!Top.first.getInt()) { + // now retrieve the real begin of the children before we dive in + It = GT::child_begin(Node); + Top.first.setInt(1); + } + + while (It != GT::child_end(Node)) { + NodeType *Next = *It++; + // Has our next sibling been visited? + if (Next && !this->Visited.count(Next)) { + // No, do it now. + this->Visited.insert(Next); + VisitStack.push_back(std::make_pair(PointerIntTy(Next, 0), + GT::child_begin(Next))); + return; + } + } + + // Oops, ran out of successors... go up a level on the stack. + VisitStack.pop_back(); + } while (!VisitStack.empty()); + } + public: typedef typename super::pointer pointer; typedef df_iterator<GraphT, SetType, ExtStorage, GT> _Self; @@ -114,7 +149,7 @@ public: inline bool operator!=(const _Self& x) const { return !operator==(x); } inline pointer operator*() const { - return VisitStack.back().first; + return VisitStack.back().first.getPointer(); } // This is a nonstandard operator-> that dereferences the pointer an extra @@ -124,24 +159,16 @@ public: inline NodeType *operator->() const { return operator*(); } inline _Self& operator++() { // Preincrement - do { - std::pair<NodeType *, ChildItTy> &Top = VisitStack.back(); - NodeType *Node = Top.first; - ChildItTy &It = Top.second; - - while (It != GT::child_end(Node)) { - NodeType *Next = *It++; - if (!this->Visited.count(Next)) { // Has our next sibling been visited? - // No, do it now. - this->Visited.insert(Next); - VisitStack.push_back(std::make_pair(Next, GT::child_begin(Next))); - return *this; - } - } + toNext(); + return *this; + } - // Oops, ran out of successors... go up a level on the stack. - VisitStack.pop_back(); - } while (!VisitStack.empty()); + // skips all children of the current node and traverses to next node + // + inline _Self& skipChildren() { + VisitStack.pop_back(); + if (!VisitStack.empty()) + toNext(); return *this; } diff --git a/include/llvm/ADT/EquivalenceClasses.h b/include/llvm/ADT/EquivalenceClasses.h index 6e00a21..ac9dd4d 100644 --- a/include/llvm/ADT/EquivalenceClasses.h +++ b/include/llvm/ADT/EquivalenceClasses.h @@ -15,7 +15,6 @@ #ifndef LLVM_ADT_EQUIVALENCECLASSES_H #define LLVM_ADT_EQUIVALENCECLASSES_H -#include "llvm/ADT/iterator.h" #include "llvm/Support/DataTypes.h" #include <set> @@ -234,8 +233,10 @@ public: return L1; } - class member_iterator : public forward_iterator<ElemTy, ptrdiff_t> { - typedef forward_iterator<const ElemTy, ptrdiff_t> super; + class member_iterator : public std::iterator<std::forward_iterator_tag, + const ElemTy, ptrdiff_t> { + typedef std::iterator<std::forward_iterator_tag, + const ElemTy, ptrdiff_t> super; const ECValue *Node; friend class EquivalenceClasses; public: diff --git a/include/llvm/ADT/FoldingSet.h b/include/llvm/ADT/FoldingSet.h index 1bcff3d..c62c47d 100644 --- a/include/llvm/ADT/FoldingSet.h +++ b/include/llvm/ADT/FoldingSet.h @@ -18,7 +18,7 @@ #include "llvm/Support/DataTypes.h" #include "llvm/ADT/SmallVector.h" -#include <string> +#include "llvm/ADT/StringRef.h" #include <iterator> namespace llvm { @@ -227,9 +227,7 @@ public: void AddInteger(long long I); void AddInteger(unsigned long long I); void AddBoolean(bool B) { AddInteger(B ? 1U : 0U); } - void AddString(const char* String, const char* End); - void AddString(const std::string &String); - void AddString(const char* String); + void AddString(StringRef String); template <typename T> inline void Add(const T& x) { FoldingSetTrait<T>::Profile(x, *this); } @@ -439,6 +437,20 @@ public: }; //===----------------------------------------------------------------------===// +/// FastFoldingSetNode - This is a subclass of FoldingSetNode which stores +/// a FoldingSetNodeID value rather than requiring the node to recompute it +/// each time it is needed. This trades space for speed (which can be +/// significant if the ID is long), and it also permits nodes to drop +/// information that would otherwise only be required for recomputing an ID. +class FastFoldingSetNode : public FoldingSetNode { + FoldingSetNodeID FastID; +protected: + explicit FastFoldingSetNode(const FoldingSetNodeID &ID) : FastID(ID) {} +public: + void Profile(FoldingSetNodeID& ID) { ID = FastID; } +}; + +//===----------------------------------------------------------------------===// // Partial specializations of FoldingSetTrait. template<typename T> struct FoldingSetTrait<T*> { diff --git a/include/llvm/ADT/ImmutableMap.h b/include/llvm/ADT/ImmutableMap.h index 52708bc..742e232 100644 --- a/include/llvm/ADT/ImmutableMap.h +++ b/include/llvm/ADT/ImmutableMap.h @@ -80,22 +80,25 @@ public: class Factory { typename TreeTy::Factory F; + const bool Canonicalize; public: - Factory() {} - - Factory(BumpPtrAllocator& Alloc) - : F(Alloc) {} + Factory(bool canonicalize = true) + : Canonicalize(canonicalize) {} + + Factory(BumpPtrAllocator& Alloc, bool canonicalize = true) + : F(Alloc), Canonicalize(canonicalize) {} ImmutableMap GetEmptyMap() { return ImmutableMap(F.GetEmptyTree()); } ImmutableMap Add(ImmutableMap Old, key_type_ref K, data_type_ref D) { - return ImmutableMap(F.Add(Old.Root, - std::make_pair<key_type,data_type>(K,D))); + TreeTy *T = F.Add(Old.Root, std::make_pair<key_type,data_type>(K,D)); + return ImmutableMap(Canonicalize ? F.GetCanonicalTree(T): T); } ImmutableMap Remove(ImmutableMap Old, key_type_ref K) { - return ImmutableMap(F.Remove(Old.Root,K)); + TreeTy *T = F.Remove(Old.Root,K); + return ImmutableMap(Canonicalize ? F.GetCanonicalTree(T): T); } private: diff --git a/include/llvm/ADT/ImmutableSet.h b/include/llvm/ADT/ImmutableSet.h index be274db..14f4ac8 100644 --- a/include/llvm/ADT/ImmutableSet.h +++ b/include/llvm/ADT/ImmutableSet.h @@ -51,10 +51,8 @@ public: /// getLeft - Returns a pointer to the left subtree. This value /// is NULL if there is no left subtree. - ImutAVLTree* getLeft() const { - assert (!isMutable() && "Node is incorrectly marked mutable."); - - return reinterpret_cast<ImutAVLTree*>(Left); + ImutAVLTree *getLeft() const { + return reinterpret_cast<ImutAVLTree*>(Left & ~LeftFlags); } /// getRight - Returns a pointer to the right subtree. This value is @@ -168,7 +166,7 @@ public: /// contains - Returns true if this tree contains a subtree (node) that /// has an data element that matches the specified key. Complexity /// is logarithmic in the size of the tree. - bool contains(const key_type_ref K) { return (bool) find(K); } + bool contains(key_type_ref K) { return (bool) find(K); } /// foreach - A member template the accepts invokes operator() on a functor /// object (specifed by Callback) for every node/subtree in the tree. @@ -227,7 +225,7 @@ private: ImutAVLTree* Right; unsigned Height; value_type Value; - unsigned Digest; + uint32_t Digest; //===----------------------------------------------------===// // Internal methods (node manipulation; used by Factory). @@ -235,12 +233,12 @@ private: private: - enum { Mutable = 0x1 }; + enum { Mutable = 0x1, NoCachedDigest = 0x2, LeftFlags = 0x3 }; /// ImutAVLTree - Internal constructor that is only called by /// ImutAVLFactory. ImutAVLTree(ImutAVLTree* l, ImutAVLTree* r, value_type_ref v, unsigned height) - : Left(reinterpret_cast<uintptr_t>(l) | Mutable), + : Left(reinterpret_cast<uintptr_t>(l) | (Mutable | NoCachedDigest)), Right(r), Height(height), Value(v), Digest(0) {} @@ -251,13 +249,10 @@ 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 Left & Mutable; } - - /// getSafeLeft - Returns the pointer to the left tree by always masking - /// out the mutable bit. This is used internally by ImutAVLFactory, - /// as no trees returned to the client should have the mutable flag set. - ImutAVLTree* getSafeLeft() const { - return reinterpret_cast<ImutAVLTree*>(Left & ~Mutable); - } + + /// 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 !(Left & NoCachedDigest); } //===----------------------------------------------------===// // Mutating operations. A tree root can be manipulated as @@ -270,64 +265,73 @@ private: // immutable. //===----------------------------------------------------===// - /// MarkImmutable - Clears the mutable flag for a tree. After this happens, - /// it is an error to call setLeft(), setRight(), and setHeight(). It - /// is also then safe to call getLeft() instead of getSafeLeft(). + /// it is an error to call setLeft(), setRight(), and setHeight(). void MarkImmutable() { - assert (isMutable() && "Mutable flag already removed."); + assert(isMutable() && "Mutable flag already removed."); Left &= ~Mutable; } + + /// MarkedCachedDigest - Clears the NoCachedDigest flag for a tree. + void MarkedCachedDigest() { + assert(!hasCachedDigest() && "NoCachedDigest flag already removed."); + Left &= ~NoCachedDigest; + } /// setLeft - Changes the reference of the left subtree. Used internally /// by ImutAVLFactory. void setLeft(ImutAVLTree* NewLeft) { - assert (isMutable() && - "Only a mutable tree can have its left subtree changed."); - - Left = reinterpret_cast<uintptr_t>(NewLeft) | Mutable; + assert(isMutable() && + "Only a mutable tree can have its left subtree changed."); + Left = reinterpret_cast<uintptr_t>(NewLeft) | LeftFlags; } /// setRight - Changes the reference of the right subtree. Used internally /// by ImutAVLFactory. void setRight(ImutAVLTree* NewRight) { - assert (isMutable() && - "Only a mutable tree can have its right subtree changed."); + assert(isMutable() && + "Only a mutable tree can have its right subtree changed."); Right = NewRight; + // Set the NoCachedDigest flag. + Left = Left | NoCachedDigest; + } /// setHeight - Changes the height of the tree. Used internally by /// ImutAVLFactory. void setHeight(unsigned h) { - assert (isMutable() && "Only a mutable tree can have its height changed."); + assert(isMutable() && "Only a mutable tree can have its height changed."); Height = h; } - static inline - unsigned ComputeDigest(ImutAVLTree* L, ImutAVLTree* R, value_type_ref V) { - unsigned digest = 0; + uint32_t ComputeDigest(ImutAVLTree* L, ImutAVLTree* R, value_type_ref V) { + uint32_t digest = 0; - if (L) digest += L->ComputeDigest(); + if (L) + digest += L->ComputeDigest(); - { // Compute digest of stored data. - FoldingSetNodeID ID; - ImutInfo::Profile(ID,V); - digest += ID.ComputeHash(); - } + // Compute digest of stored data. + FoldingSetNodeID ID; + ImutInfo::Profile(ID,V); + digest += ID.ComputeHash(); - if (R) digest += R->ComputeDigest(); + if (R) + digest += R->ComputeDigest(); return digest; } - inline unsigned ComputeDigest() { - if (Digest) return Digest; - - unsigned X = ComputeDigest(getSafeLeft(), getRight(), getValue()); - if (!isMutable()) Digest = X; + inline uint32_t ComputeDigest() { + // Check the lowest bit to determine if digest has actually been + // pre-computed. + if (hasCachedDigest()) + return Digest; + uint32_t X = ComputeDigest(getLeft(), getRight(), getValue()); + Digest = X; + MarkedCachedDigest(); return X; } }; @@ -394,7 +398,7 @@ private: bool isEmpty(TreeTy* T) const { return !T; } unsigned Height(TreeTy* T) const { return T ? T->getHeight() : 0; } - TreeTy* Left(TreeTy* T) const { return T->getSafeLeft(); } + TreeTy* Left(TreeTy* T) const { return T->getLeft(); } TreeTy* Right(TreeTy* T) const { return T->getRight(); } value_type_ref Value(TreeTy* T) const { return T->Value; } @@ -404,7 +408,6 @@ private: return ( hl > hr ? hl : hr ) + 1; } - static bool CompareTreeWithSection(TreeTy* T, typename TreeTy::iterator& TI, typename TreeTy::iterator& TE) { @@ -428,62 +431,10 @@ private: // returned to the caller. //===--------------------------------------------------===// - TreeTy* CreateNode(TreeTy* L, value_type_ref V, TreeTy* R) { - // Search the FoldingSet bucket for a Tree with the same digest. - FoldingSetNodeID ID; - unsigned digest = TreeTy::ComputeDigest(L, R, V); - ID.AddInteger(digest); - unsigned hash = ID.ComputeHash(); - - typename CacheTy::bucket_iterator I = Cache.bucket_begin(hash); - typename CacheTy::bucket_iterator E = Cache.bucket_end(hash); - - for (; I != E; ++I) { - TreeTy* T = &*I; - - if (T->ComputeDigest() != digest) - continue; - - // We found a collision. Perform a comparison of Contents('T') - // with Contents('L')+'V'+Contents('R'). - - typename TreeTy::iterator TI = T->begin(), TE = T->end(); - - // First compare Contents('L') with the (initial) contents of T. - if (!CompareTreeWithSection(L, TI, TE)) - continue; - - // Now compare the new data element. - if (TI == TE || !TI->ElementEqual(V)) - continue; - - ++TI; - - // Now compare the remainder of 'T' with 'R'. - if (!CompareTreeWithSection(R, TI, TE)) - continue; - - if (TI != TE) // Contents('R') did not match suffix of 'T'. - continue; - - // Trees did match! Return 'T'. - return T; - } - - // No tree with the contents: Contents('L')+'V'+Contents('R'). - // Create it. - - // Allocate the new tree node and insert it into the cache. + TreeTy* CreateNode(TreeTy* L, value_type_ref V, TreeTy* R) { BumpPtrAllocator& A = getAllocator(); TreeTy* T = (TreeTy*) A.Allocate<TreeTy>(); new (T) TreeTy(L,R,V,IncrementHeight(L,R)); - - // We do not insert 'T' into the FoldingSet here. This is because - // this tree is still mutable and things may get rebalanced. - // Because our digest is associative and based on the contents of - // the set, this should hopefully not cause any strange bugs. - // 'T' is inserted by 'MarkImmutable'. - return T; } @@ -496,7 +447,8 @@ private: OldTree->setHeight(IncrementHeight(L,R)); return OldTree; } - else return CreateNode(L, Value(OldTree), R); + else + return CreateNode(L, Value(OldTree), R); } /// Balance - Used by Add_internal and Remove_internal to @@ -615,12 +567,56 @@ private: T->MarkImmutable(); MarkImmutable(Left(T)); MarkImmutable(Right(T)); + } + +public: + TreeTy *GetCanonicalTree(TreeTy *TNew) { + if (!TNew) + return NULL; + + // Search the FoldingSet bucket for a Tree with the same digest. + FoldingSetNodeID ID; + unsigned digest = TNew->ComputeDigest(); + ID.AddInteger(digest); + unsigned hash = ID.ComputeHash(); + + typename CacheTy::bucket_iterator I = Cache.bucket_begin(hash); + typename CacheTy::bucket_iterator E = Cache.bucket_end(hash); + + for (; I != E; ++I) { + TreeTy *T = &*I; + + if (T->ComputeDigest() != digest) + continue; + + // We found a collision. Perform a comparison of Contents('T') + // with Contents('L')+'V'+Contents('R'). + typename TreeTy::iterator TI = T->begin(), TE = T->end(); + + // First compare Contents('L') with the (initial) contents of T. + if (!CompareTreeWithSection(TNew->getLeft(), TI, TE)) + continue; + + // Now compare the new data element. + if (TI == TE || !TI->ElementEqual(TNew->getValue())) + continue; + + ++TI; + + // Now compare the remainder of 'T' with 'R'. + if (!CompareTreeWithSection(TNew->getRight(), TI, TE)) + continue; + + if (TI != TE) + continue; // Contents('R') did not match suffix of 'T'. + + // Trees did match! Return 'T'. + return T; + } - // Now that the node is immutable it can safely be inserted - // into the node cache. - llvm::FoldingSetNodeID ID; - ID.AddInteger(T->ComputeDigest()); - Cache.InsertNode(T, (void*) &*Cache.bucket_end(ID.ComputeHash())); + // 'TNew' is the only tree of its kind. Return it. + Cache.InsertNode(TNew, (void*) &*Cache.bucket_end(hash)); + return TNew; } }; @@ -701,7 +697,7 @@ public: switch (getVisitState()) { case VisitedNone: - if (TreeTy* L = Current->getSafeLeft()) + if (TreeTy* L = Current->getLeft()) stack.push_back(reinterpret_cast<uintptr_t>(L)); else stack.back() |= VisitedLeft; @@ -940,8 +936,8 @@ public: typedef ImutAVLTree<ValInfo> TreeTy; private: - TreeTy* Root; - + 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 @@ -951,15 +947,19 @@ public: class Factory { typename TreeTy::Factory F; + const bool Canonicalize; public: - Factory() {} + Factory(bool canonicalize = true) + : Canonicalize(canonicalize) {} - Factory(BumpPtrAllocator& Alloc) - : F(Alloc) {} + Factory(BumpPtrAllocator& Alloc, bool canonicalize = true) + : F(Alloc), Canonicalize(canonicalize) {} /// GetEmptySet - Returns an immutable set that contains no elements. - ImmutableSet GetEmptySet() { return ImmutableSet(F.GetEmptyTree()); } + ImmutableSet GetEmptySet() { + return ImmutableSet(F.GetEmptyTree()); + } /// Add - Creates a new immutable set that contains all of the values /// of the original set with the addition of the specified value. If @@ -969,7 +969,8 @@ public: /// The memory allocated to represent the set is released when the /// factory object that created the set is destroyed. ImmutableSet Add(ImmutableSet Old, value_type_ref V) { - return ImmutableSet(F.Add(Old.Root,V)); + TreeTy *NewT = F.Add(Old.Root, V); + return ImmutableSet(Canonicalize ? F.GetCanonicalTree(NewT) : NewT); } /// Remove - Creates a new immutable set that contains all of the values @@ -980,7 +981,8 @@ public: /// The memory allocated to represent the set is released when the /// factory object that created the set is destroyed. ImmutableSet Remove(ImmutableSet Old, value_type_ref V) { - return ImmutableSet(F.Remove(Old.Root,V)); + TreeTy *NewT = F.Remove(Old.Root, V); + return ImmutableSet(Canonicalize ? F.GetCanonicalTree(NewT) : NewT); } BumpPtrAllocator& getAllocator() { return F.getAllocator(); } @@ -993,7 +995,7 @@ public: friend class Factory; /// contains - Returns true if the set contains the specified value. - bool contains(const value_type_ref V) const { + bool contains(value_type_ref V) const { return Root ? Root->contains(V) : false; } @@ -1005,7 +1007,9 @@ public: return Root && RHS.Root ? Root->isNotEqual(*RHS.Root) : Root != RHS.Root; } - TreeTy* getRoot() const { return Root; } + TreeTy *getRoot() { + return Root; + } /// isEmpty - Return true if the set contains no elements. bool isEmpty() const { return !Root; } @@ -1026,11 +1030,10 @@ public: class iterator { typename TreeTy::iterator itr; - - iterator() {} iterator(TreeTy* t) : itr(t) {} friend class ImmutableSet<ValT,ValInfo>; public: + iterator() {} inline value_type_ref operator*() const { return itr->getValue(); } inline iterator& operator++() { ++itr; return *this; } inline iterator operator++(int) { iterator tmp(*this); ++itr; return tmp; } diff --git a/include/llvm/ADT/IndexedMap.h b/include/llvm/ADT/IndexedMap.h index ff5d3a1..89f0dfa 100644 --- a/include/llvm/ADT/IndexedMap.h +++ b/include/llvm/ADT/IndexedMap.h @@ -26,7 +26,7 @@ namespace llvm { - struct IdentityFunctor : std::unary_function<unsigned, unsigned> { + struct IdentityFunctor : public std::unary_function<unsigned, unsigned> { unsigned operator()(unsigned Index) const { return Index; } diff --git a/include/llvm/ADT/PointerIntPair.h b/include/llvm/ADT/PointerIntPair.h index 0aa478b..73ba3c7 100644 --- a/include/llvm/ADT/PointerIntPair.h +++ b/include/llvm/ADT/PointerIntPair.h @@ -65,7 +65,8 @@ public: } PointerTy getPointer() const { - return reinterpret_cast<PointerTy>(Value & PointerBitMask); + return PtrTraits::getFromVoidPointer( + reinterpret_cast<void*>(Value & PointerBitMask)); } IntType getInt() const { @@ -73,7 +74,8 @@ public: } void setPointer(PointerTy Ptr) { - intptr_t PtrVal = reinterpret_cast<intptr_t>(Ptr); + intptr_t PtrVal + = reinterpret_cast<intptr_t>(PtrTraits::getAsVoidPointer(Ptr)); assert((PtrVal & ((1 << PtrTraits::NumLowBitsAvailable)-1)) == 0 && "Pointer is not sufficiently aligned"); // Preserve all low bits, just update the pointer. @@ -141,8 +143,7 @@ public: return PointerIntPair<PointerTy, IntBits, IntType>::getFromOpaqueValue(P); } enum { - NumLowBitsAvailable = - PointerLikeTypeTraits<PointerTy>::NumLowBitsAvailable - IntBits + NumLowBitsAvailable = PtrTraits::NumLowBitsAvailable - IntBits }; }; diff --git a/include/llvm/ADT/PointerUnion.h b/include/llvm/ADT/PointerUnion.h index 1b36aee..33f2fcb 100644 --- a/include/llvm/ADT/PointerUnion.h +++ b/include/llvm/ADT/PointerUnion.h @@ -79,7 +79,7 @@ namespace llvm { Val.setInt(1); } - /// isNull - Return true if the pointer help in the union is null, + /// isNull - Return true if the pointer held in the union is null, /// regardless of which type it is. bool isNull() const { return Val.getPointer() == 0; } operator bool() const { return !isNull(); } @@ -176,7 +176,7 @@ namespace llvm { Val = V; } - /// isNull - Return true if the pointer help in the union is null, + /// isNull - Return true if the pointer held in the union is null, /// regardless of which type it is. bool isNull() const { return Val.isNull(); } operator bool() const { return !isNull(); } @@ -254,6 +254,115 @@ namespace llvm { ::NumLowBitsAvailable }; }; + + /// PointerUnion4 - This is a pointer union of four pointer types. See + /// documentation for PointerUnion for usage. + template <typename PT1, typename PT2, typename PT3, typename PT4> + class PointerUnion4 { + public: + typedef PointerUnion<PT1, PT2> InnerUnion1; + typedef PointerUnion<PT3, PT4> InnerUnion2; + typedef PointerUnion<InnerUnion1, InnerUnion2> ValTy; + private: + ValTy Val; + public: + PointerUnion4() {} + + PointerUnion4(PT1 V) { + Val = InnerUnion1(V); + } + PointerUnion4(PT2 V) { + Val = InnerUnion1(V); + } + PointerUnion4(PT3 V) { + Val = InnerUnion2(V); + } + PointerUnion4(PT4 V) { + Val = InnerUnion2(V); + } + + /// isNull - Return true if the pointer held in the union is null, + /// regardless of which type it is. + bool isNull() const { return Val.isNull(); } + operator bool() const { return !isNull(); } + + /// is<T>() return true if the Union currently holds the type matching T. + template<typename T> + int is() const { + // Is it PT1/PT2? + if (::llvm::getPointerUnionTypeNum<PT1, PT2>((T*)0) != -1) + return Val.is<InnerUnion1>() && Val.get<InnerUnion1>().is<T>(); + return Val.is<InnerUnion2>() && Val.get<InnerUnion2>().is<T>(); + } + + /// get<T>() - Return the value of the specified pointer type. If the + /// specified pointer type is incorrect, assert. + template<typename T> + T get() const { + assert(is<T>() && "Invalid accessor called"); + // Is it PT1/PT2? + if (::llvm::getPointerUnionTypeNum<PT1, PT2>((T*)0) != -1) + return Val.get<InnerUnion1>().get<T>(); + + return Val.get<InnerUnion2>().get<T>(); + } + + /// dyn_cast<T>() - If the current value is of the specified pointer type, + /// return it, otherwise return null. + template<typename T> + T dyn_cast() const { + if (is<T>()) return get<T>(); + return T(); + } + + /// Assignment operators - Allow assigning into this union from either + /// pointer type, setting the discriminator to remember what it came from. + const PointerUnion4 &operator=(const PT1 &RHS) { + Val = InnerUnion1(RHS); + return *this; + } + const PointerUnion4 &operator=(const PT2 &RHS) { + Val = InnerUnion1(RHS); + return *this; + } + const PointerUnion4 &operator=(const PT3 &RHS) { + Val = InnerUnion2(RHS); + return *this; + } + const PointerUnion4 &operator=(const PT4 &RHS) { + Val = InnerUnion2(RHS); + return *this; + } + + void *getOpaqueValue() const { return Val.getOpaqueValue(); } + static PointerUnion4 getFromOpaqueValue(void *VP) { + PointerUnion4 V; + V.Val = ValTy::getFromOpaqueValue(VP); + return V; + } + }; + + // Teach SmallPtrSet that PointerUnion4 is "basically a pointer", that has + // # low bits available = min(PT1bits,PT2bits,PT2bits)-2. + template<typename PT1, typename PT2, typename PT3, typename PT4> + class PointerLikeTypeTraits<PointerUnion4<PT1, PT2, PT3, PT4> > { + public: + static inline void * + getAsVoidPointer(const PointerUnion4<PT1, PT2, PT3, PT4> &P) { + return P.getOpaqueValue(); + } + static inline PointerUnion4<PT1, PT2, PT3, PT4> + getFromVoidPointer(void *P) { + return PointerUnion4<PT1, PT2, PT3, PT4>::getFromOpaqueValue(P); + } + + // The number of bits available are the min of the two pointer types. + enum { + NumLowBitsAvailable = + PointerLikeTypeTraits<typename PointerUnion4<PT1, PT2, PT3, PT4>::ValTy> + ::NumLowBitsAvailable + }; + }; } #endif diff --git a/include/llvm/ADT/PostOrderIterator.h b/include/llvm/ADT/PostOrderIterator.h index b477d0a..8315bc9 100644 --- a/include/llvm/ADT/PostOrderIterator.h +++ b/include/llvm/ADT/PostOrderIterator.h @@ -17,7 +17,6 @@ #define LLVM_ADT_POSTORDERITERATOR_H #include "llvm/ADT/GraphTraits.h" -#include "llvm/ADT/iterator.h" #include "llvm/ADT/SmallPtrSet.h" #include <set> #include <stack> @@ -43,9 +42,11 @@ template<class GraphT, class SetType = llvm::SmallPtrSet<typename GraphTraits<GraphT>::NodeType*, 8>, bool ExtStorage = false, class GT = GraphTraits<GraphT> > -class po_iterator : public forward_iterator<typename GT::NodeType, ptrdiff_t>, +class po_iterator : public std::iterator<std::forward_iterator_tag, + typename GT::NodeType, ptrdiff_t>, public po_iterator_storage<SetType, ExtStorage> { - typedef forward_iterator<typename GT::NodeType, ptrdiff_t> super; + typedef std::iterator<std::forward_iterator_tag, + typename GT::NodeType, ptrdiff_t> super; typedef typename GT::NodeType NodeType; typedef typename GT::ChildIteratorType ChildItTy; @@ -71,7 +72,7 @@ class po_iterator : public forward_iterator<typename GT::NodeType, ptrdiff_t>, inline po_iterator() {} // End is when stack is empty. inline po_iterator(NodeType *BB, SetType &S) : - po_iterator_storage<SetType, ExtStorage>(&S) { + po_iterator_storage<SetType, ExtStorage>(S) { if(!S.count(BB)) { this->Visited.insert(BB); VisitStack.push(std::make_pair(BB, GT::child_begin(BB))); @@ -80,7 +81,7 @@ class po_iterator : public forward_iterator<typename GT::NodeType, ptrdiff_t>, } inline po_iterator(SetType &S) : - po_iterator_storage<SetType, ExtStorage>(&S) { + po_iterator_storage<SetType, ExtStorage>(S) { } // End is when stack is empty. public: typedef typename super::pointer pointer; diff --git a/include/llvm/ADT/SCCIterator.h b/include/llvm/ADT/SCCIterator.h index e28f4ca..db985b5 100644 --- a/include/llvm/ADT/SCCIterator.h +++ b/include/llvm/ADT/SCCIterator.h @@ -22,8 +22,7 @@ #define LLVM_ADT_SCCITERATOR_H #include "llvm/ADT/GraphTraits.h" -#include "llvm/ADT/iterator.h" -#include <map> +#include "llvm/ADT/DenseMap.h" #include <vector> namespace llvm { @@ -35,11 +34,13 @@ namespace llvm { /// template<class GraphT, class GT = GraphTraits<GraphT> > class scc_iterator - : public forward_iterator<std::vector<typename GT::NodeType>, ptrdiff_t> { + : public std::iterator<std::forward_iterator_tag, + std::vector<typename GT::NodeType>, ptrdiff_t> { typedef typename GT::NodeType NodeType; typedef typename GT::ChildIteratorType ChildItTy; typedef std::vector<NodeType*> SccTy; - typedef forward_iterator<SccTy, ptrdiff_t> super; + typedef std::iterator<std::forward_iterator_tag, + std::vector<typename GT::NodeType>, ptrdiff_t> super; typedef typename super::reference reference; typedef typename super::pointer pointer; @@ -47,7 +48,7 @@ class scc_iterator // visitNum is the global counter. // nodeVisitNumbers are per-node visit numbers, also used as DFS flags. unsigned visitNum; - std::map<NodeType *, unsigned> nodeVisitNumbers; + DenseMap<NodeType *, unsigned> nodeVisitNumbers; // SCCNodeStack - Stack holding nodes of the SCC. std::vector<NodeType *> SCCNodeStack; @@ -71,7 +72,7 @@ class scc_iterator SCCNodeStack.push_back(N); MinVisitNumStack.push_back(visitNum); VisitStack.push_back(std::make_pair(N, GT::child_begin(N))); - //DOUT << "TarjanSCC: Node " << N << + //errs() << "TarjanSCC: Node " << N << // " : visitNum = " << visitNum << "\n"; } @@ -106,7 +107,7 @@ class scc_iterator if (!MinVisitNumStack.empty() && MinVisitNumStack.back() > minVisitNum) MinVisitNumStack.back() = minVisitNum; - //DOUT << "TarjanSCC: Popped node " << visitingN << + //errs() << "TarjanSCC: Popped node " << visitingN << // " : minVisitNum = " << minVisitNum << "; Node visit num = " << // nodeVisitNumbers[visitingN] << "\n"; diff --git a/include/llvm/ADT/STLExtras.h b/include/llvm/ADT/STLExtras.h index 964e7e0..6f47692 100644 --- a/include/llvm/ADT/STLExtras.h +++ b/include/llvm/ADT/STLExtras.h @@ -19,8 +19,8 @@ #include <cstddef> // for std::size_t #include <functional> +#include <iterator> #include <utility> // for std::pair -#include "llvm/ADT/iterator.h" namespace llvm { @@ -29,6 +29,13 @@ namespace llvm { //===----------------------------------------------------------------------===// template<class Ty> +struct less_ptr : public std::binary_function<Ty, Ty, bool> { + bool operator()(const Ty* left, const Ty* right) const { + return *left < *right; + } +}; + +template<class Ty> struct greater_ptr : public std::binary_function<Ty, Ty, bool> { bool operator()(const Ty* left, const Ty* right) const { return *right < *left; diff --git a/include/llvm/ADT/SmallPtrSet.h b/include/llvm/ADT/SmallPtrSet.h index a189de2..7d00e9a 100644 --- a/include/llvm/ADT/SmallPtrSet.h +++ b/include/llvm/ADT/SmallPtrSet.h @@ -17,6 +17,7 @@ #include <cassert> #include <cstring> +#include <iterator> #include "llvm/Support/DataTypes.h" #include "llvm/Support/PointerLikeTypeTraits.h" @@ -170,7 +171,14 @@ protected: template<typename PtrTy> class SmallPtrSetIterator : public SmallPtrSetIteratorImpl { typedef PointerLikeTypeTraits<PtrTy> PtrTraits; + public: + typedef PtrTy value_type; + typedef PtrTy reference; + typedef PtrTy pointer; + typedef std::ptrdiff_t difference_type; + typedef std::forward_iterator_tag iterator_category; + explicit SmallPtrSetIterator(const void *const *BP) : SmallPtrSetIteratorImpl(BP) {} diff --git a/include/llvm/ADT/SmallSet.h b/include/llvm/ADT/SmallSet.h index caaa96c..d03f1be 100644 --- a/include/llvm/ADT/SmallSet.h +++ b/include/llvm/ADT/SmallSet.h @@ -30,7 +30,7 @@ namespace llvm { template <typename T, unsigned N> class SmallSet { /// Use a SmallVector to hold the elements here (even though it will never - /// reach it's 'large' stage) to avoid calling the default ctors of elements + /// reach its 'large' stage) to avoid calling the default ctors of elements /// we will never use. SmallVector<T, N> Vector; std::set<T> Set; diff --git a/include/llvm/ADT/SmallString.h b/include/llvm/ADT/SmallString.h index 687fa2d..0354625 100644 --- a/include/llvm/ADT/SmallString.h +++ b/include/llvm/ADT/SmallString.h @@ -15,8 +15,7 @@ #define LLVM_ADT_SMALLSTRING_H #include "llvm/ADT/SmallVector.h" -#include "llvm/Support/DataTypes.h" -#include <cstring> +#include "llvm/ADT/StringRef.h" namespace llvm { @@ -37,73 +36,30 @@ public: // Extra methods. - const char *c_str() const { - SmallString *This = const_cast<SmallString*>(this); - // Ensure that there is a \0 at the end of the string. - This->reserve(this->size()+1); - This->End[0] = 0; - return this->begin(); - } + StringRef str() const { return StringRef(this->begin(), this->size()); } + const char *c_str() { + this->push_back(0); + this->pop_back(); + return this->data(); + } + // Extra operators. - const SmallString &operator=(const char *RHS) { + const SmallString &operator=(StringRef RHS) { this->clear(); return *this += RHS; } - SmallString &operator+=(const char *RHS) { - this->append(RHS, RHS+strlen(RHS)); + SmallString &operator+=(StringRef RHS) { + this->append(RHS.begin(), RHS.end()); return *this; } SmallString &operator+=(char C) { this->push_back(C); return *this; } - - SmallString &append_uint_32(uint32_t N) { - char Buffer[20]; - char *BufPtr = Buffer+20; - - if (N == 0) *--BufPtr = '0'; // Handle special case. - - while (N) { - *--BufPtr = '0' + char(N % 10); - N /= 10; - } - this->append(BufPtr, Buffer+20); - return *this; - } - - SmallString &append_uint(uint64_t N) { - if (N == uint32_t(N)) - return append_uint_32(uint32_t(N)); - - char Buffer[40]; - char *BufPtr = Buffer+40; - - if (N == 0) *--BufPtr = '0'; // Handle special case... - - while (N) { - *--BufPtr = '0' + char(N % 10); - N /= 10; - } - - this->append(BufPtr, Buffer+40); - return *this; - } - - SmallString &append_sint(int64_t N) { - // TODO, wrong for minint64. - if (N < 0) { - this->push_back('-'); - N = -N; - } - return append_uint(N); - } - }; - } #endif diff --git a/include/llvm/ADT/SmallVector.h b/include/llvm/ADT/SmallVector.h index f59a438..f3b4533 100644 --- a/include/llvm/ADT/SmallVector.h +++ b/include/llvm/ADT/SmallVector.h @@ -14,7 +14,6 @@ #ifndef LLVM_ADT_SMALLVECTOR_H #define LLVM_ADT_SMALLVECTOR_H -#include "llvm/ADT/iterator.h" #include "llvm/Support/type_traits.h" #include <algorithm> #include <cassert> @@ -122,11 +121,11 @@ public: reference operator[](unsigned idx) { - assert (Begin + idx < End); + assert(Begin + idx < End); return Begin[idx]; } const_reference operator[](unsigned idx) const { - assert (Begin + idx < End); + assert(Begin + idx < End); return Begin[idx]; } @@ -399,6 +398,24 @@ public: RHS.begin(), RHS.end()); } + /// capacity - Return the total number of elements in the currently allocated + /// buffer. + size_t capacity() const { return Capacity - Begin; } + + /// set_size - Set the array size to \arg N, which the current array must have + /// enough capacity for. + /// + /// This does not construct or destroy any elements in the vector. + /// + /// Clients can use this in conjunction with capacity() to write past the end + /// of the buffer when they know that more elements are available, and only + /// update the size later. This avoids the cost of value initializing elements + /// which will only be overwritten. + void set_size(unsigned N) { + assert(N <= capacity()); + End = Begin + N; + } + private: /// isSmall - Return true if this is a smallvector which has not had dynamic /// memory allocated for it. diff --git a/include/llvm/ADT/SparseBitVector.h b/include/llvm/ADT/SparseBitVector.h index 6230135..b7a6873 100644 --- a/include/llvm/ADT/SparseBitVector.h +++ b/include/llvm/ADT/SparseBitVector.h @@ -15,13 +15,14 @@ #ifndef LLVM_ADT_SPARSEBITVECTOR_H #define LLVM_ADT_SPARSEBITVECTOR_H +#include "llvm/ADT/ilist.h" +#include "llvm/ADT/ilist_node.h" +#include "llvm/Support/DataTypes.h" +#include "llvm/Support/MathExtras.h" +#include "llvm/Support/raw_ostream.h" #include <cassert> #include <climits> #include <cstring> -#include "llvm/Support/DataTypes.h" -#include "llvm/ADT/STLExtras.h" -#include "llvm/Support/MathExtras.h" -#include "llvm/ADT/ilist.h" namespace llvm { @@ -41,7 +42,7 @@ namespace llvm { template <unsigned ElementSize = 128> struct SparseBitVectorElement - : ilist_node<SparseBitVectorElement<ElementSize> > { + : public ilist_node<SparseBitVectorElement<ElementSize> > { public: typedef unsigned long BitWord; enum { @@ -887,7 +888,7 @@ operator-(const SparseBitVector<ElementSize> &LHS, // Dump a SparseBitVector to a stream template <unsigned ElementSize> -void dump(const SparseBitVector<ElementSize> &LHS, llvm::OStream &out) { +void dump(const SparseBitVector<ElementSize> &LHS, raw_ostream &out) { out << "[ "; typename SparseBitVector<ElementSize>::iterator bi; diff --git a/include/llvm/ADT/StringExtras.h b/include/llvm/ADT/StringExtras.h index e40e409..3d1993c 100644 --- a/include/llvm/ADT/StringExtras.h +++ b/include/llvm/ADT/StringExtras.h @@ -103,10 +103,6 @@ static inline std::string itostr(int64_t X) { return utostr(static_cast<uint64_t>(X)); } -static inline std::string itohexstr(int64_t X) { - return utohexstr(static_cast<uint64_t>(X)); -} - static inline std::string ftostr(double V) { char Buffer[200]; sprintf(Buffer, "%20.6e", V); diff --git a/include/llvm/ADT/StringMap.h b/include/llvm/ADT/StringMap.h index a15d24e..73fd635 100644 --- a/include/llvm/ADT/StringMap.h +++ b/include/llvm/ADT/StringMap.h @@ -14,6 +14,7 @@ #ifndef LLVM_ADT_STRINGMAP_H #define LLVM_ADT_STRINGMAP_H +#include "llvm/ADT/StringRef.h" #include "llvm/Support/Allocator.h" #include <cstring> #include <string> @@ -95,12 +96,12 @@ protected: /// specified bucket will be non-null. Otherwise, it will be null. In either /// case, the FullHashValue field of the bucket will be set to the hash value /// of the string. - unsigned LookupBucketFor(const char *KeyStart, const char *KeyEnd); + unsigned LookupBucketFor(const StringRef &Key); /// FindKey - Look up the bucket that contains the specified key. If it exists /// in the map, return the bucket number of the key. Otherwise return -1. /// This does not modify the map. - int FindKey(const char *KeyStart, const char *KeyEnd) const; + int FindKey(const StringRef &Key) const; /// RemoveKey - Remove the specified StringMapEntry from the table, but do not /// delete it. This aborts if the value isn't in the table. @@ -108,7 +109,7 @@ protected: /// RemoveKey - Remove the StringMapEntry for the specified key from the /// table, returning it. If the key is not in the table, this returns null. - StringMapEntryBase *RemoveKey(const char *KeyStart, const char *KeyEnd); + StringMapEntryBase *RemoveKey(const StringRef &Key); private: void init(unsigned Size); public: @@ -136,6 +137,10 @@ public: StringMapEntry(unsigned strLen, const ValueTy &V) : StringMapEntryBase(strLen), second(V) {} + StringRef getKey() const { + return StringRef(getKeyData(), getKeyLength()); + } + const ValueTy &getValue() const { return second; } ValueTy &getValue() { return second; } @@ -277,75 +282,40 @@ public: return const_iterator(TheTable+NumBuckets, true); } - iterator find(const char *KeyStart, const char *KeyEnd) { - int Bucket = FindKey(KeyStart, KeyEnd); + iterator find(const StringRef &Key) { + int Bucket = FindKey(Key); if (Bucket == -1) return end(); return iterator(TheTable+Bucket); } - iterator find(const char *Key) { - return find(Key, Key + strlen(Key)); - } - iterator find(const std::string &Key) { - return find(Key.data(), Key.data() + Key.size()); - } - const_iterator find(const char *KeyStart, const char *KeyEnd) const { - int Bucket = FindKey(KeyStart, KeyEnd); + const_iterator find(const StringRef &Key) const { + int Bucket = FindKey(Key); if (Bucket == -1) return end(); return const_iterator(TheTable+Bucket); } - const_iterator find(const char *Key) const { - return find(Key, Key + strlen(Key)); - } - const_iterator find(const std::string &Key) const { - return find(Key.data(), Key.data() + Key.size()); - } /// lookup - Return the entry for the specified key, or a default /// constructed value if no such entry exists. - ValueTy lookup(const char *KeyStart, const char *KeyEnd) const { - const_iterator it = find(KeyStart, KeyEnd); - if (it != end()) - return it->second; - return ValueTy(); - } - ValueTy lookup(const char *Key) const { - const_iterator it = find(Key); - if (it != end()) - return it->second; - return ValueTy(); - } - ValueTy lookup(const std::string &Key) const { + ValueTy lookup(const StringRef &Key) const { const_iterator it = find(Key); if (it != end()) return it->second; return ValueTy(); } - ValueTy& operator[](const char *Key) { - return GetOrCreateValue(Key, Key + strlen(Key)).getValue(); - } - ValueTy& operator[](const std::string &Key) { - return GetOrCreateValue(Key.data(), Key.data() + Key.size()).getValue(); + ValueTy& operator[](const StringRef &Key) { + return GetOrCreateValue(Key).getValue(); } - size_type count(const char *KeyStart, const char *KeyEnd) const { - return find(KeyStart, KeyEnd) == end() ? 0 : 1; - } - size_type count(const char *Key) const { - return count(Key, Key + strlen(Key)); - } - size_type count(const std::string &Key) const { - return count(Key.data(), Key.data() + Key.size()); + size_type count(const StringRef &Key) const { + return find(Key) == end() ? 0 : 1; } /// insert - Insert the specified key/value pair into the map. If the key /// already exists in the map, return false and ignore the request, otherwise /// insert it and return true. bool insert(MapEntryTy *KeyValue) { - unsigned BucketNo = - LookupBucketFor(KeyValue->getKeyData(), - KeyValue->getKeyData()+KeyValue->getKeyLength()); + unsigned BucketNo = LookupBucketFor(KeyValue->getKey()); ItemBucket &Bucket = TheTable[BucketNo]; if (Bucket.Item && Bucket.Item != getTombstoneVal()) return false; // Already exists in map. @@ -380,15 +350,15 @@ public: /// exists, return it. Otherwise, default construct a value, insert it, and /// return. template <typename InitTy> - StringMapEntry<ValueTy> &GetOrCreateValue(const char *KeyStart, - const char *KeyEnd, + StringMapEntry<ValueTy> &GetOrCreateValue(const StringRef &Key, InitTy Val) { - unsigned BucketNo = LookupBucketFor(KeyStart, KeyEnd); + unsigned BucketNo = LookupBucketFor(Key); ItemBucket &Bucket = TheTable[BucketNo]; if (Bucket.Item && Bucket.Item != getTombstoneVal()) return *static_cast<MapEntryTy*>(Bucket.Item); - MapEntryTy *NewItem = MapEntryTy::Create(KeyStart, KeyEnd, Allocator, Val); + MapEntryTy *NewItem = + MapEntryTy::Create(Key.begin(), Key.end(), Allocator, Val); if (Bucket.Item == getTombstoneVal()) --NumTombstones; @@ -403,9 +373,20 @@ public: return *NewItem; } + StringMapEntry<ValueTy> &GetOrCreateValue(const StringRef &Key) { + return GetOrCreateValue(Key, ValueTy()); + } + + template <typename InitTy> + StringMapEntry<ValueTy> &GetOrCreateValue(const char *KeyStart, + const char *KeyEnd, + InitTy Val) { + return GetOrCreateValue(StringRef(KeyStart, KeyEnd - KeyStart), Val); + } + StringMapEntry<ValueTy> &GetOrCreateValue(const char *KeyStart, const char *KeyEnd) { - return GetOrCreateValue(KeyStart, KeyEnd, ValueTy()); + return GetOrCreateValue(StringRef(KeyStart, KeyEnd - KeyStart)); } /// remove - Remove the specified key/value pair from the map, but do not @@ -420,14 +401,7 @@ public: V.Destroy(Allocator); } - bool erase(const char *Key) { - iterator I = find(Key); - if (I == end()) return false; - erase(I); - return true; - } - - bool erase(const std::string &Key) { + bool erase(const StringRef &Key) { iterator I = find(Key); if (I == end()) return false; erase(I); diff --git a/include/llvm/ADT/StringRef.h b/include/llvm/ADT/StringRef.h new file mode 100644 index 0000000..aa7d577 --- /dev/null +++ b/include/llvm/ADT/StringRef.h @@ -0,0 +1,335 @@ +//===--- StringRef.h - Constant String Reference Wrapper --------*- 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_STRINGREF_H +#define LLVM_ADT_STRINGREF_H + +#include <algorithm> +#include <cassert> +#include <cstring> +#include <string> + +namespace llvm { + + /// StringRef - Represent a constant reference to a string, i.e. a character + /// array and a length, which need not be null terminated. + /// + /// This class does not own the string data, it is expected to be used in + /// situations where the character data resides in some other buffer, whose + /// lifetime extends past that of the StringRef. For this reason, it is not in + /// general safe to store a StringRef. + class StringRef { + public: + typedef const char *iterator; + static const size_t npos = ~size_t(0); + typedef size_t size_type; + + private: + /// The start of the string, in an external buffer. + const char *Data; + + /// The length of the string. + size_t Length; + + public: + /// @name Constructors + /// @{ + + /// Construct an empty string ref. + /*implicit*/ StringRef() : Data(0), Length(0) {} + + /// Construct a string ref from a cstring. + /*implicit*/ StringRef(const char *Str) + : Data(Str) { if (Str) Length = ::strlen(Str); else Length = 0; } + + /// Construct a string ref from a pointer and length. + /*implicit*/ StringRef(const char *data, unsigned length) + : Data(data), Length(length) {} + + /// Construct a string ref from an std::string. + /*implicit*/ StringRef(const std::string &Str) + : Data(Str.c_str()), Length(Str.length()) {} + + /// @} + /// @name Iterators + /// @{ + + iterator begin() const { return Data; } + + iterator end() const { return Data + Length; } + + /// @} + /// @name String Operations + /// @{ + + /// data - Get a pointer to the start of the string (which may not be null + /// terminated). + const char *data() const { return Data; } + + /// empty - Check if the string is empty. + bool empty() const { return Length == 0; } + + /// size - Get the string size. + size_t size() const { return Length; } + + /// front - Get the first character in the string. + char front() const { + assert(!empty()); + return Data[0]; + } + + /// back - Get the last character in the string. + char back() const { + assert(!empty()); + return Data[Length-1]; + } + + /// equals - Check for string equality, this is more efficient than + /// compare() when the relative ordering of inequal strings isn't needed. + bool equals(const StringRef &RHS) const { + return (Length == RHS.Length && + memcmp(Data, RHS.Data, RHS.Length) == 0); + } + + /// compare - Compare two strings; the result is -1, 0, or 1 if this string + /// is lexicographically less than, equal to, or greater than the \arg RHS. + int compare(const StringRef &RHS) const { + // Check the prefix for a mismatch. + if (int Res = memcmp(Data, RHS.Data, std::min(Length, RHS.Length))) + return Res < 0 ? -1 : 1; + + // Otherwise the prefixes match, so we only need to check the lengths. + if (Length == RHS.Length) + return 0; + return Length < RHS.Length ? -1 : 1; + } + + /// str - Get the contents as an std::string. + std::string str() const { return std::string(Data, Length); } + + /// @} + /// @name Operator Overloads + /// @{ + + char operator[](size_t Index) const { + assert(Index < Length && "Invalid index!"); + return Data[Index]; + } + + /// @} + /// @name Type Conversions + /// @{ + + operator std::string() const { + return str(); + } + + /// @} + /// @name String Predicates + /// @{ + + /// startswith - Check if this string starts with the given \arg Prefix. + bool startswith(const StringRef &Prefix) const { + return substr(0, Prefix.Length).equals(Prefix); + } + + /// endswith - Check if this string ends with the given \arg Suffix. + bool endswith(const StringRef &Suffix) const { + return slice(size() - Suffix.Length, size()).equals(Suffix); + } + + /// @} + /// @name String Searching + /// @{ + + /// find - Search for the first character \arg C in the string. + /// + /// \return - The index of the first occurence of \arg C, or npos if not + /// found. + size_t find(char C) const { + for (size_t i = 0, e = Length; i != e; ++i) + if (Data[i] == C) + return i; + return npos; + } + + /// find - Search for the first string \arg Str in the string. + /// + /// \return - The index of the first occurence of \arg Str, or npos if not + /// found. + size_t find(const StringRef &Str) const; + + /// rfind - Search for the last character \arg C in the string. + /// + /// \return - The index of the last occurence of \arg C, or npos if not + /// found. + size_t rfind(char C, size_t From = npos) const { + From = std::min(From, Length); + size_t i = From; + while (i != 0) { + --i; + if (Data[i] == C) + return i; + } + return npos; + } + + /// rfind - Search for the last string \arg Str in the string. + /// + /// \return - The index of the last occurence of \arg Str, or npos if not + /// found. + size_t rfind(const StringRef &Str) const; + + /// find_first_of - Find the first instance of the specified character or + /// return npos if not in string. Same as find. + size_type find_first_of(char C) const { return find(C); } + + /// find_first_of - Find the first character from the string 'Chars' in the + /// current string or return npos if not in string. + size_type find_first_of(StringRef Chars) const; + + /// find_first_not_of - Find the first character in the string that is not + /// in the string 'Chars' or return npos if all are in string. Same as find. + size_type find_first_not_of(StringRef Chars) const; + + /// @} + /// @name Helpful Algorithms + /// @{ + + /// count - Return the number of occurrences of \arg C in the string. + size_t count(char C) const { + size_t Count = 0; + for (size_t i = 0, e = Length; i != e; ++i) + if (Data[i] == C) + ++Count; + return Count; + } + + /// count - Return the number of non-overlapped occurrences of \arg Str in + /// the string. + size_t count(const 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 + /// 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. + /// + bool getAsInteger(unsigned Radix, long long &Result) const; + bool getAsInteger(unsigned Radix, unsigned long long &Result) const; + bool getAsInteger(unsigned Radix, int &Result) const; + bool getAsInteger(unsigned Radix, unsigned &Result) const; + + // TODO: Provide overloads for int/unsigned that check for overflow. + + /// @} + /// @name Substring Operations + /// @{ + + /// substr - Return a reference to the substring from [Start, Start + N). + /// + /// \param Start - The index of the starting character in the substring; if + /// the index is npos or greater than the length of the string then the + /// empty substring will be returned. + /// + /// \param N - The number of characters to included in the substring. If N + /// exceeds the number of characters remaining in the string, the string + /// suffix (starting with \arg Start) will be returned. + StringRef substr(size_t Start, size_t N = npos) const { + Start = std::min(Start, Length); + return StringRef(Data + Start, std::min(N, Length - Start)); + } + + /// slice - Return a reference to the substring from [Start, End). + /// + /// \param Start - The index of the starting character in the substring; if + /// the index is npos or greater than the length of the string then the + /// empty substring will be returned. + /// + /// \param End - The index following the last character to include in the + /// substring. If this is npos, or less than \arg Start, or exceeds the + /// number of characters remaining in the string, the string suffix + /// (starting with \arg Start) will be returned. + StringRef slice(size_t Start, size_t End) const { + Start = std::min(Start, Length); + End = std::min(std::max(Start, End), Length); + return StringRef(Data + Start, End - Start); + } + + /// split - Split into two substrings around the first occurence of a + /// separator character. + /// + /// If \arg 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 + /// pair (LHS, RHS) where (*this == LHS) and (RHS == ""). + /// + /// \param Separator - The character to split on. + /// \return - The split substrings. + std::pair<StringRef, StringRef> split(char Separator) const { + size_t Idx = find(Separator); + if (Idx == npos) + return std::make_pair(*this, StringRef()); + return std::make_pair(slice(0, Idx), slice(Idx+1, npos)); + } + + /// rsplit - Split into two substrings around the last occurence of a + /// separator character. + /// + /// If \arg 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 + /// pair (LHS, RHS) where (*this == LHS) and (RHS == ""). + /// + /// \param Separator - The character to split on. + /// \return - The split substrings. + std::pair<StringRef, StringRef> rsplit(char Separator) const { + size_t Idx = rfind(Separator); + if (Idx == npos) + return std::make_pair(*this, StringRef()); + return std::make_pair(slice(0, Idx), slice(Idx+1, npos)); + } + + /// @} + }; + + /// @name StringRef Comparison Operators + /// @{ + + inline bool operator==(const StringRef &LHS, const StringRef &RHS) { + return LHS.equals(RHS); + } + + inline bool operator!=(const StringRef &LHS, const StringRef &RHS) { + return !(LHS == RHS); + } + + inline bool operator<(const StringRef &LHS, const StringRef &RHS) { + return LHS.compare(RHS) == -1; + } + + inline bool operator<=(const StringRef &LHS, const StringRef &RHS) { + return LHS.compare(RHS) != 1; + } + + inline bool operator>(const StringRef &LHS, const StringRef &RHS) { + return LHS.compare(RHS) == 1; + } + + inline bool operator>=(const StringRef &LHS, const StringRef &RHS) { + return LHS.compare(RHS) != -1; + } + + /// @} + +} + +#endif diff --git a/include/llvm/ADT/Trie.h b/include/llvm/ADT/Trie.h index ed94f9d..cf92862 100644 --- a/include/llvm/ADT/Trie.h +++ b/include/llvm/ADT/Trie.h @@ -118,12 +118,12 @@ public: #if 0 inline void dump() { - std::cerr << "Node: " << this << "\n" + llvm::cerr << "Node: " << this << "\n" << "Label: " << Label << "\n" << "Children:\n"; for (iterator I = Children.begin(), E = Children.end(); I != E; ++I) - std::cerr << (*I)->Label << "\n"; + llvm::cerr << (*I)->Label << "\n"; } #endif diff --git a/include/llvm/ADT/Triple.h b/include/llvm/ADT/Triple.h index 96c0357..89736bc 100644 --- a/include/llvm/ADT/Triple.h +++ b/include/llvm/ADT/Triple.h @@ -10,9 +10,17 @@ #ifndef LLVM_ADT_TRIPLE_H #define LLVM_ADT_TRIPLE_H +#include "llvm/ADT/StringRef.h" #include <string> +// Some system headers or GCC predefined macros conflict with identifiers in +// this file. Undefine them here. +#undef mips +#undef sparc + namespace llvm { +class StringRef; +class Twine; /// Triple - Helper class for working with target triples. /// @@ -26,17 +34,44 @@ namespace llvm { /// behavior for particular targets. This class isolates the mapping /// from the components of the target triple to well known IDs. /// -/// See autoconf/config.guess for a glimpse into what they look like -/// in practice. +/// At its core the Triple class is designed to be a wrapper for a triple +/// string; it does not normally change or normalize the triple string, instead +/// it provides additional APIs to parse normalized parts out of the triple. +/// +/// One curiosity this implies is that for some odd triples the results of, +/// e.g., getOSName() can be very different from the result of getOS(). For +/// example, for 'i386-mingw32', getOS() will return MinGW32, but since +/// getOSName() is purely based on the string structure that will return the +/// empty string. +/// +/// Clients should generally avoid using getOSName() and related APIs unless +/// they are familiar with the triple format (this is particularly true when +/// rewriting a triple). +/// +/// See autoconf/config.guess for a glimpse into what they look like in +/// practice. class Triple { public: enum ArchType { UnknownArch, - x86, // i?86 - ppc, // powerpc - ppc64, // powerpc64 - x86_64, // amd64, x86_64 + alpha, // Alpha: alpha + arm, // ARM; arm, armv.*, xscale + bfin, // Blackfin: bfin + cellspu, // CellSPU: spu, cellspu + mips, // MIPS: mips, mipsallegrex + mipsel, // MIPSEL: mipsel, mipsallegrexel, psp + msp430, // MSP430: msp430 + pic16, // PIC16: pic16 + ppc, // PPC: powerpc + ppc64, // PPC64: powerpc64 + sparc, // Sparc: sparc + systemz, // SystemZ: s390x + tce, // TCE (http://tce.cs.tut.fi/): tce + thumb, // Thumb: thumb, thumbv.* + x86, // X86: i[3-9]86 + x86_64, // X86-64: amd64, x86_64 + xcore, // XCore: xcore InvalidArch }; @@ -50,11 +85,17 @@ public: UnknownOS, AuroraUX, + Cygwin, Darwin, DragonFly, FreeBSD, Linux, - OpenBSD + MinGW32, + MinGW64, + NetBSD, + OpenBSD, + Solaris, + Win32 }; private: @@ -76,9 +117,9 @@ public: /// @name Constructors /// @{ - Triple() : Data(""), Arch(InvalidArch) {} - explicit Triple(const char *Str) : Data(Str), Arch(InvalidArch) {} - explicit Triple(const char *ArchStr, const char *VendorStr, const char *OSStr) + Triple() : Data(), Arch(InvalidArch) {} + explicit Triple(StringRef Str) : Data(Str), Arch(InvalidArch) {} + explicit Triple(StringRef ArchStr, StringRef VendorStr, StringRef OSStr) : Data(ArchStr), Arch(InvalidArch) { Data += '-'; Data += VendorStr; @@ -120,29 +161,41 @@ public: const std::string &getTriple() const { return Data; } - // FIXME: Invent a lightweight string representation for these to - // use. - /// getArchName - Get the architecture (first) component of the /// triple. - std::string getArchName() const; + StringRef getArchName() const; /// getVendorName - Get the vendor (second) component of the triple. - std::string getVendorName() const; + StringRef getVendorName() const; /// getOSName - Get the operating system (third) component of the /// triple. - std::string getOSName() const; + StringRef getOSName() const; /// getEnvironmentName - Get the optional environment (fourth) /// component of the triple, or "" if empty. - std::string getEnvironmentName() const; + StringRef getEnvironmentName() const; /// getOSAndEnvironmentName - Get the operating system and optional /// environment components as a single string (separated by a '-' /// if the environment component is present). - std::string getOSAndEnvironmentName() const; + StringRef getOSAndEnvironmentName() const; + + /// getDarwinNumber - Parse the 'darwin number' out of the specific target + /// triple. For example, if we have darwin8.5 return 8,5,0. If any entry is + /// not defined, return 0's. This requires that the triple have an OSType of + /// darwin before it is called. + void getDarwinNumber(unsigned &Maj, unsigned &Min, unsigned &Revision) const; + + /// getDarwinMajorNumber - Return just the major version number, this is + /// specialized because it is a common query. + unsigned getDarwinMajorNumber() const { + unsigned Maj, Min, Rev; + getDarwinNumber(Maj, Min, Rev); + return Maj; + } + /// @} /// @name Mutators /// @{ @@ -160,27 +213,27 @@ public: void setOS(OSType Kind); /// setTriple - Set all components to the new triple \arg Str. - void setTriple(const std::string &Str); + void setTriple(const Twine &Str); /// setArchName - Set the architecture (first) component of the /// triple by name. - void setArchName(const std::string &Str); + void setArchName(const StringRef &Str); /// setVendorName - Set the vendor (second) component of the triple /// by name. - void setVendorName(const std::string &Str); + void setVendorName(const StringRef &Str); /// setOSName - Set the operating system (third) component of the /// triple by name. - void setOSName(const std::string &Str); + void setOSName(const StringRef &Str); /// setEnvironmentName - Set the optional environment (fourth) /// component of the triple by name. - void setEnvironmentName(const std::string &Str); + void setEnvironmentName(const StringRef &Str); /// setOSAndEnvironmentName - Set the operating system and optional /// environment components with a single string. - void setOSAndEnvironmentName(const std::string &Str); + void setOSAndEnvironmentName(const StringRef &Str); /// @} /// @name Static helpers for IDs. @@ -190,6 +243,14 @@ public: /// architecture. static const char *getArchTypeName(ArchType Kind); + /// getArchTypePrefix - Get the "prefix" canonical name for the \arg Kind + /// architecture. This is the prefix used by the architecture specific + /// builtins, and is suitable for passing to \see + /// Intrinsic::getIntrinsicForGCCBuiltin(). + /// + /// \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. static const char *getVendorTypeName(VendorType Kind); @@ -198,6 +259,19 @@ public: static const char *getOSTypeName(OSType Kind); /// @} + /// @name Static helpers for converting alternate architecture names. + /// @{ + + /// getArchTypeForLLVMName - The canonical type for the given LLVM + /// architecture name (e.g., "x86"). + static ArchType getArchTypeForLLVMName(const 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(const StringRef &Str); + + /// @} }; } // End llvm namespace diff --git a/include/llvm/ADT/Twine.h b/include/llvm/ADT/Twine.h new file mode 100644 index 0000000..88fde0a --- /dev/null +++ b/include/llvm/ADT/Twine.h @@ -0,0 +1,422 @@ +//===-- Twine.h - Fast Temporary String Concatenation -----------*- 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_TWINE_H +#define LLVM_ADT_TWINE_H + +#include "llvm/ADT/StringRef.h" +#include "llvm/Support/DataTypes.h" +#include <cassert> +#include <string> + +namespace llvm { + template <typename T> + class SmallVectorImpl; + class StringRef; + class raw_ostream; + + /// Twine - A lightweight data structure for efficiently representing the + /// concatenation of temporary values as strings. + /// + /// A Twine is a kind of rope, it represents a concatenated string using a + /// binary-tree, where the string is the preorder of the nodes. Since the + /// Twine can be efficiently rendered into a buffer when its result is used, + /// it avoids the cost of generating temporary values for intermediate string + /// results -- particularly in cases when the Twine result is never + /// required. By explicitly tracking the type of leaf nodes, we can also avoid + /// the creation of temporary strings for conversions operations (such as + /// appending an integer to a string). + /// + /// A Twine is not intended for use directly and should not be stored, its + /// implementation relies on the ability to store pointers to temporary stack + /// objects which may be deallocated at the end of a statement. Twines should + /// only be used accepted as const references in arguments, when an API wishes + /// to accept possibly-concatenated strings. + /// + /// Twines support a special 'null' value, which always concatenates to form + /// 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 + /// + /// Given the nature of a Twine, it is not possible for the Twine's + /// concatenation method to construct interior nodes; the result must be + /// represented inside the returned value. For this reason a Twine object + /// actually holds two values, the left- and right-hand sides of a + /// concatenation. We also have nullary Twine objects, which are effectively + /// sentinel values that represent empty strings. + /// + /// Thus, a Twine can effectively have zero, one, or two children. The \see + /// isNullary(), \see isUnary(), and \see isBinary() predicates exist for + /// testing the number of children. + /// + /// We maintain a number of invariants on Twine objects (FIXME: Why): + /// - Nullary twines are always represented with their Kind on the left-hand + /// side, and the Empty kind on the right-hand side. + /// - Unary twines are always represented with the value on the left-hand + /// side, and the Empty kind on the right-hand side. + /// - If a Twine has another Twine as a child, that child should always be + /// binary (otherwise it could have been folded into the parent). + /// + /// These invariants are check by \see isValid(). + /// + /// \b Efficiency Considerations \n + /// + /// The Twine is designed to yield efficient and small code for common + /// situations. For this reason, the concat() method is inlined so that + /// concatenations of leaf nodes can be optimized into stores directly into a + /// single stack allocated object. + /// + /// In practice, not all compilers can be trusted to optimize concat() fully, + /// so we provide two additional methods (and accompanying operator+ + /// overloads) to guarantee that particularly important cases (cstring plus + /// StringRef) codegen as desired. + class Twine { + /// NodeKind - Represent the type of an argument. + enum NodeKind { + /// An empty string; the result of concatenating anything with it is also + /// empty. + NullKind, + + /// The empty string. + EmptyKind, + + /// A pointer to a Twine instance. + TwineKind, + + /// A pointer to a C string instance. + CStringKind, + + /// A pointer to an std::string instance. + StdStringKind, + + /// A pointer to a StringRef instance. + StringRefKind, + + /// A pointer to an unsigned int value, to render as an unsigned decimal + /// integer. + DecUIKind, + + /// A pointer to an int value, to render as a signed decimal integer. + DecIKind, + + /// A pointer to an unsigned long value, to render as an unsigned decimal + /// integer. + DecULKind, + + /// A pointer to a long value, to render as a signed decimal integer. + DecLKind, + + /// A pointer to an unsigned long long value, to render as an unsigned + /// decimal integer. + DecULLKind, + + /// A pointer to a long long value, to render as a signed decimal integer. + DecLLKind, + + /// A pointer to a uint64_t value, to render as an unsigned hexadecimal + /// integer. + UHexKind + }; + + private: + /// LHS - The prefix in the concatenation, which may be uninitialized for + /// Null or Empty kinds. + const void *LHS; + /// RHS - The suffix in the concatenation, which may be uninitialized for + /// Null or Empty kinds. + const void *RHS; + /// LHSKind - The NodeKind of the left hand side, \see getLHSKind(). + NodeKind LHSKind : 8; + /// RHSKind - The NodeKind of the left hand side, \see getLHSKind(). + NodeKind RHSKind : 8; + + private: + /// Construct a nullary twine; the kind must be NullKind or EmptyKind. + explicit Twine(NodeKind Kind) + : LHSKind(Kind), RHSKind(EmptyKind) { + assert(isNullary() && "Invalid kind!"); + } + + /// Construct a binary twine. + explicit Twine(const Twine &_LHS, const Twine &_RHS) + : LHS(&_LHS), RHS(&_RHS), LHSKind(TwineKind), RHSKind(TwineKind) { + assert(isValid() && "Invalid twine!"); + } + + /// Construct a twine from explicit values. + explicit Twine(const void *_LHS, NodeKind _LHSKind, + const void *_RHS, NodeKind _RHSKind) + : LHS(_LHS), RHS(_RHS), LHSKind(_LHSKind), RHSKind(_RHSKind) { + assert(isValid() && "Invalid twine!"); + } + + /// isNull - Check for the null twine. + bool isNull() const { + return getLHSKind() == NullKind; + } + + /// isEmpty - Check for the empty twine. + bool isEmpty() const { + return getLHSKind() == EmptyKind; + } + + /// isNullary - Check if this is a nullary twine (null or empty). + bool isNullary() const { + return isNull() || isEmpty(); + } + + /// isUnary - Check if this is a unary twine. + bool isUnary() const { + return getRHSKind() == EmptyKind && !isNullary(); + } + + /// isBinary - Check if this is a binary twine. + bool isBinary() const { + return getLHSKind() != NullKind && getRHSKind() != EmptyKind; + } + + /// isValid - Check if this is a valid twine (satisfying the invariants on + /// order and number of arguments). + bool isValid() const { + // Nullary twines always have Empty on the RHS. + if (isNullary() && getRHSKind() != EmptyKind) + return false; + + // Null should never appear on the RHS. + if (getRHSKind() == NullKind) + return false; + + // The RHS cannot be non-empty if the LHS is empty. + if (getRHSKind() != EmptyKind && getLHSKind() == EmptyKind) + return false; + + // A twine child should always be binary. + if (getLHSKind() == TwineKind && + !static_cast<const Twine*>(LHS)->isBinary()) + return false; + if (getRHSKind() == TwineKind && + !static_cast<const Twine*>(RHS)->isBinary()) + return false; + + return true; + } + + /// getLHSKind - Get the NodeKind of the left-hand side. + NodeKind getLHSKind() const { return LHSKind; } + + /// getRHSKind - Get the NodeKind of the left-hand side. + NodeKind getRHSKind() const { return RHSKind; } + + /// printOneChild - Print one child from a twine. + void printOneChild(raw_ostream &OS, const void *Ptr, NodeKind Kind) const; + + /// printOneChildRepr - Print the representation of one child from a twine. + void printOneChildRepr(raw_ostream &OS, const void *Ptr, + NodeKind Kind) const; + + public: + /// @name Constructors + /// @{ + + /// Construct from an empty string. + /*implicit*/ Twine() : LHSKind(EmptyKind), RHSKind(EmptyKind) { + assert(isValid() && "Invalid twine!"); + } + + /// Construct from a C string. + /// + /// We take care here to optimize "" into the empty twine -- this will be + /// optimized out for string constants. This allows Twine arguments have + /// default "" values, without introducing unnecessary string constants. + /*implicit*/ Twine(const char *Str) + : RHSKind(EmptyKind) { + if (Str[0] != '\0') { + LHS = Str; + LHSKind = CStringKind; + } else + LHSKind = EmptyKind; + + assert(isValid() && "Invalid twine!"); + } + + /// Construct from an std::string. + /*implicit*/ Twine(const std::string &Str) + : LHS(&Str), LHSKind(StdStringKind), RHSKind(EmptyKind) { + assert(isValid() && "Invalid twine!"); + } + + /// Construct from a StringRef. + /*implicit*/ Twine(const StringRef &Str) + : LHS(&Str), LHSKind(StringRefKind), RHSKind(EmptyKind) { + assert(isValid() && "Invalid twine!"); + } + + /// Construct a twine to print \arg Val as an unsigned decimal integer. + explicit Twine(const unsigned int &Val) + : LHS(&Val), LHSKind(DecUIKind), RHSKind(EmptyKind) { + } + + /// Construct a twine to print \arg Val as a signed decimal integer. + explicit Twine(const int &Val) + : LHS(&Val), LHSKind(DecIKind), RHSKind(EmptyKind) { + } + + /// Construct a twine to print \arg Val as an unsigned decimal integer. + explicit Twine(const unsigned long &Val) + : LHS(&Val), LHSKind(DecULKind), RHSKind(EmptyKind) { + } + + /// Construct a twine to print \arg Val as a signed decimal integer. + explicit Twine(const long &Val) + : LHS(&Val), LHSKind(DecLKind), RHSKind(EmptyKind) { + } + + /// Construct a twine to print \arg Val as an unsigned decimal integer. + explicit Twine(const unsigned long long &Val) + : LHS(&Val), LHSKind(DecULLKind), RHSKind(EmptyKind) { + } + + /// Construct a twine to print \arg Val as a signed decimal integer. + explicit Twine(const long long &Val) + : LHS(&Val), LHSKind(DecLLKind), RHSKind(EmptyKind) { + } + + // FIXME: Unfortunately, to make sure this is as efficient as possible we + // need extra binary constructors from particular types. We can't rely on + // the compiler to be smart enough to fold operator+()/concat() down to the + // right thing. Yet. + + /// Construct as the concatenation of a C string and a StringRef. + /*implicit*/ Twine(const char *_LHS, const StringRef &_RHS) + : LHS(_LHS), RHS(&_RHS), LHSKind(CStringKind), RHSKind(StringRefKind) { + assert(isValid() && "Invalid twine!"); + } + + /// Construct as the concatenation of a StringRef and a C string. + /*implicit*/ Twine(const StringRef &_LHS, const char *_RHS) + : LHS(&_LHS), RHS(_RHS), LHSKind(StringRefKind), RHSKind(CStringKind) { + assert(isValid() && "Invalid twine!"); + } + + /// Create a 'null' string, which is an empty string that always + /// concatenates to form another empty string. + static Twine createNull() { + return Twine(NullKind); + } + + /// @} + /// @name Numeric Conversions + /// @{ + + // Construct a twine to print \arg Val as an unsigned hexadecimal integer. + static Twine utohexstr(const uint64_t &Val) { + return Twine(&Val, UHexKind, 0, EmptyKind); + } + + /// @} + /// @name Predicate Operations + /// @{ + + /// isTriviallyEmpty - Check if this twine is trivially empty; a false + /// return value does not necessarily mean the twine is empty. + bool isTriviallyEmpty() const { + return isNullary(); + } + + /// @} + /// @name String Operations + /// @{ + + Twine concat(const Twine &Suffix) const; + + /// @} + /// @name Output & Conversion. + /// @{ + + /// str - Return the twine contents as a std::string. + std::string str() const; + + /// toVector - Write the concatenated string into the given SmallString or + /// SmallVector. + void toVector(SmallVectorImpl<char> &Out) const; + + /// print - Write the concatenated string represented by this twine to the + /// stream \arg OS. + void print(raw_ostream &OS) const; + + /// dump - 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. + void printRepr(raw_ostream &OS) const; + + /// dumpRepr - Dump the representation of this twine to stderr. + void dumpRepr() const; + + /// @} + }; + + /// @name Twine Inline Implementations + /// @{ + + inline Twine Twine::concat(const Twine &Suffix) const { + // Concatenation with null is null. + if (isNull() || Suffix.isNull()) + return Twine(NullKind); + + // Concatenation with empty yields the other side. + if (isEmpty()) + return Suffix; + if (Suffix.isEmpty()) + return *this; + + // Otherwise we need to create a new node, taking care to fold in unary + // twines. + const void *NewLHS = this, *NewRHS = &Suffix; + NodeKind NewLHSKind = TwineKind, NewRHSKind = TwineKind; + if (isUnary()) { + NewLHS = LHS; + NewLHSKind = getLHSKind(); + } + if (Suffix.isUnary()) { + NewRHS = Suffix.LHS; + NewRHSKind = Suffix.getLHSKind(); + } + + return Twine(NewLHS, NewLHSKind, NewRHS, NewRHSKind); + } + + inline Twine operator+(const Twine &LHS, const Twine &RHS) { + return LHS.concat(RHS); + } + + /// Additional overload to guarantee simplified codegen; this is equivalent to + /// concat(). + + inline Twine operator+(const char *LHS, const StringRef &RHS) { + return Twine(LHS, RHS); + } + + /// Additional overload to guarantee simplified codegen; this is equivalent to + /// concat(). + + inline Twine operator+(const StringRef &LHS, const char *RHS) { + return Twine(LHS, RHS); + } + + inline raw_ostream &operator<<(raw_ostream &OS, const Twine &RHS) { + RHS.print(OS); + return OS; + } + + /// @} +} + +#endif diff --git a/include/llvm/ADT/ilist.h b/include/llvm/ADT/ilist.h index b95e3e0..b3824a2 100644 --- a/include/llvm/ADT/ilist.h +++ b/include/llvm/ADT/ilist.h @@ -38,8 +38,8 @@ #ifndef LLVM_ADT_ILIST_H #define LLVM_ADT_ILIST_H -#include "llvm/ADT/iterator.h" #include <cassert> +#include <iterator> namespace llvm { @@ -121,15 +121,15 @@ struct ilist_node_traits { /// for all common operations. /// template<typename NodeTy> -struct ilist_default_traits : ilist_nextprev_traits<NodeTy>, - ilist_sentinel_traits<NodeTy>, - ilist_node_traits<NodeTy> { +struct ilist_default_traits : public ilist_nextprev_traits<NodeTy>, + public ilist_sentinel_traits<NodeTy>, + public ilist_node_traits<NodeTy> { }; // Template traits for intrusive list. By specializing this template class, you // can change what next/prev fields are used to store the links... template<typename NodeTy> -struct ilist_traits : ilist_default_traits<NodeTy> {}; +struct ilist_traits : public ilist_default_traits<NodeTy> {}; // Const traits are the same as nonconst traits... template<typename Ty> @@ -140,11 +140,12 @@ struct ilist_traits<const Ty> : public ilist_traits<Ty> {}; // template<typename NodeTy> class ilist_iterator - : public bidirectional_iterator<NodeTy, ptrdiff_t> { + : public std::iterator<std::bidirectional_iterator_tag, NodeTy, ptrdiff_t> { public: typedef ilist_traits<NodeTy> Traits; - typedef bidirectional_iterator<NodeTy, ptrdiff_t> super; + typedef std::iterator<std::bidirectional_iterator_tag, + NodeTy, ptrdiff_t> super; typedef typename super::value_type value_type; typedef typename super::difference_type difference_type; @@ -189,12 +190,10 @@ public: // Accessors... operator pointer() const { - assert(Traits::getNext(NodePtr) != 0 && "Dereferencing end()!"); return NodePtr; } reference operator*() const { - assert(Traits::getNext(NodePtr) != 0 && "Dereferencing end()!"); return *NodePtr; } pointer operator->() const { return &operator*(); } @@ -215,7 +214,6 @@ public: } ilist_iterator &operator++() { // preincrement - Advance NodePtr = Traits::getNext(NodePtr); - assert(NodePtr && "++'d off the end of an ilist!"); return *this; } ilist_iterator operator--(int) { // postdecrement operators... @@ -323,13 +321,13 @@ class iplist : public Traits { /// CreateLazySentinel - This method verifies whether the sentinel for the /// list has been created and lazily makes it if not. void CreateLazySentinel() const { - this->Traits::ensureHead(Head); + this->ensureHead(Head); } static bool op_less(NodeTy &L, NodeTy &R) { return L < R; } static bool op_equal(NodeTy &L, NodeTy &R) { return L == R; } - // No fundamental reason why iplist can't by copyable, but the default + // 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 @@ -347,7 +345,7 @@ public: typedef std::reverse_iterator<const_iterator> const_reverse_iterator; typedef std::reverse_iterator<iterator> reverse_iterator; - iplist() : Head(this->Traits::provideInitialHead()) {} + iplist() : Head(this->provideInitialHead()) {} ~iplist() { if (!Head) return; clear(); diff --git a/include/llvm/ADT/ilist_node.h b/include/llvm/ADT/ilist_node.h index dae7475..da25f95 100644 --- a/include/llvm/ADT/ilist_node.h +++ b/include/llvm/ADT/ilist_node.h @@ -18,28 +18,37 @@ namespace llvm { template<typename NodeTy> -struct ilist_nextprev_traits; +struct ilist_traits; +/// ilist_half_node - Base class that provides prev services for sentinels. +/// template<typename NodeTy> -struct ilist_traits; +class ilist_half_node { + friend struct ilist_traits<NodeTy>; + NodeTy *Prev; +protected: + NodeTy *getPrev() { return Prev; } + const NodeTy *getPrev() const { return Prev; } + void setPrev(NodeTy *P) { Prev = P; } + ilist_half_node() : Prev(0) {} +}; + +template<typename NodeTy> +struct ilist_nextprev_traits; /// ilist_node - Base class that provides next/prev services for nodes /// that use ilist_nextprev_traits or ilist_default_traits. /// template<typename NodeTy> -class ilist_node { -private: +class ilist_node : private ilist_half_node<NodeTy> { friend struct ilist_nextprev_traits<NodeTy>; friend struct ilist_traits<NodeTy>; - NodeTy *Prev, *Next; - NodeTy *getPrev() { return Prev; } + NodeTy *Next; NodeTy *getNext() { return Next; } - const NodeTy *getPrev() const { return Prev; } const NodeTy *getNext() const { return Next; } - void setPrev(NodeTy *N) { Prev = N; } void setNext(NodeTy *N) { Next = N; } protected: - ilist_node() : Prev(0), Next(0) {} + ilist_node() : Next(0) {} }; } // End llvm namespace |
