This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: PR 64454: Improve VRP for %


On Sat, May 2, 2015 at 12:46 AM, Marc Glisse <marc.glisse@inria.fr> wrote:
> Hello,
>
> this patch tries to tighten a bit the range estimate for x%y. slp-perm-7.c
> started failing by vectorizing more than expected, I assumed it was a good
> thing and updated the test. I am less conservative than Jakub with division
> by 0, but I still don't really understand how empty ranges are supposed to
> be represented in VRP.
>
> Bootstrap+testsuite on x86_64-linux-gnu.

Hmm, so I don't like how you (continute to) use trees for the constant
computations.
wide-ints would be a better fit today.  I also notice that
fold_unary_to_constant can
return NULL_TREE and neither the old nor your code handles that.

"empty" ranges are basically UNDEFINED.

Aren't you pessimizing the case where the old code used
value_range_nonnegative_p()
by just using TYPE_UNSIGNED?

Thanks,
Richard.

> 2015-05-02  Marc Glisse  <marc.glisse@inria.fr>
>
>         PR tree-optimization/64454
> gcc/
>         * tree-vrp.c (extract_range_from_binary_expr_1) <TRUNC_MOD_EXPR>:
>         Rewrite.
> gcc/testsuite/
>         * gcc.dg/tree-ssa/vrp97.c: New file.
>         * gcc.dg/vect/slp-perm-7.c: Update.
>
> --
> Marc Glisse
> Index: gcc/testsuite/gcc.dg/tree-ssa/vrp97.c
> ===================================================================
> --- gcc/testsuite/gcc.dg/tree-ssa/vrp97.c       (revision 0)
> +++ gcc/testsuite/gcc.dg/tree-ssa/vrp97.c       (working copy)
> @@ -0,0 +1,13 @@
> +/* PR tree-optimization/64454 */
> +/* { dg-options "-O2 -fdump-tree-vrp1" } */
> +
> +int f(int a, int b)
> +{
> +    if (a < -3 || a > 13) __builtin_unreachable();
> +    if (b < -6 || b > 9) __builtin_unreachable();
> +    int c = a % b;
> +    return c >= -3 && c <= 8;
> +}
> +
> +/* { dg-final { scan-tree-dump "return 1;" "vrp1" } } */
> +/* { dg-final { cleanup-tree-dump "vrp1" } } */
> Index: gcc/testsuite/gcc.dg/vect/slp-perm-7.c
> ===================================================================
> --- gcc/testsuite/gcc.dg/vect/slp-perm-7.c      (revision 222708)
> +++ gcc/testsuite/gcc.dg/vect/slp-perm-7.c      (working copy)
> @@ -63,15 +63,15 @@ int main (int argc, const char* argv[])
>
>    foo (input, output, input2, output2);
>
>    for (i = 0; i < N; i++)
>       if (output[i] != check_results[i] || output2[i] != check_results2[i])
>         abort ();
>
>    return 0;
>  }
>
> -/* { dg-final { scan-tree-dump-times "vectorized 1 loops" 1 "vect"  {
> target vect_perm } } } */
> +/* { dg-final { scan-tree-dump-times "vectorized 1 loops" 2 "vect"  {
> target vect_perm } } } */
>  /* { dg-final { scan-tree-dump-times "vectorizing stmts using SLP" 1 "vect"
> { target vect_perm } } } */
>  /* { dg-final { cleanup-tree-dump "vect" } } */
>
>
> Index: gcc/tree-vrp.c
> ===================================================================
> --- gcc/tree-vrp.c      (revision 222708)
> +++ gcc/tree-vrp.c      (working copy)
> @@ -3189,40 +3189,83 @@ extract_range_from_binary_expr_1 (value_
>             }
>         }
>        else
>         {
>           extract_range_from_multiplicative_op_1 (vr, code, &vr0, &vr1);
>           return;
>         }
>      }
>    else if (code == TRUNC_MOD_EXPR)
>      {
> -      if (vr1.type != VR_RANGE
> -         || range_includes_zero_p (vr1.min, vr1.max) != 0
> -         || vrp_val_is_min (vr1.min))
> +      if (range_is_null (&vr1))
> +       {
> +         set_value_range_to_undefined (vr);
> +         return;
> +       }
> +      // Some propagation of symbolic ranges should be possible
> +      // at least in the unsigned case.
> +      bool has_vr0 = vr0.type == VR_RANGE && !symbolic_range_p (&vr0);
> +      bool has_vr1 = vr1.type == VR_RANGE && !symbolic_range_p (&vr1);
> +      if (!has_vr0 && !has_vr1)
>         {
>           set_value_range_to_varying (vr);
>           return;
>         }
>        type = VR_RANGE;
> -      /* Compute MAX <|vr1.min|, |vr1.max|> - 1.  */
> -      max = fold_unary_to_constant (ABS_EXPR, expr_type, vr1.min);
> -      if (tree_int_cst_lt (max, vr1.max))
> -       max = vr1.max;
> -      max = int_const_binop (MINUS_EXPR, max, build_int_cst (TREE_TYPE
> (max), 1));
> -      /* If the dividend is non-negative the modulus will be
> -        non-negative as well.  */
> -      if (TYPE_UNSIGNED (expr_type)
> -         || value_range_nonnegative_p (&vr0))
> -       min = build_int_cst (TREE_TYPE (max), 0);
> +      if (TYPE_UNSIGNED (expr_type))
> +       {
> +         // A % B is at most A and smaller than B.
> +         min = build_int_cst (expr_type, 0);
> +         if (has_vr0 && (!has_vr1 || tree_int_cst_lt (vr0.max, vr1.max)))
> +           max = vr0.max;
> +         else
> +           max = int_const_binop (MINUS_EXPR, vr1.max,
> +                                  build_int_cst (expr_type, 1));
> +       }
>        else
> -       min = fold_unary_to_constant (NEGATE_EXPR, expr_type, max);
> +       {
> +         tree min1 = NULL_TREE;
> +         tree max1 = NULL_TREE;
> +         if (has_vr1)
> +           {
> +             // ABS (A % B) < ABS (B)
> +             max1 = fold_unary_to_constant (ABS_EXPR, expr_type, vr1.min);
> +             if (tree_int_cst_lt (max1, vr1.max))
> +               max1 = vr1.max;
> +             max1 = int_const_binop (MINUS_EXPR, max1,
> +                                     build_int_cst (expr_type, 1));
> +             min1 = fold_unary_to_constant (NEGATE_EXPR, expr_type, max1);
> +           }
> +         if (has_vr0)
> +           {
> +             // Either 0 <= A % B <= A or A <= A % B <= 0.
> +             max = vr0.max;
> +             min = vr0.min;
> +             tree zero = build_int_cst (expr_type, 0);
> +             if (tree_int_cst_lt (zero, min))
> +               min = zero;
> +             if (tree_int_cst_lt (max, zero))
> +               max = zero;
> +             if (has_vr1)
> +               {
> +                 if (tree_int_cst_lt (min, min1))
> +                   min = min1;
> +                 if (tree_int_cst_lt (max1, max))
> +                   max = max1;
> +               }
> +           }
> +         else
> +           {
> +             min = min1;
> +             max = max1;
> +           }
> +       }
>      }
>    else if (code == BIT_AND_EXPR || code == BIT_IOR_EXPR || code ==
> BIT_XOR_EXPR)
>      {
>        bool int_cst_range0, int_cst_range1;
>        wide_int may_be_nonzero0, may_be_nonzero1;
>        wide_int must_be_nonzero0, must_be_nonzero1;
>
>        int_cst_range0 = zero_nonzero_bits_from_vr (expr_type, &vr0,
>                                                   &may_be_nonzero0,
>                                                   &must_be_nonzero0);
>


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]