Page MenuHomePhabricator

[WinEH] Clone funclets with multiple parents
ClosedPublic

Authored by andrew.w.kaylor on Sep 29 2015, 3:08 PM.

Details

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.

Diff Detail

Repository
rL LLVM

Event Timeline

There are a very large number of changes, so older changes are hidden. Show Older Changes
JosephTremoulet added inline comments.Oct 1 2015, 1:48 PM
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 added inline comments.Oct 1 2015, 2:04 PM
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 edited edge metadata.Oct 1 2015, 2:17 PM

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?

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 added inline comments.Oct 2 2015, 6:03 PM
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...

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?

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.

  1. 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.

  1. 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.

  1. 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...
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 edited edge metadata.Oct 6 2015, 11:58 AM

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.

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.

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.

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).

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 edited edge metadata.

-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.

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?

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.

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.

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.

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

JosephTremoulet accepted this revision.Nov 5 2015, 12:12 PM
JosephTremoulet edited edge metadata.

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"

This revision is now accepted and ready to land.Nov 5 2015, 12:12 PM
This revision was automatically updated to reflect the committed changes.
chapuni added a subscriber: chapuni.Nov 6 2015, 2:34 AM

Reverted in r252279.

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

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?

lib/CodeGen/WinEHPrepare.cpp
856–860 ↗(On Diff #37951)

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