[PATCH PR81913]Skip niter analysis if either IV in exit condition can wrap

[PATCH PR81913]Skip niter analysis if either IV in exit condition can wrap

[Bin Cheng]

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

Hi,
I added code handle exit condition like "IV1 le/lt IV2" by changing it into "IV1' le/lt INV".
Unfortunately, wrapping behavior has subtle impact on the transformation.  This patch for
now skips niter analysis if either IV1 or IV2 can wrap.  We can still handle pointer case
as reported in PR81196, but unsigned type needs more work.  The patch also includes two
XFAIL tests showing what shall be improved here.
Bootstrap and test on AArch64.  Is it OK?

Thanks,
bin
2017-08-24  Bin Cheng  <bin.cheng@arm.com>

	PR tree-optimization/81913
	* tree-ssa-loop-niter.c (number_of_iterations_cond): Skip niter
	analysis when either IVs in condition can wrap.

gcc/testsuite
2017-08-24  Bin Cheng  <bin.cheng@arm.com>

	PR tree-optimization/81913
	* gcc.c-torture/execute/pr81913.c: New test.
	* gcc.dg/tree-ssa/loop-niter-1.c: New test.
	* gcc.dg/tree-ssa/loop-niter-2.c: New test.

[-- Attachment #2: pr81913-20170817.txt --]
[-- Type: text/plain, Size: 3956 bytes --]

From 58262ff795e2c2f4cff2982dc8c7aecc240d3227 Mon Sep 17 00:00:00 2001
From: Bin Cheng <binche01@e108451-lin.cambridge.arm.com>
Date: Wed, 23 Aug 2017 10:04:01 +0100
Subject: [PATCH] pr81913-20170817.txt

---
 gcc/testsuite/gcc.c-torture/execute/pr81913.c | 27 +++++++++++++++++++++++
 gcc/testsuite/gcc.dg/tree-ssa/loop-niter-1.c  | 31 +++++++++++++++++++++++++++
 gcc/testsuite/gcc.dg/tree-ssa/loop-niter-2.c  | 31 +++++++++++++++++++++++++++
 gcc/tree-ssa-loop-niter.c                     |  6 ++++--
 4 files changed, 93 insertions(+), 2 deletions(-)
 create mode 100644 gcc/testsuite/gcc.c-torture/execute/pr81913.c
 create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/loop-niter-1.c
 create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/loop-niter-2.c

diff --git a/gcc/testsuite/gcc.c-torture/execute/pr81913.c b/gcc/testsuite/gcc.c-torture/execute/pr81913.c
new file mode 100644
index 0000000..11eec4e
--- /dev/null
+++ b/gcc/testsuite/gcc.c-torture/execute/pr81913.c
@@ -0,0 +1,27 @@
+/* PR tree-optimization/81913 */
+
+typedef unsigned char u8;
+typedef unsigned int u32;
+
+static u32
+b (u8 d, u32 e, u32 g)
+{
+  do
+    {
+      e += g + 1;
+      d--;
+    }
+  while (d >= (u8) e);
+
+  return e;
+}
+
+int
+main (void)
+{
+  u32 x = b (1, -0x378704, ~0xba64fc);
+  if (x != 0xd93190d0)
+    __builtin_abort ();
+  return 0;
+}
+
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/loop-niter-1.c b/gcc/testsuite/gcc.dg/tree-ssa/loop-niter-1.c
new file mode 100644
index 0000000..16c76fe
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/loop-niter-1.c
@@ -0,0 +1,31 @@
+/* { dg-do run } */
+/* { dg-options "-O2 -fdump-tree-sccp-details" } */
+
+typedef unsigned char u8;
+typedef unsigned int u32;
+
+static u32
+b (u8 d, u32 e, u32 g)
+{
+  do
+    {
+      e += g + 1;
+      d--;
+    }
+  while (d >= (u8) e);
+
+  return e;
+}
+
+int
+main (void)
+{
+  u32 x = b (200, -0x378704, ~0xba64fc);
+  if (x != 0xe1ee4ca0)
+    __builtin_abort ();
+
+  return 0;
+}
+
+/* Niter analyzer should be able to compute niters for the loop.  */
+/* { dg-final { scan-tree-dump "Replacing uses of: .* with: 3790490784" "sccp" { xfail *-*-* } } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/loop-niter-2.c b/gcc/testsuite/gcc.dg/tree-ssa/loop-niter-2.c
new file mode 100644
index 0000000..2377e6c
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/loop-niter-2.c
@@ -0,0 +1,31 @@
+/* { dg-do run } */
+/* { dg-options "-O2 -fdump-tree-sccp-details" } */
+
+typedef unsigned char u8;
+typedef unsigned int u32;
+
+static u32
+b (u8 d, u32 e, u32 g)
+{
+  do
+    {
+      e += g + 1;
+      d--;
+    }
+  while (d >= (u8) e);
+
+  return e;
+}
+
+int
+main (void)
+{
+  u32 x = b (1, -0x378704, ~0xba64fc);
+  if (x != 0xd93190d0)
+    __builtin_abort ();
+  return 0;
+}
+
+/* Niter analyzer should be able to compute niters for the loop even though
+   IV:d wraps.  */
+/* { dg-final { scan-tree-dump "Replacing uses of: .* with: 3643904208" "sccp" { xfail *-*-* } } } */
diff --git a/gcc/tree-ssa-loop-niter.c b/gcc/tree-ssa-loop-niter.c
index 0d6d101..27244eb 100644
--- a/gcc/tree-ssa-loop-niter.c
+++ b/gcc/tree-ssa-loop-niter.c
@@ -1728,7 +1728,7 @@ number_of_iterations_cond (struct loop *loop,
      provided that either below condition is satisfied:
 
        a) the test is NE_EXPR;
-       b) iv0.step - iv1.step is positive integer.
+       b) iv0.step - iv1.step is integer and iv0/iv1 don't overflow.
 
      This rarely occurs in practice, but it is simple enough to manage.  */
   if (!integer_zerop (iv0->step) && !integer_zerop (iv1->step))
@@ -1739,7 +1739,9 @@ number_of_iterations_cond (struct loop *loop,
 
       /* 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)
+      if (code != NE_EXPR
+	  && (TREE_CODE (step) != INTEGER_CST
+	      || !iv0->no_overflow || !iv1->no_overflow))
 	return false;
 
       iv0->step = step;
-- 
1.9.1

Re: [PATCH PR81913]Skip niter analysis if either IV in exit condition can wrap

[Richard Biener]

On Thu, Aug 24, 2017 at 12:58 PM, Bin Cheng <Bin.Cheng@arm.com> wrote:
> Hi,
> I added code handle exit condition like "IV1 le/lt IV2" by changing it into "IV1' le/lt INV".
> Unfortunately, wrapping behavior has subtle impact on the transformation.  This patch for
> now skips niter analysis if either IV1 or IV2 can wrap.  We can still handle pointer case
> as reported in PR81196, but unsigned type needs more work.  The patch also includes two
> XFAIL tests showing what shall be improved here.
> Bootstrap and test on AArch64.  Is it OK?

Ok.

Richard.

>
> Thanks,
> bin
> 2017-08-24  Bin Cheng  <bin.cheng@arm.com>
>
>         PR tree-optimization/81913
>         * tree-ssa-loop-niter.c (number_of_iterations_cond): Skip niter
>         analysis when either IVs in condition can wrap.
>
> gcc/testsuite
> 2017-08-24  Bin Cheng  <bin.cheng@arm.com>
>
>         PR tree-optimization/81913
>         * gcc.c-torture/execute/pr81913.c: New test.
>         * gcc.dg/tree-ssa/loop-niter-1.c: New test.
>         * gcc.dg/tree-ssa/loop-niter-2.c: New test.