Line data Source code
1 : /* Support routines for value ranges.
2 : Copyright (C) 2019-2026 Free Software Foundation, Inc.
3 : Major hacks by Aldy Hernandez <aldyh@redhat.com> and
4 : Andrew MacLeod <amacleod@redhat.com>.
5 :
6 : This file is part of GCC.
7 :
8 : GCC is free software; you can redistribute it and/or modify
9 : it under the terms of the GNU General Public License as published by
10 : the Free Software Foundation; either version 3, or (at your option)
11 : any later version.
12 :
13 : GCC is distributed in the hope that it will be useful,
14 : but WITHOUT ANY WARRANTY; without even the implied warranty of
15 : MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 : GNU General Public License for more details.
17 :
18 : You should have received a copy of the GNU General Public License
19 : along with GCC; see the file COPYING3. If not see
20 : <http://www.gnu.org/licenses/>. */
21 :
22 : #include "config.h"
23 : #include "system.h"
24 : #include "coretypes.h"
25 : #include "backend.h"
26 : #include "tree.h"
27 : #include "gimple.h"
28 : #include "ssa.h"
29 : #include "tree-pretty-print.h"
30 : #include "value-range-pretty-print.h"
31 : #include "fold-const.h"
32 : #include "gimple-range.h"
33 : #include "tree-dfa.h"
34 : #include "tree-affine.h"
35 :
36 : // Return the bitmask inherent in a range : TYPE [MIN, MAX].
37 : // This used to be get_bitmask_from_range ().
38 :
39 1165787423 : irange_bitmask::irange_bitmask (tree type,
40 1165787423 : const wide_int &min, const wide_int &max)
41 : {
42 1165787423 : unsigned prec = TYPE_PRECISION (type);
43 : // All the bits of a singleton are known.
44 1165787423 : if (min == max)
45 : {
46 155051007 : m_mask = wi::zero (prec);
47 155051007 : m_value = min;
48 : }
49 : else
50 : {
51 1010736416 : wide_int xorv = min ^ max;
52 : // Mask will have leading zeros for all leading bits that are
53 : // common, both zeros and ones.
54 1010736416 : m_mask = wi::mask (prec - wi::clz (xorv), false, prec);
55 : // Now set value to those bits which are known, and zero the rest.
56 1010747032 : m_value = ~m_mask & min;
57 1010736416 : }
58 1165787423 : }
59 :
60 : // Return a range in R of TYPE for this bitmask which encompasses
61 : // a set of valid values which are allowable for this bitmask/value
62 : // combination. If false is returned, no range was set.
63 :
64 : bool
65 121294769 : irange_bitmask::range_from_mask (irange &r, tree type) const
66 : {
67 121294769 : if (unknown_p ())
68 : return false;
69 :
70 242467828 : gcc_checking_assert ((value () & mask ()) == 0);
71 121233592 : unsigned popcount = wi::popcount (mask ());
72 :
73 : // For 0, 1 or 2 bits set, create a range with only the allowed values.
74 121233592 : if (popcount <= 2)
75 : {
76 : // VALUE is always a valid range.
77 23663788 : r.set (type, value (), value ());
78 : // If there are bits in mask, (VALUE | MASK) is also valid.
79 23663747 : if (popcount >= 1)
80 11133253 : r.union_ (int_range<1> (type, value () | mask (), value () | mask ()));
81 : // If there are 2 bits set, add the other 2 possible values.
82 11133173 : if (popcount == 2)
83 : {
84 : // Extract the two 1-bit masks into lb and ub.
85 4632765 : wide_int lb = mask () & -mask (); // Lowest set bit.
86 4632765 : wide_int ub = mask () & (mask () - 1); // The other bit.
87 4632765 : r.union_ (int_range<1> (type, value () | lb, value () | lb));
88 4632765 : r.union_ (int_range<1> (type, value () | ub, value () | ub));
89 4632765 : }
90 23663747 : return true;
91 : }
92 :
93 : // Otherwise, calculate the valid range allowed by the bitmask.
94 97569845 : int prec = TYPE_PRECISION (type);
95 97570448 : wide_int ub = mask () | value ();
96 97569845 : wide_int sign_bit = wi::one (prec) << (prec - 1);
97 97569845 : wide_int sign_mask = mask () & sign_bit;
98 97569845 : wide_int sign_value = value () & sign_bit;
99 : // Create a lower and upper bound.
100 : // If unsigned, or the sign is known to be positive, create [lb, ub]
101 97569845 : if (TYPE_SIGN (type) == UNSIGNED || (sign_mask == 0 && sign_value == 0))
102 90540638 : r.set (type, value (), mask () | value ());
103 : // If the sign bit is KNOWN to be 1, we have a completely negative range.
104 7031499 : else if (sign_mask == 0 && sign_value != 0)
105 678428 : r.set (type, value (), value () | (mask () & ~sign_bit));
106 : else
107 : {
108 : // Otherwise there are 2 ranges, a negative and positive interval.
109 6353101 : wide_int neg_base = value () | sign_bit;
110 6353126 : wide_int pos_mask = mask () & ~sign_bit;
111 6353101 : r.set (type, neg_base , neg_base | pos_mask);
112 6353176 : r.union_ (int_range<1> (type, value (), value () | pos_mask));
113 6353126 : }
114 :
115 : // If the mask doesn't have a trailing zero, there is nothing else to filter.
116 97569845 : int z = wi::ctz (mask ());
117 97569845 : if (z == 0)
118 : return true;
119 :
120 : // Remove the [0, X] values which the trailing-zero mask rules out.
121 : // For example, if z == 4, the mask is 0xFFF0, and the lowest 4 bits
122 : // define the range [0, 15]. Only (value & low_mask) is allowed.
123 30074480 : ub = (wi::one (prec) << z) - 1; // Upper bound of range.
124 30074461 : int_range<4> mask_range (type, wi::zero (prec), ub);
125 : // Remove the valid value from the excluded range and form an anti-range.
126 30074461 : wide_int allow = value () & ub;
127 30074461 : mask_range.intersect (int_range<2> (type, allow, allow, VR_ANTI_RANGE));
128 30074461 : mask_range.invert ();
129 30074461 : r.intersect (mask_range);
130 :
131 30074461 : if (TYPE_SIGN (type) == SIGNED)
132 : {
133 : // For signed negative values, find the lowest value with trailing zeros.
134 : // This forms a range such as [-512, -1] for z=9.
135 11450055 : wide_int lb = -(wi::one (prec) << z);
136 11450055 : int_range<4> mask_range (type, lb, wi::minus_one (prec));
137 : // Remove the one allowed value from that set.
138 11450055 : wide_int allow = value () | lb;
139 11450055 : mask_range.intersect (int_range<2> (type, allow, allow, VR_ANTI_RANGE));
140 11450055 : mask_range.invert ();
141 11450055 : r.intersect (mask_range);
142 11450074 : }
143 30074461 : return true;
144 127646115 : }
145 :
146 :
147 : void
148 38411 : irange::accept (const vrange_visitor &v) const
149 : {
150 38411 : v.visit (*this);
151 38411 : }
152 :
153 : void
154 23438 : value_range::dump (FILE *out) const
155 : {
156 23438 : if (m_vrange)
157 23438 : m_vrange->dump (out);
158 : else
159 0 : fprintf (out, "NULL");
160 23438 : }
161 :
162 : void
163 0 : value_range::print (pretty_printer *pp) const
164 : {
165 0 : if (m_vrange)
166 : {
167 0 : vrange_printer vrange_pp (pp);
168 0 : m_vrange->accept (vrange_pp);
169 : }
170 : else
171 0 : pp_string (pp, "NULL");
172 0 : }
173 :
174 : DEBUG_FUNCTION void
175 0 : debug (const value_range &r)
176 : {
177 0 : r.dump (stderr);
178 0 : fprintf (stderr, "\n");
179 0 : }
180 :
181 : DEBUG_FUNCTION void
182 0 : debug (const irange_bitmask &bm)
183 : {
184 0 : bm.dump (stderr);
185 0 : fprintf (stderr, "\n");
186 0 : }
187 :
188 : // Definitions for unsupported_range.
189 :
190 : void
191 578 : unsupported_range::accept (const vrange_visitor &v) const
192 : {
193 578 : v.visit (*this);
194 578 : }
195 :
196 : void
197 0 : vrange::update_bitmask (const class irange_bitmask &)
198 : {
199 0 : }
200 :
201 : irange_bitmask
202 0 : vrange::get_bitmask () const
203 : {
204 : // Return all unknown bits for the given precision.
205 0 : return irange_bitmask (TYPE_PRECISION (type ()));
206 : }
207 :
208 : bool
209 0 : unsupported_range::contains_p (tree) const
210 : {
211 0 : return varying_p ();
212 : }
213 :
214 : bool
215 1117466 : unsupported_range::singleton_p (tree *) const
216 : {
217 1117466 : return false;
218 : }
219 :
220 : void
221 0 : unsupported_range::set (tree min, tree, value_range_kind)
222 : {
223 0 : set_varying (TREE_TYPE (min));
224 0 : }
225 :
226 : tree
227 0 : unsupported_range::type () const
228 : {
229 0 : return void_type_node;
230 : }
231 :
232 : bool
233 19740294 : unsupported_range::supports_type_p (const_tree) const
234 : {
235 19740294 : return false;
236 : }
237 :
238 : void
239 108722412 : unsupported_range::set_undefined ()
240 : {
241 108722412 : m_kind = VR_UNDEFINED;
242 108722412 : }
243 :
244 : void
245 3340462 : unsupported_range::set_varying (tree)
246 : {
247 3340462 : m_kind = VR_VARYING;
248 3340462 : }
249 :
250 : bool
251 0 : unsupported_range::union_ (const vrange &v)
252 : {
253 0 : const unsupported_range &r = as_a <unsupported_range> (v);
254 :
255 0 : if (r.undefined_p () || varying_p ())
256 : return false;
257 0 : if (undefined_p () || r.varying_p ())
258 : {
259 0 : operator= (r);
260 0 : return true;
261 : }
262 0 : gcc_unreachable ();
263 : return false;
264 : }
265 :
266 : bool
267 0 : unsupported_range::intersect (const vrange &v)
268 : {
269 0 : const unsupported_range &r = as_a <unsupported_range> (v);
270 :
271 0 : if (undefined_p () || r.varying_p ())
272 : return false;
273 0 : if (r.undefined_p ())
274 : {
275 0 : set_undefined ();
276 0 : return true;
277 : }
278 0 : if (varying_p ())
279 : {
280 0 : operator= (r);
281 0 : return true;
282 : }
283 0 : gcc_unreachable ();
284 : return false;
285 : }
286 :
287 : bool
288 0 : unsupported_range::zero_p () const
289 : {
290 0 : return false;
291 : }
292 :
293 : bool
294 0 : unsupported_range::nonzero_p () const
295 : {
296 0 : return false;
297 : }
298 :
299 : void
300 0 : unsupported_range::set_nonzero (tree type)
301 : {
302 0 : set_varying (type);
303 0 : }
304 :
305 : void
306 0 : unsupported_range::set_zero (tree type)
307 : {
308 0 : set_varying (type);
309 0 : }
310 :
311 : void
312 0 : unsupported_range::set_nonnegative (tree type)
313 : {
314 0 : set_varying (type);
315 0 : }
316 :
317 : bool
318 0 : unsupported_range::fits_p (const vrange &) const
319 : {
320 0 : return true;
321 : }
322 :
323 : unsupported_range &
324 741474 : unsupported_range::operator= (const unsupported_range &r)
325 : {
326 741474 : if (r.undefined_p ())
327 741474 : set_undefined ();
328 0 : else if (r.varying_p ())
329 0 : set_varying (void_type_node);
330 : else
331 0 : gcc_unreachable ();
332 741474 : return *this;
333 : }
334 :
335 : tree
336 0 : unsupported_range::lbound () const
337 : {
338 0 : return NULL;
339 : }
340 :
341 : tree
342 0 : unsupported_range::ubound () const
343 : {
344 0 : return NULL;
345 : }
346 :
347 : // Assignment operator for generic ranges. Copying incompatible types
348 : // is not allowed.
349 :
350 : vrange &
351 9745618 : vrange::operator= (const vrange &src)
352 : {
353 9745618 : if (is_a <irange> (src))
354 8678091 : as_a <irange> (*this) = as_a <irange> (src);
355 1067527 : else if (is_a <prange> (src))
356 801900 : as_a <prange> (*this) = as_a <prange> (src);
357 265627 : else if (is_a <frange> (src))
358 265627 : as_a <frange> (*this) = as_a <frange> (src);
359 : else
360 : {
361 0 : gcc_checking_assert (is_a <unsupported_range> (src));
362 0 : m_kind = src.m_kind;
363 : }
364 9745618 : return *this;
365 : }
366 :
367 : // Equality operator for generic ranges.
368 :
369 : bool
370 37411544 : vrange::operator== (const vrange &src) const
371 : {
372 37411544 : if (is_a <irange> (src))
373 32770403 : return as_a <irange> (*this) == as_a <irange> (src);
374 4641141 : if (is_a <prange> (src))
375 4590743 : return as_a <prange> (*this) == as_a <prange> (src);
376 50398 : if (is_a <frange> (src))
377 50398 : return as_a <frange> (*this) == as_a <frange> (src);
378 0 : gcc_unreachable ();
379 : }
380 :
381 : // Wrapper for vrange_printer to dump a range to a file.
382 :
383 : void
384 37817 : vrange::dump (FILE *file) const
385 : {
386 37817 : pretty_printer pp;
387 37817 : pp_needs_newline (&pp) = true;
388 37817 : pp.set_output_stream (file);
389 37817 : vrange_printer vrange_pp (&pp);
390 37817 : this->accept (vrange_pp);
391 37817 : pp_flush (&pp);
392 37817 : }
393 :
394 : void
395 0 : irange_bitmask::dump (FILE *file) const
396 : {
397 0 : char buf[WIDE_INT_PRINT_BUFFER_SIZE], *p;
398 0 : pretty_printer pp;
399 :
400 0 : pp_needs_newline (&pp) = true;
401 0 : pp.set_output_stream (file);
402 0 : pp_string (&pp, "MASK ");
403 0 : unsigned len_mask, len_val;
404 0 : if (print_hex_buf_size (m_mask, &len_mask)
405 0 : | print_hex_buf_size (m_value, &len_val))
406 0 : p = XALLOCAVEC (char, MAX (len_mask, len_val));
407 : else
408 : p = buf;
409 0 : print_hex (m_mask, p);
410 0 : pp_string (&pp, p);
411 0 : pp_string (&pp, " VALUE ");
412 0 : print_hex (m_value, p);
413 0 : pp_string (&pp, p);
414 0 : pp_flush (&pp);
415 0 : }
416 :
417 : namespace inchash
418 : {
419 :
420 : void
421 30139988 : add_vrange (const vrange &v, inchash::hash &hstate,
422 : unsigned int)
423 : {
424 30139988 : if (v.undefined_p ())
425 : {
426 0 : hstate.add_int (VR_UNDEFINED);
427 0 : return;
428 : }
429 : // Types are ignored throughout to inhibit two ranges being equal
430 : // but having different hash values. This can happen when two
431 : // ranges are equal and their types are different (but
432 : // types_compatible_p is true).
433 30139988 : if (is_a <irange> (v))
434 : {
435 9306753 : const irange &r = as_a <irange> (v);
436 9306753 : if (r.varying_p ())
437 0 : hstate.add_int (VR_VARYING);
438 : else
439 9306753 : hstate.add_int (VR_RANGE);
440 19555262 : for (unsigned i = 0; i < r.num_pairs (); ++i)
441 : {
442 10248509 : hstate.add_wide_int (r.lower_bound (i));
443 10249048 : hstate.add_wide_int (r.upper_bound (i));
444 : }
445 9306753 : irange_bitmask bm = r.get_bitmask ();
446 9306753 : hstate.add_wide_int (bm.value ());
447 9306753 : hstate.add_wide_int (bm.mask ());
448 9306753 : return;
449 9306753 : }
450 20833235 : if (is_a <prange> (v))
451 : {
452 20767118 : const prange &r = as_a <prange> (v);
453 20767118 : if (r.varying_p ())
454 0 : hstate.add_int (VR_VARYING);
455 : else
456 : {
457 20767118 : hstate.add_int (VR_RANGE);
458 20767118 : hstate.add_wide_int (r.lower_bound ());
459 20767118 : hstate.add_wide_int (r.upper_bound ());
460 20767118 : irange_bitmask bm = r.get_bitmask ();
461 20767118 : hstate.add_wide_int (bm.value ());
462 20767118 : hstate.add_wide_int (bm.mask ());
463 20767118 : bool flag = false;
464 20767118 : tree tmp = r.pt_invariant ();
465 : if (tmp)
466 : flag = true;
467 : else
468 1466770 : tmp = r.pt_invariant_away ();
469 20767118 : hstate.add_ptr (tmp);
470 20767118 : hstate.add_flag (flag);
471 20767118 : }
472 20767118 : return;
473 : }
474 66117 : if (is_a <frange> (v))
475 : {
476 66117 : const frange &r = as_a <frange> (v);
477 66117 : if (r.known_isnan ())
478 286 : hstate.add_int (VR_NAN);
479 : else
480 : {
481 65831 : hstate.add_int (r.varying_p () ? VR_VARYING : VR_RANGE);
482 65831 : hstate.add_real_value (r.lower_bound ());
483 65831 : hstate.add_real_value (r.upper_bound ());
484 : }
485 66117 : nan_state nan = r.get_nan_state ();
486 66117 : hstate.add_int (nan.pos_p ());
487 66117 : hstate.add_int (nan.neg_p ());
488 66117 : return;
489 : }
490 0 : gcc_unreachable ();
491 : }
492 :
493 : } //namespace inchash
494 :
495 : bool
496 36047 : irange::nonnegative_p () const
497 : {
498 36047 : return wi::ge_p (lower_bound (), 0, TYPE_SIGN (type ()));
499 : }
500 :
501 : bool
502 31233 : irange::nonpositive_p () const
503 : {
504 31233 : return wi::le_p (upper_bound (), 0, TYPE_SIGN (type ()));
505 : }
506 :
507 : bool
508 637750680 : irange::supports_type_p (const_tree type) const
509 : {
510 637750680 : return supports_p (type);
511 : }
512 :
513 : // Return TRUE if R fits in THIS.
514 :
515 : bool
516 0 : irange::fits_p (const vrange &r) const
517 : {
518 0 : return m_max_ranges >= as_a <irange> (r).num_pairs ();
519 : }
520 :
521 : void
522 41816 : irange::set_nonnegative (tree type)
523 : {
524 41816 : set (type,
525 83632 : wi::zero (TYPE_PRECISION (type)),
526 41816 : wi::to_wide (TYPE_MAX_VALUE (type)));
527 41816 : }
528 :
529 :
530 : // Set the points to info for EXPR if possible. POINTS_TO_P is true if it
531 : // points to EXPR, and FALSE if it points away.
532 :
533 : void
534 13927397 : prange::set_pt (tree expr, bool points_to_p)
535 : {
536 13927397 : gcc_checking_assert (m_kind != VR_UNDEFINED);
537 13927397 : gcc_checking_assert (!expr || TREE_CODE (expr) != SSA_NAME);
538 :
539 13927397 : m_pt = NULL_TREE;
540 13927397 : m_points_to_p = false;
541 :
542 : // No points to initially may make this VARYING.
543 13927397 : if (varying_compatible_p ())
544 373379 : set_varying (type ());
545 : else
546 13554018 : m_kind = VR_RANGE;
547 :
548 13927397 : if (!expr)
549 3958893 : return;
550 :
551 13927397 : gcc_checking_assert (TREE_CODE (expr) == ADDR_EXPR);
552 :
553 : // Ensure only constants get through for now.
554 13927397 : if (!is_gimple_min_invariant (expr))
555 : return;
556 :
557 19937008 : aff_tree offset;
558 : poly_widest_int size;
559 9968504 : tree obj = TREE_OPERAND (expr, 0);
560 9968504 : tree base = get_inner_reference_aff (obj, &offset, &size);
561 :
562 9968504 : if (!base)
563 0 : return;
564 9968504 : if (!offset.offset.is_constant ())
565 : return;
566 9968504 : if (!size.is_constant ())
567 : return;
568 :
569 9968504 : m_pt = expr;
570 9968504 : m_points_to_p = points_to_p;
571 9968504 : m_kind = VR_RANGE;
572 9968504 : }
573 :
574 : // Return object/allocation the pointer refers into, otherwise NULL_TREE.
575 :
576 : tree
577 397 : prange::pt_base () const
578 : {
579 397 : if (!m_pt)
580 : return NULL_TREE;
581 :
582 794 : aff_tree off;
583 : poly_widest_int sz;
584 :
585 397 : gcc_checking_assert (m_pt);
586 397 : return get_inner_reference_aff (m_pt, &off, &sz);
587 397 : }
588 :
589 : // Return possible byte offset range from BASE.
590 :
591 : void
592 397 : prange::pt_offset (irange &r) const
593 : {
594 794 : aff_tree off;
595 : poly_widest_int sz;
596 :
597 397 : gcc_checking_assert (m_pt);
598 :
599 397 : get_inner_reference_aff (m_pt, &off, &sz);
600 397 : gcc_checking_assert (off.offset.is_constant ());
601 :
602 397 : widest_int w = off.offset.coeffs[0];
603 397 : wide_int w2 = wi::to_wide (wide_int_to_tree (sizetype, w));
604 397 : r.set (sizetype, w2, w2);
605 397 : }
606 :
607 : // Return possible size range of the referenced object.
608 :
609 : void
610 397 : prange::pt_size (irange &r) const
611 : {
612 794 : aff_tree off;
613 : poly_widest_int sz;
614 :
615 397 : gcc_checking_assert (m_pt);
616 :
617 397 : get_inner_reference_aff (m_pt, &off, &sz);
618 397 : gcc_checking_assert (sz.is_constant ());
619 :
620 397 : widest_int w = sz.coeffs[0];
621 397 : wide_int w2 = wi::to_wide (wide_int_to_tree (sizetype, w));
622 397 : r.set (sizetype, w2, w2);
623 397 : }
624 : // Prange implementation.
625 :
626 : void
627 1432 : prange::accept (const vrange_visitor &v) const
628 : {
629 1432 : v.visit (*this);
630 1432 : }
631 :
632 : void
633 0 : prange::set_nonnegative (tree type)
634 : {
635 0 : set (type,
636 0 : wi::zero (TYPE_PRECISION (type)),
637 0 : wi::max_value (TYPE_PRECISION (type), UNSIGNED));
638 0 : }
639 :
640 : void
641 13786496 : prange::set (tree min, tree max, value_range_kind kind)
642 : {
643 13786496 : return set (TREE_TYPE (min), wi::to_wide (min), wi::to_wide (max), kind);
644 : }
645 :
646 : void
647 39250005 : prange::set (tree type, const wide_int &min, const wide_int &max,
648 : value_range_kind kind)
649 : {
650 39250005 : if (kind == VR_UNDEFINED)
651 : {
652 0 : set_undefined ();
653 0 : return;
654 : }
655 39250005 : if (kind == VR_VARYING)
656 : {
657 0 : set_varying (type);
658 0 : return;
659 : }
660 39250005 : if (kind == VR_ANTI_RANGE)
661 : {
662 0 : gcc_checking_assert (min == 0 && max == 0);
663 0 : set_nonzero (type);
664 0 : return;
665 : }
666 39250005 : m_type = type;
667 39250005 : m_min = min;
668 39250005 : m_max = max;
669 39250005 : set_pt_unknown ();
670 :
671 39250005 : if (m_min == 0 && m_max == -1)
672 : {
673 4884279 : m_kind = VR_VARYING;
674 4884279 : m_bitmask.set_unknown (TYPE_PRECISION (type));
675 4884279 : if (flag_checking)
676 4884279 : verify_range ();
677 4884279 : return;
678 : }
679 :
680 34365726 : m_kind = VR_RANGE;
681 34365726 : m_bitmask = irange_bitmask (type, min, max);
682 34365726 : if (flag_checking)
683 34365714 : verify_range ();
684 : }
685 :
686 : bool
687 2995724 : prange::contains_p (const wide_int &w) const
688 : {
689 2995724 : if (undefined_p ())
690 : return false;
691 :
692 2995724 : if (varying_p ())
693 : return true;
694 :
695 4685362 : return (wi::le_p (lower_bound (), w, UNSIGNED)
696 2345004 : && wi::ge_p (upper_bound (), w, UNSIGNED));
697 : }
698 :
699 : bool
700 215302984 : prange::singleton_p (tree *result) const
701 : {
702 300506291 : if (m_kind == VR_RANGE && lower_bound () == upper_bound ())
703 : {
704 186886 : if (result)
705 70613 : *result = wide_int_to_tree (type (), m_min);
706 186886 : return true;
707 : }
708 : return false;
709 : }
710 :
711 : tree
712 4766311 : prange::lbound () const
713 : {
714 4766311 : return wide_int_to_tree (type (), m_min);
715 : }
716 :
717 : tree
718 761324 : prange::ubound () const
719 : {
720 761324 : return wide_int_to_tree (type (), m_max);
721 : }
722 :
723 : bool
724 16530817 : prange::union_ (const vrange &v)
725 : {
726 16530817 : const prange &r = as_a <prange> (v);
727 :
728 16530817 : if (r.undefined_p ())
729 : return false;
730 16389865 : if (undefined_p ())
731 : {
732 8345685 : *this = r;
733 8345685 : if (flag_checking)
734 8345685 : verify_range ();
735 8345685 : return true;
736 : }
737 8044180 : if (varying_p ())
738 : return false;
739 4241846 : if (r.varying_p ())
740 : {
741 1274030 : set_varying (type ());
742 1274030 : return true;
743 : }
744 :
745 2967816 : wide_int new_lb = wi::min (r.lower_bound (), lower_bound (), UNSIGNED);
746 2967816 : wide_int new_ub = wi::max (r.upper_bound (), upper_bound (), UNSIGNED);
747 2967816 : prange new_range (type (), new_lb, new_ub);
748 2967816 : new_range.m_bitmask.union_ (m_bitmask);
749 2967816 : new_range.m_bitmask.union_ (r.m_bitmask);
750 :
751 : // Keep it simple, either both point to the same thing or both
752 : // do not point to the same thing, or we drop the points to info.
753 2967816 : if (pt_equal_p (r))
754 2341610 : new_range.set_pt (*this);
755 :
756 2967816 : if (new_range.varying_compatible_p ())
757 : {
758 313728 : set_varying (type ());
759 313728 : return true;
760 : }
761 2654088 : if (flag_checking)
762 2654088 : new_range.verify_range ();
763 2654088 : if (new_range == *this)
764 : return false;
765 301602 : *this = new_range;
766 301602 : return true;
767 2967816 : }
768 :
769 : bool
770 189255473 : prange::intersect (const vrange &v)
771 : {
772 189255473 : const prange &r = as_a <prange> (v);
773 189255473 : gcc_checking_assert (undefined_p () || r.undefined_p ()
774 : || range_compatible_p (type (), r.type ()));
775 :
776 189255473 : if (undefined_p ())
777 : return false;
778 189144872 : if (r.undefined_p ())
779 : {
780 30113 : set_undefined ();
781 30113 : return true;
782 : }
783 189114759 : if (r.varying_p ())
784 : return false;
785 101488680 : if (varying_p ())
786 : {
787 45800979 : *this = r;
788 45800979 : return true;
789 : }
790 :
791 : // If this points to and away, results are undefined,
792 55687701 : if (pt_inverted_p (r))
793 : {
794 0 : set_undefined ();
795 0 : return true;
796 : }
797 :
798 55687701 : prange save = *this;
799 55687701 : m_min = wi::max (r.lower_bound (), lower_bound (), UNSIGNED);
800 55687701 : m_max = wi::min (r.upper_bound (), upper_bound (), UNSIGNED);
801 55687701 : if (wi::gt_p (m_min, m_max, UNSIGNED))
802 : {
803 370520 : set_undefined ();
804 370520 : return true;
805 : }
806 :
807 : // Intersect all bitmasks: the old one, the new one, and the other operand's.
808 55317181 : irange_bitmask new_bitmask (m_type, m_min, m_max);
809 55317181 : if (!m_bitmask.intersect (new_bitmask))
810 12 : set_undefined ();
811 55317169 : else if (!m_bitmask.intersect (r.m_bitmask))
812 4 : set_undefined ();
813 : // If only one object points to something, that is the intersection.
814 55317165 : else if (pt_unknown_p () && !r.pt_unknown_p ())
815 534860 : set_pt (r);
816 54782305 : else if (!pt_unknown_p () && !r.pt_unknown_p ())
817 : {
818 : // If both point to something, we want to be careful. Without aliasing
819 : // 2 different values can point to the same thing, so UNDEFINED is
820 : // not appropriate, but we want to keep the rule that intersection
821 : // never becomes larger.
822 : // If the other object points to something specific, and this one does
823 : // not, use the specific one. Otherwise leave the range as is.
824 103847 : if (pt_invariant_away () && r.pt_invariant ())
825 0 : set_pt (r);
826 : }
827 :
828 55317181 : if (varying_compatible_p ())
829 : {
830 0 : set_varying (type ());
831 0 : return true;
832 : }
833 :
834 55317181 : if (flag_checking)
835 55317076 : verify_range ();
836 55317181 : if (*this == save)
837 : return false;
838 : return true;
839 55687701 : }
840 :
841 : prange &
842 180435574 : prange::operator= (const prange &src)
843 : {
844 180435574 : m_type = src.m_type;
845 180435574 : m_kind = src.m_kind;
846 180435574 : m_min = src.m_min;
847 180435574 : m_max = src.m_max;
848 180435574 : m_bitmask = src.m_bitmask;
849 180435574 : set_pt (src);
850 180435574 : if (flag_checking)
851 180435439 : verify_range ();
852 180435574 : return *this;
853 : }
854 :
855 : bool
856 62562016 : prange::operator== (const prange &src) const
857 : {
858 62562016 : if (m_kind == src.m_kind)
859 : {
860 61987828 : if (undefined_p ())
861 : return true;
862 :
863 61979822 : if (varying_p ())
864 956399 : return types_compatible_p (type (), src.type ());
865 :
866 61023423 : if (!pt_equal_p (src))
867 : return false;
868 :
869 119926641 : return (m_min == src.m_min && m_max == src.m_max
870 119551371 : && m_bitmask == src.m_bitmask);
871 : }
872 : return false;
873 : }
874 :
875 :
876 : void
877 2584763 : prange::invert ()
878 : {
879 2584763 : gcc_checking_assert (!undefined_p () && !varying_p ());
880 :
881 : // Invert the points_to object. If that worked, this is done.
882 2584763 : if (pt_invert ())
883 0 : return;
884 : else
885 2584763 : set_pt_unknown ();
886 :
887 2584763 : wide_int new_lb, new_ub;
888 2584763 : unsigned prec = TYPE_PRECISION (type ());
889 2584763 : wide_int type_min = wi::zero (prec);
890 2584763 : wide_int type_max = wi::max_value (prec, UNSIGNED);
891 2584763 : wi::overflow_type ovf;
892 :
893 2584763 : if (lower_bound () == type_min)
894 : {
895 2577837 : new_lb = wi::add (upper_bound (), 1, UNSIGNED, &ovf);
896 2577837 : if (ovf)
897 0 : new_lb = type_min;
898 2577837 : new_ub = type_max;
899 2577837 : set (type (), new_lb, new_ub);
900 : }
901 6926 : else if (upper_bound () == type_max)
902 : {
903 2860 : wi::overflow_type ovf;
904 2860 : new_lb = type_min;
905 2860 : new_ub = wi::sub (lower_bound (), 1, UNSIGNED, &ovf);
906 2860 : if (ovf)
907 0 : new_ub = type_max;
908 2860 : set (type (), new_lb, new_ub);
909 : }
910 : else
911 4066 : set_varying (type ());
912 2584763 : }
913 :
914 : void
915 1141778476 : prange::verify_range () const
916 : {
917 1141778476 : gcc_checking_assert (m_discriminator == VR_PRANGE);
918 :
919 1141778476 : if (m_kind == VR_UNDEFINED)
920 : {
921 64068 : gcc_checking_assert (pt_unknown_p ());
922 : return;
923 : }
924 :
925 1141714408 : gcc_checking_assert (supports_p (type ()));
926 :
927 1141714408 : if (m_kind == VR_VARYING)
928 : {
929 496456442 : gcc_checking_assert (varying_compatible_p ());
930 : return;
931 : }
932 645257966 : gcc_checking_assert (!varying_compatible_p ());
933 645257966 : gcc_checking_assert (m_kind == VR_RANGE);
934 : }
935 :
936 : void
937 28867715 : prange::update_bitmask (const irange_bitmask &bm)
938 : {
939 28867715 : gcc_checking_assert (!undefined_p ());
940 :
941 : // If all the bits are known, this is a singleton.
942 28867715 : if (bm.mask () == 0)
943 : {
944 151945 : set (type (), bm.value (), bm.value ());
945 151945 : return;
946 : }
947 :
948 : // Drop VARYINGs with known bits to a plain range.
949 35925648 : if (m_kind == VR_VARYING && !bm.unknown_p ())
950 38587 : m_kind = VR_RANGE;
951 :
952 28715770 : m_bitmask = bm;
953 28715770 : if (varying_compatible_p ())
954 7171291 : m_kind = VR_VARYING;
955 :
956 28715770 : if (flag_checking)
957 28715770 : verify_range ();
958 : }
959 :
960 :
961 : // Frange implementation.
962 :
963 : void
964 209 : frange::accept (const vrange_visitor &v) const
965 : {
966 209 : v.visit (*this);
967 209 : }
968 :
969 : bool
970 0 : frange::fits_p (const vrange &) const
971 : {
972 0 : return true;
973 : }
974 :
975 : // Flush denormal endpoints to the appropriate 0.0.
976 :
977 : void
978 6625177 : frange::flush_denormals_to_zero ()
979 : {
980 6625177 : if (undefined_p () || known_isnan ())
981 : return;
982 :
983 6625177 : machine_mode mode = TYPE_MODE (type ());
984 : // Flush [x, -DENORMAL] to [x, -0.0].
985 6625177 : if (real_isdenormal (&m_max, mode) && real_isneg (&m_max))
986 : {
987 2032 : if (HONOR_SIGNED_ZEROS (m_type))
988 2032 : m_max = dconstm0;
989 : else
990 0 : m_max = dconst0;
991 : }
992 : // Flush [+DENORMAL, x] to [+0.0, x].
993 6625177 : if (real_isdenormal (&m_min, mode) && !real_isneg (&m_min))
994 3704 : m_min = dconst0;
995 : }
996 :
997 : // Setter for franges.
998 :
999 : void
1000 63098885 : frange::set (tree type,
1001 : const REAL_VALUE_TYPE &min, const REAL_VALUE_TYPE &max,
1002 : const nan_state &nan, value_range_kind kind)
1003 : {
1004 63098885 : switch (kind)
1005 : {
1006 0 : case VR_UNDEFINED:
1007 0 : set_undefined ();
1008 0 : return;
1009 32738028 : case VR_VARYING:
1010 32738028 : case VR_ANTI_RANGE:
1011 32738028 : set_varying (type);
1012 32738028 : return;
1013 30360857 : case VR_RANGE:
1014 30360857 : break;
1015 0 : default:
1016 0 : gcc_unreachable ();
1017 : }
1018 :
1019 30360857 : gcc_checking_assert (!real_isnan (&min) && !real_isnan (&max));
1020 :
1021 30360857 : m_kind = kind;
1022 30360857 : m_type = type;
1023 30360857 : m_min = min;
1024 30360857 : m_max = max;
1025 30360857 : if (HONOR_NANS (m_type))
1026 : {
1027 29468234 : m_pos_nan = nan.pos_p ();
1028 29468234 : m_neg_nan = nan.neg_p ();
1029 : }
1030 : else
1031 : {
1032 892623 : m_pos_nan = false;
1033 892623 : m_neg_nan = false;
1034 : }
1035 :
1036 121443428 : if (!MODE_HAS_SIGNED_ZEROS (TYPE_MODE (m_type)))
1037 : {
1038 0 : if (real_iszero (&m_min, 1))
1039 0 : m_min.sign = 0;
1040 0 : if (real_iszero (&m_max, 1))
1041 0 : m_max.sign = 0;
1042 : }
1043 30360857 : else if (!HONOR_SIGNED_ZEROS (m_type))
1044 : {
1045 925612 : if (real_iszero (&m_max, 1))
1046 23 : m_max.sign = 0;
1047 925612 : if (real_iszero (&m_min, 0))
1048 26739 : m_min.sign = 1;
1049 : }
1050 :
1051 : // For -ffinite-math-only we can drop ranges outside the
1052 : // representable numbers to min/max for the type.
1053 30360857 : if (!HONOR_INFINITIES (m_type))
1054 : {
1055 892623 : REAL_VALUE_TYPE min_repr = frange_val_min (m_type);
1056 892623 : REAL_VALUE_TYPE max_repr = frange_val_max (m_type);
1057 892623 : if (real_less (&m_min, &min_repr))
1058 316035 : m_min = min_repr;
1059 576588 : else if (real_less (&max_repr, &m_min))
1060 1 : m_min = max_repr;
1061 892623 : if (real_less (&max_repr, &m_max))
1062 318903 : m_max = max_repr;
1063 573720 : else if (real_less (&m_max, &min_repr))
1064 0 : m_max = min_repr;
1065 : }
1066 :
1067 : // Check for swapped ranges.
1068 30360857 : gcc_checking_assert (real_compare (LE_EXPR, &min, &max));
1069 :
1070 30360857 : normalize_kind ();
1071 : }
1072 :
1073 : // Setter for an frange defaulting the NAN possibility to +-NAN when
1074 : // HONOR_NANS.
1075 :
1076 : void
1077 50035483 : frange::set (tree type,
1078 : const REAL_VALUE_TYPE &min, const REAL_VALUE_TYPE &max,
1079 : value_range_kind kind)
1080 : {
1081 50035483 : set (type, min, max, nan_state (true), kind);
1082 50035483 : }
1083 :
1084 : void
1085 62 : frange::set (tree min, tree max, value_range_kind kind)
1086 : {
1087 124 : set (TREE_TYPE (min),
1088 62 : *TREE_REAL_CST_PTR (min), *TREE_REAL_CST_PTR (max), kind);
1089 62 : }
1090 :
1091 : // Normalize range to VARYING or UNDEFINED, or vice versa. Return
1092 : // TRUE if anything changed.
1093 : //
1094 : // A range with no known properties can be dropped to VARYING.
1095 : // Similarly, a VARYING with any properties should be dropped to a
1096 : // VR_RANGE. Normalizing ranges upon changing them ensures there is
1097 : // only one representation for a given range.
1098 :
1099 : bool
1100 59908879 : frange::normalize_kind ()
1101 : {
1102 59908879 : if (m_kind == VR_RANGE
1103 52463018 : && frange_val_is_min (m_min, m_type)
1104 71062680 : && frange_val_is_max (m_max, m_type))
1105 : {
1106 8209882 : if (!HONOR_NANS (m_type) || (m_pos_nan && m_neg_nan))
1107 : {
1108 6696162 : set_varying (m_type);
1109 6696162 : return true;
1110 : }
1111 : }
1112 51698997 : else if (m_kind == VR_VARYING)
1113 : {
1114 7445570 : if (HONOR_NANS (m_type) && (!m_pos_nan || !m_neg_nan))
1115 : {
1116 1972933 : m_kind = VR_RANGE;
1117 1972933 : m_min = frange_val_min (m_type);
1118 1972933 : m_max = frange_val_max (m_type);
1119 1972933 : if (flag_checking)
1120 1972933 : verify_range ();
1121 1972933 : return true;
1122 : }
1123 : }
1124 44253427 : else if (m_kind == VR_NAN && !m_pos_nan && !m_neg_nan)
1125 4 : set_undefined ();
1126 : return false;
1127 : }
1128 :
1129 : // Union or intersect the zero endpoints of two ranges. For example:
1130 : // [-0, x] U [+0, x] => [-0, x]
1131 : // [ x, -0] U [ x, +0] => [ x, +0]
1132 : // [-0, x] ^ [+0, x] => [+0, x]
1133 : // [ x, -0] ^ [ x, +0] => [ x, -0]
1134 : //
1135 : // UNION_P is true when performing a union, or false when intersecting.
1136 :
1137 : bool
1138 8408493 : frange::combine_zeros (const frange &r, bool union_p)
1139 : {
1140 8408493 : gcc_checking_assert (!undefined_p () && !known_isnan ());
1141 :
1142 8408493 : bool changed = false;
1143 11158116 : if (real_iszero (&m_min) && real_iszero (&r.m_min)
1144 10759161 : && real_isneg (&m_min) != real_isneg (&r.m_min))
1145 : {
1146 163553 : m_min.sign = union_p;
1147 163553 : changed = true;
1148 : }
1149 8625454 : if (real_iszero (&m_max) && real_iszero (&r.m_max)
1150 8582200 : && real_isneg (&m_max) != real_isneg (&r.m_max))
1151 : {
1152 3944 : m_max.sign = !union_p;
1153 3944 : changed = true;
1154 : }
1155 : // If the signs are swapped, the resulting range is empty.
1156 8408493 : if (m_min.sign == 0 && m_max.sign == 1)
1157 : {
1158 136 : if (maybe_isnan ())
1159 8 : m_kind = VR_NAN;
1160 : else
1161 64 : set_undefined ();
1162 : changed = true;
1163 : }
1164 8408493 : return changed;
1165 : }
1166 :
1167 : // Union two ranges when one is known to be a NAN.
1168 :
1169 : bool
1170 205839 : frange::union_nans (const frange &r)
1171 : {
1172 205839 : gcc_checking_assert (known_isnan () || r.known_isnan ());
1173 :
1174 205839 : bool changed = false;
1175 205839 : if (known_isnan () && m_kind != r.m_kind)
1176 : {
1177 41291 : m_kind = r.m_kind;
1178 41291 : m_min = r.m_min;
1179 41291 : m_max = r.m_max;
1180 41291 : changed = true;
1181 : }
1182 205839 : if (m_pos_nan != r.m_pos_nan || m_neg_nan != r.m_neg_nan)
1183 : {
1184 196220 : m_pos_nan |= r.m_pos_nan;
1185 196220 : m_neg_nan |= r.m_neg_nan;
1186 196220 : changed = true;
1187 : }
1188 205839 : if (changed)
1189 : {
1190 204217 : normalize_kind ();
1191 204217 : return true;
1192 : }
1193 : return false;
1194 : }
1195 :
1196 : bool
1197 3865868 : frange::union_ (const vrange &v)
1198 : {
1199 3865868 : const frange &r = as_a <frange> (v);
1200 :
1201 3865868 : if (r.undefined_p () || varying_p ())
1202 : return false;
1203 3211838 : if (undefined_p () || r.varying_p ())
1204 : {
1205 1923473 : *this = r;
1206 1923473 : return true;
1207 : }
1208 :
1209 : // Combine NAN info.
1210 1288365 : if (known_isnan () || r.known_isnan ())
1211 205839 : return union_nans (r);
1212 1082526 : bool changed = false;
1213 1082526 : if (m_pos_nan != r.m_pos_nan || m_neg_nan != r.m_neg_nan)
1214 : {
1215 378697 : m_pos_nan |= r.m_pos_nan;
1216 378697 : m_neg_nan |= r.m_neg_nan;
1217 378697 : changed = true;
1218 : }
1219 :
1220 : // Combine endpoints.
1221 1082526 : if (real_less (&r.m_min, &m_min))
1222 : {
1223 513165 : m_min = r.m_min;
1224 513165 : changed = true;
1225 : }
1226 1082526 : if (real_less (&m_max, &r.m_max))
1227 : {
1228 78953 : m_max = r.m_max;
1229 78953 : changed = true;
1230 : }
1231 :
1232 1082526 : if (HONOR_SIGNED_ZEROS (m_type))
1233 1079493 : changed |= combine_zeros (r, true);
1234 :
1235 1082526 : changed |= normalize_kind ();
1236 1082526 : return changed;
1237 : }
1238 :
1239 : // Intersect two ranges when one is known to be a NAN.
1240 :
1241 : bool
1242 51920 : frange::intersect_nans (const frange &r)
1243 : {
1244 51920 : gcc_checking_assert (known_isnan () || r.known_isnan ());
1245 :
1246 51920 : m_pos_nan &= r.m_pos_nan;
1247 51920 : m_neg_nan &= r.m_neg_nan;
1248 54516 : if (maybe_isnan ())
1249 49356 : m_kind = VR_NAN;
1250 : else
1251 2564 : set_undefined ();
1252 51920 : if (flag_checking)
1253 51920 : verify_range ();
1254 51920 : return true;
1255 : }
1256 :
1257 : bool
1258 24865401 : frange::intersect (const vrange &v)
1259 : {
1260 24865401 : const frange &r = as_a <frange> (v);
1261 :
1262 24865401 : if (undefined_p () || r.varying_p ())
1263 : return false;
1264 9799106 : if (r.undefined_p ())
1265 : {
1266 5610 : set_undefined ();
1267 5610 : return true;
1268 : }
1269 9793496 : if (varying_p ())
1270 : {
1271 2294708 : *this = r;
1272 2294708 : return true;
1273 : }
1274 :
1275 : // Combine NAN info.
1276 7498788 : if (known_isnan () || r.known_isnan ())
1277 51920 : return intersect_nans (r);
1278 7446868 : bool changed = false;
1279 7446868 : if (m_pos_nan != r.m_pos_nan || m_neg_nan != r.m_neg_nan)
1280 : {
1281 2402303 : m_pos_nan &= r.m_pos_nan;
1282 2402303 : m_neg_nan &= r.m_neg_nan;
1283 2402303 : changed = true;
1284 : }
1285 :
1286 : // Combine endpoints.
1287 7446868 : if (real_less (&m_min, &r.m_min))
1288 : {
1289 1433124 : m_min = r.m_min;
1290 1433124 : changed = true;
1291 : }
1292 7446868 : if (real_less (&r.m_max, &m_max))
1293 : {
1294 1215651 : m_max = r.m_max;
1295 1215651 : changed = true;
1296 : }
1297 : // If the endpoints are swapped, the resulting range is empty.
1298 7446868 : if (real_less (&m_max, &m_min))
1299 : {
1300 36883 : if (maybe_isnan ())
1301 29087 : m_kind = VR_NAN;
1302 : else
1303 3898 : set_undefined ();
1304 32985 : if (flag_checking)
1305 32985 : verify_range ();
1306 32985 : return true;
1307 : }
1308 :
1309 7413883 : if (HONOR_SIGNED_ZEROS (m_type))
1310 7329000 : changed |= combine_zeros (r, false);
1311 :
1312 7413883 : changed |= normalize_kind ();
1313 7413883 : return changed;
1314 : }
1315 :
1316 : frange &
1317 53713273 : frange::operator= (const frange &src)
1318 : {
1319 53713273 : m_kind = src.m_kind;
1320 53713273 : m_type = src.m_type;
1321 53713273 : m_min = src.m_min;
1322 53713273 : m_max = src.m_max;
1323 53713273 : m_pos_nan = src.m_pos_nan;
1324 53713273 : m_neg_nan = src.m_neg_nan;
1325 :
1326 53713273 : if (flag_checking)
1327 53713273 : verify_range ();
1328 53713273 : return *this;
1329 : }
1330 :
1331 : bool
1332 71030 : frange::operator== (const frange &src) const
1333 : {
1334 71030 : if (m_kind == src.m_kind)
1335 : {
1336 60581 : if (undefined_p ())
1337 : return true;
1338 :
1339 60442 : if (varying_p ())
1340 25476 : return types_compatible_p (m_type, src.m_type);
1341 :
1342 34966 : bool nan1 = known_isnan ();
1343 34966 : bool nan2 = src.known_isnan ();
1344 34966 : if (nan1 || nan2)
1345 : {
1346 123 : if (nan1 && nan2)
1347 123 : return (m_pos_nan == src.m_pos_nan
1348 123 : && m_neg_nan == src.m_neg_nan);
1349 : return false;
1350 : }
1351 :
1352 34843 : return (real_identical (&m_min, &src.m_min)
1353 30769 : && real_identical (&m_max, &src.m_max)
1354 30401 : && m_pos_nan == src.m_pos_nan
1355 30378 : && m_neg_nan == src.m_neg_nan
1356 65008 : && types_compatible_p (m_type, src.m_type));
1357 : }
1358 : return false;
1359 : }
1360 :
1361 : // Return TRUE if range contains R.
1362 :
1363 : bool
1364 49993 : frange::contains_p (const REAL_VALUE_TYPE &r) const
1365 : {
1366 49993 : gcc_checking_assert (m_kind != VR_ANTI_RANGE);
1367 :
1368 49993 : if (undefined_p ())
1369 : return false;
1370 :
1371 49993 : if (varying_p ())
1372 : return true;
1373 :
1374 47504 : if (real_isnan (&r))
1375 : {
1376 : // No NAN in range.
1377 0 : if (!m_pos_nan && !m_neg_nan)
1378 : return false;
1379 : // Both +NAN and -NAN are present.
1380 0 : if (m_pos_nan && m_neg_nan)
1381 : return true;
1382 0 : return m_neg_nan == r.sign;
1383 : }
1384 47504 : if (known_isnan ())
1385 : return false;
1386 :
1387 47504 : if (real_compare (GE_EXPR, &r, &m_min) && real_compare (LE_EXPR, &r, &m_max))
1388 : {
1389 : // Make sure the signs are equal for signed zeros.
1390 14932 : if (HONOR_SIGNED_ZEROS (m_type) && real_iszero (&r))
1391 29590 : return r.sign == m_min.sign || r.sign == m_max.sign;
1392 17 : return true;
1393 : }
1394 : return false;
1395 : }
1396 :
1397 : // If range is a singleton, place it in RESULT and return TRUE. If
1398 : // RESULT is NULL, just return TRUE.
1399 : //
1400 : // A NAN can never be a singleton.
1401 :
1402 : bool
1403 23674585 : frange::internal_singleton_p (REAL_VALUE_TYPE *result) const
1404 : {
1405 23674585 : if (m_kind == VR_RANGE && real_identical (&m_min, &m_max))
1406 : {
1407 : // Return false for any singleton that may be a NAN.
1408 23783126 : if (HONOR_NANS (m_type) && maybe_isnan ())
1409 : return false;
1410 :
1411 749112 : if (MODE_COMPOSITE_P (TYPE_MODE (m_type)))
1412 : {
1413 : // For IBM long doubles, if the value is +-Inf or is exactly
1414 : // representable in double, the other double could be +0.0
1415 : // or -0.0. Since this means there is more than one way to
1416 : // represent a value, return false to avoid propagating it.
1417 : // See libgcc/config/rs6000/ibm-ldouble-format for details.
1418 0 : if (real_isinf (&m_min))
1419 0 : return false;
1420 0 : REAL_VALUE_TYPE r;
1421 0 : real_convert (&r, DFmode, &m_min);
1422 0 : if (real_identical (&r, &m_min))
1423 : return false;
1424 : }
1425 :
1426 107016 : if (result)
1427 0 : *result = m_min;
1428 107016 : return true;
1429 : }
1430 : return false;
1431 : }
1432 :
1433 : bool
1434 23674585 : frange::singleton_p (tree *result) const
1435 : {
1436 23674585 : if (internal_singleton_p ())
1437 : {
1438 107016 : if (result)
1439 7758 : *result = build_real (m_type, m_min);
1440 107016 : return true;
1441 : }
1442 : return false;
1443 : }
1444 :
1445 : bool
1446 0 : frange::singleton_p (REAL_VALUE_TYPE &r) const
1447 : {
1448 0 : return internal_singleton_p (&r);
1449 : }
1450 :
1451 : bool
1452 62845414 : frange::supports_type_p (const_tree type) const
1453 : {
1454 62845414 : return supports_p (type);
1455 : }
1456 :
1457 : void
1458 207980352 : frange::verify_range () const
1459 : {
1460 207980352 : if (!undefined_p ())
1461 82191373 : gcc_checking_assert (HONOR_NANS (m_type) || !maybe_isnan ());
1462 207980352 : switch (m_kind)
1463 : {
1464 131046314 : case VR_UNDEFINED:
1465 131046314 : gcc_checking_assert (!m_type);
1466 : return;
1467 42754033 : case VR_VARYING:
1468 42754033 : gcc_checking_assert (m_type);
1469 42754033 : gcc_checking_assert (frange_val_is_min (m_min, m_type));
1470 42754033 : gcc_checking_assert (frange_val_is_max (m_max, m_type));
1471 42754033 : if (HONOR_NANS (m_type))
1472 38231423 : gcc_checking_assert (m_pos_nan && m_neg_nan);
1473 : else
1474 4522610 : gcc_checking_assert (!m_pos_nan && !m_neg_nan);
1475 : return;
1476 33691368 : case VR_RANGE:
1477 33691368 : gcc_checking_assert (m_type);
1478 33691368 : break;
1479 488637 : case VR_NAN:
1480 488637 : gcc_checking_assert (m_type);
1481 488637 : gcc_checking_assert (m_pos_nan || m_neg_nan);
1482 : return;
1483 0 : default:
1484 0 : gcc_unreachable ();
1485 : }
1486 :
1487 : // NANs cannot appear in the endpoints of a range.
1488 33691368 : gcc_checking_assert (!real_isnan (&m_min) && !real_isnan (&m_max));
1489 :
1490 : // Make sure we don't have swapped ranges.
1491 33691368 : gcc_checking_assert (!real_less (&m_max, &m_min));
1492 :
1493 : // [ +0.0, -0.0 ] is nonsensical.
1494 33691368 : gcc_checking_assert (!(real_iszero (&m_min, 0) && real_iszero (&m_max, 1)));
1495 :
1496 : // If all the properties are clear, we better not span the entire
1497 : // domain, because that would make us varying.
1498 33691368 : if (m_pos_nan && m_neg_nan)
1499 12352996 : gcc_checking_assert (!frange_val_is_min (m_min, m_type)
1500 : || !frange_val_is_max (m_max, m_type));
1501 : }
1502 :
1503 : // We can't do much with nonzeros yet.
1504 : void
1505 0 : frange::set_nonzero (tree type)
1506 : {
1507 0 : set_varying (type);
1508 0 : }
1509 :
1510 : // We can't do much with nonzeros yet.
1511 : bool
1512 0 : frange::nonzero_p () const
1513 : {
1514 0 : return false;
1515 : }
1516 :
1517 : // Set range to [+0.0, +0.0] if honoring signed zeros, or [0.0, 0.0]
1518 : // otherwise.
1519 :
1520 : void
1521 157995 : frange::set_zero (tree type)
1522 : {
1523 157995 : if (HONOR_SIGNED_ZEROS (type))
1524 : {
1525 157995 : set (type, dconstm0, dconst0);
1526 157995 : clear_nan ();
1527 : }
1528 : else
1529 0 : set (type, dconst0, dconst0);
1530 157995 : }
1531 :
1532 : // Return TRUE for any zero regardless of sign.
1533 :
1534 : bool
1535 8992 : frange::zero_p () const
1536 : {
1537 8992 : return (m_kind == VR_RANGE
1538 7905 : && real_iszero (&m_min)
1539 10990 : && real_iszero (&m_max));
1540 : }
1541 :
1542 : // Set the range to non-negative numbers, that is [+0.0, +INF].
1543 : //
1544 : // The NAN in the resulting range (if HONOR_NANS) has a varying sign
1545 : // as there are no guarantees in IEEE 754 wrt to the sign of a NAN,
1546 : // except for copy, abs, and copysign. It is the responsibility of
1547 : // the caller to set the NAN's sign if desired.
1548 :
1549 : void
1550 37425 : frange::set_nonnegative (tree type)
1551 : {
1552 37425 : set (type, dconst0, frange_val_max (type));
1553 37425 : }
1554 :
1555 : tree
1556 0 : frange::lbound () const
1557 : {
1558 0 : return build_real (type (), lower_bound ());
1559 : }
1560 :
1561 : tree
1562 0 : frange::ubound () const
1563 : {
1564 0 : return build_real (type (), upper_bound ());
1565 : }
1566 :
1567 : // Here we copy between any two irange's.
1568 :
1569 : irange &
1570 1010058137 : irange::operator= (const irange &src)
1571 : {
1572 1010058137 : int needed = src.num_pairs ();
1573 1010058137 : maybe_resize (needed);
1574 :
1575 1010058137 : unsigned x;
1576 1010058137 : unsigned lim = src.m_num_ranges;
1577 1010058137 : if (lim > m_max_ranges)
1578 16641 : lim = m_max_ranges;
1579 :
1580 3209978803 : for (x = 0; x < lim * 2; ++x)
1581 2199920666 : m_base[x] = src.m_base[x];
1582 :
1583 : // If the range didn't fit, the last range should cover the rest.
1584 1010058137 : if (lim != src.m_num_ranges)
1585 16641 : m_base[x - 1] = src.m_base[src.m_num_ranges * 2 - 1];
1586 :
1587 1010058137 : m_num_ranges = lim;
1588 1010058137 : m_type = src.m_type;
1589 1010058137 : m_kind = src.m_kind;
1590 1010058137 : m_bitmask = src.m_bitmask;
1591 1010058137 : if (m_max_ranges == 1)
1592 20987454 : normalize_kind ();
1593 1010058137 : if (flag_checking)
1594 1010052306 : verify_range ();
1595 1010058137 : return *this;
1596 : }
1597 :
1598 : static value_range_kind
1599 20712842 : get_legacy_range (const irange &r, tree &min, tree &max)
1600 : {
1601 20712842 : if (r.undefined_p ())
1602 : {
1603 104717 : min = NULL_TREE;
1604 104717 : max = NULL_TREE;
1605 104717 : return VR_UNDEFINED;
1606 : }
1607 :
1608 20608125 : tree type = r.type ();
1609 20608125 : if (r.varying_p ())
1610 : {
1611 8764917 : min = wide_int_to_tree (type, r.lower_bound ());
1612 8764917 : max = wide_int_to_tree (type, r.upper_bound ());
1613 8764917 : return VR_VARYING;
1614 : }
1615 :
1616 11843208 : unsigned int precision = TYPE_PRECISION (type);
1617 11843208 : signop sign = TYPE_SIGN (type);
1618 23686416 : if (r.num_pairs () > 1
1619 3135178 : && precision > 1
1620 18113564 : && r.lower_bound () == wi::min_value (precision, sign)
1621 16990702 : && r.upper_bound () == wi::max_value (precision, sign))
1622 : {
1623 532987 : int_range<3> inv (r);
1624 532987 : inv.invert ();
1625 532987 : min = wide_int_to_tree (type, inv.lower_bound (0));
1626 532987 : max = wide_int_to_tree (type, inv.upper_bound (0));
1627 532987 : return VR_ANTI_RANGE;
1628 532987 : }
1629 :
1630 11310221 : min = wide_int_to_tree (type, r.lower_bound ());
1631 11310221 : max = wide_int_to_tree (type, r.upper_bound ());
1632 11310221 : return VR_RANGE;
1633 : }
1634 :
1635 : static value_range_kind
1636 2939292 : get_legacy_range (const prange &r, tree &min, tree &max)
1637 : {
1638 2939292 : if (r.undefined_p ())
1639 : {
1640 0 : min = NULL_TREE;
1641 0 : max = NULL_TREE;
1642 0 : return VR_UNDEFINED;
1643 : }
1644 :
1645 2939292 : tree type = r.type ();
1646 2939292 : if (r.varying_p ())
1647 : {
1648 0 : min = r.lbound ();
1649 0 : max = r.ubound ();
1650 0 : return VR_VARYING;
1651 : }
1652 2939292 : if (r.zero_p ())
1653 : {
1654 2226009 : min = max = r.lbound ();
1655 2226009 : return VR_RANGE;
1656 : }
1657 713283 : if (r.nonzero_p ())
1658 : {
1659 0 : min = max = build_zero_cst (type);
1660 0 : return VR_ANTI_RANGE;
1661 : }
1662 713283 : min = r.lbound ();
1663 713283 : max = r.ubound ();
1664 713283 : return VR_RANGE;
1665 : }
1666 :
1667 : // Given a range in V, return an old-style legacy range consisting of
1668 : // a value_range_kind with a MIN/MAX. This is to maintain
1669 : // compatibility with passes that still depend on VR_ANTI_RANGE, and
1670 : // only works for integers and pointers.
1671 :
1672 : value_range_kind
1673 23652134 : get_legacy_range (const vrange &v, tree &min, tree &max)
1674 : {
1675 23652134 : if (is_a <irange> (v))
1676 20712842 : return get_legacy_range (as_a <irange> (v), min, max);
1677 :
1678 2939292 : return get_legacy_range (as_a <prange> (v), min, max);
1679 : }
1680 :
1681 : /* Set value range to the canonical form of {VRTYPE, MIN, MAX, EQUIV}.
1682 : This means adjusting VRTYPE, MIN and MAX representing the case of a
1683 : wrapping range with MAX < MIN covering [MIN, type_max] U [type_min, MAX]
1684 : as anti-rage ~[MAX+1, MIN-1]. Likewise for wrapping anti-ranges.
1685 : In corner cases where MAX+1 or MIN-1 wraps this will fall back
1686 : to varying.
1687 : This routine exists to ease canonicalization in the case where we
1688 : extract ranges from var + CST op limit. */
1689 :
1690 : void
1691 1318299559 : irange::set (tree type, const wide_int &min, const wide_int &max,
1692 : value_range_kind kind)
1693 : {
1694 1318299559 : unsigned prec = TYPE_PRECISION (type);
1695 1318299559 : signop sign = TYPE_SIGN (type);
1696 1318299559 : wide_int min_value = wi::min_value (prec, sign);
1697 1318299559 : wide_int max_value = wi::max_value (prec, sign);
1698 :
1699 1318299559 : m_type = type;
1700 1318299559 : m_bitmask.set_unknown (prec);
1701 :
1702 1318299559 : if (kind == VR_RANGE)
1703 : {
1704 1263028074 : m_base[0] = min;
1705 1263028074 : m_base[1] = max;
1706 1263028074 : m_num_ranges = 1;
1707 1684949401 : if (min == min_value && max == max_value)
1708 30339325 : m_kind = VR_VARYING;
1709 : else
1710 1232688749 : m_kind = VR_RANGE;
1711 : }
1712 : else
1713 : {
1714 55271485 : gcc_checking_assert (kind == VR_ANTI_RANGE);
1715 55271485 : gcc_checking_assert (m_max_ranges > 1);
1716 :
1717 55271485 : m_kind = VR_UNDEFINED;
1718 55271485 : m_num_ranges = 0;
1719 55271485 : wi::overflow_type ovf;
1720 55271485 : wide_int lim;
1721 55271485 : if (sign == SIGNED)
1722 26481094 : lim = wi::add (min, -1, sign, &ovf);
1723 : else
1724 28790820 : lim = wi::sub (min, 1, sign, &ovf);
1725 :
1726 55271485 : if (!ovf)
1727 : {
1728 39057617 : m_kind = VR_RANGE;
1729 39057617 : m_base[0] = min_value;
1730 39057617 : m_base[1] = lim;
1731 39057617 : ++m_num_ranges;
1732 : }
1733 55271485 : if (sign == SIGNED)
1734 26481094 : lim = wi::sub (max, -1, sign, &ovf);
1735 : else
1736 28790820 : lim = wi::add (max, 1, sign, &ovf);
1737 55271485 : if (!ovf)
1738 : {
1739 55270052 : m_kind = VR_RANGE;
1740 55270052 : m_base[m_num_ranges * 2] = lim;
1741 55270052 : m_base[m_num_ranges * 2 + 1] = max_value;
1742 55270052 : ++m_num_ranges;
1743 : }
1744 55271485 : }
1745 :
1746 1318299559 : if (flag_checking)
1747 1318294716 : verify_range ();
1748 1318299559 : }
1749 :
1750 : void
1751 214180820 : irange::set (tree min, tree max, value_range_kind kind)
1752 : {
1753 214180820 : if (POLY_INT_CST_P (min) || POLY_INT_CST_P (max))
1754 : {
1755 : set_varying (TREE_TYPE (min));
1756 : return;
1757 : }
1758 :
1759 214180820 : gcc_checking_assert (TREE_CODE (min) == INTEGER_CST);
1760 214180820 : gcc_checking_assert (TREE_CODE (max) == INTEGER_CST);
1761 :
1762 214181651 : return set (TREE_TYPE (min), wi::to_wide (min), wi::to_wide (max), kind);
1763 : }
1764 :
1765 : // Check the validity of the range.
1766 :
1767 : void
1768 4419706995 : irange::verify_range () const
1769 : {
1770 4419706995 : gcc_checking_assert (m_discriminator == VR_IRANGE);
1771 4419706995 : if (m_kind == VR_UNDEFINED)
1772 : {
1773 172189 : gcc_checking_assert (m_num_ranges == 0);
1774 : return;
1775 : }
1776 4419534806 : gcc_checking_assert (supports_p (type ()));
1777 4419534806 : gcc_checking_assert (m_num_ranges <= m_max_ranges);
1778 :
1779 : // Legacy allowed these to represent VARYING for unknown types.
1780 : // Leave this in for now, until all users are converted. Eventually
1781 : // we should abort in set_varying.
1782 4419534806 : if (m_kind == VR_VARYING && m_type == error_mark_node)
1783 : return;
1784 :
1785 4419534806 : unsigned prec = TYPE_PRECISION (m_type);
1786 4419534806 : if (m_kind == VR_VARYING)
1787 : {
1788 228272698 : gcc_checking_assert (m_bitmask.unknown_p ());
1789 228272698 : gcc_checking_assert (m_num_ranges == 1);
1790 228272698 : gcc_checking_assert (varying_compatible_p ());
1791 228272698 : gcc_checking_assert (lower_bound ().get_precision () == prec);
1792 228272698 : gcc_checking_assert (upper_bound ().get_precision () == prec);
1793 228272698 : return;
1794 : }
1795 4191262108 : gcc_checking_assert (m_num_ranges != 0);
1796 4191262108 : gcc_checking_assert (!varying_compatible_p ());
1797 10542699187 : for (unsigned i = 0; i < m_num_ranges; ++i)
1798 : {
1799 6351437079 : wide_int lb = lower_bound (i);
1800 6351437079 : wide_int ub = upper_bound (i);
1801 6351437079 : gcc_checking_assert (lb.get_precision () == prec);
1802 6351437079 : gcc_checking_assert (ub.get_precision () == prec);
1803 6351437079 : int c = wi::cmp (lb, ub, TYPE_SIGN (m_type));
1804 6351437079 : gcc_checking_assert (c == 0 || c == -1);
1805 : // Previous UB should be lower than LB
1806 6351437079 : if (i > 0)
1807 4320349942 : gcc_checking_assert (wi::lt_p (upper_bound (i - 1),
1808 : lb,
1809 : TYPE_SIGN (m_type)));
1810 6351459149 : }
1811 4191262108 : m_bitmask.verify_mask ();
1812 : }
1813 :
1814 : bool
1815 150893260 : irange::operator== (const irange &other) const
1816 : {
1817 150893260 : if (m_num_ranges != other.m_num_ranges)
1818 : return false;
1819 :
1820 143450330 : if (m_num_ranges == 0)
1821 : return true;
1822 :
1823 143288995 : signop sign1 = TYPE_SIGN (type ());
1824 143288995 : signop sign2 = TYPE_SIGN (other.type ());
1825 :
1826 181313466 : for (unsigned i = 0; i < m_num_ranges; ++i)
1827 : {
1828 148456428 : widest_int lb = widest_int::from (lower_bound (i), sign1);
1829 148456428 : widest_int ub = widest_int::from (upper_bound (i), sign1);
1830 148456428 : widest_int lb_other = widest_int::from (other.lower_bound (i), sign2);
1831 148456428 : widest_int ub_other = widest_int::from (other.upper_bound (i), sign2);
1832 238265689 : if (lb != lb_other || ub != ub_other)
1833 110431957 : return false;
1834 148456843 : }
1835 :
1836 32857038 : irange_bitmask bm1 = get_bitmask ();
1837 32857038 : irange_bitmask bm2 = other.get_bitmask ();
1838 32857038 : widest_int tmp1 = widest_int::from (bm1.mask (), sign1);
1839 32857038 : widest_int tmp2 = widest_int::from (bm2.mask (), sign2);
1840 32857038 : if (tmp1 != tmp2)
1841 : return false;
1842 32853456 : if (bm1.unknown_p ())
1843 : return true;
1844 23203080 : tmp1 = widest_int::from (bm1.value (), sign1);
1845 23203080 : tmp2 = widest_int::from (bm2.value (), sign2);
1846 23203064 : return tmp1 == tmp2;
1847 32857077 : }
1848 :
1849 : /* If range is a singleton, place it in RESULT and return TRUE. */
1850 :
1851 : bool
1852 651543093 : irange::singleton_p (tree *result) const
1853 : {
1854 1212103999 : if (num_pairs () == 1 && lower_bound () == upper_bound ())
1855 : {
1856 37623008 : if (result)
1857 7353889 : *result = wide_int_to_tree (type (), lower_bound ());
1858 37623008 : return true;
1859 : }
1860 : return false;
1861 : }
1862 :
1863 : bool
1864 488335786 : irange::singleton_p (wide_int &w) const
1865 : {
1866 658813385 : if (num_pairs () == 1 && lower_bound () == upper_bound ())
1867 : {
1868 18253108 : w = lower_bound ();
1869 18253108 : return true;
1870 : }
1871 : return false;
1872 : }
1873 :
1874 : /* Return 1 if CST is inside value range.
1875 : 0 if CST is not inside value range.
1876 :
1877 : Benchmark compile/20001226-1.c compilation time after changing this
1878 : function. */
1879 :
1880 : bool
1881 204769537 : irange::contains_p (const wide_int &cst) const
1882 : {
1883 204769537 : if (undefined_p ())
1884 : return false;
1885 :
1886 : // Check if the known bits in bitmask exclude CST.
1887 204688895 : if (!m_bitmask.member_p (cst))
1888 : return false;
1889 :
1890 204156190 : signop sign = TYPE_SIGN (type ());
1891 219331235 : for (unsigned r = 0; r < m_num_ranges; ++r)
1892 : {
1893 219071388 : if (wi::lt_p (cst, lower_bound (r), sign))
1894 : return false;
1895 123664833 : if (wi::le_p (cst, upper_bound (r), sign))
1896 : return true;
1897 : }
1898 :
1899 : return false;
1900 : }
1901 :
1902 : // Perform an efficient union with R when both ranges have only a single pair.
1903 : // Excluded are VARYING and UNDEFINED ranges.
1904 :
1905 : bool
1906 110899228 : irange::irange_single_pair_union (const irange &r)
1907 : {
1908 110899228 : gcc_checking_assert (!undefined_p () && !varying_p ());
1909 110899228 : gcc_checking_assert (!r.undefined_p () && !varying_p ());
1910 :
1911 110899228 : signop sign = TYPE_SIGN (m_type);
1912 : // Check if current lower bound is also the new lower bound.
1913 110899228 : if (wi::le_p (m_base[0], r.m_base[0], sign))
1914 : {
1915 : // If current upper bound is new upper bound, we're done.
1916 97141169 : if (wi::le_p (r.m_base[1], m_base[1], sign))
1917 14061815 : return union_bitmask (r);
1918 : // Otherwise R has the new upper bound.
1919 : // Check for overlap/touching ranges, or single target range.
1920 166158708 : if (m_max_ranges == 1
1921 332317404 : || (widest_int::from (m_base[1], sign) + 1
1922 332317404 : >= widest_int::from (r.m_base[0], TYPE_SIGN (r.m_type))))
1923 25983529 : m_base[1] = r.m_base[1];
1924 : else
1925 : {
1926 : // This is a dual range result.
1927 57095825 : m_base[2] = r.m_base[0];
1928 57095825 : m_base[3] = r.m_base[1];
1929 57095825 : m_num_ranges = 2;
1930 : }
1931 : // The range has been altered, so normalize it even if nothing
1932 : // changed in the mask.
1933 83079354 : if (!union_bitmask (r))
1934 82215632 : normalize_kind ();
1935 83079354 : if (flag_checking)
1936 83079236 : verify_range ();
1937 83079354 : return true;
1938 : }
1939 :
1940 : // Set the new lower bound to R's lower bound.
1941 13758059 : wide_int lb = m_base[0];
1942 13758059 : m_base[0] = r.m_base[0];
1943 :
1944 : // If R fully contains THIS range, just set the upper bound.
1945 13758059 : if (wi::ge_p (r.m_base[1], m_base[1], sign))
1946 1435450 : m_base[1] = r.m_base[1];
1947 : // Check for overlapping ranges, or target limited to a single range.
1948 24645218 : else if (m_max_ranges == 1
1949 49290436 : || (widest_int::from (r.m_base[1], TYPE_SIGN (r.m_type)) + 1
1950 49290436 : >= widest_int::from (lb, sign)))
1951 : ;
1952 : else
1953 : {
1954 : // Left with 2 pairs.
1955 6003873 : m_num_ranges = 2;
1956 6003873 : m_base[2] = lb;
1957 6003873 : m_base[3] = m_base[1];
1958 6003873 : m_base[1] = r.m_base[1];
1959 : }
1960 : // The range has been altered, so normalize it even if nothing
1961 : // changed in the mask.
1962 13758059 : if (!union_bitmask (r))
1963 12683449 : normalize_kind ();
1964 13758059 : if (flag_checking)
1965 13758048 : verify_range ();
1966 13758059 : return true;
1967 13758059 : }
1968 :
1969 : // Append R to this range, knowing that R occurs after all of these subranges.
1970 : // Return TRUE as something must have changed.
1971 :
1972 : bool
1973 138555874 : irange::union_append (const irange &r)
1974 : {
1975 : // Check if the first range in R is an immediate successor to the last
1976 : // range, thus requiring a merge.
1977 138555874 : signop sign = TYPE_SIGN (m_type);
1978 138555874 : wide_int lb = r.lower_bound ();
1979 138555874 : wide_int ub = upper_bound ();
1980 138555874 : unsigned start = 0;
1981 415667622 : if (widest_int::from (ub, sign) + 1
1982 415667622 : == widest_int::from (lb, sign))
1983 : {
1984 854703 : m_base[m_num_ranges * 2 - 1] = r.m_base[1];
1985 854703 : start = 1;
1986 : }
1987 138555874 : maybe_resize (m_num_ranges + r.m_num_ranges - start);
1988 414869768 : for ( ; start < r.m_num_ranges; start++)
1989 : {
1990 : // Merge the last ranges if it exceeds the maximum size.
1991 138544609 : if (m_num_ranges + 1 > m_max_ranges)
1992 : {
1993 786589 : m_base[m_max_ranges * 2 - 1] = r.m_base[r.m_num_ranges * 2 - 1];
1994 786589 : break;
1995 : }
1996 137758020 : m_base[m_num_ranges * 2] = r.m_base[start * 2];
1997 137758020 : m_base[m_num_ranges * 2 + 1] = r.m_base[start * 2 + 1];
1998 137758020 : m_num_ranges++;
1999 : }
2000 :
2001 138555874 : if (!union_bitmask (r))
2002 138518382 : normalize_kind ();
2003 138555874 : if (flag_checking)
2004 138555874 : verify_range ();
2005 138555874 : return true;
2006 138555874 : }
2007 :
2008 : // Return TRUE if anything changes.
2009 :
2010 : bool
2011 383338507 : irange::union_ (const vrange &v)
2012 : {
2013 383338507 : const irange &r = as_a <irange> (v);
2014 :
2015 383338507 : if (r.undefined_p ())
2016 : return false;
2017 :
2018 381204098 : if (undefined_p ())
2019 : {
2020 90943181 : operator= (r);
2021 90943181 : if (flag_checking)
2022 90942625 : verify_range ();
2023 90943181 : return true;
2024 : }
2025 :
2026 290260917 : if (varying_p ())
2027 : return false;
2028 :
2029 280781576 : if (r.varying_p ())
2030 : {
2031 6463637 : set_varying (type ());
2032 6463637 : return true;
2033 : }
2034 :
2035 : // Special case one range union one range.
2036 274317939 : if (m_num_ranges == 1 && r.m_num_ranges == 1)
2037 110899228 : return irange_single_pair_union (r);
2038 :
2039 163418711 : signop sign = TYPE_SIGN (m_type);
2040 : // Check for an append to the end.
2041 490256133 : if (m_kind == VR_RANGE && wi::gt_p (r.lower_bound (), upper_bound (), sign))
2042 138555874 : return union_append (r);
2043 :
2044 : // If this ranges fully contains R, then we need do nothing.
2045 24862837 : if (irange_contains_p (r))
2046 3817341 : return union_bitmask (r);
2047 :
2048 : // Do not worry about merging and such by reserving twice as many
2049 : // pairs as needed, and then simply sort the 2 ranges into this
2050 : // intermediate form.
2051 : //
2052 : // The intermediate result will have the property that the beginning
2053 : // of each range is <= the beginning of the next range. There may
2054 : // be overlapping ranges at this point. I.e. this would be valid
2055 : // [-20, 10], [-10, 0], [0, 20], [40, 90] as it satisfies this
2056 : // constraint : -20 < -10 < 0 < 40. When the range is rebuilt into r,
2057 : // the merge is performed.
2058 : //
2059 : // [Xi,Yi]..[Xn,Yn] U [Xj,Yj]..[Xm,Ym] --> [Xk,Yk]..[Xp,Yp]
2060 21045496 : auto_vec<wide_int, 20> res (m_num_ranges * 2 + r.m_num_ranges * 2);
2061 21045496 : unsigned i = 0, j = 0, k = 0;
2062 :
2063 91474326 : while (i < m_num_ranges * 2 && j < r.m_num_ranges * 2)
2064 : {
2065 : // lower of Xi and Xj is the lowest point.
2066 98766668 : if (widest_int::from (m_base[i], sign)
2067 148150002 : <= widest_int::from (r.m_base[j], sign))
2068 : {
2069 25706275 : res.quick_push (m_base[i]);
2070 25706275 : res.quick_push (m_base[i + 1]);
2071 25706275 : k += 2;
2072 25706275 : i += 2;
2073 : }
2074 : else
2075 : {
2076 23677059 : res.quick_push (r.m_base[j]);
2077 23677059 : res.quick_push (r.m_base[j + 1]);
2078 23677059 : k += 2;
2079 23677059 : j += 2;
2080 : }
2081 : }
2082 43096862 : for ( ; i < m_num_ranges * 2; i += 2)
2083 : {
2084 22051366 : res.quick_push (m_base[i]);
2085 22051366 : res.quick_push (m_base[i + 1]);
2086 22051366 : k += 2;
2087 : }
2088 26937702 : for ( ; j < r.m_num_ranges * 2; j += 2)
2089 : {
2090 5892206 : res.quick_push (r.m_base[j]);
2091 5892206 : res.quick_push (r.m_base[j + 1]);
2092 5892206 : k += 2;
2093 : }
2094 :
2095 : // Now normalize the vector removing any overlaps.
2096 : i = 2;
2097 77326906 : for (j = 2; j < k ; j += 2)
2098 : {
2099 : // Current upper+1 is >= lower bound next pair, then we merge ranges.
2100 168844243 : if (widest_int::from (res[i - 1], sign) + 1
2101 168844230 : >= widest_int::from (res[j], sign))
2102 : {
2103 : // New upper bounds is greater of current or the next one.
2104 48631824 : if (widest_int::from (res[j + 1], sign)
2105 72947736 : > widest_int::from (res[i - 1], sign))
2106 18462245 : res[i - 1] = res[j + 1];
2107 : }
2108 : else
2109 : {
2110 : // This is a new distinct range, but no point in copying it
2111 : // if it is already in the right place.
2112 31965498 : if (i != j)
2113 : {
2114 10202311 : res[i++] = res[j];
2115 10202311 : res[i++] = res[j + 1];
2116 : }
2117 : else
2118 21763187 : i += 2;
2119 : }
2120 : }
2121 :
2122 : // At this point, the vector should have i ranges, none overlapping.
2123 : // Now it simply needs to be copied, and if there are too many
2124 : // ranges, merge some. We wont do any analysis as to what the
2125 : // "best" merges are, simply combine the final ranges into one.
2126 21045496 : maybe_resize (i / 2);
2127 21045496 : if (i > m_max_ranges * 2)
2128 : {
2129 1552 : res[m_max_ranges * 2 - 1] = res[i - 1];
2130 1552 : i = m_max_ranges * 2;
2131 : }
2132 :
2133 127064380 : for (j = 0; j < i ; j++)
2134 106018884 : m_base[j] = res [j];
2135 21045496 : m_num_ranges = i / 2;
2136 :
2137 21045496 : m_kind = VR_RANGE;
2138 : // The range has been altered, so normalize it even if nothing
2139 : // changed in the mask.
2140 21045496 : if (!union_bitmask (r))
2141 20119587 : normalize_kind ();
2142 21045496 : if (flag_checking)
2143 21045449 : verify_range ();
2144 21045496 : return true;
2145 21045496 : }
2146 :
2147 : // Return TRUE if THIS fully contains R. No undefined or varying cases.
2148 :
2149 : bool
2150 177914893 : irange::irange_contains_p (const irange &r) const
2151 : {
2152 177914893 : gcc_checking_assert (!undefined_p () && !varying_p ());
2153 177914893 : gcc_checking_assert (!r.undefined_p () && !varying_p ());
2154 :
2155 : // Check singletons directly which will include any bitmasks.
2156 177914893 : wide_int rl;
2157 177914893 : if (r.singleton_p (rl))
2158 13512596 : return contains_p (rl);
2159 :
2160 : // In order for THIS to fully contain R, all of the pairs within R must
2161 : // be fully contained by the pairs in this object.
2162 164402297 : signop sign = TYPE_SIGN (m_type);
2163 164402297 : unsigned ri = 0;
2164 164402297 : unsigned i = 0;
2165 164402297 : rl = r.m_base[0];
2166 164402297 : wide_int ru = r.m_base[1];
2167 164402297 : wide_int l = m_base[0];
2168 164402297 : wide_int u = m_base[1];
2169 427454898 : while (1)
2170 : {
2171 : // If r is contained within this range, move to the next R
2172 427454898 : if (wi::ge_p (rl, l, sign)
2173 427454898 : && wi::le_p (ru, u, sign))
2174 : {
2175 : // This pair is OK, Either done, or bump to the next.
2176 200429917 : if (++ri >= r.num_pairs ())
2177 : return true;
2178 130380829 : rl = r.m_base[ri * 2];
2179 130380829 : ru = r.m_base[ri * 2 + 1];
2180 130380829 : continue;
2181 : }
2182 : // Otherwise, check if this's pair occurs before R's.
2183 227024981 : if (wi::lt_p (u, rl, sign))
2184 : {
2185 : // There's still at least one pair of R left.
2186 133399237 : if (++i >= num_pairs ())
2187 : return false;
2188 132671772 : l = m_base[i * 2];
2189 132671772 : u = m_base[i * 2 + 1];
2190 132671772 : continue;
2191 : }
2192 : return false;
2193 : }
2194 : return false;
2195 164404591 : }
2196 :
2197 :
2198 : // Return TRUE if anything changes.
2199 :
2200 : bool
2201 876782134 : irange::intersect (const vrange &v)
2202 : {
2203 876782134 : const irange &r = as_a <irange> (v);
2204 876782134 : gcc_checking_assert (undefined_p () || r.undefined_p ()
2205 : || range_compatible_p (type (), r.type ()));
2206 :
2207 876782134 : if (undefined_p ())
2208 : return false;
2209 875735185 : if (r.undefined_p ())
2210 : {
2211 437028 : set_undefined ();
2212 437028 : return true;
2213 : }
2214 875298157 : if (r.varying_p ())
2215 : return false;
2216 587373986 : if (varying_p ())
2217 : {
2218 80519164 : operator= (r);
2219 80519164 : return true;
2220 : }
2221 :
2222 506854822 : if (r.num_pairs () == 1)
2223 : {
2224 353795759 : bool res = intersect (r.lower_bound (), r.upper_bound ());
2225 353794088 : if (undefined_p ())
2226 : return true;
2227 :
2228 328654194 : res |= intersect_bitmask (r);
2229 328654194 : if (res)
2230 113179177 : normalize_kind ();
2231 328654194 : return res;
2232 : }
2233 :
2234 : // If either range is a singleton and the other range does not contain
2235 : // it, the result is undefined.
2236 153060734 : wide_int val;
2237 154165858 : if ((singleton_p (val) && !r.contains_p (val))
2238 154157180 : || (r.singleton_p (val) && !contains_p (val)))
2239 : {
2240 8678 : set_undefined ();
2241 8678 : return true;
2242 : }
2243 :
2244 : // If R fully contains this, then intersection will change nothing.
2245 153052056 : if (r.irange_contains_p (*this))
2246 68770589 : return intersect_bitmask (r);
2247 :
2248 : // ?? We could probably come up with something smarter than the
2249 : // worst case scenario here.
2250 84281467 : int needed = num_pairs () + r.num_pairs ();
2251 84281467 : maybe_resize (needed);
2252 :
2253 84281467 : signop sign = TYPE_SIGN (m_type);
2254 84281467 : unsigned bld_pair = 0;
2255 84281467 : unsigned bld_lim = m_max_ranges;
2256 84281467 : int_range_max r2 (*this);
2257 84281467 : unsigned r2_lim = r2.num_pairs ();
2258 84281467 : unsigned i2 = 0;
2259 84281467 : bool need_snapping = !m_bitmask.unknown_p ();
2260 245438541 : for (unsigned i = 0; i < r.num_pairs (); )
2261 : {
2262 : // If r1's upper is < r2's lower, we can skip r1's pair.
2263 218535298 : wide_int ru = r.m_base[i * 2 + 1];
2264 218535298 : wide_int r2l = r2.m_base[i2 * 2];
2265 218535298 : if (wi::lt_p (ru, r2l, sign))
2266 : {
2267 20699328 : i++;
2268 20699328 : continue;
2269 : }
2270 : // Likewise, skip r2's pair if its excluded.
2271 197835970 : wide_int r2u = r2.m_base[i2 * 2 + 1];
2272 197835970 : wide_int rl = r.m_base[i * 2];
2273 197835970 : if (wi::lt_p (r2u, rl, sign))
2274 : {
2275 20563402 : i2++;
2276 20563402 : if (i2 < r2_lim)
2277 16247431 : continue;
2278 : // No more r2, break.
2279 : break;
2280 : }
2281 :
2282 : // Must be some overlap. Find the highest of the lower bounds,
2283 : // and set it, unless the build limits lower bounds is already
2284 : // set.
2285 177272568 : if (bld_pair < bld_lim)
2286 : {
2287 176969922 : if (wi::ge_p (rl, r2l, sign))
2288 150220588 : m_base[bld_pair * 2] = rl;
2289 : else
2290 26749334 : m_base[bld_pair * 2] = r2l;
2291 : }
2292 : else
2293 : // Decrease the index to use the existing lower bound, and
2294 : // set a new upper for this pair.
2295 302646 : bld_pair--;
2296 :
2297 : // Changes to false if the last value in i2's range is consumed.
2298 177272568 : bool more = true;
2299 : // ...and choose the lower of the upper bounds.
2300 177272568 : if (wi::le_p (ru, r2u, sign))
2301 : {
2302 112724837 : m_base[bld_pair * 2 + 1] = ru;
2303 : // Move past the r1 pair and keep trying.
2304 112724837 : i++;
2305 : }
2306 : else
2307 : {
2308 64547731 : m_base[bld_pair * 2 + 1] = r2u;
2309 64547731 : i2++;
2310 : // No more r2, break the loop when done.
2311 64547731 : if (i2 >= r2_lim)
2312 53062253 : more = false;
2313 : }
2314 : // Now snap these ranges to the bitmask, if there is one.
2315 177272568 : if (need_snapping)
2316 : {
2317 51573094 : bool ovf;
2318 51573094 : wide_int lb, ub;
2319 51573094 : if (snap (m_base[bld_pair * 2], m_base[bld_pair * 2 + 1],
2320 : lb, ub, ovf))
2321 : {
2322 : // If the new subrange does not fit the mask, skip it.
2323 1108250 : if (ovf)
2324 : {
2325 4088 : if (!more)
2326 : break;
2327 4088 : continue;
2328 : }
2329 : // Otherwise adjust the pair.
2330 1104162 : m_base[bld_pair * 2] = lb;
2331 1104162 : m_base[bld_pair * 2 + 1] = ub;
2332 : }
2333 51573094 : }
2334 : // Current pair now satisfies any mask, ready for another pair.
2335 177268480 : bld_pair++;
2336 177268480 : if (!more)
2337 : break;
2338 234788598 : }
2339 :
2340 : // At the exit of this loop, it is one of 2 things:
2341 : // ran out of r1, or r2, but either means we are done.
2342 84281467 : m_num_ranges = bld_pair;
2343 84281467 : if (m_num_ranges == 0)
2344 : {
2345 95594 : set_undefined ();
2346 95594 : return true;
2347 : }
2348 :
2349 84185873 : m_kind = VR_RANGE;
2350 : // The range has been altered, so normalize it even if nothing
2351 : // changed in the mask.
2352 84185873 : if (!intersect_bitmask (r))
2353 77640779 : normalize_kind ();
2354 84185873 : if (flag_checking)
2355 84185851 : verify_range ();
2356 : return true;
2357 237342201 : }
2358 :
2359 :
2360 : // Multirange intersect for a specified wide_int [lb, ub] range.
2361 : // Return TRUE if intersect changed anything.
2362 : //
2363 : // NOTE: It is the caller's responsibility to intersect the mask.
2364 :
2365 : bool
2366 353794088 : irange::intersect (const wide_int& lb, const wide_int& ub)
2367 : {
2368 : // Undefined remains undefined.
2369 353794088 : if (undefined_p ())
2370 : return false;
2371 :
2372 353794088 : tree range_type = type();
2373 353794088 : signop sign = TYPE_SIGN (range_type);
2374 :
2375 353794088 : gcc_checking_assert (TYPE_PRECISION (range_type) == wi::get_precision (lb));
2376 353794088 : gcc_checking_assert (TYPE_PRECISION (range_type) == wi::get_precision (ub));
2377 :
2378 : // If this range is fully contained, then intersection will do nothing.
2379 707588176 : if (wi::ge_p (lower_bound (), lb, sign)
2380 637461963 : && wi::le_p (upper_bound (), ub, sign))
2381 : return false;
2382 :
2383 125915742 : unsigned bld_index = 0;
2384 125915742 : unsigned pair_lim = num_pairs ();
2385 189058532 : for (unsigned i = 0; i < pair_lim; i++)
2386 : {
2387 139435107 : wide_int pairl = m_base[i * 2];
2388 139435107 : wide_int pairu = m_base[i * 2 + 1];
2389 : // Once UB is less than a pairs lower bound, we're done.
2390 139435107 : if (wi::lt_p (ub, pairl, sign))
2391 : break;
2392 : // if LB is greater than this pairs upper, this pair is excluded.
2393 119101787 : if (wi::lt_p (pairu, lb, sign))
2394 16790391 : continue;
2395 :
2396 : // Must be some overlap. Find the highest of the lower bounds,
2397 : // and set it
2398 102311396 : if (wi::gt_p (lb, pairl, sign))
2399 55442777 : m_base[bld_index * 2] = lb;
2400 : else
2401 46868619 : m_base[bld_index * 2] = pairl;
2402 :
2403 : // ...and choose the lower of the upper bounds and if the base pair
2404 : // has the lower upper bound, need to check next pair too.
2405 102311396 : if (wi::lt_p (ub, pairu, sign))
2406 : {
2407 55958997 : m_base[bld_index++ * 2 + 1] = ub;
2408 55958997 : break;
2409 : }
2410 : else
2411 46352399 : m_base[bld_index++ * 2 + 1] = pairu;
2412 139435559 : }
2413 :
2414 125915742 : m_num_ranges = bld_index;
2415 125915742 : if (m_num_ranges == 0)
2416 : {
2417 25139894 : set_undefined ();
2418 25139894 : return true;
2419 : }
2420 :
2421 100775848 : m_kind = VR_RANGE;
2422 : // The caller must normalize and verify the range, as the bitmask
2423 : // still needs to be handled.
2424 100775848 : return true;
2425 : }
2426 :
2427 :
2428 : // Signed 1-bits are strange. You can't subtract 1, because you can't
2429 : // represent the number 1. This works around that for the invert routine.
2430 :
2431 : static wide_int inline
2432 56101460 : subtract_one (const wide_int &x, tree type, wi::overflow_type &overflow)
2433 : {
2434 56101460 : if (TYPE_SIGN (type) == SIGNED)
2435 34202915 : return wi::add (x, -1, SIGNED, &overflow);
2436 : else
2437 21898545 : return wi::sub (x, 1, UNSIGNED, &overflow);
2438 : }
2439 :
2440 : // The analogous function for adding 1.
2441 :
2442 : static wide_int inline
2443 58070389 : add_one (const wide_int &x, tree type, wi::overflow_type &overflow)
2444 : {
2445 58070389 : if (TYPE_SIGN (type) == SIGNED)
2446 28763505 : return wi::sub (x, -1, SIGNED, &overflow);
2447 : else
2448 29306884 : return wi::add (x, 1, UNSIGNED, &overflow);
2449 : }
2450 :
2451 : // Return the inverse of a range.
2452 :
2453 : void
2454 58906463 : irange::invert ()
2455 : {
2456 58906463 : gcc_checking_assert (!undefined_p () && !varying_p ());
2457 :
2458 : // We always need one more set of bounds to represent an inverse, so
2459 : // if we're at the limit, we can't properly represent things.
2460 : //
2461 : // For instance, to represent the inverse of a 2 sub-range set
2462 : // [5, 10][20, 30], we would need a 3 sub-range set
2463 : // [-MIN, 4][11, 19][31, MAX].
2464 : //
2465 : // In this case, return the most conservative thing.
2466 : //
2467 : // However, if any of the extremes of the range are -MIN/+MAX, we
2468 : // know we will not need an extra bound. For example:
2469 : //
2470 : // INVERT([-MIN,20][30,40]) => [21,29][41,+MAX]
2471 : // INVERT([-MIN,20][30,MAX]) => [21,29]
2472 58906463 : tree ttype = type ();
2473 58906463 : unsigned prec = TYPE_PRECISION (ttype);
2474 58906463 : signop sign = TYPE_SIGN (ttype);
2475 58906463 : wide_int type_min = wi::min_value (prec, sign);
2476 58906463 : wide_int type_max = wi::max_value (prec, sign);
2477 58906463 : m_bitmask.set_unknown (prec);
2478 :
2479 : // At this point, we need one extra sub-range to represent the
2480 : // inverse.
2481 58906463 : maybe_resize (m_num_ranges + 1);
2482 :
2483 : // The algorithm is as follows. To calculate INVERT ([a,b][c,d]), we
2484 : // generate [-MIN, a-1][b+1, c-1][d+1, MAX].
2485 : //
2486 : // If there is an over/underflow in the calculation for any
2487 : // sub-range, we eliminate that subrange. This allows us to easily
2488 : // calculate INVERT([-MIN, 5]) with: [-MIN, -MIN-1][6, MAX]. And since
2489 : // we eliminate the underflow, only [6, MAX] remains.
2490 58906463 : unsigned i = 0;
2491 58906463 : wi::overflow_type ovf;
2492 : // Construct leftmost range.
2493 58906463 : int_range_max orig_range (*this);
2494 58906463 : unsigned nitems = 0;
2495 58906463 : wide_int tmp;
2496 : // If this is going to underflow on the MINUS 1, don't even bother
2497 : // checking. This also handles subtracting one from an unsigned 0,
2498 : // which doesn't set the underflow bit.
2499 58906508 : if (type_min != orig_range.lower_bound ())
2500 : {
2501 48654895 : m_base[nitems++] = type_min;
2502 48654940 : tmp = subtract_one (orig_range.lower_bound (), ttype, ovf);
2503 48654895 : m_base[nitems++] = tmp;
2504 48654895 : if (ovf)
2505 10251568 : nitems = 0;
2506 : }
2507 58906463 : i++;
2508 : // Construct middle ranges if applicable.
2509 58906463 : if (orig_range.num_pairs () > 1)
2510 : {
2511 : unsigned j = i;
2512 14883016 : for (; j < (orig_range.num_pairs () * 2) - 1; j += 2)
2513 : {
2514 : // The middle ranges cannot have MAX/MIN, so there's no need
2515 : // to check for unsigned overflow on the +1 and -1 here.
2516 7446565 : tmp = wi::add (orig_range.m_base[j], 1, sign, &ovf);
2517 7446565 : m_base[nitems++] = tmp;
2518 7446565 : tmp = subtract_one (orig_range.m_base[j + 1], ttype, ovf);
2519 7446565 : m_base[nitems++] = tmp;
2520 7446565 : if (ovf)
2521 0 : nitems -= 2;
2522 : }
2523 : i = j;
2524 : }
2525 : // Construct rightmost range.
2526 : //
2527 : // However, if this will overflow on the PLUS 1, don't even bother.
2528 : // This also handles adding one to an unsigned MAX, which doesn't
2529 : // set the overflow bit.
2530 58906463 : if (type_max != orig_range.m_base[i])
2531 : {
2532 58070389 : tmp = add_one (orig_range.m_base[i], ttype, ovf);
2533 58070389 : m_base[nitems++] = tmp;
2534 58070389 : m_base[nitems++] = type_max;
2535 58070389 : if (ovf)
2536 836074 : nitems -= 2;
2537 : }
2538 58906463 : m_num_ranges = nitems / 2;
2539 :
2540 : // We disallow undefined or varying coming in, so the result can
2541 : // only be a VR_RANGE.
2542 58906463 : gcc_checking_assert (m_kind == VR_RANGE);
2543 :
2544 58906463 : if (flag_checking)
2545 58906369 : verify_range ();
2546 58906508 : }
2547 :
2548 : // This routine will take the bounds [LB, UB], and apply the bitmask to those
2549 : // values such that both bounds satisfy the bitmask. TRUE is returned
2550 : // if either bound changes, and they are returned as [NEW_LB, NEW_UB].
2551 : // If there is an overflow, or if (NEW_UB < NEW_LB), then the entire bound is
2552 : // to be removed as none of the values are valid. This is indicated by
2553 : // teturning TRUE in OVF. False indicates the bounds are fine.
2554 : // ie, [4, 14] MASK 0xFFFE VALUE 0x1
2555 : // means all values must be odd, the new bounds returned will be [5, 13] with
2556 : // OVF set to FALSE.
2557 : // ie, [4, 4] MASK 0xFFFE VALUE 0x1
2558 : // would return TRUE and OVF == TRUE. The entire subrange should be removed.
2559 :
2560 : bool
2561 220859158 : irange::snap (const wide_int &lb, const wide_int &ub,
2562 : wide_int &new_lb, wide_int &new_ub, bool &ovf)
2563 : {
2564 220859158 : ovf = false;
2565 220859158 : int z = wi::ctz (m_bitmask.mask ());
2566 220859158 : if (z == 0)
2567 : return false;
2568 :
2569 : // Shortcircuit check for values that are already good.
2570 260278358 : if ((((lb ^ m_bitmask.value ()) | (ub ^ m_bitmask.value ()))
2571 390417145 : & ~m_bitmask.mask ()) == 0)
2572 : return false;
2573 :
2574 13580814 : const wide_int step = (wi::one (TYPE_PRECISION (type ())) << z);
2575 13580814 : const wide_int match_mask = step - 1;
2576 13580814 : const wide_int value = m_bitmask.value () & match_mask;
2577 :
2578 13580814 : wide_int rem_lb = lb & match_mask;
2579 13580814 : wide_int offset = (value - rem_lb) & match_mask;
2580 13580814 : new_lb = lb + offset;
2581 : // Check for overflows at +INF
2582 13580814 : if (wi::lt_p (new_lb, lb, TYPE_SIGN (type ())))
2583 : {
2584 1948 : ovf = true;
2585 1948 : return true;
2586 : }
2587 :
2588 13578866 : wide_int rem_ub = ub & match_mask;
2589 13578866 : wide_int offset_ub = (rem_ub - value) & match_mask;
2590 13578866 : new_ub = ub - offset_ub;
2591 : // Check for underflows at -INF
2592 13578866 : if (wi::gt_p (new_ub, ub, TYPE_SIGN (type ())))
2593 : {
2594 117040 : ovf = true;
2595 117040 : return true;
2596 : }
2597 :
2598 : // If inverted range is invalid, set overflow to TRUE.
2599 13461826 : if (wi::lt_p (new_ub, new_lb, TYPE_SIGN (type ())))
2600 : {
2601 9891 : ovf = true;
2602 9891 : return true;
2603 : }
2604 24398424 : return (new_lb != lb) || (new_ub != ub);
2605 27159760 : }
2606 :
2607 : // This method loops through the subranges in THIS, and adjusts any bounds
2608 : // to satisfy the constraints of the BITMASK. If a subrange is invalid,
2609 : // it is removed. TRUE is returned if there were any changes.
2610 :
2611 : bool
2612 121294814 : irange::snap_subranges ()
2613 : {
2614 121294814 : bool changed = false;
2615 121294814 : int_range_max invalid;
2616 121294814 : unsigned x;
2617 121294814 : wide_int lb, ub;
2618 290580878 : for (x = 0; x < m_num_ranges; x++)
2619 : {
2620 169286064 : bool ovf;
2621 169287776 : if (snap (lower_bound (x), upper_bound (x), lb, ub, ovf))
2622 : {
2623 12239044 : changed = true;
2624 : // Check if this subrange is to be completely removed.
2625 12239044 : if (ovf)
2626 : {
2627 124791 : int_range<1> tmp (type (), lower_bound (x), upper_bound (x));
2628 124791 : invalid.union_ (tmp);
2629 124791 : continue;
2630 124791 : }
2631 12114269 : if (lower_bound (x) != lb)
2632 1733511 : m_base[x * 2] = lb;
2633 12114269 : if (upper_bound (x) != ub)
2634 10982710 : m_base[x * 2 + 1] = ub;
2635 : }
2636 : }
2637 : // Remove any subranges which are no invalid.
2638 121294814 : if (!invalid.undefined_p ())
2639 : {
2640 123842 : invalid.invert ();
2641 123842 : intersect (invalid);
2642 : }
2643 121294814 : return changed;
2644 121294830 : }
2645 :
2646 : // If the bitmask has a range representation, intersect this range with
2647 : // the bitmasks range. Then ensure all endpoints match the bitmask.
2648 : // Return TRUE if the range changes at all.
2649 :
2650 : bool
2651 121294814 : irange::set_range_from_bitmask ()
2652 : {
2653 121294814 : gcc_checking_assert (!undefined_p ());
2654 : // Snap subranmges when bitmask is first set.
2655 121294814 : snap_subranges ();
2656 121294814 : if (undefined_p ())
2657 : return true;
2658 :
2659 : // Calculate the set of ranges valid for the bitmask.
2660 121294769 : int_range_max allow;
2661 121294769 : if (!m_bitmask.range_from_mask (allow, m_type))
2662 : return false;
2663 : // And intersect that set of ranges with the current set.
2664 121233592 : return intersect (allow);
2665 121294769 : }
2666 :
2667 : void
2668 176808821 : irange::update_bitmask (const irange_bitmask &bm)
2669 : {
2670 176808821 : gcc_checking_assert (!undefined_p ());
2671 :
2672 : // If masks are the same, there is no change.
2673 176808821 : if (m_bitmask == bm)
2674 : return;
2675 :
2676 : // Drop VARYINGs with known bits to a plain range.
2677 86434360 : if (m_kind == VR_VARYING && !bm.unknown_p ())
2678 15511837 : m_kind = VR_RANGE;
2679 :
2680 70922523 : m_bitmask = bm;
2681 70922523 : if (!set_range_from_bitmask ())
2682 41731223 : normalize_kind ();
2683 70922523 : if (flag_checking)
2684 70922427 : verify_range ();
2685 : }
2686 :
2687 : // Return the bitmask of known bits that includes the bitmask inherent
2688 : // in the range.
2689 :
2690 : irange_bitmask
2691 1076104516 : irange::get_bitmask () const
2692 : {
2693 1076104516 : gcc_checking_assert (!undefined_p ());
2694 :
2695 : // The mask inherent in the range is calculated on-demand. For
2696 : // example, [0,255] does not have known bits set by default. This
2697 : // saves us considerable time, because setting it at creation incurs
2698 : // a large penalty for irange::set. At the time of writing there
2699 : // was a 5% slowdown in VRP if we kept the mask precisely up to date
2700 : // at all times. Instead, we default to -1 and set it when
2701 : // explicitly requested. However, this function will always return
2702 : // the correct mask.
2703 : //
2704 : // This also means that the mask may have a finer granularity than
2705 : // the range and thus contradict it. Think of the mask as an
2706 : // enhancement to the range. For example:
2707 : //
2708 : // [3, 1000] MASK 0xfffffffe VALUE 0x0
2709 : //
2710 : // 3 is in the range endpoints, but is excluded per the known 0 bits
2711 : // in the mask.
2712 : //
2713 : // See also the note in irange_bitmask::intersect.
2714 1076110714 : irange_bitmask bm (type (), lower_bound (), upper_bound ());
2715 1076104516 : if (!m_bitmask.unknown_p ())
2716 : {
2717 : // If the new intersection is unknown, it means there are inconsistent
2718 : // bits, so simply return the original bitmask.
2719 498896267 : if (!bm.intersect (m_bitmask))
2720 18363 : return m_bitmask;
2721 : }
2722 1076086153 : return bm;
2723 1076104516 : }
2724 :
2725 : // Set the nonzero bits in R into THIS. Return TRUE and
2726 : // normalize the range if anything changed.
2727 :
2728 : void
2729 621103 : vrange::set_nonzero_bits (const wide_int &bits)
2730 : {
2731 621103 : gcc_checking_assert (!undefined_p ());
2732 621103 : irange_bitmask bm (wi::zero (TYPE_PRECISION (type ())), bits);
2733 621103 : update_bitmask (bm);
2734 621103 : }
2735 :
2736 : // Return the nonzero bits in R.
2737 :
2738 : wide_int
2739 224726149 : vrange::get_nonzero_bits () const
2740 : {
2741 224726149 : gcc_checking_assert (!undefined_p ());
2742 224726149 : irange_bitmask bm = get_bitmask ();
2743 224726715 : return bm.value () | bm.mask ();
2744 224726149 : }
2745 :
2746 : // Intersect the bitmask in R into THIS and normalize the range.
2747 : // Return TRUE if the intersection changed anything.
2748 :
2749 : bool
2750 481610656 : irange::intersect_bitmask (const irange &r)
2751 : {
2752 481610656 : gcc_checking_assert (!undefined_p () && !r.undefined_p ());
2753 :
2754 : // If the bitmasks are the same, do nothing.
2755 481610656 : if (m_bitmask == r.m_bitmask)
2756 : return false;
2757 :
2758 175288672 : irange_bitmask bm = get_bitmask ();
2759 175288672 : irange_bitmask save = bm;
2760 175288672 : if (!bm.intersect (r.get_bitmask ()))
2761 : {
2762 25544 : set_undefined ();
2763 25544 : return true;
2764 : }
2765 :
2766 : // If the new mask is the same, there is no change.
2767 175263128 : if (m_bitmask == bm)
2768 : return false;
2769 :
2770 50372291 : m_bitmask = bm;
2771 50372291 : if (!set_range_from_bitmask ())
2772 49970602 : normalize_kind ();
2773 50372291 : if (flag_checking)
2774 50372138 : verify_range ();
2775 : return true;
2776 175288672 : }
2777 :
2778 : // Union the bitmask in R into THIS. Return TRUE and normalize the
2779 : // range if anything changed.
2780 :
2781 : bool
2782 274317939 : irange::union_bitmask (const irange &r)
2783 : {
2784 274317939 : gcc_checking_assert (!undefined_p () && !r.undefined_p ());
2785 :
2786 274317939 : if (m_bitmask == r.m_bitmask)
2787 : return false;
2788 :
2789 12468681 : irange_bitmask bm = get_bitmask ();
2790 12468681 : irange_bitmask save = bm;
2791 12468681 : bm.union_ (r.get_bitmask ());
2792 22002079 : if (save == bm && (!bm.unknown_p () || m_bitmask.unknown_p ()))
2793 9533398 : return false;
2794 :
2795 2935283 : m_bitmask = bm;
2796 :
2797 : // Updating m_bitmask may still yield a semantic bitmask (as
2798 : // returned by get_bitmask) which is functionally equivalent to what
2799 : // we originally had. In which case, there's still no change.
2800 2935283 : if (save == get_bitmask ())
2801 : return false;
2802 :
2803 : // No need to call set_range_from_mask, because we'll never
2804 : // narrow the range. Besides, it would cause endless recursion
2805 : // because of the union_ in set_range_from_mask.
2806 2935283 : normalize_kind ();
2807 2935283 : return true;
2808 12468681 : }
2809 :
2810 : tree
2811 9002912 : irange::lbound () const
2812 : {
2813 9002912 : return wide_int_to_tree (type (), lower_bound ());
2814 : }
2815 :
2816 : tree
2817 296387 : irange::ubound () const
2818 : {
2819 296387 : return wide_int_to_tree (type (), upper_bound ());
2820 : }
2821 :
2822 : void
2823 9506396131 : irange_bitmask::verify_mask () const
2824 : {
2825 9506396131 : gcc_assert (m_value.get_precision () == m_mask.get_precision ());
2826 9506396131 : gcc_checking_assert (wi::bit_and (m_mask, m_value) == 0);
2827 9506396131 : }
2828 :
2829 : void
2830 0 : dump_value_range (FILE *file, const vrange *vr)
2831 : {
2832 0 : vr->dump (file);
2833 0 : }
2834 :
2835 : DEBUG_FUNCTION void
2836 0 : debug (const vrange *vr)
2837 : {
2838 0 : dump_value_range (stderr, vr);
2839 0 : fprintf (stderr, "\n");
2840 0 : }
2841 :
2842 : DEBUG_FUNCTION void
2843 0 : debug (const vrange &vr)
2844 : {
2845 0 : debug (&vr);
2846 0 : }
2847 :
2848 : /* Return true, if VAL1 and VAL2 are equal values for VRP purposes. */
2849 :
2850 : bool
2851 79558826 : vrp_operand_equal_p (const_tree val1, const_tree val2)
2852 : {
2853 79558826 : if (val1 == val2)
2854 : return true;
2855 62600158 : if (!val1 || !val2 || !operand_equal_p (val1, val2, 0))
2856 62026855 : return false;
2857 : return true;
2858 : }
2859 :
2860 : #define DEFINE_INT_RANGE_INSTANCE(N) \
2861 : template int_range<N>::int_range(tree_node *, \
2862 : const wide_int &, \
2863 : const wide_int &, \
2864 : value_range_kind); \
2865 : template int_range<N>::int_range(tree); \
2866 : template int_range<N>::int_range(const irange &); \
2867 : template int_range<N>::int_range(const int_range &); \
2868 : template int_range<N>& int_range<N>::operator= (const int_range &);
2869 :
2870 : DEFINE_INT_RANGE_INSTANCE(1)
2871 : DEFINE_INT_RANGE_INSTANCE(2)
2872 : DEFINE_INT_RANGE_INSTANCE(3)
2873 : DEFINE_INT_RANGE_INSTANCE(255)
2874 :
2875 : #if CHECKING_P
2876 : #include "selftest.h"
2877 :
2878 : #define INT(x) wi::shwi ((x), TYPE_PRECISION (integer_type_node))
2879 : #define UINT(x) wi::uhwi ((x), TYPE_PRECISION (unsigned_type_node))
2880 : #define SCHAR(x) wi::shwi ((x), TYPE_PRECISION (signed_char_type_node))
2881 :
2882 : namespace selftest
2883 : {
2884 :
2885 : static int_range<2>
2886 584 : range (tree type, int a, int b, value_range_kind kind = VR_RANGE)
2887 : {
2888 584 : wide_int w1, w2;
2889 584 : if (TYPE_UNSIGNED (type))
2890 : {
2891 40 : w1 = wi::uhwi (a, TYPE_PRECISION (type));
2892 40 : w2 = wi::uhwi (b, TYPE_PRECISION (type));
2893 : }
2894 : else
2895 : {
2896 544 : w1 = wi::shwi (a, TYPE_PRECISION (type));
2897 544 : w2 = wi::shwi (b, TYPE_PRECISION (type));
2898 : }
2899 584 : return int_range<2> (type, w1, w2, kind);
2900 584 : }
2901 :
2902 : static int_range<2>
2903 540 : range_int (int a, int b, value_range_kind kind = VR_RANGE)
2904 : {
2905 0 : return range (integer_type_node, a, b, kind);
2906 : }
2907 :
2908 : static int_range<2>
2909 8 : range_uint (int a, int b, value_range_kind kind = VR_RANGE)
2910 : {
2911 0 : return range (unsigned_type_node, a, b, kind);
2912 : }
2913 :
2914 : static int_range<2>
2915 8 : range_uint128 (int a, int b, value_range_kind kind = VR_RANGE)
2916 : {
2917 8 : tree u128_type_node = build_nonstandard_integer_type (128, 1);
2918 8 : return range (u128_type_node, a, b, kind);
2919 : }
2920 :
2921 : static int_range<2>
2922 12 : range_uchar (int a, int b, value_range_kind kind = VR_RANGE)
2923 : {
2924 0 : return range (unsigned_char_type_node, a, b, kind);
2925 : }
2926 :
2927 : static int_range<2>
2928 4 : range_char (int a, int b, value_range_kind kind = VR_RANGE)
2929 : {
2930 0 : return range (signed_char_type_node, a, b, kind);
2931 : }
2932 :
2933 : static int_range<3>
2934 44 : build_range3 (int a, int b, int c, int d, int e, int f)
2935 : {
2936 44 : int_range<3> i1 = range_int (a, b);
2937 44 : int_range<3> i2 = range_int (c, d);
2938 44 : int_range<3> i3 = range_int (e, f);
2939 44 : i1.union_ (i2);
2940 44 : i1.union_ (i3);
2941 88 : return i1;
2942 44 : }
2943 :
2944 : static void
2945 4 : range_tests_irange3 ()
2946 : {
2947 4 : int_range<3> r0, r1, r2;
2948 4 : int_range<3> i1, i2, i3;
2949 :
2950 : // ([10,20] U [5,8]) U [1,3] ==> [1,3][5,8][10,20].
2951 4 : r0 = range_int (10, 20);
2952 4 : r1 = range_int (5, 8);
2953 4 : r0.union_ (r1);
2954 4 : r1 = range_int (1, 3);
2955 4 : r0.union_ (r1);
2956 4 : ASSERT_TRUE (r0 == build_range3 (1, 3, 5, 8, 10, 20));
2957 :
2958 : // [1,3][5,8][10,20] U [-5,0] => [-5,3][5,8][10,20].
2959 4 : r1 = range_int (-5, 0);
2960 4 : r0.union_ (r1);
2961 4 : ASSERT_TRUE (r0 == build_range3 (-5, 3, 5, 8, 10, 20));
2962 :
2963 : // [10,20][30,40] U [50,60] ==> [10,20][30,40][50,60].
2964 4 : r1 = range_int (50, 60);
2965 4 : r0 = range_int (10, 20);
2966 4 : r0.union_ (range_int (30, 40));
2967 4 : r0.union_ (r1);
2968 4 : ASSERT_TRUE (r0 == build_range3 (10, 20, 30, 40, 50, 60));
2969 : // [10,20][30,40][50,60] U [70, 80] ==> [10,20][30,40][50,60][70,80].
2970 4 : r1 = range_int (70, 80);
2971 4 : r0.union_ (r1);
2972 :
2973 4 : r2 = build_range3 (10, 20, 30, 40, 50, 60);
2974 4 : r2.union_ (range_int (70, 80));
2975 4 : ASSERT_TRUE (r0 == r2);
2976 :
2977 : // [10,20][30,40][50,60] U [6,35] => [6,40][50,60].
2978 4 : r0 = build_range3 (10, 20, 30, 40, 50, 60);
2979 4 : r1 = range_int (6, 35);
2980 4 : r0.union_ (r1);
2981 4 : r1 = range_int (6, 40);
2982 4 : r1.union_ (range_int (50, 60));
2983 4 : ASSERT_TRUE (r0 == r1);
2984 :
2985 : // [10,20][30,40][50,60] U [6,60] => [6,60].
2986 4 : r0 = build_range3 (10, 20, 30, 40, 50, 60);
2987 4 : r1 = range_int (6, 60);
2988 4 : r0.union_ (r1);
2989 4 : ASSERT_TRUE (r0 == range_int (6, 60));
2990 :
2991 : // [10,20][30,40][50,60] U [6,70] => [6,70].
2992 4 : r0 = build_range3 (10, 20, 30, 40, 50, 60);
2993 4 : r1 = range_int (6, 70);
2994 4 : r0.union_ (r1);
2995 4 : ASSERT_TRUE (r0 == range_int (6, 70));
2996 :
2997 : // [10,20][30,40][50,60] U [35,70] => [10,20][30,70].
2998 4 : r0 = build_range3 (10, 20, 30, 40, 50, 60);
2999 4 : r1 = range_int (35, 70);
3000 4 : r0.union_ (r1);
3001 4 : r1 = range_int (10, 20);
3002 4 : r1.union_ (range_int (30, 70));
3003 4 : ASSERT_TRUE (r0 == r1);
3004 :
3005 : // [10,20][30,40][50,60] U [15,35] => [10,40][50,60].
3006 4 : r0 = build_range3 (10, 20, 30, 40, 50, 60);
3007 4 : r1 = range_int (15, 35);
3008 4 : r0.union_ (r1);
3009 4 : r1 = range_int (10, 40);
3010 4 : r1.union_ (range_int (50, 60));
3011 4 : ASSERT_TRUE (r0 == r1);
3012 :
3013 : // [10,20][30,40][50,60] U [35,35] => [10,20][30,40][50,60].
3014 4 : r0 = build_range3 (10, 20, 30, 40, 50, 60);
3015 4 : r1 = range_int (35, 35);
3016 4 : r0.union_ (r1);
3017 4 : ASSERT_TRUE (r0 == build_range3 (10, 20, 30, 40, 50, 60));
3018 4 : }
3019 :
3020 : static void
3021 4 : range_tests_int_range_max ()
3022 : {
3023 4 : int_range_max big;
3024 4 : unsigned int nrange;
3025 :
3026 : // Build a huge multi-range range.
3027 204 : for (nrange = 0; nrange < 50; ++nrange)
3028 : {
3029 200 : int_range<1> tmp = range_int (nrange*10, nrange *10 + 5);
3030 200 : big.union_ (tmp);
3031 200 : }
3032 4 : ASSERT_TRUE (big.num_pairs () == nrange);
3033 :
3034 : // Verify that we can copy it without loosing precision.
3035 4 : int_range_max copy (big);
3036 4 : ASSERT_TRUE (copy.num_pairs () == nrange);
3037 :
3038 : // Inverting it should produce one more sub-range.
3039 4 : big.invert ();
3040 4 : ASSERT_TRUE (big.num_pairs () == nrange + 1);
3041 :
3042 4 : int_range<1> tmp = range_int (5, 37);
3043 4 : big.intersect (tmp);
3044 4 : ASSERT_TRUE (big.num_pairs () == 4);
3045 :
3046 : // Test that [10,10][20,20] does NOT contain 15.
3047 4 : {
3048 4 : int_range_max i1 = range_int (10, 10);
3049 4 : int_range_max i2 = range_int (20, 20);
3050 4 : i1.union_ (i2);
3051 4 : ASSERT_FALSE (i1.contains_p (INT (15)));
3052 4 : }
3053 4 : }
3054 :
3055 : // Simulate -fstrict-enums where the domain of a type is less than the
3056 : // underlying type.
3057 :
3058 : static void
3059 4 : range_tests_strict_enum ()
3060 : {
3061 : // The enum can only hold [0, 3].
3062 4 : tree rtype = copy_node (unsigned_type_node);
3063 4 : TYPE_MIN_VALUE (rtype) = build_int_cstu (rtype, 0);
3064 4 : TYPE_MAX_VALUE (rtype) = build_int_cstu (rtype, 3);
3065 :
3066 : // Test that even though vr1 covers the strict enum domain ([0, 3]),
3067 : // it does not cover the domain of the underlying type.
3068 4 : int_range<1> vr1 = range (rtype, 0, 1);
3069 4 : int_range<1> vr2 = range (rtype, 2, 3);
3070 4 : vr1.union_ (vr2);
3071 4 : ASSERT_TRUE (vr1 == range (rtype, 0, 3));
3072 4 : ASSERT_FALSE (vr1.varying_p ());
3073 :
3074 : // Test that copying to a multi-range does not change things.
3075 4 : int_range<2> ir1 (vr1);
3076 4 : ASSERT_TRUE (ir1 == vr1);
3077 4 : ASSERT_FALSE (ir1.varying_p ());
3078 :
3079 : // The same test as above, but using TYPE_{MIN,MAX}_VALUE instead of [0,3].
3080 8 : vr1 = int_range<2> (rtype,
3081 8 : wi::to_wide (TYPE_MIN_VALUE (rtype)),
3082 12 : wi::to_wide (TYPE_MAX_VALUE (rtype)));
3083 4 : ir1 = vr1;
3084 4 : ASSERT_TRUE (ir1 == vr1);
3085 4 : ASSERT_FALSE (ir1.varying_p ());
3086 4 : }
3087 :
3088 : // Test that range bounds are "snapped" to where they are expected to be.
3089 :
3090 : static void
3091 104 : assert_snap_result (int lb_val, int ub_val,
3092 : int expected_lb, int expected_ub,
3093 : unsigned mask_val, unsigned value_val,
3094 : tree type)
3095 : {
3096 104 : wide_int lb = wi::shwi (lb_val, TYPE_PRECISION (type));
3097 104 : wide_int ub = wi::shwi (ub_val, TYPE_PRECISION (type));
3098 104 : wide_int new_lb, new_ub;
3099 :
3100 208 : irange_bitmask bm (wi::uhwi (value_val, TYPE_PRECISION (type)),
3101 208 : wi::uhwi (mask_val, TYPE_PRECISION (type)));
3102 :
3103 104 : int_range_max r (type);
3104 104 : r.set (type, lb, ub);
3105 104 : r.update_bitmask (bm);
3106 :
3107 104 : if (TYPE_SIGN (type) == SIGNED && expected_ub < expected_lb)
3108 20 : gcc_checking_assert (r.undefined_p ());
3109 84 : else if (TYPE_SIGN (type) == UNSIGNED
3110 84 : && ((unsigned)expected_ub < (unsigned)expected_lb))
3111 16 : gcc_checking_assert (r.undefined_p ());
3112 : else
3113 : {
3114 68 : gcc_checking_assert (wi::eq_p (r.lower_bound (),
3115 : wi::shwi (expected_lb,
3116 : TYPE_PRECISION (type))));
3117 136 : gcc_checking_assert (wi::eq_p (r.upper_bound (),
3118 : wi::shwi (expected_ub,
3119 : TYPE_PRECISION (type))));
3120 : }
3121 104 : }
3122 :
3123 :
3124 : // Run a selection of tests that confirm, bounds are snapped as expected.
3125 : // We only test individual pairs, multiple pairs use the same snapping
3126 : // routine as single pairs.
3127 :
3128 : static void
3129 4 : test_irange_snap_bounds ()
3130 : {
3131 4 : tree u32 = unsigned_type_node;
3132 4 : tree s32 = integer_type_node;
3133 4 : tree s8 = build_nonstandard_integer_type (8, /*unsigned=*/ 0);
3134 4 : tree s1 = build_nonstandard_integer_type (1, /*unsigned=*/ 0);
3135 4 : tree u1 = build_nonstandard_integer_type (1, /*unsigned=*/ 1);
3136 :
3137 : // Basic aligned range: even-only
3138 4 : assert_snap_result (5, 15, 6, 14, 0xE, 0x0, u32);
3139 : // Singleton that doesn't match mask: undefined.
3140 4 : assert_snap_result (7, 7, 1, 0, 0xFFFFFFFE, 0x0, u32);
3141 : // 8-bit signed char, mask 0xF0 (i.e. step of 16).
3142 4 : assert_snap_result (-100, 100, -96, 96, 0xF0, 0x00, s8);
3143 : // Already aligned range: no change.
3144 4 : assert_snap_result (0, 240, 0, 240, 0xF0, 0x00, u32);
3145 : // Negative range, step 16 alignment (s32).
3146 4 : assert_snap_result (-123, -17, -112, -32, 0xFFFFFFF0, 0x00, s32);
3147 : // Negative range, step 16 alignment (trailing-zero aligned mask).
3148 4 : assert_snap_result (-123, -17, -112, -32, 0xFFFFFFF0, 0x00, s32);
3149 : // s8, 16-alignment mask, value = 0 (valid).
3150 4 : assert_snap_result (-50, 10, -48, 0, 0xF0, 0x00, s8);
3151 : // No values in range [-3,2] match alignment except 0.
3152 4 : assert_snap_result (-3, 2, 0, 0, 0xF8, 0x00, s8);
3153 : // No values in range [-3,2] match alignment — undefined.
3154 4 : assert_snap_result (-3, 2, 1, 0, 0xF8, 0x04, s8);
3155 : // Already aligned range: no change.
3156 4 : assert_snap_result (0, 240, 0, 240, 0xF0, 0x00, s32);
3157 : // 1-bit signed: only -1 allowed (0b1).
3158 4 : assert_snap_result (-1, 0, -1, -1, 0x00, 0x01, s1);
3159 : // 1-bit signed: only 0 allowed (0b0).
3160 4 : assert_snap_result (-1, 0, 0, 0, 0x00, 0x00, s1);
3161 : // 1-bit signed: no match (invalid case).
3162 4 : assert_snap_result (-1, -1, 1, 0, 0x00, 0x00, s1);
3163 : // 1-bit signed: no match (invalid case).
3164 4 : assert_snap_result (0, 0, 1, 0, 0x00, 0x01, s1);
3165 : // 1-bit unsigned: only 1 allowed.
3166 4 : assert_snap_result (0, 1, 1, 1, 0x00, 0x01, u1);
3167 : // 1-bit unsigned: only 0 allowed.
3168 4 : assert_snap_result (0, 1, 0, 0, 0x00, 0x00, u1);
3169 : // 1-bit unsigned: no match (invalid case).
3170 4 : assert_snap_result (1, 1, 1, 0, 0x00, 0x00, u1);
3171 : // 1-bit unsigned: no match (invalid case).
3172 4 : assert_snap_result (0, 0, 1, 0, 0x00, 0x01, u1);
3173 : // Unsigned: Near overflow, even alignment.
3174 4 : assert_snap_result (UINT_MAX - 6, UINT_MAX, UINT_MAX - 5, UINT_MAX - 1,
3175 : 0xFFFFFFFE, 0x00, u32);
3176 : // Unsigned: Wraparound-like range — no valid snapped values.
3177 4 : assert_snap_result (UINT_MAX - 5, UINT_MAX, 1, 0, 0xFFFFFFF0, 0x00, u32);
3178 : // Signed: Near INT_MAX, 8-aligned.
3179 4 : assert_snap_result (INT_MAX - 18, INT_MAX, INT_MAX - 15, INT_MAX - 7,
3180 : 0xFFFFFFF8, 0x00, s32);
3181 : // Signed: Near INT_MIN, 16-aligned.
3182 4 : assert_snap_result (INT_MIN, INT_MIN + 30, INT_MIN, INT_MIN + 16,
3183 : 0xFFFFFFF0, 0x00, s32);
3184 : // Signed: Full domain, 4-aligned.
3185 4 : assert_snap_result (-128, 127, -128, 124, 0xFC, 0x00, s8);
3186 : // Singleton at INT_MIN that doesn’t match alignment — undefined
3187 4 : assert_snap_result (INT_MIN, INT_MIN, 1, 0, 0xFFFFFFFE, 0x01, s32);
3188 : // Range at INT_MIN that doesn’t match alignment — undefined.
3189 4 : assert_snap_result (INT_MIN, INT_MIN + 10, 1, 0, 0xFFFFFFF0, 0x0F, s32);
3190 : // Unsigned: Full domain, 256-aligned.
3191 4 : assert_snap_result (0, UINT_MAX, 0, UINT_MAX & ~255, 0xFFFFFF00, 0x00, u32);
3192 4 : }
3193 :
3194 : static void
3195 4 : range_tests_misc ()
3196 : {
3197 4 : tree u128_type = build_nonstandard_integer_type (128, /*unsigned=*/1);
3198 4 : int_range<2> i1, i2, i3;
3199 4 : int_range<2> r0, r1, rold;
3200 :
3201 : // Test 1-bit signed integer union.
3202 : // [-1,-1] U [0,0] = VARYING.
3203 4 : tree one_bit_type = build_nonstandard_integer_type (1, 0);
3204 4 : wide_int one_bit_min = irange_val_min (one_bit_type);
3205 4 : wide_int one_bit_max = irange_val_max (one_bit_type);
3206 4 : {
3207 4 : int_range<2> min = int_range<2> (one_bit_type, one_bit_min, one_bit_min);
3208 4 : int_range<2> max = int_range<2> (one_bit_type, one_bit_max, one_bit_max);
3209 4 : max.union_ (min);
3210 4 : ASSERT_TRUE (max.varying_p ());
3211 4 : }
3212 : // Test that we can set a range of true+false for a 1-bit signed int.
3213 4 : r0 = range_true_and_false (one_bit_type);
3214 :
3215 : // Test inversion of 1-bit signed integers.
3216 4 : {
3217 4 : int_range<2> min = int_range<2> (one_bit_type, one_bit_min, one_bit_min);
3218 4 : int_range<2> max = int_range<2> (one_bit_type, one_bit_max, one_bit_max);
3219 4 : int_range<2> t;
3220 4 : t = min;
3221 4 : t.invert ();
3222 4 : ASSERT_TRUE (t == max);
3223 4 : t = max;
3224 4 : t.invert ();
3225 4 : ASSERT_TRUE (t == min);
3226 4 : }
3227 :
3228 : // Test that NOT(255) is [0..254] in 8-bit land.
3229 4 : int_range<1> not_255 = range_uchar (255, 255, VR_ANTI_RANGE);
3230 4 : ASSERT_TRUE (not_255 == range_uchar (0, 254));
3231 :
3232 : // Test that NOT(0) is [1..255] in 8-bit land.
3233 4 : int_range<2> not_zero;
3234 4 : not_zero.set_nonzero (unsigned_char_type_node);
3235 4 : ASSERT_TRUE (not_zero == range_uchar (1, 255));
3236 :
3237 : // Check that [0,127][0x..ffffff80,0x..ffffff]
3238 : // => ~[128, 0x..ffffff7f].
3239 4 : r0 = range_uint128 (0, 127);
3240 4 : wide_int high = wi::minus_one (128);
3241 : // low = -1 - 127 => 0x..ffffff80.
3242 4 : wide_int low = wi::sub (high, wi::uhwi (127, 128));
3243 4 : r1 = int_range<1> (u128_type, low, high); // [0x..ffffff80, 0x..ffffffff]
3244 : // r0 = [0,127][0x..ffffff80,0x..fffffff].
3245 4 : r0.union_ (r1);
3246 : // r1 = [128, 0x..ffffff7f].
3247 12 : r1 = int_range<1> (u128_type,
3248 8 : wi::uhwi (128, 128),
3249 8 : wi::sub (wi::minus_one (128), wi::uhwi (128, 128)));
3250 4 : r0.invert ();
3251 4 : ASSERT_TRUE (r0 == r1);
3252 :
3253 4 : r0.set_varying (integer_type_node);
3254 4 : wide_int minint = r0.lower_bound ();
3255 4 : wide_int maxint = r0.upper_bound ();
3256 :
3257 4 : r0.set_varying (short_integer_type_node);
3258 :
3259 4 : r0.set_varying (unsigned_type_node);
3260 4 : wide_int maxuint = r0.upper_bound ();
3261 :
3262 : // Check that ~[0,5] => [6,MAX] for unsigned int.
3263 4 : r0 = range_uint (0, 5);
3264 4 : r0.invert ();
3265 4 : ASSERT_TRUE (r0 == int_range<1> (unsigned_type_node,
3266 : wi::uhwi (6, TYPE_PRECISION (unsigned_type_node)),
3267 : maxuint));
3268 :
3269 : // Check that ~[10,MAX] => [0,9] for unsigned int.
3270 8 : r0 = int_range<1> (unsigned_type_node,
3271 4 : wi::uhwi (10, TYPE_PRECISION (unsigned_type_node)),
3272 8 : maxuint);
3273 4 : r0.invert ();
3274 4 : ASSERT_TRUE (r0 == range_uint (0, 9));
3275 :
3276 : // Check that ~[0,5] => [6,MAX] for unsigned 128-bit numbers.
3277 4 : r0 = range_uint128 (0, 5, VR_ANTI_RANGE);
3278 4 : r1 = int_range<1> (u128_type, wi::uhwi (6, 128), wi::minus_one (128));
3279 4 : ASSERT_TRUE (r0 == r1);
3280 :
3281 : // Check that [~5] is really [-MIN,4][6,MAX].
3282 4 : r0 = range_int (5, 5, VR_ANTI_RANGE);
3283 4 : r1 = int_range<1> (integer_type_node, minint, INT (4));
3284 4 : r1.union_ (int_range<1> (integer_type_node, INT (6), maxint));
3285 4 : ASSERT_FALSE (r1.undefined_p ());
3286 4 : ASSERT_TRUE (r0 == r1);
3287 :
3288 4 : r1 = range_int (5, 5);
3289 4 : int_range<2> r2 (r1);
3290 4 : ASSERT_TRUE (r1 == r2);
3291 :
3292 4 : r1 = range_int (5, 10);
3293 :
3294 4 : r1 = range_int (5, 10);
3295 4 : ASSERT_TRUE (r1.contains_p (INT (7)));
3296 :
3297 4 : r1 = range_char (0, 20);
3298 4 : ASSERT_TRUE (r1.contains_p (SCHAR(15)));
3299 4 : ASSERT_FALSE (r1.contains_p (SCHAR(300)));
3300 :
3301 : // NOT([10,20]) ==> [-MIN,9][21,MAX].
3302 4 : r0 = r1 = range_int (10, 20);
3303 4 : r2 = int_range<1> (integer_type_node, minint, INT(9));
3304 4 : r2.union_ (int_range<1> (integer_type_node, INT(21), maxint));
3305 4 : ASSERT_FALSE (r2.undefined_p ());
3306 4 : r1.invert ();
3307 4 : ASSERT_TRUE (r1 == r2);
3308 : // Test that NOT(NOT(x)) == x.
3309 4 : r2.invert ();
3310 4 : ASSERT_TRUE (r0 == r2);
3311 :
3312 : // Test that booleans and their inverse work as expected.
3313 4 : r0.set_zero (boolean_type_node);
3314 4 : ASSERT_TRUE (r0 == range_false ());
3315 4 : r0.invert ();
3316 4 : ASSERT_TRUE (r0 == range_true ());
3317 :
3318 : // Make sure NULL and non-NULL of pointer types work, and that
3319 : // inverses of them are consistent.
3320 4 : tree voidp = build_pointer_type (void_type_node);
3321 4 : prange p0;
3322 4 : p0.set_zero (voidp);
3323 4 : prange p1 = p0;
3324 4 : p0.invert ();
3325 4 : p0.invert ();
3326 4 : ASSERT_TRUE (p0 == p1);
3327 :
3328 : // The intersection of:
3329 : // [0, +INF] MASK 0xff..00 VALUE 0xf8
3330 : // [0, +INF] MASK 0xff..00 VALUE 0x00
3331 : // is [0, +INF] MASK 0xff..ff VALUE 0x00, which is VARYING.
3332 : // Test that we normalized to VARYING.
3333 4 : unsigned prec = TYPE_PRECISION (voidp);
3334 4 : p0.set_varying (voidp);
3335 4 : wide_int mask = wi::mask (8, true, prec);
3336 4 : wide_int value = wi::uhwi (0xf8, prec);
3337 4 : irange_bitmask bm (wi::uhwi (0xf8, prec), mask);
3338 4 : p0.update_bitmask (bm);
3339 4 : p1.set_varying (voidp);
3340 4 : bm = irange_bitmask (wi::zero (prec), mask);
3341 4 : p1.update_bitmask (bm);
3342 4 : p0.intersect (p1);
3343 :
3344 : // [10,20] U [15, 30] => [10, 30].
3345 4 : r0 = range_int (10, 20);
3346 4 : r1 = range_int (15, 30);
3347 4 : r0.union_ (r1);
3348 4 : ASSERT_TRUE (r0 == range_int (10, 30));
3349 :
3350 : // [15,40] U [] => [15,40].
3351 4 : r0 = range_int (15, 40);
3352 4 : r1.set_undefined ();
3353 4 : r0.union_ (r1);
3354 4 : ASSERT_TRUE (r0 == range_int (15, 40));
3355 :
3356 : // [10,20] U [10,10] => [10,20].
3357 4 : r0 = range_int (10, 20);
3358 4 : r1 = range_int (10, 10);
3359 4 : r0.union_ (r1);
3360 4 : ASSERT_TRUE (r0 == range_int (10, 20));
3361 :
3362 : // [10,20] U [9,9] => [9,20].
3363 4 : r0 = range_int (10, 20);
3364 4 : r1 = range_int (9, 9);
3365 4 : r0.union_ (r1);
3366 4 : ASSERT_TRUE (r0 == range_int (9, 20));
3367 :
3368 : // [10,20] ^ [15,30] => [15,20].
3369 4 : r0 = range_int (10, 20);
3370 4 : r1 = range_int (15, 30);
3371 4 : r0.intersect (r1);
3372 4 : ASSERT_TRUE (r0 == range_int (15, 20));
3373 :
3374 : // Test the internal sanity of wide_int's wrt HWIs.
3375 4 : ASSERT_TRUE (wi::max_value (TYPE_PRECISION (boolean_type_node),
3376 : TYPE_SIGN (boolean_type_node))
3377 : == wi::uhwi (1, TYPE_PRECISION (boolean_type_node)));
3378 :
3379 : // Test zero_p().
3380 4 : r0 = range_int (0, 0);
3381 4 : ASSERT_TRUE (r0.zero_p ());
3382 :
3383 : // Test nonzero_p().
3384 4 : r0 = range_int (0, 0);
3385 4 : r0.invert ();
3386 4 : ASSERT_TRUE (r0.nonzero_p ());
3387 :
3388 : // r0 = ~[1,1]
3389 4 : r0 = range_int (1, 1, VR_ANTI_RANGE);
3390 : // r1 = ~[3,3]
3391 4 : r1 = range_int (3, 3, VR_ANTI_RANGE);
3392 :
3393 : // vv = [0,0][2,2][4, MAX]
3394 4 : int_range<3> vv = r0;
3395 4 : vv.intersect (r1);
3396 :
3397 4 : ASSERT_TRUE (vv.contains_p (UINT (2)));
3398 4 : ASSERT_TRUE (vv.num_pairs () == 3);
3399 :
3400 4 : r0 = range_int (1, 1);
3401 : // And union it with [0,0][2,2][4,MAX] multi range
3402 4 : r0.union_ (vv);
3403 : // The result should be [0,2][4,MAX], or ~[3,3] but it must contain 2
3404 4 : ASSERT_TRUE (r0.contains_p (INT (2)));
3405 4 : }
3406 :
3407 : static void
3408 4 : range_tests_nonzero_bits ()
3409 : {
3410 4 : int_range<8> r0, r1;
3411 :
3412 : // Adding nonzero bits to a varying drops the varying.
3413 4 : r0.set_varying (integer_type_node);
3414 4 : r0.set_nonzero_bits (INT (255));
3415 4 : ASSERT_TRUE (!r0.varying_p ());
3416 :
3417 : // Test contains_p with nonzero bits.
3418 4 : r0.set_zero (integer_type_node);
3419 4 : ASSERT_TRUE (r0.contains_p (INT (0)));
3420 4 : ASSERT_FALSE (r0.contains_p (INT (1)));
3421 4 : r0.set_nonzero_bits (INT (0xfe));
3422 4 : ASSERT_FALSE (r0.contains_p (INT (0x100)));
3423 4 : ASSERT_FALSE (r0.contains_p (INT (0x3)));
3424 :
3425 : // Union of nonzero bits.
3426 4 : r0.set_varying (integer_type_node);
3427 4 : r0.set_nonzero_bits (INT (0xf0));
3428 4 : r1.set_varying (integer_type_node);
3429 4 : r1.set_nonzero_bits (INT (0xf));
3430 4 : r0.union_ (r1);
3431 4 : ASSERT_TRUE (r0.get_nonzero_bits () == 0xff);
3432 :
3433 : // Intersect of nonzero bits.
3434 4 : r0 = range_int (0, 255);
3435 4 : r0.set_nonzero_bits (INT (0xfe));
3436 4 : r1.set_varying (integer_type_node);
3437 4 : r1.set_nonzero_bits (INT (0xf0));
3438 4 : r0.intersect (r1);
3439 4 : ASSERT_TRUE (r0.get_nonzero_bits () == 0xf0);
3440 :
3441 : // Intersect where the mask of nonzero bits is implicit from the range.
3442 4 : r0.set_varying (integer_type_node);
3443 4 : r1 = range_int (0, 255);
3444 4 : r0.intersect (r1);
3445 4 : ASSERT_TRUE (r0.get_nonzero_bits () == 0xff);
3446 :
3447 : // Test that setting a nonzero bit of 1 does not pessimize the range.
3448 4 : r0.set_zero (integer_type_node);
3449 4 : r0.set_nonzero_bits (INT (1));
3450 4 : ASSERT_TRUE (r0.zero_p ());
3451 :
3452 : // Now test that range bounds are snapped to match bitmask alignments.
3453 4 : test_irange_snap_bounds ();
3454 4 : }
3455 :
3456 : // Build an frange from string endpoints.
3457 :
3458 : static inline frange
3459 492 : frange_float (const char *lb, const char *ub, tree type = float_type_node)
3460 : {
3461 492 : REAL_VALUE_TYPE min, max;
3462 492 : gcc_assert (real_from_string (&min, lb) == 0);
3463 492 : gcc_assert (real_from_string (&max, ub) == 0);
3464 492 : return frange (type, min, max);
3465 : }
3466 :
3467 : static void
3468 4 : range_tests_nan ()
3469 : {
3470 4 : frange r0, r1;
3471 4 : REAL_VALUE_TYPE q, r;
3472 4 : bool signbit;
3473 :
3474 : // Equal ranges but with differing NAN bits are not equal.
3475 4 : if (HONOR_NANS (float_type_node))
3476 : {
3477 4 : r1 = frange_float ("10", "12");
3478 4 : r0 = r1;
3479 4 : ASSERT_EQ (r0, r1);
3480 4 : r0.clear_nan ();
3481 4 : ASSERT_NE (r0, r1);
3482 4 : r0.update_nan ();
3483 4 : ASSERT_EQ (r0, r1);
3484 :
3485 : // [10, 20] NAN ^ [30, 40] NAN = NAN.
3486 4 : r0 = frange_float ("10", "20");
3487 4 : r1 = frange_float ("30", "40");
3488 4 : r0.intersect (r1);
3489 4 : ASSERT_TRUE (r0.known_isnan ());
3490 :
3491 : // [3,5] U [5,10] NAN = ... NAN
3492 4 : r0 = frange_float ("3", "5");
3493 4 : r0.clear_nan ();
3494 4 : r1 = frange_float ("5", "10");
3495 4 : r0.union_ (r1);
3496 8 : ASSERT_TRUE (r0.maybe_isnan ());
3497 : }
3498 :
3499 : // [5,6] U NAN = [5,6] NAN.
3500 4 : r0 = frange_float ("5", "6");
3501 4 : r0.clear_nan ();
3502 4 : r1.set_nan (float_type_node);
3503 4 : r0.union_ (r1);
3504 4 : real_from_string (&q, "5");
3505 4 : real_from_string (&r, "6");
3506 4 : ASSERT_TRUE (real_identical (&q, &r0.lower_bound ()));
3507 4 : ASSERT_TRUE (real_identical (&r, &r0.upper_bound ()));
3508 8 : ASSERT_TRUE (r0.maybe_isnan ());
3509 :
3510 : // NAN U NAN = NAN
3511 4 : r0.set_nan (float_type_node);
3512 4 : r1.set_nan (float_type_node);
3513 4 : r0.union_ (r1);
3514 4 : ASSERT_TRUE (r0.known_isnan ());
3515 :
3516 : // [INF, INF] NAN ^ NAN = NAN
3517 4 : r0.set_nan (float_type_node);
3518 4 : r1 = frange_float ("+Inf", "+Inf");
3519 4 : if (!HONOR_NANS (float_type_node))
3520 0 : r1.update_nan ();
3521 4 : r0.intersect (r1);
3522 4 : ASSERT_TRUE (r0.known_isnan ());
3523 :
3524 : // NAN ^ NAN = NAN
3525 4 : r0.set_nan (float_type_node);
3526 4 : r1.set_nan (float_type_node);
3527 4 : r0.intersect (r1);
3528 4 : ASSERT_TRUE (r0.known_isnan ());
3529 :
3530 : // +NAN ^ -NAN = UNDEFINED
3531 4 : r0.set_nan (float_type_node, false);
3532 4 : r1.set_nan (float_type_node, true);
3533 4 : r0.intersect (r1);
3534 4 : ASSERT_TRUE (r0.undefined_p ());
3535 :
3536 : // VARYING ^ NAN = NAN.
3537 4 : r0.set_nan (float_type_node);
3538 4 : r1.set_varying (float_type_node);
3539 4 : r0.intersect (r1);
3540 4 : ASSERT_TRUE (r0.known_isnan ());
3541 :
3542 : // [3,4] ^ NAN = UNDEFINED.
3543 4 : r0 = frange_float ("3", "4");
3544 4 : r0.clear_nan ();
3545 4 : r1.set_nan (float_type_node);
3546 4 : r0.intersect (r1);
3547 4 : ASSERT_TRUE (r0.undefined_p ());
3548 :
3549 : // [-3, 5] ^ NAN = UNDEFINED
3550 4 : r0 = frange_float ("-3", "5");
3551 4 : r0.clear_nan ();
3552 4 : r1.set_nan (float_type_node);
3553 4 : r0.intersect (r1);
3554 4 : ASSERT_TRUE (r0.undefined_p ());
3555 :
3556 : // Setting the NAN bit to yes does not make us a known NAN.
3557 4 : r0.set_varying (float_type_node);
3558 4 : r0.update_nan ();
3559 4 : ASSERT_FALSE (r0.known_isnan ());
3560 :
3561 : // NAN is in a VARYING.
3562 4 : r0.set_varying (float_type_node);
3563 4 : real_nan (&r, "", 1, TYPE_MODE (float_type_node));
3564 4 : REAL_VALUE_TYPE nan = r;
3565 4 : ASSERT_TRUE (r0.contains_p (nan));
3566 :
3567 : // -NAN is in a VARYING.
3568 4 : r0.set_varying (float_type_node);
3569 4 : q = real_value_negate (&r);
3570 4 : REAL_VALUE_TYPE neg_nan = q;
3571 4 : ASSERT_TRUE (r0.contains_p (neg_nan));
3572 :
3573 : // Clearing the NAN on a [] NAN is the empty set.
3574 4 : r0.set_nan (float_type_node);
3575 4 : r0.clear_nan ();
3576 4 : ASSERT_TRUE (r0.undefined_p ());
3577 :
3578 : // [10,20] NAN ^ [21,25] NAN = [NAN]
3579 4 : r0 = frange_float ("10", "20");
3580 4 : r0.update_nan ();
3581 4 : r1 = frange_float ("21", "25");
3582 4 : r1.update_nan ();
3583 4 : r0.intersect (r1);
3584 4 : ASSERT_TRUE (r0.known_isnan ());
3585 :
3586 : // NAN U [5,6] should be [5,6] +-NAN.
3587 4 : r0.set_nan (float_type_node);
3588 4 : r1 = frange_float ("5", "6");
3589 4 : r1.clear_nan ();
3590 4 : r0.union_ (r1);
3591 4 : real_from_string (&q, "5");
3592 4 : real_from_string (&r, "6");
3593 4 : ASSERT_TRUE (real_identical (&q, &r0.lower_bound ()));
3594 4 : ASSERT_TRUE (real_identical (&r, &r0.upper_bound ()));
3595 4 : ASSERT_TRUE (!r0.signbit_p (signbit));
3596 8 : ASSERT_TRUE (r0.maybe_isnan ());
3597 :
3598 : // NAN U NAN shouldn't change anything.
3599 4 : r0.set_nan (float_type_node);
3600 4 : r1.set_nan (float_type_node);
3601 4 : ASSERT_FALSE (r0.union_ (r1));
3602 :
3603 : // [3,5] NAN U NAN shouldn't change anything.
3604 4 : r0 = frange_float ("3", "5");
3605 4 : r1.set_nan (float_type_node);
3606 4 : ASSERT_FALSE (r0.union_ (r1));
3607 :
3608 : // [3,5] U NAN *does* trigger a change.
3609 4 : r0 = frange_float ("3", "5");
3610 4 : r0.clear_nan ();
3611 4 : r1.set_nan (float_type_node);
3612 4 : ASSERT_TRUE (r0.union_ (r1));
3613 4 : }
3614 :
3615 : static void
3616 8 : range_tests_signed_zeros ()
3617 : {
3618 8 : REAL_VALUE_TYPE zero = dconst0;
3619 8 : REAL_VALUE_TYPE neg_zero = zero;
3620 8 : neg_zero.sign = 1;
3621 8 : frange r0, r1;
3622 8 : bool signbit;
3623 :
3624 : // [0,0] contains [0,0] but not [-0,-0] and vice versa.
3625 8 : r0 = frange_float ("0.0", "0.0");
3626 8 : r1 = frange_float ("-0.0", "-0.0");
3627 8 : ASSERT_TRUE (r0.contains_p (zero));
3628 8 : ASSERT_TRUE (!r0.contains_p (neg_zero));
3629 8 : ASSERT_TRUE (r1.contains_p (neg_zero));
3630 8 : ASSERT_TRUE (!r1.contains_p (zero));
3631 :
3632 : // Test contains_p() when we know the sign of the zero.
3633 8 : r0 = frange_float ("0.0", "0.0");
3634 8 : ASSERT_TRUE (r0.contains_p (zero));
3635 8 : ASSERT_FALSE (r0.contains_p (neg_zero));
3636 8 : r0 = frange_float ("-0.0", "-0.0");
3637 8 : ASSERT_TRUE (r0.contains_p (neg_zero));
3638 8 : ASSERT_FALSE (r0.contains_p (zero));
3639 :
3640 8 : r0 = frange_float ("-0.0", "0.0");
3641 8 : ASSERT_TRUE (r0.contains_p (neg_zero));
3642 8 : ASSERT_TRUE (r0.contains_p (zero));
3643 :
3644 8 : r0 = frange_float ("-3", "5");
3645 8 : ASSERT_TRUE (r0.contains_p (neg_zero));
3646 8 : ASSERT_TRUE (r0.contains_p (zero));
3647 :
3648 : // The intersection of zeros that differ in sign is a NAN (or
3649 : // undefined if not honoring NANs).
3650 8 : r0 = frange_float ("-0.0", "-0.0");
3651 8 : r1 = frange_float ("0.0", "0.0");
3652 8 : r0.intersect (r1);
3653 8 : if (HONOR_NANS (float_type_node))
3654 4 : ASSERT_TRUE (r0.known_isnan ());
3655 : else
3656 4 : ASSERT_TRUE (r0.undefined_p ());
3657 :
3658 : // The union of zeros that differ in sign is a zero with unknown sign.
3659 8 : r0 = frange_float ("0.0", "0.0");
3660 8 : r1 = frange_float ("-0.0", "-0.0");
3661 8 : r0.union_ (r1);
3662 8 : ASSERT_TRUE (r0.zero_p () && !r0.signbit_p (signbit));
3663 :
3664 : // [-0, +0] has an unknown sign.
3665 8 : r0 = frange_float ("-0.0", "0.0");
3666 8 : ASSERT_TRUE (r0.zero_p () && !r0.signbit_p (signbit));
3667 :
3668 : // [-0, +0] ^ [0, 0] is [0, 0]
3669 8 : r0 = frange_float ("-0.0", "0.0");
3670 8 : r1 = frange_float ("0.0", "0.0");
3671 8 : r0.intersect (r1);
3672 8 : ASSERT_TRUE (r0.zero_p ());
3673 :
3674 8 : r0 = frange_float ("+0", "5");
3675 8 : r0.clear_nan ();
3676 8 : ASSERT_TRUE (r0.signbit_p (signbit) && !signbit);
3677 :
3678 8 : r0 = frange_float ("-0", "5");
3679 8 : r0.clear_nan ();
3680 8 : ASSERT_TRUE (!r0.signbit_p (signbit));
3681 :
3682 8 : r0 = frange_float ("-0", "10");
3683 8 : r1 = frange_float ("0", "5");
3684 8 : r0.intersect (r1);
3685 8 : ASSERT_TRUE (real_iszero (&r0.lower_bound (), false));
3686 :
3687 8 : r0 = frange_float ("-0", "5");
3688 8 : r1 = frange_float ("0", "5");
3689 8 : r0.union_ (r1);
3690 8 : ASSERT_TRUE (real_iszero (&r0.lower_bound (), true));
3691 :
3692 8 : r0 = frange_float ("-5", "-0");
3693 8 : r0.update_nan ();
3694 8 : r1 = frange_float ("0", "0");
3695 8 : r1.update_nan ();
3696 8 : r0.intersect (r1);
3697 8 : if (HONOR_NANS (float_type_node))
3698 4 : ASSERT_TRUE (r0.known_isnan ());
3699 : else
3700 4 : ASSERT_TRUE (r0.undefined_p ());
3701 :
3702 8 : r0.set_nonnegative (float_type_node);
3703 8 : if (HONOR_NANS (float_type_node))
3704 8 : ASSERT_TRUE (r0.maybe_isnan ());
3705 :
3706 : // Numbers containing zero should have an unknown SIGNBIT.
3707 8 : r0 = frange_float ("0", "10");
3708 8 : r0.clear_nan ();
3709 8 : ASSERT_TRUE (r0.signbit_p (signbit) && !signbit);
3710 8 : }
3711 :
3712 : static void
3713 8 : range_tests_signbit ()
3714 : {
3715 8 : frange r0, r1;
3716 8 : bool signbit;
3717 :
3718 : // Negative numbers should have the SIGNBIT set.
3719 8 : r0 = frange_float ("-5", "-1");
3720 8 : r0.clear_nan ();
3721 8 : ASSERT_TRUE (r0.signbit_p (signbit) && signbit);
3722 : // Positive numbers should have the SIGNBIT clear.
3723 8 : r0 = frange_float ("1", "10");
3724 8 : r0.clear_nan ();
3725 8 : ASSERT_TRUE (r0.signbit_p (signbit) && !signbit);
3726 : // Numbers spanning both positive and negative should have an
3727 : // unknown SIGNBIT.
3728 8 : r0 = frange_float ("-10", "10");
3729 8 : r0.clear_nan ();
3730 8 : ASSERT_TRUE (!r0.signbit_p (signbit));
3731 8 : r0.set_varying (float_type_node);
3732 8 : ASSERT_TRUE (!r0.signbit_p (signbit));
3733 8 : }
3734 :
3735 : static void
3736 8 : range_tests_floats ()
3737 : {
3738 8 : frange r0, r1;
3739 :
3740 8 : if (HONOR_NANS (float_type_node))
3741 4 : range_tests_nan ();
3742 8 : range_tests_signbit ();
3743 :
3744 8 : if (HONOR_SIGNED_ZEROS (float_type_node))
3745 8 : range_tests_signed_zeros ();
3746 :
3747 : // A range of [-INF,+INF] is actually VARYING if no other properties
3748 : // are set.
3749 8 : r0 = frange_float ("-Inf", "+Inf");
3750 8 : ASSERT_TRUE (r0.varying_p ());
3751 : // ...unless it has some special property...
3752 8 : if (HONOR_NANS (r0.type ()))
3753 : {
3754 4 : r0.clear_nan ();
3755 4 : ASSERT_FALSE (r0.varying_p ());
3756 : }
3757 :
3758 : // For most architectures, where float and double are different
3759 : // sizes, having the same endpoints does not necessarily mean the
3760 : // ranges are equal.
3761 8 : if (!types_compatible_p (float_type_node, double_type_node))
3762 : {
3763 8 : r0 = frange_float ("3.0", "3.0", float_type_node);
3764 8 : r1 = frange_float ("3.0", "3.0", double_type_node);
3765 8 : ASSERT_NE (r0, r1);
3766 : }
3767 :
3768 : // [3,5] U [10,12] = [3,12].
3769 8 : r0 = frange_float ("3", "5");
3770 8 : r1 = frange_float ("10", "12");
3771 8 : r0.union_ (r1);
3772 8 : ASSERT_EQ (r0, frange_float ("3", "12"));
3773 :
3774 : // [5,10] U [4,8] = [4,10]
3775 8 : r0 = frange_float ("5", "10");
3776 8 : r1 = frange_float ("4", "8");
3777 8 : r0.union_ (r1);
3778 8 : ASSERT_EQ (r0, frange_float ("4", "10"));
3779 :
3780 : // [3,5] U [4,10] = [3,10]
3781 8 : r0 = frange_float ("3", "5");
3782 8 : r1 = frange_float ("4", "10");
3783 8 : r0.union_ (r1);
3784 8 : ASSERT_EQ (r0, frange_float ("3", "10"));
3785 :
3786 : // [4,10] U [5,11] = [4,11]
3787 8 : r0 = frange_float ("4", "10");
3788 8 : r1 = frange_float ("5", "11");
3789 8 : r0.union_ (r1);
3790 8 : ASSERT_EQ (r0, frange_float ("4", "11"));
3791 :
3792 : // [3,12] ^ [10,12] = [10,12].
3793 8 : r0 = frange_float ("3", "12");
3794 8 : r1 = frange_float ("10", "12");
3795 8 : r0.intersect (r1);
3796 8 : ASSERT_EQ (r0, frange_float ("10", "12"));
3797 :
3798 : // [10,12] ^ [11,11] = [11,11]
3799 8 : r0 = frange_float ("10", "12");
3800 8 : r1 = frange_float ("11", "11");
3801 8 : r0.intersect (r1);
3802 8 : ASSERT_EQ (r0, frange_float ("11", "11"));
3803 :
3804 : // [10,20] ^ [5,15] = [10,15]
3805 8 : r0 = frange_float ("10", "20");
3806 8 : r1 = frange_float ("5", "15");
3807 8 : r0.intersect (r1);
3808 8 : ASSERT_EQ (r0, frange_float ("10", "15"));
3809 :
3810 : // [10,20] ^ [15,25] = [15,20]
3811 8 : r0 = frange_float ("10", "20");
3812 8 : r1 = frange_float ("15", "25");
3813 8 : r0.intersect (r1);
3814 8 : ASSERT_EQ (r0, frange_float ("15", "20"));
3815 :
3816 : // [10,20] ^ [21,25] = []
3817 8 : r0 = frange_float ("10", "20");
3818 8 : r0.clear_nan ();
3819 8 : r1 = frange_float ("21", "25");
3820 8 : r1.clear_nan ();
3821 8 : r0.intersect (r1);
3822 8 : ASSERT_TRUE (r0.undefined_p ());
3823 :
3824 8 : if (HONOR_INFINITIES (float_type_node))
3825 : {
3826 : // Make sure [-Inf, -Inf] doesn't get normalized.
3827 4 : r0 = frange_float ("-Inf", "-Inf");
3828 4 : ASSERT_TRUE (real_isinf (&r0.lower_bound (), true));
3829 4 : ASSERT_TRUE (real_isinf (&r0.upper_bound (), true));
3830 : }
3831 :
3832 : // Test that reading back a global range yields the same result as
3833 : // what we wrote into it.
3834 8 : tree ssa = make_temp_ssa_name (float_type_node, NULL, "blah");
3835 8 : r0.set_varying (float_type_node);
3836 8 : r0.clear_nan ();
3837 8 : set_range_info (ssa, r0);
3838 8 : get_global_range_query ()->range_of_expr (r1, ssa);
3839 8 : ASSERT_EQ (r0, r1);
3840 8 : }
3841 :
3842 : // Run floating range tests for various combinations of NAN and INF
3843 : // support.
3844 :
3845 : static void
3846 4 : range_tests_floats_various ()
3847 : {
3848 4 : int save_finite_math_only = flag_finite_math_only;
3849 :
3850 : // Test -ffinite-math-only.
3851 4 : flag_finite_math_only = 1;
3852 4 : range_tests_floats ();
3853 : // Test -fno-finite-math-only.
3854 4 : flag_finite_math_only = 0;
3855 4 : range_tests_floats ();
3856 :
3857 4 : flag_finite_math_only = save_finite_math_only;
3858 4 : }
3859 :
3860 : void
3861 4 : range_tests ()
3862 : {
3863 4 : range_tests_irange3 ();
3864 4 : range_tests_int_range_max ();
3865 4 : range_tests_strict_enum ();
3866 4 : range_tests_nonzero_bits ();
3867 4 : range_tests_floats_various ();
3868 4 : range_tests_misc ();
3869 4 : }
3870 :
3871 : } // namespace selftest
3872 :
3873 : #endif // CHECKING_P
|
