[PATCH 2/2] Decouple adjust_range_from_scev from vr_values and value_range_equiv.

Richard Biener richard.guenther@gmail.com
Tue Aug 4 13:27:34 GMT 2020


On Tue, Aug 4, 2020 at 2:05 PM Aldy Hernandez via Gcc-patches
<gcc-patches@gcc.gnu.org> wrote:
>
> I've abstracted out the parts of the code that had nothing to do with
> value_range_equiv into an externally visible range_of_var_in_loop().
> This way, it can be called with any range.
>
> adjust_range_with_scev still works as before, intersecting with a
> known range.  Due to the way value_range_equiv::intersect works,
> intersecting a value_range_equiv with no equivalences into one
> with equivalences will result in the resulting range maintaining
> whatever equivalences it had.  So everything works as the
> vr->update() did before (remember that ::update() retains
> equivalences).
>
> OK?
>
> gcc/ChangeLog:
>
>         * vr-values.c (check_for_binary_op_overflow): Change type of store
>         to range_query.
>         (vr_values::adjust_range_with_scev): Abstract most of the code...
>         (range_of_var_in_loop): ...here.  Remove value_range_equiv uses.
>         (simplify_using_ranges::simplify_using_ranges): Change type of store
>         to range_query.
>         * vr-values.h (class range_query): New.
>         (class simplify_using_ranges): Use range_query.
>         (class vr_values): Add OVERRIDE to get_value_range.
>         (range_of_var_in_loop): New.
> ---
>  gcc/vr-values.c | 140 ++++++++++++++++++++++--------------------------
>  gcc/vr-values.h |  23 ++++++--
>  2 files changed, 81 insertions(+), 82 deletions(-)
>
> diff --git a/gcc/vr-values.c b/gcc/vr-values.c
> index 9002d87c14b..e7f97bdbf7b 100644
> --- a/gcc/vr-values.c
> +++ b/gcc/vr-values.c
> @@ -1004,7 +1004,7 @@ vr_values::extract_range_from_comparison (value_range_equiv *vr,
>     overflow.  */
>
>  static bool
> -check_for_binary_op_overflow (vr_values *store,
> +check_for_binary_op_overflow (range_query *store,
>                               enum tree_code subcode, tree type,
>                               tree op0, tree op1, bool *ovf)
>  {
> @@ -1737,22 +1737,18 @@ compare_range_with_value (enum tree_code comp, const value_range *vr,
>
>    gcc_unreachable ();
>  }
> +
>  /* Given a range VR, a LOOP and a variable VAR, determine whether it
>     would be profitable to adjust VR using scalar evolution information
>     for VAR.  If so, update VR with the new limits.  */

Certainly this comment needs updating now.  It's tempting to provide
a range from the scalar evolution info separately from "adjusting" a range,
at least the comment suggests we'll not always do so.  I'm not sure
your patch factors that decision out or simply returns [-INF,+INF] for
intersection.  For example...

>  void
> -vr_values::adjust_range_with_scev (value_range_equiv *vr, class loop *loop,
> -                                  gimple *stmt, tree var)
> +range_of_var_in_loop (irange *vr, range_query *query,
> +                     class loop *loop, gimple *stmt, tree var)
>  {
> -  tree init, step, chrec, tmin, tmax, min, max, type, tem;
> +  tree init, step, chrec, tmin, tmax, min, max, type;
>    enum ev_direction dir;
>
> -  /* TODO.  Don't adjust anti-ranges.  An anti-range may provide
> -     better opportunities than a regular range, but I'm not sure.  */
> -  if (vr->kind () == VR_ANTI_RANGE)
> -    return;
> -

... this (probably the worst example).  The rest seem to be more
correctness issues than profitability.

>    chrec = instantiate_parameters (loop, analyze_scalar_evolution (loop, var));
>
>    /* Like in PR19590, scev can return a constant function.  */
> @@ -1763,16 +1759,17 @@ vr_values::adjust_range_with_scev (value_range_equiv *vr, class loop *loop,
>      }
>
>    if (TREE_CODE (chrec) != POLYNOMIAL_CHREC)
> -    return;
> +    {
> +      vr->set_varying (TREE_TYPE (var));
> +      return;
> +    }
>
>    init = initial_condition_in_loop_num (chrec, loop->num);
> -  tem = op_with_constant_singleton_value_range (init);
> -  if (tem)
> -    init = tem;
> +  if (TREE_CODE (init) == SSA_NAME)
> +    query->get_value_range (init, stmt)->singleton_p (&init);
>    step = evolution_part_in_loop_num (chrec, loop->num);
> -  tem = op_with_constant_singleton_value_range (step);
> -  if (tem)
> -    step = tem;
> +  if (TREE_CODE (step) == SSA_NAME)
> +    query->get_value_range (step, stmt)->singleton_p (&step);
>
>    /* If STEP is symbolic, we can't know whether INIT will be the
>       minimum or maximum value in the range.  Also, unless INIT is
> @@ -1781,7 +1778,10 @@ vr_values::adjust_range_with_scev (value_range_equiv *vr, class loop *loop,
>    if (step == NULL_TREE
>        || !is_gimple_min_invariant (step)
>        || !valid_value_p (init))
> -    return;
> +    {
> +      vr->set_varying (TREE_TYPE (var));
> +      return;
> +    }
>
>    dir = scev_direction (chrec);
>    if (/* Do not adjust ranges if we do not know whether the iv increases
> @@ -1790,7 +1790,10 @@ vr_values::adjust_range_with_scev (value_range_equiv *vr, class loop *loop,
>        /* ... or if it may wrap.  */
>        || scev_probably_wraps_p (NULL_TREE, init, step, stmt,
>                                 get_chrec_loop (chrec), true))
> -    return;
> +    {
> +      vr->set_varying (TREE_TYPE (var));
> +      return;
> +    }
>
>    type = TREE_TYPE (var);
>    if (POINTER_TYPE_P (type) || !TYPE_MIN_VALUE (type))
> @@ -1807,7 +1810,7 @@ vr_values::adjust_range_with_scev (value_range_equiv *vr, class loop *loop,
>    if (TREE_CODE (step) == INTEGER_CST
>        && is_gimple_val (init)
>        && (TREE_CODE (init) != SSA_NAME
> -         || get_value_range (init, stmt)->kind () == VR_RANGE))
> +         || query->get_value_range (init, stmt)->kind () == VR_RANGE))
>      {
>        widest_int nit;
>
> @@ -1830,21 +1833,32 @@ vr_values::adjust_range_with_scev (value_range_equiv *vr, class loop *loop,
>               && (sgn == UNSIGNED
>                   || wi::gts_p (wtmp, 0) == wi::gts_p (wi::to_wide (step), 0)))
>             {
> -             value_range_equiv maxvr;
> -             tem = wide_int_to_tree (TREE_TYPE (init), wtmp);
> -             extract_range_from_binary_expr (&maxvr, PLUS_EXPR,
> -                                             TREE_TYPE (init), init, tem);
> +             value_range maxvr, vr0, vr1;
> +             if (TREE_CODE (init) == SSA_NAME)
> +               vr0 = *(query->get_value_range (init, stmt));
> +             else if (is_gimple_min_invariant (init))
> +               vr0.set (init);
> +             else
> +               vr0.set_varying (TREE_TYPE (init));
> +             tree tem = wide_int_to_tree (TREE_TYPE (init), wtmp);
> +             vr1.set (tem, tem);
> +             range_fold_binary_expr (&maxvr, PLUS_EXPR,
> +                                     TREE_TYPE (init), &vr0, &vr1);
> +
>               /* Likewise if the addition did.  */
>               if (maxvr.kind () == VR_RANGE)
>                 {
>                   value_range initvr;
>
>                   if (TREE_CODE (init) == SSA_NAME)
> -                   initvr = *(get_value_range (init, stmt));
> +                   initvr = *(query->get_value_range (init, stmt));
>                   else if (is_gimple_min_invariant (init))
>                     initvr.set (init);
>                   else
> -                   return;
> +                   {
> +                     vr->set_varying (TREE_TYPE (var));
> +                     return;
> +                   }
>
>                   /* Check if init + nit * step overflows.  Though we checked
>                      scev {init, step}_loop doesn't wrap, it is not enough
> @@ -1854,7 +1868,10 @@ vr_values::adjust_range_with_scev (value_range_equiv *vr, class loop *loop,
>                        && compare_values (maxvr.min (), initvr.min ()) != -1)
>                       || (dir == EV_DIR_GROWS
>                           && compare_values (maxvr.max (), initvr.max ()) != 1))
> -                   return;
> +                   {
> +                     vr->set_varying (TREE_TYPE (var));
> +                     return;
> +                   }
>
>                   tmin = maxvr.min ();
>                   tmax = maxvr.max ();
> @@ -1863,56 +1880,12 @@ vr_values::adjust_range_with_scev (value_range_equiv *vr, class loop *loop,
>         }
>      }
>
> -  if (vr->varying_p () || vr->undefined_p ())
> -    {
> -      min = tmin;
> -      max = tmax;
> -
> -      /* For VARYING or UNDEFINED ranges, just about anything we get
> -        from scalar evolutions should be better.  */
> -
> -      if (dir == EV_DIR_DECREASES)
> -       max = init;
> -      else
> -       min = init;
> -    }
> -  else if (vr->kind () == VR_RANGE)
> -    {
> -      min = vr->min ();
> -      max = vr->max ();
> -
> -      if (dir == EV_DIR_DECREASES)
> -       {
> -         /* INIT is the maximum value.  If INIT is lower than VR->MAX ()
> -            but no smaller than VR->MIN (), set VR->MAX () to INIT.  */
> -         if (compare_values (init, max) == -1)
> -           max = init;
> -
> -         /* According to the loop information, the variable does not
> -            overflow.  */
> -         if (compare_values (min, tmin) == -1)
> -           min = tmin;
> -
> -       }
> -      else
> -       {
> -         /* If INIT is bigger than VR->MIN (), set VR->MIN () to INIT.  */
> -         if (compare_values (init, min) == 1)
> -           min = init;
> -
> -         if (compare_values (tmax, max) == -1)
> -           max = tmax;
> -       }
> -    }
> +  min = tmin;
> +  max = tmax;
> +  if (dir == EV_DIR_DECREASES)
> +    max = init;
>    else
> -    return;
> -
> -  /* If we just created an invalid range with the minimum
> -     greater than the maximum, we fail conservatively.
> -     This should happen only in unreachable
> -     parts of code, or for invalid programs.  */
> -  if (compare_values (min, max) == 1)
> -    return;
> +    min = init;
>
>    /* Even for valid range info, sometimes overflow flag will leak in.
>       As GIMPLE IL should have no constants with TREE_OVERFLOW set, we
> @@ -1922,7 +1895,20 @@ vr_values::adjust_range_with_scev (value_range_equiv *vr, class loop *loop,
>    if (TREE_OVERFLOW_P (max))
>      max = drop_tree_overflow (max);
>
> -  vr->update (min, max);
> +  gcc_checking_assert (compare_values (min, max) != 1);
> +  if (TREE_CODE (min) == INTEGER_CST && TREE_CODE (max) == INTEGER_CST)
> +    vr->set (min, max);
> +  else
> +    vr->set_varying (TREE_TYPE (var));
> +}
> +
> +void
> +vr_values::adjust_range_with_scev (value_range_equiv *vr, class loop *loop,
> +                                  gimple *stmt, tree var)
> +{
> +  value_range_equiv r;
> +  range_of_var_in_loop (&r, this, loop, stmt, var);
> +  vr->intersect (&r);
>  }
>
>  /* Dump value ranges of all SSA_NAMEs to FILE.  */
> @@ -4217,7 +4203,7 @@ simplify_using_ranges::two_valued_val_range_p (tree var, tree *a, tree *b)
>    return false;
>  }
>
> -simplify_using_ranges::simplify_using_ranges (vr_values *store)
> +simplify_using_ranges::simplify_using_ranges (range_query *store)
>    : store (store)
>  {
>    to_remove_edges = vNULL;
> diff --git a/gcc/vr-values.h b/gcc/vr-values.h
> index 3fbea9bd69f..28bccf62063 100644
> --- a/gcc/vr-values.h
> +++ b/gcc/vr-values.h
> @@ -22,16 +22,25 @@ along with GCC; see the file COPYING3.  If not see
>
>  #include "value-range-equiv.h"
>
> +// Abstract class to return a range for a given SSA.
> +
> +class range_query
> +{
> +public:
> +  virtual const value_range_equiv *get_value_range (const_tree, gimple *) = 0;
> +  virtual ~range_query () { }
> +};
> +
>  // Class to simplify a statement using range information.
>  //
>  // The constructor takes a full vr_values, but all it needs is
>  // get_value_range() from it.  This class could be made to work with
>  // any range repository.
>
> -class simplify_using_ranges
> +class simplify_using_ranges : public range_query
>  {
>  public:
> -  simplify_using_ranges (class vr_values *);
> +  simplify_using_ranges (class range_query *);
>    ~simplify_using_ranges ();
>    bool simplify (gimple_stmt_iterator *);
>
> @@ -43,7 +52,8 @@ public:
>                                                 bool *, bool *);
>
>  private:
> -  const value_range_equiv *get_value_range (const_tree op, gimple *stmt);
> +  const value_range_equiv *get_value_range (const_tree op, gimple *stmt)
> +    OVERRIDE;
>    bool simplify_truth_ops_using_ranges (gimple_stmt_iterator *, gimple *);
>    bool simplify_div_or_mod_using_ranges (gimple_stmt_iterator *, gimple *);
>    bool simplify_abs_using_ranges (gimple_stmt_iterator *, gimple *);
> @@ -78,7 +88,7 @@ private:
>
>    vec<edge> to_remove_edges;
>    vec<switch_update> to_update_switch_stmts;
> -  class vr_values *store;
> +  class range_query *store;
>  };
>
>  /* The VR_VALUES class holds the current view of range information
> @@ -95,7 +105,7 @@ private:
>     gets attached to an SSA_NAME.  It's unclear how useful that global
>     information will be in a world where we can compute context sensitive
>     range information fast or perform on-demand queries.  */
> -class vr_values
> +class vr_values : public range_query
>  {
>   public:
>    vr_values (void);
> @@ -177,4 +187,7 @@ extern tree get_output_for_vrp (gimple *);
>  // FIXME: Move this to tree-vrp.c.
>  void simplify_cond_using_ranges_2 (class vr_values *, gcond *);
>
> +extern void range_of_var_in_loop (irange *, range_query *,
> +                                 class loop *loop, gimple *stmt, tree var);
> +
>  #endif /* GCC_VR_VALUES_H */
> --
> 2.26.2
>


More information about the Gcc-patches mailing list