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 "value-range-storage.h"
32 : #include "fold-const.h"
33 : #include "gimple-range.h"
34 : #include "tree-dfa.h"
35 : #include "tree-affine.h"
36 :
37 : // Return the bitmask inherent in a range : TYPE [MIN, MAX].
38 : // This used to be get_bitmask_from_range ().
39 :
40 1217419269 : irange_bitmask::irange_bitmask (tree type,
41 1217419269 : const wide_int &min, const wide_int &max)
42 : {
43 1217419269 : unsigned prec = TYPE_PRECISION (type);
44 : // All the bits of a singleton are known.
45 1217419269 : if (min == max)
46 : {
47 167405165 : m_mask = wi::zero (prec);
48 167405165 : m_value = min;
49 : }
50 : else
51 : {
52 1050014104 : wide_int xorv = min ^ max;
53 : // Mask will have leading zeros for all leading bits that are
54 : // common, both zeros and ones.
55 1050014104 : m_mask = wi::mask (prec - wi::clz (xorv), false, prec);
56 : // Now set value to those bits which are known, and zero the rest.
57 1050161718 : m_value = ~m_mask & min;
58 1050014104 : }
59 1217419269 : }
60 :
61 : // Return a range in R of TYPE for this bitmask which encompasses
62 : // a set of valid values which are allowable for this bitmask/value
63 : // combination. If false is returned, no range was set.
64 :
65 : bool
66 125674692 : irange_bitmask::range_from_mask (irange &r, tree type) const
67 : {
68 125674692 : if (unknown_p ())
69 : return false;
70 :
71 251191494 : gcc_checking_assert ((value () & mask ()) == 0);
72 125595100 : unsigned popcount = wi::popcount (mask ());
73 :
74 : // For 0, 1 or 2 bits set, create a range with only the allowed values.
75 125595100 : if (popcount <= 2)
76 : {
77 : // VALUE is always a valid range.
78 25313669 : r.set (type, value (), value ());
79 : // If there are bits in mask, (VALUE | MASK) is also valid.
80 25313626 : if (popcount >= 1)
81 11624086 : r.union_ (int_range<1> (type, value () | mask (), value () | mask ()));
82 : // If there are 2 bits set, add the other 2 possible values.
83 11624006 : if (popcount == 2)
84 : {
85 : // Extract the two 1-bit masks into lb and ub.
86 4827507 : wide_int lb = mask () & -mask (); // Lowest set bit.
87 4827507 : wide_int ub = mask () & (mask () - 1); // The other bit.
88 4827507 : r.union_ (int_range<1> (type, value () | lb, value () | lb));
89 4827507 : r.union_ (int_range<1> (type, value () | ub, value () | ub));
90 4827507 : }
91 : return true;
92 : }
93 :
94 : // Otherwise, calculate the valid range allowed by the bitmask.
95 100281474 : int prec = TYPE_PRECISION (type);
96 100282725 : wide_int ub = mask () | value ();
97 100281474 : wide_int sign_bit = wi::one (prec) << (prec - 1);
98 100281474 : wide_int sign_mask = mask () & sign_bit;
99 100281474 : wide_int sign_value = value () & sign_bit;
100 : // Create a lower and upper bound.
101 : // If unsigned, or the sign is known to be positive, create [lb, ub]
102 100281474 : if (TYPE_SIGN (type) == UNSIGNED || (sign_mask == 0 && sign_value == 0))
103 93239689 : r.set (type, value (), mask () | value ());
104 : // If the sign bit is KNOWN to be 1, we have a completely negative range.
105 7046613 : else if (sign_mask == 0 && sign_value != 0)
106 723442 : r.set (type, value (), value () | (mask () & ~sign_bit));
107 : else
108 : {
109 : // Otherwise there are 2 ranges, a negative and positive interval.
110 6323201 : wide_int neg_base = value () | sign_bit;
111 6323240 : wide_int pos_mask = mask () & ~sign_bit;
112 6323201 : r.set (type, neg_base , neg_base | pos_mask);
113 6323318 : r.union_ (int_range<1> (type, value (), value () | pos_mask));
114 6323240 : }
115 :
116 : // If the mask doesn't have a trailing zero, there is nothing else to filter.
117 100281474 : int z = wi::ctz (mask ());
118 100281474 : if (z == 0)
119 : return true;
120 :
121 : // Remove the [0, X] values which the trailing-zero mask rules out.
122 : // For example, if z == 4, the mask is 0xFFF0, and the lowest 4 bits
123 : // define the range [0, 15]. Only (value & low_mask) is allowed.
124 30235059 : ub = (wi::one (prec) << z) - 1; // Upper bound of range.
125 30234770 : int_range<4> mask_range (type, wi::zero (prec), ub);
126 : // Remove the valid value from the excluded range and form an anti-range.
127 30234770 : wide_int allow = value () & ub;
128 30234770 : mask_range.intersect (int_range<2> (type, allow, allow, VR_ANTI_RANGE));
129 30234770 : bool res = mask_range.invert ();
130 30234770 : gcc_checking_assert (res);
131 30234770 : r.intersect (mask_range);
132 :
133 30234770 : if (TYPE_SIGN (type) == SIGNED)
134 : {
135 : // For signed negative values, find the lowest value with trailing zeros.
136 : // This forms a range such as [-512, -1] for z=9.
137 11452439 : wide_int lb = -(wi::one (prec) << z);
138 11452439 : int_range<4> mask_range (type, lb, wi::minus_one (prec));
139 : // Remove the one allowed value from that set.
140 11452439 : wide_int allow = value () | lb;
141 11452439 : mask_range.intersect (int_range<2> (type, allow, allow, VR_ANTI_RANGE));
142 11452439 : res = mask_range.invert ();
143 11452439 : gcc_checking_assert (res);
144 11452439 : r.intersect (mask_range);
145 11452728 : }
146 30234770 : return true;
147 130519997 : }
148 :
149 :
150 : void
151 38477 : irange::accept (const vrange_visitor &v) const
152 : {
153 38477 : v.visit (*this);
154 38477 : }
155 :
156 : void
157 23510 : value_range::dump (FILE *out) const
158 : {
159 23510 : if (m_vrange)
160 23510 : m_vrange->dump (out);
161 : else
162 0 : fprintf (out, "NULL");
163 23510 : }
164 :
165 : void
166 0 : value_range::print (pretty_printer *pp) const
167 : {
168 0 : if (m_vrange)
169 : {
170 0 : vrange_printer vrange_pp (pp);
171 0 : m_vrange->accept (vrange_pp);
172 : }
173 : else
174 0 : pp_string (pp, "NULL");
175 0 : }
176 :
177 : DEBUG_FUNCTION void
178 0 : debug (const value_range &r)
179 : {
180 0 : r.dump (stderr);
181 0 : fprintf (stderr, "\n");
182 0 : }
183 :
184 : DEBUG_FUNCTION void
185 0 : debug (const irange_bitmask &bm)
186 : {
187 0 : bm.dump (stderr);
188 0 : fprintf (stderr, "\n");
189 0 : }
190 :
191 : // Definitions for unsupported_range.
192 :
193 : void
194 577 : unsupported_range::accept (const vrange_visitor &v) const
195 : {
196 577 : v.visit (*this);
197 577 : }
198 :
199 : void
200 0 : vrange::update_bitmask (const class irange_bitmask &)
201 : {
202 0 : }
203 :
204 : irange_bitmask
205 0 : vrange::get_bitmask () const
206 : {
207 : // Return all unknown bits for the given precision.
208 0 : return irange_bitmask (TYPE_PRECISION (type ()));
209 : }
210 :
211 : bool
212 0 : unsupported_range::contains_p (tree) const
213 : {
214 0 : return varying_p ();
215 : }
216 :
217 : bool
218 1308471 : unsupported_range::singleton_p (tree *) const
219 : {
220 1308471 : return false;
221 : }
222 :
223 : void
224 0 : unsupported_range::set (tree min, tree, value_range_kind)
225 : {
226 0 : set_varying (TREE_TYPE (min));
227 0 : }
228 :
229 : tree
230 0 : unsupported_range::type () const
231 : {
232 0 : return void_type_node;
233 : }
234 :
235 : bool
236 20926250 : unsupported_range::supports_type_p (const_tree) const
237 : {
238 20926250 : return false;
239 : }
240 :
241 : void
242 114832959 : unsupported_range::set_undefined ()
243 : {
244 114832959 : m_kind = VR_UNDEFINED;
245 114832959 : }
246 :
247 : void
248 3619661 : unsupported_range::set_varying (tree)
249 : {
250 3619661 : m_kind = VR_VARYING;
251 3619661 : }
252 :
253 : bool
254 0 : unsupported_range::union_ (const vrange &v)
255 : {
256 0 : const unsupported_range &r = as_a <unsupported_range> (v);
257 :
258 0 : if (r.undefined_p () || varying_p ())
259 : return false;
260 0 : if (undefined_p () || r.varying_p ())
261 : {
262 0 : operator= (r);
263 0 : return true;
264 : }
265 0 : gcc_unreachable ();
266 : return false;
267 : }
268 :
269 : bool
270 0 : unsupported_range::intersect (const vrange &v)
271 : {
272 0 : const unsupported_range &r = as_a <unsupported_range> (v);
273 :
274 0 : if (undefined_p () || r.varying_p ())
275 : return false;
276 0 : if (r.undefined_p ())
277 : {
278 0 : set_undefined ();
279 0 : return true;
280 : }
281 0 : if (varying_p ())
282 : {
283 0 : operator= (r);
284 0 : return true;
285 : }
286 0 : gcc_unreachable ();
287 : return false;
288 : }
289 :
290 : bool
291 0 : unsupported_range::zero_p () const
292 : {
293 0 : return false;
294 : }
295 :
296 : bool
297 0 : unsupported_range::contains_zero_p () const
298 : {
299 0 : return varying_p ();
300 : }
301 :
302 : void
303 0 : unsupported_range::set_nonzero (tree type)
304 : {
305 0 : set_varying (type);
306 0 : }
307 :
308 : void
309 0 : unsupported_range::set_zero (tree type)
310 : {
311 0 : set_varying (type);
312 0 : }
313 :
314 : void
315 0 : unsupported_range::set_nonnegative (tree type)
316 : {
317 0 : set_varying (type);
318 0 : }
319 :
320 : bool
321 0 : unsupported_range::fits_p (const vrange &) const
322 : {
323 0 : return true;
324 : }
325 :
326 : unsupported_range &
327 652680 : unsupported_range::operator= (const unsupported_range &r)
328 : {
329 652680 : if (r.undefined_p ())
330 652680 : set_undefined ();
331 0 : else if (r.varying_p ())
332 0 : set_varying (void_type_node);
333 : else
334 0 : gcc_unreachable ();
335 652680 : return *this;
336 : }
337 :
338 : tree
339 0 : unsupported_range::lbound () const
340 : {
341 0 : return NULL;
342 : }
343 :
344 : tree
345 0 : unsupported_range::ubound () const
346 : {
347 0 : return NULL;
348 : }
349 :
350 : // Assignment operator for generic ranges. Copying incompatible types
351 : // is not allowed.
352 :
353 : vrange &
354 10568190 : vrange::operator= (const vrange &src)
355 : {
356 10568190 : if (is_a <irange> (src))
357 9444635 : as_a <irange> (*this) = as_a <irange> (src);
358 1123555 : else if (is_a <prange> (src))
359 830723 : as_a <prange> (*this) = as_a <prange> (src);
360 292832 : else if (is_a <frange> (src))
361 292832 : as_a <frange> (*this) = as_a <frange> (src);
362 : else
363 : {
364 0 : gcc_checking_assert (is_a <unsupported_range> (src));
365 0 : m_kind = src.m_kind;
366 : }
367 10568190 : return *this;
368 : }
369 :
370 : // Equality operator for generic ranges.
371 :
372 : bool
373 39667745 : vrange::operator== (const vrange &src) const
374 : {
375 39667745 : if (is_a <irange> (src))
376 34462312 : return as_a <irange> (*this) == as_a <irange> (src);
377 5205433 : if (is_a <prange> (src))
378 5150782 : return as_a <prange> (*this) == as_a <prange> (src);
379 54651 : if (is_a <frange> (src))
380 54651 : return as_a <frange> (*this) == as_a <frange> (src);
381 0 : gcc_unreachable ();
382 : }
383 :
384 : // Wrapper for vrange_printer to dump a range to a file.
385 :
386 : void
387 37898 : vrange::dump (FILE *file) const
388 : {
389 37898 : pretty_printer pp;
390 37898 : pp_needs_newline (&pp) = true;
391 37898 : pp.set_output_stream (file);
392 37898 : vrange_printer vrange_pp (&pp);
393 37898 : this->accept (vrange_pp);
394 37898 : pp_flush (&pp);
395 37898 : }
396 :
397 : void
398 0 : irange_bitmask::dump (FILE *file) const
399 : {
400 0 : char buf[WIDE_INT_PRINT_BUFFER_SIZE], *p;
401 0 : pretty_printer pp;
402 :
403 0 : pp_needs_newline (&pp) = true;
404 0 : pp.set_output_stream (file);
405 0 : pp_string (&pp, "MASK ");
406 0 : unsigned len_mask, len_val;
407 0 : if (print_hex_buf_size (m_mask, &len_mask)
408 0 : | print_hex_buf_size (m_value, &len_val))
409 0 : p = XALLOCAVEC (char, MAX (len_mask, len_val));
410 : else
411 : p = buf;
412 0 : print_hex (m_mask, p);
413 0 : pp_string (&pp, p);
414 0 : pp_string (&pp, " VALUE ");
415 0 : print_hex (m_value, p);
416 0 : pp_string (&pp, p);
417 0 : pp_flush (&pp);
418 0 : }
419 :
420 : namespace inchash
421 : {
422 :
423 : void
424 32050522 : add_vrange (const vrange &v, inchash::hash &hstate,
425 : unsigned int)
426 : {
427 32050522 : if (v.undefined_p ())
428 : {
429 0 : hstate.add_int (VR_UNDEFINED);
430 0 : return;
431 : }
432 : // Types are ignored throughout to inhibit two ranges being equal
433 : // but having different hash values. This can happen when two
434 : // ranges are equal and their types are different (but
435 : // types_compatible_p is true).
436 32050522 : if (is_a <irange> (v))
437 : {
438 9754914 : const irange &r = as_a <irange> (v);
439 9754914 : if (r.varying_p ())
440 0 : hstate.add_int (VR_VARYING);
441 : else
442 9754914 : hstate.add_int (VR_RANGE);
443 20532443 : for (unsigned i = 0; i < r.num_pairs (); ++i)
444 : {
445 10777529 : hstate.add_wide_int (r.lower_bound (i));
446 10778116 : hstate.add_wide_int (r.upper_bound (i));
447 : }
448 9754914 : irange_bitmask bm = r.get_bitmask ();
449 9754914 : hstate.add_wide_int (bm.value ());
450 9754914 : hstate.add_wide_int (bm.mask ());
451 9754914 : return;
452 9754914 : }
453 22295608 : if (is_a <prange> (v))
454 : {
455 22219482 : const prange &r = as_a <prange> (v);
456 22219482 : if (r.varying_p ())
457 0 : hstate.add_int (VR_VARYING);
458 : else
459 : {
460 22219482 : hstate.add_int (VR_RANGE);
461 22219482 : hstate.add_wide_int (r.lower_bound ());
462 22219482 : hstate.add_wide_int (r.upper_bound ());
463 22219482 : irange_bitmask bm = r.get_bitmask ();
464 22219482 : hstate.add_wide_int (bm.value ());
465 22219482 : hstate.add_wide_int (bm.mask ());
466 22219482 : bool flag = false;
467 22219482 : tree tmp = r.pt_invariant ();
468 : if (tmp)
469 : flag = true;
470 : else
471 1551991 : tmp = r.pt_invariant_away ();
472 22219482 : hstate.add_ptr (tmp);
473 22219482 : hstate.add_flag (flag);
474 22219482 : }
475 : return;
476 : }
477 76126 : if (is_a <frange> (v))
478 : {
479 76126 : const frange &r = as_a <frange> (v);
480 76126 : if (r.known_isnan ())
481 284 : hstate.add_int (VR_NAN);
482 : else
483 : {
484 75842 : hstate.add_int (r.varying_p () ? VR_VARYING : VR_RANGE);
485 75842 : hstate.add_real_value (r.lower_bound ());
486 75842 : hstate.add_real_value (r.upper_bound ());
487 : }
488 76126 : nan_state nan = r.get_nan_state ();
489 76126 : hstate.add_int (nan.pos_p ());
490 76126 : hstate.add_int (nan.neg_p ());
491 76126 : return;
492 : }
493 0 : gcc_unreachable ();
494 : }
495 :
496 : } //namespace inchash
497 :
498 : bool
499 1781320 : irange::nonnegative_p () const
500 : {
501 1781320 : return wi::ge_p (lower_bound (), 0, TYPE_SIGN (type ()));
502 : }
503 :
504 : bool
505 1187107 : irange::nonpositive_p () const
506 : {
507 1187107 : return wi::le_p (upper_bound (), 0, TYPE_SIGN (type ()));
508 : }
509 :
510 : bool
511 694768338 : irange::supports_type_p (const_tree type) const
512 : {
513 694768338 : return supports_p (type);
514 : }
515 :
516 : // Return TRUE if R fits in THIS.
517 :
518 : bool
519 0 : irange::fits_p (const vrange &r) const
520 : {
521 0 : return m_max_ranges >= as_a <irange> (r).num_pairs ();
522 : }
523 :
524 : void
525 44144 : irange::set_nonnegative (tree type)
526 : {
527 44144 : set (type,
528 88288 : wi::zero (TYPE_PRECISION (type)),
529 44144 : wi::to_wide (TYPE_MAX_VALUE (type)));
530 44144 : }
531 :
532 :
533 : // Set the points to info for EXPR if possible. POINTS_TO_P is true if it
534 : // points to EXPR, and FALSE if it points away.
535 :
536 : void
537 15289085 : prange::set_pt (tree expr, bool points_to_p)
538 : {
539 15289085 : gcc_checking_assert (m_kind != VR_UNDEFINED);
540 15289085 : gcc_checking_assert (!expr || TREE_CODE (expr) != SSA_NAME);
541 :
542 15289085 : m_pt = NULL_TREE;
543 15289085 : m_points_to_p = false;
544 :
545 : // A zero range means no points-to info.
546 15289085 : if (zero_p ())
547 4311419 : return;
548 :
549 : // No points to initially may make this VARYING.
550 15289043 : if (varying_compatible_p ())
551 386641 : set_varying (type ());
552 : else
553 14902402 : m_kind = VR_RANGE;
554 :
555 15289043 : if (!expr)
556 : return;
557 :
558 15289043 : gcc_checking_assert (TREE_CODE (expr) == ADDR_EXPR);
559 :
560 : // Ensure only constants get through for now.
561 15289043 : if (!is_gimple_min_invariant (expr))
562 : return;
563 :
564 10977666 : aff_tree offset;
565 10977666 : poly_widest_int size;
566 10977666 : tree obj = TREE_OPERAND (expr, 0);
567 10977666 : tree base = get_inner_reference_aff (obj, &offset, &size);
568 :
569 10977666 : if (!base)
570 0 : return;
571 10977666 : if (!offset.offset.is_constant ())
572 : return;
573 10977666 : if (!size.is_constant ())
574 : return;
575 :
576 10977666 : m_pt = expr;
577 10977666 : m_points_to_p = points_to_p;
578 10977666 : m_kind = VR_RANGE;
579 10977666 : }
580 :
581 : // Return object/allocation the pointer refers into, otherwise NULL_TREE.
582 :
583 : tree
584 435 : prange::pt_base () const
585 : {
586 435 : if (!m_pt)
587 : return NULL_TREE;
588 :
589 435 : aff_tree off;
590 435 : poly_widest_int sz;
591 :
592 435 : gcc_checking_assert (m_pt);
593 435 : return get_inner_reference_aff (m_pt, &off, &sz);
594 435 : }
595 :
596 : // Return possible byte offset range from BASE.
597 :
598 : void
599 435 : prange::pt_offset (irange &r) const
600 : {
601 435 : aff_tree off;
602 435 : poly_widest_int sz;
603 :
604 435 : gcc_checking_assert (m_pt);
605 :
606 435 : get_inner_reference_aff (m_pt, &off, &sz);
607 435 : gcc_checking_assert (off.offset.is_constant ());
608 :
609 435 : widest_int w = off.offset.coeffs[0];
610 435 : wide_int w2 = wi::to_wide (wide_int_to_tree (sizetype, w));
611 435 : r.set (sizetype, w2, w2);
612 435 : }
613 :
614 : // Return possible size range of the referenced object.
615 :
616 : void
617 435 : prange::pt_size (irange &r) const
618 : {
619 435 : aff_tree off;
620 435 : poly_widest_int sz;
621 :
622 435 : gcc_checking_assert (m_pt);
623 :
624 435 : get_inner_reference_aff (m_pt, &off, &sz);
625 435 : gcc_checking_assert (sz.is_constant ());
626 :
627 435 : widest_int w = sz.coeffs[0];
628 435 : wide_int w2 = wi::to_wide (wide_int_to_tree (sizetype, w));
629 435 : r.set (sizetype, w2, w2);
630 435 : }
631 : // Prange implementation.
632 :
633 : void
634 1433 : prange::accept (const vrange_visitor &v) const
635 : {
636 1433 : v.visit (*this);
637 1433 : }
638 :
639 : void
640 0 : prange::set_nonnegative (tree type)
641 : {
642 0 : set (type,
643 0 : wi::zero (TYPE_PRECISION (type)),
644 0 : wi::max_value (TYPE_PRECISION (type), UNSIGNED));
645 0 : }
646 :
647 : void
648 14307306 : prange::set (tree min, tree max, value_range_kind kind)
649 : {
650 14307306 : return set (TREE_TYPE (min), wi::to_wide (min), wi::to_wide (max), kind);
651 : }
652 :
653 : void
654 42026931 : prange::set (tree type, const wide_int &min, const wide_int &max,
655 : value_range_kind kind)
656 : {
657 42026931 : if (kind == VR_UNDEFINED)
658 : {
659 0 : set_undefined ();
660 0 : return;
661 : }
662 42026931 : if (kind == VR_VARYING)
663 : {
664 0 : set_varying (type);
665 0 : return;
666 : }
667 42026931 : if (kind == VR_ANTI_RANGE)
668 : {
669 0 : gcc_checking_assert (min == 0 && max == 0);
670 0 : set_nonzero (type);
671 0 : return;
672 : }
673 42026931 : m_type = type;
674 42026931 : m_min = min;
675 42026931 : m_max = max;
676 42026931 : set_pt_unknown ();
677 :
678 42026931 : if (m_min == 0 && m_max == -1)
679 : {
680 5392961 : m_kind = VR_VARYING;
681 5392961 : m_bitmask.set_unknown (TYPE_PRECISION (type));
682 5392961 : if (flag_checking)
683 5392961 : verify_range ();
684 : return;
685 : }
686 :
687 36633970 : m_kind = VR_RANGE;
688 36633970 : m_bitmask = irange_bitmask (type, min, max);
689 36633970 : if (flag_checking)
690 36633958 : verify_range ();
691 : }
692 :
693 : bool
694 56147778 : prange::contains_p (const wide_int &w) const
695 : {
696 56147778 : if (undefined_p ())
697 : return false;
698 :
699 56147778 : if (varying_p ())
700 : return true;
701 :
702 45209558 : return (wi::le_p (lower_bound (), w, UNSIGNED)
703 23245799 : && wi::ge_p (upper_bound (), w, UNSIGNED));
704 : }
705 :
706 : bool
707 241767921 : prange::singleton_p (tree *result) const
708 : {
709 338069276 : if (m_kind == VR_RANGE && lower_bound () == upper_bound ())
710 : {
711 253049 : if (result)
712 126483 : *result = wide_int_to_tree (type (), m_min);
713 : return true;
714 : }
715 : return false;
716 : }
717 :
718 : tree
719 4891399 : prange::lbound () const
720 : {
721 4891399 : return wide_int_to_tree (type (), m_min);
722 : }
723 :
724 : tree
725 807376 : prange::ubound () const
726 : {
727 807376 : return wide_int_to_tree (type (), m_max);
728 : }
729 :
730 : bool
731 17284238 : prange::union_ (const vrange &v)
732 : {
733 17284238 : const prange &r = as_a <prange> (v);
734 :
735 17284238 : if (r.undefined_p ())
736 : return false;
737 17129764 : if (undefined_p ())
738 : {
739 8710717 : *this = r;
740 8710717 : if (flag_checking)
741 8710717 : verify_range ();
742 : return true;
743 : }
744 8419047 : if (varying_p ())
745 : return false;
746 4523055 : if (r.varying_p ())
747 : {
748 1298227 : set_varying (type ());
749 1298227 : return true;
750 : }
751 :
752 3224828 : wide_int new_lb = wi::min (r.lower_bound (), lower_bound (), UNSIGNED);
753 3224828 : wide_int new_ub = wi::max (r.upper_bound (), upper_bound (), UNSIGNED);
754 3224828 : prange new_range (type (), new_lb, new_ub);
755 3224828 : new_range.m_bitmask.union_ (m_bitmask);
756 3224828 : new_range.m_bitmask.union_ (r.m_bitmask);
757 :
758 : // Keep it simple, either both point to the same thing or both
759 : // do not point to the same thing, or we drop the points to info.
760 3224828 : if (pt_equal_p (r))
761 2550027 : new_range.set_pt (*this);
762 :
763 3224828 : if (new_range.varying_compatible_p ())
764 : {
765 331829 : set_varying (type ());
766 331829 : return true;
767 : }
768 2892999 : if (flag_checking)
769 2892999 : new_range.verify_range ();
770 2892999 : if (new_range == *this)
771 : return false;
772 286845 : *this = new_range;
773 286845 : return true;
774 3224828 : }
775 :
776 : bool
777 203602154 : prange::intersect (const vrange &v)
778 : {
779 203602154 : const prange &r = as_a <prange> (v);
780 203602154 : gcc_checking_assert (undefined_p () || r.undefined_p ()
781 : || range_compatible_p (type (), r.type ()));
782 :
783 203602154 : if (undefined_p ())
784 : return false;
785 203477673 : if (r.undefined_p ())
786 : {
787 33414 : set_undefined ();
788 33414 : return true;
789 : }
790 203444259 : if (r.varying_p ())
791 : return false;
792 107666580 : if (varying_p ())
793 : {
794 48094092 : *this = r;
795 48094092 : return true;
796 : }
797 :
798 : // If this points to and away, results are undefined,
799 59572488 : if (pt_inverted_p (r))
800 : {
801 0 : set_undefined ();
802 0 : return true;
803 : }
804 :
805 59572488 : prange save = *this;
806 59572488 : m_min = wi::max (r.lower_bound (), lower_bound (), UNSIGNED);
807 59572488 : m_max = wi::min (r.upper_bound (), upper_bound (), UNSIGNED);
808 59572488 : if (wi::gt_p (m_min, m_max, UNSIGNED))
809 : {
810 398429 : set_undefined ();
811 398429 : return true;
812 : }
813 :
814 : // Intersect all bitmasks: the old one, the new one, and the other operand's.
815 59174059 : irange_bitmask new_bitmask (m_type, m_min, m_max);
816 59174059 : if (!m_bitmask.intersect (new_bitmask))
817 12 : set_undefined ();
818 59174047 : else if (!m_bitmask.intersect (r.m_bitmask))
819 4 : set_undefined ();
820 : // If only one object points to something, that is the intersection.
821 59174043 : else if (pt_unknown_p () && !r.pt_unknown_p ())
822 626614 : set_pt (r);
823 58547429 : else if (!pt_unknown_p () && !r.pt_unknown_p ())
824 : {
825 : // If both point to something, we want to be careful. Without aliasing
826 : // 2 different values can point to the same thing, so UNDEFINED is
827 : // not appropriate, but we want to keep the rule that intersection
828 : // never becomes larger.
829 : // If the other object points to something specific, and this one does
830 : // not, use the specific one. Otherwise leave the range as is.
831 140626 : if (pt_invariant_away () && r.pt_invariant ())
832 0 : set_pt (r);
833 : }
834 :
835 : // If this evolves to zero, clear all points-to info.
836 59174059 : if (zero_p () && !pt_unknown_p ())
837 5909 : set_pt_unknown ();
838 :
839 59174059 : if (varying_compatible_p ())
840 : {
841 0 : set_varying (type ());
842 0 : return true;
843 : }
844 :
845 59174059 : if (flag_checking)
846 59173954 : verify_range ();
847 59174059 : if (*this == save)
848 57586266 : return false;
849 : return true;
850 59572488 : }
851 :
852 : prange &
853 191415611 : prange::operator= (const prange &src)
854 : {
855 191415611 : m_type = src.m_type;
856 191415611 : m_kind = src.m_kind;
857 191415611 : m_min = src.m_min;
858 191415611 : m_max = src.m_max;
859 191415611 : m_bitmask = src.m_bitmask;
860 191415611 : set_pt (src);
861 191415611 : if (flag_checking)
862 191415476 : verify_range ();
863 191415611 : return *this;
864 : }
865 :
866 : bool
867 67217844 : prange::operator== (const prange &src) const
868 : {
869 67217844 : if (m_kind == src.m_kind)
870 : {
871 66575963 : if (undefined_p ())
872 : return true;
873 :
874 66567198 : if (varying_p ())
875 1142132 : return types_compatible_p (type (), src.type ());
876 :
877 65425066 : if (!pt_equal_p (src))
878 : return false;
879 :
880 128490530 : return (m_min == src.m_min && m_max == src.m_max
881 128093592 : && m_bitmask == src.m_bitmask);
882 : }
883 : return false;
884 : }
885 :
886 :
887 : // Return the inverse of a range. Return false if thre is no invert
888 : // calculatable.
889 :
890 : bool
891 2744224 : prange::invert ()
892 : {
893 2744224 : if (undefined_p () || varying_p ())
894 : return false;
895 :
896 : // Invert the points_to object. If that worked, this is done.
897 2744224 : if (pt_invert ())
898 0 : return true;
899 : else
900 2744224 : set_pt_unknown ();
901 :
902 2744224 : wide_int new_lb, new_ub;
903 2744224 : unsigned prec = TYPE_PRECISION (type ());
904 2744224 : wide_int type_min = wi::zero (prec);
905 2744224 : wide_int type_max = wi::max_value (prec, UNSIGNED);
906 2744224 : wi::overflow_type ovf;
907 :
908 2744224 : if (lower_bound () == type_min)
909 : {
910 2736466 : new_lb = wi::add (upper_bound (), 1, UNSIGNED, &ovf);
911 2736466 : if (ovf)
912 0 : new_lb = type_min;
913 2736466 : new_ub = type_max;
914 2736466 : set (type (), new_lb, new_ub);
915 : }
916 7758 : else if (upper_bound () == type_max)
917 : {
918 2947 : wi::overflow_type ovf;
919 2947 : new_lb = type_min;
920 2947 : new_ub = wi::sub (lower_bound (), 1, UNSIGNED, &ovf);
921 2947 : if (ovf)
922 0 : new_ub = type_max;
923 2947 : set (type (), new_lb, new_ub);
924 : }
925 : else
926 4811 : set_varying (type ());
927 2744224 : return true;
928 2744224 : }
929 :
930 : void
931 1539901022 : prange::verify_range () const
932 : {
933 1539901022 : gcc_checking_assert (m_discriminator == VR_PRANGE);
934 :
935 1539901022 : if (m_kind == VR_UNDEFINED)
936 : {
937 65630 : gcc_checking_assert (pt_unknown_p ());
938 : return;
939 : }
940 :
941 1539835392 : gcc_checking_assert (supports_p (type ()));
942 :
943 1539835392 : if (m_kind == VR_VARYING)
944 : {
945 692745108 : gcc_checking_assert (varying_compatible_p ());
946 : return;
947 : }
948 847090284 : gcc_checking_assert (!varying_compatible_p ());
949 847090284 : gcc_checking_assert (m_kind == VR_RANGE);
950 847090284 : if (!pt_unknown_p ())
951 : {
952 41553721 : gcc_checking_assert (!varying_p ());
953 41553721 : gcc_checking_assert (!undefined_p ());
954 41553721 : gcc_checking_assert (!zero_p ());
955 : }
956 : }
957 :
958 : void
959 31095272 : prange::update_bitmask (const irange_bitmask &bm)
960 : {
961 31095272 : gcc_checking_assert (!undefined_p ());
962 :
963 : // If all the bits are known, this is a singleton.
964 31095272 : if (bm.mask () == 0)
965 : {
966 162455 : set (type (), bm.value (), bm.value ());
967 162455 : return;
968 : }
969 :
970 : // Drop VARYINGs with known bits to a plain range.
971 38624317 : if (m_kind == VR_VARYING && !bm.unknown_p ())
972 39245 : m_kind = VR_RANGE;
973 :
974 30932817 : m_bitmask = bm;
975 30932817 : if (varying_compatible_p ())
976 7652255 : m_kind = VR_VARYING;
977 :
978 30932817 : if (flag_checking)
979 30932817 : verify_range ();
980 : }
981 :
982 :
983 : // Frange implementation.
984 :
985 : void
986 226 : frange::accept (const vrange_visitor &v) const
987 : {
988 226 : v.visit (*this);
989 226 : }
990 :
991 : bool
992 0 : frange::fits_p (const vrange &) const
993 : {
994 0 : return true;
995 : }
996 :
997 : // Compare two range endpoints.
998 : //
999 : // In IEEE -0.0 and +0.0 equal for comparison purposes, but as endpoints they
1000 : // are distinct. Order -0.0 strictly below +0.0 and use this rather than
1001 : // real_less/real_compare, and the signed zeros stop needing a special case.
1002 :
1003 : static int
1004 121392022 : frange_cmp (const REAL_VALUE_TYPE &a, const REAL_VALUE_TYPE &b)
1005 : {
1006 121392022 : gcc_checking_assert (!real_isnan (&a) && !real_isnan (&b));
1007 :
1008 121392022 : if (real_less (&a, &b))
1009 : return -1;
1010 51647116 : if (real_less (&b, &a))
1011 : return 1;
1012 24522309 : if (real_iszero (&a) && real_iszero (&b))
1013 : {
1014 5213185 : bool nega = real_isneg (&a);
1015 5213185 : bool negb = real_isneg (&b);
1016 5213185 : if (nega && !negb)
1017 : return -1;
1018 3963218 : if (!nega && negb)
1019 298825 : return 1;
1020 : }
1021 : return 0;
1022 : }
1023 :
1024 : static inline const REAL_VALUE_TYPE &
1025 8872477 : frange_min (const REAL_VALUE_TYPE &a, const REAL_VALUE_TYPE &b)
1026 : {
1027 8872477 : return frange_cmp (a, b) <= 0 ? a : b;
1028 : }
1029 :
1030 : static inline const REAL_VALUE_TYPE &
1031 8872477 : frange_max (const REAL_VALUE_TYPE &a, const REAL_VALUE_TYPE &b)
1032 : {
1033 8872477 : return frange_cmp (a, b) >= 0 ? a : b;
1034 : }
1035 :
1036 : // Return TRUE if [..., A_MAX] and [B_MIN, ...] can be fused into one interval,
1037 : // either because they overlap or because no representable value exists between
1038 : // them. The latter is how -0.0 and +0.0 abut: there is nothing in between, so
1039 : // [x, -0.0] U [+0.0, y] is really [x, y].
1040 :
1041 : static bool
1042 10033478 : frange_fusible_p (machine_mode mode, const REAL_VALUE_TYPE &a_max,
1043 : const REAL_VALUE_TYPE &b_min)
1044 : {
1045 10033478 : if (frange_cmp (b_min, a_max) <= 0)
1046 : return true;
1047 9238736 : REAL_VALUE_TYPE next = a_max;
1048 9238736 : frange_nextafter (mode, next, dconstinf);
1049 9238736 : return frange_cmp (b_min, next) <= 0;
1050 : }
1051 :
1052 : // Flush denormal endpoints to the appropriate 0.0.
1053 :
1054 : void
1055 6519679 : frange::flush_denormals_to_zero ()
1056 : {
1057 6519679 : if (undefined_p () || known_isnan ())
1058 0 : return;
1059 :
1060 6519679 : machine_mode mode = TYPE_MODE (type ());
1061 6519679 : frange_pair pairs[MAX_PAIRS];
1062 6519679 : unsigned n = m_num_ranges;
1063 :
1064 : // Flush a denormal endpoint to a zero of the same sign: a +denormal lower
1065 : // bound to +0.0, and a -denormal upper bound to -0.0. Then set_pairs, via
1066 : // canonicalize_zeros, rewrites the sign to whatever the flags make
1067 : // canonical. For example, under !HONOR_SIGNED_ZEROS (-fno-signed-zeros) a
1068 : // range reaching zero must hold both signs of it, so:
1069 : //
1070 : // [ +DENORMAL, 5.0 ] flushes to [ -0.0, 5.0 ]
1071 : //
1072 : // keeping contains_p (-0.0) true; under HONOR_SIGNED_ZEROS the sign stands
1073 : // and it stays [ +0.0, 5.0 ].
1074 13118554 : for (unsigned i = 0; i < n; ++i)
1075 : {
1076 6598875 : pairs[i] = m_pairs[i];
1077 6598875 : if (real_isdenormal (&pairs[i].max, mode) && real_isneg (&pairs[i].max))
1078 4454 : pairs[i].max = dconstm0;
1079 6598875 : if (real_isdenormal (&pairs[i].min, mode) && !real_isneg (&pairs[i].min))
1080 7092 : pairs[i].min = dconst0;
1081 : }
1082 :
1083 6519679 : set_pairs (pairs, n);
1084 : }
1085 :
1086 : // Canonicalize the signed zeros of a sub-range according with what the target
1087 : // and flags want:
1088 : //
1089 : // !MODE_HAS_SIGNED_ZEROS: the mode has no signed zero, so any zero is +0.0.
1090 : //
1091 : // !HONOR_SIGNED_ZEROS: the two zeros are one value, so widen the range to
1092 : // include both signs of it.
1093 : //
1094 : // Otherwise the sign is a real distinction, and we keep it.
1095 :
1096 : void
1097 51994898 : frange::canonicalize_zeros (frange_pair &p)
1098 : {
1099 207979592 : if (!MODE_HAS_SIGNED_ZEROS (TYPE_MODE (m_type)))
1100 : {
1101 0 : if (real_iszero (&p.min, 1))
1102 0 : p.min.sign = 0;
1103 0 : if (real_iszero (&p.max, 1))
1104 0 : p.max.sign = 0;
1105 : }
1106 51994898 : else if (!HONOR_SIGNED_ZEROS (m_type))
1107 : {
1108 1347535 : if (real_iszero (&p.max, 1))
1109 47 : p.max.sign = 0;
1110 1347535 : if (real_iszero (&p.min, 0))
1111 27656 : p.min.sign = 1;
1112 : }
1113 51994898 : }
1114 :
1115 : // Sort, fuse and install the N intervals in PAIRS as this range's sub-ranges.
1116 : //
1117 : // Fusing merges intervals that overlap or abut. If more than MAX_PAIRS still
1118 : // survive, the last slot swallows the surplus.
1119 :
1120 : void
1121 16756313 : frange::set_pairs (frange_pair *pairs, unsigned n)
1122 : {
1123 16756313 : gcc_checking_assert (n > 0);
1124 16756313 : machine_mode mode = TYPE_MODE (m_type);
1125 :
1126 : // Sort by lower bound. N is tiny (at most 2 * MAX_PAIRS).
1127 21022969 : for (unsigned i = 0; i + 1 < n; ++i)
1128 8911787 : for (unsigned j = i + 1; j < n; ++j)
1129 4645131 : if (frange_cmp (pairs[j].min, pairs[i].min) < 0)
1130 788667 : std::swap (pairs[i], pairs[j]);
1131 :
1132 : // Fuse overlapping and abutting intervals.
1133 : unsigned k = 0;
1134 21022969 : for (unsigned i = 1; i < n; ++i)
1135 : {
1136 4266656 : if (frange_fusible_p (mode, pairs[k].max, pairs[i].min))
1137 : {
1138 1183035 : if (frange_cmp (pairs[i].max, pairs[k].max) > 0)
1139 554055 : pairs[k].max = pairs[i].max;
1140 : }
1141 : else
1142 3083621 : pairs[++k] = pairs[i];
1143 : }
1144 16756313 : n = k + 1;
1145 :
1146 : // Only MAX_PAIRS fit. Like irange, keep the first pieces and let the last
1147 : // slot swallow the rest.
1148 16756313 : if (n > MAX_PAIRS)
1149 : {
1150 67393 : pairs[MAX_PAIRS - 1].max = pairs[n - 1].max;
1151 67393 : n = MAX_PAIRS;
1152 : }
1153 :
1154 16756313 : m_kind = VR_RANGE;
1155 16756313 : m_num_ranges = n;
1156 36528750 : for (unsigned i = 0; i < n; ++i)
1157 : {
1158 19772437 : m_pairs[i] = pairs[i];
1159 19772437 : canonicalize_zeros (m_pairs[i]);
1160 : }
1161 :
1162 16756313 : normalize_kind ();
1163 16756313 : if (flag_checking)
1164 16756313 : verify_range ();
1165 16756313 : }
1166 :
1167 : // Set the range to everything except the closed interval [MIN, MAX], which
1168 : // takes two sub-ranges:
1169 : //
1170 : // [-INF, prev (MIN)] U [next (MAX), +INF]
1171 : //
1172 : // Either half falls away when the excluded interval reaches the edge of the
1173 : // domain, and if it covers the entire domain.
1174 :
1175 : void
1176 83660 : frange::set_excluding (tree type, const REAL_VALUE_TYPE &min,
1177 : const REAL_VALUE_TYPE &max, const nan_state &nan)
1178 : {
1179 83660 : gcc_checking_assert (frange_cmp (min, max) <= 0);
1180 :
1181 83660 : machine_mode mode = TYPE_MODE (type);
1182 83660 : REAL_VALUE_TYPE dom_min = frange_val_min (type);
1183 83660 : REAL_VALUE_TYPE dom_max = frange_val_max (type);
1184 83660 : frange_pair pairs[MAX_PAIRS];
1185 83660 : unsigned n = 0;
1186 :
1187 : // PREV is the largest value below MIN, so DOM_MIN <= PREV whenever there is
1188 : // anything below MIN at all. Likewise for NEXT above MAX.
1189 83660 : if (frange_cmp (dom_min, min) < 0)
1190 : {
1191 82987 : REAL_VALUE_TYPE prev = min;
1192 82987 : frange_nextafter (mode, prev, dconstninf);
1193 82987 : pairs[n++] = { dom_min, prev };
1194 : }
1195 83660 : if (frange_cmp (max, dom_max) < 0)
1196 : {
1197 81349 : REAL_VALUE_TYPE next = max;
1198 81349 : frange_nextafter (mode, next, dconstinf);
1199 81349 : pairs[n++] = { next, dom_max };
1200 : }
1201 :
1202 : // The excluded interval covered the entire domain.
1203 83660 : if (n == 0)
1204 : {
1205 0 : if (HONOR_NANS (type) && (nan.pos_p () || nan.neg_p ()))
1206 0 : set_nan (type, nan);
1207 : else
1208 0 : set_undefined ();
1209 0 : return;
1210 : }
1211 :
1212 83660 : set (type, pairs[0].min, pairs[0].max, nan);
1213 83660 : if (n == 2)
1214 : {
1215 80676 : frange tmp;
1216 80676 : tmp.set (type, pairs[1].min, pairs[1].max, nan);
1217 80676 : union_ (tmp);
1218 80676 : }
1219 : }
1220 :
1221 : // Setter for franges.
1222 :
1223 : void
1224 32306121 : frange::set (tree type,
1225 : const REAL_VALUE_TYPE &min, const REAL_VALUE_TYPE &max,
1226 : const nan_state &nan, value_range_kind kind)
1227 : {
1228 : // VARYING and UNDEFINED go through set_varying() and set_undefined()
1229 : // respectively, like we do for irange.
1230 32306121 : gcc_checking_assert (kind == VR_RANGE || kind == VR_ANTI_RANGE);
1231 32306121 : gcc_checking_assert (!real_isnan (&min) && !real_isnan (&max));
1232 :
1233 32306121 : if (kind == VR_ANTI_RANGE)
1234 : {
1235 83660 : set_excluding (type, min, max, nan);
1236 83660 : return;
1237 : }
1238 :
1239 32222461 : m_kind = kind;
1240 32222461 : m_type = type;
1241 32222461 : m_num_ranges = 1;
1242 32222461 : m_pairs[0].min = min;
1243 32222461 : m_pairs[0].max = max;
1244 32222461 : if (HONOR_NANS (m_type))
1245 : {
1246 31351801 : m_pos_nan = nan.pos_p ();
1247 31351801 : m_neg_nan = nan.neg_p ();
1248 : }
1249 : else
1250 : {
1251 870660 : m_pos_nan = false;
1252 870660 : m_neg_nan = false;
1253 : }
1254 :
1255 32222461 : canonicalize_zeros (m_pairs[0]);
1256 :
1257 : // For -ffinite-math-only we can drop ranges outside the
1258 : // representable numbers to min/max for the type.
1259 32222461 : if (!HONOR_INFINITIES (m_type))
1260 : {
1261 870660 : REAL_VALUE_TYPE min_repr = frange_val_min (m_type);
1262 870660 : REAL_VALUE_TYPE max_repr = frange_val_max (m_type);
1263 870660 : if (real_less (&m_pairs[0].min, &min_repr))
1264 298570 : m_pairs[0].min = min_repr;
1265 572090 : else if (real_less (&max_repr, &m_pairs[0].min))
1266 1 : m_pairs[0].min = max_repr;
1267 870660 : if (real_less (&max_repr, &m_pairs[0].max))
1268 301983 : m_pairs[0].max = max_repr;
1269 568677 : else if (real_less (&m_pairs[0].max, &min_repr))
1270 0 : m_pairs[0].max = min_repr;
1271 : }
1272 :
1273 : // Check for swapped ranges.
1274 32222461 : gcc_checking_assert (real_compare (LE_EXPR, &min, &max));
1275 :
1276 32222461 : normalize_kind ();
1277 : }
1278 :
1279 : // Setter for an frange defaulting the NAN possibility to +-NAN when
1280 : // HONOR_NANS.
1281 :
1282 : void
1283 19622298 : frange::set (tree type,
1284 : const REAL_VALUE_TYPE &min, const REAL_VALUE_TYPE &max,
1285 : value_range_kind kind)
1286 : {
1287 19622298 : set (type, min, max, nan_state (true), kind);
1288 19622298 : }
1289 :
1290 : void
1291 62 : frange::set (tree min, tree max, value_range_kind kind)
1292 : {
1293 124 : set (TREE_TYPE (min),
1294 62 : *TREE_REAL_CST_PTR (min), *TREE_REAL_CST_PTR (max), kind);
1295 62 : }
1296 :
1297 : // Normalize range to VARYING or UNDEFINED, or vice versa. Return
1298 : // TRUE if anything changed.
1299 : //
1300 : // A range with no known properties can be dropped to VARYING.
1301 : // Similarly, a VARYING with any properties should be dropped to a
1302 : // VR_RANGE. Normalizing ranges upon changing them ensures there is
1303 : // only one representation for a given range.
1304 :
1305 : bool
1306 68679406 : frange::normalize_kind ()
1307 : {
1308 68679406 : if (m_kind == VR_RANGE
1309 63703194 : && m_num_ranges == 1
1310 59523977 : && frange_val_is_min (m_pairs[0].min, m_type)
1311 85037343 : && frange_val_is_max (m_pairs[0].max, m_type))
1312 : {
1313 12570351 : if (!HONOR_NANS (m_type) || (m_pos_nan && m_neg_nan))
1314 : {
1315 11074538 : set_varying (m_type);
1316 11074538 : return true;
1317 : }
1318 : }
1319 56109055 : else if (m_kind == VR_VARYING)
1320 : {
1321 4975997 : if (HONOR_NANS (m_type) && (!m_pos_nan || !m_neg_nan))
1322 : {
1323 1933554 : m_kind = VR_RANGE;
1324 1933554 : m_num_ranges = 1;
1325 1933554 : m_pairs[0].min = frange_val_min (m_type);
1326 1933554 : m_pairs[0].max = frange_val_max (m_type);
1327 1933554 : if (flag_checking)
1328 1933554 : verify_range ();
1329 : return true;
1330 : }
1331 : }
1332 51133058 : else if (m_kind == VR_NAN && !m_pos_nan && !m_neg_nan)
1333 4 : set_undefined ();
1334 : return false;
1335 : }
1336 :
1337 : // Union two ranges when one is known to be a NAN.
1338 :
1339 : bool
1340 216206 : frange::union_nans (const frange &r)
1341 : {
1342 216206 : gcc_checking_assert (known_isnan () || r.known_isnan ());
1343 :
1344 216206 : bool changed = false;
1345 216206 : if (known_isnan () && m_kind != r.m_kind)
1346 : {
1347 42138 : m_kind = r.m_kind;
1348 42138 : m_num_ranges = r.m_num_ranges;
1349 85224 : for (unsigned i = 0; i < r.m_num_ranges; ++i)
1350 43086 : m_pairs[i] = r.m_pairs[i];
1351 : changed = true;
1352 : }
1353 216206 : if (m_pos_nan != r.m_pos_nan || m_neg_nan != r.m_neg_nan)
1354 : {
1355 205658 : m_pos_nan |= r.m_pos_nan;
1356 205658 : m_neg_nan |= r.m_neg_nan;
1357 205658 : changed = true;
1358 : }
1359 216206 : if (changed)
1360 : {
1361 213650 : normalize_kind ();
1362 213650 : return true;
1363 : }
1364 : return false;
1365 : }
1366 :
1367 : bool
1368 27789992 : frange::union_ (const vrange &v)
1369 : {
1370 27789992 : const frange &r = as_a <frange> (v);
1371 :
1372 27789992 : if (r.undefined_p () || varying_p ())
1373 : return false;
1374 26788312 : if (undefined_p () || r.varying_p ())
1375 : {
1376 23373307 : *this = r;
1377 23373307 : return true;
1378 : }
1379 :
1380 : // Combine NAN info.
1381 3415005 : if (known_isnan () || r.known_isnan ())
1382 216206 : return union_nans (r);
1383 :
1384 3198799 : frange save = *this;
1385 3198799 : m_pos_nan |= r.m_pos_nan;
1386 3198799 : m_neg_nan |= r.m_neg_nan;
1387 :
1388 : // Throw both operands' sub-ranges into the pot as set_pairs will
1389 : // canonicalize things and hand us back at most MAX_PAIRS.
1390 : //
1391 : // NOTE: Both operands are already sorted and disjoint, so a merge could
1392 : // combine them in O(n) like irange::union_ rather than have set_pairs
1393 : // re-sort. Not worth it while MAX_PAIRS is tiny; revisit if it grows.
1394 3198799 : frange_pair pairs[2 * MAX_PAIRS];
1395 3198799 : unsigned n = 0;
1396 6691142 : for (unsigned i = 0; i < save.m_num_ranges; ++i)
1397 3492343 : pairs[n++] = save.m_pairs[i];
1398 6455808 : for (unsigned i = 0; i < r.m_num_ranges; ++i)
1399 3257009 : pairs[n++] = r.m_pairs[i];
1400 :
1401 3198799 : set_pairs (pairs, n);
1402 3198799 : return *this != save;
1403 3198799 : }
1404 :
1405 : // Intersect two ranges when one is known to be a NAN.
1406 :
1407 : bool
1408 55455 : frange::intersect_nans (const frange &r)
1409 : {
1410 55455 : gcc_checking_assert (known_isnan () || r.known_isnan ());
1411 :
1412 55455 : m_pos_nan &= r.m_pos_nan;
1413 55455 : m_neg_nan &= r.m_neg_nan;
1414 58055 : if (maybe_isnan ())
1415 52887 : set_nan (m_type, get_nan_state ());
1416 : else
1417 2568 : set_undefined ();
1418 55455 : return true;
1419 : }
1420 :
1421 : bool
1422 23971154 : frange::intersect (const vrange &v)
1423 : {
1424 23971154 : const frange &r = as_a <frange> (v);
1425 :
1426 23971154 : if (undefined_p () || r.varying_p ())
1427 : return false;
1428 9651425 : if (r.undefined_p ())
1429 : {
1430 5804 : set_undefined ();
1431 5804 : return true;
1432 : }
1433 9645621 : if (varying_p ())
1434 : {
1435 2517177 : *this = r;
1436 2517177 : return true;
1437 : }
1438 :
1439 : // Combine NAN info.
1440 7128444 : if (known_isnan () || r.known_isnan ())
1441 55455 : return intersect_nans (r);
1442 :
1443 7072989 : frange save = *this;
1444 7072989 : m_pos_nan &= r.m_pos_nan;
1445 7072989 : m_neg_nan &= r.m_neg_nan;
1446 :
1447 : // Meet every sub-range against every other. Two sorted, disjoint sets of at
1448 : // most MAX_PAIRS each cannot yield more than MAX_PAIRS^2 pieces.
1449 : //
1450 : // NOTE: Since both operands are sorted, a merge-style meet like irange would
1451 : // be O(n) and leave set_pairs nothing to sort. Not worth it while MAX_PAIRS
1452 : // is tiny; revisit if it grows.
1453 7072989 : frange_pair pairs[MAX_PAIRS * MAX_PAIRS];
1454 7072989 : unsigned n = 0;
1455 14846093 : for (unsigned i = 0; i < save.m_num_ranges; ++i)
1456 16645581 : for (unsigned j = 0; j < r.m_num_ranges; ++j)
1457 : {
1458 8872477 : const REAL_VALUE_TYPE &min
1459 8872477 : = frange_max (save.m_pairs[i].min, r.m_pairs[j].min);
1460 8872477 : const REAL_VALUE_TYPE &max
1461 8872477 : = frange_min (save.m_pairs[i].max, r.m_pairs[j].max);
1462 : // A reversed interval means these two do not overlap. This also
1463 : // catches [+0.0, -0.0], which is empty rather than nonsensical.
1464 8872477 : if (frange_cmp (min, max) <= 0)
1465 7674742 : pairs[n++] = { min, max };
1466 : }
1467 :
1468 : // Nothing but a possible NAN survives.
1469 7072989 : if (n == 0)
1470 : {
1471 41034 : if (maybe_isnan ())
1472 29274 : set_nan (m_type, get_nan_state ());
1473 : else
1474 5880 : set_undefined ();
1475 : return true;
1476 : }
1477 :
1478 7037835 : set_pairs (pairs, n);
1479 7037835 : return *this != save;
1480 : }
1481 :
1482 : frange &
1483 40376609 : frange::operator= (const frange &src)
1484 : {
1485 40376609 : m_kind = src.m_kind;
1486 40376609 : m_type = src.m_type;
1487 40376609 : m_num_ranges = src.m_num_ranges;
1488 82342852 : for (unsigned i = 0; i < src.m_num_ranges; ++i)
1489 41966243 : m_pairs[i] = src.m_pairs[i];
1490 40376609 : m_pos_nan = src.m_pos_nan;
1491 40376609 : m_neg_nan = src.m_neg_nan;
1492 :
1493 40376609 : if (flag_checking)
1494 40376609 : verify_range ();
1495 40376609 : return *this;
1496 : }
1497 :
1498 : bool
1499 10354965 : frange::operator== (const frange &src) const
1500 : {
1501 10354965 : if (m_kind == src.m_kind)
1502 : {
1503 10214275 : if (undefined_p ())
1504 : return true;
1505 :
1506 10214137 : if (varying_p ())
1507 49290 : return types_compatible_p (m_type, src.m_type);
1508 :
1509 10164847 : bool nan1 = known_isnan ();
1510 10164847 : bool nan2 = src.known_isnan ();
1511 10164847 : if (nan1 || nan2)
1512 : {
1513 123 : if (nan1 && nan2)
1514 123 : return (m_pos_nan == src.m_pos_nan
1515 123 : && m_neg_nan == src.m_neg_nan);
1516 : return false;
1517 : }
1518 :
1519 10164724 : if (m_num_ranges != src.m_num_ranges)
1520 : return false;
1521 14125709 : for (unsigned i = 0; i < m_num_ranges; ++i)
1522 8637225 : if (!real_identical (&m_pairs[i].min, &src.m_pairs[i].min)
1523 8637225 : || !real_identical (&m_pairs[i].max, &src.m_pairs[i].max))
1524 : return false;
1525 :
1526 5488484 : return (m_pos_nan == src.m_pos_nan
1527 5313063 : && m_neg_nan == src.m_neg_nan
1528 10708764 : && types_compatible_p (m_type, src.m_type));
1529 : }
1530 : return false;
1531 : }
1532 :
1533 : // Return TRUE if range contains R.
1534 :
1535 : bool
1536 1288943 : frange::contains_p (const REAL_VALUE_TYPE &r) const
1537 : {
1538 1288943 : gcc_checking_assert (m_kind != VR_ANTI_RANGE);
1539 :
1540 1288943 : if (undefined_p ())
1541 : return false;
1542 :
1543 1288943 : if (varying_p ())
1544 : return true;
1545 :
1546 967966 : if (real_isnan (&r))
1547 : {
1548 : // No NAN in range.
1549 0 : if (!m_pos_nan && !m_neg_nan)
1550 : return false;
1551 : // Both +NAN and -NAN are present.
1552 0 : if (m_pos_nan && m_neg_nan)
1553 : return true;
1554 0 : return m_neg_nan == r.sign;
1555 : }
1556 967966 : if (known_isnan ())
1557 : return false;
1558 :
1559 1581389 : for (unsigned i = 0; i < m_num_ranges; ++i)
1560 977360 : if (frange_cmp (r, m_pairs[i].min) >= 0
1561 977360 : && frange_cmp (r, m_pairs[i].max) <= 0)
1562 : return true;
1563 :
1564 : return false;
1565 : }
1566 :
1567 : // If range is a singleton, place it in RESULT and return TRUE. If
1568 : // RESULT is NULL, just return TRUE.
1569 : //
1570 : // A NAN can never be a singleton.
1571 :
1572 : bool
1573 23856795 : frange::internal_singleton_p (REAL_VALUE_TYPE *result) const
1574 : {
1575 23856795 : if (m_kind == VR_RANGE
1576 4156958 : && m_num_ranges == 1
1577 27333494 : && real_identical (&m_pairs[0].min, &m_pairs[0].max))
1578 : {
1579 : // Return false for any singleton that may be a NAN.
1580 225662 : if (HONOR_NANS (m_type) && maybe_isnan ())
1581 : return false;
1582 :
1583 783454 : if (MODE_COMPOSITE_P (TYPE_MODE (m_type)))
1584 : {
1585 : // For IBM long doubles, if the value is +-Inf or is exactly
1586 : // representable in double, the other double could be +0.0
1587 : // or -0.0. Since this means there is more than one way to
1588 : // represent a value, return false to avoid propagating it.
1589 : // See libgcc/config/rs6000/ibm-ldouble-format for details.
1590 0 : if (real_isinf (&m_pairs[0].min))
1591 0 : return false;
1592 0 : REAL_VALUE_TYPE r;
1593 0 : real_convert (&r, DFmode, &m_pairs[0].min);
1594 0 : if (real_identical (&r, &m_pairs[0].min))
1595 : return false;
1596 : }
1597 :
1598 111922 : if (result)
1599 0 : *result = m_pairs[0].min;
1600 : return true;
1601 : }
1602 : return false;
1603 : }
1604 :
1605 : bool
1606 23856795 : frange::singleton_p (tree *result) const
1607 : {
1608 23856795 : if (internal_singleton_p ())
1609 : {
1610 111922 : if (result)
1611 9252 : *result = build_real (m_type, m_pairs[0].min);
1612 : return true;
1613 : }
1614 : return false;
1615 : }
1616 :
1617 : bool
1618 0 : frange::singleton_p (REAL_VALUE_TYPE &r) const
1619 : {
1620 0 : return internal_singleton_p (&r);
1621 : }
1622 :
1623 : bool
1624 62592066 : frange::supports_type_p (const_tree type) const
1625 : {
1626 62592066 : return supports_p (type);
1627 : }
1628 :
1629 : void
1630 236689923 : frange::verify_range () const
1631 : {
1632 236689923 : if (!undefined_p ())
1633 80816576 : gcc_checking_assert (HONOR_NANS (m_type) || !maybe_isnan ());
1634 236689923 : switch (m_kind)
1635 : {
1636 157716035 : case VR_UNDEFINED:
1637 157716035 : gcc_checking_assert (!m_type);
1638 : return;
1639 16261205 : case VR_VARYING:
1640 16261205 : gcc_checking_assert (m_type);
1641 16261205 : gcc_checking_assert (m_num_ranges == 1);
1642 16261205 : gcc_checking_assert (frange_val_is_min (m_pairs[0].min, m_type));
1643 16261205 : gcc_checking_assert (frange_val_is_max (m_pairs[0].max, m_type));
1644 16261205 : if (HONOR_NANS (m_type))
1645 15549514 : gcc_checking_assert (m_pos_nan && m_neg_nan);
1646 : else
1647 711691 : gcc_checking_assert (!m_pos_nan && !m_neg_nan);
1648 : return;
1649 62200106 : case VR_RANGE:
1650 62200106 : gcc_checking_assert (m_type);
1651 62200106 : gcc_checking_assert (m_num_ranges >= 1 && m_num_ranges <= MAX_PAIRS);
1652 : break;
1653 512577 : case VR_NAN:
1654 512577 : gcc_checking_assert (m_type);
1655 512577 : gcc_checking_assert (m_pos_nan || m_neg_nan);
1656 : return;
1657 0 : default:
1658 0 : gcc_unreachable ();
1659 : }
1660 :
1661 130167034 : for (unsigned i = 0; i < m_num_ranges; ++i)
1662 : {
1663 : // NANs cannot appear in the endpoints of a range.
1664 67966928 : gcc_checking_assert (!real_isnan (&m_pairs[i].min)
1665 : && !real_isnan (&m_pairs[i].max));
1666 :
1667 : // Make sure we don't have swapped ranges.
1668 : // This also catches [ +0.0, -0.0].
1669 67966928 : gcc_checking_assert (frange_cmp (m_pairs[i].min, m_pairs[i].max) <= 0);
1670 :
1671 : // A zero endpoint must carry its canonical sign. Every producer runs
1672 : // canonicalize_zeros, so a zero bound can only descend from a canonical
1673 : // one.
1674 271867712 : if (!MODE_HAS_SIGNED_ZEROS (TYPE_MODE (m_type)))
1675 0 : gcc_checking_assert (!real_iszero (&m_pairs[i].min, 1)
1676 : && !real_iszero (&m_pairs[i].max, 1));
1677 67966928 : else if (!HONOR_SIGNED_ZEROS (m_type))
1678 1197288 : gcc_checking_assert (!real_iszero (&m_pairs[i].min, 0)
1679 : && !real_iszero (&m_pairs[i].max, 1));
1680 : }
1681 :
1682 : // Sub-ranges are sorted and separated by at least one representable value.
1683 67966928 : for (unsigned i = 1; i < m_num_ranges; ++i)
1684 5766822 : gcc_checking_assert (!frange_fusible_p (TYPE_MODE (m_type),
1685 : m_pairs[i - 1].max,
1686 : m_pairs[i].min));
1687 :
1688 : // If all the properties are clear, we better not span the entire
1689 : // domain, because that would make us varying.
1690 62200106 : if (m_num_ranges == 1 && m_pos_nan && m_neg_nan)
1691 18428652 : gcc_checking_assert (!frange_val_is_min (m_pairs[0].min, m_type)
1692 : || !frange_val_is_max (m_pairs[0].max, m_type));
1693 : }
1694 :
1695 : void
1696 8 : frange::set_nonzero (tree type)
1697 : {
1698 8 : set (type, dconstm0, dconst0, VR_ANTI_RANGE);
1699 8 : }
1700 :
1701 : // Return TRUE if the range contains zero (+0.0 or -0.0).
1702 :
1703 : bool
1704 952765 : frange::contains_zero_p () const
1705 : {
1706 952765 : return contains_p (dconst0) || contains_p (dconstm0);
1707 : }
1708 :
1709 : // Set range to [+0.0, +0.0] if honoring signed zeros, or [0.0, 0.0]
1710 : // otherwise.
1711 :
1712 : void
1713 642113 : frange::set_zero (tree type)
1714 : {
1715 642113 : if (HONOR_SIGNED_ZEROS (type))
1716 : {
1717 642113 : set (type, dconstm0, dconst0);
1718 642113 : clear_nan ();
1719 : }
1720 : else
1721 0 : set (type, dconst0, dconst0);
1722 642113 : }
1723 :
1724 : // Return TRUE for any zero regardless of sign.
1725 :
1726 : bool
1727 8191 : frange::zero_p () const
1728 : {
1729 8191 : return (m_kind == VR_RANGE
1730 7194 : && m_num_ranges == 1
1731 6954 : && real_iszero (&m_pairs[0].min)
1732 10106 : && real_iszero (&m_pairs[0].max));
1733 : }
1734 :
1735 : // Set the range to non-negative numbers, that is [+0.0, +INF].
1736 : //
1737 : // The NAN in the resulting range (if HONOR_NANS) has a varying sign
1738 : // as there are no guarantees in IEEE 754 wrt to the sign of a NAN,
1739 : // except for copy, abs, and copysign. It is the responsibility of
1740 : // the caller to set the NAN's sign if desired.
1741 :
1742 : void
1743 38219 : frange::set_nonnegative (tree type)
1744 : {
1745 38219 : set (type, dconst0, frange_val_max (type));
1746 38219 : }
1747 :
1748 : tree
1749 0 : frange::lbound () const
1750 : {
1751 0 : return build_real (type (), lower_bound ());
1752 : }
1753 :
1754 : tree
1755 0 : frange::ubound () const
1756 : {
1757 0 : return build_real (type (), upper_bound ());
1758 : }
1759 :
1760 : /* Widen a single bound of a sub-range by 1ulp (or 0.5ulp) in the direction of
1761 : DIR. */
1762 :
1763 : static REAL_VALUE_TYPE
1764 1898910 : float_widen_bound (tree type, const REAL_VALUE_TYPE &bound,
1765 : const REAL_VALUE_TYPE &dir)
1766 : {
1767 1898910 : REAL_VALUE_TYPE res = bound;
1768 1898910 : if (!real_isfinite (&bound) && real_isneg (&bound) == real_isneg (&dir))
1769 : return res;
1770 1374094 : frange_nextafter (TYPE_MODE (type), res, dir);
1771 1374094 : if (real_isinf (&res))
1772 : {
1773 : /* For +-DBL_MAX, instead of +-Inf use nexttoward (+-DBL_MAX, +-LDBL_MAX)
1774 : in a hypothetical wider type with the same mantissa precision but
1775 : larger exponent range; it is outside of range of double values, but
1776 : makes it clear it is just one ulp larger rather than infinite amount
1777 : larger. */
1778 122038 : res = real_isneg (&dir) ? dconstm1 : dconst1;
1779 488152 : SET_REAL_EXP (&res, FLOAT_MODE_FORMAT (TYPE_MODE (type))->emax + 1);
1780 : }
1781 1374094 : if (!flag_rounding_math
1782 9618507 : && !MODE_COMPOSITE_P (TYPE_MODE (type))
1783 2747996 : && real_isfinite (&bound))
1784 : {
1785 : /* If not -frounding-math nor IBM double double, actually widen
1786 : just by 0.5ulp rather than 1ulp. */
1787 1372901 : REAL_VALUE_TYPE tem;
1788 1372901 : real_arithmetic (&tem, PLUS_EXPR, &bound, &res);
1789 1372901 : real_arithmetic (&res, RDIV_EXPR, &tem, &dconst2);
1790 : }
1791 : return res;
1792 : }
1793 :
1794 : /* Extend the *this range by 1ulp in each direction. For op1_range
1795 : or op2_range of binary operations just computing the inverse
1796 : operation on ranges isn't sufficient. Consider e.g.
1797 : [1., 1.] = op1 + [1., 1.]. op1's range is not [0., 0.], but
1798 : [-0x1.0p-54, 0x1.0p-53] (when not -frounding-math), any value for
1799 : which adding 1. to it results in 1. after rounding to nearest.
1800 : So, for op1_range/op2_range extend the lhs range by 1ulp (or 0.5ulp)
1801 : in each direction. See PR109008 for more details. */
1802 :
1803 : void
1804 892879 : frange::widen (tree type)
1805 : {
1806 892879 : if (known_isnan ())
1807 : return;
1808 : /* Temporarily disable -ffinite-math-only, so that frange::set doesn't
1809 : reduce the range back to real_min_representable (type) as lower bound
1810 : or real_max_representable (type) as upper bound. */
1811 886298 : bool save_flag_finite_math_only = flag_finite_math_only;
1812 886298 : flag_finite_math_only = false;
1813 886298 : unsigned j = 0;
1814 1835753 : for (unsigned i = 0; i < num_pairs (); ++i)
1815 : {
1816 949455 : REAL_VALUE_TYPE lb = float_widen_bound (type, lower_bound (i),
1817 : dconstninf);
1818 949455 : REAL_VALUE_TYPE ub = float_widen_bound (type, upper_bound (i),
1819 : dconstinf);
1820 : /* The result of float_widen_bound is often not representable in
1821 : type (could be smaller by 1ulp from representable finite minimum,
1822 : 0.5ulp from some representable finite value or 1ulp larger than
1823 : representable finite maximum). On such values calling e.g.
1824 : frange_nextafter doesn't work properly, so avoid merging the
1825 : pairs with union_ because that calls frange_fusible_p etc.
1826 : This range is often just something that should have the
1827 : real values passed to frange_arithmetic etc. and have the result
1828 : of that converted to something actually representable in the
1829 : type. See PR126641 and PR109008. As lhs should have been
1830 : canonicalized before, the slightly adjusted range should have
1831 : similar properties, just merge pairs where max would be >= than
1832 : min of the next pair. */
1833 949455 : if (j && !real_less (&m_pairs[j - 1].max, &lb))
1834 0 : m_pairs[j - 1].max = ub;
1835 : else
1836 : {
1837 949455 : m_pairs[j].min = lb;
1838 949455 : m_pairs[j].max = ub;
1839 949455 : ++j;
1840 : }
1841 : }
1842 886298 : m_num_ranges = j;
1843 886298 : flag_finite_math_only = save_flag_finite_math_only;
1844 : }
1845 :
1846 : // Here we copy between any two irange's.
1847 :
1848 : irange &
1849 1077228096 : irange::operator= (const irange &src)
1850 : {
1851 1077228096 : int needed = src.num_pairs ();
1852 1077228096 : maybe_resize (needed);
1853 :
1854 1077228096 : unsigned x;
1855 1077228096 : unsigned lim = src.m_num_ranges;
1856 1077228096 : if (lim > m_max_ranges)
1857 15305 : lim = m_max_ranges;
1858 :
1859 3418589594 : for (x = 0; x < lim * 2; ++x)
1860 2341361498 : m_base[x] = src.m_base[x];
1861 :
1862 : // If the range didn't fit, the last range should cover the rest.
1863 1077228096 : if (lim != src.m_num_ranges)
1864 15305 : m_base[x - 1] = src.m_base[src.m_num_ranges * 2 - 1];
1865 :
1866 1077228096 : m_num_ranges = lim;
1867 1077228096 : m_type = src.m_type;
1868 1077228096 : m_kind = src.m_kind;
1869 1077228096 : m_bitmask = src.m_bitmask;
1870 1077228096 : if (m_max_ranges == 1)
1871 21795634 : normalize_kind ();
1872 1077228096 : if (flag_checking)
1873 1077222286 : verify_range ();
1874 1077228096 : return *this;
1875 : }
1876 :
1877 : static value_range_kind
1878 21015680 : get_legacy_range (const irange &r, tree &min, tree &max)
1879 : {
1880 21015680 : if (r.undefined_p ())
1881 : {
1882 104391 : min = NULL_TREE;
1883 104391 : max = NULL_TREE;
1884 104391 : return VR_UNDEFINED;
1885 : }
1886 :
1887 20911289 : tree type = r.type ();
1888 20911289 : if (r.varying_p ())
1889 : {
1890 8895833 : min = wide_int_to_tree (type, r.lower_bound ());
1891 8895833 : max = wide_int_to_tree (type, r.upper_bound ());
1892 8895833 : return VR_VARYING;
1893 : }
1894 :
1895 12015456 : unsigned int precision = TYPE_PRECISION (type);
1896 12015456 : signop sign = TYPE_SIGN (type);
1897 24030912 : if (r.num_pairs () > 1
1898 3141493 : && precision > 1
1899 18298442 : && r.lower_bound () == wi::min_value (precision, sign)
1900 17187733 : && r.upper_bound () == wi::max_value (precision, sign))
1901 : {
1902 542722 : int_range<3> inv (r);
1903 542722 : inv.invert ();
1904 542722 : min = wide_int_to_tree (type, inv.lower_bound (0));
1905 542722 : max = wide_int_to_tree (type, inv.upper_bound (0));
1906 542722 : return VR_ANTI_RANGE;
1907 542722 : }
1908 :
1909 11472734 : min = wide_int_to_tree (type, r.lower_bound ());
1910 11472734 : max = wide_int_to_tree (type, r.upper_bound ());
1911 11472734 : return VR_RANGE;
1912 : }
1913 :
1914 : static value_range_kind
1915 3051859 : get_legacy_range (const prange &r, tree &min, tree &max)
1916 : {
1917 3051859 : if (r.undefined_p ())
1918 : {
1919 0 : min = NULL_TREE;
1920 0 : max = NULL_TREE;
1921 0 : return VR_UNDEFINED;
1922 : }
1923 :
1924 3051859 : tree type = r.type ();
1925 3051859 : if (r.varying_p ())
1926 : {
1927 0 : min = r.lbound ();
1928 0 : max = r.ubound ();
1929 0 : return VR_VARYING;
1930 : }
1931 3051859 : if (r.zero_p ())
1932 : {
1933 2293600 : min = max = r.lbound ();
1934 2293600 : return VR_RANGE;
1935 : }
1936 758259 : prange nonzero (type);
1937 758259 : nonzero.set_nonzero (type);
1938 1516518 : if (r.lower_bound () == nonzero.lower_bound ()
1939 792118 : && r.upper_bound () == nonzero.upper_bound ())
1940 : {
1941 0 : min = max = build_zero_cst (type);
1942 0 : return VR_ANTI_RANGE;
1943 : }
1944 758259 : min = r.lbound ();
1945 758259 : max = r.ubound ();
1946 758259 : return VR_RANGE;
1947 758259 : }
1948 :
1949 : // Given a range in V, return an old-style legacy range consisting of
1950 : // a value_range_kind with a MIN/MAX. This is to maintain
1951 : // compatibility with passes that still depend on VR_ANTI_RANGE, and
1952 : // only works for integers and pointers.
1953 :
1954 : value_range_kind
1955 24067539 : get_legacy_range (const vrange &v, tree &min, tree &max)
1956 : {
1957 24067539 : if (is_a <irange> (v))
1958 21015680 : return get_legacy_range (as_a <irange> (v), min, max);
1959 :
1960 3051859 : return get_legacy_range (as_a <prange> (v), min, max);
1961 : }
1962 :
1963 : /* Set value range to the canonical form of {VRTYPE, MIN, MAX, EQUIV}.
1964 : This means adjusting VRTYPE, MIN and MAX representing the case of a
1965 : wrapping range with MAX < MIN covering [MIN, type_max] U [type_min, MAX]
1966 : as anti-rage ~[MAX+1, MIN-1]. Likewise for wrapping anti-ranges.
1967 : In corner cases where MAX+1 or MIN-1 wraps this will fall back
1968 : to varying.
1969 : This routine exists to ease canonicalization in the case where we
1970 : extract ranges from var + CST op limit. */
1971 :
1972 : void
1973 1395032335 : irange::set (tree type, const wide_int &min, const wide_int &max,
1974 : value_range_kind kind)
1975 : {
1976 1395032335 : unsigned prec = TYPE_PRECISION (type);
1977 1395032335 : signop sign = TYPE_SIGN (type);
1978 1395032335 : wide_int min_value = wi::min_value (prec, sign);
1979 1395032335 : wide_int max_value = wi::max_value (prec, sign);
1980 :
1981 1395032335 : m_type = type;
1982 1395032335 : m_bitmask.set_unknown (prec);
1983 :
1984 1395032335 : if (kind == VR_RANGE)
1985 : {
1986 1339155752 : m_base[0] = min;
1987 1339155752 : m_base[1] = max;
1988 1339155752 : m_num_ranges = 1;
1989 1789844418 : if (min == min_value && max == max_value)
1990 31051764 : m_kind = VR_VARYING;
1991 : else
1992 1308103988 : m_kind = VR_RANGE;
1993 : }
1994 : else
1995 : {
1996 55876583 : gcc_checking_assert (kind == VR_ANTI_RANGE);
1997 55876583 : gcc_checking_assert (m_max_ranges > 1);
1998 :
1999 55876583 : m_kind = VR_UNDEFINED;
2000 55876583 : m_num_ranges = 0;
2001 55876583 : wi::overflow_type ovf;
2002 55876583 : wide_int lim;
2003 55876583 : if (sign == SIGNED)
2004 26641259 : lim = wi::add (min, -1, sign, &ovf);
2005 : else
2006 29236316 : lim = wi::sub (min, 1, sign, &ovf);
2007 :
2008 55876583 : if (!ovf)
2009 : {
2010 39556488 : m_kind = VR_RANGE;
2011 39556488 : m_base[0] = min_value;
2012 39556488 : m_base[1] = lim;
2013 39556488 : ++m_num_ranges;
2014 : }
2015 55876583 : if (sign == SIGNED)
2016 26641259 : lim = wi::sub (max, -1, sign, &ovf);
2017 : else
2018 29236316 : lim = wi::add (max, 1, sign, &ovf);
2019 55876583 : if (!ovf)
2020 : {
2021 55875155 : m_kind = VR_RANGE;
2022 55875155 : m_base[m_num_ranges * 2] = lim;
2023 55875155 : m_base[m_num_ranges * 2 + 1] = max_value;
2024 55875155 : ++m_num_ranges;
2025 : }
2026 55876583 : }
2027 :
2028 1395032335 : if (flag_checking)
2029 1395027378 : verify_range ();
2030 1395032335 : }
2031 :
2032 : void
2033 228677979 : irange::set (tree min, tree max, value_range_kind kind)
2034 : {
2035 228677979 : if (POLY_INT_CST_P (min) || POLY_INT_CST_P (max))
2036 : {
2037 : set_varying (TREE_TYPE (min));
2038 : return;
2039 : }
2040 :
2041 228677979 : gcc_checking_assert (TREE_CODE (min) == INTEGER_CST);
2042 228677979 : gcc_checking_assert (TREE_CODE (max) == INTEGER_CST);
2043 :
2044 228679102 : return set (TREE_TYPE (min), wi::to_wide (min), wi::to_wide (max), kind);
2045 : }
2046 :
2047 : // Check the validity of the range.
2048 :
2049 : void
2050 4643310422 : irange::verify_range () const
2051 : {
2052 4643310422 : gcc_checking_assert (m_discriminator == VR_IRANGE);
2053 4643310422 : if (m_kind == VR_UNDEFINED)
2054 : {
2055 194785 : gcc_checking_assert (m_num_ranges == 0);
2056 : return;
2057 : }
2058 4643115637 : gcc_checking_assert (supports_p (type ()));
2059 4643115637 : gcc_checking_assert (m_num_ranges <= m_max_ranges);
2060 :
2061 : // Legacy allowed these to represent VARYING for unknown types.
2062 : // Leave this in for now, until all users are converted. Eventually
2063 : // we should abort in set_varying.
2064 4643115637 : if (m_kind == VR_VARYING && m_type == error_mark_node)
2065 : return;
2066 :
2067 4643115637 : unsigned prec = TYPE_PRECISION (m_type);
2068 4643115637 : if (m_kind == VR_VARYING)
2069 : {
2070 237926531 : gcc_checking_assert (m_bitmask.unknown_p ());
2071 237926531 : gcc_checking_assert (m_num_ranges == 1);
2072 237926531 : gcc_checking_assert (varying_compatible_p ());
2073 237926531 : gcc_checking_assert (lower_bound ().get_precision () == prec);
2074 237926531 : gcc_checking_assert (upper_bound ().get_precision () == prec);
2075 237926531 : return;
2076 : }
2077 4405189106 : gcc_checking_assert (m_num_ranges != 0);
2078 4405189106 : gcc_checking_assert (!varying_compatible_p ());
2079 11092146599 : for (unsigned i = 0; i < m_num_ranges; ++i)
2080 : {
2081 6686957493 : wide_int lb = lower_bound (i);
2082 6686957493 : wide_int ub = upper_bound (i);
2083 6686957493 : gcc_checking_assert (lb.get_precision () == prec);
2084 6686957493 : gcc_checking_assert (ub.get_precision () == prec);
2085 6686957493 : int c = wi::cmp (lb, ub, TYPE_SIGN (m_type));
2086 6686957493 : gcc_checking_assert (c == 0 || c == -1);
2087 : // Previous UB should be lower than LB
2088 6686957493 : if (i > 0)
2089 4563536774 : gcc_checking_assert (wi::lt_p (upper_bound (i - 1),
2090 : lb,
2091 : TYPE_SIGN (m_type)));
2092 6689231814 : }
2093 4405189106 : m_bitmask.verify_mask ();
2094 : }
2095 :
2096 : bool
2097 164701632 : irange::operator== (const irange &other) const
2098 : {
2099 164701632 : if (m_num_ranges != other.m_num_ranges)
2100 : return false;
2101 :
2102 157292204 : if (m_num_ranges == 0)
2103 : return true;
2104 :
2105 157128790 : signop sign1 = TYPE_SIGN (type ());
2106 157128790 : signop sign2 = TYPE_SIGN (other.type ());
2107 :
2108 199819295 : for (unsigned i = 0; i < m_num_ranges; ++i)
2109 : {
2110 162568135 : widest_int lb = widest_int::from (lower_bound (i), sign1);
2111 162568135 : widest_int ub = widest_int::from (upper_bound (i), sign1);
2112 162568135 : widest_int lb_other = widest_int::from (other.lower_bound (i), sign2);
2113 162568135 : widest_int ub_other = widest_int::from (other.upper_bound (i), sign2);
2114 261199645 : if (lb != lb_other || ub != ub_other)
2115 119877630 : return false;
2116 162568559 : }
2117 :
2118 37251160 : irange_bitmask bm1 = get_bitmask ();
2119 37251160 : irange_bitmask bm2 = other.get_bitmask ();
2120 37251160 : widest_int tmp1 = widest_int::from (bm1.mask (), sign1);
2121 37251160 : widest_int tmp2 = widest_int::from (bm2.mask (), sign2);
2122 37251160 : if (tmp1 != tmp2)
2123 : return false;
2124 37246876 : if (bm1.unknown_p ())
2125 : return true;
2126 27063675 : tmp1 = widest_int::from (bm1.value (), sign1);
2127 27063675 : tmp2 = widest_int::from (bm2.value (), sign2);
2128 27063659 : return tmp1 == tmp2;
2129 37251199 : }
2130 :
2131 : /* If range is a singleton, place it in RESULT and return TRUE. */
2132 :
2133 : bool
2134 694208724 : irange::singleton_p (tree *result) const
2135 : {
2136 1287055487 : if (num_pairs () == 1 && lower_bound () == upper_bound ())
2137 : {
2138 44650040 : if (result)
2139 9940143 : *result = wide_int_to_tree (type (), lower_bound ());
2140 : return true;
2141 : }
2142 : return false;
2143 : }
2144 :
2145 : bool
2146 497716512 : irange::singleton_p (wide_int &w) const
2147 : {
2148 670903911 : if (num_pairs () == 1 && lower_bound () == upper_bound ())
2149 : {
2150 19084684 : w = lower_bound ();
2151 19084684 : return true;
2152 : }
2153 : return false;
2154 : }
2155 :
2156 : /* Return 1 if CST is inside value range.
2157 : 0 if CST is not inside value range.
2158 :
2159 : Benchmark compile/20001226-1.c compilation time after changing this
2160 : function. */
2161 :
2162 : bool
2163 217674197 : irange::contains_p (const wide_int &cst) const
2164 : {
2165 217674197 : if (undefined_p ())
2166 : return false;
2167 :
2168 : // Check if the known bits in bitmask exclude CST.
2169 217583587 : if (!m_bitmask.member_p (cst))
2170 : return false;
2171 :
2172 216977518 : signop sign = TYPE_SIGN (type ());
2173 232939379 : for (unsigned r = 0; r < m_num_ranges; ++r)
2174 : {
2175 232668852 : if (wi::lt_p (cst, lower_bound (r), sign))
2176 : return false;
2177 129881616 : if (wi::le_p (cst, upper_bound (r), sign))
2178 : return true;
2179 : }
2180 :
2181 : return false;
2182 : }
2183 :
2184 : // Perform an efficient union with R when both ranges have only a single pair.
2185 : // Excluded are VARYING and UNDEFINED ranges.
2186 :
2187 : bool
2188 113779067 : irange::irange_single_pair_union (const irange &r)
2189 : {
2190 113779067 : gcc_checking_assert (!undefined_p () && !varying_p ());
2191 113779067 : gcc_checking_assert (!r.undefined_p () && !varying_p ());
2192 :
2193 113779067 : signop sign = TYPE_SIGN (m_type);
2194 : // Check if current lower bound is also the new lower bound.
2195 113779067 : if (wi::le_p (m_base[0], r.m_base[0], sign))
2196 : {
2197 : // If current upper bound is new upper bound, we're done.
2198 99545910 : if (wi::le_p (r.m_base[1], m_base[1], sign))
2199 14634184 : return union_bitmask (r);
2200 : // Otherwise R has the new upper bound.
2201 : // Check for overlap/touching ranges, or single target range.
2202 169823452 : if (m_max_ranges == 1
2203 254735170 : || (widest_int::from (m_base[1], sign) + 1
2204 339646892 : >= widest_int::from (r.m_base[0], TYPE_SIGN (r.m_type))))
2205 26270906 : m_base[1] = r.m_base[1];
2206 : else
2207 : {
2208 : // This is a dual range result.
2209 58640820 : m_base[2] = r.m_base[0];
2210 58640820 : m_base[3] = r.m_base[1];
2211 58640820 : m_num_ranges = 2;
2212 : }
2213 : // The range has been altered, so normalize it even if nothing
2214 : // changed in the mask.
2215 84911726 : if (!union_bitmask (r))
2216 83977732 : normalize_kind ();
2217 84911726 : if (flag_checking)
2218 84911594 : verify_range ();
2219 : return true;
2220 : }
2221 :
2222 : // Set the new lower bound to R's lower bound.
2223 14233157 : wide_int lb = m_base[0];
2224 14233157 : m_base[0] = r.m_base[0];
2225 :
2226 : // If R fully contains THIS range, just set the upper bound.
2227 14233157 : if (wi::ge_p (r.m_base[1], m_base[1], sign))
2228 1384779 : m_base[1] = r.m_base[1];
2229 : // Check for overlapping ranges, or target limited to a single range.
2230 25696756 : else if (m_max_ranges == 1
2231 38545134 : || (widest_int::from (r.m_base[1], TYPE_SIGN (r.m_type)) + 1
2232 51393512 : >= widest_int::from (lb, sign)))
2233 : ;
2234 : else
2235 : {
2236 : // Left with 2 pairs.
2237 6231547 : m_num_ranges = 2;
2238 6231547 : m_base[2] = lb;
2239 6231547 : m_base[3] = m_base[1];
2240 6231547 : m_base[1] = r.m_base[1];
2241 : }
2242 : // The range has been altered, so normalize it even if nothing
2243 : // changed in the mask.
2244 14233157 : if (!union_bitmask (r))
2245 13077177 : normalize_kind ();
2246 14233157 : if (flag_checking)
2247 14233146 : verify_range ();
2248 14233157 : return true;
2249 14233157 : }
2250 :
2251 : // Append R to this range, knowing that R occurs after all of these subranges.
2252 : // Return TRUE as something must have changed.
2253 :
2254 : bool
2255 142566914 : irange::union_append (const irange &r)
2256 : {
2257 : // Check if the first range in R is an immediate successor to the last
2258 : // range, thus requiring a merge.
2259 142566914 : signop sign = TYPE_SIGN (m_type);
2260 142566914 : wide_int lb = r.lower_bound ();
2261 142566914 : wide_int ub = upper_bound ();
2262 142566914 : unsigned start = 0;
2263 427700742 : if (widest_int::from (ub, sign) + 1
2264 427700742 : == widest_int::from (lb, sign))
2265 : {
2266 943234 : m_base[m_num_ranges * 2 - 1] = r.m_base[1];
2267 943234 : start = 1;
2268 : }
2269 142566914 : maybe_resize (m_num_ranges + r.m_num_ranges - start);
2270 426802861 : for ( ; start < r.m_num_ranges; start++)
2271 : {
2272 : // Merge the last ranges if it exceeds the maximum size.
2273 142484422 : if (m_num_ranges + 1 > m_max_ranges)
2274 : {
2275 815389 : m_base[m_max_ranges * 2 - 1] = r.m_base[r.m_num_ranges * 2 - 1];
2276 815389 : break;
2277 : }
2278 141669033 : m_base[m_num_ranges * 2] = r.m_base[start * 2];
2279 141669033 : m_base[m_num_ranges * 2 + 1] = r.m_base[start * 2 + 1];
2280 141669033 : m_num_ranges++;
2281 : }
2282 :
2283 142566914 : if (!union_bitmask (r))
2284 142529086 : normalize_kind ();
2285 142566914 : if (flag_checking)
2286 142566914 : verify_range ();
2287 142566914 : return true;
2288 142566914 : }
2289 :
2290 : // Return TRUE if anything changes.
2291 :
2292 : bool
2293 391154213 : irange::union_ (const vrange &v)
2294 : {
2295 391154213 : const irange &r = as_a <irange> (v);
2296 :
2297 391154213 : if (r.undefined_p ())
2298 : return false;
2299 :
2300 388996045 : if (undefined_p ())
2301 : {
2302 91519094 : operator= (r);
2303 91519094 : if (flag_checking)
2304 91518689 : verify_range ();
2305 : return true;
2306 : }
2307 :
2308 297476951 : if (varying_p ())
2309 : return false;
2310 :
2311 288152223 : if (r.varying_p ())
2312 : {
2313 6543544 : set_varying (type ());
2314 6543544 : return true;
2315 : }
2316 :
2317 : // Special case one range union one range.
2318 281608679 : if (m_num_ranges == 1 && r.m_num_ranges == 1)
2319 113779067 : return irange_single_pair_union (r);
2320 :
2321 167829612 : signop sign = TYPE_SIGN (m_type);
2322 : // Check for an append to the end.
2323 503488836 : if (m_kind == VR_RANGE && wi::gt_p (r.lower_bound (), upper_bound (), sign))
2324 142566914 : return union_append (r);
2325 :
2326 : // If this ranges fully contains R, then we need do nothing.
2327 25262698 : if (irange_contains_p (r))
2328 4046431 : return union_bitmask (r);
2329 :
2330 : // Do not worry about merging and such by reserving twice as many
2331 : // pairs as needed, and then simply sort the 2 ranges into this
2332 : // intermediate form.
2333 : //
2334 : // The intermediate result will have the property that the beginning
2335 : // of each range is <= the beginning of the next range. There may
2336 : // be overlapping ranges at this point. I.e. this would be valid
2337 : // [-20, 10], [-10, 0], [0, 20], [40, 90] as it satisfies this
2338 : // constraint : -20 < -10 < 0 < 40. When the range is rebuilt into r,
2339 : // the merge is performed.
2340 : //
2341 : // [Xi,Yi]..[Xn,Yn] U [Xj,Yj]..[Xm,Ym] --> [Xk,Yk]..[Xp,Yp]
2342 21216267 : auto_vec<wide_int, 20> res (m_num_ranges * 2 + r.m_num_ranges * 2);
2343 21216267 : unsigned i = 0, j = 0, k = 0;
2344 :
2345 92925430 : while (i < m_num_ranges * 2 && j < r.m_num_ranges * 2)
2346 : {
2347 : // lower of Xi and Xj is the lowest point.
2348 100985792 : if (widest_int::from (m_base[i], sign)
2349 151478688 : <= widest_int::from (r.m_base[j], sign))
2350 : {
2351 26395495 : res.quick_push (m_base[i]);
2352 26395495 : res.quick_push (m_base[i + 1]);
2353 26395495 : k += 2;
2354 26395495 : i += 2;
2355 : }
2356 : else
2357 : {
2358 24097401 : res.quick_push (r.m_base[j]);
2359 24097401 : res.quick_push (r.m_base[j + 1]);
2360 24097401 : k += 2;
2361 24097401 : j += 2;
2362 : }
2363 : }
2364 42581686 : for ( ; i < m_num_ranges * 2; i += 2)
2365 : {
2366 21365419 : res.quick_push (m_base[i]);
2367 21365419 : res.quick_push (m_base[i + 1]);
2368 21365419 : k += 2;
2369 : }
2370 27164190 : for ( ; j < r.m_num_ranges * 2; j += 2)
2371 : {
2372 5947923 : res.quick_push (r.m_base[j]);
2373 5947923 : res.quick_push (r.m_base[j + 1]);
2374 5947923 : k += 2;
2375 : }
2376 :
2377 : // Now normalize the vector removing any overlaps.
2378 : i = 2;
2379 77806238 : for (j = 2; j < k ; j += 2)
2380 : {
2381 : // Current upper+1 is >= lower bound next pair, then we merge ranges.
2382 169769925 : if (widest_int::from (res[i - 1], sign) + 1
2383 169769913 : >= widest_int::from (res[j], sign))
2384 : {
2385 : // New upper bounds is greater of current or the next one.
2386 50097928 : if (widest_int::from (res[j + 1], sign)
2387 75146892 : > widest_int::from (res[i - 1], sign))
2388 19159818 : res[i - 1] = res[j + 1];
2389 : }
2390 : else
2391 : {
2392 : // This is a new distinct range, but no point in copying it
2393 : // if it is already in the right place.
2394 31541007 : if (i != j)
2395 : {
2396 10475997 : res[i++] = res[j];
2397 10475997 : res[i++] = res[j + 1];
2398 : }
2399 : else
2400 21065010 : i += 2;
2401 : }
2402 : }
2403 :
2404 : // At this point, the vector should have i ranges, none overlapping.
2405 : // Now it simply needs to be copied, and if there are too many
2406 : // ranges, merge some. We wont do any analysis as to what the
2407 : // "best" merges are, simply combine the final ranges into one.
2408 21216267 : maybe_resize (i / 2);
2409 21216267 : if (i > m_max_ranges * 2)
2410 : {
2411 1735 : res[m_max_ranges * 2 - 1] = res[i - 1];
2412 1735 : i = m_max_ranges * 2;
2413 : }
2414 :
2415 126727345 : for (j = 0; j < i ; j++)
2416 105511078 : m_base[j] = res [j];
2417 21216267 : m_num_ranges = i / 2;
2418 :
2419 21216267 : m_kind = VR_RANGE;
2420 : // The range has been altered, so normalize it even if nothing
2421 : // changed in the mask.
2422 21216267 : if (!union_bitmask (r))
2423 20255635 : normalize_kind ();
2424 21216267 : if (flag_checking)
2425 21216225 : verify_range ();
2426 21216267 : return true;
2427 21216267 : }
2428 :
2429 : // Return TRUE if THIS fully contains R. No undefined or varying cases.
2430 :
2431 : bool
2432 181268519 : irange::irange_contains_p (const irange &r) const
2433 : {
2434 181268519 : gcc_checking_assert (!undefined_p () && !varying_p ());
2435 181268519 : gcc_checking_assert (!r.undefined_p () && !varying_p ());
2436 :
2437 : // Check singletons directly which will include any bitmasks.
2438 181268519 : wide_int rl;
2439 181268519 : if (r.singleton_p (rl))
2440 14137802 : return contains_p (rl);
2441 :
2442 : // In order for THIS to fully contain R, all of the pairs within R must
2443 : // be fully contained by the pairs in this object.
2444 167130717 : signop sign = TYPE_SIGN (m_type);
2445 167130717 : unsigned ri = 0;
2446 167130717 : unsigned i = 0;
2447 167130717 : rl = r.m_base[0];
2448 167130717 : wide_int ru = r.m_base[1];
2449 167130717 : wide_int l = m_base[0];
2450 167130717 : wide_int u = m_base[1];
2451 433561963 : while (1)
2452 : {
2453 : // If r is contained within this range, move to the next R
2454 433561963 : if (wi::ge_p (rl, l, sign)
2455 433561963 : && wi::le_p (ru, u, sign))
2456 : {
2457 : // This pair is OK, Either done, or bump to the next.
2458 203318713 : if (++ri >= r.num_pairs ())
2459 : return true;
2460 131692168 : rl = r.m_base[ri * 2];
2461 131692168 : ru = r.m_base[ri * 2 + 1];
2462 131692168 : continue;
2463 : }
2464 : // Otherwise, check if this's pair occurs before R's.
2465 230243250 : if (wi::lt_p (u, rl, sign))
2466 : {
2467 : // There's still at least one pair of R left.
2468 135477806 : if (++i >= num_pairs ())
2469 : return false;
2470 134739078 : l = m_base[i * 2];
2471 134739078 : u = m_base[i * 2 + 1];
2472 134739078 : continue;
2473 : }
2474 : return false;
2475 : }
2476 : return false;
2477 167136355 : }
2478 :
2479 :
2480 : // Return TRUE if anything changes.
2481 :
2482 : bool
2483 916037291 : irange::intersect (const vrange &v)
2484 : {
2485 916037291 : const irange &r = as_a <irange> (v);
2486 916037291 : gcc_checking_assert (undefined_p () || r.undefined_p ()
2487 : || range_compatible_p (type (), r.type ()));
2488 :
2489 916037291 : if (undefined_p ())
2490 : return false;
2491 914925980 : if (r.undefined_p ())
2492 : {
2493 459603 : set_undefined ();
2494 459603 : return true;
2495 : }
2496 914466377 : if (r.varying_p ())
2497 : return false;
2498 613390121 : if (varying_p ())
2499 : {
2500 84207597 : operator= (r);
2501 84207597 : return true;
2502 : }
2503 :
2504 529182524 : if (r.num_pairs () == 1)
2505 : {
2506 373167444 : bool res = intersect (r.lower_bound (), r.upper_bound ());
2507 373165057 : if (undefined_p ())
2508 : return true;
2509 :
2510 344434285 : res |= intersect_bitmask (r);
2511 344434285 : if (res)
2512 119475295 : normalize_kind ();
2513 : return res;
2514 : }
2515 :
2516 : // If either range is a singleton and the other range does not contain
2517 : // it, the result is undefined.
2518 156017467 : wide_int val;
2519 157230862 : if ((singleton_p (val) && !r.contains_p (val))
2520 157219216 : || (r.singleton_p (val) && !contains_p (val)))
2521 : {
2522 11646 : set_undefined ();
2523 11646 : return true;
2524 : }
2525 :
2526 : // If R fully contains this, then intersection will change nothing.
2527 156005821 : if (r.irange_contains_p (*this))
2528 70387567 : return intersect_bitmask (r);
2529 :
2530 : // ?? We could probably come up with something smarter than the
2531 : // worst case scenario here.
2532 85618254 : int needed = num_pairs () + r.num_pairs ();
2533 85618254 : maybe_resize (needed);
2534 :
2535 85618254 : signop sign = TYPE_SIGN (m_type);
2536 85618254 : unsigned bld_pair = 0;
2537 85618254 : unsigned bld_lim = m_max_ranges;
2538 85618254 : int_range_max r2 (*this);
2539 85618254 : unsigned r2_lim = r2.num_pairs ();
2540 85618254 : unsigned i2 = 0;
2541 85618254 : bool need_snapping = !m_bitmask.unknown_p ();
2542 250753938 : for (unsigned i = 0; i < r.num_pairs (); )
2543 : {
2544 : // If r1's upper is < r2's lower, we can skip r1's pair.
2545 222812177 : wide_int ru = r.m_base[i * 2 + 1];
2546 222812177 : wide_int r2l = r2.m_base[i2 * 2];
2547 222812177 : if (wi::lt_p (ru, r2l, sign))
2548 : {
2549 20975634 : i++;
2550 20975634 : continue;
2551 : }
2552 : // Likewise, skip r2's pair if its excluded.
2553 201836543 : wide_int r2u = r2.m_base[i2 * 2 + 1];
2554 201836543 : wide_int rl = r.m_base[i * 2];
2555 201836543 : if (wi::lt_p (r2u, rl, sign))
2556 : {
2557 21423905 : i2++;
2558 21423905 : if (i2 < r2_lim)
2559 17068469 : continue;
2560 : // No more r2, break.
2561 : break;
2562 : }
2563 :
2564 : // Must be some overlap. Find the highest of the lower bounds,
2565 : // and set it, unless the build limits lower bounds is already
2566 : // set.
2567 180412638 : if (bld_pair < bld_lim)
2568 : {
2569 180116541 : if (wi::ge_p (rl, r2l, sign))
2570 152876677 : m_base[bld_pair * 2] = rl;
2571 : else
2572 27239864 : m_base[bld_pair * 2] = r2l;
2573 : }
2574 : else
2575 : // Decrease the index to use the existing lower bound, and
2576 : // set a new upper for this pair.
2577 296097 : bld_pair--;
2578 :
2579 : // Changes to false if the last value in i2's range is consumed.
2580 180412638 : bool more = true;
2581 : // ...and choose the lower of the upper bounds.
2582 180412638 : if (wi::le_p (ru, r2u, sign))
2583 : {
2584 115308514 : m_base[bld_pair * 2 + 1] = ru;
2585 : // Move past the r1 pair and keep trying.
2586 115308514 : i++;
2587 : }
2588 : else
2589 : {
2590 65104124 : m_base[bld_pair * 2 + 1] = r2u;
2591 65104124 : i2++;
2592 : // No more r2, break the loop when done.
2593 65104124 : if (i2 >= r2_lim)
2594 53321057 : more = false;
2595 : }
2596 : // Now snap these ranges to the bitmask, if there is one.
2597 180412638 : if (need_snapping)
2598 : {
2599 52756557 : bool ovf;
2600 52756557 : wide_int lb, ub;
2601 52756557 : if (snap (m_base[bld_pair * 2], m_base[bld_pair * 2 + 1],
2602 : lb, ub, ovf))
2603 : {
2604 : // If the new subrange does not fit the mask, skip it.
2605 1125169 : if (ovf)
2606 : {
2607 4132 : if (!more)
2608 : break;
2609 4132 : continue;
2610 : }
2611 : // Otherwise adjust the pair.
2612 1121037 : m_base[bld_pair * 2] = lb;
2613 1121037 : m_base[bld_pair * 2 + 1] = ub;
2614 : }
2615 52756557 : }
2616 : // Current pair now satisfies any mask, ready for another pair.
2617 180408506 : bld_pair++;
2618 180408506 : if (!more)
2619 : break;
2620 239890444 : }
2621 :
2622 : // At the exit of this loop, it is one of 2 things:
2623 : // ran out of r1, or r2, but either means we are done.
2624 85618254 : m_num_ranges = bld_pair;
2625 85618254 : if (m_num_ranges == 0)
2626 : {
2627 104143 : set_undefined ();
2628 104143 : return true;
2629 : }
2630 :
2631 85514111 : m_kind = VR_RANGE;
2632 : // The range has been altered, so normalize it even if nothing
2633 : // changed in the mask.
2634 85514111 : if (!intersect_bitmask (r))
2635 78783556 : normalize_kind ();
2636 85514111 : if (flag_checking)
2637 85514089 : verify_range ();
2638 : return true;
2639 241635721 : }
2640 :
2641 :
2642 : // Multirange intersect for a specified wide_int [lb, ub] range.
2643 : // Return TRUE if intersect changed anything.
2644 : //
2645 : // NOTE: It is the caller's responsibility to intersect the mask.
2646 :
2647 : bool
2648 373165057 : irange::intersect (const wide_int& lb, const wide_int& ub)
2649 : {
2650 : // Undefined remains undefined.
2651 373165057 : if (undefined_p ())
2652 : return false;
2653 :
2654 373165057 : tree range_type = type();
2655 373165057 : signop sign = TYPE_SIGN (range_type);
2656 :
2657 373165057 : gcc_checking_assert (TYPE_PRECISION (range_type) == wi::get_precision (lb));
2658 373165057 : gcc_checking_assert (TYPE_PRECISION (range_type) == wi::get_precision (ub));
2659 :
2660 : // If this range is fully contained, then intersection will do nothing.
2661 746330114 : if (wi::ge_p (lower_bound (), lb, sign)
2662 670189142 : && wi::le_p (upper_bound (), ub, sign))
2663 : return false;
2664 :
2665 135611684 : unsigned bld_index = 0;
2666 135611684 : unsigned pair_lim = num_pairs ();
2667 204602748 : for (unsigned i = 0; i < pair_lim; i++)
2668 : {
2669 150191342 : wide_int pairl = m_base[i * 2];
2670 150191342 : wide_int pairu = m_base[i * 2 + 1];
2671 : // Once UB is less than a pairs lower bound, we're done.
2672 150191342 : if (wi::lt_p (ub, pairl, sign))
2673 : break;
2674 : // if LB is greater than this pairs upper, this pair is excluded.
2675 127847594 : if (wi::lt_p (pairu, lb, sign))
2676 19303878 : continue;
2677 :
2678 : // Must be some overlap. Find the highest of the lower bounds,
2679 : // and set it
2680 108543716 : if (wi::gt_p (lb, pairl, sign))
2681 59018919 : m_base[bld_index * 2] = lb;
2682 : else
2683 49524797 : m_base[bld_index * 2] = pairl;
2684 :
2685 : // ...and choose the lower of the upper bounds and if the base pair
2686 : // has the lower upper bound, need to check next pair too.
2687 108543716 : if (wi::lt_p (ub, pairu, sign))
2688 : {
2689 58856530 : m_base[bld_index++ * 2 + 1] = ub;
2690 58856530 : break;
2691 : }
2692 : else
2693 49687186 : m_base[bld_index++ * 2 + 1] = pairu;
2694 150191826 : }
2695 :
2696 135611684 : m_num_ranges = bld_index;
2697 135611684 : if (m_num_ranges == 0)
2698 : {
2699 28730772 : set_undefined ();
2700 28730772 : return true;
2701 : }
2702 :
2703 106880912 : m_kind = VR_RANGE;
2704 : // The caller must normalize and verify the range, as the bitmask
2705 : // still needs to be handled.
2706 106880912 : return true;
2707 : }
2708 :
2709 :
2710 : // Signed 1-bits are strange. You can't subtract 1, because you can't
2711 : // represent the number 1. This works around that for the invert routine.
2712 :
2713 : static wide_int inline
2714 57146161 : subtract_one (const wide_int &x, tree type, wi::overflow_type &overflow)
2715 : {
2716 57146161 : if (TYPE_SIGN (type) == SIGNED)
2717 34880943 : return wi::add (x, -1, SIGNED, &overflow);
2718 : else
2719 22265218 : return wi::sub (x, 1, UNSIGNED, &overflow);
2720 : }
2721 :
2722 : // The analogous function for adding 1.
2723 :
2724 : static wide_int inline
2725 59562043 : add_one (const wide_int &x, tree type, wi::overflow_type &overflow)
2726 : {
2727 59562043 : if (TYPE_SIGN (type) == SIGNED)
2728 29366600 : return wi::sub (x, -1, SIGNED, &overflow);
2729 : else
2730 30195443 : return wi::add (x, 1, UNSIGNED, &overflow);
2731 : }
2732 :
2733 : // Return the inverse of a range. Return false if thre is no invert
2734 : // calculatable.
2735 :
2736 : bool
2737 60442663 : irange::invert ()
2738 : {
2739 : // UNDEFINED cannot be converted to varying because there is no type
2740 : // assocaited. Callers need to handle these cases.
2741 : // Its also ambiguous.. VARYING inverted could also arguably be VARYING
2742 : // in some cases. Likewise with UNDEFINED.
2743 60442663 : if (undefined_p () || varying_p ())
2744 : return false;
2745 :
2746 : // We always need one more set of bounds to represent an inverse, so
2747 : // if we're at the limit, we can't properly represent things.
2748 : //
2749 : // For instance, to represent the inverse of a 2 sub-range set
2750 : // [5, 10][20, 30], we would need a 3 sub-range set
2751 : // [-MIN, 4][11, 19][31, MAX].
2752 : //
2753 : // In this case, return false.
2754 : //
2755 : // However, if any of the extremes of the range are -MIN/+MAX, we
2756 : // know we will not need an extra bound. For example:
2757 : //
2758 : // INVERT([-MIN,20][30,40]) => [21,29][41,+MAX]
2759 : // INVERT([-MIN,20][30,MAX]) => [21,29]
2760 60442663 : tree ttype = type ();
2761 60442663 : unsigned prec = TYPE_PRECISION (ttype);
2762 60442663 : signop sign = TYPE_SIGN (ttype);
2763 60442663 : wide_int type_min = wi::min_value (prec, sign);
2764 60442663 : wide_int type_max = wi::max_value (prec, sign);
2765 60442663 : m_bitmask.set_unknown (prec);
2766 :
2767 : // At this point, we need one extra sub-range to represent the
2768 : // inverse.
2769 60442663 : maybe_resize (m_num_ranges + 1);
2770 :
2771 : // The algorithm is as follows. To calculate INVERT ([a,b][c,d]), we
2772 : // generate [-MIN, a-1][b+1, c-1][d+1, MAX].
2773 : //
2774 : // If there is an over/underflow in the calculation for any
2775 : // sub-range, we eliminate that subrange. This allows us to easily
2776 : // calculate INVERT([-MIN, 5]) with: [-MIN, -MIN-1][6, MAX]. And since
2777 : // we eliminate the underflow, only [6, MAX] remains.
2778 60442663 : unsigned i = 0;
2779 60442663 : wi::overflow_type ovf;
2780 : // Construct leftmost range.
2781 60442663 : int_range_max orig_range (*this);
2782 60442663 : unsigned nitems = 0;
2783 60442663 : wide_int tmp;
2784 : // If this is going to underflow on the MINUS 1, don't even bother
2785 : // checking. This also handles subtracting one from an unsigned 0,
2786 : // which doesn't set the underflow bit.
2787 60443248 : if (type_min != orig_range.lower_bound ())
2788 : {
2789 49611496 : m_base[nitems++] = type_min;
2790 49612081 : tmp = subtract_one (orig_range.lower_bound (), ttype, ovf);
2791 49611496 : m_base[nitems++] = tmp;
2792 49611496 : if (ovf)
2793 10831167 : nitems = 0;
2794 : }
2795 60442663 : i++;
2796 : // Construct middle ranges if applicable.
2797 60442663 : if (orig_range.num_pairs () > 1)
2798 : {
2799 : unsigned j = i;
2800 15058405 : for (; j < (orig_range.num_pairs () * 2) - 1; j += 2)
2801 : {
2802 : // The middle ranges cannot have MAX/MIN, so there's no need
2803 : // to check for unsigned overflow on the +1 and -1 here.
2804 7534665 : tmp = wi::add (orig_range.m_base[j], 1, sign, &ovf);
2805 7534665 : m_base[nitems++] = tmp;
2806 7534665 : tmp = subtract_one (orig_range.m_base[j + 1], ttype, ovf);
2807 7534665 : m_base[nitems++] = tmp;
2808 7534665 : if (ovf)
2809 0 : nitems -= 2;
2810 : }
2811 : i = j;
2812 : }
2813 : // Construct rightmost range.
2814 : //
2815 : // However, if this will overflow on the PLUS 1, don't even bother.
2816 : // This also handles adding one to an unsigned MAX, which doesn't
2817 : // set the overflow bit.
2818 60442663 : if (type_max != orig_range.m_base[i])
2819 : {
2820 59562043 : tmp = add_one (orig_range.m_base[i], ttype, ovf);
2821 59562043 : if (!ovf)
2822 : {
2823 : // Check to see if this inversion is going to work.
2824 59562043 : if (nitems / 2 >= m_max_ranges)
2825 : {
2826 : // No room for the extra field, so revert to the original value
2827 : // and return false.
2828 7 : *this = orig_range;
2829 7 : return false;
2830 : }
2831 59562036 : m_base[nitems++] = tmp;
2832 59562036 : m_base[nitems++] = type_max;
2833 : }
2834 : }
2835 60442656 : m_num_ranges = nitems / 2;
2836 :
2837 : // We disallow undefined or varying coming in, so the result can
2838 : // only be a VR_RANGE.
2839 60442656 : gcc_checking_assert (m_kind == VR_RANGE);
2840 :
2841 60442656 : if (flag_checking)
2842 60442564 : verify_range ();
2843 : return true;
2844 60443833 : }
2845 :
2846 : // This routine will take the bounds [LB, UB], and apply the bitmask to those
2847 : // values such that both bounds satisfy the bitmask. TRUE is returned
2848 : // if either bound changes, and they are returned as [NEW_LB, NEW_UB].
2849 : // If there is an overflow, or if (NEW_UB < NEW_LB), then the entire bound is
2850 : // to be removed as none of the values are valid. This is indicated by
2851 : // teturning TRUE in OVF. False indicates the bounds are fine.
2852 : // ie, [4, 14] MASK 0xFFFE VALUE 0x1
2853 : // means all values must be odd, the new bounds returned will be [5, 13] with
2854 : // OVF set to FALSE.
2855 : // ie, [4, 4] MASK 0xFFFE VALUE 0x1
2856 : // would return TRUE and OVF == TRUE. The entire subrange should be removed.
2857 :
2858 : bool
2859 225993880 : irange::snap (const wide_int &lb, const wide_int &ub,
2860 : wide_int &new_lb, wide_int &new_ub, bool &ovf)
2861 : {
2862 225993880 : ovf = false;
2863 225993880 : int z = wi::ctz (m_bitmask.mask ());
2864 225993880 : if (z == 0)
2865 : return false;
2866 :
2867 : // Shortcircuit check for values that are already good.
2868 263483526 : if ((((lb ^ m_bitmask.value ()) | (ub ^ m_bitmask.value ()))
2869 395220745 : & ~m_bitmask.mask ()) == 0)
2870 : return false;
2871 :
2872 13725783 : const wide_int step = (wi::one (TYPE_PRECISION (type ())) << z);
2873 13725783 : const wide_int match_mask = step - 1;
2874 13725783 : const wide_int value = m_bitmask.value () & match_mask;
2875 :
2876 13725783 : wide_int rem_lb = lb & match_mask;
2877 13725783 : wide_int offset = (value - rem_lb) & match_mask;
2878 13725783 : new_lb = lb + offset;
2879 : // Check for overflows at +INF
2880 13725783 : if (wi::lt_p (new_lb, lb, TYPE_SIGN (type ())))
2881 : {
2882 1809 : ovf = true;
2883 1809 : return true;
2884 : }
2885 :
2886 13723974 : wide_int rem_ub = ub & match_mask;
2887 13723974 : wide_int offset_ub = (rem_ub - value) & match_mask;
2888 13723974 : new_ub = ub - offset_ub;
2889 : // Check for underflows at -INF
2890 13723974 : if (wi::gt_p (new_ub, ub, TYPE_SIGN (type ())))
2891 : {
2892 115752 : ovf = true;
2893 115752 : return true;
2894 : }
2895 :
2896 : // If inverted range is invalid, set overflow to TRUE.
2897 13608222 : if (wi::lt_p (new_ub, new_lb, TYPE_SIGN (type ())))
2898 : {
2899 11749 : ovf = true;
2900 11749 : return true;
2901 : }
2902 24683765 : return (new_lb != lb) || (new_ub != ub);
2903 27449907 : }
2904 :
2905 : // This method loops through the subranges in THIS, and adjusts any bounds
2906 : // to satisfy the constraints of the BITMASK. If a subrange is invalid,
2907 : // it is removed. TRUE is returned if there were any changes.
2908 :
2909 : bool
2910 125674736 : irange::snap_subranges ()
2911 : {
2912 125674736 : bool changed = false;
2913 125674736 : int_range_max invalid;
2914 125674736 : unsigned x;
2915 125674736 : wide_int lb, ub;
2916 298912059 : for (x = 0; x < m_num_ranges; x++)
2917 : {
2918 173237323 : bool ovf;
2919 173243281 : if (snap (lower_bound (x), upper_bound (x), lb, ub, ovf))
2920 : {
2921 12387962 : changed = true;
2922 : // Check if this subrange is to be completely removed.
2923 12387962 : if (ovf)
2924 : {
2925 125178 : int_range<1> tmp (type (), lower_bound (x), upper_bound (x));
2926 125178 : invalid.union_ (tmp);
2927 125178 : continue;
2928 125178 : }
2929 12262814 : if (lower_bound (x) != lb)
2930 1729060 : m_base[x * 2] = lb;
2931 12262814 : if (upper_bound (x) != ub)
2932 11152414 : m_base[x * 2 + 1] = ub;
2933 : }
2934 : }
2935 : // Remove any subranges which are no invalid.
2936 125674736 : if (!invalid.undefined_p ())
2937 : {
2938 123527 : bool res = invalid.invert ();
2939 123527 : gcc_checking_assert (res);
2940 123527 : intersect (invalid);
2941 : }
2942 125674736 : return changed;
2943 125674766 : }
2944 :
2945 : // If the bitmask has a range representation, intersect this range with
2946 : // the bitmasks range. Then ensure all endpoints match the bitmask.
2947 : // Return TRUE if the range changes at all.
2948 :
2949 : bool
2950 125674736 : irange::set_range_from_bitmask ()
2951 : {
2952 125674736 : gcc_checking_assert (!undefined_p ());
2953 : // Snap subranmges when bitmask is first set.
2954 125674736 : snap_subranges ();
2955 125674736 : if (undefined_p ())
2956 : return true;
2957 :
2958 : // Calculate the set of ranges valid for the bitmask.
2959 125674692 : int_range_max allow;
2960 125674692 : if (!m_bitmask.range_from_mask (allow, m_type))
2961 : return false;
2962 : // And intersect that set of ranges with the current set.
2963 125595100 : return intersect (allow);
2964 125674692 : }
2965 :
2966 : void
2967 183495892 : irange::update_bitmask (const irange_bitmask &bm)
2968 : {
2969 183495892 : gcc_checking_assert (!undefined_p ());
2970 :
2971 : // If masks are the same, there is no change.
2972 183495892 : if (m_bitmask == bm)
2973 : return;
2974 :
2975 : // Drop VARYINGs with known bits to a plain range.
2976 88944707 : if (m_kind == VR_VARYING && !bm.unknown_p ())
2977 16019905 : m_kind = VR_RANGE;
2978 :
2979 72924802 : m_bitmask = bm;
2980 72924802 : if (!set_range_from_bitmask ())
2981 43516804 : normalize_kind ();
2982 72924802 : if (flag_checking)
2983 72924692 : verify_range ();
2984 : }
2985 :
2986 : // Return the bitmask of known bits that includes the bitmask inherent
2987 : // in the range.
2988 :
2989 : irange_bitmask
2990 1121611240 : irange::get_bitmask () const
2991 : {
2992 1121611240 : gcc_checking_assert (!undefined_p ());
2993 :
2994 : // The mask inherent in the range is calculated on-demand. For
2995 : // example, [0,255] does not have known bits set by default. This
2996 : // saves us considerable time, because setting it at creation incurs
2997 : // a large penalty for irange::set. At the time of writing there
2998 : // was a 5% slowdown in VRP if we kept the mask precisely up to date
2999 : // at all times. Instead, we default to -1 and set it when
3000 : // explicitly requested. However, this function will always return
3001 : // the correct mask.
3002 : //
3003 : // This also means that the mask may have a finer granularity than
3004 : // the range and thus contradict it. Think of the mask as an
3005 : // enhancement to the range. For example:
3006 : //
3007 : // [3, 1000] MASK 0xfffffffe VALUE 0x0
3008 : //
3009 : // 3 is in the range endpoints, but is excluded per the known 0 bits
3010 : // in the mask.
3011 : //
3012 : // See also the note in irange_bitmask::intersect.
3013 1121686288 : irange_bitmask bm (type (), lower_bound (), upper_bound ());
3014 1121611240 : if (!m_bitmask.unknown_p ())
3015 : {
3016 : // If the new intersection is unknown, it means there are inconsistent
3017 : // bits, so simply return the original bitmask.
3018 515887804 : if (!bm.intersect (m_bitmask))
3019 18158 : return m_bitmask;
3020 : }
3021 1121593082 : return bm;
3022 1121611240 : }
3023 :
3024 : // Set the nonzero bits in R into THIS. Return TRUE and
3025 : // normalize the range if anything changed.
3026 :
3027 : void
3028 636310 : vrange::set_nonzero_bits (const wide_int &bits)
3029 : {
3030 636310 : gcc_checking_assert (!undefined_p ());
3031 636310 : irange_bitmask bm (wi::zero (TYPE_PRECISION (type ())), bits);
3032 636310 : update_bitmask (bm);
3033 636310 : }
3034 :
3035 : // Return the nonzero bits in R.
3036 :
3037 : wide_int
3038 230993795 : vrange::get_nonzero_bits () const
3039 : {
3040 230993795 : gcc_checking_assert (!undefined_p ());
3041 230993795 : irange_bitmask bm = get_bitmask ();
3042 231059943 : return bm.value () | bm.mask ();
3043 230993795 : }
3044 :
3045 : // Intersect the bitmask in R into THIS and normalize the range.
3046 : // Return TRUE if the intersection changed anything.
3047 :
3048 : bool
3049 500335963 : irange::intersect_bitmask (const irange &r)
3050 : {
3051 500335963 : gcc_checking_assert (!undefined_p () && !r.undefined_p ());
3052 :
3053 : // If the bitmasks are the same, do nothing.
3054 500335963 : if (m_bitmask == r.m_bitmask)
3055 : return false;
3056 :
3057 182526394 : irange_bitmask bm = get_bitmask ();
3058 182526394 : irange_bitmask save = bm;
3059 182526394 : if (!bm.intersect (r.get_bitmask ()))
3060 : {
3061 30406 : set_undefined ();
3062 30406 : return true;
3063 : }
3064 :
3065 : // If the new mask is the same, there is no change.
3066 182495988 : if (m_bitmask == bm)
3067 : return false;
3068 :
3069 52749934 : m_bitmask = bm;
3070 52749934 : if (!set_range_from_bitmask ())
3071 52340727 : normalize_kind ();
3072 52749934 : if (flag_checking)
3073 52749769 : verify_range ();
3074 : return true;
3075 182526394 : }
3076 :
3077 : // Union the bitmask in R into THIS. Return TRUE and normalize the
3078 : // range if anything changed.
3079 :
3080 : bool
3081 281608679 : irange::union_bitmask (const irange &r)
3082 : {
3083 281608679 : gcc_checking_assert (!undefined_p () && !r.undefined_p ());
3084 :
3085 281608679 : if (m_bitmask == r.m_bitmask)
3086 : return false;
3087 :
3088 12466711 : irange_bitmask bm = get_bitmask ();
3089 12466711 : irange_bitmask save = bm;
3090 12466711 : bm.union_ (r.get_bitmask ());
3091 21809716 : if (save == bm && (!bm.unknown_p () || m_bitmask.unknown_p ()))
3092 : return false;
3093 :
3094 3123706 : m_bitmask = bm;
3095 :
3096 : // Updating m_bitmask may still yield a semantic bitmask (as
3097 : // returned by get_bitmask) which is functionally equivalent to what
3098 : // we originally had. In which case, there's still no change.
3099 3123706 : if (save == get_bitmask ())
3100 : return false;
3101 :
3102 : // No need to call set_range_from_mask, because we'll never
3103 : // narrow the range. Besides, it would cause endless recursion
3104 : // because of the union_ in set_range_from_mask.
3105 3123706 : normalize_kind ();
3106 3123706 : return true;
3107 12466711 : }
3108 :
3109 : tree
3110 9109766 : irange::lbound () const
3111 : {
3112 9109766 : return wide_int_to_tree (type (), lower_bound ());
3113 : }
3114 :
3115 : tree
3116 302643 : irange::ubound () const
3117 : {
3118 302643 : return wide_int_to_tree (type (), upper_bound ());
3119 : }
3120 :
3121 : void
3122 10324124057 : irange_bitmask::verify_mask () const
3123 : {
3124 10324124057 : gcc_assert (m_value.get_precision () == m_mask.get_precision ());
3125 10324124057 : gcc_checking_assert (wi::bit_and (m_mask, m_value) == 0);
3126 10324124057 : }
3127 :
3128 : void
3129 0 : dump_value_range (FILE *file, const vrange *vr)
3130 : {
3131 0 : vr->dump (file);
3132 0 : }
3133 :
3134 : DEBUG_FUNCTION void
3135 0 : debug (const vrange *vr)
3136 : {
3137 0 : dump_value_range (stderr, vr);
3138 0 : fprintf (stderr, "\n");
3139 0 : }
3140 :
3141 : DEBUG_FUNCTION void
3142 0 : debug (const vrange &vr)
3143 : {
3144 0 : debug (&vr);
3145 0 : }
3146 :
3147 : /* Return true, if VAL1 and VAL2 are equal values for VRP purposes. */
3148 :
3149 : bool
3150 144897477 : vrp_operand_equal_p (const_tree val1, const_tree val2)
3151 : {
3152 144897477 : if (val1 == val2)
3153 : return true;
3154 59994426 : if (!val1 || !val2 || !operand_equal_p (val1, val2, 0))
3155 59393748 : return false;
3156 : return true;
3157 : }
3158 :
3159 : #define DEFINE_INT_RANGE_INSTANCE(N) \
3160 : template int_range<N>::int_range(tree_node *, \
3161 : const wide_int &, \
3162 : const wide_int &, \
3163 : value_range_kind); \
3164 : template int_range<N>::int_range(tree); \
3165 : template int_range<N>::int_range(const irange &); \
3166 : template int_range<N>::int_range(const int_range &); \
3167 : template int_range<N>& int_range<N>::operator= (const int_range &);
3168 :
3169 : DEFINE_INT_RANGE_INSTANCE(1)
3170 : DEFINE_INT_RANGE_INSTANCE(2)
3171 : DEFINE_INT_RANGE_INSTANCE(3)
3172 : DEFINE_INT_RANGE_INSTANCE(255)
3173 :
3174 : #if CHECKING_P
3175 : #include "selftest.h"
3176 :
3177 : #define INT(x) wi::shwi ((x), TYPE_PRECISION (integer_type_node))
3178 : #define UINT(x) wi::uhwi ((x), TYPE_PRECISION (unsigned_type_node))
3179 : #define SCHAR(x) wi::shwi ((x), TYPE_PRECISION (signed_char_type_node))
3180 :
3181 : namespace selftest
3182 : {
3183 :
3184 : static int_range<2>
3185 584 : range (tree type, int a, int b, value_range_kind kind = VR_RANGE)
3186 : {
3187 584 : wide_int w1, w2;
3188 584 : if (TYPE_UNSIGNED (type))
3189 : {
3190 40 : w1 = wi::uhwi (a, TYPE_PRECISION (type));
3191 40 : w2 = wi::uhwi (b, TYPE_PRECISION (type));
3192 : }
3193 : else
3194 : {
3195 544 : w1 = wi::shwi (a, TYPE_PRECISION (type));
3196 544 : w2 = wi::shwi (b, TYPE_PRECISION (type));
3197 : }
3198 584 : return int_range<2> (type, w1, w2, kind);
3199 584 : }
3200 :
3201 : static int_range<2>
3202 540 : range_int (int a, int b, value_range_kind kind = VR_RANGE)
3203 : {
3204 0 : return range (integer_type_node, a, b, kind);
3205 : }
3206 :
3207 : static int_range<2>
3208 8 : range_uint (int a, int b, value_range_kind kind = VR_RANGE)
3209 : {
3210 4 : return range (unsigned_type_node, a, b, kind);
3211 : }
3212 :
3213 : static int_range<2>
3214 8 : range_uint128 (int a, int b, value_range_kind kind = VR_RANGE)
3215 : {
3216 8 : tree u128_type_node = build_nonstandard_integer_type (128, 1);
3217 8 : return range (u128_type_node, a, b, kind);
3218 : }
3219 :
3220 : static int_range<2>
3221 12 : range_uchar (int a, int b, value_range_kind kind = VR_RANGE)
3222 : {
3223 0 : return range (unsigned_char_type_node, a, b, kind);
3224 : }
3225 :
3226 : static int_range<2>
3227 4 : range_char (int a, int b, value_range_kind kind = VR_RANGE)
3228 : {
3229 0 : return range (signed_char_type_node, a, b, kind);
3230 : }
3231 :
3232 : static int_range<3>
3233 44 : build_range3 (int a, int b, int c, int d, int e, int f)
3234 : {
3235 44 : int_range<3> i1 = range_int (a, b);
3236 44 : int_range<3> i2 = range_int (c, d);
3237 44 : int_range<3> i3 = range_int (e, f);
3238 44 : i1.union_ (i2);
3239 44 : i1.union_ (i3);
3240 88 : return i1;
3241 44 : }
3242 :
3243 : static void
3244 4 : range_tests_irange3 ()
3245 : {
3246 4 : int_range<3> r0, r1, r2;
3247 4 : int_range<3> i1, i2, i3;
3248 :
3249 : // ([10,20] U [5,8]) U [1,3] ==> [1,3][5,8][10,20].
3250 4 : r0 = range_int (10, 20);
3251 4 : r1 = range_int (5, 8);
3252 4 : r0.union_ (r1);
3253 4 : r1 = range_int (1, 3);
3254 4 : r0.union_ (r1);
3255 4 : ASSERT_TRUE (r0 == build_range3 (1, 3, 5, 8, 10, 20));
3256 :
3257 : // [1,3][5,8][10,20] U [-5,0] => [-5,3][5,8][10,20].
3258 4 : r1 = range_int (-5, 0);
3259 4 : r0.union_ (r1);
3260 4 : ASSERT_TRUE (r0 == build_range3 (-5, 3, 5, 8, 10, 20));
3261 :
3262 : // [10,20][30,40] U [50,60] ==> [10,20][30,40][50,60].
3263 4 : r1 = range_int (50, 60);
3264 4 : r0 = range_int (10, 20);
3265 4 : r0.union_ (range_int (30, 40));
3266 4 : r0.union_ (r1);
3267 4 : ASSERT_TRUE (r0 == build_range3 (10, 20, 30, 40, 50, 60));
3268 : // [10,20][30,40][50,60] U [70, 80] ==> [10,20][30,40][50,60][70,80].
3269 4 : r1 = range_int (70, 80);
3270 4 : r0.union_ (r1);
3271 :
3272 4 : r2 = build_range3 (10, 20, 30, 40, 50, 60);
3273 4 : r2.union_ (range_int (70, 80));
3274 4 : ASSERT_TRUE (r0 == r2);
3275 :
3276 : // [10,20][30,40][50,60] U [6,35] => [6,40][50,60].
3277 4 : r0 = build_range3 (10, 20, 30, 40, 50, 60);
3278 4 : r1 = range_int (6, 35);
3279 4 : r0.union_ (r1);
3280 4 : r1 = range_int (6, 40);
3281 4 : r1.union_ (range_int (50, 60));
3282 4 : ASSERT_TRUE (r0 == r1);
3283 :
3284 : // [10,20][30,40][50,60] U [6,60] => [6,60].
3285 4 : r0 = build_range3 (10, 20, 30, 40, 50, 60);
3286 4 : r1 = range_int (6, 60);
3287 4 : r0.union_ (r1);
3288 4 : ASSERT_TRUE (r0 == range_int (6, 60));
3289 :
3290 : // [10,20][30,40][50,60] U [6,70] => [6,70].
3291 4 : r0 = build_range3 (10, 20, 30, 40, 50, 60);
3292 4 : r1 = range_int (6, 70);
3293 4 : r0.union_ (r1);
3294 4 : ASSERT_TRUE (r0 == range_int (6, 70));
3295 :
3296 : // [10,20][30,40][50,60] U [35,70] => [10,20][30,70].
3297 4 : r0 = build_range3 (10, 20, 30, 40, 50, 60);
3298 4 : r1 = range_int (35, 70);
3299 4 : r0.union_ (r1);
3300 4 : r1 = range_int (10, 20);
3301 4 : r1.union_ (range_int (30, 70));
3302 4 : ASSERT_TRUE (r0 == r1);
3303 :
3304 : // [10,20][30,40][50,60] U [15,35] => [10,40][50,60].
3305 4 : r0 = build_range3 (10, 20, 30, 40, 50, 60);
3306 4 : r1 = range_int (15, 35);
3307 4 : r0.union_ (r1);
3308 4 : r1 = range_int (10, 40);
3309 4 : r1.union_ (range_int (50, 60));
3310 4 : ASSERT_TRUE (r0 == r1);
3311 :
3312 : // [10,20][30,40][50,60] U [35,35] => [10,20][30,40][50,60].
3313 4 : r0 = build_range3 (10, 20, 30, 40, 50, 60);
3314 4 : r1 = range_int (35, 35);
3315 4 : r0.union_ (r1);
3316 4 : ASSERT_TRUE (r0 == build_range3 (10, 20, 30, 40, 50, 60));
3317 4 : }
3318 :
3319 : static void
3320 4 : range_tests_int_range_max ()
3321 : {
3322 4 : int_range_max big;
3323 4 : unsigned int nrange;
3324 :
3325 : // Build a huge multi-range range.
3326 208 : for (nrange = 0; nrange < 50; ++nrange)
3327 : {
3328 200 : int_range<1> tmp = range_int (nrange*10, nrange *10 + 5);
3329 200 : big.union_ (tmp);
3330 200 : }
3331 4 : ASSERT_TRUE (big.num_pairs () == nrange);
3332 :
3333 : // Verify that we can copy it without loosing precision.
3334 4 : int_range_max copy (big);
3335 4 : ASSERT_TRUE (copy.num_pairs () == nrange);
3336 :
3337 : // Inverting it should produce one more sub-range.
3338 4 : big.invert ();
3339 4 : ASSERT_TRUE (big.num_pairs () == nrange + 1);
3340 :
3341 4 : int_range<1> tmp = range_int (5, 37);
3342 4 : big.intersect (tmp);
3343 4 : ASSERT_TRUE (big.num_pairs () == 4);
3344 :
3345 : // Cannot resize tmp, and the invert does not fit,
3346 4 : ASSERT_FALSE (tmp.invert ());
3347 :
3348 : // Test that [10,10][20,20] does NOT contain 15.
3349 4 : {
3350 4 : int_range_max i1 = range_int (10, 10);
3351 4 : int_range_max i2 = range_int (20, 20);
3352 4 : i1.union_ (i2);
3353 4 : ASSERT_FALSE (i1.contains_p (INT (15)));
3354 4 : }
3355 4 : }
3356 :
3357 : // Simulate -fstrict-enums where the domain of a type is less than the
3358 : // underlying type.
3359 :
3360 : static void
3361 4 : range_tests_strict_enum ()
3362 : {
3363 : // The enum can only hold [0, 3].
3364 4 : tree rtype = copy_node (unsigned_type_node);
3365 4 : TYPE_MIN_VALUE (rtype) = build_int_cstu (rtype, 0);
3366 4 : TYPE_MAX_VALUE (rtype) = build_int_cstu (rtype, 3);
3367 :
3368 : // Test that even though vr1 covers the strict enum domain ([0, 3]),
3369 : // it does not cover the domain of the underlying type.
3370 4 : int_range<1> vr1 = range (rtype, 0, 1);
3371 4 : int_range<1> vr2 = range (rtype, 2, 3);
3372 4 : vr1.union_ (vr2);
3373 4 : ASSERT_TRUE (vr1 == range (rtype, 0, 3));
3374 4 : ASSERT_FALSE (vr1.varying_p ());
3375 :
3376 : // Test that copying to a multi-range does not change things.
3377 4 : int_range<2> ir1 (vr1);
3378 4 : ASSERT_TRUE (ir1 == vr1);
3379 4 : ASSERT_FALSE (ir1.varying_p ());
3380 :
3381 : // The same test as above, but using TYPE_{MIN,MAX}_VALUE instead of [0,3].
3382 8 : vr1 = int_range<2> (rtype,
3383 8 : wi::to_wide (TYPE_MIN_VALUE (rtype)),
3384 12 : wi::to_wide (TYPE_MAX_VALUE (rtype)));
3385 4 : ir1 = vr1;
3386 4 : ASSERT_TRUE (ir1 == vr1);
3387 4 : ASSERT_FALSE (ir1.varying_p ());
3388 4 : }
3389 :
3390 : // Test that range bounds are "snapped" to where they are expected to be.
3391 :
3392 : static void
3393 104 : assert_snap_result (int lb_val, int ub_val,
3394 : int expected_lb, int expected_ub,
3395 : unsigned mask_val, unsigned value_val,
3396 : tree type)
3397 : {
3398 104 : wide_int lb = wi::shwi (lb_val, TYPE_PRECISION (type));
3399 104 : wide_int ub = wi::shwi (ub_val, TYPE_PRECISION (type));
3400 104 : wide_int new_lb, new_ub;
3401 :
3402 208 : irange_bitmask bm (wi::uhwi (value_val, TYPE_PRECISION (type)),
3403 208 : wi::uhwi (mask_val, TYPE_PRECISION (type)));
3404 :
3405 104 : int_range_max r (type);
3406 104 : r.set (type, lb, ub);
3407 104 : r.update_bitmask (bm);
3408 :
3409 104 : if (TYPE_SIGN (type) == SIGNED && expected_ub < expected_lb)
3410 20 : gcc_checking_assert (r.undefined_p ());
3411 84 : else if (TYPE_SIGN (type) == UNSIGNED
3412 84 : && ((unsigned)expected_ub < (unsigned)expected_lb))
3413 16 : gcc_checking_assert (r.undefined_p ());
3414 : else
3415 : {
3416 68 : gcc_checking_assert (wi::eq_p (r.lower_bound (),
3417 : wi::shwi (expected_lb,
3418 : TYPE_PRECISION (type))));
3419 136 : gcc_checking_assert (wi::eq_p (r.upper_bound (),
3420 : wi::shwi (expected_ub,
3421 : TYPE_PRECISION (type))));
3422 : }
3423 104 : }
3424 :
3425 :
3426 : // Run a selection of tests that confirm, bounds are snapped as expected.
3427 : // We only test individual pairs, multiple pairs use the same snapping
3428 : // routine as single pairs.
3429 :
3430 : static void
3431 4 : test_irange_snap_bounds ()
3432 : {
3433 4 : tree u32 = unsigned_type_node;
3434 4 : tree s32 = integer_type_node;
3435 4 : tree s8 = build_nonstandard_integer_type (8, /*unsigned=*/ 0);
3436 4 : tree s1 = build_nonstandard_integer_type (1, /*unsigned=*/ 0);
3437 4 : tree u1 = build_nonstandard_integer_type (1, /*unsigned=*/ 1);
3438 :
3439 : // Basic aligned range: even-only
3440 4 : assert_snap_result (5, 15, 6, 14, 0xE, 0x0, u32);
3441 : // Singleton that doesn't match mask: undefined.
3442 4 : assert_snap_result (7, 7, 1, 0, 0xFFFFFFFE, 0x0, u32);
3443 : // 8-bit signed char, mask 0xF0 (i.e. step of 16).
3444 4 : assert_snap_result (-100, 100, -96, 96, 0xF0, 0x00, s8);
3445 : // Already aligned range: no change.
3446 4 : assert_snap_result (0, 240, 0, 240, 0xF0, 0x00, u32);
3447 : // Negative range, step 16 alignment (s32).
3448 4 : assert_snap_result (-123, -17, -112, -32, 0xFFFFFFF0, 0x00, s32);
3449 : // Negative range, step 16 alignment (trailing-zero aligned mask).
3450 4 : assert_snap_result (-123, -17, -112, -32, 0xFFFFFFF0, 0x00, s32);
3451 : // s8, 16-alignment mask, value = 0 (valid).
3452 4 : assert_snap_result (-50, 10, -48, 0, 0xF0, 0x00, s8);
3453 : // No values in range [-3,2] match alignment except 0.
3454 4 : assert_snap_result (-3, 2, 0, 0, 0xF8, 0x00, s8);
3455 : // No values in range [-3,2] match alignment — undefined.
3456 4 : assert_snap_result (-3, 2, 1, 0, 0xF8, 0x04, s8);
3457 : // Already aligned range: no change.
3458 4 : assert_snap_result (0, 240, 0, 240, 0xF0, 0x00, s32);
3459 : // 1-bit signed: only -1 allowed (0b1).
3460 4 : assert_snap_result (-1, 0, -1, -1, 0x00, 0x01, s1);
3461 : // 1-bit signed: only 0 allowed (0b0).
3462 4 : assert_snap_result (-1, 0, 0, 0, 0x00, 0x00, s1);
3463 : // 1-bit signed: no match (invalid case).
3464 4 : assert_snap_result (-1, -1, 1, 0, 0x00, 0x00, s1);
3465 : // 1-bit signed: no match (invalid case).
3466 4 : assert_snap_result (0, 0, 1, 0, 0x00, 0x01, s1);
3467 : // 1-bit unsigned: only 1 allowed.
3468 4 : assert_snap_result (0, 1, 1, 1, 0x00, 0x01, u1);
3469 : // 1-bit unsigned: only 0 allowed.
3470 4 : assert_snap_result (0, 1, 0, 0, 0x00, 0x00, u1);
3471 : // 1-bit unsigned: no match (invalid case).
3472 4 : assert_snap_result (1, 1, 1, 0, 0x00, 0x00, u1);
3473 : // 1-bit unsigned: no match (invalid case).
3474 4 : assert_snap_result (0, 0, 1, 0, 0x00, 0x01, u1);
3475 : // Unsigned: Near overflow, even alignment.
3476 4 : assert_snap_result (UINT_MAX - 6, UINT_MAX, UINT_MAX - 5, UINT_MAX - 1,
3477 : 0xFFFFFFFE, 0x00, u32);
3478 : // Unsigned: Wraparound-like range — no valid snapped values.
3479 4 : assert_snap_result (UINT_MAX - 5, UINT_MAX, 1, 0, 0xFFFFFFF0, 0x00, u32);
3480 : // Signed: Near INT_MAX, 8-aligned.
3481 4 : assert_snap_result (INT_MAX - 18, INT_MAX, INT_MAX - 15, INT_MAX - 7,
3482 : 0xFFFFFFF8, 0x00, s32);
3483 : // Signed: Near INT_MIN, 16-aligned.
3484 4 : assert_snap_result (INT_MIN, INT_MIN + 30, INT_MIN, INT_MIN + 16,
3485 : 0xFFFFFFF0, 0x00, s32);
3486 : // Signed: Full domain, 4-aligned.
3487 4 : assert_snap_result (-128, 127, -128, 124, 0xFC, 0x00, s8);
3488 : // Singleton at INT_MIN that doesn’t match alignment — undefined
3489 4 : assert_snap_result (INT_MIN, INT_MIN, 1, 0, 0xFFFFFFFE, 0x01, s32);
3490 : // Range at INT_MIN that doesn’t match alignment — undefined.
3491 4 : assert_snap_result (INT_MIN, INT_MIN + 10, 1, 0, 0xFFFFFFF0, 0x0F, s32);
3492 : // Unsigned: Full domain, 256-aligned.
3493 4 : assert_snap_result (0, UINT_MAX, 0, UINT_MAX & ~255, 0xFFFFFF00, 0x00, u32);
3494 4 : }
3495 :
3496 : static void
3497 4 : range_tests_misc ()
3498 : {
3499 4 : bool res;
3500 4 : tree u128_type = build_nonstandard_integer_type (128, /*unsigned=*/1);
3501 4 : int_range<2> i1, i2, i3;
3502 4 : int_range<2> r0, r1, rold;
3503 :
3504 : // Test 1-bit signed integer union.
3505 : // [-1,-1] U [0,0] = VARYING.
3506 4 : tree one_bit_type = build_nonstandard_integer_type (1, 0);
3507 4 : wide_int one_bit_min = irange_val_min (one_bit_type);
3508 4 : wide_int one_bit_max = irange_val_max (one_bit_type);
3509 4 : {
3510 4 : int_range<2> min = int_range<2> (one_bit_type, one_bit_min, one_bit_min);
3511 4 : int_range<2> max = int_range<2> (one_bit_type, one_bit_max, one_bit_max);
3512 4 : max.union_ (min);
3513 4 : ASSERT_TRUE (max.varying_p ());
3514 4 : }
3515 : // Test that we can set a range of true+false for a 1-bit signed int.
3516 4 : r0 = range_true_and_false (one_bit_type);
3517 :
3518 : // Test inversion of 1-bit signed integers.
3519 4 : {
3520 4 : int_range<2> min = int_range<2> (one_bit_type, one_bit_min, one_bit_min);
3521 4 : int_range<2> max = int_range<2> (one_bit_type, one_bit_max, one_bit_max);
3522 4 : int_range<2> t;
3523 4 : t = min;
3524 4 : res = t.invert ();
3525 4 : ASSERT_TRUE (res && t == max);
3526 4 : t = max;
3527 4 : res = t.invert ();
3528 4 : ASSERT_TRUE (res && t == min);
3529 4 : }
3530 :
3531 : // Test that NOT(255) is [0..254] in 8-bit land.
3532 4 : int_range<1> not_255 = range_uchar (255, 255, VR_ANTI_RANGE);
3533 4 : ASSERT_TRUE (not_255 == range_uchar (0, 254));
3534 :
3535 : // Test that NOT(0) is [1..255] in 8-bit land.
3536 4 : int_range<2> not_zero;
3537 4 : not_zero.set_nonzero (unsigned_char_type_node);
3538 4 : ASSERT_TRUE (not_zero == range_uchar (1, 255));
3539 :
3540 : // Check that [0,127][0x..ffffff80,0x..ffffff]
3541 : // => ~[128, 0x..ffffff7f].
3542 4 : r0 = range_uint128 (0, 127);
3543 4 : wide_int high = wi::minus_one (128);
3544 : // low = -1 - 127 => 0x..ffffff80.
3545 4 : wide_int low = wi::sub (high, wi::uhwi (127, 128));
3546 4 : r1 = int_range<1> (u128_type, low, high); // [0x..ffffff80, 0x..ffffffff]
3547 : // r0 = [0,127][0x..ffffff80,0x..fffffff].
3548 4 : r0.union_ (r1);
3549 : // r1 = [128, 0x..ffffff7f].
3550 12 : r1 = int_range<1> (u128_type,
3551 8 : wi::uhwi (128, 128),
3552 8 : wi::sub (wi::minus_one (128), wi::uhwi (128, 128)));
3553 4 : res = r0.invert ();
3554 4 : ASSERT_TRUE (res && r0 == r1);
3555 :
3556 4 : r0.set_varying (integer_type_node);
3557 4 : wide_int minint = r0.lower_bound ();
3558 4 : wide_int maxint = r0.upper_bound ();
3559 :
3560 4 : r0.set_varying (short_integer_type_node);
3561 :
3562 4 : r0.set_varying (unsigned_type_node);
3563 4 : wide_int maxuint = r0.upper_bound ();
3564 :
3565 : // Check that ~[0,5] => [6,MAX] for unsigned int.
3566 4 : r0 = range_uint (0, 5);
3567 4 : res = r0.invert ();
3568 4 : ASSERT_TRUE (res);
3569 4 : ASSERT_TRUE (r0 == int_range<1> (unsigned_type_node,
3570 : wi::uhwi (6, TYPE_PRECISION (unsigned_type_node)),
3571 : maxuint));
3572 :
3573 : // Check that ~[10,MAX] => [0,9] for unsigned int.
3574 8 : r0 = int_range<1> (unsigned_type_node,
3575 4 : wi::uhwi (10, TYPE_PRECISION (unsigned_type_node)),
3576 8 : maxuint);
3577 4 : res = r0.invert ();
3578 8 : ASSERT_TRUE (res && r0 == range_uint (0, 9));
3579 :
3580 : // Check that ~[0,5] => [6,MAX] for unsigned 128-bit numbers.
3581 4 : r0 = range_uint128 (0, 5, VR_ANTI_RANGE);
3582 4 : r1 = int_range<1> (u128_type, wi::uhwi (6, 128), wi::minus_one (128));
3583 4 : ASSERT_TRUE (r0 == r1);
3584 :
3585 : // Check that [~5] is really [-MIN,4][6,MAX].
3586 4 : r0 = range_int (5, 5, VR_ANTI_RANGE);
3587 4 : r1 = int_range<1> (integer_type_node, minint, INT (4));
3588 4 : r1.union_ (int_range<1> (integer_type_node, INT (6), maxint));
3589 4 : ASSERT_FALSE (r1.undefined_p ());
3590 4 : ASSERT_TRUE (r0 == r1);
3591 :
3592 4 : r1 = range_int (5, 5);
3593 4 : int_range<2> r2 (r1);
3594 4 : ASSERT_TRUE (r1 == r2);
3595 :
3596 4 : r1 = range_int (5, 10);
3597 :
3598 4 : r1 = range_int (5, 10);
3599 4 : ASSERT_TRUE (r1.contains_p (INT (7)));
3600 :
3601 4 : r1 = range_char (0, 20);
3602 4 : ASSERT_TRUE (r1.contains_p (SCHAR(15)));
3603 4 : ASSERT_FALSE (r1.contains_p (SCHAR(300)));
3604 :
3605 : // NOT([10,20]) ==> [-MIN,9][21,MAX].
3606 4 : r0 = r1 = range_int (10, 20);
3607 4 : r2 = int_range<1> (integer_type_node, minint, INT(9));
3608 4 : r2.union_ (int_range<1> (integer_type_node, INT(21), maxint));
3609 4 : ASSERT_FALSE (r2.undefined_p ());
3610 4 : res = r1.invert ();
3611 4 : ASSERT_TRUE (res && r1 == r2);
3612 : // Test that NOT(NOT(x)) == x.
3613 4 : res = r2.invert ();
3614 4 : ASSERT_TRUE (res && r0 == r2);
3615 :
3616 : // Test that booleans and their inverse work as expected.
3617 4 : r0.set_zero (boolean_type_node);
3618 4 : ASSERT_TRUE (r0 == range_false ());
3619 4 : res = r0.invert ();
3620 4 : ASSERT_TRUE (res && r0 == range_true ());
3621 :
3622 : // Make sure NULL and non-NULL of pointer types work, and that
3623 : // inverses of them are consistent.
3624 4 : tree voidp = build_pointer_type (void_type_node);
3625 4 : prange p0;
3626 4 : p0.set_zero (voidp);
3627 4 : prange p1 = p0;
3628 4 : res = p0.invert ();
3629 4 : ASSERT_TRUE (res);
3630 4 : res = p0.invert ();
3631 4 : ASSERT_TRUE (res && p0 == p1);
3632 :
3633 : // The intersection of:
3634 : // [0, +INF] MASK 0xff..00 VALUE 0xf8
3635 : // [0, +INF] MASK 0xff..00 VALUE 0x00
3636 : // is [0, +INF] MASK 0xff..ff VALUE 0x00, which is VARYING.
3637 : // Test that we normalized to VARYING.
3638 4 : unsigned prec = TYPE_PRECISION (voidp);
3639 4 : p0.set_varying (voidp);
3640 4 : wide_int mask = wi::mask (8, true, prec);
3641 4 : wide_int value = wi::uhwi (0xf8, prec);
3642 4 : irange_bitmask bm (wi::uhwi (0xf8, prec), mask);
3643 4 : p0.update_bitmask (bm);
3644 4 : p1.set_varying (voidp);
3645 4 : bm = irange_bitmask (wi::zero (prec), mask);
3646 4 : p1.update_bitmask (bm);
3647 4 : p0.intersect (p1);
3648 :
3649 : // [10,20] U [15, 30] => [10, 30].
3650 4 : r0 = range_int (10, 20);
3651 4 : r1 = range_int (15, 30);
3652 4 : r0.union_ (r1);
3653 4 : ASSERT_TRUE (r0 == range_int (10, 30));
3654 :
3655 : // [15,40] U [] => [15,40].
3656 4 : r0 = range_int (15, 40);
3657 4 : r1.set_undefined ();
3658 4 : r0.union_ (r1);
3659 4 : ASSERT_TRUE (r0 == range_int (15, 40));
3660 :
3661 : // [10,20] U [10,10] => [10,20].
3662 4 : r0 = range_int (10, 20);
3663 4 : r1 = range_int (10, 10);
3664 4 : r0.union_ (r1);
3665 4 : ASSERT_TRUE (r0 == range_int (10, 20));
3666 :
3667 : // [10,20] U [9,9] => [9,20].
3668 4 : r0 = range_int (10, 20);
3669 4 : r1 = range_int (9, 9);
3670 4 : r0.union_ (r1);
3671 4 : ASSERT_TRUE (r0 == range_int (9, 20));
3672 :
3673 : // [10,20] ^ [15,30] => [15,20].
3674 4 : r0 = range_int (10, 20);
3675 4 : r1 = range_int (15, 30);
3676 4 : r0.intersect (r1);
3677 4 : ASSERT_TRUE (r0 == range_int (15, 20));
3678 :
3679 : // Test the internal sanity of wide_int's wrt HWIs.
3680 4 : ASSERT_TRUE (wi::max_value (TYPE_PRECISION (boolean_type_node),
3681 : TYPE_SIGN (boolean_type_node))
3682 : == wi::uhwi (1, TYPE_PRECISION (boolean_type_node)));
3683 :
3684 : // Test zero_p().
3685 4 : r0 = range_int (0, 0);
3686 4 : ASSERT_TRUE (r0.zero_p ());
3687 :
3688 : // Test contains_zero_p().
3689 4 : r0 = range_int (0, 0);
3690 4 : res = r0.invert ();
3691 4 : ASSERT_TRUE (res);
3692 4 : ASSERT_FALSE (r0.contains_zero_p ());
3693 :
3694 : // r0 = ~[1,1]
3695 4 : r0 = range_int (1, 1, VR_ANTI_RANGE);
3696 : // r1 = ~[3,3]
3697 4 : r1 = range_int (3, 3, VR_ANTI_RANGE);
3698 :
3699 : // vv = [0,0][2,2][4, MAX]
3700 4 : int_range<3> vv = r0;
3701 4 : vv.intersect (r1);
3702 :
3703 4 : ASSERT_TRUE (vv.contains_p (UINT (2)));
3704 4 : ASSERT_TRUE (vv.num_pairs () == 3);
3705 :
3706 4 : r0 = range_int (1, 1);
3707 : // And union it with [0,0][2,2][4,MAX] multi range
3708 4 : r0.union_ (vv);
3709 : // The result should be [0,2][4,MAX], or ~[3,3] but it must contain 2
3710 4 : ASSERT_TRUE (r0.contains_p (INT (2)));
3711 4 : }
3712 :
3713 : static void
3714 4 : range_tests_nonzero_bits ()
3715 : {
3716 4 : int_range<8> r0, r1;
3717 :
3718 : // Adding nonzero bits to a varying drops the varying.
3719 4 : r0.set_varying (integer_type_node);
3720 4 : r0.set_nonzero_bits (INT (255));
3721 4 : ASSERT_TRUE (!r0.varying_p ());
3722 :
3723 : // Test contains_p with nonzero bits.
3724 4 : r0.set_zero (integer_type_node);
3725 4 : ASSERT_TRUE (r0.contains_p (INT (0)));
3726 4 : ASSERT_FALSE (r0.contains_p (INT (1)));
3727 4 : r0.set_nonzero_bits (INT (0xfe));
3728 4 : ASSERT_FALSE (r0.contains_p (INT (0x100)));
3729 4 : ASSERT_FALSE (r0.contains_p (INT (0x3)));
3730 :
3731 : // Union of nonzero bits.
3732 4 : r0.set_varying (integer_type_node);
3733 4 : r0.set_nonzero_bits (INT (0xf0));
3734 4 : r1.set_varying (integer_type_node);
3735 4 : r1.set_nonzero_bits (INT (0xf));
3736 4 : r0.union_ (r1);
3737 4 : ASSERT_TRUE (r0.get_nonzero_bits () == 0xff);
3738 :
3739 : // Intersect of nonzero bits.
3740 4 : r0 = range_int (0, 255);
3741 4 : r0.set_nonzero_bits (INT (0xfe));
3742 4 : r1.set_varying (integer_type_node);
3743 4 : r1.set_nonzero_bits (INT (0xf0));
3744 4 : r0.intersect (r1);
3745 4 : ASSERT_TRUE (r0.get_nonzero_bits () == 0xf0);
3746 :
3747 : // Intersect where the mask of nonzero bits is implicit from the range.
3748 4 : r0.set_varying (integer_type_node);
3749 4 : r1 = range_int (0, 255);
3750 4 : r0.intersect (r1);
3751 4 : ASSERT_TRUE (r0.get_nonzero_bits () == 0xff);
3752 :
3753 : // Test that setting a nonzero bit of 1 does not pessimize the range.
3754 4 : r0.set_zero (integer_type_node);
3755 4 : r0.set_nonzero_bits (INT (1));
3756 4 : ASSERT_TRUE (r0.zero_p ());
3757 :
3758 : // Now test that range bounds are snapped to match bitmask alignments.
3759 4 : test_irange_snap_bounds ();
3760 4 : }
3761 :
3762 : // Build an frange from string endpoints.
3763 :
3764 : static inline frange
3765 712 : frange_float (const char *lb, const char *ub, tree type = float_type_node)
3766 : {
3767 712 : REAL_VALUE_TYPE min, max;
3768 712 : gcc_assert (real_from_string (&min, lb) == 0);
3769 712 : gcc_assert (real_from_string (&max, ub) == 0);
3770 712 : return frange (type, min, max);
3771 : }
3772 :
3773 : // Build the REAL_VALUE_TYPE for the string S.
3774 :
3775 : static REAL_VALUE_TYPE
3776 304 : real_from_str (const char *s)
3777 : {
3778 304 : REAL_VALUE_TYPE r;
3779 304 : gcc_assert (real_from_string (&r, s) == 0);
3780 304 : return r;
3781 : }
3782 :
3783 : static void
3784 8 : range_tests_sub_ranges ()
3785 : {
3786 8 : frange r0, r1;
3787 :
3788 : // A union of two disjoint intervals keeps both.
3789 8 : r0 = frange_float ("3", "5");
3790 8 : r1 = frange_float ("10", "12");
3791 8 : r0.union_ (r1);
3792 8 : ASSERT_EQ (r0.num_pairs (), 2);
3793 8 : ASSERT_TRUE (r0.contains_p (real_from_str ("4")));
3794 8 : ASSERT_TRUE (r0.contains_p (real_from_str ("11")));
3795 8 : ASSERT_FALSE (r0.contains_p (real_from_str ("7")));
3796 :
3797 8 : REAL_VALUE_TYPE three = real_from_str ("3");
3798 8 : REAL_VALUE_TYPE twelve = real_from_str ("12");
3799 8 : ASSERT_TRUE (real_identical (&r0.lower_bound (), &three));
3800 8 : ASSERT_TRUE (real_identical (&r0.upper_bound (), &twelve));
3801 :
3802 : // Intersecting away one side leaves a single interval again.
3803 8 : r1 = frange_float ("0", "6");
3804 8 : r0.intersect (r1);
3805 8 : ASSERT_EQ (r0.num_pairs (), 1);
3806 8 : ASSERT_TRUE (r0.contains_p (real_from_str ("4")));
3807 8 : ASSERT_FALSE (r0.contains_p (real_from_str ("11")));
3808 :
3809 : // Overlapping intervals fuse rather than leave a gap.
3810 8 : r0 = frange_float ("3", "8");
3811 8 : r1 = frange_float ("5", "12");
3812 8 : r0.union_ (r1);
3813 8 : ASSERT_EQ (r0.num_pairs (), 1);
3814 8 : ASSERT_TRUE (r0.contains_p (real_from_str ("7")));
3815 :
3816 8 : if (frange::MAX_PAIRS == 2)
3817 : {
3818 : // When more pieces arrive than fit, the last slot swallows the tail:
3819 : // [0,1] stays and [3,4], [100,101] merge into [3,101].
3820 8 : r0 = frange_float ("0", "1");
3821 8 : r1 = frange_float ("100", "101");
3822 8 : r0.union_ (r1);
3823 8 : r1 = frange_float ("3", "4");
3824 8 : r0.union_ (r1);
3825 8 : ASSERT_EQ (r0.num_pairs (), 2);
3826 8 : ASSERT_TRUE (r0.contains_p (real_from_str ("50")));
3827 8 : ASSERT_TRUE (r0.contains_p (real_from_str ("3.5")));
3828 8 : ASSERT_TRUE (r0.contains_p (real_from_str ("100.5")));
3829 : }
3830 :
3831 : // Equality accounts for the sub-ranges.
3832 8 : r0 = frange_float ("3", "5");
3833 8 : r1 = frange_float ("10", "12");
3834 8 : r0.union_ (r1);
3835 8 : r1 = frange_float ("3", "12");
3836 8 : ASSERT_NE (r0, r1);
3837 :
3838 : // Intersecting every piece away, with the NAN cleared, leaves UNDEFINED.
3839 8 : r0 = frange_float ("3", "5");
3840 8 : r1 = frange_float ("10", "12");
3841 8 : r0.union_ (r1);
3842 8 : r0.clear_nan ();
3843 8 : r1 = frange_float ("20", "25");
3844 8 : r1.clear_nan ();
3845 8 : r0.intersect (r1);
3846 8 : ASSERT_TRUE (r0.undefined_p ());
3847 8 : }
3848 :
3849 : // Build a range that excludes the single point C.
3850 :
3851 : static frange
3852 112 : frange_float_excluding (const char *c)
3853 : {
3854 112 : REAL_VALUE_TYPE r = real_from_str (c);
3855 112 : frange f;
3856 112 : f.set (float_type_node, r, r, VR_ANTI_RANGE);
3857 112 : return f;
3858 : }
3859 :
3860 : static void
3861 8 : range_tests_excluding ()
3862 : {
3863 8 : frange r0, r1;
3864 :
3865 : // "x != 1.0" is two sub-ranges with 1.0 missing.
3866 8 : r0 = frange_float_excluding ("1.0");
3867 8 : ASSERT_FALSE (r0.varying_p ());
3868 8 : ASSERT_FALSE (r0.undefined_p ());
3869 8 : ASSERT_EQ (r0.num_pairs (), 2);
3870 8 : ASSERT_FALSE (r0.contains_p (real_from_str ("1.0")));
3871 8 : ASSERT_TRUE (r0.contains_p (real_from_str ("2.0")));
3872 8 : ASSERT_TRUE (r0.contains_p (real_from_str ("0.0")));
3873 8 : ASSERT_TRUE (r0.contains_p (real_from_str ("-1.0")));
3874 8 : ASSERT_FALSE (r0.singleton_p ());
3875 : // A NAN compares unequal to everything, so this says nothing about NANs.
3876 8 : if (HONOR_NANS (float_type_node))
3877 8 : ASSERT_TRUE (r0.maybe_isnan ());
3878 : // The extremes still span the domain.
3879 8 : REAL_VALUE_TYPE dom_min = frange_val_min (float_type_node);
3880 8 : REAL_VALUE_TYPE dom_max = frange_val_max (float_type_node);
3881 8 : ASSERT_TRUE (real_identical (&r0.lower_bound (), &dom_min));
3882 8 : ASSERT_TRUE (real_identical (&r0.upper_bound (), &dom_max));
3883 :
3884 : // Any constant, not just 0.0 or 1.0.
3885 8 : r0 = frange_float_excluding ("5.5");
3886 8 : ASSERT_EQ (r0.num_pairs (), 2);
3887 8 : ASSERT_FALSE (r0.contains_p (real_from_str ("5.5")));
3888 8 : ASSERT_TRUE (r0.contains_p (real_from_str ("5.4")));
3889 :
3890 : // "x != 1.0" met with [1.0, 1.0] is empty.
3891 8 : r0 = frange_float_excluding ("1.0");
3892 8 : r1 = frange_float ("1.0", "1.0");
3893 8 : r1.clear_nan ();
3894 8 : r0.intersect (r1);
3895 8 : ASSERT_TRUE (r0.undefined_p ());
3896 :
3897 : // Excluding a point outside a range changes nothing.
3898 8 : r0 = frange_float ("3.0", "5.0");
3899 8 : r0.clear_nan ();
3900 8 : r1 = frange_float_excluding ("1.0");
3901 8 : r0.intersect (r1);
3902 8 : ASSERT_EQ (r0.num_pairs (), 1);
3903 8 : ASSERT_TRUE (r0.contains_p (real_from_str ("3.0")));
3904 8 : ASSERT_TRUE (r0.contains_p (real_from_str ("5.0")));
3905 :
3906 : // Union puts the point back.
3907 8 : r0 = frange_float_excluding ("1.0");
3908 8 : r1 = frange_float ("1.0", "1.0");
3909 8 : r0.union_ (r1);
3910 8 : ASSERT_TRUE (r0.varying_p ());
3911 :
3912 : // Two different exclusions cannot both be held.
3913 8 : r0 = frange_float_excluding ("1.0");
3914 8 : r1 = frange_float_excluding ("2.0");
3915 8 : r0.union_ (r1);
3916 8 : ASSERT_TRUE (r0.varying_p ());
3917 :
3918 : // Nor can an intersection hold both.
3919 8 : r0 = frange_float_excluding ("1.0");
3920 8 : r1 = frange_float_excluding ("2.0");
3921 8 : r0.intersect (r1);
3922 8 : ASSERT_TRUE (r0.contains_p (real_from_str ("0.0")));
3923 8 : ASSERT_TRUE (r0.contains_p (real_from_str ("3.0")));
3924 :
3925 : // Equality accounts for the gap.
3926 8 : r0 = frange_float_excluding ("1.0");
3927 8 : r1 = frange_float_excluding ("2.0");
3928 8 : ASSERT_NE (r0, r1);
3929 8 : r1 = frange_float_excluding ("1.0");
3930 8 : ASSERT_EQ (r0, r1);
3931 8 : }
3932 :
3933 : static void
3934 8 : range_tests_sub_ranges_zero ()
3935 : {
3936 8 : frange r0, r1;
3937 :
3938 : // "x != 0.0" must exclude BOTH zeros, since -0.0 == 0.0 and so "x != 0.0" is
3939 : // false for either. The seam lands on the denormals either side of zero,
3940 : // which falls out of nextafter with no special case.
3941 8 : r0 = frange_float_excluding ("0.0");
3942 8 : ASSERT_EQ (r0.num_pairs (), 2);
3943 8 : ASSERT_FALSE (r0.contains_p (dconst0));
3944 8 : ASSERT_FALSE (r0.contains_p (dconstm0));
3945 8 : ASSERT_TRUE (r0.contains_p (real_from_str ("1.0")));
3946 8 : ASSERT_TRUE (r0.contains_p (real_from_str ("-1.0")));
3947 :
3948 : // Excluding zero from [-0.0, 5.0] eats the lower end entirely.
3949 8 : r0.set_nonzero (float_type_node);
3950 8 : ASSERT_FALSE (r0.contains_zero_p ());
3951 8 : ASSERT_FALSE (r0.contains_p (dconst0));
3952 8 : ASSERT_FALSE (r0.contains_p (dconstm0));
3953 :
3954 : // A NAN is not a zero, so clearing the NAN leaves the range nonzero.
3955 8 : r0.clear_nan ();
3956 8 : ASSERT_FALSE (r0.contains_zero_p ());
3957 :
3958 : // A range that avoids zero does not contain zero.
3959 8 : r0 = frange_float ("1.0", "10.0");
3960 8 : ASSERT_FALSE (r0.contains_zero_p ());
3961 :
3962 : // Excluding zero from [-0.0, 5.0] leaves (0, 5], which does not contain zero.
3963 8 : r0 = frange_float ("-0.0", "5.0");
3964 8 : r0.clear_nan ();
3965 8 : r1 = frange_float_excluding ("0.0");
3966 8 : r0.intersect (r1);
3967 8 : ASSERT_EQ (r0.num_pairs (), 1);
3968 8 : ASSERT_FALSE (r0.contains_zero_p ());
3969 8 : ASSERT_FALSE (r0.contains_p (dconst0));
3970 8 : ASSERT_FALSE (r0.contains_p (dconstm0));
3971 8 : ASSERT_TRUE (r0.contains_p (real_from_str ("5.0")));
3972 :
3973 : // -0.0 and +0.0 abut: nothing is representable between them, so the two
3974 : // halves fuse into one interval rather than leaving a gap.
3975 8 : r0 = frange_float ("-5", "-0.0");
3976 8 : r0.clear_nan ();
3977 8 : r1 = frange_float ("0.0", "5");
3978 8 : r1.clear_nan ();
3979 8 : r0.union_ (r1);
3980 8 : ASSERT_EQ (r0.num_pairs (), 1);
3981 8 : ASSERT_TRUE (r0.contains_p (dconst0));
3982 8 : ASSERT_TRUE (r0.contains_p (dconstm0));
3983 8 : }
3984 :
3985 : // A cached frange must come back with every sub-range intact.
3986 :
3987 : static void
3988 8 : range_tests_sub_ranges_storage ()
3989 : {
3990 8 : vrange_allocator alloc (false);
3991 :
3992 : // A two-piece range comes back as two pieces, unchanged.
3993 8 : frange r0 = frange_float ("3", "5");
3994 8 : frange r1 = frange_float ("10", "12");
3995 8 : r0.union_ (r1);
3996 8 : ASSERT_EQ (r0.num_pairs (), 2);
3997 :
3998 8 : vrange_storage *slot = alloc.clone (r0);
3999 8 : frange r2;
4000 8 : slot->get_vrange (r2, float_type_node);
4001 8 : ASSERT_EQ (r2.num_pairs (), 2);
4002 8 : ASSERT_EQ (r2, r0);
4003 8 : }
4004 :
4005 : // NANs and sub-ranges: unioning in a NAN keeps the intervals, while
4006 : // intersecting the intervals away collapses to a plain NAN with a single
4007 : // pair.
4008 :
4009 : static void
4010 4 : range_tests_sub_ranges_nan ()
4011 : {
4012 4 : frange r0, r1;
4013 :
4014 : // Union with a NAN keeps both intervals and gains the NAN.
4015 4 : r0 = frange_float ("3", "5");
4016 4 : r1 = frange_float ("10", "12");
4017 4 : r0.union_ (r1);
4018 4 : r0.clear_nan ();
4019 4 : r1.set_nan (float_type_node);
4020 4 : r0.union_ (r1);
4021 4 : ASSERT_EQ (r0.num_pairs (), 2);
4022 8 : ASSERT_TRUE (r0.maybe_isnan ());
4023 :
4024 : // Intersecting the intervals away leaves just the NAN.
4025 4 : r0 = frange_float ("3", "5");
4026 4 : r1 = frange_float ("10", "12");
4027 4 : r0.union_ (r1);
4028 4 : r1 = frange_float ("20", "25");
4029 4 : r0.intersect (r1);
4030 4 : ASSERT_TRUE (r0.known_isnan ());
4031 4 : ASSERT_EQ (r0.num_pairs (), 1);
4032 4 : }
4033 :
4034 : static void
4035 4 : range_tests_nan ()
4036 : {
4037 4 : frange r0, r1;
4038 4 : REAL_VALUE_TYPE q, r;
4039 4 : bool signbit;
4040 :
4041 : // Equal ranges but with differing NAN bits are not equal.
4042 4 : if (HONOR_NANS (float_type_node))
4043 : {
4044 4 : r1 = frange_float ("10", "12");
4045 4 : r0 = r1;
4046 4 : ASSERT_EQ (r0, r1);
4047 4 : r0.clear_nan ();
4048 4 : ASSERT_NE (r0, r1);
4049 4 : r0.update_nan ();
4050 4 : ASSERT_EQ (r0, r1);
4051 :
4052 : // [10, 20] NAN ^ [30, 40] NAN = NAN.
4053 4 : r0 = frange_float ("10", "20");
4054 4 : r1 = frange_float ("30", "40");
4055 4 : r0.intersect (r1);
4056 4 : ASSERT_TRUE (r0.known_isnan ());
4057 :
4058 : // [3,5] U [5,10] NAN = ... NAN
4059 4 : r0 = frange_float ("3", "5");
4060 4 : r0.clear_nan ();
4061 4 : r1 = frange_float ("5", "10");
4062 4 : r0.union_ (r1);
4063 8 : ASSERT_TRUE (r0.maybe_isnan ());
4064 : }
4065 :
4066 : // [5,6] U NAN = [5,6] NAN.
4067 4 : r0 = frange_float ("5", "6");
4068 4 : r0.clear_nan ();
4069 4 : r1.set_nan (float_type_node);
4070 4 : r0.union_ (r1);
4071 4 : real_from_string (&q, "5");
4072 4 : real_from_string (&r, "6");
4073 4 : ASSERT_TRUE (real_identical (&q, &r0.lower_bound ()));
4074 4 : ASSERT_TRUE (real_identical (&r, &r0.upper_bound ()));
4075 8 : ASSERT_TRUE (r0.maybe_isnan ());
4076 :
4077 : // NAN U NAN = NAN
4078 4 : r0.set_nan (float_type_node);
4079 4 : r1.set_nan (float_type_node);
4080 4 : r0.union_ (r1);
4081 4 : ASSERT_TRUE (r0.known_isnan ());
4082 :
4083 : // [INF, INF] NAN ^ NAN = NAN
4084 4 : r0.set_nan (float_type_node);
4085 4 : r1 = frange_float ("+Inf", "+Inf");
4086 4 : if (!HONOR_NANS (float_type_node))
4087 0 : r1.update_nan ();
4088 4 : r0.intersect (r1);
4089 4 : ASSERT_TRUE (r0.known_isnan ());
4090 :
4091 : // NAN ^ NAN = NAN
4092 4 : r0.set_nan (float_type_node);
4093 4 : r1.set_nan (float_type_node);
4094 4 : r0.intersect (r1);
4095 4 : ASSERT_TRUE (r0.known_isnan ());
4096 :
4097 : // +NAN ^ -NAN = UNDEFINED
4098 4 : r0.set_nan (float_type_node, false);
4099 4 : r1.set_nan (float_type_node, true);
4100 4 : r0.intersect (r1);
4101 4 : ASSERT_TRUE (r0.undefined_p ());
4102 :
4103 : // VARYING ^ NAN = NAN.
4104 4 : r0.set_nan (float_type_node);
4105 4 : r1.set_varying (float_type_node);
4106 4 : r0.intersect (r1);
4107 4 : ASSERT_TRUE (r0.known_isnan ());
4108 :
4109 : // [3,4] ^ NAN = UNDEFINED.
4110 4 : r0 = frange_float ("3", "4");
4111 4 : r0.clear_nan ();
4112 4 : r1.set_nan (float_type_node);
4113 4 : r0.intersect (r1);
4114 4 : ASSERT_TRUE (r0.undefined_p ());
4115 :
4116 : // [-3, 5] ^ NAN = UNDEFINED
4117 4 : r0 = frange_float ("-3", "5");
4118 4 : r0.clear_nan ();
4119 4 : r1.set_nan (float_type_node);
4120 4 : r0.intersect (r1);
4121 4 : ASSERT_TRUE (r0.undefined_p ());
4122 :
4123 : // Setting the NAN bit to yes does not make us a known NAN.
4124 4 : r0.set_varying (float_type_node);
4125 4 : r0.update_nan ();
4126 4 : ASSERT_FALSE (r0.known_isnan ());
4127 :
4128 : // NAN is in a VARYING.
4129 4 : r0.set_varying (float_type_node);
4130 4 : real_nan (&r, "", 1, TYPE_MODE (float_type_node));
4131 4 : REAL_VALUE_TYPE nan = r;
4132 4 : ASSERT_TRUE (r0.contains_p (nan));
4133 :
4134 : // -NAN is in a VARYING.
4135 4 : r0.set_varying (float_type_node);
4136 4 : q = real_value_negate (&r);
4137 4 : REAL_VALUE_TYPE neg_nan = q;
4138 4 : ASSERT_TRUE (r0.contains_p (neg_nan));
4139 :
4140 : // Clearing the NAN on a [] NAN is the empty set.
4141 4 : r0.set_nan (float_type_node);
4142 4 : r0.clear_nan ();
4143 4 : ASSERT_TRUE (r0.undefined_p ());
4144 :
4145 : // [10,20] NAN ^ [21,25] NAN = [NAN]
4146 4 : r0 = frange_float ("10", "20");
4147 4 : r0.update_nan ();
4148 4 : r1 = frange_float ("21", "25");
4149 4 : r1.update_nan ();
4150 4 : r0.intersect (r1);
4151 4 : ASSERT_TRUE (r0.known_isnan ());
4152 :
4153 : // NAN U [5,6] should be [5,6] +-NAN.
4154 4 : r0.set_nan (float_type_node);
4155 4 : r1 = frange_float ("5", "6");
4156 4 : r1.clear_nan ();
4157 4 : r0.union_ (r1);
4158 4 : real_from_string (&q, "5");
4159 4 : real_from_string (&r, "6");
4160 4 : ASSERT_TRUE (real_identical (&q, &r0.lower_bound ()));
4161 4 : ASSERT_TRUE (real_identical (&r, &r0.upper_bound ()));
4162 4 : ASSERT_TRUE (!r0.signbit_p (signbit));
4163 8 : ASSERT_TRUE (r0.maybe_isnan ());
4164 :
4165 : // NAN U NAN shouldn't change anything.
4166 4 : r0.set_nan (float_type_node);
4167 4 : r1.set_nan (float_type_node);
4168 4 : ASSERT_FALSE (r0.union_ (r1));
4169 :
4170 : // [3,5] NAN U NAN shouldn't change anything.
4171 4 : r0 = frange_float ("3", "5");
4172 4 : r1.set_nan (float_type_node);
4173 4 : ASSERT_FALSE (r0.union_ (r1));
4174 :
4175 : // [3,5] U NAN *does* trigger a change.
4176 4 : r0 = frange_float ("3", "5");
4177 4 : r0.clear_nan ();
4178 4 : r1.set_nan (float_type_node);
4179 4 : ASSERT_TRUE (r0.union_ (r1));
4180 4 : }
4181 :
4182 : static void
4183 8 : range_tests_signed_zeros ()
4184 : {
4185 8 : REAL_VALUE_TYPE zero = dconst0;
4186 8 : REAL_VALUE_TYPE neg_zero = zero;
4187 8 : neg_zero.sign = 1;
4188 8 : frange r0, r1;
4189 8 : bool signbit;
4190 :
4191 : // [0,0] contains [0,0] but not [-0,-0] and vice versa.
4192 8 : r0 = frange_float ("0.0", "0.0");
4193 8 : r1 = frange_float ("-0.0", "-0.0");
4194 8 : ASSERT_TRUE (r0.contains_p (zero));
4195 8 : ASSERT_TRUE (!r0.contains_p (neg_zero));
4196 8 : ASSERT_TRUE (r1.contains_p (neg_zero));
4197 8 : ASSERT_TRUE (!r1.contains_p (zero));
4198 :
4199 : // Test contains_p() when we know the sign of the zero.
4200 8 : r0 = frange_float ("0.0", "0.0");
4201 8 : ASSERT_TRUE (r0.contains_p (zero));
4202 8 : ASSERT_FALSE (r0.contains_p (neg_zero));
4203 8 : r0 = frange_float ("-0.0", "-0.0");
4204 8 : ASSERT_TRUE (r0.contains_p (neg_zero));
4205 8 : ASSERT_FALSE (r0.contains_p (zero));
4206 :
4207 8 : r0 = frange_float ("-0.0", "0.0");
4208 8 : ASSERT_TRUE (r0.contains_p (neg_zero));
4209 8 : ASSERT_TRUE (r0.contains_p (zero));
4210 :
4211 8 : r0 = frange_float ("-3", "5");
4212 8 : ASSERT_TRUE (r0.contains_p (neg_zero));
4213 8 : ASSERT_TRUE (r0.contains_p (zero));
4214 :
4215 : // The intersection of zeros that differ in sign is a NAN (or
4216 : // undefined if not honoring NANs).
4217 8 : r0 = frange_float ("-0.0", "-0.0");
4218 8 : r1 = frange_float ("0.0", "0.0");
4219 8 : r0.intersect (r1);
4220 8 : if (HONOR_NANS (float_type_node))
4221 4 : ASSERT_TRUE (r0.known_isnan ());
4222 : else
4223 4 : ASSERT_TRUE (r0.undefined_p ());
4224 :
4225 : // The union of zeros that differ in sign is a zero with unknown sign.
4226 8 : r0 = frange_float ("0.0", "0.0");
4227 8 : r1 = frange_float ("-0.0", "-0.0");
4228 8 : r0.union_ (r1);
4229 8 : ASSERT_TRUE (r0.zero_p () && !r0.signbit_p (signbit));
4230 :
4231 : // [-0, +0] has an unknown sign.
4232 8 : r0 = frange_float ("-0.0", "0.0");
4233 8 : ASSERT_TRUE (r0.zero_p () && !r0.signbit_p (signbit));
4234 :
4235 : // [-0, +0] ^ [0, 0] is [0, 0]
4236 8 : r0 = frange_float ("-0.0", "0.0");
4237 8 : r1 = frange_float ("0.0", "0.0");
4238 8 : r0.intersect (r1);
4239 8 : ASSERT_TRUE (r0.zero_p ());
4240 :
4241 8 : r0 = frange_float ("+0", "5");
4242 8 : r0.clear_nan ();
4243 8 : ASSERT_TRUE (r0.signbit_p (signbit) && !signbit);
4244 :
4245 8 : r0 = frange_float ("-0", "5");
4246 8 : r0.clear_nan ();
4247 8 : ASSERT_TRUE (!r0.signbit_p (signbit));
4248 :
4249 8 : r0 = frange_float ("-0", "10");
4250 8 : r1 = frange_float ("0", "5");
4251 8 : r0.intersect (r1);
4252 8 : ASSERT_TRUE (real_iszero (&r0.lower_bound (), false));
4253 :
4254 8 : r0 = frange_float ("-0", "5");
4255 8 : r1 = frange_float ("0", "5");
4256 8 : r0.union_ (r1);
4257 8 : ASSERT_TRUE (real_iszero (&r0.lower_bound (), true));
4258 :
4259 8 : r0 = frange_float ("-5", "-0");
4260 8 : r0.update_nan ();
4261 8 : r1 = frange_float ("0", "0");
4262 8 : r1.update_nan ();
4263 8 : r0.intersect (r1);
4264 8 : if (HONOR_NANS (float_type_node))
4265 4 : ASSERT_TRUE (r0.known_isnan ());
4266 : else
4267 4 : ASSERT_TRUE (r0.undefined_p ());
4268 :
4269 8 : r0.set_nonnegative (float_type_node);
4270 8 : if (HONOR_NANS (float_type_node))
4271 8 : ASSERT_TRUE (r0.maybe_isnan ());
4272 :
4273 : // Numbers containing zero should have an unknown SIGNBIT.
4274 8 : r0 = frange_float ("0", "10");
4275 8 : r0.clear_nan ();
4276 8 : ASSERT_TRUE (r0.signbit_p (signbit) && !signbit);
4277 8 : }
4278 :
4279 : static void
4280 8 : range_tests_signbit ()
4281 : {
4282 8 : frange r0, r1;
4283 8 : bool signbit;
4284 :
4285 : // Negative numbers should have the SIGNBIT set.
4286 8 : r0 = frange_float ("-5", "-1");
4287 8 : r0.clear_nan ();
4288 8 : ASSERT_TRUE (r0.signbit_p (signbit) && signbit);
4289 : // Positive numbers should have the SIGNBIT clear.
4290 8 : r0 = frange_float ("1", "10");
4291 8 : r0.clear_nan ();
4292 8 : ASSERT_TRUE (r0.signbit_p (signbit) && !signbit);
4293 : // Numbers spanning both positive and negative should have an
4294 : // unknown SIGNBIT.
4295 8 : r0 = frange_float ("-10", "10");
4296 8 : r0.clear_nan ();
4297 8 : ASSERT_TRUE (!r0.signbit_p (signbit));
4298 8 : r0.set_varying (float_type_node);
4299 8 : ASSERT_TRUE (!r0.signbit_p (signbit));
4300 8 : }
4301 :
4302 : static void
4303 8 : range_tests_flush_denormals ()
4304 : {
4305 : // We need -0.0 to exist for any of this to mean anything.
4306 32 : if (!MODE_HAS_SIGNED_ZEROS (TYPE_MODE (float_type_node)))
4307 0 : return;
4308 :
4309 8 : int save_flag = flag_signed_zeros;
4310 8 : flag_signed_zeros = 0;
4311 :
4312 : // Flushing a positive denormal lower bound to zero must canonicalize that
4313 : // zero to -0.0 to agree with set().
4314 8 : frange flushed = frange_float ("1e-40", "5");
4315 8 : flushed.clear_nan ();
4316 8 : flushed.flush_denormals_to_zero ();
4317 :
4318 8 : frange built = frange_float ("0", "5");
4319 8 : built.clear_nan ();
4320 :
4321 8 : ASSERT_TRUE (flushed == built);
4322 8 : ASSERT_TRUE (flushed.contains_p (dconstm0));
4323 8 : ASSERT_TRUE (flushed.contains_p (dconst0));
4324 :
4325 8 : flag_signed_zeros = save_flag;
4326 8 : }
4327 :
4328 : static void
4329 8 : range_tests_floats ()
4330 : {
4331 8 : frange r0, r1;
4332 :
4333 8 : if (HONOR_NANS (float_type_node))
4334 : {
4335 4 : range_tests_nan ();
4336 4 : range_tests_sub_ranges_nan ();
4337 : }
4338 8 : range_tests_signbit ();
4339 8 : range_tests_flush_denormals ();
4340 8 : range_tests_sub_ranges ();
4341 8 : range_tests_sub_ranges_storage ();
4342 8 : range_tests_excluding ();
4343 :
4344 8 : if (HONOR_SIGNED_ZEROS (float_type_node))
4345 : {
4346 8 : range_tests_signed_zeros ();
4347 8 : range_tests_sub_ranges_zero ();
4348 : }
4349 :
4350 : // A range of [-INF,+INF] is actually VARYING if no other properties
4351 : // are set.
4352 8 : r0 = frange_float ("-Inf", "+Inf");
4353 8 : ASSERT_TRUE (r0.varying_p ());
4354 : // ...unless it has some special property...
4355 8 : if (HONOR_NANS (r0.type ()))
4356 : {
4357 4 : r0.clear_nan ();
4358 4 : ASSERT_FALSE (r0.varying_p ());
4359 : }
4360 :
4361 : // For most architectures, where float and double are different
4362 : // sizes, having the same endpoints does not necessarily mean the
4363 : // ranges are equal.
4364 8 : if (!types_compatible_p (float_type_node, double_type_node))
4365 : {
4366 8 : r0 = frange_float ("3.0", "3.0", float_type_node);
4367 8 : r1 = frange_float ("3.0", "3.0", double_type_node);
4368 8 : ASSERT_NE (r0, r1);
4369 : }
4370 :
4371 : // [3,5] U [10,12] = [3,5][10,12]
4372 8 : r0 = frange_float ("3", "5");
4373 8 : r1 = frange_float ("10", "12");
4374 8 : r0.union_ (r1);
4375 8 : ASSERT_EQ (r0.num_pairs (), 2);
4376 8 : ASSERT_NE (r0, frange_float ("3", "12"));
4377 :
4378 : // [5,10] U [4,8] = [4,10]
4379 8 : r0 = frange_float ("5", "10");
4380 8 : r1 = frange_float ("4", "8");
4381 8 : r0.union_ (r1);
4382 8 : ASSERT_EQ (r0, frange_float ("4", "10"));
4383 :
4384 : // [3,5] U [4,10] = [3,10]
4385 8 : r0 = frange_float ("3", "5");
4386 8 : r1 = frange_float ("4", "10");
4387 8 : r0.union_ (r1);
4388 8 : ASSERT_EQ (r0, frange_float ("3", "10"));
4389 :
4390 : // [4,10] U [5,11] = [4,11]
4391 8 : r0 = frange_float ("4", "10");
4392 8 : r1 = frange_float ("5", "11");
4393 8 : r0.union_ (r1);
4394 8 : ASSERT_EQ (r0, frange_float ("4", "11"));
4395 :
4396 : // [3,12] ^ [10,12] = [10,12].
4397 8 : r0 = frange_float ("3", "12");
4398 8 : r1 = frange_float ("10", "12");
4399 8 : r0.intersect (r1);
4400 8 : ASSERT_EQ (r0, frange_float ("10", "12"));
4401 :
4402 : // [10,12] ^ [11,11] = [11,11]
4403 8 : r0 = frange_float ("10", "12");
4404 8 : r1 = frange_float ("11", "11");
4405 8 : r0.intersect (r1);
4406 8 : ASSERT_EQ (r0, frange_float ("11", "11"));
4407 :
4408 : // [10,20] ^ [5,15] = [10,15]
4409 8 : r0 = frange_float ("10", "20");
4410 8 : r1 = frange_float ("5", "15");
4411 8 : r0.intersect (r1);
4412 8 : ASSERT_EQ (r0, frange_float ("10", "15"));
4413 :
4414 : // [10,20] ^ [15,25] = [15,20]
4415 8 : r0 = frange_float ("10", "20");
4416 8 : r1 = frange_float ("15", "25");
4417 8 : r0.intersect (r1);
4418 8 : ASSERT_EQ (r0, frange_float ("15", "20"));
4419 :
4420 : // [10,20] ^ [21,25] = []
4421 8 : r0 = frange_float ("10", "20");
4422 8 : r0.clear_nan ();
4423 8 : r1 = frange_float ("21", "25");
4424 8 : r1.clear_nan ();
4425 8 : r0.intersect (r1);
4426 8 : ASSERT_TRUE (r0.undefined_p ());
4427 :
4428 8 : if (HONOR_INFINITIES (float_type_node))
4429 : {
4430 : // Make sure [-Inf, -Inf] doesn't get normalized.
4431 4 : r0 = frange_float ("-Inf", "-Inf");
4432 4 : ASSERT_TRUE (real_isinf (&r0.lower_bound (), true));
4433 4 : ASSERT_TRUE (real_isinf (&r0.upper_bound (), true));
4434 : }
4435 :
4436 : // Test that reading back a global range yields the same result as
4437 : // what we wrote into it.
4438 8 : tree ssa = make_temp_ssa_name (float_type_node, NULL, "blah");
4439 8 : r0.set_varying (float_type_node);
4440 8 : r0.clear_nan ();
4441 8 : set_range_info (ssa, r0);
4442 8 : get_global_range_query ()->range_of_expr (r1, ssa);
4443 8 : ASSERT_EQ (r0, r1);
4444 8 : }
4445 :
4446 : // Run floating range tests for various combinations of NAN and INF
4447 : // support.
4448 :
4449 : static void
4450 4 : range_tests_floats_various ()
4451 : {
4452 4 : int save_finite_math_only = flag_finite_math_only;
4453 :
4454 : // Test -ffinite-math-only.
4455 4 : flag_finite_math_only = 1;
4456 4 : range_tests_floats ();
4457 : // Test -fno-finite-math-only.
4458 4 : flag_finite_math_only = 0;
4459 4 : range_tests_floats ();
4460 :
4461 4 : flag_finite_math_only = save_finite_math_only;
4462 4 : }
4463 :
4464 : void
4465 4 : range_tests ()
4466 : {
4467 4 : range_tests_irange3 ();
4468 4 : range_tests_int_range_max ();
4469 4 : range_tests_strict_enum ();
4470 4 : range_tests_nonzero_bits ();
4471 4 : range_tests_floats_various ();
4472 4 : range_tests_misc ();
4473 4 : }
4474 :
4475 : } // namespace selftest
4476 :
4477 : #endif // CHECKING_P
|
