[PR78365] ICE in determine_value_range, at tree-ssa-loo p-niter.c:413

Hi,

On Fri, Dec 09, 2016 at 01:18:25PM +0100, Richard Biener wrote:
> 
> The patch looks somewhat backward.  It populates the param type from
> the callee but the only thing we really know is the _originating_ type
> from the callers DECL_ARGUMENTS (if the JF is based on a parameter
> which is the only case where we do not know the type of the actual
> value statically -- we only know the type we expect).
> 
> So the type would be present only on IPA_JF_PASS_THROUGH JFs
> (? does that also cover modified params?).
> 
> At propagation time when applying the jump-function we have to make
> sure to first convert the actual parameter value to that expected type
> (or drop to BOTTOM if we can't do that conversion due to excess mismatches).
> 

I wanted to have a look at this myself for some time but the omp-low
splitting took far more time than I had anticipated and so it took my
until yesterday evening to come up with "my fix" which you can find
below.  It has the added benefit of also fixing PR 78599.

The patch removes the LTO WPA attempt to figure out types of actual
arguments from TYPE_ARG_TYPES and instead it adds streaming them into
node summaries, i.e. they come from the compile time unit with the
actual function definition (as opposed to the information we have at
call-sites when building jump functions).

Because in various corner cases and plain-garbage-code cases the types
of the actual and formal arguments can be quite different, especially
with LTO, I have reorganized propagate_vr_accross_jump_function so
that it uses extract_range_from_unary_expr in all but the
IPA_JF_PASS_THROUGH cases, because those rely on fold_convert.

In order to have all the information for
extract_range_from_unary_expr, I needed to stream also the type of the
actual argument, which hitherto we did not have for the cases when the
jump function was IPA_JF_UNKNOWN but still had vr_known set (and thus
did contain any info for constant propagation but still some info
about VR).  I am not happy about adding another field to this data
structure but at this point see not way around it.

Perhaps propagate_vr_accross_jump_function can now be simplified
further, running extract_range_from_unary_expr pretty much always (or
only when the types are not useless_type_conversion_p).  But I think I
should post what I have now.  The patch passes bootstrap, lto-boostrap
(of C, C++ and Fortran) and testing on x86_64-linux.

What do you think?

Martin

2016-12-13  Martin Jambor  <mjambor@suse.cz>

	PR ipa/78365
	* ipa-prop.h (ipa_jump_func): New field pased_type.
	* ipa-cp.c (ipa_vr_operation_and_type_effects): New function.
	(propagate_vr_accross_jump_function): Use the above function for all
	value range computations for pass-through jump functions and type
	converasion from explicit value range values.
	(ipcp_propagate_stage): Do not attempt to deduce types of formal
	parameters from TYPE_ARG_TYPES.
	* ipa-prop.c (ipa_compute_jump_functions_for_edge): Set
	jfunc->passed_type whenever setting jfunc->vr_known to true.
	(ipa_write_jump_function): Remove trailing whitespace, stream
	passed_type.
	(ipa_read_jump_function): Stream passed_type.
	(ipa_write_node_info): Stream type of the actual argument.
	(ipa_read_node_info): Likewise. Also remove trailing whitespace.

testsuite/
	* gcc.dg/torture/pr78365.c: New test.
---
 gcc/ipa-cp.c                           | 70 +++++++++++++++++-----------------
 gcc/ipa-prop.c                         | 22 ++++++++---
 gcc/ipa-prop.h                         |  3 ++
 gcc/testsuite/gcc.dg/torture/pr78365.c | 21 ++++++++++
 4 files changed, 75 insertions(+), 41 deletions(-)
 create mode 100644 gcc/testsuite/gcc.dg/torture/pr78365.c

On Wed, Dec 14, 2016 at 11:15 AM, Martin Jambor <mjambor@suse.cz> wrote:
> Hi,
>
> On Fri, Dec 09, 2016 at 01:18:25PM +0100, Richard Biener wrote:
>>
>> The patch looks somewhat backward.  It populates the param type from
>> the callee but the only thing we really know is the _originating_ type
>> from the callers DECL_ARGUMENTS (if the JF is based on a parameter
>> which is the only case where we do not know the type of the actual
>> value statically -- we only know the type we expect).
>>
>> So the type would be present only on IPA_JF_PASS_THROUGH JFs
>> (? does that also cover modified params?).
>>
>> At propagation time when applying the jump-function we have to make
>> sure to first convert the actual parameter value to that expected type
>> (or drop to BOTTOM if we can't do that conversion due to excess mismatches).
>>
>
> I wanted to have a look at this myself for some time but the omp-low
> splitting took far more time than I had anticipated and so it took my
> until yesterday evening to come up with "my fix" which you can find
> below.  It has the added benefit of also fixing PR 78599.
>
> The patch removes the LTO WPA attempt to figure out types of actual
> arguments from TYPE_ARG_TYPES and instead it adds streaming them into
> node summaries, i.e. they come from the compile time unit with the
> actual function definition (as opposed to the information we have at
> call-sites when building jump functions).
>
> Because in various corner cases and plain-garbage-code cases the types
> of the actual and formal arguments can be quite different, especially
> with LTO, I have reorganized propagate_vr_accross_jump_function so
> that it uses extract_range_from_unary_expr in all but the
> IPA_JF_PASS_THROUGH cases, because those rely on fold_convert.
>
> In order to have all the information for
> extract_range_from_unary_expr, I needed to stream also the type of the
> actual argument, which hitherto we did not have for the cases when the
> jump function was IPA_JF_UNKNOWN but still had vr_known set (and thus
> did contain any info for constant propagation but still some info
> about VR).  I am not happy about adding another field to this data
> structure but at this point see not way around it.
>
> Perhaps propagate_vr_accross_jump_function can now be simplified
> further, running extract_range_from_unary_expr pretty much always (or
> only when the types are not useless_type_conversion_p).  But I think I
> should post what I have now.  The patch passes bootstrap, lto-boostrap
> (of C, C++ and Fortran) and testing on x86_64-linux.
>
> What do you think?
>
> Martin
>
> 2016-12-13  Martin Jambor  <mjambor@suse.cz>
>
>         PR ipa/78365
>         * ipa-prop.h (ipa_jump_func): New field pased_type.
>         * ipa-cp.c (ipa_vr_operation_and_type_effects): New function.
>         (propagate_vr_accross_jump_function): Use the above function for all
>         value range computations for pass-through jump functions and type
>         converasion from explicit value range values.
>         (ipcp_propagate_stage): Do not attempt to deduce types of formal
>         parameters from TYPE_ARG_TYPES.
>         * ipa-prop.c (ipa_compute_jump_functions_for_edge): Set
>         jfunc->passed_type whenever setting jfunc->vr_known to true.
>         (ipa_write_jump_function): Remove trailing whitespace, stream
>         passed_type.
>         (ipa_read_jump_function): Stream passed_type.
>         (ipa_write_node_info): Stream type of the actual argument.
>         (ipa_read_node_info): Likewise. Also remove trailing whitespace.
>
> testsuite/
>         * gcc.dg/torture/pr78365.c: New test.
> ---
>  gcc/ipa-cp.c                           | 70 +++++++++++++++++-----------------
>  gcc/ipa-prop.c                         | 22 ++++++++---
>  gcc/ipa-prop.h                         |  3 ++
>  gcc/testsuite/gcc.dg/torture/pr78365.c | 21 ++++++++++
>  4 files changed, 75 insertions(+), 41 deletions(-)
>  create mode 100644 gcc/testsuite/gcc.dg/torture/pr78365.c
>
> diff --git a/gcc/ipa-cp.c b/gcc/ipa-cp.c
> index 4ec7cc5..7e6fc9a 100644
> --- a/gcc/ipa-cp.c
> +++ b/gcc/ipa-cp.c
> @@ -1839,6 +1839,23 @@ propagate_bits_accross_jump_function (cgraph_edge *cs, int idx, ipa_jump_func *j
>      return dest_lattice->set_to_bottom ();
>  }
>
> +/* Emulate effects of unary OPERATION and/or conversion from SRC_TYPE to
> +   DST_TYPE on value range in SRC_VR and store it to DST_VR.  Return true if
> +   the result is a range or an anti-range.  */
> +
> +static bool
> +ipa_vr_operation_and_type_effects (value_range *dst_vr, value_range *src_vr,
> +                                  enum tree_code operation,
> +                                  tree dst_type, tree src_type)
> +{
> +  memset (dst_vr, 0, sizeof (*dst_vr));

The memset is not necessary.

> +  extract_range_from_unary_expr (dst_vr, operation, dst_type, src_vr, src_type);
> +  if (dst_vr->type == VR_RANGE || dst_vr->type == VR_ANTI_RANGE)
> +    return true;
> +  else
> +    return false;
> +}
> +
>  /* Propagate value range across jump function JFUNC that is associated with
>     edge CS with param of callee of PARAM_TYPE and update DEST_PLATS
>     accordingly.  */
> @@ -1849,7 +1866,6 @@ propagate_vr_accross_jump_function (cgraph_edge *cs,
>                                     struct ipcp_param_lattices *dest_plats,
>                                     tree param_type)
>  {
> -  struct ipcp_param_lattices *src_lats;
>    ipcp_vr_lattice *dest_lat = &dest_plats->m_value_range;
>
>    if (dest_lat->bottom_p ())
> @@ -1862,31 +1878,23 @@ propagate_vr_accross_jump_function (cgraph_edge *cs,
>
>    if (jfunc->type == IPA_JF_PASS_THROUGH)
>      {
> -      struct ipa_node_params *caller_info = IPA_NODE_REF (cs->caller);
> -      int src_idx = ipa_get_jf_pass_through_formal_id (jfunc);
> -      src_lats = ipa_get_parm_lattices (caller_info, src_idx);
> +      enum tree_code operation = ipa_get_jf_pass_through_operation (jfunc);
>
> -      if (ipa_get_jf_pass_through_operation (jfunc) == NOP_EXPR)
> -       return dest_lat->meet_with (src_lats->m_value_range);
> -      else if (param_type
> -              && (TREE_CODE_CLASS (ipa_get_jf_pass_through_operation (jfunc))
> -                  == tcc_unary))
> +      if (TREE_CODE_CLASS (operation) == tcc_unary)
>         {
> -         value_range vr;
> -         memset (&vr, 0, sizeof (vr));
> +         struct ipa_node_params *caller_info = IPA_NODE_REF (cs->caller);
> +         int src_idx = ipa_get_jf_pass_through_formal_id (jfunc);
>           tree operand_type = ipa_get_type (caller_info, src_idx);
> -         enum tree_code operation = ipa_get_jf_pass_through_operation (jfunc);
> +         struct ipcp_param_lattices *src_lats
> +           = ipa_get_parm_lattices (caller_info, src_idx);
>
>           if (src_lats->m_value_range.bottom_p ())
>             return dest_lat->set_to_bottom ();
> -
> -         extract_range_from_unary_expr (&vr,
> -                                        operation,
> -                                        param_type,
> -                                        &src_lats->m_value_range.m_vr,
> -                                        operand_type);
> -         if (vr.type == VR_RANGE
> -             || vr.type == VR_ANTI_RANGE)
> +         value_range vr;
> +         if (ipa_vr_operation_and_type_effects (&vr,
> +                                                &src_lats->m_value_range.m_vr,
> +                                                operation, param_type,
> +                                                operand_type))
>             return dest_lat->meet_with (&vr);
>         }
>      }
> @@ -1906,8 +1914,11 @@ propagate_vr_accross_jump_function (cgraph_edge *cs,
>         }
>      }
>
> -  if (jfunc->vr_known)
> -    return dest_lat->meet_with (&jfunc->m_vr);
> +  value_range vr;
> +  if (jfunc->vr_known
> +      && ipa_vr_operation_and_type_effects (&vr, &jfunc->m_vr, NOP_EXPR,
> +                                           param_type, jfunc->passed_type))

but instead of a new jfunc->passed_type you can use TREE_TYPE (jfunc->m_vr.min)
for example.

I notice that ipa_jump_func is badly laid out:

struct GTY (()) ipa_jump_func
{
  /* Aggregate contants description.  See struct ipa_agg_jump_function and its
     description.  */
  struct ipa_agg_jump_function agg;

  /* Information about zero/non-zero bits.  */
  struct ipa_bits bits;

  /* Information about value range.  */
  bool vr_known;
  value_range m_vr;

  enum jump_func_type type;
  /* Represents a value of a jump function.  pass_through is used only in jump
     function context.  constant represents the actual constant in constant jump
     functions and member_cst holds constant c++ member functions.  */
  union jump_func_value
  {
    struct ipa_constant_data GTY ((tag ("IPA_JF_CONST"))) constant;
    struct ipa_pass_through_data GTY ((tag ("IPA_JF_PASS_THROUGH")))
pass_through;
    struct ipa_ancestor_jf_data GTY ((tag ("IPA_JF_ANCESTOR"))) ancestor;
  } GTY ((desc ("%1.type"))) value;
};

vr_known should be moved to pack with type.  and ipa_bits::known
should be moved out
of it as well.  I also think we do not use the equiv member of m_vr
and thus that is a waste.

Not sure if memory use of this struct is an issue.

Richard.

> +    return dest_lat->meet_with (&vr);
>    else
>      return dest_lat->set_to_bottom ();
>  }
> @@ -2247,7 +2258,7 @@ propagate_constants_accross_call (struct cgraph_edge *cs)
>      {
>        struct ipa_jump_func *jump_func = ipa_get_ith_jump_func (args, i);
>        struct ipcp_param_lattices *dest_plats;
> -      tree param_type = ipa_get_callee_param_type (cs, i);
> +      tree param_type = ipa_get_type (callee_info, i);
>
>        dest_plats = ipa_get_parm_lattices (callee_info, i);
>        if (availability == AVAIL_INTERPOSABLE)
> @@ -3234,19 +3245,6 @@ ipcp_propagate_stage (struct ipa_topo_info *topo)
>    {
>      struct ipa_node_params *info = IPA_NODE_REF (node);
>
> -    /* In LTO we do not have PARM_DECLs but we would still like to be able to
> -       look at types of parameters.  */
> -    if (in_lto_p)
> -      {
> -       tree t = TYPE_ARG_TYPES (TREE_TYPE (node->decl));
> -       for (int k = 0; k < ipa_get_param_count (info) && t; k++)
> -         {
> -           gcc_assert (t != void_list_node);
> -           info->descriptors[k].decl_or_type = TREE_VALUE (t);
> -           t = t ? TREE_CHAIN (t) : NULL;
> -         }
> -      }
> -
>      determine_versionability (node, info);
>      if (node->has_gimple_body_p ())
>        {
> diff --git a/gcc/ipa-prop.c b/gcc/ipa-prop.c
> index 642111d..123d422 100644
> --- a/gcc/ipa-prop.c
> +++ b/gcc/ipa-prop.c
> @@ -1751,6 +1751,7 @@ ipa_compute_jump_functions_for_edge (struct ipa_func_body_info *fbi,
>               jfunc->m_vr.min = build_int_cst (TREE_TYPE (arg), 0);
>               jfunc->m_vr.max = build_int_cst (TREE_TYPE (arg), 0);
>               jfunc->m_vr.equiv = NULL;
> +             jfunc->passed_type = TREE_TYPE (arg);
>             }
>           else
>             gcc_assert (!jfunc->vr_known);
> @@ -1776,7 +1777,10 @@ ipa_compute_jump_functions_for_edge (struct ipa_func_body_info *fbi,
>                                              &vr, TREE_TYPE (arg));
>               if (jfunc->m_vr.type == VR_RANGE
>                   || jfunc->m_vr.type == VR_ANTI_RANGE)
> -               jfunc->vr_known = true;
> +               {
> +                 jfunc->vr_known = true;
> +                 jfunc->passed_type = TREE_TYPE (arg);
> +               }
>               else
>                 jfunc->vr_known = false;
>             }
> @@ -4775,7 +4779,7 @@ ipa_write_jump_function (struct output_block *ob,
>      {
>        streamer_write_widest_int (ob, jump_func->bits.value);
>        streamer_write_widest_int (ob, jump_func->bits.mask);
> -    }
> +    }
>    bp_pack_value (&bp, jump_func->vr_known, 1);
>    streamer_write_bitpack (&bp);
>    if (jump_func->vr_known)
> @@ -4784,6 +4788,7 @@ ipa_write_jump_function (struct output_block *ob,
>                            VR_LAST, jump_func->m_vr.type);
>        stream_write_tree (ob, jump_func->m_vr.min, true);
>        stream_write_tree (ob, jump_func->m_vr.max, true);
> +      stream_write_tree (ob, jump_func->passed_type, true);
>      }
>  }
>
> @@ -4877,6 +4882,7 @@ ipa_read_jump_function (struct lto_input_block *ib,
>                                                  VR_LAST);
>        jump_func->m_vr.min = stream_read_tree (ib, data_in);
>        jump_func->m_vr.max = stream_read_tree (ib, data_in);
> +      jump_func->passed_type = stream_read_tree (ib, data_in);
>      }
>    else
>      jump_func->vr_known = false;
> @@ -4973,7 +4979,10 @@ ipa_write_node_info (struct output_block *ob, struct cgraph_node *node)
>      bp_pack_value (&bp, ipa_is_param_used (info, j), 1);
>    streamer_write_bitpack (&bp);
>    for (j = 0; j < ipa_get_param_count (info); j++)
> -    streamer_write_hwi (ob, ipa_get_controlled_uses (info, j));
> +    {
> +      streamer_write_hwi (ob, ipa_get_controlled_uses (info, j));
> +      stream_write_tree (ob, ipa_get_type (info, j), true);
> +    }
>    for (e = node->callees; e; e = e->next_callee)
>      {
>        struct ipa_edge_args *args = IPA_EDGE_REF (e);
> @@ -5020,7 +5029,7 @@ ipa_read_node_info (struct lto_input_block *ib, struct cgraph_node *node,
>
>    for (k = 0; k < ipa_get_param_count (info); k++)
>      info->descriptors[k].move_cost = streamer_read_uhwi (ib);
> -
> +
>    bp = streamer_read_bitpack (ib);
>    if (ipa_get_param_count (info) != 0)
>      info->analysis_done = true;
> @@ -5028,7 +5037,10 @@ ipa_read_node_info (struct lto_input_block *ib, struct cgraph_node *node,
>    for (k = 0; k < ipa_get_param_count (info); k++)
>      ipa_set_param_used (info, k, bp_unpack_value (&bp, 1));
>    for (k = 0; k < ipa_get_param_count (info); k++)
> -    ipa_set_controlled_uses (info, k, streamer_read_hwi (ib));
> +    {
> +      ipa_set_controlled_uses (info, k, streamer_read_hwi (ib));
> +      info->descriptors[k].decl_or_type = stream_read_tree (ib, data_in);
> +    }
>    for (e = node->callees; e; e = e->next_callee)
>      {
>        struct ipa_edge_args *args = IPA_EDGE_REF (e);
> diff --git a/gcc/ipa-prop.h b/gcc/ipa-prop.h
> index 0e75cf4..e4de8ed 100644
> --- a/gcc/ipa-prop.h
> +++ b/gcc/ipa-prop.h
> @@ -181,6 +181,9 @@ struct GTY (()) ipa_jump_func
>    /* Information about value range.  */
>    bool vr_known;
>    value_range m_vr;
> +  /* If value range is known, this is the type in which we pass the date at the
> +     caller side.  */
> +  tree passed_type;
>
>    enum jump_func_type type;
>    /* Represents a value of a jump function.  pass_through is used only in jump
> diff --git a/gcc/testsuite/gcc.dg/torture/pr78365.c b/gcc/testsuite/gcc.dg/torture/pr78365.c
> new file mode 100644
> index 0000000..5180a01
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/torture/pr78365.c
> @@ -0,0 +1,21 @@
> +/* { dg-do compile } */
> +
> +int a, b, c;
> +char d;
> +static void fn1 (void *, int);
> +int fn2 (int);
> +
> +void fn1 (cc, yh) void *cc;
> +char yh;
> +{
> +  char y;
> +  a = fn2(c - b + 1);
> +  for (; y <= yh; y++)
> +    ;
> +}
> +
> +void fn3()
> +{
> +    fn1((void *)fn3, 1);
> +    fn1((void *)fn3, d - 1);
> +}
> --
> 2.10.2
>