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

Aldy Hernandez aldyh@redhat.com
Mon Aug 17 10:04:42 GMT 2020



On 8/14/20 7:16 PM, Andrew MacLeod wrote:
> On 8/14/20 12:05 PM, Aldy Hernandez wrote:
>> I made some minor changes to the function comments.
>>
>> 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 | 150 ++++++++++++++++++++++--------------------------
>>  gcc/vr-values.h |  23 ++++++--
>>  2 files changed, 88 insertions(+), 85 deletions(-)
>>
>> diff --git a/gcc/vr-values.c b/gcc/vr-values.c
>> index 9002d87c14b..5b7bae3bfb7 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.  */
>> +
>> +/* Given a VAR in STMT within LOOP, determine the range of the
>> +   variable and store it in VR.  If no range can be determined, the
>> +   resulting range will be set to VARYING.  */
>>
>>  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;
>> -
> 
> IIUC, you've switched to using the new API, so the bounds calls will 
> basically turn and ANTI range into a varying , making [lbound,ubound] 
> will be [MIN, MAX] ?
> so its effectively a no-op, except we will not punt on getting a range 
> when VR is an anti range anymore.. so that goodness...

Yes.

> 
> 
>> 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;
>> +    }
> 
> Im seeing a lot of this pattern...
> Maybe we should set vr to varying upon entry to the function as the 
> default return value.. then we can just return like it did before in all 
> those places.
> 
> Better yet, since this routine doesn't "update" anymore and simply 
> returns a range, maybe it could instead return a boolean if it finds a 
> range rather than the current behaviour...
> then those simply become
> 
> +    return false;
> 
> We won't have to intersect at the caller if we don't need to, and its 
> useful information at other points to know a range was calculated 
> without having to see if varying_p () came back from the call.
> ie, we'd the usage pattern would then be
> 
> value_range_equiv r;
> if (range_of_var_in_loop (&r, this, loop, stmt, var))
>     vr->intersect (&r);
> 
> This is the pattern we use throughout the ranger.

Done.

> 
> 
>>
>>    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 I read this correctly, we get values for init and step... and if they 
> are SSA_NAMES, then we query ranges, otherwise use what we got back.. So 
> that would seem to be the same behaviour as before then..
> Perhaps a comment is warranted? I had to read it a few times :-)

Indeed.  I am trying to do too much in one line.  I've added a comment.

> 
> 
>>
>>    /* 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,24 @@ 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));
>> +}
> 
> if min OR max is an integer (not both as in here),  shouldn't we be 
> setting the bounds we do know?
> ie  [min, +INF] or [0/-INF, max] ?
> or is that an behaviour change?

It is definitely a behavior change.  However, I did try it just in case, 
but it caused a stage gengtype error, which I'm quite disinterested in 
chasing down.

OK?

Aldy
-------------- next part --------------
A non-text attachment was scrubbed...
Name: 0001-Decouple-adjust_range_from_scev-from-vr_values-and-v.patch
Type: text/x-patch
Size: 11559 bytes
Desc: not available
URL: <https://gcc.gnu.org/pipermail/gcc-patches/attachments/20200817/ccccc803/attachment-0001.bin>


More information about the Gcc-patches mailing list