Import LLVM 74788.

8 files changed, 660 insertions, 345 deletions

diff --git a/lib/Analysis/DebugInfo.cpp b/lib/Analysis/DebugInfo.cpp
index 6b27cf4..9eecc33 100644
--- a/lib/Analysis/DebugInfo.cpp
+++ b/lib/Analysis/DebugInfo.cpp
@@ -21,6 +21,7 @@
 #include "llvm/Module.h"
 #include "llvm/Analysis/ValueTracking.h"
 #include "llvm/Support/Dwarf.h"
+#include "llvm/Support/DebugLoc.h"
 #include "llvm/Support/Streams.h"
 
 using namespace llvm;
@@ -321,13 +322,140 @@ bool DISubprogram::describes(const Function *F) {
 }
 
 //===----------------------------------------------------------------------===//
+// DIDescriptor: dump routines for all descriptors.
+//===----------------------------------------------------------------------===//
+
+
+/// dump - Print descriptor.
+void DIDescriptor::dump() const {
+  cerr << "[" << dwarf::TagString(getTag()) << "] ";
+  cerr << std::hex << "[GV:" << DbgGV << "]" << std::dec;
+}
+
+/// dump - Print compile unit.
+void DICompileUnit::dump() const {
+  if (getLanguage())
+    cerr << " [" << dwarf::LanguageString(getLanguage()) << "] ";
+
+  std::string Res1, Res2;
+  cerr << " [" << getDirectory(Res1) << "/" << getFilename(Res2) << " ]";
+}
+
+/// dump - Print type.
+void DIType::dump() const {
+  if (isNull()) return;
+
+  std::string Res;
+  if (!getName(Res).empty())
+    cerr << " [" << Res << "] ";
+
+  unsigned Tag = getTag();
+  cerr << " [" << dwarf::TagString(Tag) << "] ";
+
+  // TODO : Print context
+  getCompileUnit().dump();
+  cerr << " [" 
+       << getLineNumber() << ", " 
+       << getSizeInBits() << ", "
+       << getAlignInBits() << ", "
+       << getOffsetInBits() 
+       << "] ";
+
+  if (isPrivate()) 
+    cerr << " [private] ";
+  else if (isProtected())
+    cerr << " [protected] ";
+
+  if (isForwardDecl())
+    cerr << " [fwd] ";
+
+  if (isBasicType(Tag))
+    DIBasicType(DbgGV).dump();
+  else if (isDerivedType(Tag))
+    DIDerivedType(DbgGV).dump();
+  else if (isCompositeType(Tag))
+    DICompositeType(DbgGV).dump();
+  else {
+    cerr << "Invalid DIType\n";
+    return;
+  }
+
+  cerr << "\n";
+}
+
+/// dump - Print basic type.
+void DIBasicType::dump() const {
+  cerr << " [" << dwarf::AttributeEncodingString(getEncoding()) << "] ";
+}
+
+/// dump - Print derived type.
+void DIDerivedType::dump() const {
+  cerr << "\n\t Derived From: "; getTypeDerivedFrom().dump();
+}
+
+/// dump - Print composite type.
+void DICompositeType::dump() const {
+  DIArray A = getTypeArray();
+  if (A.isNull())
+    return;
+  cerr << " [" << A.getNumElements() << " elements]";
+}
+
+/// dump - Print global.
+void DIGlobal::dump() const {
+  std::string Res;
+  if (!getName(Res).empty())
+    cerr << " [" << Res << "] ";
+
+  unsigned Tag = getTag();
+  cerr << " [" << dwarf::TagString(Tag) << "] ";
+
+  // TODO : Print context
+  getCompileUnit().dump();
+  cerr << " [" << getLineNumber() << "] ";
+
+  if (isLocalToUnit())
+    cerr << " [local] ";
+
+  if (isDefinition())
+    cerr << " [def] ";
+
+  if (isGlobalVariable(Tag))
+    DIGlobalVariable(DbgGV).dump();
+
+  cerr << "\n";
+}
+
+/// dump - Print subprogram.
+void DISubprogram::dump() const {
+  DIGlobal::dump();
+}
+
+/// dump - Print global variable.
+void DIGlobalVariable::dump() const {
+  cerr << " ["; getGlobal()->dump(); cerr << "] ";
+}
+
+/// dump - Print variable.
+void DIVariable::dump() const {
+  std::string Res;
+  if (!getName(Res).empty())
+    cerr << " [" << Res << "] ";
+
+  getCompileUnit().dump();
+  cerr << " [" << getLineNumber() << "] ";
+  getType().dump();
+  cerr << "\n";
+}
+
+//===----------------------------------------------------------------------===//
 // DIFactory: Basic Helpers
 //===----------------------------------------------------------------------===//
 
 DIFactory::DIFactory(Module &m)
   : M(m), StopPointFn(0), FuncStartFn(0), RegionStartFn(0), RegionEndFn(0),
     DeclareFn(0) {
-  EmptyStructPtr = PointerType::getUnqual(StructType::get(NULL, NULL));
+  EmptyStructPtr = PointerType::getUnqual(StructType::get());
 }
 
 /// getCastToEmpty - Return this descriptor as a Constant* with type '{}*'.
@@ -923,127 +1051,108 @@ namespace llvm {
       }
     }
   }
-}
-
-/// dump - Print descriptor.
-void DIDescriptor::dump() const {
-  cerr << "[" << dwarf::TagString(getTag()) << "] ";
-  cerr << std::hex << "[GV:" << DbgGV << "]" << std::dec;
-}
-
-/// dump - Print compile unit.
-void DICompileUnit::dump() const {
-  if (getLanguage())
-    cerr << " [" << dwarf::LanguageString(getLanguage()) << "] ";
-
-  std::string Res1, Res2;
-  cerr << " [" << getDirectory(Res1) << "/" << getFilename(Res2) << " ]";
-}
-
-/// dump - Print type.
-void DIType::dump() const {
-  if (isNull()) return;
-
-  std::string Res;
-  if (!getName(Res).empty())
-    cerr << " [" << Res << "] ";
-
-  unsigned Tag = getTag();
-  cerr << " [" << dwarf::TagString(Tag) << "] ";
-
-  // TODO : Print context
-  getCompileUnit().dump();
-  cerr << " [" 
-       << getLineNumber() << ", " 
-       << getSizeInBits() << ", "
-       << getAlignInBits() << ", "
-       << getOffsetInBits() 
-       << "] ";
-
-  if (isPrivate()) 
-    cerr << " [private] ";
-  else if (isProtected())
-    cerr << " [protected] ";
-
-  if (isForwardDecl())
-    cerr << " [fwd] ";
 
-  if (isBasicType(Tag))
-    DIBasicType(DbgGV).dump();
-  else if (isDerivedType(Tag))
-    DIDerivedType(DbgGV).dump();
-  else if (isCompositeType(Tag))
-    DICompositeType(DbgGV).dump();
-  else {
-    cerr << "Invalid DIType\n";
-    return;
+  /// isValidDebugInfoIntrinsic - Return true if SPI is a valid debug 
+  /// info intrinsic.
+  bool isValidDebugInfoIntrinsic(DbgStopPointInst &SPI, 
+                                 CodeGenOpt::Level OptLev) {
+    return DIDescriptor::ValidDebugInfo(SPI.getContext(), OptLev);
   }
 
-  cerr << "\n";
-}
-
-/// dump - Print basic type.
-void DIBasicType::dump() const {
-  cerr << " [" << dwarf::AttributeEncodingString(getEncoding()) << "] ";
-}
-
-/// dump - Print derived type.
-void DIDerivedType::dump() const {
-  cerr << "\n\t Derived From: "; getTypeDerivedFrom().dump();
-}
-
-/// dump - Print composite type.
-void DICompositeType::dump() const {
-  DIArray A = getTypeArray();
-  if (A.isNull())
-    return;
-  cerr << " [" << A.getNumElements() << " elements]";
-}
+  /// isValidDebugInfoIntrinsic - Return true if FSI is a valid debug 
+  /// info intrinsic.
+  bool isValidDebugInfoIntrinsic(DbgFuncStartInst &FSI,
+                                 CodeGenOpt::Level OptLev) {
+    return DIDescriptor::ValidDebugInfo(FSI.getSubprogram(), OptLev);
+  }
 
-/// dump - Print global.
-void DIGlobal::dump() const {
-  std::string Res;
-  if (!getName(Res).empty())
-    cerr << " [" << Res << "] ";
+  /// isValidDebugInfoIntrinsic - Return true if RSI is a valid debug 
+  /// info intrinsic.
+  bool isValidDebugInfoIntrinsic(DbgRegionStartInst &RSI,
+                                 CodeGenOpt::Level OptLev) {
+    return DIDescriptor::ValidDebugInfo(RSI.getContext(), OptLev);
+  }
 
-  unsigned Tag = getTag();
-  cerr << " [" << dwarf::TagString(Tag) << "] ";
+  /// isValidDebugInfoIntrinsic - Return true if REI is a valid debug 
+  /// info intrinsic.
+  bool isValidDebugInfoIntrinsic(DbgRegionEndInst &REI,
+                                 CodeGenOpt::Level OptLev) {
+    return DIDescriptor::ValidDebugInfo(REI.getContext(), OptLev);
+  }
 
-  // TODO : Print context
-  getCompileUnit().dump();
-  cerr << " [" << getLineNumber() << "] ";
 
-  if (isLocalToUnit())
-    cerr << " [local] ";
+  /// isValidDebugInfoIntrinsic - Return true if DI is a valid debug 
+  /// info intrinsic.
+  bool isValidDebugInfoIntrinsic(DbgDeclareInst &DI,
+                                 CodeGenOpt::Level OptLev) {
+    return DIDescriptor::ValidDebugInfo(DI.getVariable(), OptLev);
+  }
 
-  if (isDefinition())
-    cerr << " [def] ";
+  /// ExtractDebugLocation - Extract debug location information 
+  /// from llvm.dbg.stoppoint intrinsic.
+  DebugLoc ExtractDebugLocation(DbgStopPointInst &SPI,
+                                DebugLocTracker &DebugLocInfo) {
+    DebugLoc DL;
+    Value *Context = SPI.getContext();
+
+    // If this location is already tracked then use it.
+    DebugLocTuple Tuple(cast<GlobalVariable>(Context), SPI.getLine(), 
+                        SPI.getColumn());
+    DenseMap<DebugLocTuple, unsigned>::iterator II
+      = DebugLocInfo.DebugIdMap.find(Tuple);
+    if (II != DebugLocInfo.DebugIdMap.end())
+      return DebugLoc::get(II->second);
+
+    // Add a new location entry.
+    unsigned Id = DebugLocInfo.DebugLocations.size();
+    DebugLocInfo.DebugLocations.push_back(Tuple);
+    DebugLocInfo.DebugIdMap[Tuple] = Id;
+    
+    return DebugLoc::get(Id);
+  }
 
-  if (isGlobalVariable(Tag))
-    DIGlobalVariable(DbgGV).dump();
+  /// ExtractDebugLocation - Extract debug location information 
+  /// from llvm.dbg.func_start intrinsic.
+  DebugLoc ExtractDebugLocation(DbgFuncStartInst &FSI,
+                                DebugLocTracker &DebugLocInfo) {
+    DebugLoc DL;
+    Value *SP = FSI.getSubprogram();
+
+    DISubprogram Subprogram(cast<GlobalVariable>(SP));
+    unsigned Line = Subprogram.getLineNumber();
+    DICompileUnit CU(Subprogram.getCompileUnit());
+
+    // If this location is already tracked then use it.
+    DebugLocTuple Tuple(CU.getGV(), Line, /* Column */ 0);
+    DenseMap<DebugLocTuple, unsigned>::iterator II
+      = DebugLocInfo.DebugIdMap.find(Tuple);
+    if (II != DebugLocInfo.DebugIdMap.end())
+      return DebugLoc::get(II->second);
+
+    // Add a new location entry.
+    unsigned Id = DebugLocInfo.DebugLocations.size();
+    DebugLocInfo.DebugLocations.push_back(Tuple);
+    DebugLocInfo.DebugIdMap[Tuple] = Id;
+    
+    return DebugLoc::get(Id);
+  }
 
-  cerr << "\n";
-}
+  /// isInlinedFnStart - Return true if FSI is starting an inlined function.
+  bool isInlinedFnStart(DbgFuncStartInst &FSI, const Function *CurrentFn) {
+    DISubprogram Subprogram(cast<GlobalVariable>(FSI.getSubprogram()));
+    if (Subprogram.describes(CurrentFn))
+      return false;
 
-/// dump - Print subprogram.
-void DISubprogram::dump() const {
-  DIGlobal::dump();
-}
+    return true;
+  }
 
-/// dump - Print global variable.
-void DIGlobalVariable::dump() const {
-  cerr << " ["; getGlobal()->dump(); cerr << "] ";
-}
+  /// isInlinedFnEnd - Return true if REI is ending an inlined function.
+  bool isInlinedFnEnd(DbgRegionEndInst &REI, const Function *CurrentFn) {
+    DISubprogram Subprogram(cast<GlobalVariable>(REI.getContext()));
+    if (Subprogram.isNull() || Subprogram.describes(CurrentFn))
+      return false;
 
-/// dump - Print variable.
-void DIVariable::dump() const {
-  std::string Res;
-  if (!getName(Res).empty())
-    cerr << " [" << Res << "] ";
+    return true;
+  }
 
-  getCompileUnit().dump();
-  cerr << " [" << getLineNumber() << "] ";
-  getType().dump();
-  cerr << "\n";
 }
-
diff --git a/lib/Analysis/IPA/Andersens.cpp b/lib/Analysis/IPA/Andersens.cpp
index 4ace049..3fb6526 100644
--- a/lib/Analysis/IPA/Andersens.cpp
+++ b/lib/Analysis/IPA/Andersens.cpp
@@ -211,7 +211,7 @@ namespace {
     // for each location equivalent Node.
     struct Node {
     private:
-      static unsigned Counter;
+      static volatile sys::cas_flag Counter;
 
     public:
       Value *Val;
@@ -618,7 +618,7 @@ X("anders-aa", "Andersen's Interprocedural Alias Analysis", false, true);
 static RegisterAnalysisGroup<AliasAnalysis> Y(X);
 
 // Initialize Timestamp Counter (static).
-unsigned Andersens::Node::Counter = 0;
+volatile llvm::sys::cas_flag Andersens::Node::Counter = 0;
 
 ModulePass *llvm::createAndersensPass() { return new Andersens(); }
 
diff --git a/lib/Analysis/LoopDependenceAnalysis.cpp b/lib/Analysis/LoopDependenceAnalysis.cpp
index 172a2be..f605783 100644
--- a/lib/Analysis/LoopDependenceAnalysis.cpp
+++ b/lib/Analysis/LoopDependenceAnalysis.cpp
@@ -18,9 +18,13 @@
 //===----------------------------------------------------------------------===//
 
 #define DEBUG_TYPE "lda"
+#include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/Analysis/LoopDependenceAnalysis.h"
 #include "llvm/Analysis/LoopPass.h"
 #include "llvm/Analysis/ScalarEvolution.h"
+#include "llvm/Instructions.h"
+#include "llvm/Support/Debug.h"
+#include "llvm/Target/TargetData.h"
 using namespace llvm;
 
 LoopPass *llvm::createLoopDependenceAnalysisPass() {
@@ -32,16 +36,132 @@ R("lda", "Loop Dependence Analysis", false, true);
 char LoopDependenceAnalysis::ID = 0;
 
 //===----------------------------------------------------------------------===//
+//                             Utility Functions
+//===----------------------------------------------------------------------===//
+
+static inline bool IsMemRefInstr(const Value *V) {
+  const Instruction *I = dyn_cast<const Instruction>(V);
+  return I && (I->mayReadFromMemory() || I->mayWriteToMemory());
+}
+
+static void GetMemRefInstrs(
+    const Loop *L, SmallVectorImpl<Instruction*> &memrefs) {
+  for (Loop::block_iterator b = L->block_begin(), be = L->block_end();
+      b != be; ++b)
+    for (BasicBlock::iterator i = (*b)->begin(), ie = (*b)->end();
+        i != ie; ++i)
+      if (IsMemRefInstr(i))
+        memrefs.push_back(i);
+}
+
+static bool IsLoadOrStoreInst(Value *I) {
+  return isa<LoadInst>(I) || isa<StoreInst>(I);
+}
+
+static Value *GetPointerOperand(Value *I) {
+  if (LoadInst *i = dyn_cast<LoadInst>(I))
+    return i->getPointerOperand();
+  if (StoreInst *i = dyn_cast<StoreInst>(I))
+    return i->getPointerOperand();
+  assert(0 && "Value is no load or store instruction!");
+  // Never reached.
+  return 0;
+}
+
+//===----------------------------------------------------------------------===//
+//                             Dependence Testing
+//===----------------------------------------------------------------------===//
+
+bool LoopDependenceAnalysis::isDependencePair(const Value *x,
+                                              const Value *y) const {
+  return IsMemRefInstr(x) &&
+         IsMemRefInstr(y) &&
+         (cast<const Instruction>(x)->mayWriteToMemory() ||
+          cast<const Instruction>(y)->mayWriteToMemory());
+}
+
+bool LoopDependenceAnalysis::depends(Value *src, Value *dst) {
+  assert(isDependencePair(src, dst) && "Values form no dependence pair!");
+  DOUT << "== LDA test ==\n" << *src << *dst;
+
+  // We only analyse loads and stores; for possible memory accesses by e.g.
+  // free, call, or invoke instructions we conservatively assume dependence.
+  if (!IsLoadOrStoreInst(src) || !IsLoadOrStoreInst(dst))
+    return true;
+
+  Value *srcPtr = GetPointerOperand(src);
+  Value *dstPtr = GetPointerOperand(dst);
+  const Value *srcObj = srcPtr->getUnderlyingObject();
+  const Value *dstObj = dstPtr->getUnderlyingObject();
+  AliasAnalysis::AliasResult alias = AA->alias(
+      srcObj, AA->getTargetData().getTypeStoreSize(srcObj->getType()),
+      dstObj, AA->getTargetData().getTypeStoreSize(dstObj->getType()));
+
+  // If we don't know whether or not the two objects alias, assume dependence.
+  if (alias == AliasAnalysis::MayAlias)
+    return true;
+
+  // If the objects noalias, they are distinct, accesses are independent.
+  if (alias == AliasAnalysis::NoAlias)
+    return false;
+
+  // TODO: the underlying objects MustAlias, test for dependence
+
+  // We couldn't establish a more precise result, so we have to conservatively
+  // assume full dependence.
+  return true;
+}
+
+//===----------------------------------------------------------------------===//
 //                   LoopDependenceAnalysis Implementation
 //===----------------------------------------------------------------------===//
 
 bool LoopDependenceAnalysis::runOnLoop(Loop *L, LPPassManager &) {
   this->L = L;
+  AA = &getAnalysis<AliasAnalysis>();
   SE = &getAnalysis<ScalarEvolution>();
   return false;
 }
 
 void LoopDependenceAnalysis::getAnalysisUsage(AnalysisUsage &AU) const {
   AU.setPreservesAll();
-  AU.addRequired<ScalarEvolution>();
+  AU.addRequiredTransitive<AliasAnalysis>();
+  AU.addRequiredTransitive<ScalarEvolution>();
+}
+
+static void PrintLoopInfo(
+    raw_ostream &OS, LoopDependenceAnalysis *LDA, const Loop *L) {
+  if (!L->empty()) return; // ignore non-innermost loops
+
+  SmallVector<Instruction*, 8> memrefs;
+  GetMemRefInstrs(L, memrefs);
+
+  OS << "Loop at depth " << L->getLoopDepth() << ", header block: ";
+  WriteAsOperand(OS, L->getHeader(), false);
+  OS << "\n";
+
+  OS << "  Load/store instructions: " << memrefs.size() << "\n";
+  for (SmallVector<Instruction*, 8>::const_iterator x = memrefs.begin(),
+      end = memrefs.end(); x != end; ++x)
+    OS << "\t" << (x - memrefs.begin()) << ": " << **x;
+
+  OS << "  Pairwise dependence results:\n";
+  for (SmallVector<Instruction*, 8>::const_iterator x = memrefs.begin(),
+      end = memrefs.end(); x != end; ++x)
+    for (SmallVector<Instruction*, 8>::const_iterator y = x + 1;
+        y != end; ++y)
+      if (LDA->isDependencePair(*x, *y))
+        OS << "\t" << (x - memrefs.begin()) << "," << (y - memrefs.begin())
+           << ": " << (LDA->depends(*x, *y) ? "dependent" : "independent")
+           << "\n";
+}
+
+void LoopDependenceAnalysis::print(raw_ostream &OS, const Module*) const {
+  // TODO: doc why const_cast is safe
+  PrintLoopInfo(OS, const_cast<LoopDependenceAnalysis*>(this), this->L);
+}
+
+void LoopDependenceAnalysis::print(std::ostream &OS, const Module *M) const {
+  raw_os_ostream os(OS);
+  print(os, M);
 }
diff --git a/lib/Analysis/LoopInfo.cpp b/lib/Analysis/LoopInfo.cpp
index a0d3974..bb53589 100644
--- a/lib/Analysis/LoopInfo.cpp
+++ b/lib/Analysis/LoopInfo.cpp
@@ -39,7 +39,7 @@ X("loops", "Natural Loop Information", true, true);
 //
 bool LoopInfo::runOnFunction(Function &) {
   releaseMemory();
-  LI->Calculate(getAnalysis<DominatorTree>().getBase());    // Update
+  LI.Calculate(getAnalysis<DominatorTree>().getBase());    // Update
   return false;
 }
 
diff --git a/lib/Analysis/LoopPass.cpp b/lib/Analysis/LoopPass.cpp
index 08c25f4..ee03556 100644
--- a/lib/Analysis/LoopPass.cpp
+++ b/lib/Analysis/LoopPass.cpp
@@ -195,6 +195,9 @@ bool LPPassManager::runOnFunction(Function &F) {
   for (LoopInfo::iterator I = LI->begin(), E = LI->end(); I != E; ++I)
     addLoopIntoQueue(*I, LQ);
 
+  if (LQ.empty()) // No loops, skip calling finalizers
+    return false;
+
   // Initialization
   for (std::deque<Loop *>::const_iterator I = LQ.begin(), E = LQ.end();
        I != E; ++I) {
diff --git a/lib/Analysis/ScalarEvolution.cpp b/lib/Analysis/ScalarEvolution.cpp
index dcb179af..4081562 100644
--- a/lib/Analysis/ScalarEvolution.cpp
+++ b/lib/Analysis/ScalarEvolution.cpp
@@ -110,7 +110,9 @@ char ScalarEvolution::ID = 0;
 //===----------------------------------------------------------------------===//
 // Implementation of the SCEV class.
 //
+
 SCEV::~SCEV() {}
+
 void SCEV::dump() const {
   print(errs());
   errs() << '\n';
@@ -142,6 +144,10 @@ bool SCEV::isAllOnesValue() const {
 SCEVCouldNotCompute::SCEVCouldNotCompute() :
   SCEV(scCouldNotCompute) {}
 
+void SCEVCouldNotCompute::Profile(FoldingSetNodeID &ID) const {
+  assert(0 && "Attempt to use a SCEVCouldNotCompute object!");
+}
+
 bool SCEVCouldNotCompute::isLoopInvariant(const Loop *L) const {
   assert(0 && "Attempt to use a SCEVCouldNotCompute object!");
   return false;
@@ -174,9 +180,15 @@ bool SCEVCouldNotCompute::classof(const SCEV *S) {
 }
 
 const SCEV* ScalarEvolution::getConstant(ConstantInt *V) {
-  SCEVConstant *&R = SCEVConstants[V];
-  if (R == 0) R = new SCEVConstant(V);
-  return R;
+  FoldingSetNodeID ID;
+  ID.AddInteger(scConstant);
+  ID.AddPointer(V);
+  void *IP = 0;
+  if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S;
+  SCEV *S = SCEVAllocator.Allocate<SCEVConstant>();
+  new (S) SCEVConstant(V);
+  UniqueSCEVs.InsertNode(S, IP);
+  return S;
 }
 
 const SCEV* ScalarEvolution::getConstant(const APInt& Val) {
@@ -188,6 +200,11 @@ ScalarEvolution::getConstant(const Type *Ty, uint64_t V, bool isSigned) {
   return getConstant(ConstantInt::get(cast<IntegerType>(Ty), V, isSigned));
 }
 
+void SCEVConstant::Profile(FoldingSetNodeID &ID) const {
+  ID.AddInteger(scConstant);
+  ID.AddPointer(V);
+}
+
 const Type *SCEVConstant::getType() const { return V->getType(); }
 
 void SCEVConstant::print(raw_ostream &OS) const {
@@ -198,6 +215,12 @@ SCEVCastExpr::SCEVCastExpr(unsigned SCEVTy,
                            const SCEV* op, const Type *ty)
   : SCEV(SCEVTy), Op(op), Ty(ty) {}
 
+void SCEVCastExpr::Profile(FoldingSetNodeID &ID) const {
+  ID.AddInteger(getSCEVType());
+  ID.AddPointer(Op);
+  ID.AddPointer(Ty);
+}
+
 bool SCEVCastExpr::dominates(BasicBlock *BB, DominatorTree *DT) const {
   return Op->dominates(BB, DT);
 }
@@ -277,6 +300,13 @@ SCEVCommutativeExpr::replaceSymbolicValuesWithConcrete(
   return this;
 }
 
+void SCEVNAryExpr::Profile(FoldingSetNodeID &ID) const {
+  ID.AddInteger(getSCEVType());
+  ID.AddInteger(Operands.size());
+  for (unsigned i = 0, e = Operands.size(); i != e; ++i)
+    ID.AddPointer(Operands[i]);
+}
+
 bool SCEVNAryExpr::dominates(BasicBlock *BB, DominatorTree *DT) const {
   for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
     if (!getOperand(i)->dominates(BB, DT))
@@ -285,6 +315,12 @@ bool SCEVNAryExpr::dominates(BasicBlock *BB, DominatorTree *DT) const {
   return true;
 }
 
+void SCEVUDivExpr::Profile(FoldingSetNodeID &ID) const {
+  ID.AddInteger(scUDivExpr);
+  ID.AddPointer(LHS);
+  ID.AddPointer(RHS);
+}
+
 bool SCEVUDivExpr::dominates(BasicBlock *BB, DominatorTree *DT) const {
   return LHS->dominates(BB, DT) && RHS->dominates(BB, DT);
 }
@@ -302,6 +338,14 @@ const Type *SCEVUDivExpr::getType() const {
   return RHS->getType();
 }
 
+void SCEVAddRecExpr::Profile(FoldingSetNodeID &ID) const {
+  ID.AddInteger(scAddRecExpr);
+  ID.AddInteger(Operands.size());
+  for (unsigned i = 0, e = Operands.size(); i != e; ++i)
+    ID.AddPointer(Operands[i]);
+  ID.AddPointer(L);
+}
+
 const SCEV *
 SCEVAddRecExpr::replaceSymbolicValuesWithConcrete(const SCEV *Sym,
                                                   const SCEV *Conc,
@@ -345,7 +389,6 @@ bool SCEVAddRecExpr::isLoopInvariant(const Loop *QueryLoop) const {
   return true;
 }
 
-
 void SCEVAddRecExpr::print(raw_ostream &OS) const {
   OS << "{" << *Operands[0];
   for (unsigned i = 1, e = Operands.size(); i != e; ++i)
@@ -353,6 +396,11 @@ void SCEVAddRecExpr::print(raw_ostream &OS) const {
   OS << "}<" << L->getHeader()->getName() + ">";
 }
 
+void SCEVUnknown::Profile(FoldingSetNodeID &ID) const {
+  ID.AddInteger(scUnknown);
+  ID.AddPointer(V);
+}
+
 bool SCEVUnknown::isLoopInvariant(const Loop *L) const {
   // All non-instruction values are loop invariant.  All instructions are loop
   // invariant if they are not contained in the specified loop.
@@ -696,6 +744,7 @@ const SCEV* ScalarEvolution::getTruncateExpr(const SCEV* Op,
          "This is not a conversion to a SCEVable type!");
   Ty = getEffectiveSCEVType(Ty);
 
+  // Fold if the operand is constant.
   if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(Op))
     return getConstant(
       cast<ConstantInt>(ConstantExpr::getTrunc(SC->getValue(), Ty)));
@@ -720,9 +769,16 @@ const SCEV* ScalarEvolution::getTruncateExpr(const SCEV* Op,
     return getAddRecExpr(Operands, AddRec->getLoop());
   }
 
-  SCEVTruncateExpr *&Result = SCEVTruncates[std::make_pair(Op, Ty)];
-  if (Result == 0) Result = new SCEVTruncateExpr(Op, Ty);
-  return Result;
+  FoldingSetNodeID ID;
+  ID.AddInteger(scTruncate);
+  ID.AddPointer(Op);
+  ID.AddPointer(Ty);
+  void *IP = 0;
+  if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S;
+  SCEV *S = SCEVAllocator.Allocate<SCEVTruncateExpr>();
+  new (S) SCEVTruncateExpr(Op, Ty);
+  UniqueSCEVs.InsertNode(S, IP);
+  return S;
 }
 
 const SCEV* ScalarEvolution::getZeroExtendExpr(const SCEV* Op,
@@ -733,6 +789,7 @@ const SCEV* ScalarEvolution::getZeroExtendExpr(const SCEV* Op,
          "This is not a conversion to a SCEVable type!");
   Ty = getEffectiveSCEVType(Ty);
 
+  // Fold if the operand is constant.
   if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(Op)) {
     const Type *IntTy = getEffectiveSCEVType(Ty);
     Constant *C = ConstantExpr::getZExt(SC->getValue(), IntTy);
@@ -808,9 +865,16 @@ const SCEV* ScalarEvolution::getZeroExtendExpr(const SCEV* Op,
       }
     }
 
-  SCEVZeroExtendExpr *&Result = SCEVZeroExtends[std::make_pair(Op, Ty)];
-  if (Result == 0) Result = new SCEVZeroExtendExpr(Op, Ty);
-  return Result;
+  FoldingSetNodeID ID;
+  ID.AddInteger(scZeroExtend);
+  ID.AddPointer(Op);
+  ID.AddPointer(Ty);
+  void *IP = 0;
+  if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S;
+  SCEV *S = SCEVAllocator.Allocate<SCEVZeroExtendExpr>();
+  new (S) SCEVZeroExtendExpr(Op, Ty);
+  UniqueSCEVs.InsertNode(S, IP);
+  return S;
 }
 
 const SCEV* ScalarEvolution::getSignExtendExpr(const SCEV* Op,
@@ -821,6 +885,7 @@ const SCEV* ScalarEvolution::getSignExtendExpr(const SCEV* Op,
          "This is not a conversion to a SCEVable type!");
   Ty = getEffectiveSCEVType(Ty);
 
+  // Fold if the operand is constant.
   if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(Op)) {
     const Type *IntTy = getEffectiveSCEVType(Ty);
     Constant *C = ConstantExpr::getSExt(SC->getValue(), IntTy);
@@ -880,9 +945,16 @@ const SCEV* ScalarEvolution::getSignExtendExpr(const SCEV* Op,
       }
     }
 
-  SCEVSignExtendExpr *&Result = SCEVSignExtends[std::make_pair(Op, Ty)];
-  if (Result == 0) Result = new SCEVSignExtendExpr(Op, Ty);
-  return Result;
+  FoldingSetNodeID ID;
+  ID.AddInteger(scSignExtend);
+  ID.AddPointer(Op);
+  ID.AddPointer(Ty);
+  void *IP = 0;
+  if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S;
+  SCEV *S = SCEVAllocator.Allocate<SCEVSignExtendExpr>();
+  new (S) SCEVSignExtendExpr(Op, Ty);
+  UniqueSCEVs.InsertNode(S, IP);
+  return S;
 }
 
 /// getAnyExtendExpr - Return a SCEV for the given operand extended with
@@ -980,9 +1052,8 @@ CollectAddOperandsWithScales(DenseMap<const SCEV*, APInt> &M,
         SmallVector<const SCEV*, 4> MulOps(Mul->op_begin()+1, Mul->op_end());
         const SCEV* Key = SE.getMulExpr(MulOps);
         std::pair<DenseMap<const SCEV*, APInt>::iterator, bool> Pair =
-          M.insert(std::make_pair(Key, APInt()));
+          M.insert(std::make_pair(Key, NewScale));
         if (Pair.second) {
-          Pair.first->second = NewScale;
           NewOps.push_back(Pair.first->first);
         } else {
           Pair.first->second += NewScale;
@@ -999,9 +1070,8 @@ CollectAddOperandsWithScales(DenseMap<const SCEV*, APInt> &M,
     } else {
       // An ordinary operand. Update the map.
       std::pair<DenseMap<const SCEV*, APInt>::iterator, bool> Pair =
-        M.insert(std::make_pair(Ops[i], APInt()));
+        M.insert(std::make_pair(Ops[i], Scale));
       if (Pair.second) {
-        Pair.first->second = Scale;
         NewOps.push_back(Pair.first->first);
       } else {
         Pair.first->second += Scale;
@@ -1343,11 +1413,17 @@ const SCEV* ScalarEvolution::getAddExpr(SmallVectorImpl<const SCEV*> &Ops) {
 
   // Okay, it looks like we really DO need an add expr.  Check to see if we
   // already have one, otherwise create a new one.
-  std::vector<const SCEV*> SCEVOps(Ops.begin(), Ops.end());
-  SCEVCommutativeExpr *&Result = SCEVCommExprs[std::make_pair(scAddExpr,
-                                                                 SCEVOps)];
-  if (Result == 0) Result = new SCEVAddExpr(Ops);
-  return Result;
+  FoldingSetNodeID ID;
+  ID.AddInteger(scAddExpr);
+  ID.AddInteger(Ops.size());
+  for (unsigned i = 0, e = Ops.size(); i != e; ++i)
+    ID.AddPointer(Ops[i]);
+  void *IP = 0;
+  if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S;
+  SCEV *S = SCEVAllocator.Allocate<SCEVAddExpr>();
+  new (S) SCEVAddExpr(Ops);
+  UniqueSCEVs.InsertNode(S, IP);
+  return S;
 }
 
 
@@ -1508,12 +1584,17 @@ const SCEV* ScalarEvolution::getMulExpr(SmallVectorImpl<const SCEV*> &Ops) {
 
   // Okay, it looks like we really DO need an mul expr.  Check to see if we
   // already have one, otherwise create a new one.
-  std::vector<const SCEV*> SCEVOps(Ops.begin(), Ops.end());
-  SCEVCommutativeExpr *&Result = SCEVCommExprs[std::make_pair(scMulExpr,
-                                                                 SCEVOps)];
-  if (Result == 0)
-    Result = new SCEVMulExpr(Ops);
-  return Result;
+  FoldingSetNodeID ID;
+  ID.AddInteger(scMulExpr);
+  ID.AddInteger(Ops.size());
+  for (unsigned i = 0, e = Ops.size(); i != e; ++i)
+    ID.AddPointer(Ops[i]);
+  void *IP = 0;
+  if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S;
+  SCEV *S = SCEVAllocator.Allocate<SCEVMulExpr>();
+  new (S) SCEVMulExpr(Ops);
+  UniqueSCEVs.InsertNode(S, IP);
+  return S;
 }
 
 /// getUDivExpr - Get a canonical multiply expression, or something simpler if
@@ -1603,9 +1684,16 @@ const SCEV *ScalarEvolution::getUDivExpr(const SCEV *LHS,
     }
   }
 
-  SCEVUDivExpr *&Result = SCEVUDivs[std::make_pair(LHS, RHS)];
-  if (Result == 0) Result = new SCEVUDivExpr(LHS, RHS);
-  return Result;
+  FoldingSetNodeID ID;
+  ID.AddInteger(scUDivExpr);
+  ID.AddPointer(LHS);
+  ID.AddPointer(RHS);
+  void *IP = 0;
+  if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S;
+  SCEV *S = SCEVAllocator.Allocate<SCEVUDivExpr>();
+  new (S) SCEVUDivExpr(LHS, RHS);
+  UniqueSCEVs.InsertNode(S, IP);
+  return S;
 }
 
 
@@ -1677,10 +1765,18 @@ ScalarEvolution::getAddRecExpr(SmallVectorImpl<const SCEV*> &Operands,
     }
   }
 
-  std::vector<const SCEV*> SCEVOps(Operands.begin(), Operands.end());
-  SCEVAddRecExpr *&Result = SCEVAddRecExprs[std::make_pair(L, SCEVOps)];
-  if (Result == 0) Result = new SCEVAddRecExpr(Operands, L);
-  return Result;
+  FoldingSetNodeID ID;
+  ID.AddInteger(scAddRecExpr);
+  ID.AddInteger(Operands.size());
+  for (unsigned i = 0, e = Operands.size(); i != e; ++i)
+    ID.AddPointer(Operands[i]);
+  ID.AddPointer(L);
+  void *IP = 0;
+  if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S;
+  SCEV *S = SCEVAllocator.Allocate<SCEVAddRecExpr>();
+  new (S) SCEVAddRecExpr(Operands, L);
+  UniqueSCEVs.InsertNode(S, IP);
+  return S;
 }
 
 const SCEV *ScalarEvolution::getSMaxExpr(const SCEV *LHS,
@@ -1767,11 +1863,17 @@ ScalarEvolution::getSMaxExpr(SmallVectorImpl<const SCEV*> &Ops) {
 
   // Okay, it looks like we really DO need an smax expr.  Check to see if we
   // already have one, otherwise create a new one.
-  std::vector<const SCEV*> SCEVOps(Ops.begin(), Ops.end());
-  SCEVCommutativeExpr *&Result = SCEVCommExprs[std::make_pair(scSMaxExpr,
-                                                                 SCEVOps)];
-  if (Result == 0) Result = new SCEVSMaxExpr(Ops);
-  return Result;
+  FoldingSetNodeID ID;
+  ID.AddInteger(scSMaxExpr);
+  ID.AddInteger(Ops.size());
+  for (unsigned i = 0, e = Ops.size(); i != e; ++i)
+    ID.AddPointer(Ops[i]);
+  void *IP = 0;
+  if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S;
+  SCEV *S = SCEVAllocator.Allocate<SCEVSMaxExpr>();
+  new (S) SCEVSMaxExpr(Ops);
+  UniqueSCEVs.InsertNode(S, IP);
+  return S;
 }
 
 const SCEV *ScalarEvolution::getUMaxExpr(const SCEV *LHS,
@@ -1858,11 +1960,17 @@ ScalarEvolution::getUMaxExpr(SmallVectorImpl<const SCEV*> &Ops) {
 
   // Okay, it looks like we really DO need a umax expr.  Check to see if we
   // already have one, otherwise create a new one.
-  std::vector<const SCEV*> SCEVOps(Ops.begin(), Ops.end());
-  SCEVCommutativeExpr *&Result = SCEVCommExprs[std::make_pair(scUMaxExpr,
-                                                                 SCEVOps)];
-  if (Result == 0) Result = new SCEVUMaxExpr(Ops);
-  return Result;
+  FoldingSetNodeID ID;
+  ID.AddInteger(scUMaxExpr);
+  ID.AddInteger(Ops.size());
+  for (unsigned i = 0, e = Ops.size(); i != e; ++i)
+    ID.AddPointer(Ops[i]);
+  void *IP = 0;
+  if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S;
+  SCEV *S = SCEVAllocator.Allocate<SCEVUMaxExpr>();
+  new (S) SCEVUMaxExpr(Ops);
+  UniqueSCEVs.InsertNode(S, IP);
+  return S;
 }
 
 const SCEV *ScalarEvolution::getSMinExpr(const SCEV *LHS,
@@ -1883,9 +1991,15 @@ const SCEV* ScalarEvolution::getUnknown(Value *V) {
   // interesting possibilities, and any other code that calls getUnknown
   // is doing so in order to hide a value from SCEV canonicalization.
 
-  SCEVUnknown *&Result = SCEVUnknowns[V];
-  if (Result == 0) Result = new SCEVUnknown(V);
-  return Result;
+  FoldingSetNodeID ID;
+  ID.AddInteger(scUnknown);
+  ID.AddPointer(V);
+  void *IP = 0;
+  if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S;
+  SCEV *S = SCEVAllocator.Allocate<SCEVUnknown>();
+  new (S) SCEVUnknown(V);
+  UniqueSCEVs.InsertNode(S, IP);
+  return S;
 }
 
 //===----------------------------------------------------------------------===//
@@ -1939,7 +2053,7 @@ const Type *ScalarEvolution::getEffectiveSCEVType(const Type *Ty) const {
 }
 
 const SCEV* ScalarEvolution::getCouldNotCompute() {
-  return CouldNotCompute;
+  return &CouldNotCompute;
 }
 
 /// hasSCEV - Return true if the SCEV for this value has already been
@@ -2750,7 +2864,7 @@ ScalarEvolution::getBackedgeTakenInfo(const Loop *L) {
     BackedgeTakenCounts.insert(std::make_pair(L, getCouldNotCompute()));
   if (Pair.second) {
     BackedgeTakenInfo ItCount = ComputeBackedgeTakenCount(L);
-    if (ItCount.Exact != CouldNotCompute) {
+    if (ItCount.Exact != getCouldNotCompute()) {
       assert(ItCount.Exact->isLoopInvariant(L) &&
              ItCount.Max->isLoopInvariant(L) &&
              "Computed trip count isn't loop invariant for loop!");
@@ -2759,7 +2873,7 @@ ScalarEvolution::getBackedgeTakenInfo(const Loop *L) {
       // Update the value in the map.
       Pair.first->second = ItCount;
     } else {
-      if (ItCount.Max != CouldNotCompute)
+      if (ItCount.Max != getCouldNotCompute())
         // Update the value in the map.
         Pair.first->second = ItCount;
       if (isa<PHINode>(L->getHeader()->begin()))
@@ -2825,27 +2939,27 @@ ScalarEvolution::ComputeBackedgeTakenCount(const Loop *L) {
   L->getExitingBlocks(ExitingBlocks);
 
   // Examine all exits and pick the most conservative values.
-  const SCEV* BECount = CouldNotCompute;
-  const SCEV* MaxBECount = CouldNotCompute;
+  const SCEV* BECount = getCouldNotCompute();
+  const SCEV* MaxBECount = getCouldNotCompute();
   bool CouldNotComputeBECount = false;
   for (unsigned i = 0, e = ExitingBlocks.size(); i != e; ++i) {
     BackedgeTakenInfo NewBTI =
       ComputeBackedgeTakenCountFromExit(L, ExitingBlocks[i]);
 
-    if (NewBTI.Exact == CouldNotCompute) {
+    if (NewBTI.Exact == getCouldNotCompute()) {
       // We couldn't compute an exact value for this exit, so
       // we won't be able to compute an exact value for the loop.
       CouldNotComputeBECount = true;
-      BECount = CouldNotCompute;
+      BECount = getCouldNotCompute();
     } else if (!CouldNotComputeBECount) {
-      if (BECount == CouldNotCompute)
+      if (BECount == getCouldNotCompute())
         BECount = NewBTI.Exact;
       else
         BECount = getUMinFromMismatchedTypes(BECount, NewBTI.Exact);
     }
-    if (MaxBECount == CouldNotCompute)
+    if (MaxBECount == getCouldNotCompute())
       MaxBECount = NewBTI.Max;
-    else if (NewBTI.Max != CouldNotCompute)
+    else if (NewBTI.Max != getCouldNotCompute())
       MaxBECount = getUMinFromMismatchedTypes(MaxBECount, NewBTI.Max);
   }
 
@@ -2863,7 +2977,7 @@ ScalarEvolution::ComputeBackedgeTakenCountFromExit(const Loop *L,
   //
   // FIXME: we should be able to handle switch instructions (with a single exit)
   BranchInst *ExitBr = dyn_cast<BranchInst>(ExitingBlock->getTerminator());
-  if (ExitBr == 0) return CouldNotCompute;
+  if (ExitBr == 0) return getCouldNotCompute();
   assert(ExitBr->isConditional() && "If unconditional, it can't be in loop!");
 
   // At this point, we know we have a conditional branch that determines whether
@@ -2892,7 +3006,7 @@ ScalarEvolution::ComputeBackedgeTakenCountFromExit(const Loop *L,
     for (BasicBlock *BB = ExitBr->getParent(); BB; ) {
       BasicBlock *Pred = BB->getUniquePredecessor();
       if (!Pred)
-        return CouldNotCompute;
+        return getCouldNotCompute();
       TerminatorInst *PredTerm = Pred->getTerminator();
       for (unsigned i = 0, e = PredTerm->getNumSuccessors(); i != e; ++i) {
         BasicBlock *PredSucc = PredTerm->getSuccessor(i);
@@ -2901,7 +3015,7 @@ ScalarEvolution::ComputeBackedgeTakenCountFromExit(const Loop *L,
         // If the predecessor has a successor that isn't BB and isn't
         // outside the loop, assume the worst.
         if (L->contains(PredSucc))
-          return CouldNotCompute;
+          return getCouldNotCompute();
       }
       if (Pred == L->getHeader()) {
         Ok = true;
@@ -2910,7 +3024,7 @@ ScalarEvolution::ComputeBackedgeTakenCountFromExit(const Loop *L,
       BB = Pred;
     }
     if (!Ok)
-      return CouldNotCompute;
+      return getCouldNotCompute();
   }
 
   // Procede to the next level to examine the exit condition expression.
@@ -2935,27 +3049,30 @@ ScalarEvolution::ComputeBackedgeTakenCountFromExitCond(const Loop *L,
         ComputeBackedgeTakenCountFromExitCond(L, BO->getOperand(0), TBB, FBB);
       BackedgeTakenInfo BTI1 =
         ComputeBackedgeTakenCountFromExitCond(L, BO->getOperand(1), TBB, FBB);
-      const SCEV* BECount = CouldNotCompute;
-      const SCEV* MaxBECount = CouldNotCompute;
+      const SCEV* BECount = getCouldNotCompute();
+      const SCEV* MaxBECount = getCouldNotCompute();
       if (L->contains(TBB)) {
         // Both conditions must be true for the loop to continue executing.
         // Choose the less conservative count.
-        if (BTI0.Exact == CouldNotCompute || BTI1.Exact == CouldNotCompute)
-          BECount = CouldNotCompute;
+        if (BTI0.Exact == getCouldNotCompute() ||
+            BTI1.Exact == getCouldNotCompute())
+          BECount = getCouldNotCompute();
         else
           BECount = getUMinFromMismatchedTypes(BTI0.Exact, BTI1.Exact);
-        if (BTI0.Max == CouldNotCompute)
+        if (BTI0.Max == getCouldNotCompute())
           MaxBECount = BTI1.Max;
-        else if (BTI1.Max == CouldNotCompute)
+        else if (BTI1.Max == getCouldNotCompute())
           MaxBECount = BTI0.Max;
         else
           MaxBECount = getUMinFromMismatchedTypes(BTI0.Max, BTI1.Max);
       } else {
         // Both conditions must be true for the loop to exit.
         assert(L->contains(FBB) && "Loop block has no successor in loop!");
-        if (BTI0.Exact != CouldNotCompute && BTI1.Exact != CouldNotCompute)
+        if (BTI0.Exact != getCouldNotCompute() &&
+            BTI1.Exact != getCouldNotCompute())
           BECount = getUMaxFromMismatchedTypes(BTI0.Exact, BTI1.Exact);
-        if (BTI0.Max != CouldNotCompute && BTI1.Max != CouldNotCompute)
+        if (BTI0.Max != getCouldNotCompute() &&
+            BTI1.Max != getCouldNotCompute())
           MaxBECount = getUMaxFromMismatchedTypes(BTI0.Max, BTI1.Max);
       }
 
@@ -2967,27 +3084,30 @@ ScalarEvolution::ComputeBackedgeTakenCountFromExitCond(const Loop *L,
         ComputeBackedgeTakenCountFromExitCond(L, BO->getOperand(0), TBB, FBB);
       BackedgeTakenInfo BTI1 =
         ComputeBackedgeTakenCountFromExitCond(L, BO->getOperand(1), TBB, FBB);
-      const SCEV* BECount = CouldNotCompute;
-      const SCEV* MaxBECount = CouldNotCompute;
+      const SCEV* BECount = getCouldNotCompute();
+      const SCEV* MaxBECount = getCouldNotCompute();
       if (L->contains(FBB)) {
         // Both conditions must be false for the loop to continue executing.
         // Choose the less conservative count.
-        if (BTI0.Exact == CouldNotCompute || BTI1.Exact == CouldNotCompute)
-          BECount = CouldNotCompute;
+        if (BTI0.Exact == getCouldNotCompute() ||
+            BTI1.Exact == getCouldNotCompute())
+          BECount = getCouldNotCompute();
         else
           BECount = getUMinFromMismatchedTypes(BTI0.Exact, BTI1.Exact);
-        if (BTI0.Max == CouldNotCompute)
+        if (BTI0.Max == getCouldNotCompute())
           MaxBECount = BTI1.Max;
-        else if (BTI1.Max == CouldNotCompute)
+        else if (BTI1.Max == getCouldNotCompute())
           MaxBECount = BTI0.Max;
         else
           MaxBECount = getUMinFromMismatchedTypes(BTI0.Max, BTI1.Max);
       } else {
         // Both conditions must be false for the loop to exit.
         assert(L->contains(TBB) && "Loop block has no successor in loop!");
-        if (BTI0.Exact != CouldNotCompute && BTI1.Exact != CouldNotCompute)
+        if (BTI0.Exact != getCouldNotCompute() &&
+            BTI1.Exact != getCouldNotCompute())
           BECount = getUMaxFromMismatchedTypes(BTI0.Exact, BTI1.Exact);
-        if (BTI0.Max != CouldNotCompute && BTI1.Max != CouldNotCompute)
+        if (BTI0.Max != getCouldNotCompute() &&
+            BTI1.Max != getCouldNotCompute())
           MaxBECount = getUMaxFromMismatchedTypes(BTI0.Max, BTI1.Max);
       }
 
@@ -3164,11 +3284,11 @@ ScalarEvolution::ComputeLoadConstantCompareBackedgeTakenCount(
                                                 Constant *RHS,
                                                 const Loop *L,
                                                 ICmpInst::Predicate predicate) {
-  if (LI->isVolatile()) return CouldNotCompute;
+  if (LI->isVolatile()) return getCouldNotCompute();
 
   // Check to see if the loaded pointer is a getelementptr of a global.
   GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(LI->getOperand(0));
-  if (!GEP) return CouldNotCompute;
+  if (!GEP) return getCouldNotCompute();
 
   // Make sure that it is really a constant global we are gepping, with an
   // initializer, and make sure the first IDX is really 0.
@@ -3176,7 +3296,7 @@ ScalarEvolution::ComputeLoadConstantCompareBackedgeTakenCount(
   if (!GV || !GV->isConstant() || !GV->hasInitializer() ||
       GEP->getNumOperands() < 3 || !isa<Constant>(GEP->getOperand(1)) ||
       !cast<Constant>(GEP->getOperand(1))->isNullValue())
-    return CouldNotCompute;
+    return getCouldNotCompute();
 
   // Okay, we allow one non-constant index into the GEP instruction.
   Value *VarIdx = 0;
@@ -3186,7 +3306,7 @@ ScalarEvolution::ComputeLoadConstantCompareBackedgeTakenCount(
     if (ConstantInt *CI = dyn_cast<ConstantInt>(GEP->getOperand(i))) {
       Indexes.push_back(CI);
     } else if (!isa<ConstantInt>(GEP->getOperand(i))) {
-      if (VarIdx) return CouldNotCompute;  // Multiple non-constant idx's.
+      if (VarIdx) return getCouldNotCompute();  // Multiple non-constant idx's.
       VarIdx = GEP->getOperand(i);
       VarIdxNum = i-2;
       Indexes.push_back(0);
@@ -3203,7 +3323,7 @@ ScalarEvolution::ComputeLoadConstantCompareBackedgeTakenCount(
   if (!IdxExpr || !IdxExpr->isAffine() || IdxExpr->isLoopInvariant(L) ||
       !isa<SCEVConstant>(IdxExpr->getOperand(0)) ||
       !isa<SCEVConstant>(IdxExpr->getOperand(1)))
-    return CouldNotCompute;
+    return getCouldNotCompute();
 
   unsigned MaxSteps = MaxBruteForceIterations;
   for (unsigned IterationNum = 0; IterationNum != MaxSteps; ++IterationNum) {
@@ -3230,7 +3350,7 @@ ScalarEvolution::ComputeLoadConstantCompareBackedgeTakenCount(
       return getConstant(ItCst);   // Found terminating iteration!
     }
   }
-  return CouldNotCompute;
+  return getCouldNotCompute();
 }
 
 
@@ -3371,13 +3491,13 @@ ScalarEvolution::getConstantEvolutionLoopExitValue(PHINode *PN,
 /// constant number of times (the condition evolves only from constants),
 /// try to evaluate a few iterations of the loop until we get the exit
 /// condition gets a value of ExitWhen (true or false).  If we cannot
-/// evaluate the trip count of the loop, return CouldNotCompute.
+/// evaluate the trip count of the loop, return getCouldNotCompute().
 const SCEV *
 ScalarEvolution::ComputeBackedgeTakenCountExhaustively(const Loop *L,
                                                        Value *Cond,
                                                        bool ExitWhen) {
   PHINode *PN = getConstantEvolvingPHI(Cond, L);
-  if (PN == 0) return CouldNotCompute;
+  if (PN == 0) return getCouldNotCompute();
 
   // Since the loop is canonicalized, the PHI node must have two entries.  One
   // entry must be a constant (coming in from outside of the loop), and the
@@ -3385,11 +3505,11 @@ ScalarEvolution::ComputeBackedgeTakenCountExhaustively(const Loop *L,
   bool SecondIsBackedge = L->contains(PN->getIncomingBlock(1));
   Constant *StartCST =
     dyn_cast<Constant>(PN->getIncomingValue(!SecondIsBackedge));
-  if (StartCST == 0) return CouldNotCompute;  // Must be a constant.
+  if (StartCST == 0) return getCouldNotCompute();  // Must be a constant.
 
   Value *BEValue = PN->getIncomingValue(SecondIsBackedge);
   PHINode *PN2 = getConstantEvolvingPHI(BEValue, L);
-  if (PN2 != PN) return CouldNotCompute;  // Not derived from same PHI.
+  if (PN2 != PN) return getCouldNotCompute();  // Not derived from same PHI.
 
   // Okay, we find a PHI node that defines the trip count of this loop.  Execute
   // the loop symbolically to determine when the condition gets a value of
@@ -3402,10 +3522,9 @@ ScalarEvolution::ComputeBackedgeTakenCountExhaustively(const Loop *L,
       dyn_cast_or_null<ConstantInt>(EvaluateExpression(Cond, PHIVal));
 
     // Couldn't symbolically evaluate.
-    if (!CondVal) return CouldNotCompute;
+    if (!CondVal) return getCouldNotCompute();
 
     if (CondVal->getValue() == uint64_t(ExitWhen)) {
-      ConstantEvolutionLoopExitValue[PN] = PHIVal;
       ++NumBruteForceTripCountsComputed;
       return getConstant(Type::Int32Ty, IterationNum);
     }
@@ -3413,12 +3532,12 @@ ScalarEvolution::ComputeBackedgeTakenCountExhaustively(const Loop *L,
     // Compute the value of the PHI node for the next iteration.
     Constant *NextPHI = EvaluateExpression(BEValue, PHIVal);
     if (NextPHI == 0 || NextPHI == PHIVal)
-      return CouldNotCompute;   // Couldn't evaluate or not making progress...
+      return getCouldNotCompute();// Couldn't evaluate or not making progress...
     PHIVal = NextPHI;
   }
 
   // Too many iterations were needed to evaluate.
-  return CouldNotCompute;
+  return getCouldNotCompute();
 }
 
 /// getSCEVAtScope - Return a SCEV expression handle for the specified value
@@ -3457,7 +3576,7 @@ const SCEV* ScalarEvolution::getSCEVAtScope(const SCEV *V, const Loop *L) {
               Constant *RV = getConstantEvolutionLoopExitValue(PN,
                                                    BTCC->getValue()->getValue(),
                                                                LI);
-              if (RV) return getUnknown(RV);
+              if (RV) return getSCEV(RV);
             }
           }
 
@@ -3471,7 +3590,7 @@ const SCEV* ScalarEvolution::getSCEVAtScope(const SCEV *V, const Loop *L) {
         std::pair<std::map<const Loop *, Constant *>::iterator, bool> Pair =
           Values.insert(std::make_pair(L, static_cast<Constant *>(0)));
         if (!Pair.second)
-          return Pair.first->second ? &*getUnknown(Pair.first->second) : V;
+          return Pair.first->second ? &*getSCEV(Pair.first->second) : V;
 
         std::vector<Constant*> Operands;
         Operands.reserve(I->getNumOperands());
@@ -3520,7 +3639,7 @@ const SCEV* ScalarEvolution::getSCEVAtScope(const SCEV *V, const Loop *L) {
           C = ConstantFoldInstOperands(I->getOpcode(), I->getType(),
                                        &Operands[0], Operands.size());
         Pair.first->second = C;
-        return getUnknown(C);
+        return getSCEV(C);
       }
     }
 
@@ -3574,7 +3693,7 @@ const SCEV* ScalarEvolution::getSCEVAtScope(const SCEV *V, const Loop *L) {
       // To evaluate this recurrence, we need to know how many times the AddRec
       // loop iterates.  Compute this now.
       const SCEV* BackedgeTakenCount = getBackedgeTakenCount(AddRec->getLoop());
-      if (BackedgeTakenCount == CouldNotCompute) return AddRec;
+      if (BackedgeTakenCount == getCouldNotCompute()) return AddRec;
 
       // Then, evaluate the AddRec.
       return AddRec->evaluateAtIteration(BackedgeTakenCount, *this);
@@ -3729,12 +3848,12 @@ const SCEV* ScalarEvolution::HowFarToZero(const SCEV *V, const Loop *L) {
   if (const SCEVConstant *C = dyn_cast<SCEVConstant>(V)) {
     // If the value is already zero, the branch will execute zero times.
     if (C->getValue()->isZero()) return C;
-    return CouldNotCompute;  // Otherwise it will loop infinitely.
+    return getCouldNotCompute();  // Otherwise it will loop infinitely.
   }
 
   const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(V);
   if (!AddRec || AddRec->getLoop() != L)
-    return CouldNotCompute;
+    return getCouldNotCompute();
 
   if (AddRec->isAffine()) {
     // If this is an affine expression, the execution count of this branch is
@@ -3798,7 +3917,7 @@ const SCEV* ScalarEvolution::HowFarToZero(const SCEV *V, const Loop *L) {
     }
   }
 
-  return CouldNotCompute;
+  return getCouldNotCompute();
 }
 
 /// HowFarToNonZero - Return the number of times a backedge checking the
@@ -3814,12 +3933,12 @@ const SCEV* ScalarEvolution::HowFarToNonZero(const SCEV *V, const Loop *L) {
   if (const SCEVConstant *C = dyn_cast<SCEVConstant>(V)) {
     if (!C->getValue()->isNullValue())
       return getIntegerSCEV(0, C->getType());
-    return CouldNotCompute;  // Otherwise it will loop infinitely.
+    return getCouldNotCompute();  // Otherwise it will loop infinitely.
   }
 
   // We could implement others, but I really doubt anyone writes loops like
   // this, and if they did, they would already be constant folded.
-  return CouldNotCompute;
+  return getCouldNotCompute();
 }
 
 /// getLoopPredecessor - If the given loop's header has exactly one unique
@@ -4037,7 +4156,7 @@ const SCEV* ScalarEvolution::getBECount(const SCEV* Start,
     getAddExpr(getZeroExtendExpr(Diff, WideTy),
                getZeroExtendExpr(RoundUp, WideTy));
   if (getZeroExtendExpr(Add, WideTy) != OperandExtendedAdd)
-    return CouldNotCompute;
+    return getCouldNotCompute();
 
   return getUDivExpr(Add, Step);
 }
@@ -4049,11 +4168,11 @@ ScalarEvolution::BackedgeTakenInfo
 ScalarEvolution::HowManyLessThans(const SCEV *LHS, const SCEV *RHS,
                                   const Loop *L, bool isSigned) {
   // Only handle:  "ADDREC < LoopInvariant".
-  if (!RHS->isLoopInvariant(L)) return CouldNotCompute;
+  if (!RHS->isLoopInvariant(L)) return getCouldNotCompute();
 
   const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(LHS);
   if (!AddRec || AddRec->getLoop() != L)
-    return CouldNotCompute;
+    return getCouldNotCompute();
 
   if (AddRec->isAffine()) {
     // FORNOW: We only support unit strides.
@@ -4063,7 +4182,7 @@ ScalarEvolution::HowManyLessThans(const SCEV *LHS, const SCEV *RHS,
     // TODO: handle non-constant strides.
     const SCEVConstant *CStep = dyn_cast<SCEVConstant>(Step);
     if (!CStep || CStep->isZero())
-      return CouldNotCompute;
+      return getCouldNotCompute();
     if (CStep->isOne()) {
       // With unit stride, the iteration never steps past the limit value.
     } else if (CStep->getValue()->getValue().isStrictlyPositive()) {
@@ -4074,19 +4193,19 @@ ScalarEvolution::HowManyLessThans(const SCEV *LHS, const SCEV *RHS,
           APInt Max = APInt::getSignedMaxValue(BitWidth);
           if ((Max - CStep->getValue()->getValue())
                 .slt(CLimit->getValue()->getValue()))
-            return CouldNotCompute;
+            return getCouldNotCompute();
         } else {
           APInt Max = APInt::getMaxValue(BitWidth);
           if ((Max - CStep->getValue()->getValue())
                 .ult(CLimit->getValue()->getValue()))
-            return CouldNotCompute;
+            return getCouldNotCompute();
         }
       } else
         // TODO: handle non-constant limit values below.
-        return CouldNotCompute;
+        return getCouldNotCompute();
     } else
       // TODO: handle negative strides below.
-      return CouldNotCompute;
+      return getCouldNotCompute();
 
     // We know the LHS is of the form {n,+,s} and the RHS is some loop-invariant
     // m.  So, we count the number of iterations in which {n,+,s} < m is true.
@@ -4126,12 +4245,12 @@ ScalarEvolution::HowManyLessThans(const SCEV *LHS, const SCEV *RHS,
 
     // The maximum backedge count is similar, except using the minimum start
     // value and the maximum end value.
-    const SCEV* MaxBECount = getBECount(MinStart, MaxEnd, Step);;
+    const SCEV* MaxBECount = getBECount(MinStart, MaxEnd, Step);
 
     return BackedgeTakenInfo(BECount, MaxBECount);
   }
 
-  return CouldNotCompute;
+  return getCouldNotCompute();
 }
 
 /// getNumIterationsInRange - Return the number of iterations of this loop that
@@ -4319,7 +4438,7 @@ ScalarEvolution::SCEVCallbackVH::SCEVCallbackVH(Value *V, ScalarEvolution *se)
 //===----------------------------------------------------------------------===//
 
 ScalarEvolution::ScalarEvolution()
-  : FunctionPass(&ID), CouldNotCompute(new SCEVCouldNotCompute()) {
+  : FunctionPass(&ID) {
 }
 
 bool ScalarEvolution::runOnFunction(Function &F) {
@@ -4334,45 +4453,8 @@ void ScalarEvolution::releaseMemory() {
   BackedgeTakenCounts.clear();
   ConstantEvolutionLoopExitValue.clear();
   ValuesAtScopes.clear();
-
-  for (std::map<ConstantInt*, SCEVConstant*>::iterator
-       I = SCEVConstants.begin(), E = SCEVConstants.end(); I != E; ++I)
-    delete I->second;
-  for (std::map<std::pair<const SCEV*, const Type*>,
-       SCEVTruncateExpr*>::iterator I = SCEVTruncates.begin(),
-       E = SCEVTruncates.end(); I != E; ++I)
-    delete I->second;
-  for (std::map<std::pair<const SCEV*, const Type*>,
-       SCEVZeroExtendExpr*>::iterator I = SCEVZeroExtends.begin(),
-       E = SCEVZeroExtends.end(); I != E; ++I)
-    delete I->second;
-  for (std::map<std::pair<unsigned, std::vector<const SCEV*> >,
-       SCEVCommutativeExpr*>::iterator I = SCEVCommExprs.begin(),
-       E = SCEVCommExprs.end(); I != E; ++I)
-    delete I->second;
-  for (std::map<std::pair<const SCEV*, const SCEV*>, SCEVUDivExpr*>::iterator
-       I = SCEVUDivs.begin(), E = SCEVUDivs.end(); I != E; ++I)
-    delete I->second;
-  for (std::map<std::pair<const SCEV*, const Type*>,
-       SCEVSignExtendExpr*>::iterator I =  SCEVSignExtends.begin(),
-       E = SCEVSignExtends.end(); I != E; ++I)
-    delete I->second;
-  for (std::map<std::pair<const Loop *, std::vector<const SCEV*> >,
-       SCEVAddRecExpr*>::iterator I = SCEVAddRecExprs.begin(),
-       E = SCEVAddRecExprs.end(); I != E; ++I)
-    delete I->second;
-  for (std::map<Value*, SCEVUnknown*>::iterator I = SCEVUnknowns.begin(),
-       E = SCEVUnknowns.end(); I != E; ++I)
-    delete I->second;
-
-  SCEVConstants.clear();
-  SCEVTruncates.clear();
-  SCEVZeroExtends.clear();
-  SCEVCommExprs.clear();
-  SCEVUDivs.clear();
-  SCEVSignExtends.clear();
-  SCEVAddRecExprs.clear();
-  SCEVUnknowns.clear();
+  UniqueSCEVs.clear();
+  SCEVAllocator.Reset();
 }
 
 void ScalarEvolution::getAnalysisUsage(AnalysisUsage &AU) const {
diff --git a/lib/Analysis/ScalarEvolutionExpander.cpp b/lib/Analysis/ScalarEvolutionExpander.cpp
index 4cc5ebc..729a0c3 100644
--- a/lib/Analysis/ScalarEvolutionExpander.cpp
+++ b/lib/Analysis/ScalarEvolutionExpander.cpp
@@ -19,16 +19,24 @@
 #include "llvm/ADT/STLExtras.h"
 using namespace llvm;
 
-/// InsertCastOfTo - Insert a cast of V to the specified type, doing what
-/// we can to share the casts.
-Value *SCEVExpander::InsertCastOfTo(Instruction::CastOps opcode, Value *V, 
-                                    const Type *Ty) {
+/// InsertNoopCastOfTo - Insert a cast of V to the specified type,
+/// which must be possible with a noop cast, doing what we can to share
+/// the casts.
+Value *SCEVExpander::InsertNoopCastOfTo(Value *V, const Type *Ty) {
+  Instruction::CastOps Op = CastInst::getCastOpcode(V, false, Ty, false);
+  assert((Op == Instruction::BitCast ||
+          Op == Instruction::PtrToInt ||
+          Op == Instruction::IntToPtr) &&
+         "InsertNoopCastOfTo cannot perform non-noop casts!");
+  assert(SE.getTypeSizeInBits(V->getType()) == SE.getTypeSizeInBits(Ty) &&
+         "InsertNoopCastOfTo cannot change sizes!");
+
   // Short-circuit unnecessary bitcasts.
-  if (opcode == Instruction::BitCast && V->getType() == Ty)
+  if (Op == Instruction::BitCast && V->getType() == Ty)
     return V;
 
   // Short-circuit unnecessary inttoptr<->ptrtoint casts.
-  if ((opcode == Instruction::PtrToInt || opcode == Instruction::IntToPtr) &&
+  if ((Op == Instruction::PtrToInt || Op == Instruction::IntToPtr) &&
       SE.getTypeSizeInBits(Ty) == SE.getTypeSizeInBits(V->getType())) {
     if (CastInst *CI = dyn_cast<CastInst>(V))
       if ((CI->getOpcode() == Instruction::PtrToInt ||
@@ -46,7 +54,7 @@ Value *SCEVExpander::InsertCastOfTo(Instruction::CastOps opcode, Value *V,
 
   // FIXME: keep track of the cast instruction.
   if (Constant *C = dyn_cast<Constant>(V))
-    return ConstantExpr::getCast(opcode, C, Ty);
+    return ConstantExpr::getCast(Op, C, Ty);
   
   if (Argument *A = dyn_cast<Argument>(V)) {
     // Check to see if there is already a cast!
@@ -54,7 +62,7 @@ Value *SCEVExpander::InsertCastOfTo(Instruction::CastOps opcode, Value *V,
          UI != E; ++UI)
       if ((*UI)->getType() == Ty)
         if (CastInst *CI = dyn_cast<CastInst>(cast<Instruction>(*UI)))
-          if (CI->getOpcode() == opcode) {
+          if (CI->getOpcode() == Op) {
             // If the cast isn't the first instruction of the function, move it.
             if (BasicBlock::iterator(CI) !=
                 A->getParent()->getEntryBlock().begin()) {
@@ -62,7 +70,7 @@ Value *SCEVExpander::InsertCastOfTo(Instruction::CastOps opcode, Value *V,
               // The old cast is left in place in case it is being used
               // as an insert point.
               Instruction *NewCI =
-                CastInst::Create(opcode, V, Ty, "",
+                CastInst::Create(Op, V, Ty, "",
                                  A->getParent()->getEntryBlock().begin());
               NewCI->takeName(CI);
               CI->replaceAllUsesWith(NewCI);
@@ -71,7 +79,7 @@ Value *SCEVExpander::InsertCastOfTo(Instruction::CastOps opcode, Value *V,
             return CI;
           }
 
-    Instruction *I = CastInst::Create(opcode, V, Ty, V->getName(),
+    Instruction *I = CastInst::Create(Op, V, Ty, V->getName(),
                                       A->getParent()->getEntryBlock().begin());
     InsertedValues.insert(I);
     return I;
@@ -84,7 +92,7 @@ Value *SCEVExpander::InsertCastOfTo(Instruction::CastOps opcode, Value *V,
        UI != E; ++UI) {
     if ((*UI)->getType() == Ty)
       if (CastInst *CI = dyn_cast<CastInst>(cast<Instruction>(*UI)))
-        if (CI->getOpcode() == opcode) {
+        if (CI->getOpcode() == Op) {
           BasicBlock::iterator It = I; ++It;
           if (isa<InvokeInst>(I))
             It = cast<InvokeInst>(I)->getNormalDest()->begin();
@@ -93,7 +101,7 @@ Value *SCEVExpander::InsertCastOfTo(Instruction::CastOps opcode, Value *V,
             // Recreate the cast at the beginning of the entry block.
             // The old cast is left in place in case it is being used
             // as an insert point.
-            Instruction *NewCI = CastInst::Create(opcode, V, Ty, "", It);
+            Instruction *NewCI = CastInst::Create(Op, V, Ty, "", It);
             NewCI->takeName(CI);
             CI->replaceAllUsesWith(NewCI);
             return NewCI;
@@ -105,28 +113,15 @@ Value *SCEVExpander::InsertCastOfTo(Instruction::CastOps opcode, Value *V,
   if (InvokeInst *II = dyn_cast<InvokeInst>(I))
     IP = II->getNormalDest()->begin();
   while (isa<PHINode>(IP)) ++IP;
-  Instruction *CI = CastInst::Create(opcode, V, Ty, V->getName(), IP);
+  Instruction *CI = CastInst::Create(Op, V, Ty, V->getName(), IP);
   InsertedValues.insert(CI);
   return CI;
 }
 
-/// InsertNoopCastOfTo - Insert a cast of V to the specified type,
-/// which must be possible with a noop cast.
-Value *SCEVExpander::InsertNoopCastOfTo(Value *V, const Type *Ty) {
-  Instruction::CastOps Op = CastInst::getCastOpcode(V, false, Ty, false);
-  assert((Op == Instruction::BitCast ||
-          Op == Instruction::PtrToInt ||
-          Op == Instruction::IntToPtr) &&
-         "InsertNoopCastOfTo cannot perform non-noop casts!");
-  assert(SE.getTypeSizeInBits(V->getType()) == SE.getTypeSizeInBits(Ty) &&
-         "InsertNoopCastOfTo cannot change sizes!");
-  return InsertCastOfTo(Op, V, Ty);
-}
-
 /// InsertBinop - Insert the specified binary operator, doing a small amount
 /// of work to avoid inserting an obviously redundant operation.
-Value *SCEVExpander::InsertBinop(Instruction::BinaryOps Opcode, Value *LHS,
-                                 Value *RHS, BasicBlock::iterator InsertPt) {
+Value *SCEVExpander::InsertBinop(Instruction::BinaryOps Opcode,
+                                 Value *LHS, Value *RHS) {
   // Fold a binop with constant operands.
   if (Constant *CLHS = dyn_cast<Constant>(LHS))
     if (Constant *CRHS = dyn_cast<Constant>(RHS))
@@ -134,10 +129,10 @@ Value *SCEVExpander::InsertBinop(Instruction::BinaryOps Opcode, Value *LHS,
 
   // Do a quick scan to see if we have this binop nearby.  If so, reuse it.
   unsigned ScanLimit = 6;
-  BasicBlock::iterator BlockBegin = InsertPt->getParent()->begin();
-  if (InsertPt != BlockBegin) {
-    // Scanning starts from the last instruction before InsertPt.
-    BasicBlock::iterator IP = InsertPt;
+  BasicBlock::iterator BlockBegin = Builder.GetInsertBlock()->begin();
+  // Scanning starts from the last instruction before the insertion point.
+  BasicBlock::iterator IP = Builder.GetInsertPoint();
+  if (IP != BlockBegin) {
     --IP;
     for (; ScanLimit; --IP, --ScanLimit) {
       if (IP->getOpcode() == (unsigned)Opcode && IP->getOperand(0) == LHS &&
@@ -146,9 +141,9 @@ Value *SCEVExpander::InsertBinop(Instruction::BinaryOps Opcode, Value *LHS,
       if (IP == BlockBegin) break;
     }
   }
-  
+
   // If we haven't found this binop, insert it.
-  Instruction *BO = BinaryOperator::Create(Opcode, LHS, RHS, "tmp", InsertPt);
+  Value *BO = Builder.CreateBinOp(Opcode, LHS, RHS, "tmp");
   InsertedValues.insert(BO);
   return BO;
 }
@@ -190,8 +185,9 @@ static bool FactorOutConstant(const SCEV* &S,
   if (const SCEVMulExpr *M = dyn_cast<SCEVMulExpr>(S))
     if (const SCEVConstant *C = dyn_cast<SCEVConstant>(M->getOperand(0)))
       if (!C->getValue()->getValue().srem(Factor)) {
-        const SmallVectorImpl<const SCEV*> &MOperands = M->getOperands();
-        SmallVector<const SCEV*, 4> NewMulOps(MOperands.begin(), MOperands.end());
+        const SmallVectorImpl<const SCEV *> &MOperands = M->getOperands();
+        SmallVector<const SCEV *, 4> NewMulOps(MOperands.begin(),
+                                               MOperands.end());
         NewMulOps[0] =
           SE.getConstant(C->getValue()->getValue().sdiv(Factor));
         S = SE.getMulExpr(NewMulOps);
@@ -336,10 +332,10 @@ Value *SCEVExpander::expandAddToGEP(const SCEV* const *op_begin,
 
     // Do a quick scan to see if we have this GEP nearby.  If so, reuse it.
     unsigned ScanLimit = 6;
-    BasicBlock::iterator BlockBegin = InsertPt->getParent()->begin();
-    if (InsertPt != BlockBegin) {
-      // Scanning starts from the last instruction before InsertPt.
-      BasicBlock::iterator IP = InsertPt;
+    BasicBlock::iterator BlockBegin = Builder.GetInsertBlock()->begin();
+    // Scanning starts from the last instruction before the insertion point.
+    BasicBlock::iterator IP = Builder.GetInsertPoint();
+    if (IP != BlockBegin) {
       --IP;
       for (; ScanLimit; --IP, --ScanLimit) {
         if (IP->getOpcode() == Instruction::GetElementPtr &&
@@ -349,16 +345,16 @@ Value *SCEVExpander::expandAddToGEP(const SCEV* const *op_begin,
       }
     }
 
-    Value *GEP = GetElementPtrInst::Create(V, Idx, "scevgep", InsertPt);
+    Value *GEP = Builder.CreateGEP(V, Idx, "scevgep");
     InsertedValues.insert(GEP);
     return GEP;
   }
 
   // Insert a pretty getelementptr.
-  Value *GEP = GetElementPtrInst::Create(V,
-                                         GepIndices.begin(),
-                                         GepIndices.end(),
-                                         "scevgep", InsertPt);
+  Value *GEP = Builder.CreateGEP(V,
+                                 GepIndices.begin(),
+                                 GepIndices.end(),
+                                 "scevgep");
   Ops.push_back(SE.getUnknown(GEP));
   InsertedValues.insert(GEP);
   return expand(SE.getAddExpr(Ops));
@@ -373,8 +369,7 @@ Value *SCEVExpander::visitAddExpr(const SCEVAddExpr *S) {
   if (SE.TD)
     if (const PointerType *PTy = dyn_cast<PointerType>(V->getType())) {
       const SmallVectorImpl<const SCEV*> &Ops = S->getOperands();
-      return expandAddToGEP(&Ops[0], &Ops[Ops.size() - 1],
-                            PTy, Ty, V);
+      return expandAddToGEP(&Ops[0], &Ops[Ops.size() - 1], PTy, Ty, V);
     }
 
   V = InsertNoopCastOfTo(V, Ty);
@@ -382,7 +377,7 @@ Value *SCEVExpander::visitAddExpr(const SCEVAddExpr *S) {
   // Emit a bunch of add instructions
   for (int i = S->getNumOperands()-2; i >= 0; --i) {
     Value *W = expandCodeFor(S->getOperand(i), Ty);
-    V = InsertBinop(Instruction::Add, V, W, InsertPt);
+    V = InsertBinop(Instruction::Add, V, W);
   }
   return V;
 }
@@ -400,12 +395,12 @@ Value *SCEVExpander::visitMulExpr(const SCEVMulExpr *S) {
   // Emit a bunch of multiply instructions
   for (; i >= FirstOp; --i) {
     Value *W = expandCodeFor(S->getOperand(i), Ty);
-    V = InsertBinop(Instruction::Mul, V, W, InsertPt);
+    V = InsertBinop(Instruction::Mul, V, W);
   }
 
   // -1 * ...  --->  0 - ...
   if (FirstOp == 1)
-    V = InsertBinop(Instruction::Sub, Constant::getNullValue(Ty), V, InsertPt);
+    V = InsertBinop(Instruction::Sub, Constant::getNullValue(Ty), V);
   return V;
 }
 
@@ -417,12 +412,11 @@ Value *SCEVExpander::visitUDivExpr(const SCEVUDivExpr *S) {
     const APInt &RHS = SC->getValue()->getValue();
     if (RHS.isPowerOf2())
       return InsertBinop(Instruction::LShr, LHS,
-                         ConstantInt::get(Ty, RHS.logBase2()),
-                         InsertPt);
+                         ConstantInt::get(Ty, RHS.logBase2()));
   }
 
   Value *RHS = expandCodeFor(S->getRHS(), Ty);
-  return InsertBinop(Instruction::UDiv, LHS, RHS, InsertPt);
+  return InsertBinop(Instruction::UDiv, LHS, RHS);
 }
 
 /// Move parts of Base into Rest to leave Base with the minimal
@@ -463,18 +457,19 @@ Value *SCEVExpander::visitAddRecExpr(const SCEVAddRecExpr *S) {
   if (CanonicalIV &&
       SE.getTypeSizeInBits(CanonicalIV->getType()) >
       SE.getTypeSizeInBits(Ty)) {
-    const SCEV* Start = SE.getAnyExtendExpr(S->getStart(),
+    const SCEV *Start = SE.getAnyExtendExpr(S->getStart(),
+                                            CanonicalIV->getType());
+    const SCEV *Step = SE.getAnyExtendExpr(S->getStepRecurrence(SE),
                                            CanonicalIV->getType());
-    const SCEV* Step = SE.getAnyExtendExpr(S->getStepRecurrence(SE),
-                                          CanonicalIV->getType());
     Value *V = expand(SE.getAddRecExpr(Start, Step, S->getLoop()));
-    BasicBlock::iterator SaveInsertPt = InsertPt;
+    BasicBlock *SaveInsertBB = Builder.GetInsertBlock();
+    BasicBlock::iterator SaveInsertPt = Builder.GetInsertPoint();
     BasicBlock::iterator NewInsertPt =
       next(BasicBlock::iterator(cast<Instruction>(V)));
     while (isa<PHINode>(NewInsertPt)) ++NewInsertPt;
     V = expandCodeFor(SE.getTruncateExpr(SE.getUnknown(V), Ty), 0,
                       NewInsertPt);
-    InsertPt = SaveInsertPt;
+    Builder.SetInsertPoint(SaveInsertBB, SaveInsertPt);
     return V;
   }
 
@@ -524,9 +519,10 @@ Value *SCEVExpander::visitAddRecExpr(const SCEVAddRecExpr *S) {
     // Create and insert the PHI node for the induction variable in the
     // specified loop.
     BasicBlock *Header = L->getHeader();
+    BasicBlock *Preheader = L->getLoopPreheader();
     PHINode *PN = PHINode::Create(Ty, "indvar", Header->begin());
     InsertedValues.insert(PN);
-    PN->addIncoming(Constant::getNullValue(Ty), L->getLoopPreheader());
+    PN->addIncoming(Constant::getNullValue(Ty), Preheader);
 
     pred_iterator HPI = pred_begin(Header);
     assert(HPI != pred_end(Header) && "Loop with zero preds???");
@@ -542,7 +538,7 @@ Value *SCEVExpander::visitAddRecExpr(const SCEVAddRecExpr *S) {
     InsertedValues.insert(Add);
 
     pred_iterator PI = pred_begin(Header);
-    if (*PI == L->getLoopPreheader())
+    if (*PI == Preheader)
       ++PI;
     PN->addIncoming(Add, *PI);
     return PN;
@@ -587,7 +583,7 @@ Value *SCEVExpander::visitTruncateExpr(const SCEVTruncateExpr *S) {
   const Type *Ty = SE.getEffectiveSCEVType(S->getType());
   Value *V = expandCodeFor(S->getOperand(),
                            SE.getEffectiveSCEVType(S->getOperand()->getType()));
-  Instruction *I = new TruncInst(V, Ty, "tmp.", InsertPt);
+  Value *I = Builder.CreateTrunc(V, Ty, "tmp");
   InsertedValues.insert(I);
   return I;
 }
@@ -596,7 +592,7 @@ Value *SCEVExpander::visitZeroExtendExpr(const SCEVZeroExtendExpr *S) {
   const Type *Ty = SE.getEffectiveSCEVType(S->getType());
   Value *V = expandCodeFor(S->getOperand(),
                            SE.getEffectiveSCEVType(S->getOperand()->getType()));
-  Instruction *I = new ZExtInst(V, Ty, "tmp.", InsertPt);
+  Value *I = Builder.CreateZExt(V, Ty, "tmp");
   InsertedValues.insert(I);
   return I;
 }
@@ -605,7 +601,7 @@ Value *SCEVExpander::visitSignExtendExpr(const SCEVSignExtendExpr *S) {
   const Type *Ty = SE.getEffectiveSCEVType(S->getType());
   Value *V = expandCodeFor(S->getOperand(),
                            SE.getEffectiveSCEVType(S->getOperand()->getType()));
-  Instruction *I = new SExtInst(V, Ty, "tmp.", InsertPt);
+  Value *I = Builder.CreateSExt(V, Ty, "tmp");
   InsertedValues.insert(I);
   return I;
 }
@@ -615,10 +611,9 @@ Value *SCEVExpander::visitSMaxExpr(const SCEVSMaxExpr *S) {
   Value *LHS = expandCodeFor(S->getOperand(0), Ty);
   for (unsigned i = 1; i < S->getNumOperands(); ++i) {
     Value *RHS = expandCodeFor(S->getOperand(i), Ty);
-    Instruction *ICmp =
-      new ICmpInst(ICmpInst::ICMP_SGT, LHS, RHS, "tmp", InsertPt);
+    Value *ICmp = Builder.CreateICmpSGT(LHS, RHS, "tmp");
     InsertedValues.insert(ICmp);
-    Instruction *Sel = SelectInst::Create(ICmp, LHS, RHS, "smax", InsertPt);
+    Value *Sel = Builder.CreateSelect(ICmp, LHS, RHS, "smax");
     InsertedValues.insert(Sel);
     LHS = Sel;
   }
@@ -630,10 +625,9 @@ Value *SCEVExpander::visitUMaxExpr(const SCEVUMaxExpr *S) {
   Value *LHS = expandCodeFor(S->getOperand(0), Ty);
   for (unsigned i = 1; i < S->getNumOperands(); ++i) {
     Value *RHS = expandCodeFor(S->getOperand(i), Ty);
-    Instruction *ICmp =
-      new ICmpInst(ICmpInst::ICMP_UGT, LHS, RHS, "tmp", InsertPt);
+    Value *ICmp = Builder.CreateICmpUGT(LHS, RHS, "tmp");
     InsertedValues.insert(ICmp);
-    Instruction *Sel = SelectInst::Create(ICmp, LHS, RHS, "umax", InsertPt);
+    Value *Sel = Builder.CreateSelect(ICmp, LHS, RHS, "umax");
     InsertedValues.insert(Sel);
     LHS = Sel;
   }
@@ -652,11 +646,10 @@ Value *SCEVExpander::expandCodeFor(const SCEV* SH, const Type *Ty) {
 }
 
 Value *SCEVExpander::expand(const SCEV *S) {
-  BasicBlock::iterator SaveInsertPt = InsertPt;
-
   // Compute an insertion point for this SCEV object. Hoist the instructions
   // as far out in the loop nest as possible.
-  for (Loop *L = SE.LI->getLoopFor(InsertPt->getParent()); ;
+  Instruction *InsertPt = Builder.GetInsertPoint();
+  for (Loop *L = SE.LI->getLoopFor(Builder.GetInsertBlock()); ;
        L = L->getParentLoop())
     if (S->isLoopInvariant(L)) {
       if (!L) break;
@@ -668,7 +661,8 @@ Value *SCEVExpander::expand(const SCEV *S) {
       // there) so that it is guaranteed to dominate any user inside the loop.
       if (L && S->hasComputableLoopEvolution(L))
         InsertPt = L->getHeader()->getFirstNonPHI();
-      while (isInsertedInstruction(InsertPt)) ++InsertPt;
+      while (isInsertedInstruction(InsertPt))
+        InsertPt = next(BasicBlock::iterator(InsertPt));
       break;
     }
 
@@ -676,10 +670,12 @@ Value *SCEVExpander::expand(const SCEV *S) {
   std::map<std::pair<const SCEV *, Instruction *>,
            AssertingVH<Value> >::iterator I =
     InsertedExpressions.find(std::make_pair(S, InsertPt));
-  if (I != InsertedExpressions.end()) {
-    InsertPt = SaveInsertPt;
+  if (I != InsertedExpressions.end())
     return I->second;
-  }
+
+  BasicBlock *SaveInsertBB = Builder.GetInsertBlock();
+  BasicBlock::iterator SaveInsertPt = Builder.GetInsertPoint();
+  Builder.SetInsertPoint(InsertPt->getParent(), InsertPt);
 
   // Expand the expression into instructions.
   Value *V = visit(S);
@@ -687,7 +683,7 @@ Value *SCEVExpander::expand(const SCEV *S) {
   // Remember the expanded value for this SCEV at this location.
   InsertedExpressions[std::make_pair(S, InsertPt)] = V;
 
-  InsertPt = SaveInsertPt;
+  Builder.SetInsertPoint(SaveInsertBB, SaveInsertPt);
   return V;
 }
 
@@ -701,8 +697,10 @@ SCEVExpander::getOrInsertCanonicalInductionVariable(const Loop *L,
   assert(Ty->isInteger() && "Can only insert integer induction variables!");
   const SCEV* H = SE.getAddRecExpr(SE.getIntegerSCEV(0, Ty),
                                    SE.getIntegerSCEV(1, Ty), L);
-  BasicBlock::iterator SaveInsertPt = InsertPt;
+  BasicBlock *SaveInsertBB = Builder.GetInsertBlock();
+  BasicBlock::iterator SaveInsertPt = Builder.GetInsertPoint();
   Value *V = expandCodeFor(H, 0, L->getHeader()->begin());
-  InsertPt = SaveInsertPt;
+  if (SaveInsertBB)
+    Builder.SetInsertPoint(SaveInsertBB, SaveInsertPt);
   return V;
 }
diff --git a/lib/Analysis/ValueTracking.cpp b/lib/Analysis/ValueTracking.cpp
index 7509e91..07a18fe 100644
--- a/lib/Analysis/ValueTracking.cpp
+++ b/lib/Analysis/ValueTracking.cpp
@@ -249,7 +249,10 @@ void llvm::ComputeMaskedBits(Value *V, const APInt &Mask,
   }
   case Instruction::BitCast: {
     const Type *SrcTy = I->getOperand(0)->getType();
-    if (SrcTy->isInteger() || isa<PointerType>(SrcTy)) {
+    if ((SrcTy->isInteger() || isa<PointerType>(SrcTy)) &&
+        // TODO: For now, not handling conversions like:
+        // (bitcast i64 %x to <2 x i32>)
+        !isa<VectorType>(I->getType())) {
       ComputeMaskedBits(I->getOperand(0), Mask, KnownZero, KnownOne, TD,
                         Depth+1);
       return;