On Tue, Aug 4, 2020 at 3:27 PM Richard Biener
<[email protected]> wrote:
>
> On Tue, Aug 4, 2020 at 2:05 PM Aldy Hernandez via Gcc-patches
> <[email protected]> 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...
The comment belonged to the original method which is now a wrapper. I've moved
the comment to its original location and have added a comment to the
new function. And yes,
we return VARYING if we weren't able to determine a range. I've documented it.
Thanks.
Aldy
>
> > 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
> >
>
