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 if (HONOR_NANS (type
))
309 bool sign
= real_isneg (&min
);
310 set_nan (type
, sign
);
321 if (HONOR_NANS (m_type
))
332 // For -ffinite-math-only we can drop ranges outside the
333 // representable numbers to min/max for the type.
334 if (flag_finite_math_only
)
336 REAL_VALUE_TYPE min_repr
= frange_val_min (m_type
);
337 REAL_VALUE_TYPE max_repr
= frange_val_max (m_type
);
338 if (real_less (&m_min
, &min_repr
))
340 if (real_less (&max_repr
, &m_max
))
344 // Check for swapped ranges.
345 gcc_checking_assert (real_compare (LE_EXPR
, &min
, &max
));
349 flush_denormals_to_zero ();
356 frange::set (tree min
, tree max
, value_range_kind kind
)
358 set (TREE_TYPE (min
),
359 *TREE_REAL_CST_PTR (min
), *TREE_REAL_CST_PTR (max
), kind
);
362 // Normalize range to VARYING or UNDEFINED, or vice versa. Return
363 // TRUE if anything changed.
365 // A range with no known properties can be dropped to VARYING.
366 // Similarly, a VARYING with any properties should be dropped to a
367 // VR_RANGE. Normalizing ranges upon changing them ensures there is
368 // only one representation for a given range.
371 frange::normalize_kind ()
373 if (m_kind
== VR_RANGE
374 && frange_val_is_min (m_min
, m_type
)
375 && frange_val_is_max (m_max
, m_type
))
377 if (m_pos_nan
&& m_neg_nan
)
379 set_varying (m_type
);
383 else if (m_kind
== VR_VARYING
)
385 if (!m_pos_nan
|| !m_neg_nan
)
388 m_min
= frange_val_min (m_type
);
389 m_max
= frange_val_max (m_type
);
393 else if (m_kind
== VR_NAN
&& !m_pos_nan
&& !m_neg_nan
)
398 // Union or intersect the zero endpoints of two ranges. For example:
399 // [-0, x] U [+0, x] => [-0, x]
400 // [ x, -0] U [ x, +0] => [ x, +0]
401 // [-0, x] ^ [+0, x] => [+0, x]
402 // [ x, -0] ^ [ x, +0] => [ x, -0]
404 // UNION_P is true when performing a union, or false when intersecting.
407 frange::combine_zeros (const frange
&r
, bool union_p
)
409 gcc_checking_assert (!undefined_p () && !known_isnan ());
411 bool changed
= false;
412 if (real_iszero (&m_min
) && real_iszero (&r
.m_min
)
413 && real_isneg (&m_min
) != real_isneg (&r
.m_min
))
415 m_min
.sign
= union_p
;
418 if (real_iszero (&m_max
) && real_iszero (&r
.m_max
)
419 && real_isneg (&m_max
) != real_isneg (&r
.m_max
))
421 m_max
.sign
= !union_p
;
424 // If the signs are swapped, the resulting range is empty.
425 if (m_min
.sign
== 0 && m_max
.sign
== 1)
436 // Union two ranges when one is known to be a NAN.
439 frange::union_nans (const frange
&r
)
441 gcc_checking_assert (known_isnan () || r
.known_isnan ());
449 m_pos_nan
|= r
.m_pos_nan
;
450 m_neg_nan
|= r
.m_neg_nan
;
458 frange::union_ (const vrange
&v
)
460 const frange
&r
= as_a
<frange
> (v
);
462 if (r
.undefined_p () || varying_p ())
464 if (undefined_p () || r
.varying_p ())
471 if (known_isnan () || r
.known_isnan ())
472 return union_nans (r
);
473 bool changed
= false;
474 if (m_pos_nan
!= r
.m_pos_nan
|| m_neg_nan
!= r
.m_neg_nan
)
476 m_pos_nan
|= r
.m_pos_nan
;
477 m_neg_nan
|= r
.m_neg_nan
;
481 // Combine endpoints.
482 if (real_less (&r
.m_min
, &m_min
))
487 if (real_less (&m_max
, &r
.m_max
))
493 if (HONOR_SIGNED_ZEROS (m_type
))
494 changed
|= combine_zeros (r
, true);
496 changed
|= normalize_kind ();
502 // Intersect two ranges when one is known to be a NAN.
505 frange::intersect_nans (const frange
&r
)
507 gcc_checking_assert (known_isnan () || r
.known_isnan ());
509 m_pos_nan
&= r
.m_pos_nan
;
510 m_neg_nan
&= r
.m_neg_nan
;
521 frange::intersect (const vrange
&v
)
523 const frange
&r
= as_a
<frange
> (v
);
525 if (undefined_p () || r
.varying_p ())
527 if (r
.undefined_p ())
539 if (known_isnan () || r
.known_isnan ())
540 return intersect_nans (r
);
541 bool changed
= false;
542 if (m_pos_nan
!= r
.m_pos_nan
|| m_neg_nan
!= r
.m_neg_nan
)
544 m_pos_nan
&= r
.m_pos_nan
;
545 m_neg_nan
&= r
.m_neg_nan
;
549 // Combine endpoints.
550 if (real_less (&m_min
, &r
.m_min
))
555 if (real_less (&r
.m_max
, &m_max
))
560 // If the endpoints are swapped, the resulting range is empty.
561 if (real_less (&m_max
, &m_min
))
572 if (HONOR_SIGNED_ZEROS (m_type
))
573 changed
|= combine_zeros (r
, false);
575 changed
|= normalize_kind ();
582 frange::operator= (const frange
&src
)
588 m_pos_nan
= src
.m_pos_nan
;
589 m_neg_nan
= src
.m_neg_nan
;
597 frange::operator== (const frange
&src
) const
599 if (m_kind
== src
.m_kind
)
605 return types_compatible_p (m_type
, src
.m_type
);
607 if (known_isnan () || src
.known_isnan ())
610 return (real_identical (&m_min
, &src
.m_min
)
611 && real_identical (&m_max
, &src
.m_max
)
612 && m_pos_nan
== src
.m_pos_nan
613 && m_neg_nan
== src
.m_neg_nan
614 && types_compatible_p (m_type
, src
.m_type
));
619 // Return TRUE if range contains the TREE_REAL_CST_PTR in CST.
622 frange::contains_p (tree cst
) const
624 gcc_checking_assert (m_kind
!= VR_ANTI_RANGE
);
625 const REAL_VALUE_TYPE
*rv
= TREE_REAL_CST_PTR (cst
);
636 if (!m_pos_nan
&& !m_neg_nan
)
638 // Both +NAN and -NAN are present.
639 if (m_pos_nan
&& m_neg_nan
)
641 return m_neg_nan
== rv
->sign
;
646 if (real_compare (GE_EXPR
, rv
, &m_min
) && real_compare (LE_EXPR
, rv
, &m_max
))
648 // Make sure the signs are equal for signed zeros.
649 if (HONOR_SIGNED_ZEROS (m_type
) && real_iszero (rv
))
650 return m_min
.sign
== m_max
.sign
&& m_min
.sign
== rv
->sign
;
656 // If range is a singleton, place it in RESULT and return TRUE. If
657 // RESULT is NULL, just return TRUE.
659 // A NAN can never be a singleton.
662 frange::singleton_p (tree
*result
) const
664 if (m_kind
== VR_RANGE
&& real_identical (&m_min
, &m_max
))
666 // Return false for any singleton that may be a NAN.
667 if (HONOR_NANS (m_type
) && maybe_isnan ())
670 if (MODE_COMPOSITE_P (TYPE_MODE (m_type
)))
672 // For IBM long doubles, if the value is +-Inf or is exactly
673 // representable in double, the other double could be +0.0
674 // or -0.0. Since this means there is more than one way to
675 // represent a value, return false to avoid propagating it.
676 // See libgcc/config/rs6000/ibm-ldouble-format for details.
677 if (real_isinf (&m_min
))
680 real_convert (&r
, DFmode
, &m_min
);
681 if (real_identical (&r
, &m_min
))
686 *result
= build_real (m_type
, m_min
);
693 frange::supports_type_p (const_tree type
) const
695 return supports_p (type
);
699 frange::verify_range ()
704 gcc_checking_assert (!m_type
);
707 gcc_checking_assert (m_type
);
708 gcc_checking_assert (m_pos_nan
&& m_neg_nan
);
709 gcc_checking_assert (frange_val_is_min (m_min
, m_type
));
710 gcc_checking_assert (frange_val_is_max (m_max
, m_type
));
713 gcc_checking_assert (m_type
);
716 gcc_checking_assert (m_type
);
717 gcc_checking_assert (m_pos_nan
|| m_neg_nan
);
723 // NANs cannot appear in the endpoints of a range.
724 gcc_checking_assert (!real_isnan (&m_min
) && !real_isnan (&m_max
));
726 // Make sure we don't have swapped ranges.
727 gcc_checking_assert (!real_less (&m_max
, &m_min
));
729 // [ +0.0, -0.0 ] is nonsensical.
730 gcc_checking_assert (!(real_iszero (&m_min
, 0) && real_iszero (&m_max
, 1)));
732 // If all the properties are clear, we better not span the entire
733 // domain, because that would make us varying.
734 if (m_pos_nan
&& m_neg_nan
)
735 gcc_checking_assert (!frange_val_is_min (m_min
, m_type
)
736 || !frange_val_is_max (m_max
, m_type
));
739 // We can't do much with nonzeros yet.
741 frange::set_nonzero (tree type
)
746 // We can't do much with nonzeros yet.
748 frange::nonzero_p () const
753 // Set range to [+0.0, +0.0] if honoring signed zeros, or [0.0, 0.0]
757 frange::set_zero (tree type
)
759 if (HONOR_SIGNED_ZEROS (type
))
761 REAL_VALUE_TYPE dconstm0
= dconst0
;
763 set (type
, dconstm0
, dconst0
);
767 set (type
, dconst0
, dconst0
);
770 // Return TRUE for any zero regardless of sign.
773 frange::zero_p () const
775 return (m_kind
== VR_RANGE
776 && real_iszero (&m_min
)
777 && real_iszero (&m_max
));
781 frange::set_nonnegative (tree type
)
783 set (type
, dconst0
, frange_val_max (type
));
785 // Set +NAN as the only possibility.
786 if (HONOR_NANS (type
))
787 update_nan (/*sign=*/0);
790 // Here we copy between any two irange's. The ranges can be legacy or
791 // multi-ranges, and copying between any combination works correctly.
794 irange::operator= (const irange
&src
)
796 if (legacy_mode_p ())
798 copy_to_legacy (src
);
801 if (src
.legacy_mode_p ())
803 copy_legacy_to_multi_range (src
);
808 unsigned lim
= src
.m_num_ranges
;
809 if (lim
> m_max_ranges
)
812 for (x
= 0; x
< lim
* 2; ++x
)
813 m_base
[x
] = src
.m_base
[x
];
815 // If the range didn't fit, the last range should cover the rest.
816 if (lim
!= src
.m_num_ranges
)
817 m_base
[x
- 1] = src
.m_base
[src
.m_num_ranges
* 2 - 1];
821 m_nonzero_mask
= src
.m_nonzero_mask
;
827 // Return TRUE if range is a multi-range that can be represented as a
831 irange::maybe_anti_range () const
833 tree ttype
= type ();
834 unsigned int precision
= TYPE_PRECISION (ttype
);
835 signop sign
= TYPE_SIGN (ttype
);
836 return (num_pairs () > 1
838 && lower_bound () == wi::min_value (precision
, sign
)
839 && upper_bound () == wi::max_value (precision
, sign
));
843 irange::copy_legacy_to_multi_range (const irange
&src
)
845 gcc_checking_assert (src
.legacy_mode_p ());
846 gcc_checking_assert (!legacy_mode_p ());
847 if (src
.undefined_p ())
849 else if (src
.varying_p ())
850 set_varying (src
.type ());
853 if (range_has_numeric_bounds_p (&src
))
854 set (src
.min (), src
.max (), src
.kind ());
857 value_range
cst (src
);
858 cst
.normalize_symbolics ();
859 gcc_checking_assert (cst
.varying_p () || cst
.kind () == VR_RANGE
);
860 set (cst
.min (), cst
.max ());
865 // Copy any type of irange into a legacy.
868 irange::copy_to_legacy (const irange
&src
)
870 gcc_checking_assert (legacy_mode_p ());
871 // Handle legacy to legacy and other things that are easy to copy.
872 if (src
.legacy_mode_p () || src
.varying_p () || src
.undefined_p ())
874 m_num_ranges
= src
.m_num_ranges
;
875 m_base
[0] = src
.m_base
[0];
876 m_base
[1] = src
.m_base
[1];
878 m_nonzero_mask
= src
.m_nonzero_mask
;
881 // Copy multi-range to legacy.
882 if (src
.maybe_anti_range ())
884 int_range
<3> r (src
);
886 // Use tree variants to save on tree -> wi -> tree conversions.
887 set (r
.tree_lower_bound (0), r
.tree_upper_bound (0), VR_ANTI_RANGE
);
890 set (src
.tree_lower_bound (), src
.tree_upper_bound ());
893 // Swap MIN/MAX if they are out of order and adjust KIND appropriately.
896 swap_out_of_order_endpoints (tree
&min
, tree
&max
, value_range_kind
&kind
)
898 gcc_checking_assert (kind
!= VR_UNDEFINED
);
899 if (kind
== VR_VARYING
)
901 /* Wrong order for min and max, to swap them and the VR type we need
903 if (tree_int_cst_lt (max
, min
))
907 /* For one bit precision if max < min, then the swapped
908 range covers all values, so for VR_RANGE it is varying and
909 for VR_ANTI_RANGE empty range, so drop to varying as well. */
910 if (TYPE_PRECISION (TREE_TYPE (min
)) == 1)
916 one
= build_int_cst (TREE_TYPE (min
), 1);
917 tmp
= int_const_binop (PLUS_EXPR
, max
, one
);
918 max
= int_const_binop (MINUS_EXPR
, min
, one
);
921 /* There's one corner case, if we had [C+1, C] before we now have
922 that again. But this represents an empty value range, so drop
923 to varying in this case. */
924 if (tree_int_cst_lt (max
, min
))
929 kind
= kind
== VR_RANGE
? VR_ANTI_RANGE
: VR_RANGE
;
934 irange::irange_set (tree min
, tree max
)
936 gcc_checking_assert (!POLY_INT_CST_P (min
));
937 gcc_checking_assert (!POLY_INT_CST_P (max
));
943 m_nonzero_mask
= NULL
;
951 irange::irange_set_1bit_anti_range (tree min
, tree max
)
953 tree type
= TREE_TYPE (min
);
954 gcc_checking_assert (TYPE_PRECISION (type
) == 1);
956 if (operand_equal_p (min
, max
))
958 // Since these are 1-bit quantities, they can only be [MIN,MIN]
960 if (vrp_val_is_min (min
))
961 min
= max
= vrp_val_max (type
);
963 min
= max
= vrp_val_min (type
);
968 // The only alternative is [MIN,MAX], which is the empty range.
969 gcc_checking_assert (vrp_val_is_min (min
));
970 gcc_checking_assert (vrp_val_is_max (max
));
978 irange::irange_set_anti_range (tree min
, tree max
)
980 gcc_checking_assert (!POLY_INT_CST_P (min
));
981 gcc_checking_assert (!POLY_INT_CST_P (max
));
983 if (TYPE_PRECISION (TREE_TYPE (min
)) == 1)
985 irange_set_1bit_anti_range (min
, max
);
990 tree type
= TREE_TYPE (min
);
991 signop sign
= TYPE_SIGN (type
);
992 int_range
<2> type_range (type
);
993 // Calculate INVERSE([I,J]) as [-MIN, I-1][J+1, +MAX].
995 wi::overflow_type ovf
;
997 wide_int w_min
= wi::to_wide (min
);
998 if (wi::ne_p (w_min
, type_range
.lower_bound ()))
1000 wide_int lim1
= wi::sub (w_min
, 1, sign
, &ovf
);
1001 gcc_checking_assert (ovf
!= wi::OVF_OVERFLOW
);
1002 m_base
[0] = type_range
.tree_lower_bound (0);
1003 m_base
[1] = wide_int_to_tree (type
, lim1
);
1006 wide_int w_max
= wi::to_wide (max
);
1007 if (wi::ne_p (w_max
, type_range
.upper_bound ()))
1009 wide_int lim2
= wi::add (w_max
, 1, sign
, &ovf
);
1010 gcc_checking_assert (ovf
!= wi::OVF_OVERFLOW
);
1011 m_base
[m_num_ranges
* 2] = wide_int_to_tree (type
, lim2
);
1012 m_base
[m_num_ranges
* 2 + 1] = type_range
.tree_upper_bound (0);
1017 m_nonzero_mask
= NULL
;
1024 /* Set value range to the canonical form of {VRTYPE, MIN, MAX, EQUIV}.
1025 This means adjusting VRTYPE, MIN and MAX representing the case of a
1026 wrapping range with MAX < MIN covering [MIN, type_max] U [type_min, MAX]
1027 as anti-rage ~[MAX+1, MIN-1]. Likewise for wrapping anti-ranges.
1028 In corner cases where MAX+1 or MIN-1 wraps this will fall back
1030 This routine exists to ease canonicalization in the case where we
1031 extract ranges from var + CST op limit. */
1034 irange::set (tree min
, tree max
, value_range_kind kind
)
1036 if (kind
== VR_UNDEFINED
)
1038 irange::set_undefined ();
1042 if (kind
== VR_VARYING
1043 || POLY_INT_CST_P (min
)
1044 || POLY_INT_CST_P (max
))
1046 set_varying (TREE_TYPE (min
));
1050 if (TREE_OVERFLOW_P (min
))
1051 min
= drop_tree_overflow (min
);
1052 if (TREE_OVERFLOW_P (max
))
1053 max
= drop_tree_overflow (max
);
1055 if (!legacy_mode_p ())
1057 if (kind
== VR_RANGE
)
1058 irange_set (min
, max
);
1061 gcc_checking_assert (kind
== VR_ANTI_RANGE
);
1062 irange_set_anti_range (min
, max
);
1066 // Nothing to canonicalize for symbolic ranges.
1067 if (TREE_CODE (min
) != INTEGER_CST
1068 || TREE_CODE (max
) != INTEGER_CST
)
1074 m_nonzero_mask
= NULL
;
1078 swap_out_of_order_endpoints (min
, max
, kind
);
1079 if (kind
== VR_VARYING
)
1081 set_varying (TREE_TYPE (min
));
1085 // Anti-ranges that can be represented as ranges should be so.
1086 if (kind
== VR_ANTI_RANGE
)
1088 bool is_min
= vrp_val_is_min (min
);
1089 bool is_max
= vrp_val_is_max (max
);
1091 if (is_min
&& is_max
)
1093 // Fall through. This will either be normalized as
1094 // VR_UNDEFINED if the anti-range spans the entire
1095 // precision, or it will remain an VR_ANTI_RANGE in the case
1096 // of an -fstrict-enum where [MIN,MAX] is less than the span
1097 // of underlying precision.
1099 else if (TYPE_PRECISION (TREE_TYPE (min
)) == 1)
1101 irange_set_1bit_anti_range (min
, max
);
1106 tree one
= build_int_cst (TREE_TYPE (max
), 1);
1107 min
= int_const_binop (PLUS_EXPR
, max
, one
);
1108 max
= vrp_val_max (TREE_TYPE (max
));
1113 tree one
= build_int_cst (TREE_TYPE (min
), 1);
1114 max
= int_const_binop (MINUS_EXPR
, min
, one
);
1115 min
= vrp_val_min (TREE_TYPE (min
));
1124 m_nonzero_mask
= NULL
;
1130 // Check the validity of the range.
1133 irange::verify_range ()
1135 gcc_checking_assert (m_discriminator
== VR_IRANGE
);
1136 if (m_kind
== VR_UNDEFINED
)
1138 gcc_checking_assert (m_num_ranges
== 0);
1139 gcc_checking_assert (!m_nonzero_mask
);
1143 gcc_checking_assert (wi::to_wide (m_nonzero_mask
) != -1);
1144 if (m_kind
== VR_VARYING
)
1146 gcc_checking_assert (!m_nonzero_mask
);
1147 gcc_checking_assert (m_num_ranges
== 1);
1148 gcc_checking_assert (varying_compatible_p ());
1151 if (!legacy_mode_p ())
1153 gcc_checking_assert (m_num_ranges
!= 0);
1154 gcc_checking_assert (!varying_compatible_p ());
1155 for (unsigned i
= 0; i
< m_num_ranges
; ++i
)
1157 tree lb
= tree_lower_bound (i
);
1158 tree ub
= tree_upper_bound (i
);
1159 int c
= compare_values (lb
, ub
);
1160 gcc_checking_assert (c
== 0 || c
== -1);
1164 if (m_kind
== VR_RANGE
|| m_kind
== VR_ANTI_RANGE
)
1166 gcc_checking_assert (m_num_ranges
== 1);
1167 int cmp
= compare_values (tree_lower_bound (0), tree_upper_bound (0));
1168 gcc_checking_assert (cmp
== 0 || cmp
== -1 || cmp
== -2);
1172 // Return the lower bound for a sub-range. PAIR is the sub-range in
1176 irange::legacy_lower_bound (unsigned pair
) const
1178 gcc_checking_assert (legacy_mode_p ());
1181 value_range
numeric_range (*this);
1182 numeric_range
.normalize_symbolics ();
1183 return numeric_range
.legacy_lower_bound (pair
);
1185 gcc_checking_assert (m_num_ranges
> 0);
1186 gcc_checking_assert (pair
+ 1 <= num_pairs ());
1187 if (m_kind
== VR_ANTI_RANGE
)
1189 tree typ
= type (), t
;
1190 if (pair
== 1 || vrp_val_is_min (min ()))
1191 t
= wide_int_to_tree (typ
, wi::to_wide (max ()) + 1);
1193 t
= vrp_val_min (typ
);
1194 return wi::to_wide (t
);
1196 return wi::to_wide (tree_lower_bound (pair
));
1199 // Return the upper bound for a sub-range. PAIR is the sub-range in
1203 irange::legacy_upper_bound (unsigned pair
) const
1205 gcc_checking_assert (legacy_mode_p ());
1208 value_range
numeric_range (*this);
1209 numeric_range
.normalize_symbolics ();
1210 return numeric_range
.legacy_upper_bound (pair
);
1212 gcc_checking_assert (m_num_ranges
> 0);
1213 gcc_checking_assert (pair
+ 1 <= num_pairs ());
1214 if (m_kind
== VR_ANTI_RANGE
)
1216 tree typ
= type (), t
;
1217 if (pair
== 1 || vrp_val_is_min (min ()))
1218 t
= vrp_val_max (typ
);
1220 t
= wide_int_to_tree (typ
, wi::to_wide (min ()) - 1);
1221 return wi::to_wide (t
);
1223 return wi::to_wide (tree_upper_bound (pair
));
1227 irange::legacy_equal_p (const irange
&other
) const
1229 gcc_checking_assert (legacy_mode_p () && other
.legacy_mode_p ());
1231 if (m_kind
!= other
.m_kind
)
1233 if (m_kind
== VR_UNDEFINED
)
1235 if (m_kind
== VR_VARYING
)
1237 return (range_compatible_p (type (), other
.type ())
1238 && vrp_operand_equal_p (m_nonzero_mask
, other
.m_nonzero_mask
));
1240 return (vrp_operand_equal_p (tree_lower_bound (0),
1241 other
.tree_lower_bound (0))
1242 && vrp_operand_equal_p (tree_upper_bound (0),
1243 other
.tree_upper_bound (0))
1244 && vrp_operand_equal_p (m_nonzero_mask
, other
.m_nonzero_mask
));
1248 irange::operator== (const irange
&other
) const
1250 if (legacy_mode_p ())
1252 if (other
.legacy_mode_p ())
1253 return legacy_equal_p (other
);
1254 value_range
tmp (other
);
1255 return legacy_equal_p (tmp
);
1257 if (other
.legacy_mode_p ())
1259 value_range
tmp2 (*this);
1260 return tmp2
.legacy_equal_p (other
);
1263 if (m_num_ranges
!= other
.m_num_ranges
)
1266 for (unsigned i
= 0; i
< m_num_ranges
; ++i
)
1268 tree lb
= tree_lower_bound (i
);
1269 tree ub
= tree_upper_bound (i
);
1270 tree lb_other
= other
.tree_lower_bound (i
);
1271 tree ub_other
= other
.tree_upper_bound (i
);
1272 if (!operand_equal_p (lb
, lb_other
, 0)
1273 || !operand_equal_p (ub
, ub_other
, 0))
1276 return vrp_operand_equal_p (m_nonzero_mask
, other
.m_nonzero_mask
);
1279 /* Return TRUE if this is a symbolic range. */
1282 irange::symbolic_p () const
1284 return (m_num_ranges
> 0
1285 && (!is_gimple_min_invariant (min ())
1286 || !is_gimple_min_invariant (max ())));
1289 /* Return TRUE if this is a constant range. */
1292 irange::constant_p () const
1294 return (m_num_ranges
> 0
1295 && TREE_CODE (min ()) == INTEGER_CST
1296 && TREE_CODE (max ()) == INTEGER_CST
);
1299 /* If range is a singleton, place it in RESULT and return TRUE.
1300 Note: A singleton can be any gimple invariant, not just constants.
1301 So, [&x, &x] counts as a singleton. */
1304 irange::singleton_p (tree
*result
) const
1306 if (!legacy_mode_p ())
1308 if (num_pairs () == 1 && (wi::to_wide (tree_lower_bound ())
1309 == wi::to_wide (tree_upper_bound ())))
1312 *result
= tree_lower_bound ();
1317 if (m_kind
== VR_ANTI_RANGE
)
1321 if (TYPE_PRECISION (type ()) == 1)
1329 if (num_pairs () == 1)
1331 value_range vr0
, vr1
;
1332 ranges_from_anti_range ((const value_range
*) this, &vr0
, &vr1
);
1333 return vr0
.singleton_p (result
);
1336 // Catches non-numeric extremes as well.
1337 if (m_kind
== VR_RANGE
1338 && vrp_operand_equal_p (min (), max ())
1339 && is_gimple_min_invariant (min ()))
1348 /* Return 1 if VAL is inside value range.
1349 0 if VAL is not inside value range.
1350 -2 if we cannot tell either way.
1352 Benchmark compile/20001226-1.c compilation time after changing this
1356 irange::value_inside_range (tree val
) const
1364 if (!legacy_mode_p () && TREE_CODE (val
) == INTEGER_CST
)
1365 return contains_p (val
);
1367 int cmp1
= operand_less_p (val
, min ());
1371 return m_kind
!= VR_RANGE
;
1373 int cmp2
= operand_less_p (max (), val
);
1377 if (m_kind
== VR_RANGE
)
1383 /* Return TRUE if it is possible that range contains VAL. */
1386 irange::may_contain_p (tree val
) const
1388 return value_inside_range (val
) != 0;
1391 /* Return TRUE if range contains INTEGER_CST. */
1392 /* Return 1 if VAL is inside value range.
1393 0 if VAL is not inside value range.
1395 Benchmark compile/20001226-1.c compilation time after changing this
1400 irange::contains_p (tree cst
) const
1405 if (legacy_mode_p ())
1407 gcc_checking_assert (TREE_CODE (cst
) == INTEGER_CST
);
1410 value_range
numeric_range (*this);
1411 numeric_range
.normalize_symbolics ();
1412 return numeric_range
.contains_p (cst
);
1414 return value_inside_range (cst
) == 1;
1417 gcc_checking_assert (TREE_CODE (cst
) == INTEGER_CST
);
1421 wide_int cstw
= wi::to_wide (cst
);
1422 if (cstw
!= 0 && wi::bit_and (wi::to_wide (m_nonzero_mask
), cstw
) == 0)
1426 signop sign
= TYPE_SIGN (TREE_TYPE (cst
));
1427 wide_int v
= wi::to_wide (cst
);
1428 for (unsigned r
= 0; r
< m_num_ranges
; ++r
)
1430 if (wi::lt_p (v
, lower_bound (r
), sign
))
1432 if (wi::le_p (v
, upper_bound (r
), sign
))
1440 /* Normalize addresses into constants. */
1443 irange::normalize_addresses ()
1448 if (!POINTER_TYPE_P (type ()) || range_has_numeric_bounds_p (this))
1451 if (!range_includes_zero_p (this))
1453 gcc_checking_assert (TREE_CODE (min ()) == ADDR_EXPR
1454 || TREE_CODE (max ()) == ADDR_EXPR
);
1455 set_nonzero (type ());
1458 set_varying (type ());
1461 /* Normalize symbolics and addresses into constants. */
1464 irange::normalize_symbolics ()
1466 if (varying_p () || undefined_p ())
1469 tree ttype
= type ();
1470 bool min_symbolic
= !is_gimple_min_invariant (min ());
1471 bool max_symbolic
= !is_gimple_min_invariant (max ());
1472 if (!min_symbolic
&& !max_symbolic
)
1474 normalize_addresses ();
1478 // [SYM, SYM] -> VARYING
1479 if (min_symbolic
&& max_symbolic
)
1481 set_varying (ttype
);
1484 if (kind () == VR_RANGE
)
1486 // [SYM, NUM] -> [-MIN, NUM]
1489 set (vrp_val_min (ttype
), max ());
1492 // [NUM, SYM] -> [NUM, +MAX]
1493 set (min (), vrp_val_max (ttype
));
1496 gcc_checking_assert (kind () == VR_ANTI_RANGE
);
1497 // ~[SYM, NUM] -> [NUM + 1, +MAX]
1500 if (!vrp_val_is_max (max ()))
1502 tree n
= wide_int_to_tree (ttype
, wi::to_wide (max ()) + 1);
1503 set (n
, vrp_val_max (ttype
));
1506 set_varying (ttype
);
1509 // ~[NUM, SYM] -> [-MIN, NUM - 1]
1510 if (!vrp_val_is_min (min ()))
1512 tree n
= wide_int_to_tree (ttype
, wi::to_wide (min ()) - 1);
1513 set (vrp_val_min (ttype
), n
);
1516 set_varying (ttype
);
1519 /* Intersect the two value-ranges { *VR0TYPE, *VR0MIN, *VR0MAX } and
1520 { VR1TYPE, VR0MIN, VR0MAX } and store the result
1521 in { *VR0TYPE, *VR0MIN, *VR0MAX }. This may not be the smallest
1522 possible such range. The resulting range is not canonicalized. */
1525 intersect_ranges (enum value_range_kind
*vr0type
,
1526 tree
*vr0min
, tree
*vr0max
,
1527 enum value_range_kind vr1type
,
1528 tree vr1min
, tree vr1max
)
1530 bool mineq
= vrp_operand_equal_p (*vr0min
, vr1min
);
1531 bool maxeq
= vrp_operand_equal_p (*vr0max
, vr1max
);
1533 /* [] is vr0, () is vr1 in the following classification comments. */
1537 if (*vr0type
== vr1type
)
1538 /* Nothing to do for equal ranges. */
1540 else if ((*vr0type
== VR_RANGE
1541 && vr1type
== VR_ANTI_RANGE
)
1542 || (*vr0type
== VR_ANTI_RANGE
1543 && vr1type
== VR_RANGE
))
1545 /* For anti-range with range intersection the result is empty. */
1546 *vr0type
= VR_UNDEFINED
;
1547 *vr0min
= NULL_TREE
;
1548 *vr0max
= NULL_TREE
;
1553 else if (operand_less_p (*vr0max
, vr1min
) == 1
1554 || operand_less_p (vr1max
, *vr0min
) == 1)
1556 /* [ ] ( ) or ( ) [ ]
1557 If the ranges have an empty intersection, the result of the
1558 intersect operation is the range for intersecting an
1559 anti-range with a range or empty when intersecting two ranges. */
1560 if (*vr0type
== VR_RANGE
1561 && vr1type
== VR_ANTI_RANGE
)
1563 else if (*vr0type
== VR_ANTI_RANGE
1564 && vr1type
== VR_RANGE
)
1570 else if (*vr0type
== VR_RANGE
1571 && vr1type
== VR_RANGE
)
1573 *vr0type
= VR_UNDEFINED
;
1574 *vr0min
= NULL_TREE
;
1575 *vr0max
= NULL_TREE
;
1577 else if (*vr0type
== VR_ANTI_RANGE
1578 && vr1type
== VR_ANTI_RANGE
)
1580 /* If the anti-ranges are adjacent to each other merge them. */
1581 if (TREE_CODE (*vr0max
) == INTEGER_CST
1582 && TREE_CODE (vr1min
) == INTEGER_CST
1583 && operand_less_p (*vr0max
, vr1min
) == 1
1584 && integer_onep (int_const_binop (MINUS_EXPR
,
1587 else if (TREE_CODE (vr1max
) == INTEGER_CST
1588 && TREE_CODE (*vr0min
) == INTEGER_CST
1589 && operand_less_p (vr1max
, *vr0min
) == 1
1590 && integer_onep (int_const_binop (MINUS_EXPR
,
1593 /* Else arbitrarily take VR0. */
1596 else if ((maxeq
|| operand_less_p (vr1max
, *vr0max
) == 1)
1597 && (mineq
|| operand_less_p (*vr0min
, vr1min
) == 1))
1599 /* [ ( ) ] or [( ) ] or [ ( )] */
1600 if (*vr0type
== VR_RANGE
1601 && vr1type
== VR_RANGE
)
1603 /* If both are ranges the result is the inner one. */
1608 else if (*vr0type
== VR_RANGE
1609 && vr1type
== VR_ANTI_RANGE
)
1611 /* Choose the right gap if the left one is empty. */
1614 if (TREE_CODE (vr1max
) != INTEGER_CST
)
1616 else if (TYPE_PRECISION (TREE_TYPE (vr1max
)) == 1
1617 && !TYPE_UNSIGNED (TREE_TYPE (vr1max
)))
1619 = int_const_binop (MINUS_EXPR
, vr1max
,
1620 build_int_cst (TREE_TYPE (vr1max
), -1));
1623 = int_const_binop (PLUS_EXPR
, vr1max
,
1624 build_int_cst (TREE_TYPE (vr1max
), 1));
1626 /* Choose the left gap if the right one is empty. */
1629 if (TREE_CODE (vr1min
) != INTEGER_CST
)
1631 else if (TYPE_PRECISION (TREE_TYPE (vr1min
)) == 1
1632 && !TYPE_UNSIGNED (TREE_TYPE (vr1min
)))
1634 = int_const_binop (PLUS_EXPR
, vr1min
,
1635 build_int_cst (TREE_TYPE (vr1min
), -1));
1638 = int_const_binop (MINUS_EXPR
, vr1min
,
1639 build_int_cst (TREE_TYPE (vr1min
), 1));
1641 /* Choose the anti-range if the range is effectively varying. */
1642 else if (vrp_val_is_min (*vr0min
)
1643 && vrp_val_is_max (*vr0max
))
1649 /* Else choose the range. */
1651 else if (*vr0type
== VR_ANTI_RANGE
1652 && vr1type
== VR_ANTI_RANGE
)
1653 /* If both are anti-ranges the result is the outer one. */
1655 else if (*vr0type
== VR_ANTI_RANGE
1656 && vr1type
== VR_RANGE
)
1658 /* The intersection is empty. */
1659 *vr0type
= VR_UNDEFINED
;
1660 *vr0min
= NULL_TREE
;
1661 *vr0max
= NULL_TREE
;
1666 else if ((maxeq
|| operand_less_p (*vr0max
, vr1max
) == 1)
1667 && (mineq
|| operand_less_p (vr1min
, *vr0min
) == 1))
1669 /* ( [ ] ) or ([ ] ) or ( [ ]) */
1670 if (*vr0type
== VR_RANGE
1671 && vr1type
== VR_RANGE
)
1672 /* Choose the inner range. */
1674 else if (*vr0type
== VR_ANTI_RANGE
1675 && vr1type
== VR_RANGE
)
1677 /* Choose the right gap if the left is empty. */
1680 *vr0type
= VR_RANGE
;
1681 if (TREE_CODE (*vr0max
) != INTEGER_CST
)
1683 else if (TYPE_PRECISION (TREE_TYPE (*vr0max
)) == 1
1684 && !TYPE_UNSIGNED (TREE_TYPE (*vr0max
)))
1686 = int_const_binop (MINUS_EXPR
, *vr0max
,
1687 build_int_cst (TREE_TYPE (*vr0max
), -1));
1690 = int_const_binop (PLUS_EXPR
, *vr0max
,
1691 build_int_cst (TREE_TYPE (*vr0max
), 1));
1694 /* Choose the left gap if the right is empty. */
1697 *vr0type
= VR_RANGE
;
1698 if (TREE_CODE (*vr0min
) != INTEGER_CST
)
1700 else if (TYPE_PRECISION (TREE_TYPE (*vr0min
)) == 1
1701 && !TYPE_UNSIGNED (TREE_TYPE (*vr0min
)))
1703 = int_const_binop (PLUS_EXPR
, *vr0min
,
1704 build_int_cst (TREE_TYPE (*vr0min
), -1));
1707 = int_const_binop (MINUS_EXPR
, *vr0min
,
1708 build_int_cst (TREE_TYPE (*vr0min
), 1));
1711 /* Choose the anti-range if the range is effectively varying. */
1712 else if (vrp_val_is_min (vr1min
)
1713 && vrp_val_is_max (vr1max
))
1715 /* Choose the anti-range if it is ~[0,0], that range is special
1716 enough to special case when vr1's range is relatively wide.
1717 At least for types bigger than int - this covers pointers
1718 and arguments to functions like ctz. */
1719 else if (*vr0min
== *vr0max
1720 && integer_zerop (*vr0min
)
1721 && ((TYPE_PRECISION (TREE_TYPE (*vr0min
))
1722 >= TYPE_PRECISION (integer_type_node
))
1723 || POINTER_TYPE_P (TREE_TYPE (*vr0min
)))
1724 && TREE_CODE (vr1max
) == INTEGER_CST
1725 && TREE_CODE (vr1min
) == INTEGER_CST
1726 && (wi::clz (wi::to_wide (vr1max
) - wi::to_wide (vr1min
))
1727 < TYPE_PRECISION (TREE_TYPE (*vr0min
)) / 2))
1729 /* Else choose the range. */
1737 else if (*vr0type
== VR_ANTI_RANGE
1738 && vr1type
== VR_ANTI_RANGE
)
1740 /* If both are anti-ranges the result is the outer one. */
1745 else if (vr1type
== VR_ANTI_RANGE
1746 && *vr0type
== VR_RANGE
)
1748 /* The intersection is empty. */
1749 *vr0type
= VR_UNDEFINED
;
1750 *vr0min
= NULL_TREE
;
1751 *vr0max
= NULL_TREE
;
1756 else if ((operand_less_p (vr1min
, *vr0max
) == 1
1757 || operand_equal_p (vr1min
, *vr0max
, 0))
1758 && operand_less_p (*vr0min
, vr1min
) == 1
1759 && operand_less_p (*vr0max
, vr1max
) == 1)
1761 /* [ ( ] ) or [ ]( ) */
1762 if (*vr0type
== VR_ANTI_RANGE
1763 && vr1type
== VR_ANTI_RANGE
)
1765 else if (*vr0type
== VR_RANGE
1766 && vr1type
== VR_RANGE
)
1768 else if (*vr0type
== VR_RANGE
1769 && vr1type
== VR_ANTI_RANGE
)
1771 if (TREE_CODE (vr1min
) == INTEGER_CST
)
1772 *vr0max
= int_const_binop (MINUS_EXPR
, vr1min
,
1773 build_int_cst (TREE_TYPE (vr1min
), 1));
1777 else if (*vr0type
== VR_ANTI_RANGE
1778 && vr1type
== VR_RANGE
)
1780 *vr0type
= VR_RANGE
;
1781 if (TREE_CODE (*vr0max
) == INTEGER_CST
)
1782 *vr0min
= int_const_binop (PLUS_EXPR
, *vr0max
,
1783 build_int_cst (TREE_TYPE (*vr0max
), 1));
1791 else if ((operand_less_p (*vr0min
, vr1max
) == 1
1792 || operand_equal_p (*vr0min
, vr1max
, 0))
1793 && operand_less_p (vr1min
, *vr0min
) == 1
1794 && operand_less_p (vr1max
, *vr0max
) == 1)
1796 /* ( [ ) ] or ( )[ ] */
1797 if (*vr0type
== VR_ANTI_RANGE
1798 && vr1type
== VR_ANTI_RANGE
)
1800 else if (*vr0type
== VR_RANGE
1801 && vr1type
== VR_RANGE
)
1803 else if (*vr0type
== VR_RANGE
1804 && vr1type
== VR_ANTI_RANGE
)
1806 if (TREE_CODE (vr1max
) == INTEGER_CST
)
1807 *vr0min
= int_const_binop (PLUS_EXPR
, vr1max
,
1808 build_int_cst (TREE_TYPE (vr1max
), 1));
1812 else if (*vr0type
== VR_ANTI_RANGE
1813 && vr1type
== VR_RANGE
)
1815 *vr0type
= VR_RANGE
;
1816 if (TREE_CODE (*vr0min
) == INTEGER_CST
)
1817 *vr0max
= int_const_binop (MINUS_EXPR
, *vr0min
,
1818 build_int_cst (TREE_TYPE (*vr0min
), 1));
1827 /* If we know the intersection is empty, there's no need to
1828 conservatively add anything else to the set. */
1829 if (*vr0type
== VR_UNDEFINED
)
1832 /* As a fallback simply use { *VRTYPE, *VR0MIN, *VR0MAX } as
1833 result for the intersection. That's always a conservative
1834 correct estimate unless VR1 is a constant singleton range
1835 in which case we choose that. */
1836 if (vr1type
== VR_RANGE
1837 && is_gimple_min_invariant (vr1min
)
1838 && vrp_operand_equal_p (vr1min
, vr1max
))
1846 /* Helper for the intersection operation for value ranges. Given two
1847 ranges VR0 and VR1, set VR0 to the intersection of both ranges.
1848 This may not be the smallest possible such range. */
1851 irange::legacy_intersect (irange
*vr0
, const irange
*vr1
)
1853 gcc_checking_assert (vr0
->legacy_mode_p ());
1854 gcc_checking_assert (vr1
->legacy_mode_p ());
1855 /* If either range is VR_VARYING the other one wins. */
1856 if (vr1
->varying_p ())
1858 if (vr0
->varying_p ())
1860 vr0
->set (vr1
->min (), vr1
->max (), vr1
->kind ());
1864 /* When either range is VR_UNDEFINED the resulting range is
1865 VR_UNDEFINED, too. */
1866 if (vr0
->undefined_p ())
1868 if (vr1
->undefined_p ())
1870 vr0
->set_undefined ();
1874 value_range_kind vr0kind
= vr0
->kind ();
1875 tree vr0min
= vr0
->min ();
1876 tree vr0max
= vr0
->max ();
1878 intersect_ranges (&vr0kind
, &vr0min
, &vr0max
,
1879 vr1
->kind (), vr1
->min (), vr1
->max ());
1881 // Pessimize nonzero masks, as we don't support them.
1882 m_nonzero_mask
= NULL
;
1884 /* Make sure to canonicalize the result though as the inversion of a
1885 VR_RANGE can still be a VR_RANGE. */
1886 if (vr0kind
== VR_UNDEFINED
)
1887 vr0
->set_undefined ();
1888 else if (vr0kind
== VR_VARYING
)
1890 /* If we failed, use the original VR0. */
1894 vr0
->set (vr0min
, vr0max
, vr0kind
);
1897 /* Union the two value-ranges { *VR0TYPE, *VR0MIN, *VR0MAX } and
1898 { VR1TYPE, VR0MIN, VR0MAX } and store the result
1899 in { *VR0TYPE, *VR0MIN, *VR0MAX }. This may not be the smallest
1900 possible such range. The resulting range is not canonicalized. */
1903 union_ranges (enum value_range_kind
*vr0type
,
1904 tree
*vr0min
, tree
*vr0max
,
1905 enum value_range_kind vr1type
,
1906 tree vr1min
, tree vr1max
)
1908 int cmpmin
= compare_values (*vr0min
, vr1min
);
1909 int cmpmax
= compare_values (*vr0max
, vr1max
);
1910 bool mineq
= cmpmin
== 0;
1911 bool maxeq
= cmpmax
== 0;
1913 /* [] is vr0, () is vr1 in the following classification comments. */
1917 if (*vr0type
== vr1type
)
1918 /* Nothing to do for equal ranges. */
1920 else if ((*vr0type
== VR_RANGE
1921 && vr1type
== VR_ANTI_RANGE
)
1922 || (*vr0type
== VR_ANTI_RANGE
1923 && vr1type
== VR_RANGE
))
1925 /* For anti-range with range union the result is varying. */
1931 else if (operand_less_p (*vr0max
, vr1min
) == 1
1932 || operand_less_p (vr1max
, *vr0min
) == 1)
1934 /* [ ] ( ) or ( ) [ ]
1935 If the ranges have an empty intersection, result of the union
1936 operation is the anti-range or if both are anti-ranges
1938 if (*vr0type
== VR_ANTI_RANGE
1939 && vr1type
== VR_ANTI_RANGE
)
1941 else if (*vr0type
== VR_ANTI_RANGE
1942 && vr1type
== VR_RANGE
)
1944 else if (*vr0type
== VR_RANGE
1945 && vr1type
== VR_ANTI_RANGE
)
1951 else if (*vr0type
== VR_RANGE
1952 && vr1type
== VR_RANGE
)
1954 /* The result is the convex hull of both ranges. */
1955 if (operand_less_p (*vr0max
, vr1min
) == 1)
1957 /* If the result can be an anti-range, create one. */
1958 if (TREE_CODE (*vr0max
) == INTEGER_CST
1959 && TREE_CODE (vr1min
) == INTEGER_CST
1960 && vrp_val_is_min (*vr0min
)
1961 && vrp_val_is_max (vr1max
))
1963 tree min
= int_const_binop (PLUS_EXPR
,
1965 build_int_cst (TREE_TYPE (*vr0max
), 1));
1966 tree max
= int_const_binop (MINUS_EXPR
,
1968 build_int_cst (TREE_TYPE (vr1min
), 1));
1969 if (!operand_less_p (max
, min
))
1971 *vr0type
= VR_ANTI_RANGE
;
1983 /* If the result can be an anti-range, create one. */
1984 if (TREE_CODE (vr1max
) == INTEGER_CST
1985 && TREE_CODE (*vr0min
) == INTEGER_CST
1986 && vrp_val_is_min (vr1min
)
1987 && vrp_val_is_max (*vr0max
))
1989 tree min
= int_const_binop (PLUS_EXPR
,
1991 build_int_cst (TREE_TYPE (vr1max
), 1));
1992 tree max
= int_const_binop (MINUS_EXPR
,
1994 build_int_cst (TREE_TYPE (*vr0min
), 1));
1995 if (!operand_less_p (max
, min
))
1997 *vr0type
= VR_ANTI_RANGE
;
2011 else if ((maxeq
|| cmpmax
== 1)
2012 && (mineq
|| cmpmin
== -1))
2014 /* [ ( ) ] or [( ) ] or [ ( )] */
2015 if (*vr0type
== VR_RANGE
2016 && vr1type
== VR_RANGE
)
2018 else if (*vr0type
== VR_ANTI_RANGE
2019 && vr1type
== VR_ANTI_RANGE
)
2025 else if (*vr0type
== VR_ANTI_RANGE
2026 && vr1type
== VR_RANGE
)
2028 /* Arbitrarily choose the right or left gap. */
2029 if (!mineq
&& TREE_CODE (vr1min
) == INTEGER_CST
)
2030 *vr0max
= int_const_binop (MINUS_EXPR
, vr1min
,
2031 build_int_cst (TREE_TYPE (vr1min
), 1));
2032 else if (!maxeq
&& TREE_CODE (vr1max
) == INTEGER_CST
)
2033 *vr0min
= int_const_binop (PLUS_EXPR
, vr1max
,
2034 build_int_cst (TREE_TYPE (vr1max
), 1));
2038 else if (*vr0type
== VR_RANGE
2039 && vr1type
== VR_ANTI_RANGE
)
2040 /* The result covers everything. */
2045 else if ((maxeq
|| cmpmax
== -1)
2046 && (mineq
|| cmpmin
== 1))
2048 /* ( [ ] ) or ([ ] ) or ( [ ]) */
2049 if (*vr0type
== VR_RANGE
2050 && vr1type
== VR_RANGE
)
2056 else if (*vr0type
== VR_ANTI_RANGE
2057 && vr1type
== VR_ANTI_RANGE
)
2059 else if (*vr0type
== VR_RANGE
2060 && vr1type
== VR_ANTI_RANGE
)
2062 *vr0type
= VR_ANTI_RANGE
;
2063 if (!mineq
&& TREE_CODE (*vr0min
) == INTEGER_CST
)
2065 *vr0max
= int_const_binop (MINUS_EXPR
, *vr0min
,
2066 build_int_cst (TREE_TYPE (*vr0min
), 1));
2069 else if (!maxeq
&& TREE_CODE (*vr0max
) == INTEGER_CST
)
2071 *vr0min
= int_const_binop (PLUS_EXPR
, *vr0max
,
2072 build_int_cst (TREE_TYPE (*vr0max
), 1));
2078 else if (*vr0type
== VR_ANTI_RANGE
2079 && vr1type
== VR_RANGE
)
2080 /* The result covers everything. */
2085 else if (cmpmin
== -1
2087 && (operand_less_p (vr1min
, *vr0max
) == 1
2088 || operand_equal_p (vr1min
, *vr0max
, 0)))
2090 /* [ ( ] ) or [ ]( ) */
2091 if (*vr0type
== VR_RANGE
2092 && vr1type
== VR_RANGE
)
2094 else if (*vr0type
== VR_ANTI_RANGE
2095 && vr1type
== VR_ANTI_RANGE
)
2097 else if (*vr0type
== VR_ANTI_RANGE
2098 && vr1type
== VR_RANGE
)
2100 if (TREE_CODE (vr1min
) == INTEGER_CST
)
2101 *vr0max
= int_const_binop (MINUS_EXPR
, vr1min
,
2102 build_int_cst (TREE_TYPE (vr1min
), 1));
2106 else if (*vr0type
== VR_RANGE
2107 && vr1type
== VR_ANTI_RANGE
)
2109 if (TREE_CODE (*vr0max
) == INTEGER_CST
)
2112 *vr0min
= int_const_binop (PLUS_EXPR
, *vr0max
,
2113 build_int_cst (TREE_TYPE (*vr0max
), 1));
2122 else if (cmpmin
== 1
2124 && (operand_less_p (*vr0min
, vr1max
) == 1
2125 || operand_equal_p (*vr0min
, vr1max
, 0)))
2127 /* ( [ ) ] or ( )[ ] */
2128 if (*vr0type
== VR_RANGE
2129 && vr1type
== VR_RANGE
)
2131 else if (*vr0type
== VR_ANTI_RANGE
2132 && vr1type
== VR_ANTI_RANGE
)
2134 else if (*vr0type
== VR_ANTI_RANGE
2135 && vr1type
== VR_RANGE
)
2137 if (TREE_CODE (vr1max
) == INTEGER_CST
)
2138 *vr0min
= int_const_binop (PLUS_EXPR
, vr1max
,
2139 build_int_cst (TREE_TYPE (vr1max
), 1));
2143 else if (*vr0type
== VR_RANGE
2144 && vr1type
== VR_ANTI_RANGE
)
2146 if (TREE_CODE (*vr0min
) == INTEGER_CST
)
2149 *vr0max
= int_const_binop (MINUS_EXPR
, *vr0min
,
2150 build_int_cst (TREE_TYPE (*vr0min
), 1));
2165 *vr0type
= VR_VARYING
;
2166 *vr0min
= NULL_TREE
;
2167 *vr0max
= NULL_TREE
;
2170 /* Helper for meet operation for value ranges. Given two ranges VR0
2171 and VR1, set VR0 to the union of both ranges. This may not be the
2172 smallest possible such range. */
2175 irange::legacy_union (irange
*vr0
, const irange
*vr1
)
2177 gcc_checking_assert (vr0
->legacy_mode_p ());
2178 gcc_checking_assert (vr1
->legacy_mode_p ());
2180 /* VR0 has the resulting range if VR1 is undefined or VR0 is varying. */
2181 if (vr1
->undefined_p ()
2182 || vr0
->varying_p ())
2185 /* VR1 has the resulting range if VR0 is undefined or VR1 is varying. */
2186 if (vr0
->undefined_p ())
2188 vr0
->set (vr1
->min (), vr1
->max (), vr1
->kind ());
2192 if (vr1
->varying_p ())
2194 vr0
->set_varying (vr1
->type ());
2198 value_range_kind vr0kind
= vr0
->kind ();
2199 tree vr0min
= vr0
->min ();
2200 tree vr0max
= vr0
->max ();
2202 union_ranges (&vr0kind
, &vr0min
, &vr0max
,
2203 vr1
->kind (), vr1
->min (), vr1
->max ());
2205 // Pessimize nonzero masks, as we don't support them.
2206 m_nonzero_mask
= NULL
;
2208 if (vr0kind
== VR_UNDEFINED
)
2209 vr0
->set_undefined ();
2210 else if (vr0kind
== VR_VARYING
)
2212 /* Failed to find an efficient meet. Before giving up and
2213 setting the result to VARYING, see if we can at least derive
2214 a non-zero range. */
2215 if (range_includes_zero_p (vr0
) == 0
2216 && range_includes_zero_p (vr1
) == 0)
2217 vr0
->set_nonzero (vr0
->type ());
2219 vr0
->set_varying (vr0
->type ());
2222 vr0
->set (vr0min
, vr0max
, vr0kind
);
2225 /* Meet operation for value ranges. Given two value ranges VR0 and
2226 VR1, store in VR0 a range that contains both VR0 and VR1. This
2227 may not be the smallest possible such range.
2228 Return TRUE if the original value changes. */
2231 irange::legacy_verbose_union_ (const irange
*other
)
2233 if (legacy_mode_p ())
2235 if (!other
->legacy_mode_p ())
2237 int_range
<1> tmp
= *other
;
2238 legacy_union (this, &tmp
);
2241 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2243 fprintf (dump_file
, "Meeting\n ");
2244 dump_value_range (dump_file
, this);
2245 fprintf (dump_file
, "\nand\n ");
2246 dump_value_range (dump_file
, other
);
2247 fprintf (dump_file
, "\n");
2250 legacy_union (this, other
);
2252 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2254 fprintf (dump_file
, "to\n ");
2255 dump_value_range (dump_file
, this);
2256 fprintf (dump_file
, "\n");
2261 if (other
->legacy_mode_p ())
2263 int_range
<2> wider
= *other
;
2264 return irange_union (wider
);
2267 return irange_union (*other
);
2271 irange::legacy_verbose_intersect (const irange
*other
)
2273 if (legacy_mode_p ())
2275 if (!other
->legacy_mode_p ())
2277 int_range
<1> tmp
= *other
;
2278 legacy_intersect (this, &tmp
);
2281 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2283 fprintf (dump_file
, "Intersecting\n ");
2284 dump_value_range (dump_file
, this);
2285 fprintf (dump_file
, "\nand\n ");
2286 dump_value_range (dump_file
, other
);
2287 fprintf (dump_file
, "\n");
2290 legacy_intersect (this, other
);
2292 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2294 fprintf (dump_file
, "to\n ");
2295 dump_value_range (dump_file
, this);
2296 fprintf (dump_file
, "\n");
2301 if (other
->legacy_mode_p ())
2305 return irange_intersect (wider
);
2308 return irange_intersect (*other
);
2311 // Perform an efficient union with R when both ranges have only a single pair.
2312 // Excluded are VARYING and UNDEFINED ranges.
2314 // NOTE: It is the caller's responsibility to set the nonzero mask.
2317 irange::irange_single_pair_union (const irange
&r
)
2319 gcc_checking_assert (!undefined_p () && !varying_p ());
2320 gcc_checking_assert (!r
.undefined_p () && !varying_p ());
2322 signop sign
= TYPE_SIGN (TREE_TYPE (m_base
[0]));
2323 // Check if current lower bound is also the new lower bound.
2324 if (wi::le_p (wi::to_wide (m_base
[0]), wi::to_wide (r
.m_base
[0]), sign
))
2326 // If current upper bound is new upper bound, we're done.
2327 if (wi::le_p (wi::to_wide (r
.m_base
[1]), wi::to_wide (m_base
[1]), sign
))
2329 // Otherwise R has the new upper bound.
2330 // Check for overlap/touching ranges, or single target range.
2331 if (m_max_ranges
== 1
2332 || wi::to_widest (m_base
[1]) + 1 >= wi::to_widest (r
.m_base
[0]))
2333 m_base
[1] = r
.m_base
[1];
2336 // This is a dual range result.
2337 m_base
[2] = r
.m_base
[0];
2338 m_base
[3] = r
.m_base
[1];
2341 if (varying_compatible_p ())
2342 m_kind
= VR_VARYING
;
2346 // Set the new lower bound to R's lower bound.
2347 tree lb
= m_base
[0];
2348 m_base
[0] = r
.m_base
[0];
2350 // If R fully contains THIS range, just set the upper bound.
2351 if (wi::ge_p (wi::to_wide (r
.m_base
[1]), wi::to_wide (m_base
[1]), sign
))
2352 m_base
[1] = r
.m_base
[1];
2353 // Check for overlapping ranges, or target limited to a single range.
2354 else if (m_max_ranges
== 1
2355 || wi::to_widest (r
.m_base
[1]) + 1 >= wi::to_widest (lb
))
2357 // This has the new upper bound, just check for varying.
2358 if (varying_compatible_p ())
2359 m_kind
= VR_VARYING
;
2363 // Left with 2 pairs.
2366 m_base
[3] = m_base
[1];
2367 m_base
[1] = r
.m_base
[1];
2369 if (varying_compatible_p ())
2370 m_kind
= VR_VARYING
;
2374 // union_ for multi-ranges.
2377 irange::irange_union (const irange
&r
)
2379 gcc_checking_assert (!legacy_mode_p () && !r
.legacy_mode_p ());
2381 if (r
.undefined_p ())
2397 set_varying (type ());
2401 // Save the nonzero mask in case the set operations below clobber it.
2402 bool ret_nz
= union_nonzero_bits (r
);
2403 tree saved_nz
= m_nonzero_mask
;
2405 // The union_nonzero_bits may have turned things into a varying.
2409 // Special case one range union one range.
2410 if (m_num_ranges
== 1 && r
.m_num_ranges
== 1)
2412 bool ret
= irange_single_pair_union (r
);
2413 set_nonzero_bits (saved_nz
);
2416 return ret
|| ret_nz
;
2419 // If this ranges fully contains R, then we need do nothing.
2420 if (irange_contains_p (r
))
2423 // Do not worry about merging and such by reserving twice as many
2424 // pairs as needed, and then simply sort the 2 ranges into this
2425 // intermediate form.
2427 // The intermediate result will have the property that the beginning
2428 // of each range is <= the beginning of the next range. There may
2429 // be overlapping ranges at this point. I.e. this would be valid
2430 // [-20, 10], [-10, 0], [0, 20], [40, 90] as it satisfies this
2431 // contraint : -20 < -10 < 0 < 40. When the range is rebuilt into r,
2432 // the merge is performed.
2434 // [Xi,Yi]..[Xn,Yn] U [Xj,Yj]..[Xm,Ym] --> [Xk,Yk]..[Xp,Yp]
2435 auto_vec
<tree
, 20> res (m_num_ranges
* 2 + r
.m_num_ranges
* 2);
2436 unsigned i
= 0, j
= 0, k
= 0;
2438 while (i
< m_num_ranges
* 2 && j
< r
.m_num_ranges
* 2)
2440 // lower of Xi and Xj is the lowest point.
2441 if (wi::to_widest (m_base
[i
]) <= wi::to_widest (r
.m_base
[j
]))
2443 res
.quick_push (m_base
[i
]);
2444 res
.quick_push (m_base
[i
+ 1]);
2450 res
.quick_push (r
.m_base
[j
]);
2451 res
.quick_push (r
.m_base
[j
+ 1]);
2456 for ( ; i
< m_num_ranges
* 2; i
+= 2)
2458 res
.quick_push (m_base
[i
]);
2459 res
.quick_push (m_base
[i
+ 1]);
2462 for ( ; j
< r
.m_num_ranges
* 2; j
+= 2)
2464 res
.quick_push (r
.m_base
[j
]);
2465 res
.quick_push (r
.m_base
[j
+ 1]);
2469 // Now normalize the vector removing any overlaps.
2471 for (j
= 2; j
< k
; j
+= 2)
2473 // Current upper+1 is >= lower bound next pair, then we merge ranges.
2474 if (wi::to_widest (res
[i
- 1]) + 1 >= wi::to_widest (res
[j
]))
2476 // New upper bounds is greater of current or the next one.
2477 if (wi::to_widest (res
[j
+ 1]) > wi::to_widest (res
[i
- 1]))
2478 res
[i
- 1] = res
[j
+ 1];
2482 // This is a new distinct range, but no point in copying it
2483 // if it is already in the right place.
2487 res
[i
++] = res
[j
+ 1];
2494 // At this point, the vector should have i ranges, none overlapping.
2495 // Now it simply needs to be copied, and if there are too many
2496 // ranges, merge some. We wont do any analysis as to what the
2497 // "best" merges are, simply combine the final ranges into one.
2498 if (i
> m_max_ranges
* 2)
2500 res
[m_max_ranges
* 2 - 1] = res
[i
- 1];
2501 i
= m_max_ranges
* 2;
2504 for (j
= 0; j
< i
; j
++)
2505 m_base
[j
] = res
[j
];
2506 m_num_ranges
= i
/ 2;
2509 m_nonzero_mask
= saved_nz
;
2517 // Return TRUE if THIS fully contains R. No undefined or varying cases.
2520 irange::irange_contains_p (const irange
&r
) const
2522 gcc_checking_assert (!undefined_p () && !varying_p ());
2523 gcc_checking_assert (!r
.undefined_p () && !varying_p ());
2525 // In order for THIS to fully contain R, all of the pairs within R must
2526 // be fully contained by the pairs in this object.
2527 signop sign
= TYPE_SIGN (TREE_TYPE(m_base
[0]));
2530 tree rl
= r
.m_base
[0];
2531 tree ru
= r
.m_base
[1];
2536 // If r is contained within this range, move to the next R
2537 if (wi::ge_p (wi::to_wide (rl
), wi::to_wide (l
), sign
)
2538 && wi::le_p (wi::to_wide (ru
), wi::to_wide (u
), sign
))
2540 // This pair is OK, Either done, or bump to the next.
2541 if (++ri
>= r
.num_pairs ())
2543 rl
= r
.m_base
[ri
* 2];
2544 ru
= r
.m_base
[ri
* 2 + 1];
2547 // Otherwise, check if this's pair occurs before R's.
2548 if (wi::lt_p (wi::to_wide (u
), wi::to_wide (rl
), sign
))
2550 // THere's still at leats one pair of R left.
2551 if (++i
>= num_pairs ())
2554 u
= m_base
[i
* 2 + 1];
2563 // Intersect for multi-ranges. Return TRUE if anything changes.
2566 irange::irange_intersect (const irange
&r
)
2568 gcc_checking_assert (!legacy_mode_p () && !r
.legacy_mode_p ());
2569 gcc_checking_assert (undefined_p () || r
.undefined_p ()
2570 || range_compatible_p (type (), r
.type ()));
2574 if (r
.undefined_p ())
2580 // Save the nonzero mask in case the set operations below clobber it.
2581 bool ret_nz
= intersect_nonzero_bits (r
);
2582 tree saved_nz
= m_nonzero_mask
;
2591 set_nonzero_bits (saved_nz
);
2597 if (r
.num_pairs () == 1)
2599 bool res
= intersect (r
.lower_bound (), r
.upper_bound ());
2603 set_nonzero_bits (saved_nz
);
2604 return res
|| saved_nz
;
2607 // If R fully contains this, then intersection will change nothing.
2608 if (r
.irange_contains_p (*this))
2611 signop sign
= TYPE_SIGN (TREE_TYPE(m_base
[0]));
2612 unsigned bld_pair
= 0;
2613 unsigned bld_lim
= m_max_ranges
;
2614 int_range_max
r2 (*this);
2615 unsigned r2_lim
= r2
.num_pairs ();
2617 for (unsigned i
= 0; i
< r
.num_pairs (); )
2619 // If r1's upper is < r2's lower, we can skip r1's pair.
2620 tree ru
= r
.m_base
[i
* 2 + 1];
2621 tree r2l
= r2
.m_base
[i2
* 2];
2622 if (wi::lt_p (wi::to_wide (ru
), wi::to_wide (r2l
), sign
))
2627 // Likewise, skip r2's pair if its excluded.
2628 tree r2u
= r2
.m_base
[i2
* 2 + 1];
2629 tree rl
= r
.m_base
[i
* 2];
2630 if (wi::lt_p (wi::to_wide (r2u
), wi::to_wide (rl
), sign
))
2635 // No more r2, break.
2639 // Must be some overlap. Find the highest of the lower bounds,
2640 // and set it, unless the build limits lower bounds is already
2642 if (bld_pair
< bld_lim
)
2644 if (wi::ge_p (wi::to_wide (rl
), wi::to_wide (r2l
), sign
))
2645 m_base
[bld_pair
* 2] = rl
;
2647 m_base
[bld_pair
* 2] = r2l
;
2650 // Decrease and set a new upper.
2653 // ...and choose the lower of the upper bounds.
2654 if (wi::le_p (wi::to_wide (ru
), wi::to_wide (r2u
), sign
))
2656 m_base
[bld_pair
* 2 + 1] = ru
;
2658 // Move past the r1 pair and keep trying.
2664 m_base
[bld_pair
* 2 + 1] = r2u
;
2669 // No more r2, break.
2672 // r2 has the higher lower bound.
2675 // At the exit of this loop, it is one of 2 things:
2676 // ran out of r1, or r2, but either means we are done.
2677 m_num_ranges
= bld_pair
;
2680 if (!undefined_p ())
2681 m_nonzero_mask
= saved_nz
;
2691 // Multirange intersect for a specified wide_int [lb, ub] range.
2692 // Return TRUE if intersect changed anything.
2694 // NOTE: It is the caller's responsibility to intersect the nonzero masks.
2697 irange::intersect (const wide_int
& lb
, const wide_int
& ub
)
2699 // Undefined remains undefined.
2703 if (legacy_mode_p ())
2705 intersect (int_range
<1> (type (), lb
, ub
));
2709 tree range_type
= type();
2710 signop sign
= TYPE_SIGN (range_type
);
2712 gcc_checking_assert (TYPE_PRECISION (range_type
) == wi::get_precision (lb
));
2713 gcc_checking_assert (TYPE_PRECISION (range_type
) == wi::get_precision (ub
));
2715 // If this range is fuly contained, then intersection will do nothing.
2716 if (wi::ge_p (lower_bound (), lb
, sign
)
2717 && wi::le_p (upper_bound (), ub
, sign
))
2720 unsigned bld_index
= 0;
2721 unsigned pair_lim
= num_pairs ();
2722 for (unsigned i
= 0; i
< pair_lim
; i
++)
2724 tree pairl
= m_base
[i
* 2];
2725 tree pairu
= m_base
[i
* 2 + 1];
2726 // Once UB is less than a pairs lower bound, we're done.
2727 if (wi::lt_p (ub
, wi::to_wide (pairl
), sign
))
2729 // if LB is greater than this pairs upper, this pair is excluded.
2730 if (wi::lt_p (wi::to_wide (pairu
), lb
, sign
))
2733 // Must be some overlap. Find the highest of the lower bounds,
2735 if (wi::gt_p (lb
, wi::to_wide (pairl
), sign
))
2736 m_base
[bld_index
* 2] = wide_int_to_tree (range_type
, lb
);
2738 m_base
[bld_index
* 2] = pairl
;
2740 // ...and choose the lower of the upper bounds and if the base pair
2741 // has the lower upper bound, need to check next pair too.
2742 if (wi::lt_p (ub
, wi::to_wide (pairu
), sign
))
2744 m_base
[bld_index
++ * 2 + 1] = wide_int_to_tree (range_type
, ub
);
2748 m_base
[bld_index
++ * 2 + 1] = pairu
;
2751 m_num_ranges
= bld_index
;
2762 // Signed 1-bits are strange. You can't subtract 1, because you can't
2763 // represent the number 1. This works around that for the invert routine.
2765 static wide_int
inline
2766 subtract_one (const wide_int
&x
, tree type
, wi::overflow_type
&overflow
)
2768 if (TYPE_SIGN (type
) == SIGNED
)
2769 return wi::add (x
, -1, SIGNED
, &overflow
);
2771 return wi::sub (x
, 1, UNSIGNED
, &overflow
);
2774 // The analogous function for adding 1.
2776 static wide_int
inline
2777 add_one (const wide_int
&x
, tree type
, wi::overflow_type
&overflow
)
2779 if (TYPE_SIGN (type
) == SIGNED
)
2780 return wi::sub (x
, -1, SIGNED
, &overflow
);
2782 return wi::add (x
, 1, UNSIGNED
, &overflow
);
2785 // Return the inverse of a range.
2790 if (legacy_mode_p ())
2792 // We can't just invert VR_RANGE and VR_ANTI_RANGE because we may
2793 // create non-canonical ranges. Use the constructors instead.
2794 if (m_kind
== VR_RANGE
)
2795 *this = value_range (min (), max (), VR_ANTI_RANGE
);
2796 else if (m_kind
== VR_ANTI_RANGE
)
2797 *this = value_range (min (), max ());
2803 gcc_checking_assert (!undefined_p () && !varying_p ());
2804 m_nonzero_mask
= NULL
;
2806 // We always need one more set of bounds to represent an inverse, so
2807 // if we're at the limit, we can't properly represent things.
2809 // For instance, to represent the inverse of a 2 sub-range set
2810 // [5, 10][20, 30], we would need a 3 sub-range set
2811 // [-MIN, 4][11, 19][31, MAX].
2813 // In this case, return the most conservative thing.
2815 // However, if any of the extremes of the range are -MIN/+MAX, we
2816 // know we will not need an extra bound. For example:
2818 // INVERT([-MIN,20][30,40]) => [21,29][41,+MAX]
2819 // INVERT([-MIN,20][30,MAX]) => [21,29]
2820 tree ttype
= type ();
2821 unsigned prec
= TYPE_PRECISION (ttype
);
2822 signop sign
= TYPE_SIGN (ttype
);
2823 wide_int type_min
= wi::min_value (prec
, sign
);
2824 wide_int type_max
= wi::max_value (prec
, sign
);
2825 if (m_num_ranges
== m_max_ranges
2826 && lower_bound () != type_min
2827 && upper_bound () != type_max
)
2829 m_base
[1] = wide_int_to_tree (ttype
, type_max
);
2833 // The algorithm is as follows. To calculate INVERT ([a,b][c,d]), we
2834 // generate [-MIN, a-1][b+1, c-1][d+1, MAX].
2836 // If there is an over/underflow in the calculation for any
2837 // sub-range, we eliminate that subrange. This allows us to easily
2838 // calculate INVERT([-MIN, 5]) with: [-MIN, -MIN-1][6, MAX]. And since
2839 // we eliminate the underflow, only [6, MAX] remains.
2841 wi::overflow_type ovf
;
2842 // Construct leftmost range.
2843 int_range_max
orig_range (*this);
2844 unsigned nitems
= 0;
2846 // If this is going to underflow on the MINUS 1, don't even bother
2847 // checking. This also handles subtracting one from an unsigned 0,
2848 // which doesn't set the underflow bit.
2849 if (type_min
!= orig_range
.lower_bound ())
2851 m_base
[nitems
++] = wide_int_to_tree (ttype
, type_min
);
2852 tmp
= subtract_one (orig_range
.lower_bound (), ttype
, ovf
);
2853 m_base
[nitems
++] = wide_int_to_tree (ttype
, tmp
);
2858 // Construct middle ranges if applicable.
2859 if (orig_range
.num_pairs () > 1)
2862 for (; j
< (orig_range
.num_pairs () * 2) - 1; j
+= 2)
2864 // The middle ranges cannot have MAX/MIN, so there's no need
2865 // to check for unsigned overflow on the +1 and -1 here.
2866 tmp
= wi::add (wi::to_wide (orig_range
.m_base
[j
]), 1, sign
, &ovf
);
2867 m_base
[nitems
++] = wide_int_to_tree (ttype
, tmp
);
2868 tmp
= subtract_one (wi::to_wide (orig_range
.m_base
[j
+ 1]),
2870 m_base
[nitems
++] = wide_int_to_tree (ttype
, tmp
);
2876 // Construct rightmost range.
2878 // However, if this will overflow on the PLUS 1, don't even bother.
2879 // This also handles adding one to an unsigned MAX, which doesn't
2880 // set the overflow bit.
2881 if (type_max
!= wi::to_wide (orig_range
.m_base
[i
]))
2883 tmp
= add_one (wi::to_wide (orig_range
.m_base
[i
]), ttype
, ovf
);
2884 m_base
[nitems
++] = wide_int_to_tree (ttype
, tmp
);
2885 m_base
[nitems
++] = wide_int_to_tree (ttype
, type_max
);
2889 m_num_ranges
= nitems
/ 2;
2891 // We disallow undefined or varying coming in, so the result can
2892 // only be a VR_RANGE.
2893 gcc_checking_assert (m_kind
== VR_RANGE
);
2900 irange::set_nonzero_bits (tree mask
)
2902 gcc_checking_assert (!undefined_p ());
2908 m_nonzero_mask
= NULL
;
2909 // Clearing the mask may have turned a range into VARYING.
2914 m_nonzero_mask
= mask
;
2915 // Setting the mask may have turned a VARYING into a range.
2916 if (m_kind
== VR_VARYING
)
2924 irange::set_nonzero_bits (const wide_int_ref
&bits
)
2926 gcc_checking_assert (!undefined_p ());
2930 set_nonzero_bits (NULL
);
2933 // If we have only one bit set in the mask, we can figure out the
2934 // range immediately.
2935 if (wi::popcount (bits
) == 1)
2937 bool has_zero
= contains_p (build_zero_cst (type ()));
2938 set (type (), bits
, bits
);
2942 zero
.set_zero (type ());
2946 set_nonzero_bits (wide_int_to_tree (type (), bits
));
2950 irange::get_nonzero_bits () const
2952 gcc_checking_assert (!undefined_p ());
2954 // In case anyone in the legacy world queries us.
2958 return wi::to_wide (m_nonzero_mask
);
2959 return wi::shwi (-1, TYPE_PRECISION (type ()));
2962 // Calculate the nonzero bits inherent in the range.
2963 wide_int min
= lower_bound ();
2964 wide_int max
= upper_bound ();
2965 wide_int xorv
= min
^ max
;
2968 unsigned prec
= TYPE_PRECISION (type ());
2969 xorv
= wi::mask (prec
- wi::clz (xorv
), false, prec
);
2971 wide_int mask
= min
| xorv
;
2973 // Return the nonzero bits augmented by the range.
2975 return mask
& wi::to_wide (m_nonzero_mask
);
2980 // Intersect the nonzero bits in R into THIS.
2983 irange::intersect_nonzero_bits (const irange
&r
)
2985 gcc_checking_assert (!undefined_p () && !r
.undefined_p ());
2987 if (m_nonzero_mask
|| r
.m_nonzero_mask
)
2989 wide_int nz
= wi::bit_and (get_nonzero_bits (),
2990 r
.get_nonzero_bits ());
2991 set_nonzero_bits (nz
);
2997 // Union the nonzero bits in R into THIS.
3000 irange::union_nonzero_bits (const irange
&r
)
3002 gcc_checking_assert (!undefined_p () && !r
.undefined_p ());
3004 if (m_nonzero_mask
|| r
.m_nonzero_mask
)
3006 wide_int nz
= wi::bit_or (get_nonzero_bits (),
3007 r
.get_nonzero_bits ());
3008 set_nonzero_bits (nz
);
3015 dump_value_range (FILE *file
, const vrange
*vr
)
3021 debug (const vrange
*vr
)
3023 dump_value_range (stderr
, vr
);
3024 fprintf (stderr
, "\n");
3028 debug (const vrange
&vr
)
3034 debug (const value_range
*vr
)
3036 dump_value_range (stderr
, vr
);
3037 fprintf (stderr
, "\n");
3041 debug (const value_range
&vr
)
3043 dump_value_range (stderr
, &vr
);
3044 fprintf (stderr
, "\n");
3047 /* Create two value-ranges in *VR0 and *VR1 from the anti-range *AR
3048 so that *VR0 U *VR1 == *AR. Returns true if that is possible,
3049 false otherwise. If *AR can be represented with a single range
3050 *VR1 will be VR_UNDEFINED. */
3053 ranges_from_anti_range (const value_range
*ar
,
3054 value_range
*vr0
, value_range
*vr1
)
3056 tree type
= ar
->type ();
3058 vr0
->set_undefined ();
3059 vr1
->set_undefined ();
3061 /* As a future improvement, we could handle ~[0, A] as: [-INF, -1] U
3062 [A+1, +INF]. Not sure if this helps in practice, though. */
3064 if (ar
->kind () != VR_ANTI_RANGE
3065 || TREE_CODE (ar
->min ()) != INTEGER_CST
3066 || TREE_CODE (ar
->max ()) != INTEGER_CST
3067 || !vrp_val_min (type
)
3068 || !vrp_val_max (type
))
3071 if (tree_int_cst_lt (vrp_val_min (type
), ar
->min ()))
3072 vr0
->set (vrp_val_min (type
),
3073 wide_int_to_tree (type
, wi::to_wide (ar
->min ()) - 1));
3074 if (tree_int_cst_lt (ar
->max (), vrp_val_max (type
)))
3075 vr1
->set (wide_int_to_tree (type
, wi::to_wide (ar
->max ()) + 1),
3076 vrp_val_max (type
));
3077 if (vr0
->undefined_p ())
3080 vr1
->set_undefined ();
3083 return !vr0
->undefined_p ();
3087 range_has_numeric_bounds_p (const irange
*vr
)
3089 return (!vr
->undefined_p ()
3090 && TREE_CODE (vr
->min ()) == INTEGER_CST
3091 && TREE_CODE (vr
->max ()) == INTEGER_CST
);
3094 /* Return whether VAL is equal to the maximum value of its type.
3095 We can't do a simple equality comparison with TYPE_MAX_VALUE because
3096 C typedefs and Ada subtypes can produce types whose TYPE_MAX_VALUE
3097 is not == to the integer constant with the same value in the type. */
3100 vrp_val_is_max (const_tree val
)
3102 tree type_max
= vrp_val_max (TREE_TYPE (val
));
3103 return (val
== type_max
3104 || (type_max
!= NULL_TREE
3105 && operand_equal_p (val
, type_max
, 0)));
3108 /* Return whether VAL is equal to the minimum value of its type. */
3111 vrp_val_is_min (const_tree val
)
3113 tree type_min
= vrp_val_min (TREE_TYPE (val
));
3114 return (val
== type_min
3115 || (type_min
!= NULL_TREE
3116 && operand_equal_p (val
, type_min
, 0)));
3119 /* Return true, if VAL1 and VAL2 are equal values for VRP purposes. */
3122 vrp_operand_equal_p (const_tree val1
, const_tree val2
)
3126 if (!val1
|| !val2
|| !operand_equal_p (val1
, val2
, 0))
3131 // ?? These stubs are for ipa-prop.cc which use a value_range in a
3132 // hash_traits. hash-traits.h defines an extern of gt_ggc_mx (T &)
3133 // instead of picking up the gt_ggc_mx (T *) version.
3135 gt_pch_nx (int_range
<1> *&x
)
3137 return gt_pch_nx ((irange
*) x
);
3141 gt_ggc_mx (int_range
<1> *&x
)
3143 return gt_ggc_mx ((irange
*) x
);
3146 #define DEFINE_INT_RANGE_INSTANCE(N) \
3147 template int_range<N>::int_range(tree, tree, value_range_kind); \
3148 template int_range<N>::int_range(tree_node *, \
3151 value_range_kind); \
3152 template int_range<N>::int_range(tree); \
3153 template int_range<N>::int_range(const irange &); \
3154 template int_range<N>::int_range(const int_range &); \
3155 template int_range<N>& int_range<N>::operator= (const int_range &);
3157 DEFINE_INT_RANGE_INSTANCE(1)
3158 DEFINE_INT_RANGE_INSTANCE(2)
3159 DEFINE_INT_RANGE_INSTANCE(3)
3160 DEFINE_INT_RANGE_INSTANCE(255)
3163 #include "selftest.h"
3167 #define INT(N) build_int_cst (integer_type_node, (N))
3168 #define UINT(N) build_int_cstu (unsigned_type_node, (N))
3169 #define UINT128(N) build_int_cstu (u128_type, (N))
3170 #define UCHAR(N) build_int_cstu (unsigned_char_type_node, (N))
3171 #define SCHAR(N) build_int_cst (signed_char_type_node, (N))
3174 build_range3 (int a
, int b
, int c
, int d
, int e
, int f
)
3176 int_range
<3> i1 (INT (a
), INT (b
));
3177 int_range
<3> i2 (INT (c
), INT (d
));
3178 int_range
<3> i3 (INT (e
), INT (f
));
3185 range_tests_irange3 ()
3187 typedef int_range
<3> int_range3
;
3188 int_range3 r0
, r1
, r2
;
3189 int_range3 i1
, i2
, i3
;
3191 // ([10,20] U [5,8]) U [1,3] ==> [1,3][5,8][10,20].
3192 r0
= int_range3 (INT (10), INT (20));
3193 r1
= int_range3 (INT (5), INT (8));
3195 r1
= int_range3 (INT (1), INT (3));
3197 ASSERT_TRUE (r0
== build_range3 (1, 3, 5, 8, 10, 20));
3199 // [1,3][5,8][10,20] U [-5,0] => [-5,3][5,8][10,20].
3200 r1
= int_range3 (INT (-5), INT (0));
3202 ASSERT_TRUE (r0
== build_range3 (-5, 3, 5, 8, 10, 20));
3204 // [10,20][30,40] U [50,60] ==> [10,20][30,40][50,60].
3205 r1
= int_range3 (INT (50), INT (60));
3206 r0
= int_range3 (INT (10), INT (20));
3207 r0
.union_ (int_range3 (INT (30), INT (40)));
3209 ASSERT_TRUE (r0
== build_range3 (10, 20, 30, 40, 50, 60));
3210 // [10,20][30,40][50,60] U [70, 80] ==> [10,20][30,40][50,60][70,80].
3211 r1
= int_range3 (INT (70), INT (80));
3214 r2
= build_range3 (10, 20, 30, 40, 50, 60);
3215 r2
.union_ (int_range3 (INT (70), INT (80)));
3216 ASSERT_TRUE (r0
== r2
);
3218 // [10,20][30,40][50,60] U [6,35] => [6,40][50,60].
3219 r0
= build_range3 (10, 20, 30, 40, 50, 60);
3220 r1
= int_range3 (INT (6), INT (35));
3222 r1
= int_range3 (INT (6), INT (40));
3223 r1
.union_ (int_range3 (INT (50), INT (60)));
3224 ASSERT_TRUE (r0
== r1
);
3226 // [10,20][30,40][50,60] U [6,60] => [6,60].
3227 r0
= build_range3 (10, 20, 30, 40, 50, 60);
3228 r1
= int_range3 (INT (6), INT (60));
3230 ASSERT_TRUE (r0
== int_range3 (INT (6), INT (60)));
3232 // [10,20][30,40][50,60] U [6,70] => [6,70].
3233 r0
= build_range3 (10, 20, 30, 40, 50, 60);
3234 r1
= int_range3 (INT (6), INT (70));
3236 ASSERT_TRUE (r0
== int_range3 (INT (6), INT (70)));
3238 // [10,20][30,40][50,60] U [35,70] => [10,20][30,70].
3239 r0
= build_range3 (10, 20, 30, 40, 50, 60);
3240 r1
= int_range3 (INT (35), INT (70));
3242 r1
= int_range3 (INT (10), INT (20));
3243 r1
.union_ (int_range3 (INT (30), INT (70)));
3244 ASSERT_TRUE (r0
== r1
);
3246 // [10,20][30,40][50,60] U [15,35] => [10,40][50,60].
3247 r0
= build_range3 (10, 20, 30, 40, 50, 60);
3248 r1
= int_range3 (INT (15), INT (35));
3250 r1
= int_range3 (INT (10), INT (40));
3251 r1
.union_ (int_range3 (INT (50), INT (60)));
3252 ASSERT_TRUE (r0
== r1
);
3254 // [10,20][30,40][50,60] U [35,35] => [10,20][30,40][50,60].
3255 r0
= build_range3 (10, 20, 30, 40, 50, 60);
3256 r1
= int_range3 (INT (35), INT (35));
3258 ASSERT_TRUE (r0
== build_range3 (10, 20, 30, 40, 50, 60));
3262 range_tests_int_range_max ()
3265 unsigned int nrange
;
3267 // Build a huge multi-range range.
3268 for (nrange
= 0; nrange
< 50; ++nrange
)
3270 int_range
<1> tmp (INT (nrange
*10), INT (nrange
*10 + 5));
3273 ASSERT_TRUE (big
.num_pairs () == nrange
);
3275 // Verify that we can copy it without loosing precision.
3276 int_range_max
copy (big
);
3277 ASSERT_TRUE (copy
.num_pairs () == nrange
);
3279 // Inverting it should produce one more sub-range.
3281 ASSERT_TRUE (big
.num_pairs () == nrange
+ 1);
3283 int_range
<1> tmp (INT (5), INT (37));
3284 big
.intersect (tmp
);
3285 ASSERT_TRUE (big
.num_pairs () == 4);
3287 // Test that [10,10][20,20] does NOT contain 15.
3289 int_range_max
i1 (build_int_cst (integer_type_node
, 10),
3290 build_int_cst (integer_type_node
, 10));
3291 int_range_max
i2 (build_int_cst (integer_type_node
, 20),
3292 build_int_cst (integer_type_node
, 20));
3294 ASSERT_FALSE (i1
.contains_p (build_int_cst (integer_type_node
, 15)));
3299 range_tests_legacy ()
3301 // Test truncating copy to int_range<1>.
3302 int_range
<3> big
= build_range3 (10, 20, 30, 40, 50, 60);
3303 int_range
<1> small
= big
;
3304 ASSERT_TRUE (small
== int_range
<1> (INT (10), INT (60)));
3306 // Test truncating copy to int_range<2>.
3307 int_range
<2> medium
= big
;
3308 ASSERT_TRUE (!medium
.undefined_p ());
3310 // Test that a truncating copy of [MIN,20][22,40][80,MAX]
3311 // ends up as a conservative anti-range of ~[21,21].
3312 big
= int_range
<3> (vrp_val_min (integer_type_node
), INT (20));
3313 big
.union_ (int_range
<1> (INT (22), INT (40)));
3314 big
.union_ (int_range
<1> (INT (80), vrp_val_max (integer_type_node
)));
3316 ASSERT_TRUE (small
== int_range
<1> (INT (21), INT (21), VR_ANTI_RANGE
));
3318 // Copying a legacy symbolic to an int_range should normalize the
3319 // symbolic at copy time.
3321 tree ssa
= make_ssa_name (integer_type_node
);
3322 value_range
legacy_range (ssa
, INT (25));
3323 int_range
<2> copy
= legacy_range
;
3324 ASSERT_TRUE (copy
== int_range
<2> (vrp_val_min (integer_type_node
),
3327 // Test that copying ~[abc_23, abc_23] to a multi-range yields varying.
3328 legacy_range
= value_range (ssa
, ssa
, VR_ANTI_RANGE
);
3329 copy
= legacy_range
;
3330 ASSERT_TRUE (copy
.varying_p ());
3333 // VARYING of different sizes should not be equal.
3334 tree big_type
= build_nonstandard_integer_type (32, 1);
3335 tree small_type
= build_nonstandard_integer_type (16, 1);
3336 int_range_max
r0 (big_type
);
3337 int_range_max
r1 (small_type
);
3338 ASSERT_TRUE (r0
!= r1
);
3339 value_range
vr0 (big_type
);
3340 int_range_max
vr1 (small_type
);
3341 ASSERT_TRUE (vr0
!= vr1
);
3344 // Simulate -fstrict-enums where the domain of a type is less than the
3348 range_tests_strict_enum ()
3350 // The enum can only hold [0, 3].
3351 tree rtype
= copy_node (unsigned_type_node
);
3352 TYPE_MIN_VALUE (rtype
) = build_int_cstu (rtype
, 0);
3353 TYPE_MAX_VALUE (rtype
) = build_int_cstu (rtype
, 3);
3355 // Test that even though vr1 covers the strict enum domain ([0, 3]),
3356 // it does not cover the domain of the underlying type.
3357 int_range
<1> vr1 (build_int_cstu (rtype
, 0), build_int_cstu (rtype
, 1));
3358 int_range
<1> vr2 (build_int_cstu (rtype
, 2), build_int_cstu (rtype
, 3));
3360 ASSERT_TRUE (vr1
== int_range
<1> (build_int_cstu (rtype
, 0),
3361 build_int_cstu (rtype
, 3)));
3362 ASSERT_FALSE (vr1
.varying_p ());
3364 // Test that copying to a multi-range does not change things.
3365 int_range
<2> ir1 (vr1
);
3366 ASSERT_TRUE (ir1
== vr1
);
3367 ASSERT_FALSE (ir1
.varying_p ());
3369 // The same test as above, but using TYPE_{MIN,MAX}_VALUE instead of [0,3].
3370 vr1
= int_range
<1> (TYPE_MIN_VALUE (rtype
), TYPE_MAX_VALUE (rtype
));
3372 ASSERT_TRUE (ir1
== vr1
);
3373 ASSERT_FALSE (ir1
.varying_p ());
3379 tree u128_type
= build_nonstandard_integer_type (128, /*unsigned=*/1);
3380 int_range
<1> i1
, i2
, i3
;
3381 int_range
<1> r0
, r1
, rold
;
3383 // Test 1-bit signed integer union.
3384 // [-1,-1] U [0,0] = VARYING.
3385 tree one_bit_type
= build_nonstandard_integer_type (1, 0);
3386 tree one_bit_min
= vrp_val_min (one_bit_type
);
3387 tree one_bit_max
= vrp_val_max (one_bit_type
);
3389 int_range
<2> min (one_bit_min
, one_bit_min
);
3390 int_range
<2> max (one_bit_max
, one_bit_max
);
3392 ASSERT_TRUE (max
.varying_p ());
3395 // Test inversion of 1-bit signed integers.
3397 int_range
<2> min (one_bit_min
, one_bit_min
);
3398 int_range
<2> max (one_bit_max
, one_bit_max
);
3402 ASSERT_TRUE (t
== max
);
3405 ASSERT_TRUE (t
== min
);
3408 // Test that NOT(255) is [0..254] in 8-bit land.
3409 int_range
<1> not_255 (UCHAR (255), UCHAR (255), VR_ANTI_RANGE
);
3410 ASSERT_TRUE (not_255
== int_range
<1> (UCHAR (0), UCHAR (254)));
3412 // Test that NOT(0) is [1..255] in 8-bit land.
3413 int_range
<1> not_zero
= range_nonzero (unsigned_char_type_node
);
3414 ASSERT_TRUE (not_zero
== int_range
<1> (UCHAR (1), UCHAR (255)));
3416 // Check that [0,127][0x..ffffff80,0x..ffffff]
3417 // => ~[128, 0x..ffffff7f].
3418 r0
= int_range
<1> (UINT128 (0), UINT128 (127));
3419 tree high
= build_minus_one_cst (u128_type
);
3420 // low = -1 - 127 => 0x..ffffff80.
3421 tree low
= fold_build2 (MINUS_EXPR
, u128_type
, high
, UINT128(127));
3422 r1
= int_range
<1> (low
, high
); // [0x..ffffff80, 0x..ffffffff]
3423 // r0 = [0,127][0x..ffffff80,0x..fffffff].
3425 // r1 = [128, 0x..ffffff7f].
3426 r1
= int_range
<1> (UINT128(128),
3427 fold_build2 (MINUS_EXPR
, u128_type
,
3428 build_minus_one_cst (u128_type
),
3431 ASSERT_TRUE (r0
== r1
);
3433 r0
.set_varying (integer_type_node
);
3434 tree minint
= wide_int_to_tree (integer_type_node
, r0
.lower_bound ());
3435 tree maxint
= wide_int_to_tree (integer_type_node
, r0
.upper_bound ());
3437 r0
.set_varying (short_integer_type_node
);
3439 r0
.set_varying (unsigned_type_node
);
3440 tree maxuint
= wide_int_to_tree (unsigned_type_node
, r0
.upper_bound ());
3442 // Check that ~[0,5] => [6,MAX] for unsigned int.
3443 r0
= int_range
<1> (UINT (0), UINT (5));
3445 ASSERT_TRUE (r0
== int_range
<1> (UINT(6), maxuint
));
3447 // Check that ~[10,MAX] => [0,9] for unsigned int.
3448 r0
= int_range
<1> (UINT(10), maxuint
);
3450 ASSERT_TRUE (r0
== int_range
<1> (UINT (0), UINT (9)));
3452 // Check that ~[0,5] => [6,MAX] for unsigned 128-bit numbers.
3453 r0
= int_range
<1> (UINT128 (0), UINT128 (5), VR_ANTI_RANGE
);
3454 r1
= int_range
<1> (UINT128(6), build_minus_one_cst (u128_type
));
3455 ASSERT_TRUE (r0
== r1
);
3457 // Check that [~5] is really [-MIN,4][6,MAX].
3458 r0
= int_range
<1> (INT (5), INT (5), VR_ANTI_RANGE
);
3459 r1
= int_range
<1> (minint
, INT (4));
3460 r1
.union_ (int_range
<1> (INT (6), maxint
));
3461 ASSERT_FALSE (r1
.undefined_p ());
3462 ASSERT_TRUE (r0
== r1
);
3464 r1
= int_range
<1> (INT (5), INT (5));
3465 int_range
<1> r2 (r1
);
3466 ASSERT_TRUE (r1
== r2
);
3468 r1
= int_range
<1> (INT (5), INT (10));
3470 r1
= int_range
<1> (integer_type_node
,
3471 wi::to_wide (INT (5)), wi::to_wide (INT (10)));
3472 ASSERT_TRUE (r1
.contains_p (INT (7)));
3474 r1
= int_range
<1> (SCHAR (0), SCHAR (20));
3475 ASSERT_TRUE (r1
.contains_p (SCHAR(15)));
3476 ASSERT_FALSE (r1
.contains_p (SCHAR(300)));
3478 // NOT([10,20]) ==> [-MIN,9][21,MAX].
3479 r0
= r1
= int_range
<1> (INT (10), INT (20));
3480 r2
= int_range
<1> (minint
, INT(9));
3481 r2
.union_ (int_range
<1> (INT(21), maxint
));
3482 ASSERT_FALSE (r2
.undefined_p ());
3484 ASSERT_TRUE (r1
== r2
);
3485 // Test that NOT(NOT(x)) == x.
3487 ASSERT_TRUE (r0
== r2
);
3489 // Test that booleans and their inverse work as expected.
3490 r0
= range_zero (boolean_type_node
);
3491 ASSERT_TRUE (r0
== int_range
<1> (build_zero_cst (boolean_type_node
),
3492 build_zero_cst (boolean_type_node
)));
3494 ASSERT_TRUE (r0
== int_range
<1> (build_one_cst (boolean_type_node
),
3495 build_one_cst (boolean_type_node
)));
3497 // Make sure NULL and non-NULL of pointer types work, and that
3498 // inverses of them are consistent.
3499 tree voidp
= build_pointer_type (void_type_node
);
3500 r0
= range_zero (voidp
);
3504 ASSERT_TRUE (r0
== r1
);
3506 // [10,20] U [15, 30] => [10, 30].
3507 r0
= int_range
<1> (INT (10), INT (20));
3508 r1
= int_range
<1> (INT (15), INT (30));
3510 ASSERT_TRUE (r0
== int_range
<1> (INT (10), INT (30)));
3512 // [15,40] U [] => [15,40].
3513 r0
= int_range
<1> (INT (15), INT (40));
3514 r1
.set_undefined ();
3516 ASSERT_TRUE (r0
== int_range
<1> (INT (15), INT (40)));
3518 // [10,20] U [10,10] => [10,20].
3519 r0
= int_range
<1> (INT (10), INT (20));
3520 r1
= int_range
<1> (INT (10), INT (10));
3522 ASSERT_TRUE (r0
== int_range
<1> (INT (10), INT (20)));
3524 // [10,20] U [9,9] => [9,20].
3525 r0
= int_range
<1> (INT (10), INT (20));
3526 r1
= int_range
<1> (INT (9), INT (9));
3528 ASSERT_TRUE (r0
== int_range
<1> (INT (9), INT (20)));
3530 // [10,20] ^ [15,30] => [15,20].
3531 r0
= int_range
<1> (INT (10), INT (20));
3532 r1
= int_range
<1> (INT (15), INT (30));
3534 ASSERT_TRUE (r0
== int_range
<1> (INT (15), INT (20)));
3536 // Test the internal sanity of wide_int's wrt HWIs.
3537 ASSERT_TRUE (wi::max_value (TYPE_PRECISION (boolean_type_node
),
3538 TYPE_SIGN (boolean_type_node
))
3539 == wi::uhwi (1, TYPE_PRECISION (boolean_type_node
)));
3542 r0
= int_range
<1> (INT (0), INT (0));
3543 ASSERT_TRUE (r0
.zero_p ());
3545 // Test nonzero_p().
3546 r0
= int_range
<1> (INT (0), INT (0));
3548 ASSERT_TRUE (r0
.nonzero_p ());
3550 // test legacy interaction
3552 r0
= int_range
<1> (UINT (1), UINT (1), VR_ANTI_RANGE
);
3554 r1
= int_range
<1> (UINT (3), UINT (3), VR_ANTI_RANGE
);
3556 // vv = [0,0][2,2][4, MAX]
3557 int_range
<3> vv
= r0
;
3560 ASSERT_TRUE (vv
.contains_p (UINT (2)));
3561 ASSERT_TRUE (vv
.num_pairs () == 3);
3563 // create r0 as legacy [1,1]
3564 r0
= int_range
<1> (UINT (1), UINT (1));
3565 // And union it with [0,0][2,2][4,MAX] multi range
3567 // The result should be [0,2][4,MAX], or ~[3,3] but it must contain 2
3568 ASSERT_TRUE (r0
.contains_p (UINT (2)));
3572 range_tests_nonzero_bits ()
3574 int_range
<2> r0
, r1
;
3576 // Adding nonzero bits to a varying drops the varying.
3577 r0
.set_varying (integer_type_node
);
3578 r0
.set_nonzero_bits (255);
3579 ASSERT_TRUE (!r0
.varying_p ());
3580 // Dropping the nonzero bits brings us back to varying.
3581 r0
.set_nonzero_bits (-1);
3582 ASSERT_TRUE (r0
.varying_p ());
3584 // Test contains_p with nonzero bits.
3585 r0
.set_zero (integer_type_node
);
3586 ASSERT_TRUE (r0
.contains_p (INT (0)));
3587 ASSERT_FALSE (r0
.contains_p (INT (1)));
3588 r0
.set_nonzero_bits (0xfe);
3589 ASSERT_FALSE (r0
.contains_p (INT (0x100)));
3590 ASSERT_FALSE (r0
.contains_p (INT (0x3)));
3592 // Union of nonzero bits.
3593 r0
.set_varying (integer_type_node
);
3594 r0
.set_nonzero_bits (0xf0);
3595 r1
.set_varying (integer_type_node
);
3596 r1
.set_nonzero_bits (0xf);
3598 ASSERT_TRUE (r0
.get_nonzero_bits () == 0xff);
3600 // Union where the mask of nonzero bits is implicit from the range.
3601 r0
.set_varying (integer_type_node
);
3602 r0
.set_nonzero_bits (0xf00);
3603 r1
.set_zero (integer_type_node
); // nonzero mask is implicitly 0
3605 ASSERT_TRUE (r0
.get_nonzero_bits () == 0xf00);
3607 // Intersect of nonzero bits.
3608 r0
.set (INT (0), INT (255));
3609 r0
.set_nonzero_bits (0xfe);
3610 r1
.set_varying (integer_type_node
);
3611 r1
.set_nonzero_bits (0xf0);
3613 ASSERT_TRUE (r0
.get_nonzero_bits () == 0xf0);
3615 // Intersect where the mask of nonzero bits is implicit from the range.
3616 r0
.set_varying (integer_type_node
);
3617 r1
.set (INT (0), INT (255));
3619 ASSERT_TRUE (r0
.get_nonzero_bits () == 0xff);
3621 // The union of a mask of 0xff..ffff00 with a mask of 0xff spans the
3622 // entire domain, and makes the range a varying.
3623 r0
.set_varying (integer_type_node
);
3624 wide_int x
= wi::shwi (0xff, TYPE_PRECISION (integer_type_node
));
3625 x
= wi::bit_not (x
);
3626 r0
.set_nonzero_bits (x
); // 0xff..ff00
3627 r1
.set_varying (integer_type_node
);
3628 r1
.set_nonzero_bits (0xff);
3630 ASSERT_TRUE (r0
.varying_p ());
3633 // Build an frange from string endpoints.
3635 static inline frange
3636 frange_float (const char *lb
, const char *ub
, tree type
= float_type_node
)
3638 REAL_VALUE_TYPE min
, max
;
3639 gcc_assert (real_from_string (&min
, lb
) == 0);
3640 gcc_assert (real_from_string (&max
, ub
) == 0);
3641 return frange (type
, min
, max
);
3648 REAL_VALUE_TYPE q
, r
;
3650 // Equal ranges but with differing NAN bits are not equal.
3651 if (HONOR_NANS (float_type_node
))
3653 r1
= frange_float ("10", "12");
3661 // [10, 20] NAN ^ [30, 40] NAN = NAN.
3662 r0
= frange_float ("10", "20");
3663 r1
= frange_float ("30", "40");
3665 ASSERT_TRUE (r0
.known_isnan ());
3667 // [3,5] U [5,10] NAN = ... NAN
3668 r0
= frange_float ("3", "5");
3670 r1
= frange_float ("5", "10");
3672 ASSERT_TRUE (r0
.maybe_isnan ());
3675 // NAN ranges are not equal to each other.
3676 r0
.set_nan (float_type_node
);
3678 ASSERT_FALSE (r0
== r1
);
3679 ASSERT_FALSE (r0
== r0
);
3680 ASSERT_TRUE (r0
!= r0
);
3682 // [5,6] U NAN = [5,6] NAN.
3683 r0
= frange_float ("5", "6");
3685 r1
.set_nan (float_type_node
);
3687 real_from_string (&q
, "5");
3688 real_from_string (&r
, "6");
3689 ASSERT_TRUE (real_identical (&q
, &r0
.lower_bound ()));
3690 ASSERT_TRUE (real_identical (&r
, &r0
.upper_bound ()));
3691 ASSERT_TRUE (r0
.maybe_isnan ());
3694 r0
.set_nan (float_type_node
);
3695 r1
.set_nan (float_type_node
);
3697 ASSERT_TRUE (r0
.known_isnan ());
3699 // [INF, INF] NAN ^ NAN = NAN
3700 r0
.set_nan (float_type_node
);
3701 r1
= frange_float ("+Inf", "+Inf");
3702 if (!HONOR_NANS (float_type_node
))
3705 ASSERT_TRUE (r0
.known_isnan ());
3708 r0
.set_nan (float_type_node
);
3709 r1
.set_nan (float_type_node
);
3711 ASSERT_TRUE (r0
.known_isnan ());
3713 // +NAN ^ -NAN = UNDEFINED
3714 r0
.set_nan (float_type_node
, false);
3715 r1
.set_nan (float_type_node
, true);
3717 ASSERT_TRUE (r0
.undefined_p ());
3719 // VARYING ^ NAN = NAN.
3720 r0
.set_nan (float_type_node
);
3721 r1
.set_varying (float_type_node
);
3723 ASSERT_TRUE (r0
.known_isnan ());
3725 // [3,4] ^ NAN = UNDEFINED.
3726 r0
= frange_float ("3", "4");
3728 r1
.set_nan (float_type_node
);
3730 ASSERT_TRUE (r0
.undefined_p ());
3732 // [-3, 5] ^ NAN = UNDEFINED
3733 r0
= frange_float ("-3", "5");
3735 r1
.set_nan (float_type_node
);
3737 ASSERT_TRUE (r0
.undefined_p ());
3739 // Setting the NAN bit to yes does not make us a known NAN.
3740 r0
.set_varying (float_type_node
);
3742 ASSERT_FALSE (r0
.known_isnan ());
3744 // NAN is in a VARYING.
3745 r0
.set_varying (float_type_node
);
3746 real_nan (&r
, "", 1, TYPE_MODE (float_type_node
));
3747 tree nan
= build_real (float_type_node
, r
);
3748 ASSERT_TRUE (r0
.contains_p (nan
));
3750 // -NAN is in a VARYING.
3751 r0
.set_varying (float_type_node
);
3752 q
= real_value_negate (&r
);
3753 tree neg_nan
= build_real (float_type_node
, q
);
3754 ASSERT_TRUE (r0
.contains_p (neg_nan
));
3756 // Clearing the NAN on a [] NAN is the empty set.
3757 r0
.set_nan (float_type_node
);
3759 ASSERT_TRUE (r0
.undefined_p ());
3763 range_tests_signed_zeros ()
3765 tree zero
= build_zero_cst (float_type_node
);
3766 tree neg_zero
= fold_build1 (NEGATE_EXPR
, float_type_node
, zero
);
3767 REAL_VALUE_TYPE q
, r
;
3771 // [0,0] contains [0,0] but not [-0,-0] and vice versa.
3772 r0
= frange (zero
, zero
);
3773 r1
= frange (neg_zero
, neg_zero
);
3774 ASSERT_TRUE (r0
.contains_p (zero
));
3775 ASSERT_TRUE (!r0
.contains_p (neg_zero
));
3776 ASSERT_TRUE (r1
.contains_p (neg_zero
));
3777 ASSERT_TRUE (!r1
.contains_p (zero
));
3779 // Test contains_p() when we know the sign of the zero.
3780 r0
= frange (zero
, zero
);
3781 ASSERT_TRUE (r0
.contains_p (zero
));
3782 ASSERT_FALSE (r0
.contains_p (neg_zero
));
3783 r0
= frange (neg_zero
, neg_zero
);
3784 ASSERT_TRUE (r0
.contains_p (neg_zero
));
3785 ASSERT_FALSE (r0
.contains_p (zero
));
3787 // The intersection of zeros that differ in sign is a NAN (or
3788 // undefined if not honoring NANs).
3789 r0
= frange (neg_zero
, neg_zero
);
3790 r1
= frange (zero
, zero
);
3792 if (HONOR_NANS (float_type_node
))
3793 ASSERT_TRUE (r0
.known_isnan ());
3795 ASSERT_TRUE (r0
.undefined_p ());
3797 // The union of zeros that differ in sign is a zero with unknown sign.
3798 r0
= frange (zero
, zero
);
3799 r1
= frange (neg_zero
, neg_zero
);
3801 ASSERT_TRUE (r0
.zero_p () && !r0
.signbit_p (signbit
));
3803 // [-0, +0] has an unknown sign.
3804 r0
= frange (neg_zero
, zero
);
3805 ASSERT_TRUE (r0
.zero_p () && !r0
.signbit_p (signbit
));
3807 // [-0, +0] ^ [0, 0] is [0, 0]
3808 r0
= frange (neg_zero
, zero
);
3809 r1
= frange (zero
, zero
);
3811 ASSERT_TRUE (r0
.zero_p ());
3813 // NAN U [5,6] should be [5,6] NAN.
3814 r0
.set_nan (float_type_node
);
3815 r1
= frange_float ("5", "6");
3818 real_from_string (&q
, "5");
3819 real_from_string (&r
, "6");
3820 ASSERT_TRUE (real_identical (&q
, &r0
.lower_bound ()));
3821 ASSERT_TRUE (real_identical (&r
, &r0
.upper_bound ()));
3822 ASSERT_TRUE (!r0
.signbit_p (signbit
));
3823 ASSERT_TRUE (r0
.maybe_isnan ());
3825 r0
= frange_float ("+0", "5");
3827 ASSERT_TRUE (r0
.signbit_p (signbit
) && !signbit
);
3829 r0
= frange_float ("-0", "5");
3831 ASSERT_TRUE (!r0
.signbit_p (signbit
));
3833 r0
= frange_float ("-0", "10");
3834 r1
= frange_float ("0", "5");
3836 ASSERT_TRUE (real_iszero (&r0
.lower_bound (), false));
3838 r0
= frange_float ("-0", "5");
3839 r1
= frange_float ("0", "5");
3841 ASSERT_TRUE (real_iszero (&r0
.lower_bound (), true));
3843 r0
= frange_float ("-5", "-0");
3845 r1
= frange_float ("0", "0");
3848 ASSERT_TRUE (r0
.known_isnan ());
3850 r0
.set_nonnegative (float_type_node
);
3851 ASSERT_TRUE (r0
.signbit_p (signbit
) && !signbit
);
3852 if (HONOR_NANS (float_type_node
))
3853 ASSERT_TRUE (r0
.maybe_isnan ());
3857 range_tests_signbit ()
3862 // Negative numbers should have the SIGNBIT set.
3863 r0
= frange_float ("-5", "-1");
3865 ASSERT_TRUE (r0
.signbit_p (signbit
) && signbit
);
3866 // Positive numbers should have the SIGNBIT clear.
3867 r0
= frange_float ("1", "10");
3869 ASSERT_TRUE (r0
.signbit_p (signbit
) && !signbit
);
3870 // Numbers containing zero should have an unknown SIGNBIT.
3871 r0
= frange_float ("0", "10");
3873 ASSERT_TRUE (r0
.signbit_p (signbit
) && !signbit
);
3874 // Numbers spanning both positive and negative should have an
3876 r0
= frange_float ("-10", "10");
3878 ASSERT_TRUE (!r0
.signbit_p (signbit
));
3879 r0
.set_varying (float_type_node
);
3880 ASSERT_TRUE (!r0
.signbit_p (signbit
));
3884 range_tests_floats ()
3889 range_tests_signbit ();
3891 if (HONOR_SIGNED_ZEROS (float_type_node
))
3892 range_tests_signed_zeros ();
3894 // A range of [-INF,+INF] is actually VARYING if no other properties
3896 r0
= frange_float ("-Inf", "+Inf");
3897 if (r0
.maybe_isnan ())
3898 ASSERT_TRUE (r0
.varying_p ());
3899 // ...unless it has some special property...
3901 ASSERT_FALSE (r0
.varying_p ());
3903 // For most architectures, where float and double are different
3904 // sizes, having the same endpoints does not necessarily mean the
3905 // ranges are equal.
3906 if (!types_compatible_p (float_type_node
, double_type_node
))
3908 r0
= frange_float ("3.0", "3.0", float_type_node
);
3909 r1
= frange_float ("3.0", "3.0", double_type_node
);
3913 // [3,5] U [10,12] = [3,12].
3914 r0
= frange_float ("3", "5");
3915 r1
= frange_float ("10", "12");
3917 ASSERT_EQ (r0
, frange_float ("3", "12"));
3919 // [5,10] U [4,8] = [4,10]
3920 r0
= frange_float ("5", "10");
3921 r1
= frange_float ("4", "8");
3923 ASSERT_EQ (r0
, frange_float ("4", "10"));
3925 // [3,5] U [4,10] = [3,10]
3926 r0
= frange_float ("3", "5");
3927 r1
= frange_float ("4", "10");
3929 ASSERT_EQ (r0
, frange_float ("3", "10"));
3931 // [4,10] U [5,11] = [4,11]
3932 r0
= frange_float ("4", "10");
3933 r1
= frange_float ("5", "11");
3935 ASSERT_EQ (r0
, frange_float ("4", "11"));
3937 // [3,12] ^ [10,12] = [10,12].
3938 r0
= frange_float ("3", "12");
3939 r1
= frange_float ("10", "12");
3941 ASSERT_EQ (r0
, frange_float ("10", "12"));
3943 // [10,12] ^ [11,11] = [11,11]
3944 r0
= frange_float ("10", "12");
3945 r1
= frange_float ("11", "11");
3947 ASSERT_EQ (r0
, frange_float ("11", "11"));
3949 // [10,20] ^ [5,15] = [10,15]
3950 r0
= frange_float ("10", "20");
3951 r1
= frange_float ("5", "15");
3953 ASSERT_EQ (r0
, frange_float ("10", "15"));
3955 // [10,20] ^ [15,25] = [15,20]
3956 r0
= frange_float ("10", "20");
3957 r1
= frange_float ("15", "25");
3959 ASSERT_EQ (r0
, frange_float ("15", "20"));
3961 // [10,20] NAN ^ [21,25] NAN = [NAN]
3962 r0
= frange_float ("10", "20");
3964 r1
= frange_float ("21", "25");
3967 ASSERT_TRUE (r0
.known_isnan ());
3969 // [10,20] ^ [21,25] = []
3970 r0
= frange_float ("10", "20");
3972 r1
= frange_float ("21", "25");
3975 ASSERT_TRUE (r0
.undefined_p ());
3981 range_tests_legacy ();
3982 range_tests_irange3 ();
3983 range_tests_int_range_max ();
3984 range_tests_strict_enum ();
3985 range_tests_nonzero_bits ();
3986 range_tests_floats ();
3987 range_tests_misc ();
3990 } // namespace selftest
3992 #endif // CHECKING_P