1 /* Support routines for value ranges.
2 Copyright (C) 2019-2023 Free Software Foundation, Inc.
3 Major hacks by Aldy Hernandez <aldyh@redhat.com> and
4 Andrew MacLeod <amacleod@redhat.com>.
6 This file is part of GCC.
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)
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.
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/>. */
24 #include "coretypes.h"
29 #include "tree-pretty-print.h"
30 #include "value-range-pretty-print.h"
31 #include "fold-const.h"
32 #include "gimple-range.h"
35 irange::accept (const vrange_visitor
&v
) const
41 unsupported_range::accept (const vrange_visitor
&v
) const
46 // Convenience function only available for integers and pointers.
49 Value_Range::lower_bound () const
51 if (is_a
<irange
> (*m_vrange
))
52 return as_a
<irange
> (*m_vrange
).lower_bound ();
56 // Convenience function only available for integers and pointers.
59 Value_Range::upper_bound () const
61 if (is_a
<irange
> (*m_vrange
))
62 return as_a
<irange
> (*m_vrange
).upper_bound ();
67 Value_Range::dump (FILE *out
) const
72 fprintf (out
, "NULL");
76 debug (const Value_Range
&r
)
79 fprintf (stderr
, "\n");
83 debug (const irange_bitmask
&bm
)
86 fprintf (stderr
, "\n");
89 // Default vrange definitions.
92 vrange::contains_p (tree
) const
98 vrange::singleton_p (tree
*) const
104 vrange::set (tree min
, tree
, value_range_kind
)
106 set_varying (TREE_TYPE (min
));
110 vrange::type () const
112 return void_type_node
;
116 vrange::supports_type_p (const_tree
) const
122 vrange::set_undefined ()
124 m_kind
= VR_UNDEFINED
;
128 vrange::set_varying (tree
)
134 vrange::union_ (const vrange
&r
)
136 if (r
.undefined_p () || varying_p ())
138 if (undefined_p () || r
.varying_p ())
148 vrange::intersect (const vrange
&r
)
150 if (undefined_p () || r
.varying_p ())
152 if (r
.undefined_p ())
167 vrange::zero_p () const
173 vrange::nonzero_p () const
179 vrange::set_nonzero (tree type
)
185 vrange::set_zero (tree type
)
191 vrange::set_nonnegative (tree type
)
197 vrange::fits_p (const vrange
&) const
202 // Assignment operator for generic ranges. Copying incompatible types
206 vrange::operator= (const vrange
&src
)
208 if (is_a
<irange
> (src
))
209 as_a
<irange
> (*this) = as_a
<irange
> (src
);
210 else if (is_a
<frange
> (src
))
211 as_a
<frange
> (*this) = as_a
<frange
> (src
);
214 gcc_checking_assert (is_a
<unsupported_range
> (src
));
220 // Equality operator for generic ranges.
223 vrange::operator== (const vrange
&src
) const
225 if (is_a
<irange
> (src
))
226 return as_a
<irange
> (*this) == as_a
<irange
> (src
);
227 if (is_a
<frange
> (src
))
228 return as_a
<frange
> (*this) == as_a
<frange
> (src
);
232 // Wrapper for vrange_printer to dump a range to a file.
235 vrange::dump (FILE *file
) const
237 pretty_printer buffer
;
238 pp_needs_newline (&buffer
) = true;
239 buffer
.buffer
->stream
= file
;
240 vrange_printer
vrange_pp (&buffer
);
241 this->accept (vrange_pp
);
246 irange_bitmask::dump (FILE *file
) const
248 char buf
[WIDE_INT_PRINT_BUFFER_SIZE
], *p
;
249 pretty_printer buffer
;
251 pp_needs_newline (&buffer
) = true;
252 buffer
.buffer
->stream
= file
;
253 pp_string (&buffer
, "MASK ");
254 unsigned len_mask
, len_val
;
255 if (print_hex_buf_size (m_mask
, &len_mask
)
256 | print_hex_buf_size (m_value
, &len_val
))
257 p
= XALLOCAVEC (char, MAX (len_mask
, len_val
));
260 print_hex (m_mask
, p
);
261 pp_string (&buffer
, p
);
262 pp_string (&buffer
, " VALUE ");
263 print_hex (m_value
, p
);
264 pp_string (&buffer
, p
);
272 add_vrange (const vrange
&v
, inchash::hash
&hstate
,
275 if (v
.undefined_p ())
277 hstate
.add_int (VR_UNDEFINED
);
280 // Types are ignored throughout to inhibit two ranges being equal
281 // but having different hash values. This can happen when two
282 // ranges are equal and their types are different (but
283 // types_compatible_p is true).
284 if (is_a
<irange
> (v
))
286 const irange
&r
= as_a
<irange
> (v
);
288 hstate
.add_int (VR_VARYING
);
290 hstate
.add_int (VR_RANGE
);
291 for (unsigned i
= 0; i
< r
.num_pairs (); ++i
)
293 hstate
.add_wide_int (r
.lower_bound (i
));
294 hstate
.add_wide_int (r
.upper_bound (i
));
296 irange_bitmask bm
= r
.get_bitmask ();
297 hstate
.add_wide_int (bm
.value ());
298 hstate
.add_wide_int (bm
.mask ());
301 if (is_a
<frange
> (v
))
303 const frange
&r
= as_a
<frange
> (v
);
304 if (r
.known_isnan ())
305 hstate
.add_int (VR_NAN
);
308 hstate
.add_int (r
.varying_p () ? VR_VARYING
: VR_RANGE
);
309 hstate
.add_real_value (r
.lower_bound ());
310 hstate
.add_real_value (r
.upper_bound ());
312 nan_state nan
= r
.get_nan_state ();
313 hstate
.add_int (nan
.pos_p ());
314 hstate
.add_int (nan
.neg_p ());
320 } //namespace inchash
323 irange::nonnegative_p () const
325 return wi::ge_p (lower_bound (), 0, TYPE_SIGN (type ()));
329 irange::nonpositive_p () const
331 return wi::le_p (upper_bound (), 0, TYPE_SIGN (type ()));
335 irange::supports_type_p (const_tree type
) const
337 return supports_p (type
);
340 // Return TRUE if R fits in THIS.
343 irange::fits_p (const vrange
&r
) const
345 return m_max_ranges
>= as_a
<irange
> (r
).num_pairs ();
349 irange::set_nonnegative (tree type
)
352 wi::zero (TYPE_PRECISION (type
)),
353 wi::to_wide (TYPE_MAX_VALUE (type
)));
357 frange::accept (const vrange_visitor
&v
) const
362 // Flush denormal endpoints to the appropriate 0.0.
365 frange::flush_denormals_to_zero ()
367 if (undefined_p () || known_isnan ())
370 machine_mode mode
= TYPE_MODE (type ());
371 // Flush [x, -DENORMAL] to [x, -0.0].
372 if (real_isdenormal (&m_max
, mode
) && real_isneg (&m_max
))
374 if (HONOR_SIGNED_ZEROS (m_type
))
379 // Flush [+DENORMAL, x] to [+0.0, x].
380 if (real_isdenormal (&m_min
, mode
) && !real_isneg (&m_min
))
384 // Setter for franges.
387 frange::set (tree type
,
388 const REAL_VALUE_TYPE
&min
, const REAL_VALUE_TYPE
&max
,
389 const nan_state
&nan
, value_range_kind kind
)
406 gcc_checking_assert (!real_isnan (&min
) && !real_isnan (&max
));
412 if (HONOR_NANS (m_type
))
414 m_pos_nan
= nan
.pos_p ();
415 m_neg_nan
= nan
.neg_p ();
423 if (!MODE_HAS_SIGNED_ZEROS (TYPE_MODE (m_type
)))
425 if (real_iszero (&m_min
, 1))
427 if (real_iszero (&m_max
, 1))
430 else if (!HONOR_SIGNED_ZEROS (m_type
))
432 if (real_iszero (&m_max
, 1))
434 if (real_iszero (&m_min
, 0))
438 // For -ffinite-math-only we can drop ranges outside the
439 // representable numbers to min/max for the type.
440 if (!HONOR_INFINITIES (m_type
))
442 REAL_VALUE_TYPE min_repr
= frange_val_min (m_type
);
443 REAL_VALUE_TYPE max_repr
= frange_val_max (m_type
);
444 if (real_less (&m_min
, &min_repr
))
446 else if (real_less (&max_repr
, &m_min
))
448 if (real_less (&max_repr
, &m_max
))
450 else if (real_less (&m_max
, &min_repr
))
454 // Check for swapped ranges.
455 gcc_checking_assert (real_compare (LE_EXPR
, &min
, &max
));
460 // Setter for an frange defaulting the NAN possibility to +-NAN when
464 frange::set (tree type
,
465 const REAL_VALUE_TYPE
&min
, const REAL_VALUE_TYPE
&max
,
466 value_range_kind kind
)
468 set (type
, min
, max
, nan_state (true), kind
);
472 frange::set (tree min
, tree max
, value_range_kind kind
)
474 set (TREE_TYPE (min
),
475 *TREE_REAL_CST_PTR (min
), *TREE_REAL_CST_PTR (max
), kind
);
478 // Normalize range to VARYING or UNDEFINED, or vice versa. Return
479 // TRUE if anything changed.
481 // A range with no known properties can be dropped to VARYING.
482 // Similarly, a VARYING with any properties should be dropped to a
483 // VR_RANGE. Normalizing ranges upon changing them ensures there is
484 // only one representation for a given range.
487 frange::normalize_kind ()
489 if (m_kind
== VR_RANGE
490 && frange_val_is_min (m_min
, m_type
)
491 && frange_val_is_max (m_max
, m_type
))
493 if (!HONOR_NANS (m_type
) || (m_pos_nan
&& m_neg_nan
))
495 set_varying (m_type
);
499 else if (m_kind
== VR_VARYING
)
501 if (HONOR_NANS (m_type
) && (!m_pos_nan
|| !m_neg_nan
))
504 m_min
= frange_val_min (m_type
);
505 m_max
= frange_val_max (m_type
);
511 else if (m_kind
== VR_NAN
&& !m_pos_nan
&& !m_neg_nan
)
516 // Union or intersect the zero endpoints of two ranges. For example:
517 // [-0, x] U [+0, x] => [-0, x]
518 // [ x, -0] U [ x, +0] => [ x, +0]
519 // [-0, x] ^ [+0, x] => [+0, x]
520 // [ x, -0] ^ [ x, +0] => [ x, -0]
522 // UNION_P is true when performing a union, or false when intersecting.
525 frange::combine_zeros (const frange
&r
, bool union_p
)
527 gcc_checking_assert (!undefined_p () && !known_isnan ());
529 bool changed
= false;
530 if (real_iszero (&m_min
) && real_iszero (&r
.m_min
)
531 && real_isneg (&m_min
) != real_isneg (&r
.m_min
))
533 m_min
.sign
= union_p
;
536 if (real_iszero (&m_max
) && real_iszero (&r
.m_max
)
537 && real_isneg (&m_max
) != real_isneg (&r
.m_max
))
539 m_max
.sign
= !union_p
;
542 // If the signs are swapped, the resulting range is empty.
543 if (m_min
.sign
== 0 && m_max
.sign
== 1)
554 // Union two ranges when one is known to be a NAN.
557 frange::union_nans (const frange
&r
)
559 gcc_checking_assert (known_isnan () || r
.known_isnan ());
561 bool changed
= false;
562 if (known_isnan () && m_kind
!= r
.m_kind
)
569 if (m_pos_nan
!= r
.m_pos_nan
|| m_neg_nan
!= r
.m_neg_nan
)
571 m_pos_nan
|= r
.m_pos_nan
;
572 m_neg_nan
|= r
.m_neg_nan
;
584 frange::union_ (const vrange
&v
)
586 const frange
&r
= as_a
<frange
> (v
);
588 if (r
.undefined_p () || varying_p ())
590 if (undefined_p () || r
.varying_p ())
597 if (known_isnan () || r
.known_isnan ())
598 return union_nans (r
);
599 bool changed
= false;
600 if (m_pos_nan
!= r
.m_pos_nan
|| m_neg_nan
!= r
.m_neg_nan
)
602 m_pos_nan
|= r
.m_pos_nan
;
603 m_neg_nan
|= r
.m_neg_nan
;
607 // Combine endpoints.
608 if (real_less (&r
.m_min
, &m_min
))
613 if (real_less (&m_max
, &r
.m_max
))
619 if (HONOR_SIGNED_ZEROS (m_type
))
620 changed
|= combine_zeros (r
, true);
622 changed
|= normalize_kind ();
626 // Intersect two ranges when one is known to be a NAN.
629 frange::intersect_nans (const frange
&r
)
631 gcc_checking_assert (known_isnan () || r
.known_isnan ());
633 m_pos_nan
&= r
.m_pos_nan
;
634 m_neg_nan
&= r
.m_neg_nan
;
645 frange::intersect (const vrange
&v
)
647 const frange
&r
= as_a
<frange
> (v
);
649 if (undefined_p () || r
.varying_p ())
651 if (r
.undefined_p ())
663 if (known_isnan () || r
.known_isnan ())
664 return intersect_nans (r
);
665 bool changed
= false;
666 if (m_pos_nan
!= r
.m_pos_nan
|| m_neg_nan
!= r
.m_neg_nan
)
668 m_pos_nan
&= r
.m_pos_nan
;
669 m_neg_nan
&= r
.m_neg_nan
;
673 // Combine endpoints.
674 if (real_less (&m_min
, &r
.m_min
))
679 if (real_less (&r
.m_max
, &m_max
))
684 // If the endpoints are swapped, the resulting range is empty.
685 if (real_less (&m_max
, &m_min
))
696 if (HONOR_SIGNED_ZEROS (m_type
))
697 changed
|= combine_zeros (r
, false);
699 changed
|= normalize_kind ();
704 frange::operator= (const frange
&src
)
710 m_pos_nan
= src
.m_pos_nan
;
711 m_neg_nan
= src
.m_neg_nan
;
719 frange::operator== (const frange
&src
) const
721 if (m_kind
== src
.m_kind
)
727 return types_compatible_p (m_type
, src
.m_type
);
729 bool nan1
= known_isnan ();
730 bool nan2
= src
.known_isnan ();
734 return (m_pos_nan
== src
.m_pos_nan
735 && m_neg_nan
== src
.m_neg_nan
);
739 return (real_identical (&m_min
, &src
.m_min
)
740 && real_identical (&m_max
, &src
.m_max
)
741 && m_pos_nan
== src
.m_pos_nan
742 && m_neg_nan
== src
.m_neg_nan
743 && types_compatible_p (m_type
, src
.m_type
));
748 // Return TRUE if range contains R.
751 frange::contains_p (const REAL_VALUE_TYPE
&r
) const
753 gcc_checking_assert (m_kind
!= VR_ANTI_RANGE
);
764 if (!m_pos_nan
&& !m_neg_nan
)
766 // Both +NAN and -NAN are present.
767 if (m_pos_nan
&& m_neg_nan
)
769 return m_neg_nan
== r
.sign
;
774 if (real_compare (GE_EXPR
, &r
, &m_min
) && real_compare (LE_EXPR
, &r
, &m_max
))
776 // Make sure the signs are equal for signed zeros.
777 if (HONOR_SIGNED_ZEROS (m_type
) && real_iszero (&r
))
778 return r
.sign
== m_min
.sign
|| r
.sign
== m_max
.sign
;
784 // If range is a singleton, place it in RESULT and return TRUE. If
785 // RESULT is NULL, just return TRUE.
787 // A NAN can never be a singleton.
790 frange::internal_singleton_p (REAL_VALUE_TYPE
*result
) const
792 if (m_kind
== VR_RANGE
&& real_identical (&m_min
, &m_max
))
794 // Return false for any singleton that may be a NAN.
795 if (HONOR_NANS (m_type
) && maybe_isnan ())
798 if (MODE_COMPOSITE_P (TYPE_MODE (m_type
)))
800 // For IBM long doubles, if the value is +-Inf or is exactly
801 // representable in double, the other double could be +0.0
802 // or -0.0. Since this means there is more than one way to
803 // represent a value, return false to avoid propagating it.
804 // See libgcc/config/rs6000/ibm-ldouble-format for details.
805 if (real_isinf (&m_min
))
808 real_convert (&r
, DFmode
, &m_min
);
809 if (real_identical (&r
, &m_min
))
821 frange::singleton_p (tree
*result
) const
823 if (internal_singleton_p ())
826 *result
= build_real (m_type
, m_min
);
833 frange::singleton_p (REAL_VALUE_TYPE
&r
) const
835 return internal_singleton_p (&r
);
839 frange::supports_type_p (const_tree type
) const
841 return supports_p (type
);
845 frange::verify_range ()
848 gcc_checking_assert (HONOR_NANS (m_type
) || !maybe_isnan ());
852 gcc_checking_assert (!m_type
);
855 gcc_checking_assert (m_type
);
856 gcc_checking_assert (frange_val_is_min (m_min
, m_type
));
857 gcc_checking_assert (frange_val_is_max (m_max
, m_type
));
858 if (HONOR_NANS (m_type
))
859 gcc_checking_assert (m_pos_nan
&& m_neg_nan
);
861 gcc_checking_assert (!m_pos_nan
&& !m_neg_nan
);
864 gcc_checking_assert (m_type
);
867 gcc_checking_assert (m_type
);
868 gcc_checking_assert (m_pos_nan
|| m_neg_nan
);
874 // NANs cannot appear in the endpoints of a range.
875 gcc_checking_assert (!real_isnan (&m_min
) && !real_isnan (&m_max
));
877 // Make sure we don't have swapped ranges.
878 gcc_checking_assert (!real_less (&m_max
, &m_min
));
880 // [ +0.0, -0.0 ] is nonsensical.
881 gcc_checking_assert (!(real_iszero (&m_min
, 0) && real_iszero (&m_max
, 1)));
883 // If all the properties are clear, we better not span the entire
884 // domain, because that would make us varying.
885 if (m_pos_nan
&& m_neg_nan
)
886 gcc_checking_assert (!frange_val_is_min (m_min
, m_type
)
887 || !frange_val_is_max (m_max
, m_type
));
890 // We can't do much with nonzeros yet.
892 frange::set_nonzero (tree type
)
897 // We can't do much with nonzeros yet.
899 frange::nonzero_p () const
904 // Set range to [+0.0, +0.0] if honoring signed zeros, or [0.0, 0.0]
908 frange::set_zero (tree type
)
910 if (HONOR_SIGNED_ZEROS (type
))
912 set (type
, dconstm0
, dconst0
);
916 set (type
, dconst0
, dconst0
);
919 // Return TRUE for any zero regardless of sign.
922 frange::zero_p () const
924 return (m_kind
== VR_RANGE
925 && real_iszero (&m_min
)
926 && real_iszero (&m_max
));
929 // Set the range to non-negative numbers, that is [+0.0, +INF].
931 // The NAN in the resulting range (if HONOR_NANS) has a varying sign
932 // as there are no guarantees in IEEE 754 wrt to the sign of a NAN,
933 // except for copy, abs, and copysign. It is the responsibility of
934 // the caller to set the NAN's sign if desired.
937 frange::set_nonnegative (tree type
)
939 set (type
, dconst0
, frange_val_max (type
));
942 // Here we copy between any two irange's.
945 irange::operator= (const irange
&src
)
947 int needed
= src
.num_pairs ();
948 maybe_resize (needed
);
951 unsigned lim
= src
.m_num_ranges
;
952 if (lim
> m_max_ranges
)
955 for (x
= 0; x
< lim
* 2; ++x
)
956 m_base
[x
] = src
.m_base
[x
];
958 // If the range didn't fit, the last range should cover the rest.
959 if (lim
!= src
.m_num_ranges
)
960 m_base
[x
- 1] = src
.m_base
[src
.m_num_ranges
* 2 - 1];
965 m_bitmask
= src
.m_bitmask
;
966 if (m_max_ranges
== 1)
974 get_legacy_range (const irange
&r
, tree
&min
, tree
&max
)
976 if (r
.undefined_p ())
983 tree type
= r
.type ();
986 min
= wide_int_to_tree (type
, r
.lower_bound ());
987 max
= wide_int_to_tree (type
, r
.upper_bound ());
991 unsigned int precision
= TYPE_PRECISION (type
);
992 signop sign
= TYPE_SIGN (type
);
993 if (r
.num_pairs () > 1
995 && r
.lower_bound () == wi::min_value (precision
, sign
)
996 && r
.upper_bound () == wi::max_value (precision
, sign
))
998 int_range
<3> inv (r
);
1000 min
= wide_int_to_tree (type
, inv
.lower_bound (0));
1001 max
= wide_int_to_tree (type
, inv
.upper_bound (0));
1002 return VR_ANTI_RANGE
;
1005 min
= wide_int_to_tree (type
, r
.lower_bound ());
1006 max
= wide_int_to_tree (type
, r
.upper_bound ());
1010 /* Set value range to the canonical form of {VRTYPE, MIN, MAX, EQUIV}.
1011 This means adjusting VRTYPE, MIN and MAX representing the case of a
1012 wrapping range with MAX < MIN covering [MIN, type_max] U [type_min, MAX]
1013 as anti-rage ~[MAX+1, MIN-1]. Likewise for wrapping anti-ranges.
1014 In corner cases where MAX+1 or MIN-1 wraps this will fall back
1016 This routine exists to ease canonicalization in the case where we
1017 extract ranges from var + CST op limit. */
1020 irange::set (tree type
, const wide_int
&min
, const wide_int
&max
,
1021 value_range_kind kind
)
1023 unsigned prec
= TYPE_PRECISION (type
);
1024 signop sign
= TYPE_SIGN (type
);
1025 wide_int min_value
= wi::min_value (prec
, sign
);
1026 wide_int max_value
= wi::max_value (prec
, sign
);
1029 m_bitmask
.set_unknown (prec
);
1031 if (kind
== VR_RANGE
)
1036 if (min
== min_value
&& max
== max_value
)
1037 m_kind
= VR_VARYING
;
1043 gcc_checking_assert (kind
== VR_ANTI_RANGE
);
1044 gcc_checking_assert (m_max_ranges
> 1);
1046 m_kind
= VR_UNDEFINED
;
1048 wi::overflow_type ovf
;
1051 lim
= wi::add (min
, -1, sign
, &ovf
);
1053 lim
= wi::sub (min
, 1, sign
, &ovf
);
1058 m_base
[0] = min_value
;
1063 lim
= wi::sub (max
, -1, sign
, &ovf
);
1065 lim
= wi::add (max
, 1, sign
, &ovf
);
1069 m_base
[m_num_ranges
* 2] = lim
;
1070 m_base
[m_num_ranges
* 2 + 1] = max_value
;
1080 irange::set (tree min
, tree max
, value_range_kind kind
)
1082 if (POLY_INT_CST_P (min
) || POLY_INT_CST_P (max
))
1084 set_varying (TREE_TYPE (min
));
1088 gcc_checking_assert (TREE_CODE (min
) == INTEGER_CST
);
1089 gcc_checking_assert (TREE_CODE (max
) == INTEGER_CST
);
1091 return set (TREE_TYPE (min
), wi::to_wide (min
), wi::to_wide (max
), kind
);
1094 // Check the validity of the range.
1097 irange::verify_range ()
1099 gcc_checking_assert (m_discriminator
== VR_IRANGE
);
1100 if (m_kind
== VR_UNDEFINED
)
1102 gcc_checking_assert (m_num_ranges
== 0);
1105 gcc_checking_assert (m_num_ranges
<= m_max_ranges
);
1107 // Legacy allowed these to represent VARYING for unknown types.
1108 // Leave this in for now, until all users are converted. Eventually
1109 // we should abort in set_varying.
1110 if (m_kind
== VR_VARYING
&& m_type
== error_mark_node
)
1113 unsigned prec
= TYPE_PRECISION (m_type
);
1114 if (m_kind
== VR_VARYING
)
1116 gcc_checking_assert (m_bitmask
.unknown_p ());
1117 gcc_checking_assert (m_num_ranges
== 1);
1118 gcc_checking_assert (varying_compatible_p ());
1119 gcc_checking_assert (lower_bound ().get_precision () == prec
);
1120 gcc_checking_assert (upper_bound ().get_precision () == prec
);
1123 gcc_checking_assert (m_num_ranges
!= 0);
1124 gcc_checking_assert (!varying_compatible_p ());
1125 for (unsigned i
= 0; i
< m_num_ranges
; ++i
)
1127 wide_int lb
= lower_bound (i
);
1128 wide_int ub
= upper_bound (i
);
1129 gcc_checking_assert (lb
.get_precision () == prec
);
1130 gcc_checking_assert (ub
.get_precision () == prec
);
1131 int c
= wi::cmp (lb
, ub
, TYPE_SIGN (m_type
));
1132 gcc_checking_assert (c
== 0 || c
== -1);
1134 m_bitmask
.verify_mask ();
1138 irange::operator== (const irange
&other
) const
1140 if (m_num_ranges
!= other
.m_num_ranges
)
1143 if (m_num_ranges
== 0)
1146 signop sign1
= TYPE_SIGN (type ());
1147 signop sign2
= TYPE_SIGN (other
.type ());
1149 for (unsigned i
= 0; i
< m_num_ranges
; ++i
)
1151 widest_int lb
= widest_int::from (lower_bound (i
), sign1
);
1152 widest_int ub
= widest_int::from (upper_bound (i
), sign1
);
1153 widest_int lb_other
= widest_int::from (other
.lower_bound (i
), sign2
);
1154 widest_int ub_other
= widest_int::from (other
.upper_bound (i
), sign2
);
1155 if (lb
!= lb_other
|| ub
!= ub_other
)
1159 irange_bitmask bm1
= get_bitmask ();
1160 irange_bitmask bm2
= other
.get_bitmask ();
1161 widest_int tmp1
= widest_int::from (bm1
.mask (), sign1
);
1162 widest_int tmp2
= widest_int::from (bm2
.mask (), sign2
);
1165 if (bm1
.unknown_p ())
1167 tmp1
= widest_int::from (bm1
.value (), sign1
);
1168 tmp2
= widest_int::from (bm2
.value (), sign2
);
1169 return tmp1
== tmp2
;
1172 /* If range is a singleton, place it in RESULT and return TRUE. */
1175 irange::singleton_p (tree
*result
) const
1177 if (num_pairs () == 1 && lower_bound () == upper_bound ())
1180 *result
= wide_int_to_tree (type (), lower_bound ());
1187 irange::singleton_p (wide_int
&w
) const
1189 if (num_pairs () == 1 && lower_bound () == upper_bound ())
1197 /* Return 1 if CST is inside value range.
1198 0 if CST is not inside value range.
1200 Benchmark compile/20001226-1.c compilation time after changing this
1204 irange::contains_p (const wide_int
&cst
) const
1209 // See if we can exclude CST based on the known 0 bits.
1210 if (!m_bitmask
.unknown_p ()
1212 && wi::bit_and (m_bitmask
.get_nonzero_bits (), cst
) == 0)
1215 signop sign
= TYPE_SIGN (type ());
1216 for (unsigned r
= 0; r
< m_num_ranges
; ++r
)
1218 if (wi::lt_p (cst
, lower_bound (r
), sign
))
1220 if (wi::le_p (cst
, upper_bound (r
), sign
))
1227 // Perform an efficient union with R when both ranges have only a single pair.
1228 // Excluded are VARYING and UNDEFINED ranges.
1231 irange::irange_single_pair_union (const irange
&r
)
1233 gcc_checking_assert (!undefined_p () && !varying_p ());
1234 gcc_checking_assert (!r
.undefined_p () && !varying_p ());
1236 signop sign
= TYPE_SIGN (m_type
);
1237 // Check if current lower bound is also the new lower bound.
1238 if (wi::le_p (m_base
[0], r
.m_base
[0], sign
))
1240 // If current upper bound is new upper bound, we're done.
1241 if (wi::le_p (r
.m_base
[1], m_base
[1], sign
))
1242 return union_bitmask (r
);
1243 // Otherwise R has the new upper bound.
1244 // Check for overlap/touching ranges, or single target range.
1245 if (m_max_ranges
== 1
1246 || (widest_int::from (m_base
[1], sign
) + 1
1247 >= widest_int::from (r
.m_base
[0], TYPE_SIGN (r
.m_type
))))
1248 m_base
[1] = r
.m_base
[1];
1251 // This is a dual range result.
1252 m_base
[2] = r
.m_base
[0];
1253 m_base
[3] = r
.m_base
[1];
1256 // The range has been altered, so normalize it even if nothing
1257 // changed in the mask.
1258 if (!union_bitmask (r
))
1265 // Set the new lower bound to R's lower bound.
1266 wide_int lb
= m_base
[0];
1267 m_base
[0] = r
.m_base
[0];
1269 // If R fully contains THIS range, just set the upper bound.
1270 if (wi::ge_p (r
.m_base
[1], m_base
[1], sign
))
1271 m_base
[1] = r
.m_base
[1];
1272 // Check for overlapping ranges, or target limited to a single range.
1273 else if (m_max_ranges
== 1
1274 || (widest_int::from (r
.m_base
[1], TYPE_SIGN (r
.m_type
)) + 1
1275 >= widest_int::from (lb
, sign
)))
1279 // Left with 2 pairs.
1282 m_base
[3] = m_base
[1];
1283 m_base
[1] = r
.m_base
[1];
1285 // The range has been altered, so normalize it even if nothing
1286 // changed in the mask.
1287 if (!union_bitmask (r
))
1294 // Append R to this range, knowing that R occurs after all of these subranges.
1295 // Return TRUE as something must have changed.
1298 irange::union_append (const irange
&r
)
1300 // Check if the first range in R is an immmediate successor to the last
1301 // range, ths requiring a merge.
1302 signop sign
= TYPE_SIGN (m_type
);
1303 wide_int lb
= r
.lower_bound ();
1304 wide_int ub
= upper_bound ();
1306 if (widest_int::from (ub
, sign
) + 1
1307 == widest_int::from (lb
, sign
))
1309 m_base
[m_num_ranges
* 2 - 1] = r
.m_base
[1];
1312 maybe_resize (m_num_ranges
+ r
.m_num_ranges
- start
);
1313 for ( ; start
< r
.m_num_ranges
; start
++)
1315 // Merge the last ranges if it exceeds the maximum size.
1316 if (m_num_ranges
+ 1 > m_max_ranges
)
1318 m_base
[m_max_ranges
* 2 - 1] = r
.m_base
[r
.m_num_ranges
* 2 - 1];
1321 m_base
[m_num_ranges
* 2] = r
.m_base
[start
* 2];
1322 m_base
[m_num_ranges
* 2 + 1] = r
.m_base
[start
* 2 + 1];
1326 if (!union_bitmask (r
))
1333 // Return TRUE if anything changes.
1336 irange::union_ (const vrange
&v
)
1338 const irange
&r
= as_a
<irange
> (v
);
1340 if (r
.undefined_p ())
1356 set_varying (type ());
1360 // Special case one range union one range.
1361 if (m_num_ranges
== 1 && r
.m_num_ranges
== 1)
1362 return irange_single_pair_union (r
);
1364 signop sign
= TYPE_SIGN (m_type
);
1365 // Check for an append to the end.
1366 if (m_kind
== VR_RANGE
&& wi::gt_p (r
.lower_bound (), upper_bound (), sign
))
1367 return union_append (r
);
1369 // If this ranges fully contains R, then we need do nothing.
1370 if (irange_contains_p (r
))
1371 return union_bitmask (r
);
1373 // Do not worry about merging and such by reserving twice as many
1374 // pairs as needed, and then simply sort the 2 ranges into this
1375 // intermediate form.
1377 // The intermediate result will have the property that the beginning
1378 // of each range is <= the beginning of the next range. There may
1379 // be overlapping ranges at this point. I.e. this would be valid
1380 // [-20, 10], [-10, 0], [0, 20], [40, 90] as it satisfies this
1381 // constraint : -20 < -10 < 0 < 40. When the range is rebuilt into r,
1382 // the merge is performed.
1384 // [Xi,Yi]..[Xn,Yn] U [Xj,Yj]..[Xm,Ym] --> [Xk,Yk]..[Xp,Yp]
1385 auto_vec
<wide_int
, 20> res (m_num_ranges
* 2 + r
.m_num_ranges
* 2);
1386 unsigned i
= 0, j
= 0, k
= 0;
1388 while (i
< m_num_ranges
* 2 && j
< r
.m_num_ranges
* 2)
1390 // lower of Xi and Xj is the lowest point.
1391 if (widest_int::from (m_base
[i
], sign
)
1392 <= widest_int::from (r
.m_base
[j
], sign
))
1394 res
.quick_push (m_base
[i
]);
1395 res
.quick_push (m_base
[i
+ 1]);
1401 res
.quick_push (r
.m_base
[j
]);
1402 res
.quick_push (r
.m_base
[j
+ 1]);
1407 for ( ; i
< m_num_ranges
* 2; i
+= 2)
1409 res
.quick_push (m_base
[i
]);
1410 res
.quick_push (m_base
[i
+ 1]);
1413 for ( ; j
< r
.m_num_ranges
* 2; j
+= 2)
1415 res
.quick_push (r
.m_base
[j
]);
1416 res
.quick_push (r
.m_base
[j
+ 1]);
1420 // Now normalize the vector removing any overlaps.
1422 for (j
= 2; j
< k
; j
+= 2)
1424 // Current upper+1 is >= lower bound next pair, then we merge ranges.
1425 if (widest_int::from (res
[i
- 1], sign
) + 1
1426 >= widest_int::from (res
[j
], sign
))
1428 // New upper bounds is greater of current or the next one.
1429 if (widest_int::from (res
[j
+ 1], sign
)
1430 > widest_int::from (res
[i
- 1], sign
))
1431 res
[i
- 1] = res
[j
+ 1];
1435 // This is a new distinct range, but no point in copying it
1436 // if it is already in the right place.
1440 res
[i
++] = res
[j
+ 1];
1447 // At this point, the vector should have i ranges, none overlapping.
1448 // Now it simply needs to be copied, and if there are too many
1449 // ranges, merge some. We wont do any analysis as to what the
1450 // "best" merges are, simply combine the final ranges into one.
1451 maybe_resize (i
/ 2);
1452 if (i
> m_max_ranges
* 2)
1454 res
[m_max_ranges
* 2 - 1] = res
[i
- 1];
1455 i
= m_max_ranges
* 2;
1458 for (j
= 0; j
< i
; j
++)
1459 m_base
[j
] = res
[j
];
1460 m_num_ranges
= i
/ 2;
1463 // The range has been altered, so normalize it even if nothing
1464 // changed in the mask.
1465 if (!union_bitmask (r
))
1472 // Return TRUE if THIS fully contains R. No undefined or varying cases.
1475 irange::irange_contains_p (const irange
&r
) const
1477 gcc_checking_assert (!undefined_p () && !varying_p ());
1478 gcc_checking_assert (!r
.undefined_p () && !varying_p ());
1480 // In order for THIS to fully contain R, all of the pairs within R must
1481 // be fully contained by the pairs in this object.
1482 signop sign
= TYPE_SIGN (m_type
);
1485 wide_int rl
= r
.m_base
[0];
1486 wide_int ru
= r
.m_base
[1];
1487 wide_int l
= m_base
[0];
1488 wide_int u
= m_base
[1];
1491 // If r is contained within this range, move to the next R
1492 if (wi::ge_p (rl
, l
, sign
)
1493 && wi::le_p (ru
, u
, sign
))
1495 // This pair is OK, Either done, or bump to the next.
1496 if (++ri
>= r
.num_pairs ())
1498 rl
= r
.m_base
[ri
* 2];
1499 ru
= r
.m_base
[ri
* 2 + 1];
1502 // Otherwise, check if this's pair occurs before R's.
1503 if (wi::lt_p (u
, rl
, sign
))
1505 // There's still at least one pair of R left.
1506 if (++i
>= num_pairs ())
1509 u
= m_base
[i
* 2 + 1];
1518 // Return TRUE if anything changes.
1521 irange::intersect (const vrange
&v
)
1523 const irange
&r
= as_a
<irange
> (v
);
1524 gcc_checking_assert (undefined_p () || r
.undefined_p ()
1525 || range_compatible_p (type (), r
.type ()));
1529 if (r
.undefined_p ())
1542 if (r
.num_pairs () == 1)
1544 bool res
= intersect (r
.lower_bound (), r
.upper_bound ());
1548 res
|= intersect_bitmask (r
);
1554 // If R fully contains this, then intersection will change nothing.
1555 if (r
.irange_contains_p (*this))
1556 return intersect_bitmask (r
);
1558 // ?? We could probably come up with something smarter than the
1559 // worst case scenario here.
1560 int needed
= num_pairs () + r
.num_pairs ();
1561 maybe_resize (needed
);
1563 signop sign
= TYPE_SIGN (m_type
);
1564 unsigned bld_pair
= 0;
1565 unsigned bld_lim
= m_max_ranges
;
1566 int_range_max
r2 (*this);
1567 unsigned r2_lim
= r2
.num_pairs ();
1569 for (unsigned i
= 0; i
< r
.num_pairs (); )
1571 // If r1's upper is < r2's lower, we can skip r1's pair.
1572 wide_int ru
= r
.m_base
[i
* 2 + 1];
1573 wide_int r2l
= r2
.m_base
[i2
* 2];
1574 if (wi::lt_p (ru
, r2l
, sign
))
1579 // Likewise, skip r2's pair if its excluded.
1580 wide_int r2u
= r2
.m_base
[i2
* 2 + 1];
1581 wide_int rl
= r
.m_base
[i
* 2];
1582 if (wi::lt_p (r2u
, rl
, sign
))
1587 // No more r2, break.
1591 // Must be some overlap. Find the highest of the lower bounds,
1592 // and set it, unless the build limits lower bounds is already
1594 if (bld_pair
< bld_lim
)
1596 if (wi::ge_p (rl
, r2l
, sign
))
1597 m_base
[bld_pair
* 2] = rl
;
1599 m_base
[bld_pair
* 2] = r2l
;
1602 // Decrease and set a new upper.
1605 // ...and choose the lower of the upper bounds.
1606 if (wi::le_p (ru
, r2u
, sign
))
1608 m_base
[bld_pair
* 2 + 1] = ru
;
1610 // Move past the r1 pair and keep trying.
1616 m_base
[bld_pair
* 2 + 1] = r2u
;
1621 // No more r2, break.
1624 // r2 has the higher lower bound.
1627 // At the exit of this loop, it is one of 2 things:
1628 // ran out of r1, or r2, but either means we are done.
1629 m_num_ranges
= bld_pair
;
1630 if (m_num_ranges
== 0)
1637 // The range has been altered, so normalize it even if nothing
1638 // changed in the mask.
1639 if (!intersect_bitmask (r
))
1647 // Multirange intersect for a specified wide_int [lb, ub] range.
1648 // Return TRUE if intersect changed anything.
1650 // NOTE: It is the caller's responsibility to intersect the mask.
1653 irange::intersect (const wide_int
& lb
, const wide_int
& ub
)
1655 // Undefined remains undefined.
1659 tree range_type
= type();
1660 signop sign
= TYPE_SIGN (range_type
);
1662 gcc_checking_assert (TYPE_PRECISION (range_type
) == wi::get_precision (lb
));
1663 gcc_checking_assert (TYPE_PRECISION (range_type
) == wi::get_precision (ub
));
1665 // If this range is fully contained, then intersection will do nothing.
1666 if (wi::ge_p (lower_bound (), lb
, sign
)
1667 && wi::le_p (upper_bound (), ub
, sign
))
1670 unsigned bld_index
= 0;
1671 unsigned pair_lim
= num_pairs ();
1672 for (unsigned i
= 0; i
< pair_lim
; i
++)
1674 wide_int pairl
= m_base
[i
* 2];
1675 wide_int pairu
= m_base
[i
* 2 + 1];
1676 // Once UB is less than a pairs lower bound, we're done.
1677 if (wi::lt_p (ub
, pairl
, sign
))
1679 // if LB is greater than this pairs upper, this pair is excluded.
1680 if (wi::lt_p (pairu
, lb
, sign
))
1683 // Must be some overlap. Find the highest of the lower bounds,
1685 if (wi::gt_p (lb
, pairl
, sign
))
1686 m_base
[bld_index
* 2] = lb
;
1688 m_base
[bld_index
* 2] = pairl
;
1690 // ...and choose the lower of the upper bounds and if the base pair
1691 // has the lower upper bound, need to check next pair too.
1692 if (wi::lt_p (ub
, pairu
, sign
))
1694 m_base
[bld_index
++ * 2 + 1] = ub
;
1698 m_base
[bld_index
++ * 2 + 1] = pairu
;
1701 m_num_ranges
= bld_index
;
1702 if (m_num_ranges
== 0)
1709 // The caller must normalize and verify the range, as the bitmask
1710 // still needs to be handled.
1715 // Signed 1-bits are strange. You can't subtract 1, because you can't
1716 // represent the number 1. This works around that for the invert routine.
1718 static wide_int
inline
1719 subtract_one (const wide_int
&x
, tree type
, wi::overflow_type
&overflow
)
1721 if (TYPE_SIGN (type
) == SIGNED
)
1722 return wi::add (x
, -1, SIGNED
, &overflow
);
1724 return wi::sub (x
, 1, UNSIGNED
, &overflow
);
1727 // The analogous function for adding 1.
1729 static wide_int
inline
1730 add_one (const wide_int
&x
, tree type
, wi::overflow_type
&overflow
)
1732 if (TYPE_SIGN (type
) == SIGNED
)
1733 return wi::sub (x
, -1, SIGNED
, &overflow
);
1735 return wi::add (x
, 1, UNSIGNED
, &overflow
);
1738 // Return the inverse of a range.
1743 gcc_checking_assert (!undefined_p () && !varying_p ());
1745 // We always need one more set of bounds to represent an inverse, so
1746 // if we're at the limit, we can't properly represent things.
1748 // For instance, to represent the inverse of a 2 sub-range set
1749 // [5, 10][20, 30], we would need a 3 sub-range set
1750 // [-MIN, 4][11, 19][31, MAX].
1752 // In this case, return the most conservative thing.
1754 // However, if any of the extremes of the range are -MIN/+MAX, we
1755 // know we will not need an extra bound. For example:
1757 // INVERT([-MIN,20][30,40]) => [21,29][41,+MAX]
1758 // INVERT([-MIN,20][30,MAX]) => [21,29]
1759 tree ttype
= type ();
1760 unsigned prec
= TYPE_PRECISION (ttype
);
1761 signop sign
= TYPE_SIGN (ttype
);
1762 wide_int type_min
= wi::min_value (prec
, sign
);
1763 wide_int type_max
= wi::max_value (prec
, sign
);
1764 m_bitmask
.set_unknown (prec
);
1766 // At this point, we need one extra sub-range to represent the
1768 maybe_resize (m_num_ranges
+ 1);
1770 // The algorithm is as follows. To calculate INVERT ([a,b][c,d]), we
1771 // generate [-MIN, a-1][b+1, c-1][d+1, MAX].
1773 // If there is an over/underflow in the calculation for any
1774 // sub-range, we eliminate that subrange. This allows us to easily
1775 // calculate INVERT([-MIN, 5]) with: [-MIN, -MIN-1][6, MAX]. And since
1776 // we eliminate the underflow, only [6, MAX] remains.
1778 wi::overflow_type ovf
;
1779 // Construct leftmost range.
1780 int_range_max
orig_range (*this);
1781 unsigned nitems
= 0;
1783 // If this is going to underflow on the MINUS 1, don't even bother
1784 // checking. This also handles subtracting one from an unsigned 0,
1785 // which doesn't set the underflow bit.
1786 if (type_min
!= orig_range
.lower_bound ())
1788 m_base
[nitems
++] = type_min
;
1789 tmp
= subtract_one (orig_range
.lower_bound (), ttype
, ovf
);
1790 m_base
[nitems
++] = tmp
;
1795 // Construct middle ranges if applicable.
1796 if (orig_range
.num_pairs () > 1)
1799 for (; j
< (orig_range
.num_pairs () * 2) - 1; j
+= 2)
1801 // The middle ranges cannot have MAX/MIN, so there's no need
1802 // to check for unsigned overflow on the +1 and -1 here.
1803 tmp
= wi::add (orig_range
.m_base
[j
], 1, sign
, &ovf
);
1804 m_base
[nitems
++] = tmp
;
1805 tmp
= subtract_one (orig_range
.m_base
[j
+ 1], ttype
, ovf
);
1806 m_base
[nitems
++] = tmp
;
1812 // Construct rightmost range.
1814 // However, if this will overflow on the PLUS 1, don't even bother.
1815 // This also handles adding one to an unsigned MAX, which doesn't
1816 // set the overflow bit.
1817 if (type_max
!= orig_range
.m_base
[i
])
1819 tmp
= add_one (orig_range
.m_base
[i
], ttype
, ovf
);
1820 m_base
[nitems
++] = tmp
;
1821 m_base
[nitems
++] = type_max
;
1825 m_num_ranges
= nitems
/ 2;
1827 // We disallow undefined or varying coming in, so the result can
1828 // only be a VR_RANGE.
1829 gcc_checking_assert (m_kind
== VR_RANGE
);
1835 // Return the bitmask inherent in the range.
1838 irange::get_bitmask_from_range () const
1840 unsigned prec
= TYPE_PRECISION (type ());
1841 wide_int min
= lower_bound ();
1842 wide_int max
= upper_bound ();
1844 // All the bits of a singleton are known.
1847 wide_int mask
= wi::zero (prec
);
1848 wide_int value
= lower_bound ();
1849 return irange_bitmask (value
, mask
);
1852 wide_int xorv
= min
^ max
;
1855 xorv
= wi::mask (prec
- wi::clz (xorv
), false, prec
);
1857 return irange_bitmask (wi::zero (prec
), min
| xorv
);
1860 // If the the mask can be trivially converted to a range, do so and
1864 irange::set_range_from_bitmask ()
1866 gcc_checking_assert (!undefined_p ());
1867 if (m_bitmask
.unknown_p ())
1870 // If all the bits are known, this is a singleton.
1871 if (m_bitmask
.mask () == 0)
1873 set (m_type
, m_bitmask
.value (), m_bitmask
.value ());
1877 unsigned popcount
= wi::popcount (m_bitmask
.get_nonzero_bits ());
1879 // If we have only one bit set in the mask, we can figure out the
1880 // range immediately.
1883 // Make sure we don't pessimize the range.
1884 if (!contains_p (m_bitmask
.get_nonzero_bits ()))
1887 bool has_zero
= contains_zero_p (*this);
1888 wide_int nz
= m_bitmask
.get_nonzero_bits ();
1889 set (m_type
, nz
, nz
);
1890 m_bitmask
.set_nonzero_bits (nz
);
1894 zero
.set_zero (type ());
1901 else if (popcount
== 0)
1910 irange::update_bitmask (const irange_bitmask
&bm
)
1912 gcc_checking_assert (!undefined_p ());
1914 // Drop VARYINGs with known bits to a plain range.
1915 if (m_kind
== VR_VARYING
&& !bm
.unknown_p ())
1919 if (!set_range_from_bitmask ())
1925 // Return the bitmask of known bits that includes the bitmask inherent
1929 irange::get_bitmask () const
1931 gcc_checking_assert (!undefined_p ());
1933 // The mask inherent in the range is calculated on-demand. For
1934 // example, [0,255] does not have known bits set by default. This
1935 // saves us considerable time, because setting it at creation incurs
1936 // a large penalty for irange::set. At the time of writing there
1937 // was a 5% slowdown in VRP if we kept the mask precisely up to date
1938 // at all times. Instead, we default to -1 and set it when
1939 // explicitly requested. However, this function will always return
1940 // the correct mask.
1942 // This also means that the mask may have a finer granularity than
1943 // the range and thus contradict it. Think of the mask as an
1944 // enhancement to the range. For example:
1946 // [3, 1000] MASK 0xfffffffe VALUE 0x0
1948 // 3 is in the range endpoints, but is excluded per the known 0 bits
1951 // See also the note in irange_bitmask::intersect.
1952 irange_bitmask bm
= get_bitmask_from_range ();
1953 if (!m_bitmask
.unknown_p ())
1954 bm
.intersect (m_bitmask
);
1958 // Set the nonzero bits in R into THIS. Return TRUE and
1959 // normalize the range if anything changed.
1962 irange::set_nonzero_bits (const wide_int
&bits
)
1964 gcc_checking_assert (!undefined_p ());
1965 irange_bitmask
bm (wi::zero (TYPE_PRECISION (type ())), bits
);
1966 update_bitmask (bm
);
1969 // Return the nonzero bits in R.
1972 irange::get_nonzero_bits () const
1974 gcc_checking_assert (!undefined_p ());
1975 irange_bitmask bm
= get_bitmask ();
1976 return bm
.value () | bm
.mask ();
1979 // Intersect the bitmask in R into THIS and normalize the range.
1980 // Return TRUE if the intersection changed anything.
1983 irange::intersect_bitmask (const irange
&r
)
1985 gcc_checking_assert (!undefined_p () && !r
.undefined_p ());
1987 if (m_bitmask
== r
.m_bitmask
)
1990 irange_bitmask bm
= get_bitmask ();
1991 irange_bitmask save
= bm
;
1992 if (!bm
.intersect (r
.get_bitmask ()))
1997 // Updating m_bitmask may still yield a semantic bitmask (as
1998 // returned by get_bitmask) which is functionally equivalent to what
1999 // we originally had. In which case, there's still no change.
2000 if (save
== get_bitmask ())
2003 if (!set_range_from_bitmask ())
2010 // Union the bitmask in R into THIS. Return TRUE and normalize the
2011 // range if anything changed.
2014 irange::union_bitmask (const irange
&r
)
2016 gcc_checking_assert (!undefined_p () && !r
.undefined_p ());
2018 if (m_bitmask
== r
.m_bitmask
)
2021 irange_bitmask bm
= get_bitmask ();
2022 irange_bitmask save
= bm
;
2023 if (!bm
.union_ (r
.get_bitmask ()))
2028 // Updating m_bitmask may still yield a semantic bitmask (as
2029 // returned by get_bitmask) which is functionally equivalent to what
2030 // we originally had. In which case, there's still no change.
2031 if (save
== get_bitmask ())
2034 // No need to call set_range_from_mask, because we'll never
2035 // narrow the range. Besides, it would cause endless recursion
2036 // because of the union_ in set_range_from_mask.
2042 irange_bitmask::verify_mask () const
2044 gcc_assert (m_value
.get_precision () == m_mask
.get_precision ());
2048 dump_value_range (FILE *file
, const vrange
*vr
)
2054 debug (const vrange
*vr
)
2056 dump_value_range (stderr
, vr
);
2057 fprintf (stderr
, "\n");
2061 debug (const vrange
&vr
)
2067 debug (const value_range
*vr
)
2069 dump_value_range (stderr
, vr
);
2070 fprintf (stderr
, "\n");
2074 debug (const value_range
&vr
)
2076 dump_value_range (stderr
, &vr
);
2077 fprintf (stderr
, "\n");
2080 /* Return true, if VAL1 and VAL2 are equal values for VRP purposes. */
2083 vrp_operand_equal_p (const_tree val1
, const_tree val2
)
2087 if (!val1
|| !val2
|| !operand_equal_p (val1
, val2
, 0))
2093 gt_ggc_mx (irange
*x
)
2095 if (!x
->undefined_p ())
2096 gt_ggc_mx (x
->m_type
);
2100 gt_pch_nx (irange
*x
)
2102 if (!x
->undefined_p ())
2103 gt_pch_nx (x
->m_type
);
2107 gt_pch_nx (irange
*x
, gt_pointer_operator op
, void *cookie
)
2109 for (unsigned i
= 0; i
< x
->m_num_ranges
; ++i
)
2111 op (&x
->m_base
[i
* 2], NULL
, cookie
);
2112 op (&x
->m_base
[i
* 2 + 1], NULL
, cookie
);
2117 gt_ggc_mx (frange
*x
)
2119 gt_ggc_mx (x
->m_type
);
2123 gt_pch_nx (frange
*x
)
2125 gt_pch_nx (x
->m_type
);
2129 gt_pch_nx (frange
*x
, gt_pointer_operator op
, void *cookie
)
2131 op (&x
->m_type
, NULL
, cookie
);
2135 gt_ggc_mx (vrange
*x
)
2137 if (is_a
<irange
> (*x
))
2138 return gt_ggc_mx ((irange
*) x
);
2139 if (is_a
<frange
> (*x
))
2140 return gt_ggc_mx ((frange
*) x
);
2145 gt_pch_nx (vrange
*x
)
2147 if (is_a
<irange
> (*x
))
2148 return gt_pch_nx ((irange
*) x
);
2149 if (is_a
<frange
> (*x
))
2150 return gt_pch_nx ((frange
*) x
);
2155 gt_pch_nx (vrange
*x
, gt_pointer_operator op
, void *cookie
)
2157 if (is_a
<irange
> (*x
))
2158 gt_pch_nx ((irange
*) x
, op
, cookie
);
2159 else if (is_a
<frange
> (*x
))
2160 gt_pch_nx ((frange
*) x
, op
, cookie
);
2165 #define DEFINE_INT_RANGE_INSTANCE(N) \
2166 template int_range<N>::int_range(tree_node *, \
2169 value_range_kind); \
2170 template int_range<N>::int_range(tree); \
2171 template int_range<N>::int_range(const irange &); \
2172 template int_range<N>::int_range(const int_range &); \
2173 template int_range<N>& int_range<N>::operator= (const int_range &);
2175 DEFINE_INT_RANGE_INSTANCE(1)
2176 DEFINE_INT_RANGE_INSTANCE(2)
2177 DEFINE_INT_RANGE_INSTANCE(3)
2178 DEFINE_INT_RANGE_INSTANCE(255)
2181 #include "selftest.h"
2183 #define INT(x) wi::shwi ((x), TYPE_PRECISION (integer_type_node))
2184 #define UINT(x) wi::uhwi ((x), TYPE_PRECISION (unsigned_type_node))
2185 #define SCHAR(x) wi::shwi ((x), TYPE_PRECISION (signed_char_type_node))
2191 range (tree type
, int a
, int b
, value_range_kind kind
= VR_RANGE
)
2194 if (TYPE_UNSIGNED (type
))
2196 w1
= wi::uhwi (a
, TYPE_PRECISION (type
));
2197 w2
= wi::uhwi (b
, TYPE_PRECISION (type
));
2201 w1
= wi::shwi (a
, TYPE_PRECISION (type
));
2202 w2
= wi::shwi (b
, TYPE_PRECISION (type
));
2204 return int_range
<2> (type
, w1
, w2
, kind
);
2208 range_int (int a
, int b
, value_range_kind kind
= VR_RANGE
)
2210 return range (integer_type_node
, a
, b
, kind
);
2214 range_uint (int a
, int b
, value_range_kind kind
= VR_RANGE
)
2216 return range (unsigned_type_node
, a
, b
, kind
);
2220 range_uint128 (int a
, int b
, value_range_kind kind
= VR_RANGE
)
2222 tree u128_type_node
= build_nonstandard_integer_type (128, 1);
2223 return range (u128_type_node
, a
, b
, kind
);
2227 range_uchar (int a
, int b
, value_range_kind kind
= VR_RANGE
)
2229 return range (unsigned_char_type_node
, a
, b
, kind
);
2233 range_char (int a
, int b
, value_range_kind kind
= VR_RANGE
)
2235 return range (signed_char_type_node
, a
, b
, kind
);
2239 build_range3 (int a
, int b
, int c
, int d
, int e
, int f
)
2241 int_range
<3> i1
= range_int (a
, b
);
2242 int_range
<3> i2
= range_int (c
, d
);
2243 int_range
<3> i3
= range_int (e
, f
);
2250 range_tests_irange3 ()
2252 int_range
<3> r0
, r1
, r2
;
2253 int_range
<3> i1
, i2
, i3
;
2255 // ([10,20] U [5,8]) U [1,3] ==> [1,3][5,8][10,20].
2256 r0
= range_int (10, 20);
2257 r1
= range_int (5, 8);
2259 r1
= range_int (1, 3);
2261 ASSERT_TRUE (r0
== build_range3 (1, 3, 5, 8, 10, 20));
2263 // [1,3][5,8][10,20] U [-5,0] => [-5,3][5,8][10,20].
2264 r1
= range_int (-5, 0);
2266 ASSERT_TRUE (r0
== build_range3 (-5, 3, 5, 8, 10, 20));
2268 // [10,20][30,40] U [50,60] ==> [10,20][30,40][50,60].
2269 r1
= range_int (50, 60);
2270 r0
= range_int (10, 20);
2271 r0
.union_ (range_int (30, 40));
2273 ASSERT_TRUE (r0
== build_range3 (10, 20, 30, 40, 50, 60));
2274 // [10,20][30,40][50,60] U [70, 80] ==> [10,20][30,40][50,60][70,80].
2275 r1
= range_int (70, 80);
2278 r2
= build_range3 (10, 20, 30, 40, 50, 60);
2279 r2
.union_ (range_int (70, 80));
2280 ASSERT_TRUE (r0
== r2
);
2282 // [10,20][30,40][50,60] U [6,35] => [6,40][50,60].
2283 r0
= build_range3 (10, 20, 30, 40, 50, 60);
2284 r1
= range_int (6, 35);
2286 r1
= range_int (6, 40);
2287 r1
.union_ (range_int (50, 60));
2288 ASSERT_TRUE (r0
== r1
);
2290 // [10,20][30,40][50,60] U [6,60] => [6,60].
2291 r0
= build_range3 (10, 20, 30, 40, 50, 60);
2292 r1
= range_int (6, 60);
2294 ASSERT_TRUE (r0
== range_int (6, 60));
2296 // [10,20][30,40][50,60] U [6,70] => [6,70].
2297 r0
= build_range3 (10, 20, 30, 40, 50, 60);
2298 r1
= range_int (6, 70);
2300 ASSERT_TRUE (r0
== range_int (6, 70));
2302 // [10,20][30,40][50,60] U [35,70] => [10,20][30,70].
2303 r0
= build_range3 (10, 20, 30, 40, 50, 60);
2304 r1
= range_int (35, 70);
2306 r1
= range_int (10, 20);
2307 r1
.union_ (range_int (30, 70));
2308 ASSERT_TRUE (r0
== r1
);
2310 // [10,20][30,40][50,60] U [15,35] => [10,40][50,60].
2311 r0
= build_range3 (10, 20, 30, 40, 50, 60);
2312 r1
= range_int (15, 35);
2314 r1
= range_int (10, 40);
2315 r1
.union_ (range_int (50, 60));
2316 ASSERT_TRUE (r0
== r1
);
2318 // [10,20][30,40][50,60] U [35,35] => [10,20][30,40][50,60].
2319 r0
= build_range3 (10, 20, 30, 40, 50, 60);
2320 r1
= range_int (35, 35);
2322 ASSERT_TRUE (r0
== build_range3 (10, 20, 30, 40, 50, 60));
2326 range_tests_int_range_max ()
2329 unsigned int nrange
;
2331 // Build a huge multi-range range.
2332 for (nrange
= 0; nrange
< 50; ++nrange
)
2334 int_range
<1> tmp
= range_int (nrange
*10, nrange
*10 + 5);
2337 ASSERT_TRUE (big
.num_pairs () == nrange
);
2339 // Verify that we can copy it without loosing precision.
2340 int_range_max
copy (big
);
2341 ASSERT_TRUE (copy
.num_pairs () == nrange
);
2343 // Inverting it should produce one more sub-range.
2345 ASSERT_TRUE (big
.num_pairs () == nrange
+ 1);
2347 int_range
<1> tmp
= range_int (5, 37);
2348 big
.intersect (tmp
);
2349 ASSERT_TRUE (big
.num_pairs () == 4);
2351 // Test that [10,10][20,20] does NOT contain 15.
2353 int_range_max i1
= range_int (10, 10);
2354 int_range_max i2
= range_int (20, 20);
2356 ASSERT_FALSE (i1
.contains_p (INT (15)));
2360 // Simulate -fstrict-enums where the domain of a type is less than the
2364 range_tests_strict_enum ()
2366 // The enum can only hold [0, 3].
2367 tree rtype
= copy_node (unsigned_type_node
);
2368 TYPE_MIN_VALUE (rtype
) = build_int_cstu (rtype
, 0);
2369 TYPE_MAX_VALUE (rtype
) = build_int_cstu (rtype
, 3);
2371 // Test that even though vr1 covers the strict enum domain ([0, 3]),
2372 // it does not cover the domain of the underlying type.
2373 int_range
<1> vr1
= range (rtype
, 0, 1);
2374 int_range
<1> vr2
= range (rtype
, 2, 3);
2376 ASSERT_TRUE (vr1
== range (rtype
, 0, 3));
2377 ASSERT_FALSE (vr1
.varying_p ());
2379 // Test that copying to a multi-range does not change things.
2380 int_range
<2> ir1 (vr1
);
2381 ASSERT_TRUE (ir1
== vr1
);
2382 ASSERT_FALSE (ir1
.varying_p ());
2384 // The same test as above, but using TYPE_{MIN,MAX}_VALUE instead of [0,3].
2385 vr1
= int_range
<2> (rtype
,
2386 wi::to_wide (TYPE_MIN_VALUE (rtype
)),
2387 wi::to_wide (TYPE_MAX_VALUE (rtype
)));
2389 ASSERT_TRUE (ir1
== vr1
);
2390 ASSERT_FALSE (ir1
.varying_p ());
2396 tree u128_type
= build_nonstandard_integer_type (128, /*unsigned=*/1);
2397 int_range
<2> i1
, i2
, i3
;
2398 int_range
<2> r0
, r1
, rold
;
2400 // Test 1-bit signed integer union.
2401 // [-1,-1] U [0,0] = VARYING.
2402 tree one_bit_type
= build_nonstandard_integer_type (1, 0);
2403 wide_int one_bit_min
= irange_val_min (one_bit_type
);
2404 wide_int one_bit_max
= irange_val_max (one_bit_type
);
2406 int_range
<2> min
= int_range
<2> (one_bit_type
, one_bit_min
, one_bit_min
);
2407 int_range
<2> max
= int_range
<2> (one_bit_type
, one_bit_max
, one_bit_max
);
2409 ASSERT_TRUE (max
.varying_p ());
2411 // Test that we can set a range of true+false for a 1-bit signed int.
2412 r0
= range_true_and_false (one_bit_type
);
2414 // Test inversion of 1-bit signed integers.
2416 int_range
<2> min
= int_range
<2> (one_bit_type
, one_bit_min
, one_bit_min
);
2417 int_range
<2> max
= int_range
<2> (one_bit_type
, one_bit_max
, one_bit_max
);
2421 ASSERT_TRUE (t
== max
);
2424 ASSERT_TRUE (t
== min
);
2427 // Test that NOT(255) is [0..254] in 8-bit land.
2428 int_range
<1> not_255
= range_uchar (255, 255, VR_ANTI_RANGE
);
2429 ASSERT_TRUE (not_255
== range_uchar (0, 254));
2431 // Test that NOT(0) is [1..255] in 8-bit land.
2432 int_range
<2> not_zero
= range_nonzero (unsigned_char_type_node
);
2433 ASSERT_TRUE (not_zero
== range_uchar (1, 255));
2435 // Check that [0,127][0x..ffffff80,0x..ffffff]
2436 // => ~[128, 0x..ffffff7f].
2437 r0
= range_uint128 (0, 127);
2438 wide_int high
= wi::minus_one (128);
2439 // low = -1 - 127 => 0x..ffffff80.
2440 wide_int low
= wi::sub (high
, wi::uhwi (127, 128));
2441 r1
= int_range
<1> (u128_type
, low
, high
); // [0x..ffffff80, 0x..ffffffff]
2442 // r0 = [0,127][0x..ffffff80,0x..fffffff].
2444 // r1 = [128, 0x..ffffff7f].
2445 r1
= int_range
<1> (u128_type
,
2446 wi::uhwi (128, 128),
2447 wi::sub (wi::minus_one (128), wi::uhwi (128, 128)));
2449 ASSERT_TRUE (r0
== r1
);
2451 r0
.set_varying (integer_type_node
);
2452 wide_int minint
= r0
.lower_bound ();
2453 wide_int maxint
= r0
.upper_bound ();
2455 r0
.set_varying (short_integer_type_node
);
2457 r0
.set_varying (unsigned_type_node
);
2458 wide_int maxuint
= r0
.upper_bound ();
2460 // Check that ~[0,5] => [6,MAX] for unsigned int.
2461 r0
= range_uint (0, 5);
2463 ASSERT_TRUE (r0
== int_range
<1> (unsigned_type_node
,
2464 wi::uhwi (6, TYPE_PRECISION (unsigned_type_node
)),
2467 // Check that ~[10,MAX] => [0,9] for unsigned int.
2468 r0
= int_range
<1> (unsigned_type_node
,
2469 wi::uhwi (10, TYPE_PRECISION (unsigned_type_node
)),
2472 ASSERT_TRUE (r0
== range_uint (0, 9));
2474 // Check that ~[0,5] => [6,MAX] for unsigned 128-bit numbers.
2475 r0
= range_uint128 (0, 5, VR_ANTI_RANGE
);
2476 r1
= int_range
<1> (u128_type
, wi::uhwi (6, 128), wi::minus_one (128));
2477 ASSERT_TRUE (r0
== r1
);
2479 // Check that [~5] is really [-MIN,4][6,MAX].
2480 r0
= range_int (5, 5, VR_ANTI_RANGE
);
2481 r1
= int_range
<1> (integer_type_node
, minint
, INT (4));
2482 r1
.union_ (int_range
<1> (integer_type_node
, INT (6), maxint
));
2483 ASSERT_FALSE (r1
.undefined_p ());
2484 ASSERT_TRUE (r0
== r1
);
2486 r1
= range_int (5, 5);
2487 int_range
<2> r2 (r1
);
2488 ASSERT_TRUE (r1
== r2
);
2490 r1
= range_int (5, 10);
2492 r1
= range_int (5, 10);
2493 ASSERT_TRUE (r1
.contains_p (INT (7)));
2495 r1
= range_char (0, 20);
2496 ASSERT_TRUE (r1
.contains_p (SCHAR(15)));
2497 ASSERT_FALSE (r1
.contains_p (SCHAR(300)));
2499 // NOT([10,20]) ==> [-MIN,9][21,MAX].
2500 r0
= r1
= range_int (10, 20);
2501 r2
= int_range
<1> (integer_type_node
, minint
, INT(9));
2502 r2
.union_ (int_range
<1> (integer_type_node
, INT(21), maxint
));
2503 ASSERT_FALSE (r2
.undefined_p ());
2505 ASSERT_TRUE (r1
== r2
);
2506 // Test that NOT(NOT(x)) == x.
2508 ASSERT_TRUE (r0
== r2
);
2510 // Test that booleans and their inverse work as expected.
2511 r0
= range_zero (boolean_type_node
);
2512 ASSERT_TRUE (r0
== range_false ());
2514 ASSERT_TRUE (r0
== range_true ());
2516 // Make sure NULL and non-NULL of pointer types work, and that
2517 // inverses of them are consistent.
2518 tree voidp
= build_pointer_type (void_type_node
);
2519 r0
= range_zero (voidp
);
2523 ASSERT_TRUE (r0
== r1
);
2525 // [10,20] U [15, 30] => [10, 30].
2526 r0
= range_int (10, 20);
2527 r1
= range_int (15, 30);
2529 ASSERT_TRUE (r0
== range_int (10, 30));
2531 // [15,40] U [] => [15,40].
2532 r0
= range_int (15, 40);
2533 r1
.set_undefined ();
2535 ASSERT_TRUE (r0
== range_int (15, 40));
2537 // [10,20] U [10,10] => [10,20].
2538 r0
= range_int (10, 20);
2539 r1
= range_int (10, 10);
2541 ASSERT_TRUE (r0
== range_int (10, 20));
2543 // [10,20] U [9,9] => [9,20].
2544 r0
= range_int (10, 20);
2545 r1
= range_int (9, 9);
2547 ASSERT_TRUE (r0
== range_int (9, 20));
2549 // [10,20] ^ [15,30] => [15,20].
2550 r0
= range_int (10, 20);
2551 r1
= range_int (15, 30);
2553 ASSERT_TRUE (r0
== range_int (15, 20));
2555 // Test the internal sanity of wide_int's wrt HWIs.
2556 ASSERT_TRUE (wi::max_value (TYPE_PRECISION (boolean_type_node
),
2557 TYPE_SIGN (boolean_type_node
))
2558 == wi::uhwi (1, TYPE_PRECISION (boolean_type_node
)));
2561 r0
= range_int (0, 0);
2562 ASSERT_TRUE (r0
.zero_p ());
2564 // Test nonzero_p().
2565 r0
= range_int (0, 0);
2567 ASSERT_TRUE (r0
.nonzero_p ());
2570 r0
= range_int (1, 1, VR_ANTI_RANGE
);
2572 r1
= range_int (3, 3, VR_ANTI_RANGE
);
2574 // vv = [0,0][2,2][4, MAX]
2575 int_range
<3> vv
= r0
;
2578 ASSERT_TRUE (vv
.contains_p (UINT (2)));
2579 ASSERT_TRUE (vv
.num_pairs () == 3);
2581 r0
= range_int (1, 1);
2582 // And union it with [0,0][2,2][4,MAX] multi range
2584 // The result should be [0,2][4,MAX], or ~[3,3] but it must contain 2
2585 ASSERT_TRUE (r0
.contains_p (INT (2)));
2589 range_tests_nonzero_bits ()
2591 int_range
<2> r0
, r1
;
2593 // Adding nonzero bits to a varying drops the varying.
2594 r0
.set_varying (integer_type_node
);
2595 r0
.set_nonzero_bits (INT (255));
2596 ASSERT_TRUE (!r0
.varying_p ());
2597 // Dropping the nonzero bits brings us back to varying.
2598 r0
.set_nonzero_bits (INT (-1));
2599 ASSERT_TRUE (r0
.varying_p ());
2601 // Test contains_p with nonzero bits.
2602 r0
.set_zero (integer_type_node
);
2603 ASSERT_TRUE (r0
.contains_p (INT (0)));
2604 ASSERT_FALSE (r0
.contains_p (INT (1)));
2605 r0
.set_nonzero_bits (INT (0xfe));
2606 ASSERT_FALSE (r0
.contains_p (INT (0x100)));
2607 ASSERT_FALSE (r0
.contains_p (INT (0x3)));
2609 // Union of nonzero bits.
2610 r0
.set_varying (integer_type_node
);
2611 r0
.set_nonzero_bits (INT (0xf0));
2612 r1
.set_varying (integer_type_node
);
2613 r1
.set_nonzero_bits (INT (0xf));
2615 ASSERT_TRUE (r0
.get_nonzero_bits () == 0xff);
2617 // Intersect of nonzero bits.
2618 r0
= range_int (0, 255);
2619 r0
.set_nonzero_bits (INT (0xfe));
2620 r1
.set_varying (integer_type_node
);
2621 r1
.set_nonzero_bits (INT (0xf0));
2623 ASSERT_TRUE (r0
.get_nonzero_bits () == 0xf0);
2625 // Intersect where the mask of nonzero bits is implicit from the range.
2626 r0
.set_varying (integer_type_node
);
2627 r1
= range_int (0, 255);
2629 ASSERT_TRUE (r0
.get_nonzero_bits () == 0xff);
2631 // The union of a mask of 0xff..ffff00 with a mask of 0xff spans the
2632 // entire domain, and makes the range a varying.
2633 r0
.set_varying (integer_type_node
);
2634 wide_int x
= wi::shwi (0xff, TYPE_PRECISION (integer_type_node
));
2635 x
= wi::bit_not (x
);
2636 r0
.set_nonzero_bits (x
); // 0xff..ff00
2637 r1
.set_varying (integer_type_node
);
2638 r1
.set_nonzero_bits (INT (0xff));
2640 ASSERT_TRUE (r0
.varying_p ());
2642 // Test that setting a nonzero bit of 1 does not pessimize the range.
2643 r0
.set_zero (integer_type_node
);
2644 r0
.set_nonzero_bits (INT (1));
2645 ASSERT_TRUE (r0
.zero_p ());
2648 // Build an frange from string endpoints.
2650 static inline frange
2651 frange_float (const char *lb
, const char *ub
, tree type
= float_type_node
)
2653 REAL_VALUE_TYPE min
, max
;
2654 gcc_assert (real_from_string (&min
, lb
) == 0);
2655 gcc_assert (real_from_string (&max
, ub
) == 0);
2656 return frange (type
, min
, max
);
2663 REAL_VALUE_TYPE q
, r
;
2666 // Equal ranges but with differing NAN bits are not equal.
2667 if (HONOR_NANS (float_type_node
))
2669 r1
= frange_float ("10", "12");
2677 // [10, 20] NAN ^ [30, 40] NAN = NAN.
2678 r0
= frange_float ("10", "20");
2679 r1
= frange_float ("30", "40");
2681 ASSERT_TRUE (r0
.known_isnan ());
2683 // [3,5] U [5,10] NAN = ... NAN
2684 r0
= frange_float ("3", "5");
2686 r1
= frange_float ("5", "10");
2688 ASSERT_TRUE (r0
.maybe_isnan ());
2691 // [5,6] U NAN = [5,6] NAN.
2692 r0
= frange_float ("5", "6");
2694 r1
.set_nan (float_type_node
);
2696 real_from_string (&q
, "5");
2697 real_from_string (&r
, "6");
2698 ASSERT_TRUE (real_identical (&q
, &r0
.lower_bound ()));
2699 ASSERT_TRUE (real_identical (&r
, &r0
.upper_bound ()));
2700 ASSERT_TRUE (r0
.maybe_isnan ());
2703 r0
.set_nan (float_type_node
);
2704 r1
.set_nan (float_type_node
);
2706 ASSERT_TRUE (r0
.known_isnan ());
2708 // [INF, INF] NAN ^ NAN = NAN
2709 r0
.set_nan (float_type_node
);
2710 r1
= frange_float ("+Inf", "+Inf");
2711 if (!HONOR_NANS (float_type_node
))
2714 ASSERT_TRUE (r0
.known_isnan ());
2717 r0
.set_nan (float_type_node
);
2718 r1
.set_nan (float_type_node
);
2720 ASSERT_TRUE (r0
.known_isnan ());
2722 // +NAN ^ -NAN = UNDEFINED
2723 r0
.set_nan (float_type_node
, false);
2724 r1
.set_nan (float_type_node
, true);
2726 ASSERT_TRUE (r0
.undefined_p ());
2728 // VARYING ^ NAN = NAN.
2729 r0
.set_nan (float_type_node
);
2730 r1
.set_varying (float_type_node
);
2732 ASSERT_TRUE (r0
.known_isnan ());
2734 // [3,4] ^ NAN = UNDEFINED.
2735 r0
= frange_float ("3", "4");
2737 r1
.set_nan (float_type_node
);
2739 ASSERT_TRUE (r0
.undefined_p ());
2741 // [-3, 5] ^ NAN = UNDEFINED
2742 r0
= frange_float ("-3", "5");
2744 r1
.set_nan (float_type_node
);
2746 ASSERT_TRUE (r0
.undefined_p ());
2748 // Setting the NAN bit to yes does not make us a known NAN.
2749 r0
.set_varying (float_type_node
);
2751 ASSERT_FALSE (r0
.known_isnan ());
2753 // NAN is in a VARYING.
2754 r0
.set_varying (float_type_node
);
2755 real_nan (&r
, "", 1, TYPE_MODE (float_type_node
));
2756 REAL_VALUE_TYPE nan
= r
;
2757 ASSERT_TRUE (r0
.contains_p (nan
));
2759 // -NAN is in a VARYING.
2760 r0
.set_varying (float_type_node
);
2761 q
= real_value_negate (&r
);
2762 REAL_VALUE_TYPE neg_nan
= q
;
2763 ASSERT_TRUE (r0
.contains_p (neg_nan
));
2765 // Clearing the NAN on a [] NAN is the empty set.
2766 r0
.set_nan (float_type_node
);
2768 ASSERT_TRUE (r0
.undefined_p ());
2770 // [10,20] NAN ^ [21,25] NAN = [NAN]
2771 r0
= frange_float ("10", "20");
2773 r1
= frange_float ("21", "25");
2776 ASSERT_TRUE (r0
.known_isnan ());
2778 // NAN U [5,6] should be [5,6] +-NAN.
2779 r0
.set_nan (float_type_node
);
2780 r1
= frange_float ("5", "6");
2783 real_from_string (&q
, "5");
2784 real_from_string (&r
, "6");
2785 ASSERT_TRUE (real_identical (&q
, &r0
.lower_bound ()));
2786 ASSERT_TRUE (real_identical (&r
, &r0
.upper_bound ()));
2787 ASSERT_TRUE (!r0
.signbit_p (signbit
));
2788 ASSERT_TRUE (r0
.maybe_isnan ());
2790 // NAN U NAN shouldn't change anything.
2791 r0
.set_nan (float_type_node
);
2792 r1
.set_nan (float_type_node
);
2793 ASSERT_FALSE (r0
.union_ (r1
));
2795 // [3,5] NAN U NAN shouldn't change anything.
2796 r0
= frange_float ("3", "5");
2797 r1
.set_nan (float_type_node
);
2798 ASSERT_FALSE (r0
.union_ (r1
));
2800 // [3,5] U NAN *does* trigger a change.
2801 r0
= frange_float ("3", "5");
2803 r1
.set_nan (float_type_node
);
2804 ASSERT_TRUE (r0
.union_ (r1
));
2808 range_tests_signed_zeros ()
2810 REAL_VALUE_TYPE zero
= dconst0
;
2811 REAL_VALUE_TYPE neg_zero
= zero
;
2816 // [0,0] contains [0,0] but not [-0,-0] and vice versa.
2817 r0
= frange_float ("0.0", "0.0");
2818 r1
= frange_float ("-0.0", "-0.0");
2819 ASSERT_TRUE (r0
.contains_p (zero
));
2820 ASSERT_TRUE (!r0
.contains_p (neg_zero
));
2821 ASSERT_TRUE (r1
.contains_p (neg_zero
));
2822 ASSERT_TRUE (!r1
.contains_p (zero
));
2824 // Test contains_p() when we know the sign of the zero.
2825 r0
= frange_float ("0.0", "0.0");
2826 ASSERT_TRUE (r0
.contains_p (zero
));
2827 ASSERT_FALSE (r0
.contains_p (neg_zero
));
2828 r0
= frange_float ("-0.0", "-0.0");
2829 ASSERT_TRUE (r0
.contains_p (neg_zero
));
2830 ASSERT_FALSE (r0
.contains_p (zero
));
2832 r0
= frange_float ("-0.0", "0.0");
2833 ASSERT_TRUE (r0
.contains_p (neg_zero
));
2834 ASSERT_TRUE (r0
.contains_p (zero
));
2836 r0
= frange_float ("-3", "5");
2837 ASSERT_TRUE (r0
.contains_p (neg_zero
));
2838 ASSERT_TRUE (r0
.contains_p (zero
));
2840 // The intersection of zeros that differ in sign is a NAN (or
2841 // undefined if not honoring NANs).
2842 r0
= frange_float ("-0.0", "-0.0");
2843 r1
= frange_float ("0.0", "0.0");
2845 if (HONOR_NANS (float_type_node
))
2846 ASSERT_TRUE (r0
.known_isnan ());
2848 ASSERT_TRUE (r0
.undefined_p ());
2850 // The union of zeros that differ in sign is a zero with unknown sign.
2851 r0
= frange_float ("0.0", "0.0");
2852 r1
= frange_float ("-0.0", "-0.0");
2854 ASSERT_TRUE (r0
.zero_p () && !r0
.signbit_p (signbit
));
2856 // [-0, +0] has an unknown sign.
2857 r0
= frange_float ("-0.0", "0.0");
2858 ASSERT_TRUE (r0
.zero_p () && !r0
.signbit_p (signbit
));
2860 // [-0, +0] ^ [0, 0] is [0, 0]
2861 r0
= frange_float ("-0.0", "0.0");
2862 r1
= frange_float ("0.0", "0.0");
2864 ASSERT_TRUE (r0
.zero_p ());
2866 r0
= frange_float ("+0", "5");
2868 ASSERT_TRUE (r0
.signbit_p (signbit
) && !signbit
);
2870 r0
= frange_float ("-0", "5");
2872 ASSERT_TRUE (!r0
.signbit_p (signbit
));
2874 r0
= frange_float ("-0", "10");
2875 r1
= frange_float ("0", "5");
2877 ASSERT_TRUE (real_iszero (&r0
.lower_bound (), false));
2879 r0
= frange_float ("-0", "5");
2880 r1
= frange_float ("0", "5");
2882 ASSERT_TRUE (real_iszero (&r0
.lower_bound (), true));
2884 r0
= frange_float ("-5", "-0");
2886 r1
= frange_float ("0", "0");
2889 if (HONOR_NANS (float_type_node
))
2890 ASSERT_TRUE (r0
.known_isnan ());
2892 ASSERT_TRUE (r0
.undefined_p ());
2894 r0
.set_nonnegative (float_type_node
);
2895 if (HONOR_NANS (float_type_node
))
2896 ASSERT_TRUE (r0
.maybe_isnan ());
2898 // Numbers containing zero should have an unknown SIGNBIT.
2899 r0
= frange_float ("0", "10");
2901 ASSERT_TRUE (r0
.signbit_p (signbit
) && !signbit
);
2905 range_tests_signbit ()
2910 // Negative numbers should have the SIGNBIT set.
2911 r0
= frange_float ("-5", "-1");
2913 ASSERT_TRUE (r0
.signbit_p (signbit
) && signbit
);
2914 // Positive numbers should have the SIGNBIT clear.
2915 r0
= frange_float ("1", "10");
2917 ASSERT_TRUE (r0
.signbit_p (signbit
) && !signbit
);
2918 // Numbers spanning both positive and negative should have an
2920 r0
= frange_float ("-10", "10");
2922 ASSERT_TRUE (!r0
.signbit_p (signbit
));
2923 r0
.set_varying (float_type_node
);
2924 ASSERT_TRUE (!r0
.signbit_p (signbit
));
2928 range_tests_floats ()
2932 if (HONOR_NANS (float_type_node
))
2934 range_tests_signbit ();
2936 if (HONOR_SIGNED_ZEROS (float_type_node
))
2937 range_tests_signed_zeros ();
2939 // A range of [-INF,+INF] is actually VARYING if no other properties
2941 r0
= frange_float ("-Inf", "+Inf");
2942 ASSERT_TRUE (r0
.varying_p ());
2943 // ...unless it has some special property...
2944 if (HONOR_NANS (r0
.type ()))
2947 ASSERT_FALSE (r0
.varying_p ());
2950 // For most architectures, where float and double are different
2951 // sizes, having the same endpoints does not necessarily mean the
2952 // ranges are equal.
2953 if (!types_compatible_p (float_type_node
, double_type_node
))
2955 r0
= frange_float ("3.0", "3.0", float_type_node
);
2956 r1
= frange_float ("3.0", "3.0", double_type_node
);
2960 // [3,5] U [10,12] = [3,12].
2961 r0
= frange_float ("3", "5");
2962 r1
= frange_float ("10", "12");
2964 ASSERT_EQ (r0
, frange_float ("3", "12"));
2966 // [5,10] U [4,8] = [4,10]
2967 r0
= frange_float ("5", "10");
2968 r1
= frange_float ("4", "8");
2970 ASSERT_EQ (r0
, frange_float ("4", "10"));
2972 // [3,5] U [4,10] = [3,10]
2973 r0
= frange_float ("3", "5");
2974 r1
= frange_float ("4", "10");
2976 ASSERT_EQ (r0
, frange_float ("3", "10"));
2978 // [4,10] U [5,11] = [4,11]
2979 r0
= frange_float ("4", "10");
2980 r1
= frange_float ("5", "11");
2982 ASSERT_EQ (r0
, frange_float ("4", "11"));
2984 // [3,12] ^ [10,12] = [10,12].
2985 r0
= frange_float ("3", "12");
2986 r1
= frange_float ("10", "12");
2988 ASSERT_EQ (r0
, frange_float ("10", "12"));
2990 // [10,12] ^ [11,11] = [11,11]
2991 r0
= frange_float ("10", "12");
2992 r1
= frange_float ("11", "11");
2994 ASSERT_EQ (r0
, frange_float ("11", "11"));
2996 // [10,20] ^ [5,15] = [10,15]
2997 r0
= frange_float ("10", "20");
2998 r1
= frange_float ("5", "15");
3000 ASSERT_EQ (r0
, frange_float ("10", "15"));
3002 // [10,20] ^ [15,25] = [15,20]
3003 r0
= frange_float ("10", "20");
3004 r1
= frange_float ("15", "25");
3006 ASSERT_EQ (r0
, frange_float ("15", "20"));
3008 // [10,20] ^ [21,25] = []
3009 r0
= frange_float ("10", "20");
3011 r1
= frange_float ("21", "25");
3014 ASSERT_TRUE (r0
.undefined_p ());
3016 if (HONOR_INFINITIES (float_type_node
))
3018 // Make sure [-Inf, -Inf] doesn't get normalized.
3019 r0
= frange_float ("-Inf", "-Inf");
3020 ASSERT_TRUE (real_isinf (&r0
.lower_bound (), true));
3021 ASSERT_TRUE (real_isinf (&r0
.upper_bound (), true));
3024 // Test that reading back a global range yields the same result as
3025 // what we wrote into it.
3026 tree ssa
= make_temp_ssa_name (float_type_node
, NULL
, "blah");
3027 r0
.set_varying (float_type_node
);
3029 set_range_info (ssa
, r0
);
3030 get_global_range_query ()->range_of_expr (r1
, ssa
);
3034 // Run floating range tests for various combinations of NAN and INF
3038 range_tests_floats_various ()
3040 int save_finite_math_only
= flag_finite_math_only
;
3042 // Test -ffinite-math-only.
3043 flag_finite_math_only
= 1;
3044 range_tests_floats ();
3045 // Test -fno-finite-math-only.
3046 flag_finite_math_only
= 0;
3047 range_tests_floats ();
3049 flag_finite_math_only
= save_finite_math_only
;
3055 range_tests_irange3 ();
3056 range_tests_int_range_max ();
3057 range_tests_strict_enum ();
3058 range_tests_nonzero_bits ();
3059 range_tests_floats_various ();
3060 range_tests_misc ();
3063 } // namespace selftest
3065 #endif // CHECKING_P