Index: lib/Transforms/Utils/PromoteMemoryToRegister.cpp
===================================================================
--- lib/Transforms/Utils/PromoteMemoryToRegister.cpp
+++ lib/Transforms/Utils/PromoteMemoryToRegister.cpp
@@ -37,6 +37,7 @@
 #include "llvm/IR/IntrinsicInst.h"
 #include "llvm/IR/Metadata.h"
 #include "llvm/IR/Module.h"
+#include "llvm/IR/PredIteratorCache.h"
 #include "llvm/Transforms/Utils/Local.h"
 #include <algorithm>
 using namespace llvm;
@@ -265,8 +266,8 @@
   /// behavior.
   DenseMap<BasicBlock *, unsigned> BBNumbers;
 
-  /// Lazily compute the number of predecessors a block has.
-  DenseMap<const BasicBlock *, unsigned> BBNumPreds;
+  /// Cache of predecessor info
+  PredIteratorCache PredCache;
 
 public:
   PromoteMem2Reg(ArrayRef<AllocaInst *> Allocas, DominatorTree &DT,
@@ -284,13 +285,6 @@
     --AllocaIdx;
   }
 
-  unsigned getNumPreds(const BasicBlock *BB) {
-    unsigned &NP = BBNumPreds[BB];
-    if (NP == 0)
-      NP = std::distance(pred_begin(BB), pred_end(BB)) + 1;
-    return NP - 1;
-  }
-
   void ComputeLiveInBlocks(AllocaInst *AI, AllocaInfo &Info,
                            const SmallPtrSetImpl<BasicBlock *> &DefBlocks,
                            SmallPtrSetImpl<BasicBlock *> &LiveInBlocks);
@@ -721,11 +715,13 @@
     // Only do work here if there the PHI nodes are missing incoming values.  We
     // know that all PHI nodes that were inserted in a block will have the same
     // number of incoming values, so we can just check any of them.
-    if (SomePHI->getNumIncomingValues() == getNumPreds(BB))
+    if (SomePHI->getNumIncomingValues() == PredCache.GetNumPreds(BB))
       continue;
 
     // Get the preds for BB.
-    SmallVector<BasicBlock *, 16> Preds(pred_begin(BB), pred_end(BB));
+    ArrayRef<BasicBlock *> PredRef =
+        makeArrayRef(PredCache.GetPreds(BB), PredCache.GetNumPreds(BB));
+    SmallVector<BasicBlock *, 16> Preds(PredRef.begin(), PredRef.end());
 
     // Ok, now we know that all of the PHI nodes are missing entries for some
     // basic blocks.  Start by sorting the incoming predecessors for efficient
@@ -825,7 +821,7 @@
     // Since the value is live into BB, it is either defined in a predecessor or
     // live into it to.  Add the preds to the worklist unless they are a
     // defining block.
-    for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) {
+    for (BasicBlock **PI = PredCache.GetPreds(BB); *PI; ++PI) {
       BasicBlock *P = *PI;
 
       // The value is not live into a predecessor if it defines the value.
@@ -852,9 +848,9 @@
 
   // Create a PhiNode using the dereferenced type... and add the phi-node to the
   // BasicBlock.
-  PN = PHINode::Create(Allocas[AllocaNo]->getAllocatedType(), getNumPreds(BB),
-                       Allocas[AllocaNo]->getName() + "." + Twine(Version++),
-                       BB->begin());
+  PN = PHINode::Create(
+      Allocas[AllocaNo]->getAllocatedType(), PredCache.GetNumPreds(BB),
+      Allocas[AllocaNo]->getName() + "." + Twine(Version++), BB->begin());
   ++NumPHIInsert;
   PhiToAllocaMap[PN] = AllocaNo;