Re: [PATCH GCC 9/9]Prove no-overflow in computation of LOOP_VINFO_NITERS and improve code generation

[kugan]

Hi Bin,

On 07/09/16 04:54, Bin Cheng wrote:
Hi,
LOOP_VINFO_NITERS is computed as LOOP_VINFO_NITERSM1 + 1, which could overflow 
in loop niters' type.  Vectorizer needs to generate more code computing 
vectorized niters if overflow does happen.  However, For common loops, there is 
no overflow actually, this patch tries to prove the no-overflow information and 
use that to improve code generation.  At the moment, no-overflow information 
comes either from loop niter analysis, or the truth that we know loop is peeled 
for non-zero iterations in prologue peeling.  For the latter case, it doesn't 
matter if the original LOOP_VINFO_NITERS overflows or not, because computation 
LOOP_VINFO_NITERS - LOOP_VINFO_PEELING_FOR_ALIGNMENT cancels the overflow by 
underflow.
Thanks,
bin

2016-09-01  Bin Cheng  <bin.ch...@arm.com>

        * tree-vect-loop.c (loop_niters_no_overflow): New func.
        (vect_transform_loop): Call loop_niters_no_overflow.  Pass the
        no-overflow information to vect_do_peeling_for_loop_bound and
        vect_gen_vector_loop_niters.


009-prove-no_overflow-for-vect-niters-20160902.txt


diff --git a/gcc/tree-vect-loop.c b/gcc/tree-vect-loop.c
index 0d37f55..2ef1f9b 100644
--- a/gcc/tree-vect-loop.c
+++ b/gcc/tree-vect-loop.c
@@ -6610,6 +6610,38 @@ vect_loop_kill_debug_uses (struct loop *loop, gimple 
*stmt)
     }
 }

+/* Given loop represented by LOOP_VINFO, return true if computation of
+   LOOP_VINFO_NITERS (= LOOP_VINFO_NITERSM1 + 1) doesn't overflow, false
+   otherwise.  */
+
+static bool
+loop_niters_no_overflow (loop_vec_info loop_vinfo)
+{
+  /* Constant case.  */
+  if (LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo))
+    {
+      int cst_niters = LOOP_VINFO_INT_NITERS (loop_vinfo);

Wouldn't it truncate by assigning this to int?


+      tree cst_nitersm1 = LOOP_VINFO_NITERSM1 (loop_vinfo);
+
+      gcc_assert (TREE_CODE (cst_nitersm1) == INTEGER_CST);
+      if (wi::to_widest (cst_nitersm1) < cst_niters)

Shouldn't you have do the addition and comparison in the type of the 
loop index instead of widest_int to see if that overflows?

Thanks,
Kugan

+       return true;
+    }
+
+  widest_int max;
+  struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
+  /* Check the upper bound of loop niters.  */
+  if (get_max_loop_iterations (loop, &max))
+    {
+      tree type = TREE_TYPE (LOOP_VINFO_NITERS (loop_vinfo));
+      signop sgn = TYPE_SIGN (type);
+      widest_int type_max = widest_int::from (wi::max_value (type), sgn);
+      if (max < type_max)
+       return true;
+    }
+  return false;
+}
+
 /* Function vect_transform_loop.

    The analysis phase has determined that the loop is vectorizable.
@@ -6697,8 +6729,9 @@ vect_transform_loop (loop_vec_info loop_vinfo)
   tree niters = vect_build_loop_niters (loop_vinfo);
   LOOP_VINFO_NITERS_UNCHANGED (loop_vinfo) = niters;
   tree nitersm1 = unshare_expr (LOOP_VINFO_NITERSM1 (loop_vinfo));
+  bool niters_no_overflow = loop_niters_no_overflow (loop_vinfo);
   vect_do_peeling (loop_vinfo, niters, nitersm1, &niters_vector, th,
-                  check_profitability, false);
+                  check_profitability, niters_no_overflow);
   if (niters_vector == NULL_TREE)
     {
       if (LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo))
@@ -6707,7 +6740,7 @@ vect_transform_loop (loop_vec_info loop_vinfo)
                           LOOP_VINFO_INT_NITERS (loop_vinfo) / vf);
       else
        vect_gen_vector_loop_niters (loop_vinfo, niters, &niters_vector,
-                                    false);
+                                    niters_no_overflow);
     }

   /* 1) Make sure the loop header has exactly two entries