Thanks, Reid. These are good points. So I guess that does take us back to something more like my original proposal. I like your suggestion of having some kind of “eh.actions” intrinsic to represent the outlining rather than the extension to landingpad that I had proposed. I was just working on something like that in conjunction with my second alternative idea. What I’d really like is to have the “eh.actions” intrinsic take a shape that makes it really easy to construct the .xdata table directly from these calls. As I think I mentioned in my original post, I think I have any idea for how to reconstruct functionally correct eh states (at least for synchronous EH purposes) from the invoke and landingpad instructions. I would like to continue, as in my original proposal, limiting the unwind representations to those that are unique to a given landing pad. I think with enough documentation I can make that seem sensible. I’ll start working on a revised proposal. Let me know if you have any more solid ideas. -Andy From: Reid Kleckner [mailto:rnk at google.com] Sent: Tuesday, January 27, 2015 11:24 AM To: Kaylor, Andrew Cc: Bataev, Alexey; Reid Kleckner (reid at kleckner.net); LLVM Developers Mailing List; Anton Korobeynikov; Kreitzer, David L Subject: Re: [LLVMdev] RFC: Native Windows C++ exception handling My original reply got stuck in llvmdev moderation (it hit the 100K limit!), so I'm resending without reply context. ------- Thanks, your explanation of the .xdata tables in terms of EH states makes a lot of sense to me. I have a few concerns about your new EH proposal, though. 1. If we number the EH states in the frontend, we will have to renumber them during inlining. This isn't insurmountable, but seems like a design weakness. The major motivation for using the @llvm.eh.typeid.for intrinsic is to delay numbering the catch clauses until codegen, which is after inlining. Honestly, we should consider lowering @llvm.eh.typeid.for during EH preparation so that we can try forming a 'switch' in IR instead of a series of conditional branches. Reminds me of http://llvm.org/PR20300, which is a similar EH preparation improvement I want to do. 2. Without the invoke instruction and accompanying landing pad, the IR has a lot of implicit control flow. Without explicit control flow, we can't promote allocas to SSA values, which LLVM basically requires before any real optimization can begin. Consider this example: int x = g(); try { f(); } catch (int) { x++; // use x as input and output } return x; Today we will promote 'x' to values like this: entry: %x = call i32 @g() invoke @f() to label %ret unwind label %lpad lpad: landingpad ... ; elided EH dispatch, assume selector is for 'int' %x1 = add i32 %x, 1 br label %ret ret: %x = phi i32 [%x, %entry ], [%x1, %lpad] In your IR example, it looks like the control flow edge from 'call void @_Z14do_inner_thingv' to the catch handler code comes at the end of the function prior to the return. How would you change it if there was an assignment of a variable like 'x' before and after the call and a load of 'x' in the catch handlers? I don't think we can do correct phi insertion on the CFG as written. 3. Ultimately, the explicit state setting intrinsics will be lowered out and we will need to form the ip2state table. Unfortunately, bracketed intrinsics aren't quite enough to recover the natural scoping of the source program, which is something we've seen with @llvm.lifetime.start / end. What should the backend do if it sees control flow like this? bb0: call void @llvm.eh.setehstate(i32 0) br label %bb3 bb1: call void @llvm.eh.setehstate(i32 2) br label %bb3 bb3: invoke void @do_something() ; Which EH state are we in? We could establish IR rules that such join points need to reset the EH state, but then we have to go and teach optimizers about it. It's basically a no-IR-modifications version of labelling each BB with an unwind label, which is something that's been proposed before more directly: http://llvm.org/PR1269. Personally, I think we could make this change to LLVM IR, but at a great cost. Implicit EH control flow would open up a completely new class of bugs in LLVM optimizers that doesn't exist today. Most LLVM hackers working on optimizations that I talk to *REALLY* don't want to carry the burden of implicit control flow. However, my coworkers may be biased, because exceptions are banned in most settings here at Google. Anyway, unless we go all the way and make the EH state a first class IR construct, I feel like @llvm.eh.state imposes too many restrictions on IR transformations. What happens if I reorder the BBs? Consider that MBB placement happens very late, and is guided primarily by branch probability, not source order. -------- So, to attempt to address this, I think maybe we can go back to something like your first proposal. I continue to think that the right thing to do is to emit the Itanium-style landingpads from the frontend, and transform the control flow into something more table-like after optimizations. If we do things this way we don't have to teach the middle-end to reason about new constructs like @llvm.eh.state. I propose that the preparation pass does all the outlining and removes all the landing pad code. It will leave behind the landingpad instruction and a call to an intrinsic (@llvm.eh.actions()) that lists the handlers and handler types in the order that they need to run. To preserve the structure of the CFG, the actions intrinsic will return an i8* that will feed into an indirectbr terminator. Similar to SjLj, SSA values live across the landing pad entrances and exits will be demoted to stack allocations. Unlike SjLj, to allow access from outlined landing pad code, the stack memory will be part of the @llvm.frameallocate block. Here's how _Z4testv would look after preparation: define void @_Z4testv() #0 { entry: %frame_alloc = call i8* @llvm.frameallocate(i32 2) %capture_block = bitcast i8* %frame_alloc to %captures._Z4testv* %outer = getelementptr %captures._Z4testv* %capture_block, i32 0, i32 0 %inner = getelementptr %captures._Z4testv* %capture_block, i32 0, i32 1 invoke void @_ZN5OuterC1Ev(%struct.Outer* %outer) to label %invoke.cont unwind label %lpad invoke.cont: ; preds = %entry invoke void @_ZN5InnerC1Ev(%struct.Inner* %inner) to label %invoke.cont2 unwind label %lpad1 invoke.cont2: ; preds = %invoke.cont invoke void @_Z14do_inner_thingv() to label %invoke.cont4 unwind label %lpad3 invoke.cont4: ; preds = %invoke.cont2 invoke void @_ZN5InnerD1Ev(%struct.Inner* %inner) to label %try.cont unwind label %lpad1 try.cont: ; preds = %invoke.cont4, %invoke.cont8 invoke void @_ZN5OuterD1Ev(%struct.Outer* %outer) to label %try.cont19 unwind label %lpad try.cont19: ; preds = %try.cont, %invoke.cont17 call void @_Z10keep_goingv() ret void lpad: ; preds = %try.cont, %entry %0 = landingpad { i8*, i32 } personality i8* bitcast (i32 (...)* @__gxx_personality_v0 to i8*) catch i8* bitcast (i8** @_ZTIf to i8*) %recover = call i8* (...)* @llvm.eh.actions( i32 1, i8* bitcast (i8** @_ZTIf to i8*), void (i8*, i8*)* @catch_float) indirectbr i8* %recover, [label %try.cont], [label %try.cont19] lpad1: ; preds = %invoke.cont4, %invoke.cont %3 = landingpad { i8*, i32 } personality i8* bitcast (i32 (...)* @__gxx_personality_v0 to i8*) cleanup catch i8* bitcast (i8** @_ZTIi to i8*) catch i8* bitcast (i8** @_ZTIf to i8*) %recover1 = call i8* (...)* @llvm.eh.actions( i32 1, i8* bitcast (i8** @_ZTIi to i8*), void (i8*, i8*)* @catch_int, i32 0, i8* null, void (i8*, i8*)* @dtor_outer, i32 2, i8* bitcast (i8** @_ZTIf to i8*), void (i8*, i8*)* @catch_float) indirectbr i8* %recover1, [label %try.cont], [label %try.cont19] lpad3: ; preds = %invoke.cont2 %6 = landingpad { i8*, i32 } personality i8* bitcast (i32 (...)* @__gxx_personality_v0 to i8*) cleanup catch i8* bitcast (i8** @_ZTIi to i8*) catch i8* bitcast (i8** @_ZTIf to i8*) %recover2 = call i8* (...)* @llvm.eh.actions( i32 0, i8* null, void (i8*, i8*)* @dtor_inner, i32 1, i8* bitcast (i8** @_ZTIi to i8*), void (i8*, i8*)* @catch_int, i32 0, i8* null, void (i8*, i8*)* @dtor_outer, i32 2, i8* bitcast (i8** @_ZTIf to i8*), void (i8*, i8*)* @catch_float) indirectbr i8* %recover2, [label %try.cont], [label %try.cont19] } One issue is that I'm not sure how to catch a "float" exception thrown by handle_int(). I'll have to think about that. It's also not clear to me that we need to have the i32 selector in @llvm.eh.actions. We need a way to distinguish between catch-all (traditionally i8* null) and a cleanup. We could just use some other constant like 'i8* inttoptr (i32 1 to i8*)' and make that the cleanup sentinel. I think there are still issues here, like how to actually implement this transform, but I'm going to hit send now and keep thinking. :) -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20150127/1a3da6b5/attachment.html>
On Tue, Jan 27, 2015 at 12:58 PM, Kaylor, Andrew <andrew.kaylor at intel.com> wrote:> Thanks, Reid. These are good points. > > > > So I guess that does take us back to something more like my original > proposal. > > > > I like your suggestion of having some kind of “eh.actions” intrinsic to > represent the outlining rather than the extension to landingpad that I had > proposed. I was just working on something like that in conjunction with my > second alternative idea. >Great!> What I’d really like is to have the “eh.actions” intrinsic take a shape > that makes it really easy to construct the .xdata table directly from these > calls. As I think I mentioned in my original post, I think I have any idea > for how to reconstruct functionally correct eh states (at least for > synchronous EH purposes) from the invoke and landingpad instructions. I > would like to continue, as in my original proposal, limiting the unwind > representations to those that are unique to a given landing pad. I think > with enough documentation I can make that seem sensible. >My thinking is that the "eh.actions" list can be transformed into a compact xdata table later, after we've done machine basic block layout. I think the algorithm will be something like 1. Input: already laid out MachineFunction 2. Call EHStreamer::computeCallSiteTable to populate a LandingPadInfo vector sorted by ascending PC values 4. Iterate the LandingPadInfos, comparing the action list of each landing pad with the previous landing pad, assuming an empty action list at function start and end. 5. Model the action list as a stack, and compute the common suffix of the landing pad action lists 6. Each new action pushed represents a new EH state number 7. Pushing a cleanup action adds a state table entry that transitions from the current EH state to the previous with a cleanup handler 8. Pushing a catch action adds a new unwind table entry with an open range from the current EH state to an unknown EH state. The state after catching is... ??? 9. Popping a catch action closes an open unwind table range So, I think the action list is at least not totally crazy. =) I’ll start working on a revised proposal. Let me know if you have any more> solid ideas. >-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20150127/4809fa20/attachment.html>
Hi Reid, I’ve worked through a few scenarios, and I think this is converging. I’m attaching a new example, which extends the one we’ve been working through to handle a few more cases. I wasn’t sure what you intended the first i32 argument in an llvm.eh.actions entry to be. I’ve been using it as a place to store the eh state that I’m associating with the action, but that’s kind of circular because I’m using the information in these tables to calculate that value. I’ll be able to do this calculation in the MSVCEHPrepare pass before these instructions are added, so I can put it there (it’s nice for readability), but the later pass that generates the tables (assuming we leave that in a later pass) will need information not represented in the action table (at least as I’ve been using it). I’m not 100% sure that this is necessary, but it seemed like the way things ought to be. I’ll experiment more before anything gets set in stone. In addition to the IP-to-state table that we’ve talked about, we also need an unwind table (which has each state, the state it transitions to when it expires and the unwind handler, if any) and a catch handler table (which has the range of states that can throw to the handlers, the state of the handlers and a map of types handled to their handlers). I’ve got examples of these in the attached example. So I now have a firm plan for how to compute these tables from the outlined IR. I think the algorithm you proposed for computing eh states doesn’t quite work. In particular, if multiple catch handlers get added by the same landing pad we’ll want to start by assuming that they have the same state. If they end up getting popped at different times then we’ll need to update the eh state of the one that gets popped first. Unfortunately my example doesn’t cover this case, but I worked through it and my new algorithm (based on your but slightly tweaked) works for that case. Also, unwind handlers get discrete states (they happen when a transition crosses the state, but in the .xdata tables they are represented with a single state). Catch handlers, on the other hand, do get a range. Anyway, here’s what I’m doing (by hand so far, I don’t have it coded yet). 1. Start with an empty stack of actions and an empty master list of eh state. 2. Visit each landing pad in succession, processing the actions at that landing pad back to front. 3. Pop actions from the current stack that aren’t in the current landing pad’s action table a. If a catch is popped that had been assumed to have the same state as a catch that isn’t being popped its state number and all state numbers above it need to be incremented b. When a catch is popped, the next available eh_state is assigned to its handler 4. As an action is pushed to the current stack, it is assigned an eh_state in the master list a. If the action was an unwind or if it was a cacth after an unwind, the next available eh_state is incremented b. If the action was a catch following a catch that was also just added, it gets the same eh_state as the previous catch 5. When all landing pads have been handled, the remaining actions are popped and processed as above. The “next” state for each eh_state can also be computed during the above process by observing the state of the action on the top of the current action stack when the action associated with the state is popped. In the case of catch handlers, I think the next state will always be the same as the next state of the corresponding catch action. So, I think it makes sense to compute the unwind and catch tables during the MSVCEHPrepare pass, but I wasn’t sure how best to preserve the information once it was computed. Is it reasonable to stick this in metadata? We can keep fine tuning this if you like, but I think it’s looking solid enough that I’m going to start revising my outlining patch to produce the results in the attached example. -Andy From: Reid Kleckner [mailto:rnk at google.com] Sent: Tuesday, January 27, 2015 1:55 PM To: Kaylor, Andrew Cc: Bataev, Alexey; Reid Kleckner (reid at kleckner.net); LLVM Developers Mailing List; Anton Korobeynikov; Kreitzer, David L Subject: Re: [LLVMdev] RFC: Native Windows C++ exception handling On Tue, Jan 27, 2015 at 12:58 PM, Kaylor, Andrew <andrew.kaylor at intel.com<mailto:andrew.kaylor at intel.com>> wrote: Thanks, Reid. These are good points. So I guess that does take us back to something more like my original proposal. I like your suggestion of having some kind of “eh.actions” intrinsic to represent the outlining rather than the extension to landingpad that I had proposed. I was just working on something like that in conjunction with my second alternative idea. Great! What I’d really like is to have the “eh.actions” intrinsic take a shape that makes it really easy to construct the .xdata table directly from these calls. As I think I mentioned in my original post, I think I have any idea for how to reconstruct functionally correct eh states (at least for synchronous EH purposes) from the invoke and landingpad instructions. I would like to continue, as in my original proposal, limiting the unwind representations to those that are unique to a given landing pad. I think with enough documentation I can make that seem sensible. My thinking is that the "eh.actions" list can be transformed into a compact xdata table later, after we've done machine basic block layout. I think the algorithm will be something like 1. Input: already laid out MachineFunction 2. Call EHStreamer::computeCallSiteTable to populate a LandingPadInfo vector sorted by ascending PC values 4. Iterate the LandingPadInfos, comparing the action list of each landing pad with the previous landing pad, assuming an empty action list at function start and end. 5. Model the action list as a stack, and compute the common suffix of the landing pad action lists 6. Each new action pushed represents a new EH state number 7. Pushing a cleanup action adds a state table entry that transitions from the current EH state to the previous with a cleanup handler 8. Pushing a catch action adds a new unwind table entry with an open range from the current EH state to an unknown EH state. The state after catching is... ??? 9. Popping a catch action closes an open unwind table range So, I think the action list is at least not totally crazy. =) I’ll start working on a revised proposal. Let me know if you have any more solid ideas. -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20150129/dddf8797/attachment.html> -------------- next part -------------- A non-text attachment was scrubbed... Name: nested-2.ll Type: application/octet-stream Size: 19583 bytes Desc: nested-2.ll URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20150129/dddf8797/attachment.obj>