[NewGVN] do phi(undef, x) -> x only if x is not poison

[nlopes]

Summary

phi([undef, A], [x, B]) -> x is only correct x is guaranteed to be a non-poison value. Otherwise we would be changing an undef to poison in the branch A.

This patch fixes this bug in NewGVN.

[asbirlea]

Thank you!

[nikic]

It looks like the current behavior matches what GVN does: https://llvm.godbolt.org/z/eTYzMjKf7

If an issue affects both GVN and NewGVN, please always fix it in GVN first. Otherwise the fix will remain untested, and this seems like a situation where it can cause a real regression in optimization quality (because we still treat uninit loads as undef, not poison).

[nlopes]

In D117907#3271648, @nikic wrote:

It looks like the current behavior matches what GVN does: https://llvm.godbolt.org/z/eTYzMjKf7

If an issue affects both GVN and NewGVN, please always fix it in GVN first. Otherwise the fix will remain untested, and this seems like a situation where it can cause a real regression in optimization quality (because we still treat uninit loads as undef, not poison).

The bug is not in GVN itself, it's in InstSimplify (which is called by GVNPass::processInstruction).
I do have a patch for InstSimplify as well, but given the potential to regress performance, I would rather delay that until after the LLVM 14 branch.

[nlopes]

In D117907#3271869, @nlopes wrote:

In D117907#3271648, @nikic wrote:

It looks like the current behavior matches what GVN does: https://llvm.godbolt.org/z/eTYzMjKf7

If an issue affects both GVN and NewGVN, please always fix it in GVN first. Otherwise the fix will remain untested, and this seems like a situation where it can cause a real regression in optimization quality (because we still treat uninit loads as undef, not poison).

The bug is not in GVN itself, it's in InstSimplify (which is called by GVNPass::processInstruction).
I do have a patch for InstSimplify as well, but given the potential to regress performance, I would rather delay that until after the LLVM 14 branch.

@nikic do you agree with this plan (commit this patch now and fix InstSimplify after 14 branches in a few weeks)?

llvm/lib/Transforms/Scalar/NewGVN.cpp

 #include "llvm/Analysis/AssumptionCache.h"
 #include "llvm/Analysis/CFGPrinter.h"
 #include "llvm/Analysis/ConstantFolding.h"
 #include "llvm/Analysis/GlobalsModRef.h"
 #include "llvm/Analysis/InstructionSimplify.h"
 #include "llvm/Analysis/MemoryBuiltins.h"
 #include "llvm/Analysis/MemorySSA.h"
 #include "llvm/Analysis/TargetLibraryInfo.h"
+#include "llvm/Analysis/ValueTracking.h"
 #include "llvm/IR/Argument.h"
 #include "llvm/IR/BasicBlock.h"
 #include "llvm/IR/Constant.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/InstrTypes.h"
 #include "llvm/IR/Instruction.h"
if (isa<UndefValue>(Arg)) {
       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 (HasPoison && !HasUndef) {
-      LLVM_DEBUG(
-          dbgs() << "PHI Node " << *I
-                 << " has no non-poison arguments, valuing it as poison\n");
-      return createConstantExpression(PoisonValue::get(I->getType()));
-    }
     if (HasUndef) {
       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
+                 << " has no non-poison arguments, valuing it as poison\n");
+      return createConstantExpression(PoisonValue::get(I->getType()));
+    }
 
     LLVM_DEBUG(dbgs() << "No arguments of PHI node " << *I << " are live\n");
     deleteExpression(E);
     return createDeadExpression();
   }
   Value *AllSameValue = *(Filtered.begin());
   ++Filtered.begin();
   // Can't use std::equal here, sadly, because filter.begin moves.
   if (llvm::all_of(Filtered, [&](Value *Arg) { return Arg == AllSameValue; })) {
+    // Can't fold phi(undef, X) -> X unless X can't be poison (thus X is undef
+    // in the worst case).
+    if (HasUndef && !isGuaranteedNotToBePoison(AllSameValue, AC, nullptr, DT))
+      return E;
+
     // In LLVM's non-standard representation of phi nodes, it's possible to have
     // phi nodes with cycles (IE dependent on other phis that are .... dependent
     // on the original phi node), especially in weird CFG's where some arguments
     // are unreachable, or uninitialized along certain paths.  This can cause
     // infinite loops during evaluation. We work around this by not trying to
     // really evaluate them independently, but instead using a variable
     // expression to say if one is equivalent to the other.
-    // We also special case undef, so that if we have an undef, we can't use the
-    // common value unless it dominates the phi block.
+    // We also special case undef/poison, so that if we have an undef, we can't
+    // use the common value unless it dominates the phi block.
     if (HasPoison || HasUndef) {
       // If we have undef and at least one other value, this is really a
       // multivalued phi, and we need to know if it's cycle free in order to
       // evaluate whether we can ignore the undef.  The other parts of this are
       // just shortcuts.  If there is no backedge, or all operands are
       // constants, it also must be cycle free.
       if (HasBackedge && !OriginalOpsConstant &&
           !isa<UndefValue>(AllSameValue) && !isCycleFree(I))
NewGVN::makePossiblePHIOfOps(Instruction *I,
   RevisitOnReachabilityChange[PHIBlock].set(InstrToDFSNum(I));
   LLVM_DEBUG(dbgs() << "Created phi of ops " << *ValuePHI << " for " << *I
                     << "\n");
 
   return E;
 }
 
 // The algorithm initially places the values of the routine in the TOP
-// congruence class. The leader of TOP is the undetermined value `undef`.
+// congruence class. The leader of TOP is the undetermined value `poison`.
 // When the algorithm has finished, values still in TOP are unreachable.
 void NewGVN::initializeCongruenceClasses(Function &F) {
   NextCongruenceNum = 0;
 
   // Note that even though we use the live on entry def as a representative
   // MemoryAccess, it is *not* the same as the actual live on entry def. We
-  // have no real equivalemnt to undef for MemoryAccesses, and so we really
+  // have no real equivalent to poison for MemoryAccesses, and so we really
   // should be checking whether the MemoryAccess is top if we want to know if it
   // is equivalent to everything.  Otherwise, what this really signifies is that
   // the access "it reaches all the way back to the beginning of the function"
 
   // Initialize all other instructions to be in TOP class.
   TOPClass = createCongruenceClass(nullptr, nullptr);
   TOPClass->setMemoryLeader(MSSA->getLiveOnEntryDef());
   //  The live on entry def gets put into it's own class
void NewGVN::valueNumberMemoryPhi(MemoryPhi *MP) {
   // TODO: We could do cycle-checking on the memory phis to allow valueizing for
   // self-phi checking.
   const BasicBlock *PHIBlock = MP->getBlock();
   auto Filtered = make_filter_range(MP->operands(), [&](const Use &U) {
     return cast<MemoryAccess>(U) != MP &&
            !isMemoryAccessTOP(cast<MemoryAccess>(U)) &&
            ReachableEdges.count({MP->getIncomingBlock(U), PHIBlock});
   });
-  // If all that is left is nothing, our memoryphi is undef. We keep it as
+  // If all that is left is nothing, our memoryphi is poison. We keep it as
   // InitialClass.  Note: The only case this should happen is if we have at
   // least one self-argument.
   if (Filtered.begin() == Filtered.end()) {
     if (setMemoryClass(MP, TOPClass))
       markMemoryUsersTouched(MP);
     return;
   }
 

llvm/test/Transforms/NewGVN/completeness.ll

 
 ;; Ensure that when reachability affects a phi of ops, we recompute
 ;; it.  Here, the phi node is marked for recomputation when bb7->bb3
 ;; becomes live, but the value does not change. if we do not directly
 ;; recompute the phi of ops instruction (tmp5), the value number will
 ;; change in the verifier, as it goes from a constant value to a
 ;; phi of [true, false]
 
-define void @test12() {
+define void @test12(i32* %p) {
 ; CHECK-LABEL: @test12(
 ; CHECK-NEXT:  bb:
-; CHECK-NEXT:    [[TMP:%.*]] = load i32, i32* null
+; CHECK-NEXT:    [[TMP:%.*]] = load i32, i32* %p
 ; CHECK-NEXT:    [[TMP1:%.*]] = icmp sgt i32 [[TMP]], 0
 ; CHECK-NEXT:    br i1 [[TMP1]], label [[BB2:%.*]], label [[BB8:%.*]]
 ; CHECK:       bb2:
 ; CHECK-NEXT:    br label [[BB3:%.*]]
 ; CHECK:       bb3:
-; CHECK-NEXT:    [[PHIOFOPS:%.*]] = phi i1 [ true, [[BB2]] ], [ false, [[BB7:%.*]] ]
-; CHECK-NEXT:    br i1 [[PHIOFOPS]], label [[BB6:%.*]], label [[BB7]]
+; CHECK-NEXT:    br i1 true, label [[BB6:%.*]], label [[BB7]]
 ; CHECK:       bb6:
 ; CHECK-NEXT:    br label [[BB7]]
 ; CHECK:       bb7:
 ; CHECK-NEXT:    br label [[BB3]]
 ; CHECK:       bb8:
 ; CHECK-NEXT:    ret void
 ;
 bb:
-  %tmp = load i32, i32* null
+  %tmp = load i32, i32* %p
   %tmp1 = icmp sgt i32 %tmp, 0
   br i1 %tmp1, label %bb2, label %bb8
 
 bb2:                                              ; preds = %bb
   br label %bb3
 
 bb3:                                              ; preds = %bb7, %bb2
-  %tmp4 = phi i32 [ %tmp, %bb2 ], [ undef, %bb7 ]
+  %tmp4 = phi i32 [ %tmp, %bb2 ], [ poison, %bb7 ]
   %tmp5 = icmp sgt i32 %tmp4, 0
   br i1 %tmp5, label %bb6, label %bb7
 
 bb6:                                              ; preds = %bb3
   br label %bb7
 
 bb7:                                              ; preds = %bb6, %bb3
   br label %bb3

llvm/test/Transforms/NewGVN/phi-edge-handling.ll

 define i8 @value_undef(i1 %cond, i8 %v) {
 ; CHECK-LABEL: @value_undef(
 ; CHECK-NEXT:    br i1 [[COND:%.*]], label [[A:%.*]], label [[B:%.*]]
 ; CHECK:       A:
 ; CHECK-NEXT:    br label [[EXIT:%.*]]
 ; CHECK:       B:
 ; CHECK-NEXT:    br label [[EXIT]]
 ; CHECK:       EXIT:
+; CHECK-NEXT:    [[R:%.*]] = phi i8 [ undef, [[A]] ], [ [[V:%.*]], [[B]] ]
+; CHECK-NEXT:    ret i8 [[R]]
+;
+  br i1 %cond, label %A, label %B
+A:
+  br label %EXIT
+B:
+  br label %EXIT
+EXIT:
+  %r = phi i8 [undef, %A], [%v, %B]
+  ret i8 %r
+}
+
+define i8 @value_undef_noundef(i1 %cond, i8 noundef %v) {
+; CHECK-LABEL: @value_undef_noundef(
+; CHECK-NEXT:    br i1 [[COND:%.*]], label [[A:%.*]], label [[B:%.*]]
+; CHECK:       A:
+; CHECK-NEXT:    br label [[EXIT:%.*]]
+; CHECK:       B:
+; CHECK-NEXT:    br label [[EXIT]]
+; CHECK:       EXIT:
 ; CHECK-NEXT:    ret i8 [[V:%.*]]
 ;
   br i1 %cond, label %A, label %B
 A:
   br label %EXIT
 B:
   br label %EXIT
 EXIT:

llvm/test/Transforms/NewGVN/pr31682.ll

 ; CHECK-NEXT:    br label [[BB10]]
 ;
 bb:
   %tmp = load %struct.foo*, %struct.foo** @global
   %tmp1 = getelementptr %struct.foo, %struct.foo* %tmp
   br label %bb2
 
 bb2:                                              ; preds = %bb2, %bb
-  %tmp3 = phi %struct.foo* [ undef, %bb ], [ %tmp6, %bb2 ]
+  %tmp3 = phi %struct.foo* [ poison, %bb ], [ %tmp6, %bb2 ]
   %tmp4 = getelementptr %struct.foo, %struct.foo* %tmp3, i64 0, i32 1
   %tmp5 = load i32, i32* %tmp4
   %tmp6 = load %struct.foo*, %struct.foo** @global
   br i1 undef, label %bb2, label %bb7
 
 bb7:                                              ; preds = %bb2
   %tmp8 = phi %struct.foo* [ %tmp6, %bb2 ]
   %tmp9 = getelementptr %struct.foo, %struct.foo* %tmp8, i64 0, i32 1
   br label %bb10
 
 bb10:                                             ; preds = %bb10, %bb7
   %tmp11 = load i32, i32* %tmp9
   br label %bb10
 }

llvm/test/Transforms/NewGVN/pr32403.ll

 for.body8.i:                                      ; preds = %for.inc24.i, %if.then13
   %nIdx.052.i = phi i32 [ %inc.i, %if.then13 ], [ %nIdx.1.i, %for.inc24.i ]
   br i1 undef, label %for.inc24.i, label %if.then17.i
 
 if.then17.i:                                      ; preds = %for.body8.i
   br label %for.inc24.i
 
 for.inc24.i:                                      ; preds = %if.then17.i, %for.body8.i
-  %nIdx.1.i = phi i32 [ undef, %if.then17.i ], [ %nIdx.052.i, %for.body8.i ]
+  %nIdx.1.i = phi i32 [ poison, %if.then17.i ], [ %nIdx.052.i, %for.body8.i ]
   br label %for.body8.i
 
 if.else58:                                        ; preds = %for.body
   %inc.i51 = add nsw i32 %refIdxLX.0, 1
   br label %for.body
 
 for.end:                                          ; preds = %entry
   ret void
 }
 
 
 

llvm/test/Transforms/NewGVN/pr32838.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ;RUN: opt -passes=newgvn -S < %s | FileCheck %s
 target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
 target triple = "x86_64-apple-macosx10.12.0"
 ;; Ensure we don't infinite loop when all phi arguments are really unreachable or self-defined
-define void @fn1(i64 %arg) {
+define void @fn1(i64 noundef %arg) {
 ; CHECK-LABEL: @fn1(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br i1 undef, label [[IF_THEN:%.*]], label [[COND_TRUE:%.*]]
 ; CHECK:       if.then:
 ; CHECK-NEXT:    br i1 false, label [[FIRSTPHIBLOCK:%.*]], label [[TEMP:%.*]]
 ; CHECK:       firstphiblock:
 ; CHECK-NEXT:    br i1 undef, label %for.cond17thread-pre-split, label [[SECONDPHIBLOCK:%.*]]
 ; CHECK:       secondphiblock:
for.cond17thread-pre-split:
   br label %cond.true
 cond.true:
   %fourthphi = phi i64 [ %arg, %entry ], [ %firstphi, %for.cond17thread-pre-split ]
   %div = sdiv i64 %fourthphi, 4
   br label %thirdphiblock
 temp:
   ret void
 }
-define void @fn2(i64 %arg) {
+define void @fn2(i64 noundef %arg) {
 ; CHECK-LABEL: @fn2(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br i1 undef, label [[IF_THEN:%.*]], label [[COND_TRUE:%.*]]
 ; CHECK:       if.then:
 ; CHECK-NEXT:    br i1 false, label [[FIRSTPHIBLOCK:%.*]], label [[TEMP:%.*]]
 ; CHECK:       firstphiblock:
 ; CHECK-NEXT:    [[FIRSTPHI:%.*]] = phi i64 [ poison, [[IF_THEN]] ], [ [[SECONDPHI:%.*]], [[SECONDPHIBLOCK:%.*]] ]
 ; CHECK-NEXT:    br i1 undef, label %for.cond17thread-pre-split, label [[SECONDPHIBLOCK]]

llvm/test/Transforms/NewGVN/pr34135.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -passes=newgvn -enable-phi-of-ops=true -S | FileCheck %s
 ;; Make sure we don't incorrectly use predicateinfo to simplify phi of ops cases
 source_filename = "pr34135.ll"
 
-define void @snork(i32 %arg) {
+define void @snork(i32 noundef %arg) {
 ; CHECK-LABEL: @snork(
 ; CHECK-NEXT:  bb:
 ; CHECK-NEXT:    [[TMP:%.*]] = sext i32 [[ARG:%.*]] to i64
 ; CHECK-NEXT:    br label [[BB1:%.*]]
 ; CHECK:       bb1:
 ; CHECK-NEXT:    [[TMP2:%.*]] = phi i64 [ 0, [[BB:%.*]] ], [ [[TMP3:%.*]], [[BB1]] ]
 ; CHECK-NEXT:    [[TMP3]] = add i64 [[TMP2]], 1
 ; CHECK-NEXT:    [[TMP4:%.*]] = icmp slt i64 [[TMP3]], [[TMP]]