Patchwork New switch optimization pass (PR tree-optimization/54742)

login
register
mail settings
Submitter Steve Ellcey
Date May 14, 2013, 9:14 p.m.
Message ID <1368566063.16206.9.camel@ubuntu-sellcey>
Download mbox | patch
Permalink /patch/243828/
State New
Headers show

Comments

Steve Ellcey - May 14, 2013, 9:14 p.m.
While Jeff works on the threader, I was wondering if I could get approval for
just the dominance.c part of the patch.  This would allow me to use my pass as
a dynamically loaded optimization pass.  But without this change to dominance.c,
the compiler aborts in iterate_fix_dominators when I do that.

Steve Ellcey
sellcey@imgtec.com



2013-05-14  Steve Ellcey  <sellcey@imgtec.com>

	* dominance.c (iterate_fix_dominators): Add null check.
Jeff Law - May 15, 2013, 5:02 a.m.
On 05/14/2013 03:14 PM, Steve Ellcey wrote:
>
> While Jeff works on the threader, I was wondering if I could get approval for
> just the dominance.c part of the patch.  This would allow me to use my pass as
> a dynamically loaded optimization pass.  But without this change to dominance.c,
> the compiler aborts in iterate_fix_dominators when I do that.
>
> Steve Ellcey
> sellcey@imgtec.com
>
>
>
> 2013-05-14  Steve Ellcey  <sellcey@imgtec.com>
>
> 	* dominance.c (iterate_fix_dominators): Add null check.
I'd like to understand this a little more before we go forward with it.

AFAICT, that routine is trying to incrementally update the dominators 
using knowledge that the region you've copied is SESE.  It's unclear 
what happens in the region is not SESE.

Threading mucks up the dominator tree in fairly serious ways and to the 
best of my knowledge neither of the calls to thread across edges make 
any attempt to incrementally update the dominator tree.  They wipe it 
completely, they also have to be quite careful in how they manipulate 
the various graphs to avoid getting into an inconsistent state, then 
calling routines that assume consistent state.


I realize you're trying to do the same, but by using the SESE copier, 
you're implicitly trying to do an incremental update.  I think you're 
going to really need to look at the assumptions of that code and verify 
that the switch FSA optimization doesn't violate those assumptions.

Jeff
Richard Guenther - May 15, 2013, 8:44 a.m.
On Wed, May 15, 2013 at 7:02 AM, Jeff Law <law@redhat.com> wrote:
> On 05/14/2013 03:14 PM, Steve Ellcey wrote:
>>
>>
>> While Jeff works on the threader, I was wondering if I could get approval
>> for
>> just the dominance.c part of the patch.  This would allow me to use my
>> pass as
>> a dynamically loaded optimization pass.  But without this change to
>> dominance.c,
>> the compiler aborts in iterate_fix_dominators when I do that.
>>
>> Steve Ellcey
>> sellcey@imgtec.com
>>
>>
>>
>> 2013-05-14  Steve Ellcey  <sellcey@imgtec.com>
>>
>>         * dominance.c (iterate_fix_dominators): Add null check.
>
> I'd like to understand this a little more before we go forward with it.
>
> AFAICT, that routine is trying to incrementally update the dominators using
> knowledge that the region you've copied is SESE.  It's unclear what happens
> in the region is not SESE.
>
> Threading mucks up the dominator tree in fairly serious ways and to the best
> of my knowledge neither of the calls to thread across edges make any attempt
> to incrementally update the dominator tree.  They wipe it completely, they
> also have to be quite careful in how they manipulate the various graphs to
> avoid getting into an inconsistent state, then calling routines that assume
> consistent state.
>
>
> I realize you're trying to do the same, but by using the SESE copier, you're
> implicitly trying to do an incremental update.  I think you're going to
> really need to look at the assumptions of that code and verify that the
> switch FSA optimization doesn't violate those assumptions.

Indeed.  I'd rather have a flag to the SESE copier that tells it the region
is SEME and in that case make it not update dominators but leave that
to the caller (which means, recompute them).  It seems the code already
handles ME regions if the other exits are "not important" (we don't have
to insert/update PHI nodes in those exit blocks), so it may be that there
are even more constraints on those unimportant exits due to the
iterative dominator update - I think that the entry block of the region
needs to dominate all exit destinations, otherwise get_dominated_by_region
is not working correctly.  In your case one exit is a back-edge?  We should
be able to add checking to the code to verify unimportant edges are
unimportant "enough".

I'm sure Zdenek knows the limitations best.

Richard.

> Jeff
Steven Bosscher - May 15, 2013, 8:56 a.m.
On Wed, May 15, 2013 at 10:44 AM, Richard Biener wrote:
> Indeed.  I'd rather have a flag to the SESE copier that tells it the region
> is SEME and in that case make it not update dominators but leave that
> to the caller (which means, recompute them).

And rename the copier to SEME copier instead of SESE ;-)

Ciao!
Steven
Jeff Law - May 15, 2013, 4:33 p.m.
On 05/15/2013 02:44 AM, Richard Biener wrote:
>
> Indeed.  I'd rather have a flag to the SESE copier that tells it the region
> is SEME and in that case make it not update dominators but leave that
> to the caller (which means, recompute them).  It seems the code already
> handles ME regions if the other exits are "not important" (we don't have
> to insert/update PHI nodes in those exit blocks), so it may be that there
> are even more constraints on those unimportant exits due to the
> iterative dominator update - I think that the entry block of the region
> needs to dominate all exit destinations, otherwise get_dominated_by_region
> is not working correctly.  In your case one exit is a back-edge?  We should
> be able to add checking to the code to verify unimportant edges are
> unimportant "enough".
There's definitely a backedge -- the whole point is to thread across the 
back edge which allows us to statically determine where the switch 
statement on the next iteration.

> I'm sure Zdenek knows the limitations best.
Yea, I relied on Zdenek for a lot of the graph stuff in the past :-0

jeff
Zdenek Dvorak - May 15, 2013, 10:32 p.m.
Hi,

> > I realize you're trying to do the same, but by using the SESE copier, you're
> > implicitly trying to do an incremental update.  I think you're going to
> > really need to look at the assumptions of that code and verify that the
> > switch FSA optimization doesn't violate those assumptions.
> 
> Indeed.  I'd rather have a flag to the SESE copier that tells it the region
> is SEME and in that case make it not update dominators but leave that
> to the caller (which means, recompute them).  It seems the code already
> handles ME regions if the other exits are "not important" (we don't have
> to insert/update PHI nodes in those exit blocks), so it may be that there
> are even more constraints on those unimportant exits due to the
> iterative dominator update - I think that the entry block of the region
> needs to dominate all exit destinations, otherwise get_dominated_by_region
> is not working correctly.  In your case one exit is a back-edge?  We should
> be able to add checking to the code to verify unimportant edges are
> unimportant "enough".
> 
> I'm sure Zdenek knows the limitations best.

as far as I remember, indeed only the single-entry assumption is important
(but I do not remember all that much, unfortunately),

Zdenek

Patch

diff --git a/gcc/dominance.c b/gcc/dominance.c
index 5c96dad..d858ad1 100644
--- a/gcc/dominance.c
+++ b/gcc/dominance.c
@@ -1251,6 +1251,7 @@  iterate_fix_dominators (enum cdi_direction dir, vec<basic_block> bbs,
   struct pointer_map_t *map;
   int *parent, *son, *brother;
   unsigned int dir_index = dom_convert_dir_to_idx (dir);
+  void **slot;
 
   /* We only support updating dominators.  There are some problems with
      updating postdominators (need to add fake edges from infinite loops
@@ -1357,7 +1358,10 @@  iterate_fix_dominators (enum cdi_direction dir, vec<basic_block> bbs,
 	  if (dom == bb)
 	    continue;
 
-	  dom_i = (size_t) *pointer_map_contains (map, dom);
+	  slot = pointer_map_contains (map, dom);
+	  if (slot == NULL)
+	    continue;
+	  dom_i = (size_t) *slot;
 
 	  /* Do not include parallel edges to G.  */
 	  if (!bitmap_set_bit ((bitmap) g->vertices[dom_i].data, i))