[NewGVN] Don't ignore poison in cyclic PHIs

[ManuelJBrito]

Summary

NewGVN gets stuck in a infinite loop for the following test case.

define void @foo() {
  br label %1

1: 
  %2 = phi i32 [ %3, %1 ], [ undef, %0 ]
  %3 = lshr i32 %2, 973496514
  br label %1

With the following steps:

%2 -> undef (edge <%1, %1> is initially unreachable)
%3 -> 0 ; start of evaluation loop
%2 -> phi [0, undef]
%3 -> poison
%2 -> phi [poison, undef] -> undef 
%3 -> 0
; repeat

The problem here is that poison and undef simplify differently and we have a cyclic dependency, so the value numbering never converges.
Not ignoring the poison breaks the cycle.

[nlopes]

llvm/test/Transforms/NewGVN/cycle_poison.ll

8

this could be folded to just undef.

16

can the test case have a terminating loop pls?
non-terminating loops are evil for verification and semantics-wise.

llvm/lib/Transforms/Scalar/NewGVN.cpp

auto Filtered = make_filter_range(E->operands(), [&](Value *Arg) {
     if (isa<UndefValue>(Arg)) {
       HasUndef = true;
       return false;
     }
     return true;
   });
   // If we are left with no operands, it's dead.
   if (Filtered.empty()) {
-    // If it has undef or poison at this point, it means there are no-non-undef
-    // arguments, and thus, the value of the phi node must be undef.
     if (HasUndef) {
+      // If we have undef and poison, we need to know if it's cycle
+      // free to ignore the poison. Otherwise we might get stuck in a evaluation
+      // loop.
+      if (HasBackedge && !OriginalOpsConstant && HasPoison && !isCycleFree(I))
+        return E;
+      // If it has undef or poison at this point, it means there are
+      // no-non-undef arguments, and thus, the value of the phi node must be
+      // undef.
       LLVM_DEBUG(
           dbgs() << "PHI Node " << *I
                  << " has no non-undef arguments, valuing it as undef\n");
       return createConstantExpression(UndefValue::get(I->getType()));
     }
     if (HasPoison) {
       LLVM_DEBUG(
           dbgs() << "PHI Node " << *I

llvm/test/Transforms/NewGVN/cycle_poison.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -passes=newgvn -S %s | FileCheck %s
+
+define void @foo() {
+; CHECK-LABEL: @foo(
+; CHECK-NEXT:    br label [[TMP1:%.*]]
+; CHECK:       1:
+; CHECK-NEXT:    [[TMP2:%.*]] = phi i32 [ poison, [[TMP1]] ], [ undef, [[TMP0:%.*]] ]
+; CHECK-NEXT:    br label [[TMP1]]
+;
+  br label %1
+
+1:                                                ; preds = %1, %0
+  %2 = phi i32 [ %3, %1 ], [ undef, %0 ]
+  %3 = lshr i32 %2, 973496514
+  br label %1
+}