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