]>
git.ipfire.org Git - thirdparty/gcc.git/blob - gcc/value-range.cc
1 /* Support routines for value ranges.
2 Copyright (C) 2019-2022 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");
82 // Default vrange definitions.
85 vrange::contains_p (tree
) const
91 vrange::singleton_p (tree
*) const
97 vrange::set (tree min
, tree
, value_range_kind
)
99 set_varying (TREE_TYPE (min
));
103 vrange::type () const
105 return void_type_node
;
109 vrange::supports_type_p (const_tree
) const
115 vrange::set_undefined ()
117 m_kind
= VR_UNDEFINED
;
121 vrange::set_varying (tree
)
127 vrange::union_ (const vrange
&r
)
129 if (r
.undefined_p () || varying_p ())
131 if (undefined_p () || r
.varying_p ())
141 vrange::intersect (const vrange
&r
)
143 if (undefined_p () || r
.varying_p ())
145 if (r
.undefined_p ())
160 vrange::zero_p () const
166 vrange::nonzero_p () const
172 vrange::set_nonzero (tree type
)
178 vrange::set_zero (tree type
)
184 vrange::set_nonnegative (tree type
)
190 vrange::fits_p (const vrange
&) const
195 // Assignment operator for generic ranges. Copying incompatible types
199 vrange::operator= (const vrange
&src
)
201 if (is_a
<irange
> (src
))
202 as_a
<irange
> (*this) = as_a
<irange
> (src
);
203 else if (is_a
<frange
> (src
))
204 as_a
<frange
> (*this) = as_a
<frange
> (src
);
210 // Equality operator for generic ranges.
213 vrange::operator== (const vrange
&src
) const
215 if (is_a
<irange
> (src
))
216 return as_a
<irange
> (*this) == as_a
<irange
> (src
);
217 if (is_a
<frange
> (src
))
218 return as_a
<frange
> (*this) == as_a
<frange
> (src
);
222 // Wrapper for vrange_printer to dump a range to a file.
225 vrange::dump (FILE *file
) const
227 pretty_printer buffer
;
228 pp_needs_newline (&buffer
) = true;
229 buffer
.buffer
->stream
= file
;
230 vrange_printer
vrange_pp (&buffer
);
231 this->accept (vrange_pp
);
236 irange::supports_type_p (const_tree type
) const
238 return supports_p (type
);
241 // Return TRUE if R fits in THIS.
244 irange::fits_p (const vrange
&r
) const
246 return m_max_ranges
>= as_a
<irange
> (r
).num_pairs ();
250 irange::set_nonnegative (tree type
)
252 set (build_int_cst (type
, 0), TYPE_MAX_VALUE (type
));
256 frange::accept (const vrange_visitor
&v
) const
261 // Flush denormal endpoints to the appropriate 0.0.
264 frange::flush_denormals_to_zero ()
266 if (undefined_p () || known_isnan ())
269 // Flush [x, -DENORMAL] to [x, -0.0].
270 if (real_isdenormal (&m_max
) && real_isneg (&m_max
))
273 if (HONOR_SIGNED_ZEROS (m_type
))
276 // Flush [+DENORMAL, x] to [+0.0, x].
277 if (real_isdenormal (&m_min
) && !real_isneg (&m_min
))
281 // Setter for franges.
284 frange::set (tree type
,
285 const REAL_VALUE_TYPE
&min
, const REAL_VALUE_TYPE
&max
,
286 value_range_kind kind
)
304 if (real_isnan (&min
) || real_isnan (&max
))
306 gcc_checking_assert (real_identical (&min
, &max
));
307 bool sign
= real_isneg (&min
);
308 set_nan (type
, sign
);
316 if (HONOR_NANS (m_type
))
327 if (!MODE_HAS_SIGNED_ZEROS (TYPE_MODE (m_type
)))
329 if (real_iszero (&m_min
, 1))
331 if (real_iszero (&m_max
, 1))
334 else if (!HONOR_SIGNED_ZEROS (m_type
))
336 if (real_iszero (&m_max
, 1))
338 if (real_iszero (&m_min
, 0))
342 // For -ffinite-math-only we can drop ranges outside the
343 // representable numbers to min/max for the type.
344 if (flag_finite_math_only
)
346 REAL_VALUE_TYPE min_repr
= frange_val_min (m_type
);
347 REAL_VALUE_TYPE max_repr
= frange_val_max (m_type
);
348 if (real_less (&m_min
, &min_repr
))
350 else if (real_less (&max_repr
, &m_min
))
352 if (real_less (&max_repr
, &m_max
))
354 else if (real_less (&m_max
, &min_repr
))
358 // Check for swapped ranges.
359 gcc_checking_assert (real_compare (LE_EXPR
, &min
, &max
));
363 flush_denormals_to_zero ();
370 frange::set (tree min
, tree max
, value_range_kind kind
)
372 set (TREE_TYPE (min
),
373 *TREE_REAL_CST_PTR (min
), *TREE_REAL_CST_PTR (max
), kind
);
376 // Normalize range to VARYING or UNDEFINED, or vice versa. Return
377 // TRUE if anything changed.
379 // A range with no known properties can be dropped to VARYING.
380 // Similarly, a VARYING with any properties should be dropped to a
381 // VR_RANGE. Normalizing ranges upon changing them ensures there is
382 // only one representation for a given range.
385 frange::normalize_kind ()
387 if (m_kind
== VR_RANGE
388 && frange_val_is_min (m_min
, m_type
)
389 && frange_val_is_max (m_max
, m_type
))
391 if (!HONOR_NANS (m_type
) || (m_pos_nan
&& m_neg_nan
))
393 set_varying (m_type
);
397 else if (m_kind
== VR_VARYING
)
399 if (HONOR_NANS (m_type
) && (!m_pos_nan
|| !m_neg_nan
))
402 m_min
= frange_val_min (m_type
);
403 m_max
= frange_val_max (m_type
);
407 else if (m_kind
== VR_NAN
&& !m_pos_nan
&& !m_neg_nan
)
412 // Union or intersect the zero endpoints of two ranges. For example:
413 // [-0, x] U [+0, x] => [-0, x]
414 // [ x, -0] U [ x, +0] => [ x, +0]
415 // [-0, x] ^ [+0, x] => [+0, x]
416 // [ x, -0] ^ [ x, +0] => [ x, -0]
418 // UNION_P is true when performing a union, or false when intersecting.
421 frange::combine_zeros (const frange
&r
, bool union_p
)
423 gcc_checking_assert (!undefined_p () && !known_isnan ());
425 bool changed
= false;
426 if (real_iszero (&m_min
) && real_iszero (&r
.m_min
)
427 && real_isneg (&m_min
) != real_isneg (&r
.m_min
))
429 m_min
.sign
= union_p
;
432 if (real_iszero (&m_max
) && real_iszero (&r
.m_max
)
433 && real_isneg (&m_max
) != real_isneg (&r
.m_max
))
435 m_max
.sign
= !union_p
;
438 // If the signs are swapped, the resulting range is empty.
439 if (m_min
.sign
== 0 && m_max
.sign
== 1)
450 // Union two ranges when one is known to be a NAN.
453 frange::union_nans (const frange
&r
)
455 gcc_checking_assert (known_isnan () || r
.known_isnan ());
463 m_pos_nan
|= r
.m_pos_nan
;
464 m_neg_nan
|= r
.m_neg_nan
;
472 frange::union_ (const vrange
&v
)
474 const frange
&r
= as_a
<frange
> (v
);
476 if (r
.undefined_p () || varying_p ())
478 if (undefined_p () || r
.varying_p ())
485 if (known_isnan () || r
.known_isnan ())
486 return union_nans (r
);
487 bool changed
= false;
488 if (m_pos_nan
!= r
.m_pos_nan
|| m_neg_nan
!= r
.m_neg_nan
)
490 m_pos_nan
|= r
.m_pos_nan
;
491 m_neg_nan
|= r
.m_neg_nan
;
495 // Combine endpoints.
496 if (real_less (&r
.m_min
, &m_min
))
501 if (real_less (&m_max
, &r
.m_max
))
507 if (HONOR_SIGNED_ZEROS (m_type
))
508 changed
|= combine_zeros (r
, true);
510 changed
|= normalize_kind ();
516 // Intersect two ranges when one is known to be a NAN.
519 frange::intersect_nans (const frange
&r
)
521 gcc_checking_assert (known_isnan () || r
.known_isnan ());
523 m_pos_nan
&= r
.m_pos_nan
;
524 m_neg_nan
&= r
.m_neg_nan
;
535 frange::intersect (const vrange
&v
)
537 const frange
&r
= as_a
<frange
> (v
);
539 if (undefined_p () || r
.varying_p ())
541 if (r
.undefined_p ())
553 if (known_isnan () || r
.known_isnan ())
554 return intersect_nans (r
);
555 bool changed
= false;
556 if (m_pos_nan
!= r
.m_pos_nan
|| m_neg_nan
!= r
.m_neg_nan
)
558 m_pos_nan
&= r
.m_pos_nan
;
559 m_neg_nan
&= r
.m_neg_nan
;
563 // Combine endpoints.
564 if (real_less (&m_min
, &r
.m_min
))
569 if (real_less (&r
.m_max
, &m_max
))
574 // If the endpoints are swapped, the resulting range is empty.
575 if (real_less (&m_max
, &m_min
))
586 if (HONOR_SIGNED_ZEROS (m_type
))
587 changed
|= combine_zeros (r
, false);
589 changed
|= normalize_kind ();
596 frange::operator= (const frange
&src
)
602 m_pos_nan
= src
.m_pos_nan
;
603 m_neg_nan
= src
.m_neg_nan
;
611 frange::operator== (const frange
&src
) const
613 if (m_kind
== src
.m_kind
)
619 return types_compatible_p (m_type
, src
.m_type
);
621 if (known_isnan () || src
.known_isnan ())
624 return (real_identical (&m_min
, &src
.m_min
)
625 && real_identical (&m_max
, &src
.m_max
)
626 && m_pos_nan
== src
.m_pos_nan
627 && m_neg_nan
== src
.m_neg_nan
628 && types_compatible_p (m_type
, src
.m_type
));
633 // Return TRUE if range contains the TREE_REAL_CST_PTR in CST.
636 frange::contains_p (tree cst
) const
638 gcc_checking_assert (m_kind
!= VR_ANTI_RANGE
);
639 const REAL_VALUE_TYPE
*rv
= TREE_REAL_CST_PTR (cst
);
650 if (!m_pos_nan
&& !m_neg_nan
)
652 // Both +NAN and -NAN are present.
653 if (m_pos_nan
&& m_neg_nan
)
655 return m_neg_nan
== rv
->sign
;
660 if (real_compare (GE_EXPR
, rv
, &m_min
) && real_compare (LE_EXPR
, rv
, &m_max
))
662 // Make sure the signs are equal for signed zeros.
663 if (HONOR_SIGNED_ZEROS (m_type
) && real_iszero (rv
))
664 return m_min
.sign
== m_max
.sign
&& m_min
.sign
== rv
->sign
;
670 // If range is a singleton, place it in RESULT and return TRUE. If
671 // RESULT is NULL, just return TRUE.
673 // A NAN can never be a singleton.
676 frange::singleton_p (tree
*result
) const
678 if (m_kind
== VR_RANGE
&& real_identical (&m_min
, &m_max
))
680 // Return false for any singleton that may be a NAN.
681 if (HONOR_NANS (m_type
) && maybe_isnan ())
684 if (MODE_COMPOSITE_P (TYPE_MODE (m_type
)))
686 // For IBM long doubles, if the value is +-Inf or is exactly
687 // representable in double, the other double could be +0.0
688 // or -0.0. Since this means there is more than one way to
689 // represent a value, return false to avoid propagating it.
690 // See libgcc/config/rs6000/ibm-ldouble-format for details.
691 if (real_isinf (&m_min
))
694 real_convert (&r
, DFmode
, &m_min
);
695 if (real_identical (&r
, &m_min
))
700 *result
= build_real (m_type
, m_min
);
707 frange::supports_type_p (const_tree type
) const
709 return supports_p (type
);
713 frange::verify_range ()
715 if (flag_finite_math_only
)
716 gcc_checking_assert (!maybe_isnan ());
720 gcc_checking_assert (!m_type
);
723 if (flag_finite_math_only
)
724 gcc_checking_assert (!m_pos_nan
&& !m_neg_nan
);
726 gcc_checking_assert (m_pos_nan
&& m_neg_nan
);
727 gcc_checking_assert (m_type
);
728 gcc_checking_assert (frange_val_is_min (m_min
, m_type
));
729 gcc_checking_assert (frange_val_is_max (m_max
, m_type
));
732 gcc_checking_assert (m_type
);
735 gcc_checking_assert (m_type
);
736 gcc_checking_assert (m_pos_nan
|| m_neg_nan
);
742 // NANs cannot appear in the endpoints of a range.
743 gcc_checking_assert (!real_isnan (&m_min
) && !real_isnan (&m_max
));
745 // Make sure we don't have swapped ranges.
746 gcc_checking_assert (!real_less (&m_max
, &m_min
));
748 // [ +0.0, -0.0 ] is nonsensical.
749 gcc_checking_assert (!(real_iszero (&m_min
, 0) && real_iszero (&m_max
, 1)));
751 // If all the properties are clear, we better not span the entire
752 // domain, because that would make us varying.
753 if (m_pos_nan
&& m_neg_nan
)
754 gcc_checking_assert (!frange_val_is_min (m_min
, m_type
)
755 || !frange_val_is_max (m_max
, m_type
));
758 // We can't do much with nonzeros yet.
760 frange::set_nonzero (tree type
)
765 // We can't do much with nonzeros yet.
767 frange::nonzero_p () const
772 // Set range to [+0.0, +0.0] if honoring signed zeros, or [0.0, 0.0]
776 frange::set_zero (tree type
)
778 if (HONOR_SIGNED_ZEROS (type
))
780 REAL_VALUE_TYPE dconstm0
= dconst0
;
782 set (type
, dconstm0
, dconst0
);
786 set (type
, dconst0
, dconst0
);
789 // Return TRUE for any zero regardless of sign.
792 frange::zero_p () const
794 return (m_kind
== VR_RANGE
795 && real_iszero (&m_min
)
796 && real_iszero (&m_max
));
800 frange::set_nonnegative (tree type
)
802 set (type
, dconst0
, frange_val_max (type
));
804 // Set +NAN as the only possibility.
805 if (HONOR_NANS (type
))
806 update_nan (/*sign=*/false);
809 // Here we copy between any two irange's. The ranges can be legacy or
810 // multi-ranges, and copying between any combination works correctly.
813 irange::operator= (const irange
&src
)
815 if (legacy_mode_p ())
817 copy_to_legacy (src
);
820 if (src
.legacy_mode_p ())
822 copy_legacy_to_multi_range (src
);
827 unsigned lim
= src
.m_num_ranges
;
828 if (lim
> m_max_ranges
)
831 for (x
= 0; x
< lim
* 2; ++x
)
832 m_base
[x
] = src
.m_base
[x
];
834 // If the range didn't fit, the last range should cover the rest.
835 if (lim
!= src
.m_num_ranges
)
836 m_base
[x
- 1] = src
.m_base
[src
.m_num_ranges
* 2 - 1];
840 m_nonzero_mask
= src
.m_nonzero_mask
;
846 // Return TRUE if range is a multi-range that can be represented as a
850 irange::maybe_anti_range () const
852 tree ttype
= type ();
853 unsigned int precision
= TYPE_PRECISION (ttype
);
854 signop sign
= TYPE_SIGN (ttype
);
855 return (num_pairs () > 1
857 && lower_bound () == wi::min_value (precision
, sign
)
858 && upper_bound () == wi::max_value (precision
, sign
));
862 irange::copy_legacy_to_multi_range (const irange
&src
)
864 gcc_checking_assert (src
.legacy_mode_p ());
865 gcc_checking_assert (!legacy_mode_p ());
866 if (src
.undefined_p ())
868 else if (src
.varying_p ())
869 set_varying (src
.type ());
872 if (range_has_numeric_bounds_p (&src
))
873 set (src
.min (), src
.max (), src
.kind ());
876 value_range
cst (src
);
877 cst
.normalize_symbolics ();
878 gcc_checking_assert (cst
.varying_p () || cst
.kind () == VR_RANGE
);
879 set (cst
.min (), cst
.max ());
884 // Copy any type of irange into a legacy.
887 irange::copy_to_legacy (const irange
&src
)
889 gcc_checking_assert (legacy_mode_p ());
890 // Handle legacy to legacy and other things that are easy to copy.
891 if (src
.legacy_mode_p () || src
.varying_p () || src
.undefined_p ())
893 m_num_ranges
= src
.m_num_ranges
;
894 m_base
[0] = src
.m_base
[0];
895 m_base
[1] = src
.m_base
[1];
897 m_nonzero_mask
= src
.m_nonzero_mask
;
900 // Copy multi-range to legacy.
901 if (src
.maybe_anti_range ())
903 int_range
<3> r (src
);
905 // Use tree variants to save on tree -> wi -> tree conversions.
906 set (r
.tree_lower_bound (0), r
.tree_upper_bound (0), VR_ANTI_RANGE
);
909 set (src
.tree_lower_bound (), src
.tree_upper_bound ());
912 // Swap MIN/MAX if they are out of order and adjust KIND appropriately.
915 swap_out_of_order_endpoints (tree
&min
, tree
&max
, value_range_kind
&kind
)
917 gcc_checking_assert (kind
!= VR_UNDEFINED
);
918 if (kind
== VR_VARYING
)
920 /* Wrong order for min and max, to swap them and the VR type we need
922 if (tree_int_cst_lt (max
, min
))
926 /* For one bit precision if max < min, then the swapped
927 range covers all values, so for VR_RANGE it is varying and
928 for VR_ANTI_RANGE empty range, so drop to varying as well. */
929 if (TYPE_PRECISION (TREE_TYPE (min
)) == 1)
935 one
= build_int_cst (TREE_TYPE (min
), 1);
936 tmp
= int_const_binop (PLUS_EXPR
, max
, one
);
937 max
= int_const_binop (MINUS_EXPR
, min
, one
);
940 /* There's one corner case, if we had [C+1, C] before we now have
941 that again. But this represents an empty value range, so drop
942 to varying in this case. */
943 if (tree_int_cst_lt (max
, min
))
948 kind
= kind
== VR_RANGE
? VR_ANTI_RANGE
: VR_RANGE
;
953 irange::irange_set (tree min
, tree max
)
955 gcc_checking_assert (!POLY_INT_CST_P (min
));
956 gcc_checking_assert (!POLY_INT_CST_P (max
));
962 m_nonzero_mask
= NULL
;
970 irange::irange_set_1bit_anti_range (tree min
, tree max
)
972 tree type
= TREE_TYPE (min
);
973 gcc_checking_assert (TYPE_PRECISION (type
) == 1);
975 if (operand_equal_p (min
, max
))
977 // Since these are 1-bit quantities, they can only be [MIN,MIN]
979 if (vrp_val_is_min (min
))
980 min
= max
= vrp_val_max (type
);
982 min
= max
= vrp_val_min (type
);
987 // The only alternative is [MIN,MAX], which is the empty range.
988 gcc_checking_assert (vrp_val_is_min (min
));
989 gcc_checking_assert (vrp_val_is_max (max
));
997 irange::irange_set_anti_range (tree min
, tree max
)
999 gcc_checking_assert (!POLY_INT_CST_P (min
));
1000 gcc_checking_assert (!POLY_INT_CST_P (max
));
1002 if (TYPE_PRECISION (TREE_TYPE (min
)) == 1)
1004 irange_set_1bit_anti_range (min
, max
);
1008 // set an anti-range
1009 tree type
= TREE_TYPE (min
);
1010 signop sign
= TYPE_SIGN (type
);
1011 int_range
<2> type_range (type
);
1012 // Calculate INVERSE([I,J]) as [-MIN, I-1][J+1, +MAX].
1014 wi::overflow_type ovf
;
1016 wide_int w_min
= wi::to_wide (min
);
1017 if (wi::ne_p (w_min
, type_range
.lower_bound ()))
1019 wide_int lim1
= wi::sub (w_min
, 1, sign
, &ovf
);
1020 gcc_checking_assert (ovf
!= wi::OVF_OVERFLOW
);
1021 m_base
[0] = type_range
.tree_lower_bound (0);
1022 m_base
[1] = wide_int_to_tree (type
, lim1
);
1025 wide_int w_max
= wi::to_wide (max
);
1026 if (wi::ne_p (w_max
, type_range
.upper_bound ()))
1028 wide_int lim2
= wi::add (w_max
, 1, sign
, &ovf
);
1029 gcc_checking_assert (ovf
!= wi::OVF_OVERFLOW
);
1030 m_base
[m_num_ranges
* 2] = wide_int_to_tree (type
, lim2
);
1031 m_base
[m_num_ranges
* 2 + 1] = type_range
.tree_upper_bound (0);
1036 m_nonzero_mask
= NULL
;
1043 /* Set value range to the canonical form of {VRTYPE, MIN, MAX, EQUIV}.
1044 This means adjusting VRTYPE, MIN and MAX representing the case of a
1045 wrapping range with MAX < MIN covering [MIN, type_max] U [type_min, MAX]
1046 as anti-rage ~[MAX+1, MIN-1]. Likewise for wrapping anti-ranges.
1047 In corner cases where MAX+1 or MIN-1 wraps this will fall back
1049 This routine exists to ease canonicalization in the case where we
1050 extract ranges from var + CST op limit. */
1053 irange::set (tree min
, tree max
, value_range_kind kind
)
1055 if (kind
== VR_UNDEFINED
)
1057 irange::set_undefined ();
1061 if (kind
== VR_VARYING
1062 || POLY_INT_CST_P (min
)
1063 || POLY_INT_CST_P (max
))
1065 set_varying (TREE_TYPE (min
));
1069 if (TREE_OVERFLOW_P (min
))
1070 min
= drop_tree_overflow (min
);
1071 if (TREE_OVERFLOW_P (max
))
1072 max
= drop_tree_overflow (max
);
1074 if (!legacy_mode_p ())
1076 if (kind
== VR_RANGE
)
1077 irange_set (min
, max
);
1080 gcc_checking_assert (kind
== VR_ANTI_RANGE
);
1081 irange_set_anti_range (min
, max
);
1085 // Nothing to canonicalize for symbolic ranges.
1086 if (TREE_CODE (min
) != INTEGER_CST
1087 || TREE_CODE (max
) != INTEGER_CST
)
1093 m_nonzero_mask
= NULL
;
1097 swap_out_of_order_endpoints (min
, max
, kind
);
1098 if (kind
== VR_VARYING
)
1100 set_varying (TREE_TYPE (min
));
1104 // Anti-ranges that can be represented as ranges should be so.
1105 if (kind
== VR_ANTI_RANGE
)
1107 bool is_min
= vrp_val_is_min (min
);
1108 bool is_max
= vrp_val_is_max (max
);
1110 if (is_min
&& is_max
)
1112 // Fall through. This will either be normalized as
1113 // VR_UNDEFINED if the anti-range spans the entire
1114 // precision, or it will remain an VR_ANTI_RANGE in the case
1115 // of an -fstrict-enum where [MIN,MAX] is less than the span
1116 // of underlying precision.
1118 else if (TYPE_PRECISION (TREE_TYPE (min
)) == 1)
1120 irange_set_1bit_anti_range (min
, max
);
1125 tree one
= build_int_cst (TREE_TYPE (max
), 1);
1126 min
= int_const_binop (PLUS_EXPR
, max
, one
);
1127 max
= vrp_val_max (TREE_TYPE (max
));
1132 tree one
= build_int_cst (TREE_TYPE (min
), 1);
1133 max
= int_const_binop (MINUS_EXPR
, min
, one
);
1134 min
= vrp_val_min (TREE_TYPE (min
));
1143 m_nonzero_mask
= NULL
;
1149 // Check the validity of the range.
1152 irange::verify_range ()
1154 gcc_checking_assert (m_discriminator
== VR_IRANGE
);
1155 if (m_kind
== VR_UNDEFINED
)
1157 gcc_checking_assert (m_num_ranges
== 0);
1160 if (m_kind
== VR_VARYING
)
1162 gcc_checking_assert (!m_nonzero_mask
1163 || wi::to_wide (m_nonzero_mask
) == -1);
1164 gcc_checking_assert (m_num_ranges
== 1);
1165 gcc_checking_assert (varying_compatible_p ());
1168 if (!legacy_mode_p ())
1170 gcc_checking_assert (m_num_ranges
!= 0);
1171 gcc_checking_assert (!varying_compatible_p ());
1172 for (unsigned i
= 0; i
< m_num_ranges
; ++i
)
1174 tree lb
= tree_lower_bound (i
);
1175 tree ub
= tree_upper_bound (i
);
1176 int c
= compare_values (lb
, ub
);
1177 gcc_checking_assert (c
== 0 || c
== -1);
1181 if (m_kind
== VR_RANGE
|| m_kind
== VR_ANTI_RANGE
)
1183 gcc_checking_assert (m_num_ranges
== 1);
1184 int cmp
= compare_values (tree_lower_bound (0), tree_upper_bound (0));
1185 gcc_checking_assert (cmp
== 0 || cmp
== -1 || cmp
== -2);
1189 // Return the lower bound for a sub-range. PAIR is the sub-range in
1193 irange::legacy_lower_bound (unsigned pair
) const
1195 gcc_checking_assert (legacy_mode_p ());
1198 value_range
numeric_range (*this);
1199 numeric_range
.normalize_symbolics ();
1200 return numeric_range
.legacy_lower_bound (pair
);
1202 gcc_checking_assert (m_num_ranges
> 0);
1203 gcc_checking_assert (pair
+ 1 <= num_pairs ());
1204 if (m_kind
== VR_ANTI_RANGE
)
1206 tree typ
= type (), t
;
1207 if (pair
== 1 || vrp_val_is_min (min ()))
1208 t
= wide_int_to_tree (typ
, wi::to_wide (max ()) + 1);
1210 t
= vrp_val_min (typ
);
1211 return wi::to_wide (t
);
1213 return wi::to_wide (tree_lower_bound (pair
));
1216 // Return the upper bound for a sub-range. PAIR is the sub-range in
1220 irange::legacy_upper_bound (unsigned pair
) const
1222 gcc_checking_assert (legacy_mode_p ());
1225 value_range
numeric_range (*this);
1226 numeric_range
.normalize_symbolics ();
1227 return numeric_range
.legacy_upper_bound (pair
);
1229 gcc_checking_assert (m_num_ranges
> 0);
1230 gcc_checking_assert (pair
+ 1 <= num_pairs ());
1231 if (m_kind
== VR_ANTI_RANGE
)
1233 tree typ
= type (), t
;
1234 if (pair
== 1 || vrp_val_is_min (min ()))
1235 t
= vrp_val_max (typ
);
1237 t
= wide_int_to_tree (typ
, wi::to_wide (min ()) - 1);
1238 return wi::to_wide (t
);
1240 return wi::to_wide (tree_upper_bound (pair
));
1244 irange::legacy_equal_p (const irange
&other
) const
1246 gcc_checking_assert (legacy_mode_p () && other
.legacy_mode_p ());
1248 if (m_kind
!= other
.m_kind
)
1250 if (m_kind
== VR_UNDEFINED
)
1252 if (m_kind
== VR_VARYING
)
1253 return range_compatible_p (type (), other
.type ());
1254 return (vrp_operand_equal_p (tree_lower_bound (0),
1255 other
.tree_lower_bound (0))
1256 && vrp_operand_equal_p (tree_upper_bound (0),
1257 other
.tree_upper_bound (0))
1258 && get_nonzero_bits () == other
.get_nonzero_bits ());
1262 irange::operator== (const irange
&other
) const
1264 if (legacy_mode_p ())
1266 if (other
.legacy_mode_p ())
1267 return legacy_equal_p (other
);
1268 value_range
tmp (other
);
1269 return legacy_equal_p (tmp
);
1271 if (other
.legacy_mode_p ())
1273 value_range
tmp2 (*this);
1274 return tmp2
.legacy_equal_p (other
);
1277 if (m_num_ranges
!= other
.m_num_ranges
)
1280 if (m_num_ranges
== 0)
1283 for (unsigned i
= 0; i
< m_num_ranges
; ++i
)
1285 tree lb
= tree_lower_bound (i
);
1286 tree ub
= tree_upper_bound (i
);
1287 tree lb_other
= other
.tree_lower_bound (i
);
1288 tree ub_other
= other
.tree_upper_bound (i
);
1289 if (!operand_equal_p (lb
, lb_other
, 0)
1290 || !operand_equal_p (ub
, ub_other
, 0))
1293 return get_nonzero_bits () == other
.get_nonzero_bits ();
1296 /* Return TRUE if this is a symbolic range. */
1299 irange::symbolic_p () const
1301 return (m_num_ranges
> 0
1302 && (!is_gimple_min_invariant (min ())
1303 || !is_gimple_min_invariant (max ())));
1306 /* Return TRUE if this is a constant range. */
1309 irange::constant_p () const
1311 return (m_num_ranges
> 0
1312 && TREE_CODE (min ()) == INTEGER_CST
1313 && TREE_CODE (max ()) == INTEGER_CST
);
1316 /* If range is a singleton, place it in RESULT and return TRUE.
1317 Note: A singleton can be any gimple invariant, not just constants.
1318 So, [&x, &x] counts as a singleton. */
1321 irange::singleton_p (tree
*result
) const
1323 if (!legacy_mode_p ())
1325 if (num_pairs () == 1 && (wi::to_wide (tree_lower_bound ())
1326 == wi::to_wide (tree_upper_bound ())))
1329 *result
= tree_lower_bound ();
1334 if (m_kind
== VR_ANTI_RANGE
)
1338 if (TYPE_PRECISION (type ()) == 1)
1346 if (num_pairs () == 1)
1348 value_range vr0
, vr1
;
1349 ranges_from_anti_range ((const value_range
*) this, &vr0
, &vr1
);
1350 return vr0
.singleton_p (result
);
1353 // Catches non-numeric extremes as well.
1354 if (m_kind
== VR_RANGE
1355 && vrp_operand_equal_p (min (), max ())
1356 && is_gimple_min_invariant (min ()))
1365 /* Return 1 if VAL is inside value range.
1366 0 if VAL is not inside value range.
1367 -2 if we cannot tell either way.
1369 Benchmark compile/20001226-1.c compilation time after changing this
1373 irange::value_inside_range (tree val
) const
1381 if (!legacy_mode_p () && TREE_CODE (val
) == INTEGER_CST
)
1382 return contains_p (val
);
1384 int cmp1
= operand_less_p (val
, min ());
1388 return m_kind
!= VR_RANGE
;
1390 int cmp2
= operand_less_p (max (), val
);
1394 if (m_kind
== VR_RANGE
)
1400 /* Return TRUE if it is possible that range contains VAL. */
1403 irange::may_contain_p (tree val
) const
1405 return value_inside_range (val
) != 0;
1408 /* Return TRUE if range contains INTEGER_CST. */
1409 /* Return 1 if VAL is inside value range.
1410 0 if VAL is not inside value range.
1412 Benchmark compile/20001226-1.c compilation time after changing this
1417 irange::contains_p (tree cst
) const
1422 if (legacy_mode_p ())
1424 gcc_checking_assert (TREE_CODE (cst
) == INTEGER_CST
);
1427 value_range
numeric_range (*this);
1428 numeric_range
.normalize_symbolics ();
1429 return numeric_range
.contains_p (cst
);
1431 return value_inside_range (cst
) == 1;
1434 gcc_checking_assert (TREE_CODE (cst
) == INTEGER_CST
);
1436 // See if we can exclude CST based on the nonzero bits.
1439 wide_int cstw
= wi::to_wide (cst
);
1440 if (cstw
!= 0 && wi::bit_and (wi::to_wide (m_nonzero_mask
), cstw
) == 0)
1444 signop sign
= TYPE_SIGN (TREE_TYPE (cst
));
1445 wide_int v
= wi::to_wide (cst
);
1446 for (unsigned r
= 0; r
< m_num_ranges
; ++r
)
1448 if (wi::lt_p (v
, lower_bound (r
), sign
))
1450 if (wi::le_p (v
, upper_bound (r
), sign
))
1458 /* Normalize addresses into constants. */
1461 irange::normalize_addresses ()
1466 if (!POINTER_TYPE_P (type ()) || range_has_numeric_bounds_p (this))
1469 if (!range_includes_zero_p (this))
1471 gcc_checking_assert (TREE_CODE (min ()) == ADDR_EXPR
1472 || TREE_CODE (max ()) == ADDR_EXPR
);
1473 set_nonzero (type ());
1476 set_varying (type ());
1479 /* Normalize symbolics and addresses into constants. */
1482 irange::normalize_symbolics ()
1484 if (varying_p () || undefined_p ())
1487 tree ttype
= type ();
1488 bool min_symbolic
= !is_gimple_min_invariant (min ());
1489 bool max_symbolic
= !is_gimple_min_invariant (max ());
1490 if (!min_symbolic
&& !max_symbolic
)
1492 normalize_addresses ();
1496 // [SYM, SYM] -> VARYING
1497 if (min_symbolic
&& max_symbolic
)
1499 set_varying (ttype
);
1502 if (kind () == VR_RANGE
)
1504 // [SYM, NUM] -> [-MIN, NUM]
1507 set (vrp_val_min (ttype
), max ());
1510 // [NUM, SYM] -> [NUM, +MAX]
1511 set (min (), vrp_val_max (ttype
));
1514 gcc_checking_assert (kind () == VR_ANTI_RANGE
);
1515 // ~[SYM, NUM] -> [NUM + 1, +MAX]
1518 if (!vrp_val_is_max (max ()))
1520 tree n
= wide_int_to_tree (ttype
, wi::to_wide (max ()) + 1);
1521 set (n
, vrp_val_max (ttype
));
1524 set_varying (ttype
);
1527 // ~[NUM, SYM] -> [-MIN, NUM - 1]
1528 if (!vrp_val_is_min (min ()))
1530 tree n
= wide_int_to_tree (ttype
, wi::to_wide (min ()) - 1);
1531 set (vrp_val_min (ttype
), n
);
1534 set_varying (ttype
);
1537 /* Intersect the two value-ranges { *VR0TYPE, *VR0MIN, *VR0MAX } and
1538 { VR1TYPE, VR0MIN, VR0MAX } and store the result
1539 in { *VR0TYPE, *VR0MIN, *VR0MAX }. This may not be the smallest
1540 possible such range. The resulting range is not canonicalized. */
1543 intersect_ranges (enum value_range_kind
*vr0type
,
1544 tree
*vr0min
, tree
*vr0max
,
1545 enum value_range_kind vr1type
,
1546 tree vr1min
, tree vr1max
)
1548 bool mineq
= vrp_operand_equal_p (*vr0min
, vr1min
);
1549 bool maxeq
= vrp_operand_equal_p (*vr0max
, vr1max
);
1551 /* [] is vr0, () is vr1 in the following classification comments. */
1555 if (*vr0type
== vr1type
)
1556 /* Nothing to do for equal ranges. */
1558 else if ((*vr0type
== VR_RANGE
1559 && vr1type
== VR_ANTI_RANGE
)
1560 || (*vr0type
== VR_ANTI_RANGE
1561 && vr1type
== VR_RANGE
))
1563 /* For anti-range with range intersection the result is empty. */
1564 *vr0type
= VR_UNDEFINED
;
1565 *vr0min
= NULL_TREE
;
1566 *vr0max
= NULL_TREE
;
1571 else if (operand_less_p (*vr0max
, vr1min
) == 1
1572 || operand_less_p (vr1max
, *vr0min
) == 1)
1574 /* [ ] ( ) or ( ) [ ]
1575 If the ranges have an empty intersection, the result of the
1576 intersect operation is the range for intersecting an
1577 anti-range with a range or empty when intersecting two ranges. */
1578 if (*vr0type
== VR_RANGE
1579 && vr1type
== VR_ANTI_RANGE
)
1581 else if (*vr0type
== VR_ANTI_RANGE
1582 && vr1type
== VR_RANGE
)
1588 else if (*vr0type
== VR_RANGE
1589 && vr1type
== VR_RANGE
)
1591 *vr0type
= VR_UNDEFINED
;
1592 *vr0min
= NULL_TREE
;
1593 *vr0max
= NULL_TREE
;
1595 else if (*vr0type
== VR_ANTI_RANGE
1596 && vr1type
== VR_ANTI_RANGE
)
1598 /* If the anti-ranges are adjacent to each other merge them. */
1599 if (TREE_CODE (*vr0max
) == INTEGER_CST
1600 && TREE_CODE (vr1min
) == INTEGER_CST
1601 && operand_less_p (*vr0max
, vr1min
) == 1
1602 && integer_onep (int_const_binop (MINUS_EXPR
,
1605 else if (TREE_CODE (vr1max
) == INTEGER_CST
1606 && TREE_CODE (*vr0min
) == INTEGER_CST
1607 && operand_less_p (vr1max
, *vr0min
) == 1
1608 && integer_onep (int_const_binop (MINUS_EXPR
,
1611 /* Else arbitrarily take VR0. */
1614 else if ((maxeq
|| operand_less_p (vr1max
, *vr0max
) == 1)
1615 && (mineq
|| operand_less_p (*vr0min
, vr1min
) == 1))
1617 /* [ ( ) ] or [( ) ] or [ ( )] */
1618 if (*vr0type
== VR_RANGE
1619 && vr1type
== VR_RANGE
)
1621 /* If both are ranges the result is the inner one. */
1626 else if (*vr0type
== VR_RANGE
1627 && vr1type
== VR_ANTI_RANGE
)
1629 /* Choose the right gap if the left one is empty. */
1632 if (TREE_CODE (vr1max
) != INTEGER_CST
)
1634 else if (TYPE_PRECISION (TREE_TYPE (vr1max
)) == 1
1635 && !TYPE_UNSIGNED (TREE_TYPE (vr1max
)))
1637 = int_const_binop (MINUS_EXPR
, vr1max
,
1638 build_int_cst (TREE_TYPE (vr1max
), -1));
1641 = int_const_binop (PLUS_EXPR
, vr1max
,
1642 build_int_cst (TREE_TYPE (vr1max
), 1));
1644 /* Choose the left gap if the right one is empty. */
1647 if (TREE_CODE (vr1min
) != INTEGER_CST
)
1649 else if (TYPE_PRECISION (TREE_TYPE (vr1min
)) == 1
1650 && !TYPE_UNSIGNED (TREE_TYPE (vr1min
)))
1652 = int_const_binop (PLUS_EXPR
, vr1min
,
1653 build_int_cst (TREE_TYPE (vr1min
), -1));
1656 = int_const_binop (MINUS_EXPR
, vr1min
,
1657 build_int_cst (TREE_TYPE (vr1min
), 1));
1659 /* Choose the anti-range if the range is effectively varying. */
1660 else if (vrp_val_is_min (*vr0min
)
1661 && vrp_val_is_max (*vr0max
))
1667 /* Else choose the range. */
1669 else if (*vr0type
== VR_ANTI_RANGE
1670 && vr1type
== VR_ANTI_RANGE
)
1671 /* If both are anti-ranges the result is the outer one. */
1673 else if (*vr0type
== VR_ANTI_RANGE
1674 && vr1type
== VR_RANGE
)
1676 /* The intersection is empty. */
1677 *vr0type
= VR_UNDEFINED
;
1678 *vr0min
= NULL_TREE
;
1679 *vr0max
= NULL_TREE
;
1684 else if ((maxeq
|| operand_less_p (*vr0max
, vr1max
) == 1)
1685 && (mineq
|| operand_less_p (vr1min
, *vr0min
) == 1))
1687 /* ( [ ] ) or ([ ] ) or ( [ ]) */
1688 if (*vr0type
== VR_RANGE
1689 && vr1type
== VR_RANGE
)
1690 /* Choose the inner range. */
1692 else if (*vr0type
== VR_ANTI_RANGE
1693 && vr1type
== VR_RANGE
)
1695 /* Choose the right gap if the left is empty. */
1698 *vr0type
= VR_RANGE
;
1699 if (TREE_CODE (*vr0max
) != INTEGER_CST
)
1701 else if (TYPE_PRECISION (TREE_TYPE (*vr0max
)) == 1
1702 && !TYPE_UNSIGNED (TREE_TYPE (*vr0max
)))
1704 = int_const_binop (MINUS_EXPR
, *vr0max
,
1705 build_int_cst (TREE_TYPE (*vr0max
), -1));
1708 = int_const_binop (PLUS_EXPR
, *vr0max
,
1709 build_int_cst (TREE_TYPE (*vr0max
), 1));
1712 /* Choose the left gap if the right is empty. */
1715 *vr0type
= VR_RANGE
;
1716 if (TREE_CODE (*vr0min
) != INTEGER_CST
)
1718 else if (TYPE_PRECISION (TREE_TYPE (*vr0min
)) == 1
1719 && !TYPE_UNSIGNED (TREE_TYPE (*vr0min
)))
1721 = int_const_binop (PLUS_EXPR
, *vr0min
,
1722 build_int_cst (TREE_TYPE (*vr0min
), -1));
1725 = int_const_binop (MINUS_EXPR
, *vr0min
,
1726 build_int_cst (TREE_TYPE (*vr0min
), 1));
1729 /* Choose the anti-range if the range is effectively varying. */
1730 else if (vrp_val_is_min (vr1min
)
1731 && vrp_val_is_max (vr1max
))
1733 /* Choose the anti-range if it is ~[0,0], that range is special
1734 enough to special case when vr1's range is relatively wide.
1735 At least for types bigger than int - this covers pointers
1736 and arguments to functions like ctz. */
1737 else if (*vr0min
== *vr0max
1738 && integer_zerop (*vr0min
)
1739 && ((TYPE_PRECISION (TREE_TYPE (*vr0min
))
1740 >= TYPE_PRECISION (integer_type_node
))
1741 || POINTER_TYPE_P (TREE_TYPE (*vr0min
)))
1742 && TREE_CODE (vr1max
) == INTEGER_CST
1743 && TREE_CODE (vr1min
) == INTEGER_CST
1744 && (wi::clz (wi::to_wide (vr1max
) - wi::to_wide (vr1min
))
1745 < TYPE_PRECISION (TREE_TYPE (*vr0min
)) / 2))
1747 /* Else choose the range. */
1755 else if (*vr0type
== VR_ANTI_RANGE
1756 && vr1type
== VR_ANTI_RANGE
)
1758 /* If both are anti-ranges the result is the outer one. */
1763 else if (vr1type
== VR_ANTI_RANGE
1764 && *vr0type
== VR_RANGE
)
1766 /* The intersection is empty. */
1767 *vr0type
= VR_UNDEFINED
;
1768 *vr0min
= NULL_TREE
;
1769 *vr0max
= NULL_TREE
;
1774 else if ((operand_less_p (vr1min
, *vr0max
) == 1
1775 || operand_equal_p (vr1min
, *vr0max
, 0))
1776 && operand_less_p (*vr0min
, vr1min
) == 1
1777 && operand_less_p (*vr0max
, vr1max
) == 1)
1779 /* [ ( ] ) or [ ]( ) */
1780 if (*vr0type
== VR_ANTI_RANGE
1781 && vr1type
== VR_ANTI_RANGE
)
1783 else if (*vr0type
== VR_RANGE
1784 && vr1type
== VR_RANGE
)
1786 else if (*vr0type
== VR_RANGE
1787 && vr1type
== VR_ANTI_RANGE
)
1789 if (TREE_CODE (vr1min
) == INTEGER_CST
)
1790 *vr0max
= int_const_binop (MINUS_EXPR
, vr1min
,
1791 build_int_cst (TREE_TYPE (vr1min
), 1));
1795 else if (*vr0type
== VR_ANTI_RANGE
1796 && vr1type
== VR_RANGE
)
1798 *vr0type
= VR_RANGE
;
1799 if (TREE_CODE (*vr0max
) == INTEGER_CST
)
1800 *vr0min
= int_const_binop (PLUS_EXPR
, *vr0max
,
1801 build_int_cst (TREE_TYPE (*vr0max
), 1));
1809 else if ((operand_less_p (*vr0min
, vr1max
) == 1
1810 || operand_equal_p (*vr0min
, vr1max
, 0))
1811 && operand_less_p (vr1min
, *vr0min
) == 1
1812 && operand_less_p (vr1max
, *vr0max
) == 1)
1814 /* ( [ ) ] or ( )[ ] */
1815 if (*vr0type
== VR_ANTI_RANGE
1816 && vr1type
== VR_ANTI_RANGE
)
1818 else if (*vr0type
== VR_RANGE
1819 && vr1type
== VR_RANGE
)
1821 else if (*vr0type
== VR_RANGE
1822 && vr1type
== VR_ANTI_RANGE
)
1824 if (TREE_CODE (vr1max
) == INTEGER_CST
)
1825 *vr0min
= int_const_binop (PLUS_EXPR
, vr1max
,
1826 build_int_cst (TREE_TYPE (vr1max
), 1));
1830 else if (*vr0type
== VR_ANTI_RANGE
1831 && vr1type
== VR_RANGE
)
1833 *vr0type
= VR_RANGE
;
1834 if (TREE_CODE (*vr0min
) == INTEGER_CST
)
1835 *vr0max
= int_const_binop (MINUS_EXPR
, *vr0min
,
1836 build_int_cst (TREE_TYPE (*vr0min
), 1));
1845 /* If we know the intersection is empty, there's no need to
1846 conservatively add anything else to the set. */
1847 if (*vr0type
== VR_UNDEFINED
)
1850 /* As a fallback simply use { *VRTYPE, *VR0MIN, *VR0MAX } as
1851 result for the intersection. That's always a conservative
1852 correct estimate unless VR1 is a constant singleton range
1853 in which case we choose that. */
1854 if (vr1type
== VR_RANGE
1855 && is_gimple_min_invariant (vr1min
)
1856 && vrp_operand_equal_p (vr1min
, vr1max
))
1864 /* Helper for the intersection operation for value ranges. Given two
1865 ranges VR0 and VR1, set VR0 to the intersection of both ranges.
1866 This may not be the smallest possible such range. */
1869 irange::legacy_intersect (irange
*vr0
, const irange
*vr1
)
1871 gcc_checking_assert (vr0
->legacy_mode_p ());
1872 gcc_checking_assert (vr1
->legacy_mode_p ());
1873 /* If either range is VR_VARYING the other one wins. */
1874 if (vr1
->varying_p ())
1876 if (vr0
->varying_p ())
1878 vr0
->set (vr1
->min (), vr1
->max (), vr1
->kind ());
1882 /* When either range is VR_UNDEFINED the resulting range is
1883 VR_UNDEFINED, too. */
1884 if (vr0
->undefined_p ())
1886 if (vr1
->undefined_p ())
1888 vr0
->set_undefined ();
1892 value_range_kind vr0kind
= vr0
->kind ();
1893 tree vr0min
= vr0
->min ();
1894 tree vr0max
= vr0
->max ();
1896 intersect_ranges (&vr0kind
, &vr0min
, &vr0max
,
1897 vr1
->kind (), vr1
->min (), vr1
->max ());
1899 /* Make sure to canonicalize the result though as the inversion of a
1900 VR_RANGE can still be a VR_RANGE. */
1901 if (vr0kind
== VR_UNDEFINED
)
1902 vr0
->set_undefined ();
1903 else if (vr0kind
== VR_VARYING
)
1905 /* If we failed, use the original VR0. */
1909 vr0
->set (vr0min
, vr0max
, vr0kind
);
1912 /* Union the two value-ranges { *VR0TYPE, *VR0MIN, *VR0MAX } and
1913 { VR1TYPE, VR0MIN, VR0MAX } and store the result
1914 in { *VR0TYPE, *VR0MIN, *VR0MAX }. This may not be the smallest
1915 possible such range. The resulting range is not canonicalized. */
1918 union_ranges (enum value_range_kind
*vr0type
,
1919 tree
*vr0min
, tree
*vr0max
,
1920 enum value_range_kind vr1type
,
1921 tree vr1min
, tree vr1max
)
1923 int cmpmin
= compare_values (*vr0min
, vr1min
);
1924 int cmpmax
= compare_values (*vr0max
, vr1max
);
1925 bool mineq
= cmpmin
== 0;
1926 bool maxeq
= cmpmax
== 0;
1928 /* [] is vr0, () is vr1 in the following classification comments. */
1932 if (*vr0type
== vr1type
)
1933 /* Nothing to do for equal ranges. */
1935 else if ((*vr0type
== VR_RANGE
1936 && vr1type
== VR_ANTI_RANGE
)
1937 || (*vr0type
== VR_ANTI_RANGE
1938 && vr1type
== VR_RANGE
))
1940 /* For anti-range with range union the result is varying. */
1946 else if (operand_less_p (*vr0max
, vr1min
) == 1
1947 || operand_less_p (vr1max
, *vr0min
) == 1)
1949 /* [ ] ( ) or ( ) [ ]
1950 If the ranges have an empty intersection, result of the union
1951 operation is the anti-range or if both are anti-ranges
1953 if (*vr0type
== VR_ANTI_RANGE
1954 && vr1type
== VR_ANTI_RANGE
)
1956 else if (*vr0type
== VR_ANTI_RANGE
1957 && vr1type
== VR_RANGE
)
1959 else if (*vr0type
== VR_RANGE
1960 && vr1type
== VR_ANTI_RANGE
)
1966 else if (*vr0type
== VR_RANGE
1967 && vr1type
== VR_RANGE
)
1969 /* The result is the convex hull of both ranges. */
1970 if (operand_less_p (*vr0max
, vr1min
) == 1)
1972 /* If the result can be an anti-range, create one. */
1973 if (TREE_CODE (*vr0max
) == INTEGER_CST
1974 && TREE_CODE (vr1min
) == INTEGER_CST
1975 && vrp_val_is_min (*vr0min
)
1976 && vrp_val_is_max (vr1max
))
1978 tree min
= int_const_binop (PLUS_EXPR
,
1980 build_int_cst (TREE_TYPE (*vr0max
), 1));
1981 tree max
= int_const_binop (MINUS_EXPR
,
1983 build_int_cst (TREE_TYPE (vr1min
), 1));
1984 if (!operand_less_p (max
, min
))
1986 *vr0type
= VR_ANTI_RANGE
;
1998 /* If the result can be an anti-range, create one. */
1999 if (TREE_CODE (vr1max
) == INTEGER_CST
2000 && TREE_CODE (*vr0min
) == INTEGER_CST
2001 && vrp_val_is_min (vr1min
)
2002 && vrp_val_is_max (*vr0max
))
2004 tree min
= int_const_binop (PLUS_EXPR
,
2006 build_int_cst (TREE_TYPE (vr1max
), 1));
2007 tree max
= int_const_binop (MINUS_EXPR
,
2009 build_int_cst (TREE_TYPE (*vr0min
), 1));
2010 if (!operand_less_p (max
, min
))
2012 *vr0type
= VR_ANTI_RANGE
;
2026 else if ((maxeq
|| cmpmax
== 1)
2027 && (mineq
|| cmpmin
== -1))
2029 /* [ ( ) ] or [( ) ] or [ ( )] */
2030 if (*vr0type
== VR_RANGE
2031 && vr1type
== VR_RANGE
)
2033 else if (*vr0type
== VR_ANTI_RANGE
2034 && vr1type
== VR_ANTI_RANGE
)
2040 else if (*vr0type
== VR_ANTI_RANGE
2041 && vr1type
== VR_RANGE
)
2043 /* Arbitrarily choose the right or left gap. */
2044 if (!mineq
&& TREE_CODE (vr1min
) == INTEGER_CST
)
2045 *vr0max
= int_const_binop (MINUS_EXPR
, vr1min
,
2046 build_int_cst (TREE_TYPE (vr1min
), 1));
2047 else if (!maxeq
&& TREE_CODE (vr1max
) == INTEGER_CST
)
2048 *vr0min
= int_const_binop (PLUS_EXPR
, vr1max
,
2049 build_int_cst (TREE_TYPE (vr1max
), 1));
2053 else if (*vr0type
== VR_RANGE
2054 && vr1type
== VR_ANTI_RANGE
)
2055 /* The result covers everything. */
2060 else if ((maxeq
|| cmpmax
== -1)
2061 && (mineq
|| cmpmin
== 1))
2063 /* ( [ ] ) or ([ ] ) or ( [ ]) */
2064 if (*vr0type
== VR_RANGE
2065 && vr1type
== VR_RANGE
)
2071 else if (*vr0type
== VR_ANTI_RANGE
2072 && vr1type
== VR_ANTI_RANGE
)
2074 else if (*vr0type
== VR_RANGE
2075 && vr1type
== VR_ANTI_RANGE
)
2077 *vr0type
= VR_ANTI_RANGE
;
2078 if (!mineq
&& TREE_CODE (*vr0min
) == INTEGER_CST
)
2080 *vr0max
= int_const_binop (MINUS_EXPR
, *vr0min
,
2081 build_int_cst (TREE_TYPE (*vr0min
), 1));
2084 else if (!maxeq
&& TREE_CODE (*vr0max
) == INTEGER_CST
)
2086 *vr0min
= int_const_binop (PLUS_EXPR
, *vr0max
,
2087 build_int_cst (TREE_TYPE (*vr0max
), 1));
2093 else if (*vr0type
== VR_ANTI_RANGE
2094 && vr1type
== VR_RANGE
)
2095 /* The result covers everything. */
2100 else if (cmpmin
== -1
2102 && (operand_less_p (vr1min
, *vr0max
) == 1
2103 || operand_equal_p (vr1min
, *vr0max
, 0)))
2105 /* [ ( ] ) or [ ]( ) */
2106 if (*vr0type
== VR_RANGE
2107 && vr1type
== VR_RANGE
)
2109 else if (*vr0type
== VR_ANTI_RANGE
2110 && vr1type
== VR_ANTI_RANGE
)
2112 else if (*vr0type
== VR_ANTI_RANGE
2113 && vr1type
== VR_RANGE
)
2115 if (TREE_CODE (vr1min
) == INTEGER_CST
)
2116 *vr0max
= int_const_binop (MINUS_EXPR
, vr1min
,
2117 build_int_cst (TREE_TYPE (vr1min
), 1));
2121 else if (*vr0type
== VR_RANGE
2122 && vr1type
== VR_ANTI_RANGE
)
2124 if (TREE_CODE (*vr0max
) == INTEGER_CST
)
2127 *vr0min
= int_const_binop (PLUS_EXPR
, *vr0max
,
2128 build_int_cst (TREE_TYPE (*vr0max
), 1));
2137 else if (cmpmin
== 1
2139 && (operand_less_p (*vr0min
, vr1max
) == 1
2140 || operand_equal_p (*vr0min
, vr1max
, 0)))
2142 /* ( [ ) ] or ( )[ ] */
2143 if (*vr0type
== VR_RANGE
2144 && vr1type
== VR_RANGE
)
2146 else if (*vr0type
== VR_ANTI_RANGE
2147 && vr1type
== VR_ANTI_RANGE
)
2149 else if (*vr0type
== VR_ANTI_RANGE
2150 && vr1type
== VR_RANGE
)
2152 if (TREE_CODE (vr1max
) == INTEGER_CST
)
2153 *vr0min
= int_const_binop (PLUS_EXPR
, vr1max
,
2154 build_int_cst (TREE_TYPE (vr1max
), 1));
2158 else if (*vr0type
== VR_RANGE
2159 && vr1type
== VR_ANTI_RANGE
)
2161 if (TREE_CODE (*vr0min
) == INTEGER_CST
)
2164 *vr0max
= int_const_binop (MINUS_EXPR
, *vr0min
,
2165 build_int_cst (TREE_TYPE (*vr0min
), 1));
2180 *vr0type
= VR_VARYING
;
2181 *vr0min
= NULL_TREE
;
2182 *vr0max
= NULL_TREE
;
2185 /* Helper for meet operation for value ranges. Given two ranges VR0
2186 and VR1, set VR0 to the union of both ranges. This may not be the
2187 smallest possible such range. */
2190 irange::legacy_union (irange
*vr0
, const irange
*vr1
)
2192 gcc_checking_assert (vr0
->legacy_mode_p ());
2193 gcc_checking_assert (vr1
->legacy_mode_p ());
2195 /* VR0 has the resulting range if VR1 is undefined or VR0 is varying. */
2196 if (vr1
->undefined_p ()
2197 || vr0
->varying_p ())
2200 /* VR1 has the resulting range if VR0 is undefined or VR1 is varying. */
2201 if (vr0
->undefined_p ())
2203 vr0
->set (vr1
->min (), vr1
->max (), vr1
->kind ());
2207 if (vr1
->varying_p ())
2209 vr0
->set_varying (vr1
->type ());
2213 value_range_kind vr0kind
= vr0
->kind ();
2214 tree vr0min
= vr0
->min ();
2215 tree vr0max
= vr0
->max ();
2217 union_ranges (&vr0kind
, &vr0min
, &vr0max
,
2218 vr1
->kind (), vr1
->min (), vr1
->max ());
2220 if (vr0kind
== VR_UNDEFINED
)
2221 vr0
->set_undefined ();
2222 else if (vr0kind
== VR_VARYING
)
2224 /* Failed to find an efficient meet. Before giving up and
2225 setting the result to VARYING, see if we can at least derive
2226 a non-zero range. */
2227 if (range_includes_zero_p (vr0
) == 0
2228 && range_includes_zero_p (vr1
) == 0)
2229 vr0
->set_nonzero (vr0
->type ());
2231 vr0
->set_varying (vr0
->type ());
2234 vr0
->set (vr0min
, vr0max
, vr0kind
);
2237 /* Meet operation for value ranges. Given two value ranges VR0 and
2238 VR1, store in VR0 a range that contains both VR0 and VR1. This
2239 may not be the smallest possible such range.
2240 Return TRUE if the original value changes. */
2243 irange::legacy_verbose_union_ (const irange
*other
)
2245 if (legacy_mode_p ())
2247 if (!other
->legacy_mode_p ())
2249 int_range
<1> tmp
= *other
;
2250 legacy_union (this, &tmp
);
2253 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2255 fprintf (dump_file
, "Meeting\n ");
2256 dump_value_range (dump_file
, this);
2257 fprintf (dump_file
, "\nand\n ");
2258 dump_value_range (dump_file
, other
);
2259 fprintf (dump_file
, "\n");
2262 legacy_union (this, other
);
2264 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2266 fprintf (dump_file
, "to\n ");
2267 dump_value_range (dump_file
, this);
2268 fprintf (dump_file
, "\n");
2273 if (other
->legacy_mode_p ())
2275 int_range
<2> wider
= *other
;
2276 return irange_union (wider
);
2279 return irange_union (*other
);
2283 irange::legacy_verbose_intersect (const irange
*other
)
2285 if (legacy_mode_p ())
2287 if (!other
->legacy_mode_p ())
2289 int_range
<1> tmp
= *other
;
2290 legacy_intersect (this, &tmp
);
2293 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2295 fprintf (dump_file
, "Intersecting\n ");
2296 dump_value_range (dump_file
, this);
2297 fprintf (dump_file
, "\nand\n ");
2298 dump_value_range (dump_file
, other
);
2299 fprintf (dump_file
, "\n");
2302 legacy_intersect (this, other
);
2304 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2306 fprintf (dump_file
, "to\n ");
2307 dump_value_range (dump_file
, this);
2308 fprintf (dump_file
, "\n");
2313 if (other
->legacy_mode_p ())
2317 return irange_intersect (wider
);
2320 return irange_intersect (*other
);
2323 // Perform an efficient union with R when both ranges have only a single pair.
2324 // Excluded are VARYING and UNDEFINED ranges.
2327 irange::irange_single_pair_union (const irange
&r
)
2329 gcc_checking_assert (!undefined_p () && !varying_p ());
2330 gcc_checking_assert (!r
.undefined_p () && !varying_p ());
2332 signop sign
= TYPE_SIGN (TREE_TYPE (m_base
[0]));
2333 // Check if current lower bound is also the new lower bound.
2334 if (wi::le_p (wi::to_wide (m_base
[0]), wi::to_wide (r
.m_base
[0]), sign
))
2336 // If current upper bound is new upper bound, we're done.
2337 if (wi::le_p (wi::to_wide (r
.m_base
[1]), wi::to_wide (m_base
[1]), sign
))
2338 return union_nonzero_bits (r
);
2339 // Otherwise R has the new upper bound.
2340 // Check for overlap/touching ranges, or single target range.
2341 if (m_max_ranges
== 1
2342 || wi::to_widest (m_base
[1]) + 1 >= wi::to_widest (r
.m_base
[0]))
2343 m_base
[1] = r
.m_base
[1];
2346 // This is a dual range result.
2347 m_base
[2] = r
.m_base
[0];
2348 m_base
[3] = r
.m_base
[1];
2351 union_nonzero_bits (r
);
2355 // Set the new lower bound to R's lower bound.
2356 tree lb
= m_base
[0];
2357 m_base
[0] = r
.m_base
[0];
2359 // If R fully contains THIS range, just set the upper bound.
2360 if (wi::ge_p (wi::to_wide (r
.m_base
[1]), wi::to_wide (m_base
[1]), sign
))
2361 m_base
[1] = r
.m_base
[1];
2362 // Check for overlapping ranges, or target limited to a single range.
2363 else if (m_max_ranges
== 1
2364 || wi::to_widest (r
.m_base
[1]) + 1 >= wi::to_widest (lb
))
2368 // Left with 2 pairs.
2371 m_base
[3] = m_base
[1];
2372 m_base
[1] = r
.m_base
[1];
2374 union_nonzero_bits (r
);
2378 // union_ for multi-ranges.
2381 irange::irange_union (const irange
&r
)
2383 gcc_checking_assert (!legacy_mode_p () && !r
.legacy_mode_p ());
2385 if (r
.undefined_p ())
2401 set_varying (type ());
2405 // Special case one range union one range.
2406 if (m_num_ranges
== 1 && r
.m_num_ranges
== 1)
2407 return irange_single_pair_union (r
);
2409 // If this ranges fully contains R, then we need do nothing.
2410 if (irange_contains_p (r
))
2411 return union_nonzero_bits (r
);
2413 // Do not worry about merging and such by reserving twice as many
2414 // pairs as needed, and then simply sort the 2 ranges into this
2415 // intermediate form.
2417 // The intermediate result will have the property that the beginning
2418 // of each range is <= the beginning of the next range. There may
2419 // be overlapping ranges at this point. I.e. this would be valid
2420 // [-20, 10], [-10, 0], [0, 20], [40, 90] as it satisfies this
2421 // contraint : -20 < -10 < 0 < 40. When the range is rebuilt into r,
2422 // the merge is performed.
2424 // [Xi,Yi]..[Xn,Yn] U [Xj,Yj]..[Xm,Ym] --> [Xk,Yk]..[Xp,Yp]
2425 auto_vec
<tree
, 20> res (m_num_ranges
* 2 + r
.m_num_ranges
* 2);
2426 unsigned i
= 0, j
= 0, k
= 0;
2428 while (i
< m_num_ranges
* 2 && j
< r
.m_num_ranges
* 2)
2430 // lower of Xi and Xj is the lowest point.
2431 if (wi::to_widest (m_base
[i
]) <= wi::to_widest (r
.m_base
[j
]))
2433 res
.quick_push (m_base
[i
]);
2434 res
.quick_push (m_base
[i
+ 1]);
2440 res
.quick_push (r
.m_base
[j
]);
2441 res
.quick_push (r
.m_base
[j
+ 1]);
2446 for ( ; i
< m_num_ranges
* 2; i
+= 2)
2448 res
.quick_push (m_base
[i
]);
2449 res
.quick_push (m_base
[i
+ 1]);
2452 for ( ; j
< r
.m_num_ranges
* 2; j
+= 2)
2454 res
.quick_push (r
.m_base
[j
]);
2455 res
.quick_push (r
.m_base
[j
+ 1]);
2459 // Now normalize the vector removing any overlaps.
2461 for (j
= 2; j
< k
; j
+= 2)
2463 // Current upper+1 is >= lower bound next pair, then we merge ranges.
2464 if (wi::to_widest (res
[i
- 1]) + 1 >= wi::to_widest (res
[j
]))
2466 // New upper bounds is greater of current or the next one.
2467 if (wi::to_widest (res
[j
+ 1]) > wi::to_widest (res
[i
- 1]))
2468 res
[i
- 1] = res
[j
+ 1];
2472 // This is a new distinct range, but no point in copying it
2473 // if it is already in the right place.
2477 res
[i
++] = res
[j
+ 1];
2484 // At this point, the vector should have i ranges, none overlapping.
2485 // Now it simply needs to be copied, and if there are too many
2486 // ranges, merge some. We wont do any analysis as to what the
2487 // "best" merges are, simply combine the final ranges into one.
2488 if (i
> m_max_ranges
* 2)
2490 res
[m_max_ranges
* 2 - 1] = res
[i
- 1];
2491 i
= m_max_ranges
* 2;
2494 for (j
= 0; j
< i
; j
++)
2495 m_base
[j
] = res
[j
];
2496 m_num_ranges
= i
/ 2;
2499 union_nonzero_bits (r
);
2503 // Return TRUE if THIS fully contains R. No undefined or varying cases.
2506 irange::irange_contains_p (const irange
&r
) const
2508 gcc_checking_assert (!undefined_p () && !varying_p ());
2509 gcc_checking_assert (!r
.undefined_p () && !varying_p ());
2511 // In order for THIS to fully contain R, all of the pairs within R must
2512 // be fully contained by the pairs in this object.
2513 signop sign
= TYPE_SIGN (TREE_TYPE(m_base
[0]));
2516 tree rl
= r
.m_base
[0];
2517 tree ru
= r
.m_base
[1];
2522 // If r is contained within this range, move to the next R
2523 if (wi::ge_p (wi::to_wide (rl
), wi::to_wide (l
), sign
)
2524 && wi::le_p (wi::to_wide (ru
), wi::to_wide (u
), sign
))
2526 // This pair is OK, Either done, or bump to the next.
2527 if (++ri
>= r
.num_pairs ())
2529 rl
= r
.m_base
[ri
* 2];
2530 ru
= r
.m_base
[ri
* 2 + 1];
2533 // Otherwise, check if this's pair occurs before R's.
2534 if (wi::lt_p (wi::to_wide (u
), wi::to_wide (rl
), sign
))
2536 // There's still at least one pair of R left.
2537 if (++i
>= num_pairs ())
2540 u
= m_base
[i
* 2 + 1];
2549 // Intersect for multi-ranges. Return TRUE if anything changes.
2552 irange::irange_intersect (const irange
&r
)
2554 gcc_checking_assert (!legacy_mode_p () && !r
.legacy_mode_p ());
2555 gcc_checking_assert (undefined_p () || r
.undefined_p ()
2556 || range_compatible_p (type (), r
.type ()));
2560 if (r
.undefined_p ())
2573 if (r
.num_pairs () == 1)
2575 bool res
= intersect (r
.lower_bound (), r
.upper_bound ());
2579 res
|= intersect_nonzero_bits (r
);
2583 // If R fully contains this, then intersection will change nothing.
2584 if (r
.irange_contains_p (*this))
2585 return intersect_nonzero_bits (r
);
2587 signop sign
= TYPE_SIGN (TREE_TYPE(m_base
[0]));
2588 unsigned bld_pair
= 0;
2589 unsigned bld_lim
= m_max_ranges
;
2590 int_range_max
r2 (*this);
2591 unsigned r2_lim
= r2
.num_pairs ();
2593 for (unsigned i
= 0; i
< r
.num_pairs (); )
2595 // If r1's upper is < r2's lower, we can skip r1's pair.
2596 tree ru
= r
.m_base
[i
* 2 + 1];
2597 tree r2l
= r2
.m_base
[i2
* 2];
2598 if (wi::lt_p (wi::to_wide (ru
), wi::to_wide (r2l
), sign
))
2603 // Likewise, skip r2's pair if its excluded.
2604 tree r2u
= r2
.m_base
[i2
* 2 + 1];
2605 tree rl
= r
.m_base
[i
* 2];
2606 if (wi::lt_p (wi::to_wide (r2u
), wi::to_wide (rl
), sign
))
2611 // No more r2, break.
2615 // Must be some overlap. Find the highest of the lower bounds,
2616 // and set it, unless the build limits lower bounds is already
2618 if (bld_pair
< bld_lim
)
2620 if (wi::ge_p (wi::to_wide (rl
), wi::to_wide (r2l
), sign
))
2621 m_base
[bld_pair
* 2] = rl
;
2623 m_base
[bld_pair
* 2] = r2l
;
2626 // Decrease and set a new upper.
2629 // ...and choose the lower of the upper bounds.
2630 if (wi::le_p (wi::to_wide (ru
), wi::to_wide (r2u
), sign
))
2632 m_base
[bld_pair
* 2 + 1] = ru
;
2634 // Move past the r1 pair and keep trying.
2640 m_base
[bld_pair
* 2 + 1] = r2u
;
2645 // No more r2, break.
2648 // r2 has the higher lower bound.
2651 // At the exit of this loop, it is one of 2 things:
2652 // ran out of r1, or r2, but either means we are done.
2653 m_num_ranges
= bld_pair
;
2654 if (m_num_ranges
== 0)
2661 intersect_nonzero_bits (r
);
2666 // Multirange intersect for a specified wide_int [lb, ub] range.
2667 // Return TRUE if intersect changed anything.
2669 // NOTE: It is the caller's responsibility to intersect the nonzero masks.
2672 irange::intersect (const wide_int
& lb
, const wide_int
& ub
)
2674 // Undefined remains undefined.
2678 if (legacy_mode_p ())
2680 intersect (int_range
<1> (type (), lb
, ub
));
2684 tree range_type
= type();
2685 signop sign
= TYPE_SIGN (range_type
);
2687 gcc_checking_assert (TYPE_PRECISION (range_type
) == wi::get_precision (lb
));
2688 gcc_checking_assert (TYPE_PRECISION (range_type
) == wi::get_precision (ub
));
2690 // If this range is fuly contained, then intersection will do nothing.
2691 if (wi::ge_p (lower_bound (), lb
, sign
)
2692 && wi::le_p (upper_bound (), ub
, sign
))
2695 unsigned bld_index
= 0;
2696 unsigned pair_lim
= num_pairs ();
2697 for (unsigned i
= 0; i
< pair_lim
; i
++)
2699 tree pairl
= m_base
[i
* 2];
2700 tree pairu
= m_base
[i
* 2 + 1];
2701 // Once UB is less than a pairs lower bound, we're done.
2702 if (wi::lt_p (ub
, wi::to_wide (pairl
), sign
))
2704 // if LB is greater than this pairs upper, this pair is excluded.
2705 if (wi::lt_p (wi::to_wide (pairu
), lb
, sign
))
2708 // Must be some overlap. Find the highest of the lower bounds,
2710 if (wi::gt_p (lb
, wi::to_wide (pairl
), sign
))
2711 m_base
[bld_index
* 2] = wide_int_to_tree (range_type
, lb
);
2713 m_base
[bld_index
* 2] = pairl
;
2715 // ...and choose the lower of the upper bounds and if the base pair
2716 // has the lower upper bound, need to check next pair too.
2717 if (wi::lt_p (ub
, wi::to_wide (pairu
), sign
))
2719 m_base
[bld_index
++ * 2 + 1] = wide_int_to_tree (range_type
, ub
);
2723 m_base
[bld_index
++ * 2 + 1] = pairu
;
2726 m_num_ranges
= bld_index
;
2727 if (m_num_ranges
== 0)
2734 // No need to call normalize_kind(), as the caller will do this
2735 // while intersecting the nonzero mask.
2742 // Signed 1-bits are strange. You can't subtract 1, because you can't
2743 // represent the number 1. This works around that for the invert routine.
2745 static wide_int
inline
2746 subtract_one (const wide_int
&x
, tree type
, wi::overflow_type
&overflow
)
2748 if (TYPE_SIGN (type
) == SIGNED
)
2749 return wi::add (x
, -1, SIGNED
, &overflow
);
2751 return wi::sub (x
, 1, UNSIGNED
, &overflow
);
2754 // The analogous function for adding 1.
2756 static wide_int
inline
2757 add_one (const wide_int
&x
, tree type
, wi::overflow_type
&overflow
)
2759 if (TYPE_SIGN (type
) == SIGNED
)
2760 return wi::sub (x
, -1, SIGNED
, &overflow
);
2762 return wi::add (x
, 1, UNSIGNED
, &overflow
);
2765 // Return the inverse of a range.
2770 if (legacy_mode_p ())
2772 // We can't just invert VR_RANGE and VR_ANTI_RANGE because we may
2773 // create non-canonical ranges. Use the constructors instead.
2774 if (m_kind
== VR_RANGE
)
2775 *this = value_range (min (), max (), VR_ANTI_RANGE
);
2776 else if (m_kind
== VR_ANTI_RANGE
)
2777 *this = value_range (min (), max ());
2783 gcc_checking_assert (!undefined_p () && !varying_p ());
2785 // We always need one more set of bounds to represent an inverse, so
2786 // if we're at the limit, we can't properly represent things.
2788 // For instance, to represent the inverse of a 2 sub-range set
2789 // [5, 10][20, 30], we would need a 3 sub-range set
2790 // [-MIN, 4][11, 19][31, MAX].
2792 // In this case, return the most conservative thing.
2794 // However, if any of the extremes of the range are -MIN/+MAX, we
2795 // know we will not need an extra bound. For example:
2797 // INVERT([-MIN,20][30,40]) => [21,29][41,+MAX]
2798 // INVERT([-MIN,20][30,MAX]) => [21,29]
2799 tree ttype
= type ();
2800 unsigned prec
= TYPE_PRECISION (ttype
);
2801 signop sign
= TYPE_SIGN (ttype
);
2802 wide_int type_min
= wi::min_value (prec
, sign
);
2803 wide_int type_max
= wi::max_value (prec
, sign
);
2804 m_nonzero_mask
= NULL
;
2805 if (m_num_ranges
== m_max_ranges
2806 && lower_bound () != type_min
2807 && upper_bound () != type_max
)
2809 m_base
[1] = wide_int_to_tree (ttype
, type_max
);
2813 // The algorithm is as follows. To calculate INVERT ([a,b][c,d]), we
2814 // generate [-MIN, a-1][b+1, c-1][d+1, MAX].
2816 // If there is an over/underflow in the calculation for any
2817 // sub-range, we eliminate that subrange. This allows us to easily
2818 // calculate INVERT([-MIN, 5]) with: [-MIN, -MIN-1][6, MAX]. And since
2819 // we eliminate the underflow, only [6, MAX] remains.
2821 wi::overflow_type ovf
;
2822 // Construct leftmost range.
2823 int_range_max
orig_range (*this);
2824 unsigned nitems
= 0;
2826 // If this is going to underflow on the MINUS 1, don't even bother
2827 // checking. This also handles subtracting one from an unsigned 0,
2828 // which doesn't set the underflow bit.
2829 if (type_min
!= orig_range
.lower_bound ())
2831 m_base
[nitems
++] = wide_int_to_tree (ttype
, type_min
);
2832 tmp
= subtract_one (orig_range
.lower_bound (), ttype
, ovf
);
2833 m_base
[nitems
++] = wide_int_to_tree (ttype
, tmp
);
2838 // Construct middle ranges if applicable.
2839 if (orig_range
.num_pairs () > 1)
2842 for (; j
< (orig_range
.num_pairs () * 2) - 1; j
+= 2)
2844 // The middle ranges cannot have MAX/MIN, so there's no need
2845 // to check for unsigned overflow on the +1 and -1 here.
2846 tmp
= wi::add (wi::to_wide (orig_range
.m_base
[j
]), 1, sign
, &ovf
);
2847 m_base
[nitems
++] = wide_int_to_tree (ttype
, tmp
);
2848 tmp
= subtract_one (wi::to_wide (orig_range
.m_base
[j
+ 1]),
2850 m_base
[nitems
++] = wide_int_to_tree (ttype
, tmp
);
2856 // Construct rightmost range.
2858 // However, if this will overflow on the PLUS 1, don't even bother.
2859 // This also handles adding one to an unsigned MAX, which doesn't
2860 // set the overflow bit.
2861 if (type_max
!= wi::to_wide (orig_range
.m_base
[i
]))
2863 tmp
= add_one (wi::to_wide (orig_range
.m_base
[i
]), ttype
, ovf
);
2864 m_base
[nitems
++] = wide_int_to_tree (ttype
, tmp
);
2865 m_base
[nitems
++] = wide_int_to_tree (ttype
, type_max
);
2869 m_num_ranges
= nitems
/ 2;
2871 // We disallow undefined or varying coming in, so the result can
2872 // only be a VR_RANGE.
2873 gcc_checking_assert (m_kind
== VR_RANGE
);
2879 // Return the nonzero bits inherent in the range.
2882 irange::get_nonzero_bits_from_range () const
2884 // For legacy symbolics.
2886 return wi::shwi (-1, TYPE_PRECISION (type ()));
2888 wide_int min
= lower_bound ();
2889 wide_int max
= upper_bound ();
2890 wide_int xorv
= min
^ max
;
2893 unsigned prec
= TYPE_PRECISION (type ());
2894 xorv
= wi::mask (prec
- wi::clz (xorv
), false, prec
);
2899 // If the the nonzero mask can be trivially converted to a range, do
2900 // so and return TRUE.
2903 irange::set_range_from_nonzero_bits ()
2905 gcc_checking_assert (!undefined_p ());
2906 if (!m_nonzero_mask
)
2908 unsigned popcount
= wi::popcount (wi::to_wide (m_nonzero_mask
));
2910 // If we have only one bit set in the mask, we can figure out the
2911 // range immediately.
2914 // Make sure we don't pessimize the range.
2915 if (!contains_p (m_nonzero_mask
))
2918 bool has_zero
= contains_p (build_zero_cst (type ()));
2919 tree nz
= m_nonzero_mask
;
2921 m_nonzero_mask
= nz
;
2925 zero
.set_zero (type ());
2930 else if (popcount
== 0)
2939 irange::set_nonzero_bits (const wide_int_ref
&bits
)
2941 gcc_checking_assert (!undefined_p ());
2942 unsigned prec
= TYPE_PRECISION (type ());
2946 m_nonzero_mask
= NULL
;
2953 // Drop VARYINGs with a nonzero mask to a plain range.
2954 if (m_kind
== VR_VARYING
&& bits
!= -1)
2957 wide_int nz
= wide_int::from (bits
, prec
, TYPE_SIGN (type ()));
2958 m_nonzero_mask
= wide_int_to_tree (type (), nz
);
2959 if (set_range_from_nonzero_bits ())
2967 // Return the nonzero bitmask. This will return the nonzero bits plus
2968 // the nonzero bits inherent in the range.
2971 irange::get_nonzero_bits () const
2973 gcc_checking_assert (!undefined_p ());
2974 // The nonzero mask inherent in the range is calculated on-demand.
2975 // For example, [0,255] does not have a 0xff nonzero mask by default
2976 // (unless manually set). This saves us considerable time, because
2977 // setting it at creation incurs a large penalty for irange::set.
2978 // At the time of writing there was a 5% slowdown in VRP if we kept
2979 // the mask precisely up to date at all times. Instead, we default
2980 // to -1 and set it when explicitly requested. However, this
2981 // function will always return the correct mask.
2983 return wi::to_wide (m_nonzero_mask
) & get_nonzero_bits_from_range ();
2985 return get_nonzero_bits_from_range ();
2988 // Convert tree mask to wide_int. Returns -1 for NULL masks.
2991 mask_to_wi (tree mask
, tree type
)
2994 return wi::to_wide (mask
);
2996 return wi::shwi (-1, TYPE_PRECISION (type
));
2999 // Intersect the nonzero bits in R into THIS and normalize the range.
3000 // Return TRUE if the intersection changed anything.
3003 irange::intersect_nonzero_bits (const irange
&r
)
3005 gcc_checking_assert (!undefined_p () && !r
.undefined_p ());
3007 if (!m_nonzero_mask
&& !r
.m_nonzero_mask
)
3015 bool changed
= false;
3017 if (mask_to_wi (m_nonzero_mask
, t
) != mask_to_wi (r
.m_nonzero_mask
, t
))
3019 wide_int nz
= get_nonzero_bits () & r
.get_nonzero_bits ();
3020 m_nonzero_mask
= wide_int_to_tree (t
, nz
);
3021 if (set_range_from_nonzero_bits ())
3031 // Union the nonzero bits in R into THIS and normalize the range.
3032 // Return TRUE if the union changed anything.
3035 irange::union_nonzero_bits (const irange
&r
)
3037 gcc_checking_assert (!undefined_p () && !r
.undefined_p ());
3039 if (!m_nonzero_mask
&& !r
.m_nonzero_mask
)
3047 bool changed
= false;
3049 if (mask_to_wi (m_nonzero_mask
, t
) != mask_to_wi (r
.m_nonzero_mask
, t
))
3051 wide_int nz
= get_nonzero_bits () | r
.get_nonzero_bits ();
3052 m_nonzero_mask
= wide_int_to_tree (t
, nz
);
3053 // No need to call set_range_from_nonzero_bits, because we'll
3054 // never narrow the range. Besides, it would cause endless
3055 // recursion because of the union_ in
3056 // set_range_from_nonzero_bits.
3066 dump_value_range (FILE *file
, const vrange
*vr
)
3072 debug (const vrange
*vr
)
3074 dump_value_range (stderr
, vr
);
3075 fprintf (stderr
, "\n");
3079 debug (const vrange
&vr
)
3085 debug (const value_range
*vr
)
3087 dump_value_range (stderr
, vr
);
3088 fprintf (stderr
, "\n");
3092 debug (const value_range
&vr
)
3094 dump_value_range (stderr
, &vr
);
3095 fprintf (stderr
, "\n");
3098 /* Create two value-ranges in *VR0 and *VR1 from the anti-range *AR
3099 so that *VR0 U *VR1 == *AR. Returns true if that is possible,
3100 false otherwise. If *AR can be represented with a single range
3101 *VR1 will be VR_UNDEFINED. */
3104 ranges_from_anti_range (const value_range
*ar
,
3105 value_range
*vr0
, value_range
*vr1
)
3107 tree type
= ar
->type ();
3109 vr0
->set_undefined ();
3110 vr1
->set_undefined ();
3112 /* As a future improvement, we could handle ~[0, A] as: [-INF, -1] U
3113 [A+1, +INF]. Not sure if this helps in practice, though. */
3115 if (ar
->kind () != VR_ANTI_RANGE
3116 || TREE_CODE (ar
->min ()) != INTEGER_CST
3117 || TREE_CODE (ar
->max ()) != INTEGER_CST
3118 || !vrp_val_min (type
)
3119 || !vrp_val_max (type
))
3122 if (tree_int_cst_lt (vrp_val_min (type
), ar
->min ()))
3123 vr0
->set (vrp_val_min (type
),
3124 wide_int_to_tree (type
, wi::to_wide (ar
->min ()) - 1));
3125 if (tree_int_cst_lt (ar
->max (), vrp_val_max (type
)))
3126 vr1
->set (wide_int_to_tree (type
, wi::to_wide (ar
->max ()) + 1),
3127 vrp_val_max (type
));
3128 if (vr0
->undefined_p ())
3131 vr1
->set_undefined ();
3134 return !vr0
->undefined_p ();
3138 range_has_numeric_bounds_p (const irange
*vr
)
3140 return (!vr
->undefined_p ()
3141 && TREE_CODE (vr
->min ()) == INTEGER_CST
3142 && TREE_CODE (vr
->max ()) == INTEGER_CST
);
3145 /* Return whether VAL is equal to the maximum value of its type.
3146 We can't do a simple equality comparison with TYPE_MAX_VALUE because
3147 C typedefs and Ada subtypes can produce types whose TYPE_MAX_VALUE
3148 is not == to the integer constant with the same value in the type. */
3151 vrp_val_is_max (const_tree val
)
3153 tree type_max
= vrp_val_max (TREE_TYPE (val
));
3154 return (val
== type_max
3155 || (type_max
!= NULL_TREE
3156 && operand_equal_p (val
, type_max
, 0)));
3159 /* Return whether VAL is equal to the minimum value of its type. */
3162 vrp_val_is_min (const_tree val
)
3164 tree type_min
= vrp_val_min (TREE_TYPE (val
));
3165 return (val
== type_min
3166 || (type_min
!= NULL_TREE
3167 && operand_equal_p (val
, type_min
, 0)));
3170 /* Return true, if VAL1 and VAL2 are equal values for VRP purposes. */
3173 vrp_operand_equal_p (const_tree val1
, const_tree val2
)
3177 if (!val1
|| !val2
|| !operand_equal_p (val1
, val2
, 0))
3182 // ?? These stubs are for ipa-prop.cc which use a value_range in a
3183 // hash_traits. hash-traits.h defines an extern of gt_ggc_mx (T &)
3184 // instead of picking up the gt_ggc_mx (T *) version.
3186 gt_pch_nx (int_range
<1> *&x
)
3188 return gt_pch_nx ((irange
*) x
);
3192 gt_ggc_mx (int_range
<1> *&x
)
3194 return gt_ggc_mx ((irange
*) x
);
3197 #define DEFINE_INT_RANGE_INSTANCE(N) \
3198 template int_range<N>::int_range(tree, tree, value_range_kind); \
3199 template int_range<N>::int_range(tree_node *, \
3202 value_range_kind); \
3203 template int_range<N>::int_range(tree); \
3204 template int_range<N>::int_range(const irange &); \
3205 template int_range<N>::int_range(const int_range &); \
3206 template int_range<N>& int_range<N>::operator= (const int_range &);
3208 DEFINE_INT_RANGE_INSTANCE(1)
3209 DEFINE_INT_RANGE_INSTANCE(2)
3210 DEFINE_INT_RANGE_INSTANCE(3)
3211 DEFINE_INT_RANGE_INSTANCE(255)
3214 #include "selftest.h"
3218 #define INT(N) build_int_cst (integer_type_node, (N))
3219 #define UINT(N) build_int_cstu (unsigned_type_node, (N))
3220 #define UINT128(N) build_int_cstu (u128_type, (N))
3221 #define UCHAR(N) build_int_cstu (unsigned_char_type_node, (N))
3222 #define SCHAR(N) build_int_cst (signed_char_type_node, (N))
3225 build_range3 (int a
, int b
, int c
, int d
, int e
, int f
)
3227 int_range
<3> i1 (INT (a
), INT (b
));
3228 int_range
<3> i2 (INT (c
), INT (d
));
3229 int_range
<3> i3 (INT (e
), INT (f
));
3236 range_tests_irange3 ()
3238 typedef int_range
<3> int_range3
;
3239 int_range3 r0
, r1
, r2
;
3240 int_range3 i1
, i2
, i3
;
3242 // ([10,20] U [5,8]) U [1,3] ==> [1,3][5,8][10,20].
3243 r0
= int_range3 (INT (10), INT (20));
3244 r1
= int_range3 (INT (5), INT (8));
3246 r1
= int_range3 (INT (1), INT (3));
3248 ASSERT_TRUE (r0
== build_range3 (1, 3, 5, 8, 10, 20));
3250 // [1,3][5,8][10,20] U [-5,0] => [-5,3][5,8][10,20].
3251 r1
= int_range3 (INT (-5), INT (0));
3253 ASSERT_TRUE (r0
== build_range3 (-5, 3, 5, 8, 10, 20));
3255 // [10,20][30,40] U [50,60] ==> [10,20][30,40][50,60].
3256 r1
= int_range3 (INT (50), INT (60));
3257 r0
= int_range3 (INT (10), INT (20));
3258 r0
.union_ (int_range3 (INT (30), INT (40)));
3260 ASSERT_TRUE (r0
== build_range3 (10, 20, 30, 40, 50, 60));
3261 // [10,20][30,40][50,60] U [70, 80] ==> [10,20][30,40][50,60][70,80].
3262 r1
= int_range3 (INT (70), INT (80));
3265 r2
= build_range3 (10, 20, 30, 40, 50, 60);
3266 r2
.union_ (int_range3 (INT (70), INT (80)));
3267 ASSERT_TRUE (r0
== r2
);
3269 // [10,20][30,40][50,60] U [6,35] => [6,40][50,60].
3270 r0
= build_range3 (10, 20, 30, 40, 50, 60);
3271 r1
= int_range3 (INT (6), INT (35));
3273 r1
= int_range3 (INT (6), INT (40));
3274 r1
.union_ (int_range3 (INT (50), INT (60)));
3275 ASSERT_TRUE (r0
== r1
);
3277 // [10,20][30,40][50,60] U [6,60] => [6,60].
3278 r0
= build_range3 (10, 20, 30, 40, 50, 60);
3279 r1
= int_range3 (INT (6), INT (60));
3281 ASSERT_TRUE (r0
== int_range3 (INT (6), INT (60)));
3283 // [10,20][30,40][50,60] U [6,70] => [6,70].
3284 r0
= build_range3 (10, 20, 30, 40, 50, 60);
3285 r1
= int_range3 (INT (6), INT (70));
3287 ASSERT_TRUE (r0
== int_range3 (INT (6), INT (70)));
3289 // [10,20][30,40][50,60] U [35,70] => [10,20][30,70].
3290 r0
= build_range3 (10, 20, 30, 40, 50, 60);
3291 r1
= int_range3 (INT (35), INT (70));
3293 r1
= int_range3 (INT (10), INT (20));
3294 r1
.union_ (int_range3 (INT (30), INT (70)));
3295 ASSERT_TRUE (r0
== r1
);
3297 // [10,20][30,40][50,60] U [15,35] => [10,40][50,60].
3298 r0
= build_range3 (10, 20, 30, 40, 50, 60);
3299 r1
= int_range3 (INT (15), INT (35));
3301 r1
= int_range3 (INT (10), INT (40));
3302 r1
.union_ (int_range3 (INT (50), INT (60)));
3303 ASSERT_TRUE (r0
== r1
);
3305 // [10,20][30,40][50,60] U [35,35] => [10,20][30,40][50,60].
3306 r0
= build_range3 (10, 20, 30, 40, 50, 60);
3307 r1
= int_range3 (INT (35), INT (35));
3309 ASSERT_TRUE (r0
== build_range3 (10, 20, 30, 40, 50, 60));
3313 range_tests_int_range_max ()
3316 unsigned int nrange
;
3318 // Build a huge multi-range range.
3319 for (nrange
= 0; nrange
< 50; ++nrange
)
3321 int_range
<1> tmp (INT (nrange
*10), INT (nrange
*10 + 5));
3324 ASSERT_TRUE (big
.num_pairs () == nrange
);
3326 // Verify that we can copy it without loosing precision.
3327 int_range_max
copy (big
);
3328 ASSERT_TRUE (copy
.num_pairs () == nrange
);
3330 // Inverting it should produce one more sub-range.
3332 ASSERT_TRUE (big
.num_pairs () == nrange
+ 1);
3334 int_range
<1> tmp (INT (5), INT (37));
3335 big
.intersect (tmp
);
3336 ASSERT_TRUE (big
.num_pairs () == 4);
3338 // Test that [10,10][20,20] does NOT contain 15.
3340 int_range_max
i1 (build_int_cst (integer_type_node
, 10),
3341 build_int_cst (integer_type_node
, 10));
3342 int_range_max
i2 (build_int_cst (integer_type_node
, 20),
3343 build_int_cst (integer_type_node
, 20));
3345 ASSERT_FALSE (i1
.contains_p (build_int_cst (integer_type_node
, 15)));
3350 range_tests_legacy ()
3352 // Test truncating copy to int_range<1>.
3353 int_range
<3> big
= build_range3 (10, 20, 30, 40, 50, 60);
3354 int_range
<1> small
= big
;
3355 ASSERT_TRUE (small
== int_range
<1> (INT (10), INT (60)));
3357 // Test truncating copy to int_range<2>.
3358 int_range
<2> medium
= big
;
3359 ASSERT_TRUE (!medium
.undefined_p ());
3361 // Test that a truncating copy of [MIN,20][22,40][80,MAX]
3362 // ends up as a conservative anti-range of ~[21,21].
3363 big
= int_range
<3> (vrp_val_min (integer_type_node
), INT (20));
3364 big
.union_ (int_range
<1> (INT (22), INT (40)));
3365 big
.union_ (int_range
<1> (INT (80), vrp_val_max (integer_type_node
)));
3367 ASSERT_TRUE (small
== int_range
<1> (INT (21), INT (21), VR_ANTI_RANGE
));
3369 // Copying a legacy symbolic to an int_range should normalize the
3370 // symbolic at copy time.
3372 tree ssa
= make_ssa_name (integer_type_node
);
3373 value_range
legacy_range (ssa
, INT (25));
3374 int_range
<2> copy
= legacy_range
;
3375 ASSERT_TRUE (copy
== int_range
<2> (vrp_val_min (integer_type_node
),
3378 // Test that copying ~[abc_23, abc_23] to a multi-range yields varying.
3379 legacy_range
= value_range (ssa
, ssa
, VR_ANTI_RANGE
);
3380 copy
= legacy_range
;
3381 ASSERT_TRUE (copy
.varying_p ());
3384 // VARYING of different sizes should not be equal.
3385 tree big_type
= build_nonstandard_integer_type (32, 1);
3386 tree small_type
= build_nonstandard_integer_type (16, 1);
3387 int_range_max
r0 (big_type
);
3388 int_range_max
r1 (small_type
);
3389 ASSERT_TRUE (r0
!= r1
);
3390 value_range
vr0 (big_type
);
3391 int_range_max
vr1 (small_type
);
3392 ASSERT_TRUE (vr0
!= vr1
);
3395 // Simulate -fstrict-enums where the domain of a type is less than the
3399 range_tests_strict_enum ()
3401 // The enum can only hold [0, 3].
3402 tree rtype
= copy_node (unsigned_type_node
);
3403 TYPE_MIN_VALUE (rtype
) = build_int_cstu (rtype
, 0);
3404 TYPE_MAX_VALUE (rtype
) = build_int_cstu (rtype
, 3);
3406 // Test that even though vr1 covers the strict enum domain ([0, 3]),
3407 // it does not cover the domain of the underlying type.
3408 int_range
<1> vr1 (build_int_cstu (rtype
, 0), build_int_cstu (rtype
, 1));
3409 int_range
<1> vr2 (build_int_cstu (rtype
, 2), build_int_cstu (rtype
, 3));
3411 ASSERT_TRUE (vr1
== int_range
<1> (build_int_cstu (rtype
, 0),
3412 build_int_cstu (rtype
, 3)));
3413 ASSERT_FALSE (vr1
.varying_p ());
3415 // Test that copying to a multi-range does not change things.
3416 int_range
<2> ir1 (vr1
);
3417 ASSERT_TRUE (ir1
== vr1
);
3418 ASSERT_FALSE (ir1
.varying_p ());
3420 // The same test as above, but using TYPE_{MIN,MAX}_VALUE instead of [0,3].
3421 vr1
= int_range
<1> (TYPE_MIN_VALUE (rtype
), TYPE_MAX_VALUE (rtype
));
3423 ASSERT_TRUE (ir1
== vr1
);
3424 ASSERT_FALSE (ir1
.varying_p ());
3430 tree u128_type
= build_nonstandard_integer_type (128, /*unsigned=*/1);
3431 int_range
<1> i1
, i2
, i3
;
3432 int_range
<1> r0
, r1
, rold
;
3434 // Test 1-bit signed integer union.
3435 // [-1,-1] U [0,0] = VARYING.
3436 tree one_bit_type
= build_nonstandard_integer_type (1, 0);
3437 tree one_bit_min
= vrp_val_min (one_bit_type
);
3438 tree one_bit_max
= vrp_val_max (one_bit_type
);
3440 int_range
<2> min (one_bit_min
, one_bit_min
);
3441 int_range
<2> max (one_bit_max
, one_bit_max
);
3443 ASSERT_TRUE (max
.varying_p ());
3445 // Test that we can set a range of true+false for a 1-bit signed int.
3446 r0
= range_true_and_false (one_bit_type
);
3448 // Test inversion of 1-bit signed integers.
3450 int_range
<2> min (one_bit_min
, one_bit_min
);
3451 int_range
<2> max (one_bit_max
, one_bit_max
);
3455 ASSERT_TRUE (t
== max
);
3458 ASSERT_TRUE (t
== min
);
3461 // Test that NOT(255) is [0..254] in 8-bit land.
3462 int_range
<1> not_255 (UCHAR (255), UCHAR (255), VR_ANTI_RANGE
);
3463 ASSERT_TRUE (not_255
== int_range
<1> (UCHAR (0), UCHAR (254)));
3465 // Test that NOT(0) is [1..255] in 8-bit land.
3466 int_range
<1> not_zero
= range_nonzero (unsigned_char_type_node
);
3467 ASSERT_TRUE (not_zero
== int_range
<1> (UCHAR (1), UCHAR (255)));
3469 // Check that [0,127][0x..ffffff80,0x..ffffff]
3470 // => ~[128, 0x..ffffff7f].
3471 r0
= int_range
<1> (UINT128 (0), UINT128 (127));
3472 tree high
= build_minus_one_cst (u128_type
);
3473 // low = -1 - 127 => 0x..ffffff80.
3474 tree low
= fold_build2 (MINUS_EXPR
, u128_type
, high
, UINT128(127));
3475 r1
= int_range
<1> (low
, high
); // [0x..ffffff80, 0x..ffffffff]
3476 // r0 = [0,127][0x..ffffff80,0x..fffffff].
3478 // r1 = [128, 0x..ffffff7f].
3479 r1
= int_range
<1> (UINT128(128),
3480 fold_build2 (MINUS_EXPR
, u128_type
,
3481 build_minus_one_cst (u128_type
),
3484 ASSERT_TRUE (r0
== r1
);
3486 r0
.set_varying (integer_type_node
);
3487 tree minint
= wide_int_to_tree (integer_type_node
, r0
.lower_bound ());
3488 tree maxint
= wide_int_to_tree (integer_type_node
, r0
.upper_bound ());
3490 r0
.set_varying (short_integer_type_node
);
3492 r0
.set_varying (unsigned_type_node
);
3493 tree maxuint
= wide_int_to_tree (unsigned_type_node
, r0
.upper_bound ());
3495 // Check that ~[0,5] => [6,MAX] for unsigned int.
3496 r0
= int_range
<1> (UINT (0), UINT (5));
3498 ASSERT_TRUE (r0
== int_range
<1> (UINT(6), maxuint
));
3500 // Check that ~[10,MAX] => [0,9] for unsigned int.
3501 r0
= int_range
<1> (UINT(10), maxuint
);
3503 ASSERT_TRUE (r0
== int_range
<1> (UINT (0), UINT (9)));
3505 // Check that ~[0,5] => [6,MAX] for unsigned 128-bit numbers.
3506 r0
= int_range
<1> (UINT128 (0), UINT128 (5), VR_ANTI_RANGE
);
3507 r1
= int_range
<1> (UINT128(6), build_minus_one_cst (u128_type
));
3508 ASSERT_TRUE (r0
== r1
);
3510 // Check that [~5] is really [-MIN,4][6,MAX].
3511 r0
= int_range
<1> (INT (5), INT (5), VR_ANTI_RANGE
);
3512 r1
= int_range
<1> (minint
, INT (4));
3513 r1
.union_ (int_range
<1> (INT (6), maxint
));
3514 ASSERT_FALSE (r1
.undefined_p ());
3515 ASSERT_TRUE (r0
== r1
);
3517 r1
= int_range
<1> (INT (5), INT (5));
3518 int_range
<1> r2 (r1
);
3519 ASSERT_TRUE (r1
== r2
);
3521 r1
= int_range
<1> (INT (5), INT (10));
3523 r1
= int_range
<1> (integer_type_node
,
3524 wi::to_wide (INT (5)), wi::to_wide (INT (10)));
3525 ASSERT_TRUE (r1
.contains_p (INT (7)));
3527 r1
= int_range
<1> (SCHAR (0), SCHAR (20));
3528 ASSERT_TRUE (r1
.contains_p (SCHAR(15)));
3529 ASSERT_FALSE (r1
.contains_p (SCHAR(300)));
3531 // NOT([10,20]) ==> [-MIN,9][21,MAX].
3532 r0
= r1
= int_range
<1> (INT (10), INT (20));
3533 r2
= int_range
<1> (minint
, INT(9));
3534 r2
.union_ (int_range
<1> (INT(21), maxint
));
3535 ASSERT_FALSE (r2
.undefined_p ());
3537 ASSERT_TRUE (r1
== r2
);
3538 // Test that NOT(NOT(x)) == x.
3540 ASSERT_TRUE (r0
== r2
);
3542 // Test that booleans and their inverse work as expected.
3543 r0
= range_zero (boolean_type_node
);
3544 ASSERT_TRUE (r0
== int_range
<1> (build_zero_cst (boolean_type_node
),
3545 build_zero_cst (boolean_type_node
)));
3547 ASSERT_TRUE (r0
== int_range
<1> (build_one_cst (boolean_type_node
),
3548 build_one_cst (boolean_type_node
)));
3550 // Make sure NULL and non-NULL of pointer types work, and that
3551 // inverses of them are consistent.
3552 tree voidp
= build_pointer_type (void_type_node
);
3553 r0
= range_zero (voidp
);
3557 ASSERT_TRUE (r0
== r1
);
3559 // [10,20] U [15, 30] => [10, 30].
3560 r0
= int_range
<1> (INT (10), INT (20));
3561 r1
= int_range
<1> (INT (15), INT (30));
3563 ASSERT_TRUE (r0
== int_range
<1> (INT (10), INT (30)));
3565 // [15,40] U [] => [15,40].
3566 r0
= int_range
<1> (INT (15), INT (40));
3567 r1
.set_undefined ();
3569 ASSERT_TRUE (r0
== int_range
<1> (INT (15), INT (40)));
3571 // [10,20] U [10,10] => [10,20].
3572 r0
= int_range
<1> (INT (10), INT (20));
3573 r1
= int_range
<1> (INT (10), INT (10));
3575 ASSERT_TRUE (r0
== int_range
<1> (INT (10), INT (20)));
3577 // [10,20] U [9,9] => [9,20].
3578 r0
= int_range
<1> (INT (10), INT (20));
3579 r1
= int_range
<1> (INT (9), INT (9));
3581 ASSERT_TRUE (r0
== int_range
<1> (INT (9), INT (20)));
3583 // [10,20] ^ [15,30] => [15,20].
3584 r0
= int_range
<1> (INT (10), INT (20));
3585 r1
= int_range
<1> (INT (15), INT (30));
3587 ASSERT_TRUE (r0
== int_range
<1> (INT (15), INT (20)));
3589 // Test the internal sanity of wide_int's wrt HWIs.
3590 ASSERT_TRUE (wi::max_value (TYPE_PRECISION (boolean_type_node
),
3591 TYPE_SIGN (boolean_type_node
))
3592 == wi::uhwi (1, TYPE_PRECISION (boolean_type_node
)));
3595 r0
= int_range
<1> (INT (0), INT (0));
3596 ASSERT_TRUE (r0
.zero_p ());
3598 // Test nonzero_p().
3599 r0
= int_range
<1> (INT (0), INT (0));
3601 ASSERT_TRUE (r0
.nonzero_p ());
3603 // test legacy interaction
3605 r0
= int_range
<1> (UINT (1), UINT (1), VR_ANTI_RANGE
);
3607 r1
= int_range
<1> (UINT (3), UINT (3), VR_ANTI_RANGE
);
3609 // vv = [0,0][2,2][4, MAX]
3610 int_range
<3> vv
= r0
;
3613 ASSERT_TRUE (vv
.contains_p (UINT (2)));
3614 ASSERT_TRUE (vv
.num_pairs () == 3);
3616 // create r0 as legacy [1,1]
3617 r0
= int_range
<1> (UINT (1), UINT (1));
3618 // And union it with [0,0][2,2][4,MAX] multi range
3620 // The result should be [0,2][4,MAX], or ~[3,3] but it must contain 2
3621 ASSERT_TRUE (r0
.contains_p (UINT (2)));
3625 range_tests_nonzero_bits ()
3627 int_range
<2> r0
, r1
;
3629 // Adding nonzero bits to a varying drops the varying.
3630 r0
.set_varying (integer_type_node
);
3631 r0
.set_nonzero_bits (255);
3632 ASSERT_TRUE (!r0
.varying_p ());
3633 // Dropping the nonzero bits brings us back to varying.
3634 r0
.set_nonzero_bits (-1);
3635 ASSERT_TRUE (r0
.varying_p ());
3637 // Test contains_p with nonzero bits.
3638 r0
.set_zero (integer_type_node
);
3639 ASSERT_TRUE (r0
.contains_p (INT (0)));
3640 ASSERT_FALSE (r0
.contains_p (INT (1)));
3641 r0
.set_nonzero_bits (0xfe);
3642 ASSERT_FALSE (r0
.contains_p (INT (0x100)));
3643 ASSERT_FALSE (r0
.contains_p (INT (0x3)));
3645 // Union of nonzero bits.
3646 r0
.set_varying (integer_type_node
);
3647 r0
.set_nonzero_bits (0xf0);
3648 r1
.set_varying (integer_type_node
);
3649 r1
.set_nonzero_bits (0xf);
3651 ASSERT_TRUE (r0
.get_nonzero_bits () == 0xff);
3653 // Intersect of nonzero bits.
3654 r0
.set (INT (0), INT (255));
3655 r0
.set_nonzero_bits (0xfe);
3656 r1
.set_varying (integer_type_node
);
3657 r1
.set_nonzero_bits (0xf0);
3659 ASSERT_TRUE (r0
.get_nonzero_bits () == 0xf0);
3661 // Intersect where the mask of nonzero bits is implicit from the range.
3662 r0
.set_varying (integer_type_node
);
3663 r1
.set (INT (0), INT (255));
3665 ASSERT_TRUE (r0
.get_nonzero_bits () == 0xff);
3667 // The union of a mask of 0xff..ffff00 with a mask of 0xff spans the
3668 // entire domain, and makes the range a varying.
3669 r0
.set_varying (integer_type_node
);
3670 wide_int x
= wi::shwi (0xff, TYPE_PRECISION (integer_type_node
));
3671 x
= wi::bit_not (x
);
3672 r0
.set_nonzero_bits (x
); // 0xff..ff00
3673 r1
.set_varying (integer_type_node
);
3674 r1
.set_nonzero_bits (0xff);
3676 ASSERT_TRUE (r0
.varying_p ());
3678 // Test that setting a nonzero bit of 1 does not pessimize the range.
3679 r0
.set_zero (integer_type_node
);
3680 r0
.set_nonzero_bits (1);
3681 ASSERT_TRUE (r0
.zero_p ());
3684 // Build an frange from string endpoints.
3686 static inline frange
3687 frange_float (const char *lb
, const char *ub
, tree type
= float_type_node
)
3689 REAL_VALUE_TYPE min
, max
;
3690 gcc_assert (real_from_string (&min
, lb
) == 0);
3691 gcc_assert (real_from_string (&max
, ub
) == 0);
3692 return frange (type
, min
, max
);
3699 REAL_VALUE_TYPE q
, r
;
3702 // Equal ranges but with differing NAN bits are not equal.
3703 if (HONOR_NANS (float_type_node
))
3705 r1
= frange_float ("10", "12");
3713 // [10, 20] NAN ^ [30, 40] NAN = NAN.
3714 r0
= frange_float ("10", "20");
3715 r1
= frange_float ("30", "40");
3717 ASSERT_TRUE (r0
.known_isnan ());
3719 // [3,5] U [5,10] NAN = ... NAN
3720 r0
= frange_float ("3", "5");
3722 r1
= frange_float ("5", "10");
3724 ASSERT_TRUE (r0
.maybe_isnan ());
3727 // NAN ranges are not equal to each other.
3728 r0
.set_nan (float_type_node
);
3730 ASSERT_FALSE (r0
== r1
);
3731 ASSERT_FALSE (r0
== r0
);
3732 ASSERT_TRUE (r0
!= r0
);
3734 // [5,6] U NAN = [5,6] NAN.
3735 r0
= frange_float ("5", "6");
3737 r1
.set_nan (float_type_node
);
3739 real_from_string (&q
, "5");
3740 real_from_string (&r
, "6");
3741 ASSERT_TRUE (real_identical (&q
, &r0
.lower_bound ()));
3742 ASSERT_TRUE (real_identical (&r
, &r0
.upper_bound ()));
3743 ASSERT_TRUE (r0
.maybe_isnan ());
3746 r0
.set_nan (float_type_node
);
3747 r1
.set_nan (float_type_node
);
3749 ASSERT_TRUE (r0
.known_isnan ());
3751 // [INF, INF] NAN ^ NAN = NAN
3752 r0
.set_nan (float_type_node
);
3753 r1
= frange_float ("+Inf", "+Inf");
3754 if (!HONOR_NANS (float_type_node
))
3757 ASSERT_TRUE (r0
.known_isnan ());
3760 r0
.set_nan (float_type_node
);
3761 r1
.set_nan (float_type_node
);
3763 ASSERT_TRUE (r0
.known_isnan ());
3765 // +NAN ^ -NAN = UNDEFINED
3766 r0
.set_nan (float_type_node
, false);
3767 r1
.set_nan (float_type_node
, true);
3769 ASSERT_TRUE (r0
.undefined_p ());
3771 // VARYING ^ NAN = NAN.
3772 r0
.set_nan (float_type_node
);
3773 r1
.set_varying (float_type_node
);
3775 ASSERT_TRUE (r0
.known_isnan ());
3777 // [3,4] ^ NAN = UNDEFINED.
3778 r0
= frange_float ("3", "4");
3780 r1
.set_nan (float_type_node
);
3782 ASSERT_TRUE (r0
.undefined_p ());
3784 // [-3, 5] ^ NAN = UNDEFINED
3785 r0
= frange_float ("-3", "5");
3787 r1
.set_nan (float_type_node
);
3789 ASSERT_TRUE (r0
.undefined_p ());
3791 // Setting the NAN bit to yes does not make us a known NAN.
3792 r0
.set_varying (float_type_node
);
3794 ASSERT_FALSE (r0
.known_isnan ());
3796 // NAN is in a VARYING.
3797 r0
.set_varying (float_type_node
);
3798 real_nan (&r
, "", 1, TYPE_MODE (float_type_node
));
3799 tree nan
= build_real (float_type_node
, r
);
3800 ASSERT_TRUE (r0
.contains_p (nan
));
3802 // -NAN is in a VARYING.
3803 r0
.set_varying (float_type_node
);
3804 q
= real_value_negate (&r
);
3805 tree neg_nan
= build_real (float_type_node
, q
);
3806 ASSERT_TRUE (r0
.contains_p (neg_nan
));
3808 // Clearing the NAN on a [] NAN is the empty set.
3809 r0
.set_nan (float_type_node
);
3811 ASSERT_TRUE (r0
.undefined_p ());
3813 // [10,20] NAN ^ [21,25] NAN = [NAN]
3814 r0
= frange_float ("10", "20");
3816 r1
= frange_float ("21", "25");
3819 ASSERT_TRUE (r0
.known_isnan ());
3821 // NAN U [5,6] should be [5,6] +-NAN.
3822 r0
.set_nan (float_type_node
);
3823 r1
= frange_float ("5", "6");
3826 real_from_string (&q
, "5");
3827 real_from_string (&r
, "6");
3828 ASSERT_TRUE (real_identical (&q
, &r0
.lower_bound ()));
3829 ASSERT_TRUE (real_identical (&r
, &r0
.upper_bound ()));
3830 ASSERT_TRUE (!r0
.signbit_p (signbit
));
3831 ASSERT_TRUE (r0
.maybe_isnan ());
3835 range_tests_signed_zeros ()
3837 tree zero
= build_zero_cst (float_type_node
);
3838 tree neg_zero
= fold_build1 (NEGATE_EXPR
, float_type_node
, zero
);
3842 // [0,0] contains [0,0] but not [-0,-0] and vice versa.
3843 r0
= frange (zero
, zero
);
3844 r1
= frange (neg_zero
, neg_zero
);
3845 ASSERT_TRUE (r0
.contains_p (zero
));
3846 ASSERT_TRUE (!r0
.contains_p (neg_zero
));
3847 ASSERT_TRUE (r1
.contains_p (neg_zero
));
3848 ASSERT_TRUE (!r1
.contains_p (zero
));
3850 // Test contains_p() when we know the sign of the zero.
3851 r0
= frange (zero
, zero
);
3852 ASSERT_TRUE (r0
.contains_p (zero
));
3853 ASSERT_FALSE (r0
.contains_p (neg_zero
));
3854 r0
= frange (neg_zero
, neg_zero
);
3855 ASSERT_TRUE (r0
.contains_p (neg_zero
));
3856 ASSERT_FALSE (r0
.contains_p (zero
));
3858 // The intersection of zeros that differ in sign is a NAN (or
3859 // undefined if not honoring NANs).
3860 r0
= frange (neg_zero
, neg_zero
);
3861 r1
= frange (zero
, zero
);
3863 if (HONOR_NANS (float_type_node
))
3864 ASSERT_TRUE (r0
.known_isnan ());
3866 ASSERT_TRUE (r0
.undefined_p ());
3868 // The union of zeros that differ in sign is a zero with unknown sign.
3869 r0
= frange (zero
, zero
);
3870 r1
= frange (neg_zero
, neg_zero
);
3872 ASSERT_TRUE (r0
.zero_p () && !r0
.signbit_p (signbit
));
3874 // [-0, +0] has an unknown sign.
3875 r0
= frange (neg_zero
, zero
);
3876 ASSERT_TRUE (r0
.zero_p () && !r0
.signbit_p (signbit
));
3878 // [-0, +0] ^ [0, 0] is [0, 0]
3879 r0
= frange (neg_zero
, zero
);
3880 r1
= frange (zero
, zero
);
3882 ASSERT_TRUE (r0
.zero_p ());
3884 r0
= frange_float ("+0", "5");
3886 ASSERT_TRUE (r0
.signbit_p (signbit
) && !signbit
);
3888 r0
= frange_float ("-0", "5");
3890 ASSERT_TRUE (!r0
.signbit_p (signbit
));
3892 r0
= frange_float ("-0", "10");
3893 r1
= frange_float ("0", "5");
3895 ASSERT_TRUE (real_iszero (&r0
.lower_bound (), false));
3897 r0
= frange_float ("-0", "5");
3898 r1
= frange_float ("0", "5");
3900 ASSERT_TRUE (real_iszero (&r0
.lower_bound (), true));
3902 r0
= frange_float ("-5", "-0");
3904 r1
= frange_float ("0", "0");
3907 if (HONOR_NANS (float_type_node
))
3908 ASSERT_TRUE (r0
.known_isnan ());
3910 ASSERT_TRUE (r0
.undefined_p ());
3912 r0
.set_nonnegative (float_type_node
);
3913 ASSERT_TRUE (r0
.signbit_p (signbit
) && !signbit
);
3914 if (HONOR_NANS (float_type_node
))
3915 ASSERT_TRUE (r0
.maybe_isnan ());
3919 range_tests_signbit ()
3924 // Negative numbers should have the SIGNBIT set.
3925 r0
= frange_float ("-5", "-1");
3927 ASSERT_TRUE (r0
.signbit_p (signbit
) && signbit
);
3928 // Positive numbers should have the SIGNBIT clear.
3929 r0
= frange_float ("1", "10");
3931 ASSERT_TRUE (r0
.signbit_p (signbit
) && !signbit
);
3932 // Numbers containing zero should have an unknown SIGNBIT.
3933 r0
= frange_float ("0", "10");
3935 ASSERT_TRUE (r0
.signbit_p (signbit
) && !signbit
);
3936 // Numbers spanning both positive and negative should have an
3938 r0
= frange_float ("-10", "10");
3940 ASSERT_TRUE (!r0
.signbit_p (signbit
));
3941 r0
.set_varying (float_type_node
);
3942 ASSERT_TRUE (!r0
.signbit_p (signbit
));
3946 range_tests_floats ()
3950 if (HONOR_NANS (float_type_node
))
3952 range_tests_signbit ();
3954 if (HONOR_SIGNED_ZEROS (float_type_node
))
3955 range_tests_signed_zeros ();
3957 // A range of [-INF,+INF] is actually VARYING if no other properties
3959 r0
= frange_float ("-Inf", "+Inf");
3960 if (r0
.maybe_isnan ())
3961 ASSERT_TRUE (r0
.varying_p ());
3962 // ...unless it has some special property...
3964 ASSERT_FALSE (r0
.varying_p ());
3966 // For most architectures, where float and double are different
3967 // sizes, having the same endpoints does not necessarily mean the
3968 // ranges are equal.
3969 if (!types_compatible_p (float_type_node
, double_type_node
))
3971 r0
= frange_float ("3.0", "3.0", float_type_node
);
3972 r1
= frange_float ("3.0", "3.0", double_type_node
);
3976 // [3,5] U [10,12] = [3,12].
3977 r0
= frange_float ("3", "5");
3978 r1
= frange_float ("10", "12");
3980 ASSERT_EQ (r0
, frange_float ("3", "12"));
3982 // [5,10] U [4,8] = [4,10]
3983 r0
= frange_float ("5", "10");
3984 r1
= frange_float ("4", "8");
3986 ASSERT_EQ (r0
, frange_float ("4", "10"));
3988 // [3,5] U [4,10] = [3,10]
3989 r0
= frange_float ("3", "5");
3990 r1
= frange_float ("4", "10");
3992 ASSERT_EQ (r0
, frange_float ("3", "10"));
3994 // [4,10] U [5,11] = [4,11]
3995 r0
= frange_float ("4", "10");
3996 r1
= frange_float ("5", "11");
3998 ASSERT_EQ (r0
, frange_float ("4", "11"));
4000 // [3,12] ^ [10,12] = [10,12].
4001 r0
= frange_float ("3", "12");
4002 r1
= frange_float ("10", "12");
4004 ASSERT_EQ (r0
, frange_float ("10", "12"));
4006 // [10,12] ^ [11,11] = [11,11]
4007 r0
= frange_float ("10", "12");
4008 r1
= frange_float ("11", "11");
4010 ASSERT_EQ (r0
, frange_float ("11", "11"));
4012 // [10,20] ^ [5,15] = [10,15]
4013 r0
= frange_float ("10", "20");
4014 r1
= frange_float ("5", "15");
4016 ASSERT_EQ (r0
, frange_float ("10", "15"));
4018 // [10,20] ^ [15,25] = [15,20]
4019 r0
= frange_float ("10", "20");
4020 r1
= frange_float ("15", "25");
4022 ASSERT_EQ (r0
, frange_float ("15", "20"));
4024 // [10,20] ^ [21,25] = []
4025 r0
= frange_float ("10", "20");
4027 r1
= frange_float ("21", "25");
4030 ASSERT_TRUE (r0
.undefined_p ());
4032 if (!flag_finite_math_only
)
4034 // Make sure [-Inf, -Inf] doesn't get normalized.
4035 r0
= frange_float ("-Inf", "-Inf");
4036 ASSERT_TRUE (real_isinf (&r0
.lower_bound (), true));
4037 ASSERT_TRUE (real_isinf (&r0
.upper_bound (), true));
4044 range_tests_legacy ();
4045 range_tests_irange3 ();
4046 range_tests_int_range_max ();
4047 range_tests_strict_enum ();
4048 range_tests_nonzero_bits ();
4049 range_tests_floats ();
4050 range_tests_misc ();
4053 } // namespace selftest
4055 #endif // CHECKING_P