[WinEH] Teach SimplfyCFG to eliminate empty cleanup pads.

[andrew.w.kaylor]

Summary

These changes introduce a new routine in SimplifyCFG to eliminate trivially empty cleanup pads from the exception handling chain.

There are a couple of places where it seemed like this could benefit from refactoring, but it seemed best for review purposes to simply note that and follow up after discussion of the basic implementation.

I also am making no attempt to handle PHI nodes. It seems unlikely that anything would put a PHI node at the top of an empty cleanup pad, but I don't know of anything that prevents it. This may need to be addressed later. Similarly, I think it's possible, but unlikely, for a lifetime intrinsic to appear in an otherwise empty cleanup pad.

[JosephTremoulet]

It seems unlikely that anything would put a PHI node at the top of an empty cleanup pad

What about something like

struct S { public: ~S() { } };
int foo() {
  int state = 1;
  try {
    S destructible;
    may_throw();
    state = 2;
    may_throw();
    // cleanup for S inserted here, which could be empty after inlining; wouldn't it get a phi for state?
  } catch (...) {
    return state;
  }
  return 0;
}

?

There are a couple of places where it seemed like this could benefit from refactoring, but it seemed best for review purposes to simply note that and follow up after discussion of the basic implementation.

I agree. Even in this same file, SimplifyUnreachable has redundant code for rewriting invoke -> call and probably should be extended to handle the EH pad -> 'unwind to caller' rewrites, and there's (going to be) a spot in WinEHPrepare where it would be useful to invoke this as a utility (see http://reviews.llvm.org/D12433#inline-100516 ).

lib/Transforms/Utils/SimplifyCFG.cpp

2965

Cleanups can have internal control flow, so this cast could fail. Presumably you want a dyn_cast and return false if it returns nullptr, since that would indicate a non-empty cleanup? (I'm not sure if this routine should be assuming that trivial flow will have already been removed or not)

test/Transforms/SimplifyCFG/empty-cleanuppad.ll

71–73

Should the CHECK-NOT follow the two CHECKs here instead of preceding them? In the input the cleanup comes after the catchendpad.

[andrew.w.kaylor]

What about something like <snip> ?

Yeah, that does it. I guess I need to add support for that now.

lib/Transforms/Utils/SimplifyCFG.cpp

2965

Oops. I actually had the dyn_cast in there and then I removed it this morning as I was doing final cleanup of this code. That's what I get for trying to doing something before the morning caffeine kicks in.

test/Transforms/SimplifyCFG/empty-cleanuppad.ll

71–73

In this case the first cleanuppad sticks around and the one below the catchpad/catchret is removed, but I do still have this line misplaced. It should be below the catchendpad.

[rnk]

lib/Transforms/Utils/SimplifyCFG.cpp

2903–2904

We usually drop these kinds of utilities in llvm/lib/Transforms/Utils/Local.cpp. You can make llvm/Transforms/Utils/LowerInvoke.cpp use it too.

2906

2-space indent

[andrew.w.kaylor]

Addressed minor comments from previous reviews.
Added support for sinking PHI nodes.
Refactoring is still TBD.

[JosephTremoulet]

lib/Transforms/Utils/SimplifyCFG.cpp

3056–3122

assert seems too strong here. Any PHI in an empty unwinds-to-caller cleanuppad must be dead (have no uses), but it would still be legal IR, right? I'd think that in the unwinds-to-caller case this should simply erase any PHIs it finds.

3069–3070

It could be a non-PHI value that dominates the empty cleanup, though, couldn't it? So something like

struct S { ... }; // has empty destructor
void foo() {
  int state = bar();
  try {
    {
      S s;
      may_throw();
    } // empty cleanup for s here
    state = 2;
    may_throw();
  } catch (...) {
    // This is UnwindDest and should have a PHI for state where IncomingBlock is the empty cleanuppad
    // and IncomingValue is the call to bar, not a PHI in the empty cleanup.
    code;
  }
}

or with a constant:

struct S { ... }; // has empty destructor
void foo() {
  int state = 1;
  try {
    {
      S s;
      may_throw();
    } // empty cleanup for s here
    state = 2;
    may_throw();
  } catch (...) {
    // This is UnwindDest and should have a PHI for state where IncomingBlock is the empty cleanuppad
    // and IncomingValue is 1, not a PHI in the empty cleanup
    code;
  }
}

Happily, I think in these cases you can just take the current incoming value in DestPN and associate it with UnwindDest's new predecessors.

3077–3080

I don't think the destination PHI node can already have an entry for this block:

• SrcPN was a PHI in a cleanuppad, so SrcPN->getIncomingBlock(SrcIdx) must have reached the cleanuppad by an unwind edge
• DestPN is in UnwindDest, which must be an EH pad and therefore all its predecessors must reach UnwindDest by an unwind edge
• No instruction has multiple unwind edges, so nothing could have unwind edges to both UnwindDest and the empty cleanup

3085

I think it's possible that SrcPN could have another use on another PHI in UnwindDest, and/or that it could have a non-PHI use. So I don't think you want to erase it here, I think instead you want the loop below to check if it has any uses and erase it if not.

Actually, you may want to move the loop below outside the if(UnwindDest) and let it be the thing that erases useless PHIs when the empty cleanup unwinds to caller.

3100

Likewise, I think the getBasicBlockIndex check here is superfluous.

[andrew.w.kaylor]

lib/Transforms/Utils/SimplifyCFG.cpp

3056–3122

I suppose you're right. I think I can handle that just by replacing the assert with a comment. The unused PHI's should go away when we remove the block. Alternatively, I could add something to go through any PHI's and assert that they have no uses.

3069–3070

Good catch. I was just thinking it couldn't be a non-PHI value in the empty cleanup pad block. I think you're right that this should be easy to handle.

3077–3080

Alright, that seems like sound reasoning to me.

3085

OK.

3100

I'm assuming "likewise" here is referring to your comments at line 3069. So you're saying that any predecessor of the unwindpad we're removing could not also have been a predecessor of UnwindDest., right?

So, any PHINode that was present in the cleanuppad block we are removing must necessarily have undefined values for any other predecessor of UnwindDest. That sounds correct. Am I correct in thinking that because the PHI value from BB could not have been used in the pre-optimized control flow there must be something (a PHI-dependent branch, perhaps) still in place that will prevent the undef value being inserted here from being referenced?

[JosephTremoulet]

lib/Transforms/Utils/SimplifyCFG.cpp

3056–3122

The unused PHI's should go away when we remove the block.

Oh, I didn't know it worked like that. Feel free to ignore my suggestion to explicitly remove them then.

3100

So you're saying that any predecessor of the unwindpad we're removing could not also have been a predecessor of UnwindDest., right?

right.

Am I correct in thinking that because the PHI value from BB could not have been used in the pre-optimized control flow there must be something (a PHI-dependent branch, perhaps) still in place that will prevent the undef value being inserted here from being referenced?

Trying to come up with a justification for that claim, I instead convinced myself that you should actually be using the PHI itself as the incoming value, rather than undef:
You'll only insert a new incoming value if UnwindDest had some predecessor other than the empty cleanup.

1. If the empty cleanup didn't dominate that other predecessor, then:
   • the empty cleanup (where the PHI used to be) can't dominate anything reachable from UnwindDest
   • then since UnwindDest was the empty cleanup's only successor, that means the empty cleanup didn't dominate anything but itself
   • and since the empty cleanup was empty, there weren't any uses there.
   • so in this case, the only place where the empty cleanup PHI could have had a use (because defs have to dominate uses) is a PHI in UnwindDef.
   • but if there was already a PHI in UnwindDef then it already had values for the other predecessors, so this isn't a case where you'll be inserting a new incoming value here.
   • so case 1 is contradictory and impossible.
2. If the empty cleanup did dominate that other predecessor, then
   1. if the other predecessor is unreachable, then it doesn't really matter what you put there
   2. if the other predecessor is reachable, then its unwind edge is a back-edge, and since the original PHI wouldn't have changed value around that back-edge we need the new PHI to preserve its value around that back-edge.

So the only possible case is 2b, and the PHI needs a self-reference on the backedge. I don't think we can get that from C++ because it would have to look something like this and the 'goto' there is illegal:

struct S { ~S() { } };

void may_throw();
void use(int);

void foo() {
  int x = 1;
  try {
    {
      S s;
      may_throw();
      x = 2;
      may_throw();
    } // empty cleanup for S with phi for x here
    return;
  loop_bottom:
    may_throw();
    return;
  } catch (...) {
    // predecessors are the empty cleanup and loop_bottom
    // no phi here before optimization
    // phi for x will be moved here by optimization
    use(x); // use of the phi that gets moved
  }
  goto loop_bottom;
}

but at the LLVM IR level I don't see anything that would prohibit someone from creating

  define void foo() personality whatever {
entry:
    invoke void may_throw()
      to label %invoke.cont unwind label %cleanup
invoke.cont:
    invoke void may_throw()
      to label %exit unwind label %cleanup
cleanup:
  %x = PHI i32 [ 1, %entry ], [ 2, %invoke.cont ]
  %clean = cleanuppad []
  cleanupret %clean unwind label %catch
catch:
  %cat = catchpad []
      to label %do_catch unwind label %endcatch
do_catch:
  call void use(i32 %x)
  catchret %cat to label %loop_bottom
loop_bottom:
  invoke void f()
    to label %exit unwind label %catch
endcatch:
  catchendpad unwind to caller
exit:
  ret void
  }

[andrew.w.kaylor]

lib/Transforms/Utils/SimplifyCFG.cpp

3100

It turns out that by this point I've already updated the terminators for BB's predecessors so they are included in this loop. This check is necessary to distinguish between blocks that previous unwound to BB (and thus already have an entry in the PHI node that we are sinking) and blocks that unwound to UnwindDest even before the transformation (and thus need an undef entry in the PHI node we are sinking).

[JosephTremoulet]

lib/Transforms/Utils/SimplifyCFG.cpp

3100

It turns out that by this point I've already updated the terminators for BB's predecessors so they are included in this loop

Oh, I see. I think it would be good to avoid foreach(pred : ...) { PN->getBasicBlockIndex(pred) here if you can; it's quadratic and I'm certain to run into cases with EH pads that have several hundred preds. What would you think about swapping the order and doing the phi rewrite before the terminator rewrite?

[JosephTremoulet]

lib/Transforms/Utils/SimplifyCFG.cpp

3100

I'd think that jump threading could turn something like

struct S { ~S() { } };

void may_throw();
void use(int);

void foo() {
  int x = 1;
  bool doStuff = true;
  do {
   // phis for x and doStuff here
    try {
      // branch on doStuff phi that JumpThreading should be interested in, removing above phi on x
      if (doStuff) {
        S s;
        may_throw();
        x = 2;
        may_throw();
        // empty cleanup for S with phi for x here (incoming values are the loop-head phi and 2, but after jump-threading could be 1 and 2)
        return;
      }
      may_throw();
      return;
    } catch (...) {
      // phi here merging the loop-head phi with the empty-cleanup phi
      // after jump-threading this phi can be removed and have its use replaced with the empty-cleanup phi
      use(x);
    }
    doStuff = false;
  } while (true);
}

(which is legal C++) into the above pattern.

[andrew.w.kaylor]

Update PHI handling.
Add new test case.

[JosephTremoulet]

LGTM with one nit, thanks.

lib/Transforms/Utils/SimplifyCFG.cpp

2993–2995

Looks like this doesn't need to be a loop anymore, and you can just have unsigned Idx = DestPN->getBasicBlockIndex(BB)

[andrew.w.kaylor]

Eliminated redundant loop in PHI handling

Any objections to my committing this as is and doing the proposed refactoring as part of a separate change set?

[JosephTremoulet]

One last nit.

Any objections to my committing this as is and doing the proposed refactoring as part of a separate change set?

No, that plan sounds good. In fact I checked in rL246751 with some code at line 3314 in WinEHPrepare.cpp that rewrites cleanupendpads as unreachable but instead ought to be calling this helper that the refactoring will create to change its predecessors to 'unwind to caller' (or from invoke to call).

lib/Transforms/Utils/SimplifyCFG.cpp

3046

I'm pretty sure you could assert Idx != -1; DestPN is a PHI node in block UnwindDest, which must have BB as a predecessor because it is the ->getUnwindDest() of BB's terminator.

lib/Transforms/Utils/SimplifyCFG.cpp

class SimplifyCFGOpt {
   bool SimplifyEqualityComparisonWithOnlyPredecessor(TerminatorInst *TI,
                                                      BasicBlock *Pred,
                                                      IRBuilder<> &Builder);
   bool FoldValueComparisonIntoPredecessors(TerminatorInst *TI,
                                            IRBuilder<> &Builder);
 
   bool SimplifyReturn(ReturnInst *RI, IRBuilder<> &Builder);
   bool SimplifyResume(ResumeInst *RI, IRBuilder<> &Builder);
+  bool SimplifyCleanupReturn(CleanupReturnInst *RI);
   bool SimplifyUnreachable(UnreachableInst *UI);
   bool SimplifySwitch(SwitchInst *SI, IRBuilder<> &Builder);
   bool SimplifyIndirectBr(IndirectBrInst *IBI);
   bool SimplifyUncondBranch(BranchInst *BI, IRBuilder <> &Builder);
   bool SimplifyCondBranch(BranchInst *BI, IRBuilder <>&Builder);
 
 public:
   SimplifyCFGOpt(const TargetTransformInfo &TTI, const DataLayout &DL,
static bool SimplifyBranchOnICmpChain(BranchInst *BI, IRBuilder<> &Builder,
 
   // Erase the old branch instruction.
   EraseTerminatorInstAndDCECond(BI);
 
   DEBUG(dbgs() << "  ** 'icmp' chain result is:\n" << *BB << '\n');
   return true;
 }
 
+// FIXME: This seems like a pretty common thing to want to do.  Consider
+// whether there is a more accessible place to put this.
+static void convertInvokeToCall(InvokeInst *II) {
+  SmallVector<Value*, 8> Args(II->op_begin(), II->op_end() - 3);
+  // Insert a call instruction before the invoke.
+  CallInst *Call = CallInst::Create(II->getCalledValue(), Args, "", II);
+  Call->takeName(II);
+  Call->setCallingConv(II->getCallingConv());
+  Call->setAttributes(II->getAttributes());
+  Call->setDebugLoc(II->getDebugLoc());
+
+  // Anything that used the value produced by the invoke instruction now uses
+  // the value produced by the call instruction.  Note that we do this even
+  // for void functions and calls with no uses so that the callgraph edge is
+  // updated.
+  II->replaceAllUsesWith(Call);
+  II->getUnwindDest()->removePredecessor(II->getParent());
+
+  // Insert a branch to the normal destination right before the invoke.
+  BranchInst::Create(II->getNormalDest(), II);
+
+  // Finally, delete the invoke instruction!
+  II->eraseFromParent();
+}
+
 bool SimplifyCFGOpt::SimplifyResume(ResumeInst *RI, IRBuilder<> &Builder) {
   // If this is a trivial landing pad that just continues unwinding the caught
   // exception then zap the landing pad, turning its invokes into calls.
   BasicBlock *BB = RI->getParent();
   LandingPadInst *LPInst = dyn_cast<LandingPadInst>(BB->getFirstNonPHI());
   if (RI->getValue() != LPInst)
     // Not a landing pad, or the resume is not unwinding the exception that
     // caused control to branch here.
     return false;
 
   // Check that there are no other instructions except for debug intrinsics.
   BasicBlock::iterator I = LPInst, E = RI;
   while (++I != E)
     if (!isa<DbgInfoIntrinsic>(I))
       return false;
 
   // Turn all invokes that unwind here into calls and delete the basic block.
   for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB); PI != PE;) {
     InvokeInst *II = cast<InvokeInst>((*PI++)->getTerminator());
-    SmallVector<Value*, 8> Args(II->op_begin(), II->op_end() - 3);
-    // Insert a call instruction before the invoke.
-    CallInst *Call = CallInst::Create(II->getCalledValue(), Args, "", II);
-    Call->takeName(II);
-    Call->setCallingConv(II->getCallingConv());
-    Call->setAttributes(II->getAttributes());
-    Call->setDebugLoc(II->getDebugLoc());
+    convertInvokeToCall(II);
+  }
 
-    // Anything that used the value produced by the invoke instruction now uses
-    // the value produced by the call instruction.  Note that we do this even
-    // for void functions and calls with no uses so that the callgraph edge is
-    // updated.
-    II->replaceAllUsesWith(Call);
-    BB->removePredecessor(II->getParent());
+  // The landingpad is now unreachable.  Zap it.
+  BB->eraseFromParent();
+  return true;
+}
 
-    // Insert a branch to the normal destination right before the invoke.
-    BranchInst::Create(II->getNormalDest(), II);
+bool SimplifyCFGOpt::SimplifyCleanupReturn(CleanupReturnInst *RI) {
+  // If this is a trivial cleanup pad that executes no instructions, it can be
+  // eliminated.  If the cleanup pad continues to the caller, any predecessor
+  // that is an EH pad will be updated to continue to the caller and any
+  // predecessor that terminates with an invoke instruction will have its invoke
+  // instruction converted to a call instruction.  If the cleanup pad being
+  // simplified does not continue to the caller, each predecessor will be
+  // updated to continue to the unwind destination of the cleanup pad being
+  // simplified.
+  BasicBlock *BB = RI->getParent();
+  Instruction *CPInst = dyn_cast<CleanupPadInst>(BB->getFirstNonPHI());
+  if (!CPInst)
+    // This isn't an empty cleanup.
+    return false;
 
-    // Finally, delete the invoke instruction!
-    II->eraseFromParent();
+  // Check that there are no other instructions except for debug intrinsics.
+  BasicBlock::iterator I = CPInst, E = RI;
+  while (++I != E)
+    if (!isa<DbgInfoIntrinsic>(I))
+      return false;
+
+  // If the cleanup return we are simplifying unwinds to the caller, this
+  // will set UnwindDest to nullptr.
+  BasicBlock *UnwindDest = RI->getUnwindDest();
+
+  // We're about to remove BB from the control flow.  Before we do, sink any
+  // PHINodes into the unwind destination.  Doing this before changing the
+  // control flow avoids some potentially slow checks, since we can currently
+  // be certain that UnwindDest and BB have no common predecessors (since they
+  // are both EH pads).
+  if (UnwindDest) {
+    // First, go through the PHI nodes in UnwindDest and update any nodes that
+    // reference the block we are removing
+    for (BasicBlock::iterator I = UnwindDest->begin(), 
+           IE = UnwindDest->getFirstNonPHI();
+         I != IE; ++I) {
+      PHINode *DestPN = cast<PHINode>(I);
+ 
+      for (unsigned Idx = 0, E = DestPN->getNumIncomingValues(); Idx != E;
+           ++Idx) {
+        if (DestPN->getIncomingBlock(Idx) == BB) {
+          // This PHI node has an incoming value that corresponds to a control
+          // path through the cleanup pad we are removing.  If the incoming
+          // value is in the cleanup pad, it must be a PHINode (because we
+          // verified above that the block is otherwise empty).  Otherwise, the
+          // value is either a constant or a value that dominates the cleanup
+          // pad being removed.
+          //
+          // Because BB and UnwindDest are both EH pads, all of their
+          // predecessors must unwind to these blocks, and since no instruction
+          // can have multiple unwind destinations, there will be no overlap in
+          // incoming blocks between SrcPN and DestPN.
+          Value *SrcVal = DestPN->getIncomingValue(Idx);
+          PHINode *SrcPN = dyn_cast<PHINode>(SrcVal);
+
+          // Remove the entry for the block we are deleting.
+          DestPN->removeIncomingValue(Idx, false);
+
+          if (SrcPN && SrcPN->getParent() == BB)
+            // If the incoming value was a PHI node in the cleanup pad we are
+            // removing, we need to merge that PHI node's incoming values into
+            // DestPN.
+            for (unsigned SrcIdx = 0, SrcE = SrcPN->getNumIncomingValues(); 
+                 SrcIdx != SrcE; ++SrcIdx)
+              DestPN->addIncoming(SrcPN->getIncomingValue(SrcIdx),
+                                  SrcPN->getIncomingBlock(SrcIdx));
+          else
+            // Otherwise, the incoming value came from above BB and
+            // so we can just reuse it.  We must associate all of BB's
+            // predecessors with this value.
+            for (auto *pred : predecessors(BB))
+              DestPN->addIncoming(SrcVal, pred);
+
+          break;
+        }
+      }
     }
 
-  // The landingpad is now unreachable.  Zap it.
+    // Sink any remaining PHI nodes directly into UnwindDest.
+    Instruction *InsertPt = UnwindDest->getFirstNonPHI();
+    for (BasicBlock::iterator I = BB->begin(), IE = BB->getFirstNonPHI();
+         I != IE;) {
+      // The iterator must be incremented here because the instructions are
+      // being moved to another block.
+      PHINode *PN = cast<PHINode>(I++);
+      if (PN->use_empty())
+        // If the PHI node has no uses, just leave it.  It will be erased
+        // when we erase BB below.
+        continue;
+
+      // Otherwise, sink this PHI node into UnwindDest.
+      // Any predecessors to UnwindDest which are not already represented
+      // must be back edges which inherit the value from the path through
+      // BB.  In this case, the PHI value must reference itself.
+      for (auto *pred : predecessors(UnwindDest))
+        if (pred != BB)
+          PN->addIncoming(PN, pred);
+      PN->moveBefore(InsertPt);
+    }
+  }
+
+  for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB); PI != PE;) {
+    // The iterator must be updated here because we are removing this pred.
+    BasicBlock *PredBB = *PI++;
+    TerminatorInst *TI = PredBB->getTerminator();
+    if (UnwindDest == nullptr) {
+      if (auto *II = dyn_cast<InvokeInst>(TI)) {
+        // The cleanup return being simplified continues to the caller and this
+        // predecessor terminated with an invoke instruction.  Convert the
+        // invoke to a call.
+        // This call updates the predecessor/successor chain.
+        convertInvokeToCall(II);
+      } else {
+        // In the remaining cases the predecessor's terminator unwinds to the
+        // block we are removing.  We need to create a new instruction that
+        // unwinds to the caller.  Simply setting the unwind destination to
+        // nullptr would leave the objects internal data in an inconsistent
+        // state.
+        // FIXME: Consider whether it is better to update setUnwindDest to
+        //        keep things consistent.
+        if (auto *CRI = dyn_cast<CleanupReturnInst>(TI)) {
+          auto *NewCRI = CleanupReturnInst::Create(CRI->getCleanupPad(),
+                                                   nullptr, CRI);
+          NewCRI->takeName(CRI);
+          NewCRI->setDebugLoc(CRI->getDebugLoc());
+          CRI->eraseFromParent();
+        } else if (auto *CEP = dyn_cast<CatchEndPadInst>(TI)) {
+          auto *NewCEP = CatchEndPadInst::Create(CEP->getContext(), nullptr,
+                                                 CEP);
+          NewCEP->takeName(CEP);
+          NewCEP->setDebugLoc(CEP->getDebugLoc());
+          CEP->eraseFromParent();
+        } else if (auto *TPI = dyn_cast<TerminatePadInst>(TI)) {
+          SmallVector<Value *, 3> TerminatePadArgs;
+          for (Value *Operand : TPI->arg_operands())
+            TerminatePadArgs.push_back(Operand);
+          auto *NewTPI = TerminatePadInst::Create(TPI->getContext(), nullptr,
+                                                  TerminatePadArgs, TPI);
+          NewTPI->takeName(TPI);
+          NewTPI->setDebugLoc(TPI->getDebugLoc());
+          TPI->eraseFromParent();
+        } else if (auto *CPI = dyn_cast<CatchPadInst>(TI)) {
+          llvm_unreachable("A catchpad may not unwind to a cleanuppad.");
+        } else {
+          llvm_unreachable("Unexpected predecessor to cleanup pad.");
+        }
+      }
+    } else {
+      // If the predecessor did not terminate with an invoke instruction, it
+      // must be some variety of EH pad.
+      TerminatorInst *TI = PredBB->getTerminator();
+      // FIXME: Introducing an EH terminator base class would simplify this.
+      if (auto *II = dyn_cast<InvokeInst>(TI))
+        II->setUnwindDest(UnwindDest);
+      else if (auto *CRI = dyn_cast<CleanupReturnInst>(TI))
+        CRI->setUnwindDest(UnwindDest);
+      else if (auto *CEP = dyn_cast<CatchEndPadInst>(TI))
+        CEP->setUnwindDest(UnwindDest);
+      else if (auto *TPI = dyn_cast<TerminatePadInst>(TI))
+        TPI->setUnwindDest(UnwindDest);
+      else if (auto *CPI = dyn_cast<CatchPadInst>(TI))
+        llvm_unreachable("A catchpad may not unwind to a cleanuppad.");
+      else
+        llvm_unreachable("Unexpected predecessor to cleanup pad.");
+    }
+  }
+
+  // The cleanup pad is now unreachable.  Zap it.
   BB->eraseFromParent();
   return true;
 }
 
 bool SimplifyCFGOpt::SimplifyReturn(ReturnInst *RI, IRBuilder<> &Builder) {
   BasicBlock *BB = RI->getParent();
   if (!BB->getFirstNonPHIOrDbg()->isTerminator()) return false;
 
if (BI->isUnconditional()) {
       if (SimplifyUncondBranch(BI, Builder)) return true;
     } else {
       if (SimplifyCondBranch(BI, Builder)) return true;
     }
   } else if (ReturnInst *RI = dyn_cast<ReturnInst>(BB->getTerminator())) {
     if (SimplifyReturn(RI, Builder)) return true;
   } else if (ResumeInst *RI = dyn_cast<ResumeInst>(BB->getTerminator())) {
     if (SimplifyResume(RI, Builder)) return true;
+  } else if (CleanupReturnInst *RI =
+               dyn_cast<CleanupReturnInst>(BB->getTerminator())) {
+    if (SimplifyCleanupReturn(RI)) return true;
   } else if (SwitchInst *SI = dyn_cast<SwitchInst>(BB->getTerminator())) {
     if (SimplifySwitch(SI, Builder)) return true;
   } else if (UnreachableInst *UI =
                dyn_cast<UnreachableInst>(BB->getTerminator())) {
     if (SimplifyUnreachable(UI)) return true;
   } else if (IndirectBrInst *IBI =
                dyn_cast<IndirectBrInst>(BB->getTerminator())) {
     if (SimplifyIndirectBr(IBI)) return true;

test/Transforms/SimplifyCFG/empty-cleanuppad.ll

+; RUN: opt < %s -simplifycfg -S | filecheck %s
+
+; ModuleID = 'cppeh-simplify.cpp'
+target datalayout = "e-m:w-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-pc-windows-msvc18.0.0"
+
+
+; This case arises when two objects with empty destructors are cleaned up.
+;
+; void f1() { 
+;   S a;
+;   S b;
+;   g(); 
+; }
+;
+; In this case, both cleanup pads can be eliminated and the invoke can be
+; converted to a call.
+;
+; CHECK: define void @f1()
+; CHECK: entry:
+; CHECK:   call void @g()
+; CHECK:   ret void
+; CHECK-NOT: cleanuppad
+; CHECK: }
+;
+define void @f1() personality i8* bitcast (i32 (...)* @__CxxFrameHandler3 to i8*) {
+entry:
+  invoke void @g() to label %invoke.cont unwind label %ehcleanup
+
+invoke.cont:                                      ; preds = %entry
+  ret void
+
+ehcleanup:                                        ; preds = %entry
+  %0 = cleanuppad []
+  cleanupret %0 unwind label %ehcleanup.1
+
+ehcleanup.1:                                      ; preds = %ehcleanup
+  %1 = cleanuppad []
+  cleanupret %1 unwind to caller
+}
+
+
+; This case arises when an object with an empty destructor must be cleaned up
+; outside of a try-block and an object with a non-empty destructor must be
+; cleaned up within the try-block.
+;
+; void f2() { 
+;   S a;
+;   try {
+;     S2 b;
+;     g();
+;   } catch (...) {}
+; }
+;
+; In this case, the outermost cleanup pad can be eliminated and the catch block
+; should unwind to the caller (that is, exception handling continues with the
+; parent frame of the caller).
+;
+; CHECK: define void @f2()
+; CHECK: entry:
+; CHECK:   invoke void @g()
+; CHECK: ehcleanup:
+; CHECK:   cleanuppad
+; CHECK:   call void @"\01??1S2@@QEAA@XZ"(%struct.S2* %b)
+; CHECK:   cleanupret %0 unwind label %catch.dispatch
+; CHECK: catch.dispatch:
+; CHECK:   catchpad
+; CHECK: catch:
+; CHECK:   catchret
+; CHECK: catchendblock:                                    ; preds = %catch.dispatch
+; CHECK:   catchendpad unwind to caller
+; CHECK-NOT: cleanuppad
+; CHECK: }
+;
+define void @f2() personality i8* bitcast (i32 (...)* @__CxxFrameHandler3 to i8*) {
+entry:
+  %b = alloca %struct.S2, align 1
+  invoke void @g() to label %invoke.cont unwind label %ehcleanup
+
+invoke.cont:                                      ; preds = %entry
+  br label %try.cont
+
+ehcleanup:                                        ; preds = %entry
+  %0 = cleanuppad []
+  call void @"\01??1S2@@QEAA@XZ"(%struct.S2* %b)
+  cleanupret %0 unwind label %catch.dispatch
+
+catch.dispatch:                                   ; preds = %ehcleanup
+  %1 = catchpad [i8* null, i8* null] to label %catch unwind label %catchendblock
+
+catch:                                            ; preds = %catch.dispatch
+  catchret %1 to label %catchret.dest
+
+catchret.dest:                                    ; preds = %catch
+  br label %try.cont
+
+try.cont:                                         ; preds = %catchret.dest, %invoke.cont
+  ret void
+
+catchendblock:                                    ; preds = %catch.dispatch
+  catchendpad unwind label %ehcleanup.1
+
+ehcleanup.1:                                      ; preds = %catchendblock
+  %2 = cleanuppad []
+  cleanupret %2 unwind to caller
+}
+
+
+; This case arises when an object with a non-empty destructor must be cleaned up
+; outside of a try-block and an object with an empty destructor must be cleaned
+; within the try-block.
+;
+; void f3() { 
+;   S2 a;
+;   try {
+;     S b;
+;     g();
+;   } catch (...) {}
+; }
+;
+; In this case the inner cleanup pad should be eliminated and the invoke of g()
+; should unwind directly to the catchpad.
+;
+; CHECK: define void @f3()
+; CHECK: entry:
+; CHECK:   invoke void @g()
+; CHECK:           to label %try.cont unwind label %catch.dispatch
+; CHECK: catch.dispatch:
+; CHECK:   catchpad [i8* null, i8* null] to label %catch unwind label %catchendblock
+; CHECK: catch:
+; CHECK:   catchret
+; CHECK: catchendblock:
+; CHECK:   catchendpad unwind label %ehcleanup.1
+; CHECK: ehcleanup.1:
+; CHECK:   cleanuppad
+; CHECK:   call void @"\01??1S2@@QEAA@XZ"(%struct.S2* %a)
+; CHECK:   cleanupret %1 unwind to caller
+; CHECK: }
+;
+define void @f3() personality i8* bitcast (i32 (...)* @__CxxFrameHandler3 to i8*) {
+entry:
+  %a = alloca %struct.S2, align 1
+  invoke void @g() to label %invoke.cont unwind label %ehcleanup
+
+invoke.cont:                                      ; preds = %entry
+  br label %try.cont
+
+ehcleanup:                                        ; preds = %entry
+  %0 = cleanuppad []
+  cleanupret %0 unwind label %catch.dispatch
+
+catch.dispatch:                                   ; preds = %ehcleanup
+  %1 = catchpad [i8* null, i8* null] to label %catch unwind label %catchendblock
+
+catch:                                            ; preds = %catch.dispatch
+  catchret %1 to label %catchret.dest
+
+catchret.dest:                                    ; preds = %catch
+  br label %try.cont
+
+try.cont:                                         ; preds = %catchret.dest, %invoke.cont
+  ret void
+
+catchendblock:                                    ; preds = %catch.dispatch
+  catchendpad unwind label %ehcleanup.1
+
+ehcleanup.1:                                      ; preds = %catchendblock
+  %2 = cleanuppad []
+  call void @"\01??1S2@@QEAA@XZ"(%struct.S2* %a)
+  cleanupret %2 unwind to caller
+}
+
+
+; This case arises when an object with an empty destructor may require cleanup
+; from either inside or outside of a try-block.
+;
+; void f4() { 
+;   S a;
+;   g();
+;   try {
+;     g();
+;   } catch (...) {}
+; }
+;
+; In this case, the cleanuppad should be eliminated, the invoke outside of the
+; call block should be converted to a call and the catchendpad should unwind
+; to the caller (that is, that is, exception handling continues with the parent
+; frame of the caller).)
+;
+; CHECK: define void @f4()
+; CHECK: entry:
+; CHECK:   call void @g
+; Note: The cleanuppad simplification will insert an unconditional branch here
+;       but it will be eliminated, placing the following invoke in the entry BB. 
+; CHECK:   invoke void @g()
+; CHECK:           to label %try.cont unwind label %catch.dispatch
+; CHECK: catch.dispatch:
+; CHECK:   catchpad
+; CHECK: catch:
+; CHECK:   catchret
+; CHECK: catchendblock:
+; CHECK:   catchendpad unwind to caller
+; CHECK-NOT: cleanuppad
+; CHECK: }
+;
+define void @f4() personality i8* bitcast (i32 (...)* @__CxxFrameHandler3 to i8*) {
+entry:
+  invoke void @g()
+          to label %invoke.cont unwind label %ehcleanup
+
+invoke.cont:                                      ; preds = %entry
+  invoke void @g()
+          to label %try.cont unwind label %catch.dispatch
+
+catch.dispatch:                                   ; preds = %invoke.cont
+  %0 = catchpad [i8* null, i8* null] to label %catch unwind label %catchendblock
+
+catch:                                            ; preds = %catch.dispatch
+  catchret %0 to label %try.cont
+
+try.cont:                                         ; preds = %catch, %invoke.cont
+  ret void
+
+catchendblock:                                    ; preds = %catch.dispatch
+  catchendpad unwind label %ehcleanup
+
+ehcleanup:                                        ; preds = %catchendblock, %entry
+  %1 = cleanuppad []
+  cleanupret %1 unwind to caller
+}
+
+; This tests the case where a terminatepad unwinds to a cleanuppad.
+; I'm not sure how this case would arise, but it seems to be syntactically
+; legal so I'm testing it.
+;
+; CHECK: define void @f5()
+; CHECK: entry:
+; CHECK:   invoke void @g()
+; CHECK:           to label %try.cont unwind label %terminate
+; CHECK: terminate:
+; CHECK:   terminatepad [i7 4] unwind to caller
+; CHECK-NOT: cleanuppad
+; CHECK: try.cont:
+; CHECK:   invoke void @g()
+; CHECK:           to label %try.cont.1 unwind label %terminate.1
+; CHECK: terminate.1:
+; CHECK:   terminatepad [i7 4] unwind label %ehcleanup.2
+; CHECK-NOT: ehcleanup.1:
+; CHECK: ehcleanup.2:
+; CHECK:   [[TMP:\%.+]] = cleanuppad
+; CHECK:   call void @"\01??1S2@@QEAA@XZ"(%struct.S2* %a)
+; CHECK:   cleanupret [[TMP]] unwind to caller
+; CHECK: }
+define void @f5() personality i8* bitcast (i32 (...)* @__CxxFrameHandler3 to i8*) {
+entry:
+  %a = alloca %struct.S2, align 1
+  invoke void @g()
+          to label %try.cont unwind label %terminate
+
+terminate:                                        ; preds = %entry
+  terminatepad [i7 4] unwind label %ehcleanup
+
+ehcleanup:                                        ; preds = %terminate
+  %0 = cleanuppad []
+  cleanupret %0 unwind to caller
+
+try.cont:                                         ; preds = %entry
+  invoke void @g()
+          to label %try.cont.1 unwind label %terminate.1
+
+terminate.1:                                      ; preds = %try.cont
+  terminatepad [i7 4] unwind label %ehcleanup.1
+
+ehcleanup.1:                                      ; preds = %terminate.1
+  %1 = cleanuppad []
+  cleanupret %1 unwind label %ehcleanup.2
+
+ehcleanup.2:                                      ; preds = %ehcleanup.1
+  %2 = cleanuppad []
+  call void @"\01??1S2@@QEAA@XZ"(%struct.S2* %a)
+  cleanupret %2 unwind to caller
+
+try.cont.1:                                       ; preds = %try.cont
+  ret void
+}
+
+; This case tests simplification of an otherwise empty cleanup pad that contains
+; a PHI node.
+;
+; int f6() {
+;   int state = 1;
+;   try {
+;     S a;
+;     g();
+;     state = 2;
+;     g();
+;   } catch (...) {
+;     return state;
+;   }
+;   return 0;
+; }
+;
+; In this case, the cleanup pad should be eliminated and the PHI node in the
+; cleanup pad should be sunk into the catch dispatch block.
+;
+; CHECK: define i32 @f6()
+; CHECK: entry:
+; CHECK:   invoke void @g()
+; CHECK: invoke.cont:
+; CHECK:   invoke void @g()
+; CHECK-NOT: ehcleanup:
+; CHECK-NOT:   cleanuppad
+; CHECK: catch.dispatch:
+; CHECK:   %state.0 = phi i32 [ 2, %invoke.cont ], [ 1, %entry ]
+; CHECK: }
+define i32 @f6() personality i8* bitcast (i32 (...)* @__CxxFrameHandler3 to i8*) {
+entry:
+  invoke void @g()
+          to label %invoke.cont unwind label %ehcleanup
+
+invoke.cont:                                      ; preds = %entry
+  invoke void @g()
+          to label %return unwind label %ehcleanup
+
+ehcleanup:                                        ; preds = %invoke.cont, %entry
+  %state.0 = phi i32 [ 2, %invoke.cont ], [ 1, %entry ]
+  %0 = cleanuppad []
+  cleanupret %0 unwind label %catch.dispatch
+
+catch.dispatch:                                   ; preds = %ehcleanup
+  %1 = catchpad [i8* null, i8* null] to label %catch unwind label %catchendblock
+
+catch:                                            ; preds = %catch.dispatch
+  catchret %1 to label %return
+
+catchendblock:                                    ; preds = %catch.dispatch
+  catchendpad unwind to caller
+
+return:                                           ; preds = %invoke.cont, %catch
+  %retval.0 = phi i32 [ %state.0, %catch ], [ 0, %invoke.cont ]
+  ret i32 %retval.0
+}
+
+; This case tests another variation of simplification of an otherwise empty
+; cleanup pad that contains a PHI node.
+;
+; int f7() {
+;   int state = 1;
+;   try {
+;     g();
+;     state = 2;
+;     S a;
+;     g();
+;     state = 3;
+;     g();
+;   } catch (...) {
+;     return state;
+;   }
+;   return 0;
+; }
+;
+; In this case, the cleanup pad should be eliminated and the PHI node in the
+; cleanup pad should be merged with the PHI node in the catch dispatch block.
+;
+; CHECK: define i32 @f7()
+; CHECK: entry:
+; CHECK:   invoke void @g()
+; CHECK: invoke.cont:
+; CHECK:   invoke void @g()
+; CHECK: invoke.cont.1:
+; CHECK:   invoke void @g()
+; CHECK-NOT: ehcleanup:
+; CHECK-NOT:   cleanuppad
+; CHECK: catch.dispatch:
+; CHECK:   %state.1 = phi i32 [ 1, %entry ], [ 3, %invoke.cont.1 ], [ 2, %invoke.cont ]
+; CHECK: }
+define i32 @f7() personality i8* bitcast (i32 (...)* @__CxxFrameHandler3 to i8*) {
+entry:
+  invoke void @g()
+          to label %invoke.cont unwind label %catch.dispatch
+
+invoke.cont:                                      ; preds = %entry
+  invoke void @g()
+          to label %invoke.cont.1 unwind label %ehcleanup
+
+invoke.cont.1:                                    ; preds = %invoke.cont
+  invoke void @g()
+          to label %return unwind label %ehcleanup
+
+ehcleanup:                                        ; preds = %invoke.cont.1, %invoke.cont
+  %state.0 = phi i32 [ 3, %invoke.cont.1 ], [ 2, %invoke.cont ]
+  %0 = cleanuppad []
+  cleanupret %0 unwind label %catch.dispatch
+
+catch.dispatch:                                   ; preds = %ehcleanup, %entry
+  %state.1 = phi i32 [ %state.0, %ehcleanup ], [ 1, %entry ]
+  %1 = catchpad [i8* null, i8* null] to label %catch unwind label %catchendblock
+
+catch:                                            ; preds = %catch.dispatch
+  catchret %1 to label %return
+
+catchendblock:                                    ; preds = %catch.dispatch
+  catchendpad unwind to caller
+
+return:                                           ; preds = %invoke.cont.1, %catch
+  %retval.0 = phi i32 [ %state.1, %catch ], [ 0, %invoke.cont.1 ]
+  ret i32 %retval.0
+}
+
+; This case tests a scenario where an empty cleanup pad is not dominated by all
+; of the predecessors of its successor, but the successor references a PHI node
+; in the empty cleanup pad.
+;
+; Conceptually, the case being modeled is something like this:
+;
+; int f8() {
+;   int x = 1;
+;   try {
+;     S a;
+;     g();
+;     x = 2;
+; retry:
+;     g();
+;     return
+;   } catch (...) {
+;     use_x(x);
+;   }
+;   goto retry;
+; }
+;
+; While that C++ syntax isn't legal, the IR below is.
+;
+; In this case, the PHI node that is sunk from ehcleanup to catch.dispatch
+; should have an incoming value entry for path from 'foo' that references the
+; PHI node itself.
+;
+; CHECK: define void @f8()
+; CHECK: entry:
+; CHECK:   invoke void @g()
+; CHECK: invoke.cont:
+; CHECK:   invoke void @g()
+; CHECK-NOT: ehcleanup:
+; CHECK-NOT:   cleanuppad
+; CHECK: catch.dispatch:
+; CHECK:   %x = phi i32 [ 2, %invoke.cont ], [ 1, %entry ], [ %x, %catch.cont ] 
+; CHECK: }
+define void @f8() personality i8* bitcast (i32 (...)* @__CxxFrameHandler3 to i8*) {
+entry:
+  invoke void @g()
+          to label %invoke.cont unwind label %ehcleanup
+
+invoke.cont:                                      ; preds = %entry
+  invoke void @g()
+          to label %return unwind label %ehcleanup
+
+ehcleanup:                                        ; preds = %invoke.cont, %entry
+  %x = phi i32 [ 2, %invoke.cont ], [ 1, %entry ]
+  %0 = cleanuppad []
+  cleanupret %0 unwind label %catch.dispatch
+
+catch.dispatch:                                   ; preds = %ehcleanup, %catch.cont
+  %1 = catchpad [i8* null, i8* null] to label %catch unwind label %catchendblock
+
+catch:                                            ; preds = %catch.dispatch
+  call void @use_x(i32 %x)
+  catchret %1 to label %catch.cont
+
+catchendblock:                                    ; preds = %catch.dispatch
+  catchendpad unwind to caller
+
+catch.cont:                                       ; preds = %catch
+  invoke void @g()
+          to label %return unwind label %catch.dispatch
+
+return:                                           ; preds = %invoke.cont, %catch.cont
+  ret void
+}
+
+%struct.S = type { i8 }
+%struct.S2 = type { i8 }
+declare void @"\01??1S2@@QEAA@XZ"(%struct.S2*)
+declare void @g()
+declare void @use_x(i32 %x)
+
+declare i32 @__CxxFrameHandler3(...)
+