Re: [PATCH 4/6] Port ipa-cp to use cgraph_edge summary.

[Martin Jambor <mjambor at suse dot cz>]

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