| Message ID | e96d4e603f04b7fb458ddfff143514e1688a91ee.1436438929.git.mliska@suse.cz |
|---|---|
| State | New |
| Headers | show |
On 07/09/2015 03:13 AM, mliska wrote: > gcc/ChangeLog: > > 2015-07-03 Martin Liska <mliska@suse.cz> > > * ipa-cp.c (struct edge_clone_summary): New structure. > (class edge_clone_summary_t): Likewise. > (edge_clone_summary_t::initialize): New method. > (edge_clone_summary_t::duplicate): Likewise. > (get_next_cgraph_edge_clone): Remove. > (get_info_about_necessary_edges): Refactor using the new > data structure. > (gather_edges_for_value): Likewise. > (perhaps_add_new_callers): Likewise. > (ipcp_driver): Allocate and deallocate newly added > instance. > --- OK. Jeff
Hi, I know the patch has been approved by Jeff, but please do not commit it before considering the following: On Thu, Jul 09, 2015 at 11:13:53AM +0200, Martin Liska wrote: > gcc/ChangeLog: > > 2015-07-03 Martin Liska <mliska@suse.cz> > > * ipa-cp.c (struct edge_clone_summary): New structure. > (class edge_clone_summary_t): Likewise. > (edge_clone_summary_t::initialize): New method. > (edge_clone_summary_t::duplicate): Likewise. > (get_next_cgraph_edge_clone): Remove. > (get_info_about_necessary_edges): Refactor using the new > data structure. > (gather_edges_for_value): Likewise. > (perhaps_add_new_callers): Likewise. > (ipcp_driver): Allocate and deallocate newly added > instance. > --- > gcc/ipa-cp.c | 198 ++++++++++++++++++++++++++++++++++------------------------- > 1 file changed, 113 insertions(+), 85 deletions(-) > > diff --git a/gcc/ipa-cp.c b/gcc/ipa-cp.c > index 16b9cde..8a50b63 100644 > --- a/gcc/ipa-cp.c > +++ b/gcc/ipa-cp.c > @@ -2888,54 +2888,79 @@ ipcp_discover_new_direct_edges (struct cgraph_node *node, > inline_update_overall_summary (node); > } > > -/* Vector of pointers which for linked lists of clones of an original crgaph > - edge. */ > +/* Edge clone summary. */ > > -static vec<cgraph_edge *> next_edge_clone; > -static vec<cgraph_edge *> prev_edge_clone; > - > -static inline void > -grow_edge_clone_vectors (void) > +struct edge_clone_summary I's got constructors and destructors so it should be a class, reaally. > { > - if (next_edge_clone.length () > - <= (unsigned) symtab->edges_max_uid) > - next_edge_clone.safe_grow_cleared (symtab->edges_max_uid + 1); > - if (prev_edge_clone.length () > - <= (unsigned) symtab->edges_max_uid) > - prev_edge_clone.safe_grow_cleared (symtab->edges_max_uid + 1); > -} > + /* Default constructor. */ > + edge_clone_summary (): edge_set (NULL), edge (NULL) {} > > -/* Edge duplication hook to grow the appropriate linked list in > - next_edge_clone. */ > + /* Default destructor. */ > + ~edge_clone_summary () > + { > + gcc_assert (edge_set != NULL); > > -static void > -ipcp_edge_duplication_hook (struct cgraph_edge *src, struct cgraph_edge *dst, > - void *) > + if (edge != NULL) > + { > + gcc_checking_assert (edge_set->contains (edge)); > + edge_set->remove (edge); > + } > + > + /* Release memory for an empty set. */ > + if (edge_set->elements () == 0) > + delete edge_set; > + } > + > + hash_set <cgraph_edge *> *edge_set; > + cgraph_edge *edge; If the hash set is supposed to replace the linked list of edge clones, then a removal mechanism seems to be missing. The whole point of prev_edge_clone vector was to allow removal of edges from the linked list, because as speculative edges are thrown away, clones can be too and then we must remove the pointer from the list, or hash set. Have you tried -O3 LTOing Firefox with these changes? But I must say that I'm not convinced that converting the linked list into a hash_set is a good idea at all. Apart from the self-removal operation, the lists are always traversed linearly and in full, so except for using a C++-style iterator, I really do not see any point. Moreover, you seem to create a hash table for each and every edge, even when it has no clones, just to be able to enter the edge itself into it, and so not skip it when you iterate over all clones. That really seems like unjustifiable overhead. And the deletion in duplication hook is also very unappealing. So the bottom line is that while I like turning the two vectors into a summary, I do not like the hash set at all. If absolutely think it is a good idea, please make that change in a separate patch so that we can better argue about its merits. On the other hand, since the summaries are hash-based themselves, it would be great if they had a predicate to find out whether there is any summary for a given edge at all and have get_next_cgraph_edge_clone return false if there was none. That would actually save memory. Thanks, Martin
On 07/10/2015 04:18 PM, Martin Jambor wrote: > Hi, > > I know the patch has been approved by Jeff, but please do not commit > it before considering the following: > > On Thu, Jul 09, 2015 at 11:13:53AM +0200, Martin Liska wrote: >> gcc/ChangeLog: >> >> 2015-07-03 Martin Liska <mliska@suse.cz> >> >> * ipa-cp.c (struct edge_clone_summary): New structure. >> (class edge_clone_summary_t): Likewise. >> (edge_clone_summary_t::initialize): New method. >> (edge_clone_summary_t::duplicate): Likewise. >> (get_next_cgraph_edge_clone): Remove. >> (get_info_about_necessary_edges): Refactor using the new >> data structure. >> (gather_edges_for_value): Likewise. >> (perhaps_add_new_callers): Likewise. >> (ipcp_driver): Allocate and deallocate newly added >> instance. >> --- >> gcc/ipa-cp.c | 198 ++++++++++++++++++++++++++++++++++------------------------- >> 1 file changed, 113 insertions(+), 85 deletions(-) >> >> diff --git a/gcc/ipa-cp.c b/gcc/ipa-cp.c >> index 16b9cde..8a50b63 100644 >> --- a/gcc/ipa-cp.c >> +++ b/gcc/ipa-cp.c >> @@ -2888,54 +2888,79 @@ ipcp_discover_new_direct_edges (struct cgraph_node *node, >> inline_update_overall_summary (node); >> } >> >> -/* Vector of pointers which for linked lists of clones of an original crgaph >> - edge. */ >> +/* Edge clone summary. */ >> >> -static vec<cgraph_edge *> next_edge_clone; >> -static vec<cgraph_edge *> prev_edge_clone; >> - >> -static inline void >> -grow_edge_clone_vectors (void) >> +struct edge_clone_summary > > I's got constructors and destructors so it should be a class, reaally. > >> { >> - if (next_edge_clone.length () >> - <= (unsigned) symtab->edges_max_uid) >> - next_edge_clone.safe_grow_cleared (symtab->edges_max_uid + 1); >> - if (prev_edge_clone.length () >> - <= (unsigned) symtab->edges_max_uid) >> - prev_edge_clone.safe_grow_cleared (symtab->edges_max_uid + 1); >> -} >> + /* Default constructor. */ >> + edge_clone_summary (): edge_set (NULL), edge (NULL) {} >> >> -/* Edge duplication hook to grow the appropriate linked list in >> - next_edge_clone. */ >> + /* Default destructor. */ >> + ~edge_clone_summary () >> + { >> + gcc_assert (edge_set != NULL); >> >> -static void >> -ipcp_edge_duplication_hook (struct cgraph_edge *src, struct cgraph_edge *dst, >> - void *) >> + if (edge != NULL) >> + { >> + gcc_checking_assert (edge_set->contains (edge)); >> + edge_set->remove (edge); >> + } >> + >> + /* Release memory for an empty set. */ >> + if (edge_set->elements () == 0) >> + delete edge_set; >> + } >> + >> + hash_set <cgraph_edge *> *edge_set; >> + cgraph_edge *edge; > > If the hash set is supposed to replace the linked list of edge clones, > then a removal mechanism seems to be missing. The whole point of > prev_edge_clone vector was to allow removal of edges from the linked > list, because as speculative edges are thrown away, clones can be too > and then we must remove the pointer from the list, or hash set. > > Have you tried -O3 LTOing Firefox with these changes? > > But I must say that I'm not convinced that converting the linked list > into a hash_set is a good idea at all. Apart from the self-removal > operation, the lists are always traversed linearly and in full, so > except for using a C++-style iterator, I really do not see any point. > > Moreover, you seem to create a hash table for each and every edge, > even when it has no clones, just to be able to enter the edge itself > into it, and so not skip it when you iterate over all clones. That > really seems like unjustifiable overhead. And the deletion in > duplication hook is also very unappealing. So the bottom line is that > while I like turning the two vectors into a summary, I do not like the > hash set at all. If absolutely think it is a good idea, please make > that change in a separate patch so that we can better argue about its > merits. > > On the other hand, since the summaries are hash-based themselves, it > would be great if they had a predicate to find out whether there is > any summary for a given edge at all and have get_next_cgraph_edge_clone > return false if there was none. That would actually save memory. > > Thanks, > > Martin > After a discussion with Martin, we made a decision to preserve current implementation and not to port the IPA CP to he newly introduced summary. Martin
diff --git a/gcc/ipa-cp.c b/gcc/ipa-cp.c index 16b9cde..8a50b63 100644 --- a/gcc/ipa-cp.c +++ b/gcc/ipa-cp.c @@ -2888,54 +2888,79 @@ ipcp_discover_new_direct_edges (struct cgraph_node *node, inline_update_overall_summary (node); } -/* Vector of pointers which for linked lists of clones of an original crgaph - edge. */ +/* Edge clone summary. */ -static vec<cgraph_edge *> next_edge_clone; -static vec<cgraph_edge *> prev_edge_clone; - -static inline void -grow_edge_clone_vectors (void) +struct edge_clone_summary { - if (next_edge_clone.length () - <= (unsigned) symtab->edges_max_uid) - next_edge_clone.safe_grow_cleared (symtab->edges_max_uid + 1); - if (prev_edge_clone.length () - <= (unsigned) symtab->edges_max_uid) - prev_edge_clone.safe_grow_cleared (symtab->edges_max_uid + 1); -} + /* Default constructor. */ + edge_clone_summary (): edge_set (NULL), edge (NULL) {} -/* Edge duplication hook to grow the appropriate linked list in - next_edge_clone. */ + /* Default destructor. */ + ~edge_clone_summary () + { + gcc_assert (edge_set != NULL); -static void -ipcp_edge_duplication_hook (struct cgraph_edge *src, struct cgraph_edge *dst, - void *) + if (edge != NULL) + { + gcc_checking_assert (edge_set->contains (edge)); + edge_set->remove (edge); + } + + /* Release memory for an empty set. */ + if (edge_set->elements () == 0) + delete edge_set; + } + + hash_set <cgraph_edge *> *edge_set; + cgraph_edge *edge; +}; + +class edge_clone_summary_t: + public edge_summary <edge_clone_summary *> { - grow_edge_clone_vectors (); +public: + edge_clone_summary_t (symbol_table *symtab): + edge_summary <edge_clone_summary *> (symtab) {} + + virtual void initialize (cgraph_edge *edge, edge_clone_summary *data); + virtual void duplicate (cgraph_edge *src_edge, cgraph_edge *dst_edge, + edge_clone_summary *src_data, + edge_clone_summary *dst_data); +}; - struct cgraph_edge *old_next = next_edge_clone[src->uid]; - if (old_next) - prev_edge_clone[old_next->uid] = dst; - prev_edge_clone[dst->uid] = src; +static edge_summary <edge_clone_summary *> *edge_clone_summaries = NULL; + +void +edge_clone_summary_t::initialize (cgraph_edge *edge, edge_clone_summary *data) +{ + gcc_checking_assert (data->edge_set == NULL); - next_edge_clone[dst->uid] = old_next; - next_edge_clone[src->uid] = dst; + data->edge_set = new hash_set <cgraph_edge *> (); + data->edge_set->add (edge); + data->edge = edge; } -/* Hook that is called by cgraph.c when an edge is removed. */ +/* Edge duplication hook. */ -static void -ipcp_edge_removal_hook (struct cgraph_edge *cs, void *) +void +edge_clone_summary_t::duplicate (cgraph_edge *src_edge, cgraph_edge *dst_edge, + edge_clone_summary *src_data, + edge_clone_summary *dst_data) { - grow_edge_clone_vectors (); - - struct cgraph_edge *prev = prev_edge_clone[cs->uid]; - struct cgraph_edge *next = next_edge_clone[cs->uid]; - if (prev) - next_edge_clone[prev->uid] = next; - if (next) - prev_edge_clone[next->uid] = prev; + dst_data->edge = dst_edge; + if (src_data->edge_set == NULL) + { + src_data->edge_set = new hash_set <cgraph_edge *> (); + src_data->edge_set->add (src_edge); + } + + src_data->edge_set->add (dst_edge); + + /* As ::initialize processes an allocation, we have to release previous + edge_set. */ + delete dst_data->edge_set; + + dst_data->edge_set = src_data->edge_set; } /* See if NODE is a clone with a known aggregate value at a given OFFSET of a @@ -3050,14 +3075,6 @@ cgraph_edge_brings_value_p (cgraph_edge *cs, plats->ctxlat.values->value); } -/* Get the next clone in the linked list of clones of an edge. */ - -static inline struct cgraph_edge * -get_next_cgraph_edge_clone (struct cgraph_edge *cs) -{ - return next_edge_clone[cs->uid]; -} - /* Given VAL that is intended for DEST, iterate over all its sources and if they still hold, add their edge frequency and their number into *FREQUENCY and *CALLER_COUNT respectively. */ @@ -3075,18 +3092,23 @@ get_info_about_necessary_edges (ipcp_value<valtype> *val, cgraph_node *dest, for (src = val->sources; src; src = src->next) { - struct cgraph_edge *cs = src->cs; - while (cs) - { - if (cgraph_edge_brings_value_p (cs, src, dest)) + cgraph_edge *cs = src->cs; + + edge_clone_summary *s = edge_clone_summaries->get (cs); + if (s->edge_set != NULL) + for (hash_set <cgraph_edge *>::iterator it = s->edge_set->begin (); + it != s->edge_set->end (); ++it) + { + cs = *it; + + if (cgraph_edge_brings_value_p (cs, src, dest)) { count++; freq += cs->frequency; cnt += cs->count; hot |= cs->maybe_hot_p (); } - cs = get_next_cgraph_edge_clone (cs); - } + } } *freq_sum = freq; @@ -3109,13 +3131,16 @@ gather_edges_for_value (ipcp_value<valtype> *val, cgraph_node *dest, ret.create (caller_count); for (src = val->sources; src; src = src->next) { - struct cgraph_edge *cs = src->cs; - while (cs) - { - if (cgraph_edge_brings_value_p (cs, src, dest)) - ret.quick_push (cs); - cs = get_next_cgraph_edge_clone (cs); - } + cgraph_edge *cs = src->cs; + edge_clone_summary *s = edge_clone_summaries->get (cs); + if (s->edge_set != NULL) + for (hash_set <cgraph_edge *>::iterator it = s->edge_set->begin (); + it != s->edge_set->end (); ++it) + { + cs = *it; + if (cgraph_edge_brings_value_p (cs, src, dest)) + ret.quick_push (cs); + } } return ret; @@ -3971,25 +3996,35 @@ perhaps_add_new_callers (cgraph_node *node, ipcp_value<valtype> *val) for (src = val->sources; src; src = src->next) { struct cgraph_edge *cs = src->cs; - while (cs) + + edge_clone_summary *s = edge_clone_summaries->get (cs); + if (s->edge_set != NULL) { - if (cgraph_edge_brings_value_p (cs, src, node) - && cgraph_edge_brings_all_scalars_for_node (cs, val->spec_node) - && cgraph_edge_brings_all_agg_vals_for_node (cs, val->spec_node)) + for (hash_set <cgraph_edge *>::iterator it = s->edge_set->begin (); + it != s->edge_set->end (); ++it) { - if (dump_file) - fprintf (dump_file, " - adding an extra caller %s/%i" - " of %s/%i\n", - xstrdup_for_dump (cs->caller->name ()), - cs->caller->order, - xstrdup_for_dump (val->spec_node->name ()), - val->spec_node->order); - - cs->redirect_callee_duplicating_thunks (val->spec_node); - val->spec_node->expand_all_artificial_thunks (); - redirected_sum += cs->count; + cgraph_edge *cs = *it; + + if (cgraph_edge_brings_value_p (cs, src, node) + && cgraph_edge_brings_all_scalars_for_node (cs, + val->spec_node) + && cgraph_edge_brings_all_agg_vals_for_node (cs, + val->spec_node)) + { + if (dump_file) + fprintf (dump_file, " - adding an extra caller %s/%i" + " of %s/%i\n", + xstrdup_for_dump (cs->caller->name ()), + cs->caller->order, + xstrdup_for_dump (val->spec_node->name ()), + val->spec_node->order); + + cs->redirect_callee_duplicating_thunks (val->spec_node); + val->spec_node->expand_all_artificial_thunks (); + redirected_sum += cs->count; + + } } - cs = get_next_cgraph_edge_clone (cs); } } @@ -4441,17 +4476,13 @@ ipcp_store_alignment_results (void) static unsigned int ipcp_driver (void) { - struct cgraph_2edge_hook_list *edge_duplication_hook_holder; - struct cgraph_edge_hook_list *edge_removal_hook_holder; struct ipa_topo_info topo; + if (edge_clone_summaries == NULL) + edge_clone_summaries = new edge_clone_summary_t (symtab); + ipa_check_create_node_params (); ipa_check_create_edge_args (); - grow_edge_clone_vectors (); - edge_duplication_hook_holder = - symtab->add_edge_duplication_hook (&ipcp_edge_duplication_hook, NULL); - edge_removal_hook_holder = - symtab->add_edge_removal_hook (&ipcp_edge_removal_hook, NULL); if (dump_file) { @@ -4472,10 +4503,7 @@ ipcp_driver (void) /* Free all IPCP structures. */ free_toporder_info (&topo); - next_edge_clone.release (); - prev_edge_clone.release (); - symtab->remove_edge_removal_hook (edge_removal_hook_holder); - symtab->remove_edge_duplication_hook (edge_duplication_hook_holder); + delete edge_clone_summaries; ipa_free_all_structures_after_ipa_cp (); if (dump_file) fprintf (dump_file, "\nIPA constant propagation end\n");