From fff2290073cc2d57dcade125227b74cd27c48066 Mon Sep 17 00:00:00 2001 From: Richard Sandiford Date: Thu, 8 Feb 2018 15:16:29 +0000 Subject: 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 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 --- gcc/wide-int.cc | 112 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 112 insertions(+) (limited to 'gcc/wide-int.cc') 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 (); run_all_wide_int_tests (); test_overflow (); + test_round_for_mask (); } } // namespace selftest -- cgit v1.1