pretty-ipa merge 16: EH redirection

[Jan Hubicka]

> 
> Huh.  I wonder if it is worth profiling them.  But well, it probably
> doesn't matter.

Probably not :)
> > + /* Return true if T1 and T2 are equivalent lists.  */
> > + 
> > + static bool
> > + list_match (tree t1, tree t2)
> > + {
> > +   for (; t1 && t2; t1 = TREE_CHAIN (t1) , t2 = TREE_CHAIN (t2))
> > +     if (TREE_VALUE (t1) != TREE_VALUE (t2))
> > +       return false;
> > +   return !t1 && !t2;
> > + }
> 
> Huh.  Ok, I cannot find an existing function that does this, but it
> belongs in tree.c, rename it to list_equal.

Well, theoretically we can be smarter there. The lists are actually
sets. (i.e. don't have particular order).  But I doubt it is worth the
effort, so I will use the list_equal test.
EH redirection will never reorder the sets, so it would match only if
user was using throw(...) markers in random orders or so.
> 
> > + 
> > + /* Return true if region R2 can be replaced by R1.  */
> > + 
> > + static bool
> > + eh_region_replaceable_by_p (const struct eh_region *r1,
> > + 			    const struct eh_region *r2)
> > + {
> 
> Please add some comments

It is just testing that the regions are equivalent.  I will try to come
up with domething.

> > + 	break;
> > +       case ERT_TRY:
> > + 	{
> > + 	  struct eh_region *c1, *c2;
> > + 	  for (c1 = r1->u.eh_try.eh_catch,
> > + 	       c2 = r2->u.eh_try.eh_catch;
> > + 	       c1 && c2;
> > + 	       c1 = c1->u.eh_catch.next_catch,
> > + 	       c2 = c2->u.eh_catch.next_catch)
> 
> So these are sorted lists?

Yes, every try region has associated catch regions that are tested in
order, so basicaly the function is verifying that all the catch regions
match.

> > + /* Merge region R2 into R1.  */
> > + 
> > + static void
> > + replace_region (struct eh_region *r1, struct eh_region *r2)
> 
> Merge or replace?

It should be replace, my original name merge_regions didn't make it
clear that it is R1 region that survive the operation and R2 region that
gets removed.

> > +   /* There are few regions to inspect;
> > +      N^2 loop matching each region with each region
> > +      will do the job well.  */
> > +   if (num_regions < 1)
> 
> < 1 doesn't sound like few but it sounds like no regions?

Ah, yes, it is left here from testing if the hash path is actually
working well ;)

There is quadratic path for case of few peers that don't have hash
overhead and non-quadratic hashtable version for many peers.
Typically there is one or two peers except for outermost region, so it
should make things generally cheaper.
> 
> > +     {
> > +       for (r1 = region; r1; r1 = r1->next_peer)
> > + 	{
> > + 	  if (r1->type == ERT_CATCH)
> > + 	    continue;
> > + 	  for (r2 = r1->next_peer; r2; r2 = next)
> > + 	    {
> > + 	      next = r2->next_peer;
> > + 	      if (eh_region_replaceable_by_p (r1, r2))
> > + 		{
> > + 		  replace_region (r1, r2);
> 
> Will relace_region (r1, r2) make the result of the n^2 loop
> incomplete?  Thus, can we ever expect more merges by iterating it?

No, one iteration should be enough.  Basically we walk for peers, look
if they are identical and merge them into the first representative.
Merging does not affect the peers themselves.
> 
> > + 		  merged = true;
> > + 		}
> > + 	    }
> > + 	}
> > +     }
> > +   else
> > +     {
> > +       htab_t hash;
> > +       hash = htab_create (num_regions, hash_eh_region,
> > + 			  eh_regions_equal_p, NULL);
> > +       for (r1 = region; r1; r1 = next)
> > + 	{
> > +           void **slot;
> > + 
> > + 	  next = r1->next_peer;
> > + 	  if (r1->type == ERT_CATCH)
> > + 	    continue;
> > + 	  slot = htab_find_slot (hash, r1, INSERT);
> > + 	  if (!*slot)
> > + 	    *slot = r1;
> > + 	  else
> > + 	    replace_region ((struct eh_region *)*slot, r1);
> > + 	}
> > +       htab_delete (hash);
> > +     }
> > +   for (r1 = region; r1; r1 = r1->next_peer)
> > +     merged |= merge_peers (r1->inner);
> 
> So the whole merge_peers operation is quadratic?  Would merging
> in different order (inner to outer) be any different?  Just
> fishing for better overall comments on this code ...

It is O(n) because of the hashtable version.  It is simple walk of
the tree from outermost to innermost always trying to find matching
regions on the same level.  We walk from outermost into
innermost because merging outer regions increase amount of sons of the
region and allow more merging of them.
> >   
> > + #ifdef ENABLE_CHECKING
> > +   verify_eh_tree (cfun);
> > + #endif
> 
> Can you restrict the eh tree verification to once before
> and once after ehcleanup, if changed?  Thanks.

Well, I would have to track if some removal, merging or updating happent
that is probably not worth the effort.  I guess I can simply drop
verify_eh_tree here.  I basically added this while I was debugging bug
that turned out to be actually bug in inliner producing invalid trees.

> >   int least_common_multiple (int, int);
> > + edge redirect_eh_edge (edge e, basic_block new_bb);
> 
> Put that into except.h instead.  It will also work for RTL EH edges,
> correct?  If not it should be called tree_redirect_eh_edge instead.

make_eh_edges and EH lowering defined in tree-eh.c is also in tree-flow.h
In general my understanding is that except.h is about the EH
datastructure manipulation + old RTX code.  But I have no problem
with moving both into except.h.

> >      langhooks.h insn-config.h hard-reg-set.h $(BASIC_BLOCK_H) output.h \
> >      dwarf2asm.h dwarf2out.h $(TOPLEV_H) $(HASHTAB_H) intl.h $(GGC_H) \
> >      gt-$(EXCEPT_H) $(CGRAPH_H) $(INTEGRATE_H) $(DIAGNOSTIC_H) dwarf2.h \
> > !    $(TARGET_H) $(TM_P_H) $(TREE_PASS_H) $(TIMEVAR_H) $(TREE_FLOW_H)
> 
> Then this should be not necessary (it's odd anyway).

I am including tree-flow.h in except.c because I need way to figure out
if region's tree_label belongs to BB we are redirecting from.
Since there can be multiple labels in gimple basic blocks, I am using
label_to_block function to test.

I could also make it to work on list of label declarations instead, that
would be probably neccesary if we wanted to make it work on RTL too.  In
general it should just work, but I am not convinced it is going to be
worth the effort to debug RTL land that makes various funny assumptions
about EH and abnormal edges.

Thanks a lot!
Honza