llvm dev - Dec 2010 - [LLVMdev] Inlining and exception handling in LLVM and GCC

Hi Renato,
>> Bill's recent exception handling proposal has rules which (if I
understand
>> them right) ensure that you can always find the actions for an invoke
without
>> any trouble (the actions would be listed in a dispatch instruction that
is
>> not allowed to be moved out of the landing pad).  Thus with this
proposal too
>> there would also be no problem in teaching the inliner to do the right
thing.
>
> If I got it right, you're saying that both proposals are similar in
> that they both fix the inlining problem and both specify uniquely the
> landing pads for every invoke.
yes, they both make the inlining problem fixable because it is always possible
to find the catch info associated with an invoke (or basic block).  In fact any
proposal that has this property would do as far as fixing inlining goes.

In the case of Bill's proposal this property holds because of special rules
about what you are allowed to do with landing pads: you are not allowed to move
a dispatch instruction out of a landing pad etc.  These rules could actually
be applied to eh.selector without any IR changes providing much the same effect
without a new instruction.  However the reason for not doing this is that it
then makes some optimizations impossible, for example when you inline a call
to _Unwind_Resume through an invoke you would like to turn it into a branch to
the landing pad, but this would result in eh.selector calls that fail the rules.
It's not clear to me if the dispatch instruction has this problem too, I
need
to ask Bill about it.

In fact Bill's proposal mostly seems to be about replacing the current
explicit
sequence of comparisons that llvm-gcc uses to find which handler to run (I guess
everyone who has looked at LLVM IR with exception handling in it has seen all
the calls to eh.typeid.for, the comparisons and the branching that I'm
talking
about here) with a more compact representation that is easier to analyse.  As
such, from my point of view it doesn't really have much to do with the
inlining
issue, which is not to say it doesn't have merit on other grounds.

An interesting point is that Bill's dispatch instruction is quite analogous
to
GCC's gimple_eh_dispatch statement.  This statement represents the transfer
of
control to the appropriate catch handler for an exception region, and is at a
fairly high level of abstraction.  It takes an exception handling try region as
an argument (it can also have an "allowed exceptions" region as an
argument,
but there's no added value in discussing that).  Since the list of
associated
catches is stored in the region info, there is no need for it to explicitly
list tries and where to branch to, while Bill is obliged to put the info that
GCC stores in the region directly into his dispatch instruction.

Once GCC has finished running the inliner it runs the lower_eh_dispatch pass,
which removes all gimple_eh_dispatch statements by turning them into explicit
control flow: a sequence of comparisons and branches (exactly like the code
llvm-gcc/clang produce right now, comparing the selector value with the result
of eh.typeid.for calls).  Since my proposal doesn't change this aspect of
LLVM,
you can consider that before this pass GCC's representation is like
Bill's and
after it is like in my proposal.
> So, in view of their equivalence, I think Bill's proposal is better
> for two reasons:
>
>    1. It eases the future elimination of invoke, or at least, the
> treatment of current instruction-level exception (as in Java) in a
> cleaner way.
I don't see what is cleaner about it, except that it is overall at a higher
level of abstraction (see above).
>    2. It reinforces the idea of having one personality function for
> each EH table (ie. per function), especially when inlining code from
> different paradigms (if that's possible).
According to Bill's proposal each dispatch instruction can specify a
different
personality function, so it's just the same as my proposal in this respect.
>
> However, your proposal is better in two other accounts:
>
>    1. If we do want to support EH tables with multiple personalities in
> the future.
As mentioned above, Bill's proposal also supports multiple personalities per
function.
>    2. It's less invasive and closer to the problem it meant to fix in
> the first place. So it'll be faster and easier to do that way.
>
>
> It's more of a design decision, IMO.
Exactly, and this brings up the question of what criteria should be used to
decide which proposal is best.  Presumably, all else being equal, whichever
one makes it easiest to optimize the IR.  I didn't yet think about the
advantages and disadvantages of each proposal in this respect.

Ciao, Duncan.

Hi Duncan,

I see the similarities with GCC and Bill's proposal, makes sense.


On 7 December 2010 20:20, Duncan Sands <baldrick at free.fr>
wrote:
>>   1. It eases the future elimination of invoke, or at least, the
>> treatment of current instruction-level exception (as in Java) in a
>> cleaner way.
>
> I don't see what is cleaner about it, except that it is overall at a
higher
> level of abstraction (see above).
If I got it right, his proposal had the unwind path in the basic block
(rather than in the invoke), so any instructions in that basic block
(including simple calls, without the nounwind attribute) would use
that as the landing pad.

That would make invokes obsolete.

>>   2. It reinforces the idea of having one personality function for
>> each EH table (ie. per function), especially when inlining code from
>> different paradigms (if that's possible).
>
> According to Bill's proposal each dispatch instruction can specify a
> different
> personality function, so it's just the same as my proposal in this
respect.
I confess that I didn't read all the emails in all threads, so I have
gotten some things wrong. I thought there could be only one dispatch
per function, but now that you mentioned, it doesn't really make
sense.

cheers,
--renato

Hi Renato,
>>>    1. It eases the future elimination of invoke, or at least, the
>>> treatment of current instruction-level exception (as in Java) in a
>>> cleaner way.
>>
>> I don't see what is cleaner about it, except that it is overall at
a higher
>> level of abstraction (see above).
>
> If I got it right, his proposal had the unwind path in the basic block
> (rather than in the invoke), so any instructions in that basic block
> (including simple calls, without the nounwind attribute) would use
> that as the landing pad.
>
> That would make invokes obsolete.
I think you took my proposal too literally :)  It's irrelevant to the idea
of it
whether catch info is attached to an invoke or to a basic block.  I showed it
attached to invokes to make the proposal more concrete.  If we are going to
change the IR then we should try to change it in such a way that we don't
have
to change it again when we remove the invoke instruction.  This means that if I
start coding my proposal then almost certainly I will attach the info to basic
blocks.  In fact it makes sense to do so even before we remove the invoke
instruction: in the short term we would still have invoke, but the catch info
for the invoke would be attached to the basic block containing the invoke,
which is equivalent to attaching it to the invoke.  One day we will remove
invoke, and the info will already be in the right spot (on the basic block).

Ciao, Duncan.

On Dec 7, 2010, at 12:20 PM, Duncan Sands wrote:
> In the case of Bill's proposal this property holds because of special
rules
> about what you are allowed to do with landing pads: you are not allowed to
move
> a dispatch instruction out of a landing pad etc.
I hope I didn't misstate this, but you can move it out of a landing pad,
however the landing pad must dominate the dispatch. For instance, code like
this:

lpad: landingpad
  call void @a_cleanup_function()
  dispatch …

may inline the @a_cleanup_function() call, which may result in the dispatch no
longer being in the landing pad.
> These rules could actually
> be applied to eh.selector without any IR changes providing much the same
effect
> without a new instruction.  However the reason for not doing this is that
it
> then makes some optimizations impossible, for example when you inline a
call
> to _Unwind_Resume through an invoke you would like to turn it into a branch
to
> the landing pad, but this would result in eh.selector calls that fail the
rules.
> It's not clear to me if the dispatch instruction has this problem too,
I need
> to ask Bill about it.
> 
> In fact Bill's proposal mostly seems to be about replacing the current
explicit
> sequence of comparisons that llvm-gcc uses to find which handler to run (I
guess
> everyone who has looked at LLVM IR with exception handling in it has seen
all
> the calls to eh.typeid.for, the comparisons and the branching that I'm
talking
> about here) with a more compact representation that is easier to analyse. 
As
> such, from my point of view it doesn't really have much to do with the
inlining
> issue, which is not to say it doesn't have merit on other grounds.
The compactness of information and ease of analysis are what I think of as the
key advantages of my proposal. Also, it doesn't rely upon intrinsics, but
builds the EH into the IR explicitly.
> An interesting point is that Bill's dispatch instruction is quite
analogous to
> GCC's gimple_eh_dispatch statement.  This statement represents the
transfer of
> control to the appropriate catch handler for an exception region, and is at
a
> fairly high level of abstraction.  It takes an exception handling try
region as
> an argument (it can also have an "allowed exceptions" region as
an argument,
> but there's no added value in discussing that).  Since the list of
associated
> catches is stored in the region info, there is no need for it to explicitly
> list tries and where to branch to, while Bill is obliged to put the info
that
> GCC stores in the region directly into his dispatch instruction.
> 
> Once GCC has finished running the inliner it runs the lower_eh_dispatch
pass,
> which removes all gimple_eh_dispatch statements by turning them into
explicit
> control flow: a sequence of comparisons and branches (exactly like the code
> llvm-gcc/clang produce right now, comparing the selector value with the
result
> of eh.typeid.for calls).  Since my proposal doesn't change this aspect
of LLVM,
> you can consider that before this pass GCC's representation is like
Bill's and
> after it is like in my proposal.
Interesting. . . How do they handle LTO with exception handling if the
gimple_eh_dispatch statements are all ready lowered?
>> So, in view of their equivalence, I think Bill's proposal is better
>> for two reasons:
>> 
>>   1. It eases the future elimination of invoke, or at least, the
>> treatment of current instruction-level exception (as in Java) in a
>> cleaner way.
> 
> I don't see what is cleaner about it, except that it is overall at a
higher
> level of abstraction (see above).
I also think that both of our proposals are flexible enough to handle the future
elimination of invokes and support of basic block throws (as you explained in a
future email).
>>   2. It reinforces the idea of having one personality function for
>> each EH table (ie. per function), especially when inlining code from
>> different paradigms (if that's possible).
> 
> According to Bill's proposal each dispatch instruction can specify a
different
> personality function, so it's just the same as my proposal in this
respect.
Yeah. Multiple personality functions per function is something Chris has a mild
interest in. The devil is in the details, of course.
>> However, your proposal is better in two other accounts:
>> 
>>   1. If we do want to support EH tables with multiple personalities in
>> the future.
> 
> As mentioned above, Bill's proposal also supports multiple
personalities per
> function.
> 
>>   2. It's less invasive and closer to the problem it meant to fix
in
>> the first place. So it'll be faster and easier to do that way.
>> 
>> 
>> It's more of a design decision, IMO.
> 
> Exactly, and this brings up the question of what criteria should be used to
> decide which proposal is best.  Presumably, all else being equal, whichever
> one makes it easiest to optimize the IR.  I didn't yet think about the
> advantages and disadvantages of each proposal in this respect.

I have my own opinions, of course. But I think there are two criteria which
should be met:

1. Firstly, it must work and work well. I.e., it will solve all of our current
EH problems – it's slow, it doesn't follow any ABI, it's fragile, it
requires expensive transformations before code-gen – and

2. It must be flexible enough for future changes.

Here are some of the things I would like to have:

1. Limited use of intrinsics.
   Reasoning: Intrinsics are indistinguishable from calls. And as such are
harder to work with than IR instructions.

2. EH metadata shouldn't be encoded in the CFG if at all possible.
   Reasoning: The IR is meant for executable instructions. As such,
transformations don't know about or care about any EH metadata there.

3. The front-ends should be able to emit the EH data easily.
   Reasoning: The front-end guys are just down the hall from me and I sit with
my back to the door. :-)

-bw

-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20101213/385d8a19/attachment.html>