Re: [PATCH] Convert ipcp_vr_lattice to type agnostic framework.

[Martin Jambor <mjambor@suse.cz>]

Hello,

On Mon, May 22 2023, Aldy Hernandez wrote:
> I've adjusted the patch with some minor cleanups that came up when I
> implemented the rest of the IPA revamp.
>
> Rested.  OK?
>
> On Wed, May 17, 2023 at 4:31 PM Aldy Hernandez <aldyh@redhat.com> wrote:
>>
>> This converts the lattice to store ranges in Value_Range instead of
>> value_range (*) to make it type agnostic, and adjust all users
>> accordingly.
>>
>> I think it is a good example on converting from static ranges to more
>> general, type agnostic ones.
>>
>> I've been careful to make sure Value_Range never ends up on GC, since
>> it contains an int_range_max and can expand on-demand onto the heap.
>> Longer term storage for ranges should be done with vrange_storage, as
>> per the previous patch ("Provide an API for ipa_vr").
>>
>> (*) I do know the Value_Range naming versus value_range is quite
>> annoying, but it was a judgement call last release for the eventual
>> migration to having "value_range" be a type agnostic range object.  We
>> will ultimately rename Value_Range to value_range.

It is quite confusing for an unsuspecting reader indeed.

>>
>> OK for trunk?

I guess I need to rely on that you know what you are doing :-)
I have seen in other messages that you measure the compile time
effects of your patches, do you look at memory use as well?

I am happy with the overall approach, I just have the following
comments, questions and a few concerns:


>>
>> gcc/ChangeLog:
>>
>>         * ipa-cp.cc (ipcp_vr_lattice::init): Take type argument.
>>         (ipcp_vr_lattice::print): Call dump method.
>>         (ipcp_vr_lattice::meet_with): Adjust for m_vr being a
>>         Value_Range.
>>         (ipcp_vr_lattice::meet_with_1): Make argument a reference.
>>         (ipcp_vr_lattice::set_to_bottom): Add type argument.
>>         (set_all_contains_variable): Same.
>>         (initialize_node_lattices): Pass type when appropriate.
>>         (ipa_vr_operation_and_type_effects): Make type agnostic.
>>         (ipa_value_range_from_jfunc): Same.
>>         (propagate_vr_across_jump_function): Same.
>>         (propagate_constants_across_call): Same.
>>         * ipa-fnsummary.cc (evaluate_conditions_for_known_args): Same.
>>         (evaluate_properties_for_edge): Same.
>>         * ipa-prop.cc (ipcp_update_vr): Same.
>>         * ipa-prop.h (ipa_value_range_from_jfunc): Same.
>>         (ipa_range_set_and_normalize): Same.
>> ---
>>  gcc/ipa-cp.cc        | 159 +++++++++++++++++++++++--------------------
>>  gcc/ipa-fnsummary.cc |  16 ++---
>>  gcc/ipa-prop.cc      |   2 +-
>>  gcc/ipa-prop.h       |  19 ++----
>>  4 files changed, 101 insertions(+), 95 deletions(-)
>>
>> diff --git a/gcc/ipa-cp.cc b/gcc/ipa-cp.cc
>> index d4b9d4ac27e..bd5b1da17b2 100644
>> --- a/gcc/ipa-cp.cc
>> +++ b/gcc/ipa-cp.cc
>> @@ -343,20 +343,29 @@ private:
>>  class ipcp_vr_lattice
>>  {
>>  public:
>> -  value_range m_vr;
>> +  Value_Range m_vr;
>>
>>    inline bool bottom_p () const;
>>    inline bool top_p () const;
>> -  inline bool set_to_bottom ();
>> -  bool meet_with (const value_range *p_vr);
>> +  inline bool set_to_bottom (tree type);

Requiring a type when setting a lattice to bottom makes for a weird
interface, can't we set the underlying Value_Range to whatever...

>> +  bool meet_with (const vrange &p_vr);
>>    bool meet_with (const ipcp_vr_lattice &other);
>> -  void init () { gcc_assert (m_vr.undefined_p ()); }
>> +  void init (tree type);
>>    void print (FILE * f);
>>
>>  private:
>> -  bool meet_with_1 (const value_range *other_vr);
>> +  bool meet_with_1 (const vrange &other_vr);
>>  };
>>
>> +inline void
>> +ipcp_vr_lattice::init (tree type)
>> +{
>> +  if (type)
>> +    m_vr.set_type (type);
>> +
>> +  // Otherwise m_vr will default to unsupported_range.

...this does?

All users of the lattice check it for not being bottom first, so it
should be safe.

If it is not possible for some reason, then I guess we should add a bool
flag to ipcp_vr_lattice instead, rather than looking up types of
unusable lattices.  ipcp_vr_lattices don't live for long.

>> +}
>> +
>>  /* Structure containing lattices for a parameter itself and for pieces of
>>     aggregates that are passed in the parameter or by a reference in a parameter
>>     plus some other useful flags.  */
>> @@ -585,7 +594,7 @@ ipcp_bits_lattice::print (FILE *f)
>>  void
>>  ipcp_vr_lattice::print (FILE * f)
>>  {
>> -  dump_value_range (f, &m_vr);
>> +  m_vr.dump (f);
>>  }
>>
>>  /* Print all ipcp_lattices of all functions to F.  */
>> @@ -1016,14 +1025,14 @@ set_agg_lats_contain_variable (class ipcp_param_lattices *plats)
>>  bool
>>  ipcp_vr_lattice::meet_with (const ipcp_vr_lattice &other)
>>  {
>> -  return meet_with_1 (&other.m_vr);
>> +  return meet_with_1 (other.m_vr);
>>  }
>>
>>  /* Meet the current value of the lattice with value range described by VR
>>     lattice.  */
>>
>>  bool
>> -ipcp_vr_lattice::meet_with (const value_range *p_vr)
>> +ipcp_vr_lattice::meet_with (const vrange &p_vr)
>>  {
>>    return meet_with_1 (p_vr);
>>  }
>> @@ -1032,23 +1041,23 @@ ipcp_vr_lattice::meet_with (const value_range *p_vr)
>>     OTHER_VR lattice.  Return TRUE if anything changed.  */
>>
>>  bool
>> -ipcp_vr_lattice::meet_with_1 (const value_range *other_vr)
>> +ipcp_vr_lattice::meet_with_1 (const vrange &other_vr)
>>  {
>>    if (bottom_p ())
>>      return false;
>>
>> -  if (other_vr->varying_p ())
>> -    return set_to_bottom ();
>> +  if (other_vr.varying_p ())
>> +    return set_to_bottom (other_vr.type ());
>>
>>    bool res;
>>    if (flag_checking)
>>      {
>> -      value_range save (m_vr);
>> -      res = m_vr.union_ (*other_vr);
>> +      Value_Range save (m_vr);
>> +      res = m_vr.union_ (other_vr);
>>        gcc_assert (res == (m_vr != save));
>>      }
>>    else
>> -    res = m_vr.union_ (*other_vr);
>> +    res = m_vr.union_ (other_vr);
>>    return res;
>>  }
>>
>> @@ -1073,16 +1082,11 @@ ipcp_vr_lattice::bottom_p () const
>>     previously was in a different state.  */
>>
>>  bool
>> -ipcp_vr_lattice::set_to_bottom ()
>> +ipcp_vr_lattice::set_to_bottom (tree type)
>>  {
>>    if (m_vr.varying_p ())
>>      return false;
>> -  /* ?? We create all sorts of VARYING ranges for floats, structures,
>> -     and other types which we cannot handle as ranges.  We should
>> -     probably avoid handling them throughout the pass, but it's easier
>> -     to create a sensible VARYING here and let the lattice
>> -     propagate.  */
>> -  m_vr.set_varying (integer_type_node);
>> +  m_vr.set_varying (type);
>>    return true;
>>  }
>>
>> @@ -1518,14 +1522,14 @@ intersect_argaggs_with (vec<ipa_argagg_value> &elts,
>>     return true is any of them has not been marked as such so far.  */
>>
>>  static inline bool
>> -set_all_contains_variable (class ipcp_param_lattices *plats)
>> +set_all_contains_variable (class ipcp_param_lattices *plats, tree type)
>>  {

...then functions like these would not need the extra parameter either.

>>    bool ret;
>>    ret = plats->itself.set_contains_variable ();
>>    ret |= plats->ctxlat.set_contains_variable ();
>>    ret |= set_agg_lats_contain_variable (plats);
>>    ret |= plats->bits_lattice.set_to_bottom ();
>> -  ret |= plats->m_value_range.set_to_bottom ();
>> +  ret |= plats->m_value_range.set_to_bottom (type);
>>    return ret;
>>  }
>>
>> @@ -1653,6 +1657,7 @@ initialize_node_lattices (struct cgraph_node *node)
>>    for (i = 0; i < ipa_get_param_count (info); i++)
>>      {
>>        ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i);
>> +      tree type = ipa_get_type (info, i);
>>        if (disable
>>           || !ipa_get_type (info, i)
>>           || (pre_modified && (surviving_params.length () <= (unsigned) i
>> @@ -1662,14 +1667,14 @@ initialize_node_lattices (struct cgraph_node *node)
>>           plats->ctxlat.set_to_bottom ();
>>           set_agg_lats_to_bottom (plats);
>>           plats->bits_lattice.set_to_bottom ();
>> -         plats->m_value_range.m_vr = value_range ();
>> -         plats->m_value_range.set_to_bottom ();
>> +         plats->m_value_range.init (type);
>> +         plats->m_value_range.set_to_bottom (type);
>>         }
>>        else
>>         {
>> -         plats->m_value_range.init ();
>> +         plats->m_value_range.init (type);
>>           if (variable)
>> -           set_all_contains_variable (plats);
>> +           set_all_contains_variable (plats, type);
>>         }
>>      }
>>
>> @@ -1903,8 +1908,8 @@ ipa_context_from_jfunc (ipa_node_params *info, cgraph_edge *cs, int csidx,
>>     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,
>> +ipa_vr_operation_and_type_effects (vrange &dst_vr,
>> +                                  const vrange &src_vr,
>>                                    enum tree_code operation,
>>                                    tree dst_type, tree src_type)
>>  {
>> @@ -1912,29 +1917,33 @@ ipa_vr_operation_and_type_effects (value_range *dst_vr,
>>      return false;
>>
>>    range_op_handler handler (operation, dst_type);
>> -  return (handler
>> -         && handler.fold_range (*dst_vr, dst_type,
>> -                                *src_vr, value_range (dst_type))
>> -         && !dst_vr->varying_p ()
>> -         && !dst_vr->undefined_p ());
>> +  if (!handler)
>> +    return false;
>> +
>> +  Value_Range varying (dst_type);
>> +  varying.set_varying (dst_type);
>> +
>> +  return (handler.fold_range (dst_vr, dst_type, src_vr, varying)
>> +         && !dst_vr.varying_p ()
>> +         && !dst_vr.undefined_p ());
>>  }
>>
>>  /* Determine value_range of JFUNC given that INFO describes the caller node or
>>     the one it is inlined to, CS is the call graph edge corresponding to JFUNC
>>     and PARM_TYPE of the parameter.  */
>>
>> -value_range
>> -ipa_value_range_from_jfunc (ipa_node_params *info, cgraph_edge *cs,
>> +void
>> +ipa_value_range_from_jfunc (vrange &vr,
>> +                           ipa_node_params *info, cgraph_edge *cs,
>>                             ipa_jump_func *jfunc, tree parm_type)

I assume that you decided to return the value in a parameter passed by
reference instead of in return value for a good reason but then can we
at least...


>>  {
>> -  value_range vr;
>>    if (jfunc->m_vr)
>> -    ipa_vr_operation_and_type_effects (&vr,
>> -                                      jfunc->m_vr,
>> +    ipa_vr_operation_and_type_effects (vr,
>> +                                      *jfunc->m_vr,
>>                                        NOP_EXPR, parm_type,
>>                                        jfunc->m_vr->type ());
>>    if (vr.singleton_p ())
>> -    return vr;
>> +    return;

...make sure that whenever the function intends to return a varying VR
it actually does so instead of not touching it at all?

>>    if (jfunc->type == IPA_JF_PASS_THROUGH)
>>      {
>>        int idx;
>> @@ -1943,33 +1952,34 @@ ipa_value_range_from_jfunc (ipa_node_params *info, cgraph_edge *cs,
>>                                            ? cs->caller->inlined_to
>>                                            : cs->caller);
>>        if (!sum || !sum->m_vr)
>> -       return vr;
>> +       return;

Likewise.

>>
>>        idx = ipa_get_jf_pass_through_formal_id (jfunc);
>>
>>        if (!(*sum->m_vr)[idx].known_p ())
>> -       return vr;
>> +       return;

Likewise.

>>        tree vr_type = ipa_get_type (info, idx);
>> -      value_range srcvr;
>> +      Value_Range srcvr (vr_type);
>>        (*sum->m_vr)[idx].get_vrange (srcvr, vr_type);
>>
>>        enum tree_code operation = ipa_get_jf_pass_through_operation (jfunc);
>>
>>        if (TREE_CODE_CLASS (operation) == tcc_unary)
>>         {
>> -         value_range res;
>> +         Value_Range res (vr_type);
>>
>> -         if (ipa_vr_operation_and_type_effects (&res,
>> -                                                &srcvr,
>> +         if (ipa_vr_operation_and_type_effects (res,
>> +                                                srcvr,
>>                                                  operation, parm_type,
>>                                                  vr_type))
>>             vr.intersect (res);

Here we also now make assumptions about the state of vr which we did not
before, should we perhaps assign res into vr instead?

>>         }
>>        else
>>         {
>> -         value_range op_res, res;
>> +         Value_Range op_res (vr_type);
>> +         Value_Range res (vr_type);
>>           tree op = ipa_get_jf_pass_through_operand (jfunc);
>> -         value_range op_vr;
>> +         Value_Range op_vr (vr_type);
>>           range_op_handler handler (operation, vr_type);
>>
>>           ipa_range_set_and_normalize (op_vr, op);
>> @@ -1979,14 +1989,13 @@ ipa_value_range_from_jfunc (ipa_node_params *info, cgraph_edge *cs,
>>               || !handler.fold_range (op_res, vr_type, srcvr, op_vr))
>>             op_res.set_varying (vr_type);
>>
>> -         if (ipa_vr_operation_and_type_effects (&res,
>> -                                                &op_res,
>> +         if (ipa_vr_operation_and_type_effects (res,
>> +                                                op_res,
>>                                                  NOP_EXPR, parm_type,
>>                                                  vr_type))
>>             vr.intersect (res);

Likewise.

>>         }
>>      }
>> -  return vr;
>>  }
>>
>>  /* Determine whether ITEM, jump function for an aggregate part, evaluates to a
>> @@ -2739,7 +2748,7 @@ propagate_vr_across_jump_function (cgraph_edge *cs, ipa_jump_func *jfunc,
>>    if (!param_type
>>        || (!INTEGRAL_TYPE_P (param_type)
>>           && !POINTER_TYPE_P (param_type)))
>> -    return dest_lat->set_to_bottom ();
>> +    return dest_lat->set_to_bottom (param_type);
>>
>>    if (jfunc->type == IPA_JF_PASS_THROUGH)
>>      {
>> @@ -2751,12 +2760,12 @@ propagate_vr_across_jump_function (cgraph_edge *cs, ipa_jump_func *jfunc,
>>        tree operand_type = ipa_get_type (caller_info, src_idx);
>>
>>        if (src_lats->m_value_range.bottom_p ())
>> -       return dest_lat->set_to_bottom ();
>> +       return dest_lat->set_to_bottom (operand_type);
>>
>> -      value_range vr;
>> +      Value_Range vr (operand_type);
>>        if (TREE_CODE_CLASS (operation) == tcc_unary)
>> -       ipa_vr_operation_and_type_effects (&vr,
>> -                                          &src_lats->m_value_range.m_vr,
>> +       ipa_vr_operation_and_type_effects (vr,
>> +                                          src_lats->m_value_range.m_vr,
>>                                            operation, param_type,
>>                                            operand_type);
>>        /* A crude way to prevent unbounded number of value range updates
>> @@ -2765,8 +2774,8 @@ propagate_vr_across_jump_function (cgraph_edge *cs, ipa_jump_func *jfunc,
>>        else if (!ipa_edge_within_scc (cs))
>>         {
>>           tree op = ipa_get_jf_pass_through_operand (jfunc);
>> -         value_range op_vr;
>> -         value_range op_res,res;
>> +         Value_Range op_vr (TREE_TYPE (op));
>> +         Value_Range op_res (operand_type);
>>           range_op_handler handler (operation, operand_type);
>>
>>           ipa_range_set_and_normalize (op_vr, op);
>> @@ -2777,8 +2786,8 @@ propagate_vr_across_jump_function (cgraph_edge *cs, ipa_jump_func *jfunc,
>>                                       src_lats->m_value_range.m_vr, op_vr))
>>             op_res.set_varying (operand_type);
>>
>> -         ipa_vr_operation_and_type_effects (&vr,
>> -                                            &op_res,
>> +         ipa_vr_operation_and_type_effects (vr,
>> +                                            op_res,
>>                                              NOP_EXPR, param_type,
>>                                              operand_type);
>>         }
>> @@ -2786,14 +2795,14 @@ propagate_vr_across_jump_function (cgraph_edge *cs, ipa_jump_func *jfunc,
>>         {
>>           if (jfunc->m_vr)
>>             {
>> -             value_range jvr;
>> -             if (ipa_vr_operation_and_type_effects (&jvr, jfunc->m_vr,
>> +             Value_Range jvr (param_type);
>> +             if (ipa_vr_operation_and_type_effects (jvr, *jfunc->m_vr,
>>                                                      NOP_EXPR,
>>                                                      param_type,
>>                                                      jfunc->m_vr->type ()))
>>                 vr.intersect (jvr);
>>             }
>> -         return dest_lat->meet_with (&vr);
>> +         return dest_lat->meet_with (vr);
>>         }
>>      }
>>    else if (jfunc->type == IPA_JF_CONST)
>> @@ -2805,20 +2814,19 @@ propagate_vr_across_jump_function (cgraph_edge *cs, ipa_jump_func *jfunc,
>>           if (TREE_OVERFLOW_P (val))
>>             val = drop_tree_overflow (val);
>>
>> -         value_range tmpvr (TREE_TYPE (val),
>> -                            wi::to_wide (val), wi::to_wide (val));
>> -         return dest_lat->meet_with (&tmpvr);
>> +         Value_Range tmpvr (val, val);
>> +         return dest_lat->meet_with (tmpvr);
>>         }
>>      }
>>
>>    value_range vr;
>>    if (jfunc->m_vr
>> -      && ipa_vr_operation_and_type_effects (&vr, jfunc->m_vr, NOP_EXPR,
>> +      && ipa_vr_operation_and_type_effects (vr, *jfunc->m_vr, NOP_EXPR,
>>                                             param_type,
>>                                             jfunc->m_vr->type ()))
>> -    return dest_lat->meet_with (&vr);
>> +    return dest_lat->meet_with (vr);
>>    else
>> -    return dest_lat->set_to_bottom ();
>> +    return dest_lat->set_to_bottom (param_type);
>>  }
>>
>>  /* If DEST_PLATS already has aggregate items, check that aggs_by_ref matches
>> @@ -3209,7 +3217,8 @@ propagate_constants_across_call (struct cgraph_edge *cs)
>>      {
>>        for (i = 0; i < parms_count; i++)
>>         ret |= set_all_contains_variable (ipa_get_parm_lattices (callee_info,
>> -                                                                i));
>> +                                                                i),
>> +                                         ipa_get_type (callee_info, i));

I have complained about it above but this another example where making
ipcp_vr_lattice::set_to_bottom not require a type which is not really
needed could even save a tiny bit of compile time.

>>        return ret;
>>      }
>>    args_count = ipa_get_cs_argument_count (args);
>> @@ -3220,7 +3229,8 @@ propagate_constants_across_call (struct cgraph_edge *cs)
>>    if (call_passes_through_thunk (cs))
>>      {
>>        ret |= set_all_contains_variable (ipa_get_parm_lattices (callee_info,
>> -                                                              0));
>> +                                                              0),
>> +                                       ipa_get_type (callee_info, 0));
>>        i = 1;
>>      }
>>    else
>> @@ -3234,7 +3244,7 @@ propagate_constants_across_call (struct cgraph_edge *cs)
>>
>>        dest_plats = ipa_get_parm_lattices (callee_info, i);
>>        if (availability == AVAIL_INTERPOSABLE)
>> -       ret |= set_all_contains_variable (dest_plats);
>> +       ret |= set_all_contains_variable (dest_plats, param_type);
>>        else
>>         {
>>           ret |= propagate_scalar_across_jump_function (cs, jump_func,
>> @@ -3251,11 +3261,12 @@ propagate_constants_across_call (struct cgraph_edge *cs)
>>             ret |= propagate_vr_across_jump_function (cs, jump_func,
>>                                                       dest_plats, param_type);
>>           else
>> -           ret |= dest_plats->m_value_range.set_to_bottom ();
>> +           ret |= dest_plats->m_value_range.set_to_bottom (param_type);
>>         }
>>      }
>>    for (; i < parms_count; i++)
>> -    ret |= set_all_contains_variable (ipa_get_parm_lattices (callee_info, i));
>> +    ret |= set_all_contains_variable (ipa_get_parm_lattices (callee_info, i),
>> +                                     ipa_get_type (callee_info, i));
>>
>>    return ret;
>>  }
>> diff --git a/gcc/ipa-fnsummary.cc b/gcc/ipa-fnsummary.cc
>> index b328bb8ce14..0474af8991e 100644
>> --- a/gcc/ipa-fnsummary.cc
>> +++ b/gcc/ipa-fnsummary.cc
>> @@ -475,7 +475,7 @@ evaluate_conditions_for_known_args (struct cgraph_node *node,
>>           && !c->agg_contents
>>           && (!val || TREE_CODE (val) != INTEGER_CST))
>>         {
>> -         value_range vr = avals->m_known_value_ranges[c->operand_num];
>> +         Value_Range vr (avals->m_known_value_ranges[c->operand_num]);
>>           if (!vr.undefined_p ()
>>               && !vr.varying_p ()
>>               && (TYPE_SIZE (c->type) == TYPE_SIZE (vr.type ())))
>> @@ -630,8 +630,8 @@ evaluate_properties_for_edge (struct cgraph_edge *e, bool inline_p,
>>                 || ipa_is_param_used_by_ipa_predicates (callee_pi, i))
>>               {
>>                 /* Determine if we know constant value of the parameter.  */
>> -               tree cst = ipa_value_from_jfunc (caller_parms_info, jf,
>> -                                                ipa_get_type (callee_pi, i));
>> +               tree type = ipa_get_type (callee_pi, i);
>> +               tree cst = ipa_value_from_jfunc (caller_parms_info, jf, type);
>>
>>                 if (!cst && e->call_stmt
>>                     && i < (int)gimple_call_num_args (e->call_stmt))
>> @@ -659,10 +659,10 @@ evaluate_properties_for_edge (struct cgraph_edge *e, bool inline_p,
>>                     && vrp_will_run_p (caller)
>>                     && ipa_is_param_used_by_ipa_predicates (callee_pi, i))
>>                   {
>> -                   value_range vr
>> -                      = ipa_value_range_from_jfunc (caller_parms_info, e, jf,
>> -                                                    ipa_get_type (callee_pi,
>> -                                                                  i));
>> +                   Value_Range vr (type);
>> +
>> +                   ipa_value_range_from_jfunc (vr, caller_parms_info, e, jf,
>> +                                               ipa_get_type (callee_pi, i));

I guess that the ipa_get_type call can also be replaced with "type" now.

>>                     if (!vr.undefined_p () && !vr.varying_p ())
>>                       {
>>                         if (!avals->m_known_value_ranges.length ())
>> @@ -670,7 +670,7 @@ evaluate_properties_for_edge (struct cgraph_edge *e, bool inline_p,
>>                             avals->m_known_value_ranges.safe_grow (count, true);
>>                             for (int i = 0; i < count; ++i)
>>                               new (&avals->m_known_value_ranges[i])
>> -                               value_range ();
>> +                               Value_Range ();
>>                           }
>>                         avals->m_known_value_ranges[i] = vr;
>>                       }

Thanks for working on this and sorry that it takes me so long to review.

Martin