Merging r258273:
authorHans Wennborg <hans@hanshq.net>
Wed, 20 Jan 2016 21:14:05 +0000 (21:14 +0000)
committerHans Wennborg <hans@hanshq.net>
Wed, 20 Jan 2016 21:14:05 +0000 (21:14 +0000)
------------------------------------------------------------------------
r258273 | josepht | 2016-01-19 18:15:15 -0800 (Tue, 19 Jan 2016) | 37 lines

[Inliner/WinEH] Honor implicit nounwinds

Summary:
Funclet EH tables require that a given funclet have only one unwind
destination for exceptional exits.  The verifier will therefore reject
e.g. two cleanuprets with different unwind dests for the same cleanup, or
two invokes exiting the same funclet but to different unwind dests.
Because catchswitch has no 'nounwind' variant, and because IR producers
are not *required* to annotate calls which will not unwind as 'nounwind',
it is legal to nest a call or an "unwind to caller" catchswitch within a
funclet pad that has an unwind destination other than caller; it is
undefined behavior for such a call or catchswitch to unwind.

Normally when inlining an invoke, calls in the inlined sequence are
rewritten to invokes that unwind to the callsite invoke's unwind
destination, and "unwind to caller" catchswitches in the inlined sequence
are rewritten to unwind to the callsite invoke's unwind destination.
However, if such a call or "unwind to caller" catchswitch is located in a
callee funclet that has another exceptional exit with an unwind
destination within the callee, applying the normal transformation would
give that callee funclet multiple unwind destinations for its exceptional
exits.  There would be no way for EH table generation to determine which
is the "true" exit, and the verifier would reject the function
accordingly.

Add logic to the inliner to detect these cases and leave such calls and
"unwind to caller" catchswitches as calls and "unwind to caller"
catchswitches in the inlined sequence.

This fixes PR26147.

Reviewers: rnk, andrew.w.kaylor, majnemer

Subscribers: alexcrichton, llvm-commits

Differential Revision: http://reviews.llvm.org/D16319
------------------------------------------------------------------------

git-svn-id: https://llvm.org/svn/llvm-project/llvm/branches/release_38@258349 91177308-0d34-0410-b5e6-96231b3b80d8

lib/Transforms/Utils/InlineFunction.cpp
test/Transforms/Inline/inline-funclets.ll [new file with mode: 0644]

index 1457411..79282a2 100644 (file)
@@ -179,13 +179,244 @@ void LandingPadInliningInfo::forwardResume(
   RI->eraseFromParent();
 }
 
+/// Helper for getUnwindDestToken/getUnwindDestTokenHelper.
+static Value *getParentPad(Value *EHPad) {
+  if (auto *FPI = dyn_cast<FuncletPadInst>(EHPad))
+    return FPI->getParentPad();
+  return cast<CatchSwitchInst>(EHPad)->getParentPad();
+}
+
+typedef DenseMap<Instruction *, Value *> UnwindDestMemoTy;
+
+/// Helper for getUnwindDestToken that does the descendant-ward part of
+/// the search.
+static Value *getUnwindDestTokenHelper(Instruction *EHPad,
+                                       UnwindDestMemoTy &MemoMap) {
+  SmallVector<Instruction *, 8> Worklist(1, EHPad);
+
+  while (!Worklist.empty()) {
+    Instruction *CurrentPad = Worklist.pop_back_val();
+    // We only put pads on the worklist that aren't in the MemoMap.  When
+    // we find an unwind dest for a pad we may update its ancestors, but
+    // the queue only ever contains uncles/great-uncles/etc. of CurrentPad,
+    // so they should never get updated while queued on the worklist.
+    assert(!MemoMap.count(CurrentPad));
+    Value *UnwindDestToken = nullptr;
+    if (auto *CatchSwitch = dyn_cast<CatchSwitchInst>(CurrentPad)) {
+      if (CatchSwitch->hasUnwindDest()) {
+        UnwindDestToken = CatchSwitch->getUnwindDest()->getFirstNonPHI();
+      } else {
+        // Catchswitch doesn't have a 'nounwind' variant, and one might be
+        // annotated as "unwinds to caller" when really it's nounwind (see
+        // e.g. SimplifyCFGOpt::SimplifyUnreachable), so we can't infer the
+        // parent's unwind dest from this.  We can check its catchpads'
+        // descendants, since they might include a cleanuppad with an
+        // "unwinds to caller" cleanupret, which can be trusted.
+        for (auto HI = CatchSwitch->handler_begin(),
+                  HE = CatchSwitch->handler_end();
+             HI != HE && !UnwindDestToken; ++HI) {
+          BasicBlock *HandlerBlock = *HI;
+          auto *CatchPad = cast<CatchPadInst>(HandlerBlock->getFirstNonPHI());
+          for (User *Child : CatchPad->users()) {
+            // Intentionally ignore invokes here -- since the catchswitch is
+            // marked "unwind to caller", it would be a verifier error if it
+            // contained an invoke which unwinds out of it, so any invoke we'd
+            // encounter must unwind to some child of the catch.
+            if (!isa<CleanupPadInst>(Child) && !isa<CatchSwitchInst>(Child))
+              continue;
+
+            Instruction *ChildPad = cast<Instruction>(Child);
+            auto Memo = MemoMap.find(ChildPad);
+            if (Memo == MemoMap.end()) {
+              // Haven't figure out this child pad yet; queue it.
+              Worklist.push_back(ChildPad);
+              continue;
+            }
+            // We've already checked this child, but might have found that
+            // it offers no proof either way.
+            Value *ChildUnwindDestToken = Memo->second;
+            if (!ChildUnwindDestToken)
+              continue;
+            // We already know the child's unwind dest, which can either
+            // be ConstantTokenNone to indicate unwind to caller, or can
+            // be another child of the catchpad.  Only the former indicates
+            // the unwind dest of the catchswitch.
+            if (isa<ConstantTokenNone>(ChildUnwindDestToken)) {
+              UnwindDestToken = ChildUnwindDestToken;
+              break;
+            }
+            assert(getParentPad(ChildUnwindDestToken) == CatchPad);
+          }
+        }
+      }
+    } else {
+      auto *CleanupPad = cast<CleanupPadInst>(CurrentPad);
+      for (User *U : CleanupPad->users()) {
+        if (auto *CleanupRet = dyn_cast<CleanupReturnInst>(U)) {
+          if (BasicBlock *RetUnwindDest = CleanupRet->getUnwindDest())
+            UnwindDestToken = RetUnwindDest->getFirstNonPHI();
+          else
+            UnwindDestToken = ConstantTokenNone::get(CleanupPad->getContext());
+          break;
+        }
+        Value *ChildUnwindDestToken;
+        if (auto *Invoke = dyn_cast<InvokeInst>(U)) {
+          ChildUnwindDestToken = Invoke->getUnwindDest()->getFirstNonPHI();
+        } else if (isa<CleanupPadInst>(U) || isa<CatchSwitchInst>(U)) {
+          Instruction *ChildPad = cast<Instruction>(U);
+          auto Memo = MemoMap.find(ChildPad);
+          if (Memo == MemoMap.end()) {
+            // Haven't resolved this child yet; queue it and keep searching.
+            Worklist.push_back(ChildPad);
+            continue;
+          }
+          // We've checked this child, but still need to ignore it if it
+          // had no proof either way.
+          ChildUnwindDestToken = Memo->second;
+          if (!ChildUnwindDestToken)
+            continue;
+        } else {
+          // Not a relevant user of the cleanuppad
+          continue;
+        }
+        // In a well-formed program, the child/invoke must either unwind to
+        // an(other) child of the cleanup, or exit the cleanup.  In the
+        // first case, continue searching.
+        if (isa<Instruction>(ChildUnwindDestToken) &&
+            getParentPad(ChildUnwindDestToken) == CleanupPad)
+          continue;
+        UnwindDestToken = ChildUnwindDestToken;
+        break;
+      }
+    }
+    // If we haven't found an unwind dest for CurrentPad, we may have queued its
+    // children, so move on to the next in the worklist.
+    if (!UnwindDestToken)
+      continue;
+
+    // Now we know that CurrentPad unwinds to UnwindDestToken.  It also exits
+    // any ancestors of CurrentPad up to but not including UnwindDestToken's
+    // parent pad.  Record this in the memo map, and check to see if the
+    // original EHPad being queried is one of the ones exited.
+    Value *UnwindParent;
+    if (auto *UnwindPad = dyn_cast<Instruction>(UnwindDestToken))
+      UnwindParent = getParentPad(UnwindPad);
+    else
+      UnwindParent = nullptr;
+    bool ExitedOriginalPad = false;
+    for (Instruction *ExitedPad = CurrentPad;
+         ExitedPad && ExitedPad != UnwindParent;
+         ExitedPad = dyn_cast<Instruction>(getParentPad(ExitedPad))) {
+      // Skip over catchpads since they just follow their catchswitches.
+      if (isa<CatchPadInst>(ExitedPad))
+        continue;
+      MemoMap[ExitedPad] = UnwindDestToken;
+      ExitedOriginalPad |= (ExitedPad == EHPad);
+    }
+
+    if (ExitedOriginalPad)
+      return UnwindDestToken;
+
+    // Continue the search.
+  }
+
+  // No definitive information is contained within this funclet.
+  return nullptr;
+}
+
+/// Given an EH pad, find where it unwinds.  If it unwinds to an EH pad,
+/// return that pad instruction.  If it unwinds to caller, return
+/// ConstantTokenNone.  If it does not have a definitive unwind destination,
+/// return nullptr.
+///
+/// This routine gets invoked for calls in funclets in inlinees when inlining
+/// an invoke.  Since many funclets don't have calls inside them, it's queried
+/// on-demand rather than building a map of pads to unwind dests up front.
+/// Determining a funclet's unwind dest may require recursively searching its
+/// descendants, and also ancestors and cousins if the descendants don't provide
+/// an answer.  Since most funclets will have their unwind dest immediately
+/// available as the unwind dest of a catchswitch or cleanupret, this routine
+/// searches top-down from the given pad and then up. To avoid worst-case
+/// quadratic run-time given that approach, it uses a memo map to avoid
+/// re-processing funclet trees.  The callers that rewrite the IR as they go
+/// take advantage of this, for correctness, by checking/forcing rewritten
+/// pads' entries to match the original callee view.
+static Value *getUnwindDestToken(Instruction *EHPad,
+                                 UnwindDestMemoTy &MemoMap) {
+  // Catchpads unwind to the same place as their catchswitch;
+  // redirct any queries on catchpads so the code below can
+  // deal with just catchswitches and cleanuppads.
+  if (auto *CPI = dyn_cast<CatchPadInst>(EHPad))
+    EHPad = CPI->getCatchSwitch();
+
+  // Check if we've already determined the unwind dest for this pad.
+  auto Memo = MemoMap.find(EHPad);
+  if (Memo != MemoMap.end())
+    return Memo->second;
+
+  // Search EHPad and, if necessary, its descendants.
+  Value *UnwindDestToken = getUnwindDestTokenHelper(EHPad, MemoMap);
+  assert((UnwindDestToken == nullptr) != (MemoMap.count(EHPad) != 0));
+  if (UnwindDestToken)
+    return UnwindDestToken;
+
+  // No information is available for this EHPad from itself or any of its
+  // descendants.  An unwind all the way out to a pad in the caller would
+  // need also to agree with the unwind dest of the parent funclet, so
+  // search up the chain to try to find a funclet with information.  Put
+  // null entries in the memo map to avoid re-processing as we go up.
+  MemoMap[EHPad] = nullptr;
+  Instruction *LastUselessPad = EHPad;
+  Value *AncestorToken;
+  for (AncestorToken = getParentPad(EHPad);
+       auto *AncestorPad = dyn_cast<Instruction>(AncestorToken);
+       AncestorToken = getParentPad(AncestorToken)) {
+    // Skip over catchpads since they just follow their catchswitches.
+    if (isa<CatchPadInst>(AncestorPad))
+      continue;
+    assert(!MemoMap.count(AncestorPad) || MemoMap[AncestorPad]);
+    auto AncestorMemo = MemoMap.find(AncestorPad);
+    if (AncestorMemo == MemoMap.end()) {
+      UnwindDestToken = getUnwindDestTokenHelper(AncestorPad, MemoMap);
+    } else {
+      UnwindDestToken = AncestorMemo->second;
+    }
+    if (UnwindDestToken)
+      break;
+    LastUselessPad = AncestorPad;
+  }
+
+  // Since the whole tree under LastUselessPad has no information, it all must
+  // match UnwindDestToken; record that to avoid repeating the search.
+  SmallVector<Instruction *, 8> Worklist(1, LastUselessPad);
+  while (!Worklist.empty()) {
+    Instruction *UselessPad = Worklist.pop_back_val();
+    assert(!MemoMap.count(UselessPad) || MemoMap[UselessPad] == nullptr);
+    MemoMap[UselessPad] = UnwindDestToken;
+    if (auto *CatchSwitch = dyn_cast<CatchSwitchInst>(UselessPad)) {
+      for (BasicBlock *HandlerBlock : CatchSwitch->handlers())
+        for (User *U : HandlerBlock->getFirstNonPHI()->users())
+          if (isa<CatchSwitchInst>(U) || isa<CleanupPadInst>(U))
+            Worklist.push_back(cast<Instruction>(U));
+    } else {
+      assert(isa<CleanupPadInst>(UselessPad));
+      for (User *U : UselessPad->users())
+        if (isa<CatchSwitchInst>(U) || isa<CleanupPadInst>(U))
+          Worklist.push_back(cast<Instruction>(U));
+    }
+  }
+
+  return UnwindDestToken;
+}
+
 /// When we inline a basic block into an invoke,
 /// we have to turn all of the calls that can throw into invokes.
 /// This function analyze BB to see if there are any calls, and if so,
 /// it rewrites them to be invokes that jump to InvokeDest and fills in the PHI
 /// nodes in that block with the values specified in InvokeDestPHIValues.
-static BasicBlock *
-HandleCallsInBlockInlinedThroughInvoke(BasicBlock *BB, BasicBlock *UnwindEdge) {
+static BasicBlock *HandleCallsInBlockInlinedThroughInvoke(
+    BasicBlock *BB, BasicBlock *UnwindEdge,
+    UnwindDestMemoTy *FuncletUnwindMap = nullptr) {
   for (BasicBlock::iterator BBI = BB->begin(), E = BB->end(); BBI != E; ) {
     Instruction *I = &*BBI++;
 
@@ -196,6 +427,31 @@ HandleCallsInBlockInlinedThroughInvoke(BasicBlock *BB, BasicBlock *UnwindEdge) {
     if (!CI || CI->doesNotThrow() || isa<InlineAsm>(CI->getCalledValue()))
       continue;
 
+    if (auto FuncletBundle = CI->getOperandBundle(LLVMContext::OB_funclet)) {
+      // This call is nested inside a funclet.  If that funclet has an unwind
+      // destination within the inlinee, then unwinding out of this call would
+      // be UB.  Rewriting this call to an invoke which targets the inlined
+      // invoke's unwind dest would give the call's parent funclet multiple
+      // unwind destinations, which is something that subsequent EH table
+      // generation can't handle and that the veirifer rejects.  So when we
+      // see such a call, leave it as a call.
+      auto *FuncletPad = cast<Instruction>(FuncletBundle->Inputs[0]);
+      Value *UnwindDestToken =
+          getUnwindDestToken(FuncletPad, *FuncletUnwindMap);
+      if (UnwindDestToken && !isa<ConstantTokenNone>(UnwindDestToken))
+        continue;
+#ifndef NDEBUG
+      Instruction *MemoKey;
+      if (auto *CatchPad = dyn_cast<CatchPadInst>(FuncletPad))
+        MemoKey = CatchPad->getCatchSwitch();
+      else
+        MemoKey = FuncletPad;
+      assert(FuncletUnwindMap->count(MemoKey) &&
+             (*FuncletUnwindMap)[MemoKey] == UnwindDestToken &&
+             "must get memoized to avoid confusing later searches");
+#endif // NDEBUG
+    }
+
     // Convert this function call into an invoke instruction.  First, split the
     // basic block.
     BasicBlock *Split =
@@ -328,13 +584,23 @@ static void HandleInlinedEHPad(InvokeInst *II, BasicBlock *FirstNewBlock,
 
   // This connects all the instructions which 'unwind to caller' to the invoke
   // destination.
+  UnwindDestMemoTy FuncletUnwindMap;
   for (Function::iterator BB = FirstNewBlock->getIterator(), E = Caller->end();
        BB != E; ++BB) {
     if (auto *CRI = dyn_cast<CleanupReturnInst>(BB->getTerminator())) {
       if (CRI->unwindsToCaller()) {
-        CleanupReturnInst::Create(CRI->getCleanupPad(), UnwindDest, CRI);
+        auto *CleanupPad = CRI->getCleanupPad();
+        CleanupReturnInst::Create(CleanupPad, UnwindDest, CRI);
         CRI->eraseFromParent();
         UpdatePHINodes(&*BB);
+        // Finding a cleanupret with an unwind destination would confuse
+        // subsequent calls to getUnwindDestToken, so map the cleanuppad
+        // to short-circuit any such calls and recognize this as an "unwind
+        // to caller" cleanup.
+        assert(!FuncletUnwindMap.count(CleanupPad) ||
+               isa<ConstantTokenNone>(FuncletUnwindMap[CleanupPad]));
+        FuncletUnwindMap[CleanupPad] =
+            ConstantTokenNone::get(Caller->getContext());
       }
     }
 
@@ -345,12 +611,41 @@ static void HandleInlinedEHPad(InvokeInst *II, BasicBlock *FirstNewBlock,
     Instruction *Replacement = nullptr;
     if (auto *CatchSwitch = dyn_cast<CatchSwitchInst>(I)) {
       if (CatchSwitch->unwindsToCaller()) {
+        Value *UnwindDestToken;
+        if (auto *ParentPad =
+                dyn_cast<Instruction>(CatchSwitch->getParentPad())) {
+          // This catchswitch is nested inside another funclet.  If that
+          // funclet has an unwind destination within the inlinee, then
+          // unwinding out of this catchswitch would be UB.  Rewriting this
+          // catchswitch to unwind to the inlined invoke's unwind dest would
+          // give the parent funclet multiple unwind destinations, which is
+          // something that subsequent EH table generation can't handle and
+          // that the veirifer rejects.  So when we see such a call, leave it
+          // as "unwind to caller".
+          UnwindDestToken = getUnwindDestToken(ParentPad, FuncletUnwindMap);
+          if (UnwindDestToken && !isa<ConstantTokenNone>(UnwindDestToken))
+            continue;
+        } else {
+          // This catchswitch has no parent to inherit constraints from, and
+          // none of its descendants can have an unwind edge that exits it and
+          // targets another funclet in the inlinee.  It may or may not have a
+          // descendant that definitively has an unwind to caller.  In either
+          // case, we'll have to assume that any unwinds out of it may need to
+          // be routed to the caller, so treat it as though it has a definitive
+          // unwind to caller.
+          UnwindDestToken = ConstantTokenNone::get(Caller->getContext());
+        }
         auto *NewCatchSwitch = CatchSwitchInst::Create(
             CatchSwitch->getParentPad(), UnwindDest,
             CatchSwitch->getNumHandlers(), CatchSwitch->getName(),
             CatchSwitch);
         for (BasicBlock *PadBB : CatchSwitch->handlers())
           NewCatchSwitch->addHandler(PadBB);
+        // Propagate info for the old catchswitch over to the new one in
+        // the unwind map.  This also serves to short-circuit any subsequent
+        // checks for the unwind dest of this catchswitch, which would get
+        // confused if they found the outer handler in the callee.
+        FuncletUnwindMap[NewCatchSwitch] = UnwindDestToken;
         Replacement = NewCatchSwitch;
       }
     } else if (!isa<FuncletPadInst>(I)) {
@@ -369,8 +664,8 @@ static void HandleInlinedEHPad(InvokeInst *II, BasicBlock *FirstNewBlock,
     for (Function::iterator BB = FirstNewBlock->getIterator(),
                             E = Caller->end();
          BB != E; ++BB)
-      if (BasicBlock *NewBB =
-              HandleCallsInBlockInlinedThroughInvoke(&*BB, UnwindDest))
+      if (BasicBlock *NewBB = HandleCallsInBlockInlinedThroughInvoke(
+              &*BB, UnwindDest, &FuncletUnwindMap))
         // Update any PHI nodes in the exceptional block to indicate that there
         // is now a new entry in them.
         UpdatePHINodes(NewBB);
@@ -1415,6 +1710,20 @@ bool llvm::InlineFunction(CallSite CS, InlineFunctionInfo &IFI,
     }
   }
 
+  // If we are inlining for an invoke instruction, we must make sure to rewrite
+  // any call instructions into invoke instructions.  This is sensitive to which
+  // funclet pads were top-level in the inlinee, so must be done before
+  // rewriting the "parent pad" links.
+  if (auto *II = dyn_cast<InvokeInst>(TheCall)) {
+    BasicBlock *UnwindDest = II->getUnwindDest();
+    Instruction *FirstNonPHI = UnwindDest->getFirstNonPHI();
+    if (isa<LandingPadInst>(FirstNonPHI)) {
+      HandleInlinedLandingPad(II, &*FirstNewBlock, InlinedFunctionInfo);
+    } else {
+      HandleInlinedEHPad(II, &*FirstNewBlock, InlinedFunctionInfo);
+    }
+  }
+
   // Update the lexical scopes of the new funclets and callsites.
   // Anything that had 'none' as its parent is now nested inside the callsite's
   // EHPad.
@@ -1472,18 +1781,6 @@ bool llvm::InlineFunction(CallSite CS, InlineFunctionInfo &IFI,
     }
   }
 
-  // If we are inlining for an invoke instruction, we must make sure to rewrite
-  // any call instructions into invoke instructions.
-  if (auto *II = dyn_cast<InvokeInst>(TheCall)) {
-    BasicBlock *UnwindDest = II->getUnwindDest();
-    Instruction *FirstNonPHI = UnwindDest->getFirstNonPHI();
-    if (isa<LandingPadInst>(FirstNonPHI)) {
-      HandleInlinedLandingPad(II, &*FirstNewBlock, InlinedFunctionInfo);
-    } else {
-      HandleInlinedEHPad(II, &*FirstNewBlock, InlinedFunctionInfo);
-    }
-  }
-
   // Handle any inlined musttail call sites.  In order for a new call site to be
   // musttail, the source of the clone and the inlined call site must have been
   // musttail.  Therefore it's safe to return without merging control into the
diff --git a/test/Transforms/Inline/inline-funclets.ll b/test/Transforms/Inline/inline-funclets.ll
new file mode 100644 (file)
index 0000000..362e03d
--- /dev/null
@@ -0,0 +1,455 @@
+; RUN: opt -inline -S %s | FileCheck %s
+
+declare void @g()
+
+
+;;; Test with a call in a funclet that needs to remain a call
+;;; when inlined because the funclet doesn't unwind to caller.
+;;; CHECK-LABEL: define void @test1(
+define void @test1() personality void ()* @g {
+entry:
+; CHECK-NEXT: entry:
+  invoke void @test1_inlinee()
+    to label %exit unwind label %cleanup
+cleanup:
+  %pad = cleanuppad within none []
+  call void @g() [ "funclet"(token %pad) ]
+  cleanupret from %pad unwind to caller
+exit:
+  ret void
+}
+
+define void @test1_inlinee() alwaysinline personality void ()* @g {
+entry:
+  invoke void @g()
+    to label %exit unwind label %cleanup.inner
+; CHECK-NEXT:  invoke void @g()
+; CHECK-NEXT:    unwind label %[[cleanup_inner:.+]]
+
+cleanup.inner:
+  %pad.inner = cleanuppad within none []
+  call void @g() [ "funclet"(token %pad.inner) ]
+  cleanupret from %pad.inner unwind label %cleanup.outer
+; CHECK: [[cleanup_inner]]:
+; The call here needs to remain a call becuase pad.inner has a cleanupret
+; that stays within the inlinee.
+; CHECK-NEXT:  %[[pad_inner:[^ ]+]] = cleanuppad within none
+; CHECK-NEXT:  call void @g() [ "funclet"(token %[[pad_inner]]) ]
+; CHECK-NEXT:  cleanupret from %[[pad_inner]] unwind label %[[cleanup_outer:.+]]
+
+cleanup.outer:
+  %pad.outer = cleanuppad within none []
+  call void @g() [ "funclet"(token %pad.outer) ]
+  cleanupret from %pad.outer unwind to caller
+; CHECK: [[cleanup_outer]]:
+; The call and cleanupret here need to be redirected to caller cleanup
+; CHECK-NEXT: %[[pad_outer:[^ ]+]] = cleanuppad within none
+; CHECK-NEXT: invoke void @g() [ "funclet"(token %[[pad_outer]]) ]
+; CHECK-NEXT:   unwind label %cleanup
+; CHECK: cleanupret from %[[pad_outer]] unwind label %cleanup{{$}}
+
+exit:
+  ret void
+}
+
+
+
+;;; Test with an "unwind to caller" catchswitch in a parent funclet
+;;; that needs to remain "unwind to caller" because the parent
+;;; doesn't unwind to caller.
+;;; CHECK-LABEL: define void @test2(
+define void @test2() personality void ()* @g {
+entry:
+; CHECK-NEXT: entry:
+  invoke void @test2_inlinee()
+    to label %exit unwind label %cleanup
+cleanup:
+  %pad = cleanuppad within none []
+  call void @g() [ "funclet"(token %pad) ]
+  cleanupret from %pad unwind to caller
+exit:
+  ret void
+}
+
+define void @test2_inlinee() alwaysinline personality void ()* @g {
+entry:
+  invoke void @g()
+    to label %exit unwind label %cleanup1
+; CHECK-NEXT:   invoke void @g()
+; CHECK-NEXT:     unwind label %[[cleanup1:.+]]
+
+cleanup1:
+  %outer = cleanuppad within none []
+  invoke void @g() [ "funclet"(token %outer) ]
+    to label %ret1 unwind label %catchswitch
+; CHECK: [[cleanup1]]:
+; CHECK-NEXT: %[[outer:[^ ]+]] = cleanuppad within none
+; CHECK-NEXT: invoke void @g() [ "funclet"(token %[[outer]]) ]
+; CHECK-NEXT:   unwind label %[[catchswitch:.+]]
+
+catchswitch:
+  %cs = catchswitch within %outer [label %catch] unwind to caller
+; CHECK: [[catchswitch]]:
+; The catchswitch here needs to remain "unwind to caller" since %outer
+; has a cleanupret that remains within the inlinee.
+; CHECK-NEXT: %[[cs:[^ ]+]] = catchswitch within %[[outer]] [label %[[catch:.+]]] unwind to caller
+
+catch:
+  %inner = catchpad within %cs []
+  call void @g() [ "funclet"(token %inner) ]
+  catchret from %inner to label %ret1
+; CHECK: [[catch]]:
+; The call here needs to remain a call since it too is within %outer
+; CHECK:   %[[inner:[^ ]+]] = catchpad within %[[cs]]
+; CHECK-NEXT: call void @g() [ "funclet"(token %[[inner]]) ]
+
+ret1:
+  cleanupret from %outer unwind label %cleanup2
+; CHECK: cleanupret from %[[outer]] unwind label %[[cleanup2:.+]]
+
+cleanup2:
+  %later = cleanuppad within none []
+  cleanupret from %later unwind to caller
+; CHECK: [[cleanup2]]:
+; The cleanupret here needs to get redirected to the caller cleanup
+; CHECK-NEXT: %[[later:[^ ]+]] = cleanuppad within none
+; CHECK-NEXT: cleanupret from %[[later]] unwind label %cleanup{{$}}
+
+exit:
+  ret void
+}
+
+
+;;; Test with a call in a cleanup that has no definitive unwind
+;;; destination, that must be rewritten to an invoke.
+;;; CHECK-LABEL: define void @test3(
+define void @test3() personality void ()* @g {
+entry:
+; CHECK-NEXT: entry:
+  invoke void @test3_inlinee()
+    to label %exit unwind label %cleanup
+cleanup:
+  %pad = cleanuppad within none []
+  call void @g() [ "funclet"(token %pad) ]
+  cleanupret from %pad unwind to caller
+exit:
+  ret void
+}
+
+define void @test3_inlinee() alwaysinline personality void ()* @g {
+entry:
+  invoke void @g()
+    to label %exit unwind label %cleanup
+; CHECK-NEXT:  invoke void @g()
+; CHECK-NEXT:    unwind label %[[cleanup:.+]]
+
+cleanup:
+  %pad = cleanuppad within none []
+  call void @g() [ "funclet"(token %pad) ]
+  unreachable
+; CHECK: [[cleanup]]:
+; The call must be rewritten to an invoke targeting the caller cleanup
+; because it may well unwind to there.
+; CHECK-NEXT: %[[pad:[^ ]+]] = cleanuppad within none
+; CHECK-NEXT: invoke void @g() [ "funclet"(token %[[pad]]) ]
+; CHECK-NEXT:   unwind label %cleanup{{$}}
+
+exit:
+  ret void
+}
+
+
+;;; Test with a catchswitch in a cleanup that has no definitive
+;;; unwind destination, that must be rewritten to unwind to the
+;;; inlined invoke's unwind dest
+;;; CHECK-LABEL: define void @test4(
+define void @test4() personality void ()* @g {
+entry:
+; CHECK-NEXT: entry:
+  invoke void @test4_inlinee()
+    to label %exit unwind label %cleanup
+cleanup:
+  %pad = cleanuppad within none []
+  call void @g() [ "funclet"(token %pad) ]
+  cleanupret from %pad unwind to caller
+exit:
+  ret void
+}
+
+define void @test4_inlinee() alwaysinline personality void ()* @g {
+entry:
+  invoke void @g()
+    to label %exit unwind label %cleanup
+; CHECK-NEXT: invoke void @g()
+; CHECK-NEXT:   unwind label %[[cleanup:.+]]
+
+cleanup:
+  %clean = cleanuppad within none []
+  invoke void @g() [ "funclet"(token %clean) ]
+    to label %unreachable unwind label %dispatch
+; CHECK: [[cleanup]]:
+; CHECK-NEXT: %[[clean:[^ ]+]] = cleanuppad within none
+; CHECK-NEXT: invoke void @g() [ "funclet"(token %[[clean]]) ]
+; CHECK-NEXT:   unwind label %[[dispatch:.+]]
+
+dispatch:
+  %cs = catchswitch within %clean [label %catch] unwind to caller
+; CHECK: [[dispatch]]:
+; The catchswitch must be rewritten to unwind to %cleanup in the caller
+; because it may well unwind to there.
+; CHECK-NEXT: %[[cs:[^ ]+]] = catchswitch within %[[clean]] [label %[[catch:.+]]] unwind label %cleanup{{$}}
+
+catch:
+  catchpad within %cs []
+  br label %unreachable
+unreachable:
+  unreachable
+exit:
+  ret void
+}
+
+
+;;; Test with multiple levels of nesting, and unwind dests
+;;; that need to be inferred from ancestors, descendants,
+;;; and cousins.
+;;; CHECK-LABEL: define void @test5(
+define void @test5() personality void ()* @g {
+entry:
+; CHECK-NEXT: entry:
+  invoke void @test5_inlinee()
+    to label %exit unwind label %cleanup
+cleanup:
+  %pad = cleanuppad within none []
+  call void @g() [ "funclet"(token %pad) ]
+  cleanupret from %pad unwind to caller
+exit:
+  ret void
+}
+
+define void @test5_inlinee() alwaysinline personality void ()* @g {
+entry:
+  invoke void @g()
+    to label %cont unwind label %noinfo.root
+; CHECK-NEXT: invoke void @g()
+; CHECK-NEXT:   to label %[[cont:[^ ]+]] unwind label %[[noinfo_root:.+]]
+
+noinfo.root:
+  %noinfo.root.pad = cleanuppad within none []
+  call void @g() [ "funclet"(token %noinfo.root.pad) ]
+  invoke void @g() [ "funclet"(token %noinfo.root.pad) ]
+    to label %noinfo.root.cont unwind label %noinfo.left
+; CHECK: [[noinfo_root]]:
+; Nothing under "noinfo.root" has a definitive unwind destination, so
+; we must assume all of it may actually unwind, and redirect unwinds
+; to the cleanup in the caller.
+; CHECK-NEXT: %[[noinfo_root_pad:[^ ]+]] = cleanuppad within none []
+; CHECK-NEXT: invoke void @g() [ "funclet"(token %[[noinfo_root_pad]]) ]
+; CHECK-NEXT:   to label %[[next:[^ ]+]] unwind label %cleanup{{$}}
+; CHECK: [[next]]:
+; CHECK-NEXT: invoke void @g() [ "funclet"(token %[[noinfo_root_pad]]) ]
+; CHECK-NEXT:   to label %[[noinfo_root_cont:[^ ]+]] unwind label %[[noinfo_left:.+]]
+
+noinfo.left:
+  %noinfo.left.pad = cleanuppad within %noinfo.root.pad []
+  invoke void @g() [ "funclet"(token %noinfo.left.pad) ]
+    to label %unreachable unwind label %noinfo.left.child
+; CHECK: [[noinfo_left]]:
+; CHECK-NEXT: %[[noinfo_left_pad:[^ ]+]] = cleanuppad within %[[noinfo_root_pad]]
+; CHECK-NEXT: invoke void @g() [ "funclet"(token %[[noinfo_left_pad]]) ]
+; CHECK-NEXT:   unwind label %[[noinfo_left_child:.+]]
+
+noinfo.left.child:
+  %noinfo.left.child.cs = catchswitch within %noinfo.left.pad [label %noinfo.left.child.catch] unwind to caller
+; CHECK: [[noinfo_left_child]]:
+; CHECK-NEXT: %[[noinfo_left_child_cs:[^ ]+]] = catchswitch within %[[noinfo_left_pad]] [label %[[noinfo_left_child_catch:[^ ]+]]] unwind label %cleanup{{$}}
+
+noinfo.left.child.catch:
+  %noinfo.left.child.pad = catchpad within %noinfo.left.child.cs []
+  call void @g() [ "funclet"(token %noinfo.left.child.pad) ]
+  br label %unreachable
+; CHECK: [[noinfo_left_child_catch]]:
+; CHECK-NEXT: %[[noinfo_left_child_pad:[^ ]+]] = catchpad within %[[noinfo_left_child_cs]] []
+; CHECK-NEXT: invoke void @g() [ "funclet"(token %[[noinfo_left_child_pad]]) ]
+; CHECK-NEXT:   unwind label %cleanup{{$}}
+
+noinfo.root.cont:
+  invoke void @g() [ "funclet"(token %noinfo.root.pad) ]
+    to label %unreachable unwind label %noinfo.right
+; CHECK: [[noinfo_root_cont]]:
+; CHECK-NEXT: invoke void @g() [ "funclet"(token %[[noinfo_root_pad]]) ]
+; CHECK-NEXT:   unwind label %[[noinfo_right:.+]]
+
+noinfo.right:
+  %noinfo.right.cs = catchswitch within %noinfo.root.pad [label %noinfo.right.catch] unwind to caller
+; CHECK: [[noinfo_right]]:
+; CHECK-NEXT: %[[noinfo_right_cs:[^ ]+]] = catchswitch within %[[noinfo_root_pad]] [label %[[noinfo_right_catch:[^ ]+]]] unwind label %cleanup{{$}}
+
+noinfo.right.catch:
+  %noinfo.right.pad = catchpad within %noinfo.right.cs []
+  invoke void @g() [ "funclet"(token %noinfo.right.pad) ]
+    to label %unreachable unwind label %noinfo.right.child
+; CHECK: [[noinfo_right_catch]]:
+; CHECK-NEXT: %[[noinfo_right_pad:[^ ]+]] = catchpad within %[[noinfo_right_cs]]
+; CHECK-NEXT: invoke void @g() [ "funclet"(token %[[noinfo_right_pad]]) ]
+; CHECK-NEXT:   unwind label %[[noinfo_right_child:.+]]
+
+noinfo.right.child:
+  %noinfo.right.child.pad = cleanuppad within %noinfo.right.pad []
+  call void @g() [ "funclet"(token %noinfo.right.child.pad) ]
+  br label %unreachable
+; CHECK: [[noinfo_right_child]]:
+; CHECK-NEXT: %[[noinfo_right_child_pad:[^ ]+]] = cleanuppad within %[[noinfo_right_pad]]
+; CHECK-NEXT: invoke void @g() [ "funclet"(token %[[noinfo_right_child_pad]]) ]
+; CHECK-NEXT:   unwind label %cleanup{{$}}
+
+cont:
+  invoke void @g()
+    to label %exit unwind label %implicit.root
+; CHECK: [[cont]]:
+; CHECK-NEXT: invoke void @g()
+; CHECK-NEXT:   unwind label %[[implicit_root:.+]]
+
+implicit.root:
+  %implicit.root.pad = cleanuppad within none []
+  call void @g() [ "funclet"(token %implicit.root.pad) ]
+  invoke void @g() [ "funclet"(token %implicit.root.pad) ]
+    to label %implicit.root.cont unwind label %implicit.left
+; CHECK: [[implicit_root]]:
+; There's an unwind edge to %internal in implicit.right, and we need to propagate that
+; fact down to implicit.right.grandchild, up to implicit.root, and down to
+; implicit.left.child.catch, leaving all calls and "unwind to caller" catchswitches
+; alone to so they don't conflict with the unwind edge in implicit.right
+; CHECK-NEXT: %[[implicit_root_pad:[^ ]+]] = cleanuppad within none
+; CHECK-NEXT: call void @g() [ "funclet"(token %[[implicit_root_pad]]) ]
+; CHECK-NEXT: invoke void @g() [ "funclet"(token %[[implicit_root_pad]]) ]
+; CHECK-NEXT:   to label %[[implicit_root_cont:[^ ]+]] unwind label %[[implicit_left:.+]]
+
+implicit.left:
+  %implicit.left.pad = cleanuppad within %implicit.root.pad []
+  invoke void @g() [ "funclet"(token %implicit.left.pad) ]
+    to label %unreachable unwind label %implicit.left.child
+; CHECK: [[implicit_left]]:
+; CHECK-NEXT: %[[implicit_left_pad:[^ ]+]] = cleanuppad within %[[implicit_root_pad:[^ ]+]]
+; CHECK-NEXT: invoke void @g() [ "funclet"(token %[[implicit_left_pad]]) ]
+; CHECK-NEXT:   unwind label %[[implicit_left_child:.+]]
+
+implicit.left.child:
+  %implicit.left.child.cs = catchswitch within %implicit.left.pad [label %implicit.left.child.catch] unwind to caller
+; CHECK: [[implicit_left_child]]:
+; CHECK-NEXT: %[[implicit_left_child_cs:[^ ]+]] = catchswitch within %[[implicit_left_pad]] [label %[[implicit_left_child_catch:[^ ]+]]] unwind to caller
+
+implicit.left.child.catch:
+  %implicit.left.child.pad = catchpad within %implicit.left.child.cs []
+  call void @g() [ "funclet"(token %implicit.left.child.pad) ]
+  br label %unreachable
+; CHECK: [[implicit_left_child_catch]]:
+; CHECK-NEXT: %[[implicit_left_child_pad:[^ ]+]] = catchpad within %[[implicit_left_child_cs]]
+; CHECK-NEXT: call void @g() [ "funclet"(token %[[implicit_left_child_pad]]) ]
+
+implicit.root.cont:
+  invoke void @g() [ "funclet"(token %implicit.root.pad) ]
+    to label %unreachable unwind label %implicit.right
+; CHECK: [[implicit_root_cont]]:
+; CHECK-NEXT: invoke void @g() [ "funclet"(token %[[implicit_root_pad]]) ]
+; CHECK-NEXT:   unwind label %[[implicit_right:.+]]
+
+implicit.right:
+  %implicit.right.cs = catchswitch within %implicit.root.pad [label %implicit.right.catch] unwind label %internal
+; CHECK: [[implicit_right]]:
+; This is the unwind edge (to %internal) whose existence needs to get propagated around the "implicit" tree
+; CHECK-NEXT: %[[implicit_right_cs:[^ ]+]] = catchswitch within %[[implicit_root_pad]] [label %[[implicit_right_catch:[^ ]+]]] unwind label %[[internal:.+]]
+
+implicit.right.catch:
+  %implicit.right.pad = catchpad within %implicit.right.cs []
+  invoke void @g() [ "funclet"(token %implicit.right.pad) ]
+    to label %unreachable unwind label %implicit.right.child
+; CHECK: [[implicit_right_catch]]:
+; CHECK-NEXT: %[[implicit_right_pad:[^ ]+]] = catchpad within %[[implicit_right_cs]]
+; CHECK-NEXT: invoke void @g() [ "funclet"(token %[[implicit_right_pad]]) ]
+; CHECK-NEXT:   unwind label %[[implicit_right_child:.+]]
+
+implicit.right.child:
+  %implicit.right.child.pad = cleanuppad within %implicit.right.pad []
+  invoke void @g() [ "funclet"(token %implicit.right.child.pad) ]
+    to label %unreachable unwind label %implicit.right.grandchild
+; CHECK: [[implicit_right_child]]:
+; CHECK-NEXT: %[[implicit_right_child_pad:[^ ]+]] = cleanuppad within %[[implicit_right_pad]]
+; CHECK-NEXT: invoke void @g() [ "funclet"(token %[[implicit_right_child_pad]]) ]
+; CHECK-NEXT:   unwind label %[[implicit_right_grandchild:.+]]
+
+implicit.right.grandchild:
+  %implicit.right.grandchild.cs = catchswitch within %implicit.right.child.pad [label %implicit.right.grandchild.catch] unwind to caller
+; CHECK: [[implicit_right_grandchild]]:
+; CHECK-NEXT: %[[implicit_right_grandchild_cs:[^ ]+]] = catchswitch within %[[implicit_right_child_pad]] [label %[[implicit_right_grandchild_catch:[^ ]+]]] unwind to caller
+
+implicit.right.grandchild.catch:
+  %implicit.right.grandhcild.pad = catchpad within %implicit.right.grandchild.cs []
+  call void @g() [ "funclet"(token %implicit.right.grandhcild.pad) ]
+  br label %unreachable
+; CHECK: [[implicit_right_grandchild_catch]]:
+; CHECK-NEXT: %[[implicit_right_grandhcild_pad:[^ ]+]] = catchpad within %[[implicit_right_grandchild_cs]]
+; CHECK-NEXT: call void @g() [ "funclet"(token %[[implicit_right_grandhcild_pad]]) ]
+
+internal:
+  %internal.pad = cleanuppad within none []
+  call void @g() [ "funclet"(token %internal.pad) ]
+  cleanupret from %internal.pad unwind to caller
+; CHECK: [[internal]]:
+; internal is a cleanup with a "return to caller" cleanuppad; that needs to get redirected
+; to %cleanup in the caller, and the call needs to get similarly rewritten to an invoke.
+; CHECK-NEXT: %[[internal_pad:[^ ]+]] = cleanuppad within none
+; CHECK-NEXT: invoke void @g() [ "funclet"(token %internal.pad.i) ]
+; CHECK-NEXT:   to label %[[next:[^ ]+]] unwind label %cleanup{{$}}
+; CHECK: [[next]]:
+; CHECK-NEXT: cleanupret from %[[internal_pad]] unwind label %cleanup{{$}}
+
+unreachable:
+  unreachable
+exit:
+  ret void
+}
+
+
+declare void @ProcessCLRException()
+
+; Make sure the logic doesn't get tripped up when the inlined invoke is
+; itself within a funclet in the caller.
+; CHECK-LABEL: define void @test6(
+define void @test6() personality void ()* @ProcessCLRException {
+entry:
+  invoke void @g()
+    to label %exit unwind label %callsite_parent
+callsite_parent:
+  %callsite_parent.pad = cleanuppad within none []
+; CHECK: %callsite_parent.pad = cleanuppad within none
+  invoke void @test6_inlinee() [ "funclet"(token %callsite_parent.pad) ]
+    to label %ret unwind label %cleanup
+ret:
+  cleanupret from %callsite_parent.pad unwind label %cleanup
+cleanup:
+  %pad = cleanuppad within none []
+  call void @g() [ "funclet"(token %pad) ]
+  cleanupret from %pad unwind to caller
+exit:
+  ret void
+}
+
+define void @test6_inlinee() alwaysinline personality void ()* @ProcessCLRException {
+entry:
+  invoke void @g()
+    to label %exit unwind label %inlinee_cleanup
+; CHECK-NEXT: invoke void @g() [ "funclet"(token %callsite_parent.pad) ]
+; CHECK-NEXT:   unwind label %[[inlinee_cleanup:.+]]
+
+inlinee_cleanup:
+  %inlinee.pad = cleanuppad within none []
+  call void @g() [ "funclet"(token %inlinee.pad) ]
+  unreachable
+; CHECK: [[inlinee_cleanup]]:
+; CHECK-NEXT: %[[inlinee_pad:[^ ]+]] = cleanuppad within %callsite_parent.pad
+; CHECK-NEXT: invoke void @g() [ "funclet"(token %[[inlinee_pad]]) ]
+; CHECK-NEXT:   unwind label %cleanup{{$}}
+
+exit:
+  ret void
+}