Index: llvm/trunk/lib/Transforms/Utils/PromoteMemoryToRegister.cpp
===================================================================
--- llvm/trunk/lib/Transforms/Utils/PromoteMemoryToRegister.cpp
+++ llvm/trunk/lib/Transforms/Utils/PromoteMemoryToRegister.cpp
@@ -751,14 +751,18 @@
     // 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
     // access.
-    llvm::sort(Preds);
+    auto CompareBBNumbers = [this](BasicBlock *A, BasicBlock *B) {
+      return BBNumbers.lookup(A) < BBNumbers.lookup(B);
+    };
+    llvm::sort(Preds, CompareBBNumbers);
 
     // Now we loop through all BB's which have entries in SomePHI and remove
     // them from the Preds list.
     for (unsigned i = 0, e = SomePHI->getNumIncomingValues(); i != e; ++i) {
       // Do a log(n) search of the Preds list for the entry we want.
       SmallVectorImpl<BasicBlock *>::iterator EntIt = std::lower_bound(
-          Preds.begin(), Preds.end(), SomePHI->getIncomingBlock(i));
+          Preds.begin(), Preds.end(), SomePHI->getIncomingBlock(i),
+          CompareBBNumbers);
       assert(EntIt != Preds.end() && *EntIt == SomePHI->getIncomingBlock(i) &&
              "PHI node has entry for a block which is not a predecessor!");
 
Index: llvm/trunk/test/Transforms/Mem2Reg/undef-order.ll
===================================================================
--- llvm/trunk/test/Transforms/Mem2Reg/undef-order.ll
+++ llvm/trunk/test/Transforms/Mem2Reg/undef-order.ll
@@ -0,0 +1,53 @@
+;RUN: opt -mem2reg -S < %s | FileCheck %s
+
+declare i1 @cond()
+
+define i32 @foo() {
+Entry:
+    %val = alloca i32
+    %c1 = call i1 @cond()
+    br i1 %c1, label %Store1, label %Store2
+Block1:
+    br label %Join
+Block2:
+    br label %Join
+Block3:
+    br label %Join
+Block4:
+    br label %Join
+Block5:
+    br label %Join
+Store1:
+    store i32 1, i32* %val
+    br label %Join
+Block6:
+    br label %Join
+Block7:
+    br label %Join
+Block8:
+    br label %Join
+Block9:
+    br label %Join
+Block10:
+    br label %Join
+Store2:
+    store i32 2, i32* %val
+    br label %Join
+Block11:
+    br label %Join
+Block12:
+    br label %Join
+Block13:
+    br label %Join
+Block14:
+    br label %Join
+Block15:
+    br label %Join
+Block16:
+    br label %Join
+Join:
+; Phi inserted here should have operands appended deterministically
+; CHECK: %val.0 = phi i32 [ 1, %Store1 ], [ 2, %Store2 ], [ undef, %Block1 ], [ undef, %Block2 ], [ undef, %Block3 ], [ undef, %Block4 ], [ undef, %Block5 ], [ undef, %Block6 ], [ undef, %Block7 ], [ undef, %Block8 ], [ undef, %Block9 ], [ undef, %Block10 ], [ undef, %Block11 ], [ undef, %Block12 ], [ undef, %Block13 ], [ undef, %Block14 ], [ undef, %Block15 ], [ undef, %Block16 ]
+    %result = load i32, i32* %val
+    ret i32 %result
+}