[WinEH] Clone funclets with multiple parents

[andrew.w.kaylor]

Summary

This patch clones the entire body of any funclet with more than one parent to avoid inconsistencies in the funclet hierarchy. Paths through the now multiple copies of the funclet which return to a funclet other than their intended parent are terminated with unreachable instructions.

Note that it was necessary to modify the wineh-demotion.ll and wineh-no-demotion.ll tests for this patch. The IR in the wineh-demotion.ll test appears to have been invalid and I just cleaned it up, attempting to preserve the intent of the test.

The wineh-no-demotion.ll test is directly impacted by the changes in this patch. Following the logic of the new funclet cloning algorithm for two of the test cases in this file results in multiple identical funclets with a unreachable terminator. This seems bad, but it wasn't clear to me whether it was preferable to not clone funclets in a situation like this given that the test cases in wineh-cloning.ll which were created in advance for this new cloning scenario include cleanup pads with unreachable terminators and seem to expect them to be cloned.

[JosephTremoulet]

Thanks for taking this on. I think the logic for cleanupret/cleanupendpad needs to be a little different, and that makeFuncletEdgeUnreachable can defer to removeUnwindEdge; aside from that, just a few nits.

lib/CodeGen/WinEHPrepare.cpp

3292–3294 ↗

(On Diff #36042)

FWIW, I had no idea what IdentityMap would be from its name. I did find Orig2Clone above intuitive, so maybe something like OriginalMap might be better?

3297–3298 ↗

(On Diff #36042)

I'm pretty sure you'd never hit this case if you pre-seeded IdentityMap to map the function entry block to itself.

3318 ↗

(On Diff #36042)

I think probably right here after the loop mapping children ends is the right place to fix up cleanupret/cleanupendpad (sibling) edges.

[JosephTremoulet]

lib/CodeGen/WinEHPrepare.cpp

2980–2987 ↗

(On Diff #36042)

Looks like you found an elegant way to determinize the output. Cool.

2997–2998 ↗

(On Diff #36042)

typo: "to an unreachable to an unreachable"

3039–3053 ↗

(On Diff #36042)

Cleanupret targets a sibling, not a parent. So,

1. I don't think this code should be here.
2. I guess you should have code somewhere that updates these sibling->sibling edges, though you probably can't do that until both siblings have been cloned...

Also, whatever you do about this with cleanupret, I think cleanupendpad should get the same treatment

3087–3100 ↗

(On Diff #36042)

As above, cleanupret should target a sibling, so I don't think this is right.

3168–3170 ↗

(On Diff #36042)

nit: you could use std::all_of to get this whole thing under the assert (or wrap it in #ifndef NDEBUG)

3206–3208 ↗

(On Diff #36042)

Why not just transform such invokes into calls?

3217–3219 ↗

(On Diff #36042)

I don't follow this logic. If simplifycfg determines an invoke's EH pad to be unreachable, it changes it to a call, and I don't see why we couldn't do the same here. It would be nice in both cases to mark the call as !MayThrow, but that can/should be a separate change.

I think the argument goes: since the unwind edge is unreachable, that must mean that no exception escapes the call/invoke, so modeling it as a call (that will happen not to throw) is sound.

3250–3251 ↗

(On Diff #36042)

CleanupEndPad transfers to sibling, same as CleanupRet

3260–3261 ↗

(On Diff #36042)

In the case that the terminator is a catchendpad or terminatepad, this has the same problem you called out above that an unreachable can't be an EH pad.

I think you could remove the special-casing for invoke (so add a case for it in the if/else ladder down here), and if it's a terminator whose unwind edge goes to the child and needs to be removed, call llvm::removeUnwindEdge(BB).

[JosephTremoulet]

lib/CodeGen/WinEHPrepare.cpp

2978 ↗

(On Diff #36042)

Since we expect multi-parent funclets to be extremely rare, it's probably worthwhile to record here whether you ever see a ColorMapItem with size > 1, then have resolveFuncletAncestry(Function*) check that and return immediately if there's no work for it to do.

[majnemer]

Intuitively, I'd expect cloning a funclet results in the creation of a new PHI if there are live-outs in the original funclet. Is this case impossible?

lib/CodeGen/WinEHPrepare.cpp

3184–3196 ↗

(On Diff #36042)

Is this strictly necessary? Will the code in cleanupPreparedFunclets not handle these cases?

[andrew.w.kaylor]

Responding to comments.

I'll update the patch when I've reworked the issues that were raised.

lib/CodeGen/WinEHPrepare.cpp

2978 ↗

(On Diff #36042)

OK

3039–3053 ↗

(On Diff #36042)

I see what you're saying, but cleanupret doesn't always unwind to a sibling. If it's the last cleanup inside a catch it can unwind to the parent (as it does in most of the current test cases).

I'll add some test cases involving sibling and then see if I can work out a good way to handle them.

3184–3196 ↗

(On Diff #36042)

I'm not sure. I believe I was seeing one-entry PHI nodes when I was debugging these changes, but I was working with an old version of the code. I'll try taking this out and if things aren't being cleaned up I'll figure out why.

3206–3208 ↗

(On Diff #36042)

I originally had it that way, but I wasn't sure it accomplished the same thing. If we convert the invoke to a call then it will unwind to whatever exception context happens to be around it, whereas my understanding was that if we get into this case it will be undefined behavior for the invoked function to throw an exception.

Then again, it did occur to me that some later pass is pretty likely to convert an invoke that unwinds to an unreachable instruction into a call.

I guess this gets at the question of what we're really trying to accomplish here. By inserting these unreachable instructions we're saying that if the code should never dynamically reach that point, but what if it does? Should we be inserting llvm.trap calls?

3292–3294 ↗

(On Diff #36042)

I see what you're saying, but I'm not sure I like OriginalMap any better. How about Clone2Orig?

3297–3298 ↗

(On Diff #36042)

Yes, that's true. I was thinking that by only inserting funclets as I see them it would save some search time for the earlier funclets encountered if we ever had a case with a lot of funclets. Thinking about it now, I'm not sure that's worth the trouble.

[JosephTremoulet]

lib/CodeGen/WinEHPrepare.cpp

3039–3053 ↗

(On Diff #36042)

Oh, yeah, huh, good point.

Thinking about that, I think that given a cleanupret/cleanupendpad:

• if it unwinds to a catchendpad, it's an edge to the grandparent (we give the catchendpad the color of the parent of the catch, and the catch it's exiting is the parent of the cleanup)
• if it unwinds to a cleanupendpad, it's an edge to the parent (we give the cleanupendpad the color of its cleanup, so this is a child cleanup unwinding to its parent cleanup)
• if it unwinds to a catchpad or a cleanup pad or a terminatepad, it's an edge to a sibling

Does that sound right?

3206–3208 ↗

(On Diff #36042)

It's my understanding that executing an 'unreachable' is UB and UB indicates conditions that the IR generator claimed could not possibly occur at runtime, and so the compiler has freedom to generate whatever dynamic behavior on that path is most convenient for it to generate. And that in this case it's most convenient to convert the invoke to a call that would unwind to whatever parent it happens to get.

Even if I'm wrong about some detail of UB in the above, given the fact that SimplifyCFG turns invokes-to-unreachable into calls, I think that's a pretty good indication that this is a legal transform.

And the langref explicitly spells out that a catchpad/cleanuppad dynamically following a cycle of unwinds is UB, so yes the IR producer in that case is giving their guarantee that it will never dynamically happen.

Honestly I think it would be preferable to mark the call nounwind while we're at it, and to also have a way to indicate that an endpad is nounwind (and SimplifyCFG has a comment to that effect, unless it got dropped in the refactoring). But it's my understanding that using call/unwind-to-caller is still legal though it's suboptimal.

What we're trying to accomplish is avoiding miscompiles if upstream passes have somehow (legally) bludgeoned the CFG into an unrecognizable derivative of itself. No matter what those upstream passes did, they must have preserved legal dynamic paths, so one or more of the acyclic paths that we see may be a preservation of one/some of the original legal dynamic paths. The langref precludes creating a well-behaved cyclic path in the original input because we don't have a way to encode that on the targets we're using this representation to target and neither do the source languages we're coming from have a way to express that so it's not a case we need to allow/handle.

3292–3294 ↗

(On Diff #36042)

Heh, I had originally suggested "OriginalMap or Clone2Orig", then I cut out the Clone2Orig suggestion before posting because I thought it would be confusing since the keys blocks aren't always clones. If that doesn't bother you, I'm fine with Clone2Orig. Or even IdentityMap if you still prefer it, I just wanted to point out that I got confused on first read. And I can't think of a better suggestion at the moment...

[andrew.w.kaylor]

lib/CodeGen/WinEHPrepare.cpp

3039–3053 ↗

(On Diff #36042)

That sounds right for IR generated in the expected ways. I'm not certain that it isn't possible to construct legal IR that does other things (like cleanret returning to an arbitrary block in the parent). I don't know why it would ever happen, but do our written rules disallow it?

[JosephTremoulet]

lib/CodeGen/WinEHPrepare.cpp

3039–3053 ↗

(On Diff #36042)

1. Regarding

if it unwinds to a catchendpad, it's an edge to the grandparent (we give the catchendpad the color of the parent of the catch, and the catch it's exiting is the parent of the cleanup)

I think that since the langref specifies:

It is undefined behavior to execute a catchendpad if, after the most recent execution of the normal successor edge of any catchpad chained to it, any other catchpad or cleanuppad has been executed but has not had a corresponding catchret/cleanupret/catchendpad/cleanupendpad executed

then it would be UB if the catchendpad were not ending a parent catch, and therefore having the grandparent color.

2. Regarding

if it unwinds to a cleanupendpad, it's an edge to the parent (we give the cleanupendpad the color of its cleanup, so this is a child cleanup unwinding to its parent cleanup)

I think that since the langref specifies

It is undefined behavior to execute a cleanupendpad if, after the most recent execution of its cleanuppad, any other cleanuppad or catchpad has been executed but has not had a corresponding cleanupret/catchret/cleanupendpad/catchendpad executed

then it would be UB if the cleanupendpad were not ending a parent cleanup, and therefore having the parent color.

3. Regarding

if it unwinds to a catchpad or a cleanup pad or a terminatepad, it's an edge to a sibling

This is a direct consequence of the coloring algorithm. For these sibling edges, I can't see why we would want to do anything other than translate them to the corresponding cloned-sibling edges between children of the cloned node.

4. Regarding

like cleanret returning to an arbitrary block in the parent

• A cleanupret successor edge is an unwind edge, and so can only target an EH pad. I actually am not seeing this in the langref, but it's certainly there in the verifier.
• A catchret targeting a block in the middle of the "wrong" handler is an interesting case. I think you're right that the langref doesn't preclude it, so I guess either we should find a wording that would preclude it or continue cloning at the point it targets? Continuing cloning would complicate the cycle detection -- the UB rules in the langref indicate that you can't enter a pad twice (execute the foopad twice without an intervening fooret/fooendpad) and that you can't return from a pad twice (execute the catchret twice without an intervening catchpad), and currently you're building the graph/tree/paths with the assumption that any node entered is entered via its entry pad and so detecting cycles just on the pad...

[JosephTremoulet]

lib/CodeGen/WinEHPrepare.cpp

3039–3053 ↗

(On Diff #36042)

Regarding

A catchret targeting a block in the middle of the "wrong" handler

We're actually already doing the extra cloning needed for that in cloneCommonBlocks (which runs just before this) -- we explicitly add the parent color to the catchret successor during coloring, so if that's "in the wrong handler" it will get two colors (the parent and the "wrong" one), and we'll clone so that the catchret only targets the parent; you should be able to assert at this point that every catchret (whose catchpad argument is the child catchpad) targets the parent.

[rnk]

Are we sure we need to handle this case with cloning? The intention of the design was that the rules around catchendpad and cleanupendpad would make it impossible for the optimizer to form invokes that don't unwind through the associated end pad.

For cleanupendpad, it directly consumes a token for the associated cleanuppad, so we can mark any invokes in a cleanuppad that don't transitively unwind to the cleanupendpad as unreachable.

For catchendpad, the rules about how catchpads are allowed to unwind should allow us to create a many-to-one association from catchpad to cleanupendpad and apply the same transformation to unreachable.

[JosephTremoulet]

In D13274#260936, @rnk wrote:

Are we sure we need to handle this case with cloning? The intention of the design was that the rules around catchendpad and cleanupendpad would make it impossible for the optimizer to form invokes that don't unwind through the associated end pad.

For cleanupendpad, it directly consumes a token for the associated cleanuppad, so we can mark any invokes in a cleanuppad that don't transitively unwind to the cleanupendpad as unreachable.

For catchendpad, the rules about how catchpads are allowed to unwind should allow us to create a many-to-one association from catchpad to cleanupendpad and apply the same transformation to unreachable.

We can do both the things you mention, and we do them in removeImplausibleTerminators. This cloning is about handling cases where what should be separate funclets branch to common code (like maybe they branch to a shared call void @abort() ; unreachable). If the common code itself has an invoke to another funclet (like maybe we started with the previous but then @abort got inlined), we can't tell which of the original two it is supposed to be a sub-funclet of, and so we clone it.

[andrew.w.kaylor]

As I've been reworking this to handle siblings, my test case has uncovered an ugly problem with the existing cloneCommonBlocks code.

Consider this test case:

define void @test13() personality i32 (...)* @__CxxFrameHandler3 {
entry:
  invoke void @f()
    to label %exit unwind label %outer

outer:
  %o = cleanuppad []
  invoke void @f()
    to label %outer.cont unwind label %left
outer.cont:
  invoke void @f()
    to label %unreachable unwind label %right
outer.end:
  cleanupendpad %o unwind to caller

left:
  %l = cleanuppad []
  invoke void @f()
    to label %left.cont unwind label %right
left.cont:
  cleanupret %l unwind label %outer.end

right:
  %r = catchpad []
    to label %right.catch unwind label %right.end
right.catch:
  invoke void @f()
    to label %unreachable unwind label %right.end
right.end:
  catchendpad unwind label %outer.end

unreachable:
  unreachable
}

colorFunclets() will assign the colors 'outer' (because of the cleanupret in 'left.cont') and 'left' (because of the catchendpad in 'right.end') to the 'outer.end' block. Subsequently, cloneCommonBlocks() will clone 'outer.end' to handle this and assign the color 'outer' to the clone and remove that color from the original, but it doesn't update the predecessors of 'outer.end' and so the cloned block is unreachable and the outer coloring is essentially lost.

I'm working on a solution to this problem now.

[majnemer]

In D13274#261224, @andrew.w.kaylor wrote:

As I've been reworking this to handle siblings, my test case has uncovered an ugly problem with the existing cloneCommonBlocks code.

Consider this test case:

define void @test13() personality i32 (...)* @__CxxFrameHandler3 {
entry:
  invoke void @f()
    to label %exit unwind label %outer

outer:
  %o = cleanuppad []
  invoke void @f()
    to label %outer.cont unwind label %left
outer.cont:
  invoke void @f()
    to label %unreachable unwind label %right
outer.end:
  cleanupendpad %o unwind to caller

left:
  %l = cleanuppad []
  invoke void @f()
    to label %left.cont unwind label %right
left.cont:
  cleanupret %l unwind label %outer.end

right:
  %r = catchpad []
    to label %right.catch unwind label %right.end
right.catch:
  invoke void @f()
    to label %unreachable unwind label %right.end
right.end:
  catchendpad unwind label %outer.end

unreachable:
  unreachable
}

colorFunclets() will assign the colors 'outer' (because of the cleanupret in 'left.cont') and 'left' (because of the catchendpad in 'right.end') to the 'outer.end' block. Subsequently, cloneCommonBlocks() will clone 'outer.end' to handle this and assign the color 'outer' to the clone and remove that color from the original, but it doesn't update the predecessors of 'outer.end' and so the cloned block is unreachable and the outer coloring is essentially lost.

I'm working on a solution to this problem now.

Isn't this IR busted because there is no associated cleanupendpad for %l?
Also, why does the cleanupendpad get more than one color? That sounds very strange because you'd never want to clone it without cloning %o... I'd expect that it either have it's own color or have cleanuppad's color (and propagate the colors feeding into cleanuppad).

[andrew.w.kaylor]

In D13274#261278, @majnemer wrote:

Isn't this IR busted because there is no associated cleanupendpad for %l?
Also, why does the cleanupendpad get more than one color? That sounds very strange because you'd never want to clone it without cloning %o... I'd expect that it either have it's own color or have cleanuppad's color (and propagate the colors feeding into cleanuppad).

This goes back to the motivation for this change set. The IR here is kind of busted, but if some paths are dynamically unreachable then it's potentially OK. Specifically, if the invoke in left.cont throws is caught by right.catch but the invoke of f() there neither throws nor returns, then it's kind of OK. The idea here is that some theoretical optimization pass combined blocks with unreachable terminators to create this state.

As for the cleanupendpad having more than one color, that's kind of a transitory issue, I think. Once the multiple parents issue has been sorted out, one of the colors should go away. Maybe this doesn't need to be resolved in cloneCommonBlocks() but it kind of alarmed me when I saw what was happening there, and I was hoping that maybe addressing it would simplify what needed to be done later to handle this case.

[andrew.w.kaylor]

-rebased
-adressed feedback from previous review
-added new test cases

I think the number of test cases I'm adding for cloning funclets with multiple parents justifies starting a new test file. The relevant tests in wineh-cloning.ll are currently duplicated for review purposes, but I'll remove those before checking in.

[JosephTremoulet]

Overall looks great, and thanks for doing this! I don't see where invoke->catchendpad edges are getting rewritten to the right parent, and there's a call to ->getUnwindDest() that I think should be a loop; other than that, just several minor nits and questions.

lib/CodeGen/WinEHPrepare.cpp

717 ↗

(On Diff #37951)

I don't understand this comment; we call this for more than just catchendpads...

724 ↗

(On Diff #37951)

if CloneParent is a catch that unwinds to another catch that unwinds to another catch that ... unwinds to a catchendpad, and that catchendpad is UnwindDest, then do you still want to take this path? I.e. I think instead of a single ->getUnwindDest() here, you may want a loop that doesn't terminate until it finds an unwind dest that's a catchendpad.

736 ↗

(On Diff #37951)

Confusing comment again; the thing that unwinds is an arbitrary EH pad, not necessarily a catchendpad, right?

762 ↗

(On Diff #37951)

same as above

811 ↗

(On Diff #37951)

Did you intend to update this pre-checkin? Fine with me to check in the FIXME as-is, just wanted to make sure it was intentional.

856–860 ↗

(On Diff #37951)

Do the new tests cover these cases? I.e. where funclet A includes a branch to block Shared, and funclet B has child catch funclet C, and Shared is the target of the catchret from C back to B?

862–865 ↗

(On Diff #37951)

does "caller" here mean the same thing as "parent"?

945 ↗

(On Diff #37951)

I think you may need to check if CloneTerminator is an invoke and UnwindDest is a catchendpad, and enforce that the catchendpad is in the parent if so.

1043–1045 ↗

(On Diff #37951)

Could this be assert(!FuncletParents[ClonedFunclet].count(Parent))?

1062–1063 ↗

(On Diff #37951)

This comment doesn't match the code (but the comment on line 1075 does) -- siblings aren't handled here.

1138–1139 ↗

(On Diff #37951)

Is cleanupendpad ever a parent-to-child edge? I'd have thought no.

1212 ↗

(On Diff #37951)

I would have thought we could assert that Parents[UnwindDest].size() == 1 here, no (i.e. we should have already resolved ancestry path for all the siblings, and the above checks should ensure this is a sibling)?

1225 ↗

(On Diff #37951)

As on line 1212, I'd have thought we could assume/assert that siblings have a single parent here.

1354 ↗

(On Diff #37951)

You can remove this now, right?

1465–1466 ↗

(On Diff #37951)

Worth asserting FuncletCloningRequired?

1474–1485 ↗

(On Diff #37951)

I see you reset BlockColors[BB] to the single parent here, but I don't see you remove BB from FuncletBlocks[OtherParent] for all the other parents. Should you be doing that?

1476–1481 ↗

(On Diff #37951)

Seems like this should assert there's only one CatchParent (in debug) and/or break out of the loop as soon as it finds one (in release).

Also, nit: You're getting the color of the parent of the catchpad that is a predecessor of the endpad, so the name CatchParent confused me a bit (I assumed it would be the parent of the catch); maybe CatchPred or even just CatchPad?

1529–1530 ↗

(On Diff #37951)

With this and all the other debug output, is there something better to print to identify the block than ->getName()? That works great for hand-written tests, but for debugging real-world failures I'd expect a front-end to either have not named these blocks (so this will be empty string if I'm reading the implementation correctly) or to have given them all the same name, like "catch.dispatch", so the printout wouldn't be helpful (again, if I'm reading getName() correctly). Printing the block's address would identify them uniquely, but then wouldn't correspond to anything in a dump of the function...

To be clear, I'm fine with this change as-is if that's just what's available, I'm really just asking to know what's available when I want to add similar debug traces in the future.

test/CodeGen/WinEH/wineh-cloning.ll

301 ↗

(On Diff #37951)

Looks like a copy-paste error: I think you want [[I_R]] here instead of [[I_R:\%.+]]

test/CodeGen/WinEH/wineh-multi-parent-cloning.ll

71 ↗

(On Diff #37951)

[[I_R]]

113–114 ↗

(On Diff #37951)

I'm not seeing why left is a parent of right. I thought that "is a parent of" meant "has an invoke or catchendpad that unwinds to, or has a child cleanuppad whose cleanupret/cleanupendpad unwinds to", and I don't see that happening anywhere in this test.

119–121 ↗

(On Diff #37951)

Did we stop making this clone with rL250534?

506–507 ↗

(On Diff #37951)

Why does that happen?

[andrew.w.kaylor]

lib/CodeGen/WinEHPrepare.cpp

717 ↗

(On Diff #37951)

Oops. Slipped through refactoring.

724 ↗

(On Diff #37951)

Yes, you're right. I'll add a test case to cover that.

811 ↗

(On Diff #37951)

I'll probably do it before checkin, but I felt like I needed to draw the line somewhere to get these changes back up for review.

856–860 ↗

(On Diff #37951)

I don't think so. I'll add something.

862–865 ↗

(On Diff #37951)

No. What I meant is that the unwind destination is null. I was trying to use the same terminology the IR dumps use ("unwind to caller"). I guess that's not entirely clear.

945 ↗

(On Diff #37951)

Hmmm. That's a bit sticky. If the funclet being cloned is a catchpad that unwinds to a catchendpad, I'm cloning the catchendpad, so if the invoke occurs in that sort of funclet it should get remapped naturally (though it's possible that the VMap isn't being updated properly in the case where the cloned catchendpad has to be associated with the original funclet rather than the clone).

On the other hand, if the funclet being cloned is a catchpad that unwinds to another catchpad, the unwind destination for the invoke may need to be a catchendpad clone that hasn't been created yet. I think I'll need to handle this case in the same place that I'm doing the sibling terminator fix-up.

More test cases....

1043–1045 ↗

(On Diff #37951)

No, because FuncletParents maps to a vector, not a set.

I could make it

assert(!std::count(FuncletParents[ClonedFunclet].begin(),

FuncletParents[ClonedFunclet].end(),
Parent));

if you think that's easier to comprehend at a glance.

1062–1063 ↗

(On Diff #37951)

Yeah, I'm not sure what I was thinking here.

1138–1139 ↗

(On Diff #37951)

Maybe not. Part of what's given me trouble in this change set is figuring out which cases that I can sneak past the verifier are legitimate things that could happen and which just don't make any sense. I'm not sure I even had a case that looked like this. I'll see if I can come up with something and if I do I'll report back.

1212 ↗

(On Diff #37951)

I don't think so. If a funclet has three parents, then the first time we encounter it we'll clone it, but the original funclet will still have two parents.

1354 ↗

(On Diff #37951)

Yes.

1465–1466 ↗

(On Diff #37951)

Yes, probably so.

1474–1485 ↗

(On Diff #37951)

Yeah, probably so.

1476–1481 ↗

(On Diff #37951)

The verifier checks that condition, but I suppose it wouldn't hurt to assert it here too. I did mean to break out of the loop when I found the catch parent.

1529–1530 ↗

(On Diff #37951)

I would expect that anytime you're trying to use the debug option you'd have names for all the blocks. They may be very similar names (catch.dipatch. catch.dipatch.1, etc.), but they will be unique.

I'm not sure if there's a way to match what the IR dumper does in the case where the blocks are unnamed. I don't know a better way to get a useful label.

test/CodeGen/WinEH/wineh-multi-parent-cloning.ll

113–114 ↗

(On Diff #37951)

This comments seems to be left over from an earlier version of the test.

119–121 ↗

(On Diff #37951)

Yes, I think so.

506–507 ↗

(On Diff #37951)

I believe it's because of the cleanupret in inner.sibling unwinding to left.end, which unwinds to right. I'll take a closer look and see exactly where this is happening and why.

It may be that this isn't happening anymore since I added the code to prevent cloning of catchendpads.

[JosephTremoulet]

lib/CodeGen/WinEHPrepare.cpp

862–865 ↗

(On Diff #37951)

Ah, ok. I think what confused me was the phrase "its caller", since you're referring to the caller of the function, and I took "it" to mean the cleanup; just changing "its caller" to "the caller" or "the calling function", or even just changing "unwinds to its caller" to "unwinds to caller" so it would more obviously match the IR text, would have cleared it up for me.

945 ↗

(On Diff #37951)

Ugh, yeah. If it's cleaner, you could try to mess with the cloning order so that you handle the unwinds-to-catchendpad catch before you handle any of the unwinds-to-catchpad catches. Not at all clear to me that that would be cleaner, just wanted to toss out the idea...

1043–1045 ↗

(On Diff #37951)

Oh, yeah, thanks for explaining. No, I think what you have is just as easy to comprehend as std::count.

1476–1481 ↗

(On Diff #37951)

FWIW, relying on the verifier makes sense to me.

[JosephTremoulet]

Another thought: the only reason I gave catchendpads the parent color was because it simplified the coloring algorithm a bit. But we could switch to another convention like giving a catchendpad the color of the catchpad that unwinds directly to it; that would only complicate the coloring algorithm a little (when visiting a catchpad we'd have to scroll through the chain to find the catchendpad and give its successor the parent color), so if it would drastically simplify this part it might be worthwhile.

[andrew.w.kaylor]

Added new test cases.
Added support for catchret in cloned funclets.
Added support for invokes that unwind to parent EH pads.

[JosephTremoulet]

LGTM, thanks for all the updates and new tests!

lib/CodeGen/WinEHPrepare.cpp

928 ↗

(On Diff #39098)

MIssing right-paren: "catch pad)."

1634 ↗

(On Diff #39098)

typo: removinv -> removing

1737–1738 ↗

(On Diff #39098)

typo: "reached from a reached from a" -> "reached from a"

[chapuni]

Reverted in r252279.

We should assume that iterating pointer key values in std::set and std::map would be nondeterministic.

[andrew.w.kaylor]

I understood that iterating sets and maps was not deterministic and thought I had accounted for that. There are several places in this code where the non-determinism is OK because it doesn't lead to non-deterministic output. I just had one bug where I was looking at unwind edges that hadn't been processed yet.

In any event, reverting was the right thing to do. I should have this ready to go back in shortly.

lib/CodeGen/WinEHPrepare.cpp

856–860 ↗

(On Diff #37951)

This isn't working and I'm not sure how it should be handled. Consider the following function:

define void @test13() personality i32 (...)* @__CxxFrameHandler3 {
entry:
  invoke void @f()
    to label %invoke.cont unwind label %left
invoke.cont:
  invoke void @f()
    to label %exit unwind label %right
left:
  %l = catchpad []
    to label %left.cont unwind label %left.end
left.cont:
  invoke void @f()
    to label %left.ret unwind label %inner
left.ret:
  catchret %l to label %invoke.cont
left.end:
  catchendpad unwind to caller
right:
  %r = catchpad []
    to label %right.catch unwind label %right.end
right.catch:
  invoke void @f()
    to label %right.ret unwind label %inner
right.ret:
  catchret %r to label %exit
right.end:
  catchendpad unwind to caller
shared:
  call void @h(i32 0)
  unreachable
inner:
  %i = catchpad []
    to label %inner.catch unwind label %inner.end
inner.catch:
  call void @h(i32 1)
  catchret %i to label %shared
inner.end:
  catchendpad unwind label %left.end
exit:
  ret void
}

The existing funclet coloring code will recognize that it needs a copy of %shared for both %left and %right, but because both are reached from the same catchret instruction one of the clones will be unreachable following cloneCommonBlocks(). Then when my new code gets to the point of cloning %inner it will remove the catchret in %inner.catch for whichever of the parents received the unreachable clone of %shared (because the reachable %shared belongs to the other funclet).

I could instead make yet another clone of %shared at this point, but that really just pushes the problem to the next block in cases where %shared has successors. What I really need to do is to be able to find the unreachable clone. Does that sound reasonable?

[andrew.w.kaylor]

lib/CodeGen/WinEHPrepare.cpp

856–860 ↗

(On Diff #37951)

This was an old comment. I'm not sure why it only showed up now.

llvm/trunk/lib/AsmParser/LLParser.cpp

if (ParseToken(lltok::kw_unwind, "expected 'unwind' in catchendpad"))
     return true;
 
   BasicBlock *UnwindBB = nullptr;
   if (Lex.getKind() == lltok::kw_to) {
     Lex.Lex();
     if (Lex.getKind() == lltok::kw_caller) {
       Lex.Lex();
     } else {
-      return true;
+      return Error(Lex.getLoc(),
+                   "'to' must be followed by 'caller' in catchendpad");
     }
   } else {
     if (ParseTypeAndBasicBlock(UnwindBB, PFS)) {
       return true;
     }
   }
 
   Inst = CleanupEndPadInst::Create(cast<CleanupPadInst>(CleanupPad), UnwindBB);

llvm/trunk/lib/CodeGen/WinEHPrepare.cpp

private:
   void replaceUseWithLoad(Value *V, Use &U, AllocaInst *&SpillSlot,
                           DenseMap<BasicBlock *, Value *> &Loads, Function &F);
   void demoteNonlocalUses(Value *V, std::set<BasicBlock *> &ColorsForBB,
                           Function &F);
   bool prepareExplicitEH(Function &F,
                          SmallVectorImpl<BasicBlock *> &EntryBlocks);
   void replaceTerminatePadWithCleanup(Function &F);
   void colorFunclets(Function &F, SmallVectorImpl<BasicBlock *> &EntryBlocks);
+  void resolveFuncletAncestry(Function &F,
+                              SmallVectorImpl<BasicBlock *> &EntryBlocks);
+  void resolveFuncletAncestryForPath(
+      Function &F, SmallVectorImpl<BasicBlock *> &FuncletPath,
+      std::map<BasicBlock *, BasicBlock *> &IdentityMap);
+  void makeFuncletEdgeUnreachable(BasicBlock *Parent, BasicBlock *Child);
+  BasicBlock *cloneFuncletForParent(Function &F, BasicBlock *FuncletEntry,
+                                    BasicBlock *Parent);
+  void updateTerminatorsAfterFuncletClone(
+      Function &F, BasicBlock *OrigFunclet, BasicBlock *CloneFunclet,
+      BasicBlock *OrigBlock, BasicBlock *CloneBlock, BasicBlock *CloneParent,
+      ValueToValueMapTy &VMap,
+      std::map<BasicBlock *, BasicBlock *> &Orig2Clone);
+
   void demotePHIsOnFunclets(Function &F);
   void demoteUsesBetweenFunclets(Function &F);
   void demoteArgumentUses(Function &F);
   void cloneCommonBlocks(Function &F,
                          SmallVectorImpl<BasicBlock *> &EntryBlocks);
   void removeImplausibleTerminators(Function &F);
   void cleanupPreparedFunclets(Function &F);
   void verifyPreparedFunclets(Function &F);
 
   // All fields are reset by runOnFunction.
   EHPersonality Personality = EHPersonality::Unknown;
 
   std::map<BasicBlock *, std::set<BasicBlock *>> BlockColors;
   std::map<BasicBlock *, std::set<BasicBlock *>> FuncletBlocks;
-  std::map<BasicBlock *, std::set<BasicBlock *>> FuncletChildren;
+  std::map<BasicBlock *, std::vector<BasicBlock *>> FuncletChildren;
+  std::map<BasicBlock *, std::vector<BasicBlock *>> FuncletParents;
+
+  // This is a flag that indicates an uncommon situation where we need to
+  // clone funclets has been detected.
+  bool FuncletCloningRequired = false;
+  // When a funclet with multiple parents contains a catchret, the block to
+  // which it returns will be cloned so that there is a copy in each parent
+  // but one of the copies will not be properly linked to the catchret and
+  // in most cases will have no predecessors.  This double map allows us
+  // to find these cloned blocks when we clone the child funclet.
+  std::map<BasicBlock *, std::map<BasicBlock *, BasicBlock*>> EstrangedBlocks;
 };
 
 } // end anonymous namespace
 
 char WinEHPrepare::ID = 0;
 INITIALIZE_TM_PASS(WinEHPrepare, "winehprepare", "Prepare Windows exceptions",
                    false, false)
 
for (BasicBlock &BB : F) {
     // instructions.
     TPI->eraseFromParent();
   }
 }
 
 static void
 colorFunclets(Function &F, SmallVectorImpl<BasicBlock *> &EntryBlocks,
               std::map<BasicBlock *, std::set<BasicBlock *>> &BlockColors,
-              std::map<BasicBlock *, std::set<BasicBlock *>> &FuncletBlocks,
-              std::map<BasicBlock *, std::set<BasicBlock *>> &FuncletChildren) {
+              std::map<BasicBlock *, std::set<BasicBlock *>> &FuncletBlocks) {
   SmallVector<std::pair<BasicBlock *, BasicBlock *>, 16> Worklist;
   BasicBlock *EntryBlock = &F.getEntryBlock();
 
   // Build up the color map, which maps each block to its set of 'colors'.
   // For any block B, the "colors" of B are the set of funclets F (possibly
   // including a root "funclet" representing the main function), such that
   // F will need to directly contain B or a copy of B (where the term "directly
   // contain" is used to distinguish from being "transitively contained" in
   // a nested funclet).
   // Use a CFG walk driven by a worklist of (block, color) pairs.  The "color"
   // sets attached during this processing to a block which is the entry of some
   // funclet F is actually the set of F's parents -- i.e. the union of colors
   // of all predecessors of F's entry.  For all other blocks, the color sets
   // are as defined above.  A post-pass fixes up the block color map to reflect
   // the same sense of "color" for funclet entries as for other blocks.
 
+  DEBUG_WITH_TYPE("winehprepare-coloring", dbgs() << "\nColoring funclets for "
+                                                  << F.getName() << "\n");
+
   Worklist.push_back({EntryBlock, EntryBlock});
 
   while (!Worklist.empty()) {
     BasicBlock *Visiting;
     BasicBlock *Color;
     std::tie(Visiting, Color) = Worklist.pop_back_val();
+    DEBUG_WITH_TYPE("winehprepare-coloring",
+                    dbgs() << "Visiting " << Visiting->getName() << ", "
+                           << Color->getName() << "\n");
     Instruction *VisitingHead = Visiting->getFirstNonPHI();
     if (VisitingHead->isEHPad() && !isa<CatchEndPadInst>(VisitingHead) &&
         !isa<CleanupEndPadInst>(VisitingHead)) {
       // Mark this as a funclet head as a member of itself.
       FuncletBlocks[Visiting].insert(Visiting);
       // Queue exits (i.e. successors of rets/endpads) with the parent color.
       // Skip any exits that are catchendpads, since the parent color must then
       // represent one of the catches chained to that catchendpad, but the
       // catchendpad should get the color of the common parent of all its
       // chained catches (i.e. the grandparent color of the current pad).
       // We don't need to worry abou catchendpads going unvisited, since the
       // catches chained to them must have unwind edges to them by which we will
       // visit them.
       for (User *U : VisitingHead->users()) {
         if (auto *Exit = dyn_cast<TerminatorInst>(U)) {
           for (BasicBlock *Succ : successors(Exit->getParent()))
             if (!isa<CatchEndPadInst>(*Succ->getFirstNonPHI()))
-              if (BlockColors[Succ].insert(Color).second)
+              if (BlockColors[Succ].insert(Color).second) {
+                DEBUG_WITH_TYPE("winehprepare-coloring",
+                                dbgs() << "  Assigned color \'"
+                                       << Color->getName() << "\' to block \'"
+                                       << Succ->getName() << "\'.\n");
                 Worklist.push_back({Succ, Color});
               }
         }
+      }
       // Handle CatchPad specially since its successors need different colors.
       if (CatchPadInst *CatchPad = dyn_cast<CatchPadInst>(VisitingHead)) {
         // Visit the normal successor with the color of the new EH pad, and
         // visit the unwind successor with the color of the parent.
         BasicBlock *NormalSucc = CatchPad->getNormalDest();
         if (BlockColors[NormalSucc].insert(Visiting).second) {
+          DEBUG_WITH_TYPE("winehprepare-coloring",
+                          dbgs() << "  Assigned color \'" << Visiting->getName()
+                                 << "\' to block \'" << NormalSucc->getName()
+                                 << "\'.\n");
           Worklist.push_back({NormalSucc, Visiting});
         }
         BasicBlock *UnwindSucc = CatchPad->getUnwindDest();
         if (BlockColors[UnwindSucc].insert(Color).second) {
+          DEBUG_WITH_TYPE("winehprepare-coloring",
+                          dbgs() << "  Assigned color \'" << Color->getName()
+                                 << "\' to block \'" << UnwindSucc->getName()
+                                 << "\'.\n");
           Worklist.push_back({UnwindSucc, Color});
         }
         continue;
       }
       // Switch color to the current node, except for terminate pads which
       // have no bodies and only unwind successors and so need their successors
       // visited with the color of the parent.
       if (!isa<TerminatePadInst>(VisitingHead))
for (BasicBlock *Succ : successors(Visiting)) {
       if (isa<CatchEndPadInst>(Succ->getFirstNonPHI())) {
         // The catchendpad needs to be visited with the parent's color, not
         // the current color.  This will happen in the code above that visits
         // any catchpad unwind successor with the parent color, so we can
         // safely skip this successor here.
         continue;
       }
       if (BlockColors[Succ].insert(Color).second) {
+        DEBUG_WITH_TYPE("winehprepare-coloring",
+                        dbgs() << "  Assigned color \'" << Color->getName()
+                               << "\' to block \'" << Succ->getName()
+                               << "\'.\n");
         Worklist.push_back({Succ, Color});
       }
     }
   }
+}
+
+static BasicBlock *getEndPadForCatch(CatchPadInst *Catch) {
+  // The catch may have sibling catches.  Follow the unwind chain until we get
+  // to the catchendpad.
+  BasicBlock *NextUnwindDest = Catch->getUnwindDest();
+  auto *UnwindTerminator = NextUnwindDest->getTerminator();
+  while (auto *NextCatch = dyn_cast<CatchPadInst>(UnwindTerminator)) {
+    NextUnwindDest = NextCatch->getUnwindDest();
+    UnwindTerminator = NextUnwindDest->getTerminator();
+  }
+  // The last catch in the chain must unwind to a catchendpad.
+  assert(isa<CatchEndPadInst>(UnwindTerminator));
+  return NextUnwindDest;
+}
+
+static void updateClonedEHPadUnwindToParent(
+    BasicBlock *UnwindDest, BasicBlock *OrigBlock, BasicBlock *CloneBlock,
+    std::vector<BasicBlock *> &OrigParents, BasicBlock *CloneParent) {
+  auto updateUnwindTerminator = [](BasicBlock *BB) {
+    auto *Terminator = BB->getTerminator();
+    if (isa<CatchEndPadInst>(Terminator) ||
+        isa<CleanupEndPadInst>(Terminator)) {
+      removeUnwindEdge(BB);
+    } else {
+      // If the block we're updating has a cleanupendpad or cleanupret
+      // terminator, we just want to replace that terminator with an
+      // unreachable instruction.
+      assert(isa<CleanupEndPadInst>(Terminator) ||
+             isa<CleanupReturnInst>(Terminator));
+      // Loop over all of the successors, removing the block's entry from any
+      // PHI nodes.
+      for (succ_iterator SI = succ_begin(BB), SE = succ_end(BB); SI != SE; ++SI)
+        (*SI)->removePredecessor(BB);
+      // Remove the terminator and replace it with an unreachable instruction.
+      BB->getTerminator()->eraseFromParent();
+      new UnreachableInst(BB->getContext(), BB);
+    }
+  };
+
+  assert(UnwindDest->isEHPad());
+  // There are many places to which this EH terminator can unwind and each has
+  // slightly different rules for whether or not it fits with the given
+  // location.
+  auto *EHPadInst = UnwindDest->getFirstNonPHI();
+  if (auto *CEP = dyn_cast<CatchEndPadInst>(EHPadInst)) {
+    auto *CloneParentCatch =
+        dyn_cast<CatchPadInst>(CloneParent->getFirstNonPHI());
+    if (!CloneParentCatch ||
+        getEndPadForCatch(CloneParentCatch) != UnwindDest) {
+      DEBUG_WITH_TYPE(
+          "winehprepare-coloring",
+          dbgs() << "      removing unwind destination of clone block \'"
+                 << CloneBlock->getName() << "\'.\n");
+      updateUnwindTerminator(CloneBlock);
+    }
+    // It's possible that the catch end pad is a legal match for both the clone
+    // and the original, so they must be checked separately.  If the original
+    // funclet will still have multiple parents after the current clone parent
+    // is removed, we'll leave its unwind terminator until later.
+    assert(OrigParents.size() >= 2);
+    if (OrigParents.size() != 2)
+      return;
+
+    // If the original funclet will have a single parent after the clone parent
+    // is removed, check that parent's unwind destination.
+    assert(OrigParents.front() == CloneParent ||
+           OrigParents.back() == CloneParent);
+    BasicBlock *OrigParent;
+    if (OrigParents.front() == CloneParent)
+      OrigParent = OrigParents.back();
+    else
+      OrigParent = OrigParents.front();
+
+    auto *OrigParentCatch =
+        dyn_cast<CatchPadInst>(OrigParent->getFirstNonPHI());
+    if (!OrigParentCatch || getEndPadForCatch(OrigParentCatch) != UnwindDest) {
+      DEBUG_WITH_TYPE(
+          "winehprepare-coloring",
+          dbgs() << "      removing unwind destination of original block \'"
+                 << OrigBlock << "\'.\n");
+      updateUnwindTerminator(OrigBlock);
+    }
+  } else if (auto *CleanupEnd = dyn_cast<CleanupEndPadInst>(EHPadInst)) {
+    // If the EH terminator unwinds to a cleanupendpad, that cleanupendpad
+    // must be ending a cleanuppad of either our clone parent or one
+    // one of the parents of the original funclet.
+    auto *CloneParentCP =
+        dyn_cast<CleanupPadInst>(CloneParent->getFirstNonPHI());
+    auto *EndedCP = CleanupEnd->getCleanupPad();
+    if (EndedCP == CloneParentCP) {
+      // If it is ending the cleanuppad of our cloned parent, then we
+      // want to remove the unwind destination of the EH terminator that
+      // we associated with the original funclet.
+      assert(isa<CatchEndPadInst>(OrigBlock->getFirstNonPHI()));
+      DEBUG_WITH_TYPE(
+          "winehprepare-coloring",
+          dbgs() << "      removing unwind destination of original block \'"
+                 << OrigBlock->getName() << "\'.\n");
+      updateUnwindTerminator(OrigBlock);
+    } else {
+      // If it isn't ending the cleanuppad of our clone parent, then we
+      // want to remove the unwind destination of the EH terminator that
+      // associated with our cloned funclet.
+      assert(isa<CatchEndPadInst>(CloneBlock->getFirstNonPHI()));
+      DEBUG_WITH_TYPE(
+          "winehprepare-coloring",
+          dbgs() << "      removing unwind destination of clone block \'"
+                 << CloneBlock->getName() << "\'.\n");
+      updateUnwindTerminator(CloneBlock);
+    }
+  } else {
+    // If the EH terminator unwinds to a catchpad, cleanuppad or
+    // terminatepad that EH pad must be a sibling of the funclet we're
+    // cloning.  We'll clone it later and update one of the catchendpad
+    // instrunctions that unwinds to it at that time.
+    assert(isa<CatchPadInst>(EHPadInst) || isa<CleanupPadInst>(EHPadInst) ||
+           isa<TerminatePadInst>(EHPadInst));
+  }
+}
+
+// If the terminator is a catchpad, we must also clone the catchendpad to which
+// it unwinds and add this to the clone parent's block list.  The catchendpad
+// unwinds to either its caller, a sibling EH pad, a cleanup end pad in its
+// parent funclet or a catch end pad in its grandparent funclet (which must be
+// coupled with the parent funclet).  If it has no unwind destination
+// (i.e. unwind to caller), there is nothing to be done. If the unwind
+// destination is a sibling EH pad, we will update the terminators later (in
+// resolveFuncletAncestryForPath).  If it unwinds to a cleanup end pad or a
+// catch end pad and this end pad corresponds to the clone parent, we will
+// remove the unwind destination in the original catchendpad. If it unwinds to
+// a cleanup end pad or a catch end pad that does not correspond to the clone
+// parent, we will remove the unwind destination in the cloned catchendpad.
+static void updateCatchTerminators(
+    Function &F, CatchPadInst *OrigCatch, CatchPadInst *CloneCatch,
+    std::vector<BasicBlock *> &OrigParents, BasicBlock *CloneParent,
+    ValueToValueMapTy &VMap,
+    std::map<BasicBlock *, std::set<BasicBlock *>> &BlockColors,
+    std::map<BasicBlock *, std::set<BasicBlock *>> &FuncletBlocks) {
+  // If we're cloning a catch pad that unwinds to a catchendpad, we also
+  // need to clone the catchendpad.  The coloring algorithm associates
+  // the catchendpad block with the funclet's parent, so we have some work
+  // to do here to figure out whether the original belongs to the clone
+  // parent or one of the original funclets other parents (it might have
+  // more than one at this point).  In either case, we might also need to
+  // remove the unwind edge if the catchendpad doesn't unwind to a block
+  // in the right grandparent funclet.
+  Instruction *I = CloneCatch->getUnwindDest()->getFirstNonPHI();
+  if (auto *CEP = dyn_cast<CatchEndPadInst>(I)) {
+    assert(BlockColors[CEP->getParent()].size() == 1);
+    BasicBlock *CEPFunclet = *(BlockColors[CEP->getParent()].begin());
+    BasicBlock *CEPCloneParent = nullptr;
+    CatchPadInst *PredCatch = nullptr;
+    if (CEPFunclet == CloneParent) {
+      // The catchendpad is in the clone parent, so we need to clone it
+      // and associate the clone with the original funclet's parent.  If
+      // the original funclet had multiple parents, we'll add it to the
+      // first parent that isn't the clone parent.  The logic in
+      // updateClonedEHPadUnwindToParent() will only remove the unwind edge
+      // if there is only one parent other than the clone parent, so we don't
+      // need to verify the ancestry.  The catchendpad will eventually be
+      // cloned into the correct parent and all invalid unwind edges will be
+      // removed.
+      for (auto *Parent : OrigParents) {
+        if (Parent != CloneParent) {
+          CEPCloneParent = Parent;
+          break;
+        }
+      }
+      PredCatch = OrigCatch;
+    } else {
+      CEPCloneParent = CloneParent;
+      PredCatch = CloneCatch;
+    }
+    assert(CEPCloneParent && PredCatch);
+    DEBUG_WITH_TYPE("winehprepare-coloring",
+                    dbgs() << "  Cloning catchendpad \'"
+                           << CEP->getParent()->getName() << "\' for funclet \'"
+                           << CEPCloneParent->getName() << "\'.\n");
+    BasicBlock *ClonedCEP = CloneBasicBlock(
+        CEP->getParent(), VMap, Twine(".from.", CEPCloneParent->getName()));
+    // Insert the clone immediately after the original to ensure determinism
+    // and to keep the same relative ordering of any funclet's blocks.
+    ClonedCEP->insertInto(&F, CEP->getParent()->getNextNode());
+    PredCatch->setUnwindDest(ClonedCEP);
+    FuncletBlocks[CEPCloneParent].insert(ClonedCEP);
+    BlockColors[ClonedCEP].insert(CEPCloneParent);
+    DEBUG_WITH_TYPE("winehprepare-coloring",
+                    dbgs() << "    Assigning color \'"
+                           << CEPCloneParent->getName() << "\' to block \'"
+                           << ClonedCEP->getName() << "\'.\n");
+    auto *ClonedCEPInst = cast<CatchEndPadInst>(ClonedCEP->getTerminator());
+    if (auto *Dest = ClonedCEPInst->getUnwindDest())
+      updateClonedEHPadUnwindToParent(Dest, OrigCatch->getUnwindDest(),
+                                      CloneCatch->getUnwindDest(), OrigParents,
+                                      CloneParent);
+  }
+}
+
+// While we are cloning a funclet because it has multiple parents, we will call
+// this routine to update the terminators for the original and cloned copies
+// of each basic block.  All blocks in the funclet have been clone by this time.
+// OrigBlock and CloneBlock will be identical except for their block label.
+//
+// If the terminator is a catchpad, we must also clone the catchendpad to which
+// it unwinds and in most cases update either the original catchendpad or the
+// clone.  See the updateCatchTerminators() helper routine for details.
+//
+// If the terminator is a catchret its successor is a block in its parent
+// funclet.  If the instruction returns to a block in the parent for which the
+// cloned funclet was created, the terminator in the original block must be
+// replaced by an unreachable instruction.  Otherwise the terminator in the
+// clone block must be replaced by an unreachable instruction.
+//
+// If the terminator is a cleanupret or cleanupendpad it either unwinds to
+// caller or unwinds to a sibling EH pad, a cleanup end pad in its parent
+// funclet or a catch end pad in its grandparent funclet (which must be
+// coupled with the parent funclet).  If it unwinds to caller there is
+// nothing to be done. If the unwind destination is a sibling EH pad, we will
+// update the terminators later (in resolveFuncletAncestryForPath).  If it
+// unwinds to a cleanup end pad or a catch end pad and this end pad corresponds
+// to the clone parent, we will replace the terminator in the original block
+// with an unreachable instruction. If it unwinds to a cleanup end pad or a
+// catch end pad that does not correspond to the clone parent, we will replace
+// the terminator in the clone block with an unreachable instruction.
+//
+// If the terminator is an invoke instruction, it unwinds either to a child
+// EH pad, a cleanup end pad in the current funclet, or a catch end pad in a
+// parent funclet (which ends either the current catch pad or a sibling
+// catch pad).  If it unwinds to a child EH pad, the child will have multiple
+// parents after this funclet is cloned and this case will be handled later in
+// the resolveFuncletAncestryForPath processing.  If it unwinds to a
+// cleanup end pad in the current funclet, the instruction remapping during
+// the cloning process should have already mapped the unwind destination to
+// the cloned copy of the cleanup end pad.  If it unwinds to a catch end pad
+// there are two possibilities: either the catch end pad is the unwind
+// destination for the catch pad we are currently cloning or it is the unwind
+// destination for a sibling catch pad.  If it it the unwind destination of the
+// catch pad we are cloning, we need to update the cloned invoke instruction
+// to unwind to the cloned catch end pad.  Otherwise, we will handle this
+// later (in resolveFuncletAncestryForPath).
+void WinEHPrepare::updateTerminatorsAfterFuncletClone(
+    Function &F, BasicBlock *OrigFunclet, BasicBlock *CloneFunclet,
+    BasicBlock *OrigBlock, BasicBlock *CloneBlock, BasicBlock *CloneParent,
+    ValueToValueMapTy &VMap, std::map<BasicBlock *, BasicBlock *> &Orig2Clone) {
+  // If the cloned block doesn't have an exceptional terminator, there is
+  // nothing to be done here.
+  TerminatorInst *CloneTerminator = CloneBlock->getTerminator();
+  if (!CloneTerminator->isExceptional())
+    return;
+
+  if (auto *CloneCatch = dyn_cast<CatchPadInst>(CloneTerminator)) {
+    // A cloned catch pad has a lot of wrinkles, so we'll call a helper function
+    // to update this case.
+    auto *OrigCatch = cast<CatchPadInst>(OrigBlock->getTerminator());
+    updateCatchTerminators(F, OrigCatch, CloneCatch,
+                           FuncletParents[OrigFunclet], CloneParent, VMap,
+                           BlockColors, FuncletBlocks);
+  } else if (auto *CRI = dyn_cast<CatchReturnInst>(CloneTerminator)) {
+    if (FuncletBlocks[CloneParent].count(CRI->getSuccessor())) {
+      BasicBlock *OrigParent;
+      // The original funclet may have more than two parents, but that's OK.
+      // We just need to remap the original catchret to any of the parents.
+      // All of the parents should have an entry in the EstrangedBlocks map
+      // if any of them do.
+      if (FuncletParents[OrigFunclet].front() == CloneParent)
+        OrigParent = FuncletParents[OrigFunclet].back();
+      else
+        OrigParent = FuncletParents[OrigFunclet].front();
+      for (succ_iterator SI = succ_begin(OrigBlock), SE = succ_end(OrigBlock);
+           SI != SE; ++SI)
+        (*SI)->removePredecessor(OrigBlock);
+      BasicBlock *LostBlock = EstrangedBlocks[OrigParent][CRI->getSuccessor()];
+      auto *OrigCatchRet = cast<CatchReturnInst>(OrigBlock->getTerminator());
+      if (LostBlock) {
+        OrigCatchRet->setSuccessor(LostBlock);
+      } else {
+        OrigCatchRet->eraseFromParent();
+        new UnreachableInst(OrigBlock->getContext(), OrigBlock);
+      }
+    } else {
+      for (succ_iterator SI = succ_begin(CloneBlock), SE = succ_end(CloneBlock);
+           SI != SE; ++SI)
+        (*SI)->removePredecessor(CloneBlock);
+      BasicBlock *LostBlock = EstrangedBlocks[CloneParent][CRI->getSuccessor()];
+      if (LostBlock) {
+        CRI->setSuccessor(LostBlock);
+      } else {
+        CRI->eraseFromParent();
+        new UnreachableInst(CloneBlock->getContext(), CloneBlock);
+      }
+    }
+  } else if (isa<CleanupReturnInst>(CloneTerminator) ||
+             isa<CleanupEndPadInst>(CloneTerminator)) {
+    BasicBlock *UnwindDest = nullptr;
+
+    // A cleanup pad can unwind through either a cleanupret or a cleanupendpad
+    // but both are handled the same way.
+    if (auto *CRI = dyn_cast<CleanupReturnInst>(CloneTerminator))
+      UnwindDest = CRI->getUnwindDest();
+    else if (auto *CEI = dyn_cast<CleanupEndPadInst>(CloneTerminator))
+      UnwindDest = CEI->getUnwindDest();
+
+    // If the instruction has no local unwind destination, there is nothing
+    // to be done.
+    if (!UnwindDest)
+      return;
+
+    // The unwind destination may be a sibling EH pad, a catchendpad in
+    // a grandparent funclet (ending a catchpad in the parent) or a cleanup
+    // cleanupendpad in the parent.  Call a helper routine to diagnose this
+    // and remove either the clone or original terminator as needed.
+    updateClonedEHPadUnwindToParent(UnwindDest, OrigBlock, CloneBlock,
+                                    FuncletParents[OrigFunclet], CloneParent);
+  } else if (auto *II = dyn_cast<InvokeInst>(CloneTerminator)) {
+    BasicBlock *UnwindDest = II->getUnwindDest();
+    assert(UnwindDest && "Invoke unwinds to a null destination.");
+    assert(UnwindDest->isEHPad() && "Invoke does not unwind to an EH pad.");
+    auto *EHPadInst = UnwindDest->getFirstNonPHI();
+    if (isa<CleanupEndPadInst>(EHPadInst)) {
+      // An invoke that unwinds to a cleanup end pad must be in a cleanup pad.
+      assert(isa<CleanupPadInst>(CloneFunclet->getFirstNonPHI()) &&
+             "Unwinding to cleanup end pad from a non cleanup pad funclet.");
+      // The funclet cloning should have remapped the destination to the cloned
+      // cleanup end pad.
+      assert(FuncletBlocks[CloneFunclet].count(UnwindDest) &&
+             "Unwind destination for invoke was not updated during cloning.");
+    } else if (auto *CEP = dyn_cast<CatchEndPadInst>(EHPadInst)) {
+      auto *OrigCatch = cast<CatchPadInst>(OrigFunclet->getFirstNonPHI());
+      auto *CloneCatch = cast<CatchPadInst>(CloneFunclet->getFirstNonPHI());
+      if (OrigCatch->getUnwindDest() == UnwindDest) {
+        // If the invoke unwinds to a catch end pad that is the unwind
+        // destination for the original catch pad, the cloned invoke should
+        // unwind to the cloned catch end pad.
+        II->setUnwindDest(CloneCatch->getUnwindDest());
+      } else if (CloneCatch->getUnwindDest() == UnwindDest) {
+        // If the invoke unwinds to a catch end pad that is the unwind
+        // destination for the clone catch pad, the original invoke should
+        // unwind to the unwind destination of the original catch pad.
+        // This happens when the catch end pad is matched to the clone
+        // parent when the catchpad instruction is cloned and the original
+        // invoke instruction unwinds to the original catch end pad (which
+        // is now the unwind destination of the cloned catch pad).
+        auto *OrigInvoke = cast<InvokeInst>(OrigBlock->getTerminator());
+        OrigInvoke->setUnwindDest(OrigCatch->getUnwindDest());
+      } else {
+        // If the invoke unwinds to a catch end pad that is not the unwind
+        // destination for the original catch pad, it must be the unwind
+        // destination for a sibling catch end pad.  We'll handle that case
+        // later.
+        assert((getEndPadForCatch(OrigCatch) == UnwindDest ||
+                getEndPadForCatch(CloneCatch) == UnwindDest) &&
+               "Invoke within catch pad unwinds to an invalid catch end pad.");
+      }
+    }
+  }
+}
+
+// Clones all blocks used by the specified funclet to avoid the funclet having
+// multiple parent funclets.  All terminators in the parent that unwind to the
+// original funclet are remapped to unwind to the clone.  Any terminator in the
+// original funclet which returned to this parent is converted to an unreachable
+// instruction. Likewise, any terminator in the cloned funclet which returns to
+// a parent funclet other than the specified parent is converted to an
+// unreachable instruction.
+BasicBlock *WinEHPrepare::cloneFuncletForParent(Function &F,
+                                                BasicBlock *FuncletEntry,
+                                                BasicBlock *Parent) {
+  std::set<BasicBlock *> &BlocksInFunclet = FuncletBlocks[FuncletEntry];
+
+  DEBUG_WITH_TYPE("winehprepare-coloring",
+                  dbgs() << "Cloning funclet \'" << FuncletEntry->getName()
+                         << "\' for parent \'" << Parent->getName() << "\'.\n");
+
+  std::map<BasicBlock *, BasicBlock *> Orig2Clone;
+  ValueToValueMapTy VMap;
+  for (BasicBlock *BB : BlocksInFunclet) {
+    // Create a new basic block and copy instructions into it.
+    BasicBlock *CBB =
+        CloneBasicBlock(BB, VMap, Twine(".from.", Parent->getName()));
+
+    // Insert the clone immediately after the original to ensure determinism
+    // and to keep the same relative ordering of any funclet's blocks.
+    CBB->insertInto(&F, BB->getNextNode());
+
+    // Add basic block mapping.
+    VMap[BB] = CBB;
+
+    // Record delta operations that we need to perform to our color mappings.
+    Orig2Clone[BB] = CBB;
+  } // end for (BasicBlock *BB : BlocksInFunclet)
+
+  BasicBlock *ClonedFunclet = Orig2Clone[FuncletEntry];
+  assert(ClonedFunclet);
+
+  // Set the coloring for the blocks we just cloned.
+  std::set<BasicBlock *> &ClonedBlocks = FuncletBlocks[ClonedFunclet];
+  for (auto &BBMapping : Orig2Clone) {
+    BasicBlock *NewBlock = BBMapping.second;
+    ClonedBlocks.insert(NewBlock);
+    BlockColors[NewBlock].insert(ClonedFunclet);
+
+    DEBUG_WITH_TYPE("winehprepare-coloring",
+                    dbgs() << "  Assigning color \'" << ClonedFunclet->getName()
+                           << "\' to block \'" << NewBlock->getName()
+                           << "\'.\n");
+
+    // Use the VMap to remap the instructions in this cloned block.
+    for (Instruction &I : *NewBlock)
+      RemapInstruction(&I, VMap, RF_IgnoreMissingEntries);
+  }
+
+  // All the cloned blocks have to be colored in the loop above before we can
+  // update the terminators because doing so can require checking the color of
+  // other blocks in the cloned funclet.
+  for (auto &BBMapping : Orig2Clone) {
+    BasicBlock *OldBlock = BBMapping.first;
+    BasicBlock *NewBlock = BBMapping.second;
+
+    // Update the terminator, if necessary, in both the original block and the
+    // cloned so that the original funclet never returns to a block in the
+    // clone parent and the clone funclet never returns to a block in any other
+    // of the original funclet's parents.
+    updateTerminatorsAfterFuncletClone(F, FuncletEntry, ClonedFunclet, OldBlock,
+                                       NewBlock, Parent, VMap, Orig2Clone);
+
+    // Check to see if the cloned block successor has PHI nodes. If so, we need
+    // to add entries to the PHI nodes for the cloned block now.
+    for (BasicBlock *SuccBB : successors(NewBlock)) {
+      for (Instruction &SuccI : *SuccBB) {
+        auto *SuccPN = dyn_cast<PHINode>(&SuccI);
+        if (!SuccPN)
+          break;
+
+        // Ok, we have a PHI node.  Figure out what the incoming value was for
+        // the OldBlock.
+        int OldBlockIdx = SuccPN->getBasicBlockIndex(OldBlock);
+        if (OldBlockIdx == -1)
+          break;
+        Value *IV = SuccPN->getIncomingValue(OldBlockIdx);
+
+        // Remap the value if necessary.
+        if (auto *Inst = dyn_cast<Instruction>(IV)) {
+          ValueToValueMapTy::iterator I = VMap.find(Inst);
+          if (I != VMap.end())
+            IV = I->second;
+        }
+
+        SuccPN->addIncoming(IV, NewBlock);
+      }
+    }
+  }
+
+  // Erase the clone's parent from the original funclet's parent list.
+  std::vector<BasicBlock *> &Parents = FuncletParents[FuncletEntry];
+  Parents.erase(std::remove(Parents.begin(), Parents.end(), Parent),
+                Parents.end());
+
+  // Store the cloned funclet's parent.
+  assert(std::find(FuncletParents[ClonedFunclet].begin(),
+                   FuncletParents[ClonedFunclet].end(),
+                   Parent) == std::end(FuncletParents[ClonedFunclet]));
+  FuncletParents[ClonedFunclet].push_back(Parent);
+
+  // Copy any children of the original funclet to the clone.  We'll either
+  // clone them too or make that path unreachable when we take the next step
+  // in resolveFuncletAncestryForPath().
+  for (auto *Child : FuncletChildren[FuncletEntry]) {
+    assert(std::find(FuncletChildren[ClonedFunclet].begin(),
+                     FuncletChildren[ClonedFunclet].end(),
+                     Child) == std::end(FuncletChildren[ClonedFunclet]));
+    FuncletChildren[ClonedFunclet].push_back(Child);
+    assert(std::find(FuncletParents[Child].begin(), FuncletParents[Child].end(),
+                     ClonedFunclet) == std::end(FuncletParents[Child]));
+    FuncletParents[Child].push_back(ClonedFunclet);
+  }
+
+  // Find any blocks that unwound to the original funclet entry from the
+  // clone parent block and remap them to the clone.
+  for (auto *U : FuncletEntry->users()) {
+    auto *UT = dyn_cast<TerminatorInst>(U);
+    if (!UT)
+      continue;
+    BasicBlock *UBB = UT->getParent();
+    assert(BlockColors[UBB].size() == 1);
+    BasicBlock *UFunclet = *(BlockColors[UBB].begin());
+    // Funclets shouldn't be able to loop back on themselves.
+    assert(UFunclet != FuncletEntry);
+    // If this instruction unwinds to the original funclet from the clone
+    // parent, remap the terminator so that it unwinds to the clone instead.
+    // We will perform a similar transformation for siblings after all
+    // the siblings have been cloned.
+    if (UFunclet == Parent) {
+      // We're about to break the path from this block to the uncloned funclet
+      // entry, so remove it as a predeccessor to clean up the PHIs.
+      FuncletEntry->removePredecessor(UBB);
+      TerminatorInst *Terminator = UBB->getTerminator();
+      RemapInstruction(Terminator, VMap, RF_IgnoreMissingEntries);
+    }
+  }
+
+  // This asserts a condition that is relied upon inside the loop below,
+  // namely that no predecessors of the original funclet entry block
+  // are also predecessors of the cloned funclet entry block.
+  assert(std::all_of(pred_begin(FuncletEntry), pred_end(FuncletEntry),
+                     [&ClonedFunclet](BasicBlock *Pred) {
+                       return std::find(pred_begin(ClonedFunclet),
+                                        pred_end(ClonedFunclet),
+                                        Pred) == pred_end(ClonedFunclet);
+                     }));
+
+  // Remove any invalid PHI node entries in the cloned funclet.cl
+  std::vector<PHINode *> PHIsToErase;
+  for (Instruction &I : *ClonedFunclet) {
+    auto *PN = dyn_cast<PHINode>(&I);
+    if (!PN)
+      break;
+
+    // Predecessors of the original funclet do not reach the cloned funclet,
+    // but the cloning process assumes they will.  Remove them now.
+    for (auto *Pred : predecessors(FuncletEntry))
+      PN->removeIncomingValue(Pred, false);
+  }
+  for (auto *PN : PHIsToErase)
+    PN->eraseFromParent();
+
+  // Replace the original funclet in the parent's children vector with the
+  // cloned funclet.
+  for (auto &It : FuncletChildren[Parent]) {
+    if (It == FuncletEntry) {
+      It = ClonedFunclet;
+      break;
+    }
+  }
+
+  return ClonedFunclet;
+}
+
+// Removes the unwind edge for any exceptional terminators within the specified
+// parent funclet that previously unwound to the specified child funclet.
+void WinEHPrepare::makeFuncletEdgeUnreachable(BasicBlock *Parent,
+                                              BasicBlock *Child) {
+  for (BasicBlock *BB : FuncletBlocks[Parent]) {
+    TerminatorInst *Terminator = BB->getTerminator();
+    if (!Terminator->isExceptional())
+      continue;
+
+    // Look for terninators that unwind to the child funclet.
+    BasicBlock *UnwindDest = nullptr;
+    if (auto *I = dyn_cast<InvokeInst>(Terminator))
+      UnwindDest = I->getUnwindDest();
+    else if (auto *I = dyn_cast<CatchEndPadInst>(Terminator))
+      UnwindDest = I->getUnwindDest();
+    else if (auto *I = dyn_cast<TerminatePadInst>(Terminator))
+      UnwindDest = I->getUnwindDest();
+    // cleanupendpad, catchret and cleanupret don't represent a parent-to-child
+    // funclet transition, so we don't need to consider them here.
+
+    // If the child funclet is the unwind destination, replace the terminator
+    // with an unreachable instruction.
+    if (UnwindDest == Child)
+      removeUnwindEdge(BB);
+  }
+  // The specified parent is no longer a parent of the specified child.
+  std::vector<BasicBlock *> &Children = FuncletChildren[Parent];
+  Children.erase(std::remove(Children.begin(), Children.end(), Child),
+                 Children.end());
+}
+
+// This routine is called after funclets with multiple parents are cloned for
+// a specific parent.  Here we look for children of the specified funclet that
+// unwind to other children of that funclet and update the unwind destinations
+// to ensure that each sibling is connected to the correct clone of the sibling
+// to which it unwinds.
+static void updateSiblingToSiblingUnwind(
+    BasicBlock *CurFunclet,
+    std::map<BasicBlock *, std::set<BasicBlock *>> &BlockColors,
+    std::map<BasicBlock *, std::set<BasicBlock *>> &FuncletBlocks,
+    std::map<BasicBlock *, std::vector<BasicBlock *>> &FuncletParents,
+    std::map<BasicBlock *, std::vector<BasicBlock *>> &FuncletChildren,
+    std::map<BasicBlock *, BasicBlock *> &Funclet2Orig) {
+  // Remap any bad sibling-to-sibling transitions for funclets that
+  // we just cloned.
+  for (BasicBlock *ChildFunclet : FuncletChildren[CurFunclet]) {
+    bool NeedOrigInvokeRemapping = false;
+    for (auto *BB : FuncletBlocks[ChildFunclet]) {
+      TerminatorInst *Terminator = BB->getTerminator();
+      if (!Terminator->isExceptional())
+        continue;
+
+      // See if this terminator has an unwind destination.
+      // Note that catchendpads are handled when the associated catchpad
+      // is cloned.  They don't fit the pattern we're looking for here.
+      BasicBlock *UnwindDest = nullptr;
+      if (auto *II = dyn_cast<InvokeInst>(Terminator)) {
+        UnwindDest = II->getUnwindDest();
+        assert(UnwindDest && "Invoke unwinds to a null destination.");
+        assert(UnwindDest->isEHPad() && "Invoke does not unwind to an EH pad.");
+        auto *EHPadInst = UnwindDest->getFirstNonPHI();
+        if (auto *CEP = dyn_cast<CatchEndPadInst>(EHPadInst)) {
+          // If the invoke unwind destination is the unwind destination for
+          // the current child catch pad funclet, there is nothing to be done.
+          auto *CurCatch = cast<CatchPadInst>(ChildFunclet->getFirstNonPHI());
+          if (CurCatch->getUnwindDest() == UnwindDest)
+            continue;
+
+          // Otherwise, the invoke unwinds to a catch end pad that is the unwind
+          // destination another catch pad in the unwind chain from either the
+          // current catch pad or one of its clones.  If it is already the
+          // catch end pad at the end unwind chain from the current catch pad,
+          // we'll need to check the invoke instructions in the original funclet
+          // later.  Otherwise, we need to remap this invoke now.
+          BasicBlock *CurCatchEnd = getEndPadForCatch(CurCatch);
+          if (CurCatchEnd == UnwindDest)
+            NeedOrigInvokeRemapping = true;
+          else
+            II->setUnwindDest(CurCatchEnd);
+          continue;
+        }
+        // All other unwind scenarios for the invoke are handled elsewhere.
+        continue;
+      } else if (auto *I = dyn_cast<CatchPadInst>(Terminator)) {
+        UnwindDest = I->getUnwindDest();
+        // The catchendpad is not a sibling destination.  This case should
+        // have been handled in cloneFuncletForParent().
+        if (isa<CatchEndPadInst>(Terminator)) {
+          assert(BlockColors[UnwindDest].size() == 1 &&
+                 "Cloned catchpad unwinds to an pad with multiple parents.");
+          assert(FuncletParents[UnwindDest].front() == CurFunclet &&
+                 "Cloned catchpad unwinds to the wrong parent.");
+          continue;
+        }
+      } else {
+        if (auto *I = dyn_cast<CleanupReturnInst>(Terminator))
+          UnwindDest = I->getUnwindDest();
+        else if (auto *I = dyn_cast<CleanupEndPadInst>(Terminator))
+          UnwindDest = I->getUnwindDest();
+
+        // If the cleanup unwinds to caller, there is nothing to be done.
+        if (!UnwindDest)
+          continue;
+      }
+
+      // If the destination is not a cleanup pad, catch pad or terminate pad
+      // we don't need to handle it here.
+      Instruction *EHPad = UnwindDest->getFirstNonPHI();
+      if (!isa<CleanupPadInst>(EHPad) && !isa<CatchPadInst>(EHPad) &&
+          !isa<TerminatePadInst>(EHPad))
+        continue;
+
+      // If it is one of these, then it is either a sibling of the current
+      // child funclet or a clone of one of those siblings.
+      // If it is a sibling, no action is needed.
+      if (FuncletParents[UnwindDest].size() == 1 &&
+          FuncletParents[UnwindDest].front() == CurFunclet)
+        continue;
+
+      // If the unwind destination is a clone of a sibling, we need to figure
+      // out which sibling it is a clone of and use that sibling as the
+      // unwind destination.
+      BasicBlock *DestOrig = Funclet2Orig[UnwindDest];
+      BasicBlock *TargetSibling = nullptr;
+      for (auto &Mapping : Funclet2Orig) {
+        if (Mapping.second != DestOrig)
+          continue;
+        BasicBlock *MappedFunclet = Mapping.first;
+        if (FuncletParents[MappedFunclet].size() == 1 &&
+            FuncletParents[MappedFunclet].front() == CurFunclet) {
+          TargetSibling = MappedFunclet;
+        }
+      }
+      // If we didn't find the sibling we were looking for then the
+      // unwind destination is not a clone of one of child's siblings.
+      // That's unexpected.
+      assert(TargetSibling && "Funclet unwinds to unexpected destination.");
+
+      // Update the terminator instruction to unwind to the correct sibling.
+      if (auto *I = dyn_cast<CatchPadInst>(Terminator))
+        I->setUnwindDest(TargetSibling);
+      else if (auto *I = dyn_cast<CleanupReturnInst>(Terminator))
+        I->setUnwindDest(TargetSibling);
+      else if (auto *I = dyn_cast<CleanupEndPadInst>(Terminator))
+        I->setUnwindDest(TargetSibling);
+    }
+    if (NeedOrigInvokeRemapping) {
+      // To properly remap invoke instructions that unwind to catch end pads
+      // that are not the unwind destination of the catch pad funclet in which
+      // the invoke appears, we must also look at the uncloned invoke in the
+      // original funclet.  If we saw an invoke that was already properly
+      // unwinding to a sibling's catch end pad, we need to check the invokes
+      // in the original funclet.
+      BasicBlock *OrigFunclet = Funclet2Orig[ChildFunclet];
+      for (auto *BB : FuncletBlocks[OrigFunclet]) {
+        auto *II = dyn_cast<InvokeInst>(BB->getTerminator());
+        if (!II)
+          continue;
+
+        BasicBlock *UnwindDest = II->getUnwindDest();
+        assert(UnwindDest && "Invoke unwinds to a null destination.");
+        assert(UnwindDest->isEHPad() && "Invoke does not unwind to an EH pad.");
+        auto *CEP = dyn_cast<CatchEndPadInst>(UnwindDest->getFirstNonPHI());
+        if (!CEP)
+          continue;
+        // If the invoke unwind destination is the unwind destination for
+        // the original catch pad funclet, there is nothing to be done.
+        auto *OrigCatch = cast<CatchPadInst>(OrigFunclet->getFirstNonPHI());
+        if (OrigCatch->getUnwindDest() == UnwindDest)
+          continue;
+
+        // Otherwise, the invoke unwinds to a catch end pad that is the unwind
+        // destination another catch pad in the unwind chain from either the
+        // current catch pad or one of its clones.  If it is not already the
+        // catch end pad at the end unwind chain from the current catch pad,
+        // we need to remap this invoke now.
+        BasicBlock *OrigCatchEnd = getEndPadForCatch(OrigCatch);
+        if (OrigCatchEnd != UnwindDest)
+          II->setUnwindDest(OrigCatchEnd);
+      }
+    }
+  }
+}
+
+void WinEHPrepare::resolveFuncletAncestry(
+    Function &F, SmallVectorImpl<BasicBlock *> &EntryBlocks) {
+  // Most of the time this will be unnecessary.  If the conditions arise that
+  // require this work, this flag will be set.
+  if (!FuncletCloningRequired)
+    return;
+
+  // Funclet2Orig is used to map any cloned funclets back to the original
+  // funclet from which they were cloned.  The map is seeded with the
+  // original funclets mapping to themselves.
+  std::map<BasicBlock *, BasicBlock *> Funclet2Orig;
+  for (auto *Funclet : EntryBlocks)
+    Funclet2Orig[Funclet] = Funclet;
+
+  // Start with the entry funclet and walk the funclet parent-child tree.
+  SmallVector<BasicBlock *, 4> FuncletPath;
+  FuncletPath.push_back(&(F.getEntryBlock()));
+  resolveFuncletAncestryForPath(F, FuncletPath, Funclet2Orig);
+}
+
+// Walks the funclet control flow, cloning any funclets that have more than one
+// parent funclet and breaking any cyclic unwind chains so that the path becomes
+// unreachable at the point where a funclet would have unwound to a funclet that
+// was already in the chain.
+void WinEHPrepare::resolveFuncletAncestryForPath(
+    Function &F, SmallVectorImpl<BasicBlock *> &FuncletPath,
+    std::map<BasicBlock *, BasicBlock *> &Funclet2Orig) {
+  bool ClonedAnyChildren = false;
+  BasicBlock *CurFunclet = FuncletPath.back();
+  // Copy the children vector because we might changing it.
+  std::vector<BasicBlock *> Children(FuncletChildren[CurFunclet]);
+  for (BasicBlock *ChildFunclet : Children) {
+    // Don't allow the funclet chain to unwind back on itself.
+    // If this funclet is already in the current funclet chain, make the
+    // path to it through the current funclet unreachable.
+    bool IsCyclic = false;
+    BasicBlock *ChildIdentity = Funclet2Orig[ChildFunclet];
+    for (BasicBlock *Ancestor : FuncletPath) {
+      BasicBlock *AncestorIdentity = Funclet2Orig[Ancestor];
+      if (AncestorIdentity == ChildIdentity) {
+        IsCyclic = true;
+        break;
+      }
+    }
+    // If the unwind chain wraps back on itself, break the chain.
+    if (IsCyclic) {
+      makeFuncletEdgeUnreachable(CurFunclet, ChildFunclet);
+      continue;
+    }
+    // If this child funclet has other parents, clone the entire funclet.
+    if (FuncletParents[ChildFunclet].size() > 1) {
+      ChildFunclet = cloneFuncletForParent(F, ChildFunclet, CurFunclet);
+      Funclet2Orig[ChildFunclet] = ChildIdentity;
+      ClonedAnyChildren = true;
+    }
+    FuncletPath.push_back(ChildFunclet);
+    resolveFuncletAncestryForPath(F, FuncletPath, Funclet2Orig);
+    FuncletPath.pop_back();
+  }
+  // If we didn't clone any children, we can return now.
+  if (!ClonedAnyChildren)
+    return;
+
+  updateSiblingToSiblingUnwind(CurFunclet, BlockColors, FuncletBlocks,
+                               FuncletParents, FuncletChildren, Funclet2Orig);
+}
+
+void WinEHPrepare::colorFunclets(Function &F,
+                                 SmallVectorImpl<BasicBlock *> &EntryBlocks) {
+  ::colorFunclets(F, EntryBlocks, BlockColors, FuncletBlocks);
 
   // The processing above actually accumulated the parent set for this
   // funclet into the color set for its entry; use the parent set to
   // populate the children map, and reset the color set to include just
   // the funclet itself (no instruction can target a funclet entry except on
   // that transitions to the child funclet).
   for (BasicBlock *FuncletEntry : EntryBlocks) {
     std::set<BasicBlock *> &ColorMapItem = BlockColors[FuncletEntry];
-    for (BasicBlock *Parent : ColorMapItem)
-      FuncletChildren[Parent].insert(FuncletEntry);
+    // It will be rare for funclets to have multiple parents, but if any
+    // do we need to clone the funclet later to address that.  Here we
+    // set a flag indicating that this case has arisen so that we don't
+    // have to do a lot of checking later to handle the more common case.
+    if (ColorMapItem.size() > 1)
+      FuncletCloningRequired = true;
+    for (BasicBlock *Parent : ColorMapItem) {
+      assert(std::find(FuncletChildren[Parent].begin(),
+                       FuncletChildren[Parent].end(),
+                       FuncletEntry) == std::end(FuncletChildren[Parent]));
+      FuncletChildren[Parent].push_back(FuncletEntry);
+      assert(std::find(FuncletParents[FuncletEntry].begin(),
+                       FuncletParents[FuncletEntry].end(),
+                       Parent) == std::end(FuncletParents[FuncletEntry]));
+      FuncletParents[FuncletEntry].push_back(Parent);
+    }
     ColorMapItem.clear();
     ColorMapItem.insert(FuncletEntry);
   }
 }
 
-void WinEHPrepare::colorFunclets(Function &F,
-                                 SmallVectorImpl<BasicBlock *> &EntryBlocks) {
-  ::colorFunclets(F, EntryBlocks, BlockColors, FuncletBlocks, FuncletChildren);
-}
-
 void llvm::calculateCatchReturnSuccessorColors(const Function *Fn,
                                                WinEHFuncInfo &FuncInfo) {
   SmallVector<BasicBlock *, 4> EntryBlocks;
   // colorFunclets needs the set of EntryBlocks, get them using
   // findFuncletEntryPoints.
   findFuncletEntryPoints(const_cast<Function &>(*Fn), EntryBlocks);
 
   std::map<BasicBlock *, std::set<BasicBlock *>> BlockColors;
   std::map<BasicBlock *, std::set<BasicBlock *>> FuncletBlocks;
-  std::map<BasicBlock *, std::set<BasicBlock *>> FuncletChildren;
   // Figure out which basic blocks belong to which funclets.
   colorFunclets(const_cast<Function &>(*Fn), EntryBlocks, BlockColors,
-                FuncletBlocks, FuncletChildren);
+                FuncletBlocks);
+
+  // The static colorFunclets routine assigns multiple colors to funclet entries
+  // because that information is needed to calculate funclets' parent-child
+  // relationship, but we don't need those relationship here and ultimately the
+  // entry blocks should have the color of the funclet they begin.
+  for (BasicBlock *FuncletEntry : EntryBlocks) {
+    BlockColors[FuncletEntry].clear();
+    BlockColors[FuncletEntry].insert(FuncletEntry);
+  }
 
   // We need to find the catchret successors.  To do this, we must first find
   // all the catchpad funclets.
   for (auto &Funclet : FuncletBlocks) {
     // Figure out what kind of funclet we are looking at; We only care about
     // catchpads.
     BasicBlock *FuncletPadBB = Funclet.first;
     Instruction *FirstNonPHI = FuncletPadBB->getFirstNonPHI();
void WinEHPrepare::cloneCommonBlocks(
   // We need to clone all blocks which belong to multiple funclets.  Values are
   // remapped throughout the funclet to propogate both the new instructions
   // *and* the new basic blocks themselves.
   for (BasicBlock *FuncletPadBB : EntryBlocks) {
     std::set<BasicBlock *> &BlocksInFunclet = FuncletBlocks[FuncletPadBB];
 
     std::map<BasicBlock *, BasicBlock *> Orig2Clone;
     ValueToValueMapTy VMap;
-    for (BasicBlock *BB : BlocksInFunclet) {
+    for (auto BlockIt = BlocksInFunclet.begin(),
+              BlockEnd = BlocksInFunclet.end();
+         BlockIt != BlockEnd;) {
+      // Increment the iterator inside the loop because we might be removing
+      // blocks from the set.
+      BasicBlock *BB = *BlockIt++;
       std::set<BasicBlock *> &ColorsForBB = BlockColors[BB];
       // We don't need to do anything if the block is monochromatic.
       size_t NumColorsForBB = ColorsForBB.size();
       if (NumColorsForBB == 1)
         continue;
 
+      // If this block is a catchendpad, it shouldn't be cloned.
+      // We will only see a catchendpad with multiple colors in the case where
+      // some funclet has multiple parents.  In that case, the color will be
+      // resolved during the resolveFuncletAncestry processing.
+      // For now, find the catchpad that unwinds to this block and assign
+      // that catchpad's first parent to be the color for this block.
+      if (auto *CEP = dyn_cast<CatchEndPadInst>(BB->getFirstNonPHI())) {
+        assert(
+            FuncletCloningRequired &&
+            "Found multi-colored catchendpad with no multi-parent funclets.");
+        BasicBlock *CatchParent = nullptr;
+        // There can only be one catchpad predecessor for a catchendpad.
+        for (BasicBlock *PredBB : predecessors(BB)) {
+          if (isa<CatchPadInst>(PredBB->getTerminator())) {
+            CatchParent = PredBB;
+            break;
+          }
+        }
+        // There must be one catchpad predecessor for a catchendpad.
+        assert(CatchParent && "No catchpad found for catchendpad.");
+
+        // If the catchpad has multiple parents, we'll clone the catchendpad
+        // when we clone the catchpad funclet and insert it into the correct
+        // funclet.  For now, we just select the first parent of the catchpad
+        // and give the catchendpad that color.
+        BasicBlock *CorrectColor = FuncletParents[CatchParent].front();
+        assert(FuncletBlocks[CorrectColor].count(BB));
+        assert(BlockColors[BB].count(CorrectColor));
+
+        // Remove this block from the FuncletBlocks set of any funclet that
+        // isn't the funclet whose color we just selected.
+        for (auto It = BlockColors[BB].begin(), End = BlockColors[BB].end();
+             It != End; ) {
+          // The iterator must be incremented here because we are removing
+          // elements from the set we're walking.
+          auto Temp = It++;
+          BasicBlock *ContainingFunclet = *Temp;
+          if (ContainingFunclet != CorrectColor) {
+            FuncletBlocks[ContainingFunclet].erase(BB);
+            BlockColors[BB].erase(Temp);
+          }
+        }
+
+        // This should leave just one color for BB.
+        assert(BlockColors[BB].size() == 1);
+        continue;
+      }
+
+      DEBUG_WITH_TYPE("winehprepare-coloring",
+                      dbgs() << "  Cloning block \'" << BB->getName()
+                              << "\' for funclet \'" << FuncletPadBB->getName()
+                              << "\'.\n");
+
       // Create a new basic block and copy instructions into it!
       BasicBlock *CBB =
           CloneBasicBlock(BB, VMap, Twine(".for.", FuncletPadBB->getName()));
       // Insert the clone immediately after the original to ensure determinism
       // and to keep the same relative ordering of any funclet's blocks.
       CBB->insertInto(&F, BB->getNextNode());
 
       // Add basic block mapping.
for (BasicBlock *FuncletPadBB : EntryBlocks) {
     // another has gained a color.
     for (auto &BBMapping : Orig2Clone) {
       BasicBlock *OldBlock = BBMapping.first;
       BasicBlock *NewBlock = BBMapping.second;
 
       BlocksInFunclet.insert(NewBlock);
       BlockColors[NewBlock].insert(FuncletPadBB);
 
+      DEBUG_WITH_TYPE("winehprepare-coloring",
+                      dbgs() << "  Assigned color \'" << FuncletPadBB->getName()
+                              << "\' to block \'" << NewBlock->getName()
+                              << "\'.\n");
+
       BlocksInFunclet.erase(OldBlock);
       BlockColors[OldBlock].erase(FuncletPadBB);
+
+      DEBUG_WITH_TYPE("winehprepare-coloring",
+                      dbgs() << "  Removed color \'" << FuncletPadBB->getName()
+                              << "\' from block \'" << OldBlock->getName()
+                              << "\'.\n");
+
+      // If we are cloning a funclet that might share a child funclet with
+      // another funclet, look to see if the cloned block is reached from a
+      // catchret instruction.  If so, save this association so we can retrieve
+      // the possibly orphaned clone when we clone the child funclet.
+      if (FuncletCloningRequired) {
+        for (auto *Pred : predecessors(OldBlock)) {
+          auto *Terminator = Pred->getTerminator();
+          if (!isa<CatchReturnInst>(Terminator))
+            continue;
+          // If this block is reached from a catchret instruction in a funclet
+          // that has multiple parents, it will have a color for each of those
+          // parents.  We just removed the color of one of the parents, but
+          // the cloned block will be unreachable until we clone the child
+          // funclet that contains the catchret instruction.  In that case we
+          // need to create a mapping that will let us find the cloned block
+          // later and associate it with the cloned child funclet.
+          bool BlockWillBeEstranged = false;
+          for (auto *Color : BlockColors[Pred]) {
+            if (FuncletParents[Color].size() > 1) {
+              BlockWillBeEstranged = true;
+              break; // Breaks out of the color loop
+            }
+          }
+          if (BlockWillBeEstranged) {
+            EstrangedBlocks[FuncletPadBB][OldBlock] = NewBlock;
+            DEBUG_WITH_TYPE("winehprepare-coloring",
+                            dbgs() << "  Saved mapping of estranged block \'"
+                                  << NewBlock->getName() << "\' for \'"
+                                  << FuncletPadBB->getName() << "\'.\n");
+            break; // Breaks out of the predecessor loop
+          }
+        }
+      }
     }
 
     // Loop over all of the instructions in this funclet, fixing up operand
     // references as we go.  This uses VMap to do all the hard work.
     for (BasicBlock *BB : BlocksInFunclet)
       // Loop over all instructions, fixing each one as we find it...
       for (Instruction &I : *BB)
         RemapInstruction(&I, VMap,
if (!DisableDemotion) {
 
     demoteUsesBetweenFunclets(F);
 
     demoteArgumentUses(F);
   }
 
   cloneCommonBlocks(F, EntryBlocks);
 
+  resolveFuncletAncestry(F, EntryBlocks);
+
   if (!DisableCleanups) {
     removeImplausibleTerminators(F);
 
     cleanupPreparedFunclets(F);
   }
 
   verifyPreparedFunclets(F);
 
   BlockColors.clear();
   FuncletBlocks.clear();
   FuncletChildren.clear();
+  FuncletParents.clear();
+  EstrangedBlocks.clear();
+  FuncletCloningRequired = false;
 
   return true;
 }
 
 // TODO: Share loads when one use dominates another, or when a catchpad exit
 // dominates uses (needs dominators).
 AllocaInst *WinEHPrepare::insertPHILoads(PHINode *PN, Function &F) {
   BasicBlock *PHIBlock = PN->getParent();

llvm/trunk/test/CodeGen/WinEH/wineh-cloning.ll

 ; unwinds to the catchendpad for %right, so the copy
 ; of %inner under %right should include it; the copy
 ; of %inner under %left should instead have an
 ; `unreachable` inserted there, but the copy under
 ; %left still needs to be created because it's possible
 ; the dynamic path enters %left, then enters %inner,
 ; then calls @h, and that the call to @h doesn't return.
 ; CHECK-LABEL: define void @test6(
-; TODO: CHECKs
+; CHECK:     left:
+; CHECK:           to label %[[SHARED_CONT_LEFT:.+]] unwind label %[[INNER_LEFT:.+]]
+; CHECK:     right:
+; CHECK:           to label %right.catch unwind label %right.end
+; CHECK:     right.catch:
+; CHECK:       %x = call i32 @g()
+; CHECK:       store i32 %x, i32* %x.wineh.spillslot
+; CHECK:           to label %shared.cont unwind label %[[INNER_RIGHT:.+]]
+; CHECK:     right.end:
+; CHECK:       catchendpad unwind to caller
+; CHECK:     shared.cont:
+; CHECK:       unreachable
+; CHECK:     [[SHARED_CONT_LEFT]]:
+; CHECK:       unreachable
+; CHECK:     [[INNER_RIGHT]]:
+; CHECK:       [[I_R:\%.+]] = cleanuppad []
+; CHECK:       [[X_RELOAD_R:\%.+]] = load i32, i32* %x.wineh.spillslot
+; CHECK:       call void @h(i32 [[X_RELOAD_R]])
+; CHECK:       cleanupret [[I_R]] unwind label %right.end
+; CHECK:     [[INNER_LEFT]]:
+; CHECK:       [[I_L:\%.+]] = cleanuppad []
+; CHECK:       [[X_RELOAD_L:\%.+]] = load i32, i32* %x.wineh.spillslot
+; CHECK:       call void @h(i32 [[X_RELOAD_L]])
+; CHECK:       unreachable
 
 
 define void @test7() personality i32 (...)* @__CxxFrameHandler3 {
 entry:
   invoke void @f()
     to label %invoke.cont unwind label %left
 invoke.cont:
   invoke void @f()
inner:
   cleanupret %i unwind label %right.end
 unreachable:
   unreachable
 }
 ; Another case of a two-parent child (like @test6), this time
 ; with the join at the entry itself instead of following a
 ; non-pad join.
 ; CHECK-LABEL: define void @test7(
-; TODO: CHECKs
+; CHECK:     invoke.cont:
+; CHECK:           to label %[[UNREACHABLE_ENTRY:.+]] unwind label %right
+; CHECK:     left:
+; CHECK:           to label %[[UNREACHABLE_LEFT:.+]] unwind label %[[INNER_LEFT:.+]]
+; CHECK:     right:
+; CHECK:           to label %right.catch unwind label %right.end
+; CHECK:     right.catch:
+; CHECK:           to label %unreachable unwind label %[[INNER_RIGHT:.+]]
+; CHECK:     right.end:
+; CHECK:       catchendpad unwind to caller
+; CHECK:     [[INNER_RIGHT]]:
+; CHECK:       [[I_R:\%.+]] = cleanuppad []
+; CHECK:       [[X_R:\%.+]] = call i32 @g()
+; CHECK:       call void @h(i32 [[X_R]])
+; CHECK:       cleanupret [[I_R]] unwind label %right.end
+; CHECK:     [[INNER_LEFT]]:
+; CHECK:       [[I_L:\%.+]] = cleanuppad []
+; CHECK:       [[X_L:\%.+]] = call i32 @g()
+; CHECK:       call void @h(i32 [[X_L]])
+; CHECK:       unreachable
+; CHECK:     unreachable:
+; CHECK:       unreachable
+; CHECK:     [[UNREACHABLE_LEFT]]:
+; CHECK:       unreachable
+; CHECK:     [[UNREACHABLE_ENTRY]]:
+; CHECK:       unreachable
 
 
 define void @test8() personality i32 (...)* @__CxxFrameHandler3 {
 entry:
   invoke void @f()
     to label %invoke.cont unwind label %left
 invoke.cont:
   invoke void @f()
inner.child:
   call void @h(i32 %x)
   unreachable
 unreachable:
   unreachable
 }
 ; %inner is a two-parent child which itself has a child; need
 ; to make two copies of both the %inner and %inner.child.
 ; CHECK-LABEL: define void @test8(
-; TODO: CHECKs
+; CHECK:     invoke.cont:
+; CHECK:               to label %[[UNREACHABLE_ENTRY:.+]] unwind label %right
+; CHECK:     left:
+; CHECK:               to label %[[UNREACHABLE_LEFT:.+]] unwind label %[[INNER_LEFT:.+]]
+; CHECK:     right:
+; CHECK:               to label %right.catch unwind label %right.end
+; CHECK:     right.catch:
+; CHECK:               to label %[[UNREACHABLE_RIGHT:.+]] unwind label %[[INNER_RIGHT:.+]]
+; CHECK:     right.end:
+; CHECK:       catchendpad unwind to caller
+; CHECK:     [[INNER_RIGHT]]:
+; CHECK:               to label %[[UNREACHABLE_INNER_RIGHT:.+]] unwind label %[[INNER_CHILD_RIGHT:.+]]
+; CHECK:     [[INNER_LEFT]]:
+; CHECK:               to label %[[UNREACHABLE_INNER_LEFT:.+]] unwind label %[[INNER_CHILD_LEFT:.+]]
+; CHECK:     [[INNER_CHILD_RIGHT]]:
+; CHECK:       [[TMP:\%.+]] = cleanuppad []
+; CHECK:       [[X:\%.+]] = call i32 @g()
+; CHECK:       call void @h(i32 [[X]])
+; CHECK:       unreachable
+; CHECK:     [[INNER_CHILD_LEFT]]:
+; CHECK:       [[TMP:\%.+]] = cleanuppad []
+; CHECK:       [[X:\%.+]] = call i32 @g()
+; CHECK:       call void @h(i32 [[X]])
+; CHECK:       unreachable
+; CHECK:     [[UNREACHABLE_INNER_RIGHT]]:
+; CHECK:       unreachable
+; CHECK:     [[UNREACHABLE_INNER_LEFT]]:
+; CHECK:       unreachable
+; CHECK:     [[UNREACHABLE_RIGHT]]:
+; CHECK:       unreachable
+; CHECK:     [[UNREACHABLE_LEFT]]:
+; CHECK:       unreachable
+; CHECK:     [[UNREACHABLE_ENTRY]]:
+; CHECK:       unreachable
 
 
 define void @test9() personality i32 (...)* @__CxxFrameHandler3 {
 entry:
   invoke void @f()
     to label %invoke.cont unwind label %left
 invoke.cont:
   invoke void @f()

 ; other a child of the opposite funclet), but also make sure not to
 ; clone self-descendants (if we tried to do that we'd need to make an
 ; infinite number of them).  Presumably if optimizations ever generated
 ; such a thing it would mean that one of the two cleanups was originally
 ; the parent of the other, but that we'd somehow lost track in the CFG
 ; of which was which along the way; generating each possibility lets
 ; whichever case was correct execute correctly.
 ; CHECK-LABEL: define void @test9(
-; TODO: CHECKs
+; CHECK:     entry:
+; CHECK:               to label %invoke.cont unwind label %[[LEFT:.+]]
+; CHECK:     invoke.cont:
+; CHECK:               to label %[[UNREACHABLE_ENTRY:.+]] unwind label %[[RIGHT:.+]]
+; CHECK:     [[LEFT_FROM_RIGHT:.+]]:
+; CHECK:       call void @h(i32 1)
+; CHECK:       call void @f()
+; CHECK:       unreachable
+; CHECK:     [[LEFT]]:
+; CHECK:       call void @h(i32 1)
+; CHECK:       invoke void @f()
+; CHECK:               to label %[[UNREACHABLE_LEFT:.+]] unwind label %[[RIGHT_FROM_LEFT:.+]]
+; CHECK:     [[RIGHT]]:
+; CHECK:       call void @h(i32 2)
+; CHECK:       invoke void @f()
+; CHECK:               to label %[[UNREACHABLE_RIGHT:.+]] unwind label %[[LEFT_FROM_RIGHT]]
+; CHECK:     [[RIGHT_FROM_LEFT]]:
+; CHECK:       call void @h(i32 2)
+; CHECK:       call void @f()
+; CHECK:       unreachable
+; CHECK:     [[UNREACHABLE_RIGHT]]:
+; CHECK:       unreachable
+; CHECK:     [[UNREACHABLE_LEFT]]:
+; CHECK:       unreachable
+; CHECK:     [[UNREACHABLE_ENTRY]]:
+; CHECK:       unreachable
+
 
 define void @test10() personality i32 (...)* @__CxxFrameHandler3 {
 entry:
   invoke void @f()
     to label %unreachable unwind label %inner
 inner:
   %cleanup = cleanuppad []
   ; make sure we don't overlook this cleanupret and try to process

llvm/trunk/test/CodeGen/WinEH/wineh-demotion.ll

 
 catch.inner:
   ; Need just one store here because only %y is affected
   ; CHECK: catch.inner:
   %z = call i32 @g()
   ; CHECK:   store i32 %z
   ; CHECK-NEXT: invoke void @f
   invoke void @f()
-          to label %catchret.inner unwind label %merge.outer
+          to label %catchret.inner unwind label %catchend.inner
 
 catchret.inner:
   catchret %cpinner to label %exit
 catchend.inner:
+  ; CHECK-NOT: = phi
+  %y = phi i32 [ %x, %merge.inner ], [ %z, %catch.inner ]
   catchendpad unwind label %merge.outer
 
 merge.outer:
   ; CHECK: merge.outer:
-  ; CHECK-NOT: = phi
   ; CHECK: [[CatchPad:%[^ ]+]] = catchpad []
-  %y = phi i32 [ %x, %catchend.inner ], [ %z, %catch.inner ]
   %cpouter = catchpad [] to label %catch.outer unwind label %catchend.outer
 
 catchend.outer:
   catchendpad unwind to caller
 
 catch.outer:
   ; Need to load x and y from two different slots since they're both live
   ; and can have different values (if we came from catch.inner)

llvm/trunk/test/CodeGen/WinEH/wineh-multi-parent-cloning.ll

+; RUN: opt -mtriple=x86_x64-pc-windows-msvc -S -winehprepare  < %s | FileCheck %s
+
+declare i32 @__CxxFrameHandler3(...)
+
+declare void @f()
+declare i32 @g()
+declare void @h(i32)
+declare i1 @b()
+
+define void @test1() personality i32 (...)* @__CxxFrameHandler3 {
+entry:
+  invoke void @f()
+    to label %invoke.cont unwind label %left
+invoke.cont:
+  invoke void @f()
+    to label %exit unwind label %right
+left:
+  cleanuppad []
+  br label %shared
+right:
+  catchpad []
+    to label %right.catch unwind label %right.end
+right.catch:
+  br label %shared
+right.end:
+  catchendpad unwind to caller
+shared:
+  %x = call i32 @g()
+  invoke void @f()
+    to label %shared.cont unwind label %inner
+shared.cont:
+  unreachable
+inner:
+  %i = cleanuppad []
+  call void @h(i32 %x)
+  cleanupret %i unwind label %right.end
+exit:
+  ret void
+}
+; %inner is a cleanup which appears both as a child of
+; %left and as a child of %right.  Since statically we
+; need each funclet to have a single parent, we need to
+; clone the entire %inner funclet so we can have one
+; copy under each parent.  The cleanupret in %inner
+; unwinds to the catchendpad for %right, so the copy
+; of %inner under %right should include it; the copy
+; of %inner under %left should instead have an
+; `unreachable` inserted there, but the copy under
+; %left still needs to be created because it's possible
+; the dynamic path enters %left, then enters %inner,
+; then calls @h, and that the call to @h doesn't return.
+; CHECK-LABEL: define void @test1(
+; CHECK:     left:
+; CHECK:           to label %[[SHARED_CONT_LEFT:.+]] unwind label %[[INNER_LEFT:.+]]
+; CHECK:     right:
+; CHECK:           to label %right.catch unwind label %right.end
+; CHECK:     right.catch:
+; CHECK:       %x = call i32 @g()
+; CHECK:       store i32 %x, i32* %x.wineh.spillslot
+; CHECK:           to label %shared.cont unwind label %[[INNER_RIGHT:.+]]
+; CHECK:     right.end:
+; CHECK:       catchendpad unwind to caller
+; CHECK:     shared.cont:
+; CHECK:       unreachable
+; CHECK:     [[SHARED_CONT_LEFT]]:
+; CHECK:       unreachable
+; CHECK:     [[INNER_RIGHT]]:
+; CHECK:       [[I_R:\%.+]] = cleanuppad []
+; CHECK:       [[X_RELOAD_R:\%.+]] = load i32, i32* %x.wineh.spillslot
+; CHECK:       call void @h(i32 [[X_RELOAD_R]])
+; CHECK:       cleanupret [[I_R]] unwind label %right.end
+; CHECK:     [[INNER_LEFT]]:
+; CHECK:       [[I_L:\%.+]] = cleanuppad []
+; CHECK:       [[X_RELOAD_L:\%.+]] = load i32, i32* %x.wineh.spillslot
+; CHECK:       call void @h(i32 [[X_RELOAD_L]])
+; CHECK:       unreachable
+
+
+define void @test2() personality i32 (...)* @__CxxFrameHandler3 {
+entry:
+  invoke void @f()
+    to label %invoke.cont unwind label %left
+invoke.cont:
+  invoke void @f()
+    to label %exit unwind label %right
+left:
+  cleanuppad []
+  br label %shared
+right:
+  catchpad []
+    to label %right.catch unwind label %right.end
+right.catch:
+  br label %shared
+right.end:
+  catchendpad unwind to caller
+shared:
+  %x = call i32 @g()
+  invoke void @f()
+    to label %shared.cont unwind label %inner
+shared.cont:
+  unreachable
+inner:
+  catchpad []
+    to label %inner.catch unwind label %inner.end
+inner.catch:
+  call void @h(i32 %x)
+  unreachable
+inner.end:
+  catchendpad unwind label %right.end
+exit:
+  ret void
+}
+; In this case left and right are both parents of inner.  This differs from
+; @test1 in that inner is a catchpad rather than a cleanuppad, which makes
+; inner.end a block that gets cloned so that left and right each contain a
+; copy (catchendpad blocks are considered to be part of the parent funclet
+; of the associated catchpad). The catchendpad in %inner.end unwinds to
+; %right.end (which belongs to the entry funclet).
+; CHECK-LABEL: define void @test2(
+; CHECK:     left:
+; CHECK:           to label %[[SHARED_CONT_LEFT:.+]] unwind label %[[INNER_LEFT:.+]]
+; CHECK:     right:
+; CHECK:           to label %right.catch unwind label %[[RIGHT_END:.+]]
+; CHECK:     right.catch:
+; CHECK:           to label %[[SHARED_CONT_RIGHT:.+]] unwind label %[[INNER_RIGHT:.+]]
+; CHECK:     [[RIGHT_END]]:
+; CHECK:       catchendpad unwind to caller
+; CHECK:     [[SHARED_CONT_RIGHT]]:
+; CHECK:       unreachable
+; CHECK:     [[SHARED_CONT_LEFT]]:
+; CHECK:       unreachable
+; CHECK:     [[INNER_RIGHT]]:
+; CHECK:       catchpad []
+; CHECK:           to label %[[INNER_CATCH_RIGHT:.+]] unwind label %[[INNER_END_RIGHT:.+]]
+; CHECK:     [[INNER_LEFT]]:
+; CHECK:       catchpad []
+; CHECK:           to label %[[INNER_CATCH_LEFT:.+]] unwind label %[[INNER_END_LEFT:.+]]
+; CHECK:     [[INNER_CATCH_RIGHT]]:
+; CHECK:       [[X_RELOAD_R:\%.+]] = load i32, i32* %x.wineh.spillslot
+; CHECK:       call void @h(i32 [[X_RELOAD_R]])
+; CHECK:       unreachable
+; CHECK:     [[INNER_CATCH_LEFT]]:
+; CHECK:       [[X_RELOAD_L:\%.+]] = load i32, i32* %x.wineh.spillslot
+; CHECK:       call void @h(i32 [[X_RELOAD_L]])
+; CHECK:       unreachable
+; CHECK:     [[INNER_END_LEFT]]:
+; CHECK:       catchendpad unwind to caller
+; CHECK:     [[INNER_END_RIGHT]]:
+; CHECK:       catchendpad unwind label %[[RIGHT_END]]
+
+define void @test3() personality i32 (...)* @__CxxFrameHandler3 {
+entry:
+  invoke void @f()
+    to label %exit unwind label %left
+left:
+  %l = cleanuppad []
+  br label %shared
+left.end:
+  cleanupendpad %l unwind label %right
+right:
+  catchpad []
+    to label %right.catch unwind label %right.end
+right.catch:
+  br label %shared
+right.end:
+  catchendpad unwind to caller
+shared:
+  %x = call i32 @g()
+  invoke void @f()
+    to label %shared.cont unwind label %inner
+shared.cont:
+  unreachable
+inner:
+  catchpad []
+    to label %inner.catch unwind label %inner.end
+inner.catch:
+  call void @h(i32 %x)
+  unreachable
+inner.end:
+  catchendpad unwind label %left.end
+exit:
+  ret void
+}
+; In this case, %left and %right are siblings with %entry as the parent of both,
+; while %left and %right are both parents of %inner.  The catchendpad in
+; %inner.end unwinds to %left.end.  When %inner is cloned a copy of %inner.end
+; will be made for both %left and %right, but because %left.end is a cleanup pad
+; and %right is a catch pad the unwind edge from the copy of %inner.end for
+; %right must be removed.
+; CHECK-LABEL: define void @test3(
+; CHECK:     left:
+; CHECK:       %l = cleanuppad []
+; CHECK:           to label %[[SHARED_CONT_LEFT:.+]] unwind label %[[INNER_LEFT:.+]]
+; CHECK:     [[LEFT_END:left.end.*]]:
+; CHECK:       cleanupendpad %l unwind label %right
+; CHECK:     right:
+; CHECK:           to label %right.catch unwind label %[[RIGHT_END:.+]]
+; CHECK:     right.catch:
+; CHECK:           to label %[[SHARED_CONT_RIGHT:.+]] unwind label %[[INNER_RIGHT:.+]]
+; CHECK:     [[RIGHT_END]]:
+; CHECK:       catchendpad unwind to caller
+; CHECK:     [[SHARED_CONT_RIGHT]]:
+; CHECK:       unreachable
+; CHECK:     [[SHARED_CONT_LEFT]]:
+; CHECK:       unreachable
+; CHECK:     [[INNER_RIGHT]]:
+; CHECK:       catchpad []
+; CHECK:           to label %[[INNER_CATCH_RIGHT:.+]] unwind label %[[INNER_END_RIGHT:.+]]
+; CHECK:     [[INNER_LEFT]]:
+; CHECK:       catchpad []
+; CHECK:           to label %[[INNER_CATCH_LEFT:.+]] unwind label %[[INNER_END_LEFT:.+]]
+; CHECK:     [[INNER_CATCH_RIGHT]]:
+; CHECK:       [[X_RELOAD_R:\%.+]] = load i32, i32* %x.wineh.spillslot
+; CHECK:       call void @h(i32 [[X_RELOAD_R]])
+; CHECK:       unreachable
+; CHECK:     [[INNER_CATCH_LEFT]]:
+; CHECK:       [[X_RELOAD_R:\%.+]] = load i32, i32* %x.wineh.spillslot
+; CHECK:       call void @h(i32 [[X_RELOAD_R]])
+; CHECK:       unreachable
+; CHECK:     [[INNER_END_LEFT]]:
+; CHECK:       catchendpad unwind label %[[LEFT_END]]
+; CHECK:     [[INNER_END_RIGHT]]:
+; CHECK:       catchendpad unwind to caller
+
+
+define void @test4() personality i32 (...)* @__CxxFrameHandler3 {
+entry:
+  invoke void @f()
+    to label %exit unwind label %left
+left:
+  catchpad []
+    to label %left.catch unwind label %left.end
+left.catch:
+  br label %shared
+left.end:
+  catchendpad unwind label %right
+right:
+  catchpad []
+    to label %right.catch unwind label %right.end
+right.catch:
+  br label %shared
+right.end:
+  catchendpad unwind to caller
+shared:
+  %x = call i32 @g()
+  invoke void @f()
+    to label %shared.cont unwind label %inner
+shared.cont:
+  unreachable
+inner:
+  catchpad []
+    to label %inner.catch unwind label %inner.end
+inner.catch:
+  call void @h(i32 %x)
+  unreachable
+inner.end:
+  catchendpad unwind label %left.end
+exit:
+  ret void
+}
+; This is a variation of @test3 in which both %left and %right are catch pads.
+; In this case, %left and %right are siblings with %entry as the parent of both,
+; while %left and %right are both parents of %inner.  The catchendpad in
+; %inner.end unwinds to %left.end.  When %inner is cloned a copy of %inner.end
+; will be made for both %left and %right, but because the catchpad in %right
+; does not unwind to %left.end the unwind edge from the copy of %inner.end for
+; %right must be removed.
+; CHECK-LABEL: define void @test4(
+; CHECK:     left:
+; CHECK:       catchpad []
+; CHECK:           to label %left.catch unwind label %[[LEFT_END:.+]]
+; CHECK:     left.catch:
+; CHECK:           to label %[[SHARED_CONT_LEFT:.+]] unwind label %[[INNER_LEFT:.+]]
+; CHECK:     [[LEFT_END]]:
+; CHECK:       catchendpad unwind label %right
+; CHECK:     right:
+; CHECK:           to label %right.catch unwind label %[[RIGHT_END:.+]]
+; CHECK:     right.catch:
+; CHECK:           to label %[[SHARED_CONT_RIGHT:.+]] unwind label %[[INNER_RIGHT:.+]]
+; CHECK:     [[RIGHT_END]]:
+; CHECK:       catchendpad unwind to caller
+; CHECK:     [[SHARED_CONT_RIGHT]]:
+; CHECK:       unreachable
+; CHECK:     [[SHARED_CONT_LEFT]]:
+; CHECK:       unreachable
+; CHECK:     [[INNER_RIGHT]]:
+; CHECK:       catchpad []
+; CHECK:           to label %[[INNER_CATCH_RIGHT:.+]] unwind label %[[INNER_END_RIGHT:.+]]
+; CHECK:     [[INNER_LEFT]]:
+; CHECK:       catchpad []
+; CHECK:           to label %[[INNER_CATCH_LEFT:.+]] unwind label %[[INNER_END_LEFT:.+]]
+; CHECK:     [[INNER_CATCH_RIGHT]]:
+; CHECK:       [[X_RELOAD_R:\%.+]] = load i32, i32* %x.wineh.spillslot
+; CHECK:       call void @h(i32 [[X_RELOAD_R]])
+; CHECK:       unreachable
+; CHECK:     [[INNER_CATCH_LEFT]]:
+; CHECK:       [[X_RELOAD_L:\%.+]] = load i32, i32* %x.wineh.spillslot
+; CHECK:       call void @h(i32 [[X_RELOAD_L]])
+; CHECK:       unreachable
+; CHECK:     [[INNER_END_LEFT]]:
+; CHECK:       catchendpad unwind label %[[LEFT_END]]
+; CHECK:     [[INNER_END_RIGHT]]:
+; CHECK:       catchendpad unwind to caller
+
+
+define void @test5() personality i32 (...)* @__CxxFrameHandler3 {
+entry:
+  invoke void @f()
+    to label %exit unwind label %left
+left:
+  catchpad []
+    to label %left.catch unwind label %left.end
+left.catch:
+  br label %shared
+left.end:
+  catchendpad unwind label %right
+right:
+  %r = cleanuppad []
+  br label %shared
+shared:
+  %x = call i32 @g()
+  invoke void @f()
+    to label %shared.cont unwind label %inner
+shared.cont:
+  unreachable
+inner:
+  catchpad []
+    to label %inner.catch unwind label %inner.end
+inner.catch:
+  call void @h(i32 %x)
+  unreachable
+inner.end:
+  catchendpad unwind label %left.end
+exit:
+  ret void
+}
+; Like @test3, %left and %right are siblings with %entry as the parent of both,
+; while %left and %right are both parents of %inner.  This case makes %left a
+; catch and %right a cleanup so that %inner unwinds to %left.end, which is a
+; block in %entry.  The %inner funclet is cloned for %left and %right, but the
+; copy of %inner.end for %right must have its unwind edge removed because the
+; catchendpad at %left.end is not compatible with %right.
+; CHECK-LABEL: define void @test5(
+; CHECK:     left:
+; CHECK:       catchpad []
+; CHECK:           to label %left.catch unwind label %[[LEFT_END:.+]]
+; CHECK:     left.catch:
+; CHECK:           to label %[[SHARED_CONT_LEFT:.+]] unwind label %[[INNER_LEFT:.+]]
+; CHECK:     [[LEFT_END]]:
+; CHECK:       catchendpad unwind label %right
+; CHECK:     right:
+; CHECK:       %r = cleanuppad []
+; CHECK:           to label %[[SHARED_CONT_RIGHT:.+]] unwind label %[[INNER_RIGHT:.+]]
+; CHECK:     [[SHARED_CONT_RIGHT]]:
+; CHECK:       unreachable
+; CHECK:     [[SHARED_CONT_LEFT]]:
+; CHECK:       unreachable
+; CHECK:     [[INNER_RIGHT]]:
+; CHECK:       catchpad []
+; CHECK:           to label %[[INNER_CATCH_RIGHT:.+]] unwind label %[[INNER_END_RIGHT:.+]]
+; CHECK:     [[INNER_LEFT]]:
+; CHECK:       catchpad []
+; CHECK:           to label %[[INNER_CATCH_LEFT:.+]] unwind label %[[INNER_END_LEFT:.+]]
+; CHECK:     [[INNER_CATCH_RIGHT]]:
+; CHECK:       [[X_RELOAD_R:\%.+]] = load i32, i32* %x.wineh.spillslot
+; CHECK:       call void @h(i32 [[X_RELOAD_R]])
+; CHECK:       unreachable
+; CHECK:     [[INNER_CATCH_LEFT]]:
+; CHECK:       [[X_RELOAD_L:\%.+]] = load i32, i32* %x.wineh.spillslot
+; CHECK:       call void @h(i32 [[X_RELOAD_L]])
+; CHECK:       unreachable
+; CHECK:     [[INNER_END_LEFT]]:
+; CHECK:       catchendpad unwind label %[[LEFT_END]]
+; CHECK:     [[INNER_END_RIGHT]]:
+; CHECK:       catchendpad unwind to caller
+
+define void @test6() personality i32 (...)* @__CxxFrameHandler3 {
+entry:
+  invoke void @f()
+    to label %exit unwind label %left
+left:
+  catchpad []
+    to label %left.catch unwind label %left.end
+left.catch:
+  br label %shared
+left.end:
+  catchendpad unwind label %middle
+middle:
+  %m = catchpad []
+    to label %middle.catch unwind label %middle.end
+middle.catch:
+  catchret %m to label %exit
+middle.end:
+  catchendpad unwind label %right
+right:
+  %r = cleanuppad []
+  br label %shared
+shared:
+  %x = call i32 @g()
+  invoke void @f()
+    to label %shared.cont unwind label %inner
+shared.cont:
+  unreachable
+inner:
+  catchpad []
+    to label %inner.catch unwind label %inner.end
+inner.catch:
+  call void @h(i32 %x)
+  unreachable
+inner.end:
+  catchendpad unwind label %left.end
+exit:
+  ret void
+}
+; This is like @test5 but it inserts another sibling between %left and %right.
+; In this case %left, %middle and %right are all siblings, while %left and
+; %right are both parents of %inner.  This checks the proper handling of the
+; catchendpad in %inner.end (which will be cloned so that %left and %right both
+; have copies) unwinding to a catchendpad that unwinds to a sibling.
+; CHECK-LABEL: define void @test6(
+; CHECK:     left:
+; CHECK:       catchpad []
+; CHECK:           to label %left.catch unwind label %[[LEFT_END:.+]]
+; CHECK:     left.catch:
+; CHECK:           to label %[[SHARED_CONT_LEFT:.+]] unwind label %[[INNER_LEFT:.+]]
+; CHECK:     [[LEFT_END]]:
+; CHECK:       catchendpad unwind label %middle
+; CHECK:     middle:
+; CHECK:       catchpad []
+; CHECK:         to label %middle.catch unwind label %middle.end
+; CHECK:     middle.catch:
+; CHECK:       catchret %m to label %exit
+; CHECK:     middle.end:
+; CHECK:       catchendpad unwind label %right
+; CHECK:     right:
+; CHECK:       %r = cleanuppad []
+; CHECK:           to label %[[SHARED_CONT_RIGHT:.+]] unwind label %[[INNER_RIGHT:.+]]
+; CHECK:     [[SHARED_CONT_RIGHT]]:
+; CHECK:       unreachable
+; CHECK:     [[SHARED_CONT_LEFT]]:
+; CHECK:       unreachable
+; CHECK:     [[INNER_RIGHT]]:
+; CHECK:       catchpad []
+; CHECK:           to label %[[INNER_CATCH_RIGHT:.+]] unwind label %[[INNER_END_RIGHT:.+]]
+; CHECK:     [[INNER_LEFT]]:
+; CHECK:       catchpad []
+; CHECK:           to label %[[INNER_CATCH_LEFT:.+]] unwind label %[[INNER_END_LEFT:.+]]
+; CHECK:     [[INNER_CATCH_RIGHT]]:
+; CHECK:       [[X_RELOAD_R:\%.+]] = load i32, i32* %x.wineh.spillslot
+; CHECK:       call void @h(i32 [[X_RELOAD_R]])
+; CHECK:       unreachable
+; CHECK:     [[INNER_CATCH_LEFT]]:
+; CHECK:       [[X_RELOAD_L:\%.+]] = load i32, i32* %x.wineh.spillslot
+; CHECK:       call void @h(i32 [[X_RELOAD_L]])
+; CHECK:       unreachable
+; CHECK:     [[INNER_END_LEFT]]:
+; CHECK:       catchendpad unwind label %[[LEFT_END]]
+; CHECK:     [[INNER_END_RIGHT]]:
+; CHECK:       catchendpad unwind to caller
+
+
+define void @test7() personality i32 (...)* @__CxxFrameHandler3 {
+entry:
+  invoke void @f()
+    to label %exit unwind label %left
+left:
+  catchpad []
+    to label %left.catch unwind label %left.end
+left.catch:
+  br label %shared
+left.end:
+  catchendpad unwind label %right
+right:
+  %r = cleanuppad []
+  br label %shared
+shared:
+  %x = call i32 @g()
+  invoke void @f()
+    to label %shared.cont unwind label %inner
+shared.cont:
+  unreachable
+inner:
+  catchpad []
+    to label %inner.catch unwind label %inner.end
+inner.catch:
+  call void @h(i32 %x)
+  unreachable
+inner.end:
+  catchendpad unwind label %inner.sibling
+inner.sibling:
+  %is = cleanuppad []
+  call void @h(i32 0)
+  cleanupret %is unwind label %left.end
+exit:
+  ret void
+}
+; This is like @test5 but instead of unwinding to %left.end, the catchendpad
+; in %inner.end unwinds to a sibling cleanup pad. Both %inner (along with its
+; associated blocks) and %inner.sibling must be cloned for %left and %right.
+; The clones of %inner will be identical, but the copy of %inner.sibling for
+; %right must end with an unreachable instruction, because it cannot unwind to
+; %left.end.
+; CHECK-LABEL: define void @test7(
+; CHECK:     left:
+; CHECK:       catchpad []
+; CHECK:           to label %left.catch unwind label %[[LEFT_END:.+]]
+; CHECK:     left.catch:
+; CHECK:           to label %[[SHARED_CONT_LEFT:.+]] unwind label %[[INNER_LEFT:.+]]
+; CHECK:     [[LEFT_END]]:
+; CHECK:       catchendpad unwind label %[[RIGHT:.+]]
+; CHECK:     [[RIGHT]]:
+; CHECK:       [[R:\%.+]] = cleanuppad []
+; CHECK:           to label %[[SHARED_CONT_RIGHT:.+]] unwind label %[[INNER_RIGHT:.+]]
+; CHECK:     [[SHARED_CONT_RIGHT]]:
+; CHECK:       unreachable
+; CHECK:     [[SHARED_CONT_LEFT]]:
+; CHECK:       unreachable
+; CHECK:     [[INNER_RIGHT]]:
+; CHECK:       catchpad []
+; CHECK:           to label %[[INNER_CATCH_RIGHT:.+]] unwind label %[[INNER_END_RIGHT:.+]]
+; CHECK:     [[INNER_LEFT]]:
+; CHECK:       catchpad []
+; CHECK:           to label %[[INNER_CATCH_LEFT:.+]] unwind label %[[INNER_END_LEFT:.+]]
+; CHECK:     [[INNER_CATCH_RIGHT]]:
+; CHECK:       [[X_RELOAD_R:\%.+]] = load i32, i32* %x.wineh.spillslot
+; CHECK:       call void @h(i32 [[X_RELOAD_R]])
+; CHECK:       unreachable
+; CHECK:     [[INNER_CATCH_LEFT]]:
+; CHECK:       [[X_RELOAD_L:\%.+]] = load i32, i32* %x.wineh.spillslot
+; CHECK:       call void @h(i32 [[X_RELOAD_L]])
+; CHECK:       unreachable
+; CHECK:     [[INNER_END_LEFT]]:
+; CHECK:       catchendpad unwind label %[[INNER_SIBLING_LEFT:.+]]
+; CHECK:     [[INNER_END_RIGHT]]:
+; CHECK:       catchendpad unwind label %[[INNER_SIBLING_RIGHT:.+]]
+; CHECK:     [[INNER_SIBLING_RIGHT]]
+; CHECK:       [[IS_R:\%.+]] = cleanuppad []
+; CHECK:       call void @h(i32 0)
+; CHECK:       unreachable
+; CHECK:     [[INNER_SIBLING_LEFT]]
+; CHECK:       [[IS_L:\%.+]] = cleanuppad []
+; CHECK:       call void @h(i32 0)
+; CHECK:       cleanupret [[IS_L]] unwind label %[[LEFT_END]]
+
+
+define void @test8() personality i32 (...)* @__CxxFrameHandler3 {
+entry:
+  invoke void @f()
+    to label %invoke.cont unwind label %left
+invoke.cont:
+  invoke void @f()
+    to label %unreachable unwind label %right
+left:
+  cleanuppad []
+  invoke void @f() to label %unreachable unwind label %inner
+right:
+  catchpad []
+    to label %right.catch unwind label %right.end
+right.catch:
+  invoke void @f() to label %unreachable unwind label %inner
+right.end:
+  catchendpad unwind to caller
+inner:
+  %i = cleanuppad []
+  %x = call i32 @g()
+  call void @h(i32 %x)
+  cleanupret %i unwind label %right.end
+unreachable:
+  unreachable
+}
+; Another case of a two-parent child (like @test1), this time
+; with the join at the entry itself instead of following a
+; non-pad join.
+; CHECK-LABEL: define void @test8(
+; CHECK:     invoke.cont:
+; CHECK:           to label %[[UNREACHABLE_ENTRY:.+]] unwind label %right
+; CHECK:     left:
+; CHECK:           to label %[[UNREACHABLE_LEFT:.+]] unwind label %[[INNER_LEFT:.+]]
+; CHECK:     right:
+; CHECK:           to label %right.catch unwind label %right.end
+; CHECK:     right.catch:
+; CHECK:           to label %unreachable unwind label %[[INNER_RIGHT:.+]]
+; CHECK:     right.end:
+; CHECK:       catchendpad unwind to caller
+; CHECK:     [[INNER_RIGHT]]:
+; CHECK:       [[I_R:\%.+]] = cleanuppad []
+; CHECK:       [[X_R:\%.+]] = call i32 @g()
+; CHECK:       call void @h(i32 [[X_R]])
+; CHECK:       cleanupret [[I_R]] unwind label %right.end
+; CHECK:     [[INNER_LEFT]]:
+; CHECK:       [[I_L:\%.+]] = cleanuppad []
+; CHECK:       [[X_L:\%.+]] = call i32 @g()
+; CHECK:       call void @h(i32 [[X_L]])
+; CHECK:       unreachable
+; CHECK:     unreachable:
+; CHECK:       unreachable
+; CHECK:     [[UNREACHABLE_LEFT]]:
+; CHECK:       unreachable
+; CHECK:     [[UNREACHABLE_ENTRY]]:
+; CHECK:       unreachable
+
+
+define void @test9() personality i32 (...)* @__CxxFrameHandler3 {
+entry:
+  invoke void @f()
+    to label %invoke.cont unwind label %left
+invoke.cont:
+  invoke void @f()
+    to label %unreachable unwind label %right
+left:
+  cleanuppad []
+  br label %shared
+right:
+  catchpad []
+    to label %right.catch unwind label %right.end
+right.catch:
+  br label %shared
+right.end:
+  catchendpad unwind to caller
+shared:
+  invoke void @f()
+    to label %unreachable unwind label %inner
+inner:
+  cleanuppad []
+  invoke void @f()
+    to label %unreachable unwind label %inner.child
+inner.child:
+  cleanuppad []
+  %x = call i32 @g()
+  call void @h(i32 %x)
+  unreachable
+unreachable:
+  unreachable
+}
+; %inner is a two-parent child which itself has a child; need
+; to make two copies of both the %inner and %inner.child.
+; CHECK-LABEL: define void @test9(
+; CHECK:     invoke.cont:
+; CHECK:               to label %[[UNREACHABLE_ENTRY:.+]] unwind label %right
+; CHECK:     left:
+; CHECK:               to label %[[UNREACHABLE_LEFT:.+]] unwind label %[[INNER_LEFT:.+]]
+; CHECK:     right:
+; CHECK:               to label %right.catch unwind label %right.end
+; CHECK:     right.catch:
+; CHECK:               to label %[[UNREACHABLE_RIGHT:.+]] unwind label %[[INNER_RIGHT:.+]]
+; CHECK:     right.end:
+; CHECK:       catchendpad unwind to caller
+; CHECK:     [[INNER_RIGHT]]:
+; CHECK:               to label %[[UNREACHABLE_INNER_RIGHT:.+]] unwind label %[[INNER_CHILD_RIGHT:.+]]
+; CHECK:     [[INNER_LEFT]]:
+; CHECK:               to label %[[UNREACHABLE_INNER_LEFT:.+]] unwind label %[[INNER_CHILD_LEFT:.+]]
+; CHECK:     [[INNER_CHILD_RIGHT]]:
+; CHECK:       [[TMP:\%.+]] = cleanuppad []
+; CHECK:       [[X:\%.+]] = call i32 @g()
+; CHECK:       call void @h(i32 [[X]])
+; CHECK:       unreachable
+; CHECK:     [[INNER_CHILD_LEFT]]:
+; CHECK:       [[TMP:\%.+]] = cleanuppad []
+; CHECK:       [[X:\%.+]] = call i32 @g()
+; CHECK:       call void @h(i32 [[X]])
+; CHECK:       unreachable
+; CHECK:     [[UNREACHABLE_INNER_RIGHT]]:
+; CHECK:       unreachable
+; CHECK:     [[UNREACHABLE_INNER_LEFT]]:
+; CHECK:       unreachable
+; CHECK:     [[UNREACHABLE_RIGHT]]:
+; CHECK:       unreachable
+; CHECK:     [[UNREACHABLE_LEFT]]:
+; CHECK:       unreachable
+; CHECK:     [[UNREACHABLE_ENTRY]]:
+; CHECK:       unreachable
+
+
+define void @test10() personality i32 (...)* @__CxxFrameHandler3 {
+entry:
+  invoke void @f()
+    to label %invoke.cont unwind label %left
+invoke.cont:
+  invoke void @f()
+    to label %unreachable unwind label %right
+left:
+  cleanuppad []
+  call void @h(i32 1)
+  invoke void @f()
+    to label %unreachable unwind label %right
+right:
+  cleanuppad []
+  call void @h(i32 2)
+  invoke void @f()
+    to label %unreachable unwind label %left
+unreachable:
+  unreachable
+}
+; This is an irreducible loop with two funclets that enter each other;
+; need to make two copies of each funclet (one a child of root, the
+; other a child of the opposite funclet), but also make sure not to
+; clone self-descendants (if we tried to do that we'd need to make an
+; infinite number of them).  Presumably if optimizations ever generated
+; such a thing it would mean that one of the two cleanups was originally
+; the parent of the other, but that we'd somehow lost track in the CFG
+; of which was which along the way; generating each possibility lets
+; whichever case was correct execute correctly.
+; CHECK-LABEL: define void @test10(
+; CHECK:     entry:
+; CHECK:               to label %invoke.cont unwind label %[[LEFT:.+]]
+; CHECK:     invoke.cont:
+; CHECK:               to label %[[UNREACHABLE_ENTRY:.+]] unwind label %[[RIGHT:.+]]
+; CHECK:     [[LEFT_FROM_RIGHT:.+]]:
+; CHECK:       call void @h(i32 1)
+; CHECK:       call void @f()
+; CHECK:       unreachable
+; CHECK:     [[LEFT]]:
+; CHECK:       call void @h(i32 1)
+; CHECK:       invoke void @f()
+; CHECK:               to label %[[UNREACHABLE_LEFT:.+]] unwind label %[[RIGHT_FROM_LEFT:.+]]
+; CHECK:     [[RIGHT]]:
+; CHECK:       call void @h(i32 2)
+; CHECK:       invoke void @f()
+; CHECK:               to label %[[UNREACHABLE_RIGHT:.+]] unwind label %[[LEFT_FROM_RIGHT]]
+; CHECK:     [[RIGHT_FROM_LEFT]]:
+; CHECK:       call void @h(i32 2)
+; CHECK:       call void @f()
+; CHECK:       unreachable
+; CHECK:     [[UNREACHABLE_RIGHT]]:
+; CHECK:       unreachable
+; CHECK:     [[UNREACHABLE_LEFT]]:
+; CHECK:       unreachable
+; CHECK:     [[UNREACHABLE_ENTRY]]:
+; CHECK:       unreachable
+
+
+define void @test11() personality i32 (...)* @__CxxFrameHandler3 {
+entry:
+  invoke void @f()
+    to label %exit unwind label %left
+left:
+  catchpad []
+    to label %left.catch unwind label %left.sibling
+left.catch:
+  br label %shared
+left.sibling:
+  %ls = catchpad []
+    to label %left.sibling.catch unwind label %left.end
+left.sibling.catch:
+  catchret %ls to label %exit
+left.end:
+  catchendpad unwind label %right
+right:
+  catchpad []
+    to label %right.catch unwind label %right.end
+right.catch:
+  br label %shared
+right.end:
+  catchendpad unwind to caller
+shared:
+  %x = call i32 @g()
+  invoke void @f()
+    to label %shared.cont unwind label %inner
+shared.cont:
+  unreachable
+inner:
+  catchpad []
+    to label %inner.catch unwind label %inner.end
+inner.catch:
+  call void @h(i32 %x)
+  unreachable
+inner.end:
+  catchendpad unwind label %left.end
+exit:
+  ret void
+}
+; This is a variation of @test4 in which the shared child funclet unwinds to a
+; catchend pad that is the unwind destination of %left.sibling rather than %left
+; but is still a valid destination for %inner as reach from %left.
+; When %inner is cloned a copy of %inner.end will be made for both %left and
+; %right, but because the catchpad in %right does not unwind to %left.end the
+; unwind edge from the copy of %inner.end for %right must be removed.
+; CHECK-LABEL: define void @test11(
+; CHECK:     left:
+; CHECK:       catchpad []
+; CHECK:           to label %left.catch unwind label %left.sibling
+; CHECK:     left.catch:
+; CHECK:           to label %[[SHARED_CONT_LEFT:.+]] unwind label %[[INNER_LEFT:.+]]
+; CHECK:     left.sibling:
+; CHECK:       catchpad []
+; CHECK:           to label %left.sibling.catch unwind label %[[LEFT_END:.+]]
+; CHECK:     [[LEFT_END]]:
+; CHECK:       catchendpad unwind label %right
+; CHECK:     right:
+; CHECK:           to label %right.catch unwind label %[[RIGHT_END:.+]]
+; CHECK:     right.catch:
+; CHECK:           to label %[[SHARED_CONT_RIGHT:.+]] unwind label %[[INNER_RIGHT:.+]]
+; CHECK:     [[RIGHT_END]]:
+; CHECK:       catchendpad unwind to caller
+; CHECK:     [[SHARED_CONT_RIGHT]]:
+; CHECK:       unreachable
+; CHECK:     [[SHARED_CONT_LEFT]]:
+; CHECK:       unreachable
+; CHECK:     [[INNER_RIGHT]]:
+; CHECK:       catchpad []
+; CHECK:           to label %[[INNER_CATCH_RIGHT:.+]] unwind label %[[INNER_END_RIGHT:.+]]
+; CHECK:     [[INNER_LEFT]]:
+; CHECK:       catchpad []
+; CHECK:           to label %[[INNER_CATCH_LEFT:.+]] unwind label %[[INNER_END_LEFT:.+]]
+; CHECK:     [[INNER_CATCH_RIGHT]]:
+; CHECK:       [[X_RELOAD_R:\%.+]] = load i32, i32* %x.wineh.spillslot
+; CHECK:       call void @h(i32 [[X_RELOAD_R]])
+; CHECK:       unreachable
+; CHECK:     [[INNER_CATCH_LEFT]]:
+; CHECK:       [[X_RELOAD_L:\%.+]] = load i32, i32* %x.wineh.spillslot
+; CHECK:       call void @h(i32 [[X_RELOAD_L]])
+; CHECK:       unreachable
+; CHECK:     [[INNER_END_LEFT]]:
+; CHECK:       catchendpad unwind label %[[LEFT_END]]
+; CHECK:     [[INNER_END_RIGHT]]:
+; CHECK:       catchendpad unwind to caller
+
+
+define void @test12() personality i32 (...)* @__CxxFrameHandler3 {
+entry:
+  invoke void @f()
+    to label %exit unwind label %left
+left:
+  catchpad []
+    to label %left.catch unwind label %right
+left.catch:
+  br label %shared
+right:
+  catchpad []
+    to label %right.catch unwind label %right.end
+right.catch:
+  br label %shared
+right.end:
+  catchendpad unwind to caller
+shared:
+  %x = call i32 @g()
+  invoke void @f()
+    to label %shared.cont unwind label %inner
+shared.cont:
+  unreachable
+inner:
+  catchpad []
+    to label %inner.catch unwind label %inner.end
+inner.catch:
+  call void @h(i32 %x)
+  unreachable
+inner.end:
+  catchendpad unwind label %right.end
+exit:
+  ret void
+}
+; In this case %left and %right are both parents of %inner, so %inner must be
+; cloned but the catchendpad unwind target in %inner.end is valid for both
+; parents, so the unwind edge should not be removed in either case.
+; CHECK-LABEL: define void @test12(
+; CHECK:     left:
+; CHECK:       catchpad []
+; CHECK:           to label %left.catch unwind label %right
+; CHECK:     left.catch:
+; CHECK:           to label %[[SHARED_CONT_LEFT:.+]] unwind label %[[INNER_LEFT:.+]]
+; CHECK:     right:
+; CHECK:           to label %right.catch unwind label %[[RIGHT_END:.+]]
+; CHECK:     right.catch:
+; CHECK:           to label %[[SHARED_CONT_RIGHT:.+]] unwind label %[[INNER_RIGHT:.+]]
+; CHECK:     [[RIGHT_END]]:
+; CHECK:       catchendpad unwind to caller
+; CHECK:     [[SHARED_CONT_RIGHT]]:
+; CHECK:       unreachable
+; CHECK:     [[SHARED_CONT_LEFT]]:
+; CHECK:       unreachable
+; CHECK:     [[INNER_RIGHT]]:
+; CHECK:       catchpad []
+; CHECK:           to label %[[INNER_CATCH_RIGHT:.+]] unwind label %[[INNER_END_RIGHT:.+]]
+; CHECK:     [[INNER_LEFT]]:
+; CHECK:       catchpad []
+; CHECK:           to label %[[INNER_CATCH_LEFT:.+]] unwind label %[[INNER_END_LEFT:.+]]
+; CHECK:     [[INNER_CATCH_RIGHT]]:
+; CHECK:       [[X_RELOAD_R:\%.+]] = load i32, i32* %x.wineh.spillslot
+; CHECK:       call void @h(i32 [[X_RELOAD_R]])
+; CHECK:       unreachable
+; CHECK:     [[INNER_CATCH_LEFT]]:
+; CHECK:       [[X_RELOAD_L:\%.+]] = load i32, i32* %x.wineh.spillslot
+; CHECK:       call void @h(i32 [[X_RELOAD_L]])
+; CHECK:       unreachable
+; CHECK:     [[INNER_END_LEFT]]:
+; CHECK:       catchendpad unwind label %[[RIGHT_END]]
+; CHECK:     [[INNER_END_RIGHT]]:
+; CHECK:       catchendpad unwind label %[[RIGHT_END]]
+
+define void @test13() personality i32 (...)* @__CxxFrameHandler3 {
+entry:
+  invoke void @f()
+    to label %invoke.cont unwind label %left
+invoke.cont:
+  invoke void @f()
+    to label %exit unwind label %right
+left:
+  %l = catchpad []
+    to label %left.cont unwind label %left.end
+left.cont:
+  invoke void @f()
+    to label %left.ret unwind label %inner
+left.ret:
+  catchret %l to label %invoke.cont
+left.end:
+  catchendpad unwind to caller
+right:
+  %r = catchpad []
+    to label %right.catch unwind label %right.end
+right.catch:
+  invoke void @f()
+    to label %right.ret unwind label %inner
+right.ret:
+  catchret %r to label %exit
+right.end:
+  catchendpad unwind to caller
+shared:
+  call void @h(i32 0)
+  unreachable
+inner:
+  %i = catchpad []
+    to label %inner.catch unwind label %inner.end
+inner.catch:
+  call void @h(i32 1)
+  catchret %i to label %shared
+inner.end:
+  catchendpad unwind label %left.end
+exit:
+  ret void
+}
+; This case tests the scenario where a funclet with multiple parents uses a
+; catchret to return to a block that may exist in either parent funclets.
+; Both %left and %right are parents of %inner.  During common block cloning
+; a clone of %shared will be made so that both %left and %right have a copy,
+; but the copy of %shared for one of the parent funclets will be unreachable
+; until the %inner funclet is cloned.  When the %inner.catch block is cloned
+; during the %inner funclet cloning, the catchret instruction should be updated
+; so that the catchret in the copy %inner.catch for %left returns to the copy of
+; %shared in %left and the catchret in the copy of %inner.catch for %right
+; returns to the copy of %shared for %right.
+; CHECK-LABEL: define void @test13(
+; CHECK:     left:
+; CHECK:       %l = catchpad []
+; CHECK:           to label %left.cont unwind label %left.end
+; CHECK:     left.cont:
+; CHECK:       invoke void @f()
+; CHECK:           to label %left.ret unwind label %[[INNER_LEFT:.+]]
+; CHECK:     left.ret:
+; CHECK:       catchret %l to label %invoke.cont
+; CHECK:     left.end:
+; CHECK:       catchendpad unwind to caller
+; CHECK:     right:
+; CHECK:       %r = catchpad []
+; CHECK:           to label %right.catch unwind label %right.end
+; CHECK:     right.catch:
+; CHECK:       invoke void @f()
+; CHECK:           to label %right.ret unwind label %[[INNER_RIGHT:.+]]
+; CHECK:     right.ret:
+; CHECK:       catchret %r to label %exit
+; CHECK:     right.end:
+; CHECK:       catchendpad unwind to caller
+; CHECK:     [[SHARED_RIGHT:.+]]:
+; CHECK:       call void @h(i32 0)
+; CHECK:       unreachable
+; CHECK:     [[SHARED_LEFT:.+]]:
+; CHECK:       call void @h(i32 0)
+; CHECK:       unreachable
+; CHECK:     [[INNER_RIGHT]]:
+; CHECK:       %[[I_RIGHT:.+]] = catchpad []
+; CHECK:           to label %[[INNER_CATCH_RIGHT:.+]] unwind label %[[INNER_END_RIGHT:.+]]
+; CHECK:     [[INNER_LEFT]]:
+; CHECK:       %[[I_LEFT:.+]] = catchpad []
+; CHECK:           to label %[[INNER_CATCH_LEFT:.+]] unwind label %[[INNER_END_LEFT:.+]]
+; CHECK:     [[INNER_CATCH_RIGHT]]:
+; CHECK:       call void @h(i32 1)
+; CHECK:       catchret %[[I_RIGHT]] to label %[[SHARED_RIGHT]]
+; CHECK:     [[INNER_CATCH_LEFT]]:
+; CHECK:       call void @h(i32 1)
+; CHECK:       catchret %[[I_LEFT]] to label %[[SHARED_LEFT]]
+; CHECK:     [[INNER_END_LEFT]]:
+; CHECK:       catchendpad unwind label %[[LEFT_END]]
+; CHECK:     [[INNER_END_RIGHT]]:
+; CHECK:       catchendpad unwind to caller
+
+
+define void @test14() personality i32 (...)* @__CxxFrameHandler3 {
+entry:
+  invoke void @f()
+    to label %exit unwind label %left
+left:
+  %l = catchpad []
+    to label %shared unwind label %left.end
+left.cont:
+  invoke void @f()
+    to label %left.ret unwind label %right
+left.ret: 
+  catchret %l to label %exit
+left.end:
+  catchendpad unwind to caller
+right:
+  catchpad []
+    to label %right.catch unwind label %right.end
+right.catch:
+  br label %shared
+right.end:
+  catchendpad unwind label %left.end
+shared:
+  invoke void @f()
+    to label %shared.cont unwind label %inner
+shared.cont:
+  unreachable
+inner:
+  %i = catchpad []
+    to label %inner.catch unwind label %inner.end
+inner.catch:
+  call void @h(i32 0)
+  catchret %i to label %left.cont
+inner.end:
+  catchendpad unwind label %left.end
+exit:
+  ret void
+}
+; This case tests another scenario where a funclet with multiple parents uses a
+; catchret to return to a block in one of the parent funclets.  Here %right and
+; %left are both parents of %inner and %left is a parent of %right.  The
+; catchret in %inner.catch will cause %left.cont and %left.ret to be cloned for
+; both %left and %right, but the catchret in %left.ret is invalid for %right
+; but the catchret instruction in the copy of %left.ret for %right will be
+; removed as an implausible terminator.
+; CHECK-LABEL: define void @test14(
+; CHECK:     left:
+; CHECK:       %l = catchpad []
+; CHECK:           to label %[[SHARED_LEFT:.+]] unwind label %[[LEFT_END:.+]]
+; CHECK:     [[LEFT_CONT:left.cont.*]]:
+; CHECK:       invoke void @f()
+; CHECK:           to label %[[LEFT_RET:.+]] unwind label %[[RIGHT:.+]]
+; CHECK:     [[LEFT_RET]]:
+; CHECK:       catchret %l to label %exit
+; CHECK:     [[LEFT_END]]:
+; CHECK:       catchendpad unwind to caller
+; CHECK:     [[RIGHT]]:
+; CHECK:       catchpad []
+; CHECK:           to label %[[RIGHT_CATCH:.+]] unwind label %[[RIGHT_END:.+]]
+; CHECK:     [[RIGHT_CATCH]]:
+; CHECK:       invoke void @f()
+; CHECK:           to label %[[SHARED_CONT_RIGHT:.+]] unwind label %[[INNER_RIGHT:.+]]
+; CHECK:     [[RIGHT_END]]:
+; CHECK:       catchendpad unwind label %[[LEFT_END]]
+; CHECK:     [[SHARED_LEFT]]:
+; CHECK:       invoke void @f()
+; CHECK:           to label %[[SHARED_CONT_LEFT:.+]] unwind label %[[INNER_LEFT:.+]]
+; CHECK:     [[SHARED_CONT_RIGHT]]:
+; CHECK:       unreachable
+; CHECK:     [[SHARED_CONT_LEFT]]:
+; CHECK:       unreachable
+; CHECK:     [[INNER_LEFT]]:
+; CHECK:       [[I_LEFT:\%.+]] = catchpad []
+; CHECK:           to label %[[INNER_CATCH_LEFT:.+]] unwind label %[[INNER_END_LEFT:.+]]
+; CHECK:     [[INNER_RIGHT]]:
+; CHECK:       [[I_RIGHT:\%.+]] = catchpad []
+; CHECK:           to label %[[INNER_CATCH_RIGHT:.+]] unwind label %[[INNER_END_RIGHT:.+]]
+; CHECK:     [[INNER_CATCH_LEFT]]:
+; CHECK:       call void @h(i32 0)
+; CHECK:       catchret [[I_LEFT]] to label %[[LEFT_CONT]]
+; CHECK:     [[INNER_CATCH_RIGHT]]:
+; CHECK:       call void @h(i32 0)
+; CHECK:       unreachable
+; CHECK:     [[INNER_END_LEFT]]:
+; CHECK:       catchendpad unwind label %[[LEFT_END]]
+; CHECK:     [[INNER_END_RIGHT]]:
+; CHECK:       catchendpad unwind to caller
+
+define void @test15() personality i32 (...)* @__CxxFrameHandler3 {
+entry:
+  invoke void @f()
+    to label %exit unwind label %left
+left:
+  %l = catchpad []
+    to label %left.catch unwind label %left.end
+left.catch:
+  invoke void @f()
+    to label %shared unwind label %right
+left.ret:
+  catchret %l to label %exit
+left.end:
+  catchendpad unwind to caller
+right:
+  catchpad []
+    to label %right.catch unwind label %right.end
+right.catch:
+  br label %shared
+right.end:
+  catchendpad unwind label %left.end
+shared:
+  invoke void @f()
+    to label %shared.cont unwind label %inner
+shared.cont:
+  unreachable
+inner:
+  %i = catchpad []
+    to label %inner.catch unwind label %inner.end
+inner.catch:
+  call void @h(i32 0)
+  catchret %i to label %left.ret
+inner.end:
+  catchendpad unwind label %left.end
+exit:
+  ret void
+}
+; This case is a variation of test14 but instead of returning to an invoke the
+; catchret in %inner.catch returns to a catchret instruction.
+; CHECK-LABEL: define void @test15(
+; CHECK:     left:
+; CHECK:       %l = catchpad []
+; CHECK:           to label %left.catch unwind label %[[LEFT_END:.+]]
+; CHECK:     left.catch:
+; CHECK:       invoke void @f()
+; CHECK:           to label %[[SHARED_LEFT:.+]] unwind label %[[RIGHT:.+]]
+; CHECK:     [[LEFT_RET_RIGHT:.+]]:
+; CHECK:       unreachable
+; CHECK:     [[LEFT_RET_LEFT:.+]]:
+; CHECK:       catchret %l to label %exit
+; CHECK:     [[LEFT_END]]:
+; CHECK:       catchendpad unwind to caller
+; CHECK:     [[RIGHT]]:
+; CHECK:       catchpad []
+; CHECK:           to label %[[RIGHT_CATCH:.+]] unwind label %[[RIGHT_END:.+]]
+; CHECK:     [[RIGHT_CATCH]]:
+; CHECK:       invoke void @f()
+; CHECK:           to label %[[SHARED_CONT_RIGHT:.+]] unwind label %[[INNER_RIGHT:.+]]
+; CHECK:     [[RIGHT_END]]:
+; CHECK:       catchendpad unwind label %[[LEFT_END]]
+; CHECK:     [[SHARED_LEFT]]:
+; CHECK:       invoke void @f()
+; CHECK:           to label %[[SHARED_CONT_LEFT:.+]] unwind label %[[INNER_LEFT:.+]]
+; CHECK:     [[SHARED_CONT_RIGHT]]:
+; CHECK:       unreachable
+; CHECK:     [[SHARED_CONT_LEFT]]:
+; CHECK:       unreachable
+; CHECK:     [[INNER_LEFT]]:
+; CHECK:       [[I_LEFT:\%.+]] = catchpad []
+; CHECK:           to label %[[INNER_CATCH_LEFT:.+]] unwind label %[[INNER_END_LEFT:.+]]
+; CHECK:     [[INNER_RIGHT]]:
+; CHECK:       [[I_RIGHT:\%.+]] = catchpad []
+; CHECK:           to label %[[INNER_CATCH_RIGHT:.+]] unwind label %[[INNER_END_RIGHT:.+]]
+; CHECK:     [[INNER_CATCH_LEFT]]:
+; CHECK:       call void @h(i32 0)
+; CHECK:       catchret [[I_LEFT]] to label %[[LEFT_RET_LEFT]]
+; CHECK:     [[INNER_CATCH_RIGHT]]:
+; CHECK:       call void @h(i32 0)
+; CHECK:       catchret [[I_RIGHT]] to label %[[LEFT_RET_RIGHT]]
+; CHECK:     [[INNER_END_LEFT]]:
+; CHECK:       catchendpad unwind label %[[LEFT_END]]
+; CHECK:     [[INNER_END_RIGHT]]:
+; CHECK:       catchendpad unwind to caller
+
+
+define void @test16() personality i32 (...)* @__CxxFrameHandler3 {
+entry:
+  invoke void @f()
+    to label %exit unwind label %left
+left:
+  %l = cleanuppad []
+  br label %shared
+left.cont:
+  cleanupret %l unwind label %right
+left.end:
+  cleanupendpad %l unwind label %right
+right:
+  catchpad []
+    to label %right.catch unwind label %right.end
+right.catch:
+  br label %shared
+right.end:
+  catchendpad unwind to caller
+shared:
+  invoke void @f()
+    to label %shared.cont unwind label %inner
+shared.cont:
+  unreachable
+inner:
+  %i = catchpad []
+    to label %inner.catch unwind label %inner.end
+inner.catch:
+  call void @h(i32 0)
+  catchret %i to label %left.cont
+inner.end:
+  catchendpad unwind label %left.end
+exit:
+  ret void
+}
+; This case is another variation of test14 but here the catchret in %inner.catch
+; returns to a cleanupret instruction.
+; CHECK-LABEL: define void @test16(
+; CHECK:     left:
+; CHECK:       %l = cleanuppad []
+; CHECK:       invoke void @f()
+; CHECK:           to label %[[SHARED_CONT_LEFT:.+]] unwind label %[[INNER_LEFT:.+]]
+; CHECK:     [[LEFT_CONT_RIGHT:.+]]:
+; CHECK:       unreachable
+; CHECK:     [[LEFT_CONT_LEFT:.+]]:
+; CHECK:       cleanupret %l unwind label %[[RIGHT:.+]]
+; CHECK:     [[LEFT_END_LEFT:.+]]:
+; CHECK:       cleanupendpad %l unwind label %[[RIGHT]]
+; CHECK:     [[RIGHT]]:
+; CHECK:       catchpad []
+; CHECK:           to label %[[RIGHT_CATCH:.+]] unwind label %[[RIGHT_END:.+]]
+; CHECK:     [[RIGHT_CATCH]]:
+; CHECK:       invoke void @f()
+; CHECK:           to label %[[SHARED_CONT_RIGHT:.+]] unwind label %[[INNER_RIGHT:.+]]
+; CHECK:     [[RIGHT_END]]:
+; CHECK:       catchendpad unwind to caller
+; CHECK:     [[SHARED_CONT_RIGHT]]:
+; CHECK:       unreachable
+; CHECK:     [[SHARED_CONT_LEFT]]:
+; CHECK:       unreachable
+; CHECK:     [[INNER_RIGHT]]:
+; CHECK:       [[I_RIGHT:\%.+]] = catchpad []
+; CHECK:           to label %[[INNER_CATCH_RIGHT:.+]] unwind label %[[INNER_END_RIGHT:.+]]
+; CHECK:     [[INNER_LEFT]]:
+; CHECK:       [[I_LEFT:\%.+]] = catchpad []
+; CHECK:           to label %[[INNER_CATCH_LEFT:.+]] unwind label %[[INNER_END_LEFT:.+]]
+; CHECK:     [[INNER_CATCH_RIGHT]]:
+; CHECK:       call void @h(i32 0)
+; CHECK:       catchret [[I_RIGHT]] to label %[[LEFT_CONT_RIGHT]]
+; CHECK:     [[INNER_CATCH_LEFT]]:
+; CHECK:       call void @h(i32 0)
+; CHECK:       catchret [[I_LEFT]] to label %[[LEFT_CONT_LEFT]]
+; CHECK:     [[INNER_END_LEFT]]:
+; CHECK:       catchendpad unwind label %[[LEFT_END_LEFT]]
+; CHECK:     [[INNER_END_RIGHT]]:
+; CHECK:       catchendpad unwind to caller
+
+
+define void @test17() personality i32 (...)* @__CxxFrameHandler3 {
+entry:
+  invoke void @f()
+    to label %invoke.cont unwind label %left
+invoke.cont:
+  invoke void @f()
+    to label %exit unwind label %right
+left:
+  %l = cleanuppad []
+  br label %shared
+right:
+  catchpad []
+    to label %right.catch unwind label %right.end
+right.catch:
+  br label %shared
+right.end:
+  catchendpad unwind to caller
+shared:
+  invoke void @f()
+    to label %unreachable unwind label %inner
+unreachable:
+  unreachable
+inner:
+  %i = catchpad []
+    to label %inner.catch unwind label %inner.sibling
+inner.catch:
+  call void @h(i32 0)
+  unreachable
+inner.sibling:
+  %is = catchpad []
+    to label %inner.sibling.catch unwind label %inner.end
+inner.sibling.catch:
+  invoke void @f()
+    to label %unreachable unwind label %inner.end
+inner.end:
+  catchendpad unwind label %right.end
+exit:
+  ret void
+}
+; This case tests the scenario where two catchpads with the same catchendpad
+; have multiple parents.  Both %left and %right are parents of %inner and
+; %inner.sibling so both of the inner funclets must be cloned.  Because
+; the catchendpad in %inner.end unwinds to the catchendpad for %right, the
+; unwind edge should be removed for the copy of %inner.end that is reached
+; from %left.  In addition, the %inner.siblin.catch block contains an invoke
+; that unwinds to the shared inner catchendpad.  The unwind destination for
+; this invoke should be updated to unwind to the correct cloned %inner.end
+; for each path to the funclet.
+; CHECK-LABEL: define void @test17(
+; CHECK:     left:
+; CHECK:       %l = cleanuppad []
+; CHECK:       invoke void @f()
+; CHECK:           to label %[[SHARED_CONT_LEFT:.+]] unwind label %[[INNER_LEFT:.+]]
+; CHECK:     right:
+; CHECK:       catchpad []
+; CHECK:           to label %[[RIGHT_CATCH:.+]] unwind label %[[RIGHT_END:.+]]
+; CHECK:     [[RIGHT_CATCH]]:
+; CHECK:       invoke void @f()
+; CHECK:           to label %[[SHARED_CONT_RIGHT:.+]] unwind label %[[INNER_RIGHT:.+]]
+; CHECK:     [[RIGHT_END]]:
+; CHECK:       catchendpad unwind to caller
+; CHECK:     [[SHARED_CONT_RIGHT]]:
+; CHECK:       unreachable
+; CHECK:     [[SHARED_CONT_LEFT]]:
+; CHECK:       unreachable
+; CHECK:     [[INNER_RIGHT]]:
+; CHECK:       [[I_RIGHT:\%.+]] = catchpad []
+; CHECK:           to label %[[INNER_CATCH_RIGHT:.+]] unwind label %[[INNER_SIBLING_RIGHT:.+]]
+; CHECK:     [[INNER_LEFT]]:
+; CHECK:       [[I_LEFT:\%.+]] = catchpad []
+; CHECK:           to label %[[INNER_CATCH_LEFT:.+]] unwind label %[[INNER_SIBLING_LEFT:.+]]
+; CHECK:     [[INNER_CATCH_RIGHT]]:
+; CHECK:       call void @h(i32 0)
+; CHECK:       unreachable
+; CHECK:     [[INNER_CATCH_LEFT]]:
+; CHECK:       call void @h(i32 0)
+; CHECK:       unreachable
+; CHECK:     [[INNER_SIBLING_RIGHT]]:
+; CHECK:       [[IS_RIGHT:\%.+]] = catchpad []
+; CHECK:           to label %[[INNER_SIBLING_CATCH_RIGHT:.+]] unwind label %[[INNER_END_RIGHT:.+]]
+; CHECK:     [[INNER_SIBLING_LEFT]]:
+; CHECK:       [[IS_LEFT:\%.+]] = catchpad []
+; CHECK:           to label %[[INNER_SIBLING_CATCH_LEFT:.+]] unwind label %[[INNER_END_LEFT:.+]]
+; CHECK:     [[INNER_SIBLING_CATCH_RIGHT]]:
+; CHECK:       invoke void @f()
+; CHECK:         to label %[[UNREACHABLE_RIGHT:.+]] unwind label %[[INNER_END_RIGHT]]
+; CHECK:     [[INNER_SIBLING_CATCH_LEFT]]:
+; CHECK:       invoke void @f()
+; CHECK:         to label %[[UNREACHABLE_LEFT:.+]] unwind label %[[INNER_END_LEFT]]
+; CHECK:     [[INNER_END_LEFT]]:
+; CHECK:       catchendpad unwind to caller
+; CHECK:     [[INNER_END_RIGHT]]:
+; CHECK:       catchendpad unwind label %[[RIGHT_END]]
+
+
+define void @test18() personality i32 (...)* @__CxxFrameHandler3 {
+entry:
+  invoke void @f()
+    to label %invoke.cont unwind label %left
+invoke.cont:
+  invoke void @f()
+    to label %exit unwind label %right
+left:
+  %l = cleanuppad []
+  br label %shared
+right:
+  catchpad []
+    to label %right.catch unwind label %right.end
+right.catch:
+  br label %shared
+right.end:
+  catchendpad unwind to caller
+shared:
+  invoke void @f()
+    to label %unreachable unwind label %inner
+unreachable:
+  unreachable
+inner:
+  %i = catchpad []
+    to label %inner.catch unwind label %inner.sibling
+inner.catch:
+  invoke void @f()
+    to label %unreachable unwind label %inner.end
+inner.sibling:
+  %is = catchpad []
+    to label %inner.sibling.catch unwind label %inner.end
+inner.sibling.catch:
+  call void @h(i32 0)
+  unreachable
+inner.end:
+  catchendpad unwind label %right.end
+exit:
+  ret void
+}
+; This is like test17 except that the inner invoke is moved from the
+; %inner.sibling funclet to %inner so that it is unwinding to a
+; catchendpad block that has not yet been cloned.  The unwind destination
+; of the invoke should still be updated to reach the correct copy of
+; %inner.end for the path by which it is reached.
+; CHECK-LABEL: define void @test18(
+; CHECK:     left:
+; CHECK:       %l = cleanuppad []
+; CHECK:       invoke void @f()
+; CHECK:           to label %[[SHARED_CONT_LEFT:.+]] unwind label %[[INNER_LEFT:.+]]
+; CHECK:     right:
+; CHECK:       catchpad []
+; CHECK:           to label %[[RIGHT_CATCH:.+]] unwind label %[[RIGHT_END:.+]]
+; CHECK:     [[RIGHT_CATCH]]:
+; CHECK:       invoke void @f()
+; CHECK:           to label %[[SHARED_CONT_RIGHT:.+]] unwind label %[[INNER_RIGHT:.+]]
+; CHECK:     [[RIGHT_END]]:
+; CHECK:       catchendpad unwind to caller
+; CHECK:     [[SHARED_CONT_RIGHT]]:
+; CHECK:       unreachable
+; CHECK:     [[SHARED_CONT_LEFT]]:
+; CHECK:       unreachable
+; CHECK:     [[INNER_RIGHT]]:
+; CHECK:       [[I_RIGHT:\%.+]] = catchpad []
+; CHECK:           to label %[[INNER_CATCH_RIGHT:.+]] unwind label %[[INNER_SIBLING_RIGHT:.+]]
+; CHECK:     [[INNER_LEFT]]:
+; CHECK:       [[I_LEFT:\%.+]] = catchpad []
+; CHECK:           to label %[[INNER_CATCH_LEFT:.+]] unwind label %[[INNER_SIBLING_LEFT:.+]]
+; CHECK:     [[INNER_CATCH_RIGHT]]:
+; CHECK:       invoke void @f()
+; CHECK:         to label %[[UNREACHABLE_RIGHT:.+]] unwind label %[[INNER_END_RIGHT:.+]]
+; CHECK:     [[INNER_CATCH_LEFT]]:
+; CHECK:       invoke void @f()
+; CHECK:         to label %[[UNREACHABLE_LEFT:.+]] unwind label %[[INNER_END_LEFT:.+]]
+; CHECK:     [[INNER_SIBLING_RIGHT]]:
+; CHECK:       [[IS_RIGHT:\%.+]] = catchpad []
+; CHECK:           to label %[[INNER_SIBLING_CATCH_RIGHT:.+]] unwind label %[[INNER_END_RIGHT]]
+; CHECK:     [[INNER_SIBLING_LEFT]]:
+; CHECK:       [[IS_LEFT:\%.+]] = catchpad []
+; CHECK:           to label %[[INNER_SIBLING_CATCH_LEFT:.+]] unwind label %[[INNER_END_LEFT]]
+; CHECK:     [[INNER_SIBLING_CATCH_RIGHT]]:
+; CHECK:       call void @h(i32 0)
+; CHECK:       unreachable
+; CHECK:     [[INNER_SIBLING_CATCH_LEFT]]:
+; CHECK:       call void @h(i32 0)
+; CHECK:       unreachable
+; CHECK:     [[INNER_END_LEFT]]:
+; CHECK:       catchendpad unwind to caller
+; CHECK:     [[INNER_END_RIGHT]]:
+; CHECK:       catchendpad unwind label %[[RIGHT_END]]
+
+
+define void @test19() personality i32 (...)* @__CxxFrameHandler3 {
+entry:
+  invoke void @f()
+    to label %invoke.cont unwind label %left
+invoke.cont:
+  invoke void @f()
+    to label %exit unwind label %right
+left:
+  %l = cleanuppad []
+  br label %shared
+right:
+  catchpad []
+    to label %right.catch unwind label %right.end
+right.catch:
+  br label %shared
+right.end:
+  catchendpad unwind to caller
+shared:
+  invoke void @f()
+    to label %unreachable unwind label %inner
+unreachable:
+  unreachable
+inner:
+  %i = cleanuppad []
+  invoke void @f()
+    to label %unreachable unwind label %inner.end
+inner.end:
+  cleanupendpad %i unwind label %right.end
+exit:
+  ret void
+}
+; This case tests the scenario where an invoke in a funclet with multiple
+; parents unwinds to a cleanup end pad for the funclet.  The unwind destination
+; for the invoke should map to the correct copy of the cleanup end pad block.
+; CHECK-LABEL: define void @test19(
+; CHECK:     left:
+; CHECK:       %l = cleanuppad []
+; CHECK:       invoke void @f()
+; CHECK:           to label %[[SHARED_CONT_LEFT:.+]] unwind label %[[INNER_LEFT:.+]]
+; CHECK:     right:
+; CHECK:       catchpad []
+; CHECK:           to label %[[RIGHT_CATCH:.+]] unwind label %[[RIGHT_END:.+]]
+; CHECK:     [[RIGHT_CATCH]]:
+; CHECK:       invoke void @f()
+; CHECK:           to label %[[SHARED_CONT_RIGHT:.+]] unwind label %[[INNER_RIGHT:.+]]
+; CHECK:     [[RIGHT_END]]:
+; CHECK:       catchendpad unwind to caller
+; CHECK:     [[SHARED_CONT_RIGHT]]:
+; CHECK:       unreachable
+; CHECK:     [[SHARED_CONT_LEFT]]:
+; CHECK:       unreachable
+; CHECK:     [[INNER_RIGHT]]:
+; CHECK:       [[I_RIGHT:\%.+]] = cleanuppad []
+; CHECK:       invoke void @f()
+; CHECK:         to label %[[UNREACHABLE_RIGHT:.+]] unwind label %[[INNER_END_RIGHT:.+]]
+; CHECK:     [[INNER_LEFT]]:
+; CHECK:       [[I_LEFT:\%.+]] = cleanuppad []
+; CHECK:       invoke void @f()
+; CHECK:         to label %[[UNREACHABLE_LEFT:.+]] unwind label %[[INNER_END_LEFT:.+]]
+; CHECK:     [[INNER_END_RIGHT]]:
+; CHECK:       cleanupendpad [[I_RIGHT]] unwind label %[[RIGHT_END]]
+; CHECK:     [[INNER_END_LEFT]]:
+; CHECK:       cleanupendpad [[I_LEFT]] unwind to caller
+
+define void @test20() personality i32 (...)* @__CxxFrameHandler3 {
+entry:
+  invoke void @f()
+    to label %invoke.cont unwind label %left
+invoke.cont:
+  invoke void @f()
+    to label %exit unwind label %right
+left:
+  %l = cleanuppad []
+  br label %shared
+right:
+  catchpad []
+    to label %right.catch unwind label %right.end
+right.catch:
+  br label %shared
+right.end:
+  catchendpad unwind to caller
+shared:
+  invoke void @f()
+    to label %unreachable unwind label %inner
+unreachable:
+  unreachable
+inner:
+  %i = cleanuppad []
+  invoke void @f()
+    to label %unreachable unwind label %inner.cleanup
+inner.cleanup:
+  cleanuppad []
+  call void @f()
+  unreachable
+exit:
+  ret void
+}
+; This tests the case where a funclet with multiple parents contains an invoke
+; instruction that unwinds to a child funclet.  Here %left and %right are both
+; parents of %inner.  Initially %inner is the only parent of %inner.cleanup but
+; after %inner is cloned, %inner.cleanup has multiple parents and so it must
+; also be cloned.
+; CHECK-LABEL: define void @test20(
+; CHECK:     left:
+; CHECK:       %l = cleanuppad []
+; CHECK:       invoke void @f()
+; CHECK:           to label %[[SHARED_CONT_LEFT:.+]] unwind label %[[INNER_LEFT:.+]]
+; CHECK:     right:
+; CHECK:       catchpad []
+; CHECK:           to label %[[RIGHT_CATCH:.+]] unwind label %[[RIGHT_END:.+]]
+; CHECK:     [[RIGHT_CATCH]]:
+; CHECK:       invoke void @f()
+; CHECK:           to label %[[SHARED_CONT_RIGHT:.+]] unwind label %[[INNER_RIGHT:.+]]
+; CHECK:     [[RIGHT_END]]:
+; CHECK:       catchendpad unwind to caller
+; CHECK:     [[SHARED_CONT_RIGHT]]:
+; CHECK:       unreachable
+; CHECK:     [[SHARED_CONT_LEFT]]:
+; CHECK:       unreachable
+; CHECK:     [[INNER_RIGHT]]:
+; CHECK:       [[I_RIGHT:\%.+]] = cleanuppad []
+; CHECK:       invoke void @f()
+; CHECK:         to label %[[UNREACHABLE_RIGHT:.+]] unwind label %[[INNER_CLEANUP_RIGHT:.+]]
+; CHECK:     [[INNER_LEFT]]:
+; CHECK:       [[I_LEFT:\%.+]] = cleanuppad []
+; CHECK:       invoke void @f()
+; CHECK:         to label %[[UNREACHABLE_LEFT:.+]] unwind label %[[INNER_CLEANUP_LEFT:.+]]
+; CHECK:     [[INNER_CLEANUP_RIGHT]]:
+; CHECK:       cleanuppad []
+; CHECK:       call void @f()
+; CHECK:       unreachable
+; CHECK:     [[INNER_CLEANUP_LEFT]]:
+; CHECK:       cleanuppad []
+; CHECK:       call void @f()
+; CHECK:       unreachable
+
+

llvm/trunk/test/CodeGen/WinEH/wineh-no-demotion.ll

shared:
   %x = call i32 @g()
   invoke void @f()
           to label %shared.cont unwind label %inner
 
 shared.cont:
   unreachable
 
 inner:
-  ; CHECK: %phi = phi i32 [ %x, %right ], [ 0, %invoke.cont2 ], [ %x.for.left, %left ]
   %phi = phi i32 [ %x, %shared ], [ 0, %invoke.cont2 ]
   %i = cleanuppad []
   call void @h(i32 %phi)
   unreachable
 
+; CHECK [[INNER_INVOKE_CONT2:inner.*]]:
+  ; CHECK: call void @h(i32 0)
+
+; CHECK [[INNER_RIGHT:inner.*]]:
+  ; CHECK: call void @h(i32 %x)
+
+; CHECK [[INNER_LEFT:inner.*]]:
+  ; CHECK: call void @h(i32 %x.for.left)
+
 exit:
   unreachable
 }
 
 ; CHECK-LABEL: @test2(
 define void @test2() personality i32 (...)* @__CxxFrameHandler3 {
 entry:
   invoke void @f()
shared:
   %x = call i32 @g()
   invoke void @f()
           to label %shared.cont unwind label %inner
 
 shared.cont:
   unreachable
 
 inner:
-  ; CHECK: %x1 = phi i32 [ %x.for.left, %left ], [ %x, %right ]
-  ; CHECK: call void @h(i32 %x1)
   %i = cleanuppad []
   call void @h(i32 %x)
   unreachable
 
+; CHECK [[INNER_RIGHT:inner.*]]:
+  ; CHECK: call void @h(i32 %x)
+
+; CHECK [[INNER_LEFT:inner.*]]:
+  ; CHECK: call void @h(i32 %x.for.left)
+
 exit:
   unreachable
 }
 
 ; CHECK-LABEL: @test3(
 define void @test3() personality i32 (...)* @__CxxFrameHandler3 {
 entry:
   invoke void @f()