[PATCH PR84648]Adjust loop exit conditions for loop-until-wrap cases.

[PATCH PR84648]Adjust loop exit conditions for loop-until-wrap cases.

[bin.cheng]

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

Hi,
This patch fixes PR84648 by adjusting exit conditions for loop-until-wrap cases.
It only handles simple cases in which IV.base are constants because we rely on
current niter analyzer which doesn't handle parameterized bound in wrapped
case.  It could be relaxed in the future.

Bootstrap and test on x86_64 in progress.

Thanks,
bin
2018-11-11  Bin Cheng  <bin.cheng@linux.alibaba.com>

        PR tree-optimization/84648
        * tree-ssa-loop-niter.c (adjust_cond_for_loop_until_wrap): New.
        (number_of_iterations_cond): Adjust exit cond for loop-until-wrap case
        by calling adjust_cond_for_loop_until_wrap.

2018-11-11  Bin Cheng  <bin.cheng@linux.alibaba.com>

        PR tree-optimization/84648
        * gcc.dg/tree-ssa/pr84648.c: New test.

[-- Attachment #2: 0001-Fix-pr84648-by-adjusting-exit-cond-for-loop-until-wr.patch --]
[-- Type: application/octet-stream, Size: 4604 bytes --]

From ba3112dd24441542188830cec8473f341bfd3669 Mon Sep 17 00:00:00 2001
From: chengbin <bin.cheng@linux.alibaba.com>
Date: Sun, 11 Nov 2018 15:42:46 +0800
Subject: [PATCH] Fix pr84648 by adjusting exit cond for loop-until-wrap

---
 gcc/testsuite/gcc.dg/tree-ssa/pr84648.c | 10 +++++
 gcc/tree-ssa-loop-niter.c               | 73 ++++++++++++++++++++++++++++-----
 2 files changed, 73 insertions(+), 10 deletions(-)
 create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/pr84648.c

diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr84648.c b/gcc/testsuite/gcc.dg/tree-ssa/pr84648.c
new file mode 100644
index 00000000000..6ff5a07cd20
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/pr84648.c
@@ -0,0 +1,10 @@
+/* { dg-do compile } */
+/* { dg-options "-O3 -fdump-tree-cddce1-details" } */
+
+int main() {
+    for (unsigned i = 0; i < (1u << 31); ++i) {
+    }
+    return 0;
+}
+
+/* { dg-final { scan-tree-dump-times "Found loop 1 to be finite: upper bound found" 1 "cddce1" } } */
diff --git a/gcc/tree-ssa-loop-niter.c b/gcc/tree-ssa-loop-niter.c
index e763b35ee84..d15a2ca6887 100644
--- a/gcc/tree-ssa-loop-niter.c
+++ b/gcc/tree-ssa-loop-niter.c
@@ -1641,6 +1641,60 @@ dump_affine_iv (FILE *file, affine_iv *iv)
     }
 }
 
+/* Given exit condition IV0 CODE IV1 in TYPE, this function adjusts
+   the condition for loop-until-wrap cases.  For example:
+     (unsigned){8, -1}_loop < 10        => {0, 1} != 9
+     10 < (unsigned){0, max - 7}_loop   => {0, 1} != 8
+   Return true if condition is successfully adjusted.  */
+
+static bool
+adjust_cond_for_loop_until_wrap (tree type, affine_iv *iv0,
+				 enum tree_code *code, affine_iv *iv1)
+{
+  /* Only support simple cases for the moment.  */
+  if (TREE_CODE (iv0->base) != INTEGER_CST
+      || TREE_CODE (iv1->base) != INTEGER_CST)
+    return false;
+
+  tree niter_type = unsigned_type_for (type), high, low;
+  /* Case: i-- < 10.  */
+  if (integer_zerop (iv1->step))
+    {
+      /* TODO: Should handle case in which abs(step) != 1.  */
+      if (!integer_minus_onep (iv0->step))
+	return false;
+      /* Give up on infinite loop.  */
+      if (*code == LE_EXPR && wi::to_wide (iv1->base) == wi::max_value (type))
+	return false;
+      high = fold_build2 (PLUS_EXPR, niter_type,
+			  fold_convert (niter_type, iv0->base),
+			  fold_convert (niter_type, integer_one_node));
+      low = fold_convert (niter_type, TYPE_MIN_VALUE (type));
+    }
+  else if (integer_zerop (iv0->step))
+    {
+      /* TODO: Should handle case in which abs(step) != 1.  */
+      if (!integer_onep (iv1->step))
+	return false;
+      /* Give up on infinite loop.  */
+      if (*code == LE_EXPR && wi::to_wide (iv0->base) == wi::min_value (type))
+	return false;
+      high = fold_convert (niter_type, TYPE_MAX_VALUE (type));
+      low = fold_build2 (MINUS_EXPR, niter_type,
+			 fold_convert (niter_type, iv1->base),
+			 fold_convert (niter_type, integer_one_node));
+    }
+  else
+    gcc_unreachable ();
+
+  iv0->base = low;
+  iv0->step = fold_convert (niter_type, integer_one_node);
+  iv1->base = high;
+  iv1->step = integer_zero_node;
+  *code = NE_EXPR;
+  return true;
+}
+
 /* Determine the number of iterations according to condition (for staying
    inside loop) which compares two induction variables using comparison
    operator CODE.  The induction variable on left side of the comparison
@@ -1764,16 +1818,6 @@ number_of_iterations_cond (struct loop *loop,
   if (integer_zerop (iv0->step) && integer_zerop (iv1->step))
     return false;
 
-  /* Ignore loops of while (i-- < 10) type.  */
-  if (code != NE_EXPR)
-    {
-      if (iv0->step && tree_int_cst_sign_bit (iv0->step))
-	return false;
-
-      if (!integer_zerop (iv1->step) && !tree_int_cst_sign_bit (iv1->step))
-	return false;
-    }
-
   /* If the loop exits immediately, there is nothing to do.  */
   tree tem = fold_binary (code, boolean_type_node, iv0->base, iv1->base);
   if (tem && integer_zerop (tem))
@@ -1783,6 +1827,15 @@ number_of_iterations_cond (struct loop *loop,
       return true;
     }
 
+  /* Handle special case loops: while (i-- < 10) and while (10 < i++) by
+     adjusting iv0, iv1 and code.  */
+  if (code != NE_EXPR
+      && (tree_int_cst_sign_bit (iv0->step)
+	  || (!integer_zerop (iv1->step)
+	      && !tree_int_cst_sign_bit (iv1->step)))
+      && !adjust_cond_for_loop_until_wrap (type, iv0, &code, iv1))
+    return false;
+
   /* OK, now we know we have a senseful loop.  Handle several cases, depending
      on what comparison operator is used.  */
   bound_difference (loop, iv1->base, iv0->base, &bnds);
-- 
2.14.4.44.g2045bb6

Re: [PATCH PR84648]Adjust loop exit conditions for loop-until-wrap cases.

[Bernhard Reutner-Fischer]

On Sun, 11 Nov 2018 16:02:33 +0800
"bin.cheng" <bin.cheng@linux.alibaba.com> wrote:

Quick observation unrelated to the real patch.

I think the coding style mandates to use the type itself and not the
underlying structure.

I know there are alot of places from before our switch to C++ that
still use enum tree_code or enum machine_mode, but new code should
adhere to the style please.

So: s/enum tree_code/tree_code/g

thanks,

Re: [PATCH PR84648]Adjust loop exit conditions for loop-until-wrap cases.

[Bin.Cheng]

On Sun, Nov 11, 2018 at 7:20 PM Bernhard Reutner-Fischer
<rep.dot.nop@gmail.com> wrote:
>
> On Sun, 11 Nov 2018 16:02:33 +0800
> "bin.cheng" <bin.cheng@linux.alibaba.com> wrote:
>
> Quick observation unrelated to the real patch.
>
> I think the coding style mandates to use the type itself and not the
> underlying structure.
>
> I know there are alot of places from before our switch to C++ that
> still use enum tree_code or enum machine_mode, but new code should
> adhere to the style please.
>
> So: s/enum tree_code/tree_code/g
Thanks very much for reminding, I forgot the switch when writing the
patch, will update along with changes for other reviews.

Thanks,
bin
>
> thanks,

Re: [PATCH PR84648]Adjust loop exit conditions for loop-until-wrap cases.

[Richard Biener]

On Sun, Nov 11, 2018 at 9:02 AM bin.cheng <bin.cheng@linux.alibaba.com> wrote:
>
> Hi,
> This patch fixes PR84648 by adjusting exit conditions for loop-until-wrap cases.
> It only handles simple cases in which IV.base are constants because we rely on
> current niter analyzer which doesn't handle parameterized bound in wrapped
> case.  It could be relaxed in the future.
>
> Bootstrap and test on x86_64 in progress.

Please use TYPE_MIN/MAX_VALUE or wi::min/max_value consistently.
Either tree_int_cst_equal (iv0->base, TYPE_MIN_VALUE (type)) or
wide_int_to_tree (niter_type, wi::max_value (TYPE_PRECISION (type),
TYPE_SIGN (type))).

Also

+  iv0->base = low;
+  iv0->step = fold_convert (niter_type, integer_one_node);

build_int_cst (niter_type, 1);

+  iv1->base = high;
+  iv1->step = integer_zero_node;

build_int_cst (niter_type, 0);

With the code, what happens to signed IVs?  I suppose we figure out things
earlier by means of undefined overflow?

Apart from the above nits OK for trunk.

Thanks,
Richard.

> Thanks,
> bin
> 2018-11-11  Bin Cheng  <bin.cheng@linux.alibaba.com>
>
>         PR tree-optimization/84648
>         * tree-ssa-loop-niter.c (adjust_cond_for_loop_until_wrap): New.
>         (number_of_iterations_cond): Adjust exit cond for loop-until-wrap case
>         by calling adjust_cond_for_loop_until_wrap.
>
> 2018-11-11  Bin Cheng  <bin.cheng@linux.alibaba.com>
>
>         PR tree-optimization/84648
>         * gcc.dg/tree-ssa/pr84648.c: New test.

Re: [PATCH PR84648]Adjust loop exit conditions for loop-until-wrap cases.

[bin.cheng]

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

------------------------------------------------------------------
Sender:Richard Biener <richard.guenther@gmail.com>
Sent at:2018 Nov 13 (Tue) 23:03
To:bin.cheng <bin.cheng@linux.alibaba.com>
Cc:GCC Patches <gcc-patches@gcc.gnu.org>
Subject:Re: [PATCH PR84648]Adjust loop exit conditions for loop-until-wrap cases.

> 
> On Sun, Nov 11, 2018 at 9:02 AM bin.cheng <bin.cheng@linux.alibaba.com> wrote:
>>
>> Hi,
>> This patch fixes PR84648 by adjusting exit conditions for loop-until-wrap cases.
>> It only handles simple cases in which IV.base are constants because we rely on
>> current niter analyzer which doesn't handle parameterized bound in wrapped
>> case.  It could be relaxed in the future.
>>
>> Bootstrap and test on x86_64 in progress.
> 
> Please use TYPE_MIN/MAX_VALUE or wi::min/max_value consistently.
> Either tree_int_cst_equal (iv0->base, TYPE_MIN_VALUE (type)) or
> wide_int_to_tree (niter_type, wi::max_value (TYPE_PRECISION (type),
> TYPE_SIGN (type))).
> 
> Also
> 
> +  iv0->base = low;
> +  iv0->step = fold_convert (niter_type, integer_one_node);
> 
> build_int_cst (niter_type, 1);
> 
> +  iv1->base = high;
> +  iv1->step = integer_zero_node;
> 
> build_int_cst (niter_type, 0);
Fixed, thanks for reviewing.

> 
> With the code, what happens to signed IVs?  I suppose we figure out things
> earlier by means of undefined overflow?
The code takes advantage of signed undefined overflow and handle it as wrap.
In the reported test case, we have following IL:
  <bb 2> :
  goto <bb 4>; [INV]

  <bb 3> :
  i_4 = i_2 + 1;

  <bb 4> :
  # i_2 = PHI <0(2), i_4(3)>
  i.0_1 = (signed int) i_2;
  if (i.0_1 >= 0)
    goto <bb 3>; [INV]
  else
    goto <bb 5>; [INV]

So the IV is actually transformed into signed int, we rely on scev to understand
type conversion correctly and generate (int){0, 1} for i.0_1.  Is this reasonable?

Updated patch attached, bootstrap and test on x86_64.

Thanks,
bin

2018-11-11  Bin Cheng  <bin.cheng@linux.alibaba.com>

        PR tree-optimization/84648
        * tree-ssa-loop-niter.c (adjust_cond_for_loop_until_wrap): New.
        (number_of_iterations_cond): Adjust exit cond for loop-until-wrap case
        by calling adjust_cond_for_loop_until_wrap.

2018-11-11  Bin Cheng  <bin.cheng@linux.alibaba.com>

        PR tree-optimization/84648
        * gcc.dg/tree-ssa/pr84648.c: New test.
        * gcc.dg/pr68317.c: Add warning check on overflow.

[-- Attachment #2: pr84648-20181114.txt --]
[-- Type: application/octet-stream, Size: 4595 bytes --]

diff --git a/gcc/testsuite/gcc.dg/pr68317.c b/gcc/testsuite/gcc.dg/pr68317.c
index 7b565639588..9ba6fb075e6 100644
--- a/gcc/testsuite/gcc.dg/pr68317.c
+++ b/gcc/testsuite/gcc.dg/pr68317.c
@@ -11,5 +11,5 @@ foo ()
  for (index; index <= 10; index--)
    /* Result of the following multiply will overflow
       when converted to signed int.  */
-   bar ((0xcafe + index) * 0xdead);
+   bar ((0xcafe + index) * 0xdead);  /* { dg-warning "iteration \[0-9\]+ invokes undefined behavior" } */
 }
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr84648.c b/gcc/testsuite/gcc.dg/tree-ssa/pr84648.c
new file mode 100644
index 00000000000..6ff5a07cd20
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/pr84648.c
@@ -0,0 +1,10 @@
+/* { dg-do compile } */
+/* { dg-options "-O3 -fdump-tree-cddce1-details" } */
+
+int main() {
+    for (unsigned i = 0; i < (1u << 31); ++i) {
+    }
+    return 0;
+}
+
+/* { dg-final { scan-tree-dump-times "Found loop 1 to be finite: upper bound found" 1 "cddce1" } } */
diff --git a/gcc/tree-ssa-loop-niter.c b/gcc/tree-ssa-loop-niter.c
index e763b35ee84..a8a7bcb8015 100644
--- a/gcc/tree-ssa-loop-niter.c
+++ b/gcc/tree-ssa-loop-niter.c
@@ -1641,6 +1641,62 @@ dump_affine_iv (FILE *file, affine_iv *iv)
     }
 }
 
+/* Given exit condition IV0 CODE IV1 in TYPE, this function adjusts
+   the condition for loop-until-wrap cases.  For example:
+     (unsigned){8, -1}_loop < 10        => {0, 1} != 9
+     10 < (unsigned){0, max - 7}_loop   => {0, 1} != 8
+   Return true if condition is successfully adjusted.  */
+
+static bool
+adjust_cond_for_loop_until_wrap (tree type, affine_iv *iv0, tree_code *code,
+				 affine_iv *iv1)
+{
+  /* Only support simple cases for the moment.  */
+  if (TREE_CODE (iv0->base) != INTEGER_CST
+      || TREE_CODE (iv1->base) != INTEGER_CST)
+    return false;
+
+  tree niter_type = unsigned_type_for (type), high, low;
+  /* Case: i-- < 10.  */
+  if (integer_zerop (iv1->step))
+    {
+      /* TODO: Should handle case in which abs(step) != 1.  */
+      if (!integer_minus_onep (iv0->step))
+	return false;
+      /* Give up on infinite loop.  */
+      if (*code == LE_EXPR
+	  && tree_int_cst_equal (iv1->base, TYPE_MAX_VALUE (type)))
+	return false;
+      high = fold_build2 (PLUS_EXPR, niter_type,
+			  fold_convert (niter_type, iv0->base),
+			  build_int_cst (niter_type, 1));
+      low = fold_convert (niter_type, TYPE_MIN_VALUE (type));
+    }
+  else if (integer_zerop (iv0->step))
+    {
+      /* TODO: Should handle case in which abs(step) != 1.  */
+      if (!integer_onep (iv1->step))
+	return false;
+      /* Give up on infinite loop.  */
+      if (*code == LE_EXPR
+	  && tree_int_cst_equal (iv0->base, TYPE_MIN_VALUE (type)))
+	return false;
+      high = fold_convert (niter_type, TYPE_MAX_VALUE (type));
+      low = fold_build2 (MINUS_EXPR, niter_type,
+			 fold_convert (niter_type, iv1->base),
+			 build_int_cst (niter_type, 1));
+    }
+  else
+    gcc_unreachable ();
+
+  iv0->base = low;
+  iv0->step = fold_convert (niter_type, integer_one_node);
+  iv1->base = high;
+  iv1->step = build_int_cst (niter_type, 0);
+  *code = NE_EXPR;
+  return true;
+}
+
 /* Determine the number of iterations according to condition (for staying
    inside loop) which compares two induction variables using comparison
    operator CODE.  The induction variable on left side of the comparison
@@ -1764,16 +1820,6 @@ number_of_iterations_cond (struct loop *loop,
   if (integer_zerop (iv0->step) && integer_zerop (iv1->step))
     return false;
 
-  /* Ignore loops of while (i-- < 10) type.  */
-  if (code != NE_EXPR)
-    {
-      if (iv0->step && tree_int_cst_sign_bit (iv0->step))
-	return false;
-
-      if (!integer_zerop (iv1->step) && !tree_int_cst_sign_bit (iv1->step))
-	return false;
-    }
-
   /* If the loop exits immediately, there is nothing to do.  */
   tree tem = fold_binary (code, boolean_type_node, iv0->base, iv1->base);
   if (tem && integer_zerop (tem))
@@ -1783,6 +1829,15 @@ number_of_iterations_cond (struct loop *loop,
       return true;
     }
 
+  /* Handle special case loops: while (i-- < 10) and while (10 < i++) by
+     adjusting iv0, iv1 and code.  */
+  if (code != NE_EXPR
+      && (tree_int_cst_sign_bit (iv0->step)
+	  || (!integer_zerop (iv1->step)
+	      && !tree_int_cst_sign_bit (iv1->step)))
+      && !adjust_cond_for_loop_until_wrap (type, iv0, &code, iv1))
+    return false;
+
   /* OK, now we know we have a senseful loop.  Handle several cases, depending
      on what comparison operator is used.  */
   bound_difference (loop, iv1->base, iv0->base, &bnds);

Re: [PATCH PR84648]Adjust loop exit conditions for loop-until-wrap cases.

[Richard Biener]

On Wed, Nov 14, 2018 at 11:09 AM bin.cheng <bin.cheng@linux.alibaba.com> wrote:
>
> ------------------------------------------------------------------
> Sender:Richard Biener <richard.guenther@gmail.com>
> Sent at:2018 Nov 13 (Tue) 23:03
> To:bin.cheng <bin.cheng@linux.alibaba.com>
> Cc:GCC Patches <gcc-patches@gcc.gnu.org>
> Subject:Re: [PATCH PR84648]Adjust loop exit conditions for loop-until-wrap cases.
>
> >
> > On Sun, Nov 11, 2018 at 9:02 AM bin.cheng <bin.cheng@linux.alibaba.com> wrote:
> >>
> >> Hi,
> >> This patch fixes PR84648 by adjusting exit conditions for loop-until-wrap cases.
> >> It only handles simple cases in which IV.base are constants because we rely on
> >> current niter analyzer which doesn't handle parameterized bound in wrapped
> >> case.  It could be relaxed in the future.
> >>
> >> Bootstrap and test on x86_64 in progress.
> >
> > Please use TYPE_MIN/MAX_VALUE or wi::min/max_value consistently.
> > Either tree_int_cst_equal (iv0->base, TYPE_MIN_VALUE (type)) or
> > wide_int_to_tree (niter_type, wi::max_value (TYPE_PRECISION (type),
> > TYPE_SIGN (type))).
> >
> > Also
> >
> > +  iv0->base = low;
> > +  iv0->step = fold_convert (niter_type, integer_one_node);
> >
> > build_int_cst (niter_type, 1);
> >
> > +  iv1->base = high;
> > +  iv1->step = integer_zero_node;
> >
> > build_int_cst (niter_type, 0);
> Fixed, thanks for reviewing.
>
> >
> > With the code, what happens to signed IVs?  I suppose we figure out things
> > earlier by means of undefined overflow?
> The code takes advantage of signed undefined overflow and handle it as wrap.
> In the reported test case, we have following IL:
>   <bb 2> :
>   goto <bb 4>; [INV]
>
>   <bb 3> :
>   i_4 = i_2 + 1;
>
>   <bb 4> :
>   # i_2 = PHI <0(2), i_4(3)>
>   i.0_1 = (signed int) i_2;
>   if (i.0_1 >= 0)
>     goto <bb 3>; [INV]
>   else
>     goto <bb 5>; [INV]
>
> So the IV is actually transformed into signed int, we rely on scev to understand
> type conversion correctly and generate (int){0, 1} for i.0_1.  Is this reasonable?

I think so.

> Updated patch attached, bootstrap and test on x86_64.

OK.

Thanks,
Richard.

> Thanks,
> bin
>
> 2018-11-11  Bin Cheng  <bin.cheng@linux.alibaba.com>
>
>         PR tree-optimization/84648
>         * tree-ssa-loop-niter.c (adjust_cond_for_loop_until_wrap): New.
>         (number_of_iterations_cond): Adjust exit cond for loop-until-wrap case
>         by calling adjust_cond_for_loop_until_wrap.
>
> 2018-11-11  Bin Cheng  <bin.cheng@linux.alibaba.com>
>
>         PR tree-optimization/84648
>         * gcc.dg/tree-ssa/pr84648.c: New test.
>         * gcc.dg/pr68317.c: Add warning check on overflow.

Re: [PATCH PR84648]Adjust loop exit conditions for loop-until-wrap cases.

[Christophe Lyon]

On Wed, 14 Nov 2018 at 11:10, bin.cheng <bin.cheng@linux.alibaba.com> wrote:
>
> ------------------------------------------------------------------
> Sender:Richard Biener <richard.guenther@gmail.com>
> Sent at:2018 Nov 13 (Tue) 23:03
> To:bin.cheng <bin.cheng@linux.alibaba.com>
> Cc:GCC Patches <gcc-patches@gcc.gnu.org>
> Subject:Re: [PATCH PR84648]Adjust loop exit conditions for loop-until-wrap cases.
>
> >
> > On Sun, Nov 11, 2018 at 9:02 AM bin.cheng <bin.cheng@linux.alibaba.com> wrote:
> >>
> >> Hi,
> >> This patch fixes PR84648 by adjusting exit conditions for loop-until-wrap cases.
> >> It only handles simple cases in which IV.base are constants because we rely on
> >> current niter analyzer which doesn't handle parameterized bound in wrapped
> >> case.  It could be relaxed in the future.
> >>
> >> Bootstrap and test on x86_64 in progress.
> >
> > Please use TYPE_MIN/MAX_VALUE or wi::min/max_value consistently.
> > Either tree_int_cst_equal (iv0->base, TYPE_MIN_VALUE (type)) or
> > wide_int_to_tree (niter_type, wi::max_value (TYPE_PRECISION (type),
> > TYPE_SIGN (type))).
> >
> > Also
> >
> > +  iv0->base = low;
> > +  iv0->step = fold_convert (niter_type, integer_one_node);
> >
> > build_int_cst (niter_type, 1);
> >
> > +  iv1->base = high;
> > +  iv1->step = integer_zero_node;
> >
> > build_int_cst (niter_type, 0);
> Fixed, thanks for reviewing.
>
> >
> > With the code, what happens to signed IVs?  I suppose we figure out things
> > earlier by means of undefined overflow?
> The code takes advantage of signed undefined overflow and handle it as wrap.
> In the reported test case, we have following IL:
>   <bb 2> :
>   goto <bb 4>; [INV]
>
>   <bb 3> :
>   i_4 = i_2 + 1;
>
>   <bb 4> :
>   # i_2 = PHI <0(2), i_4(3)>
>   i.0_1 = (signed int) i_2;
>   if (i.0_1 >= 0)
>     goto <bb 3>; [INV]
>   else
>     goto <bb 5>; [INV]
>
> So the IV is actually transformed into signed int, we rely on scev to understand
> type conversion correctly and generate (int){0, 1} for i.0_1.  Is this reasonable?
>
> Updated patch attached, bootstrap and test on x86_64.
>
> Thanks,
> bin
>
> 2018-11-11  Bin Cheng  <bin.cheng@linux.alibaba.com>
>
>         PR tree-optimization/84648
>         * tree-ssa-loop-niter.c (adjust_cond_for_loop_until_wrap): New.
>         (number_of_iterations_cond): Adjust exit cond for loop-until-wrap case
>         by calling adjust_cond_for_loop_until_wrap.
>
> 2018-11-11  Bin Cheng  <bin.cheng@linux.alibaba.com>
>
>         PR tree-optimization/84648
>         * gcc.dg/tree-ssa/pr84648.c: New test.
>         * gcc.dg/pr68317.c: Add warning check on overflow.


Hi Bin,

Since you committed this patch (r266171), I've noticed a regression
in fortran:
FAIL: gfortran.dg/transfer_intrinsic_3.f90   -O3 -fomit-frame-pointer
-funroll-loops -fpeel-loops -ftracer -finline-functions  execution
test
FAIL: gfortran.dg/transfer_intrinsic_3.f90   -O3 -g  execution test
on arm-none-linux-gnueabihf
--with-cpu cortex-a5
--with-fpu vfpv3-d16-fp16

cortex-a9+neon-fp16, cortex-a15+neon-vfpv4 and
cortex-a57+crypto-neon-fp-armv8 are still OK.

Christophe

Re: [PATCH PR84648]Adjust loop exit conditions for loop-until-wrap cases.

[Bin.Cheng]

On Mon, Nov 19, 2018 at 9:17 PM Christophe Lyon
<christophe.lyon@linaro.org> wrote:
>
> On Wed, 14 Nov 2018 at 11:10, bin.cheng <bin.cheng@linux.alibaba.com> wrote:
> >
> > ------------------------------------------------------------------
> > Sender:Richard Biener <richard.guenther@gmail.com>
> > Sent at:2018 Nov 13 (Tue) 23:03
> > To:bin.cheng <bin.cheng@linux.alibaba.com>
> > Cc:GCC Patches <gcc-patches@gcc.gnu.org>
> > Subject:Re: [PATCH PR84648]Adjust loop exit conditions for loop-until-wrap cases.
> >
> > >
> > > On Sun, Nov 11, 2018 at 9:02 AM bin.cheng <bin.cheng@linux.alibaba.com> wrote:
> > >>
> > >> Hi,
> > >> This patch fixes PR84648 by adjusting exit conditions for loop-until-wrap cases.
> > >> It only handles simple cases in which IV.base are constants because we rely on
> > >> current niter analyzer which doesn't handle parameterized bound in wrapped
> > >> case.  It could be relaxed in the future.
> > >>
> > >> Bootstrap and test on x86_64 in progress.
> > >
> > > Please use TYPE_MIN/MAX_VALUE or wi::min/max_value consistently.
> > > Either tree_int_cst_equal (iv0->base, TYPE_MIN_VALUE (type)) or
> > > wide_int_to_tree (niter_type, wi::max_value (TYPE_PRECISION (type),
> > > TYPE_SIGN (type))).
> > >
> > > Also
> > >
> > > +  iv0->base = low;
> > > +  iv0->step = fold_convert (niter_type, integer_one_node);
> > >
> > > build_int_cst (niter_type, 1);
> > >
> > > +  iv1->base = high;
> > > +  iv1->step = integer_zero_node;
> > >
> > > build_int_cst (niter_type, 0);
> > Fixed, thanks for reviewing.
> >
> > >
> > > With the code, what happens to signed IVs?  I suppose we figure out things
> > > earlier by means of undefined overflow?
> > The code takes advantage of signed undefined overflow and handle it as wrap.
> > In the reported test case, we have following IL:
> >   <bb 2> :
> >   goto <bb 4>; [INV]
> >
> >   <bb 3> :
> >   i_4 = i_2 + 1;
> >
> >   <bb 4> :
> >   # i_2 = PHI <0(2), i_4(3)>
> >   i.0_1 = (signed int) i_2;
> >   if (i.0_1 >= 0)
> >     goto <bb 3>; [INV]
> >   else
> >     goto <bb 5>; [INV]
> >
> > So the IV is actually transformed into signed int, we rely on scev to understand
> > type conversion correctly and generate (int){0, 1} for i.0_1.  Is this reasonable?
> >
> > Updated patch attached, bootstrap and test on x86_64.
> >
> > Thanks,
> > bin
> >
> > 2018-11-11  Bin Cheng  <bin.cheng@linux.alibaba.com>
> >
> >         PR tree-optimization/84648
> >         * tree-ssa-loop-niter.c (adjust_cond_for_loop_until_wrap): New.
> >         (number_of_iterations_cond): Adjust exit cond for loop-until-wrap case
> >         by calling adjust_cond_for_loop_until_wrap.
> >
> > 2018-11-11  Bin Cheng  <bin.cheng@linux.alibaba.com>
> >
> >         PR tree-optimization/84648
> >         * gcc.dg/tree-ssa/pr84648.c: New test.
> >         * gcc.dg/pr68317.c: Add warning check on overflow.
>
>
> Hi Bin,
>
> Since you committed this patch (r266171), I've noticed a regression
> in fortran:
Very sorry for the breakage.  It's reported as pr88044, I will investigate it.

Thanks,
bin
> FAIL: gfortran.dg/transfer_intrinsic_3.f90   -O3 -fomit-frame-pointer
> -funroll-loops -fpeel-loops -ftracer -finline-functions  execution
> test
> FAIL: gfortran.dg/transfer_intrinsic_3.f90   -O3 -g  execution test
> on arm-none-linux-gnueabihf
> --with-cpu cortex-a5
> --with-fpu vfpv3-d16-fp16
>
> cortex-a9+neon-fp16, cortex-a15+neon-vfpv4 and
> cortex-a57+crypto-neon-fp-armv8 are still OK.
>
> Christophe