From e5fae2e7c318fb405c693d4c88141eeb221d41d4 Mon Sep 17 00:00:00 2001
From: Bjorn Pettersson <bjorn.a.pettersson@ericsson.com>
Date: Tue, 8 May 2018 06:59:47 +0000
Subject: [PATCH] [LCSSA] Do not remove used PHI nodes in
 formLCSSAForInstructions

Summary:
In formLCSSAForInstructions we speculatively add new PHI
nodes, that sometimes ends up without having any uses. It
has been discovered that sometimes an added PHI node can
appear as being unused in one iteration of the Worklist,
although it can end up being used by a PHI node added in
a later iteration. We now check, a second time, that the
PHI node still is unused before we remove it. This avoids
an assert about "Trying to remove a phi with uses." for the
added test case.

Reviewers: davide, mzolotukhin, mattd, dberlin

Reviewed By: mzolotukhin, dberlin

Subscribers: dberlin, mzolotukhin, davide, bjope, uabelho, llvm-commits

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

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@331741 91177308-0d34-0410-b5e6-96231b3b80d8
---
 lib/Transforms/Utils/LCSSA.cpp       | 15 ++++++----
 test/Transforms/LCSSA/remove-phis.ll | 56 ++++++++++++++++++++++++++++++++++++
 2 files changed, 66 insertions(+), 5 deletions(-)
 create mode 100644 test/Transforms/LCSSA/remove-phis.ll

diff --git a/lib/Transforms/Utils/LCSSA.cpp b/lib/Transforms/Utils/LCSSA.cpp
index 7b0ec6652db..22af1216a4f 100644
--- a/lib/Transforms/Utils/LCSSA.cpp
+++ b/lib/Transforms/Utils/LCSSA.cpp
@@ -226,11 +226,16 @@ bool llvm::formLCSSAForInstructions(SmallVectorImpl<Instruction *> &Worklist,
     insertDebugValuesForPHIs(InstBB, NeedDbgValues);
     Changed = true;
   }
-  // Remove PHI nodes that did not have any uses rewritten.
-  for (PHINode *PN : PHIsToRemove) {
-    assert (PN->use_empty() && "Trying to remove a phi with uses.");
-    PN->eraseFromParent();
-  }
+  // Remove PHI nodes that did not have any uses rewritten. We need to redo the
+  // use_empty() check here, because even if the PHI node wasn't used when added
+  // to PHIsToRemove, later added PHI nodes can be using it.  This cleanup is
+  // not guaranteed to handle trees/cycles of PHI nodes that only are used by
+  // each other. Such situations has only been noticed when the input IR
+  // contains unreachable code, and leaving some extra redundant PHI nodes in
+  // such situations is considered a minor problem.
+  for (PHINode *PN : PHIsToRemove)
+    if (PN->use_empty())
+      PN->eraseFromParent();
   return Changed;
 }
 
diff --git a/test/Transforms/LCSSA/remove-phis.ll b/test/Transforms/LCSSA/remove-phis.ll
new file mode 100644
index 00000000000..587fe7af3b9
--- /dev/null
+++ b/test/Transforms/LCSSA/remove-phis.ll
@@ -0,0 +1,56 @@
+; RUN: opt < %s -lcssa -verify -S -o /dev/null
+
+; This bugpoint reduced test case used to assert when removing unused PHI nodes.
+; Just verify that we do not assert/crash.
+
+define void @test() {
+entry:
+  br label %gazank
+
+gazank:
+  %value = phi i16 [ 0, %entry ], [ undef, %gazonk ]
+  br i1 undef, label %gazink, label %qqq
+
+gazink:
+  br i1 undef, label %gazonk, label %infinite.loop.pred
+
+gazonk:
+  br i1 undef, label %exit1, label %gazank
+
+qqq:
+  br i1 undef, label %www, label %exit2
+
+www:
+  br i1 undef, label %qqq, label %foo.pred
+
+foo.pred:
+  br label %foo
+
+foo:
+  br i1 undef, label %bar, label %exit1.pred
+
+bar:
+  br i1 undef, label %foo, label %exit2.pred
+
+unreachable1:
+  br i1 undef, label %foo, label %exit2.pred
+
+exit1.pred:
+  br label %exit1
+
+exit1:
+  ret void
+
+exit2.pred:
+  br label %exit2
+
+exit2:
+  ret void
+
+infinite.loop.pred:
+  br label %infinite.loop
+
+infinite.loop:
+  %dead = phi i16 [ %value, %infinite.loop.pred ], [ 0, %infinite.loop ]
+  br label %infinite.loop
+}
-- 
2.11.0