diff options
| -rw-r--r-- | gcc/ChangeLog | 8 | ||||
| -rw-r--r-- | gcc/Makefile.in | 1 | ||||
| -rw-r--r-- | gcc/tree-vrp.c | 611 | ||||
| -rw-r--r-- | gcc/tree-vrp.h | 77 | ||||
| -rw-r--r-- | gcc/wide-int-range.cc | 607 | ||||
| -rw-r--r-- | gcc/wide-int-range.h | 115 |
6 files changed, 737 insertions, 682 deletions
diff --git a/gcc/ChangeLog b/gcc/ChangeLog index 8d2814b19b3..08e2d79aa69 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,11 @@ +2018-08-03 Aldy Hernandez <aldyh@redhat.com> + + * Makefile.in (wide-int-range.o): New. + * tree-vrp.c: Move all the wide_int_* functions to... + * wide-int-range.cc: ...here. + * tree-vrp.h: Move all the wide_int_* prototypes to... + * wide-int-range.h: ...here. + 2018-08-03 Tom de Vries <tdevries@suse.de> * common/config/nvptx/nvptx-common.c (nvptx_except_unwind_info): Return diff --git a/gcc/Makefile.in b/gcc/Makefile.in index b8716406533..e7d818d174c 100644 --- a/gcc/Makefile.in +++ b/gcc/Makefile.in @@ -1601,6 +1601,7 @@ OBJS = \ web.o \ wide-int.o \ wide-int-print.o \ + wide-int-range.o \ xcoffout.o \ $(out_object_file) \ $(EXTRA_OBJS) \ diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c index d18c72d0a02..e1875d8d46e 100644 --- a/gcc/tree-vrp.c +++ b/gcc/tree-vrp.c @@ -67,6 +67,7 @@ along with GCC; see the file COPYING3. If not see #include "attribs.h" #include "vr-values.h" #include "builtins.h" +#include "wide-int-range.h" /* Set of SSA names found live during the RPO traversal of the function for still active basic-blocks. */ @@ -956,98 +957,7 @@ value_range_constant_singleton (value_range *vr) return NULL_TREE; } -/* Wrapper around wide_int_binop that adjusts for overflow. - - Return true if we can compute the result; i.e. if the operation - doesn't overflow or if the overflow is undefined. In the latter - case (if the operation overflows and overflow is undefined), then - adjust the result to be -INF or +INF depending on CODE, VAL1 and - VAL2. Return the value in *RES. - - Return false for division by zero, for which the result is - indeterminate. */ - -static bool -wide_int_binop_overflow (wide_int &res, - enum tree_code code, - const wide_int &w0, const wide_int &w1, - signop sign, bool overflow_undefined) -{ - wi::overflow_type overflow; - if (!wide_int_binop (res, code, w0, w1, sign, &overflow)) - return false; - - /* If the operation overflowed return -INF or +INF depending on the - operation and the combination of signs of the operands. */ - if (overflow && overflow_undefined) - { - switch (code) - { - case MULT_EXPR: - /* For multiplication, the sign of the overflow is given - by the comparison of the signs of the operands. */ - if (sign == UNSIGNED || w0.sign_mask () == w1.sign_mask ()) - res = wi::max_value (w0.get_precision (), sign); - else - res = wi::min_value (w0.get_precision (), sign); - return true; - - case TRUNC_DIV_EXPR: - case FLOOR_DIV_EXPR: - case CEIL_DIV_EXPR: - case EXACT_DIV_EXPR: - case ROUND_DIV_EXPR: - /* For division, the only case is -INF / -1 = +INF. */ - res = wi::max_value (w0.get_precision (), sign); - return true; - - default: - gcc_unreachable (); - } - } - return !overflow; -} - -/* For range [LB, UB] compute two wide_int bit masks. - - In the MAY_BE_NONZERO bit mask, if some bit is unset, it means that - for all numbers in the range the bit is 0, otherwise it might be 0 - or 1. - - In the MUST_BE_NONZERO bit mask, if some bit is set, it means that - for all numbers in the range the bit is 1, otherwise it might be 0 - or 1. */ - -void -wide_int_set_zero_nonzero_bits (signop sign, - const wide_int &lb, const wide_int &ub, - wide_int &may_be_nonzero, - wide_int &must_be_nonzero) -{ - may_be_nonzero = wi::minus_one (lb.get_precision ()); - must_be_nonzero = wi::zero (lb.get_precision ()); - - if (wi::eq_p (lb, ub)) - { - may_be_nonzero = lb; - must_be_nonzero = may_be_nonzero; - } - else if (wi::ge_p (lb, 0, sign) || wi::lt_p (ub, 0, sign)) - { - wide_int xor_mask = lb ^ ub; - may_be_nonzero = lb | ub; - must_be_nonzero = lb & ub; - if (xor_mask != 0) - { - wide_int mask = wi::mask (wi::floor_log2 (xor_mask), false, - may_be_nonzero.get_precision ()); - may_be_nonzero = may_be_nonzero | mask; - must_be_nonzero = wi::bit_and_not (must_be_nonzero, mask); - } - } -} - -/* Value range wrapper for wide_int_set_zero_nonzero_bits. +/* Value range wrapper for wide_int_range_set_zero_nonzero_bits. Compute MAY_BE_NONZERO and MUST_BE_NONZERO bit masks for range in VR. @@ -1066,9 +976,10 @@ vrp_set_zero_nonzero_bits (const tree expr_type, *must_be_nonzero = wi::zero (TYPE_PRECISION (expr_type)); return false; } - wide_int_set_zero_nonzero_bits (TYPE_SIGN (expr_type), - wi::to_wide (vr->min), wi::to_wide (vr->max), - *may_be_nonzero, *must_be_nonzero); + wide_int_range_set_zero_nonzero_bits (TYPE_SIGN (expr_type), + wi::to_wide (vr->min), + wi::to_wide (vr->max), + *may_be_nonzero, *must_be_nonzero); return true; } @@ -1114,516 +1025,6 @@ ranges_from_anti_range (value_range *ar, return vr0->type != VR_UNDEFINED; } -/* Order 2 sets of wide int ranges (w0/w1, w2/w3) and set MIN/MAX - accordingly. */ - -static void -wide_int_range_min_max (wide_int &min, wide_int &max, - wide_int &w0, wide_int &w1, wide_int &w2, wide_int &w3, - signop sign) -{ - /* Order pairs w0,w1 and w2,w3. */ - if (wi::gt_p (w0, w1, sign)) - std::swap (w0, w1); - if (wi::gt_p (w2, w3, sign)) - std::swap (w2, w3); - - /* Choose min and max from the ordered pairs. */ - min = wi::min (w0, w2, sign); - max = wi::max (w1, w3, sign); -} - -/* Calculate the cross product of two sets of ranges (VR0 and VR1) and - store the result in [RES_LB, RES_UB]. - - CODE is the operation to perform with sign SIGN. - - OVERFLOW_UNDEFINED is set if overflow is undefined for the operation type. - - Return TRUE if we were able to calculate the cross product. */ - -bool -wide_int_range_cross_product (wide_int &res_lb, wide_int &res_ub, - enum tree_code code, signop sign, - const wide_int &vr0_lb, const wide_int &vr0_ub, - const wide_int &vr1_lb, const wide_int &vr1_ub, - bool overflow_undefined) -{ - wide_int cp1, cp2, cp3, cp4; - - /* Compute the 4 cross operations, bailing if we get an overflow we - can't handle. */ - - if (!wide_int_binop_overflow (cp1, code, vr0_lb, vr1_lb, sign, - overflow_undefined)) - return false; - - if (wi::eq_p (vr0_lb, vr0_ub)) - cp3 = cp1; - else if (!wide_int_binop_overflow (cp3, code, vr0_ub, vr1_lb, sign, - overflow_undefined)) - return false; - - if (wi::eq_p (vr1_lb, vr1_ub)) - cp2 = cp1; - else if (!wide_int_binop_overflow (cp2, code, vr0_lb, vr1_ub, sign, - overflow_undefined)) - return false; - - if (wi::eq_p (vr0_lb, vr0_ub)) - cp4 = cp2; - else if (!wide_int_binop_overflow (cp4, code, vr0_ub, vr1_ub, sign, - overflow_undefined)) - return false; - - wide_int_range_min_max (res_lb, res_ub, cp1, cp2, cp3, cp4, sign); - return true; -} - -/* Multiply two ranges when TYPE_OVERFLOW_WRAPS: - - [RES_LB, RES_UB] = [MIN0, MAX0] * [MIN1, MAX1] - - This is basically fancy code so we don't drop to varying with an - unsigned [-3,-1]*[-3,-1]. - - Return TRUE if we were able to perform the operation. */ - -bool -wide_int_range_mult_wrapping (wide_int &res_lb, - wide_int &res_ub, - signop sign, - unsigned prec, - const wide_int &min0_, - const wide_int &max0_, - const wide_int &min1_, - const wide_int &max1_) -{ - /* This test requires 2*prec bits if both operands are signed and - 2*prec + 2 bits if either is not. Therefore, extend the values - using the sign of the result to PREC2. From here on out, - everthing is just signed math no matter what the input types - were. */ - widest2_int min0 = widest2_int::from (min0_, sign); - widest2_int max0 = widest2_int::from (max0_, sign); - widest2_int min1 = widest2_int::from (min1_, sign); - widest2_int max1 = widest2_int::from (max1_, sign); - widest2_int sizem1 = wi::mask <widest2_int> (prec, false); - widest2_int size = sizem1 + 1; - - /* Canonicalize the intervals. */ - if (sign == UNSIGNED) - { - if (wi::ltu_p (size, min0 + max0)) - { - min0 -= size; - max0 -= size; - } - - if (wi::ltu_p (size, min1 + max1)) - { - min1 -= size; - max1 -= size; - } - } - - widest2_int prod0 = min0 * min1; - widest2_int prod1 = min0 * max1; - widest2_int prod2 = max0 * min1; - widest2_int prod3 = max0 * max1; - - /* Sort the 4 products so that min is in prod0 and max is in - prod3. */ - /* min0min1 > max0max1 */ - if (prod0 > prod3) - std::swap (prod0, prod3); - - /* min0max1 > max0min1 */ - if (prod1 > prod2) - std::swap (prod1, prod2); - - if (prod0 > prod1) - std::swap (prod0, prod1); - - if (prod2 > prod3) - std::swap (prod2, prod3); - - /* diff = max - min. */ - prod2 = prod3 - prod0; - if (wi::geu_p (prod2, sizem1)) - /* The range covers all values. */ - return false; - - res_lb = wide_int::from (prod0, prec, sign); - res_ub = wide_int::from (prod3, prec, sign); - return true; -} - -/* Perform multiplicative operation CODE on two ranges: - - [RES_LB, RES_UB] = [VR0_LB, VR0_UB] .CODE. [VR1_LB, VR1_LB] - - Return TRUE if we were able to perform the operation. - - NOTE: If code is MULT_EXPR and TYPE_OVERFLOW_WRAPS, the resulting - range must be canonicalized by the caller because its components - may be swapped. */ - -bool -wide_int_range_multiplicative_op (wide_int &res_lb, wide_int &res_ub, - enum tree_code code, - signop sign, - unsigned prec, - const wide_int &vr0_lb, - const wide_int &vr0_ub, - const wide_int &vr1_lb, - const wide_int &vr1_ub, - bool overflow_undefined, - bool overflow_wraps) -{ - /* Multiplications, divisions and shifts are a bit tricky to handle, - depending on the mix of signs we have in the two ranges, we - need to operate on different values to get the minimum and - maximum values for the new range. One approach is to figure - out all the variations of range combinations and do the - operations. - - However, this involves several calls to compare_values and it - is pretty convoluted. It's simpler to do the 4 operations - (MIN0 OP MIN1, MIN0 OP MAX1, MAX0 OP MIN1 and MAX0 OP MAX0 OP - MAX1) and then figure the smallest and largest values to form - the new range. */ - if (code == MULT_EXPR && overflow_wraps) - return wide_int_range_mult_wrapping (res_lb, res_ub, - sign, prec, - vr0_lb, vr0_ub, vr1_lb, vr1_ub); - return wide_int_range_cross_product (res_lb, res_ub, - code, sign, - vr0_lb, vr0_ub, vr1_lb, vr1_ub, - overflow_undefined); -} - -/* Perform a left shift operation on two ranges: - - [RES_LB, RES_UB] = [VR0_LB, VR0_UB] << [VR1_LB, VR1_LB] - - Return TRUE if we were able to perform the operation. - - NOTE: The resulting range must be canonicalized by the caller - because its contents components may be swapped. */ - -bool -wide_int_range_lshift (wide_int &res_lb, wide_int &res_ub, - signop sign, unsigned prec, - const wide_int &vr0_lb, const wide_int &vr0_ub, - const wide_int &vr1_lb, const wide_int &vr1_ub, - bool overflow_undefined, bool overflow_wraps) -{ - /* Transform left shifts by constants into multiplies. */ - if (wi::eq_p (vr1_lb, vr1_ub)) - { - int shift = wi::extract_uhwi (vr1_ub, 0, vr1_ub.get_precision ()); - wide_int tmp = wi::set_bit_in_zero (shift, prec); - return wide_int_range_multiplicative_op (res_lb, res_ub, - MULT_EXPR, sign, prec, - vr0_lb, vr0_ub, tmp, tmp, - overflow_undefined, - /*overflow_wraps=*/true); - } - - int overflow_pos = prec; - if (sign == SIGNED) - overflow_pos -= 1; - int bound_shift = overflow_pos - vr1_ub.to_shwi (); - /* If bound_shift == HOST_BITS_PER_WIDE_INT, the llshift can - overflow. However, for that to happen, vr1.max needs to be - zero, which means vr1 is a singleton range of zero, which - means it should be handled by the previous LSHIFT_EXPR - if-clause. */ - wide_int bound = wi::set_bit_in_zero (bound_shift, prec); - wide_int complement = ~(bound - 1); - wide_int low_bound, high_bound; - bool in_bounds = false; - if (sign == UNSIGNED) - { - low_bound = bound; - high_bound = complement; - if (wi::ltu_p (vr0_ub, low_bound)) - { - /* [5, 6] << [1, 2] == [10, 24]. */ - /* We're shifting out only zeroes, the value increases - monotonically. */ - in_bounds = true; - } - else if (wi::ltu_p (high_bound, vr0_lb)) - { - /* [0xffffff00, 0xffffffff] << [1, 2] - == [0xfffffc00, 0xfffffffe]. */ - /* We're shifting out only ones, the value decreases - monotonically. */ - in_bounds = true; - } - } - else - { - /* [-1, 1] << [1, 2] == [-4, 4]. */ - low_bound = complement; - high_bound = bound; - if (wi::lts_p (vr0_ub, high_bound) - && wi::lts_p (low_bound, vr0_lb)) - { - /* For non-negative numbers, we're shifting out only - zeroes, the value increases monotonically. - For negative numbers, we're shifting out only ones, the - value decreases monotomically. */ - in_bounds = true; - } - } - if (in_bounds) - return wide_int_range_multiplicative_op (res_lb, res_ub, - LSHIFT_EXPR, sign, prec, - vr0_lb, vr0_ub, - vr1_lb, vr1_ub, - overflow_undefined, - overflow_wraps); - return false; -} - -/* Return TRUE if a bit operation on two ranges can be easily - optimized in terms of a mask. - - Basically, for BIT_AND_EXPR or BIT_IOR_EXPR see if we can optimize: - - [LB, UB] op Z - into: - [LB op Z, UB op Z] - - It is up to the caller to perform the actual folding above. */ - -bool -wide_int_range_can_optimize_bit_op (tree_code code, - const wide_int &lb, const wide_int &ub, - const wide_int &mask) - -{ - if (code != BIT_AND_EXPR && code != BIT_IOR_EXPR) - return false; - /* If Z is a constant which (for op | its bitwise not) has n - consecutive least significant bits cleared followed by m 1 - consecutive bits set immediately above it and either - m + n == precision, or (x >> (m + n)) == (y >> (m + n)). - - The least significant n bits of all the values in the range are - cleared or set, the m bits above it are preserved and any bits - above these are required to be the same for all values in the - range. */ - - wide_int w = mask; - int m = 0, n = 0; - if (code == BIT_IOR_EXPR) - w = ~w; - if (wi::eq_p (w, 0)) - n = w.get_precision (); - else - { - n = wi::ctz (w); - w = ~(w | wi::mask (n, false, w.get_precision ())); - if (wi::eq_p (w, 0)) - m = w.get_precision () - n; - else - m = wi::ctz (w) - n; - } - wide_int new_mask = wi::mask (m + n, true, w.get_precision ()); - if ((new_mask & lb) == (new_mask & ub)) - return true; - - return false; -} - -/* Return TRUE if shifting by range [MIN, MAX] is undefined behavior. - - FIXME: Make this inline when it moves outside of tree-vrp. */ - -bool -wide_int_range_shift_undefined_p (signop sign, unsigned prec, - const wide_int &min, const wide_int &max) -{ - /* ?? Note: The original comment said this only applied to - RSHIFT_EXPR, but it was being applied to both left and right - shifts. Is this OK? */ - - /* Shifting by any values outside [0..prec-1], gets undefined - behavior from the shift operation. We cannot even trust - SHIFT_COUNT_TRUNCATED at this stage, because that applies to rtl - shifts, and the operation at the tree level may be widened. */ - return wi::lt_p (min, 0, sign) || wi::ge_p (max, prec, sign); -} - -/* Calculate the XOR of two ranges and store the result in [WMIN,WMAX]. - The two input ranges are described by their MUST_BE_NONZERO and - MAY_BE_NONZERO bit masks. - - Return TRUE if we were able to successfully calculate the new range. */ - -bool -wide_int_range_bit_xor (wide_int &wmin, wide_int &wmax, - signop sign, - unsigned prec, - const wide_int &must_be_nonzero0, - const wide_int &may_be_nonzero0, - const wide_int &must_be_nonzero1, - const wide_int &may_be_nonzero1) -{ - wide_int result_zero_bits = ((must_be_nonzero0 & must_be_nonzero1) - | ~(may_be_nonzero0 | may_be_nonzero1)); - wide_int result_one_bits - = (wi::bit_and_not (must_be_nonzero0, may_be_nonzero1) - | wi::bit_and_not (must_be_nonzero1, may_be_nonzero0)); - wmax = ~result_zero_bits; - wmin = result_one_bits; - /* If the range has all positive or all negative values, the result - is better than VARYING. */ - if (wi::lt_p (wmin, 0, sign) || wi::ge_p (wmax, 0, sign)) - return true; - wmin = wi::min_value (prec, sign); - wmax = wi::max_value (prec, sign); - return false; -} - -/* Calculate the IOR of two ranges and store the result in [WMIN,WMAX]. - Return TRUE if we were able to successfully calculate the new range. */ - -bool -wide_int_range_bit_ior (wide_int &wmin, wide_int &wmax, - signop sign, - const wide_int &vr0_min, - const wide_int &vr0_max, - const wide_int &vr1_min, - const wide_int &vr1_max, - const wide_int &must_be_nonzero0, - const wide_int &may_be_nonzero0, - const wide_int &must_be_nonzero1, - const wide_int &may_be_nonzero1) -{ - wmin = must_be_nonzero0 | must_be_nonzero1; - wmax = may_be_nonzero0 | may_be_nonzero1; - /* If the input ranges contain only positive values we can - truncate the minimum of the result range to the maximum - of the input range minima. */ - if (wi::ge_p (vr0_min, 0, sign) - && wi::ge_p (vr1_min, 0, sign)) - { - wmin = wi::max (wmin, vr0_min, sign); - wmin = wi::max (wmin, vr1_min, sign); - } - /* If either input range contains only negative values - we can truncate the minimum of the result range to the - respective minimum range. */ - if (wi::lt_p (vr0_max, 0, sign)) - wmin = wi::max (wmin, vr0_min, sign); - if (wi::lt_p (vr1_max, 0, sign)) - wmin = wi::max (wmin, vr1_min, sign); - /* If the limits got swapped around, indicate error so we can adjust - the range to VARYING. */ - if (wi::gt_p (wmin, wmax,sign)) - return false; - return true; -} - -/* Calculate the bitwise AND of two ranges and store the result in [WMIN,WMAX]. - Return TRUE if we were able to successfully calculate the new range. */ - -bool -wide_int_range_bit_and (wide_int &wmin, wide_int &wmax, - signop sign, - unsigned prec, - const wide_int &vr0_min, - const wide_int &vr0_max, - const wide_int &vr1_min, - const wide_int &vr1_max, - const wide_int &must_be_nonzero0, - const wide_int &may_be_nonzero0, - const wide_int &must_be_nonzero1, - const wide_int &may_be_nonzero1) -{ - wmin = must_be_nonzero0 & must_be_nonzero1; - wmax = may_be_nonzero0 & may_be_nonzero1; - /* If both input ranges contain only negative values we can - truncate the result range maximum to the minimum of the - input range maxima. */ - if (wi::lt_p (vr0_max, 0, sign) && wi::lt_p (vr1_max, 0, sign)) - { - wmax = wi::min (wmax, vr0_max, sign); - wmax = wi::min (wmax, vr1_max, sign); - } - /* If either input range contains only non-negative values - we can truncate the result range maximum to the respective - maximum of the input range. */ - if (wi::ge_p (vr0_min, 0, sign)) - wmax = wi::min (wmax, vr0_max, sign); - if (wi::ge_p (vr1_min, 0, sign)) - wmax = wi::min (wmax, vr1_max, sign); - /* PR68217: In case of signed & sign-bit-CST should - result in [-INF, 0] instead of [-INF, INF]. */ - if (wi::gt_p (wmin, wmax, sign)) - { - wide_int sign_bit = wi::set_bit_in_zero (prec - 1, prec); - if (sign == SIGNED - && ((wi::eq_p (vr0_min, vr0_max) - && !wi::cmps (vr0_min, sign_bit)) - || (wi::eq_p (vr1_min, vr1_max) - && !wi::cmps (vr1_min, sign_bit)))) - { - wmin = wi::min_value (prec, sign); - wmax = wi::zero (prec); - } - } - /* If the limits got swapped around, indicate error so we can adjust - the range to VARYING. */ - if (wi::gt_p (wmin, wmax,sign)) - return false; - return true; -} - -/* Calculate TRUNC_MOD_EXPR on two ranges and store the result in - [WMIN,WMAX]. */ - -void -wide_int_range_trunc_mod (wide_int &wmin, wide_int &wmax, - signop sign, - unsigned prec, - const wide_int &vr0_min, - const wide_int &vr0_max, - const wide_int &vr1_min, - const wide_int &vr1_max) -{ - wide_int tmp; - - /* ABS (A % B) < ABS (B) and either - 0 <= A % B <= A or A <= A % B <= 0. */ - wmax = vr1_max - 1; - if (sign == SIGNED) - { - tmp = -1 - vr1_min; - wmax = wi::smax (wmax, tmp); - } - - if (sign == UNSIGNED) - wmin = wi::zero (prec); - else - { - wmin = -wmax; - tmp = vr0_min; - if (wi::gts_p (tmp, 0)) - tmp = wi::zero (prec); - wmin = wi::smax (wmin, tmp); - } - tmp = vr0_max; - if (sign == SIGNED && wi::neg_p (tmp)) - tmp = wi::zero (prec); - wmax = wi::min (wmax, tmp, sign); -} - /* Extract the components of a value range into a pair of wide ints in [WMIN, WMAX]. diff --git a/gcc/tree-vrp.h b/gcc/tree-vrp.h index 8cac7daada7..0c1fb3637cf 100644 --- a/gcc/tree-vrp.h +++ b/gcc/tree-vrp.h @@ -105,83 +105,6 @@ extern bool vrp_val_is_min (const_tree); extern bool vrp_val_is_max (const_tree); extern void copy_value_range (value_range *, value_range *); extern void set_value_range_to_value (value_range *, tree, bitmap); -extern bool wide_int_range_cross_product (wide_int &res_lb, wide_int &res_ub, - enum tree_code code, signop sign, - const wide_int &, const wide_int &, - const wide_int &, const wide_int &, - bool overflow_undefined); -extern bool wide_int_range_mult_wrapping (wide_int &res_lb, - wide_int &res_ub, - signop sign, - unsigned prec, - const wide_int &min0_, - const wide_int &max0_, - const wide_int &min1_, - const wide_int &max1_); -extern bool wide_int_range_multiplicative_op (wide_int &res_lb, - wide_int &res_ub, - enum tree_code code, - signop sign, - unsigned prec, - const wide_int &vr0_lb, - const wide_int &vr0_ub, - const wide_int &vr1_lb, - const wide_int &vr1_ub, - bool overflow_undefined, - bool overflow_wraps); -extern bool wide_int_range_lshift (wide_int &res_lb, wide_int &res_ub, - signop sign, unsigned prec, - const wide_int &, const wide_int &, - const wide_int &, const wide_int &, - bool overflow_undefined, - bool overflow_wraps); -extern bool wide_int_range_shift_undefined_p (signop sign, unsigned prec, - const wide_int &min, - const wide_int &max); -extern void wide_int_set_zero_nonzero_bits (signop, - const wide_int &lb, - const wide_int &ub, - wide_int &may_be_nonzero, - wide_int &must_be_nonzero); -extern bool wide_int_range_can_optimize_bit_op (tree_code, - const wide_int &lb, - const wide_int &ub, - const wide_int &mask); -extern bool wide_int_range_bit_xor (wide_int &wmin, wide_int &wmax, - signop sign, - unsigned prec, - const wide_int &must_be_nonzero0, - const wide_int &may_be_nonzero0, - const wide_int &must_be_nonzero1, - const wide_int &may_be_nonzero1); -extern bool wide_int_range_bit_ior (wide_int &wmin, wide_int &wmax, - signop sign, - const wide_int &vr0_min, - const wide_int &vr0_max, - const wide_int &vr1_min, - const wide_int &vr1_max, - const wide_int &must_be_nonzero0, - const wide_int &may_be_nonzero0, - const wide_int &must_be_nonzero1, - const wide_int &may_be_nonzero1); -extern bool wide_int_range_bit_and (wide_int &wmin, wide_int &wmax, - signop sign, - unsigned prec, - const wide_int &vr0_min, - const wide_int &vr0_max, - const wide_int &vr1_min, - const wide_int &vr1_max, - const wide_int &must_be_nonzero0, - const wide_int &may_be_nonzero0, - const wide_int &must_be_nonzero1, - const wide_int &may_be_nonzero1); -extern void wide_int_range_trunc_mod (wide_int &wmin, wide_int &wmax, - signop sign, - unsigned prec, - const wide_int &vr0_min, - const wide_int &vr0_max, - const wide_int &vr1_min, - const wide_int &vr1_max); extern void extract_range_from_binary_expr_1 (value_range *, enum tree_code, tree, value_range *, value_range *); diff --git a/gcc/wide-int-range.cc b/gcc/wide-int-range.cc new file mode 100644 index 00000000000..3491d89664d --- /dev/null +++ b/gcc/wide-int-range.cc @@ -0,0 +1,607 @@ +/* Support routines for range operations on wide ints. + Copyright (C) 2018 Free Software Foundation, Inc. + +This file is part of GCC. + +GCC is free software; you can redistribute it and/or modify +it under the terms of the GNU General Public License as published by +the Free Software Foundation; either version 3, or (at your option) +any later version. + +GCC is distributed in the hope that it will be useful, +but WITHOUT ANY WARRANTY; without even the implied warranty of +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +GNU General Public License for more details. + +You should have received a copy of the GNU General Public License +along with GCC; see the file COPYING3. If not see +<http://www.gnu.org/licenses/>. */ + +#include "config.h" +#include "system.h" +#include "coretypes.h" +#include "tree.h" +#include "fold-const.h" +#include "wide-int-range.h" + +/* Wrapper around wide_int_binop that adjusts for overflow. + + Return true if we can compute the result; i.e. if the operation + doesn't overflow or if the overflow is undefined. In the latter + case (if the operation overflows and overflow is undefined), then + adjust the result to be -INF or +INF depending on CODE, VAL1 and + VAL2. Return the value in *RES. + + Return false for division by zero, for which the result is + indeterminate. */ + +static bool +wide_int_binop_overflow (wide_int &res, + enum tree_code code, + const wide_int &w0, const wide_int &w1, + signop sign, bool overflow_undefined) +{ + wi::overflow_type overflow; + if (!wide_int_binop (res, code, w0, w1, sign, &overflow)) + return false; + + /* If the operation overflowed return -INF or +INF depending on the + operation and the combination of signs of the operands. */ + if (overflow && overflow_undefined) + { + switch (code) + { + case MULT_EXPR: + /* For multiplication, the sign of the overflow is given + by the comparison of the signs of the operands. */ + if (sign == UNSIGNED || w0.sign_mask () == w1.sign_mask ()) + res = wi::max_value (w0.get_precision (), sign); + else + res = wi::min_value (w0.get_precision (), sign); + return true; + + case TRUNC_DIV_EXPR: + case FLOOR_DIV_EXPR: + case CEIL_DIV_EXPR: + case EXACT_DIV_EXPR: + case ROUND_DIV_EXPR: + /* For division, the only case is -INF / -1 = +INF. */ + res = wi::max_value (w0.get_precision (), sign); + return true; + + default: + gcc_unreachable (); + } + } + return !overflow; +} + +/* For range [LB, UB] compute two wide_int bit masks. + + In the MAY_BE_NONZERO bit mask, if some bit is unset, it means that + for all numbers in the range the bit is 0, otherwise it might be 0 + or 1. + + In the MUST_BE_NONZERO bit mask, if some bit is set, it means that + for all numbers in the range the bit is 1, otherwise it might be 0 + or 1. */ + +void +wide_int_range_set_zero_nonzero_bits (signop sign, + const wide_int &lb, const wide_int &ub, + wide_int &may_be_nonzero, + wide_int &must_be_nonzero) +{ + may_be_nonzero = wi::minus_one (lb.get_precision ()); + must_be_nonzero = wi::zero (lb.get_precision ()); + + if (wi::eq_p (lb, ub)) + { + may_be_nonzero = lb; + must_be_nonzero = may_be_nonzero; + } + else if (wi::ge_p (lb, 0, sign) || wi::lt_p (ub, 0, sign)) + { + wide_int xor_mask = lb ^ ub; + may_be_nonzero = lb | ub; + must_be_nonzero = lb & ub; + if (xor_mask != 0) + { + wide_int mask = wi::mask (wi::floor_log2 (xor_mask), false, + may_be_nonzero.get_precision ()); + may_be_nonzero = may_be_nonzero | mask; + must_be_nonzero = wi::bit_and_not (must_be_nonzero, mask); + } + } +} + +/* Order 2 sets of wide int ranges (w0/w1, w2/w3) and set MIN/MAX + accordingly. */ + +static void +wide_int_range_min_max (wide_int &min, wide_int &max, + wide_int &w0, wide_int &w1, wide_int &w2, wide_int &w3, + signop sign) +{ + /* Order pairs w0,w1 and w2,w3. */ + if (wi::gt_p (w0, w1, sign)) + std::swap (w0, w1); + if (wi::gt_p (w2, w3, sign)) + std::swap (w2, w3); + + /* Choose min and max from the ordered pairs. */ + min = wi::min (w0, w2, sign); + max = wi::max (w1, w3, sign); +} + +/* Calculate the cross product of two sets of ranges (VR0 and VR1) and + store the result in [RES_LB, RES_UB]. + + CODE is the operation to perform with sign SIGN. + + OVERFLOW_UNDEFINED is set if overflow is undefined for the operation type. + + Return TRUE if we were able to calculate the cross product. */ + +bool +wide_int_range_cross_product (wide_int &res_lb, wide_int &res_ub, + enum tree_code code, signop sign, + const wide_int &vr0_lb, const wide_int &vr0_ub, + const wide_int &vr1_lb, const wide_int &vr1_ub, + bool overflow_undefined) +{ + wide_int cp1, cp2, cp3, cp4; + + /* Compute the 4 cross operations, bailing if we get an overflow we + can't handle. */ + + if (!wide_int_binop_overflow (cp1, code, vr0_lb, vr1_lb, sign, + overflow_undefined)) + return false; + + if (wi::eq_p (vr0_lb, vr0_ub)) + cp3 = cp1; + else if (!wide_int_binop_overflow (cp3, code, vr0_ub, vr1_lb, sign, + overflow_undefined)) + return false; + + if (wi::eq_p (vr1_lb, vr1_ub)) + cp2 = cp1; + else if (!wide_int_binop_overflow (cp2, code, vr0_lb, vr1_ub, sign, + overflow_undefined)) + return false; + + if (wi::eq_p (vr0_lb, vr0_ub)) + cp4 = cp2; + else if (!wide_int_binop_overflow (cp4, code, vr0_ub, vr1_ub, sign, + overflow_undefined)) + return false; + + wide_int_range_min_max (res_lb, res_ub, cp1, cp2, cp3, cp4, sign); + return true; +} + +/* Multiply two ranges when TYPE_OVERFLOW_WRAPS: + + [RES_LB, RES_UB] = [MIN0, MAX0] * [MIN1, MAX1] + + This is basically fancy code so we don't drop to varying with an + unsigned [-3,-1]*[-3,-1]. + + Return TRUE if we were able to perform the operation. */ + +bool +wide_int_range_mult_wrapping (wide_int &res_lb, + wide_int &res_ub, + signop sign, + unsigned prec, + const wide_int &min0_, + const wide_int &max0_, + const wide_int &min1_, + const wide_int &max1_) +{ + /* This test requires 2*prec bits if both operands are signed and + 2*prec + 2 bits if either is not. Therefore, extend the values + using the sign of the result to PREC2. From here on out, + everthing is just signed math no matter what the input types + were. */ + widest2_int min0 = widest2_int::from (min0_, sign); + widest2_int max0 = widest2_int::from (max0_, sign); + widest2_int min1 = widest2_int::from (min1_, sign); + widest2_int max1 = widest2_int::from (max1_, sign); + widest2_int sizem1 = wi::mask <widest2_int> (prec, false); + widest2_int size = sizem1 + 1; + + /* Canonicalize the intervals. */ + if (sign == UNSIGNED) + { + if (wi::ltu_p (size, min0 + max0)) + { + min0 -= size; + max0 -= size; + } + + if (wi::ltu_p (size, min1 + max1)) + { + min1 -= size; + max1 -= size; + } + } + + widest2_int prod0 = min0 * min1; + widest2_int prod1 = min0 * max1; + widest2_int prod2 = max0 * min1; + widest2_int prod3 = max0 * max1; + + /* Sort the 4 products so that min is in prod0 and max is in + prod3. */ + /* min0min1 > max0max1 */ + if (prod0 > prod3) + std::swap (prod0, prod3); + + /* min0max1 > max0min1 */ + if (prod1 > prod2) + std::swap (prod1, prod2); + + if (prod0 > prod1) + std::swap (prod0, prod1); + + if (prod2 > prod3) + std::swap (prod2, prod3); + + /* diff = max - min. */ + prod2 = prod3 - prod0; + if (wi::geu_p (prod2, sizem1)) + /* The range covers all values. */ + return false; + + res_lb = wide_int::from (prod0, prec, sign); + res_ub = wide_int::from (prod3, prec, sign); + return true; +} + +/* Perform multiplicative operation CODE on two ranges: + + [RES_LB, RES_UB] = [VR0_LB, VR0_UB] .CODE. [VR1_LB, VR1_LB] + + Return TRUE if we were able to perform the operation. + + NOTE: If code is MULT_EXPR and TYPE_OVERFLOW_WRAPS, the resulting + range must be canonicalized by the caller because its components + may be swapped. */ + +bool +wide_int_range_multiplicative_op (wide_int &res_lb, wide_int &res_ub, + enum tree_code code, + signop sign, + unsigned prec, + const wide_int &vr0_lb, + const wide_int &vr0_ub, + const wide_int &vr1_lb, + const wide_int &vr1_ub, + bool overflow_undefined, + bool overflow_wraps) +{ + /* Multiplications, divisions and shifts are a bit tricky to handle, + depending on the mix of signs we have in the two ranges, we + need to operate on different values to get the minimum and + maximum values for the new range. One approach is to figure + out all the variations of range combinations and do the + operations. + + However, this involves several calls to compare_values and it + is pretty convoluted. It's simpler to do the 4 operations + (MIN0 OP MIN1, MIN0 OP MAX1, MAX0 OP MIN1 and MAX0 OP MAX0 OP + MAX1) and then figure the smallest and largest values to form + the new range. */ + if (code == MULT_EXPR && overflow_wraps) + return wide_int_range_mult_wrapping (res_lb, res_ub, + sign, prec, + vr0_lb, vr0_ub, vr1_lb, vr1_ub); + return wide_int_range_cross_product (res_lb, res_ub, + code, sign, + vr0_lb, vr0_ub, vr1_lb, vr1_ub, + overflow_undefined); +} + +/* Perform a left shift operation on two ranges: + + [RES_LB, RES_UB] = [VR0_LB, VR0_UB] << [VR1_LB, VR1_LB] + + Return TRUE if we were able to perform the operation. + + NOTE: The resulting range must be canonicalized by the caller + because its contents components may be swapped. */ + +bool +wide_int_range_lshift (wide_int &res_lb, wide_int &res_ub, + signop sign, unsigned prec, + const wide_int &vr0_lb, const wide_int &vr0_ub, + const wide_int &vr1_lb, const wide_int &vr1_ub, + bool overflow_undefined, bool overflow_wraps) +{ + /* Transform left shifts by constants into multiplies. */ + if (wi::eq_p (vr1_lb, vr1_ub)) + { + int shift = wi::extract_uhwi (vr1_ub, 0, vr1_ub.get_precision ()); + wide_int tmp = wi::set_bit_in_zero (shift, prec); + return wide_int_range_multiplicative_op (res_lb, res_ub, + MULT_EXPR, sign, prec, + vr0_lb, vr0_ub, tmp, tmp, + overflow_undefined, + /*overflow_wraps=*/true); + } + + int overflow_pos = prec; + if (sign == SIGNED) + overflow_pos -= 1; + int bound_shift = overflow_pos - vr1_ub.to_shwi (); + /* If bound_shift == HOST_BITS_PER_WIDE_INT, the llshift can + overflow. However, for that to happen, vr1.max needs to be + zero, which means vr1 is a singleton range of zero, which + means it should be handled by the previous LSHIFT_EXPR + if-clause. */ + wide_int bound = wi::set_bit_in_zero (bound_shift, prec); + wide_int complement = ~(bound - 1); + wide_int low_bound, high_bound; + bool in_bounds = false; + if (sign == UNSIGNED) + { + low_bound = bound; + high_bound = complement; + if (wi::ltu_p (vr0_ub, low_bound)) + { + /* [5, 6] << [1, 2] == [10, 24]. */ + /* We're shifting out only zeroes, the value increases + monotonically. */ + in_bounds = true; + } + else if (wi::ltu_p (high_bound, vr0_lb)) + { + /* [0xffffff00, 0xffffffff] << [1, 2] + == [0xfffffc00, 0xfffffffe]. */ + /* We're shifting out only ones, the value decreases + monotonically. */ + in_bounds = true; + } + } + else + { + /* [-1, 1] << [1, 2] == [-4, 4]. */ + low_bound = complement; + high_bound = bound; + if (wi::lts_p (vr0_ub, high_bound) + && wi::lts_p (low_bound, vr0_lb)) + { + /* For non-negative numbers, we're shifting out only + zeroes, the value increases monotonically. + For negative numbers, we're shifting out only ones, the + value decreases monotomically. */ + in_bounds = true; + } + } + if (in_bounds) + return wide_int_range_multiplicative_op (res_lb, res_ub, + LSHIFT_EXPR, sign, prec, + vr0_lb, vr0_ub, + vr1_lb, vr1_ub, + overflow_undefined, + overflow_wraps); + return false; +} + +/* Return TRUE if a bit operation on two ranges can be easily + optimized in terms of a mask. + + Basically, for BIT_AND_EXPR or BIT_IOR_EXPR see if we can optimize: + + [LB, UB] op Z + into: + [LB op Z, UB op Z] + + It is up to the caller to perform the actual folding above. */ + +bool +wide_int_range_can_optimize_bit_op (tree_code code, + const wide_int &lb, const wide_int &ub, + const wide_int &mask) + +{ + if (code != BIT_AND_EXPR && code != BIT_IOR_EXPR) + return false; + /* If Z is a constant which (for op | its bitwise not) has n + consecutive least significant bits cleared followed by m 1 + consecutive bits set immediately above it and either + m + n == precision, or (x >> (m + n)) == (y >> (m + n)). + + The least significant n bits of all the values in the range are + cleared or set, the m bits above it are preserved and any bits + above these are required to be the same for all values in the + range. */ + + wide_int w = mask; + int m = 0, n = 0; + if (code == BIT_IOR_EXPR) + w = ~w; + if (wi::eq_p (w, 0)) + n = w.get_precision (); + else + { + n = wi::ctz (w); + w = ~(w | wi::mask (n, false, w.get_precision ())); + if (wi::eq_p (w, 0)) + m = w.get_precision () - n; + else + m = wi::ctz (w) - n; + } + wide_int new_mask = wi::mask (m + n, true, w.get_precision ()); + if ((new_mask & lb) == (new_mask & ub)) + return true; + + return false; +} + +/* Calculate the XOR of two ranges and store the result in [WMIN,WMAX]. + The two input ranges are described by their MUST_BE_NONZERO and + MAY_BE_NONZERO bit masks. + + Return TRUE if we were able to successfully calculate the new range. */ + +bool +wide_int_range_bit_xor (wide_int &wmin, wide_int &wmax, + signop sign, + unsigned prec, + const wide_int &must_be_nonzero0, + const wide_int &may_be_nonzero0, + const wide_int &must_be_nonzero1, + const wide_int &may_be_nonzero1) +{ + wide_int result_zero_bits = ((must_be_nonzero0 & must_be_nonzero1) + | ~(may_be_nonzero0 | may_be_nonzero1)); + wide_int result_one_bits + = (wi::bit_and_not (must_be_nonzero0, may_be_nonzero1) + | wi::bit_and_not (must_be_nonzero1, may_be_nonzero0)); + wmax = ~result_zero_bits; + wmin = result_one_bits; + /* If the range has all positive or all negative values, the result + is better than VARYING. */ + if (wi::lt_p (wmin, 0, sign) || wi::ge_p (wmax, 0, sign)) + return true; + wmin = wi::min_value (prec, sign); + wmax = wi::max_value (prec, sign); + return false; +} + +/* Calculate the IOR of two ranges and store the result in [WMIN,WMAX]. + Return TRUE if we were able to successfully calculate the new range. */ + +bool +wide_int_range_bit_ior (wide_int &wmin, wide_int &wmax, + signop sign, + const wide_int &vr0_min, + const wide_int &vr0_max, + const wide_int &vr1_min, + const wide_int &vr1_max, + const wide_int &must_be_nonzero0, + const wide_int &may_be_nonzero0, + const wide_int &must_be_nonzero1, + const wide_int &may_be_nonzero1) +{ + wmin = must_be_nonzero0 | must_be_nonzero1; + wmax = may_be_nonzero0 | may_be_nonzero1; + /* If the input ranges contain only positive values we can + truncate the minimum of the result range to the maximum + of the input range minima. */ + if (wi::ge_p (vr0_min, 0, sign) + && wi::ge_p (vr1_min, 0, sign)) + { + wmin = wi::max (wmin, vr0_min, sign); + wmin = wi::max (wmin, vr1_min, sign); + } + /* If either input range contains only negative values + we can truncate the minimum of the result range to the + respective minimum range. */ + if (wi::lt_p (vr0_max, 0, sign)) + wmin = wi::max (wmin, vr0_min, sign); + if (wi::lt_p (vr1_max, 0, sign)) + wmin = wi::max (wmin, vr1_min, sign); + /* If the limits got swapped around, indicate error so we can adjust + the range to VARYING. */ + if (wi::gt_p (wmin, wmax,sign)) + return false; + return true; +} + +/* Calculate the bitwise AND of two ranges and store the result in [WMIN,WMAX]. + Return TRUE if we were able to successfully calculate the new range. */ + +bool +wide_int_range_bit_and (wide_int &wmin, wide_int &wmax, + signop sign, + unsigned prec, + const wide_int &vr0_min, + const wide_int &vr0_max, + const wide_int &vr1_min, + const wide_int &vr1_max, + const wide_int &must_be_nonzero0, + const wide_int &may_be_nonzero0, + const wide_int &must_be_nonzero1, + const wide_int &may_be_nonzero1) +{ + wmin = must_be_nonzero0 & must_be_nonzero1; + wmax = may_be_nonzero0 & may_be_nonzero1; + /* If both input ranges contain only negative values we can + truncate the result range maximum to the minimum of the + input range maxima. */ + if (wi::lt_p (vr0_max, 0, sign) && wi::lt_p (vr1_max, 0, sign)) + { + wmax = wi::min (wmax, vr0_max, sign); + wmax = wi::min (wmax, vr1_max, sign); + } + /* If either input range contains only non-negative values + we can truncate the result range maximum to the respective + maximum of the input range. */ + if (wi::ge_p (vr0_min, 0, sign)) + wmax = wi::min (wmax, vr0_max, sign); + if (wi::ge_p (vr1_min, 0, sign)) + wmax = wi::min (wmax, vr1_max, sign); + /* PR68217: In case of signed & sign-bit-CST should + result in [-INF, 0] instead of [-INF, INF]. */ + if (wi::gt_p (wmin, wmax, sign)) + { + wide_int sign_bit = wi::set_bit_in_zero (prec - 1, prec); + if (sign == SIGNED + && ((wi::eq_p (vr0_min, vr0_max) + && !wi::cmps (vr0_min, sign_bit)) + || (wi::eq_p (vr1_min, vr1_max) + && !wi::cmps (vr1_min, sign_bit)))) + { + wmin = wi::min_value (prec, sign); + wmax = wi::zero (prec); + } + } + /* If the limits got swapped around, indicate error so we can adjust + the range to VARYING. */ + if (wi::gt_p (wmin, wmax,sign)) + return false; + return true; +} + +/* Calculate TRUNC_MOD_EXPR on two ranges and store the result in + [WMIN,WMAX]. */ + +void +wide_int_range_trunc_mod (wide_int &wmin, wide_int &wmax, + signop sign, + unsigned prec, + const wide_int &vr0_min, + const wide_int &vr0_max, + const wide_int &vr1_min, + const wide_int &vr1_max) +{ + wide_int tmp; + + /* ABS (A % B) < ABS (B) and either + 0 <= A % B <= A or A <= A % B <= 0. */ + wmax = vr1_max - 1; + if (sign == SIGNED) + { + tmp = -1 - vr1_min; + wmax = wi::smax (wmax, tmp); + } + + if (sign == UNSIGNED) + wmin = wi::zero (prec); + else + { + wmin = -wmax; + tmp = vr0_min; + if (wi::gts_p (tmp, 0)) + tmp = wi::zero (prec); + wmin = wi::smax (wmin, tmp); + } + tmp = vr0_max; + if (sign == SIGNED && wi::neg_p (tmp)) + tmp = wi::zero (prec); + wmax = wi::min (wmax, tmp, sign); +} diff --git a/gcc/wide-int-range.h b/gcc/wide-int-range.h new file mode 100644 index 00000000000..4421bc8aeca --- /dev/null +++ b/gcc/wide-int-range.h @@ -0,0 +1,115 @@ +/* Support routines for range operations on wide ints. + Copyright (C) 2018 Free Software Foundation, Inc. + +This file is part of GCC. + +GCC is free software; you can redistribute it and/or modify +it under the terms of the GNU General Public License as published by +the Free Software Foundation; either version 3, or (at your option) +any later version. + +GCC is distributed in the hope that it will be useful, +but WITHOUT ANY WARRANTY; without even the implied warranty of +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +GNU General Public License for more details. + +You should have received a copy of the GNU General Public License +along with GCC; see the file COPYING3. If not see +<http://www.gnu.org/licenses/>. */ + +#ifndef GCC_WIDE_INT_RANGE_H +#define GCC_WIDE_INT_RANGE_H + +extern bool wide_int_range_cross_product (wide_int &res_lb, wide_int &res_ub, + enum tree_code code, signop sign, + const wide_int &, const wide_int &, + const wide_int &, const wide_int &, + bool overflow_undefined); +extern bool wide_int_range_mult_wrapping (wide_int &res_lb, + wide_int &res_ub, + signop sign, + unsigned prec, + const wide_int &min0_, + const wide_int &max0_, + const wide_int &min1_, + const wide_int &max1_); +extern bool wide_int_range_multiplicative_op (wide_int &res_lb, + wide_int &res_ub, + enum tree_code code, + signop sign, + unsigned prec, + const wide_int &vr0_lb, + const wide_int &vr0_ub, + const wide_int &vr1_lb, + const wide_int &vr1_ub, + bool overflow_undefined, + bool overflow_wraps); +extern bool wide_int_range_lshift (wide_int &res_lb, wide_int &res_ub, + signop sign, unsigned prec, + const wide_int &, const wide_int &, + const wide_int &, const wide_int &, + bool overflow_undefined, + bool overflow_wraps); +extern void wide_int_range_set_zero_nonzero_bits (signop, + const wide_int &lb, + const wide_int &ub, + wide_int &may_be_nonzero, + wide_int &must_be_nonzero); +extern bool wide_int_range_can_optimize_bit_op (tree_code, + const wide_int &lb, + const wide_int &ub, + const wide_int &mask); +extern bool wide_int_range_bit_xor (wide_int &wmin, wide_int &wmax, + signop sign, + unsigned prec, + const wide_int &must_be_nonzero0, + const wide_int &may_be_nonzero0, + const wide_int &must_be_nonzero1, + const wide_int &may_be_nonzero1); +extern bool wide_int_range_bit_ior (wide_int &wmin, wide_int &wmax, + signop sign, + const wide_int &vr0_min, + const wide_int &vr0_max, + const wide_int &vr1_min, + const wide_int &vr1_max, + const wide_int &must_be_nonzero0, + const wide_int &may_be_nonzero0, + const wide_int &must_be_nonzero1, + const wide_int &may_be_nonzero1); +extern bool wide_int_range_bit_and (wide_int &wmin, wide_int &wmax, + signop sign, + unsigned prec, + const wide_int &vr0_min, + const wide_int &vr0_max, + const wide_int &vr1_min, + const wide_int &vr1_max, + const wide_int &must_be_nonzero0, + const wide_int &may_be_nonzero0, + const wide_int &must_be_nonzero1, + const wide_int &may_be_nonzero1); +extern void wide_int_range_trunc_mod (wide_int &wmin, wide_int &wmax, + signop sign, + unsigned prec, + const wide_int &vr0_min, + const wide_int &vr0_max, + const wide_int &vr1_min, + const wide_int &vr1_max); + +/* Return TRUE if shifting by range [MIN, MAX] is undefined behavior. */ + +inline bool +wide_int_range_shift_undefined_p (signop sign, unsigned prec, + const wide_int &min, const wide_int &max) +{ + /* ?? Note: The original comment said this only applied to + RSHIFT_EXPR, but it was being applied to both left and right + shifts. */ + + /* Shifting by any values outside [0..prec-1], gets undefined + behavior from the shift operation. We cannot even trust + SHIFT_COUNT_TRUNCATED at this stage, because that applies to rtl + shifts, and the operation at the tree level may be widened. */ + return wi::lt_p (min, 0, sign) || wi::ge_p (max, prec, sign); +} + +#endif /* GCC_WIDE_INT_RANGE_H */ |