]>
git.ipfire.org Git - thirdparty/gcc.git/blob - gcc/value-range.cc
1 /* Support routines for value ranges.
2 Copyright (C) 2019-2021 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 "fold-const.h"
31 #include "gimple-range.h"
33 // Here we copy between any two irange's. The ranges can be legacy or
34 // multi-ranges, and copying between any combination works correctly.
37 irange::operator= (const irange
&src
)
44 if (src
.legacy_mode_p ())
46 copy_legacy_to_multi_range (src
);
51 unsigned lim
= src
.m_num_ranges
;
52 if (lim
> m_max_ranges
)
55 for (x
= 0; x
< lim
* 2; ++x
)
56 m_base
[x
] = src
.m_base
[x
];
58 // If the range didn't fit, the last range should cover the rest.
59 if (lim
!= src
.m_num_ranges
)
60 m_base
[x
- 1] = src
.m_base
[src
.m_num_ranges
* 2 - 1];
67 // Return TRUE if range is a multi-range that can be represented as a
71 irange::maybe_anti_range () const
74 unsigned int precision
= TYPE_PRECISION (ttype
);
75 signop sign
= TYPE_SIGN (ttype
);
76 return (num_pairs () > 1
78 && lower_bound () == wi::min_value (precision
, sign
)
79 && upper_bound () == wi::max_value (precision
, sign
));
83 irange::copy_legacy_to_multi_range (const irange
&src
)
85 gcc_checking_assert (src
.legacy_mode_p ());
86 gcc_checking_assert (!legacy_mode_p ());
87 if (src
.undefined_p ())
89 else if (src
.varying_p ())
90 set_varying (src
.type ());
93 if (range_has_numeric_bounds_p (&src
))
94 set (src
.min (), src
.max (), src
.kind ());
97 value_range
cst (src
);
98 cst
.normalize_symbolics ();
99 gcc_checking_assert (cst
.varying_p () || cst
.kind () == VR_RANGE
);
100 set (cst
.min (), cst
.max ());
105 // Copy any type of irange into a legacy.
108 irange::copy_to_legacy (const irange
&src
)
110 gcc_checking_assert (legacy_mode_p ());
111 // Handle legacy to legacy and other things that are easy to copy.
112 if (src
.legacy_mode_p () || src
.varying_p () || src
.undefined_p ())
114 m_num_ranges
= src
.m_num_ranges
;
115 m_base
[0] = src
.m_base
[0];
116 m_base
[1] = src
.m_base
[1];
120 // Copy multi-range to legacy.
121 if (src
.maybe_anti_range ())
123 int_range
<3> r (src
);
125 // Use tree variants to save on tree -> wi -> tree conversions.
126 set (r
.tree_lower_bound (0), r
.tree_upper_bound (0), VR_ANTI_RANGE
);
129 set (src
.tree_lower_bound (), src
.tree_upper_bound ());
132 // Swap MIN/MAX if they are out of order and adjust KIND appropriately.
135 swap_out_of_order_endpoints (tree
&min
, tree
&max
, value_range_kind
&kind
)
137 gcc_checking_assert (kind
!= VR_UNDEFINED
);
138 if (kind
== VR_VARYING
)
140 /* Wrong order for min and max, to swap them and the VR type we need
142 if (tree_int_cst_lt (max
, min
))
146 /* For one bit precision if max < min, then the swapped
147 range covers all values, so for VR_RANGE it is varying and
148 for VR_ANTI_RANGE empty range, so drop to varying as well. */
149 if (TYPE_PRECISION (TREE_TYPE (min
)) == 1)
155 one
= build_int_cst (TREE_TYPE (min
), 1);
156 tmp
= int_const_binop (PLUS_EXPR
, max
, one
);
157 max
= int_const_binop (MINUS_EXPR
, min
, one
);
160 /* There's one corner case, if we had [C+1, C] before we now have
161 that again. But this represents an empty value range, so drop
162 to varying in this case. */
163 if (tree_int_cst_lt (max
, min
))
168 kind
= kind
== VR_RANGE
? VR_ANTI_RANGE
: VR_RANGE
;
173 irange::irange_set (tree min
, tree max
)
175 gcc_checking_assert (!POLY_INT_CST_P (min
));
176 gcc_checking_assert (!POLY_INT_CST_P (max
));
189 irange::irange_set_1bit_anti_range (tree min
, tree max
)
191 tree type
= TREE_TYPE (min
);
192 gcc_checking_assert (TYPE_PRECISION (type
) == 1);
194 if (operand_equal_p (min
, max
))
196 // Since these are 1-bit quantities, they can only be [MIN,MIN]
198 if (vrp_val_is_min (min
))
199 min
= max
= vrp_val_max (type
);
201 min
= max
= vrp_val_min (type
);
206 // The only alternative is [MIN,MAX], which is the empty range.
207 gcc_checking_assert (vrp_val_is_min (min
));
208 gcc_checking_assert (vrp_val_is_max (max
));
216 irange::irange_set_anti_range (tree min
, tree max
)
218 gcc_checking_assert (!POLY_INT_CST_P (min
));
219 gcc_checking_assert (!POLY_INT_CST_P (max
));
221 if (TYPE_PRECISION (TREE_TYPE (min
)) == 1)
223 irange_set_1bit_anti_range (min
, max
);
228 tree type
= TREE_TYPE (min
);
229 signop sign
= TYPE_SIGN (type
);
230 int_range
<2> type_range (type
);
231 // Calculate INVERSE([I,J]) as [-MIN, I-1][J+1, +MAX].
233 wi::overflow_type ovf
;
235 wide_int w_min
= wi::to_wide (min
);
236 if (wi::ne_p (w_min
, type_range
.lower_bound ()))
238 wide_int lim1
= wi::sub (w_min
, 1, sign
, &ovf
);
239 gcc_checking_assert (ovf
!= wi::OVF_OVERFLOW
);
240 m_base
[0] = type_range
.tree_lower_bound (0);
241 m_base
[1] = wide_int_to_tree (type
, lim1
);
244 wide_int w_max
= wi::to_wide (max
);
245 if (wi::ne_p (w_max
, type_range
.upper_bound ()))
247 wide_int lim2
= wi::add (w_max
, 1, sign
, &ovf
);
248 gcc_checking_assert (ovf
!= wi::OVF_OVERFLOW
);
249 m_base
[m_num_ranges
* 2] = wide_int_to_tree (type
, lim2
);
250 m_base
[m_num_ranges
* 2 + 1] = type_range
.tree_upper_bound (0);
261 /* Set value range to the canonical form of {VRTYPE, MIN, MAX, EQUIV}.
262 This means adjusting VRTYPE, MIN and MAX representing the case of a
263 wrapping range with MAX < MIN covering [MIN, type_max] U [type_min, MAX]
264 as anti-rage ~[MAX+1, MIN-1]. Likewise for wrapping anti-ranges.
265 In corner cases where MAX+1 or MIN-1 wraps this will fall back
267 This routine exists to ease canonicalization in the case where we
268 extract ranges from var + CST op limit. */
271 irange::set (tree min
, tree max
, value_range_kind kind
)
273 if (!legacy_mode_p ())
275 if (kind
== VR_RANGE
)
276 irange_set (min
, max
);
279 gcc_checking_assert (kind
== VR_ANTI_RANGE
);
280 irange_set_anti_range (min
, max
);
284 if (kind
== VR_UNDEFINED
)
290 if (kind
== VR_VARYING
291 || POLY_INT_CST_P (min
)
292 || POLY_INT_CST_P (max
))
294 set_varying (TREE_TYPE (min
));
298 // Nothing to canonicalize for symbolic ranges.
299 if (TREE_CODE (min
) != INTEGER_CST
300 || TREE_CODE (max
) != INTEGER_CST
)
309 swap_out_of_order_endpoints (min
, max
, kind
);
310 if (kind
== VR_VARYING
)
312 set_varying (TREE_TYPE (min
));
316 // Anti-ranges that can be represented as ranges should be so.
317 if (kind
== VR_ANTI_RANGE
)
319 bool is_min
= vrp_val_is_min (min
);
320 bool is_max
= vrp_val_is_max (max
);
322 if (is_min
&& is_max
)
324 // Fall through. This will either be normalized as
325 // VR_UNDEFINED if the anti-range spans the entire
326 // precision, or it will remain an VR_ANTI_RANGE in the case
327 // of an -fstrict-enum where [MIN,MAX] is less than the span
328 // of underlying precision.
330 else if (TYPE_PRECISION (TREE_TYPE (min
)) == 1)
332 irange_set_1bit_anti_range (min
, max
);
337 tree one
= build_int_cst (TREE_TYPE (max
), 1);
338 min
= int_const_binop (PLUS_EXPR
, max
, one
);
339 max
= vrp_val_max (TREE_TYPE (max
));
344 tree one
= build_int_cst (TREE_TYPE (min
), 1);
345 max
= int_const_binop (MINUS_EXPR
, min
, one
);
346 min
= vrp_val_min (TREE_TYPE (min
));
360 // Check the validity of the range.
363 irange::verify_range ()
365 if (m_kind
== VR_UNDEFINED
)
367 gcc_checking_assert (m_num_ranges
== 0);
370 if (m_kind
== VR_VARYING
)
372 gcc_checking_assert (m_num_ranges
== 1);
373 gcc_checking_assert (varying_compatible_p ());
376 if (!legacy_mode_p ())
378 gcc_checking_assert (m_num_ranges
!= 0);
379 gcc_checking_assert (!varying_compatible_p ());
380 for (unsigned i
= 0; i
< m_num_ranges
; ++i
)
382 tree lb
= tree_lower_bound (i
);
383 tree ub
= tree_upper_bound (i
);
384 int c
= compare_values (lb
, ub
);
385 gcc_checking_assert (c
== 0 || c
== -1);
389 if (m_kind
== VR_RANGE
|| m_kind
== VR_ANTI_RANGE
)
391 gcc_checking_assert (m_num_ranges
== 1);
392 int cmp
= compare_values (tree_lower_bound (0), tree_upper_bound (0));
393 gcc_checking_assert (cmp
== 0 || cmp
== -1 || cmp
== -2);
397 // Return the lower bound for a sub-range. PAIR is the sub-range in
401 irange::legacy_lower_bound (unsigned pair
) const
403 gcc_checking_assert (legacy_mode_p ());
406 value_range
numeric_range (*this);
407 numeric_range
.normalize_symbolics ();
408 return numeric_range
.legacy_lower_bound (pair
);
410 gcc_checking_assert (m_num_ranges
> 0);
411 gcc_checking_assert (pair
+ 1 <= num_pairs ());
412 if (m_kind
== VR_ANTI_RANGE
)
414 tree typ
= type (), t
;
415 if (pair
== 1 || vrp_val_is_min (min ()))
416 t
= wide_int_to_tree (typ
, wi::to_wide (max ()) + 1);
418 t
= vrp_val_min (typ
);
419 return wi::to_wide (t
);
421 return wi::to_wide (tree_lower_bound (pair
));
424 // Return the upper bound for a sub-range. PAIR is the sub-range in
428 irange::legacy_upper_bound (unsigned pair
) const
430 gcc_checking_assert (legacy_mode_p ());
433 value_range
numeric_range (*this);
434 numeric_range
.normalize_symbolics ();
435 return numeric_range
.legacy_upper_bound (pair
);
437 gcc_checking_assert (m_num_ranges
> 0);
438 gcc_checking_assert (pair
+ 1 <= num_pairs ());
439 if (m_kind
== VR_ANTI_RANGE
)
441 tree typ
= type (), t
;
442 if (pair
== 1 || vrp_val_is_min (min ()))
443 t
= vrp_val_max (typ
);
445 t
= wide_int_to_tree (typ
, wi::to_wide (min ()) - 1);
446 return wi::to_wide (t
);
448 return wi::to_wide (tree_upper_bound (pair
));
452 irange::legacy_equal_p (const irange
&other
) const
454 gcc_checking_assert (legacy_mode_p () && other
.legacy_mode_p ());
456 if (m_kind
!= other
.m_kind
)
458 if (m_kind
== VR_UNDEFINED
)
460 if (m_kind
== VR_VARYING
)
461 return range_compatible_p (type (), other
.type ());
462 return (vrp_operand_equal_p (tree_lower_bound (0),
463 other
.tree_lower_bound (0))
464 && vrp_operand_equal_p (tree_upper_bound (0),
465 other
.tree_upper_bound (0)));
469 irange::equal_p (const irange
&other
) const
471 if (legacy_mode_p ())
473 if (other
.legacy_mode_p ())
474 return legacy_equal_p (other
);
475 value_range
tmp (other
);
476 return legacy_equal_p (tmp
);
478 if (other
.legacy_mode_p ())
480 value_range
tmp2 (*this);
481 return tmp2
.legacy_equal_p (other
);
484 if (m_num_ranges
!= other
.m_num_ranges
)
487 for (unsigned i
= 0; i
< m_num_ranges
; ++i
)
489 tree lb
= tree_lower_bound (i
);
490 tree ub
= tree_upper_bound (i
);
491 tree lb_other
= other
.tree_lower_bound (i
);
492 tree ub_other
= other
.tree_upper_bound (i
);
493 if (!operand_equal_p (lb
, lb_other
, 0)
494 || !operand_equal_p (ub
, ub_other
, 0))
500 /* Return TRUE if this is a symbolic range. */
503 irange::symbolic_p () const
505 return (m_num_ranges
> 0
506 && (!is_gimple_min_invariant (min ())
507 || !is_gimple_min_invariant (max ())));
510 /* Return TRUE if this is a constant range. */
513 irange::constant_p () const
515 return (m_num_ranges
> 0
516 && TREE_CODE (min ()) == INTEGER_CST
517 && TREE_CODE (max ()) == INTEGER_CST
);
520 /* If range is a singleton, place it in RESULT and return TRUE.
521 Note: A singleton can be any gimple invariant, not just constants.
522 So, [&x, &x] counts as a singleton. */
525 irange::singleton_p (tree
*result
) const
527 if (!legacy_mode_p ())
529 if (num_pairs () == 1 && (wi::to_wide (tree_lower_bound ())
530 == wi::to_wide (tree_upper_bound ())))
533 *result
= tree_lower_bound ();
538 if (m_kind
== VR_ANTI_RANGE
)
542 if (TYPE_PRECISION (type ()) == 1)
550 if (num_pairs () == 1)
552 value_range vr0
, vr1
;
553 ranges_from_anti_range ((const value_range
*) this, &vr0
, &vr1
);
554 return vr0
.singleton_p (result
);
557 // Catches non-numeric extremes as well.
558 if (m_kind
== VR_RANGE
559 && vrp_operand_equal_p (min (), max ())
560 && is_gimple_min_invariant (min ()))
569 /* Return 1 if VAL is inside value range.
570 0 if VAL is not inside value range.
571 -2 if we cannot tell either way.
573 Benchmark compile/20001226-1.c compilation time after changing this
577 irange::value_inside_range (tree val
) const
585 if (!legacy_mode_p () && TREE_CODE (val
) == INTEGER_CST
)
586 return contains_p (val
);
588 int cmp1
= operand_less_p (val
, min ());
592 return m_kind
!= VR_RANGE
;
594 int cmp2
= operand_less_p (max (), val
);
598 if (m_kind
== VR_RANGE
)
604 /* Return TRUE if it is possible that range contains VAL. */
607 irange::may_contain_p (tree val
) const
609 return value_inside_range (val
) != 0;
612 /* Return TRUE if range contains INTEGER_CST. */
613 /* Return 1 if VAL is inside value range.
614 0 if VAL is not inside value range.
616 Benchmark compile/20001226-1.c compilation time after changing this
621 irange::contains_p (tree cst
) const
626 if (legacy_mode_p ())
628 gcc_checking_assert (TREE_CODE (cst
) == INTEGER_CST
);
631 value_range
numeric_range (*this);
632 numeric_range
.normalize_symbolics ();
633 return numeric_range
.contains_p (cst
);
635 return value_inside_range (cst
) == 1;
638 gcc_checking_assert (TREE_CODE (cst
) == INTEGER_CST
);
639 signop sign
= TYPE_SIGN (TREE_TYPE (cst
));
640 wide_int v
= wi::to_wide (cst
);
641 for (unsigned r
= 0; r
< m_num_ranges
; ++r
)
643 if (wi::lt_p (v
, lower_bound (r
), sign
))
645 if (wi::le_p (v
, upper_bound (r
), sign
))
653 /* Normalize addresses into constants. */
656 irange::normalize_addresses ()
661 if (!POINTER_TYPE_P (type ()) || range_has_numeric_bounds_p (this))
664 if (!range_includes_zero_p (this))
666 gcc_checking_assert (TREE_CODE (min ()) == ADDR_EXPR
667 || TREE_CODE (max ()) == ADDR_EXPR
);
668 set_nonzero (type ());
671 set_varying (type ());
674 /* Normalize symbolics and addresses into constants. */
677 irange::normalize_symbolics ()
679 if (varying_p () || undefined_p ())
682 tree ttype
= type ();
683 bool min_symbolic
= !is_gimple_min_invariant (min ());
684 bool max_symbolic
= !is_gimple_min_invariant (max ());
685 if (!min_symbolic
&& !max_symbolic
)
687 normalize_addresses ();
691 // [SYM, SYM] -> VARYING
692 if (min_symbolic
&& max_symbolic
)
697 if (kind () == VR_RANGE
)
699 // [SYM, NUM] -> [-MIN, NUM]
702 set (vrp_val_min (ttype
), max ());
705 // [NUM, SYM] -> [NUM, +MAX]
706 set (min (), vrp_val_max (ttype
));
709 gcc_checking_assert (kind () == VR_ANTI_RANGE
);
710 // ~[SYM, NUM] -> [NUM + 1, +MAX]
713 if (!vrp_val_is_max (max ()))
715 tree n
= wide_int_to_tree (ttype
, wi::to_wide (max ()) + 1);
716 set (n
, vrp_val_max (ttype
));
722 // ~[NUM, SYM] -> [-MIN, NUM - 1]
723 if (!vrp_val_is_min (min ()))
725 tree n
= wide_int_to_tree (ttype
, wi::to_wide (min ()) - 1);
726 set (vrp_val_min (ttype
), n
);
732 /* Intersect the two value-ranges { *VR0TYPE, *VR0MIN, *VR0MAX } and
733 { VR1TYPE, VR0MIN, VR0MAX } and store the result
734 in { *VR0TYPE, *VR0MIN, *VR0MAX }. This may not be the smallest
735 possible such range. The resulting range is not canonicalized. */
738 intersect_ranges (enum value_range_kind
*vr0type
,
739 tree
*vr0min
, tree
*vr0max
,
740 enum value_range_kind vr1type
,
741 tree vr1min
, tree vr1max
)
743 bool mineq
= vrp_operand_equal_p (*vr0min
, vr1min
);
744 bool maxeq
= vrp_operand_equal_p (*vr0max
, vr1max
);
746 /* [] is vr0, () is vr1 in the following classification comments. */
750 if (*vr0type
== vr1type
)
751 /* Nothing to do for equal ranges. */
753 else if ((*vr0type
== VR_RANGE
754 && vr1type
== VR_ANTI_RANGE
)
755 || (*vr0type
== VR_ANTI_RANGE
756 && vr1type
== VR_RANGE
))
758 /* For anti-range with range intersection the result is empty. */
759 *vr0type
= VR_UNDEFINED
;
766 else if (operand_less_p (*vr0max
, vr1min
) == 1
767 || operand_less_p (vr1max
, *vr0min
) == 1)
769 /* [ ] ( ) or ( ) [ ]
770 If the ranges have an empty intersection, the result of the
771 intersect operation is the range for intersecting an
772 anti-range with a range or empty when intersecting two ranges. */
773 if (*vr0type
== VR_RANGE
774 && vr1type
== VR_ANTI_RANGE
)
776 else if (*vr0type
== VR_ANTI_RANGE
777 && vr1type
== VR_RANGE
)
783 else if (*vr0type
== VR_RANGE
784 && vr1type
== VR_RANGE
)
786 *vr0type
= VR_UNDEFINED
;
790 else if (*vr0type
== VR_ANTI_RANGE
791 && vr1type
== VR_ANTI_RANGE
)
793 /* If the anti-ranges are adjacent to each other merge them. */
794 if (TREE_CODE (*vr0max
) == INTEGER_CST
795 && TREE_CODE (vr1min
) == INTEGER_CST
796 && operand_less_p (*vr0max
, vr1min
) == 1
797 && integer_onep (int_const_binop (MINUS_EXPR
,
800 else if (TREE_CODE (vr1max
) == INTEGER_CST
801 && TREE_CODE (*vr0min
) == INTEGER_CST
802 && operand_less_p (vr1max
, *vr0min
) == 1
803 && integer_onep (int_const_binop (MINUS_EXPR
,
806 /* Else arbitrarily take VR0. */
809 else if ((maxeq
|| operand_less_p (vr1max
, *vr0max
) == 1)
810 && (mineq
|| operand_less_p (*vr0min
, vr1min
) == 1))
812 /* [ ( ) ] or [( ) ] or [ ( )] */
813 if (*vr0type
== VR_RANGE
814 && vr1type
== VR_RANGE
)
816 /* If both are ranges the result is the inner one. */
821 else if (*vr0type
== VR_RANGE
822 && vr1type
== VR_ANTI_RANGE
)
824 /* Choose the right gap if the left one is empty. */
827 if (TREE_CODE (vr1max
) != INTEGER_CST
)
829 else if (TYPE_PRECISION (TREE_TYPE (vr1max
)) == 1
830 && !TYPE_UNSIGNED (TREE_TYPE (vr1max
)))
832 = int_const_binop (MINUS_EXPR
, vr1max
,
833 build_int_cst (TREE_TYPE (vr1max
), -1));
836 = int_const_binop (PLUS_EXPR
, vr1max
,
837 build_int_cst (TREE_TYPE (vr1max
), 1));
839 /* Choose the left gap if the right one is empty. */
842 if (TREE_CODE (vr1min
) != INTEGER_CST
)
844 else if (TYPE_PRECISION (TREE_TYPE (vr1min
)) == 1
845 && !TYPE_UNSIGNED (TREE_TYPE (vr1min
)))
847 = int_const_binop (PLUS_EXPR
, vr1min
,
848 build_int_cst (TREE_TYPE (vr1min
), -1));
851 = int_const_binop (MINUS_EXPR
, vr1min
,
852 build_int_cst (TREE_TYPE (vr1min
), 1));
854 /* Choose the anti-range if the range is effectively varying. */
855 else if (vrp_val_is_min (*vr0min
)
856 && vrp_val_is_max (*vr0max
))
862 /* Else choose the range. */
864 else if (*vr0type
== VR_ANTI_RANGE
865 && vr1type
== VR_ANTI_RANGE
)
866 /* If both are anti-ranges the result is the outer one. */
868 else if (*vr0type
== VR_ANTI_RANGE
869 && vr1type
== VR_RANGE
)
871 /* The intersection is empty. */
872 *vr0type
= VR_UNDEFINED
;
879 else if ((maxeq
|| operand_less_p (*vr0max
, vr1max
) == 1)
880 && (mineq
|| operand_less_p (vr1min
, *vr0min
) == 1))
882 /* ( [ ] ) or ([ ] ) or ( [ ]) */
883 if (*vr0type
== VR_RANGE
884 && vr1type
== VR_RANGE
)
885 /* Choose the inner range. */
887 else if (*vr0type
== VR_ANTI_RANGE
888 && vr1type
== VR_RANGE
)
890 /* Choose the right gap if the left is empty. */
894 if (TREE_CODE (*vr0max
) != INTEGER_CST
)
896 else if (TYPE_PRECISION (TREE_TYPE (*vr0max
)) == 1
897 && !TYPE_UNSIGNED (TREE_TYPE (*vr0max
)))
899 = int_const_binop (MINUS_EXPR
, *vr0max
,
900 build_int_cst (TREE_TYPE (*vr0max
), -1));
903 = int_const_binop (PLUS_EXPR
, *vr0max
,
904 build_int_cst (TREE_TYPE (*vr0max
), 1));
907 /* Choose the left gap if the right is empty. */
911 if (TREE_CODE (*vr0min
) != INTEGER_CST
)
913 else if (TYPE_PRECISION (TREE_TYPE (*vr0min
)) == 1
914 && !TYPE_UNSIGNED (TREE_TYPE (*vr0min
)))
916 = int_const_binop (PLUS_EXPR
, *vr0min
,
917 build_int_cst (TREE_TYPE (*vr0min
), -1));
920 = int_const_binop (MINUS_EXPR
, *vr0min
,
921 build_int_cst (TREE_TYPE (*vr0min
), 1));
924 /* Choose the anti-range if the range is effectively varying. */
925 else if (vrp_val_is_min (vr1min
)
926 && vrp_val_is_max (vr1max
))
928 /* Choose the anti-range if it is ~[0,0], that range is special
929 enough to special case when vr1's range is relatively wide.
930 At least for types bigger than int - this covers pointers
931 and arguments to functions like ctz. */
932 else if (*vr0min
== *vr0max
933 && integer_zerop (*vr0min
)
934 && ((TYPE_PRECISION (TREE_TYPE (*vr0min
))
935 >= TYPE_PRECISION (integer_type_node
))
936 || POINTER_TYPE_P (TREE_TYPE (*vr0min
)))
937 && TREE_CODE (vr1max
) == INTEGER_CST
938 && TREE_CODE (vr1min
) == INTEGER_CST
939 && (wi::clz (wi::to_wide (vr1max
) - wi::to_wide (vr1min
))
940 < TYPE_PRECISION (TREE_TYPE (*vr0min
)) / 2))
942 /* Else choose the range. */
950 else if (*vr0type
== VR_ANTI_RANGE
951 && vr1type
== VR_ANTI_RANGE
)
953 /* If both are anti-ranges the result is the outer one. */
958 else if (vr1type
== VR_ANTI_RANGE
959 && *vr0type
== VR_RANGE
)
961 /* The intersection is empty. */
962 *vr0type
= VR_UNDEFINED
;
969 else if ((operand_less_p (vr1min
, *vr0max
) == 1
970 || operand_equal_p (vr1min
, *vr0max
, 0))
971 && operand_less_p (*vr0min
, vr1min
) == 1
972 && operand_less_p (*vr0max
, vr1max
) == 1)
974 /* [ ( ] ) or [ ]( ) */
975 if (*vr0type
== VR_ANTI_RANGE
976 && vr1type
== VR_ANTI_RANGE
)
978 else if (*vr0type
== VR_RANGE
979 && vr1type
== VR_RANGE
)
981 else if (*vr0type
== VR_RANGE
982 && vr1type
== VR_ANTI_RANGE
)
984 if (TREE_CODE (vr1min
) == INTEGER_CST
)
985 *vr0max
= int_const_binop (MINUS_EXPR
, vr1min
,
986 build_int_cst (TREE_TYPE (vr1min
), 1));
990 else if (*vr0type
== VR_ANTI_RANGE
991 && vr1type
== VR_RANGE
)
994 if (TREE_CODE (*vr0max
) == INTEGER_CST
)
995 *vr0min
= int_const_binop (PLUS_EXPR
, *vr0max
,
996 build_int_cst (TREE_TYPE (*vr0max
), 1));
1004 else if ((operand_less_p (*vr0min
, vr1max
) == 1
1005 || operand_equal_p (*vr0min
, vr1max
, 0))
1006 && operand_less_p (vr1min
, *vr0min
) == 1
1007 && operand_less_p (vr1max
, *vr0max
) == 1)
1009 /* ( [ ) ] or ( )[ ] */
1010 if (*vr0type
== VR_ANTI_RANGE
1011 && vr1type
== VR_ANTI_RANGE
)
1013 else if (*vr0type
== VR_RANGE
1014 && vr1type
== VR_RANGE
)
1016 else if (*vr0type
== VR_RANGE
1017 && vr1type
== VR_ANTI_RANGE
)
1019 if (TREE_CODE (vr1max
) == INTEGER_CST
)
1020 *vr0min
= int_const_binop (PLUS_EXPR
, vr1max
,
1021 build_int_cst (TREE_TYPE (vr1max
), 1));
1025 else if (*vr0type
== VR_ANTI_RANGE
1026 && vr1type
== VR_RANGE
)
1028 *vr0type
= VR_RANGE
;
1029 if (TREE_CODE (*vr0min
) == INTEGER_CST
)
1030 *vr0max
= int_const_binop (MINUS_EXPR
, *vr0min
,
1031 build_int_cst (TREE_TYPE (*vr0min
), 1));
1040 /* If we know the intersection is empty, there's no need to
1041 conservatively add anything else to the set. */
1042 if (*vr0type
== VR_UNDEFINED
)
1045 /* As a fallback simply use { *VRTYPE, *VR0MIN, *VR0MAX } as
1046 result for the intersection. That's always a conservative
1047 correct estimate unless VR1 is a constant singleton range
1048 in which case we choose that. */
1049 if (vr1type
== VR_RANGE
1050 && is_gimple_min_invariant (vr1min
)
1051 && vrp_operand_equal_p (vr1min
, vr1max
))
1059 /* Helper for the intersection operation for value ranges. Given two
1060 ranges VR0 and VR1, set VR0 to the intersection of both ranges.
1061 This may not be the smallest possible such range. */
1064 irange::legacy_intersect (irange
*vr0
, const irange
*vr1
)
1066 gcc_checking_assert (vr0
->legacy_mode_p ());
1067 gcc_checking_assert (vr1
->legacy_mode_p ());
1068 /* If either range is VR_VARYING the other one wins. */
1069 if (vr1
->varying_p ())
1071 if (vr0
->varying_p ())
1073 vr0
->set (vr1
->min (), vr1
->max (), vr1
->kind ());
1077 /* When either range is VR_UNDEFINED the resulting range is
1078 VR_UNDEFINED, too. */
1079 if (vr0
->undefined_p ())
1081 if (vr1
->undefined_p ())
1083 vr0
->set_undefined ();
1087 value_range_kind vr0kind
= vr0
->kind ();
1088 tree vr0min
= vr0
->min ();
1089 tree vr0max
= vr0
->max ();
1091 intersect_ranges (&vr0kind
, &vr0min
, &vr0max
,
1092 vr1
->kind (), vr1
->min (), vr1
->max ());
1094 /* Make sure to canonicalize the result though as the inversion of a
1095 VR_RANGE can still be a VR_RANGE. */
1096 if (vr0kind
== VR_UNDEFINED
)
1097 vr0
->set_undefined ();
1098 else if (vr0kind
== VR_VARYING
)
1100 /* If we failed, use the original VR0. */
1104 vr0
->set (vr0min
, vr0max
, vr0kind
);
1107 /* Union the two value-ranges { *VR0TYPE, *VR0MIN, *VR0MAX } and
1108 { VR1TYPE, VR0MIN, VR0MAX } and store the result
1109 in { *VR0TYPE, *VR0MIN, *VR0MAX }. This may not be the smallest
1110 possible such range. The resulting range is not canonicalized. */
1113 union_ranges (enum value_range_kind
*vr0type
,
1114 tree
*vr0min
, tree
*vr0max
,
1115 enum value_range_kind vr1type
,
1116 tree vr1min
, tree vr1max
)
1118 int cmpmin
= compare_values (*vr0min
, vr1min
);
1119 int cmpmax
= compare_values (*vr0max
, vr1max
);
1120 bool mineq
= cmpmin
== 0;
1121 bool maxeq
= cmpmax
== 0;
1123 /* [] is vr0, () is vr1 in the following classification comments. */
1127 if (*vr0type
== vr1type
)
1128 /* Nothing to do for equal ranges. */
1130 else if ((*vr0type
== VR_RANGE
1131 && vr1type
== VR_ANTI_RANGE
)
1132 || (*vr0type
== VR_ANTI_RANGE
1133 && vr1type
== VR_RANGE
))
1135 /* For anti-range with range union the result is varying. */
1141 else if (operand_less_p (*vr0max
, vr1min
) == 1
1142 || operand_less_p (vr1max
, *vr0min
) == 1)
1144 /* [ ] ( ) or ( ) [ ]
1145 If the ranges have an empty intersection, result of the union
1146 operation is the anti-range or if both are anti-ranges
1148 if (*vr0type
== VR_ANTI_RANGE
1149 && vr1type
== VR_ANTI_RANGE
)
1151 else if (*vr0type
== VR_ANTI_RANGE
1152 && vr1type
== VR_RANGE
)
1154 else if (*vr0type
== VR_RANGE
1155 && vr1type
== VR_ANTI_RANGE
)
1161 else if (*vr0type
== VR_RANGE
1162 && vr1type
== VR_RANGE
)
1164 /* The result is the convex hull of both ranges. */
1165 if (operand_less_p (*vr0max
, vr1min
) == 1)
1167 /* If the result can be an anti-range, create one. */
1168 if (TREE_CODE (*vr0max
) == INTEGER_CST
1169 && TREE_CODE (vr1min
) == INTEGER_CST
1170 && vrp_val_is_min (*vr0min
)
1171 && vrp_val_is_max (vr1max
))
1173 tree min
= int_const_binop (PLUS_EXPR
,
1175 build_int_cst (TREE_TYPE (*vr0max
), 1));
1176 tree max
= int_const_binop (MINUS_EXPR
,
1178 build_int_cst (TREE_TYPE (vr1min
), 1));
1179 if (!operand_less_p (max
, min
))
1181 *vr0type
= VR_ANTI_RANGE
;
1193 /* If the result can be an anti-range, create one. */
1194 if (TREE_CODE (vr1max
) == INTEGER_CST
1195 && TREE_CODE (*vr0min
) == INTEGER_CST
1196 && vrp_val_is_min (vr1min
)
1197 && vrp_val_is_max (*vr0max
))
1199 tree min
= int_const_binop (PLUS_EXPR
,
1201 build_int_cst (TREE_TYPE (vr1max
), 1));
1202 tree max
= int_const_binop (MINUS_EXPR
,
1204 build_int_cst (TREE_TYPE (*vr0min
), 1));
1205 if (!operand_less_p (max
, min
))
1207 *vr0type
= VR_ANTI_RANGE
;
1221 else if ((maxeq
|| cmpmax
== 1)
1222 && (mineq
|| cmpmin
== -1))
1224 /* [ ( ) ] or [( ) ] or [ ( )] */
1225 if (*vr0type
== VR_RANGE
1226 && vr1type
== VR_RANGE
)
1228 else if (*vr0type
== VR_ANTI_RANGE
1229 && vr1type
== VR_ANTI_RANGE
)
1235 else if (*vr0type
== VR_ANTI_RANGE
1236 && vr1type
== VR_RANGE
)
1238 /* Arbitrarily choose the right or left gap. */
1239 if (!mineq
&& TREE_CODE (vr1min
) == INTEGER_CST
)
1240 *vr0max
= int_const_binop (MINUS_EXPR
, vr1min
,
1241 build_int_cst (TREE_TYPE (vr1min
), 1));
1242 else if (!maxeq
&& TREE_CODE (vr1max
) == INTEGER_CST
)
1243 *vr0min
= int_const_binop (PLUS_EXPR
, vr1max
,
1244 build_int_cst (TREE_TYPE (vr1max
), 1));
1248 else if (*vr0type
== VR_RANGE
1249 && vr1type
== VR_ANTI_RANGE
)
1250 /* The result covers everything. */
1255 else if ((maxeq
|| cmpmax
== -1)
1256 && (mineq
|| cmpmin
== 1))
1258 /* ( [ ] ) or ([ ] ) or ( [ ]) */
1259 if (*vr0type
== VR_RANGE
1260 && vr1type
== VR_RANGE
)
1266 else if (*vr0type
== VR_ANTI_RANGE
1267 && vr1type
== VR_ANTI_RANGE
)
1269 else if (*vr0type
== VR_RANGE
1270 && vr1type
== VR_ANTI_RANGE
)
1272 *vr0type
= VR_ANTI_RANGE
;
1273 if (!mineq
&& TREE_CODE (*vr0min
) == INTEGER_CST
)
1275 *vr0max
= int_const_binop (MINUS_EXPR
, *vr0min
,
1276 build_int_cst (TREE_TYPE (*vr0min
), 1));
1279 else if (!maxeq
&& TREE_CODE (*vr0max
) == INTEGER_CST
)
1281 *vr0min
= int_const_binop (PLUS_EXPR
, *vr0max
,
1282 build_int_cst (TREE_TYPE (*vr0max
), 1));
1288 else if (*vr0type
== VR_ANTI_RANGE
1289 && vr1type
== VR_RANGE
)
1290 /* The result covers everything. */
1295 else if (cmpmin
== -1
1297 && (operand_less_p (vr1min
, *vr0max
) == 1
1298 || operand_equal_p (vr1min
, *vr0max
, 0)))
1300 /* [ ( ] ) or [ ]( ) */
1301 if (*vr0type
== VR_RANGE
1302 && vr1type
== VR_RANGE
)
1304 else if (*vr0type
== VR_ANTI_RANGE
1305 && vr1type
== VR_ANTI_RANGE
)
1307 else if (*vr0type
== VR_ANTI_RANGE
1308 && vr1type
== VR_RANGE
)
1310 if (TREE_CODE (vr1min
) == INTEGER_CST
)
1311 *vr0max
= int_const_binop (MINUS_EXPR
, vr1min
,
1312 build_int_cst (TREE_TYPE (vr1min
), 1));
1316 else if (*vr0type
== VR_RANGE
1317 && vr1type
== VR_ANTI_RANGE
)
1319 if (TREE_CODE (*vr0max
) == INTEGER_CST
)
1322 *vr0min
= int_const_binop (PLUS_EXPR
, *vr0max
,
1323 build_int_cst (TREE_TYPE (*vr0max
), 1));
1332 else if (cmpmin
== 1
1334 && (operand_less_p (*vr0min
, vr1max
) == 1
1335 || operand_equal_p (*vr0min
, vr1max
, 0)))
1337 /* ( [ ) ] or ( )[ ] */
1338 if (*vr0type
== VR_RANGE
1339 && vr1type
== VR_RANGE
)
1341 else if (*vr0type
== VR_ANTI_RANGE
1342 && vr1type
== VR_ANTI_RANGE
)
1344 else if (*vr0type
== VR_ANTI_RANGE
1345 && vr1type
== VR_RANGE
)
1347 if (TREE_CODE (vr1max
) == INTEGER_CST
)
1348 *vr0min
= int_const_binop (PLUS_EXPR
, vr1max
,
1349 build_int_cst (TREE_TYPE (vr1max
), 1));
1353 else if (*vr0type
== VR_RANGE
1354 && vr1type
== VR_ANTI_RANGE
)
1356 if (TREE_CODE (*vr0min
) == INTEGER_CST
)
1359 *vr0max
= int_const_binop (MINUS_EXPR
, *vr0min
,
1360 build_int_cst (TREE_TYPE (*vr0min
), 1));
1375 *vr0type
= VR_VARYING
;
1376 *vr0min
= NULL_TREE
;
1377 *vr0max
= NULL_TREE
;
1380 /* Helper for meet operation for value ranges. Given two ranges VR0
1381 and VR1, set VR0 to the union of both ranges. This may not be the
1382 smallest possible such range. */
1385 irange::legacy_union (irange
*vr0
, const irange
*vr1
)
1387 gcc_checking_assert (vr0
->legacy_mode_p ());
1388 gcc_checking_assert (vr1
->legacy_mode_p ());
1390 /* VR0 has the resulting range if VR1 is undefined or VR0 is varying. */
1391 if (vr1
->undefined_p ()
1392 || vr0
->varying_p ())
1395 /* VR1 has the resulting range if VR0 is undefined or VR1 is varying. */
1396 if (vr0
->undefined_p ())
1398 vr0
->set (vr1
->min (), vr1
->max (), vr1
->kind ());
1402 if (vr1
->varying_p ())
1404 vr0
->set_varying (vr1
->type ());
1408 value_range_kind vr0kind
= vr0
->kind ();
1409 tree vr0min
= vr0
->min ();
1410 tree vr0max
= vr0
->max ();
1412 union_ranges (&vr0kind
, &vr0min
, &vr0max
,
1413 vr1
->kind (), vr1
->min (), vr1
->max ());
1415 if (vr0kind
== VR_UNDEFINED
)
1416 vr0
->set_undefined ();
1417 else if (vr0kind
== VR_VARYING
)
1419 /* Failed to find an efficient meet. Before giving up and
1420 setting the result to VARYING, see if we can at least derive
1421 a non-zero range. */
1422 if (range_includes_zero_p (vr0
) == 0
1423 && range_includes_zero_p (vr1
) == 0)
1424 vr0
->set_nonzero (vr0
->type ());
1426 vr0
->set_varying (vr0
->type ());
1429 vr0
->set (vr0min
, vr0max
, vr0kind
);
1432 /* Meet operation for value ranges. Given two value ranges VR0 and
1433 VR1, store in VR0 a range that contains both VR0 and VR1. This
1434 may not be the smallest possible such range. */
1437 irange::union_ (const irange
*other
)
1439 if (legacy_mode_p ())
1441 if (!other
->legacy_mode_p ())
1443 int_range
<1> tmp
= *other
;
1444 legacy_union (this, &tmp
);
1447 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1449 fprintf (dump_file
, "Meeting\n ");
1450 dump_value_range (dump_file
, this);
1451 fprintf (dump_file
, "\nand\n ");
1452 dump_value_range (dump_file
, other
);
1453 fprintf (dump_file
, "\n");
1456 legacy_union (this, other
);
1458 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1460 fprintf (dump_file
, "to\n ");
1461 dump_value_range (dump_file
, this);
1462 fprintf (dump_file
, "\n");
1467 if (other
->legacy_mode_p ())
1469 int_range
<2> wider
= *other
;
1470 irange_union (wider
);
1473 irange_union (*other
);
1477 irange::intersect (const irange
*other
)
1479 if (legacy_mode_p ())
1481 if (!other
->legacy_mode_p ())
1483 int_range
<1> tmp
= *other
;
1484 legacy_intersect (this, &tmp
);
1487 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1489 fprintf (dump_file
, "Intersecting\n ");
1490 dump_value_range (dump_file
, this);
1491 fprintf (dump_file
, "\nand\n ");
1492 dump_value_range (dump_file
, other
);
1493 fprintf (dump_file
, "\n");
1496 legacy_intersect (this, other
);
1498 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1500 fprintf (dump_file
, "to\n ");
1501 dump_value_range (dump_file
, this);
1502 fprintf (dump_file
, "\n");
1507 if (other
->legacy_mode_p ())
1511 irange_intersect (wider
);
1514 irange_intersect (*other
);
1517 // union_ for multi-ranges.
1520 irange::irange_union (const irange
&r
)
1522 gcc_checking_assert (!legacy_mode_p () && !r
.legacy_mode_p ());
1524 if (r
.undefined_p () || varying_p ())
1527 if (undefined_p () || r
.varying_p ())
1533 // Do not worry about merging and such by reserving twice as many
1534 // pairs as needed, and then simply sort the 2 ranges into this
1535 // intermediate form.
1537 // The intermediate result will have the property that the beginning
1538 // of each range is <= the beginning of the next range. There may
1539 // be overlapping ranges at this point. I.e. this would be valid
1540 // [-20, 10], [-10, 0], [0, 20], [40, 90] as it satisfies this
1541 // contraint : -20 < -10 < 0 < 40. When the range is rebuilt into r,
1542 // the merge is performed.
1544 // [Xi,Yi]..[Xn,Yn] U [Xj,Yj]..[Xm,Ym] --> [Xk,Yk]..[Xp,Yp]
1545 tree ttype
= r
.type ();
1546 signop sign
= TYPE_SIGN (ttype
);
1548 auto_vec
<tree
, 20> res
;
1550 wi::overflow_type ovf
;
1551 unsigned i
= 0, j
= 0, k
= 0;
1553 while (i
< m_num_ranges
* 2 && j
< r
.m_num_ranges
* 2)
1555 // lower of Xi and Xj is the lowest point.
1556 if (wi::le_p (wi::to_wide (m_base
[i
]), wi::to_wide (r
.m_base
[j
]), sign
))
1558 res
.safe_push (m_base
[i
]);
1559 res
.safe_push (m_base
[i
+ 1]);
1565 res
.safe_push (r
.m_base
[j
]);
1566 res
.safe_push (r
.m_base
[j
+ 1]);
1571 for ( ; i
< m_num_ranges
* 2; i
+= 2)
1573 res
.safe_push (m_base
[i
]);
1574 res
.safe_push (m_base
[i
+ 1]);
1577 for ( ; j
< r
.m_num_ranges
* 2; j
+= 2)
1579 res
.safe_push (r
.m_base
[j
]);
1580 res
.safe_push (r
.m_base
[j
+ 1]);
1584 // Now normalize the vector removing any overlaps.
1586 int prec
= TYPE_PRECISION (ttype
);
1587 wide_int max_val
= wi::max_value (prec
, sign
);
1588 for (j
= 2; j
< k
; j
+= 2)
1590 wide_int val_im1
= wi::to_wide (res
[i
- 1]);
1591 if (val_im1
== max_val
)
1593 u1
= wi::add (val_im1
, 1, sign
, &ovf
);
1595 // Overflow indicates we are at MAX already.
1596 // A wide int bug requires the previous max_val check
1597 // trigger: gcc.c-torture/compile/pr80443.c with -O3
1598 if (ovf
== wi::OVF_OVERFLOW
)
1601 wide_int val_j
= wi::to_wide (res
[j
]);
1602 wide_int val_jp1
= wi::to_wide (res
[j
+1]);
1603 // Current upper+1 is >= lower bound next pair, then we merge ranges.
1604 if (wi::ge_p (u1
, val_j
, sign
))
1606 // New upper bounds is greater of current or the next one.
1607 if (wi::gt_p (val_jp1
, val_im1
, sign
))
1608 res
[i
- 1] = res
[j
+ 1];
1612 // This is a new distinct range, but no point in copying it
1613 // if it is already in the right place.
1617 res
[i
++] = res
[j
+ 1];
1624 // At this point, the vector should have i ranges, none overlapping.
1625 // Now it simply needs to be copied, and if there are too many
1626 // ranges, merge some. We wont do any analysis as to what the
1627 // "best" merges are, simply combine the final ranges into one.
1628 if (i
> m_max_ranges
* 2)
1630 res
[m_max_ranges
* 2 - 1] = res
[i
- 1];
1631 i
= m_max_ranges
* 2;
1634 for (j
= 0; j
< i
; j
++)
1635 m_base
[j
] = res
[j
];
1636 m_num_ranges
= i
/ 2;
1645 // intersect for multi-ranges.
1648 irange::irange_intersect (const irange
&r
)
1650 gcc_checking_assert (!legacy_mode_p () && !r
.legacy_mode_p ());
1652 if (undefined_p () || r
.varying_p ())
1654 if (r
.undefined_p ())
1665 signop sign
= TYPE_SIGN (TREE_TYPE(m_base
[0]));
1666 unsigned bld_pair
= 0;
1667 unsigned bld_lim
= m_max_ranges
;
1668 int_range_max
r2 (*this);
1669 unsigned r2_lim
= r2
.num_pairs ();
1671 for (unsigned i
= 0; i
< r
.num_pairs (); )
1673 // If r1's upper is < r2's lower, we can skip r1's pair.
1674 tree ru
= r
.m_base
[i
* 2 + 1];
1675 tree r2l
= r2
.m_base
[i2
* 2];
1676 if (wi::lt_p (wi::to_wide (ru
), wi::to_wide (r2l
), sign
))
1681 // Likewise, skip r2's pair if its excluded.
1682 tree r2u
= r2
.m_base
[i2
* 2 + 1];
1683 tree rl
= r
.m_base
[i
* 2];
1684 if (wi::lt_p (wi::to_wide (r2u
), wi::to_wide (rl
), sign
))
1689 // No more r2, break.
1693 // Must be some overlap. Find the highest of the lower bounds,
1694 // and set it, unless the build limits lower bounds is already
1696 if (bld_pair
< bld_lim
)
1698 if (wi::ge_p (wi::to_wide (rl
), wi::to_wide (r2l
), sign
))
1699 m_base
[bld_pair
* 2] = rl
;
1701 m_base
[bld_pair
* 2] = r2l
;
1704 // Decrease and set a new upper.
1707 // ...and choose the lower of the upper bounds.
1708 if (wi::le_p (wi::to_wide (ru
), wi::to_wide (r2u
), sign
))
1710 m_base
[bld_pair
* 2 + 1] = ru
;
1712 // Move past the r1 pair and keep trying.
1718 m_base
[bld_pair
* 2 + 1] = r2u
;
1723 // No more r2, break.
1726 // r2 has the higher lower bound.
1729 // At the exit of this loop, it is one of 2 things:
1730 // ran out of r1, or r2, but either means we are done.
1731 m_num_ranges
= bld_pair
;
1740 // Signed 1-bits are strange. You can't subtract 1, because you can't
1741 // represent the number 1. This works around that for the invert routine.
1743 static wide_int
inline
1744 subtract_one (const wide_int
&x
, tree type
, wi::overflow_type
&overflow
)
1746 if (TYPE_SIGN (type
) == SIGNED
)
1747 return wi::add (x
, -1, SIGNED
, &overflow
);
1749 return wi::sub (x
, 1, UNSIGNED
, &overflow
);
1752 // The analogous function for adding 1.
1754 static wide_int
inline
1755 add_one (const wide_int
&x
, tree type
, wi::overflow_type
&overflow
)
1757 if (TYPE_SIGN (type
) == SIGNED
)
1758 return wi::sub (x
, -1, SIGNED
, &overflow
);
1760 return wi::add (x
, 1, UNSIGNED
, &overflow
);
1763 // Return the inverse of a range.
1768 if (legacy_mode_p ())
1770 // We can't just invert VR_RANGE and VR_ANTI_RANGE because we may
1771 // create non-canonical ranges. Use the constructors instead.
1772 if (m_kind
== VR_RANGE
)
1773 *this = value_range (min (), max (), VR_ANTI_RANGE
);
1774 else if (m_kind
== VR_ANTI_RANGE
)
1775 *this = value_range (min (), max ());
1781 gcc_checking_assert (!undefined_p () && !varying_p ());
1783 // We always need one more set of bounds to represent an inverse, so
1784 // if we're at the limit, we can't properly represent things.
1786 // For instance, to represent the inverse of a 2 sub-range set
1787 // [5, 10][20, 30], we would need a 3 sub-range set
1788 // [-MIN, 4][11, 19][31, MAX].
1790 // In this case, return the most conservative thing.
1792 // However, if any of the extremes of the range are -MIN/+MAX, we
1793 // know we will not need an extra bound. For example:
1795 // INVERT([-MIN,20][30,40]) => [21,29][41,+MAX]
1796 // INVERT([-MIN,20][30,MAX]) => [21,29]
1797 tree ttype
= type ();
1798 unsigned prec
= TYPE_PRECISION (ttype
);
1799 signop sign
= TYPE_SIGN (ttype
);
1800 wide_int type_min
= wi::min_value (prec
, sign
);
1801 wide_int type_max
= wi::max_value (prec
, sign
);
1802 if (m_num_ranges
== m_max_ranges
1803 && lower_bound () != type_min
1804 && upper_bound () != type_max
)
1806 m_base
[1] = wide_int_to_tree (ttype
, type_max
);
1810 // The algorithm is as follows. To calculate INVERT ([a,b][c,d]), we
1811 // generate [-MIN, a-1][b+1, c-1][d+1, MAX].
1813 // If there is an over/underflow in the calculation for any
1814 // sub-range, we eliminate that subrange. This allows us to easily
1815 // calculate INVERT([-MIN, 5]) with: [-MIN, -MIN-1][6, MAX]. And since
1816 // we eliminate the underflow, only [6, MAX] remains.
1818 wi::overflow_type ovf
;
1819 // Construct leftmost range.
1820 int_range_max
orig_range (*this);
1821 unsigned nitems
= 0;
1823 // If this is going to underflow on the MINUS 1, don't even bother
1824 // checking. This also handles subtracting one from an unsigned 0,
1825 // which doesn't set the underflow bit.
1826 if (type_min
!= orig_range
.lower_bound ())
1828 m_base
[nitems
++] = wide_int_to_tree (ttype
, type_min
);
1829 tmp
= subtract_one (orig_range
.lower_bound (), ttype
, ovf
);
1830 m_base
[nitems
++] = wide_int_to_tree (ttype
, tmp
);
1835 // Construct middle ranges if applicable.
1836 if (orig_range
.num_pairs () > 1)
1839 for (; j
< (orig_range
.num_pairs () * 2) - 1; j
+= 2)
1841 // The middle ranges cannot have MAX/MIN, so there's no need
1842 // to check for unsigned overflow on the +1 and -1 here.
1843 tmp
= wi::add (wi::to_wide (orig_range
.m_base
[j
]), 1, sign
, &ovf
);
1844 m_base
[nitems
++] = wide_int_to_tree (ttype
, tmp
);
1845 tmp
= subtract_one (wi::to_wide (orig_range
.m_base
[j
+ 1]),
1847 m_base
[nitems
++] = wide_int_to_tree (ttype
, tmp
);
1853 // Construct rightmost range.
1855 // However, if this will overflow on the PLUS 1, don't even bother.
1856 // This also handles adding one to an unsigned MAX, which doesn't
1857 // set the overflow bit.
1858 if (type_max
!= wi::to_wide (orig_range
.m_base
[i
]))
1860 tmp
= add_one (wi::to_wide (orig_range
.m_base
[i
]), ttype
, ovf
);
1861 m_base
[nitems
++] = wide_int_to_tree (ttype
, tmp
);
1862 m_base
[nitems
++] = wide_int_to_tree (ttype
, type_max
);
1866 m_num_ranges
= nitems
/ 2;
1868 // We disallow undefined or varying coming in, so the result can
1869 // only be a VR_RANGE.
1870 gcc_checking_assert (m_kind
== VR_RANGE
);
1877 dump_bound_with_infinite_markers (FILE *file
, tree bound
)
1879 tree type
= TREE_TYPE (bound
);
1880 wide_int type_min
= wi::min_value (TYPE_PRECISION (type
), TYPE_SIGN (type
));
1881 wide_int type_max
= wi::max_value (TYPE_PRECISION (type
), TYPE_SIGN (type
));
1883 if (INTEGRAL_TYPE_P (type
)
1884 && !TYPE_UNSIGNED (type
)
1885 && TREE_CODE (bound
) == INTEGER_CST
1886 && wi::to_wide (bound
) == type_min
1887 && TYPE_PRECISION (type
) != 1)
1888 fprintf (file
, "-INF");
1889 else if (TREE_CODE (bound
) == INTEGER_CST
1890 && wi::to_wide (bound
) == type_max
1891 && TYPE_PRECISION (type
) != 1)
1892 fprintf (file
, "+INF");
1894 print_generic_expr (file
, bound
);
1898 irange::dump (FILE *file
) const
1902 fprintf (file
, "UNDEFINED");
1905 print_generic_expr (file
, type ());
1906 fprintf (file
, " ");
1909 fprintf (file
, "VARYING");
1912 if (legacy_mode_p ())
1914 fprintf (file
, "%s[", (m_kind
== VR_ANTI_RANGE
) ? "~" : "");
1915 dump_bound_with_infinite_markers (file
, min ());
1916 fprintf (file
, ", ");
1917 dump_bound_with_infinite_markers (file
, max ());
1918 fprintf (file
, "]");
1921 for (unsigned i
= 0; i
< m_num_ranges
; ++i
)
1923 tree lb
= m_base
[i
* 2];
1924 tree ub
= m_base
[i
* 2 + 1];
1925 fprintf (file
, "[");
1926 dump_bound_with_infinite_markers (file
, lb
);
1927 fprintf (file
, ", ");
1928 dump_bound_with_infinite_markers (file
, ub
);
1929 fprintf (file
, "]");
1934 dump_value_range (FILE *file
, const irange
*vr
)
1940 debug (const irange
*vr
)
1942 dump_value_range (stderr
, vr
);
1943 fprintf (stderr
, "\n");
1947 debug (const irange
&vr
)
1953 debug (const value_range
*vr
)
1955 dump_value_range (stderr
, vr
);
1956 fprintf (stderr
, "\n");
1960 debug (const value_range
&vr
)
1962 dump_value_range (stderr
, &vr
);
1963 fprintf (stderr
, "\n");
1966 /* Create two value-ranges in *VR0 and *VR1 from the anti-range *AR
1967 so that *VR0 U *VR1 == *AR. Returns true if that is possible,
1968 false otherwise. If *AR can be represented with a single range
1969 *VR1 will be VR_UNDEFINED. */
1972 ranges_from_anti_range (const value_range
*ar
,
1973 value_range
*vr0
, value_range
*vr1
)
1975 tree type
= ar
->type ();
1977 vr0
->set_undefined ();
1978 vr1
->set_undefined ();
1980 /* As a future improvement, we could handle ~[0, A] as: [-INF, -1] U
1981 [A+1, +INF]. Not sure if this helps in practice, though. */
1983 if (ar
->kind () != VR_ANTI_RANGE
1984 || TREE_CODE (ar
->min ()) != INTEGER_CST
1985 || TREE_CODE (ar
->max ()) != INTEGER_CST
1986 || !vrp_val_min (type
)
1987 || !vrp_val_max (type
))
1990 if (tree_int_cst_lt (vrp_val_min (type
), ar
->min ()))
1991 vr0
->set (vrp_val_min (type
),
1992 wide_int_to_tree (type
, wi::to_wide (ar
->min ()) - 1));
1993 if (tree_int_cst_lt (ar
->max (), vrp_val_max (type
)))
1994 vr1
->set (wide_int_to_tree (type
, wi::to_wide (ar
->max ()) + 1),
1995 vrp_val_max (type
));
1996 if (vr0
->undefined_p ())
1999 vr1
->set_undefined ();
2002 return !vr0
->undefined_p ();
2006 range_has_numeric_bounds_p (const irange
*vr
)
2008 return (!vr
->undefined_p ()
2009 && TREE_CODE (vr
->min ()) == INTEGER_CST
2010 && TREE_CODE (vr
->max ()) == INTEGER_CST
);
2013 /* Return whether VAL is equal to the maximum value of its type.
2014 We can't do a simple equality comparison with TYPE_MAX_VALUE because
2015 C typedefs and Ada subtypes can produce types whose TYPE_MAX_VALUE
2016 is not == to the integer constant with the same value in the type. */
2019 vrp_val_is_max (const_tree val
)
2021 tree type_max
= vrp_val_max (TREE_TYPE (val
));
2022 return (val
== type_max
2023 || (type_max
!= NULL_TREE
2024 && operand_equal_p (val
, type_max
, 0)));
2027 /* Return whether VAL is equal to the minimum value of its type. */
2030 vrp_val_is_min (const_tree val
)
2032 tree type_min
= vrp_val_min (TREE_TYPE (val
));
2033 return (val
== type_min
2034 || (type_min
!= NULL_TREE
2035 && operand_equal_p (val
, type_min
, 0)));
2038 /* Return true, if VAL1 and VAL2 are equal values for VRP purposes. */
2041 vrp_operand_equal_p (const_tree val1
, const_tree val2
)
2045 if (!val1
|| !val2
|| !operand_equal_p (val1
, val2
, 0))
2050 // ?? These stubs are for ipa-prop.c which use a value_range in a
2051 // hash_traits. hash-traits.h defines an extern of gt_ggc_mx (T &)
2052 // instead of picking up the gt_ggc_mx (T *) version.
2054 gt_pch_nx (int_range
<1> *&x
)
2056 return gt_pch_nx ((irange
*) x
);
2060 gt_ggc_mx (int_range
<1> *&x
)
2062 return gt_ggc_mx ((irange
*) x
);
2065 #define DEFINE_INT_RANGE_INSTANCE(N) \
2066 template int_range<N>::int_range(tree, tree, value_range_kind); \
2067 template int_range<N>::int_range(tree_node *, \
2070 value_range_kind); \
2071 template int_range<N>::int_range(tree); \
2072 template int_range<N>::int_range(const irange &); \
2073 template int_range<N>::int_range(const int_range &); \
2074 template int_range<N>& int_range<N>::operator= (const int_range &);
2076 DEFINE_INT_RANGE_INSTANCE(1)
2077 DEFINE_INT_RANGE_INSTANCE(2)
2078 DEFINE_INT_RANGE_INSTANCE(3)
2079 DEFINE_INT_RANGE_INSTANCE(255)
2082 #include "selftest.h"
2086 #define INT(N) build_int_cst (integer_type_node, (N))
2087 #define UINT(N) build_int_cstu (unsigned_type_node, (N))
2088 #define UINT128(N) build_int_cstu (u128_type, (N))
2089 #define UCHAR(N) build_int_cstu (unsigned_char_type_node, (N))
2090 #define SCHAR(N) build_int_cst (signed_char_type_node, (N))
2093 build_range3 (int a
, int b
, int c
, int d
, int e
, int f
)
2095 int_range
<3> i1 (INT (a
), INT (b
));
2096 int_range
<3> i2 (INT (c
), INT (d
));
2097 int_range
<3> i3 (INT (e
), INT (f
));
2104 range_tests_irange3 ()
2106 typedef int_range
<3> int_range3
;
2107 int_range3 r0
, r1
, r2
;
2108 int_range3 i1
, i2
, i3
;
2110 // ([10,20] U [5,8]) U [1,3] ==> [1,3][5,8][10,20].
2111 r0
= int_range3 (INT (10), INT (20));
2112 r1
= int_range3 (INT (5), INT (8));
2114 r1
= int_range3 (INT (1), INT (3));
2116 ASSERT_TRUE (r0
== build_range3 (1, 3, 5, 8, 10, 20));
2118 // [1,3][5,8][10,20] U [-5,0] => [-5,3][5,8][10,20].
2119 r1
= int_range3 (INT (-5), INT (0));
2121 ASSERT_TRUE (r0
== build_range3 (-5, 3, 5, 8, 10, 20));
2123 // [10,20][30,40] U [50,60] ==> [10,20][30,40][50,60].
2124 r1
= int_range3 (INT (50), INT (60));
2125 r0
= int_range3 (INT (10), INT (20));
2126 r0
.union_ (int_range3 (INT (30), INT (40)));
2128 ASSERT_TRUE (r0
== build_range3 (10, 20, 30, 40, 50, 60));
2129 // [10,20][30,40][50,60] U [70, 80] ==> [10,20][30,40][50,60][70,80].
2130 r1
= int_range3 (INT (70), INT (80));
2133 r2
= build_range3 (10, 20, 30, 40, 50, 60);
2134 r2
.union_ (int_range3 (INT (70), INT (80)));
2135 ASSERT_TRUE (r0
== r2
);
2137 // [10,20][30,40][50,60] U [6,35] => [6,40][50,60].
2138 r0
= build_range3 (10, 20, 30, 40, 50, 60);
2139 r1
= int_range3 (INT (6), INT (35));
2141 r1
= int_range3 (INT (6), INT (40));
2142 r1
.union_ (int_range3 (INT (50), INT (60)));
2143 ASSERT_TRUE (r0
== r1
);
2145 // [10,20][30,40][50,60] U [6,60] => [6,60].
2146 r0
= build_range3 (10, 20, 30, 40, 50, 60);
2147 r1
= int_range3 (INT (6), INT (60));
2149 ASSERT_TRUE (r0
== int_range3 (INT (6), INT (60)));
2151 // [10,20][30,40][50,60] U [6,70] => [6,70].
2152 r0
= build_range3 (10, 20, 30, 40, 50, 60);
2153 r1
= int_range3 (INT (6), INT (70));
2155 ASSERT_TRUE (r0
== int_range3 (INT (6), INT (70)));
2157 // [10,20][30,40][50,60] U [35,70] => [10,20][30,70].
2158 r0
= build_range3 (10, 20, 30, 40, 50, 60);
2159 r1
= int_range3 (INT (35), INT (70));
2161 r1
= int_range3 (INT (10), INT (20));
2162 r1
.union_ (int_range3 (INT (30), INT (70)));
2163 ASSERT_TRUE (r0
== r1
);
2165 // [10,20][30,40][50,60] U [15,35] => [10,40][50,60].
2166 r0
= build_range3 (10, 20, 30, 40, 50, 60);
2167 r1
= int_range3 (INT (15), INT (35));
2169 r1
= int_range3 (INT (10), INT (40));
2170 r1
.union_ (int_range3 (INT (50), INT (60)));
2171 ASSERT_TRUE (r0
== r1
);
2173 // [10,20][30,40][50,60] U [35,35] => [10,20][30,40][50,60].
2174 r0
= build_range3 (10, 20, 30, 40, 50, 60);
2175 r1
= int_range3 (INT (35), INT (35));
2177 ASSERT_TRUE (r0
== build_range3 (10, 20, 30, 40, 50, 60));
2181 range_tests_int_range_max ()
2184 unsigned int nrange
;
2186 // Build a huge multi-range range.
2187 for (nrange
= 0; nrange
< 50; ++nrange
)
2189 int_range
<1> tmp (INT (nrange
*10), INT (nrange
*10 + 5));
2192 ASSERT_TRUE (big
.num_pairs () == nrange
);
2194 // Verify that we can copy it without loosing precision.
2195 int_range_max
copy (big
);
2196 ASSERT_TRUE (copy
.num_pairs () == nrange
);
2198 // Inverting it should produce one more sub-range.
2200 ASSERT_TRUE (big
.num_pairs () == nrange
+ 1);
2202 int_range
<1> tmp (INT (5), INT (37));
2203 big
.intersect (tmp
);
2204 ASSERT_TRUE (big
.num_pairs () == 4);
2206 // Test that [10,10][20,20] does NOT contain 15.
2208 int_range_max
i1 (build_int_cst (integer_type_node
, 10),
2209 build_int_cst (integer_type_node
, 10));
2210 int_range_max
i2 (build_int_cst (integer_type_node
, 20),
2211 build_int_cst (integer_type_node
, 20));
2213 ASSERT_FALSE (i1
.contains_p (build_int_cst (integer_type_node
, 15)));
2218 range_tests_legacy ()
2220 // Test truncating copy to int_range<1>.
2221 int_range
<3> big
= build_range3 (10, 20, 30, 40, 50, 60);
2222 int_range
<1> small
= big
;
2223 ASSERT_TRUE (small
== int_range
<1> (INT (10), INT (60)));
2225 // Test truncating copy to int_range<2>.
2226 int_range
<2> medium
= big
;
2227 ASSERT_TRUE (!medium
.undefined_p ());
2229 // Test that a truncating copy of [MIN,20][22,40][80,MAX]
2230 // ends up as a conservative anti-range of ~[21,21].
2231 big
= int_range
<3> (vrp_val_min (integer_type_node
), INT (20));
2232 big
.union_ (int_range
<1> (INT (22), INT (40)));
2233 big
.union_ (int_range
<1> (INT (80), vrp_val_max (integer_type_node
)));
2235 ASSERT_TRUE (small
== int_range
<1> (INT (21), INT (21), VR_ANTI_RANGE
));
2237 // Copying a legacy symbolic to an int_range should normalize the
2238 // symbolic at copy time.
2240 tree ssa
= make_ssa_name (integer_type_node
);
2241 value_range
legacy_range (ssa
, INT (25));
2242 int_range
<2> copy
= legacy_range
;
2243 ASSERT_TRUE (copy
== int_range
<2> (vrp_val_min (integer_type_node
),
2246 // Test that copying ~[abc_23, abc_23] to a multi-range yields varying.
2247 legacy_range
= value_range (ssa
, ssa
, VR_ANTI_RANGE
);
2248 copy
= legacy_range
;
2249 ASSERT_TRUE (copy
.varying_p ());
2252 // VARYING of different sizes should not be equal.
2253 tree big_type
= build_nonstandard_integer_type (32, 1);
2254 tree small_type
= build_nonstandard_integer_type (16, 1);
2255 int_range_max
r0 (big_type
);
2256 int_range_max
r1 (small_type
);
2257 ASSERT_TRUE (r0
!= r1
);
2258 value_range
vr0 (big_type
);
2259 int_range_max
vr1 (small_type
);
2260 ASSERT_TRUE (vr0
!= vr1
);
2263 // Simulate -fstrict-enums where the domain of a type is less than the
2267 range_tests_strict_enum ()
2269 // The enum can only hold [0, 3].
2270 tree rtype
= copy_node (unsigned_type_node
);
2271 TYPE_MIN_VALUE (rtype
) = build_int_cstu (rtype
, 0);
2272 TYPE_MAX_VALUE (rtype
) = build_int_cstu (rtype
, 3);
2274 // Test that even though vr1 covers the strict enum domain ([0, 3]),
2275 // it does not cover the domain of the underlying type.
2276 int_range
<1> vr1 (build_int_cstu (rtype
, 0), build_int_cstu (rtype
, 1));
2277 int_range
<1> vr2 (build_int_cstu (rtype
, 2), build_int_cstu (rtype
, 3));
2279 ASSERT_TRUE (vr1
== int_range
<1> (build_int_cstu (rtype
, 0),
2280 build_int_cstu (rtype
, 3)));
2281 ASSERT_FALSE (vr1
.varying_p ());
2283 // Test that copying to a multi-range does not change things.
2284 int_range
<2> ir1 (vr1
);
2285 ASSERT_TRUE (ir1
== vr1
);
2286 ASSERT_FALSE (ir1
.varying_p ());
2288 // The same test as above, but using TYPE_{MIN,MAX}_VALUE instead of [0,3].
2289 vr1
= int_range
<1> (TYPE_MIN_VALUE (rtype
), TYPE_MAX_VALUE (rtype
));
2291 ASSERT_TRUE (ir1
== vr1
);
2292 ASSERT_FALSE (ir1
.varying_p ());
2298 tree u128_type
= build_nonstandard_integer_type (128, /*unsigned=*/1);
2299 int_range
<1> i1
, i2
, i3
;
2300 int_range
<1> r0
, r1
, rold
;
2302 // Test 1-bit signed integer union.
2303 // [-1,-1] U [0,0] = VARYING.
2304 tree one_bit_type
= build_nonstandard_integer_type (1, 0);
2305 tree one_bit_min
= vrp_val_min (one_bit_type
);
2306 tree one_bit_max
= vrp_val_max (one_bit_type
);
2308 int_range
<2> min (one_bit_min
, one_bit_min
);
2309 int_range
<2> max (one_bit_max
, one_bit_max
);
2311 ASSERT_TRUE (max
.varying_p ());
2314 // Test inversion of 1-bit signed integers.
2316 int_range
<2> min (one_bit_min
, one_bit_min
);
2317 int_range
<2> max (one_bit_max
, one_bit_max
);
2321 ASSERT_TRUE (t
== max
);
2324 ASSERT_TRUE (t
== min
);
2327 // Test that NOT(255) is [0..254] in 8-bit land.
2328 int_range
<1> not_255 (UCHAR (255), UCHAR (255), VR_ANTI_RANGE
);
2329 ASSERT_TRUE (not_255
== int_range
<1> (UCHAR (0), UCHAR (254)));
2331 // Test that NOT(0) is [1..255] in 8-bit land.
2332 int_range
<1> not_zero
= range_nonzero (unsigned_char_type_node
);
2333 ASSERT_TRUE (not_zero
== int_range
<1> (UCHAR (1), UCHAR (255)));
2335 // Check that [0,127][0x..ffffff80,0x..ffffff]
2336 // => ~[128, 0x..ffffff7f].
2337 r0
= int_range
<1> (UINT128 (0), UINT128 (127));
2338 tree high
= build_minus_one_cst (u128_type
);
2339 // low = -1 - 127 => 0x..ffffff80.
2340 tree low
= fold_build2 (MINUS_EXPR
, u128_type
, high
, UINT128(127));
2341 r1
= int_range
<1> (low
, high
); // [0x..ffffff80, 0x..ffffffff]
2342 // r0 = [0,127][0x..ffffff80,0x..fffffff].
2344 // r1 = [128, 0x..ffffff7f].
2345 r1
= int_range
<1> (UINT128(128),
2346 fold_build2 (MINUS_EXPR
, u128_type
,
2347 build_minus_one_cst (u128_type
),
2350 ASSERT_TRUE (r0
== r1
);
2352 r0
.set_varying (integer_type_node
);
2353 tree minint
= wide_int_to_tree (integer_type_node
, r0
.lower_bound ());
2354 tree maxint
= wide_int_to_tree (integer_type_node
, r0
.upper_bound ());
2356 r0
.set_varying (short_integer_type_node
);
2358 r0
.set_varying (unsigned_type_node
);
2359 tree maxuint
= wide_int_to_tree (unsigned_type_node
, r0
.upper_bound ());
2361 // Check that ~[0,5] => [6,MAX] for unsigned int.
2362 r0
= int_range
<1> (UINT (0), UINT (5));
2364 ASSERT_TRUE (r0
== int_range
<1> (UINT(6), maxuint
));
2366 // Check that ~[10,MAX] => [0,9] for unsigned int.
2367 r0
= int_range
<1> (UINT(10), maxuint
);
2369 ASSERT_TRUE (r0
== int_range
<1> (UINT (0), UINT (9)));
2371 // Check that ~[0,5] => [6,MAX] for unsigned 128-bit numbers.
2372 r0
= int_range
<1> (UINT128 (0), UINT128 (5), VR_ANTI_RANGE
);
2373 r1
= int_range
<1> (UINT128(6), build_minus_one_cst (u128_type
));
2374 ASSERT_TRUE (r0
== r1
);
2376 // Check that [~5] is really [-MIN,4][6,MAX].
2377 r0
= int_range
<1> (INT (5), INT (5), VR_ANTI_RANGE
);
2378 r1
= int_range
<1> (minint
, INT (4));
2379 r1
.union_ (int_range
<1> (INT (6), maxint
));
2380 ASSERT_FALSE (r1
.undefined_p ());
2381 ASSERT_TRUE (r0
== r1
);
2383 r1
= int_range
<1> (INT (5), INT (5));
2384 int_range
<1> r2 (r1
);
2385 ASSERT_TRUE (r1
== r2
);
2387 r1
= int_range
<1> (INT (5), INT (10));
2389 r1
= int_range
<1> (integer_type_node
,
2390 wi::to_wide (INT (5)), wi::to_wide (INT (10)));
2391 ASSERT_TRUE (r1
.contains_p (INT (7)));
2393 r1
= int_range
<1> (SCHAR (0), SCHAR (20));
2394 ASSERT_TRUE (r1
.contains_p (SCHAR(15)));
2395 ASSERT_FALSE (r1
.contains_p (SCHAR(300)));
2397 // NOT([10,20]) ==> [-MIN,9][21,MAX].
2398 r0
= r1
= int_range
<1> (INT (10), INT (20));
2399 r2
= int_range
<1> (minint
, INT(9));
2400 r2
.union_ (int_range
<1> (INT(21), maxint
));
2401 ASSERT_FALSE (r2
.undefined_p ());
2403 ASSERT_TRUE (r1
== r2
);
2404 // Test that NOT(NOT(x)) == x.
2406 ASSERT_TRUE (r0
== r2
);
2408 // Test that booleans and their inverse work as expected.
2409 r0
= range_zero (boolean_type_node
);
2410 ASSERT_TRUE (r0
== int_range
<1> (build_zero_cst (boolean_type_node
),
2411 build_zero_cst (boolean_type_node
)));
2413 ASSERT_TRUE (r0
== int_range
<1> (build_one_cst (boolean_type_node
),
2414 build_one_cst (boolean_type_node
)));
2416 // Make sure NULL and non-NULL of pointer types work, and that
2417 // inverses of them are consistent.
2418 tree voidp
= build_pointer_type (void_type_node
);
2419 r0
= range_zero (voidp
);
2423 ASSERT_TRUE (r0
== r1
);
2425 // [10,20] U [15, 30] => [10, 30].
2426 r0
= int_range
<1> (INT (10), INT (20));
2427 r1
= int_range
<1> (INT (15), INT (30));
2429 ASSERT_TRUE (r0
== int_range
<1> (INT (10), INT (30)));
2431 // [15,40] U [] => [15,40].
2432 r0
= int_range
<1> (INT (15), INT (40));
2433 r1
.set_undefined ();
2435 ASSERT_TRUE (r0
== int_range
<1> (INT (15), INT (40)));
2437 // [10,20] U [10,10] => [10,20].
2438 r0
= int_range
<1> (INT (10), INT (20));
2439 r1
= int_range
<1> (INT (10), INT (10));
2441 ASSERT_TRUE (r0
== int_range
<1> (INT (10), INT (20)));
2443 // [10,20] U [9,9] => [9,20].
2444 r0
= int_range
<1> (INT (10), INT (20));
2445 r1
= int_range
<1> (INT (9), INT (9));
2447 ASSERT_TRUE (r0
== int_range
<1> (INT (9), INT (20)));
2449 // [10,20] ^ [15,30] => [15,20].
2450 r0
= int_range
<1> (INT (10), INT (20));
2451 r1
= int_range
<1> (INT (15), INT (30));
2453 ASSERT_TRUE (r0
== int_range
<1> (INT (15), INT (20)));
2455 // Test the internal sanity of wide_int's wrt HWIs.
2456 ASSERT_TRUE (wi::max_value (TYPE_PRECISION (boolean_type_node
),
2457 TYPE_SIGN (boolean_type_node
))
2458 == wi::uhwi (1, TYPE_PRECISION (boolean_type_node
)));
2461 r0
= int_range
<1> (INT (0), INT (0));
2462 ASSERT_TRUE (r0
.zero_p ());
2464 // Test nonzero_p().
2465 r0
= int_range
<1> (INT (0), INT (0));
2467 ASSERT_TRUE (r0
.nonzero_p ());
2469 // test legacy interaction
2471 r0
= int_range
<1> (UINT (1), UINT (1), VR_ANTI_RANGE
);
2473 r1
= int_range
<1> (UINT (3), UINT (3), VR_ANTI_RANGE
);
2475 // vv = [0,0][2,2][4, MAX]
2476 int_range
<3> vv
= r0
;
2479 ASSERT_TRUE (vv
.contains_p (UINT (2)));
2480 ASSERT_TRUE (vv
.num_pairs () == 3);
2482 // create r0 as legacy [1,1]
2483 r0
= int_range
<1> (UINT (1), UINT (1));
2484 // And union it with [0,0][2,2][4,MAX] multi range
2486 // The result should be [0,2][4,MAX], or ~[3,3] but it must contain 2
2487 ASSERT_TRUE (r0
.contains_p (UINT (2)));
2493 range_tests_legacy ();
2494 range_tests_irange3 ();
2495 range_tests_int_range_max ();
2496 range_tests_strict_enum ();
2497 range_tests_misc ();
2500 } // namespace selftest
2502 #endif // CHECKING_P