Re: [PATCH 1/2] ipa-cp: Better representation of aggregate values we clone for

[Jan Hubicka <hubicka@ucw.cz>]

> gcc/ChangeLog:
> 
> 2022-08-26  Martin Jambor  <mjambor@suse.cz>
> 
> 	* ipa-prop.h (IPA_PROP_ARG_INDEX_LIMIT_BITS): New.
> 	(ipcp_transformation): Added forward declaration.
> 	(ipa_argagg_value): New type.
> 	(ipa_argagg_value_list): New type.
> 	(ipa_agg_replacement_value): Removed type.
> 	(ipcp_transformation): Switch from using ipa_agg_replacement_value
> 	to ipa_argagg_value_list.
> 	(ipa_get_agg_replacements_for_node): Removed.
> 	(ipa_dump_agg_replacement_values): Removed declaration.
> 	* ipa-cp.cc: Include <algorithm>.
> 	(values_equal_for_ipcp_p): Moved up in the file.
> 	(ipa_argagg_value_list::dump): Likewise.
> 	(ipa_argagg_value_list::debug): Likewise.
> 	(ipa_argagg_value_list::get_elt): Likewise.
> 	(ipa_argagg_value_list::get_elt_for_index): Likewise.
> 	(ipa_argagg_value_list::get_value): New overloaded functions.
> 	(ipa_argagg_value_list::superset_of_p): New function.
> 	(new ipa_argagg_value_list::push_adjusted_values): Likewise.
> 	(push_agg_values_from_plats): Likewise.
> 	(intersect_argaggs_with): Likewise.
> 	(get_clone_agg_value): Removed.
> 	(ipa_agg_value_from_node): Make last parameter const, use
> 	ipa_argagg_value_list to search values coming from clones.
> 	(ipa_get_indirect_edge_target_1): Use ipa_argagg_value_list to search
> 	values coming from clones.
> 	(ipcp_discover_new_direct_edges): Pass around a vector of
> 	ipa_argagg_values rather than a link list of replacement values.
> 	(cgraph_edge_brings_value_p): Use ipa_argagg_value_list to search
> 	values coming from clones.
> 	(create_specialized_node): Work with a vector of ipa_argagg_values
> 	rather than a link list of replacement values.
> 	(self_recursive_agg_pass_through_p): Make the pointer parameters
> 	const.
> 	(copy_plats_to_inter): Removed.
> 	(intersect_with_plats): Likewise.
> 	(agg_replacements_to_vector): Likewise.
> 	(intersect_with_agg_replacements): Likewise.
> 	(intersect_aggregates_with_edge): Likewise.
> 	(push_agg_values_for_index_from_edge): Likewise.
> 	(push_agg_values_from_edge): Likewise.
> 	(find_aggregate_values_for_callers_subset): Rewrite.
> 	(cgraph_edge_brings_all_agg_vals_for_node): Likewise.
> 	(ipcp_val_agg_replacement_ok_p): Use ipa_argagg_value_list to search
> 	aggregate values.
> 	(decide_about_value): Work with a vector of ipa_argagg_values rather
> 	than a link list of replacement values.
> 	(decide_whether_version_node): Likewise.
> 	(ipa_analyze_node): Check number of parameters, assert that there
> 	are no descriptors when bailing out.
> 	* ipa-prop.cc (ipa_set_node_agg_value_chain): Switch to a vector of
> 	ipa_argagg_value.
> 	(ipa_node_params_t::duplicate): Removed superfluous handling of
> 	ipa_agg_replacement_values.  Name of src parameter removed because
> 	it is no longer used.
> 	(ipcp_transformation_t::duplicate): Replaced duplication of
> 	ipa_agg_replacement_values with copying vector m_agg_values.
> 	(ipa_dump_agg_replacement_values): Removed.
> 	(write_ipcp_transformation_info): Stream the new data-structure
> 	instead of the old.
> 	(read_ipcp_transformation_info): Likewise.
> 	(adjust_agg_replacement_values): Work with ipa_argagg_values instead
> 	of linked lists of ipa_agg_replacement_values, copy the items and
> 	truncate the vector as necessary to keep it sorted instead of marking
> 	items as invalid.  Return one bool if CFG should be updated.
> 	(ipcp_modif_dom_walker): Store ipcp_transformation instead of
> 	linked list of ipa_agg_replacement_values.
> 	(ipcp_modif_dom_walker::before_dom_children): Use
> 	ipa_argagg_value_list instead of walking a list of
> 	ipa_agg_replacement_values.
> 	(ipcp_transform_function): Switch to the new data structure, adjust
> 	dumping.
> 
> gcc/testsuite/ChangeLog:
> 
> 2022-08-15  Martin Jambor  <mjambor@suse.cz>
> 
> 	* gcc.dg/ipa/ipcp-agg-11.c: Adjust dumps.
> 	* gcc.dg/ipa/ipcp-agg-8.c: Likewise.
> ---
>  gcc/ipa-cp.cc                          | 1010 ++++++++++++------------
>  gcc/ipa-prop.cc                        |  254 +++---
>  gcc/ipa-prop.h                         |  139 +++-
>  gcc/testsuite/gcc.dg/ipa/ipcp-agg-11.c |    4 +-
>  gcc/testsuite/gcc.dg/ipa/ipcp-agg-8.c  |    4 +-
>  5 files changed, 736 insertions(+), 675 deletions(-)
> 
> diff --git a/gcc/ipa-cp.cc b/gcc/ipa-cp.cc
> index 543a9334e2c..024f8c06b5d 100644
> --- a/gcc/ipa-cp.cc
> +++ b/gcc/ipa-cp.cc
> @@ -127,6 +127,7 @@ along with GCC; see the file COPYING3.  If not see
>  #include "attribs.h"
>  #include "dbgcnt.h"
>  #include "symtab-clones.h"
> +#include <algorithm>
>  
>  template <typename valtype> class ipcp_value;
>  
> @@ -455,6 +456,26 @@ ipcp_lattice<valtype>::is_single_const ()
>      return true;
>  }
>  
> +/* Return true iff X and Y should be considered equal values by IPA-CP.  */
> +
> +static bool
> +values_equal_for_ipcp_p (tree x, tree y)
> +{
> +  gcc_checking_assert (x != NULL_TREE && y != NULL_TREE);
> +
> +  if (x == y)
> +    return true;
> +
> +  if (TREE_CODE (x) == ADDR_EXPR
> +      && TREE_CODE (y) == ADDR_EXPR
> +      && TREE_CODE (TREE_OPERAND (x, 0)) == CONST_DECL
> +      && TREE_CODE (TREE_OPERAND (y, 0)) == CONST_DECL)
> +    return operand_equal_p (DECL_INITIAL (TREE_OPERAND (x, 0)),
> +			    DECL_INITIAL (TREE_OPERAND (y, 0)), 0);

I wonder if we want to handle MEM_REFs here too? They get quite common
in IPA mode and I think we miss the fixup removing them here.
> +  else
> +    return operand_equal_p (x, y, 0);
> +/* Return the item describing a constant stored for INDEX at UNIT_OFFSET or
> +   NULL if there is no such constant.  */
> +
> +const ipa_argagg_value *
> +ipa_argagg_value_list::get_elt (int index, unsigned unit_offset) const
> +{
> +  ipa_argagg_value key;
> +  key.index = index;
> +  key.unit_offset = unit_offset;
> +  const ipa_argagg_value *res
> +    = std::lower_bound (m_elts.begin (), m_elts.end (), key,
> +			[] (const ipa_argagg_value &elt,
> +			    const ipa_argagg_value &val)
> +			{
> +			  if (elt.index < val.index)
> +			    return true;
> +			  if (elt.index > val.index)
> +			    return false;
> +			  if (elt.unit_offset < val.unit_offset)
> +			    return true;
> +			  return false;
> +			});
> +
> +  if (res == m_elts.end ()
> +      || res->index != index
> +      || res->unit_offset != unit_offset)
> +    res = nullptr;
> +
> +  /* TODO: perhaps remove after some extensive testing? */
> +  if (!flag_checking)
> +    return res;
> +
> +  const ipa_argagg_value *slow_res = NULL;
> +  int prev_index = -1;
> +  unsigned prev_unit_offset = 0;
> +  for (const ipa_argagg_value &av : m_elts)
> +    {
> +      gcc_assert (prev_index < 0
> +		  || prev_index < av.index
> +		  || prev_unit_offset < av.unit_offset);
> +      prev_index = av.index;
> +      prev_unit_offset = av.unit_offset;
> +      if (av.index == index
> +	  && av.unit_offset == unit_offset)
> +	slow_res = &av;
> +    }
> +  gcc_assert (res == slow_res);
So this is just checking that the std::lower_bound works as expected?
I am just curious if you expect it to break?
> +/* Turn all values that are not present in OTHER into NULL_TREEs.  Return the
> +   number of remaining valid entries.  */
> +
> +bool
> +ipa_argagg_value_list::superset_of_p (const ipa_argagg_value_list &other) const
It returns bool, so not number of entries.
> +/* Push into RES aggregate all stored aggregate values relating to parameter
> +   with SRC_INDEX as those relating to of DST_INDEX while subtracting
> +   UNIT_DELTA from the individual unit offsets.  */
> +
> +void
> +ipa_argagg_value_list::push_adjusted_values (unsigned src_index,
> +					     unsigned dest_index,
> +					     unsigned unit_delta,
> +					     vec<ipa_argagg_value> *res) const
> +{
> +  const ipa_argagg_value *av = get_elt_for_index (src_index);
> +  if (!av)
> +    return;
> +  unsigned prev_unit_offset = 0;
> +  bool first = true;
> +  for (; av < m_elts.end (); ++av)
> +    {
> +      if (av->index > src_index)
> +	return;
> +      if (av->index == src_index
> +	  && (av->unit_offset >= unit_delta)
> +	  && av->value)
> +	{
> +	  ipa_argagg_value new_av;
> +	  gcc_checking_assert (av->value);
> +	  new_av.value = av->value;
> +	  new_av.unit_offset = av->unit_offset - unit_delta;
> +	  new_av.index = dest_index;
> +	  new_av.by_ref = av->by_ref;
I am bit lost on what is going here, so perhaps a comment would help.
>  
> +class ipcp_transformation;
> +
> +/* Element of a vector describing aggregate values for a number of arguments in
> +   a particular context, be it a call or the aggregate constants that a node is
> +   specialized for.  */
> +
> +struct GTY(()) ipa_argagg_value
> +{
> +  /* The constant value.  In the contexts where the list of known values is
> +     being pruned, NULL means a variable value.  */
> +  tree value;
> +  /* Unit offset within the aggregate.  */
> +  unsigned unit_offset;
since this is 32bit, it makes me wonder if we have overflow checks (even
though greater than 4GB structures on stack are likely rare even today)
> +  /* Index of the parameter, as it was in the original function (i.e. needs
> +     remapping after parameter modification is carried out as part of clone
> +     materialization).  */
> +  unsigned index : IPA_PROP_ARG_INDEX_LIMIT_BITS;
> +  /* Whether the value was passed by reference.  */
> +  unsigned by_ref : 1;
> +};
> +
> +/* A view into a sorted list of aggregate values in a particular context, be it
> +   a call or the aggregate constants that a node is specialized for.  The
> +   actual data is stored in the vector this has been constructed from.  */
> +
> +class ipa_argagg_value_list
> +{
> +public:
> +  ipa_argagg_value_list () = delete;
> +  ipa_argagg_value_list (const vec<ipa_argagg_value, va_gc> *values)
> +    : m_elts (values)
> +  {}
> +  ipa_argagg_value_list (const vec<ipa_argagg_value> *values)
> +    : m_elts (*values)
> +  {}
> +  ipa_argagg_value_list (const ipcp_transformation *tinfo);
> +
> +  /* Return the aggregate constant stored for INDEX at UNIT_OFFSET, if it is
> +     passed by reference or not according to BY_REF, or NULL_TREE
> +     otherwise.  */
> +
> +  tree get_value (int index, unsigned unit_offset, bool by_ref) const;
> +
> +  /* Return the aggregate constant stored for INDEX at UNIT_OFFSET, not
> +     performing any check of whether value is passed by reference.  Return
> +     NULL_TREE if there is no such constant.  */
> +
> +  tree get_value (int index, unsigned unit_offset) const;
> +
> +  /* Return the item describing a constant stored for INDEX at UNIT_OFFSET or
> +     NULL if there is no such constant.  */
> +
> +  const ipa_argagg_value *get_elt (int index, unsigned unit_offset) const;
> +
> +  /* Return the first item describing a constant stored for parameter with
> +     INDEX, regardless of offset or reference, or NULL if there is no such
> +     constant.  */
> +
> +  const ipa_argagg_value *get_elt_for_index (int index) const;
> +
> +  /* Return true if all elements present in OTHER are also present in this
> +     class.  */
> +
> +  bool superset_of_p (const ipa_argagg_value_list &other) const;
> +
> +  /* Push into RES aggregate all stored aggregate values relating to parameter
> +     with SRC_INDEX as those relating to of DST_INDEX while subtracting
> +     UNIT_DELTA from the individual unit offsets.  */
> +
> +  void push_adjusted_values (unsigned src_index, unsigned dest_index,
> +			     unsigned unit_delta,
> +			     vec<ipa_argagg_value> *res) const;
> +
> +  /* Dump aggregate constants to FILE.  */
> +
> +  void dump (FILE *f);
> +
> +  /* Dump aggregate constants to stderr.  */
> +
DEBUG_FUNCTION here.
> +  void debug ();
> +
> +  /* Array slice pointing to the actual storage.  */
> +
> +  array_slice<const ipa_argagg_value> m_elts;
> +};
> +

Patch is OK with those changes.
Thanks,
Honza