public inbox for gcc-patches@gcc.gnu.org
 help / color / mirror / Atom feed
* Simplify more EXACT_DIV_EXPR comparisons
@ 2019-05-19 16:16 Marc Glisse
  2019-05-20  8:04 ` Richard Biener
  0 siblings, 1 reply; 22+ messages in thread
From: Marc Glisse @ 2019-05-19 16:16 UTC (permalink / raw)
  To: gcc-patches

[-- Attachment #1: Type: TEXT/PLAIN, Size: 1777 bytes --]

Hello,

2 pieces:

- the first one handles the case where the denominator is negative. It 
doesn't happen often with exact_div, so I don't handle it everywhere, but 
this one looked trivial

- handle the case where a pointer difference is cast to an unsigned type 
before being compared to a constant (I hit this in std::vector). With some 
range info we could probably handle some non-constant cases as well...

The second piece breaks Walloca-13.c (-Walloca-larger-than=100 -O2)

void f (void*);
void g (int *p, int *q)
{
   __SIZE_TYPE__ n = (__SIZE_TYPE__)(p - q);
   if (n < 100)
     f (__builtin_alloca (n));
}

At the time of walloca2, we have

   _1 = p_5(D) - q_6(D);
   # RANGE [-2305843009213693952, 2305843009213693951]
   _2 = _1 /[ex] 4;
   # RANGE ~[2305843009213693952, 16140901064495857663]
   n_7 = (long unsigned intD.10) _2;
   _11 = (long unsigned intD.10) _1;
   if (_11 <= 396)
[...]
   _3 = allocaD.1059 (n_7);

and warn. However, DOM3 later produces

   _1 = p_5(D) - q_6(D);
   _11 = (long unsigned intD.10) _1;
   if (_11 <= 396)
[...]
   # RANGE [0, 99] NONZERO 127
   _2 = _1 /[ex] 4;
   # RANGE [0, 99] NONZERO 127
   n_7 = (long unsigned intD.10) _2;
   _3 = allocaD.1059 (n_7);

so I am tempted to say that the walloca2 pass is too early, xfail the 
testcase and file an issue...

A single_use restriction would also probably fix this testcase, but I 
don't think that's a good idea, the new code is better because the 
division is now in the branch.

2019-05-20  Marc Glisse  <marc.glisse@inria.fr>

gcc/
 	* match.pd (X/[ex]D<Y/[ex]D): Handle negative denominator.
 	((size_t)(A /[ex] B) CMP C): New transformation.

gcc/testsuite/
 	* gcc.dg/tree-ssa/cmpexactdiv-3.c: New file.
 	* gcc.dg/tree-ssa/cmpexactdiv-4.c: New file.

-- 
Marc Glisse

[-- Attachment #2: Type: TEXT/PLAIN, Size: 4249 bytes --]

Index: gcc/match.pd
===================================================================
--- gcc/match.pd	(revision 271376)
+++ gcc/match.pd	(working copy)
@@ -1490,21 +1490,23 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
 	&& (wi::to_wide (@2)
 	    == wi::max_value (TYPE_PRECISION (TREE_TYPE (@0)), SIGNED) - 1))
     (with { tree stype = signed_type_for (TREE_TYPE (@0)); }
      (icmp (convert:stype @0) { build_int_cst (stype, 0); })))))
 
 /* X / 4 < Y / 4 iff X < Y when the division is known to be exact.  */
 (for cmp (simple_comparison)
  (simplify
   (cmp (exact_div @0 INTEGER_CST@2) (exact_div @1 @2))
   (if (wi::gt_p (wi::to_wide (@2), 0, TYPE_SIGN (TREE_TYPE (@2))))
-   (cmp @0 @1))))
+   (cmp @0 @1)
+   (if (wi::lt_p (wi::to_wide (@2), 0, TYPE_SIGN (TREE_TYPE (@2))))
+    (cmp @1 @0)))))
 
 /* X / C1 op C2 into a simple range test.  */
 (for cmp (simple_comparison)
  (simplify
   (cmp (trunc_div:s @0 INTEGER_CST@1) INTEGER_CST@2)
   (if (INTEGRAL_TYPE_P (TREE_TYPE (@0))
        && integer_nonzerop (@1)
        && !TREE_OVERFLOW (@1)
        && !TREE_OVERFLOW (@2))
    (with { tree lo, hi; bool neg_overflow;
@@ -3626,20 +3634,47 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
       wi::overflow_type ovf;
       wide_int prod = wi::mul (wi::to_wide (@2), wi::to_wide (@1),
 			       TYPE_SIGN (TREE_TYPE (@1)), &ovf);
     }
     (if (ovf)
      { constant_boolean_node (wi::lt_p (wi::to_wide (@2), 0,
 					TYPE_SIGN (TREE_TYPE (@2)))
 			      != (cmp == LT_EXPR || cmp == LE_EXPR), type); }
      (cmp @0 { wide_int_to_tree (TREE_TYPE (@0), prod); }))))))
 
+/* Fold (size_t)(A /[ex] B) CMP C to (size_t)A CMP (size_t)B * C or A CMP' 0.
+
+   For small C (less than max/B), this is (size_t)A CMP (size_t)B * C.
+   For large C (more than min/B+2^size), this is also true, with the
+   multiplication computed modulo 2^size.
+   For intermediate C, this just tests the sign of A.  */
+(for cmp  (lt le gt ge)
+     cmp2 (ge ge lt lt)
+ (simplify
+  (cmp (convert (exact_div @0 INTEGER_CST@1)) INTEGER_CST@2)
+  (if (tree_nop_conversion_p (TREE_TYPE (@0), TREE_TYPE (@2))
+       && TYPE_UNSIGNED (TREE_TYPE (@2)) && !TYPE_UNSIGNED (TREE_TYPE (@0))
+       && wi::gt_p (wi::to_wide (@1), 0, TYPE_SIGN (TREE_TYPE (@1))))
+   (with
+    {
+      tree utype = TREE_TYPE (@2);
+      wide_int denom = wi::to_wide (@1);
+      wide_int right = wi::to_wide (@2);
+      wide_int smax = wi::sdiv_trunc (wi::max_value (TREE_TYPE (@0)), denom);
+      wide_int smin = wi::sdiv_trunc (wi::min_value (TREE_TYPE (@0)), denom);
+      bool small = wi::leu_p (right, smax);
+      bool large = wi::geu_p (right, smin);
+    }
+    (if (small || large)
+     (cmp (convert:utype @0) (mult @2 (convert @1)))
+     (cmp2 @0 { build_zero_cst (TREE_TYPE (@0)); }))))))
+
 /* Unordered tests if either argument is a NaN.  */
 (simplify
  (bit_ior (unordered @0 @0) (unordered @1 @1))
  (if (types_match (@0, @1))
   (unordered @0 @1)))
 (simplify
  (bit_and (ordered @0 @0) (ordered @1 @1))
  (if (types_match (@0, @1))
   (ordered @0 @1)))
 (simplify
Index: gcc/testsuite/gcc.dg/tree-ssa/cmpexactdiv-3.c
===================================================================
--- gcc/testsuite/gcc.dg/tree-ssa/cmpexactdiv-3.c	(nonexistent)
+++ gcc/testsuite/gcc.dg/tree-ssa/cmpexactdiv-3.c	(working copy)
@@ -0,0 +1,10 @@
+/* { dg-do compile } */
+/* { dg-options "-O -fdump-tree-optimized-raw" } */
+
+int f(int*a,int*b){
+  if(sizeof(__SIZE_TYPE__)!=sizeof(__PTRDIFF_TYPE__)) return -1;
+  __SIZE_TYPE__ d = b - a;
+  return d >= 5;
+}
+
+/* { dg-final { scan-tree-dump-not "exact_div_expr" "optimized" } } */
Index: gcc/testsuite/gcc.dg/tree-ssa/cmpexactdiv-4.c
===================================================================
--- gcc/testsuite/gcc.dg/tree-ssa/cmpexactdiv-4.c	(nonexistent)
+++ gcc/testsuite/gcc.dg/tree-ssa/cmpexactdiv-4.c	(working copy)
@@ -0,0 +1,10 @@
+/* { dg-do compile } */
+/* { dg-options "-O -fdump-tree-optimized-raw" } */
+
+int f(int*a,int*b,int*c){
+  __PTRDIFF_TYPE__ x = -(b - a);
+  __PTRDIFF_TYPE__ y = -(c - a);
+  return x < y;
+}
+
+/* { dg-final { scan-tree-dump-not "exact_div_expr" "optimized" } } */

^ permalink raw reply	[flat|nested] 22+ messages in thread
end of thread, other threads:[~2019-05-31 15:51 UTC | newest]

Thread overview: 22+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2019-05-19 16:16 Simplify more EXACT_DIV_EXPR comparisons Marc Glisse
2019-05-20  8:04 ` Richard Biener
2019-05-20  8:16   ` Marc Glisse
2019-05-20  9:16     ` Richard Biener
2019-05-20 17:28       ` Jeff Law
2019-05-20 17:38         ` Marc Glisse
2019-05-20 17:41           ` Jeff Law
2019-05-21  2:13       ` Martin Sebor
2019-05-21  9:53         ` Richard Biener
2019-05-27 13:39           ` Aldy Hernandez
2019-05-27 13:58             ` Richard Biener
2019-05-27 14:44               ` Aldy Hernandez
2019-05-28 15:43           ` Martin Sebor
2019-05-29  7:47             ` Richard Biener
2019-05-29 16:31               ` Jeff Law
2019-05-29 21:33       ` Marc Glisse
2019-05-30 16:38         ` Jeff Law
2019-05-31  9:03           ` Aldy Hernandez
2019-05-31 15:51             ` Marc Glisse
2019-05-31 16:00               ` Aldy Hernandez
2019-05-31  9:00         ` Richard Biener
2019-05-20 17:32   ` Jeff Law

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).