[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

14–17

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

14–17

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

void llvm::MergeBasicBlockIntoOnlyPred(BasicBlock *DestBB,
 
   else {
     PredBB->eraseFromParent(); // Nuke BB if DTU is nullptr.
   }
 }
 
 /// Return true if we can choose one of these values to use in place of the
 /// other. Note that we will always choose the non-undef value to keep.
-static bool CanMergeValues(Value *First, Value *Second) {
-  return First == Second || isa<UndefValue>(First) || isa<UndefValue>(Second);
+/// The XOR logic prevents merging poison with undef. We can merge either of
+/// those into a defined value, but not into each other.
+static bool canMergeValues(Value *First, Value *Second) {
+  return First == Second || (isa<UndefValue>(First) ^ isa<UndefValue>(Second));
 }
 
 /// Return true if we can fold BB, an almost-empty BB ending in an unconditional
 /// branch to Succ, into Succ.
 ///
 /// Assumption: Succ is the single successor for BB.
 static bool CanPropagatePredecessorsForPHIs(BasicBlock *BB, BasicBlock *Succ) {
   assert(*succ_begin(BB) == Succ && "Succ is not successor of BB!");
for (BasicBlock::iterator I = Succ->begin(); isa<PHINode>(I); ++I) {
     // If the incoming value from BB is again a PHINode in
     // BB which has the same incoming value for *PI as PN does, we can
     // merge the phi nodes and then the blocks can still be merged
     PHINode *BBPN = dyn_cast<PHINode>(PN->getIncomingValueForBlock(BB));
     if (BBPN && BBPN->getParent() == BB) {
       for (unsigned PI = 0, PE = PN->getNumIncomingValues(); PI != PE; ++PI) {
         BasicBlock *IBB = PN->getIncomingBlock(PI);
         if (BBPreds.count(IBB) &&
-            !CanMergeValues(BBPN->getIncomingValueForBlock(IBB),
+            !canMergeValues(BBPN->getIncomingValueForBlock(IBB),
                             PN->getIncomingValue(PI))) {
           LLVM_DEBUG(dbgs()
                      << "Can't fold, phi node " << PN->getName() << " in "
                      << Succ->getName() << " is conflicting with "
                      << BBPN->getName() << " with regard to common predecessor "
                      << IBB->getName() << "\n");
           return false;
         }
       }
     } else {
       Value* Val = PN->getIncomingValueForBlock(BB);
       for (unsigned PI = 0, PE = PN->getNumIncomingValues(); PI != PE; ++PI) {
         // See if the incoming value for the common predecessor is equal to the
         // one for BB, in which case this phi node will not prevent the merging
         // of the block.
         BasicBlock *IBB = PN->getIncomingBlock(PI);
         if (BBPreds.count(IBB) &&
-            !CanMergeValues(Val, PN->getIncomingValue(PI))) {
+            !canMergeValues(Val, PN->getIncomingValue(PI))) {
           LLVM_DEBUG(dbgs() << "Can't fold, phi node " << PN->getName()
                             << " in " << Succ->getName()
                             << " is conflicting with regard to common "
                             << "predecessor " << IBB->getName() << "\n");
           return false;
         }
       }
     }

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
+
+; 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 [[LOOP:%.*]]
+; CHECK-NEXT:    i32 12, label [[G:%.*]]
+; CHECK-NEXT:    ]
+; CHECK:       loop:
+; CHECK-NEXT:    [[K2:%.*]] = phi i64 [ [[K3:%.*]], [[G]] ], [ undef, [[ENTRY:%.*]] ]
+; CHECK-NEXT:    br label [[G]]
+; CHECK:       g:
+; CHECK-NEXT:    [[K3]] = phi i64 [ [[K2]], [[LOOP]] ], [ poison, [[ENTRY]] ]
+; CHECK-NEXT:    br label [[LOOP]]
+; 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
+}