Line data Source code
1 : /* Support routines for value ranges.
2 : Copyright (C) 2019-2026 Free Software Foundation, Inc.
3 : Major hacks by Aldy Hernandez <aldyh@redhat.com> and
4 : Andrew MacLeod <amacleod@redhat.com>.
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"
30 : #include "value-range-pretty-print.h"
31 : #include "fold-const.h"
32 : #include "gimple-range.h"
33 :
34 : // Return the bitmask inherent in a range : TYPE [MIN, MAX].
35 : // This used to be get_bitmask_from_range ().
36 :
37 1193721397 : irange_bitmask::irange_bitmask (tree type,
38 1193721397 : const wide_int &min, const wide_int &max)
39 : {
40 1193721397 : unsigned prec = TYPE_PRECISION (type);
41 : // All the bits of a singleton are known.
42 1193721397 : if (min == max)
43 : {
44 165142430 : m_mask = wi::zero (prec);
45 165142430 : m_value = min;
46 : }
47 : else
48 : {
49 1028578967 : wide_int xorv = min ^ max;
50 : // Mask will have leading zeros for all leading bits that are
51 : // common, both zeros and ones.
52 1028578967 : m_mask = wi::mask (prec - wi::clz (xorv), false, prec);
53 : // Now set value to those bits which are known, and zero the rest.
54 1028589151 : m_value = ~m_mask & min;
55 1028578967 : }
56 1193721397 : }
57 :
58 : // Return a range in R of TYPE for this bitmask which encompasses
59 : // a set of valid values which are allowable for this bitmask/value
60 : // combination. If false is returned, no range was set.
61 :
62 : bool
63 123624624 : irange_bitmask::range_from_mask (irange &r, tree type) const
64 : {
65 123624624 : if (unknown_p ())
66 : return false;
67 :
68 247101421 : gcc_checking_assert ((value () & mask ()) == 0);
69 123550411 : unsigned popcount = wi::popcount (mask ());
70 :
71 : // For 0, 1 or 2 bits set, create a range with only the allowed values.
72 123550411 : if (popcount <= 2)
73 : {
74 : // VALUE is always a valid range.
75 24165086 : r.set (type, value (), value ());
76 : // If there are bits in mask, (VALUE | MASK) is also valid.
77 24165065 : if (popcount >= 1)
78 11393332 : r.union_ (int_range<1> (type, value () | mask (), value () | mask ()));
79 : // If there are 2 bits set, add the other 2 possible values.
80 11393252 : if (popcount == 2)
81 : {
82 : // Extract the two 1-bit masks into lb and ub.
83 4815913 : wide_int lb = mask () & -mask (); // Lowest set bit.
84 4815913 : wide_int ub = mask () & (mask () - 1); // The other bit.
85 4815913 : r.union_ (int_range<1> (type, value () | lb, value () | lb));
86 4815913 : r.union_ (int_range<1> (type, value () | ub, value () | ub));
87 4815913 : }
88 24165065 : return true;
89 : }
90 :
91 : // Otherwise, calculate the valid range allowed by the bitmask.
92 99385346 : int prec = TYPE_PRECISION (type);
93 99385924 : wide_int ub = mask () | value ();
94 99385346 : wide_int sign_bit = wi::one (prec) << (prec - 1);
95 99385346 : wide_int sign_mask = mask () & sign_bit;
96 99385346 : wide_int sign_value = value () & sign_bit;
97 : // Create a lower and upper bound.
98 : // If unsigned, or the sign is known to be positive, create [lb, ub]
99 99385346 : if (TYPE_SIGN (type) == UNSIGNED || (sign_mask == 0 && sign_value == 0))
100 92556833 : r.set (type, value (), mask () | value ());
101 : // If the sign bit is KNOWN to be 1, we have a completely negative range.
102 6830705 : else if (sign_mask == 0 && sign_value != 0)
103 645724 : r.set (type, value (), value () | (mask () & ~sign_bit));
104 : else
105 : {
106 : // Otherwise there are 2 ranges, a negative and positive interval.
107 6185011 : wide_int neg_base = value () | sign_bit;
108 6185036 : wide_int pos_mask = mask () & ~sign_bit;
109 6185011 : r.set (type, neg_base , neg_base | pos_mask);
110 6185086 : r.union_ (int_range<1> (type, value (), value () | pos_mask));
111 6185036 : }
112 :
113 : // If the mask doesn't have a trailing zero, there is nothing else to filter.
114 99385346 : int z = wi::ctz (mask ());
115 99385346 : if (z == 0)
116 : return true;
117 :
118 : // Remove the [0, X] values which the trailing-zero mask rules out.
119 : // For example, if z == 4, the mask is 0xFFF0, and the lowest 4 bits
120 : // define the range [0, 15]. Only (value & low_mask) is allowed.
121 30229551 : ub = (wi::one (prec) << z) - 1; // Upper bound of range.
122 30229532 : int_range<4> mask_range (type, wi::zero (prec), ub);
123 : // Remove the valid value from the excluded range and form an anti-range.
124 30229532 : wide_int allow = value () & ub;
125 30229532 : mask_range.intersect (int_range<2> (type, allow, allow, VR_ANTI_RANGE));
126 30229532 : mask_range.invert ();
127 30229532 : r.intersect (mask_range);
128 :
129 30229532 : if (TYPE_SIGN (type) == SIGNED)
130 : {
131 : // For signed negative values, find the lowest value with trailing zeros.
132 : // This forms a range such as [-512, -1] for z=9.
133 11310901 : wide_int lb = -(wi::one (prec) << z);
134 11310901 : int_range<4> mask_range (type, lb, wi::minus_one (prec));
135 : // Remove the one allowed value from that set.
136 11310901 : wide_int allow = value () | lb;
137 11310901 : mask_range.intersect (int_range<2> (type, allow, allow, VR_ANTI_RANGE));
138 11310901 : mask_range.invert ();
139 11310901 : r.intersect (mask_range);
140 11310920 : }
141 30229532 : return true;
142 129616612 : }
143 :
144 :
145 : void
146 38066 : irange::accept (const vrange_visitor &v) const
147 : {
148 38066 : v.visit (*this);
149 38066 : }
150 :
151 : void
152 23126 : value_range::dump (FILE *out) const
153 : {
154 23126 : if (m_vrange)
155 23126 : m_vrange->dump (out);
156 : else
157 0 : fprintf (out, "NULL");
158 23126 : }
159 :
160 : DEBUG_FUNCTION void
161 0 : debug (const value_range &r)
162 : {
163 0 : r.dump (stderr);
164 0 : fprintf (stderr, "\n");
165 0 : }
166 :
167 : DEBUG_FUNCTION void
168 0 : debug (const irange_bitmask &bm)
169 : {
170 0 : bm.dump (stderr);
171 0 : fprintf (stderr, "\n");
172 0 : }
173 :
174 : // Definitions for unsupported_range.
175 :
176 : void
177 575 : unsupported_range::accept (const vrange_visitor &v) const
178 : {
179 575 : v.visit (*this);
180 575 : }
181 :
182 : void
183 0 : vrange::update_bitmask (const class irange_bitmask &)
184 : {
185 0 : }
186 :
187 : irange_bitmask
188 0 : vrange::get_bitmask () const
189 : {
190 : // Return all unknown bits for the given precision.
191 0 : return irange_bitmask (TYPE_PRECISION (type ()));
192 : }
193 :
194 : bool
195 0 : unsupported_range::contains_p (tree) const
196 : {
197 0 : return varying_p ();
198 : }
199 :
200 : bool
201 1060528 : unsupported_range::singleton_p (tree *) const
202 : {
203 1060528 : return false;
204 : }
205 :
206 : void
207 0 : unsupported_range::set (tree min, tree, value_range_kind)
208 : {
209 0 : set_varying (TREE_TYPE (min));
210 0 : }
211 :
212 : tree
213 0 : unsupported_range::type () const
214 : {
215 0 : return void_type_node;
216 : }
217 :
218 : bool
219 0 : unsupported_range::supports_type_p (const_tree) const
220 : {
221 0 : return false;
222 : }
223 :
224 : void
225 108450437 : unsupported_range::set_undefined ()
226 : {
227 108450437 : m_kind = VR_UNDEFINED;
228 108450437 : }
229 :
230 : void
231 3290474 : unsupported_range::set_varying (tree)
232 : {
233 3290474 : m_kind = VR_VARYING;
234 3290474 : }
235 :
236 : bool
237 0 : unsupported_range::union_ (const vrange &v)
238 : {
239 0 : const unsupported_range &r = as_a <unsupported_range> (v);
240 :
241 0 : if (r.undefined_p () || varying_p ())
242 : return false;
243 0 : if (undefined_p () || r.varying_p ())
244 : {
245 0 : operator= (r);
246 0 : return true;
247 : }
248 0 : gcc_unreachable ();
249 : return false;
250 : }
251 :
252 : bool
253 0 : unsupported_range::intersect (const vrange &v)
254 : {
255 0 : const unsupported_range &r = as_a <unsupported_range> (v);
256 :
257 0 : if (undefined_p () || r.varying_p ())
258 : return false;
259 0 : if (r.undefined_p ())
260 : {
261 0 : set_undefined ();
262 0 : return true;
263 : }
264 0 : if (varying_p ())
265 : {
266 0 : operator= (r);
267 0 : return true;
268 : }
269 0 : gcc_unreachable ();
270 : return false;
271 : }
272 :
273 : bool
274 0 : unsupported_range::zero_p () const
275 : {
276 0 : return false;
277 : }
278 :
279 : bool
280 0 : unsupported_range::nonzero_p () const
281 : {
282 0 : return false;
283 : }
284 :
285 : void
286 0 : unsupported_range::set_nonzero (tree type)
287 : {
288 0 : set_varying (type);
289 0 : }
290 :
291 : void
292 0 : unsupported_range::set_zero (tree type)
293 : {
294 0 : set_varying (type);
295 0 : }
296 :
297 : void
298 0 : unsupported_range::set_nonnegative (tree type)
299 : {
300 0 : set_varying (type);
301 0 : }
302 :
303 : bool
304 0 : unsupported_range::fits_p (const vrange &) const
305 : {
306 0 : return true;
307 : }
308 :
309 : unsupported_range &
310 865181 : unsupported_range::operator= (const unsupported_range &r)
311 : {
312 865181 : if (r.undefined_p ())
313 865181 : set_undefined ();
314 0 : else if (r.varying_p ())
315 0 : set_varying (void_type_node);
316 : else
317 0 : gcc_unreachable ();
318 865181 : return *this;
319 : }
320 :
321 : tree
322 0 : unsupported_range::lbound () const
323 : {
324 0 : return NULL;
325 : }
326 :
327 : tree
328 0 : unsupported_range::ubound () const
329 : {
330 0 : return NULL;
331 : }
332 :
333 : // Assignment operator for generic ranges. Copying incompatible types
334 : // is not allowed.
335 :
336 : vrange &
337 9874994 : vrange::operator= (const vrange &src)
338 : {
339 9874994 : if (is_a <irange> (src))
340 8815270 : as_a <irange> (*this) = as_a <irange> (src);
341 1059724 : else if (is_a <prange> (src))
342 793399 : as_a <prange> (*this) = as_a <prange> (src);
343 266325 : else if (is_a <frange> (src))
344 266325 : as_a <frange> (*this) = as_a <frange> (src);
345 : else
346 : {
347 0 : gcc_checking_assert (is_a <unsupported_range> (src));
348 0 : m_kind = src.m_kind;
349 : }
350 9874994 : return *this;
351 : }
352 :
353 : // Equality operator for generic ranges.
354 :
355 : bool
356 40474682 : vrange::operator== (const vrange &src) const
357 : {
358 40474682 : if (is_a <irange> (src))
359 35224659 : return as_a <irange> (*this) == as_a <irange> (src);
360 5250023 : if (is_a <prange> (src))
361 5199925 : return as_a <prange> (*this) == as_a <prange> (src);
362 50098 : if (is_a <frange> (src))
363 50098 : return as_a <frange> (*this) == as_a <frange> (src);
364 0 : gcc_unreachable ();
365 : }
366 :
367 : // Wrapper for vrange_printer to dump a range to a file.
368 :
369 : void
370 37443 : vrange::dump (FILE *file) const
371 : {
372 37443 : pretty_printer pp;
373 37443 : pp_needs_newline (&pp) = true;
374 37443 : pp.set_output_stream (file);
375 37443 : vrange_printer vrange_pp (&pp);
376 37443 : this->accept (vrange_pp);
377 37443 : pp_flush (&pp);
378 37443 : }
379 :
380 : void
381 0 : irange_bitmask::dump (FILE *file) const
382 : {
383 0 : char buf[WIDE_INT_PRINT_BUFFER_SIZE], *p;
384 0 : pretty_printer pp;
385 :
386 0 : pp_needs_newline (&pp) = true;
387 0 : pp.set_output_stream (file);
388 0 : pp_string (&pp, "MASK ");
389 0 : unsigned len_mask, len_val;
390 0 : if (print_hex_buf_size (m_mask, &len_mask)
391 0 : | print_hex_buf_size (m_value, &len_val))
392 0 : p = XALLOCAVEC (char, MAX (len_mask, len_val));
393 : else
394 : p = buf;
395 0 : print_hex (m_mask, p);
396 0 : pp_string (&pp, p);
397 0 : pp_string (&pp, " VALUE ");
398 0 : print_hex (m_value, p);
399 0 : pp_string (&pp, p);
400 0 : pp_flush (&pp);
401 0 : }
402 :
403 : namespace inchash
404 : {
405 :
406 : void
407 22978328 : add_vrange (const vrange &v, inchash::hash &hstate,
408 : unsigned int)
409 : {
410 22978328 : if (v.undefined_p ())
411 : {
412 0 : hstate.add_int (VR_UNDEFINED);
413 0 : return;
414 : }
415 : // Types are ignored throughout to inhibit two ranges being equal
416 : // but having different hash values. This can happen when two
417 : // ranges are equal and their types are different (but
418 : // types_compatible_p is true).
419 22978328 : if (is_a <irange> (v))
420 : {
421 16446839 : const irange &r = as_a <irange> (v);
422 16446839 : if (r.varying_p ())
423 0 : hstate.add_int (VR_VARYING);
424 : else
425 16446839 : hstate.add_int (VR_RANGE);
426 35485234 : for (unsigned i = 0; i < r.num_pairs (); ++i)
427 : {
428 19038395 : hstate.add_wide_int (r.lower_bound (i));
429 19038519 : hstate.add_wide_int (r.upper_bound (i));
430 : }
431 16446839 : irange_bitmask bm = r.get_bitmask ();
432 16446839 : hstate.add_wide_int (bm.value ());
433 16446839 : hstate.add_wide_int (bm.mask ());
434 16446839 : return;
435 16446839 : }
436 6531489 : if (is_a <prange> (v))
437 : {
438 6453133 : const prange &r = as_a <prange> (v);
439 6453133 : if (r.varying_p ())
440 0 : hstate.add_int (VR_VARYING);
441 : else
442 : {
443 6453133 : hstate.add_int (VR_RANGE);
444 6453133 : hstate.add_wide_int (r.lower_bound ());
445 6453133 : hstate.add_wide_int (r.upper_bound ());
446 6453133 : irange_bitmask bm = r.get_bitmask ();
447 6453133 : hstate.add_wide_int (bm.value ());
448 6453133 : hstate.add_wide_int (bm.mask ());
449 6453133 : }
450 6453133 : return;
451 : }
452 78356 : if (is_a <frange> (v))
453 : {
454 78356 : const frange &r = as_a <frange> (v);
455 78356 : if (r.known_isnan ())
456 260 : hstate.add_int (VR_NAN);
457 : else
458 : {
459 78096 : hstate.add_int (r.varying_p () ? VR_VARYING : VR_RANGE);
460 78096 : hstate.add_real_value (r.lower_bound ());
461 78096 : hstate.add_real_value (r.upper_bound ());
462 : }
463 78356 : nan_state nan = r.get_nan_state ();
464 78356 : hstate.add_int (nan.pos_p ());
465 78356 : hstate.add_int (nan.neg_p ());
466 78356 : return;
467 : }
468 0 : gcc_unreachable ();
469 : }
470 :
471 : } //namespace inchash
472 :
473 : bool
474 36778 : irange::nonnegative_p () const
475 : {
476 36778 : return wi::ge_p (lower_bound (), 0, TYPE_SIGN (type ()));
477 : }
478 :
479 : bool
480 31382 : irange::nonpositive_p () const
481 : {
482 31382 : return wi::le_p (upper_bound (), 0, TYPE_SIGN (type ()));
483 : }
484 :
485 : bool
486 421228511 : irange::supports_type_p (const_tree type) const
487 : {
488 421228511 : return supports_p (type);
489 : }
490 :
491 : // Return TRUE if R fits in THIS.
492 :
493 : bool
494 0 : irange::fits_p (const vrange &r) const
495 : {
496 0 : return m_max_ranges >= as_a <irange> (r).num_pairs ();
497 : }
498 :
499 : void
500 39714760 : irange::set_nonnegative (tree type)
501 : {
502 39714760 : set (type,
503 79429520 : wi::zero (TYPE_PRECISION (type)),
504 39714760 : wi::to_wide (TYPE_MAX_VALUE (type)));
505 39714760 : }
506 :
507 : // Prange implementation.
508 :
509 : void
510 1449 : prange::accept (const vrange_visitor &v) const
511 : {
512 1449 : v.visit (*this);
513 1449 : }
514 :
515 : void
516 0 : prange::set_nonnegative (tree type)
517 : {
518 0 : set (type,
519 0 : wi::zero (TYPE_PRECISION (type)),
520 0 : wi::max_value (TYPE_PRECISION (type), UNSIGNED));
521 0 : }
522 :
523 : void
524 13957684 : prange::set (tree min, tree max, value_range_kind kind)
525 : {
526 13957684 : return set (TREE_TYPE (min), wi::to_wide (min), wi::to_wide (max), kind);
527 : }
528 :
529 : void
530 39906962 : prange::set (tree type, const wide_int &min, const wide_int &max,
531 : value_range_kind kind)
532 : {
533 39906962 : if (kind == VR_UNDEFINED)
534 : {
535 0 : set_undefined ();
536 0 : return;
537 : }
538 39906962 : if (kind == VR_VARYING)
539 : {
540 0 : set_varying (type);
541 0 : return;
542 : }
543 39906962 : if (kind == VR_ANTI_RANGE)
544 : {
545 0 : gcc_checking_assert (min == 0 && max == 0);
546 0 : set_nonzero (type);
547 0 : return;
548 : }
549 39906962 : m_type = type;
550 39906962 : m_min = min;
551 39906962 : m_max = max;
552 39906962 : if (m_min == 0 && m_max == -1)
553 : {
554 5017186 : m_kind = VR_VARYING;
555 5017186 : m_bitmask.set_unknown (TYPE_PRECISION (type));
556 5017186 : if (flag_checking)
557 5017186 : verify_range ();
558 5017186 : return;
559 : }
560 :
561 34889776 : m_kind = VR_RANGE;
562 34889776 : m_bitmask = irange_bitmask (type, min, max);
563 34889776 : if (flag_checking)
564 34889764 : verify_range ();
565 : }
566 :
567 : bool
568 3199804 : prange::contains_p (const wide_int &w) const
569 : {
570 3199804 : if (undefined_p ())
571 : return false;
572 :
573 3199804 : if (varying_p ())
574 : return true;
575 :
576 5012786 : return (wi::le_p (lower_bound (), w, UNSIGNED)
577 2508561 : && wi::ge_p (upper_bound (), w, UNSIGNED));
578 : }
579 :
580 : bool
581 216984244 : prange::singleton_p (tree *result) const
582 : {
583 308046350 : if (m_kind == VR_RANGE && lower_bound () == upper_bound ())
584 : {
585 231562 : if (result)
586 76795 : *result = wide_int_to_tree (type (), m_min);
587 231562 : return true;
588 : }
589 : return false;
590 : }
591 :
592 : tree
593 4741882 : prange::lbound () const
594 : {
595 4741882 : return wide_int_to_tree (type (), m_min);
596 : }
597 :
598 : tree
599 758443 : prange::ubound () const
600 : {
601 758443 : return wide_int_to_tree (type (), m_max);
602 : }
603 :
604 : bool
605 17507157 : prange::union_ (const vrange &v)
606 : {
607 17507157 : const prange &r = as_a <prange> (v);
608 :
609 17507157 : if (r.undefined_p ())
610 : return false;
611 17358967 : if (undefined_p ())
612 : {
613 8828104 : *this = r;
614 8828104 : if (flag_checking)
615 8828104 : verify_range ();
616 8828104 : return true;
617 : }
618 8530863 : if (varying_p ())
619 : return false;
620 4552820 : if (r.varying_p ())
621 : {
622 1352526 : set_varying (type ());
623 1352526 : return true;
624 : }
625 :
626 3200294 : wide_int new_lb = wi::min (r.lower_bound (), lower_bound (), UNSIGNED);
627 3200294 : wide_int new_ub = wi::max (r.upper_bound (), upper_bound (), UNSIGNED);
628 3200294 : prange new_range (type (), new_lb, new_ub);
629 3200294 : new_range.m_bitmask.union_ (m_bitmask);
630 3200294 : new_range.m_bitmask.union_ (r.m_bitmask);
631 3200294 : if (new_range.varying_compatible_p ())
632 : {
633 324000 : set_varying (type ());
634 324000 : return true;
635 : }
636 2876294 : if (flag_checking)
637 2876294 : new_range.verify_range ();
638 2876294 : if (new_range == *this)
639 : return false;
640 51530 : *this = new_range;
641 51530 : return true;
642 3200294 : }
643 :
644 : bool
645 194991710 : prange::intersect (const vrange &v)
646 : {
647 194991710 : const prange &r = as_a <prange> (v);
648 194991710 : gcc_checking_assert (undefined_p () || r.undefined_p ()
649 : || range_compatible_p (type (), r.type ()));
650 :
651 194991710 : if (undefined_p ())
652 : return false;
653 194879340 : if (r.undefined_p ())
654 : {
655 31885 : set_undefined ();
656 31885 : return true;
657 : }
658 194847455 : if (r.varying_p ())
659 : return false;
660 105534217 : if (varying_p ())
661 : {
662 47981049 : *this = r;
663 47981049 : return true;
664 : }
665 :
666 57553168 : prange save = *this;
667 57553168 : m_min = wi::max (r.lower_bound (), lower_bound (), UNSIGNED);
668 57553168 : m_max = wi::min (r.upper_bound (), upper_bound (), UNSIGNED);
669 57553168 : if (wi::gt_p (m_min, m_max, UNSIGNED))
670 : {
671 368900 : set_undefined ();
672 368900 : return true;
673 : }
674 :
675 : // Intersect all bitmasks: the old one, the new one, and the other operand's.
676 57184268 : irange_bitmask new_bitmask (m_type, m_min, m_max);
677 57184268 : if (!m_bitmask.intersect (new_bitmask))
678 12 : set_undefined ();
679 57184256 : else if (!m_bitmask.intersect (r.m_bitmask))
680 4 : set_undefined ();
681 57184268 : if (varying_compatible_p ())
682 : {
683 0 : set_varying (type ());
684 0 : return true;
685 : }
686 :
687 57184268 : if (flag_checking)
688 57184163 : verify_range ();
689 57184268 : if (*this == save)
690 : return false;
691 : return true;
692 57553168 : }
693 :
694 : prange &
695 187147181 : prange::operator= (const prange &src)
696 : {
697 187147181 : m_type = src.m_type;
698 187147181 : m_kind = src.m_kind;
699 187147181 : m_min = src.m_min;
700 187147181 : m_max = src.m_max;
701 187147181 : m_bitmask = src.m_bitmask;
702 187147181 : if (flag_checking)
703 187147046 : verify_range ();
704 187147181 : return *this;
705 : }
706 :
707 : bool
708 70304491 : prange::operator== (const prange &src) const
709 : {
710 70304491 : if (m_kind == src.m_kind)
711 : {
712 69698909 : if (undefined_p ())
713 : return true;
714 :
715 69690673 : if (varying_p ())
716 1061350 : return types_compatible_p (type (), src.type ());
717 :
718 136344537 : return (m_min == src.m_min && m_max == src.m_max
719 136008104 : && m_bitmask == src.m_bitmask);
720 : }
721 : return false;
722 : }
723 :
724 : void
725 2632450 : prange::invert ()
726 : {
727 2632450 : gcc_checking_assert (!undefined_p () && !varying_p ());
728 :
729 2632450 : wide_int new_lb, new_ub;
730 2632450 : unsigned prec = TYPE_PRECISION (type ());
731 2632450 : wide_int type_min = wi::zero (prec);
732 2632450 : wide_int type_max = wi::max_value (prec, UNSIGNED);
733 2632450 : wi::overflow_type ovf;
734 :
735 2632450 : if (lower_bound () == type_min)
736 : {
737 2625648 : new_lb = wi::add (upper_bound (), 1, UNSIGNED, &ovf);
738 2625648 : if (ovf)
739 0 : new_lb = type_min;
740 2625648 : new_ub = type_max;
741 2625648 : set (type (), new_lb, new_ub);
742 : }
743 6802 : else if (upper_bound () == type_max)
744 : {
745 2838 : wi::overflow_type ovf;
746 2838 : new_lb = type_min;
747 2838 : new_ub = wi::sub (lower_bound (), 1, UNSIGNED, &ovf);
748 2838 : if (ovf)
749 0 : new_ub = type_max;
750 2838 : set (type (), new_lb, new_ub);
751 : }
752 : else
753 3964 : set_varying (type ());
754 2632450 : }
755 :
756 : void
757 981511439 : prange::verify_range () const
758 : {
759 981511439 : gcc_checking_assert (m_discriminator == VR_PRANGE);
760 :
761 981511439 : if (m_kind == VR_UNDEFINED)
762 : return;
763 :
764 981446495 : gcc_checking_assert (supports_p (type ()));
765 :
766 981446495 : if (m_kind == VR_VARYING)
767 : {
768 476970530 : gcc_checking_assert (varying_compatible_p ());
769 : return;
770 : }
771 504475965 : gcc_checking_assert (!varying_compatible_p ());
772 504475965 : gcc_checking_assert (m_kind == VR_RANGE);
773 : }
774 :
775 : void
776 29567702 : prange::update_bitmask (const irange_bitmask &bm)
777 : {
778 29567702 : gcc_checking_assert (!undefined_p ());
779 :
780 : // If all the bits are known, this is a singleton.
781 29567702 : if (bm.mask () == 0)
782 : {
783 148548 : set (type (), bm.value (), bm.value ());
784 148548 : return;
785 : }
786 :
787 : // Drop VARYINGs with known bits to a plain range.
788 36953217 : if (m_kind == VR_VARYING && !bm.unknown_p ())
789 200282 : m_kind = VR_RANGE;
790 :
791 29419154 : m_bitmask = bm;
792 29419154 : if (varying_compatible_p ())
793 7333781 : m_kind = VR_VARYING;
794 :
795 29419154 : if (flag_checking)
796 29419154 : verify_range ();
797 : }
798 :
799 :
800 : // Frange implementation.
801 :
802 : void
803 448 : frange::accept (const vrange_visitor &v) const
804 : {
805 448 : v.visit (*this);
806 448 : }
807 :
808 : bool
809 0 : frange::fits_p (const vrange &) const
810 : {
811 0 : return true;
812 : }
813 :
814 : // Flush denormal endpoints to the appropriate 0.0.
815 :
816 : void
817 6783984 : frange::flush_denormals_to_zero ()
818 : {
819 6783984 : if (undefined_p () || known_isnan ())
820 : return;
821 :
822 6783984 : machine_mode mode = TYPE_MODE (type ());
823 : // Flush [x, -DENORMAL] to [x, -0.0].
824 6783984 : if (real_isdenormal (&m_max, mode) && real_isneg (&m_max))
825 : {
826 2114 : if (HONOR_SIGNED_ZEROS (m_type))
827 2114 : m_max = dconstm0;
828 : else
829 0 : m_max = dconst0;
830 : }
831 : // Flush [+DENORMAL, x] to [+0.0, x].
832 6783984 : if (real_isdenormal (&m_min, mode) && !real_isneg (&m_min))
833 3776 : m_min = dconst0;
834 : }
835 :
836 : // Setter for franges.
837 :
838 : void
839 64257341 : frange::set (tree type,
840 : const REAL_VALUE_TYPE &min, const REAL_VALUE_TYPE &max,
841 : const nan_state &nan, value_range_kind kind)
842 : {
843 64257341 : switch (kind)
844 : {
845 0 : case VR_UNDEFINED:
846 0 : set_undefined ();
847 0 : return;
848 32891358 : case VR_VARYING:
849 32891358 : case VR_ANTI_RANGE:
850 32891358 : set_varying (type);
851 32891358 : return;
852 31365983 : case VR_RANGE:
853 31365983 : break;
854 0 : default:
855 0 : gcc_unreachable ();
856 : }
857 :
858 31365983 : gcc_checking_assert (!real_isnan (&min) && !real_isnan (&max));
859 :
860 31365983 : m_kind = kind;
861 31365983 : m_type = type;
862 31365983 : m_min = min;
863 31365983 : m_max = max;
864 31365983 : if (HONOR_NANS (m_type))
865 : {
866 30463783 : m_pos_nan = nan.pos_p ();
867 30463783 : m_neg_nan = nan.neg_p ();
868 : }
869 : else
870 : {
871 902200 : m_pos_nan = false;
872 902200 : m_neg_nan = false;
873 : }
874 :
875 125463932 : if (!MODE_HAS_SIGNED_ZEROS (TYPE_MODE (m_type)))
876 : {
877 0 : if (real_iszero (&m_min, 1))
878 0 : m_min.sign = 0;
879 0 : if (real_iszero (&m_max, 1))
880 0 : m_max.sign = 0;
881 : }
882 31365983 : else if (!HONOR_SIGNED_ZEROS (m_type))
883 : {
884 935746 : if (real_iszero (&m_max, 1))
885 26 : m_max.sign = 0;
886 935746 : if (real_iszero (&m_min, 0))
887 29366 : m_min.sign = 1;
888 : }
889 :
890 : // For -ffinite-math-only we can drop ranges outside the
891 : // representable numbers to min/max for the type.
892 31365983 : if (!HONOR_INFINITIES (m_type))
893 : {
894 902200 : REAL_VALUE_TYPE min_repr = frange_val_min (m_type);
895 902200 : REAL_VALUE_TYPE max_repr = frange_val_max (m_type);
896 902200 : if (real_less (&m_min, &min_repr))
897 314404 : m_min = min_repr;
898 587796 : else if (real_less (&max_repr, &m_min))
899 1 : m_min = max_repr;
900 902200 : if (real_less (&max_repr, &m_max))
901 317316 : m_max = max_repr;
902 584884 : else if (real_less (&m_max, &min_repr))
903 0 : m_max = min_repr;
904 : }
905 :
906 : // Check for swapped ranges.
907 31365983 : gcc_checking_assert (real_compare (LE_EXPR, &min, &max));
908 :
909 31365983 : normalize_kind ();
910 : }
911 :
912 : // Setter for an frange defaulting the NAN possibility to +-NAN when
913 : // HONOR_NANS.
914 :
915 : void
916 50847046 : frange::set (tree type,
917 : const REAL_VALUE_TYPE &min, const REAL_VALUE_TYPE &max,
918 : value_range_kind kind)
919 : {
920 50847046 : set (type, min, max, nan_state (true), kind);
921 50847046 : }
922 :
923 : void
924 16 : frange::set (tree min, tree max, value_range_kind kind)
925 : {
926 32 : set (TREE_TYPE (min),
927 16 : *TREE_REAL_CST_PTR (min), *TREE_REAL_CST_PTR (max), kind);
928 16 : }
929 :
930 : // Normalize range to VARYING or UNDEFINED, or vice versa. Return
931 : // TRUE if anything changed.
932 : //
933 : // A range with no known properties can be dropped to VARYING.
934 : // Similarly, a VARYING with any properties should be dropped to a
935 : // VR_RANGE. Normalizing ranges upon changing them ensures there is
936 : // only one representation for a given range.
937 :
938 : bool
939 61972113 : frange::normalize_kind ()
940 : {
941 61972113 : if (m_kind == VR_RANGE
942 54505274 : && frange_val_is_min (m_min, m_type)
943 73228503 : && frange_val_is_max (m_max, m_type))
944 : {
945 8252836 : if (!HONOR_NANS (m_type) || (m_pos_nan && m_neg_nan))
946 : {
947 6734145 : set_varying (m_type);
948 6734145 : return true;
949 : }
950 : }
951 53719277 : else if (m_kind == VR_VARYING)
952 : {
953 7466548 : if (HONOR_NANS (m_type) && (!m_pos_nan || !m_neg_nan))
954 : {
955 2000763 : m_kind = VR_RANGE;
956 2000763 : m_min = frange_val_min (m_type);
957 2000763 : m_max = frange_val_max (m_type);
958 2000763 : if (flag_checking)
959 2000763 : verify_range ();
960 2000763 : return true;
961 : }
962 : }
963 46252729 : else if (m_kind == VR_NAN && !m_pos_nan && !m_neg_nan)
964 4 : set_undefined ();
965 : return false;
966 : }
967 :
968 : // Union or intersect the zero endpoints of two ranges. For example:
969 : // [-0, x] U [+0, x] => [-0, x]
970 : // [ x, -0] U [ x, +0] => [ x, +0]
971 : // [-0, x] ^ [+0, x] => [+0, x]
972 : // [ x, -0] ^ [ x, +0] => [ x, -0]
973 : //
974 : // UNION_P is true when performing a union, or false when intersecting.
975 :
976 : bool
977 8773494 : frange::combine_zeros (const frange &r, bool union_p)
978 : {
979 8773494 : gcc_checking_assert (!undefined_p () && !known_isnan ());
980 :
981 8773494 : bool changed = false;
982 11681906 : if (real_iszero (&m_min) && real_iszero (&r.m_min)
983 11256710 : && real_isneg (&m_min) != real_isneg (&r.m_min))
984 : {
985 165668 : m_min.sign = union_p;
986 165668 : changed = true;
987 : }
988 8991912 : if (real_iszero (&m_max) && real_iszero (&r.m_max)
989 8948368 : && real_isneg (&m_max) != real_isneg (&r.m_max))
990 : {
991 3942 : m_max.sign = !union_p;
992 3942 : changed = true;
993 : }
994 : // If the signs are swapped, the resulting range is empty.
995 8773494 : if (m_min.sign == 0 && m_max.sign == 1)
996 : {
997 136 : if (maybe_isnan ())
998 8 : m_kind = VR_NAN;
999 : else
1000 64 : set_undefined ();
1001 : changed = true;
1002 : }
1003 8773494 : return changed;
1004 : }
1005 :
1006 : // Union two ranges when one is known to be a NAN.
1007 :
1008 : bool
1009 206041 : frange::union_nans (const frange &r)
1010 : {
1011 206041 : gcc_checking_assert (known_isnan () || r.known_isnan ());
1012 :
1013 206041 : bool changed = false;
1014 206041 : if (known_isnan () && m_kind != r.m_kind)
1015 : {
1016 41202 : m_kind = r.m_kind;
1017 41202 : m_min = r.m_min;
1018 41202 : m_max = r.m_max;
1019 41202 : changed = true;
1020 : }
1021 206041 : if (m_pos_nan != r.m_pos_nan || m_neg_nan != r.m_neg_nan)
1022 : {
1023 196540 : m_pos_nan |= r.m_pos_nan;
1024 196540 : m_neg_nan |= r.m_neg_nan;
1025 196540 : changed = true;
1026 : }
1027 206041 : if (changed)
1028 : {
1029 204464 : normalize_kind ();
1030 204464 : return true;
1031 : }
1032 : return false;
1033 : }
1034 :
1035 : bool
1036 3888506 : frange::union_ (const vrange &v)
1037 : {
1038 3888506 : const frange &r = as_a <frange> (v);
1039 :
1040 3888506 : if (r.undefined_p () || varying_p ())
1041 : return false;
1042 3227327 : if (undefined_p () || r.varying_p ())
1043 : {
1044 1931848 : *this = r;
1045 1931848 : return true;
1046 : }
1047 :
1048 : // Combine NAN info.
1049 1295479 : if (known_isnan () || r.known_isnan ())
1050 206041 : return union_nans (r);
1051 1089438 : bool changed = false;
1052 1089438 : if (m_pos_nan != r.m_pos_nan || m_neg_nan != r.m_neg_nan)
1053 : {
1054 381853 : m_pos_nan |= r.m_pos_nan;
1055 381853 : m_neg_nan |= r.m_neg_nan;
1056 381853 : changed = true;
1057 : }
1058 :
1059 : // Combine endpoints.
1060 1089438 : if (real_less (&r.m_min, &m_min))
1061 : {
1062 515098 : m_min = r.m_min;
1063 515098 : changed = true;
1064 : }
1065 1089438 : if (real_less (&m_max, &r.m_max))
1066 : {
1067 79782 : m_max = r.m_max;
1068 79782 : changed = true;
1069 : }
1070 :
1071 1089438 : if (HONOR_SIGNED_ZEROS (m_type))
1072 1085492 : changed |= combine_zeros (r, true);
1073 :
1074 1089438 : changed |= normalize_kind ();
1075 1089438 : return changed;
1076 : }
1077 :
1078 : // Intersect two ranges when one is known to be a NAN.
1079 :
1080 : bool
1081 51402 : frange::intersect_nans (const frange &r)
1082 : {
1083 51402 : gcc_checking_assert (known_isnan () || r.known_isnan ());
1084 :
1085 51402 : m_pos_nan &= r.m_pos_nan;
1086 51402 : m_neg_nan &= r.m_neg_nan;
1087 53964 : if (maybe_isnan ())
1088 48872 : m_kind = VR_NAN;
1089 : else
1090 2530 : set_undefined ();
1091 51402 : if (flag_checking)
1092 51402 : verify_range ();
1093 51402 : return true;
1094 : }
1095 :
1096 : bool
1097 25345016 : frange::intersect (const vrange &v)
1098 : {
1099 25345016 : const frange &r = as_a <frange> (v);
1100 :
1101 25345016 : if (undefined_p () || r.varying_p ())
1102 : return false;
1103 10177004 : if (r.undefined_p ())
1104 : {
1105 5571 : set_undefined ();
1106 5571 : return true;
1107 : }
1108 10171433 : if (varying_p ())
1109 : {
1110 2312882 : *this = r;
1111 2312882 : return true;
1112 : }
1113 :
1114 : // Combine NAN info.
1115 7858551 : if (known_isnan () || r.known_isnan ())
1116 51402 : return intersect_nans (r);
1117 7807149 : bool changed = false;
1118 7807149 : if (m_pos_nan != r.m_pos_nan || m_neg_nan != r.m_neg_nan)
1119 : {
1120 2535091 : m_pos_nan &= r.m_pos_nan;
1121 2535091 : m_neg_nan &= r.m_neg_nan;
1122 2535091 : changed = true;
1123 : }
1124 :
1125 : // Combine endpoints.
1126 7807149 : if (real_less (&m_min, &r.m_min))
1127 : {
1128 1535897 : m_min = r.m_min;
1129 1535897 : changed = true;
1130 : }
1131 7807149 : if (real_less (&r.m_max, &m_max))
1132 : {
1133 1317547 : m_max = r.m_max;
1134 1317547 : changed = true;
1135 : }
1136 : // If the endpoints are swapped, the resulting range is empty.
1137 7807149 : if (real_less (&m_max, &m_min))
1138 : {
1139 37001 : if (maybe_isnan ())
1140 29087 : m_kind = VR_NAN;
1141 : else
1142 3957 : set_undefined ();
1143 33044 : if (flag_checking)
1144 33044 : verify_range ();
1145 33044 : return true;
1146 : }
1147 :
1148 7774105 : if (HONOR_SIGNED_ZEROS (m_type))
1149 7688002 : changed |= combine_zeros (r, false);
1150 :
1151 7774105 : changed |= normalize_kind ();
1152 7774105 : return changed;
1153 : }
1154 :
1155 : frange &
1156 54598977 : frange::operator= (const frange &src)
1157 : {
1158 54598977 : m_kind = src.m_kind;
1159 54598977 : m_type = src.m_type;
1160 54598977 : m_min = src.m_min;
1161 54598977 : m_max = src.m_max;
1162 54598977 : m_pos_nan = src.m_pos_nan;
1163 54598977 : m_neg_nan = src.m_neg_nan;
1164 :
1165 54598977 : if (flag_checking)
1166 54598977 : verify_range ();
1167 54598977 : return *this;
1168 : }
1169 :
1170 : bool
1171 71160 : frange::operator== (const frange &src) const
1172 : {
1173 71160 : if (m_kind == src.m_kind)
1174 : {
1175 60793 : if (undefined_p ())
1176 : return true;
1177 :
1178 60654 : if (varying_p ())
1179 25446 : return types_compatible_p (m_type, src.m_type);
1180 :
1181 35208 : bool nan1 = known_isnan ();
1182 35208 : bool nan2 = src.known_isnan ();
1183 35208 : if (nan1 || nan2)
1184 : {
1185 123 : if (nan1 && nan2)
1186 123 : return (m_pos_nan == src.m_pos_nan
1187 123 : && m_neg_nan == src.m_neg_nan);
1188 : return false;
1189 : }
1190 :
1191 35085 : return (real_identical (&m_min, &src.m_min)
1192 30790 : && real_identical (&m_max, &src.m_max)
1193 30415 : && m_pos_nan == src.m_pos_nan
1194 30392 : && m_neg_nan == src.m_neg_nan
1195 65264 : && types_compatible_p (m_type, src.m_type));
1196 : }
1197 : return false;
1198 : }
1199 :
1200 : // Return TRUE if range contains R.
1201 :
1202 : bool
1203 50260 : frange::contains_p (const REAL_VALUE_TYPE &r) const
1204 : {
1205 50260 : gcc_checking_assert (m_kind != VR_ANTI_RANGE);
1206 :
1207 50260 : if (undefined_p ())
1208 : return false;
1209 :
1210 50260 : if (varying_p ())
1211 : return true;
1212 :
1213 47715 : if (real_isnan (&r))
1214 : {
1215 : // No NAN in range.
1216 0 : if (!m_pos_nan && !m_neg_nan)
1217 : return false;
1218 : // Both +NAN and -NAN are present.
1219 0 : if (m_pos_nan && m_neg_nan)
1220 : return true;
1221 0 : return m_neg_nan == r.sign;
1222 : }
1223 47715 : if (known_isnan ())
1224 : return false;
1225 :
1226 47715 : if (real_compare (GE_EXPR, &r, &m_min) && real_compare (LE_EXPR, &r, &m_max))
1227 : {
1228 : // Make sure the signs are equal for signed zeros.
1229 15229 : if (HONOR_SIGNED_ZEROS (m_type) && real_iszero (&r))
1230 30184 : return r.sign == m_min.sign || r.sign == m_max.sign;
1231 17 : return true;
1232 : }
1233 : return false;
1234 : }
1235 :
1236 : // If range is a singleton, place it in RESULT and return TRUE. If
1237 : // RESULT is NULL, just return TRUE.
1238 : //
1239 : // A NAN can never be a singleton.
1240 :
1241 : bool
1242 23691203 : frange::internal_singleton_p (REAL_VALUE_TYPE *result) const
1243 : {
1244 23691203 : if (m_kind == VR_RANGE && real_identical (&m_min, &m_max))
1245 : {
1246 : // Return false for any singleton that may be a NAN.
1247 23803377 : if (HONOR_NANS (m_type) && maybe_isnan ())
1248 : return false;
1249 :
1250 776349 : if (MODE_COMPOSITE_P (TYPE_MODE (m_type)))
1251 : {
1252 : // For IBM long doubles, if the value is +-Inf or is exactly
1253 : // representable in double, the other double could be +0.0
1254 : // or -0.0. Since this means there is more than one way to
1255 : // represent a value, return false to avoid propagating it.
1256 : // See libgcc/config/rs6000/ibm-ldouble-format for details.
1257 0 : if (real_isinf (&m_min))
1258 0 : return false;
1259 0 : REAL_VALUE_TYPE r;
1260 0 : real_convert (&r, DFmode, &m_min);
1261 0 : if (real_identical (&r, &m_min))
1262 : return false;
1263 : }
1264 :
1265 110907 : if (result)
1266 0 : *result = m_min;
1267 110907 : return true;
1268 : }
1269 : return false;
1270 : }
1271 :
1272 : bool
1273 23691203 : frange::singleton_p (tree *result) const
1274 : {
1275 23691203 : if (internal_singleton_p ())
1276 : {
1277 110907 : if (result)
1278 8617 : *result = build_real (m_type, m_min);
1279 110907 : return true;
1280 : }
1281 : return false;
1282 : }
1283 :
1284 : bool
1285 0 : frange::singleton_p (REAL_VALUE_TYPE &r) const
1286 : {
1287 0 : return internal_singleton_p (&r);
1288 : }
1289 :
1290 : bool
1291 58338641 : frange::supports_type_p (const_tree type) const
1292 : {
1293 58338641 : return supports_p (type);
1294 : }
1295 :
1296 : void
1297 211753082 : frange::verify_range () const
1298 : {
1299 211753082 : if (!undefined_p ())
1300 83806720 : gcc_checking_assert (HONOR_NANS (m_type) || !maybe_isnan ());
1301 211753082 : switch (m_kind)
1302 : {
1303 133215232 : case VR_UNDEFINED:
1304 133215232 : gcc_checking_assert (!m_type);
1305 : return;
1306 42928466 : case VR_VARYING:
1307 42928466 : gcc_checking_assert (m_type);
1308 42928466 : gcc_checking_assert (frange_val_is_min (m_min, m_type));
1309 42928466 : gcc_checking_assert (frange_val_is_max (m_max, m_type));
1310 42928466 : if (HONOR_NANS (m_type))
1311 38410391 : gcc_checking_assert (m_pos_nan && m_neg_nan);
1312 : else
1313 4518075 : gcc_checking_assert (!m_pos_nan && !m_neg_nan);
1314 : return;
1315 35120829 : case VR_RANGE:
1316 35120829 : gcc_checking_assert (m_type);
1317 35120829 : break;
1318 488555 : case VR_NAN:
1319 488555 : gcc_checking_assert (m_type);
1320 488555 : gcc_checking_assert (m_pos_nan || m_neg_nan);
1321 : return;
1322 0 : default:
1323 0 : gcc_unreachable ();
1324 : }
1325 :
1326 : // NANs cannot appear in the endpoints of a range.
1327 35120829 : gcc_checking_assert (!real_isnan (&m_min) && !real_isnan (&m_max));
1328 :
1329 : // Make sure we don't have swapped ranges.
1330 35120829 : gcc_checking_assert (!real_less (&m_max, &m_min));
1331 :
1332 : // [ +0.0, -0.0 ] is nonsensical.
1333 35120829 : gcc_checking_assert (!(real_iszero (&m_min, 0) && real_iszero (&m_max, 1)));
1334 :
1335 : // If all the properties are clear, we better not span the entire
1336 : // domain, because that would make us varying.
1337 35120829 : if (m_pos_nan && m_neg_nan)
1338 12822567 : gcc_checking_assert (!frange_val_is_min (m_min, m_type)
1339 : || !frange_val_is_max (m_max, m_type));
1340 : }
1341 :
1342 : // We can't do much with nonzeros yet.
1343 : void
1344 0 : frange::set_nonzero (tree type)
1345 : {
1346 0 : set_varying (type);
1347 0 : }
1348 :
1349 : // We can't do much with nonzeros yet.
1350 : bool
1351 0 : frange::nonzero_p () const
1352 : {
1353 0 : return false;
1354 : }
1355 :
1356 : // Set range to [+0.0, +0.0] if honoring signed zeros, or [0.0, 0.0]
1357 : // otherwise.
1358 :
1359 : void
1360 159556 : frange::set_zero (tree type)
1361 : {
1362 159556 : if (HONOR_SIGNED_ZEROS (type))
1363 : {
1364 159556 : set (type, dconstm0, dconst0);
1365 159556 : clear_nan ();
1366 : }
1367 : else
1368 0 : set (type, dconst0, dconst0);
1369 159556 : }
1370 :
1371 : // Return TRUE for any zero regardless of sign.
1372 :
1373 : bool
1374 9083 : frange::zero_p () const
1375 : {
1376 9083 : return (m_kind == VR_RANGE
1377 8024 : && real_iszero (&m_min)
1378 11243 : && real_iszero (&m_max));
1379 : }
1380 :
1381 : // Set the range to non-negative numbers, that is [+0.0, +INF].
1382 : //
1383 : // The NAN in the resulting range (if HONOR_NANS) has a varying sign
1384 : // as there are no guarantees in IEEE 754 wrt to the sign of a NAN,
1385 : // except for copy, abs, and copysign. It is the responsibility of
1386 : // the caller to set the NAN's sign if desired.
1387 :
1388 : void
1389 36280 : frange::set_nonnegative (tree type)
1390 : {
1391 36280 : set (type, dconst0, frange_val_max (type));
1392 36280 : }
1393 :
1394 : tree
1395 0 : frange::lbound () const
1396 : {
1397 0 : return build_real (type (), lower_bound ());
1398 : }
1399 :
1400 : tree
1401 0 : frange::ubound () const
1402 : {
1403 0 : return build_real (type (), upper_bound ());
1404 : }
1405 :
1406 : // Here we copy between any two irange's.
1407 :
1408 : irange &
1409 1043651835 : irange::operator= (const irange &src)
1410 : {
1411 1043651835 : int needed = src.num_pairs ();
1412 1043651835 : maybe_resize (needed);
1413 :
1414 1043651835 : unsigned x;
1415 1043651835 : unsigned lim = src.m_num_ranges;
1416 1043651835 : if (lim > m_max_ranges)
1417 16505 : lim = m_max_ranges;
1418 :
1419 3318940749 : for (x = 0; x < lim * 2; ++x)
1420 2275288914 : m_base[x] = src.m_base[x];
1421 :
1422 : // If the range didn't fit, the last range should cover the rest.
1423 1043651835 : if (lim != src.m_num_ranges)
1424 16505 : m_base[x - 1] = src.m_base[src.m_num_ranges * 2 - 1];
1425 :
1426 1043651835 : m_num_ranges = lim;
1427 1043651835 : m_type = src.m_type;
1428 1043651835 : m_kind = src.m_kind;
1429 1043651835 : m_bitmask = src.m_bitmask;
1430 1043651835 : if (m_max_ranges == 1)
1431 21268706 : normalize_kind ();
1432 1043651835 : if (flag_checking)
1433 1043645654 : verify_range ();
1434 1043651835 : return *this;
1435 : }
1436 :
1437 : static value_range_kind
1438 20024855 : get_legacy_range (const irange &r, tree &min, tree &max)
1439 : {
1440 20024855 : if (r.undefined_p ())
1441 : {
1442 103989 : min = NULL_TREE;
1443 103989 : max = NULL_TREE;
1444 103989 : return VR_UNDEFINED;
1445 : }
1446 :
1447 19920866 : tree type = r.type ();
1448 19920866 : if (r.varying_p ())
1449 : {
1450 8504697 : min = wide_int_to_tree (type, r.lower_bound ());
1451 8504697 : max = wide_int_to_tree (type, r.upper_bound ());
1452 8504697 : return VR_VARYING;
1453 : }
1454 :
1455 11416169 : unsigned int precision = TYPE_PRECISION (type);
1456 11416169 : signop sign = TYPE_SIGN (type);
1457 22832338 : if (r.num_pairs () > 1
1458 2992472 : && precision > 1
1459 17401113 : && r.lower_bound () == wi::min_value (precision, sign)
1460 16334335 : && r.upper_bound () == wi::max_value (precision, sign))
1461 : {
1462 512381 : int_range<3> inv (r);
1463 512381 : inv.invert ();
1464 512381 : min = wide_int_to_tree (type, inv.lower_bound (0));
1465 512381 : max = wide_int_to_tree (type, inv.upper_bound (0));
1466 512381 : return VR_ANTI_RANGE;
1467 512381 : }
1468 :
1469 10903788 : min = wide_int_to_tree (type, r.lower_bound ());
1470 10903788 : max = wide_int_to_tree (type, r.upper_bound ());
1471 10903788 : return VR_RANGE;
1472 : }
1473 :
1474 : static value_range_kind
1475 2923100 : get_legacy_range (const prange &r, tree &min, tree &max)
1476 : {
1477 2923100 : if (r.undefined_p ())
1478 : {
1479 0 : min = NULL_TREE;
1480 0 : max = NULL_TREE;
1481 0 : return VR_UNDEFINED;
1482 : }
1483 :
1484 2923100 : tree type = r.type ();
1485 2923100 : if (r.varying_p ())
1486 : {
1487 0 : min = r.lbound ();
1488 0 : max = r.ubound ();
1489 0 : return VR_VARYING;
1490 : }
1491 2923100 : if (r.zero_p ())
1492 : {
1493 2216618 : min = max = r.lbound ();
1494 2216618 : return VR_RANGE;
1495 : }
1496 706482 : if (r.nonzero_p ())
1497 : {
1498 0 : min = max = build_zero_cst (type);
1499 0 : return VR_ANTI_RANGE;
1500 : }
1501 706482 : min = r.lbound ();
1502 706482 : max = r.ubound ();
1503 706482 : return VR_RANGE;
1504 : }
1505 :
1506 : // Given a range in V, return an old-style legacy range consisting of
1507 : // a value_range_kind with a MIN/MAX. This is to maintain
1508 : // compatibility with passes that still depend on VR_ANTI_RANGE, and
1509 : // only works for integers and pointers.
1510 :
1511 : value_range_kind
1512 22947955 : get_legacy_range (const vrange &v, tree &min, tree &max)
1513 : {
1514 22947955 : if (is_a <irange> (v))
1515 20024855 : return get_legacy_range (as_a <irange> (v), min, max);
1516 :
1517 2923100 : return get_legacy_range (as_a <prange> (v), min, max);
1518 : }
1519 :
1520 : /* Set value range to the canonical form of {VRTYPE, MIN, MAX, EQUIV}.
1521 : This means adjusting VRTYPE, MIN and MAX representing the case of a
1522 : wrapping range with MAX < MIN covering [MIN, type_max] U [type_min, MAX]
1523 : as anti-rage ~[MAX+1, MIN-1]. Likewise for wrapping anti-ranges.
1524 : In corner cases where MAX+1 or MIN-1 wraps this will fall back
1525 : to varying.
1526 : This routine exists to ease canonicalization in the case where we
1527 : extract ranges from var + CST op limit. */
1528 :
1529 : void
1530 1384862842 : irange::set (tree type, const wide_int &min, const wide_int &max,
1531 : value_range_kind kind)
1532 : {
1533 1384862842 : unsigned prec = TYPE_PRECISION (type);
1534 1384862842 : signop sign = TYPE_SIGN (type);
1535 1384862842 : wide_int min_value = wi::min_value (prec, sign);
1536 1384862842 : wide_int max_value = wi::max_value (prec, sign);
1537 :
1538 1384862842 : m_type = type;
1539 1384862842 : m_bitmask.set_unknown (prec);
1540 :
1541 1384862842 : if (kind == VR_RANGE)
1542 : {
1543 1329098309 : m_base[0] = min;
1544 1329098309 : m_base[1] = max;
1545 1329098309 : m_num_ranges = 1;
1546 1803167036 : if (min == min_value && max == max_value)
1547 70008625 : m_kind = VR_VARYING;
1548 : else
1549 1259089684 : m_kind = VR_RANGE;
1550 : }
1551 : else
1552 : {
1553 55764533 : gcc_checking_assert (kind == VR_ANTI_RANGE);
1554 55764533 : gcc_checking_assert (m_max_ranges > 1);
1555 :
1556 55764533 : m_kind = VR_UNDEFINED;
1557 55764533 : m_num_ranges = 0;
1558 55764533 : wi::overflow_type ovf;
1559 55764533 : wide_int lim;
1560 55764533 : if (sign == SIGNED)
1561 26235380 : lim = wi::add (min, -1, sign, &ovf);
1562 : else
1563 29529570 : lim = wi::sub (min, 1, sign, &ovf);
1564 :
1565 55764533 : if (!ovf)
1566 : {
1567 39384254 : m_kind = VR_RANGE;
1568 39384254 : m_base[0] = min_value;
1569 39384254 : m_base[1] = lim;
1570 39384254 : ++m_num_ranges;
1571 : }
1572 55764533 : if (sign == SIGNED)
1573 26235380 : lim = wi::sub (max, -1, sign, &ovf);
1574 : else
1575 29529570 : lim = wi::add (max, 1, sign, &ovf);
1576 55764533 : if (!ovf)
1577 : {
1578 55763327 : m_kind = VR_RANGE;
1579 55763327 : m_base[m_num_ranges * 2] = lim;
1580 55763327 : m_base[m_num_ranges * 2 + 1] = max_value;
1581 55763327 : ++m_num_ranges;
1582 : }
1583 55764533 : }
1584 :
1585 1384862842 : if (flag_checking)
1586 1384857566 : verify_range ();
1587 1384862842 : }
1588 :
1589 : void
1590 219771145 : irange::set (tree min, tree max, value_range_kind kind)
1591 : {
1592 219771145 : if (POLY_INT_CST_P (min) || POLY_INT_CST_P (max))
1593 : {
1594 : set_varying (TREE_TYPE (min));
1595 : return;
1596 : }
1597 :
1598 219771145 : gcc_checking_assert (TREE_CODE (min) == INTEGER_CST);
1599 219771145 : gcc_checking_assert (TREE_CODE (max) == INTEGER_CST);
1600 :
1601 219771766 : return set (TREE_TYPE (min), wi::to_wide (min), wi::to_wide (max), kind);
1602 : }
1603 :
1604 : // Check the validity of the range.
1605 :
1606 : void
1607 4532617881 : irange::verify_range () const
1608 : {
1609 4532617881 : gcc_checking_assert (m_discriminator == VR_IRANGE);
1610 4532617881 : if (m_kind == VR_UNDEFINED)
1611 : {
1612 173064 : gcc_checking_assert (m_num_ranges == 0);
1613 : return;
1614 : }
1615 4532444817 : gcc_checking_assert (supports_p (type ()));
1616 4532444817 : gcc_checking_assert (m_num_ranges <= m_max_ranges);
1617 :
1618 : // Legacy allowed these to represent VARYING for unknown types.
1619 : // Leave this in for now, until all users are converted. Eventually
1620 : // we should abort in set_varying.
1621 4532444817 : if (m_kind == VR_VARYING && m_type == error_mark_node)
1622 : return;
1623 :
1624 4532444817 : unsigned prec = TYPE_PRECISION (m_type);
1625 4532444817 : if (m_kind == VR_VARYING)
1626 : {
1627 274364322 : gcc_checking_assert (m_bitmask.unknown_p ());
1628 274364322 : gcc_checking_assert (m_num_ranges == 1);
1629 274364322 : gcc_checking_assert (varying_compatible_p ());
1630 274364322 : gcc_checking_assert (lower_bound ().get_precision () == prec);
1631 274364322 : gcc_checking_assert (upper_bound ().get_precision () == prec);
1632 274364322 : return;
1633 : }
1634 4258080495 : gcc_checking_assert (m_num_ranges != 0);
1635 4258080495 : gcc_checking_assert (!varying_compatible_p ());
1636 10664839654 : for (unsigned i = 0; i < m_num_ranges; ++i)
1637 : {
1638 6406759159 : wide_int lb = lower_bound (i);
1639 6406759159 : wide_int ub = upper_bound (i);
1640 6406759159 : gcc_checking_assert (lb.get_precision () == prec);
1641 6406759159 : gcc_checking_assert (ub.get_precision () == prec);
1642 6406759159 : int c = wi::cmp (lb, ub, TYPE_SIGN (m_type));
1643 6406759159 : gcc_checking_assert (c == 0 || c == -1);
1644 : // Previous UB should be lower than LB
1645 6406759159 : if (i > 0)
1646 4297357328 : gcc_checking_assert (wi::lt_p (upper_bound (i - 1),
1647 : lb,
1648 : TYPE_SIGN (m_type)));
1649 6406779687 : }
1650 4258080495 : m_bitmask.verify_mask ();
1651 : }
1652 :
1653 : bool
1654 158829660 : irange::operator== (const irange &other) const
1655 : {
1656 158829660 : if (m_num_ranges != other.m_num_ranges)
1657 : return false;
1658 :
1659 151094084 : if (m_num_ranges == 0)
1660 : return true;
1661 :
1662 150932349 : signop sign1 = TYPE_SIGN (type ());
1663 150932349 : signop sign2 = TYPE_SIGN (other.type ());
1664 :
1665 191964296 : for (unsigned i = 0; i < m_num_ranges; ++i)
1666 : {
1667 156730219 : widest_int lb = widest_int::from (lower_bound (i), sign1);
1668 156730219 : widest_int ub = widest_int::from (upper_bound (i), sign1);
1669 156730219 : widest_int lb_other = widest_int::from (other.lower_bound (i), sign2);
1670 156730219 : widest_int ub_other = widest_int::from (other.upper_bound (i), sign2);
1671 251785612 : if (lb != lb_other || ub != ub_other)
1672 115698272 : return false;
1673 156730597 : }
1674 :
1675 35234077 : irange_bitmask bm1 = get_bitmask ();
1676 35234077 : irange_bitmask bm2 = other.get_bitmask ();
1677 35234077 : widest_int tmp1 = widest_int::from (bm1.mask (), sign1);
1678 35234077 : widest_int tmp2 = widest_int::from (bm2.mask (), sign2);
1679 35234077 : if (tmp1 != tmp2)
1680 : return false;
1681 35230386 : if (bm1.unknown_p ())
1682 : return true;
1683 24346634 : tmp1 = widest_int::from (bm1.value (), sign1);
1684 24346634 : tmp2 = widest_int::from (bm2.value (), sign2);
1685 24346622 : return tmp1 == tmp2;
1686 35234113 : }
1687 :
1688 : /* If range is a singleton, place it in RESULT and return TRUE. */
1689 :
1690 : bool
1691 631069410 : irange::singleton_p (tree *result) const
1692 : {
1693 1180832096 : if (num_pairs () == 1 && lower_bound () == upper_bound ())
1694 : {
1695 37456880 : if (result)
1696 6684548 : *result = wide_int_to_tree (type (), lower_bound ());
1697 37456880 : return true;
1698 : }
1699 : return false;
1700 : }
1701 :
1702 : bool
1703 491075487 : irange::singleton_p (wide_int &w) const
1704 : {
1705 663585281 : if (num_pairs () == 1 && lower_bound () == upper_bound ())
1706 : {
1707 18950561 : w = lower_bound ();
1708 18950561 : return true;
1709 : }
1710 : return false;
1711 : }
1712 :
1713 : /* Return 1 if CST is inside value range.
1714 : 0 if CST is not inside value range.
1715 :
1716 : Benchmark compile/20001226-1.c compilation time after changing this
1717 : function. */
1718 :
1719 : bool
1720 213274273 : irange::contains_p (const wide_int &cst) const
1721 : {
1722 213274273 : if (undefined_p ())
1723 : return false;
1724 :
1725 : // Check if the known bits in bitmask exclude CST.
1726 213186907 : if (!m_bitmask.member_p (cst))
1727 : return false;
1728 :
1729 212660450 : signop sign = TYPE_SIGN (type ());
1730 228419064 : for (unsigned r = 0; r < m_num_ranges; ++r)
1731 : {
1732 228156315 : if (wi::lt_p (cst, lower_bound (r), sign))
1733 : return false;
1734 124572033 : if (wi::le_p (cst, upper_bound (r), sign))
1735 : return true;
1736 : }
1737 :
1738 : return false;
1739 : }
1740 :
1741 : // Perform an efficient union with R when both ranges have only a single pair.
1742 : // Excluded are VARYING and UNDEFINED ranges.
1743 :
1744 : bool
1745 112071271 : irange::irange_single_pair_union (const irange &r)
1746 : {
1747 112071271 : gcc_checking_assert (!undefined_p () && !varying_p ());
1748 112071271 : gcc_checking_assert (!r.undefined_p () && !varying_p ());
1749 :
1750 112071271 : signop sign = TYPE_SIGN (m_type);
1751 : // Check if current lower bound is also the new lower bound.
1752 112071271 : if (wi::le_p (m_base[0], r.m_base[0], sign))
1753 : {
1754 : // If current upper bound is new upper bound, we're done.
1755 97982274 : if (wi::le_p (r.m_base[1], m_base[1], sign))
1756 14370637 : return union_bitmask (r);
1757 : // Otherwise R has the new upper bound.
1758 : // Check for overlap/touching ranges, or single target range.
1759 167223274 : if (m_max_ranges == 1
1760 334446536 : || (widest_int::from (m_base[1], sign) + 1
1761 334446536 : >= widest_int::from (r.m_base[0], TYPE_SIGN (r.m_type))))
1762 26333447 : m_base[1] = r.m_base[1];
1763 : else
1764 : {
1765 : // This is a dual range result.
1766 57278190 : m_base[2] = r.m_base[0];
1767 57278190 : m_base[3] = r.m_base[1];
1768 57278190 : m_num_ranges = 2;
1769 : }
1770 : // The range has been altered, so normalize it even if nothing
1771 : // changed in the mask.
1772 83611637 : if (!union_bitmask (r))
1773 82707599 : normalize_kind ();
1774 83611637 : if (flag_checking)
1775 83611500 : verify_range ();
1776 83611637 : return true;
1777 : }
1778 :
1779 : // Set the new lower bound to R's lower bound.
1780 14088997 : wide_int lb = m_base[0];
1781 14088997 : m_base[0] = r.m_base[0];
1782 :
1783 : // If R fully contains THIS range, just set the upper bound.
1784 14088997 : if (wi::ge_p (r.m_base[1], m_base[1], sign))
1785 1441130 : m_base[1] = r.m_base[1];
1786 : // Check for overlapping ranges, or target limited to a single range.
1787 25295734 : else if (m_max_ranges == 1
1788 50591468 : || (widest_int::from (r.m_base[1], TYPE_SIGN (r.m_type)) + 1
1789 50591468 : >= widest_int::from (lb, sign)))
1790 : ;
1791 : else
1792 : {
1793 : // Left with 2 pairs.
1794 5982547 : m_num_ranges = 2;
1795 5982547 : m_base[2] = lb;
1796 5982547 : m_base[3] = m_base[1];
1797 5982547 : m_base[1] = r.m_base[1];
1798 : }
1799 : // The range has been altered, so normalize it even if nothing
1800 : // changed in the mask.
1801 14088997 : if (!union_bitmask (r))
1802 13047983 : normalize_kind ();
1803 14088997 : if (flag_checking)
1804 14088986 : verify_range ();
1805 14088997 : return true;
1806 14088997 : }
1807 :
1808 : // Append R to this range, knowing that R occurs after all of these subranges.
1809 : // Return TRUE as something must have changed.
1810 :
1811 : bool
1812 136475941 : irange::union_append (const irange &r)
1813 : {
1814 : // Check if the first range in R is an immmediate successor to the last
1815 : // range, ths requiring a merge.
1816 136475941 : signop sign = TYPE_SIGN (m_type);
1817 136475941 : wide_int lb = r.lower_bound ();
1818 136475941 : wide_int ub = upper_bound ();
1819 136475941 : unsigned start = 0;
1820 409427823 : if (widest_int::from (ub, sign) + 1
1821 409427823 : == widest_int::from (lb, sign))
1822 : {
1823 942075 : m_base[m_num_ranges * 2 - 1] = r.m_base[1];
1824 942075 : start = 1;
1825 : }
1826 136475941 : maybe_resize (m_num_ranges + r.m_num_ranges - start);
1827 408631389 : for ( ; start < r.m_num_ranges; start++)
1828 : {
1829 : // Merge the last ranges if it exceeds the maximum size.
1830 136450927 : if (m_num_ranges + 1 > m_max_ranges)
1831 : {
1832 771420 : m_base[m_max_ranges * 2 - 1] = r.m_base[r.m_num_ranges * 2 - 1];
1833 771420 : break;
1834 : }
1835 135679507 : m_base[m_num_ranges * 2] = r.m_base[start * 2];
1836 135679507 : m_base[m_num_ranges * 2 + 1] = r.m_base[start * 2 + 1];
1837 135679507 : m_num_ranges++;
1838 : }
1839 :
1840 136475941 : if (!union_bitmask (r))
1841 136438800 : normalize_kind ();
1842 136475941 : if (flag_checking)
1843 136475941 : verify_range ();
1844 136475941 : return true;
1845 136475941 : }
1846 :
1847 : // Return TRUE if anything changes.
1848 :
1849 : bool
1850 386447076 : irange::union_ (const vrange &v)
1851 : {
1852 386447076 : const irange &r = as_a <irange> (v);
1853 :
1854 386447076 : if (r.undefined_p ())
1855 : return false;
1856 :
1857 384212245 : if (undefined_p ())
1858 : {
1859 92859331 : operator= (r);
1860 92859331 : if (flag_checking)
1861 92858749 : verify_range ();
1862 92859331 : return true;
1863 : }
1864 :
1865 291352914 : if (varying_p ())
1866 : return false;
1867 :
1868 281519784 : if (r.varying_p ())
1869 : {
1870 6743998 : set_varying (type ());
1871 6743998 : return true;
1872 : }
1873 :
1874 : // Special case one range union one range.
1875 274775786 : if (m_num_ranges == 1 && r.m_num_ranges == 1)
1876 112071271 : return irange_single_pair_union (r);
1877 :
1878 162704515 : signop sign = TYPE_SIGN (m_type);
1879 : // Check for an append to the end.
1880 488113545 : if (m_kind == VR_RANGE && wi::gt_p (r.lower_bound (), upper_bound (), sign))
1881 136475941 : return union_append (r);
1882 :
1883 : // If this ranges fully contains R, then we need do nothing.
1884 26228574 : if (irange_contains_p (r))
1885 4069546 : return union_bitmask (r);
1886 :
1887 : // Do not worry about merging and such by reserving twice as many
1888 : // pairs as needed, and then simply sort the 2 ranges into this
1889 : // intermediate form.
1890 : //
1891 : // The intermediate result will have the property that the beginning
1892 : // of each range is <= the beginning of the next range. There may
1893 : // be overlapping ranges at this point. I.e. this would be valid
1894 : // [-20, 10], [-10, 0], [0, 20], [40, 90] as it satisfies this
1895 : // constraint : -20 < -10 < 0 < 40. When the range is rebuilt into r,
1896 : // the merge is performed.
1897 : //
1898 : // [Xi,Yi]..[Xn,Yn] U [Xj,Yj]..[Xm,Ym] --> [Xk,Yk]..[Xp,Yp]
1899 22159028 : auto_vec<wide_int, 20> res (m_num_ranges * 2 + r.m_num_ranges * 2);
1900 22159028 : unsigned i = 0, j = 0, k = 0;
1901 :
1902 96994868 : while (i < m_num_ranges * 2 && j < r.m_num_ranges * 2)
1903 : {
1904 : // lower of Xi and Xj is the lowest point.
1905 105353624 : if (widest_int::from (m_base[i], sign)
1906 158030436 : <= widest_int::from (r.m_base[j], sign))
1907 : {
1908 27605815 : res.quick_push (m_base[i]);
1909 27605815 : res.quick_push (m_base[i + 1]);
1910 27605815 : k += 2;
1911 27605815 : i += 2;
1912 : }
1913 : else
1914 : {
1915 25070997 : res.quick_push (r.m_base[j]);
1916 25070997 : res.quick_push (r.m_base[j + 1]);
1917 25070997 : k += 2;
1918 25070997 : j += 2;
1919 : }
1920 : }
1921 44834507 : for ( ; i < m_num_ranges * 2; i += 2)
1922 : {
1923 22675479 : res.quick_push (m_base[i]);
1924 22675479 : res.quick_push (m_base[i + 1]);
1925 22675479 : k += 2;
1926 : }
1927 28506255 : for ( ; j < r.m_num_ranges * 2; j += 2)
1928 : {
1929 6347227 : res.quick_push (r.m_base[j]);
1930 6347227 : res.quick_push (r.m_base[j + 1]);
1931 6347227 : k += 2;
1932 : }
1933 :
1934 : // Now normalize the vector removing any overlaps.
1935 : i = 2;
1936 81699518 : for (j = 2; j < k ; j += 2)
1937 : {
1938 : // Current upper+1 is >= lower bound next pair, then we merge ranges.
1939 178621483 : if (widest_int::from (res[i - 1], sign) + 1
1940 178621470 : >= widest_int::from (res[j], sign))
1941 : {
1942 : // New upper bounds is greater of current or the next one.
1943 51411536 : if (widest_int::from (res[j + 1], sign)
1944 77117304 : > widest_int::from (res[i - 1], sign))
1945 19624576 : res[i - 1] = res[j + 1];
1946 : }
1947 : else
1948 : {
1949 : // This is a new distinct range, but no point in copying it
1950 : // if it is already in the right place.
1951 33834722 : if (i != j)
1952 : {
1953 11030522 : res[i++] = res[j];
1954 11030522 : res[i++] = res[j + 1];
1955 : }
1956 : else
1957 22804200 : i += 2;
1958 : }
1959 : }
1960 :
1961 : // At this point, the vector should have i ranges, none overlapping.
1962 : // Now it simply needs to be copied, and if there are too many
1963 : // ranges, merge some. We wont do any analysis as to what the
1964 : // "best" merges are, simply combine the final ranges into one.
1965 22159028 : maybe_resize (i / 2);
1966 22159028 : if (i > m_max_ranges * 2)
1967 : {
1968 1412 : res[m_max_ranges * 2 - 1] = res[i - 1];
1969 1412 : i = m_max_ranges * 2;
1970 : }
1971 :
1972 134143704 : for (j = 0; j < i ; j++)
1973 111984676 : m_base[j] = res [j];
1974 22159028 : m_num_ranges = i / 2;
1975 :
1976 22159028 : m_kind = VR_RANGE;
1977 : // The range has been altered, so normalize it even if nothing
1978 : // changed in the mask.
1979 22159028 : if (!union_bitmask (r))
1980 21194804 : normalize_kind ();
1981 22159028 : if (flag_checking)
1982 22158981 : verify_range ();
1983 22159028 : return true;
1984 22159028 : }
1985 :
1986 : // Return TRUE if THIS fully contains R. No undefined or varying cases.
1987 :
1988 : bool
1989 179732096 : irange::irange_contains_p (const irange &r) const
1990 : {
1991 179732096 : gcc_checking_assert (!undefined_p () && !varying_p ());
1992 179732096 : gcc_checking_assert (!r.undefined_p () && !varying_p ());
1993 :
1994 : // Check singletons directly which will include any bitmasks.
1995 179732096 : wide_int rl;
1996 179732096 : if (r.singleton_p (rl))
1997 14147862 : return contains_p (rl);
1998 :
1999 : // In order for THIS to fully contain R, all of the pairs within R must
2000 : // be fully contained by the pairs in this object.
2001 165584234 : signop sign = TYPE_SIGN (m_type);
2002 165584234 : unsigned ri = 0;
2003 165584234 : unsigned i = 0;
2004 165584234 : rl = r.m_base[0];
2005 165584234 : wide_int ru = r.m_base[1];
2006 165584234 : wide_int l = m_base[0];
2007 165584234 : wide_int u = m_base[1];
2008 430469250 : while (1)
2009 : {
2010 : // If r is contained within this range, move to the next R
2011 430469250 : if (wi::ge_p (rl, l, sign)
2012 430469250 : && wi::le_p (ru, u, sign))
2013 : {
2014 : // This pair is OK, Either done, or bump to the next.
2015 201000550 : if (++ri >= r.num_pairs ())
2016 : return true;
2017 131253673 : rl = r.m_base[ri * 2];
2018 131253673 : ru = r.m_base[ri * 2 + 1];
2019 131253673 : continue;
2020 : }
2021 : // Otherwise, check if this's pair occurs before R's.
2022 229468700 : if (wi::lt_p (u, rl, sign))
2023 : {
2024 : // There's still at least one pair of R left.
2025 134340828 : if (++i >= num_pairs ())
2026 : return false;
2027 133631343 : l = m_base[i * 2];
2028 133631343 : u = m_base[i * 2 + 1];
2029 133631343 : continue;
2030 : }
2031 : return false;
2032 : }
2033 : return false;
2034 165586496 : }
2035 :
2036 :
2037 : // Return TRUE if anything changes.
2038 :
2039 : bool
2040 893562251 : irange::intersect (const vrange &v)
2041 : {
2042 893562251 : const irange &r = as_a <irange> (v);
2043 893562251 : gcc_checking_assert (undefined_p () || r.undefined_p ()
2044 : || range_compatible_p (type (), r.type ()));
2045 :
2046 893562251 : if (undefined_p ())
2047 : return false;
2048 892511096 : if (r.undefined_p ())
2049 : {
2050 459370 : set_undefined ();
2051 459370 : return true;
2052 : }
2053 892051726 : if (r.varying_p ())
2054 : return false;
2055 596738841 : if (varying_p ())
2056 : {
2057 81825603 : operator= (r);
2058 81825603 : return true;
2059 : }
2060 :
2061 514913238 : if (r.num_pairs () == 1)
2062 : {
2063 361401737 : bool res = intersect (r.lower_bound (), r.upper_bound ());
2064 361400169 : if (undefined_p ())
2065 : return true;
2066 :
2067 334665485 : res |= intersect_bitmask (r);
2068 334665485 : if (res)
2069 115965763 : normalize_kind ();
2070 334665485 : return res;
2071 : }
2072 :
2073 : // If either range is a singleton and the other range does not contain
2074 : // it, the result is undefined.
2075 153513069 : wide_int val;
2076 154642272 : if ((singleton_p (val) && !r.contains_p (val))
2077 154632725 : || (r.singleton_p (val) && !contains_p (val)))
2078 : {
2079 9547 : set_undefined ();
2080 9547 : return true;
2081 : }
2082 :
2083 : // If R fully contains this, then intersection will change nothing.
2084 153503522 : if (r.irange_contains_p (*this))
2085 68396736 : return intersect_bitmask (r);
2086 :
2087 : // ?? We could probably come up with something smarter than the
2088 : // worst case scenario here.
2089 85106786 : int needed = num_pairs () + r.num_pairs ();
2090 85106786 : maybe_resize (needed);
2091 :
2092 85106786 : signop sign = TYPE_SIGN (m_type);
2093 85106786 : unsigned bld_pair = 0;
2094 85106786 : unsigned bld_lim = m_max_ranges;
2095 85106786 : int_range_max r2 (*this);
2096 85106786 : unsigned r2_lim = r2.num_pairs ();
2097 85106786 : unsigned i2 = 0;
2098 249074073 : for (unsigned i = 0; i < r.num_pairs (); )
2099 : {
2100 : // If r1's upper is < r2's lower, we can skip r1's pair.
2101 221300533 : wide_int ru = r.m_base[i * 2 + 1];
2102 221300533 : wide_int r2l = r2.m_base[i2 * 2];
2103 221300533 : if (wi::lt_p (ru, r2l, sign))
2104 : {
2105 20601360 : i++;
2106 20601360 : continue;
2107 : }
2108 : // Likewise, skip r2's pair if its excluded.
2109 200699173 : wide_int r2u = r2.m_base[i2 * 2 + 1];
2110 200699173 : wide_int rl = r.m_base[i * 2];
2111 200699173 : if (wi::lt_p (r2u, rl, sign))
2112 : {
2113 21091790 : i2++;
2114 21091790 : if (i2 < r2_lim)
2115 16640273 : continue;
2116 : // No more r2, break.
2117 : break;
2118 : }
2119 :
2120 : // Must be some overlap. Find the highest of the lower bounds,
2121 : // and set it, unless the build limits lower bounds is already
2122 : // set.
2123 179607383 : if (bld_pair < bld_lim)
2124 : {
2125 179304950 : if (wi::ge_p (rl, r2l, sign))
2126 152309143 : m_base[bld_pair * 2] = rl;
2127 : else
2128 26995807 : m_base[bld_pair * 2] = r2l;
2129 : }
2130 : else
2131 : // Decrease and set a new upper.
2132 302433 : bld_pair--;
2133 :
2134 : // ...and choose the lower of the upper bounds.
2135 179607383 : if (wi::le_p (ru, r2u, sign))
2136 : {
2137 114989671 : m_base[bld_pair * 2 + 1] = ru;
2138 114989671 : bld_pair++;
2139 : // Move past the r1 pair and keep trying.
2140 114989671 : i++;
2141 114989671 : continue;
2142 : }
2143 : else
2144 : {
2145 64617712 : m_base[bld_pair * 2 + 1] = r2u;
2146 64617712 : bld_pair++;
2147 64617712 : i2++;
2148 64617712 : if (i2 < r2_lim)
2149 11735983 : continue;
2150 : // No more r2, break.
2151 : break;
2152 : }
2153 : // r2 has the higher lower bound.
2154 364667746 : }
2155 :
2156 : // At the exit of this loop, it is one of 2 things:
2157 : // ran out of r1, or r2, but either means we are done.
2158 85106786 : m_num_ranges = bld_pair;
2159 85106786 : if (m_num_ranges == 0)
2160 : {
2161 96325 : set_undefined ();
2162 96325 : return true;
2163 : }
2164 :
2165 85010461 : m_kind = VR_RANGE;
2166 : // Snap subranges if there is a bitmask. See PR 123319.
2167 85010461 : if (!m_bitmask.unknown_p ())
2168 : {
2169 18892091 : snap_subranges ();
2170 18892091 : if (undefined_p ())
2171 : return true;
2172 : }
2173 : // The range has been altered, so normalize it even if nothing
2174 : // changed in the mask.
2175 85010225 : if (!intersect_bitmask (r))
2176 78146788 : normalize_kind ();
2177 85010225 : if (flag_checking)
2178 85010158 : verify_range ();
2179 : return true;
2180 238619855 : }
2181 :
2182 :
2183 : // Multirange intersect for a specified wide_int [lb, ub] range.
2184 : // Return TRUE if intersect changed anything.
2185 : //
2186 : // NOTE: It is the caller's responsibility to intersect the mask.
2187 :
2188 : bool
2189 361400169 : irange::intersect (const wide_int& lb, const wide_int& ub)
2190 : {
2191 : // Undefined remains undefined.
2192 361400169 : if (undefined_p ())
2193 : return false;
2194 :
2195 361400169 : tree range_type = type();
2196 361400169 : signop sign = TYPE_SIGN (range_type);
2197 :
2198 361400169 : gcc_checking_assert (TYPE_PRECISION (range_type) == wi::get_precision (lb));
2199 361400169 : gcc_checking_assert (TYPE_PRECISION (range_type) == wi::get_precision (ub));
2200 :
2201 : // If this range is fully contained, then intersection will do nothing.
2202 722800338 : if (wi::ge_p (lower_bound (), lb, sign)
2203 650496995 : && wi::le_p (upper_bound (), ub, sign))
2204 : return false;
2205 :
2206 129422956 : unsigned bld_index = 0;
2207 129422956 : unsigned pair_lim = num_pairs ();
2208 194395680 : for (unsigned i = 0; i < pair_lim; i++)
2209 : {
2210 143595573 : wide_int pairl = m_base[i * 2];
2211 143595573 : wide_int pairu = m_base[i * 2 + 1];
2212 : // Once UB is less than a pairs lower bound, we're done.
2213 143595573 : if (wi::lt_p (ub, pairl, sign))
2214 : break;
2215 : // if LB is greater than this pairs upper, this pair is excluded.
2216 122192516 : if (wi::lt_p (pairu, lb, sign))
2217 17760444 : continue;
2218 :
2219 : // Must be some overlap. Find the highest of the lower bounds,
2220 : // and set it
2221 104432072 : if (wi::gt_p (lb, pairl, sign))
2222 56734320 : m_base[bld_index * 2] = lb;
2223 : else
2224 47697752 : m_base[bld_index * 2] = pairl;
2225 :
2226 : // ...and choose the lower of the upper bounds and if the base pair
2227 : // has the lower upper bound, need to check next pair too.
2228 104432072 : if (wi::lt_p (ub, pairu, sign))
2229 : {
2230 57219792 : m_base[bld_index++ * 2 + 1] = ub;
2231 57219792 : break;
2232 : }
2233 : else
2234 47212280 : m_base[bld_index++ * 2 + 1] = pairu;
2235 143596013 : }
2236 :
2237 129422956 : m_num_ranges = bld_index;
2238 129422956 : if (m_num_ranges == 0)
2239 : {
2240 26734684 : set_undefined ();
2241 26734684 : return true;
2242 : }
2243 :
2244 102688272 : m_kind = VR_RANGE;
2245 : // The caller must normalize and verify the range, as the bitmask
2246 : // still needs to be handled.
2247 102688272 : return true;
2248 : }
2249 :
2250 :
2251 : // Signed 1-bits are strange. You can't subtract 1, because you can't
2252 : // represent the number 1. This works around that for the invert routine.
2253 :
2254 : static wide_int inline
2255 57322051 : subtract_one (const wide_int &x, tree type, wi::overflow_type &overflow)
2256 : {
2257 57322051 : if (TYPE_SIGN (type) == SIGNED)
2258 34518194 : return wi::add (x, -1, SIGNED, &overflow);
2259 : else
2260 22803857 : return wi::sub (x, 1, UNSIGNED, &overflow);
2261 : }
2262 :
2263 : // The analogous function for adding 1.
2264 :
2265 : static wide_int inline
2266 59475798 : add_one (const wide_int &x, tree type, wi::overflow_type &overflow)
2267 : {
2268 59475798 : if (TYPE_SIGN (type) == SIGNED)
2269 29003316 : return wi::sub (x, -1, SIGNED, &overflow);
2270 : else
2271 30472482 : return wi::add (x, 1, UNSIGNED, &overflow);
2272 : }
2273 :
2274 : // Return the inverse of a range.
2275 :
2276 : void
2277 60384295 : irange::invert ()
2278 : {
2279 60384295 : gcc_checking_assert (!undefined_p () && !varying_p ());
2280 :
2281 : // We always need one more set of bounds to represent an inverse, so
2282 : // if we're at the limit, we can't properly represent things.
2283 : //
2284 : // For instance, to represent the inverse of a 2 sub-range set
2285 : // [5, 10][20, 30], we would need a 3 sub-range set
2286 : // [-MIN, 4][11, 19][31, MAX].
2287 : //
2288 : // In this case, return the most conservative thing.
2289 : //
2290 : // However, if any of the extremes of the range are -MIN/+MAX, we
2291 : // know we will not need an extra bound. For example:
2292 : //
2293 : // INVERT([-MIN,20][30,40]) => [21,29][41,+MAX]
2294 : // INVERT([-MIN,20][30,MAX]) => [21,29]
2295 60384295 : tree ttype = type ();
2296 60384295 : unsigned prec = TYPE_PRECISION (ttype);
2297 60384295 : signop sign = TYPE_SIGN (ttype);
2298 60384295 : wide_int type_min = wi::min_value (prec, sign);
2299 60384295 : wide_int type_max = wi::max_value (prec, sign);
2300 60384295 : m_bitmask.set_unknown (prec);
2301 :
2302 : // At this point, we need one extra sub-range to represent the
2303 : // inverse.
2304 60384295 : maybe_resize (m_num_ranges + 1);
2305 :
2306 : // The algorithm is as follows. To calculate INVERT ([a,b][c,d]), we
2307 : // generate [-MIN, a-1][b+1, c-1][d+1, MAX].
2308 : //
2309 : // If there is an over/underflow in the calculation for any
2310 : // sub-range, we eliminate that subrange. This allows us to easily
2311 : // calculate INVERT([-MIN, 5]) with: [-MIN, -MIN-1][6, MAX]. And since
2312 : // we eliminate the underflow, only [6, MAX] remains.
2313 60384295 : unsigned i = 0;
2314 60384295 : wi::overflow_type ovf;
2315 : // Construct leftmost range.
2316 60384295 : int_range_max orig_range (*this);
2317 60384295 : unsigned nitems = 0;
2318 60384295 : wide_int tmp;
2319 : // If this is going to underflow on the MINUS 1, don't even bother
2320 : // checking. This also handles subtracting one from an unsigned 0,
2321 : // which doesn't set the underflow bit.
2322 60384340 : if (type_min != orig_range.lower_bound ())
2323 : {
2324 49774626 : m_base[nitems++] = type_min;
2325 49774671 : tmp = subtract_one (orig_range.lower_bound (), ttype, ovf);
2326 49774626 : m_base[nitems++] = tmp;
2327 49774626 : if (ovf)
2328 10609669 : nitems = 0;
2329 : }
2330 60384295 : i++;
2331 : // Construct middle ranges if applicable.
2332 60384295 : if (orig_range.num_pairs () > 1)
2333 : {
2334 : unsigned j = i;
2335 15082970 : for (; j < (orig_range.num_pairs () * 2) - 1; j += 2)
2336 : {
2337 : // The middle ranges cannot have MAX/MIN, so there's no need
2338 : // to check for unsigned overflow on the +1 and -1 here.
2339 7547425 : tmp = wi::add (orig_range.m_base[j], 1, sign, &ovf);
2340 7547425 : m_base[nitems++] = tmp;
2341 7547425 : tmp = subtract_one (orig_range.m_base[j + 1], ttype, ovf);
2342 7547425 : m_base[nitems++] = tmp;
2343 7547425 : if (ovf)
2344 0 : nitems -= 2;
2345 : }
2346 : i = j;
2347 : }
2348 : // Construct rightmost range.
2349 : //
2350 : // However, if this will overflow on the PLUS 1, don't even bother.
2351 : // This also handles adding one to an unsigned MAX, which doesn't
2352 : // set the overflow bit.
2353 60384295 : if (type_max != orig_range.m_base[i])
2354 : {
2355 59475798 : tmp = add_one (orig_range.m_base[i], ttype, ovf);
2356 59475798 : m_base[nitems++] = tmp;
2357 59475798 : m_base[nitems++] = type_max;
2358 59475798 : if (ovf)
2359 908497 : nitems -= 2;
2360 : }
2361 60384295 : m_num_ranges = nitems / 2;
2362 :
2363 : // We disallow undefined or varying coming in, so the result can
2364 : // only be a VR_RANGE.
2365 60384295 : gcc_checking_assert (m_kind == VR_RANGE);
2366 :
2367 60384295 : if (flag_checking)
2368 60384165 : verify_range ();
2369 60384340 : }
2370 :
2371 : // This routine will take the bounds [LB, UB], and apply the bitmask to those
2372 : // values such that both bounds satisfy the bitmask. TRUE is returned
2373 : // if either bound changes, and they are returned as [NEW_LB, NEW_UB].
2374 : // If there is an overflow, or if (NEW_UB < NEW_LB), then the entire bound is
2375 : // to be removed as none of the values are valid. This is indicated by
2376 : // teturning TRUE in OVF. False indicates the bounds are fine.
2377 : // ie, [4, 14] MASK 0xFFFE VALUE 0x1
2378 : // means all values must be odd, the new bounds returned will be [5, 13] with
2379 : // OVF set to FALSE.
2380 : // ie, [4, 4] MASK 0xFFFE VALUE 0x1
2381 : // would return TRUE and OVF == TRUE. The entire subrange should be removed.
2382 :
2383 : bool
2384 224436941 : irange::snap (const wide_int &lb, const wide_int &ub,
2385 : wide_int &new_lb, wide_int &new_ub, bool &ovf)
2386 : {
2387 224436941 : ovf = false;
2388 224436941 : int z = wi::ctz (m_bitmask.mask ());
2389 224436941 : if (z == 0)
2390 : return false;
2391 :
2392 : // Shortcircuit check for values that are already good.
2393 261011460 : if ((((lb ^ m_bitmask.value ()) | (ub ^ m_bitmask.value ()))
2394 391516878 : & ~m_bitmask.mask ()) == 0)
2395 : return false;
2396 :
2397 13642468 : const wide_int step = (wi::one (TYPE_PRECISION (type ())) << z);
2398 13642468 : const wide_int match_mask = step - 1;
2399 13642468 : const wide_int value = m_bitmask.value () & match_mask;
2400 :
2401 13642468 : wide_int rem_lb = lb & match_mask;
2402 13642468 : wide_int offset = (value - rem_lb) & match_mask;
2403 13642468 : new_lb = lb + offset;
2404 : // Check for overflows at +INF
2405 13642468 : if (wi::lt_p (new_lb, lb, TYPE_SIGN (type ())))
2406 : {
2407 1956 : ovf = true;
2408 1956 : return true;
2409 : }
2410 :
2411 13640512 : wide_int rem_ub = ub & match_mask;
2412 13640512 : wide_int offset_ub = (rem_ub - value) & match_mask;
2413 13640512 : new_ub = ub - offset_ub;
2414 : // Check for underflows at -INF
2415 13640512 : if (wi::gt_p (new_ub, ub, TYPE_SIGN (type ())))
2416 : {
2417 113474 : ovf = true;
2418 113474 : return true;
2419 : }
2420 :
2421 : // If inverted range is invalid, set overflow to TRUE.
2422 13527038 : if (wi::lt_p (new_ub, new_lb, TYPE_SIGN (type ())))
2423 : {
2424 13911 : ovf = true;
2425 13911 : return true;
2426 : }
2427 24417981 : return (new_lb != lb) || (new_ub != ub);
2428 27283060 : }
2429 :
2430 : // This method loops through the subranges in THIS, and adjusts any bounds
2431 : // to satisfy the contraints of the BITMASK. If a subrange is invalid,
2432 : // it is removed. TRUE is returned if there were any changes.
2433 :
2434 : bool
2435 142516760 : irange::snap_subranges ()
2436 : {
2437 142516760 : bool changed = false;
2438 142516760 : int_range_max invalid;
2439 142516760 : unsigned x;
2440 142516760 : wide_int lb, ub;
2441 366953701 : for (x = 0; x < m_num_ranges; x++)
2442 : {
2443 224436941 : bool ovf;
2444 224439339 : if (snap (lower_bound (x), upper_bound (x), lb, ub, ovf))
2445 : {
2446 13415129 : changed = true;
2447 : // Check if this subrange is to be completely removed.
2448 13415129 : if (ovf)
2449 : {
2450 129341 : int_range<1> tmp (type (), lower_bound (x), upper_bound (x));
2451 129341 : invalid.union_ (tmp);
2452 129341 : continue;
2453 129341 : }
2454 13285804 : if (lower_bound (x) != lb)
2455 2608273 : m_base[x * 2] = lb;
2456 13285804 : if (upper_bound (x) != ub)
2457 11293660 : m_base[x * 2 + 1] = ub;
2458 : }
2459 : }
2460 : // Remove any subranges which are no invalid.
2461 142516760 : if (!invalid.undefined_p ())
2462 : {
2463 123915 : invalid.invert ();
2464 123915 : intersect (invalid);
2465 : }
2466 142516760 : return changed;
2467 142516776 : }
2468 :
2469 : // If the bitmask has a range representation, intersect this range with
2470 : // the bitmasks range. Then ensure all enpoints match the bitmask.
2471 : // Return TRUE if the range changes at all.
2472 :
2473 : bool
2474 123624669 : irange::set_range_from_bitmask ()
2475 : {
2476 123624669 : gcc_checking_assert (!undefined_p ());
2477 : // Snap subranmges when bitmask is first set.
2478 123624669 : snap_subranges ();
2479 123624669 : if (undefined_p ())
2480 : return true;
2481 :
2482 : // Calculate the set of ranges valid for the bitmask.
2483 123624624 : int_range_max allow;
2484 123624624 : if (!m_bitmask.range_from_mask (allow, m_type))
2485 : return false;
2486 : // And intersect that set of ranges with the current set.
2487 123550411 : return intersect (allow);
2488 123624624 : }
2489 :
2490 : void
2491 178529808 : irange::update_bitmask (const irange_bitmask &bm)
2492 : {
2493 178529808 : gcc_checking_assert (!undefined_p ());
2494 :
2495 : // If masks are the same, there is no change.
2496 178529808 : if (m_bitmask == bm)
2497 : return;
2498 :
2499 : // Drop VARYINGs with known bits to a plain range.
2500 86785800 : if (m_kind == VR_VARYING && !bm.unknown_p ())
2501 15535621 : m_kind = VR_RANGE;
2502 :
2503 71250179 : m_bitmask = bm;
2504 71250179 : if (!set_range_from_bitmask ())
2505 41569830 : normalize_kind ();
2506 71250179 : if (flag_checking)
2507 71250069 : verify_range ();
2508 : }
2509 :
2510 : // Return the bitmask of known bits that includes the bitmask inherent
2511 : // in the range.
2512 :
2513 : irange_bitmask
2514 1101647353 : irange::get_bitmask () const
2515 : {
2516 1101647353 : gcc_checking_assert (!undefined_p ());
2517 :
2518 : // The mask inherent in the range is calculated on-demand. For
2519 : // example, [0,255] does not have known bits set by default. This
2520 : // saves us considerable time, because setting it at creation incurs
2521 : // a large penalty for irange::set. At the time of writing there
2522 : // was a 5% slowdown in VRP if we kept the mask precisely up to date
2523 : // at all times. Instead, we default to -1 and set it when
2524 : // explicitly requested. However, this function will always return
2525 : // the correct mask.
2526 : //
2527 : // This also means that the mask may have a finer granularity than
2528 : // the range and thus contradict it. Think of the mask as an
2529 : // enhancement to the range. For example:
2530 : //
2531 : // [3, 1000] MASK 0xfffffffe VALUE 0x0
2532 : //
2533 : // 3 is in the range endpoints, but is excluded per the known 0 bits
2534 : // in the mask.
2535 : //
2536 : // See also the note in irange_bitmask::intersect.
2537 1101652795 : irange_bitmask bm (type (), lower_bound (), upper_bound ());
2538 1101647353 : if (!m_bitmask.unknown_p ())
2539 : {
2540 : // If the new intersection is unknown, it means there are inconstent
2541 : // bits, so simply return the original bitmask.
2542 507089621 : if (!bm.intersect (m_bitmask))
2543 18423 : return m_bitmask;
2544 : }
2545 1101628930 : return bm;
2546 1101647353 : }
2547 :
2548 : // Set the nonzero bits in R into THIS. Return TRUE and
2549 : // normalize the range if anything changed.
2550 :
2551 : void
2552 638945 : vrange::set_nonzero_bits (const wide_int &bits)
2553 : {
2554 638945 : gcc_checking_assert (!undefined_p ());
2555 638945 : irange_bitmask bm (wi::zero (TYPE_PRECISION (type ())), bits);
2556 638945 : update_bitmask (bm);
2557 638945 : }
2558 :
2559 : // Return the nonzero bits in R.
2560 :
2561 : wide_int
2562 223564814 : vrange::get_nonzero_bits () const
2563 : {
2564 223564814 : gcc_checking_assert (!undefined_p ());
2565 223564814 : irange_bitmask bm = get_bitmask ();
2566 223565364 : return bm.value () | bm.mask ();
2567 223564814 : }
2568 :
2569 : // Intersect the bitmask in R into THIS and normalize the range.
2570 : // Return TRUE if the intersection changed anything.
2571 :
2572 : bool
2573 488072446 : irange::intersect_bitmask (const irange &r)
2574 : {
2575 488072446 : gcc_checking_assert (!undefined_p () && !r.undefined_p ());
2576 :
2577 : // If the bitmasks are the same, do nothing.
2578 488072446 : if (m_bitmask == r.m_bitmask)
2579 : return false;
2580 :
2581 179267461 : irange_bitmask bm = get_bitmask ();
2582 179267461 : irange_bitmask save = bm;
2583 179267461 : if (!bm.intersect (r.get_bitmask ()))
2584 : {
2585 25534 : set_undefined ();
2586 25534 : return true;
2587 : }
2588 :
2589 : // If the new mask is the same, there is no change.
2590 179241927 : if (m_bitmask == bm)
2591 : return false;
2592 :
2593 52374490 : m_bitmask = bm;
2594 52374490 : if (!set_range_from_bitmask ())
2595 51956609 : normalize_kind ();
2596 52374490 : if (flag_checking)
2597 52374310 : verify_range ();
2598 : return true;
2599 179267461 : }
2600 :
2601 : // Union the bitmask in R into THIS. Return TRUE and normalize the
2602 : // range if anything changed.
2603 :
2604 : bool
2605 274775786 : irange::union_bitmask (const irange &r)
2606 : {
2607 274775786 : gcc_checking_assert (!undefined_p () && !r.undefined_p ());
2608 :
2609 274775786 : if (m_bitmask == r.m_bitmask)
2610 : return false;
2611 :
2612 13019552 : irange_bitmask bm = get_bitmask ();
2613 13019552 : irange_bitmask save = bm;
2614 13019552 : bm.union_ (r.get_bitmask ());
2615 23084103 : if (save == bm && (!bm.unknown_p () || m_bitmask.unknown_p ()))
2616 10064551 : return false;
2617 :
2618 2955001 : m_bitmask = bm;
2619 :
2620 : // Updating m_bitmask may still yield a semantic bitmask (as
2621 : // returned by get_bitmask) which is functionally equivalent to what
2622 : // we originally had. In which case, there's still no change.
2623 2955001 : if (save == get_bitmask ())
2624 : return false;
2625 :
2626 : // No need to call set_range_from_mask, because we'll never
2627 : // narrow the range. Besides, it would cause endless recursion
2628 : // because of the union_ in set_range_from_mask.
2629 2955001 : normalize_kind ();
2630 2955001 : return true;
2631 13019552 : }
2632 :
2633 : tree
2634 8947600 : irange::lbound () const
2635 : {
2636 8947600 : return wide_int_to_tree (type (), lower_bound ());
2637 : }
2638 :
2639 : tree
2640 294233 : irange::ubound () const
2641 : {
2642 294233 : return wide_int_to_tree (type (), upper_bound ());
2643 : }
2644 :
2645 : void
2646 9497051309 : irange_bitmask::verify_mask () const
2647 : {
2648 9497051309 : gcc_assert (m_value.get_precision () == m_mask.get_precision ());
2649 9497051309 : gcc_checking_assert (wi::bit_and (m_mask, m_value) == 0);
2650 9497051309 : }
2651 :
2652 : void
2653 0 : dump_value_range (FILE *file, const vrange *vr)
2654 : {
2655 0 : vr->dump (file);
2656 0 : }
2657 :
2658 : DEBUG_FUNCTION void
2659 0 : debug (const vrange *vr)
2660 : {
2661 0 : dump_value_range (stderr, vr);
2662 0 : fprintf (stderr, "\n");
2663 0 : }
2664 :
2665 : DEBUG_FUNCTION void
2666 0 : debug (const vrange &vr)
2667 : {
2668 0 : debug (&vr);
2669 0 : }
2670 :
2671 : /* Return true, if VAL1 and VAL2 are equal values for VRP purposes. */
2672 :
2673 : bool
2674 57165580 : vrp_operand_equal_p (const_tree val1, const_tree val2)
2675 : {
2676 57165580 : if (val1 == val2)
2677 : return true;
2678 41263327 : if (!val1 || !val2 || !operand_equal_p (val1, val2, 0))
2679 40601107 : return false;
2680 : return true;
2681 : }
2682 :
2683 : #define DEFINE_INT_RANGE_INSTANCE(N) \
2684 : template int_range<N>::int_range(tree_node *, \
2685 : const wide_int &, \
2686 : const wide_int &, \
2687 : value_range_kind); \
2688 : template int_range<N>::int_range(tree); \
2689 : template int_range<N>::int_range(const irange &); \
2690 : template int_range<N>::int_range(const int_range &); \
2691 : template int_range<N>& int_range<N>::operator= (const int_range &);
2692 :
2693 : DEFINE_INT_RANGE_INSTANCE(1)
2694 : DEFINE_INT_RANGE_INSTANCE(2)
2695 : DEFINE_INT_RANGE_INSTANCE(3)
2696 : DEFINE_INT_RANGE_INSTANCE(255)
2697 :
2698 : #if CHECKING_P
2699 : #include "selftest.h"
2700 :
2701 : #define INT(x) wi::shwi ((x), TYPE_PRECISION (integer_type_node))
2702 : #define UINT(x) wi::uhwi ((x), TYPE_PRECISION (unsigned_type_node))
2703 : #define SCHAR(x) wi::shwi ((x), TYPE_PRECISION (signed_char_type_node))
2704 :
2705 : namespace selftest
2706 : {
2707 :
2708 : static int_range<2>
2709 584 : range (tree type, int a, int b, value_range_kind kind = VR_RANGE)
2710 : {
2711 584 : wide_int w1, w2;
2712 584 : if (TYPE_UNSIGNED (type))
2713 : {
2714 40 : w1 = wi::uhwi (a, TYPE_PRECISION (type));
2715 40 : w2 = wi::uhwi (b, TYPE_PRECISION (type));
2716 : }
2717 : else
2718 : {
2719 544 : w1 = wi::shwi (a, TYPE_PRECISION (type));
2720 544 : w2 = wi::shwi (b, TYPE_PRECISION (type));
2721 : }
2722 584 : return int_range<2> (type, w1, w2, kind);
2723 584 : }
2724 :
2725 : static int_range<2>
2726 540 : range_int (int a, int b, value_range_kind kind = VR_RANGE)
2727 : {
2728 0 : return range (integer_type_node, a, b, kind);
2729 : }
2730 :
2731 : static int_range<2>
2732 8 : range_uint (int a, int b, value_range_kind kind = VR_RANGE)
2733 : {
2734 0 : return range (unsigned_type_node, a, b, kind);
2735 : }
2736 :
2737 : static int_range<2>
2738 8 : range_uint128 (int a, int b, value_range_kind kind = VR_RANGE)
2739 : {
2740 8 : tree u128_type_node = build_nonstandard_integer_type (128, 1);
2741 8 : return range (u128_type_node, a, b, kind);
2742 : }
2743 :
2744 : static int_range<2>
2745 12 : range_uchar (int a, int b, value_range_kind kind = VR_RANGE)
2746 : {
2747 0 : return range (unsigned_char_type_node, a, b, kind);
2748 : }
2749 :
2750 : static int_range<2>
2751 4 : range_char (int a, int b, value_range_kind kind = VR_RANGE)
2752 : {
2753 0 : return range (signed_char_type_node, a, b, kind);
2754 : }
2755 :
2756 : static int_range<3>
2757 44 : build_range3 (int a, int b, int c, int d, int e, int f)
2758 : {
2759 44 : int_range<3> i1 = range_int (a, b);
2760 44 : int_range<3> i2 = range_int (c, d);
2761 44 : int_range<3> i3 = range_int (e, f);
2762 44 : i1.union_ (i2);
2763 44 : i1.union_ (i3);
2764 88 : return i1;
2765 44 : }
2766 :
2767 : static void
2768 4 : range_tests_irange3 ()
2769 : {
2770 4 : int_range<3> r0, r1, r2;
2771 4 : int_range<3> i1, i2, i3;
2772 :
2773 : // ([10,20] U [5,8]) U [1,3] ==> [1,3][5,8][10,20].
2774 4 : r0 = range_int (10, 20);
2775 4 : r1 = range_int (5, 8);
2776 4 : r0.union_ (r1);
2777 4 : r1 = range_int (1, 3);
2778 4 : r0.union_ (r1);
2779 4 : ASSERT_TRUE (r0 == build_range3 (1, 3, 5, 8, 10, 20));
2780 :
2781 : // [1,3][5,8][10,20] U [-5,0] => [-5,3][5,8][10,20].
2782 4 : r1 = range_int (-5, 0);
2783 4 : r0.union_ (r1);
2784 4 : ASSERT_TRUE (r0 == build_range3 (-5, 3, 5, 8, 10, 20));
2785 :
2786 : // [10,20][30,40] U [50,60] ==> [10,20][30,40][50,60].
2787 4 : r1 = range_int (50, 60);
2788 4 : r0 = range_int (10, 20);
2789 4 : r0.union_ (range_int (30, 40));
2790 4 : r0.union_ (r1);
2791 4 : ASSERT_TRUE (r0 == build_range3 (10, 20, 30, 40, 50, 60));
2792 : // [10,20][30,40][50,60] U [70, 80] ==> [10,20][30,40][50,60][70,80].
2793 4 : r1 = range_int (70, 80);
2794 4 : r0.union_ (r1);
2795 :
2796 4 : r2 = build_range3 (10, 20, 30, 40, 50, 60);
2797 4 : r2.union_ (range_int (70, 80));
2798 4 : ASSERT_TRUE (r0 == r2);
2799 :
2800 : // [10,20][30,40][50,60] U [6,35] => [6,40][50,60].
2801 4 : r0 = build_range3 (10, 20, 30, 40, 50, 60);
2802 4 : r1 = range_int (6, 35);
2803 4 : r0.union_ (r1);
2804 4 : r1 = range_int (6, 40);
2805 4 : r1.union_ (range_int (50, 60));
2806 4 : ASSERT_TRUE (r0 == r1);
2807 :
2808 : // [10,20][30,40][50,60] U [6,60] => [6,60].
2809 4 : r0 = build_range3 (10, 20, 30, 40, 50, 60);
2810 4 : r1 = range_int (6, 60);
2811 4 : r0.union_ (r1);
2812 4 : ASSERT_TRUE (r0 == range_int (6, 60));
2813 :
2814 : // [10,20][30,40][50,60] U [6,70] => [6,70].
2815 4 : r0 = build_range3 (10, 20, 30, 40, 50, 60);
2816 4 : r1 = range_int (6, 70);
2817 4 : r0.union_ (r1);
2818 4 : ASSERT_TRUE (r0 == range_int (6, 70));
2819 :
2820 : // [10,20][30,40][50,60] U [35,70] => [10,20][30,70].
2821 4 : r0 = build_range3 (10, 20, 30, 40, 50, 60);
2822 4 : r1 = range_int (35, 70);
2823 4 : r0.union_ (r1);
2824 4 : r1 = range_int (10, 20);
2825 4 : r1.union_ (range_int (30, 70));
2826 4 : ASSERT_TRUE (r0 == r1);
2827 :
2828 : // [10,20][30,40][50,60] U [15,35] => [10,40][50,60].
2829 4 : r0 = build_range3 (10, 20, 30, 40, 50, 60);
2830 4 : r1 = range_int (15, 35);
2831 4 : r0.union_ (r1);
2832 4 : r1 = range_int (10, 40);
2833 4 : r1.union_ (range_int (50, 60));
2834 4 : ASSERT_TRUE (r0 == r1);
2835 :
2836 : // [10,20][30,40][50,60] U [35,35] => [10,20][30,40][50,60].
2837 4 : r0 = build_range3 (10, 20, 30, 40, 50, 60);
2838 4 : r1 = range_int (35, 35);
2839 4 : r0.union_ (r1);
2840 4 : ASSERT_TRUE (r0 == build_range3 (10, 20, 30, 40, 50, 60));
2841 4 : }
2842 :
2843 : static void
2844 4 : range_tests_int_range_max ()
2845 : {
2846 4 : int_range_max big;
2847 4 : unsigned int nrange;
2848 :
2849 : // Build a huge multi-range range.
2850 204 : for (nrange = 0; nrange < 50; ++nrange)
2851 : {
2852 200 : int_range<1> tmp = range_int (nrange*10, nrange *10 + 5);
2853 200 : big.union_ (tmp);
2854 200 : }
2855 4 : ASSERT_TRUE (big.num_pairs () == nrange);
2856 :
2857 : // Verify that we can copy it without loosing precision.
2858 4 : int_range_max copy (big);
2859 4 : ASSERT_TRUE (copy.num_pairs () == nrange);
2860 :
2861 : // Inverting it should produce one more sub-range.
2862 4 : big.invert ();
2863 4 : ASSERT_TRUE (big.num_pairs () == nrange + 1);
2864 :
2865 4 : int_range<1> tmp = range_int (5, 37);
2866 4 : big.intersect (tmp);
2867 4 : ASSERT_TRUE (big.num_pairs () == 4);
2868 :
2869 : // Test that [10,10][20,20] does NOT contain 15.
2870 4 : {
2871 4 : int_range_max i1 = range_int (10, 10);
2872 4 : int_range_max i2 = range_int (20, 20);
2873 4 : i1.union_ (i2);
2874 4 : ASSERT_FALSE (i1.contains_p (INT (15)));
2875 4 : }
2876 4 : }
2877 :
2878 : // Simulate -fstrict-enums where the domain of a type is less than the
2879 : // underlying type.
2880 :
2881 : static void
2882 4 : range_tests_strict_enum ()
2883 : {
2884 : // The enum can only hold [0, 3].
2885 4 : tree rtype = copy_node (unsigned_type_node);
2886 4 : TYPE_MIN_VALUE (rtype) = build_int_cstu (rtype, 0);
2887 4 : TYPE_MAX_VALUE (rtype) = build_int_cstu (rtype, 3);
2888 :
2889 : // Test that even though vr1 covers the strict enum domain ([0, 3]),
2890 : // it does not cover the domain of the underlying type.
2891 4 : int_range<1> vr1 = range (rtype, 0, 1);
2892 4 : int_range<1> vr2 = range (rtype, 2, 3);
2893 4 : vr1.union_ (vr2);
2894 4 : ASSERT_TRUE (vr1 == range (rtype, 0, 3));
2895 4 : ASSERT_FALSE (vr1.varying_p ());
2896 :
2897 : // Test that copying to a multi-range does not change things.
2898 4 : int_range<2> ir1 (vr1);
2899 4 : ASSERT_TRUE (ir1 == vr1);
2900 4 : ASSERT_FALSE (ir1.varying_p ());
2901 :
2902 : // The same test as above, but using TYPE_{MIN,MAX}_VALUE instead of [0,3].
2903 8 : vr1 = int_range<2> (rtype,
2904 8 : wi::to_wide (TYPE_MIN_VALUE (rtype)),
2905 12 : wi::to_wide (TYPE_MAX_VALUE (rtype)));
2906 4 : ir1 = vr1;
2907 4 : ASSERT_TRUE (ir1 == vr1);
2908 4 : ASSERT_FALSE (ir1.varying_p ());
2909 4 : }
2910 :
2911 : // Test that range bounds are "snapped" to where they are expected to be.
2912 :
2913 : static void
2914 104 : assert_snap_result (int lb_val, int ub_val,
2915 : int expected_lb, int expected_ub,
2916 : unsigned mask_val, unsigned value_val,
2917 : tree type)
2918 : {
2919 104 : wide_int lb = wi::shwi (lb_val, TYPE_PRECISION (type));
2920 104 : wide_int ub = wi::shwi (ub_val, TYPE_PRECISION (type));
2921 104 : wide_int new_lb, new_ub;
2922 :
2923 208 : irange_bitmask bm (wi::uhwi (value_val, TYPE_PRECISION (type)),
2924 208 : wi::uhwi (mask_val, TYPE_PRECISION (type)));
2925 :
2926 104 : int_range_max r (type);
2927 104 : r.set (type, lb, ub);
2928 104 : r.update_bitmask (bm);
2929 :
2930 104 : if (TYPE_SIGN (type) == SIGNED && expected_ub < expected_lb)
2931 20 : gcc_checking_assert (r.undefined_p ());
2932 84 : else if (TYPE_SIGN (type) == UNSIGNED
2933 84 : && ((unsigned)expected_ub < (unsigned)expected_lb))
2934 16 : gcc_checking_assert (r.undefined_p ());
2935 : else
2936 : {
2937 68 : gcc_checking_assert (wi::eq_p (r.lower_bound (),
2938 : wi::shwi (expected_lb,
2939 : TYPE_PRECISION (type))));
2940 136 : gcc_checking_assert (wi::eq_p (r.upper_bound (),
2941 : wi::shwi (expected_ub,
2942 : TYPE_PRECISION (type))));
2943 : }
2944 104 : }
2945 :
2946 :
2947 : // Run a selection of tests that confirm, bounds are snapped as expected.
2948 : // We only test individual pairs, multiple pairs use the same snapping
2949 : // routine as single pairs.
2950 :
2951 : static void
2952 4 : test_irange_snap_bounds ()
2953 : {
2954 4 : tree u32 = unsigned_type_node;
2955 4 : tree s32 = integer_type_node;
2956 4 : tree s8 = build_nonstandard_integer_type (8, /*unsigned=*/ 0);
2957 4 : tree s1 = build_nonstandard_integer_type (1, /*unsigned=*/ 0);
2958 4 : tree u1 = build_nonstandard_integer_type (1, /*unsigned=*/ 1);
2959 :
2960 : // Basic aligned range: even-only
2961 4 : assert_snap_result (5, 15, 6, 14, 0xE, 0x0, u32);
2962 : // Singleton that doesn't match mask: undefined.
2963 4 : assert_snap_result (7, 7, 1, 0, 0xFFFFFFFE, 0x0, u32);
2964 : // 8-bit signed char, mask 0xF0 (i.e. step of 16).
2965 4 : assert_snap_result (-100, 100, -96, 96, 0xF0, 0x00, s8);
2966 : // Already aligned range: no change.
2967 4 : assert_snap_result (0, 240, 0, 240, 0xF0, 0x00, u32);
2968 : // Negative range, step 16 alignment (s32).
2969 4 : assert_snap_result (-123, -17, -112, -32, 0xFFFFFFF0, 0x00, s32);
2970 : // Negative range, step 16 alignment (trailing-zero aligned mask).
2971 4 : assert_snap_result (-123, -17, -112, -32, 0xFFFFFFF0, 0x00, s32);
2972 : // s8, 16-alignment mask, value = 0 (valid).
2973 4 : assert_snap_result (-50, 10, -48, 0, 0xF0, 0x00, s8);
2974 : // No values in range [-3,2] match alignment except 0.
2975 4 : assert_snap_result (-3, 2, 0, 0, 0xF8, 0x00, s8);
2976 : // No values in range [-3,2] match alignment — undefined.
2977 4 : assert_snap_result (-3, 2, 1, 0, 0xF8, 0x04, s8);
2978 : // Already aligned range: no change.
2979 4 : assert_snap_result (0, 240, 0, 240, 0xF0, 0x00, s32);
2980 : // 1-bit signed: only -1 allowed (0b1).
2981 4 : assert_snap_result (-1, 0, -1, -1, 0x00, 0x01, s1);
2982 : // 1-bit signed: only 0 allowed (0b0).
2983 4 : assert_snap_result (-1, 0, 0, 0, 0x00, 0x00, s1);
2984 : // 1-bit signed: no match (invalid case).
2985 4 : assert_snap_result (-1, -1, 1, 0, 0x00, 0x00, s1);
2986 : // 1-bit signed: no match (invalid case).
2987 4 : assert_snap_result (0, 0, 1, 0, 0x00, 0x01, s1);
2988 : // 1-bit unsigned: only 1 allowed.
2989 4 : assert_snap_result (0, 1, 1, 1, 0x00, 0x01, u1);
2990 : // 1-bit unsigned: only 0 allowed.
2991 4 : assert_snap_result (0, 1, 0, 0, 0x00, 0x00, u1);
2992 : // 1-bit unsigned: no match (invalid case).
2993 4 : assert_snap_result (1, 1, 1, 0, 0x00, 0x00, u1);
2994 : // 1-bit unsigned: no match (invalid case).
2995 4 : assert_snap_result (0, 0, 1, 0, 0x00, 0x01, u1);
2996 : // Unsigned: Near overflow, even alignment.
2997 4 : assert_snap_result (UINT_MAX - 6, UINT_MAX, UINT_MAX - 5, UINT_MAX - 1,
2998 : 0xFFFFFFFE, 0x00, u32);
2999 : // Unsigned: Wraparound-like range — no valid snapped values.
3000 4 : assert_snap_result (UINT_MAX - 5, UINT_MAX, 1, 0, 0xFFFFFFF0, 0x00, u32);
3001 : // Signed: Near INT_MAX, 8-aligned.
3002 4 : assert_snap_result (INT_MAX - 18, INT_MAX, INT_MAX - 15, INT_MAX - 7,
3003 : 0xFFFFFFF8, 0x00, s32);
3004 : // Signed: Near INT_MIN, 16-aligned.
3005 4 : assert_snap_result (INT_MIN, INT_MIN + 30, INT_MIN, INT_MIN + 16,
3006 : 0xFFFFFFF0, 0x00, s32);
3007 : // Signed: Full domain, 4-aligned.
3008 4 : assert_snap_result (-128, 127, -128, 124, 0xFC, 0x00, s8);
3009 : // Singleton at INT_MIN that doesn’t match alignment — undefined
3010 4 : assert_snap_result (INT_MIN, INT_MIN, 1, 0, 0xFFFFFFFE, 0x01, s32);
3011 : // Range at INT_MIN that doesn’t match alignment — undefined.
3012 4 : assert_snap_result (INT_MIN, INT_MIN + 10, 1, 0, 0xFFFFFFF0, 0x0F, s32);
3013 : // Unsigned: Full domain, 256-aligned.
3014 4 : assert_snap_result (0, UINT_MAX, 0, UINT_MAX & ~255, 0xFFFFFF00, 0x00, u32);
3015 4 : }
3016 :
3017 : static void
3018 4 : range_tests_misc ()
3019 : {
3020 4 : tree u128_type = build_nonstandard_integer_type (128, /*unsigned=*/1);
3021 4 : int_range<2> i1, i2, i3;
3022 4 : int_range<2> r0, r1, rold;
3023 :
3024 : // Test 1-bit signed integer union.
3025 : // [-1,-1] U [0,0] = VARYING.
3026 4 : tree one_bit_type = build_nonstandard_integer_type (1, 0);
3027 4 : wide_int one_bit_min = irange_val_min (one_bit_type);
3028 4 : wide_int one_bit_max = irange_val_max (one_bit_type);
3029 4 : {
3030 4 : int_range<2> min = int_range<2> (one_bit_type, one_bit_min, one_bit_min);
3031 4 : int_range<2> max = int_range<2> (one_bit_type, one_bit_max, one_bit_max);
3032 4 : max.union_ (min);
3033 4 : ASSERT_TRUE (max.varying_p ());
3034 4 : }
3035 : // Test that we can set a range of true+false for a 1-bit signed int.
3036 4 : r0 = range_true_and_false (one_bit_type);
3037 :
3038 : // Test inversion of 1-bit signed integers.
3039 4 : {
3040 4 : int_range<2> min = int_range<2> (one_bit_type, one_bit_min, one_bit_min);
3041 4 : int_range<2> max = int_range<2> (one_bit_type, one_bit_max, one_bit_max);
3042 4 : int_range<2> t;
3043 4 : t = min;
3044 4 : t.invert ();
3045 4 : ASSERT_TRUE (t == max);
3046 4 : t = max;
3047 4 : t.invert ();
3048 4 : ASSERT_TRUE (t == min);
3049 4 : }
3050 :
3051 : // Test that NOT(255) is [0..254] in 8-bit land.
3052 4 : int_range<1> not_255 = range_uchar (255, 255, VR_ANTI_RANGE);
3053 4 : ASSERT_TRUE (not_255 == range_uchar (0, 254));
3054 :
3055 : // Test that NOT(0) is [1..255] in 8-bit land.
3056 4 : int_range<2> not_zero;
3057 4 : not_zero.set_nonzero (unsigned_char_type_node);
3058 4 : ASSERT_TRUE (not_zero == range_uchar (1, 255));
3059 :
3060 : // Check that [0,127][0x..ffffff80,0x..ffffff]
3061 : // => ~[128, 0x..ffffff7f].
3062 4 : r0 = range_uint128 (0, 127);
3063 4 : wide_int high = wi::minus_one (128);
3064 : // low = -1 - 127 => 0x..ffffff80.
3065 4 : wide_int low = wi::sub (high, wi::uhwi (127, 128));
3066 4 : r1 = int_range<1> (u128_type, low, high); // [0x..ffffff80, 0x..ffffffff]
3067 : // r0 = [0,127][0x..ffffff80,0x..fffffff].
3068 4 : r0.union_ (r1);
3069 : // r1 = [128, 0x..ffffff7f].
3070 12 : r1 = int_range<1> (u128_type,
3071 8 : wi::uhwi (128, 128),
3072 8 : wi::sub (wi::minus_one (128), wi::uhwi (128, 128)));
3073 4 : r0.invert ();
3074 4 : ASSERT_TRUE (r0 == r1);
3075 :
3076 4 : r0.set_varying (integer_type_node);
3077 4 : wide_int minint = r0.lower_bound ();
3078 4 : wide_int maxint = r0.upper_bound ();
3079 :
3080 4 : r0.set_varying (short_integer_type_node);
3081 :
3082 4 : r0.set_varying (unsigned_type_node);
3083 4 : wide_int maxuint = r0.upper_bound ();
3084 :
3085 : // Check that ~[0,5] => [6,MAX] for unsigned int.
3086 4 : r0 = range_uint (0, 5);
3087 4 : r0.invert ();
3088 4 : ASSERT_TRUE (r0 == int_range<1> (unsigned_type_node,
3089 : wi::uhwi (6, TYPE_PRECISION (unsigned_type_node)),
3090 : maxuint));
3091 :
3092 : // Check that ~[10,MAX] => [0,9] for unsigned int.
3093 8 : r0 = int_range<1> (unsigned_type_node,
3094 4 : wi::uhwi (10, TYPE_PRECISION (unsigned_type_node)),
3095 8 : maxuint);
3096 4 : r0.invert ();
3097 4 : ASSERT_TRUE (r0 == range_uint (0, 9));
3098 :
3099 : // Check that ~[0,5] => [6,MAX] for unsigned 128-bit numbers.
3100 4 : r0 = range_uint128 (0, 5, VR_ANTI_RANGE);
3101 4 : r1 = int_range<1> (u128_type, wi::uhwi (6, 128), wi::minus_one (128));
3102 4 : ASSERT_TRUE (r0 == r1);
3103 :
3104 : // Check that [~5] is really [-MIN,4][6,MAX].
3105 4 : r0 = range_int (5, 5, VR_ANTI_RANGE);
3106 4 : r1 = int_range<1> (integer_type_node, minint, INT (4));
3107 4 : r1.union_ (int_range<1> (integer_type_node, INT (6), maxint));
3108 4 : ASSERT_FALSE (r1.undefined_p ());
3109 4 : ASSERT_TRUE (r0 == r1);
3110 :
3111 4 : r1 = range_int (5, 5);
3112 4 : int_range<2> r2 (r1);
3113 4 : ASSERT_TRUE (r1 == r2);
3114 :
3115 4 : r1 = range_int (5, 10);
3116 :
3117 4 : r1 = range_int (5, 10);
3118 4 : ASSERT_TRUE (r1.contains_p (INT (7)));
3119 :
3120 4 : r1 = range_char (0, 20);
3121 4 : ASSERT_TRUE (r1.contains_p (SCHAR(15)));
3122 4 : ASSERT_FALSE (r1.contains_p (SCHAR(300)));
3123 :
3124 : // NOT([10,20]) ==> [-MIN,9][21,MAX].
3125 4 : r0 = r1 = range_int (10, 20);
3126 4 : r2 = int_range<1> (integer_type_node, minint, INT(9));
3127 4 : r2.union_ (int_range<1> (integer_type_node, INT(21), maxint));
3128 4 : ASSERT_FALSE (r2.undefined_p ());
3129 4 : r1.invert ();
3130 4 : ASSERT_TRUE (r1 == r2);
3131 : // Test that NOT(NOT(x)) == x.
3132 4 : r2.invert ();
3133 4 : ASSERT_TRUE (r0 == r2);
3134 :
3135 : // Test that booleans and their inverse work as expected.
3136 4 : r0.set_zero (boolean_type_node);
3137 4 : ASSERT_TRUE (r0 == range_false ());
3138 4 : r0.invert ();
3139 4 : ASSERT_TRUE (r0 == range_true ());
3140 :
3141 : // Make sure NULL and non-NULL of pointer types work, and that
3142 : // inverses of them are consistent.
3143 4 : tree voidp = build_pointer_type (void_type_node);
3144 4 : prange p0;
3145 4 : p0.set_zero (voidp);
3146 4 : prange p1 = p0;
3147 4 : p0.invert ();
3148 4 : p0.invert ();
3149 4 : ASSERT_TRUE (p0 == p1);
3150 :
3151 : // The intersection of:
3152 : // [0, +INF] MASK 0xff..00 VALUE 0xf8
3153 : // [0, +INF] MASK 0xff..00 VALUE 0x00
3154 : // is [0, +INF] MASK 0xff..ff VALUE 0x00, which is VARYING.
3155 : // Test that we normalized to VARYING.
3156 4 : unsigned prec = TYPE_PRECISION (voidp);
3157 4 : p0.set_varying (voidp);
3158 4 : wide_int mask = wi::mask (8, true, prec);
3159 4 : wide_int value = wi::uhwi (0xf8, prec);
3160 4 : irange_bitmask bm (wi::uhwi (0xf8, prec), mask);
3161 4 : p0.update_bitmask (bm);
3162 4 : p1.set_varying (voidp);
3163 4 : bm = irange_bitmask (wi::zero (prec), mask);
3164 4 : p1.update_bitmask (bm);
3165 4 : p0.intersect (p1);
3166 :
3167 : // [10,20] U [15, 30] => [10, 30].
3168 4 : r0 = range_int (10, 20);
3169 4 : r1 = range_int (15, 30);
3170 4 : r0.union_ (r1);
3171 4 : ASSERT_TRUE (r0 == range_int (10, 30));
3172 :
3173 : // [15,40] U [] => [15,40].
3174 4 : r0 = range_int (15, 40);
3175 4 : r1.set_undefined ();
3176 4 : r0.union_ (r1);
3177 4 : ASSERT_TRUE (r0 == range_int (15, 40));
3178 :
3179 : // [10,20] U [10,10] => [10,20].
3180 4 : r0 = range_int (10, 20);
3181 4 : r1 = range_int (10, 10);
3182 4 : r0.union_ (r1);
3183 4 : ASSERT_TRUE (r0 == range_int (10, 20));
3184 :
3185 : // [10,20] U [9,9] => [9,20].
3186 4 : r0 = range_int (10, 20);
3187 4 : r1 = range_int (9, 9);
3188 4 : r0.union_ (r1);
3189 4 : ASSERT_TRUE (r0 == range_int (9, 20));
3190 :
3191 : // [10,20] ^ [15,30] => [15,20].
3192 4 : r0 = range_int (10, 20);
3193 4 : r1 = range_int (15, 30);
3194 4 : r0.intersect (r1);
3195 4 : ASSERT_TRUE (r0 == range_int (15, 20));
3196 :
3197 : // Test the internal sanity of wide_int's wrt HWIs.
3198 4 : ASSERT_TRUE (wi::max_value (TYPE_PRECISION (boolean_type_node),
3199 : TYPE_SIGN (boolean_type_node))
3200 : == wi::uhwi (1, TYPE_PRECISION (boolean_type_node)));
3201 :
3202 : // Test zero_p().
3203 4 : r0 = range_int (0, 0);
3204 4 : ASSERT_TRUE (r0.zero_p ());
3205 :
3206 : // Test nonzero_p().
3207 4 : r0 = range_int (0, 0);
3208 4 : r0.invert ();
3209 4 : ASSERT_TRUE (r0.nonzero_p ());
3210 :
3211 : // r0 = ~[1,1]
3212 4 : r0 = range_int (1, 1, VR_ANTI_RANGE);
3213 : // r1 = ~[3,3]
3214 4 : r1 = range_int (3, 3, VR_ANTI_RANGE);
3215 :
3216 : // vv = [0,0][2,2][4, MAX]
3217 4 : int_range<3> vv = r0;
3218 4 : vv.intersect (r1);
3219 :
3220 4 : ASSERT_TRUE (vv.contains_p (UINT (2)));
3221 4 : ASSERT_TRUE (vv.num_pairs () == 3);
3222 :
3223 4 : r0 = range_int (1, 1);
3224 : // And union it with [0,0][2,2][4,MAX] multi range
3225 4 : r0.union_ (vv);
3226 : // The result should be [0,2][4,MAX], or ~[3,3] but it must contain 2
3227 4 : ASSERT_TRUE (r0.contains_p (INT (2)));
3228 4 : }
3229 :
3230 : static void
3231 4 : range_tests_nonzero_bits ()
3232 : {
3233 4 : int_range<8> r0, r1;
3234 :
3235 : // Adding nonzero bits to a varying drops the varying.
3236 4 : r0.set_varying (integer_type_node);
3237 4 : r0.set_nonzero_bits (INT (255));
3238 4 : ASSERT_TRUE (!r0.varying_p ());
3239 :
3240 : // Test contains_p with nonzero bits.
3241 4 : r0.set_zero (integer_type_node);
3242 4 : ASSERT_TRUE (r0.contains_p (INT (0)));
3243 4 : ASSERT_FALSE (r0.contains_p (INT (1)));
3244 4 : r0.set_nonzero_bits (INT (0xfe));
3245 4 : ASSERT_FALSE (r0.contains_p (INT (0x100)));
3246 4 : ASSERT_FALSE (r0.contains_p (INT (0x3)));
3247 :
3248 : // Union of nonzero bits.
3249 4 : r0.set_varying (integer_type_node);
3250 4 : r0.set_nonzero_bits (INT (0xf0));
3251 4 : r1.set_varying (integer_type_node);
3252 4 : r1.set_nonzero_bits (INT (0xf));
3253 4 : r0.union_ (r1);
3254 4 : ASSERT_TRUE (r0.get_nonzero_bits () == 0xff);
3255 :
3256 : // Intersect of nonzero bits.
3257 4 : r0 = range_int (0, 255);
3258 4 : r0.set_nonzero_bits (INT (0xfe));
3259 4 : r1.set_varying (integer_type_node);
3260 4 : r1.set_nonzero_bits (INT (0xf0));
3261 4 : r0.intersect (r1);
3262 4 : ASSERT_TRUE (r0.get_nonzero_bits () == 0xf0);
3263 :
3264 : // Intersect where the mask of nonzero bits is implicit from the range.
3265 4 : r0.set_varying (integer_type_node);
3266 4 : r1 = range_int (0, 255);
3267 4 : r0.intersect (r1);
3268 4 : ASSERT_TRUE (r0.get_nonzero_bits () == 0xff);
3269 :
3270 : // Test that setting a nonzero bit of 1 does not pessimize the range.
3271 4 : r0.set_zero (integer_type_node);
3272 4 : r0.set_nonzero_bits (INT (1));
3273 4 : ASSERT_TRUE (r0.zero_p ());
3274 :
3275 : // Now test that range bounds are snapped to match bitmask alignments.
3276 4 : test_irange_snap_bounds ();
3277 4 : }
3278 :
3279 : // Build an frange from string endpoints.
3280 :
3281 : static inline frange
3282 492 : frange_float (const char *lb, const char *ub, tree type = float_type_node)
3283 : {
3284 492 : REAL_VALUE_TYPE min, max;
3285 492 : gcc_assert (real_from_string (&min, lb) == 0);
3286 492 : gcc_assert (real_from_string (&max, ub) == 0);
3287 492 : return frange (type, min, max);
3288 : }
3289 :
3290 : static void
3291 4 : range_tests_nan ()
3292 : {
3293 4 : frange r0, r1;
3294 4 : REAL_VALUE_TYPE q, r;
3295 4 : bool signbit;
3296 :
3297 : // Equal ranges but with differing NAN bits are not equal.
3298 4 : if (HONOR_NANS (float_type_node))
3299 : {
3300 4 : r1 = frange_float ("10", "12");
3301 4 : r0 = r1;
3302 4 : ASSERT_EQ (r0, r1);
3303 4 : r0.clear_nan ();
3304 4 : ASSERT_NE (r0, r1);
3305 4 : r0.update_nan ();
3306 4 : ASSERT_EQ (r0, r1);
3307 :
3308 : // [10, 20] NAN ^ [30, 40] NAN = NAN.
3309 4 : r0 = frange_float ("10", "20");
3310 4 : r1 = frange_float ("30", "40");
3311 4 : r0.intersect (r1);
3312 4 : ASSERT_TRUE (r0.known_isnan ());
3313 :
3314 : // [3,5] U [5,10] NAN = ... NAN
3315 4 : r0 = frange_float ("3", "5");
3316 4 : r0.clear_nan ();
3317 4 : r1 = frange_float ("5", "10");
3318 4 : r0.union_ (r1);
3319 8 : ASSERT_TRUE (r0.maybe_isnan ());
3320 : }
3321 :
3322 : // [5,6] U NAN = [5,6] NAN.
3323 4 : r0 = frange_float ("5", "6");
3324 4 : r0.clear_nan ();
3325 4 : r1.set_nan (float_type_node);
3326 4 : r0.union_ (r1);
3327 4 : real_from_string (&q, "5");
3328 4 : real_from_string (&r, "6");
3329 4 : ASSERT_TRUE (real_identical (&q, &r0.lower_bound ()));
3330 4 : ASSERT_TRUE (real_identical (&r, &r0.upper_bound ()));
3331 8 : ASSERT_TRUE (r0.maybe_isnan ());
3332 :
3333 : // NAN U NAN = NAN
3334 4 : r0.set_nan (float_type_node);
3335 4 : r1.set_nan (float_type_node);
3336 4 : r0.union_ (r1);
3337 4 : ASSERT_TRUE (r0.known_isnan ());
3338 :
3339 : // [INF, INF] NAN ^ NAN = NAN
3340 4 : r0.set_nan (float_type_node);
3341 4 : r1 = frange_float ("+Inf", "+Inf");
3342 4 : if (!HONOR_NANS (float_type_node))
3343 0 : r1.update_nan ();
3344 4 : r0.intersect (r1);
3345 4 : ASSERT_TRUE (r0.known_isnan ());
3346 :
3347 : // NAN ^ NAN = NAN
3348 4 : r0.set_nan (float_type_node);
3349 4 : r1.set_nan (float_type_node);
3350 4 : r0.intersect (r1);
3351 4 : ASSERT_TRUE (r0.known_isnan ());
3352 :
3353 : // +NAN ^ -NAN = UNDEFINED
3354 4 : r0.set_nan (float_type_node, false);
3355 4 : r1.set_nan (float_type_node, true);
3356 4 : r0.intersect (r1);
3357 4 : ASSERT_TRUE (r0.undefined_p ());
3358 :
3359 : // VARYING ^ NAN = NAN.
3360 4 : r0.set_nan (float_type_node);
3361 4 : r1.set_varying (float_type_node);
3362 4 : r0.intersect (r1);
3363 4 : ASSERT_TRUE (r0.known_isnan ());
3364 :
3365 : // [3,4] ^ NAN = UNDEFINED.
3366 4 : r0 = frange_float ("3", "4");
3367 4 : r0.clear_nan ();
3368 4 : r1.set_nan (float_type_node);
3369 4 : r0.intersect (r1);
3370 4 : ASSERT_TRUE (r0.undefined_p ());
3371 :
3372 : // [-3, 5] ^ NAN = UNDEFINED
3373 4 : r0 = frange_float ("-3", "5");
3374 4 : r0.clear_nan ();
3375 4 : r1.set_nan (float_type_node);
3376 4 : r0.intersect (r1);
3377 4 : ASSERT_TRUE (r0.undefined_p ());
3378 :
3379 : // Setting the NAN bit to yes does not make us a known NAN.
3380 4 : r0.set_varying (float_type_node);
3381 4 : r0.update_nan ();
3382 4 : ASSERT_FALSE (r0.known_isnan ());
3383 :
3384 : // NAN is in a VARYING.
3385 4 : r0.set_varying (float_type_node);
3386 4 : real_nan (&r, "", 1, TYPE_MODE (float_type_node));
3387 4 : REAL_VALUE_TYPE nan = r;
3388 4 : ASSERT_TRUE (r0.contains_p (nan));
3389 :
3390 : // -NAN is in a VARYING.
3391 4 : r0.set_varying (float_type_node);
3392 4 : q = real_value_negate (&r);
3393 4 : REAL_VALUE_TYPE neg_nan = q;
3394 4 : ASSERT_TRUE (r0.contains_p (neg_nan));
3395 :
3396 : // Clearing the NAN on a [] NAN is the empty set.
3397 4 : r0.set_nan (float_type_node);
3398 4 : r0.clear_nan ();
3399 4 : ASSERT_TRUE (r0.undefined_p ());
3400 :
3401 : // [10,20] NAN ^ [21,25] NAN = [NAN]
3402 4 : r0 = frange_float ("10", "20");
3403 4 : r0.update_nan ();
3404 4 : r1 = frange_float ("21", "25");
3405 4 : r1.update_nan ();
3406 4 : r0.intersect (r1);
3407 4 : ASSERT_TRUE (r0.known_isnan ());
3408 :
3409 : // NAN U [5,6] should be [5,6] +-NAN.
3410 4 : r0.set_nan (float_type_node);
3411 4 : r1 = frange_float ("5", "6");
3412 4 : r1.clear_nan ();
3413 4 : r0.union_ (r1);
3414 4 : real_from_string (&q, "5");
3415 4 : real_from_string (&r, "6");
3416 4 : ASSERT_TRUE (real_identical (&q, &r0.lower_bound ()));
3417 4 : ASSERT_TRUE (real_identical (&r, &r0.upper_bound ()));
3418 4 : ASSERT_TRUE (!r0.signbit_p (signbit));
3419 8 : ASSERT_TRUE (r0.maybe_isnan ());
3420 :
3421 : // NAN U NAN shouldn't change anything.
3422 4 : r0.set_nan (float_type_node);
3423 4 : r1.set_nan (float_type_node);
3424 4 : ASSERT_FALSE (r0.union_ (r1));
3425 :
3426 : // [3,5] NAN U NAN shouldn't change anything.
3427 4 : r0 = frange_float ("3", "5");
3428 4 : r1.set_nan (float_type_node);
3429 4 : ASSERT_FALSE (r0.union_ (r1));
3430 :
3431 : // [3,5] U NAN *does* trigger a change.
3432 4 : r0 = frange_float ("3", "5");
3433 4 : r0.clear_nan ();
3434 4 : r1.set_nan (float_type_node);
3435 4 : ASSERT_TRUE (r0.union_ (r1));
3436 4 : }
3437 :
3438 : static void
3439 8 : range_tests_signed_zeros ()
3440 : {
3441 8 : REAL_VALUE_TYPE zero = dconst0;
3442 8 : REAL_VALUE_TYPE neg_zero = zero;
3443 8 : neg_zero.sign = 1;
3444 8 : frange r0, r1;
3445 8 : bool signbit;
3446 :
3447 : // [0,0] contains [0,0] but not [-0,-0] and vice versa.
3448 8 : r0 = frange_float ("0.0", "0.0");
3449 8 : r1 = frange_float ("-0.0", "-0.0");
3450 8 : ASSERT_TRUE (r0.contains_p (zero));
3451 8 : ASSERT_TRUE (!r0.contains_p (neg_zero));
3452 8 : ASSERT_TRUE (r1.contains_p (neg_zero));
3453 8 : ASSERT_TRUE (!r1.contains_p (zero));
3454 :
3455 : // Test contains_p() when we know the sign of the zero.
3456 8 : r0 = frange_float ("0.0", "0.0");
3457 8 : ASSERT_TRUE (r0.contains_p (zero));
3458 8 : ASSERT_FALSE (r0.contains_p (neg_zero));
3459 8 : r0 = frange_float ("-0.0", "-0.0");
3460 8 : ASSERT_TRUE (r0.contains_p (neg_zero));
3461 8 : ASSERT_FALSE (r0.contains_p (zero));
3462 :
3463 8 : r0 = frange_float ("-0.0", "0.0");
3464 8 : ASSERT_TRUE (r0.contains_p (neg_zero));
3465 8 : ASSERT_TRUE (r0.contains_p (zero));
3466 :
3467 8 : r0 = frange_float ("-3", "5");
3468 8 : ASSERT_TRUE (r0.contains_p (neg_zero));
3469 8 : ASSERT_TRUE (r0.contains_p (zero));
3470 :
3471 : // The intersection of zeros that differ in sign is a NAN (or
3472 : // undefined if not honoring NANs).
3473 8 : r0 = frange_float ("-0.0", "-0.0");
3474 8 : r1 = frange_float ("0.0", "0.0");
3475 8 : r0.intersect (r1);
3476 8 : if (HONOR_NANS (float_type_node))
3477 4 : ASSERT_TRUE (r0.known_isnan ());
3478 : else
3479 4 : ASSERT_TRUE (r0.undefined_p ());
3480 :
3481 : // The union of zeros that differ in sign is a zero with unknown sign.
3482 8 : r0 = frange_float ("0.0", "0.0");
3483 8 : r1 = frange_float ("-0.0", "-0.0");
3484 8 : r0.union_ (r1);
3485 8 : ASSERT_TRUE (r0.zero_p () && !r0.signbit_p (signbit));
3486 :
3487 : // [-0, +0] has an unknown sign.
3488 8 : r0 = frange_float ("-0.0", "0.0");
3489 8 : ASSERT_TRUE (r0.zero_p () && !r0.signbit_p (signbit));
3490 :
3491 : // [-0, +0] ^ [0, 0] is [0, 0]
3492 8 : r0 = frange_float ("-0.0", "0.0");
3493 8 : r1 = frange_float ("0.0", "0.0");
3494 8 : r0.intersect (r1);
3495 8 : ASSERT_TRUE (r0.zero_p ());
3496 :
3497 8 : r0 = frange_float ("+0", "5");
3498 8 : r0.clear_nan ();
3499 8 : ASSERT_TRUE (r0.signbit_p (signbit) && !signbit);
3500 :
3501 8 : r0 = frange_float ("-0", "5");
3502 8 : r0.clear_nan ();
3503 8 : ASSERT_TRUE (!r0.signbit_p (signbit));
3504 :
3505 8 : r0 = frange_float ("-0", "10");
3506 8 : r1 = frange_float ("0", "5");
3507 8 : r0.intersect (r1);
3508 8 : ASSERT_TRUE (real_iszero (&r0.lower_bound (), false));
3509 :
3510 8 : r0 = frange_float ("-0", "5");
3511 8 : r1 = frange_float ("0", "5");
3512 8 : r0.union_ (r1);
3513 8 : ASSERT_TRUE (real_iszero (&r0.lower_bound (), true));
3514 :
3515 8 : r0 = frange_float ("-5", "-0");
3516 8 : r0.update_nan ();
3517 8 : r1 = frange_float ("0", "0");
3518 8 : r1.update_nan ();
3519 8 : r0.intersect (r1);
3520 8 : if (HONOR_NANS (float_type_node))
3521 4 : ASSERT_TRUE (r0.known_isnan ());
3522 : else
3523 4 : ASSERT_TRUE (r0.undefined_p ());
3524 :
3525 8 : r0.set_nonnegative (float_type_node);
3526 8 : if (HONOR_NANS (float_type_node))
3527 8 : ASSERT_TRUE (r0.maybe_isnan ());
3528 :
3529 : // Numbers containing zero should have an unknown SIGNBIT.
3530 8 : r0 = frange_float ("0", "10");
3531 8 : r0.clear_nan ();
3532 8 : ASSERT_TRUE (r0.signbit_p (signbit) && !signbit);
3533 8 : }
3534 :
3535 : static void
3536 8 : range_tests_signbit ()
3537 : {
3538 8 : frange r0, r1;
3539 8 : bool signbit;
3540 :
3541 : // Negative numbers should have the SIGNBIT set.
3542 8 : r0 = frange_float ("-5", "-1");
3543 8 : r0.clear_nan ();
3544 8 : ASSERT_TRUE (r0.signbit_p (signbit) && signbit);
3545 : // Positive numbers should have the SIGNBIT clear.
3546 8 : r0 = frange_float ("1", "10");
3547 8 : r0.clear_nan ();
3548 8 : ASSERT_TRUE (r0.signbit_p (signbit) && !signbit);
3549 : // Numbers spanning both positive and negative should have an
3550 : // unknown SIGNBIT.
3551 8 : r0 = frange_float ("-10", "10");
3552 8 : r0.clear_nan ();
3553 8 : ASSERT_TRUE (!r0.signbit_p (signbit));
3554 8 : r0.set_varying (float_type_node);
3555 8 : ASSERT_TRUE (!r0.signbit_p (signbit));
3556 8 : }
3557 :
3558 : static void
3559 8 : range_tests_floats ()
3560 : {
3561 8 : frange r0, r1;
3562 :
3563 8 : if (HONOR_NANS (float_type_node))
3564 4 : range_tests_nan ();
3565 8 : range_tests_signbit ();
3566 :
3567 8 : if (HONOR_SIGNED_ZEROS (float_type_node))
3568 8 : range_tests_signed_zeros ();
3569 :
3570 : // A range of [-INF,+INF] is actually VARYING if no other properties
3571 : // are set.
3572 8 : r0 = frange_float ("-Inf", "+Inf");
3573 8 : ASSERT_TRUE (r0.varying_p ());
3574 : // ...unless it has some special property...
3575 8 : if (HONOR_NANS (r0.type ()))
3576 : {
3577 4 : r0.clear_nan ();
3578 4 : ASSERT_FALSE (r0.varying_p ());
3579 : }
3580 :
3581 : // For most architectures, where float and double are different
3582 : // sizes, having the same endpoints does not necessarily mean the
3583 : // ranges are equal.
3584 8 : if (!types_compatible_p (float_type_node, double_type_node))
3585 : {
3586 8 : r0 = frange_float ("3.0", "3.0", float_type_node);
3587 8 : r1 = frange_float ("3.0", "3.0", double_type_node);
3588 8 : ASSERT_NE (r0, r1);
3589 : }
3590 :
3591 : // [3,5] U [10,12] = [3,12].
3592 8 : r0 = frange_float ("3", "5");
3593 8 : r1 = frange_float ("10", "12");
3594 8 : r0.union_ (r1);
3595 8 : ASSERT_EQ (r0, frange_float ("3", "12"));
3596 :
3597 : // [5,10] U [4,8] = [4,10]
3598 8 : r0 = frange_float ("5", "10");
3599 8 : r1 = frange_float ("4", "8");
3600 8 : r0.union_ (r1);
3601 8 : ASSERT_EQ (r0, frange_float ("4", "10"));
3602 :
3603 : // [3,5] U [4,10] = [3,10]
3604 8 : r0 = frange_float ("3", "5");
3605 8 : r1 = frange_float ("4", "10");
3606 8 : r0.union_ (r1);
3607 8 : ASSERT_EQ (r0, frange_float ("3", "10"));
3608 :
3609 : // [4,10] U [5,11] = [4,11]
3610 8 : r0 = frange_float ("4", "10");
3611 8 : r1 = frange_float ("5", "11");
3612 8 : r0.union_ (r1);
3613 8 : ASSERT_EQ (r0, frange_float ("4", "11"));
3614 :
3615 : // [3,12] ^ [10,12] = [10,12].
3616 8 : r0 = frange_float ("3", "12");
3617 8 : r1 = frange_float ("10", "12");
3618 8 : r0.intersect (r1);
3619 8 : ASSERT_EQ (r0, frange_float ("10", "12"));
3620 :
3621 : // [10,12] ^ [11,11] = [11,11]
3622 8 : r0 = frange_float ("10", "12");
3623 8 : r1 = frange_float ("11", "11");
3624 8 : r0.intersect (r1);
3625 8 : ASSERT_EQ (r0, frange_float ("11", "11"));
3626 :
3627 : // [10,20] ^ [5,15] = [10,15]
3628 8 : r0 = frange_float ("10", "20");
3629 8 : r1 = frange_float ("5", "15");
3630 8 : r0.intersect (r1);
3631 8 : ASSERT_EQ (r0, frange_float ("10", "15"));
3632 :
3633 : // [10,20] ^ [15,25] = [15,20]
3634 8 : r0 = frange_float ("10", "20");
3635 8 : r1 = frange_float ("15", "25");
3636 8 : r0.intersect (r1);
3637 8 : ASSERT_EQ (r0, frange_float ("15", "20"));
3638 :
3639 : // [10,20] ^ [21,25] = []
3640 8 : r0 = frange_float ("10", "20");
3641 8 : r0.clear_nan ();
3642 8 : r1 = frange_float ("21", "25");
3643 8 : r1.clear_nan ();
3644 8 : r0.intersect (r1);
3645 8 : ASSERT_TRUE (r0.undefined_p ());
3646 :
3647 8 : if (HONOR_INFINITIES (float_type_node))
3648 : {
3649 : // Make sure [-Inf, -Inf] doesn't get normalized.
3650 4 : r0 = frange_float ("-Inf", "-Inf");
3651 4 : ASSERT_TRUE (real_isinf (&r0.lower_bound (), true));
3652 4 : ASSERT_TRUE (real_isinf (&r0.upper_bound (), true));
3653 : }
3654 :
3655 : // Test that reading back a global range yields the same result as
3656 : // what we wrote into it.
3657 8 : tree ssa = make_temp_ssa_name (float_type_node, NULL, "blah");
3658 8 : r0.set_varying (float_type_node);
3659 8 : r0.clear_nan ();
3660 8 : set_range_info (ssa, r0);
3661 8 : get_global_range_query ()->range_of_expr (r1, ssa);
3662 8 : ASSERT_EQ (r0, r1);
3663 8 : }
3664 :
3665 : // Run floating range tests for various combinations of NAN and INF
3666 : // support.
3667 :
3668 : static void
3669 4 : range_tests_floats_various ()
3670 : {
3671 4 : int save_finite_math_only = flag_finite_math_only;
3672 :
3673 : // Test -ffinite-math-only.
3674 4 : flag_finite_math_only = 1;
3675 4 : range_tests_floats ();
3676 : // Test -fno-finite-math-only.
3677 4 : flag_finite_math_only = 0;
3678 4 : range_tests_floats ();
3679 :
3680 4 : flag_finite_math_only = save_finite_math_only;
3681 4 : }
3682 :
3683 : void
3684 4 : range_tests ()
3685 : {
3686 4 : range_tests_irange3 ();
3687 4 : range_tests_int_range_max ();
3688 4 : range_tests_strict_enum ();
3689 4 : range_tests_nonzero_bits ();
3690 4 : range_tests_floats_various ();
3691 4 : range_tests_misc ();
3692 4 : }
3693 :
3694 : } // namespace selftest
3695 :
3696 : #endif // CHECKING_P
|
