Vendor import of llvm trunk r130700:

http://llvm.org/svn/llvm-project/llvm/trunk@130700

18 files changed, 335 insertions, 131 deletions

diff --git a/include/llvm/ADT/APFloat.h b/include/llvm/ADT/APFloat.h
index ca4138b..21b8c86 100644
--- a/include/llvm/ADT/APFloat.h
+++ b/include/llvm/ADT/APFloat.h
@@ -353,6 +353,10 @@ namespace llvm {
                   unsigned FormatPrecision = 0,
                   unsigned FormatMaxPadding = 3) const;
 
+    /// getExactInverse - If this value has an exact multiplicative inverse,
+    /// store it in inv and return true.
+    bool getExactInverse(APFloat *inv) const;
+
   private:
 
     /* Trivial queries.  */
diff --git a/include/llvm/ADT/APInt.h b/include/llvm/ADT/APInt.h
index d1fd3e5..2feef07 100644
--- a/include/llvm/ADT/APInt.h
+++ b/include/llvm/ADT/APInt.h
@@ -818,6 +818,7 @@ public:
   APInt usub_ov(const APInt &RHS, bool &Overflow) const;
   APInt sdiv_ov(const APInt &RHS, bool &Overflow) const;
   APInt smul_ov(const APInt &RHS, bool &Overflow) const;
+  APInt umul_ov(const APInt &RHS, bool &Overflow) const;
   APInt sshl_ov(unsigned Amt, bool &Overflow) const;
 
   /// @returns the bit value at bitPosition
@@ -1372,7 +1373,7 @@ public:
 
   /// Calculate the magic number for unsigned division by a constant.
   struct mu;
-  mu magicu() const;
+  mu magicu(unsigned LeadingZeros = 0) const;
 
   /// @}
   /// @name Building-block Operations for APInt and APFloat
diff --git a/include/llvm/ADT/ArrayRef.h b/include/llvm/ADT/ArrayRef.h
index d3ea9c0..97e42cb 100644
--- a/include/llvm/ADT/ArrayRef.h
+++ b/include/llvm/ADT/ArrayRef.h
@@ -22,8 +22,8 @@ namespace llvm {
   ///
   /// This class does not own the underlying data, it is expected to be used in
   /// situations where the data resides in some other buffer, whose lifetime
-  /// extends past that of the StringRef. For this reason, it is not in general
-  /// safe to store a ArrayRef.
+  /// extends past that of the ArrayRef. For this reason, it is not in general
+  /// safe to store an ArrayRef.
   ///
   /// This is intended to be trivially copyable, so it should be passed by
   /// value.
@@ -79,6 +79,8 @@ namespace llvm {
     /// empty - Check if the array is empty.
     bool empty() const { return Length == 0; }
     
+    const T *data() const { return Data; }
+    
     /// size - Get the array size.
     size_t size() const { return Length; }
     
@@ -94,10 +96,22 @@ namespace llvm {
       return Data[Length-1];
     }
     
+    /// slice(n) - Chop off the first N elements of the array.
+    ArrayRef<T> slice(unsigned N) {
+      assert(N <= size() && "Invalid specifier");
+      return ArrayRef<T>(data()+N, size()-N);
+    }
+
+    /// slice(n, m) - Chop off the first N elements of the array, and keep M
+    /// elements in the array.
+    ArrayRef<T> slice(unsigned N, unsigned M) {
+      assert(N+M <= size() && "Invalid specifier");
+      return ArrayRef<T>(data()+N, M);
+    }
+    
     /// @}
     /// @name Operator Overloads
     /// @{
-    
     const T &operator[](size_t Index) const {
       assert(Index < Length && "Invalid index!");
       return Data[Index];
@@ -106,7 +120,6 @@ namespace llvm {
     /// @}
     /// @name Expensive Operations
     /// @{
-    
     std::vector<T> vec() const {
       return std::vector<T>(Data, Data+Length);
     }
diff --git a/include/llvm/ADT/DenseMap.h b/include/llvm/ADT/DenseMap.h
index 61d6ae7..0f1cfeb 100644
--- a/include/llvm/ADT/DenseMap.h
+++ b/include/llvm/ADT/DenseMap.h
@@ -53,13 +53,13 @@ public:
     CopyFrom(other);
   }
 
-  explicit DenseMap(unsigned NumInitBuckets = 64) {
+  explicit DenseMap(unsigned NumInitBuckets = 0) {
     init(NumInitBuckets);
   }
 
   template<typename InputIt>
   DenseMap(const InputIt &I, const InputIt &E) {
-    init(64);
+    init(NextPowerOf2(std::distance(I, E)));
     insert(I, E);
   }
   
@@ -72,7 +72,8 @@ public:
       P->first.~KeyT();
     }
 #ifndef NDEBUG
-    memset(Buckets, 0x5a, sizeof(BucketT)*NumBuckets);
+    if (NumBuckets)
+      memset((void*)Buckets, 0x5a, sizeof(BucketT)*NumBuckets);
 #endif
     operator delete(Buckets);
   }
@@ -98,7 +99,10 @@ public:
   unsigned size() const { return NumEntries; }
 
   /// Grow the densemap so that it has at least Size buckets. Does not shrink
-  void resize(size_t Size) { grow(Size); }
+  void resize(size_t Size) {
+    if (Size > NumBuckets)
+      grow(Size);
+  }
 
   void clear() {
     if (NumEntries == 0 && NumTombstones == 0) return;
@@ -248,23 +252,29 @@ private:
 
     if (NumBuckets) {
 #ifndef NDEBUG
-      memset(Buckets, 0x5a, sizeof(BucketT)*NumBuckets);
+      memset((void*)Buckets, 0x5a, sizeof(BucketT)*NumBuckets);
 #endif
       operator delete(Buckets);
     }
-    Buckets = static_cast<BucketT*>(operator new(sizeof(BucketT) *
-                                                 other.NumBuckets));
+
+    NumBuckets = other.NumBuckets;
+
+    if (NumBuckets == 0) {
+      Buckets = 0;
+      return;
+    }
+
+    Buckets = static_cast<BucketT*>(operator new(sizeof(BucketT) * NumBuckets));
 
     if (isPodLike<KeyInfoT>::value && isPodLike<ValueInfoT>::value)
-      memcpy(Buckets, other.Buckets, other.NumBuckets * sizeof(BucketT));
+      memcpy(Buckets, other.Buckets, NumBuckets * sizeof(BucketT));
     else
-      for (size_t i = 0; i < other.NumBuckets; ++i) {
+      for (size_t i = 0; i < NumBuckets; ++i) {
         new (&Buckets[i].first) KeyT(other.Buckets[i].first);
         if (!KeyInfoT::isEqual(Buckets[i].first, getEmptyKey()) &&
             !KeyInfoT::isEqual(Buckets[i].first, getTombstoneKey()))
           new (&Buckets[i].second) ValueT(other.Buckets[i].second);
       }
-    NumBuckets = other.NumBuckets;
   }
 
   BucketT *InsertIntoBucket(const KeyT &Key, const ValueT &Value,
@@ -279,11 +289,14 @@ private:
     // table completely filled with tombstones, no lookup would ever succeed,
     // causing infinite loops in lookup.
     ++NumEntries;
-    if (NumEntries*4 >= NumBuckets*3 ||
-        NumBuckets-(NumEntries+NumTombstones) < NumBuckets/8) {
+    if (NumEntries*4 >= NumBuckets*3) {
       this->grow(NumBuckets * 2);
       LookupBucketFor(Key, TheBucket);
     }
+    if (NumBuckets-(NumEntries+NumTombstones) < NumBuckets/8) {
+      this->grow(NumBuckets);
+      LookupBucketFor(Key, TheBucket);
+    }
 
     // If we are writing over a tombstone, remember this.
     if (!KeyInfoT::isEqual(TheBucket->first, getEmptyKey()))
@@ -313,6 +326,11 @@ private:
     unsigned ProbeAmt = 1;
     BucketT *BucketsPtr = Buckets;
 
+    if (NumBuckets == 0) {
+      FoundBucket = 0;
+      return false;
+    }
+
     // FoundTombstone - Keep track of whether we find a tombstone while probing.
     BucketT *FoundTombstone = 0;
     const KeyT EmptyKey = getEmptyKey();
@@ -354,6 +372,12 @@ private:
     NumEntries = 0;
     NumTombstones = 0;
     NumBuckets = InitBuckets;
+
+    if (InitBuckets == 0) {
+      Buckets = 0;
+      return;
+    }
+
     assert(InitBuckets && (InitBuckets & (InitBuckets-1)) == 0 &&
            "# initial buckets must be a power of two!");
     Buckets = static_cast<BucketT*>(operator new(sizeof(BucketT)*InitBuckets));
@@ -367,6 +391,9 @@ private:
     unsigned OldNumBuckets = NumBuckets;
     BucketT *OldBuckets = Buckets;
 
+    if (NumBuckets < 64)
+      NumBuckets = 64;
+
     // Double the number of buckets.
     while (NumBuckets < AtLeast)
       NumBuckets <<= 1;
@@ -398,7 +425,8 @@ private:
     }
 
 #ifndef NDEBUG
-    memset(OldBuckets, 0x5a, sizeof(BucketT)*OldNumBuckets);
+    if (OldNumBuckets)
+      memset((void*)OldBuckets, 0x5a, sizeof(BucketT)*OldNumBuckets);
 #endif
     // Free the old table.
     operator delete(OldBuckets);
@@ -431,13 +459,22 @@ private:
     }
 
 #ifndef NDEBUG
-    memset(OldBuckets, 0x5a, sizeof(BucketT)*OldNumBuckets);
+    memset((void*)OldBuckets, 0x5a, sizeof(BucketT)*OldNumBuckets);
 #endif
     // Free the old table.
     operator delete(OldBuckets);
 
     NumEntries = 0;
   }
+  
+public:
+  /// Return the approximate size (in bytes) of the actual map.
+  /// This is just the raw memory used by DenseMap.
+  /// If entries are pointers to objects, the size of the referenced objects
+  /// are not included.
+  size_t getMemorySize() const {
+    return NumBuckets * sizeof(BucketT);
+  }
 };
 
 template<typename KeyT, typename ValueT,
diff --git a/include/llvm/ADT/DenseMapInfo.h b/include/llvm/ADT/DenseMapInfo.h
index 25e341b..744b6f4 100644
--- a/include/llvm/ADT/DenseMapInfo.h
+++ b/include/llvm/ADT/DenseMapInfo.h
@@ -157,7 +157,10 @@ struct DenseMapInfo<std::pair<T, U> > {
     key ^= (key >> 31);
     return (unsigned)key;
   }
-  static bool isEqual(const Pair& LHS, const Pair& RHS) { return LHS == RHS; }
+  static bool isEqual(const Pair &LHS, const Pair &RHS) {
+    return FirstInfo::isEqual(LHS.first, RHS.first) && 
+           SecondInfo::isEqual(LHS.second, RHS.second);
+  }
 };
 
 } // end namespace llvm
diff --git a/include/llvm/ADT/DepthFirstIterator.h b/include/llvm/ADT/DepthFirstIterator.h
index b9e5cbd..dd13a2c 100644
--- a/include/llvm/ADT/DepthFirstIterator.h
+++ b/include/llvm/ADT/DepthFirstIterator.h
@@ -143,8 +143,7 @@ public:
   static inline _Self end(const GraphT& G, SetType &S) { return _Self(S); }
 
   inline bool operator==(const _Self& x) const {
-    return VisitStack.size() == x.VisitStack.size() &&
-           VisitStack == x.VisitStack;
+    return VisitStack == x.VisitStack;
   }
   inline bool operator!=(const _Self& x) const { return !operator==(x); }
 
diff --git a/include/llvm/ADT/FoldingSet.h b/include/llvm/ADT/FoldingSet.h
index 879dbd0..52e0434 100644
--- a/include/llvm/ADT/FoldingSet.h
+++ b/include/llvm/ADT/FoldingSet.h
@@ -209,10 +209,10 @@ template<typename T> struct FoldingSetTrait;
 /// for FoldingSetTrait implementations.
 ///
 template<typename T> struct DefaultFoldingSetTrait {
-  static void Profile(const T& X, FoldingSetNodeID& ID) {
+  static void Profile(const T &X, FoldingSetNodeID &ID) {
     X.Profile(ID);
   }
-  static void Profile(T& X, FoldingSetNodeID& ID) {
+  static void Profile(T &X, FoldingSetNodeID &ID) {
     X.Profile(ID);
   }
 
@@ -267,7 +267,7 @@ template<typename T, typename Ctx> struct ContextualFoldingSetTrait
 /// is often much larger than necessary, and the possibility of heap
 /// allocation means it requires a non-trivial destructor call.
 class FoldingSetNodeIDRef {
-  const unsigned* Data;
+  const unsigned *Data;
   size_t Size;
 public:
   FoldingSetNodeIDRef() : Data(0), Size(0) {}
@@ -310,9 +310,10 @@ public:
   void AddInteger(unsigned long long I);
   void AddBoolean(bool B) { AddInteger(B ? 1U : 0U); }
   void AddString(StringRef String);
+  void AddNodeID(const FoldingSetNodeID &ID);
 
   template <typename T>
-  inline void Add(const T& x) { FoldingSetTrait<T>::Profile(x, *this); }
+  inline void Add(const T &x) { FoldingSetTrait<T>::Profile(x, *this); }
 
   /// clear - Clear the accumulated profile, allowing this FoldingSetNodeID
   /// object to be used to compute a new profile.
@@ -548,7 +549,7 @@ public:
     return static_cast<T*>(NodePtr);
   }
 
-  inline FoldingSetIterator& operator++() {          // Preincrement
+  inline FoldingSetIterator &operator++() {          // Preincrement
     advance();
     return *this;
   }
@@ -596,10 +597,10 @@ public:
   FoldingSetBucketIterator(void **Bucket, bool) :
     FoldingSetBucketIteratorImpl(Bucket, true) {}
 
-  T& operator*() const { return *static_cast<T*>(Ptr); }
-  T* operator->() const { return static_cast<T*>(Ptr); }
+  T &operator*() const { return *static_cast<T*>(Ptr); }
+  T *operator->() const { return static_cast<T*>(Ptr); }
 
-  inline FoldingSetBucketIterator& operator++() { // Preincrement
+  inline FoldingSetBucketIterator &operator++() { // Preincrement
     advance();
     return *this;
   }
@@ -615,36 +616,36 @@ template <typename T>
 class FoldingSetNodeWrapper : public FoldingSetNode {
   T data;
 public:
-  explicit FoldingSetNodeWrapper(const T& x) : data(x) {}
+  explicit FoldingSetNodeWrapper(const T &x) : data(x) {}
   virtual ~FoldingSetNodeWrapper() {}
 
   template<typename A1>
-  explicit FoldingSetNodeWrapper(const A1& a1)
+  explicit FoldingSetNodeWrapper(const A1 &a1)
     : data(a1) {}
 
   template <typename A1, typename A2>
-  explicit FoldingSetNodeWrapper(const A1& a1, const A2& a2)
+  explicit FoldingSetNodeWrapper(const A1 &a1, const A2 &a2)
     : data(a1,a2) {}
 
   template <typename A1, typename A2, typename A3>
-  explicit FoldingSetNodeWrapper(const A1& a1, const A2& a2, const A3& a3)
+  explicit FoldingSetNodeWrapper(const A1 &a1, const A2 &a2, const A3 &a3)
     : data(a1,a2,a3) {}
 
   template <typename A1, typename A2, typename A3, typename A4>
-  explicit FoldingSetNodeWrapper(const A1& a1, const A2& a2, const A3& a3,
-                                 const A4& a4)
+  explicit FoldingSetNodeWrapper(const A1 &a1, const A2 &a2, const A3 &a3,
+                                 const A4 &a4)
     : data(a1,a2,a3,a4) {}
 
   template <typename A1, typename A2, typename A3, typename A4, typename A5>
-  explicit FoldingSetNodeWrapper(const A1& a1, const A2& a2, const A3& a3,
-                                 const A4& a4, const A5& a5)
+  explicit FoldingSetNodeWrapper(const A1 &a1, const A2 &a2, const A3 &a3,
+                                 const A4 &a4, const A5 &a5)
   : data(a1,a2,a3,a4,a5) {}
 
 
-  void Profile(FoldingSetNodeID& ID) { FoldingSetTrait<T>::Profile(data, ID); }
+  void Profile(FoldingSetNodeID &ID) { FoldingSetTrait<T>::Profile(data, ID); }
 
-  T& getValue() { return data; }
-  const T& getValue() const { return data; }
+  T &getValue() { return data; }
+  const T &getValue() const { return data; }
 
   operator T&() { return data; }
   operator const T&() const { return data; }
@@ -661,20 +662,22 @@ class FastFoldingSetNode : public FoldingSetNode {
 protected:
   explicit FastFoldingSetNode(const FoldingSetNodeID &ID) : FastID(ID) {}
 public:
-  void Profile(FoldingSetNodeID& ID) const { ID = FastID; }
+  void Profile(FoldingSetNodeID &ID) const { 
+    ID.AddNodeID(FastID); 
+  }
 };
 
 //===----------------------------------------------------------------------===//
 // Partial specializations of FoldingSetTrait.
 
 template<typename T> struct FoldingSetTrait<T*> {
-  static inline void Profile(const T* X, FoldingSetNodeID& ID) {
+  static inline void Profile(const T *X, FoldingSetNodeID &ID) {
     ID.AddPointer(X);
   }
 };
 
 template<typename T> struct FoldingSetTrait<const T*> {
-  static inline void Profile(const T* X, FoldingSetNodeID& ID) {
+  static inline void Profile(const T *X, FoldingSetNodeID &ID) {
     ID.AddPointer(X);
   }
 };
diff --git a/include/llvm/ADT/ImmutableIntervalMap.h b/include/llvm/ADT/ImmutableIntervalMap.h
index 0d8fcf3..fa7ccb9 100644
--- a/include/llvm/ADT/ImmutableIntervalMap.h
+++ b/include/llvm/ADT/ImmutableIntervalMap.h
@@ -10,6 +10,10 @@
 // This file defines the ImmutableIntervalMap class.
 //
 //===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ADT_IMMUTABLE_INTERVAL_MAP_H
+#define LLVM_ADT_IMMUTABLE_INTERVAL_MAP_H
+
 #include "llvm/ADT/ImmutableMap.h"
 
 namespace llvm {
@@ -240,3 +244,5 @@ private:
 };
 
 } // end namespace llvm
+
+#endif
diff --git a/include/llvm/ADT/IntervalMap.h b/include/llvm/ADT/IntervalMap.h
index 79f24d3..f28ebf3 100644
--- a/include/llvm/ADT/IntervalMap.h
+++ b/include/llvm/ADT/IntervalMap.h
@@ -1328,6 +1328,10 @@ public:
   /// const_iterator - Create an iterator that isn't pointing anywhere.
   const_iterator() : map(0) {}
 
+  /// setMap - Change the map iterated over. This call must be followed by a
+  /// call to goToBegin(), goToEnd(), or find()
+  void setMap(const IntervalMap &m) { map = const_cast<IntervalMap*>(&m); }
+
   /// valid - Return true if the current position is valid, false for end().
   bool valid() const { return path.valid(); }
 
diff --git a/include/llvm/ADT/IntrusiveRefCntPtr.h b/include/llvm/ADT/IntrusiveRefCntPtr.h
index 37d4ac9..2f6fd2b 100644
--- a/include/llvm/ADT/IntrusiveRefCntPtr.h
+++ b/include/llvm/ADT/IntrusiveRefCntPtr.h
@@ -42,18 +42,16 @@ namespace llvm {
 //===----------------------------------------------------------------------===//
   template <class Derived>
   class RefCountedBase {
-    unsigned ref_cnt;
+    mutable unsigned ref_cnt;
 
-  protected:
+  public:
     RefCountedBase() : ref_cnt(0) {}
 
-    void Retain() { ++ref_cnt; }
-    void Release() {
+    void Retain() const { ++ref_cnt; }
+    void Release() const {
       assert (ref_cnt > 0 && "Reference count is already zero.");
-      if (--ref_cnt == 0) delete static_cast<Derived*>(this);
+      if (--ref_cnt == 0) delete static_cast<const Derived*>(this);
     }
-
-    friend class IntrusiveRefCntPtr<Derived>;
   };
 
 //===----------------------------------------------------------------------===//
@@ -64,21 +62,21 @@ namespace llvm {
 ///  inherit from RefCountedBaseVPTR can't be allocated on stack -
 ///  attempting to do this will produce a compile error.
 //===----------------------------------------------------------------------===//
-  template <class Derived>
   class RefCountedBaseVPTR {
-    unsigned ref_cnt;
+    mutable unsigned ref_cnt;
 
   protected:
     RefCountedBaseVPTR() : ref_cnt(0) {}
     virtual ~RefCountedBaseVPTR() {}
 
-    void Retain() { ++ref_cnt; }
-    void Release() {
+    void Retain() const { ++ref_cnt; }
+    void Release() const {
       assert (ref_cnt > 0 && "Reference count is already zero.");
       if (--ref_cnt == 0) delete this;
     }
 
-    friend class IntrusiveRefCntPtr<Derived>;
+    template <typename T>
+    friend class IntrusiveRefCntPtr;
   };
 
 //===----------------------------------------------------------------------===//
@@ -155,6 +153,10 @@ namespace llvm {
       other.Obj = Obj;
       Obj = tmp;
     }
+    
+    void resetWithoutRelease() {
+      Obj = 0;
+    }
 
   private:
     void retain() { if (Obj) Obj->Retain(); }
diff --git a/include/llvm/ADT/PointerUnion.h b/include/llvm/ADT/PointerUnion.h
index 61de042..13b98ce 100644
--- a/include/llvm/ADT/PointerUnion.h
+++ b/include/llvm/ADT/PointerUnion.h
@@ -19,16 +19,33 @@
 
 namespace llvm {
 
-  /// getPointerUnionTypeNum - If the argument has type PT1* or PT2* return
-  /// false or true respectively.
-  template <typename PT1, typename PT2>
-  static inline int getPointerUnionTypeNum(PT1 *P) { return 0; }
-  template <typename PT1, typename PT2>
-  static inline int getPointerUnionTypeNum(PT2 *P) { return 1; }
-  template <typename PT1, typename PT2>
-  static inline int getPointerUnionTypeNum(...) { return -1; }
-  
-  
+  template <typename T>
+  struct PointerUnionTypeSelectorReturn {
+    typedef T Return;
+  };
+
+  /// \brief Get a type based on whether two types are the same or not. For:
+  /// @code
+  /// typedef typename PointerUnionTypeSelector<T1, T2, EQ, NE>::Return Ret;
+  /// @endcode
+  /// Ret will be EQ type if T1 is same as T2 or NE type otherwise.
+  template <typename T1, typename T2, typename RET_EQ, typename RET_NE>
+  struct PointerUnionTypeSelector {
+    typedef typename PointerUnionTypeSelectorReturn<RET_NE>::Return Return;
+  };
+
+  template <typename T, typename RET_EQ, typename RET_NE>
+  struct PointerUnionTypeSelector<T, T, RET_EQ, RET_NE> {
+    typedef typename PointerUnionTypeSelectorReturn<RET_EQ>::Return Return;
+  };
+
+  template <typename T1, typename T2, typename RET_EQ, typename RET_NE>
+  struct PointerUnionTypeSelectorReturn<
+                            PointerUnionTypeSelector<T1, T2, RET_EQ, RET_NE> > {
+    typedef typename PointerUnionTypeSelector<T1, T2, RET_EQ, RET_NE>::Return
+        Return;
+  };
+
   /// Provide PointerLikeTypeTraits for void* that is used by PointerUnion
   /// for the two template arguments.
   template <typename PT1, typename PT2>
@@ -65,6 +82,16 @@ namespace llvm {
                            PointerUnionUIntTraits<PT1,PT2> > ValTy;
   private:
     ValTy Val;
+
+    struct IsPT1 {
+      static const int Num = 0;
+    };
+    struct IsPT2 {
+      static const int Num = 1;
+    };
+    template <typename T>
+    struct UNION_DOESNT_CONTAIN_TYPE { };
+
   public:
     PointerUnion() {}
     
@@ -87,8 +114,11 @@ namespace llvm {
     /// is<T>() return true if the Union currently holds the type matching T.
     template<typename T>
     int is() const {
-      int TyNo = ::llvm::getPointerUnionTypeNum<PT1, PT2>((T*)0);
-      assert(TyNo != -1 && "Type query could never succeed on PointerUnion!");
+      typedef typename
+        ::llvm::PointerUnionTypeSelector<PT1, T, IsPT1,
+          ::llvm::PointerUnionTypeSelector<PT2, T, IsPT2,
+                                    UNION_DOESNT_CONTAIN_TYPE<T> > >::Return Ty;
+      int TyNo = Ty::Num;
       return static_cast<int>(Val.getInt()) == TyNo;
     }
     
@@ -175,6 +205,34 @@ namespace llvm {
     typedef PointerUnion<InnerUnion, PT3> ValTy;
   private:
     ValTy Val;
+
+    struct IsInnerUnion {
+      ValTy Val;
+      IsInnerUnion(ValTy val) : Val(val) { }
+      template<typename T>
+      int is() const {
+        return Val.template is<InnerUnion>() && 
+               Val.template get<InnerUnion>().template is<T>();
+      }
+      template<typename T>
+      T get() const {
+        return Val.template get<InnerUnion>().template get<T>();
+      }
+    };
+
+    struct IsPT3 {
+      ValTy Val;
+      IsPT3(ValTy val) : Val(val) { }
+      template<typename T>
+      int is() const {
+        return Val.template is<T>();
+      }
+      template<typename T>
+      T get() const {
+        return Val.template get<T>();
+      }
+    };
+
   public:
     PointerUnion3() {}
     
@@ -196,11 +254,12 @@ namespace llvm {
     /// 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.template is<InnerUnion>() && 
-               Val.template get<InnerUnion>().template is<T>();
-      return Val.template is<T>();
+      // If T is PT1/PT2 choose IsInnerUnion otherwise choose IsPT3.
+      typedef typename
+        ::llvm::PointerUnionTypeSelector<PT1, T, IsInnerUnion,
+          ::llvm::PointerUnionTypeSelector<PT2, T, IsInnerUnion, IsPT3 >
+                                                                   >::Return Ty;
+      return Ty(Val).is<T>();
     }
     
     /// get<T>() - Return the value of the specified pointer type. If the
@@ -208,11 +267,12 @@ namespace llvm {
     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.template get<InnerUnion>().template get<T>();
-      
-      return Val.template get<T>();
+      // If T is PT1/PT2 choose IsInnerUnion otherwise choose IsPT3.
+      typedef typename
+        ::llvm::PointerUnionTypeSelector<PT1, T, IsInnerUnion,
+          ::llvm::PointerUnionTypeSelector<PT2, T, IsInnerUnion, IsPT3 >
+                                                                   >::Return Ty;
+      return Ty(Val).get<T>();
     }
     
     /// dyn_cast<T>() - If the current value is of the specified pointer type,
@@ -302,12 +362,13 @@ namespace llvm {
     /// 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.template is<InnerUnion1>() && 
-               Val.template get<InnerUnion1>().template is<T>();
-      return Val.template is<InnerUnion2>() && 
-             Val.template get<InnerUnion2>().template is<T>();
+      // If T is PT1/PT2 choose InnerUnion1 otherwise choose InnerUnion2.
+      typedef typename
+        ::llvm::PointerUnionTypeSelector<PT1, T, InnerUnion1,
+          ::llvm::PointerUnionTypeSelector<PT2, T, InnerUnion1, InnerUnion2 >
+                                                                   >::Return Ty;
+      return Val.template is<Ty>() && 
+             Val.template get<Ty>().template is<T>();
     }
     
     /// get<T>() - Return the value of the specified pointer type. If the
@@ -315,11 +376,12 @@ namespace llvm {
     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.template get<InnerUnion1>().template get<T>();
-      
-      return Val.template get<InnerUnion2>().template get<T>();
+      // If T is PT1/PT2 choose InnerUnion1 otherwise choose InnerUnion2.
+      typedef typename
+        ::llvm::PointerUnionTypeSelector<PT1, T, InnerUnion1,
+          ::llvm::PointerUnionTypeSelector<PT2, T, InnerUnion1, InnerUnion2 >
+                                                                   >::Return Ty;
+      return Val.template get<Ty>().template get<T>();
     }
     
     /// dyn_cast<T>() - If the current value is of the specified pointer type,
diff --git a/include/llvm/ADT/ScopedHashTable.h b/include/llvm/ADT/ScopedHashTable.h
index af3c482..a6803ee 100644
--- a/include/llvm/ADT/ScopedHashTable.h
+++ b/include/llvm/ADT/ScopedHashTable.h
@@ -96,6 +96,9 @@ public:
   ScopedHashTableScope(ScopedHashTable<K, V, KInfo, AllocatorTy> &HT);
   ~ScopedHashTableScope();
 
+  ScopedHashTableScope *getParentScope() { return PrevScope; }
+  const ScopedHashTableScope *getParentScope() const { return PrevScope; }
+  
 private:
   friend class ScopedHashTable<K, V, KInfo, AllocatorTy>;
   ScopedHashTableVal<K, V> *getLastValInScope() {
@@ -141,9 +144,14 @@ public:
 
 template <typename K, typename V, typename KInfo, typename AllocatorTy>
 class ScopedHashTable {
+public:
+  /// ScopeTy - This is a helpful typedef that allows clients to get easy access
+  /// to the name of the scope for this hash table.
+  typedef ScopedHashTableScope<K, V, KInfo, AllocatorTy> ScopeTy;
+private:
   typedef ScopedHashTableVal<K, V> ValTy;
   DenseMap<K, ValTy*, KInfo> TopLevelMap;
-  ScopedHashTableScope<K, V, KInfo, AllocatorTy> *CurScope;
+  ScopeTy *CurScope;
   
   AllocatorTy Allocator;
   
@@ -157,9 +165,6 @@ public:
     assert(CurScope == 0 && TopLevelMap.empty() && "Scope imbalance!");
   }
   
-  /// ScopeTy - This is a helpful typedef that allows clients to get easy access
-  /// to the name of the scope for this hash table.
-  typedef ScopedHashTableScope<K, V, KInfo, AllocatorTy> ScopeTy;
 
   /// Access to the allocator.
   typedef typename ReferenceAdder<AllocatorTy>::result AllocatorRefTy;
@@ -180,13 +185,7 @@ public:
   }
 
   void insert(const K &Key, const V &Val) {
-    assert(CurScope && "No scope active!");
-
-    ScopedHashTableVal<K, V> *&KeyEntry = TopLevelMap[Key];
-
-    KeyEntry = ValTy::Create(CurScope->getLastValInScope(), KeyEntry, Key, Val,
-                             Allocator);
-    CurScope->setLastValInScope(KeyEntry);
+    insertIntoScope(CurScope, Key, Val);
   }
 
   typedef ScopedHashTableIterator<K, V, KInfo> iterator;
@@ -199,6 +198,21 @@ public:
     if (I == TopLevelMap.end()) return end();
     return iterator(I->second);
   }
+  
+  ScopeTy *getCurScope() { return CurScope; }
+  const ScopeTy *getCurScope() const { return CurScope; }
+
+  /// insertIntoScope - This inserts the specified key/value at the specified
+  /// (possibly not the current) scope.  While it is ok to insert into a scope
+  /// that isn't the current one, it isn't ok to insert *underneath* an existing
+  /// value of the specified key.
+  void insertIntoScope(ScopeTy *S, const K &Key, const V &Val) {
+    assert(S && "No scope active!");
+    ScopedHashTableVal<K, V> *&KeyEntry = TopLevelMap[Key];
+    KeyEntry = ValTy::Create(S->getLastValInScope(), KeyEntry, Key, Val,
+                             Allocator);
+    S->setLastValInScope(KeyEntry);
+  }
 };
 
 /// ScopedHashTableScope ctor - Install this as the current scope for the hash
diff --git a/include/llvm/ADT/SmallPtrSet.h b/include/llvm/ADT/SmallPtrSet.h
index ff32ba8..9992858 100644
--- a/include/llvm/ADT/SmallPtrSet.h
+++ b/include/llvm/ADT/SmallPtrSet.h
@@ -133,7 +133,7 @@ private:
   void shrink_and_clear();
 
   /// Grow - Allocate a larger backing store for the buckets and move it over.
-  void Grow();
+  void Grow(unsigned NewSize);
 
   void operator=(const SmallPtrSetImpl &RHS);  // DO NOT IMPLEMENT.
 protected:
diff --git a/include/llvm/ADT/Statistic.h b/include/llvm/ADT/Statistic.h
index f137ea2..fda99c6 100644
--- a/include/llvm/ADT/Statistic.h
+++ b/include/llvm/ADT/Statistic.h
@@ -121,6 +121,9 @@ protected:
 /// \brief Enable the collection and printing of statistics.
 void EnableStatistics();
 
+/// \brief Check if statistics are enabled.
+bool AreStatisticsEnabled();
+
 /// \brief Print statistics to the file returned by CreateInfoOutputFile().
 void PrintStatistics();
 
diff --git a/include/llvm/ADT/StringExtras.h b/include/llvm/ADT/StringExtras.h
index acbed66..5f5c041 100644
--- a/include/llvm/ADT/StringExtras.h
+++ b/include/llvm/ADT/StringExtras.h
@@ -20,7 +20,6 @@
 #include <cctype>
 #include <cstdio>
 #include <string>
-#include <vector>
 
 namespace llvm {
 template<typename T> class SmallVectorImpl;
@@ -153,7 +152,7 @@ void SplitString(StringRef Source,
                  SmallVectorImpl<StringRef> &OutFragments,
                  StringRef Delimiters = " \t\n\v\f\r");
 
-/// HashString - Hash funtion for strings.
+/// HashString - Hash function for strings.
 ///
 /// This is the Bernstein hash function.
 //
diff --git a/include/llvm/ADT/StringMap.h b/include/llvm/ADT/StringMap.h
index bad0e6f..934cacc 100644
--- a/include/llvm/ADT/StringMap.h
+++ b/include/llvm/ADT/StringMap.h
@@ -17,7 +17,6 @@
 #include "llvm/ADT/StringRef.h"
 #include "llvm/Support/Allocator.h"
 #include <cstring>
-#include <string>
 
 namespace llvm {
   template<typename ValueT>
@@ -81,16 +80,6 @@ protected:
   StringMapImpl(unsigned InitSize, unsigned ItemSize);
   void RehashTable();
 
-  /// ShouldRehash - Return true if the table should be rehashed after a new
-  /// element was recently inserted.
-  bool ShouldRehash() const {
-    // If the hash table is now more than 3/4 full, or if fewer than 1/8 of
-    // the buckets are empty (meaning that many are filled with tombstones),
-    // grow the table.
-    return NumItems*4 > NumBuckets*3 ||
-           NumBuckets-(NumItems+NumTombstones) < NumBuckets/8;
-  }
-
   /// LookupBucketFor - Look up the bucket that the specified string should end
   /// up in.  If it already exists as a key in the map, the Item pointer for the
   /// specified bucket will be non-null.  Otherwise, it will be null.  In either
@@ -339,9 +328,9 @@ public:
       --NumTombstones;
     Bucket.Item = KeyValue;
     ++NumItems;
+    assert(NumItems + NumTombstones <= NumBuckets);
 
-    if (ShouldRehash())
-      RehashTable();
+    RehashTable();
     return true;
   }
 
@@ -359,6 +348,7 @@ public:
     }
 
     NumItems = 0;
+    NumTombstones = 0;
   }
 
   /// GetOrCreateValue - Look up the specified key in the table.  If a value
@@ -378,13 +368,13 @@ public:
     if (Bucket.Item == getTombstoneVal())
       --NumTombstones;
     ++NumItems;
+    assert(NumItems + NumTombstones <= NumBuckets);
 
     // Fill in the bucket for the hash table.  The FullHashValue was already
     // filled in by LookupBucketFor.
     Bucket.Item = NewItem;
 
-    if (ShouldRehash())
-      RehashTable();
+    RehashTable();
     return *NewItem;
   }
 
diff --git a/include/llvm/ADT/Triple.h b/include/llvm/ADT/Triple.h
index e6dcc23..2659bce 100644
--- a/include/llvm/ADT/Triple.h
+++ b/include/llvm/ADT/Triple.h
@@ -64,7 +64,8 @@ public:
     x86_64,  // X86-64: amd64, x86_64
     xcore,   // XCore: xcore
     mblaze,  // MBlaze: mblaze
-    ptx,     // PTX: ptx
+    ptx32,   // PTX: ptx (32-bit)
+    ptx64,   // PTX: ptx (64-bit)
 
     InvalidArch
   };
@@ -72,7 +73,8 @@ public:
     UnknownVendor,
 
     Apple,
-    PC
+    PC,
+    SCEI
   };
   enum OSType {
     UnknownOS,
@@ -82,8 +84,10 @@ public:
     Darwin,
     DragonFly,
     FreeBSD,
+    IOS,
     Linux,
     Lv2,        // PS3
+    MacOSX,
     MinGW32,    // i*86-pc-mingw32, *-w64-mingw32
     NetBSD,
     OpenBSD,
@@ -221,21 +225,81 @@ public:
   /// if the environment component is present).
   StringRef getOSAndEnvironmentName() const;
 
+  /// getOSNumber - Parse the version number from the OS name component of the
+  /// triple, if present.
+  ///
+  /// For example, "fooos1.2.3" would return (1, 2, 3).
+  ///
+  /// If an entry is not defined, it will be returned as 0.
+  void getOSVersion(unsigned &Major, unsigned &Minor, unsigned &Micro) const;
 
-  /// 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
+  /// getOSMajorVersion - 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);
+  unsigned getOSMajorVersion() const {
+    unsigned Maj, Min, Micro;
+    getDarwinNumber(Maj, Min, Micro);
     return Maj;
   }
 
+  void getDarwinNumber(unsigned &Major, unsigned &Minor,
+                       unsigned &Micro) const {
+    return getOSVersion(Major, Minor, Micro);
+  }
+
+  unsigned getDarwinMajorNumber() const {
+    return getOSMajorVersion();
+  }
+
+  /// isOSVersionLT - Helper function for doing comparisons against version
+  /// numbers included in the target triple.
+  bool isOSVersionLT(unsigned Major, unsigned Minor = 0,
+                     unsigned Micro = 0) const {
+    unsigned LHS[3];
+    getOSVersion(LHS[0], LHS[1], LHS[2]);
+
+    if (LHS[0] != Major)
+      return LHS[0] < Major;
+    if (LHS[1] != Minor)
+      return LHS[1] < Minor;
+    if (LHS[2] != Micro)
+      return LHS[1] < Micro;
+
+    return false;
+  }
+
+  /// isMacOSX - Is this a Mac OS X triple. For legacy reasons, we support both
+  /// "darwin" and "osx" as OS X triples.
+  bool isMacOSX() const {
+    return getOS() == Triple::Darwin || getOS() == Triple::MacOSX;
+  }
+
+  /// isOSDarwin - Is this a "Darwin" OS (OS X or iOS).
+  bool isOSDarwin() const {
+    return isMacOSX() ||getOS() == Triple::IOS;
+  }
+
+  /// isOSWindows - Is this a "Windows" OS.
+  bool isOSWindows() const {
+    return getOS() == Triple::Win32 || getOS() == Triple::Cygwin ||
+      getOS() == Triple::MinGW32;
+  }
+
+  /// isMacOSXVersionLT - Comparison function for checking OS X version
+  /// compatibility, which handles supporting skewed version numbering schemes
+  /// used by the "darwin" triples.
+  unsigned isMacOSXVersionLT(unsigned Major, unsigned Minor = 0,
+                          unsigned Micro = 0) const {
+    assert(isMacOSX() && "Not an OS X triple!");
+
+    // If this is OS X, expect a sane version number.
+    if (getOS() == Triple::MacOSX)
+      return isOSVersionLT(Major, Minor, Micro);
+
+    // Otherwise, compare to the "Darwin" number.
+    assert(Major == 10 && "Unexpected major version");
+    return isOSVersionLT(Minor + 4, Micro, 0);
+  }
+    
   /// @}
   /// @name Mutators
   /// @{
diff --git a/include/llvm/ADT/ilist.h b/include/llvm/ADT/ilist.h
index 865fcb3..bcacfd9 100644
--- a/include/llvm/ADT/ilist.h
+++ b/include/llvm/ADT/ilist.h
@@ -289,7 +289,7 @@ template<typename NodeTy> struct simplify_type<const ilist_iterator<NodeTy> > {
 //===----------------------------------------------------------------------===//
 //
 /// iplist - The subset of list functionality that can safely be used on nodes
-/// of polymorphic types, i.e. a heterogenous list with a common base class that
+/// of polymorphic types, i.e. a heterogeneous list with a common base class that
 /// holds the next/prev pointers.  The only state of the list itself is a single
 /// pointer to the head of the list.
 ///