[PATCH GCC]Improve loop bound info by simplifying conversions in iv base

["Bin Cheng" <bin.cheng@arm.com>]

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

Hi,
For now, SCEV may compute iv base in the form of "(signed T)((unsigned
T)base + step))".  This complicates other optimizations/analysis depending
on SCEV because it's hard to dive into type conversions.  For many cases,
such type conversions can be simplified with additional range information
implied by loop initial conditions.  This patch does such simplification.
With simplified iv base, loop niter analysis can compute more accurate bound
information since sensible value range can be derived for "base+step".  For
example, accurate loop bound&may_be_zero information is computed for cases
added by this patch.
The code is actually borrowed from loop_exits_before_overflow.  Moreover,
with simplified iv base, the second case handled in that function now
becomes the first case.  I didn't remove that part of code because it may(?)
still be visited in scev analysis itself and simple_iv isn't an interface
for that.

Is it OK?

Thanks,
bin

2015-07-28  Bin Cheng  <bin.cheng@arm.com>

	* tree-ssa-loop-niter.c (tree_simplify_using_condition): Export
	the interface.
	* tree-ssa-loop-niter.h (tree_simplify_using_condition): Declare.
	* tree-scalar-evolution.c (simple_iv): Simplify type conversions
	in iv base using loop initial conditions.

gcc/testsuite/ChangeLog
2015-07-28  Bin Cheng  <bin.cheng@arm.com>

	* gcc.dg/tree-ssa/loop-bound-2.c: New test.
	* gcc.dg/tree-ssa/loop-bound-4.c: New test.
	* gcc.dg/tree-ssa/loop-bound-6.c: New test.

[-- Attachment #2: simplify-iv_base-using-loop-initial-conditions-20150728.txt --]
[-- Type: text/plain, Size: 6432 bytes --]

Index: gcc/testsuite/gcc.dg/tree-ssa/loop-bound-2.c
===================================================================
--- gcc/testsuite/gcc.dg/tree-ssa/loop-bound-2.c	(revision 0)
+++ gcc/testsuite/gcc.dg/tree-ssa/loop-bound-2.c	(revision 0)
@@ -0,0 +1,23 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-ivopts-details" } */
+
+int *a;
+
+int
+foo (signed char s, signed char l)
+{
+  signed char i;
+  int sum = 0;
+
+  for (i = s; i < l; i++)
+    {
+      sum += a[i];
+    }
+
+  return sum;
+}
+
+/* Check loop niter bound information.  */
+/* { dg-final { scan-tree-dump "bounded by 254" "ivopts" } } */
+/* { dg-final { scan-tree-dump-not "bounded by 255" "ivopts" } } */
+/* { dg-final { scan-tree-dump-not "zero if " "ivopts" } } */
Index: gcc/testsuite/gcc.dg/tree-ssa/loop-bound-4.c
===================================================================
--- gcc/testsuite/gcc.dg/tree-ssa/loop-bound-4.c	(revision 0)
+++ gcc/testsuite/gcc.dg/tree-ssa/loop-bound-4.c	(revision 0)
@@ -0,0 +1,23 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-ivopts-details" } */
+
+int *a;
+
+int
+foo (signed char s, signed char l)
+{
+  signed char i;
+  int sum = 0;
+
+  for (i = s; i > l; i--)
+    {
+      sum += a[i];
+    }
+
+  return sum;
+}
+
+/* Check loop niter bound information.  */
+/* { dg-final { scan-tree-dump "bounded by 254" "ivopts" } } */
+/* { dg-final { scan-tree-dump-not "bounded by 255" "ivopts" } } */
+/* { dg-final { scan-tree-dump-not "zero if " "ivopts" } } */
Index: gcc/testsuite/gcc.dg/tree-ssa/loop-bound-6.c
===================================================================
--- gcc/testsuite/gcc.dg/tree-ssa/loop-bound-6.c	(revision 0)
+++ gcc/testsuite/gcc.dg/tree-ssa/loop-bound-6.c	(revision 0)
@@ -0,0 +1,23 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-ivopts-details" } */
+
+int *a;
+
+int
+foo (signed char s)
+{
+  signed char i;
+  int sum = 0;
+
+  for (i = s; i > 0; i--)
+    {
+      sum += a[i];
+    }
+
+  return sum;
+}
+
+/* Check loop niter bound information.  */
+/* { dg-final { scan-tree-dump "bounded by 126" "ivopts" } } */
+/* { dg-final { scan-tree-dump-not "bounded by 127" "ivopts" } } */
+/* { dg-final { scan-tree-dump-not "zero if " "ivopts" } } */
Index: gcc/tree-ssa-loop-niter.c
===================================================================
--- gcc/tree-ssa-loop-niter.c	(revision 225859)
+++ gcc/tree-ssa-loop-niter.c	(working copy)
@@ -1779,9 +2043,9 @@ tree_simplify_using_condition (tree cond, tree exp
 
 /* Tries to simplify EXPR using the conditions on entry to LOOP.
    Returns the simplified expression (or EXPR unchanged, if no
-   simplification was possible).*/
+   simplification was possible).  */
 
-static tree
+tree
 simplify_using_initial_conditions (struct loop *loop, tree expr)
 {
   edge e;
Index: gcc/tree-ssa-loop-niter.h
===================================================================
--- gcc/tree-ssa-loop-niter.h	(revision 225859)
+++ gcc/tree-ssa-loop-niter.h	(working copy)
@@ -21,6 +21,7 @@ along with GCC; see the file COPYING3.  If not see
 #define GCC_TREE_SSA_LOOP_NITER_H
 
 extern tree expand_simple_operations (tree, tree = NULL);
+extern tree simplify_using_initial_conditions (struct loop *, tree);
 extern bool loop_only_exit_p (const struct loop *, const_edge);
 extern bool number_of_iterations_exit (struct loop *, edge,
 				       struct tree_niter_desc *niter, bool,
Index: gcc/tree-scalar-evolution.c
===================================================================
--- gcc/tree-scalar-evolution.c	(revision 225859)
+++ gcc/tree-scalar-evolution.c	(working copy)
@@ -3234,7 +3234,8 @@ bool
 simple_iv (struct loop *wrto_loop, struct loop *use_loop, tree op,
 	   affine_iv *iv, bool allow_nonconstant_step)
 {
-  tree type, ev;
+  enum tree_code code;
+  tree type, ev, base, e, extreme;
   bool folded_casts;
 
   iv->base = NULL_TREE;
@@ -3276,6 +3277,77 @@ simple_iv (struct loop *wrto_loop, struct loop *us
   iv->no_overflow = (!folded_casts && ANY_INTEGRAL_TYPE_P (type)
 		     && TYPE_OVERFLOW_UNDEFINED (type));
 
+  /* Try to simplify iv base:
+
+       (signed T) ((unsigned T)base + step) ;; TREE_TYPE (base) == signed T
+	 == (signed T)(unsigned T)base + step
+	 == base + step
+
+     If we can prove operation (base + step) doesn't overflow or underflow.
+     Specifically, we try to prove below conditions are satisfied:
+
+	     base <= UPPER_BOUND (type) - step  ;;step > 0
+	     base >= LOWER_BOUND (type) - step  ;;step < 0
+
+     This is done by proving the reverse conditions are false using loop's
+     initial conditions.
+
+     The is necessary to make loop niter, or iv overflow analysis easier
+     for below example:
+
+       int foo (int *a, signed char s, signed char l)
+	 {
+	   signed char i;
+	   for (i = s; i < l; i++)
+	     a[i] = 0;
+	   return 0;
+	  }
+
+     Note variable I is firstly converted to type unsigned char, incremented,
+     then converted back to type signed char.  */
+
+  if (wrto_loop->num != use_loop->num)
+    return true;
+
+  if (!CONVERT_EXPR_P (iv->base))
+    return true;
+  type = TREE_TYPE (iv->base);
+  e = TREE_OPERAND (iv->base, 0);
+  if (TREE_CODE (e) != PLUS_EXPR
+      || TREE_CODE (TREE_OPERAND (e, 1)) != INTEGER_CST
+      || !operand_equal_p (iv->step,
+			   fold_convert (type,
+					 TREE_OPERAND (e, 1)), 0))
+    return true;
+  e = TREE_OPERAND (e, 0);
+  if (!CONVERT_EXPR_P (e))
+    return true;
+  base = TREE_OPERAND (e, 0);
+  if (!useless_type_conversion_p (type, TREE_TYPE (base)))
+    return true;
+
+  if (tree_int_cst_sign_bit (iv->step))
+    {
+      code = LT_EXPR;
+      extreme = lower_bound_in_type (type, type);
+    }
+  else
+    {
+      code = GT_EXPR;
+      extreme = upper_bound_in_type (type, type);
+    }
+  extreme = fold_build2 (MINUS_EXPR, type, extreme, iv->step);
+  e = fold_build2 (code, boolean_type_node, base, extreme);
+  e = simplify_using_initial_conditions (use_loop, e);
+  if (!integer_zerop (e))
+    return true;
+
+  if (POINTER_TYPE_P (TREE_TYPE (base)))
+    code = POINTER_PLUS_EXPR;
+  else
+    code = PLUS_EXPR;
+
+  iv->base = fold_build2 (code, TREE_TYPE (base), base, iv->step);
   return true;
 }