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