[Reassociate] Prevent infinite loops when processing PHIs.

Phi nodes can reside in live blocks but one of their incoming
arguments can come from a dead block. Dead blocks and reassociate
don't play nice together. In fact, reassociate performs an RPO
as a first step to avoid processing dead blocks.

The reason why Reassociate might not fixpoint when examining
dead blocks is that the following:

  %xor0 = xor i16 %xor1, undef
  %xor1 = xor i16 %xor0, undef

is perfectly valid LLVM IR (if it appears in a dead block),
so the worklist algorithm keeps pushing the two instructions for
reexamination. Note that this is not Reassociate fault, at least
not entirely. It's llvm that has a weird definition of dominance.

Fixes PR37390.

llvm-svn: 332100

1 files changed, 28 insertions, 0 deletions

diff --git a/llvm/test/Transforms/Reassociate/infloop-deadphi.ll b/llvm/test/Transforms/Reassociate/infloop-deadphi.ll
new file mode 100644
index 00000000000..c5a45a4f7eb
--- /dev/null
+++ b/llvm/test/Transforms/Reassociate/infloop-deadphi.ll
@@ -0,0 +1,28 @@
+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -reassociate %s -S | FileCheck %s
+
+target triple = "x86_64-unknown-linux-gnu"
+
+define void @f() {
+; CHECK-LABEL: @f(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[DONE:%.*]]
+; CHECK:       dead:
+; CHECK-NEXT:    [[XOR0:%.*]] = xor i16 [[XOR1:%.*]], undef
+; CHECK-NEXT:    [[XOR1]] = xor i16 [[XOR0]], undef
+; CHECK-NEXT:    br i1 undef, label [[DEAD:%.*]], label [[DONE]]
+; CHECK:       done:
+; CHECK-NEXT:    ret void
+;
+entry:
+  br label %done
+
+dead:
+  %xor0 = xor i16 %xor1, undef
+  %xor1 = xor i16 %xor0, undef
+  br i1 undef, label %dead, label %done
+
+done:
+  %e = phi i16 [ %xor1, %dead ], [ 0, %entry ]
+  ret void
+}