[SimplifyCFG] avoid illegal phi with both poison and undef

[spatel]

Summary

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 ]

I think we could soften the poison to undef, but it seems unlikely that this would matter in any real code.

[lebedev.ri]

llvm/test/Transforms/SimplifyCFG/poison-merge.ll

15–18

It looks like we didn't merge them after all?

[aqjune]

What about updating redirectValuesFromPredecessorsToPhi to lower conflicting poison to undef?
We can maintain two sets of incoming BBs, say BBundef and BBpoison that have poison incoming values and undef incoming values.
At the end of redirectValuesFromPredecessorsToPhi, if BBundef and BBpoison overlaps, there are operands that need to be updated.
It will keep the transformation enabled.

[spatel]

llvm/test/Transforms/SimplifyCFG/poison-merge.ll

15–18

That's correct - let me add some tests of the other value combos to make it clearer what this patch does.

[lebedev.ri]

I'm fine with having this as a quickfix, but i think we shouldn't pessimize such case in general, but actually properly handle it.

[spatel]

Patch updated:
No code change, but added negative (for this patch) tests to show that the transform still fires in the expected (existing) combinations.

[spatel]

In D97495#2589631, @aqjune wrote:

What about updating redirectValuesFromPredecessorsToPhi to lower conflicting poison to undef?
We can maintain two sets of incoming BBs, say BBundef and BBpoison that have poison incoming values and undef incoming values.
At the end of redirectValuesFromPredecessorsToPhi, if BBundef and BBpoison overlaps, there are operands that need to be updated.
It will keep the transformation enabled.

Yes, we can do better on this, but I suspect it's rare to encounter both poison and undef (and gets more rare as we eliminate more and more undef from IR?).

[aqjune]

In D97495#2590004, @spatel wrote:

In D97495#2589631, @aqjune wrote:

What about updating redirectValuesFromPredecessorsToPhi to lower conflicting poison to undef?
We can maintain two sets of incoming BBs, say BBundef and BBpoison that have poison incoming values and undef incoming values.
At the end of redirectValuesFromPredecessorsToPhi, if BBundef and BBpoison overlaps, there are operands that need to be updated.
It will keep the transformation enabled.

Yes, we can do better on this, but I suspect it's rare to encounter both poison and undef (and gets more rare as we eliminate more and more undef from IR?).

I think it won't be very rare ATM because there are quite a few places that create poison constants.

Maybe we can create a new function that 'sanitizes' operands in PHI: it checks whether a PHI has multiple incoming edges with different undef/poison constants, and if there's any, replace such poison constants with undefs.

p = phi [ undef, BB ], [ poison, BB ]
  -> PHINode::sanitize (or something like this, I guess this isn't the best name)
p = phi [ undef,  BB ], [ undef, BB ]

If a new bug that's similar to this issue is reported, we can simply add a call to this function and it will fix the bug.

[spatel]

Patch updated:
We have a dedicated function for replacing undef incoming values, so I enhanced that to account for poison mismatches.
This gives us the expected, optimized result in all of the test examples.

[aqjune]

LGTM
The fix is conservative, but I think it is okay. I believe this will be helpful in addressing (imaginary) hidden crashes by making undef/poison operands homogeneous.

[lebedev.ri]

Looks ok to me, thanks.

llvm/lib/Transforms/Utils/Local.cpp

 
 /// Replace the incoming undef values to a phi with the values
 /// from a block-to-value map.
 ///
 /// \param PN The phi we are replacing the undefs in.
 /// \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);
 
     if (!isa<UndefValue>(V)) continue;
 
     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
 /// potentially multiple instances of that value flowing from the
 /// block's predecessors to the phi.
 ///
 /// \param BB The block with the value flowing into the phi.
 /// \param BBPreds The predecessors of BB.

llvm/test/Transforms/SimplifyCFG/poison-merge.ll

+; 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
+}