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

Andrew MacLeod amacleod@redhat.com
Mon Aug 17 15:59:06 GMT 2020


On 8/17/20 6:04 AM, Aldy Hernandez wrote:
>
>
> 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?
>
>
hum. is it a behaviour change?  It might be for multiranges, but it 
seems like min or max could be symbolics in legacy mode... and we'd lose 
that information...

why can't we just    set (min, max) all the time like it did before?

I guess its possible that the loop bounds info may return symbolics, 
which wont jive well with ranger/multi-range code.   I expect we'll have 
to enhance the loop interface for ranger later anyway.



  Andrew






More information about the Gcc-patches mailing list