Page MenuHomePhabricator

[IR] Reformulate LLVM's EH funclet IR
ClosedPublic

Authored by majnemer on Dec 1 2015, 11:25 PM.

Details

Summary

While we have successfully implemented a funclet-oriented EH scheme on
top of LLVM IR, our scheme has some notable deficiencies:

  • catchendpad and cleanupendpad are necessary in the current design but they are difficult to explain to others, even to seasoned LLVM experts.
  • catchendpad and cleanupendpad are optimization barriers. They cannot be split and force all potentially throwing call-sites to be invokes. This has a noticable effect on the quality of our code generation.
  • catchpad, while similar in some aspects to invoke, is fairly awkward. It is unsplittable, starts a funclet, and has control flow to other funclets.
  • The nesting relationship between funclets is currently a property of control flow edges. Because of this, we are forced to carefully analyze the flow graph to see if there might potentially exist illegal nesting among funclets. While we have logic to clone funclets when they are illegally nested, it would be nicer if we had a representation which forbade them upfront.

Let's clean this up a bit by doing the following:

  • Instead, make catchpad more like cleanuppad and landingpad: no control flow, just a bunch of simple operands; catchpad would be splittable.
  • Introduce catchswitch, a control flow instruction designed to model the constraints of funclet oriented EH.
  • Make funclet scoping explicit by having funclet instructions consume the token produced by the funclet which contains them.
  • Remove catchendpad and cleanupendpad. Their presence can be inferred implicitly using coloring information.

N.B. The state numbering code for the CLR has been updated but the
veracity of it's output cannot be spoken for. An expert should take a
look to make sure the results are reasonable.

Diff Detail

Repository
rL LLVM

Event Timeline

There are a very large number of changes, so older changes are hidden. Show Older Changes
lib/AsmParser/LLParser.cpp
5189–5190 ↗(On Diff #41832)

I'm happy with "unwind label %foo" as the preferred and documented syntax. I was only suggesting that the parser tolerate the presence of a 'to' token here. I suppose that's too imprecise for the philosophy of the IR. I can live with that. The number of people who would ever care is likely to be less than five and may only be one.

rnk added inline comments.Dec 4 2015, 11:08 AM
lib/CodeGen/WinEHPrepare.cpp
180–184 ↗(On Diff #41832)

It sounds like it's OK if C++ and the CLR number these slightly differently:

void f() {
  try {
    g(0); // state 0
    try {
      g(1); // state 1
    } catch( ...) {
      // C++ needs to be in TryHigh+1 to CatchHigh interval
      g(2); // CLR state 0, C++ state 2
    }
  } catch(...) {
  }
}

You actually want to assign the outer state of 0 to the g(2) call site, and the table emitter will do the work of emitting duplicate clauses on the handler.

In that case, I think you can avoid filling in FuncletBaseStateMap, always use BaseState = NullState, and things will work.

JosephTremoulet added inline comments.Dec 6 2015, 5:10 PM
lib/CodeGen/WinEHPrepare.cpp
86 ↗(On Diff #41832)

IIUC the DenseMap will require a contiguous allocation sized like the number of BasicBlocks

Um, sorry, clearly I didn't understand correctly. For one, I meant the MapVector, not the DenseMap, and for two, its vector would be sized like the number of funclets, not the number of blocks. So that's no different footprint-wise than the explicit EntryBlocks vector, and to boot is easier to read and maintain. So, disregard this comment, sorry for the noise.

(and, separately, IIUC now, the DenseMap does indeed fit all its entries in a contiguous allocation, but I'm less concerned with that since the API surface is the same and we can always switch it back to std::map if it makes something blow up [or have DenseMap degrade gracefully or etc])

andrew.w.kaylor added inline comments.Dec 7 2015, 1:11 PM
lib/CodeGen/WinEHPrepare.cpp
169 ↗(On Diff #41832)

Am I right in thinking that you could assert(FuncletPad || FuncletEntryBB == &Fn->getEntryBlock()) here?

215 ↗(On Diff #41832)

This code could really use some comments. I had to build it and step through some examples in the debugger to understand how it works. It would be nice to have a single large comment block somewhere explaining the whole process of state numbering for a C++ function in addition to a few remarks sprinkled throughout this function.

219 ↗(On Diff #41832)

s/no/not

243 ↗(On Diff #41832)

This assigns the same base state to all catchpads within a catchswitch. That seems sketchy to me. Consider the following example:

void foo() {
  try {
    f(1);
  } catch (int) {
    f(2);
    try {
      f(3);
    } catch (...) { }
  } catch (...) {
    f(4);
    try {
      f(5);
    } catch (...) {}
  }
}

Because both outer-level catches get the same base state (1), this state will be assigned to both f(2) and f(4). I think it's possible that __CxxFrameHandler3 will correctly deal with the same state appearing in two different funclets, but I'm not confident of that.

261 ↗(On Diff #41832)

With the new implementation, I don't think it is possible to get here twice for the same cleanup pad. So this could be made an assertion, right?

lib/IR/Verifier.cpp
3011 ↗(On Diff #41832)

Shouldn't this be verifying the unwind destination?

3022 ↗(On Diff #41832)

This should also exclude CatchPadInst.

3048 ↗(On Diff #41832)

This should also exclude CatchPadInst.

andrew.w.kaylor added inline comments.Dec 7 2015, 5:08 PM
lib/Transforms/Utils/InlineFunction.cpp
371 ↗(On Diff #41832)

This needs an RAUW for the catchswitch case.

andrew.w.kaylor added inline comments.Dec 8 2015, 4:18 PM
lib/Transforms/Utils/SimplifyCFG.cpp
3276 ↗(On Diff #41832)

Can a cleanupret ever unwind to a catchpad? If not, this should be CleanupPadInst.

3284 ↗(On Diff #41832)

Can you explain to me the scenario where we can't remove the empty cleanup pad?

I would have expected that for any legal IR there would be something we could do to remove the cleanup pad.

test/CodeGen/WinEH/wineh-cloning.ll
276 ↗(On Diff #41832)

Here, on the other hand, I don't think we need to generalize, since this block won't be cloned.

281 ↗(On Diff #41832)

Is there any reason to keep this test case? There doesn't seem to be anything interesting happening here.

326 ↗(On Diff #41832)

This test case also seems to be redundant now.

383 ↗(On Diff #41832)

It bothers me that this is still apparently legal. I would think that an exception thrown from within a top level EH pad should only be able to unwind to caller. In any event, the test is now verifying that we did not resolve the problem that the old implementation of this test was looking for.

What would the state numbering code do with this if we left it in the state that is checked here?

479 ↗(On Diff #41832)

This comment is incorrect now, since there is no invoke in %merge anymore. I think this test case is also obsolete.

lib/Transforms/Utils/InlineFunction.cpp
1443–1451 ↗(On Diff #41832)

I think you can remove CallSiteEHPad && from each of these three tests, as it's redundant with the guarding check up on line 1434.

lib/Transforms/Utils/InlineFunction.cpp
1099 ↗(On Diff #41832)

This could be

if (CallerPersonality) {
  assert(CalledPersonality);

since the code just above sets CalledPersonality if it is null but CallerPersonality is not.

lib/Transforms/Utils/InlineFunction.cpp
1099 ↗(On Diff #41832)

...no, I just totally misread that. Sorry for the noise.

majnemer added inline comments.Dec 11 2015, 12:47 AM
docs/ExceptionHandling.rst
617–618 ↗(On Diff #41832)

Done.

632–633 ↗(On Diff #41832)

cleanupret and catchret are similar in that they both exit their constituent funclet. I'll keep it as cleanupret unless there is an overwhelming desire to move in that direction.

761 ↗(On Diff #41832)

Done.

docs/LangRef.rst
5342 ↗(On Diff #41715)

I considered this approach while designing the new instructions (i.e. making getOuterScope return nullptr if it has no lexical parent). I rejected it for a few reasons:

  • It makes it all too easy to get the nesting wrong if no token is necessary. Things will seem to work until they don't. Making the token always explicit is a way of making IR creators consider the nesting case.
  • It provides us a sentinel value which we can use when wanting to talk about scopes. nullptr is often used to indicate failure and I wanted to make sure this confusion would never occur.

Regardless, we can do this change down the road at any time.

8618–8631 ↗(On Diff #41715)

#1 is done.

With regard to #2, we will tag call-sites in funclets with bundles but this does not allow us to enforce this as a verifier rule. Tail-merging can still make invokes with conflicting/illegal unwind destinations show up in other funclets. The tagging will allow us to get rid of them in WinEHPrepare.

5368 ↗(On Diff #41832)

Done.

5430 ↗(On Diff #41832)

Done.

8579 ↗(On Diff #41832)

Done.

include/llvm/Analysis/CFG.h
92 ↗(On Diff #41832)

Done.

include/llvm/Bitcode/LLVMBitCodes.h
425 ↗(On Diff #41832)

Bitcode is supposed to be stable within reason; we are breaking compatibility because it is not sensible to add heroic logic to the auto-upgrader to make these instructions: nobody should have MSVC++ EH bitcodes around.

It is fair game for 54 to be reused because, for all intents and purposes, it has never been used except by a tiny number of people.

Operand bundles are currently under development by other folks, it would be in poor taste to renumber them under their feet.

include/llvm/IR/Instructions.h
4164 ↗(On Diff #41832)

Done.

4220 ↗(On Diff #41832)

getTargetScope and getDestinationScope make you feel like they imply the existence of CFG edges which aren't really there. I'll leave this alone unless a compelling name shows up.

lib/Analysis/CFG.cpp
21 ↗(On Diff #41832)

Done.

lib/Analysis/EHPersonalities.cpp
12 ↗(On Diff #41832)

Yes, for llvm::successors.

52–57 ↗(On Diff #41832)

Done.

54 ↗(On Diff #41832)

Done.

lib/Analysis/ScalarEvolutionExpander.cpp
102–103 ↗(On Diff #41832)

This code cannot fire if the terminatepad unwinds to caller. It is only possible to get here if we have a PHI on the terminatepad (or one of it's predecessors) and the PHI's use is dominated by the terminatepad. Such a use shouldn't exist if the terminatepad unwinds to caller.

lib/AsmParser/LLParser.cpp
2371–2372 ↗(On Diff #41832)

Done.

lib/CodeGen/AsmPrinter/WinException.cpp
799–804 ↗(On Diff #41832)

Done.

lib/CodeGen/SelectionDAG/FunctionLoweringInfo.cpp
228–234 ↗(On Diff #41832)

The PHIs in the IR are not the same as the ones we need in the machine CFG. This is because invokes have a single successor in the IR but multiple successors in the machine CFG. To disable the demotion, we would need to fix the PHIs as we build the machine CFG.

lib/CodeGen/WinEHPrepare.cpp
169 ↗(On Diff #41832)

Done.

219 ↗(On Diff #41832)

Done.

261 ↗(On Diff #41832)

It still is because two cleanuprets from the same cleanuppad can unwind to the same funclet-pad. We will then do getEHPadFromPredecessor and visit the same cleanup twice.

lib/IR/Instructions.cpp
936 ↗(On Diff #41832)

Done.

1002 ↗(On Diff #41832)

Done.

lib/IR/Verifier.cpp
401–402 ↗(On Diff #41832)

This is UB, langref is updated.

2850 ↗(On Diff #41832)

Done.

3011 ↗(On Diff #41832)

Done.

3022 ↗(On Diff #41832)

visitEHPadPredecessors should do this for us when we visit CatchPadInst.

3048 ↗(On Diff #41832)

visitEHPadPredecessors should do this for us when we visit CatchPadInst.

lib/Transforms/Utils/InlineFunction.cpp
371 ↗(On Diff #41832)

Done.

1433 ↗(On Diff #41832)

Done.

1443–1451 ↗(On Diff #41832)

Done.

lib/Transforms/Utils/SimplifyCFG.cpp
3276 ↗(On Diff #41832)

Done.

test/CodeGen/WinEH/wineh-cloning.ll
276 ↗(On Diff #41832)

Done.

281 ↗(On Diff #41832)

Done.

326 ↗(On Diff #41832)

Done.

383 ↗(On Diff #41832)

There is no problem here because funclet ancestry is explicit. It should not be necessary for us to do any cloning. It is up to the front-end to emit IR that the personality routine is capable of. However, this example is impossible to construct from the front-end.

479 ↗(On Diff #41832)

Done.

majnemer updated this revision to Diff 42509.Dec 11 2015, 12:50 AM
  • Move colorEHFunclets to EHPersonalities.h
  • Fix some first draft review comments
  • Address Andy's latest comments
  • Make the IR a little easier to read
  • Make the catchswitch syntax more like invoke
  • Address Andy's latest comments.
  • Address Joseph's review comments
  • Remove unneeded #includes
  • Address Joseph's comments
  • Don't unswitch cleanuppads, we don't know how to split invoke edges to them.
  • Don't sink into a catchswitch, it won't work.
  • Make CatchSwitchInst::handlers() return BasicBlock * intead of const Use &
  • Address review comments
rnk added inline comments.Dec 11 2015, 9:39 AM
lib/CodeGen/WinEHPrepare.cpp
223–231 ↗(On Diff #42509)

It really could. Comments fell by the wayside because we were impatiently trying to pair program something that would work.

I'm probably the person who should write them, though, so I'd rather commit this and then try to clean up the algorithm in tree.

There's other stuff to do as well. It would be good to share the EH traversal between the CLR, C++, and SEH, so this is probably going to get rewritten.

250 ↗(On Diff #42509)

This assigns the same base state to all catchpads within a catchswitch. That seems sketchy to me.

That's not actually different from how things work with catchendpad today, and I think it's consistent with what MSVC does. Here's how I read the states produced by MSVC on your example:

void f(int);
void foo() {
  try {
    f(1); // state 0
  } catch (int) {
    f(2); // state 1
    try {
      f(3); // state 2
    } catch (...) {
      // state 3
    }
  } catch (...) {
    f(4); // state 1
    try {
      f(5); // state 4
    } catch (...) {
      // state 5
    }
  }
}
// unwind map
// 0 -> -1
// 1 -> -1
// 2 -> 1
// 3 -> 1
// 4 -> 1
// 5 -> 1

Clang today computes the same table as MSVC on this example, and I'm pretty sure this patch will keep our behavior here the same.

rnk added inline comments.Dec 11 2015, 10:10 AM
lib/Transforms/Utils/SimplifyCFG.cpp
3284 ↗(On Diff #42509)

I made this change and I think I completely misunderstood what the code was trying to do. I thought it was trying to merge consecutive cleanups together, not just remove empty cleanups. We can probably revert this.

LGTM aside from:

  • two naming issues (which, since they're naming issues, are bikeshedding, and could always be changed post-commit anyway):
    • The term "outer scope" used for the "within" argument of pads seems discordant with the rest of our terminology. I'd rather refer to them as "pads" since that's what we call them everywhere else, and just need an adjective. Since the textual IR uses "within", having a good counterpart for that would work, something like getOuterPad or getEnclosingPad or getContainingPad. Since in a few places we'll need to talk about the transitive closure of it, calling it getParentPad would also work for me, so that "ancestor" will be available for the transitive case.
    • I still think it's confusing that a catchret's "outer" scope is the parent of the catchswitch. I tried a few more suggestions inline, of course you'd want to s/Scope/Pad/ in them if the previous bullet sways you.
  • one inline nit
  • the thing Andy pointed out in SimplifyCFG
include/llvm/IR/Instructions.h
4220 ↗(On Diff #41832)

I'd argue the edge is there -- you're getting the "scope" that contains the target of the CFG edge. I think getReturnedToScope could make sense, but is awkward. getScopeAtDestination? getOuterScopeOfCatchswitch? getNotExitedAncestorScope? getExitScope? getInvokeScope? getPreExceptionScope? getPreviousScope? getPriorScope?

3907 ↗(On Diff #42509)

nit: seems like the two handler_helpers should be private.

rnk edited edge metadata.Dec 11 2015, 11:11 AM

I like getParentPad best from your list of names for getOuterScope.

majnemer updated this revision to Diff 42556.Dec 11 2015, 12:42 PM
majnemer edited edge metadata.
  • Address review comments
include/llvm/IR/InstrTypes.h
1122 ↗(On Diff #42556)

(here and other constructors and Create methods) parameter should probably be renamed ParentPad as well.

lib/CodeGen/WinEHPrepare.cpp
207 ↗(On Diff #42556)

This parameter name too

lib/IR/Verifier.cpp
2994 ↗(On Diff #42556)

nit: Also these locals (this, visitCatchSwitchInst, and visitTerminatePadInst)

andrew.w.kaylor accepted this revision.Dec 11 2015, 3:53 PM
andrew.w.kaylor edited edge metadata.

Except for the irreducible loop issue, this looks good to me. I would be OK with putting off addressing that problem until some later time, as it seems like a fairly unlikely corner case, but I do think we should probably think about it.

lib/CodeGen/WinEHPrepare.cpp
223–232 ↗(On Diff #42556)

Sounds like a plan.

250 ↗(On Diff #42556)

OK, if MSVC does this also then I feel a lot better about the long term viability of doing it this way.

test/CodeGen/WinEH/wineh-cloning.ll
288–289 ↗(On Diff #42556)

The original concern was that some future optimization would innocently transform otherwise reasonable code into this form. I think the hypothetically dangerous input looked something like this:

left:
  cleanuppad within none []
  call void @h(i32 1)
  invoke void @f()
    to label %unreachable unwind label %not_right
not_right:
  cleanuppad within none []
  call void @h(i32 2)
  call void @f()
  unreachable
right:
  cleanuppad within none []
  call void @h(i32 2)
  invoke void @f()
    to label %unreachable unwind label %not_left
not_left:
  cleanuppad within none []
  call void @h(i32 1)
  call void @f()
  unreachable

So if we can get that out of the clang front end, then a reasonable optimization could transform it into this test case, and I don't see how the code generator could do anything reasonable with the form shown in this test case.

This revision is now accepted and ready to land.Dec 11 2015, 3:53 PM
majnemer added inline comments.Dec 11 2015, 6:24 PM
include/llvm/IR/InstrTypes.h
1122 ↗(On Diff #42556)

Done.

lib/CodeGen/WinEHPrepare.cpp
207 ↗(On Diff #42556)

Done.

lib/IR/Verifier.cpp
2994 ↗(On Diff #42556)

Done.

test/CodeGen/WinEH/wineh-cloning.ll
288–289 ↗(On Diff #42556)

Such a hypothetical optimization would be defeated once we add support for bundle operands in the front-end. The bundle operands will defeat tail-merging/CSE because the call-sites will look like they have different operands.

test/CodeGen/WinEH/wineh-cloning.ll
288–289 ↗(On Diff #42556)

I think this is another example of a case where we'll need the bundles tagging calls/invokes in EH pads. With that, the notion of which pad an invoke "is in" will be well-defined, and we'll be able to add a rule that it's UB to take an invoke's unwind edge if its unwind dest's parent pad isn't the parent of the pad that the invoke is in. WinEHPrep will then be able to prune the UB unwind edges, so if presented with the IR in this test (which, as David points out, couldn't be the result of optimizing your example anymore, but I think would still be legal/verifiable IR) it would see that the two invokes to @f() unwind to illegal destinations, and rewrite those as calls.

majnemer updated this revision to Diff 42619.Dec 11 2015, 7:06 PM
majnemer edited edge metadata.
  • Move colorEHFunclets to EHPersonalities.h
  • Fix some first draft review comments
  • Address Andy's latest comments
  • Make the IR a little easier to read
  • Make the catchswitch syntax more like invoke
  • Address Andy's latest comments.
  • Address Joseph's review comments
  • Remove unneeded #includes
  • Address Joseph's comments
  • Don't unswitch cleanuppads, we don't know how to split invoke edges to them.
  • Don't sink into a catchswitch, it won't work.
  • Make CatchSwitchInst::handlers() return BasicBlock * intead of const Use &
  • Address review comments
  • Address review comments
  • Address review comments.
JosephTremoulet accepted this revision.Dec 11 2015, 7:22 PM
JosephTremoulet edited edge metadata.

LGTM, no caveats.

This revision was automatically updated to reflect the committed changes.