diff --git a/llvm/lib/Transforms/InstCombine/InstructionCombining.cpp b/llvm/lib/Transforms/InstCombine/InstructionCombining.cpp --- a/llvm/lib/Transforms/InstCombine/InstructionCombining.cpp +++ b/llvm/lib/Transforms/InstCombine/InstructionCombining.cpp @@ -2870,38 +2870,80 @@ 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()) { - // 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. + SmallVector Worklist; + SmallPtrSet KnownEmptyUnreachableBlocks; + Worklist.emplace_back(I.getParent()); + while (!Worklist.empty()) { + BasicBlock *BB = Worklist.pop_back_val(); + Instruction *Term = BB->getTerminator(); + Instruction *Instr; - if (!isGuaranteedToTransferExecutionToSuccessor(Prev)) - return nullptr; // Can not drop any more instructions. We're done here. - // Otherwise, this instruction can be freely erased, - // even if it is not side-effect free. + // 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 (Instr->isEHPad()) + break; // Can not drop any more instructions from this block. - // 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(Prev)) - if (SI->isVolatile()) - return nullptr; // Can not drop this instruction. 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. - // 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); + // 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(Instr)) + if (SI->isVolatile()) + 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(*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 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; } diff --git a/llvm/test/Transforms/InstCombine/assume.ll b/llvm/test/Transforms/InstCombine/assume.ll --- a/llvm/test/Transforms/InstCombine/assume.ll +++ b/llvm/test/Transforms/InstCombine/assume.ll @@ -630,16 +630,8 @@ 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 @@ -667,16 +659,8 @@ 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 @@ -704,16 +688,8 @@ 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 @@ -744,16 +720,8 @@ 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