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