Notes toward re-implementing EH in gimple

Notes toward re-implementing EH in gimple

[Richard Henderson]

[-- Attachment #1: Type: text/plain, Size: 155 bytes --]

> I've also been thinking a good deal about a grand EH reorg; I'll try
> to post something for you to comment on later today.

Here ya go.  Thoughts?


r~

[-- Attachment #2: EH-NOTES --]
[-- Type: text/plain, Size: 7884 bytes --]

New constructs:

  { exc_ptr, filter } = EH_LANDING_PAD;

	Placeholder for the landing-pad rtl.  Has 2 outputs
	for both the exception pointer and the filter.

  EH_DISPATCH (filter);

	Placeholder for the switch statement that we'll
	generate to jump between the alternatives for 
	different catches.

  ERT_NOP

	A new type of exception region that merely implies
	a different landing pad to the containing region.
	Inserting one of these below the "current" region
	is how we'll split critical edges, instead of copying
	regions.

  exc_ptr and filter members in each eh_region

	The code within each region will use these decls.
	When falling through from an inner region to an
	outer region, these variables must be initialized.
	These replace the EXC_PTR_EXPR and FILTER_EXPR
	constructs that we currently use.

  RESX (exc_ptr, filter);

	Of course we have this now, but we also store the
	region number in the statement directly, instead
	of via add_stmt_to_eh_region.  Which leads to special
	cases all over.  There does not seem to be a real
	point to this.  Also, we need to propagate ext_ptr
	and filter up to the next level, if we're not calling
	_Unwind_Resume.

Examples:

  Catch with nested cleanup:

	struct S { ~S(); };
	void bar();
	int x, y;
	void foo()
	{
	  try {
	    S s;
	    bar();
	  } catch (int) {
	    x++;
	  } catch (float) {
	    y++;
	  }
	}

  Compiles to (before eh_dispatch/resx expansion)

	EH Region Tree:
	  3 catch int -> post-land = BB8
	  4 catch float -> post-land = BB9
	  2 try -> { e2, f2 }, land = BB6, post-land = BB7
	    1 cleanup -> { e1, f1 }, land = BB4, post-land = BB5
	  5 must_not_throw

	BB1:
	  bar();			[EH 1]
	  # succ 2 4(eh)
	BB2:
	  S::~S(&s);			[EH 2]
	  # succ 3
	BB3:
	  return;
	  # succ exit
	BB4:
	  { e1, f1 } = EH_LANDING_PAD;	[EH 1]
	  # succ 5
	BB5:
	  S::~S(&s);			[EH 5]
	  RESX (e1, f1);
	  # succ 6(eh)
	BB6:
	  { e2, f2 } = EH_LANDING_PAD;	[EH 2]
	  # succ 7
	BB7:
	  EH_DISPATCH (f2);		[EH 2]
	  # succ 8(ab) 9(ab) 10(ab)
	BB8:
	  __cxa_begin_catch (e2);
	  x++;
	  __cxa_end_catch (e2);
	  # succ 3
	BB9:
	  __cxa_begin_catch (e2);
	  y++;
	  __cxa_end_catch (e2);
	  # succ 3
	BB10:
	  RESX (e2, f2);		[EH 2]

  After inlining, we have a new pass that expands both RESX and EH_DISPATCH:

	BB5:
	  e2 = e1;
	  f2 = f1;
	  # succ 7

	BB7:
	  switch (f2)
	    {
	    case 1:  goto BB8;
	    case 2:  goto BB9;
	    default: goto BB10
	    }
	  # succ 8 9 10

	BB10:
	  _Unwind_Resume (e2);

  There are a couple of advantages that ought to be clear immediately.
  First, no more silliness that tree_empty_eh_handler_p has to clean up.
  Second, everything can be properly put into SSA form.
  Third, we're not too late to easily generate switch statements.  See

          /* ??? It is mighty inconvenient to call back into the
             switch statement generation code in expand_end_case.
             Rapid prototyping sez a sequence of ifs.  */

  which has been in except.c for nearly 10 years.

  Critical edge splitting:

        struct S { ~S() throw(); };
        void bar();
        void foo()
        {
          S s1;
          bar();
	  bar();
	  S s0;
	  bar();
        }

  Compiles to:

	EH Region Tree:
	1 cleanup -> { e1, f1 }, land = BB7, post-land = BB8
	  2 cleanup -> { e2, f2 }, land = BB5, post-land = BB6

	BB0:
	  bar();		[EH 1]
	  # succ 1 7(eh)
	BB1:
	  bar();		[EH 1]
	  # succ 2 7(eh)
	BB2:
	  bar();		[EH 2]
	  # succ 3 5(eh)
	BB3:
	  S::~S(&s0);
	  S::~S(&s1);
	  # succ 4
	BB4:
	  return;
	BB5:
	  { e2, f2 } = EH_LANDING_PAD;
	  # succ 6
	BB6:
	  S::~S(&s0);
	  RESX (e2, f2);
	  # succ 7(eh)
	BB7:
	  { e1, f1 } = EH_LANDING_PAD;
	  # succ 8
	BB8:
	  S::~S(&s1);
	  RESX (e1, f1)

  Expand RESX and we get

	BB6:
	  S::~S(&s0);
	  e1 = e2;
	  f1 = f2;
	  # succ 8

	BB8:
	  S::~S(&s1);
	  _Unwind_Resume (e1);

  We decide we want to split edge BB1->BB7, so we modify:

	EH Region Tree:
	1 cleanup -> { e1, f1 }, land = BB7, post-land = BB8
	  2 cleanup -> { e2, f2 }, land = BB5, post-land = BB6
	  3 nop -> { e1, f1 }, land = BB9, post-land = BB8

	BB1:
	  bar();		[EH 3]
	  # succ 2 9(eh)

	BB9:
	  { e1, f1 } = EH_LANDING_PAD;
	  # succ 8

  Which, if I'm not mistaken, duplicates far less code than you
  do at present to split these edges.

  Exception optimization:

	void f();
	void g() throw();
	void h() throw();
	void foo() {
	  try {
	    try {
	      f();
	    } catch (int) {
	      g();
	    }
	  } catch (int) {
	    h();
	  }
	}

  Compiles to:

	EH Region Tree:
	4 catch int
	1 try -> { e1, f1 }, land = BB6, post-land = BB7
	  3 catch int
	  2 try -> { e2, f2 }, land = BB2, post-land = BB3

	BB0:
	  f();
	  # succ 1 2(eh)		[EH 2]
	BB1:
	  return;
	  # succ exit
	BB2:
	  { e2, f2 } = EH_LANDING_PAD;	[EH 2]
	  # succ 3
	BB3:
	  EH_DISPATCH (f2);		[EH 2]
	  # succ 4(ab) 5(ab)
	BB4:
	  __cxa_begin_catch (e2);
	  g();
	  __cxa_end_catch (e2);
	  # succ 1
	BB5:
	  RESX (e2, f2);		[EH 2]
	  # succ 6(eh)
	BB6:
	  { e1, f1 } = EH_LANDING_PAD;	[EH 1]
	  # succ 7
	BB7:
	  EH_DISPATCH (f1);		[EH 1]
	  # succ 8(ab) 9(ab)
	BB8:
	  __cxa_begin_catch (e1);
	  h();
	  __cxa_end_catch (e1);
	  # succ 1
	BB9:
	  RESX (e1, f1);

  Expanding RESX and EH_DISPATCH:

	BB3:
	  switch (f2)
	    {
	    case 0:  goto BB4;
	    default: goto BB5;
	    }
	  # succ 4 5

	BB5:
	  e1 = e2;
	  f1 = f2;
	  # succ 7

	BB7:
	  switch (f1)
	    {
	    case 0:  goto BB8;
	    default: goto BB9;
	    }
	  # succ 8 9

	BB9:
	  _Unwind_Resume (e1);

  See below for more discussion.

Implementation:

  EH_LANDING_PAD

	The existing code in except.c should be easily adaptable
	to expanding this gimple stmt.  All we need to do is pass
	along the two output arguments and use those instead of
	the hard-coded crtl->eh.exc_ptr and crtl->eh.filter.

  EH_DISPATCH:

	Should be expanded after inlining, and maybe before EH optimization.
	Again, the existing code within except.c can be adapted.  We
	just need to call assign_filter_values to get all the numbers
	assigned.  At which point it is trivial to build the actual
	switch.

  RESX:

	Should be expanded after inlining, and probably before EH
	optimization.  All we need to do here is either notice that
	there's no outer region and expand to _Unwind_Resume, or
	copy the exc_ptr/filter variables around and goto.

  EH optimization:

	This pass would remove shadowed exception handlers and other
	unreachable code.  It's supposed to be currently handled in
	reachable_next_level, and consists of some moderately complicated
	type checking every time we ask stmt_throws_internal.  Instead
	of having the complicated code run all the time, we'd have a
	special pass.

	(As an aside, the dead handler elimination we attempt in
	reachable_next_level doesn't work because the C++ front end
	tells us that __cxa_end_catch can throw, which is only true
	when the thrown object has a destructor that can throw.  With
	a single extra check in the front end, we can set the NOTHROW
	bit on that __cxa_end_catch call and re-enable this.)

	It could be implemented as a special form of value-range
	propagation.  We know that the runtime will only enter a
	landing pad under certain conditions, and the values that
	the FILTER variable will contain under those conditions.
	With that, it's trivial to propagate the values around.

	For instance, in the example above, we know that the only
	value that F1 and F0 will ever be assigned by EH_LANDING_PAD
	is 0.  From that we can determine that BB5 and BB9 are dead.

	If there were a cleanup handler somewhere in the middle,
	we'd have to bail, because the FILTER values for a cleanup
	can be anything (I think; but in any case it might have a
	different number as we'd generate for "int").

	We'll need something slightly different than the min/max
	values currently supported by VRP.  We'll need to track exact
	sets of values, but happily only for (generally) small numbers.

Re: Notes toward re-implementing EH in gimple

[Diego Novillo]

On Thu, Aug 6, 2009 at 15:35, Richard Henderson<rth@redhat.com> wrote:
>> I've also been thinking a good deal about a grand EH reorg; I'll try
>> to post something for you to comment on later today.
>
> Here ya go.  Thoughts?

Y'all are going to make the LTO streamer cry.

Re: Notes toward re-implementing EH in gimple

[Jan Hubicka]

> New constructs:
> 
>   { exc_ptr, filter } = EH_LANDING_PAD;
> 
> 	Placeholder for the landing-pad rtl.  Has 2 outputs
> 	for both the exception pointer and the filter.

Hmm, EH_LANDING_PAD will still need to be somewhat special (as moving it
across eh edge or something will change behaviour) but it indeed seems
uite sane representation of fact that the EH/filter is really set by
runtime...
> 
>   EH_DISPATCH (filter);
> 
> 	Placeholder for the switch statement that we'll
> 	generate to jump between the alternatives for 
> 	different catches.

Similarly here, it seemed to me that normal switch would suffice.
> 
>   ERT_NOP
> 
> 	A new type of exception region that merely implies
> 	a different landing pad to the containing region.
> 	Inserting one of these below the "current" region
> 	is how we'll split critical edges, instead of copying
> 	regions.

I am not sure how this will work.
When you have throwing statement inside several catch...try regions with
different types caught, you will have multiple EH edges from that
statement.  It seems that all those edges are neccesary since runtime
can really deliver control flow to any of the try..catch handlers.

We might want to redirect edge that does not correspond to the innermost
try...catch that is where we need to copy nontrivial chain of EH regions
for specific redirection.  You intend to represent this by ERT_NOP?
>   After inlining, we have a new pass that expands both RESX and EH_DISPATCH:
> 
> 	BB5:
> 	  e2 = e1;
> 	  f2 = f1;
> 	  # succ 7
> 
> 	BB7:
> 	  switch (f2)
> 	    {
> 	    case 1:  goto BB8;
> 	    case 2:  goto BB9;
> 	    default: goto BB10
> 	    }
> 	  # succ 8 9 10
> 
> 	BB10:
> 	  _Unwind_Resume (e2);

Seems sane.  Removing fully optimized out cleanups still benefits from
RESX not being lowered to _Unwind_Resume, but the lowering can happen
somewhere at later half of the optimization queue, it is not probably
going to bring that much new optimization oppurtunities.
> 
>   There are a couple of advantages that ought to be clear immediately.
>   First, no more silliness that tree_empty_eh_handler_p has to clean up.
>   Second, everything can be properly put into SSA form.
>   Third, we're not too late to easily generate switch statements.  See
> 
>           /* ??? It is mighty inconvenient to call back into the
>              switch statement generation code in expand_end_case.
>              Rapid prototyping sez a sequence of ifs.  */
> 
>   which has been in except.c for nearly 10 years.

Yep, I also found this comment entertaining ;)
> 
>   We decide we want to split edge BB1->BB7, so we modify:
> 
> 	EH Region Tree:
> 	1 cleanup -> { e1, f1 }, land = BB7, post-land = BB8
> 	  2 cleanup -> { e2, f2 }, land = BB5, post-land = BB6
> 	  3 nop -> { e1, f1 }, land = BB9, post-land = BB8
> 
> 	BB1:
> 	  bar();		[EH 3]
> 	  # succ 2 9(eh)
> 
> 	BB9:
> 	  { e1, f1 } = EH_LANDING_PAD;
> 	  # succ 8
> 
>   Which, if I'm not mistaken, duplicates far less code than you
>   do at present to split these edges.

Hmm, if I understand right, edge rediretion now involve creation of new
BB.  I don't think it is very lucky solution.  With current
implementation EH redirection behave same way as redirection of normal
edges.

We don't duplicate code, just pieces of EH tree and when we end up
redirecting things back, we cleanup.  So passes don't need to care EH
edges specially and also critical edge splitting is fully undone by
cfg+eh cleanup when nothing is inserted over the split paths.
>   EH optimization:
> 
> 	This pass would remove shadowed exception handlers and other
> 	unreachable code.  It's supposed to be currently handled in

Yes, current way of handling via unreachable code don't work as
originally was designed to, so I hoped to move this code away too.
We will need to propagate lists of types into every resx and propagate
where the resx can be reached, but it don't seem that difficult to do.

> 	(As an aside, the dead handler elimination we attempt in
> 	reachable_next_level doesn't work because the C++ front end
> 	tells us that __cxa_end_catch can throw, which is only true
> 	when the thrown object has a destructor that can throw.  With
> 	a single extra check in the front end, we can set the NOTHROW
> 	bit on that __cxa_end_catch call and re-enable this.)

Hmm, we probably should fix this...
But still there is problem that originally we didn't have RESX->outer
region edges as we do now, so regions that has types completely shadowed
by inner regions we will still have it reachable from the RESX of inner
regions (that no longer have the type info)

I will need to look into this tomorrow.  Thanks for writting this up!
Honza

Re: Notes toward re-implementing EH in gimple

[Richard Henderson]

On 08/06/2009 01:44 PM, Jan Hubicka wrote:
> Hmm, EH_LANDING_PAD will still need to be somewhat special (as moving it
> across eh edge or something will change behaviour) but it indeed seems
> uite sane representation of fact that the EH/filter is really set by
> runtime...

Yes, EH_LANDING_PAD is still somewhat special in that it cannot be
moved *at all*.  Specifically, it must be the first statement in the
block whose label is recorded in the EH Region Table.

But that's not a very onerous special case.

> Similarly here, it seemed to me that normal switch would suffice.

A normal switch only suffices after inlining, when we've collected
the complete set of types which can be caught within the function.
Until then, we must make do with a place holder.

>>    ERT_NOP
>>
>> 	A new type of exception region that merely implies
>> 	a different landing pad to the containing region.
>> 	Inserting one of these below the "current" region
>> 	is how we'll split critical edges, instead of copying
>> 	regions.
>
> I am not sure how this will work.
> When you have throwing statement inside several catch...try regions with
> different types caught, you will have multiple EH edges from that
> statement.  It seems that all those edges are neccesary since runtime
> can really deliver control flow to any of the try..catch handlers.
>
> We might want to redirect edge that does not correspond to the innermost
> try...catch that is where we need to copy nontrivial chain of EH regions
> for specific redirection.  You intend to represent this by ERT_NOP?

You're misunderstanding how the edges are to be drawn.

Under the current scheme, before rtl's finish_eh_generation runs,
we do have edges that go direct from a call to each of the possible
handlers and cleanups.

Under this proposed scheme, we model how the runtime actually
works, right from the beginning.  There is only *one* EH edge for
any one statement that can throw, and that edge is to the landing
pad.  From the landing pad, the filter value de-multiplexes this
one edge to select the proper handler/cleanup.

It seems extremely unlikely to me that we actually want to put fixup
code before handler X, as opposed to merely on any EH edge, simply
because the CFG won't be drawn that way.

We *can* put anything we want into the landing pad block (after the
actual EH_LANDING_PAD statement).  We can even duplicate the
EH_DISPATCH stmt (nee SWITCH stmt) and so split edges to individual
handlers if we really needed to go that far.

> Seems sane.  Removing fully optimized out cleanups still benefits from
> RESX not being lowered to _Unwind_Resume, but the lowering can happen
> somewhere at later half of the optimization queue, it is not probably
> going to bring that much new optimization oppurtunities.

I'd been imagining lowering RESX/EH_DISPATCH here:

   p = &all_passes;
+ NEXT_PASS (pass_lower_eh_dispatch);
   NEXT_PASS (pass_all_optimizations);

so that it happens immediately after inlining even without -O1.

>>    There are a couple of advantages that ought to be clear immediately.
>>    First, no more silliness that tree_empty_eh_handler_p has to clean up.
>>    Second, everything can be properly put into SSA form.
>>    Third, we're not too late to easily generate switch statements.  See
>>
>>            /* ??? It is mighty inconvenient to call back into the
>>               switch statement generation code in expand_end_case.
>>               Rapid prototyping sez a sequence of ifs.  */
>>
>>    which has been in except.c for nearly 10 years.
>
> Yep, I also found this comment entertaining ;)
>>    We decide we want to split edge BB1->BB7, so we modify:
>>
>> 	EH Region Tree:
>> 	1 cleanup ->  { e1, f1 }, land = BB7, post-land = BB8
>> 	  2 cleanup ->  { e2, f2 }, land = BB5, post-land = BB6
>> 	  3 nop ->  { e1, f1 }, land = BB9, post-land = BB8
>>
>> 	BB1:
>> 	  bar();		[EH 3]
>> 	  # succ 2 9(eh)
>>
>> 	BB9:
>> 	  { e1, f1 } = EH_LANDING_PAD;
>> 	  # succ 8
>>
>>    Which, if I'm not mistaken, duplicates far less code than you
>>    do at present to split these edges.
>
> Hmm, if I understand right, edge rediretion now involve creation of new
> BB.  I don't think it is very lucky solution.  With current
> implementation EH redirection behave same way as redirection of normal
> edges.

Pardon?  Edge splitting always involves creation of a new block.
The only thing that's different here is that the new block isn't
empty -- it must include the EH_LANDING_PAD statement.

What did you think you are doing in the current implementation?
It's the same, except the expansion of the landing pad is hidden
in the rtl code, triggered by the label being in the EH tables.

I almost wish the EH_LANDING_PAD could be hidden within the PHIs,
so that it couldn't be separated from the beginning of the block.

Actually, it occurs to me that we *could* do something really
really special here.  Suppose we make SSA notice EH landing pad
labels, and go off to the EH table to find the statement.  In
that way, the EH_LANDING_PAD statement wouldn't really exist
in the normal code stream, and so it couldn't be mis-placed.

I do wonder if the fact that the statement isn't in the code
stream causes other weird side effects, but I can't imagine it's
any weirder than PHIs not being in the code stream.

> We don't duplicate code, just pieces of EH tree and when we end up
> redirecting things back, we cleanup.  So passes don't need to care EH
> edges specially and also critical edge splitting is fully undone by
> cfg+eh cleanup when nothing is inserted over the split paths.

Hmm.  Perhaps you could find an example of when this splitting
and cleanup is done on the current tree?  I have a feeling it
would be a similar amount of code with my scheme.

> But still there is problem that originally we didn't have RESX->outer
> region edges as we do now, so regions that has types completely shadowed
> by inner regions we will still have it reachable from the RESX of inner
> regions (that no longer have the type info)

We *don't* actually have those RESX->outer edges at the moment.
That's one of the things that I'm trying to fix with my trans-mem
dominator patch... which I've spent most of the day not working on.  :-P


r~

Re: Notes toward re-implementing EH in gimple

[Richard Henderson]

On 08/06/2009 12:35 PM, Richard Henderson wrote:
>   { exc_ptr, filter } = EH_LANDING_PAD;
>
> 	Placeholder for the landing-pad rtl.  Has 2 outputs
> 	for both the exception pointer and the filter.

I'm going to drop this construct.  Instead, I'm going to mark
the label, and have the landing pad code be emitted as it
currently is by the rtl.  This will prevent any problems with
the landing pad code being moved away from the start of the
block.

I'm going to adjust the rtl code so that it generates different
pseudos for exc_ptr and filter for each region.  These will be
accessible from gimple with the EXC_PTR_EXPR and FILTER_EXPR
tree codes.

EXC_PTR_EXPR and FILTER_EXPR will be expanded to take the EH
region number as a parameter.  Since they no longer need to be
saved and restored, they will no longer be gimple lvalues.

In gimple, the landing pad will be generated as

L.N:
   exc_ptr.1 = EXC_PTR_EXPR (N);
   filter.1 = FILTER_EXPR (N);

ie, copied into normal variables for use.  These can be moved
about, or deleted, as the optimizer desires.

All of this seems much cleaner than what I initially imagined.


r~

Re: Notes toward re-implementing EH in gimple

[Richard Guenther]

On Fri, Aug 7, 2009 at 9:22 PM, Richard Henderson<rth@redhat.com> wrote:
> On 08/06/2009 12:35 PM, Richard Henderson wrote:
>>
>>  { exc_ptr, filter } = EH_LANDING_PAD;
>>
>>        Placeholder for the landing-pad rtl.  Has 2 outputs
>>        for both the exception pointer and the filter.
>
> I'm going to drop this construct.  Instead, I'm going to mark
> the label, and have the landing pad code be emitted as it
> currently is by the rtl.  This will prevent any problems with
> the landing pad code being moved away from the start of the
> block.
>
> I'm going to adjust the rtl code so that it generates different
> pseudos for exc_ptr and filter for each region.  These will be
> accessible from gimple with the EXC_PTR_EXPR and FILTER_EXPR
> tree codes.
>
> EXC_PTR_EXPR and FILTER_EXPR will be expanded to take the EH
> region number as a parameter.  Since they no longer need to be
> saved and restored, they will no longer be gimple lvalues.
>
> In gimple, the landing pad will be generated as
>
> L.N:
>  exc_ptr.1 = EXC_PTR_EXPR (N);
>  filter.1 = FILTER_EXPR (N);

Will exc_ptr.1 and filter.1 be gimple registers?  Does the above have
virtual operands, thus are there any aliases to whatever EXP_PTR_EXPR
or FILTER_EXPR load?

Can we CSE FILTER_EXPR (N) and EXC_PTR_EXPR (N)?

> ie, copied into normal variables for use.  These can be moved
> about, or deleted, as the optimizer desires.
>
> All of this seems much cleaner than what I initially imagined.

Thanks for cleaning this up.

Richard.

>
> r~
>
>

Re: Notes toward re-implementing EH in gimple

[Richard Henderson]

On 08/07/2009 12:31 PM, Richard Guenther wrote:
>> L.N:
>>   exc_ptr.1 = EXC_PTR_EXPR (N);
>>   filter.1 = FILTER_EXPR (N);
>
> Will exc_ptr.1 and filter.1 be gimple registers?

Yes.

> Does the above have
> virtual operands, thus are there any aliases to whatever EXP_PTR_EXPR
> or FILTER_EXPR load?

No and no.  They will eventually resolve to pseudos generated during
rtl eh expansion.  But to avoid silliness at the gimple level I don't
want to allow them to appear at random.

Ideally, the rtl would generate what it needs directly into exc_ptr.1,
but I couldn't figure out any way to do that cleanly.  In the end,
generating an extra pseudo for register allocation to coalesce is not
the worst sin I could commit here.

> Can we CSE FILTER_EXPR (N) and EXC_PTR_EXPR (N)?

Yes.


r~

Re: Notes toward re-implementing EH in gimple

[Michael Matz]

Hi,

On Fri, 7 Aug 2009, Richard Henderson wrote:

> On 08/07/2009 12:31 PM, Richard Guenther wrote:
> > > L.N:
> > >   exc_ptr.1 = EXC_PTR_EXPR (N);
> > >   filter.1 = FILTER_EXPR (N);
> >
> > Does the above have
> > virtual operands, thus are there any aliases to whatever EXP_PTR_EXPR
> > or FILTER_EXPR load?
> 
> No and no.  They will eventually resolve to pseudos generated during
> rtl eh expansion.  But to avoid silliness at the gimple level I don't
> want to allow them to appear at random.

Shouldn't it be enough to have EXC_PTR_EXPR/FILTER_EXPR simply be builtin 
functions with proper attributes.  They wouldn't be moved upwards over the 
EH edge because that would introduce effects after the throwing stmt, and 
they wouldn't be moved downwards due to use-def relationships on 
exc_ptr.1/filter.1 in the EH_DISPATCH/RESX uses.

> Ideally, the rtl would generate what it needs directly into exc_ptr.1,
> but I couldn't figure out any way to do that cleanly.  In the end,
> generating an extra pseudo for register allocation to coalesce is not
> the worst sin I could commit here.
> 
> > Can we CSE FILTER_EXPR (N) and EXC_PTR_EXPR (N)?
> 
> Yes.

Which also would just work with builtin functions of proper attributes.


Ciao,
Michael.

Re: Notes toward re-implementing EH in gimple

[Richard Guenther]

On Mon, Aug 10, 2009 at 2:53 PM, Michael Matz<matz@suse.de> wrote:
> Hi,
>
> On Fri, 7 Aug 2009, Richard Henderson wrote:
>
>> On 08/07/2009 12:31 PM, Richard Guenther wrote:
>> > > L.N:
>> > >   exc_ptr.1 = EXC_PTR_EXPR (N);
>> > >   filter.1 = FILTER_EXPR (N);
>> >
>> > Does the above have
>> > virtual operands, thus are there any aliases to whatever EXP_PTR_EXPR
>> > or FILTER_EXPR load?
>>
>> No and no.  They will eventually resolve to pseudos generated during
>> rtl eh expansion.  But to avoid silliness at the gimple level I don't
>> want to allow them to appear at random.
>
> Shouldn't it be enough to have EXC_PTR_EXPR/FILTER_EXPR simply be builtin
> functions with proper attributes.  They wouldn't be moved upwards over the
> EH edge because that would introduce effects after the throwing stmt, and
> they wouldn't be moved downwards due to use-def relationships on
> exc_ptr.1/filter.1 in the EH_DISPATCH/RESX uses.

What would these attributes be?  If you want to have the builtin
having side-effects it can't be pure or const.

>> Ideally, the rtl would generate what it needs directly into exc_ptr.1,
>> but I couldn't figure out any way to do that cleanly.  In the end,
>> generating an extra pseudo for register allocation to coalesce is not
>> the worst sin I could commit here.
>>
>> > Can we CSE FILTER_EXPR (N) and EXC_PTR_EXPR (N)?
>>
>> Yes.
>
> Which also would just work with builtin functions of proper attributes.

Which would require either pure or const attributes.

Richard.

Re: Notes toward re-implementing EH in gimple

[Michael Matz]

[-- Attachment #1: Type: TEXT/PLAIN, Size: 1020 bytes --]

Hi,

On Mon, 10 Aug 2009, Richard Guenther wrote:

> >> No and no.  They will eventually resolve to pseudos generated during 
> >> rtl eh expansion.  But to avoid silliness at the gimple level I don't 
> >> want to allow them to appear at random.
> >
> > Shouldn't it be enough to have EXC_PTR_EXPR/FILTER_EXPR simply be 
> > builtin functions with proper attributes.  They wouldn't be moved 
> > upwards over the EH edge because that would introduce effects after 
> > the throwing stmt, and they wouldn't be moved downwards due to use-def 
> > relationships on exc_ptr.1/filter.1 in the EH_DISPATCH/RESX uses.
> 
> What would these attributes be?  If you want to have the builtin having 
> side-effects it can't be pure or const.

Ah, you got me, I conciously wrote 'proper' :)  Theoretically these 
functions are pure, with the EH edges clobbering global state.  The latter 
might possibly be modeled with PHI nodes on .MEM.  But that would probably 
prevent the below CSEing again :-/

Hmm.


Ciao,
Michael.

Re: Notes toward re-implementing EH in gimple

[Richard Guenther]

On Mon, Aug 10, 2009 at 3:21 PM, Michael Matz<matz@suse.de> wrote:
> Hi,
>
> On Mon, 10 Aug 2009, Richard Guenther wrote:
>
>> >> No and no.  They will eventually resolve to pseudos generated during
>> >> rtl eh expansion.  But to avoid silliness at the gimple level I don't
>> >> want to allow them to appear at random.
>> >
>> > Shouldn't it be enough to have EXC_PTR_EXPR/FILTER_EXPR simply be
>> > builtin functions with proper attributes.  They wouldn't be moved
>> > upwards over the EH edge because that would introduce effects after
>> > the throwing stmt, and they wouldn't be moved downwards due to use-def
>> > relationships on exc_ptr.1/filter.1 in the EH_DISPATCH/RESX uses.
>>
>> What would these attributes be?  If you want to have the builtin having
>> side-effects it can't be pure or const.
>
> Ah, you got me, I conciously wrote 'proper' :)  Theoretically these
> functions are pure, with the EH edges clobbering global state.  The latter
> might possibly be modeled with PHI nodes on .MEM.  But that would probably
> prevent the below CSEing again :-/

For pure functions there should indeed be PHI nodes for .MEM because
we have new state on the incoming EH edges.  So it might even work.
It doesn't prevent the function from being sinked somewhere, but
nobody is going to do that for reads anyway (fingers crossing).

Richard.

> Hmm.
>
>
> Ciao,
> Michael.

Re: Notes toward re-implementing EH in gimple

[Richard Henderson]

On 08/10/2009 05:53 AM, Michael Matz wrote:
> Shouldn't it be enough to have EXC_PTR_EXPR/FILTER_EXPR simply be builtin
> functions with proper attributes.

Yes, that would be entirely possible.  I thought about that later,
after I'd posted that message.

Yall worry about pure/const'ness downthread: they could be const.
There are absolutely no side effects at the site of the builtin
at all.  Really, it's just a placeholder for a pseudo that rtl eh
expanders created elsewhere at the landing pad.

Cleaning that up won't be in my initial patch, I don't think, but
it will be easy to do later.


r~

Re: Notes toward re-implementing EH in gimple

[Michael Matz]

Hi,

On Mon, 10 Aug 2009, Richard Henderson wrote:

> On 08/10/2009 05:53 AM, Michael Matz wrote:
> > Shouldn't it be enough to have EXC_PTR_EXPR/FILTER_EXPR simply be builtin
> > functions with proper attributes.
> 
> Yes, that would be entirely possible.  I thought about that later,
> after I'd posted that message.
> 
> Yall worry about pure/const'ness downthread: they could be const.

If they were const (implying no dependency on global memory state) they 
could be hoisted out of loops right to the functions start (if EH edges 
aren't magic).  You certainly don't want that and IMHO it would be good to 
make EH edges less magic than more.

> There are absolutely no side effects at the site of the builtin
> at all.

It's not that they _create_ side-effects, but they depend on some.

  Really, it's just a placeholder for a pseudo that rtl eh
> expanders created elsewhere at the landing pad.

Right, but conceptually this magic setting of registers happens on the 
traversal of the EH edge there and it is this change of global state that 
these two builtins would need to depend on.  A VUSE would be one method of 
modelling it and that's exactly the difference between const and pure 
functions, only the latter have VUSE<.MEM>.

> Cleaning that up won't be in my initial patch, I don't think, but
> it will be easy to do later.

Btw, it's really wonderful that someone tackles EH-on-gimple ;-)


Ciao,
Michael.

Re: Notes toward re-implementing EH in gimple

[Richard Henderson]

On 08/10/2009 08:20 AM, Michael Matz wrote:
> It's not that they _create_ side-effects, but they depend on some.

Ah, fair enough.  I hadn't actually thought that all through.

> Btw, it's really wonderful that someone tackles EH-on-gimple ;-)

I hadn't been planning on it, but my trans-mem branch is stalled
on the dominator-breaking representation we have in gimple atm.

I tried fixing that, but ran quite afoul of Honza's critical edge
splitting pass.  There's absolutely no way to split a resx edge
in the current representation, and we're saved only by the fact
that resx statements don't have edges at the moment.  Though you
wouldn't know it by looking at the code.  Lots of places seem to
think resx should have edges.  But deep down in the middle you'd
find that resx doesn't satisfy stmt_could_throw_p, which stops
the eh edge creation right in its tracks.

So it seems there's nothing to do but rewrite it all.  ;-)


r~

Re: Notes toward re-implementing EH in gimple

[Jan Hubicka]

Hi,
sorry for jumping in late, I had relatively urgent things to work at
and didn't had much time to think this over.

I am still having some problems understanding the plans on critical edge
splitting.

> EXC_PTR_EXPR and FILTER_EXPR will be expanded to take the EH
> region number as a parameter.  Since they no longer need to be
> saved and restored, they will no longer be gimple lvalues.
> 
> In gimple, the landing pad will be generated as
> 
> L.N:
>   exc_ptr.1 = EXC_PTR_EXPR (N);
>   filter.1 = FILTER_EXPR (N);
> 
> ie, copied into normal variables for use.  These can be moved
> about, or deleted, as the optimizer desires.
> 
> All of this seems much cleaner than what I initially imagined.

This seems quite stramlined representation.  When splitting the edge, we
do create new landing pad, but will re-use the same (N) value so code
don't needs to be duplicated/updated, right?
This makes my comment on need for new BB mood. Sure critical edge
splitting involves creating of new BB, but I was concerned about the
fact that BB needs to have { e1, f1 } = EH_LANDING_PAD; in it.  I wanted
to more note that it seems to make snese to aim towards EH edges
arbitrarily redirectable without need to modify basic blocks while doing
so. Even if critical edge splitting is main use for it, it is IMO better
if EH edges behave regularly like other edges for the compiler if it is
feasible to do so.  Otherwise we would need to keep ABNORMAL flag on
them and end up having specialized code to do CFG transformations we
want (I am not sure how much besides critical edge splitting and EH
cleanup we actually want though, but it seems to me that eventually we
will find more use for it). Situation seems similar here to RTL
non-cfglayout issues, just less evil.

I do understand that at mainline we used to have edges from call to
every possible handler and no resx edges first to allow DCE code to work
out non-trivially inaccessible EH handlers because of type handling
logic in foreach_reachable_handler. I also see that you intend to add EH
edges only to the control flow transitions that really happen at runtime
(that include EH edges from RESX to outer region) that will result in
smaller CFG that is technically correct. Nontrivially dead EH stuff can
be handled by EH clenaup.

If there is only one edge from each EH statement, I see that you can use
the NOP region tree to assign it new destination label instead of
duplicating parts of EH tree to do the same redirection.  (current code
involve no code duplicaiton, just EH tree, so the duplication don't seem
that evil to me since EH trees are small and resulting code won't
change).

What I still fail to see how this scheme is going to avoid need for
multiple edges from a call.  I was under impression that code in
collect_one_action_chain produces dwarf representation as list labels
and conditionals executed by runtime. So the runtime actually can
deliever EH from the call to several EH regions and we ought to have
edges for all of them. Otherwise we will get wrong code bug adding
something across the path from innermost possible handler to the outer
handler that won't be executed if the outer handler is delivered by the
runtime dirrectly.

In fact I was considering going further here and drop the current
lexical EH tree representation and instead do the lowering to action
chains very early and do all the transformations later on the lowered
chains.  It seems a lot easier representation to think of than what we
have now?

EH regions could be just action lists and we can do hashing of action
lists to catch duplicates as we do redirecting and other operations on
them.

> We *don't* actually have those RESX->outer edges at the moment.
> That's one of the things that I'm trying to fix with my trans-mem
> dominator patch... which I've spent most of the day not working on.  :-P

Note that there are edges from RESX to the outer region, just in mainlie
not all of them that is more a bug IMO (I run into this issue previously
too since I tried to change the scheme EH edges are drawn as you
outlined above). You can easilly verify that there are EH edges out of
BBs ending with RESX.

Honza
> 
> 
> r~

Re: Notes toward re-implementing EH in gimple

[Richard Henderson]

On 08/13/2009 06:48 AM, Jan Hubicka wrote:
>> In gimple, the landing pad will be generated as
>>
>> L.N:
>>    exc_ptr.1 = EXC_PTR_EXPR (N);
>>    filter.1 = FILTER_EXPR (N);
>>
>> ie, copied into normal variables for use.  These can be moved
>> about, or deleted, as the optimizer desires.
>>
>> All of this seems much cleaner than what I initially imagined.
>
> This seems quite stramlined representation.  When splitting the edge, we
> do create new landing pad, but will re-use the same (N) value so code
> don't needs to be duplicated/updated, right?

Yes.  Although I'm streamlining things even more now.  I've eliminated
the "global" variables that store the excptr/filter, and instead each
individual use location is asking for what it needs locally.

Further, the actual landing pad itself is *not* generated in gimple.
I had too many problems updating SSA form (in particular PHIs) when
I tried to prevent non-EH edges from using the EH landing pad label.
So now it's really a post-landing-pad label, and the actual landing
pad is still generated in rtl.

However, the CFG is still much improved over the current state.

>  I wanted
> to more note that it seems to make snese to aim towards EH edges
> arbitrarily redirectable without need to modify basic blocks while doing
> so.

This is exactly what I've got now.

> What I still fail to see how this scheme is going to avoid need for
> multiple edges from a call.  I was under impression that code in
> collect_one_action_chain produces dwarf representation as list labels
> and conditionals executed by runtime. So the runtime actually can
> deliever EH from the call to several EH regions and we ought to have
> edges for all of them.

collect_one_action_chain only produces one landing_pad label for
any one call site.  It does not produce multiple edges.

> In fact I was considering going further here and drop the current
> lexical EH tree representation and instead do the lowering to action
> chains very early and do all the transformations later on the lowered
> chains.  It seems a lot easier representation to think of than what we
> have now?

I'm really not sure what you mean by this.  Make the EH region number
associated with each statement be the action chain index?  A possibly
interesting idea, but I'm not sure what it gains you.  Certainly not
ease of optimization when it comes to cleaning up shadowed catch
handlers.

> Note that there are edges from RESX to the outer region, just in mainlie
> not all of them that is more a bug IMO (I run into this issue previously
> too since I tried to change the scheme EH edges are drawn as you
> outlined above). You can easilly verify that there are EH edges out of
> BBs ending with RESX.

I easily verified that there were not edges out of BBs ending with RESX.
Further, I first fixed the bug that prevented them, and then watched the
crited pass die because it doesn't properly handle splitting RESX edges.


r~

Re: Notes toward re-implementing EH in gimple

[Jan Hubicka]

> On 08/10/2009 08:20 AM, Michael Matz wrote:
> >It's not that they _create_ side-effects, but they depend on some.
> 
> Ah, fair enough.  I hadn't actually thought that all through.
> 
> >Btw, it's really wonderful that someone tackles EH-on-gimple ;-)
> 
> I hadn't been planning on it, but my trans-mem branch is stalled
> on the dominator-breaking representation we have in gimple atm.
> 
> I tried fixing that, but ran quite afoul of Honza's critical edge
> splitting pass.  There's absolutely no way to split a resx edge
> in the current representation, and we're saved only by the fact
> that resx statements don't have edges at the moment.  Though you

You should be able to split it by copying the regions and I was
definitly dealing with RESX edges when working on the redirection patch.
(we no longer require RESX region number to match region number of
exception we are just serving).

make_edges do call make_eh_edges for resx:
         case GIMPLE_RESX:
                  make_eh_edges (last);
and make_eh_edges will create them for you.
and I do get them in i.e. tramp3d dumps:

  save_filt.98_8 = [filter_expr] <<<filter object>>>;
  save_eptr.97_9 = [exc_ptr_expr] <<<exception object>>>;
  std::allocator<int>::~allocator (&D.99154);
  <<<exception object>>> = save_eptr.97_9;
  <<<filter object>>> = save_filt.98_8;
  resx 4
  # SUCC: 7 [100.0%]  (eh)

So perhaps you get the edges purged? But that is using can_throw_internal 
that also handles the edges.

> wouldn't know it by looking at the code.  Lots of places seem to
> think resx should have edges.  But deep down in the middle you'd
> find that resx doesn't satisfy stmt_could_throw_p, which stops
> the eh edge creation right in its tracks.
> 
> So it seems there's nothing to do but rewrite it all.  ;-)

If it helps in short term, I can try to fix this if you send me your
patch fixing the missing edges problem.

Honza
> 
> 
> r~

Re: Notes toward re-implementing EH in gimple

[Jan Hubicka]

> 
> Yes.  Although I'm streamlining things even more now.  I've eliminated
> the "global" variables that store the excptr/filter, and instead each
> individual use location is asking for what it needs locally.
> 
> Further, the actual landing pad itself is *not* generated in gimple.
> I had too many problems updating SSA form (in particular PHIs) when
> I tried to prevent non-EH edges from using the EH landing pad label.
> So now it's really a post-landing-pad label, and the actual landing
> pad is still generated in rtl.

This sounds fine.
> > I wanted
> >to more note that it seems to make snese to aim towards EH edges
> >arbitrarily redirectable without need to modify basic blocks while doing
> >so.
> 
> This is exactly what I've got now.

And this too, of course :)
> 
> >What I still fail to see how this scheme is going to avoid need for
> >multiple edges from a call.  I was under impression that code in
> >collect_one_action_chain produces dwarf representation as list labels
> >and conditionals executed by runtime. So the runtime actually can
> >deliever EH from the call to several EH regions and we ought to have
> >edges for all of them.
> 
> collect_one_action_chain only produces one landing_pad label for
> any one call site.  It does not produce multiple edges.

And this is major point of my confussion.  I allways assumed that
there are multiple labels, not that we always land to the innermost
landing pad on the way.
> 
> >In fact I was considering going further here and drop the current
> >lexical EH tree representation and instead do the lowering to action
> >chains very early and do all the transformations later on the lowered
> >chains.  It seems a lot easier representation to think of than what we
> >have now?
> 
> I'm really not sure what you mean by this.  Make the EH region number
> associated with each statement be the action chain index?  A possibly
> interesting idea, but I'm not sure what it gains you.  Certainly not
> ease of optimization when it comes to cleaning up shadowed catch
> handlers.

Yes, this is what I was thinking about.  
In the lowered representation one would actually need to do VRP style
dataflow to prove that given EH region is shadowed, while in higher
representation we can stick with the current algorithm that is used for
CFG buid just without actually building CFG just marking reachability...

Honza