[WinEH] Simplify unreachable catchpads

[JosephTremoulet]

Summary

At least for CoreCLR, a catchpad which immediately executes an
unreachable instruction indicates that the exception can never have a
matching type, and so such catchpads can be removed, and so can their
catchswitches if the catchswitch becomes empty.

[majnemer]

Can we get a test with a cleanupret which unwinds to a catchswitch which has unreachable catchpads with and without it being unwinds to caller?

lib/IR/Instructions.cpp

938

Please end this with a period.

942

Ditto.

lib/Transforms/Utils/SimplifyCFG.cpp

3523–3560

Please use auto *II here.

3528

Please use auto *CSI here.

3545

I'd write this as CSI->getNumHandlers() == 0.

3546

Couldn't some other predecessor cause Changed to be true? I think we could rephrase this as an assertion that CSI->getNumHandlers() != 0 before the loop.

[JosephTremoulet]

rebase, fix cosmetics (still need to update tests)

[JosephTremoulet]

lib/Transforms/Utils/SimplifyCFG.cpp

3528

Sure. I went ahead and changed the rest of the function to use auto in these situations, to keep it consistent.

3546

I guess the intention of the assertion wasn't clear -- you seem to be interpreting it as "assert that we only eliminate a catchswitch if the code just above is what made it empty", but that's not what I was worried about (empty catchswitches fail the verifier anyway). This was just "We're about to change the IR, but we don't need Changed = true; here because we know Changed is already true if we've reached this spot".

I'm happy to add an assert message, or put in both asserts, or just replace the assertion with Changed = true; for simplicity; do you have a preference?

[JosephTremoulet]

• Expand test to cover all pred opcodes
• Fix handling for cleanupret preds (need to rewrite to unwind-to-caller, not replace with unreachable)

[majnemer]

lib/Transforms/Utils/SimplifyCFG.cpp

3546

Yes, I wasn't sure what you are asserting here. I'll leave this up to your judgement.

[JosephTremoulet]

replace assertion with code that handles the hypothetical failing case, for readability

[JosephTremoulet]

I believe I've addressed all the feedback.

[majnemer]

LGTM

include/llvm/IR/Instructions.h

public:
   }
 
   /// addHandler - Add an entry to the switch instruction...
   /// Note:
   /// This action invalidates handler_end(). Old handler_end() iterator will
   /// point to the added handler.
   void addHandler(BasicBlock *Dest);
 
+  void removeHandler(handler_iterator HI);
+
   unsigned getNumSuccessors() const { return getNumOperands() - 1; }
   BasicBlock *getSuccessor(unsigned Idx) const {
     assert(Idx < getNumSuccessors() &&
            "Successor # out of range for catchswitch!");
     return cast<BasicBlock>(getOperand(Idx + 1));
   }
   void setSuccessor(unsigned Idx, BasicBlock *NewSucc) {
     assert(Idx < getNumSuccessors() &&

lib/IR/Instructions.cpp

 void CatchSwitchInst::addHandler(BasicBlock *Handler) {
   unsigned OpNo = getNumOperands();
   growOperands(1);
   assert(OpNo < ReservedSpace && "Growing didn't work!");
   setNumHungOffUseOperands(getNumOperands() + 1);
   getOperandList()[OpNo] = Handler;
 }
 
+void CatchSwitchInst::removeHandler(handler_iterator HI) {
+  // Move all subsequent handlers up one.
+  Use *EndDst = op_end() - 1;
+  for (Use *CurDst = HI.getCurrent(); CurDst != EndDst; ++CurDst)
+    *CurDst = *(CurDst + 1);
+  // Null out the last handler use.
+  *EndDst = nullptr;
+
+  setNumHungOffUseOperands(getNumOperands() - 1);
+}
+
 BasicBlock *CatchSwitchInst::getSuccessorV(unsigned idx) const {
   return getSuccessor(idx);
 }
 unsigned CatchSwitchInst::getNumSuccessorsV() const {
   return getNumSuccessors();
 }
 void CatchSwitchInst::setSuccessorV(unsigned idx, BasicBlock *B) {
   setSuccessor(idx, B);

lib/Transforms/Utils/SimplifyCFG.cpp

 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SetOperations.h"
 #include "llvm/ADT/SetVector.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/ConstantFolding.h"
+#include "llvm/Analysis/EHPersonalities.h"
 #include "llvm/Analysis/InstructionSimplify.h"
 #include "llvm/Analysis/TargetTransformInfo.h"
 #include "llvm/Analysis/ValueTracking.h"
 #include "llvm/IR/CFG.h"
 #include "llvm/IR/ConstantRange.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/DerivedTypes.h"
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 (StoreInst *SI = dyn_cast<StoreInst>(BBI)) {
+      if (auto *SI = dyn_cast<StoreInst>(BBI)) {
         if (SI->isVolatile())
           break;
-      } else if (LoadInst *LI = dyn_cast<LoadInst>(BBI)) {
+      } else if (auto *LI = dyn_cast<LoadInst>(BBI)) {
         if (LI->isVolatile())
           break;
-      } else if (AtomicRMWInst *RMWI = dyn_cast<AtomicRMWInst>(BBI)) {
+      } else if (auto *RMWI = dyn_cast<AtomicRMWInst>(BBI)) {
         if (RMWI->isVolatile())
           break;
-      } else if (AtomicCmpXchgInst *CXI = dyn_cast<AtomicCmpXchgInst>(BBI)) {
+      } else if (auto *CXI = dyn_cast<AtomicCmpXchgInst>(BBI)) {
         if (CXI->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<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.
bool SimplifyCFGOpt::SimplifyUnreachable(UnreachableInst *UI) {
   // If the unreachable instruction is the first in the block, take a gander
   // at all of the predecessors of this instruction, and simplify them.
   if (&BB->front() != UI) return Changed;
 
   SmallVector<BasicBlock*, 8> Preds(pred_begin(BB), pred_end(BB));
   for (unsigned i = 0, e = Preds.size(); i != e; ++i) {
     TerminatorInst *TI = Preds[i]->getTerminator();
     IRBuilder<> Builder(TI);
-    if (BranchInst *BI = dyn_cast<BranchInst>(TI)) {
+    if (auto *BI = dyn_cast<BranchInst>(TI)) {
       if (BI->isUnconditional()) {
         if (BI->getSuccessor(0) == BB) {
           new UnreachableInst(TI->getContext(), TI);
           TI->eraseFromParent();
           Changed = true;
         }
       } else {
         if (BI->getSuccessor(0) == BB) {
           Builder.CreateBr(BI->getSuccessor(1));
           EraseTerminatorInstAndDCECond(BI);
         } else if (BI->getSuccessor(1) == BB) {
           Builder.CreateBr(BI->getSuccessor(0));
           EraseTerminatorInstAndDCECond(BI);
           Changed = true;
         }
       }
-    } else if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) {
+    } else if (auto *SI = dyn_cast<SwitchInst>(TI)) {
       for (SwitchInst::CaseIt i = SI->case_begin(), e = SI->case_end();
            i != e; ++i)
         if (i.getCaseSuccessor() == BB) {
           BB->removePredecessor(SI->getParent());
           SI->removeCase(i);
           --i; --e;
           Changed = true;
         }
-    } else if ((isa<InvokeInst>(TI) &&
-                cast<InvokeInst>(TI)->getUnwindDest() == BB) ||
-               isa<CatchSwitchInst>(TI)) {
+    } else if (auto *II = dyn_cast<InvokeInst>(TI)) {
+      if (II->getUnwindDest() == BB) {
         removeUnwindEdge(TI->getParent());
         Changed = true;
+      }
+    } else if (auto *CSI = dyn_cast<CatchSwitchInst>(TI)) {
+      if (CSI->getUnwindDest() == BB) {
+        removeUnwindEdge(TI->getParent());
+        Changed = true;
+        continue;
+      }
+
+      for (CatchSwitchInst::handler_iterator I = CSI->handler_begin(),
+                                             E = CSI->handler_end();
+           I != E; ++I) {
+        if (*I == BB) {
+          CSI->removeHandler(I);
+          --I;
+          --E;
+          Changed = true;
+        }
+      }
+      if (CSI->getNumHandlers() == 0) {
+        BasicBlock *CatchSwitchBB = CSI->getParent();
+        if (CSI->hasUnwindDest()) {
+          // Redirect preds to the unwind dest
+          CatchSwitchBB->replaceAllUsesWith(CSI->getUnwindDest());
+        } else {
+          // Rewrite all preds to unwind to caller (or from invoke to call).
+          SmallVector<BasicBlock *, 8> EHPreds(predecessors(CatchSwitchBB));
+          for (BasicBlock *EHPred : EHPreds)
+            removeUnwindEdge(EHPred);
+        }
+        // The catchswitch is no longer reachable.
+        new UnreachableInst(CSI->getContext(), CSI);
+        CSI->eraseFromParent();
+        Changed = true;
+      }
     } else if (isa<CleanupReturnInst>(TI)) {
       new UnreachableInst(TI->getContext(), TI);
       TI->eraseFromParent();
       Changed = true;
     }
-    // TODO: We can remove a catchswitch if all it's catchpads end in
-    // unreachable.
   }
 
   // If this block is now dead, remove it.
   if (pred_empty(BB) &&
       BB != &BB->getParent()->getEntryBlock()) {
     // We know there are no successors, so just nuke the block.
     BB->eraseFromParent();
     return true;

test/Transforms/SimplifyCFG/empty-catchpad.ll

+; RUN: opt < %s -simplifycfg -S | FileCheck %s
+
+declare void @f()
+declare void @llvm.foo(i32) nounwind
+declare void @ProcessCLRException()
+
+define void @test1() personality void ()* @ProcessCLRException {
+entry:
+  invoke void @f()
+    to label %exit unwind label %exn.dispatch
+exn.dispatch:
+  %cs = catchswitch within none [label %pad1, label %pad2] unwind to caller
+pad1:
+  %cp1 = catchpad within %cs [i32 1]
+  call void @llvm.foo(i32 1)
+  catchret from %cp1 to label %exit
+pad2:
+  %cp2 = catchpad within %cs [i32 2]
+  unreachable
+exit:
+  ret void
+}
+; Remove unreachble catch2, leave catch1 as-is
+; CHECK-LABEL: define void @test1()
+; CHECK: %cs = catchswitch within none [label %pad1] unwind to caller
+; CHECK-NOT: catchpad
+; CHECK: %cp1 = catchpad within %cs [i32 1]
+; CHECK-NOT: catchpad
+
+; Remove both catchpads and the catchswitch from exn.dispatch
+; CHECK-LABEL: define void @test2()
+define void @test2() personality void ()* @ProcessCLRException {
+entry:
+  invoke void @f()
+    to label %via.cleanup unwind label %exn.dispatch
+  ; CHECK-NOT: invoke
+  ; CHECK: call void @f()
+via.cleanup:
+  invoke void @f()
+    to label %via.catchswitch unwind label %cleanup.inner
+cleanup.inner:
+  %cp.inner = cleanuppad within none []
+  call void @llvm.foo(i32 0)
+  cleanupret from %cp.inner unwind label %exn.dispatch
+  ; CHECK: cleanupret from %cp.inner unwind to caller
+via.catchswitch:
+  invoke void @f()
+    to label %exit unwind label %dispatch.inner
+dispatch.inner:
+  %cs.inner = catchswitch within none [label %pad.inner] unwind label %exn.dispatch
+  ; CHECK: %cs.inner = catchswitch within none [label %pad.inner] unwind to caller
+pad.inner:
+  %catch.inner = catchpad within %cs.inner [i32 0]
+  ; CHECK: %catch.inner = catchpad within %cs.inner
+  call void @llvm.foo(i32 1)
+  catchret from %catch.inner to label %exit
+exn.dispatch:
+  %cs = catchswitch within none [label %pad1, label %pad2] unwind to caller
+  ; CHECK-NOT: catchswitch within
+  ; CHECK-NOT: catchpad
+pad1:
+  catchpad within %cs [i32 1]
+  unreachable
+pad2:
+  catchpad within %cs [i32 2]
+  unreachable
+exit:
+  ret void
+}
+
+; Same as @test2, but exn.dispatch catchswitch has an unwind dest that
+; preds need to be reidrected to
+; CHECK-LABEL: define void @test3()
+define void @test3() personality void ()* @ProcessCLRException {
+entry:
+  invoke void @f()
+    to label %via.cleanup unwind label %exn.dispatch
+  ; CHECK: invoke void @f()
+  ; CHECK-NEXT: to label %via.cleanup unwind label %cleanup
+via.cleanup:
+  invoke void @f()
+    to label %via.catchswitch unwind label %cleanup.inner
+cleanup.inner:
+  %cp.inner = cleanuppad within none []
+  call void @llvm.foo(i32 0)
+  cleanupret from %cp.inner unwind label %exn.dispatch
+  ; CHECK: cleanupret from %cp.inner unwind label %cleanup
+via.catchswitch:
+  invoke void @f()
+    to label %exit unwind label %dispatch.inner
+dispatch.inner:
+  %cs.inner = catchswitch within none [label %pad.inner] unwind label %exn.dispatch
+  ; CHECK: %cs.inner = catchswitch within none [label %pad.inner] unwind label %cleanup
+pad.inner:
+  %catch.inner = catchpad within %cs.inner [i32 0]
+  ; CHECK: %catch.inner = catchpad within %cs.inner
+  call void @llvm.foo(i32 1)
+  catchret from %catch.inner to label %exit
+exn.dispatch:
+  %cs = catchswitch within none [label %pad1, label %pad2] unwind label %cleanup
+  ; CHECK-NOT: catchswitch within
+  ; CHECK-NOT: catchpad
+pad1:
+  catchpad within %cs [i32 1]
+  unreachable
+pad2:
+  catchpad within %cs [i32 2]
+  unreachable
+cleanup:
+  %cp = cleanuppad within none []
+  call void @llvm.foo(i32 0)
+  cleanupret from %cp unwind to caller
+exit:
+  ret void
+}