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 : 968704803 : irange_bitmask::irange_bitmask (tree type,
38 : 968704803 : const wide_int &min, const wide_int &max)
39 : : {
40 : 968704803 : unsigned prec = TYPE_PRECISION (type);
41 : : // All the bits of a singleton are known.
42 : 968704803 : if (min == max)
43 : : {
44 : 129941803 : m_mask = wi::zero (prec);
45 : 129941803 : m_value = min;
46 : : }
47 : : else
48 : : {
49 : 838763000 : wide_int xorv = min ^ max;
50 : : // Mask will have leading zeros for all leading bits that are
51 : : // common, both zeros and ones.
52 : 838763000 : 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 : 838770936 : m_value = ~m_mask & min;
55 : 838763000 : }
56 : 968704803 : }
57 : :
58 : : void
59 : 8176 : irange::accept (const vrange_visitor &v) const
60 : : {
61 : 8176 : v.visit (*this);
62 : 8176 : }
63 : :
64 : : void
65 : 7383 : value_range::dump (FILE *out) const
66 : : {
67 : 7383 : if (m_vrange)
68 : 7383 : m_vrange->dump (out);
69 : : else
70 : 0 : fprintf (out, "NULL");
71 : 7383 : }
72 : :
73 : : DEBUG_FUNCTION void
74 : 0 : debug (const value_range &r)
75 : : {
76 : 0 : r.dump (stderr);
77 : 0 : fprintf (stderr, "\n");
78 : 0 : }
79 : :
80 : : DEBUG_FUNCTION void
81 : 0 : debug (const irange_bitmask &bm)
82 : : {
83 : 0 : bm.dump (stderr);
84 : 0 : fprintf (stderr, "\n");
85 : 0 : }
86 : :
87 : : // Definitions for unsupported_range.
88 : :
89 : : void
90 : 720 : unsupported_range::accept (const vrange_visitor &v) const
91 : : {
92 : 720 : v.visit (*this);
93 : 720 : }
94 : :
95 : : void
96 : 0 : vrange::update_bitmask (const class irange_bitmask &)
97 : : {
98 : 0 : }
99 : :
100 : : irange_bitmask
101 : 0 : vrange::get_bitmask () const
102 : : {
103 : : // Return all unknown bits for the given precision.
104 : 0 : return irange_bitmask (TYPE_PRECISION (type ()));
105 : : }
106 : :
107 : : bool
108 : 0 : unsupported_range::contains_p (tree) const
109 : : {
110 : 0 : return varying_p ();
111 : : }
112 : :
113 : : bool
114 : 1203658 : unsupported_range::singleton_p (tree *) const
115 : : {
116 : 1203658 : return false;
117 : : }
118 : :
119 : : void
120 : 0 : unsupported_range::set (tree min, tree, value_range_kind)
121 : : {
122 : 0 : set_varying (TREE_TYPE (min));
123 : 0 : }
124 : :
125 : : tree
126 : 0 : unsupported_range::type () const
127 : : {
128 : 0 : return void_type_node;
129 : : }
130 : :
131 : : bool
132 : 0 : unsupported_range::supports_type_p (const_tree) const
133 : : {
134 : 0 : return false;
135 : : }
136 : :
137 : : void
138 : 114975396 : unsupported_range::set_undefined ()
139 : : {
140 : 114975396 : m_kind = VR_UNDEFINED;
141 : 114975396 : }
142 : :
143 : : void
144 : 3449641 : unsupported_range::set_varying (tree)
145 : : {
146 : 3449641 : m_kind = VR_VARYING;
147 : 3449641 : }
148 : :
149 : : bool
150 : 0 : unsupported_range::union_ (const vrange &v)
151 : : {
152 : 0 : const unsupported_range &r = as_a <unsupported_range> (v);
153 : :
154 : 0 : if (r.undefined_p () || varying_p ())
155 : : return false;
156 : 0 : if (undefined_p () || r.varying_p ())
157 : : {
158 : 0 : operator= (r);
159 : 0 : return true;
160 : : }
161 : 0 : gcc_unreachable ();
162 : : return false;
163 : : }
164 : :
165 : : bool
166 : 0 : unsupported_range::intersect (const vrange &v)
167 : : {
168 : 0 : const unsupported_range &r = as_a <unsupported_range> (v);
169 : :
170 : 0 : if (undefined_p () || r.varying_p ())
171 : : return false;
172 : 0 : if (r.undefined_p ())
173 : : {
174 : 0 : set_undefined ();
175 : 0 : return true;
176 : : }
177 : 0 : if (varying_p ())
178 : : {
179 : 0 : operator= (r);
180 : 0 : return true;
181 : : }
182 : 0 : gcc_unreachable ();
183 : : return false;
184 : : }
185 : :
186 : : bool
187 : 0 : unsupported_range::zero_p () const
188 : : {
189 : 0 : return false;
190 : : }
191 : :
192 : : bool
193 : 0 : unsupported_range::nonzero_p () const
194 : : {
195 : 0 : return false;
196 : : }
197 : :
198 : : void
199 : 0 : unsupported_range::set_nonzero (tree type)
200 : : {
201 : 0 : set_varying (type);
202 : 0 : }
203 : :
204 : : void
205 : 0 : unsupported_range::set_zero (tree type)
206 : : {
207 : 0 : set_varying (type);
208 : 0 : }
209 : :
210 : : void
211 : 0 : unsupported_range::set_nonnegative (tree type)
212 : : {
213 : 0 : set_varying (type);
214 : 0 : }
215 : :
216 : : bool
217 : 0 : unsupported_range::fits_p (const vrange &) const
218 : : {
219 : 0 : return true;
220 : : }
221 : :
222 : : unsupported_range &
223 : 913422 : unsupported_range::operator= (const unsupported_range &r)
224 : : {
225 : 913422 : if (r.undefined_p ())
226 : 913422 : set_undefined ();
227 : 0 : else if (r.varying_p ())
228 : 0 : set_varying (void_type_node);
229 : : else
230 : 0 : gcc_unreachable ();
231 : 913422 : return *this;
232 : : }
233 : :
234 : : tree
235 : 0 : unsupported_range::lbound () const
236 : : {
237 : 0 : return NULL;
238 : : }
239 : :
240 : : tree
241 : 0 : unsupported_range::ubound () const
242 : : {
243 : 0 : return NULL;
244 : : }
245 : :
246 : : // Assignment operator for generic ranges. Copying incompatible types
247 : : // is not allowed.
248 : :
249 : : vrange &
250 : 10197226 : vrange::operator= (const vrange &src)
251 : : {
252 : 10197226 : if (is_a <irange> (src))
253 : 8943238 : as_a <irange> (*this) = as_a <irange> (src);
254 : 1253988 : else if (is_a <prange> (src))
255 : 1001184 : as_a <prange> (*this) = as_a <prange> (src);
256 : 252804 : else if (is_a <frange> (src))
257 : 252804 : as_a <frange> (*this) = as_a <frange> (src);
258 : : else
259 : : {
260 : 0 : gcc_checking_assert (is_a <unsupported_range> (src));
261 : 0 : m_kind = src.m_kind;
262 : : }
263 : 10197226 : return *this;
264 : : }
265 : :
266 : : // Equality operator for generic ranges.
267 : :
268 : : bool
269 : 33548896 : vrange::operator== (const vrange &src) const
270 : : {
271 : 33548896 : if (is_a <irange> (src))
272 : 28570501 : return as_a <irange> (*this) == as_a <irange> (src);
273 : 4978395 : if (is_a <prange> (src))
274 : 4934462 : return as_a <prange> (*this) == as_a <prange> (src);
275 : 43933 : if (is_a <frange> (src))
276 : 43933 : return as_a <frange> (*this) == as_a <frange> (src);
277 : 0 : gcc_unreachable ();
278 : : }
279 : :
280 : : // Wrapper for vrange_printer to dump a range to a file.
281 : :
282 : : void
283 : 7480 : vrange::dump (FILE *file) const
284 : : {
285 : 7480 : pretty_printer pp;
286 : 7480 : pp_needs_newline (&pp) = true;
287 : 7480 : pp.set_output_stream (file);
288 : 7480 : vrange_printer vrange_pp (&pp);
289 : 7480 : this->accept (vrange_pp);
290 : 7480 : pp_flush (&pp);
291 : 7480 : }
292 : :
293 : : void
294 : 0 : irange_bitmask::dump (FILE *file) const
295 : : {
296 : 0 : char buf[WIDE_INT_PRINT_BUFFER_SIZE], *p;
297 : 0 : pretty_printer pp;
298 : :
299 : 0 : pp_needs_newline (&pp) = true;
300 : 0 : pp.set_output_stream (file);
301 : 0 : pp_string (&pp, "MASK ");
302 : 0 : unsigned len_mask, len_val;
303 : 0 : if (print_hex_buf_size (m_mask, &len_mask)
304 : 0 : | print_hex_buf_size (m_value, &len_val))
305 : 0 : p = XALLOCAVEC (char, MAX (len_mask, len_val));
306 : : else
307 : : p = buf;
308 : 0 : print_hex (m_mask, p);
309 : 0 : pp_string (&pp, p);
310 : 0 : pp_string (&pp, " VALUE ");
311 : 0 : print_hex (m_value, p);
312 : 0 : pp_string (&pp, p);
313 : 0 : pp_flush (&pp);
314 : 0 : }
315 : :
316 : : namespace inchash
317 : : {
318 : :
319 : : void
320 : 22606196 : add_vrange (const vrange &v, inchash::hash &hstate,
321 : : unsigned int)
322 : : {
323 : 22606196 : if (v.undefined_p ())
324 : : {
325 : 0 : hstate.add_int (VR_UNDEFINED);
326 : 0 : return;
327 : : }
328 : : // Types are ignored throughout to inhibit two ranges being equal
329 : : // but having different hash values. This can happen when two
330 : : // ranges are equal and their types are different (but
331 : : // types_compatible_p is true).
332 : 22606196 : if (is_a <irange> (v))
333 : : {
334 : 16076029 : const irange &r = as_a <irange> (v);
335 : 16076029 : if (r.varying_p ())
336 : 0 : hstate.add_int (VR_VARYING);
337 : : else
338 : 16076029 : hstate.add_int (VR_RANGE);
339 : 35066165 : for (unsigned i = 0; i < r.num_pairs (); ++i)
340 : : {
341 : 18990136 : hstate.add_wide_int (r.lower_bound (i));
342 : 18990233 : hstate.add_wide_int (r.upper_bound (i));
343 : : }
344 : 16076029 : irange_bitmask bm = r.get_bitmask ();
345 : 16076029 : hstate.add_wide_int (bm.value ());
346 : 16076029 : hstate.add_wide_int (bm.mask ());
347 : 16076029 : return;
348 : 16076029 : }
349 : 6530167 : if (is_a <prange> (v))
350 : : {
351 : 6444258 : const prange &r = as_a <prange> (v);
352 : 6444258 : if (r.varying_p ())
353 : 0 : hstate.add_int (VR_VARYING);
354 : : else
355 : : {
356 : 6444258 : hstate.add_int (VR_RANGE);
357 : 6444258 : hstate.add_wide_int (r.lower_bound ());
358 : 6444258 : hstate.add_wide_int (r.upper_bound ());
359 : 6444258 : irange_bitmask bm = r.get_bitmask ();
360 : 6444258 : hstate.add_wide_int (bm.value ());
361 : 6444258 : hstate.add_wide_int (bm.mask ());
362 : 6444258 : }
363 : 6444258 : return;
364 : : }
365 : 85909 : if (is_a <frange> (v))
366 : : {
367 : 85909 : const frange &r = as_a <frange> (v);
368 : 85909 : if (r.known_isnan ())
369 : 258 : hstate.add_int (VR_NAN);
370 : : else
371 : : {
372 : 85651 : hstate.add_int (r.varying_p () ? VR_VARYING : VR_RANGE);
373 : 85651 : hstate.add_real_value (r.lower_bound ());
374 : 85651 : hstate.add_real_value (r.upper_bound ());
375 : : }
376 : 85909 : nan_state nan = r.get_nan_state ();
377 : 85909 : hstate.add_int (nan.pos_p ());
378 : 85909 : hstate.add_int (nan.neg_p ());
379 : 85909 : return;
380 : : }
381 : 0 : gcc_unreachable ();
382 : : }
383 : :
384 : : } //namespace inchash
385 : :
386 : : bool
387 : 36529 : irange::nonnegative_p () const
388 : : {
389 : 36529 : return wi::ge_p (lower_bound (), 0, TYPE_SIGN (type ()));
390 : : }
391 : :
392 : : bool
393 : 31161 : irange::nonpositive_p () const
394 : : {
395 : 31161 : return wi::le_p (upper_bound (), 0, TYPE_SIGN (type ()));
396 : : }
397 : :
398 : : bool
399 : 398585518 : irange::supports_type_p (const_tree type) const
400 : : {
401 : 398585518 : return supports_p (type);
402 : : }
403 : :
404 : : // Return TRUE if R fits in THIS.
405 : :
406 : : bool
407 : 0 : irange::fits_p (const vrange &r) const
408 : : {
409 : 0 : return m_max_ranges >= as_a <irange> (r).num_pairs ();
410 : : }
411 : :
412 : : void
413 : 37269347 : irange::set_nonnegative (tree type)
414 : : {
415 : 37269347 : set (type,
416 : 74538694 : wi::zero (TYPE_PRECISION (type)),
417 : 37269347 : wi::to_wide (TYPE_MAX_VALUE (type)));
418 : 37269347 : }
419 : :
420 : : // Prange implementation.
421 : :
422 : : void
423 : 1279 : prange::accept (const vrange_visitor &v) const
424 : : {
425 : 1279 : v.visit (*this);
426 : 1279 : }
427 : :
428 : : void
429 : 0 : prange::set_nonnegative (tree type)
430 : : {
431 : 0 : set (type,
432 : 0 : wi::zero (TYPE_PRECISION (type)),
433 : 0 : wi::max_value (TYPE_PRECISION (type), UNSIGNED));
434 : 0 : }
435 : :
436 : : void
437 : 13555669 : prange::set (tree min, tree max, value_range_kind kind)
438 : : {
439 : 13555669 : return set (TREE_TYPE (min), wi::to_wide (min), wi::to_wide (max), kind);
440 : : }
441 : :
442 : : void
443 : 38533553 : prange::set (tree type, const wide_int &min, const wide_int &max,
444 : : value_range_kind kind)
445 : : {
446 : 38533553 : if (kind == VR_UNDEFINED)
447 : : {
448 : 0 : set_undefined ();
449 : 0 : return;
450 : : }
451 : 38533553 : if (kind == VR_VARYING)
452 : : {
453 : 0 : set_varying (type);
454 : 0 : return;
455 : : }
456 : 38533553 : if (kind == VR_ANTI_RANGE)
457 : : {
458 : 0 : gcc_checking_assert (min == 0 && max == 0);
459 : 0 : set_nonzero (type);
460 : 0 : return;
461 : : }
462 : 38533553 : m_type = type;
463 : 38533553 : m_min = min;
464 : 38533553 : m_max = max;
465 : 38533553 : if (m_min == 0 && m_max == -1)
466 : : {
467 : 4709358 : m_kind = VR_VARYING;
468 : 4709358 : m_bitmask.set_unknown (TYPE_PRECISION (type));
469 : 4709358 : if (flag_checking)
470 : 4709358 : verify_range ();
471 : 4709358 : return;
472 : : }
473 : :
474 : 33824195 : m_kind = VR_RANGE;
475 : 33824195 : m_bitmask = irange_bitmask (type, min, max);
476 : 33824195 : if (flag_checking)
477 : 33824183 : verify_range ();
478 : : }
479 : :
480 : : bool
481 : 2878298 : prange::contains_p (const wide_int &w) const
482 : : {
483 : 2878298 : if (undefined_p ())
484 : : return false;
485 : :
486 : 2878298 : if (varying_p ())
487 : : return true;
488 : :
489 : 4424794 : return (wi::le_p (lower_bound (), w, UNSIGNED)
490 : 2213914 : && wi::ge_p (upper_bound (), w, UNSIGNED));
491 : : }
492 : :
493 : : bool
494 : 213744682 : prange::singleton_p (tree *result) const
495 : : {
496 : 304719365 : if (m_kind == VR_RANGE && lower_bound () == upper_bound ())
497 : : {
498 : 240994 : if (result)
499 : 88403 : *result = wide_int_to_tree (type (), m_min);
500 : 240994 : return true;
501 : : }
502 : : return false;
503 : : }
504 : :
505 : : tree
506 : 4676027 : prange::lbound () const
507 : : {
508 : 4676027 : return wide_int_to_tree (type (), m_min);
509 : : }
510 : :
511 : : tree
512 : 770004 : prange::ubound () const
513 : : {
514 : 770004 : return wide_int_to_tree (type (), m_max);
515 : : }
516 : :
517 : : bool
518 : 16767773 : prange::union_ (const vrange &v)
519 : : {
520 : 16767773 : const prange &r = as_a <prange> (v);
521 : :
522 : 16767773 : if (r.undefined_p ())
523 : : return false;
524 : 16567475 : if (undefined_p ())
525 : : {
526 : 8474539 : *this = r;
527 : 8474539 : if (flag_checking)
528 : 8474539 : verify_range ();
529 : 8474539 : return true;
530 : : }
531 : 8092936 : if (varying_p ())
532 : : return false;
533 : 4260517 : if (r.varying_p ())
534 : : {
535 : 1219929 : set_varying (type ());
536 : 1219929 : return true;
537 : : }
538 : :
539 : 3040588 : wide_int new_lb = wi::min (r.lower_bound (), lower_bound (), UNSIGNED);
540 : 3040588 : wide_int new_ub = wi::max (r.upper_bound (), upper_bound (), UNSIGNED);
541 : 3040588 : prange new_range (type (), new_lb, new_ub);
542 : 3040588 : new_range.m_bitmask.union_ (m_bitmask);
543 : 3040588 : new_range.m_bitmask.union_ (r.m_bitmask);
544 : 3040588 : if (new_range.varying_compatible_p ())
545 : : {
546 : 319025 : set_varying (type ());
547 : 319025 : return true;
548 : : }
549 : 2721563 : if (flag_checking)
550 : 2721563 : new_range.verify_range ();
551 : 2721563 : if (new_range == *this)
552 : : return false;
553 : 48405 : *this = new_range;
554 : 48405 : return true;
555 : 3040588 : }
556 : :
557 : : bool
558 : 185228691 : prange::intersect (const vrange &v)
559 : : {
560 : 185228691 : const prange &r = as_a <prange> (v);
561 : 185228691 : gcc_checking_assert (undefined_p () || r.undefined_p ()
562 : : || range_compatible_p (type (), r.type ()));
563 : :
564 : 185228691 : if (undefined_p ())
565 : : return false;
566 : 185122143 : if (r.undefined_p ())
567 : : {
568 : 22376 : set_undefined ();
569 : 22376 : return true;
570 : : }
571 : 185099767 : if (r.varying_p ())
572 : : return false;
573 : 100170041 : if (varying_p ())
574 : : {
575 : 46127597 : *this = r;
576 : 46127597 : return true;
577 : : }
578 : :
579 : 54042444 : prange save = *this;
580 : 54042444 : m_min = wi::max (r.lower_bound (), lower_bound (), UNSIGNED);
581 : 54042444 : m_max = wi::min (r.upper_bound (), upper_bound (), UNSIGNED);
582 : 54042444 : if (wi::gt_p (m_min, m_max, UNSIGNED))
583 : : {
584 : 352364 : set_undefined ();
585 : 352364 : return true;
586 : : }
587 : :
588 : : // Intersect all bitmasks: the old one, the new one, and the other operand's.
589 : 53690080 : irange_bitmask new_bitmask (m_type, m_min, m_max);
590 : 53690080 : m_bitmask.intersect (new_bitmask);
591 : 53690080 : m_bitmask.intersect (r.m_bitmask);
592 : 53690080 : if (varying_compatible_p ())
593 : : {
594 : 4 : set_varying (type ());
595 : 4 : return true;
596 : : }
597 : :
598 : 53690076 : if (flag_checking)
599 : 53689974 : verify_range ();
600 : 53690076 : if (*this == save)
601 : : return false;
602 : : return true;
603 : 54042444 : }
604 : :
605 : : prange &
606 : 178890995 : prange::operator= (const prange &src)
607 : : {
608 : 178890995 : m_type = src.m_type;
609 : 178890995 : m_kind = src.m_kind;
610 : 178890995 : m_min = src.m_min;
611 : 178890995 : m_max = src.m_max;
612 : 178890995 : m_bitmask = src.m_bitmask;
613 : 178890995 : if (flag_checking)
614 : 178890863 : verify_range ();
615 : 178890995 : return *this;
616 : : }
617 : :
618 : : bool
619 : 66423368 : prange::operator== (const prange &src) const
620 : : {
621 : 66423368 : if (m_kind == src.m_kind)
622 : : {
623 : 65825128 : if (undefined_p ())
624 : : return true;
625 : :
626 : 65815504 : if (varying_p ())
627 : 961906 : return types_compatible_p (type (), src.type ());
628 : :
629 : 128822713 : return (m_min == src.m_min && m_max == src.m_max
630 : 128471629 : && m_bitmask == src.m_bitmask);
631 : : }
632 : : return false;
633 : : }
634 : :
635 : : void
636 : 2538344 : prange::invert ()
637 : : {
638 : 2538344 : gcc_checking_assert (!undefined_p () && !varying_p ());
639 : :
640 : 2538344 : wide_int new_lb, new_ub;
641 : 2538344 : unsigned prec = TYPE_PRECISION (type ());
642 : 2538344 : wide_int type_min = wi::zero (prec);
643 : 2538344 : wide_int type_max = wi::max_value (prec, UNSIGNED);
644 : 2538344 : wi::overflow_type ovf;
645 : :
646 : 2538344 : if (lower_bound () == type_min)
647 : : {
648 : 2531737 : new_lb = wi::add (upper_bound (), 1, UNSIGNED, &ovf);
649 : 2531737 : if (ovf)
650 : 0 : new_lb = type_min;
651 : 2531737 : new_ub = type_max;
652 : 2531737 : set (type (), new_lb, new_ub);
653 : : }
654 : 6607 : else if (upper_bound () == type_max)
655 : : {
656 : 2720 : wi::overflow_type ovf;
657 : 2720 : new_lb = type_min;
658 : 2720 : new_ub = wi::sub (lower_bound (), 1, UNSIGNED, &ovf);
659 : 2720 : if (ovf)
660 : 0 : new_ub = type_max;
661 : 2720 : set (type (), new_lb, new_ub);
662 : : }
663 : : else
664 : 3887 : set_varying (type ());
665 : 2538344 : }
666 : :
667 : : void
668 : 943514955 : prange::verify_range () const
669 : : {
670 : 943514955 : gcc_checking_assert (m_discriminator == VR_PRANGE);
671 : :
672 : 943514955 : if (m_kind == VR_UNDEFINED)
673 : : return;
674 : :
675 : 943459586 : gcc_checking_assert (supports_p (type ()));
676 : :
677 : 943459586 : if (m_kind == VR_VARYING)
678 : : {
679 : 458558453 : gcc_checking_assert (varying_compatible_p ());
680 : : return;
681 : : }
682 : 484901133 : gcc_checking_assert (!varying_compatible_p ());
683 : 484901133 : gcc_checking_assert (m_kind == VR_RANGE);
684 : : }
685 : :
686 : : void
687 : 28484598 : prange::update_bitmask (const irange_bitmask &bm)
688 : : {
689 : 28484598 : gcc_checking_assert (!undefined_p ());
690 : :
691 : : // If all the bits are known, this is a singleton.
692 : 28484598 : if (bm.mask () == 0)
693 : : {
694 : 147880 : set (type (), bm.value (), bm.value ());
695 : 147880 : return;
696 : : }
697 : :
698 : : // Drop VARYINGs with known bits to a plain range.
699 : 35465752 : if (m_kind == VR_VARYING && !bm.unknown_p ())
700 : 194084 : m_kind = VR_RANGE;
701 : :
702 : 28336718 : m_bitmask = bm;
703 : 28336718 : if (varying_compatible_p ())
704 : 6934950 : m_kind = VR_VARYING;
705 : :
706 : 28336718 : if (flag_checking)
707 : 28336718 : verify_range ();
708 : : }
709 : :
710 : :
711 : : // Frange implementation.
712 : :
713 : : void
714 : 566 : frange::accept (const vrange_visitor &v) const
715 : : {
716 : 566 : v.visit (*this);
717 : 566 : }
718 : :
719 : : bool
720 : 0 : frange::fits_p (const vrange &) const
721 : : {
722 : 0 : return true;
723 : : }
724 : :
725 : : // Flush denormal endpoints to the appropriate 0.0.
726 : :
727 : : void
728 : 6728295 : frange::flush_denormals_to_zero ()
729 : : {
730 : 6728295 : if (undefined_p () || known_isnan ())
731 : : return;
732 : :
733 : 6728295 : machine_mode mode = TYPE_MODE (type ());
734 : : // Flush [x, -DENORMAL] to [x, -0.0].
735 : 6728295 : if (real_isdenormal (&m_max, mode) && real_isneg (&m_max))
736 : : {
737 : 2120 : if (HONOR_SIGNED_ZEROS (m_type))
738 : 2120 : m_max = dconstm0;
739 : : else
740 : 0 : m_max = dconst0;
741 : : }
742 : : // Flush [+DENORMAL, x] to [+0.0, x].
743 : 6728295 : if (real_isdenormal (&m_min, mode) && !real_isneg (&m_min))
744 : 3433 : m_min = dconst0;
745 : : }
746 : :
747 : : // Setter for franges.
748 : :
749 : : void
750 : 62993081 : frange::set (tree type,
751 : : const REAL_VALUE_TYPE &min, const REAL_VALUE_TYPE &max,
752 : : const nan_state &nan, value_range_kind kind)
753 : : {
754 : 62993081 : switch (kind)
755 : : {
756 : 0 : case VR_UNDEFINED:
757 : 0 : set_undefined ();
758 : 0 : return;
759 : 32637090 : case VR_VARYING:
760 : 32637090 : case VR_ANTI_RANGE:
761 : 32637090 : set_varying (type);
762 : 32637090 : return;
763 : 30355991 : case VR_RANGE:
764 : 30355991 : break;
765 : 0 : default:
766 : 0 : gcc_unreachable ();
767 : : }
768 : :
769 : 30355991 : gcc_checking_assert (!real_isnan (&min) && !real_isnan (&max));
770 : :
771 : 30355991 : m_kind = kind;
772 : 30355991 : m_type = type;
773 : 30355991 : m_min = min;
774 : 30355991 : m_max = max;
775 : 30355991 : if (HONOR_NANS (m_type))
776 : : {
777 : 29592226 : m_pos_nan = nan.pos_p ();
778 : 29592226 : m_neg_nan = nan.neg_p ();
779 : : }
780 : : else
781 : : {
782 : 763765 : m_pos_nan = false;
783 : 763765 : m_neg_nan = false;
784 : : }
785 : :
786 : 121423964 : if (!MODE_HAS_SIGNED_ZEROS (TYPE_MODE (m_type)))
787 : : {
788 : 0 : if (real_iszero (&m_min, 1))
789 : 0 : m_min.sign = 0;
790 : 0 : if (real_iszero (&m_max, 1))
791 : 0 : m_max.sign = 0;
792 : : }
793 : 30355991 : else if (!HONOR_SIGNED_ZEROS (m_type))
794 : : {
795 : 792627 : if (real_iszero (&m_max, 1))
796 : 18 : m_max.sign = 0;
797 : 792627 : if (real_iszero (&m_min, 0))
798 : 27458 : m_min.sign = 1;
799 : : }
800 : :
801 : : // For -ffinite-math-only we can drop ranges outside the
802 : : // representable numbers to min/max for the type.
803 : 30355991 : if (!HONOR_INFINITIES (m_type))
804 : : {
805 : 763765 : REAL_VALUE_TYPE min_repr = frange_val_min (m_type);
806 : 763765 : REAL_VALUE_TYPE max_repr = frange_val_max (m_type);
807 : 763765 : if (real_less (&m_min, &min_repr))
808 : 289472 : m_min = min_repr;
809 : 474293 : else if (real_less (&max_repr, &m_min))
810 : 1 : m_min = max_repr;
811 : 763765 : if (real_less (&max_repr, &m_max))
812 : 292289 : m_max = max_repr;
813 : 471476 : else if (real_less (&m_max, &min_repr))
814 : 0 : m_max = min_repr;
815 : : }
816 : :
817 : : // Check for swapped ranges.
818 : 30355991 : gcc_checking_assert (real_compare (LE_EXPR, &min, &max));
819 : :
820 : 30355991 : normalize_kind ();
821 : : }
822 : :
823 : : // Setter for an frange defaulting the NAN possibility to +-NAN when
824 : : // HONOR_NANS.
825 : :
826 : : void
827 : 49721398 : frange::set (tree type,
828 : : const REAL_VALUE_TYPE &min, const REAL_VALUE_TYPE &max,
829 : : value_range_kind kind)
830 : : {
831 : 49721398 : set (type, min, max, nan_state (true), kind);
832 : 49721398 : }
833 : :
834 : : void
835 : 16 : frange::set (tree min, tree max, value_range_kind kind)
836 : : {
837 : 32 : set (TREE_TYPE (min),
838 : 16 : *TREE_REAL_CST_PTR (min), *TREE_REAL_CST_PTR (max), kind);
839 : 16 : }
840 : :
841 : : // Normalize range to VARYING or UNDEFINED, or vice versa. Return
842 : : // TRUE if anything changed.
843 : : //
844 : : // A range with no known properties can be dropped to VARYING.
845 : : // Similarly, a VARYING with any properties should be dropped to a
846 : : // VR_RANGE. Normalizing ranges upon changing them ensures there is
847 : : // only one representation for a given range.
848 : :
849 : : bool
850 : 59556298 : frange::normalize_kind ()
851 : : {
852 : 59556298 : if (m_kind == VR_RANGE
853 : 52263871 : && frange_val_is_min (m_min, m_type)
854 : 70330111 : && frange_val_is_max (m_max, m_type))
855 : : {
856 : 7862128 : if (!HONOR_NANS (m_type) || (m_pos_nan && m_neg_nan))
857 : : {
858 : 6443262 : set_varying (m_type);
859 : 6443262 : return true;
860 : : }
861 : : }
862 : 51694170 : else if (m_kind == VR_VARYING)
863 : : {
864 : 7292118 : if (HONOR_NANS (m_type) && (!m_pos_nan || !m_neg_nan))
865 : : {
866 : 1761852 : m_kind = VR_RANGE;
867 : 1761852 : m_min = frange_val_min (m_type);
868 : 1761852 : m_max = frange_val_max (m_type);
869 : 1761852 : if (flag_checking)
870 : 1761852 : verify_range ();
871 : 1761852 : return true;
872 : : }
873 : : }
874 : 44402052 : else if (m_kind == VR_NAN && !m_pos_nan && !m_neg_nan)
875 : 4 : set_undefined ();
876 : : return false;
877 : : }
878 : :
879 : : // Union or intersect the zero endpoints of two ranges. For example:
880 : : // [-0, x] U [+0, x] => [-0, x]
881 : : // [ x, -0] U [ x, +0] => [ x, +0]
882 : : // [-0, x] ^ [+0, x] => [+0, x]
883 : : // [ x, -0] ^ [ x, +0] => [ x, -0]
884 : : //
885 : : // UNION_P is true when performing a union, or false when intersecting.
886 : :
887 : : bool
888 : 8211780 : frange::combine_zeros (const frange &r, bool union_p)
889 : : {
890 : 8211780 : gcc_checking_assert (!undefined_p () && !known_isnan ());
891 : :
892 : 8211780 : bool changed = false;
893 : 10929930 : if (real_iszero (&m_min) && real_iszero (&r.m_min)
894 : 10516974 : && real_isneg (&m_min) != real_isneg (&r.m_min))
895 : : {
896 : 145569 : m_min.sign = union_p;
897 : 145569 : changed = true;
898 : : }
899 : 8406003 : if (real_iszero (&m_max) && real_iszero (&r.m_max)
900 : 8364987 : && real_isneg (&m_max) != real_isneg (&r.m_max))
901 : : {
902 : 3961 : m_max.sign = !union_p;
903 : 3961 : changed = true;
904 : : }
905 : : // If the signs are swapped, the resulting range is empty.
906 : 8211780 : if (m_min.sign == 0 && m_max.sign == 1)
907 : : {
908 : 136 : if (maybe_isnan ())
909 : 8 : m_kind = VR_NAN;
910 : : else
911 : 64 : set_undefined ();
912 : : changed = true;
913 : : }
914 : 8211780 : return changed;
915 : : }
916 : :
917 : : // Union two ranges when one is known to be a NAN.
918 : :
919 : : bool
920 : 192813 : frange::union_nans (const frange &r)
921 : : {
922 : 192813 : gcc_checking_assert (known_isnan () || r.known_isnan ());
923 : :
924 : 192813 : bool changed = false;
925 : 192813 : if (known_isnan () && m_kind != r.m_kind)
926 : : {
927 : 38349 : m_kind = r.m_kind;
928 : 38349 : m_min = r.m_min;
929 : 38349 : m_max = r.m_max;
930 : 38349 : changed = true;
931 : : }
932 : 192813 : if (m_pos_nan != r.m_pos_nan || m_neg_nan != r.m_neg_nan)
933 : : {
934 : 183920 : m_pos_nan |= r.m_pos_nan;
935 : 183920 : m_neg_nan |= r.m_neg_nan;
936 : 183920 : changed = true;
937 : : }
938 : 192813 : if (changed)
939 : : {
940 : 191348 : normalize_kind ();
941 : 191348 : return true;
942 : : }
943 : : return false;
944 : : }
945 : :
946 : : bool
947 : 3817095 : frange::union_ (const vrange &v)
948 : : {
949 : 3817095 : const frange &r = as_a <frange> (v);
950 : :
951 : 3817095 : if (r.undefined_p () || varying_p ())
952 : : return false;
953 : 3158560 : if (undefined_p () || r.varying_p ())
954 : : {
955 : 1928144 : *this = r;
956 : 1928144 : return true;
957 : : }
958 : :
959 : : // Combine NAN info.
960 : 1230416 : if (known_isnan () || r.known_isnan ())
961 : 192813 : return union_nans (r);
962 : 1037603 : bool changed = false;
963 : 1037603 : if (m_pos_nan != r.m_pos_nan || m_neg_nan != r.m_neg_nan)
964 : : {
965 : 361988 : m_pos_nan |= r.m_pos_nan;
966 : 361988 : m_neg_nan |= r.m_neg_nan;
967 : 361988 : changed = true;
968 : : }
969 : :
970 : : // Combine endpoints.
971 : 1037603 : if (real_less (&r.m_min, &m_min))
972 : : {
973 : 492561 : m_min = r.m_min;
974 : 492561 : changed = true;
975 : : }
976 : 1037603 : if (real_less (&m_max, &r.m_max))
977 : : {
978 : 68212 : m_max = r.m_max;
979 : 68212 : changed = true;
980 : : }
981 : :
982 : 1037603 : if (HONOR_SIGNED_ZEROS (m_type))
983 : 1033713 : changed |= combine_zeros (r, true);
984 : :
985 : 1037603 : changed |= normalize_kind ();
986 : 1037603 : return changed;
987 : : }
988 : :
989 : : // Intersect two ranges when one is known to be a NAN.
990 : :
991 : : bool
992 : 40764 : frange::intersect_nans (const frange &r)
993 : : {
994 : 40764 : gcc_checking_assert (known_isnan () || r.known_isnan ());
995 : :
996 : 40764 : m_pos_nan &= r.m_pos_nan;
997 : 40764 : m_neg_nan &= r.m_neg_nan;
998 : 42610 : if (maybe_isnan ())
999 : 38950 : m_kind = VR_NAN;
1000 : : else
1001 : 1814 : set_undefined ();
1002 : 40764 : if (flag_checking)
1003 : 40764 : verify_range ();
1004 : 40764 : return true;
1005 : : }
1006 : :
1007 : : bool
1008 : 24525944 : frange::intersect (const vrange &v)
1009 : : {
1010 : 24525944 : const frange &r = as_a <frange> (v);
1011 : :
1012 : 24525944 : if (undefined_p () || r.varying_p ())
1013 : : return false;
1014 : 9565073 : if (r.undefined_p ())
1015 : : {
1016 : 4203 : set_undefined ();
1017 : 4203 : return true;
1018 : : }
1019 : 9560870 : if (varying_p ())
1020 : : {
1021 : 2239973 : *this = r;
1022 : 2239973 : return true;
1023 : : }
1024 : :
1025 : : // Combine NAN info.
1026 : 7320897 : if (known_isnan () || r.known_isnan ())
1027 : 40764 : return intersect_nans (r);
1028 : 7280133 : bool changed = false;
1029 : 7280133 : if (m_pos_nan != r.m_pos_nan || m_neg_nan != r.m_neg_nan)
1030 : : {
1031 : 2465722 : m_pos_nan &= r.m_pos_nan;
1032 : 2465722 : m_neg_nan &= r.m_neg_nan;
1033 : 2465722 : changed = true;
1034 : : }
1035 : :
1036 : : // Combine endpoints.
1037 : 7280133 : if (real_less (&m_min, &r.m_min))
1038 : : {
1039 : 1472187 : m_min = r.m_min;
1040 : 1472187 : changed = true;
1041 : : }
1042 : 7280133 : if (real_less (&r.m_max, &m_max))
1043 : : {
1044 : 1269129 : m_max = r.m_max;
1045 : 1269129 : changed = true;
1046 : : }
1047 : : // If the endpoints are swapped, the resulting range is empty.
1048 : 7280133 : if (real_less (&m_max, &m_min))
1049 : : {
1050 : 33536 : if (maybe_isnan ())
1051 : 27420 : m_kind = VR_NAN;
1052 : : else
1053 : 3058 : set_undefined ();
1054 : 30478 : if (flag_checking)
1055 : 30478 : verify_range ();
1056 : 30478 : return true;
1057 : : }
1058 : :
1059 : 7249655 : if (HONOR_SIGNED_ZEROS (m_type))
1060 : 7178067 : changed |= combine_zeros (r, false);
1061 : :
1062 : 7249655 : changed |= normalize_kind ();
1063 : 7249655 : return changed;
1064 : : }
1065 : :
1066 : : frange &
1067 : 53479053 : frange::operator= (const frange &src)
1068 : : {
1069 : 53479053 : m_kind = src.m_kind;
1070 : 53479053 : m_type = src.m_type;
1071 : 53479053 : m_min = src.m_min;
1072 : 53479053 : m_max = src.m_max;
1073 : 53479053 : m_pos_nan = src.m_pos_nan;
1074 : 53479053 : m_neg_nan = src.m_neg_nan;
1075 : :
1076 : 53479053 : if (flag_checking)
1077 : 53479053 : verify_range ();
1078 : 53479053 : return *this;
1079 : : }
1080 : :
1081 : : bool
1082 : 65368 : frange::operator== (const frange &src) const
1083 : : {
1084 : 65368 : if (m_kind == src.m_kind)
1085 : : {
1086 : 56384 : if (undefined_p ())
1087 : : return true;
1088 : :
1089 : 56266 : if (varying_p ())
1090 : 25767 : return types_compatible_p (m_type, src.m_type);
1091 : :
1092 : 30499 : bool nan1 = known_isnan ();
1093 : 30499 : bool nan2 = src.known_isnan ();
1094 : 30499 : if (nan1 || nan2)
1095 : : {
1096 : 102 : if (nan1 && nan2)
1097 : 102 : return (m_pos_nan == src.m_pos_nan
1098 : 102 : && m_neg_nan == src.m_neg_nan);
1099 : : return false;
1100 : : }
1101 : :
1102 : 30397 : return (real_identical (&m_min, &src.m_min)
1103 : 26037 : && real_identical (&m_max, &src.m_max)
1104 : 25823 : && m_pos_nan == src.m_pos_nan
1105 : 25800 : && m_neg_nan == src.m_neg_nan
1106 : 55984 : && types_compatible_p (m_type, src.m_type));
1107 : : }
1108 : : return false;
1109 : : }
1110 : :
1111 : : // Return TRUE if range contains R.
1112 : :
1113 : : bool
1114 : 50546 : frange::contains_p (const REAL_VALUE_TYPE &r) const
1115 : : {
1116 : 50546 : gcc_checking_assert (m_kind != VR_ANTI_RANGE);
1117 : :
1118 : 50546 : if (undefined_p ())
1119 : : return false;
1120 : :
1121 : 50546 : if (varying_p ())
1122 : : return true;
1123 : :
1124 : 48039 : if (real_isnan (&r))
1125 : : {
1126 : : // No NAN in range.
1127 : 0 : if (!m_pos_nan && !m_neg_nan)
1128 : : return false;
1129 : : // Both +NAN and -NAN are present.
1130 : 0 : if (m_pos_nan && m_neg_nan)
1131 : : return true;
1132 : 0 : return m_neg_nan == r.sign;
1133 : : }
1134 : 48039 : if (known_isnan ())
1135 : : return false;
1136 : :
1137 : 48039 : if (real_compare (GE_EXPR, &r, &m_min) && real_compare (LE_EXPR, &r, &m_max))
1138 : : {
1139 : : // Make sure the signs are equal for signed zeros.
1140 : 15553 : if (HONOR_SIGNED_ZEROS (m_type) && real_iszero (&r))
1141 : 30832 : return r.sign == m_min.sign || r.sign == m_max.sign;
1142 : 17 : return true;
1143 : : }
1144 : : return false;
1145 : : }
1146 : :
1147 : : // If range is a singleton, place it in RESULT and return TRUE. If
1148 : : // RESULT is NULL, just return TRUE.
1149 : : //
1150 : : // A NAN can never be a singleton.
1151 : :
1152 : : bool
1153 : 23497554 : frange::internal_singleton_p (REAL_VALUE_TYPE *result) const
1154 : : {
1155 : 23497554 : if (m_kind == VR_RANGE && real_identical (&m_min, &m_max))
1156 : : {
1157 : : // Return false for any singleton that may be a NAN.
1158 : 23606079 : if (HONOR_NANS (m_type) && maybe_isnan ())
1159 : : return false;
1160 : :
1161 : 749385 : if (MODE_COMPOSITE_P (TYPE_MODE (m_type)))
1162 : : {
1163 : : // For IBM long doubles, if the value is +-Inf or is exactly
1164 : : // representable in double, the other double could be +0.0
1165 : : // or -0.0. Since this means there is more than one way to
1166 : : // represent a value, return false to avoid propagating it.
1167 : : // See libgcc/config/rs6000/ibm-ldouble-format for details.
1168 : 0 : if (real_isinf (&m_min))
1169 : 0 : return false;
1170 : 0 : REAL_VALUE_TYPE r;
1171 : 0 : real_convert (&r, DFmode, &m_min);
1172 : 0 : if (real_identical (&r, &m_min))
1173 : : return false;
1174 : : }
1175 : :
1176 : 107055 : if (result)
1177 : 0 : *result = m_min;
1178 : 107055 : return true;
1179 : : }
1180 : : return false;
1181 : : }
1182 : :
1183 : : bool
1184 : 23497554 : frange::singleton_p (tree *result) const
1185 : : {
1186 : 23497554 : if (internal_singleton_p ())
1187 : : {
1188 : 107055 : if (result)
1189 : 8643 : *result = build_real (m_type, m_min);
1190 : 107055 : return true;
1191 : : }
1192 : : return false;
1193 : : }
1194 : :
1195 : : bool
1196 : 0 : frange::singleton_p (REAL_VALUE_TYPE &r) const
1197 : : {
1198 : 0 : return internal_singleton_p (&r);
1199 : : }
1200 : :
1201 : : bool
1202 : 57188669 : frange::supports_type_p (const_tree type) const
1203 : : {
1204 : 57188669 : return supports_p (type);
1205 : : }
1206 : :
1207 : : void
1208 : 206791045 : frange::verify_range ()
1209 : : {
1210 : 206791045 : if (!undefined_p ())
1211 : 81604507 : gcc_checking_assert (HONOR_NANS (m_type) || !maybe_isnan ());
1212 : 206791045 : switch (m_kind)
1213 : : {
1214 : 130476382 : case VR_UNDEFINED:
1215 : 130476382 : gcc_checking_assert (!m_type);
1216 : : return;
1217 : 42474432 : case VR_VARYING:
1218 : 42474432 : gcc_checking_assert (m_type);
1219 : 42474432 : gcc_checking_assert (frange_val_is_min (m_min, m_type));
1220 : 42474432 : gcc_checking_assert (frange_val_is_max (m_max, m_type));
1221 : 42474432 : if (HONOR_NANS (m_type))
1222 : 37808227 : gcc_checking_assert (m_pos_nan && m_neg_nan);
1223 : : else
1224 : 4666205 : gcc_checking_assert (!m_pos_nan && !m_neg_nan);
1225 : : return;
1226 : 33412367 : case VR_RANGE:
1227 : 33412367 : gcc_checking_assert (m_type);
1228 : 33412367 : break;
1229 : 427864 : case VR_NAN:
1230 : 427864 : gcc_checking_assert (m_type);
1231 : 427864 : gcc_checking_assert (m_pos_nan || m_neg_nan);
1232 : : return;
1233 : 0 : default:
1234 : 0 : gcc_unreachable ();
1235 : : }
1236 : :
1237 : : // NANs cannot appear in the endpoints of a range.
1238 : 33412367 : gcc_checking_assert (!real_isnan (&m_min) && !real_isnan (&m_max));
1239 : :
1240 : : // Make sure we don't have swapped ranges.
1241 : 33412367 : gcc_checking_assert (!real_less (&m_max, &m_min));
1242 : :
1243 : : // [ +0.0, -0.0 ] is nonsensical.
1244 : 33412367 : gcc_checking_assert (!(real_iszero (&m_min, 0) && real_iszero (&m_max, 1)));
1245 : :
1246 : : // If all the properties are clear, we better not span the entire
1247 : : // domain, because that would make us varying.
1248 : 33412367 : if (m_pos_nan && m_neg_nan)
1249 : 12431457 : gcc_checking_assert (!frange_val_is_min (m_min, m_type)
1250 : : || !frange_val_is_max (m_max, m_type));
1251 : : }
1252 : :
1253 : : // We can't do much with nonzeros yet.
1254 : : void
1255 : 0 : frange::set_nonzero (tree type)
1256 : : {
1257 : 0 : set_varying (type);
1258 : 0 : }
1259 : :
1260 : : // We can't do much with nonzeros yet.
1261 : : bool
1262 : 0 : frange::nonzero_p () const
1263 : : {
1264 : 0 : return false;
1265 : : }
1266 : :
1267 : : // Set range to [+0.0, +0.0] if honoring signed zeros, or [0.0, 0.0]
1268 : : // otherwise.
1269 : :
1270 : : void
1271 : 145220 : frange::set_zero (tree type)
1272 : : {
1273 : 145220 : if (HONOR_SIGNED_ZEROS (type))
1274 : : {
1275 : 145220 : set (type, dconstm0, dconst0);
1276 : 145220 : clear_nan ();
1277 : : }
1278 : : else
1279 : 0 : set (type, dconst0, dconst0);
1280 : 145220 : }
1281 : :
1282 : : // Return TRUE for any zero regardless of sign.
1283 : :
1284 : : bool
1285 : 9274 : frange::zero_p () const
1286 : : {
1287 : 9274 : return (m_kind == VR_RANGE
1288 : 8349 : && real_iszero (&m_min)
1289 : 11408 : && real_iszero (&m_max));
1290 : : }
1291 : :
1292 : : // Set the range to non-negative numbers, that is [+0.0, +INF].
1293 : : //
1294 : : // The NAN in the resulting range (if HONOR_NANS) has a varying sign
1295 : : // as there are no guarantees in IEEE 754 wrt to the sign of a NAN,
1296 : : // except for copy, abs, and copysign. It is the responsibility of
1297 : : // the caller to set the NAN's sign if desired.
1298 : :
1299 : : void
1300 : 33228 : frange::set_nonnegative (tree type)
1301 : : {
1302 : 33228 : set (type, dconst0, frange_val_max (type));
1303 : 33228 : }
1304 : :
1305 : : tree
1306 : 0 : frange::lbound () const
1307 : : {
1308 : 0 : return build_real (type (), lower_bound ());
1309 : : }
1310 : :
1311 : : tree
1312 : 0 : frange::ubound () const
1313 : : {
1314 : 0 : return build_real (type (), upper_bound ());
1315 : : }
1316 : :
1317 : : // Here we copy between any two irange's.
1318 : :
1319 : : irange &
1320 : 975193661 : irange::operator= (const irange &src)
1321 : : {
1322 : 975193661 : int needed = src.num_pairs ();
1323 : 975193661 : maybe_resize (needed);
1324 : :
1325 : 975193661 : unsigned x;
1326 : 975193661 : unsigned lim = src.m_num_ranges;
1327 : 975193661 : if (lim > m_max_ranges)
1328 : 13164 : lim = m_max_ranges;
1329 : :
1330 : 3081068013 : for (x = 0; x < lim * 2; ++x)
1331 : 2105874352 : m_base[x] = src.m_base[x];
1332 : :
1333 : : // If the range didn't fit, the last range should cover the rest.
1334 : 975193661 : if (lim != src.m_num_ranges)
1335 : 13164 : m_base[x - 1] = src.m_base[src.m_num_ranges * 2 - 1];
1336 : :
1337 : 975193661 : m_num_ranges = lim;
1338 : 975193661 : m_type = src.m_type;
1339 : 975193661 : m_kind = src.m_kind;
1340 : 975193661 : m_bitmask = src.m_bitmask;
1341 : 975193661 : if (m_max_ranges == 1)
1342 : 20996443 : normalize_kind ();
1343 : 975193661 : if (flag_checking)
1344 : 975187590 : verify_range ();
1345 : 975193661 : return *this;
1346 : : }
1347 : :
1348 : : static value_range_kind
1349 : 19442766 : get_legacy_range (const irange &r, tree &min, tree &max)
1350 : : {
1351 : 19442766 : if (r.undefined_p ())
1352 : : {
1353 : 103866 : min = NULL_TREE;
1354 : 103866 : max = NULL_TREE;
1355 : 103866 : return VR_UNDEFINED;
1356 : : }
1357 : :
1358 : 19338900 : tree type = r.type ();
1359 : 19338900 : if (r.varying_p ())
1360 : : {
1361 : 8423298 : min = wide_int_to_tree (type, r.lower_bound ());
1362 : 8423298 : max = wide_int_to_tree (type, r.upper_bound ());
1363 : 8423298 : return VR_VARYING;
1364 : : }
1365 : :
1366 : 10915602 : unsigned int precision = TYPE_PRECISION (type);
1367 : 10915602 : signop sign = TYPE_SIGN (type);
1368 : 21831204 : if (r.num_pairs () > 1
1369 : 2932356 : && precision > 1
1370 : 16780314 : && r.lower_bound () == wi::min_value (precision, sign)
1371 : 15717080 : && r.upper_bound () == wi::max_value (precision, sign))
1372 : : {
1373 : 495473 : int_range<3> inv (r);
1374 : 495473 : inv.invert ();
1375 : 495473 : min = wide_int_to_tree (type, inv.lower_bound (0));
1376 : 495473 : max = wide_int_to_tree (type, inv.upper_bound (0));
1377 : 495473 : return VR_ANTI_RANGE;
1378 : 495473 : }
1379 : :
1380 : 10420129 : min = wide_int_to_tree (type, r.lower_bound ());
1381 : 10420129 : max = wide_int_to_tree (type, r.upper_bound ());
1382 : 10420129 : return VR_RANGE;
1383 : : }
1384 : :
1385 : : static value_range_kind
1386 : 2925194 : get_legacy_range (const prange &r, tree &min, tree &max)
1387 : : {
1388 : 2925194 : if (r.undefined_p ())
1389 : : {
1390 : 0 : min = NULL_TREE;
1391 : 0 : max = NULL_TREE;
1392 : 0 : return VR_UNDEFINED;
1393 : : }
1394 : :
1395 : 2925194 : tree type = r.type ();
1396 : 2925194 : if (r.varying_p ())
1397 : : {
1398 : 0 : min = r.lbound ();
1399 : 0 : max = r.ubound ();
1400 : 0 : return VR_VARYING;
1401 : : }
1402 : 2925194 : if (r.zero_p ())
1403 : : {
1404 : 2205736 : min = max = r.lbound ();
1405 : 2205736 : return VR_RANGE;
1406 : : }
1407 : 719458 : if (r.nonzero_p ())
1408 : : {
1409 : 0 : min = max = build_zero_cst (type);
1410 : 0 : return VR_ANTI_RANGE;
1411 : : }
1412 : 719458 : min = r.lbound ();
1413 : 719458 : max = r.ubound ();
1414 : 719458 : return VR_RANGE;
1415 : : }
1416 : :
1417 : : // Given a range in V, return an old-style legacy range consisting of
1418 : : // a value_range_kind with a MIN/MAX. This is to maintain
1419 : : // compatibility with passes that still depend on VR_ANTI_RANGE, and
1420 : : // only works for integers and pointers.
1421 : :
1422 : : value_range_kind
1423 : 22367960 : get_legacy_range (const vrange &v, tree &min, tree &max)
1424 : : {
1425 : 22367960 : if (is_a <irange> (v))
1426 : 19442766 : return get_legacy_range (as_a <irange> (v), min, max);
1427 : :
1428 : 2925194 : return get_legacy_range (as_a <prange> (v), min, max);
1429 : : }
1430 : :
1431 : : /* Set value range to the canonical form of {VRTYPE, MIN, MAX, EQUIV}.
1432 : : This means adjusting VRTYPE, MIN and MAX representing the case of a
1433 : : wrapping range with MAX < MIN covering [MIN, type_max] U [type_min, MAX]
1434 : : as anti-rage ~[MAX+1, MIN-1]. Likewise for wrapping anti-ranges.
1435 : : In corner cases where MAX+1 or MIN-1 wraps this will fall back
1436 : : to varying.
1437 : : This routine exists to ease canonicalization in the case where we
1438 : : extract ranges from var + CST op limit. */
1439 : :
1440 : : void
1441 : 1129091949 : irange::set (tree type, const wide_int &min, const wide_int &max,
1442 : : value_range_kind kind)
1443 : : {
1444 : 1129091949 : unsigned prec = TYPE_PRECISION (type);
1445 : 1129091949 : signop sign = TYPE_SIGN (type);
1446 : 1129091949 : wide_int min_value = wi::min_value (prec, sign);
1447 : 1129091949 : wide_int max_value = wi::max_value (prec, sign);
1448 : :
1449 : 1129091949 : m_type = type;
1450 : 1129091949 : m_bitmask.set_unknown (prec);
1451 : :
1452 : 1129091949 : if (kind == VR_RANGE)
1453 : : {
1454 : 1087258848 : m_base[0] = min;
1455 : 1087258848 : m_base[1] = max;
1456 : 1087258848 : m_num_ranges = 1;
1457 : 1486993449 : if (min == min_value && max == max_value)
1458 : 64286137 : m_kind = VR_VARYING;
1459 : : else
1460 : 1022972711 : m_kind = VR_RANGE;
1461 : : }
1462 : : else
1463 : : {
1464 : 41833101 : gcc_checking_assert (kind == VR_ANTI_RANGE);
1465 : 41833101 : gcc_checking_assert (m_max_ranges > 1);
1466 : :
1467 : 41833101 : m_kind = VR_UNDEFINED;
1468 : 41833101 : m_num_ranges = 0;
1469 : 41833101 : wi::overflow_type ovf;
1470 : 41833101 : wide_int lim;
1471 : 41833101 : if (sign == SIGNED)
1472 : 16653429 : lim = wi::add (min, -1, sign, &ovf);
1473 : : else
1474 : 25180086 : lim = wi::sub (min, 1, sign, &ovf);
1475 : :
1476 : 41833101 : if (!ovf)
1477 : : {
1478 : 28263512 : m_kind = VR_RANGE;
1479 : 28263512 : m_base[0] = min_value;
1480 : 28263512 : m_base[1] = lim;
1481 : 28263512 : ++m_num_ranges;
1482 : : }
1483 : 41833101 : if (sign == SIGNED)
1484 : 16653429 : lim = wi::sub (max, -1, sign, &ovf);
1485 : : else
1486 : 25180086 : lim = wi::add (max, 1, sign, &ovf);
1487 : 41833101 : if (!ovf)
1488 : : {
1489 : 41832235 : m_kind = VR_RANGE;
1490 : 41832235 : m_base[m_num_ranges * 2] = lim;
1491 : 41832235 : m_base[m_num_ranges * 2 + 1] = max_value;
1492 : 41832235 : ++m_num_ranges;
1493 : : }
1494 : 41833101 : }
1495 : :
1496 : 1129091949 : if (flag_checking)
1497 : 1129087105 : verify_range ();
1498 : 1129091949 : }
1499 : :
1500 : : void
1501 : 204361099 : irange::set (tree min, tree max, value_range_kind kind)
1502 : : {
1503 : 204361099 : if (POLY_INT_CST_P (min) || POLY_INT_CST_P (max))
1504 : : {
1505 : : set_varying (TREE_TYPE (min));
1506 : : return;
1507 : : }
1508 : :
1509 : 204361099 : gcc_checking_assert (TREE_CODE (min) == INTEGER_CST);
1510 : 204361099 : gcc_checking_assert (TREE_CODE (max) == INTEGER_CST);
1511 : :
1512 : 204361681 : return set (TREE_TYPE (min), wi::to_wide (min), wi::to_wide (max), kind);
1513 : : }
1514 : :
1515 : : // Check the validity of the range.
1516 : :
1517 : : void
1518 : 3794825578 : irange::verify_range ()
1519 : : {
1520 : 3794825578 : gcc_checking_assert (m_discriminator == VR_IRANGE);
1521 : 3794825578 : if (m_kind == VR_UNDEFINED)
1522 : : {
1523 : 114505 : gcc_checking_assert (m_num_ranges == 0);
1524 : : return;
1525 : : }
1526 : 3794711073 : gcc_checking_assert (supports_p (type ()));
1527 : 3794711073 : gcc_checking_assert (m_num_ranges <= m_max_ranges);
1528 : :
1529 : : // Legacy allowed these to represent VARYING for unknown types.
1530 : : // Leave this in for now, until all users are converted. Eventually
1531 : : // we should abort in set_varying.
1532 : 3794711073 : if (m_kind == VR_VARYING && m_type == error_mark_node)
1533 : : return;
1534 : :
1535 : 3794711073 : unsigned prec = TYPE_PRECISION (m_type);
1536 : 3794711073 : if (m_kind == VR_VARYING)
1537 : : {
1538 : 259768244 : gcc_checking_assert (m_bitmask.unknown_p ());
1539 : 259768244 : gcc_checking_assert (m_num_ranges == 1);
1540 : 259768244 : gcc_checking_assert (varying_compatible_p ());
1541 : 259768244 : gcc_checking_assert (lower_bound ().get_precision () == prec);
1542 : 259768244 : gcc_checking_assert (upper_bound ().get_precision () == prec);
1543 : 259768244 : return;
1544 : : }
1545 : 3534942829 : gcc_checking_assert (m_num_ranges != 0);
1546 : 3534942829 : gcc_checking_assert (!varying_compatible_p ());
1547 : 8750169976 : for (unsigned i = 0; i < m_num_ranges; ++i)
1548 : : {
1549 : 5215227147 : wide_int lb = lower_bound (i);
1550 : 5215227147 : wide_int ub = upper_bound (i);
1551 : 5215227147 : gcc_checking_assert (lb.get_precision () == prec);
1552 : 5215227147 : gcc_checking_assert (ub.get_precision () == prec);
1553 : 5215227147 : int c = wi::cmp (lb, ub, TYPE_SIGN (m_type));
1554 : 5215227147 : gcc_checking_assert (c == 0 || c == -1);
1555 : : // Previous UB should be lower than LB
1556 : 5215227147 : if (i > 0)
1557 : 3360568636 : gcc_checking_assert (wi::lt_p (upper_bound (i - 1),
1558 : : lb,
1559 : : TYPE_SIGN (m_type)));
1560 : 5215246078 : }
1561 : 3534942829 : m_bitmask.verify_mask ();
1562 : : }
1563 : :
1564 : : bool
1565 : 148617145 : irange::operator== (const irange &other) const
1566 : : {
1567 : 148617145 : if (m_num_ranges != other.m_num_ranges)
1568 : : return false;
1569 : :
1570 : 143724521 : if (m_num_ranges == 0)
1571 : : return true;
1572 : :
1573 : 143652263 : signop sign1 = TYPE_SIGN (type ());
1574 : 143652263 : signop sign2 = TYPE_SIGN (other.type ());
1575 : :
1576 : 179407749 : for (unsigned i = 0; i < m_num_ranges; ++i)
1577 : : {
1578 : 148173122 : widest_int lb = widest_int::from (lower_bound (i), sign1);
1579 : 148173122 : widest_int ub = widest_int::from (upper_bound (i), sign1);
1580 : 148173122 : widest_int lb_other = widest_int::from (other.lower_bound (i), sign2);
1581 : 148173122 : widest_int ub_other = widest_int::from (other.upper_bound (i), sign2);
1582 : 236385485 : if (lb != lb_other || ub != ub_other)
1583 : 112417636 : return false;
1584 : 148173540 : }
1585 : :
1586 : 31234627 : irange_bitmask bm1 = get_bitmask ();
1587 : 31234627 : irange_bitmask bm2 = other.get_bitmask ();
1588 : 31234627 : widest_int tmp1 = widest_int::from (bm1.mask (), sign1);
1589 : 31234627 : widest_int tmp2 = widest_int::from (bm2.mask (), sign2);
1590 : 31234627 : if (tmp1 != tmp2)
1591 : : return false;
1592 : 31232947 : if (bm1.unknown_p ())
1593 : : return true;
1594 : 21288863 : tmp1 = widest_int::from (bm1.value (), sign1);
1595 : 21288863 : tmp2 = widest_int::from (bm2.value (), sign2);
1596 : 21288851 : return tmp1 == tmp2;
1597 : 31234659 : }
1598 : :
1599 : : /* If range is a singleton, place it in RESULT and return TRUE. */
1600 : :
1601 : : bool
1602 : 594137684 : irange::singleton_p (tree *result) const
1603 : : {
1604 : 1112344177 : if (num_pairs () == 1 && lower_bound () == upper_bound ())
1605 : : {
1606 : 36397072 : if (result)
1607 : 6490018 : *result = wide_int_to_tree (type (), lower_bound ());
1608 : 36397072 : return true;
1609 : : }
1610 : : return false;
1611 : : }
1612 : :
1613 : : bool
1614 : 297224337 : irange::singleton_p (wide_int &w) const
1615 : : {
1616 : 381064505 : if (num_pairs () == 1 && lower_bound () == upper_bound ())
1617 : : {
1618 : 8102365 : w = lower_bound ();
1619 : 8102365 : return true;
1620 : : }
1621 : : return false;
1622 : : }
1623 : :
1624 : : /* Return 1 if CST is inside value range.
1625 : : 0 if CST is not inside value range.
1626 : :
1627 : : Benchmark compile/20001226-1.c compilation time after changing this
1628 : : function. */
1629 : :
1630 : : bool
1631 : 202198471 : irange::contains_p (const wide_int &cst) const
1632 : : {
1633 : 202198471 : if (undefined_p ())
1634 : : return false;
1635 : :
1636 : : // Check if the known bits in bitmask exclude CST.
1637 : 202131996 : if (!m_bitmask.member_p (cst))
1638 : : return false;
1639 : :
1640 : 201697761 : signop sign = TYPE_SIGN (type ());
1641 : 205925880 : for (unsigned r = 0; r < m_num_ranges; ++r)
1642 : : {
1643 : 205682757 : if (wi::lt_p (cst, lower_bound (r), sign))
1644 : : return false;
1645 : 122713204 : if (wi::le_p (cst, upper_bound (r), sign))
1646 : : return true;
1647 : : }
1648 : :
1649 : : return false;
1650 : : }
1651 : :
1652 : : // Perform an efficient union with R when both ranges have only a single pair.
1653 : : // Excluded are VARYING and UNDEFINED ranges.
1654 : :
1655 : : bool
1656 : 85020698 : irange::irange_single_pair_union (const irange &r)
1657 : : {
1658 : 85020698 : gcc_checking_assert (!undefined_p () && !varying_p ());
1659 : 85020698 : gcc_checking_assert (!r.undefined_p () && !varying_p ());
1660 : :
1661 : 85020698 : signop sign = TYPE_SIGN (m_type);
1662 : : // Check if current lower bound is also the new lower bound.
1663 : 85020698 : if (wi::le_p (m_base[0], r.m_base[0], sign))
1664 : : {
1665 : : // If current upper bound is new upper bound, we're done.
1666 : 67703460 : if (wi::le_p (r.m_base[1], m_base[1], sign))
1667 : 11974798 : return union_bitmask (r);
1668 : : // Otherwise R has the new upper bound.
1669 : : // Check for overlap/touching ranges, or single target range.
1670 : 111457324 : if (m_max_ranges == 1
1671 : 222914636 : || (widest_int::from (m_base[1], sign) + 1
1672 : 222914636 : >= widest_int::from (r.m_base[0], TYPE_SIGN (r.m_type))))
1673 : 19769270 : m_base[1] = r.m_base[1];
1674 : : else
1675 : : {
1676 : : // This is a dual range result.
1677 : 35959392 : m_base[2] = r.m_base[0];
1678 : 35959392 : m_base[3] = r.m_base[1];
1679 : 35959392 : m_num_ranges = 2;
1680 : : }
1681 : : // The range has been altered, so normalize it even if nothing
1682 : : // changed in the mask.
1683 : 55728662 : if (!union_bitmask (r))
1684 : 55075748 : normalize_kind ();
1685 : 55728662 : if (flag_checking)
1686 : 55728642 : verify_range ();
1687 : 55728662 : return true;
1688 : : }
1689 : :
1690 : : // Set the new lower bound to R's lower bound.
1691 : 17317238 : wide_int lb = m_base[0];
1692 : 17317238 : m_base[0] = r.m_base[0];
1693 : :
1694 : : // If R fully contains THIS range, just set the upper bound.
1695 : 17317238 : if (wi::ge_p (r.m_base[1], m_base[1], sign))
1696 : 1130947 : m_base[1] = r.m_base[1];
1697 : : // Check for overlapping ranges, or target limited to a single range.
1698 : 32372582 : else if (m_max_ranges == 1
1699 : 64745164 : || (widest_int::from (r.m_base[1], TYPE_SIGN (r.m_type)) + 1
1700 : 64745164 : >= widest_int::from (lb, sign)))
1701 : : ;
1702 : : else
1703 : : {
1704 : : // Left with 2 pairs.
1705 : 6628714 : m_num_ranges = 2;
1706 : 6628714 : m_base[2] = lb;
1707 : 6628714 : m_base[3] = m_base[1];
1708 : 6628714 : m_base[1] = r.m_base[1];
1709 : : }
1710 : : // The range has been altered, so normalize it even if nothing
1711 : : // changed in the mask.
1712 : 17317238 : if (!union_bitmask (r))
1713 : 16495718 : normalize_kind ();
1714 : 17317238 : if (flag_checking)
1715 : 17317128 : verify_range ();
1716 : 17317238 : return true;
1717 : 17317238 : }
1718 : :
1719 : : // Append R to this range, knowing that R occurs after all of these subranges.
1720 : : // Return TRUE as something must have changed.
1721 : :
1722 : : bool
1723 : 110463265 : irange::union_append (const irange &r)
1724 : : {
1725 : : // Check if the first range in R is an immmediate successor to the last
1726 : : // range, ths requiring a merge.
1727 : 110463265 : signop sign = TYPE_SIGN (m_type);
1728 : 110463265 : wide_int lb = r.lower_bound ();
1729 : 110463265 : wide_int ub = upper_bound ();
1730 : 110463265 : unsigned start = 0;
1731 : 331389795 : if (widest_int::from (ub, sign) + 1
1732 : 331389795 : == widest_int::from (lb, sign))
1733 : : {
1734 : 796794 : m_base[m_num_ranges * 2 - 1] = r.m_base[1];
1735 : 796794 : start = 1;
1736 : : }
1737 : 110463265 : maybe_resize (m_num_ranges + r.m_num_ranges - start);
1738 : 330862575 : for ( ; start < r.m_num_ranges; start++)
1739 : : {
1740 : : // Merge the last ranges if it exceeds the maximum size.
1741 : 110406890 : if (m_num_ranges + 1 > m_max_ranges)
1742 : : {
1743 : 470845 : m_base[m_max_ranges * 2 - 1] = r.m_base[r.m_num_ranges * 2 - 1];
1744 : 470845 : break;
1745 : : }
1746 : 109936045 : m_base[m_num_ranges * 2] = r.m_base[start * 2];
1747 : 109936045 : m_base[m_num_ranges * 2 + 1] = r.m_base[start * 2 + 1];
1748 : 109936045 : m_num_ranges++;
1749 : : }
1750 : :
1751 : 110463265 : if (!union_bitmask (r))
1752 : 110429342 : normalize_kind ();
1753 : 110463265 : if (flag_checking)
1754 : 110463265 : verify_range ();
1755 : 110463265 : return true;
1756 : 110463265 : }
1757 : :
1758 : : // Return TRUE if anything changes.
1759 : :
1760 : : bool
1761 : 303824041 : irange::union_ (const vrange &v)
1762 : : {
1763 : 303824041 : const irange &r = as_a <irange> (v);
1764 : :
1765 : 303824041 : if (r.undefined_p ())
1766 : : return false;
1767 : :
1768 : 302958825 : if (undefined_p ())
1769 : : {
1770 : 77726908 : operator= (r);
1771 : 77726908 : if (flag_checking)
1772 : 77726319 : verify_range ();
1773 : 77726908 : return true;
1774 : : }
1775 : :
1776 : 225231917 : if (varying_p ())
1777 : : return false;
1778 : :
1779 : 215299760 : if (r.varying_p ())
1780 : : {
1781 : 6151191 : set_varying (type ());
1782 : 6151191 : return true;
1783 : : }
1784 : :
1785 : : // Special case one range union one range.
1786 : 209148569 : if (m_num_ranges == 1 && r.m_num_ranges == 1)
1787 : 85020698 : return irange_single_pair_union (r);
1788 : :
1789 : 124127871 : signop sign = TYPE_SIGN (m_type);
1790 : : // Check for an append to the end.
1791 : 372383613 : if (m_kind == VR_RANGE && wi::gt_p (r.lower_bound (), upper_bound (), sign))
1792 : 110463265 : return union_append (r);
1793 : :
1794 : : // If this ranges fully contains R, then we need do nothing.
1795 : 13664606 : if (irange_contains_p (r))
1796 : 3269588 : return union_bitmask (r);
1797 : :
1798 : : // Do not worry about merging and such by reserving twice as many
1799 : : // pairs as needed, and then simply sort the 2 ranges into this
1800 : : // intermediate form.
1801 : : //
1802 : : // The intermediate result will have the property that the beginning
1803 : : // of each range is <= the beginning of the next range. There may
1804 : : // be overlapping ranges at this point. I.e. this would be valid
1805 : : // [-20, 10], [-10, 0], [0, 20], [40, 90] as it satisfies this
1806 : : // constraint : -20 < -10 < 0 < 40. When the range is rebuilt into r,
1807 : : // the merge is performed.
1808 : : //
1809 : : // [Xi,Yi]..[Xn,Yn] U [Xj,Yj]..[Xm,Ym] --> [Xk,Yk]..[Xp,Yp]
1810 : 10395018 : auto_vec<wide_int, 20> res (m_num_ranges * 2 + r.m_num_ranges * 2);
1811 : 10395018 : unsigned i = 0, j = 0, k = 0;
1812 : :
1813 : 45283274 : while (i < m_num_ranges * 2 && j < r.m_num_ranges * 2)
1814 : : {
1815 : : // lower of Xi and Xj is the lowest point.
1816 : 48986476 : if (widest_int::from (m_base[i], sign)
1817 : 73479714 : <= widest_int::from (r.m_base[j], sign))
1818 : : {
1819 : 12614797 : res.quick_push (m_base[i]);
1820 : 12614797 : res.quick_push (m_base[i + 1]);
1821 : 12614797 : k += 2;
1822 : 12614797 : i += 2;
1823 : : }
1824 : : else
1825 : : {
1826 : 11878441 : res.quick_push (r.m_base[j]);
1827 : 11878441 : res.quick_push (r.m_base[j + 1]);
1828 : 11878441 : k += 2;
1829 : 11878441 : j += 2;
1830 : : }
1831 : : }
1832 : 20844848 : for ( ; i < m_num_ranges * 2; i += 2)
1833 : : {
1834 : 10449830 : res.quick_push (m_base[i]);
1835 : 10449830 : res.quick_push (m_base[i + 1]);
1836 : 10449830 : k += 2;
1837 : : }
1838 : 15280812 : for ( ; j < r.m_num_ranges * 2; j += 2)
1839 : : {
1840 : 4885794 : res.quick_push (r.m_base[j]);
1841 : 4885794 : res.quick_push (r.m_base[j + 1]);
1842 : 4885794 : k += 2;
1843 : : }
1844 : :
1845 : : // Now normalize the vector removing any overlaps.
1846 : : i = 2;
1847 : 39828862 : for (j = 2; j < k ; j += 2)
1848 : : {
1849 : : // Current upper+1 is >= lower bound next pair, then we merge ranges.
1850 : 88301543 : if (widest_int::from (res[i - 1], sign) + 1
1851 : 88301532 : >= widest_int::from (res[j], sign))
1852 : : {
1853 : : // New upper bounds is greater of current or the next one.
1854 : 21470732 : if (widest_int::from (res[j + 1], sign)
1855 : 32206098 : > widest_int::from (res[i - 1], sign))
1856 : 7498039 : res[i - 1] = res[j + 1];
1857 : : }
1858 : : else
1859 : : {
1860 : : // This is a new distinct range, but no point in copying it
1861 : : // if it is already in the right place.
1862 : 18698478 : if (i != j)
1863 : : {
1864 : 5054008 : res[i++] = res[j];
1865 : 5054008 : res[i++] = res[j + 1];
1866 : : }
1867 : : else
1868 : 13644470 : i += 2;
1869 : : }
1870 : : }
1871 : :
1872 : : // At this point, the vector should have i ranges, none overlapping.
1873 : : // Now it simply needs to be copied, and if there are too many
1874 : : // ranges, merge some. We wont do any analysis as to what the
1875 : : // "best" merges are, simply combine the final ranges into one.
1876 : 10395018 : maybe_resize (i / 2);
1877 : 10395018 : if (i > m_max_ranges * 2)
1878 : : {
1879 : 726 : res[m_max_ranges * 2 - 1] = res[i - 1];
1880 : 726 : i = m_max_ranges * 2;
1881 : : }
1882 : :
1883 : 68580558 : for (j = 0; j < i ; j++)
1884 : 58185540 : m_base[j] = res [j];
1885 : 10395018 : m_num_ranges = i / 2;
1886 : :
1887 : 10395018 : m_kind = VR_RANGE;
1888 : : // The range has been altered, so normalize it even if nothing
1889 : : // changed in the mask.
1890 : 10395018 : if (!union_bitmask (r))
1891 : 9608741 : normalize_kind ();
1892 : 10395018 : if (flag_checking)
1893 : 10394979 : verify_range ();
1894 : 10395018 : return true;
1895 : 10395018 : }
1896 : :
1897 : : // Return TRUE if THIS fully contains R. No undefined or varying cases.
1898 : :
1899 : : bool
1900 : 106862279 : irange::irange_contains_p (const irange &r) const
1901 : : {
1902 : 106862279 : gcc_checking_assert (!undefined_p () && !varying_p ());
1903 : 106862279 : gcc_checking_assert (!r.undefined_p () && !varying_p ());
1904 : :
1905 : : // Check singletons directly which will include any bitmasks.
1906 : 106862279 : wide_int rl;
1907 : 106862279 : if (r.singleton_p (rl))
1908 : 3800948 : return contains_p (rl);
1909 : :
1910 : : // In order for THIS to fully contain R, all of the pairs within R must
1911 : : // be fully contained by the pairs in this object.
1912 : 103061331 : signop sign = TYPE_SIGN (m_type);
1913 : 103061331 : unsigned ri = 0;
1914 : 103061331 : unsigned i = 0;
1915 : 103061331 : rl = r.m_base[0];
1916 : 103061331 : wide_int ru = r.m_base[1];
1917 : 103061331 : wide_int l = m_base[0];
1918 : 103061331 : wide_int u = m_base[1];
1919 : 282665547 : while (1)
1920 : : {
1921 : : // If r is contained within this range, move to the next R
1922 : 282665547 : if (wi::ge_p (rl, l, sign)
1923 : 282665547 : && wi::le_p (ru, u, sign))
1924 : : {
1925 : : // This pair is OK, Either done, or bump to the next.
1926 : 139296834 : if (++ri >= r.num_pairs ())
1927 : : return true;
1928 : 90277989 : rl = r.m_base[ri * 2];
1929 : 90277989 : ru = r.m_base[ri * 2 + 1];
1930 : 90277989 : continue;
1931 : : }
1932 : : // Otherwise, check if this's pair occurs before R's.
1933 : 143368713 : if (wi::lt_p (u, rl, sign))
1934 : : {
1935 : : // There's still at least one pair of R left.
1936 : 89876554 : if (++i >= num_pairs ())
1937 : : return false;
1938 : 89326227 : l = m_base[i * 2];
1939 : 89326227 : u = m_base[i * 2 + 1];
1940 : 89326227 : continue;
1941 : : }
1942 : : return false;
1943 : : }
1944 : : return false;
1945 : 103063141 : }
1946 : :
1947 : :
1948 : : // Return TRUE if anything changes.
1949 : :
1950 : : bool
1951 : 714176777 : irange::intersect (const vrange &v)
1952 : : {
1953 : 714176777 : const irange &r = as_a <irange> (v);
1954 : 714176777 : gcc_checking_assert (undefined_p () || r.undefined_p ()
1955 : : || range_compatible_p (type (), r.type ()));
1956 : :
1957 : 714176777 : if (undefined_p ())
1958 : : return false;
1959 : 713279216 : if (r.undefined_p ())
1960 : : {
1961 : 350485 : set_undefined ();
1962 : 350485 : return true;
1963 : : }
1964 : 712928731 : if (r.varying_p ())
1965 : : return false;
1966 : 428951873 : if (varying_p ())
1967 : : {
1968 : 79016713 : operator= (r);
1969 : 79016713 : return true;
1970 : : }
1971 : :
1972 : 349935160 : if (r.num_pairs () == 1)
1973 : : {
1974 : 256731033 : bool res = intersect (r.lower_bound (), r.upper_bound ());
1975 : 256730167 : if (undefined_p ())
1976 : : return true;
1977 : :
1978 : 231567640 : res |= intersect_bitmask (r);
1979 : 231567640 : if (res)
1980 : 89834985 : normalize_kind ();
1981 : 231567640 : return res;
1982 : : }
1983 : :
1984 : : // If either range is a singleton and the other range does not contain
1985 : : // it, the result is undefined.
1986 : 93204993 : wide_int val;
1987 : 94121890 : if ((singleton_p (val) && !r.contains_p (val))
1988 : 94114570 : || (r.singleton_p (val) && !contains_p (val)))
1989 : : {
1990 : 7320 : set_undefined ();
1991 : 7320 : return true;
1992 : : }
1993 : :
1994 : : // If R fully contains this, then intersection will change nothing.
1995 : 93197673 : if (r.irange_contains_p (*this))
1996 : 48139202 : return intersect_bitmask (r);
1997 : :
1998 : : // ?? We could probably come up with something smarter than the
1999 : : // worst case scenario here.
2000 : 45058471 : int needed = num_pairs () + r.num_pairs ();
2001 : 45058471 : maybe_resize (needed);
2002 : :
2003 : 45058471 : signop sign = TYPE_SIGN (m_type);
2004 : 45058471 : unsigned bld_pair = 0;
2005 : 45058471 : unsigned bld_lim = m_max_ranges;
2006 : 45058471 : int_range_max r2 (*this);
2007 : 45058471 : unsigned r2_lim = r2.num_pairs ();
2008 : 45058471 : unsigned i2 = 0;
2009 : 148454337 : for (unsigned i = 0; i < r.num_pairs (); )
2010 : : {
2011 : : // If r1's upper is < r2's lower, we can skip r1's pair.
2012 : 125492172 : wide_int ru = r.m_base[i * 2 + 1];
2013 : 125492172 : wide_int r2l = r2.m_base[i2 * 2];
2014 : 125492172 : if (wi::lt_p (ru, r2l, sign))
2015 : : {
2016 : 12391724 : i++;
2017 : 12391724 : continue;
2018 : : }
2019 : : // Likewise, skip r2's pair if its excluded.
2020 : 113100448 : wide_int r2u = r2.m_base[i2 * 2 + 1];
2021 : 113100448 : wide_int rl = r.m_base[i * 2];
2022 : 113100448 : if (wi::lt_p (r2u, rl, sign))
2023 : : {
2024 : 16579846 : i2++;
2025 : 16579846 : if (i2 < r2_lim)
2026 : 13546241 : continue;
2027 : : // No more r2, break.
2028 : : break;
2029 : : }
2030 : :
2031 : : // Must be some overlap. Find the highest of the lower bounds,
2032 : : // and set it, unless the build limits lower bounds is already
2033 : : // set.
2034 : 96520602 : if (bld_pair < bld_lim)
2035 : : {
2036 : 96299992 : if (wi::ge_p (rl, r2l, sign))
2037 : 80071646 : m_base[bld_pair * 2] = rl;
2038 : : else
2039 : 16228346 : m_base[bld_pair * 2] = r2l;
2040 : : }
2041 : : else
2042 : : // Decrease and set a new upper.
2043 : 220610 : bld_pair--;
2044 : :
2045 : : // ...and choose the lower of the upper bounds.
2046 : 96520602 : if (wi::le_p (ru, r2u, sign))
2047 : : {
2048 : 67708033 : m_base[bld_pair * 2 + 1] = ru;
2049 : 67708033 : bld_pair++;
2050 : : // Move past the r1 pair and keep trying.
2051 : 67708033 : i++;
2052 : 67708033 : continue;
2053 : : }
2054 : : else
2055 : : {
2056 : 28812569 : m_base[bld_pair * 2 + 1] = r2u;
2057 : 28812569 : bld_pair++;
2058 : 28812569 : i2++;
2059 : 28812569 : if (i2 < r2_lim)
2060 : 9749868 : continue;
2061 : : // No more r2, break.
2062 : : break;
2063 : : }
2064 : : // r2 has the higher lower bound.
2065 : 216497481 : }
2066 : :
2067 : : // At the exit of this loop, it is one of 2 things:
2068 : : // ran out of r1, or r2, but either means we are done.
2069 : 45058471 : m_num_ranges = bld_pair;
2070 : 45058471 : if (m_num_ranges == 0)
2071 : : {
2072 : 94900 : set_undefined ();
2073 : 94900 : return true;
2074 : : }
2075 : :
2076 : 44963571 : m_kind = VR_RANGE;
2077 : : // The range has been altered, so normalize it even if nothing
2078 : : // changed in the mask.
2079 : 44963571 : if (!intersect_bitmask (r))
2080 : 41834425 : normalize_kind ();
2081 : 44963571 : if (flag_checking)
2082 : 44963508 : verify_range ();
2083 : : return true;
2084 : 138263464 : }
2085 : :
2086 : :
2087 : : // Multirange intersect for a specified wide_int [lb, ub] range.
2088 : : // Return TRUE if intersect changed anything.
2089 : : //
2090 : : // NOTE: It is the caller's responsibility to intersect the mask.
2091 : :
2092 : : bool
2093 : 256730167 : irange::intersect (const wide_int& lb, const wide_int& ub)
2094 : : {
2095 : : // Undefined remains undefined.
2096 : 256730167 : if (undefined_p ())
2097 : : return false;
2098 : :
2099 : 256730167 : tree range_type = type();
2100 : 256730167 : signop sign = TYPE_SIGN (range_type);
2101 : :
2102 : 256730167 : gcc_checking_assert (TYPE_PRECISION (range_type) == wi::get_precision (lb));
2103 : 256730167 : gcc_checking_assert (TYPE_PRECISION (range_type) == wi::get_precision (ub));
2104 : :
2105 : : // If this range is fully contained, then intersection will do nothing.
2106 : 513460334 : if (wi::ge_p (lower_bound (), lb, sign)
2107 : 452881923 : && wi::le_p (upper_bound (), ub, sign))
2108 : : return false;
2109 : :
2110 : 114388665 : unsigned bld_index = 0;
2111 : 114388665 : unsigned pair_lim = num_pairs ();
2112 : 179815220 : for (unsigned i = 0; i < pair_lim; i++)
2113 : : {
2114 : 136263240 : wide_int pairl = m_base[i * 2];
2115 : 136263240 : wide_int pairu = m_base[i * 2 + 1];
2116 : : // Once UB is less than a pairs lower bound, we're done.
2117 : 136263240 : if (wi::lt_p (ub, pairl, sign))
2118 : : break;
2119 : : // if LB is greater than this pairs upper, this pair is excluded.
2120 : 115776437 : if (wi::lt_p (pairu, lb, sign))
2121 : 16502412 : continue;
2122 : :
2123 : : // Must be some overlap. Find the highest of the lower bounds,
2124 : : // and set it
2125 : 99274025 : if (wi::gt_p (lb, pairl, sign))
2126 : 46106688 : m_base[bld_index * 2] = lb;
2127 : : else
2128 : 53167337 : m_base[bld_index * 2] = pairl;
2129 : :
2130 : : // ...and choose the lower of the upper bounds and if the base pair
2131 : : // has the lower upper bound, need to check next pair too.
2132 : 99274025 : if (wi::lt_p (ub, pairu, sign))
2133 : : {
2134 : 50349882 : m_base[bld_index++ * 2 + 1] = ub;
2135 : 50349882 : break;
2136 : : }
2137 : : else
2138 : 48924143 : m_base[bld_index++ * 2 + 1] = pairu;
2139 : 136263519 : }
2140 : :
2141 : 114388665 : m_num_ranges = bld_index;
2142 : 114388665 : if (m_num_ranges == 0)
2143 : : {
2144 : 25162527 : set_undefined ();
2145 : 25162527 : return true;
2146 : : }
2147 : :
2148 : 89226138 : m_kind = VR_RANGE;
2149 : : // The caller must normalize and verify the range, as the bitmask
2150 : : // still needs to be handled.
2151 : 89226138 : return true;
2152 : : }
2153 : :
2154 : :
2155 : : // Signed 1-bits are strange. You can't subtract 1, because you can't
2156 : : // represent the number 1. This works around that for the invert routine.
2157 : :
2158 : : static wide_int inline
2159 : 41801452 : subtract_one (const wide_int &x, tree type, wi::overflow_type &overflow)
2160 : : {
2161 : 41801452 : if (TYPE_SIGN (type) == SIGNED)
2162 : 22446905 : return wi::add (x, -1, SIGNED, &overflow);
2163 : : else
2164 : 19354547 : return wi::sub (x, 1, UNSIGNED, &overflow);
2165 : : }
2166 : :
2167 : : // The analogous function for adding 1.
2168 : :
2169 : : static wide_int inline
2170 : 46198821 : add_one (const wide_int &x, tree type, wi::overflow_type &overflow)
2171 : : {
2172 : 46198821 : if (TYPE_SIGN (type) == SIGNED)
2173 : 19950484 : return wi::sub (x, -1, SIGNED, &overflow);
2174 : : else
2175 : 26248337 : return wi::add (x, 1, UNSIGNED, &overflow);
2176 : : }
2177 : :
2178 : : // Return the inverse of a range.
2179 : :
2180 : : void
2181 : 47097357 : irange::invert ()
2182 : : {
2183 : 47097357 : gcc_checking_assert (!undefined_p () && !varying_p ());
2184 : :
2185 : : // We always need one more set of bounds to represent an inverse, so
2186 : : // if we're at the limit, we can't properly represent things.
2187 : : //
2188 : : // For instance, to represent the inverse of a 2 sub-range set
2189 : : // [5, 10][20, 30], we would need a 3 sub-range set
2190 : : // [-MIN, 4][11, 19][31, MAX].
2191 : : //
2192 : : // In this case, return the most conservative thing.
2193 : : //
2194 : : // However, if any of the extremes of the range are -MIN/+MAX, we
2195 : : // know we will not need an extra bound. For example:
2196 : : //
2197 : : // INVERT([-MIN,20][30,40]) => [21,29][41,+MAX]
2198 : : // INVERT([-MIN,20][30,MAX]) => [21,29]
2199 : 47097357 : tree ttype = type ();
2200 : 47097357 : unsigned prec = TYPE_PRECISION (ttype);
2201 : 47097357 : signop sign = TYPE_SIGN (ttype);
2202 : 47097357 : wide_int type_min = wi::min_value (prec, sign);
2203 : 47097357 : wide_int type_max = wi::max_value (prec, sign);
2204 : 47097357 : m_bitmask.set_unknown (prec);
2205 : :
2206 : : // At this point, we need one extra sub-range to represent the
2207 : : // inverse.
2208 : 47097357 : maybe_resize (m_num_ranges + 1);
2209 : :
2210 : : // The algorithm is as follows. To calculate INVERT ([a,b][c,d]), we
2211 : : // generate [-MIN, a-1][b+1, c-1][d+1, MAX].
2212 : : //
2213 : : // If there is an over/underflow in the calculation for any
2214 : : // sub-range, we eliminate that subrange. This allows us to easily
2215 : : // calculate INVERT([-MIN, 5]) with: [-MIN, -MIN-1][6, MAX]. And since
2216 : : // we eliminate the underflow, only [6, MAX] remains.
2217 : 47097357 : unsigned i = 0;
2218 : 47097357 : wi::overflow_type ovf;
2219 : : // Construct leftmost range.
2220 : 47097357 : int_range_max orig_range (*this);
2221 : 47097357 : unsigned nitems = 0;
2222 : 47097357 : wide_int tmp;
2223 : : // If this is going to underflow on the MINUS 1, don't even bother
2224 : : // checking. This also handles subtracting one from an unsigned 0,
2225 : : // which doesn't set the underflow bit.
2226 : 47097400 : if (type_min != orig_range.lower_bound ())
2227 : : {
2228 : 37680459 : m_base[nitems++] = type_min;
2229 : 37680502 : tmp = subtract_one (orig_range.lower_bound (), ttype, ovf);
2230 : 37680459 : m_base[nitems++] = tmp;
2231 : 37680459 : if (ovf)
2232 : 9416898 : nitems = 0;
2233 : : }
2234 : 47097357 : i++;
2235 : : // Construct middle ranges if applicable.
2236 : 47097357 : if (orig_range.num_pairs () > 1)
2237 : : {
2238 : : unsigned j = i;
2239 : 8229555 : for (; j < (orig_range.num_pairs () * 2) - 1; j += 2)
2240 : : {
2241 : : // The middle ranges cannot have MAX/MIN, so there's no need
2242 : : // to check for unsigned overflow on the +1 and -1 here.
2243 : 4120993 : tmp = wi::add (orig_range.m_base[j], 1, sign, &ovf);
2244 : 4120993 : m_base[nitems++] = tmp;
2245 : 4120993 : tmp = subtract_one (orig_range.m_base[j + 1], ttype, ovf);
2246 : 4120993 : m_base[nitems++] = tmp;
2247 : 4120993 : if (ovf)
2248 : 0 : nitems -= 2;
2249 : : }
2250 : : i = j;
2251 : : }
2252 : : // Construct rightmost range.
2253 : : //
2254 : : // However, if this will overflow on the PLUS 1, don't even bother.
2255 : : // This also handles adding one to an unsigned MAX, which doesn't
2256 : : // set the overflow bit.
2257 : 47097357 : if (type_max != orig_range.m_base[i])
2258 : : {
2259 : 46198821 : tmp = add_one (orig_range.m_base[i], ttype, ovf);
2260 : 46198821 : m_base[nitems++] = tmp;
2261 : 46198821 : m_base[nitems++] = type_max;
2262 : 46198821 : if (ovf)
2263 : 898536 : nitems -= 2;
2264 : : }
2265 : 47097357 : m_num_ranges = nitems / 2;
2266 : :
2267 : : // We disallow undefined or varying coming in, so the result can
2268 : : // only be a VR_RANGE.
2269 : 47097357 : gcc_checking_assert (m_kind == VR_RANGE);
2270 : :
2271 : 47097357 : if (flag_checking)
2272 : 47097226 : verify_range ();
2273 : 47097400 : }
2274 : :
2275 : : // This routine will take the bounds [LB, UB], and apply the bitmask to those
2276 : : // values such that both bounds satisfy the bitmask. TRUE is returned
2277 : : // if either bound changes, and they are returned as [NEW_LB, NEW_UB].
2278 : : // if NEW_UB < NEW_LB, then the entire bound is to be removed as none of
2279 : : // the values are valid.
2280 : : // ie, [4, 14] MASK 0xFFFE VALUE 0x1
2281 : : // means all values must be odd, the new bounds returned will be [5, 13].
2282 : : // ie, [4, 4] MASK 0xFFFE VALUE 0x1
2283 : : // would return [1, 0] and as the LB < UB, the entire subrange is invalid
2284 : : // and should be removed.
2285 : :
2286 : : bool
2287 : 61959912 : irange::snap (const wide_int &lb, const wide_int &ub,
2288 : : wide_int &new_lb, wide_int &new_ub)
2289 : : {
2290 : 61959912 : uint z = wi::ctz (m_bitmask.mask ());
2291 : 61959912 : if (z == 0)
2292 : : return false;
2293 : :
2294 : 61959912 : const wide_int step = (wi::one (TYPE_PRECISION (type ())) << z);
2295 : 61959912 : const wide_int match_mask = step - 1;
2296 : 61959912 : const wide_int value = m_bitmask.value () & match_mask;
2297 : :
2298 : 61959912 : bool ovf = false;
2299 : :
2300 : 61959912 : wide_int rem_lb = lb & match_mask;
2301 : 61959912 : wide_int offset = (value - rem_lb) & match_mask;
2302 : 61959912 : new_lb = lb + offset;
2303 : : // Check for overflows at +INF
2304 : 61959912 : if (wi::lt_p (new_lb, lb, TYPE_SIGN (type ())))
2305 : : ovf = true;
2306 : :
2307 : 61959912 : wide_int rem_ub = ub & match_mask;
2308 : 61959912 : wide_int offset_ub = (rem_ub - value) & match_mask;
2309 : 61959912 : new_ub = ub - offset_ub;
2310 : : // Check for underflows at -INF
2311 : 61959912 : if (wi::gt_p (new_ub, ub, TYPE_SIGN (type ())))
2312 : : ovf = true;
2313 : :
2314 : : // Overflow or inverted range = invalid
2315 : 61959908 : if (ovf || wi::lt_p (new_ub, new_lb, TYPE_SIGN (type ())))
2316 : : {
2317 : 13204 : new_lb = wi::one (lb.get_precision ());
2318 : 13204 : new_ub = wi::zero (ub.get_precision ());
2319 : 13204 : return true;
2320 : : }
2321 : 122355639 : return (new_lb != lb) || (new_ub != ub);
2322 : 61960254 : }
2323 : :
2324 : : // This method loops through the subranges in THIS, and adjusts any bounds
2325 : : // to satisfy the contraints of the BITMASK. If a subrange is invalid,
2326 : : // it is removed. TRUE is returned if there were any changes.
2327 : :
2328 : : bool
2329 : 24173530 : irange::snap_subranges ()
2330 : : {
2331 : 24173530 : bool changed = false;
2332 : 24173530 : int_range_max invalid;
2333 : 24173530 : unsigned x;
2334 : 24173530 : wide_int lb, ub;
2335 : 86133442 : for (x = 0; x < m_num_ranges; x++)
2336 : : {
2337 : 61960026 : if (snap (lower_bound (x), upper_bound (x), lb, ub))
2338 : : {
2339 : 4035217 : changed = true;
2340 : : // This subrange is to be completely removed.
2341 : 4035217 : if (wi::lt_p (ub, lb, TYPE_SIGN (type ())))
2342 : : {
2343 : 13204 : int_range<1> tmp (type (), lower_bound (x), upper_bound (x));
2344 : 13204 : invalid.union_ (tmp);
2345 : 13204 : continue;
2346 : 13204 : }
2347 : 4022029 : if (lower_bound (x) != lb)
2348 : 1537777 : m_base[x * 2] = lb;
2349 : 4022029 : if (upper_bound (x) != ub)
2350 : 2788591 : m_base[x * 2 + 1] = ub;
2351 : : }
2352 : : }
2353 : : // Remove any subranges which are no invalid.
2354 : 24173530 : if (!invalid.undefined_p ())
2355 : : {
2356 : 8656 : invalid.invert ();
2357 : 8656 : intersect (invalid);
2358 : : }
2359 : 24173530 : return changed;
2360 : 24173549 : }
2361 : :
2362 : : // If the mask can be trivially converted to a range, do so.
2363 : : // Otherwise attempt to remove the lower bits from the range.
2364 : : // Return true if the range changed in any way.
2365 : :
2366 : : bool
2367 : 69435994 : irange::set_range_from_bitmask ()
2368 : : {
2369 : 69435994 : gcc_checking_assert (!undefined_p ());
2370 : 69435994 : if (m_bitmask.unknown_p ())
2371 : : return false;
2372 : :
2373 : : // If all the bits are known, this is a singleton.
2374 : 69433661 : if (m_bitmask.mask () == 0)
2375 : : {
2376 : : // Make sure the singleton is within the range.
2377 : 286092 : if (contains_p (m_bitmask.value ()))
2378 : 286083 : set (m_type, m_bitmask.value (), m_bitmask.value ());
2379 : : else
2380 : 12 : set_undefined ();
2381 : 286089 : return true;
2382 : : }
2383 : :
2384 : 69147005 : unsigned popcount = wi::popcount (m_bitmask.get_nonzero_bits ());
2385 : :
2386 : : // If we have only one bit set in the mask, we can figure out the
2387 : : // range immediately.
2388 : 69147005 : if (popcount == 1)
2389 : : {
2390 : : // Make sure we don't pessimize the range.
2391 : 5323382 : if (!contains_p (m_bitmask.get_nonzero_bits ()))
2392 : : return false;
2393 : :
2394 : 5323299 : bool has_zero = contains_zero_p (*this);
2395 : 5323299 : wide_int nz = m_bitmask.get_nonzero_bits ();
2396 : 5323299 : set (m_type, nz, nz);
2397 : 5323299 : m_bitmask.set_nonzero_bits (nz);
2398 : 5323299 : if (has_zero)
2399 : : {
2400 : 5322991 : int_range<2> zero;
2401 : 5322991 : zero.set_zero (m_type);
2402 : 5322991 : union_ (zero);
2403 : 5322991 : }
2404 : 5323299 : if (flag_checking)
2405 : 5323200 : verify_range ();
2406 : 5323299 : return true;
2407 : 5323299 : }
2408 : 63823639 : else if (popcount == 0)
2409 : : {
2410 : 0 : set_zero (m_type);
2411 : 0 : return true;
2412 : : }
2413 : :
2414 : : // If the mask doesn't have a trailing zero, theres nothing to filter.
2415 : 63823639 : int z = wi::ctz (m_bitmask.mask ());
2416 : 63823639 : if (!z)
2417 : : return false;
2418 : :
2419 : 24173530 : int prec = TYPE_PRECISION (m_type);
2420 : 24173530 : wide_int value = m_bitmask.value ();
2421 : 24173530 : wide_int mask = m_bitmask.mask ();
2422 : :
2423 : : // Remove the [0, X] values which the trailing-zero mask rules out.
2424 : : // For example, if z == 4, the mask is 0xFFF0, and the lowest 4 bits
2425 : : // define the range [0, 15]. Only one of which (value & low_mask) is allowed.
2426 : 24173530 : wide_int ub = (wi::one (prec) << z) - 1; // Upper bound of affected range.
2427 : 24173530 : int_range_max mask_range (m_type, wi::zero (prec), ub);
2428 : :
2429 : : // Remove the one valid value from the excluded range and form an anti-range.
2430 : 24173530 : wide_int allow = value & ub;
2431 : 24173530 : mask_range.intersect (int_range<2> (m_type, allow, allow, VR_ANTI_RANGE));
2432 : :
2433 : : // Invert it to get the allowed values and intersect it with the main range.
2434 : 24173530 : mask_range.invert ();
2435 : 24173530 : bool changed = intersect (mask_range);
2436 : :
2437 : : // Now handle the rest of the domain — the upper side for positive values,
2438 : : // or [-X, -1] for signed negatives.
2439 : : // Compute the maximum value representable under the mask/value constraint.
2440 : 24173530 : ub = mask | value;
2441 : :
2442 : : // If value is non-negative, adjust the upper limit to remove values above
2443 : : // UB that conflict with known fixed bits.
2444 : 32688919 : if (TYPE_SIGN (m_type) == UNSIGNED || wi::clz (ub) > 0)
2445 : 19292040 : mask_range = int_range<1> (m_type, wi::zero (prec), ub);
2446 : : else
2447 : : {
2448 : : // For signed negative values, find the lowest value with trailing zeros.
2449 : : // This forms a range such as [-512, -1] for z=9.
2450 : 4881490 : wide_int lb = -(wi::one (prec) << z);
2451 : 4881490 : mask_range = int_range<2> (m_type, lb, wi::minus_one (prec));
2452 : :
2453 : : // Remove the one allowed value from that set.
2454 : 4881490 : allow = value | lb;
2455 : 4881490 : mask_range.intersect (int_range<2> (m_type, allow, allow, VR_ANTI_RANGE));
2456 : 4881490 : mask_range.invert ();
2457 : 4881490 : }
2458 : :
2459 : : // Make sure we call intersect, so do it first.
2460 : 24173530 : changed = intersect (mask_range) | changed;
2461 : : // Now make sure each subrange endpoint matches the bitmask.
2462 : 24173530 : changed |= snap_subranges ();
2463 : :
2464 : 24173530 : return changed;
2465 : 24173587 : }
2466 : :
2467 : : void
2468 : 158181126 : irange::update_bitmask (const irange_bitmask &bm)
2469 : : {
2470 : 158181126 : gcc_checking_assert (!undefined_p ());
2471 : :
2472 : : // If masks are the same, there is no change.
2473 : 158181126 : if (m_bitmask == bm)
2474 : : return;
2475 : :
2476 : : // Drop VARYINGs with known bits to a plain range.
2477 : 80255383 : if (m_kind == VR_VARYING && !bm.unknown_p ())
2478 : 15564052 : m_kind = VR_RANGE;
2479 : :
2480 : 64691331 : m_bitmask = bm;
2481 : 64691331 : if (!set_range_from_bitmask ())
2482 : 45398426 : normalize_kind ();
2483 : 64691331 : if (flag_checking)
2484 : 64691225 : verify_range ();
2485 : : }
2486 : :
2487 : : // Return the bitmask of known bits that includes the bitmask inherent
2488 : : // in the range.
2489 : :
2490 : : irange_bitmask
2491 : 881190528 : irange::get_bitmask () const
2492 : : {
2493 : 881190528 : gcc_checking_assert (!undefined_p ());
2494 : :
2495 : : // The mask inherent in the range is calculated on-demand. For
2496 : : // example, [0,255] does not have known bits set by default. This
2497 : : // saves us considerable time, because setting it at creation incurs
2498 : : // a large penalty for irange::set. At the time of writing there
2499 : : // was a 5% slowdown in VRP if we kept the mask precisely up to date
2500 : : // at all times. Instead, we default to -1 and set it when
2501 : : // explicitly requested. However, this function will always return
2502 : : // the correct mask.
2503 : : //
2504 : : // This also means that the mask may have a finer granularity than
2505 : : // the range and thus contradict it. Think of the mask as an
2506 : : // enhancement to the range. For example:
2507 : : //
2508 : : // [3, 1000] MASK 0xfffffffe VALUE 0x0
2509 : : //
2510 : : // 3 is in the range endpoints, but is excluded per the known 0 bits
2511 : : // in the mask.
2512 : : //
2513 : : // See also the note in irange_bitmask::intersect.
2514 : 881194820 : irange_bitmask bm (type (), lower_bound (), upper_bound ());
2515 : 881190528 : if (!m_bitmask.unknown_p ())
2516 : 347936037 : bm.intersect (m_bitmask);
2517 : 881190528 : return bm;
2518 : : }
2519 : :
2520 : : // Set the nonzero bits in R into THIS. Return TRUE and
2521 : : // normalize the range if anything changed.
2522 : :
2523 : : void
2524 : 619615 : vrange::set_nonzero_bits (const wide_int &bits)
2525 : : {
2526 : 619615 : gcc_checking_assert (!undefined_p ());
2527 : 619615 : irange_bitmask bm (wi::zero (TYPE_PRECISION (type ())), bits);
2528 : 619615 : update_bitmask (bm);
2529 : 619615 : }
2530 : :
2531 : : // Return the nonzero bits in R.
2532 : :
2533 : : wide_int
2534 : 219191089 : vrange::get_nonzero_bits () const
2535 : : {
2536 : 219191089 : gcc_checking_assert (!undefined_p ());
2537 : 219191089 : irange_bitmask bm = get_bitmask ();
2538 : 219191627 : return bm.value () | bm.mask ();
2539 : 219191089 : }
2540 : :
2541 : : // Intersect the bitmask in R into THIS and normalize the range.
2542 : : // Return TRUE if the intersection changed anything.
2543 : :
2544 : : bool
2545 : 324670413 : irange::intersect_bitmask (const irange &r)
2546 : : {
2547 : 324670413 : gcc_checking_assert (!undefined_p () && !r.undefined_p ());
2548 : :
2549 : 324670413 : if (m_bitmask == r.m_bitmask)
2550 : : return false;
2551 : :
2552 : 89915123 : irange_bitmask bm = get_bitmask ();
2553 : 89915123 : irange_bitmask save = bm;
2554 : 89915123 : bm.intersect (r.get_bitmask ());
2555 : : // Use ths opportunity to make sure mask always reflects the
2556 : : // best mask we have.
2557 : 89915123 : m_bitmask = bm;
2558 : :
2559 : : // Updating m_bitmask may still yield a semantic bitmask (as
2560 : : // returned by get_bitmask) which is functionally equivalent to what
2561 : : // we originally had. In which case, there's still no change.
2562 : 89915123 : if (save == bm || save == get_bitmask ())
2563 : : return false;
2564 : :
2565 : 4744663 : if (!set_range_from_bitmask ())
2566 : 3598387 : normalize_kind ();
2567 : 4744663 : if (flag_checking)
2568 : 4744658 : verify_range ();
2569 : : return true;
2570 : 89915123 : }
2571 : :
2572 : : // Union the bitmask in R into THIS. Return TRUE and normalize the
2573 : : // range if anything changed.
2574 : :
2575 : : bool
2576 : 209148569 : irange::union_bitmask (const irange &r)
2577 : : {
2578 : 209148569 : gcc_checking_assert (!undefined_p () && !r.undefined_p ());
2579 : :
2580 : 209148569 : if (m_bitmask == r.m_bitmask)
2581 : : return false;
2582 : :
2583 : 15916909 : irange_bitmask bm = get_bitmask ();
2584 : 15916909 : irange_bitmask save = bm;
2585 : 15916909 : bm.union_ (r.get_bitmask ());
2586 : 29528583 : if (save == bm && (!bm.unknown_p () || m_bitmask.unknown_p ()))
2587 : 13611674 : return false;
2588 : :
2589 : 2305235 : m_bitmask = bm;
2590 : :
2591 : : // Updating m_bitmask may still yield a semantic bitmask (as
2592 : : // returned by get_bitmask) which is functionally equivalent to what
2593 : : // we originally had. In which case, there's still no change.
2594 : 2305235 : if (save == get_bitmask ())
2595 : : return false;
2596 : :
2597 : : // No need to call set_range_from_mask, because we'll never
2598 : : // narrow the range. Besides, it would cause endless recursion
2599 : : // because of the union_ in set_range_from_mask.
2600 : 2305235 : normalize_kind ();
2601 : 2305235 : return true;
2602 : 15916909 : }
2603 : :
2604 : : tree
2605 : 8774798 : irange::lbound () const
2606 : : {
2607 : 8774798 : return wide_int_to_tree (type (), lower_bound ());
2608 : : }
2609 : :
2610 : : tree
2611 : 278130 : irange::ubound () const
2612 : : {
2613 : 278130 : return wide_int_to_tree (type (), upper_bound ());
2614 : : }
2615 : :
2616 : : void
2617 : 8090677737 : irange_bitmask::verify_mask () const
2618 : : {
2619 : 8090677737 : gcc_assert (m_value.get_precision () == m_mask.get_precision ());
2620 : 8090677737 : gcc_checking_assert (wi::bit_and (m_mask, m_value) == 0);
2621 : 8090677737 : }
2622 : :
2623 : : void
2624 : 0 : dump_value_range (FILE *file, const vrange *vr)
2625 : : {
2626 : 0 : vr->dump (file);
2627 : 0 : }
2628 : :
2629 : : DEBUG_FUNCTION void
2630 : 0 : debug (const vrange *vr)
2631 : : {
2632 : 0 : dump_value_range (stderr, vr);
2633 : 0 : fprintf (stderr, "\n");
2634 : 0 : }
2635 : :
2636 : : DEBUG_FUNCTION void
2637 : 0 : debug (const vrange &vr)
2638 : : {
2639 : 0 : debug (&vr);
2640 : 0 : }
2641 : :
2642 : : /* Return true, if VAL1 and VAL2 are equal values for VRP purposes. */
2643 : :
2644 : : bool
2645 : 63555737 : vrp_operand_equal_p (const_tree val1, const_tree val2)
2646 : : {
2647 : 63555737 : if (val1 == val2)
2648 : : return true;
2649 : 48287641 : if (!val1 || !val2 || !operand_equal_p (val1, val2, 0))
2650 : 47568365 : return false;
2651 : : return true;
2652 : : }
2653 : :
2654 : : #define DEFINE_INT_RANGE_INSTANCE(N) \
2655 : : template int_range<N>::int_range(tree_node *, \
2656 : : const wide_int &, \
2657 : : const wide_int &, \
2658 : : value_range_kind); \
2659 : : template int_range<N>::int_range(tree); \
2660 : : template int_range<N>::int_range(const irange &); \
2661 : : template int_range<N>::int_range(const int_range &); \
2662 : : template int_range<N>& int_range<N>::operator= (const int_range &);
2663 : :
2664 : : DEFINE_INT_RANGE_INSTANCE(1)
2665 : : DEFINE_INT_RANGE_INSTANCE(2)
2666 : : DEFINE_INT_RANGE_INSTANCE(3)
2667 : : DEFINE_INT_RANGE_INSTANCE(255)
2668 : :
2669 : : #if CHECKING_P
2670 : : #include "selftest.h"
2671 : :
2672 : : #define INT(x) wi::shwi ((x), TYPE_PRECISION (integer_type_node))
2673 : : #define UINT(x) wi::uhwi ((x), TYPE_PRECISION (unsigned_type_node))
2674 : : #define SCHAR(x) wi::shwi ((x), TYPE_PRECISION (signed_char_type_node))
2675 : :
2676 : : namespace selftest
2677 : : {
2678 : :
2679 : : static int_range<2>
2680 : 584 : range (tree type, int a, int b, value_range_kind kind = VR_RANGE)
2681 : : {
2682 : 584 : wide_int w1, w2;
2683 : 584 : if (TYPE_UNSIGNED (type))
2684 : : {
2685 : 40 : w1 = wi::uhwi (a, TYPE_PRECISION (type));
2686 : 40 : w2 = wi::uhwi (b, TYPE_PRECISION (type));
2687 : : }
2688 : : else
2689 : : {
2690 : 544 : w1 = wi::shwi (a, TYPE_PRECISION (type));
2691 : 544 : w2 = wi::shwi (b, TYPE_PRECISION (type));
2692 : : }
2693 : 584 : return int_range<2> (type, w1, w2, kind);
2694 : 584 : }
2695 : :
2696 : : static int_range<2>
2697 : 540 : range_int (int a, int b, value_range_kind kind = VR_RANGE)
2698 : : {
2699 : 0 : return range (integer_type_node, a, b, kind);
2700 : : }
2701 : :
2702 : : static int_range<2>
2703 : 8 : range_uint (int a, int b, value_range_kind kind = VR_RANGE)
2704 : : {
2705 : 0 : return range (unsigned_type_node, a, b, kind);
2706 : : }
2707 : :
2708 : : static int_range<2>
2709 : 8 : range_uint128 (int a, int b, value_range_kind kind = VR_RANGE)
2710 : : {
2711 : 8 : tree u128_type_node = build_nonstandard_integer_type (128, 1);
2712 : 8 : return range (u128_type_node, a, b, kind);
2713 : : }
2714 : :
2715 : : static int_range<2>
2716 : 12 : range_uchar (int a, int b, value_range_kind kind = VR_RANGE)
2717 : : {
2718 : 0 : return range (unsigned_char_type_node, a, b, kind);
2719 : : }
2720 : :
2721 : : static int_range<2>
2722 : 4 : range_char (int a, int b, value_range_kind kind = VR_RANGE)
2723 : : {
2724 : 0 : return range (signed_char_type_node, a, b, kind);
2725 : : }
2726 : :
2727 : : static int_range<3>
2728 : 44 : build_range3 (int a, int b, int c, int d, int e, int f)
2729 : : {
2730 : 44 : int_range<3> i1 = range_int (a, b);
2731 : 44 : int_range<3> i2 = range_int (c, d);
2732 : 44 : int_range<3> i3 = range_int (e, f);
2733 : 44 : i1.union_ (i2);
2734 : 44 : i1.union_ (i3);
2735 : 88 : return i1;
2736 : 44 : }
2737 : :
2738 : : static void
2739 : 4 : range_tests_irange3 ()
2740 : : {
2741 : 4 : int_range<3> r0, r1, r2;
2742 : 4 : int_range<3> i1, i2, i3;
2743 : :
2744 : : // ([10,20] U [5,8]) U [1,3] ==> [1,3][5,8][10,20].
2745 : 4 : r0 = range_int (10, 20);
2746 : 4 : r1 = range_int (5, 8);
2747 : 4 : r0.union_ (r1);
2748 : 4 : r1 = range_int (1, 3);
2749 : 4 : r0.union_ (r1);
2750 : 4 : ASSERT_TRUE (r0 == build_range3 (1, 3, 5, 8, 10, 20));
2751 : :
2752 : : // [1,3][5,8][10,20] U [-5,0] => [-5,3][5,8][10,20].
2753 : 4 : r1 = range_int (-5, 0);
2754 : 4 : r0.union_ (r1);
2755 : 4 : ASSERT_TRUE (r0 == build_range3 (-5, 3, 5, 8, 10, 20));
2756 : :
2757 : : // [10,20][30,40] U [50,60] ==> [10,20][30,40][50,60].
2758 : 4 : r1 = range_int (50, 60);
2759 : 4 : r0 = range_int (10, 20);
2760 : 4 : r0.union_ (range_int (30, 40));
2761 : 4 : r0.union_ (r1);
2762 : 4 : ASSERT_TRUE (r0 == build_range3 (10, 20, 30, 40, 50, 60));
2763 : : // [10,20][30,40][50,60] U [70, 80] ==> [10,20][30,40][50,60][70,80].
2764 : 4 : r1 = range_int (70, 80);
2765 : 4 : r0.union_ (r1);
2766 : :
2767 : 4 : r2 = build_range3 (10, 20, 30, 40, 50, 60);
2768 : 4 : r2.union_ (range_int (70, 80));
2769 : 4 : ASSERT_TRUE (r0 == r2);
2770 : :
2771 : : // [10,20][30,40][50,60] U [6,35] => [6,40][50,60].
2772 : 4 : r0 = build_range3 (10, 20, 30, 40, 50, 60);
2773 : 4 : r1 = range_int (6, 35);
2774 : 4 : r0.union_ (r1);
2775 : 4 : r1 = range_int (6, 40);
2776 : 4 : r1.union_ (range_int (50, 60));
2777 : 4 : ASSERT_TRUE (r0 == r1);
2778 : :
2779 : : // [10,20][30,40][50,60] U [6,60] => [6,60].
2780 : 4 : r0 = build_range3 (10, 20, 30, 40, 50, 60);
2781 : 4 : r1 = range_int (6, 60);
2782 : 4 : r0.union_ (r1);
2783 : 4 : ASSERT_TRUE (r0 == range_int (6, 60));
2784 : :
2785 : : // [10,20][30,40][50,60] U [6,70] => [6,70].
2786 : 4 : r0 = build_range3 (10, 20, 30, 40, 50, 60);
2787 : 4 : r1 = range_int (6, 70);
2788 : 4 : r0.union_ (r1);
2789 : 4 : ASSERT_TRUE (r0 == range_int (6, 70));
2790 : :
2791 : : // [10,20][30,40][50,60] U [35,70] => [10,20][30,70].
2792 : 4 : r0 = build_range3 (10, 20, 30, 40, 50, 60);
2793 : 4 : r1 = range_int (35, 70);
2794 : 4 : r0.union_ (r1);
2795 : 4 : r1 = range_int (10, 20);
2796 : 4 : r1.union_ (range_int (30, 70));
2797 : 4 : ASSERT_TRUE (r0 == r1);
2798 : :
2799 : : // [10,20][30,40][50,60] U [15,35] => [10,40][50,60].
2800 : 4 : r0 = build_range3 (10, 20, 30, 40, 50, 60);
2801 : 4 : r1 = range_int (15, 35);
2802 : 4 : r0.union_ (r1);
2803 : 4 : r1 = range_int (10, 40);
2804 : 4 : r1.union_ (range_int (50, 60));
2805 : 4 : ASSERT_TRUE (r0 == r1);
2806 : :
2807 : : // [10,20][30,40][50,60] U [35,35] => [10,20][30,40][50,60].
2808 : 4 : r0 = build_range3 (10, 20, 30, 40, 50, 60);
2809 : 4 : r1 = range_int (35, 35);
2810 : 4 : r0.union_ (r1);
2811 : 4 : ASSERT_TRUE (r0 == build_range3 (10, 20, 30, 40, 50, 60));
2812 : 4 : }
2813 : :
2814 : : static void
2815 : 4 : range_tests_int_range_max ()
2816 : : {
2817 : 4 : int_range_max big;
2818 : 4 : unsigned int nrange;
2819 : :
2820 : : // Build a huge multi-range range.
2821 : 204 : for (nrange = 0; nrange < 50; ++nrange)
2822 : : {
2823 : 200 : int_range<1> tmp = range_int (nrange*10, nrange *10 + 5);
2824 : 200 : big.union_ (tmp);
2825 : 200 : }
2826 : 4 : ASSERT_TRUE (big.num_pairs () == nrange);
2827 : :
2828 : : // Verify that we can copy it without loosing precision.
2829 : 4 : int_range_max copy (big);
2830 : 4 : ASSERT_TRUE (copy.num_pairs () == nrange);
2831 : :
2832 : : // Inverting it should produce one more sub-range.
2833 : 4 : big.invert ();
2834 : 4 : ASSERT_TRUE (big.num_pairs () == nrange + 1);
2835 : :
2836 : 4 : int_range<1> tmp = range_int (5, 37);
2837 : 4 : big.intersect (tmp);
2838 : 4 : ASSERT_TRUE (big.num_pairs () == 4);
2839 : :
2840 : : // Test that [10,10][20,20] does NOT contain 15.
2841 : 4 : {
2842 : 4 : int_range_max i1 = range_int (10, 10);
2843 : 4 : int_range_max i2 = range_int (20, 20);
2844 : 4 : i1.union_ (i2);
2845 : 4 : ASSERT_FALSE (i1.contains_p (INT (15)));
2846 : 4 : }
2847 : 4 : }
2848 : :
2849 : : // Simulate -fstrict-enums where the domain of a type is less than the
2850 : : // underlying type.
2851 : :
2852 : : static void
2853 : 4 : range_tests_strict_enum ()
2854 : : {
2855 : : // The enum can only hold [0, 3].
2856 : 4 : tree rtype = copy_node (unsigned_type_node);
2857 : 4 : TYPE_MIN_VALUE (rtype) = build_int_cstu (rtype, 0);
2858 : 4 : TYPE_MAX_VALUE (rtype) = build_int_cstu (rtype, 3);
2859 : :
2860 : : // Test that even though vr1 covers the strict enum domain ([0, 3]),
2861 : : // it does not cover the domain of the underlying type.
2862 : 4 : int_range<1> vr1 = range (rtype, 0, 1);
2863 : 4 : int_range<1> vr2 = range (rtype, 2, 3);
2864 : 4 : vr1.union_ (vr2);
2865 : 4 : ASSERT_TRUE (vr1 == range (rtype, 0, 3));
2866 : 4 : ASSERT_FALSE (vr1.varying_p ());
2867 : :
2868 : : // Test that copying to a multi-range does not change things.
2869 : 4 : int_range<2> ir1 (vr1);
2870 : 4 : ASSERT_TRUE (ir1 == vr1);
2871 : 4 : ASSERT_FALSE (ir1.varying_p ());
2872 : :
2873 : : // The same test as above, but using TYPE_{MIN,MAX}_VALUE instead of [0,3].
2874 : 8 : vr1 = int_range<2> (rtype,
2875 : 8 : wi::to_wide (TYPE_MIN_VALUE (rtype)),
2876 : 12 : wi::to_wide (TYPE_MAX_VALUE (rtype)));
2877 : 4 : ir1 = vr1;
2878 : 4 : ASSERT_TRUE (ir1 == vr1);
2879 : 4 : ASSERT_FALSE (ir1.varying_p ());
2880 : 4 : }
2881 : :
2882 : : static void
2883 : 4 : range_tests_misc ()
2884 : : {
2885 : 4 : tree u128_type = build_nonstandard_integer_type (128, /*unsigned=*/1);
2886 : 4 : int_range<2> i1, i2, i3;
2887 : 4 : int_range<2> r0, r1, rold;
2888 : :
2889 : : // Test 1-bit signed integer union.
2890 : : // [-1,-1] U [0,0] = VARYING.
2891 : 4 : tree one_bit_type = build_nonstandard_integer_type (1, 0);
2892 : 4 : wide_int one_bit_min = irange_val_min (one_bit_type);
2893 : 4 : wide_int one_bit_max = irange_val_max (one_bit_type);
2894 : 4 : {
2895 : 4 : int_range<2> min = int_range<2> (one_bit_type, one_bit_min, one_bit_min);
2896 : 4 : int_range<2> max = int_range<2> (one_bit_type, one_bit_max, one_bit_max);
2897 : 4 : max.union_ (min);
2898 : 4 : ASSERT_TRUE (max.varying_p ());
2899 : 4 : }
2900 : : // Test that we can set a range of true+false for a 1-bit signed int.
2901 : 4 : r0 = range_true_and_false (one_bit_type);
2902 : :
2903 : : // Test inversion of 1-bit signed integers.
2904 : 4 : {
2905 : 4 : int_range<2> min = int_range<2> (one_bit_type, one_bit_min, one_bit_min);
2906 : 4 : int_range<2> max = int_range<2> (one_bit_type, one_bit_max, one_bit_max);
2907 : 4 : int_range<2> t;
2908 : 4 : t = min;
2909 : 4 : t.invert ();
2910 : 4 : ASSERT_TRUE (t == max);
2911 : 4 : t = max;
2912 : 4 : t.invert ();
2913 : 4 : ASSERT_TRUE (t == min);
2914 : 4 : }
2915 : :
2916 : : // Test that NOT(255) is [0..254] in 8-bit land.
2917 : 4 : int_range<1> not_255 = range_uchar (255, 255, VR_ANTI_RANGE);
2918 : 4 : ASSERT_TRUE (not_255 == range_uchar (0, 254));
2919 : :
2920 : : // Test that NOT(0) is [1..255] in 8-bit land.
2921 : 4 : int_range<2> not_zero;
2922 : 4 : not_zero.set_nonzero (unsigned_char_type_node);
2923 : 4 : ASSERT_TRUE (not_zero == range_uchar (1, 255));
2924 : :
2925 : : // Check that [0,127][0x..ffffff80,0x..ffffff]
2926 : : // => ~[128, 0x..ffffff7f].
2927 : 4 : r0 = range_uint128 (0, 127);
2928 : 4 : wide_int high = wi::minus_one (128);
2929 : : // low = -1 - 127 => 0x..ffffff80.
2930 : 4 : wide_int low = wi::sub (high, wi::uhwi (127, 128));
2931 : 4 : r1 = int_range<1> (u128_type, low, high); // [0x..ffffff80, 0x..ffffffff]
2932 : : // r0 = [0,127][0x..ffffff80,0x..fffffff].
2933 : 4 : r0.union_ (r1);
2934 : : // r1 = [128, 0x..ffffff7f].
2935 : 12 : r1 = int_range<1> (u128_type,
2936 : 8 : wi::uhwi (128, 128),
2937 : 8 : wi::sub (wi::minus_one (128), wi::uhwi (128, 128)));
2938 : 4 : r0.invert ();
2939 : 4 : ASSERT_TRUE (r0 == r1);
2940 : :
2941 : 4 : r0.set_varying (integer_type_node);
2942 : 4 : wide_int minint = r0.lower_bound ();
2943 : 4 : wide_int maxint = r0.upper_bound ();
2944 : :
2945 : 4 : r0.set_varying (short_integer_type_node);
2946 : :
2947 : 4 : r0.set_varying (unsigned_type_node);
2948 : 4 : wide_int maxuint = r0.upper_bound ();
2949 : :
2950 : : // Check that ~[0,5] => [6,MAX] for unsigned int.
2951 : 4 : r0 = range_uint (0, 5);
2952 : 4 : r0.invert ();
2953 : 4 : ASSERT_TRUE (r0 == int_range<1> (unsigned_type_node,
2954 : : wi::uhwi (6, TYPE_PRECISION (unsigned_type_node)),
2955 : : maxuint));
2956 : :
2957 : : // Check that ~[10,MAX] => [0,9] for unsigned int.
2958 : 8 : r0 = int_range<1> (unsigned_type_node,
2959 : 4 : wi::uhwi (10, TYPE_PRECISION (unsigned_type_node)),
2960 : 8 : maxuint);
2961 : 4 : r0.invert ();
2962 : 4 : ASSERT_TRUE (r0 == range_uint (0, 9));
2963 : :
2964 : : // Check that ~[0,5] => [6,MAX] for unsigned 128-bit numbers.
2965 : 4 : r0 = range_uint128 (0, 5, VR_ANTI_RANGE);
2966 : 4 : r1 = int_range<1> (u128_type, wi::uhwi (6, 128), wi::minus_one (128));
2967 : 4 : ASSERT_TRUE (r0 == r1);
2968 : :
2969 : : // Check that [~5] is really [-MIN,4][6,MAX].
2970 : 4 : r0 = range_int (5, 5, VR_ANTI_RANGE);
2971 : 4 : r1 = int_range<1> (integer_type_node, minint, INT (4));
2972 : 4 : r1.union_ (int_range<1> (integer_type_node, INT (6), maxint));
2973 : 4 : ASSERT_FALSE (r1.undefined_p ());
2974 : 4 : ASSERT_TRUE (r0 == r1);
2975 : :
2976 : 4 : r1 = range_int (5, 5);
2977 : 4 : int_range<2> r2 (r1);
2978 : 4 : ASSERT_TRUE (r1 == r2);
2979 : :
2980 : 4 : r1 = range_int (5, 10);
2981 : :
2982 : 4 : r1 = range_int (5, 10);
2983 : 4 : ASSERT_TRUE (r1.contains_p (INT (7)));
2984 : :
2985 : 4 : r1 = range_char (0, 20);
2986 : 4 : ASSERT_TRUE (r1.contains_p (SCHAR(15)));
2987 : 4 : ASSERT_FALSE (r1.contains_p (SCHAR(300)));
2988 : :
2989 : : // NOT([10,20]) ==> [-MIN,9][21,MAX].
2990 : 4 : r0 = r1 = range_int (10, 20);
2991 : 4 : r2 = int_range<1> (integer_type_node, minint, INT(9));
2992 : 4 : r2.union_ (int_range<1> (integer_type_node, INT(21), maxint));
2993 : 4 : ASSERT_FALSE (r2.undefined_p ());
2994 : 4 : r1.invert ();
2995 : 4 : ASSERT_TRUE (r1 == r2);
2996 : : // Test that NOT(NOT(x)) == x.
2997 : 4 : r2.invert ();
2998 : 4 : ASSERT_TRUE (r0 == r2);
2999 : :
3000 : : // Test that booleans and their inverse work as expected.
3001 : 4 : r0.set_zero (boolean_type_node);
3002 : 4 : ASSERT_TRUE (r0 == range_false ());
3003 : 4 : r0.invert ();
3004 : 4 : ASSERT_TRUE (r0 == range_true ());
3005 : :
3006 : : // Make sure NULL and non-NULL of pointer types work, and that
3007 : : // inverses of them are consistent.
3008 : 4 : tree voidp = build_pointer_type (void_type_node);
3009 : 4 : prange p0;
3010 : 4 : p0.set_zero (voidp);
3011 : 4 : prange p1 = p0;
3012 : 4 : p0.invert ();
3013 : 4 : p0.invert ();
3014 : 4 : ASSERT_TRUE (p0 == p1);
3015 : :
3016 : : // The intersection of:
3017 : : // [0, +INF] MASK 0xff..00 VALUE 0xf8
3018 : : // [0, +INF] MASK 0xff..00 VALUE 0x00
3019 : : // is [0, +INF] MASK 0xff..ff VALUE 0x00, which is VARYING.
3020 : : // Test that we normalized to VARYING.
3021 : 4 : unsigned prec = TYPE_PRECISION (voidp);
3022 : 4 : p0.set_varying (voidp);
3023 : 4 : wide_int mask = wi::mask (8, true, prec);
3024 : 4 : wide_int value = wi::uhwi (0xf8, prec);
3025 : 4 : irange_bitmask bm (wi::uhwi (0xf8, prec), mask);
3026 : 4 : p0.update_bitmask (bm);
3027 : 4 : p1.set_varying (voidp);
3028 : 4 : bm = irange_bitmask (wi::zero (prec), mask);
3029 : 4 : p1.update_bitmask (bm);
3030 : 4 : p0.intersect (p1);
3031 : :
3032 : : // [10,20] U [15, 30] => [10, 30].
3033 : 4 : r0 = range_int (10, 20);
3034 : 4 : r1 = range_int (15, 30);
3035 : 4 : r0.union_ (r1);
3036 : 4 : ASSERT_TRUE (r0 == range_int (10, 30));
3037 : :
3038 : : // [15,40] U [] => [15,40].
3039 : 4 : r0 = range_int (15, 40);
3040 : 4 : r1.set_undefined ();
3041 : 4 : r0.union_ (r1);
3042 : 4 : ASSERT_TRUE (r0 == range_int (15, 40));
3043 : :
3044 : : // [10,20] U [10,10] => [10,20].
3045 : 4 : r0 = range_int (10, 20);
3046 : 4 : r1 = range_int (10, 10);
3047 : 4 : r0.union_ (r1);
3048 : 4 : ASSERT_TRUE (r0 == range_int (10, 20));
3049 : :
3050 : : // [10,20] U [9,9] => [9,20].
3051 : 4 : r0 = range_int (10, 20);
3052 : 4 : r1 = range_int (9, 9);
3053 : 4 : r0.union_ (r1);
3054 : 4 : ASSERT_TRUE (r0 == range_int (9, 20));
3055 : :
3056 : : // [10,20] ^ [15,30] => [15,20].
3057 : 4 : r0 = range_int (10, 20);
3058 : 4 : r1 = range_int (15, 30);
3059 : 4 : r0.intersect (r1);
3060 : 4 : ASSERT_TRUE (r0 == range_int (15, 20));
3061 : :
3062 : : // Test the internal sanity of wide_int's wrt HWIs.
3063 : 4 : ASSERT_TRUE (wi::max_value (TYPE_PRECISION (boolean_type_node),
3064 : : TYPE_SIGN (boolean_type_node))
3065 : : == wi::uhwi (1, TYPE_PRECISION (boolean_type_node)));
3066 : :
3067 : : // Test zero_p().
3068 : 4 : r0 = range_int (0, 0);
3069 : 4 : ASSERT_TRUE (r0.zero_p ());
3070 : :
3071 : : // Test nonzero_p().
3072 : 4 : r0 = range_int (0, 0);
3073 : 4 : r0.invert ();
3074 : 4 : ASSERT_TRUE (r0.nonzero_p ());
3075 : :
3076 : : // r0 = ~[1,1]
3077 : 4 : r0 = range_int (1, 1, VR_ANTI_RANGE);
3078 : : // r1 = ~[3,3]
3079 : 4 : r1 = range_int (3, 3, VR_ANTI_RANGE);
3080 : :
3081 : : // vv = [0,0][2,2][4, MAX]
3082 : 4 : int_range<3> vv = r0;
3083 : 4 : vv.intersect (r1);
3084 : :
3085 : 4 : ASSERT_TRUE (vv.contains_p (UINT (2)));
3086 : 4 : ASSERT_TRUE (vv.num_pairs () == 3);
3087 : :
3088 : 4 : r0 = range_int (1, 1);
3089 : : // And union it with [0,0][2,2][4,MAX] multi range
3090 : 4 : r0.union_ (vv);
3091 : : // The result should be [0,2][4,MAX], or ~[3,3] but it must contain 2
3092 : 4 : ASSERT_TRUE (r0.contains_p (INT (2)));
3093 : 4 : }
3094 : :
3095 : : static void
3096 : 4 : range_tests_nonzero_bits ()
3097 : : {
3098 : 4 : int_range<2> r0, r1;
3099 : :
3100 : : // Adding nonzero bits to a varying drops the varying.
3101 : 4 : r0.set_varying (integer_type_node);
3102 : 4 : r0.set_nonzero_bits (INT (255));
3103 : 4 : ASSERT_TRUE (!r0.varying_p ());
3104 : : // Dropping the nonzero bits brings us back to varying.
3105 : 4 : r0.set_nonzero_bits (INT (-1));
3106 : 4 : ASSERT_TRUE (r0.varying_p ());
3107 : :
3108 : : // Test contains_p with nonzero bits.
3109 : 4 : r0.set_zero (integer_type_node);
3110 : 4 : ASSERT_TRUE (r0.contains_p (INT (0)));
3111 : 4 : ASSERT_FALSE (r0.contains_p (INT (1)));
3112 : 4 : r0.set_nonzero_bits (INT (0xfe));
3113 : 4 : ASSERT_FALSE (r0.contains_p (INT (0x100)));
3114 : 4 : ASSERT_FALSE (r0.contains_p (INT (0x3)));
3115 : :
3116 : : // Union of nonzero bits.
3117 : 4 : r0.set_varying (integer_type_node);
3118 : 4 : r0.set_nonzero_bits (INT (0xf0));
3119 : 4 : r1.set_varying (integer_type_node);
3120 : 4 : r1.set_nonzero_bits (INT (0xf));
3121 : 4 : r0.union_ (r1);
3122 : 4 : ASSERT_TRUE (r0.get_nonzero_bits () == 0xff);
3123 : :
3124 : : // Intersect of nonzero bits.
3125 : 4 : r0 = range_int (0, 255);
3126 : 4 : r0.set_nonzero_bits (INT (0xfe));
3127 : 4 : r1.set_varying (integer_type_node);
3128 : 4 : r1.set_nonzero_bits (INT (0xf0));
3129 : 4 : r0.intersect (r1);
3130 : 4 : ASSERT_TRUE (r0.get_nonzero_bits () == 0xf0);
3131 : :
3132 : : // Intersect where the mask of nonzero bits is implicit from the range.
3133 : 4 : r0.set_varying (integer_type_node);
3134 : 4 : r1 = range_int (0, 255);
3135 : 4 : r0.intersect (r1);
3136 : 4 : ASSERT_TRUE (r0.get_nonzero_bits () == 0xff);
3137 : :
3138 : : // The union of a mask of 0xff..ffff00 with a mask of 0xff spans the
3139 : : // entire domain, and makes the range a varying.
3140 : 4 : r0.set_varying (integer_type_node);
3141 : 4 : wide_int x = wi::shwi (0xff, TYPE_PRECISION (integer_type_node));
3142 : 4 : x = wi::bit_not (x);
3143 : 4 : r0.set_nonzero_bits (x); // 0xff..ff00
3144 : 4 : r1.set_varying (integer_type_node);
3145 : 4 : r1.set_nonzero_bits (INT (0xff));
3146 : 4 : r0.union_ (r1);
3147 : 4 : ASSERT_TRUE (r0.varying_p ());
3148 : :
3149 : : // Test that setting a nonzero bit of 1 does not pessimize the range.
3150 : 4 : r0.set_zero (integer_type_node);
3151 : 4 : r0.set_nonzero_bits (INT (1));
3152 : 4 : ASSERT_TRUE (r0.zero_p ());
3153 : 4 : }
3154 : :
3155 : : // Build an frange from string endpoints.
3156 : :
3157 : : static inline frange
3158 : 492 : frange_float (const char *lb, const char *ub, tree type = float_type_node)
3159 : : {
3160 : 492 : REAL_VALUE_TYPE min, max;
3161 : 492 : gcc_assert (real_from_string (&min, lb) == 0);
3162 : 492 : gcc_assert (real_from_string (&max, ub) == 0);
3163 : 492 : return frange (type, min, max);
3164 : : }
3165 : :
3166 : : static void
3167 : 4 : range_tests_nan ()
3168 : : {
3169 : 4 : frange r0, r1;
3170 : 4 : REAL_VALUE_TYPE q, r;
3171 : 4 : bool signbit;
3172 : :
3173 : : // Equal ranges but with differing NAN bits are not equal.
3174 : 4 : if (HONOR_NANS (float_type_node))
3175 : : {
3176 : 4 : r1 = frange_float ("10", "12");
3177 : 4 : r0 = r1;
3178 : 4 : ASSERT_EQ (r0, r1);
3179 : 4 : r0.clear_nan ();
3180 : 4 : ASSERT_NE (r0, r1);
3181 : 4 : r0.update_nan ();
3182 : 4 : ASSERT_EQ (r0, r1);
3183 : :
3184 : : // [10, 20] NAN ^ [30, 40] NAN = NAN.
3185 : 4 : r0 = frange_float ("10", "20");
3186 : 4 : r1 = frange_float ("30", "40");
3187 : 4 : r0.intersect (r1);
3188 : 4 : ASSERT_TRUE (r0.known_isnan ());
3189 : :
3190 : : // [3,5] U [5,10] NAN = ... NAN
3191 : 4 : r0 = frange_float ("3", "5");
3192 : 4 : r0.clear_nan ();
3193 : 4 : r1 = frange_float ("5", "10");
3194 : 4 : r0.union_ (r1);
3195 : 8 : ASSERT_TRUE (r0.maybe_isnan ());
3196 : : }
3197 : :
3198 : : // [5,6] U NAN = [5,6] NAN.
3199 : 4 : r0 = frange_float ("5", "6");
3200 : 4 : r0.clear_nan ();
3201 : 4 : r1.set_nan (float_type_node);
3202 : 4 : r0.union_ (r1);
3203 : 4 : real_from_string (&q, "5");
3204 : 4 : real_from_string (&r, "6");
3205 : 4 : ASSERT_TRUE (real_identical (&q, &r0.lower_bound ()));
3206 : 4 : ASSERT_TRUE (real_identical (&r, &r0.upper_bound ()));
3207 : 8 : ASSERT_TRUE (r0.maybe_isnan ());
3208 : :
3209 : : // NAN U NAN = NAN
3210 : 4 : r0.set_nan (float_type_node);
3211 : 4 : r1.set_nan (float_type_node);
3212 : 4 : r0.union_ (r1);
3213 : 4 : ASSERT_TRUE (r0.known_isnan ());
3214 : :
3215 : : // [INF, INF] NAN ^ NAN = NAN
3216 : 4 : r0.set_nan (float_type_node);
3217 : 4 : r1 = frange_float ("+Inf", "+Inf");
3218 : 4 : if (!HONOR_NANS (float_type_node))
3219 : 0 : r1.update_nan ();
3220 : 4 : r0.intersect (r1);
3221 : 4 : ASSERT_TRUE (r0.known_isnan ());
3222 : :
3223 : : // NAN ^ NAN = NAN
3224 : 4 : r0.set_nan (float_type_node);
3225 : 4 : r1.set_nan (float_type_node);
3226 : 4 : r0.intersect (r1);
3227 : 4 : ASSERT_TRUE (r0.known_isnan ());
3228 : :
3229 : : // +NAN ^ -NAN = UNDEFINED
3230 : 4 : r0.set_nan (float_type_node, false);
3231 : 4 : r1.set_nan (float_type_node, true);
3232 : 4 : r0.intersect (r1);
3233 : 4 : ASSERT_TRUE (r0.undefined_p ());
3234 : :
3235 : : // VARYING ^ NAN = NAN.
3236 : 4 : r0.set_nan (float_type_node);
3237 : 4 : r1.set_varying (float_type_node);
3238 : 4 : r0.intersect (r1);
3239 : 4 : ASSERT_TRUE (r0.known_isnan ());
3240 : :
3241 : : // [3,4] ^ NAN = UNDEFINED.
3242 : 4 : r0 = frange_float ("3", "4");
3243 : 4 : r0.clear_nan ();
3244 : 4 : r1.set_nan (float_type_node);
3245 : 4 : r0.intersect (r1);
3246 : 4 : ASSERT_TRUE (r0.undefined_p ());
3247 : :
3248 : : // [-3, 5] ^ NAN = UNDEFINED
3249 : 4 : r0 = frange_float ("-3", "5");
3250 : 4 : r0.clear_nan ();
3251 : 4 : r1.set_nan (float_type_node);
3252 : 4 : r0.intersect (r1);
3253 : 4 : ASSERT_TRUE (r0.undefined_p ());
3254 : :
3255 : : // Setting the NAN bit to yes does not make us a known NAN.
3256 : 4 : r0.set_varying (float_type_node);
3257 : 4 : r0.update_nan ();
3258 : 4 : ASSERT_FALSE (r0.known_isnan ());
3259 : :
3260 : : // NAN is in a VARYING.
3261 : 4 : r0.set_varying (float_type_node);
3262 : 4 : real_nan (&r, "", 1, TYPE_MODE (float_type_node));
3263 : 4 : REAL_VALUE_TYPE nan = r;
3264 : 4 : ASSERT_TRUE (r0.contains_p (nan));
3265 : :
3266 : : // -NAN is in a VARYING.
3267 : 4 : r0.set_varying (float_type_node);
3268 : 4 : q = real_value_negate (&r);
3269 : 4 : REAL_VALUE_TYPE neg_nan = q;
3270 : 4 : ASSERT_TRUE (r0.contains_p (neg_nan));
3271 : :
3272 : : // Clearing the NAN on a [] NAN is the empty set.
3273 : 4 : r0.set_nan (float_type_node);
3274 : 4 : r0.clear_nan ();
3275 : 4 : ASSERT_TRUE (r0.undefined_p ());
3276 : :
3277 : : // [10,20] NAN ^ [21,25] NAN = [NAN]
3278 : 4 : r0 = frange_float ("10", "20");
3279 : 4 : r0.update_nan ();
3280 : 4 : r1 = frange_float ("21", "25");
3281 : 4 : r1.update_nan ();
3282 : 4 : r0.intersect (r1);
3283 : 4 : ASSERT_TRUE (r0.known_isnan ());
3284 : :
3285 : : // NAN U [5,6] should be [5,6] +-NAN.
3286 : 4 : r0.set_nan (float_type_node);
3287 : 4 : r1 = frange_float ("5", "6");
3288 : 4 : r1.clear_nan ();
3289 : 4 : r0.union_ (r1);
3290 : 4 : real_from_string (&q, "5");
3291 : 4 : real_from_string (&r, "6");
3292 : 4 : ASSERT_TRUE (real_identical (&q, &r0.lower_bound ()));
3293 : 4 : ASSERT_TRUE (real_identical (&r, &r0.upper_bound ()));
3294 : 4 : ASSERT_TRUE (!r0.signbit_p (signbit));
3295 : 8 : ASSERT_TRUE (r0.maybe_isnan ());
3296 : :
3297 : : // NAN U NAN shouldn't change anything.
3298 : 4 : r0.set_nan (float_type_node);
3299 : 4 : r1.set_nan (float_type_node);
3300 : 4 : ASSERT_FALSE (r0.union_ (r1));
3301 : :
3302 : : // [3,5] NAN U NAN shouldn't change anything.
3303 : 4 : r0 = frange_float ("3", "5");
3304 : 4 : r1.set_nan (float_type_node);
3305 : 4 : ASSERT_FALSE (r0.union_ (r1));
3306 : :
3307 : : // [3,5] U NAN *does* trigger a change.
3308 : 4 : r0 = frange_float ("3", "5");
3309 : 4 : r0.clear_nan ();
3310 : 4 : r1.set_nan (float_type_node);
3311 : 4 : ASSERT_TRUE (r0.union_ (r1));
3312 : 4 : }
3313 : :
3314 : : static void
3315 : 8 : range_tests_signed_zeros ()
3316 : : {
3317 : 8 : REAL_VALUE_TYPE zero = dconst0;
3318 : 8 : REAL_VALUE_TYPE neg_zero = zero;
3319 : 8 : neg_zero.sign = 1;
3320 : 8 : frange r0, r1;
3321 : 8 : bool signbit;
3322 : :
3323 : : // [0,0] contains [0,0] but not [-0,-0] and vice versa.
3324 : 8 : r0 = frange_float ("0.0", "0.0");
3325 : 8 : r1 = frange_float ("-0.0", "-0.0");
3326 : 8 : ASSERT_TRUE (r0.contains_p (zero));
3327 : 8 : ASSERT_TRUE (!r0.contains_p (neg_zero));
3328 : 8 : ASSERT_TRUE (r1.contains_p (neg_zero));
3329 : 8 : ASSERT_TRUE (!r1.contains_p (zero));
3330 : :
3331 : : // Test contains_p() when we know the sign of the zero.
3332 : 8 : r0 = frange_float ("0.0", "0.0");
3333 : 8 : ASSERT_TRUE (r0.contains_p (zero));
3334 : 8 : ASSERT_FALSE (r0.contains_p (neg_zero));
3335 : 8 : r0 = frange_float ("-0.0", "-0.0");
3336 : 8 : ASSERT_TRUE (r0.contains_p (neg_zero));
3337 : 8 : ASSERT_FALSE (r0.contains_p (zero));
3338 : :
3339 : 8 : r0 = frange_float ("-0.0", "0.0");
3340 : 8 : ASSERT_TRUE (r0.contains_p (neg_zero));
3341 : 8 : ASSERT_TRUE (r0.contains_p (zero));
3342 : :
3343 : 8 : r0 = frange_float ("-3", "5");
3344 : 8 : ASSERT_TRUE (r0.contains_p (neg_zero));
3345 : 8 : ASSERT_TRUE (r0.contains_p (zero));
3346 : :
3347 : : // The intersection of zeros that differ in sign is a NAN (or
3348 : : // undefined if not honoring NANs).
3349 : 8 : r0 = frange_float ("-0.0", "-0.0");
3350 : 8 : r1 = frange_float ("0.0", "0.0");
3351 : 8 : r0.intersect (r1);
3352 : 8 : if (HONOR_NANS (float_type_node))
3353 : 4 : ASSERT_TRUE (r0.known_isnan ());
3354 : : else
3355 : 4 : ASSERT_TRUE (r0.undefined_p ());
3356 : :
3357 : : // The union of zeros that differ in sign is a zero with unknown sign.
3358 : 8 : r0 = frange_float ("0.0", "0.0");
3359 : 8 : r1 = frange_float ("-0.0", "-0.0");
3360 : 8 : r0.union_ (r1);
3361 : 8 : ASSERT_TRUE (r0.zero_p () && !r0.signbit_p (signbit));
3362 : :
3363 : : // [-0, +0] has an unknown sign.
3364 : 8 : r0 = frange_float ("-0.0", "0.0");
3365 : 8 : ASSERT_TRUE (r0.zero_p () && !r0.signbit_p (signbit));
3366 : :
3367 : : // [-0, +0] ^ [0, 0] is [0, 0]
3368 : 8 : r0 = frange_float ("-0.0", "0.0");
3369 : 8 : r1 = frange_float ("0.0", "0.0");
3370 : 8 : r0.intersect (r1);
3371 : 8 : ASSERT_TRUE (r0.zero_p ());
3372 : :
3373 : 8 : r0 = frange_float ("+0", "5");
3374 : 8 : r0.clear_nan ();
3375 : 8 : ASSERT_TRUE (r0.signbit_p (signbit) && !signbit);
3376 : :
3377 : 8 : r0 = frange_float ("-0", "5");
3378 : 8 : r0.clear_nan ();
3379 : 8 : ASSERT_TRUE (!r0.signbit_p (signbit));
3380 : :
3381 : 8 : r0 = frange_float ("-0", "10");
3382 : 8 : r1 = frange_float ("0", "5");
3383 : 8 : r0.intersect (r1);
3384 : 8 : ASSERT_TRUE (real_iszero (&r0.lower_bound (), false));
3385 : :
3386 : 8 : r0 = frange_float ("-0", "5");
3387 : 8 : r1 = frange_float ("0", "5");
3388 : 8 : r0.union_ (r1);
3389 : 8 : ASSERT_TRUE (real_iszero (&r0.lower_bound (), true));
3390 : :
3391 : 8 : r0 = frange_float ("-5", "-0");
3392 : 8 : r0.update_nan ();
3393 : 8 : r1 = frange_float ("0", "0");
3394 : 8 : r1.update_nan ();
3395 : 8 : r0.intersect (r1);
3396 : 8 : if (HONOR_NANS (float_type_node))
3397 : 4 : ASSERT_TRUE (r0.known_isnan ());
3398 : : else
3399 : 4 : ASSERT_TRUE (r0.undefined_p ());
3400 : :
3401 : 8 : r0.set_nonnegative (float_type_node);
3402 : 8 : if (HONOR_NANS (float_type_node))
3403 : 8 : ASSERT_TRUE (r0.maybe_isnan ());
3404 : :
3405 : : // Numbers containing zero should have an unknown SIGNBIT.
3406 : 8 : r0 = frange_float ("0", "10");
3407 : 8 : r0.clear_nan ();
3408 : 8 : ASSERT_TRUE (r0.signbit_p (signbit) && !signbit);
3409 : 8 : }
3410 : :
3411 : : static void
3412 : 8 : range_tests_signbit ()
3413 : : {
3414 : 8 : frange r0, r1;
3415 : 8 : bool signbit;
3416 : :
3417 : : // Negative numbers should have the SIGNBIT set.
3418 : 8 : r0 = frange_float ("-5", "-1");
3419 : 8 : r0.clear_nan ();
3420 : 8 : ASSERT_TRUE (r0.signbit_p (signbit) && signbit);
3421 : : // Positive numbers should have the SIGNBIT clear.
3422 : 8 : r0 = frange_float ("1", "10");
3423 : 8 : r0.clear_nan ();
3424 : 8 : ASSERT_TRUE (r0.signbit_p (signbit) && !signbit);
3425 : : // Numbers spanning both positive and negative should have an
3426 : : // unknown SIGNBIT.
3427 : 8 : r0 = frange_float ("-10", "10");
3428 : 8 : r0.clear_nan ();
3429 : 8 : ASSERT_TRUE (!r0.signbit_p (signbit));
3430 : 8 : r0.set_varying (float_type_node);
3431 : 8 : ASSERT_TRUE (!r0.signbit_p (signbit));
3432 : 8 : }
3433 : :
3434 : : static void
3435 : 8 : range_tests_floats ()
3436 : : {
3437 : 8 : frange r0, r1;
3438 : :
3439 : 8 : if (HONOR_NANS (float_type_node))
3440 : 4 : range_tests_nan ();
3441 : 8 : range_tests_signbit ();
3442 : :
3443 : 8 : if (HONOR_SIGNED_ZEROS (float_type_node))
3444 : 8 : range_tests_signed_zeros ();
3445 : :
3446 : : // A range of [-INF,+INF] is actually VARYING if no other properties
3447 : : // are set.
3448 : 8 : r0 = frange_float ("-Inf", "+Inf");
3449 : 8 : ASSERT_TRUE (r0.varying_p ());
3450 : : // ...unless it has some special property...
3451 : 8 : if (HONOR_NANS (r0.type ()))
3452 : : {
3453 : 4 : r0.clear_nan ();
3454 : 4 : ASSERT_FALSE (r0.varying_p ());
3455 : : }
3456 : :
3457 : : // For most architectures, where float and double are different
3458 : : // sizes, having the same endpoints does not necessarily mean the
3459 : : // ranges are equal.
3460 : 8 : if (!types_compatible_p (float_type_node, double_type_node))
3461 : : {
3462 : 8 : r0 = frange_float ("3.0", "3.0", float_type_node);
3463 : 8 : r1 = frange_float ("3.0", "3.0", double_type_node);
3464 : 8 : ASSERT_NE (r0, r1);
3465 : : }
3466 : :
3467 : : // [3,5] U [10,12] = [3,12].
3468 : 8 : r0 = frange_float ("3", "5");
3469 : 8 : r1 = frange_float ("10", "12");
3470 : 8 : r0.union_ (r1);
3471 : 8 : ASSERT_EQ (r0, frange_float ("3", "12"));
3472 : :
3473 : : // [5,10] U [4,8] = [4,10]
3474 : 8 : r0 = frange_float ("5", "10");
3475 : 8 : r1 = frange_float ("4", "8");
3476 : 8 : r0.union_ (r1);
3477 : 8 : ASSERT_EQ (r0, frange_float ("4", "10"));
3478 : :
3479 : : // [3,5] U [4,10] = [3,10]
3480 : 8 : r0 = frange_float ("3", "5");
3481 : 8 : r1 = frange_float ("4", "10");
3482 : 8 : r0.union_ (r1);
3483 : 8 : ASSERT_EQ (r0, frange_float ("3", "10"));
3484 : :
3485 : : // [4,10] U [5,11] = [4,11]
3486 : 8 : r0 = frange_float ("4", "10");
3487 : 8 : r1 = frange_float ("5", "11");
3488 : 8 : r0.union_ (r1);
3489 : 8 : ASSERT_EQ (r0, frange_float ("4", "11"));
3490 : :
3491 : : // [3,12] ^ [10,12] = [10,12].
3492 : 8 : r0 = frange_float ("3", "12");
3493 : 8 : r1 = frange_float ("10", "12");
3494 : 8 : r0.intersect (r1);
3495 : 8 : ASSERT_EQ (r0, frange_float ("10", "12"));
3496 : :
3497 : : // [10,12] ^ [11,11] = [11,11]
3498 : 8 : r0 = frange_float ("10", "12");
3499 : 8 : r1 = frange_float ("11", "11");
3500 : 8 : r0.intersect (r1);
3501 : 8 : ASSERT_EQ (r0, frange_float ("11", "11"));
3502 : :
3503 : : // [10,20] ^ [5,15] = [10,15]
3504 : 8 : r0 = frange_float ("10", "20");
3505 : 8 : r1 = frange_float ("5", "15");
3506 : 8 : r0.intersect (r1);
3507 : 8 : ASSERT_EQ (r0, frange_float ("10", "15"));
3508 : :
3509 : : // [10,20] ^ [15,25] = [15,20]
3510 : 8 : r0 = frange_float ("10", "20");
3511 : 8 : r1 = frange_float ("15", "25");
3512 : 8 : r0.intersect (r1);
3513 : 8 : ASSERT_EQ (r0, frange_float ("15", "20"));
3514 : :
3515 : : // [10,20] ^ [21,25] = []
3516 : 8 : r0 = frange_float ("10", "20");
3517 : 8 : r0.clear_nan ();
3518 : 8 : r1 = frange_float ("21", "25");
3519 : 8 : r1.clear_nan ();
3520 : 8 : r0.intersect (r1);
3521 : 8 : ASSERT_TRUE (r0.undefined_p ());
3522 : :
3523 : 8 : if (HONOR_INFINITIES (float_type_node))
3524 : : {
3525 : : // Make sure [-Inf, -Inf] doesn't get normalized.
3526 : 4 : r0 = frange_float ("-Inf", "-Inf");
3527 : 4 : ASSERT_TRUE (real_isinf (&r0.lower_bound (), true));
3528 : 4 : ASSERT_TRUE (real_isinf (&r0.upper_bound (), true));
3529 : : }
3530 : :
3531 : : // Test that reading back a global range yields the same result as
3532 : : // what we wrote into it.
3533 : 8 : tree ssa = make_temp_ssa_name (float_type_node, NULL, "blah");
3534 : 8 : r0.set_varying (float_type_node);
3535 : 8 : r0.clear_nan ();
3536 : 8 : set_range_info (ssa, r0);
3537 : 8 : get_global_range_query ()->range_of_expr (r1, ssa);
3538 : 8 : ASSERT_EQ (r0, r1);
3539 : 8 : }
3540 : :
3541 : : // Run floating range tests for various combinations of NAN and INF
3542 : : // support.
3543 : :
3544 : : static void
3545 : 4 : range_tests_floats_various ()
3546 : : {
3547 : 4 : int save_finite_math_only = flag_finite_math_only;
3548 : :
3549 : : // Test -ffinite-math-only.
3550 : 4 : flag_finite_math_only = 1;
3551 : 4 : range_tests_floats ();
3552 : : // Test -fno-finite-math-only.
3553 : 4 : flag_finite_math_only = 0;
3554 : 4 : range_tests_floats ();
3555 : :
3556 : 4 : flag_finite_math_only = save_finite_math_only;
3557 : 4 : }
3558 : :
3559 : : void
3560 : 4 : range_tests ()
3561 : : {
3562 : 4 : range_tests_irange3 ();
3563 : 4 : range_tests_int_range_max ();
3564 : 4 : range_tests_strict_enum ();
3565 : 4 : range_tests_nonzero_bits ();
3566 : 4 : range_tests_floats_various ();
3567 : 4 : range_tests_misc ();
3568 : 4 : }
3569 : :
3570 : : } // namespace selftest
3571 : :
3572 : : #endif // CHECKING_P
|
