This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Re: pretty-ipa merge 16: EH redirection
On Sat, 25 Apr 2009, Jan Hubicka wrote:
> >
> > 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.
Ok, you can then disregard my last two comments.
Richard.