From 43e0b376cbb83c77a14be605c3858309b496d88a Mon Sep 17 00:00:00 2001 From: Aldy Hernandez Date: Thu, 27 Jun 2019 04:07:31 +0000 Subject: Move ssa-range* things from range.[hc] into ssa-range-gori. From-SVN: r272728 --- gcc/range.c | 2445 ++++++++++++++++++++++++------------------------- gcc/range.h | 7 - gcc/ssa-range-gori.cc | 77 +- gcc/ssa-range-gori.h | 3 +- gcc/ssa-range.h | 1 - gcc/tree-vrp.h | 4 +- gcc/vr-values.c | 3 +- 7 files changed, 1265 insertions(+), 1275 deletions(-) (limited to 'gcc') diff --git a/gcc/range.c b/gcc/range.c index 8864a56..f0f711b 100644 --- a/gcc/range.c +++ b/gcc/range.c @@ -75,80 +75,6 @@ irange::operator!= (const irange &r) const return !(*this == r); } -// Set range from an SSA_NAME's available range. If there is no -// available range, build a range for its entire domain. - -irange -range_from_ssa (tree ssa) -{ - tree type = TREE_TYPE (ssa); - gcc_checking_assert (irange::supports_type_p (type)); - if (!SSA_NAME_RANGE_INFO (ssa) || POINTER_TYPE_P (type)) - return irange (type); - wide_int min, max; - enum value_range_kind kind = get_range_info (ssa, &min, &max); - return irange (kind, type, min, max); -} - -// This function returns a range for tree node EXPR in R. Return -// false if ranges are not supported. - -bool -get_tree_range (irange &r, tree expr) -{ - tree type; - switch (TREE_CODE (expr)) - { - case INTEGER_CST: - if (!TREE_OVERFLOW_P (expr)) - r = irange (expr, expr); - else - // If we encounter an overflow, simply punt and drop to varying - // since we hvae no idea how it will be used. - r.set_varying (TREE_TYPE (expr)); - return true; - - case SSA_NAME: - if (irange::supports_ssa_p (expr)) - { - r = range_from_ssa (expr); - return true; - } - break; - - case ADDR_EXPR: - { - // handle &var which can show up in phi arguments - bool ov; - type = TREE_TYPE (expr); - if (irange::supports_type_p (type)) - { - if (tree_single_nonzero_warnv_p (expr, &ov)) - r = range_nonzero (type); - else - r.set_varying (type); - return true; - } - break; - } - - default: - if (TYPE_P (expr)) - type = expr; - else - type = TREE_TYPE (expr); - if (irange::supports_type_p (type)) - { - // Set to range for this type. - r.set_varying (type); - return true; - } - break; - } - - return false; -} - irange range_intersect (const irange &r1, const irange &r2) { @@ -207,1374 +133,1373 @@ range_negatives (tree type) return r; } -#if USE_IRANGE -// Standalone irange implementation. +#if CHECKING_P +#include "stor-layout.h" -// Subtract 1 from X and set OVERFLOW if the operation overflows. +// Ideally this should go in namespace selftest, but range_tests +// needs to be a friend of class irange so it can access +// irange::m_max_pairs. -static wide_int inline -subtract_one (const wide_int &x, tree type, wi::overflow_type &overflow) -{ - // A signed 1-bit bit-field, has a range of [-1,0] so subtracting +1 - // overflows, since +1 is unrepresentable. This is why we have an - // addition of -1 here. - if (TYPE_SIGN (type) == SIGNED) - return wi::add (x, -1 , SIGNED, &overflow); - else - return wi::sub (x, 1, UNSIGNED, &overflow); -} +#define INT(N) build_int_cst (integer_type_node, (N)) +#define UINT(N) build_int_cstu (unsigned_type_node, (N)) +#define INT16(N) build_int_cst (short_integer_type_node, (N)) +#define UINT16(N) build_int_cstu (short_unsigned_type_node, (N)) +#define INT64(N) build_int_cstu (long_long_integer_type_node, (N)) +#define UINT64(N) build_int_cstu (long_long_unsigned_type_node, (N)) +#define UINT128(N) build_int_cstu (u128_type, (N)) +#define UCHAR(N) build_int_cstu (unsigned_char_type_node, (N)) +#define SCHAR(N) build_int_cst (signed_char_type_node, (N)) -// Set range from wide ints. +#define RANGE3(A,B,C,D,E,F) \ +( i1 = irange (INT (A), INT (B)), \ + i2 = irange (INT (C), INT (D)), \ + i3 = irange (INT (E), INT (F)), \ + i1.union_ (i2), \ + i1.union_ (i3), \ + i1 ) + +// Run all of the selftests within this file. void -irange::init (tree type, const wide_int &lbound, const wide_int &ubound, - value_range_kind rt) +range_tests () { - if (rt == VR_UNDEFINED) - { - set_undefined (type); - return; - } - if (rt == VR_VARYING) - { - set_varying (type); - return; - } - gcc_checking_assert (irange::supports_type_p (type)); - gcc_checking_assert (TYPE_PRECISION (type) == lbound.get_precision ()); - gcc_checking_assert (lbound.get_precision () == ubound.get_precision ()); - m_type = type; - gcc_checking_assert (wi::le_p (lbound, ubound, TYPE_SIGN (type))); - if (rt == VR_ANTI_RANGE) - { - // Calculate INVERSE([I,J]) as [-MIN, I-1][J+1, +MAX]. - wi::overflow_type ovf; - m_nitems = 0; - wide_int min = wi::min_value (TYPE_PRECISION (type), TYPE_SIGN (type)); - wide_int max = wi::max_value (TYPE_PRECISION (type), TYPE_SIGN (type)); - - // If we will overflow, don't bother. This will handle unsigned - // underflow which doesn't set the overflow bit. - if (lbound != min) - { - m_bounds[m_nitems++] = min; - m_bounds[m_nitems++] = subtract_one (lbound, type, ovf); - if (ovf) - m_nitems = 0; - } - // If we will overflow, don't bother. This will handle unsigned - // overflow which doesn't set the overflow bit. - if (ubound != max) - { - m_bounds[m_nitems++] = wi::add (ubound, 1, TYPE_SIGN (type), &ovf); - if (ovf) - m_nitems--; - else - m_bounds[m_nitems++] = max; - } - // If we get here with N==0, it means we tried to calculate the - // inverse of [-MIN, +MAX] which is actually the empty set, and - // N==0 maps nicely to the empty set. - } - else - { - m_bounds[0] = lbound; - m_bounds[1] = ubound; - m_nitems = 2; - } -} + tree u128_type = build_nonstandard_integer_type (128, /*unsigned=*/1); + irange i1, i2, i3; + irange r0, r1, rold; -irange::irange (tree type) -{ - set_varying (type); -} + // Test that NOT(255) is [0..254] in 8-bit land. + irange not_255 (VR_ANTI_RANGE, UCHAR (255), UCHAR (255)); + ASSERT_TRUE (not_255 == irange (UCHAR (0), UCHAR (254))); -irange::irange (value_range_kind rt, tree type, - const wide_int &lbound, const wide_int &ubound) -{ - init (type, lbound, ubound, rt); -} + // Test that NOT(0) is [1..255] in 8-bit land. + irange not_zero = range_nonzero (unsigned_char_type_node); + ASSERT_TRUE (not_zero == irange (UCHAR (1), UCHAR (255))); -irange::irange (tree type, const wide_int &lbound, const wide_int &ubound) -{ - init (type, lbound, ubound, VR_RANGE); -} + // Check that [0,127][0x..ffffff80,0x..ffffff] + // => ~[128, 0x..ffffff7f]. + r0 = irange (UINT128 (0), UINT128 (127)); + tree high = build_minus_one_cst (u128_type); + // low = -1 - 127 => 0x..ffffff80. + tree low = fold_build2 (MINUS_EXPR, u128_type, high, UINT128(127)); + r1 = irange (low, high); // [0x..ffffff80, 0x..ffffffff] + // r0 = [0,127][0x..ffffff80,0x..fffffff]. + r0.union_ (r1); + // r1 = [128, 0x..ffffff7f]. + r1 = irange (UINT128(128), + fold_build2 (MINUS_EXPR, u128_type, + build_minus_one_cst (u128_type), + UINT128(128))); + r0.invert (); + ASSERT_TRUE (r0 == r1); -irange::irange (value_range_kind rt, tree lbound, tree ubound) -{ - gcc_checking_assert (rt == VR_RANGE || rt == VR_ANTI_RANGE); - tree type = TREE_TYPE (lbound); - init (type, wi::to_wide (lbound), wi::to_wide (ubound), rt); -} + r0.set_varying (integer_type_node); + tree minint = wide_int_to_tree (integer_type_node, r0.lower_bound ()); + tree maxint = wide_int_to_tree (integer_type_node, r0.upper_bound ()); -irange::irange (tree lbound, tree ubound) -{ - tree type = TREE_TYPE (lbound); - init (type, wi::to_wide (lbound), wi::to_wide (ubound), VR_RANGE); -} + r0.set_varying (short_integer_type_node); + tree minshort = wide_int_to_tree (short_integer_type_node, r0.lower_bound ()); + tree maxshort = wide_int_to_tree (short_integer_type_node, r0.upper_bound ()); -// Mark pair [i, j] to empty. This is done by building a non-sensical pair. + r0.set_varying (unsigned_type_node); + tree maxuint = wide_int_to_tree (unsigned_type_node, r0.upper_bound ()); -void -irange_storage::set_empty_pair (unsigned i, unsigned j, tree type) -{ - unsigned precision = trailing_bounds[0].get_precision (); - if (precision == 1 && TYPE_SIGN (type) == SIGNED) - { - // For stupid ass signed 1-bit types, we can't use [1, 0] as a - // nonsensical pair, since it maps to [-1, 0] which is valid. - // In this case, use [0, 1] which is invalid in this brain-dead world. - trailing_bounds[i] = wi::zero (precision); - trailing_bounds[j] = wi::one (precision); - } - else - { - // For almost all types, we mark empty ranges with a nonsensical [1, 0] range. - trailing_bounds[i] = wi::one (precision); - trailing_bounds[j] = wi::zero (precision); - } -} + // Check that ~[0,5] => [6,MAX] for unsigned int. + r0 = irange (UINT (0), UINT (5)); + r0.invert (); + ASSERT_TRUE (r0 == irange (UINT(6), maxuint)); -irange::irange (tree type, const irange_storage *storage) -{ - m_type = type; - m_nitems = 0; - unsigned i = 0; - unsigned precision = wi::get_precision (storage->trailing_bounds[0]); - gcc_checking_assert (precision == TYPE_PRECISION (type)); - while (i < m_max_pairs * 2) - { - if (storage->empty_pair_p (i, i + 1, type)) - break; - m_bounds[i] = storage->trailing_bounds[i]; - m_bounds[i + 1] = storage->trailing_bounds[i + 1]; - i += 2; - } - m_nitems = i; -} + // Check that ~[10,MAX] => [0,9] for unsigned int. + r0 = irange (VR_RANGE, UINT(10), maxuint); + r0.invert (); + ASSERT_TRUE (r0 == irange (UINT (0), UINT (9))); -// Set range from the full domain of TYPE. + // Check that ~[0,5] => [6,MAX] for unsigned 128-bit numbers. + r0 = irange (VR_ANTI_RANGE, UINT128 (0), UINT128 (5)); + r1 = irange (UINT128(6), build_minus_one_cst (u128_type)); + ASSERT_TRUE (r0 == r1); -void -irange::set_varying (tree type) -{ - wide_int min = wi::min_value (TYPE_PRECISION (type), TYPE_SIGN (type)); - wide_int max = wi::max_value (TYPE_PRECISION (type), TYPE_SIGN (type)); - init (type, min, max); -} + // Check that [~5] is really [-MIN,4][6,MAX]. + r0 = irange (VR_ANTI_RANGE, INT (5), INT (5)); + r1 = irange (minint, INT (4)); + r1.union_ (irange (INT (6), maxint)); + ASSERT_FALSE (r1.undefined_p ()); + ASSERT_TRUE (r0 == r1); -bool -irange::valid_p () const -{ - if (m_type == NULL - || m_nitems % 2 - || m_nitems > m_max_pairs * 2) - return false; + r1 = irange (INT (5), INT (5)); + r1.check (); + irange r2 (r1); + ASSERT_TRUE (r1 == r2); - if (undefined_p ()) - return true; + r1 = irange (INT (5), INT (10)); + r1.check (); - // Check that the bounds are in the right order. - // So for [a,b][c,d][e,f] we must have: a <= b < c <= d < e <= f. - if (wi::gt_p (lower_bound (0), upper_bound (0), TYPE_SIGN (m_type))) - return false; - for (unsigned p = 1; p < num_pairs (); ++p) - { - if (wi::le_p (lower_bound (p), upper_bound (p - 1), TYPE_SIGN (m_type))) - return false; - if (wi::gt_p (lower_bound (p), upper_bound (p), TYPE_SIGN (m_type))) - return false; - } - return true; -} + r1 = irange (integer_type_node, + wi::to_wide (INT (5)), wi::to_wide (INT (10))); + r1.check (); + ASSERT_TRUE (r1.contains_p (INT (7))); -void -irange::check () const -{ - gcc_assert (valid_p ()); -} + r1 = irange (SCHAR (0), SCHAR (20)); + ASSERT_TRUE (r1.contains_p (SCHAR(15))); + ASSERT_FALSE (r1.contains_p (SCHAR(300))); -// Convert the current range in place into a range of type NEW_TYPE. + // If a range is in any way outside of the range for the converted + // to range, default to the range for the new type. + r1 = irange (integer_zero_node, maxint); + r1.cast (short_integer_type_node); + ASSERT_TRUE (r1.lower_bound () == wi::to_wide (minshort) + && r1.upper_bound() == wi::to_wide (maxshort)); -void -irange::cast (tree new_type) -{ - // If the expression involves a pointer, we are only interested in - // determining if it evaluates to NULL [0, 0] or non-NULL (~[0, 0]). - if (POINTER_TYPE_P (new_type) || POINTER_TYPE_P (m_type)) - { - if (!contains_p (wi::zero (TYPE_PRECISION (m_type)))) - { - // Don't use range_nonzero because it will recurse into cast(). - unsigned prec = TYPE_PRECISION (new_type); - irange nz (VR_ANTI_RANGE, new_type, - wi::zero (prec), wi::zero (prec)); - *this = nz; - } - else if (zero_p ()) - *this = range_zero (new_type); - else - set_varying (new_type); - return; - } + // (unsigned char)[-5,-1] => [251,255]. + r0 = rold = irange (SCHAR (-5), SCHAR (-1)); + r0.cast (unsigned_char_type_node); + ASSERT_TRUE (r0 == irange (UCHAR (251), UCHAR (255))); + r0.cast (signed_char_type_node); + ASSERT_TRUE (r0 == rold); - // If nothing changed, this is a simple type conversion between two - // variants of the same type. - bool sign_change = TYPE_SIGN (new_type) != TYPE_SIGN (m_type); - unsigned old_precision = TYPE_PRECISION (m_type); - unsigned new_precision = TYPE_PRECISION (new_type); - signop old_sign = TYPE_SIGN (m_type); - signop new_sign = TYPE_SIGN (new_type); - if (undefined_p () || (!sign_change && old_precision == new_precision)) + // (signed char)[15, 150] => [-128,-106][15,127]. + r0 = rold = irange (UCHAR (15), UCHAR (150)); + r0.cast (signed_char_type_node); + r1 = irange (SCHAR (15), SCHAR (127)); + r2 = irange (SCHAR (-128), SCHAR (-106)); + r1.union_ (r2); + ASSERT_TRUE (r1 == r0); + r0.cast (unsigned_char_type_node); + ASSERT_TRUE (r0 == rold); + + // (unsigned char)[-5, 5] => [0,5][251,255]. + r0 = rold = irange (SCHAR (-5), SCHAR (5)); + r0.cast (unsigned_char_type_node); + r1 = irange (UCHAR (251), UCHAR (255)); + r2 = irange (UCHAR (0), UCHAR (5)); + r1.union_ (r2); + ASSERT_TRUE (r0 == r1); + r0.cast (signed_char_type_node); + ASSERT_TRUE (r0 == rold); + + // (unsigned char)[-5,5] => [0,5][251,255]. + r0 = irange (INT (-5), INT (5)); + r0.cast (unsigned_char_type_node); + r1 = irange (UCHAR (0), UCHAR (5)); + r1.union_ (irange (UCHAR (251), UCHAR (255))); + ASSERT_TRUE (r0 == r1); + + // (unsigned char)[5U,1974U] => [0,255]. + r0 = irange (UINT (5), UINT (1974)); + r0.cast (unsigned_char_type_node); + ASSERT_TRUE (r0 == irange (UCHAR (0), UCHAR (255))); + r0.cast (integer_type_node); + // Going to a wider range should not sign extend. + ASSERT_TRUE (r0 == irange (INT (0), INT (255))); + + // (unsigned char)[-350,15] => [0,255]. + r0 = irange (INT (-350), INT (15)); + r0.cast (unsigned_char_type_node); + ASSERT_TRUE (r0 == irange (TYPE_MIN_VALUE (unsigned_char_type_node), + TYPE_MAX_VALUE (unsigned_char_type_node))); + + // Casting [-120,20] from signed char to unsigned short. + // => [0, 20][0xff88, 0xffff]. + r0 = irange (SCHAR (-120), SCHAR (20)); + r0.cast (short_unsigned_type_node); + r1 = irange (UINT16 (0), UINT16 (20)); + r2 = irange (UINT16 (0xff88), UINT16 (0xffff)); + r1.union_ (r2); + ASSERT_TRUE (r0 == r1); + // A truncating cast back to signed char will work because [-120, 20] + // is representable in signed char. + r0.cast (signed_char_type_node); + ASSERT_TRUE (r0 == irange (SCHAR (-120), SCHAR (20))); + + // unsigned char -> signed short + // (signed short)[(unsigned char)25, (unsigned char)250] + // => [(signed short)25, (signed short)250] + r0 = rold = irange (UCHAR (25), UCHAR (250)); + r0.cast (short_integer_type_node); + r1 = irange (INT16 (25), INT16 (250)); + ASSERT_TRUE (r0 == r1); + r0.cast (unsigned_char_type_node); + ASSERT_TRUE (r0 == rold); + + // Test casting a wider signed [-MIN,MAX] to a nar`rower unsigned. + r0 = irange (TYPE_MIN_VALUE (long_long_integer_type_node), + TYPE_MAX_VALUE (long_long_integer_type_node)); + r0.cast (short_unsigned_type_node); + r1 = irange (TYPE_MIN_VALUE (short_unsigned_type_node), + TYPE_MAX_VALUE (short_unsigned_type_node)); + ASSERT_TRUE (r0 == r1); + + // Test that casting a range with MAX_PAIRS that changes sign is + // done conservatively. + // + // (unsigned short)[-5,5][20,30][40,50]... + // => (unsigned short)[-5,50] + // => [0,50][65531,65535] + r0 = irange (INT16 (-5), INT16 (5)); + gcc_assert (irange::m_max_pairs * 2 * 10 + 10 < 32767); + unsigned i; + for (i = 2; i < irange::m_max_pairs * 2; i += 2) { - m_type = new_type; - return; + r1 = irange (INT16 (i * 10), INT16 (i * 10 + 10)); + r0.union_ (r1); } + r0.cast(short_unsigned_type_node); + r1 = irange (UINT16 (0), UINT16 ((i - 2) * 10 + 10)); + r2 = irange (UINT16 (65531), UINT16 (65535)); + r1.union_ (r2); + ASSERT_TRUE (r0 == r1); - wide_int orig_lowest = lower_bound (); - wide_int orig_highest = upper_bound (); - wide_int new_type_min = wi::min_value (new_precision, new_sign); - wide_int new_type_max = wi::max_value (new_precision, new_sign); - unsigned n = m_nitems; - for (unsigned i = 0; i < n; i += 2) + // NOT([10,20]) ==> [-MIN,9][21,MAX]. + r0 = r1 = irange (INT (10), INT (20)); + r2 = irange (minint, INT(9)); + r2.union_ (irange (INT(21), maxint)); + ASSERT_FALSE (r2.undefined_p ()); + r1.invert (); + ASSERT_TRUE (r1 == r2); + // Test that NOT(NOT(x)) == x. + r2.invert (); + ASSERT_TRUE (r0 == r2); + + // NOT(-MIN,+MAX) is the empty set and should return false. + r0 = irange (minint, maxint); + r0.invert (); + ASSERT_TRUE (r0.undefined_p ()); + r1.set_undefined (); + ASSERT_TRUE (r0 == r1); + + // Test that booleans and their inverse work as expected. + r0 = range_zero (boolean_type_node); + ASSERT_TRUE (r0 == irange (build_zero_cst (boolean_type_node), + build_zero_cst (boolean_type_node))); + r0.invert(); + ASSERT_TRUE (r0 == irange (build_one_cst (boolean_type_node), + build_one_cst (boolean_type_node))); + + // Casting NONZERO to a narrower type will wrap/overflow so + // it's just the entire range for the narrower type. + // + // "NOT 0 at signed 32-bits" ==> [-MIN_32,-1][1, +MAX_32]. This is + // is outside of the range of a smaller range, return the full + // smaller range. + r0 = range_nonzero (integer_type_node); + r0.cast (short_integer_type_node); + r1 = irange (TYPE_MIN_VALUE (short_integer_type_node), + TYPE_MAX_VALUE (short_integer_type_node)); + ASSERT_TRUE (r0 == r1); + + // Casting NONZERO from a narrower signed to a wider signed. + // + // NONZERO signed 16-bits is [-MIN_16,-1][1, +MAX_16]. + // Converting this to 32-bits signed is [-MIN_16,-1][1, +MAX_16]. + r0 = range_nonzero (short_integer_type_node); + r0.cast (integer_type_node); + r1 = irange (INT (-32768), INT (-1)); + r2 = irange (INT (1), INT (32767)); + r1.union_ (r2); + ASSERT_TRUE (r0 == r1); + + if (irange::m_max_pairs > 2) { - // If this sub-range doesn't fit in the new range type, bail. - wide_int new_min, new_max; - if (!wide_int_range_convert (new_min, new_max, - old_sign, old_precision, - new_sign, new_precision, - m_bounds[i], m_bounds[i + 1])) - { - m_type = new_type; - m_nitems = 2; - m_bounds[0] = new_type_min; - m_bounds[1] = new_type_max; - return; - } - // If the new bounds are in the right order, we can do a - // straight up conversion. - if (wi::le_p (new_min, new_max, new_sign)) - { - m_bounds[i] = new_min; - m_bounds[i + 1] = new_max; - } - // Otherwise, the bounds have wrapped and we must handle them - // specially as [-MIN,Y][X,MAX]. - else - { - /* For one bit precision, the swapped range covers all values. */ - if (TYPE_PRECISION (new_type) == 1) - { - set_varying (new_type); - return; - } - // If we're about to go over the maximum number of ranges, - // convert to something conservative and cast again. - if (m_nitems >= m_max_pairs * 2) - { - m_nitems = 2; - m_bounds[0] = orig_lowest; - m_bounds[1] = orig_highest; - cast (new_type); - return; - } - // Handle wrapping of [X,Y] as [-MIN,Y][X,MAX]. - m_bounds[i] = new_type_min; - m_bounds[i + 1] = new_max; - // If we're about to construct [-MIN, MAX], no sense - // calculating anything else. - if (m_bounds[i + 1] == new_type_max) - { - m_nitems = 2; - m_type = new_type; - m_bounds[0] = new_type_min; - m_bounds[1] = new_type_max; - return; - } - m_bounds[m_nitems++] = new_min; - m_bounds[m_nitems++] = new_type_max; - } - } - m_type = new_type; - canonicalize (); -} + // ([10,20] U [5,8]) U [1,3] ==> [1,3][5,8][10,20]. + r0 = irange (INT (10), INT (20)); + r1 = irange (INT (5), INT (8)); + r0.union_ (r1); + r1 = irange (INT (1), INT (3)); + r0.union_ (r1); + ASSERT_TRUE (r0 == RANGE3 (1, 3, 5, 8, 10, 20)); -// Return TRUE if the current range contains wide-int ELEMENT. + // [1,3][5,8][10,20] U [-5,0] => [-5,3][5,8][10,20]. + r1 = irange (INT (-5), INT (0)); + r0.union_ (r1); + ASSERT_TRUE (r0 == RANGE3 (-5, 3, 5, 8, 10, 20)); + } -bool -irange::contains_p (const wide_int &element) const -{ - for (unsigned p = 0; p < num_pairs (); ++p) - if (wi::ge_p (element, lower_bound (p), TYPE_SIGN (m_type)) - && wi::le_p (element, upper_bound (p), TYPE_SIGN (m_type))) - return true; - return false; -} + // [10,20] U [30,40] ==> [10,20][30,40]. + r0 = irange (INT (10), INT (20)); + r1 = irange (INT (30), INT (40)); + r0.union_ (r1); + ASSERT_TRUE (r0 == range_union (irange (INT (10), INT (20)), + irange (INT (30), INT (40)))); + if (irange::m_max_pairs > 2) + { + // [10,20][30,40] U [50,60] ==> [10,20][30,40][50,60]. + r1 = irange (INT (50), INT (60)); + r0.union_ (r1); + ASSERT_TRUE (r0 == RANGE3 (10, 20, 30, 40, 50, 60)); + // [10,20][30,40][50,60] U [70, 80] ==> [10,20][30,40][50,60][70,80]. + r1 = irange (INT (70), INT (80)); + r0.union_ (r1); -// Return TRUE if the current range contains tree ELEMENT. + r2 = RANGE3 (10, 20, 30, 40, 50, 60); + r2.union_ (irange (INT (70), INT (80))); + ASSERT_TRUE (r0 == r2); + } -bool -irange::contains_p (tree element) const -{ - return contains_p (wi::to_wide (element)); -} + // Make sure NULL and non-NULL of pointer types work, and that + // inverses of them are consistent. + tree voidp = build_pointer_type (void_type_node); + r0 = range_zero (voidp); + r1 = r0; + r0.invert (); + r0.invert (); + ASSERT_TRUE (r0 == r1); -// Remove PAIR. + if (irange::m_max_pairs > 2) + { + // [10,20][30,40][50,60] U [6,35] => [6,40][50,60]. + r0 = RANGE3 (10, 20, 30, 40, 50, 60); + r1 = irange (INT (6), INT (35)); + r0.union_ (r1); + ASSERT_TRUE (r0 == range_union (irange (INT (6), INT (40)), + irange (INT (50), INT (60)))); -void -irange::remove_pair (unsigned pair) -{ - unsigned i = pair * 2; - unsigned j = i + 1; - gcc_checking_assert (i < m_nitems && i < j); - unsigned dst = i; - unsigned ndeleted = j - i + 1; - for (++j; j < m_nitems; ++j) - m_bounds[dst++] = m_bounds[j]; - m_nitems -= ndeleted; -} + // [10,20][30,40][50,60] U [6,60] => [6,60] */ + r0 = RANGE3 (10, 20, 30, 40, 50, 60); + r1 = irange (INT (6), INT (60)); + r0.union_ (r1); + ASSERT_TRUE (r0 == irange (INT (6), INT (60))); -// Canonicalize the current range. + // [10,20][30,40][50,60] U [6,70] => [6,70]. + r0 = RANGE3 (10, 20, 30, 40, 50, 60); + r1 = irange (INT (6), INT (70)); + r0.union_ (r1); + ASSERT_TRUE (r0 == irange (INT (6), INT (70))); -void -irange::canonicalize () -{ - if (undefined_p ()) - return; + // [10,20][30,40][50,60] U [35,70] => [10,20][30,70]. + r0 = RANGE3 (10, 20, 30, 40, 50, 60); + r1 = irange (INT (35), INT (70)); + r0.union_ (r1); + ASSERT_TRUE (r0 == range_union (irange (INT (10), INT (20)), + irange (INT (30), INT (70)))); + } - // Fix any out of order ranges: [10,20][-5,5] into [-5,5][10,20]. - signop sign = TYPE_SIGN (m_type); - for (unsigned p = 0; p < num_pairs (); ++p) - for (unsigned q = p; q < num_pairs (); ++q) - if (wi::gt_p (lower_bound (p), lower_bound (q), sign)) - { - wide_int t1 = lower_bound (p); - wide_int t2 = upper_bound (p); - set_lower_bound (p, lower_bound (q)); - set_upper_bound (p, upper_bound (q)); - set_lower_bound (q, t1); - set_upper_bound (q, t2); - } - // Merge sub-ranges when appropriate. - for (unsigned p = 0; p < num_pairs () - 1; ) + // [10,20][30,40] U [25,70] => [10,70]. + r0 = range_union (irange (INT (10), INT (20)), + irange (INT (30), INT (40))); + r1 = irange (INT (25), INT (70)); + r0.union_ (r1); + ASSERT_TRUE (r0 == range_union (irange (INT (10), INT (20)), + irange (INT (25), INT (70)))); + + if (irange::m_max_pairs > 2) { - // Merge edges that touch: - // [9,10][11,20] => [9,20] - // [9,10][10,20] => [9,20]. - wi::overflow_type ovf; - if (upper_bound (p) == lower_bound (p + 1) - || (wi::add (upper_bound (p), 1, sign, &ovf) == lower_bound (p + 1) - && !ovf)) - { - set_upper_bound (p, upper_bound (p + 1)); - remove_pair (p + 1); - } - // Merge pairs that bleed into each other: - // [10,20][11,18] => [10,20] - // [10,20][15,30] => [10,30] - else if (wi::le_p (lower_bound (p), lower_bound (p + 1), sign) - && wi::ge_p (upper_bound (p), lower_bound (p + 1), sign)) - { - set_upper_bound (p, wi::max (upper_bound (p), upper_bound (p + 1), sign)); - remove_pair (p + 1); - } - else - ++p; + // [10,20][30,40][50,60] U [15,35] => [10,40][50,60]. + r0 = RANGE3 (10, 20, 30, 40, 50, 60); + r1 = irange (INT (15), INT (35)); + r0.union_ (r1); + ASSERT_TRUE (r0 == range_union (irange (INT (10), INT (40)), + irange (INT (50), INT (60)))); } - if (flag_checking) - check (); -} -// THIS = THIS U R + // [10,20] U [15, 30] => [10, 30]. + r0 = irange (INT (10), INT (20)); + r1 = irange (INT (15), INT (30)); + r0.union_ (r1); + ASSERT_TRUE (r0 == irange (INT (10), INT (30))); -void -irange::union_ (const irange &r) -{ - gcc_checking_assert (range_compatible_p (m_type, r.m_type)); + // [10,20] U [25,25] => [10,20][25,25]. + r0 = irange (INT (10), INT (20)); + r1 = irange (INT (25), INT (25)); + r0.union_ (r1); + ASSERT_TRUE (r0 == range_union (irange (INT (10), INT (20)), + irange (INT (25), INT (25)))); - if (undefined_p ()) + if (irange::m_max_pairs > 2) { - *this = r; - return; + // [10,20][30,40][50,60] U [35,35] => [10,20][30,40][50,60]. + r0 = RANGE3 (10, 20, 30, 40, 50, 60); + r1 = irange (INT (35), INT (35)); + r0.union_ (r1); + ASSERT_TRUE (r0 == RANGE3 (10, 20, 30, 40, 50, 60)); } - else if (r.undefined_p ()) - return; - // Do not worry about merging and such by reserving twice as many - // pairs as needed, and then simply sort the 2 ranges into this - // intermediate form. - // - // The intermediate result will have the property that the beginning - // of each range is <= the beginning of the next range. There may - // be overlapping ranges at this point. I.e. this would be valid - // [-20, 10], [-10, 0], [0, 20], [40, 90] as it satisfies this - // contraint : -20 < -10 < 0 < 40 When the range is rebuilt into r, - // the merge is performed. - // - // [Xi,Yi]..[Xn,Yn] U [Xj,Yj]..[Xm,Ym] --> [Xk,Yk]..[Xp,Yp] - signop sign = TYPE_SIGN (m_type); - wide_int res[m_max_pairs * 4]; - wide_int u1 ; - wi::overflow_type ovf; - unsigned i = 0, j = 0, k = 0; + // [15,40] U [] => [15,40]. + r0 = irange (INT (15), INT (40)); + r1.set_undefined (); + r0.union_ (r1); + ASSERT_TRUE (r0 == irange (INT (15), INT (40))); - while (i < m_nitems && j < r.m_nitems) + // [10,20] U [10,10] => [10,20]. + r0 = irange (INT (10), INT (20)); + r1 = irange (INT (10), INT (10)); + r0.union_ (r1); + ASSERT_TRUE (r0 == irange (INT (10), INT (20))); + + // [10,20] U [9,9] => [9,20]. + r0 = irange (INT (10), INT (20)); + r1 = irange (INT (9), INT (9)); + r0.union_ (r1); + ASSERT_TRUE (r0 == irange (INT (9), INT (20))); + + if (irange::m_max_pairs > 2) { - // lower of Xi and Xj is the lowest point. - if (wi::le_p (m_bounds[i], r.m_bounds[j], sign)) - { - res[k++] = m_bounds[i]; - res[k++] = m_bounds[i + 1]; - i += 2; + // [10,10][12,12][20,100] ^ [15,200]. + r0 = RANGE3 (10, 10, 12, 12, 20, 100); + r1 = irange (INT (15), INT (200)); + r0.intersect (r1); + ASSERT_TRUE (r0 == irange (INT (20), INT (100))); + + // [10,20][30,40][50,60] ^ [15,25][38,51][55,70] + // => [15,20][38,40][50,51][55,60] + r0 = RANGE3 (10, 20, 30, 40, 50, 60); + r1 = RANGE3 (15, 25, 38, 51, 55, 70); + r0.intersect (r1); + if (irange::m_max_pairs == 3) + { + // When pairs==3, we don't have enough space, so + // conservatively handle things. Thus, the ...[50,60]. + ASSERT_TRUE (r0 == RANGE3 (15, 20, 38, 40, 50, 60)); } else - { - res[k++] = r.m_bounds[j]; - res[k++] = r.m_bounds[j + 1]; - j += 2; + { + r2 = RANGE3 (15, 20, 38, 40, 50, 51); + r2.union_ (irange (INT (55), INT (60))); + ASSERT_TRUE (r0 == r2); } - } - for ( ; i < m_nitems; i += 2) - { - res[k++] = m_bounds[i]; - res[k++] = m_bounds[i + 1]; - } - for ( ; j < r.m_nitems; j += 2) - { - res[k++] = r.m_bounds[j]; - res[k++] = r.m_bounds[j + 1]; + + // [15,20][30,40][50,60] ^ [15,35][40,90][100,200] + // => [15,20][30,35][40,60] + r0 = RANGE3 (15, 20, 30, 40, 50, 60); + r1 = RANGE3 (15, 35, 40, 90, 100, 200); + r0.intersect (r1); + if (irange::m_max_pairs == 3) + { + // When pairs==3, we don't have enough space, so + // conservatively handle things. + ASSERT_TRUE (r0 == RANGE3 (15, 20, 30, 35, 40, 60)); + } + else + { + r2 = RANGE3 (15, 20, 30, 35, 40, 40); + r2.union_ (irange (INT (50), INT (60))); + ASSERT_TRUE (r0 == r2); + } + + // Test cases where a union inserts a sub-range inside a larger + // range. + // + // [8,10][135,255] U [14,14] => [8,10][14,14][135,255] + r0 = range_union (irange (INT (8), INT (10)), + irange (INT (135), INT (255))); + r1 = irange (INT (14), INT (14)); + r0.union_ (r1); + ASSERT_TRUE (r0 == RANGE3 (8, 10, 14, 14, 135, 255)); } - // Now normalize the vector removing any overlaps. - i = 2; - int prec = TYPE_PRECISION (m_type); - wide_int max_val = wi::max_value (prec, sign); - for (j = 2; j < k ; j += 2) - { - if (res[i - 1] == max_val) - break; - u1 = wi::add (res[i - 1], 1, sign, &ovf); + // [10,20] ^ [15,30] => [15,20]. + r0 = irange (INT (10), INT (20)); + r1 = irange (INT (15), INT (30)); + r0.intersect (r1); + ASSERT_TRUE (r0 == irange (INT (15), INT (20))); - // Overflow indicates we are at MAX already. - // A wide int bug requires the previous max_val check - // trigger: gcc.c-torture/compile/pr80443.c with -O3 - if (ovf) - break; + // [10,20][30,40] ^ [40,50] => [40,40]. + r0 = range_union (irange (INT (10), INT (20)), + irange (INT (30), INT (40))); + r1 = irange (INT (40), INT (50)); + r0.intersect (r1); + ASSERT_TRUE (r0 == irange (INT (40), INT (40))); - // Current upper+1 is >= lower bound next pair, then we merge ranges. - if (wi::ge_p (u1, res[j], sign)) - { - // New upper bounds is greater of current or the next one. - if (wi::gt_p (res[j + 1], res [i - 1], sign)) - res [i - 1] = res[j + 1]; - } - else - { - // This is a new distinct range, but no point in copying it - // if it is already in the right place. - if (i != j) - { - res[i++] = res[j]; - res[i++] = res[j + 1]; - } - else - i += 2; + // Test non-destructive intersection. + r0 = rold = irange (INT (10), INT (20)); + ASSERT_FALSE (range_intersect (r0, irange (INT (15), + INT (30))).undefined_p ()); + ASSERT_TRUE (r0 == rold); - } - } - - // At this point, the vector should have i ranges, none - // overlapping. Now it simply needs to be copied, and if there are - // too many ranges, merge some. We wont do any analysis as to what - // the "best" merges are, simply combine the final ranges into one. - if (i > m_max_pairs * 2) - { - res[m_max_pairs * 2 - 1] = res[i - 1]; - i = m_max_pairs * 2; - } + // Test the internal sanity of wide_int's wrt HWIs. + ASSERT_TRUE (wi::max_value (TYPE_PRECISION (boolean_type_node), + TYPE_SIGN (boolean_type_node)) + == wi::uhwi (1, TYPE_PRECISION (boolean_type_node))); - for (j = 0; j < i ; j++) - m_bounds[j] = res [j]; - m_nitems = i; + // Test irange_storage. + r0 = irange (INT (5), INT (10)); + irange_storage *stow = irange_storage::alloc (r0); + r1 = irange (integer_type_node, stow); + ASSERT_TRUE (r0 == r1); - if (flag_checking) - check (); -} + // Test irange_storage with signed 1-bit fields. + tree s1bit_type = make_signed_type (1); + r0 = irange (build_int_cst (s1bit_type, -1), build_int_cst (s1bit_type, 0)); + stow = irange_storage::alloc (r0); + r1 = irange (s1bit_type, stow); + ASSERT_TRUE (r0 == r1); -// THIS = THIS ^ [X,Y]. + // Test zero_p(). + r0 = irange (INT (0), INT (0)); + ASSERT_TRUE (r0.zero_p ()); -void -irange::intersect (const wide_int &x, const wide_int &y) -{ - unsigned pos = 0; + // Test nonzero_p(). + r0 = irange (INT (0), INT (0)); + r0.invert (); + ASSERT_TRUE (r0.nonzero_p ()); - for (unsigned i = 0; i < m_nitems; i += 2) - { - signop sign = TYPE_SIGN (m_type); - wide_int newlo = wi::max (m_bounds[i], x, sign); - wide_int newhi = wi::min (m_bounds[i + 1], y, sign); - if (wi::gt_p (newlo, newhi, sign)) - { - // If the new sub-range doesn't make sense, it's an - // impossible range and must be kept out of the result. - } - else - { - m_bounds[pos++] = newlo; - m_bounds[pos++] = newhi; - } - } - m_nitems = pos; - if (flag_checking) - check (); + // Test irange / value_range conversion functions. + r0 = irange (VR_ANTI_RANGE, INT (10), INT (20)); + value_range_base vr = r0; + ASSERT_TRUE (vr.kind () == VR_ANTI_RANGE); + ASSERT_TRUE (wi::eq_p (10, wi::to_wide (vr.min ())) + && wi::eq_p (20, wi::to_wide (vr.max ()))); + r1 = vr; + ASSERT_TRUE (r0 == r1); } +#endif // CHECKING_P -// THIS = THIS ^ R. - -void -irange::intersect (const irange &r) -{ - gcc_checking_assert (range_compatible_p (m_type, r.m_type)); - irange orig_range (*this); +#if USE_IRANGE +// Standalone irange implementation. - // Intersection with an empty range is an empty range. - set_undefined (); - if (orig_range.undefined_p () || r.undefined_p ()) - return; +// Subtract 1 from X and set OVERFLOW if the operation overflows. - // The general algorithm is as follows. - // - // Intersect each sub-range of R with all of ORIG_RANGE one at a time, and - // join/union the results of these intersections together. I.e: - // - // [10,20][30,40][50,60] ^ [15,25][38,51][55,70] - // - // Step 1: [10,20][30,40][50,60] ^ [15,25] => [15,20] - // Step 2: [10,20][30,40][50,60] ^ [38,51] => [38,40] - // Step 3: [10,20][30,40][50,60] ^ [55,70] => [55,60] - // Final: [15,20] U [38,40] U [55,60] => [15,20][38,40][55,60] - for (unsigned i = 0; i < r.m_nitems; i += 2) - { - irange tmp (orig_range); - tmp.intersect (r.m_bounds[i], r.m_bounds[i + 1]); - union_ (tmp); - } - // There is no check here because the calls to union_ above would - // have verified sanity. +static wide_int inline +subtract_one (const wide_int &x, tree type, wi::overflow_type &overflow) +{ + // A signed 1-bit bit-field, has a range of [-1,0] so subtracting +1 + // overflows, since +1 is unrepresentable. This is why we have an + // addition of -1 here. + if (TYPE_SIGN (type) == SIGNED) + return wi::add (x, -1 , SIGNED, &overflow); + else + return wi::sub (x, 1, UNSIGNED, &overflow); } -// Set THIS to the inverse of its range. +// Set range from wide ints. void -irange::invert () +irange::init (tree type, const wide_int &lbound, const wide_int &ubound, + value_range_kind rt) { - // We always need one more set of bounds to represent an inverse, so - // if we're at the limit, we can't properly represent things. - // - // For instance, to represent the inverse of a 2 sub-range set - // [5, 10][20, 30], we would need a 3 sub-range set - // [-MIN, 4][11, 19][31, MAX]. - // - // In this case, return the most conservative thing. - // - // However, if any of the extremes of the range are -MIN/+MAX, we - // know we will not need an extra bound. For example: - // - // INVERT([-MIN,20][30,40]) => [21,29][41,+MAX] - // INVERT([-MIN,20][30,MAX]) => [21,29] - wide_int min = wi::min_value (TYPE_PRECISION (m_type), TYPE_SIGN (m_type)); - wide_int max = wi::max_value (TYPE_PRECISION (m_type), TYPE_SIGN (m_type)); - if (m_nitems == m_max_pairs * 2 - && m_bounds[0] != min - && m_bounds[m_nitems] != max) + if (rt == VR_UNDEFINED) { - m_bounds[1] = max; - m_nitems = 2; + set_undefined (type); return; } - - // The inverse of the empty set is the entire domain. - if (undefined_p ()) + if (rt == VR_VARYING) { - set_varying (m_type); + set_varying (type); return; } - - // The algorithm is as follows. To calculate INVERT ([a,b][c,d]), we - // generate [-MIN, a-1][b+1, c-1][d+1, MAX]. - // - // If there is an over/underflow in the calculation for any - // sub-range, we eliminate that subrange. This allows us to easily - // calculate INVERT([-MIN, 5]) with: [-MIN, -MIN-1][6, MAX]. And since - // we eliminate the underflow, only [6, MAX] remains. - - unsigned i = 0; - wi::overflow_type ovf; - - // Construct leftmost range. - irange orig_range (*this); - m_nitems = 0; - // If this is going to underflow on the MINUS 1, don't even bother - // checking. This also handles subtracting one from an unsigned 0, - // which doesn't set the underflow bit. - if (min != orig_range.m_bounds[i]) - { - m_bounds[m_nitems++] = min; - m_bounds[m_nitems++] = subtract_one (orig_range.m_bounds[i], - m_type, ovf); - if (ovf) - m_nitems = 0; - } - i++; - // Construct middle ranges if applicable. - if (orig_range.m_nitems > 2) + gcc_checking_assert (irange::supports_type_p (type)); + gcc_checking_assert (TYPE_PRECISION (type) == lbound.get_precision ()); + gcc_checking_assert (lbound.get_precision () == ubound.get_precision ()); + m_type = type; + gcc_checking_assert (wi::le_p (lbound, ubound, TYPE_SIGN (type))); + if (rt == VR_ANTI_RANGE) { - unsigned j = i; - for (; j < (unsigned) (orig_range.m_nitems - 2); j += 2) + // Calculate INVERSE([I,J]) as [-MIN, I-1][J+1, +MAX]. + wi::overflow_type ovf; + m_nitems = 0; + wide_int min = wi::min_value (TYPE_PRECISION (type), TYPE_SIGN (type)); + wide_int max = wi::max_value (TYPE_PRECISION (type), TYPE_SIGN (type)); + + // If we will overflow, don't bother. This will handle unsigned + // underflow which doesn't set the overflow bit. + if (lbound != min) { - // The middle ranges cannot have MAX/MIN, so there's no need - // to check for unsigned overflow on the +1 and -1 here. - m_bounds[m_nitems++] - = wi::add (orig_range.m_bounds[j], 1, TYPE_SIGN (m_type), &ovf); - m_bounds[m_nitems++] - = subtract_one (orig_range.m_bounds[j + 1], m_type, ovf); + m_bounds[m_nitems++] = min; + m_bounds[m_nitems++] = subtract_one (lbound, type, ovf); if (ovf) - m_nitems -= 2; + m_nitems = 0; } - i = j; + // If we will overflow, don't bother. This will handle unsigned + // overflow which doesn't set the overflow bit. + if (ubound != max) + { + m_bounds[m_nitems++] = wi::add (ubound, 1, TYPE_SIGN (type), &ovf); + if (ovf) + m_nitems--; + else + m_bounds[m_nitems++] = max; + } + // If we get here with N==0, it means we tried to calculate the + // inverse of [-MIN, +MAX] which is actually the empty set, and + // N==0 maps nicely to the empty set. } - // Construct rightmost range. - // - // However, if this will overflow on the PLUS 1, don't even bother. - // This also handles adding one to an unsigned MAX, which doesn't - // set the overflow bit. - if (max != orig_range.m_bounds[i]) + else { - m_bounds[m_nitems++] - = wi::add (orig_range.m_bounds[i], 1, TYPE_SIGN (m_type), &ovf); - m_bounds[m_nitems++] = max; - if (ovf) - m_nitems -= 2; + m_bounds[0] = lbound; + m_bounds[1] = ubound; + m_nitems = 2; } +} + +irange::irange (tree type) +{ + set_varying (type); +} + +irange::irange (value_range_kind rt, tree type, + const wide_int &lbound, const wide_int &ubound) +{ + init (type, lbound, ubound, rt); +} + +irange::irange (tree type, const wide_int &lbound, const wide_int &ubound) +{ + init (type, lbound, ubound, VR_RANGE); +} + +irange::irange (value_range_kind rt, tree lbound, tree ubound) +{ + gcc_checking_assert (rt == VR_RANGE || rt == VR_ANTI_RANGE); + tree type = TREE_TYPE (lbound); + init (type, wi::to_wide (lbound), wi::to_wide (ubound), rt); +} - if (flag_checking) - check (); +irange::irange (tree lbound, tree ubound) +{ + tree type = TREE_TYPE (lbound); + init (type, wi::to_wide (lbound), wi::to_wide (ubound), VR_RANGE); } -// Dump the current range onto BUFFER. +// Mark pair [i, j] to empty. This is done by building a non-sensical pair. void -irange::dump (pretty_printer *buffer) const +irange_storage::set_empty_pair (unsigned i, unsigned j, tree type) { - wide_int min = wi::min_value (TYPE_PRECISION (m_type), TYPE_SIGN (m_type)); - wide_int max = wi::max_value (TYPE_PRECISION (m_type), TYPE_SIGN (m_type)); - if (POINTER_TYPE_P (m_type) && nonzero_p ()) - pp_string (buffer, "[ non-zero pointer ]"); + unsigned precision = trailing_bounds[0].get_precision (); + if (precision == 1 && TYPE_SIGN (type) == SIGNED) + { + // For stupid ass signed 1-bit types, we can't use [1, 0] as a + // nonsensical pair, since it maps to [-1, 0] which is valid. + // In this case, use [0, 1] which is invalid in this brain-dead world. + trailing_bounds[i] = wi::zero (precision); + trailing_bounds[j] = wi::one (precision); + } else - for (unsigned i = 0; i < m_nitems; ++i) - { - if (i % 2 == 0) - pp_character (buffer, '['); - - // Wide ints may be sign extended to the full extent of the - // underlying HWI storage, even if the precision we care about - // is smaller. Chop off the excess bits for prettier output. - signop sign = TYPE_UNSIGNED (m_type) ? UNSIGNED : SIGNED; - widest_int val = widest_int::from (m_bounds[i], sign); - val &= wi::mask (m_bounds[i].get_precision (), false); - - if (i == 0 - && INTEGRAL_TYPE_P (m_type) - && !TYPE_UNSIGNED (m_type) - && m_bounds[i] == min - && TYPE_PRECISION (m_type) != 1) - pp_string (buffer, "-INF"); - else if (i + 1 == m_nitems - && INTEGRAL_TYPE_P (m_type) - && !TYPE_UNSIGNED (m_type) - && m_bounds[i] == max - && TYPE_PRECISION (m_type) != 1) - pp_string (buffer, "+INF"); - else - { - if (val > 0xffff) - print_hex (val, pp_buffer (buffer)->digit_buffer); - else - print_dec (m_bounds[i], pp_buffer (buffer)->digit_buffer, sign); - pp_string (buffer, pp_buffer (buffer)->digit_buffer); - } - if (i % 2 == 0) - pp_string (buffer, ", "); - else - pp_character (buffer, ']'); - } - if (undefined_p ()) - pp_string (buffer, "[]"); + { + // For almost all types, we mark empty ranges with a nonsensical [1, 0] range. + trailing_bounds[i] = wi::one (precision); + trailing_bounds[j] = wi::zero (precision); + } +} - pp_character (buffer, ' '); - dump_generic_node (buffer, m_type, 0, TDF_NONE, false); - pp_flush (buffer); +irange::irange (tree type, const irange_storage *storage) +{ + m_type = type; + m_nitems = 0; + unsigned i = 0; + unsigned precision = wi::get_precision (storage->trailing_bounds[0]); + gcc_checking_assert (precision == TYPE_PRECISION (type)); + while (i < m_max_pairs * 2) + { + if (storage->empty_pair_p (i, i + 1, type)) + break; + m_bounds[i] = storage->trailing_bounds[i]; + m_bounds[i + 1] = storage->trailing_bounds[i + 1]; + i += 2; + } + m_nitems = i; } -// Dump the current range onto FILE F. +// Set range from the full domain of TYPE. void -irange::dump (FILE *f) const +irange::set_varying (tree type) { - pretty_printer buffer; - buffer.buffer->stream = f; - dump (&buffer); + wide_int min = wi::min_value (TYPE_PRECISION (type), TYPE_SIGN (type)); + wide_int max = wi::max_value (TYPE_PRECISION (type), TYPE_SIGN (type)); + init (type, min, max); } -// Like above but dump to STDERR. -// -// You'd think we could have a default parameter for dump(FILE), -// but gdb currently doesn't do default parameters gracefully-- or at -// all, and since this is a function we need to be callable from the -// debugger... +bool +irange::valid_p () const +{ + if (m_type == NULL + || m_nitems % 2 + || m_nitems > m_max_pairs * 2) + return false; + + if (undefined_p ()) + return true; + + // Check that the bounds are in the right order. + // So for [a,b][c,d][e,f] we must have: a <= b < c <= d < e <= f. + if (wi::gt_p (lower_bound (0), upper_bound (0), TYPE_SIGN (m_type))) + return false; + for (unsigned p = 1; p < num_pairs (); ++p) + { + if (wi::le_p (lower_bound (p), upper_bound (p - 1), TYPE_SIGN (m_type))) + return false; + if (wi::gt_p (lower_bound (p), upper_bound (p), TYPE_SIGN (m_type))) + return false; + } + return true; +} void -irange::dump () const +irange::check () const { - dump (stderr); + gcc_assert (valid_p ()); } -// Initialize the current irange_storage to the irange in IR. +// Convert the current range in place into a range of type NEW_TYPE. void -irange_storage::set (const irange &ir) +irange::cast (tree new_type) { - unsigned precision = TYPE_PRECISION (ir.type ()); - trailing_bounds.set_precision (precision); - unsigned i; - for (i = 0; i < ir.num_pairs () * 2; ++i) - trailing_bounds[i] = ir.m_bounds[i]; + // If the expression involves a pointer, we are only interested in + // determining if it evaluates to NULL [0, 0] or non-NULL (~[0, 0]). + if (POINTER_TYPE_P (new_type) || POINTER_TYPE_P (m_type)) + { + if (!contains_p (wi::zero (TYPE_PRECISION (m_type)))) + { + // Don't use range_nonzero because it will recurse into cast(). + unsigned prec = TYPE_PRECISION (new_type); + irange nz (VR_ANTI_RANGE, new_type, + wi::zero (prec), wi::zero (prec)); + *this = nz; + } + else if (zero_p ()) + *this = range_zero (new_type); + else + set_varying (new_type); + return; + } - // Clear the remaining empty ranges. - for (; i < irange::m_max_pairs * 2; i += 2) - set_empty_pair (i, i + 1, ir.type ()); + // If nothing changed, this is a simple type conversion between two + // variants of the same type. + bool sign_change = TYPE_SIGN (new_type) != TYPE_SIGN (m_type); + unsigned old_precision = TYPE_PRECISION (m_type); + unsigned new_precision = TYPE_PRECISION (new_type); + signop old_sign = TYPE_SIGN (m_type); + signop new_sign = TYPE_SIGN (new_type); + if (undefined_p () || (!sign_change && old_precision == new_precision)) + { + m_type = new_type; + return; + } + + wide_int orig_lowest = lower_bound (); + wide_int orig_highest = upper_bound (); + wide_int new_type_min = wi::min_value (new_precision, new_sign); + wide_int new_type_max = wi::max_value (new_precision, new_sign); + unsigned n = m_nitems; + for (unsigned i = 0; i < n; i += 2) + { + // If this sub-range doesn't fit in the new range type, bail. + wide_int new_min, new_max; + if (!wide_int_range_convert (new_min, new_max, + old_sign, old_precision, + new_sign, new_precision, + m_bounds[i], m_bounds[i + 1])) + { + m_type = new_type; + m_nitems = 2; + m_bounds[0] = new_type_min; + m_bounds[1] = new_type_max; + return; + } + // If the new bounds are in the right order, we can do a + // straight up conversion. + if (wi::le_p (new_min, new_max, new_sign)) + { + m_bounds[i] = new_min; + m_bounds[i + 1] = new_max; + } + // Otherwise, the bounds have wrapped and we must handle them + // specially as [-MIN,Y][X,MAX]. + else + { + /* For one bit precision, the swapped range covers all values. */ + if (TYPE_PRECISION (new_type) == 1) + { + set_varying (new_type); + return; + } + // If we're about to go over the maximum number of ranges, + // convert to something conservative and cast again. + if (m_nitems >= m_max_pairs * 2) + { + m_nitems = 2; + m_bounds[0] = orig_lowest; + m_bounds[1] = orig_highest; + cast (new_type); + return; + } + // Handle wrapping of [X,Y] as [-MIN,Y][X,MAX]. + m_bounds[i] = new_type_min; + m_bounds[i + 1] = new_max; + // If we're about to construct [-MIN, MAX], no sense + // calculating anything else. + if (m_bounds[i + 1] == new_type_max) + { + m_nitems = 2; + m_type = new_type; + m_bounds[0] = new_type_min; + m_bounds[1] = new_type_max; + return; + } + m_bounds[m_nitems++] = new_min; + m_bounds[m_nitems++] = new_type_max; + } + } + m_type = new_type; + canonicalize (); } -// Update a previously initialized irange_storage to NEW_RANGE, iff the -// precision of the present range is the same as the precision of -// the new range. Return TRUE if update was successful. +// Return TRUE if the current range contains wide-int ELEMENT. bool -irange_storage::update (const irange &new_range) +irange::contains_p (const wide_int &element) const { - if (trailing_bounds.get_precision () == TYPE_PRECISION (new_range.type ())) - { - set (new_range); + for (unsigned p = 0; p < num_pairs (); ++p) + if (wi::ge_p (element, lower_bound (p), TYPE_SIGN (m_type)) + && wi::le_p (element, upper_bound (p), TYPE_SIGN (m_type))) return true; - } return false; } -// Return TRUE if range contains exactly one element and set RESULT to it. +// Return TRUE if the current range contains tree ELEMENT. bool -irange::singleton_p (tree *result) const +irange::contains_p (tree element) const { - if (num_pairs () == 1 && lower_bound (0) == upper_bound (0)) - { - if (result) - *result = wide_int_to_tree (type (), lower_bound ()); - return true; - } - return false; + return contains_p (wi::to_wide (element)); } -// Convert irange to a value_range. +// Remove PAIR. -value_range_base -irange_to_value_range (const irange &r) +void +irange::remove_pair (unsigned pair) { - value_range_base vr; - if (r.varying_p ()) - { - vr.set_varying (r.type ()); - return vr; - } - if (r.undefined_p ()) - { - vr.set_undefined (r.type ()); - return vr; - } - tree type = r.type (); - unsigned int precision = TYPE_PRECISION (type); - // Represent non-zero correctly. - if (TYPE_UNSIGNED (type) - && r.num_pairs () == 1 - && r.lower_bound () == wi::uhwi (1, precision) - && r.upper_bound () == wi::max_value (precision, UNSIGNED) - // Do not get confused by booleans. - && TYPE_PRECISION (type) != 1) - vr = value_range (VR_ANTI_RANGE, - build_int_cst (type, 0), build_int_cst (type, 0)); - // Represent anti-ranges. - else if ((r.num_pairs () == 2 - || r.num_pairs () == 3) - // Do not get confused by booleans. - && TYPE_PRECISION (type) != 1 - && r.lower_bound () == wi::min_value (precision, TYPE_SIGN (type)) - && r.upper_bound () == wi::max_value (precision, TYPE_SIGN (type))) - { - irange tmp = r; - if (r.num_pairs () == 3) - { - // Hack to make up for the fact that we can compute finer - // grained ranges that VRP can only approximate with an - // anti-range. Attempt to reconstruct sub-ranges of the form: - // - // [0, 94][96, 127][0xff80, 0xffff] => ~[95,95] - // [0, 1][3, 0x7fffffff][0xff..80000000, 0xff..ff] => ~[2, 2]. - // - // Merge the last two bounds. - tmp = irange (type, r.lower_bound (0), r.upper_bound (0)); - tmp.union_ (irange (type, r.lower_bound (1), r.upper_bound ())); - } - tmp = range_invert (tmp); - vr = value_range (VR_ANTI_RANGE, - wide_int_to_tree (type, tmp.lower_bound ()), - wide_int_to_tree (type, tmp.upper_bound ())); - } - else - vr = value_range (VR_RANGE, - wide_int_to_tree (type, r.lower_bound ()), - wide_int_to_tree (type, r.upper_bound ())); - return vr; + unsigned i = pair * 2; + unsigned j = i + 1; + gcc_checking_assert (i < m_nitems && i < j); + unsigned dst = i; + unsigned ndeleted = j - i + 1; + for (++j; j < m_nitems; ++j) + m_bounds[dst++] = m_bounds[j]; + m_nitems -= ndeleted; } -// Convert a value_range into an irange. +// Canonicalize the current range. -static irange -value_range_to_irange (const value_range_base &vr) +void +irange::canonicalize () { - tree type = vr.type (); - if (vr.varying_p ()) - return irange (type); - if (vr.undefined_p ()) + if (undefined_p ()) + return; + + // Fix any out of order ranges: [10,20][-5,5] into [-5,5][10,20]. + signop sign = TYPE_SIGN (m_type); + for (unsigned p = 0; p < num_pairs (); ++p) + for (unsigned q = p; q < num_pairs (); ++q) + if (wi::gt_p (lower_bound (p), lower_bound (q), sign)) + { + wide_int t1 = lower_bound (p); + wide_int t2 = upper_bound (p); + set_lower_bound (p, lower_bound (q)); + set_upper_bound (p, upper_bound (q)); + set_lower_bound (q, t1); + set_upper_bound (q, t2); + } + // Merge sub-ranges when appropriate. + for (unsigned p = 0; p < num_pairs () - 1; ) { - irange r; - r.set_undefined (type); - return r; + // Merge edges that touch: + // [9,10][11,20] => [9,20] + // [9,10][10,20] => [9,20]. + wi::overflow_type ovf; + if (upper_bound (p) == lower_bound (p + 1) + || (wi::add (upper_bound (p), 1, sign, &ovf) == lower_bound (p + 1) + && !ovf)) + { + set_upper_bound (p, upper_bound (p + 1)); + remove_pair (p + 1); + } + // Merge pairs that bleed into each other: + // [10,20][11,18] => [10,20] + // [10,20][15,30] => [10,30] + else if (wi::le_p (lower_bound (p), lower_bound (p + 1), sign) + && wi::ge_p (upper_bound (p), lower_bound (p + 1), sign)) + { + set_upper_bound (p, wi::max (upper_bound (p), upper_bound (p + 1), sign)); + remove_pair (p + 1); + } + else + ++p; } - return irange (vr.kind (), vr.min (), vr.max ()); -} - -irange::irange (const value_range_base &vr) -{ - *this = value_range_to_irange (vr); + if (flag_checking) + check (); } -#endif // USE_IRANGE - -#if CHECKING_P -#include "stor-layout.h" - -// Ideally this should go in namespace selftest, but range_tests -// needs to be a friend of class irange so it can access -// irange::m_max_pairs. - -#define INT(N) build_int_cst (integer_type_node, (N)) -#define UINT(N) build_int_cstu (unsigned_type_node, (N)) -#define INT16(N) build_int_cst (short_integer_type_node, (N)) -#define UINT16(N) build_int_cstu (short_unsigned_type_node, (N)) -#define INT64(N) build_int_cstu (long_long_integer_type_node, (N)) -#define UINT64(N) build_int_cstu (long_long_unsigned_type_node, (N)) -#define UINT128(N) build_int_cstu (u128_type, (N)) -#define UCHAR(N) build_int_cstu (unsigned_char_type_node, (N)) -#define SCHAR(N) build_int_cst (signed_char_type_node, (N)) - -#define RANGE3(A,B,C,D,E,F) \ -( i1 = irange (INT (A), INT (B)), \ - i2 = irange (INT (C), INT (D)), \ - i3 = irange (INT (E), INT (F)), \ - i1.union_ (i2), \ - i1.union_ (i3), \ - i1 ) - -// Run all of the selftests within this file. +// THIS = THIS U R void -range_tests () +irange::union_ (const irange &r) { - tree u128_type = build_nonstandard_integer_type (128, /*unsigned=*/1); - irange i1, i2, i3; - irange r0, r1, rold; - - // Test that NOT(255) is [0..254] in 8-bit land. - irange not_255 (VR_ANTI_RANGE, UCHAR (255), UCHAR (255)); - ASSERT_TRUE (not_255 == irange (UCHAR (0), UCHAR (254))); - - // Test that NOT(0) is [1..255] in 8-bit land. - irange not_zero = range_nonzero (unsigned_char_type_node); - ASSERT_TRUE (not_zero == irange (UCHAR (1), UCHAR (255))); - - // Check that [0,127][0x..ffffff80,0x..ffffff] - // => ~[128, 0x..ffffff7f]. - r0 = irange (UINT128 (0), UINT128 (127)); - tree high = build_minus_one_cst (u128_type); - // low = -1 - 127 => 0x..ffffff80. - tree low = fold_build2 (MINUS_EXPR, u128_type, high, UINT128(127)); - r1 = irange (low, high); // [0x..ffffff80, 0x..ffffffff] - // r0 = [0,127][0x..ffffff80,0x..fffffff]. - r0.union_ (r1); - // r1 = [128, 0x..ffffff7f]. - r1 = irange (UINT128(128), - fold_build2 (MINUS_EXPR, u128_type, - build_minus_one_cst (u128_type), - UINT128(128))); - r0.invert (); - ASSERT_TRUE (r0 == r1); - - r0.set_varying (integer_type_node); - tree minint = wide_int_to_tree (integer_type_node, r0.lower_bound ()); - tree maxint = wide_int_to_tree (integer_type_node, r0.upper_bound ()); - - r0.set_varying (short_integer_type_node); - tree minshort = wide_int_to_tree (short_integer_type_node, r0.lower_bound ()); - tree maxshort = wide_int_to_tree (short_integer_type_node, r0.upper_bound ()); - - r0.set_varying (unsigned_type_node); - tree maxuint = wide_int_to_tree (unsigned_type_node, r0.upper_bound ()); - - // Check that ~[0,5] => [6,MAX] for unsigned int. - r0 = irange (UINT (0), UINT (5)); - r0.invert (); - ASSERT_TRUE (r0 == irange (UINT(6), maxuint)); - - // Check that ~[10,MAX] => [0,9] for unsigned int. - r0 = irange (VR_RANGE, UINT(10), maxuint); - r0.invert (); - ASSERT_TRUE (r0 == irange (UINT (0), UINT (9))); - - // Check that ~[0,5] => [6,MAX] for unsigned 128-bit numbers. - r0 = irange (VR_ANTI_RANGE, UINT128 (0), UINT128 (5)); - r1 = irange (UINT128(6), build_minus_one_cst (u128_type)); - ASSERT_TRUE (r0 == r1); + gcc_checking_assert (range_compatible_p (m_type, r.m_type)); - // Check that [~5] is really [-MIN,4][6,MAX]. - r0 = irange (VR_ANTI_RANGE, INT (5), INT (5)); - r1 = irange (minint, INT (4)); - r1.union_ (irange (INT (6), maxint)); - ASSERT_FALSE (r1.undefined_p ()); - ASSERT_TRUE (r0 == r1); + if (undefined_p ()) + { + *this = r; + return; + } + else if (r.undefined_p ()) + return; - r1 = irange (INT (5), INT (5)); - r1.check (); - irange r2 (r1); - ASSERT_TRUE (r1 == r2); + // Do not worry about merging and such by reserving twice as many + // pairs as needed, and then simply sort the 2 ranges into this + // intermediate form. + // + // The intermediate result will have the property that the beginning + // of each range is <= the beginning of the next range. There may + // be overlapping ranges at this point. I.e. this would be valid + // [-20, 10], [-10, 0], [0, 20], [40, 90] as it satisfies this + // contraint : -20 < -10 < 0 < 40 When the range is rebuilt into r, + // the merge is performed. + // + // [Xi,Yi]..[Xn,Yn] U [Xj,Yj]..[Xm,Ym] --> [Xk,Yk]..[Xp,Yp] + signop sign = TYPE_SIGN (m_type); + wide_int res[m_max_pairs * 4]; + wide_int u1 ; + wi::overflow_type ovf; + unsigned i = 0, j = 0, k = 0; - r1 = irange (INT (5), INT (10)); - r1.check (); + while (i < m_nitems && j < r.m_nitems) + { + // lower of Xi and Xj is the lowest point. + if (wi::le_p (m_bounds[i], r.m_bounds[j], sign)) + { + res[k++] = m_bounds[i]; + res[k++] = m_bounds[i + 1]; + i += 2; + } + else + { + res[k++] = r.m_bounds[j]; + res[k++] = r.m_bounds[j + 1]; + j += 2; + } + } + for ( ; i < m_nitems; i += 2) + { + res[k++] = m_bounds[i]; + res[k++] = m_bounds[i + 1]; + } + for ( ; j < r.m_nitems; j += 2) + { + res[k++] = r.m_bounds[j]; + res[k++] = r.m_bounds[j + 1]; + } - r1 = irange (integer_type_node, - wi::to_wide (INT (5)), wi::to_wide (INT (10))); - r1.check (); - ASSERT_TRUE (r1.contains_p (INT (7))); + // Now normalize the vector removing any overlaps. + i = 2; + int prec = TYPE_PRECISION (m_type); + wide_int max_val = wi::max_value (prec, sign); + for (j = 2; j < k ; j += 2) + { + if (res[i - 1] == max_val) + break; + u1 = wi::add (res[i - 1], 1, sign, &ovf); - r1 = irange (SCHAR (0), SCHAR (20)); - ASSERT_TRUE (r1.contains_p (SCHAR(15))); - ASSERT_FALSE (r1.contains_p (SCHAR(300))); + // Overflow indicates we are at MAX already. + // A wide int bug requires the previous max_val check + // trigger: gcc.c-torture/compile/pr80443.c with -O3 + if (ovf) + break; - // If a range is in any way outside of the range for the converted - // to range, default to the range for the new type. - r1 = irange (integer_zero_node, maxint); - r1.cast (short_integer_type_node); - ASSERT_TRUE (r1.lower_bound () == wi::to_wide (minshort) - && r1.upper_bound() == wi::to_wide (maxshort)); + // Current upper+1 is >= lower bound next pair, then we merge ranges. + if (wi::ge_p (u1, res[j], sign)) + { + // New upper bounds is greater of current or the next one. + if (wi::gt_p (res[j + 1], res [i - 1], sign)) + res [i - 1] = res[j + 1]; + } + else + { + // This is a new distinct range, but no point in copying it + // if it is already in the right place. + if (i != j) + { + res[i++] = res[j]; + res[i++] = res[j + 1]; + } + else + i += 2; - // (unsigned char)[-5,-1] => [251,255]. - r0 = rold = irange (SCHAR (-5), SCHAR (-1)); - r0.cast (unsigned_char_type_node); - ASSERT_TRUE (r0 == irange (UCHAR (251), UCHAR (255))); - r0.cast (signed_char_type_node); - ASSERT_TRUE (r0 == rold); + } + } + + // At this point, the vector should have i ranges, none + // overlapping. Now it simply needs to be copied, and if there are + // too many ranges, merge some. We wont do any analysis as to what + // the "best" merges are, simply combine the final ranges into one. + if (i > m_max_pairs * 2) + { + res[m_max_pairs * 2 - 1] = res[i - 1]; + i = m_max_pairs * 2; + } - // (signed char)[15, 150] => [-128,-106][15,127]. - r0 = rold = irange (UCHAR (15), UCHAR (150)); - r0.cast (signed_char_type_node); - r1 = irange (SCHAR (15), SCHAR (127)); - r2 = irange (SCHAR (-128), SCHAR (-106)); - r1.union_ (r2); - ASSERT_TRUE (r1 == r0); - r0.cast (unsigned_char_type_node); - ASSERT_TRUE (r0 == rold); + for (j = 0; j < i ; j++) + m_bounds[j] = res [j]; + m_nitems = i; - // (unsigned char)[-5, 5] => [0,5][251,255]. - r0 = rold = irange (SCHAR (-5), SCHAR (5)); - r0.cast (unsigned_char_type_node); - r1 = irange (UCHAR (251), UCHAR (255)); - r2 = irange (UCHAR (0), UCHAR (5)); - r1.union_ (r2); - ASSERT_TRUE (r0 == r1); - r0.cast (signed_char_type_node); - ASSERT_TRUE (r0 == rold); + if (flag_checking) + check (); +} - // (unsigned char)[-5,5] => [0,5][251,255]. - r0 = irange (INT (-5), INT (5)); - r0.cast (unsigned_char_type_node); - r1 = irange (UCHAR (0), UCHAR (5)); - r1.union_ (irange (UCHAR (251), UCHAR (255))); - ASSERT_TRUE (r0 == r1); +// THIS = THIS ^ [X,Y]. - // (unsigned char)[5U,1974U] => [0,255]. - r0 = irange (UINT (5), UINT (1974)); - r0.cast (unsigned_char_type_node); - ASSERT_TRUE (r0 == irange (UCHAR (0), UCHAR (255))); - r0.cast (integer_type_node); - // Going to a wider range should not sign extend. - ASSERT_TRUE (r0 == irange (INT (0), INT (255))); +void +irange::intersect (const wide_int &x, const wide_int &y) +{ + unsigned pos = 0; - // (unsigned char)[-350,15] => [0,255]. - r0 = irange (INT (-350), INT (15)); - r0.cast (unsigned_char_type_node); - ASSERT_TRUE (r0 == irange (TYPE_MIN_VALUE (unsigned_char_type_node), - TYPE_MAX_VALUE (unsigned_char_type_node))); + for (unsigned i = 0; i < m_nitems; i += 2) + { + signop sign = TYPE_SIGN (m_type); + wide_int newlo = wi::max (m_bounds[i], x, sign); + wide_int newhi = wi::min (m_bounds[i + 1], y, sign); + if (wi::gt_p (newlo, newhi, sign)) + { + // If the new sub-range doesn't make sense, it's an + // impossible range and must be kept out of the result. + } + else + { + m_bounds[pos++] = newlo; + m_bounds[pos++] = newhi; + } + } + m_nitems = pos; + if (flag_checking) + check (); +} - // Casting [-120,20] from signed char to unsigned short. - // => [0, 20][0xff88, 0xffff]. - r0 = irange (SCHAR (-120), SCHAR (20)); - r0.cast (short_unsigned_type_node); - r1 = irange (UINT16 (0), UINT16 (20)); - r2 = irange (UINT16 (0xff88), UINT16 (0xffff)); - r1.union_ (r2); - ASSERT_TRUE (r0 == r1); - // A truncating cast back to signed char will work because [-120, 20] - // is representable in signed char. - r0.cast (signed_char_type_node); - ASSERT_TRUE (r0 == irange (SCHAR (-120), SCHAR (20))); +// THIS = THIS ^ R. - // unsigned char -> signed short - // (signed short)[(unsigned char)25, (unsigned char)250] - // => [(signed short)25, (signed short)250] - r0 = rold = irange (UCHAR (25), UCHAR (250)); - r0.cast (short_integer_type_node); - r1 = irange (INT16 (25), INT16 (250)); - ASSERT_TRUE (r0 == r1); - r0.cast (unsigned_char_type_node); - ASSERT_TRUE (r0 == rold); +void +irange::intersect (const irange &r) +{ + gcc_checking_assert (range_compatible_p (m_type, r.m_type)); + irange orig_range (*this); - // Test casting a wider signed [-MIN,MAX] to a nar`rower unsigned. - r0 = irange (TYPE_MIN_VALUE (long_long_integer_type_node), - TYPE_MAX_VALUE (long_long_integer_type_node)); - r0.cast (short_unsigned_type_node); - r1 = irange (TYPE_MIN_VALUE (short_unsigned_type_node), - TYPE_MAX_VALUE (short_unsigned_type_node)); - ASSERT_TRUE (r0 == r1); + // Intersection with an empty range is an empty range. + set_undefined (); + if (orig_range.undefined_p () || r.undefined_p ()) + return; - // Test that casting a range with MAX_PAIRS that changes sign is - // done conservatively. + // The general algorithm is as follows. // - // (unsigned short)[-5,5][20,30][40,50]... - // => (unsigned short)[-5,50] - // => [0,50][65531,65535] - r0 = irange (INT16 (-5), INT16 (5)); - gcc_assert (irange::m_max_pairs * 2 * 10 + 10 < 32767); - unsigned i; - for (i = 2; i < irange::m_max_pairs * 2; i += 2) + // Intersect each sub-range of R with all of ORIG_RANGE one at a time, and + // join/union the results of these intersections together. I.e: + // + // [10,20][30,40][50,60] ^ [15,25][38,51][55,70] + // + // Step 1: [10,20][30,40][50,60] ^ [15,25] => [15,20] + // Step 2: [10,20][30,40][50,60] ^ [38,51] => [38,40] + // Step 3: [10,20][30,40][50,60] ^ [55,70] => [55,60] + // Final: [15,20] U [38,40] U [55,60] => [15,20][38,40][55,60] + for (unsigned i = 0; i < r.m_nitems; i += 2) { - r1 = irange (INT16 (i * 10), INT16 (i * 10 + 10)); - r0.union_ (r1); + irange tmp (orig_range); + tmp.intersect (r.m_bounds[i], r.m_bounds[i + 1]); + union_ (tmp); + } + // There is no check here because the calls to union_ above would + // have verified sanity. +} + +// Set THIS to the inverse of its range. + +void +irange::invert () +{ + // We always need one more set of bounds to represent an inverse, so + // if we're at the limit, we can't properly represent things. + // + // For instance, to represent the inverse of a 2 sub-range set + // [5, 10][20, 30], we would need a 3 sub-range set + // [-MIN, 4][11, 19][31, MAX]. + // + // In this case, return the most conservative thing. + // + // However, if any of the extremes of the range are -MIN/+MAX, we + // know we will not need an extra bound. For example: + // + // INVERT([-MIN,20][30,40]) => [21,29][41,+MAX] + // INVERT([-MIN,20][30,MAX]) => [21,29] + wide_int min = wi::min_value (TYPE_PRECISION (m_type), TYPE_SIGN (m_type)); + wide_int max = wi::max_value (TYPE_PRECISION (m_type), TYPE_SIGN (m_type)); + if (m_nitems == m_max_pairs * 2 + && m_bounds[0] != min + && m_bounds[m_nitems] != max) + { + m_bounds[1] = max; + m_nitems = 2; + return; } - r0.cast(short_unsigned_type_node); - r1 = irange (UINT16 (0), UINT16 ((i - 2) * 10 + 10)); - r2 = irange (UINT16 (65531), UINT16 (65535)); - r1.union_ (r2); - ASSERT_TRUE (r0 == r1); - - // NOT([10,20]) ==> [-MIN,9][21,MAX]. - r0 = r1 = irange (INT (10), INT (20)); - r2 = irange (minint, INT(9)); - r2.union_ (irange (INT(21), maxint)); - ASSERT_FALSE (r2.undefined_p ()); - r1.invert (); - ASSERT_TRUE (r1 == r2); - // Test that NOT(NOT(x)) == x. - r2.invert (); - ASSERT_TRUE (r0 == r2); - - // NOT(-MIN,+MAX) is the empty set and should return false. - r0 = irange (minint, maxint); - r0.invert (); - ASSERT_TRUE (r0.undefined_p ()); - r1.set_undefined (); - ASSERT_TRUE (r0 == r1); - // Test that booleans and their inverse work as expected. - r0 = range_zero (boolean_type_node); - ASSERT_TRUE (r0 == irange (build_zero_cst (boolean_type_node), - build_zero_cst (boolean_type_node))); - r0.invert(); - ASSERT_TRUE (r0 == irange (build_one_cst (boolean_type_node), - build_one_cst (boolean_type_node))); + // The inverse of the empty set is the entire domain. + if (undefined_p ()) + { + set_varying (m_type); + return; + } - // Casting NONZERO to a narrower type will wrap/overflow so - // it's just the entire range for the narrower type. + // The algorithm is as follows. To calculate INVERT ([a,b][c,d]), we + // generate [-MIN, a-1][b+1, c-1][d+1, MAX]. // - // "NOT 0 at signed 32-bits" ==> [-MIN_32,-1][1, +MAX_32]. This is - // is outside of the range of a smaller range, return the full - // smaller range. - r0 = range_nonzero (integer_type_node); - r0.cast (short_integer_type_node); - r1 = irange (TYPE_MIN_VALUE (short_integer_type_node), - TYPE_MAX_VALUE (short_integer_type_node)); - ASSERT_TRUE (r0 == r1); + // If there is an over/underflow in the calculation for any + // sub-range, we eliminate that subrange. This allows us to easily + // calculate INVERT([-MIN, 5]) with: [-MIN, -MIN-1][6, MAX]. And since + // we eliminate the underflow, only [6, MAX] remains. - // Casting NONZERO from a narrower signed to a wider signed. - // - // NONZERO signed 16-bits is [-MIN_16,-1][1, +MAX_16]. - // Converting this to 32-bits signed is [-MIN_16,-1][1, +MAX_16]. - r0 = range_nonzero (short_integer_type_node); - r0.cast (integer_type_node); - r1 = irange (INT (-32768), INT (-1)); - r2 = irange (INT (1), INT (32767)); - r1.union_ (r2); - ASSERT_TRUE (r0 == r1); + unsigned i = 0; + wi::overflow_type ovf; - if (irange::m_max_pairs > 2) + // Construct leftmost range. + irange orig_range (*this); + m_nitems = 0; + // If this is going to underflow on the MINUS 1, don't even bother + // checking. This also handles subtracting one from an unsigned 0, + // which doesn't set the underflow bit. + if (min != orig_range.m_bounds[i]) { - // ([10,20] U [5,8]) U [1,3] ==> [1,3][5,8][10,20]. - r0 = irange (INT (10), INT (20)); - r1 = irange (INT (5), INT (8)); - r0.union_ (r1); - r1 = irange (INT (1), INT (3)); - r0.union_ (r1); - ASSERT_TRUE (r0 == RANGE3 (1, 3, 5, 8, 10, 20)); - - // [1,3][5,8][10,20] U [-5,0] => [-5,3][5,8][10,20]. - r1 = irange (INT (-5), INT (0)); - r0.union_ (r1); - ASSERT_TRUE (r0 == RANGE3 (-5, 3, 5, 8, 10, 20)); + m_bounds[m_nitems++] = min; + m_bounds[m_nitems++] = subtract_one (orig_range.m_bounds[i], + m_type, ovf); + if (ovf) + m_nitems = 0; } - - // [10,20] U [30,40] ==> [10,20][30,40]. - r0 = irange (INT (10), INT (20)); - r1 = irange (INT (30), INT (40)); - r0.union_ (r1); - ASSERT_TRUE (r0 == range_union (irange (INT (10), INT (20)), - irange (INT (30), INT (40)))); - if (irange::m_max_pairs > 2) + i++; + // Construct middle ranges if applicable. + if (orig_range.m_nitems > 2) { - // [10,20][30,40] U [50,60] ==> [10,20][30,40][50,60]. - r1 = irange (INT (50), INT (60)); - r0.union_ (r1); - ASSERT_TRUE (r0 == RANGE3 (10, 20, 30, 40, 50, 60)); - // [10,20][30,40][50,60] U [70, 80] ==> [10,20][30,40][50,60][70,80]. - r1 = irange (INT (70), INT (80)); - r0.union_ (r1); - - r2 = RANGE3 (10, 20, 30, 40, 50, 60); - r2.union_ (irange (INT (70), INT (80))); - ASSERT_TRUE (r0 == r2); + unsigned j = i; + for (; j < (unsigned) (orig_range.m_nitems - 2); j += 2) + { + // The middle ranges cannot have MAX/MIN, so there's no need + // to check for unsigned overflow on the +1 and -1 here. + m_bounds[m_nitems++] + = wi::add (orig_range.m_bounds[j], 1, TYPE_SIGN (m_type), &ovf); + m_bounds[m_nitems++] + = subtract_one (orig_range.m_bounds[j + 1], m_type, ovf); + if (ovf) + m_nitems -= 2; + } + i = j; + } + // Construct rightmost range. + // + // However, if this will overflow on the PLUS 1, don't even bother. + // This also handles adding one to an unsigned MAX, which doesn't + // set the overflow bit. + if (max != orig_range.m_bounds[i]) + { + m_bounds[m_nitems++] + = wi::add (orig_range.m_bounds[i], 1, TYPE_SIGN (m_type), &ovf); + m_bounds[m_nitems++] = max; + if (ovf) + m_nitems -= 2; } - // Make sure NULL and non-NULL of pointer types work, and that - // inverses of them are consistent. - tree voidp = build_pointer_type (void_type_node); - r0 = range_zero (voidp); - r1 = r0; - r0.invert (); - r0.invert (); - ASSERT_TRUE (r0 == r1); + if (flag_checking) + check (); +} - if (irange::m_max_pairs > 2) - { - // [10,20][30,40][50,60] U [6,35] => [6,40][50,60]. - r0 = RANGE3 (10, 20, 30, 40, 50, 60); - r1 = irange (INT (6), INT (35)); - r0.union_ (r1); - ASSERT_TRUE (r0 == range_union (irange (INT (6), INT (40)), - irange (INT (50), INT (60)))); +// Dump the current range onto BUFFER. - // [10,20][30,40][50,60] U [6,60] => [6,60] */ - r0 = RANGE3 (10, 20, 30, 40, 50, 60); - r1 = irange (INT (6), INT (60)); - r0.union_ (r1); - ASSERT_TRUE (r0 == irange (INT (6), INT (60))); +void +irange::dump (pretty_printer *buffer) const +{ + wide_int min = wi::min_value (TYPE_PRECISION (m_type), TYPE_SIGN (m_type)); + wide_int max = wi::max_value (TYPE_PRECISION (m_type), TYPE_SIGN (m_type)); + if (POINTER_TYPE_P (m_type) && nonzero_p ()) + pp_string (buffer, "[ non-zero pointer ]"); + else + for (unsigned i = 0; i < m_nitems; ++i) + { + if (i % 2 == 0) + pp_character (buffer, '['); - // [10,20][30,40][50,60] U [6,70] => [6,70]. - r0 = RANGE3 (10, 20, 30, 40, 50, 60); - r1 = irange (INT (6), INT (70)); - r0.union_ (r1); - ASSERT_TRUE (r0 == irange (INT (6), INT (70))); + // Wide ints may be sign extended to the full extent of the + // underlying HWI storage, even if the precision we care about + // is smaller. Chop off the excess bits for prettier output. + signop sign = TYPE_UNSIGNED (m_type) ? UNSIGNED : SIGNED; + widest_int val = widest_int::from (m_bounds[i], sign); + val &= wi::mask (m_bounds[i].get_precision (), false); - // [10,20][30,40][50,60] U [35,70] => [10,20][30,70]. - r0 = RANGE3 (10, 20, 30, 40, 50, 60); - r1 = irange (INT (35), INT (70)); - r0.union_ (r1); - ASSERT_TRUE (r0 == range_union (irange (INT (10), INT (20)), - irange (INT (30), INT (70)))); - } + if (i == 0 + && INTEGRAL_TYPE_P (m_type) + && !TYPE_UNSIGNED (m_type) + && m_bounds[i] == min + && TYPE_PRECISION (m_type) != 1) + pp_string (buffer, "-INF"); + else if (i + 1 == m_nitems + && INTEGRAL_TYPE_P (m_type) + && !TYPE_UNSIGNED (m_type) + && m_bounds[i] == max + && TYPE_PRECISION (m_type) != 1) + pp_string (buffer, "+INF"); + else + { + if (val > 0xffff) + print_hex (val, pp_buffer (buffer)->digit_buffer); + else + print_dec (m_bounds[i], pp_buffer (buffer)->digit_buffer, sign); + pp_string (buffer, pp_buffer (buffer)->digit_buffer); + } + if (i % 2 == 0) + pp_string (buffer, ", "); + else + pp_character (buffer, ']'); + } + if (undefined_p ()) + pp_string (buffer, "[]"); - // [10,20][30,40] U [25,70] => [10,70]. - r0 = range_union (irange (INT (10), INT (20)), - irange (INT (30), INT (40))); - r1 = irange (INT (25), INT (70)); - r0.union_ (r1); - ASSERT_TRUE (r0 == range_union (irange (INT (10), INT (20)), - irange (INT (25), INT (70)))); + pp_character (buffer, ' '); + dump_generic_node (buffer, m_type, 0, TDF_NONE, false); + pp_flush (buffer); +} + +// Dump the current range onto FILE F. + +void +irange::dump (FILE *f) const +{ + pretty_printer buffer; + buffer.buffer->stream = f; + dump (&buffer); +} + +// Like above but dump to STDERR. +// +// You'd think we could have a default parameter for dump(FILE), +// but gdb currently doesn't do default parameters gracefully-- or at +// all, and since this is a function we need to be callable from the +// debugger... + +void +irange::dump () const +{ + dump (stderr); +} - if (irange::m_max_pairs > 2) - { - // [10,20][30,40][50,60] U [15,35] => [10,40][50,60]. - r0 = RANGE3 (10, 20, 30, 40, 50, 60); - r1 = irange (INT (15), INT (35)); - r0.union_ (r1); - ASSERT_TRUE (r0 == range_union (irange (INT (10), INT (40)), - irange (INT (50), INT (60)))); - } +// Initialize the current irange_storage to the irange in IR. - // [10,20] U [15, 30] => [10, 30]. - r0 = irange (INT (10), INT (20)); - r1 = irange (INT (15), INT (30)); - r0.union_ (r1); - ASSERT_TRUE (r0 == irange (INT (10), INT (30))); +void +irange_storage::set (const irange &ir) +{ + unsigned precision = TYPE_PRECISION (ir.type ()); + trailing_bounds.set_precision (precision); + unsigned i; + for (i = 0; i < ir.num_pairs () * 2; ++i) + trailing_bounds[i] = ir.m_bounds[i]; - // [10,20] U [25,25] => [10,20][25,25]. - r0 = irange (INT (10), INT (20)); - r1 = irange (INT (25), INT (25)); - r0.union_ (r1); - ASSERT_TRUE (r0 == range_union (irange (INT (10), INT (20)), - irange (INT (25), INT (25)))); + // Clear the remaining empty ranges. + for (; i < irange::m_max_pairs * 2; i += 2) + set_empty_pair (i, i + 1, ir.type ()); +} - if (irange::m_max_pairs > 2) +// Update a previously initialized irange_storage to NEW_RANGE, iff the +// precision of the present range is the same as the precision of +// the new range. Return TRUE if update was successful. + +bool +irange_storage::update (const irange &new_range) +{ + if (trailing_bounds.get_precision () == TYPE_PRECISION (new_range.type ())) { - // [10,20][30,40][50,60] U [35,35] => [10,20][30,40][50,60]. - r0 = RANGE3 (10, 20, 30, 40, 50, 60); - r1 = irange (INT (35), INT (35)); - r0.union_ (r1); - ASSERT_TRUE (r0 == RANGE3 (10, 20, 30, 40, 50, 60)); + set (new_range); + return true; } + return false; +} - // [15,40] U [] => [15,40]. - r0 = irange (INT (15), INT (40)); - r1.set_undefined (); - r0.union_ (r1); - ASSERT_TRUE (r0 == irange (INT (15), INT (40))); - - // [10,20] U [10,10] => [10,20]. - r0 = irange (INT (10), INT (20)); - r1 = irange (INT (10), INT (10)); - r0.union_ (r1); - ASSERT_TRUE (r0 == irange (INT (10), INT (20))); - - // [10,20] U [9,9] => [9,20]. - r0 = irange (INT (10), INT (20)); - r1 = irange (INT (9), INT (9)); - r0.union_ (r1); - ASSERT_TRUE (r0 == irange (INT (9), INT (20))); +// Return TRUE if range contains exactly one element and set RESULT to it. - if (irange::m_max_pairs > 2) +bool +irange::singleton_p (tree *result) const +{ + if (num_pairs () == 1 && lower_bound (0) == upper_bound (0)) { - // [10,10][12,12][20,100] ^ [15,200]. - r0 = RANGE3 (10, 10, 12, 12, 20, 100); - r1 = irange (INT (15), INT (200)); - r0.intersect (r1); - ASSERT_TRUE (r0 == irange (INT (20), INT (100))); + if (result) + *result = wide_int_to_tree (type (), lower_bound ()); + return true; + } + return false; +} - // [10,20][30,40][50,60] ^ [15,25][38,51][55,70] - // => [15,20][38,40][50,51][55,60] - r0 = RANGE3 (10, 20, 30, 40, 50, 60); - r1 = RANGE3 (15, 25, 38, 51, 55, 70); - r0.intersect (r1); - if (irange::m_max_pairs == 3) - { - // When pairs==3, we don't have enough space, so - // conservatively handle things. Thus, the ...[50,60]. - ASSERT_TRUE (r0 == RANGE3 (15, 20, 38, 40, 50, 60)); - } - else - { - r2 = RANGE3 (15, 20, 38, 40, 50, 51); - r2.union_ (irange (INT (55), INT (60))); - ASSERT_TRUE (r0 == r2); - } +// Convert irange to a value_range. - // [15,20][30,40][50,60] ^ [15,35][40,90][100,200] - // => [15,20][30,35][40,60] - r0 = RANGE3 (15, 20, 30, 40, 50, 60); - r1 = RANGE3 (15, 35, 40, 90, 100, 200); - r0.intersect (r1); - if (irange::m_max_pairs == 3) - { - // When pairs==3, we don't have enough space, so - // conservatively handle things. - ASSERT_TRUE (r0 == RANGE3 (15, 20, 30, 35, 40, 60)); - } - else +value_range_base +irange_to_value_range (const irange &r) +{ + value_range_base vr; + if (r.varying_p ()) + { + vr.set_varying (r.type ()); + return vr; + } + if (r.undefined_p ()) + { + vr.set_undefined (r.type ()); + return vr; + } + tree type = r.type (); + unsigned int precision = TYPE_PRECISION (type); + // Represent non-zero correctly. + if (TYPE_UNSIGNED (type) + && r.num_pairs () == 1 + && r.lower_bound () == wi::uhwi (1, precision) + && r.upper_bound () == wi::max_value (precision, UNSIGNED) + // Do not get confused by booleans. + && TYPE_PRECISION (type) != 1) + vr = value_range (VR_ANTI_RANGE, + build_int_cst (type, 0), build_int_cst (type, 0)); + // Represent anti-ranges. + else if ((r.num_pairs () == 2 + || r.num_pairs () == 3) + // Do not get confused by booleans. + && TYPE_PRECISION (type) != 1 + && r.lower_bound () == wi::min_value (precision, TYPE_SIGN (type)) + && r.upper_bound () == wi::max_value (precision, TYPE_SIGN (type))) + { + irange tmp = r; + if (r.num_pairs () == 3) { - r2 = RANGE3 (15, 20, 30, 35, 40, 40); - r2.union_ (irange (INT (50), INT (60))); - ASSERT_TRUE (r0 == r2); + // Hack to make up for the fact that we can compute finer + // grained ranges that VRP can only approximate with an + // anti-range. Attempt to reconstruct sub-ranges of the form: + // + // [0, 94][96, 127][0xff80, 0xffff] => ~[95,95] + // [0, 1][3, 0x7fffffff][0xff..80000000, 0xff..ff] => ~[2, 2]. + // + // Merge the last two bounds. + tmp = irange (type, r.lower_bound (0), r.upper_bound (0)); + tmp.union_ (irange (type, r.lower_bound (1), r.upper_bound ())); } - - // Test cases where a union inserts a sub-range inside a larger - // range. - // - // [8,10][135,255] U [14,14] => [8,10][14,14][135,255] - r0 = range_union (irange (INT (8), INT (10)), - irange (INT (135), INT (255))); - r1 = irange (INT (14), INT (14)); - r0.union_ (r1); - ASSERT_TRUE (r0 == RANGE3 (8, 10, 14, 14, 135, 255)); + tmp = range_invert (tmp); + vr = value_range (VR_ANTI_RANGE, + wide_int_to_tree (type, tmp.lower_bound ()), + wide_int_to_tree (type, tmp.upper_bound ())); } + else + vr = value_range (VR_RANGE, + wide_int_to_tree (type, r.lower_bound ()), + wide_int_to_tree (type, r.upper_bound ())); + return vr; +} - // [10,20] ^ [15,30] => [15,20]. - r0 = irange (INT (10), INT (20)); - r1 = irange (INT (15), INT (30)); - r0.intersect (r1); - ASSERT_TRUE (r0 == irange (INT (15), INT (20))); - - // [10,20][30,40] ^ [40,50] => [40,40]. - r0 = range_union (irange (INT (10), INT (20)), - irange (INT (30), INT (40))); - r1 = irange (INT (40), INT (50)); - r0.intersect (r1); - ASSERT_TRUE (r0 == irange (INT (40), INT (40))); - - // Test non-destructive intersection. - r0 = rold = irange (INT (10), INT (20)); - ASSERT_FALSE (range_intersect (r0, irange (INT (15), - INT (30))).undefined_p ()); - ASSERT_TRUE (r0 == rold); - - // Test the internal sanity of wide_int's wrt HWIs. - ASSERT_TRUE (wi::max_value (TYPE_PRECISION (boolean_type_node), - TYPE_SIGN (boolean_type_node)) - == wi::uhwi (1, TYPE_PRECISION (boolean_type_node))); - - // Test irange_storage. - r0 = irange (INT (5), INT (10)); - irange_storage *stow = irange_storage::alloc (r0); - r1 = irange (integer_type_node, stow); - ASSERT_TRUE (r0 == r1); - - // Test irange_storage with signed 1-bit fields. - tree s1bit_type = make_signed_type (1); - r0 = irange (build_int_cst (s1bit_type, -1), build_int_cst (s1bit_type, 0)); - stow = irange_storage::alloc (r0); - r1 = irange (s1bit_type, stow); - ASSERT_TRUE (r0 == r1); - - // Test zero_p(). - r0 = irange (INT (0), INT (0)); - ASSERT_TRUE (r0.zero_p ()); +// Convert a value_range into an irange. - // Test nonzero_p(). - r0 = irange (INT (0), INT (0)); - r0.invert (); - ASSERT_TRUE (r0.nonzero_p ()); +static irange +value_range_to_irange (const value_range_base &vr) +{ + tree type = vr.type (); + if (vr.varying_p ()) + return irange (type); + if (vr.undefined_p ()) + { + irange r; + r.set_undefined (type); + return r; + } + return irange (vr.kind (), vr.min (), vr.max ()); +} - // Test irange / value_range conversion functions. - r0 = irange (VR_ANTI_RANGE, INT (10), INT (20)); - value_range_base vr = r0; - ASSERT_TRUE (vr.kind () == VR_ANTI_RANGE); - ASSERT_TRUE (wi::eq_p (10, wi::to_wide (vr.min ())) - && wi::eq_p (20, wi::to_wide (vr.max ()))); - r1 = vr; - ASSERT_TRUE (r0 == r1); +irange::irange (const value_range_base &vr) +{ + *this = value_range_to_irange (vr); } -#endif // CHECKING_P +#endif // USE_IRANGE diff --git a/gcc/range.h b/gcc/range.h index 9205d0b..5b10232 100644 --- a/gcc/range.h +++ b/gcc/range.h @@ -61,10 +61,7 @@ class irange irange (value_range_kind, tree, tree); irange (tree, tree); irange (tree type, const irange_storage *); -#if USE_IRANGE - /* Only for branch. */ irange (const value_range_base &); -#endif static bool supports_type_p (tree type); static bool supports_ssa_p (tree ssa); @@ -341,10 +338,6 @@ irange range_nonzero (tree type); irange range_intersect (const irange &, const irange &); irange range_union (const irange &, const irange &); irange range_invert (const irange &); -irange range_from_ssa (tree ssa); irange range_positives (tree type); irange range_negatives (tree type); - -// Extract a range from a tree node. -bool get_tree_range (irange &r, tree expr); #endif // GCC_RANGE_H diff --git a/gcc/ssa-range-gori.cc b/gcc/ssa-range-gori.cc index 1e67da7..f5fdaf0 100644 --- a/gcc/ssa-range-gori.cc +++ b/gcc/ssa-range-gori.cc @@ -29,6 +29,7 @@ along with GCC; see the file COPYING3. If not see #include "diagnostic-core.h" #include "wide-int.h" #include "ssa-range.h" +#include "fold-const.h" // Construct a range_def_chain @@ -470,9 +471,81 @@ gori_map::dump(FILE *f) } } +// Set range from an SSA_NAME's available range. If there is no +// available range, build a range for its entire domain. -// Overloaded get_tree_range to perform substitution of NAME wth -// RANGE_OF_NAME if expr happens to match it. +irange +range_from_ssa (tree ssa) +{ + tree type = TREE_TYPE (ssa); + gcc_checking_assert (irange::supports_type_p (type)); + if (!SSA_NAME_RANGE_INFO (ssa) || POINTER_TYPE_P (type)) + return irange (type); + wide_int min, max; + enum value_range_kind kind = get_range_info (ssa, &min, &max); + return irange (kind, type, min, max); +} + +// This function returns a range for tree node EXPR in R. Return +// false if ranges are not supported. + +bool +get_tree_range (irange &r, tree expr) +{ + tree type; + switch (TREE_CODE (expr)) + { + case INTEGER_CST: + if (!TREE_OVERFLOW_P (expr)) + r = irange (expr, expr); + else + // If we encounter an overflow, simply punt and drop to varying + // since we hvae no idea how it will be used. + r.set_varying (TREE_TYPE (expr)); + return true; + + case SSA_NAME: + if (irange::supports_ssa_p (expr)) + { + r = range_from_ssa (expr); + return true; + } + break; + + case ADDR_EXPR: + { + // handle &var which can show up in phi arguments + bool ov; + type = TREE_TYPE (expr); + if (irange::supports_type_p (type)) + { + if (tree_single_nonzero_warnv_p (expr, &ov)) + r = range_nonzero (type); + else + r.set_varying (type); + return true; + } + break; + } + + default: + if (TYPE_P (expr)) + type = expr; + else + type = TREE_TYPE (expr); + if (irange::supports_type_p (type)) + { + // Set to range for this type. + r.set_varying (type); + return true; + } + break; + } + return false; +} + +// Same but perform substitution of NAME with RANGE_OF_NAME if expr +// happens to match it. static bool get_tree_range (irange &r, tree expr, tree name, irange *range_of_name) diff --git a/gcc/ssa-range-gori.h b/gcc/ssa-range-gori.h index e98b309..080564b 100644 --- a/gcc/ssa-range-gori.h +++ b/gcc/ssa-range-gori.h @@ -186,6 +186,7 @@ private: irange m_bool_one; /* Boolean true cached. */ }; - +bool get_tree_range (irange &r, tree expr); +irange range_from_ssa (tree ssa); #endif // GCC_SSA_RANGE_GORI_H diff --git a/gcc/ssa-range.h b/gcc/ssa-range.h index 44201a0..80ce3f6 100644 --- a/gcc/ssa-range.h +++ b/gcc/ssa-range.h @@ -28,7 +28,6 @@ along with GCC; see the file COPYING3. If not see extern gimple_stmt_iterator gsi_outgoing_range_stmt (basic_block bb); extern gimple *gimple_outgoing_range_stmt_p (basic_block bb); extern gimple *gimple_outgoing_edge_range_p (irange &r, edge e); -extern bool get_tree_range (irange &r, tree expr); // This is the basic range generator interface. // diff --git a/gcc/tree-vrp.h b/gcc/tree-vrp.h index b186c25..1d4fe3b 100644 --- a/gcc/tree-vrp.h +++ b/gcc/tree-vrp.h @@ -22,8 +22,8 @@ along with GCC; see the file COPYING3. If not see class value_range_storage; -// Set to one if irange is a standalone class containing multiple -// sub-ranges, or zero if irange is just value_range_base underneath. +// Set to one if irange is a standalone class, or zero if irange is +// just value_range_base underneath. #define USE_IRANGE 1 #if USE_IRANGE diff --git a/gcc/vr-values.c b/gcc/vr-values.c index 0d80f1e..d0e2583 100644 --- a/gcc/vr-values.c +++ b/gcc/vr-values.c @@ -1754,8 +1754,7 @@ range_misc::adjust_range_with_loop (irange &ir, struct loop *loop, /* Like in PR19590, scev can return a constant function. */ if (is_gimple_min_invariant (chrec)) { - extern bool get_tree_range (irange &r, tree expr); - get_tree_range (ir, chrec); + ir = irange (chrec, chrec); return; } -- cgit v1.1