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
));
368 // Setter for an frange defaulting the NAN possibility to +-NAN when
372 frange::set (tree type
,
373 const REAL_VALUE_TYPE
&min
, const REAL_VALUE_TYPE
&max
,
374 value_range_kind kind
)
377 set (type
, min
, max
, nan
, kind
);
381 frange::set (tree min
, tree max
, value_range_kind kind
)
383 set (TREE_TYPE (min
),
384 *TREE_REAL_CST_PTR (min
), *TREE_REAL_CST_PTR (max
), kind
);
387 // Normalize range to VARYING or UNDEFINED, or vice versa. Return
388 // TRUE if anything changed.
390 // A range with no known properties can be dropped to VARYING.
391 // Similarly, a VARYING with any properties should be dropped to a
392 // VR_RANGE. Normalizing ranges upon changing them ensures there is
393 // only one representation for a given range.
396 frange::normalize_kind ()
398 if (m_kind
== VR_RANGE
399 && frange_val_is_min (m_min
, m_type
)
400 && frange_val_is_max (m_max
, m_type
))
402 if (!HONOR_NANS (m_type
) || (m_pos_nan
&& m_neg_nan
))
404 set_varying (m_type
);
408 else if (m_kind
== VR_VARYING
)
410 if (HONOR_NANS (m_type
) && (!m_pos_nan
|| !m_neg_nan
))
413 m_min
= frange_val_min (m_type
);
414 m_max
= frange_val_max (m_type
);
418 else if (m_kind
== VR_NAN
&& !m_pos_nan
&& !m_neg_nan
)
423 // Union or intersect the zero endpoints of two ranges. For example:
424 // [-0, x] U [+0, x] => [-0, x]
425 // [ x, -0] U [ x, +0] => [ x, +0]
426 // [-0, x] ^ [+0, x] => [+0, x]
427 // [ x, -0] ^ [ x, +0] => [ x, -0]
429 // UNION_P is true when performing a union, or false when intersecting.
432 frange::combine_zeros (const frange
&r
, bool union_p
)
434 gcc_checking_assert (!undefined_p () && !known_isnan ());
436 bool changed
= false;
437 if (real_iszero (&m_min
) && real_iszero (&r
.m_min
)
438 && real_isneg (&m_min
) != real_isneg (&r
.m_min
))
440 m_min
.sign
= union_p
;
443 if (real_iszero (&m_max
) && real_iszero (&r
.m_max
)
444 && real_isneg (&m_max
) != real_isneg (&r
.m_max
))
446 m_max
.sign
= !union_p
;
449 // If the signs are swapped, the resulting range is empty.
450 if (m_min
.sign
== 0 && m_max
.sign
== 1)
461 // Union two ranges when one is known to be a NAN.
464 frange::union_nans (const frange
&r
)
466 gcc_checking_assert (known_isnan () || r
.known_isnan ());
474 m_pos_nan
|= r
.m_pos_nan
;
475 m_neg_nan
|= r
.m_neg_nan
;
483 frange::union_ (const vrange
&v
)
485 const frange
&r
= as_a
<frange
> (v
);
487 if (r
.undefined_p () || varying_p ())
489 if (undefined_p () || r
.varying_p ())
496 if (known_isnan () || r
.known_isnan ())
497 return union_nans (r
);
498 bool changed
= false;
499 if (m_pos_nan
!= r
.m_pos_nan
|| m_neg_nan
!= r
.m_neg_nan
)
501 m_pos_nan
|= r
.m_pos_nan
;
502 m_neg_nan
|= r
.m_neg_nan
;
506 // Combine endpoints.
507 if (real_less (&r
.m_min
, &m_min
))
512 if (real_less (&m_max
, &r
.m_max
))
518 if (HONOR_SIGNED_ZEROS (m_type
))
519 changed
|= combine_zeros (r
, true);
521 changed
|= normalize_kind ();
527 // Intersect two ranges when one is known to be a NAN.
530 frange::intersect_nans (const frange
&r
)
532 gcc_checking_assert (known_isnan () || r
.known_isnan ());
534 m_pos_nan
&= r
.m_pos_nan
;
535 m_neg_nan
&= r
.m_neg_nan
;
546 frange::intersect (const vrange
&v
)
548 const frange
&r
= as_a
<frange
> (v
);
550 if (undefined_p () || r
.varying_p ())
552 if (r
.undefined_p ())
564 if (known_isnan () || r
.known_isnan ())
565 return intersect_nans (r
);
566 bool changed
= false;
567 if (m_pos_nan
!= r
.m_pos_nan
|| m_neg_nan
!= r
.m_neg_nan
)
569 m_pos_nan
&= r
.m_pos_nan
;
570 m_neg_nan
&= r
.m_neg_nan
;
574 // Combine endpoints.
575 if (real_less (&m_min
, &r
.m_min
))
580 if (real_less (&r
.m_max
, &m_max
))
585 // If the endpoints are swapped, the resulting range is empty.
586 if (real_less (&m_max
, &m_min
))
597 if (HONOR_SIGNED_ZEROS (m_type
))
598 changed
|= combine_zeros (r
, false);
600 changed
|= normalize_kind ();
607 frange::operator= (const frange
&src
)
613 m_pos_nan
= src
.m_pos_nan
;
614 m_neg_nan
= src
.m_neg_nan
;
622 frange::operator== (const frange
&src
) const
624 if (m_kind
== src
.m_kind
)
630 return types_compatible_p (m_type
, src
.m_type
);
632 if (known_isnan () || src
.known_isnan ())
635 return (real_identical (&m_min
, &src
.m_min
)
636 && real_identical (&m_max
, &src
.m_max
)
637 && m_pos_nan
== src
.m_pos_nan
638 && m_neg_nan
== src
.m_neg_nan
639 && types_compatible_p (m_type
, src
.m_type
));
644 // Return TRUE if range contains the TREE_REAL_CST_PTR in CST.
647 frange::contains_p (tree cst
) const
649 gcc_checking_assert (m_kind
!= VR_ANTI_RANGE
);
650 const REAL_VALUE_TYPE
*rv
= TREE_REAL_CST_PTR (cst
);
661 if (!m_pos_nan
&& !m_neg_nan
)
663 // Both +NAN and -NAN are present.
664 if (m_pos_nan
&& m_neg_nan
)
666 return m_neg_nan
== rv
->sign
;
671 if (real_compare (GE_EXPR
, rv
, &m_min
) && real_compare (LE_EXPR
, rv
, &m_max
))
673 // Make sure the signs are equal for signed zeros.
674 if (HONOR_SIGNED_ZEROS (m_type
) && real_iszero (rv
))
675 return rv
->sign
== m_min
.sign
|| rv
->sign
== m_max
.sign
;
681 // If range is a singleton, place it in RESULT and return TRUE. If
682 // RESULT is NULL, just return TRUE.
684 // A NAN can never be a singleton.
687 frange::singleton_p (tree
*result
) const
689 if (m_kind
== VR_RANGE
&& real_identical (&m_min
, &m_max
))
691 // Return false for any singleton that may be a NAN.
692 if (HONOR_NANS (m_type
) && maybe_isnan ())
695 if (MODE_COMPOSITE_P (TYPE_MODE (m_type
)))
697 // For IBM long doubles, if the value is +-Inf or is exactly
698 // representable in double, the other double could be +0.0
699 // or -0.0. Since this means there is more than one way to
700 // represent a value, return false to avoid propagating it.
701 // See libgcc/config/rs6000/ibm-ldouble-format for details.
702 if (real_isinf (&m_min
))
705 real_convert (&r
, DFmode
, &m_min
);
706 if (real_identical (&r
, &m_min
))
711 *result
= build_real (m_type
, m_min
);
718 frange::supports_type_p (const_tree type
) const
720 return supports_p (type
);
724 frange::verify_range ()
727 gcc_checking_assert (HONOR_NANS (m_type
) || !maybe_isnan ());
731 gcc_checking_assert (!m_type
);
734 gcc_checking_assert (m_type
);
735 gcc_checking_assert (frange_val_is_min (m_min
, m_type
));
736 gcc_checking_assert (frange_val_is_max (m_max
, m_type
));
737 if (HONOR_NANS (m_type
))
738 gcc_checking_assert (m_pos_nan
&& m_neg_nan
);
740 gcc_checking_assert (!m_pos_nan
&& !m_neg_nan
);
743 gcc_checking_assert (m_type
);
746 gcc_checking_assert (m_type
);
747 gcc_checking_assert (m_pos_nan
|| m_neg_nan
);
753 // NANs cannot appear in the endpoints of a range.
754 gcc_checking_assert (!real_isnan (&m_min
) && !real_isnan (&m_max
));
756 // Make sure we don't have swapped ranges.
757 gcc_checking_assert (!real_less (&m_max
, &m_min
));
759 // [ +0.0, -0.0 ] is nonsensical.
760 gcc_checking_assert (!(real_iszero (&m_min
, 0) && real_iszero (&m_max
, 1)));
762 // If all the properties are clear, we better not span the entire
763 // domain, because that would make us varying.
764 if (m_pos_nan
&& m_neg_nan
)
765 gcc_checking_assert (!frange_val_is_min (m_min
, m_type
)
766 || !frange_val_is_max (m_max
, m_type
));
769 // We can't do much with nonzeros yet.
771 frange::set_nonzero (tree type
)
776 // We can't do much with nonzeros yet.
778 frange::nonzero_p () const
783 // Set range to [+0.0, +0.0] if honoring signed zeros, or [0.0, 0.0]
787 frange::set_zero (tree type
)
789 if (HONOR_SIGNED_ZEROS (type
))
791 REAL_VALUE_TYPE dconstm0
= dconst0
;
793 set (type
, dconstm0
, dconst0
);
797 set (type
, dconst0
, dconst0
);
800 // Return TRUE for any zero regardless of sign.
803 frange::zero_p () const
805 return (m_kind
== VR_RANGE
806 && real_iszero (&m_min
)
807 && real_iszero (&m_max
));
810 // Set the range to non-negative numbers, that is [+0.0, +INF].
812 // The NAN in the resulting range (if HONOR_NANS) has a varying sign
813 // as there are no guarantees in IEEE 754 wrt to the sign of a NAN,
814 // except for copy, abs, and copysign. It is the responsibility of
815 // the caller to set the NAN's sign if desired.
818 frange::set_nonnegative (tree type
)
820 set (type
, dconst0
, frange_val_max (type
));
823 // Here we copy between any two irange's. The ranges can be legacy or
824 // multi-ranges, and copying between any combination works correctly.
827 irange::operator= (const irange
&src
)
829 if (legacy_mode_p ())
831 copy_to_legacy (src
);
834 if (src
.legacy_mode_p ())
836 copy_legacy_to_multi_range (src
);
841 unsigned lim
= src
.m_num_ranges
;
842 if (lim
> m_max_ranges
)
845 for (x
= 0; x
< lim
* 2; ++x
)
846 m_base
[x
] = src
.m_base
[x
];
848 // If the range didn't fit, the last range should cover the rest.
849 if (lim
!= src
.m_num_ranges
)
850 m_base
[x
- 1] = src
.m_base
[src
.m_num_ranges
* 2 - 1];
854 m_nonzero_mask
= src
.m_nonzero_mask
;
860 // Return TRUE if range is a multi-range that can be represented as a
864 irange::maybe_anti_range () const
866 tree ttype
= type ();
867 unsigned int precision
= TYPE_PRECISION (ttype
);
868 signop sign
= TYPE_SIGN (ttype
);
869 return (num_pairs () > 1
871 && lower_bound () == wi::min_value (precision
, sign
)
872 && upper_bound () == wi::max_value (precision
, sign
));
876 irange::copy_legacy_to_multi_range (const irange
&src
)
878 gcc_checking_assert (src
.legacy_mode_p ());
879 gcc_checking_assert (!legacy_mode_p ());
880 if (src
.undefined_p ())
882 else if (src
.varying_p ())
883 set_varying (src
.type ());
886 if (range_has_numeric_bounds_p (&src
))
887 set (src
.min (), src
.max (), src
.kind ());
890 value_range
cst (src
);
891 cst
.normalize_symbolics ();
892 gcc_checking_assert (cst
.varying_p () || cst
.kind () == VR_RANGE
);
893 set (cst
.min (), cst
.max ());
898 // Copy any type of irange into a legacy.
901 irange::copy_to_legacy (const irange
&src
)
903 gcc_checking_assert (legacy_mode_p ());
904 // Handle legacy to legacy and other things that are easy to copy.
905 if (src
.legacy_mode_p () || src
.varying_p () || src
.undefined_p ())
907 m_num_ranges
= src
.m_num_ranges
;
908 m_base
[0] = src
.m_base
[0];
909 m_base
[1] = src
.m_base
[1];
911 m_nonzero_mask
= src
.m_nonzero_mask
;
914 // Copy multi-range to legacy.
915 if (src
.maybe_anti_range ())
917 int_range
<3> r (src
);
919 // Use tree variants to save on tree -> wi -> tree conversions.
920 set (r
.tree_lower_bound (0), r
.tree_upper_bound (0), VR_ANTI_RANGE
);
923 set (src
.tree_lower_bound (), src
.tree_upper_bound ());
926 // Swap MIN/MAX if they are out of order and adjust KIND appropriately.
929 swap_out_of_order_endpoints (tree
&min
, tree
&max
, value_range_kind
&kind
)
931 gcc_checking_assert (kind
!= VR_UNDEFINED
);
932 if (kind
== VR_VARYING
)
934 /* Wrong order for min and max, to swap them and the VR type we need
936 if (tree_int_cst_lt (max
, min
))
940 /* For one bit precision if max < min, then the swapped
941 range covers all values, so for VR_RANGE it is varying and
942 for VR_ANTI_RANGE empty range, so drop to varying as well. */
943 if (TYPE_PRECISION (TREE_TYPE (min
)) == 1)
949 one
= build_int_cst (TREE_TYPE (min
), 1);
950 tmp
= int_const_binop (PLUS_EXPR
, max
, one
);
951 max
= int_const_binop (MINUS_EXPR
, min
, one
);
954 /* There's one corner case, if we had [C+1, C] before we now have
955 that again. But this represents an empty value range, so drop
956 to varying in this case. */
957 if (tree_int_cst_lt (max
, min
))
962 kind
= kind
== VR_RANGE
? VR_ANTI_RANGE
: VR_RANGE
;
967 irange::irange_set (tree min
, tree max
)
969 gcc_checking_assert (!POLY_INT_CST_P (min
));
970 gcc_checking_assert (!POLY_INT_CST_P (max
));
976 m_nonzero_mask
= NULL
;
984 irange::irange_set_1bit_anti_range (tree min
, tree max
)
986 tree type
= TREE_TYPE (min
);
987 gcc_checking_assert (TYPE_PRECISION (type
) == 1);
989 if (operand_equal_p (min
, max
))
991 // Since these are 1-bit quantities, they can only be [MIN,MIN]
993 if (vrp_val_is_min (min
))
994 min
= max
= vrp_val_max (type
);
996 min
= max
= vrp_val_min (type
);
1001 // The only alternative is [MIN,MAX], which is the empty range.
1002 gcc_checking_assert (vrp_val_is_min (min
));
1003 gcc_checking_assert (vrp_val_is_max (max
));
1011 irange::irange_set_anti_range (tree min
, tree max
)
1013 gcc_checking_assert (!POLY_INT_CST_P (min
));
1014 gcc_checking_assert (!POLY_INT_CST_P (max
));
1016 if (TYPE_PRECISION (TREE_TYPE (min
)) == 1)
1018 irange_set_1bit_anti_range (min
, max
);
1022 // set an anti-range
1023 tree type
= TREE_TYPE (min
);
1024 signop sign
= TYPE_SIGN (type
);
1025 int_range
<2> type_range (type
);
1026 // Calculate INVERSE([I,J]) as [-MIN, I-1][J+1, +MAX].
1028 wi::overflow_type ovf
;
1030 wide_int w_min
= wi::to_wide (min
);
1031 if (wi::ne_p (w_min
, type_range
.lower_bound ()))
1033 wide_int lim1
= wi::sub (w_min
, 1, sign
, &ovf
);
1034 gcc_checking_assert (ovf
!= wi::OVF_OVERFLOW
);
1035 m_base
[0] = type_range
.tree_lower_bound (0);
1036 m_base
[1] = wide_int_to_tree (type
, lim1
);
1039 wide_int w_max
= wi::to_wide (max
);
1040 if (wi::ne_p (w_max
, type_range
.upper_bound ()))
1042 wide_int lim2
= wi::add (w_max
, 1, sign
, &ovf
);
1043 gcc_checking_assert (ovf
!= wi::OVF_OVERFLOW
);
1044 m_base
[m_num_ranges
* 2] = wide_int_to_tree (type
, lim2
);
1045 m_base
[m_num_ranges
* 2 + 1] = type_range
.tree_upper_bound (0);
1050 m_nonzero_mask
= NULL
;
1057 /* Set value range to the canonical form of {VRTYPE, MIN, MAX, EQUIV}.
1058 This means adjusting VRTYPE, MIN and MAX representing the case of a
1059 wrapping range with MAX < MIN covering [MIN, type_max] U [type_min, MAX]
1060 as anti-rage ~[MAX+1, MIN-1]. Likewise for wrapping anti-ranges.
1061 In corner cases where MAX+1 or MIN-1 wraps this will fall back
1063 This routine exists to ease canonicalization in the case where we
1064 extract ranges from var + CST op limit. */
1067 irange::set (tree min
, tree max
, value_range_kind kind
)
1069 if (kind
== VR_UNDEFINED
)
1071 irange::set_undefined ();
1075 if (kind
== VR_VARYING
1076 || POLY_INT_CST_P (min
)
1077 || POLY_INT_CST_P (max
))
1079 set_varying (TREE_TYPE (min
));
1083 if (TREE_OVERFLOW_P (min
))
1084 min
= drop_tree_overflow (min
);
1085 if (TREE_OVERFLOW_P (max
))
1086 max
= drop_tree_overflow (max
);
1088 if (!legacy_mode_p ())
1090 if (kind
== VR_RANGE
)
1091 irange_set (min
, max
);
1094 gcc_checking_assert (kind
== VR_ANTI_RANGE
);
1095 irange_set_anti_range (min
, max
);
1099 // Nothing to canonicalize for symbolic ranges.
1100 if (TREE_CODE (min
) != INTEGER_CST
1101 || TREE_CODE (max
) != INTEGER_CST
)
1107 m_nonzero_mask
= NULL
;
1111 swap_out_of_order_endpoints (min
, max
, kind
);
1112 if (kind
== VR_VARYING
)
1114 set_varying (TREE_TYPE (min
));
1118 // Anti-ranges that can be represented as ranges should be so.
1119 if (kind
== VR_ANTI_RANGE
)
1121 bool is_min
= vrp_val_is_min (min
);
1122 bool is_max
= vrp_val_is_max (max
);
1124 if (is_min
&& is_max
)
1126 // Fall through. This will either be normalized as
1127 // VR_UNDEFINED if the anti-range spans the entire
1128 // precision, or it will remain an VR_ANTI_RANGE in the case
1129 // of an -fstrict-enum where [MIN,MAX] is less than the span
1130 // of underlying precision.
1132 else if (TYPE_PRECISION (TREE_TYPE (min
)) == 1)
1134 irange_set_1bit_anti_range (min
, max
);
1139 tree one
= build_int_cst (TREE_TYPE (max
), 1);
1140 min
= int_const_binop (PLUS_EXPR
, max
, one
);
1141 max
= vrp_val_max (TREE_TYPE (max
));
1146 tree one
= build_int_cst (TREE_TYPE (min
), 1);
1147 max
= int_const_binop (MINUS_EXPR
, min
, one
);
1148 min
= vrp_val_min (TREE_TYPE (min
));
1157 m_nonzero_mask
= NULL
;
1163 // Check the validity of the range.
1166 irange::verify_range ()
1168 gcc_checking_assert (m_discriminator
== VR_IRANGE
);
1169 if (m_kind
== VR_UNDEFINED
)
1171 gcc_checking_assert (m_num_ranges
== 0);
1174 if (m_kind
== VR_VARYING
)
1176 gcc_checking_assert (!m_nonzero_mask
1177 || wi::to_wide (m_nonzero_mask
) == -1);
1178 gcc_checking_assert (m_num_ranges
== 1);
1179 gcc_checking_assert (varying_compatible_p ());
1182 if (!legacy_mode_p ())
1184 gcc_checking_assert (m_num_ranges
!= 0);
1185 gcc_checking_assert (!varying_compatible_p ());
1186 for (unsigned i
= 0; i
< m_num_ranges
; ++i
)
1188 tree lb
= tree_lower_bound (i
);
1189 tree ub
= tree_upper_bound (i
);
1190 int c
= compare_values (lb
, ub
);
1191 gcc_checking_assert (c
== 0 || c
== -1);
1195 if (m_kind
== VR_RANGE
|| m_kind
== VR_ANTI_RANGE
)
1197 gcc_checking_assert (m_num_ranges
== 1);
1198 int cmp
= compare_values (tree_lower_bound (0), tree_upper_bound (0));
1199 gcc_checking_assert (cmp
== 0 || cmp
== -1 || cmp
== -2);
1203 // Return the lower bound for a sub-range. PAIR is the sub-range in
1207 irange::legacy_lower_bound (unsigned pair
) const
1209 gcc_checking_assert (legacy_mode_p ());
1212 value_range
numeric_range (*this);
1213 numeric_range
.normalize_symbolics ();
1214 return numeric_range
.legacy_lower_bound (pair
);
1216 gcc_checking_assert (m_num_ranges
> 0);
1217 gcc_checking_assert (pair
+ 1 <= num_pairs ());
1218 if (m_kind
== VR_ANTI_RANGE
)
1220 tree typ
= type (), t
;
1221 if (pair
== 1 || vrp_val_is_min (min ()))
1222 t
= wide_int_to_tree (typ
, wi::to_wide (max ()) + 1);
1224 t
= vrp_val_min (typ
);
1225 return wi::to_wide (t
);
1227 return wi::to_wide (tree_lower_bound (pair
));
1230 // Return the upper bound for a sub-range. PAIR is the sub-range in
1234 irange::legacy_upper_bound (unsigned pair
) const
1236 gcc_checking_assert (legacy_mode_p ());
1239 value_range
numeric_range (*this);
1240 numeric_range
.normalize_symbolics ();
1241 return numeric_range
.legacy_upper_bound (pair
);
1243 gcc_checking_assert (m_num_ranges
> 0);
1244 gcc_checking_assert (pair
+ 1 <= num_pairs ());
1245 if (m_kind
== VR_ANTI_RANGE
)
1247 tree typ
= type (), t
;
1248 if (pair
== 1 || vrp_val_is_min (min ()))
1249 t
= vrp_val_max (typ
);
1251 t
= wide_int_to_tree (typ
, wi::to_wide (min ()) - 1);
1252 return wi::to_wide (t
);
1254 return wi::to_wide (tree_upper_bound (pair
));
1258 irange::legacy_equal_p (const irange
&other
) const
1260 gcc_checking_assert (legacy_mode_p () && other
.legacy_mode_p ());
1262 if (m_kind
!= other
.m_kind
)
1264 if (m_kind
== VR_UNDEFINED
)
1266 if (m_kind
== VR_VARYING
)
1267 return range_compatible_p (type (), other
.type ());
1268 return (vrp_operand_equal_p (tree_lower_bound (0),
1269 other
.tree_lower_bound (0))
1270 && vrp_operand_equal_p (tree_upper_bound (0),
1271 other
.tree_upper_bound (0))
1272 && (widest_int::from (get_nonzero_bits (),
1273 TYPE_SIGN (type ()))
1274 == widest_int::from (other
.get_nonzero_bits (),
1275 TYPE_SIGN (other
.type ()))));
1279 irange::operator== (const irange
&other
) const
1281 if (legacy_mode_p ())
1283 if (other
.legacy_mode_p ())
1284 return legacy_equal_p (other
);
1285 value_range
tmp (other
);
1286 return legacy_equal_p (tmp
);
1288 if (other
.legacy_mode_p ())
1290 value_range
tmp2 (*this);
1291 return tmp2
.legacy_equal_p (other
);
1294 if (m_num_ranges
!= other
.m_num_ranges
)
1297 if (m_num_ranges
== 0)
1300 for (unsigned i
= 0; i
< m_num_ranges
; ++i
)
1302 tree lb
= tree_lower_bound (i
);
1303 tree ub
= tree_upper_bound (i
);
1304 tree lb_other
= other
.tree_lower_bound (i
);
1305 tree ub_other
= other
.tree_upper_bound (i
);
1306 if (!operand_equal_p (lb
, lb_other
, 0)
1307 || !operand_equal_p (ub
, ub_other
, 0))
1310 widest_int nz1
= widest_int::from (get_nonzero_bits (),
1311 TYPE_SIGN (type ()));
1312 widest_int nz2
= widest_int::from (other
.get_nonzero_bits (),
1313 TYPE_SIGN (other
.type ()));
1317 /* Return TRUE if this is a symbolic range. */
1320 irange::symbolic_p () const
1322 return (m_num_ranges
> 0
1323 && (!is_gimple_min_invariant (min ())
1324 || !is_gimple_min_invariant (max ())));
1327 /* Return TRUE if this is a constant range. */
1330 irange::constant_p () const
1332 return (m_num_ranges
> 0
1333 && TREE_CODE (min ()) == INTEGER_CST
1334 && TREE_CODE (max ()) == INTEGER_CST
);
1337 /* If range is a singleton, place it in RESULT and return TRUE.
1338 Note: A singleton can be any gimple invariant, not just constants.
1339 So, [&x, &x] counts as a singleton. */
1342 irange::singleton_p (tree
*result
) const
1344 if (!legacy_mode_p ())
1346 if (num_pairs () == 1 && (wi::to_wide (tree_lower_bound ())
1347 == wi::to_wide (tree_upper_bound ())))
1350 *result
= tree_lower_bound ();
1355 if (m_kind
== VR_ANTI_RANGE
)
1359 if (TYPE_PRECISION (type ()) == 1)
1367 if (num_pairs () == 1)
1369 value_range vr0
, vr1
;
1370 ranges_from_anti_range ((const value_range
*) this, &vr0
, &vr1
);
1371 return vr0
.singleton_p (result
);
1374 // Catches non-numeric extremes as well.
1375 if (m_kind
== VR_RANGE
1376 && vrp_operand_equal_p (min (), max ())
1377 && is_gimple_min_invariant (min ()))
1386 /* Return 1 if VAL is inside value range.
1387 0 if VAL is not inside value range.
1388 -2 if we cannot tell either way.
1390 Benchmark compile/20001226-1.c compilation time after changing this
1394 irange::value_inside_range (tree val
) const
1402 if (!legacy_mode_p () && TREE_CODE (val
) == INTEGER_CST
)
1403 return contains_p (val
);
1405 int cmp1
= operand_less_p (val
, min ());
1409 return m_kind
!= VR_RANGE
;
1411 int cmp2
= operand_less_p (max (), val
);
1415 if (m_kind
== VR_RANGE
)
1421 /* Return TRUE if it is possible that range contains VAL. */
1424 irange::may_contain_p (tree val
) const
1426 return value_inside_range (val
) != 0;
1429 /* Return TRUE if range contains INTEGER_CST. */
1430 /* Return 1 if VAL is inside value range.
1431 0 if VAL is not inside value range.
1433 Benchmark compile/20001226-1.c compilation time after changing this
1438 irange::contains_p (tree cst
) const
1443 if (legacy_mode_p ())
1445 gcc_checking_assert (TREE_CODE (cst
) == INTEGER_CST
);
1448 value_range
numeric_range (*this);
1449 numeric_range
.normalize_symbolics ();
1450 return numeric_range
.contains_p (cst
);
1452 return value_inside_range (cst
) == 1;
1455 gcc_checking_assert (TREE_CODE (cst
) == INTEGER_CST
);
1457 // See if we can exclude CST based on the nonzero bits.
1460 wide_int cstw
= wi::to_wide (cst
);
1461 if (cstw
!= 0 && wi::bit_and (wi::to_wide (m_nonzero_mask
), cstw
) == 0)
1465 signop sign
= TYPE_SIGN (TREE_TYPE (cst
));
1466 wide_int v
= wi::to_wide (cst
);
1467 for (unsigned r
= 0; r
< m_num_ranges
; ++r
)
1469 if (wi::lt_p (v
, lower_bound (r
), sign
))
1471 if (wi::le_p (v
, upper_bound (r
), sign
))
1479 /* Normalize addresses into constants. */
1482 irange::normalize_addresses ()
1487 if (!POINTER_TYPE_P (type ()) || range_has_numeric_bounds_p (this))
1490 if (!range_includes_zero_p (this))
1492 gcc_checking_assert (TREE_CODE (min ()) == ADDR_EXPR
1493 || TREE_CODE (max ()) == ADDR_EXPR
);
1494 set_nonzero (type ());
1497 set_varying (type ());
1500 /* Normalize symbolics and addresses into constants. */
1503 irange::normalize_symbolics ()
1505 if (varying_p () || undefined_p ())
1508 tree ttype
= type ();
1509 bool min_symbolic
= !is_gimple_min_invariant (min ());
1510 bool max_symbolic
= !is_gimple_min_invariant (max ());
1511 if (!min_symbolic
&& !max_symbolic
)
1513 normalize_addresses ();
1517 // [SYM, SYM] -> VARYING
1518 if (min_symbolic
&& max_symbolic
)
1520 set_varying (ttype
);
1523 if (kind () == VR_RANGE
)
1525 // [SYM, NUM] -> [-MIN, NUM]
1528 set (vrp_val_min (ttype
), max ());
1531 // [NUM, SYM] -> [NUM, +MAX]
1532 set (min (), vrp_val_max (ttype
));
1535 gcc_checking_assert (kind () == VR_ANTI_RANGE
);
1536 // ~[SYM, NUM] -> [NUM + 1, +MAX]
1539 if (!vrp_val_is_max (max ()))
1541 tree n
= wide_int_to_tree (ttype
, wi::to_wide (max ()) + 1);
1542 set (n
, vrp_val_max (ttype
));
1545 set_varying (ttype
);
1548 // ~[NUM, SYM] -> [-MIN, NUM - 1]
1549 if (!vrp_val_is_min (min ()))
1551 tree n
= wide_int_to_tree (ttype
, wi::to_wide (min ()) - 1);
1552 set (vrp_val_min (ttype
), n
);
1555 set_varying (ttype
);
1558 /* Intersect the two value-ranges { *VR0TYPE, *VR0MIN, *VR0MAX } and
1559 { VR1TYPE, VR0MIN, VR0MAX } and store the result
1560 in { *VR0TYPE, *VR0MIN, *VR0MAX }. This may not be the smallest
1561 possible such range. The resulting range is not canonicalized. */
1564 intersect_ranges (enum value_range_kind
*vr0type
,
1565 tree
*vr0min
, tree
*vr0max
,
1566 enum value_range_kind vr1type
,
1567 tree vr1min
, tree vr1max
)
1569 bool mineq
= vrp_operand_equal_p (*vr0min
, vr1min
);
1570 bool maxeq
= vrp_operand_equal_p (*vr0max
, vr1max
);
1572 /* [] is vr0, () is vr1 in the following classification comments. */
1576 if (*vr0type
== vr1type
)
1577 /* Nothing to do for equal ranges. */
1579 else if ((*vr0type
== VR_RANGE
1580 && vr1type
== VR_ANTI_RANGE
)
1581 || (*vr0type
== VR_ANTI_RANGE
1582 && vr1type
== VR_RANGE
))
1584 /* For anti-range with range intersection the result is empty. */
1585 *vr0type
= VR_UNDEFINED
;
1586 *vr0min
= NULL_TREE
;
1587 *vr0max
= NULL_TREE
;
1592 else if (operand_less_p (*vr0max
, vr1min
) == 1
1593 || operand_less_p (vr1max
, *vr0min
) == 1)
1595 /* [ ] ( ) or ( ) [ ]
1596 If the ranges have an empty intersection, the result of the
1597 intersect operation is the range for intersecting an
1598 anti-range with a range or empty when intersecting two ranges. */
1599 if (*vr0type
== VR_RANGE
1600 && vr1type
== VR_ANTI_RANGE
)
1602 else if (*vr0type
== VR_ANTI_RANGE
1603 && vr1type
== VR_RANGE
)
1609 else if (*vr0type
== VR_RANGE
1610 && vr1type
== VR_RANGE
)
1612 *vr0type
= VR_UNDEFINED
;
1613 *vr0min
= NULL_TREE
;
1614 *vr0max
= NULL_TREE
;
1616 else if (*vr0type
== VR_ANTI_RANGE
1617 && vr1type
== VR_ANTI_RANGE
)
1619 /* If the anti-ranges are adjacent to each other merge them. */
1620 if (TREE_CODE (*vr0max
) == INTEGER_CST
1621 && TREE_CODE (vr1min
) == INTEGER_CST
1622 && operand_less_p (*vr0max
, vr1min
) == 1
1623 && integer_onep (int_const_binop (MINUS_EXPR
,
1626 else if (TREE_CODE (vr1max
) == INTEGER_CST
1627 && TREE_CODE (*vr0min
) == INTEGER_CST
1628 && operand_less_p (vr1max
, *vr0min
) == 1
1629 && integer_onep (int_const_binop (MINUS_EXPR
,
1632 /* Else arbitrarily take VR0. */
1635 else if ((maxeq
|| operand_less_p (vr1max
, *vr0max
) == 1)
1636 && (mineq
|| operand_less_p (*vr0min
, vr1min
) == 1))
1638 /* [ ( ) ] or [( ) ] or [ ( )] */
1639 if (*vr0type
== VR_RANGE
1640 && vr1type
== VR_RANGE
)
1642 /* If both are ranges the result is the inner one. */
1647 else if (*vr0type
== VR_RANGE
1648 && vr1type
== VR_ANTI_RANGE
)
1650 /* Choose the right gap if the left one is empty. */
1653 if (TREE_CODE (vr1max
) != INTEGER_CST
)
1655 else if (TYPE_PRECISION (TREE_TYPE (vr1max
)) == 1
1656 && !TYPE_UNSIGNED (TREE_TYPE (vr1max
)))
1658 = int_const_binop (MINUS_EXPR
, vr1max
,
1659 build_int_cst (TREE_TYPE (vr1max
), -1));
1662 = int_const_binop (PLUS_EXPR
, vr1max
,
1663 build_int_cst (TREE_TYPE (vr1max
), 1));
1665 /* Choose the left gap if the right one is empty. */
1668 if (TREE_CODE (vr1min
) != INTEGER_CST
)
1670 else if (TYPE_PRECISION (TREE_TYPE (vr1min
)) == 1
1671 && !TYPE_UNSIGNED (TREE_TYPE (vr1min
)))
1673 = int_const_binop (PLUS_EXPR
, vr1min
,
1674 build_int_cst (TREE_TYPE (vr1min
), -1));
1677 = int_const_binop (MINUS_EXPR
, vr1min
,
1678 build_int_cst (TREE_TYPE (vr1min
), 1));
1680 /* Choose the anti-range if the range is effectively varying. */
1681 else if (vrp_val_is_min (*vr0min
)
1682 && vrp_val_is_max (*vr0max
))
1688 /* Else choose the range. */
1690 else if (*vr0type
== VR_ANTI_RANGE
1691 && vr1type
== VR_ANTI_RANGE
)
1692 /* If both are anti-ranges the result is the outer one. */
1694 else if (*vr0type
== VR_ANTI_RANGE
1695 && vr1type
== VR_RANGE
)
1697 /* The intersection is empty. */
1698 *vr0type
= VR_UNDEFINED
;
1699 *vr0min
= NULL_TREE
;
1700 *vr0max
= NULL_TREE
;
1705 else if ((maxeq
|| operand_less_p (*vr0max
, vr1max
) == 1)
1706 && (mineq
|| operand_less_p (vr1min
, *vr0min
) == 1))
1708 /* ( [ ] ) or ([ ] ) or ( [ ]) */
1709 if (*vr0type
== VR_RANGE
1710 && vr1type
== VR_RANGE
)
1711 /* Choose the inner range. */
1713 else if (*vr0type
== VR_ANTI_RANGE
1714 && vr1type
== VR_RANGE
)
1716 /* Choose the right gap if the left is empty. */
1719 *vr0type
= VR_RANGE
;
1720 if (TREE_CODE (*vr0max
) != INTEGER_CST
)
1722 else if (TYPE_PRECISION (TREE_TYPE (*vr0max
)) == 1
1723 && !TYPE_UNSIGNED (TREE_TYPE (*vr0max
)))
1725 = int_const_binop (MINUS_EXPR
, *vr0max
,
1726 build_int_cst (TREE_TYPE (*vr0max
), -1));
1729 = int_const_binop (PLUS_EXPR
, *vr0max
,
1730 build_int_cst (TREE_TYPE (*vr0max
), 1));
1733 /* Choose the left gap if the right is empty. */
1736 *vr0type
= VR_RANGE
;
1737 if (TREE_CODE (*vr0min
) != INTEGER_CST
)
1739 else if (TYPE_PRECISION (TREE_TYPE (*vr0min
)) == 1
1740 && !TYPE_UNSIGNED (TREE_TYPE (*vr0min
)))
1742 = int_const_binop (PLUS_EXPR
, *vr0min
,
1743 build_int_cst (TREE_TYPE (*vr0min
), -1));
1746 = int_const_binop (MINUS_EXPR
, *vr0min
,
1747 build_int_cst (TREE_TYPE (*vr0min
), 1));
1750 /* Choose the anti-range if the range is effectively varying. */
1751 else if (vrp_val_is_min (vr1min
)
1752 && vrp_val_is_max (vr1max
))
1754 /* Choose the anti-range if it is ~[0,0], that range is special
1755 enough to special case when vr1's range is relatively wide.
1756 At least for types bigger than int - this covers pointers
1757 and arguments to functions like ctz. */
1758 else if (*vr0min
== *vr0max
1759 && integer_zerop (*vr0min
)
1760 && ((TYPE_PRECISION (TREE_TYPE (*vr0min
))
1761 >= TYPE_PRECISION (integer_type_node
))
1762 || POINTER_TYPE_P (TREE_TYPE (*vr0min
)))
1763 && TREE_CODE (vr1max
) == INTEGER_CST
1764 && TREE_CODE (vr1min
) == INTEGER_CST
1765 && (wi::clz (wi::to_wide (vr1max
) - wi::to_wide (vr1min
))
1766 < TYPE_PRECISION (TREE_TYPE (*vr0min
)) / 2))
1768 /* Else choose the range. */
1776 else if (*vr0type
== VR_ANTI_RANGE
1777 && vr1type
== VR_ANTI_RANGE
)
1779 /* If both are anti-ranges the result is the outer one. */
1784 else if (vr1type
== VR_ANTI_RANGE
1785 && *vr0type
== VR_RANGE
)
1787 /* The intersection is empty. */
1788 *vr0type
= VR_UNDEFINED
;
1789 *vr0min
= NULL_TREE
;
1790 *vr0max
= NULL_TREE
;
1795 else if ((operand_less_p (vr1min
, *vr0max
) == 1
1796 || operand_equal_p (vr1min
, *vr0max
, 0))
1797 && operand_less_p (*vr0min
, vr1min
) == 1
1798 && operand_less_p (*vr0max
, vr1max
) == 1)
1800 /* [ ( ] ) or [ ]( ) */
1801 if (*vr0type
== VR_ANTI_RANGE
1802 && vr1type
== VR_ANTI_RANGE
)
1804 else if (*vr0type
== VR_RANGE
1805 && vr1type
== VR_RANGE
)
1807 else if (*vr0type
== VR_RANGE
1808 && vr1type
== VR_ANTI_RANGE
)
1810 if (TREE_CODE (vr1min
) == INTEGER_CST
)
1811 *vr0max
= int_const_binop (MINUS_EXPR
, vr1min
,
1812 build_int_cst (TREE_TYPE (vr1min
), 1));
1816 else if (*vr0type
== VR_ANTI_RANGE
1817 && vr1type
== VR_RANGE
)
1819 *vr0type
= VR_RANGE
;
1820 if (TREE_CODE (*vr0max
) == INTEGER_CST
)
1821 *vr0min
= int_const_binop (PLUS_EXPR
, *vr0max
,
1822 build_int_cst (TREE_TYPE (*vr0max
), 1));
1830 else if ((operand_less_p (*vr0min
, vr1max
) == 1
1831 || operand_equal_p (*vr0min
, vr1max
, 0))
1832 && operand_less_p (vr1min
, *vr0min
) == 1
1833 && operand_less_p (vr1max
, *vr0max
) == 1)
1835 /* ( [ ) ] or ( )[ ] */
1836 if (*vr0type
== VR_ANTI_RANGE
1837 && vr1type
== VR_ANTI_RANGE
)
1839 else if (*vr0type
== VR_RANGE
1840 && vr1type
== VR_RANGE
)
1842 else if (*vr0type
== VR_RANGE
1843 && vr1type
== VR_ANTI_RANGE
)
1845 if (TREE_CODE (vr1max
) == INTEGER_CST
)
1846 *vr0min
= int_const_binop (PLUS_EXPR
, vr1max
,
1847 build_int_cst (TREE_TYPE (vr1max
), 1));
1851 else if (*vr0type
== VR_ANTI_RANGE
1852 && vr1type
== VR_RANGE
)
1854 *vr0type
= VR_RANGE
;
1855 if (TREE_CODE (*vr0min
) == INTEGER_CST
)
1856 *vr0max
= int_const_binop (MINUS_EXPR
, *vr0min
,
1857 build_int_cst (TREE_TYPE (*vr0min
), 1));
1866 /* If we know the intersection is empty, there's no need to
1867 conservatively add anything else to the set. */
1868 if (*vr0type
== VR_UNDEFINED
)
1871 /* As a fallback simply use { *VRTYPE, *VR0MIN, *VR0MAX } as
1872 result for the intersection. That's always a conservative
1873 correct estimate unless VR1 is a constant singleton range
1874 in which case we choose that. */
1875 if (vr1type
== VR_RANGE
1876 && is_gimple_min_invariant (vr1min
)
1877 && vrp_operand_equal_p (vr1min
, vr1max
))
1885 /* Helper for the intersection operation for value ranges. Given two
1886 ranges VR0 and VR1, set VR0 to the intersection of both ranges.
1887 This may not be the smallest possible such range. */
1890 irange::legacy_intersect (irange
*vr0
, const irange
*vr1
)
1892 gcc_checking_assert (vr0
->legacy_mode_p ());
1893 gcc_checking_assert (vr1
->legacy_mode_p ());
1894 /* If either range is VR_VARYING the other one wins. */
1895 if (vr1
->varying_p ())
1897 if (vr0
->varying_p ())
1899 vr0
->set (vr1
->min (), vr1
->max (), vr1
->kind ());
1903 /* When either range is VR_UNDEFINED the resulting range is
1904 VR_UNDEFINED, too. */
1905 if (vr0
->undefined_p ())
1907 if (vr1
->undefined_p ())
1909 vr0
->set_undefined ();
1913 value_range_kind vr0kind
= vr0
->kind ();
1914 tree vr0min
= vr0
->min ();
1915 tree vr0max
= vr0
->max ();
1917 intersect_ranges (&vr0kind
, &vr0min
, &vr0max
,
1918 vr1
->kind (), vr1
->min (), vr1
->max ());
1920 /* Make sure to canonicalize the result though as the inversion of a
1921 VR_RANGE can still be a VR_RANGE. */
1922 if (vr0kind
== VR_UNDEFINED
)
1923 vr0
->set_undefined ();
1924 else if (vr0kind
== VR_VARYING
)
1926 /* If we failed, use the original VR0. */
1930 vr0
->set (vr0min
, vr0max
, vr0kind
);
1933 /* Union the two value-ranges { *VR0TYPE, *VR0MIN, *VR0MAX } and
1934 { VR1TYPE, VR0MIN, VR0MAX } and store the result
1935 in { *VR0TYPE, *VR0MIN, *VR0MAX }. This may not be the smallest
1936 possible such range. The resulting range is not canonicalized. */
1939 union_ranges (enum value_range_kind
*vr0type
,
1940 tree
*vr0min
, tree
*vr0max
,
1941 enum value_range_kind vr1type
,
1942 tree vr1min
, tree vr1max
)
1944 int cmpmin
= compare_values (*vr0min
, vr1min
);
1945 int cmpmax
= compare_values (*vr0max
, vr1max
);
1946 bool mineq
= cmpmin
== 0;
1947 bool maxeq
= cmpmax
== 0;
1949 /* [] is vr0, () is vr1 in the following classification comments. */
1953 if (*vr0type
== vr1type
)
1954 /* Nothing to do for equal ranges. */
1956 else if ((*vr0type
== VR_RANGE
1957 && vr1type
== VR_ANTI_RANGE
)
1958 || (*vr0type
== VR_ANTI_RANGE
1959 && vr1type
== VR_RANGE
))
1961 /* For anti-range with range union the result is varying. */
1967 else if (operand_less_p (*vr0max
, vr1min
) == 1
1968 || operand_less_p (vr1max
, *vr0min
) == 1)
1970 /* [ ] ( ) or ( ) [ ]
1971 If the ranges have an empty intersection, result of the union
1972 operation is the anti-range or if both are anti-ranges
1974 if (*vr0type
== VR_ANTI_RANGE
1975 && vr1type
== VR_ANTI_RANGE
)
1977 else if (*vr0type
== VR_ANTI_RANGE
1978 && vr1type
== VR_RANGE
)
1980 else if (*vr0type
== VR_RANGE
1981 && vr1type
== VR_ANTI_RANGE
)
1987 else if (*vr0type
== VR_RANGE
1988 && vr1type
== VR_RANGE
)
1990 /* The result is the convex hull of both ranges. */
1991 if (operand_less_p (*vr0max
, vr1min
) == 1)
1993 /* If the result can be an anti-range, create one. */
1994 if (TREE_CODE (*vr0max
) == INTEGER_CST
1995 && TREE_CODE (vr1min
) == INTEGER_CST
1996 && vrp_val_is_min (*vr0min
)
1997 && vrp_val_is_max (vr1max
))
1999 tree min
= int_const_binop (PLUS_EXPR
,
2001 build_int_cst (TREE_TYPE (*vr0max
), 1));
2002 tree max
= int_const_binop (MINUS_EXPR
,
2004 build_int_cst (TREE_TYPE (vr1min
), 1));
2005 if (!operand_less_p (max
, min
))
2007 *vr0type
= VR_ANTI_RANGE
;
2019 /* If the result can be an anti-range, create one. */
2020 if (TREE_CODE (vr1max
) == INTEGER_CST
2021 && TREE_CODE (*vr0min
) == INTEGER_CST
2022 && vrp_val_is_min (vr1min
)
2023 && vrp_val_is_max (*vr0max
))
2025 tree min
= int_const_binop (PLUS_EXPR
,
2027 build_int_cst (TREE_TYPE (vr1max
), 1));
2028 tree max
= int_const_binop (MINUS_EXPR
,
2030 build_int_cst (TREE_TYPE (*vr0min
), 1));
2031 if (!operand_less_p (max
, min
))
2033 *vr0type
= VR_ANTI_RANGE
;
2047 else if ((maxeq
|| cmpmax
== 1)
2048 && (mineq
|| cmpmin
== -1))
2050 /* [ ( ) ] or [( ) ] or [ ( )] */
2051 if (*vr0type
== VR_RANGE
2052 && vr1type
== VR_RANGE
)
2054 else if (*vr0type
== VR_ANTI_RANGE
2055 && vr1type
== VR_ANTI_RANGE
)
2061 else if (*vr0type
== VR_ANTI_RANGE
2062 && vr1type
== VR_RANGE
)
2064 /* Arbitrarily choose the right or left gap. */
2065 if (!mineq
&& TREE_CODE (vr1min
) == INTEGER_CST
)
2066 *vr0max
= int_const_binop (MINUS_EXPR
, vr1min
,
2067 build_int_cst (TREE_TYPE (vr1min
), 1));
2068 else if (!maxeq
&& TREE_CODE (vr1max
) == INTEGER_CST
)
2069 *vr0min
= int_const_binop (PLUS_EXPR
, vr1max
,
2070 build_int_cst (TREE_TYPE (vr1max
), 1));
2074 else if (*vr0type
== VR_RANGE
2075 && vr1type
== VR_ANTI_RANGE
)
2076 /* The result covers everything. */
2081 else if ((maxeq
|| cmpmax
== -1)
2082 && (mineq
|| cmpmin
== 1))
2084 /* ( [ ] ) or ([ ] ) or ( [ ]) */
2085 if (*vr0type
== VR_RANGE
2086 && vr1type
== VR_RANGE
)
2092 else if (*vr0type
== VR_ANTI_RANGE
2093 && vr1type
== VR_ANTI_RANGE
)
2095 else if (*vr0type
== VR_RANGE
2096 && vr1type
== VR_ANTI_RANGE
)
2098 *vr0type
= VR_ANTI_RANGE
;
2099 if (!mineq
&& TREE_CODE (*vr0min
) == INTEGER_CST
)
2101 *vr0max
= int_const_binop (MINUS_EXPR
, *vr0min
,
2102 build_int_cst (TREE_TYPE (*vr0min
), 1));
2105 else if (!maxeq
&& TREE_CODE (*vr0max
) == INTEGER_CST
)
2107 *vr0min
= int_const_binop (PLUS_EXPR
, *vr0max
,
2108 build_int_cst (TREE_TYPE (*vr0max
), 1));
2114 else if (*vr0type
== VR_ANTI_RANGE
2115 && vr1type
== VR_RANGE
)
2116 /* The result covers everything. */
2121 else if (cmpmin
== -1
2123 && (operand_less_p (vr1min
, *vr0max
) == 1
2124 || operand_equal_p (vr1min
, *vr0max
, 0)))
2126 /* [ ( ] ) or [ ]( ) */
2127 if (*vr0type
== VR_RANGE
2128 && vr1type
== VR_RANGE
)
2130 else if (*vr0type
== VR_ANTI_RANGE
2131 && vr1type
== VR_ANTI_RANGE
)
2133 else if (*vr0type
== VR_ANTI_RANGE
2134 && vr1type
== VR_RANGE
)
2136 if (TREE_CODE (vr1min
) == INTEGER_CST
)
2137 *vr0max
= int_const_binop (MINUS_EXPR
, vr1min
,
2138 build_int_cst (TREE_TYPE (vr1min
), 1));
2142 else if (*vr0type
== VR_RANGE
2143 && vr1type
== VR_ANTI_RANGE
)
2145 if (TREE_CODE (*vr0max
) == INTEGER_CST
)
2148 *vr0min
= int_const_binop (PLUS_EXPR
, *vr0max
,
2149 build_int_cst (TREE_TYPE (*vr0max
), 1));
2158 else if (cmpmin
== 1
2160 && (operand_less_p (*vr0min
, vr1max
) == 1
2161 || operand_equal_p (*vr0min
, vr1max
, 0)))
2163 /* ( [ ) ] or ( )[ ] */
2164 if (*vr0type
== VR_RANGE
2165 && vr1type
== VR_RANGE
)
2167 else if (*vr0type
== VR_ANTI_RANGE
2168 && vr1type
== VR_ANTI_RANGE
)
2170 else if (*vr0type
== VR_ANTI_RANGE
2171 && vr1type
== VR_RANGE
)
2173 if (TREE_CODE (vr1max
) == INTEGER_CST
)
2174 *vr0min
= int_const_binop (PLUS_EXPR
, vr1max
,
2175 build_int_cst (TREE_TYPE (vr1max
), 1));
2179 else if (*vr0type
== VR_RANGE
2180 && vr1type
== VR_ANTI_RANGE
)
2182 if (TREE_CODE (*vr0min
) == INTEGER_CST
)
2185 *vr0max
= int_const_binop (MINUS_EXPR
, *vr0min
,
2186 build_int_cst (TREE_TYPE (*vr0min
), 1));
2201 *vr0type
= VR_VARYING
;
2202 *vr0min
= NULL_TREE
;
2203 *vr0max
= NULL_TREE
;
2206 /* Helper for meet operation for value ranges. Given two ranges VR0
2207 and VR1, set VR0 to the union of both ranges. This may not be the
2208 smallest possible such range. */
2211 irange::legacy_union (irange
*vr0
, const irange
*vr1
)
2213 gcc_checking_assert (vr0
->legacy_mode_p ());
2214 gcc_checking_assert (vr1
->legacy_mode_p ());
2216 /* VR0 has the resulting range if VR1 is undefined or VR0 is varying. */
2217 if (vr1
->undefined_p ()
2218 || vr0
->varying_p ())
2221 /* VR1 has the resulting range if VR0 is undefined or VR1 is varying. */
2222 if (vr0
->undefined_p ())
2224 vr0
->set (vr1
->min (), vr1
->max (), vr1
->kind ());
2228 if (vr1
->varying_p ())
2230 vr0
->set_varying (vr1
->type ());
2234 value_range_kind vr0kind
= vr0
->kind ();
2235 tree vr0min
= vr0
->min ();
2236 tree vr0max
= vr0
->max ();
2238 union_ranges (&vr0kind
, &vr0min
, &vr0max
,
2239 vr1
->kind (), vr1
->min (), vr1
->max ());
2241 if (vr0kind
== VR_UNDEFINED
)
2242 vr0
->set_undefined ();
2243 else if (vr0kind
== VR_VARYING
)
2245 /* Failed to find an efficient meet. Before giving up and
2246 setting the result to VARYING, see if we can at least derive
2247 a non-zero range. */
2248 if (range_includes_zero_p (vr0
) == 0
2249 && range_includes_zero_p (vr1
) == 0)
2250 vr0
->set_nonzero (vr0
->type ());
2252 vr0
->set_varying (vr0
->type ());
2255 vr0
->set (vr0min
, vr0max
, vr0kind
);
2258 /* Meet operation for value ranges. Given two value ranges VR0 and
2259 VR1, store in VR0 a range that contains both VR0 and VR1. This
2260 may not be the smallest possible such range.
2261 Return TRUE if the original value changes. */
2264 irange::legacy_verbose_union_ (const irange
*other
)
2266 if (legacy_mode_p ())
2268 if (!other
->legacy_mode_p ())
2270 int_range
<1> tmp
= *other
;
2271 legacy_union (this, &tmp
);
2274 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2276 fprintf (dump_file
, "Meeting\n ");
2277 dump_value_range (dump_file
, this);
2278 fprintf (dump_file
, "\nand\n ");
2279 dump_value_range (dump_file
, other
);
2280 fprintf (dump_file
, "\n");
2283 legacy_union (this, other
);
2285 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2287 fprintf (dump_file
, "to\n ");
2288 dump_value_range (dump_file
, this);
2289 fprintf (dump_file
, "\n");
2294 if (other
->legacy_mode_p ())
2296 int_range
<2> wider
= *other
;
2297 return irange_union (wider
);
2300 return irange_union (*other
);
2304 irange::legacy_verbose_intersect (const irange
*other
)
2306 if (legacy_mode_p ())
2308 if (!other
->legacy_mode_p ())
2310 int_range
<1> tmp
= *other
;
2311 legacy_intersect (this, &tmp
);
2314 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2316 fprintf (dump_file
, "Intersecting\n ");
2317 dump_value_range (dump_file
, this);
2318 fprintf (dump_file
, "\nand\n ");
2319 dump_value_range (dump_file
, other
);
2320 fprintf (dump_file
, "\n");
2323 legacy_intersect (this, other
);
2325 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2327 fprintf (dump_file
, "to\n ");
2328 dump_value_range (dump_file
, this);
2329 fprintf (dump_file
, "\n");
2334 if (other
->legacy_mode_p ())
2338 return irange_intersect (wider
);
2341 return irange_intersect (*other
);
2344 // Perform an efficient union with R when both ranges have only a single pair.
2345 // Excluded are VARYING and UNDEFINED ranges.
2348 irange::irange_single_pair_union (const irange
&r
)
2350 gcc_checking_assert (!undefined_p () && !varying_p ());
2351 gcc_checking_assert (!r
.undefined_p () && !varying_p ());
2353 signop sign
= TYPE_SIGN (TREE_TYPE (m_base
[0]));
2354 // Check if current lower bound is also the new lower bound.
2355 if (wi::le_p (wi::to_wide (m_base
[0]), wi::to_wide (r
.m_base
[0]), sign
))
2357 // If current upper bound is new upper bound, we're done.
2358 if (wi::le_p (wi::to_wide (r
.m_base
[1]), wi::to_wide (m_base
[1]), sign
))
2359 return union_nonzero_bits (r
);
2360 // Otherwise R has the new upper bound.
2361 // Check for overlap/touching ranges, or single target range.
2362 if (m_max_ranges
== 1
2363 || wi::to_widest (m_base
[1]) + 1 >= wi::to_widest (r
.m_base
[0]))
2364 m_base
[1] = r
.m_base
[1];
2367 // This is a dual range result.
2368 m_base
[2] = r
.m_base
[0];
2369 m_base
[3] = r
.m_base
[1];
2372 union_nonzero_bits (r
);
2376 // Set the new lower bound to R's lower bound.
2377 tree lb
= m_base
[0];
2378 m_base
[0] = r
.m_base
[0];
2380 // If R fully contains THIS range, just set the upper bound.
2381 if (wi::ge_p (wi::to_wide (r
.m_base
[1]), wi::to_wide (m_base
[1]), sign
))
2382 m_base
[1] = r
.m_base
[1];
2383 // Check for overlapping ranges, or target limited to a single range.
2384 else if (m_max_ranges
== 1
2385 || wi::to_widest (r
.m_base
[1]) + 1 >= wi::to_widest (lb
))
2389 // Left with 2 pairs.
2392 m_base
[3] = m_base
[1];
2393 m_base
[1] = r
.m_base
[1];
2395 union_nonzero_bits (r
);
2399 // union_ for multi-ranges.
2402 irange::irange_union (const irange
&r
)
2404 gcc_checking_assert (!legacy_mode_p () && !r
.legacy_mode_p ());
2406 if (r
.undefined_p ())
2422 set_varying (type ());
2426 // Special case one range union one range.
2427 if (m_num_ranges
== 1 && r
.m_num_ranges
== 1)
2428 return irange_single_pair_union (r
);
2430 // If this ranges fully contains R, then we need do nothing.
2431 if (irange_contains_p (r
))
2432 return union_nonzero_bits (r
);
2434 // Do not worry about merging and such by reserving twice as many
2435 // pairs as needed, and then simply sort the 2 ranges into this
2436 // intermediate form.
2438 // The intermediate result will have the property that the beginning
2439 // of each range is <= the beginning of the next range. There may
2440 // be overlapping ranges at this point. I.e. this would be valid
2441 // [-20, 10], [-10, 0], [0, 20], [40, 90] as it satisfies this
2442 // constraint : -20 < -10 < 0 < 40. When the range is rebuilt into r,
2443 // the merge is performed.
2445 // [Xi,Yi]..[Xn,Yn] U [Xj,Yj]..[Xm,Ym] --> [Xk,Yk]..[Xp,Yp]
2446 auto_vec
<tree
, 20> res (m_num_ranges
* 2 + r
.m_num_ranges
* 2);
2447 unsigned i
= 0, j
= 0, k
= 0;
2449 while (i
< m_num_ranges
* 2 && j
< r
.m_num_ranges
* 2)
2451 // lower of Xi and Xj is the lowest point.
2452 if (wi::to_widest (m_base
[i
]) <= wi::to_widest (r
.m_base
[j
]))
2454 res
.quick_push (m_base
[i
]);
2455 res
.quick_push (m_base
[i
+ 1]);
2461 res
.quick_push (r
.m_base
[j
]);
2462 res
.quick_push (r
.m_base
[j
+ 1]);
2467 for ( ; i
< m_num_ranges
* 2; i
+= 2)
2469 res
.quick_push (m_base
[i
]);
2470 res
.quick_push (m_base
[i
+ 1]);
2473 for ( ; j
< r
.m_num_ranges
* 2; j
+= 2)
2475 res
.quick_push (r
.m_base
[j
]);
2476 res
.quick_push (r
.m_base
[j
+ 1]);
2480 // Now normalize the vector removing any overlaps.
2482 for (j
= 2; j
< k
; j
+= 2)
2484 // Current upper+1 is >= lower bound next pair, then we merge ranges.
2485 if (wi::to_widest (res
[i
- 1]) + 1 >= wi::to_widest (res
[j
]))
2487 // New upper bounds is greater of current or the next one.
2488 if (wi::to_widest (res
[j
+ 1]) > wi::to_widest (res
[i
- 1]))
2489 res
[i
- 1] = res
[j
+ 1];
2493 // This is a new distinct range, but no point in copying it
2494 // if it is already in the right place.
2498 res
[i
++] = res
[j
+ 1];
2505 // At this point, the vector should have i ranges, none overlapping.
2506 // Now it simply needs to be copied, and if there are too many
2507 // ranges, merge some. We wont do any analysis as to what the
2508 // "best" merges are, simply combine the final ranges into one.
2509 if (i
> m_max_ranges
* 2)
2511 res
[m_max_ranges
* 2 - 1] = res
[i
- 1];
2512 i
= m_max_ranges
* 2;
2515 for (j
= 0; j
< i
; j
++)
2516 m_base
[j
] = res
[j
];
2517 m_num_ranges
= i
/ 2;
2520 union_nonzero_bits (r
);
2524 // Return TRUE if THIS fully contains R. No undefined or varying cases.
2527 irange::irange_contains_p (const irange
&r
) const
2529 gcc_checking_assert (!undefined_p () && !varying_p ());
2530 gcc_checking_assert (!r
.undefined_p () && !varying_p ());
2532 // In order for THIS to fully contain R, all of the pairs within R must
2533 // be fully contained by the pairs in this object.
2534 signop sign
= TYPE_SIGN (TREE_TYPE(m_base
[0]));
2537 tree rl
= r
.m_base
[0];
2538 tree ru
= r
.m_base
[1];
2543 // If r is contained within this range, move to the next R
2544 if (wi::ge_p (wi::to_wide (rl
), wi::to_wide (l
), sign
)
2545 && wi::le_p (wi::to_wide (ru
), wi::to_wide (u
), sign
))
2547 // This pair is OK, Either done, or bump to the next.
2548 if (++ri
>= r
.num_pairs ())
2550 rl
= r
.m_base
[ri
* 2];
2551 ru
= r
.m_base
[ri
* 2 + 1];
2554 // Otherwise, check if this's pair occurs before R's.
2555 if (wi::lt_p (wi::to_wide (u
), wi::to_wide (rl
), sign
))
2557 // There's still at least one pair of R left.
2558 if (++i
>= num_pairs ())
2561 u
= m_base
[i
* 2 + 1];
2570 // Intersect for multi-ranges. Return TRUE if anything changes.
2573 irange::irange_intersect (const irange
&r
)
2575 gcc_checking_assert (!legacy_mode_p () && !r
.legacy_mode_p ());
2576 gcc_checking_assert (undefined_p () || r
.undefined_p ()
2577 || range_compatible_p (type (), r
.type ()));
2581 if (r
.undefined_p ())
2594 if (r
.num_pairs () == 1)
2596 bool res
= intersect (r
.lower_bound (), r
.upper_bound ());
2600 res
|= intersect_nonzero_bits (r
);
2604 // If R fully contains this, then intersection will change nothing.
2605 if (r
.irange_contains_p (*this))
2606 return intersect_nonzero_bits (r
);
2608 signop sign
= TYPE_SIGN (TREE_TYPE(m_base
[0]));
2609 unsigned bld_pair
= 0;
2610 unsigned bld_lim
= m_max_ranges
;
2611 int_range_max
r2 (*this);
2612 unsigned r2_lim
= r2
.num_pairs ();
2614 for (unsigned i
= 0; i
< r
.num_pairs (); )
2616 // If r1's upper is < r2's lower, we can skip r1's pair.
2617 tree ru
= r
.m_base
[i
* 2 + 1];
2618 tree r2l
= r2
.m_base
[i2
* 2];
2619 if (wi::lt_p (wi::to_wide (ru
), wi::to_wide (r2l
), sign
))
2624 // Likewise, skip r2's pair if its excluded.
2625 tree r2u
= r2
.m_base
[i2
* 2 + 1];
2626 tree rl
= r
.m_base
[i
* 2];
2627 if (wi::lt_p (wi::to_wide (r2u
), wi::to_wide (rl
), sign
))
2632 // No more r2, break.
2636 // Must be some overlap. Find the highest of the lower bounds,
2637 // and set it, unless the build limits lower bounds is already
2639 if (bld_pair
< bld_lim
)
2641 if (wi::ge_p (wi::to_wide (rl
), wi::to_wide (r2l
), sign
))
2642 m_base
[bld_pair
* 2] = rl
;
2644 m_base
[bld_pair
* 2] = r2l
;
2647 // Decrease and set a new upper.
2650 // ...and choose the lower of the upper bounds.
2651 if (wi::le_p (wi::to_wide (ru
), wi::to_wide (r2u
), sign
))
2653 m_base
[bld_pair
* 2 + 1] = ru
;
2655 // Move past the r1 pair and keep trying.
2661 m_base
[bld_pair
* 2 + 1] = r2u
;
2666 // No more r2, break.
2669 // r2 has the higher lower bound.
2672 // At the exit of this loop, it is one of 2 things:
2673 // ran out of r1, or r2, but either means we are done.
2674 m_num_ranges
= bld_pair
;
2675 if (m_num_ranges
== 0)
2682 intersect_nonzero_bits (r
);
2687 // Multirange intersect for a specified wide_int [lb, ub] range.
2688 // Return TRUE if intersect changed anything.
2690 // NOTE: It is the caller's responsibility to intersect the nonzero masks.
2693 irange::intersect (const wide_int
& lb
, const wide_int
& ub
)
2695 // Undefined remains undefined.
2699 if (legacy_mode_p ())
2701 intersect (int_range
<1> (type (), lb
, ub
));
2705 tree range_type
= type();
2706 signop sign
= TYPE_SIGN (range_type
);
2708 gcc_checking_assert (TYPE_PRECISION (range_type
) == wi::get_precision (lb
));
2709 gcc_checking_assert (TYPE_PRECISION (range_type
) == wi::get_precision (ub
));
2711 // If this range is fully contained, then intersection will do nothing.
2712 if (wi::ge_p (lower_bound (), lb
, sign
)
2713 && wi::le_p (upper_bound (), ub
, sign
))
2716 unsigned bld_index
= 0;
2717 unsigned pair_lim
= num_pairs ();
2718 for (unsigned i
= 0; i
< pair_lim
; i
++)
2720 tree pairl
= m_base
[i
* 2];
2721 tree pairu
= m_base
[i
* 2 + 1];
2722 // Once UB is less than a pairs lower bound, we're done.
2723 if (wi::lt_p (ub
, wi::to_wide (pairl
), sign
))
2725 // if LB is greater than this pairs upper, this pair is excluded.
2726 if (wi::lt_p (wi::to_wide (pairu
), lb
, sign
))
2729 // Must be some overlap. Find the highest of the lower bounds,
2731 if (wi::gt_p (lb
, wi::to_wide (pairl
), sign
))
2732 m_base
[bld_index
* 2] = wide_int_to_tree (range_type
, lb
);
2734 m_base
[bld_index
* 2] = pairl
;
2736 // ...and choose the lower of the upper bounds and if the base pair
2737 // has the lower upper bound, need to check next pair too.
2738 if (wi::lt_p (ub
, wi::to_wide (pairu
), sign
))
2740 m_base
[bld_index
++ * 2 + 1] = wide_int_to_tree (range_type
, ub
);
2744 m_base
[bld_index
++ * 2 + 1] = pairu
;
2747 m_num_ranges
= bld_index
;
2748 if (m_num_ranges
== 0)
2755 // No need to call normalize_kind(), as the caller will do this
2756 // while intersecting the nonzero mask.
2763 // Signed 1-bits are strange. You can't subtract 1, because you can't
2764 // represent the number 1. This works around that for the invert routine.
2766 static wide_int
inline
2767 subtract_one (const wide_int
&x
, tree type
, wi::overflow_type
&overflow
)
2769 if (TYPE_SIGN (type
) == SIGNED
)
2770 return wi::add (x
, -1, SIGNED
, &overflow
);
2772 return wi::sub (x
, 1, UNSIGNED
, &overflow
);
2775 // The analogous function for adding 1.
2777 static wide_int
inline
2778 add_one (const wide_int
&x
, tree type
, wi::overflow_type
&overflow
)
2780 if (TYPE_SIGN (type
) == SIGNED
)
2781 return wi::sub (x
, -1, SIGNED
, &overflow
);
2783 return wi::add (x
, 1, UNSIGNED
, &overflow
);
2786 // Return the inverse of a range.
2791 if (legacy_mode_p ())
2793 // We can't just invert VR_RANGE and VR_ANTI_RANGE because we may
2794 // create non-canonical ranges. Use the constructors instead.
2795 if (m_kind
== VR_RANGE
)
2796 *this = value_range (min (), max (), VR_ANTI_RANGE
);
2797 else if (m_kind
== VR_ANTI_RANGE
)
2798 *this = value_range (min (), max ());
2804 gcc_checking_assert (!undefined_p () && !varying_p ());
2806 // We always need one more set of bounds to represent an inverse, so
2807 // if we're at the limit, we can't properly represent things.
2809 // For instance, to represent the inverse of a 2 sub-range set
2810 // [5, 10][20, 30], we would need a 3 sub-range set
2811 // [-MIN, 4][11, 19][31, MAX].
2813 // In this case, return the most conservative thing.
2815 // However, if any of the extremes of the range are -MIN/+MAX, we
2816 // know we will not need an extra bound. For example:
2818 // INVERT([-MIN,20][30,40]) => [21,29][41,+MAX]
2819 // INVERT([-MIN,20][30,MAX]) => [21,29]
2820 tree ttype
= type ();
2821 unsigned prec
= TYPE_PRECISION (ttype
);
2822 signop sign
= TYPE_SIGN (ttype
);
2823 wide_int type_min
= wi::min_value (prec
, sign
);
2824 wide_int type_max
= wi::max_value (prec
, sign
);
2825 m_nonzero_mask
= NULL
;
2826 if (m_num_ranges
== m_max_ranges
2827 && lower_bound () != type_min
2828 && upper_bound () != type_max
)
2830 m_base
[1] = wide_int_to_tree (ttype
, type_max
);
2834 // The algorithm is as follows. To calculate INVERT ([a,b][c,d]), we
2835 // generate [-MIN, a-1][b+1, c-1][d+1, MAX].
2837 // If there is an over/underflow in the calculation for any
2838 // sub-range, we eliminate that subrange. This allows us to easily
2839 // calculate INVERT([-MIN, 5]) with: [-MIN, -MIN-1][6, MAX]. And since
2840 // we eliminate the underflow, only [6, MAX] remains.
2842 wi::overflow_type ovf
;
2843 // Construct leftmost range.
2844 int_range_max
orig_range (*this);
2845 unsigned nitems
= 0;
2847 // If this is going to underflow on the MINUS 1, don't even bother
2848 // checking. This also handles subtracting one from an unsigned 0,
2849 // which doesn't set the underflow bit.
2850 if (type_min
!= orig_range
.lower_bound ())
2852 m_base
[nitems
++] = wide_int_to_tree (ttype
, type_min
);
2853 tmp
= subtract_one (orig_range
.lower_bound (), ttype
, ovf
);
2854 m_base
[nitems
++] = wide_int_to_tree (ttype
, tmp
);
2859 // Construct middle ranges if applicable.
2860 if (orig_range
.num_pairs () > 1)
2863 for (; j
< (orig_range
.num_pairs () * 2) - 1; j
+= 2)
2865 // The middle ranges cannot have MAX/MIN, so there's no need
2866 // to check for unsigned overflow on the +1 and -1 here.
2867 tmp
= wi::add (wi::to_wide (orig_range
.m_base
[j
]), 1, sign
, &ovf
);
2868 m_base
[nitems
++] = wide_int_to_tree (ttype
, tmp
);
2869 tmp
= subtract_one (wi::to_wide (orig_range
.m_base
[j
+ 1]),
2871 m_base
[nitems
++] = wide_int_to_tree (ttype
, tmp
);
2877 // Construct rightmost range.
2879 // However, if this will overflow on the PLUS 1, don't even bother.
2880 // This also handles adding one to an unsigned MAX, which doesn't
2881 // set the overflow bit.
2882 if (type_max
!= wi::to_wide (orig_range
.m_base
[i
]))
2884 tmp
= add_one (wi::to_wide (orig_range
.m_base
[i
]), ttype
, ovf
);
2885 m_base
[nitems
++] = wide_int_to_tree (ttype
, tmp
);
2886 m_base
[nitems
++] = wide_int_to_tree (ttype
, type_max
);
2890 m_num_ranges
= nitems
/ 2;
2892 // We disallow undefined or varying coming in, so the result can
2893 // only be a VR_RANGE.
2894 gcc_checking_assert (m_kind
== VR_RANGE
);
2900 // Return the nonzero bits inherent in the range.
2903 irange::get_nonzero_bits_from_range () const
2905 // For legacy symbolics.
2907 return wi::shwi (-1, TYPE_PRECISION (type ()));
2909 wide_int min
= lower_bound ();
2910 wide_int max
= upper_bound ();
2911 wide_int xorv
= min
^ max
;
2914 unsigned prec
= TYPE_PRECISION (type ());
2915 xorv
= wi::mask (prec
- wi::clz (xorv
), false, prec
);
2920 // If the the nonzero mask can be trivially converted to a range, do
2921 // so and return TRUE.
2924 irange::set_range_from_nonzero_bits ()
2926 gcc_checking_assert (!undefined_p ());
2927 if (!m_nonzero_mask
)
2929 unsigned popcount
= wi::popcount (wi::to_wide (m_nonzero_mask
));
2931 // If we have only one bit set in the mask, we can figure out the
2932 // range immediately.
2935 // Make sure we don't pessimize the range.
2936 if (!contains_p (m_nonzero_mask
))
2939 bool has_zero
= contains_p (build_zero_cst (type ()));
2940 tree nz
= m_nonzero_mask
;
2942 m_nonzero_mask
= nz
;
2946 zero
.set_zero (type ());
2951 else if (popcount
== 0)
2960 irange::set_nonzero_bits (const wide_int_ref
&bits
)
2962 gcc_checking_assert (!undefined_p ());
2963 unsigned prec
= TYPE_PRECISION (type ());
2967 m_nonzero_mask
= NULL
;
2974 // Drop VARYINGs with a nonzero mask to a plain range.
2975 if (m_kind
== VR_VARYING
&& bits
!= -1)
2978 wide_int nz
= wide_int::from (bits
, prec
, TYPE_SIGN (type ()));
2979 m_nonzero_mask
= wide_int_to_tree (type (), nz
);
2980 if (set_range_from_nonzero_bits ())
2988 // Return the nonzero bitmask. This will return the nonzero bits plus
2989 // the nonzero bits inherent in the range.
2992 irange::get_nonzero_bits () const
2994 gcc_checking_assert (!undefined_p ());
2995 // The nonzero mask inherent in the range is calculated on-demand.
2996 // For example, [0,255] does not have a 0xff nonzero mask by default
2997 // (unless manually set). This saves us considerable time, because
2998 // setting it at creation incurs a large penalty for irange::set.
2999 // At the time of writing there was a 5% slowdown in VRP if we kept
3000 // the mask precisely up to date at all times. Instead, we default
3001 // to -1 and set it when explicitly requested. However, this
3002 // function will always return the correct mask.
3004 return wi::to_wide (m_nonzero_mask
) & get_nonzero_bits_from_range ();
3006 return get_nonzero_bits_from_range ();
3009 // Convert tree mask to wide_int. Returns -1 for NULL masks.
3012 mask_to_wi (tree mask
, tree type
)
3015 return wi::to_wide (mask
);
3017 return wi::shwi (-1, TYPE_PRECISION (type
));
3020 // Intersect the nonzero bits in R into THIS and normalize the range.
3021 // Return TRUE if the intersection changed anything.
3024 irange::intersect_nonzero_bits (const irange
&r
)
3026 gcc_checking_assert (!undefined_p () && !r
.undefined_p ());
3028 if (!m_nonzero_mask
&& !r
.m_nonzero_mask
)
3036 bool changed
= false;
3038 if (mask_to_wi (m_nonzero_mask
, t
) != mask_to_wi (r
.m_nonzero_mask
, t
))
3040 wide_int nz
= get_nonzero_bits () & r
.get_nonzero_bits ();
3041 // If the nonzero bits did not change, return false.
3042 if (nz
== get_nonzero_bits ())
3045 m_nonzero_mask
= wide_int_to_tree (t
, nz
);
3046 if (set_range_from_nonzero_bits ())
3056 // Union the nonzero bits in R into THIS and normalize the range.
3057 // Return TRUE if the union changed anything.
3060 irange::union_nonzero_bits (const irange
&r
)
3062 gcc_checking_assert (!undefined_p () && !r
.undefined_p ());
3064 if (!m_nonzero_mask
&& !r
.m_nonzero_mask
)
3072 bool changed
= false;
3074 if (mask_to_wi (m_nonzero_mask
, t
) != mask_to_wi (r
.m_nonzero_mask
, t
))
3076 wide_int nz
= get_nonzero_bits () | r
.get_nonzero_bits ();
3077 m_nonzero_mask
= wide_int_to_tree (t
, nz
);
3078 // No need to call set_range_from_nonzero_bits, because we'll
3079 // never narrow the range. Besides, it would cause endless
3080 // recursion because of the union_ in
3081 // set_range_from_nonzero_bits.
3091 dump_value_range (FILE *file
, const vrange
*vr
)
3097 debug (const vrange
*vr
)
3099 dump_value_range (stderr
, vr
);
3100 fprintf (stderr
, "\n");
3104 debug (const vrange
&vr
)
3110 debug (const value_range
*vr
)
3112 dump_value_range (stderr
, vr
);
3113 fprintf (stderr
, "\n");
3117 debug (const value_range
&vr
)
3119 dump_value_range (stderr
, &vr
);
3120 fprintf (stderr
, "\n");
3123 /* Create two value-ranges in *VR0 and *VR1 from the anti-range *AR
3124 so that *VR0 U *VR1 == *AR. Returns true if that is possible,
3125 false otherwise. If *AR can be represented with a single range
3126 *VR1 will be VR_UNDEFINED. */
3129 ranges_from_anti_range (const value_range
*ar
,
3130 value_range
*vr0
, value_range
*vr1
)
3132 tree type
= ar
->type ();
3134 vr0
->set_undefined ();
3135 vr1
->set_undefined ();
3137 /* As a future improvement, we could handle ~[0, A] as: [-INF, -1] U
3138 [A+1, +INF]. Not sure if this helps in practice, though. */
3140 if (ar
->kind () != VR_ANTI_RANGE
3141 || TREE_CODE (ar
->min ()) != INTEGER_CST
3142 || TREE_CODE (ar
->max ()) != INTEGER_CST
3143 || !vrp_val_min (type
)
3144 || !vrp_val_max (type
))
3147 if (tree_int_cst_lt (vrp_val_min (type
), ar
->min ()))
3148 vr0
->set (vrp_val_min (type
),
3149 wide_int_to_tree (type
, wi::to_wide (ar
->min ()) - 1));
3150 if (tree_int_cst_lt (ar
->max (), vrp_val_max (type
)))
3151 vr1
->set (wide_int_to_tree (type
, wi::to_wide (ar
->max ()) + 1),
3152 vrp_val_max (type
));
3153 if (vr0
->undefined_p ())
3156 vr1
->set_undefined ();
3159 return !vr0
->undefined_p ();
3163 range_has_numeric_bounds_p (const irange
*vr
)
3165 return (!vr
->undefined_p ()
3166 && TREE_CODE (vr
->min ()) == INTEGER_CST
3167 && TREE_CODE (vr
->max ()) == INTEGER_CST
);
3170 /* Return whether VAL is equal to the maximum value of its type.
3171 We can't do a simple equality comparison with TYPE_MAX_VALUE because
3172 C typedefs and Ada subtypes can produce types whose TYPE_MAX_VALUE
3173 is not == to the integer constant with the same value in the type. */
3176 vrp_val_is_max (const_tree val
)
3178 tree type_max
= vrp_val_max (TREE_TYPE (val
));
3179 return (val
== type_max
3180 || (type_max
!= NULL_TREE
3181 && operand_equal_p (val
, type_max
, 0)));
3184 /* Return whether VAL is equal to the minimum value of its type. */
3187 vrp_val_is_min (const_tree val
)
3189 tree type_min
= vrp_val_min (TREE_TYPE (val
));
3190 return (val
== type_min
3191 || (type_min
!= NULL_TREE
3192 && operand_equal_p (val
, type_min
, 0)));
3195 /* Return true, if VAL1 and VAL2 are equal values for VRP purposes. */
3198 vrp_operand_equal_p (const_tree val1
, const_tree val2
)
3202 if (!val1
|| !val2
|| !operand_equal_p (val1
, val2
, 0))
3207 // ?? These stubs are for ipa-prop.cc which use a value_range in a
3208 // hash_traits. hash-traits.h defines an extern of gt_ggc_mx (T &)
3209 // instead of picking up the gt_ggc_mx (T *) version.
3211 gt_pch_nx (int_range
<1> *&x
)
3213 return gt_pch_nx ((irange
*) x
);
3217 gt_ggc_mx (int_range
<1> *&x
)
3219 return gt_ggc_mx ((irange
*) x
);
3222 #define DEFINE_INT_RANGE_INSTANCE(N) \
3223 template int_range<N>::int_range(tree, tree, value_range_kind); \
3224 template int_range<N>::int_range(tree_node *, \
3227 value_range_kind); \
3228 template int_range<N>::int_range(tree); \
3229 template int_range<N>::int_range(const irange &); \
3230 template int_range<N>::int_range(const int_range &); \
3231 template int_range<N>& int_range<N>::operator= (const int_range &);
3233 DEFINE_INT_RANGE_INSTANCE(1)
3234 DEFINE_INT_RANGE_INSTANCE(2)
3235 DEFINE_INT_RANGE_INSTANCE(3)
3236 DEFINE_INT_RANGE_INSTANCE(255)
3239 #include "selftest.h"
3243 #define INT(N) build_int_cst (integer_type_node, (N))
3244 #define UINT(N) build_int_cstu (unsigned_type_node, (N))
3245 #define UINT128(N) build_int_cstu (u128_type, (N))
3246 #define UCHAR(N) build_int_cstu (unsigned_char_type_node, (N))
3247 #define SCHAR(N) build_int_cst (signed_char_type_node, (N))
3250 build_range3 (int a
, int b
, int c
, int d
, int e
, int f
)
3252 int_range
<3> i1 (INT (a
), INT (b
));
3253 int_range
<3> i2 (INT (c
), INT (d
));
3254 int_range
<3> i3 (INT (e
), INT (f
));
3261 range_tests_irange3 ()
3263 typedef int_range
<3> int_range3
;
3264 int_range3 r0
, r1
, r2
;
3265 int_range3 i1
, i2
, i3
;
3267 // ([10,20] U [5,8]) U [1,3] ==> [1,3][5,8][10,20].
3268 r0
= int_range3 (INT (10), INT (20));
3269 r1
= int_range3 (INT (5), INT (8));
3271 r1
= int_range3 (INT (1), INT (3));
3273 ASSERT_TRUE (r0
== build_range3 (1, 3, 5, 8, 10, 20));
3275 // [1,3][5,8][10,20] U [-5,0] => [-5,3][5,8][10,20].
3276 r1
= int_range3 (INT (-5), INT (0));
3278 ASSERT_TRUE (r0
== build_range3 (-5, 3, 5, 8, 10, 20));
3280 // [10,20][30,40] U [50,60] ==> [10,20][30,40][50,60].
3281 r1
= int_range3 (INT (50), INT (60));
3282 r0
= int_range3 (INT (10), INT (20));
3283 r0
.union_ (int_range3 (INT (30), INT (40)));
3285 ASSERT_TRUE (r0
== build_range3 (10, 20, 30, 40, 50, 60));
3286 // [10,20][30,40][50,60] U [70, 80] ==> [10,20][30,40][50,60][70,80].
3287 r1
= int_range3 (INT (70), INT (80));
3290 r2
= build_range3 (10, 20, 30, 40, 50, 60);
3291 r2
.union_ (int_range3 (INT (70), INT (80)));
3292 ASSERT_TRUE (r0
== r2
);
3294 // [10,20][30,40][50,60] U [6,35] => [6,40][50,60].
3295 r0
= build_range3 (10, 20, 30, 40, 50, 60);
3296 r1
= int_range3 (INT (6), INT (35));
3298 r1
= int_range3 (INT (6), INT (40));
3299 r1
.union_ (int_range3 (INT (50), INT (60)));
3300 ASSERT_TRUE (r0
== r1
);
3302 // [10,20][30,40][50,60] U [6,60] => [6,60].
3303 r0
= build_range3 (10, 20, 30, 40, 50, 60);
3304 r1
= int_range3 (INT (6), INT (60));
3306 ASSERT_TRUE (r0
== int_range3 (INT (6), INT (60)));
3308 // [10,20][30,40][50,60] U [6,70] => [6,70].
3309 r0
= build_range3 (10, 20, 30, 40, 50, 60);
3310 r1
= int_range3 (INT (6), INT (70));
3312 ASSERT_TRUE (r0
== int_range3 (INT (6), INT (70)));
3314 // [10,20][30,40][50,60] U [35,70] => [10,20][30,70].
3315 r0
= build_range3 (10, 20, 30, 40, 50, 60);
3316 r1
= int_range3 (INT (35), INT (70));
3318 r1
= int_range3 (INT (10), INT (20));
3319 r1
.union_ (int_range3 (INT (30), INT (70)));
3320 ASSERT_TRUE (r0
== r1
);
3322 // [10,20][30,40][50,60] U [15,35] => [10,40][50,60].
3323 r0
= build_range3 (10, 20, 30, 40, 50, 60);
3324 r1
= int_range3 (INT (15), INT (35));
3326 r1
= int_range3 (INT (10), INT (40));
3327 r1
.union_ (int_range3 (INT (50), INT (60)));
3328 ASSERT_TRUE (r0
== r1
);
3330 // [10,20][30,40][50,60] U [35,35] => [10,20][30,40][50,60].
3331 r0
= build_range3 (10, 20, 30, 40, 50, 60);
3332 r1
= int_range3 (INT (35), INT (35));
3334 ASSERT_TRUE (r0
== build_range3 (10, 20, 30, 40, 50, 60));
3338 range_tests_int_range_max ()
3341 unsigned int nrange
;
3343 // Build a huge multi-range range.
3344 for (nrange
= 0; nrange
< 50; ++nrange
)
3346 int_range
<1> tmp (INT (nrange
*10), INT (nrange
*10 + 5));
3349 ASSERT_TRUE (big
.num_pairs () == nrange
);
3351 // Verify that we can copy it without loosing precision.
3352 int_range_max
copy (big
);
3353 ASSERT_TRUE (copy
.num_pairs () == nrange
);
3355 // Inverting it should produce one more sub-range.
3357 ASSERT_TRUE (big
.num_pairs () == nrange
+ 1);
3359 int_range
<1> tmp (INT (5), INT (37));
3360 big
.intersect (tmp
);
3361 ASSERT_TRUE (big
.num_pairs () == 4);
3363 // Test that [10,10][20,20] does NOT contain 15.
3365 int_range_max
i1 (build_int_cst (integer_type_node
, 10),
3366 build_int_cst (integer_type_node
, 10));
3367 int_range_max
i2 (build_int_cst (integer_type_node
, 20),
3368 build_int_cst (integer_type_node
, 20));
3370 ASSERT_FALSE (i1
.contains_p (build_int_cst (integer_type_node
, 15)));
3375 range_tests_legacy ()
3377 // Test truncating copy to int_range<1>.
3378 int_range
<3> big
= build_range3 (10, 20, 30, 40, 50, 60);
3379 int_range
<1> small
= big
;
3380 ASSERT_TRUE (small
== int_range
<1> (INT (10), INT (60)));
3382 // Test truncating copy to int_range<2>.
3383 int_range
<2> medium
= big
;
3384 ASSERT_TRUE (!medium
.undefined_p ());
3386 // Test that a truncating copy of [MIN,20][22,40][80,MAX]
3387 // ends up as a conservative anti-range of ~[21,21].
3388 big
= int_range
<3> (vrp_val_min (integer_type_node
), INT (20));
3389 big
.union_ (int_range
<1> (INT (22), INT (40)));
3390 big
.union_ (int_range
<1> (INT (80), vrp_val_max (integer_type_node
)));
3392 ASSERT_TRUE (small
== int_range
<1> (INT (21), INT (21), VR_ANTI_RANGE
));
3394 // Copying a legacy symbolic to an int_range should normalize the
3395 // symbolic at copy time.
3397 tree ssa
= make_ssa_name (integer_type_node
);
3398 value_range
legacy_range (ssa
, INT (25));
3399 int_range
<2> copy
= legacy_range
;
3400 ASSERT_TRUE (copy
== int_range
<2> (vrp_val_min (integer_type_node
),
3403 // Test that copying ~[abc_23, abc_23] to a multi-range yields varying.
3404 legacy_range
= value_range (ssa
, ssa
, VR_ANTI_RANGE
);
3405 copy
= legacy_range
;
3406 ASSERT_TRUE (copy
.varying_p ());
3409 // VARYING of different sizes should not be equal.
3410 tree big_type
= build_nonstandard_integer_type (32, 1);
3411 tree small_type
= build_nonstandard_integer_type (16, 1);
3412 int_range_max
r0 (big_type
);
3413 int_range_max
r1 (small_type
);
3414 ASSERT_TRUE (r0
!= r1
);
3415 value_range
vr0 (big_type
);
3416 int_range_max
vr1 (small_type
);
3417 ASSERT_TRUE (vr0
!= vr1
);
3420 // Simulate -fstrict-enums where the domain of a type is less than the
3424 range_tests_strict_enum ()
3426 // The enum can only hold [0, 3].
3427 tree rtype
= copy_node (unsigned_type_node
);
3428 TYPE_MIN_VALUE (rtype
) = build_int_cstu (rtype
, 0);
3429 TYPE_MAX_VALUE (rtype
) = build_int_cstu (rtype
, 3);
3431 // Test that even though vr1 covers the strict enum domain ([0, 3]),
3432 // it does not cover the domain of the underlying type.
3433 int_range
<1> vr1 (build_int_cstu (rtype
, 0), build_int_cstu (rtype
, 1));
3434 int_range
<1> vr2 (build_int_cstu (rtype
, 2), build_int_cstu (rtype
, 3));
3436 ASSERT_TRUE (vr1
== int_range
<1> (build_int_cstu (rtype
, 0),
3437 build_int_cstu (rtype
, 3)));
3438 ASSERT_FALSE (vr1
.varying_p ());
3440 // Test that copying to a multi-range does not change things.
3441 int_range
<2> ir1 (vr1
);
3442 ASSERT_TRUE (ir1
== vr1
);
3443 ASSERT_FALSE (ir1
.varying_p ());
3445 // The same test as above, but using TYPE_{MIN,MAX}_VALUE instead of [0,3].
3446 vr1
= int_range
<1> (TYPE_MIN_VALUE (rtype
), TYPE_MAX_VALUE (rtype
));
3448 ASSERT_TRUE (ir1
== vr1
);
3449 ASSERT_FALSE (ir1
.varying_p ());
3455 tree u128_type
= build_nonstandard_integer_type (128, /*unsigned=*/1);
3456 int_range
<1> i1
, i2
, i3
;
3457 int_range
<1> r0
, r1
, rold
;
3459 // Test 1-bit signed integer union.
3460 // [-1,-1] U [0,0] = VARYING.
3461 tree one_bit_type
= build_nonstandard_integer_type (1, 0);
3462 tree one_bit_min
= vrp_val_min (one_bit_type
);
3463 tree one_bit_max
= vrp_val_max (one_bit_type
);
3465 int_range
<2> min (one_bit_min
, one_bit_min
);
3466 int_range
<2> max (one_bit_max
, one_bit_max
);
3468 ASSERT_TRUE (max
.varying_p ());
3470 // Test that we can set a range of true+false for a 1-bit signed int.
3471 r0
= range_true_and_false (one_bit_type
);
3473 // Test inversion of 1-bit signed integers.
3475 int_range
<2> min (one_bit_min
, one_bit_min
);
3476 int_range
<2> max (one_bit_max
, one_bit_max
);
3480 ASSERT_TRUE (t
== max
);
3483 ASSERT_TRUE (t
== min
);
3486 // Test that NOT(255) is [0..254] in 8-bit land.
3487 int_range
<1> not_255 (UCHAR (255), UCHAR (255), VR_ANTI_RANGE
);
3488 ASSERT_TRUE (not_255
== int_range
<1> (UCHAR (0), UCHAR (254)));
3490 // Test that NOT(0) is [1..255] in 8-bit land.
3491 int_range
<1> not_zero
= range_nonzero (unsigned_char_type_node
);
3492 ASSERT_TRUE (not_zero
== int_range
<1> (UCHAR (1), UCHAR (255)));
3494 // Check that [0,127][0x..ffffff80,0x..ffffff]
3495 // => ~[128, 0x..ffffff7f].
3496 r0
= int_range
<1> (UINT128 (0), UINT128 (127));
3497 tree high
= build_minus_one_cst (u128_type
);
3498 // low = -1 - 127 => 0x..ffffff80.
3499 tree low
= fold_build2 (MINUS_EXPR
, u128_type
, high
, UINT128(127));
3500 r1
= int_range
<1> (low
, high
); // [0x..ffffff80, 0x..ffffffff]
3501 // r0 = [0,127][0x..ffffff80,0x..fffffff].
3503 // r1 = [128, 0x..ffffff7f].
3504 r1
= int_range
<1> (UINT128(128),
3505 fold_build2 (MINUS_EXPR
, u128_type
,
3506 build_minus_one_cst (u128_type
),
3509 ASSERT_TRUE (r0
== r1
);
3511 r0
.set_varying (integer_type_node
);
3512 tree minint
= wide_int_to_tree (integer_type_node
, r0
.lower_bound ());
3513 tree maxint
= wide_int_to_tree (integer_type_node
, r0
.upper_bound ());
3515 r0
.set_varying (short_integer_type_node
);
3517 r0
.set_varying (unsigned_type_node
);
3518 tree maxuint
= wide_int_to_tree (unsigned_type_node
, r0
.upper_bound ());
3520 // Check that ~[0,5] => [6,MAX] for unsigned int.
3521 r0
= int_range
<1> (UINT (0), UINT (5));
3523 ASSERT_TRUE (r0
== int_range
<1> (UINT(6), maxuint
));
3525 // Check that ~[10,MAX] => [0,9] for unsigned int.
3526 r0
= int_range
<1> (UINT(10), maxuint
);
3528 ASSERT_TRUE (r0
== int_range
<1> (UINT (0), UINT (9)));
3530 // Check that ~[0,5] => [6,MAX] for unsigned 128-bit numbers.
3531 r0
= int_range
<1> (UINT128 (0), UINT128 (5), VR_ANTI_RANGE
);
3532 r1
= int_range
<1> (UINT128(6), build_minus_one_cst (u128_type
));
3533 ASSERT_TRUE (r0
== r1
);
3535 // Check that [~5] is really [-MIN,4][6,MAX].
3536 r0
= int_range
<1> (INT (5), INT (5), VR_ANTI_RANGE
);
3537 r1
= int_range
<1> (minint
, INT (4));
3538 r1
.union_ (int_range
<1> (INT (6), maxint
));
3539 ASSERT_FALSE (r1
.undefined_p ());
3540 ASSERT_TRUE (r0
== r1
);
3542 r1
= int_range
<1> (INT (5), INT (5));
3543 int_range
<1> r2 (r1
);
3544 ASSERT_TRUE (r1
== r2
);
3546 r1
= int_range
<1> (INT (5), INT (10));
3548 r1
= int_range
<1> (integer_type_node
,
3549 wi::to_wide (INT (5)), wi::to_wide (INT (10)));
3550 ASSERT_TRUE (r1
.contains_p (INT (7)));
3552 r1
= int_range
<1> (SCHAR (0), SCHAR (20));
3553 ASSERT_TRUE (r1
.contains_p (SCHAR(15)));
3554 ASSERT_FALSE (r1
.contains_p (SCHAR(300)));
3556 // NOT([10,20]) ==> [-MIN,9][21,MAX].
3557 r0
= r1
= int_range
<1> (INT (10), INT (20));
3558 r2
= int_range
<1> (minint
, INT(9));
3559 r2
.union_ (int_range
<1> (INT(21), maxint
));
3560 ASSERT_FALSE (r2
.undefined_p ());
3562 ASSERT_TRUE (r1
== r2
);
3563 // Test that NOT(NOT(x)) == x.
3565 ASSERT_TRUE (r0
== r2
);
3567 // Test that booleans and their inverse work as expected.
3568 r0
= range_zero (boolean_type_node
);
3569 ASSERT_TRUE (r0
== int_range
<1> (build_zero_cst (boolean_type_node
),
3570 build_zero_cst (boolean_type_node
)));
3572 ASSERT_TRUE (r0
== int_range
<1> (build_one_cst (boolean_type_node
),
3573 build_one_cst (boolean_type_node
)));
3575 // Make sure NULL and non-NULL of pointer types work, and that
3576 // inverses of them are consistent.
3577 tree voidp
= build_pointer_type (void_type_node
);
3578 r0
= range_zero (voidp
);
3582 ASSERT_TRUE (r0
== r1
);
3584 // [10,20] U [15, 30] => [10, 30].
3585 r0
= int_range
<1> (INT (10), INT (20));
3586 r1
= int_range
<1> (INT (15), INT (30));
3588 ASSERT_TRUE (r0
== int_range
<1> (INT (10), INT (30)));
3590 // [15,40] U [] => [15,40].
3591 r0
= int_range
<1> (INT (15), INT (40));
3592 r1
.set_undefined ();
3594 ASSERT_TRUE (r0
== int_range
<1> (INT (15), INT (40)));
3596 // [10,20] U [10,10] => [10,20].
3597 r0
= int_range
<1> (INT (10), INT (20));
3598 r1
= int_range
<1> (INT (10), INT (10));
3600 ASSERT_TRUE (r0
== int_range
<1> (INT (10), INT (20)));
3602 // [10,20] U [9,9] => [9,20].
3603 r0
= int_range
<1> (INT (10), INT (20));
3604 r1
= int_range
<1> (INT (9), INT (9));
3606 ASSERT_TRUE (r0
== int_range
<1> (INT (9), INT (20)));
3608 // [10,20] ^ [15,30] => [15,20].
3609 r0
= int_range
<1> (INT (10), INT (20));
3610 r1
= int_range
<1> (INT (15), INT (30));
3612 ASSERT_TRUE (r0
== int_range
<1> (INT (15), INT (20)));
3614 // Test the internal sanity of wide_int's wrt HWIs.
3615 ASSERT_TRUE (wi::max_value (TYPE_PRECISION (boolean_type_node
),
3616 TYPE_SIGN (boolean_type_node
))
3617 == wi::uhwi (1, TYPE_PRECISION (boolean_type_node
)));
3620 r0
= int_range
<1> (INT (0), INT (0));
3621 ASSERT_TRUE (r0
.zero_p ());
3623 // Test nonzero_p().
3624 r0
= int_range
<1> (INT (0), INT (0));
3626 ASSERT_TRUE (r0
.nonzero_p ());
3628 // test legacy interaction
3630 r0
= int_range
<1> (UINT (1), UINT (1), VR_ANTI_RANGE
);
3632 r1
= int_range
<1> (UINT (3), UINT (3), VR_ANTI_RANGE
);
3634 // vv = [0,0][2,2][4, MAX]
3635 int_range
<3> vv
= r0
;
3638 ASSERT_TRUE (vv
.contains_p (UINT (2)));
3639 ASSERT_TRUE (vv
.num_pairs () == 3);
3641 // create r0 as legacy [1,1]
3642 r0
= int_range
<1> (UINT (1), UINT (1));
3643 // And union it with [0,0][2,2][4,MAX] multi range
3645 // The result should be [0,2][4,MAX], or ~[3,3] but it must contain 2
3646 ASSERT_TRUE (r0
.contains_p (UINT (2)));
3650 range_tests_nonzero_bits ()
3652 int_range
<2> r0
, r1
;
3654 // Adding nonzero bits to a varying drops the varying.
3655 r0
.set_varying (integer_type_node
);
3656 r0
.set_nonzero_bits (255);
3657 ASSERT_TRUE (!r0
.varying_p ());
3658 // Dropping the nonzero bits brings us back to varying.
3659 r0
.set_nonzero_bits (-1);
3660 ASSERT_TRUE (r0
.varying_p ());
3662 // Test contains_p with nonzero bits.
3663 r0
.set_zero (integer_type_node
);
3664 ASSERT_TRUE (r0
.contains_p (INT (0)));
3665 ASSERT_FALSE (r0
.contains_p (INT (1)));
3666 r0
.set_nonzero_bits (0xfe);
3667 ASSERT_FALSE (r0
.contains_p (INT (0x100)));
3668 ASSERT_FALSE (r0
.contains_p (INT (0x3)));
3670 // Union of nonzero bits.
3671 r0
.set_varying (integer_type_node
);
3672 r0
.set_nonzero_bits (0xf0);
3673 r1
.set_varying (integer_type_node
);
3674 r1
.set_nonzero_bits (0xf);
3676 ASSERT_TRUE (r0
.get_nonzero_bits () == 0xff);
3678 // Intersect of nonzero bits.
3679 r0
.set (INT (0), INT (255));
3680 r0
.set_nonzero_bits (0xfe);
3681 r1
.set_varying (integer_type_node
);
3682 r1
.set_nonzero_bits (0xf0);
3684 ASSERT_TRUE (r0
.get_nonzero_bits () == 0xf0);
3686 // Intersect where the mask of nonzero bits is implicit from the range.
3687 r0
.set_varying (integer_type_node
);
3688 r1
.set (INT (0), INT (255));
3690 ASSERT_TRUE (r0
.get_nonzero_bits () == 0xff);
3692 // The union of a mask of 0xff..ffff00 with a mask of 0xff spans the
3693 // entire domain, and makes the range a varying.
3694 r0
.set_varying (integer_type_node
);
3695 wide_int x
= wi::shwi (0xff, TYPE_PRECISION (integer_type_node
));
3696 x
= wi::bit_not (x
);
3697 r0
.set_nonzero_bits (x
); // 0xff..ff00
3698 r1
.set_varying (integer_type_node
);
3699 r1
.set_nonzero_bits (0xff);
3701 ASSERT_TRUE (r0
.varying_p ());
3703 // Test that setting a nonzero bit of 1 does not pessimize the range.
3704 r0
.set_zero (integer_type_node
);
3705 r0
.set_nonzero_bits (1);
3706 ASSERT_TRUE (r0
.zero_p ());
3709 // Build an frange from string endpoints.
3711 static inline frange
3712 frange_float (const char *lb
, const char *ub
, tree type
= float_type_node
)
3714 REAL_VALUE_TYPE min
, max
;
3715 gcc_assert (real_from_string (&min
, lb
) == 0);
3716 gcc_assert (real_from_string (&max
, ub
) == 0);
3717 return frange (type
, min
, max
);
3724 REAL_VALUE_TYPE q
, r
;
3727 // Equal ranges but with differing NAN bits are not equal.
3728 if (HONOR_NANS (float_type_node
))
3730 r1
= frange_float ("10", "12");
3738 // [10, 20] NAN ^ [30, 40] NAN = NAN.
3739 r0
= frange_float ("10", "20");
3740 r1
= frange_float ("30", "40");
3742 ASSERT_TRUE (r0
.known_isnan ());
3744 // [3,5] U [5,10] NAN = ... NAN
3745 r0
= frange_float ("3", "5");
3747 r1
= frange_float ("5", "10");
3749 ASSERT_TRUE (r0
.maybe_isnan ());
3752 // NAN ranges are not equal to each other.
3753 r0
.set_nan (float_type_node
);
3755 ASSERT_FALSE (r0
== r1
);
3756 ASSERT_FALSE (r0
== r0
);
3757 ASSERT_TRUE (r0
!= r0
);
3759 // [5,6] U NAN = [5,6] NAN.
3760 r0
= frange_float ("5", "6");
3762 r1
.set_nan (float_type_node
);
3764 real_from_string (&q
, "5");
3765 real_from_string (&r
, "6");
3766 ASSERT_TRUE (real_identical (&q
, &r0
.lower_bound ()));
3767 ASSERT_TRUE (real_identical (&r
, &r0
.upper_bound ()));
3768 ASSERT_TRUE (r0
.maybe_isnan ());
3771 r0
.set_nan (float_type_node
);
3772 r1
.set_nan (float_type_node
);
3774 ASSERT_TRUE (r0
.known_isnan ());
3776 // [INF, INF] NAN ^ NAN = NAN
3777 r0
.set_nan (float_type_node
);
3778 r1
= frange_float ("+Inf", "+Inf");
3779 if (!HONOR_NANS (float_type_node
))
3782 ASSERT_TRUE (r0
.known_isnan ());
3785 r0
.set_nan (float_type_node
);
3786 r1
.set_nan (float_type_node
);
3788 ASSERT_TRUE (r0
.known_isnan ());
3790 // +NAN ^ -NAN = UNDEFINED
3791 r0
.set_nan (float_type_node
, false);
3792 r1
.set_nan (float_type_node
, true);
3794 ASSERT_TRUE (r0
.undefined_p ());
3796 // VARYING ^ NAN = NAN.
3797 r0
.set_nan (float_type_node
);
3798 r1
.set_varying (float_type_node
);
3800 ASSERT_TRUE (r0
.known_isnan ());
3802 // [3,4] ^ NAN = UNDEFINED.
3803 r0
= frange_float ("3", "4");
3805 r1
.set_nan (float_type_node
);
3807 ASSERT_TRUE (r0
.undefined_p ());
3809 // [-3, 5] ^ NAN = UNDEFINED
3810 r0
= frange_float ("-3", "5");
3812 r1
.set_nan (float_type_node
);
3814 ASSERT_TRUE (r0
.undefined_p ());
3816 // Setting the NAN bit to yes does not make us a known NAN.
3817 r0
.set_varying (float_type_node
);
3819 ASSERT_FALSE (r0
.known_isnan ());
3821 // NAN is in a VARYING.
3822 r0
.set_varying (float_type_node
);
3823 real_nan (&r
, "", 1, TYPE_MODE (float_type_node
));
3824 tree nan
= build_real (float_type_node
, r
);
3825 ASSERT_TRUE (r0
.contains_p (nan
));
3827 // -NAN is in a VARYING.
3828 r0
.set_varying (float_type_node
);
3829 q
= real_value_negate (&r
);
3830 tree neg_nan
= build_real (float_type_node
, q
);
3831 ASSERT_TRUE (r0
.contains_p (neg_nan
));
3833 // Clearing the NAN on a [] NAN is the empty set.
3834 r0
.set_nan (float_type_node
);
3836 ASSERT_TRUE (r0
.undefined_p ());
3838 // [10,20] NAN ^ [21,25] NAN = [NAN]
3839 r0
= frange_float ("10", "20");
3841 r1
= frange_float ("21", "25");
3844 ASSERT_TRUE (r0
.known_isnan ());
3846 // NAN U [5,6] should be [5,6] +-NAN.
3847 r0
.set_nan (float_type_node
);
3848 r1
= frange_float ("5", "6");
3851 real_from_string (&q
, "5");
3852 real_from_string (&r
, "6");
3853 ASSERT_TRUE (real_identical (&q
, &r0
.lower_bound ()));
3854 ASSERT_TRUE (real_identical (&r
, &r0
.upper_bound ()));
3855 ASSERT_TRUE (!r0
.signbit_p (signbit
));
3856 ASSERT_TRUE (r0
.maybe_isnan ());
3860 range_tests_signed_zeros ()
3862 tree zero
= build_zero_cst (float_type_node
);
3863 tree neg_zero
= fold_build1 (NEGATE_EXPR
, float_type_node
, zero
);
3867 // [0,0] contains [0,0] but not [-0,-0] and vice versa.
3868 r0
= frange (zero
, zero
);
3869 r1
= frange (neg_zero
, neg_zero
);
3870 ASSERT_TRUE (r0
.contains_p (zero
));
3871 ASSERT_TRUE (!r0
.contains_p (neg_zero
));
3872 ASSERT_TRUE (r1
.contains_p (neg_zero
));
3873 ASSERT_TRUE (!r1
.contains_p (zero
));
3875 // Test contains_p() when we know the sign of the zero.
3876 r0
= frange (zero
, zero
);
3877 ASSERT_TRUE (r0
.contains_p (zero
));
3878 ASSERT_FALSE (r0
.contains_p (neg_zero
));
3879 r0
= frange (neg_zero
, neg_zero
);
3880 ASSERT_TRUE (r0
.contains_p (neg_zero
));
3881 ASSERT_FALSE (r0
.contains_p (zero
));
3883 r0
= frange (neg_zero
, zero
);
3884 ASSERT_TRUE (r0
.contains_p (neg_zero
));
3885 ASSERT_TRUE (r0
.contains_p (zero
));
3887 r0
= frange_float ("-3", "5");
3888 ASSERT_TRUE (r0
.contains_p (neg_zero
));
3889 ASSERT_TRUE (r0
.contains_p (zero
));
3891 // The intersection of zeros that differ in sign is a NAN (or
3892 // undefined if not honoring NANs).
3893 r0
= frange (neg_zero
, neg_zero
);
3894 r1
= frange (zero
, zero
);
3896 if (HONOR_NANS (float_type_node
))
3897 ASSERT_TRUE (r0
.known_isnan ());
3899 ASSERT_TRUE (r0
.undefined_p ());
3901 // The union of zeros that differ in sign is a zero with unknown sign.
3902 r0
= frange (zero
, zero
);
3903 r1
= frange (neg_zero
, neg_zero
);
3905 ASSERT_TRUE (r0
.zero_p () && !r0
.signbit_p (signbit
));
3907 // [-0, +0] has an unknown sign.
3908 r0
= frange (neg_zero
, zero
);
3909 ASSERT_TRUE (r0
.zero_p () && !r0
.signbit_p (signbit
));
3911 // [-0, +0] ^ [0, 0] is [0, 0]
3912 r0
= frange (neg_zero
, zero
);
3913 r1
= frange (zero
, zero
);
3915 ASSERT_TRUE (r0
.zero_p ());
3917 r0
= frange_float ("+0", "5");
3919 ASSERT_TRUE (r0
.signbit_p (signbit
) && !signbit
);
3921 r0
= frange_float ("-0", "5");
3923 ASSERT_TRUE (!r0
.signbit_p (signbit
));
3925 r0
= frange_float ("-0", "10");
3926 r1
= frange_float ("0", "5");
3928 ASSERT_TRUE (real_iszero (&r0
.lower_bound (), false));
3930 r0
= frange_float ("-0", "5");
3931 r1
= frange_float ("0", "5");
3933 ASSERT_TRUE (real_iszero (&r0
.lower_bound (), true));
3935 r0
= frange_float ("-5", "-0");
3937 r1
= frange_float ("0", "0");
3940 if (HONOR_NANS (float_type_node
))
3941 ASSERT_TRUE (r0
.known_isnan ());
3943 ASSERT_TRUE (r0
.undefined_p ());
3945 r0
.set_nonnegative (float_type_node
);
3946 if (HONOR_NANS (float_type_node
))
3947 ASSERT_TRUE (r0
.maybe_isnan ());
3949 // Numbers containing zero should have an unknown SIGNBIT.
3950 r0
= frange_float ("0", "10");
3952 ASSERT_TRUE (r0
.signbit_p (signbit
) && !signbit
);
3956 range_tests_signbit ()
3961 // Negative numbers should have the SIGNBIT set.
3962 r0
= frange_float ("-5", "-1");
3964 ASSERT_TRUE (r0
.signbit_p (signbit
) && signbit
);
3965 // Positive numbers should have the SIGNBIT clear.
3966 r0
= frange_float ("1", "10");
3968 ASSERT_TRUE (r0
.signbit_p (signbit
) && !signbit
);
3969 // Numbers spanning both positive and negative should have an
3971 r0
= frange_float ("-10", "10");
3973 ASSERT_TRUE (!r0
.signbit_p (signbit
));
3974 r0
.set_varying (float_type_node
);
3975 ASSERT_TRUE (!r0
.signbit_p (signbit
));
3979 range_tests_floats ()
3983 if (HONOR_NANS (float_type_node
))
3985 range_tests_signbit ();
3987 if (HONOR_SIGNED_ZEROS (float_type_node
))
3988 range_tests_signed_zeros ();
3990 // A range of [-INF,+INF] is actually VARYING if no other properties
3992 r0
= frange_float ("-Inf", "+Inf");
3993 ASSERT_TRUE (r0
.varying_p ());
3994 // ...unless it has some special property...
3995 if (HONOR_NANS (r0
.type ()))
3998 ASSERT_FALSE (r0
.varying_p ());
4001 // For most architectures, where float and double are different
4002 // sizes, having the same endpoints does not necessarily mean the
4003 // ranges are equal.
4004 if (!types_compatible_p (float_type_node
, double_type_node
))
4006 r0
= frange_float ("3.0", "3.0", float_type_node
);
4007 r1
= frange_float ("3.0", "3.0", double_type_node
);
4011 // [3,5] U [10,12] = [3,12].
4012 r0
= frange_float ("3", "5");
4013 r1
= frange_float ("10", "12");
4015 ASSERT_EQ (r0
, frange_float ("3", "12"));
4017 // [5,10] U [4,8] = [4,10]
4018 r0
= frange_float ("5", "10");
4019 r1
= frange_float ("4", "8");
4021 ASSERT_EQ (r0
, frange_float ("4", "10"));
4023 // [3,5] U [4,10] = [3,10]
4024 r0
= frange_float ("3", "5");
4025 r1
= frange_float ("4", "10");
4027 ASSERT_EQ (r0
, frange_float ("3", "10"));
4029 // [4,10] U [5,11] = [4,11]
4030 r0
= frange_float ("4", "10");
4031 r1
= frange_float ("5", "11");
4033 ASSERT_EQ (r0
, frange_float ("4", "11"));
4035 // [3,12] ^ [10,12] = [10,12].
4036 r0
= frange_float ("3", "12");
4037 r1
= frange_float ("10", "12");
4039 ASSERT_EQ (r0
, frange_float ("10", "12"));
4041 // [10,12] ^ [11,11] = [11,11]
4042 r0
= frange_float ("10", "12");
4043 r1
= frange_float ("11", "11");
4045 ASSERT_EQ (r0
, frange_float ("11", "11"));
4047 // [10,20] ^ [5,15] = [10,15]
4048 r0
= frange_float ("10", "20");
4049 r1
= frange_float ("5", "15");
4051 ASSERT_EQ (r0
, frange_float ("10", "15"));
4053 // [10,20] ^ [15,25] = [15,20]
4054 r0
= frange_float ("10", "20");
4055 r1
= frange_float ("15", "25");
4057 ASSERT_EQ (r0
, frange_float ("15", "20"));
4059 // [10,20] ^ [21,25] = []
4060 r0
= frange_float ("10", "20");
4062 r1
= frange_float ("21", "25");
4065 ASSERT_TRUE (r0
.undefined_p ());
4067 if (HONOR_INFINITIES (float_type_node
))
4069 // Make sure [-Inf, -Inf] doesn't get normalized.
4070 r0
= frange_float ("-Inf", "-Inf");
4071 ASSERT_TRUE (real_isinf (&r0
.lower_bound (), true));
4072 ASSERT_TRUE (real_isinf (&r0
.upper_bound (), true));
4075 // Test that reading back a global range yields the same result as
4076 // what we wrote into it.
4077 tree ssa
= make_temp_ssa_name (float_type_node
, NULL
, "blah");
4078 r0
.set_varying (float_type_node
);
4080 set_range_info (ssa
, r0
);
4081 get_global_range_query ()->range_of_expr (r1
, ssa
);
4085 // Run floating range tests for various combinations of NAN and INF
4089 range_tests_floats_various ()
4091 int save_finite_math_only
= flag_finite_math_only
;
4093 // Test -ffinite-math-only.
4094 flag_finite_math_only
= 1;
4095 range_tests_floats ();
4096 // Test -fno-finite-math-only.
4097 flag_finite_math_only
= 0;
4098 range_tests_floats ();
4100 flag_finite_math_only
= save_finite_math_only
;
4106 range_tests_legacy ();
4107 range_tests_irange3 ();
4108 range_tests_int_range_max ();
4109 range_tests_strict_enum ();
4110 range_tests_nonzero_bits ();
4111 range_tests_floats_various ();
4112 range_tests_misc ();
4115 } // namespace selftest
4117 #endif // CHECKING_P