[PATCH PR81196]Analyze ntiers for loop with exit condition comparing induction variables

[PATCH PR81196]Analyze ntiers for loop with exit condition comparing induction variables

[Bin Cheng]

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

Hi,
This patch picks up a missed-optimization case in loop niter analysis.  With this
patch, niters information for loop as in added test can be analyzed.  Bootstrap
and test on x86_64 and AArch64.  Is it OK?

Thanks,
bin
2017-06-27  Bin Cheng  <bin.cheng@arm.com>

	PR tree-optimization/81196
	* tree-ssa-loop-niter.c (number_of_iterations_cond): Handle loop
	exit condition comparing two IVs.

gcc/testsuite/ChangeLog
2017-06-27  Bin Cheng  <bin.cheng@arm.com>

	PR tree-optimization/81196
	* gcc.dg/vect/pr81196.c: New.

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: 0001-pr81196-20170626.txt.patch --]
[-- Type: text/x-patch; name="0001-pr81196-20170626.txt.patch", Size: 2831 bytes --]

From e11856e20b64bacaa4c5ebc3ea08f875160161dc Mon Sep 17 00:00:00 2001
From: Bin Cheng <binche01@e108451-lin.cambridge.arm.com>
Date: Mon, 26 Jun 2017 15:06:31 +0100
Subject: [PATCH] pr81196-20170626.txt

---
 gcc/testsuite/gcc.dg/vect/pr81196.c | 19 +++++++++++++++++++
 gcc/tree-ssa-loop-niter.c           | 30 +++++++++++++++++++++++-------
 2 files changed, 42 insertions(+), 7 deletions(-)
 create mode 100644 gcc/testsuite/gcc.dg/vect/pr81196.c

diff --git a/gcc/testsuite/gcc.dg/vect/pr81196.c b/gcc/testsuite/gcc.dg/vect/pr81196.c
new file mode 100644
index 0000000..46d7a9e
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/vect/pr81196.c
@@ -0,0 +1,19 @@
+/* { dg-do compile } */
+/* { dg-require-effective-target vect_int } */
+/* { dg-require-effective-target vect_perm_short } */
+
+void f(short*p){
+  p=(short*)__builtin_assume_aligned(p,64);
+  short*q=p+256;
+  for(;p!=q;++p,--q){
+    short t=*p;*p=*q;*q=t;
+  }
+}
+void b(short*p){
+  p=(short*)__builtin_assume_aligned(p,64);
+  short*q=p+256;
+  for(;p<q;++p,--q){
+    short t=*p;*p=*q;*q=t;
+  }
+}
+/* { dg-final { scan-tree-dump-times "vectorized 1 loops" 2 "vect" } } */
diff --git a/gcc/tree-ssa-loop-niter.c b/gcc/tree-ssa-loop-niter.c
index 848e812..934e3b7 100644
--- a/gcc/tree-ssa-loop-niter.c
+++ b/gcc/tree-ssa-loop-niter.c
@@ -1668,18 +1668,34 @@ number_of_iterations_cond (struct loop *loop,
 	exit_must_be_taken = true;
     }
 
-  /* We can handle the case when neither of the sides of the comparison is
-     invariant, provided that the test is NE_EXPR.  This rarely occurs in
-     practice, but it is simple enough to manage.  */
+  /* We can handle cases which neither of the sides of the comparison is
+     invariant:
+
+       {iv0.base, iv0.step} cmp_code {iv1.base, iv1.step}
+     as if:
+       {iv0.base, iv0.step - iv1.step} cmp_code {iv1.base, 0}
+
+     provided that either below condition is satisfied:
+
+       a) the test is NE_EXP;
+       b) iv0.step - iv1.step is positive integer.
+
+     This rarely occurs in practice, but it is simple enough to manage.  */
   if (!integer_zerop (iv0->step) && !integer_zerop (iv1->step))
     {
       tree step_type = POINTER_TYPE_P (type) ? sizetype : type;
-      if (code != NE_EXPR)
+      tree step = fold_binary_to_constant (MINUS_EXPR, step_type,
+					   iv0->step, iv1->step);
+
+      /* 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)
 	return false;
 
-      iv0->step = fold_binary_to_constant (MINUS_EXPR, step_type,
-					   iv0->step, iv1->step);
-      iv0->no_overflow = false;
+      iv0->step = step;
+      if (!POINTER_TYPE_P (type))
+	iv0->no_overflow = false;
+
       iv1->step = build_int_cst (step_type, 0);
       iv1->no_overflow = true;
     }
-- 
1.9.1

Re: [PATCH PR81196]Analyze ntiers for loop with exit condition comparing induction variables

[Richard Biener]

On Wed, Jun 28, 2017 at 11:32 AM, Bin Cheng <Bin.Cheng@arm.com> wrote:
> Hi,
> This patch picks up a missed-optimization case in loop niter analysis.  With this
> patch, niters information for loop as in added test can be analyzed.  Bootstrap
> and test on x86_64 and AArch64.  Is it OK?


+     provided that either below condition is satisfied:
+
+       a) the test is NE_EXP;

NE_EXPR

+       b) iv0.step - iv1.step is positive integer.

Ok with that change.

Thanks,
Richard.

> Thanks,
> bin
> 2017-06-27  Bin Cheng  <bin.cheng@arm.com>
>
>         PR tree-optimization/81196
>         * tree-ssa-loop-niter.c (number_of_iterations_cond): Handle loop
>         exit condition comparing two IVs.
>
> gcc/testsuite/ChangeLog
> 2017-06-27  Bin Cheng  <bin.cheng@arm.com>
>
>         PR tree-optimization/81196
>         * gcc.dg/vect/pr81196.c: New.