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