Mercurial > hg > CbC > CbC_gcc

comparison gcc/wide-int-range.cc @ 131:84e7813d76e9

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
gcc-8.2
author mir3636
date Thu, 25 Oct 2018 07:37:49 +0900
parents
children
comparison
equal deleted inserted replaced
111:04ced10e8804 131:84e7813d76e9
1 /* Support routines for range operations on wide ints.
2 Copyright (C) 2018 Free Software Foundation, Inc.
3
4 This file is part of GCC.
5
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)
9 any later version.
10
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.
15
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/>. */
19
20 #include "config.h"
21 #include "system.h"
22 #include "coretypes.h"
23 #include "tree.h"
24 #include "function.h"
25 #include "fold-const.h"
26 #include "wide-int-range.h"
27
28 /* Wrapper around wide_int_binop that adjusts for overflow.
29
30 Return true if we can compute the result; i.e. if the operation
31 doesn't overflow or if the overflow is undefined. In the latter
32 case (if the operation overflows and overflow is undefined), then
33 adjust the result to be -INF or +INF depending on CODE, VAL1 and
34 VAL2. Return the value in *RES.
35
36 Return false for division by zero, for which the result is
37 indeterminate. */
38
39 static bool
40 wide_int_binop_overflow (wide_int &res,
41 enum tree_code code,
42 const wide_int &w0, const wide_int &w1,
43 signop sign, bool overflow_undefined)
44 {
45 wi::overflow_type overflow;
46 if (!wide_int_binop (res, code, w0, w1, sign, &overflow))
47 return false;
48
49 /* If the operation overflowed return -INF or +INF depending on the
50 operation and the combination of signs of the operands. */
51 if (overflow && overflow_undefined)
52 {
53 switch (code)
54 {
55 case MULT_EXPR:
56 /* For multiplication, the sign of the overflow is given
57 by the comparison of the signs of the operands. */
58 if (sign == UNSIGNED || w0.sign_mask () == w1.sign_mask ())
59 res = wi::max_value (w0.get_precision (), sign);
60 else
61 res = wi::min_value (w0.get_precision (), sign);
62 return true;
63
64 case TRUNC_DIV_EXPR:
65 case FLOOR_DIV_EXPR:
66 case CEIL_DIV_EXPR:
67 case EXACT_DIV_EXPR:
68 case ROUND_DIV_EXPR:
69 /* For division, the only case is -INF / -1 = +INF. */
70 res = wi::max_value (w0.get_precision (), sign);
71 return true;
72
73 default:
74 gcc_unreachable ();
75 }
76 }
77 return !overflow;
78 }
79
80 /* For range [LB, UB] compute two wide_int bit masks.
81
82 In the MAY_BE_NONZERO bit mask, if some bit is unset, it means that
83 for all numbers in the range the bit is 0, otherwise it might be 0
84 or 1.
85
86 In the MUST_BE_NONZERO bit mask, if some bit is set, it means that
87 for all numbers in the range the bit is 1, otherwise it might be 0
88 or 1. */
89
90 void
91 wide_int_range_set_zero_nonzero_bits (signop sign,
92 const wide_int &lb, const wide_int &ub,
93 wide_int &may_be_nonzero,
94 wide_int &must_be_nonzero)
95 {
96 may_be_nonzero = wi::minus_one (lb.get_precision ());
97 must_be_nonzero = wi::zero (lb.get_precision ());
98
99 if (wi::eq_p (lb, ub))
100 {
101 may_be_nonzero = lb;
102 must_be_nonzero = may_be_nonzero;
103 }
104 else if (wi::ge_p (lb, 0, sign) || wi::lt_p (ub, 0, sign))
105 {
106 wide_int xor_mask = lb ^ ub;
107 may_be_nonzero = lb | ub;
108 must_be_nonzero = lb & ub;
109 if (xor_mask != 0)
110 {
111 wide_int mask = wi::mask (wi::floor_log2 (xor_mask), false,
112 may_be_nonzero.get_precision ());
113 may_be_nonzero = may_be_nonzero | mask;
114 must_be_nonzero = wi::bit_and_not (must_be_nonzero, mask);
115 }
116 }
117 }
118
119 /* Order 2 sets of wide int ranges (w0/w1, w2/w3) and set MIN/MAX
120 accordingly. */
121
122 static void
123 wide_int_range_order_set (wide_int &min, wide_int &max,
124 wide_int &w0, wide_int &w1,
125 wide_int &w2, wide_int &w3,
126 signop sign)
127 {
128 /* Order pairs w0,w1 and w2,w3. */
129 if (wi::gt_p (w0, w1, sign))
130 std::swap (w0, w1);
131 if (wi::gt_p (w2, w3, sign))
132 std::swap (w2, w3);
133
134 /* Choose min and max from the ordered pairs. */
135 min = wi::min (w0, w2, sign);
136 max = wi::max (w1, w3, sign);
137 }
138
139 /* Calculate the cross product of two sets of ranges (VR0 and VR1) and
140 store the result in [RES_LB, RES_UB].
141
142 CODE is the operation to perform with sign SIGN.
143
144 OVERFLOW_UNDEFINED is set if overflow is undefined for the operation type.
145
146 Return TRUE if we were able to calculate the cross product. */
147
148 bool
149 wide_int_range_cross_product (wide_int &res_lb, wide_int &res_ub,
150 enum tree_code code, signop sign,
151 const wide_int &vr0_lb, const wide_int &vr0_ub,
152 const wide_int &vr1_lb, const wide_int &vr1_ub,
153 bool overflow_undefined)
154 {
155 wide_int cp1, cp2, cp3, cp4;
156
157 /* Compute the 4 cross operations, bailing if we get an overflow we
158 can't handle. */
159
160 if (!wide_int_binop_overflow (cp1, code, vr0_lb, vr1_lb, sign,
161 overflow_undefined))
162 return false;
163
164 if (wi::eq_p (vr0_lb, vr0_ub))
165 cp3 = cp1;
166 else if (!wide_int_binop_overflow (cp3, code, vr0_ub, vr1_lb, sign,
167 overflow_undefined))
168 return false;
169
170 if (wi::eq_p (vr1_lb, vr1_ub))
171 cp2 = cp1;
172 else if (!wide_int_binop_overflow (cp2, code, vr0_lb, vr1_ub, sign,
173 overflow_undefined))
174 return false;
175
176 if (wi::eq_p (vr0_lb, vr0_ub))
177 cp4 = cp2;
178 else if (!wide_int_binop_overflow (cp4, code, vr0_ub, vr1_ub, sign,
179 overflow_undefined))
180 return false;
181
182 wide_int_range_order_set (res_lb, res_ub, cp1, cp2, cp3, cp4, sign);
183 return true;
184 }
185
186 /* Multiply two ranges when TYPE_OVERFLOW_WRAPS:
187
188 [RES_LB, RES_UB] = [MIN0, MAX0] * [MIN1, MAX1]
189
190 This is basically fancy code so we don't drop to varying with an
191 unsigned [-3,-1]*[-3,-1].
192
193 Return TRUE if we were able to perform the operation. */
194
195 bool
196 wide_int_range_mult_wrapping (wide_int &res_lb,
197 wide_int &res_ub,
198 signop sign,
199 unsigned prec,
200 const wide_int &min0_,
201 const wide_int &max0_,
202 const wide_int &min1_,
203 const wide_int &max1_)
204 {
205 /* This test requires 2*prec bits if both operands are signed and
206 2*prec + 2 bits if either is not. Therefore, extend the values
207 using the sign of the result to PREC2. From here on out,
208 everthing is just signed math no matter what the input types
209 were. */
210 widest2_int min0 = widest2_int::from (min0_, sign);
211 widest2_int max0 = widest2_int::from (max0_, sign);
212 widest2_int min1 = widest2_int::from (min1_, sign);
213 widest2_int max1 = widest2_int::from (max1_, sign);
214 widest2_int sizem1 = wi::mask <widest2_int> (prec, false);
215 widest2_int size = sizem1 + 1;
216
217 /* Canonicalize the intervals. */
218 if (sign == UNSIGNED)
219 {
220 if (wi::ltu_p (size, min0 + max0))
221 {
222 min0 -= size;
223 max0 -= size;
224 }
225
226 if (wi::ltu_p (size, min1 + max1))
227 {
228 min1 -= size;
229 max1 -= size;
230 }
231 }
232
233 widest2_int prod0 = min0 * min1;
234 widest2_int prod1 = min0 * max1;
235 widest2_int prod2 = max0 * min1;
236 widest2_int prod3 = max0 * max1;
237
238 /* Sort the 4 products so that min is in prod0 and max is in
239 prod3. */
240 /* min0min1 > max0max1 */
241 if (prod0 > prod3)
242 std::swap (prod0, prod3);
243
244 /* min0max1 > max0min1 */
245 if (prod1 > prod2)
246 std::swap (prod1, prod2);
247
248 if (prod0 > prod1)
249 std::swap (prod0, prod1);
250
251 if (prod2 > prod3)
252 std::swap (prod2, prod3);
253
254 /* diff = max - min. */
255 prod2 = prod3 - prod0;
256 if (wi::geu_p (prod2, sizem1))
257 /* The range covers all values. */
258 return false;
259
260 res_lb = wide_int::from (prod0, prec, sign);
261 res_ub = wide_int::from (prod3, prec, sign);
262 return true;
263 }
264
265 /* Perform multiplicative operation CODE on two ranges:
266
267 [RES_LB, RES_UB] = [VR0_LB, VR0_UB] .CODE. [VR1_LB, VR1_LB]
268
269 Return TRUE if we were able to perform the operation.
270
271 NOTE: If code is MULT_EXPR and !TYPE_OVERFLOW_UNDEFINED, the resulting
272 range must be canonicalized by the caller because its components
273 may be swapped. */
274
275 bool
276 wide_int_range_multiplicative_op (wide_int &res_lb, wide_int &res_ub,
277 enum tree_code code,
278 signop sign,
279 unsigned prec,
280 const wide_int &vr0_lb,
281 const wide_int &vr0_ub,
282 const wide_int &vr1_lb,
283 const wide_int &vr1_ub,
284 bool overflow_undefined)
285 {
286 /* Multiplications, divisions and shifts are a bit tricky to handle,
287 depending on the mix of signs we have in the two ranges, we
288 need to operate on different values to get the minimum and
289 maximum values for the new range. One approach is to figure
290 out all the variations of range combinations and do the
291 operations.
292
293 However, this involves several calls to compare_values and it
294 is pretty convoluted. It's simpler to do the 4 operations
295 (MIN0 OP MIN1, MIN0 OP MAX1, MAX0 OP MIN1 and MAX0 OP MAX0 OP
296 MAX1) and then figure the smallest and largest values to form
297 the new range. */
298 if (code == MULT_EXPR && !overflow_undefined)
299 return wide_int_range_mult_wrapping (res_lb, res_ub,
300 sign, prec,
301 vr0_lb, vr0_ub, vr1_lb, vr1_ub);
302 return wide_int_range_cross_product (res_lb, res_ub,
303 code, sign,
304 vr0_lb, vr0_ub, vr1_lb, vr1_ub,
305 overflow_undefined);
306 }
307
308 /* Perform a left shift operation on two ranges:
309
310 [RES_LB, RES_UB] = [VR0_LB, VR0_UB] << [VR1_LB, VR1_LB]
311
312 Return TRUE if we were able to perform the operation.
313
314 NOTE: The resulting range must be canonicalized by the caller
315 because its contents components may be swapped. */
316
317 bool
318 wide_int_range_lshift (wide_int &res_lb, wide_int &res_ub,
319 signop sign, unsigned prec,
320 const wide_int &vr0_lb, const wide_int &vr0_ub,
321 const wide_int &vr1_lb, const wide_int &vr1_ub,
322 bool overflow_undefined)
323 {
324 /* Transform left shifts by constants into multiplies. */
325 if (wi::eq_p (vr1_lb, vr1_ub))
326 {
327 unsigned shift = vr1_ub.to_uhwi ();
328 wide_int tmp = wi::set_bit_in_zero (shift, prec);
329 return wide_int_range_multiplicative_op (res_lb, res_ub,
330 MULT_EXPR, sign, prec,
331 vr0_lb, vr0_ub, tmp, tmp,
332 /*overflow_undefined=*/false);
333 }
334
335 int overflow_pos = prec;
336 if (sign == SIGNED)
337 overflow_pos -= 1;
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
343 if-clause. */
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)
349 {
350 low_bound = bound;
351 high_bound = complement;
352 if (wi::ltu_p (vr0_ub, low_bound))
353 {
354 /* [5, 6] << [1, 2] == [10, 24]. */
355 /* We're shifting out only zeroes, the value increases
356 monotonically. */
357 in_bounds = true;
358 }
359 else if (wi::ltu_p (high_bound, vr0_lb))
360 {
361 /* [0xffffff00, 0xffffffff] << [1, 2]
362 == [0xfffffc00, 0xfffffffe]. */
363 /* We're shifting out only ones, the value decreases
364 monotonically. */
365 in_bounds = true;
366 }
367 }
368 else
369 {
370 /* [-1, 1] << [1, 2] == [-4, 4]. */
371 low_bound = complement;
372 high_bound = bound;
373 if (wi::lts_p (vr0_ub, high_bound)
374 && wi::lts_p (low_bound, vr0_lb))
375 {
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. */
380 in_bounds = true;
381 }
382 }
383 if (in_bounds)
384 return wide_int_range_multiplicative_op (res_lb, res_ub,
385 LSHIFT_EXPR, sign, prec,
386 vr0_lb, vr0_ub,
387 vr1_lb, vr1_ub,
388 overflow_undefined);
389 return false;
390 }
391
392 /* Return TRUE if a bit operation on two ranges can be easily
393 optimized in terms of a mask.
394
395 Basically, for BIT_AND_EXPR or BIT_IOR_EXPR see if we can optimize:
396
397 [LB, UB] op Z
398 into:
399 [LB op Z, UB op Z]
400
401 It is up to the caller to perform the actual folding above. */
402
403 static bool
404 wide_int_range_can_optimize_bit_op (tree_code code,
405 const wide_int &lb, const wide_int &ub,
406 const wide_int &mask)
407
408 {
409 if (code != BIT_AND_EXPR && code != BIT_IOR_EXPR)
410 return false;
411 /* If Z is a constant which (for op | its bitwise not) has n
412 consecutive least significant bits cleared followed by m 1
413 consecutive bits set immediately above it and either
414 m + n == precision, or (x >> (m + n)) == (y >> (m + n)).
415
416 The least significant n bits of all the values in the range are
417 cleared or set, the m bits above it are preserved and any bits
418 above these are required to be the same for all values in the
419 range. */
420
421 wide_int w = mask;
422 int m = 0, n = 0;
423 if (code == BIT_IOR_EXPR)
424 w = ~w;
425 if (wi::eq_p (w, 0))
426 n = w.get_precision ();
427 else
428 {
429 n = wi::ctz (w);
430 w = ~(w | wi::mask (n, false, w.get_precision ()));
431 if (wi::eq_p (w, 0))
432 m = w.get_precision () - n;
433 else
434 m = wi::ctz (w) - n;
435 }
436 wide_int new_mask = wi::mask (m + n, true, w.get_precision ());
437 if ((new_mask & lb) == (new_mask & ub))
438 return true;
439
440 return false;
441 }
442
443 /* Helper function for wide_int_range_optimize_bit_op.
444
445 Calculates bounds and mask for a pair of ranges. The mask is the
446 singleton range among the ranges, if any. The bounds are the
447 bounds for the remaining range. */
448
449 bool
450 wide_int_range_get_mask_and_bounds (wide_int &mask,
451 wide_int &lower_bound,
452 wide_int &upper_bound,
453 const wide_int &vr0_min,
454 const wide_int &vr0_max,
455 const wide_int &vr1_min,
456 const wide_int &vr1_max)
457 {
458 if (wi::eq_p (vr1_min, vr1_max))
459 {
460 mask = vr1_min;
461 lower_bound = vr0_min;
462 upper_bound = vr0_max;
463 return true;
464 }
465 else if (wi::eq_p (vr0_min, vr0_max))
466 {
467 mask = vr0_min;
468 lower_bound = vr1_min;
469 upper_bound = vr1_max;
470 return true;
471 }
472 return false;
473 }
474
475 /* Optimize a bit operation (BIT_AND_EXPR or BIT_IOR_EXPR) if
476 possible. If so, return TRUE and store the result in
477 [RES_LB, RES_UB]. */
478
479 bool
480 wide_int_range_optimize_bit_op (wide_int &res_lb, wide_int &res_ub,
481 enum tree_code code,
482 signop sign,
483 const wide_int &vr0_min,
484 const wide_int &vr0_max,
485 const wide_int &vr1_min,
486 const wide_int &vr1_max)
487 {
488 gcc_assert (code == BIT_AND_EXPR || code == BIT_IOR_EXPR);
489
490 wide_int lower_bound, upper_bound, mask;
491 if (!wide_int_range_get_mask_and_bounds (mask, lower_bound, upper_bound,
492 vr0_min, vr0_max, vr1_min, vr1_max))
493 return false;
494 if (wide_int_range_can_optimize_bit_op (code,
495 lower_bound, upper_bound, mask))
496 {
497 wi::overflow_type ovf;
498 wide_int_binop (res_lb, code, lower_bound, mask, sign, &ovf);
499 wide_int_binop (res_ub, code, upper_bound, mask, sign, &ovf);
500 return true;
501 }
502 return false;
503 }
504
505 /* Calculate the XOR of two ranges and store the result in [WMIN,WMAX].
506 The two input ranges are described by their MUST_BE_NONZERO and
507 MAY_BE_NONZERO bit masks.
508
509 Return TRUE if we were able to successfully calculate the new range. */
510
511 bool
512 wide_int_range_bit_xor (wide_int &wmin, wide_int &wmax,
513 signop sign,
514 unsigned prec,
515 const wide_int &must_be_nonzero0,
516 const wide_int &may_be_nonzero0,
517 const wide_int &must_be_nonzero1,
518 const wide_int &may_be_nonzero1)
519 {
520 wide_int result_zero_bits = ((must_be_nonzero0 & must_be_nonzero1)
521 | ~(may_be_nonzero0 | may_be_nonzero1));
522 wide_int result_one_bits
523 = (wi::bit_and_not (must_be_nonzero0, may_be_nonzero1)
524 | wi::bit_and_not (must_be_nonzero1, may_be_nonzero0));
525 wmax = ~result_zero_bits;
526 wmin = result_one_bits;
527 /* If the range has all positive or all negative values, the result
528 is better than VARYING. */
529 if (wi::lt_p (wmin, 0, sign) || wi::ge_p (wmax, 0, sign))
530 return true;
531 wmin = wi::min_value (prec, sign);
532 wmax = wi::max_value (prec, sign);
533 return false;
534 }
535
536 /* Calculate the IOR of two ranges and store the result in [WMIN,WMAX].
537 Return TRUE if we were able to successfully calculate the new range. */
538
539 bool
540 wide_int_range_bit_ior (wide_int &wmin, wide_int &wmax,
541 signop sign,
542 const wide_int &vr0_min,
543 const wide_int &vr0_max,
544 const wide_int &vr1_min,
545 const wide_int &vr1_max,
546 const wide_int &must_be_nonzero0,
547 const wide_int &may_be_nonzero0,
548 const wide_int &must_be_nonzero1,
549 const wide_int &may_be_nonzero1)
550 {
551 if (wide_int_range_optimize_bit_op (wmin, wmax, BIT_IOR_EXPR, sign,
552 vr0_min, vr0_max,
553 vr1_min, vr1_max))
554 return true;
555 wmin = must_be_nonzero0 | must_be_nonzero1;
556 wmax = may_be_nonzero0 | may_be_nonzero1;
557 /* If the input ranges contain only positive values we can
558 truncate the minimum of the result range to the maximum
559 of the input range minima. */
560 if (wi::ge_p (vr0_min, 0, sign)
561 && wi::ge_p (vr1_min, 0, sign))
562 {
563 wmin = wi::max (wmin, vr0_min, sign);
564 wmin = wi::max (wmin, vr1_min, sign);
565 }
566 /* If either input range contains only negative values
567 we can truncate the minimum of the result range to the
568 respective minimum range. */
569 if (wi::lt_p (vr0_max, 0, sign))
570 wmin = wi::max (wmin, vr0_min, sign);
571 if (wi::lt_p (vr1_max, 0, sign))
572 wmin = wi::max (wmin, vr1_min, sign);
573 /* If the limits got swapped around, indicate error so we can adjust
574 the range to VARYING. */
575 if (wi::gt_p (wmin, wmax,sign))
576 return false;
577 return true;
578 }
579
580 /* Calculate the bitwise AND of two ranges and store the result in [WMIN,WMAX].
581 Return TRUE if we were able to successfully calculate the new range. */
582
583 bool
584 wide_int_range_bit_and (wide_int &wmin, wide_int &wmax,
585 signop sign,
586 unsigned prec,
587 const wide_int &vr0_min,
588 const wide_int &vr0_max,
589 const wide_int &vr1_min,
590 const wide_int &vr1_max,
591 const wide_int &must_be_nonzero0,
592 const wide_int &may_be_nonzero0,
593 const wide_int &must_be_nonzero1,
594 const wide_int &may_be_nonzero1)
595 {
596 if (wide_int_range_optimize_bit_op (wmin, wmax, BIT_AND_EXPR, sign,
597 vr0_min, vr0_max,
598 vr1_min, vr1_max))
599 return true;
600 wmin = must_be_nonzero0 & must_be_nonzero1;
601 wmax = may_be_nonzero0 & may_be_nonzero1;
602 /* If both input ranges contain only negative values we can
603 truncate the result range maximum to the minimum of the
604 input range maxima. */
605 if (wi::lt_p (vr0_max, 0, sign) && wi::lt_p (vr1_max, 0, sign))
606 {
607 wmax = wi::min (wmax, vr0_max, sign);
608 wmax = wi::min (wmax, vr1_max, sign);
609 }
610 /* If either input range contains only non-negative values
611 we can truncate the result range maximum to the respective
612 maximum of the input range. */
613 if (wi::ge_p (vr0_min, 0, sign))
614 wmax = wi::min (wmax, vr0_max, sign);
615 if (wi::ge_p (vr1_min, 0, sign))
616 wmax = wi::min (wmax, vr1_max, sign);
617 /* PR68217: In case of signed & sign-bit-CST should
618 result in [-INF, 0] instead of [-INF, INF]. */
619 if (wi::gt_p (wmin, wmax, sign))
620 {
621 wide_int sign_bit = wi::set_bit_in_zero (prec - 1, prec);
622 if (sign == SIGNED
623 && ((wi::eq_p (vr0_min, vr0_max)
624 && !wi::cmps (vr0_min, sign_bit))
625 || (wi::eq_p (vr1_min, vr1_max)
626 && !wi::cmps (vr1_min, sign_bit))))
627 {
628 wmin = wi::min_value (prec, sign);
629 wmax = wi::zero (prec);
630 }
631 }
632 /* If the limits got swapped around, indicate error so we can adjust
633 the range to VARYING. */
634 if (wi::gt_p (wmin, wmax,sign))
635 return false;
636 return true;
637 }
638
639 /* Calculate TRUNC_MOD_EXPR on two ranges and store the result in
640 [WMIN,WMAX]. */
641
642 void
643 wide_int_range_trunc_mod (wide_int &wmin, wide_int &wmax,
644 signop sign,
645 unsigned prec,
646 const wide_int &vr0_min,
647 const wide_int &vr0_max,
648 const wide_int &vr1_min,
649 const wide_int &vr1_max)
650 {
651 wide_int tmp;
652
653 /* ABS (A % B) < ABS (B) and either
654 0 <= A % B <= A or A <= A % B <= 0. */
655 wmax = vr1_max - 1;
656 if (sign == SIGNED)
657 {
658 tmp = -1 - vr1_min;
659 wmax = wi::smax (wmax, tmp);
660 }
661
662 if (sign == UNSIGNED)
663 wmin = wi::zero (prec);
664 else
665 {
666 wmin = -wmax;
667 tmp = vr0_min;
668 if (wi::gts_p (tmp, 0))
669 tmp = wi::zero (prec);
670 wmin = wi::smax (wmin, tmp);
671 }
672 tmp = vr0_max;
673 if (sign == SIGNED && wi::neg_p (tmp))
674 tmp = wi::zero (prec);
675 wmax = wi::min (wmax, tmp, sign);
676 }
677
678 /* Calculate ABS_EXPR on a range and store the result in [MIN, MAX]. */
679
680 bool
681 wide_int_range_abs (wide_int &min, wide_int &max,
682 signop sign, unsigned prec,
683 const wide_int &vr0_min, const wide_int &vr0_max,
684 bool overflow_undefined)
685 {
686 /* Pass through VR0 the easy cases. */
687 if (sign == UNSIGNED || wi::ge_p (vr0_min, 0, sign))
688 {
689 min = vr0_min;
690 max = vr0_max;
691 return true;
692 }
693
694 /* -TYPE_MIN_VALUE = TYPE_MIN_VALUE with flag_wrapv so we can't get a
695 useful range. */
696 wide_int min_value = wi::min_value (prec, sign);
697 wide_int max_value = wi::max_value (prec, sign);
698 if (!overflow_undefined && wi::eq_p (vr0_min, min_value))
699 return false;
700
701 /* ABS_EXPR may flip the range around, if the original range
702 included negative values. */
703 if (wi::eq_p (vr0_min, min_value))
704 min = max_value;
705 else
706 min = wi::abs (vr0_min);
707 if (wi::eq_p (vr0_max, min_value))
708 max = max_value;
709 else
710 max = wi::abs (vr0_max);
711
712 /* If the range contains zero then we know that the minimum value in the
713 range will be zero. */
714 if (wi::le_p (vr0_min, 0, sign) && wi::ge_p (vr0_max, 0, sign))
715 {
716 if (wi::gt_p (min, max, sign))
717 max = min;
718 min = wi::zero (prec);
719 }
720 else
721 {
722 /* If the range was reversed, swap MIN and MAX. */
723 if (wi::gt_p (min, max, sign))
724 std::swap (min, max);
725 }
726
727 /* If the new range has its limits swapped around (MIN > MAX), then
728 the operation caused one of them to wrap around. The only thing
729 we know is that the result is positive. */
730 if (wi::gt_p (min, max, sign))
731 {
732 min = wi::zero (prec);
733 max = max_value;
734 }
735 return true;
736 }
737
738 /* Convert range in [VR0_MIN, VR0_MAX] with INNER_SIGN and INNER_PREC,
739 to a range in [MIN, MAX] with OUTER_SIGN and OUTER_PREC.
740
741 Return TRUE if we were able to successfully calculate the new range.
742
743 Caller is responsible for canonicalizing the resulting range. */
744
745 bool
746 wide_int_range_convert (wide_int &min, wide_int &max,
747 signop inner_sign,
748 unsigned inner_prec,
749 signop outer_sign,
750 unsigned outer_prec,
751 const wide_int &vr0_min,
752 const wide_int &vr0_max)
753 {
754 /* If the conversion is not truncating we can convert the min and
755 max values and canonicalize the resulting range. Otherwise we
756 can do the conversion if the size of the range is less than what
757 the precision of the target type can represent. */
758 if (outer_prec >= inner_prec
759 || wi::rshift (wi::sub (vr0_max, vr0_min),
760 wi::uhwi (outer_prec, inner_prec),
761 inner_sign) == 0)
762 {
763 min = wide_int::from (vr0_min, outer_prec, inner_sign);
764 max = wide_int::from (vr0_max, outer_prec, inner_sign);
765 return (!wi::eq_p (min, wi::min_value (outer_prec, outer_sign))
766 || !wi::eq_p (max, wi::max_value (outer_prec, outer_sign)));
767 }
768 return false;
769 }
770
771 /* Calculate a division operation on two ranges and store the result in
772 [WMIN, WMAX] U [EXTRA_MIN, EXTRA_MAX].
773
774 If EXTRA_RANGE_P is set upon return, EXTRA_MIN/EXTRA_MAX hold
775 meaningful information, otherwise they should be ignored.
776
777 Return TRUE if we were able to successfully calculate the new range. */
778
779 bool
780 wide_int_range_div (wide_int &wmin, wide_int &wmax,
781 tree_code code, signop sign, unsigned prec,
782 const wide_int &dividend_min, const wide_int &dividend_max,
783 const wide_int &divisor_min, const wide_int &divisor_max,
784 bool overflow_undefined,
785 bool &extra_range_p,
786 wide_int &extra_min, wide_int &extra_max)
787 {
788 extra_range_p = false;
789
790 /* If we know we won't divide by zero, just do the division. */
791 if (!wide_int_range_includes_zero_p (divisor_min, divisor_max, sign))
792 return wide_int_range_multiplicative_op (wmin, wmax, code, sign, prec,
793 dividend_min, dividend_max,
794 divisor_min, divisor_max,
795 overflow_undefined);
796
797 /* If flag_non_call_exceptions, we must not eliminate a division
798 by zero. */
799 if (cfun->can_throw_non_call_exceptions)
800 return false;
801
802 /* If we're definitely dividing by zero, there's nothing to do. */
803 if (wide_int_range_zero_p (divisor_min, divisor_max, prec))
804 return false;
805
806 /* Perform the division in 2 parts, [LB, -1] and [1, UB],
807 which will skip any division by zero.
808
809 First divide by the negative numbers, if any. */
810 if (wi::neg_p (divisor_min, sign))
811 {
812 if (!wide_int_range_multiplicative_op (wmin, wmax,
813 code, sign, prec,
814 dividend_min, dividend_max,
815 divisor_min, wi::minus_one (prec),
816 overflow_undefined))
817 return false;
818 extra_range_p = true;
819 }
820 /* Then divide by the non-zero positive numbers, if any. */
821 if (wi::gt_p (divisor_max, wi::zero (prec), sign))
822 {
823 if (!wide_int_range_multiplicative_op (extra_range_p ? extra_min : wmin,
824 extra_range_p ? extra_max : wmax,
825 code, sign, prec,
826 dividend_min, dividend_max,
827 wi::one (prec), divisor_max,
828 overflow_undefined))
829 return false;
830 }
831 else
832 extra_range_p = false;
833 return true;
834 }