|
131
|
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 ÷nd_min, const wide_int ÷nd_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 }
|
