[SimplifyCFG] avoid illegal phi with both poison and undef

In the example based on:
https://llvm.org/PR49218
...we are crashing because poison is a subclass of undef, so we merge blocks and create:

PHI node has multiple entries for the same basic block with different incoming values!
  %k3 = phi i64 [ poison, %entry ], [ %k3, %g ], [ undef, %entry ]

If both poison and undef values are incoming, we soften the poison values to undef.

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

(cherry picked from commit 356cdabd3a9e0ff919ea2c1a35c8706ecb915297)

2 files changed, 223 insertions, 1 deletions

diff --git a/llvm/lib/Transforms/Utils/Local.cpp b/llvm/lib/Transforms/Utils/Local.cpp
index d055f3d..ae26058 100644
--- a/llvm/lib/Transforms/Utils/Local.cpp
+++ b/llvm/lib/Transforms/Utils/Local.cpp
@@ -918,6 +918,7 @@ static void gatherIncomingValuesToPhi(PHINode *PN,
 /// \param IncomingValues A map from block to value.
 static void replaceUndefValuesInPhi(PHINode *PN,
                                     const IncomingValueMap &IncomingValues) {
+  SmallVector<unsigned> TrueUndefOps;
   for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
     Value *V = PN->getIncomingValue(i);
 
@@ -925,10 +926,31 @@ static void replaceUndefValuesInPhi(PHINode *PN,
 
     BasicBlock *BB = PN->getIncomingBlock(i);
     IncomingValueMap::const_iterator It = IncomingValues.find(BB);
-    if (It == IncomingValues.end()) continue;
 
+    // Keep track of undef/poison incoming values. Those must match, so we fix
+    // them up below if needed.
+    // Note: this is conservatively correct, but we could try harder and group
+    // the undef values per incoming basic block.
+    if (It == IncomingValues.end()) {
+      TrueUndefOps.push_back(i);
+      continue;
+    }
+
+    // There is a defined value for this incoming block, so map this undef
+    // incoming value to the defined value.
     PN->setIncomingValue(i, It->second);
   }
+
+  // If there are both undef and poison values incoming, then convert those
+  // values to undef. It is invalid to have different values for the same
+  // incoming block.
+  unsigned PoisonCount = count_if(TrueUndefOps, [&](unsigned i) {
+    return isa<PoisonValue>(PN->getIncomingValue(i));
+  });
+  if (PoisonCount != 0 && PoisonCount != TrueUndefOps.size()) {
+    for (unsigned i : TrueUndefOps)
+      PN->setIncomingValue(i, UndefValue::get(PN->getType()));
+  }
 }
 
 /// Replace a value flowing from a block to a phi with
diff --git a/llvm/test/Transforms/SimplifyCFG/poison-merge.ll b/llvm/test/Transforms/SimplifyCFG/poison-merge.ll
new file mode 100644
index 0000000..93d9b0b
--- /dev/null
+++ b/llvm/test/Transforms/SimplifyCFG/poison-merge.ll
@@ -0,0 +1,200 @@
+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -S -simplifycfg -simplifycfg-require-and-preserve-domtree=1 -keep-loops=0 < %s | FileCheck %s
+
+; Merge 2 undefined incoming values.
+
+define i32 @undef_merge(i32 %x) {
+; CHECK-LABEL: @undef_merge(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    switch i32 [[X:%.*]], label [[EXIT:%.*]] [
+; CHECK-NEXT:    i32 4, label [[G:%.*]]
+; CHECK-NEXT:    i32 12, label [[G]]
+; CHECK-NEXT:    ]
+; CHECK:       g:
+; CHECK-NEXT:    [[K3:%.*]] = phi i64 [ undef, [[ENTRY:%.*]] ], [ [[K3]], [[G]] ], [ undef, [[ENTRY]] ]
+; CHECK-NEXT:    br label [[G]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret i32 undef
+;
+entry:
+  switch i32 %x, label %exit [
+  i32 4, label %loop
+  i32 12, label %g
+  ]
+
+loop:
+  %k2 = phi i64 [ %k3, %g ], [ undef, %entry ]
+  br label %g
+
+g:
+  %k3 = phi i64 [ %k2, %loop ], [ undef, %entry ]
+  br label %loop
+
+exit:
+  ret i32 undef
+}
+
+; Merge 2 poison incoming values.
+
+define i32 @poison_merge(i32 %x) {
+; CHECK-LABEL: @poison_merge(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    switch i32 [[X:%.*]], label [[EXIT:%.*]] [
+; CHECK-NEXT:    i32 4, label [[G:%.*]]
+; CHECK-NEXT:    i32 12, label [[G]]
+; CHECK-NEXT:    ]
+; CHECK:       g:
+; CHECK-NEXT:    [[K3:%.*]] = phi i64 [ poison, [[ENTRY:%.*]] ], [ [[K3]], [[G]] ], [ poison, [[ENTRY]] ]
+; CHECK-NEXT:    br label [[G]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret i32 undef
+;
+entry:
+  switch i32 %x, label %exit [
+  i32 4, label %loop
+  i32 12, label %g
+  ]
+
+loop:
+  %k2 = phi i64 [ %k3, %g ], [ poison, %entry ]
+  br label %g
+
+g:
+  %k3 = phi i64 [ %k2, %loop ], [ poison, %entry ]
+  br label %loop
+
+exit:
+  ret i32 undef
+}
+
+; Merge equal defined incoming values.
+
+define i32 @defined_merge(i32 %x) {
+; CHECK-LABEL: @defined_merge(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    switch i32 [[X:%.*]], label [[EXIT:%.*]] [
+; CHECK-NEXT:    i32 4, label [[G:%.*]]
+; CHECK-NEXT:    i32 12, label [[G]]
+; CHECK-NEXT:    ]
+; CHECK:       g:
+; CHECK-NEXT:    [[K3:%.*]] = phi i64 [ 42, [[ENTRY:%.*]] ], [ [[K3]], [[G]] ], [ 42, [[ENTRY]] ]
+; CHECK-NEXT:    br label [[G]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret i32 undef
+;
+entry:
+  switch i32 %x, label %exit [
+  i32 4, label %loop
+  i32 12, label %g
+  ]
+
+loop:
+  %k2 = phi i64 [ %k3, %g ], [ 42, %entry ]
+  br label %g
+
+g:
+  %k3 = phi i64 [ %k2, %loop ], [ 42, %entry ]
+  br label %loop
+
+exit:
+  ret i32 undef
+}
+
+; Merge defined and undef incoming values.
+
+define i32 @defined_and_undef_merge(i32 %x) {
+; CHECK-LABEL: @defined_and_undef_merge(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    switch i32 [[X:%.*]], label [[EXIT:%.*]] [
+; CHECK-NEXT:    i32 4, label [[G:%.*]]
+; CHECK-NEXT:    i32 12, label [[G]]
+; CHECK-NEXT:    ]
+; CHECK:       g:
+; CHECK-NEXT:    [[K3:%.*]] = phi i64 [ 42, [[ENTRY:%.*]] ], [ [[K3]], [[G]] ], [ 42, [[ENTRY]] ]
+; CHECK-NEXT:    br label [[G]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret i32 undef
+;
+entry:
+  switch i32 %x, label %exit [
+  i32 4, label %loop
+  i32 12, label %g
+  ]
+
+loop:
+  %k2 = phi i64 [ %k3, %g ], [ undef, %entry ]
+  br label %g
+
+g:
+  %k3 = phi i64 [ %k2, %loop ], [ 42, %entry ]
+  br label %loop
+
+exit:
+  ret i32 undef
+}
+
+; Merge defined and poison incoming values.
+
+define i32 @defined_and_poison_merge(i32 %x) {
+; CHECK-LABEL: @defined_and_poison_merge(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    switch i32 [[X:%.*]], label [[EXIT:%.*]] [
+; CHECK-NEXT:    i32 4, label [[G:%.*]]
+; CHECK-NEXT:    i32 12, label [[G]]
+; CHECK-NEXT:    ]
+; CHECK:       g:
+; CHECK-NEXT:    [[K3:%.*]] = phi i64 [ 42, [[ENTRY:%.*]] ], [ [[K3]], [[G]] ], [ 42, [[ENTRY]] ]
+; CHECK-NEXT:    br label [[G]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret i32 undef
+;
+entry:
+  switch i32 %x, label %exit [
+  i32 4, label %loop
+  i32 12, label %g
+  ]
+
+loop:
+  %k2 = phi i64 [ %k3, %g ], [ poison, %entry ]
+  br label %g
+
+g:
+  %k3 = phi i64 [ %k2, %loop ], [ 42, %entry ]
+  br label %loop
+
+exit:
+  ret i32 undef
+}
+
+; Do not crash trying to merge poison and undef into a single phi.
+
+define i32 @PR49218(i32 %x) {
+; CHECK-LABEL: @PR49218(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    switch i32 [[X:%.*]], label [[EXIT:%.*]] [
+; CHECK-NEXT:    i32 4, label [[G:%.*]]
+; CHECK-NEXT:    i32 12, label [[G]]
+; CHECK-NEXT:    ]
+; CHECK:       g:
+; CHECK-NEXT:    [[K3:%.*]] = phi i64 [ undef, [[ENTRY:%.*]] ], [ [[K3]], [[G]] ], [ undef, [[ENTRY]] ]
+; CHECK-NEXT:    br label [[G]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret i32 undef
+;
+entry:
+  switch i32 %x, label %exit [
+  i32 4, label %loop
+  i32 12, label %g
+  ]
+
+loop:
+  %k2 = phi i64 [ %k3, %g ], [ undef, %entry ]
+  br label %g
+
+g:
+  %k3 = phi i64 [ %k2, %loop ], [ poison, %entry ]
+  br label %loop
+
+exit:
+  ret i32 undef
+}