diff options
Diffstat (limited to 'gcc/value-range.cc')
| -rw-r--r-- | gcc/value-range.cc | 462 |
1 files changed, 417 insertions, 45 deletions
diff --git a/gcc/value-range.cc b/gcc/value-range.cc index edd10bf..bcc6651 100644 --- a/gcc/value-range.cc +++ b/gcc/value-range.cc @@ -291,41 +291,20 @@ frange::set (tree min, tree max, value_range_kind kind) m_kind = kind; m_type = TREE_TYPE (min); m_props.set_varying (); + m_min = *TREE_REAL_CST_PTR (min); + m_max = *TREE_REAL_CST_PTR (max); - bool is_min = vrp_val_is_min (min); - bool is_max = vrp_val_is_max (max); bool is_nan = (real_isnan (TREE_REAL_CST_PTR (min)) || real_isnan (TREE_REAL_CST_PTR (max))); // Ranges with a NAN and a non-NAN endpoint are nonsensical. gcc_checking_assert (!is_nan || operand_equal_p (min, max)); - // The properties for singletons can be all set ahead of time. - if (operand_equal_p (min, max)) - { - // Set INF properties. - if (is_min) - m_props.ninf_set_yes (); - else - m_props.ninf_set_no (); - if (is_max) - m_props.inf_set_yes (); - else - m_props.inf_set_no (); - // Set NAN property. - if (is_nan) - m_props.nan_set_yes (); - else - m_props.nan_set_no (); - } - else - { - // Mark when the endpoints can't be +-INF. - if (!is_min) - m_props.ninf_set_no (); - if (!is_max) - m_props.inf_set_no (); - } + // Set NAN property if we're absolutely sure. + if (is_nan && operand_equal_p (min, max)) + m_props.nan_set_yes (); + else if (!HONOR_NANS (m_type)) + m_props.nan_set_no (); // Check for swapped ranges. gcc_checking_assert (is_nan || tree_compare (LE_EXPR, min, max)); @@ -336,6 +315,16 @@ frange::set (tree min, tree max, value_range_kind kind) verify_range (); } +// Setter for frange from REAL_VALUE_TYPE endpoints. + +void +frange::set (tree type, + const REAL_VALUE_TYPE &min, const REAL_VALUE_TYPE &max, + value_range_kind kind) +{ + set (build_real (type, min), build_real (type, max), kind); +} + // Normalize range to VARYING or UNDEFINED, or vice versa. Return // TRUE if anything changed. // @@ -347,7 +336,15 @@ frange::set (tree min, tree max, value_range_kind kind) bool frange::normalize_kind () { - if (m_kind == VR_RANGE) + // Undefined is viral. + if (m_props.nan_undefined_p ()) + { + set_undefined (); + return true; + } + if (m_kind == VR_RANGE + && real_isinf (&m_min, 1) + && real_isinf (&m_max, 0)) { // No FP properties set means varying. if (m_props.varying_p ()) @@ -355,14 +352,6 @@ frange::normalize_kind () set_varying (m_type); return true; } - // Undefined is viral. - if (m_props.nan_undefined_p () - || m_props.inf_undefined_p () - || m_props.ninf_undefined_p ()) - { - set_undefined (); - return true; - } } else if (m_kind == VR_VARYING) { @@ -370,12 +359,32 @@ frange::normalize_kind () if (!m_props.varying_p ()) { m_kind = VR_RANGE; + real_inf (&m_min, 1); + real_inf (&m_max, 0); return true; } } return false; } +// If both operands are definitely NAN, do nothing as they combine +// perfectly. If OTOH, only one is a NAN, set R to VARYING as they +// can't be neither unioned nor intersected. Return TRUE if we +// changed anything. + +static inline bool +early_nan_resolve (frange &r, const frange &other) +{ + gcc_checking_assert (r.get_nan ().yes_p () || other.get_nan ().yes_p ()); + + // There's nothing to do for both NANs. + if (r.get_nan ().yes_p () == other.get_nan ().yes_p ()) + return false; + // But only one NAN complicates things. + r.set_varying (r.type ()); + return true; +} + bool frange::union_ (const vrange &v) { @@ -388,13 +397,34 @@ frange::union_ (const vrange &v) *this = r; return true; } + // ?? We could do better here. [5,6] U NAN should be [5,6] with the + // NAN maybe bits set. For now, this is conservatively correct. + if (get_nan ().yes_p () || r.get_nan ().yes_p ()) + return early_nan_resolve (*this, r); - bool ret = m_props.union_ (r.m_props); - ret |= normalize_kind (); + bool changed = m_props.union_ (r.m_props); + + // Note: for the combination of zeros that differ in sign we keep + // the endpoints untouched. This means that for -0.0 U +0.0, the + // result will be -0.0. Ultimately this doesn't matter, because we + // keep singleton zeros ambiguous throughout to avoid propagating + // them. See frange::singleton_p(). + + if (real_less (&r.m_min, &m_min)) + { + m_min = r.m_min; + changed = true; + } + if (real_less (&m_max, &r.m_max)) + { + m_max = r.m_max; + changed = true; + } + changed |= normalize_kind (); if (flag_checking) verify_range (); - return ret; + return changed; } bool @@ -414,13 +444,38 @@ frange::intersect (const vrange &v) *this = r; return true; } + if (get_nan ().yes_p () || r.get_nan ().yes_p ()) + return early_nan_resolve (*this, r); + + bool changed = m_props.intersect (r.m_props); + + // Note: for the combination of zeros that differ in sign we keep + // the endpoints untouched. This means that for -0.0 ^ +0.0, the + // result will be -0.0. Ultimately this doesn't matter, because we + // keep singleton zeros ambiguous throughout to avoid propagating + // them. See frange::singleton_p(). - bool ret = m_props.intersect (r.m_props); - ret |= normalize_kind (); + if (real_less (&m_min, &r.m_min)) + { + m_min = r.m_min; + changed = true; + } + if (real_less (&r.m_max, &m_max)) + { + m_max = r.m_max; + changed = true; + } + // If the endpoints are swapped, the ranges are disjoint. + if (real_less (&m_max, &m_min)) + { + set_undefined (); + return true; + } + changed |= normalize_kind (); if (flag_checking) verify_range (); - return ret; + return changed; } frange & @@ -428,6 +483,8 @@ frange::operator= (const frange &src) { m_kind = src.m_kind; m_type = src.m_type; + m_min = src.m_min; + m_max = src.m_max; m_props = src.m_props; if (flag_checking) @@ -446,7 +503,59 @@ frange::operator== (const frange &src) const if (varying_p ()) return types_compatible_p (m_type, src.m_type); - return m_props == src.m_props; + if (m_props.get_nan ().yes_p () + || src.m_props.get_nan ().yes_p ()) + return false; + + return (real_identical (&m_min, &src.m_min) + && real_identical (&m_max, &src.m_max) + && m_props == src.m_props + && types_compatible_p (m_type, src.m_type)); + } + return false; +} + +// Return TRUE if range contains the TREE_REAL_CST_PTR in CST. + +bool +frange::contains_p (tree cst) const +{ + if (undefined_p ()) + return false; + + if (varying_p ()) + return true; + + gcc_checking_assert (m_kind == VR_RANGE); + + return (real_compare (GE_EXPR, TREE_REAL_CST_PTR (cst), &m_min) + && real_compare (LE_EXPR, TREE_REAL_CST_PTR (cst), &m_max)); +} + +// If range is a singleton, place it in RESULT and return TRUE. If +// RESULT is NULL, just return TRUE. +// +// A NAN can never be a singleton, and neither can a 0.0 if we're +// honoring signed zeros because we have no way of telling which zero +// it is. + +bool +frange::singleton_p (tree *result) const +{ + if (m_kind == VR_RANGE && real_identical (&m_min, &m_max)) + { + // If we're honoring signed zeros, fail because we don't know + // which zero we have. This avoids propagating the wrong zero. + if (HONOR_SIGNED_ZEROS (m_type) && zero_p ()) + return false; + + // Return false for any singleton that may be a NAN. + if (HONOR_NANS (m_type) && !get_nan ().no_p ()) + return false; + + if (result) + *result = build_real (m_type, m_min); + return true; } return false; } @@ -465,13 +574,82 @@ frange::verify_range () gcc_checking_assert (m_props.undefined_p ()); return; } + gcc_checking_assert (!m_props.undefined_p ()); + if (varying_p ()) { gcc_checking_assert (m_props.varying_p ()); return; } + + // We don't support the inverse of an frange (yet). gcc_checking_assert (m_kind == VR_RANGE); - gcc_checking_assert (!m_props.varying_p () && !m_props.undefined_p ()); + + bool is_nan = real_isnan (&m_min) || real_isnan (&m_max); + if (is_nan) + { + // If either is a NAN, both must be a NAN. + gcc_checking_assert (real_identical (&m_min, &m_max)); + gcc_checking_assert (get_nan ().yes_p ()); + } + else + // Make sure we don't have swapped ranges. + gcc_checking_assert (!real_less (&m_max, &m_min)); + + // If we're absolutely sure we have a NAN, the endpoints should + // reflect this, otherwise we'd have more than one way to represent + // a NAN. + if (m_props.get_nan ().yes_p ()) + { + gcc_checking_assert (real_isnan (&m_min)); + gcc_checking_assert (real_isnan (&m_max)); + } + + // If all the properties are clear, we better not span the entire + // domain, because that would make us varying. + if (m_props.varying_p ()) + gcc_checking_assert (!real_isinf (&m_min, 1) || !real_isinf (&m_max, 0)); +} + +// We can't do much with nonzeros yet. +void +frange::set_nonzero (tree type) +{ + set_varying (type); +} + +// We can't do much with nonzeros yet. +bool +frange::nonzero_p () const +{ + return false; +} + +// Set range to [+0.0, +0.0]. + +void +frange::set_zero (tree type) +{ + tree zero = build_zero_cst (type); + set (zero, zero); +} + +// Return TRUE for any [0.0, 0.0] regardless of sign. + +bool +frange::zero_p () const +{ + return (m_kind == VR_RANGE + && real_iszero (&m_min) + && real_iszero (&m_max)); +} + +void +frange::set_nonnegative (tree type) +{ + tree zero = build_zero_cst (type); + tree inf = vrp_val_max (type); + set (zero, inf); } // Here we copy between any two irange's. The ranges can be legacy or @@ -3304,6 +3482,199 @@ range_tests_nonzero_bits () ASSERT_TRUE (r0.varying_p ()); } +// Build an frange from string endpoints. + +static inline frange +frange_float (const char *lb, const char *ub, tree type = float_type_node) +{ + REAL_VALUE_TYPE min, max; + gcc_assert (real_from_string (&min, lb) == 0); + gcc_assert (real_from_string (&max, ub) == 0); + return frange (type, min, max); +} + +// Build a NAN of type TYPE. + +static inline frange +frange_nan (tree type = float_type_node) +{ + REAL_VALUE_TYPE r; + + gcc_assert (real_nan (&r, "", 1, TYPE_MODE (type))); + return frange (type, r, r); +} + +static void +range_tests_nan () +{ + frange r0, r1; + + // Equal ranges but with differing NAN bits are not equal. + r1 = frange_float ("10", "12"); + r0 = r1; + ASSERT_EQ (r0, r1); + r0.set_nan (fp_prop::NO); + ASSERT_NE (r0, r1); + r0.set_nan (fp_prop::YES); + ASSERT_NE (r0, r1); + r0.set_nan (fp_prop::VARYING); + ASSERT_EQ (r0, r1); + + // NAN ranges are not equal to each other. + r0 = frange_nan (); + r1 = r0; + ASSERT_FALSE (r0 == r1); + ASSERT_FALSE (r0 == r0); + ASSERT_TRUE (r0 != r0); + + // Make sure that combining NAN and INF doesn't give any crazy results. + r0 = frange_nan (); + ASSERT_TRUE (r0.get_nan ().yes_p ()); + r1 = frange_float ("+Inf", "+Inf"); + r0.union_ (r1); + // [INF, INF] U NAN = VARYING + ASSERT_TRUE (r0.varying_p ()); + + // [INF, INF] ^ NAN = VARYING + r0 = frange_nan (); + r1 = frange_float ("+Inf", "+Inf"); + r0.intersect (r1); + ASSERT_TRUE (r0.varying_p ()); + + // NAN ^ NAN = NAN + r0 = frange_nan (); + r1 = frange_nan (); + r0.intersect (r1); + ASSERT_TRUE (r0.get_nan ().yes_p ()); + + // VARYING ^ NAN = NAN. + r0 = frange_nan (); + r1.set_varying (float_type_node); + r0.intersect (r1); + ASSERT_TRUE (r0.get_nan ().yes_p ()); +} + +static void +range_tests_signed_zeros () +{ + tree zero = build_zero_cst (float_type_node); + tree neg_zero = fold_build1 (NEGATE_EXPR, float_type_node, zero); + frange r0, r1; + + // ?? If -0.0 == +0.0, then a range of [-0.0, -0.0] should + // contain +0.0 and vice versa. We probably need a property to + // track signed zeros in the frange like we do for NAN, to + // properly model all this. + r0 = frange (zero, zero); + r1 = frange (neg_zero, neg_zero); + ASSERT_TRUE (r0.contains_p (zero)); + ASSERT_TRUE (r0.contains_p (neg_zero)); + ASSERT_TRUE (r1.contains_p (zero)); + ASSERT_TRUE (r1.contains_p (neg_zero)); +} + +static void +range_tests_floats () +{ + frange r0, r1; + + range_tests_nan (); + + if (HONOR_SIGNED_ZEROS (float_type_node)) + range_tests_signed_zeros (); + + // A range of [-INF,+INF] is actually VARYING... + r0 = frange_float ("-Inf", "+Inf"); + ASSERT_TRUE (r0.varying_p ()); + // ...unless it has some special property... + r0.set_nan (fp_prop::NO); + ASSERT_FALSE (r0.varying_p ()); + + // The endpoints of a VARYING are +-INF. + REAL_VALUE_TYPE inf, ninf; + real_inf (&inf, 0); + real_inf (&ninf, 1); + r0.set_varying (float_type_node); + ASSERT_TRUE (real_identical (&r0.lower_bound (), &ninf)); + ASSERT_TRUE (real_identical (&r0.upper_bound (), &inf)); + + // The maximum representable range for a type is still a subset of VARYING. + REAL_VALUE_TYPE q, r; + real_min_representable (&q, float_type_node); + real_max_representable (&r, float_type_node); + r0 = frange (float_type_node, q, r); + // r0 is not a varying, because it does not include -INF/+INF. + ASSERT_FALSE (r0.varying_p ()); + // The upper bound of r0 must be less than +INF. + ASSERT_TRUE (real_less (&r0.upper_bound (), &inf)); + // The lower bound of r0 must be greater than -INF. + ASSERT_TRUE (real_less (&ninf, &r0.lower_bound ())); + + // For most architectures, where float and double are different + // sizes, having the same endpoints does not necessarily mean the + // ranges are equal. + if (!types_compatible_p (float_type_node, double_type_node)) + { + r0 = frange_float ("3.0", "3.0", float_type_node); + r1 = frange_float ("3.0", "3.0", double_type_node); + ASSERT_NE (r0, r1); + } + + // [3,5] U [10,12] = [3,12]. + r0 = frange_float ("3", "5"); + r1 = frange_float ("10", "12"); + r0.union_ (r1); + ASSERT_EQ (r0, frange_float ("3", "12")); + + // [5,10] U [4,8] = [4,10] + r0 = frange_float ("5", "10"); + r1 = frange_float ("4", "8"); + r0.union_ (r1); + ASSERT_EQ (r0, frange_float ("4", "10")); + + // [3,5] U [4,10] = [3,10] + r0 = frange_float ("3", "5"); + r1 = frange_float ("4", "10"); + r0.union_ (r1); + ASSERT_EQ (r0, frange_float ("3", "10")); + + // [4,10] U [5,11] = [4,11] + r0 = frange_float ("4", "10"); + r1 = frange_float ("5", "11"); + r0.union_ (r1); + ASSERT_EQ (r0, frange_float ("4", "11")); + + // [3,12] ^ [10,12] = [10,12]. + r0 = frange_float ("3", "12"); + r1 = frange_float ("10", "12"); + r0.intersect (r1); + ASSERT_EQ (r0, frange_float ("10", "12")); + + // [10,12] ^ [11,11] = [11,11] + r0 = frange_float ("10", "12"); + r1 = frange_float ("11", "11"); + r0.intersect (r1); + ASSERT_EQ (r0, frange_float ("11", "11")); + + // [10,20] ^ [5,15] = [10,15] + r0 = frange_float ("10", "20"); + r1 = frange_float ("5", "15"); + r0.intersect (r1); + ASSERT_EQ (r0, frange_float ("10", "15")); + + // [10,20] ^ [15,25] = [15,20] + r0 = frange_float ("10", "20"); + r1 = frange_float ("15", "25"); + r0.intersect (r1); + ASSERT_EQ (r0, frange_float ("15", "20")); + + // [10,20] ^ [21,25] = [] + r0 = frange_float ("10", "20"); + r1 = frange_float ("21", "25"); + r0.intersect (r1); + ASSERT_TRUE (r0.undefined_p ()); +} + void range_tests () { @@ -3312,6 +3683,7 @@ range_tests () range_tests_int_range_max (); range_tests_strict_enum (); range_tests_nonzero_bits (); + range_tests_floats (); range_tests_misc (); } |