On 8/17/20 5:59 PM, Andrew MacLeod wrote:
> 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?

Ah crap.  You're right.  Loop info may give us [SYM, 10] which must play 
well with a VR of say [5, 8].

I changed the interface to take in a *MIN and *MAX and set those in a 
function which is now called bounds_of_var_in_loop() since it's 
returning a pair of bounds, not a range.

I also moved the tweaking what was being done in said function into 
adjust_range_with_scev, which should now handle symbolics as we were 
doing before.

And as a bonus I tested all this by making sure that my new code gives 
the same result as the old code (see "FIXME: Temporary testing 
construct" in patch).  Bootstraps without failing the sanity check. 
Tests currently running.

For the ranger code, we can just normalize MIN/MAX into constants (or 
resolve any symbolics on-demand), and then just intersect.  For the 
record, any symbolics are guaranteed to be either SYM or SYM +- INT (per 
the valid_value_p() predicate in bounds_of_var_in_loop).  So they will 
be easy to parse.

I added a future enhancement comment for anti-ranges in the 
adjust_range_with_scev method if anyone is so inclined.  The previous 
code bailed on anti-ranges in preference of the VR passed down.  I have 
kept this functionality to avoid changing current behavior (and failing 
the sanity test).  And yes, we are steering away from anti-ranges and 
kind() as a whole, but adjust_range_with_scev() is meant to work with 
legacy ranges.

OK pending tests (provided I remove the double checking blocks :)).

Aldy