Update LLVM to r86025.

110 files changed, 2223 insertions, 1024 deletions

diff --git a/include/llvm-c/Core.h b/include/llvm-c/Core.h
index 353cab2..7cb5bc3 100644
--- a/include/llvm-c/Core.h
+++ b/include/llvm-c/Core.h
@@ -33,7 +33,7 @@
 #ifndef LLVM_C_CORE_H
 #define LLVM_C_CORE_H
 
-#include "llvm/Support/DataTypes.h"
+#include "llvm/System/DataTypes.h"
 
 #ifdef __cplusplus
 
@@ -455,8 +455,7 @@ void LLVMDisposeTypeHandle(LLVMTypeHandleRef TypeHandle);
         macro(UnreachableInst)              \
         macro(UnwindInst)                   \
     macro(UnaryInstruction)                 \
-      macro(AllocationInst)                 \
-        macro(AllocaInst)                   \
+      macro(AllocaInst)                     \
       macro(CastInst)                       \
         macro(BitCastInst)                  \
         macro(FPExtInst)                    \
@@ -471,7 +470,6 @@ void LLVMDisposeTypeHandle(LLVMTypeHandleRef TypeHandle);
         macro(UIToFPInst)                   \
         macro(ZExtInst)                     \
       macro(ExtractValueInst)               \
-      macro(FreeInst)                       \
       macro(LoadInst)                       \
       macro(VAArgInst)
 
diff --git a/include/llvm-c/Transforms/IPO.h b/include/llvm-c/Transforms/IPO.h
index 9bc947f..0a94315 100644
--- a/include/llvm-c/Transforms/IPO.h
+++ b/include/llvm-c/Transforms/IPO.h
@@ -54,7 +54,7 @@ void LLVMAddLowerSetJmpPass(LLVMPassManagerRef PM);
 /** See llvm::createPruneEHPass function. */
 void LLVMAddPruneEHPass(LLVMPassManagerRef PM);
 
-/** See llvm::createRaiseAllocationsPass function. */
+// FIXME: Remove in LLVM 3.0.
 void LLVMAddRaiseAllocationsPass(LLVMPassManagerRef PM);
 
 /** See llvm::createStripDeadPrototypesPass function. */
diff --git a/include/llvm/ADT/DenseMap.h b/include/llvm/ADT/DenseMap.h
index 0ed2d5a..52354b7 100644
--- a/include/llvm/ADT/DenseMap.h
+++ b/include/llvm/ADT/DenseMap.h
@@ -454,12 +454,12 @@ public:
     return Ptr != RHS.Ptr;
   }
 
-  inline DenseMapIterator& operator++() {          // Preincrement
+  inline DenseMapIterator& operator++() {  // Preincrement
     ++Ptr;
     AdvancePastEmptyBuckets();
     return *this;
   }
-  DenseMapIterator operator++(int) {        // Postincrement
+  DenseMapIterator operator++(int) {  // Postincrement
     DenseMapIterator tmp = *this; ++*this; return tmp;
   }
 
diff --git a/include/llvm/ADT/EquivalenceClasses.h b/include/llvm/ADT/EquivalenceClasses.h
index ac9dd4d..f5f3d49 100644
--- a/include/llvm/ADT/EquivalenceClasses.h
+++ b/include/llvm/ADT/EquivalenceClasses.h
@@ -15,7 +15,7 @@
 #ifndef LLVM_ADT_EQUIVALENCECLASSES_H
 #define LLVM_ADT_EQUIVALENCECLASSES_H
 
-#include "llvm/Support/DataTypes.h"
+#include "llvm/System/DataTypes.h"
 #include <set>
 
 namespace llvm {
diff --git a/include/llvm/ADT/FoldingSet.h b/include/llvm/ADT/FoldingSet.h
index 26090ce..81dc469 100644
--- a/include/llvm/ADT/FoldingSet.h
+++ b/include/llvm/ADT/FoldingSet.h
@@ -16,7 +16,7 @@
 #ifndef LLVM_ADT_FOLDINGSET_H
 #define LLVM_ADT_FOLDINGSET_H
 
-#include "llvm/Support/DataTypes.h"
+#include "llvm/System/DataTypes.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/StringRef.h"
 
diff --git a/include/llvm/ADT/ImmutableList.h b/include/llvm/ADT/ImmutableList.h
index a7f5819..5f8cb57 100644
--- a/include/llvm/ADT/ImmutableList.h
+++ b/include/llvm/ADT/ImmutableList.h
@@ -16,7 +16,7 @@
 
 #include "llvm/Support/Allocator.h"
 #include "llvm/ADT/FoldingSet.h"
-#include "llvm/Support/DataTypes.h"
+#include "llvm/System/DataTypes.h"
 #include <cassert>
 
 namespace llvm {
diff --git a/include/llvm/ADT/ImmutableSet.h b/include/llvm/ADT/ImmutableSet.h
index 8627909..16b4403 100644
--- a/include/llvm/ADT/ImmutableSet.h
+++ b/include/llvm/ADT/ImmutableSet.h
@@ -16,7 +16,7 @@
 
 #include "llvm/Support/Allocator.h"
 #include "llvm/ADT/FoldingSet.h"
-#include "llvm/Support/DataTypes.h"
+#include "llvm/System/DataTypes.h"
 #include <cassert>
 #include <functional>
 
diff --git a/include/llvm/ADT/SmallPtrSet.h b/include/llvm/ADT/SmallPtrSet.h
index 7d00e9a..c29fc9f 100644
--- a/include/llvm/ADT/SmallPtrSet.h
+++ b/include/llvm/ADT/SmallPtrSet.h
@@ -18,7 +18,7 @@
 #include <cassert>
 #include <cstring>
 #include <iterator>
-#include "llvm/Support/DataTypes.h"
+#include "llvm/System/DataTypes.h"
 #include "llvm/Support/PointerLikeTypeTraits.h"
 
 namespace llvm {
diff --git a/include/llvm/ADT/SparseBitVector.h b/include/llvm/ADT/SparseBitVector.h
index b7a6873..6c813ec 100644
--- a/include/llvm/ADT/SparseBitVector.h
+++ b/include/llvm/ADT/SparseBitVector.h
@@ -17,7 +17,7 @@
 
 #include "llvm/ADT/ilist.h"
 #include "llvm/ADT/ilist_node.h"
-#include "llvm/Support/DataTypes.h"
+#include "llvm/System/DataTypes.h"
 #include "llvm/Support/MathExtras.h"
 #include "llvm/Support/raw_ostream.h"
 #include <cassert>
diff --git a/include/llvm/ADT/StringExtras.h b/include/llvm/ADT/StringExtras.h
index 899823d..85936c0 100644
--- a/include/llvm/ADT/StringExtras.h
+++ b/include/llvm/ADT/StringExtras.h
@@ -14,7 +14,7 @@
 #ifndef LLVM_ADT_STRINGEXTRAS_H
 #define LLVM_ADT_STRINGEXTRAS_H
 
-#include "llvm/Support/DataTypes.h"
+#include "llvm/System/DataTypes.h"
 #include "llvm/ADT/APFloat.h"
 #include "llvm/ADT/StringRef.h"
 #include <cctype>
diff --git a/include/llvm/ADT/StringSwitch.h b/include/llvm/ADT/StringSwitch.h
new file mode 100644
index 0000000..48a52de
--- /dev/null
+++ b/include/llvm/ADT/StringSwitch.h
@@ -0,0 +1,83 @@
+//===--- StringSwitch.h - Switch-on-literal-string Construct --------------===/
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//===----------------------------------------------------------------------===/
+//
+//  This file implements the StringSwitch template, which mimics a switch()
+//  statements whose cases are string literals.
+//
+//===----------------------------------------------------------------------===/
+#ifndef LLVM_ADT_STRINGSWITCH_H
+#define LLVM_ADT_STRINGSWITCH_H
+
+#include "llvm/ADT/StringRef.h"
+#include <cassert>
+#include <cstring>
+
+namespace llvm {
+  
+/// \brief A switch()-like statement whose cases are string literals.
+///
+/// The StringSwitch class is a simple form of a switch() statement that
+/// determines whether the given string matches one of the given string
+/// literals. The template type parameter \p T is the type of the value that
+/// will be returned from the string-switch expression. For example,
+/// the following code switches on the name of a color in \c argv[i]:
+///
+/// \code
+/// Color color = StringSwitch<Color>(argv[i])
+///   .Case("red", Red)
+///   .Case("orange", Orange)
+///   .Case("yellow", Yellow)
+///   .Case("green", Green)
+///   .Case("blue", Blue)
+///   .Case("indigo", Indigo)
+///   .Case("violet", Violet)
+///   .Default(UnknownColor);
+/// \endcode
+template<typename T>
+class StringSwitch {
+  /// \brief The string we are matching.
+  StringRef Str;
+  
+  /// \brief The result of this switch statement, once known.
+  T Result;
+  
+  /// \brief Set true when the result of this switch is already known; in this
+  /// case, Result is valid.
+  bool ResultKnown;
+  
+public:
+  explicit StringSwitch(StringRef Str) 
+  : Str(Str), ResultKnown(false) { }
+  
+  template<unsigned N>
+  StringSwitch& Case(const char (&S)[N], const T& Value) {
+    if (!ResultKnown && N-1 == Str.size() && 
+        (std::memcmp(S, Str.data(), N-1) == 0)) {
+      Result = Value;
+      ResultKnown = true;
+    }
+    
+    return *this;
+  }
+  
+  T Default(const T& Value) {
+    if (ResultKnown)
+      return Result;
+    
+    return Value;
+  }
+  
+  operator T() {
+    assert(ResultKnown && "Fell off the end of a string-switch");
+    return Result;
+  }
+};
+
+} // end namespace llvm
+
+#endif // LLVM_ADT_STRINGSWITCH_H
diff --git a/include/llvm/ADT/Twine.h b/include/llvm/ADT/Twine.h
index 88fde0a..f4722db 100644
--- a/include/llvm/ADT/Twine.h
+++ b/include/llvm/ADT/Twine.h
@@ -11,7 +11,7 @@
 #define LLVM_ADT_TWINE_H
 
 #include "llvm/ADT/StringRef.h"
-#include "llvm/Support/DataTypes.h"
+#include "llvm/System/DataTypes.h"
 #include <cassert>
 #include <string>
 
diff --git a/include/llvm/ADT/ValueMap.h b/include/llvm/ADT/ValueMap.h
index 14f2100..b043c38 100644
--- a/include/llvm/ADT/ValueMap.h
+++ b/include/llvm/ADT/ValueMap.h
@@ -7,7 +7,19 @@
 //
 //===----------------------------------------------------------------------===//
 //
-// This file defines the ValueMap class.
+// This file defines the ValueMap class.  ValueMap maps Value* or any subclass
+// to an arbitrary other type.  It provides the DenseMap interface but updates
+// itself to remain safe when keys are RAUWed or deleted.  By default, when a
+// key is RAUWed from V1 to V2, the old mapping V1->target is removed, and a new
+// mapping V2->target is added.  If V2 already existed, its old target is
+// overwritten.  When a key is deleted, its mapping is removed.
+//
+// You can override a ValueMap's Config parameter to control exactly what
+// happens on RAUW and destruction and to get called back on each event.  It's
+// legal to call back into the ValueMap from a Config's callbacks.  Config
+// parameters should inherit from ValueMapConfig<KeyT> to get default
+// implementations of all the methods ValueMap uses.  See ValueMapConfig for
+// documentation of the functions you can override.
 //
 //===----------------------------------------------------------------------===//
 
@@ -31,6 +43,9 @@ class ValueMapIterator;
 template<typename DenseMapT, typename KeyT>
 class ValueMapConstIterator;
 
+/// This class defines the default behavior for configurable aspects of
+/// ValueMap<>.  User Configs should inherit from this class to be as compatible
+/// as possible with future versions of ValueMap.
 template<typename KeyT>
 struct ValueMapConfig {
   /// If FollowRAUW is true, the ValueMap will update mappings on RAUW. If it's
@@ -46,27 +61,17 @@ struct ValueMapConfig {
   template<typename ExtraDataT>
   static void onRAUW(const ExtraDataT &Data, KeyT Old, KeyT New) {}
   template<typename ExtraDataT>
-  static void onDeleted(const ExtraDataT &Data, KeyT Old) {}
+  static void onDelete(const ExtraDataT &Data, KeyT Old) {}
 
   /// Returns a mutex that should be acquired around any changes to the map.
   /// This is only acquired from the CallbackVH (and held around calls to onRAUW
-  /// and onDeleted) and not inside other ValueMap methods.  NULL means that no
+  /// and onDelete) and not inside other ValueMap methods.  NULL means that no
   /// mutex is necessary.
   template<typename ExtraDataT>
   static sys::Mutex *getMutex(const ExtraDataT &Data) { return NULL; }
 };
 
-/// ValueMap maps Value* or any subclass to an arbitrary other
-/// type. It provides the DenseMap interface.  When the key values are
-/// deleted or RAUWed, ValueMap relies on the Config to decide what to
-/// do.  Config parameters should inherit from ValueMapConfig<KeyT> to
-/// get default implementations of all the methods ValueMap uses.
-///
-/// By default, when a key is RAUWed from V1 to V2, the old mapping
-/// V1->target is removed, and a new mapping V2->target is added.  If
-/// V2 already existed, its old target is overwritten.  When a key is
-/// deleted, its mapping is removed.  You can override Config to get
-/// called back on each event.
+/// See the file comment.
 template<typename KeyT, typename ValueT, typename Config = ValueMapConfig<KeyT>,
          typename ValueInfoT = DenseMapInfo<ValueT> >
 class ValueMap {
@@ -177,6 +182,9 @@ public:
   }
 
 private:
+  // Takes a key being looked up in the map and wraps it into a
+  // ValueMapCallbackVH, the actual key type of the map.  We use a helper
+  // function because ValueMapCVH is constructed with a second parameter.
   ValueMapCVH Wrap(KeyT key) const {
     // The only way the resulting CallbackVH could try to modify *this (making
     // the const_cast incorrect) is if it gets inserted into the map.  But then
@@ -186,10 +194,12 @@ private:
   }
 };
 
+// This CallbackVH updates its ValueMap when the contained Value changes,
+// according to the user's preferences expressed through the Config object.
 template<typename KeyT, typename ValueT, typename Config, typename ValueInfoT>
 class ValueMapCallbackVH : public CallbackVH {
   friend class ValueMap<KeyT, ValueT, Config, ValueInfoT>;
-  friend class DenseMapInfo<ValueMapCallbackVH>;
+  friend struct DenseMapInfo<ValueMapCallbackVH>;
   typedef ValueMap<KeyT, ValueT, Config, ValueInfoT> ValueMapT;
   typedef typename llvm::remove_pointer<KeyT>::type KeySansPointerT;
 
@@ -208,7 +218,7 @@ public:
     sys::Mutex *M = Config::getMutex(Copy.Map->Data);
     if (M)
       M->acquire();
-    Config::onDeleted(Copy.Map->Data, Copy.Unwrap());  // May destroy *this.
+    Config::onDelete(Copy.Map->Data, Copy.Unwrap());  // May destroy *this.
     Copy.Map->Map.erase(Copy);  // Definitely destroys *this.
     if (M)
       M->release();
@@ -279,7 +289,7 @@ public:
   struct ValueTypeProxy {
     const KeyT first;
     ValueT& second;
-    ValueTypeProxy *operator->()  { return this; }
+    ValueTypeProxy *operator->() { return this; }
     operator std::pair<KeyT, ValueT>() const {
       return std::make_pair(first, second);
     }
@@ -301,11 +311,11 @@ public:
     return I != RHS.I;
   }
 
-  inline ValueMapIterator& operator++() {          // Preincrement
+  inline ValueMapIterator& operator++() {  // Preincrement
     ++I;
     return *this;
   }
-  ValueMapIterator operator++(int) {        // Postincrement
+  ValueMapIterator operator++(int) {  // Postincrement
     ValueMapIterator tmp = *this; ++*this; return tmp;
   }
 };
@@ -329,7 +339,7 @@ public:
   struct ValueTypeProxy {
     const KeyT first;
     const ValueT& second;
-    ValueTypeProxy *operator->()  { return this; }
+    ValueTypeProxy *operator->() { return this; }
     operator std::pair<KeyT, ValueT>() const {
       return std::make_pair(first, second);
     }
@@ -351,11 +361,11 @@ public:
     return I != RHS.I;
   }
 
-  inline ValueMapConstIterator& operator++() {          // Preincrement
+  inline ValueMapConstIterator& operator++() {  // Preincrement
     ++I;
     return *this;
   }
-  ValueMapConstIterator operator++(int) {        // Postincrement
+  ValueMapConstIterator operator++(int) {  // Postincrement
     ValueMapConstIterator tmp = *this; ++*this; return tmp;
   }
 };
diff --git a/include/llvm/Analysis/AliasSetTracker.h b/include/llvm/Analysis/AliasSetTracker.h
index 239f30f..42a377e 100644
--- a/include/llvm/Analysis/AliasSetTracker.h
+++ b/include/llvm/Analysis/AliasSetTracker.h
@@ -29,7 +29,6 @@ namespace llvm {
 class AliasAnalysis;
 class LoadInst;
 class StoreInst;
-class FreeInst;
 class VAArgInst;
 class AliasSetTracker;
 class AliasSet;
@@ -298,7 +297,6 @@ public:
   bool add(Value *Ptr, unsigned Size);  // Add a location
   bool add(LoadInst *LI);
   bool add(StoreInst *SI);
-  bool add(FreeInst *FI);
   bool add(VAArgInst *VAAI);
   bool add(CallSite CS);          // Call/Invoke instructions
   bool add(CallInst *CI)   { return add(CallSite(CI)); }
@@ -313,7 +311,6 @@ public:
   bool remove(Value *Ptr, unsigned Size);  // Remove a location
   bool remove(LoadInst *LI);
   bool remove(StoreInst *SI);
-  bool remove(FreeInst *FI);
   bool remove(VAArgInst *VAAI);
   bool remove(CallSite CS);
   bool remove(CallInst *CI)   { return remove(CallSite(CI)); }
diff --git a/include/llvm/Analysis/DebugInfo.h b/include/llvm/Analysis/DebugInfo.h
index f76aa46..cfe3632 100644
--- a/include/llvm/Analysis/DebugInfo.h
+++ b/include/llvm/Analysis/DebugInfo.h
@@ -514,6 +514,13 @@ namespace llvm {
                                 uint64_t OffsetInBits, unsigned Flags,
                                 unsigned Encoding);
 
+    /// CreateBasicType - Create a basic type like int, float, etc.
+    DIBasicType CreateBasicTypeEx(DIDescriptor Context, StringRef Name,
+                                DICompileUnit CompileUnit, unsigned LineNumber,
+                                Constant *SizeInBits, Constant *AlignInBits,
+                                Constant *OffsetInBits, unsigned Flags,
+                                unsigned Encoding);
+
     /// CreateDerivedType - Create a derived type like const qualified type,
     /// pointer, typedef, etc.
     DIDerivedType CreateDerivedType(unsigned Tag, DIDescriptor Context,
@@ -524,6 +531,16 @@ namespace llvm {
                                     uint64_t OffsetInBits, unsigned Flags,
                                     DIType DerivedFrom);
 
+    /// CreateDerivedType - Create a derived type like const qualified type,
+    /// pointer, typedef, etc.
+    DIDerivedType CreateDerivedTypeEx(unsigned Tag, DIDescriptor Context,
+                                        StringRef Name,
+                                    DICompileUnit CompileUnit,
+                                    unsigned LineNumber,
+                                    Constant *SizeInBits, Constant *AlignInBits,
+                                    Constant *OffsetInBits, unsigned Flags,
+                                    DIType DerivedFrom);
+
     /// CreateCompositeType - Create a composite type like array, struct, etc.
     DICompositeType CreateCompositeType(unsigned Tag, DIDescriptor Context,
                                         StringRef Name,
@@ -536,6 +553,18 @@ namespace llvm {
                                         DIArray Elements,
                                         unsigned RunTimeLang = 0);
 
+    /// CreateCompositeType - Create a composite type like array, struct, etc.
+    DICompositeType CreateCompositeTypeEx(unsigned Tag, DIDescriptor Context,
+                                        StringRef Name,
+                                        DICompileUnit CompileUnit,
+                                        unsigned LineNumber,
+                                        Constant *SizeInBits,
+                                        Constant *AlignInBits,
+                                        Constant *OffsetInBits, unsigned Flags,
+                                        DIType DerivedFrom,
+                                        DIArray Elements,
+                                        unsigned RunTimeLang = 0);
+
     /// CreateSubprogram - Create a new descriptor for the specified subprogram.
     /// See comments in DISubprogram for descriptions of these fields.
     DISubprogram CreateSubprogram(DIDescriptor Context, StringRef Name,
diff --git a/include/llvm/Analysis/Dominators.h b/include/llvm/Analysis/Dominators.h
index 59ce6e7..17aaf95 100644
--- a/include/llvm/Analysis/Dominators.h
+++ b/include/llvm/Analysis/Dominators.h
@@ -905,9 +905,9 @@ public:
   iterator       find(BasicBlock *B)       { return Frontiers.find(B); }
   const_iterator find(BasicBlock *B) const { return Frontiers.find(B); }
 
-  void addBasicBlock(BasicBlock *BB, const DomSetType &frontier) {
+  iterator addBasicBlock(BasicBlock *BB, const DomSetType &frontier) {
     assert(find(BB) == end() && "Block already in DominanceFrontier!");
-    Frontiers.insert(std::make_pair(BB, frontier));
+    return Frontiers.insert(std::make_pair(BB, frontier)).first;
   }
 
   /// removeBlock - Remove basic block BB's frontier.
diff --git a/include/llvm/Analysis/LoopInfo.h b/include/llvm/Analysis/LoopInfo.h
index 7631110..bc87adb 100644
--- a/include/llvm/Analysis/LoopInfo.h
+++ b/include/llvm/Analysis/LoopInfo.h
@@ -114,10 +114,10 @@ public:
   block_iterator block_begin() const { return Blocks.begin(); }
   block_iterator block_end() const { return Blocks.end(); }
 
-  /// isLoopExit - True if terminator in the block can branch to another block
+  /// isLoopExiting - True if terminator in the block can branch to another block
   /// that is outside of the current loop.
   ///
-  bool isLoopExit(const BlockT *BB) const {
+  bool isLoopExiting(const BlockT *BB) const {
     typedef GraphTraits<BlockT*> BlockTraits;
     for (typename BlockTraits::ChildIteratorType SI =
          BlockTraits::child_begin(const_cast<BlockT*>(BB)),
@@ -465,7 +465,7 @@ public:
       WriteAsOperand(OS, BB, false);
       if (BB == getHeader())    OS << "<header>";
       if (BB == getLoopLatch()) OS << "<latch>";
-      if (isLoopExit(BB))       OS << "<exit>";
+      if (isLoopExiting(BB))    OS << "<exiting>";
     }
     OS << "\n";
 
diff --git a/include/llvm/Analysis/MemoryBuiltins.h b/include/llvm/Analysis/MemoryBuiltins.h
new file mode 100644
index 0000000..5fd0bb0
--- /dev/null
+++ b/include/llvm/Analysis/MemoryBuiltins.h
@@ -0,0 +1,79 @@
+//===- llvm/Analysis/MemoryBuiltins.h- Calls to memory builtins -*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This family of functions identifies calls to builtin functions that allocate
+// or free memory.  
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ANALYSIS_MEMORYBUILTINS_H
+#define LLVM_ANALYSIS_MEMORYBUILTINS_H
+
+namespace llvm {
+class CallInst;
+class LLVMContext;
+class PointerType;
+class TargetData;
+class Type;
+class Value;
+
+//===----------------------------------------------------------------------===//
+//  malloc Call Utility Functions.
+//
+
+/// isMalloc - Returns true if the value is either a malloc call or a bitcast of 
+/// the result of a malloc call
+bool isMalloc(const Value* I);
+
+/// extractMallocCall - Returns the corresponding CallInst if the instruction
+/// is a malloc call.  Since CallInst::CreateMalloc() only creates calls, we
+/// ignore InvokeInst here.
+const CallInst* extractMallocCall(const Value* I);
+CallInst* extractMallocCall(Value* I);
+
+/// extractMallocCallFromBitCast - Returns the corresponding CallInst if the
+/// instruction is a bitcast of the result of a malloc call.
+const CallInst* extractMallocCallFromBitCast(const Value* I);
+CallInst* extractMallocCallFromBitCast(Value* I);
+
+/// isArrayMalloc - Returns the corresponding CallInst if the instruction 
+/// is a call to malloc whose array size can be determined and the array size
+/// is not constant 1.  Otherwise, return NULL.
+CallInst* isArrayMalloc(Value* I, LLVMContext &Context, const TargetData* TD);
+const CallInst* isArrayMalloc(const Value* I, LLVMContext &Context,
+                              const TargetData* TD);
+
+/// getMallocType - Returns the PointerType resulting from the malloc call.
+/// This PointerType is the result type of the call's only bitcast use.
+/// If there is no unique bitcast use, then return NULL.
+const PointerType* getMallocType(const CallInst* CI);
+
+/// getMallocAllocatedType - Returns the Type allocated by malloc call. This
+/// Type is the result type of the call's only bitcast use. If there is no
+/// unique bitcast use, then return NULL.
+const Type* getMallocAllocatedType(const CallInst* CI);
+
+/// getMallocArraySize - Returns the array size of a malloc call.  If the 
+/// argument passed to malloc is a multiple of the size of the malloced type,
+/// then return that multiple.  For non-array mallocs, the multiple is
+/// constant 1.  Otherwise, return NULL for mallocs whose array size cannot be
+/// determined.
+Value* getMallocArraySize(CallInst* CI, LLVMContext &Context,
+                          const TargetData* TD);
+                          
+//===----------------------------------------------------------------------===//
+//  free Call Utility Functions.
+//
+
+/// isFreeCall - Returns true if the the value is a call to the builtin free()
+bool isFreeCall(const Value* I);
+
+} // End llvm namespace
+
+#endif
diff --git a/include/llvm/Analysis/ScalarEvolution.h b/include/llvm/Analysis/ScalarEvolution.h
index ed5d18e..4aa3dfa 100644
--- a/include/llvm/Analysis/ScalarEvolution.h
+++ b/include/llvm/Analysis/ScalarEvolution.h
@@ -24,7 +24,7 @@
 #include "llvm/Pass.h"
 #include "llvm/Instructions.h"
 #include "llvm/Function.h"
-#include "llvm/Support/DataTypes.h"
+#include "llvm/System/DataTypes.h"
 #include "llvm/Support/ValueHandle.h"
 #include "llvm/Support/Allocator.h"
 #include "llvm/Support/ConstantRange.h"
@@ -563,11 +563,10 @@ namespace llvm {
     /// has an analyzable loop-invariant backedge-taken count.
     bool hasLoopInvariantBackedgeTakenCount(const Loop *L);
 
-    /// forgetLoopBackedgeTakenCount - This method should be called by the
-    /// client when it has changed a loop in a way that may effect
-    /// ScalarEvolution's ability to compute a trip count, or if the loop
-    /// is deleted.
-    void forgetLoopBackedgeTakenCount(const Loop *L);
+    /// forgetLoop - This method should be called by the client when it has
+    /// changed a loop in a way that may effect ScalarEvolution's ability to
+    /// compute a trip count, or if the loop is deleted.
+    void forgetLoop(const Loop *L);
 
     /// GetMinTrailingZeros - Determine the minimum number of zero bits that S
     /// is guaranteed to end in (at every loop iteration).  It is, at the same
diff --git a/include/llvm/Analysis/ValueTracking.h b/include/llvm/Analysis/ValueTracking.h
index 212b5d1..f233608 100644
--- a/include/llvm/Analysis/ValueTracking.h
+++ b/include/llvm/Analysis/ValueTracking.h
@@ -15,7 +15,7 @@
 #ifndef LLVM_ANALYSIS_VALUETRACKING_H
 #define LLVM_ANALYSIS_VALUETRACKING_H
 
-#include "llvm/Support/DataTypes.h"
+#include "llvm/System/DataTypes.h"
 #include <string>
 
 namespace llvm {
diff --git a/include/llvm/BasicBlock.h b/include/llvm/BasicBlock.h
index b497827..ba4caeb 100644
--- a/include/llvm/BasicBlock.h
+++ b/include/llvm/BasicBlock.h
@@ -17,12 +17,13 @@
 #include "llvm/Instruction.h"
 #include "llvm/SymbolTableListTraits.h"
 #include "llvm/ADT/ilist.h"
-#include "llvm/Support/DataTypes.h"
+#include "llvm/System/DataTypes.h"
 
 namespace llvm {
 
 class TerminatorInst;
 class LLVMContext;
+class BlockAddress;
 
 template<> struct ilist_traits<Instruction>
   : public SymbolTableListTraits<Instruction, BasicBlock> {
@@ -66,7 +67,7 @@ private:
 /// @brief LLVM Basic Block Representation
 class BasicBlock : public Value, // Basic blocks are data objects also
                    public ilist_node<BasicBlock> {
-
+  friend class BlockAddress;
 public:
   typedef iplist<Instruction> InstListType;
 private:
@@ -108,10 +109,10 @@ public:
         Function *getParent()       { return Parent; }
 
   /// use_back - Specialize the methods defined in Value, as we know that an
-  /// BasicBlock can only be used by Instructions (specifically PHI nodes and
-  /// terminators).
-  Instruction       *use_back()       { return cast<Instruction>(*use_begin());}
-  const Instruction *use_back() const { return cast<Instruction>(*use_begin());}
+  /// BasicBlock can only be used by Users (specifically PHI nodes, terminators,
+  /// and BlockAddress's).
+  User       *use_back()       { return cast<User>(*use_begin());}
+  const User *use_back() const { return cast<User>(*use_begin());}
   
   /// getTerminator() - If this is a well formed basic block, then this returns
   /// a pointer to the terminator instruction.  If it is not, then you get a
@@ -235,6 +236,19 @@ public:
   /// keeping loop information consistent, use the SplitBlock utility function.
   ///
   BasicBlock *splitBasicBlock(iterator I, const Twine &BBName = "");
+
+  /// hasAddressTaken - returns true if there are any uses of this basic block
+  /// other than direct branches, switches, etc. to it.
+  bool hasAddressTaken() const { return SubclassData != 0; }
+                     
+private:
+  /// AdjustBlockAddressRefCount - BasicBlock stores the number of BlockAddress
+  /// objects using it.  This is almost always 0, sometimes one, possibly but
+  /// almost never 2, and inconceivably 3 or more.
+  void AdjustBlockAddressRefCount(int Amt) {
+    SubclassData += Amt;
+    assert((int)(char)SubclassData >= 0 && "Refcount wrap-around");
+  }
 };
 
 } // End llvm namespace
diff --git a/include/llvm/Bitcode/BitCodes.h b/include/llvm/Bitcode/BitCodes.h
index 449dc35..ada2e65 100644
--- a/include/llvm/Bitcode/BitCodes.h
+++ b/include/llvm/Bitcode/BitCodes.h
@@ -19,7 +19,7 @@
 #define LLVM_BITCODE_BITCODES_H
 
 #include "llvm/ADT/SmallVector.h"
-#include "llvm/Support/DataTypes.h"
+#include "llvm/System/DataTypes.h"
 #include <cassert>
 
 namespace llvm {
diff --git a/include/llvm/Bitcode/Deserialize.h b/include/llvm/Bitcode/Deserialize.h
index 3e90227..90a5141 100644
--- a/include/llvm/Bitcode/Deserialize.h
+++ b/include/llvm/Bitcode/Deserialize.h
@@ -20,7 +20,7 @@
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/Support/Allocator.h"
-#include "llvm/Support/DataTypes.h"
+#include "llvm/System/DataTypes.h"
 #include <vector>
 
 namespace llvm {
diff --git a/include/llvm/Bitcode/LLVMBitCodes.h b/include/llvm/Bitcode/LLVMBitCodes.h
index dccd8e0..c037399 100644
--- a/include/llvm/Bitcode/LLVMBitCodes.h
+++ b/include/llvm/Bitcode/LLVMBitCodes.h
@@ -138,7 +138,8 @@ namespace bitc {
     CST_CODE_CE_CMP        = 17,  // CE_CMP:        [opty, opval, opval, pred]
     CST_CODE_INLINEASM     = 18,  // INLINEASM:     [sideeffect,asmstr,conststr]
     CST_CODE_CE_SHUFVEC_EX = 19,  // SHUFVEC_EX:    [opty, opval, opval, opval]
-    CST_CODE_CE_INBOUNDS_GEP = 20 // INBOUNDS_GEP:  [n x operands]
+    CST_CODE_CE_INBOUNDS_GEP = 20,// INBOUNDS_GEP:  [n x operands]
+    CST_CODE_BLOCKADDRESS  = 21   // CST_CODE_BLOCKADDRESS [fnty, fnval, bb#]
   };
 
   /// CastOpcodes - These are values used in the bitcode files to encode which
@@ -209,7 +210,7 @@ namespace bitc {
 
     FUNC_CODE_INST_RET         = 10, // RET:        [opty,opval<both optional>]
     FUNC_CODE_INST_BR          = 11, // BR:         [bb#, bb#, cond] or [bb#]
-    FUNC_CODE_INST_SWITCH      = 12, // SWITCH:     [opty, opval, n, n x ops]
+    FUNC_CODE_INST_SWITCH      = 12, // SWITCH:     [opty, op0, op1, ...]
     FUNC_CODE_INST_INVOKE      = 13, // INVOKE:     [attr, fnty, op0,op1, ...]
     FUNC_CODE_INST_UNWIND      = 14, // UNWIND
     FUNC_CODE_INST_UNREACHABLE = 15, // UNREACHABLE
@@ -236,7 +237,8 @@ namespace bitc {
     FUNC_CODE_INST_CMP2        = 28, // CMP2:       [opty, opval, opval, pred]
     // new select on i1 or [N x i1]
     FUNC_CODE_INST_VSELECT     = 29, // VSELECT:    [ty,opval,opval,predty,pred]
-    FUNC_CODE_INST_INBOUNDS_GEP = 30 // INBOUNDS_GEP: [n x operands]
+    FUNC_CODE_INST_INBOUNDS_GEP= 30, // INBOUNDS_GEP: [n x operands]
+    FUNC_CODE_INST_INDIRECTBR  = 31  // INDIRECTBR: [opty, op0, op1, ...]
   };
 } // End bitc namespace
 } // End llvm namespace
diff --git a/include/llvm/CodeGen/AsmPrinter.h b/include/llvm/CodeGen/AsmPrinter.h
index 62d0679..a0bd330 100644
--- a/include/llvm/CodeGen/AsmPrinter.h
+++ b/include/llvm/CodeGen/AsmPrinter.h
@@ -22,6 +22,7 @@
 #include "llvm/ADT/DenseMap.h"
 
 namespace llvm {
+  class BlockAddress;
   class GCStrategy;
   class Constant;
   class ConstantArray;
@@ -334,6 +335,12 @@ namespace llvm {
     /// block label.
     MCSymbol *GetMBBSymbol(unsigned MBBID) const;
     
+    /// GetBlockAddressSymbol - Return the MCSymbol used to satisfy BlockAddress
+    /// uses of the specified basic block.
+    MCSymbol *GetBlockAddressSymbol(const BlockAddress *BA) const;
+    MCSymbol *GetBlockAddressSymbol(const Function *F,
+                                    const BasicBlock *BB) const;
+
     /// EmitBasicBlockStart - This method prints the label for the specified
     /// MachineBasicBlock, an alignment (if present) and a comment describing
     /// it if appropriate.
diff --git a/include/llvm/CodeGen/BinaryObject.h b/include/llvm/CodeGen/BinaryObject.h
index 2d4bd73..9e2ef18 100644
--- a/include/llvm/CodeGen/BinaryObject.h
+++ b/include/llvm/CodeGen/BinaryObject.h
@@ -15,7 +15,7 @@
 #ifndef LLVM_CODEGEN_BINARYOBJECT_H
 #define LLVM_CODEGEN_BINARYOBJECT_H
 
-#include "llvm/Support/DataTypes.h"
+#include "llvm/System/DataTypes.h"
 
 #include <string>
 #include <vector>
diff --git a/include/llvm/CodeGen/ELFRelocation.h b/include/llvm/CodeGen/ELFRelocation.h
index c3f88f1..e58b8df 100644
--- a/include/llvm/CodeGen/ELFRelocation.h
+++ b/include/llvm/CodeGen/ELFRelocation.h
@@ -14,7 +14,7 @@
 #ifndef LLVM_CODEGEN_ELF_RELOCATION_H
 #define LLVM_CODEGEN_ELF_RELOCATION_H
 
-#include "llvm/Support/DataTypes.h"
+#include "llvm/System/DataTypes.h"
 
 namespace llvm {
 
diff --git a/include/llvm/CodeGen/JITCodeEmitter.h b/include/llvm/CodeGen/JITCodeEmitter.h
index 180783a..792fb59 100644
--- a/include/llvm/CodeGen/JITCodeEmitter.h
+++ b/include/llvm/CodeGen/JITCodeEmitter.h
@@ -18,7 +18,7 @@
 #define LLVM_CODEGEN_JITCODEEMITTER_H
 
 #include <string>
-#include "llvm/Support/DataTypes.h"
+#include "llvm/System/DataTypes.h"
 #include "llvm/Support/MathExtras.h"
 #include "llvm/CodeGen/MachineCodeEmitter.h"
 
diff --git a/include/llvm/CodeGen/LatencyPriorityQueue.h b/include/llvm/CodeGen/LatencyPriorityQueue.h
index 71fae2a..a7cebee 100644
--- a/include/llvm/CodeGen/LatencyPriorityQueue.h
+++ b/include/llvm/CodeGen/LatencyPriorityQueue.h
@@ -39,12 +39,21 @@ namespace llvm {
     /// predecessor for.  This is used as a tie-breaker heuristic for better
     /// mobility.
     std::vector<unsigned> NumNodesSolelyBlocking;
-
+    
+    /// IgnoreAntiDep - Ignore anti-dependencies
+    bool IgnoreAntiDep;
+    
+    /// Queue - The queue.
     PriorityQueue<SUnit*, std::vector<SUnit*>, latency_sort> Queue;
+
 public:
-    LatencyPriorityQueue() : Queue(latency_sort(this)) {
+  LatencyPriorityQueue() : IgnoreAntiDep(false), Queue(latency_sort(this)) {
     }
-    
+
+    void setIgnoreAntiDep(bool ignore) {
+      IgnoreAntiDep = ignore;
+    }
+
     void initNodes(std::vector<SUnit> &sunits) {
       SUnits = &sunits;
       NumNodesSolelyBlocking.resize(SUnits->size(), 0);
@@ -63,7 +72,7 @@ public:
     
     unsigned getLatency(unsigned NodeNum) const {
       assert(NodeNum < (*SUnits).size());
-      return (*SUnits)[NodeNum].getHeight();
+      return (*SUnits)[NodeNum].getHeight(IgnoreAntiDep);
     }
     
     unsigned getNumSolelyBlockNodes(unsigned NodeNum) const {
diff --git a/include/llvm/CodeGen/LiveInterval.h b/include/llvm/CodeGen/LiveInterval.h
index 05bd173..e31a7f0 100644
--- a/include/llvm/CodeGen/LiveInterval.h
+++ b/include/llvm/CodeGen/LiveInterval.h
@@ -21,221 +21,19 @@
 #ifndef LLVM_CODEGEN_LIVEINTERVAL_H
 #define LLVM_CODEGEN_LIVEINTERVAL_H
 
-#include "llvm/ADT/DenseMapInfo.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/Support/Allocator.h"
 #include "llvm/Support/AlignOf.h"
+#include "llvm/CodeGen/SlotIndexes.h"
 #include <cassert>
 #include <climits>
 
 namespace llvm {
+  class LiveIntervals;
   class MachineInstr;
   class MachineRegisterInfo;
   class TargetRegisterInfo;
   class raw_ostream;
-  
-  /// LiveIndex - An opaque wrapper around machine indexes.
-  class LiveIndex {
-    friend class VNInfo;
-    friend class LiveInterval;
-    friend class LiveIntervals;
-    friend struct DenseMapInfo<LiveIndex>;
-
-  public:
-
-    enum Slot { LOAD, USE, DEF, STORE, NUM };
-
-  private:
-
-    unsigned index;
-
-    static const unsigned PHI_BIT = 1 << 31;
-
-  public:
-
-    /// Construct a default LiveIndex pointing to a reserved index.
-    LiveIndex() : index(0) {}
-
-    /// Construct an index from the given index, pointing to the given slot.
-    LiveIndex(LiveIndex m, Slot s)
-      : index((m.index / NUM) * NUM + s) {} 
-    
-    /// Print this index to the given raw_ostream.
-    void print(raw_ostream &os) const;
-
-    /// Compare two LiveIndex objects for equality.
-    bool operator==(LiveIndex other) const {
-      return ((index & ~PHI_BIT) == (other.index & ~PHI_BIT));
-    }
-    /// Compare two LiveIndex objects for inequality.
-    bool operator!=(LiveIndex other) const {
-      return ((index & ~PHI_BIT) != (other.index & ~PHI_BIT));
-    }
-   
-    /// Compare two LiveIndex objects. Return true if the first index
-    /// is strictly lower than the second.
-    bool operator<(LiveIndex other) const {
-      return ((index & ~PHI_BIT) < (other.index & ~PHI_BIT));
-    }
-    /// Compare two LiveIndex objects. Return true if the first index
-    /// is lower than, or equal to, the second.
-    bool operator<=(LiveIndex other) const {
-      return ((index & ~PHI_BIT) <= (other.index & ~PHI_BIT));
-    }
-
-    /// Compare two LiveIndex objects. Return true if the first index
-    /// is greater than the second.
-    bool operator>(LiveIndex other) const {
-      return ((index & ~PHI_BIT) > (other.index & ~PHI_BIT));
-    }
-
-    /// Compare two LiveIndex objects. Return true if the first index
-    /// is greater than, or equal to, the second.
-    bool operator>=(LiveIndex other) const {
-      return ((index & ~PHI_BIT) >= (other.index & ~PHI_BIT));
-    }
-
-    /// Returns true if this index represents a load.
-    bool isLoad() const {
-      return ((index % NUM) == LOAD);
-    }
-
-    /// Returns true if this index represents a use.
-    bool isUse() const {
-      return ((index % NUM) == USE);
-    }
-
-    /// Returns true if this index represents a def.
-    bool isDef() const {
-      return ((index % NUM) == DEF);
-    }
-
-    /// Returns true if this index represents a store.
-    bool isStore() const {
-      return ((index % NUM) == STORE);
-    }
-
-    /// Returns the slot for this LiveIndex.
-    Slot getSlot() const {
-      return static_cast<Slot>(index % NUM);
-    }
-
-    /// Returns true if this index represents a non-PHI use/def.
-    bool isNonPHIIndex() const {
-      return ((index & PHI_BIT) == 0);
-    }
-
-    /// Returns true if this index represents a PHI use/def.
-    bool isPHIIndex() const {
-      return ((index & PHI_BIT) == PHI_BIT);
-    }
-
-  private:
-
-    /// Construct an index from the given index, with its PHI kill marker set.
-    LiveIndex(bool phi, LiveIndex o) : index(o.index) {
-      if (phi)
-        index |= PHI_BIT;
-      else
-        index &= ~PHI_BIT;
-    }
-
-    explicit LiveIndex(unsigned idx)
-      : index(idx & ~PHI_BIT) {}
-
-    LiveIndex(bool phi, unsigned idx)
-      : index(idx & ~PHI_BIT) {
-      if (phi)
-        index |= PHI_BIT;
-    }
-
-    LiveIndex(bool phi, unsigned idx, Slot slot)
-      : index(((idx / NUM) * NUM + slot) & ~PHI_BIT) {
-      if (phi)
-        index |= PHI_BIT;
-    }
-    
-    LiveIndex nextSlot_() const {
-      assert((index & PHI_BIT) == ((index + 1) & PHI_BIT) &&
-             "Index out of bounds.");
-      return LiveIndex(index + 1);
-    }
-
-    LiveIndex nextIndex_() const {
-      assert((index & PHI_BIT) == ((index + NUM) & PHI_BIT) &&
-             "Index out of bounds.");
-      return LiveIndex(index + NUM);
-    }
-
-    LiveIndex prevSlot_() const {
-      assert((index & PHI_BIT) == ((index - 1) & PHI_BIT) &&
-             "Index out of bounds.");
-      return LiveIndex(index - 1);
-    }
-
-    LiveIndex prevIndex_() const {
-      assert((index & PHI_BIT) == ((index - NUM) & PHI_BIT) &&
-             "Index out of bounds.");
-      return LiveIndex(index - NUM);
-    }
-
-    int distance(LiveIndex other) const {
-      return (other.index & ~PHI_BIT) - (index & ~PHI_BIT);
-    }
-
-    /// Returns an unsigned number suitable as an index into a
-    /// vector over all instructions.
-    unsigned getVecIndex() const {
-      return (index & ~PHI_BIT) / NUM;
-    }
-
-    /// Scale this index by the given factor.
-    LiveIndex scale(unsigned factor) const {
-      unsigned i = (index & ~PHI_BIT) / NUM,
-               o = (index % ~PHI_BIT) % NUM;
-      assert(index <= (~0U & ~PHI_BIT) / (factor * NUM) &&
-             "Rescaled interval would overflow");
-      return LiveIndex(i * NUM * factor, o);
-    }
-
-    static LiveIndex emptyKey() {
-      return LiveIndex(true, 0x7fffffff);
-    }
-
-    static LiveIndex tombstoneKey() {
-      return LiveIndex(true, 0x7ffffffe);
-    }
-
-    static unsigned getHashValue(const LiveIndex &v) {
-      return v.index * 37;
-    }
-
-  };
-
-  inline raw_ostream& operator<<(raw_ostream &os, LiveIndex mi) {
-    mi.print(os);
-    return os;
-  }
-
-  /// Densemap specialization for LiveIndex.
-  template <>
-  struct DenseMapInfo<LiveIndex> {
-    static inline LiveIndex getEmptyKey() {
-      return LiveIndex::emptyKey();
-    }
-    static inline LiveIndex getTombstoneKey() {
-      return LiveIndex::tombstoneKey();
-    }
-    static inline unsigned getHashValue(const LiveIndex &v) {
-      return LiveIndex::getHashValue(v);
-    }
-    static inline bool isEqual(const LiveIndex &LHS,
-                               const LiveIndex &RHS) {
-      return (LHS == RHS);
-    }
-    static inline bool isPod() { return true; }
-  };
-
 
   /// VNInfo - Value Number Information.
   /// This class holds information about a machine level values, including
@@ -270,23 +68,25 @@ namespace llvm {
 
   public:
 
-    typedef SmallVector<LiveIndex, 4> KillSet;
+    typedef SmallVector<SlotIndex, 4> KillSet;
 
     /// The ID number of this value.
     unsigned id;
     
     /// The index of the defining instruction (if isDefAccurate() returns true).
-    LiveIndex def;
+    SlotIndex def;
 
     KillSet kills;
 
-    VNInfo()
-      : flags(IS_UNUSED), id(~1U) { cr.copy = 0; }
+    /*
+    VNInfo(LiveIntervals &li_)
+      : defflags(IS_UNUSED), id(~1U) { cr.copy = 0; }
+    */
 
     /// VNInfo constructor.
     /// d is presumed to point to the actual defining instr. If it doesn't
     /// setIsDefAccurate(false) should be called after construction.
-    VNInfo(unsigned i, LiveIndex d, MachineInstr *c)
+    VNInfo(unsigned i, SlotIndex d, MachineInstr *c)
       : flags(IS_DEF_ACCURATE), id(i), def(d) { cr.copy = c; }
 
     /// VNInfo construtor, copies values from orig, except for the value number.
@@ -377,7 +177,7 @@ namespace llvm {
     }
 
     /// Returns true if the given index is a kill of this value.
-    bool isKill(LiveIndex k) const {
+    bool isKill(SlotIndex k) const {
       KillSet::const_iterator
         i = std::lower_bound(kills.begin(), kills.end(), k);
       return (i != kills.end() && *i == k);
@@ -385,7 +185,7 @@ namespace llvm {
 
     /// addKill - Add a kill instruction index to the specified value
     /// number.
-    void addKill(LiveIndex k) {
+    void addKill(SlotIndex k) {
       if (kills.empty()) {
         kills.push_back(k);
       } else {
@@ -397,7 +197,7 @@ namespace llvm {
 
     /// Remove the specified kill index from this value's kills list.
     /// Returns true if the value was present, otherwise returns false.
-    bool removeKill(LiveIndex k) {
+    bool removeKill(SlotIndex k) {
       KillSet::iterator i = std::lower_bound(kills.begin(), kills.end(), k);
       if (i != kills.end() && *i == k) {
         kills.erase(i);
@@ -407,7 +207,7 @@ namespace llvm {
     }
 
     /// Remove all kills in the range [s, e).
-    void removeKills(LiveIndex s, LiveIndex e) {
+    void removeKills(SlotIndex s, SlotIndex e) {
       KillSet::iterator
         si = std::lower_bound(kills.begin(), kills.end(), s),
         se = std::upper_bound(kills.begin(), kills.end(), e);
@@ -421,11 +221,11 @@ namespace llvm {
   /// program, with an inclusive start point and an exclusive end point.
   /// These ranges are rendered as [start,end).
   struct LiveRange {
-    LiveIndex start;  // Start point of the interval (inclusive)
-    LiveIndex end;    // End point of the interval (exclusive)
+    SlotIndex start;  // Start point of the interval (inclusive)
+    SlotIndex end;    // End point of the interval (exclusive)
     VNInfo *valno;   // identifier for the value contained in this interval.
 
-    LiveRange(LiveIndex S, LiveIndex E, VNInfo *V)
+    LiveRange(SlotIndex S, SlotIndex E, VNInfo *V)
       : start(S), end(E), valno(V) {
 
       assert(S < E && "Cannot create empty or backwards range");
@@ -433,13 +233,13 @@ namespace llvm {
 
     /// contains - Return true if the index is covered by this range.
     ///
-    bool contains(LiveIndex I) const {
+    bool contains(SlotIndex I) const {
       return start <= I && I < end;
     }
 
     /// containsRange - Return true if the given range, [S, E), is covered by
     /// this range. 
-    bool containsRange(LiveIndex S, LiveIndex E) const {
+    bool containsRange(SlotIndex S, SlotIndex E) const {
       assert((S < E) && "Backwards interval?");
       return (start <= S && S < end) && (start < E && E <= end);
     }
@@ -461,11 +261,11 @@ namespace llvm {
   raw_ostream& operator<<(raw_ostream& os, const LiveRange &LR);
 
 
-  inline bool operator<(LiveIndex V, const LiveRange &LR) {
+  inline bool operator<(SlotIndex V, const LiveRange &LR) {
     return V < LR.start;
   }
 
-  inline bool operator<(const LiveRange &LR, LiveIndex V) {
+  inline bool operator<(const LiveRange &LR, SlotIndex V) {
     return LR.start < V;
   }
 
@@ -522,7 +322,7 @@ namespace llvm {
     /// end of the interval.  If no LiveRange contains this position, but the
     /// position is in a hole, this method returns an iterator pointing the the
     /// LiveRange immediately after the hole.
-    iterator advanceTo(iterator I, LiveIndex Pos) {
+    iterator advanceTo(iterator I, SlotIndex Pos) {
       if (Pos >= endIndex())
         return end();
       while (I->end <= Pos) ++I;
@@ -569,7 +369,7 @@ namespace llvm {
 
     /// getNextValue - Create a new value number and return it.  MIIdx specifies
     /// the instruction that defines the value number.
-    VNInfo *getNextValue(LiveIndex def, MachineInstr *CopyMI,
+    VNInfo *getNextValue(SlotIndex def, MachineInstr *CopyMI,
                          bool isDefAccurate, BumpPtrAllocator &VNInfoAllocator){
       VNInfo *VNI =
         static_cast<VNInfo*>(VNInfoAllocator.Allocate((unsigned)sizeof(VNInfo),
@@ -625,13 +425,15 @@ namespace llvm {
     /// current interval, but are defined in the Clobbers interval, mark them
     /// used with an unknown definition value. Caller must pass in reference to
     /// VNInfoAllocator since it will create a new val#.
-    void MergeInClobberRanges(const LiveInterval &Clobbers,
+    void MergeInClobberRanges(LiveIntervals &li_,
+                              const LiveInterval &Clobbers,
                               BumpPtrAllocator &VNInfoAllocator);
 
     /// MergeInClobberRange - Same as MergeInClobberRanges except it merge in a
     /// single LiveRange only.
-    void MergeInClobberRange(LiveIndex Start,
-                             LiveIndex End,
+    void MergeInClobberRange(LiveIntervals &li_,
+                             SlotIndex Start,
+                             SlotIndex End,
                              BumpPtrAllocator &VNInfoAllocator);
 
     /// MergeValueInAsValue - Merge all of the live ranges of a specific val#
@@ -657,56 +459,54 @@ namespace llvm {
     bool empty() const { return ranges.empty(); }
 
     /// beginIndex - Return the lowest numbered slot covered by interval.
-    LiveIndex beginIndex() const {
-      if (empty())
-        return LiveIndex();
+    SlotIndex beginIndex() const {
+      assert(!empty() && "Call to beginIndex() on empty interval.");
       return ranges.front().start;
     }
 
     /// endNumber - return the maximum point of the interval of the whole,
     /// exclusive.
-    LiveIndex endIndex() const {
-      if (empty())
-        return LiveIndex();
+    SlotIndex endIndex() const {
+      assert(!empty() && "Call to endIndex() on empty interval.");
       return ranges.back().end;
     }
 
-    bool expiredAt(LiveIndex index) const {
+    bool expiredAt(SlotIndex index) const {
       return index >= endIndex();
     }
 
-    bool liveAt(LiveIndex index) const;
+    bool liveAt(SlotIndex index) const;
 
     // liveBeforeAndAt - Check if the interval is live at the index and the
     // index just before it. If index is liveAt, check if it starts a new live
     // range.If it does, then check if the previous live range ends at index-1.
-    bool liveBeforeAndAt(LiveIndex index) const;
+    bool liveBeforeAndAt(SlotIndex index) const;
 
     /// getLiveRangeContaining - Return the live range that contains the
     /// specified index, or null if there is none.
-    const LiveRange *getLiveRangeContaining(LiveIndex Idx) const {
+    const LiveRange *getLiveRangeContaining(SlotIndex Idx) const {
       const_iterator I = FindLiveRangeContaining(Idx);
       return I == end() ? 0 : &*I;
     }
 
     /// getLiveRangeContaining - Return the live range that contains the
     /// specified index, or null if there is none.
-    LiveRange *getLiveRangeContaining(LiveIndex Idx) {
+    LiveRange *getLiveRangeContaining(SlotIndex Idx) {
       iterator I = FindLiveRangeContaining(Idx);
       return I == end() ? 0 : &*I;
     }
 
     /// FindLiveRangeContaining - Return an iterator to the live range that
     /// contains the specified index, or end() if there is none.
-    const_iterator FindLiveRangeContaining(LiveIndex Idx) const;
+    const_iterator FindLiveRangeContaining(SlotIndex Idx) const;
 
     /// FindLiveRangeContaining - Return an iterator to the live range that
     /// contains the specified index, or end() if there is none.
-    iterator FindLiveRangeContaining(LiveIndex Idx);
+    iterator FindLiveRangeContaining(SlotIndex Idx);
 
     /// findDefinedVNInfo - Find the by the specified
     /// index (register interval) or defined 
-    VNInfo *findDefinedVNInfoForRegInt(LiveIndex Idx) const;
+    VNInfo *findDefinedVNInfoForRegInt(SlotIndex Idx) const;
 
     /// findDefinedVNInfo - Find the VNInfo that's defined by the specified
     /// register (stack inteval only).
@@ -721,7 +521,7 @@ namespace llvm {
 
     /// overlaps - Return true if the live interval overlaps a range specified
     /// by [Start, End).
-    bool overlaps(LiveIndex Start, LiveIndex End) const;
+    bool overlaps(SlotIndex Start, SlotIndex End) const;
 
     /// overlapsFrom - Return true if the intersection of the two live intervals
     /// is not empty.  The specified iterator is a hint that we can begin
@@ -738,18 +538,19 @@ namespace llvm {
     /// join - Join two live intervals (this, and other) together.  This applies
     /// mappings to the value numbers in the LHS/RHS intervals as specified.  If
     /// the intervals are not joinable, this aborts.
-    void join(LiveInterval &Other, const int *ValNoAssignments,
+    void join(LiveInterval &Other,
+              const int *ValNoAssignments,
               const int *RHSValNoAssignments,
               SmallVector<VNInfo*, 16> &NewVNInfo,
               MachineRegisterInfo *MRI);
 
     /// isInOneLiveRange - Return true if the range specified is entirely in the
     /// a single LiveRange of the live interval.
-    bool isInOneLiveRange(LiveIndex Start, LiveIndex End);
+    bool isInOneLiveRange(SlotIndex Start, SlotIndex End);
 
     /// removeRange - Remove the specified range from this interval.  Note that
     /// the range must be a single LiveRange in its entirety.
-    void removeRange(LiveIndex Start, LiveIndex End,
+    void removeRange(SlotIndex Start, SlotIndex End,
                      bool RemoveDeadValNo = false);
 
     void removeRange(LiveRange LR, bool RemoveDeadValNo = false) {
@@ -773,8 +574,8 @@ namespace llvm {
     void ComputeJoinedWeight(const LiveInterval &Other);
 
     bool operator<(const LiveInterval& other) const {
-      const LiveIndex &thisIndex = beginIndex();
-      const LiveIndex &otherIndex = other.beginIndex();
+      const SlotIndex &thisIndex = beginIndex();
+      const SlotIndex &otherIndex = other.beginIndex();
       return (thisIndex < otherIndex ||
               (thisIndex == otherIndex && reg < other.reg));
     }
@@ -785,8 +586,9 @@ namespace llvm {
   private:
 
     Ranges::iterator addRangeFrom(LiveRange LR, Ranges::iterator From);
-    void extendIntervalEndTo(Ranges::iterator I, LiveIndex NewEnd);
-    Ranges::iterator extendIntervalStartTo(Ranges::iterator I, LiveIndex NewStr);
+    void extendIntervalEndTo(Ranges::iterator I, SlotIndex NewEnd);
+    Ranges::iterator extendIntervalStartTo(Ranges::iterator I, SlotIndex NewStr);
+
     LiveInterval& operator=(const LiveInterval& rhs); // DO NOT IMPLEMENT
 
   };
diff --git a/include/llvm/CodeGen/LiveIntervalAnalysis.h b/include/llvm/CodeGen/LiveIntervalAnalysis.h
index 511db6d..efb4a03 100644
--- a/include/llvm/CodeGen/LiveIntervalAnalysis.h
+++ b/include/llvm/CodeGen/LiveIntervalAnalysis.h
@@ -23,12 +23,14 @@
 #include "llvm/CodeGen/MachineBasicBlock.h"
 #include "llvm/CodeGen/MachineFunctionPass.h"
 #include "llvm/CodeGen/LiveInterval.h"
+#include "llvm/CodeGen/SlotIndexes.h"
 #include "llvm/ADT/BitVector.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/Support/Allocator.h"
 #include <cmath>
+#include <iterator>
 
 namespace llvm {
 
@@ -40,21 +42,6 @@ namespace llvm {
   class TargetInstrInfo;
   class TargetRegisterClass;
   class VirtRegMap;
-  typedef std::pair<LiveIndex, MachineBasicBlock*> IdxMBBPair;
-
-  inline bool operator<(LiveIndex V, const IdxMBBPair &IM) {
-    return V < IM.first;
-  }
-
-  inline bool operator<(const IdxMBBPair &IM, LiveIndex V) {
-    return IM.first < V;
-  }
-
-  struct Idx2MBBCompare {
-    bool operator()(const IdxMBBPair &LHS, const IdxMBBPair &RHS) const {
-      return LHS.first < RHS.first;
-    }
-  };
   
   class LiveIntervals : public MachineFunctionPass {
     MachineFunction* mf_;
@@ -64,33 +51,15 @@ namespace llvm {
     const TargetInstrInfo* tii_;
     AliasAnalysis *aa_;
     LiveVariables* lv_;
+    SlotIndexes* indexes_;
 
     /// Special pool allocator for VNInfo's (LiveInterval val#).
     ///
     BumpPtrAllocator VNInfoAllocator;
 
-    /// MBB2IdxMap - The indexes of the first and last instructions in the
-    /// specified basic block.
-    std::vector<std::pair<LiveIndex, LiveIndex> > MBB2IdxMap;
-
-    /// Idx2MBBMap - Sorted list of pairs of index of first instruction
-    /// and MBB id.
-    std::vector<IdxMBBPair> Idx2MBBMap;
-
-    /// FunctionSize - The number of instructions present in the function
-    uint64_t FunctionSize;
-
-    typedef DenseMap<const MachineInstr*, LiveIndex> Mi2IndexMap;
-    Mi2IndexMap mi2iMap_;
-
-    typedef std::vector<MachineInstr*> Index2MiMap;
-    Index2MiMap i2miMap_;
-
     typedef DenseMap<unsigned, LiveInterval*> Reg2IntervalMap;
     Reg2IntervalMap r2iMap_;
 
-    DenseMap<MachineBasicBlock*, LiveIndex> terminatorGaps;
-
     /// phiJoinCopies - Copy instructions which are PHI joins.
     SmallVector<MachineInstr*, 16> phiJoinCopies;
 
@@ -100,48 +69,10 @@ namespace llvm {
     /// CloneMIs - A list of clones as result of re-materialization.
     std::vector<MachineInstr*> CloneMIs;
 
-    typedef LiveInterval::InstrSlots InstrSlots;
-
   public:
     static char ID; // Pass identification, replacement for typeid
     LiveIntervals() : MachineFunctionPass(&ID) {}
 
-    LiveIndex getBaseIndex(LiveIndex index) {
-      return LiveIndex(index, LiveIndex::LOAD);
-    }
-    LiveIndex getBoundaryIndex(LiveIndex index) {
-      return LiveIndex(index,
-        (LiveIndex::Slot)(LiveIndex::NUM - 1));
-    }
-    LiveIndex getLoadIndex(LiveIndex index) {
-      return LiveIndex(index, LiveIndex::LOAD);
-    }
-    LiveIndex getUseIndex(LiveIndex index) {
-      return LiveIndex(index, LiveIndex::USE);
-    }
-    LiveIndex getDefIndex(LiveIndex index) {
-      return LiveIndex(index, LiveIndex::DEF);
-    }
-    LiveIndex getStoreIndex(LiveIndex index) {
-      return LiveIndex(index, LiveIndex::STORE);
-    }    
-
-    LiveIndex getNextSlot(LiveIndex m) const {
-      return m.nextSlot_();
-    }
-
-    LiveIndex getNextIndex(LiveIndex m) const {
-      return m.nextIndex_();
-    }
-
-    LiveIndex getPrevSlot(LiveIndex m) const {
-      return m.prevSlot_();
-    }
-
-    LiveIndex getPrevIndex(LiveIndex m) const {
-      return m.prevIndex_();
-    }
-
     static float getSpillWeight(bool isDef, bool isUse, unsigned loopDepth) {
       return (isDef + isUse) * powf(10.0F, (float)loopDepth);
     }
@@ -170,111 +101,18 @@ namespace llvm {
       return r2iMap_.count(reg);
     }
 
-    /// getMBBStartIdx - Return the base index of the first instruction in the
-    /// specified MachineBasicBlock.
-    LiveIndex getMBBStartIdx(MachineBasicBlock *MBB) const {
-      return getMBBStartIdx(MBB->getNumber());
-    }
-    LiveIndex getMBBStartIdx(unsigned MBBNo) const {
-      assert(MBBNo < MBB2IdxMap.size() && "Invalid MBB number!");
-      return MBB2IdxMap[MBBNo].first;
-    }
-
-    /// getMBBEndIdx - Return the store index of the last instruction in the
-    /// specified MachineBasicBlock.
-    LiveIndex getMBBEndIdx(MachineBasicBlock *MBB) const {
-      return getMBBEndIdx(MBB->getNumber());
-    }
-    LiveIndex getMBBEndIdx(unsigned MBBNo) const {
-      assert(MBBNo < MBB2IdxMap.size() && "Invalid MBB number!");
-      return MBB2IdxMap[MBBNo].second;
-    }
-
     /// getScaledIntervalSize - get the size of an interval in "units,"
     /// where every function is composed of one thousand units.  This
     /// measure scales properly with empty index slots in the function.
     double getScaledIntervalSize(LiveInterval& I) {
-      return (1000.0 / InstrSlots::NUM * I.getSize()) / i2miMap_.size();
+      return (1000.0 * I.getSize()) / indexes_->getIndexesLength();
     }
     
     /// getApproximateInstructionCount - computes an estimate of the number
     /// of instructions in a given LiveInterval.
     unsigned getApproximateInstructionCount(LiveInterval& I) {
       double IntervalPercentage = getScaledIntervalSize(I) / 1000.0;
-      return (unsigned)(IntervalPercentage * FunctionSize);
-    }
-
-    /// getMBBFromIndex - given an index in any instruction of an
-    /// MBB return a pointer the MBB
-    MachineBasicBlock* getMBBFromIndex(LiveIndex index) const {
-      std::vector<IdxMBBPair>::const_iterator I =
-        std::lower_bound(Idx2MBBMap.begin(), Idx2MBBMap.end(), index);
-      // Take the pair containing the index
-      std::vector<IdxMBBPair>::const_iterator J =
-        ((I != Idx2MBBMap.end() && I->first > index) ||
-         (I == Idx2MBBMap.end() && Idx2MBBMap.size()>0)) ? (I-1): I;
-
-      assert(J != Idx2MBBMap.end() && J->first <= index &&
-             index <= getMBBEndIdx(J->second) &&
-             "index does not correspond to an MBB");
-      return J->second;
-    }
-
-    /// getInstructionIndex - returns the base index of instr
-    LiveIndex getInstructionIndex(const MachineInstr* instr) const {
-      Mi2IndexMap::const_iterator it = mi2iMap_.find(instr);
-      assert(it != mi2iMap_.end() && "Invalid instruction!");
-      return it->second;
-    }
-
-    /// getInstructionFromIndex - given an index in any slot of an
-    /// instruction return a pointer the instruction
-    MachineInstr* getInstructionFromIndex(LiveIndex index) const {
-      // convert index to vector index
-      unsigned i = index.getVecIndex();
-      assert(i < i2miMap_.size() &&
-             "index does not correspond to an instruction");
-      return i2miMap_[i];
-    }
-
-    /// hasGapBeforeInstr - Return true if the previous instruction slot,
-    /// i.e. Index - InstrSlots::NUM, is not occupied.
-    bool hasGapBeforeInstr(LiveIndex Index) {
-      Index = getBaseIndex(getPrevIndex(Index));
-      return getInstructionFromIndex(Index) == 0;
-    }
-
-    /// hasGapAfterInstr - Return true if the successive instruction slot,
-    /// i.e. Index + InstrSlots::Num, is not occupied.
-    bool hasGapAfterInstr(LiveIndex Index) {
-      Index = getBaseIndex(getNextIndex(Index));
-      return getInstructionFromIndex(Index) == 0;
-    }
-
-    /// findGapBeforeInstr - Find an empty instruction slot before the
-    /// specified index. If "Furthest" is true, find one that's furthest
-    /// away from the index (but before any index that's occupied).
-    LiveIndex findGapBeforeInstr(LiveIndex Index, bool Furthest = false) {
-      Index = getBaseIndex(getPrevIndex(Index));
-      if (getInstructionFromIndex(Index))
-        return LiveIndex();  // No gap!
-      if (!Furthest)
-        return Index;
-      LiveIndex PrevIndex = getBaseIndex(getPrevIndex(Index));
-      while (getInstructionFromIndex(Index)) {
-        Index = PrevIndex;
-        PrevIndex = getBaseIndex(getPrevIndex(Index));
-      }
-      return Index;
-    }
-
-    /// InsertMachineInstrInMaps - Insert the specified machine instruction
-    /// into the instruction index map at the given index.
-    void InsertMachineInstrInMaps(MachineInstr *MI, LiveIndex Index) {
-      i2miMap_[Index.getVecIndex()] = MI;
-      Mi2IndexMap::iterator it = mi2iMap_.find(MI);
-      assert(it == mi2iMap_.end() && "Already in map!");
-      mi2iMap_[MI] = Index;
+      return (unsigned)(IntervalPercentage * indexes_->getFunctionSize());
     }
 
     /// conflictsWithPhysRegDef - Returns true if the specified register
@@ -288,19 +126,7 @@ namespace llvm {
                                  bool CheckUse,
                                  SmallPtrSet<MachineInstr*,32> &JoinedCopies);
 
-    /// findLiveInMBBs - Given a live range, if the value of the range
-    /// is live in any MBB returns true as well as the list of basic blocks
-    /// in which the value is live.
-    bool findLiveInMBBs(LiveIndex Start, LiveIndex End,
-                        SmallVectorImpl<MachineBasicBlock*> &MBBs) const;
-
-    /// findReachableMBBs - Return a list MBB that can be reached via any
-    /// branch or fallthroughs. Return true if the list is not empty.
-    bool findReachableMBBs(LiveIndex Start, LiveIndex End,
-                        SmallVectorImpl<MachineBasicBlock*> &MBBs) const;
-
     // Interval creation
-
     LiveInterval &getOrCreateInterval(unsigned reg) {
       Reg2IntervalMap::iterator I = r2iMap_.find(reg);
       if (I == r2iMap_.end())
@@ -325,36 +151,75 @@ namespace llvm {
       r2iMap_.erase(I);
     }
 
+    SlotIndex getZeroIndex() const {
+      return indexes_->getZeroIndex();
+    }
+
+    SlotIndex getInvalidIndex() const {
+      return indexes_->getInvalidIndex();
+    }
+
     /// isNotInMIMap - returns true if the specified machine instr has been
     /// removed or was never entered in the map.
-    bool isNotInMIMap(MachineInstr* instr) const {
-      return !mi2iMap_.count(instr);
+    bool isNotInMIMap(const MachineInstr* Instr) const {
+      return !indexes_->hasIndex(Instr);
+    }
+
+    /// Returns the base index of the given instruction.
+    SlotIndex getInstructionIndex(const MachineInstr *instr) const {
+      return indexes_->getInstructionIndex(instr);
+    }
+    
+    /// Returns the instruction associated with the given index.
+    MachineInstr* getInstructionFromIndex(SlotIndex index) const {
+      return indexes_->getInstructionFromIndex(index);
+    }
+
+    /// Return the first index in the given basic block.
+    SlotIndex getMBBStartIdx(const MachineBasicBlock *mbb) const {
+      return indexes_->getMBBStartIdx(mbb);
+    } 
+
+    /// Return the last index in the given basic block.
+    SlotIndex getMBBEndIdx(const MachineBasicBlock *mbb) const {
+      return indexes_->getMBBEndIdx(mbb);
+    } 
+
+    MachineBasicBlock* getMBBFromIndex(SlotIndex index) const {
+      return indexes_->getMBBFromIndex(index);
+    }
+
+    bool hasGapBeforeInstr(SlotIndex index) {
+      return indexes_->hasGapBeforeInstr(index);
+    }
+
+    bool hasGapAfterInstr(SlotIndex index) {
+      return indexes_->hasGapAfterInstr(index);
+    }
+
+    SlotIndex findGapBeforeInstr(SlotIndex index, bool furthest = false) {
+      return indexes_->findGapBeforeInstr(index, furthest);
+    }
+
+    void InsertMachineInstrInMaps(MachineInstr *MI, SlotIndex Index) {
+      indexes_->insertMachineInstrInMaps(MI, Index);
     }
 
-    /// RemoveMachineInstrFromMaps - This marks the specified machine instr as
-    /// deleted.
     void RemoveMachineInstrFromMaps(MachineInstr *MI) {
-      // remove index -> MachineInstr and
-      // MachineInstr -> index mappings
-      Mi2IndexMap::iterator mi2i = mi2iMap_.find(MI);
-      if (mi2i != mi2iMap_.end()) {
-        i2miMap_[mi2i->second.index/InstrSlots::NUM] = 0;
-        mi2iMap_.erase(mi2i);
-      }
+      indexes_->removeMachineInstrFromMaps(MI);
     }
 
-    /// ReplaceMachineInstrInMaps - Replacing a machine instr with a new one in
-    /// maps used by register allocator.
     void ReplaceMachineInstrInMaps(MachineInstr *MI, MachineInstr *NewMI) {
-      Mi2IndexMap::iterator mi2i = mi2iMap_.find(MI);
-      if (mi2i == mi2iMap_.end())
-        return;
-      i2miMap_[mi2i->second.index/InstrSlots::NUM] = NewMI;
-      Mi2IndexMap::iterator it = mi2iMap_.find(MI);
-      assert(it != mi2iMap_.end() && "Invalid instruction!");
-      LiveIndex Index = it->second;
-      mi2iMap_.erase(it);
-      mi2iMap_[NewMI] = Index;
+      indexes_->replaceMachineInstrInMaps(MI, NewMI);
+    }
+
+    bool findLiveInMBBs(SlotIndex Start, SlotIndex End,
+                        SmallVectorImpl<MachineBasicBlock*> &MBBs) const {
+      return indexes_->findLiveInMBBs(Start, End, MBBs);
+    }
+
+    void renumber() {
+      indexes_->renumber();
     }
 
     BumpPtrAllocator& getVNInfoAllocator() { return VNInfoAllocator; }
@@ -417,13 +282,6 @@ namespace llvm {
     /// marker to implicit_def defs and their uses.
     void processImplicitDefs();
 
-    /// computeNumbering - Compute the index numbering.
-    void computeNumbering();
-
-    /// scaleNumbering - Rescale interval numbers to introduce gaps for new
-    /// instructions
-    void scaleNumbering(int factor);
-
     /// intervalIsInOneMBB - Returns true if the specified interval is entirely
     /// within a single basic block.
     bool intervalIsInOneMBB(const LiveInterval &li) const;
@@ -443,14 +301,14 @@ namespace llvm {
     /// handleVirtualRegisterDef)
     void handleRegisterDef(MachineBasicBlock *MBB,
                            MachineBasicBlock::iterator MI,
-                           LiveIndex MIIdx,
+                           SlotIndex MIIdx,
                            MachineOperand& MO, unsigned MOIdx);
 
     /// handleVirtualRegisterDef - update intervals for a virtual
     /// register def
     void handleVirtualRegisterDef(MachineBasicBlock *MBB,
                                   MachineBasicBlock::iterator MI,
-                                  LiveIndex MIIdx, MachineOperand& MO,
+                                  SlotIndex MIIdx, MachineOperand& MO,
                                   unsigned MOIdx,
                                   LiveInterval& interval);
 
@@ -458,13 +316,13 @@ namespace llvm {
     /// def.
     void handlePhysicalRegisterDef(MachineBasicBlock* mbb,
                                    MachineBasicBlock::iterator mi,
-                                   LiveIndex MIIdx, MachineOperand& MO,
+                                   SlotIndex MIIdx, MachineOperand& MO,
                                    LiveInterval &interval,
                                    MachineInstr *CopyMI);
 
     /// handleLiveInRegister - Create interval for a livein register.
     void handleLiveInRegister(MachineBasicBlock* mbb,
-                              LiveIndex MIIdx,
+                              SlotIndex MIIdx,
                               LiveInterval &interval, bool isAlias = false);
 
     /// getReMatImplicitUse - If the remat definition MI has one (for now, we
@@ -477,7 +335,7 @@ namespace llvm {
     /// which reaches the given instruction also reaches the specified use
     /// index.
     bool isValNoAvailableAt(const LiveInterval &li, MachineInstr *MI,
-                            LiveIndex UseIdx) const;
+                            SlotIndex UseIdx) const;
 
     /// isReMaterializable - Returns true if the definition MI of the specified
     /// val# of the specified interval is re-materializable. Also returns true
@@ -492,7 +350,7 @@ namespace llvm {
     /// MI. If it is successul, MI is updated with the newly created MI and
     /// returns true.
     bool tryFoldMemoryOperand(MachineInstr* &MI, VirtRegMap &vrm,
-                              MachineInstr *DefMI, LiveIndex InstrIdx,
+                              MachineInstr *DefMI, SlotIndex InstrIdx,
                               SmallVector<unsigned, 2> &Ops,
                               bool isSS, int FrameIndex, unsigned Reg);
 
@@ -506,7 +364,7 @@ namespace llvm {
     /// VNInfo that's after the specified index but is within the basic block.
     bool anyKillInMBBAfterIdx(const LiveInterval &li, const VNInfo *VNI,
                               MachineBasicBlock *MBB,
-                              LiveIndex Idx) const;
+                              SlotIndex Idx) const;
 
     /// hasAllocatableSuperReg - Return true if the specified physical register
     /// has any super register that's allocatable.
@@ -514,17 +372,17 @@ namespace llvm {
 
     /// SRInfo - Spill / restore info.
     struct SRInfo {
-      LiveIndex index;
+      SlotIndex index;
       unsigned vreg;
       bool canFold;
-      SRInfo(LiveIndex i, unsigned vr, bool f)
+      SRInfo(SlotIndex i, unsigned vr, bool f)
         : index(i), vreg(vr), canFold(f) {}
     };
 
-    bool alsoFoldARestore(int Id, LiveIndex index, unsigned vr,
+    bool alsoFoldARestore(int Id, SlotIndex index, unsigned vr,
                           BitVector &RestoreMBBs,
                           DenseMap<unsigned,std::vector<SRInfo> >&RestoreIdxes);
-    void eraseRestoreInfo(int Id, LiveIndex index, unsigned vr,
+    void eraseRestoreInfo(int Id, SlotIndex index, unsigned vr,
                           BitVector &RestoreMBBs,
                           DenseMap<unsigned,std::vector<SRInfo> >&RestoreIdxes);
 
@@ -543,7 +401,7 @@ namespace llvm {
     /// functions for addIntervalsForSpills to rewrite uses / defs for the given
     /// live range.
     bool rewriteInstructionForSpills(const LiveInterval &li, const VNInfo *VNI,
-        bool TrySplit, LiveIndex index, LiveIndex end,
+        bool TrySplit, SlotIndex index, SlotIndex end,
         MachineInstr *MI, MachineInstr *OrigDefMI, MachineInstr *DefMI,
         unsigned Slot, int LdSlot,
         bool isLoad, bool isLoadSS, bool DefIsReMat, bool CanDelete,
diff --git a/include/llvm/CodeGen/LiveStackAnalysis.h b/include/llvm/CodeGen/LiveStackAnalysis.h
index d63a222..e01d1ae 100644
--- a/include/llvm/CodeGen/LiveStackAnalysis.h
+++ b/include/llvm/CodeGen/LiveStackAnalysis.h
@@ -48,8 +48,6 @@ namespace llvm {
     iterator begin() { return S2IMap.begin(); }
     iterator end() { return S2IMap.end(); }
 
-    void scaleNumbering(int factor);
-
     unsigned getNumIntervals() const { return (unsigned)S2IMap.size(); }
 
     LiveInterval &getOrCreateInterval(int Slot, const TargetRegisterClass *RC) {
diff --git a/include/llvm/CodeGen/MachineBasicBlock.h b/include/llvm/CodeGen/MachineBasicBlock.h
index 2a9e86a..585ee14 100644
--- a/include/llvm/CodeGen/MachineBasicBlock.h
+++ b/include/llvm/CodeGen/MachineBasicBlock.h
@@ -76,6 +76,10 @@ class MachineBasicBlock : public ilist_node<MachineBasicBlock> {
   /// exception handler.
   bool IsLandingPad;
 
+  /// AddressTaken - Indicate that this basic block is potentially the
+  /// target of an indirect branch.
+  bool AddressTaken;
+
   // Intrusive list support
   MachineBasicBlock() {}
 
@@ -92,6 +96,14 @@ public:
   ///
   const BasicBlock *getBasicBlock() const { return BB; }
 
+  /// hasAddressTaken - Test whether this block is potentially the target
+  /// of an indirect branch.
+  bool hasAddressTaken() const { return AddressTaken; }
+
+  /// setHasAddressTaken - Set this block to reflect that it potentially
+  /// is the target of an indirect branch.
+  void setHasAddressTaken() { AddressTaken = true; }
+
   /// getParent - Return the MachineFunction containing this basic block.
   ///
   const MachineFunction *getParent() const { return xParent; }
diff --git a/include/llvm/CodeGen/MachineCodeEmitter.h b/include/llvm/CodeGen/MachineCodeEmitter.h
index abb6dd9..c55a9e6 100644
--- a/include/llvm/CodeGen/MachineCodeEmitter.h
+++ b/include/llvm/CodeGen/MachineCodeEmitter.h
@@ -17,7 +17,7 @@
 #ifndef LLVM_CODEGEN_MACHINECODEEMITTER_H
 #define LLVM_CODEGEN_MACHINECODEEMITTER_H
 
-#include "llvm/Support/DataTypes.h"
+#include "llvm/System/DataTypes.h"
 #include "llvm/Support/DebugLoc.h"
 
 namespace llvm {
diff --git a/include/llvm/CodeGen/MachineFrameInfo.h b/include/llvm/CodeGen/MachineFrameInfo.h
index a04189c..07c1eca 100644
--- a/include/llvm/CodeGen/MachineFrameInfo.h
+++ b/include/llvm/CodeGen/MachineFrameInfo.h
@@ -16,7 +16,7 @@
 
 #include "llvm/ADT/BitVector.h"
 #include "llvm/ADT/DenseSet.h"
-#include "llvm/Support/DataTypes.h"
+#include "llvm/System/DataTypes.h"
 #include <cassert>
 #include <vector>
 
diff --git a/include/llvm/CodeGen/MachineInstrBuilder.h b/include/llvm/CodeGen/MachineInstrBuilder.h
index 7f681d7..6ca63f0 100644
--- a/include/llvm/CodeGen/MachineInstrBuilder.h
+++ b/include/llvm/CodeGen/MachineInstrBuilder.h
@@ -108,13 +108,6 @@ public:
     return *this;
   }
 
-  const MachineInstrBuilder &addMetadata(MDNode *N,
-                                         int64_t Offset = 0,
-                                         unsigned char TargetFlags = 0) const {
-    MI->addOperand(MachineOperand::CreateMDNode(N, Offset, TargetFlags));
-    return *this;
-  }
-
   const MachineInstrBuilder &addExternalSymbol(const char *FnName,
                                           unsigned char TargetFlags = 0) const {
     MI->addOperand(MachineOperand::CreateES(FnName, TargetFlags));
diff --git a/include/llvm/CodeGen/MachineModuleInfo.h b/include/llvm/CodeGen/MachineModuleInfo.h
index 1b924f2..f2b027b 100644
--- a/include/llvm/CodeGen/MachineModuleInfo.h
+++ b/include/llvm/CodeGen/MachineModuleInfo.h
@@ -32,7 +32,7 @@
 #define LLVM_CODEGEN_MACHINEMODULEINFO_H
 
 #include "llvm/Support/Dwarf.h"
-#include "llvm/Support/DataTypes.h"
+#include "llvm/System/DataTypes.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/UniqueVector.h"
diff --git a/include/llvm/CodeGen/MachineOperand.h b/include/llvm/CodeGen/MachineOperand.h
index f715c44..eede2cc 100644
--- a/include/llvm/CodeGen/MachineOperand.h
+++ b/include/llvm/CodeGen/MachineOperand.h
@@ -14,15 +14,15 @@
 #ifndef LLVM_CODEGEN_MACHINEOPERAND_H
 #define LLVM_CODEGEN_MACHINEOPERAND_H
 
-#include "llvm/Support/DataTypes.h"
+#include "llvm/System/DataTypes.h"
 #include <cassert>
 
 namespace llvm {
   
 class ConstantFP;
+class BlockAddress;
 class MachineBasicBlock;
 class GlobalValue;
-class MDNode;
 class MachineInstr;
 class TargetMachine;
 class MachineRegisterInfo;
@@ -42,7 +42,7 @@ public:
     MO_JumpTableIndex,         ///< Address of indexed Jump Table for switch
     MO_ExternalSymbol,         ///< Name of external global symbol
     MO_GlobalAddress,          ///< Address of a global value
-    MO_Metadata                ///< Metadata info
+    MO_BlockAddress            ///< Address of a basic block
   };
 
 private:
@@ -108,7 +108,7 @@ private:
         int Index;                // For MO_*Index - The index itself.
         const char *SymbolName;   // For MO_ExternalSymbol.
         GlobalValue *GV;          // For MO_GlobalAddress.
-        MDNode *Node;             // For MO_Metadata.
+        BlockAddress *BA;         // For MO_BlockAddress.
       } Val;
       int64_t Offset;             // An offset from the object.
     } OffsetedInfo;
@@ -156,8 +156,8 @@ public:
   bool isGlobal() const { return OpKind == MO_GlobalAddress; }
   /// isSymbol - Tests if this is a MO_ExternalSymbol operand.
   bool isSymbol() const { return OpKind == MO_ExternalSymbol; }
-  /// isMetadata - Tests if this is a MO_Metadata operand.
-  bool isMetadata() const { return OpKind == MO_Metadata; }
+  /// isBlockAddress - Tests if this is a MO_BlockAddress operand.
+  bool isBlockAddress() const { return OpKind == MO_BlockAddress; }
 
   //===--------------------------------------------------------------------===//
   // Accessors for Register Operands
@@ -293,15 +293,16 @@ public:
     assert(isGlobal() && "Wrong MachineOperand accessor");
     return Contents.OffsetedInfo.Val.GV;
   }
-  
-  MDNode *getMDNode() const {
-    return Contents.OffsetedInfo.Val.Node;
+
+  BlockAddress *getBlockAddress() const {
+    assert(isBlockAddress() && "Wrong MachineOperand accessor");
+    return Contents.OffsetedInfo.Val.BA;
   }
   
   /// getOffset - Return the offset from the symbol in this operand. This always
   /// returns 0 for ExternalSymbol operands.
   int64_t getOffset() const {
-    assert((isGlobal() || isSymbol() || isCPI()) &&
+    assert((isGlobal() || isSymbol() || isCPI() || isBlockAddress()) &&
            "Wrong MachineOperand accessor");
     return Contents.OffsetedInfo.Offset;
   }
@@ -321,7 +322,7 @@ public:
   }
 
   void setOffset(int64_t Offset) {
-    assert((isGlobal() || isSymbol() || isCPI() || isMetadata()) &&
+    assert((isGlobal() || isSymbol() || isCPI() || isBlockAddress()) &&
         "Wrong MachineOperand accessor");
     Contents.OffsetedInfo.Offset = Offset;
   }
@@ -426,14 +427,6 @@ public:
     Op.setTargetFlags(TargetFlags);
     return Op;
   }
-  static MachineOperand CreateMDNode(MDNode *N, int64_t Offset,
-                                     unsigned char TargetFlags = 0) {
-    MachineOperand Op(MachineOperand::MO_Metadata);
-    Op.Contents.OffsetedInfo.Val.Node = N;
-    Op.setOffset(Offset);
-    Op.setTargetFlags(TargetFlags);
-    return Op;
-  }
   static MachineOperand CreateES(const char *SymName,
                                  unsigned char TargetFlags = 0) {
     MachineOperand Op(MachineOperand::MO_ExternalSymbol);
@@ -442,6 +435,12 @@ public:
     Op.setTargetFlags(TargetFlags);
     return Op;
   }
+  static MachineOperand CreateBA(BlockAddress *BA) {
+    MachineOperand Op(MachineOperand::MO_BlockAddress);
+    Op.Contents.OffsetedInfo.Val.BA = BA;
+    Op.setOffset(0); // Offset is always 0.
+    return Op;
+  }
 
   friend class MachineInstr;
   friend class MachineRegisterInfo;
diff --git a/include/llvm/CodeGen/MachineRelocation.h b/include/llvm/CodeGen/MachineRelocation.h
index c539781..6ea8f07 100644
--- a/include/llvm/CodeGen/MachineRelocation.h
+++ b/include/llvm/CodeGen/MachineRelocation.h
@@ -14,7 +14,7 @@
 #ifndef LLVM_CODEGEN_MACHINERELOCATION_H
 #define LLVM_CODEGEN_MACHINERELOCATION_H
 
-#include "llvm/Support/DataTypes.h"
+#include "llvm/System/DataTypes.h"
 #include <cassert>
 
 namespace llvm {
diff --git a/include/llvm/CodeGen/ProcessImplicitDefs.h b/include/llvm/CodeGen/ProcessImplicitDefs.h
new file mode 100644
index 0000000..cec867f
--- /dev/null
+++ b/include/llvm/CodeGen/ProcessImplicitDefs.h
@@ -0,0 +1,41 @@
+//===-------------- llvm/CodeGen/ProcessImplicitDefs.h ----------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+
+#ifndef LLVM_CODEGEN_PROCESSIMPLICITDEFS_H
+#define LLVM_CODEGEN_PROCESSIMPLICITDEFS_H
+
+#include "llvm/CodeGen/MachineFunctionPass.h"
+
+namespace llvm {
+
+  class MachineInstr;
+  class TargetInstrInfo;
+
+  /// Process IMPLICIT_DEF instructions and make sure there is one implicit_def
+  /// for each use. Add isUndef marker to implicit_def defs and their uses.
+  class ProcessImplicitDefs : public MachineFunctionPass {
+  private:
+
+    bool CanTurnIntoImplicitDef(MachineInstr *MI, unsigned Reg,
+                                unsigned OpIdx, const TargetInstrInfo *tii_);
+
+  public:
+    static char ID;
+
+    ProcessImplicitDefs() : MachineFunctionPass(&ID) {}
+
+    virtual void getAnalysisUsage(AnalysisUsage &au) const;
+
+    virtual bool runOnMachineFunction(MachineFunction &fn);
+  };
+
+}
+
+#endif // LLVM_CODEGEN_PROCESSIMPLICITDEFS_H
diff --git a/include/llvm/CodeGen/PseudoSourceValue.h b/include/llvm/CodeGen/PseudoSourceValue.h
index 7a9122d..26392f5 100644
--- a/include/llvm/CodeGen/PseudoSourceValue.h
+++ b/include/llvm/CodeGen/PseudoSourceValue.h
@@ -43,6 +43,10 @@ namespace llvm {
     /// PseudoSourceValue may also be pointed to by an LLVM IR Value.
     virtual bool isAliased(const MachineFrameInfo *) const;
 
+    /// mayAlias - Return true if the memory pointed to by this
+    /// PseudoSourceValue can ever alias a LLVM IR Value.
+    virtual bool mayAlias(const MachineFrameInfo *) const;
+
     /// classof - Methods for support type inquiry through isa, cast, and
     /// dyn_cast:
     ///
diff --git a/include/llvm/CodeGen/ScheduleDAG.h b/include/llvm/CodeGen/ScheduleDAG.h
index fdbbb1e..d5e7020 100644
--- a/include/llvm/CodeGen/ScheduleDAG.h
+++ b/include/llvm/CodeGen/ScheduleDAG.h
@@ -340,28 +340,34 @@ namespace llvm {
     void removePred(const SDep &D);
 
     /// getDepth - Return the depth of this node, which is the length of the
-    /// maximum path up to any node with has no predecessors.
-    unsigned getDepth() const {
-      if (!isDepthCurrent) const_cast<SUnit *>(this)->ComputeDepth();
+    /// maximum path up to any node with has no predecessors. If IgnoreAntiDep
+    /// is true, ignore anti-dependence edges.
+    unsigned getDepth(bool IgnoreAntiDep=false) const {
+      if (!isDepthCurrent) 
+        const_cast<SUnit *>(this)->ComputeDepth(IgnoreAntiDep);
       return Depth;
     }
 
     /// getHeight - Return the height of this node, which is the length of the
-    /// maximum path down to any node with has no successors.
-    unsigned getHeight() const {
-      if (!isHeightCurrent) const_cast<SUnit *>(this)->ComputeHeight();
+    /// maximum path down to any node with has no successors. If IgnoreAntiDep
+    /// is true, ignore anti-dependence edges.
+    unsigned getHeight(bool IgnoreAntiDep=false) const {
+      if (!isHeightCurrent) 
+        const_cast<SUnit *>(this)->ComputeHeight(IgnoreAntiDep);
       return Height;
     }
 
-    /// setDepthToAtLeast - If NewDepth is greater than this node's depth
-    /// value, set it to be the new depth value. This also recursively
-    /// marks successor nodes dirty.
-    void setDepthToAtLeast(unsigned NewDepth);
+    /// setDepthToAtLeast - If NewDepth is greater than this node's
+    /// depth value, set it to be the new depth value. This also
+    /// recursively marks successor nodes dirty.  If IgnoreAntiDep is
+    /// true, ignore anti-dependence edges.
+    void setDepthToAtLeast(unsigned NewDepth, bool IgnoreAntiDep=false);
 
-    /// setDepthToAtLeast - If NewDepth is greater than this node's depth
-    /// value, set it to be the new height value. This also recursively
-    /// marks predecessor nodes dirty.
-    void setHeightToAtLeast(unsigned NewHeight);
+    /// setDepthToAtLeast - If NewDepth is greater than this node's
+    /// depth value, set it to be the new height value. This also
+    /// recursively marks predecessor nodes dirty. If IgnoreAntiDep is
+    /// true, ignore anti-dependence edges.
+    void setHeightToAtLeast(unsigned NewHeight, bool IgnoreAntiDep=false);
 
     /// setDepthDirty - Set a flag in this node to indicate that its
     /// stored Depth value will require recomputation the next time
@@ -394,8 +400,8 @@ namespace llvm {
     void print(raw_ostream &O, const ScheduleDAG *G) const;
 
   private:
-    void ComputeDepth();
-    void ComputeHeight();
+    void ComputeDepth(bool IgnoreAntiDep);
+    void ComputeHeight(bool IgnoreAntiDep);
   };
 
   //===--------------------------------------------------------------------===//
diff --git a/include/llvm/CodeGen/SelectionDAG.h b/include/llvm/CodeGen/SelectionDAG.h
index e0198ef..8400e86 100644
--- a/include/llvm/CodeGen/SelectionDAG.h
+++ b/include/llvm/CodeGen/SelectionDAG.h
@@ -326,6 +326,8 @@ public:
                           unsigned Line, unsigned Col, MDNode *CU);
   SDValue getLabel(unsigned Opcode, DebugLoc dl, SDValue Root,
                    unsigned LabelID);
+  SDValue getBlockAddress(BlockAddress *BA, DebugLoc dl,
+                          bool isTarget = false);
 
   SDValue getCopyToReg(SDValue Chain, DebugLoc dl, unsigned Reg, SDValue N) {
     return getNode(ISD::CopyToReg, dl, MVT::Other, Chain,
diff --git a/include/llvm/CodeGen/SelectionDAGISel.h b/include/llvm/CodeGen/SelectionDAGISel.h
index 2b713f1..5d33224 100644
--- a/include/llvm/CodeGen/SelectionDAGISel.h
+++ b/include/llvm/CodeGen/SelectionDAGISel.h
@@ -110,6 +110,14 @@ protected:
   bool CheckOrMask(SDValue LHS, ConstantSDNode *RHS,
                     int64_t DesiredMaskS) const;
   
+  // Calls to these functions are generated by tblgen.
+  SDNode *Select_INLINEASM(SDValue N);
+  SDNode *Select_UNDEF(const SDValue &N);
+  SDNode *Select_DBG_LABEL(const SDValue &N);
+  SDNode *Select_EH_LABEL(const SDValue &N);
+  void CannotYetSelect(SDValue N);
+  void CannotYetSelectIntrinsic(SDValue N);
+
 private:
   void SelectAllBasicBlocks(Function &Fn, MachineFunction &MF,
                             MachineModuleInfo *MMI,
diff --git a/include/llvm/CodeGen/SelectionDAGNodes.h b/include/llvm/CodeGen/SelectionDAGNodes.h
index d7c8f1c..f960851 100644
--- a/include/llvm/CodeGen/SelectionDAGNodes.h
+++ b/include/llvm/CodeGen/SelectionDAGNodes.h
@@ -28,7 +28,7 @@
 #include "llvm/CodeGen/ValueTypes.h"
 #include "llvm/CodeGen/MachineMemOperand.h"
 #include "llvm/Support/MathExtras.h"
-#include "llvm/Support/DataTypes.h"
+#include "llvm/System/DataTypes.h"
 #include "llvm/Support/DebugLoc.h"
 #include <cassert>
 
@@ -97,7 +97,7 @@ namespace ISD {
     BasicBlock, VALUETYPE, CONDCODE, Register,
     Constant, ConstantFP,
     GlobalAddress, GlobalTLSAddress, FrameIndex,
-    JumpTable, ConstantPool, ExternalSymbol,
+    JumpTable, ConstantPool, ExternalSymbol, BlockAddress,
 
     // The address of the GOT
     GLOBAL_OFFSET_TABLE,
@@ -146,6 +146,7 @@ namespace ISD {
     TargetJumpTable,
     TargetConstantPool,
     TargetExternalSymbol,
+    TargetBlockAddress,
 
     /// RESULT = INTRINSIC_WO_CHAIN(INTRINSICID, arg1, arg2, ...)
     /// This node represents a target intrinsic function with no side effects.
@@ -2026,11 +2027,27 @@ public:
   }
 };
 
+class BlockAddressSDNode : public SDNode {
+  BlockAddress *BA;
+  friend class SelectionDAG;
+  BlockAddressSDNode(unsigned NodeTy, DebugLoc dl, EVT VT, BlockAddress *ba)
+    : SDNode(NodeTy, dl, getSDVTList(VT)), BA(ba) {
+  }
+public:
+  BlockAddress *getBlockAddress() const { return BA; }
+
+  static bool classof(const BlockAddressSDNode *) { return true; }
+  static bool classof(const SDNode *N) {
+    return N->getOpcode() == ISD::BlockAddress ||
+           N->getOpcode() == ISD::TargetBlockAddress;
+  }
+};
+
 class LabelSDNode : public SDNode {
   SDUse Chain;
   unsigned LabelID;
   friend class SelectionDAG;
-LabelSDNode(unsigned NodeTy, DebugLoc dl, SDValue ch, unsigned id)
+  LabelSDNode(unsigned NodeTy, DebugLoc dl, SDValue ch, unsigned id)
     : SDNode(NodeTy, dl, getSDVTList(MVT::Other)), LabelID(id) {
     InitOperands(&Chain, ch);
   }
diff --git a/include/llvm/CodeGen/SlotIndexes.h b/include/llvm/CodeGen/SlotIndexes.h
new file mode 100644
index 0000000..3f175a7
--- /dev/null
+++ b/include/llvm/CodeGen/SlotIndexes.h
@@ -0,0 +1,740 @@
+//===- llvm/CodeGen/SlotIndexes.h - Slot indexes representation -*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file implements SlotIndex and related classes. The purpuse of SlotIndex
+// is to describe a position at which a register can become live, or cease to
+// be live.
+//
+// SlotIndex is mostly a proxy for entries of the SlotIndexList, a class which
+// is held is LiveIntervals and provides the real numbering. This allows
+// LiveIntervals to perform largely transparent renumbering. The SlotIndex
+// class does hold a PHI bit, which determines whether the index relates to a
+// PHI use or def point, or an actual instruction. See the SlotIndex class
+// description for futher information.
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CODEGEN_SLOTINDEXES_H
+#define LLVM_CODEGEN_SLOTINDEXES_H
+
+#include "llvm/ADT/PointerIntPair.h"
+#include "llvm/ADT/SmallVector.h"
+#include "llvm/CodeGen/MachineBasicBlock.h"
+#include "llvm/CodeGen/MachineFunctionPass.h"
+#include "llvm/CodeGen/MachineInstr.h"
+#include "llvm/Support/Allocator.h"
+
+namespace llvm {
+
+  /// This class represents an entry in the slot index list held in the
+  /// SlotIndexes pass. It should not be used directly. See the
+  /// SlotIndex & SlotIndexes classes for the public interface to this
+  /// information.
+  class IndexListEntry {
+  private:
+
+    IndexListEntry *next, *prev;
+    MachineInstr *mi;
+    unsigned index;
+
+  public:
+
+    IndexListEntry(MachineInstr *mi, unsigned index)
+      : mi(mi), index(index) {}
+
+    MachineInstr* getInstr() const { return mi; }
+    void setInstr(MachineInstr *mi) { this->mi = mi; }
+
+    unsigned getIndex() const { return index; }
+    void setIndex(unsigned index) { this->index = index; }
+    
+    IndexListEntry* getNext() { return next; }
+    const IndexListEntry* getNext() const { return next; }
+    void setNext(IndexListEntry *next) { this->next = next; }
+
+    IndexListEntry* getPrev() { return prev; }
+    const IndexListEntry* getPrev() const { return prev; }
+    void setPrev(IndexListEntry *prev) { this->prev = prev; }
+  };
+
+  // Specialize PointerLikeTypeTraits for IndexListEntry.
+  template <>
+  class PointerLikeTypeTraits<IndexListEntry*> { 
+  public:
+    static inline void* getAsVoidPointer(IndexListEntry *p) {
+      return p;
+    }
+    static inline IndexListEntry* getFromVoidPointer(void *p) {
+      return static_cast<IndexListEntry*>(p);
+    }
+    enum { NumLowBitsAvailable = 3 };
+  };
+
+  /// SlotIndex - An opaque wrapper around machine indexes.
+  class SlotIndex {
+    friend class SlotIndexes;
+    friend class DenseMapInfo<SlotIndex>;
+
+  private:
+
+    // FIXME: Is there any way to statically allocate these things and have
+    // them 8-byte aligned?
+    static std::auto_ptr<IndexListEntry> emptyKeyPtr, tombstoneKeyPtr;
+    static const unsigned PHI_BIT = 1 << 2;
+
+    PointerIntPair<IndexListEntry*, 3, unsigned> lie;
+
+    SlotIndex(IndexListEntry *entry, unsigned phiAndSlot)
+      : lie(entry, phiAndSlot) {
+      assert(entry != 0 && "Attempt to construct index with 0 pointer.");
+    }
+
+    IndexListEntry& entry() const {
+      assert(lie.getPointer() != 0 && "Use of invalid index.");
+      return *lie.getPointer();
+    }
+
+    int getIndex() const {
+      return entry().getIndex() | getSlot();
+    }
+
+    static inline unsigned getHashValue(const SlotIndex &v) {
+      IndexListEntry *ptrVal = &v.entry();
+      return (unsigned((intptr_t)ptrVal) >> 4) ^
+             (unsigned((intptr_t)ptrVal) >> 9);
+    }
+
+  public:
+
+    // FIXME: Ugh. This is public because LiveIntervalAnalysis is still using it
+    // for some spill weight stuff. Fix that, then make this private.
+    enum Slot { LOAD, USE, DEF, STORE, NUM };
+
+    static inline SlotIndex getEmptyKey() {
+      // FIXME: How do we guarantee these numbers don't get allocated to
+      // legit indexes?
+      if (emptyKeyPtr.get() == 0)
+        emptyKeyPtr.reset(new IndexListEntry(0, ~0U & ~3U));
+
+      return SlotIndex(emptyKeyPtr.get(), 0);
+    }
+
+    static inline SlotIndex getTombstoneKey() {
+      // FIXME: How do we guarantee these numbers don't get allocated to
+      // legit indexes?
+      if (tombstoneKeyPtr.get() == 0)
+        tombstoneKeyPtr.reset(new IndexListEntry(0, ~0U & ~7U));
+
+      return SlotIndex(tombstoneKeyPtr.get(), 0);
+    }
+    
+    /// Construct an invalid index.
+    SlotIndex() : lie(&getEmptyKey().entry(), 0) {}
+
+    // Construct a new slot index from the given one, set the phi flag on the
+    // new index to the value of the phi parameter.
+    SlotIndex(const SlotIndex &li, bool phi)
+      : lie(&li.entry(), phi ? PHI_BIT & li.getSlot() : (unsigned)li.getSlot()){
+      assert(lie.getPointer() != 0 &&
+             "Attempt to construct index with 0 pointer.");
+    }
+
+    // Construct a new slot index from the given one, set the phi flag on the
+    // new index to the value of the phi parameter, and the slot to the new slot.
+    SlotIndex(const SlotIndex &li, bool phi, Slot s)
+      : lie(&li.entry(), phi ? PHI_BIT & s : (unsigned)s) {
+      assert(lie.getPointer() != 0 &&
+             "Attempt to construct index with 0 pointer.");
+    }
+
+    /// Returns true if this is a valid index. Invalid indicies do
+    /// not point into an index table, and cannot be compared.
+    bool isValid() const {
+      return (lie.getPointer() != 0) && (lie.getPointer()->getIndex() != 0);
+    }
+
+    /// Print this index to the given raw_ostream.
+    void print(raw_ostream &os) const;
+
+    /// Dump this index to stderr.
+    void dump() const;
+
+    /// Compare two SlotIndex objects for equality.
+    bool operator==(SlotIndex other) const {
+      return getIndex() == other.getIndex();
+    }
+    /// Compare two SlotIndex objects for inequality.
+    bool operator!=(SlotIndex other) const {
+      return getIndex() != other.getIndex(); 
+    }
+   
+    /// Compare two SlotIndex objects. Return true if the first index
+    /// is strictly lower than the second.
+    bool operator<(SlotIndex other) const {
+      return getIndex() < other.getIndex();
+    }
+    /// Compare two SlotIndex objects. Return true if the first index
+    /// is lower than, or equal to, the second.
+    bool operator<=(SlotIndex other) const {
+      return getIndex() <= other.getIndex();
+    }
+
+    /// Compare two SlotIndex objects. Return true if the first index
+    /// is greater than the second.
+    bool operator>(SlotIndex other) const {
+      return getIndex() > other.getIndex();
+    }
+
+    /// Compare two SlotIndex objects. Return true if the first index
+    /// is greater than, or equal to, the second.
+    bool operator>=(SlotIndex other) const {
+      return getIndex() >= other.getIndex();
+    }
+
+    /// Return the distance from this index to the given one.
+    int distance(SlotIndex other) const {
+      return other.getIndex() - getIndex();
+    }
+
+    /// Returns the slot for this SlotIndex.
+    Slot getSlot() const {
+      return static_cast<Slot>(lie.getInt()  & ~PHI_BIT);
+    }
+
+    /// Returns the state of the PHI bit.
+    bool isPHI() const {
+      return lie.getInt() & PHI_BIT;
+    }
+
+    /// Returns the base index for associated with this index. The base index
+    /// is the one associated with the LOAD slot for the instruction pointed to
+    /// by this index.
+    SlotIndex getBaseIndex() const {
+      return getLoadIndex();
+    }
+
+    /// Returns the boundary index for associated with this index. The boundary
+    /// index is the one associated with the LOAD slot for the instruction
+    /// pointed to by this index.
+    SlotIndex getBoundaryIndex() const {
+      return getStoreIndex();
+    }
+
+    /// Returns the index of the LOAD slot for the instruction pointed to by
+    /// this index.
+    SlotIndex getLoadIndex() const {
+      return SlotIndex(&entry(), SlotIndex::LOAD);
+    }    
+
+    /// Returns the index of the USE slot for the instruction pointed to by
+    /// this index.
+    SlotIndex getUseIndex() const {
+      return SlotIndex(&entry(), SlotIndex::USE);
+    }
+
+    /// Returns the index of the DEF slot for the instruction pointed to by
+    /// this index.
+    SlotIndex getDefIndex() const {
+      return SlotIndex(&entry(), SlotIndex::DEF);
+    }
+
+    /// Returns the index of the STORE slot for the instruction pointed to by
+    /// this index.
+    SlotIndex getStoreIndex() const {
+      return SlotIndex(&entry(), SlotIndex::STORE);
+    }    
+
+    /// Returns the next slot in the index list. This could be either the
+    /// next slot for the instruction pointed to by this index or, if this
+    /// index is a STORE, the first slot for the next instruction.
+    /// WARNING: This method is considerably more expensive than the methods
+    /// that return specific slots (getUseIndex(), etc). If you can - please
+    /// use one of those methods.
+    SlotIndex getNextSlot() const {
+      Slot s = getSlot();
+      if (s == SlotIndex::STORE) {
+        return SlotIndex(entry().getNext(), SlotIndex::LOAD);
+      }
+      return SlotIndex(&entry(), s + 1);
+    }
+
+    /// Returns the next index. This is the index corresponding to the this
+    /// index's slot, but for the next instruction.
+    SlotIndex getNextIndex() const {
+      return SlotIndex(entry().getNext(), getSlot());
+    }
+
+    /// Returns the previous slot in the index list. This could be either the
+    /// previous slot for the instruction pointed to by this index or, if this
+    /// index is a LOAD, the last slot for the previous instruction.
+    /// WARNING: This method is considerably more expensive than the methods
+    /// that return specific slots (getUseIndex(), etc). If you can - please
+    /// use one of those methods.
+    SlotIndex getPrevSlot() const {
+      Slot s = getSlot();
+      if (s == SlotIndex::LOAD) {
+        return SlotIndex(entry().getPrev(), SlotIndex::STORE);
+      }
+      return SlotIndex(&entry(), s - 1);
+    }
+
+    /// Returns the previous index. This is the index corresponding to this
+    /// index's slot, but for the previous instruction.
+    SlotIndex getPrevIndex() const {
+      return SlotIndex(entry().getPrev(), getSlot());
+    }
+
+  };
+
+  /// DenseMapInfo specialization for SlotIndex.
+  template <>
+  struct DenseMapInfo<SlotIndex> {
+    static inline SlotIndex getEmptyKey() {
+      return SlotIndex::getEmptyKey();
+    }
+    static inline SlotIndex getTombstoneKey() {
+      return SlotIndex::getTombstoneKey();
+    }
+    static inline unsigned getHashValue(const SlotIndex &v) {
+      return SlotIndex::getHashValue(v);
+    }
+    static inline bool isEqual(const SlotIndex &LHS, const SlotIndex &RHS) {
+      return (LHS == RHS);
+    }
+    static inline bool isPod() { return false; }
+  };
+
+  inline raw_ostream& operator<<(raw_ostream &os, SlotIndex li) {
+    li.print(os);
+    return os;
+  }
+
+  typedef std::pair<SlotIndex, MachineBasicBlock*> IdxMBBPair;
+
+  inline bool operator<(SlotIndex V, const IdxMBBPair &IM) {
+    return V < IM.first;
+  }
+
+  inline bool operator<(const IdxMBBPair &IM, SlotIndex V) {
+    return IM.first < V;
+  }
+
+  struct Idx2MBBCompare {
+    bool operator()(const IdxMBBPair &LHS, const IdxMBBPair &RHS) const {
+      return LHS.first < RHS.first;
+    }
+  };
+
+  /// SlotIndexes pass.
+  ///
+  /// This pass assigns indexes to each instruction.
+  class SlotIndexes : public MachineFunctionPass {
+  private:
+
+    MachineFunction *mf;
+    IndexListEntry *indexListHead;
+    unsigned functionSize;
+
+    typedef DenseMap<const MachineInstr*, SlotIndex> Mi2IndexMap;
+    Mi2IndexMap mi2iMap;
+
+    /// MBB2IdxMap - The indexes of the first and last instructions in the
+    /// specified basic block.
+    typedef DenseMap<const MachineBasicBlock*,
+                     std::pair<SlotIndex, SlotIndex> > MBB2IdxMap;
+    MBB2IdxMap mbb2IdxMap;
+
+    /// Idx2MBBMap - Sorted list of pairs of index of first instruction
+    /// and MBB id.
+    std::vector<IdxMBBPair> idx2MBBMap;
+
+    typedef DenseMap<const MachineBasicBlock*, SlotIndex> TerminatorGapsMap;
+    TerminatorGapsMap terminatorGaps;
+
+    // IndexListEntry allocator.
+    BumpPtrAllocator ileAllocator;
+
+    IndexListEntry* createEntry(MachineInstr *mi, unsigned index) {
+      IndexListEntry *entry =
+        static_cast<IndexListEntry*>(
+          ileAllocator.Allocate(sizeof(IndexListEntry),
+          alignof<IndexListEntry>()));
+
+      new (entry) IndexListEntry(mi, index);
+
+      return entry;
+    }
+
+    void initList() {
+      assert(indexListHead == 0 && "Zero entry non-null at initialisation.");
+      indexListHead = createEntry(0, ~0U);
+      indexListHead->setNext(0);
+      indexListHead->setPrev(indexListHead);
+    }
+
+    void clearList() {
+      indexListHead = 0;
+      ileAllocator.Reset();
+    }
+
+    IndexListEntry* getTail() {
+      assert(indexListHead != 0 && "Call to getTail on uninitialized list.");
+      return indexListHead->getPrev();
+    }
+
+    const IndexListEntry* getTail() const {
+      assert(indexListHead != 0 && "Call to getTail on uninitialized list.");
+      return indexListHead->getPrev();
+    }
+
+    // Returns true if the index list is empty.
+    bool empty() const { return (indexListHead == getTail()); }
+
+    IndexListEntry* front() {
+      assert(!empty() && "front() called on empty index list.");
+      return indexListHead;
+    }
+
+    const IndexListEntry* front() const {
+      assert(!empty() && "front() called on empty index list.");
+      return indexListHead;
+    }
+
+    IndexListEntry* back() {
+      assert(!empty() && "back() called on empty index list.");
+      return getTail()->getPrev();
+    }
+
+    const IndexListEntry* back() const {
+      assert(!empty() && "back() called on empty index list.");
+      return getTail()->getPrev();
+    }
+
+    /// Insert a new entry before itr.
+    void insert(IndexListEntry *itr, IndexListEntry *val) {
+      assert(itr != 0 && "itr should not be null.");
+      IndexListEntry *prev = itr->getPrev();
+      val->setNext(itr);
+      val->setPrev(prev);
+      
+      if (itr != indexListHead) {
+        prev->setNext(val);
+      }
+      else {
+        indexListHead = val;
+      }
+      itr->setPrev(val);
+    }
+
+    /// Push a new entry on to the end of the list.
+    void push_back(IndexListEntry *val) {
+      insert(getTail(), val);
+    }
+
+  public:
+    static char ID;
+
+    SlotIndexes() : MachineFunctionPass(&ID), indexListHead(0) {}
+
+    virtual void getAnalysisUsage(AnalysisUsage &au) const;
+    virtual void releaseMemory(); 
+
+    virtual bool runOnMachineFunction(MachineFunction &fn);
+
+    /// Dump the indexes.
+    void dump() const;
+
+    /// Renumber the index list, providing space for new instructions.
+    void renumber();
+
+    /// Returns the zero index for this analysis.
+    SlotIndex getZeroIndex() {
+      assert(front()->getIndex() == 0 && "First index is not 0?");
+      return SlotIndex(front(), 0);
+    }
+
+    /// Returns the invalid index marker for this analysis.
+    SlotIndex getInvalidIndex() {
+      return getZeroIndex();
+    }
+
+    /// Returns the distance between the highest and lowest indexes allocated
+    /// so far.
+    unsigned getIndexesLength() const {
+      assert(front()->getIndex() == 0 &&
+             "Initial index isn't zero?");
+
+      return back()->getIndex();
+    }
+
+    /// Returns the number of instructions in the function.
+    unsigned getFunctionSize() const {
+      return functionSize;
+    }
+
+    /// Returns true if the given machine instr is mapped to an index,
+    /// otherwise returns false.
+    bool hasIndex(const MachineInstr *instr) const {
+      return (mi2iMap.find(instr) != mi2iMap.end());
+    }
+
+    /// Returns the base index for the given instruction.
+    SlotIndex getInstructionIndex(const MachineInstr *instr) const {
+      Mi2IndexMap::const_iterator itr = mi2iMap.find(instr);
+      assert(itr != mi2iMap.end() && "Instruction not found in maps.");
+      return itr->second;
+    }
+
+    /// Returns the instruction for the given index, or null if the given
+    /// index has no instruction associated with it.
+    MachineInstr* getInstructionFromIndex(SlotIndex index) const {
+      return index.entry().getInstr();
+    }
+
+    /// Returns the next non-null index.
+    SlotIndex getNextNonNullIndex(SlotIndex index) {
+      SlotIndex nextNonNull = index.getNextIndex();
+
+      while (&nextNonNull.entry() != getTail() &&
+             getInstructionFromIndex(nextNonNull) == 0) {
+        nextNonNull = nextNonNull.getNextIndex();
+      }
+
+      return nextNonNull;
+    }
+
+    /// Returns the first index in the given basic block.
+    SlotIndex getMBBStartIdx(const MachineBasicBlock *mbb) const {
+      MBB2IdxMap::const_iterator itr = mbb2IdxMap.find(mbb);
+      assert(itr != mbb2IdxMap.end() && "MBB not found in maps.");
+      return itr->second.first;
+    }
+
+    /// Returns the last index in the given basic block.
+    SlotIndex getMBBEndIdx(const MachineBasicBlock *mbb) const {
+      MBB2IdxMap::const_iterator itr = mbb2IdxMap.find(mbb);
+      assert(itr != mbb2IdxMap.end() && "MBB not found in maps.");
+      return itr->second.second;
+    }
+
+    /// Returns the terminator gap for the given index.
+    SlotIndex getTerminatorGap(const MachineBasicBlock *mbb) {
+      TerminatorGapsMap::iterator itr = terminatorGaps.find(mbb);
+      assert(itr != terminatorGaps.end() &&
+             "All MBBs should have terminator gaps in their indexes.");
+      return itr->second;
+    }
+
+    /// Returns the basic block which the given index falls in.
+    MachineBasicBlock* getMBBFromIndex(SlotIndex index) const {
+      std::vector<IdxMBBPair>::const_iterator I =
+        std::lower_bound(idx2MBBMap.begin(), idx2MBBMap.end(), index);
+      // Take the pair containing the index
+      std::vector<IdxMBBPair>::const_iterator J =
+        ((I != idx2MBBMap.end() && I->first > index) ||
+         (I == idx2MBBMap.end() && idx2MBBMap.size()>0)) ? (I-1): I;
+
+      assert(J != idx2MBBMap.end() && J->first <= index &&
+             index <= getMBBEndIdx(J->second) &&
+             "index does not correspond to an MBB");
+      return J->second;
+    }
+
+    bool findLiveInMBBs(SlotIndex start, SlotIndex end,
+                        SmallVectorImpl<MachineBasicBlock*> &mbbs) const {
+      std::vector<IdxMBBPair>::const_iterator itr =
+        std::lower_bound(idx2MBBMap.begin(), idx2MBBMap.end(), start);
+      bool resVal = false;
+
+      while (itr != idx2MBBMap.end()) {
+        if (itr->first >= end)
+          break;
+        mbbs.push_back(itr->second);
+        resVal = true;
+        ++itr;
+      }
+      return resVal;
+    }
+
+    /// Return a list of MBBs that can be reach via any branches or
+    /// fall-throughs.
+    bool findReachableMBBs(SlotIndex start, SlotIndex end,
+                           SmallVectorImpl<MachineBasicBlock*> &mbbs) const {
+      std::vector<IdxMBBPair>::const_iterator itr =
+        std::lower_bound(idx2MBBMap.begin(), idx2MBBMap.end(), start);
+
+      bool resVal = false;
+      while (itr != idx2MBBMap.end()) {
+        if (itr->first > end)
+          break;
+        MachineBasicBlock *mbb = itr->second;
+        if (getMBBEndIdx(mbb) > end)
+          break;
+        for (MachineBasicBlock::succ_iterator si = mbb->succ_begin(),
+             se = mbb->succ_end(); si != se; ++si)
+          mbbs.push_back(*si);
+        resVal = true;
+        ++itr;
+      }
+      return resVal;
+    }
+
+    /// Returns the MBB covering the given range, or null if the range covers
+    /// more than one basic block.
+    MachineBasicBlock* getMBBCoveringRange(SlotIndex start, SlotIndex end) const {
+
+      assert(start < end && "Backwards ranges not allowed.");
+
+      std::vector<IdxMBBPair>::const_iterator itr =
+        std::lower_bound(idx2MBBMap.begin(), idx2MBBMap.end(), start);
+
+      if (itr == idx2MBBMap.end()) {
+        itr = prior(itr);
+        return itr->second;
+      }
+
+      // Check that we don't cross the boundary into this block.
+      if (itr->first < end)
+        return 0;
+
+      itr = prior(itr);
+
+      if (itr->first <= start)
+        return itr->second;
+
+      return 0;
+    }
+
+    /// Returns true if there is a gap in the numbering before the given index.
+    bool hasGapBeforeInstr(SlotIndex index) {
+      index = index.getBaseIndex();
+      SlotIndex prevIndex = index.getPrevIndex();
+      
+      if (prevIndex == getZeroIndex())
+        return false;
+
+      if (getInstructionFromIndex(prevIndex) == 0)
+        return true;
+
+      if (prevIndex.distance(index) >= 2 * SlotIndex::NUM)
+        return true;
+
+      return false;
+    }
+
+    /// Returns true if there is a gap in the numbering after the given index.
+    bool hasGapAfterInstr(SlotIndex index) const {
+      // Not implemented yet.
+      assert(false &&
+             "SlotIndexes::hasGapAfterInstr(SlotIndex) not implemented yet.");
+      return false;
+    }
+
+    /// findGapBeforeInstr - Find an empty instruction slot before the
+    /// specified index. If "Furthest" is true, find one that's furthest
+    /// away from the index (but before any index that's occupied).
+    // FIXME: This whole method should go away in future. It should
+    // always be possible to insert code between existing indices.
+    SlotIndex findGapBeforeInstr(SlotIndex index, bool furthest = false) {
+      if (index == getZeroIndex())
+        return getInvalidIndex();
+
+      index = index.getBaseIndex();
+      SlotIndex prevIndex = index.getPrevIndex();
+
+      if (prevIndex == getZeroIndex())
+        return getInvalidIndex();
+
+      // Try to reuse existing index objects with null-instrs.
+      if (getInstructionFromIndex(prevIndex) == 0) {
+        if (furthest) {
+          while (getInstructionFromIndex(prevIndex) == 0 &&
+                 prevIndex != getZeroIndex()) {
+            prevIndex = prevIndex.getPrevIndex();
+          }
+
+          prevIndex = prevIndex.getNextIndex();
+        }
+ 
+        assert(getInstructionFromIndex(prevIndex) == 0 && "Index list is broken.");
+
+        return prevIndex;
+      }
+
+      int dist = prevIndex.distance(index);
+
+      // Double check that the spacing between this instruction and
+      // the last is sane.
+      assert(dist >= SlotIndex::NUM &&
+             "Distance between indexes too small.");
+
+      // If there's no gap return an invalid index.
+      if (dist < 2*SlotIndex::NUM) {
+        return getInvalidIndex();
+      }
+
+      // Otherwise insert new index entries into the list using the
+      // gap in the numbering.
+      IndexListEntry *newEntry =
+        createEntry(0, prevIndex.entry().getIndex() + SlotIndex::NUM);
+
+      insert(&index.entry(), newEntry);
+
+      // And return a pointer to the entry at the start of the gap.
+      return index.getPrevIndex();
+    }
+
+    /// Insert the given machine instruction into the mapping at the given
+    /// index.
+    void insertMachineInstrInMaps(MachineInstr *mi, SlotIndex index) {
+      index = index.getBaseIndex();
+      IndexListEntry *miEntry = &index.entry();
+      assert(miEntry->getInstr() == 0 && "Index already in use.");
+      miEntry->setInstr(mi);
+
+      assert(mi2iMap.find(mi) == mi2iMap.end() &&
+             "MachineInstr already has an index.");
+
+      mi2iMap.insert(std::make_pair(mi, index));
+    }
+
+    /// Remove the given machine instruction from the mapping.
+    void removeMachineInstrFromMaps(MachineInstr *mi) {
+      // remove index -> MachineInstr and
+      // MachineInstr -> index mappings
+      Mi2IndexMap::iterator mi2iItr = mi2iMap.find(mi);
+      if (mi2iItr != mi2iMap.end()) {
+        IndexListEntry *miEntry(&mi2iItr->second.entry());        
+        assert(miEntry->getInstr() == mi && "Instruction indexes broken.");
+        // FIXME: Eventually we want to actually delete these indexes.
+        miEntry->setInstr(0);
+        mi2iMap.erase(mi2iItr);
+      }
+    }
+
+    /// ReplaceMachineInstrInMaps - Replacing a machine instr with a new one in
+    /// maps used by register allocator.
+    void replaceMachineInstrInMaps(MachineInstr *mi, MachineInstr *newMI) {
+      Mi2IndexMap::iterator mi2iItr = mi2iMap.find(mi);
+      if (mi2iItr == mi2iMap.end())
+        return;
+      SlotIndex replaceBaseIndex = mi2iItr->second;
+      IndexListEntry *miEntry(&replaceBaseIndex.entry());
+      assert(miEntry->getInstr() == mi &&
+             "Mismatched instruction in index tables.");
+      miEntry->setInstr(newMI);
+      mi2iMap.erase(mi2iItr);
+      mi2iMap.insert(std::make_pair(newMI, replaceBaseIndex));
+    }
+
+  };
+
+
+}
+
+#endif // LLVM_CODEGEN_LIVEINDEX_H 
diff --git a/include/llvm/CodeGen/ValueTypes.h b/include/llvm/CodeGen/ValueTypes.h
index 1f0dd21..45ef9b9 100644
--- a/include/llvm/CodeGen/ValueTypes.h
+++ b/include/llvm/CodeGen/ValueTypes.h
@@ -18,7 +18,7 @@
 
 #include <cassert>
 #include <string>
-#include "llvm/Support/DataTypes.h"
+#include "llvm/System/DataTypes.h"
 #include "llvm/Support/MathExtras.h"
 
 namespace llvm {
diff --git a/include/llvm/Constant.h b/include/llvm/Constant.h
index a42c7d4..8072fd9 100644
--- a/include/llvm/Constant.h
+++ b/include/llvm/Constant.h
@@ -48,6 +48,10 @@ protected:
     : User(ty, vty, Ops, NumOps) {}
 
   void destroyConstantImpl();
+  
+  void setOperand(unsigned i, Value *V) {
+    User::setOperand(i, V);
+  }
 public:
   /// isNullValue - Return true if this is the value that would be returned by
   /// getNullValue.
@@ -61,6 +65,10 @@ public:
   /// true for things like constant expressions that could divide by zero.
   bool canTrap() const;
 
+  /// isConstantUsed - Return true if the constant has users other than constant
+  /// exprs and other dangling things.
+  bool isConstantUsed() const;
+  
   enum PossibleRelocationsTy {
     NoRelocation = 0,
     LocalRelocation = 1,
@@ -83,16 +91,13 @@ public:
   /// FIXME: This really should not be in VMCore.
   PossibleRelocationsTy getRelocationInfo() const;
   
-  // Specialize get/setOperand for Constants as their operands are always
-  // constants as well.
-  Constant *getOperand(unsigned i) {
-    return static_cast<Constant*>(User::getOperand(i));
-  }
-  const Constant *getOperand(unsigned i) const {
-    return static_cast<const Constant*>(User::getOperand(i));
+  // Specialize get/setOperand for Users as their operands are always
+  // constants or BasicBlocks as well.
+  User *getOperand(unsigned i) {
+    return static_cast<User*>(User::getOperand(i));
   }
-  void setOperand(unsigned i, Constant *C) {
-    User::setOperand(i, C);
+  const User *getOperand(unsigned i) const {
+    return static_cast<const User*>(User::getOperand(i));
   }
   
   /// getVectorElements - This method, which is only valid on constant of vector
diff --git a/include/llvm/Constants.h b/include/llvm/Constants.h
index 2855fdc..99928d9 100644
--- a/include/llvm/Constants.h
+++ b/include/llvm/Constants.h
@@ -549,7 +549,47 @@ public:
   }
 };
 
+/// BlockAddress - The address of a basic block.
+///
+class BlockAddress : public Constant {
+  void *operator new(size_t, unsigned);                  // DO NOT IMPLEMENT
+  void *operator new(size_t s) { return User::operator new(s, 2); }
+  BlockAddress(Function *F, BasicBlock *BB);
+public:
+  /// get - Return a BlockAddress for the specified function and basic block.
+  static BlockAddress *get(Function *F, BasicBlock *BB);
+  
+  /// get - Return a BlockAddress for the specified basic block.  The basic
+  /// block must be embedded into a function.
+  static BlockAddress *get(BasicBlock *BB);
+  
+  /// Transparently provide more efficient getOperand methods.
+  DECLARE_TRANSPARENT_OPERAND_ACCESSORS(Value);
+  
+  Function *getFunction() const { return (Function*)Op<0>().get(); }
+  BasicBlock *getBasicBlock() const { return (BasicBlock*)Op<1>().get(); }
+  
+  /// isNullValue - Return true if this is the value that would be returned by
+  /// getNullValue.
+  virtual bool isNullValue() const { return false; }
+  
+  virtual void destroyConstant();
+  virtual void replaceUsesOfWithOnConstant(Value *From, Value *To, Use *U);
+  
+  /// Methods for support type inquiry through isa, cast, and dyn_cast:
+  static inline bool classof(const BlockAddress *) { return true; }
+  static inline bool classof(const Value *V) {
+    return V->getValueID() == BlockAddressVal;
+  }
+};
+
+template <>
+struct OperandTraits<BlockAddress> : public FixedNumOperandTraits<2> {
+};
 
+DEFINE_TRANSPARENT_CASTED_OPERAND_ACCESSORS(BlockAddress, Value)
+  
+//===----------------------------------------------------------------------===//
 /// ConstantExpr - a constant value that is initialized with an expression using
 /// other constant values.
 ///
diff --git a/include/llvm/ExecutionEngine/ExecutionEngine.h b/include/llvm/ExecutionEngine/ExecutionEngine.h
index b9da0fc..4b828e46 100644
--- a/include/llvm/ExecutionEngine/ExecutionEngine.h
+++ b/include/llvm/ExecutionEngine/ExecutionEngine.h
@@ -19,6 +19,7 @@
 #include <map>
 #include <string>
 #include "llvm/ADT/SmallVector.h"
+#include "llvm/ADT/ValueMap.h"
 #include "llvm/Support/ValueHandle.h"
 #include "llvm/System/Mutex.h"
 #include "llvm/Target/TargetMachine.h"
@@ -42,26 +43,23 @@ class Type;
 
 class ExecutionEngineState {
 public:
-  class MapUpdatingCVH : public CallbackVH {
-    ExecutionEngineState &EES;
-
-  public:
-    MapUpdatingCVH(ExecutionEngineState &EES, const GlobalValue *GV);
-
-    operator const GlobalValue*() const {
-      return cast<GlobalValue>(getValPtr());
-    }
-
-    virtual void deleted();
-    virtual void allUsesReplacedWith(Value *new_value);
+  struct AddressMapConfig : public ValueMapConfig<const GlobalValue*> {
+    typedef ExecutionEngineState *ExtraData;
+    static sys::Mutex *getMutex(ExecutionEngineState *EES);
+    static void onDelete(ExecutionEngineState *EES, const GlobalValue *Old);
+    static void onRAUW(ExecutionEngineState *, const GlobalValue *,
+                       const GlobalValue *);
   };
 
+  typedef ValueMap<const GlobalValue *, void *, AddressMapConfig>
+      GlobalAddressMapTy;
+
 private:
   ExecutionEngine &EE;
 
   /// GlobalAddressMap - A mapping between LLVM global values and their
   /// actualized version...
-  std::map<MapUpdatingCVH, void *> GlobalAddressMap;
+  GlobalAddressMapTy GlobalAddressMap;
 
   /// GlobalAddressReverseMap - This is the reverse mapping of GlobalAddressMap,
   /// used to convert raw addresses into the LLVM global value that is emitted
@@ -70,13 +68,9 @@ private:
   std::map<void *, AssertingVH<const GlobalValue> > GlobalAddressReverseMap;
 
 public:
-  ExecutionEngineState(ExecutionEngine &EE) : EE(EE) {}
+  ExecutionEngineState(ExecutionEngine &EE);
 
-  MapUpdatingCVH getVH(const GlobalValue *GV) {
-    return MapUpdatingCVH(*this, GV);
-  }
-
-  std::map<MapUpdatingCVH, void *> &
+  GlobalAddressMapTy &
   getGlobalAddressMap(const MutexGuard &) {
     return GlobalAddressMap;
   }
@@ -94,7 +88,7 @@ public:
 class ExecutionEngine {
   const TargetData *TD;
   ExecutionEngineState EEState;
-  bool LazyCompilationDisabled;
+  bool CompilingLazily;
   bool GVCompilationDisabled;
   bool SymbolSearchingDisabled;
   bool DlsymStubsEnabled;
@@ -269,12 +263,17 @@ public:
   /// getPointerToFunction - The different EE's represent function bodies in
   /// different ways.  They should each implement this to say what a function
   /// pointer should look like.  When F is destroyed, the ExecutionEngine will
-  /// remove its global mapping but will not yet free its machine code.  Call
-  /// freeMachineCodeForFunction(F) explicitly to do that.  Note that global
-  /// optimizations can destroy Functions without notifying the ExecutionEngine.
+  /// remove its global mapping and free any machine code.  Be sure no threads
+  /// are running inside F when that happens.
   ///
   virtual void *getPointerToFunction(Function *F) = 0;
 
+  /// getPointerToBasicBlock - The different EE's represent basic blocks in
+  /// different ways.  Return the representation for a blockaddress of the
+  /// specified block.
+  ///
+  virtual void *getPointerToBasicBlock(BasicBlock *BB) = 0;
+  
   /// getPointerToFunctionOrStub - If the specified function has been
   /// code-gen'd, return a pointer to the function.  If not, compile it, or use
   /// a stub to implement lazy compilation if available.  See
@@ -326,13 +325,29 @@ public:
   virtual void RegisterJITEventListener(JITEventListener *) {}
   virtual void UnregisterJITEventListener(JITEventListener *) {}
 
-  /// DisableLazyCompilation - If called, the JIT will abort if lazy compilation
-  /// is ever attempted.
+  /// DisableLazyCompilation - When lazy compilation is off (the default), the
+  /// JIT will eagerly compile every function reachable from the argument to
+  /// getPointerToFunction.  If lazy compilation is turned on, the JIT will only
+  /// compile the one function and emit stubs to compile the rest when they're
+  /// first called.  If lazy compilation is turned off again while some lazy
+  /// stubs are still around, and one of those stubs is called, the program will
+  /// abort.
+  ///
+  /// In order to safely compile lazily in a threaded program, the user must
+  /// ensure that 1) only one thread at a time can call any particular lazy
+  /// stub, and 2) any thread modifying LLVM IR must hold the JIT's lock
+  /// (ExecutionEngine::lock) or otherwise ensure that no other thread calls a
+  /// lazy stub.  See http://llvm.org/PR5184 for details.
   void DisableLazyCompilation(bool Disabled = true) {
-    LazyCompilationDisabled = Disabled;
+    CompilingLazily = !Disabled;
+  }
+  bool isCompilingLazily() const {
+    return CompilingLazily;
   }
+  // Deprecated in favor of isCompilingLazily (to reduce double-negatives).
+  // Remove this in LLVM 2.8.
   bool isLazyCompilationDisabled() const {
-    return LazyCompilationDisabled;
+    return !CompilingLazily;
   }
 
   /// DisableGVCompilation - If called, the JIT will abort if it's asked to
@@ -485,15 +500,8 @@ class EngineBuilder {
   }
 
   ExecutionEngine *create();
-
 };
 
-inline bool operator<(const ExecutionEngineState::MapUpdatingCVH& lhs,
-                      const ExecutionEngineState::MapUpdatingCVH& rhs) {
-    return static_cast<const GlobalValue*>(lhs) <
-        static_cast<const GlobalValue*>(rhs);
-}
-
 } // End llvm namespace
 
 #endif
diff --git a/include/llvm/ExecutionEngine/GenericValue.h b/include/llvm/ExecutionEngine/GenericValue.h
index a2fed98..1301320 100644
--- a/include/llvm/ExecutionEngine/GenericValue.h
+++ b/include/llvm/ExecutionEngine/GenericValue.h
@@ -16,7 +16,7 @@
 #define GENERIC_VALUE_H
 
 #include "llvm/ADT/APInt.h"
-#include "llvm/Support/DataTypes.h"
+#include "llvm/System/DataTypes.h"
 
 namespace llvm {
 
diff --git a/include/llvm/ExecutionEngine/JITEventListener.h b/include/llvm/ExecutionEngine/JITEventListener.h
index e895e73..dcc66b2 100644
--- a/include/llvm/ExecutionEngine/JITEventListener.h
+++ b/include/llvm/ExecutionEngine/JITEventListener.h
@@ -15,7 +15,7 @@
 #ifndef LLVM_EXECUTION_ENGINE_JIT_EVENTLISTENER_H
 #define LLVM_EXECUTION_ENGINE_JIT_EVENTLISTENER_H
 
-#include "llvm/Support/DataTypes.h"
+#include "llvm/System/DataTypes.h"
 #include "llvm/Support/DebugLoc.h"
 
 #include <vector>
@@ -63,8 +63,11 @@ public:
   /// NotifyFreeingMachineCode - This is called inside of
   /// freeMachineCodeForFunction(), after the global mapping is removed, but
   /// before the machine code is returned to the allocator.  OldPtr is the
-  /// address of the machine code.
-  virtual void NotifyFreeingMachineCode(const Function &F, void *OldPtr) {}
+  /// address of the machine code and will be the same as the Code parameter to
+  /// a previous NotifyFunctionEmitted call.  The Function passed to
+  /// NotifyFunctionEmitted may have been destroyed by the time of the matching
+  /// NotifyFreeingMachineCode call.
+  virtual void NotifyFreeingMachineCode(void *OldPtr) {}
 };
 
 // This returns NULL if support isn't available.
diff --git a/include/llvm/ExecutionEngine/JITMemoryManager.h b/include/llvm/ExecutionEngine/JITMemoryManager.h
index 56851889..130612e 100644
--- a/include/llvm/ExecutionEngine/JITMemoryManager.h
+++ b/include/llvm/ExecutionEngine/JITMemoryManager.h
@@ -14,7 +14,7 @@
 #ifndef LLVM_EXECUTION_ENGINE_JIT_MEMMANAGER_H
 #define LLVM_EXECUTION_ENGINE_JIT_MEMMANAGER_H
 
-#include "llvm/Support/DataTypes.h"
+#include "llvm/System/DataTypes.h"
 #include <string>
 
 namespace llvm {
diff --git a/include/llvm/InstrTypes.h b/include/llvm/InstrTypes.h
index 45d366f..df7eb43 100644
--- a/include/llvm/InstrTypes.h
+++ b/include/llvm/InstrTypes.h
@@ -51,10 +51,9 @@ protected:
   virtual BasicBlock *getSuccessorV(unsigned idx) const = 0;
   virtual unsigned getNumSuccessorsV() const = 0;
   virtual void setSuccessorV(unsigned idx, BasicBlock *B) = 0;
+  virtual TerminatorInst *clone_impl() const = 0;
 public:
 
-  virtual TerminatorInst *clone() const = 0;
-
   /// getNumSuccessors - Return the number of successors that this terminator
   /// has.
   unsigned getNumSuccessors() const {
@@ -117,7 +116,6 @@ public:
   static inline bool classof(const UnaryInstruction *) { return true; }
   static inline bool classof(const Instruction *I) {
     return I->getOpcode() == Instruction::Alloca ||
-           I->getOpcode() == Instruction::Free ||
            I->getOpcode() == Instruction::Load ||
            I->getOpcode() == Instruction::VAArg ||
            I->getOpcode() == Instruction::ExtractValue ||
@@ -146,6 +144,7 @@ protected:
                  const Twine &Name, Instruction *InsertBefore);
   BinaryOperator(BinaryOps iType, Value *S1, Value *S2, const Type *Ty,
                  const Twine &Name, BasicBlock *InsertAtEnd);
+  virtual BinaryOperator *clone_impl() const;
 public:
   // allocate space for exactly two operands
   void *operator new(size_t s) {
@@ -298,8 +297,6 @@ public:
     return static_cast<BinaryOps>(Instruction::getOpcode());
   }
 
-  virtual BinaryOperator *clone() const;
-
   /// swapOperands - Exchange the two operands to this instruction.
   /// This instruction is safe to use on any binary instruction and
   /// does not modify the semantics of the instruction.  If the instruction
@@ -718,6 +715,30 @@ public:
   /// @brief Determine if this is an equals/not equals predicate.
   bool isEquality();
 
+  /// @returns true if the comparison is signed, false otherwise.
+  /// @brief Determine if this instruction is using a signed comparison.
+  bool isSigned() const {
+    return isSigned(getPredicate());
+  }
+
+  /// @returns true if the comparison is unsigned, false otherwise.
+  /// @brief Determine if this instruction is using an unsigned comparison.
+  bool isUnsigned() const {
+    return isUnsigned(getPredicate());
+  }
+
+  /// This is just a convenience.
+  /// @brief Determine if this is true when both operands are the same.
+  bool isTrueWhenEqual() const {
+    return isTrueWhenEqual(getPredicate());
+  }
+
+  /// This is just a convenience.
+  /// @brief Determine if this is false when both operands are the same.
+  bool isFalseWhenEqual() const {
+    return isFalseWhenEqual(getPredicate());
+  }
+
   /// @returns true if the predicate is unsigned, false otherwise.
   /// @brief Determine if the predicate is an unsigned operation.
   static bool isUnsigned(unsigned short predicate);
@@ -732,6 +753,12 @@ public:
   /// @brief Determine if the predicate is an unordered operation.
   static bool isUnordered(unsigned short predicate);
 
+  /// Determine if the predicate is true when comparing a value with itself.
+  static bool isTrueWhenEqual(unsigned short predicate);
+
+  /// Determine if the predicate is false when comparing a value with itself.
+  static bool isFalseWhenEqual(unsigned short predicate);
+
   /// @brief Methods for support type inquiry through isa, cast, and dyn_cast:
   static inline bool classof(const CmpInst *) { return true; }
   static inline bool classof(const Instruction *I) {
diff --git a/include/llvm/Instruction.def b/include/llvm/Instruction.def
index 5c8fe3e..205f303 100644
--- a/include/llvm/Instruction.def
+++ b/include/llvm/Instruction.def
@@ -97,38 +97,38 @@
 HANDLE_TERM_INST  ( 1, Ret        , ReturnInst)
 HANDLE_TERM_INST  ( 2, Br         , BranchInst)
 HANDLE_TERM_INST  ( 3, Switch     , SwitchInst)
-HANDLE_TERM_INST  ( 4, Invoke     , InvokeInst)
-HANDLE_TERM_INST  ( 5, Unwind     , UnwindInst)
-HANDLE_TERM_INST  ( 6, Unreachable, UnreachableInst)
-  LAST_TERM_INST  ( 6)
+HANDLE_TERM_INST  ( 4, IndirectBr , IndirectBrInst)
+HANDLE_TERM_INST  ( 5, Invoke     , InvokeInst)
+HANDLE_TERM_INST  ( 6, Unwind     , UnwindInst)
+HANDLE_TERM_INST  ( 7, Unreachable, UnreachableInst)
+  LAST_TERM_INST  ( 7)
 
 // Standard binary operators...
- FIRST_BINARY_INST( 7)
-HANDLE_BINARY_INST( 7, Add  , BinaryOperator)
-HANDLE_BINARY_INST( 8, FAdd  , BinaryOperator)
-HANDLE_BINARY_INST( 9, Sub  , BinaryOperator)
-HANDLE_BINARY_INST(10, FSub  , BinaryOperator)
-HANDLE_BINARY_INST(11, Mul  , BinaryOperator)
-HANDLE_BINARY_INST(12, FMul  , BinaryOperator)
-HANDLE_BINARY_INST(13, UDiv , BinaryOperator)
-HANDLE_BINARY_INST(14, SDiv , BinaryOperator)
-HANDLE_BINARY_INST(15, FDiv , BinaryOperator)
-HANDLE_BINARY_INST(16, URem , BinaryOperator)
-HANDLE_BINARY_INST(17, SRem , BinaryOperator)
-HANDLE_BINARY_INST(18, FRem , BinaryOperator)
+ FIRST_BINARY_INST( 8)
+HANDLE_BINARY_INST( 8, Add  , BinaryOperator)
+HANDLE_BINARY_INST( 9, FAdd  , BinaryOperator)
+HANDLE_BINARY_INST(10, Sub  , BinaryOperator)
+HANDLE_BINARY_INST(11, FSub  , BinaryOperator)
+HANDLE_BINARY_INST(12, Mul  , BinaryOperator)
+HANDLE_BINARY_INST(13, FMul  , BinaryOperator)
+HANDLE_BINARY_INST(14, UDiv , BinaryOperator)
+HANDLE_BINARY_INST(15, SDiv , BinaryOperator)
+HANDLE_BINARY_INST(16, FDiv , BinaryOperator)
+HANDLE_BINARY_INST(17, URem , BinaryOperator)
+HANDLE_BINARY_INST(18, SRem , BinaryOperator)
+HANDLE_BINARY_INST(19, FRem , BinaryOperator)
 
 // Logical operators (integer operands)
-HANDLE_BINARY_INST(19, Shl  , BinaryOperator) // Shift left  (logical)
-HANDLE_BINARY_INST(20, LShr , BinaryOperator) // Shift right (logical)
-HANDLE_BINARY_INST(21, AShr , BinaryOperator) // Shift right (arithmetic)
-HANDLE_BINARY_INST(22, And  , BinaryOperator)
-HANDLE_BINARY_INST(23, Or   , BinaryOperator)
-HANDLE_BINARY_INST(24, Xor  , BinaryOperator)
-  LAST_BINARY_INST(24)
+HANDLE_BINARY_INST(20, Shl  , BinaryOperator) // Shift left  (logical)
+HANDLE_BINARY_INST(21, LShr , BinaryOperator) // Shift right (logical)
+HANDLE_BINARY_INST(22, AShr , BinaryOperator) // Shift right (arithmetic)
+HANDLE_BINARY_INST(23, And  , BinaryOperator)
+HANDLE_BINARY_INST(24, Or   , BinaryOperator)
+HANDLE_BINARY_INST(25, Xor  , BinaryOperator)
+  LAST_BINARY_INST(25)
 
 // Memory operators...
- FIRST_MEMORY_INST(25)
-HANDLE_MEMORY_INST(25, Free  , FreeInst  )  // Heap management instructions
+ FIRST_MEMORY_INST(26)
 HANDLE_MEMORY_INST(26, Alloca, AllocaInst)  // Stack management
 HANDLE_MEMORY_INST(27, Load  , LoadInst  )  // Memory manipulation instrs
 HANDLE_MEMORY_INST(28, Store , StoreInst )
diff --git a/include/llvm/Instruction.h b/include/llvm/Instruction.h
index fdae3d7..07b3231 100644
--- a/include/llvm/Instruction.h
+++ b/include/llvm/Instruction.h
@@ -38,6 +38,7 @@ protected:
               Instruction *InsertBefore = 0);
   Instruction(const Type *Ty, unsigned iType, Use *Ops, unsigned NumOps,
               BasicBlock *InsertAtEnd);
+  virtual Instruction *clone_impl() const = 0;
 public:
   // Out of line virtual method, so the vtable, etc has a home.
   ~Instruction();
@@ -47,7 +48,7 @@ public:
   ///   * The instruction has no parent
   ///   * The instruction has no name
   ///
-  virtual Instruction *clone() const = 0;
+  Instruction *clone() const;
 
   /// isIdenticalTo - Return true if the specified instruction is exactly
   /// identical to the current one.  This means that all operands match and any
diff --git a/include/llvm/Instructions.h b/include/llvm/Instructions.h
index dbeb9e1..28854df 100644
--- a/include/llvm/Instructions.h
+++ b/include/llvm/Instructions.h
@@ -19,9 +19,7 @@
 #include "llvm/InstrTypes.h"
 #include "llvm/DerivedTypes.h"
 #include "llvm/Attributes.h"
-#include "llvm/BasicBlock.h"
 #include "llvm/CallingConv.h"
-#include "llvm/LLVMContext.h"
 #include "llvm/ADT/SmallVector.h"
 #include <iterator>
 
@@ -34,22 +32,30 @@ class LLVMContext;
 class DominatorTree;
 
 //===----------------------------------------------------------------------===//
-//                             AllocationInst Class
+//                                AllocaInst Class
 //===----------------------------------------------------------------------===//
 
-/// AllocationInst - This class is the base class of AllocaInst.
+/// AllocaInst - an instruction to allocate memory on the stack
 ///
-class AllocationInst : public UnaryInstruction {
+class AllocaInst : public UnaryInstruction {
 protected:
-  AllocationInst(const Type *Ty, Value *ArraySize, 
-                 unsigned iTy, unsigned Align, const Twine &Name = "", 
-                 Instruction *InsertBefore = 0);
-  AllocationInst(const Type *Ty, Value *ArraySize,
-                 unsigned iTy, unsigned Align, const Twine &Name,
-                 BasicBlock *InsertAtEnd);
+  virtual AllocaInst *clone_impl() const;
 public:
+  explicit AllocaInst(const Type *Ty, Value *ArraySize = 0,
+                      const Twine &Name = "", Instruction *InsertBefore = 0);
+  AllocaInst(const Type *Ty, Value *ArraySize, 
+             const Twine &Name, BasicBlock *InsertAtEnd);
+
+  AllocaInst(const Type *Ty, const Twine &Name, Instruction *InsertBefore = 0);
+  AllocaInst(const Type *Ty, const Twine &Name, BasicBlock *InsertAtEnd);
+
+  AllocaInst(const Type *Ty, Value *ArraySize, unsigned Align,
+             const Twine &Name = "", Instruction *InsertBefore = 0);
+  AllocaInst(const Type *Ty, Value *ArraySize, unsigned Align,
+             const Twine &Name, BasicBlock *InsertAtEnd);
+
   // Out of line virtual method, so the vtable, etc. has a home.
-  virtual ~AllocationInst();
+  virtual ~AllocaInst();
 
   /// isArrayAllocation - Return true if there is an allocation size parameter
   /// to the allocation instruction that is not 1.
@@ -79,58 +85,6 @@ public:
   unsigned getAlignment() const { return (1u << SubclassData) >> 1; }
   void setAlignment(unsigned Align);
 
-  virtual AllocationInst *clone() const = 0;
-
-  // Methods for support type inquiry through isa, cast, and dyn_cast:
-  static inline bool classof(const AllocationInst *) { return true; }
-  static inline bool classof(const Instruction *I) {
-    return I->getOpcode() == Instruction::Alloca;
-  }
-  static inline bool classof(const Value *V) {
-    return isa<Instruction>(V) && classof(cast<Instruction>(V));
-  }
-};
-
-
-//===----------------------------------------------------------------------===//
-//                                AllocaInst Class
-//===----------------------------------------------------------------------===//
-
-/// AllocaInst - an instruction to allocate memory on the stack
-///
-class AllocaInst : public AllocationInst {
-public:
-  explicit AllocaInst(const Type *Ty,
-                      Value *ArraySize = 0,
-                      const Twine &NameStr = "",
-                      Instruction *InsertBefore = 0)
-    : AllocationInst(Ty, ArraySize, Alloca,
-                     0, NameStr, InsertBefore) {}
-  AllocaInst(const Type *Ty,
-             Value *ArraySize, const Twine &NameStr,
-             BasicBlock *InsertAtEnd)
-    : AllocationInst(Ty, ArraySize, Alloca, 0, NameStr, InsertAtEnd) {}
-
-  AllocaInst(const Type *Ty, const Twine &NameStr,
-             Instruction *InsertBefore = 0)
-    : AllocationInst(Ty, 0, Alloca, 0, NameStr, InsertBefore) {}
-  AllocaInst(const Type *Ty, const Twine &NameStr,
-             BasicBlock *InsertAtEnd)
-    : AllocationInst(Ty, 0, Alloca, 0, NameStr, InsertAtEnd) {}
-
-  AllocaInst(const Type *Ty, Value *ArraySize,
-             unsigned Align, const Twine &NameStr = "",
-             Instruction *InsertBefore = 0)
-    : AllocationInst(Ty, ArraySize, Alloca,
-                     Align, NameStr, InsertBefore) {}
-  AllocaInst(const Type *Ty, Value *ArraySize,
-             unsigned Align, const Twine &NameStr,
-             BasicBlock *InsertAtEnd)
-    : AllocationInst(Ty, ArraySize, Alloca,
-                     Align, NameStr, InsertAtEnd) {}
-
-  virtual AllocaInst *clone() const;
-
   /// isStaticAlloca - Return true if this alloca is in the entry block of the
   /// function and is a constant size.  If so, the code generator will fold it
   /// into the prolog/epilog code, so it is basically free.
@@ -148,35 +102,6 @@ public:
 
 
 //===----------------------------------------------------------------------===//
-//                                 FreeInst Class
-//===----------------------------------------------------------------------===//
-
-/// FreeInst - an instruction to deallocate memory
-///
-class FreeInst : public UnaryInstruction {
-  void AssertOK();
-public:
-  explicit FreeInst(Value *Ptr, Instruction *InsertBefore = 0);
-  FreeInst(Value *Ptr, BasicBlock *InsertAfter);
-
-  virtual FreeInst *clone() const;
-
-  // Accessor methods for consistency with other memory operations
-  Value *getPointerOperand() { return getOperand(0); }
-  const Value *getPointerOperand() const { return getOperand(0); }
-
-  // Methods for support type inquiry through isa, cast, and dyn_cast:
-  static inline bool classof(const FreeInst *) { return true; }
-  static inline bool classof(const Instruction *I) {
-    return (I->getOpcode() == Instruction::Free);
-  }
-  static inline bool classof(const Value *V) {
-    return isa<Instruction>(V) && classof(cast<Instruction>(V));
-  }
-};
-
-
-//===----------------------------------------------------------------------===//
 //                                LoadInst Class
 //===----------------------------------------------------------------------===//
 
@@ -185,6 +110,8 @@ public:
 ///
 class LoadInst : public UnaryInstruction {
   void AssertOK();
+protected:
+  virtual LoadInst *clone_impl() const;
 public:
   LoadInst(Value *Ptr, const Twine &NameStr, Instruction *InsertBefore);
   LoadInst(Value *Ptr, const Twine &NameStr, BasicBlock *InsertAtEnd);
@@ -215,8 +142,6 @@ public:
     SubclassData = (SubclassData & ~1) | (V ? 1 : 0);
   }
 
-  virtual LoadInst *clone() const;
-
   /// getAlignment - Return the alignment of the access that is being performed
   ///
   unsigned getAlignment() const {
@@ -254,6 +179,8 @@ public:
 class StoreInst : public Instruction {
   void *operator new(size_t, unsigned);  // DO NOT IMPLEMENT
   void AssertOK();
+protected:
+  virtual StoreInst *clone_impl() const;
 public:
   // allocate space for exactly two operands
   void *operator new(size_t s) {
@@ -292,8 +219,6 @@ public:
 
   void setAlignment(unsigned Align);
 
-  virtual StoreInst *clone() const;
-
   Value *getPointerOperand() { return getOperand(1); }
   const Value *getPointerOperand() const { return getOperand(1); }
   static unsigned getPointerOperandIndex() { return 1U; }
@@ -402,6 +327,8 @@ class GetElementPtrInst : public Instruction {
                     Instruction *InsertBefore = 0);
   GetElementPtrInst(Value *Ptr, Value *Idx,
                     const Twine &NameStr, BasicBlock *InsertAtEnd);
+protected:
+  virtual GetElementPtrInst *clone_impl() const;
 public:
   template<typename InputIterator>
   static GetElementPtrInst *Create(Value *Ptr, InputIterator IdxBegin,
@@ -475,8 +402,6 @@ public:
     return GEP;
   }
 
-  virtual GetElementPtrInst *clone() const;
-
   /// Transparently provide more efficient getOperand methods.
   DECLARE_TRANSPARENT_OPERAND_ACCESSORS(Value);
 
@@ -623,6 +548,9 @@ DEFINE_TRANSPARENT_OPERAND_ACCESSORS(GetElementPtrInst, Value)
 /// must be identical types.
 /// @brief Represent an integer comparison operator.
 class ICmpInst: public CmpInst {
+protected:
+  /// @brief Clone an indentical ICmpInst
+  virtual ICmpInst *clone_impl() const;  
 public:
   /// @brief Constructor with insert-before-instruction semantics.
   ICmpInst(
@@ -737,30 +665,6 @@ public:
     return !isEquality(P);
   }
 
-  /// @returns true if the predicate of this ICmpInst is signed, false otherwise
-  /// @brief Determine if this instruction's predicate is signed.
-  bool isSignedPredicate() const { return isSignedPredicate(getPredicate()); }
-
-  /// @returns true if the predicate provided is signed, false otherwise
-  /// @brief Determine if the predicate is signed.
-  static bool isSignedPredicate(Predicate pred);
-
-  /// @returns true if the specified compare predicate is
-  /// true when both operands are equal...
-  /// @brief Determine if the icmp is true when both operands are equal
-  static bool isTrueWhenEqual(ICmpInst::Predicate pred) {
-    return pred == ICmpInst::ICMP_EQ  || pred == ICmpInst::ICMP_UGE ||
-           pred == ICmpInst::ICMP_SGE || pred == ICmpInst::ICMP_ULE ||
-           pred == ICmpInst::ICMP_SLE;
-  }
-
-  /// @returns true if the specified compare instruction is
-  /// true when both operands are equal...
-  /// @brief Determine if the ICmpInst returns true when both operands are equal
-  bool isTrueWhenEqual() {
-    return isTrueWhenEqual(getPredicate());
-  }
-
   /// Initialize a set of values that all satisfy the predicate with C.
   /// @brief Make a ConstantRange for a relation with a constant value.
   static ConstantRange makeConstantRange(Predicate pred, const APInt &C);
@@ -775,8 +679,6 @@ public:
     Op<0>().swap(Op<1>());
   }
 
-  virtual ICmpInst *clone() const;
-
   // Methods for support type inquiry through isa, cast, and dyn_cast:
   static inline bool classof(const ICmpInst *) { return true; }
   static inline bool classof(const Instruction *I) {
@@ -797,6 +699,9 @@ public:
 /// vectors of floating point values. The operands must be identical types.
 /// @brief Represents a floating point comparison operator.
 class FCmpInst: public CmpInst {
+protected:
+  /// @brief Clone an indentical FCmpInst
+  virtual FCmpInst *clone_impl() const;
 public:
   /// @brief Constructor with insert-before-instruction semantics.
   FCmpInst(
@@ -884,8 +789,6 @@ public:
     Op<0>().swap(Op<1>());
   }
 
-  virtual FCmpInst *clone() const;
-
   /// @brief Methods for support type inquiry through isa, cast, and dyn_cast:
   static inline bool classof(const FCmpInst *) { return true; }
   static inline bool classof(const Instruction *I) {
@@ -953,6 +856,8 @@ class CallInst : public Instruction {
   explicit CallInst(Value *F, const Twine &NameStr,
                     Instruction *InsertBefore);
   CallInst(Value *F, const Twine &NameStr, BasicBlock *InsertAtEnd);
+protected:
+  virtual CallInst *clone_impl() const;
 public:
   template<typename InputIterator>
   static CallInst *Create(Value *Func,
@@ -1000,6 +905,9 @@ public:
                                    const Type *IntPtrTy, const Type *AllocTy,
                                    Value *ArraySize = 0, Function* MallocF = 0,
                                    const Twine &Name = "");
+  /// CreateFree - Generate the IR for a call to the builtin free function.
+  static void CreateFree(Value* Source, Instruction *InsertBefore);
+  static Instruction* CreateFree(Value* Source, BasicBlock *InsertAtEnd);
 
   ~CallInst();
 
@@ -1008,8 +916,6 @@ public:
     SubclassData = (SubclassData & ~1) | unsigned(isTC);
   }
 
-  virtual CallInst *clone() const;
-
   /// Provide fast operand accessors
   DECLARE_TRANSPARENT_OPERAND_ACCESSORS(Value);
 
@@ -1177,6 +1083,8 @@ class SelectInst : public Instruction {
     init(C, S1, S2);
     setName(NameStr);
   }
+protected:
+  virtual SelectInst *clone_impl() const;
 public:
   static SelectInst *Create(Value *C, Value *S1, Value *S2,
                             const Twine &NameStr = "",
@@ -1207,8 +1115,6 @@ public:
     return static_cast<OtherOps>(Instruction::getOpcode());
   }
 
-  virtual SelectInst *clone() const;
-
   // Methods for support type inquiry through isa, cast, and dyn_cast:
   static inline bool classof(const SelectInst *) { return true; }
   static inline bool classof(const Instruction *I) {
@@ -1233,6 +1139,9 @@ DEFINE_TRANSPARENT_OPERAND_ACCESSORS(SelectInst, Value)
 /// an argument of the specified type given a va_list and increments that list
 ///
 class VAArgInst : public UnaryInstruction {
+protected:
+  virtual VAArgInst *clone_impl() const;
+
 public:
   VAArgInst(Value *List, const Type *Ty, const Twine &NameStr = "",
              Instruction *InsertBefore = 0)
@@ -1245,8 +1154,6 @@ public:
     setName(NameStr);
   }
 
-  virtual VAArgInst *clone() const;
-
   // Methods for support type inquiry through isa, cast, and dyn_cast:
   static inline bool classof(const VAArgInst *) { return true; }
   static inline bool classof(const Instruction *I) {
@@ -1269,6 +1176,9 @@ class ExtractElementInst : public Instruction {
                      Instruction *InsertBefore = 0);
   ExtractElementInst(Value *Vec, Value *Idx, const Twine &NameStr,
                      BasicBlock *InsertAtEnd);
+protected:
+  virtual ExtractElementInst *clone_impl() const;
+
 public:
   static ExtractElementInst *Create(Value *Vec, Value *Idx,
                                    const Twine &NameStr = "",
@@ -1285,8 +1195,6 @@ public:
   /// formed with the specified operands.
   static bool isValidOperands(const Value *Vec, const Value *Idx);
 
-  virtual ExtractElementInst *clone() const;
-
   Value *getVectorOperand() { return Op<0>(); }
   Value *getIndexOperand() { return Op<1>(); }
   const Value *getVectorOperand() const { return Op<0>(); }
@@ -1329,6 +1237,9 @@ class InsertElementInst : public Instruction {
                     Instruction *InsertBefore = 0);
   InsertElementInst(Value *Vec, Value *NewElt, Value *Idx,
                     const Twine &NameStr, BasicBlock *InsertAtEnd);
+protected:
+  virtual InsertElementInst *clone_impl() const;
+
 public:
   static InsertElementInst *Create(Value *Vec, Value *NewElt, Value *Idx,
                                    const Twine &NameStr = "",
@@ -1346,8 +1257,6 @@ public:
   static bool isValidOperands(const Value *Vec, const Value *NewElt,
                               const Value *Idx);
 
-  virtual InsertElementInst *clone() const;
-
   /// getType - Overload to return most specific vector type.
   ///
   const VectorType *getType() const {
@@ -1381,6 +1290,9 @@ DEFINE_TRANSPARENT_OPERAND_ACCESSORS(InsertElementInst, Value)
 /// input vectors.
 ///
 class ShuffleVectorInst : public Instruction {
+protected:
+  virtual ShuffleVectorInst *clone_impl() const;
+
 public:
   // allocate space for exactly three operands
   void *operator new(size_t s) {
@@ -1397,8 +1309,6 @@ public:
   static bool isValidOperands(const Value *V1, const Value *V2,
                               const Value *Mask);
 
-  virtual ShuffleVectorInst *clone() const;
-
   /// getType - Overload to return most specific vector type.
   ///
   const VectorType *getType() const {
@@ -1507,6 +1417,8 @@ class ExtractValueInst : public UnaryInstruction {
   void *operator new(size_t s) {
     return User::operator new(s, 1);
   }
+protected:
+  virtual ExtractValueInst *clone_impl() const;
 
 public:
   template<typename InputIterator>
@@ -1541,8 +1453,6 @@ public:
     return new ExtractValueInst(Agg, Idxs, Idxs + 1, NameStr, InsertAtEnd);
   }
 
-  virtual ExtractValueInst *clone() const;
-
   /// getIndexedType - Returns the type of the element that would be extracted
   /// with an extractvalue instruction with the specified parameters.
   ///
@@ -1674,6 +1584,8 @@ class InsertValueInst : public Instruction {
                   Instruction *InsertBefore = 0);
   InsertValueInst(Value *Agg, Value *Val, unsigned Idx,
                   const Twine &NameStr, BasicBlock *InsertAtEnd);
+protected:
+  virtual InsertValueInst *clone_impl() const;
 public:
   // allocate space for exactly two operands
   void *operator new(size_t s) {
@@ -1711,8 +1623,6 @@ public:
     return new InsertValueInst(Agg, Val, Idx, NameStr, InsertAtEnd);
   }
 
-  virtual InsertValueInst *clone() const;
-
   /// Transparently provide more efficient getOperand methods.
   DECLARE_TRANSPARENT_OPERAND_ACCESSORS(Value);
 
@@ -1821,6 +1731,8 @@ class PHINode : public Instruction {
       ReservedSpace(0) {
     setName(NameStr);
   }
+protected:
+  virtual PHINode *clone_impl() const;
 public:
   static PHINode *Create(const Type *Ty, const Twine &NameStr = "",
                          Instruction *InsertBefore = 0) {
@@ -1840,8 +1752,6 @@ public:
     resizeOperands(NumValues*2);
   }
 
-  virtual PHINode *clone() const;
-
   /// Provide fast operand accessors
   DECLARE_TRANSPARENT_OPERAND_ACCESSORS(Value);
 
@@ -1891,7 +1801,7 @@ public:
   
   
   void setIncomingBlock(unsigned i, BasicBlock *BB) {
-    setOperand(i*2+1, BB);
+    setOperand(i*2+1, (Value*)BB);
   }
   static unsigned getOperandNumForIncomingBlock(unsigned i) {
     return i*2+1;
@@ -1914,7 +1824,7 @@ public:
     // Initialize some new operands.
     NumOperands = OpNo+2;
     OperandList[OpNo] = V;
-    OperandList[OpNo+1] = BB;
+    OperandList[OpNo+1] = (Value*)BB;
   }
 
   /// removeIncomingValue - Remove an incoming value.  This is useful if a
@@ -1939,7 +1849,7 @@ public:
   int getBasicBlockIndex(const BasicBlock *BB) const {
     Use *OL = OperandList;
     for (unsigned i = 0, e = getNumOperands(); i != e; i += 2)
-      if (OL[i+1].get() == BB) return i/2;
+      if (OL[i+1].get() == (const Value*)BB) return i/2;
     return -1;
   }
 
@@ -2003,6 +1913,8 @@ private:
                       Instruction *InsertBefore = 0);
   ReturnInst(LLVMContext &C, Value *retVal, BasicBlock *InsertAtEnd);
   explicit ReturnInst(LLVMContext &C, BasicBlock *InsertAtEnd);
+protected:
+  virtual ReturnInst *clone_impl() const;
 public:
   static ReturnInst* Create(LLVMContext &C, Value *retVal = 0,
                             Instruction *InsertBefore = 0) {
@@ -2017,8 +1929,6 @@ public:
   }
   virtual ~ReturnInst();
 
-  virtual ReturnInst *clone() const;
-
   /// Provide fast operand accessors
   DECLARE_TRANSPARENT_OPERAND_ACCESSORS(Value);
 
@@ -2078,6 +1988,8 @@ class BranchInst : public TerminatorInst {
   BranchInst(BasicBlock *IfTrue, BasicBlock *InsertAtEnd);
   BranchInst(BasicBlock *IfTrue, BasicBlock *IfFalse, Value *Cond,
              BasicBlock *InsertAtEnd);
+protected:
+  virtual BranchInst *clone_impl() const;
 public:
   static BranchInst *Create(BasicBlock *IfTrue, Instruction *InsertBefore = 0) {
     return new(1, true) BranchInst(IfTrue, InsertBefore);
@@ -2099,8 +2011,6 @@ public:
   /// Transparently provide more efficient getOperand methods.
   DECLARE_TRANSPARENT_OPERAND_ACCESSORS(Value);
 
-  virtual BranchInst *clone() const;
-
   bool isUnconditional() const { return getNumOperands() == 1; }
   bool isConditional()   const { return getNumOperands() == 3; }
 
@@ -2118,7 +2028,7 @@ public:
   // targeting the specified block.
   // FIXME: Eliminate this ugly method.
   void setUnconditionalDest(BasicBlock *Dest) {
-    Op<-1>() = Dest;
+    Op<-1>() = (Value*)Dest;
     if (isConditional()) {  // Convert this to an uncond branch.
       Op<-2>() = 0;
       Op<-3>() = 0;
@@ -2136,7 +2046,7 @@ public:
 
   void setSuccessor(unsigned idx, BasicBlock *NewSucc) {
     assert(idx < getNumSuccessors() && "Successor # out of range for Branch!");
-    *(&Op<-1>() - idx) = NewSucc;
+    *(&Op<-1>() - idx) = (Value*)NewSucc;
   }
 
   // Methods for support type inquiry through isa, cast, and dyn_cast:
@@ -2172,7 +2082,7 @@ class SwitchInst : public TerminatorInst {
   // Operand[1]    = Default basic block destination
   // Operand[2n  ] = Value to match
   // Operand[2n+1] = BasicBlock to go to on match
-  SwitchInst(const SwitchInst &RI);
+  SwitchInst(const SwitchInst &SI);
   void init(Value *Value, BasicBlock *Default, unsigned NumCases);
   void resizeOperands(unsigned No);
   // allocate space for exactly zero operands
@@ -2184,7 +2094,7 @@ class SwitchInst : public TerminatorInst {
   /// be specified here to make memory allocation more efficient.  This
   /// constructor can also autoinsert before another instruction.
   SwitchInst(Value *Value, BasicBlock *Default, unsigned NumCases,
-             Instruction *InsertBefore = 0);
+             Instruction *InsertBefore);
 
   /// SwitchInst ctor - Create a new switch instruction, specifying a value to
   /// switch on and a default destination.  The number of additional cases can
@@ -2192,6 +2102,8 @@ class SwitchInst : public TerminatorInst {
   /// constructor also autoinserts at the end of the specified BasicBlock.
   SwitchInst(Value *Value, BasicBlock *Default, unsigned NumCases,
              BasicBlock *InsertAtEnd);
+protected:
+  virtual SwitchInst *clone_impl() const;
 public:
   static SwitchInst *Create(Value *Value, BasicBlock *Default,
                             unsigned NumCases, Instruction *InsertBefore = 0) {
@@ -2269,8 +2181,6 @@ public:
   ///
   void removeCase(unsigned idx);
 
-  virtual SwitchInst *clone() const;
-
   unsigned getNumSuccessors() const { return getNumOperands()/2; }
   BasicBlock *getSuccessor(unsigned idx) const {
     assert(idx < getNumSuccessors() &&"Successor idx out of range for switch!");
@@ -2278,7 +2188,7 @@ public:
   }
   void setSuccessor(unsigned idx, BasicBlock *NewSucc) {
     assert(idx < getNumSuccessors() && "Successor # out of range for switch!");
-    setOperand(idx*2+1, NewSucc);
+    setOperand(idx*2+1, (Value*)NewSucc);
   }
 
   // getSuccessorValue - Return the value associated with the specified
@@ -2310,6 +2220,105 @@ DEFINE_TRANSPARENT_OPERAND_ACCESSORS(SwitchInst, Value)
 
 
 //===----------------------------------------------------------------------===//
+//                             IndirectBrInst Class
+//===----------------------------------------------------------------------===//
+
+//===---------------------------------------------------------------------------
+/// IndirectBrInst - Indirect Branch Instruction.
+///
+class IndirectBrInst : public TerminatorInst {
+  void *operator new(size_t, unsigned);  // DO NOT IMPLEMENT
+  unsigned ReservedSpace;
+  // Operand[0]    = Value to switch on
+  // Operand[1]    = Default basic block destination
+  // Operand[2n  ] = Value to match
+  // Operand[2n+1] = BasicBlock to go to on match
+  IndirectBrInst(const IndirectBrInst &IBI);
+  void init(Value *Address, unsigned NumDests);
+  void resizeOperands(unsigned No);
+  // allocate space for exactly zero operands
+  void *operator new(size_t s) {
+    return User::operator new(s, 0);
+  }
+  /// IndirectBrInst ctor - Create a new indirectbr instruction, specifying an
+  /// Address to jump to.  The number of expected destinations can be specified
+  /// here to make memory allocation more efficient.  This constructor can also
+  /// autoinsert before another instruction.
+  IndirectBrInst(Value *Address, unsigned NumDests, Instruction *InsertBefore);
+  
+  /// IndirectBrInst ctor - Create a new indirectbr instruction, specifying an
+  /// Address to jump to.  The number of expected destinations can be specified
+  /// here to make memory allocation more efficient.  This constructor also
+  /// autoinserts at the end of the specified BasicBlock.
+  IndirectBrInst(Value *Address, unsigned NumDests, BasicBlock *InsertAtEnd);
+protected:
+  virtual IndirectBrInst *clone_impl() const;
+public:
+  static IndirectBrInst *Create(Value *Address, unsigned NumDests,
+                                Instruction *InsertBefore = 0) {
+    return new IndirectBrInst(Address, NumDests, InsertBefore);
+  }
+  static IndirectBrInst *Create(Value *Address, unsigned NumDests,
+                                BasicBlock *InsertAtEnd) {
+    return new IndirectBrInst(Address, NumDests, InsertAtEnd);
+  }
+  ~IndirectBrInst();
+  
+  /// Provide fast operand accessors.
+  DECLARE_TRANSPARENT_OPERAND_ACCESSORS(Value);
+  
+  // Accessor Methods for IndirectBrInst instruction.
+  Value *getAddress() { return getOperand(0); }
+  const Value *getAddress() const { return getOperand(0); }
+  void setAddress(Value *V) { setOperand(0, V); }
+  
+  
+  /// getNumDestinations - return the number of possible destinations in this
+  /// indirectbr instruction.
+  unsigned getNumDestinations() const { return getNumOperands()-1; }
+  
+  /// getDestination - Return the specified destination.
+  BasicBlock *getDestination(unsigned i) { return getSuccessor(i); }
+  const BasicBlock *getDestination(unsigned i) const { return getSuccessor(i); }
+  
+  /// addDestination - Add a destination.
+  ///
+  void addDestination(BasicBlock *Dest);
+  
+  /// removeDestination - This method removes the specified successor from the
+  /// indirectbr instruction.
+  void removeDestination(unsigned i);
+  
+  unsigned getNumSuccessors() const { return getNumOperands()-1; }
+  BasicBlock *getSuccessor(unsigned i) const {
+    return cast<BasicBlock>(getOperand(i+1));
+  }
+  void setSuccessor(unsigned i, BasicBlock *NewSucc) {
+    setOperand(i+1, (Value*)NewSucc);
+  }
+  
+  // Methods for support type inquiry through isa, cast, and dyn_cast:
+  static inline bool classof(const IndirectBrInst *) { return true; }
+  static inline bool classof(const Instruction *I) {
+    return I->getOpcode() == Instruction::IndirectBr;
+  }
+  static inline bool classof(const Value *V) {
+    return isa<Instruction>(V) && classof(cast<Instruction>(V));
+  }
+private:
+  virtual BasicBlock *getSuccessorV(unsigned idx) const;
+  virtual unsigned getNumSuccessorsV() const;
+  virtual void setSuccessorV(unsigned idx, BasicBlock *B);
+};
+
+template <>
+struct OperandTraits<IndirectBrInst> : public HungoffOperandTraits<1> {
+};
+
+DEFINE_TRANSPARENT_OPERAND_ACCESSORS(IndirectBrInst, Value)
+  
+  
+//===----------------------------------------------------------------------===//
 //                               InvokeInst Class
 //===----------------------------------------------------------------------===//
 
@@ -2361,6 +2370,8 @@ class InvokeInst : public TerminatorInst {
                     InputIterator ArgBegin, InputIterator ArgEnd,
                     unsigned Values,
                     const Twine &NameStr, BasicBlock *InsertAtEnd);
+protected:
+  virtual InvokeInst *clone_impl() const;
 public:
   template<typename InputIterator>
   static InvokeInst *Create(Value *Func,
@@ -2383,8 +2394,6 @@ public:
                                   Values, NameStr, InsertAtEnd);
   }
 
-  virtual InvokeInst *clone() const;
-
   /// Provide fast operand accessors
   DECLARE_TRANSPARENT_OPERAND_ACCESSORS(Value);
 
@@ -2487,11 +2496,11 @@ public:
     return cast<BasicBlock>(getOperand(2));
   }
   void setNormalDest(BasicBlock *B) {
-    setOperand(1, B);
+    setOperand(1, (Value*)B);
   }
 
   void setUnwindDest(BasicBlock *B) {
-    setOperand(2, B);
+    setOperand(2, (Value*)B);
   }
 
   BasicBlock *getSuccessor(unsigned i) const {
@@ -2501,7 +2510,7 @@ public:
 
   void setSuccessor(unsigned idx, BasicBlock *NewSucc) {
     assert(idx < 2 && "Successor # out of range for invoke!");
-    setOperand(idx+1, NewSucc);
+    setOperand(idx+1, (Value*)NewSucc);
   }
 
   unsigned getNumSuccessors() const { return 2; }
@@ -2565,6 +2574,8 @@ DEFINE_TRANSPARENT_OPERAND_ACCESSORS(InvokeInst, Value)
 ///
 class UnwindInst : public TerminatorInst {
   void *operator new(size_t, unsigned);  // DO NOT IMPLEMENT
+protected:
+  virtual UnwindInst *clone_impl() const;
 public:
   // allocate space for exactly zero operands
   void *operator new(size_t s) {
@@ -2573,8 +2584,6 @@ public:
   explicit UnwindInst(LLVMContext &C, Instruction *InsertBefore = 0);
   explicit UnwindInst(LLVMContext &C, BasicBlock *InsertAtEnd);
 
-  virtual UnwindInst *clone() const;
-
   unsigned getNumSuccessors() const { return 0; }
 
   // Methods for support type inquiry through isa, cast, and dyn_cast:
@@ -2602,6 +2611,9 @@ private:
 ///
 class UnreachableInst : public TerminatorInst {
   void *operator new(size_t, unsigned);  // DO NOT IMPLEMENT
+protected:
+  virtual UnreachableInst *clone_impl() const;
+
 public:
   // allocate space for exactly zero operands
   void *operator new(size_t s) {
@@ -2610,8 +2622,6 @@ public:
   explicit UnreachableInst(LLVMContext &C, Instruction *InsertBefore = 0);
   explicit UnreachableInst(LLVMContext &C, BasicBlock *InsertAtEnd);
 
-  virtual UnreachableInst *clone() const;
-
   unsigned getNumSuccessors() const { return 0; }
 
   // Methods for support type inquiry through isa, cast, and dyn_cast:
@@ -2634,6 +2644,10 @@ private:
 
 /// @brief This class represents a truncation of integer types.
 class TruncInst : public CastInst {
+protected:
+  /// @brief Clone an identical TruncInst
+  virtual TruncInst *clone_impl() const;
+
 public:
   /// @brief Constructor with insert-before-instruction semantics
   TruncInst(
@@ -2651,9 +2665,6 @@ public:
     BasicBlock *InsertAtEnd       ///< The block to insert the instruction into
   );
 
-  /// @brief Clone an identical TruncInst
-  virtual TruncInst *clone() const;
-
   /// @brief Methods for support type inquiry through isa, cast, and dyn_cast:
   static inline bool classof(const TruncInst *) { return true; }
   static inline bool classof(const Instruction *I) {
@@ -2670,6 +2681,10 @@ public:
 
 /// @brief This class represents zero extension of integer types.
 class ZExtInst : public CastInst {
+protected:
+  /// @brief Clone an identical ZExtInst
+  virtual ZExtInst *clone_impl() const;
+
 public:
   /// @brief Constructor with insert-before-instruction semantics
   ZExtInst(
@@ -2687,9 +2702,6 @@ public:
     BasicBlock *InsertAtEnd       ///< The block to insert the instruction into
   );
 
-  /// @brief Clone an identical ZExtInst
-  virtual ZExtInst *clone() const;
-
   /// @brief Methods for support type inquiry through isa, cast, and dyn_cast:
   static inline bool classof(const ZExtInst *) { return true; }
   static inline bool classof(const Instruction *I) {
@@ -2706,6 +2718,10 @@ public:
 
 /// @brief This class represents a sign extension of integer types.
 class SExtInst : public CastInst {
+protected:
+  /// @brief Clone an identical SExtInst
+  virtual SExtInst *clone_impl() const;
+
 public:
   /// @brief Constructor with insert-before-instruction semantics
   SExtInst(
@@ -2723,9 +2739,6 @@ public:
     BasicBlock *InsertAtEnd       ///< The block to insert the instruction into
   );
 
-  /// @brief Clone an identical SExtInst
-  virtual SExtInst *clone() const;
-
   /// @brief Methods for support type inquiry through isa, cast, and dyn_cast:
   static inline bool classof(const SExtInst *) { return true; }
   static inline bool classof(const Instruction *I) {
@@ -2742,6 +2755,10 @@ public:
 
 /// @brief This class represents a truncation of floating point types.
 class FPTruncInst : public CastInst {
+protected:
+  /// @brief Clone an identical FPTruncInst
+  virtual FPTruncInst *clone_impl() const;
+
 public:
   /// @brief Constructor with insert-before-instruction semantics
   FPTruncInst(
@@ -2759,9 +2776,6 @@ public:
     BasicBlock *InsertAtEnd       ///< The block to insert the instruction into
   );
 
-  /// @brief Clone an identical FPTruncInst
-  virtual FPTruncInst *clone() const;
-
   /// @brief Methods for support type inquiry through isa, cast, and dyn_cast:
   static inline bool classof(const FPTruncInst *) { return true; }
   static inline bool classof(const Instruction *I) {
@@ -2778,6 +2792,10 @@ public:
 
 /// @brief This class represents an extension of floating point types.
 class FPExtInst : public CastInst {
+protected:
+  /// @brief Clone an identical FPExtInst
+  virtual FPExtInst *clone_impl() const;
+
 public:
   /// @brief Constructor with insert-before-instruction semantics
   FPExtInst(
@@ -2795,9 +2813,6 @@ public:
     BasicBlock *InsertAtEnd       ///< The block to insert the instruction into
   );
 
-  /// @brief Clone an identical FPExtInst
-  virtual FPExtInst *clone() const;
-
   /// @brief Methods for support type inquiry through isa, cast, and dyn_cast:
   static inline bool classof(const FPExtInst *) { return true; }
   static inline bool classof(const Instruction *I) {
@@ -2814,6 +2829,10 @@ public:
 
 /// @brief This class represents a cast unsigned integer to floating point.
 class UIToFPInst : public CastInst {
+protected:
+  /// @brief Clone an identical UIToFPInst
+  virtual UIToFPInst *clone_impl() const;
+
 public:
   /// @brief Constructor with insert-before-instruction semantics
   UIToFPInst(
@@ -2831,9 +2850,6 @@ public:
     BasicBlock *InsertAtEnd       ///< The block to insert the instruction into
   );
 
-  /// @brief Clone an identical UIToFPInst
-  virtual UIToFPInst *clone() const;
-
   /// @brief Methods for support type inquiry through isa, cast, and dyn_cast:
   static inline bool classof(const UIToFPInst *) { return true; }
   static inline bool classof(const Instruction *I) {
@@ -2850,6 +2866,10 @@ public:
 
 /// @brief This class represents a cast from signed integer to floating point.
 class SIToFPInst : public CastInst {
+protected:
+  /// @brief Clone an identical SIToFPInst
+  virtual SIToFPInst *clone_impl() const;
+
 public:
   /// @brief Constructor with insert-before-instruction semantics
   SIToFPInst(
@@ -2867,9 +2887,6 @@ public:
     BasicBlock *InsertAtEnd       ///< The block to insert the instruction into
   );
 
-  /// @brief Clone an identical SIToFPInst
-  virtual SIToFPInst *clone() const;
-
   /// @brief Methods for support type inquiry through isa, cast, and dyn_cast:
   static inline bool classof(const SIToFPInst *) { return true; }
   static inline bool classof(const Instruction *I) {
@@ -2886,6 +2903,10 @@ public:
 
 /// @brief This class represents a cast from floating point to unsigned integer
 class FPToUIInst  : public CastInst {
+protected:
+  /// @brief Clone an identical FPToUIInst
+  virtual FPToUIInst *clone_impl() const;
+
 public:
   /// @brief Constructor with insert-before-instruction semantics
   FPToUIInst(
@@ -2903,9 +2924,6 @@ public:
     BasicBlock *InsertAtEnd       ///< Where to insert the new instruction
   );
 
-  /// @brief Clone an identical FPToUIInst
-  virtual FPToUIInst *clone() const;
-
   /// @brief Methods for support type inquiry through isa, cast, and dyn_cast:
   static inline bool classof(const FPToUIInst *) { return true; }
   static inline bool classof(const Instruction *I) {
@@ -2922,6 +2940,10 @@ public:
 
 /// @brief This class represents a cast from floating point to signed integer.
 class FPToSIInst  : public CastInst {
+protected:
+  /// @brief Clone an identical FPToSIInst
+  virtual FPToSIInst *clone_impl() const;
+
 public:
   /// @brief Constructor with insert-before-instruction semantics
   FPToSIInst(
@@ -2939,9 +2961,6 @@ public:
     BasicBlock *InsertAtEnd       ///< The block to insert the instruction into
   );
 
-  /// @brief Clone an identical FPToSIInst
-  virtual FPToSIInst *clone() const;
-
   /// @brief Methods for support type inquiry through isa, cast, and dyn_cast:
   static inline bool classof(const FPToSIInst *) { return true; }
   static inline bool classof(const Instruction *I) {
@@ -2976,7 +2995,7 @@ public:
   );
 
   /// @brief Clone an identical IntToPtrInst
-  virtual IntToPtrInst *clone() const;
+  virtual IntToPtrInst *clone_impl() const;
 
   // Methods for support type inquiry through isa, cast, and dyn_cast:
   static inline bool classof(const IntToPtrInst *) { return true; }
@@ -2994,6 +3013,10 @@ public:
 
 /// @brief This class represents a cast from a pointer to an integer
 class PtrToIntInst : public CastInst {
+protected:
+  /// @brief Clone an identical PtrToIntInst
+  virtual PtrToIntInst *clone_impl() const;
+
 public:
   /// @brief Constructor with insert-before-instruction semantics
   PtrToIntInst(
@@ -3011,9 +3034,6 @@ public:
     BasicBlock *InsertAtEnd       ///< The block to insert the instruction into
   );
 
-  /// @brief Clone an identical PtrToIntInst
-  virtual PtrToIntInst *clone() const;
-
   // Methods for support type inquiry through isa, cast, and dyn_cast:
   static inline bool classof(const PtrToIntInst *) { return true; }
   static inline bool classof(const Instruction *I) {
@@ -3030,6 +3050,10 @@ public:
 
 /// @brief This class represents a no-op cast from one type to another.
 class BitCastInst : public CastInst {
+protected:
+  /// @brief Clone an identical BitCastInst
+  virtual BitCastInst *clone_impl() const;
+
 public:
   /// @brief Constructor with insert-before-instruction semantics
   BitCastInst(
@@ -3047,9 +3071,6 @@ public:
     BasicBlock *InsertAtEnd       ///< The block to insert the instruction into
   );
 
-  /// @brief Clone an identical BitCastInst
-  virtual BitCastInst *clone() const;
-
   // Methods for support type inquiry through isa, cast, and dyn_cast:
   static inline bool classof(const BitCastInst *) { return true; }
   static inline bool classof(const Instruction *I) {
diff --git a/include/llvm/Intrinsics.td b/include/llvm/Intrinsics.td
index e6d8007..c0cf00e 100644
--- a/include/llvm/Intrinsics.td
+++ b/include/llvm/Intrinsics.td
@@ -259,6 +259,11 @@ def int_longjmp    : Intrinsic<[llvm_void_ty], [llvm_ptr_ty, llvm_i32_ty]>;
 def int_sigsetjmp  : Intrinsic<[llvm_i32_ty] , [llvm_ptr_ty, llvm_i32_ty]>;
 def int_siglongjmp : Intrinsic<[llvm_void_ty], [llvm_ptr_ty, llvm_i32_ty]>;
 
+// Internal interface for object size checking
+def int_objectsize : Intrinsic<[llvm_anyint_ty], [llvm_ptr_ty, llvm_i32_ty],
+                               [IntrReadArgMem]>,
+                               GCCBuiltin<"__builtin_object_size">;
+
 //===-------------------- Bit Manipulation Intrinsics ---------------------===//
 //
 
diff --git a/include/llvm/LinkAllPasses.h b/include/llvm/LinkAllPasses.h
index 3342ea8..bcb98c1 100644
--- a/include/llvm/LinkAllPasses.h
+++ b/include/llvm/LinkAllPasses.h
@@ -91,7 +91,6 @@ namespace {
       (void) llvm::createLoopUnswitchPass();
       (void) llvm::createLoopRotatePass();
       (void) llvm::createLoopIndexSplitPass();
-      (void) llvm::createLowerAllocationsPass();
       (void) llvm::createLowerInvokePass();
       (void) llvm::createLowerSetJmpPass();
       (void) llvm::createLowerSwitchPass();
@@ -107,7 +106,6 @@ namespace {
       (void) llvm::createPostDomPrinterPass();
       (void) llvm::createPostDomOnlyViewerPass();
       (void) llvm::createPostDomViewerPass();
-      (void) llvm::createRaiseAllocationsPass();
       (void) llvm::createReassociatePass();
       (void) llvm::createSCCPPass();
       (void) llvm::createScalarReplAggregatesPass();
@@ -125,7 +123,6 @@ namespace {
       (void) llvm::createNullProfilerRSPass();
       (void) llvm::createRSProfilingPass();
       (void) llvm::createInstCountPass();
-      (void) llvm::createCodeGenLICMPass();
       (void) llvm::createCodeGenPreparePass();
       (void) llvm::createGVNPass();
       (void) llvm::createMemCpyOptPass();
@@ -142,6 +139,9 @@ namespace {
       (void) llvm::createPartialInliningPass();
       (void) llvm::createSSIPass();
       (void) llvm::createSSIEverythingPass();
+      (void) llvm::createGEPSplitterPass();
+      (void) llvm::createSCCVNPass();
+      (void) llvm::createABCDPass();
 
       (void)new llvm::IntervalPartition();
       (void)new llvm::FindUsedTypes();
diff --git a/include/llvm/MC/MCAsmLexer.h b/include/llvm/MC/MCAsmLexer.h
index e66425a..e369e30 100644
--- a/include/llvm/MC/MCAsmLexer.h
+++ b/include/llvm/MC/MCAsmLexer.h
@@ -11,7 +11,7 @@
 #define LLVM_MC_MCASMLEXER_H
 
 #include "llvm/ADT/StringRef.h"
-#include "llvm/Support/DataTypes.h"
+#include "llvm/System/DataTypes.h"
 
 namespace llvm {
 class MCAsmLexer;
diff --git a/include/llvm/MC/MCAsmParser.h b/include/llvm/MC/MCAsmParser.h
index c1b5d13..d530093 100644
--- a/include/llvm/MC/MCAsmParser.h
+++ b/include/llvm/MC/MCAsmParser.h
@@ -10,7 +10,7 @@
 #ifndef LLVM_MC_MCASMPARSER_H
 #define LLVM_MC_MCASMPARSER_H
 
-#include "llvm/Support/DataTypes.h"
+#include "llvm/System/DataTypes.h"
 
 namespace llvm {
 class MCAsmLexer;
diff --git a/include/llvm/MC/MCAssembler.h b/include/llvm/MC/MCAssembler.h
index 76ed3df..8656927 100644
--- a/include/llvm/MC/MCAssembler.h
+++ b/include/llvm/MC/MCAssembler.h
@@ -14,7 +14,7 @@
 #include "llvm/ADT/ilist.h"
 #include "llvm/ADT/ilist_node.h"
 #include "llvm/Support/Casting.h"
-#include "llvm/Support/DataTypes.h"
+#include "llvm/System/DataTypes.h"
 #include <vector> // FIXME: Shouldn't be needed.
 
 namespace llvm {
diff --git a/include/llvm/MC/MCDisassembler.h b/include/llvm/MC/MCDisassembler.h
index ef10b80..ffa0e41 100644
--- a/include/llvm/MC/MCDisassembler.h
+++ b/include/llvm/MC/MCDisassembler.h
@@ -9,7 +9,7 @@
 #ifndef MCDISASSEMBLER_H
 #define MCDISASSEMBLER_H
 
-#include "llvm/Support/DataTypes.h"
+#include "llvm/System/DataTypes.h"
 
 namespace llvm {
   
diff --git a/include/llvm/MC/MCExpr.h b/include/llvm/MC/MCExpr.h
index 7a2a0d5..4318628 100644
--- a/include/llvm/MC/MCExpr.h
+++ b/include/llvm/MC/MCExpr.h
@@ -11,7 +11,7 @@
 #define LLVM_MC_MCEXPR_H
 
 #include "llvm/Support/Casting.h"
-#include "llvm/Support/DataTypes.h"
+#include "llvm/System/DataTypes.h"
 
 namespace llvm {
 class MCAsmInfo;
diff --git a/include/llvm/MC/MCInst.h b/include/llvm/MC/MCInst.h
index 0fc4d18..29b38dd 100644
--- a/include/llvm/MC/MCInst.h
+++ b/include/llvm/MC/MCInst.h
@@ -17,7 +17,7 @@
 #define LLVM_MC_MCINST_H
 
 #include "llvm/ADT/SmallVector.h"
-#include "llvm/Support/DataTypes.h"
+#include "llvm/System/DataTypes.h"
 
 namespace llvm {
 class raw_ostream;
@@ -43,7 +43,6 @@ class MCOperand {
 public:
   
   MCOperand() : Kind(kInvalid) {}
-  MCOperand(const MCOperand &RHS) { *this = RHS; }
 
   bool isValid() const { return Kind != kInvalid; }
   bool isReg() const { return Kind == kRegister; }
diff --git a/include/llvm/MC/MCStreamer.h b/include/llvm/MC/MCStreamer.h
index 248e6b0..4d72f32 100644
--- a/include/llvm/MC/MCStreamer.h
+++ b/include/llvm/MC/MCStreamer.h
@@ -14,7 +14,7 @@
 #ifndef LLVM_MC_MCSTREAMER_H
 #define LLVM_MC_MCSTREAMER_H
 
-#include "llvm/Support/DataTypes.h"
+#include "llvm/System/DataTypes.h"
 
 namespace llvm {
   class MCAsmInfo;
diff --git a/include/llvm/MC/MCSymbol.h b/include/llvm/MC/MCSymbol.h
index d08f0e5..c6efe72 100644
--- a/include/llvm/MC/MCSymbol.h
+++ b/include/llvm/MC/MCSymbol.h
@@ -16,7 +16,7 @@
 
 #include <string>
 #include "llvm/ADT/StringRef.h"
-#include "llvm/Support/DataTypes.h"
+#include "llvm/System/DataTypes.h"
 
 namespace llvm {
   class MCAsmInfo;
diff --git a/include/llvm/MC/MCValue.h b/include/llvm/MC/MCValue.h
index 62aca6e..4f5ab31 100644
--- a/include/llvm/MC/MCValue.h
+++ b/include/llvm/MC/MCValue.h
@@ -14,7 +14,7 @@
 #ifndef LLVM_MC_MCVALUE_H
 #define LLVM_MC_MCVALUE_H
 
-#include "llvm/Support/DataTypes.h"
+#include "llvm/System/DataTypes.h"
 #include "llvm/MC/MCSymbol.h"
 #include <cassert>
 
diff --git a/include/llvm/Metadata.h b/include/llvm/Metadata.h
index c983015..ed87d42 100644
--- a/include/llvm/Metadata.h
+++ b/include/llvm/Metadata.h
@@ -63,7 +63,7 @@ public:
   
   StringRef getString() const { return Str; }
 
-  unsigned getLength() const { return Str.size(); }
+  unsigned getLength() const { return (unsigned)Str.size(); }
 
   typedef StringRef::iterator iterator;
   
@@ -191,7 +191,7 @@ public:
 
   /// getNumElements - Return number of NamedMDNode elements.
   unsigned getNumElements() const {
-    return Node.size();
+    return (unsigned)Node.size();
   }
 
   /// addElement - Add metadata element.
diff --git a/include/llvm/Module.h b/include/llvm/Module.h
index 501625d..70eba68 100644
--- a/include/llvm/Module.h
+++ b/include/llvm/Module.h
@@ -19,7 +19,7 @@
 #include "llvm/GlobalVariable.h"
 #include "llvm/GlobalAlias.h"
 #include "llvm/Metadata.h"
-#include "llvm/Support/DataTypes.h"
+#include "llvm/System/DataTypes.h"
 #include <vector>
 
 namespace llvm {
@@ -252,6 +252,7 @@ public:
                                 AttrListPtr AttributeList,
                                 const Type *RetTy, ...)  END_WITH_NULL;
 
+  /// getOrInsertFunction - Same as above, but without the attributes.
   Constant *getOrInsertFunction(const StringRef &Name, const Type *RetTy, ...)
     END_WITH_NULL;
 
diff --git a/include/llvm/Pass.h b/include/llvm/Pass.h
index 2791936..6bef2e7 100644
--- a/include/llvm/Pass.h
+++ b/include/llvm/Pass.h
@@ -29,7 +29,7 @@
 #ifndef LLVM_PASS_H
 #define LLVM_PASS_H
 
-#include "llvm/Support/DataTypes.h"
+#include "llvm/System/DataTypes.h"
 #include <cassert>
 #include <utility>
 #include <vector>
diff --git a/include/llvm/Support/Allocator.h b/include/llvm/Support/Allocator.h
index 4c84878..b0ed33d 100644
--- a/include/llvm/Support/Allocator.h
+++ b/include/llvm/Support/Allocator.h
@@ -15,7 +15,7 @@
 #define LLVM_SUPPORT_ALLOCATOR_H
 
 #include "llvm/Support/AlignOf.h"
-#include "llvm/Support/DataTypes.h"
+#include "llvm/System/DataTypes.h"
 #include <cassert>
 #include <cstdlib>
 
diff --git a/include/llvm/Support/ConstantRange.h b/include/llvm/Support/ConstantRange.h
index e9c8c7c..3846d46 100644
--- a/include/llvm/Support/ConstantRange.h
+++ b/include/llvm/Support/ConstantRange.h
@@ -33,7 +33,7 @@
 #define LLVM_SUPPORT_CONSTANT_RANGE_H
 
 #include "llvm/ADT/APInt.h"
-#include "llvm/Support/DataTypes.h"
+#include "llvm/System/DataTypes.h"
 
 namespace llvm {
 
diff --git a/include/llvm/Support/Debug.h b/include/llvm/Support/Debug.h
index 6f82ea7..afa828c 100644
--- a/include/llvm/Support/Debug.h
+++ b/include/llvm/Support/Debug.h
@@ -28,39 +28,47 @@
 
 namespace llvm {
 
-// DebugFlag - This boolean is set to true if the '-debug' command line option
-// is specified.  This should probably not be referenced directly, instead, use
-// the DEBUG macro below.
-//
-#ifndef NDEBUG
-extern bool DebugFlag;
+/// DEBUG_TYPE macro - Files can specify a DEBUG_TYPE as a string, which causes
+/// all of their DEBUG statements to be activatable with -debug-only=thatstring.
+#ifndef DEBUG_TYPE
+#define DEBUG_TYPE ""
 #endif
-
-// isCurrentDebugType - Return true if the specified string is the debug type
-// specified on the command line, or if none was specified on the command line
-// with the -debug-only=X option.
-//
+  
 #ifndef NDEBUG
+/// DebugFlag - This boolean is set to true if the '-debug' command line option
+/// is specified.  This should probably not be referenced directly, instead, use
+/// the DEBUG macro below.
+///
+extern bool DebugFlag;
+  
+/// isCurrentDebugType - Return true if the specified string is the debug type
+/// specified on the command line, or if none was specified on the command line
+/// with the -debug-only=X option.
+///
 bool isCurrentDebugType(const char *Type);
-#else
-#define isCurrentDebugType(X) (false)
-#endif
-
-// DEBUG_WITH_TYPE macro - This macro should be used by passes to emit debug
-// information.  In the '-debug' option is specified on the commandline, and if
-// this is a debug build, then the code specified as the option to the macro
-// will be executed.  Otherwise it will not be.  Example:
-//
-// DEBUG_WITH_TYPE("bitset", errs() << "Bitset contains: " << Bitset << "\n");
-//
-// This will emit the debug information if -debug is present, and -debug-only is
-// not specified, or is specified as "bitset".
 
-#ifdef NDEBUG
-#define DEBUG_WITH_TYPE(TYPE, X) do { } while (0)
-#else
+/// SetCurrentDebugType - Set the current debug type, as if the -debug-only=X
+/// option were specified.  Note that DebugFlag also needs to be set to true for
+/// debug output to be produced.
+///
+void SetCurrentDebugType(const char *Type);
+  
+/// DEBUG_WITH_TYPE macro - This macro should be used by passes to emit debug
+/// information.  In the '-debug' option is specified on the commandline, and if
+/// this is a debug build, then the code specified as the option to the macro
+/// will be executed.  Otherwise it will not be.  Example:
+///
+/// DEBUG_WITH_TYPE("bitset", errs() << "Bitset contains: " << Bitset << "\n");
+///
+/// This will emit the debug information if -debug is present, and -debug-only
+/// is not specified, or is specified as "bitset".
 #define DEBUG_WITH_TYPE(TYPE, X)                                        \
   do { if (DebugFlag && isCurrentDebugType(TYPE)) { X; } } while (0)
+
+#else
+#define isCurrentDebugType(X) (false)
+#define SetCurrentDebugType(X)
+#define DEBUG_WITH_TYPE(TYPE, X) do { } while (0)
 #endif
 
 // DEBUG macro - This macro should be used by passes to emit debug information.
@@ -70,11 +78,6 @@ bool isCurrentDebugType(const char *Type);
 //
 // DEBUG(errs() << "Bitset contains: " << Bitset << "\n");
 //
-
-#ifndef DEBUG_TYPE
-#define DEBUG_TYPE ""
-#endif
-
 #define DEBUG(X) DEBUG_WITH_TYPE(DEBUG_TYPE, X)
   
 } // End llvm namespace
diff --git a/include/llvm/Support/ELF.h b/include/llvm/Support/ELF.h
index aa27946..e747c7a 100644
--- a/include/llvm/Support/ELF.h
+++ b/include/llvm/Support/ELF.h
@@ -21,7 +21,7 @@
 #ifndef LLVM_SUPPORT_ELF_H
 #define LLVM_SUPPORT_ELF_H
 
-#include "llvm/Support/DataTypes.h"
+#include "llvm/System/DataTypes.h"
 #include <cstring>
 
 namespace llvm {
diff --git a/include/llvm/Support/IRBuilder.h b/include/llvm/Support/IRBuilder.h
index 83df9ed..4652e8f 100644
--- a/include/llvm/Support/IRBuilder.h
+++ b/include/llvm/Support/IRBuilder.h
@@ -253,6 +253,13 @@ public:
     return Insert(SwitchInst::Create(V, Dest, NumCases));
   }
 
+  /// CreateIndirectBr - Create an indirect branch instruction with the
+  /// specified address operand, with an optional hint for the number of
+  /// destinations that will be added (for efficient allocation).
+  IndirectBrInst *CreateIndirectBr(Value *Addr, unsigned NumDests = 10) {
+    return Insert(IndirectBrInst::Create(Addr, NumDests));
+  }
+
   /// CreateInvoke - Create an invoke instruction.
   template<typename InputIterator>
   InvokeInst *CreateInvoke(Value *Callee, BasicBlock *NormalDest,
@@ -383,15 +390,21 @@ public:
     return Insert(BinaryOperator::CreateAShr(LHS, RHS), Name);
   }
   Value *CreateAnd(Value *LHS, Value *RHS, const Twine &Name = "") {
-    if (Constant *LC = dyn_cast<Constant>(LHS))
-      if (Constant *RC = dyn_cast<Constant>(RHS))
+    if (Constant *RC = dyn_cast<Constant>(RHS)) {
+      if (isa<ConstantInt>(RC) && cast<ConstantInt>(RC)->isAllOnesValue())
+        return LHS;  // LHS & -1 -> LHS
+      if (Constant *LC = dyn_cast<Constant>(LHS))
         return Folder.CreateAnd(LC, RC);
+    }
     return Insert(BinaryOperator::CreateAnd(LHS, RHS), Name);
   }
   Value *CreateOr(Value *LHS, Value *RHS, const Twine &Name = "") {
-    if (Constant *LC = dyn_cast<Constant>(LHS))
-      if (Constant *RC = dyn_cast<Constant>(RHS))
+    if (Constant *RC = dyn_cast<Constant>(RHS)) {
+      if (RC->isNullValue())
+        return LHS;  // LHS | 0 -> LHS
+      if (Constant *LC = dyn_cast<Constant>(LHS))
         return Folder.CreateOr(LC, RC);
+    }
     return Insert(BinaryOperator::CreateOr(LHS, RHS), Name);
   }
   Value *CreateXor(Value *LHS, Value *RHS, const Twine &Name = "") {
@@ -433,9 +446,6 @@ public:
                            const Twine &Name = "") {
     return Insert(new AllocaInst(Ty, ArraySize), Name);
   }
-  FreeInst *CreateFree(Value *Ptr) {
-    return Insert(new FreeInst(Ptr));
-  }
   // Provided to resolve 'CreateLoad(Ptr, "...")' correctly, instead of
   // converting the string to 'bool' for the isVolatile parameter.
   LoadInst *CreateLoad(Value *Ptr, const char *Name) {
diff --git a/include/llvm/Support/InstVisitor.h b/include/llvm/Support/InstVisitor.h
index 440657c..b2e5d58 100644
--- a/include/llvm/Support/InstVisitor.h
+++ b/include/llvm/Support/InstVisitor.h
@@ -160,13 +160,13 @@ public:
   RetTy visitReturnInst(ReturnInst &I)              { DELEGATE(TerminatorInst);}
   RetTy visitBranchInst(BranchInst &I)              { DELEGATE(TerminatorInst);}
   RetTy visitSwitchInst(SwitchInst &I)              { DELEGATE(TerminatorInst);}
+  RetTy visitIndirectBrInst(IndirectBrInst &I)      { DELEGATE(TerminatorInst);}
   RetTy visitInvokeInst(InvokeInst &I)              { DELEGATE(TerminatorInst);}
   RetTy visitUnwindInst(UnwindInst &I)              { DELEGATE(TerminatorInst);}
   RetTy visitUnreachableInst(UnreachableInst &I)    { DELEGATE(TerminatorInst);}
   RetTy visitICmpInst(ICmpInst &I)                  { DELEGATE(CmpInst);}
   RetTy visitFCmpInst(FCmpInst &I)                  { DELEGATE(CmpInst);}
-  RetTy visitAllocaInst(AllocaInst &I)              { DELEGATE(AllocationInst);}
-  RetTy visitFreeInst(FreeInst     &I)              { DELEGATE(Instruction); }
+  RetTy visitAllocaInst(AllocaInst &I)              { DELEGATE(Instruction); }
   RetTy visitLoadInst(LoadInst     &I)              { DELEGATE(Instruction); }
   RetTy visitStoreInst(StoreInst   &I)              { DELEGATE(Instruction); }
   RetTy visitGetElementPtrInst(GetElementPtrInst &I){ DELEGATE(Instruction); }
@@ -198,7 +198,6 @@ public:
   //
   RetTy visitTerminatorInst(TerminatorInst &I) { DELEGATE(Instruction); }
   RetTy visitBinaryOperator(BinaryOperator &I) { DELEGATE(Instruction); }
-  RetTy visitAllocationInst(AllocationInst &I) { DELEGATE(Instruction); }
   RetTy visitCmpInst(CmpInst &I)               { DELEGATE(Instruction); }
   RetTy visitCastInst(CastInst &I)             { DELEGATE(Instruction); }
 
diff --git a/include/llvm/Support/MathExtras.h b/include/llvm/Support/MathExtras.h
index 6fa618e..438b021e 100644
--- a/include/llvm/Support/MathExtras.h
+++ b/include/llvm/Support/MathExtras.h
@@ -14,7 +14,7 @@
 #ifndef LLVM_SUPPORT_MATHEXTRAS_H
 #define LLVM_SUPPORT_MATHEXTRAS_H
 
-#include "llvm/Support/DataTypes.h"
+#include "llvm/System/DataTypes.h"
 
 namespace llvm {
 
diff --git a/include/llvm/Support/MemoryBuffer.h b/include/llvm/Support/MemoryBuffer.h
index eb4784c..f9a4d6d 100644
--- a/include/llvm/Support/MemoryBuffer.h
+++ b/include/llvm/Support/MemoryBuffer.h
@@ -15,7 +15,7 @@
 #define LLVM_SUPPORT_MEMORYBUFFER_H
 
 #include "llvm/ADT/StringRef.h"
-#include "llvm/Support/DataTypes.h"
+#include "llvm/System/DataTypes.h"
 #include <string>
 
 namespace llvm {
diff --git a/include/llvm/Support/MemoryObject.h b/include/llvm/Support/MemoryObject.h
index dec0f13..e193ca2 100644
--- a/include/llvm/Support/MemoryObject.h
+++ b/include/llvm/Support/MemoryObject.h
@@ -10,7 +10,7 @@
 #ifndef MEMORYOBJECT_H
 #define MEMORYOBJECT_H
 
-#include "llvm/Support/DataTypes.h"
+#include "llvm/System/DataTypes.h"
 
 namespace llvm {
 
diff --git a/include/llvm/Support/PointerLikeTypeTraits.h b/include/llvm/Support/PointerLikeTypeTraits.h
index d64993f..b851404 100644
--- a/include/llvm/Support/PointerLikeTypeTraits.h
+++ b/include/llvm/Support/PointerLikeTypeTraits.h
@@ -15,7 +15,7 @@
 #ifndef LLVM_SUPPORT_POINTERLIKETYPETRAITS_H
 #define LLVM_SUPPORT_POINTERLIKETYPETRAITS_H
 
-#include "llvm/Support/DataTypes.h"
+#include "llvm/System/DataTypes.h"
 
 namespace llvm {
   
@@ -38,7 +38,7 @@ public:
     return static_cast<T*>(P);
   }
   
-  /// Note, we assume here that malloc returns objects at least 8-byte aligned.
+  /// Note, we assume here that malloc returns objects at least 4-byte aligned.
   /// However, this may be wrong, or pointers may be from something other than
   /// malloc.  In this case, you should specialize this template to reduce this.
   ///
diff --git a/include/llvm/Support/SlowOperationInformer.h b/include/llvm/Support/SlowOperationInformer.h
index b30aa98..524049c 100644
--- a/include/llvm/Support/SlowOperationInformer.h
+++ b/include/llvm/Support/SlowOperationInformer.h
@@ -31,7 +31,7 @@
 
 #include <string>
 #include <cassert>
-#include "llvm/Support/DataTypes.h"
+#include "llvm/System/DataTypes.h"
 
 namespace llvm {
   class SlowOperationInformer {
diff --git a/include/llvm/Support/StandardPasses.h b/include/llvm/Support/StandardPasses.h
index c71e6b9..1a6d06b 100644
--- a/include/llvm/Support/StandardPasses.h
+++ b/include/llvm/Support/StandardPasses.h
@@ -96,41 +96,43 @@ namespace llvm {
       return;
     }
     
-    if (UnitAtATime)
-      PM->add(createRaiseAllocationsPass());    // call %malloc -> malloc inst
-    PM->add(createCFGSimplificationPass());     // Clean up disgusting code
     if (UnitAtATime) {
       PM->add(createGlobalOptimizerPass());     // Optimize out global vars
-      PM->add(createGlobalDCEPass());           // Remove unused fns and globs
-      // IP Constant Propagation
-      PM->add(createIPConstantPropagationPass());
+      
+      PM->add(createIPSCCPPass());              // IP SCCP
       PM->add(createDeadArgEliminationPass());  // Dead argument elimination
     }
     PM->add(createInstructionCombiningPass());  // Clean up after IPCP & DAE
     PM->add(createCFGSimplificationPass());     // Clean up after IPCP & DAE
-    if (UnitAtATime) {
-      if (HaveExceptions)
-        PM->add(createPruneEHPass());           // Remove dead EH info
-      PM->add(createFunctionAttrsPass());       // Set readonly/readnone attrs
-    }
+    
+    // Start of CallGraph SCC passes.
+    if (UnitAtATime && HaveExceptions)
+      PM->add(createPruneEHPass());           // Remove dead EH info
     if (InliningPass)
       PM->add(InliningPass);
+    if (UnitAtATime)
+      PM->add(createFunctionAttrsPass());       // Set readonly/readnone attrs
     if (OptimizationLevel > 2)
       PM->add(createArgumentPromotionPass());   // Scalarize uninlined fn args
+    
+    // Start of function pass.
+    
+    PM->add(createScalarReplAggregatesPass());  // Break up aggregate allocas
     if (SimplifyLibCalls)
       PM->add(createSimplifyLibCallsPass());    // Library Call Optimizations
     PM->add(createInstructionCombiningPass());  // Cleanup for scalarrepl.
     PM->add(createJumpThreadingPass());         // Thread jumps.
     PM->add(createCFGSimplificationPass());     // Merge & remove BBs
-    PM->add(createScalarReplAggregatesPass());  // Break up aggregate allocas
     PM->add(createInstructionCombiningPass());  // Combine silly seq's
+    
+    // FIXME: CondProp breaks critical edges, which is slow.
     PM->add(createCondPropagationPass());       // Propagate conditionals
     PM->add(createTailCallEliminationPass());   // Eliminate tail calls
     PM->add(createCFGSimplificationPass());     // Merge & remove BBs
     PM->add(createReassociatePass());           // Reassociate expressions
     PM->add(createLoopRotatePass());            // Rotate Loop
     PM->add(createLICMPass());                  // Hoist loop invariants
-    PM->add(createLoopUnswitchPass(OptimizeSize));
+    PM->add(createLoopUnswitchPass(OptimizeSize || OptimizationLevel < 3));
     PM->add(createInstructionCombiningPass());  
     PM->add(createIndVarSimplifyPass());        // Canonicalize indvars
     PM->add(createLoopDeletionPass());          // Delete dead loops
@@ -152,10 +154,15 @@ namespace llvm {
     if (UnitAtATime) {
       PM->add(createStripDeadPrototypesPass()); // Get rid of dead prototypes
       PM->add(createDeadTypeEliminationPass()); // Eliminate dead types
-    }
 
-    if (OptimizationLevel > 1 && UnitAtATime)
-      PM->add(createConstantMergePass());       // Merge dup global constants
+      // GlobalOpt already deletes dead functions and globals, at -O3 try a
+      // late pass of GlobalDCE.  It is capable of deleting dead cycles.
+      if (OptimizationLevel > 2)
+        PM->add(createGlobalDCEPass());         // Remove dead fns and globals.
+    
+      if (OptimizationLevel > 1)
+        PM->add(createConstantMergePass());       // Merge dup global constants
+    }
   }
 
   static inline void addOnePass(PassManager *PM, Pass *P, bool AndVerify) {
diff --git a/include/llvm/Support/TargetFolder.h b/include/llvm/Support/TargetFolder.h
index 8e28632..46ad9b6 100644
--- a/include/llvm/Support/TargetFolder.h
+++ b/include/llvm/Support/TargetFolder.h
@@ -179,6 +179,16 @@ public:
   Constant *CreatePtrToInt(Constant *C, const Type *DestTy) const {
     return CreateCast(Instruction::PtrToInt, C, DestTy);
   }
+  Constant *CreateZExtOrBitCast(Constant *C, const Type *DestTy) const {
+    if (C->getType() == DestTy)
+      return C; // avoid calling Fold
+    return Fold(ConstantExpr::getZExtOrBitCast(C, DestTy));
+  }
+  Constant *CreateSExtOrBitCast(Constant *C, const Type *DestTy) const {
+    if (C->getType() == DestTy)
+      return C; // avoid calling Fold
+    return Fold(ConstantExpr::getSExtOrBitCast(C, DestTy));
+  }
   Constant *CreateTruncOrBitCast(Constant *C, const Type *DestTy) const {
     if (C->getType() == DestTy)
       return C; // avoid calling Fold
diff --git a/include/llvm/Support/Timer.h b/include/llvm/Support/Timer.h
index 54f1da9..8a0f55d 100644
--- a/include/llvm/Support/Timer.h
+++ b/include/llvm/Support/Timer.h
@@ -15,7 +15,7 @@
 #ifndef LLVM_SUPPORT_TIMER_H
 #define LLVM_SUPPORT_TIMER_H
 
-#include "llvm/Support/DataTypes.h"
+#include "llvm/System/DataTypes.h"
 #include "llvm/System/Mutex.h"
 #include <string>
 #include <vector>
diff --git a/include/llvm/Support/raw_ostream.h b/include/llvm/Support/raw_ostream.h
index e67ff85..66d6aaa 100644
--- a/include/llvm/Support/raw_ostream.h
+++ b/include/llvm/Support/raw_ostream.h
@@ -15,7 +15,7 @@
 #define LLVM_SUPPORT_RAW_OSTREAM_H
 
 #include "llvm/ADT/StringRef.h"
-#include "llvm/Support/DataTypes.h"
+#include "llvm/System/DataTypes.h"
 
 namespace llvm {
   class format_object_base;
diff --git a/include/llvm/System/AIXDataTypesFix.h b/include/llvm/System/AIXDataTypesFix.h
new file mode 100644
index 0000000..8dbf02f
--- /dev/null
+++ b/include/llvm/System/AIXDataTypesFix.h
@@ -0,0 +1,25 @@
+//===-- llvm/System/AIXDataTypesFix.h - Fix datatype defs ------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file overrides default system-defined types and limits which cannot be
+// done in DataTypes.h.in because it is processed by autoheader first, which
+// comments out any #undef statement
+//
+//===----------------------------------------------------------------------===//
+
+// No include guards desired!
+
+#ifndef SUPPORT_DATATYPES_H
+#error "AIXDataTypesFix.h must only be included via DataTypes.h!"
+#endif
+
+// GCC is strict about defining large constants: they must have LL modifier.
+// These will be defined properly at the end of DataTypes.h
+#undef INT64_MAX
+#undef INT64_MIN
diff --git a/include/llvm/System/Atomic.h b/include/llvm/System/Atomic.h
index 4ec117b..0c05d69 100644
--- a/include/llvm/System/Atomic.h
+++ b/include/llvm/System/Atomic.h
@@ -14,7 +14,7 @@
 #ifndef LLVM_SYSTEM_ATOMIC_H
 #define LLVM_SYSTEM_ATOMIC_H
 
-#include "llvm/Support/DataTypes.h"
+#include "llvm/System/DataTypes.h"
 
 namespace llvm {
   namespace sys {
diff --git a/include/llvm/System/DataTypes.h.cmake b/include/llvm/System/DataTypes.h.cmake
new file mode 100644
index 0000000..180c86c
--- /dev/null
+++ b/include/llvm/System/DataTypes.h.cmake
@@ -0,0 +1,152 @@
+/*===-- include/System/DataTypes.h - Define fixed size types -----*- C -*-===*\
+|*                                                                            *|
+|*                     The LLVM Compiler Infrastructure                       *|
+|*                                                                            *|
+|* This file is distributed under the University of Illinois Open Source      *|
+|* License. See LICENSE.TXT for details.                                      *|
+|*                                                                            *|
+|*===----------------------------------------------------------------------===*|
+|*                                                                            *|
+|* This file contains definitions to figure out the size of _HOST_ data types.*|
+|* This file is important because different host OS's define different macros,*|
+|* which makes portability tough.  This file exports the following            *|
+|* definitions:                                                               *|
+|*                                                                            *|
+|*   [u]int(32|64)_t : typedefs for signed and unsigned 32/64 bit system types*|
+|*   [U]INT(8|16|32|64)_(MIN|MAX) : Constants for the min and max values.     *|
+|*                                                                            *|
+|* No library is required when using these functinons.                        *|
+|*                                                                            *|
+|*===----------------------------------------------------------------------===*/
+
+/* Please leave this file C-compatible. */
+
+#ifndef SUPPORT_DATATYPES_H
+#define SUPPORT_DATATYPES_H
+
+#cmakedefine HAVE_SYS_TYPES_H ${HAVE_SYS_TYPES_H}
+#cmakedefine HAVE_INTTYPES_H ${HAVE_INTTYPES_H}
+#cmakedefine HAVE_STDINT_H ${HAVE_STDINT_H}
+#cmakedefine HAVE_UINT64_T ${HAVE_UINT64_T}
+#cmakedefine HAVE_U_INT64_T ${HAVE_U_INT64_T}
+
+#ifdef __cplusplus
+#include <cmath>
+#else
+#include <math.h>
+#endif
+
+#ifndef _MSC_VER
+
+/* Note that this header's correct operation depends on __STDC_LIMIT_MACROS
+   being defined.  We would define it here, but in order to prevent Bad Things
+   happening when system headers or C++ STL headers include stdint.h before we
+   define it here, we define it on the g++ command line (in Makefile.rules). */
+#if !defined(__STDC_LIMIT_MACROS)
+# error "Must #define __STDC_LIMIT_MACROS before #including System/DataTypes.h"
+#endif
+
+#if !defined(__STDC_CONSTANT_MACROS)
+# error "Must #define __STDC_CONSTANT_MACROS before " \
+        "#including System/DataTypes.h"
+#endif
+
+/* Note that <inttypes.h> includes <stdint.h>, if this is a C99 system. */
+#ifdef HAVE_SYS_TYPES_H
+#include <sys/types.h>
+#endif
+
+#ifdef HAVE_INTTYPES_H
+#include <inttypes.h>
+#endif
+
+#ifdef HAVE_STDINT_H
+#include <stdint.h>
+#endif
+
+#ifdef _AIX
+#include "llvm/System/AIXDataTypesFix.h"
+#endif
+
+/* Handle incorrect definition of uint64_t as u_int64_t */
+#ifndef HAVE_UINT64_T
+#ifdef HAVE_U_INT64_T
+typedef u_int64_t uint64_t;
+#else
+# error "Don't have a definition for uint64_t on this platform"
+#endif
+#endif
+
+#ifdef _OpenBSD_
+#define INT8_MAX 127
+#define INT8_MIN -128
+#define UINT8_MAX 255
+#define INT16_MAX 32767
+#define INT16_MIN -32768
+#define UINT16_MAX 65535
+#define INT32_MAX 2147483647
+#define INT32_MIN -2147483648
+#define UINT32_MAX 4294967295U
+#endif
+
+#else /* _MSC_VER */
+/* Visual C++ doesn't provide standard integer headers, but it does provide
+   built-in data types. */
+#include <stdlib.h>
+#include <stddef.h>
+#include <sys/types.h>
+#ifdef __cplusplus
+#include <cmath>
+#else
+#include <math.h>
+#endif
+typedef __int64 int64_t;
+typedef unsigned __int64 uint64_t;
+typedef signed int int32_t;
+typedef unsigned int uint32_t;
+typedef short int16_t;
+typedef unsigned short uint16_t;
+typedef signed char int8_t;
+typedef unsigned char uint8_t;
+typedef signed int ssize_t;
+#define INT8_MAX 127
+#define INT8_MIN -128
+#define UINT8_MAX 255
+#define INT16_MAX 32767
+#define INT16_MIN -32768
+#define UINT16_MAX 65535
+#define INT32_MAX 2147483647
+#define INT32_MIN -2147483648
+#define UINT32_MAX 4294967295U
+#define INT8_C(C)   C
+#define UINT8_C(C)  C
+#define INT16_C(C)  C
+#define UINT16_C(C) C
+#define INT32_C(C)  C
+#define UINT32_C(C) C ## U
+#define INT64_C(C)  ((int64_t) C ## LL)
+#define UINT64_C(C) ((uint64_t) C ## ULL)
+#endif /* _MSC_VER */
+
+/* Set defaults for constants which we cannot find. */
+#if !defined(INT64_MAX)
+# define INT64_MAX 9223372036854775807LL
+#endif
+#if !defined(INT64_MIN)
+# define INT64_MIN ((-INT64_MAX)-1)
+#endif
+#if !defined(UINT64_MAX)
+# define UINT64_MAX 0xffffffffffffffffULL
+#endif
+
+#if __GNUC__ > 3
+#define END_WITH_NULL __attribute__((sentinel))
+#else
+#define END_WITH_NULL
+#endif
+
+#ifndef HUGE_VALF
+#define HUGE_VALF (float)HUGE_VAL
+#endif
+
+#endif  /* SUPPORT_DATATYPES_H */
diff --git a/include/llvm/System/DataTypes.h.in b/include/llvm/System/DataTypes.h.in
new file mode 100644
index 0000000..d574910
--- /dev/null
+++ b/include/llvm/System/DataTypes.h.in
@@ -0,0 +1,147 @@
+/*===-- include/System/DataTypes.h - Define fixed size types -----*- C -*-===*\
+|*                                                                            *|
+|*                     The LLVM Compiler Infrastructure                       *|
+|*                                                                            *|
+|* This file is distributed under the University of Illinois Open Source      *|
+|* License. See LICENSE.TXT for details.                                      *|
+|*                                                                            *|
+|*===----------------------------------------------------------------------===*|
+|*                                                                            *|
+|* This file contains definitions to figure out the size of _HOST_ data types.*|
+|* This file is important because different host OS's define different macros,*|
+|* which makes portability tough.  This file exports the following            *|
+|* definitions:                                                               *|
+|*                                                                            *|
+|*   [u]int(32|64)_t : typedefs for signed and unsigned 32/64 bit system types*|
+|*   [U]INT(8|16|32|64)_(MIN|MAX) : Constants for the min and max values.     *|
+|*                                                                            *|
+|* No library is required when using these functinons.                        *|
+|*                                                                            *|
+|*===----------------------------------------------------------------------===*/
+
+/* Please leave this file C-compatible. */
+
+#ifndef SUPPORT_DATATYPES_H
+#define SUPPORT_DATATYPES_H
+
+#undef HAVE_SYS_TYPES_H
+#undef HAVE_INTTYPES_H
+#undef HAVE_STDINT_H
+#undef HAVE_UINT64_T
+#undef HAVE_U_INT64_T
+
+#ifdef __cplusplus
+#include <cmath>
+#else
+#include <math.h>
+#endif
+
+#ifndef _MSC_VER
+
+/* Note that this header's correct operation depends on __STDC_LIMIT_MACROS
+   being defined.  We would define it here, but in order to prevent Bad Things
+   happening when system headers or C++ STL headers include stdint.h before we
+   define it here, we define it on the g++ command line (in Makefile.rules). */
+#if !defined(__STDC_LIMIT_MACROS)
+# error "Must #define __STDC_LIMIT_MACROS before #including System/DataTypes.h"
+#endif
+
+#if !defined(__STDC_CONSTANT_MACROS)
+# error "Must #define __STDC_CONSTANT_MACROS before " \
+        "#including System/DataTypes.h"
+#endif
+
+/* Note that <inttypes.h> includes <stdint.h>, if this is a C99 system. */
+#ifdef HAVE_SYS_TYPES_H
+#include <sys/types.h>
+#endif
+
+#ifdef HAVE_INTTYPES_H
+#include <inttypes.h>
+#endif
+
+#ifdef HAVE_STDINT_H
+#include <stdint.h>
+#endif
+
+#ifdef _AIX
+#include "llvm/System/AIXDataTypesFix.h"
+#endif
+
+/* Handle incorrect definition of uint64_t as u_int64_t */
+#ifndef HAVE_UINT64_T
+#ifdef HAVE_U_INT64_T
+typedef u_int64_t uint64_t;
+#else
+# error "Don't have a definition for uint64_t on this platform"
+#endif
+#endif
+
+#ifdef _OpenBSD_
+#define INT8_MAX 127
+#define INT8_MIN -128
+#define UINT8_MAX 255
+#define INT16_MAX 32767
+#define INT16_MIN -32768
+#define UINT16_MAX 65535
+#define INT32_MAX 2147483647
+#define INT32_MIN -2147483648
+#define UINT32_MAX 4294967295U
+#endif
+
+#else /* _MSC_VER */
+/* Visual C++ doesn't provide standard integer headers, but it does provide
+   built-in data types. */
+#include <stdlib.h>
+#include <stddef.h>
+#include <sys/types.h>
+typedef __int64 int64_t;
+typedef unsigned __int64 uint64_t;
+typedef signed int int32_t;
+typedef unsigned int uint32_t;
+typedef short int16_t;
+typedef unsigned short uint16_t;
+typedef signed char int8_t;
+typedef unsigned char uint8_t;
+typedef signed int ssize_t;
+#define INT8_MAX 127
+#define INT8_MIN -128
+#define UINT8_MAX 255
+#define INT16_MAX 32767
+#define INT16_MIN -32768
+#define UINT16_MAX 65535
+#define INT32_MAX 2147483647
+#define INT32_MIN -2147483648
+#define UINT32_MAX 4294967295U
+#define INT8_C(C)   C
+#define UINT8_C(C)  C
+#define INT16_C(C)  C
+#define UINT16_C(C) C
+#define INT32_C(C)  C
+#define UINT32_C(C) C ## U
+#define INT64_C(C)  ((int64_t) C ## LL)
+#define UINT64_C(C) ((uint64_t) C ## ULL)
+#endif /* _MSC_VER */
+
+/* Set defaults for constants which we cannot find. */
+#if !defined(INT64_MAX)
+# define INT64_MAX 9223372036854775807LL
+#endif
+#if !defined(INT64_MIN)
+# define INT64_MIN ((-INT64_MAX)-1)
+#endif
+#if !defined(UINT64_MAX)
+# define UINT64_MAX 0xffffffffffffffffULL
+#endif
+
+#if __GNUC__ > 3
+#define END_WITH_NULL __attribute__((sentinel))
+#else
+#define END_WITH_NULL
+#endif
+
+#ifndef HUGE_VALF
+#define HUGE_VALF (float)HUGE_VAL
+#endif
+
+#endif  /* SUPPORT_DATATYPES_H */
diff --git a/include/llvm/System/Disassembler.h b/include/llvm/System/Disassembler.h
index 6d1cc0f..e11e792 100644
--- a/include/llvm/System/Disassembler.h
+++ b/include/llvm/System/Disassembler.h
@@ -15,7 +15,7 @@
 #ifndef LLVM_SYSTEM_DISASSEMBLER_H
 #define LLVM_SYSTEM_DISASSEMBLER_H
 
-#include "llvm/Support/DataTypes.h"
+#include "llvm/System/DataTypes.h"
 #include <string>
 
 namespace llvm {
diff --git a/include/llvm/System/Memory.h b/include/llvm/System/Memory.h
index d6300db..69251dd 100644
--- a/include/llvm/System/Memory.h
+++ b/include/llvm/System/Memory.h
@@ -14,7 +14,7 @@
 #ifndef LLVM_SYSTEM_MEMORY_H
 #define LLVM_SYSTEM_MEMORY_H
 
-#include "llvm/Support/DataTypes.h"
+#include "llvm/System/DataTypes.h"
 #include <string>
 
 namespace llvm {
diff --git a/include/llvm/System/TimeValue.h b/include/llvm/System/TimeValue.h
index 10997304..168e2a7 100644
--- a/include/llvm/System/TimeValue.h
+++ b/include/llvm/System/TimeValue.h
@@ -11,7 +11,7 @@
 //
 //===----------------------------------------------------------------------===//
 
-#include "llvm/Support/DataTypes.h"
+#include "llvm/System/DataTypes.h"
 #include <string>
 
 #ifndef LLVM_SYSTEM_TIMEVALUE_H
diff --git a/include/llvm/Target/SubtargetFeature.h b/include/llvm/Target/SubtargetFeature.h
index 58333e2..a709f52 100644
--- a/include/llvm/Target/SubtargetFeature.h
+++ b/include/llvm/Target/SubtargetFeature.h
@@ -21,7 +21,7 @@
 #include <string>
 #include <vector>
 #include <cstring>
-#include "llvm/Support/DataTypes.h"
+#include "llvm/System/DataTypes.h"
 
 namespace llvm {
   class raw_ostream;
diff --git a/include/llvm/Target/Target.td b/include/llvm/Target/Target.td
index 4d65b19..edb8582 100644
--- a/include/llvm/Target/Target.td
+++ b/include/llvm/Target/Target.td
@@ -199,7 +199,7 @@ class Instruction {
   bit isReMaterializable = 0; // Is this instruction re-materializable?
   bit isPredicable = 0;     // Is this instruction predicable?
   bit hasDelaySlot = 0;     // Does this instruction have an delay slot?
-  bit usesCustomDAGSchedInserter = 0; // Pseudo instr needing special help.
+  bit usesCustomInserter = 0; // Pseudo instr needing special help.
   bit hasCtrlDep   = 0;     // Does this instruction r/w ctrl-flow chains?
   bit isNotDuplicable = 0;  // Is it unsafe to duplicate this instruction?
   bit isAsCheapAsAMove = 0; // As cheap (or cheaper) than a move instruction.
diff --git a/include/llvm/Target/TargetData.h b/include/llvm/Target/TargetData.h
index f8ea64b..af85f73 100644
--- a/include/llvm/Target/TargetData.h
+++ b/include/llvm/Target/TargetData.h
@@ -21,7 +21,7 @@
 #define LLVM_TARGET_TARGETDATA_H
 
 #include "llvm/Pass.h"
-#include "llvm/Support/DataTypes.h"
+#include "llvm/System/DataTypes.h"
 #include "llvm/Support/ErrorHandling.h"
 #include "llvm/ADT/SmallVector.h"
 #include <string>
diff --git a/include/llvm/Target/TargetInstrDesc.h b/include/llvm/Target/TargetInstrDesc.h
index d828a23..b0ed0bf 100644
--- a/include/llvm/Target/TargetInstrDesc.h
+++ b/include/llvm/Target/TargetInstrDesc.h
@@ -109,7 +109,7 @@ namespace TID {
     UnmodeledSideEffects,
     Commutable,
     ConvertibleTo3Addr,
-    UsesCustomDAGSchedInserter,
+    UsesCustomInserter,
     Rematerializable,
     CheapAsAMove,
     ExtraSrcRegAllocReq,
@@ -416,7 +416,7 @@ public:
     return Flags & (1 << TID::ConvertibleTo3Addr);
   }
   
-  /// usesCustomDAGSchedInsertionHook - Return true if this instruction requires
+  /// usesCustomInsertionHook - Return true if this instruction requires
   /// custom insertion support when the DAG scheduler is inserting it into a
   /// machine basic block.  If this is true for the instruction, it basically
   /// means that it is a pseudo instruction used at SelectionDAG time that is 
@@ -424,8 +424,8 @@ public:
   ///
   /// If this is true, the TargetLoweringInfo::InsertAtEndOfBasicBlock method
   /// is used to insert this into the MachineBasicBlock.
-  bool usesCustomDAGSchedInsertionHook() const {
-    return Flags & (1 << TID::UsesCustomDAGSchedInserter);
+  bool usesCustomInsertionHook() const {
+    return Flags & (1 << TID::UsesCustomInserter);
   }
   
   /// isRematerializable - Returns true if this instruction is a candidate for
diff --git a/include/llvm/Target/TargetInstrInfo.h b/include/llvm/Target/TargetInstrInfo.h
index 919bef1..1d42c32 100644
--- a/include/llvm/Target/TargetInstrInfo.h
+++ b/include/llvm/Target/TargetInstrInfo.h
@@ -133,13 +133,34 @@ private:
                                                 AliasAnalysis *AA) const;
 
 public:
-  /// Return true if the instruction is a register to register move and return
-  /// the source and dest operands and their sub-register indices by reference.
+  /// isMoveInstr - Return true if the instruction is a register to register
+  /// move and return the source and dest operands and their sub-register
+  /// indices by reference.
   virtual bool isMoveInstr(const MachineInstr& MI,
                            unsigned& SrcReg, unsigned& DstReg,
                            unsigned& SrcSubIdx, unsigned& DstSubIdx) const {
     return false;
   }
+
+  /// isIdentityCopy - Return true if the instruction is a copy (or
+  /// extract_subreg, insert_subreg, subreg_to_reg) where the source and
+  /// destination registers are the same.
+  bool isIdentityCopy(const MachineInstr &MI) const {
+    unsigned SrcReg, DstReg, SrcSubIdx, DstSubIdx;
+    if (isMoveInstr(MI, SrcReg, DstReg, SrcSubIdx, DstSubIdx) &&
+        SrcReg == DstReg)
+      return true;
+
+    if (MI.getOpcode() == TargetInstrInfo::EXTRACT_SUBREG &&
+        MI.getOperand(0).getReg() == MI.getOperand(1).getReg())
+    return true;
+
+    if ((MI.getOpcode() == TargetInstrInfo::INSERT_SUBREG ||
+         MI.getOpcode() == TargetInstrInfo::SUBREG_TO_REG) &&
+        MI.getOperand(0).getReg() == MI.getOperand(2).getReg())
+      return true;
+    return false;
+  }
   
   /// isLoadFromStackSlot - If the specified machine instruction is a direct
   /// load from a stack slot, return the virtual or physical register number of
@@ -384,9 +405,12 @@ public:
   /// getOpcodeAfterMemoryUnfold - Returns the opcode of the would be new
   /// instruction after load / store are unfolded from an instruction of the
   /// specified opcode. It returns zero if the specified unfolding is not
-  /// possible.
+  /// possible. If LoadRegIndex is non-null, it is filled in with the operand
+  /// index of the operand which will hold the register holding the loaded
+  /// value.
   virtual unsigned getOpcodeAfterMemoryUnfold(unsigned Opc,
-                                      bool UnfoldLoad, bool UnfoldStore) const {
+                                      bool UnfoldLoad, bool UnfoldStore,
+                                      unsigned *LoadRegIndex = 0) const {
     return 0;
   }
   
diff --git a/include/llvm/Target/TargetJITInfo.h b/include/llvm/Target/TargetJITInfo.h
index 9545689..809f183 100644
--- a/include/llvm/Target/TargetJITInfo.h
+++ b/include/llvm/Target/TargetJITInfo.h
@@ -18,7 +18,7 @@
 #define LLVM_TARGET_TARGETJITINFO_H
 
 #include <cassert>
-#include "llvm/Support/DataTypes.h"
+#include "llvm/System/DataTypes.h"
 
 namespace llvm {
   class Function;
diff --git a/include/llvm/Target/TargetLowering.h b/include/llvm/Target/TargetLowering.h
index 4f567b0..8bc39d0 100644
--- a/include/llvm/Target/TargetLowering.h
+++ b/include/llvm/Target/TargetLowering.h
@@ -325,12 +325,11 @@ public:
   /// scalarizing vs using the wider vector type.
   virtual EVT getWidenVectorType(EVT VT) const;
 
-  typedef std::vector<APFloat>::const_iterator legal_fpimm_iterator;
-  legal_fpimm_iterator legal_fpimm_begin() const {
-    return LegalFPImmediates.begin();
-  }
-  legal_fpimm_iterator legal_fpimm_end() const {
-    return LegalFPImmediates.end();
+  /// isFPImmLegal - Returns true if the target can instruction select the
+  /// specified FP immediate natively. If false, the legalizer will materialize
+  /// the FP immediate as a load from a constant pool.
+  virtual bool isFPImmLegal(const APFloat &Imm, EVT VT) const {
+    return false;
   }
   
   /// isShuffleMaskLegal - Targets can use this to indicate that they only
@@ -1051,12 +1050,6 @@ protected:
     PromoteToType[std::make_pair(Opc, OrigVT.SimpleTy)] = DestVT.SimpleTy;
   }
 
-  /// addLegalFPImmediate - Indicate that this target can instruction select
-  /// the specified FP immediate natively.
-  void addLegalFPImmediate(const APFloat& Imm) {
-    LegalFPImmediates.push_back(Imm);
-  }
-
   /// setTargetDAGCombine - Targets should invoke this method for each target
   /// independent node that they want to provide a custom DAG combiner for by
   /// implementing the PerformDAGCombine virtual method.
@@ -1432,14 +1425,15 @@ public:
                                             SelectionDAG &DAG) const;
   
   //===--------------------------------------------------------------------===//
-  // Scheduler hooks
+  // Instruction Emitting Hooks
   //
   
   // EmitInstrWithCustomInserter - This method should be implemented by targets
-  // that mark instructions with the 'usesCustomDAGSchedInserter' flag.  These
+  // that mark instructions with the 'usesCustomInserter' flag.  These
   // instructions are special in various ways, which require special support to
   // insert.  The specified MachineInstr is created but not inserted into any
-  // basic blocks, and the scheduler passes ownership of it to this method.
+  // basic blocks, and this method is called to expand it into a sequence of
+  // instructions, potentially also creating new basic blocks and control flow.
   // When new basic blocks are inserted and the edges from MBB to its successors
   // are modified, the method should insert pairs of <OldSucc, NewSucc> into the
   // DenseMap.
@@ -1696,8 +1690,6 @@ private:
 
   ValueTypeActionImpl ValueTypeActions;
 
-  std::vector<APFloat> LegalFPImmediates;
-
   std::vector<std::pair<EVT, TargetRegisterClass*> > AvailableRegClasses;
 
   /// TargetDAGCombineArray - Targets can specify ISD nodes that they would
diff --git a/include/llvm/Target/TargetSelectionDAG.td b/include/llvm/Target/TargetSelectionDAG.td
index 700c64c..f123d66 100644
--- a/include/llvm/Target/TargetSelectionDAG.td
+++ b/include/llvm/Target/TargetSelectionDAG.td
@@ -269,6 +269,10 @@ def externalsym : SDNode<"ISD::ExternalSymbol",       SDTPtrLeaf, [],
                          "ExternalSymbolSDNode">;
 def texternalsym: SDNode<"ISD::TargetExternalSymbol", SDTPtrLeaf, [],
                          "ExternalSymbolSDNode">;
+def blockaddress : SDNode<"ISD::BlockAddress",        SDTPtrLeaf, [],
+                         "BlockAddressSDNode">;
+def tblockaddress: SDNode<"ISD::TargetBlockAddress",  SDTPtrLeaf, [],
+                         "BlockAddressSDNode">;
 
 def add        : SDNode<"ISD::ADD"       , SDTIntBinOp   ,
                         [SDNPCommutative, SDNPAssociative]>;
@@ -325,6 +329,8 @@ def fneg       : SDNode<"ISD::FNEG"       , SDTFPUnaryOp>;
 def fsqrt      : SDNode<"ISD::FSQRT"      , SDTFPUnaryOp>;
 def fsin       : SDNode<"ISD::FSIN"       , SDTFPUnaryOp>;
 def fcos       : SDNode<"ISD::FCOS"       , SDTFPUnaryOp>;
+def fexp2      : SDNode<"ISD::FEXP2"      , SDTFPUnaryOp>;
+def flog2      : SDNode<"ISD::FLOG2"      , SDTFPUnaryOp>;
 def frint      : SDNode<"ISD::FRINT"      , SDTFPUnaryOp>;
 def ftrunc     : SDNode<"ISD::FTRUNC"     , SDTFPUnaryOp>;
 def fceil      : SDNode<"ISD::FCEIL"      , SDTFPUnaryOp>;
diff --git a/include/llvm/Transforms/IPO.h b/include/llvm/Transforms/IPO.h
index 9189c43..5e17904 100644
--- a/include/llvm/Transforms/IPO.h
+++ b/include/llvm/Transforms/IPO.h
@@ -69,13 +69,6 @@ ModulePass *createGlobalOptimizerPass();
 
 
 //===----------------------------------------------------------------------===//
-/// createRaiseAllocationsPass - Return a new pass that transforms malloc and
-/// free function calls into malloc and free instructions.
-///
-ModulePass *createRaiseAllocationsPass();
-
-
-//===----------------------------------------------------------------------===//
 /// createDeadTypeEliminationPass - Return a new pass that eliminates symbol
 /// table entries for types that are never used.
 ///
diff --git a/include/llvm/Transforms/Scalar.h b/include/llvm/Transforms/Scalar.h
index fee4e65..523a8f4 100644
--- a/include/llvm/Transforms/Scalar.h
+++ b/include/llvm/Transforms/Scalar.h
@@ -225,15 +225,6 @@ extern const PassInfo *const LoopSimplifyID;
 
 //===----------------------------------------------------------------------===//
 //
-// LowerAllocations - Turn free instructions into @free calls.
-//
-//   AU.addRequiredID(LowerAllocationsID);
-//
-Pass *createLowerAllocationsPass();
-extern const PassInfo *const LowerAllocationsID;
-
-//===----------------------------------------------------------------------===//
-//
 // TailCallElimination - This pass eliminates call instructions to the current
 // function which occur immediately before return instructions.
 //
@@ -280,7 +271,7 @@ extern const PassInfo *const LCSSAID;
 // GVN - This pass performs global value numbering and redundant load 
 // elimination cotemporaneously.
 //
-FunctionPass *createGVNPass();
+FunctionPass *createGVNPass(bool NoPRE = false);
 
 //===----------------------------------------------------------------------===//
 //
@@ -316,12 +307,6 @@ FunctionPass *createCodeGenPreparePass(const TargetLowering *TLI = 0);
 
 //===----------------------------------------------------------------------===//
 //
-// CodeGenLICM - This pass performs late LICM; hoisting constants out of loops.
-//
-Pass *createCodeGenLICMPass();
-  
-//===----------------------------------------------------------------------===//
-//
 // InstructionNamer - Give any unnamed non-void instructions "tmp" names.
 //
 FunctionPass *createInstructionNamerPass();
@@ -341,6 +326,24 @@ FunctionPass *createSSIPass();
 //
 FunctionPass *createSSIEverythingPass();
 
+//===----------------------------------------------------------------------===//
+//
+// GEPSplitter - Split complex GEPs into simple ones
+//
+FunctionPass *createGEPSplitterPass();
+
+//===----------------------------------------------------------------------===//
+//
+// SCCVN - Aggressively eliminate redundant scalar values
+//
+FunctionPass *createSCCVNPass();
+
+//===----------------------------------------------------------------------===//
+//
+// ABCD - Elimination of Array Bounds Checks on Demand
+//
+FunctionPass *createABCDPass();
+
 } // End llvm namespace
 
 #endif
diff --git a/include/llvm/Transforms/Utils/BasicBlockUtils.h b/include/llvm/Transforms/Utils/BasicBlockUtils.h
index e766d72..8172114 100644
--- a/include/llvm/Transforms/Utils/BasicBlockUtils.h
+++ b/include/llvm/Transforms/Utils/BasicBlockUtils.h
@@ -116,8 +116,8 @@ bool isCriticalEdge(const TerminatorInst *TI, unsigned SuccNum,
 /// SplitCriticalEdge - If this edge is a critical edge, insert a new node to
 /// split the critical edge.  This will update DominatorTree and
 /// DominatorFrontier information if it is available, thus calling this pass
-/// will not invalidate either of them. This returns true if the edge was split,
-/// false otherwise.  
+/// will not invalidate either of them. This returns the new block if the edge
+/// was split, null otherwise.
 ///
 /// If MergeIdenticalEdges is true (not the default), *all* edges from TI to the
 /// specified successor will be merged into the same critical edge block.  
@@ -126,10 +126,16 @@ bool isCriticalEdge(const TerminatorInst *TI, unsigned SuccNum,
 /// dest go to one block instead of each going to a different block, but isn't 
 /// the standard definition of a "critical edge".
 ///
+/// It is invalid to call this function on a critical edge that starts at an
+/// IndirectBrInst.  Splitting these edges will almost always create an invalid
+/// program because the address of the new block won't be the one that is jumped
+/// to.
+///
 BasicBlock *SplitCriticalEdge(TerminatorInst *TI, unsigned SuccNum,
                               Pass *P = 0, bool MergeIdenticalEdges = false);
 
-inline BasicBlock *SplitCriticalEdge(BasicBlock *BB, succ_iterator SI, Pass *P = 0) {
+inline BasicBlock *SplitCriticalEdge(BasicBlock *BB, succ_iterator SI,
+                                     Pass *P = 0) {
   return SplitCriticalEdge(BB->getTerminator(), SI.getSuccessorIndex(), P);
 }
 
diff --git a/include/llvm/Transforms/Utils/SSAUpdater.h b/include/llvm/Transforms/Utils/SSAUpdater.h
index ad99c74..2364330 100644
--- a/include/llvm/Transforms/Utils/SSAUpdater.h
+++ b/include/llvm/Transforms/Utils/SSAUpdater.h
@@ -50,7 +50,7 @@ class SSAUpdater {
 public:
   /// SSAUpdater constructor.  If InsertedPHIs is specified, it will be filled
   /// in with all PHI Nodes created by rewriting.
-  SSAUpdater(SmallVectorImpl<PHINode*> *InsertedPHIs = 0);
+  explicit SSAUpdater(SmallVectorImpl<PHINode*> *InsertedPHIs = 0);
   ~SSAUpdater();
 
   /// Initialize - Reset this object to get ready for a new set of SSA
diff --git a/include/llvm/Transforms/Utils/ValueMapper.h b/include/llvm/Transforms/Utils/ValueMapper.h
index d31edab..ed33413 100644
--- a/include/llvm/Transforms/Utils/ValueMapper.h
+++ b/include/llvm/Transforms/Utils/ValueMapper.h
@@ -20,10 +20,9 @@
 namespace llvm {
   class Value;
   class Instruction;
-  class LLVMContext;
   typedef DenseMap<const Value *, Value *> ValueMapTy;
 
-  Value *MapValue(const Value *V, ValueMapTy &VM, LLVMContext &Context);
+  Value *MapValue(const Value *V, ValueMapTy &VM);
   void RemapInstruction(Instruction *I, ValueMapTy &VM);
 } // End llvm namespace
 
diff --git a/include/llvm/Type.h b/include/llvm/Type.h
index 4a470af..752635c 100644
--- a/include/llvm/Type.h
+++ b/include/llvm/Type.h
@@ -12,9 +12,8 @@
 #define LLVM_TYPE_H
 
 #include "llvm/AbstractTypeUser.h"
-#include "llvm/LLVMContext.h"
 #include "llvm/Support/Casting.h"
-#include "llvm/Support/DataTypes.h"
+#include "llvm/System/DataTypes.h"
 #include "llvm/System/Atomic.h"
 #include "llvm/ADT/GraphTraits.h"
 #include <string>
@@ -28,6 +27,7 @@ class IntegerType;
 class TypeMapBase;
 class raw_ostream;
 class Module;
+class LLVMContext;
 
 /// This file contains the declaration of the Type class.  For more "Type" type
 /// stuff, look in DerivedTypes.h.
diff --git a/include/llvm/TypeSymbolTable.h b/include/llvm/TypeSymbolTable.h
index 4dd3a4a..d84196f 100644
--- a/include/llvm/TypeSymbolTable.h
+++ b/include/llvm/TypeSymbolTable.h
@@ -15,6 +15,7 @@
 #define LLVM_TYPE_SYMBOL_TABLE_H
 
 #include "llvm/Type.h"
+#include "llvm/ADT/StringRef.h"
 #include <map>
 
 namespace llvm {
@@ -69,12 +70,16 @@ public:
   /// Lookup the type associated with name.
   /// @returns end() if the name is not found, or an iterator at the entry for
   /// Type.
-  iterator find(const StringRef &name);
+  iterator find(const StringRef &Name) {
+    return tmap.find(Name);
+  }
 
   /// Lookup the type associated with name.
   /// @returns end() if the name is not found, or an iterator at the entry for
   /// Type.
-  const_iterator find(const StringRef &name) const;
+  const_iterator find(const StringRef &Name) const {
+    return tmap.find(Name);
+  }
 
   /// @returns true iff the symbol table is empty.
   /// @brief Determine if the symbol table is empty
diff --git a/include/llvm/Value.h b/include/llvm/Value.h
index c09fdfb..b485524 100644
--- a/include/llvm/Value.h
+++ b/include/llvm/Value.h
@@ -210,6 +210,7 @@ public:
     GlobalAliasVal,           // This is an instance of GlobalAlias
     GlobalVariableVal,        // This is an instance of GlobalVariable
     UndefValueVal,            // This is an instance of UndefValue
+    BlockAddressVal,          // This is an instance of BlockAddress
     ConstantExprVal,          // This is an instance of ConstantExpr
     ConstantAggregateZeroVal, // This is an instance of ConstantAggregateNull
     ConstantIntVal,           // This is an instance of ConstantInt
diff --git a/include/llvm/ValueSymbolTable.h b/include/llvm/ValueSymbolTable.h
index 4f8ebe8..b147c1e 100644
--- a/include/llvm/ValueSymbolTable.h
+++ b/include/llvm/ValueSymbolTable.h
@@ -16,7 +16,7 @@
 
 #include "llvm/Value.h"
 #include "llvm/ADT/StringMap.h"
-#include "llvm/Support/DataTypes.h"
+#include "llvm/System/DataTypes.h"
 
 namespace llvm {
   template<typename ValueSubClass, typename ItemParentClass>