]>
Commit | Line | Data |
---|---|---|
cca78449 | 1 | /* Support routines for value ranges. |
7adcbafe | 2 | Copyright (C) 2019-2022 Free Software Foundation, Inc. |
4ba9fb0a AH |
3 | Major hacks by Aldy Hernandez <aldyh@redhat.com> and |
4 | Andrew MacLeod <amacleod@redhat.com>. | |
cca78449 AH |
5 | |
6 | This file is part of GCC. | |
7 | ||
8 | GCC is free software; you can redistribute it and/or modify | |
9 | it under the terms of the GNU General Public License as published by | |
10 | the Free Software Foundation; either version 3, or (at your option) | |
11 | any later version. | |
12 | ||
13 | GCC is distributed in the hope that it will be useful, | |
14 | but WITHOUT ANY WARRANTY; without even the implied warranty of | |
15 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
16 | GNU General Public License for more details. | |
17 | ||
18 | You should have received a copy of the GNU General Public License | |
19 | along with GCC; see the file COPYING3. If not see | |
20 | <http://www.gnu.org/licenses/>. */ | |
21 | ||
22 | #include "config.h" | |
23 | #include "system.h" | |
24 | #include "coretypes.h" | |
25 | #include "backend.h" | |
26 | #include "tree.h" | |
27 | #include "gimple.h" | |
28 | #include "ssa.h" | |
29 | #include "tree-pretty-print.h" | |
64864aa9 | 30 | #include "value-range-pretty-print.h" |
cca78449 | 31 | #include "fold-const.h" |
ca8cc827 | 32 | #include "gimple-range.h" |
cca78449 | 33 | |
91a7f306 AH |
34 | void |
35 | irange::accept (const vrange_visitor &v) const | |
36 | { | |
37 | v.visit (*this); | |
38 | } | |
39 | ||
40 | void | |
41 | unsupported_range::accept (const vrange_visitor &v) const | |
42 | { | |
43 | v.visit (*this); | |
44 | } | |
45 | ||
59c8e96d AH |
46 | // Convenience function only available for integers and pointers. |
47 | ||
48 | wide_int | |
49 | Value_Range::lower_bound () const | |
50 | { | |
51 | if (is_a <irange> (*m_vrange)) | |
52 | return as_a <irange> (*m_vrange).lower_bound (); | |
53 | gcc_unreachable (); | |
54 | } | |
55 | ||
56 | // Convenience function only available for integers and pointers. | |
57 | ||
58 | wide_int | |
59 | Value_Range::upper_bound () const | |
60 | { | |
61 | if (is_a <irange> (*m_vrange)) | |
62 | return as_a <irange> (*m_vrange).upper_bound (); | |
63 | gcc_unreachable (); | |
64 | } | |
65 | ||
66 | void | |
67 | Value_Range::dump (FILE *out) const | |
68 | { | |
69 | if (m_vrange) | |
70 | m_vrange->dump (out); | |
71 | else | |
72 | fprintf (out, "NULL"); | |
73 | } | |
74 | ||
75 | DEBUG_FUNCTION void | |
76 | debug (const Value_Range &r) | |
77 | { | |
78 | r.dump (stderr); | |
79 | fprintf (stderr, "\n"); | |
80 | } | |
81 | ||
89b0276d | 82 | // Default vrange definitions. |
4f1bce19 AH |
83 | |
84 | bool | |
85 | vrange::contains_p (tree) const | |
86 | { | |
89b0276d | 87 | return varying_p (); |
4f1bce19 AH |
88 | } |
89 | ||
4f1bce19 AH |
90 | bool |
91 | vrange::singleton_p (tree *) const | |
92 | { | |
93 | return false; | |
94 | } | |
95 | ||
89b0276d AH |
96 | void |
97 | vrange::set (tree, tree, value_range_kind) | |
4f1bce19 | 98 | { |
4f1bce19 AH |
99 | } |
100 | ||
89b0276d AH |
101 | tree |
102 | vrange::type () const | |
4f1bce19 | 103 | { |
89b0276d | 104 | return void_type_node; |
4f1bce19 AH |
105 | } |
106 | ||
a9058b08 | 107 | bool |
89b0276d | 108 | vrange::supports_type_p (tree) const |
a9058b08 | 109 | { |
89b0276d | 110 | return false; |
a9058b08 AH |
111 | } |
112 | ||
89b0276d AH |
113 | void |
114 | vrange::set_undefined () | |
4f1bce19 | 115 | { |
89b0276d | 116 | m_kind = VR_UNDEFINED; |
4f1bce19 AH |
117 | } |
118 | ||
119 | void | |
89b0276d | 120 | vrange::set_varying (tree) |
4f1bce19 | 121 | { |
89b0276d | 122 | m_kind = VR_VARYING; |
4f1bce19 AH |
123 | } |
124 | ||
89b0276d AH |
125 | bool |
126 | vrange::union_ (const vrange &r) | |
4f1bce19 | 127 | { |
89b0276d AH |
128 | if (r.undefined_p () || varying_p ()) |
129 | return false; | |
130 | if (undefined_p () || r.varying_p ()) | |
131 | { | |
132 | operator= (r); | |
133 | return true; | |
134 | } | |
135 | gcc_unreachable (); | |
136 | return false; | |
4f1bce19 AH |
137 | } |
138 | ||
89b0276d AH |
139 | bool |
140 | vrange::intersect (const vrange &r) | |
4f1bce19 | 141 | { |
89b0276d AH |
142 | if (undefined_p () || r.varying_p ()) |
143 | return false; | |
144 | if (r.undefined_p ()) | |
145 | { | |
146 | set_undefined (); | |
147 | return true; | |
148 | } | |
149 | if (varying_p ()) | |
150 | { | |
151 | operator= (r); | |
152 | return true; | |
153 | } | |
4f1bce19 | 154 | gcc_unreachable (); |
89b0276d | 155 | return false; |
4f1bce19 AH |
156 | } |
157 | ||
89b0276d AH |
158 | bool |
159 | vrange::zero_p () const | |
4f1bce19 | 160 | { |
89b0276d | 161 | return false; |
4f1bce19 AH |
162 | } |
163 | ||
a9058b08 | 164 | bool |
89b0276d | 165 | vrange::nonzero_p () const |
a9058b08 AH |
166 | { |
167 | return false; | |
168 | } | |
169 | ||
4f1bce19 | 170 | void |
89b0276d | 171 | vrange::set_nonzero (tree) |
4f1bce19 | 172 | { |
4f1bce19 AH |
173 | } |
174 | ||
175 | void | |
89b0276d | 176 | vrange::set_zero (tree) |
4f1bce19 | 177 | { |
4f1bce19 AH |
178 | } |
179 | ||
180 | void | |
89b0276d | 181 | vrange::set_nonnegative (tree) |
4f1bce19 | 182 | { |
4f1bce19 AH |
183 | } |
184 | ||
185 | bool | |
89b0276d | 186 | vrange::fits_p (const vrange &) const |
4f1bce19 | 187 | { |
89b0276d | 188 | return true; |
4f1bce19 AH |
189 | } |
190 | ||
89b0276d AH |
191 | // Assignment operator for generic ranges. Copying incompatible types |
192 | // is not allowed. | |
193 | ||
194 | vrange & | |
195 | vrange::operator= (const vrange &src) | |
4f1bce19 | 196 | { |
89b0276d AH |
197 | if (is_a <irange> (src)) |
198 | { | |
199 | as_a <irange> (*this) = as_a <irange> (src); | |
200 | return *this; | |
201 | } | |
202 | else | |
203 | gcc_unreachable (); | |
4f1bce19 AH |
204 | } |
205 | ||
89b0276d AH |
206 | // Equality operator for generic ranges. |
207 | ||
4f1bce19 | 208 | bool |
89b0276d | 209 | vrange::operator== (const vrange &src) const |
4f1bce19 | 210 | { |
89b0276d AH |
211 | if (is_a <irange> (src)) |
212 | return as_a <irange> (*this) == as_a <irange> (src); | |
4f1bce19 | 213 | gcc_unreachable (); |
4f1bce19 AH |
214 | } |
215 | ||
64864aa9 AH |
216 | // Wrapper for vrange_printer to dump a range to a file. |
217 | ||
218 | void | |
219 | vrange::dump (FILE *file) const | |
220 | { | |
221 | pretty_printer buffer; | |
222 | pp_needs_newline (&buffer) = true; | |
223 | buffer.buffer->stream = file; | |
224 | vrange_printer vrange_pp (&buffer); | |
225 | this->accept (vrange_pp); | |
226 | pp_flush (&buffer); | |
227 | } | |
228 | ||
4f1bce19 | 229 | bool |
89b0276d | 230 | irange::supports_type_p (tree type) const |
4f1bce19 | 231 | { |
89b0276d | 232 | return supports_p (type); |
4f1bce19 AH |
233 | } |
234 | ||
89b0276d AH |
235 | // Return TRUE if R fits in THIS. |
236 | ||
237 | bool | |
238 | irange::fits_p (const vrange &r) const | |
4f1bce19 | 239 | { |
89b0276d | 240 | return m_max_ranges >= as_a <irange> (r).num_pairs (); |
4f1bce19 AH |
241 | } |
242 | ||
243 | void | |
89b0276d | 244 | irange::set_nonnegative (tree type) |
4f1bce19 | 245 | { |
89b0276d | 246 | set (build_int_cst (type, 0), TYPE_MAX_VALUE (type)); |
4f1bce19 AH |
247 | } |
248 | ||
89b0276d | 249 | unsupported_range::unsupported_range () |
4f1bce19 | 250 | { |
89b0276d AH |
251 | m_discriminator = VR_UNKNOWN; |
252 | set_undefined (); | |
4f1bce19 AH |
253 | } |
254 | ||
4ba9fb0a AH |
255 | // Here we copy between any two irange's. The ranges can be legacy or |
256 | // multi-ranges, and copying between any combination works correctly. | |
257 | ||
258 | irange & | |
259 | irange::operator= (const irange &src) | |
260 | { | |
5bcd7de6 | 261 | if (legacy_mode_p ()) |
4ba9fb0a | 262 | { |
5bcd7de6 | 263 | copy_to_legacy (src); |
4ba9fb0a AH |
264 | return *this; |
265 | } | |
5bcd7de6 | 266 | if (src.legacy_mode_p ()) |
4ba9fb0a | 267 | { |
5bcd7de6 | 268 | copy_legacy_to_multi_range (src); |
4ba9fb0a AH |
269 | return *this; |
270 | } | |
271 | ||
272 | unsigned x; | |
273 | unsigned lim = src.m_num_ranges; | |
274 | if (lim > m_max_ranges) | |
275 | lim = m_max_ranges; | |
276 | ||
277 | for (x = 0; x < lim * 2; ++x) | |
278 | m_base[x] = src.m_base[x]; | |
279 | ||
280 | // If the range didn't fit, the last range should cover the rest. | |
281 | if (lim != src.m_num_ranges) | |
282 | m_base[x - 1] = src.m_base[src.m_num_ranges * 2 - 1]; | |
283 | ||
284 | m_num_ranges = lim; | |
dc80d5e8 | 285 | m_kind = src.m_kind; |
4e82205b | 286 | m_nonzero_mask = src.m_nonzero_mask; |
c106825b AH |
287 | if (flag_checking) |
288 | verify_range (); | |
4ba9fb0a AH |
289 | return *this; |
290 | } | |
291 | ||
292 | // Return TRUE if range is a multi-range that can be represented as a | |
293 | // VR_ANTI_RANGE. | |
294 | ||
295 | bool | |
296 | irange::maybe_anti_range () const | |
cca78449 | 297 | { |
4ba9fb0a AH |
298 | tree ttype = type (); |
299 | unsigned int precision = TYPE_PRECISION (ttype); | |
300 | signop sign = TYPE_SIGN (ttype); | |
301 | return (num_pairs () > 1 | |
302 | && precision > 1 | |
303 | && lower_bound () == wi::min_value (precision, sign) | |
304 | && upper_bound () == wi::max_value (precision, sign)); | |
cca78449 AH |
305 | } |
306 | ||
4ba9fb0a | 307 | void |
5bcd7de6 | 308 | irange::copy_legacy_to_multi_range (const irange &src) |
cca78449 | 309 | { |
5bcd7de6 AH |
310 | gcc_checking_assert (src.legacy_mode_p ()); |
311 | gcc_checking_assert (!legacy_mode_p ()); | |
4ba9fb0a AH |
312 | if (src.undefined_p ()) |
313 | set_undefined (); | |
314 | else if (src.varying_p ()) | |
315 | set_varying (src.type ()); | |
4ba9fb0a | 316 | else |
80cbca32 | 317 | { |
5bcd7de6 AH |
318 | if (range_has_numeric_bounds_p (&src)) |
319 | set (src.min (), src.max (), src.kind ()); | |
320 | else | |
80cbca32 AH |
321 | { |
322 | value_range cst (src); | |
323 | cst.normalize_symbolics (); | |
5bcd7de6 | 324 | gcc_checking_assert (cst.varying_p () || cst.kind () == VR_RANGE); |
80cbca32 | 325 | set (cst.min (), cst.max ()); |
80cbca32 | 326 | } |
80cbca32 | 327 | } |
cca78449 AH |
328 | } |
329 | ||
5bcd7de6 AH |
330 | // Copy any type of irange into a legacy. |
331 | ||
332 | void | |
333 | irange::copy_to_legacy (const irange &src) | |
334 | { | |
335 | gcc_checking_assert (legacy_mode_p ()); | |
dc80d5e8 AH |
336 | // Handle legacy to legacy and other things that are easy to copy. |
337 | if (src.legacy_mode_p () || src.varying_p () || src.undefined_p ()) | |
5bcd7de6 AH |
338 | { |
339 | m_num_ranges = src.m_num_ranges; | |
340 | m_base[0] = src.m_base[0]; | |
341 | m_base[1] = src.m_base[1]; | |
342 | m_kind = src.m_kind; | |
554b21ed | 343 | m_nonzero_mask = src.m_nonzero_mask; |
5bcd7de6 AH |
344 | return; |
345 | } | |
346 | // Copy multi-range to legacy. | |
dc80d5e8 | 347 | if (src.maybe_anti_range ()) |
5bcd7de6 AH |
348 | { |
349 | int_range<3> r (src); | |
350 | r.invert (); | |
351 | // Use tree variants to save on tree -> wi -> tree conversions. | |
352 | set (r.tree_lower_bound (0), r.tree_upper_bound (0), VR_ANTI_RANGE); | |
353 | } | |
354 | else | |
355 | set (src.tree_lower_bound (), src.tree_upper_bound ()); | |
356 | } | |
357 | ||
4e85ad79 | 358 | // Swap MIN/MAX if they are out of order and adjust KIND appropriately. |
4ba9fb0a | 359 | |
4e85ad79 AH |
360 | static void |
361 | swap_out_of_order_endpoints (tree &min, tree &max, value_range_kind &kind) | |
cca78449 | 362 | { |
4e85ad79 AH |
363 | gcc_checking_assert (kind != VR_UNDEFINED); |
364 | if (kind == VR_VARYING) | |
365 | return; | |
4ba9fb0a AH |
366 | /* Wrong order for min and max, to swap them and the VR type we need |
367 | to adjust them. */ | |
368 | if (tree_int_cst_lt (max, min)) | |
369 | { | |
370 | tree one, tmp; | |
371 | ||
372 | /* For one bit precision if max < min, then the swapped | |
373 | range covers all values, so for VR_RANGE it is varying and | |
374 | for VR_ANTI_RANGE empty range, so drop to varying as well. */ | |
375 | if (TYPE_PRECISION (TREE_TYPE (min)) == 1) | |
376 | { | |
4e85ad79 AH |
377 | kind = VR_VARYING; |
378 | return; | |
4ba9fb0a AH |
379 | } |
380 | ||
381 | one = build_int_cst (TREE_TYPE (min), 1); | |
382 | tmp = int_const_binop (PLUS_EXPR, max, one); | |
383 | max = int_const_binop (MINUS_EXPR, min, one); | |
384 | min = tmp; | |
385 | ||
386 | /* There's one corner case, if we had [C+1, C] before we now have | |
387 | that again. But this represents an empty value range, so drop | |
388 | to varying in this case. */ | |
389 | if (tree_int_cst_lt (max, min)) | |
390 | { | |
4e85ad79 AH |
391 | kind = VR_VARYING; |
392 | return; | |
4ba9fb0a AH |
393 | } |
394 | kind = kind == VR_RANGE ? VR_ANTI_RANGE : VR_RANGE; | |
395 | } | |
cca78449 AH |
396 | } |
397 | ||
398 | void | |
4ba9fb0a | 399 | irange::irange_set (tree min, tree max) |
cca78449 | 400 | { |
4ba9fb0a AH |
401 | gcc_checking_assert (!POLY_INT_CST_P (min)); |
402 | gcc_checking_assert (!POLY_INT_CST_P (max)); | |
403 | ||
404 | m_base[0] = min; | |
405 | m_base[1] = max; | |
406 | m_num_ranges = 1; | |
dc80d5e8 | 407 | m_kind = VR_RANGE; |
4e82205b | 408 | m_nonzero_mask = NULL; |
c106825b | 409 | normalize_kind (); |
dc80d5e8 | 410 | |
4ba9fb0a AH |
411 | if (flag_checking) |
412 | verify_range (); | |
cca78449 AH |
413 | } |
414 | ||
88081d38 AH |
415 | void |
416 | irange::irange_set_1bit_anti_range (tree min, tree max) | |
417 | { | |
418 | tree type = TREE_TYPE (min); | |
419 | gcc_checking_assert (TYPE_PRECISION (type) == 1); | |
420 | ||
421 | if (operand_equal_p (min, max)) | |
422 | { | |
423 | // Since these are 1-bit quantities, they can only be [MIN,MIN] | |
424 | // or [MAX,MAX]. | |
425 | if (vrp_val_is_min (min)) | |
426 | min = max = vrp_val_max (type); | |
427 | else | |
428 | min = max = vrp_val_min (type); | |
429 | set (min, max); | |
430 | } | |
431 | else | |
432 | { | |
433 | // The only alternative is [MIN,MAX], which is the empty range. | |
e6455a09 AH |
434 | gcc_checking_assert (vrp_val_is_min (min)); |
435 | gcc_checking_assert (vrp_val_is_max (max)); | |
88081d38 AH |
436 | set_undefined (); |
437 | } | |
438 | if (flag_checking) | |
439 | verify_range (); | |
440 | } | |
441 | ||
cca78449 | 442 | void |
4ba9fb0a | 443 | irange::irange_set_anti_range (tree min, tree max) |
cca78449 | 444 | { |
4ba9fb0a AH |
445 | gcc_checking_assert (!POLY_INT_CST_P (min)); |
446 | gcc_checking_assert (!POLY_INT_CST_P (max)); | |
447 | ||
88081d38 AH |
448 | if (TYPE_PRECISION (TREE_TYPE (min)) == 1) |
449 | { | |
450 | irange_set_1bit_anti_range (min, max); | |
451 | return; | |
452 | } | |
453 | ||
4ba9fb0a AH |
454 | // set an anti-range |
455 | tree type = TREE_TYPE (min); | |
456 | signop sign = TYPE_SIGN (type); | |
457 | int_range<2> type_range (type); | |
458 | // Calculate INVERSE([I,J]) as [-MIN, I-1][J+1, +MAX]. | |
459 | m_num_ranges = 0; | |
460 | wi::overflow_type ovf; | |
461 | ||
462 | wide_int w_min = wi::to_wide (min); | |
463 | if (wi::ne_p (w_min, type_range.lower_bound ())) | |
cca78449 | 464 | { |
4ba9fb0a AH |
465 | wide_int lim1 = wi::sub (w_min, 1, sign, &ovf); |
466 | gcc_checking_assert (ovf != wi::OVF_OVERFLOW); | |
467 | m_base[0] = type_range.tree_lower_bound (0); | |
468 | m_base[1] = wide_int_to_tree (type, lim1); | |
469 | m_num_ranges = 1; | |
cca78449 | 470 | } |
4ba9fb0a AH |
471 | wide_int w_max = wi::to_wide (max); |
472 | if (wi::ne_p (w_max, type_range.upper_bound ())) | |
473 | { | |
474 | wide_int lim2 = wi::add (w_max, 1, sign, &ovf); | |
475 | gcc_checking_assert (ovf != wi::OVF_OVERFLOW); | |
476 | m_base[m_num_ranges * 2] = wide_int_to_tree (type, lim2); | |
477 | m_base[m_num_ranges * 2 + 1] = type_range.tree_upper_bound (0); | |
478 | ++m_num_ranges; | |
479 | } | |
dc80d5e8 AH |
480 | |
481 | m_kind = VR_RANGE; | |
4e82205b | 482 | m_nonzero_mask = NULL; |
c106825b | 483 | normalize_kind (); |
dc80d5e8 | 484 | |
4ba9fb0a AH |
485 | if (flag_checking) |
486 | verify_range (); | |
cca78449 AH |
487 | } |
488 | ||
489 | /* Set value range to the canonical form of {VRTYPE, MIN, MAX, EQUIV}. | |
490 | This means adjusting VRTYPE, MIN and MAX representing the case of a | |
491 | wrapping range with MAX < MIN covering [MIN, type_max] U [type_min, MAX] | |
492 | as anti-rage ~[MAX+1, MIN-1]. Likewise for wrapping anti-ranges. | |
493 | In corner cases where MAX+1 or MIN-1 wraps this will fall back | |
494 | to varying. | |
495 | This routine exists to ease canonicalization in the case where we | |
496 | extract ranges from var + CST op limit. */ | |
497 | ||
498 | void | |
4ba9fb0a | 499 | irange::set (tree min, tree max, value_range_kind kind) |
cca78449 | 500 | { |
6c29c9d6 AH |
501 | if (kind != VR_UNDEFINED) |
502 | { | |
503 | if (TREE_OVERFLOW_P (min)) | |
504 | min = drop_tree_overflow (min); | |
505 | if (TREE_OVERFLOW_P (max)) | |
506 | max = drop_tree_overflow (max); | |
507 | } | |
508 | ||
4ba9fb0a AH |
509 | if (!legacy_mode_p ()) |
510 | { | |
511 | if (kind == VR_RANGE) | |
512 | irange_set (min, max); | |
513 | else | |
514 | { | |
515 | gcc_checking_assert (kind == VR_ANTI_RANGE); | |
516 | irange_set_anti_range (min, max); | |
517 | } | |
518 | return; | |
519 | } | |
cca78449 AH |
520 | if (kind == VR_UNDEFINED) |
521 | { | |
4f1bce19 | 522 | irange::set_undefined (); |
cca78449 AH |
523 | return; |
524 | } | |
54ef7701 | 525 | |
c76c23a0 AH |
526 | if (kind == VR_VARYING |
527 | || POLY_INT_CST_P (min) | |
528 | || POLY_INT_CST_P (max)) | |
5e41e7f0 AH |
529 | { |
530 | set_varying (TREE_TYPE (min)); | |
531 | return; | |
532 | } | |
54ef7701 | 533 | |
4ba9fb0a | 534 | // Nothing to canonicalize for symbolic ranges. |
cca78449 AH |
535 | if (TREE_CODE (min) != INTEGER_CST |
536 | || TREE_CODE (max) != INTEGER_CST) | |
537 | { | |
538 | m_kind = kind; | |
4ba9fb0a AH |
539 | m_base[0] = min; |
540 | m_base[1] = max; | |
541 | m_num_ranges = 1; | |
4e82205b | 542 | m_nonzero_mask = NULL; |
cca78449 AH |
543 | return; |
544 | } | |
4e85ad79 AH |
545 | |
546 | swap_out_of_order_endpoints (min, max, kind); | |
547 | if (kind == VR_VARYING) | |
548 | { | |
549 | set_varying (TREE_TYPE (min)); | |
550 | return; | |
551 | } | |
cca78449 | 552 | |
4ba9fb0a | 553 | // Anti-ranges that can be represented as ranges should be so. |
cca78449 AH |
554 | if (kind == VR_ANTI_RANGE) |
555 | { | |
cca78449 AH |
556 | bool is_min = vrp_val_is_min (min); |
557 | bool is_max = vrp_val_is_max (max); | |
558 | ||
559 | if (is_min && is_max) | |
560 | { | |
e6455a09 AH |
561 | // Fall through. This will either be normalized as |
562 | // VR_UNDEFINED if the anti-range spans the entire | |
563 | // precision, or it will remain an VR_ANTI_RANGE in the case | |
564 | // of an -fstrict-enum where [MIN,MAX] is less than the span | |
565 | // of underlying precision. | |
cca78449 | 566 | } |
e6455a09 | 567 | else if (TYPE_PRECISION (TREE_TYPE (min)) == 1) |
cca78449 | 568 | { |
e6455a09 AH |
569 | irange_set_1bit_anti_range (min, max); |
570 | return; | |
cca78449 AH |
571 | } |
572 | else if (is_min) | |
573 | { | |
574 | tree one = build_int_cst (TREE_TYPE (max), 1); | |
575 | min = int_const_binop (PLUS_EXPR, max, one); | |
576 | max = vrp_val_max (TREE_TYPE (max)); | |
577 | kind = VR_RANGE; | |
578 | } | |
579 | else if (is_max) | |
580 | { | |
581 | tree one = build_int_cst (TREE_TYPE (min), 1); | |
582 | max = int_const_binop (MINUS_EXPR, min, one); | |
583 | min = vrp_val_min (TREE_TYPE (min)); | |
584 | kind = VR_RANGE; | |
585 | } | |
586 | } | |
cca78449 | 587 | |
4e85ad79 AH |
588 | m_kind = kind; |
589 | m_base[0] = min; | |
590 | m_base[1] = max; | |
591 | m_num_ranges = 1; | |
4e82205b | 592 | m_nonzero_mask = NULL; |
c106825b | 593 | normalize_kind (); |
cca78449 | 594 | if (flag_checking) |
4ba9fb0a | 595 | verify_range (); |
cca78449 AH |
596 | } |
597 | ||
4e85ad79 | 598 | // Check the validity of the range. |
cca78449 AH |
599 | |
600 | void | |
4ba9fb0a | 601 | irange::verify_range () |
cca78449 | 602 | { |
4f1bce19 | 603 | gcc_checking_assert (m_discriminator == VR_IRANGE); |
dc80d5e8 AH |
604 | if (m_kind == VR_UNDEFINED) |
605 | { | |
db3581c4 | 606 | gcc_checking_assert (m_num_ranges == 0); |
4e82205b | 607 | gcc_checking_assert (!m_nonzero_mask); |
dc80d5e8 AH |
608 | return; |
609 | } | |
4e82205b AH |
610 | if (m_nonzero_mask) |
611 | gcc_checking_assert (wi::to_wide (m_nonzero_mask) != -1); | |
dc80d5e8 AH |
612 | if (m_kind == VR_VARYING) |
613 | { | |
c106825b | 614 | gcc_checking_assert (!m_nonzero_mask); |
dc80d5e8 AH |
615 | gcc_checking_assert (m_num_ranges == 1); |
616 | gcc_checking_assert (varying_compatible_p ()); | |
617 | return; | |
618 | } | |
4ba9fb0a | 619 | if (!legacy_mode_p ()) |
cca78449 | 620 | { |
db3581c4 | 621 | gcc_checking_assert (m_num_ranges != 0); |
dc80d5e8 | 622 | gcc_checking_assert (!varying_compatible_p ()); |
4ba9fb0a AH |
623 | for (unsigned i = 0; i < m_num_ranges; ++i) |
624 | { | |
625 | tree lb = tree_lower_bound (i); | |
626 | tree ub = tree_upper_bound (i); | |
627 | int c = compare_values (lb, ub); | |
db3581c4 | 628 | gcc_checking_assert (c == 0 || c == -1); |
4ba9fb0a AH |
629 | } |
630 | return; | |
631 | } | |
dc80d5e8 | 632 | if (m_kind == VR_RANGE || m_kind == VR_ANTI_RANGE) |
4ba9fb0a | 633 | { |
db3581c4 | 634 | gcc_checking_assert (m_num_ranges == 1); |
dc80d5e8 | 635 | int cmp = compare_values (tree_lower_bound (0), tree_upper_bound (0)); |
db3581c4 | 636 | gcc_checking_assert (cmp == 0 || cmp == -1 || cmp == -2); |
cca78449 | 637 | } |
cca78449 AH |
638 | } |
639 | ||
4ba9fb0a AH |
640 | // Return the lower bound for a sub-range. PAIR is the sub-range in |
641 | // question. | |
cca78449 AH |
642 | |
643 | wide_int | |
4ba9fb0a | 644 | irange::legacy_lower_bound (unsigned pair) const |
cca78449 | 645 | { |
4ba9fb0a | 646 | gcc_checking_assert (legacy_mode_p ()); |
cca78449 | 647 | if (symbolic_p ()) |
6ee86466 AH |
648 | { |
649 | value_range numeric_range (*this); | |
650 | numeric_range.normalize_symbolics (); | |
4ba9fb0a | 651 | return numeric_range.legacy_lower_bound (pair); |
6ee86466 | 652 | } |
77803216 | 653 | gcc_checking_assert (m_num_ranges > 0); |
cca78449 | 654 | gcc_checking_assert (pair + 1 <= num_pairs ()); |
cca78449 AH |
655 | if (m_kind == VR_ANTI_RANGE) |
656 | { | |
4ba9fb0a AH |
657 | tree typ = type (), t; |
658 | if (pair == 1 || vrp_val_is_min (min ())) | |
659 | t = wide_int_to_tree (typ, wi::to_wide (max ()) + 1); | |
cca78449 AH |
660 | else |
661 | t = vrp_val_min (typ); | |
4ba9fb0a | 662 | return wi::to_wide (t); |
cca78449 | 663 | } |
4ba9fb0a | 664 | return wi::to_wide (tree_lower_bound (pair)); |
cca78449 AH |
665 | } |
666 | ||
4ba9fb0a AH |
667 | // Return the upper bound for a sub-range. PAIR is the sub-range in |
668 | // question. | |
cca78449 AH |
669 | |
670 | wide_int | |
4ba9fb0a | 671 | irange::legacy_upper_bound (unsigned pair) const |
cca78449 | 672 | { |
4ba9fb0a | 673 | gcc_checking_assert (legacy_mode_p ()); |
cca78449 | 674 | if (symbolic_p ()) |
6ee86466 AH |
675 | { |
676 | value_range numeric_range (*this); | |
677 | numeric_range.normalize_symbolics (); | |
4ba9fb0a | 678 | return numeric_range.legacy_upper_bound (pair); |
6ee86466 | 679 | } |
77803216 | 680 | gcc_checking_assert (m_num_ranges > 0); |
cca78449 | 681 | gcc_checking_assert (pair + 1 <= num_pairs ()); |
cca78449 AH |
682 | if (m_kind == VR_ANTI_RANGE) |
683 | { | |
4ba9fb0a AH |
684 | tree typ = type (), t; |
685 | if (pair == 1 || vrp_val_is_min (min ())) | |
cca78449 AH |
686 | t = vrp_val_max (typ); |
687 | else | |
4ba9fb0a AH |
688 | t = wide_int_to_tree (typ, wi::to_wide (min ()) - 1); |
689 | return wi::to_wide (t); | |
cca78449 | 690 | } |
4ba9fb0a | 691 | return wi::to_wide (tree_upper_bound (pair)); |
cca78449 AH |
692 | } |
693 | ||
694 | bool | |
4ba9fb0a | 695 | irange::legacy_equal_p (const irange &other) const |
cca78449 | 696 | { |
4ba9fb0a | 697 | gcc_checking_assert (legacy_mode_p () && other.legacy_mode_p ()); |
cca78449 | 698 | |
4ba9fb0a AH |
699 | if (m_kind != other.m_kind) |
700 | return false; | |
ca8cc827 | 701 | if (m_kind == VR_UNDEFINED) |
4ba9fb0a | 702 | return true; |
ca8cc827 | 703 | if (m_kind == VR_VARYING) |
4e82205b AH |
704 | { |
705 | return (range_compatible_p (type (), other.type ()) | |
706 | && vrp_operand_equal_p (m_nonzero_mask, other.m_nonzero_mask)); | |
707 | } | |
4ba9fb0a AH |
708 | return (vrp_operand_equal_p (tree_lower_bound (0), |
709 | other.tree_lower_bound (0)) | |
710 | && vrp_operand_equal_p (tree_upper_bound (0), | |
4e82205b AH |
711 | other.tree_upper_bound (0)) |
712 | && vrp_operand_equal_p (m_nonzero_mask, other.m_nonzero_mask)); | |
cca78449 AH |
713 | } |
714 | ||
715 | bool | |
bbe836bc | 716 | irange::operator== (const irange &other) const |
cca78449 | 717 | { |
4ba9fb0a AH |
718 | if (legacy_mode_p ()) |
719 | { | |
720 | if (other.legacy_mode_p ()) | |
721 | return legacy_equal_p (other); | |
722 | value_range tmp (other); | |
723 | return legacy_equal_p (tmp); | |
724 | } | |
725 | if (other.legacy_mode_p ()) | |
726 | { | |
727 | value_range tmp2 (*this); | |
728 | return tmp2.legacy_equal_p (other); | |
729 | } | |
730 | ||
731 | if (m_num_ranges != other.m_num_ranges) | |
732 | return false; | |
733 | ||
734 | for (unsigned i = 0; i < m_num_ranges; ++i) | |
735 | { | |
736 | tree lb = tree_lower_bound (i); | |
737 | tree ub = tree_upper_bound (i); | |
738 | tree lb_other = other.tree_lower_bound (i); | |
739 | tree ub_other = other.tree_upper_bound (i); | |
740 | if (!operand_equal_p (lb, lb_other, 0) | |
741 | || !operand_equal_p (ub, ub_other, 0)) | |
742 | return false; | |
743 | } | |
4e82205b | 744 | return vrp_operand_equal_p (m_nonzero_mask, other.m_nonzero_mask); |
cca78449 AH |
745 | } |
746 | ||
cca78449 AH |
747 | /* Return TRUE if this is a symbolic range. */ |
748 | ||
749 | bool | |
4ba9fb0a | 750 | irange::symbolic_p () const |
cca78449 | 751 | { |
694c956b | 752 | return (m_num_ranges > 0 |
4ba9fb0a AH |
753 | && (!is_gimple_min_invariant (min ()) |
754 | || !is_gimple_min_invariant (max ()))); | |
cca78449 AH |
755 | } |
756 | ||
694c956b | 757 | /* Return TRUE if this is a constant range. */ |
cca78449 AH |
758 | |
759 | bool | |
4ba9fb0a | 760 | irange::constant_p () const |
cca78449 | 761 | { |
694c956b | 762 | return (m_num_ranges > 0 |
4ba9fb0a AH |
763 | && TREE_CODE (min ()) == INTEGER_CST |
764 | && TREE_CODE (max ()) == INTEGER_CST); | |
cca78449 AH |
765 | } |
766 | ||
4ba9fb0a AH |
767 | /* If range is a singleton, place it in RESULT and return TRUE. |
768 | Note: A singleton can be any gimple invariant, not just constants. | |
769 | So, [&x, &x] counts as a singleton. */ | |
770 | ||
cca78449 | 771 | bool |
4ba9fb0a | 772 | irange::singleton_p (tree *result) const |
cca78449 | 773 | { |
4ba9fb0a AH |
774 | if (!legacy_mode_p ()) |
775 | { | |
776 | if (num_pairs () == 1 && (wi::to_wide (tree_lower_bound ()) | |
777 | == wi::to_wide (tree_upper_bound ()))) | |
778 | { | |
779 | if (result) | |
780 | *result = tree_lower_bound (); | |
781 | return true; | |
782 | } | |
783 | return false; | |
784 | } | |
cca78449 AH |
785 | if (m_kind == VR_ANTI_RANGE) |
786 | { | |
787 | if (nonzero_p ()) | |
788 | { | |
789 | if (TYPE_PRECISION (type ()) == 1) | |
790 | { | |
791 | if (result) | |
4ba9fb0a | 792 | *result = max (); |
cca78449 AH |
793 | return true; |
794 | } | |
795 | return false; | |
796 | } | |
797 | if (num_pairs () == 1) | |
798 | { | |
799 | value_range vr0, vr1; | |
4ba9fb0a | 800 | ranges_from_anti_range ((const value_range *) this, &vr0, &vr1); |
cca78449 AH |
801 | return vr0.singleton_p (result); |
802 | } | |
803 | } | |
4ba9fb0a | 804 | // Catches non-numeric extremes as well. |
cca78449 AH |
805 | if (m_kind == VR_RANGE |
806 | && vrp_operand_equal_p (min (), max ()) | |
807 | && is_gimple_min_invariant (min ())) | |
808 | { | |
809 | if (result) | |
810 | *result = min (); | |
811 | return true; | |
812 | } | |
813 | return false; | |
814 | } | |
815 | ||
816 | /* Return 1 if VAL is inside value range. | |
4ba9fb0a | 817 | 0 if VAL is not inside value range. |
cca78449 AH |
818 | -2 if we cannot tell either way. |
819 | ||
820 | Benchmark compile/20001226-1.c compilation time after changing this | |
821 | function. */ | |
822 | ||
823 | int | |
4ba9fb0a | 824 | irange::value_inside_range (tree val) const |
cca78449 | 825 | { |
cca78449 AH |
826 | if (varying_p ()) |
827 | return 1; | |
828 | ||
829 | if (undefined_p ()) | |
830 | return 0; | |
831 | ||
4ba9fb0a AH |
832 | if (!legacy_mode_p () && TREE_CODE (val) == INTEGER_CST) |
833 | return contains_p (val); | |
834 | ||
835 | int cmp1 = operand_less_p (val, min ()); | |
cca78449 AH |
836 | if (cmp1 == -2) |
837 | return -2; | |
838 | if (cmp1 == 1) | |
839 | return m_kind != VR_RANGE; | |
840 | ||
4ba9fb0a | 841 | int cmp2 = operand_less_p (max (), val); |
cca78449 AH |
842 | if (cmp2 == -2) |
843 | return -2; | |
844 | ||
845 | if (m_kind == VR_RANGE) | |
846 | return !cmp2; | |
847 | else | |
848 | return !!cmp2; | |
849 | } | |
850 | ||
851 | /* Return TRUE if it is possible that range contains VAL. */ | |
852 | ||
853 | bool | |
4ba9fb0a | 854 | irange::may_contain_p (tree val) const |
cca78449 AH |
855 | { |
856 | return value_inside_range (val) != 0; | |
857 | } | |
858 | ||
859 | /* Return TRUE if range contains INTEGER_CST. */ | |
4ba9fb0a AH |
860 | /* Return 1 if VAL is inside value range. |
861 | 0 if VAL is not inside value range. | |
862 | ||
863 | Benchmark compile/20001226-1.c compilation time after changing this | |
864 | function. */ | |
865 | ||
cca78449 AH |
866 | |
867 | bool | |
4ba9fb0a | 868 | irange::contains_p (tree cst) const |
cca78449 | 869 | { |
4ba9fb0a AH |
870 | if (undefined_p ()) |
871 | return false; | |
872 | ||
873 | if (legacy_mode_p ()) | |
874 | { | |
875 | gcc_checking_assert (TREE_CODE (cst) == INTEGER_CST); | |
876 | if (symbolic_p ()) | |
877 | { | |
878 | value_range numeric_range (*this); | |
879 | numeric_range.normalize_symbolics (); | |
880 | return numeric_range.contains_p (cst); | |
881 | } | |
882 | return value_inside_range (cst) == 1; | |
883 | } | |
884 | ||
cca78449 | 885 | gcc_checking_assert (TREE_CODE (cst) == INTEGER_CST); |
4e82205b AH |
886 | |
887 | if (m_nonzero_mask) | |
888 | { | |
889 | wide_int cstw = wi::to_wide (cst); | |
890 | if (cstw != 0 && wi::bit_and (wi::to_wide (m_nonzero_mask), cstw) == 0) | |
891 | return false; | |
892 | } | |
893 | ||
4ba9fb0a AH |
894 | signop sign = TYPE_SIGN (TREE_TYPE (cst)); |
895 | wide_int v = wi::to_wide (cst); | |
896 | for (unsigned r = 0; r < m_num_ranges; ++r) | |
6ee86466 | 897 | { |
4ba9fb0a AH |
898 | if (wi::lt_p (v, lower_bound (r), sign)) |
899 | return false; | |
900 | if (wi::le_p (v, upper_bound (r), sign)) | |
901 | return true; | |
6ee86466 | 902 | } |
4ba9fb0a AH |
903 | |
904 | return false; | |
cca78449 AH |
905 | } |
906 | ||
4ba9fb0a | 907 | |
cca78449 AH |
908 | /* Normalize addresses into constants. */ |
909 | ||
6ee86466 | 910 | void |
4ba9fb0a | 911 | irange::normalize_addresses () |
cca78449 AH |
912 | { |
913 | if (undefined_p ()) | |
6ee86466 | 914 | return; |
cca78449 AH |
915 | |
916 | if (!POINTER_TYPE_P (type ()) || range_has_numeric_bounds_p (this)) | |
6ee86466 | 917 | return; |
cca78449 AH |
918 | |
919 | if (!range_includes_zero_p (this)) | |
920 | { | |
4ba9fb0a AH |
921 | gcc_checking_assert (TREE_CODE (min ()) == ADDR_EXPR |
922 | || TREE_CODE (max ()) == ADDR_EXPR); | |
6ee86466 AH |
923 | set_nonzero (type ()); |
924 | return; | |
cca78449 | 925 | } |
6ee86466 | 926 | set_varying (type ()); |
cca78449 AH |
927 | } |
928 | ||
929 | /* Normalize symbolics and addresses into constants. */ | |
930 | ||
6ee86466 | 931 | void |
4ba9fb0a | 932 | irange::normalize_symbolics () |
cca78449 AH |
933 | { |
934 | if (varying_p () || undefined_p ()) | |
6ee86466 AH |
935 | return; |
936 | ||
cca78449 AH |
937 | tree ttype = type (); |
938 | bool min_symbolic = !is_gimple_min_invariant (min ()); | |
939 | bool max_symbolic = !is_gimple_min_invariant (max ()); | |
940 | if (!min_symbolic && !max_symbolic) | |
6ee86466 AH |
941 | { |
942 | normalize_addresses (); | |
943 | return; | |
944 | } | |
cca78449 AH |
945 | |
946 | // [SYM, SYM] -> VARYING | |
947 | if (min_symbolic && max_symbolic) | |
948 | { | |
6ee86466 AH |
949 | set_varying (ttype); |
950 | return; | |
cca78449 AH |
951 | } |
952 | if (kind () == VR_RANGE) | |
953 | { | |
954 | // [SYM, NUM] -> [-MIN, NUM] | |
955 | if (min_symbolic) | |
6ee86466 AH |
956 | { |
957 | set (vrp_val_min (ttype), max ()); | |
958 | return; | |
959 | } | |
cca78449 | 960 | // [NUM, SYM] -> [NUM, +MAX] |
6ee86466 AH |
961 | set (min (), vrp_val_max (ttype)); |
962 | return; | |
cca78449 AH |
963 | } |
964 | gcc_checking_assert (kind () == VR_ANTI_RANGE); | |
965 | // ~[SYM, NUM] -> [NUM + 1, +MAX] | |
966 | if (min_symbolic) | |
967 | { | |
968 | if (!vrp_val_is_max (max ())) | |
969 | { | |
970 | tree n = wide_int_to_tree (ttype, wi::to_wide (max ()) + 1); | |
6ee86466 AH |
971 | set (n, vrp_val_max (ttype)); |
972 | return; | |
cca78449 | 973 | } |
6ee86466 AH |
974 | set_varying (ttype); |
975 | return; | |
cca78449 AH |
976 | } |
977 | // ~[NUM, SYM] -> [-MIN, NUM - 1] | |
978 | if (!vrp_val_is_min (min ())) | |
979 | { | |
980 | tree n = wide_int_to_tree (ttype, wi::to_wide (min ()) - 1); | |
6ee86466 AH |
981 | set (vrp_val_min (ttype), n); |
982 | return; | |
cca78449 | 983 | } |
6ee86466 | 984 | set_varying (ttype); |
cca78449 AH |
985 | } |
986 | ||
987 | /* Intersect the two value-ranges { *VR0TYPE, *VR0MIN, *VR0MAX } and | |
988 | { VR1TYPE, VR0MIN, VR0MAX } and store the result | |
989 | in { *VR0TYPE, *VR0MIN, *VR0MAX }. This may not be the smallest | |
990 | possible such range. The resulting range is not canonicalized. */ | |
991 | ||
992 | static void | |
993 | intersect_ranges (enum value_range_kind *vr0type, | |
994 | tree *vr0min, tree *vr0max, | |
995 | enum value_range_kind vr1type, | |
996 | tree vr1min, tree vr1max) | |
997 | { | |
998 | bool mineq = vrp_operand_equal_p (*vr0min, vr1min); | |
999 | bool maxeq = vrp_operand_equal_p (*vr0max, vr1max); | |
1000 | ||
1001 | /* [] is vr0, () is vr1 in the following classification comments. */ | |
1002 | if (mineq && maxeq) | |
1003 | { | |
1004 | /* [( )] */ | |
1005 | if (*vr0type == vr1type) | |
1006 | /* Nothing to do for equal ranges. */ | |
1007 | ; | |
1008 | else if ((*vr0type == VR_RANGE | |
1009 | && vr1type == VR_ANTI_RANGE) | |
1010 | || (*vr0type == VR_ANTI_RANGE | |
1011 | && vr1type == VR_RANGE)) | |
1012 | { | |
1013 | /* For anti-range with range intersection the result is empty. */ | |
1014 | *vr0type = VR_UNDEFINED; | |
1015 | *vr0min = NULL_TREE; | |
1016 | *vr0max = NULL_TREE; | |
1017 | } | |
1018 | else | |
1019 | gcc_unreachable (); | |
1020 | } | |
1021 | else if (operand_less_p (*vr0max, vr1min) == 1 | |
1022 | || operand_less_p (vr1max, *vr0min) == 1) | |
1023 | { | |
1024 | /* [ ] ( ) or ( ) [ ] | |
1025 | If the ranges have an empty intersection, the result of the | |
1026 | intersect operation is the range for intersecting an | |
1027 | anti-range with a range or empty when intersecting two ranges. */ | |
1028 | if (*vr0type == VR_RANGE | |
1029 | && vr1type == VR_ANTI_RANGE) | |
1030 | ; | |
1031 | else if (*vr0type == VR_ANTI_RANGE | |
1032 | && vr1type == VR_RANGE) | |
1033 | { | |
1034 | *vr0type = vr1type; | |
1035 | *vr0min = vr1min; | |
1036 | *vr0max = vr1max; | |
1037 | } | |
1038 | else if (*vr0type == VR_RANGE | |
1039 | && vr1type == VR_RANGE) | |
1040 | { | |
1041 | *vr0type = VR_UNDEFINED; | |
1042 | *vr0min = NULL_TREE; | |
1043 | *vr0max = NULL_TREE; | |
1044 | } | |
1045 | else if (*vr0type == VR_ANTI_RANGE | |
1046 | && vr1type == VR_ANTI_RANGE) | |
1047 | { | |
1048 | /* If the anti-ranges are adjacent to each other merge them. */ | |
1049 | if (TREE_CODE (*vr0max) == INTEGER_CST | |
1050 | && TREE_CODE (vr1min) == INTEGER_CST | |
1051 | && operand_less_p (*vr0max, vr1min) == 1 | |
1052 | && integer_onep (int_const_binop (MINUS_EXPR, | |
1053 | vr1min, *vr0max))) | |
1054 | *vr0max = vr1max; | |
1055 | else if (TREE_CODE (vr1max) == INTEGER_CST | |
1056 | && TREE_CODE (*vr0min) == INTEGER_CST | |
1057 | && operand_less_p (vr1max, *vr0min) == 1 | |
1058 | && integer_onep (int_const_binop (MINUS_EXPR, | |
1059 | *vr0min, vr1max))) | |
1060 | *vr0min = vr1min; | |
1061 | /* Else arbitrarily take VR0. */ | |
1062 | } | |
1063 | } | |
1064 | else if ((maxeq || operand_less_p (vr1max, *vr0max) == 1) | |
1065 | && (mineq || operand_less_p (*vr0min, vr1min) == 1)) | |
1066 | { | |
1067 | /* [ ( ) ] or [( ) ] or [ ( )] */ | |
1068 | if (*vr0type == VR_RANGE | |
1069 | && vr1type == VR_RANGE) | |
1070 | { | |
1071 | /* If both are ranges the result is the inner one. */ | |
1072 | *vr0type = vr1type; | |
1073 | *vr0min = vr1min; | |
1074 | *vr0max = vr1max; | |
1075 | } | |
1076 | else if (*vr0type == VR_RANGE | |
1077 | && vr1type == VR_ANTI_RANGE) | |
1078 | { | |
1079 | /* Choose the right gap if the left one is empty. */ | |
1080 | if (mineq) | |
1081 | { | |
1082 | if (TREE_CODE (vr1max) != INTEGER_CST) | |
1083 | *vr0min = vr1max; | |
1084 | else if (TYPE_PRECISION (TREE_TYPE (vr1max)) == 1 | |
1085 | && !TYPE_UNSIGNED (TREE_TYPE (vr1max))) | |
1086 | *vr0min | |
1087 | = int_const_binop (MINUS_EXPR, vr1max, | |
1088 | build_int_cst (TREE_TYPE (vr1max), -1)); | |
1089 | else | |
1090 | *vr0min | |
1091 | = int_const_binop (PLUS_EXPR, vr1max, | |
1092 | build_int_cst (TREE_TYPE (vr1max), 1)); | |
1093 | } | |
1094 | /* Choose the left gap if the right one is empty. */ | |
1095 | else if (maxeq) | |
1096 | { | |
1097 | if (TREE_CODE (vr1min) != INTEGER_CST) | |
1098 | *vr0max = vr1min; | |
1099 | else if (TYPE_PRECISION (TREE_TYPE (vr1min)) == 1 | |
1100 | && !TYPE_UNSIGNED (TREE_TYPE (vr1min))) | |
1101 | *vr0max | |
1102 | = int_const_binop (PLUS_EXPR, vr1min, | |
1103 | build_int_cst (TREE_TYPE (vr1min), -1)); | |
1104 | else | |
1105 | *vr0max | |
1106 | = int_const_binop (MINUS_EXPR, vr1min, | |
1107 | build_int_cst (TREE_TYPE (vr1min), 1)); | |
1108 | } | |
1109 | /* Choose the anti-range if the range is effectively varying. */ | |
1110 | else if (vrp_val_is_min (*vr0min) | |
1111 | && vrp_val_is_max (*vr0max)) | |
1112 | { | |
1113 | *vr0type = vr1type; | |
1114 | *vr0min = vr1min; | |
1115 | *vr0max = vr1max; | |
1116 | } | |
1117 | /* Else choose the range. */ | |
1118 | } | |
1119 | else if (*vr0type == VR_ANTI_RANGE | |
1120 | && vr1type == VR_ANTI_RANGE) | |
1121 | /* If both are anti-ranges the result is the outer one. */ | |
1122 | ; | |
1123 | else if (*vr0type == VR_ANTI_RANGE | |
1124 | && vr1type == VR_RANGE) | |
1125 | { | |
1126 | /* The intersection is empty. */ | |
1127 | *vr0type = VR_UNDEFINED; | |
1128 | *vr0min = NULL_TREE; | |
1129 | *vr0max = NULL_TREE; | |
1130 | } | |
1131 | else | |
1132 | gcc_unreachable (); | |
1133 | } | |
1134 | else if ((maxeq || operand_less_p (*vr0max, vr1max) == 1) | |
1135 | && (mineq || operand_less_p (vr1min, *vr0min) == 1)) | |
1136 | { | |
1137 | /* ( [ ] ) or ([ ] ) or ( [ ]) */ | |
1138 | if (*vr0type == VR_RANGE | |
1139 | && vr1type == VR_RANGE) | |
1140 | /* Choose the inner range. */ | |
1141 | ; | |
1142 | else if (*vr0type == VR_ANTI_RANGE | |
1143 | && vr1type == VR_RANGE) | |
1144 | { | |
1145 | /* Choose the right gap if the left is empty. */ | |
1146 | if (mineq) | |
1147 | { | |
1148 | *vr0type = VR_RANGE; | |
1149 | if (TREE_CODE (*vr0max) != INTEGER_CST) | |
1150 | *vr0min = *vr0max; | |
1151 | else if (TYPE_PRECISION (TREE_TYPE (*vr0max)) == 1 | |
1152 | && !TYPE_UNSIGNED (TREE_TYPE (*vr0max))) | |
1153 | *vr0min | |
1154 | = int_const_binop (MINUS_EXPR, *vr0max, | |
1155 | build_int_cst (TREE_TYPE (*vr0max), -1)); | |
1156 | else | |
1157 | *vr0min | |
1158 | = int_const_binop (PLUS_EXPR, *vr0max, | |
1159 | build_int_cst (TREE_TYPE (*vr0max), 1)); | |
1160 | *vr0max = vr1max; | |
1161 | } | |
1162 | /* Choose the left gap if the right is empty. */ | |
1163 | else if (maxeq) | |
1164 | { | |
1165 | *vr0type = VR_RANGE; | |
1166 | if (TREE_CODE (*vr0min) != INTEGER_CST) | |
1167 | *vr0max = *vr0min; | |
1168 | else if (TYPE_PRECISION (TREE_TYPE (*vr0min)) == 1 | |
1169 | && !TYPE_UNSIGNED (TREE_TYPE (*vr0min))) | |
1170 | *vr0max | |
1171 | = int_const_binop (PLUS_EXPR, *vr0min, | |
1172 | build_int_cst (TREE_TYPE (*vr0min), -1)); | |
1173 | else | |
1174 | *vr0max | |
1175 | = int_const_binop (MINUS_EXPR, *vr0min, | |
1176 | build_int_cst (TREE_TYPE (*vr0min), 1)); | |
1177 | *vr0min = vr1min; | |
1178 | } | |
1179 | /* Choose the anti-range if the range is effectively varying. */ | |
1180 | else if (vrp_val_is_min (vr1min) | |
1181 | && vrp_val_is_max (vr1max)) | |
1182 | ; | |
1183 | /* Choose the anti-range if it is ~[0,0], that range is special | |
1184 | enough to special case when vr1's range is relatively wide. | |
1185 | At least for types bigger than int - this covers pointers | |
1186 | and arguments to functions like ctz. */ | |
1187 | else if (*vr0min == *vr0max | |
1188 | && integer_zerop (*vr0min) | |
1189 | && ((TYPE_PRECISION (TREE_TYPE (*vr0min)) | |
1190 | >= TYPE_PRECISION (integer_type_node)) | |
1191 | || POINTER_TYPE_P (TREE_TYPE (*vr0min))) | |
1192 | && TREE_CODE (vr1max) == INTEGER_CST | |
1193 | && TREE_CODE (vr1min) == INTEGER_CST | |
1194 | && (wi::clz (wi::to_wide (vr1max) - wi::to_wide (vr1min)) | |
1195 | < TYPE_PRECISION (TREE_TYPE (*vr0min)) / 2)) | |
1196 | ; | |
1197 | /* Else choose the range. */ | |
1198 | else | |
1199 | { | |
1200 | *vr0type = vr1type; | |
1201 | *vr0min = vr1min; | |
1202 | *vr0max = vr1max; | |
1203 | } | |
1204 | } | |
1205 | else if (*vr0type == VR_ANTI_RANGE | |
1206 | && vr1type == VR_ANTI_RANGE) | |
1207 | { | |
1208 | /* If both are anti-ranges the result is the outer one. */ | |
1209 | *vr0type = vr1type; | |
1210 | *vr0min = vr1min; | |
1211 | *vr0max = vr1max; | |
1212 | } | |
1213 | else if (vr1type == VR_ANTI_RANGE | |
1214 | && *vr0type == VR_RANGE) | |
1215 | { | |
1216 | /* The intersection is empty. */ | |
1217 | *vr0type = VR_UNDEFINED; | |
1218 | *vr0min = NULL_TREE; | |
1219 | *vr0max = NULL_TREE; | |
1220 | } | |
1221 | else | |
1222 | gcc_unreachable (); | |
1223 | } | |
1224 | else if ((operand_less_p (vr1min, *vr0max) == 1 | |
1225 | || operand_equal_p (vr1min, *vr0max, 0)) | |
a05cc70a RB |
1226 | && operand_less_p (*vr0min, vr1min) == 1 |
1227 | && operand_less_p (*vr0max, vr1max) == 1) | |
cca78449 AH |
1228 | { |
1229 | /* [ ( ] ) or [ ]( ) */ | |
1230 | if (*vr0type == VR_ANTI_RANGE | |
1231 | && vr1type == VR_ANTI_RANGE) | |
1232 | *vr0max = vr1max; | |
1233 | else if (*vr0type == VR_RANGE | |
1234 | && vr1type == VR_RANGE) | |
1235 | *vr0min = vr1min; | |
1236 | else if (*vr0type == VR_RANGE | |
1237 | && vr1type == VR_ANTI_RANGE) | |
1238 | { | |
1239 | if (TREE_CODE (vr1min) == INTEGER_CST) | |
1240 | *vr0max = int_const_binop (MINUS_EXPR, vr1min, | |
1241 | build_int_cst (TREE_TYPE (vr1min), 1)); | |
1242 | else | |
1243 | *vr0max = vr1min; | |
1244 | } | |
1245 | else if (*vr0type == VR_ANTI_RANGE | |
1246 | && vr1type == VR_RANGE) | |
1247 | { | |
1248 | *vr0type = VR_RANGE; | |
1249 | if (TREE_CODE (*vr0max) == INTEGER_CST) | |
1250 | *vr0min = int_const_binop (PLUS_EXPR, *vr0max, | |
1251 | build_int_cst (TREE_TYPE (*vr0max), 1)); | |
1252 | else | |
1253 | *vr0min = *vr0max; | |
1254 | *vr0max = vr1max; | |
1255 | } | |
1256 | else | |
1257 | gcc_unreachable (); | |
1258 | } | |
1259 | else if ((operand_less_p (*vr0min, vr1max) == 1 | |
1260 | || operand_equal_p (*vr0min, vr1max, 0)) | |
a05cc70a RB |
1261 | && operand_less_p (vr1min, *vr0min) == 1 |
1262 | && operand_less_p (vr1max, *vr0max) == 1) | |
cca78449 AH |
1263 | { |
1264 | /* ( [ ) ] or ( )[ ] */ | |
1265 | if (*vr0type == VR_ANTI_RANGE | |
1266 | && vr1type == VR_ANTI_RANGE) | |
1267 | *vr0min = vr1min; | |
1268 | else if (*vr0type == VR_RANGE | |
1269 | && vr1type == VR_RANGE) | |
1270 | *vr0max = vr1max; | |
1271 | else if (*vr0type == VR_RANGE | |
1272 | && vr1type == VR_ANTI_RANGE) | |
1273 | { | |
1274 | if (TREE_CODE (vr1max) == INTEGER_CST) | |
1275 | *vr0min = int_const_binop (PLUS_EXPR, vr1max, | |
1276 | build_int_cst (TREE_TYPE (vr1max), 1)); | |
1277 | else | |
1278 | *vr0min = vr1max; | |
1279 | } | |
1280 | else if (*vr0type == VR_ANTI_RANGE | |
1281 | && vr1type == VR_RANGE) | |
1282 | { | |
1283 | *vr0type = VR_RANGE; | |
1284 | if (TREE_CODE (*vr0min) == INTEGER_CST) | |
1285 | *vr0max = int_const_binop (MINUS_EXPR, *vr0min, | |
1286 | build_int_cst (TREE_TYPE (*vr0min), 1)); | |
1287 | else | |
1288 | *vr0max = *vr0min; | |
1289 | *vr0min = vr1min; | |
1290 | } | |
1291 | else | |
1292 | gcc_unreachable (); | |
1293 | } | |
1294 | ||
1295 | /* If we know the intersection is empty, there's no need to | |
1296 | conservatively add anything else to the set. */ | |
1297 | if (*vr0type == VR_UNDEFINED) | |
1298 | return; | |
1299 | ||
1300 | /* As a fallback simply use { *VRTYPE, *VR0MIN, *VR0MAX } as | |
1301 | result for the intersection. That's always a conservative | |
1302 | correct estimate unless VR1 is a constant singleton range | |
1303 | in which case we choose that. */ | |
1304 | if (vr1type == VR_RANGE | |
1305 | && is_gimple_min_invariant (vr1min) | |
1306 | && vrp_operand_equal_p (vr1min, vr1max)) | |
1307 | { | |
1308 | *vr0type = vr1type; | |
1309 | *vr0min = vr1min; | |
1310 | *vr0max = vr1max; | |
1311 | } | |
1312 | } | |
1313 | ||
1314 | /* Helper for the intersection operation for value ranges. Given two | |
4ba9fb0a AH |
1315 | ranges VR0 and VR1, set VR0 to the intersection of both ranges. |
1316 | This may not be the smallest possible such range. */ | |
cca78449 | 1317 | |
4ba9fb0a AH |
1318 | void |
1319 | irange::legacy_intersect (irange *vr0, const irange *vr1) | |
cca78449 | 1320 | { |
ea6da7f5 AH |
1321 | gcc_checking_assert (vr0->legacy_mode_p ()); |
1322 | gcc_checking_assert (vr1->legacy_mode_p ()); | |
cca78449 AH |
1323 | /* If either range is VR_VARYING the other one wins. */ |
1324 | if (vr1->varying_p ()) | |
4ba9fb0a | 1325 | return; |
cca78449 | 1326 | if (vr0->varying_p ()) |
4ba9fb0a | 1327 | { |
ea6da7f5 | 1328 | vr0->set (vr1->min (), vr1->max (), vr1->kind ()); |
4ba9fb0a AH |
1329 | return; |
1330 | } | |
cca78449 AH |
1331 | |
1332 | /* When either range is VR_UNDEFINED the resulting range is | |
1333 | VR_UNDEFINED, too. */ | |
1334 | if (vr0->undefined_p ()) | |
4ba9fb0a | 1335 | return; |
cca78449 | 1336 | if (vr1->undefined_p ()) |
4ba9fb0a AH |
1337 | { |
1338 | vr0->set_undefined (); | |
1339 | return; | |
1340 | } | |
cca78449 AH |
1341 | |
1342 | value_range_kind vr0kind = vr0->kind (); | |
1343 | tree vr0min = vr0->min (); | |
1344 | tree vr0max = vr0->max (); | |
ea6da7f5 AH |
1345 | |
1346 | intersect_ranges (&vr0kind, &vr0min, &vr0max, | |
1347 | vr1->kind (), vr1->min (), vr1->max ()); | |
4ba9fb0a | 1348 | |
554b21ed AH |
1349 | // Pessimize nonzero masks, as we don't support them. |
1350 | m_nonzero_mask = NULL; | |
1351 | ||
cca78449 | 1352 | /* Make sure to canonicalize the result though as the inversion of a |
4ba9fb0a | 1353 | VR_RANGE can still be a VR_RANGE. */ |
cca78449 | 1354 | if (vr0kind == VR_UNDEFINED) |
4ba9fb0a | 1355 | vr0->set_undefined (); |
cca78449 | 1356 | else if (vr0kind == VR_VARYING) |
4ba9fb0a AH |
1357 | { |
1358 | /* If we failed, use the original VR0. */ | |
1359 | return; | |
1360 | } | |
cca78449 | 1361 | else |
4ba9fb0a | 1362 | vr0->set (vr0min, vr0max, vr0kind); |
cca78449 AH |
1363 | } |
1364 | ||
1365 | /* Union the two value-ranges { *VR0TYPE, *VR0MIN, *VR0MAX } and | |
1366 | { VR1TYPE, VR0MIN, VR0MAX } and store the result | |
1367 | in { *VR0TYPE, *VR0MIN, *VR0MAX }. This may not be the smallest | |
1368 | possible such range. The resulting range is not canonicalized. */ | |
1369 | ||
1370 | static void | |
1371 | union_ranges (enum value_range_kind *vr0type, | |
1372 | tree *vr0min, tree *vr0max, | |
1373 | enum value_range_kind vr1type, | |
1374 | tree vr1min, tree vr1max) | |
1375 | { | |
1376 | int cmpmin = compare_values (*vr0min, vr1min); | |
1377 | int cmpmax = compare_values (*vr0max, vr1max); | |
1378 | bool mineq = cmpmin == 0; | |
1379 | bool maxeq = cmpmax == 0; | |
1380 | ||
1381 | /* [] is vr0, () is vr1 in the following classification comments. */ | |
1382 | if (mineq && maxeq) | |
1383 | { | |
1384 | /* [( )] */ | |
1385 | if (*vr0type == vr1type) | |
1386 | /* Nothing to do for equal ranges. */ | |
1387 | ; | |
1388 | else if ((*vr0type == VR_RANGE | |
1389 | && vr1type == VR_ANTI_RANGE) | |
1390 | || (*vr0type == VR_ANTI_RANGE | |
1391 | && vr1type == VR_RANGE)) | |
1392 | { | |
1393 | /* For anti-range with range union the result is varying. */ | |
1394 | goto give_up; | |
1395 | } | |
1396 | else | |
1397 | gcc_unreachable (); | |
1398 | } | |
1399 | else if (operand_less_p (*vr0max, vr1min) == 1 | |
1400 | || operand_less_p (vr1max, *vr0min) == 1) | |
1401 | { | |
1402 | /* [ ] ( ) or ( ) [ ] | |
1403 | If the ranges have an empty intersection, result of the union | |
1404 | operation is the anti-range or if both are anti-ranges | |
1405 | it covers all. */ | |
1406 | if (*vr0type == VR_ANTI_RANGE | |
1407 | && vr1type == VR_ANTI_RANGE) | |
1408 | goto give_up; | |
1409 | else if (*vr0type == VR_ANTI_RANGE | |
1410 | && vr1type == VR_RANGE) | |
1411 | ; | |
1412 | else if (*vr0type == VR_RANGE | |
1413 | && vr1type == VR_ANTI_RANGE) | |
1414 | { | |
1415 | *vr0type = vr1type; | |
1416 | *vr0min = vr1min; | |
1417 | *vr0max = vr1max; | |
1418 | } | |
1419 | else if (*vr0type == VR_RANGE | |
1420 | && vr1type == VR_RANGE) | |
1421 | { | |
1422 | /* The result is the convex hull of both ranges. */ | |
1423 | if (operand_less_p (*vr0max, vr1min) == 1) | |
1424 | { | |
1425 | /* If the result can be an anti-range, create one. */ | |
1426 | if (TREE_CODE (*vr0max) == INTEGER_CST | |
1427 | && TREE_CODE (vr1min) == INTEGER_CST | |
1428 | && vrp_val_is_min (*vr0min) | |
1429 | && vrp_val_is_max (vr1max)) | |
1430 | { | |
1431 | tree min = int_const_binop (PLUS_EXPR, | |
1432 | *vr0max, | |
1433 | build_int_cst (TREE_TYPE (*vr0max), 1)); | |
1434 | tree max = int_const_binop (MINUS_EXPR, | |
1435 | vr1min, | |
1436 | build_int_cst (TREE_TYPE (vr1min), 1)); | |
1437 | if (!operand_less_p (max, min)) | |
1438 | { | |
1439 | *vr0type = VR_ANTI_RANGE; | |
1440 | *vr0min = min; | |
1441 | *vr0max = max; | |
1442 | } | |
1443 | else | |
1444 | *vr0max = vr1max; | |
1445 | } | |
1446 | else | |
1447 | *vr0max = vr1max; | |
1448 | } | |
1449 | else | |
1450 | { | |
1451 | /* If the result can be an anti-range, create one. */ | |
1452 | if (TREE_CODE (vr1max) == INTEGER_CST | |
1453 | && TREE_CODE (*vr0min) == INTEGER_CST | |
1454 | && vrp_val_is_min (vr1min) | |
1455 | && vrp_val_is_max (*vr0max)) | |
1456 | { | |
1457 | tree min = int_const_binop (PLUS_EXPR, | |
1458 | vr1max, | |
1459 | build_int_cst (TREE_TYPE (vr1max), 1)); | |
1460 | tree max = int_const_binop (MINUS_EXPR, | |
1461 | *vr0min, | |
1462 | build_int_cst (TREE_TYPE (*vr0min), 1)); | |
1463 | if (!operand_less_p (max, min)) | |
1464 | { | |
1465 | *vr0type = VR_ANTI_RANGE; | |
1466 | *vr0min = min; | |
1467 | *vr0max = max; | |
1468 | } | |
1469 | else | |
1470 | *vr0min = vr1min; | |
1471 | } | |
1472 | else | |
1473 | *vr0min = vr1min; | |
1474 | } | |
1475 | } | |
1476 | else | |
1477 | gcc_unreachable (); | |
1478 | } | |
1479 | else if ((maxeq || cmpmax == 1) | |
1480 | && (mineq || cmpmin == -1)) | |
1481 | { | |
1482 | /* [ ( ) ] or [( ) ] or [ ( )] */ | |
1483 | if (*vr0type == VR_RANGE | |
1484 | && vr1type == VR_RANGE) | |
1485 | ; | |
1486 | else if (*vr0type == VR_ANTI_RANGE | |
1487 | && vr1type == VR_ANTI_RANGE) | |
1488 | { | |
1489 | *vr0type = vr1type; | |
1490 | *vr0min = vr1min; | |
1491 | *vr0max = vr1max; | |
1492 | } | |
1493 | else if (*vr0type == VR_ANTI_RANGE | |
1494 | && vr1type == VR_RANGE) | |
1495 | { | |
1496 | /* Arbitrarily choose the right or left gap. */ | |
1497 | if (!mineq && TREE_CODE (vr1min) == INTEGER_CST) | |
1498 | *vr0max = int_const_binop (MINUS_EXPR, vr1min, | |
1499 | build_int_cst (TREE_TYPE (vr1min), 1)); | |
1500 | else if (!maxeq && TREE_CODE (vr1max) == INTEGER_CST) | |
1501 | *vr0min = int_const_binop (PLUS_EXPR, vr1max, | |
1502 | build_int_cst (TREE_TYPE (vr1max), 1)); | |
1503 | else | |
1504 | goto give_up; | |
1505 | } | |
1506 | else if (*vr0type == VR_RANGE | |
1507 | && vr1type == VR_ANTI_RANGE) | |
1508 | /* The result covers everything. */ | |
1509 | goto give_up; | |
1510 | else | |
1511 | gcc_unreachable (); | |
1512 | } | |
1513 | else if ((maxeq || cmpmax == -1) | |
1514 | && (mineq || cmpmin == 1)) | |
1515 | { | |
1516 | /* ( [ ] ) or ([ ] ) or ( [ ]) */ | |
1517 | if (*vr0type == VR_RANGE | |
1518 | && vr1type == VR_RANGE) | |
1519 | { | |
1520 | *vr0type = vr1type; | |
1521 | *vr0min = vr1min; | |
1522 | *vr0max = vr1max; | |
1523 | } | |
1524 | else if (*vr0type == VR_ANTI_RANGE | |
1525 | && vr1type == VR_ANTI_RANGE) | |
1526 | ; | |
1527 | else if (*vr0type == VR_RANGE | |
1528 | && vr1type == VR_ANTI_RANGE) | |
1529 | { | |
1530 | *vr0type = VR_ANTI_RANGE; | |
1531 | if (!mineq && TREE_CODE (*vr0min) == INTEGER_CST) | |
1532 | { | |
1533 | *vr0max = int_const_binop (MINUS_EXPR, *vr0min, | |
1534 | build_int_cst (TREE_TYPE (*vr0min), 1)); | |
1535 | *vr0min = vr1min; | |
1536 | } | |
1537 | else if (!maxeq && TREE_CODE (*vr0max) == INTEGER_CST) | |
1538 | { | |
1539 | *vr0min = int_const_binop (PLUS_EXPR, *vr0max, | |
1540 | build_int_cst (TREE_TYPE (*vr0max), 1)); | |
1541 | *vr0max = vr1max; | |
1542 | } | |
1543 | else | |
1544 | goto give_up; | |
1545 | } | |
1546 | else if (*vr0type == VR_ANTI_RANGE | |
1547 | && vr1type == VR_RANGE) | |
1548 | /* The result covers everything. */ | |
1549 | goto give_up; | |
1550 | else | |
1551 | gcc_unreachable (); | |
1552 | } | |
1553 | else if (cmpmin == -1 | |
1554 | && cmpmax == -1 | |
1555 | && (operand_less_p (vr1min, *vr0max) == 1 | |
1556 | || operand_equal_p (vr1min, *vr0max, 0))) | |
1557 | { | |
1558 | /* [ ( ] ) or [ ]( ) */ | |
1559 | if (*vr0type == VR_RANGE | |
1560 | && vr1type == VR_RANGE) | |
1561 | *vr0max = vr1max; | |
1562 | else if (*vr0type == VR_ANTI_RANGE | |
1563 | && vr1type == VR_ANTI_RANGE) | |
1564 | *vr0min = vr1min; | |
1565 | else if (*vr0type == VR_ANTI_RANGE | |
1566 | && vr1type == VR_RANGE) | |
1567 | { | |
1568 | if (TREE_CODE (vr1min) == INTEGER_CST) | |
1569 | *vr0max = int_const_binop (MINUS_EXPR, vr1min, | |
1570 | build_int_cst (TREE_TYPE (vr1min), 1)); | |
1571 | else | |
1572 | goto give_up; | |
1573 | } | |
1574 | else if (*vr0type == VR_RANGE | |
1575 | && vr1type == VR_ANTI_RANGE) | |
1576 | { | |
1577 | if (TREE_CODE (*vr0max) == INTEGER_CST) | |
1578 | { | |
1579 | *vr0type = vr1type; | |
1580 | *vr0min = int_const_binop (PLUS_EXPR, *vr0max, | |
1581 | build_int_cst (TREE_TYPE (*vr0max), 1)); | |
1582 | *vr0max = vr1max; | |
1583 | } | |
1584 | else | |
1585 | goto give_up; | |
1586 | } | |
1587 | else | |
1588 | gcc_unreachable (); | |
1589 | } | |
1590 | else if (cmpmin == 1 | |
1591 | && cmpmax == 1 | |
1592 | && (operand_less_p (*vr0min, vr1max) == 1 | |
1593 | || operand_equal_p (*vr0min, vr1max, 0))) | |
1594 | { | |
1595 | /* ( [ ) ] or ( )[ ] */ | |
1596 | if (*vr0type == VR_RANGE | |
1597 | && vr1type == VR_RANGE) | |
1598 | *vr0min = vr1min; | |
1599 | else if (*vr0type == VR_ANTI_RANGE | |
1600 | && vr1type == VR_ANTI_RANGE) | |
1601 | *vr0max = vr1max; | |
1602 | else if (*vr0type == VR_ANTI_RANGE | |
1603 | && vr1type == VR_RANGE) | |
1604 | { | |
1605 | if (TREE_CODE (vr1max) == INTEGER_CST) | |
1606 | *vr0min = int_const_binop (PLUS_EXPR, vr1max, | |
1607 | build_int_cst (TREE_TYPE (vr1max), 1)); | |
1608 | else | |
1609 | goto give_up; | |
1610 | } | |
1611 | else if (*vr0type == VR_RANGE | |
1612 | && vr1type == VR_ANTI_RANGE) | |
1613 | { | |
1614 | if (TREE_CODE (*vr0min) == INTEGER_CST) | |
1615 | { | |
1616 | *vr0type = vr1type; | |
1617 | *vr0max = int_const_binop (MINUS_EXPR, *vr0min, | |
1618 | build_int_cst (TREE_TYPE (*vr0min), 1)); | |
1619 | *vr0min = vr1min; | |
1620 | } | |
1621 | else | |
1622 | goto give_up; | |
1623 | } | |
1624 | else | |
1625 | gcc_unreachable (); | |
1626 | } | |
1627 | else | |
1628 | goto give_up; | |
1629 | ||
1630 | return; | |
1631 | ||
1632 | give_up: | |
1633 | *vr0type = VR_VARYING; | |
1634 | *vr0min = NULL_TREE; | |
1635 | *vr0max = NULL_TREE; | |
1636 | } | |
1637 | ||
4ba9fb0a AH |
1638 | /* Helper for meet operation for value ranges. Given two ranges VR0 |
1639 | and VR1, set VR0 to the union of both ranges. This may not be the | |
cca78449 AH |
1640 | smallest possible such range. */ |
1641 | ||
4ba9fb0a AH |
1642 | void |
1643 | irange::legacy_union (irange *vr0, const irange *vr1) | |
cca78449 | 1644 | { |
ea6da7f5 AH |
1645 | gcc_checking_assert (vr0->legacy_mode_p ()); |
1646 | gcc_checking_assert (vr1->legacy_mode_p ()); | |
1647 | ||
cca78449 AH |
1648 | /* VR0 has the resulting range if VR1 is undefined or VR0 is varying. */ |
1649 | if (vr1->undefined_p () | |
1650 | || vr0->varying_p ()) | |
4ba9fb0a | 1651 | return; |
cca78449 AH |
1652 | |
1653 | /* VR1 has the resulting range if VR0 is undefined or VR1 is varying. */ | |
4ba9fb0a AH |
1654 | if (vr0->undefined_p ()) |
1655 | { | |
ea6da7f5 | 1656 | vr0->set (vr1->min (), vr1->max (), vr1->kind ()); |
4ba9fb0a AH |
1657 | return; |
1658 | } | |
ea6da7f5 | 1659 | |
4ba9fb0a AH |
1660 | if (vr1->varying_p ()) |
1661 | { | |
1662 | vr0->set_varying (vr1->type ()); | |
1663 | return; | |
1664 | } | |
cca78449 AH |
1665 | |
1666 | value_range_kind vr0kind = vr0->kind (); | |
1667 | tree vr0min = vr0->min (); | |
1668 | tree vr0max = vr0->max (); | |
ea6da7f5 AH |
1669 | |
1670 | union_ranges (&vr0kind, &vr0min, &vr0max, | |
1671 | vr1->kind (), vr1->min (), vr1->max ()); | |
cca78449 | 1672 | |
554b21ed AH |
1673 | // Pessimize nonzero masks, as we don't support them. |
1674 | m_nonzero_mask = NULL; | |
1675 | ||
cca78449 | 1676 | if (vr0kind == VR_UNDEFINED) |
4ba9fb0a | 1677 | vr0->set_undefined (); |
cca78449 | 1678 | else if (vr0kind == VR_VARYING) |
cca78449 | 1679 | { |
4ba9fb0a AH |
1680 | /* Failed to find an efficient meet. Before giving up and |
1681 | setting the result to VARYING, see if we can at least derive | |
1682 | a non-zero range. */ | |
1683 | if (range_includes_zero_p (vr0) == 0 | |
1684 | && range_includes_zero_p (vr1) == 0) | |
1685 | vr0->set_nonzero (vr0->type ()); | |
1686 | else | |
1687 | vr0->set_varying (vr0->type ()); | |
cca78449 | 1688 | } |
4ba9fb0a AH |
1689 | else |
1690 | vr0->set (vr0min, vr0max, vr0kind); | |
cca78449 AH |
1691 | } |
1692 | ||
1693 | /* Meet operation for value ranges. Given two value ranges VR0 and | |
1694 | VR1, store in VR0 a range that contains both VR0 and VR1. This | |
f3204ce1 AM |
1695 | may not be the smallest possible such range. |
1696 | Return TRUE if the original value changes. */ | |
cca78449 | 1697 | |
f3204ce1 | 1698 | bool |
c13fd1b8 | 1699 | irange::legacy_verbose_union_ (const irange *other) |
cca78449 | 1700 | { |
4ba9fb0a | 1701 | if (legacy_mode_p ()) |
cca78449 | 1702 | { |
ea6da7f5 AH |
1703 | if (!other->legacy_mode_p ()) |
1704 | { | |
1705 | int_range<1> tmp = *other; | |
1706 | legacy_union (this, &tmp); | |
f3204ce1 | 1707 | return true; |
ea6da7f5 | 1708 | } |
4ba9fb0a AH |
1709 | if (dump_file && (dump_flags & TDF_DETAILS)) |
1710 | { | |
1711 | fprintf (dump_file, "Meeting\n "); | |
1712 | dump_value_range (dump_file, this); | |
1713 | fprintf (dump_file, "\nand\n "); | |
1714 | dump_value_range (dump_file, other); | |
1715 | fprintf (dump_file, "\n"); | |
1716 | } | |
cca78449 | 1717 | |
4ba9fb0a | 1718 | legacy_union (this, other); |
cca78449 | 1719 | |
4ba9fb0a AH |
1720 | if (dump_file && (dump_flags & TDF_DETAILS)) |
1721 | { | |
1722 | fprintf (dump_file, "to\n "); | |
1723 | dump_value_range (dump_file, this); | |
1724 | fprintf (dump_file, "\n"); | |
1725 | } | |
f3204ce1 | 1726 | return true; |
4ba9fb0a AH |
1727 | } |
1728 | ||
1729 | if (other->legacy_mode_p ()) | |
cca78449 | 1730 | { |
ea6da7f5 | 1731 | int_range<2> wider = *other; |
f3204ce1 | 1732 | return irange_union (wider); |
cca78449 | 1733 | } |
4ba9fb0a | 1734 | else |
f3204ce1 | 1735 | return irange_union (*other); |
cca78449 AH |
1736 | } |
1737 | ||
1d3d7e88 | 1738 | bool |
c13fd1b8 | 1739 | irange::legacy_verbose_intersect (const irange *other) |
cca78449 | 1740 | { |
4ba9fb0a AH |
1741 | if (legacy_mode_p ()) |
1742 | { | |
ea6da7f5 AH |
1743 | if (!other->legacy_mode_p ()) |
1744 | { | |
1745 | int_range<1> tmp = *other; | |
1746 | legacy_intersect (this, &tmp); | |
1d3d7e88 | 1747 | return true; |
ea6da7f5 | 1748 | } |
4ba9fb0a AH |
1749 | if (dump_file && (dump_flags & TDF_DETAILS)) |
1750 | { | |
1751 | fprintf (dump_file, "Intersecting\n "); | |
1752 | dump_value_range (dump_file, this); | |
1753 | fprintf (dump_file, "\nand\n "); | |
1754 | dump_value_range (dump_file, other); | |
1755 | fprintf (dump_file, "\n"); | |
1756 | } | |
1757 | ||
1758 | legacy_intersect (this, other); | |
1759 | ||
1760 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
1761 | { | |
1762 | fprintf (dump_file, "to\n "); | |
1763 | dump_value_range (dump_file, this); | |
1764 | fprintf (dump_file, "\n"); | |
1765 | } | |
1d3d7e88 | 1766 | return true; |
4ba9fb0a AH |
1767 | } |
1768 | ||
1769 | if (other->legacy_mode_p ()) | |
1770 | { | |
1771 | int_range<2> wider; | |
1772 | wider = *other; | |
1d3d7e88 | 1773 | return irange_intersect (wider); |
4ba9fb0a AH |
1774 | } |
1775 | else | |
1d3d7e88 | 1776 | return irange_intersect (*other); |
cca78449 AH |
1777 | } |
1778 | ||
f3204ce1 AM |
1779 | // Perform an efficient union with R when both ranges have only a single pair. |
1780 | // Excluded are VARYING and UNDEFINED ranges. | |
c106825b AH |
1781 | // |
1782 | // NOTE: It is the caller's responsibility to set the nonzero mask. | |
f3204ce1 AM |
1783 | |
1784 | bool | |
1785 | irange::irange_single_pair_union (const irange &r) | |
1786 | { | |
1787 | gcc_checking_assert (!undefined_p () && !varying_p ()); | |
1788 | gcc_checking_assert (!r.undefined_p () && !varying_p ()); | |
1789 | ||
1790 | signop sign = TYPE_SIGN (TREE_TYPE (m_base[0])); | |
1791 | // Check if current lower bound is also the new lower bound. | |
1792 | if (wi::le_p (wi::to_wide (m_base[0]), wi::to_wide (r.m_base[0]), sign)) | |
1793 | { | |
1794 | // If current upper bound is new upper bound, we're done. | |
1795 | if (wi::le_p (wi::to_wide (r.m_base[1]), wi::to_wide (m_base[1]), sign)) | |
1796 | return false; | |
1797 | // Otherwise R has the new upper bound. | |
1798 | // Check for overlap/touching ranges, or single target range. | |
1799 | if (m_max_ranges == 1 | |
1800 | || wi::to_widest (m_base[1]) + 1 >= wi::to_widest (r.m_base[0])) | |
030a53c6 | 1801 | m_base[1] = r.m_base[1]; |
f3204ce1 AM |
1802 | else |
1803 | { | |
1804 | // This is a dual range result. | |
1805 | m_base[2] = r.m_base[0]; | |
1806 | m_base[3] = r.m_base[1]; | |
1807 | m_num_ranges = 2; | |
1808 | } | |
030a53c6 AH |
1809 | if (varying_compatible_p ()) |
1810 | m_kind = VR_VARYING; | |
f3204ce1 AM |
1811 | return true; |
1812 | } | |
1813 | ||
1814 | // Set the new lower bound to R's lower bound. | |
1815 | tree lb = m_base[0]; | |
1816 | m_base[0] = r.m_base[0]; | |
1817 | ||
1818 | // If R fully contains THIS range, just set the upper bound. | |
1819 | if (wi::ge_p (wi::to_wide (r.m_base[1]), wi::to_wide (m_base[1]), sign)) | |
1820 | m_base[1] = r.m_base[1]; | |
1821 | // Check for overlapping ranges, or target limited to a single range. | |
1822 | else if (m_max_ranges == 1 | |
1823 | || wi::to_widest (r.m_base[1]) + 1 >= wi::to_widest (lb)) | |
1824 | { | |
1825 | // This has the new upper bound, just check for varying. | |
1826 | if (varying_compatible_p ()) | |
1827 | m_kind = VR_VARYING; | |
1828 | } | |
1829 | else | |
1830 | { | |
1831 | // Left with 2 pairs. | |
1832 | m_num_ranges = 2; | |
1833 | m_base[2] = lb; | |
1834 | m_base[3] = m_base[1]; | |
1835 | m_base[1] = r.m_base[1]; | |
1836 | } | |
030a53c6 AH |
1837 | if (varying_compatible_p ()) |
1838 | m_kind = VR_VARYING; | |
f3204ce1 AM |
1839 | return true; |
1840 | } | |
1841 | ||
4ba9fb0a AH |
1842 | // union_ for multi-ranges. |
1843 | ||
f3204ce1 | 1844 | bool |
4ba9fb0a | 1845 | irange::irange_union (const irange &r) |
cca78449 | 1846 | { |
4ba9fb0a AH |
1847 | gcc_checking_assert (!legacy_mode_p () && !r.legacy_mode_p ()); |
1848 | ||
4e82205b | 1849 | if (r.undefined_p ()) |
f3204ce1 | 1850 | return false; |
4ba9fb0a | 1851 | |
4e82205b | 1852 | if (undefined_p ()) |
cca78449 | 1853 | { |
4ba9fb0a | 1854 | operator= (r); |
c106825b AH |
1855 | if (flag_checking) |
1856 | verify_range (); | |
f3204ce1 | 1857 | return true; |
cca78449 AH |
1858 | } |
1859 | ||
4e82205b | 1860 | if (varying_p ()) |
c106825b | 1861 | return false; |
4e82205b AH |
1862 | |
1863 | if (r.varying_p ()) | |
1864 | { | |
c106825b | 1865 | set_varying (type ()); |
4e82205b AH |
1866 | return true; |
1867 | } | |
1868 | ||
c106825b AH |
1869 | // Save the nonzero mask in case the set operations below clobber it. |
1870 | bool ret_nz = union_nonzero_bits (r); | |
1871 | tree saved_nz = m_nonzero_mask; | |
1872 | ||
1873 | // The union_nonzero_bits may have turned things into a varying. | |
1874 | if (varying_p ()) | |
1875 | return true; | |
1876 | ||
f3204ce1 AM |
1877 | // Special case one range union one range. |
1878 | if (m_num_ranges == 1 && r.m_num_ranges == 1) | |
4e82205b AH |
1879 | { |
1880 | bool ret = irange_single_pair_union (r); | |
1881 | set_nonzero_bits (saved_nz); | |
030a53c6 AH |
1882 | if (flag_checking) |
1883 | verify_range (); | |
4e82205b AH |
1884 | return ret || ret_nz; |
1885 | } | |
f3204ce1 AM |
1886 | |
1887 | // If this ranges fully contains R, then we need do nothing. | |
1888 | if (irange_contains_p (r)) | |
4e82205b | 1889 | return ret_nz; |
f3204ce1 | 1890 | |
4ba9fb0a AH |
1891 | // Do not worry about merging and such by reserving twice as many |
1892 | // pairs as needed, and then simply sort the 2 ranges into this | |
1893 | // intermediate form. | |
1894 | // | |
1895 | // The intermediate result will have the property that the beginning | |
1896 | // of each range is <= the beginning of the next range. There may | |
1897 | // be overlapping ranges at this point. I.e. this would be valid | |
1898 | // [-20, 10], [-10, 0], [0, 20], [40, 90] as it satisfies this | |
1899 | // contraint : -20 < -10 < 0 < 40. When the range is rebuilt into r, | |
1900 | // the merge is performed. | |
1901 | // | |
1902 | // [Xi,Yi]..[Xn,Yn] U [Xj,Yj]..[Xm,Ym] --> [Xk,Yk]..[Xp,Yp] | |
d27b7e69 | 1903 | auto_vec<tree, 20> res (m_num_ranges * 2 + r.m_num_ranges * 2); |
4ba9fb0a AH |
1904 | unsigned i = 0, j = 0, k = 0; |
1905 | ||
1906 | while (i < m_num_ranges * 2 && j < r.m_num_ranges * 2) | |
1907 | { | |
1908 | // lower of Xi and Xj is the lowest point. | |
d27b7e69 | 1909 | if (wi::to_widest (m_base[i]) <= wi::to_widest (r.m_base[j])) |
4ba9fb0a | 1910 | { |
d27b7e69 RS |
1911 | res.quick_push (m_base[i]); |
1912 | res.quick_push (m_base[i + 1]); | |
4ba9fb0a AH |
1913 | k += 2; |
1914 | i += 2; | |
1915 | } | |
1916 | else | |
1917 | { | |
d27b7e69 RS |
1918 | res.quick_push (r.m_base[j]); |
1919 | res.quick_push (r.m_base[j + 1]); | |
4ba9fb0a AH |
1920 | k += 2; |
1921 | j += 2; | |
1922 | } | |
1923 | } | |
1924 | for ( ; i < m_num_ranges * 2; i += 2) | |
1925 | { | |
d27b7e69 RS |
1926 | res.quick_push (m_base[i]); |
1927 | res.quick_push (m_base[i + 1]); | |
4ba9fb0a AH |
1928 | k += 2; |
1929 | } | |
1930 | for ( ; j < r.m_num_ranges * 2; j += 2) | |
1931 | { | |
d27b7e69 RS |
1932 | res.quick_push (r.m_base[j]); |
1933 | res.quick_push (r.m_base[j + 1]); | |
4ba9fb0a AH |
1934 | k += 2; |
1935 | } | |
cca78449 | 1936 | |
4ba9fb0a AH |
1937 | // Now normalize the vector removing any overlaps. |
1938 | i = 2; | |
4ba9fb0a | 1939 | for (j = 2; j < k ; j += 2) |
cca78449 | 1940 | { |
4ba9fb0a | 1941 | // Current upper+1 is >= lower bound next pair, then we merge ranges. |
d27b7e69 | 1942 | if (wi::to_widest (res[i - 1]) + 1 >= wi::to_widest (res[j])) |
4ba9fb0a AH |
1943 | { |
1944 | // New upper bounds is greater of current or the next one. | |
d27b7e69 RS |
1945 | if (wi::to_widest (res[j + 1]) > wi::to_widest (res[i - 1])) |
1946 | res[i - 1] = res[j + 1]; | |
4ba9fb0a AH |
1947 | } |
1948 | else | |
1949 | { | |
1950 | // This is a new distinct range, but no point in copying it | |
1951 | // if it is already in the right place. | |
1952 | if (i != j) | |
1953 | { | |
1954 | res[i++] = res[j]; | |
1955 | res[i++] = res[j + 1]; | |
1956 | } | |
1957 | else | |
1958 | i += 2; | |
1959 | } | |
cca78449 | 1960 | } |
4ba9fb0a AH |
1961 | |
1962 | // At this point, the vector should have i ranges, none overlapping. | |
1963 | // Now it simply needs to be copied, and if there are too many | |
1964 | // ranges, merge some. We wont do any analysis as to what the | |
1965 | // "best" merges are, simply combine the final ranges into one. | |
1966 | if (i > m_max_ranges * 2) | |
1967 | { | |
1968 | res[m_max_ranges * 2 - 1] = res[i - 1]; | |
1969 | i = m_max_ranges * 2; | |
1970 | } | |
1971 | ||
1972 | for (j = 0; j < i ; j++) | |
1973 | m_base[j] = res [j]; | |
1974 | m_num_ranges = i / 2; | |
1975 | ||
dc80d5e8 | 1976 | m_kind = VR_RANGE; |
c106825b | 1977 | m_nonzero_mask = saved_nz; |
dc80d5e8 AH |
1978 | normalize_kind (); |
1979 | ||
4ba9fb0a AH |
1980 | if (flag_checking) |
1981 | verify_range (); | |
f3204ce1 | 1982 | return true; |
cca78449 AH |
1983 | } |
1984 | ||
1d3d7e88 | 1985 | // Return TRUE if THIS fully contains R. No undefined or varying cases. |
cca78449 | 1986 | |
1d3d7e88 AM |
1987 | bool |
1988 | irange::irange_contains_p (const irange &r) const | |
1989 | { | |
1990 | gcc_checking_assert (!undefined_p () && !varying_p ()); | |
1991 | gcc_checking_assert (!r.undefined_p () && !varying_p ()); | |
1992 | ||
1993 | // In order for THIS to fully contain R, all of the pairs within R must | |
1994 | // be fully contained by the pairs in this object. | |
1995 | signop sign = TYPE_SIGN (TREE_TYPE(m_base[0])); | |
1996 | unsigned ri = 0; | |
1997 | unsigned i = 0; | |
1998 | tree rl = r.m_base[0]; | |
1999 | tree ru = r.m_base[1]; | |
2000 | tree l = m_base[0]; | |
2001 | tree u = m_base[1]; | |
2002 | while (1) | |
2003 | { | |
2004 | // If r is contained within this range, move to the next R | |
2005 | if (wi::ge_p (wi::to_wide (rl), wi::to_wide (l), sign) | |
2006 | && wi::le_p (wi::to_wide (ru), wi::to_wide (u), sign)) | |
2007 | { | |
2008 | // This pair is OK, Either done, or bump to the next. | |
2009 | if (++ri >= r.num_pairs ()) | |
2010 | return true; | |
2011 | rl = r.m_base[ri * 2]; | |
2012 | ru = r.m_base[ri * 2 + 1]; | |
2013 | continue; | |
2014 | } | |
2015 | // Otherwise, check if this's pair occurs before R's. | |
2016 | if (wi::lt_p (wi::to_wide (u), wi::to_wide (rl), sign)) | |
2017 | { | |
2018 | // THere's still at leats one pair of R left. | |
2019 | if (++i >= num_pairs ()) | |
2020 | return false; | |
2021 | l = m_base[i * 2]; | |
2022 | u = m_base[i * 2 + 1]; | |
2023 | continue; | |
2024 | } | |
2025 | return false; | |
2026 | } | |
2027 | return false; | |
2028 | } | |
2029 | ||
2030 | ||
2031 | // Intersect for multi-ranges. Return TRUE if anything changes. | |
2032 | ||
2033 | bool | |
4ba9fb0a AH |
2034 | irange::irange_intersect (const irange &r) |
2035 | { | |
2036 | gcc_checking_assert (!legacy_mode_p () && !r.legacy_mode_p ()); | |
ad451b02 AM |
2037 | gcc_checking_assert (undefined_p () || r.undefined_p () |
2038 | || range_compatible_p (type (), r.type ())); | |
4ba9fb0a | 2039 | |
4e82205b | 2040 | if (undefined_p ()) |
1d3d7e88 | 2041 | return false; |
4ba9fb0a AH |
2042 | if (r.undefined_p ()) |
2043 | { | |
2044 | set_undefined (); | |
1d3d7e88 | 2045 | return true; |
4ba9fb0a | 2046 | } |
4e82205b AH |
2047 | |
2048 | // Save the nonzero mask in case the set operations below clobber it. | |
2049 | bool ret_nz = intersect_nonzero_bits (r); | |
2050 | tree saved_nz = m_nonzero_mask; | |
2051 | ||
2052 | if (r.varying_p ()) | |
2053 | return ret_nz; | |
2054 | ||
4ba9fb0a AH |
2055 | if (varying_p ()) |
2056 | { | |
2057 | operator= (r); | |
c106825b AH |
2058 | if (saved_nz) |
2059 | set_nonzero_bits (saved_nz); | |
2060 | if (flag_checking) | |
2061 | verify_range (); | |
1d3d7e88 | 2062 | return true; |
4ba9fb0a AH |
2063 | } |
2064 | ||
ad451b02 | 2065 | if (r.num_pairs () == 1) |
4e82205b AH |
2066 | { |
2067 | bool res = intersect (r.lower_bound (), r.upper_bound ()); | |
c106825b AH |
2068 | if (undefined_p ()) |
2069 | return true; | |
2070 | ||
4e82205b AH |
2071 | set_nonzero_bits (saved_nz); |
2072 | return res || saved_nz; | |
2073 | } | |
1d3d7e88 AM |
2074 | |
2075 | // If R fully contains this, then intersection will change nothing. | |
2076 | if (r.irange_contains_p (*this)) | |
4e82205b | 2077 | return ret_nz; |
ad451b02 | 2078 | |
4ba9fb0a AH |
2079 | signop sign = TYPE_SIGN (TREE_TYPE(m_base[0])); |
2080 | unsigned bld_pair = 0; | |
2081 | unsigned bld_lim = m_max_ranges; | |
c5a6c223 | 2082 | int_range_max r2 (*this); |
4ba9fb0a AH |
2083 | unsigned r2_lim = r2.num_pairs (); |
2084 | unsigned i2 = 0; | |
2085 | for (unsigned i = 0; i < r.num_pairs (); ) | |
2086 | { | |
2087 | // If r1's upper is < r2's lower, we can skip r1's pair. | |
2088 | tree ru = r.m_base[i * 2 + 1]; | |
2089 | tree r2l = r2.m_base[i2 * 2]; | |
2090 | if (wi::lt_p (wi::to_wide (ru), wi::to_wide (r2l), sign)) | |
2091 | { | |
2092 | i++; | |
2093 | continue; | |
2094 | } | |
2095 | // Likewise, skip r2's pair if its excluded. | |
2096 | tree r2u = r2.m_base[i2 * 2 + 1]; | |
2097 | tree rl = r.m_base[i * 2]; | |
2098 | if (wi::lt_p (wi::to_wide (r2u), wi::to_wide (rl), sign)) | |
2099 | { | |
2100 | i2++; | |
2101 | if (i2 < r2_lim) | |
2102 | continue; | |
2103 | // No more r2, break. | |
2104 | break; | |
2105 | } | |
2106 | ||
2107 | // Must be some overlap. Find the highest of the lower bounds, | |
2108 | // and set it, unless the build limits lower bounds is already | |
2109 | // set. | |
2110 | if (bld_pair < bld_lim) | |
2111 | { | |
2112 | if (wi::ge_p (wi::to_wide (rl), wi::to_wide (r2l), sign)) | |
2113 | m_base[bld_pair * 2] = rl; | |
2114 | else | |
2115 | m_base[bld_pair * 2] = r2l; | |
2116 | } | |
2117 | else | |
2118 | // Decrease and set a new upper. | |
2119 | bld_pair--; | |
2120 | ||
2121 | // ...and choose the lower of the upper bounds. | |
2122 | if (wi::le_p (wi::to_wide (ru), wi::to_wide (r2u), sign)) | |
2123 | { | |
2124 | m_base[bld_pair * 2 + 1] = ru; | |
2125 | bld_pair++; | |
2126 | // Move past the r1 pair and keep trying. | |
2127 | i++; | |
2128 | continue; | |
2129 | } | |
2130 | else | |
2131 | { | |
2132 | m_base[bld_pair * 2 + 1] = r2u; | |
2133 | bld_pair++; | |
2134 | i2++; | |
2135 | if (i2 < r2_lim) | |
2136 | continue; | |
2137 | // No more r2, break. | |
2138 | break; | |
2139 | } | |
2140 | // r2 has the higher lower bound. | |
2141 | } | |
2142 | ||
2143 | // At the exit of this loop, it is one of 2 things: | |
2144 | // ran out of r1, or r2, but either means we are done. | |
2145 | m_num_ranges = bld_pair; | |
dc80d5e8 AH |
2146 | |
2147 | m_kind = VR_RANGE; | |
4e82205b | 2148 | if (!undefined_p ()) |
c106825b AH |
2149 | m_nonzero_mask = saved_nz; |
2150 | normalize_kind (); | |
dc80d5e8 | 2151 | |
4ba9fb0a AH |
2152 | if (flag_checking) |
2153 | verify_range (); | |
1d3d7e88 AM |
2154 | |
2155 | return true; | |
4ba9fb0a AH |
2156 | } |
2157 | ||
1d3d7e88 | 2158 | |
ad451b02 | 2159 | // Multirange intersect for a specified wide_int [lb, ub] range. |
1d3d7e88 | 2160 | // Return TRUE if intersect changed anything. |
4e82205b AH |
2161 | // |
2162 | // NOTE: It is the caller's responsibility to intersect the nonzero masks. | |
ad451b02 | 2163 | |
1d3d7e88 | 2164 | bool |
ad451b02 AM |
2165 | irange::intersect (const wide_int& lb, const wide_int& ub) |
2166 | { | |
2167 | // Undefined remains undefined. | |
2168 | if (undefined_p ()) | |
1d3d7e88 | 2169 | return false; |
ad451b02 AM |
2170 | |
2171 | if (legacy_mode_p ()) | |
2172 | { | |
2173 | intersect (int_range<1> (type (), lb, ub)); | |
1d3d7e88 | 2174 | return true; |
ad451b02 AM |
2175 | } |
2176 | ||
2177 | tree range_type = type(); | |
2178 | signop sign = TYPE_SIGN (range_type); | |
2179 | ||
2180 | gcc_checking_assert (TYPE_PRECISION (range_type) == wi::get_precision (lb)); | |
2181 | gcc_checking_assert (TYPE_PRECISION (range_type) == wi::get_precision (ub)); | |
2182 | ||
1d3d7e88 AM |
2183 | // If this range is fuly contained, then intersection will do nothing. |
2184 | if (wi::ge_p (lower_bound (), lb, sign) | |
2185 | && wi::le_p (upper_bound (), ub, sign)) | |
2186 | return false; | |
2187 | ||
ad451b02 AM |
2188 | unsigned bld_index = 0; |
2189 | unsigned pair_lim = num_pairs (); | |
2190 | for (unsigned i = 0; i < pair_lim; i++) | |
2191 | { | |
2192 | tree pairl = m_base[i * 2]; | |
2193 | tree pairu = m_base[i * 2 + 1]; | |
2194 | // Once UB is less than a pairs lower bound, we're done. | |
2195 | if (wi::lt_p (ub, wi::to_wide (pairl), sign)) | |
2196 | break; | |
2197 | // if LB is greater than this pairs upper, this pair is excluded. | |
2198 | if (wi::lt_p (wi::to_wide (pairu), lb, sign)) | |
2199 | continue; | |
2200 | ||
2201 | // Must be some overlap. Find the highest of the lower bounds, | |
2202 | // and set it | |
2203 | if (wi::gt_p (lb, wi::to_wide (pairl), sign)) | |
2204 | m_base[bld_index * 2] = wide_int_to_tree (range_type, lb); | |
2205 | else | |
2206 | m_base[bld_index * 2] = pairl; | |
2207 | ||
2208 | // ...and choose the lower of the upper bounds and if the base pair | |
2209 | // has the lower upper bound, need to check next pair too. | |
2210 | if (wi::lt_p (ub, wi::to_wide (pairu), sign)) | |
2211 | { | |
2212 | m_base[bld_index++ * 2 + 1] = wide_int_to_tree (range_type, ub); | |
2213 | break; | |
2214 | } | |
2215 | else | |
2216 | m_base[bld_index++ * 2 + 1] = pairu; | |
2217 | } | |
2218 | ||
2219 | m_num_ranges = bld_index; | |
2220 | ||
2221 | m_kind = VR_RANGE; | |
2222 | normalize_kind (); | |
2223 | ||
2224 | if (flag_checking) | |
2225 | verify_range (); | |
1d3d7e88 | 2226 | return true; |
ad451b02 | 2227 | } |
1d3d7e88 AM |
2228 | |
2229 | ||
2118438f AH |
2230 | // Signed 1-bits are strange. You can't subtract 1, because you can't |
2231 | // represent the number 1. This works around that for the invert routine. | |
2232 | ||
4ba9fb0a AH |
2233 | static wide_int inline |
2234 | subtract_one (const wide_int &x, tree type, wi::overflow_type &overflow) | |
cca78449 | 2235 | { |
4ba9fb0a | 2236 | if (TYPE_SIGN (type) == SIGNED) |
2118438f | 2237 | return wi::add (x, -1, SIGNED, &overflow); |
4ba9fb0a AH |
2238 | else |
2239 | return wi::sub (x, 1, UNSIGNED, &overflow); | |
cca78449 AH |
2240 | } |
2241 | ||
2118438f AH |
2242 | // The analogous function for adding 1. |
2243 | ||
2244 | static wide_int inline | |
2245 | add_one (const wide_int &x, tree type, wi::overflow_type &overflow) | |
2246 | { | |
2247 | if (TYPE_SIGN (type) == SIGNED) | |
2248 | return wi::sub (x, -1, SIGNED, &overflow); | |
2249 | else | |
2250 | return wi::add (x, 1, UNSIGNED, &overflow); | |
2251 | } | |
2252 | ||
2253 | // Return the inverse of a range. | |
cca78449 AH |
2254 | |
2255 | void | |
4ba9fb0a | 2256 | irange::invert () |
cca78449 | 2257 | { |
4ba9fb0a AH |
2258 | if (legacy_mode_p ()) |
2259 | { | |
2260 | // We can't just invert VR_RANGE and VR_ANTI_RANGE because we may | |
2261 | // create non-canonical ranges. Use the constructors instead. | |
2262 | if (m_kind == VR_RANGE) | |
2263 | *this = value_range (min (), max (), VR_ANTI_RANGE); | |
2264 | else if (m_kind == VR_ANTI_RANGE) | |
2265 | *this = value_range (min (), max ()); | |
2266 | else | |
2267 | gcc_unreachable (); | |
2268 | return; | |
2269 | } | |
2270 | ||
db3581c4 | 2271 | gcc_checking_assert (!undefined_p () && !varying_p ()); |
554b21ed | 2272 | m_nonzero_mask = NULL; |
4ba9fb0a AH |
2273 | |
2274 | // We always need one more set of bounds to represent an inverse, so | |
2275 | // if we're at the limit, we can't properly represent things. | |
2276 | // | |
2277 | // For instance, to represent the inverse of a 2 sub-range set | |
2278 | // [5, 10][20, 30], we would need a 3 sub-range set | |
2279 | // [-MIN, 4][11, 19][31, MAX]. | |
2280 | // | |
2281 | // In this case, return the most conservative thing. | |
2282 | // | |
2283 | // However, if any of the extremes of the range are -MIN/+MAX, we | |
2284 | // know we will not need an extra bound. For example: | |
2285 | // | |
2286 | // INVERT([-MIN,20][30,40]) => [21,29][41,+MAX] | |
2287 | // INVERT([-MIN,20][30,MAX]) => [21,29] | |
2288 | tree ttype = type (); | |
2289 | unsigned prec = TYPE_PRECISION (ttype); | |
2290 | signop sign = TYPE_SIGN (ttype); | |
2291 | wide_int type_min = wi::min_value (prec, sign); | |
2292 | wide_int type_max = wi::max_value (prec, sign); | |
2293 | if (m_num_ranges == m_max_ranges | |
2294 | && lower_bound () != type_min | |
2295 | && upper_bound () != type_max) | |
2296 | { | |
2297 | m_base[1] = wide_int_to_tree (ttype, type_max); | |
2298 | m_num_ranges = 1; | |
2299 | return; | |
2300 | } | |
2301 | // The algorithm is as follows. To calculate INVERT ([a,b][c,d]), we | |
2302 | // generate [-MIN, a-1][b+1, c-1][d+1, MAX]. | |
2303 | // | |
2304 | // If there is an over/underflow in the calculation for any | |
2305 | // sub-range, we eliminate that subrange. This allows us to easily | |
2306 | // calculate INVERT([-MIN, 5]) with: [-MIN, -MIN-1][6, MAX]. And since | |
2307 | // we eliminate the underflow, only [6, MAX] remains. | |
2308 | unsigned i = 0; | |
2309 | wi::overflow_type ovf; | |
2310 | // Construct leftmost range. | |
c5a6c223 | 2311 | int_range_max orig_range (*this); |
4ba9fb0a AH |
2312 | unsigned nitems = 0; |
2313 | wide_int tmp; | |
2314 | // If this is going to underflow on the MINUS 1, don't even bother | |
2315 | // checking. This also handles subtracting one from an unsigned 0, | |
2316 | // which doesn't set the underflow bit. | |
2317 | if (type_min != orig_range.lower_bound ()) | |
2318 | { | |
2319 | m_base[nitems++] = wide_int_to_tree (ttype, type_min); | |
2320 | tmp = subtract_one (orig_range.lower_bound (), ttype, ovf); | |
2321 | m_base[nitems++] = wide_int_to_tree (ttype, tmp); | |
2322 | if (ovf) | |
2323 | nitems = 0; | |
2324 | } | |
2325 | i++; | |
2326 | // Construct middle ranges if applicable. | |
2327 | if (orig_range.num_pairs () > 1) | |
2328 | { | |
2329 | unsigned j = i; | |
2330 | for (; j < (orig_range.num_pairs () * 2) - 1; j += 2) | |
2331 | { | |
2332 | // The middle ranges cannot have MAX/MIN, so there's no need | |
2333 | // to check for unsigned overflow on the +1 and -1 here. | |
2334 | tmp = wi::add (wi::to_wide (orig_range.m_base[j]), 1, sign, &ovf); | |
2335 | m_base[nitems++] = wide_int_to_tree (ttype, tmp); | |
2336 | tmp = subtract_one (wi::to_wide (orig_range.m_base[j + 1]), | |
2337 | ttype, ovf); | |
2338 | m_base[nitems++] = wide_int_to_tree (ttype, tmp); | |
2339 | if (ovf) | |
2340 | nitems -= 2; | |
2341 | } | |
2342 | i = j; | |
2343 | } | |
2344 | // Construct rightmost range. | |
2345 | // | |
2346 | // However, if this will overflow on the PLUS 1, don't even bother. | |
2347 | // This also handles adding one to an unsigned MAX, which doesn't | |
2348 | // set the overflow bit. | |
2349 | if (type_max != wi::to_wide (orig_range.m_base[i])) | |
2350 | { | |
2118438f | 2351 | tmp = add_one (wi::to_wide (orig_range.m_base[i]), ttype, ovf); |
4ba9fb0a AH |
2352 | m_base[nitems++] = wide_int_to_tree (ttype, tmp); |
2353 | m_base[nitems++] = wide_int_to_tree (ttype, type_max); | |
2354 | if (ovf) | |
2355 | nitems -= 2; | |
2356 | } | |
2357 | m_num_ranges = nitems / 2; | |
2358 | ||
dc80d5e8 AH |
2359 | // We disallow undefined or varying coming in, so the result can |
2360 | // only be a VR_RANGE. | |
2361 | gcc_checking_assert (m_kind == VR_RANGE); | |
2362 | ||
4ba9fb0a AH |
2363 | if (flag_checking) |
2364 | verify_range (); | |
2365 | } | |
2366 | ||
c106825b AH |
2367 | void |
2368 | irange::set_nonzero_bits (tree mask) | |
2369 | { | |
2370 | gcc_checking_assert (!undefined_p ()); | |
2371 | ||
2372 | if (!mask) | |
2373 | { | |
2374 | if (m_nonzero_mask) | |
2375 | { | |
2376 | m_nonzero_mask = NULL; | |
2377 | // Clearing the mask may have turned a range into VARYING. | |
2378 | normalize_kind (); | |
2379 | } | |
2380 | return; | |
2381 | } | |
2382 | m_nonzero_mask = mask; | |
2383 | // Setting the mask may have turned a VARYING into a range. | |
2384 | if (m_kind == VR_VARYING) | |
2385 | m_kind = VR_RANGE; | |
2386 | ||
2387 | if (flag_checking) | |
2388 | verify_range (); | |
2389 | } | |
2390 | ||
4e82205b AH |
2391 | void |
2392 | irange::set_nonzero_bits (const wide_int_ref &bits) | |
2393 | { | |
2394 | gcc_checking_assert (!undefined_p ()); | |
2395 | ||
2396 | if (bits == -1) | |
2397 | { | |
c106825b | 2398 | set_nonzero_bits (NULL); |
4e82205b AH |
2399 | return; |
2400 | } | |
c106825b | 2401 | set_nonzero_bits (wide_int_to_tree (type (), bits)); |
4e82205b AH |
2402 | } |
2403 | ||
2404 | wide_int | |
2405 | irange::get_nonzero_bits () const | |
2406 | { | |
2407 | gcc_checking_assert (!undefined_p ()); | |
4e82205b AH |
2408 | |
2409 | // Calculate the nonzero bits inherent in the range. | |
2410 | wide_int min = lower_bound (); | |
2411 | wide_int max = upper_bound (); | |
2412 | wide_int xorv = min ^ max; | |
2413 | if (xorv != 0) | |
2414 | { | |
2415 | unsigned prec = TYPE_PRECISION (type ()); | |
2416 | xorv = wi::mask (prec - wi::clz (xorv), false, prec); | |
2417 | } | |
2418 | wide_int mask = min | xorv; | |
2419 | ||
2420 | // Return the nonzero bits augmented by the range. | |
2421 | if (m_nonzero_mask) | |
2422 | return mask & wi::to_wide (m_nonzero_mask); | |
2423 | ||
2424 | return mask; | |
2425 | } | |
2426 | ||
2427 | // Intersect the nonzero bits in R into THIS. | |
2428 | ||
2429 | bool | |
2430 | irange::intersect_nonzero_bits (const irange &r) | |
2431 | { | |
2432 | gcc_checking_assert (!undefined_p () && !r.undefined_p ()); | |
2433 | ||
c106825b | 2434 | if (m_nonzero_mask || r.m_nonzero_mask) |
4e82205b | 2435 | { |
c106825b AH |
2436 | wide_int nz = wi::bit_and (get_nonzero_bits (), |
2437 | r.get_nonzero_bits ()); | |
2438 | set_nonzero_bits (nz); | |
4e82205b AH |
2439 | return true; |
2440 | } | |
c106825b | 2441 | return false; |
4e82205b AH |
2442 | } |
2443 | ||
2444 | // Union the nonzero bits in R into THIS. | |
2445 | ||
2446 | bool | |
2447 | irange::union_nonzero_bits (const irange &r) | |
2448 | { | |
2449 | gcc_checking_assert (!undefined_p () && !r.undefined_p ()); | |
2450 | ||
c106825b | 2451 | if (m_nonzero_mask || r.m_nonzero_mask) |
4e82205b | 2452 | { |
c106825b AH |
2453 | wide_int nz = wi::bit_or (get_nonzero_bits (), |
2454 | r.get_nonzero_bits ()); | |
2455 | set_nonzero_bits (nz); | |
2456 | return true; | |
4e82205b | 2457 | } |
c106825b | 2458 | return false; |
4e82205b AH |
2459 | } |
2460 | ||
cca78449 | 2461 | void |
4f1bce19 | 2462 | dump_value_range (FILE *file, const vrange *vr) |
cca78449 | 2463 | { |
4ba9fb0a | 2464 | vr->dump (file); |
cca78449 AH |
2465 | } |
2466 | ||
4ba9fb0a | 2467 | DEBUG_FUNCTION void |
4f1bce19 | 2468 | debug (const vrange *vr) |
cca78449 | 2469 | { |
4ba9fb0a AH |
2470 | dump_value_range (stderr, vr); |
2471 | fprintf (stderr, "\n"); | |
2472 | } | |
2473 | ||
2474 | DEBUG_FUNCTION void | |
4f1bce19 | 2475 | debug (const vrange &vr) |
4ba9fb0a AH |
2476 | { |
2477 | debug (&vr); | |
cca78449 AH |
2478 | } |
2479 | ||
2480 | DEBUG_FUNCTION void | |
2481 | debug (const value_range *vr) | |
2482 | { | |
2483 | dump_value_range (stderr, vr); | |
4ba9fb0a | 2484 | fprintf (stderr, "\n"); |
cca78449 AH |
2485 | } |
2486 | ||
2487 | DEBUG_FUNCTION void | |
2488 | debug (const value_range &vr) | |
2489 | { | |
2490 | dump_value_range (stderr, &vr); | |
4ba9fb0a | 2491 | fprintf (stderr, "\n"); |
cca78449 AH |
2492 | } |
2493 | ||
2494 | /* Create two value-ranges in *VR0 and *VR1 from the anti-range *AR | |
2495 | so that *VR0 U *VR1 == *AR. Returns true if that is possible, | |
2496 | false otherwise. If *AR can be represented with a single range | |
2497 | *VR1 will be VR_UNDEFINED. */ | |
2498 | ||
2499 | bool | |
2500 | ranges_from_anti_range (const value_range *ar, | |
2501 | value_range *vr0, value_range *vr1) | |
2502 | { | |
2503 | tree type = ar->type (); | |
2504 | ||
2505 | vr0->set_undefined (); | |
2506 | vr1->set_undefined (); | |
2507 | ||
2508 | /* As a future improvement, we could handle ~[0, A] as: [-INF, -1] U | |
2509 | [A+1, +INF]. Not sure if this helps in practice, though. */ | |
2510 | ||
2511 | if (ar->kind () != VR_ANTI_RANGE | |
2512 | || TREE_CODE (ar->min ()) != INTEGER_CST | |
2513 | || TREE_CODE (ar->max ()) != INTEGER_CST | |
2514 | || !vrp_val_min (type) | |
2515 | || !vrp_val_max (type)) | |
2516 | return false; | |
2517 | ||
2518 | if (tree_int_cst_lt (vrp_val_min (type), ar->min ())) | |
2519 | vr0->set (vrp_val_min (type), | |
2520 | wide_int_to_tree (type, wi::to_wide (ar->min ()) - 1)); | |
2521 | if (tree_int_cst_lt (ar->max (), vrp_val_max (type))) | |
2522 | vr1->set (wide_int_to_tree (type, wi::to_wide (ar->max ()) + 1), | |
2523 | vrp_val_max (type)); | |
2524 | if (vr0->undefined_p ()) | |
2525 | { | |
2526 | *vr0 = *vr1; | |
2527 | vr1->set_undefined (); | |
2528 | } | |
2529 | ||
2530 | return !vr0->undefined_p (); | |
2531 | } | |
2532 | ||
2533 | bool | |
4ba9fb0a | 2534 | range_has_numeric_bounds_p (const irange *vr) |
cca78449 | 2535 | { |
4ba9fb0a | 2536 | return (!vr->undefined_p () |
cca78449 AH |
2537 | && TREE_CODE (vr->min ()) == INTEGER_CST |
2538 | && TREE_CODE (vr->max ()) == INTEGER_CST); | |
2539 | } | |
2540 | ||
cca78449 AH |
2541 | /* Return whether VAL is equal to the maximum value of its type. |
2542 | We can't do a simple equality comparison with TYPE_MAX_VALUE because | |
2543 | C typedefs and Ada subtypes can produce types whose TYPE_MAX_VALUE | |
2544 | is not == to the integer constant with the same value in the type. */ | |
2545 | ||
2546 | bool | |
2547 | vrp_val_is_max (const_tree val) | |
2548 | { | |
2549 | tree type_max = vrp_val_max (TREE_TYPE (val)); | |
2550 | return (val == type_max | |
2551 | || (type_max != NULL_TREE | |
2552 | && operand_equal_p (val, type_max, 0))); | |
2553 | } | |
2554 | ||
2555 | /* Return whether VAL is equal to the minimum value of its type. */ | |
2556 | ||
2557 | bool | |
2558 | vrp_val_is_min (const_tree val) | |
2559 | { | |
2560 | tree type_min = vrp_val_min (TREE_TYPE (val)); | |
2561 | return (val == type_min | |
2562 | || (type_min != NULL_TREE | |
2563 | && operand_equal_p (val, type_min, 0))); | |
2564 | } | |
2565 | ||
2566 | /* Return true, if VAL1 and VAL2 are equal values for VRP purposes. */ | |
2567 | ||
2568 | bool | |
2569 | vrp_operand_equal_p (const_tree val1, const_tree val2) | |
2570 | { | |
2571 | if (val1 == val2) | |
2572 | return true; | |
2573 | if (!val1 || !val2 || !operand_equal_p (val1, val2, 0)) | |
2574 | return false; | |
2575 | return true; | |
2576 | } | |
4ba9fb0a | 2577 | |
e53b6e56 | 2578 | // ?? These stubs are for ipa-prop.cc which use a value_range in a |
3c658587 AH |
2579 | // hash_traits. hash-traits.h defines an extern of gt_ggc_mx (T &) |
2580 | // instead of picking up the gt_ggc_mx (T *) version. | |
2581 | void | |
2582 | gt_pch_nx (int_range<1> *&x) | |
2583 | { | |
2584 | return gt_pch_nx ((irange *) x); | |
2585 | } | |
2586 | ||
2587 | void | |
2588 | gt_ggc_mx (int_range<1> *&x) | |
2589 | { | |
2590 | return gt_ggc_mx ((irange *) x); | |
2591 | } | |
4ba9fb0a AH |
2592 | |
2593 | #define DEFINE_INT_RANGE_INSTANCE(N) \ | |
2594 | template int_range<N>::int_range(tree, tree, value_range_kind); \ | |
2595 | template int_range<N>::int_range(tree_node *, \ | |
2596 | const wide_int &, \ | |
2597 | const wide_int &, \ | |
2598 | value_range_kind); \ | |
2599 | template int_range<N>::int_range(tree); \ | |
2600 | template int_range<N>::int_range(const irange &); \ | |
2601 | template int_range<N>::int_range(const int_range &); \ | |
2602 | template int_range<N>& int_range<N>::operator= (const int_range &); | |
2603 | ||
2604 | DEFINE_INT_RANGE_INSTANCE(1) | |
2605 | DEFINE_INT_RANGE_INSTANCE(2) | |
2606 | DEFINE_INT_RANGE_INSTANCE(3) | |
2607 | DEFINE_INT_RANGE_INSTANCE(255) | |
b5cff0db AH |
2608 | |
2609 | #if CHECKING_P | |
2610 | #include "selftest.h" | |
2611 | ||
2612 | namespace selftest | |
2613 | { | |
2614 | #define INT(N) build_int_cst (integer_type_node, (N)) | |
2615 | #define UINT(N) build_int_cstu (unsigned_type_node, (N)) | |
2616 | #define UINT128(N) build_int_cstu (u128_type, (N)) | |
2617 | #define UCHAR(N) build_int_cstu (unsigned_char_type_node, (N)) | |
2618 | #define SCHAR(N) build_int_cst (signed_char_type_node, (N)) | |
2619 | ||
2620 | static int_range<3> | |
2621 | build_range3 (int a, int b, int c, int d, int e, int f) | |
2622 | { | |
2623 | int_range<3> i1 (INT (a), INT (b)); | |
2624 | int_range<3> i2 (INT (c), INT (d)); | |
2625 | int_range<3> i3 (INT (e), INT (f)); | |
2626 | i1.union_ (i2); | |
2627 | i1.union_ (i3); | |
2628 | return i1; | |
2629 | } | |
2630 | ||
2631 | static void | |
2632 | range_tests_irange3 () | |
2633 | { | |
2634 | typedef int_range<3> int_range3; | |
2635 | int_range3 r0, r1, r2; | |
2636 | int_range3 i1, i2, i3; | |
2637 | ||
2638 | // ([10,20] U [5,8]) U [1,3] ==> [1,3][5,8][10,20]. | |
2639 | r0 = int_range3 (INT (10), INT (20)); | |
2640 | r1 = int_range3 (INT (5), INT (8)); | |
2641 | r0.union_ (r1); | |
2642 | r1 = int_range3 (INT (1), INT (3)); | |
2643 | r0.union_ (r1); | |
2644 | ASSERT_TRUE (r0 == build_range3 (1, 3, 5, 8, 10, 20)); | |
2645 | ||
2646 | // [1,3][5,8][10,20] U [-5,0] => [-5,3][5,8][10,20]. | |
2647 | r1 = int_range3 (INT (-5), INT (0)); | |
2648 | r0.union_ (r1); | |
2649 | ASSERT_TRUE (r0 == build_range3 (-5, 3, 5, 8, 10, 20)); | |
2650 | ||
2651 | // [10,20][30,40] U [50,60] ==> [10,20][30,40][50,60]. | |
2652 | r1 = int_range3 (INT (50), INT (60)); | |
2653 | r0 = int_range3 (INT (10), INT (20)); | |
2654 | r0.union_ (int_range3 (INT (30), INT (40))); | |
2655 | r0.union_ (r1); | |
2656 | ASSERT_TRUE (r0 == build_range3 (10, 20, 30, 40, 50, 60)); | |
2657 | // [10,20][30,40][50,60] U [70, 80] ==> [10,20][30,40][50,60][70,80]. | |
2658 | r1 = int_range3 (INT (70), INT (80)); | |
2659 | r0.union_ (r1); | |
2660 | ||
2661 | r2 = build_range3 (10, 20, 30, 40, 50, 60); | |
2662 | r2.union_ (int_range3 (INT (70), INT (80))); | |
2663 | ASSERT_TRUE (r0 == r2); | |
2664 | ||
2665 | // [10,20][30,40][50,60] U [6,35] => [6,40][50,60]. | |
2666 | r0 = build_range3 (10, 20, 30, 40, 50, 60); | |
2667 | r1 = int_range3 (INT (6), INT (35)); | |
2668 | r0.union_ (r1); | |
2669 | r1 = int_range3 (INT (6), INT (40)); | |
2670 | r1.union_ (int_range3 (INT (50), INT (60))); | |
2671 | ASSERT_TRUE (r0 == r1); | |
2672 | ||
2673 | // [10,20][30,40][50,60] U [6,60] => [6,60]. | |
2674 | r0 = build_range3 (10, 20, 30, 40, 50, 60); | |
2675 | r1 = int_range3 (INT (6), INT (60)); | |
2676 | r0.union_ (r1); | |
2677 | ASSERT_TRUE (r0 == int_range3 (INT (6), INT (60))); | |
2678 | ||
2679 | // [10,20][30,40][50,60] U [6,70] => [6,70]. | |
2680 | r0 = build_range3 (10, 20, 30, 40, 50, 60); | |
2681 | r1 = int_range3 (INT (6), INT (70)); | |
2682 | r0.union_ (r1); | |
2683 | ASSERT_TRUE (r0 == int_range3 (INT (6), INT (70))); | |
2684 | ||
2685 | // [10,20][30,40][50,60] U [35,70] => [10,20][30,70]. | |
2686 | r0 = build_range3 (10, 20, 30, 40, 50, 60); | |
2687 | r1 = int_range3 (INT (35), INT (70)); | |
2688 | r0.union_ (r1); | |
2689 | r1 = int_range3 (INT (10), INT (20)); | |
2690 | r1.union_ (int_range3 (INT (30), INT (70))); | |
2691 | ASSERT_TRUE (r0 == r1); | |
2692 | ||
2693 | // [10,20][30,40][50,60] U [15,35] => [10,40][50,60]. | |
2694 | r0 = build_range3 (10, 20, 30, 40, 50, 60); | |
2695 | r1 = int_range3 (INT (15), INT (35)); | |
2696 | r0.union_ (r1); | |
2697 | r1 = int_range3 (INT (10), INT (40)); | |
2698 | r1.union_ (int_range3 (INT (50), INT (60))); | |
2699 | ASSERT_TRUE (r0 == r1); | |
2700 | ||
2701 | // [10,20][30,40][50,60] U [35,35] => [10,20][30,40][50,60]. | |
2702 | r0 = build_range3 (10, 20, 30, 40, 50, 60); | |
2703 | r1 = int_range3 (INT (35), INT (35)); | |
2704 | r0.union_ (r1); | |
2705 | ASSERT_TRUE (r0 == build_range3 (10, 20, 30, 40, 50, 60)); | |
2706 | } | |
2707 | ||
2708 | static void | |
2709 | range_tests_int_range_max () | |
2710 | { | |
2711 | int_range_max big; | |
2712 | unsigned int nrange; | |
2713 | ||
2714 | // Build a huge multi-range range. | |
2715 | for (nrange = 0; nrange < 50; ++nrange) | |
2716 | { | |
2717 | int_range<1> tmp (INT (nrange*10), INT (nrange*10 + 5)); | |
2718 | big.union_ (tmp); | |
2719 | } | |
2720 | ASSERT_TRUE (big.num_pairs () == nrange); | |
2721 | ||
2722 | // Verify that we can copy it without loosing precision. | |
2723 | int_range_max copy (big); | |
2724 | ASSERT_TRUE (copy.num_pairs () == nrange); | |
2725 | ||
2726 | // Inverting it should produce one more sub-range. | |
2727 | big.invert (); | |
2728 | ASSERT_TRUE (big.num_pairs () == nrange + 1); | |
2729 | ||
2730 | int_range<1> tmp (INT (5), INT (37)); | |
2731 | big.intersect (tmp); | |
2732 | ASSERT_TRUE (big.num_pairs () == 4); | |
2733 | ||
2734 | // Test that [10,10][20,20] does NOT contain 15. | |
2735 | { | |
2736 | int_range_max i1 (build_int_cst (integer_type_node, 10), | |
2737 | build_int_cst (integer_type_node, 10)); | |
2738 | int_range_max i2 (build_int_cst (integer_type_node, 20), | |
2739 | build_int_cst (integer_type_node, 20)); | |
2740 | i1.union_ (i2); | |
2741 | ASSERT_FALSE (i1.contains_p (build_int_cst (integer_type_node, 15))); | |
2742 | } | |
2743 | } | |
2744 | ||
2745 | static void | |
2746 | range_tests_legacy () | |
2747 | { | |
2748 | // Test truncating copy to int_range<1>. | |
2749 | int_range<3> big = build_range3 (10, 20, 30, 40, 50, 60); | |
2750 | int_range<1> small = big; | |
2751 | ASSERT_TRUE (small == int_range<1> (INT (10), INT (60))); | |
2752 | ||
2753 | // Test truncating copy to int_range<2>. | |
2754 | int_range<2> medium = big; | |
2755 | ASSERT_TRUE (!medium.undefined_p ()); | |
2756 | ||
2757 | // Test that a truncating copy of [MIN,20][22,40][80,MAX] | |
2758 | // ends up as a conservative anti-range of ~[21,21]. | |
2759 | big = int_range<3> (vrp_val_min (integer_type_node), INT (20)); | |
2760 | big.union_ (int_range<1> (INT (22), INT (40))); | |
2761 | big.union_ (int_range<1> (INT (80), vrp_val_max (integer_type_node))); | |
2762 | small = big; | |
2763 | ASSERT_TRUE (small == int_range<1> (INT (21), INT (21), VR_ANTI_RANGE)); | |
2764 | ||
2765 | // Copying a legacy symbolic to an int_range should normalize the | |
2766 | // symbolic at copy time. | |
2767 | { | |
2768 | tree ssa = make_ssa_name (integer_type_node); | |
2769 | value_range legacy_range (ssa, INT (25)); | |
2770 | int_range<2> copy = legacy_range; | |
2771 | ASSERT_TRUE (copy == int_range<2> (vrp_val_min (integer_type_node), | |
2772 | INT (25))); | |
2773 | ||
2774 | // Test that copying ~[abc_23, abc_23] to a multi-range yields varying. | |
2775 | legacy_range = value_range (ssa, ssa, VR_ANTI_RANGE); | |
2776 | copy = legacy_range; | |
2777 | ASSERT_TRUE (copy.varying_p ()); | |
2778 | } | |
ca8cc827 AH |
2779 | |
2780 | // VARYING of different sizes should not be equal. | |
41ddc5b0 AH |
2781 | tree big_type = build_nonstandard_integer_type (32, 1); |
2782 | tree small_type = build_nonstandard_integer_type (16, 1); | |
2783 | int_range_max r0 (big_type); | |
2784 | int_range_max r1 (small_type); | |
ca8cc827 | 2785 | ASSERT_TRUE (r0 != r1); |
41ddc5b0 AH |
2786 | value_range vr0 (big_type); |
2787 | int_range_max vr1 (small_type); | |
ca8cc827 | 2788 | ASSERT_TRUE (vr0 != vr1); |
b5cff0db AH |
2789 | } |
2790 | ||
3d3470e2 AH |
2791 | // Simulate -fstrict-enums where the domain of a type is less than the |
2792 | // underlying type. | |
2793 | ||
2794 | static void | |
2795 | range_tests_strict_enum () | |
2796 | { | |
2797 | // The enum can only hold [0, 3]. | |
2798 | tree rtype = copy_node (unsigned_type_node); | |
2799 | TYPE_MIN_VALUE (rtype) = build_int_cstu (rtype, 0); | |
2800 | TYPE_MAX_VALUE (rtype) = build_int_cstu (rtype, 3); | |
2801 | ||
2802 | // Test that even though vr1 covers the strict enum domain ([0, 3]), | |
2803 | // it does not cover the domain of the underlying type. | |
2804 | int_range<1> vr1 (build_int_cstu (rtype, 0), build_int_cstu (rtype, 1)); | |
2805 | int_range<1> vr2 (build_int_cstu (rtype, 2), build_int_cstu (rtype, 3)); | |
2806 | vr1.union_ (vr2); | |
2807 | ASSERT_TRUE (vr1 == int_range<1> (build_int_cstu (rtype, 0), | |
2808 | build_int_cstu (rtype, 3))); | |
2809 | ASSERT_FALSE (vr1.varying_p ()); | |
2810 | ||
2811 | // Test that copying to a multi-range does not change things. | |
2812 | int_range<2> ir1 (vr1); | |
2813 | ASSERT_TRUE (ir1 == vr1); | |
2814 | ASSERT_FALSE (ir1.varying_p ()); | |
2815 | ||
2816 | // The same test as above, but using TYPE_{MIN,MAX}_VALUE instead of [0,3]. | |
2817 | vr1 = int_range<1> (TYPE_MIN_VALUE (rtype), TYPE_MAX_VALUE (rtype)); | |
2818 | ir1 = vr1; | |
2819 | ASSERT_TRUE (ir1 == vr1); | |
2820 | ASSERT_FALSE (ir1.varying_p ()); | |
2821 | } | |
2822 | ||
b5cff0db AH |
2823 | static void |
2824 | range_tests_misc () | |
2825 | { | |
2826 | tree u128_type = build_nonstandard_integer_type (128, /*unsigned=*/1); | |
2827 | int_range<1> i1, i2, i3; | |
2828 | int_range<1> r0, r1, rold; | |
2829 | ||
2830 | // Test 1-bit signed integer union. | |
2831 | // [-1,-1] U [0,0] = VARYING. | |
2832 | tree one_bit_type = build_nonstandard_integer_type (1, 0); | |
2833 | tree one_bit_min = vrp_val_min (one_bit_type); | |
2834 | tree one_bit_max = vrp_val_max (one_bit_type); | |
2835 | { | |
2836 | int_range<2> min (one_bit_min, one_bit_min); | |
2837 | int_range<2> max (one_bit_max, one_bit_max); | |
2838 | max.union_ (min); | |
2839 | ASSERT_TRUE (max.varying_p ()); | |
2840 | } | |
2841 | ||
2842 | // Test inversion of 1-bit signed integers. | |
2843 | { | |
2844 | int_range<2> min (one_bit_min, one_bit_min); | |
2845 | int_range<2> max (one_bit_max, one_bit_max); | |
2846 | int_range<2> t; | |
2847 | t = min; | |
2848 | t.invert (); | |
2849 | ASSERT_TRUE (t == max); | |
2850 | t = max; | |
2851 | t.invert (); | |
2852 | ASSERT_TRUE (t == min); | |
2853 | } | |
2854 | ||
2855 | // Test that NOT(255) is [0..254] in 8-bit land. | |
2856 | int_range<1> not_255 (UCHAR (255), UCHAR (255), VR_ANTI_RANGE); | |
2857 | ASSERT_TRUE (not_255 == int_range<1> (UCHAR (0), UCHAR (254))); | |
2858 | ||
2859 | // Test that NOT(0) is [1..255] in 8-bit land. | |
2860 | int_range<1> not_zero = range_nonzero (unsigned_char_type_node); | |
2861 | ASSERT_TRUE (not_zero == int_range<1> (UCHAR (1), UCHAR (255))); | |
2862 | ||
2863 | // Check that [0,127][0x..ffffff80,0x..ffffff] | |
2864 | // => ~[128, 0x..ffffff7f]. | |
2865 | r0 = int_range<1> (UINT128 (0), UINT128 (127)); | |
2866 | tree high = build_minus_one_cst (u128_type); | |
2867 | // low = -1 - 127 => 0x..ffffff80. | |
2868 | tree low = fold_build2 (MINUS_EXPR, u128_type, high, UINT128(127)); | |
2869 | r1 = int_range<1> (low, high); // [0x..ffffff80, 0x..ffffffff] | |
2870 | // r0 = [0,127][0x..ffffff80,0x..fffffff]. | |
2871 | r0.union_ (r1); | |
2872 | // r1 = [128, 0x..ffffff7f]. | |
2873 | r1 = int_range<1> (UINT128(128), | |
2874 | fold_build2 (MINUS_EXPR, u128_type, | |
2875 | build_minus_one_cst (u128_type), | |
2876 | UINT128(128))); | |
2877 | r0.invert (); | |
2878 | ASSERT_TRUE (r0 == r1); | |
2879 | ||
2880 | r0.set_varying (integer_type_node); | |
2881 | tree minint = wide_int_to_tree (integer_type_node, r0.lower_bound ()); | |
2882 | tree maxint = wide_int_to_tree (integer_type_node, r0.upper_bound ()); | |
2883 | ||
2884 | r0.set_varying (short_integer_type_node); | |
2885 | ||
2886 | r0.set_varying (unsigned_type_node); | |
2887 | tree maxuint = wide_int_to_tree (unsigned_type_node, r0.upper_bound ()); | |
2888 | ||
2889 | // Check that ~[0,5] => [6,MAX] for unsigned int. | |
2890 | r0 = int_range<1> (UINT (0), UINT (5)); | |
2891 | r0.invert (); | |
2892 | ASSERT_TRUE (r0 == int_range<1> (UINT(6), maxuint)); | |
2893 | ||
2894 | // Check that ~[10,MAX] => [0,9] for unsigned int. | |
2895 | r0 = int_range<1> (UINT(10), maxuint); | |
2896 | r0.invert (); | |
2897 | ASSERT_TRUE (r0 == int_range<1> (UINT (0), UINT (9))); | |
2898 | ||
2899 | // Check that ~[0,5] => [6,MAX] for unsigned 128-bit numbers. | |
2900 | r0 = int_range<1> (UINT128 (0), UINT128 (5), VR_ANTI_RANGE); | |
2901 | r1 = int_range<1> (UINT128(6), build_minus_one_cst (u128_type)); | |
2902 | ASSERT_TRUE (r0 == r1); | |
2903 | ||
2904 | // Check that [~5] is really [-MIN,4][6,MAX]. | |
2905 | r0 = int_range<1> (INT (5), INT (5), VR_ANTI_RANGE); | |
2906 | r1 = int_range<1> (minint, INT (4)); | |
2907 | r1.union_ (int_range<1> (INT (6), maxint)); | |
2908 | ASSERT_FALSE (r1.undefined_p ()); | |
2909 | ASSERT_TRUE (r0 == r1); | |
2910 | ||
2911 | r1 = int_range<1> (INT (5), INT (5)); | |
2912 | int_range<1> r2 (r1); | |
2913 | ASSERT_TRUE (r1 == r2); | |
2914 | ||
2915 | r1 = int_range<1> (INT (5), INT (10)); | |
2916 | ||
2917 | r1 = int_range<1> (integer_type_node, | |
2918 | wi::to_wide (INT (5)), wi::to_wide (INT (10))); | |
2919 | ASSERT_TRUE (r1.contains_p (INT (7))); | |
2920 | ||
2921 | r1 = int_range<1> (SCHAR (0), SCHAR (20)); | |
2922 | ASSERT_TRUE (r1.contains_p (SCHAR(15))); | |
2923 | ASSERT_FALSE (r1.contains_p (SCHAR(300))); | |
2924 | ||
2925 | // NOT([10,20]) ==> [-MIN,9][21,MAX]. | |
2926 | r0 = r1 = int_range<1> (INT (10), INT (20)); | |
2927 | r2 = int_range<1> (minint, INT(9)); | |
2928 | r2.union_ (int_range<1> (INT(21), maxint)); | |
2929 | ASSERT_FALSE (r2.undefined_p ()); | |
2930 | r1.invert (); | |
2931 | ASSERT_TRUE (r1 == r2); | |
2932 | // Test that NOT(NOT(x)) == x. | |
2933 | r2.invert (); | |
2934 | ASSERT_TRUE (r0 == r2); | |
2935 | ||
2936 | // Test that booleans and their inverse work as expected. | |
2937 | r0 = range_zero (boolean_type_node); | |
2938 | ASSERT_TRUE (r0 == int_range<1> (build_zero_cst (boolean_type_node), | |
2939 | build_zero_cst (boolean_type_node))); | |
2940 | r0.invert (); | |
2941 | ASSERT_TRUE (r0 == int_range<1> (build_one_cst (boolean_type_node), | |
2942 | build_one_cst (boolean_type_node))); | |
2943 | ||
2944 | // Make sure NULL and non-NULL of pointer types work, and that | |
2945 | // inverses of them are consistent. | |
2946 | tree voidp = build_pointer_type (void_type_node); | |
2947 | r0 = range_zero (voidp); | |
2948 | r1 = r0; | |
2949 | r0.invert (); | |
2950 | r0.invert (); | |
2951 | ASSERT_TRUE (r0 == r1); | |
2952 | ||
2953 | // [10,20] U [15, 30] => [10, 30]. | |
2954 | r0 = int_range<1> (INT (10), INT (20)); | |
2955 | r1 = int_range<1> (INT (15), INT (30)); | |
2956 | r0.union_ (r1); | |
2957 | ASSERT_TRUE (r0 == int_range<1> (INT (10), INT (30))); | |
2958 | ||
2959 | // [15,40] U [] => [15,40]. | |
2960 | r0 = int_range<1> (INT (15), INT (40)); | |
2961 | r1.set_undefined (); | |
2962 | r0.union_ (r1); | |
2963 | ASSERT_TRUE (r0 == int_range<1> (INT (15), INT (40))); | |
2964 | ||
2965 | // [10,20] U [10,10] => [10,20]. | |
2966 | r0 = int_range<1> (INT (10), INT (20)); | |
2967 | r1 = int_range<1> (INT (10), INT (10)); | |
2968 | r0.union_ (r1); | |
2969 | ASSERT_TRUE (r0 == int_range<1> (INT (10), INT (20))); | |
2970 | ||
2971 | // [10,20] U [9,9] => [9,20]. | |
2972 | r0 = int_range<1> (INT (10), INT (20)); | |
2973 | r1 = int_range<1> (INT (9), INT (9)); | |
2974 | r0.union_ (r1); | |
2975 | ASSERT_TRUE (r0 == int_range<1> (INT (9), INT (20))); | |
2976 | ||
2977 | // [10,20] ^ [15,30] => [15,20]. | |
2978 | r0 = int_range<1> (INT (10), INT (20)); | |
2979 | r1 = int_range<1> (INT (15), INT (30)); | |
2980 | r0.intersect (r1); | |
2981 | ASSERT_TRUE (r0 == int_range<1> (INT (15), INT (20))); | |
2982 | ||
2983 | // Test the internal sanity of wide_int's wrt HWIs. | |
2984 | ASSERT_TRUE (wi::max_value (TYPE_PRECISION (boolean_type_node), | |
2985 | TYPE_SIGN (boolean_type_node)) | |
2986 | == wi::uhwi (1, TYPE_PRECISION (boolean_type_node))); | |
2987 | ||
2988 | // Test zero_p(). | |
2989 | r0 = int_range<1> (INT (0), INT (0)); | |
2990 | ASSERT_TRUE (r0.zero_p ()); | |
2991 | ||
2992 | // Test nonzero_p(). | |
2993 | r0 = int_range<1> (INT (0), INT (0)); | |
2994 | r0.invert (); | |
2995 | ASSERT_TRUE (r0.nonzero_p ()); | |
2996 | ||
2997 | // test legacy interaction | |
2998 | // r0 = ~[1,1] | |
2999 | r0 = int_range<1> (UINT (1), UINT (1), VR_ANTI_RANGE); | |
3000 | // r1 = ~[3,3] | |
3001 | r1 = int_range<1> (UINT (3), UINT (3), VR_ANTI_RANGE); | |
3002 | ||
3003 | // vv = [0,0][2,2][4, MAX] | |
3004 | int_range<3> vv = r0; | |
3005 | vv.intersect (r1); | |
3006 | ||
3007 | ASSERT_TRUE (vv.contains_p (UINT (2))); | |
3008 | ASSERT_TRUE (vv.num_pairs () == 3); | |
3009 | ||
3010 | // create r0 as legacy [1,1] | |
3011 | r0 = int_range<1> (UINT (1), UINT (1)); | |
3012 | // And union it with [0,0][2,2][4,MAX] multi range | |
3013 | r0.union_ (vv); | |
3014 | // The result should be [0,2][4,MAX], or ~[3,3] but it must contain 2 | |
3015 | ASSERT_TRUE (r0.contains_p (UINT (2))); | |
3016 | } | |
3017 | ||
c106825b AH |
3018 | static void |
3019 | range_tests_nonzero_bits () | |
3020 | { | |
3021 | int_range<2> r0, r1; | |
3022 | ||
3023 | // Adding nonzero bits to a varying drops the varying. | |
3024 | r0.set_varying (integer_type_node); | |
3025 | r0.set_nonzero_bits (255); | |
3026 | ASSERT_TRUE (!r0.varying_p ()); | |
3027 | // Dropping the nonzero bits brings us back to varying. | |
3028 | r0.set_nonzero_bits (-1); | |
3029 | ASSERT_TRUE (r0.varying_p ()); | |
3030 | ||
3031 | // Test contains_p with nonzero bits. | |
3032 | r0.set_zero (integer_type_node); | |
3033 | ASSERT_TRUE (r0.contains_p (INT (0))); | |
3034 | ASSERT_FALSE (r0.contains_p (INT (1))); | |
3035 | r0.set_nonzero_bits (0xfe); | |
3036 | ASSERT_FALSE (r0.contains_p (INT (0x100))); | |
3037 | ASSERT_FALSE (r0.contains_p (INT (0x3))); | |
3038 | ||
3039 | // Union of nonzero bits. | |
3040 | r0.set_varying (integer_type_node); | |
3041 | r0.set_nonzero_bits (0xf0); | |
3042 | r1.set_varying (integer_type_node); | |
3043 | r1.set_nonzero_bits (0xf); | |
3044 | r0.union_ (r1); | |
3045 | ASSERT_TRUE (r0.get_nonzero_bits () == 0xff); | |
3046 | ||
3047 | // Union where the mask of nonzero bits is implicit from the range. | |
3048 | r0.set_varying (integer_type_node); | |
3049 | r0.set_nonzero_bits (0xf00); | |
3050 | r1.set_zero (integer_type_node); // nonzero mask is implicitly 0 | |
3051 | r0.union_ (r1); | |
3052 | ASSERT_TRUE (r0.get_nonzero_bits () == 0xf00); | |
3053 | ||
3054 | // Intersect of nonzero bits. | |
3055 | r0.set (INT (0), INT (255)); | |
3056 | r0.set_nonzero_bits (0xfe); | |
3057 | r1.set_varying (integer_type_node); | |
3058 | r1.set_nonzero_bits (0xf0); | |
3059 | r0.intersect (r1); | |
3060 | ASSERT_TRUE (r0.get_nonzero_bits () == 0xf0); | |
3061 | ||
3062 | // Intersect where the mask of nonzero bits is implicit from the range. | |
3063 | r0.set_varying (integer_type_node); | |
3064 | r1.set (INT (0), INT (255)); | |
3065 | r0.intersect (r1); | |
3066 | ASSERT_TRUE (r0.get_nonzero_bits () == 0xff); | |
3067 | ||
3068 | // The union of a mask of 0xff..ffff00 with a mask of 0xff spans the | |
3069 | // entire domain, and makes the range a varying. | |
3070 | r0.set_varying (integer_type_node); | |
3071 | wide_int x = wi::shwi (0xff, TYPE_PRECISION (integer_type_node)); | |
3072 | x = wi::bit_not (x); | |
3073 | r0.set_nonzero_bits (x); // 0xff..ff00 | |
3074 | r1.set_varying (integer_type_node); | |
3075 | r1.set_nonzero_bits (0xff); | |
3076 | r0.union_ (r1); | |
3077 | ASSERT_TRUE (r0.varying_p ()); | |
3078 | } | |
3079 | ||
b5cff0db AH |
3080 | void |
3081 | range_tests () | |
3082 | { | |
3083 | range_tests_legacy (); | |
3084 | range_tests_irange3 (); | |
3085 | range_tests_int_range_max (); | |
3d3470e2 | 3086 | range_tests_strict_enum (); |
c106825b | 3087 | range_tests_nonzero_bits (); |
b5cff0db AH |
3088 | range_tests_misc (); |
3089 | } | |
3090 | ||
3091 | } // namespace selftest | |
3092 | ||
3093 | #endif // CHECKING_P |