Use nonzero bits to refine range in split_constant_offset (PR 81635)

This patch is part 2 of the fix for PR 81635.  It means that
split_constant_offset can handle loops like:

  for (unsigned int i = 0; i < n; i += 4)
    {
      a[i] = ...;
      a[i + 1] = ...;
    }

CCP records that "i" must have its low 2 bits clear, but we don't
include this information in the range of "i", which remains [0, +INF].
I tried making set_nonzero_bits update the range info in the same
way that set_range_info updates the nonzero bits, but it regressed
cases like vrp117.c and made some other tests worse.

vrp117.c has a multiplication by 10, so CCP can infer that the low bit
of the result is clear.  If we included that in the range, the range
would go from [-INF, +INF] to [-INF, not-quite-+INF].  However,
the multiplication is also known to overflow in all cases, so VRP
saturates the result to [INT_MAX, INT_MAX].  This obviously creates a
contradiction with the nonzero bits, and intersecting the new saturated
range with an existing not-quite-+INF range would make us drop to
VR_UNDEFINED.  We're prepared to fold a comparison with an [INT_MAX,
INT_MAX] value but not with a VR_UNDEFINED value.

The other problems were created when intersecting [-INF, not-quite-+INF]
with a useful VR_ANTI_RANGE like ~[-1, 1].  The intersection would
keep the former range rather than the latter.

The patch therefore keeps the adjustment local to split_constant_offset
for now, but adds a helper routine so that it's easy to move this later.

2018-02-08  Richard Sandiford  <richard.sandiford@linaro.org>

gcc/
	PR tree-optimization/81635
	* wide-int.h (wi::round_down_for_mask, wi::round_up_for_mask): Declare.
	* wide-int.cc (wi::round_down_for_mask, wi::round_up_for_mask)
	(test_round_for_mask): New functions.
	(wide_int_cc_tests): Call test_round_for_mask.
	* tree-vrp.h (intersect_range_with_nonzero_bits): Declare.
	* tree-vrp.c (intersect_range_with_nonzero_bits): New function.
	* tree-data-ref.c (split_constant_offset_1): Use it to refine the
	range returned by get_range_info.

gcc/testsuite/
	PR tree-optimization/81635
	* gcc.dg/vect/bb-slp-pr81635-3.c: New test.
	* gcc.dg/vect/bb-slp-pr81635-4.c: Likewise.

From-SVN: r257491

1 files changed, 112 insertions, 0 deletions

diff --git a/gcc/wide-int.cc b/gcc/wide-int.cc
index 21eac22..8173146 100644
--- a/gcc/wide-int.cc
+++ b/gcc/wide-int.cc
@@ -2132,6 +2132,70 @@ wi::only_sign_bit_p (const wide_int_ref &x)
   return only_sign_bit_p (x, x.precision);
 }
 
+/* Return VAL if VAL has no bits set outside MASK.  Otherwise round VAL
+   down to the previous value that has no bits set outside MASK.
+   This rounding wraps for signed values if VAL is negative and
+   the top bit of MASK is clear.
+
+   For example, round_down_for_mask (6, 0xf1) would give 1 and
+   round_down_for_mask (24, 0xf1) would give 17.  */
+
+wide_int
+wi::round_down_for_mask (const wide_int &val, const wide_int &mask)
+{
+  /* Get the bits in VAL that are outside the mask.  */
+  wide_int extra_bits = wi::bit_and_not (val, mask);
+  if (extra_bits == 0)
+    return val;
+
+  /* Get a mask that includes the top bit in EXTRA_BITS and is all 1s
+     below that bit.  */
+  unsigned int precision = val.get_precision ();
+  wide_int lower_mask = wi::mask (precision - wi::clz (extra_bits),
+				  false, precision);
+
+  /* Clear the bits that aren't in MASK, but ensure that all bits
+     in MASK below the top cleared bit are set.  */
+  return (val & mask) | (mask & lower_mask);
+}
+
+/* Return VAL if VAL has no bits set outside MASK.  Otherwise round VAL
+   up to the next value that has no bits set outside MASK.  The rounding
+   wraps if there are no suitable values greater than VAL.
+
+   For example, round_up_for_mask (6, 0xf1) would give 16 and
+   round_up_for_mask (24, 0xf1) would give 32.  */
+
+wide_int
+wi::round_up_for_mask (const wide_int &val, const wide_int &mask)
+{
+  /* Get the bits in VAL that are outside the mask.  */
+  wide_int extra_bits = wi::bit_and_not (val, mask);
+  if (extra_bits == 0)
+    return val;
+
+  /* Get a mask that is all 1s above the top bit in EXTRA_BITS.  */
+  unsigned int precision = val.get_precision ();
+  wide_int upper_mask = wi::mask (precision - wi::clz (extra_bits),
+				  true, precision);
+
+  /* Get the bits of the mask that are above the top bit in EXTRA_BITS.  */
+  upper_mask &= mask;
+
+  /* Conceptually we need to:
+
+     - clear bits of VAL outside UPPER_MASK
+     - add the lowest bit in UPPER_MASK to VAL (or add 0 if UPPER_MASK is 0)
+     - propagate the carry through the bits of VAL in UPPER_MASK
+
+     If (~VAL & UPPER_MASK) is nonzero, the carry eventually
+     reaches that bit and the process leaves all lower bits clear.
+     If (~VAL & UPPER_MASK) is zero then the result is also zero.  */
+  wide_int tmp = wi::bit_and_not (upper_mask, val);
+
+  return (val | tmp) & -tmp;
+}
+
 /*
  * Private utilities.
  */
@@ -2384,6 +2448,53 @@ test_overflow ()
     }
 }
 
+/* Test the round_{down,up}_for_mask functions.  */
+
+static void
+test_round_for_mask ()
+{
+  unsigned int prec = 18;
+  ASSERT_EQ (17, wi::round_down_for_mask (wi::shwi (17, prec),
+					  wi::shwi (0xf1, prec)));
+  ASSERT_EQ (17, wi::round_up_for_mask (wi::shwi (17, prec),
+					wi::shwi (0xf1, prec)));
+
+  ASSERT_EQ (1, wi::round_down_for_mask (wi::shwi (6, prec),
+					 wi::shwi (0xf1, prec)));
+  ASSERT_EQ (16, wi::round_up_for_mask (wi::shwi (6, prec),
+					wi::shwi (0xf1, prec)));
+
+  ASSERT_EQ (17, wi::round_down_for_mask (wi::shwi (24, prec),
+					  wi::shwi (0xf1, prec)));
+  ASSERT_EQ (32, wi::round_up_for_mask (wi::shwi (24, prec),
+					wi::shwi (0xf1, prec)));
+
+  ASSERT_EQ (0x011, wi::round_down_for_mask (wi::shwi (0x22, prec),
+					     wi::shwi (0x111, prec)));
+  ASSERT_EQ (0x100, wi::round_up_for_mask (wi::shwi (0x22, prec),
+					   wi::shwi (0x111, prec)));
+
+  ASSERT_EQ (100, wi::round_down_for_mask (wi::shwi (101, prec),
+					   wi::shwi (0xfc, prec)));
+  ASSERT_EQ (104, wi::round_up_for_mask (wi::shwi (101, prec),
+					 wi::shwi (0xfc, prec)));
+
+  ASSERT_EQ (0x2bc, wi::round_down_for_mask (wi::shwi (0x2c2, prec),
+					     wi::shwi (0xabc, prec)));
+  ASSERT_EQ (0x800, wi::round_up_for_mask (wi::shwi (0x2c2, prec),
+					   wi::shwi (0xabc, prec)));
+
+  ASSERT_EQ (0xabc, wi::round_down_for_mask (wi::shwi (0xabd, prec),
+					     wi::shwi (0xabc, prec)));
+  ASSERT_EQ (0, wi::round_up_for_mask (wi::shwi (0xabd, prec),
+				       wi::shwi (0xabc, prec)));
+
+  ASSERT_EQ (0xabc, wi::round_down_for_mask (wi::shwi (0x1000, prec),
+					     wi::shwi (0xabc, prec)));
+  ASSERT_EQ (0, wi::round_up_for_mask (wi::shwi (0x1000, prec),
+				       wi::shwi (0xabc, prec)));
+}
+
 /* Run all of the selftests within this file, for all value types.  */
 
 void
@@ -2393,6 +2504,7 @@ wide_int_cc_tests ()
   run_all_wide_int_tests <offset_int> ();
   run_all_wide_int_tests <widest_int> ();
   test_overflow ();
+  test_round_for_mask ();
 }
 
 } // namespace selftest