[InstCombine] Transitively propagate `unreachable` into predecessors

[lebedev.ri]

Summary

Currently we try to erase instructions only in the very block
that literally has unreachable terminator.
While this is conservatively correct, we can do better.

If the block consists only of said unreachable,
then it stops being a successor of it's predecessors,
and if for some predecessor that means it no longer has
any successors, then said predecessor earns an unreachable
terminator itself. And so on.

SimplifyCFG would do at least some of that,
but relying on that requires for the InstCombine pass
to be rerun after SimplifyCFG, which isn't optimal..

[nikic]

This is walking the edge of what is appropriate for InstCombine, so I'd like to understand why we want to try so hard to remove unreachable code here. As InstCombine does not introduce its own unreachable terminators, after recent changes to SimplifyCFG, running SimplifyCFG+InstCombine should produce an optimal result (as far as unreachable code is concerned). There is no need to iterate between them to reach a fixed point (again, as far as this transform is concerned).

InstCombine can introduce pseudo-unreachable code in the form of either the store null pattern, or branches on constants that render certain edges effectively dead. Handling those cases could cut down fixpoint iteration. Is extending towards such cases the plan here?

[lebedev.ri]

In D105363#2856664, @nikic wrote:

This is walking the edge of what is appropriate for InstCombine, so I'd like to understand why we want to try so hard to remove unreachable code here. As InstCombine does not introduce its own unreachable terminators, after recent changes to SimplifyCFG, running SimplifyCFG+InstCombine should produce an optimal result (as far as unreachable code is concerned). There is no need to iterate between them to reach a fixed point (again, as far as this transform is concerned).

I'm mainly trying to harden the handling of unreachable as much as possible before D104870,
in hope that some of the regressions caused by that patch are avoidable.

InstCombine can introduce pseudo-unreachable code in the form of either the store null pattern, or branches on constants that render certain edges effectively dead. Handling those cases could cut down fixpoint iteration. Is extending towards such cases the plan here?

Yes, dealing with that as much as reasonably possible in instcombine itself is something i'd like to see happen.

[lebedev.ri]

@spatel thoughts?

[spatel]

In D105363#2863232, @lebedev.ri wrote:

@spatel thoughts?

I haven't closely followed the related patches, so I'm probably not adding much here...
But if I run -simplifycfg on any of the tests with diffs here, they are completely zapped down to a single unreachable.
Can you add a test to demonstrate where we might fall through the cracks of both passes? (possibly a test for PhaseOrdering)

[lebedev.ri]

In D105363#2865153, @spatel wrote:

In D105363#2863232, @lebedev.ri wrote:

@spatel thoughts?

I haven't closely followed the related patches, so I'm probably not adding much here...
But if I run -simplifycfg on any of the tests with diffs here, they are completely zapped down to a single unreachable.
Can you add a test to demonstrate where we might fall through the cracks of both passes? (possibly a test for PhaseOrdering)

I'm not really sure if there is any pattern that fits your description.
The goal/question here is mostly: should we, the instcombine, be able to get rid of more known-dead code,
potentially allowing further folds, without deferring until the next time instcombine runs after simplifycfg runs after us?

[spatel]

In D105363#2865190, @lebedev.ri wrote:

In D105363#2865153, @spatel wrote:

In D105363#2863232, @lebedev.ri wrote:

@spatel thoughts?

I haven't closely followed the related patches, so I'm probably not adding much here...
But if I run -simplifycfg on any of the tests with diffs here, they are completely zapped down to a single unreachable.
Can you add a test to demonstrate where we might fall through the cracks of both passes? (possibly a test for PhaseOrdering)

I'm not really sure if there is any pattern that fits your description.
The goal/question here is mostly: should we, the instcombine, be able to get rid of more known-dead code,
potentially allowing further folds, without deferring until the next time instcombine runs after simplifycfg runs after us?

I'm leaning towards "no" then. It seems similar to me to arguments between CSE and InstCombine. For example, we could try harder to make InstCombine see through identical values via pattern matching, but we intentionally do not try that because we have passes dedicated to that functionality. Here, we have a pass (SimplifyCFG) that can and does have the logic to propagate unreachable code, so I don't think we should duplicate that effort for a potential small improvement in efficiency.

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

Instruction *InstCombinerImpl::visitReturnInst(ReturnInst &RI) {
   KnownBits Known = computeKnownBits(ResultOp, 0, &RI);
   if (Known.isConstant())
     return replaceOperand(RI, 0,
         Constant::getIntegerValue(VTy, Known.getConstant()));
 
   return nullptr;
 }
 
+// FIXME: we should treat non-CFG-altering sudo-unreachable as unreachable!
 Instruction *InstCombinerImpl::visitUnreachableInst(UnreachableInst &I) {
-  // Try to remove the previous instruction if it must lead to unreachable.
-  // This includes instructions like stores and "llvm.assume" that may not get
-  // removed by simple dead code elimination.
-  while (Instruction *Prev = I.getPrevNonDebugInstruction()) {
+  SmallVector<BasicBlock *, 16> Worklist;
+  SmallPtrSet<BasicBlock *, 16> KnownEmptyUnreachableBlocks;
+  Worklist.emplace_back(I.getParent());
+  while (!Worklist.empty()) {
+    BasicBlock *BB = Worklist.pop_back_val();
+    Instruction *Term = BB->getTerminator();
+    Instruction *Instr;
+
+    // This block (maybe transitively) ends in an `unreachable`.
+    // Iteratively try to remove preceding instruction if it must lead to
+    // said `unreachable`. This includes instructions like stores and
+    // "llvm.assume" that may not get removed by simple dead code elimination.
+    while ((Instr = Term->getPrevNonDebugInstruction())) {
       // While we theoretically can erase EH, that would result in a block that
       // used to start with an EH no longer starting with EH, which is invalid.
       // To make it valid, we'd need to fixup predecessors to no longer refer to
       // this block, but that changes CFG, which is not allowed in InstCombine.
-    if (Prev->isEHPad())
-      return nullptr; // Can not drop any more instructions. We're done here.
+      if (Instr->isEHPad())
+        break; // Can not drop any more instructions from this block.
 
-    if (!isGuaranteedToTransferExecutionToSuccessor(Prev))
-      return nullptr; // Can not drop any more instructions. We're done here.
+      if (!isGuaranteedToTransferExecutionToSuccessor(Instr))
+        break; // Can not drop any more instructions from this block.
       // Otherwise, this instruction can be freely erased,
       // even if it is not side-effect free.
 
-    // Temporarily disable removal of volatile stores preceding unreachable,
+      // Temporarily disable removal of volatile stores preceding `unreachable`,
       // pending a potential LangRef change permitting volatile stores to trap.
       // TODO: Either remove this code, or properly integrate the check into
       // isGuaranteedToTransferExecutionToSuccessor().
-    if (auto *SI = dyn_cast<StoreInst>(Prev))
+      if (auto *SI = dyn_cast<StoreInst>(Instr))
         if (SI->isVolatile())
-        return nullptr; // Can not drop this instruction. We're done here.
+          break; // Can not drop any more instructions from this block.
 
       // A value may still have uses before we process it here (for example, in
       // another unreachable block), so convert those to poison.
-    replaceInstUsesWith(*Prev, PoisonValue::get(Prev->getType()));
-    eraseInstFromFunction(*Prev);
+      replaceInstUsesWith(*Instr, PoisonValue::get(Instr->getType()));
+      eraseInstFromFunction(*Instr);
+    }
+
+    // Okay, we've erased all the instruction we could from this block.
+    // But did we erase *all* the instructions, or did we stop before that?
+    assert((Instr == nullptr) == hasNItems(BB->instructionsWithoutDebug(), 1) &&
+           "Checking that Instr is nullptr is eqivalent to checking that "
+           "the block has no other instructions.");
+    if (Instr)
+      continue; // Block not empty, other instructions remain.
+
+    // Aha, so the block (maybe transitively) consists only of an `unreachable`.
+    KnownEmptyUnreachableBlocks.insert(BB);
+    // Which means that the predecessors no longer branch to this block, and if
+    // they have no other successors, they also end in `unreachable`.
+    // Let's not wait until SimplifyCFG runs and propagates `unreachable`,
+    // but let's just pretend that already happened, and repeat the process.
+    SmallPtrSet<BasicBlock *, 4> AnalyzedPreds;
+    for (BasicBlock *Pred : predecessors(BB)) {
+      // Have we not dealt with this predecessor before?
+      if (!AnalyzedPreds.insert(Pred).second)
+        continue; // We have.
+      // Does this predecessor block branch only to the blocks
+      // that we know to (transitively) end in an `unreachable`?
+      // FIXME: we could try traversing into the blocks that we don't know
+      // to (transitively) end in an `unreachable` to check if they actually do.
+      if (!all_of(successors(Pred),
+                  [&KnownEmptyUnreachableBlocks](BasicBlock *SuccOfPred) {
+                    return KnownEmptyUnreachableBlocks.contains(SuccOfPred);
+                  }))
+        continue; // It does not, some successors *may* be non-`unreachable`.
+      // Otherwise, let's spread the `unreachable` knowledge to it!
+      Worklist.emplace_back(Pred);
+    }
   }
-  assert(I.getParent()->sizeWithoutDebug() == 1 && "The block is now empty.");
-  // FIXME: recurse into unconditional predecessors?
+
   return nullptr;
 }
 
 Instruction *InstCombinerImpl::visitUnconditionalBranchInst(BranchInst &BI) {
   assert(BI.isUnconditional() && "Only for unconditional branches.");
 
   // If this store is the second-to-last instruction in the basic block
   // (excluding debug info and bitcasts of pointers) and if the block ends with

llvm/test/Transforms/InstCombine/assume.ll

;
   unreachable
 }
 
 ; PR47416
 
 define i32 @unreachable_assume(i32 %x, i32 %y) {
 ; CHECK-LABEL: @unreachable_assume(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[CMP0:%.*]] = icmp sgt i32 [[X:%.*]], 1
-; CHECK-NEXT:    [[CMP1:%.*]] = icmp eq i32 [[Y:%.*]], 1
-; CHECK-NEXT:    [[OR:%.*]] = or i1 [[CMP0]], [[CMP1]]
-; CHECK-NEXT:    tail call void @llvm.assume(i1 [[OR]])
-; CHECK-NEXT:    [[CMP2:%.*]] = icmp eq i32 [[X]], 1
-; CHECK-NEXT:    br i1 [[CMP2]], label [[IF:%.*]], label [[EXIT:%.*]]
+; CHECK-NEXT:    br i1 poison, label [[IF:%.*]], label [[EXIT:%.*]]
 ; CHECK:       if:
-; CHECK-NEXT:    [[A:%.*]] = and i32 [[Y]], -2
-; CHECK-NEXT:    [[CMP3:%.*]] = icmp ne i32 [[A]], 104
-; CHECK-NEXT:    tail call void @llvm.assume(i1 [[CMP3]])
 ; CHECK-NEXT:    br label [[EXIT]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    unreachable
 ;
 entry:
   %cmp0 = icmp sgt i32 %x, 1
   %cmp1 = icmp eq i32 %y, 1
   %or = or i1 %cmp0, %cmp1
exit:
   %cmp4 = icmp eq i32 %x, 2
   tail call void @llvm.assume(i1 %cmp4)
   unreachable
 }
 
 define i32 @unreachable_assume_logical(i32 %x, i32 %y) {
 ; CHECK-LABEL: @unreachable_assume_logical(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[CMP0:%.*]] = icmp sgt i32 [[X:%.*]], 1
-; CHECK-NEXT:    [[CMP1:%.*]] = icmp eq i32 [[Y:%.*]], 1
-; CHECK-NEXT:    [[OR:%.*]] = select i1 [[CMP0]], i1 true, i1 [[CMP1]]
-; CHECK-NEXT:    tail call void @llvm.assume(i1 [[OR]])
-; CHECK-NEXT:    [[CMP2:%.*]] = icmp eq i32 [[X]], 1
-; CHECK-NEXT:    br i1 [[CMP2]], label [[IF:%.*]], label [[EXIT:%.*]]
+; CHECK-NEXT:    br i1 poison, label [[IF:%.*]], label [[EXIT:%.*]]
 ; CHECK:       if:
-; CHECK-NEXT:    [[A:%.*]] = and i32 [[Y]], -2
-; CHECK-NEXT:    [[CMP3:%.*]] = icmp ne i32 [[A]], 104
-; CHECK-NEXT:    tail call void @llvm.assume(i1 [[CMP3]])
 ; CHECK-NEXT:    br label [[EXIT]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    unreachable
 ;
 entry:
   %cmp0 = icmp sgt i32 %x, 1
   %cmp1 = icmp eq i32 %y, 1
   %or = select i1 %cmp0, i1 true, i1 %cmp1
exit:
   %cmp4 = icmp eq i32 %x, 2
   tail call void @llvm.assume(i1 %cmp4)
   unreachable
 }
 
 define i32 @unreachable_assumes_and_store(i32 %x, i32 %y, i32* %p) {
 ; CHECK-LABEL: @unreachable_assumes_and_store(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[CMP0:%.*]] = icmp sgt i32 [[X:%.*]], 1
-; CHECK-NEXT:    [[CMP1:%.*]] = icmp eq i32 [[Y:%.*]], 1
-; CHECK-NEXT:    [[OR:%.*]] = or i1 [[CMP0]], [[CMP1]]
-; CHECK-NEXT:    tail call void @llvm.assume(i1 [[OR]])
-; CHECK-NEXT:    [[CMP2:%.*]] = icmp eq i32 [[X]], 1
-; CHECK-NEXT:    br i1 [[CMP2]], label [[IF:%.*]], label [[EXIT:%.*]]
+; CHECK-NEXT:    br i1 poison, label [[IF:%.*]], label [[EXIT:%.*]]
 ; CHECK:       if:
-; CHECK-NEXT:    [[A:%.*]] = and i32 [[Y]], -2
-; CHECK-NEXT:    [[CMP3:%.*]] = icmp ne i32 [[A]], 104
-; CHECK-NEXT:    tail call void @llvm.assume(i1 [[CMP3]])
 ; CHECK-NEXT:    br label [[EXIT]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    unreachable
 ;
 entry:
   %cmp0 = icmp sgt i32 %x, 1
   %cmp1 = icmp eq i32 %y, 1
   %or = or i1 %cmp0, %cmp1
exit:
   tail call void @llvm.assume(i1 %cmp5)
   store i32 %x, i32* %p
   unreachable
 }
 
 define i32 @unreachable_assumes_and_store_logical(i32 %x, i32 %y, i32* %p) {
 ; CHECK-LABEL: @unreachable_assumes_and_store_logical(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[CMP0:%.*]] = icmp sgt i32 [[X:%.*]], 1
-; CHECK-NEXT:    [[CMP1:%.*]] = icmp eq i32 [[Y:%.*]], 1
-; CHECK-NEXT:    [[OR:%.*]] = select i1 [[CMP0]], i1 true, i1 [[CMP1]]
-; CHECK-NEXT:    tail call void @llvm.assume(i1 [[OR]])
-; CHECK-NEXT:    [[CMP2:%.*]] = icmp eq i32 [[X]], 1
-; CHECK-NEXT:    br i1 [[CMP2]], label [[IF:%.*]], label [[EXIT:%.*]]
+; CHECK-NEXT:    br i1 poison, label [[IF:%.*]], label [[EXIT:%.*]]
 ; CHECK:       if:
-; CHECK-NEXT:    [[A:%.*]] = and i32 [[Y]], -2
-; CHECK-NEXT:    [[CMP3:%.*]] = icmp ne i32 [[A]], 104
-; CHECK-NEXT:    tail call void @llvm.assume(i1 [[CMP3]])
 ; CHECK-NEXT:    br label [[EXIT]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    unreachable
 ;
 entry:
   %cmp0 = icmp sgt i32 %x, 1
   %cmp1 = icmp eq i32 %y, 1
   %or = select i1 %cmp0, i1 true, i1 %cmp1