[IR][LoopRotate] avoid leaving phi with no operands (PR48296)

[spatel]

Summary

https://llvm.org/PR48296 shows an example where we delete all of the operands of a phi without actually deleting the phi, and that is invalid IR. The reduced test included here currently crashes for that reason. This was updated relatively recently in D80141.

I'm not familiar with all of the callers and use cases, but it seems there are passes that expect to handle deleting such a phi at a later time. We get regression test failures if we just stub out the DeletePHIIfEmpty argument in removeIncomingValue() for example.

So I changed the logic in BasicBlock::removePredecessor() to allow deletion of the phi if it has only one predecessor to start with because removing the lone predecessor is guaranteed to produce invalid IR in that case. This does not appear to cause problems in other passes.

[lebedev.ri]

I think the bug is downstream - removePredecessor()'s default for KeepOneInputPHIs is false,
so someone explicitly asked for this behaviour.

[spatel]

In D92247#2420756, @lebedev.ri wrote:

I think the bug is downstream - removePredecessor()'s default for KeepOneInputPHIs is false,
so someone explicitly asked for this behaviour.

For this example, we're getting to removePredecessor() from llvm::changeToUnreachable(), where PreserveLCSSA is set and becomes KeepOneInputPHIs. If I change that to ignore PreserveLCSSA, then we get a different crash. So there's apparently some valid reason to keep the behavior where the phi ends up with 1 predecessor vs. ends up with 0 predecessors.

[lebedev.ri]

llvm/lib/IR/BasicBlock.cpp

320–321

There's also a comment at the declaration of the function

321–346

Ok, but i think this is rather akward.
It should be more like this.
Note that removeIncomingValue() *only* removes PHI's if they had a single pred,
so it doesn't make sense to pass anything related to KeepOneInputPHIs to it.

[lattner]

I don't think this is the right way to go, this breaks the invariant that # inputs to a phi node should match the # predecessors to a block. I'd recommend allowing zero input phi nodes in zero-predecessor blocks. I'm not sure why we ban zero input phi nodes right now.

[spatel]

Patch updated:
Pre-committed the suggested cleanups ( 2cebad7 , ce134da ), so this patch becomes even simpler.

[spatel]

In D92247#2421208, @lattner wrote:

I don't think this is the right way to go, this breaks the invariant that # inputs to a phi node should match the # predecessors to a block. I'd recommend allowing zero input phi nodes in zero-predecessor blocks. I'm not sure why we ban zero input phi nodes right now.

I'm not seeing how this would break the assumption (and maybe that's clearer with the updated patch?), but that's an interesting question and independent of this fix IIUC.

The verifier assertion says:

// Ensure that PHI nodes have at least one entry!
Assert(PN.getNumIncomingValues() != 0,
       "PHI nodes must have at least one entry.  If the block is dead, "
       "the PHI should be removed!",
       &PN);

But if we're in an unreachable block, then we allow other IR forms that are even less expected (self-reference), so we should loosen this restriction?

[lebedev.ri]

LGTM, thanks.

This only matters for unreachable blocks,
so i think i agree that the assertion should be relaxed,
but this is a reasonable cleanup regardless.

[lattner]

But if we're in an unreachable block, then we allow other IR forms that are even less expected (self-reference), so we should loosen this restriction?

Yes, I'm suggesting we delete that assertion entirely and just check that # entries = # predecessors.

[foad]

llvm/lib/IR/BasicBlock.cpp

333

FYI I tried this as part of D80206 but had to revert because of https://bugs.llvm.org/show_bug.cgi?id=46343.

[spatel]

llvm/lib/IR/BasicBlock.cpp

333

Hmm...I tried the test case from that report with this patch, and I don't see crashing. D80206 was bigger than this change, so something else might be needed to trigger the bug. It's also possible that jump-threading got better about ignoring dead code?

If there are no objections, I think we should make this change just to make things simpler. I can look at relaxing the assert as a next step.

[foad]

llvm/lib/IR/BasicBlock.cpp

333

No objections from me.

llvm/include/llvm/IR/BasicBlock.h

public:
   /// counts go to zero.  Then everything is delete'd for real.  Note that no
   /// operations are valid on an object that has "dropped all references",
   /// except operator delete.
   void dropAllReferences();
 
   /// Update PHI nodes in this BasicBlock before removal of predecessor \p Pred.
   /// Note that this function does not actually remove the predecessor.
   ///
-  /// If \p KeepOneInputPHIs is true then don't remove PHIs that are left with
-  /// zero or one incoming values, and don't simplify PHIs with all incoming
-  /// values the same.
+  /// If \p KeepOneInputPHIs is true, then don't remove PHIs that are left with
+  /// one incoming value and don't simplify PHIs with all incoming values the
+  /// same.
   void removePredecessor(BasicBlock *Pred, bool KeepOneInputPHIs = false);
 
   bool canSplitPredecessors() const;
 
   /// Split the basic block into two basic blocks at the specified instruction.
   ///
   /// Note that all instructions BEFORE the specified iterator stay as part of
   /// the original basic block, an unconditional branch is added to the original

llvm/lib/IR/BasicBlock.cpp

const BasicBlock *BasicBlock::getUniqueSuccessor() const {
   }
   return SuccBB;
 }
 
 iterator_range<BasicBlock::phi_iterator> BasicBlock::phis() {
   PHINode *P = empty() ? nullptr : dyn_cast<PHINode>(&*begin());
   return make_range<phi_iterator>(P, nullptr);
 }
 
 void BasicBlock::removePredecessor(BasicBlock *Pred,
                                    bool KeepOneInputPHIs) {
   // Use hasNUsesOrMore to bound the cost of this assertion for complex CFGs.
   assert((hasNUsesOrMore(16) || llvm::is_contained(predecessors(this), Pred)) &&
          "Pred is not a predecessor!");
 
   // Return early if there are no PHI nodes to update.
   if (!isa<PHINode>(begin()))
     return;
 
   unsigned NumPreds = cast<PHINode>(front()).getNumIncomingValues();
   for (PHINode &Phi : make_early_inc_range(phis())) {
-    Phi.removeIncomingValue(Pred, !KeepOneInputPHIs);
+    Phi.removeIncomingValue(Pred);
     if (KeepOneInputPHIs)
       continue;
     // If we have a single predecessor, removeIncomingValue erased the PHI
     // node itself.
     // Try to replace the PHI node with a constant value.
     if (NumPreds > 1) {
       if (Value *PhiConstant = Phi.hasConstantValue()) {
         Phi.replaceAllUsesWith(PhiConstant);
         Phi.eraseFromParent();
       }
     }
   }
 }
 
 bool BasicBlock::canSplitPredecessors() const {
   const Instruction *FirstNonPHI = getFirstNonPHI();
   if (isa<LandingPadInst>(FirstNonPHI))
     return true;
   // This is perhaps a little conservative because constructs like
   // CleanupBlockInst are pretty easy to split.  However, SplitBlockPredecessors
   // cannot handle such things just yet.

llvm/test/Transforms/LoopRotate/phi-empty.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -S -lcssa -loop-rotate < %s | FileCheck %s
+
+define void @PR48296(i1 %cond) {
+; CHECK-LABEL: @PR48296(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[LOOP:%.*]]
+; CHECK:       loop:
+; CHECK-NEXT:    br i1 [[COND:%.*]], label [[INC:%.*]], label [[LOOP_BACKEDGE:%.*]]
+; CHECK:       loop.backedge:
+; CHECK-NEXT:    br label [[LOOP]]
+; CHECK:       dead:
+; CHECK-NEXT:    unreachable
+; CHECK:       inc:
+; CHECK-NEXT:    br label [[LOOP_BACKEDGE]]
+; CHECK:       return:
+; CHECK-NEXT:    ret void
+;
+entry:
+  br label %loop
+
+loop:
+  br i1 %cond, label %inc, label %loop
+
+dead:                                        ; No predecessors!
+  br i1 %cond, label %inc, label %return
+
+inc:
+  br label %loop
+
+return:
+  %r = phi i32 [ undef, %dead ]
+  ret void
+}