]>
gcc.gnu.org Git - gcc.git/blob - gcc/value-range.cc
1 /* Support routines for value ranges.
2 Copyright (C) 2019-2022 Free Software Foundation, Inc.
3 Major hacks by Aldy Hernandez <aldyh@redhat.com> and
4 Andrew MacLeod <amacleod@redhat.com>.
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify
9 it under the terms of the GNU General Public License as published by
10 the Free Software Foundation; either version 3, or (at your option)
13 GCC is distributed in the hope that it will be useful,
14 but WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 GNU General Public License for more details.
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
24 #include "coretypes.h"
29 #include "tree-pretty-print.h"
30 #include "value-range-pretty-print.h"
31 #include "fold-const.h"
32 #include "gimple-range.h"
35 irange::accept (const vrange_visitor
&v
) const
41 unsupported_range::accept (const vrange_visitor
&v
) const
46 // Convenience function only available for integers and pointers.
49 Value_Range::lower_bound () const
51 if (is_a
<irange
> (*m_vrange
))
52 return as_a
<irange
> (*m_vrange
).lower_bound ();
56 // Convenience function only available for integers and pointers.
59 Value_Range::upper_bound () const
61 if (is_a
<irange
> (*m_vrange
))
62 return as_a
<irange
> (*m_vrange
).upper_bound ();
67 Value_Range::dump (FILE *out
) const
72 fprintf (out
, "NULL");
76 debug (const Value_Range
&r
)
79 fprintf (stderr
, "\n");
82 // Default vrange definitions.
85 vrange::contains_p (tree
) const
91 vrange::singleton_p (tree
*) const
97 vrange::set (tree
, tree
, value_range_kind
)
102 vrange::type () const
104 return void_type_node
;
108 vrange::supports_type_p (const_tree
) const
114 vrange::set_undefined ()
116 m_kind
= VR_UNDEFINED
;
120 vrange::set_varying (tree
)
126 vrange::union_ (const vrange
&r
)
128 if (r
.undefined_p () || varying_p ())
130 if (undefined_p () || r
.varying_p ())
140 vrange::intersect (const vrange
&r
)
142 if (undefined_p () || r
.varying_p ())
144 if (r
.undefined_p ())
159 vrange::zero_p () const
165 vrange::nonzero_p () const
171 vrange::set_nonzero (tree
)
176 vrange::set_zero (tree
)
181 vrange::set_nonnegative (tree
)
186 vrange::fits_p (const vrange
&) const
191 // Assignment operator for generic ranges. Copying incompatible types
195 vrange::operator= (const vrange
&src
)
197 if (is_a
<irange
> (src
))
198 as_a
<irange
> (*this) = as_a
<irange
> (src
);
199 else if (is_a
<frange
> (src
))
200 as_a
<frange
> (*this) = as_a
<frange
> (src
);
206 // Equality operator for generic ranges.
209 vrange::operator== (const vrange
&src
) const
211 if (is_a
<irange
> (src
))
212 return as_a
<irange
> (*this) == as_a
<irange
> (src
);
213 if (is_a
<frange
> (src
))
214 return as_a
<frange
> (*this) == as_a
<frange
> (src
);
218 // Wrapper for vrange_printer to dump a range to a file.
221 vrange::dump (FILE *file
) const
223 pretty_printer buffer
;
224 pp_needs_newline (&buffer
) = true;
225 buffer
.buffer
->stream
= file
;
226 vrange_printer
vrange_pp (&buffer
);
227 this->accept (vrange_pp
);
232 irange::supports_type_p (const_tree type
) const
234 return supports_p (type
);
237 // Return TRUE if R fits in THIS.
240 irange::fits_p (const vrange
&r
) const
242 return m_max_ranges
>= as_a
<irange
> (r
).num_pairs ();
246 irange::set_nonnegative (tree type
)
248 set (build_int_cst (type
, 0), TYPE_MAX_VALUE (type
));
251 unsupported_range::unsupported_range ()
253 m_discriminator
= VR_UNKNOWN
;
258 frange::accept (const vrange_visitor
&v
) const
263 // Setter for franges. Currently only singletons are supported.
266 frange::set (tree min
, tree max
, value_range_kind kind
)
268 gcc_checking_assert (kind
== VR_RANGE
);
269 gcc_checking_assert (operand_equal_p (min
, max
));
270 gcc_checking_assert (TREE_CODE (min
) == REAL_CST
);
273 m_type
= TREE_TYPE (min
);
275 REAL_VALUE_TYPE
*const cst
= TREE_REAL_CST_PTR (min
);
276 if (real_isnan (cst
))
277 m_props
.nan_set_yes ();
279 m_props
.nan_set_no ();
281 if (real_isinf (cst
))
283 if (real_isneg (cst
))
285 m_props
.inf_set_no ();
286 m_props
.ninf_set_yes ();
290 m_props
.inf_set_yes ();
291 m_props
.ninf_set_no ();
296 m_props
.inf_set_no ();
297 m_props
.ninf_set_no ();
304 // Normalize range to VARYING or UNDEFINED, or vice versa.
306 // A range with no known properties can be dropped to VARYING.
307 // Similarly, a VARYING with any properties should be dropped to a
308 // VR_RANGE. Normalizing ranges upon changing them ensures there is
309 // only one representation for a given range.
312 frange::normalize_kind ()
314 if (m_kind
== VR_RANGE
)
316 // No FP properties set means varying.
317 if (m_props
.nan_varying_p ()
318 && m_props
.inf_varying_p ()
319 && m_props
.ninf_varying_p ())
321 set_varying (m_type
);
324 // Undefined is viral.
325 if (m_props
.nan_undefined_p ()
326 || m_props
.inf_undefined_p ()
327 || m_props
.ninf_undefined_p ())
333 else if (m_kind
== VR_VARYING
)
335 // If a VARYING has any FP properties, it's no longer VARYING.
336 if (!m_props
.nan_varying_p ()
337 || !m_props
.inf_varying_p ()
338 || !m_props
.ninf_varying_p ())
344 frange::union_ (const vrange
&v
)
346 const frange
&r
= as_a
<frange
> (v
);
348 if (r
.undefined_p () || varying_p ())
350 if (undefined_p () || r
.varying_p ())
356 bool ret
= m_props
.union_ (r
.m_props
);
365 frange::intersect (const vrange
&v
)
367 const frange
&r
= as_a
<frange
> (v
);
369 if (undefined_p () || r
.varying_p ())
371 if (r
.undefined_p ())
382 bool ret
= m_props
.intersect (r
.m_props
);
391 frange::operator= (const frange
&src
)
395 m_props
= src
.m_props
;
403 frange::operator== (const frange
&src
) const
405 if (m_kind
== src
.m_kind
)
411 return types_compatible_p (m_type
, src
.m_type
);
413 return m_props
== src
.m_props
;
419 frange::supports_type_p (const_tree type
) const
421 return supports_p (type
);
425 frange::verify_range ()
429 gcc_checking_assert (m_props
.undefined_p ());
432 else if (varying_p ())
434 gcc_checking_assert (m_props
.varying_p ());
438 gcc_checking_assert (m_kind
== VR_RANGE
);
439 gcc_checking_assert (!m_props
.varying_p () && !m_props
.undefined_p ());
442 // Here we copy between any two irange's. The ranges can be legacy or
443 // multi-ranges, and copying between any combination works correctly.
446 irange::operator= (const irange
&src
)
448 if (legacy_mode_p ())
450 copy_to_legacy (src
);
453 if (src
.legacy_mode_p ())
455 copy_legacy_to_multi_range (src
);
460 unsigned lim
= src
.m_num_ranges
;
461 if (lim
> m_max_ranges
)
464 for (x
= 0; x
< lim
* 2; ++x
)
465 m_base
[x
] = src
.m_base
[x
];
467 // If the range didn't fit, the last range should cover the rest.
468 if (lim
!= src
.m_num_ranges
)
469 m_base
[x
- 1] = src
.m_base
[src
.m_num_ranges
* 2 - 1];
473 m_nonzero_mask
= src
.m_nonzero_mask
;
479 // Return TRUE if range is a multi-range that can be represented as a
483 irange::maybe_anti_range () const
485 tree ttype
= type ();
486 unsigned int precision
= TYPE_PRECISION (ttype
);
487 signop sign
= TYPE_SIGN (ttype
);
488 return (num_pairs () > 1
490 && lower_bound () == wi::min_value (precision
, sign
)
491 && upper_bound () == wi::max_value (precision
, sign
));
495 irange::copy_legacy_to_multi_range (const irange
&src
)
497 gcc_checking_assert (src
.legacy_mode_p ());
498 gcc_checking_assert (!legacy_mode_p ());
499 if (src
.undefined_p ())
501 else if (src
.varying_p ())
502 set_varying (src
.type ());
505 if (range_has_numeric_bounds_p (&src
))
506 set (src
.min (), src
.max (), src
.kind ());
509 value_range
cst (src
);
510 cst
.normalize_symbolics ();
511 gcc_checking_assert (cst
.varying_p () || cst
.kind () == VR_RANGE
);
512 set (cst
.min (), cst
.max ());
517 // Copy any type of irange into a legacy.
520 irange::copy_to_legacy (const irange
&src
)
522 gcc_checking_assert (legacy_mode_p ());
523 // Handle legacy to legacy and other things that are easy to copy.
524 if (src
.legacy_mode_p () || src
.varying_p () || src
.undefined_p ())
526 m_num_ranges
= src
.m_num_ranges
;
527 m_base
[0] = src
.m_base
[0];
528 m_base
[1] = src
.m_base
[1];
530 m_nonzero_mask
= src
.m_nonzero_mask
;
533 // Copy multi-range to legacy.
534 if (src
.maybe_anti_range ())
536 int_range
<3> r (src
);
538 // Use tree variants to save on tree -> wi -> tree conversions.
539 set (r
.tree_lower_bound (0), r
.tree_upper_bound (0), VR_ANTI_RANGE
);
542 set (src
.tree_lower_bound (), src
.tree_upper_bound ());
545 // Swap MIN/MAX if they are out of order and adjust KIND appropriately.
548 swap_out_of_order_endpoints (tree
&min
, tree
&max
, value_range_kind
&kind
)
550 gcc_checking_assert (kind
!= VR_UNDEFINED
);
551 if (kind
== VR_VARYING
)
553 /* Wrong order for min and max, to swap them and the VR type we need
555 if (tree_int_cst_lt (max
, min
))
559 /* For one bit precision if max < min, then the swapped
560 range covers all values, so for VR_RANGE it is varying and
561 for VR_ANTI_RANGE empty range, so drop to varying as well. */
562 if (TYPE_PRECISION (TREE_TYPE (min
)) == 1)
568 one
= build_int_cst (TREE_TYPE (min
), 1);
569 tmp
= int_const_binop (PLUS_EXPR
, max
, one
);
570 max
= int_const_binop (MINUS_EXPR
, min
, one
);
573 /* There's one corner case, if we had [C+1, C] before we now have
574 that again. But this represents an empty value range, so drop
575 to varying in this case. */
576 if (tree_int_cst_lt (max
, min
))
581 kind
= kind
== VR_RANGE
? VR_ANTI_RANGE
: VR_RANGE
;
586 irange::irange_set (tree min
, tree max
)
588 gcc_checking_assert (!POLY_INT_CST_P (min
));
589 gcc_checking_assert (!POLY_INT_CST_P (max
));
595 m_nonzero_mask
= NULL
;
603 irange::irange_set_1bit_anti_range (tree min
, tree max
)
605 tree type
= TREE_TYPE (min
);
606 gcc_checking_assert (TYPE_PRECISION (type
) == 1);
608 if (operand_equal_p (min
, max
))
610 // Since these are 1-bit quantities, they can only be [MIN,MIN]
612 if (vrp_val_is_min (min
))
613 min
= max
= vrp_val_max (type
);
615 min
= max
= vrp_val_min (type
);
620 // The only alternative is [MIN,MAX], which is the empty range.
621 gcc_checking_assert (vrp_val_is_min (min
));
622 gcc_checking_assert (vrp_val_is_max (max
));
630 irange::irange_set_anti_range (tree min
, tree max
)
632 gcc_checking_assert (!POLY_INT_CST_P (min
));
633 gcc_checking_assert (!POLY_INT_CST_P (max
));
635 if (TYPE_PRECISION (TREE_TYPE (min
)) == 1)
637 irange_set_1bit_anti_range (min
, max
);
642 tree type
= TREE_TYPE (min
);
643 signop sign
= TYPE_SIGN (type
);
644 int_range
<2> type_range (type
);
645 // Calculate INVERSE([I,J]) as [-MIN, I-1][J+1, +MAX].
647 wi::overflow_type ovf
;
649 wide_int w_min
= wi::to_wide (min
);
650 if (wi::ne_p (w_min
, type_range
.lower_bound ()))
652 wide_int lim1
= wi::sub (w_min
, 1, sign
, &ovf
);
653 gcc_checking_assert (ovf
!= wi::OVF_OVERFLOW
);
654 m_base
[0] = type_range
.tree_lower_bound (0);
655 m_base
[1] = wide_int_to_tree (type
, lim1
);
658 wide_int w_max
= wi::to_wide (max
);
659 if (wi::ne_p (w_max
, type_range
.upper_bound ()))
661 wide_int lim2
= wi::add (w_max
, 1, sign
, &ovf
);
662 gcc_checking_assert (ovf
!= wi::OVF_OVERFLOW
);
663 m_base
[m_num_ranges
* 2] = wide_int_to_tree (type
, lim2
);
664 m_base
[m_num_ranges
* 2 + 1] = type_range
.tree_upper_bound (0);
669 m_nonzero_mask
= NULL
;
676 /* Set value range to the canonical form of {VRTYPE, MIN, MAX, EQUIV}.
677 This means adjusting VRTYPE, MIN and MAX representing the case of a
678 wrapping range with MAX < MIN covering [MIN, type_max] U [type_min, MAX]
679 as anti-rage ~[MAX+1, MIN-1]. Likewise for wrapping anti-ranges.
680 In corner cases where MAX+1 or MIN-1 wraps this will fall back
682 This routine exists to ease canonicalization in the case where we
683 extract ranges from var + CST op limit. */
686 irange::set (tree min
, tree max
, value_range_kind kind
)
688 if (kind
!= VR_UNDEFINED
)
690 if (TREE_OVERFLOW_P (min
))
691 min
= drop_tree_overflow (min
);
692 if (TREE_OVERFLOW_P (max
))
693 max
= drop_tree_overflow (max
);
696 if (!legacy_mode_p ())
698 if (kind
== VR_RANGE
)
699 irange_set (min
, max
);
702 gcc_checking_assert (kind
== VR_ANTI_RANGE
);
703 irange_set_anti_range (min
, max
);
707 if (kind
== VR_UNDEFINED
)
709 irange::set_undefined ();
713 if (kind
== VR_VARYING
714 || POLY_INT_CST_P (min
)
715 || POLY_INT_CST_P (max
))
717 set_varying (TREE_TYPE (min
));
721 // Nothing to canonicalize for symbolic ranges.
722 if (TREE_CODE (min
) != INTEGER_CST
723 || TREE_CODE (max
) != INTEGER_CST
)
729 m_nonzero_mask
= NULL
;
733 swap_out_of_order_endpoints (min
, max
, kind
);
734 if (kind
== VR_VARYING
)
736 set_varying (TREE_TYPE (min
));
740 // Anti-ranges that can be represented as ranges should be so.
741 if (kind
== VR_ANTI_RANGE
)
743 bool is_min
= vrp_val_is_min (min
);
744 bool is_max
= vrp_val_is_max (max
);
746 if (is_min
&& is_max
)
748 // Fall through. This will either be normalized as
749 // VR_UNDEFINED if the anti-range spans the entire
750 // precision, or it will remain an VR_ANTI_RANGE in the case
751 // of an -fstrict-enum where [MIN,MAX] is less than the span
752 // of underlying precision.
754 else if (TYPE_PRECISION (TREE_TYPE (min
)) == 1)
756 irange_set_1bit_anti_range (min
, max
);
761 tree one
= build_int_cst (TREE_TYPE (max
), 1);
762 min
= int_const_binop (PLUS_EXPR
, max
, one
);
763 max
= vrp_val_max (TREE_TYPE (max
));
768 tree one
= build_int_cst (TREE_TYPE (min
), 1);
769 max
= int_const_binop (MINUS_EXPR
, min
, one
);
770 min
= vrp_val_min (TREE_TYPE (min
));
779 m_nonzero_mask
= NULL
;
785 // Check the validity of the range.
788 irange::verify_range ()
790 gcc_checking_assert (m_discriminator
== VR_IRANGE
);
791 if (m_kind
== VR_UNDEFINED
)
793 gcc_checking_assert (m_num_ranges
== 0);
794 gcc_checking_assert (!m_nonzero_mask
);
798 gcc_checking_assert (wi::to_wide (m_nonzero_mask
) != -1);
799 if (m_kind
== VR_VARYING
)
801 gcc_checking_assert (!m_nonzero_mask
);
802 gcc_checking_assert (m_num_ranges
== 1);
803 gcc_checking_assert (varying_compatible_p ());
806 if (!legacy_mode_p ())
808 gcc_checking_assert (m_num_ranges
!= 0);
809 gcc_checking_assert (!varying_compatible_p ());
810 for (unsigned i
= 0; i
< m_num_ranges
; ++i
)
812 tree lb
= tree_lower_bound (i
);
813 tree ub
= tree_upper_bound (i
);
814 int c
= compare_values (lb
, ub
);
815 gcc_checking_assert (c
== 0 || c
== -1);
819 if (m_kind
== VR_RANGE
|| m_kind
== VR_ANTI_RANGE
)
821 gcc_checking_assert (m_num_ranges
== 1);
822 int cmp
= compare_values (tree_lower_bound (0), tree_upper_bound (0));
823 gcc_checking_assert (cmp
== 0 || cmp
== -1 || cmp
== -2);
827 // Return the lower bound for a sub-range. PAIR is the sub-range in
831 irange::legacy_lower_bound (unsigned pair
) const
833 gcc_checking_assert (legacy_mode_p ());
836 value_range
numeric_range (*this);
837 numeric_range
.normalize_symbolics ();
838 return numeric_range
.legacy_lower_bound (pair
);
840 gcc_checking_assert (m_num_ranges
> 0);
841 gcc_checking_assert (pair
+ 1 <= num_pairs ());
842 if (m_kind
== VR_ANTI_RANGE
)
844 tree typ
= type (), t
;
845 if (pair
== 1 || vrp_val_is_min (min ()))
846 t
= wide_int_to_tree (typ
, wi::to_wide (max ()) + 1);
848 t
= vrp_val_min (typ
);
849 return wi::to_wide (t
);
851 return wi::to_wide (tree_lower_bound (pair
));
854 // Return the upper bound for a sub-range. PAIR is the sub-range in
858 irange::legacy_upper_bound (unsigned pair
) const
860 gcc_checking_assert (legacy_mode_p ());
863 value_range
numeric_range (*this);
864 numeric_range
.normalize_symbolics ();
865 return numeric_range
.legacy_upper_bound (pair
);
867 gcc_checking_assert (m_num_ranges
> 0);
868 gcc_checking_assert (pair
+ 1 <= num_pairs ());
869 if (m_kind
== VR_ANTI_RANGE
)
871 tree typ
= type (), t
;
872 if (pair
== 1 || vrp_val_is_min (min ()))
873 t
= vrp_val_max (typ
);
875 t
= wide_int_to_tree (typ
, wi::to_wide (min ()) - 1);
876 return wi::to_wide (t
);
878 return wi::to_wide (tree_upper_bound (pair
));
882 irange::legacy_equal_p (const irange
&other
) const
884 gcc_checking_assert (legacy_mode_p () && other
.legacy_mode_p ());
886 if (m_kind
!= other
.m_kind
)
888 if (m_kind
== VR_UNDEFINED
)
890 if (m_kind
== VR_VARYING
)
892 return (range_compatible_p (type (), other
.type ())
893 && vrp_operand_equal_p (m_nonzero_mask
, other
.m_nonzero_mask
));
895 return (vrp_operand_equal_p (tree_lower_bound (0),
896 other
.tree_lower_bound (0))
897 && vrp_operand_equal_p (tree_upper_bound (0),
898 other
.tree_upper_bound (0))
899 && vrp_operand_equal_p (m_nonzero_mask
, other
.m_nonzero_mask
));
903 irange::operator== (const irange
&other
) const
905 if (legacy_mode_p ())
907 if (other
.legacy_mode_p ())
908 return legacy_equal_p (other
);
909 value_range
tmp (other
);
910 return legacy_equal_p (tmp
);
912 if (other
.legacy_mode_p ())
914 value_range
tmp2 (*this);
915 return tmp2
.legacy_equal_p (other
);
918 if (m_num_ranges
!= other
.m_num_ranges
)
921 for (unsigned i
= 0; i
< m_num_ranges
; ++i
)
923 tree lb
= tree_lower_bound (i
);
924 tree ub
= tree_upper_bound (i
);
925 tree lb_other
= other
.tree_lower_bound (i
);
926 tree ub_other
= other
.tree_upper_bound (i
);
927 if (!operand_equal_p (lb
, lb_other
, 0)
928 || !operand_equal_p (ub
, ub_other
, 0))
931 return vrp_operand_equal_p (m_nonzero_mask
, other
.m_nonzero_mask
);
934 /* Return TRUE if this is a symbolic range. */
937 irange::symbolic_p () const
939 return (m_num_ranges
> 0
940 && (!is_gimple_min_invariant (min ())
941 || !is_gimple_min_invariant (max ())));
944 /* Return TRUE if this is a constant range. */
947 irange::constant_p () const
949 return (m_num_ranges
> 0
950 && TREE_CODE (min ()) == INTEGER_CST
951 && TREE_CODE (max ()) == INTEGER_CST
);
954 /* If range is a singleton, place it in RESULT and return TRUE.
955 Note: A singleton can be any gimple invariant, not just constants.
956 So, [&x, &x] counts as a singleton. */
959 irange::singleton_p (tree
*result
) const
961 if (!legacy_mode_p ())
963 if (num_pairs () == 1 && (wi::to_wide (tree_lower_bound ())
964 == wi::to_wide (tree_upper_bound ())))
967 *result
= tree_lower_bound ();
972 if (m_kind
== VR_ANTI_RANGE
)
976 if (TYPE_PRECISION (type ()) == 1)
984 if (num_pairs () == 1)
986 value_range vr0
, vr1
;
987 ranges_from_anti_range ((const value_range
*) this, &vr0
, &vr1
);
988 return vr0
.singleton_p (result
);
991 // Catches non-numeric extremes as well.
992 if (m_kind
== VR_RANGE
993 && vrp_operand_equal_p (min (), max ())
994 && is_gimple_min_invariant (min ()))
1003 /* Return 1 if VAL is inside value range.
1004 0 if VAL is not inside value range.
1005 -2 if we cannot tell either way.
1007 Benchmark compile/20001226-1.c compilation time after changing this
1011 irange::value_inside_range (tree val
) const
1019 if (!legacy_mode_p () && TREE_CODE (val
) == INTEGER_CST
)
1020 return contains_p (val
);
1022 int cmp1
= operand_less_p (val
, min ());
1026 return m_kind
!= VR_RANGE
;
1028 int cmp2
= operand_less_p (max (), val
);
1032 if (m_kind
== VR_RANGE
)
1038 /* Return TRUE if it is possible that range contains VAL. */
1041 irange::may_contain_p (tree val
) const
1043 return value_inside_range (val
) != 0;
1046 /* Return TRUE if range contains INTEGER_CST. */
1047 /* Return 1 if VAL is inside value range.
1048 0 if VAL is not inside value range.
1050 Benchmark compile/20001226-1.c compilation time after changing this
1055 irange::contains_p (tree cst
) const
1060 if (legacy_mode_p ())
1062 gcc_checking_assert (TREE_CODE (cst
) == INTEGER_CST
);
1065 value_range
numeric_range (*this);
1066 numeric_range
.normalize_symbolics ();
1067 return numeric_range
.contains_p (cst
);
1069 return value_inside_range (cst
) == 1;
1072 gcc_checking_assert (TREE_CODE (cst
) == INTEGER_CST
);
1076 wide_int cstw
= wi::to_wide (cst
);
1077 if (cstw
!= 0 && wi::bit_and (wi::to_wide (m_nonzero_mask
), cstw
) == 0)
1081 signop sign
= TYPE_SIGN (TREE_TYPE (cst
));
1082 wide_int v
= wi::to_wide (cst
);
1083 for (unsigned r
= 0; r
< m_num_ranges
; ++r
)
1085 if (wi::lt_p (v
, lower_bound (r
), sign
))
1087 if (wi::le_p (v
, upper_bound (r
), sign
))
1095 /* Normalize addresses into constants. */
1098 irange::normalize_addresses ()
1103 if (!POINTER_TYPE_P (type ()) || range_has_numeric_bounds_p (this))
1106 if (!range_includes_zero_p (this))
1108 gcc_checking_assert (TREE_CODE (min ()) == ADDR_EXPR
1109 || TREE_CODE (max ()) == ADDR_EXPR
);
1110 set_nonzero (type ());
1113 set_varying (type ());
1116 /* Normalize symbolics and addresses into constants. */
1119 irange::normalize_symbolics ()
1121 if (varying_p () || undefined_p ())
1124 tree ttype
= type ();
1125 bool min_symbolic
= !is_gimple_min_invariant (min ());
1126 bool max_symbolic
= !is_gimple_min_invariant (max ());
1127 if (!min_symbolic
&& !max_symbolic
)
1129 normalize_addresses ();
1133 // [SYM, SYM] -> VARYING
1134 if (min_symbolic
&& max_symbolic
)
1136 set_varying (ttype
);
1139 if (kind () == VR_RANGE
)
1141 // [SYM, NUM] -> [-MIN, NUM]
1144 set (vrp_val_min (ttype
), max ());
1147 // [NUM, SYM] -> [NUM, +MAX]
1148 set (min (), vrp_val_max (ttype
));
1151 gcc_checking_assert (kind () == VR_ANTI_RANGE
);
1152 // ~[SYM, NUM] -> [NUM + 1, +MAX]
1155 if (!vrp_val_is_max (max ()))
1157 tree n
= wide_int_to_tree (ttype
, wi::to_wide (max ()) + 1);
1158 set (n
, vrp_val_max (ttype
));
1161 set_varying (ttype
);
1164 // ~[NUM, SYM] -> [-MIN, NUM - 1]
1165 if (!vrp_val_is_min (min ()))
1167 tree n
= wide_int_to_tree (ttype
, wi::to_wide (min ()) - 1);
1168 set (vrp_val_min (ttype
), n
);
1171 set_varying (ttype
);
1174 /* Intersect the two value-ranges { *VR0TYPE, *VR0MIN, *VR0MAX } and
1175 { VR1TYPE, VR0MIN, VR0MAX } and store the result
1176 in { *VR0TYPE, *VR0MIN, *VR0MAX }. This may not be the smallest
1177 possible such range. The resulting range is not canonicalized. */
1180 intersect_ranges (enum value_range_kind
*vr0type
,
1181 tree
*vr0min
, tree
*vr0max
,
1182 enum value_range_kind vr1type
,
1183 tree vr1min
, tree vr1max
)
1185 bool mineq
= vrp_operand_equal_p (*vr0min
, vr1min
);
1186 bool maxeq
= vrp_operand_equal_p (*vr0max
, vr1max
);
1188 /* [] is vr0, () is vr1 in the following classification comments. */
1192 if (*vr0type
== vr1type
)
1193 /* Nothing to do for equal ranges. */
1195 else if ((*vr0type
== VR_RANGE
1196 && vr1type
== VR_ANTI_RANGE
)
1197 || (*vr0type
== VR_ANTI_RANGE
1198 && vr1type
== VR_RANGE
))
1200 /* For anti-range with range intersection the result is empty. */
1201 *vr0type
= VR_UNDEFINED
;
1202 *vr0min
= NULL_TREE
;
1203 *vr0max
= NULL_TREE
;
1208 else if (operand_less_p (*vr0max
, vr1min
) == 1
1209 || operand_less_p (vr1max
, *vr0min
) == 1)
1211 /* [ ] ( ) or ( ) [ ]
1212 If the ranges have an empty intersection, the result of the
1213 intersect operation is the range for intersecting an
1214 anti-range with a range or empty when intersecting two ranges. */
1215 if (*vr0type
== VR_RANGE
1216 && vr1type
== VR_ANTI_RANGE
)
1218 else if (*vr0type
== VR_ANTI_RANGE
1219 && vr1type
== VR_RANGE
)
1225 else if (*vr0type
== VR_RANGE
1226 && vr1type
== VR_RANGE
)
1228 *vr0type
= VR_UNDEFINED
;
1229 *vr0min
= NULL_TREE
;
1230 *vr0max
= NULL_TREE
;
1232 else if (*vr0type
== VR_ANTI_RANGE
1233 && vr1type
== VR_ANTI_RANGE
)
1235 /* If the anti-ranges are adjacent to each other merge them. */
1236 if (TREE_CODE (*vr0max
) == INTEGER_CST
1237 && TREE_CODE (vr1min
) == INTEGER_CST
1238 && operand_less_p (*vr0max
, vr1min
) == 1
1239 && integer_onep (int_const_binop (MINUS_EXPR
,
1242 else if (TREE_CODE (vr1max
) == INTEGER_CST
1243 && TREE_CODE (*vr0min
) == INTEGER_CST
1244 && operand_less_p (vr1max
, *vr0min
) == 1
1245 && integer_onep (int_const_binop (MINUS_EXPR
,
1248 /* Else arbitrarily take VR0. */
1251 else if ((maxeq
|| operand_less_p (vr1max
, *vr0max
) == 1)
1252 && (mineq
|| operand_less_p (*vr0min
, vr1min
) == 1))
1254 /* [ ( ) ] or [( ) ] or [ ( )] */
1255 if (*vr0type
== VR_RANGE
1256 && vr1type
== VR_RANGE
)
1258 /* If both are ranges the result is the inner one. */
1263 else if (*vr0type
== VR_RANGE
1264 && vr1type
== VR_ANTI_RANGE
)
1266 /* Choose the right gap if the left one is empty. */
1269 if (TREE_CODE (vr1max
) != INTEGER_CST
)
1271 else if (TYPE_PRECISION (TREE_TYPE (vr1max
)) == 1
1272 && !TYPE_UNSIGNED (TREE_TYPE (vr1max
)))
1274 = int_const_binop (MINUS_EXPR
, vr1max
,
1275 build_int_cst (TREE_TYPE (vr1max
), -1));
1278 = int_const_binop (PLUS_EXPR
, vr1max
,
1279 build_int_cst (TREE_TYPE (vr1max
), 1));
1281 /* Choose the left gap if the right one is empty. */
1284 if (TREE_CODE (vr1min
) != INTEGER_CST
)
1286 else if (TYPE_PRECISION (TREE_TYPE (vr1min
)) == 1
1287 && !TYPE_UNSIGNED (TREE_TYPE (vr1min
)))
1289 = int_const_binop (PLUS_EXPR
, vr1min
,
1290 build_int_cst (TREE_TYPE (vr1min
), -1));
1293 = int_const_binop (MINUS_EXPR
, vr1min
,
1294 build_int_cst (TREE_TYPE (vr1min
), 1));
1296 /* Choose the anti-range if the range is effectively varying. */
1297 else if (vrp_val_is_min (*vr0min
)
1298 && vrp_val_is_max (*vr0max
))
1304 /* Else choose the range. */
1306 else if (*vr0type
== VR_ANTI_RANGE
1307 && vr1type
== VR_ANTI_RANGE
)
1308 /* If both are anti-ranges the result is the outer one. */
1310 else if (*vr0type
== VR_ANTI_RANGE
1311 && vr1type
== VR_RANGE
)
1313 /* The intersection is empty. */
1314 *vr0type
= VR_UNDEFINED
;
1315 *vr0min
= NULL_TREE
;
1316 *vr0max
= NULL_TREE
;
1321 else if ((maxeq
|| operand_less_p (*vr0max
, vr1max
) == 1)
1322 && (mineq
|| operand_less_p (vr1min
, *vr0min
) == 1))
1324 /* ( [ ] ) or ([ ] ) or ( [ ]) */
1325 if (*vr0type
== VR_RANGE
1326 && vr1type
== VR_RANGE
)
1327 /* Choose the inner range. */
1329 else if (*vr0type
== VR_ANTI_RANGE
1330 && vr1type
== VR_RANGE
)
1332 /* Choose the right gap if the left is empty. */
1335 *vr0type
= VR_RANGE
;
1336 if (TREE_CODE (*vr0max
) != INTEGER_CST
)
1338 else if (TYPE_PRECISION (TREE_TYPE (*vr0max
)) == 1
1339 && !TYPE_UNSIGNED (TREE_TYPE (*vr0max
)))
1341 = int_const_binop (MINUS_EXPR
, *vr0max
,
1342 build_int_cst (TREE_TYPE (*vr0max
), -1));
1345 = int_const_binop (PLUS_EXPR
, *vr0max
,
1346 build_int_cst (TREE_TYPE (*vr0max
), 1));
1349 /* Choose the left gap if the right is empty. */
1352 *vr0type
= VR_RANGE
;
1353 if (TREE_CODE (*vr0min
) != INTEGER_CST
)
1355 else if (TYPE_PRECISION (TREE_TYPE (*vr0min
)) == 1
1356 && !TYPE_UNSIGNED (TREE_TYPE (*vr0min
)))
1358 = int_const_binop (PLUS_EXPR
, *vr0min
,
1359 build_int_cst (TREE_TYPE (*vr0min
), -1));
1362 = int_const_binop (MINUS_EXPR
, *vr0min
,
1363 build_int_cst (TREE_TYPE (*vr0min
), 1));
1366 /* Choose the anti-range if the range is effectively varying. */
1367 else if (vrp_val_is_min (vr1min
)
1368 && vrp_val_is_max (vr1max
))
1370 /* Choose the anti-range if it is ~[0,0], that range is special
1371 enough to special case when vr1's range is relatively wide.
1372 At least for types bigger than int - this covers pointers
1373 and arguments to functions like ctz. */
1374 else if (*vr0min
== *vr0max
1375 && integer_zerop (*vr0min
)
1376 && ((TYPE_PRECISION (TREE_TYPE (*vr0min
))
1377 >= TYPE_PRECISION (integer_type_node
))
1378 || POINTER_TYPE_P (TREE_TYPE (*vr0min
)))
1379 && TREE_CODE (vr1max
) == INTEGER_CST
1380 && TREE_CODE (vr1min
) == INTEGER_CST
1381 && (wi::clz (wi::to_wide (vr1max
) - wi::to_wide (vr1min
))
1382 < TYPE_PRECISION (TREE_TYPE (*vr0min
)) / 2))
1384 /* Else choose the range. */
1392 else if (*vr0type
== VR_ANTI_RANGE
1393 && vr1type
== VR_ANTI_RANGE
)
1395 /* If both are anti-ranges the result is the outer one. */
1400 else if (vr1type
== VR_ANTI_RANGE
1401 && *vr0type
== VR_RANGE
)
1403 /* The intersection is empty. */
1404 *vr0type
= VR_UNDEFINED
;
1405 *vr0min
= NULL_TREE
;
1406 *vr0max
= NULL_TREE
;
1411 else if ((operand_less_p (vr1min
, *vr0max
) == 1
1412 || operand_equal_p (vr1min
, *vr0max
, 0))
1413 && operand_less_p (*vr0min
, vr1min
) == 1
1414 && operand_less_p (*vr0max
, vr1max
) == 1)
1416 /* [ ( ] ) or [ ]( ) */
1417 if (*vr0type
== VR_ANTI_RANGE
1418 && vr1type
== VR_ANTI_RANGE
)
1420 else if (*vr0type
== VR_RANGE
1421 && vr1type
== VR_RANGE
)
1423 else if (*vr0type
== VR_RANGE
1424 && vr1type
== VR_ANTI_RANGE
)
1426 if (TREE_CODE (vr1min
) == INTEGER_CST
)
1427 *vr0max
= int_const_binop (MINUS_EXPR
, vr1min
,
1428 build_int_cst (TREE_TYPE (vr1min
), 1));
1432 else if (*vr0type
== VR_ANTI_RANGE
1433 && vr1type
== VR_RANGE
)
1435 *vr0type
= VR_RANGE
;
1436 if (TREE_CODE (*vr0max
) == INTEGER_CST
)
1437 *vr0min
= int_const_binop (PLUS_EXPR
, *vr0max
,
1438 build_int_cst (TREE_TYPE (*vr0max
), 1));
1446 else if ((operand_less_p (*vr0min
, vr1max
) == 1
1447 || operand_equal_p (*vr0min
, vr1max
, 0))
1448 && operand_less_p (vr1min
, *vr0min
) == 1
1449 && operand_less_p (vr1max
, *vr0max
) == 1)
1451 /* ( [ ) ] or ( )[ ] */
1452 if (*vr0type
== VR_ANTI_RANGE
1453 && vr1type
== VR_ANTI_RANGE
)
1455 else if (*vr0type
== VR_RANGE
1456 && vr1type
== VR_RANGE
)
1458 else if (*vr0type
== VR_RANGE
1459 && vr1type
== VR_ANTI_RANGE
)
1461 if (TREE_CODE (vr1max
) == INTEGER_CST
)
1462 *vr0min
= int_const_binop (PLUS_EXPR
, vr1max
,
1463 build_int_cst (TREE_TYPE (vr1max
), 1));
1467 else if (*vr0type
== VR_ANTI_RANGE
1468 && vr1type
== VR_RANGE
)
1470 *vr0type
= VR_RANGE
;
1471 if (TREE_CODE (*vr0min
) == INTEGER_CST
)
1472 *vr0max
= int_const_binop (MINUS_EXPR
, *vr0min
,
1473 build_int_cst (TREE_TYPE (*vr0min
), 1));
1482 /* If we know the intersection is empty, there's no need to
1483 conservatively add anything else to the set. */
1484 if (*vr0type
== VR_UNDEFINED
)
1487 /* As a fallback simply use { *VRTYPE, *VR0MIN, *VR0MAX } as
1488 result for the intersection. That's always a conservative
1489 correct estimate unless VR1 is a constant singleton range
1490 in which case we choose that. */
1491 if (vr1type
== VR_RANGE
1492 && is_gimple_min_invariant (vr1min
)
1493 && vrp_operand_equal_p (vr1min
, vr1max
))
1501 /* Helper for the intersection operation for value ranges. Given two
1502 ranges VR0 and VR1, set VR0 to the intersection of both ranges.
1503 This may not be the smallest possible such range. */
1506 irange::legacy_intersect (irange
*vr0
, const irange
*vr1
)
1508 gcc_checking_assert (vr0
->legacy_mode_p ());
1509 gcc_checking_assert (vr1
->legacy_mode_p ());
1510 /* If either range is VR_VARYING the other one wins. */
1511 if (vr1
->varying_p ())
1513 if (vr0
->varying_p ())
1515 vr0
->set (vr1
->min (), vr1
->max (), vr1
->kind ());
1519 /* When either range is VR_UNDEFINED the resulting range is
1520 VR_UNDEFINED, too. */
1521 if (vr0
->undefined_p ())
1523 if (vr1
->undefined_p ())
1525 vr0
->set_undefined ();
1529 value_range_kind vr0kind
= vr0
->kind ();
1530 tree vr0min
= vr0
->min ();
1531 tree vr0max
= vr0
->max ();
1533 intersect_ranges (&vr0kind
, &vr0min
, &vr0max
,
1534 vr1
->kind (), vr1
->min (), vr1
->max ());
1536 // Pessimize nonzero masks, as we don't support them.
1537 m_nonzero_mask
= NULL
;
1539 /* Make sure to canonicalize the result though as the inversion of a
1540 VR_RANGE can still be a VR_RANGE. */
1541 if (vr0kind
== VR_UNDEFINED
)
1542 vr0
->set_undefined ();
1543 else if (vr0kind
== VR_VARYING
)
1545 /* If we failed, use the original VR0. */
1549 vr0
->set (vr0min
, vr0max
, vr0kind
);
1552 /* Union the two value-ranges { *VR0TYPE, *VR0MIN, *VR0MAX } and
1553 { VR1TYPE, VR0MIN, VR0MAX } and store the result
1554 in { *VR0TYPE, *VR0MIN, *VR0MAX }. This may not be the smallest
1555 possible such range. The resulting range is not canonicalized. */
1558 union_ranges (enum value_range_kind
*vr0type
,
1559 tree
*vr0min
, tree
*vr0max
,
1560 enum value_range_kind vr1type
,
1561 tree vr1min
, tree vr1max
)
1563 int cmpmin
= compare_values (*vr0min
, vr1min
);
1564 int cmpmax
= compare_values (*vr0max
, vr1max
);
1565 bool mineq
= cmpmin
== 0;
1566 bool maxeq
= cmpmax
== 0;
1568 /* [] is vr0, () is vr1 in the following classification comments. */
1572 if (*vr0type
== vr1type
)
1573 /* Nothing to do for equal ranges. */
1575 else if ((*vr0type
== VR_RANGE
1576 && vr1type
== VR_ANTI_RANGE
)
1577 || (*vr0type
== VR_ANTI_RANGE
1578 && vr1type
== VR_RANGE
))
1580 /* For anti-range with range union the result is varying. */
1586 else if (operand_less_p (*vr0max
, vr1min
) == 1
1587 || operand_less_p (vr1max
, *vr0min
) == 1)
1589 /* [ ] ( ) or ( ) [ ]
1590 If the ranges have an empty intersection, result of the union
1591 operation is the anti-range or if both are anti-ranges
1593 if (*vr0type
== VR_ANTI_RANGE
1594 && vr1type
== VR_ANTI_RANGE
)
1596 else if (*vr0type
== VR_ANTI_RANGE
1597 && vr1type
== VR_RANGE
)
1599 else if (*vr0type
== VR_RANGE
1600 && vr1type
== VR_ANTI_RANGE
)
1606 else if (*vr0type
== VR_RANGE
1607 && vr1type
== VR_RANGE
)
1609 /* The result is the convex hull of both ranges. */
1610 if (operand_less_p (*vr0max
, vr1min
) == 1)
1612 /* If the result can be an anti-range, create one. */
1613 if (TREE_CODE (*vr0max
) == INTEGER_CST
1614 && TREE_CODE (vr1min
) == INTEGER_CST
1615 && vrp_val_is_min (*vr0min
)
1616 && vrp_val_is_max (vr1max
))
1618 tree min
= int_const_binop (PLUS_EXPR
,
1620 build_int_cst (TREE_TYPE (*vr0max
), 1));
1621 tree max
= int_const_binop (MINUS_EXPR
,
1623 build_int_cst (TREE_TYPE (vr1min
), 1));
1624 if (!operand_less_p (max
, min
))
1626 *vr0type
= VR_ANTI_RANGE
;
1638 /* If the result can be an anti-range, create one. */
1639 if (TREE_CODE (vr1max
) == INTEGER_CST
1640 && TREE_CODE (*vr0min
) == INTEGER_CST
1641 && vrp_val_is_min (vr1min
)
1642 && vrp_val_is_max (*vr0max
))
1644 tree min
= int_const_binop (PLUS_EXPR
,
1646 build_int_cst (TREE_TYPE (vr1max
), 1));
1647 tree max
= int_const_binop (MINUS_EXPR
,
1649 build_int_cst (TREE_TYPE (*vr0min
), 1));
1650 if (!operand_less_p (max
, min
))
1652 *vr0type
= VR_ANTI_RANGE
;
1666 else if ((maxeq
|| cmpmax
== 1)
1667 && (mineq
|| cmpmin
== -1))
1669 /* [ ( ) ] or [( ) ] or [ ( )] */
1670 if (*vr0type
== VR_RANGE
1671 && vr1type
== VR_RANGE
)
1673 else if (*vr0type
== VR_ANTI_RANGE
1674 && vr1type
== VR_ANTI_RANGE
)
1680 else if (*vr0type
== VR_ANTI_RANGE
1681 && vr1type
== VR_RANGE
)
1683 /* Arbitrarily choose the right or left gap. */
1684 if (!mineq
&& TREE_CODE (vr1min
) == INTEGER_CST
)
1685 *vr0max
= int_const_binop (MINUS_EXPR
, vr1min
,
1686 build_int_cst (TREE_TYPE (vr1min
), 1));
1687 else if (!maxeq
&& TREE_CODE (vr1max
) == INTEGER_CST
)
1688 *vr0min
= int_const_binop (PLUS_EXPR
, vr1max
,
1689 build_int_cst (TREE_TYPE (vr1max
), 1));
1693 else if (*vr0type
== VR_RANGE
1694 && vr1type
== VR_ANTI_RANGE
)
1695 /* The result covers everything. */
1700 else if ((maxeq
|| cmpmax
== -1)
1701 && (mineq
|| cmpmin
== 1))
1703 /* ( [ ] ) or ([ ] ) or ( [ ]) */
1704 if (*vr0type
== VR_RANGE
1705 && vr1type
== VR_RANGE
)
1711 else if (*vr0type
== VR_ANTI_RANGE
1712 && vr1type
== VR_ANTI_RANGE
)
1714 else if (*vr0type
== VR_RANGE
1715 && vr1type
== VR_ANTI_RANGE
)
1717 *vr0type
= VR_ANTI_RANGE
;
1718 if (!mineq
&& TREE_CODE (*vr0min
) == INTEGER_CST
)
1720 *vr0max
= int_const_binop (MINUS_EXPR
, *vr0min
,
1721 build_int_cst (TREE_TYPE (*vr0min
), 1));
1724 else if (!maxeq
&& TREE_CODE (*vr0max
) == INTEGER_CST
)
1726 *vr0min
= int_const_binop (PLUS_EXPR
, *vr0max
,
1727 build_int_cst (TREE_TYPE (*vr0max
), 1));
1733 else if (*vr0type
== VR_ANTI_RANGE
1734 && vr1type
== VR_RANGE
)
1735 /* The result covers everything. */
1740 else if (cmpmin
== -1
1742 && (operand_less_p (vr1min
, *vr0max
) == 1
1743 || operand_equal_p (vr1min
, *vr0max
, 0)))
1745 /* [ ( ] ) or [ ]( ) */
1746 if (*vr0type
== VR_RANGE
1747 && vr1type
== VR_RANGE
)
1749 else if (*vr0type
== VR_ANTI_RANGE
1750 && vr1type
== VR_ANTI_RANGE
)
1752 else if (*vr0type
== VR_ANTI_RANGE
1753 && vr1type
== VR_RANGE
)
1755 if (TREE_CODE (vr1min
) == INTEGER_CST
)
1756 *vr0max
= int_const_binop (MINUS_EXPR
, vr1min
,
1757 build_int_cst (TREE_TYPE (vr1min
), 1));
1761 else if (*vr0type
== VR_RANGE
1762 && vr1type
== VR_ANTI_RANGE
)
1764 if (TREE_CODE (*vr0max
) == INTEGER_CST
)
1767 *vr0min
= int_const_binop (PLUS_EXPR
, *vr0max
,
1768 build_int_cst (TREE_TYPE (*vr0max
), 1));
1777 else if (cmpmin
== 1
1779 && (operand_less_p (*vr0min
, vr1max
) == 1
1780 || operand_equal_p (*vr0min
, vr1max
, 0)))
1782 /* ( [ ) ] or ( )[ ] */
1783 if (*vr0type
== VR_RANGE
1784 && vr1type
== VR_RANGE
)
1786 else if (*vr0type
== VR_ANTI_RANGE
1787 && vr1type
== VR_ANTI_RANGE
)
1789 else if (*vr0type
== VR_ANTI_RANGE
1790 && vr1type
== VR_RANGE
)
1792 if (TREE_CODE (vr1max
) == INTEGER_CST
)
1793 *vr0min
= int_const_binop (PLUS_EXPR
, vr1max
,
1794 build_int_cst (TREE_TYPE (vr1max
), 1));
1798 else if (*vr0type
== VR_RANGE
1799 && vr1type
== VR_ANTI_RANGE
)
1801 if (TREE_CODE (*vr0min
) == INTEGER_CST
)
1804 *vr0max
= int_const_binop (MINUS_EXPR
, *vr0min
,
1805 build_int_cst (TREE_TYPE (*vr0min
), 1));
1820 *vr0type
= VR_VARYING
;
1821 *vr0min
= NULL_TREE
;
1822 *vr0max
= NULL_TREE
;
1825 /* Helper for meet operation for value ranges. Given two ranges VR0
1826 and VR1, set VR0 to the union of both ranges. This may not be the
1827 smallest possible such range. */
1830 irange::legacy_union (irange
*vr0
, const irange
*vr1
)
1832 gcc_checking_assert (vr0
->legacy_mode_p ());
1833 gcc_checking_assert (vr1
->legacy_mode_p ());
1835 /* VR0 has the resulting range if VR1 is undefined or VR0 is varying. */
1836 if (vr1
->undefined_p ()
1837 || vr0
->varying_p ())
1840 /* VR1 has the resulting range if VR0 is undefined or VR1 is varying. */
1841 if (vr0
->undefined_p ())
1843 vr0
->set (vr1
->min (), vr1
->max (), vr1
->kind ());
1847 if (vr1
->varying_p ())
1849 vr0
->set_varying (vr1
->type ());
1853 value_range_kind vr0kind
= vr0
->kind ();
1854 tree vr0min
= vr0
->min ();
1855 tree vr0max
= vr0
->max ();
1857 union_ranges (&vr0kind
, &vr0min
, &vr0max
,
1858 vr1
->kind (), vr1
->min (), vr1
->max ());
1860 // Pessimize nonzero masks, as we don't support them.
1861 m_nonzero_mask
= NULL
;
1863 if (vr0kind
== VR_UNDEFINED
)
1864 vr0
->set_undefined ();
1865 else if (vr0kind
== VR_VARYING
)
1867 /* Failed to find an efficient meet. Before giving up and
1868 setting the result to VARYING, see if we can at least derive
1869 a non-zero range. */
1870 if (range_includes_zero_p (vr0
) == 0
1871 && range_includes_zero_p (vr1
) == 0)
1872 vr0
->set_nonzero (vr0
->type ());
1874 vr0
->set_varying (vr0
->type ());
1877 vr0
->set (vr0min
, vr0max
, vr0kind
);
1880 /* Meet operation for value ranges. Given two value ranges VR0 and
1881 VR1, store in VR0 a range that contains both VR0 and VR1. This
1882 may not be the smallest possible such range.
1883 Return TRUE if the original value changes. */
1886 irange::legacy_verbose_union_ (const irange
*other
)
1888 if (legacy_mode_p ())
1890 if (!other
->legacy_mode_p ())
1892 int_range
<1> tmp
= *other
;
1893 legacy_union (this, &tmp
);
1896 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1898 fprintf (dump_file
, "Meeting\n ");
1899 dump_value_range (dump_file
, this);
1900 fprintf (dump_file
, "\nand\n ");
1901 dump_value_range (dump_file
, other
);
1902 fprintf (dump_file
, "\n");
1905 legacy_union (this, other
);
1907 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1909 fprintf (dump_file
, "to\n ");
1910 dump_value_range (dump_file
, this);
1911 fprintf (dump_file
, "\n");
1916 if (other
->legacy_mode_p ())
1918 int_range
<2> wider
= *other
;
1919 return irange_union (wider
);
1922 return irange_union (*other
);
1926 irange::legacy_verbose_intersect (const irange
*other
)
1928 if (legacy_mode_p ())
1930 if (!other
->legacy_mode_p ())
1932 int_range
<1> tmp
= *other
;
1933 legacy_intersect (this, &tmp
);
1936 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1938 fprintf (dump_file
, "Intersecting\n ");
1939 dump_value_range (dump_file
, this);
1940 fprintf (dump_file
, "\nand\n ");
1941 dump_value_range (dump_file
, other
);
1942 fprintf (dump_file
, "\n");
1945 legacy_intersect (this, other
);
1947 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1949 fprintf (dump_file
, "to\n ");
1950 dump_value_range (dump_file
, this);
1951 fprintf (dump_file
, "\n");
1956 if (other
->legacy_mode_p ())
1960 return irange_intersect (wider
);
1963 return irange_intersect (*other
);
1966 // Perform an efficient union with R when both ranges have only a single pair.
1967 // Excluded are VARYING and UNDEFINED ranges.
1969 // NOTE: It is the caller's responsibility to set the nonzero mask.
1972 irange::irange_single_pair_union (const irange
&r
)
1974 gcc_checking_assert (!undefined_p () && !varying_p ());
1975 gcc_checking_assert (!r
.undefined_p () && !varying_p ());
1977 signop sign
= TYPE_SIGN (TREE_TYPE (m_base
[0]));
1978 // Check if current lower bound is also the new lower bound.
1979 if (wi::le_p (wi::to_wide (m_base
[0]), wi::to_wide (r
.m_base
[0]), sign
))
1981 // If current upper bound is new upper bound, we're done.
1982 if (wi::le_p (wi::to_wide (r
.m_base
[1]), wi::to_wide (m_base
[1]), sign
))
1984 // Otherwise R has the new upper bound.
1985 // Check for overlap/touching ranges, or single target range.
1986 if (m_max_ranges
== 1
1987 || wi::to_widest (m_base
[1]) + 1 >= wi::to_widest (r
.m_base
[0]))
1988 m_base
[1] = r
.m_base
[1];
1991 // This is a dual range result.
1992 m_base
[2] = r
.m_base
[0];
1993 m_base
[3] = r
.m_base
[1];
1996 if (varying_compatible_p ())
1997 m_kind
= VR_VARYING
;
2001 // Set the new lower bound to R's lower bound.
2002 tree lb
= m_base
[0];
2003 m_base
[0] = r
.m_base
[0];
2005 // If R fully contains THIS range, just set the upper bound.
2006 if (wi::ge_p (wi::to_wide (r
.m_base
[1]), wi::to_wide (m_base
[1]), sign
))
2007 m_base
[1] = r
.m_base
[1];
2008 // Check for overlapping ranges, or target limited to a single range.
2009 else if (m_max_ranges
== 1
2010 || wi::to_widest (r
.m_base
[1]) + 1 >= wi::to_widest (lb
))
2012 // This has the new upper bound, just check for varying.
2013 if (varying_compatible_p ())
2014 m_kind
= VR_VARYING
;
2018 // Left with 2 pairs.
2021 m_base
[3] = m_base
[1];
2022 m_base
[1] = r
.m_base
[1];
2024 if (varying_compatible_p ())
2025 m_kind
= VR_VARYING
;
2029 // union_ for multi-ranges.
2032 irange::irange_union (const irange
&r
)
2034 gcc_checking_assert (!legacy_mode_p () && !r
.legacy_mode_p ());
2036 if (r
.undefined_p ())
2052 set_varying (type ());
2056 // Save the nonzero mask in case the set operations below clobber it.
2057 bool ret_nz
= union_nonzero_bits (r
);
2058 tree saved_nz
= m_nonzero_mask
;
2060 // The union_nonzero_bits may have turned things into a varying.
2064 // Special case one range union one range.
2065 if (m_num_ranges
== 1 && r
.m_num_ranges
== 1)
2067 bool ret
= irange_single_pair_union (r
);
2068 set_nonzero_bits (saved_nz
);
2071 return ret
|| ret_nz
;
2074 // If this ranges fully contains R, then we need do nothing.
2075 if (irange_contains_p (r
))
2078 // Do not worry about merging and such by reserving twice as many
2079 // pairs as needed, and then simply sort the 2 ranges into this
2080 // intermediate form.
2082 // The intermediate result will have the property that the beginning
2083 // of each range is <= the beginning of the next range. There may
2084 // be overlapping ranges at this point. I.e. this would be valid
2085 // [-20, 10], [-10, 0], [0, 20], [40, 90] as it satisfies this
2086 // contraint : -20 < -10 < 0 < 40. When the range is rebuilt into r,
2087 // the merge is performed.
2089 // [Xi,Yi]..[Xn,Yn] U [Xj,Yj]..[Xm,Ym] --> [Xk,Yk]..[Xp,Yp]
2090 auto_vec
<tree
, 20> res (m_num_ranges
* 2 + r
.m_num_ranges
* 2);
2091 unsigned i
= 0, j
= 0, k
= 0;
2093 while (i
< m_num_ranges
* 2 && j
< r
.m_num_ranges
* 2)
2095 // lower of Xi and Xj is the lowest point.
2096 if (wi::to_widest (m_base
[i
]) <= wi::to_widest (r
.m_base
[j
]))
2098 res
.quick_push (m_base
[i
]);
2099 res
.quick_push (m_base
[i
+ 1]);
2105 res
.quick_push (r
.m_base
[j
]);
2106 res
.quick_push (r
.m_base
[j
+ 1]);
2111 for ( ; i
< m_num_ranges
* 2; i
+= 2)
2113 res
.quick_push (m_base
[i
]);
2114 res
.quick_push (m_base
[i
+ 1]);
2117 for ( ; j
< r
.m_num_ranges
* 2; j
+= 2)
2119 res
.quick_push (r
.m_base
[j
]);
2120 res
.quick_push (r
.m_base
[j
+ 1]);
2124 // Now normalize the vector removing any overlaps.
2126 for (j
= 2; j
< k
; j
+= 2)
2128 // Current upper+1 is >= lower bound next pair, then we merge ranges.
2129 if (wi::to_widest (res
[i
- 1]) + 1 >= wi::to_widest (res
[j
]))
2131 // New upper bounds is greater of current or the next one.
2132 if (wi::to_widest (res
[j
+ 1]) > wi::to_widest (res
[i
- 1]))
2133 res
[i
- 1] = res
[j
+ 1];
2137 // This is a new distinct range, but no point in copying it
2138 // if it is already in the right place.
2142 res
[i
++] = res
[j
+ 1];
2149 // At this point, the vector should have i ranges, none overlapping.
2150 // Now it simply needs to be copied, and if there are too many
2151 // ranges, merge some. We wont do any analysis as to what the
2152 // "best" merges are, simply combine the final ranges into one.
2153 if (i
> m_max_ranges
* 2)
2155 res
[m_max_ranges
* 2 - 1] = res
[i
- 1];
2156 i
= m_max_ranges
* 2;
2159 for (j
= 0; j
< i
; j
++)
2160 m_base
[j
] = res
[j
];
2161 m_num_ranges
= i
/ 2;
2164 m_nonzero_mask
= saved_nz
;
2172 // Return TRUE if THIS fully contains R. No undefined or varying cases.
2175 irange::irange_contains_p (const irange
&r
) const
2177 gcc_checking_assert (!undefined_p () && !varying_p ());
2178 gcc_checking_assert (!r
.undefined_p () && !varying_p ());
2180 // In order for THIS to fully contain R, all of the pairs within R must
2181 // be fully contained by the pairs in this object.
2182 signop sign
= TYPE_SIGN (TREE_TYPE(m_base
[0]));
2185 tree rl
= r
.m_base
[0];
2186 tree ru
= r
.m_base
[1];
2191 // If r is contained within this range, move to the next R
2192 if (wi::ge_p (wi::to_wide (rl
), wi::to_wide (l
), sign
)
2193 && wi::le_p (wi::to_wide (ru
), wi::to_wide (u
), sign
))
2195 // This pair is OK, Either done, or bump to the next.
2196 if (++ri
>= r
.num_pairs ())
2198 rl
= r
.m_base
[ri
* 2];
2199 ru
= r
.m_base
[ri
* 2 + 1];
2202 // Otherwise, check if this's pair occurs before R's.
2203 if (wi::lt_p (wi::to_wide (u
), wi::to_wide (rl
), sign
))
2205 // THere's still at leats one pair of R left.
2206 if (++i
>= num_pairs ())
2209 u
= m_base
[i
* 2 + 1];
2218 // Intersect for multi-ranges. Return TRUE if anything changes.
2221 irange::irange_intersect (const irange
&r
)
2223 gcc_checking_assert (!legacy_mode_p () && !r
.legacy_mode_p ());
2224 gcc_checking_assert (undefined_p () || r
.undefined_p ()
2225 || range_compatible_p (type (), r
.type ()));
2229 if (r
.undefined_p ())
2235 // Save the nonzero mask in case the set operations below clobber it.
2236 bool ret_nz
= intersect_nonzero_bits (r
);
2237 tree saved_nz
= m_nonzero_mask
;
2246 set_nonzero_bits (saved_nz
);
2252 if (r
.num_pairs () == 1)
2254 bool res
= intersect (r
.lower_bound (), r
.upper_bound ());
2258 set_nonzero_bits (saved_nz
);
2259 return res
|| saved_nz
;
2262 // If R fully contains this, then intersection will change nothing.
2263 if (r
.irange_contains_p (*this))
2266 signop sign
= TYPE_SIGN (TREE_TYPE(m_base
[0]));
2267 unsigned bld_pair
= 0;
2268 unsigned bld_lim
= m_max_ranges
;
2269 int_range_max
r2 (*this);
2270 unsigned r2_lim
= r2
.num_pairs ();
2272 for (unsigned i
= 0; i
< r
.num_pairs (); )
2274 // If r1's upper is < r2's lower, we can skip r1's pair.
2275 tree ru
= r
.m_base
[i
* 2 + 1];
2276 tree r2l
= r2
.m_base
[i2
* 2];
2277 if (wi::lt_p (wi::to_wide (ru
), wi::to_wide (r2l
), sign
))
2282 // Likewise, skip r2's pair if its excluded.
2283 tree r2u
= r2
.m_base
[i2
* 2 + 1];
2284 tree rl
= r
.m_base
[i
* 2];
2285 if (wi::lt_p (wi::to_wide (r2u
), wi::to_wide (rl
), sign
))
2290 // No more r2, break.
2294 // Must be some overlap. Find the highest of the lower bounds,
2295 // and set it, unless the build limits lower bounds is already
2297 if (bld_pair
< bld_lim
)
2299 if (wi::ge_p (wi::to_wide (rl
), wi::to_wide (r2l
), sign
))
2300 m_base
[bld_pair
* 2] = rl
;
2302 m_base
[bld_pair
* 2] = r2l
;
2305 // Decrease and set a new upper.
2308 // ...and choose the lower of the upper bounds.
2309 if (wi::le_p (wi::to_wide (ru
), wi::to_wide (r2u
), sign
))
2311 m_base
[bld_pair
* 2 + 1] = ru
;
2313 // Move past the r1 pair and keep trying.
2319 m_base
[bld_pair
* 2 + 1] = r2u
;
2324 // No more r2, break.
2327 // r2 has the higher lower bound.
2330 // At the exit of this loop, it is one of 2 things:
2331 // ran out of r1, or r2, but either means we are done.
2332 m_num_ranges
= bld_pair
;
2335 if (!undefined_p ())
2336 m_nonzero_mask
= saved_nz
;
2346 // Multirange intersect for a specified wide_int [lb, ub] range.
2347 // Return TRUE if intersect changed anything.
2349 // NOTE: It is the caller's responsibility to intersect the nonzero masks.
2352 irange::intersect (const wide_int
& lb
, const wide_int
& ub
)
2354 // Undefined remains undefined.
2358 if (legacy_mode_p ())
2360 intersect (int_range
<1> (type (), lb
, ub
));
2364 tree range_type
= type();
2365 signop sign
= TYPE_SIGN (range_type
);
2367 gcc_checking_assert (TYPE_PRECISION (range_type
) == wi::get_precision (lb
));
2368 gcc_checking_assert (TYPE_PRECISION (range_type
) == wi::get_precision (ub
));
2370 // If this range is fuly contained, then intersection will do nothing.
2371 if (wi::ge_p (lower_bound (), lb
, sign
)
2372 && wi::le_p (upper_bound (), ub
, sign
))
2375 unsigned bld_index
= 0;
2376 unsigned pair_lim
= num_pairs ();
2377 for (unsigned i
= 0; i
< pair_lim
; i
++)
2379 tree pairl
= m_base
[i
* 2];
2380 tree pairu
= m_base
[i
* 2 + 1];
2381 // Once UB is less than a pairs lower bound, we're done.
2382 if (wi::lt_p (ub
, wi::to_wide (pairl
), sign
))
2384 // if LB is greater than this pairs upper, this pair is excluded.
2385 if (wi::lt_p (wi::to_wide (pairu
), lb
, sign
))
2388 // Must be some overlap. Find the highest of the lower bounds,
2390 if (wi::gt_p (lb
, wi::to_wide (pairl
), sign
))
2391 m_base
[bld_index
* 2] = wide_int_to_tree (range_type
, lb
);
2393 m_base
[bld_index
* 2] = pairl
;
2395 // ...and choose the lower of the upper bounds and if the base pair
2396 // has the lower upper bound, need to check next pair too.
2397 if (wi::lt_p (ub
, wi::to_wide (pairu
), sign
))
2399 m_base
[bld_index
++ * 2 + 1] = wide_int_to_tree (range_type
, ub
);
2403 m_base
[bld_index
++ * 2 + 1] = pairu
;
2406 m_num_ranges
= bld_index
;
2417 // Signed 1-bits are strange. You can't subtract 1, because you can't
2418 // represent the number 1. This works around that for the invert routine.
2420 static wide_int
inline
2421 subtract_one (const wide_int
&x
, tree type
, wi::overflow_type
&overflow
)
2423 if (TYPE_SIGN (type
) == SIGNED
)
2424 return wi::add (x
, -1, SIGNED
, &overflow
);
2426 return wi::sub (x
, 1, UNSIGNED
, &overflow
);
2429 // The analogous function for adding 1.
2431 static wide_int
inline
2432 add_one (const wide_int
&x
, tree type
, wi::overflow_type
&overflow
)
2434 if (TYPE_SIGN (type
) == SIGNED
)
2435 return wi::sub (x
, -1, SIGNED
, &overflow
);
2437 return wi::add (x
, 1, UNSIGNED
, &overflow
);
2440 // Return the inverse of a range.
2445 if (legacy_mode_p ())
2447 // We can't just invert VR_RANGE and VR_ANTI_RANGE because we may
2448 // create non-canonical ranges. Use the constructors instead.
2449 if (m_kind
== VR_RANGE
)
2450 *this = value_range (min (), max (), VR_ANTI_RANGE
);
2451 else if (m_kind
== VR_ANTI_RANGE
)
2452 *this = value_range (min (), max ());
2458 gcc_checking_assert (!undefined_p () && !varying_p ());
2459 m_nonzero_mask
= NULL
;
2461 // We always need one more set of bounds to represent an inverse, so
2462 // if we're at the limit, we can't properly represent things.
2464 // For instance, to represent the inverse of a 2 sub-range set
2465 // [5, 10][20, 30], we would need a 3 sub-range set
2466 // [-MIN, 4][11, 19][31, MAX].
2468 // In this case, return the most conservative thing.
2470 // However, if any of the extremes of the range are -MIN/+MAX, we
2471 // know we will not need an extra bound. For example:
2473 // INVERT([-MIN,20][30,40]) => [21,29][41,+MAX]
2474 // INVERT([-MIN,20][30,MAX]) => [21,29]
2475 tree ttype
= type ();
2476 unsigned prec
= TYPE_PRECISION (ttype
);
2477 signop sign
= TYPE_SIGN (ttype
);
2478 wide_int type_min
= wi::min_value (prec
, sign
);
2479 wide_int type_max
= wi::max_value (prec
, sign
);
2480 if (m_num_ranges
== m_max_ranges
2481 && lower_bound () != type_min
2482 && upper_bound () != type_max
)
2484 m_base
[1] = wide_int_to_tree (ttype
, type_max
);
2488 // The algorithm is as follows. To calculate INVERT ([a,b][c,d]), we
2489 // generate [-MIN, a-1][b+1, c-1][d+1, MAX].
2491 // If there is an over/underflow in the calculation for any
2492 // sub-range, we eliminate that subrange. This allows us to easily
2493 // calculate INVERT([-MIN, 5]) with: [-MIN, -MIN-1][6, MAX]. And since
2494 // we eliminate the underflow, only [6, MAX] remains.
2496 wi::overflow_type ovf
;
2497 // Construct leftmost range.
2498 int_range_max
orig_range (*this);
2499 unsigned nitems
= 0;
2501 // If this is going to underflow on the MINUS 1, don't even bother
2502 // checking. This also handles subtracting one from an unsigned 0,
2503 // which doesn't set the underflow bit.
2504 if (type_min
!= orig_range
.lower_bound ())
2506 m_base
[nitems
++] = wide_int_to_tree (ttype
, type_min
);
2507 tmp
= subtract_one (orig_range
.lower_bound (), ttype
, ovf
);
2508 m_base
[nitems
++] = wide_int_to_tree (ttype
, tmp
);
2513 // Construct middle ranges if applicable.
2514 if (orig_range
.num_pairs () > 1)
2517 for (; j
< (orig_range
.num_pairs () * 2) - 1; j
+= 2)
2519 // The middle ranges cannot have MAX/MIN, so there's no need
2520 // to check for unsigned overflow on the +1 and -1 here.
2521 tmp
= wi::add (wi::to_wide (orig_range
.m_base
[j
]), 1, sign
, &ovf
);
2522 m_base
[nitems
++] = wide_int_to_tree (ttype
, tmp
);
2523 tmp
= subtract_one (wi::to_wide (orig_range
.m_base
[j
+ 1]),
2525 m_base
[nitems
++] = wide_int_to_tree (ttype
, tmp
);
2531 // Construct rightmost range.
2533 // However, if this will overflow on the PLUS 1, don't even bother.
2534 // This also handles adding one to an unsigned MAX, which doesn't
2535 // set the overflow bit.
2536 if (type_max
!= wi::to_wide (orig_range
.m_base
[i
]))
2538 tmp
= add_one (wi::to_wide (orig_range
.m_base
[i
]), ttype
, ovf
);
2539 m_base
[nitems
++] = wide_int_to_tree (ttype
, tmp
);
2540 m_base
[nitems
++] = wide_int_to_tree (ttype
, type_max
);
2544 m_num_ranges
= nitems
/ 2;
2546 // We disallow undefined or varying coming in, so the result can
2547 // only be a VR_RANGE.
2548 gcc_checking_assert (m_kind
== VR_RANGE
);
2555 irange::set_nonzero_bits (tree mask
)
2557 gcc_checking_assert (!undefined_p ());
2563 m_nonzero_mask
= NULL
;
2564 // Clearing the mask may have turned a range into VARYING.
2569 m_nonzero_mask
= mask
;
2570 // Setting the mask may have turned a VARYING into a range.
2571 if (m_kind
== VR_VARYING
)
2579 irange::set_nonzero_bits (const wide_int_ref
&bits
)
2581 gcc_checking_assert (!undefined_p ());
2585 set_nonzero_bits (NULL
);
2588 set_nonzero_bits (wide_int_to_tree (type (), bits
));
2592 irange::get_nonzero_bits () const
2594 gcc_checking_assert (!undefined_p ());
2596 // In case anyone in the legacy world queries us.
2600 return wi::to_wide (m_nonzero_mask
);
2601 return wi::shwi (-1, TYPE_PRECISION (type ()));
2604 // Calculate the nonzero bits inherent in the range.
2605 wide_int min
= lower_bound ();
2606 wide_int max
= upper_bound ();
2607 wide_int xorv
= min
^ max
;
2610 unsigned prec
= TYPE_PRECISION (type ());
2611 xorv
= wi::mask (prec
- wi::clz (xorv
), false, prec
);
2613 wide_int mask
= min
| xorv
;
2615 // Return the nonzero bits augmented by the range.
2617 return mask
& wi::to_wide (m_nonzero_mask
);
2622 // Intersect the nonzero bits in R into THIS.
2625 irange::intersect_nonzero_bits (const irange
&r
)
2627 gcc_checking_assert (!undefined_p () && !r
.undefined_p ());
2629 if (m_nonzero_mask
|| r
.m_nonzero_mask
)
2631 wide_int nz
= wi::bit_and (get_nonzero_bits (),
2632 r
.get_nonzero_bits ());
2633 set_nonzero_bits (nz
);
2639 // Union the nonzero bits in R into THIS.
2642 irange::union_nonzero_bits (const irange
&r
)
2644 gcc_checking_assert (!undefined_p () && !r
.undefined_p ());
2646 if (m_nonzero_mask
|| r
.m_nonzero_mask
)
2648 wide_int nz
= wi::bit_or (get_nonzero_bits (),
2649 r
.get_nonzero_bits ());
2650 set_nonzero_bits (nz
);
2657 dump_value_range (FILE *file
, const vrange
*vr
)
2663 debug (const vrange
*vr
)
2665 dump_value_range (stderr
, vr
);
2666 fprintf (stderr
, "\n");
2670 debug (const vrange
&vr
)
2676 debug (const value_range
*vr
)
2678 dump_value_range (stderr
, vr
);
2679 fprintf (stderr
, "\n");
2683 debug (const value_range
&vr
)
2685 dump_value_range (stderr
, &vr
);
2686 fprintf (stderr
, "\n");
2689 /* Create two value-ranges in *VR0 and *VR1 from the anti-range *AR
2690 so that *VR0 U *VR1 == *AR. Returns true if that is possible,
2691 false otherwise. If *AR can be represented with a single range
2692 *VR1 will be VR_UNDEFINED. */
2695 ranges_from_anti_range (const value_range
*ar
,
2696 value_range
*vr0
, value_range
*vr1
)
2698 tree type
= ar
->type ();
2700 vr0
->set_undefined ();
2701 vr1
->set_undefined ();
2703 /* As a future improvement, we could handle ~[0, A] as: [-INF, -1] U
2704 [A+1, +INF]. Not sure if this helps in practice, though. */
2706 if (ar
->kind () != VR_ANTI_RANGE
2707 || TREE_CODE (ar
->min ()) != INTEGER_CST
2708 || TREE_CODE (ar
->max ()) != INTEGER_CST
2709 || !vrp_val_min (type
)
2710 || !vrp_val_max (type
))
2713 if (tree_int_cst_lt (vrp_val_min (type
), ar
->min ()))
2714 vr0
->set (vrp_val_min (type
),
2715 wide_int_to_tree (type
, wi::to_wide (ar
->min ()) - 1));
2716 if (tree_int_cst_lt (ar
->max (), vrp_val_max (type
)))
2717 vr1
->set (wide_int_to_tree (type
, wi::to_wide (ar
->max ()) + 1),
2718 vrp_val_max (type
));
2719 if (vr0
->undefined_p ())
2722 vr1
->set_undefined ();
2725 return !vr0
->undefined_p ();
2729 range_has_numeric_bounds_p (const irange
*vr
)
2731 return (!vr
->undefined_p ()
2732 && TREE_CODE (vr
->min ()) == INTEGER_CST
2733 && TREE_CODE (vr
->max ()) == INTEGER_CST
);
2736 /* Return whether VAL is equal to the maximum value of its type.
2737 We can't do a simple equality comparison with TYPE_MAX_VALUE because
2738 C typedefs and Ada subtypes can produce types whose TYPE_MAX_VALUE
2739 is not == to the integer constant with the same value in the type. */
2742 vrp_val_is_max (const_tree val
)
2744 tree type_max
= vrp_val_max (TREE_TYPE (val
));
2745 return (val
== type_max
2746 || (type_max
!= NULL_TREE
2747 && operand_equal_p (val
, type_max
, 0)));
2750 /* Return whether VAL is equal to the minimum value of its type. */
2753 vrp_val_is_min (const_tree val
)
2755 tree type_min
= vrp_val_min (TREE_TYPE (val
));
2756 return (val
== type_min
2757 || (type_min
!= NULL_TREE
2758 && operand_equal_p (val
, type_min
, 0)));
2761 /* Return true, if VAL1 and VAL2 are equal values for VRP purposes. */
2764 vrp_operand_equal_p (const_tree val1
, const_tree val2
)
2768 if (!val1
|| !val2
|| !operand_equal_p (val1
, val2
, 0))
2773 // ?? These stubs are for ipa-prop.cc which use a value_range in a
2774 // hash_traits. hash-traits.h defines an extern of gt_ggc_mx (T &)
2775 // instead of picking up the gt_ggc_mx (T *) version.
2777 gt_pch_nx (int_range
<1> *&x
)
2779 return gt_pch_nx ((irange
*) x
);
2783 gt_ggc_mx (int_range
<1> *&x
)
2785 return gt_ggc_mx ((irange
*) x
);
2788 #define DEFINE_INT_RANGE_INSTANCE(N) \
2789 template int_range<N>::int_range(tree, tree, value_range_kind); \
2790 template int_range<N>::int_range(tree_node *, \
2793 value_range_kind); \
2794 template int_range<N>::int_range(tree); \
2795 template int_range<N>::int_range(const irange &); \
2796 template int_range<N>::int_range(const int_range &); \
2797 template int_range<N>& int_range<N>::operator= (const int_range &);
2799 DEFINE_INT_RANGE_INSTANCE(1)
2800 DEFINE_INT_RANGE_INSTANCE(2)
2801 DEFINE_INT_RANGE_INSTANCE(3)
2802 DEFINE_INT_RANGE_INSTANCE(255)
2805 #include "selftest.h"
2809 #define INT(N) build_int_cst (integer_type_node, (N))
2810 #define UINT(N) build_int_cstu (unsigned_type_node, (N))
2811 #define UINT128(N) build_int_cstu (u128_type, (N))
2812 #define UCHAR(N) build_int_cstu (unsigned_char_type_node, (N))
2813 #define SCHAR(N) build_int_cst (signed_char_type_node, (N))
2816 build_range3 (int a
, int b
, int c
, int d
, int e
, int f
)
2818 int_range
<3> i1 (INT (a
), INT (b
));
2819 int_range
<3> i2 (INT (c
), INT (d
));
2820 int_range
<3> i3 (INT (e
), INT (f
));
2827 range_tests_irange3 ()
2829 typedef int_range
<3> int_range3
;
2830 int_range3 r0
, r1
, r2
;
2831 int_range3 i1
, i2
, i3
;
2833 // ([10,20] U [5,8]) U [1,3] ==> [1,3][5,8][10,20].
2834 r0
= int_range3 (INT (10), INT (20));
2835 r1
= int_range3 (INT (5), INT (8));
2837 r1
= int_range3 (INT (1), INT (3));
2839 ASSERT_TRUE (r0
== build_range3 (1, 3, 5, 8, 10, 20));
2841 // [1,3][5,8][10,20] U [-5,0] => [-5,3][5,8][10,20].
2842 r1
= int_range3 (INT (-5), INT (0));
2844 ASSERT_TRUE (r0
== build_range3 (-5, 3, 5, 8, 10, 20));
2846 // [10,20][30,40] U [50,60] ==> [10,20][30,40][50,60].
2847 r1
= int_range3 (INT (50), INT (60));
2848 r0
= int_range3 (INT (10), INT (20));
2849 r0
.union_ (int_range3 (INT (30), INT (40)));
2851 ASSERT_TRUE (r0
== build_range3 (10, 20, 30, 40, 50, 60));
2852 // [10,20][30,40][50,60] U [70, 80] ==> [10,20][30,40][50,60][70,80].
2853 r1
= int_range3 (INT (70), INT (80));
2856 r2
= build_range3 (10, 20, 30, 40, 50, 60);
2857 r2
.union_ (int_range3 (INT (70), INT (80)));
2858 ASSERT_TRUE (r0
== r2
);
2860 // [10,20][30,40][50,60] U [6,35] => [6,40][50,60].
2861 r0
= build_range3 (10, 20, 30, 40, 50, 60);
2862 r1
= int_range3 (INT (6), INT (35));
2864 r1
= int_range3 (INT (6), INT (40));
2865 r1
.union_ (int_range3 (INT (50), INT (60)));
2866 ASSERT_TRUE (r0
== r1
);
2868 // [10,20][30,40][50,60] U [6,60] => [6,60].
2869 r0
= build_range3 (10, 20, 30, 40, 50, 60);
2870 r1
= int_range3 (INT (6), INT (60));
2872 ASSERT_TRUE (r0
== int_range3 (INT (6), INT (60)));
2874 // [10,20][30,40][50,60] U [6,70] => [6,70].
2875 r0
= build_range3 (10, 20, 30, 40, 50, 60);
2876 r1
= int_range3 (INT (6), INT (70));
2878 ASSERT_TRUE (r0
== int_range3 (INT (6), INT (70)));
2880 // [10,20][30,40][50,60] U [35,70] => [10,20][30,70].
2881 r0
= build_range3 (10, 20, 30, 40, 50, 60);
2882 r1
= int_range3 (INT (35), INT (70));
2884 r1
= int_range3 (INT (10), INT (20));
2885 r1
.union_ (int_range3 (INT (30), INT (70)));
2886 ASSERT_TRUE (r0
== r1
);
2888 // [10,20][30,40][50,60] U [15,35] => [10,40][50,60].
2889 r0
= build_range3 (10, 20, 30, 40, 50, 60);
2890 r1
= int_range3 (INT (15), INT (35));
2892 r1
= int_range3 (INT (10), INT (40));
2893 r1
.union_ (int_range3 (INT (50), INT (60)));
2894 ASSERT_TRUE (r0
== r1
);
2896 // [10,20][30,40][50,60] U [35,35] => [10,20][30,40][50,60].
2897 r0
= build_range3 (10, 20, 30, 40, 50, 60);
2898 r1
= int_range3 (INT (35), INT (35));
2900 ASSERT_TRUE (r0
== build_range3 (10, 20, 30, 40, 50, 60));
2904 range_tests_int_range_max ()
2907 unsigned int nrange
;
2909 // Build a huge multi-range range.
2910 for (nrange
= 0; nrange
< 50; ++nrange
)
2912 int_range
<1> tmp (INT (nrange
*10), INT (nrange
*10 + 5));
2915 ASSERT_TRUE (big
.num_pairs () == nrange
);
2917 // Verify that we can copy it without loosing precision.
2918 int_range_max
copy (big
);
2919 ASSERT_TRUE (copy
.num_pairs () == nrange
);
2921 // Inverting it should produce one more sub-range.
2923 ASSERT_TRUE (big
.num_pairs () == nrange
+ 1);
2925 int_range
<1> tmp (INT (5), INT (37));
2926 big
.intersect (tmp
);
2927 ASSERT_TRUE (big
.num_pairs () == 4);
2929 // Test that [10,10][20,20] does NOT contain 15.
2931 int_range_max
i1 (build_int_cst (integer_type_node
, 10),
2932 build_int_cst (integer_type_node
, 10));
2933 int_range_max
i2 (build_int_cst (integer_type_node
, 20),
2934 build_int_cst (integer_type_node
, 20));
2936 ASSERT_FALSE (i1
.contains_p (build_int_cst (integer_type_node
, 15)));
2941 range_tests_legacy ()
2943 // Test truncating copy to int_range<1>.
2944 int_range
<3> big
= build_range3 (10, 20, 30, 40, 50, 60);
2945 int_range
<1> small
= big
;
2946 ASSERT_TRUE (small
== int_range
<1> (INT (10), INT (60)));
2948 // Test truncating copy to int_range<2>.
2949 int_range
<2> medium
= big
;
2950 ASSERT_TRUE (!medium
.undefined_p ());
2952 // Test that a truncating copy of [MIN,20][22,40][80,MAX]
2953 // ends up as a conservative anti-range of ~[21,21].
2954 big
= int_range
<3> (vrp_val_min (integer_type_node
), INT (20));
2955 big
.union_ (int_range
<1> (INT (22), INT (40)));
2956 big
.union_ (int_range
<1> (INT (80), vrp_val_max (integer_type_node
)));
2958 ASSERT_TRUE (small
== int_range
<1> (INT (21), INT (21), VR_ANTI_RANGE
));
2960 // Copying a legacy symbolic to an int_range should normalize the
2961 // symbolic at copy time.
2963 tree ssa
= make_ssa_name (integer_type_node
);
2964 value_range
legacy_range (ssa
, INT (25));
2965 int_range
<2> copy
= legacy_range
;
2966 ASSERT_TRUE (copy
== int_range
<2> (vrp_val_min (integer_type_node
),
2969 // Test that copying ~[abc_23, abc_23] to a multi-range yields varying.
2970 legacy_range
= value_range (ssa
, ssa
, VR_ANTI_RANGE
);
2971 copy
= legacy_range
;
2972 ASSERT_TRUE (copy
.varying_p ());
2975 // VARYING of different sizes should not be equal.
2976 tree big_type
= build_nonstandard_integer_type (32, 1);
2977 tree small_type
= build_nonstandard_integer_type (16, 1);
2978 int_range_max
r0 (big_type
);
2979 int_range_max
r1 (small_type
);
2980 ASSERT_TRUE (r0
!= r1
);
2981 value_range
vr0 (big_type
);
2982 int_range_max
vr1 (small_type
);
2983 ASSERT_TRUE (vr0
!= vr1
);
2986 // Simulate -fstrict-enums where the domain of a type is less than the
2990 range_tests_strict_enum ()
2992 // The enum can only hold [0, 3].
2993 tree rtype
= copy_node (unsigned_type_node
);
2994 TYPE_MIN_VALUE (rtype
) = build_int_cstu (rtype
, 0);
2995 TYPE_MAX_VALUE (rtype
) = build_int_cstu (rtype
, 3);
2997 // Test that even though vr1 covers the strict enum domain ([0, 3]),
2998 // it does not cover the domain of the underlying type.
2999 int_range
<1> vr1 (build_int_cstu (rtype
, 0), build_int_cstu (rtype
, 1));
3000 int_range
<1> vr2 (build_int_cstu (rtype
, 2), build_int_cstu (rtype
, 3));
3002 ASSERT_TRUE (vr1
== int_range
<1> (build_int_cstu (rtype
, 0),
3003 build_int_cstu (rtype
, 3)));
3004 ASSERT_FALSE (vr1
.varying_p ());
3006 // Test that copying to a multi-range does not change things.
3007 int_range
<2> ir1 (vr1
);
3008 ASSERT_TRUE (ir1
== vr1
);
3009 ASSERT_FALSE (ir1
.varying_p ());
3011 // The same test as above, but using TYPE_{MIN,MAX}_VALUE instead of [0,3].
3012 vr1
= int_range
<1> (TYPE_MIN_VALUE (rtype
), TYPE_MAX_VALUE (rtype
));
3014 ASSERT_TRUE (ir1
== vr1
);
3015 ASSERT_FALSE (ir1
.varying_p ());
3021 tree u128_type
= build_nonstandard_integer_type (128, /*unsigned=*/1);
3022 int_range
<1> i1
, i2
, i3
;
3023 int_range
<1> r0
, r1
, rold
;
3025 // Test 1-bit signed integer union.
3026 // [-1,-1] U [0,0] = VARYING.
3027 tree one_bit_type
= build_nonstandard_integer_type (1, 0);
3028 tree one_bit_min
= vrp_val_min (one_bit_type
);
3029 tree one_bit_max
= vrp_val_max (one_bit_type
);
3031 int_range
<2> min (one_bit_min
, one_bit_min
);
3032 int_range
<2> max (one_bit_max
, one_bit_max
);
3034 ASSERT_TRUE (max
.varying_p ());
3037 // Test inversion of 1-bit signed integers.
3039 int_range
<2> min (one_bit_min
, one_bit_min
);
3040 int_range
<2> max (one_bit_max
, one_bit_max
);
3044 ASSERT_TRUE (t
== max
);
3047 ASSERT_TRUE (t
== min
);
3050 // Test that NOT(255) is [0..254] in 8-bit land.
3051 int_range
<1> not_255 (UCHAR (255), UCHAR (255), VR_ANTI_RANGE
);
3052 ASSERT_TRUE (not_255
== int_range
<1> (UCHAR (0), UCHAR (254)));
3054 // Test that NOT(0) is [1..255] in 8-bit land.
3055 int_range
<1> not_zero
= range_nonzero (unsigned_char_type_node
);
3056 ASSERT_TRUE (not_zero
== int_range
<1> (UCHAR (1), UCHAR (255)));
3058 // Check that [0,127][0x..ffffff80,0x..ffffff]
3059 // => ~[128, 0x..ffffff7f].
3060 r0
= int_range
<1> (UINT128 (0), UINT128 (127));
3061 tree high
= build_minus_one_cst (u128_type
);
3062 // low = -1 - 127 => 0x..ffffff80.
3063 tree low
= fold_build2 (MINUS_EXPR
, u128_type
, high
, UINT128(127));
3064 r1
= int_range
<1> (low
, high
); // [0x..ffffff80, 0x..ffffffff]
3065 // r0 = [0,127][0x..ffffff80,0x..fffffff].
3067 // r1 = [128, 0x..ffffff7f].
3068 r1
= int_range
<1> (UINT128(128),
3069 fold_build2 (MINUS_EXPR
, u128_type
,
3070 build_minus_one_cst (u128_type
),
3073 ASSERT_TRUE (r0
== r1
);
3075 r0
.set_varying (integer_type_node
);
3076 tree minint
= wide_int_to_tree (integer_type_node
, r0
.lower_bound ());
3077 tree maxint
= wide_int_to_tree (integer_type_node
, r0
.upper_bound ());
3079 r0
.set_varying (short_integer_type_node
);
3081 r0
.set_varying (unsigned_type_node
);
3082 tree maxuint
= wide_int_to_tree (unsigned_type_node
, r0
.upper_bound ());
3084 // Check that ~[0,5] => [6,MAX] for unsigned int.
3085 r0
= int_range
<1> (UINT (0), UINT (5));
3087 ASSERT_TRUE (r0
== int_range
<1> (UINT(6), maxuint
));
3089 // Check that ~[10,MAX] => [0,9] for unsigned int.
3090 r0
= int_range
<1> (UINT(10), maxuint
);
3092 ASSERT_TRUE (r0
== int_range
<1> (UINT (0), UINT (9)));
3094 // Check that ~[0,5] => [6,MAX] for unsigned 128-bit numbers.
3095 r0
= int_range
<1> (UINT128 (0), UINT128 (5), VR_ANTI_RANGE
);
3096 r1
= int_range
<1> (UINT128(6), build_minus_one_cst (u128_type
));
3097 ASSERT_TRUE (r0
== r1
);
3099 // Check that [~5] is really [-MIN,4][6,MAX].
3100 r0
= int_range
<1> (INT (5), INT (5), VR_ANTI_RANGE
);
3101 r1
= int_range
<1> (minint
, INT (4));
3102 r1
.union_ (int_range
<1> (INT (6), maxint
));
3103 ASSERT_FALSE (r1
.undefined_p ());
3104 ASSERT_TRUE (r0
== r1
);
3106 r1
= int_range
<1> (INT (5), INT (5));
3107 int_range
<1> r2 (r1
);
3108 ASSERT_TRUE (r1
== r2
);
3110 r1
= int_range
<1> (INT (5), INT (10));
3112 r1
= int_range
<1> (integer_type_node
,
3113 wi::to_wide (INT (5)), wi::to_wide (INT (10)));
3114 ASSERT_TRUE (r1
.contains_p (INT (7)));
3116 r1
= int_range
<1> (SCHAR (0), SCHAR (20));
3117 ASSERT_TRUE (r1
.contains_p (SCHAR(15)));
3118 ASSERT_FALSE (r1
.contains_p (SCHAR(300)));
3120 // NOT([10,20]) ==> [-MIN,9][21,MAX].
3121 r0
= r1
= int_range
<1> (INT (10), INT (20));
3122 r2
= int_range
<1> (minint
, INT(9));
3123 r2
.union_ (int_range
<1> (INT(21), maxint
));
3124 ASSERT_FALSE (r2
.undefined_p ());
3126 ASSERT_TRUE (r1
== r2
);
3127 // Test that NOT(NOT(x)) == x.
3129 ASSERT_TRUE (r0
== r2
);
3131 // Test that booleans and their inverse work as expected.
3132 r0
= range_zero (boolean_type_node
);
3133 ASSERT_TRUE (r0
== int_range
<1> (build_zero_cst (boolean_type_node
),
3134 build_zero_cst (boolean_type_node
)));
3136 ASSERT_TRUE (r0
== int_range
<1> (build_one_cst (boolean_type_node
),
3137 build_one_cst (boolean_type_node
)));
3139 // Make sure NULL and non-NULL of pointer types work, and that
3140 // inverses of them are consistent.
3141 tree voidp
= build_pointer_type (void_type_node
);
3142 r0
= range_zero (voidp
);
3146 ASSERT_TRUE (r0
== r1
);
3148 // [10,20] U [15, 30] => [10, 30].
3149 r0
= int_range
<1> (INT (10), INT (20));
3150 r1
= int_range
<1> (INT (15), INT (30));
3152 ASSERT_TRUE (r0
== int_range
<1> (INT (10), INT (30)));
3154 // [15,40] U [] => [15,40].
3155 r0
= int_range
<1> (INT (15), INT (40));
3156 r1
.set_undefined ();
3158 ASSERT_TRUE (r0
== int_range
<1> (INT (15), INT (40)));
3160 // [10,20] U [10,10] => [10,20].
3161 r0
= int_range
<1> (INT (10), INT (20));
3162 r1
= int_range
<1> (INT (10), INT (10));
3164 ASSERT_TRUE (r0
== int_range
<1> (INT (10), INT (20)));
3166 // [10,20] U [9,9] => [9,20].
3167 r0
= int_range
<1> (INT (10), INT (20));
3168 r1
= int_range
<1> (INT (9), INT (9));
3170 ASSERT_TRUE (r0
== int_range
<1> (INT (9), INT (20)));
3172 // [10,20] ^ [15,30] => [15,20].
3173 r0
= int_range
<1> (INT (10), INT (20));
3174 r1
= int_range
<1> (INT (15), INT (30));
3176 ASSERT_TRUE (r0
== int_range
<1> (INT (15), INT (20)));
3178 // Test the internal sanity of wide_int's wrt HWIs.
3179 ASSERT_TRUE (wi::max_value (TYPE_PRECISION (boolean_type_node
),
3180 TYPE_SIGN (boolean_type_node
))
3181 == wi::uhwi (1, TYPE_PRECISION (boolean_type_node
)));
3184 r0
= int_range
<1> (INT (0), INT (0));
3185 ASSERT_TRUE (r0
.zero_p ());
3187 // Test nonzero_p().
3188 r0
= int_range
<1> (INT (0), INT (0));
3190 ASSERT_TRUE (r0
.nonzero_p ());
3192 // test legacy interaction
3194 r0
= int_range
<1> (UINT (1), UINT (1), VR_ANTI_RANGE
);
3196 r1
= int_range
<1> (UINT (3), UINT (3), VR_ANTI_RANGE
);
3198 // vv = [0,0][2,2][4, MAX]
3199 int_range
<3> vv
= r0
;
3202 ASSERT_TRUE (vv
.contains_p (UINT (2)));
3203 ASSERT_TRUE (vv
.num_pairs () == 3);
3205 // create r0 as legacy [1,1]
3206 r0
= int_range
<1> (UINT (1), UINT (1));
3207 // And union it with [0,0][2,2][4,MAX] multi range
3209 // The result should be [0,2][4,MAX], or ~[3,3] but it must contain 2
3210 ASSERT_TRUE (r0
.contains_p (UINT (2)));
3214 range_tests_nonzero_bits ()
3216 int_range
<2> r0
, r1
;
3218 // Adding nonzero bits to a varying drops the varying.
3219 r0
.set_varying (integer_type_node
);
3220 r0
.set_nonzero_bits (255);
3221 ASSERT_TRUE (!r0
.varying_p ());
3222 // Dropping the nonzero bits brings us back to varying.
3223 r0
.set_nonzero_bits (-1);
3224 ASSERT_TRUE (r0
.varying_p ());
3226 // Test contains_p with nonzero bits.
3227 r0
.set_zero (integer_type_node
);
3228 ASSERT_TRUE (r0
.contains_p (INT (0)));
3229 ASSERT_FALSE (r0
.contains_p (INT (1)));
3230 r0
.set_nonzero_bits (0xfe);
3231 ASSERT_FALSE (r0
.contains_p (INT (0x100)));
3232 ASSERT_FALSE (r0
.contains_p (INT (0x3)));
3234 // Union of nonzero bits.
3235 r0
.set_varying (integer_type_node
);
3236 r0
.set_nonzero_bits (0xf0);
3237 r1
.set_varying (integer_type_node
);
3238 r1
.set_nonzero_bits (0xf);
3240 ASSERT_TRUE (r0
.get_nonzero_bits () == 0xff);
3242 // Union where the mask of nonzero bits is implicit from the range.
3243 r0
.set_varying (integer_type_node
);
3244 r0
.set_nonzero_bits (0xf00);
3245 r1
.set_zero (integer_type_node
); // nonzero mask is implicitly 0
3247 ASSERT_TRUE (r0
.get_nonzero_bits () == 0xf00);
3249 // Intersect of nonzero bits.
3250 r0
.set (INT (0), INT (255));
3251 r0
.set_nonzero_bits (0xfe);
3252 r1
.set_varying (integer_type_node
);
3253 r1
.set_nonzero_bits (0xf0);
3255 ASSERT_TRUE (r0
.get_nonzero_bits () == 0xf0);
3257 // Intersect where the mask of nonzero bits is implicit from the range.
3258 r0
.set_varying (integer_type_node
);
3259 r1
.set (INT (0), INT (255));
3261 ASSERT_TRUE (r0
.get_nonzero_bits () == 0xff);
3263 // The union of a mask of 0xff..ffff00 with a mask of 0xff spans the
3264 // entire domain, and makes the range a varying.
3265 r0
.set_varying (integer_type_node
);
3266 wide_int x
= wi::shwi (0xff, TYPE_PRECISION (integer_type_node
));
3267 x
= wi::bit_not (x
);
3268 r0
.set_nonzero_bits (x
); // 0xff..ff00
3269 r1
.set_varying (integer_type_node
);
3270 r1
.set_nonzero_bits (0xff);
3272 ASSERT_TRUE (r0
.varying_p ());
3278 range_tests_legacy ();
3279 range_tests_irange3 ();
3280 range_tests_int_range_max ();
3281 range_tests_strict_enum ();
3282 range_tests_nonzero_bits ();
3283 range_tests_misc ();
3286 } // namespace selftest
3288 #endif // CHECKING_P
This page took 0.181759 seconds and 5 git commands to generate.