Re: [PATCH GCC]Improve no-overflow check in SCEV using value range info.

[Richard Biener <richard dot guenther at gmail dot com>]

On Mon, Jul 18, 2016 at 6:27 PM, Bin Cheng <Bin.Cheng@arm.com> wrote:
> Hi,
> Scalar evolution needs to prove no-overflow for source variable when handling type conversion.  This is important because otherwise we would fail to recognize result of the conversion as SCEV, resulting in missing loop optimizations.  Take case added by this patch as an example, the loop can't be distributed as memset call because address of memory reference is not recognized.  At the moment, we rely on type overflow semantics and loop niter info for no-overflow checking, unfortunately that's not enough.  This patch introduces new method checking no-overflow using value range information.  As commented in the patch, value range can only be used when source operand variable evaluates on every loop iteration, rather than guarded by some conditions.
>
> This together with patch improving loop niter analysis (https://gcc.gnu.org/ml/gcc-patches/2016-07/msg00736.html) can help various loop passes like vectorization.
> Bootstrap and test on x86_64 and AArch64.  Is it OK?

@@ -3187,7 +3187,8 @@ idx_infer_loop_bounds (tree base, tree *idx, void *dta)
   /* If access is not executed on every iteration, we must ensure that overlow
      may not make the access valid later.  */
   if (!dominated_by_p (CDI_DOMINATORS, loop->latch, gimple_bb (data->stmt))
-      && scev_probably_wraps_p (initial_condition_in_loop_num (ev, loop->num),
+      && scev_probably_wraps_p (NULL,

use NULL_TREE for the null pointer constant of tree.

+  /* Check if VAR evaluates in every loop iteration.  */
+  gimple *def;
+  if ((def = SSA_NAME_DEF_STMT (var)) != NULL

def is never NULL but it might be a GIMPLE_NOP which has a NULL gimple_bb.
Better check for ! SSA_DEFAULT_DEF_P (var)

+  if (TREE_CODE (step) != INTEGER_CST || !INTEGRAL_TYPE_P (TREE_TYPE (var)))
+    return false;

this looks like a cheaper test so please do that first.

+  step_wi = step;
+  type = TREE_TYPE (var);
+  if (tree_int_cst_sign_bit (step))
+    {
+      diff = lower_bound_in_type (type, type);
+      diff = minv - diff;
+      step_wi = - step_wi;
+    }
+  else
+    {
+      diff = upper_bound_in_type (type, type);
+      diff = diff - maxv;
+    }

this lacks a comment - it's not obvious to me what the gymnastics
with lower/upper_bound_in_type are supposed to achieve.

As VRP uses niter analysis itself I wonder how this fires back-to-back between
VRP1 and VRP2?  If the def of var dominates the latch isn't it enough to do
a + 1 to check whether VRP bumped the range up to INT_MAX/MIN?  That is,
why do we need to add step if not for the TYPE_OVERFLOW_UNDEFINED case
of VRP handling the ranges optimistically?

Thanks,
Richard.

> Thanks,
> bin
>
> 2016-07-15  Bin Cheng  <bin.cheng@arm.com>
>
>         * tree-chrec.c (convert_affine_scev): New parameter.  Pass new arg.
>         (chrec_convert_1, chrec_convert): Ditto.
>         * tree-chrec.h (chrec_convert, convert_affine_scev): New parameter.
>         * tree-scalar-evolution.c (interpret_rhs_expr): Pass new arg.
>         * tree-vrp.c (adjust_range_with_scev): Ditto.
>         * tree-ssa-loop-niter.c (idx_infer_loop_bounds): Ditto.
>         (scev_var_range_cant_overflow): New function.
>         (scev_probably_wraps_p): New parameter.  Call above function.
>         * tree-ssa-loop-niter.h (scev_probably_wraps_p): New parameter.
>
> gcc/testsuite/ChangeLog
> 2016-07-15  Bin Cheng  <bin.cheng@arm.com>
>
>         * gcc.dg/tree-ssa/scev-15.c: New.