From 27b1e3bd4f7a064a2672e30cc6be31433ebd300b Mon Sep 17 00:00:00 2001
From: Joseph Tremoulet <jotrem@microsoft.com>
Date: Fri, 30 Nov 2018 19:20:02 +0000
Subject: [PATCH] [Mem2Reg] Fix nondeterministic corner case

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.


Reviewers: majnemer

Reviewed By: majnemer

Subscribers: mgrang, llvm-commits

Differential Revision: https://reviews.llvm.org/D55077

llvm-svn: 348024
---
 .../Transforms/Utils/PromoteMemoryToRegister.cpp   |  8 +++-
 llvm/test/Transforms/Mem2Reg/undef-order.ll        | 53 ++++++++++++++++++++++
 2 files changed, 59 insertions(+), 2 deletions(-)
 create mode 100644 llvm/test/Transforms/Mem2Reg/undef-order.ll

diff --git a/llvm/lib/Transforms/Utils/PromoteMemoryToRegister.cpp b/llvm/lib/Transforms/Utils/PromoteMemoryToRegister.cpp
index 6773ad7..a53083c 100644
--- a/llvm/lib/Transforms/Utils/PromoteMemoryToRegister.cpp
+++ b/llvm/lib/Transforms/Utils/PromoteMemoryToRegister.cpp
@@ -751,14 +751,18 @@ void PromoteMem2Reg::run() {
     // 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!");
 
diff --git a/llvm/test/Transforms/Mem2Reg/undef-order.ll b/llvm/test/Transforms/Mem2Reg/undef-order.ll
new file mode 100644
index 0000000..0968751
--- /dev/null
+++ b/llvm/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
+}
-- 
2.7.4