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 : 1193864341 : irange_bitmask::irange_bitmask (tree type,
38 : 1193864341 : const wide_int &min, const wide_int &max)
39 : : {
40 : 1193864341 : unsigned prec = TYPE_PRECISION (type);
41 : : // All the bits of a singleton are known.
42 : 1193864341 : if (min == max)
43 : : {
44 : 165819979 : m_mask = wi::zero (prec);
45 : 165819979 : m_value = min;
46 : : }
47 : : else
48 : : {
49 : 1028044362 : wide_int xorv = min ^ max;
50 : : // Mask will have leading zeros for all leading bits that are
51 : : // common, both zeros and ones.
52 : 1028044362 : 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 : 1028054524 : m_value = ~m_mask & min;
55 : 1028044362 : }
56 : 1193864341 : }
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 : 122855261 : irange_bitmask::range_from_mask (irange &r, tree type) const
64 : : {
65 : 122855261 : if (unknown_p ())
66 : : return false;
67 : :
68 : 245556200 : gcc_checking_assert ((value () & mask ()) == 0);
69 : 122777803 : unsigned popcount = wi::popcount (mask ());
70 : :
71 : : // For 0, 1 or 2 bits set, create a range with only the allowed values.
72 : 122777803 : if (popcount <= 2)
73 : : {
74 : : // VALUE is always a valid range.
75 : 24624740 : r.set (type, value (), value ());
76 : : // If there are bits in mask, (VALUE | MASK) is also valid.
77 : 24624719 : if (popcount >= 1)
78 : 11718435 : r.union_ (int_range<1> (type, value () | mask (), value () | mask ()));
79 : : // If there are 2 bits set, add the other 2 possible values.
80 : 11718355 : if (popcount == 2)
81 : : {
82 : : // Extract the two 1-bit masks into lb and ub.
83 : 4878533 : wide_int lb = mask () & -mask (); // Lowest set bit.
84 : 4878533 : wide_int ub = mask () & (mask () - 1); // The other bit.
85 : 4878533 : r.union_ (int_range<1> (type, value () | lb, value () | lb));
86 : 4878533 : r.union_ (int_range<1> (type, value () | ub, value () | ub));
87 : 4878533 : }
88 : 24624719 : return true;
89 : : }
90 : :
91 : : // Otherwise, calculate the valid range allowed by the bitmask.
92 : 98153084 : int prec = TYPE_PRECISION (type);
93 : 98153657 : wide_int ub = mask () | value ();
94 : 98153084 : wide_int sign_bit = wi::one (prec) << (prec - 1);
95 : 98153084 : wide_int sign_mask = mask () & sign_bit;
96 : 98153084 : 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 : 98153084 : if (TYPE_SIGN (type) == UNSIGNED || (sign_mask == 0 && sign_value == 0))
100 : 91276134 : r.set (type, value (), mask () | value ());
101 : : // If the sign bit is KNOWN to be 1, we have a completely negative range.
102 : 6879122 : else if (sign_mask == 0 && sign_value != 0)
103 : 690919 : r.set (type, value (), value () | (mask () & ~sign_bit));
104 : : else
105 : : {
106 : : // Otherwise there are 2 ranges, a negative and positive interval.
107 : 6188233 : wide_int neg_base = value () | sign_bit;
108 : 6188258 : wide_int pos_mask = mask () & ~sign_bit;
109 : 6188233 : r.set (type, neg_base , neg_base | pos_mask);
110 : 6188308 : r.union_ (int_range<1> (type, value (), value () | pos_mask));
111 : 6188258 : }
112 : :
113 : : // If the mask doesn't have a trailing zero, there is nothing else to filter.
114 : 98153084 : int z = wi::ctz (mask ());
115 : 98153084 : 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 : 29458192 : ub = (wi::one (prec) << z) - 1; // Upper bound of range.
122 : 29458173 : 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 : 29458173 : wide_int allow = value () & ub;
125 : 29458173 : mask_range.intersect (int_range<2> (type, allow, allow, VR_ANTI_RANGE));
126 : 29458173 : mask_range.invert ();
127 : 29458173 : r.intersect (mask_range);
128 : :
129 : 29458173 : 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 : 11251168 : wide_int lb = -(wi::one (prec) << z);
134 : 11251168 : int_range<4> mask_range (type, lb, wi::minus_one (prec));
135 : : // Remove the one allowed value from that set.
136 : 11251168 : wide_int allow = value () | lb;
137 : 11251168 : mask_range.intersect (int_range<2> (type, allow, allow, VR_ANTI_RANGE));
138 : 11251168 : mask_range.invert ();
139 : 11251168 : r.intersect (mask_range);
140 : 11251187 : }
141 : 29458173 : return true;
142 : 127612976 : }
143 : :
144 : :
145 : : void
146 : 36585 : irange::accept (const vrange_visitor &v) const
147 : : {
148 : 36585 : v.visit (*this);
149 : 36585 : }
150 : :
151 : : void
152 : 22326 : value_range::dump (FILE *out) const
153 : : {
154 : 22326 : if (m_vrange)
155 : 22326 : m_vrange->dump (out);
156 : : else
157 : 0 : fprintf (out, "NULL");
158 : 22326 : }
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 : 731 : unsupported_range::accept (const vrange_visitor &v) const
178 : : {
179 : 731 : v.visit (*this);
180 : 731 : }
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 : 1108604 : unsupported_range::singleton_p (tree *) const
202 : : {
203 : 1108604 : 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 : 111421724 : unsupported_range::set_undefined ()
226 : : {
227 : 111421724 : m_kind = VR_UNDEFINED;
228 : 111421724 : }
229 : :
230 : : void
231 : 3384384 : unsupported_range::set_varying (tree)
232 : : {
233 : 3384384 : m_kind = VR_VARYING;
234 : 3384384 : }
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 : 1052730 : unsupported_range::operator= (const unsupported_range &r)
311 : : {
312 : 1052730 : if (r.undefined_p ())
313 : 1052730 : set_undefined ();
314 : 0 : else if (r.varying_p ())
315 : 0 : set_varying (void_type_node);
316 : : else
317 : 0 : gcc_unreachable ();
318 : 1052730 : 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 : 10450954 : vrange::operator= (const vrange &src)
338 : : {
339 : 10450954 : if (is_a <irange> (src))
340 : 9109704 : as_a <irange> (*this) = as_a <irange> (src);
341 : 1341250 : else if (is_a <prange> (src))
342 : 1072921 : as_a <prange> (*this) = as_a <prange> (src);
343 : 268329 : else if (is_a <frange> (src))
344 : 268329 : 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 : 10450954 : return *this;
351 : : }
352 : :
353 : : // Equality operator for generic ranges.
354 : :
355 : : bool
356 : 40077449 : vrange::operator== (const vrange &src) const
357 : : {
358 : 40077449 : if (is_a <irange> (src))
359 : 34941377 : return as_a <irange> (*this) == as_a <irange> (src);
360 : 5136072 : if (is_a <prange> (src))
361 : 5086047 : return as_a <prange> (*this) == as_a <prange> (src);
362 : 50025 : if (is_a <frange> (src))
363 : 50025 : 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 : 35943 : vrange::dump (FILE *file) const
371 : : {
372 : 35943 : pretty_printer pp;
373 : 35943 : pp_needs_newline (&pp) = true;
374 : 35943 : pp.set_output_stream (file);
375 : 35943 : vrange_printer vrange_pp (&pp);
376 : 35943 : this->accept (vrange_pp);
377 : 35943 : pp_flush (&pp);
378 : 35943 : }
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 : 23315742 : add_vrange (const vrange &v, inchash::hash &hstate,
408 : : unsigned int)
409 : : {
410 : 23315742 : 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 : 23315742 : if (is_a <irange> (v))
420 : : {
421 : 16744735 : const irange &r = as_a <irange> (v);
422 : 16744735 : if (r.varying_p ())
423 : 0 : hstate.add_int (VR_VARYING);
424 : : else
425 : 16744735 : hstate.add_int (VR_RANGE);
426 : 36486161 : for (unsigned i = 0; i < r.num_pairs (); ++i)
427 : : {
428 : 19741426 : hstate.add_wide_int (r.lower_bound (i));
429 : 19741549 : hstate.add_wide_int (r.upper_bound (i));
430 : : }
431 : 16744735 : irange_bitmask bm = r.get_bitmask ();
432 : 16744735 : hstate.add_wide_int (bm.value ());
433 : 16744735 : hstate.add_wide_int (bm.mask ());
434 : 16744735 : return;
435 : 16744735 : }
436 : 6571007 : if (is_a <prange> (v))
437 : : {
438 : 6480560 : const prange &r = as_a <prange> (v);
439 : 6480560 : if (r.varying_p ())
440 : 0 : hstate.add_int (VR_VARYING);
441 : : else
442 : : {
443 : 6480560 : hstate.add_int (VR_RANGE);
444 : 6480560 : hstate.add_wide_int (r.lower_bound ());
445 : 6480560 : hstate.add_wide_int (r.upper_bound ());
446 : 6480560 : irange_bitmask bm = r.get_bitmask ();
447 : 6480560 : hstate.add_wide_int (bm.value ());
448 : 6480560 : hstate.add_wide_int (bm.mask ());
449 : 6480560 : }
450 : 6480560 : return;
451 : : }
452 : 90447 : if (is_a <frange> (v))
453 : : {
454 : 90447 : const frange &r = as_a <frange> (v);
455 : 90447 : if (r.known_isnan ())
456 : 260 : hstate.add_int (VR_NAN);
457 : : else
458 : : {
459 : 90187 : hstate.add_int (r.varying_p () ? VR_VARYING : VR_RANGE);
460 : 90187 : hstate.add_real_value (r.lower_bound ());
461 : 90187 : hstate.add_real_value (r.upper_bound ());
462 : : }
463 : 90447 : nan_state nan = r.get_nan_state ();
464 : 90447 : hstate.add_int (nan.pos_p ());
465 : 90447 : hstate.add_int (nan.neg_p ());
466 : 90447 : return;
467 : : }
468 : 0 : gcc_unreachable ();
469 : : }
470 : :
471 : : } //namespace inchash
472 : :
473 : : bool
474 : 35242 : irange::nonnegative_p () const
475 : : {
476 : 35242 : return wi::ge_p (lower_bound (), 0, TYPE_SIGN (type ()));
477 : : }
478 : :
479 : : bool
480 : 30924 : irange::nonpositive_p () const
481 : : {
482 : 30924 : return wi::le_p (upper_bound (), 0, TYPE_SIGN (type ()));
483 : : }
484 : :
485 : : bool
486 : 426305279 : irange::supports_type_p (const_tree type) const
487 : : {
488 : 426305279 : 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 : 41060405 : irange::set_nonnegative (tree type)
501 : : {
502 : 41060405 : set (type,
503 : 82120810 : wi::zero (TYPE_PRECISION (type)),
504 : 41060405 : wi::to_wide (TYPE_MAX_VALUE (type)));
505 : 41060405 : }
506 : :
507 : : // Prange implementation.
508 : :
509 : : void
510 : 1302 : prange::accept (const vrange_visitor &v) const
511 : : {
512 : 1302 : v.visit (*this);
513 : 1302 : }
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 : 14047193 : prange::set (tree min, tree max, value_range_kind kind)
525 : : {
526 : 14047193 : return set (TREE_TYPE (min), wi::to_wide (min), wi::to_wide (max), kind);
527 : : }
528 : :
529 : : void
530 : 40264393 : prange::set (tree type, const wide_int &min, const wide_int &max,
531 : : value_range_kind kind)
532 : : {
533 : 40264393 : if (kind == VR_UNDEFINED)
534 : : {
535 : 0 : set_undefined ();
536 : 0 : return;
537 : : }
538 : 40264393 : if (kind == VR_VARYING)
539 : : {
540 : 0 : set_varying (type);
541 : 0 : return;
542 : : }
543 : 40264393 : 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 : 40264393 : m_type = type;
550 : 40264393 : m_min = min;
551 : 40264393 : m_max = max;
552 : 40264393 : if (m_min == 0 && m_max == -1)
553 : : {
554 : 5001933 : m_kind = VR_VARYING;
555 : 5001933 : m_bitmask.set_unknown (TYPE_PRECISION (type));
556 : 5001933 : if (flag_checking)
557 : 5001933 : verify_range ();
558 : 5001933 : return;
559 : : }
560 : :
561 : 35262460 : m_kind = VR_RANGE;
562 : 35262460 : m_bitmask = irange_bitmask (type, min, max);
563 : 35262460 : if (flag_checking)
564 : 35262448 : verify_range ();
565 : : }
566 : :
567 : : bool
568 : 3040843 : prange::contains_p (const wide_int &w) const
569 : : {
570 : 3040843 : if (undefined_p ())
571 : : return false;
572 : :
573 : 3040843 : if (varying_p ())
574 : : return true;
575 : :
576 : 4721480 : return (wi::le_p (lower_bound (), w, UNSIGNED)
577 : 2362466 : && wi::ge_p (upper_bound (), w, UNSIGNED));
578 : : }
579 : :
580 : : bool
581 : 218620999 : prange::singleton_p (tree *result) const
582 : : {
583 : 310678667 : if (m_kind == VR_RANGE && lower_bound () == upper_bound ())
584 : : {
585 : 230695 : if (result)
586 : 79283 : *result = wide_int_to_tree (type (), m_min);
587 : 230695 : return true;
588 : : }
589 : : return false;
590 : : }
591 : :
592 : : tree
593 : 4819885 : prange::lbound () const
594 : : {
595 : 4819885 : return wide_int_to_tree (type (), m_min);
596 : : }
597 : :
598 : : tree
599 : 802126 : prange::ubound () const
600 : : {
601 : 802126 : return wide_int_to_tree (type (), m_max);
602 : : }
603 : :
604 : : bool
605 : 17347229 : prange::union_ (const vrange &v)
606 : : {
607 : 17347229 : const prange &r = as_a <prange> (v);
608 : :
609 : 17347229 : if (r.undefined_p ())
610 : : return false;
611 : 17204319 : if (undefined_p ())
612 : : {
613 : 8715452 : *this = r;
614 : 8715452 : if (flag_checking)
615 : 8715452 : verify_range ();
616 : 8715452 : return true;
617 : : }
618 : 8488867 : if (varying_p ())
619 : : return false;
620 : 4503255 : if (r.varying_p ())
621 : : {
622 : 1263456 : set_varying (type ());
623 : 1263456 : return true;
624 : : }
625 : :
626 : 3239799 : wide_int new_lb = wi::min (r.lower_bound (), lower_bound (), UNSIGNED);
627 : 3239799 : wide_int new_ub = wi::max (r.upper_bound (), upper_bound (), UNSIGNED);
628 : 3239799 : prange new_range (type (), new_lb, new_ub);
629 : 3239799 : new_range.m_bitmask.union_ (m_bitmask);
630 : 3239799 : new_range.m_bitmask.union_ (r.m_bitmask);
631 : 3239799 : if (new_range.varying_compatible_p ())
632 : : {
633 : 336552 : set_varying (type ());
634 : 336552 : return true;
635 : : }
636 : 2903247 : if (flag_checking)
637 : 2903247 : new_range.verify_range ();
638 : 2903247 : if (new_range == *this)
639 : : return false;
640 : 52513 : *this = new_range;
641 : 52513 : return true;
642 : 3239799 : }
643 : :
644 : : bool
645 : 194762543 : prange::intersect (const vrange &v)
646 : : {
647 : 194762543 : const prange &r = as_a <prange> (v);
648 : 194762543 : gcc_checking_assert (undefined_p () || r.undefined_p ()
649 : : || range_compatible_p (type (), r.type ()));
650 : :
651 : 194762543 : if (undefined_p ())
652 : : return false;
653 : 194654961 : if (r.undefined_p ())
654 : : {
655 : 26463 : set_undefined ();
656 : 26463 : return true;
657 : : }
658 : 194628498 : if (r.varying_p ())
659 : : return false;
660 : 106131512 : if (varying_p ())
661 : : {
662 : 47961468 : *this = r;
663 : 47961468 : return true;
664 : : }
665 : :
666 : 58170044 : prange save = *this;
667 : 58170044 : m_min = wi::max (r.lower_bound (), lower_bound (), UNSIGNED);
668 : 58170044 : m_max = wi::min (r.upper_bound (), upper_bound (), UNSIGNED);
669 : 58170044 : if (wi::gt_p (m_min, m_max, UNSIGNED))
670 : : {
671 : 373626 : set_undefined ();
672 : 373626 : return true;
673 : : }
674 : :
675 : : // Intersect all bitmasks: the old one, the new one, and the other operand's.
676 : 57796418 : irange_bitmask new_bitmask (m_type, m_min, m_max);
677 : 57796418 : if (!m_bitmask.intersect (new_bitmask))
678 : 12 : set_undefined ();
679 : 57796406 : else if (!m_bitmask.intersect (r.m_bitmask))
680 : 4 : set_undefined ();
681 : 57796418 : if (varying_compatible_p ())
682 : : {
683 : 0 : set_varying (type ());
684 : 0 : return true;
685 : : }
686 : :
687 : 57796418 : if (flag_checking)
688 : 57796313 : verify_range ();
689 : 57796418 : if (*this == save)
690 : : return false;
691 : : return true;
692 : 58170044 : }
693 : :
694 : : prange &
695 : 187875886 : prange::operator= (const prange &src)
696 : : {
697 : 187875886 : m_type = src.m_type;
698 : 187875886 : m_kind = src.m_kind;
699 : 187875886 : m_min = src.m_min;
700 : 187875886 : m_max = src.m_max;
701 : 187875886 : m_bitmask = src.m_bitmask;
702 : 187875886 : if (flag_checking)
703 : 187875751 : verify_range ();
704 : 187875886 : return *this;
705 : : }
706 : :
707 : : bool
708 : 70871169 : prange::operator== (const prange &src) const
709 : : {
710 : 70871169 : if (m_kind == src.m_kind)
711 : : {
712 : 70307953 : if (undefined_p ())
713 : : return true;
714 : :
715 : 70300737 : if (varying_p ())
716 : 1013271 : return types_compatible_p (type (), src.type ());
717 : :
718 : 137651286 : return (m_min == src.m_min && m_max == src.m_max
719 : 137286249 : && m_bitmask == src.m_bitmask);
720 : : }
721 : : return false;
722 : : }
723 : :
724 : : void
725 : 2671125 : prange::invert ()
726 : : {
727 : 2671125 : gcc_checking_assert (!undefined_p () && !varying_p ());
728 : :
729 : 2671125 : wide_int new_lb, new_ub;
730 : 2671125 : unsigned prec = TYPE_PRECISION (type ());
731 : 2671125 : wide_int type_min = wi::zero (prec);
732 : 2671125 : wide_int type_max = wi::max_value (prec, UNSIGNED);
733 : 2671125 : wi::overflow_type ovf;
734 : :
735 : 2671125 : if (lower_bound () == type_min)
736 : : {
737 : 2664359 : new_lb = wi::add (upper_bound (), 1, UNSIGNED, &ovf);
738 : 2664359 : if (ovf)
739 : 0 : new_lb = type_min;
740 : 2664359 : new_ub = type_max;
741 : 2664359 : set (type (), new_lb, new_ub);
742 : : }
743 : 6766 : else if (upper_bound () == type_max)
744 : : {
745 : 2802 : wi::overflow_type ovf;
746 : 2802 : new_lb = type_min;
747 : 2802 : new_ub = wi::sub (lower_bound (), 1, UNSIGNED, &ovf);
748 : 2802 : if (ovf)
749 : 0 : new_ub = type_max;
750 : 2802 : set (type (), new_lb, new_ub);
751 : : }
752 : : else
753 : 3964 : set_varying (type ());
754 : 2671125 : }
755 : :
756 : : void
757 : 984134223 : prange::verify_range () const
758 : : {
759 : 984134223 : gcc_checking_assert (m_discriminator == VR_PRANGE);
760 : :
761 : 984134223 : if (m_kind == VR_UNDEFINED)
762 : : return;
763 : :
764 : 984075284 : gcc_checking_assert (supports_p (type ()));
765 : :
766 : 984075284 : if (m_kind == VR_VARYING)
767 : : {
768 : 476348506 : gcc_checking_assert (varying_compatible_p ());
769 : : return;
770 : : }
771 : 507726778 : gcc_checking_assert (!varying_compatible_p ());
772 : 507726778 : gcc_checking_assert (m_kind == VR_RANGE);
773 : : }
774 : :
775 : : void
776 : 29795202 : prange::update_bitmask (const irange_bitmask &bm)
777 : : {
778 : 29795202 : gcc_checking_assert (!undefined_p ());
779 : :
780 : : // If all the bits are known, this is a singleton.
781 : 29795202 : if (bm.mask () == 0)
782 : : {
783 : 151999 : set (type (), bm.value (), bm.value ());
784 : 151999 : return;
785 : : }
786 : :
787 : : // Drop VARYINGs with known bits to a plain range.
788 : 37150050 : if (m_kind == VR_VARYING && !bm.unknown_p ())
789 : 196824 : m_kind = VR_RANGE;
790 : :
791 : 29643203 : m_bitmask = bm;
792 : 29643203 : if (varying_compatible_p ())
793 : 7310023 : m_kind = VR_VARYING;
794 : :
795 : 29643203 : if (flag_checking)
796 : 29643203 : verify_range ();
797 : : }
798 : :
799 : :
800 : : // Frange implementation.
801 : :
802 : : void
803 : 448 : frange::accept (const vrange_visitor &v) const
804 : : {
805 : 448 : v.visit (*this);
806 : 448 : }
807 : :
808 : : bool
809 : 0 : frange::fits_p (const vrange &) const
810 : : {
811 : 0 : return true;
812 : : }
813 : :
814 : : // Flush denormal endpoints to the appropriate 0.0.
815 : :
816 : : void
817 : 6805301 : frange::flush_denormals_to_zero ()
818 : : {
819 : 6805301 : if (undefined_p () || known_isnan ())
820 : : return;
821 : :
822 : 6805301 : machine_mode mode = TYPE_MODE (type ());
823 : : // Flush [x, -DENORMAL] to [x, -0.0].
824 : 6805301 : if (real_isdenormal (&m_max, mode) && real_isneg (&m_max))
825 : : {
826 : 2114 : if (HONOR_SIGNED_ZEROS (m_type))
827 : 2114 : m_max = dconstm0;
828 : : else
829 : 0 : m_max = dconst0;
830 : : }
831 : : // Flush [+DENORMAL, x] to [+0.0, x].
832 : 6805301 : if (real_isdenormal (&m_min, mode) && !real_isneg (&m_min))
833 : 3776 : m_min = dconst0;
834 : : }
835 : :
836 : : // Setter for franges.
837 : :
838 : : void
839 : 64602024 : frange::set (tree type,
840 : : const REAL_VALUE_TYPE &min, const REAL_VALUE_TYPE &max,
841 : : const nan_state &nan, value_range_kind kind)
842 : : {
843 : 64602024 : switch (kind)
844 : : {
845 : 0 : case VR_UNDEFINED:
846 : 0 : set_undefined ();
847 : 0 : return;
848 : 33037509 : case VR_VARYING:
849 : 33037509 : case VR_ANTI_RANGE:
850 : 33037509 : set_varying (type);
851 : 33037509 : return;
852 : 31564515 : case VR_RANGE:
853 : 31564515 : break;
854 : 0 : default:
855 : 0 : gcc_unreachable ();
856 : : }
857 : :
858 : 31564515 : gcc_checking_assert (!real_isnan (&min) && !real_isnan (&max));
859 : :
860 : 31564515 : m_kind = kind;
861 : 31564515 : m_type = type;
862 : 31564515 : m_min = min;
863 : 31564515 : m_max = max;
864 : 31564515 : if (HONOR_NANS (m_type))
865 : : {
866 : 30670317 : m_pos_nan = nan.pos_p ();
867 : 30670317 : m_neg_nan = nan.neg_p ();
868 : : }
869 : : else
870 : : {
871 : 894198 : m_pos_nan = false;
872 : 894198 : m_neg_nan = false;
873 : : }
874 : :
875 : 126258060 : if (!MODE_HAS_SIGNED_ZEROS (TYPE_MODE (m_type)))
876 : : {
877 : 0 : if (real_iszero (&m_min, 1))
878 : 0 : m_min.sign = 0;
879 : 0 : if (real_iszero (&m_max, 1))
880 : 0 : m_max.sign = 0;
881 : : }
882 : 31564515 : else if (!HONOR_SIGNED_ZEROS (m_type))
883 : : {
884 : 929231 : if (real_iszero (&m_max, 1))
885 : 26 : m_max.sign = 0;
886 : 929231 : if (real_iszero (&m_min, 0))
887 : 29344 : m_min.sign = 1;
888 : : }
889 : :
890 : : // For -ffinite-math-only we can drop ranges outside the
891 : : // representable numbers to min/max for the type.
892 : 31564515 : if (!HONOR_INFINITIES (m_type))
893 : : {
894 : 894198 : REAL_VALUE_TYPE min_repr = frange_val_min (m_type);
895 : 894198 : REAL_VALUE_TYPE max_repr = frange_val_max (m_type);
896 : 894198 : if (real_less (&m_min, &min_repr))
897 : 314493 : m_min = min_repr;
898 : 579705 : else if (real_less (&max_repr, &m_min))
899 : 1 : m_min = max_repr;
900 : 894198 : if (real_less (&max_repr, &m_max))
901 : 317387 : m_max = max_repr;
902 : 576811 : else if (real_less (&m_max, &min_repr))
903 : 0 : m_max = min_repr;
904 : : }
905 : :
906 : : // Check for swapped ranges.
907 : 31564515 : gcc_checking_assert (real_compare (LE_EXPR, &min, &max));
908 : :
909 : 31564515 : normalize_kind ();
910 : : }
911 : :
912 : : // Setter for an frange defaulting the NAN possibility to +-NAN when
913 : : // HONOR_NANS.
914 : :
915 : : void
916 : 51126847 : frange::set (tree type,
917 : : const REAL_VALUE_TYPE &min, const REAL_VALUE_TYPE &max,
918 : : value_range_kind kind)
919 : : {
920 : 51126847 : set (type, min, max, nan_state (true), kind);
921 : 51126847 : }
922 : :
923 : : void
924 : 16 : frange::set (tree min, tree max, value_range_kind kind)
925 : : {
926 : 32 : set (TREE_TYPE (min),
927 : 16 : *TREE_REAL_CST_PTR (min), *TREE_REAL_CST_PTR (max), kind);
928 : 16 : }
929 : :
930 : : // Normalize range to VARYING or UNDEFINED, or vice versa. Return
931 : : // TRUE if anything changed.
932 : : //
933 : : // A range with no known properties can be dropped to VARYING.
934 : : // Similarly, a VARYING with any properties should be dropped to a
935 : : // VR_RANGE. Normalizing ranges upon changing them ensures there is
936 : : // only one representation for a given range.
937 : :
938 : : bool
939 : 62332482 : frange::normalize_kind ()
940 : : {
941 : 62332482 : if (m_kind == VR_RANGE
942 : 54850776 : && frange_val_is_min (m_min, m_type)
943 : 73683399 : && frange_val_is_max (m_max, m_type))
944 : : {
945 : 8279151 : if (!HONOR_NANS (m_type) || (m_pos_nan && m_neg_nan))
946 : : {
947 : 6755120 : set_varying (m_type);
948 : 6755120 : return true;
949 : : }
950 : : }
951 : 54053331 : else if (m_kind == VR_VARYING)
952 : : {
953 : 7481415 : if (HONOR_NANS (m_type) && (!m_pos_nan || !m_neg_nan))
954 : : {
955 : 2008470 : m_kind = VR_RANGE;
956 : 2008470 : m_min = frange_val_min (m_type);
957 : 2008470 : m_max = frange_val_max (m_type);
958 : 2008470 : if (flag_checking)
959 : 2008470 : verify_range ();
960 : 2008470 : return true;
961 : : }
962 : : }
963 : 46571916 : else if (m_kind == VR_NAN && !m_pos_nan && !m_neg_nan)
964 : 4 : set_undefined ();
965 : : return false;
966 : : }
967 : :
968 : : // Union or intersect the zero endpoints of two ranges. For example:
969 : : // [-0, x] U [+0, x] => [-0, x]
970 : : // [ x, -0] U [ x, +0] => [ x, +0]
971 : : // [-0, x] ^ [+0, x] => [+0, x]
972 : : // [ x, -0] ^ [ x, +0] => [ x, -0]
973 : : //
974 : : // UNION_P is true when performing a union, or false when intersecting.
975 : :
976 : : bool
977 : 8820992 : frange::combine_zeros (const frange &r, bool union_p)
978 : : {
979 : 8820992 : gcc_checking_assert (!undefined_p () && !known_isnan ());
980 : :
981 : 8820992 : bool changed = false;
982 : 11739829 : if (real_iszero (&m_min) && real_iszero (&r.m_min)
983 : 11312474 : && real_isneg (&m_min) != real_isneg (&r.m_min))
984 : : {
985 : 166300 : m_min.sign = union_p;
986 : 166300 : changed = true;
987 : : }
988 : 9037822 : if (real_iszero (&m_max) && real_iszero (&r.m_max)
989 : 8994249 : && real_isneg (&m_max) != real_isneg (&r.m_max))
990 : : {
991 : 3945 : m_max.sign = !union_p;
992 : 3945 : changed = true;
993 : : }
994 : : // If the signs are swapped, the resulting range is empty.
995 : 8820992 : if (m_min.sign == 0 && m_max.sign == 1)
996 : : {
997 : 136 : if (maybe_isnan ())
998 : 8 : m_kind = VR_NAN;
999 : : else
1000 : 64 : set_undefined ();
1001 : : changed = true;
1002 : : }
1003 : 8820992 : return changed;
1004 : : }
1005 : :
1006 : : // Union two ranges when one is known to be a NAN.
1007 : :
1008 : : bool
1009 : 207557 : frange::union_nans (const frange &r)
1010 : : {
1011 : 207557 : gcc_checking_assert (known_isnan () || r.known_isnan ());
1012 : :
1013 : 207557 : bool changed = false;
1014 : 207557 : if (known_isnan () && m_kind != r.m_kind)
1015 : : {
1016 : 41121 : m_kind = r.m_kind;
1017 : 41121 : m_min = r.m_min;
1018 : 41121 : m_max = r.m_max;
1019 : 41121 : changed = true;
1020 : : }
1021 : 207557 : if (m_pos_nan != r.m_pos_nan || m_neg_nan != r.m_neg_nan)
1022 : : {
1023 : 198066 : m_pos_nan |= r.m_pos_nan;
1024 : 198066 : m_neg_nan |= r.m_neg_nan;
1025 : 198066 : changed = true;
1026 : : }
1027 : 207557 : if (changed)
1028 : : {
1029 : 205978 : normalize_kind ();
1030 : 205978 : return true;
1031 : : }
1032 : : return false;
1033 : : }
1034 : :
1035 : : bool
1036 : 3906128 : frange::union_ (const vrange &v)
1037 : : {
1038 : 3906128 : const frange &r = as_a <frange> (v);
1039 : :
1040 : 3906128 : if (r.undefined_p () || varying_p ())
1041 : : return false;
1042 : 3239822 : if (undefined_p () || r.varying_p ())
1043 : : {
1044 : 1936158 : *this = r;
1045 : 1936158 : return true;
1046 : : }
1047 : :
1048 : : // Combine NAN info.
1049 : 1303664 : if (known_isnan () || r.known_isnan ())
1050 : 207557 : return union_nans (r);
1051 : 1096107 : bool changed = false;
1052 : 1096107 : if (m_pos_nan != r.m_pos_nan || m_neg_nan != r.m_neg_nan)
1053 : : {
1054 : 386673 : m_pos_nan |= r.m_pos_nan;
1055 : 386673 : m_neg_nan |= r.m_neg_nan;
1056 : 386673 : changed = true;
1057 : : }
1058 : :
1059 : : // Combine endpoints.
1060 : 1096107 : if (real_less (&r.m_min, &m_min))
1061 : : {
1062 : 517709 : m_min = r.m_min;
1063 : 517709 : changed = true;
1064 : : }
1065 : 1096107 : if (real_less (&m_max, &r.m_max))
1066 : : {
1067 : 81040 : m_max = r.m_max;
1068 : 81040 : changed = true;
1069 : : }
1070 : :
1071 : 1096107 : if (HONOR_SIGNED_ZEROS (m_type))
1072 : 1092159 : changed |= combine_zeros (r, true);
1073 : :
1074 : 1096107 : changed |= normalize_kind ();
1075 : 1096107 : return changed;
1076 : : }
1077 : :
1078 : : // Intersect two ranges when one is known to be a NAN.
1079 : :
1080 : : bool
1081 : 51405 : frange::intersect_nans (const frange &r)
1082 : : {
1083 : 51405 : gcc_checking_assert (known_isnan () || r.known_isnan ());
1084 : :
1085 : 51405 : m_pos_nan &= r.m_pos_nan;
1086 : 51405 : m_neg_nan &= r.m_neg_nan;
1087 : 53981 : if (maybe_isnan ())
1088 : 48861 : m_kind = VR_NAN;
1089 : : else
1090 : 2544 : set_undefined ();
1091 : 51405 : if (flag_checking)
1092 : 51405 : verify_range ();
1093 : 51405 : return true;
1094 : : }
1095 : :
1096 : : bool
1097 : 25487285 : frange::intersect (const vrange &v)
1098 : : {
1099 : 25487285 : const frange &r = as_a <frange> (v);
1100 : :
1101 : 25487285 : if (undefined_p () || r.varying_p ())
1102 : : return false;
1103 : 10237210 : if (r.undefined_p ())
1104 : : {
1105 : 5526 : set_undefined ();
1106 : 5526 : return true;
1107 : : }
1108 : 10231684 : if (varying_p ())
1109 : : {
1110 : 2333522 : *this = r;
1111 : 2333522 : return true;
1112 : : }
1113 : :
1114 : : // Combine NAN info.
1115 : 7898162 : if (known_isnan () || r.known_isnan ())
1116 : 51405 : return intersect_nans (r);
1117 : 7846757 : bool changed = false;
1118 : 7846757 : if (m_pos_nan != r.m_pos_nan || m_neg_nan != r.m_neg_nan)
1119 : : {
1120 : 2547610 : m_pos_nan &= r.m_pos_nan;
1121 : 2547610 : m_neg_nan &= r.m_neg_nan;
1122 : 2547610 : changed = true;
1123 : : }
1124 : :
1125 : : // Combine endpoints.
1126 : 7846757 : if (real_less (&m_min, &r.m_min))
1127 : : {
1128 : 1546020 : m_min = r.m_min;
1129 : 1546020 : changed = true;
1130 : : }
1131 : 7846757 : if (real_less (&r.m_max, &m_max))
1132 : : {
1133 : 1321200 : m_max = r.m_max;
1134 : 1321200 : changed = true;
1135 : : }
1136 : : // If the endpoints are swapped, the resulting range is empty.
1137 : 7846757 : if (real_less (&m_max, &m_min))
1138 : : {
1139 : 37047 : if (maybe_isnan ())
1140 : 29079 : m_kind = VR_NAN;
1141 : : else
1142 : 3984 : set_undefined ();
1143 : 33063 : if (flag_checking)
1144 : 33063 : verify_range ();
1145 : 33063 : return true;
1146 : : }
1147 : :
1148 : 7813694 : if (HONOR_SIGNED_ZEROS (m_type))
1149 : 7728833 : changed |= combine_zeros (r, false);
1150 : :
1151 : 7813694 : changed |= normalize_kind ();
1152 : 7813694 : return changed;
1153 : : }
1154 : :
1155 : : frange &
1156 : 54909924 : frange::operator= (const frange &src)
1157 : : {
1158 : 54909924 : m_kind = src.m_kind;
1159 : 54909924 : m_type = src.m_type;
1160 : 54909924 : m_min = src.m_min;
1161 : 54909924 : m_max = src.m_max;
1162 : 54909924 : m_pos_nan = src.m_pos_nan;
1163 : 54909924 : m_neg_nan = src.m_neg_nan;
1164 : :
1165 : 54909924 : if (flag_checking)
1166 : 54909924 : verify_range ();
1167 : 54909924 : return *this;
1168 : : }
1169 : :
1170 : : bool
1171 : 70899 : frange::operator== (const frange &src) const
1172 : : {
1173 : 70899 : if (m_kind == src.m_kind)
1174 : : {
1175 : 60624 : if (undefined_p ())
1176 : : return true;
1177 : :
1178 : 60485 : if (varying_p ())
1179 : 25418 : return types_compatible_p (m_type, src.m_type);
1180 : :
1181 : 35067 : bool nan1 = known_isnan ();
1182 : 35067 : bool nan2 = src.known_isnan ();
1183 : 35067 : if (nan1 || nan2)
1184 : : {
1185 : 123 : if (nan1 && nan2)
1186 : 123 : return (m_pos_nan == src.m_pos_nan
1187 : 123 : && m_neg_nan == src.m_neg_nan);
1188 : : return false;
1189 : : }
1190 : :
1191 : 34944 : return (real_identical (&m_min, &src.m_min)
1192 : 30529 : && real_identical (&m_max, &src.m_max)
1193 : 30191 : && m_pos_nan == src.m_pos_nan
1194 : 30168 : && m_neg_nan == src.m_neg_nan
1195 : 64899 : && types_compatible_p (m_type, src.m_type));
1196 : : }
1197 : : return false;
1198 : : }
1199 : :
1200 : : // Return TRUE if range contains R.
1201 : :
1202 : : bool
1203 : 51671 : frange::contains_p (const REAL_VALUE_TYPE &r) const
1204 : : {
1205 : 51671 : gcc_checking_assert (m_kind != VR_ANTI_RANGE);
1206 : :
1207 : 51671 : if (undefined_p ())
1208 : : return false;
1209 : :
1210 : 51671 : if (varying_p ())
1211 : : return true;
1212 : :
1213 : 49142 : if (real_isnan (&r))
1214 : : {
1215 : : // No NAN in range.
1216 : 0 : if (!m_pos_nan && !m_neg_nan)
1217 : : return false;
1218 : : // Both +NAN and -NAN are present.
1219 : 0 : if (m_pos_nan && m_neg_nan)
1220 : : return true;
1221 : 0 : return m_neg_nan == r.sign;
1222 : : }
1223 : 49142 : if (known_isnan ())
1224 : : return false;
1225 : :
1226 : 49142 : if (real_compare (GE_EXPR, &r, &m_min) && real_compare (LE_EXPR, &r, &m_max))
1227 : : {
1228 : : // Make sure the signs are equal for signed zeros.
1229 : 16240 : if (HONOR_SIGNED_ZEROS (m_type) && real_iszero (&r))
1230 : 32206 : return r.sign == m_min.sign || r.sign == m_max.sign;
1231 : 17 : return true;
1232 : : }
1233 : : return false;
1234 : : }
1235 : :
1236 : : // If range is a singleton, place it in RESULT and return TRUE. If
1237 : : // RESULT is NULL, just return TRUE.
1238 : : //
1239 : : // A NAN can never be a singleton.
1240 : :
1241 : : bool
1242 : 23780703 : frange::internal_singleton_p (REAL_VALUE_TYPE *result) const
1243 : : {
1244 : 23780703 : if (m_kind == VR_RANGE && real_identical (&m_min, &m_max))
1245 : : {
1246 : : // Return false for any singleton that may be a NAN.
1247 : 23893267 : if (HONOR_NANS (m_type) && maybe_isnan ())
1248 : : return false;
1249 : :
1250 : 778876 : if (MODE_COMPOSITE_P (TYPE_MODE (m_type)))
1251 : : {
1252 : : // For IBM long doubles, if the value is +-Inf or is exactly
1253 : : // representable in double, the other double could be +0.0
1254 : : // or -0.0. Since this means there is more than one way to
1255 : : // represent a value, return false to avoid propagating it.
1256 : : // See libgcc/config/rs6000/ibm-ldouble-format for details.
1257 : 0 : if (real_isinf (&m_min))
1258 : 0 : return false;
1259 : 0 : REAL_VALUE_TYPE r;
1260 : 0 : real_convert (&r, DFmode, &m_min);
1261 : 0 : if (real_identical (&r, &m_min))
1262 : : return false;
1263 : : }
1264 : :
1265 : 111268 : if (result)
1266 : 0 : *result = m_min;
1267 : 111268 : return true;
1268 : : }
1269 : : return false;
1270 : : }
1271 : :
1272 : : bool
1273 : 23780703 : frange::singleton_p (tree *result) const
1274 : : {
1275 : 23780703 : if (internal_singleton_p ())
1276 : : {
1277 : 111268 : if (result)
1278 : 8670 : *result = build_real (m_type, m_min);
1279 : 111268 : return true;
1280 : : }
1281 : : return false;
1282 : : }
1283 : :
1284 : : bool
1285 : 0 : frange::singleton_p (REAL_VALUE_TYPE &r) const
1286 : : {
1287 : 0 : return internal_singleton_p (&r);
1288 : : }
1289 : :
1290 : : bool
1291 : 58684396 : frange::supports_type_p (const_tree type) const
1292 : : {
1293 : 58684396 : return supports_p (type);
1294 : : }
1295 : :
1296 : : void
1297 : 212948906 : frange::verify_range () const
1298 : : {
1299 : 212948906 : if (!undefined_p ())
1300 : 84222398 : gcc_checking_assert (HONOR_NANS (m_type) || !maybe_isnan ());
1301 : 212948906 : switch (m_kind)
1302 : : {
1303 : 133976677 : case VR_UNDEFINED:
1304 : 133976677 : gcc_checking_assert (!m_type);
1305 : : return;
1306 : 43093705 : case VR_VARYING:
1307 : 43093705 : gcc_checking_assert (m_type);
1308 : 43093705 : gcc_checking_assert (frange_val_is_min (m_min, m_type));
1309 : 43093705 : gcc_checking_assert (frange_val_is_max (m_max, m_type));
1310 : 43093705 : if (HONOR_NANS (m_type))
1311 : 38580452 : gcc_checking_assert (m_pos_nan && m_neg_nan);
1312 : : else
1313 : 4513253 : gcc_checking_assert (!m_pos_nan && !m_neg_nan);
1314 : : return;
1315 : 35388325 : case VR_RANGE:
1316 : 35388325 : gcc_checking_assert (m_type);
1317 : 35388325 : break;
1318 : 490199 : case VR_NAN:
1319 : 490199 : gcc_checking_assert (m_type);
1320 : 490199 : gcc_checking_assert (m_pos_nan || m_neg_nan);
1321 : : return;
1322 : 0 : default:
1323 : 0 : gcc_unreachable ();
1324 : : }
1325 : :
1326 : : // NANs cannot appear in the endpoints of a range.
1327 : 35388325 : gcc_checking_assert (!real_isnan (&m_min) && !real_isnan (&m_max));
1328 : :
1329 : : // Make sure we don't have swapped ranges.
1330 : 35388325 : gcc_checking_assert (!real_less (&m_max, &m_min));
1331 : :
1332 : : // [ +0.0, -0.0 ] is nonsensical.
1333 : 35388325 : gcc_checking_assert (!(real_iszero (&m_min, 0) && real_iszero (&m_max, 1)));
1334 : :
1335 : : // If all the properties are clear, we better not span the entire
1336 : : // domain, because that would make us varying.
1337 : 35388325 : if (m_pos_nan && m_neg_nan)
1338 : 12931983 : gcc_checking_assert (!frange_val_is_min (m_min, m_type)
1339 : : || !frange_val_is_max (m_max, m_type));
1340 : : }
1341 : :
1342 : : // We can't do much with nonzeros yet.
1343 : : void
1344 : 0 : frange::set_nonzero (tree type)
1345 : : {
1346 : 0 : set_varying (type);
1347 : 0 : }
1348 : :
1349 : : // We can't do much with nonzeros yet.
1350 : : bool
1351 : 0 : frange::nonzero_p () const
1352 : : {
1353 : 0 : return false;
1354 : : }
1355 : :
1356 : : // Set range to [+0.0, +0.0] if honoring signed zeros, or [0.0, 0.0]
1357 : : // otherwise.
1358 : :
1359 : : void
1360 : 160037 : frange::set_zero (tree type)
1361 : : {
1362 : 160037 : if (HONOR_SIGNED_ZEROS (type))
1363 : : {
1364 : 160037 : set (type, dconstm0, dconst0);
1365 : 160037 : clear_nan ();
1366 : : }
1367 : : else
1368 : 0 : set (type, dconst0, dconst0);
1369 : 160037 : }
1370 : :
1371 : : // Return TRUE for any zero regardless of sign.
1372 : :
1373 : : bool
1374 : 9485 : frange::zero_p () const
1375 : : {
1376 : 9485 : return (m_kind == VR_RANGE
1377 : 8444 : && real_iszero (&m_min)
1378 : 11645 : && real_iszero (&m_max));
1379 : : }
1380 : :
1381 : : // Set the range to non-negative numbers, that is [+0.0, +INF].
1382 : : //
1383 : : // The NAN in the resulting range (if HONOR_NANS) has a varying sign
1384 : : // as there are no guarantees in IEEE 754 wrt to the sign of a NAN,
1385 : : // except for copy, abs, and copysign. It is the responsibility of
1386 : : // the caller to set the NAN's sign if desired.
1387 : :
1388 : : void
1389 : 33354 : frange::set_nonnegative (tree type)
1390 : : {
1391 : 33354 : set (type, dconst0, frange_val_max (type));
1392 : 33354 : }
1393 : :
1394 : : tree
1395 : 0 : frange::lbound () const
1396 : : {
1397 : 0 : return build_real (type (), lower_bound ());
1398 : : }
1399 : :
1400 : : tree
1401 : 0 : frange::ubound () const
1402 : : {
1403 : 0 : return build_real (type (), upper_bound ());
1404 : : }
1405 : :
1406 : : // Here we copy between any two irange's.
1407 : :
1408 : : irange &
1409 : 1051978247 : irange::operator= (const irange &src)
1410 : : {
1411 : 1051978247 : int needed = src.num_pairs ();
1412 : 1051978247 : maybe_resize (needed);
1413 : :
1414 : 1051978247 : unsigned x;
1415 : 1051978247 : unsigned lim = src.m_num_ranges;
1416 : 1051978247 : if (lim > m_max_ranges)
1417 : 17238 : lim = m_max_ranges;
1418 : :
1419 : 3350041013 : for (x = 0; x < lim * 2; ++x)
1420 : 2298062766 : m_base[x] = src.m_base[x];
1421 : :
1422 : : // If the range didn't fit, the last range should cover the rest.
1423 : 1051978247 : if (lim != src.m_num_ranges)
1424 : 17238 : m_base[x - 1] = src.m_base[src.m_num_ranges * 2 - 1];
1425 : :
1426 : 1051978247 : m_num_ranges = lim;
1427 : 1051978247 : m_type = src.m_type;
1428 : 1051978247 : m_kind = src.m_kind;
1429 : 1051978247 : m_bitmask = src.m_bitmask;
1430 : 1051978247 : if (m_max_ranges == 1)
1431 : 21533737 : normalize_kind ();
1432 : 1051978247 : if (flag_checking)
1433 : 1051972062 : verify_range ();
1434 : 1051978247 : return *this;
1435 : : }
1436 : :
1437 : : static value_range_kind
1438 : 19770373 : get_legacy_range (const irange &r, tree &min, tree &max)
1439 : : {
1440 : 19770373 : if (r.undefined_p ())
1441 : : {
1442 : 103987 : min = NULL_TREE;
1443 : 103987 : max = NULL_TREE;
1444 : 103987 : return VR_UNDEFINED;
1445 : : }
1446 : :
1447 : 19666386 : tree type = r.type ();
1448 : 19666386 : if (r.varying_p ())
1449 : : {
1450 : 8385693 : min = wide_int_to_tree (type, r.lower_bound ());
1451 : 8385693 : max = wide_int_to_tree (type, r.upper_bound ());
1452 : 8385693 : return VR_VARYING;
1453 : : }
1454 : :
1455 : 11280693 : unsigned int precision = TYPE_PRECISION (type);
1456 : 11280693 : signop sign = TYPE_SIGN (type);
1457 : 22561386 : if (r.num_pairs () > 1
1458 : 2966695 : && precision > 1
1459 : 17214083 : && r.lower_bound () == wi::min_value (precision, sign)
1460 : 16138967 : && r.upper_bound () == wi::max_value (precision, sign))
1461 : : {
1462 : 502214 : int_range<3> inv (r);
1463 : 502214 : inv.invert ();
1464 : 502214 : min = wide_int_to_tree (type, inv.lower_bound (0));
1465 : 502214 : max = wide_int_to_tree (type, inv.upper_bound (0));
1466 : 502214 : return VR_ANTI_RANGE;
1467 : 502214 : }
1468 : :
1469 : 10778479 : min = wide_int_to_tree (type, r.lower_bound ());
1470 : 10778479 : max = wide_int_to_tree (type, r.upper_bound ());
1471 : 10778479 : return VR_RANGE;
1472 : : }
1473 : :
1474 : : static value_range_kind
1475 : 3013906 : get_legacy_range (const prange &r, tree &min, tree &max)
1476 : : {
1477 : 3013906 : if (r.undefined_p ())
1478 : : {
1479 : 0 : min = NULL_TREE;
1480 : 0 : max = NULL_TREE;
1481 : 0 : return VR_UNDEFINED;
1482 : : }
1483 : :
1484 : 3013906 : tree type = r.type ();
1485 : 3013906 : if (r.varying_p ())
1486 : : {
1487 : 0 : min = r.lbound ();
1488 : 0 : max = r.ubound ();
1489 : 0 : return VR_VARYING;
1490 : : }
1491 : 3013906 : if (r.zero_p ())
1492 : : {
1493 : 2267403 : min = max = r.lbound ();
1494 : 2267403 : return VR_RANGE;
1495 : : }
1496 : 746503 : if (r.nonzero_p ())
1497 : : {
1498 : 0 : min = max = build_zero_cst (type);
1499 : 0 : return VR_ANTI_RANGE;
1500 : : }
1501 : 746503 : min = r.lbound ();
1502 : 746503 : max = r.ubound ();
1503 : 746503 : return VR_RANGE;
1504 : : }
1505 : :
1506 : : // Given a range in V, return an old-style legacy range consisting of
1507 : : // a value_range_kind with a MIN/MAX. This is to maintain
1508 : : // compatibility with passes that still depend on VR_ANTI_RANGE, and
1509 : : // only works for integers and pointers.
1510 : :
1511 : : value_range_kind
1512 : 22784279 : get_legacy_range (const vrange &v, tree &min, tree &max)
1513 : : {
1514 : 22784279 : if (is_a <irange> (v))
1515 : 19770373 : return get_legacy_range (as_a <irange> (v), min, max);
1516 : :
1517 : 3013906 : return get_legacy_range (as_a <prange> (v), min, max);
1518 : : }
1519 : :
1520 : : /* Set value range to the canonical form of {VRTYPE, MIN, MAX, EQUIV}.
1521 : : This means adjusting VRTYPE, MIN and MAX representing the case of a
1522 : : wrapping range with MAX < MIN covering [MIN, type_max] U [type_min, MAX]
1523 : : as anti-rage ~[MAX+1, MIN-1]. Likewise for wrapping anti-ranges.
1524 : : In corner cases where MAX+1 or MIN-1 wraps this will fall back
1525 : : to varying.
1526 : : This routine exists to ease canonicalization in the case where we
1527 : : extract ranges from var + CST op limit. */
1528 : :
1529 : : void
1530 : 1397533993 : irange::set (tree type, const wide_int &min, const wide_int &max,
1531 : : value_range_kind kind)
1532 : : {
1533 : 1397533993 : unsigned prec = TYPE_PRECISION (type);
1534 : 1397533993 : signop sign = TYPE_SIGN (type);
1535 : 1397533993 : wide_int min_value = wi::min_value (prec, sign);
1536 : 1397533993 : wide_int max_value = wi::max_value (prec, sign);
1537 : :
1538 : 1397533993 : m_type = type;
1539 : 1397533993 : m_bitmask.set_unknown (prec);
1540 : :
1541 : 1397533993 : if (kind == VR_RANGE)
1542 : : {
1543 : 1342780742 : m_base[0] = min;
1544 : 1342780742 : m_base[1] = max;
1545 : 1342780742 : m_num_ranges = 1;
1546 : 1821315829 : if (min == min_value && max == max_value)
1547 : 71295110 : m_kind = VR_VARYING;
1548 : : else
1549 : 1271485632 : m_kind = VR_RANGE;
1550 : : }
1551 : : else
1552 : : {
1553 : 54753251 : gcc_checking_assert (kind == VR_ANTI_RANGE);
1554 : 54753251 : gcc_checking_assert (m_max_ranges > 1);
1555 : :
1556 : 54753251 : m_kind = VR_UNDEFINED;
1557 : 54753251 : m_num_ranges = 0;
1558 : 54753251 : wi::overflow_type ovf;
1559 : 54753251 : wide_int lim;
1560 : 54753251 : if (sign == SIGNED)
1561 : 26202316 : lim = wi::add (min, -1, sign, &ovf);
1562 : : else
1563 : 28551352 : lim = wi::sub (min, 1, sign, &ovf);
1564 : :
1565 : 54753251 : if (!ovf)
1566 : : {
1567 : 39146791 : m_kind = VR_RANGE;
1568 : 39146791 : m_base[0] = min_value;
1569 : 39146791 : m_base[1] = lim;
1570 : 39146791 : ++m_num_ranges;
1571 : : }
1572 : 54753251 : if (sign == SIGNED)
1573 : 26202316 : lim = wi::sub (max, -1, sign, &ovf);
1574 : : else
1575 : 28551352 : lim = wi::add (max, 1, sign, &ovf);
1576 : 54753251 : if (!ovf)
1577 : : {
1578 : 54752401 : m_kind = VR_RANGE;
1579 : 54752401 : m_base[m_num_ranges * 2] = lim;
1580 : 54752401 : m_base[m_num_ranges * 2 + 1] = max_value;
1581 : 54752401 : ++m_num_ranges;
1582 : : }
1583 : 54753251 : }
1584 : :
1585 : 1397533993 : if (flag_checking)
1586 : 1397528749 : verify_range ();
1587 : 1397533993 : }
1588 : :
1589 : : void
1590 : 220868400 : irange::set (tree min, tree max, value_range_kind kind)
1591 : : {
1592 : 220868400 : if (POLY_INT_CST_P (min) || POLY_INT_CST_P (max))
1593 : : {
1594 : : set_varying (TREE_TYPE (min));
1595 : : return;
1596 : : }
1597 : :
1598 : 220868400 : gcc_checking_assert (TREE_CODE (min) == INTEGER_CST);
1599 : 220868400 : gcc_checking_assert (TREE_CODE (max) == INTEGER_CST);
1600 : :
1601 : 220869012 : return set (TREE_TYPE (min), wi::to_wide (min), wi::to_wide (max), kind);
1602 : : }
1603 : :
1604 : : // Check the validity of the range.
1605 : :
1606 : : void
1607 : 4568209409 : irange::verify_range () const
1608 : : {
1609 : 4568209409 : gcc_checking_assert (m_discriminator == VR_IRANGE);
1610 : 4568209409 : if (m_kind == VR_UNDEFINED)
1611 : : {
1612 : 167112 : gcc_checking_assert (m_num_ranges == 0);
1613 : : return;
1614 : : }
1615 : 4568042297 : gcc_checking_assert (supports_p (type ()));
1616 : 4568042297 : gcc_checking_assert (m_num_ranges <= m_max_ranges);
1617 : :
1618 : : // Legacy allowed these to represent VARYING for unknown types.
1619 : : // Leave this in for now, until all users are converted. Eventually
1620 : : // we should abort in set_varying.
1621 : 4568042297 : if (m_kind == VR_VARYING && m_type == error_mark_node)
1622 : : return;
1623 : :
1624 : 4568042297 : unsigned prec = TYPE_PRECISION (m_type);
1625 : 4568042297 : if (m_kind == VR_VARYING)
1626 : : {
1627 : 279652104 : gcc_checking_assert (m_bitmask.unknown_p ());
1628 : 279652104 : gcc_checking_assert (m_num_ranges == 1);
1629 : 279652104 : gcc_checking_assert (varying_compatible_p ());
1630 : 279652104 : gcc_checking_assert (lower_bound ().get_precision () == prec);
1631 : 279652104 : gcc_checking_assert (upper_bound ().get_precision () == prec);
1632 : 279652104 : return;
1633 : : }
1634 : 4288390193 : gcc_checking_assert (m_num_ranges != 0);
1635 : 4288390193 : gcc_checking_assert (!varying_compatible_p ());
1636 : 10795115276 : for (unsigned i = 0; i < m_num_ranges; ++i)
1637 : : {
1638 : 6506725083 : wide_int lb = lower_bound (i);
1639 : 6506725083 : wide_int ub = upper_bound (i);
1640 : 6506725083 : gcc_checking_assert (lb.get_precision () == prec);
1641 : 6506725083 : gcc_checking_assert (ub.get_precision () == prec);
1642 : 6506725083 : int c = wi::cmp (lb, ub, TYPE_SIGN (m_type));
1643 : 6506725083 : gcc_checking_assert (c == 0 || c == -1);
1644 : : // Previous UB should be lower than LB
1645 : 6506725083 : if (i > 0)
1646 : 4436669780 : gcc_checking_assert (wi::lt_p (upper_bound (i - 1),
1647 : : lb,
1648 : : TYPE_SIGN (m_type)));
1649 : 6506745589 : }
1650 : 4288390193 : m_bitmask.verify_mask ();
1651 : : }
1652 : :
1653 : : bool
1654 : 159749719 : irange::operator== (const irange &other) const
1655 : : {
1656 : 159749719 : if (m_num_ranges != other.m_num_ranges)
1657 : : return false;
1658 : :
1659 : 152045970 : if (m_num_ranges == 0)
1660 : : return true;
1661 : :
1662 : 151900027 : signop sign1 = TYPE_SIGN (type ());
1663 : 151900027 : signop sign2 = TYPE_SIGN (other.type ());
1664 : :
1665 : 192936633 : for (unsigned i = 0; i < m_num_ranges; ++i)
1666 : : {
1667 : 157673995 : widest_int lb = widest_int::from (lower_bound (i), sign1);
1668 : 157673995 : widest_int ub = widest_int::from (upper_bound (i), sign1);
1669 : 157673995 : widest_int lb_other = widest_int::from (other.lower_bound (i), sign2);
1670 : 157673995 : widest_int ub_other = widest_int::from (other.upper_bound (i), sign2);
1671 : 253288167 : if (lb != lb_other || ub != ub_other)
1672 : 116637389 : return false;
1673 : 157674377 : }
1674 : :
1675 : 35262638 : irange_bitmask bm1 = get_bitmask ();
1676 : 35262638 : irange_bitmask bm2 = other.get_bitmask ();
1677 : 35262638 : widest_int tmp1 = widest_int::from (bm1.mask (), sign1);
1678 : 35262638 : widest_int tmp2 = widest_int::from (bm2.mask (), sign2);
1679 : 35262638 : if (tmp1 != tmp2)
1680 : : return false;
1681 : 35259027 : if (bm1.unknown_p ())
1682 : : return true;
1683 : 24054105 : tmp1 = widest_int::from (bm1.value (), sign1);
1684 : 24054105 : tmp2 = widest_int::from (bm2.value (), sign2);
1685 : 24054093 : return tmp1 == tmp2;
1686 : 35262676 : }
1687 : :
1688 : : /* If range is a singleton, place it in RESULT and return TRUE. */
1689 : :
1690 : : bool
1691 : 637304277 : irange::singleton_p (tree *result) const
1692 : : {
1693 : 1193227802 : if (num_pairs () == 1 && lower_bound () == upper_bound ())
1694 : : {
1695 : 38352919 : if (result)
1696 : 6784328 : *result = wide_int_to_tree (type (), lower_bound ());
1697 : 38352919 : return true;
1698 : : }
1699 : : return false;
1700 : : }
1701 : :
1702 : : bool
1703 : 489971474 : irange::singleton_p (wide_int &w) const
1704 : : {
1705 : 660293841 : if (num_pairs () == 1 && lower_bound () == upper_bound ())
1706 : : {
1707 : 19284094 : w = lower_bound ();
1708 : 19284094 : return true;
1709 : : }
1710 : : return false;
1711 : : }
1712 : :
1713 : : /* Return 1 if CST is inside value range.
1714 : : 0 if CST is not inside value range.
1715 : :
1716 : : Benchmark compile/20001226-1.c compilation time after changing this
1717 : : function. */
1718 : :
1719 : : bool
1720 : 215498980 : irange::contains_p (const wide_int &cst) const
1721 : : {
1722 : 215498980 : if (undefined_p ())
1723 : : return false;
1724 : :
1725 : : // Check if the known bits in bitmask exclude CST.
1726 : 215424834 : if (!m_bitmask.member_p (cst))
1727 : : return false;
1728 : :
1729 : 214890646 : signop sign = TYPE_SIGN (type ());
1730 : 230987890 : for (unsigned r = 0; r < m_num_ranges; ++r)
1731 : : {
1732 : 230726290 : if (wi::lt_p (cst, lower_bound (r), sign))
1733 : : return false;
1734 : 127491067 : if (wi::le_p (cst, upper_bound (r), sign))
1735 : : return true;
1736 : : }
1737 : :
1738 : : return false;
1739 : : }
1740 : :
1741 : : // Perform an efficient union with R when both ranges have only a single pair.
1742 : : // Excluded are VARYING and UNDEFINED ranges.
1743 : :
1744 : : bool
1745 : 114874816 : irange::irange_single_pair_union (const irange &r)
1746 : : {
1747 : 114874816 : gcc_checking_assert (!undefined_p () && !varying_p ());
1748 : 114874816 : gcc_checking_assert (!r.undefined_p () && !varying_p ());
1749 : :
1750 : 114874816 : signop sign = TYPE_SIGN (m_type);
1751 : : // Check if current lower bound is also the new lower bound.
1752 : 114874816 : if (wi::le_p (m_base[0], r.m_base[0], sign))
1753 : : {
1754 : : // If current upper bound is new upper bound, we're done.
1755 : 100785508 : if (wi::le_p (r.m_base[1], m_base[1], sign))
1756 : 14823093 : return union_bitmask (r);
1757 : : // Otherwise R has the new upper bound.
1758 : : // Check for overlap/touching ranges, or single target range.
1759 : 171924830 : if (m_max_ranges == 1
1760 : 343849648 : || (widest_int::from (m_base[1], sign) + 1
1761 : 343849648 : >= widest_int::from (r.m_base[0], TYPE_SIGN (r.m_type))))
1762 : 26628012 : m_base[1] = r.m_base[1];
1763 : : else
1764 : : {
1765 : : // This is a dual range result.
1766 : 59334403 : m_base[2] = r.m_base[0];
1767 : 59334403 : m_base[3] = r.m_base[1];
1768 : 59334403 : m_num_ranges = 2;
1769 : : }
1770 : : // The range has been altered, so normalize it even if nothing
1771 : : // changed in the mask.
1772 : 85962415 : if (!union_bitmask (r))
1773 : 85101746 : normalize_kind ();
1774 : 85962415 : if (flag_checking)
1775 : 85962282 : verify_range ();
1776 : 85962415 : return true;
1777 : : }
1778 : :
1779 : : // Set the new lower bound to R's lower bound.
1780 : 14089308 : wide_int lb = m_base[0];
1781 : 14089308 : m_base[0] = r.m_base[0];
1782 : :
1783 : : // If R fully contains THIS range, just set the upper bound.
1784 : 14089308 : if (wi::ge_p (r.m_base[1], m_base[1], sign))
1785 : 1363614 : m_base[1] = r.m_base[1];
1786 : : // Check for overlapping ranges, or target limited to a single range.
1787 : 25451388 : else if (m_max_ranges == 1
1788 : 50902776 : || (widest_int::from (r.m_base[1], TYPE_SIGN (r.m_type)) + 1
1789 : 50902776 : >= widest_int::from (lb, sign)))
1790 : : ;
1791 : : else
1792 : : {
1793 : : // Left with 2 pairs.
1794 : 5976548 : m_num_ranges = 2;
1795 : 5976548 : m_base[2] = lb;
1796 : 5976548 : m_base[3] = m_base[1];
1797 : 5976548 : m_base[1] = r.m_base[1];
1798 : : }
1799 : : // The range has been altered, so normalize it even if nothing
1800 : : // changed in the mask.
1801 : 14089308 : if (!union_bitmask (r))
1802 : 13063793 : normalize_kind ();
1803 : 14089308 : if (flag_checking)
1804 : 14089297 : verify_range ();
1805 : 14089308 : return true;
1806 : 14089308 : }
1807 : :
1808 : : // Append R to this range, knowing that R occurs after all of these subranges.
1809 : : // Return TRUE as something must have changed.
1810 : :
1811 : : bool
1812 : 142411247 : irange::union_append (const irange &r)
1813 : : {
1814 : : // Check if the first range in R is an immmediate successor to the last
1815 : : // range, ths requiring a merge.
1816 : 142411247 : signop sign = TYPE_SIGN (m_type);
1817 : 142411247 : wide_int lb = r.lower_bound ();
1818 : 142411247 : wide_int ub = upper_bound ();
1819 : 142411247 : unsigned start = 0;
1820 : 427233741 : if (widest_int::from (ub, sign) + 1
1821 : 427233741 : == widest_int::from (lb, sign))
1822 : : {
1823 : 968420 : m_base[m_num_ranges * 2 - 1] = r.m_base[1];
1824 : 968420 : start = 1;
1825 : : }
1826 : 142411247 : maybe_resize (m_num_ranges + r.m_num_ranges - start);
1827 : 426334064 : for ( ; start < r.m_num_ranges; start++)
1828 : : {
1829 : : // Merge the last ranges if it exceeds the maximum size.
1830 : 142359412 : if (m_num_ranges + 1 > m_max_ranges)
1831 : : {
1832 : 847842 : m_base[m_max_ranges * 2 - 1] = r.m_base[r.m_num_ranges * 2 - 1];
1833 : 847842 : break;
1834 : : }
1835 : 141511570 : m_base[m_num_ranges * 2] = r.m_base[start * 2];
1836 : 141511570 : m_base[m_num_ranges * 2 + 1] = r.m_base[start * 2 + 1];
1837 : 141511570 : m_num_ranges++;
1838 : : }
1839 : :
1840 : 142411247 : if (!union_bitmask (r))
1841 : 142374112 : normalize_kind ();
1842 : 142411247 : if (flag_checking)
1843 : 142411247 : verify_range ();
1844 : 142411247 : return true;
1845 : 142411247 : }
1846 : :
1847 : : // Return TRUE if anything changes.
1848 : :
1849 : : bool
1850 : 398494082 : irange::union_ (const vrange &v)
1851 : : {
1852 : 398494082 : const irange &r = as_a <irange> (v);
1853 : :
1854 : 398494082 : if (r.undefined_p ())
1855 : : return false;
1856 : :
1857 : 396316695 : if (undefined_p ())
1858 : : {
1859 : 95060547 : operator= (r);
1860 : 95060547 : if (flag_checking)
1861 : 95059969 : verify_range ();
1862 : 95060547 : return true;
1863 : : }
1864 : :
1865 : 301256148 : if (varying_p ())
1866 : : return false;
1867 : :
1868 : 290786231 : if (r.varying_p ())
1869 : : {
1870 : 7020820 : set_varying (type ());
1871 : 7020820 : return true;
1872 : : }
1873 : :
1874 : : // Special case one range union one range.
1875 : 283765411 : if (m_num_ranges == 1 && r.m_num_ranges == 1)
1876 : 114874816 : return irange_single_pair_union (r);
1877 : :
1878 : 168890595 : signop sign = TYPE_SIGN (m_type);
1879 : : // Check for an append to the end.
1880 : 506671785 : if (m_kind == VR_RANGE && wi::gt_p (r.lower_bound (), upper_bound (), sign))
1881 : 142411247 : return union_append (r);
1882 : :
1883 : : // If this ranges fully contains R, then we need do nothing.
1884 : 26479348 : if (irange_contains_p (r))
1885 : 4217704 : return union_bitmask (r);
1886 : :
1887 : : // Do not worry about merging and such by reserving twice as many
1888 : : // pairs as needed, and then simply sort the 2 ranges into this
1889 : : // intermediate form.
1890 : : //
1891 : : // The intermediate result will have the property that the beginning
1892 : : // of each range is <= the beginning of the next range. There may
1893 : : // be overlapping ranges at this point. I.e. this would be valid
1894 : : // [-20, 10], [-10, 0], [0, 20], [40, 90] as it satisfies this
1895 : : // constraint : -20 < -10 < 0 < 40. When the range is rebuilt into r,
1896 : : // the merge is performed.
1897 : : //
1898 : : // [Xi,Yi]..[Xn,Yn] U [Xj,Yj]..[Xm,Ym] --> [Xk,Yk]..[Xp,Yp]
1899 : 22261644 : auto_vec<wide_int, 20> res (m_num_ranges * 2 + r.m_num_ranges * 2);
1900 : 22261644 : unsigned i = 0, j = 0, k = 0;
1901 : :
1902 : 98204959 : while (i < m_num_ranges * 2 && j < r.m_num_ranges * 2)
1903 : : {
1904 : : // lower of Xi and Xj is the lowest point.
1905 : 107363342 : if (widest_int::from (m_base[i], sign)
1906 : 161045013 : <= widest_int::from (r.m_base[j], sign))
1907 : : {
1908 : 28215161 : res.quick_push (m_base[i]);
1909 : 28215161 : res.quick_push (m_base[i + 1]);
1910 : 28215161 : k += 2;
1911 : 28215161 : i += 2;
1912 : : }
1913 : : else
1914 : : {
1915 : 25466510 : res.quick_push (r.m_base[j]);
1916 : 25466510 : res.quick_push (r.m_base[j + 1]);
1917 : 25466510 : k += 2;
1918 : 25466510 : j += 2;
1919 : : }
1920 : : }
1921 : 44994985 : for ( ; i < m_num_ranges * 2; i += 2)
1922 : : {
1923 : 22733341 : res.quick_push (m_base[i]);
1924 : 22733341 : res.quick_push (m_base[i + 1]);
1925 : 22733341 : k += 2;
1926 : : }
1927 : 28639541 : for ( ; j < r.m_num_ranges * 2; j += 2)
1928 : : {
1929 : 6377897 : res.quick_push (r.m_base[j]);
1930 : 6377897 : res.quick_push (r.m_base[j + 1]);
1931 : 6377897 : k += 2;
1932 : : }
1933 : :
1934 : : // Now normalize the vector removing any overlaps.
1935 : : i = 2;
1936 : 82792909 : for (j = 2; j < k ; j += 2)
1937 : : {
1938 : : // Current upper+1 is >= lower bound next pair, then we merge ranges.
1939 : 181593808 : if (widest_int::from (res[i - 1], sign) + 1
1940 : 181593795 : >= widest_int::from (res[j], sign))
1941 : : {
1942 : : // New upper bounds is greater of current or the next one.
1943 : 52165490 : if (widest_int::from (res[j + 1], sign)
1944 : 78248235 : > widest_int::from (res[i - 1], sign))
1945 : 19852860 : res[i - 1] = res[j + 1];
1946 : : }
1947 : : else
1948 : : {
1949 : : // This is a new distinct range, but no point in copying it
1950 : : // if it is already in the right place.
1951 : 34448520 : if (i != j)
1952 : : {
1953 : 11295238 : res[i++] = res[j];
1954 : 11295238 : res[i++] = res[j + 1];
1955 : : }
1956 : : else
1957 : 23153282 : i += 2;
1958 : : }
1959 : : }
1960 : :
1961 : : // At this point, the vector should have i ranges, none overlapping.
1962 : : // Now it simply needs to be copied, and if there are too many
1963 : : // ranges, merge some. We wont do any analysis as to what the
1964 : : // "best" merges are, simply combine the final ranges into one.
1965 : 22261644 : maybe_resize (i / 2);
1966 : 22261644 : if (i > m_max_ranges * 2)
1967 : : {
1968 : 1433 : res[m_max_ranges * 2 - 1] = res[i - 1];
1969 : 1433 : i = m_max_ranges * 2;
1970 : : }
1971 : :
1972 : 135679106 : for (j = 0; j < i ; j++)
1973 : 113417462 : m_base[j] = res [j];
1974 : 22261644 : m_num_ranges = i / 2;
1975 : :
1976 : 22261644 : m_kind = VR_RANGE;
1977 : : // The range has been altered, so normalize it even if nothing
1978 : : // changed in the mask.
1979 : 22261644 : if (!union_bitmask (r))
1980 : 21292639 : normalize_kind ();
1981 : 22261644 : if (flag_checking)
1982 : 22261597 : verify_range ();
1983 : 22261644 : return true;
1984 : 22261644 : }
1985 : :
1986 : : // Return TRUE if THIS fully contains R. No undefined or varying cases.
1987 : :
1988 : : bool
1989 : 179515665 : irange::irange_contains_p (const irange &r) const
1990 : : {
1991 : 179515665 : gcc_checking_assert (!undefined_p () && !varying_p ());
1992 : 179515665 : gcc_checking_assert (!r.undefined_p () && !varying_p ());
1993 : :
1994 : : // Check singletons directly which will include any bitmasks.
1995 : 179515665 : wide_int rl;
1996 : 179515665 : if (r.singleton_p (rl))
1997 : 14385674 : return contains_p (rl);
1998 : :
1999 : : // In order for THIS to fully contain R, all of the pairs within R must
2000 : : // be fully contained by the pairs in this object.
2001 : 165129991 : signop sign = TYPE_SIGN (m_type);
2002 : 165129991 : unsigned ri = 0;
2003 : 165129991 : unsigned i = 0;
2004 : 165129991 : rl = r.m_base[0];
2005 : 165129991 : wide_int ru = r.m_base[1];
2006 : 165129991 : wide_int l = m_base[0];
2007 : 165129991 : wide_int u = m_base[1];
2008 : 433642540 : while (1)
2009 : : {
2010 : : // If r is contained within this range, move to the next R
2011 : 433642540 : if (wi::ge_p (rl, l, sign)
2012 : 433642540 : && wi::le_p (ru, u, sign))
2013 : : {
2014 : : // This pair is OK, Either done, or bump to the next.
2015 : 203291094 : if (++ri >= r.num_pairs ())
2016 : : return true;
2017 : 133773400 : rl = r.m_base[ri * 2];
2018 : 133773400 : ru = r.m_base[ri * 2 + 1];
2019 : 133773400 : continue;
2020 : : }
2021 : : // Otherwise, check if this's pair occurs before R's.
2022 : 230351446 : if (wi::lt_p (u, rl, sign))
2023 : : {
2024 : : // There's still at least one pair of R left.
2025 : 135449461 : if (++i >= num_pairs ())
2026 : : return false;
2027 : 134739149 : l = m_base[i * 2];
2028 : 134739149 : u = m_base[i * 2 + 1];
2029 : 134739149 : continue;
2030 : : }
2031 : : return false;
2032 : : }
2033 : : return false;
2034 : 165132253 : }
2035 : :
2036 : :
2037 : : // Return TRUE if anything changes.
2038 : :
2039 : : bool
2040 : 897318596 : irange::intersect (const vrange &v)
2041 : : {
2042 : 897318596 : const irange &r = as_a <irange> (v);
2043 : 897318596 : gcc_checking_assert (undefined_p () || r.undefined_p ()
2044 : : || range_compatible_p (type (), r.type ()));
2045 : :
2046 : 897318596 : if (undefined_p ())
2047 : : return false;
2048 : 896288912 : if (r.undefined_p ())
2049 : : {
2050 : 429650 : set_undefined ();
2051 : 429650 : return true;
2052 : : }
2053 : 895859262 : if (r.varying_p ())
2054 : : return false;
2055 : 595288760 : if (varying_p ())
2056 : : {
2057 : 83429918 : operator= (r);
2058 : 83429918 : return true;
2059 : : }
2060 : :
2061 : 511858842 : if (r.num_pairs () == 1)
2062 : : {
2063 : 358813977 : bool res = intersect (r.lower_bound (), r.upper_bound ());
2064 : 358812396 : if (undefined_p ())
2065 : : return true;
2066 : :
2067 : 332098163 : res |= intersect_bitmask (r);
2068 : 332098163 : if (res)
2069 : 113638548 : normalize_kind ();
2070 : 332098163 : return res;
2071 : : }
2072 : :
2073 : : // If either range is a singleton and the other range does not contain
2074 : : // it, the result is undefined.
2075 : 153046446 : wide_int val;
2076 : 154205851 : if ((singleton_p (val) && !r.contains_p (val))
2077 : 154195722 : || (r.singleton_p (val) && !contains_p (val)))
2078 : : {
2079 : 10129 : set_undefined ();
2080 : 10129 : return true;
2081 : : }
2082 : :
2083 : : // If R fully contains this, then intersection will change nothing.
2084 : 153036317 : if (r.irange_contains_p (*this))
2085 : 68118483 : return intersect_bitmask (r);
2086 : :
2087 : : // ?? We could probably come up with something smarter than the
2088 : : // worst case scenario here.
2089 : 84917834 : int needed = num_pairs () + r.num_pairs ();
2090 : 84917834 : maybe_resize (needed);
2091 : :
2092 : 84917834 : signop sign = TYPE_SIGN (m_type);
2093 : 84917834 : unsigned bld_pair = 0;
2094 : 84917834 : unsigned bld_lim = m_max_ranges;
2095 : 84917834 : int_range_max r2 (*this);
2096 : 84917834 : unsigned r2_lim = r2.num_pairs ();
2097 : 84917834 : unsigned i2 = 0;
2098 : 251155864 : for (unsigned i = 0; i < r.num_pairs (); )
2099 : : {
2100 : : // If r1's upper is < r2's lower, we can skip r1's pair.
2101 : 222745993 : wide_int ru = r.m_base[i * 2 + 1];
2102 : 222745993 : wide_int r2l = r2.m_base[i2 * 2];
2103 : 222745993 : if (wi::lt_p (ru, r2l, sign))
2104 : : {
2105 : 20630372 : i++;
2106 : 20630372 : continue;
2107 : : }
2108 : : // Likewise, skip r2's pair if its excluded.
2109 : 202115621 : wide_int r2u = r2.m_base[i2 * 2 + 1];
2110 : 202115621 : wide_int rl = r.m_base[i * 2];
2111 : 202115621 : if (wi::lt_p (r2u, rl, sign))
2112 : : {
2113 : 21579315 : i2++;
2114 : 21579315 : if (i2 < r2_lim)
2115 : 17235029 : continue;
2116 : : // No more r2, break.
2117 : : break;
2118 : : }
2119 : :
2120 : : // Must be some overlap. Find the highest of the lower bounds,
2121 : : // and set it, unless the build limits lower bounds is already
2122 : : // set.
2123 : 180536306 : if (bld_pair < bld_lim)
2124 : : {
2125 : 180237631 : if (wi::ge_p (rl, r2l, sign))
2126 : 152811738 : m_base[bld_pair * 2] = rl;
2127 : : else
2128 : 27425893 : m_base[bld_pair * 2] = r2l;
2129 : : }
2130 : : else
2131 : : // Decrease and set a new upper.
2132 : 298675 : bld_pair--;
2133 : :
2134 : : // ...and choose the lower of the upper bounds.
2135 : 180536306 : if (wi::le_p (ru, r2u, sign))
2136 : : {
2137 : 116101046 : m_base[bld_pair * 2 + 1] = ru;
2138 : 116101046 : bld_pair++;
2139 : : // Move past the r1 pair and keep trying.
2140 : 116101046 : i++;
2141 : 116101046 : continue;
2142 : : }
2143 : : else
2144 : : {
2145 : 64435260 : m_base[bld_pair * 2 + 1] = r2u;
2146 : 64435260 : bld_pair++;
2147 : 64435260 : i2++;
2148 : 64435260 : if (i2 < r2_lim)
2149 : 12271583 : continue;
2150 : : // No more r2, break.
2151 : : break;
2152 : : }
2153 : : // r2 has the higher lower bound.
2154 : 368354937 : }
2155 : :
2156 : : // At the exit of this loop, it is one of 2 things:
2157 : : // ran out of r1, or r2, but either means we are done.
2158 : 84917834 : m_num_ranges = bld_pair;
2159 : 84917834 : if (m_num_ranges == 0)
2160 : : {
2161 : 104850 : set_undefined ();
2162 : 104850 : return true;
2163 : : }
2164 : :
2165 : 84812984 : m_kind = VR_RANGE;
2166 : : // The range has been altered, so normalize it even if nothing
2167 : : // changed in the mask.
2168 : 84812984 : if (!intersect_bitmask (r))
2169 : 77999203 : normalize_kind ();
2170 : 84812984 : if (flag_checking)
2171 : 84812917 : verify_range ();
2172 : : return true;
2173 : 237964280 : }
2174 : :
2175 : :
2176 : : // Multirange intersect for a specified wide_int [lb, ub] range.
2177 : : // Return TRUE if intersect changed anything.
2178 : : //
2179 : : // NOTE: It is the caller's responsibility to intersect the mask.
2180 : :
2181 : : bool
2182 : 358812396 : irange::intersect (const wide_int& lb, const wide_int& ub)
2183 : : {
2184 : : // Undefined remains undefined.
2185 : 358812396 : if (undefined_p ())
2186 : : return false;
2187 : :
2188 : 358812396 : tree range_type = type();
2189 : 358812396 : signop sign = TYPE_SIGN (range_type);
2190 : :
2191 : 358812396 : gcc_checking_assert (TYPE_PRECISION (range_type) == wi::get_precision (lb));
2192 : 358812396 : gcc_checking_assert (TYPE_PRECISION (range_type) == wi::get_precision (ub));
2193 : :
2194 : : // If this range is fully contained, then intersection will do nothing.
2195 : 717624792 : if (wi::ge_p (lower_bound (), lb, sign)
2196 : 646606430 : && wi::le_p (upper_bound (), ub, sign))
2197 : : return false;
2198 : :
2199 : 127358906 : unsigned bld_index = 0;
2200 : 127358906 : unsigned pair_lim = num_pairs ();
2201 : 191521164 : for (unsigned i = 0; i < pair_lim; i++)
2202 : : {
2203 : 141805897 : wide_int pairl = m_base[i * 2];
2204 : 141805897 : wide_int pairu = m_base[i * 2 + 1];
2205 : : // Once UB is less than a pairs lower bound, we're done.
2206 : 141805897 : if (wi::lt_p (ub, pairl, sign))
2207 : : break;
2208 : : // if LB is greater than this pairs upper, this pair is excluded.
2209 : 120290173 : if (wi::lt_p (pairu, lb, sign))
2210 : 17870469 : continue;
2211 : :
2212 : : // Must be some overlap. Find the highest of the lower bounds,
2213 : : // and set it
2214 : 102419704 : if (wi::gt_p (lb, pairl, sign))
2215 : 55382753 : m_base[bld_index * 2] = lb;
2216 : : else
2217 : 47036951 : m_base[bld_index * 2] = pairl;
2218 : :
2219 : : // ...and choose the lower of the upper bounds and if the base pair
2220 : : // has the lower upper bound, need to check next pair too.
2221 : 102419704 : if (wi::lt_p (ub, pairu, sign))
2222 : : {
2223 : 56127915 : m_base[bld_index++ * 2 + 1] = ub;
2224 : 56127915 : break;
2225 : : }
2226 : : else
2227 : 46291789 : m_base[bld_index++ * 2 + 1] = pairu;
2228 : 141806345 : }
2229 : :
2230 : 127358906 : m_num_ranges = bld_index;
2231 : 127358906 : if (m_num_ranges == 0)
2232 : : {
2233 : 26714233 : set_undefined ();
2234 : 26714233 : return true;
2235 : : }
2236 : :
2237 : 100644673 : m_kind = VR_RANGE;
2238 : : // The caller must normalize and verify the range, as the bitmask
2239 : : // still needs to be handled.
2240 : 100644673 : return true;
2241 : : }
2242 : :
2243 : :
2244 : : // Signed 1-bits are strange. You can't subtract 1, because you can't
2245 : : // represent the number 1. This works around that for the invert routine.
2246 : :
2247 : : static wide_int inline
2248 : 56920593 : subtract_one (const wide_int &x, tree type, wi::overflow_type &overflow)
2249 : : {
2250 : 56920593 : if (TYPE_SIGN (type) == SIGNED)
2251 : 34715108 : return wi::add (x, -1, SIGNED, &overflow);
2252 : : else
2253 : 22205485 : return wi::sub (x, 1, UNSIGNED, &overflow);
2254 : : }
2255 : :
2256 : : // The analogous function for adding 1.
2257 : :
2258 : : static wide_int inline
2259 : 59331662 : add_one (const wide_int &x, tree type, wi::overflow_type &overflow)
2260 : : {
2261 : 59331662 : if (TYPE_SIGN (type) == SIGNED)
2262 : 29185348 : return wi::sub (x, -1, SIGNED, &overflow);
2263 : : else
2264 : 30146314 : return wi::add (x, 1, UNSIGNED, &overflow);
2265 : : }
2266 : :
2267 : : // Return the inverse of a range.
2268 : :
2269 : : void
2270 : 60300444 : irange::invert ()
2271 : : {
2272 : 60300444 : gcc_checking_assert (!undefined_p () && !varying_p ());
2273 : :
2274 : : // We always need one more set of bounds to represent an inverse, so
2275 : : // if we're at the limit, we can't properly represent things.
2276 : : //
2277 : : // For instance, to represent the inverse of a 2 sub-range set
2278 : : // [5, 10][20, 30], we would need a 3 sub-range set
2279 : : // [-MIN, 4][11, 19][31, MAX].
2280 : : //
2281 : : // In this case, return the most conservative thing.
2282 : : //
2283 : : // However, if any of the extremes of the range are -MIN/+MAX, we
2284 : : // know we will not need an extra bound. For example:
2285 : : //
2286 : : // INVERT([-MIN,20][30,40]) => [21,29][41,+MAX]
2287 : : // INVERT([-MIN,20][30,MAX]) => [21,29]
2288 : 60300444 : tree ttype = type ();
2289 : 60300444 : unsigned prec = TYPE_PRECISION (ttype);
2290 : 60300444 : signop sign = TYPE_SIGN (ttype);
2291 : 60300444 : wide_int type_min = wi::min_value (prec, sign);
2292 : 60300444 : wide_int type_max = wi::max_value (prec, sign);
2293 : 60300444 : m_bitmask.set_unknown (prec);
2294 : :
2295 : : // At this point, we need one extra sub-range to represent the
2296 : : // inverse.
2297 : 60300444 : maybe_resize (m_num_ranges + 1);
2298 : :
2299 : : // The algorithm is as follows. To calculate INVERT ([a,b][c,d]), we
2300 : : // generate [-MIN, a-1][b+1, c-1][d+1, MAX].
2301 : : //
2302 : : // If there is an over/underflow in the calculation for any
2303 : : // sub-range, we eliminate that subrange. This allows us to easily
2304 : : // calculate INVERT([-MIN, 5]) with: [-MIN, -MIN-1][6, MAX]. And since
2305 : : // we eliminate the underflow, only [6, MAX] remains.
2306 : 60300444 : unsigned i = 0;
2307 : 60300444 : wi::overflow_type ovf;
2308 : : // Construct leftmost range.
2309 : 60300444 : int_range_max orig_range (*this);
2310 : 60300444 : unsigned nitems = 0;
2311 : 60300444 : wide_int tmp;
2312 : : // If this is going to underflow on the MINUS 1, don't even bother
2313 : : // checking. This also handles subtracting one from an unsigned 0,
2314 : : // which doesn't set the underflow bit.
2315 : 60300487 : if (type_min != orig_range.lower_bound ())
2316 : : {
2317 : 49297381 : m_base[nitems++] = type_min;
2318 : 49297424 : tmp = subtract_one (orig_range.lower_bound (), ttype, ovf);
2319 : 49297381 : m_base[nitems++] = tmp;
2320 : 49297381 : if (ovf)
2321 : 11003063 : nitems = 0;
2322 : : }
2323 : 60300444 : i++;
2324 : : // Construct middle ranges if applicable.
2325 : 60300444 : if (orig_range.num_pairs () > 1)
2326 : : {
2327 : : unsigned j = i;
2328 : 15233986 : for (; j < (orig_range.num_pairs () * 2) - 1; j += 2)
2329 : : {
2330 : : // The middle ranges cannot have MAX/MIN, so there's no need
2331 : : // to check for unsigned overflow on the +1 and -1 here.
2332 : 7623212 : tmp = wi::add (orig_range.m_base[j], 1, sign, &ovf);
2333 : 7623212 : m_base[nitems++] = tmp;
2334 : 7623212 : tmp = subtract_one (orig_range.m_base[j + 1], ttype, ovf);
2335 : 7623212 : m_base[nitems++] = tmp;
2336 : 7623212 : if (ovf)
2337 : 0 : nitems -= 2;
2338 : : }
2339 : : i = j;
2340 : : }
2341 : : // Construct rightmost range.
2342 : : //
2343 : : // However, if this will overflow on the PLUS 1, don't even bother.
2344 : : // This also handles adding one to an unsigned MAX, which doesn't
2345 : : // set the overflow bit.
2346 : 60300444 : if (type_max != orig_range.m_base[i])
2347 : : {
2348 : 59331662 : tmp = add_one (orig_range.m_base[i], ttype, ovf);
2349 : 59331662 : m_base[nitems++] = tmp;
2350 : 59331662 : m_base[nitems++] = type_max;
2351 : 59331662 : if (ovf)
2352 : 968782 : nitems -= 2;
2353 : : }
2354 : 60300444 : m_num_ranges = nitems / 2;
2355 : :
2356 : : // We disallow undefined or varying coming in, so the result can
2357 : : // only be a VR_RANGE.
2358 : 60300444 : gcc_checking_assert (m_kind == VR_RANGE);
2359 : :
2360 : 60300444 : if (flag_checking)
2361 : 60300314 : verify_range ();
2362 : 60300487 : }
2363 : :
2364 : : // This routine will take the bounds [LB, UB], and apply the bitmask to those
2365 : : // values such that both bounds satisfy the bitmask. TRUE is returned
2366 : : // if either bound changes, and they are returned as [NEW_LB, NEW_UB].
2367 : : // If there is an overflow, or if (NEW_UB < NEW_LB), then the entire bound is
2368 : : // to be removed as none of the values are valid. This is indicated by
2369 : : // teturning TRUE in OVF. False indicates the bounds are fine.
2370 : : // ie, [4, 14] MASK 0xFFFE VALUE 0x1
2371 : : // means all values must be odd, the new bounds returned will be [5, 13] with
2372 : : // OVF set to FALSE.
2373 : : // ie, [4, 4] MASK 0xFFFE VALUE 0x1
2374 : : // would return TRUE and OVF == TRUE. The entire subrange should be removed.
2375 : :
2376 : : bool
2377 : 172802599 : irange::snap (const wide_int &lb, const wide_int &ub,
2378 : : wide_int &new_lb, wide_int &new_ub, bool &ovf)
2379 : : {
2380 : 172802599 : ovf = false;
2381 : 172802599 : int z = wi::ctz (m_bitmask.mask ());
2382 : 172802599 : if (z == 0)
2383 : : return false;
2384 : :
2385 : : // Shortcircuit check for values that are already good.
2386 : 168264002 : if ((((lb ^ m_bitmask.value ()) | (ub ^ m_bitmask.value ()))
2387 : 252395883 : & ~m_bitmask.mask ()) == 0)
2388 : : return false;
2389 : :
2390 : 12968830 : const wide_int step = (wi::one (TYPE_PRECISION (type ())) << z);
2391 : 12968830 : const wide_int match_mask = step - 1;
2392 : 12968830 : const wide_int value = m_bitmask.value () & match_mask;
2393 : :
2394 : 12968830 : wide_int rem_lb = lb & match_mask;
2395 : 12968830 : wide_int offset = (value - rem_lb) & match_mask;
2396 : 12968830 : new_lb = lb + offset;
2397 : : // Check for overflows at +INF
2398 : 12968830 : if (wi::lt_p (new_lb, lb, TYPE_SIGN (type ())))
2399 : : {
2400 : 2213 : ovf = true;
2401 : 2213 : return true;
2402 : : }
2403 : :
2404 : 12966617 : wide_int rem_ub = ub & match_mask;
2405 : 12966617 : wide_int offset_ub = (rem_ub - value) & match_mask;
2406 : 12966617 : new_ub = ub - offset_ub;
2407 : : // Check for underflows at -INF
2408 : 12966617 : if (wi::gt_p (new_ub, ub, TYPE_SIGN (type ())))
2409 : : {
2410 : 111113 : ovf = true;
2411 : 111113 : return true;
2412 : : }
2413 : :
2414 : : // If inverted range is invalid, set overflow to TRUE.
2415 : 12855504 : if (wi::lt_p (new_ub, new_lb, TYPE_SIGN (type ())))
2416 : : {
2417 : 17890 : ovf = true;
2418 : 17890 : return true;
2419 : : }
2420 : 23449366 : return (new_lb != lb) || (new_ub != ub);
2421 : 25935527 : }
2422 : :
2423 : : // This method loops through the subranges in THIS, and adjusts any bounds
2424 : : // to satisfy the contraints of the BITMASK. If a subrange is invalid,
2425 : : // it is removed. TRUE is returned if there were any changes.
2426 : :
2427 : : bool
2428 : 122855307 : irange::snap_subranges ()
2429 : : {
2430 : 122855307 : bool changed = false;
2431 : 122855307 : int_range_max invalid;
2432 : 122855307 : unsigned x;
2433 : 122855307 : wide_int lb, ub;
2434 : 295657906 : for (x = 0; x < m_num_ranges; x++)
2435 : : {
2436 : 172802599 : bool ovf;
2437 : 172804211 : if (snap (lower_bound (x), upper_bound (x), lb, ub, ovf))
2438 : : {
2439 : 12862978 : changed = true;
2440 : : // Check if this subrange is to be completely removed.
2441 : 12862978 : if (ovf)
2442 : : {
2443 : 131216 : int_range<1> tmp (type (), lower_bound (x), upper_bound (x));
2444 : 131216 : invalid.union_ (tmp);
2445 : 131216 : continue;
2446 : 131216 : }
2447 : 12731778 : if (lower_bound (x) != lb)
2448 : 2225862 : m_base[x * 2] = lb;
2449 : 12731778 : if (upper_bound (x) != ub)
2450 : 11214660 : m_base[x * 2 + 1] = ub;
2451 : : }
2452 : : }
2453 : : // Remove any subranges which are no invalid.
2454 : 122855307 : if (!invalid.undefined_p ())
2455 : : {
2456 : 125792 : invalid.invert ();
2457 : 125792 : intersect (invalid);
2458 : : }
2459 : 122855307 : return changed;
2460 : 122855323 : }
2461 : :
2462 : : // If the bitmask has a range representation, intersect this range with
2463 : : // the bitmasks range. Then ensure all enpoints match the bitmask.
2464 : : // Return TRUE if the range changes at all.
2465 : :
2466 : : bool
2467 : 122855307 : irange::set_range_from_bitmask ()
2468 : : {
2469 : 122855307 : gcc_checking_assert (!undefined_p ());
2470 : : // Snap subranmges when bitmask is first set.
2471 : 122855307 : snap_subranges ();
2472 : 122855307 : if (undefined_p ())
2473 : : return true;
2474 : :
2475 : : // Calculate the set of ranges valid for the bitmask.
2476 : 122855261 : int_range_max allow;
2477 : 122855261 : if (!m_bitmask.range_from_mask (allow, m_type))
2478 : : return false;
2479 : : // And intersect that set of ranges with the current set.
2480 : 122777803 : return intersect (allow);
2481 : 122855261 : }
2482 : :
2483 : : void
2484 : 179382292 : irange::update_bitmask (const irange_bitmask &bm)
2485 : : {
2486 : 179382292 : gcc_checking_assert (!undefined_p ());
2487 : :
2488 : : // If masks are the same, there is no change.
2489 : 179382292 : if (m_bitmask == bm)
2490 : : return;
2491 : :
2492 : : // Drop VARYINGs with known bits to a plain range.
2493 : 87430894 : if (m_kind == VR_VARYING && !bm.unknown_p ())
2494 : 15791153 : m_kind = VR_RANGE;
2495 : :
2496 : 71639741 : m_bitmask = bm;
2497 : 71639741 : if (!set_range_from_bitmask ())
2498 : 41580219 : normalize_kind ();
2499 : 71639741 : if (flag_checking)
2500 : 71639635 : verify_range ();
2501 : : }
2502 : :
2503 : : // Return the bitmask of known bits that includes the bitmask inherent
2504 : : // in the range.
2505 : :
2506 : : irange_bitmask
2507 : 1100805463 : irange::get_bitmask () const
2508 : : {
2509 : 1100805463 : gcc_checking_assert (!undefined_p ());
2510 : :
2511 : : // The mask inherent in the range is calculated on-demand. For
2512 : : // example, [0,255] does not have known bits set by default. This
2513 : : // saves us considerable time, because setting it at creation incurs
2514 : : // a large penalty for irange::set. At the time of writing there
2515 : : // was a 5% slowdown in VRP if we kept the mask precisely up to date
2516 : : // at all times. Instead, we default to -1 and set it when
2517 : : // explicitly requested. However, this function will always return
2518 : : // the correct mask.
2519 : : //
2520 : : // This also means that the mask may have a finer granularity than
2521 : : // the range and thus contradict it. Think of the mask as an
2522 : : // enhancement to the range. For example:
2523 : : //
2524 : : // [3, 1000] MASK 0xfffffffe VALUE 0x0
2525 : : //
2526 : : // 3 is in the range endpoints, but is excluded per the known 0 bits
2527 : : // in the mask.
2528 : : //
2529 : : // See also the note in irange_bitmask::intersect.
2530 : 1100810894 : irange_bitmask bm (type (), lower_bound (), upper_bound ());
2531 : 1100805463 : if (!m_bitmask.unknown_p ())
2532 : : {
2533 : : // If the new intersection is unknown, it means there are inconstent
2534 : : // bits, so simply return the original bitmask.
2535 : 505166823 : if (!bm.intersect (m_bitmask))
2536 : 17571 : return m_bitmask;
2537 : : }
2538 : 1100787892 : return bm;
2539 : 1100805463 : }
2540 : :
2541 : : // Set the nonzero bits in R into THIS. Return TRUE and
2542 : : // normalize the range if anything changed.
2543 : :
2544 : : void
2545 : 669066 : vrange::set_nonzero_bits (const wide_int &bits)
2546 : : {
2547 : 669066 : gcc_checking_assert (!undefined_p ());
2548 : 669066 : irange_bitmask bm (wi::zero (TYPE_PRECISION (type ())), bits);
2549 : 669066 : update_bitmask (bm);
2550 : 669066 : }
2551 : :
2552 : : // Return the nonzero bits in R.
2553 : :
2554 : : wide_int
2555 : 223914975 : vrange::get_nonzero_bits () const
2556 : : {
2557 : 223914975 : gcc_checking_assert (!undefined_p ());
2558 : 223914975 : irange_bitmask bm = get_bitmask ();
2559 : 223915521 : return bm.value () | bm.mask ();
2560 : 223914975 : }
2561 : :
2562 : : // Intersect the bitmask in R into THIS and normalize the range.
2563 : : // Return TRUE if the intersection changed anything.
2564 : :
2565 : : bool
2566 : 485029630 : irange::intersect_bitmask (const irange &r)
2567 : : {
2568 : 485029630 : gcc_checking_assert (!undefined_p () && !r.undefined_p ());
2569 : :
2570 : : // If the bitmasks are the same, do nothing.
2571 : 485029630 : if (m_bitmask == r.m_bitmask)
2572 : : return false;
2573 : :
2574 : 177113625 : irange_bitmask bm = get_bitmask ();
2575 : 177113625 : irange_bitmask save = bm;
2576 : 177113625 : if (!bm.intersect (r.get_bitmask ()))
2577 : : {
2578 : 24691 : set_undefined ();
2579 : 24691 : return true;
2580 : : }
2581 : :
2582 : : // If the new mask is the same, there is no change.
2583 : 177088934 : if (m_bitmask == bm)
2584 : : return false;
2585 : :
2586 : 51215566 : m_bitmask = bm;
2587 : 51215566 : if (!set_range_from_bitmask ())
2588 : 50809343 : normalize_kind ();
2589 : 51215566 : if (flag_checking)
2590 : 51215398 : verify_range ();
2591 : : return true;
2592 : 177113625 : }
2593 : :
2594 : : // Union the bitmask in R into THIS. Return TRUE and normalize the
2595 : : // range if anything changed.
2596 : :
2597 : : bool
2598 : 283765411 : irange::union_bitmask (const irange &r)
2599 : : {
2600 : 283765411 : gcc_checking_assert (!undefined_p () && !r.undefined_p ());
2601 : :
2602 : 283765411 : if (m_bitmask == r.m_bitmask)
2603 : : return false;
2604 : :
2605 : 12959736 : irange_bitmask bm = get_bitmask ();
2606 : 12959736 : irange_bitmask save = bm;
2607 : 12959736 : bm.union_ (r.get_bitmask ());
2608 : 23021703 : if (save == bm && (!bm.unknown_p () || m_bitmask.unknown_p ()))
2609 : 10061967 : return false;
2610 : :
2611 : 2897769 : m_bitmask = bm;
2612 : :
2613 : : // Updating m_bitmask may still yield a semantic bitmask (as
2614 : : // returned by get_bitmask) which is functionally equivalent to what
2615 : : // we originally had. In which case, there's still no change.
2616 : 2897769 : if (save == get_bitmask ())
2617 : : return false;
2618 : :
2619 : : // No need to call set_range_from_mask, because we'll never
2620 : : // narrow the range. Besides, it would cause endless recursion
2621 : : // because of the union_ in set_range_from_mask.
2622 : 2897769 : normalize_kind ();
2623 : 2897769 : return true;
2624 : 12959736 : }
2625 : :
2626 : : tree
2627 : 8869218 : irange::lbound () const
2628 : : {
2629 : 8869218 : return wide_int_to_tree (type (), lower_bound ());
2630 : : }
2631 : :
2632 : : tree
2633 : 295272 : irange::ubound () const
2634 : : {
2635 : 295272 : return wide_int_to_tree (type (), upper_bound ());
2636 : : }
2637 : :
2638 : : void
2639 : 9556671573 : irange_bitmask::verify_mask () const
2640 : : {
2641 : 9556671573 : gcc_assert (m_value.get_precision () == m_mask.get_precision ());
2642 : 9556671573 : gcc_checking_assert (wi::bit_and (m_mask, m_value) == 0);
2643 : 9556671573 : }
2644 : :
2645 : : void
2646 : 0 : dump_value_range (FILE *file, const vrange *vr)
2647 : : {
2648 : 0 : vr->dump (file);
2649 : 0 : }
2650 : :
2651 : : DEBUG_FUNCTION void
2652 : 0 : debug (const vrange *vr)
2653 : : {
2654 : 0 : dump_value_range (stderr, vr);
2655 : 0 : fprintf (stderr, "\n");
2656 : 0 : }
2657 : :
2658 : : DEBUG_FUNCTION void
2659 : 0 : debug (const vrange &vr)
2660 : : {
2661 : 0 : debug (&vr);
2662 : 0 : }
2663 : :
2664 : : /* Return true, if VAL1 and VAL2 are equal values for VRP purposes. */
2665 : :
2666 : : bool
2667 : 64177060 : vrp_operand_equal_p (const_tree val1, const_tree val2)
2668 : : {
2669 : 64177060 : if (val1 == val2)
2670 : : return true;
2671 : 48339353 : if (!val1 || !val2 || !operand_equal_p (val1, val2, 0))
2672 : 47615972 : return false;
2673 : : return true;
2674 : : }
2675 : :
2676 : : #define DEFINE_INT_RANGE_INSTANCE(N) \
2677 : : template int_range<N>::int_range(tree_node *, \
2678 : : const wide_int &, \
2679 : : const wide_int &, \
2680 : : value_range_kind); \
2681 : : template int_range<N>::int_range(tree); \
2682 : : template int_range<N>::int_range(const irange &); \
2683 : : template int_range<N>::int_range(const int_range &); \
2684 : : template int_range<N>& int_range<N>::operator= (const int_range &);
2685 : :
2686 : : DEFINE_INT_RANGE_INSTANCE(1)
2687 : : DEFINE_INT_RANGE_INSTANCE(2)
2688 : : DEFINE_INT_RANGE_INSTANCE(3)
2689 : : DEFINE_INT_RANGE_INSTANCE(255)
2690 : :
2691 : : #if CHECKING_P
2692 : : #include "selftest.h"
2693 : :
2694 : : #define INT(x) wi::shwi ((x), TYPE_PRECISION (integer_type_node))
2695 : : #define UINT(x) wi::uhwi ((x), TYPE_PRECISION (unsigned_type_node))
2696 : : #define SCHAR(x) wi::shwi ((x), TYPE_PRECISION (signed_char_type_node))
2697 : :
2698 : : namespace selftest
2699 : : {
2700 : :
2701 : : static int_range<2>
2702 : 584 : range (tree type, int a, int b, value_range_kind kind = VR_RANGE)
2703 : : {
2704 : 584 : wide_int w1, w2;
2705 : 584 : if (TYPE_UNSIGNED (type))
2706 : : {
2707 : 40 : w1 = wi::uhwi (a, TYPE_PRECISION (type));
2708 : 40 : w2 = wi::uhwi (b, TYPE_PRECISION (type));
2709 : : }
2710 : : else
2711 : : {
2712 : 544 : w1 = wi::shwi (a, TYPE_PRECISION (type));
2713 : 544 : w2 = wi::shwi (b, TYPE_PRECISION (type));
2714 : : }
2715 : 584 : return int_range<2> (type, w1, w2, kind);
2716 : 584 : }
2717 : :
2718 : : static int_range<2>
2719 : 540 : range_int (int a, int b, value_range_kind kind = VR_RANGE)
2720 : : {
2721 : 0 : return range (integer_type_node, a, b, kind);
2722 : : }
2723 : :
2724 : : static int_range<2>
2725 : 8 : range_uint (int a, int b, value_range_kind kind = VR_RANGE)
2726 : : {
2727 : 0 : return range (unsigned_type_node, a, b, kind);
2728 : : }
2729 : :
2730 : : static int_range<2>
2731 : 8 : range_uint128 (int a, int b, value_range_kind kind = VR_RANGE)
2732 : : {
2733 : 8 : tree u128_type_node = build_nonstandard_integer_type (128, 1);
2734 : 8 : return range (u128_type_node, a, b, kind);
2735 : : }
2736 : :
2737 : : static int_range<2>
2738 : 12 : range_uchar (int a, int b, value_range_kind kind = VR_RANGE)
2739 : : {
2740 : 0 : return range (unsigned_char_type_node, a, b, kind);
2741 : : }
2742 : :
2743 : : static int_range<2>
2744 : 4 : range_char (int a, int b, value_range_kind kind = VR_RANGE)
2745 : : {
2746 : 0 : return range (signed_char_type_node, a, b, kind);
2747 : : }
2748 : :
2749 : : static int_range<3>
2750 : 44 : build_range3 (int a, int b, int c, int d, int e, int f)
2751 : : {
2752 : 44 : int_range<3> i1 = range_int (a, b);
2753 : 44 : int_range<3> i2 = range_int (c, d);
2754 : 44 : int_range<3> i3 = range_int (e, f);
2755 : 44 : i1.union_ (i2);
2756 : 44 : i1.union_ (i3);
2757 : 88 : return i1;
2758 : 44 : }
2759 : :
2760 : : static void
2761 : 4 : range_tests_irange3 ()
2762 : : {
2763 : 4 : int_range<3> r0, r1, r2;
2764 : 4 : int_range<3> i1, i2, i3;
2765 : :
2766 : : // ([10,20] U [5,8]) U [1,3] ==> [1,3][5,8][10,20].
2767 : 4 : r0 = range_int (10, 20);
2768 : 4 : r1 = range_int (5, 8);
2769 : 4 : r0.union_ (r1);
2770 : 4 : r1 = range_int (1, 3);
2771 : 4 : r0.union_ (r1);
2772 : 4 : ASSERT_TRUE (r0 == build_range3 (1, 3, 5, 8, 10, 20));
2773 : :
2774 : : // [1,3][5,8][10,20] U [-5,0] => [-5,3][5,8][10,20].
2775 : 4 : r1 = range_int (-5, 0);
2776 : 4 : r0.union_ (r1);
2777 : 4 : ASSERT_TRUE (r0 == build_range3 (-5, 3, 5, 8, 10, 20));
2778 : :
2779 : : // [10,20][30,40] U [50,60] ==> [10,20][30,40][50,60].
2780 : 4 : r1 = range_int (50, 60);
2781 : 4 : r0 = range_int (10, 20);
2782 : 4 : r0.union_ (range_int (30, 40));
2783 : 4 : r0.union_ (r1);
2784 : 4 : ASSERT_TRUE (r0 == build_range3 (10, 20, 30, 40, 50, 60));
2785 : : // [10,20][30,40][50,60] U [70, 80] ==> [10,20][30,40][50,60][70,80].
2786 : 4 : r1 = range_int (70, 80);
2787 : 4 : r0.union_ (r1);
2788 : :
2789 : 4 : r2 = build_range3 (10, 20, 30, 40, 50, 60);
2790 : 4 : r2.union_ (range_int (70, 80));
2791 : 4 : ASSERT_TRUE (r0 == r2);
2792 : :
2793 : : // [10,20][30,40][50,60] U [6,35] => [6,40][50,60].
2794 : 4 : r0 = build_range3 (10, 20, 30, 40, 50, 60);
2795 : 4 : r1 = range_int (6, 35);
2796 : 4 : r0.union_ (r1);
2797 : 4 : r1 = range_int (6, 40);
2798 : 4 : r1.union_ (range_int (50, 60));
2799 : 4 : ASSERT_TRUE (r0 == r1);
2800 : :
2801 : : // [10,20][30,40][50,60] U [6,60] => [6,60].
2802 : 4 : r0 = build_range3 (10, 20, 30, 40, 50, 60);
2803 : 4 : r1 = range_int (6, 60);
2804 : 4 : r0.union_ (r1);
2805 : 4 : ASSERT_TRUE (r0 == range_int (6, 60));
2806 : :
2807 : : // [10,20][30,40][50,60] U [6,70] => [6,70].
2808 : 4 : r0 = build_range3 (10, 20, 30, 40, 50, 60);
2809 : 4 : r1 = range_int (6, 70);
2810 : 4 : r0.union_ (r1);
2811 : 4 : ASSERT_TRUE (r0 == range_int (6, 70));
2812 : :
2813 : : // [10,20][30,40][50,60] U [35,70] => [10,20][30,70].
2814 : 4 : r0 = build_range3 (10, 20, 30, 40, 50, 60);
2815 : 4 : r1 = range_int (35, 70);
2816 : 4 : r0.union_ (r1);
2817 : 4 : r1 = range_int (10, 20);
2818 : 4 : r1.union_ (range_int (30, 70));
2819 : 4 : ASSERT_TRUE (r0 == r1);
2820 : :
2821 : : // [10,20][30,40][50,60] U [15,35] => [10,40][50,60].
2822 : 4 : r0 = build_range3 (10, 20, 30, 40, 50, 60);
2823 : 4 : r1 = range_int (15, 35);
2824 : 4 : r0.union_ (r1);
2825 : 4 : r1 = range_int (10, 40);
2826 : 4 : r1.union_ (range_int (50, 60));
2827 : 4 : ASSERT_TRUE (r0 == r1);
2828 : :
2829 : : // [10,20][30,40][50,60] U [35,35] => [10,20][30,40][50,60].
2830 : 4 : r0 = build_range3 (10, 20, 30, 40, 50, 60);
2831 : 4 : r1 = range_int (35, 35);
2832 : 4 : r0.union_ (r1);
2833 : 4 : ASSERT_TRUE (r0 == build_range3 (10, 20, 30, 40, 50, 60));
2834 : 4 : }
2835 : :
2836 : : static void
2837 : 4 : range_tests_int_range_max ()
2838 : : {
2839 : 4 : int_range_max big;
2840 : 4 : unsigned int nrange;
2841 : :
2842 : : // Build a huge multi-range range.
2843 : 204 : for (nrange = 0; nrange < 50; ++nrange)
2844 : : {
2845 : 200 : int_range<1> tmp = range_int (nrange*10, nrange *10 + 5);
2846 : 200 : big.union_ (tmp);
2847 : 200 : }
2848 : 4 : ASSERT_TRUE (big.num_pairs () == nrange);
2849 : :
2850 : : // Verify that we can copy it without loosing precision.
2851 : 4 : int_range_max copy (big);
2852 : 4 : ASSERT_TRUE (copy.num_pairs () == nrange);
2853 : :
2854 : : // Inverting it should produce one more sub-range.
2855 : 4 : big.invert ();
2856 : 4 : ASSERT_TRUE (big.num_pairs () == nrange + 1);
2857 : :
2858 : 4 : int_range<1> tmp = range_int (5, 37);
2859 : 4 : big.intersect (tmp);
2860 : 4 : ASSERT_TRUE (big.num_pairs () == 4);
2861 : :
2862 : : // Test that [10,10][20,20] does NOT contain 15.
2863 : 4 : {
2864 : 4 : int_range_max i1 = range_int (10, 10);
2865 : 4 : int_range_max i2 = range_int (20, 20);
2866 : 4 : i1.union_ (i2);
2867 : 4 : ASSERT_FALSE (i1.contains_p (INT (15)));
2868 : 4 : }
2869 : 4 : }
2870 : :
2871 : : // Simulate -fstrict-enums where the domain of a type is less than the
2872 : : // underlying type.
2873 : :
2874 : : static void
2875 : 4 : range_tests_strict_enum ()
2876 : : {
2877 : : // The enum can only hold [0, 3].
2878 : 4 : tree rtype = copy_node (unsigned_type_node);
2879 : 4 : TYPE_MIN_VALUE (rtype) = build_int_cstu (rtype, 0);
2880 : 4 : TYPE_MAX_VALUE (rtype) = build_int_cstu (rtype, 3);
2881 : :
2882 : : // Test that even though vr1 covers the strict enum domain ([0, 3]),
2883 : : // it does not cover the domain of the underlying type.
2884 : 4 : int_range<1> vr1 = range (rtype, 0, 1);
2885 : 4 : int_range<1> vr2 = range (rtype, 2, 3);
2886 : 4 : vr1.union_ (vr2);
2887 : 4 : ASSERT_TRUE (vr1 == range (rtype, 0, 3));
2888 : 4 : ASSERT_FALSE (vr1.varying_p ());
2889 : :
2890 : : // Test that copying to a multi-range does not change things.
2891 : 4 : int_range<2> ir1 (vr1);
2892 : 4 : ASSERT_TRUE (ir1 == vr1);
2893 : 4 : ASSERT_FALSE (ir1.varying_p ());
2894 : :
2895 : : // The same test as above, but using TYPE_{MIN,MAX}_VALUE instead of [0,3].
2896 : 8 : vr1 = int_range<2> (rtype,
2897 : 8 : wi::to_wide (TYPE_MIN_VALUE (rtype)),
2898 : 12 : wi::to_wide (TYPE_MAX_VALUE (rtype)));
2899 : 4 : ir1 = vr1;
2900 : 4 : ASSERT_TRUE (ir1 == vr1);
2901 : 4 : ASSERT_FALSE (ir1.varying_p ());
2902 : 4 : }
2903 : :
2904 : : // Test that range bounds are "snapped" to where they are expected to be.
2905 : :
2906 : : static void
2907 : 104 : assert_snap_result (int lb_val, int ub_val,
2908 : : int expected_lb, int expected_ub,
2909 : : unsigned mask_val, unsigned value_val,
2910 : : tree type)
2911 : : {
2912 : 104 : wide_int lb = wi::shwi (lb_val, TYPE_PRECISION (type));
2913 : 104 : wide_int ub = wi::shwi (ub_val, TYPE_PRECISION (type));
2914 : 104 : wide_int new_lb, new_ub;
2915 : :
2916 : 208 : irange_bitmask bm (wi::uhwi (value_val, TYPE_PRECISION (type)),
2917 : 208 : wi::uhwi (mask_val, TYPE_PRECISION (type)));
2918 : :
2919 : 104 : int_range_max r (type);
2920 : 104 : r.set (type, lb, ub);
2921 : 104 : r.update_bitmask (bm);
2922 : :
2923 : 104 : if (TYPE_SIGN (type) == SIGNED && expected_ub < expected_lb)
2924 : 20 : gcc_checking_assert (r.undefined_p ());
2925 : 84 : else if (TYPE_SIGN (type) == UNSIGNED
2926 : 84 : && ((unsigned)expected_ub < (unsigned)expected_lb))
2927 : 16 : gcc_checking_assert (r.undefined_p ());
2928 : : else
2929 : : {
2930 : 68 : gcc_checking_assert (wi::eq_p (r.lower_bound (),
2931 : : wi::shwi (expected_lb,
2932 : : TYPE_PRECISION (type))));
2933 : 136 : gcc_checking_assert (wi::eq_p (r.upper_bound (),
2934 : : wi::shwi (expected_ub,
2935 : : TYPE_PRECISION (type))));
2936 : : }
2937 : 104 : }
2938 : :
2939 : :
2940 : : // Run a selection of tests that confirm, bounds are snapped as expected.
2941 : : // We only test individual pairs, multiple pairs use the same snapping
2942 : : // routine as single pairs.
2943 : :
2944 : : static void
2945 : 4 : test_irange_snap_bounds ()
2946 : : {
2947 : 4 : tree u32 = unsigned_type_node;
2948 : 4 : tree s32 = integer_type_node;
2949 : 4 : tree s8 = build_nonstandard_integer_type (8, /*unsigned=*/ 0);
2950 : 4 : tree s1 = build_nonstandard_integer_type (1, /*unsigned=*/ 0);
2951 : 4 : tree u1 = build_nonstandard_integer_type (1, /*unsigned=*/ 1);
2952 : :
2953 : : // Basic aligned range: even-only
2954 : 4 : assert_snap_result (5, 15, 6, 14, 0xE, 0x0, u32);
2955 : : // Singleton that doesn't match mask: undefined.
2956 : 4 : assert_snap_result (7, 7, 1, 0, 0xFFFFFFFE, 0x0, u32);
2957 : : // 8-bit signed char, mask 0xF0 (i.e. step of 16).
2958 : 4 : assert_snap_result (-100, 100, -96, 96, 0xF0, 0x00, s8);
2959 : : // Already aligned range: no change.
2960 : 4 : assert_snap_result (0, 240, 0, 240, 0xF0, 0x00, u32);
2961 : : // Negative range, step 16 alignment (s32).
2962 : 4 : assert_snap_result (-123, -17, -112, -32, 0xFFFFFFF0, 0x00, s32);
2963 : : // Negative range, step 16 alignment (trailing-zero aligned mask).
2964 : 4 : assert_snap_result (-123, -17, -112, -32, 0xFFFFFFF0, 0x00, s32);
2965 : : // s8, 16-alignment mask, value = 0 (valid).
2966 : 4 : assert_snap_result (-50, 10, -48, 0, 0xF0, 0x00, s8);
2967 : : // No values in range [-3,2] match alignment except 0.
2968 : 4 : assert_snap_result (-3, 2, 0, 0, 0xF8, 0x00, s8);
2969 : : // No values in range [-3,2] match alignment — undefined.
2970 : 4 : assert_snap_result (-3, 2, 1, 0, 0xF8, 0x04, s8);
2971 : : // Already aligned range: no change.
2972 : 4 : assert_snap_result (0, 240, 0, 240, 0xF0, 0x00, s32);
2973 : : // 1-bit signed: only -1 allowed (0b1).
2974 : 4 : assert_snap_result (-1, 0, -1, -1, 0x00, 0x01, s1);
2975 : : // 1-bit signed: only 0 allowed (0b0).
2976 : 4 : assert_snap_result (-1, 0, 0, 0, 0x00, 0x00, s1);
2977 : : // 1-bit signed: no match (invalid case).
2978 : 4 : assert_snap_result (-1, -1, 1, 0, 0x00, 0x00, s1);
2979 : : // 1-bit signed: no match (invalid case).
2980 : 4 : assert_snap_result (0, 0, 1, 0, 0x00, 0x01, s1);
2981 : : // 1-bit unsigned: only 1 allowed.
2982 : 4 : assert_snap_result (0, 1, 1, 1, 0x00, 0x01, u1);
2983 : : // 1-bit unsigned: only 0 allowed.
2984 : 4 : assert_snap_result (0, 1, 0, 0, 0x00, 0x00, u1);
2985 : : // 1-bit unsigned: no match (invalid case).
2986 : 4 : assert_snap_result (1, 1, 1, 0, 0x00, 0x00, u1);
2987 : : // 1-bit unsigned: no match (invalid case).
2988 : 4 : assert_snap_result (0, 0, 1, 0, 0x00, 0x01, u1);
2989 : : // Unsigned: Near overflow, even alignment.
2990 : 4 : assert_snap_result (UINT_MAX - 6, UINT_MAX, UINT_MAX - 5, UINT_MAX - 1,
2991 : : 0xFFFFFFFE, 0x00, u32);
2992 : : // Unsigned: Wraparound-like range — no valid snapped values.
2993 : 4 : assert_snap_result (UINT_MAX - 5, UINT_MAX, 1, 0, 0xFFFFFFF0, 0x00, u32);
2994 : : // Signed: Near INT_MAX, 8-aligned.
2995 : 4 : assert_snap_result (INT_MAX - 18, INT_MAX, INT_MAX - 15, INT_MAX - 7,
2996 : : 0xFFFFFFF8, 0x00, s32);
2997 : : // Signed: Near INT_MIN, 16-aligned.
2998 : 4 : assert_snap_result (INT_MIN, INT_MIN + 30, INT_MIN, INT_MIN + 16,
2999 : : 0xFFFFFFF0, 0x00, s32);
3000 : : // Signed: Full domain, 4-aligned.
3001 : 4 : assert_snap_result (-128, 127, -128, 124, 0xFC, 0x00, s8);
3002 : : // Singleton at INT_MIN that doesn’t match alignment — undefined
3003 : 4 : assert_snap_result (INT_MIN, INT_MIN, 1, 0, 0xFFFFFFFE, 0x01, s32);
3004 : : // Range at INT_MIN that doesn’t match alignment — undefined.
3005 : 4 : assert_snap_result (INT_MIN, INT_MIN + 10, 1, 0, 0xFFFFFFF0, 0x0F, s32);
3006 : : // Unsigned: Full domain, 256-aligned.
3007 : 4 : assert_snap_result (0, UINT_MAX, 0, UINT_MAX & ~255, 0xFFFFFF00, 0x00, u32);
3008 : 4 : }
3009 : :
3010 : : static void
3011 : 4 : range_tests_misc ()
3012 : : {
3013 : 4 : tree u128_type = build_nonstandard_integer_type (128, /*unsigned=*/1);
3014 : 4 : int_range<2> i1, i2, i3;
3015 : 4 : int_range<2> r0, r1, rold;
3016 : :
3017 : : // Test 1-bit signed integer union.
3018 : : // [-1,-1] U [0,0] = VARYING.
3019 : 4 : tree one_bit_type = build_nonstandard_integer_type (1, 0);
3020 : 4 : wide_int one_bit_min = irange_val_min (one_bit_type);
3021 : 4 : wide_int one_bit_max = irange_val_max (one_bit_type);
3022 : 4 : {
3023 : 4 : int_range<2> min = int_range<2> (one_bit_type, one_bit_min, one_bit_min);
3024 : 4 : int_range<2> max = int_range<2> (one_bit_type, one_bit_max, one_bit_max);
3025 : 4 : max.union_ (min);
3026 : 4 : ASSERT_TRUE (max.varying_p ());
3027 : 4 : }
3028 : : // Test that we can set a range of true+false for a 1-bit signed int.
3029 : 4 : r0 = range_true_and_false (one_bit_type);
3030 : :
3031 : : // Test inversion of 1-bit signed integers.
3032 : 4 : {
3033 : 4 : int_range<2> min = int_range<2> (one_bit_type, one_bit_min, one_bit_min);
3034 : 4 : int_range<2> max = int_range<2> (one_bit_type, one_bit_max, one_bit_max);
3035 : 4 : int_range<2> t;
3036 : 4 : t = min;
3037 : 4 : t.invert ();
3038 : 4 : ASSERT_TRUE (t == max);
3039 : 4 : t = max;
3040 : 4 : t.invert ();
3041 : 4 : ASSERT_TRUE (t == min);
3042 : 4 : }
3043 : :
3044 : : // Test that NOT(255) is [0..254] in 8-bit land.
3045 : 4 : int_range<1> not_255 = range_uchar (255, 255, VR_ANTI_RANGE);
3046 : 4 : ASSERT_TRUE (not_255 == range_uchar (0, 254));
3047 : :
3048 : : // Test that NOT(0) is [1..255] in 8-bit land.
3049 : 4 : int_range<2> not_zero;
3050 : 4 : not_zero.set_nonzero (unsigned_char_type_node);
3051 : 4 : ASSERT_TRUE (not_zero == range_uchar (1, 255));
3052 : :
3053 : : // Check that [0,127][0x..ffffff80,0x..ffffff]
3054 : : // => ~[128, 0x..ffffff7f].
3055 : 4 : r0 = range_uint128 (0, 127);
3056 : 4 : wide_int high = wi::minus_one (128);
3057 : : // low = -1 - 127 => 0x..ffffff80.
3058 : 4 : wide_int low = wi::sub (high, wi::uhwi (127, 128));
3059 : 4 : r1 = int_range<1> (u128_type, low, high); // [0x..ffffff80, 0x..ffffffff]
3060 : : // r0 = [0,127][0x..ffffff80,0x..fffffff].
3061 : 4 : r0.union_ (r1);
3062 : : // r1 = [128, 0x..ffffff7f].
3063 : 12 : r1 = int_range<1> (u128_type,
3064 : 8 : wi::uhwi (128, 128),
3065 : 8 : wi::sub (wi::minus_one (128), wi::uhwi (128, 128)));
3066 : 4 : r0.invert ();
3067 : 4 : ASSERT_TRUE (r0 == r1);
3068 : :
3069 : 4 : r0.set_varying (integer_type_node);
3070 : 4 : wide_int minint = r0.lower_bound ();
3071 : 4 : wide_int maxint = r0.upper_bound ();
3072 : :
3073 : 4 : r0.set_varying (short_integer_type_node);
3074 : :
3075 : 4 : r0.set_varying (unsigned_type_node);
3076 : 4 : wide_int maxuint = r0.upper_bound ();
3077 : :
3078 : : // Check that ~[0,5] => [6,MAX] for unsigned int.
3079 : 4 : r0 = range_uint (0, 5);
3080 : 4 : r0.invert ();
3081 : 4 : ASSERT_TRUE (r0 == int_range<1> (unsigned_type_node,
3082 : : wi::uhwi (6, TYPE_PRECISION (unsigned_type_node)),
3083 : : maxuint));
3084 : :
3085 : : // Check that ~[10,MAX] => [0,9] for unsigned int.
3086 : 8 : r0 = int_range<1> (unsigned_type_node,
3087 : 4 : wi::uhwi (10, TYPE_PRECISION (unsigned_type_node)),
3088 : 8 : maxuint);
3089 : 4 : r0.invert ();
3090 : 4 : ASSERT_TRUE (r0 == range_uint (0, 9));
3091 : :
3092 : : // Check that ~[0,5] => [6,MAX] for unsigned 128-bit numbers.
3093 : 4 : r0 = range_uint128 (0, 5, VR_ANTI_RANGE);
3094 : 4 : r1 = int_range<1> (u128_type, wi::uhwi (6, 128), wi::minus_one (128));
3095 : 4 : ASSERT_TRUE (r0 == r1);
3096 : :
3097 : : // Check that [~5] is really [-MIN,4][6,MAX].
3098 : 4 : r0 = range_int (5, 5, VR_ANTI_RANGE);
3099 : 4 : r1 = int_range<1> (integer_type_node, minint, INT (4));
3100 : 4 : r1.union_ (int_range<1> (integer_type_node, INT (6), maxint));
3101 : 4 : ASSERT_FALSE (r1.undefined_p ());
3102 : 4 : ASSERT_TRUE (r0 == r1);
3103 : :
3104 : 4 : r1 = range_int (5, 5);
3105 : 4 : int_range<2> r2 (r1);
3106 : 4 : ASSERT_TRUE (r1 == r2);
3107 : :
3108 : 4 : r1 = range_int (5, 10);
3109 : :
3110 : 4 : r1 = range_int (5, 10);
3111 : 4 : ASSERT_TRUE (r1.contains_p (INT (7)));
3112 : :
3113 : 4 : r1 = range_char (0, 20);
3114 : 4 : ASSERT_TRUE (r1.contains_p (SCHAR(15)));
3115 : 4 : ASSERT_FALSE (r1.contains_p (SCHAR(300)));
3116 : :
3117 : : // NOT([10,20]) ==> [-MIN,9][21,MAX].
3118 : 4 : r0 = r1 = range_int (10, 20);
3119 : 4 : r2 = int_range<1> (integer_type_node, minint, INT(9));
3120 : 4 : r2.union_ (int_range<1> (integer_type_node, INT(21), maxint));
3121 : 4 : ASSERT_FALSE (r2.undefined_p ());
3122 : 4 : r1.invert ();
3123 : 4 : ASSERT_TRUE (r1 == r2);
3124 : : // Test that NOT(NOT(x)) == x.
3125 : 4 : r2.invert ();
3126 : 4 : ASSERT_TRUE (r0 == r2);
3127 : :
3128 : : // Test that booleans and their inverse work as expected.
3129 : 4 : r0.set_zero (boolean_type_node);
3130 : 4 : ASSERT_TRUE (r0 == range_false ());
3131 : 4 : r0.invert ();
3132 : 4 : ASSERT_TRUE (r0 == range_true ());
3133 : :
3134 : : // Make sure NULL and non-NULL of pointer types work, and that
3135 : : // inverses of them are consistent.
3136 : 4 : tree voidp = build_pointer_type (void_type_node);
3137 : 4 : prange p0;
3138 : 4 : p0.set_zero (voidp);
3139 : 4 : prange p1 = p0;
3140 : 4 : p0.invert ();
3141 : 4 : p0.invert ();
3142 : 4 : ASSERT_TRUE (p0 == p1);
3143 : :
3144 : : // The intersection of:
3145 : : // [0, +INF] MASK 0xff..00 VALUE 0xf8
3146 : : // [0, +INF] MASK 0xff..00 VALUE 0x00
3147 : : // is [0, +INF] MASK 0xff..ff VALUE 0x00, which is VARYING.
3148 : : // Test that we normalized to VARYING.
3149 : 4 : unsigned prec = TYPE_PRECISION (voidp);
3150 : 4 : p0.set_varying (voidp);
3151 : 4 : wide_int mask = wi::mask (8, true, prec);
3152 : 4 : wide_int value = wi::uhwi (0xf8, prec);
3153 : 4 : irange_bitmask bm (wi::uhwi (0xf8, prec), mask);
3154 : 4 : p0.update_bitmask (bm);
3155 : 4 : p1.set_varying (voidp);
3156 : 4 : bm = irange_bitmask (wi::zero (prec), mask);
3157 : 4 : p1.update_bitmask (bm);
3158 : 4 : p0.intersect (p1);
3159 : :
3160 : : // [10,20] U [15, 30] => [10, 30].
3161 : 4 : r0 = range_int (10, 20);
3162 : 4 : r1 = range_int (15, 30);
3163 : 4 : r0.union_ (r1);
3164 : 4 : ASSERT_TRUE (r0 == range_int (10, 30));
3165 : :
3166 : : // [15,40] U [] => [15,40].
3167 : 4 : r0 = range_int (15, 40);
3168 : 4 : r1.set_undefined ();
3169 : 4 : r0.union_ (r1);
3170 : 4 : ASSERT_TRUE (r0 == range_int (15, 40));
3171 : :
3172 : : // [10,20] U [10,10] => [10,20].
3173 : 4 : r0 = range_int (10, 20);
3174 : 4 : r1 = range_int (10, 10);
3175 : 4 : r0.union_ (r1);
3176 : 4 : ASSERT_TRUE (r0 == range_int (10, 20));
3177 : :
3178 : : // [10,20] U [9,9] => [9,20].
3179 : 4 : r0 = range_int (10, 20);
3180 : 4 : r1 = range_int (9, 9);
3181 : 4 : r0.union_ (r1);
3182 : 4 : ASSERT_TRUE (r0 == range_int (9, 20));
3183 : :
3184 : : // [10,20] ^ [15,30] => [15,20].
3185 : 4 : r0 = range_int (10, 20);
3186 : 4 : r1 = range_int (15, 30);
3187 : 4 : r0.intersect (r1);
3188 : 4 : ASSERT_TRUE (r0 == range_int (15, 20));
3189 : :
3190 : : // Test the internal sanity of wide_int's wrt HWIs.
3191 : 4 : ASSERT_TRUE (wi::max_value (TYPE_PRECISION (boolean_type_node),
3192 : : TYPE_SIGN (boolean_type_node))
3193 : : == wi::uhwi (1, TYPE_PRECISION (boolean_type_node)));
3194 : :
3195 : : // Test zero_p().
3196 : 4 : r0 = range_int (0, 0);
3197 : 4 : ASSERT_TRUE (r0.zero_p ());
3198 : :
3199 : : // Test nonzero_p().
3200 : 4 : r0 = range_int (0, 0);
3201 : 4 : r0.invert ();
3202 : 4 : ASSERT_TRUE (r0.nonzero_p ());
3203 : :
3204 : : // r0 = ~[1,1]
3205 : 4 : r0 = range_int (1, 1, VR_ANTI_RANGE);
3206 : : // r1 = ~[3,3]
3207 : 4 : r1 = range_int (3, 3, VR_ANTI_RANGE);
3208 : :
3209 : : // vv = [0,0][2,2][4, MAX]
3210 : 4 : int_range<3> vv = r0;
3211 : 4 : vv.intersect (r1);
3212 : :
3213 : 4 : ASSERT_TRUE (vv.contains_p (UINT (2)));
3214 : 4 : ASSERT_TRUE (vv.num_pairs () == 3);
3215 : :
3216 : 4 : r0 = range_int (1, 1);
3217 : : // And union it with [0,0][2,2][4,MAX] multi range
3218 : 4 : r0.union_ (vv);
3219 : : // The result should be [0,2][4,MAX], or ~[3,3] but it must contain 2
3220 : 4 : ASSERT_TRUE (r0.contains_p (INT (2)));
3221 : 4 : }
3222 : :
3223 : : static void
3224 : 4 : range_tests_nonzero_bits ()
3225 : : {
3226 : 4 : int_range<8> r0, r1;
3227 : :
3228 : : // Adding nonzero bits to a varying drops the varying.
3229 : 4 : r0.set_varying (integer_type_node);
3230 : 4 : r0.set_nonzero_bits (INT (255));
3231 : 4 : ASSERT_TRUE (!r0.varying_p ());
3232 : :
3233 : : // Test contains_p with nonzero bits.
3234 : 4 : r0.set_zero (integer_type_node);
3235 : 4 : ASSERT_TRUE (r0.contains_p (INT (0)));
3236 : 4 : ASSERT_FALSE (r0.contains_p (INT (1)));
3237 : 4 : r0.set_nonzero_bits (INT (0xfe));
3238 : 4 : ASSERT_FALSE (r0.contains_p (INT (0x100)));
3239 : 4 : ASSERT_FALSE (r0.contains_p (INT (0x3)));
3240 : :
3241 : : // Union of nonzero bits.
3242 : 4 : r0.set_varying (integer_type_node);
3243 : 4 : r0.set_nonzero_bits (INT (0xf0));
3244 : 4 : r1.set_varying (integer_type_node);
3245 : 4 : r1.set_nonzero_bits (INT (0xf));
3246 : 4 : r0.union_ (r1);
3247 : 4 : ASSERT_TRUE (r0.get_nonzero_bits () == 0xff);
3248 : :
3249 : : // Intersect of nonzero bits.
3250 : 4 : r0 = range_int (0, 255);
3251 : 4 : r0.set_nonzero_bits (INT (0xfe));
3252 : 4 : r1.set_varying (integer_type_node);
3253 : 4 : r1.set_nonzero_bits (INT (0xf0));
3254 : 4 : r0.intersect (r1);
3255 : 4 : ASSERT_TRUE (r0.get_nonzero_bits () == 0xf0);
3256 : :
3257 : : // Intersect where the mask of nonzero bits is implicit from the range.
3258 : 4 : r0.set_varying (integer_type_node);
3259 : 4 : r1 = range_int (0, 255);
3260 : 4 : r0.intersect (r1);
3261 : 4 : ASSERT_TRUE (r0.get_nonzero_bits () == 0xff);
3262 : :
3263 : : // Test that setting a nonzero bit of 1 does not pessimize the range.
3264 : 4 : r0.set_zero (integer_type_node);
3265 : 4 : r0.set_nonzero_bits (INT (1));
3266 : 4 : ASSERT_TRUE (r0.zero_p ());
3267 : :
3268 : : // Now test that range bounds are snapped to match bitmask alignments.
3269 : 4 : test_irange_snap_bounds ();
3270 : 4 : }
3271 : :
3272 : : // Build an frange from string endpoints.
3273 : :
3274 : : static inline frange
3275 : 492 : frange_float (const char *lb, const char *ub, tree type = float_type_node)
3276 : : {
3277 : 492 : REAL_VALUE_TYPE min, max;
3278 : 492 : gcc_assert (real_from_string (&min, lb) == 0);
3279 : 492 : gcc_assert (real_from_string (&max, ub) == 0);
3280 : 492 : return frange (type, min, max);
3281 : : }
3282 : :
3283 : : static void
3284 : 4 : range_tests_nan ()
3285 : : {
3286 : 4 : frange r0, r1;
3287 : 4 : REAL_VALUE_TYPE q, r;
3288 : 4 : bool signbit;
3289 : :
3290 : : // Equal ranges but with differing NAN bits are not equal.
3291 : 4 : if (HONOR_NANS (float_type_node))
3292 : : {
3293 : 4 : r1 = frange_float ("10", "12");
3294 : 4 : r0 = r1;
3295 : 4 : ASSERT_EQ (r0, r1);
3296 : 4 : r0.clear_nan ();
3297 : 4 : ASSERT_NE (r0, r1);
3298 : 4 : r0.update_nan ();
3299 : 4 : ASSERT_EQ (r0, r1);
3300 : :
3301 : : // [10, 20] NAN ^ [30, 40] NAN = NAN.
3302 : 4 : r0 = frange_float ("10", "20");
3303 : 4 : r1 = frange_float ("30", "40");
3304 : 4 : r0.intersect (r1);
3305 : 4 : ASSERT_TRUE (r0.known_isnan ());
3306 : :
3307 : : // [3,5] U [5,10] NAN = ... NAN
3308 : 4 : r0 = frange_float ("3", "5");
3309 : 4 : r0.clear_nan ();
3310 : 4 : r1 = frange_float ("5", "10");
3311 : 4 : r0.union_ (r1);
3312 : 8 : ASSERT_TRUE (r0.maybe_isnan ());
3313 : : }
3314 : :
3315 : : // [5,6] U NAN = [5,6] NAN.
3316 : 4 : r0 = frange_float ("5", "6");
3317 : 4 : r0.clear_nan ();
3318 : 4 : r1.set_nan (float_type_node);
3319 : 4 : r0.union_ (r1);
3320 : 4 : real_from_string (&q, "5");
3321 : 4 : real_from_string (&r, "6");
3322 : 4 : ASSERT_TRUE (real_identical (&q, &r0.lower_bound ()));
3323 : 4 : ASSERT_TRUE (real_identical (&r, &r0.upper_bound ()));
3324 : 8 : ASSERT_TRUE (r0.maybe_isnan ());
3325 : :
3326 : : // NAN U NAN = NAN
3327 : 4 : r0.set_nan (float_type_node);
3328 : 4 : r1.set_nan (float_type_node);
3329 : 4 : r0.union_ (r1);
3330 : 4 : ASSERT_TRUE (r0.known_isnan ());
3331 : :
3332 : : // [INF, INF] NAN ^ NAN = NAN
3333 : 4 : r0.set_nan (float_type_node);
3334 : 4 : r1 = frange_float ("+Inf", "+Inf");
3335 : 4 : if (!HONOR_NANS (float_type_node))
3336 : 0 : r1.update_nan ();
3337 : 4 : r0.intersect (r1);
3338 : 4 : ASSERT_TRUE (r0.known_isnan ());
3339 : :
3340 : : // NAN ^ NAN = NAN
3341 : 4 : r0.set_nan (float_type_node);
3342 : 4 : r1.set_nan (float_type_node);
3343 : 4 : r0.intersect (r1);
3344 : 4 : ASSERT_TRUE (r0.known_isnan ());
3345 : :
3346 : : // +NAN ^ -NAN = UNDEFINED
3347 : 4 : r0.set_nan (float_type_node, false);
3348 : 4 : r1.set_nan (float_type_node, true);
3349 : 4 : r0.intersect (r1);
3350 : 4 : ASSERT_TRUE (r0.undefined_p ());
3351 : :
3352 : : // VARYING ^ NAN = NAN.
3353 : 4 : r0.set_nan (float_type_node);
3354 : 4 : r1.set_varying (float_type_node);
3355 : 4 : r0.intersect (r1);
3356 : 4 : ASSERT_TRUE (r0.known_isnan ());
3357 : :
3358 : : // [3,4] ^ NAN = UNDEFINED.
3359 : 4 : r0 = frange_float ("3", "4");
3360 : 4 : r0.clear_nan ();
3361 : 4 : r1.set_nan (float_type_node);
3362 : 4 : r0.intersect (r1);
3363 : 4 : ASSERT_TRUE (r0.undefined_p ());
3364 : :
3365 : : // [-3, 5] ^ NAN = UNDEFINED
3366 : 4 : r0 = frange_float ("-3", "5");
3367 : 4 : r0.clear_nan ();
3368 : 4 : r1.set_nan (float_type_node);
3369 : 4 : r0.intersect (r1);
3370 : 4 : ASSERT_TRUE (r0.undefined_p ());
3371 : :
3372 : : // Setting the NAN bit to yes does not make us a known NAN.
3373 : 4 : r0.set_varying (float_type_node);
3374 : 4 : r0.update_nan ();
3375 : 4 : ASSERT_FALSE (r0.known_isnan ());
3376 : :
3377 : : // NAN is in a VARYING.
3378 : 4 : r0.set_varying (float_type_node);
3379 : 4 : real_nan (&r, "", 1, TYPE_MODE (float_type_node));
3380 : 4 : REAL_VALUE_TYPE nan = r;
3381 : 4 : ASSERT_TRUE (r0.contains_p (nan));
3382 : :
3383 : : // -NAN is in a VARYING.
3384 : 4 : r0.set_varying (float_type_node);
3385 : 4 : q = real_value_negate (&r);
3386 : 4 : REAL_VALUE_TYPE neg_nan = q;
3387 : 4 : ASSERT_TRUE (r0.contains_p (neg_nan));
3388 : :
3389 : : // Clearing the NAN on a [] NAN is the empty set.
3390 : 4 : r0.set_nan (float_type_node);
3391 : 4 : r0.clear_nan ();
3392 : 4 : ASSERT_TRUE (r0.undefined_p ());
3393 : :
3394 : : // [10,20] NAN ^ [21,25] NAN = [NAN]
3395 : 4 : r0 = frange_float ("10", "20");
3396 : 4 : r0.update_nan ();
3397 : 4 : r1 = frange_float ("21", "25");
3398 : 4 : r1.update_nan ();
3399 : 4 : r0.intersect (r1);
3400 : 4 : ASSERT_TRUE (r0.known_isnan ());
3401 : :
3402 : : // NAN U [5,6] should be [5,6] +-NAN.
3403 : 4 : r0.set_nan (float_type_node);
3404 : 4 : r1 = frange_float ("5", "6");
3405 : 4 : r1.clear_nan ();
3406 : 4 : r0.union_ (r1);
3407 : 4 : real_from_string (&q, "5");
3408 : 4 : real_from_string (&r, "6");
3409 : 4 : ASSERT_TRUE (real_identical (&q, &r0.lower_bound ()));
3410 : 4 : ASSERT_TRUE (real_identical (&r, &r0.upper_bound ()));
3411 : 4 : ASSERT_TRUE (!r0.signbit_p (signbit));
3412 : 8 : ASSERT_TRUE (r0.maybe_isnan ());
3413 : :
3414 : : // NAN U NAN shouldn't change anything.
3415 : 4 : r0.set_nan (float_type_node);
3416 : 4 : r1.set_nan (float_type_node);
3417 : 4 : ASSERT_FALSE (r0.union_ (r1));
3418 : :
3419 : : // [3,5] NAN U NAN shouldn't change anything.
3420 : 4 : r0 = frange_float ("3", "5");
3421 : 4 : r1.set_nan (float_type_node);
3422 : 4 : ASSERT_FALSE (r0.union_ (r1));
3423 : :
3424 : : // [3,5] U NAN *does* trigger a change.
3425 : 4 : r0 = frange_float ("3", "5");
3426 : 4 : r0.clear_nan ();
3427 : 4 : r1.set_nan (float_type_node);
3428 : 4 : ASSERT_TRUE (r0.union_ (r1));
3429 : 4 : }
3430 : :
3431 : : static void
3432 : 8 : range_tests_signed_zeros ()
3433 : : {
3434 : 8 : REAL_VALUE_TYPE zero = dconst0;
3435 : 8 : REAL_VALUE_TYPE neg_zero = zero;
3436 : 8 : neg_zero.sign = 1;
3437 : 8 : frange r0, r1;
3438 : 8 : bool signbit;
3439 : :
3440 : : // [0,0] contains [0,0] but not [-0,-0] and vice versa.
3441 : 8 : r0 = frange_float ("0.0", "0.0");
3442 : 8 : r1 = frange_float ("-0.0", "-0.0");
3443 : 8 : ASSERT_TRUE (r0.contains_p (zero));
3444 : 8 : ASSERT_TRUE (!r0.contains_p (neg_zero));
3445 : 8 : ASSERT_TRUE (r1.contains_p (neg_zero));
3446 : 8 : ASSERT_TRUE (!r1.contains_p (zero));
3447 : :
3448 : : // Test contains_p() when we know the sign of the zero.
3449 : 8 : r0 = frange_float ("0.0", "0.0");
3450 : 8 : ASSERT_TRUE (r0.contains_p (zero));
3451 : 8 : ASSERT_FALSE (r0.contains_p (neg_zero));
3452 : 8 : r0 = frange_float ("-0.0", "-0.0");
3453 : 8 : ASSERT_TRUE (r0.contains_p (neg_zero));
3454 : 8 : ASSERT_FALSE (r0.contains_p (zero));
3455 : :
3456 : 8 : r0 = frange_float ("-0.0", "0.0");
3457 : 8 : ASSERT_TRUE (r0.contains_p (neg_zero));
3458 : 8 : ASSERT_TRUE (r0.contains_p (zero));
3459 : :
3460 : 8 : r0 = frange_float ("-3", "5");
3461 : 8 : ASSERT_TRUE (r0.contains_p (neg_zero));
3462 : 8 : ASSERT_TRUE (r0.contains_p (zero));
3463 : :
3464 : : // The intersection of zeros that differ in sign is a NAN (or
3465 : : // undefined if not honoring NANs).
3466 : 8 : r0 = frange_float ("-0.0", "-0.0");
3467 : 8 : r1 = frange_float ("0.0", "0.0");
3468 : 8 : r0.intersect (r1);
3469 : 8 : if (HONOR_NANS (float_type_node))
3470 : 4 : ASSERT_TRUE (r0.known_isnan ());
3471 : : else
3472 : 4 : ASSERT_TRUE (r0.undefined_p ());
3473 : :
3474 : : // The union of zeros that differ in sign is a zero with unknown sign.
3475 : 8 : r0 = frange_float ("0.0", "0.0");
3476 : 8 : r1 = frange_float ("-0.0", "-0.0");
3477 : 8 : r0.union_ (r1);
3478 : 8 : ASSERT_TRUE (r0.zero_p () && !r0.signbit_p (signbit));
3479 : :
3480 : : // [-0, +0] has an unknown sign.
3481 : 8 : r0 = frange_float ("-0.0", "0.0");
3482 : 8 : ASSERT_TRUE (r0.zero_p () && !r0.signbit_p (signbit));
3483 : :
3484 : : // [-0, +0] ^ [0, 0] is [0, 0]
3485 : 8 : r0 = frange_float ("-0.0", "0.0");
3486 : 8 : r1 = frange_float ("0.0", "0.0");
3487 : 8 : r0.intersect (r1);
3488 : 8 : ASSERT_TRUE (r0.zero_p ());
3489 : :
3490 : 8 : r0 = frange_float ("+0", "5");
3491 : 8 : r0.clear_nan ();
3492 : 8 : ASSERT_TRUE (r0.signbit_p (signbit) && !signbit);
3493 : :
3494 : 8 : r0 = frange_float ("-0", "5");
3495 : 8 : r0.clear_nan ();
3496 : 8 : ASSERT_TRUE (!r0.signbit_p (signbit));
3497 : :
3498 : 8 : r0 = frange_float ("-0", "10");
3499 : 8 : r1 = frange_float ("0", "5");
3500 : 8 : r0.intersect (r1);
3501 : 8 : ASSERT_TRUE (real_iszero (&r0.lower_bound (), false));
3502 : :
3503 : 8 : r0 = frange_float ("-0", "5");
3504 : 8 : r1 = frange_float ("0", "5");
3505 : 8 : r0.union_ (r1);
3506 : 8 : ASSERT_TRUE (real_iszero (&r0.lower_bound (), true));
3507 : :
3508 : 8 : r0 = frange_float ("-5", "-0");
3509 : 8 : r0.update_nan ();
3510 : 8 : r1 = frange_float ("0", "0");
3511 : 8 : r1.update_nan ();
3512 : 8 : r0.intersect (r1);
3513 : 8 : if (HONOR_NANS (float_type_node))
3514 : 4 : ASSERT_TRUE (r0.known_isnan ());
3515 : : else
3516 : 4 : ASSERT_TRUE (r0.undefined_p ());
3517 : :
3518 : 8 : r0.set_nonnegative (float_type_node);
3519 : 8 : if (HONOR_NANS (float_type_node))
3520 : 8 : ASSERT_TRUE (r0.maybe_isnan ());
3521 : :
3522 : : // Numbers containing zero should have an unknown SIGNBIT.
3523 : 8 : r0 = frange_float ("0", "10");
3524 : 8 : r0.clear_nan ();
3525 : 8 : ASSERT_TRUE (r0.signbit_p (signbit) && !signbit);
3526 : 8 : }
3527 : :
3528 : : static void
3529 : 8 : range_tests_signbit ()
3530 : : {
3531 : 8 : frange r0, r1;
3532 : 8 : bool signbit;
3533 : :
3534 : : // Negative numbers should have the SIGNBIT set.
3535 : 8 : r0 = frange_float ("-5", "-1");
3536 : 8 : r0.clear_nan ();
3537 : 8 : ASSERT_TRUE (r0.signbit_p (signbit) && signbit);
3538 : : // Positive numbers should have the SIGNBIT clear.
3539 : 8 : r0 = frange_float ("1", "10");
3540 : 8 : r0.clear_nan ();
3541 : 8 : ASSERT_TRUE (r0.signbit_p (signbit) && !signbit);
3542 : : // Numbers spanning both positive and negative should have an
3543 : : // unknown SIGNBIT.
3544 : 8 : r0 = frange_float ("-10", "10");
3545 : 8 : r0.clear_nan ();
3546 : 8 : ASSERT_TRUE (!r0.signbit_p (signbit));
3547 : 8 : r0.set_varying (float_type_node);
3548 : 8 : ASSERT_TRUE (!r0.signbit_p (signbit));
3549 : 8 : }
3550 : :
3551 : : static void
3552 : 8 : range_tests_floats ()
3553 : : {
3554 : 8 : frange r0, r1;
3555 : :
3556 : 8 : if (HONOR_NANS (float_type_node))
3557 : 4 : range_tests_nan ();
3558 : 8 : range_tests_signbit ();
3559 : :
3560 : 8 : if (HONOR_SIGNED_ZEROS (float_type_node))
3561 : 8 : range_tests_signed_zeros ();
3562 : :
3563 : : // A range of [-INF,+INF] is actually VARYING if no other properties
3564 : : // are set.
3565 : 8 : r0 = frange_float ("-Inf", "+Inf");
3566 : 8 : ASSERT_TRUE (r0.varying_p ());
3567 : : // ...unless it has some special property...
3568 : 8 : if (HONOR_NANS (r0.type ()))
3569 : : {
3570 : 4 : r0.clear_nan ();
3571 : 4 : ASSERT_FALSE (r0.varying_p ());
3572 : : }
3573 : :
3574 : : // For most architectures, where float and double are different
3575 : : // sizes, having the same endpoints does not necessarily mean the
3576 : : // ranges are equal.
3577 : 8 : if (!types_compatible_p (float_type_node, double_type_node))
3578 : : {
3579 : 8 : r0 = frange_float ("3.0", "3.0", float_type_node);
3580 : 8 : r1 = frange_float ("3.0", "3.0", double_type_node);
3581 : 8 : ASSERT_NE (r0, r1);
3582 : : }
3583 : :
3584 : : // [3,5] U [10,12] = [3,12].
3585 : 8 : r0 = frange_float ("3", "5");
3586 : 8 : r1 = frange_float ("10", "12");
3587 : 8 : r0.union_ (r1);
3588 : 8 : ASSERT_EQ (r0, frange_float ("3", "12"));
3589 : :
3590 : : // [5,10] U [4,8] = [4,10]
3591 : 8 : r0 = frange_float ("5", "10");
3592 : 8 : r1 = frange_float ("4", "8");
3593 : 8 : r0.union_ (r1);
3594 : 8 : ASSERT_EQ (r0, frange_float ("4", "10"));
3595 : :
3596 : : // [3,5] U [4,10] = [3,10]
3597 : 8 : r0 = frange_float ("3", "5");
3598 : 8 : r1 = frange_float ("4", "10");
3599 : 8 : r0.union_ (r1);
3600 : 8 : ASSERT_EQ (r0, frange_float ("3", "10"));
3601 : :
3602 : : // [4,10] U [5,11] = [4,11]
3603 : 8 : r0 = frange_float ("4", "10");
3604 : 8 : r1 = frange_float ("5", "11");
3605 : 8 : r0.union_ (r1);
3606 : 8 : ASSERT_EQ (r0, frange_float ("4", "11"));
3607 : :
3608 : : // [3,12] ^ [10,12] = [10,12].
3609 : 8 : r0 = frange_float ("3", "12");
3610 : 8 : r1 = frange_float ("10", "12");
3611 : 8 : r0.intersect (r1);
3612 : 8 : ASSERT_EQ (r0, frange_float ("10", "12"));
3613 : :
3614 : : // [10,12] ^ [11,11] = [11,11]
3615 : 8 : r0 = frange_float ("10", "12");
3616 : 8 : r1 = frange_float ("11", "11");
3617 : 8 : r0.intersect (r1);
3618 : 8 : ASSERT_EQ (r0, frange_float ("11", "11"));
3619 : :
3620 : : // [10,20] ^ [5,15] = [10,15]
3621 : 8 : r0 = frange_float ("10", "20");
3622 : 8 : r1 = frange_float ("5", "15");
3623 : 8 : r0.intersect (r1);
3624 : 8 : ASSERT_EQ (r0, frange_float ("10", "15"));
3625 : :
3626 : : // [10,20] ^ [15,25] = [15,20]
3627 : 8 : r0 = frange_float ("10", "20");
3628 : 8 : r1 = frange_float ("15", "25");
3629 : 8 : r0.intersect (r1);
3630 : 8 : ASSERT_EQ (r0, frange_float ("15", "20"));
3631 : :
3632 : : // [10,20] ^ [21,25] = []
3633 : 8 : r0 = frange_float ("10", "20");
3634 : 8 : r0.clear_nan ();
3635 : 8 : r1 = frange_float ("21", "25");
3636 : 8 : r1.clear_nan ();
3637 : 8 : r0.intersect (r1);
3638 : 8 : ASSERT_TRUE (r0.undefined_p ());
3639 : :
3640 : 8 : if (HONOR_INFINITIES (float_type_node))
3641 : : {
3642 : : // Make sure [-Inf, -Inf] doesn't get normalized.
3643 : 4 : r0 = frange_float ("-Inf", "-Inf");
3644 : 4 : ASSERT_TRUE (real_isinf (&r0.lower_bound (), true));
3645 : 4 : ASSERT_TRUE (real_isinf (&r0.upper_bound (), true));
3646 : : }
3647 : :
3648 : : // Test that reading back a global range yields the same result as
3649 : : // what we wrote into it.
3650 : 8 : tree ssa = make_temp_ssa_name (float_type_node, NULL, "blah");
3651 : 8 : r0.set_varying (float_type_node);
3652 : 8 : r0.clear_nan ();
3653 : 8 : set_range_info (ssa, r0);
3654 : 8 : get_global_range_query ()->range_of_expr (r1, ssa);
3655 : 8 : ASSERT_EQ (r0, r1);
3656 : 8 : }
3657 : :
3658 : : // Run floating range tests for various combinations of NAN and INF
3659 : : // support.
3660 : :
3661 : : static void
3662 : 4 : range_tests_floats_various ()
3663 : : {
3664 : 4 : int save_finite_math_only = flag_finite_math_only;
3665 : :
3666 : : // Test -ffinite-math-only.
3667 : 4 : flag_finite_math_only = 1;
3668 : 4 : range_tests_floats ();
3669 : : // Test -fno-finite-math-only.
3670 : 4 : flag_finite_math_only = 0;
3671 : 4 : range_tests_floats ();
3672 : :
3673 : 4 : flag_finite_math_only = save_finite_math_only;
3674 : 4 : }
3675 : :
3676 : : void
3677 : 4 : range_tests ()
3678 : : {
3679 : 4 : range_tests_irange3 ();
3680 : 4 : range_tests_int_range_max ();
3681 : 4 : range_tests_strict_enum ();
3682 : 4 : range_tests_nonzero_bits ();
3683 : 4 : range_tests_floats_various ();
3684 : 4 : range_tests_misc ();
3685 : 4 : }
3686 : :
3687 : : } // namespace selftest
3688 : :
3689 : : #endif // CHECKING_P
|
