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

[Bin.Cheng]

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
-------------- next part --------------
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