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

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

[bin.cheng]

[-- Attachment #1: Type: text/plain, Size: 180 bytes --]

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?

Thanks,
bin

[-- Attachment #2: pr100740-20210525.txt --]
[-- Type: application/octet-stream, Size: 2700 bytes --]

commit 71454637909401501ec0fa268f83db0bc8ffbc03
Author: Bin Cheng <bin.cheng@linux.alibaba.com>
Date:   Fri May 28 16:49:54 2021 +0800

    Fix overflow check in simplifying exit cond comparing two IVs.
    
    We should also check that iv1.step - iv2.step doesn't overflow,
    in addition to overflowness of the two IVs.
    
    gcc:
            PR tree-optimization/100740
            * tree-ssa-loop-niter.c (number_of_iterations_cond): Check
              overflowness for subtract operation of the two IVs.
    
    gcc/testsuite:
            * gcc.c-torture/execute/pr100740.c

diff --git a/gcc/testsuite/gcc.c-torture/execute/pr100740.c b/gcc/testsuite/gcc.c-torture/execute/pr100740.c
new file mode 100644
index 00000000000..8fcdaffef3b
--- /dev/null
+++ b/gcc/testsuite/gcc.c-torture/execute/pr100740.c
@@ -0,0 +1,11 @@
+/* PR tree-optimization/100740 */
+
+unsigned a, b;
+int main() {
+  unsigned c = 0;
+  for (a = 0; a < 2; a++)
+    for (b = 0; b < 2; b++)
+      if (++c < a)
+        __builtin_abort ();
+  return 0;
+}
diff --git a/gcc/tree-ssa-loop-niter.c b/gcc/tree-ssa-loop-niter.c
index 325bd978609..45c8d99c43d 100644
--- a/gcc/tree-ssa-loop-niter.c
+++ b/gcc/tree-ssa-loop-niter.c
@@ -1782,7 +1782,9 @@ number_of_iterations_cond (class loop *loop,
      provided that either below condition is satisfied:
 
        a) the test is NE_EXPR;
-       b) iv0.step - iv1.step is integer and iv0/iv1 don't overflow.
+       b) no overlfow happens during simplification;
+	  - iv0 and iv1 don't overflow.
+	  - iv0.step - iv1.step is integer and doesn't overflow.
 
      This rarely occurs in practice, but it is simple enough to manage.  */
   if (!integer_zerop (iv0->step) && !integer_zerop (iv1->step))
@@ -1790,14 +1792,27 @@ number_of_iterations_cond (class loop *loop,
       tree step_type = POINTER_TYPE_P (type) ? sizetype : type;
       tree step = fold_binary_to_constant (MINUS_EXPR, step_type,
 					   iv0->step, iv1->step);
+      if (code != NE_EXPR)
+	{
+	  if (TREE_CODE (step) != INTEGER_CST)
+	    return false;
+
+	  if (!iv0->no_overflow || !iv1->no_overflow)
+	    return false;
+
+	  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);
+	    }
+	  if (wrap_p)
+	    return false;
+	}
 
       /* No need to check sign of the new step since below code takes care
 	 of this well.  */
-      if (code != NE_EXPR
-	  && (TREE_CODE (step) != INTEGER_CST
-	      || !iv0->no_overflow || !iv1->no_overflow))
-	return false;
-
       iv0->step = step;
       if (!POINTER_TYPE_P (type))
 	iv0->no_overflow = false;

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

[Richard Biener]

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
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;

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

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

[Bin.Cheng]

[-- Attachment #1: Type: text/plain, Size: 2544 bytes --]

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.

> 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

[-- Attachment #2: pr100740-20210603.txt --]
[-- Type: text/plain, Size: 2764 bytes --]

From 395dd6595cabebb7fd3e71a5fbfe84544d598608 Mon Sep 17 00:00:00 2001
Author: Bin Cheng <bin.cheng@linux.alibaba.com>
Date: Fri, 28 May 2021 16:49:54 +0800
Subject: [PATCH] Simplify exit cond comparing two IVs only if they converge.

We should also check that iv1.step >= iv2.step so that the two IVs
converge to each other under comparison condition LE_EXPR/LT_EXPR.

gcc:
	PR tree-optimization/100740
	* tree-ssa-loop-niter.c (number_of_iterations_cond): Check
	  IVs converge or not.

gcc/testsuite:
	* gcc.c-torture/execute/pr100740.c
---
 .../gcc.c-torture/execute/pr100740.c          | 11 ++++++++++
 gcc/tree-ssa-loop-niter.c                     | 20 +++++++++++++------
 2 files changed, 25 insertions(+), 6 deletions(-)
 create mode 100644 gcc/testsuite/gcc.c-torture/execute/pr100740.c

diff --git a/gcc/testsuite/gcc.c-torture/execute/pr100740.c b/gcc/testsuite/gcc.c-torture/execute/pr100740.c
new file mode 100644
index 00000000000..8fcdaffef3b
--- /dev/null
+++ b/gcc/testsuite/gcc.c-torture/execute/pr100740.c
@@ -0,0 +1,11 @@
+/* PR tree-optimization/100740 */
+
+unsigned a, b;
+int main() {
+  unsigned c = 0;
+  for (a = 0; a < 2; a++)
+    for (b = 0; b < 2; b++)
+      if (++c < a)
+        __builtin_abort ();
+  return 0;
+}
diff --git a/gcc/tree-ssa-loop-niter.c b/gcc/tree-ssa-loop-niter.c
index 325bd978609..6240084782a 100644
--- a/gcc/tree-ssa-loop-niter.c
+++ b/gcc/tree-ssa-loop-niter.c
@@ -1782,7 +1782,9 @@ number_of_iterations_cond (class loop *loop,
      provided that either below condition is satisfied:
 
        a) the test is NE_EXPR;
-       b) iv0.step - iv1.step is integer and iv0/iv1 don't overflow.
+       b) iv0.step and iv1.step are integers and:
+	  - iv0 and iv1 don't overflow.
+	  - iv0 and iv1 converge to each other, under cond LE_EXPR/LT_EXPR.
 
      This rarely occurs in practice, but it is simple enough to manage.  */
   if (!integer_zerop (iv0->step) && !integer_zerop (iv1->step))
@@ -1790,14 +1792,20 @@ number_of_iterations_cond (class loop *loop,
       tree step_type = POINTER_TYPE_P (type) ? sizetype : type;
       tree step = fold_binary_to_constant (MINUS_EXPR, step_type,
 					   iv0->step, iv1->step);
+      if (code != NE_EXPR)
+	{
+	  if (TREE_CODE (step) != INTEGER_CST)
+	    return false;
+
+	  if (!iv0->no_overflow || !iv1->no_overflow)
+	    return false;
+
+	  if (tree_int_cst_lt (iv0->step, iv1->step))
+	    return false;
+	}
 
       /* No need to check sign of the new step since below code takes care
 	 of this well.  */
-      if (code != NE_EXPR
-	  && (TREE_CODE (step) != INTEGER_CST
-	      || !iv0->no_overflow || !iv1->no_overflow))
-	return false;
-
       iv0->step = step;
       if (!POINTER_TYPE_P (type))
 	iv0->no_overflow = false;
-- 
2.19.1.6.gb485710b

Re: [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

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

[Richard Biener]

[-- Attachment #1: Type: text/plain, Size: 5384 bytes --]

On Mon, Jun 7, 2021 at 4:35 PM Richard Biener
<richard.guenther@gmail.com> wrote:
>
> 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 ;)

Just to pick up things where we left them (and seeing the patch to
unti-wrap which reminded me), I've digged in myself a bit and
came to the following conclusion.

The b0 + s0 < b1 + s1 -> b0 + s0 - s1 < b1 transform is only
valid if b0 + s0 - s1 does not wrap which we can only ensure
by ensuring that b0 + s0 and b1 + s1 do not wrap (which we
already check) but also - what we're missing - that (s0 - s1)
makes b0 still evolve in the same direction (thus s0-s1 has the
same sign as s0) and that its magnitude is less that that of s0.

Extra cases could be handled if we have an upper bound for
the number of iterations from other sources, not sure if that's
worth checking.

Thus I am testing the attached now.

Hope you don't mind - and I of course welcome any comments.

Thanks,
Richard.

> 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

[-- Attachment #2: p --]
[-- Type: application/octet-stream, Size: 3044 bytes --]

From 344faea133e5b88cf72db80d54f6551349e1c36a Mon Sep 17 00:00:00 2001
From: Richard Biener <rguenther@suse.de>
Date: Thu, 1 Jul 2021 14:08:22 +0200
Subject: [PATCH] tree-optimization/100740 - fix niter analysis of two IV
 compare
To: gcc-patches@gcc.gnu.org

When transforming { b1, +, step1 } <= { b2, +, step2 } to
{ b1, +, step1 - step2 } <= b2 we have to take care to not
have the new IV wrap, otherwise, as for the testcase,
where we transform { 1u, +, 1u } <= { 4u, +, 2u } to
{ 1u, +, -1u } <= 4u this is not valid.

2021-07-01  Bin Cheng  <bin.cheng@linux.alibaba.com>
	    Richard Biener  <rguenther@suse.de>

	PR tree-optimization/100740
	* tree-ssa-loop-niter.c (number_of_iterations_cond): Check
	the simplified IV does not wrap.

	* gcc.dg/torture/pr100740.c: New testcase.
---
 gcc/testsuite/gcc.dg/torture/pr100740.c | 14 ++++++++++++++
 gcc/tree-ssa-loop-niter.c               | 22 ++++++++++++++++------
 2 files changed, 30 insertions(+), 6 deletions(-)
 create mode 100644 gcc/testsuite/gcc.dg/torture/pr100740.c

diff --git a/gcc/testsuite/gcc.dg/torture/pr100740.c b/gcc/testsuite/gcc.dg/torture/pr100740.c
new file mode 100644
index 00000000000..3479e1d5d89
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/torture/pr100740.c
@@ -0,0 +1,14 @@
+/* { dg-do run } */
+
+unsigned a;
+int main()
+{
+  unsigned c = 0;
+  for (a = 0; a < 16; a++)
+    {
+      c += 2;
+      if (c < a)
+        __builtin_abort ();
+    }
+  return 0;
+}
diff --git a/gcc/tree-ssa-loop-niter.c b/gcc/tree-ssa-loop-niter.c
index b5add827018..707eac17646 100644
--- a/gcc/tree-ssa-loop-niter.c
+++ b/gcc/tree-ssa-loop-niter.c
@@ -1814,7 +1814,8 @@ number_of_iterations_cond (class loop *loop,
      provided that either below condition is satisfied:
 
        a) the test is NE_EXPR;
-       b) iv0.step - iv1.step is integer and iv0/iv1 don't overflow.
+       b) iv0.step - iv1.step is integer and neither the old
+	  nor the new IV overflow.
 
      This rarely occurs in practice, but it is simple enough to manage.  */
   if (!integer_zerop (iv0->step) && !integer_zerop (iv1->step))
@@ -1823,13 +1824,22 @@ number_of_iterations_cond (class loop *loop,
       tree step = fold_binary_to_constant (MINUS_EXPR, step_type,
 					   iv0->step, iv1->step);
 
+      if (code != NE_EXPR)
+	{
+	  if (TREE_CODE (step) != INTEGER_CST)
+	    return false;
+	  if (!iv0->no_overflow || !iv1->no_overflow)
+	    return false;
+	  /* The new IV does not overflow if the step has the same
+	     sign and is less in magnitude.  */
+	  if (tree_int_cst_sign_bit (iv0->step) != tree_int_cst_sign_bit (step)
+	      || wi::geu_p (wi::abs (wi::to_wide (step)),
+			    wi::abs (wi::to_wide (iv0->step))))
+	    return false;
+	}
+
       /* No need to check sign of the new step since below code takes care
 	 of this well.  */
-      if (code != NE_EXPR
-	  && (TREE_CODE (step) != INTEGER_CST
-	      || !iv0->no_overflow || !iv1->no_overflow))
-	return false;
-
       iv0->step = step;
       if (!POINTER_TYPE_P (type))
 	iv0->no_overflow = false;
-- 
2.26.2

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

[Bin.Cheng]

On Thu, Jul 1, 2021 at 8:19 PM Richard Biener
<richard.guenther@gmail.com> wrote:
>
> On Mon, Jun 7, 2021 at 4:35 PM Richard Biener
> <richard.guenther@gmail.com> wrote:
> >
> > 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 ;)
>
> Just to pick up things where we left them (and seeing the patch to
> unti-wrap which reminded me), I've digged in myself a bit and
> came to the following conclusion.
>
> The b0 + s0 < b1 + s1 -> b0 + s0 - s1 < b1 transform is only
> valid if b0 + s0 - s1 does not wrap which we can only ensure
> by ensuring that b0 + s0 and b1 + s1 do not wrap (which we
> already check) but also - what we're missing - that (s0 - s1)
> makes b0 still evolve in the same direction (thus s0-s1 has the
> same sign as s0) and that its magnitude is less that that of s0.
>
> Extra cases could be handled if we have an upper bound for
> the number of iterations from other sources, not sure if that's
> worth checking.
>
> Thus I am testing the attached now.
>
> Hope you don't mind - and I of course welcome any comments.
Oh, not at all.  Your help on these issues are greatly appreciated.

As for the change:

> +         if (tree_int_cst_sign_bit (iv0->step) != tree_int_cst_sign_bit (step)
> +             || wi::geu_p (wi::abs (wi::to_wide (step)),
> +                           wi::abs (wi::to_wide (iv0->step))))
It returns false on condition "{base, 5}_iv0 < {base, -1}_iv1", but
this is like the "convergence" case I mentioned and could be analyzed?

Thanks,
bin
> +           return false;
> +       }


Thanks,
bin
>
> Thanks,
> Richard.
>
> > 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

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

[Richard Biener]

On Fri, Jul 2, 2021 at 3:37 AM Bin.Cheng <amker.cheng@gmail.com> wrote:
>
> On Thu, Jul 1, 2021 at 8:19 PM Richard Biener
> <richard.guenther@gmail.com> wrote:
> >
> > On Mon, Jun 7, 2021 at 4:35 PM Richard Biener
> > <richard.guenther@gmail.com> wrote:
> > >
> > > 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 ;)
> >
> > Just to pick up things where we left them (and seeing the patch to
> > unti-wrap which reminded me), I've digged in myself a bit and
> > came to the following conclusion.
> >
> > The b0 + s0 < b1 + s1 -> b0 + s0 - s1 < b1 transform is only
> > valid if b0 + s0 - s1 does not wrap which we can only ensure
> > by ensuring that b0 + s0 and b1 + s1 do not wrap (which we
> > already check) but also - what we're missing - that (s0 - s1)
> > makes b0 still evolve in the same direction (thus s0-s1 has the
> > same sign as s0) and that its magnitude is less that that of s0.
> >
> > Extra cases could be handled if we have an upper bound for
> > the number of iterations from other sources, not sure if that's
> > worth checking.
> >
> > Thus I am testing the attached now.
> >
> > Hope you don't mind - and I of course welcome any comments.
> Oh, not at all.  Your help on these issues are greatly appreciated.
>
> As for the change:
>
> > +         if (tree_int_cst_sign_bit (iv0->step) != tree_int_cst_sign_bit (step)
> > +             || wi::geu_p (wi::abs (wi::to_wide (step)),
> > +                           wi::abs (wi::to_wide (iv0->step))))
> It returns false on condition "{base, 5}_iv0 < {base, -1}_iv1", but
> this is like the "convergence" case I mentioned and could be analyzed?

Yes, I think so.  I just didn't manage to convince myself that a simple
step0 < step1 check is enough to ensure convergence.  So I settled
on the argument that the general
  x + CST1 < y + CST2   ->   X + CST1 - CST2 < y
transform is valid if the original adds did not wrap and the new
adds do not either.  Your step0 < step1 check would say converging
for {base, -1}_iv0 < {base, 1}_iv1 and that looked wrong - OTOH then
maybe we'd have computed iv0->no_overflow or iv1->no_overflow
to false since if the IVs do not converge there must be overflow for
the condition to switch from false to true (or vice versa)?  But then
the check would be not needed at all.

Hmm, so maybe our testcase analysis is wrong given the exit
we compute the wrong number of iterations is never taken, and when
it would be take the IVs would have wrapped but we likely computed
->no_overflow based on the _other_ exit which puts an upper bound
on the number of iterations ...?

So maybe adjust_cond_for_loop_until_wrap which is what in the
end adjusts things for the computation of the bogus niters assumes
the exit analyzed is eventually taken and that's a wrong assumption?

Richard.

> Thanks,
> bin
> > +           return false;
> > +       }
>
>
> Thanks,
> bin
> >
> > Thanks,
> > Richard.
> >
> > > 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