From f52666985d7011b539f26f54e09a5c89b62dad56 Mon Sep 17 00:00:00 2001
From: Nathan Chancellor <nathan@kernel.org>
Date: Mon, 21 Jun 2021 10:18:55 -0700
Subject: [PATCH] Revert "[LoopDeletion] Handle Phis with similar inputs from
 different blocks"

This reverts commit bb1dc876ebb8a2eef38d5183d00c2db1437f1c91.

This patch causes an assertion failure when building an arm64 defconfig
Linux kernel.

See https://reviews.llvm.org/D103959 for a link to the original bug
report and a reduced reproducer.
---
 llvm/lib/Transforms/Scalar/LoopDeletion.cpp        | 47 +++++++++++-----------
 .../LoopDeletion/eval_first_iteration.ll           | 11 +++--
 2 files changed, 28 insertions(+), 30 deletions(-)

diff --git a/llvm/lib/Transforms/Scalar/LoopDeletion.cpp b/llvm/lib/Transforms/Scalar/LoopDeletion.cpp
index a287f68..4d7925e 100644
--- a/llvm/lib/Transforms/Scalar/LoopDeletion.cpp
+++ b/llvm/lib/Transforms/Scalar/LoopDeletion.cpp
@@ -245,25 +245,23 @@ static bool canProveExitOnFirstIteration(Loop *L, DominatorTree &DT,
       MarkLiveEdge(BB, Succ);
   };
 
-  // Check if there is only one value coming from all live predecessor blocks.
-  // Note that because we iterate in RPOT, we have already visited all its
-  // (non-latch) predecessors.
-  auto GetSoleInputOnFirstIteration = [&](PHINode & PN)->Value * {
-    BasicBlock *BB = PN.getParent();
+  // Check if there is only one predecessor on 1st iteration. Note that because
+  // we iterate in RPOT, we have already visited all its (non-latch)
+  // predecessors.
+  auto GetSolePredecessorOnFirstIteration = [&](BasicBlock * BB)->BasicBlock * {
     if (BB == Header)
-      return PN.getIncomingValueForBlock(L->getLoopPredecessor());
-    Value *OnlyInput = nullptr;
+      return L->getLoopPredecessor();
+    BasicBlock *OnlyPred = nullptr;
     for (auto *Pred : predecessors(BB))
-      if (LiveEdges.count({ Pred, BB })) {
-        Value *Incoming = PN.getIncomingValueForBlock(Pred);
-        // Two inputs.
-        if (OnlyInput && OnlyInput != Incoming)
+      if (OnlyPred != Pred && LiveEdges.count({ Pred, BB })) {
+        // 2 live preds.
+        if (OnlyPred)
           return nullptr;
-        OnlyInput = Incoming;
+        OnlyPred = Pred;
       }
 
-    assert(OnlyInput && "No live predecessors?");
-    return OnlyInput;
+    assert(OnlyPred && "No live predecessors?");
+    return OnlyPred;
   };
   DenseMap<Value *, Value *> FirstIterValue;
 
@@ -292,17 +290,18 @@ static bool canProveExitOnFirstIteration(Loop *L, DominatorTree &DT,
       continue;
     }
 
-    // If Phi has only one input from all live input blocks, use it.
-    for (auto &PN : BB->phis()) {
-      if (!PN.getType()->isIntegerTy())
-        continue;
-      auto *Incoming = GetSoleInputOnFirstIteration(PN);
-      if (Incoming && DT.dominates(Incoming, BB->getTerminator())) {
-        Value *FirstIterV =
-            getValueOnFirstIteration(Incoming, FirstIterValue, SQ);
-        FirstIterValue[&PN] = FirstIterV;
+    // If this block has only one live pred, map its phis onto their SCEVs.
+    if (auto *OnlyPred = GetSolePredecessorOnFirstIteration(BB))
+      for (auto &PN : BB->phis()) {
+        if (!PN.getType()->isIntegerTy())
+          continue;
+        auto *Incoming = PN.getIncomingValueForBlock(OnlyPred);
+        if (DT.dominates(Incoming, BB->getTerminator())) {
+          Value *FirstIterV =
+              getValueOnFirstIteration(Incoming, FirstIterValue, SQ);
+          FirstIterValue[&PN] = FirstIterV;
+        }
       }
-    }
 
     using namespace PatternMatch;
     ICmpInst::Predicate Pred;
diff --git a/llvm/test/Transforms/LoopDeletion/eval_first_iteration.ll b/llvm/test/Transforms/LoopDeletion/eval_first_iteration.ll
index 15ebd7d..f2543e2 100644
--- a/llvm/test/Transforms/LoopDeletion/eval_first_iteration.ll
+++ b/llvm/test/Transforms/LoopDeletion/eval_first_iteration.ll
@@ -655,19 +655,20 @@ failure:
   unreachable
 }
 
+; TODO: We can break the backedge here.
 define i32 @test_multiple_pred_2() {
 ; CHECK-LABEL: @test_multiple_pred_2(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
-; CHECK-NEXT:    [[SUM:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ]
+; CHECK-NEXT:    [[SUM:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[SUM_NEXT:%.*]], [[BACKEDGE:%.*]] ]
 ; CHECK-NEXT:    [[SUB:%.*]] = sub i32 4, [[SUM]]
 ; CHECK-NEXT:    [[IS_POSITIVE:%.*]] = icmp sgt i32 [[SUB]], 0
 ; CHECK-NEXT:    br i1 [[IS_POSITIVE]], label [[IF_TRUE:%.*]], label [[IF_FALSE:%.*]]
 ; CHECK:       if.true:
 ; CHECK-NEXT:    br i1 undef, label [[IF_TRUE_1:%.*]], label [[IF_TRUE_2:%.*]]
 ; CHECK:       if.true.1:
-; CHECK-NEXT:    br label [[BACKEDGE:%.*]]
+; CHECK-NEXT:    br label [[BACKEDGE]]
 ; CHECK:       if.true.2:
 ; CHECK-NEXT:    br label [[BACKEDGE]]
 ; CHECK:       if.false:
@@ -678,11 +679,9 @@ define i32 @test_multiple_pred_2() {
 ; CHECK-NEXT:    br label [[BACKEDGE]]
 ; CHECK:       backedge:
 ; CHECK-NEXT:    [[MERGE_PHI:%.*]] = phi i32 [ 0, [[IF_FALSE_1]] ], [ 0, [[IF_FALSE_2]] ], [ [[SUB]], [[IF_TRUE_1]] ], [ [[SUB]], [[IF_TRUE_2]] ]
-; CHECK-NEXT:    [[SUM_NEXT:%.*]] = add i32 [[SUM]], [[MERGE_PHI]]
+; CHECK-NEXT:    [[SUM_NEXT]] = add i32 [[SUM]], [[MERGE_PHI]]
 ; CHECK-NEXT:    [[LOOP_COND:%.*]] = icmp ne i32 [[SUM_NEXT]], 4
-; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[BACKEDGE_LOOP_CRIT_EDGE:%.*]], label [[DONE:%.*]]
-; CHECK:       backedge.loop_crit_edge:
-; CHECK-NEXT:    unreachable
+; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[DONE:%.*]]
 ; CHECK:       done:
 ; CHECK-NEXT:    [[SUM_NEXT_LCSSA:%.*]] = phi i32 [ [[SUM_NEXT]], [[BACKEDGE]] ]
 ; CHECK-NEXT:    ret i32 [[SUM_NEXT_LCSSA]]
-- 
2.7.4