[PATCH PR100740]Fix overflow check in simplifying exit cond comparing two IVs.

[Richard Biener]

On Sun, Jun 6, 2021 at 12:01 PM Bin.Cheng <amker.cheng@gmail.com> wrote:
>
> On Wed, Jun 2, 2021 at 3:28 PM Richard Biener via Gcc-patches
> <gcc-patches@gcc.gnu.org> wrote:
> >
> > On Tue, Jun 1, 2021 at 4:00 PM bin.cheng via Gcc-patches
> > <gcc-patches@gcc.gnu.org> wrote:
> > >
> > > Hi,
> > > As described in patch summary, this fixes the wrong code issue by adding overflow-ness
> > > check for iv1.step - iv2.step.
> > >
> > > Bootstrap and test on x86_64.  Any comments?
> >
> > +         bool wrap_p = TYPE_OVERFLOW_WRAPS (step_type);
> > +         if (wrap_p)
> > +           {
> > +             tree t = fold_binary_to_constant (GE_EXPR, step_type,
> > +                                               iv0->step, iv1->step);
> > +             wrap_p = integer_zerop (t);
> > +           }
> >
> > I think we can't use TYPE_OVERFLOW_WRAPS/TYPE_OVERFLOW_UNDEFINED since
> > that's only relevant for expressions written by the user - we're
> > computing iv0.step - iv1.step
> > which can even overflow when TYPE_OVERFLOW_UNDEFINED (in fact we may not
> > even generate this expression then!).  So I think we have to do sth like
> >
> >    /* If the iv0->step - iv1->step wraps, fail.  */
> >    if (!operand_equal_p (iv0->step, iv1->step)
> >        && (TREE_CODE (iv0->step) != INTEGER_CST || TREE_CODE
> > (iv1->step) != INTEGER_CST)
> >        && !wi::gt (wi::to_widest (iv0->step), wi::to_widest (iv1->step))
> >      return false;
> >
> > which only handles equality and all integer constant steps. You could
> Thanks for the suggestion.  I realized that we have LE/LT/NE
> conditions here, and for LE/LT what we need to check is iv0/iv1
> converge to each other, rather than diverge.  Also steps here can only
> be constants, so there is no need to use range information.

Ah, that simplifies things.

+         if (tree_int_cst_lt (iv0->step, iv1->step))
+           return false;

so it looks to me that iv?->step can be negative which means we should
verify that abs(iv0->step - iv1->step) <= abs (iv0->step), correct?

       tree step = fold_binary_to_constant (MINUS_EXPR, step_type,
                                           iv0->step, iv1->step);
...
+         if (TREE_CODE (step) != INTEGER_CST)
+           return false;

note fold_binary_to_constant will return NULL if the result is not
TREE_CONSTANT (which would also include symbolic constants
like &a - &b).  It wasn't checked before, of course but since we're
touching the code we might very well be checking for NULL step ...
(or assert it is not for documentation purposes).

That said, if iv0->step and iv1->step are known INTEGER_CSTs
(I think they indeed are given the constraints we impose on
simple_iv_with_niters).

That said, with just a quick look again it looks to me the
IV1 {<=,<} IV2 transform to IV1 - IV2step {<=,<} IV2base
is OK whenever the effective step magnitude on the IV1'
decreases, thus abs(IV1.step - IV2.step) <= abs(IV1.step)
since then IV1 is still guaranteed to not overflow.  But
for example {0, +, 1} and {10, -, 1} also converge if the
number of iterations is less than 10 but they would not pass
this criteria.  So I'm not sure "convergence" is a good wording
here - but maybe I'm missing some critical piece of understanding
here.

But in any case it looks like we're on the right track ;)

Thanks,
Richard.

> > also use ranges
> > like
> >
> >  wide_int min0, max0, min1, max1;
> >   if (!operand_equal_p (iv->step, iv1->step)
> >       && (determine_value_range (iv0->step, &min0, &max0) != VR_RANGE
> >              || determine_value_range (iv1->step, &min1, &max1) != VR_RANGE
> >              || !wi::ge (min0, max1)))
> >    return false;
> >
> > Note I'm not sure why
> >
> >        iv0->step = step;
> >        if (!POINTER_TYPE_P (type))
> >         iv0->no_overflow = false;
> I don't exactly remember, this was added sometime when no_overflow was
> introduced.  Note we only do various checks for non NE_EXPR so the
> step isn't always less in absolute value?  I will check if we should
> reset it in all cases.
>
> Patch updated.  test ongoing.
>
> Thanks,
> bin
> >
> > here the no_overflow reset does not happen for pointer types?  Or
> > rather why does
> > it happen at all?  Don't we strictly make the step less in absolute value?
> >
> > > Thanks,
> > > bin