llvm dev - May 2015 - [LLVMdev] RFC: New EH representation for MSVC compatibility

On Mon, May 18, 2015 at 8:40 PM, Joseph Tremoulet <jotrem at
microsoft.com>
wrote:
>  > I want to have separate normal and exceptional codepaths
>
> I assume you at least mean that's what you'll be doing in
Clang's initial
> IR generation.  Do you also mean to impose this as a restriction on other
> IR generators, and as a property that IR transformations must preserve?
> I.e., is this something that EH preparation can assume?
>
EH preparation should not assume that each basic block lives in exactly one
funclet. People seem to get really upset when I suggest that we change the
language rules to maintain that invariant. :-)

Instead, the EH preparation pass is responsible for establishing that
invariant by duplicating blocks, but it should be *way* easier with real
basic block terminator instructions to mark handler transitions.
> For __finally, we outline the finally body early in clang and emit two
> calls to it as before, but passing in the frameaddress as an argument
>
> But then you have to frameescape any __finally-referenced local before
> optimization, and doesn't that defeat the purpose of delaying funclet
> outlining to EH preparation?
>
True. I'm not committed to this approach, I just want to preserve
functionality until we implement the de-commoning part of EH preparation,
which I figured we could do later, since it's one of the more obscure
corner cases.

Also, __finally is pretty rare, so it's not too crazy to teach the inliner
how to undo framerecover and let the optimization fall out that way.

> > tail merging could kick in like you mention. Undoing this would be and
> currently is the job of WinEHPrepare. I guess I felt like the extra
> representational complexity wasn't worth the confidence that it would
buy us
>
> For one, it seems counterproductive to let tail merge think it can kick in
> when it's doomed to be undone.
>
I'm only saying that the tail merging is legal, and not that it is
desirable. We can teach simplifycfg that tail merging 'resume'
instructions
is a waste of time, for example.

>  For another, if we're talking about a setup where EH paths might
mingle
> with non-EH paths but the funclet will only be invoked for the EH cases,
> then I believe this would help the  "pruning as many unreachable CFG
> edges as possible " step be more effective -- after finding out which
> blocks are reachable from a catch/cleanup, you could intersect that with
> the set of blocks from which a corresponding resume can be reached.  Any
> funclet blocks ending in condbr/switch that only wind up with one successor
> in the funclet could then have their terminators rewritten as unconditional
> branches, without needing to recover dataflow and chase constants through
> phis and resolve compares/switches and all that.
>
For discussion purposes, let's imagine that 'resume' takes a
'from' label
which must be an EH block (it starts with one of these new instructions).
The nice thing about using a label here is that, unlike most SSA values,
labels cannot be phi'd. Now tail merging will have to give up or insert an
i1 ph and a conditional branch on the resume instruction, which
realistically it won't since it's not a clear win.

Originally, I was thinking that this extra funclet cloning precision wasn't
worth it, because we'd arrange the frontend and optimizers to make it
unlikely, but I'm coming around to it. It mirrors the EH pointer value
required by Itanium EH.

> > I'm not married to reusing 'resume', other candidate names
include
> 'unwind' and 'continue', and I'd like more ideas
>
> The first thing that comes to mind is 'endatch/exitcatch', but to
use that
> you'd need to rename other things since it would be confusing vis-à-vis
> catchendblock and lack symmetry with catchblock that isn't prefixed
with
> begin/enter.
>
> You could consider 'filter' (or 'filterblock') for
'catchblock', since
> conceptually it plays the role of a filter (typically one which consults
> type information; I've seen such things called
"typetestfilter" before).
> Or
'dispatch'/'dispatchblock'/'exceptiondispatch'/'dispatchexception'
> (isn't that what Clang names the blocks it creates for the explicit
> dispatch code?); 'catchendblock' would then be something like
> 'unwinddispatch' or 'continuedispatch' or
'resumedispatch' and the resume
> that returns to normal execution could be 'exitdispatch' or
'exitcatch' or
> even 'uncatch'.
>
> For the resumes that end cleanups, something like 'endcleanup'
might work.
>
> Names are hard…
>
'dispatch' might work for the instruction which transitions from a
cleanup
to the next EH block. :) I don't really see how to work filter in,
especially since we've already used it for landingpad filters, which exist
to support exception specifications.

Chatting around the office, we came up with 'recover' and
'unwind' for
ending catch and cleanup blocks respectively.

A 'recover' instruction would end a catch block, and would target the
block
where the exception is over. This instruction would modify memory, because
it destroys the exception object.

An 'unwind' instruction would end a cleanup block, and would target the
next action. I like this because I talk a lot about "unwind edges" in
the
CFG, and a cleanup finishing feels like an unwind edge. I could also see
'dispatch' here.

Some possible new syntax:

recover from label %maycatch.int to label %endcatchbb
unwind from label %cleanup.obj to label %nextaction
unwind from label %cleanup.obj    ; unwinds out of the function, hook it up
to the unwind edge of an inlined call site

For Itanium, tail merging is profitable and doable with phis, so we might
want to do this instead:

recover to label %endcatchbb
unwind i8* %ehptr to label %nextaction
unwind i8* %ehptr    ; unwinds out of the function, hook it up to the
unwind edge of an inlined call site

Itanium requires threading the active exception pointer through to the next
action or _Unwind_Resume, so it passes along an SSA value. MSVC needs this
weird kind of control dependence instead. We could drop the 'from' token
as
unnecessary, but I want to make it easier to reason about the textual
representation.
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20150519/abf5e16d/attachment.html>

> teach the inliner how to undo framerecover and let the optimization fall
out that way
You'd still have the problem that the referenced variables were frameescaped
and appear to be read/written at unrelated calls.
> __finally is pretty rare
`__finally` may be rare in SEH code, but `finally` is quite common in .Net code,
so we're going to need a solution that avoids early `finally` outlining for
the same reasons we're avoiding early `catch` outlining.
While we do need something that's amenable to duplicating `finally` code on
hot/non-EH paths (since this is an important optimization for .Net code), I
think there also needs to be a path that can be taken for very cold code / very
large cleanups / very deeply-nested cleanups to avoid quadratic code expansion
on those cases.  Early outlining of just those cases could maybe be made to
work, but would require that the decision be made early; it would be much more
palatable to make the decision in the natural course of optimization (e.g. some
sort of tail duplication).
So I think we should have a way to enter/exit cleanup blocks on non-EH paths.
The smallest change to your proposal that comes to mind which would allow this
would be:
   - a normal branch can target a cleanupblock
   - the resume/unwind terminator that ends a cleanup would have another
optional target label (%normalsucc).  The semantics would be that the EH edge to
%nextaction would be taken if the cleanupblock were entered by an EH edge, and
the normal edge to %normalsucc would be taken otherwise.
   - converting this to landingpads would manifest an i1 that would need to be
set before branching to the cleanupblock, and turn the unwind/resume into a
condbr on that
   - codegen for windows could turn the branch to cleanupblock into a call to
the handler followed by a jump to the %normalsucc
A change that I'd consider preferable since it avoids the need for an
auxiliary switch in the non-EH code would be:
    - some new terminator along the lines of 'entercleanup %cleanupblock
recover to %recoverblock', rather than a plain branch, can target
cleanupblocks
    - the resume/unwind terminator that ends a cleanup would have any number of
additional successors, and just like the rule that the EH target must match the
%nextaction referenced on the cleanupblock, the non-EH targets would need to
match one of the %recoverblocks specified on one of the entercleanups targeting
the cleanupblock
    - converting this to landingpads would manifest an int that would need to be
set before branching to the cleanupblock, and turn the unwind/resume into a
switch
    - codegen for windows could turn entercleanup into a call to the handler
followed by a jump to the %recoverblock
Those are the first two options that come to mind, anyway.  I'm sure there
are other options, but the key points are:
1) can avoid early outlining of finally bodies, and
2) can avoid runaway code expansions

Regarding naming, I like your new suggestions (though the changes I'm
suggesting to cleanup-ending terminators are a mix between recover and unwind…
FWIW, 'endfinally' would be a natural name for that in my world ☺. 
Personally I wouldn't hate something verbose like recover_or_unwind for the
forms that may be doing either.  'endcleanup' also comes to mind.).

Thanks
-Joseph


From: Reid Kleckner [mailto:rnk at google.com]
Sent: Tuesday, May 19, 2015 3:40 PM
To: Joseph Tremoulet
Cc: LLVM Developers Mailing List; Bill Wendling; Nick Lewycky; Kaylor, Andrew
Subject: Re: [LLVMdev] RFC: New EH representation for MSVC compatibility

On Mon, May 18, 2015 at 8:40 PM, Joseph Tremoulet <jotrem at
microsoft.com<mailto:jotrem at microsoft.com>>
wrote:
> I want to have separate normal and exceptional codepaths
I assume you at least mean that's what you'll be doing in Clang's
initial IR generation.  Do you also mean to impose this as a restriction on
other IR generators, and as a property that IR transformations must preserve? 
I.e., is this something that EH preparation can assume?

EH preparation should not assume that each basic block lives in exactly one
funclet. People seem to get really upset when I suggest that we change the
language rules to maintain that invariant. :-)

Instead, the EH preparation pass is responsible for establishing that invariant
by duplicating blocks, but it should be *way* easier with real basic block
terminator instructions to mark handler transitions.
> For __finally, we outline the finally body early in clang and emit two
calls to it as before, but passing in the frameaddress as an argument
But then you have to frameescape any __finally-referenced local before
optimization, and doesn't that defeat the purpose of delaying funclet
outlining to EH preparation?

True. I'm not committed to this approach, I just want to preserve
functionality until we implement the de-commoning part of EH preparation, which
I figured we could do later, since it's one of the more obscure corner
cases.

Also, __finally is pretty rare, so it's not too crazy to teach the inliner
how to undo framerecover and let the optimization fall out that way.
> tail merging could kick in like you mention. Undoing this would be and
currently is the job of WinEHPrepare. I guess I felt like the extra
representational complexity wasn't worth the confidence that it would buy us
For one, it seems counterproductive to let tail merge think it can kick in when
it's doomed to be undone.

I'm only saying that the tail merging is legal, and not that it is
desirable. We can teach simplifycfg that tail merging 'resume'
instructions is a waste of time, for example.

For another, if we're talking about a setup where EH paths might mingle with
non-EH paths but the funclet will only be invoked for the EH cases, then I
believe this would help the  "pruning as many unreachable CFG edges as
possible " step be more effective -- after finding out which blocks are
reachable from a catch/cleanup, you could intersect that with the set of blocks
from which a corresponding resume can be reached.  Any funclet blocks ending in
condbr/switch that only wind up with one successor in the funclet could then
have their terminators rewritten as unconditional branches, without needing to
recover dataflow and chase constants through phis and resolve compares/switches
and all that.

For discussion purposes, let's imagine that 'resume' takes a
'from' label which must be an EH block (it starts with one of these new
instructions). The nice thing about using a label here is that, unlike most SSA
values, labels cannot be phi'd. Now tail merging will have to give up or
insert an i1 ph and a conditional branch on the resume instruction, which
realistically it won't since it's not a clear win.

Originally, I was thinking that this extra funclet cloning precision wasn't
worth it, because we'd arrange the frontend and optimizers to make it
unlikely, but I'm coming around to it. It mirrors the EH pointer value
required by Itanium EH.
> I'm not married to reusing 'resume', other candidate names
include 'unwind' and 'continue', and I'd like more ideas
The first thing that comes to mind is 'endatch/exitcatch', but to use
that you'd need to rename other things since it would be confusing vis-à-vis
catchendblock and lack symmetry with catchblock that isn't prefixed with
begin/enter.
You could consider 'filter' (or 'filterblock') for
'catchblock', since conceptually it plays the role of a filter
(typically one which consults type information; I've seen such things called
"typetestfilter" before).  Or
'dispatch'/'dispatchblock'/'exceptiondispatch'/'dispatchexception'
(isn't that what Clang names the blocks it creates for the explicit dispatch
code?); 'catchendblock' would then be something like
'unwinddispatch' or 'continuedispatch' or
'resumedispatch' and the resume that returns to normal execution could
be 'exitdispatch' or 'exitcatch' or even 'uncatch'.
For the resumes that end cleanups, something like 'endcleanup' might
work.
Names are hard…

'dispatch' might work for the instruction which transitions from a
cleanup to the next EH block. :) I don't really see how to work filter in,
especially since we've already used it for landingpad filters, which exist
to support exception specifications.

Chatting around the office, we came up with 'recover' and
'unwind' for ending catch and cleanup blocks respectively.

A 'recover' instruction would end a catch block, and would target the
block where the exception is over. This instruction would modify memory, because
it destroys the exception object.

An 'unwind' instruction would end a cleanup block, and would target the
next action. I like this because I talk a lot about "unwind edges" in
the CFG, and a cleanup finishing feels like an unwind edge. I could also see
'dispatch' here.

Some possible new syntax:

recover from label %maycatch.int<http://maycatch.int> to label %endcatchbb
unwind from label %cleanup.obj to label %nextaction
unwind from label %cleanup.obj    ; unwinds out of the function, hook it up to
the unwind edge of an inlined call site

For Itanium, tail merging is profitable and doable with phis, so we might want
to do this instead:

recover to label %endcatchbb
unwind i8* %ehptr to label %nextaction
unwind i8* %ehptr    ; unwinds out of the function, hook it up to the unwind
edge of an inlined call site

Itanium requires threading the active exception pointer through to the next
action or _Unwind_Resume, so it passes along an SSA value. MSVC needs this weird
kind of control dependence instead. We could drop the 'from' token as
unnecessary, but I want to make it easier to reason about the textual
representation.
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20150519/03554876/attachment.html>

I think adding transitions to cleanupblocks on the normal execution path
would be an optimization barrier. Most passes would see the cleanupblock
instruction and run the other way. It's definitely appealing from the
perspective of getting the smallest possible code, but I'm OK with having
no more than two copies of everything in the finally block.

I think with the addition of the 'from' label we can just use shared
basic
blocks without runaway code duplication, like so:
try {
  f();
} finally {
  do_finally();
}

  ...
  invoke void @f()
    to label %cont unwind label %cleanup
cont:
  br label %finally
cleanup:
  cleanupblock
  br label %finally
finally:
  %abnormal = phi i1 [true, %cleanup], [false, %cont]
  call void @do_finally()
  br i1 %abnormal, label %finally.unwind, label %finally.normal
finally.unwind:
  unwind from label %cleanupblock
finally.normal:
  ret void

With two reachability checks we can see that cleanup, finally, and
finally.unwind are the only BBs in the finally funclet, and only finally is
shared. We can duplicate it in WinEHPrepare and fix up the CFG to reflect
that. I don't think the quadratic case is possible, even in a nested case
like:

try {
  try {
    f();
  } finally {
    do_finally(1);
  }
} finally {
  do_finally(2);
}

We'll end up with four calls to do_finally in this example. Does that seem
OK?

If that much duplication isn't OK, you can also have your frontend do early
outlining without using frameescape. Instead of passing the frame pointer,
it would pass the address of each escaped local variable. If the cleanup is
simple, it'll be inlined and some locals may be eliminated, and if not, the
outlined funclet will only contain a single call with lots of lea+push
pairs.

On Tue, May 19, 2015 at 2:22 PM, Joseph Tremoulet <jotrem at
microsoft.com>
wrote:
>  > teach the inliner how to undo framerecover and let the optimization
> fall out that way
>
> You'd still have the problem that the referenced variables were
> frameescaped and appear to be read/written at unrelated calls.
>
>
>
> > __finally is pretty rare
>
> `__finally` may be rare in SEH code, but `finally` is quite common in .Net
> code, so we're going to need a solution that avoids early `finally`
> outlining for the same reasons we're avoiding early `catch` outlining.
>
> While we do need something that's amenable to duplicating `finally`
code
> on hot/non-EH paths (since this is an important optimization for .Net
> code), I think there also needs to be a path that can be taken for very
> cold code / very large cleanups / very deeply-nested cleanups to avoid
> quadratic code expansion on those cases.  Early outlining of just those
> cases could maybe be made to work, but would require that the decision be
> made early; it would be much more palatable to make the decision in the
> natural course of optimization (e.g. some sort of tail duplication).
>
> So I think we should have a way to enter/exit cleanup blocks on non-EH
> paths.
>
> The smallest change to your proposal that comes to mind which would allow
> this would be:
>
>    - a normal branch can target a cleanupblock
>
>    - the resume/unwind terminator that ends a cleanup would have another
> optional target label (%normalsucc).  The semantics would be that the EH
> edge to %nextaction would be taken if the cleanupblock were entered by an
> EH edge, and the normal edge to %normalsucc would be taken otherwise.
>
>    - converting this to landingpads would manifest an i1 that would need
> to be set before branching to the cleanupblock, and turn the unwind/resume
> into a condbr on that
>
>    - codegen for windows could turn the branch to cleanupblock into a call
> to the handler followed by a jump to the %normalsucc
>
> A change that I'd consider preferable since it avoids the need for an
> auxiliary switch in the non-EH code would be:
>
>     - some new terminator along the lines of 'entercleanup
%cleanupblock
> recover to %recoverblock', rather than a plain branch, can target
> cleanupblocks
>
>     - the resume/unwind terminator that ends a cleanup would have any
> number of additional successors, and just like the rule that the EH target
> must match the %nextaction referenced on the cleanupblock, the non-EH
> targets would need to match one of the %recoverblocks specified on one of
> the entercleanups targeting the cleanupblock
>
>     - converting this to landingpads would manifest an int that would need
> to be set before branching to the cleanupblock, and turn the unwind/resume
> into a switch
>
>     - codegen for windows could turn entercleanup into a call to the
> handler followed by a jump to the %recoverblock
>
> Those are the first two options that come to mind, anyway.  I'm sure
there
> are other options, but the key points are:
>
> 1) can avoid early outlining of finally bodies, and
>
> 2) can avoid runaway code expansions
>
>
>
> Regarding naming, I like your new suggestions (though the changes I'm
> suggesting to cleanup-ending terminators are a mix between recover and
> unwind… FWIW, 'endfinally' would be a natural name for that in my
world J.
> Personally I wouldn't hate something verbose like recover_or_unwind for
the
> forms that may be doing either.  'endcleanup' also comes to mind.).
>
>
>
> Thanks
>
> -Joseph
>
>
>
>
>
> *From:* Reid Kleckner [mailto:rnk at google.com]
> *Sent:* Tuesday, May 19, 2015 3:40 PM
> *To:* Joseph Tremoulet
> *Cc:* LLVM Developers Mailing List; Bill Wendling; Nick Lewycky; Kaylor,
> Andrew
> *Subject:* Re: [LLVMdev] RFC: New EH representation for MSVC compatibility
>
>
>
> On Mon, May 18, 2015 at 8:40 PM, Joseph Tremoulet <jotrem at
microsoft.com>
> wrote:
>
>  > I want to have separate normal and exceptional codepaths
>
> I assume you at least mean that's what you'll be doing in
Clang's initial
> IR generation.  Do you also mean to impose this as a restriction on other
> IR generators, and as a property that IR transformations must preserve?
> I.e., is this something that EH preparation can assume?
>
>
>
> EH preparation should not assume that each basic block lives in exactly
> one funclet. People seem to get really upset when I suggest that we change
> the language rules to maintain that invariant. :-)
>
>
>
> Instead, the EH preparation pass is responsible for establishing that
> invariant by duplicating blocks, but it should be *way* easier with real
> basic block terminator instructions to mark handler transitions.
>
>
>
>  > For __finally, we outline the finally body early in clang and emit
two
> calls to it as before, but passing in the frameaddress as an argument
>
> But then you have to frameescape any __finally-referenced local before
> optimization, and doesn't that defeat the purpose of delaying funclet
> outlining to EH preparation?
>
>
>
> True. I'm not committed to this approach, I just want to preserve
> functionality until we implement the de-commoning part of EH preparation,
> which I figured we could do later, since it's one of the more obscure
> corner cases.
>
>
>
> Also, __finally is pretty rare, so it's not too crazy to teach the
inliner
> how to undo framerecover and let the optimization fall out that way.
>
>
>
>  > tail merging could kick in like you mention. Undoing this would be
and
> currently is the job of WinEHPrepare. I guess I felt like the extra
> representational complexity wasn't worth the confidence that it would
buy us
>
> For one, it seems counterproductive to let tail merge think it can kick in
> when it's doomed to be undone.
>
>
>
> I'm only saying that the tail merging is legal, and not that it is
> desirable. We can teach simplifycfg that tail merging 'resume'
instructions
> is a waste of time, for example.
>
>
>
>  For another, if we're talking about a setup where EH paths might
mingle
> with non-EH paths but the funclet will only be invoked for the EH cases,
> then I believe this would help the  "pruning as many unreachable CFG
> edges as possible " step be more effective -- after finding out which
> blocks are reachable from a catch/cleanup, you could intersect that with
> the set of blocks from which a corresponding resume can be reached.  Any
> funclet blocks ending in condbr/switch that only wind up with one successor
> in the funclet could then have their terminators rewritten as unconditional
> branches, without needing to recover dataflow and chase constants through
> phis and resolve compares/switches and all that.
>
>
>
> For discussion purposes, let's imagine that 'resume' takes a
'from' label
> which must be an EH block (it starts with one of these new instructions).
> The nice thing about using a label here is that, unlike most SSA values,
> labels cannot be phi'd. Now tail merging will have to give up or insert
an
> i1 ph and a conditional branch on the resume instruction, which
> realistically it won't since it's not a clear win.
>
>
>
> Originally, I was thinking that this extra funclet cloning precision
> wasn't worth it, because we'd arrange the frontend and optimizers
to make
> it unlikely, but I'm coming around to it. It mirrors the EH pointer
value
> required by Itanium EH.
>
>
>
>  > I'm not married to reusing 'resume', other candidate
names include
> 'unwind' and 'continue', and I'd like more ideas
>
> The first thing that comes to mind is 'endatch/exitcatch', but to
use that
> you'd need to rename other things since it would be confusing vis-à-vis
> catchendblock and lack symmetry with catchblock that isn't prefixed
with
> begin/enter.
>
> You could consider 'filter' (or 'filterblock') for
'catchblock', since
> conceptually it plays the role of a filter (typically one which consults
> type information; I've seen such things called
"typetestfilter" before).
> Or
'dispatch'/'dispatchblock'/'exceptiondispatch'/'dispatchexception'
> (isn't that what Clang names the blocks it creates for the explicit
> dispatch code?); 'catchendblock' would then be something like
> 'unwinddispatch' or 'continuedispatch' or
'resumedispatch' and the resume
> that returns to normal execution could be 'exitdispatch' or
'exitcatch' or
> even 'uncatch'.
>
> For the resumes that end cleanups, something like 'endcleanup'
might work.
>
> Names are hard…
>
>
>
> 'dispatch' might work for the instruction which transitions from a
cleanup
> to the next EH block. :) I don't really see how to work filter in,
> especially since we've already used it for landingpad filters, which
exist
> to support exception specifications.
>
>
>
> Chatting around the office, we came up with 'recover' and
'unwind' for
> ending catch and cleanup blocks respectively.
>
>
>
> A 'recover' instruction would end a catch block, and would target
the
> block where the exception is over. This instruction would modify memory,
> because it destroys the exception object.
>
>
>
> An 'unwind' instruction would end a cleanup block, and would target
the
> next action. I like this because I talk a lot about "unwind
edges" in the
> CFG, and a cleanup finishing feels like an unwind edge. I could also see
> 'dispatch' here.
>
>
>
> Some possible new syntax:
>
>
>
> recover from label %maycatch.int to label %endcatchbb
>
> unwind from label %cleanup.obj to label %nextaction
>
> unwind from label %cleanup.obj    ; unwinds out of the function, hook it
> up to the unwind edge of an inlined call site
>
>
>
> For Itanium, tail merging is profitable and doable with phis, so we might
> want to do this instead:
>
>
>
> recover to label %endcatchbb
>
> unwind i8* %ehptr to label %nextaction
>
> unwind i8* %ehptr    ; unwinds out of the function, hook it up to the
> unwind edge of an inlined call site
>
>
>
> Itanium requires threading the active exception pointer through to the
> next action or _Unwind_Resume, so it passes along an SSA value. MSVC needs
> this weird kind of control dependence instead. We could drop the
'from'
> token as unnecessary, but I want to make it easier to reason about the
> textual representation.
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20150519/9e73bfed/attachment.html>