[PATCH] Fix VRP handling of __builtin_ffs* (PR tree-optimization/61725)

[Jakub Jelinek <jakub at redhat dot com>]

Hi!

When writing this code, I've been assuming __builtin_ffs* argument
is unsigned, which is the case of popcount also handled there, and
many other builtins (clz, ctz, ...), except that clrsb has signed argument.
But in reality for some reason ffs has signed argument and some time ago
Marek has even changed the documentation to match the code rather than the
other way around.

So, here is an attempt to deal with it; to return range starting from 1
rather than 0 we need to test for argument range that doesn't include
zero (I'm now including range_includes_zero_p for that), and in case of
maximum of the range if minimum is negative, then one of the negative
values is in the range and therefore the topmost bit is sometimes set.

Bootstrapped/regtested on x86_64-linux and i686-linux, ok for trunk/4.9?

2014-07-08  Jakub Jelinek  <jakub@redhat.com>

	PR tree-optimization/61725
	* tree-vrp.c (extract_range_basic): Don't assume vr0 is unsigned
	range, use range_includes_zerop_p instead of integer_zerop on
	vr0->min, only use log2 of max if min is not negative.

	* gcc.dg/tree-ssa/vrp93.c: New test.
	* gcc.c-torture/execute/pr61725.c: New test.

--- gcc/tree-vrp.c.jj	2014-06-24 09:38:12.000000000 +0200
+++ gcc/tree-vrp.c	2014-07-07 11:26:30.308749523 +0200
@@ -3536,15 +3536,18 @@ extract_range_basic (value_range_t *vr,
 	      /* If arg is non-zero, then ffs or popcount
 		 are non-zero.  */
 	      if (((vr0->type == VR_RANGE
-		    && integer_nonzerop (vr0->min))
+		    && range_includes_zero_p (vr0->min, vr0->max) == 0)
 		   || (vr0->type == VR_ANTI_RANGE
-		       && integer_zerop (vr0->min)))
-		  && !is_overflow_infinity (vr0->min))
+		       && range_includes_zero_p (vr0->min, vr0->max) == 1))
+		  && !is_overflow_infinity (vr0->min)
+		  && !is_overflow_infinity (vr0->max))
 		mini = 1;
 	      /* If some high bits are known to be zero,
 		 we can decrease the maximum.  */
 	      if (vr0->type == VR_RANGE
 		  && TREE_CODE (vr0->max) == INTEGER_CST
+		  && !operand_less_p (vr0->min,
+				      build_zero_cst (TREE_TYPE (vr0->min)))
 		  && !is_overflow_infinity (vr0->max))
 		maxi = tree_floor_log2 (vr0->max) + 1;
 	    }
--- gcc/testsuite/gcc.dg/tree-ssa/vrp93.c.jj	2014-07-07 16:37:39.247344076 +0200
+++ gcc/testsuite/gcc.dg/tree-ssa/vrp93.c	2014-07-07 16:46:33.523847807 +0200
@@ -0,0 +1,36 @@
+/* PR target/29776 */
+/* PR tree-optimization/61725 */
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-vrp1" } */
+/* { dg-final { scan-tree-dump-not "link_error" "vrp1"} } */
+/* { dg-final { cleanup-tree-dump "vrp1" } } */
+
+#define A(fn, arg, min, max) \
+  if (__builtin_##fn (arg) < min || __builtin_##fn (arg) > max) \
+    link_error ();
+#define B(fn, min, max) \
+  A (fn, a, min, max) A (fn##l, b, min, max) A (fn##ll, c, min, max)
+#define C(fn, min, sub) \
+  A (fn, a, min, ((int) sizeof (a) * __CHAR_BIT__ - sub)) \
+  A (fn##l, b, min, ((int) sizeof (b) * __CHAR_BIT__ - sub)) \
+  A (fn##ll, c, min, ((int) sizeof (c) * __CHAR_BIT__ - sub))
+
+extern void link_error (void);
+
+unsigned int d;
+unsigned long e;
+unsigned long long f;
+
+void
+foo (int a, long b, long long c)
+{
+  C (ffs, 0, 0)
+  a &= 63; b &= 63; c &= 63;
+  B (ffs, 0, 6)
+  a++; b++; c++;
+  B (ffs, 1, 7)
+  a -= 2; b -= 2; c -= 2;
+  C (ffs, 0, 0)
+  a -= 63; b -= 63; c -= 63;
+  C (ffs, 1, 0)
+}
--- gcc/testsuite/gcc.c-torture/execute/pr61725.c.jj	2014-07-07 11:04:07.936218135 +0200
+++ gcc/testsuite/gcc.c-torture/execute/pr61725.c	2014-07-07 11:03:47.000000000 +0200
@@ -0,0 +1,14 @@
+/* PR tree-optimization/61725 */
+
+int
+main ()
+{
+  int x;
+  for (x = -128; x <= 128; x++)
+    {
+      int a = __builtin_ffs (x);
+      if (x == 0 && a != 0)
+        __builtin_abort ();
+    }
+  return 0;
+}

	Jakub