[SimplifyCFG] simplifyUnreachable(): erase instructions iff they are guaranteed to transfer execution to unreachable

[lebedev.ri]

Summary

This replaces the current ad-hoc implementation,
by syncing the code from InstCombine's implementation in InstCombinerImpl::visitUnreachableInst(),
with one exception that here in SimplifyCFG we are allowed to remove EH instructions.

Effectively, this now allows SimplifyCFG to remove calls (iff they won't throw and will return),
arithmetic/logic operations, etc.

[lebedev.ri]

llvm/test/CodeGen/PowerPC/2007-11-16-landingpad-split.ll

86–87

What happens here is that call void @llvm.stackrestore() ends up being located
right before unreachable, and we now happily erase it.
I think that makes sense, because resume would cause us to "return" from the function,
freeing all the stack anyways.

[efriedma]

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

4685

Invoke or catchswitch.

[nikic]

llvm/test/CodeGen/PowerPC/2007-11-16-landingpad-split.ll

86–87

This test is probably supposed to have a cleanup on the landingpad.

Speaking of, can someone point me to the relevant wording in LangRef/ExceptionHandling on why resuming from a non-cleanup landingpad is UB? At least that's how I understand the DwarfEHPrepare code.

[efriedma]

llvm/test/CodeGen/PowerPC/2007-11-16-landingpad-split.ll

86–87

I'm not sure it's really justified anywhere.

In practice, I think it works out for clang because we only use "resume" for cleanups; to rethrow an exception, we use __cxa_rethrow().

[lebedev.ri]

Tune comment.

[lebedev.ri]

Fix test instead of showing how it changes.

[nikic]

LGTM

[lebedev.ri]

Thank you for the review.

llvm/lib/Analysis/ValueTracking.cpp

 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/ADT/iterator_range.h"
 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/Analysis/AssumeBundleQueries.h"
 #include "llvm/Analysis/AssumptionCache.h"
+#include "llvm/Analysis/EHPersonalities.h"
 #include "llvm/Analysis/GuardUtils.h"
 #include "llvm/Analysis/InstructionSimplify.h"
 #include "llvm/Analysis/Loads.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Analysis/OptimizationRemarkEmitter.h"
 #include "llvm/Analysis/TargetLibraryInfo.h"
 #include "llvm/IR/Argument.h"
 #include "llvm/IR/Attributes.h"
bool llvm::isGuaranteedToTransferExecutionToSuccessor(const Instruction *I) {
   // arbitrary length of time, but programs aren't allowed to rely on that.
 
   // If there is no successor, then execution can't transfer to it.
   if (isa<ReturnInst>(I))
     return false;
   if (isa<UnreachableInst>(I))
     return false;
 
+  if (isa<CatchPadInst>(I)) {
+    switch (classifyEHPersonality(I->getFunction()->getPersonalityFn())) {
+    default:
+      // A catchpad may invoke exception object constructors and such, which
+      // in some languages can be arbitrary code, so be conservative by default.
+      return false;
+    case EHPersonality::CoreCLR:
+      // For CoreCLR, it just involves a type test.
+      return true;
+    }
+  }
+
   // An instruction that returns without throwing must transfer control flow
   // to a successor.
   return !I->mayThrow() && I->willReturn();
 }
 
 bool llvm::isGuaranteedToTransferExecutionToSuccessor(const BasicBlock *BB) {
   // TODO: This is slightly conservative for invoke instruction since exiting
   // via an exception *is* normal control for them.

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;
 }
 
+// WARNING: keep in sync with SimplifyCFGOpt::simplifyUnreachable()!
 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

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

while (!CondBranchPreds.empty()) {
     if (isa<ReturnInst>(BI->getSuccessor(0)->getTerminator()) &&
         isa<ReturnInst>(BI->getSuccessor(1)->getTerminator()) &&
         SimplifyCondBranchToTwoReturns(BI, Builder))
       return true;
   }
   return false;
 }
 
+// WARNING: keep in sync with InstCombinerImpl::visitUnreachableInst()!
 bool SimplifyCFGOpt::simplifyUnreachable(UnreachableInst *UI) {
   BasicBlock *BB = UI->getParent();
 
   bool Changed = false;
 
   // If there are any instructions immediately before the unreachable that can
   // be removed, do so.
   while (UI->getIterator() != BB->begin()) {
     BasicBlock::iterator BBI = UI->getIterator();
     --BBI;
-    // Do not delete instructions that can have side effects which might cause
-    // the unreachable to not be reachable; specifically, calls and volatile
-    // operations may have this effect.
-    if (isa<CallInst>(BBI) && !isa<DbgInfoIntrinsic>(BBI))
-      break;
 
-    if (BBI->mayHaveSideEffects()) {
-      if (auto *SI = dyn_cast<StoreInst>(BBI)) {
-        // 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 (SI->isVolatile())
-          break;
-      } else if (isa<CatchPadInst>(BBI)) {
-        // A catchpad may invoke exception object constructors and such, which
-        // in some languages can be arbitrary code, so be conservative by
-        // default.
-        // For CoreCLR, it just involves a type test, so can be removed.
-        if (classifyEHPersonality(BB->getParent()->getPersonalityFn()) !=
-            EHPersonality::CoreCLR)
-          break;
-      } else if (!isa<LoadInst>(BBI) && !isa<AtomicRMWInst>(BBI) &&
-                 !isa<AtomicCmpXchgInst>(BBI) && !isa<FenceInst>(BBI) &&
-                 !isa<VAArgInst>(BBI) && !isa<LandingPadInst>(BBI)) {
-        break;
-      }
-      // Note that deleting LandingPad's here is in fact okay, although it
-      // involves a bit of subtle reasoning. If this inst is a LandingPad,
-      // all the predecessors of this block will be the unwind edges of Invokes,
-      // and we can therefore guarantee this block will be erased.
-    }
+    if (!isGuaranteedToTransferExecutionToSuccessor(&*BBI))
+      break; // 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.
+
+    // pending a potential LangRef change permitting volatile stores to trap.
+    if (auto *SI = dyn_cast<StoreInst>(&*BBI))
+        break; // Can not drop this instruction. We're done here.
+
+    // Note that deleting EH's here is in fact okay, although it involves a bit
+    // of subtle reasoning. If this inst is an EH, all the predecessors of this
+    // block will be the unwind edges of Invoke/CatchSwitch/CleanupReturn,
 
     // Delete this instruction (any uses are guaranteed to be dead)
     BBI->replaceAllUsesWith(PoisonValue::get(BBI->getType()));
     BBI->eraseFromParent();
     Changed = true;
   }
 
   // If the unreachable instruction is the first in the block, take a gander

llvm/test/CodeGen/PowerPC/2007-11-16-landingpad-split.ll

 ; CHECK-NEXT:    std 31, -8(1)
 ; CHECK-NEXT:    std 0, 16(1)
 ; CHECK-NEXT:    stdu 1, -176(1)
 ; CHECK-NEXT:    .cfi_def_cfa_offset 176
 ; CHECK-NEXT:    .cfi_offset r31, -8
 ; CHECK-NEXT:    .cfi_offset lr, 16
 ; CHECK-NEXT:    mr 31, 1
 ; CHECK-NEXT:    .cfi_def_cfa_register r31
-; CHECK-NEXT:    .cfi_offset r27, -40
 ; CHECK-NEXT:    .cfi_offset r28, -32
 ; CHECK-NEXT:    .cfi_offset r29, -24
 ; CHECK-NEXT:    .cfi_offset r30, -16
-; CHECK-NEXT:    std 29, 152(31) # 8-byte Folded Spill
-; CHECK-NEXT:    mr 29, 3
-; CHECK-NEXT:    rldic 3, 5, 3, 29
-; CHECK-NEXT:    std 27, 136(31) # 8-byte Folded Spill
 ; CHECK-NEXT:    std 30, 160(31) # 8-byte Folded Spill
 ; CHECK-NEXT:    mr 30, 4
-; CHECK-NEXT:    addi 3, 3, 15
-; CHECK-NEXT:    rldicl 3, 3, 60, 4
-; CHECK-NEXT:    mr 27, 1
-; CHECK-NEXT:    rldicl 3, 3, 4, 28
-; CHECK-NEXT:    addi 4, 31, 176
-; CHECK-NEXT:    neg 3, 3
+; CHECK-NEXT:    rldic 4, 5, 3, 29
+; CHECK-NEXT:    std 29, 152(31) # 8-byte Folded Spill
+; CHECK-NEXT:    mr 29, 3
+; CHECK-NEXT:    addi 4, 4, 15
+; CHECK-NEXT:    rldicl 4, 4, 60, 4
+; CHECK-NEXT:    addi 3, 31, 176
+; CHECK-NEXT:    rldicl 4, 4, 4, 28
 ; CHECK-NEXT:    std 28, 144(31) # 8-byte Folded Spill
-; CHECK-NEXT:    stdux 4, 1, 3
+; CHECK-NEXT:    neg 4, 4
+; CHECK-NEXT:    stdux 3, 1, 4
 ; CHECK-NEXT:    addi 3, 1, 112
 ; CHECK-NEXT:  .Ltmp0:
 ; CHECK-NEXT:    bl Foo
 ; CHECK-NEXT:    nop
 ; CHECK-NEXT:  .Ltmp1:
 ; CHECK-NEXT:  # %bb.1: # %bb30.preheader
-; CHECK-NEXT:    addi 28, 31, 120
+; CHECK-NEXT:    addi 28, 31, 128
 ; CHECK-NEXT:    cmpldi 30, 0
 ; CHECK-NEXT:    beq 0, .LBB0_4
 ; CHECK-NEXT:  .LBB0_2: # %cond_true
 ; CHECK-NEXT:    #
 ; CHECK-NEXT:  .Ltmp3:
 ; CHECK-NEXT:    mr 3, 29
 ; CHECK-NEXT:    mr 4, 28
 ; CHECK-NEXT:    bl Bar
 ; CHECK-NEXT:    nop
 ; CHECK-NEXT:  .Ltmp4:
 ; CHECK-NEXT:  # %bb.3: # %invcont23
 ; CHECK-NEXT:    #
-; CHECK-NEXT:    ld 3, 128(31)
+; CHECK-NEXT:    ld 3, 136(31)
 ; CHECK-NEXT:    sub 30, 30, 3
 ; CHECK-NEXT:    cmpldi 30, 0
 ; CHECK-NEXT:    bne 0, .LBB0_2
 ; CHECK-NEXT:  .LBB0_4: # %cleanup
 ; CHECK-NEXT:    ld 30, 160(31) # 8-byte Folded Reload
 ; CHECK-NEXT:    ld 29, 152(31) # 8-byte Folded Reload
 ; CHECK-NEXT:    ld 28, 144(31) # 8-byte Folded Reload
-; CHECK-NEXT:    ld 27, 136(31) # 8-byte Folded Reload
 ; CHECK-NEXT:    ld 1, 0(1)
 ; CHECK-NEXT:    ld 0, 16(1)
 ; CHECK-NEXT:    ld 31, -8(1)
 ; CHECK-NEXT:    mtlr 0
 ; CHECK-NEXT:    blr
 ; CHECK-NEXT:  .LBB0_5: # %unwind.loopexit.split-lp
 ; CHECK-NEXT:  .Ltmp2:
-; CHECK-NEXT:    b .LBB0_7
 ; CHECK-NEXT:  .LBB0_6: # %unwind.loopexit
 ; CHECK-NEXT:  .Ltmp5:
-; CHECK-NEXT:  .LBB0_7: # %unwind
-; CHECK-NEXT:    ld 3, 0(1)
-; CHECK-NEXT:    mr 1, 27
-; CHECK-NEXT:    std 3, 0(1)
 entry:
   %effectiveRange = alloca %struct.Range, align 8    ; <%struct.Range*> [#uses=2]
   %tmp4 = call i8* @llvm.stacksave()    ; <i8*> [#uses=1]
   %size1 = trunc i64 %size to i32   ; <i32> [#uses=1]
   %tmp17 = alloca i8*, i32 %size1   ; <i8**> [#uses=1]
   invoke void @Foo(i8** %tmp17)
       to label %bb30.preheader unwind label %unwind
 
 bb30.preheader:   ; preds = %entry
   %tmp26 = getelementptr %struct.Range, %struct.Range* %effectiveRange, i64 0, i32 1    ; <i64*> [#uses=1]
   br label %bb30
 
 unwind:   ; preds = %cond_true, %entry
         %exn = landingpad {i8*, i32}
                  catch i8* null
   call void @llvm.stackrestore(i8* %tmp4)
         resume { i8*, i32 } %exn
 
 invcont23:    ; preds = %cond_true
   %tmp27 = load i64, i64* %tmp26, align 8    ; <i64> [#uses=1]
   %tmp28 = sub i64 %range_addr.1.0, %tmp27    ; <i64> [#uses=1]
   br label %bb30
 
 bb30:   ; preds = %invcont23, %bb30.preheader
   %range_addr.1.0 = phi i64 [ %tmp28, %invcont23 ], [ %range.0.1, %bb30.preheader ]    ; <i64> [#uses=2]

llvm/test/Transforms/SimplifyCFG/simplifyUnreachable-degenerate-conditional-branch-with-matching-destinations.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -S -simplifycfg -simplifycfg-require-and-preserve-domtree=1 < %s | FileCheck %s
 
 @global = external global i16, align 1
 @global.1 = external global i16, align 1
 @global.2 = external global i16, align 1
 
 define void @widget() {
 ; CHECK-LABEL: @widget(
 ; CHECK-NEXT:  bb:
-; CHECK-NEXT:    [[I:%.*]] = load i16, i16* @global, align 1
-; CHECK-NEXT:    [[I13:%.*]] = icmp ne i16 [[I]], 0
-; CHECK-NEXT:    call void @llvm.assume(i1 [[I13]])
 ; CHECK-NEXT:    unreachable
 ;
 bb:
   %i = load i16, i16* @global, align 1
   %i13 = icmp ne i16 %i, 0
   br i1 %i13, label %bb16, label %bb14
 
 bb14:                                             ; preds = %bb

llvm/test/Transforms/SimplifyCFG/switch-range-to-icmp.ll

 }
 
 ; This would crash because we did not clean up the
 ; default block of the switch before removing the switch.
 
 define void @PR42737(i32* %a, i1 %c) {
 ; CHECK-LABEL: @PR42737(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[TMP0:%.*]] = xor i1 [[C:%.*]], true
-; CHECK-NEXT:    call void @llvm.assume(i1 [[TMP0]])
 ; CHECK-NEXT:    unreachable
 ;
 entry:
   br i1 %c, label %switch, label %else
 
 else:
   store i32 2, i32* %a
   br label %switch