diff options
Diffstat (limited to 'gcc/value-range.cc')
| -rw-r--r-- | gcc/value-range.cc | 258 |
1 files changed, 129 insertions, 129 deletions
diff --git a/gcc/value-range.cc b/gcc/value-range.cc index d34a262..f93a7e5 100644 --- a/gcc/value-range.cc +++ b/gcc/value-range.cc @@ -55,6 +55,93 @@ irange_bitmask::irange_bitmask (tree type, } } +// Return a range in R of TYPE for this bitmask which encompasses +// a set of valid values which are allowable for this bitmask/value +// combination. If false is returned, no range was set. + +bool +irange_bitmask::range_from_mask (irange &r, tree type) const +{ + if (unknown_p ()) + return false; + + gcc_checking_assert ((value () & mask ()) == 0); + unsigned popcount = wi::popcount (mask ()); + + // For 0, 1 or 2 bits set, create a range with only the allowed values. + if (popcount <= 2) + { + // VALUE is always a valid range. + r.set (type, value (), value ()); + // If there are bits in mask, (VALUE | MASK) is also valid. + if (popcount >= 1) + r.union_ (int_range<1> (type, value () | mask (), value () | mask ())); + // If there are 2 bits set, add the other 2 possible values. + if (popcount == 2) + { + // Extract the two 1-bit masks into lb and ub. + wide_int lb = mask () & -mask (); // Lowest set bit. + wide_int ub = mask () & (mask () - 1); // The other bit. + r.union_ (int_range<1> (type, value () | lb, value () | lb)); + r.union_ (int_range<1> (type, value () | ub, value () | ub)); + } + return true; + } + + // Otherwise, calculate the valid range allowed by the bitmask. + int prec = TYPE_PRECISION (type); + wide_int ub = mask () | value (); + wide_int sign_bit = wi::one (prec) << (prec - 1); + wide_int sign_mask = mask () & sign_bit; + wide_int sign_value = value () & sign_bit; + // Create a lower and upper bound. + // If unsigned, or the sign is known to be positive, create [lb, ub] + if (TYPE_SIGN (type) == UNSIGNED || (sign_mask == 0 && sign_value == 0)) + r.set (type, value (), mask () | value ()); + // If the sign bit is KNOWN to be 1, we have a completely negative range. + else if (sign_mask == 0 && sign_value != 0) + r.set (type, value (), value () | (mask () & ~sign_bit)); + else + { + // Otherwise there are 2 ranges, a negative and positive interval. + wide_int neg_base = value () | sign_bit; + wide_int pos_mask = mask () & ~sign_bit; + r.set (type, neg_base , neg_base | pos_mask); + r.union_ (int_range<1> (type, value (), value () | pos_mask)); + } + + // If the mask doesn't have a trailing zero, there is nothing else to filter. + int z = wi::ctz (mask ()); + if (z == 0) + return true; + + // Remove the [0, X] values which the trailing-zero mask rules out. + // For example, if z == 4, the mask is 0xFFF0, and the lowest 4 bits + // define the range [0, 15]. Only (value & low_mask) is allowed. + ub = (wi::one (prec) << z) - 1; // Upper bound of range. + int_range<4> mask_range (type, wi::zero (prec), ub); + // Remove the valid value from the excluded range and form an anti-range. + wide_int allow = value () & ub; + mask_range.intersect (int_range<2> (type, allow, allow, VR_ANTI_RANGE)); + mask_range.invert (); + r.intersect (mask_range); + + if (TYPE_SIGN (type) == SIGNED) + { + // For signed negative values, find the lowest value with trailing zeros. + // This forms a range such as [-512, -1] for z=9. + wide_int lb = -(wi::one (prec) << z); + int_range<4> mask_range (type, lb, wi::minus_one (prec)); + // Remove the one allowed value from that set. + wide_int allow = value () | lb; + mask_range.intersect (int_range<2> (type, allow, allow, VR_ANTI_RANGE)); + mask_range.invert (); + r.intersect (mask_range); + } + return true; +} + + void irange::accept (const vrange_visitor &v) const { @@ -2275,47 +2362,57 @@ irange::invert () // This routine will take the bounds [LB, UB], and apply the bitmask to those // values such that both bounds satisfy the bitmask. TRUE is returned // if either bound changes, and they are returned as [NEW_LB, NEW_UB]. -// if NEW_UB < NEW_LB, then the entire bound is to be removed as none of -// the values are valid. +// If there is an overflow, or if (NEW_UB < NEW_LB), then the entire bound is +// to be removed as none of the values are valid. This is indicated by +// teturning TRUE in OVF. False indicates the bounds are fine. // ie, [4, 14] MASK 0xFFFE VALUE 0x1 -// means all values must be odd, the new bounds returned will be [5, 13]. +// means all values must be odd, the new bounds returned will be [5, 13] with +// OVF set to FALSE. // ie, [4, 4] MASK 0xFFFE VALUE 0x1 -// would return [1, 0] and as the LB < UB, the entire subrange is invalid -// and should be removed. +// would return TRUE and OVF == TRUE. The entire subrange should be removed. bool irange::snap (const wide_int &lb, const wide_int &ub, - wide_int &new_lb, wide_int &new_ub) + wide_int &new_lb, wide_int &new_ub, bool &ovf) { + ovf = false; int z = wi::ctz (m_bitmask.mask ()); if (z == 0) return false; + // Shortcircuit check for values that are already good. + if ((((lb ^ m_bitmask.value ()) | (ub ^ m_bitmask.value ())) + & ~m_bitmask.mask ()) == 0) + return false; + const wide_int step = (wi::one (TYPE_PRECISION (type ())) << z); const wide_int match_mask = step - 1; const wide_int value = m_bitmask.value () & match_mask; - bool ovf = false; - wide_int rem_lb = lb & match_mask; wide_int offset = (value - rem_lb) & match_mask; new_lb = lb + offset; // Check for overflows at +INF if (wi::lt_p (new_lb, lb, TYPE_SIGN (type ()))) - ovf = true; + { + ovf = true; + return true; + } wide_int rem_ub = ub & match_mask; wide_int offset_ub = (rem_ub - value) & match_mask; new_ub = ub - offset_ub; // Check for underflows at -INF if (wi::gt_p (new_ub, ub, TYPE_SIGN (type ()))) - ovf = true; + { + ovf = true; + return true; + } - // Overflow or inverted range = invalid - if (ovf || wi::lt_p (new_ub, new_lb, TYPE_SIGN (type ()))) + // If inverted range is invalid, set overflow to TRUE. + if (wi::lt_p (new_ub, new_lb, TYPE_SIGN (type ()))) { - new_lb = wi::one (lb.get_precision ()); - new_ub = wi::zero (ub.get_precision ()); + ovf = true; return true; } return (new_lb != lb) || (new_ub != ub); @@ -2334,11 +2431,12 @@ irange::snap_subranges () wide_int lb, ub; for (x = 0; x < m_num_ranges; x++) { - if (snap (lower_bound (x), upper_bound (x), lb, ub)) + bool ovf; + if (snap (lower_bound (x), upper_bound (x), lb, ub, ovf)) { changed = true; - // This subrange is to be completely removed. - if (wi::lt_p (ub, lb, TYPE_SIGN (type ()))) + // Check if this subrange is to be completely removed. + if (ovf) { int_range<1> tmp (type (), lower_bound (x), upper_bound (x)); invalid.union_ (tmp); @@ -2359,109 +2457,25 @@ irange::snap_subranges () return changed; } -// If the mask can be trivially converted to a range, do so. -// Otherwise attempt to remove the lower bits from the range. -// Return true if the range changed in any way. +// If the bitmask has a range representation, intersect this range with +// the bitmasks range. Then ensure all enpoints match the bitmask. +// Return TRUE if the range changes at all. bool irange::set_range_from_bitmask () { gcc_checking_assert (!undefined_p ()); - if (m_bitmask.unknown_p ()) - return false; - - // If all the bits are known, this is a singleton. - if (m_bitmask.mask () == 0) - { - // Make sure the singleton is within the range. - if (contains_p (m_bitmask.value ())) - set (m_type, m_bitmask.value (), m_bitmask.value ()); - else - set_undefined (); - return true; - } - - unsigned popcount = wi::popcount (m_bitmask.get_nonzero_bits ()); - - // If we have only one bit set in the mask, we can figure out the - // range immediately. - if (popcount == 1) - { - // Make sure we don't pessimize the range. - if (!contains_p (m_bitmask.get_nonzero_bits ())) - return false; - - bool has_zero = contains_zero_p (*this); - wide_int nz = m_bitmask.get_nonzero_bits (); - set (m_type, nz, nz); - m_bitmask.set_nonzero_bits (nz); - if (has_zero) - { - int_range<2> zero; - zero.set_zero (m_type); - union_ (zero); - } - if (flag_checking) - verify_range (); - return true; - } - else if (popcount == 0) - { - set_zero (m_type); - return true; - } + // Snap subranmges when bitmask is first set. + snap_subranges (); + if (undefined_p ()) + return true; - // If the mask doesn't have a trailing zero, theres nothing to filter. - int z = wi::ctz (m_bitmask.mask ()); - if (!z) + // Calculate the set of ranges valid for the bitmask. + int_range_max allow; + if (!m_bitmask.range_from_mask (allow, m_type)) return false; - - int prec = TYPE_PRECISION (m_type); - wide_int value = m_bitmask.value (); - wide_int mask = m_bitmask.mask (); - - // Remove the [0, X] values which the trailing-zero mask rules out. - // For example, if z == 4, the mask is 0xFFF0, and the lowest 4 bits - // define the range [0, 15]. Only one of which (value & low_mask) is allowed. - wide_int ub = (wi::one (prec) << z) - 1; // Upper bound of affected range. - int_range_max mask_range (m_type, wi::zero (prec), ub); - - // Remove the one valid value from the excluded range and form an anti-range. - wide_int allow = value & ub; - mask_range.intersect (int_range<2> (m_type, allow, allow, VR_ANTI_RANGE)); - - // Invert it to get the allowed values and intersect it with the main range. - mask_range.invert (); - bool changed = intersect (mask_range); - - // Now handle the rest of the domain — the upper side for positive values, - // or [-X, -1] for signed negatives. - // Compute the maximum value representable under the mask/value constraint. - ub = mask | value; - - // If value is non-negative, adjust the upper limit to remove values above - // UB that conflict with known fixed bits. - if (TYPE_SIGN (m_type) == UNSIGNED || wi::clz (ub) > 0) - mask_range = int_range<1> (m_type, wi::zero (prec), ub); - else - { - // For signed negative values, find the lowest value with trailing zeros. - // This forms a range such as [-512, -1] for z=9. - wide_int lb = -(wi::one (prec) << z); - mask_range = int_range<2> (m_type, lb, wi::minus_one (prec)); - - // Remove the one allowed value from that set. - allow = value | lb; - mask_range.intersect (int_range<2> (m_type, allow, allow, VR_ANTI_RANGE)); - mask_range.invert (); - } - - // Make sure we call intersect, so do it first. - changed = intersect (mask_range) | changed; - // Now make sure each subrange endpoint matches the bitmask. - changed |= snap_subranges (); - - return changed; + // And intersect that set of ranges with the current set. + return intersect (allow); } void @@ -2932,7 +2946,7 @@ test_irange_snap_bounds () tree u1 = build_nonstandard_integer_type (1, /*unsigned=*/ 1); // Basic aligned range: even-only - assert_snap_result (5, 15, 6, 14, 0xFFFFFFFE, 0x0, u32); + assert_snap_result (5, 15, 6, 14, 0xE, 0x0, u32); // Singleton that doesn't match mask: undefined. assert_snap_result (7, 7, 1, 0, 0xFFFFFFFE, 0x0, u32); // 8-bit signed char, mask 0xF0 (i.e. step of 16). @@ -3204,15 +3218,12 @@ range_tests_misc () static void range_tests_nonzero_bits () { - int_range<2> r0, r1; + int_range<8> r0, r1; // Adding nonzero bits to a varying drops the varying. r0.set_varying (integer_type_node); r0.set_nonzero_bits (INT (255)); ASSERT_TRUE (!r0.varying_p ()); - // Dropping the nonzero bits brings us back to varying. - r0.set_nonzero_bits (INT (-1)); - ASSERT_TRUE (r0.varying_p ()); // Test contains_p with nonzero bits. r0.set_zero (integer_type_node); @@ -3244,17 +3255,6 @@ range_tests_nonzero_bits () r0.intersect (r1); ASSERT_TRUE (r0.get_nonzero_bits () == 0xff); - // The union of a mask of 0xff..ffff00 with a mask of 0xff spans the - // entire domain, and makes the range a varying. - r0.set_varying (integer_type_node); - wide_int x = wi::shwi (0xff, TYPE_PRECISION (integer_type_node)); - x = wi::bit_not (x); - r0.set_nonzero_bits (x); // 0xff..ff00 - r1.set_varying (integer_type_node); - r1.set_nonzero_bits (INT (0xff)); - r0.union_ (r1); - ASSERT_TRUE (r0.varying_p ()); - // Test that setting a nonzero bit of 1 does not pessimize the range. r0.set_zero (integer_type_node); r0.set_nonzero_bits (INT (1)); |