1 /* Support routines for range operations on wide ints.
2 Copyright (C) 2018 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 3, or (at your option)
11 GCC is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING3. If not see
18 <http://www.gnu.org/licenses/>. */
22 #include "coretypes.h"
24 #include "fold-const.h"
25 #include "wide-int-range.h"
27 /* Wrapper around wide_int_binop that adjusts for overflow.
29 Return true if we can compute the result; i.e. if the operation
30 doesn't overflow or if the overflow is undefined. In the latter
31 case (if the operation overflows and overflow is undefined), then
32 adjust the result to be -INF or +INF depending on CODE, VAL1 and
33 VAL2. Return the value in *RES.
35 Return false for division by zero, for which the result is
39 wide_int_binop_overflow (wide_int
&res
,
41 const wide_int
&w0
, const wide_int
&w1
,
42 signop sign
, bool overflow_undefined
)
44 wi::overflow_type overflow
;
45 if (!wide_int_binop (res
, code
, w0
, w1
, sign
, &overflow
))
48 /* If the operation overflowed return -INF or +INF depending on the
49 operation and the combination of signs of the operands. */
50 if (overflow
&& overflow_undefined
)
55 /* For multiplication, the sign of the overflow is given
56 by the comparison of the signs of the operands. */
57 if (sign
== UNSIGNED
|| w0
.sign_mask () == w1
.sign_mask ())
58 res
= wi::max_value (w0
.get_precision (), sign
);
60 res
= wi::min_value (w0
.get_precision (), sign
);
68 /* For division, the only case is -INF / -1 = +INF. */
69 res
= wi::max_value (w0
.get_precision (), sign
);
79 /* For range [LB, UB] compute two wide_int bit masks.
81 In the MAY_BE_NONZERO bit mask, if some bit is unset, it means that
82 for all numbers in the range the bit is 0, otherwise it might be 0
85 In the MUST_BE_NONZERO bit mask, if some bit is set, it means that
86 for all numbers in the range the bit is 1, otherwise it might be 0
90 wide_int_range_set_zero_nonzero_bits (signop sign
,
91 const wide_int
&lb
, const wide_int
&ub
,
92 wide_int
&may_be_nonzero
,
93 wide_int
&must_be_nonzero
)
95 may_be_nonzero
= wi::minus_one (lb
.get_precision ());
96 must_be_nonzero
= wi::zero (lb
.get_precision ());
98 if (wi::eq_p (lb
, ub
))
101 must_be_nonzero
= may_be_nonzero
;
103 else if (wi::ge_p (lb
, 0, sign
) || wi::lt_p (ub
, 0, sign
))
105 wide_int xor_mask
= lb
^ ub
;
106 may_be_nonzero
= lb
| ub
;
107 must_be_nonzero
= lb
& ub
;
110 wide_int mask
= wi::mask (wi::floor_log2 (xor_mask
), false,
111 may_be_nonzero
.get_precision ());
112 may_be_nonzero
= may_be_nonzero
| mask
;
113 must_be_nonzero
= wi::bit_and_not (must_be_nonzero
, mask
);
118 /* Order 2 sets of wide int ranges (w0/w1, w2/w3) and set MIN/MAX
122 wide_int_range_min_max (wide_int
&min
, wide_int
&max
,
123 wide_int
&w0
, wide_int
&w1
, wide_int
&w2
, wide_int
&w3
,
126 /* Order pairs w0,w1 and w2,w3. */
127 if (wi::gt_p (w0
, w1
, sign
))
129 if (wi::gt_p (w2
, w3
, sign
))
132 /* Choose min and max from the ordered pairs. */
133 min
= wi::min (w0
, w2
, sign
);
134 max
= wi::max (w1
, w3
, sign
);
137 /* Calculate the cross product of two sets of ranges (VR0 and VR1) and
138 store the result in [RES_LB, RES_UB].
140 CODE is the operation to perform with sign SIGN.
142 OVERFLOW_UNDEFINED is set if overflow is undefined for the operation type.
144 Return TRUE if we were able to calculate the cross product. */
147 wide_int_range_cross_product (wide_int
&res_lb
, wide_int
&res_ub
,
148 enum tree_code code
, signop sign
,
149 const wide_int
&vr0_lb
, const wide_int
&vr0_ub
,
150 const wide_int
&vr1_lb
, const wide_int
&vr1_ub
,
151 bool overflow_undefined
)
153 wide_int cp1
, cp2
, cp3
, cp4
;
155 /* Compute the 4 cross operations, bailing if we get an overflow we
158 if (!wide_int_binop_overflow (cp1
, code
, vr0_lb
, vr1_lb
, sign
,
162 if (wi::eq_p (vr0_lb
, vr0_ub
))
164 else if (!wide_int_binop_overflow (cp3
, code
, vr0_ub
, vr1_lb
, sign
,
168 if (wi::eq_p (vr1_lb
, vr1_ub
))
170 else if (!wide_int_binop_overflow (cp2
, code
, vr0_lb
, vr1_ub
, sign
,
174 if (wi::eq_p (vr0_lb
, vr0_ub
))
176 else if (!wide_int_binop_overflow (cp4
, code
, vr0_ub
, vr1_ub
, sign
,
180 wide_int_range_min_max (res_lb
, res_ub
, cp1
, cp2
, cp3
, cp4
, sign
);
184 /* Multiply two ranges when TYPE_OVERFLOW_WRAPS:
186 [RES_LB, RES_UB] = [MIN0, MAX0] * [MIN1, MAX1]
188 This is basically fancy code so we don't drop to varying with an
189 unsigned [-3,-1]*[-3,-1].
191 Return TRUE if we were able to perform the operation. */
194 wide_int_range_mult_wrapping (wide_int
&res_lb
,
198 const wide_int
&min0_
,
199 const wide_int
&max0_
,
200 const wide_int
&min1_
,
201 const wide_int
&max1_
)
203 /* This test requires 2*prec bits if both operands are signed and
204 2*prec + 2 bits if either is not. Therefore, extend the values
205 using the sign of the result to PREC2. From here on out,
206 everthing is just signed math no matter what the input types
208 widest2_int min0
= widest2_int::from (min0_
, sign
);
209 widest2_int max0
= widest2_int::from (max0_
, sign
);
210 widest2_int min1
= widest2_int::from (min1_
, sign
);
211 widest2_int max1
= widest2_int::from (max1_
, sign
);
212 widest2_int sizem1
= wi::mask
<widest2_int
> (prec
, false);
213 widest2_int size
= sizem1
+ 1;
215 /* Canonicalize the intervals. */
216 if (sign
== UNSIGNED
)
218 if (wi::ltu_p (size
, min0
+ max0
))
224 if (wi::ltu_p (size
, min1
+ max1
))
231 widest2_int prod0
= min0
* min1
;
232 widest2_int prod1
= min0
* max1
;
233 widest2_int prod2
= max0
* min1
;
234 widest2_int prod3
= max0
* max1
;
236 /* Sort the 4 products so that min is in prod0 and max is in
238 /* min0min1 > max0max1 */
240 std::swap (prod0
, prod3
);
242 /* min0max1 > max0min1 */
244 std::swap (prod1
, prod2
);
247 std::swap (prod0
, prod1
);
250 std::swap (prod2
, prod3
);
252 /* diff = max - min. */
253 prod2
= prod3
- prod0
;
254 if (wi::geu_p (prod2
, sizem1
))
255 /* The range covers all values. */
258 res_lb
= wide_int::from (prod0
, prec
, sign
);
259 res_ub
= wide_int::from (prod3
, prec
, sign
);
263 /* Perform multiplicative operation CODE on two ranges:
265 [RES_LB, RES_UB] = [VR0_LB, VR0_UB] .CODE. [VR1_LB, VR1_LB]
267 Return TRUE if we were able to perform the operation.
269 NOTE: If code is MULT_EXPR and TYPE_OVERFLOW_WRAPS, the resulting
270 range must be canonicalized by the caller because its components
274 wide_int_range_multiplicative_op (wide_int
&res_lb
, wide_int
&res_ub
,
278 const wide_int
&vr0_lb
,
279 const wide_int
&vr0_ub
,
280 const wide_int
&vr1_lb
,
281 const wide_int
&vr1_ub
,
282 bool overflow_undefined
,
285 /* Multiplications, divisions and shifts are a bit tricky to handle,
286 depending on the mix of signs we have in the two ranges, we
287 need to operate on different values to get the minimum and
288 maximum values for the new range. One approach is to figure
289 out all the variations of range combinations and do the
292 However, this involves several calls to compare_values and it
293 is pretty convoluted. It's simpler to do the 4 operations
294 (MIN0 OP MIN1, MIN0 OP MAX1, MAX0 OP MIN1 and MAX0 OP MAX0 OP
295 MAX1) and then figure the smallest and largest values to form
297 if (code
== MULT_EXPR
&& overflow_wraps
)
298 return wide_int_range_mult_wrapping (res_lb
, res_ub
,
300 vr0_lb
, vr0_ub
, vr1_lb
, vr1_ub
);
301 return wide_int_range_cross_product (res_lb
, res_ub
,
303 vr0_lb
, vr0_ub
, vr1_lb
, vr1_ub
,
307 /* Perform a left shift operation on two ranges:
309 [RES_LB, RES_UB] = [VR0_LB, VR0_UB] << [VR1_LB, VR1_LB]
311 Return TRUE if we were able to perform the operation.
313 NOTE: The resulting range must be canonicalized by the caller
314 because its contents components may be swapped. */
317 wide_int_range_lshift (wide_int
&res_lb
, wide_int
&res_ub
,
318 signop sign
, unsigned prec
,
319 const wide_int
&vr0_lb
, const wide_int
&vr0_ub
,
320 const wide_int
&vr1_lb
, const wide_int
&vr1_ub
,
321 bool overflow_undefined
, bool overflow_wraps
)
323 /* Transform left shifts by constants into multiplies. */
324 if (wi::eq_p (vr1_lb
, vr1_ub
))
326 int shift
= wi::extract_uhwi (vr1_ub
, 0, vr1_ub
.get_precision ());
327 wide_int tmp
= wi::set_bit_in_zero (shift
, prec
);
328 return wide_int_range_multiplicative_op (res_lb
, res_ub
,
329 MULT_EXPR
, sign
, prec
,
330 vr0_lb
, vr0_ub
, tmp
, tmp
,
332 /*overflow_wraps=*/true);
335 int overflow_pos
= prec
;
338 int bound_shift
= overflow_pos
- vr1_ub
.to_shwi ();
339 /* If bound_shift == HOST_BITS_PER_WIDE_INT, the llshift can
340 overflow. However, for that to happen, vr1.max needs to be
341 zero, which means vr1 is a singleton range of zero, which
342 means it should be handled by the previous LSHIFT_EXPR
344 wide_int bound
= wi::set_bit_in_zero (bound_shift
, prec
);
345 wide_int complement
= ~(bound
- 1);
346 wide_int low_bound
, high_bound
;
347 bool in_bounds
= false;
348 if (sign
== UNSIGNED
)
351 high_bound
= complement
;
352 if (wi::ltu_p (vr0_ub
, low_bound
))
354 /* [5, 6] << [1, 2] == [10, 24]. */
355 /* We're shifting out only zeroes, the value increases
359 else if (wi::ltu_p (high_bound
, vr0_lb
))
361 /* [0xffffff00, 0xffffffff] << [1, 2]
362 == [0xfffffc00, 0xfffffffe]. */
363 /* We're shifting out only ones, the value decreases
370 /* [-1, 1] << [1, 2] == [-4, 4]. */
371 low_bound
= complement
;
373 if (wi::lts_p (vr0_ub
, high_bound
)
374 && wi::lts_p (low_bound
, vr0_lb
))
376 /* For non-negative numbers, we're shifting out only
377 zeroes, the value increases monotonically.
378 For negative numbers, we're shifting out only ones, the
379 value decreases monotomically. */
384 return wide_int_range_multiplicative_op (res_lb
, res_ub
,
385 LSHIFT_EXPR
, sign
, prec
,
393 /* Return TRUE if a bit operation on two ranges can be easily
394 optimized in terms of a mask.
396 Basically, for BIT_AND_EXPR or BIT_IOR_EXPR see if we can optimize:
402 It is up to the caller to perform the actual folding above. */
405 wide_int_range_can_optimize_bit_op (tree_code code
,
406 const wide_int
&lb
, const wide_int
&ub
,
407 const wide_int
&mask
)
410 if (code
!= BIT_AND_EXPR
&& code
!= BIT_IOR_EXPR
)
412 /* If Z is a constant which (for op | its bitwise not) has n
413 consecutive least significant bits cleared followed by m 1
414 consecutive bits set immediately above it and either
415 m + n == precision, or (x >> (m + n)) == (y >> (m + n)).
417 The least significant n bits of all the values in the range are
418 cleared or set, the m bits above it are preserved and any bits
419 above these are required to be the same for all values in the
424 if (code
== BIT_IOR_EXPR
)
427 n
= w
.get_precision ();
431 w
= ~(w
| wi::mask (n
, false, w
.get_precision ()));
433 m
= w
.get_precision () - n
;
437 wide_int new_mask
= wi::mask (m
+ n
, true, w
.get_precision ());
438 if ((new_mask
& lb
) == (new_mask
& ub
))
444 /* Calculate the XOR of two ranges and store the result in [WMIN,WMAX].
445 The two input ranges are described by their MUST_BE_NONZERO and
446 MAY_BE_NONZERO bit masks.
448 Return TRUE if we were able to successfully calculate the new range. */
451 wide_int_range_bit_xor (wide_int
&wmin
, wide_int
&wmax
,
454 const wide_int
&must_be_nonzero0
,
455 const wide_int
&may_be_nonzero0
,
456 const wide_int
&must_be_nonzero1
,
457 const wide_int
&may_be_nonzero1
)
459 wide_int result_zero_bits
= ((must_be_nonzero0
& must_be_nonzero1
)
460 | ~(may_be_nonzero0
| may_be_nonzero1
));
461 wide_int result_one_bits
462 = (wi::bit_and_not (must_be_nonzero0
, may_be_nonzero1
)
463 | wi::bit_and_not (must_be_nonzero1
, may_be_nonzero0
));
464 wmax
= ~result_zero_bits
;
465 wmin
= result_one_bits
;
466 /* If the range has all positive or all negative values, the result
467 is better than VARYING. */
468 if (wi::lt_p (wmin
, 0, sign
) || wi::ge_p (wmax
, 0, sign
))
470 wmin
= wi::min_value (prec
, sign
);
471 wmax
= wi::max_value (prec
, sign
);
475 /* Calculate the IOR of two ranges and store the result in [WMIN,WMAX].
476 Return TRUE if we were able to successfully calculate the new range. */
479 wide_int_range_bit_ior (wide_int
&wmin
, wide_int
&wmax
,
481 const wide_int
&vr0_min
,
482 const wide_int
&vr0_max
,
483 const wide_int
&vr1_min
,
484 const wide_int
&vr1_max
,
485 const wide_int
&must_be_nonzero0
,
486 const wide_int
&may_be_nonzero0
,
487 const wide_int
&must_be_nonzero1
,
488 const wide_int
&may_be_nonzero1
)
490 wmin
= must_be_nonzero0
| must_be_nonzero1
;
491 wmax
= may_be_nonzero0
| may_be_nonzero1
;
492 /* If the input ranges contain only positive values we can
493 truncate the minimum of the result range to the maximum
494 of the input range minima. */
495 if (wi::ge_p (vr0_min
, 0, sign
)
496 && wi::ge_p (vr1_min
, 0, sign
))
498 wmin
= wi::max (wmin
, vr0_min
, sign
);
499 wmin
= wi::max (wmin
, vr1_min
, sign
);
501 /* If either input range contains only negative values
502 we can truncate the minimum of the result range to the
503 respective minimum range. */
504 if (wi::lt_p (vr0_max
, 0, sign
))
505 wmin
= wi::max (wmin
, vr0_min
, sign
);
506 if (wi::lt_p (vr1_max
, 0, sign
))
507 wmin
= wi::max (wmin
, vr1_min
, sign
);
508 /* If the limits got swapped around, indicate error so we can adjust
509 the range to VARYING. */
510 if (wi::gt_p (wmin
, wmax
,sign
))
515 /* Calculate the bitwise AND of two ranges and store the result in [WMIN,WMAX].
516 Return TRUE if we were able to successfully calculate the new range. */
519 wide_int_range_bit_and (wide_int
&wmin
, wide_int
&wmax
,
522 const wide_int
&vr0_min
,
523 const wide_int
&vr0_max
,
524 const wide_int
&vr1_min
,
525 const wide_int
&vr1_max
,
526 const wide_int
&must_be_nonzero0
,
527 const wide_int
&may_be_nonzero0
,
528 const wide_int
&must_be_nonzero1
,
529 const wide_int
&may_be_nonzero1
)
531 wmin
= must_be_nonzero0
& must_be_nonzero1
;
532 wmax
= may_be_nonzero0
& may_be_nonzero1
;
533 /* If both input ranges contain only negative values we can
534 truncate the result range maximum to the minimum of the
535 input range maxima. */
536 if (wi::lt_p (vr0_max
, 0, sign
) && wi::lt_p (vr1_max
, 0, sign
))
538 wmax
= wi::min (wmax
, vr0_max
, sign
);
539 wmax
= wi::min (wmax
, vr1_max
, sign
);
541 /* If either input range contains only non-negative values
542 we can truncate the result range maximum to the respective
543 maximum of the input range. */
544 if (wi::ge_p (vr0_min
, 0, sign
))
545 wmax
= wi::min (wmax
, vr0_max
, sign
);
546 if (wi::ge_p (vr1_min
, 0, sign
))
547 wmax
= wi::min (wmax
, vr1_max
, sign
);
548 /* PR68217: In case of signed & sign-bit-CST should
549 result in [-INF, 0] instead of [-INF, INF]. */
550 if (wi::gt_p (wmin
, wmax
, sign
))
552 wide_int sign_bit
= wi::set_bit_in_zero (prec
- 1, prec
);
554 && ((wi::eq_p (vr0_min
, vr0_max
)
555 && !wi::cmps (vr0_min
, sign_bit
))
556 || (wi::eq_p (vr1_min
, vr1_max
)
557 && !wi::cmps (vr1_min
, sign_bit
))))
559 wmin
= wi::min_value (prec
, sign
);
560 wmax
= wi::zero (prec
);
563 /* If the limits got swapped around, indicate error so we can adjust
564 the range to VARYING. */
565 if (wi::gt_p (wmin
, wmax
,sign
))
570 /* Calculate TRUNC_MOD_EXPR on two ranges and store the result in
574 wide_int_range_trunc_mod (wide_int
&wmin
, wide_int
&wmax
,
577 const wide_int
&vr0_min
,
578 const wide_int
&vr0_max
,
579 const wide_int
&vr1_min
,
580 const wide_int
&vr1_max
)
584 /* ABS (A % B) < ABS (B) and either
585 0 <= A % B <= A or A <= A % B <= 0. */
590 wmax
= wi::smax (wmax
, tmp
);
593 if (sign
== UNSIGNED
)
594 wmin
= wi::zero (prec
);
599 if (wi::gts_p (tmp
, 0))
600 tmp
= wi::zero (prec
);
601 wmin
= wi::smax (wmin
, tmp
);
604 if (sign
== SIGNED
&& wi::neg_p (tmp
))
605 tmp
= wi::zero (prec
);
606 wmax
= wi::min (wmax
, tmp
, sign
);