[Mem2Reg] Fix nondeterministic corner case

[JosephTremoulet]

Summary

When mem2reg inserts phi nodes in blocks with unreachable predecessors,
it adds undef operands for those incoming edges. When there are
multiple such predecessors, the order is currently based on the address
of the BasicBlocks. This change fixes that by using the BBNumbers in
the sort/search predicates, as is done elsewhere in mem2reg to ensure
determinism.

Also adds a testcase with a bunch of unreachable preds, which
(nodeterministically) fails without the fix.

[majnemer]

LGTM

llvm/trunk/lib/Transforms/Utils/PromoteMemoryToRegister.cpp

if (SomePHI->getNumIncomingValues() == getNumPreds(BB))
       continue;
 
     // Get the preds for BB.
     SmallVector<BasicBlock *, 16> Preds(pred_begin(BB), pred_end(BB));
 
     // 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!");
 
       // Remove the entry
       Preds.erase(EntIt);
     }
 
     // At this point, the blocks left in the preds list must have dummy

llvm/trunk/test/Transforms/Mem2Reg/undef-order.ll

+;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
+}