1 /* Support routines for value ranges.
2 Copyright (C) 2019-2023 Free Software Foundation, Inc.
3 Major hacks by Aldy Hernandez <aldyh@redhat.com> and
4 Andrew MacLeod <amacleod@redhat.com>.
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify
9 it under the terms of the GNU General Public License as published by
10 the Free Software Foundation; either version 3, or (at your option)
13 GCC is distributed in the hope that it will be useful,
14 but WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 GNU General Public License for more details.
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
24 #include "coretypes.h"
29 #include "tree-pretty-print.h"
30 #include "value-range-pretty-print.h"
31 #include "fold-const.h"
32 #include "gimple-range.h"
35 irange::accept (const vrange_visitor
&v
) const
41 unsupported_range::accept (const vrange_visitor
&v
) const
46 // Convenience function only available for integers and pointers.
49 Value_Range::lower_bound () const
51 if (is_a
<irange
> (*m_vrange
))
52 return as_a
<irange
> (*m_vrange
).lower_bound ();
56 // Convenience function only available for integers and pointers.
59 Value_Range::upper_bound () const
61 if (is_a
<irange
> (*m_vrange
))
62 return as_a
<irange
> (*m_vrange
).upper_bound ();
67 Value_Range::dump (FILE *out
) const
72 fprintf (out
, "NULL");
76 debug (const Value_Range
&r
)
79 fprintf (stderr
, "\n");
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 machine_mode mode
= TYPE_MODE (type ());
270 // Flush [x, -DENORMAL] to [x, -0.0].
271 if (real_isdenormal (&m_max
, mode
) && real_isneg (&m_max
))
274 if (HONOR_SIGNED_ZEROS (m_type
))
277 // Flush [+DENORMAL, x] to [+0.0, x].
278 if (real_isdenormal (&m_min
, mode
) && !real_isneg (&m_min
))
282 // Setter for franges.
285 frange::set (tree type
,
286 const REAL_VALUE_TYPE
&min
, const REAL_VALUE_TYPE
&max
,
287 const nan_state
&nan
, value_range_kind kind
)
305 if (real_isnan (&min
) || real_isnan (&max
))
307 gcc_checking_assert (real_identical (&min
, &max
));
308 bool sign
= real_isneg (&min
);
309 set_nan (type
, sign
);
317 if (HONOR_NANS (m_type
))
319 m_pos_nan
= nan
.pos_p ();
320 m_neg_nan
= nan
.neg_p ();
328 if (!MODE_HAS_SIGNED_ZEROS (TYPE_MODE (m_type
)))
330 if (real_iszero (&m_min
, 1))
332 if (real_iszero (&m_max
, 1))
335 else if (!HONOR_SIGNED_ZEROS (m_type
))
337 if (real_iszero (&m_max
, 1))
339 if (real_iszero (&m_min
, 0))
343 // For -ffinite-math-only we can drop ranges outside the
344 // representable numbers to min/max for the type.
345 if (!HONOR_INFINITIES (m_type
))
347 REAL_VALUE_TYPE min_repr
= frange_val_min (m_type
);
348 REAL_VALUE_TYPE max_repr
= frange_val_max (m_type
);
349 if (real_less (&m_min
, &min_repr
))
351 else if (real_less (&max_repr
, &m_min
))
353 if (real_less (&max_repr
, &m_max
))
355 else if (real_less (&m_max
, &min_repr
))
359 // Check for swapped ranges.
360 gcc_checking_assert (real_compare (LE_EXPR
, &min
, &max
));
364 flush_denormals_to_zero ();
370 // Setter for an frange defaulting the NAN possibility to +-NAN when
374 frange::set (tree type
,
375 const REAL_VALUE_TYPE
&min
, const REAL_VALUE_TYPE
&max
,
376 value_range_kind kind
)
379 set (type
, min
, max
, nan
, kind
);
383 frange::set (tree min
, tree max
, value_range_kind kind
)
385 set (TREE_TYPE (min
),
386 *TREE_REAL_CST_PTR (min
), *TREE_REAL_CST_PTR (max
), kind
);
389 // Normalize range to VARYING or UNDEFINED, or vice versa. Return
390 // TRUE if anything changed.
392 // A range with no known properties can be dropped to VARYING.
393 // Similarly, a VARYING with any properties should be dropped to a
394 // VR_RANGE. Normalizing ranges upon changing them ensures there is
395 // only one representation for a given range.
398 frange::normalize_kind ()
400 if (m_kind
== VR_RANGE
401 && frange_val_is_min (m_min
, m_type
)
402 && frange_val_is_max (m_max
, m_type
))
404 if (!HONOR_NANS (m_type
) || (m_pos_nan
&& m_neg_nan
))
406 set_varying (m_type
);
410 else if (m_kind
== VR_VARYING
)
412 if (HONOR_NANS (m_type
) && (!m_pos_nan
|| !m_neg_nan
))
415 m_min
= frange_val_min (m_type
);
416 m_max
= frange_val_max (m_type
);
420 else if (m_kind
== VR_NAN
&& !m_pos_nan
&& !m_neg_nan
)
425 // Union or intersect the zero endpoints of two ranges. For example:
426 // [-0, x] U [+0, x] => [-0, x]
427 // [ x, -0] U [ x, +0] => [ x, +0]
428 // [-0, x] ^ [+0, x] => [+0, x]
429 // [ x, -0] ^ [ x, +0] => [ x, -0]
431 // UNION_P is true when performing a union, or false when intersecting.
434 frange::combine_zeros (const frange
&r
, bool union_p
)
436 gcc_checking_assert (!undefined_p () && !known_isnan ());
438 bool changed
= false;
439 if (real_iszero (&m_min
) && real_iszero (&r
.m_min
)
440 && real_isneg (&m_min
) != real_isneg (&r
.m_min
))
442 m_min
.sign
= union_p
;
445 if (real_iszero (&m_max
) && real_iszero (&r
.m_max
)
446 && real_isneg (&m_max
) != real_isneg (&r
.m_max
))
448 m_max
.sign
= !union_p
;
451 // If the signs are swapped, the resulting range is empty.
452 if (m_min
.sign
== 0 && m_max
.sign
== 1)
463 // Union two ranges when one is known to be a NAN.
466 frange::union_nans (const frange
&r
)
468 gcc_checking_assert (known_isnan () || r
.known_isnan ());
476 m_pos_nan
|= r
.m_pos_nan
;
477 m_neg_nan
|= r
.m_neg_nan
;
485 frange::union_ (const vrange
&v
)
487 const frange
&r
= as_a
<frange
> (v
);
489 if (r
.undefined_p () || varying_p ())
491 if (undefined_p () || r
.varying_p ())
498 if (known_isnan () || r
.known_isnan ())
499 return union_nans (r
);
500 bool changed
= false;
501 if (m_pos_nan
!= r
.m_pos_nan
|| m_neg_nan
!= r
.m_neg_nan
)
503 m_pos_nan
|= r
.m_pos_nan
;
504 m_neg_nan
|= r
.m_neg_nan
;
508 // Combine endpoints.
509 if (real_less (&r
.m_min
, &m_min
))
514 if (real_less (&m_max
, &r
.m_max
))
520 if (HONOR_SIGNED_ZEROS (m_type
))
521 changed
|= combine_zeros (r
, true);
523 changed
|= normalize_kind ();
529 // Intersect two ranges when one is known to be a NAN.
532 frange::intersect_nans (const frange
&r
)
534 gcc_checking_assert (known_isnan () || r
.known_isnan ());
536 m_pos_nan
&= r
.m_pos_nan
;
537 m_neg_nan
&= r
.m_neg_nan
;
548 frange::intersect (const vrange
&v
)
550 const frange
&r
= as_a
<frange
> (v
);
552 if (undefined_p () || r
.varying_p ())
554 if (r
.undefined_p ())
566 if (known_isnan () || r
.known_isnan ())
567 return intersect_nans (r
);
568 bool changed
= false;
569 if (m_pos_nan
!= r
.m_pos_nan
|| m_neg_nan
!= r
.m_neg_nan
)
571 m_pos_nan
&= r
.m_pos_nan
;
572 m_neg_nan
&= r
.m_neg_nan
;
576 // Combine endpoints.
577 if (real_less (&m_min
, &r
.m_min
))
582 if (real_less (&r
.m_max
, &m_max
))
587 // If the endpoints are swapped, the resulting range is empty.
588 if (real_less (&m_max
, &m_min
))
599 if (HONOR_SIGNED_ZEROS (m_type
))
600 changed
|= combine_zeros (r
, false);
602 changed
|= normalize_kind ();
609 frange::operator= (const frange
&src
)
615 m_pos_nan
= src
.m_pos_nan
;
616 m_neg_nan
= src
.m_neg_nan
;
624 frange::operator== (const frange
&src
) const
626 if (m_kind
== src
.m_kind
)
632 return types_compatible_p (m_type
, src
.m_type
);
634 if (known_isnan () || src
.known_isnan ())
637 return (real_identical (&m_min
, &src
.m_min
)
638 && real_identical (&m_max
, &src
.m_max
)
639 && m_pos_nan
== src
.m_pos_nan
640 && m_neg_nan
== src
.m_neg_nan
641 && types_compatible_p (m_type
, src
.m_type
));
646 // Return TRUE if range contains the TREE_REAL_CST_PTR in CST.
649 frange::contains_p (tree cst
) const
651 gcc_checking_assert (m_kind
!= VR_ANTI_RANGE
);
652 const REAL_VALUE_TYPE
*rv
= TREE_REAL_CST_PTR (cst
);
663 if (!m_pos_nan
&& !m_neg_nan
)
665 // Both +NAN and -NAN are present.
666 if (m_pos_nan
&& m_neg_nan
)
668 return m_neg_nan
== rv
->sign
;
673 if (real_compare (GE_EXPR
, rv
, &m_min
) && real_compare (LE_EXPR
, rv
, &m_max
))
675 // Make sure the signs are equal for signed zeros.
676 if (HONOR_SIGNED_ZEROS (m_type
) && real_iszero (rv
))
677 return rv
->sign
== m_min
.sign
|| rv
->sign
== m_max
.sign
;
683 // If range is a singleton, place it in RESULT and return TRUE. If
684 // RESULT is NULL, just return TRUE.
686 // A NAN can never be a singleton.
689 frange::singleton_p (tree
*result
) const
691 if (m_kind
== VR_RANGE
&& real_identical (&m_min
, &m_max
))
693 // Return false for any singleton that may be a NAN.
694 if (HONOR_NANS (m_type
) && maybe_isnan ())
697 if (MODE_COMPOSITE_P (TYPE_MODE (m_type
)))
699 // For IBM long doubles, if the value is +-Inf or is exactly
700 // representable in double, the other double could be +0.0
701 // or -0.0. Since this means there is more than one way to
702 // represent a value, return false to avoid propagating it.
703 // See libgcc/config/rs6000/ibm-ldouble-format for details.
704 if (real_isinf (&m_min
))
707 real_convert (&r
, DFmode
, &m_min
);
708 if (real_identical (&r
, &m_min
))
713 *result
= build_real (m_type
, m_min
);
720 frange::supports_type_p (const_tree type
) const
722 return supports_p (type
);
726 frange::verify_range ()
729 gcc_checking_assert (HONOR_NANS (m_type
) || !maybe_isnan ());
733 gcc_checking_assert (!m_type
);
736 gcc_checking_assert (m_type
);
737 gcc_checking_assert (frange_val_is_min (m_min
, m_type
));
738 gcc_checking_assert (frange_val_is_max (m_max
, m_type
));
739 if (HONOR_NANS (m_type
))
740 gcc_checking_assert (m_pos_nan
&& m_neg_nan
);
742 gcc_checking_assert (!m_pos_nan
&& !m_neg_nan
);
745 gcc_checking_assert (m_type
);
748 gcc_checking_assert (m_type
);
749 gcc_checking_assert (m_pos_nan
|| m_neg_nan
);
755 // NANs cannot appear in the endpoints of a range.
756 gcc_checking_assert (!real_isnan (&m_min
) && !real_isnan (&m_max
));
758 // Make sure we don't have swapped ranges.
759 gcc_checking_assert (!real_less (&m_max
, &m_min
));
761 // [ +0.0, -0.0 ] is nonsensical.
762 gcc_checking_assert (!(real_iszero (&m_min
, 0) && real_iszero (&m_max
, 1)));
764 // If all the properties are clear, we better not span the entire
765 // domain, because that would make us varying.
766 if (m_pos_nan
&& m_neg_nan
)
767 gcc_checking_assert (!frange_val_is_min (m_min
, m_type
)
768 || !frange_val_is_max (m_max
, m_type
));
771 // We can't do much with nonzeros yet.
773 frange::set_nonzero (tree type
)
778 // We can't do much with nonzeros yet.
780 frange::nonzero_p () const
785 // Set range to [+0.0, +0.0] if honoring signed zeros, or [0.0, 0.0]
789 frange::set_zero (tree type
)
791 if (HONOR_SIGNED_ZEROS (type
))
793 REAL_VALUE_TYPE dconstm0
= dconst0
;
795 set (type
, dconstm0
, dconst0
);
799 set (type
, dconst0
, dconst0
);
802 // Return TRUE for any zero regardless of sign.
805 frange::zero_p () const
807 return (m_kind
== VR_RANGE
808 && real_iszero (&m_min
)
809 && real_iszero (&m_max
));
812 // Set the range to non-negative numbers, that is [+0.0, +INF].
814 // The NAN in the resulting range (if HONOR_NANS) has a varying sign
815 // as there are no guarantees in IEEE 754 wrt to the sign of a NAN,
816 // except for copy, abs, and copysign. It is the responsibility of
817 // the caller to set the NAN's sign if desired.
820 frange::set_nonnegative (tree type
)
822 set (type
, dconst0
, frange_val_max (type
));
825 // Here we copy between any two irange's. The ranges can be legacy or
826 // multi-ranges, and copying between any combination works correctly.
829 irange::operator= (const irange
&src
)
831 if (legacy_mode_p ())
833 copy_to_legacy (src
);
836 if (src
.legacy_mode_p ())
838 copy_legacy_to_multi_range (src
);
843 unsigned lim
= src
.m_num_ranges
;
844 if (lim
> m_max_ranges
)
847 for (x
= 0; x
< lim
* 2; ++x
)
848 m_base
[x
] = src
.m_base
[x
];
850 // If the range didn't fit, the last range should cover the rest.
851 if (lim
!= src
.m_num_ranges
)
852 m_base
[x
- 1] = src
.m_base
[src
.m_num_ranges
* 2 - 1];
856 m_nonzero_mask
= src
.m_nonzero_mask
;
862 // Return TRUE if range is a multi-range that can be represented as a
866 irange::maybe_anti_range () const
868 tree ttype
= type ();
869 unsigned int precision
= TYPE_PRECISION (ttype
);
870 signop sign
= TYPE_SIGN (ttype
);
871 return (num_pairs () > 1
873 && lower_bound () == wi::min_value (precision
, sign
)
874 && upper_bound () == wi::max_value (precision
, sign
));
878 irange::copy_legacy_to_multi_range (const irange
&src
)
880 gcc_checking_assert (src
.legacy_mode_p ());
881 gcc_checking_assert (!legacy_mode_p ());
882 if (src
.undefined_p ())
884 else if (src
.varying_p ())
885 set_varying (src
.type ());
888 if (range_has_numeric_bounds_p (&src
))
889 set (src
.min (), src
.max (), src
.kind ());
892 value_range
cst (src
);
893 cst
.normalize_symbolics ();
894 gcc_checking_assert (cst
.varying_p () || cst
.kind () == VR_RANGE
);
895 set (cst
.min (), cst
.max ());
900 // Copy any type of irange into a legacy.
903 irange::copy_to_legacy (const irange
&src
)
905 gcc_checking_assert (legacy_mode_p ());
906 // Handle legacy to legacy and other things that are easy to copy.
907 if (src
.legacy_mode_p () || src
.varying_p () || src
.undefined_p ())
909 m_num_ranges
= src
.m_num_ranges
;
910 m_base
[0] = src
.m_base
[0];
911 m_base
[1] = src
.m_base
[1];
913 m_nonzero_mask
= src
.m_nonzero_mask
;
916 // Copy multi-range to legacy.
917 if (src
.maybe_anti_range ())
919 int_range
<3> r (src
);
921 // Use tree variants to save on tree -> wi -> tree conversions.
922 set (r
.tree_lower_bound (0), r
.tree_upper_bound (0), VR_ANTI_RANGE
);
925 set (src
.tree_lower_bound (), src
.tree_upper_bound ());
928 // Swap MIN/MAX if they are out of order and adjust KIND appropriately.
931 swap_out_of_order_endpoints (tree
&min
, tree
&max
, value_range_kind
&kind
)
933 gcc_checking_assert (kind
!= VR_UNDEFINED
);
934 if (kind
== VR_VARYING
)
936 /* Wrong order for min and max, to swap them and the VR type we need
938 if (tree_int_cst_lt (max
, min
))
942 /* For one bit precision if max < min, then the swapped
943 range covers all values, so for VR_RANGE it is varying and
944 for VR_ANTI_RANGE empty range, so drop to varying as well. */
945 if (TYPE_PRECISION (TREE_TYPE (min
)) == 1)
951 one
= build_int_cst (TREE_TYPE (min
), 1);
952 tmp
= int_const_binop (PLUS_EXPR
, max
, one
);
953 max
= int_const_binop (MINUS_EXPR
, min
, one
);
956 /* There's one corner case, if we had [C+1, C] before we now have
957 that again. But this represents an empty value range, so drop
958 to varying in this case. */
959 if (tree_int_cst_lt (max
, min
))
964 kind
= kind
== VR_RANGE
? VR_ANTI_RANGE
: VR_RANGE
;
969 irange::irange_set (tree min
, tree max
)
971 gcc_checking_assert (!POLY_INT_CST_P (min
));
972 gcc_checking_assert (!POLY_INT_CST_P (max
));
978 m_nonzero_mask
= NULL
;
986 irange::irange_set_1bit_anti_range (tree min
, tree max
)
988 tree type
= TREE_TYPE (min
);
989 gcc_checking_assert (TYPE_PRECISION (type
) == 1);
991 if (operand_equal_p (min
, max
))
993 // Since these are 1-bit quantities, they can only be [MIN,MIN]
995 if (vrp_val_is_min (min
))
996 min
= max
= vrp_val_max (type
);
998 min
= max
= vrp_val_min (type
);
1003 // The only alternative is [MIN,MAX], which is the empty range.
1004 gcc_checking_assert (vrp_val_is_min (min
));
1005 gcc_checking_assert (vrp_val_is_max (max
));
1013 irange::irange_set_anti_range (tree min
, tree max
)
1015 gcc_checking_assert (!POLY_INT_CST_P (min
));
1016 gcc_checking_assert (!POLY_INT_CST_P (max
));
1018 if (TYPE_PRECISION (TREE_TYPE (min
)) == 1)
1020 irange_set_1bit_anti_range (min
, max
);
1024 // set an anti-range
1025 tree type
= TREE_TYPE (min
);
1026 signop sign
= TYPE_SIGN (type
);
1027 int_range
<2> type_range (type
);
1028 // Calculate INVERSE([I,J]) as [-MIN, I-1][J+1, +MAX].
1030 wi::overflow_type ovf
;
1032 wide_int w_min
= wi::to_wide (min
);
1033 if (wi::ne_p (w_min
, type_range
.lower_bound ()))
1035 wide_int lim1
= wi::sub (w_min
, 1, sign
, &ovf
);
1036 gcc_checking_assert (ovf
!= wi::OVF_OVERFLOW
);
1037 m_base
[0] = type_range
.tree_lower_bound (0);
1038 m_base
[1] = wide_int_to_tree (type
, lim1
);
1041 wide_int w_max
= wi::to_wide (max
);
1042 if (wi::ne_p (w_max
, type_range
.upper_bound ()))
1044 wide_int lim2
= wi::add (w_max
, 1, sign
, &ovf
);
1045 gcc_checking_assert (ovf
!= wi::OVF_OVERFLOW
);
1046 m_base
[m_num_ranges
* 2] = wide_int_to_tree (type
, lim2
);
1047 m_base
[m_num_ranges
* 2 + 1] = type_range
.tree_upper_bound (0);
1052 m_nonzero_mask
= NULL
;
1059 /* Set value range to the canonical form of {VRTYPE, MIN, MAX, EQUIV}.
1060 This means adjusting VRTYPE, MIN and MAX representing the case of a
1061 wrapping range with MAX < MIN covering [MIN, type_max] U [type_min, MAX]
1062 as anti-rage ~[MAX+1, MIN-1]. Likewise for wrapping anti-ranges.
1063 In corner cases where MAX+1 or MIN-1 wraps this will fall back
1065 This routine exists to ease canonicalization in the case where we
1066 extract ranges from var + CST op limit. */
1069 irange::set (tree min
, tree max
, value_range_kind kind
)
1071 if (kind
== VR_UNDEFINED
)
1073 irange::set_undefined ();
1077 if (kind
== VR_VARYING
1078 || POLY_INT_CST_P (min
)
1079 || POLY_INT_CST_P (max
))
1081 set_varying (TREE_TYPE (min
));
1085 if (TREE_OVERFLOW_P (min
))
1086 min
= drop_tree_overflow (min
);
1087 if (TREE_OVERFLOW_P (max
))
1088 max
= drop_tree_overflow (max
);
1090 if (!legacy_mode_p ())
1092 if (kind
== VR_RANGE
)
1093 irange_set (min
, max
);
1096 gcc_checking_assert (kind
== VR_ANTI_RANGE
);
1097 irange_set_anti_range (min
, max
);
1101 // Nothing to canonicalize for symbolic ranges.
1102 if (TREE_CODE (min
) != INTEGER_CST
1103 || TREE_CODE (max
) != INTEGER_CST
)
1109 m_nonzero_mask
= NULL
;
1113 swap_out_of_order_endpoints (min
, max
, kind
);
1114 if (kind
== VR_VARYING
)
1116 set_varying (TREE_TYPE (min
));
1120 // Anti-ranges that can be represented as ranges should be so.
1121 if (kind
== VR_ANTI_RANGE
)
1123 bool is_min
= vrp_val_is_min (min
);
1124 bool is_max
= vrp_val_is_max (max
);
1126 if (is_min
&& is_max
)
1128 // Fall through. This will either be normalized as
1129 // VR_UNDEFINED if the anti-range spans the entire
1130 // precision, or it will remain an VR_ANTI_RANGE in the case
1131 // of an -fstrict-enum where [MIN,MAX] is less than the span
1132 // of underlying precision.
1134 else if (TYPE_PRECISION (TREE_TYPE (min
)) == 1)
1136 irange_set_1bit_anti_range (min
, max
);
1141 tree one
= build_int_cst (TREE_TYPE (max
), 1);
1142 min
= int_const_binop (PLUS_EXPR
, max
, one
);
1143 max
= vrp_val_max (TREE_TYPE (max
));
1148 tree one
= build_int_cst (TREE_TYPE (min
), 1);
1149 max
= int_const_binop (MINUS_EXPR
, min
, one
);
1150 min
= vrp_val_min (TREE_TYPE (min
));
1159 m_nonzero_mask
= NULL
;
1165 // Check the validity of the range.
1168 irange::verify_range ()
1170 gcc_checking_assert (m_discriminator
== VR_IRANGE
);
1171 if (m_kind
== VR_UNDEFINED
)
1173 gcc_checking_assert (m_num_ranges
== 0);
1176 if (m_kind
== VR_VARYING
)
1178 gcc_checking_assert (!m_nonzero_mask
1179 || wi::to_wide (m_nonzero_mask
) == -1);
1180 gcc_checking_assert (m_num_ranges
== 1);
1181 gcc_checking_assert (varying_compatible_p ());
1184 if (!legacy_mode_p ())
1186 gcc_checking_assert (m_num_ranges
!= 0);
1187 gcc_checking_assert (!varying_compatible_p ());
1188 for (unsigned i
= 0; i
< m_num_ranges
; ++i
)
1190 tree lb
= tree_lower_bound (i
);
1191 tree ub
= tree_upper_bound (i
);
1192 int c
= compare_values (lb
, ub
);
1193 gcc_checking_assert (c
== 0 || c
== -1);
1197 if (m_kind
== VR_RANGE
|| m_kind
== VR_ANTI_RANGE
)
1199 gcc_checking_assert (m_num_ranges
== 1);
1200 int cmp
= compare_values (tree_lower_bound (0), tree_upper_bound (0));
1201 gcc_checking_assert (cmp
== 0 || cmp
== -1 || cmp
== -2);
1205 // Return the lower bound for a sub-range. PAIR is the sub-range in
1209 irange::legacy_lower_bound (unsigned pair
) const
1211 gcc_checking_assert (legacy_mode_p ());
1214 value_range
numeric_range (*this);
1215 numeric_range
.normalize_symbolics ();
1216 return numeric_range
.legacy_lower_bound (pair
);
1218 gcc_checking_assert (m_num_ranges
> 0);
1219 gcc_checking_assert (pair
+ 1 <= num_pairs ());
1220 if (m_kind
== VR_ANTI_RANGE
)
1222 tree typ
= type (), t
;
1223 if (pair
== 1 || vrp_val_is_min (min ()))
1224 t
= wide_int_to_tree (typ
, wi::to_wide (max ()) + 1);
1226 t
= vrp_val_min (typ
);
1227 return wi::to_wide (t
);
1229 return wi::to_wide (tree_lower_bound (pair
));
1232 // Return the upper bound for a sub-range. PAIR is the sub-range in
1236 irange::legacy_upper_bound (unsigned pair
) const
1238 gcc_checking_assert (legacy_mode_p ());
1241 value_range
numeric_range (*this);
1242 numeric_range
.normalize_symbolics ();
1243 return numeric_range
.legacy_upper_bound (pair
);
1245 gcc_checking_assert (m_num_ranges
> 0);
1246 gcc_checking_assert (pair
+ 1 <= num_pairs ());
1247 if (m_kind
== VR_ANTI_RANGE
)
1249 tree typ
= type (), t
;
1250 if (pair
== 1 || vrp_val_is_min (min ()))
1251 t
= vrp_val_max (typ
);
1253 t
= wide_int_to_tree (typ
, wi::to_wide (min ()) - 1);
1254 return wi::to_wide (t
);
1256 return wi::to_wide (tree_upper_bound (pair
));
1260 irange::legacy_equal_p (const irange
&other
) const
1262 gcc_checking_assert (legacy_mode_p () && other
.legacy_mode_p ());
1264 if (m_kind
!= other
.m_kind
)
1266 if (m_kind
== VR_UNDEFINED
)
1268 if (m_kind
== VR_VARYING
)
1269 return range_compatible_p (type (), other
.type ());
1270 return (vrp_operand_equal_p (tree_lower_bound (0),
1271 other
.tree_lower_bound (0))
1272 && vrp_operand_equal_p (tree_upper_bound (0),
1273 other
.tree_upper_bound (0))
1274 && (widest_int::from (get_nonzero_bits (),
1275 TYPE_SIGN (type ()))
1276 == widest_int::from (other
.get_nonzero_bits (),
1277 TYPE_SIGN (other
.type ()))));
1281 irange::operator== (const irange
&other
) const
1283 if (legacy_mode_p ())
1285 if (other
.legacy_mode_p ())
1286 return legacy_equal_p (other
);
1287 value_range
tmp (other
);
1288 return legacy_equal_p (tmp
);
1290 if (other
.legacy_mode_p ())
1292 value_range
tmp2 (*this);
1293 return tmp2
.legacy_equal_p (other
);
1296 if (m_num_ranges
!= other
.m_num_ranges
)
1299 if (m_num_ranges
== 0)
1302 for (unsigned i
= 0; i
< m_num_ranges
; ++i
)
1304 tree lb
= tree_lower_bound (i
);
1305 tree ub
= tree_upper_bound (i
);
1306 tree lb_other
= other
.tree_lower_bound (i
);
1307 tree ub_other
= other
.tree_upper_bound (i
);
1308 if (!operand_equal_p (lb
, lb_other
, 0)
1309 || !operand_equal_p (ub
, ub_other
, 0))
1312 widest_int nz1
= widest_int::from (get_nonzero_bits (),
1313 TYPE_SIGN (type ()));
1314 widest_int nz2
= widest_int::from (other
.get_nonzero_bits (),
1315 TYPE_SIGN (other
.type ()));
1319 /* Return TRUE if this is a symbolic range. */
1322 irange::symbolic_p () const
1324 return (m_num_ranges
> 0
1325 && (!is_gimple_min_invariant (min ())
1326 || !is_gimple_min_invariant (max ())));
1329 /* Return TRUE if this is a constant range. */
1332 irange::constant_p () const
1334 return (m_num_ranges
> 0
1335 && TREE_CODE (min ()) == INTEGER_CST
1336 && TREE_CODE (max ()) == INTEGER_CST
);
1339 /* If range is a singleton, place it in RESULT and return TRUE.
1340 Note: A singleton can be any gimple invariant, not just constants.
1341 So, [&x, &x] counts as a singleton. */
1344 irange::singleton_p (tree
*result
) const
1346 if (!legacy_mode_p ())
1348 if (num_pairs () == 1 && (wi::to_wide (tree_lower_bound ())
1349 == wi::to_wide (tree_upper_bound ())))
1352 *result
= tree_lower_bound ();
1357 if (m_kind
== VR_ANTI_RANGE
)
1361 if (TYPE_PRECISION (type ()) == 1)
1369 if (num_pairs () == 1)
1371 value_range vr0
, vr1
;
1372 ranges_from_anti_range ((const value_range
*) this, &vr0
, &vr1
);
1373 return vr0
.singleton_p (result
);
1376 // Catches non-numeric extremes as well.
1377 if (m_kind
== VR_RANGE
1378 && vrp_operand_equal_p (min (), max ())
1379 && is_gimple_min_invariant (min ()))
1388 /* Return 1 if VAL is inside value range.
1389 0 if VAL is not inside value range.
1390 -2 if we cannot tell either way.
1392 Benchmark compile/20001226-1.c compilation time after changing this
1396 irange::value_inside_range (tree val
) const
1404 if (!legacy_mode_p () && TREE_CODE (val
) == INTEGER_CST
)
1405 return contains_p (val
);
1407 int cmp1
= operand_less_p (val
, min ());
1411 return m_kind
!= VR_RANGE
;
1413 int cmp2
= operand_less_p (max (), val
);
1417 if (m_kind
== VR_RANGE
)
1423 /* Return TRUE if it is possible that range contains VAL. */
1426 irange::may_contain_p (tree val
) const
1428 return value_inside_range (val
) != 0;
1431 /* Return TRUE if range contains INTEGER_CST. */
1432 /* Return 1 if VAL is inside value range.
1433 0 if VAL is not inside value range.
1435 Benchmark compile/20001226-1.c compilation time after changing this
1440 irange::contains_p (tree cst
) const
1445 if (legacy_mode_p ())
1447 gcc_checking_assert (TREE_CODE (cst
) == INTEGER_CST
);
1450 value_range
numeric_range (*this);
1451 numeric_range
.normalize_symbolics ();
1452 return numeric_range
.contains_p (cst
);
1454 return value_inside_range (cst
) == 1;
1457 gcc_checking_assert (TREE_CODE (cst
) == INTEGER_CST
);
1459 // See if we can exclude CST based on the nonzero bits.
1462 wide_int cstw
= wi::to_wide (cst
);
1463 if (cstw
!= 0 && wi::bit_and (wi::to_wide (m_nonzero_mask
), cstw
) == 0)
1467 signop sign
= TYPE_SIGN (TREE_TYPE (cst
));
1468 wide_int v
= wi::to_wide (cst
);
1469 for (unsigned r
= 0; r
< m_num_ranges
; ++r
)
1471 if (wi::lt_p (v
, lower_bound (r
), sign
))
1473 if (wi::le_p (v
, upper_bound (r
), sign
))
1481 /* Normalize addresses into constants. */
1484 irange::normalize_addresses ()
1489 if (!POINTER_TYPE_P (type ()) || range_has_numeric_bounds_p (this))
1492 if (!range_includes_zero_p (this))
1494 gcc_checking_assert (TREE_CODE (min ()) == ADDR_EXPR
1495 || TREE_CODE (max ()) == ADDR_EXPR
);
1496 set_nonzero (type ());
1499 set_varying (type ());
1502 /* Normalize symbolics and addresses into constants. */
1505 irange::normalize_symbolics ()
1507 if (varying_p () || undefined_p ())
1510 tree ttype
= type ();
1511 bool min_symbolic
= !is_gimple_min_invariant (min ());
1512 bool max_symbolic
= !is_gimple_min_invariant (max ());
1513 if (!min_symbolic
&& !max_symbolic
)
1515 normalize_addresses ();
1519 // [SYM, SYM] -> VARYING
1520 if (min_symbolic
&& max_symbolic
)
1522 set_varying (ttype
);
1525 if (kind () == VR_RANGE
)
1527 // [SYM, NUM] -> [-MIN, NUM]
1530 set (vrp_val_min (ttype
), max ());
1533 // [NUM, SYM] -> [NUM, +MAX]
1534 set (min (), vrp_val_max (ttype
));
1537 gcc_checking_assert (kind () == VR_ANTI_RANGE
);
1538 // ~[SYM, NUM] -> [NUM + 1, +MAX]
1541 if (!vrp_val_is_max (max ()))
1543 tree n
= wide_int_to_tree (ttype
, wi::to_wide (max ()) + 1);
1544 set (n
, vrp_val_max (ttype
));
1547 set_varying (ttype
);
1550 // ~[NUM, SYM] -> [-MIN, NUM - 1]
1551 if (!vrp_val_is_min (min ()))
1553 tree n
= wide_int_to_tree (ttype
, wi::to_wide (min ()) - 1);
1554 set (vrp_val_min (ttype
), n
);
1557 set_varying (ttype
);
1560 /* Intersect the two value-ranges { *VR0TYPE, *VR0MIN, *VR0MAX } and
1561 { VR1TYPE, VR0MIN, VR0MAX } and store the result
1562 in { *VR0TYPE, *VR0MIN, *VR0MAX }. This may not be the smallest
1563 possible such range. The resulting range is not canonicalized. */
1566 intersect_ranges (enum value_range_kind
*vr0type
,
1567 tree
*vr0min
, tree
*vr0max
,
1568 enum value_range_kind vr1type
,
1569 tree vr1min
, tree vr1max
)
1571 bool mineq
= vrp_operand_equal_p (*vr0min
, vr1min
);
1572 bool maxeq
= vrp_operand_equal_p (*vr0max
, vr1max
);
1574 /* [] is vr0, () is vr1 in the following classification comments. */
1578 if (*vr0type
== vr1type
)
1579 /* Nothing to do for equal ranges. */
1581 else if ((*vr0type
== VR_RANGE
1582 && vr1type
== VR_ANTI_RANGE
)
1583 || (*vr0type
== VR_ANTI_RANGE
1584 && vr1type
== VR_RANGE
))
1586 /* For anti-range with range intersection the result is empty. */
1587 *vr0type
= VR_UNDEFINED
;
1588 *vr0min
= NULL_TREE
;
1589 *vr0max
= NULL_TREE
;
1594 else if (operand_less_p (*vr0max
, vr1min
) == 1
1595 || operand_less_p (vr1max
, *vr0min
) == 1)
1597 /* [ ] ( ) or ( ) [ ]
1598 If the ranges have an empty intersection, the result of the
1599 intersect operation is the range for intersecting an
1600 anti-range with a range or empty when intersecting two ranges. */
1601 if (*vr0type
== VR_RANGE
1602 && vr1type
== VR_ANTI_RANGE
)
1604 else if (*vr0type
== VR_ANTI_RANGE
1605 && vr1type
== VR_RANGE
)
1611 else if (*vr0type
== VR_RANGE
1612 && vr1type
== VR_RANGE
)
1614 *vr0type
= VR_UNDEFINED
;
1615 *vr0min
= NULL_TREE
;
1616 *vr0max
= NULL_TREE
;
1618 else if (*vr0type
== VR_ANTI_RANGE
1619 && vr1type
== VR_ANTI_RANGE
)
1621 /* If the anti-ranges are adjacent to each other merge them. */
1622 if (TREE_CODE (*vr0max
) == INTEGER_CST
1623 && TREE_CODE (vr1min
) == INTEGER_CST
1624 && operand_less_p (*vr0max
, vr1min
) == 1
1625 && integer_onep (int_const_binop (MINUS_EXPR
,
1628 else if (TREE_CODE (vr1max
) == INTEGER_CST
1629 && TREE_CODE (*vr0min
) == INTEGER_CST
1630 && operand_less_p (vr1max
, *vr0min
) == 1
1631 && integer_onep (int_const_binop (MINUS_EXPR
,
1634 /* Else arbitrarily take VR0. */
1637 else if ((maxeq
|| operand_less_p (vr1max
, *vr0max
) == 1)
1638 && (mineq
|| operand_less_p (*vr0min
, vr1min
) == 1))
1640 /* [ ( ) ] or [( ) ] or [ ( )] */
1641 if (*vr0type
== VR_RANGE
1642 && vr1type
== VR_RANGE
)
1644 /* If both are ranges the result is the inner one. */
1649 else if (*vr0type
== VR_RANGE
1650 && vr1type
== VR_ANTI_RANGE
)
1652 /* Choose the right gap if the left one is empty. */
1655 if (TREE_CODE (vr1max
) != INTEGER_CST
)
1657 else if (TYPE_PRECISION (TREE_TYPE (vr1max
)) == 1
1658 && !TYPE_UNSIGNED (TREE_TYPE (vr1max
)))
1660 = int_const_binop (MINUS_EXPR
, vr1max
,
1661 build_int_cst (TREE_TYPE (vr1max
), -1));
1664 = int_const_binop (PLUS_EXPR
, vr1max
,
1665 build_int_cst (TREE_TYPE (vr1max
), 1));
1667 /* Choose the left gap if the right one is empty. */
1670 if (TREE_CODE (vr1min
) != INTEGER_CST
)
1672 else if (TYPE_PRECISION (TREE_TYPE (vr1min
)) == 1
1673 && !TYPE_UNSIGNED (TREE_TYPE (vr1min
)))
1675 = int_const_binop (PLUS_EXPR
, vr1min
,
1676 build_int_cst (TREE_TYPE (vr1min
), -1));
1679 = int_const_binop (MINUS_EXPR
, vr1min
,
1680 build_int_cst (TREE_TYPE (vr1min
), 1));
1682 /* Choose the anti-range if the range is effectively varying. */
1683 else if (vrp_val_is_min (*vr0min
)
1684 && vrp_val_is_max (*vr0max
))
1690 /* Else choose the range. */
1692 else if (*vr0type
== VR_ANTI_RANGE
1693 && vr1type
== VR_ANTI_RANGE
)
1694 /* If both are anti-ranges the result is the outer one. */
1696 else if (*vr0type
== VR_ANTI_RANGE
1697 && vr1type
== VR_RANGE
)
1699 /* The intersection is empty. */
1700 *vr0type
= VR_UNDEFINED
;
1701 *vr0min
= NULL_TREE
;
1702 *vr0max
= NULL_TREE
;
1707 else if ((maxeq
|| operand_less_p (*vr0max
, vr1max
) == 1)
1708 && (mineq
|| operand_less_p (vr1min
, *vr0min
) == 1))
1710 /* ( [ ] ) or ([ ] ) or ( [ ]) */
1711 if (*vr0type
== VR_RANGE
1712 && vr1type
== VR_RANGE
)
1713 /* Choose the inner range. */
1715 else if (*vr0type
== VR_ANTI_RANGE
1716 && vr1type
== VR_RANGE
)
1718 /* Choose the right gap if the left is empty. */
1721 *vr0type
= VR_RANGE
;
1722 if (TREE_CODE (*vr0max
) != INTEGER_CST
)
1724 else if (TYPE_PRECISION (TREE_TYPE (*vr0max
)) == 1
1725 && !TYPE_UNSIGNED (TREE_TYPE (*vr0max
)))
1727 = int_const_binop (MINUS_EXPR
, *vr0max
,
1728 build_int_cst (TREE_TYPE (*vr0max
), -1));
1731 = int_const_binop (PLUS_EXPR
, *vr0max
,
1732 build_int_cst (TREE_TYPE (*vr0max
), 1));
1735 /* Choose the left gap if the right is empty. */
1738 *vr0type
= VR_RANGE
;
1739 if (TREE_CODE (*vr0min
) != INTEGER_CST
)
1741 else if (TYPE_PRECISION (TREE_TYPE (*vr0min
)) == 1
1742 && !TYPE_UNSIGNED (TREE_TYPE (*vr0min
)))
1744 = int_const_binop (PLUS_EXPR
, *vr0min
,
1745 build_int_cst (TREE_TYPE (*vr0min
), -1));
1748 = int_const_binop (MINUS_EXPR
, *vr0min
,
1749 build_int_cst (TREE_TYPE (*vr0min
), 1));
1752 /* Choose the anti-range if the range is effectively varying. */
1753 else if (vrp_val_is_min (vr1min
)
1754 && vrp_val_is_max (vr1max
))
1756 /* Choose the anti-range if it is ~[0,0], that range is special
1757 enough to special case when vr1's range is relatively wide.
1758 At least for types bigger than int - this covers pointers
1759 and arguments to functions like ctz. */
1760 else if (*vr0min
== *vr0max
1761 && integer_zerop (*vr0min
)
1762 && ((TYPE_PRECISION (TREE_TYPE (*vr0min
))
1763 >= TYPE_PRECISION (integer_type_node
))
1764 || POINTER_TYPE_P (TREE_TYPE (*vr0min
)))
1765 && TREE_CODE (vr1max
) == INTEGER_CST
1766 && TREE_CODE (vr1min
) == INTEGER_CST
1767 && (wi::clz (wi::to_wide (vr1max
) - wi::to_wide (vr1min
))
1768 < TYPE_PRECISION (TREE_TYPE (*vr0min
)) / 2))
1770 /* Else choose the range. */
1778 else if (*vr0type
== VR_ANTI_RANGE
1779 && vr1type
== VR_ANTI_RANGE
)
1781 /* If both are anti-ranges the result is the outer one. */
1786 else if (vr1type
== VR_ANTI_RANGE
1787 && *vr0type
== VR_RANGE
)
1789 /* The intersection is empty. */
1790 *vr0type
= VR_UNDEFINED
;
1791 *vr0min
= NULL_TREE
;
1792 *vr0max
= NULL_TREE
;
1797 else if ((operand_less_p (vr1min
, *vr0max
) == 1
1798 || operand_equal_p (vr1min
, *vr0max
, 0))
1799 && operand_less_p (*vr0min
, vr1min
) == 1
1800 && operand_less_p (*vr0max
, vr1max
) == 1)
1802 /* [ ( ] ) or [ ]( ) */
1803 if (*vr0type
== VR_ANTI_RANGE
1804 && vr1type
== VR_ANTI_RANGE
)
1806 else if (*vr0type
== VR_RANGE
1807 && vr1type
== VR_RANGE
)
1809 else if (*vr0type
== VR_RANGE
1810 && vr1type
== VR_ANTI_RANGE
)
1812 if (TREE_CODE (vr1min
) == INTEGER_CST
)
1813 *vr0max
= int_const_binop (MINUS_EXPR
, vr1min
,
1814 build_int_cst (TREE_TYPE (vr1min
), 1));
1818 else if (*vr0type
== VR_ANTI_RANGE
1819 && vr1type
== VR_RANGE
)
1821 *vr0type
= VR_RANGE
;
1822 if (TREE_CODE (*vr0max
) == INTEGER_CST
)
1823 *vr0min
= int_const_binop (PLUS_EXPR
, *vr0max
,
1824 build_int_cst (TREE_TYPE (*vr0max
), 1));
1832 else if ((operand_less_p (*vr0min
, vr1max
) == 1
1833 || operand_equal_p (*vr0min
, vr1max
, 0))
1834 && operand_less_p (vr1min
, *vr0min
) == 1
1835 && operand_less_p (vr1max
, *vr0max
) == 1)
1837 /* ( [ ) ] or ( )[ ] */
1838 if (*vr0type
== VR_ANTI_RANGE
1839 && vr1type
== VR_ANTI_RANGE
)
1841 else if (*vr0type
== VR_RANGE
1842 && vr1type
== VR_RANGE
)
1844 else if (*vr0type
== VR_RANGE
1845 && vr1type
== VR_ANTI_RANGE
)
1847 if (TREE_CODE (vr1max
) == INTEGER_CST
)
1848 *vr0min
= int_const_binop (PLUS_EXPR
, vr1max
,
1849 build_int_cst (TREE_TYPE (vr1max
), 1));
1853 else if (*vr0type
== VR_ANTI_RANGE
1854 && vr1type
== VR_RANGE
)
1856 *vr0type
= VR_RANGE
;
1857 if (TREE_CODE (*vr0min
) == INTEGER_CST
)
1858 *vr0max
= int_const_binop (MINUS_EXPR
, *vr0min
,
1859 build_int_cst (TREE_TYPE (*vr0min
), 1));
1868 /* If we know the intersection is empty, there's no need to
1869 conservatively add anything else to the set. */
1870 if (*vr0type
== VR_UNDEFINED
)
1873 /* As a fallback simply use { *VRTYPE, *VR0MIN, *VR0MAX } as
1874 result for the intersection. That's always a conservative
1875 correct estimate unless VR1 is a constant singleton range
1876 in which case we choose that. */
1877 if (vr1type
== VR_RANGE
1878 && is_gimple_min_invariant (vr1min
)
1879 && vrp_operand_equal_p (vr1min
, vr1max
))
1887 /* Helper for the intersection operation for value ranges. Given two
1888 ranges VR0 and VR1, set VR0 to the intersection of both ranges.
1889 This may not be the smallest possible such range. */
1892 irange::legacy_intersect (irange
*vr0
, const irange
*vr1
)
1894 gcc_checking_assert (vr0
->legacy_mode_p ());
1895 gcc_checking_assert (vr1
->legacy_mode_p ());
1896 /* If either range is VR_VARYING the other one wins. */
1897 if (vr1
->varying_p ())
1899 if (vr0
->varying_p ())
1901 vr0
->set (vr1
->min (), vr1
->max (), vr1
->kind ());
1905 /* When either range is VR_UNDEFINED the resulting range is
1906 VR_UNDEFINED, too. */
1907 if (vr0
->undefined_p ())
1909 if (vr1
->undefined_p ())
1911 vr0
->set_undefined ();
1915 value_range_kind vr0kind
= vr0
->kind ();
1916 tree vr0min
= vr0
->min ();
1917 tree vr0max
= vr0
->max ();
1919 intersect_ranges (&vr0kind
, &vr0min
, &vr0max
,
1920 vr1
->kind (), vr1
->min (), vr1
->max ());
1922 /* Make sure to canonicalize the result though as the inversion of a
1923 VR_RANGE can still be a VR_RANGE. */
1924 if (vr0kind
== VR_UNDEFINED
)
1925 vr0
->set_undefined ();
1926 else if (vr0kind
== VR_VARYING
)
1928 /* If we failed, use the original VR0. */
1932 vr0
->set (vr0min
, vr0max
, vr0kind
);
1935 /* Union the two value-ranges { *VR0TYPE, *VR0MIN, *VR0MAX } and
1936 { VR1TYPE, VR0MIN, VR0MAX } and store the result
1937 in { *VR0TYPE, *VR0MIN, *VR0MAX }. This may not be the smallest
1938 possible such range. The resulting range is not canonicalized. */
1941 union_ranges (enum value_range_kind
*vr0type
,
1942 tree
*vr0min
, tree
*vr0max
,
1943 enum value_range_kind vr1type
,
1944 tree vr1min
, tree vr1max
)
1946 int cmpmin
= compare_values (*vr0min
, vr1min
);
1947 int cmpmax
= compare_values (*vr0max
, vr1max
);
1948 bool mineq
= cmpmin
== 0;
1949 bool maxeq
= cmpmax
== 0;
1951 /* [] is vr0, () is vr1 in the following classification comments. */
1955 if (*vr0type
== vr1type
)
1956 /* Nothing to do for equal ranges. */
1958 else if ((*vr0type
== VR_RANGE
1959 && vr1type
== VR_ANTI_RANGE
)
1960 || (*vr0type
== VR_ANTI_RANGE
1961 && vr1type
== VR_RANGE
))
1963 /* For anti-range with range union the result is varying. */
1969 else if (operand_less_p (*vr0max
, vr1min
) == 1
1970 || operand_less_p (vr1max
, *vr0min
) == 1)
1972 /* [ ] ( ) or ( ) [ ]
1973 If the ranges have an empty intersection, result of the union
1974 operation is the anti-range or if both are anti-ranges
1976 if (*vr0type
== VR_ANTI_RANGE
1977 && vr1type
== VR_ANTI_RANGE
)
1979 else if (*vr0type
== VR_ANTI_RANGE
1980 && vr1type
== VR_RANGE
)
1982 else if (*vr0type
== VR_RANGE
1983 && vr1type
== VR_ANTI_RANGE
)
1989 else if (*vr0type
== VR_RANGE
1990 && vr1type
== VR_RANGE
)
1992 /* The result is the convex hull of both ranges. */
1993 if (operand_less_p (*vr0max
, vr1min
) == 1)
1995 /* If the result can be an anti-range, create one. */
1996 if (TREE_CODE (*vr0max
) == INTEGER_CST
1997 && TREE_CODE (vr1min
) == INTEGER_CST
1998 && vrp_val_is_min (*vr0min
)
1999 && vrp_val_is_max (vr1max
))
2001 tree min
= int_const_binop (PLUS_EXPR
,
2003 build_int_cst (TREE_TYPE (*vr0max
), 1));
2004 tree max
= int_const_binop (MINUS_EXPR
,
2006 build_int_cst (TREE_TYPE (vr1min
), 1));
2007 if (!operand_less_p (max
, min
))
2009 *vr0type
= VR_ANTI_RANGE
;
2021 /* If the result can be an anti-range, create one. */
2022 if (TREE_CODE (vr1max
) == INTEGER_CST
2023 && TREE_CODE (*vr0min
) == INTEGER_CST
2024 && vrp_val_is_min (vr1min
)
2025 && vrp_val_is_max (*vr0max
))
2027 tree min
= int_const_binop (PLUS_EXPR
,
2029 build_int_cst (TREE_TYPE (vr1max
), 1));
2030 tree max
= int_const_binop (MINUS_EXPR
,
2032 build_int_cst (TREE_TYPE (*vr0min
), 1));
2033 if (!operand_less_p (max
, min
))
2035 *vr0type
= VR_ANTI_RANGE
;
2049 else if ((maxeq
|| cmpmax
== 1)
2050 && (mineq
|| cmpmin
== -1))
2052 /* [ ( ) ] or [( ) ] or [ ( )] */
2053 if (*vr0type
== VR_RANGE
2054 && vr1type
== VR_RANGE
)
2056 else if (*vr0type
== VR_ANTI_RANGE
2057 && vr1type
== VR_ANTI_RANGE
)
2063 else if (*vr0type
== VR_ANTI_RANGE
2064 && vr1type
== VR_RANGE
)
2066 /* Arbitrarily choose the right or left gap. */
2067 if (!mineq
&& TREE_CODE (vr1min
) == INTEGER_CST
)
2068 *vr0max
= int_const_binop (MINUS_EXPR
, vr1min
,
2069 build_int_cst (TREE_TYPE (vr1min
), 1));
2070 else if (!maxeq
&& TREE_CODE (vr1max
) == INTEGER_CST
)
2071 *vr0min
= int_const_binop (PLUS_EXPR
, vr1max
,
2072 build_int_cst (TREE_TYPE (vr1max
), 1));
2076 else if (*vr0type
== VR_RANGE
2077 && vr1type
== VR_ANTI_RANGE
)
2078 /* The result covers everything. */
2083 else if ((maxeq
|| cmpmax
== -1)
2084 && (mineq
|| cmpmin
== 1))
2086 /* ( [ ] ) or ([ ] ) or ( [ ]) */
2087 if (*vr0type
== VR_RANGE
2088 && vr1type
== VR_RANGE
)
2094 else if (*vr0type
== VR_ANTI_RANGE
2095 && vr1type
== VR_ANTI_RANGE
)
2097 else if (*vr0type
== VR_RANGE
2098 && vr1type
== VR_ANTI_RANGE
)
2100 *vr0type
= VR_ANTI_RANGE
;
2101 if (!mineq
&& TREE_CODE (*vr0min
) == INTEGER_CST
)
2103 *vr0max
= int_const_binop (MINUS_EXPR
, *vr0min
,
2104 build_int_cst (TREE_TYPE (*vr0min
), 1));
2107 else if (!maxeq
&& TREE_CODE (*vr0max
) == INTEGER_CST
)
2109 *vr0min
= int_const_binop (PLUS_EXPR
, *vr0max
,
2110 build_int_cst (TREE_TYPE (*vr0max
), 1));
2116 else if (*vr0type
== VR_ANTI_RANGE
2117 && vr1type
== VR_RANGE
)
2118 /* The result covers everything. */
2123 else if (cmpmin
== -1
2125 && (operand_less_p (vr1min
, *vr0max
) == 1
2126 || operand_equal_p (vr1min
, *vr0max
, 0)))
2128 /* [ ( ] ) or [ ]( ) */
2129 if (*vr0type
== VR_RANGE
2130 && vr1type
== VR_RANGE
)
2132 else if (*vr0type
== VR_ANTI_RANGE
2133 && vr1type
== VR_ANTI_RANGE
)
2135 else if (*vr0type
== VR_ANTI_RANGE
2136 && vr1type
== VR_RANGE
)
2138 if (TREE_CODE (vr1min
) == INTEGER_CST
)
2139 *vr0max
= int_const_binop (MINUS_EXPR
, vr1min
,
2140 build_int_cst (TREE_TYPE (vr1min
), 1));
2144 else if (*vr0type
== VR_RANGE
2145 && vr1type
== VR_ANTI_RANGE
)
2147 if (TREE_CODE (*vr0max
) == INTEGER_CST
)
2150 *vr0min
= int_const_binop (PLUS_EXPR
, *vr0max
,
2151 build_int_cst (TREE_TYPE (*vr0max
), 1));
2160 else if (cmpmin
== 1
2162 && (operand_less_p (*vr0min
, vr1max
) == 1
2163 || operand_equal_p (*vr0min
, vr1max
, 0)))
2165 /* ( [ ) ] or ( )[ ] */
2166 if (*vr0type
== VR_RANGE
2167 && vr1type
== VR_RANGE
)
2169 else if (*vr0type
== VR_ANTI_RANGE
2170 && vr1type
== VR_ANTI_RANGE
)
2172 else if (*vr0type
== VR_ANTI_RANGE
2173 && vr1type
== VR_RANGE
)
2175 if (TREE_CODE (vr1max
) == INTEGER_CST
)
2176 *vr0min
= int_const_binop (PLUS_EXPR
, vr1max
,
2177 build_int_cst (TREE_TYPE (vr1max
), 1));
2181 else if (*vr0type
== VR_RANGE
2182 && vr1type
== VR_ANTI_RANGE
)
2184 if (TREE_CODE (*vr0min
) == INTEGER_CST
)
2187 *vr0max
= int_const_binop (MINUS_EXPR
, *vr0min
,
2188 build_int_cst (TREE_TYPE (*vr0min
), 1));
2203 *vr0type
= VR_VARYING
;
2204 *vr0min
= NULL_TREE
;
2205 *vr0max
= NULL_TREE
;
2208 /* Helper for meet operation for value ranges. Given two ranges VR0
2209 and VR1, set VR0 to the union of both ranges. This may not be the
2210 smallest possible such range. */
2213 irange::legacy_union (irange
*vr0
, const irange
*vr1
)
2215 gcc_checking_assert (vr0
->legacy_mode_p ());
2216 gcc_checking_assert (vr1
->legacy_mode_p ());
2218 /* VR0 has the resulting range if VR1 is undefined or VR0 is varying. */
2219 if (vr1
->undefined_p ()
2220 || vr0
->varying_p ())
2223 /* VR1 has the resulting range if VR0 is undefined or VR1 is varying. */
2224 if (vr0
->undefined_p ())
2226 vr0
->set (vr1
->min (), vr1
->max (), vr1
->kind ());
2230 if (vr1
->varying_p ())
2232 vr0
->set_varying (vr1
->type ());
2236 value_range_kind vr0kind
= vr0
->kind ();
2237 tree vr0min
= vr0
->min ();
2238 tree vr0max
= vr0
->max ();
2240 union_ranges (&vr0kind
, &vr0min
, &vr0max
,
2241 vr1
->kind (), vr1
->min (), vr1
->max ());
2243 if (vr0kind
== VR_UNDEFINED
)
2244 vr0
->set_undefined ();
2245 else if (vr0kind
== VR_VARYING
)
2247 /* Failed to find an efficient meet. Before giving up and
2248 setting the result to VARYING, see if we can at least derive
2249 a non-zero range. */
2250 if (range_includes_zero_p (vr0
) == 0
2251 && range_includes_zero_p (vr1
) == 0)
2252 vr0
->set_nonzero (vr0
->type ());
2254 vr0
->set_varying (vr0
->type ());
2257 vr0
->set (vr0min
, vr0max
, vr0kind
);
2260 /* Meet operation for value ranges. Given two value ranges VR0 and
2261 VR1, store in VR0 a range that contains both VR0 and VR1. This
2262 may not be the smallest possible such range.
2263 Return TRUE if the original value changes. */
2266 irange::legacy_verbose_union_ (const irange
*other
)
2268 if (legacy_mode_p ())
2270 if (!other
->legacy_mode_p ())
2272 int_range
<1> tmp
= *other
;
2273 legacy_union (this, &tmp
);
2276 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2278 fprintf (dump_file
, "Meeting\n ");
2279 dump_value_range (dump_file
, this);
2280 fprintf (dump_file
, "\nand\n ");
2281 dump_value_range (dump_file
, other
);
2282 fprintf (dump_file
, "\n");
2285 legacy_union (this, other
);
2287 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2289 fprintf (dump_file
, "to\n ");
2290 dump_value_range (dump_file
, this);
2291 fprintf (dump_file
, "\n");
2296 if (other
->legacy_mode_p ())
2298 int_range
<2> wider
= *other
;
2299 return irange_union (wider
);
2302 return irange_union (*other
);
2306 irange::legacy_verbose_intersect (const irange
*other
)
2308 if (legacy_mode_p ())
2310 if (!other
->legacy_mode_p ())
2312 int_range
<1> tmp
= *other
;
2313 legacy_intersect (this, &tmp
);
2316 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2318 fprintf (dump_file
, "Intersecting\n ");
2319 dump_value_range (dump_file
, this);
2320 fprintf (dump_file
, "\nand\n ");
2321 dump_value_range (dump_file
, other
);
2322 fprintf (dump_file
, "\n");
2325 legacy_intersect (this, other
);
2327 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2329 fprintf (dump_file
, "to\n ");
2330 dump_value_range (dump_file
, this);
2331 fprintf (dump_file
, "\n");
2336 if (other
->legacy_mode_p ())
2340 return irange_intersect (wider
);
2343 return irange_intersect (*other
);
2346 // Perform an efficient union with R when both ranges have only a single pair.
2347 // Excluded are VARYING and UNDEFINED ranges.
2350 irange::irange_single_pair_union (const irange
&r
)
2352 gcc_checking_assert (!undefined_p () && !varying_p ());
2353 gcc_checking_assert (!r
.undefined_p () && !varying_p ());
2355 signop sign
= TYPE_SIGN (TREE_TYPE (m_base
[0]));
2356 // Check if current lower bound is also the new lower bound.
2357 if (wi::le_p (wi::to_wide (m_base
[0]), wi::to_wide (r
.m_base
[0]), sign
))
2359 // If current upper bound is new upper bound, we're done.
2360 if (wi::le_p (wi::to_wide (r
.m_base
[1]), wi::to_wide (m_base
[1]), sign
))
2361 return union_nonzero_bits (r
);
2362 // Otherwise R has the new upper bound.
2363 // Check for overlap/touching ranges, or single target range.
2364 if (m_max_ranges
== 1
2365 || wi::to_widest (m_base
[1]) + 1 >= wi::to_widest (r
.m_base
[0]))
2366 m_base
[1] = r
.m_base
[1];
2369 // This is a dual range result.
2370 m_base
[2] = r
.m_base
[0];
2371 m_base
[3] = r
.m_base
[1];
2374 union_nonzero_bits (r
);
2378 // Set the new lower bound to R's lower bound.
2379 tree lb
= m_base
[0];
2380 m_base
[0] = r
.m_base
[0];
2382 // If R fully contains THIS range, just set the upper bound.
2383 if (wi::ge_p (wi::to_wide (r
.m_base
[1]), wi::to_wide (m_base
[1]), sign
))
2384 m_base
[1] = r
.m_base
[1];
2385 // Check for overlapping ranges, or target limited to a single range.
2386 else if (m_max_ranges
== 1
2387 || wi::to_widest (r
.m_base
[1]) + 1 >= wi::to_widest (lb
))
2391 // Left with 2 pairs.
2394 m_base
[3] = m_base
[1];
2395 m_base
[1] = r
.m_base
[1];
2397 union_nonzero_bits (r
);
2401 // union_ for multi-ranges.
2404 irange::irange_union (const irange
&r
)
2406 gcc_checking_assert (!legacy_mode_p () && !r
.legacy_mode_p ());
2408 if (r
.undefined_p ())
2424 set_varying (type ());
2428 // Special case one range union one range.
2429 if (m_num_ranges
== 1 && r
.m_num_ranges
== 1)
2430 return irange_single_pair_union (r
);
2432 // If this ranges fully contains R, then we need do nothing.
2433 if (irange_contains_p (r
))
2434 return union_nonzero_bits (r
);
2436 // Do not worry about merging and such by reserving twice as many
2437 // pairs as needed, and then simply sort the 2 ranges into this
2438 // intermediate form.
2440 // The intermediate result will have the property that the beginning
2441 // of each range is <= the beginning of the next range. There may
2442 // be overlapping ranges at this point. I.e. this would be valid
2443 // [-20, 10], [-10, 0], [0, 20], [40, 90] as it satisfies this
2444 // constraint : -20 < -10 < 0 < 40. When the range is rebuilt into r,
2445 // the merge is performed.
2447 // [Xi,Yi]..[Xn,Yn] U [Xj,Yj]..[Xm,Ym] --> [Xk,Yk]..[Xp,Yp]
2448 auto_vec
<tree
, 20> res (m_num_ranges
* 2 + r
.m_num_ranges
* 2);
2449 unsigned i
= 0, j
= 0, k
= 0;
2451 while (i
< m_num_ranges
* 2 && j
< r
.m_num_ranges
* 2)
2453 // lower of Xi and Xj is the lowest point.
2454 if (wi::to_widest (m_base
[i
]) <= wi::to_widest (r
.m_base
[j
]))
2456 res
.quick_push (m_base
[i
]);
2457 res
.quick_push (m_base
[i
+ 1]);
2463 res
.quick_push (r
.m_base
[j
]);
2464 res
.quick_push (r
.m_base
[j
+ 1]);
2469 for ( ; i
< m_num_ranges
* 2; i
+= 2)
2471 res
.quick_push (m_base
[i
]);
2472 res
.quick_push (m_base
[i
+ 1]);
2475 for ( ; j
< r
.m_num_ranges
* 2; j
+= 2)
2477 res
.quick_push (r
.m_base
[j
]);
2478 res
.quick_push (r
.m_base
[j
+ 1]);
2482 // Now normalize the vector removing any overlaps.
2484 for (j
= 2; j
< k
; j
+= 2)
2486 // Current upper+1 is >= lower bound next pair, then we merge ranges.
2487 if (wi::to_widest (res
[i
- 1]) + 1 >= wi::to_widest (res
[j
]))
2489 // New upper bounds is greater of current or the next one.
2490 if (wi::to_widest (res
[j
+ 1]) > wi::to_widest (res
[i
- 1]))
2491 res
[i
- 1] = res
[j
+ 1];
2495 // This is a new distinct range, but no point in copying it
2496 // if it is already in the right place.
2500 res
[i
++] = res
[j
+ 1];
2507 // At this point, the vector should have i ranges, none overlapping.
2508 // Now it simply needs to be copied, and if there are too many
2509 // ranges, merge some. We wont do any analysis as to what the
2510 // "best" merges are, simply combine the final ranges into one.
2511 if (i
> m_max_ranges
* 2)
2513 res
[m_max_ranges
* 2 - 1] = res
[i
- 1];
2514 i
= m_max_ranges
* 2;
2517 for (j
= 0; j
< i
; j
++)
2518 m_base
[j
] = res
[j
];
2519 m_num_ranges
= i
/ 2;
2522 union_nonzero_bits (r
);
2526 // Return TRUE if THIS fully contains R. No undefined or varying cases.
2529 irange::irange_contains_p (const irange
&r
) const
2531 gcc_checking_assert (!undefined_p () && !varying_p ());
2532 gcc_checking_assert (!r
.undefined_p () && !varying_p ());
2534 // In order for THIS to fully contain R, all of the pairs within R must
2535 // be fully contained by the pairs in this object.
2536 signop sign
= TYPE_SIGN (TREE_TYPE(m_base
[0]));
2539 tree rl
= r
.m_base
[0];
2540 tree ru
= r
.m_base
[1];
2545 // If r is contained within this range, move to the next R
2546 if (wi::ge_p (wi::to_wide (rl
), wi::to_wide (l
), sign
)
2547 && wi::le_p (wi::to_wide (ru
), wi::to_wide (u
), sign
))
2549 // This pair is OK, Either done, or bump to the next.
2550 if (++ri
>= r
.num_pairs ())
2552 rl
= r
.m_base
[ri
* 2];
2553 ru
= r
.m_base
[ri
* 2 + 1];
2556 // Otherwise, check if this's pair occurs before R's.
2557 if (wi::lt_p (wi::to_wide (u
), wi::to_wide (rl
), sign
))
2559 // There's still at least one pair of R left.
2560 if (++i
>= num_pairs ())
2563 u
= m_base
[i
* 2 + 1];
2572 // Intersect for multi-ranges. Return TRUE if anything changes.
2575 irange::irange_intersect (const irange
&r
)
2577 gcc_checking_assert (!legacy_mode_p () && !r
.legacy_mode_p ());
2578 gcc_checking_assert (undefined_p () || r
.undefined_p ()
2579 || range_compatible_p (type (), r
.type ()));
2583 if (r
.undefined_p ())
2596 if (r
.num_pairs () == 1)
2598 bool res
= intersect (r
.lower_bound (), r
.upper_bound ());
2602 res
|= intersect_nonzero_bits (r
);
2606 // If R fully contains this, then intersection will change nothing.
2607 if (r
.irange_contains_p (*this))
2608 return intersect_nonzero_bits (r
);
2610 signop sign
= TYPE_SIGN (TREE_TYPE(m_base
[0]));
2611 unsigned bld_pair
= 0;
2612 unsigned bld_lim
= m_max_ranges
;
2613 int_range_max
r2 (*this);
2614 unsigned r2_lim
= r2
.num_pairs ();
2616 for (unsigned i
= 0; i
< r
.num_pairs (); )
2618 // If r1's upper is < r2's lower, we can skip r1's pair.
2619 tree ru
= r
.m_base
[i
* 2 + 1];
2620 tree r2l
= r2
.m_base
[i2
* 2];
2621 if (wi::lt_p (wi::to_wide (ru
), wi::to_wide (r2l
), sign
))
2626 // Likewise, skip r2's pair if its excluded.
2627 tree r2u
= r2
.m_base
[i2
* 2 + 1];
2628 tree rl
= r
.m_base
[i
* 2];
2629 if (wi::lt_p (wi::to_wide (r2u
), wi::to_wide (rl
), sign
))
2634 // No more r2, break.
2638 // Must be some overlap. Find the highest of the lower bounds,
2639 // and set it, unless the build limits lower bounds is already
2641 if (bld_pair
< bld_lim
)
2643 if (wi::ge_p (wi::to_wide (rl
), wi::to_wide (r2l
), sign
))
2644 m_base
[bld_pair
* 2] = rl
;
2646 m_base
[bld_pair
* 2] = r2l
;
2649 // Decrease and set a new upper.
2652 // ...and choose the lower of the upper bounds.
2653 if (wi::le_p (wi::to_wide (ru
), wi::to_wide (r2u
), sign
))
2655 m_base
[bld_pair
* 2 + 1] = ru
;
2657 // Move past the r1 pair and keep trying.
2663 m_base
[bld_pair
* 2 + 1] = r2u
;
2668 // No more r2, break.
2671 // r2 has the higher lower bound.
2674 // At the exit of this loop, it is one of 2 things:
2675 // ran out of r1, or r2, but either means we are done.
2676 m_num_ranges
= bld_pair
;
2677 if (m_num_ranges
== 0)
2684 intersect_nonzero_bits (r
);
2689 // Multirange intersect for a specified wide_int [lb, ub] range.
2690 // Return TRUE if intersect changed anything.
2692 // NOTE: It is the caller's responsibility to intersect the nonzero masks.
2695 irange::intersect (const wide_int
& lb
, const wide_int
& ub
)
2697 // Undefined remains undefined.
2701 if (legacy_mode_p ())
2703 intersect (int_range
<1> (type (), lb
, ub
));
2707 tree range_type
= type();
2708 signop sign
= TYPE_SIGN (range_type
);
2710 gcc_checking_assert (TYPE_PRECISION (range_type
) == wi::get_precision (lb
));
2711 gcc_checking_assert (TYPE_PRECISION (range_type
) == wi::get_precision (ub
));
2713 // If this range is fully contained, then intersection will do nothing.
2714 if (wi::ge_p (lower_bound (), lb
, sign
)
2715 && wi::le_p (upper_bound (), ub
, sign
))
2718 unsigned bld_index
= 0;
2719 unsigned pair_lim
= num_pairs ();
2720 for (unsigned i
= 0; i
< pair_lim
; i
++)
2722 tree pairl
= m_base
[i
* 2];
2723 tree pairu
= m_base
[i
* 2 + 1];
2724 // Once UB is less than a pairs lower bound, we're done.
2725 if (wi::lt_p (ub
, wi::to_wide (pairl
), sign
))
2727 // if LB is greater than this pairs upper, this pair is excluded.
2728 if (wi::lt_p (wi::to_wide (pairu
), lb
, sign
))
2731 // Must be some overlap. Find the highest of the lower bounds,
2733 if (wi::gt_p (lb
, wi::to_wide (pairl
), sign
))
2734 m_base
[bld_index
* 2] = wide_int_to_tree (range_type
, lb
);
2736 m_base
[bld_index
* 2] = pairl
;
2738 // ...and choose the lower of the upper bounds and if the base pair
2739 // has the lower upper bound, need to check next pair too.
2740 if (wi::lt_p (ub
, wi::to_wide (pairu
), sign
))
2742 m_base
[bld_index
++ * 2 + 1] = wide_int_to_tree (range_type
, ub
);
2746 m_base
[bld_index
++ * 2 + 1] = pairu
;
2749 m_num_ranges
= bld_index
;
2750 if (m_num_ranges
== 0)
2757 // No need to call normalize_kind(), as the caller will do this
2758 // while intersecting the nonzero mask.
2765 // Signed 1-bits are strange. You can't subtract 1, because you can't
2766 // represent the number 1. This works around that for the invert routine.
2768 static wide_int
inline
2769 subtract_one (const wide_int
&x
, tree type
, wi::overflow_type
&overflow
)
2771 if (TYPE_SIGN (type
) == SIGNED
)
2772 return wi::add (x
, -1, SIGNED
, &overflow
);
2774 return wi::sub (x
, 1, UNSIGNED
, &overflow
);
2777 // The analogous function for adding 1.
2779 static wide_int
inline
2780 add_one (const wide_int
&x
, tree type
, wi::overflow_type
&overflow
)
2782 if (TYPE_SIGN (type
) == SIGNED
)
2783 return wi::sub (x
, -1, SIGNED
, &overflow
);
2785 return wi::add (x
, 1, UNSIGNED
, &overflow
);
2788 // Return the inverse of a range.
2793 if (legacy_mode_p ())
2795 // We can't just invert VR_RANGE and VR_ANTI_RANGE because we may
2796 // create non-canonical ranges. Use the constructors instead.
2797 if (m_kind
== VR_RANGE
)
2798 *this = value_range (min (), max (), VR_ANTI_RANGE
);
2799 else if (m_kind
== VR_ANTI_RANGE
)
2800 *this = value_range (min (), max ());
2806 gcc_checking_assert (!undefined_p () && !varying_p ());
2808 // We always need one more set of bounds to represent an inverse, so
2809 // if we're at the limit, we can't properly represent things.
2811 // For instance, to represent the inverse of a 2 sub-range set
2812 // [5, 10][20, 30], we would need a 3 sub-range set
2813 // [-MIN, 4][11, 19][31, MAX].
2815 // In this case, return the most conservative thing.
2817 // However, if any of the extremes of the range are -MIN/+MAX, we
2818 // know we will not need an extra bound. For example:
2820 // INVERT([-MIN,20][30,40]) => [21,29][41,+MAX]
2821 // INVERT([-MIN,20][30,MAX]) => [21,29]
2822 tree ttype
= type ();
2823 unsigned prec
= TYPE_PRECISION (ttype
);
2824 signop sign
= TYPE_SIGN (ttype
);
2825 wide_int type_min
= wi::min_value (prec
, sign
);
2826 wide_int type_max
= wi::max_value (prec
, sign
);
2827 m_nonzero_mask
= NULL
;
2828 if (m_num_ranges
== m_max_ranges
2829 && lower_bound () != type_min
2830 && upper_bound () != type_max
)
2832 m_base
[1] = wide_int_to_tree (ttype
, type_max
);
2836 // The algorithm is as follows. To calculate INVERT ([a,b][c,d]), we
2837 // generate [-MIN, a-1][b+1, c-1][d+1, MAX].
2839 // If there is an over/underflow in the calculation for any
2840 // sub-range, we eliminate that subrange. This allows us to easily
2841 // calculate INVERT([-MIN, 5]) with: [-MIN, -MIN-1][6, MAX]. And since
2842 // we eliminate the underflow, only [6, MAX] remains.
2844 wi::overflow_type ovf
;
2845 // Construct leftmost range.
2846 int_range_max
orig_range (*this);
2847 unsigned nitems
= 0;
2849 // If this is going to underflow on the MINUS 1, don't even bother
2850 // checking. This also handles subtracting one from an unsigned 0,
2851 // which doesn't set the underflow bit.
2852 if (type_min
!= orig_range
.lower_bound ())
2854 m_base
[nitems
++] = wide_int_to_tree (ttype
, type_min
);
2855 tmp
= subtract_one (orig_range
.lower_bound (), ttype
, ovf
);
2856 m_base
[nitems
++] = wide_int_to_tree (ttype
, tmp
);
2861 // Construct middle ranges if applicable.
2862 if (orig_range
.num_pairs () > 1)
2865 for (; j
< (orig_range
.num_pairs () * 2) - 1; j
+= 2)
2867 // The middle ranges cannot have MAX/MIN, so there's no need
2868 // to check for unsigned overflow on the +1 and -1 here.
2869 tmp
= wi::add (wi::to_wide (orig_range
.m_base
[j
]), 1, sign
, &ovf
);
2870 m_base
[nitems
++] = wide_int_to_tree (ttype
, tmp
);
2871 tmp
= subtract_one (wi::to_wide (orig_range
.m_base
[j
+ 1]),
2873 m_base
[nitems
++] = wide_int_to_tree (ttype
, tmp
);
2879 // Construct rightmost range.
2881 // However, if this will overflow on the PLUS 1, don't even bother.
2882 // This also handles adding one to an unsigned MAX, which doesn't
2883 // set the overflow bit.
2884 if (type_max
!= wi::to_wide (orig_range
.m_base
[i
]))
2886 tmp
= add_one (wi::to_wide (orig_range
.m_base
[i
]), ttype
, ovf
);
2887 m_base
[nitems
++] = wide_int_to_tree (ttype
, tmp
);
2888 m_base
[nitems
++] = wide_int_to_tree (ttype
, type_max
);
2892 m_num_ranges
= nitems
/ 2;
2894 // We disallow undefined or varying coming in, so the result can
2895 // only be a VR_RANGE.
2896 gcc_checking_assert (m_kind
== VR_RANGE
);
2902 // Return the nonzero bits inherent in the range.
2905 irange::get_nonzero_bits_from_range () const
2907 // For legacy symbolics.
2909 return wi::shwi (-1, TYPE_PRECISION (type ()));
2911 wide_int min
= lower_bound ();
2912 wide_int max
= upper_bound ();
2913 wide_int xorv
= min
^ max
;
2916 unsigned prec
= TYPE_PRECISION (type ());
2917 xorv
= wi::mask (prec
- wi::clz (xorv
), false, prec
);
2922 // If the the nonzero mask can be trivially converted to a range, do
2923 // so and return TRUE.
2926 irange::set_range_from_nonzero_bits ()
2928 gcc_checking_assert (!undefined_p ());
2929 if (!m_nonzero_mask
)
2931 unsigned popcount
= wi::popcount (wi::to_wide (m_nonzero_mask
));
2933 // If we have only one bit set in the mask, we can figure out the
2934 // range immediately.
2937 // Make sure we don't pessimize the range.
2938 if (!contains_p (m_nonzero_mask
))
2941 bool has_zero
= contains_p (build_zero_cst (type ()));
2942 tree nz
= m_nonzero_mask
;
2944 m_nonzero_mask
= nz
;
2948 zero
.set_zero (type ());
2953 else if (popcount
== 0)
2962 irange::set_nonzero_bits (const wide_int_ref
&bits
)
2964 gcc_checking_assert (!undefined_p ());
2965 unsigned prec
= TYPE_PRECISION (type ());
2969 m_nonzero_mask
= NULL
;
2976 // Drop VARYINGs with a nonzero mask to a plain range.
2977 if (m_kind
== VR_VARYING
&& bits
!= -1)
2980 wide_int nz
= wide_int::from (bits
, prec
, TYPE_SIGN (type ()));
2981 m_nonzero_mask
= wide_int_to_tree (type (), nz
);
2982 if (set_range_from_nonzero_bits ())
2990 // Return the nonzero bitmask. This will return the nonzero bits plus
2991 // the nonzero bits inherent in the range.
2994 irange::get_nonzero_bits () const
2996 gcc_checking_assert (!undefined_p ());
2997 // The nonzero mask inherent in the range is calculated on-demand.
2998 // For example, [0,255] does not have a 0xff nonzero mask by default
2999 // (unless manually set). This saves us considerable time, because
3000 // setting it at creation incurs a large penalty for irange::set.
3001 // At the time of writing there was a 5% slowdown in VRP if we kept
3002 // the mask precisely up to date at all times. Instead, we default
3003 // to -1 and set it when explicitly requested. However, this
3004 // function will always return the correct mask.
3006 return wi::to_wide (m_nonzero_mask
) & get_nonzero_bits_from_range ();
3008 return get_nonzero_bits_from_range ();
3011 // Convert tree mask to wide_int. Returns -1 for NULL masks.
3014 mask_to_wi (tree mask
, tree type
)
3017 return wi::to_wide (mask
);
3019 return wi::shwi (-1, TYPE_PRECISION (type
));
3022 // Intersect the nonzero bits in R into THIS and normalize the range.
3023 // Return TRUE if the intersection changed anything.
3026 irange::intersect_nonzero_bits (const irange
&r
)
3028 gcc_checking_assert (!undefined_p () && !r
.undefined_p ());
3030 if (!m_nonzero_mask
&& !r
.m_nonzero_mask
)
3038 bool changed
= false;
3040 if (mask_to_wi (m_nonzero_mask
, t
) != mask_to_wi (r
.m_nonzero_mask
, t
))
3042 wide_int nz
= get_nonzero_bits () & r
.get_nonzero_bits ();
3043 // If the nonzero bits did not change, return false.
3044 if (nz
== get_nonzero_bits ())
3047 m_nonzero_mask
= wide_int_to_tree (t
, nz
);
3048 if (set_range_from_nonzero_bits ())
3058 // Union the nonzero bits in R into THIS and normalize the range.
3059 // Return TRUE if the union changed anything.
3062 irange::union_nonzero_bits (const irange
&r
)
3064 gcc_checking_assert (!undefined_p () && !r
.undefined_p ());
3066 if (!m_nonzero_mask
&& !r
.m_nonzero_mask
)
3074 bool changed
= false;
3076 if (mask_to_wi (m_nonzero_mask
, t
) != mask_to_wi (r
.m_nonzero_mask
, t
))
3078 wide_int nz
= get_nonzero_bits () | r
.get_nonzero_bits ();
3079 m_nonzero_mask
= wide_int_to_tree (t
, nz
);
3080 // No need to call set_range_from_nonzero_bits, because we'll
3081 // never narrow the range. Besides, it would cause endless
3082 // recursion because of the union_ in
3083 // set_range_from_nonzero_bits.
3093 dump_value_range (FILE *file
, const vrange
*vr
)
3099 debug (const vrange
*vr
)
3101 dump_value_range (stderr
, vr
);
3102 fprintf (stderr
, "\n");
3106 debug (const vrange
&vr
)
3112 debug (const value_range
*vr
)
3114 dump_value_range (stderr
, vr
);
3115 fprintf (stderr
, "\n");
3119 debug (const value_range
&vr
)
3121 dump_value_range (stderr
, &vr
);
3122 fprintf (stderr
, "\n");
3125 /* Create two value-ranges in *VR0 and *VR1 from the anti-range *AR
3126 so that *VR0 U *VR1 == *AR. Returns true if that is possible,
3127 false otherwise. If *AR can be represented with a single range
3128 *VR1 will be VR_UNDEFINED. */
3131 ranges_from_anti_range (const value_range
*ar
,
3132 value_range
*vr0
, value_range
*vr1
)
3134 tree type
= ar
->type ();
3136 vr0
->set_undefined ();
3137 vr1
->set_undefined ();
3139 /* As a future improvement, we could handle ~[0, A] as: [-INF, -1] U
3140 [A+1, +INF]. Not sure if this helps in practice, though. */
3142 if (ar
->kind () != VR_ANTI_RANGE
3143 || TREE_CODE (ar
->min ()) != INTEGER_CST
3144 || TREE_CODE (ar
->max ()) != INTEGER_CST
3145 || !vrp_val_min (type
)
3146 || !vrp_val_max (type
))
3149 if (tree_int_cst_lt (vrp_val_min (type
), ar
->min ()))
3150 vr0
->set (vrp_val_min (type
),
3151 wide_int_to_tree (type
, wi::to_wide (ar
->min ()) - 1));
3152 if (tree_int_cst_lt (ar
->max (), vrp_val_max (type
)))
3153 vr1
->set (wide_int_to_tree (type
, wi::to_wide (ar
->max ()) + 1),
3154 vrp_val_max (type
));
3155 if (vr0
->undefined_p ())
3158 vr1
->set_undefined ();
3161 return !vr0
->undefined_p ();
3165 range_has_numeric_bounds_p (const irange
*vr
)
3167 return (!vr
->undefined_p ()
3168 && TREE_CODE (vr
->min ()) == INTEGER_CST
3169 && TREE_CODE (vr
->max ()) == INTEGER_CST
);
3172 /* Return whether VAL is equal to the maximum value of its type.
3173 We can't do a simple equality comparison with TYPE_MAX_VALUE because
3174 C typedefs and Ada subtypes can produce types whose TYPE_MAX_VALUE
3175 is not == to the integer constant with the same value in the type. */
3178 vrp_val_is_max (const_tree val
)
3180 tree type_max
= vrp_val_max (TREE_TYPE (val
));
3181 return (val
== type_max
3182 || (type_max
!= NULL_TREE
3183 && operand_equal_p (val
, type_max
, 0)));
3186 /* Return whether VAL is equal to the minimum value of its type. */
3189 vrp_val_is_min (const_tree val
)
3191 tree type_min
= vrp_val_min (TREE_TYPE (val
));
3192 return (val
== type_min
3193 || (type_min
!= NULL_TREE
3194 && operand_equal_p (val
, type_min
, 0)));
3197 /* Return true, if VAL1 and VAL2 are equal values for VRP purposes. */
3200 vrp_operand_equal_p (const_tree val1
, const_tree val2
)
3204 if (!val1
|| !val2
|| !operand_equal_p (val1
, val2
, 0))
3209 // ?? These stubs are for ipa-prop.cc which use a value_range in a
3210 // hash_traits. hash-traits.h defines an extern of gt_ggc_mx (T &)
3211 // instead of picking up the gt_ggc_mx (T *) version.
3213 gt_pch_nx (int_range
<1> *&x
)
3215 return gt_pch_nx ((irange
*) x
);
3219 gt_ggc_mx (int_range
<1> *&x
)
3221 return gt_ggc_mx ((irange
*) x
);
3224 #define DEFINE_INT_RANGE_INSTANCE(N) \
3225 template int_range<N>::int_range(tree, tree, value_range_kind); \
3226 template int_range<N>::int_range(tree_node *, \
3229 value_range_kind); \
3230 template int_range<N>::int_range(tree); \
3231 template int_range<N>::int_range(const irange &); \
3232 template int_range<N>::int_range(const int_range &); \
3233 template int_range<N>& int_range<N>::operator= (const int_range &);
3235 DEFINE_INT_RANGE_INSTANCE(1)
3236 DEFINE_INT_RANGE_INSTANCE(2)
3237 DEFINE_INT_RANGE_INSTANCE(3)
3238 DEFINE_INT_RANGE_INSTANCE(255)
3241 #include "selftest.h"
3245 #define INT(N) build_int_cst (integer_type_node, (N))
3246 #define UINT(N) build_int_cstu (unsigned_type_node, (N))
3247 #define UINT128(N) build_int_cstu (u128_type, (N))
3248 #define UCHAR(N) build_int_cstu (unsigned_char_type_node, (N))
3249 #define SCHAR(N) build_int_cst (signed_char_type_node, (N))
3252 build_range3 (int a
, int b
, int c
, int d
, int e
, int f
)
3254 int_range
<3> i1 (INT (a
), INT (b
));
3255 int_range
<3> i2 (INT (c
), INT (d
));
3256 int_range
<3> i3 (INT (e
), INT (f
));
3263 range_tests_irange3 ()
3265 typedef int_range
<3> int_range3
;
3266 int_range3 r0
, r1
, r2
;
3267 int_range3 i1
, i2
, i3
;
3269 // ([10,20] U [5,8]) U [1,3] ==> [1,3][5,8][10,20].
3270 r0
= int_range3 (INT (10), INT (20));
3271 r1
= int_range3 (INT (5), INT (8));
3273 r1
= int_range3 (INT (1), INT (3));
3275 ASSERT_TRUE (r0
== build_range3 (1, 3, 5, 8, 10, 20));
3277 // [1,3][5,8][10,20] U [-5,0] => [-5,3][5,8][10,20].
3278 r1
= int_range3 (INT (-5), INT (0));
3280 ASSERT_TRUE (r0
== build_range3 (-5, 3, 5, 8, 10, 20));
3282 // [10,20][30,40] U [50,60] ==> [10,20][30,40][50,60].
3283 r1
= int_range3 (INT (50), INT (60));
3284 r0
= int_range3 (INT (10), INT (20));
3285 r0
.union_ (int_range3 (INT (30), INT (40)));
3287 ASSERT_TRUE (r0
== build_range3 (10, 20, 30, 40, 50, 60));
3288 // [10,20][30,40][50,60] U [70, 80] ==> [10,20][30,40][50,60][70,80].
3289 r1
= int_range3 (INT (70), INT (80));
3292 r2
= build_range3 (10, 20, 30, 40, 50, 60);
3293 r2
.union_ (int_range3 (INT (70), INT (80)));
3294 ASSERT_TRUE (r0
== r2
);
3296 // [10,20][30,40][50,60] U [6,35] => [6,40][50,60].
3297 r0
= build_range3 (10, 20, 30, 40, 50, 60);
3298 r1
= int_range3 (INT (6), INT (35));
3300 r1
= int_range3 (INT (6), INT (40));
3301 r1
.union_ (int_range3 (INT (50), INT (60)));
3302 ASSERT_TRUE (r0
== r1
);
3304 // [10,20][30,40][50,60] U [6,60] => [6,60].
3305 r0
= build_range3 (10, 20, 30, 40, 50, 60);
3306 r1
= int_range3 (INT (6), INT (60));
3308 ASSERT_TRUE (r0
== int_range3 (INT (6), INT (60)));
3310 // [10,20][30,40][50,60] U [6,70] => [6,70].
3311 r0
= build_range3 (10, 20, 30, 40, 50, 60);
3312 r1
= int_range3 (INT (6), INT (70));
3314 ASSERT_TRUE (r0
== int_range3 (INT (6), INT (70)));
3316 // [10,20][30,40][50,60] U [35,70] => [10,20][30,70].
3317 r0
= build_range3 (10, 20, 30, 40, 50, 60);
3318 r1
= int_range3 (INT (35), INT (70));
3320 r1
= int_range3 (INT (10), INT (20));
3321 r1
.union_ (int_range3 (INT (30), INT (70)));
3322 ASSERT_TRUE (r0
== r1
);
3324 // [10,20][30,40][50,60] U [15,35] => [10,40][50,60].
3325 r0
= build_range3 (10, 20, 30, 40, 50, 60);
3326 r1
= int_range3 (INT (15), INT (35));
3328 r1
= int_range3 (INT (10), INT (40));
3329 r1
.union_ (int_range3 (INT (50), INT (60)));
3330 ASSERT_TRUE (r0
== r1
);
3332 // [10,20][30,40][50,60] U [35,35] => [10,20][30,40][50,60].
3333 r0
= build_range3 (10, 20, 30, 40, 50, 60);
3334 r1
= int_range3 (INT (35), INT (35));
3336 ASSERT_TRUE (r0
== build_range3 (10, 20, 30, 40, 50, 60));
3340 range_tests_int_range_max ()
3343 unsigned int nrange
;
3345 // Build a huge multi-range range.
3346 for (nrange
= 0; nrange
< 50; ++nrange
)
3348 int_range
<1> tmp (INT (nrange
*10), INT (nrange
*10 + 5));
3351 ASSERT_TRUE (big
.num_pairs () == nrange
);
3353 // Verify that we can copy it without loosing precision.
3354 int_range_max
copy (big
);
3355 ASSERT_TRUE (copy
.num_pairs () == nrange
);
3357 // Inverting it should produce one more sub-range.
3359 ASSERT_TRUE (big
.num_pairs () == nrange
+ 1);
3361 int_range
<1> tmp (INT (5), INT (37));
3362 big
.intersect (tmp
);
3363 ASSERT_TRUE (big
.num_pairs () == 4);
3365 // Test that [10,10][20,20] does NOT contain 15.
3367 int_range_max
i1 (build_int_cst (integer_type_node
, 10),
3368 build_int_cst (integer_type_node
, 10));
3369 int_range_max
i2 (build_int_cst (integer_type_node
, 20),
3370 build_int_cst (integer_type_node
, 20));
3372 ASSERT_FALSE (i1
.contains_p (build_int_cst (integer_type_node
, 15)));
3377 range_tests_legacy ()
3379 // Test truncating copy to int_range<1>.
3380 int_range
<3> big
= build_range3 (10, 20, 30, 40, 50, 60);
3381 int_range
<1> small
= big
;
3382 ASSERT_TRUE (small
== int_range
<1> (INT (10), INT (60)));
3384 // Test truncating copy to int_range<2>.
3385 int_range
<2> medium
= big
;
3386 ASSERT_TRUE (!medium
.undefined_p ());
3388 // Test that a truncating copy of [MIN,20][22,40][80,MAX]
3389 // ends up as a conservative anti-range of ~[21,21].
3390 big
= int_range
<3> (vrp_val_min (integer_type_node
), INT (20));
3391 big
.union_ (int_range
<1> (INT (22), INT (40)));
3392 big
.union_ (int_range
<1> (INT (80), vrp_val_max (integer_type_node
)));
3394 ASSERT_TRUE (small
== int_range
<1> (INT (21), INT (21), VR_ANTI_RANGE
));
3396 // Copying a legacy symbolic to an int_range should normalize the
3397 // symbolic at copy time.
3399 tree ssa
= make_ssa_name (integer_type_node
);
3400 value_range
legacy_range (ssa
, INT (25));
3401 int_range
<2> copy
= legacy_range
;
3402 ASSERT_TRUE (copy
== int_range
<2> (vrp_val_min (integer_type_node
),
3405 // Test that copying ~[abc_23, abc_23] to a multi-range yields varying.
3406 legacy_range
= value_range (ssa
, ssa
, VR_ANTI_RANGE
);
3407 copy
= legacy_range
;
3408 ASSERT_TRUE (copy
.varying_p ());
3411 // VARYING of different sizes should not be equal.
3412 tree big_type
= build_nonstandard_integer_type (32, 1);
3413 tree small_type
= build_nonstandard_integer_type (16, 1);
3414 int_range_max
r0 (big_type
);
3415 int_range_max
r1 (small_type
);
3416 ASSERT_TRUE (r0
!= r1
);
3417 value_range
vr0 (big_type
);
3418 int_range_max
vr1 (small_type
);
3419 ASSERT_TRUE (vr0
!= vr1
);
3422 // Simulate -fstrict-enums where the domain of a type is less than the
3426 range_tests_strict_enum ()
3428 // The enum can only hold [0, 3].
3429 tree rtype
= copy_node (unsigned_type_node
);
3430 TYPE_MIN_VALUE (rtype
) = build_int_cstu (rtype
, 0);
3431 TYPE_MAX_VALUE (rtype
) = build_int_cstu (rtype
, 3);
3433 // Test that even though vr1 covers the strict enum domain ([0, 3]),
3434 // it does not cover the domain of the underlying type.
3435 int_range
<1> vr1 (build_int_cstu (rtype
, 0), build_int_cstu (rtype
, 1));
3436 int_range
<1> vr2 (build_int_cstu (rtype
, 2), build_int_cstu (rtype
, 3));
3438 ASSERT_TRUE (vr1
== int_range
<1> (build_int_cstu (rtype
, 0),
3439 build_int_cstu (rtype
, 3)));
3440 ASSERT_FALSE (vr1
.varying_p ());
3442 // Test that copying to a multi-range does not change things.
3443 int_range
<2> ir1 (vr1
);
3444 ASSERT_TRUE (ir1
== vr1
);
3445 ASSERT_FALSE (ir1
.varying_p ());
3447 // The same test as above, but using TYPE_{MIN,MAX}_VALUE instead of [0,3].
3448 vr1
= int_range
<1> (TYPE_MIN_VALUE (rtype
), TYPE_MAX_VALUE (rtype
));
3450 ASSERT_TRUE (ir1
== vr1
);
3451 ASSERT_FALSE (ir1
.varying_p ());
3457 tree u128_type
= build_nonstandard_integer_type (128, /*unsigned=*/1);
3458 int_range
<1> i1
, i2
, i3
;
3459 int_range
<1> r0
, r1
, rold
;
3461 // Test 1-bit signed integer union.
3462 // [-1,-1] U [0,0] = VARYING.
3463 tree one_bit_type
= build_nonstandard_integer_type (1, 0);
3464 tree one_bit_min
= vrp_val_min (one_bit_type
);
3465 tree one_bit_max
= vrp_val_max (one_bit_type
);
3467 int_range
<2> min (one_bit_min
, one_bit_min
);
3468 int_range
<2> max (one_bit_max
, one_bit_max
);
3470 ASSERT_TRUE (max
.varying_p ());
3472 // Test that we can set a range of true+false for a 1-bit signed int.
3473 r0
= range_true_and_false (one_bit_type
);
3475 // Test inversion of 1-bit signed integers.
3477 int_range
<2> min (one_bit_min
, one_bit_min
);
3478 int_range
<2> max (one_bit_max
, one_bit_max
);
3482 ASSERT_TRUE (t
== max
);
3485 ASSERT_TRUE (t
== min
);
3488 // Test that NOT(255) is [0..254] in 8-bit land.
3489 int_range
<1> not_255 (UCHAR (255), UCHAR (255), VR_ANTI_RANGE
);
3490 ASSERT_TRUE (not_255
== int_range
<1> (UCHAR (0), UCHAR (254)));
3492 // Test that NOT(0) is [1..255] in 8-bit land.
3493 int_range
<1> not_zero
= range_nonzero (unsigned_char_type_node
);
3494 ASSERT_TRUE (not_zero
== int_range
<1> (UCHAR (1), UCHAR (255)));
3496 // Check that [0,127][0x..ffffff80,0x..ffffff]
3497 // => ~[128, 0x..ffffff7f].
3498 r0
= int_range
<1> (UINT128 (0), UINT128 (127));
3499 tree high
= build_minus_one_cst (u128_type
);
3500 // low = -1 - 127 => 0x..ffffff80.
3501 tree low
= fold_build2 (MINUS_EXPR
, u128_type
, high
, UINT128(127));
3502 r1
= int_range
<1> (low
, high
); // [0x..ffffff80, 0x..ffffffff]
3503 // r0 = [0,127][0x..ffffff80,0x..fffffff].
3505 // r1 = [128, 0x..ffffff7f].
3506 r1
= int_range
<1> (UINT128(128),
3507 fold_build2 (MINUS_EXPR
, u128_type
,
3508 build_minus_one_cst (u128_type
),
3511 ASSERT_TRUE (r0
== r1
);
3513 r0
.set_varying (integer_type_node
);
3514 tree minint
= wide_int_to_tree (integer_type_node
, r0
.lower_bound ());
3515 tree maxint
= wide_int_to_tree (integer_type_node
, r0
.upper_bound ());
3517 r0
.set_varying (short_integer_type_node
);
3519 r0
.set_varying (unsigned_type_node
);
3520 tree maxuint
= wide_int_to_tree (unsigned_type_node
, r0
.upper_bound ());
3522 // Check that ~[0,5] => [6,MAX] for unsigned int.
3523 r0
= int_range
<1> (UINT (0), UINT (5));
3525 ASSERT_TRUE (r0
== int_range
<1> (UINT(6), maxuint
));
3527 // Check that ~[10,MAX] => [0,9] for unsigned int.
3528 r0
= int_range
<1> (UINT(10), maxuint
);
3530 ASSERT_TRUE (r0
== int_range
<1> (UINT (0), UINT (9)));
3532 // Check that ~[0,5] => [6,MAX] for unsigned 128-bit numbers.
3533 r0
= int_range
<1> (UINT128 (0), UINT128 (5), VR_ANTI_RANGE
);
3534 r1
= int_range
<1> (UINT128(6), build_minus_one_cst (u128_type
));
3535 ASSERT_TRUE (r0
== r1
);
3537 // Check that [~5] is really [-MIN,4][6,MAX].
3538 r0
= int_range
<1> (INT (5), INT (5), VR_ANTI_RANGE
);
3539 r1
= int_range
<1> (minint
, INT (4));
3540 r1
.union_ (int_range
<1> (INT (6), maxint
));
3541 ASSERT_FALSE (r1
.undefined_p ());
3542 ASSERT_TRUE (r0
== r1
);
3544 r1
= int_range
<1> (INT (5), INT (5));
3545 int_range
<1> r2 (r1
);
3546 ASSERT_TRUE (r1
== r2
);
3548 r1
= int_range
<1> (INT (5), INT (10));
3550 r1
= int_range
<1> (integer_type_node
,
3551 wi::to_wide (INT (5)), wi::to_wide (INT (10)));
3552 ASSERT_TRUE (r1
.contains_p (INT (7)));
3554 r1
= int_range
<1> (SCHAR (0), SCHAR (20));
3555 ASSERT_TRUE (r1
.contains_p (SCHAR(15)));
3556 ASSERT_FALSE (r1
.contains_p (SCHAR(300)));
3558 // NOT([10,20]) ==> [-MIN,9][21,MAX].
3559 r0
= r1
= int_range
<1> (INT (10), INT (20));
3560 r2
= int_range
<1> (minint
, INT(9));
3561 r2
.union_ (int_range
<1> (INT(21), maxint
));
3562 ASSERT_FALSE (r2
.undefined_p ());
3564 ASSERT_TRUE (r1
== r2
);
3565 // Test that NOT(NOT(x)) == x.
3567 ASSERT_TRUE (r0
== r2
);
3569 // Test that booleans and their inverse work as expected.
3570 r0
= range_zero (boolean_type_node
);
3571 ASSERT_TRUE (r0
== int_range
<1> (build_zero_cst (boolean_type_node
),
3572 build_zero_cst (boolean_type_node
)));
3574 ASSERT_TRUE (r0
== int_range
<1> (build_one_cst (boolean_type_node
),
3575 build_one_cst (boolean_type_node
)));
3577 // Make sure NULL and non-NULL of pointer types work, and that
3578 // inverses of them are consistent.
3579 tree voidp
= build_pointer_type (void_type_node
);
3580 r0
= range_zero (voidp
);
3584 ASSERT_TRUE (r0
== r1
);
3586 // [10,20] U [15, 30] => [10, 30].
3587 r0
= int_range
<1> (INT (10), INT (20));
3588 r1
= int_range
<1> (INT (15), INT (30));
3590 ASSERT_TRUE (r0
== int_range
<1> (INT (10), INT (30)));
3592 // [15,40] U [] => [15,40].
3593 r0
= int_range
<1> (INT (15), INT (40));
3594 r1
.set_undefined ();
3596 ASSERT_TRUE (r0
== int_range
<1> (INT (15), INT (40)));
3598 // [10,20] U [10,10] => [10,20].
3599 r0
= int_range
<1> (INT (10), INT (20));
3600 r1
= int_range
<1> (INT (10), INT (10));
3602 ASSERT_TRUE (r0
== int_range
<1> (INT (10), INT (20)));
3604 // [10,20] U [9,9] => [9,20].
3605 r0
= int_range
<1> (INT (10), INT (20));
3606 r1
= int_range
<1> (INT (9), INT (9));
3608 ASSERT_TRUE (r0
== int_range
<1> (INT (9), INT (20)));
3610 // [10,20] ^ [15,30] => [15,20].
3611 r0
= int_range
<1> (INT (10), INT (20));
3612 r1
= int_range
<1> (INT (15), INT (30));
3614 ASSERT_TRUE (r0
== int_range
<1> (INT (15), INT (20)));
3616 // Test the internal sanity of wide_int's wrt HWIs.
3617 ASSERT_TRUE (wi::max_value (TYPE_PRECISION (boolean_type_node
),
3618 TYPE_SIGN (boolean_type_node
))
3619 == wi::uhwi (1, TYPE_PRECISION (boolean_type_node
)));
3622 r0
= int_range
<1> (INT (0), INT (0));
3623 ASSERT_TRUE (r0
.zero_p ());
3625 // Test nonzero_p().
3626 r0
= int_range
<1> (INT (0), INT (0));
3628 ASSERT_TRUE (r0
.nonzero_p ());
3630 // test legacy interaction
3632 r0
= int_range
<1> (UINT (1), UINT (1), VR_ANTI_RANGE
);
3634 r1
= int_range
<1> (UINT (3), UINT (3), VR_ANTI_RANGE
);
3636 // vv = [0,0][2,2][4, MAX]
3637 int_range
<3> vv
= r0
;
3640 ASSERT_TRUE (vv
.contains_p (UINT (2)));
3641 ASSERT_TRUE (vv
.num_pairs () == 3);
3643 // create r0 as legacy [1,1]
3644 r0
= int_range
<1> (UINT (1), UINT (1));
3645 // And union it with [0,0][2,2][4,MAX] multi range
3647 // The result should be [0,2][4,MAX], or ~[3,3] but it must contain 2
3648 ASSERT_TRUE (r0
.contains_p (UINT (2)));
3652 range_tests_nonzero_bits ()
3654 int_range
<2> r0
, r1
;
3656 // Adding nonzero bits to a varying drops the varying.
3657 r0
.set_varying (integer_type_node
);
3658 r0
.set_nonzero_bits (255);
3659 ASSERT_TRUE (!r0
.varying_p ());
3660 // Dropping the nonzero bits brings us back to varying.
3661 r0
.set_nonzero_bits (-1);
3662 ASSERT_TRUE (r0
.varying_p ());
3664 // Test contains_p with nonzero bits.
3665 r0
.set_zero (integer_type_node
);
3666 ASSERT_TRUE (r0
.contains_p (INT (0)));
3667 ASSERT_FALSE (r0
.contains_p (INT (1)));
3668 r0
.set_nonzero_bits (0xfe);
3669 ASSERT_FALSE (r0
.contains_p (INT (0x100)));
3670 ASSERT_FALSE (r0
.contains_p (INT (0x3)));
3672 // Union of nonzero bits.
3673 r0
.set_varying (integer_type_node
);
3674 r0
.set_nonzero_bits (0xf0);
3675 r1
.set_varying (integer_type_node
);
3676 r1
.set_nonzero_bits (0xf);
3678 ASSERT_TRUE (r0
.get_nonzero_bits () == 0xff);
3680 // Intersect of nonzero bits.
3681 r0
.set (INT (0), INT (255));
3682 r0
.set_nonzero_bits (0xfe);
3683 r1
.set_varying (integer_type_node
);
3684 r1
.set_nonzero_bits (0xf0);
3686 ASSERT_TRUE (r0
.get_nonzero_bits () == 0xf0);
3688 // Intersect where the mask of nonzero bits is implicit from the range.
3689 r0
.set_varying (integer_type_node
);
3690 r1
.set (INT (0), INT (255));
3692 ASSERT_TRUE (r0
.get_nonzero_bits () == 0xff);
3694 // The union of a mask of 0xff..ffff00 with a mask of 0xff spans the
3695 // entire domain, and makes the range a varying.
3696 r0
.set_varying (integer_type_node
);
3697 wide_int x
= wi::shwi (0xff, TYPE_PRECISION (integer_type_node
));
3698 x
= wi::bit_not (x
);
3699 r0
.set_nonzero_bits (x
); // 0xff..ff00
3700 r1
.set_varying (integer_type_node
);
3701 r1
.set_nonzero_bits (0xff);
3703 ASSERT_TRUE (r0
.varying_p ());
3705 // Test that setting a nonzero bit of 1 does not pessimize the range.
3706 r0
.set_zero (integer_type_node
);
3707 r0
.set_nonzero_bits (1);
3708 ASSERT_TRUE (r0
.zero_p ());
3711 // Build an frange from string endpoints.
3713 static inline frange
3714 frange_float (const char *lb
, const char *ub
, tree type
= float_type_node
)
3716 REAL_VALUE_TYPE min
, max
;
3717 gcc_assert (real_from_string (&min
, lb
) == 0);
3718 gcc_assert (real_from_string (&max
, ub
) == 0);
3719 return frange (type
, min
, max
);
3726 REAL_VALUE_TYPE q
, r
;
3729 // Equal ranges but with differing NAN bits are not equal.
3730 if (HONOR_NANS (float_type_node
))
3732 r1
= frange_float ("10", "12");
3740 // [10, 20] NAN ^ [30, 40] NAN = NAN.
3741 r0
= frange_float ("10", "20");
3742 r1
= frange_float ("30", "40");
3744 ASSERT_TRUE (r0
.known_isnan ());
3746 // [3,5] U [5,10] NAN = ... NAN
3747 r0
= frange_float ("3", "5");
3749 r1
= frange_float ("5", "10");
3751 ASSERT_TRUE (r0
.maybe_isnan ());
3754 // NAN ranges are not equal to each other.
3755 r0
.set_nan (float_type_node
);
3757 ASSERT_FALSE (r0
== r1
);
3758 ASSERT_FALSE (r0
== r0
);
3759 ASSERT_TRUE (r0
!= r0
);
3761 // [5,6] U NAN = [5,6] NAN.
3762 r0
= frange_float ("5", "6");
3764 r1
.set_nan (float_type_node
);
3766 real_from_string (&q
, "5");
3767 real_from_string (&r
, "6");
3768 ASSERT_TRUE (real_identical (&q
, &r0
.lower_bound ()));
3769 ASSERT_TRUE (real_identical (&r
, &r0
.upper_bound ()));
3770 ASSERT_TRUE (r0
.maybe_isnan ());
3773 r0
.set_nan (float_type_node
);
3774 r1
.set_nan (float_type_node
);
3776 ASSERT_TRUE (r0
.known_isnan ());
3778 // [INF, INF] NAN ^ NAN = NAN
3779 r0
.set_nan (float_type_node
);
3780 r1
= frange_float ("+Inf", "+Inf");
3781 if (!HONOR_NANS (float_type_node
))
3784 ASSERT_TRUE (r0
.known_isnan ());
3787 r0
.set_nan (float_type_node
);
3788 r1
.set_nan (float_type_node
);
3790 ASSERT_TRUE (r0
.known_isnan ());
3792 // +NAN ^ -NAN = UNDEFINED
3793 r0
.set_nan (float_type_node
, false);
3794 r1
.set_nan (float_type_node
, true);
3796 ASSERT_TRUE (r0
.undefined_p ());
3798 // VARYING ^ NAN = NAN.
3799 r0
.set_nan (float_type_node
);
3800 r1
.set_varying (float_type_node
);
3802 ASSERT_TRUE (r0
.known_isnan ());
3804 // [3,4] ^ NAN = UNDEFINED.
3805 r0
= frange_float ("3", "4");
3807 r1
.set_nan (float_type_node
);
3809 ASSERT_TRUE (r0
.undefined_p ());
3811 // [-3, 5] ^ NAN = UNDEFINED
3812 r0
= frange_float ("-3", "5");
3814 r1
.set_nan (float_type_node
);
3816 ASSERT_TRUE (r0
.undefined_p ());
3818 // Setting the NAN bit to yes does not make us a known NAN.
3819 r0
.set_varying (float_type_node
);
3821 ASSERT_FALSE (r0
.known_isnan ());
3823 // NAN is in a VARYING.
3824 r0
.set_varying (float_type_node
);
3825 real_nan (&r
, "", 1, TYPE_MODE (float_type_node
));
3826 tree nan
= build_real (float_type_node
, r
);
3827 ASSERT_TRUE (r0
.contains_p (nan
));
3829 // -NAN is in a VARYING.
3830 r0
.set_varying (float_type_node
);
3831 q
= real_value_negate (&r
);
3832 tree neg_nan
= build_real (float_type_node
, q
);
3833 ASSERT_TRUE (r0
.contains_p (neg_nan
));
3835 // Clearing the NAN on a [] NAN is the empty set.
3836 r0
.set_nan (float_type_node
);
3838 ASSERT_TRUE (r0
.undefined_p ());
3840 // [10,20] NAN ^ [21,25] NAN = [NAN]
3841 r0
= frange_float ("10", "20");
3843 r1
= frange_float ("21", "25");
3846 ASSERT_TRUE (r0
.known_isnan ());
3848 // NAN U [5,6] should be [5,6] +-NAN.
3849 r0
.set_nan (float_type_node
);
3850 r1
= frange_float ("5", "6");
3853 real_from_string (&q
, "5");
3854 real_from_string (&r
, "6");
3855 ASSERT_TRUE (real_identical (&q
, &r0
.lower_bound ()));
3856 ASSERT_TRUE (real_identical (&r
, &r0
.upper_bound ()));
3857 ASSERT_TRUE (!r0
.signbit_p (signbit
));
3858 ASSERT_TRUE (r0
.maybe_isnan ());
3862 range_tests_signed_zeros ()
3864 tree zero
= build_zero_cst (float_type_node
);
3865 tree neg_zero
= fold_build1 (NEGATE_EXPR
, float_type_node
, zero
);
3869 // [0,0] contains [0,0] but not [-0,-0] and vice versa.
3870 r0
= frange (zero
, zero
);
3871 r1
= frange (neg_zero
, neg_zero
);
3872 ASSERT_TRUE (r0
.contains_p (zero
));
3873 ASSERT_TRUE (!r0
.contains_p (neg_zero
));
3874 ASSERT_TRUE (r1
.contains_p (neg_zero
));
3875 ASSERT_TRUE (!r1
.contains_p (zero
));
3877 // Test contains_p() when we know the sign of the zero.
3878 r0
= frange (zero
, zero
);
3879 ASSERT_TRUE (r0
.contains_p (zero
));
3880 ASSERT_FALSE (r0
.contains_p (neg_zero
));
3881 r0
= frange (neg_zero
, neg_zero
);
3882 ASSERT_TRUE (r0
.contains_p (neg_zero
));
3883 ASSERT_FALSE (r0
.contains_p (zero
));
3885 r0
= frange (neg_zero
, zero
);
3886 ASSERT_TRUE (r0
.contains_p (neg_zero
));
3887 ASSERT_TRUE (r0
.contains_p (zero
));
3889 r0
= frange_float ("-3", "5");
3890 ASSERT_TRUE (r0
.contains_p (neg_zero
));
3891 ASSERT_TRUE (r0
.contains_p (zero
));
3893 // The intersection of zeros that differ in sign is a NAN (or
3894 // undefined if not honoring NANs).
3895 r0
= frange (neg_zero
, neg_zero
);
3896 r1
= frange (zero
, zero
);
3898 if (HONOR_NANS (float_type_node
))
3899 ASSERT_TRUE (r0
.known_isnan ());
3901 ASSERT_TRUE (r0
.undefined_p ());
3903 // The union of zeros that differ in sign is a zero with unknown sign.
3904 r0
= frange (zero
, zero
);
3905 r1
= frange (neg_zero
, neg_zero
);
3907 ASSERT_TRUE (r0
.zero_p () && !r0
.signbit_p (signbit
));
3909 // [-0, +0] has an unknown sign.
3910 r0
= frange (neg_zero
, zero
);
3911 ASSERT_TRUE (r0
.zero_p () && !r0
.signbit_p (signbit
));
3913 // [-0, +0] ^ [0, 0] is [0, 0]
3914 r0
= frange (neg_zero
, zero
);
3915 r1
= frange (zero
, zero
);
3917 ASSERT_TRUE (r0
.zero_p ());
3919 r0
= frange_float ("+0", "5");
3921 ASSERT_TRUE (r0
.signbit_p (signbit
) && !signbit
);
3923 r0
= frange_float ("-0", "5");
3925 ASSERT_TRUE (!r0
.signbit_p (signbit
));
3927 r0
= frange_float ("-0", "10");
3928 r1
= frange_float ("0", "5");
3930 ASSERT_TRUE (real_iszero (&r0
.lower_bound (), false));
3932 r0
= frange_float ("-0", "5");
3933 r1
= frange_float ("0", "5");
3935 ASSERT_TRUE (real_iszero (&r0
.lower_bound (), true));
3937 r0
= frange_float ("-5", "-0");
3939 r1
= frange_float ("0", "0");
3942 if (HONOR_NANS (float_type_node
))
3943 ASSERT_TRUE (r0
.known_isnan ());
3945 ASSERT_TRUE (r0
.undefined_p ());
3947 r0
.set_nonnegative (float_type_node
);
3948 if (HONOR_NANS (float_type_node
))
3949 ASSERT_TRUE (r0
.maybe_isnan ());
3951 // Numbers containing zero should have an unknown SIGNBIT.
3952 r0
= frange_float ("0", "10");
3954 ASSERT_TRUE (r0
.signbit_p (signbit
) && !signbit
);
3958 range_tests_signbit ()
3963 // Negative numbers should have the SIGNBIT set.
3964 r0
= frange_float ("-5", "-1");
3966 ASSERT_TRUE (r0
.signbit_p (signbit
) && signbit
);
3967 // Positive numbers should have the SIGNBIT clear.
3968 r0
= frange_float ("1", "10");
3970 ASSERT_TRUE (r0
.signbit_p (signbit
) && !signbit
);
3971 // Numbers spanning both positive and negative should have an
3973 r0
= frange_float ("-10", "10");
3975 ASSERT_TRUE (!r0
.signbit_p (signbit
));
3976 r0
.set_varying (float_type_node
);
3977 ASSERT_TRUE (!r0
.signbit_p (signbit
));
3981 range_tests_floats ()
3985 if (HONOR_NANS (float_type_node
))
3987 range_tests_signbit ();
3989 if (HONOR_SIGNED_ZEROS (float_type_node
))
3990 range_tests_signed_zeros ();
3992 // A range of [-INF,+INF] is actually VARYING if no other properties
3994 r0
= frange_float ("-Inf", "+Inf");
3995 ASSERT_TRUE (r0
.varying_p ());
3996 // ...unless it has some special property...
3997 if (HONOR_NANS (r0
.type ()))
4000 ASSERT_FALSE (r0
.varying_p ());
4003 // For most architectures, where float and double are different
4004 // sizes, having the same endpoints does not necessarily mean the
4005 // ranges are equal.
4006 if (!types_compatible_p (float_type_node
, double_type_node
))
4008 r0
= frange_float ("3.0", "3.0", float_type_node
);
4009 r1
= frange_float ("3.0", "3.0", double_type_node
);
4013 // [3,5] U [10,12] = [3,12].
4014 r0
= frange_float ("3", "5");
4015 r1
= frange_float ("10", "12");
4017 ASSERT_EQ (r0
, frange_float ("3", "12"));
4019 // [5,10] U [4,8] = [4,10]
4020 r0
= frange_float ("5", "10");
4021 r1
= frange_float ("4", "8");
4023 ASSERT_EQ (r0
, frange_float ("4", "10"));
4025 // [3,5] U [4,10] = [3,10]
4026 r0
= frange_float ("3", "5");
4027 r1
= frange_float ("4", "10");
4029 ASSERT_EQ (r0
, frange_float ("3", "10"));
4031 // [4,10] U [5,11] = [4,11]
4032 r0
= frange_float ("4", "10");
4033 r1
= frange_float ("5", "11");
4035 ASSERT_EQ (r0
, frange_float ("4", "11"));
4037 // [3,12] ^ [10,12] = [10,12].
4038 r0
= frange_float ("3", "12");
4039 r1
= frange_float ("10", "12");
4041 ASSERT_EQ (r0
, frange_float ("10", "12"));
4043 // [10,12] ^ [11,11] = [11,11]
4044 r0
= frange_float ("10", "12");
4045 r1
= frange_float ("11", "11");
4047 ASSERT_EQ (r0
, frange_float ("11", "11"));
4049 // [10,20] ^ [5,15] = [10,15]
4050 r0
= frange_float ("10", "20");
4051 r1
= frange_float ("5", "15");
4053 ASSERT_EQ (r0
, frange_float ("10", "15"));
4055 // [10,20] ^ [15,25] = [15,20]
4056 r0
= frange_float ("10", "20");
4057 r1
= frange_float ("15", "25");
4059 ASSERT_EQ (r0
, frange_float ("15", "20"));
4061 // [10,20] ^ [21,25] = []
4062 r0
= frange_float ("10", "20");
4064 r1
= frange_float ("21", "25");
4067 ASSERT_TRUE (r0
.undefined_p ());
4069 if (HONOR_INFINITIES (float_type_node
))
4071 // Make sure [-Inf, -Inf] doesn't get normalized.
4072 r0
= frange_float ("-Inf", "-Inf");
4073 ASSERT_TRUE (real_isinf (&r0
.lower_bound (), true));
4074 ASSERT_TRUE (real_isinf (&r0
.upper_bound (), true));
4077 // Test that reading back a global range yields the same result as
4078 // what we wrote into it.
4079 tree ssa
= make_temp_ssa_name (float_type_node
, NULL
, "blah");
4080 r0
.set_varying (float_type_node
);
4082 set_range_info (ssa
, r0
);
4083 get_global_range_query ()->range_of_expr (r1
, ssa
);
4087 // Run floating range tests for various combinations of NAN and INF
4091 range_tests_floats_various ()
4093 int save_finite_math_only
= flag_finite_math_only
;
4095 // Test -ffinite-math-only.
4096 flag_finite_math_only
= 1;
4097 range_tests_floats ();
4098 // Test -fno-finite-math-only.
4099 flag_finite_math_only
= 0;
4100 range_tests_floats ();
4102 flag_finite_math_only
= save_finite_math_only
;
4108 range_tests_legacy ();
4109 range_tests_irange3 ();
4110 range_tests_int_range_max ();
4111 range_tests_strict_enum ();
4112 range_tests_nonzero_bits ();
4113 range_tests_floats_various ();
4114 range_tests_misc ();
4117 } // namespace selftest
4119 #endif // CHECKING_P