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"
32 // Here we copy between any two irange's. The ranges can be legacy or
33 // multi-ranges, and copying between any combination works correctly.
36 irange::operator= (const irange
&src
)
43 if (src
.legacy_mode_p ())
45 copy_legacy_to_multi_range (src
);
50 unsigned lim
= src
.m_num_ranges
;
51 if (lim
> m_max_ranges
)
54 for (x
= 0; x
< lim
* 2; ++x
)
55 m_base
[x
] = src
.m_base
[x
];
57 // If the range didn't fit, the last range should cover the rest.
58 if (lim
!= src
.m_num_ranges
)
59 m_base
[x
- 1] = src
.m_base
[src
.m_num_ranges
* 2 - 1];
65 // Return TRUE if range is a multi-range that can be represented as a
69 irange::maybe_anti_range () const
72 unsigned int precision
= TYPE_PRECISION (ttype
);
73 signop sign
= TYPE_SIGN (ttype
);
74 return (num_pairs () > 1
76 && lower_bound () == wi::min_value (precision
, sign
)
77 && upper_bound () == wi::max_value (precision
, sign
));
81 irange::copy_legacy_to_multi_range (const irange
&src
)
83 gcc_checking_assert (src
.legacy_mode_p ());
84 gcc_checking_assert (!legacy_mode_p ());
85 if (src
.undefined_p ())
87 else if (src
.varying_p ())
88 set_varying (src
.type ());
91 if (range_has_numeric_bounds_p (&src
))
92 set (src
.min (), src
.max (), src
.kind ());
95 value_range
cst (src
);
96 cst
.normalize_symbolics ();
97 gcc_checking_assert (cst
.varying_p () || cst
.kind () == VR_RANGE
);
98 set (cst
.min (), cst
.max ());
103 // Copy any type of irange into a legacy.
106 irange::copy_to_legacy (const irange
&src
)
108 gcc_checking_assert (legacy_mode_p ());
109 // Copy legacy to legacy.
110 if (src
.legacy_mode_p ())
112 m_num_ranges
= src
.m_num_ranges
;
113 m_base
[0] = src
.m_base
[0];
114 m_base
[1] = src
.m_base
[1];
118 // Copy multi-range to legacy.
119 if (src
.undefined_p ())
121 else if (src
.varying_p ())
122 set_varying (src
.type ());
123 else if (src
.maybe_anti_range ())
125 int_range
<3> r (src
);
127 // Use tree variants to save on tree -> wi -> tree conversions.
128 set (r
.tree_lower_bound (0), r
.tree_upper_bound (0), VR_ANTI_RANGE
);
131 set (src
.tree_lower_bound (), src
.tree_upper_bound ());
134 // Swap MIN/MAX if they are out of order and adjust KIND appropriately.
137 swap_out_of_order_endpoints (tree
&min
, tree
&max
, value_range_kind
&kind
)
139 gcc_checking_assert (kind
!= VR_UNDEFINED
);
140 if (kind
== VR_VARYING
)
142 /* Wrong order for min and max, to swap them and the VR type we need
144 if (tree_int_cst_lt (max
, min
))
148 /* For one bit precision if max < min, then the swapped
149 range covers all values, so for VR_RANGE it is varying and
150 for VR_ANTI_RANGE empty range, so drop to varying as well. */
151 if (TYPE_PRECISION (TREE_TYPE (min
)) == 1)
157 one
= build_int_cst (TREE_TYPE (min
), 1);
158 tmp
= int_const_binop (PLUS_EXPR
, max
, one
);
159 max
= int_const_binop (MINUS_EXPR
, min
, one
);
162 /* There's one corner case, if we had [C+1, C] before we now have
163 that again. But this represents an empty value range, so drop
164 to varying in this case. */
165 if (tree_int_cst_lt (max
, min
))
170 kind
= kind
== VR_RANGE
? VR_ANTI_RANGE
: VR_RANGE
;
175 irange::irange_set (tree min
, tree max
)
177 gcc_checking_assert (!POLY_INT_CST_P (min
));
178 gcc_checking_assert (!POLY_INT_CST_P (max
));
188 irange::irange_set_anti_range (tree min
, tree max
)
190 gcc_checking_assert (!POLY_INT_CST_P (min
));
191 gcc_checking_assert (!POLY_INT_CST_P (max
));
194 tree type
= TREE_TYPE (min
);
195 signop sign
= TYPE_SIGN (type
);
196 int_range
<2> type_range (type
);
197 // Calculate INVERSE([I,J]) as [-MIN, I-1][J+1, +MAX].
199 wi::overflow_type ovf
;
201 wide_int w_min
= wi::to_wide (min
);
202 if (wi::ne_p (w_min
, type_range
.lower_bound ()))
204 wide_int lim1
= wi::sub (w_min
, 1, sign
, &ovf
);
205 gcc_checking_assert (ovf
!= wi::OVF_OVERFLOW
);
206 m_base
[0] = type_range
.tree_lower_bound (0);
207 m_base
[1] = wide_int_to_tree (type
, lim1
);
210 wide_int w_max
= wi::to_wide (max
);
211 if (wi::ne_p (w_max
, type_range
.upper_bound ()))
213 wide_int lim2
= wi::add (w_max
, 1, sign
, &ovf
);
214 gcc_checking_assert (ovf
!= wi::OVF_OVERFLOW
);
215 m_base
[m_num_ranges
* 2] = wide_int_to_tree (type
, lim2
);
216 m_base
[m_num_ranges
* 2 + 1] = type_range
.tree_upper_bound (0);
223 /* Set value range to the canonical form of {VRTYPE, MIN, MAX, EQUIV}.
224 This means adjusting VRTYPE, MIN and MAX representing the case of a
225 wrapping range with MAX < MIN covering [MIN, type_max] U [type_min, MAX]
226 as anti-rage ~[MAX+1, MIN-1]. Likewise for wrapping anti-ranges.
227 In corner cases where MAX+1 or MIN-1 wraps this will fall back
229 This routine exists to ease canonicalization in the case where we
230 extract ranges from var + CST op limit. */
233 irange::set (tree min
, tree max
, value_range_kind kind
)
235 if (!legacy_mode_p ())
237 if (kind
== VR_RANGE
)
238 irange_set (min
, max
);
241 gcc_checking_assert (kind
== VR_ANTI_RANGE
);
242 irange_set_anti_range (min
, max
);
246 if (kind
== VR_UNDEFINED
)
252 if (kind
== VR_VARYING
253 || POLY_INT_CST_P (min
)
254 || POLY_INT_CST_P (max
))
256 set_varying (TREE_TYPE (min
));
260 // Nothing to canonicalize for symbolic ranges.
261 if (TREE_CODE (min
) != INTEGER_CST
262 || TREE_CODE (max
) != INTEGER_CST
)
271 swap_out_of_order_endpoints (min
, max
, kind
);
272 if (kind
== VR_VARYING
)
274 set_varying (TREE_TYPE (min
));
278 // Anti-ranges that can be represented as ranges should be so.
279 if (kind
== VR_ANTI_RANGE
)
281 /* For -fstrict-enums we may receive out-of-range ranges so consider
282 values < -INF and values > INF as -INF/INF as well. */
283 bool is_min
= vrp_val_is_min (min
);
284 bool is_max
= vrp_val_is_max (max
);
285 tree type
= TREE_TYPE (min
);
287 if (is_min
&& is_max
)
289 /* We cannot deal with empty ranges, drop to varying.
290 ??? This could be VR_UNDEFINED instead. */
294 else if (TYPE_PRECISION (TREE_TYPE (min
)) == 1
295 && (is_min
|| is_max
))
297 /* Non-empty boolean ranges can always be represented
298 as a singleton range. */
300 min
= max
= vrp_val_max (TREE_TYPE (min
));
302 min
= max
= vrp_val_min (TREE_TYPE (min
));
307 tree one
= build_int_cst (TREE_TYPE (max
), 1);
308 min
= int_const_binop (PLUS_EXPR
, max
, one
);
309 max
= vrp_val_max (TREE_TYPE (max
));
314 tree one
= build_int_cst (TREE_TYPE (min
), 1);
315 max
= int_const_binop (MINUS_EXPR
, min
, one
);
316 min
= vrp_val_min (TREE_TYPE (min
));
325 normalize_min_max ();
330 // Check the validity of the range.
333 irange::verify_range ()
335 if (!legacy_mode_p ())
337 gcc_checking_assert (m_kind
== VR_RANGE
);
338 for (unsigned i
= 0; i
< m_num_ranges
; ++i
)
340 tree lb
= tree_lower_bound (i
);
341 tree ub
= tree_upper_bound (i
);
342 int c
= compare_values (lb
, ub
);
343 gcc_assert (c
== 0 || c
== -1);
351 gcc_assert (m_num_ranges
== 0);
355 gcc_assert (m_num_ranges
== 1);
361 gcc_assert (m_num_ranges
== 1);
362 int cmp
= compare_values (tree_lower_bound (0), tree_upper_bound (0));
363 gcc_assert (cmp
== 0 || cmp
== -1 || cmp
== -2);
373 irange::legacy_num_pairs () const
375 gcc_checking_assert (legacy_mode_p ());
381 // Inlined symbolic_p for performance:
382 if (!is_gimple_min_invariant (min ()) || !is_gimple_min_invariant (max ()))
384 value_range
numeric_range (*this);
385 numeric_range
.normalize_symbolics ();
386 return numeric_range
.num_pairs ();
388 if (m_kind
== VR_ANTI_RANGE
)
390 // ~[MIN, X] has one sub-range of [X+1, MAX], and
391 // ~[X, MAX] has one sub-range of [MIN, X-1].
392 if (vrp_val_is_min (min ()) || vrp_val_is_max (max ()))
396 gcc_checking_assert (m_num_ranges
== 1);
400 // Return the lower bound for a sub-range. PAIR is the sub-range in
404 irange::legacy_lower_bound (unsigned pair
) const
406 gcc_checking_assert (legacy_mode_p ());
409 value_range
numeric_range (*this);
410 numeric_range
.normalize_symbolics ();
411 return numeric_range
.legacy_lower_bound (pair
);
413 gcc_checking_assert (!undefined_p ());
414 gcc_checking_assert (pair
+ 1 <= num_pairs ());
415 if (m_kind
== VR_ANTI_RANGE
)
417 tree typ
= type (), t
;
418 if (pair
== 1 || vrp_val_is_min (min ()))
419 t
= wide_int_to_tree (typ
, wi::to_wide (max ()) + 1);
421 t
= vrp_val_min (typ
);
422 return wi::to_wide (t
);
424 return wi::to_wide (tree_lower_bound (pair
));
427 // Return the upper bound for a sub-range. PAIR is the sub-range in
431 irange::legacy_upper_bound (unsigned pair
) const
433 gcc_checking_assert (legacy_mode_p ());
436 value_range
numeric_range (*this);
437 numeric_range
.normalize_symbolics ();
438 return numeric_range
.legacy_upper_bound (pair
);
440 gcc_checking_assert (!undefined_p ());
441 gcc_checking_assert (pair
+ 1 <= num_pairs ());
442 if (m_kind
== VR_ANTI_RANGE
)
444 tree typ
= type (), t
;
445 if (pair
== 1 || vrp_val_is_min (min ()))
446 t
= vrp_val_max (typ
);
448 t
= wide_int_to_tree (typ
, wi::to_wide (min ()) - 1);
449 return wi::to_wide (t
);
451 return wi::to_wide (tree_upper_bound (pair
));
455 irange::legacy_equal_p (const irange
&other
) const
457 gcc_checking_assert (legacy_mode_p () && other
.legacy_mode_p ());
459 if (m_kind
!= other
.m_kind
)
461 if (m_kind
== VR_UNDEFINED
|| m_kind
== VR_VARYING
)
463 return (vrp_operand_equal_p (tree_lower_bound (0),
464 other
.tree_lower_bound (0))
465 && vrp_operand_equal_p (tree_upper_bound (0),
466 other
.tree_upper_bound (0)));
470 irange::equal_p (const irange
&other
) const
472 if (legacy_mode_p ())
474 if (other
.legacy_mode_p ())
475 return legacy_equal_p (other
);
476 value_range
tmp (other
);
477 return legacy_equal_p (tmp
);
479 if (other
.legacy_mode_p ())
481 value_range
tmp2 (*this);
482 return tmp2
.legacy_equal_p (other
);
485 if (m_num_ranges
!= other
.m_num_ranges
)
488 for (unsigned i
= 0; i
< m_num_ranges
; ++i
)
490 tree lb
= tree_lower_bound (i
);
491 tree ub
= tree_upper_bound (i
);
492 tree lb_other
= other
.tree_lower_bound (i
);
493 tree ub_other
= other
.tree_upper_bound (i
);
494 if (!operand_equal_p (lb
, lb_other
, 0)
495 || !operand_equal_p (ub
, ub_other
, 0))
501 /* Return TRUE if this is a symbolic range. */
504 irange::symbolic_p () const
506 return (!varying_p ()
508 && (!is_gimple_min_invariant (min ())
509 || !is_gimple_min_invariant (max ())));
512 /* NOTE: This is not the inverse of symbolic_p because the range
513 could also be varying or undefined. Ideally they should be inverse
514 of each other, with varying only applying to symbolics. Varying of
515 constants would be represented as [-MIN, +MAX]. */
518 irange::constant_p () const
520 return (!varying_p ()
522 && TREE_CODE (min ()) == INTEGER_CST
523 && TREE_CODE (max ()) == INTEGER_CST
);
526 /* If range is a singleton, place it in RESULT and return TRUE.
527 Note: A singleton can be any gimple invariant, not just constants.
528 So, [&x, &x] counts as a singleton. */
531 irange::singleton_p (tree
*result
) const
533 if (!legacy_mode_p ())
535 if (num_pairs () == 1 && (wi::to_wide (tree_lower_bound ())
536 == wi::to_wide (tree_upper_bound ())))
539 *result
= tree_lower_bound ();
544 if (m_kind
== VR_ANTI_RANGE
)
548 if (TYPE_PRECISION (type ()) == 1)
556 if (num_pairs () == 1)
558 value_range vr0
, vr1
;
559 ranges_from_anti_range ((const value_range
*) this, &vr0
, &vr1
);
560 return vr0
.singleton_p (result
);
563 // Catches non-numeric extremes as well.
564 if (m_kind
== VR_RANGE
565 && vrp_operand_equal_p (min (), max ())
566 && is_gimple_min_invariant (min ()))
575 /* Return 1 if VAL is inside value range.
576 0 if VAL is not inside value range.
577 -2 if we cannot tell either way.
579 Benchmark compile/20001226-1.c compilation time after changing this
583 irange::value_inside_range (tree val
) const
591 if (!legacy_mode_p () && TREE_CODE (val
) == INTEGER_CST
)
592 return contains_p (val
);
594 int cmp1
= operand_less_p (val
, min ());
598 return m_kind
!= VR_RANGE
;
600 int cmp2
= operand_less_p (max (), val
);
604 if (m_kind
== VR_RANGE
)
610 /* Return TRUE if it is possible that range contains VAL. */
613 irange::may_contain_p (tree val
) const
615 return value_inside_range (val
) != 0;
618 /* Return TRUE if range contains INTEGER_CST. */
619 /* Return 1 if VAL is inside value range.
620 0 if VAL is not inside value range.
622 Benchmark compile/20001226-1.c compilation time after changing this
627 irange::contains_p (tree cst
) const
632 if (legacy_mode_p ())
634 gcc_checking_assert (TREE_CODE (cst
) == INTEGER_CST
);
637 value_range
numeric_range (*this);
638 numeric_range
.normalize_symbolics ();
639 return numeric_range
.contains_p (cst
);
641 return value_inside_range (cst
) == 1;
644 gcc_checking_assert (TREE_CODE (cst
) == INTEGER_CST
);
645 signop sign
= TYPE_SIGN (TREE_TYPE (cst
));
646 wide_int v
= wi::to_wide (cst
);
647 for (unsigned r
= 0; r
< m_num_ranges
; ++r
)
649 if (wi::lt_p (v
, lower_bound (r
), sign
))
651 if (wi::le_p (v
, upper_bound (r
), sign
))
659 /* Normalize addresses into constants. */
662 irange::normalize_addresses ()
667 if (!POINTER_TYPE_P (type ()) || range_has_numeric_bounds_p (this))
670 if (!range_includes_zero_p (this))
672 gcc_checking_assert (TREE_CODE (min ()) == ADDR_EXPR
673 || TREE_CODE (max ()) == ADDR_EXPR
);
674 set_nonzero (type ());
677 set_varying (type ());
680 /* Normalize symbolics and addresses into constants. */
683 irange::normalize_symbolics ()
685 if (varying_p () || undefined_p ())
688 tree ttype
= type ();
689 bool min_symbolic
= !is_gimple_min_invariant (min ());
690 bool max_symbolic
= !is_gimple_min_invariant (max ());
691 if (!min_symbolic
&& !max_symbolic
)
693 normalize_addresses ();
697 // [SYM, SYM] -> VARYING
698 if (min_symbolic
&& max_symbolic
)
703 if (kind () == VR_RANGE
)
705 // [SYM, NUM] -> [-MIN, NUM]
708 set (vrp_val_min (ttype
), max ());
711 // [NUM, SYM] -> [NUM, +MAX]
712 set (min (), vrp_val_max (ttype
));
715 gcc_checking_assert (kind () == VR_ANTI_RANGE
);
716 // ~[SYM, NUM] -> [NUM + 1, +MAX]
719 if (!vrp_val_is_max (max ()))
721 tree n
= wide_int_to_tree (ttype
, wi::to_wide (max ()) + 1);
722 set (n
, vrp_val_max (ttype
));
728 // ~[NUM, SYM] -> [-MIN, NUM - 1]
729 if (!vrp_val_is_min (min ()))
731 tree n
= wide_int_to_tree (ttype
, wi::to_wide (min ()) - 1);
732 set (vrp_val_min (ttype
), n
);
738 /* Intersect the two value-ranges { *VR0TYPE, *VR0MIN, *VR0MAX } and
739 { VR1TYPE, VR0MIN, VR0MAX } and store the result
740 in { *VR0TYPE, *VR0MIN, *VR0MAX }. This may not be the smallest
741 possible such range. The resulting range is not canonicalized. */
744 intersect_ranges (enum value_range_kind
*vr0type
,
745 tree
*vr0min
, tree
*vr0max
,
746 enum value_range_kind vr1type
,
747 tree vr1min
, tree vr1max
)
749 bool mineq
= vrp_operand_equal_p (*vr0min
, vr1min
);
750 bool maxeq
= vrp_operand_equal_p (*vr0max
, vr1max
);
752 /* [] is vr0, () is vr1 in the following classification comments. */
756 if (*vr0type
== vr1type
)
757 /* Nothing to do for equal ranges. */
759 else if ((*vr0type
== VR_RANGE
760 && vr1type
== VR_ANTI_RANGE
)
761 || (*vr0type
== VR_ANTI_RANGE
762 && vr1type
== VR_RANGE
))
764 /* For anti-range with range intersection the result is empty. */
765 *vr0type
= VR_UNDEFINED
;
772 else if (operand_less_p (*vr0max
, vr1min
) == 1
773 || operand_less_p (vr1max
, *vr0min
) == 1)
775 /* [ ] ( ) or ( ) [ ]
776 If the ranges have an empty intersection, the result of the
777 intersect operation is the range for intersecting an
778 anti-range with a range or empty when intersecting two ranges. */
779 if (*vr0type
== VR_RANGE
780 && vr1type
== VR_ANTI_RANGE
)
782 else if (*vr0type
== VR_ANTI_RANGE
783 && vr1type
== VR_RANGE
)
789 else if (*vr0type
== VR_RANGE
790 && vr1type
== VR_RANGE
)
792 *vr0type
= VR_UNDEFINED
;
796 else if (*vr0type
== VR_ANTI_RANGE
797 && vr1type
== VR_ANTI_RANGE
)
799 /* If the anti-ranges are adjacent to each other merge them. */
800 if (TREE_CODE (*vr0max
) == INTEGER_CST
801 && TREE_CODE (vr1min
) == INTEGER_CST
802 && operand_less_p (*vr0max
, vr1min
) == 1
803 && integer_onep (int_const_binop (MINUS_EXPR
,
806 else if (TREE_CODE (vr1max
) == INTEGER_CST
807 && TREE_CODE (*vr0min
) == INTEGER_CST
808 && operand_less_p (vr1max
, *vr0min
) == 1
809 && integer_onep (int_const_binop (MINUS_EXPR
,
812 /* Else arbitrarily take VR0. */
815 else if ((maxeq
|| operand_less_p (vr1max
, *vr0max
) == 1)
816 && (mineq
|| operand_less_p (*vr0min
, vr1min
) == 1))
818 /* [ ( ) ] or [( ) ] or [ ( )] */
819 if (*vr0type
== VR_RANGE
820 && vr1type
== VR_RANGE
)
822 /* If both are ranges the result is the inner one. */
827 else if (*vr0type
== VR_RANGE
828 && vr1type
== VR_ANTI_RANGE
)
830 /* Choose the right gap if the left one is empty. */
833 if (TREE_CODE (vr1max
) != INTEGER_CST
)
835 else if (TYPE_PRECISION (TREE_TYPE (vr1max
)) == 1
836 && !TYPE_UNSIGNED (TREE_TYPE (vr1max
)))
838 = int_const_binop (MINUS_EXPR
, vr1max
,
839 build_int_cst (TREE_TYPE (vr1max
), -1));
842 = int_const_binop (PLUS_EXPR
, vr1max
,
843 build_int_cst (TREE_TYPE (vr1max
), 1));
845 /* Choose the left gap if the right one is empty. */
848 if (TREE_CODE (vr1min
) != INTEGER_CST
)
850 else if (TYPE_PRECISION (TREE_TYPE (vr1min
)) == 1
851 && !TYPE_UNSIGNED (TREE_TYPE (vr1min
)))
853 = int_const_binop (PLUS_EXPR
, vr1min
,
854 build_int_cst (TREE_TYPE (vr1min
), -1));
857 = int_const_binop (MINUS_EXPR
, vr1min
,
858 build_int_cst (TREE_TYPE (vr1min
), 1));
860 /* Choose the anti-range if the range is effectively varying. */
861 else if (vrp_val_is_min (*vr0min
)
862 && vrp_val_is_max (*vr0max
))
868 /* Else choose the range. */
870 else if (*vr0type
== VR_ANTI_RANGE
871 && vr1type
== VR_ANTI_RANGE
)
872 /* If both are anti-ranges the result is the outer one. */
874 else if (*vr0type
== VR_ANTI_RANGE
875 && vr1type
== VR_RANGE
)
877 /* The intersection is empty. */
878 *vr0type
= VR_UNDEFINED
;
885 else if ((maxeq
|| operand_less_p (*vr0max
, vr1max
) == 1)
886 && (mineq
|| operand_less_p (vr1min
, *vr0min
) == 1))
888 /* ( [ ] ) or ([ ] ) or ( [ ]) */
889 if (*vr0type
== VR_RANGE
890 && vr1type
== VR_RANGE
)
891 /* Choose the inner range. */
893 else if (*vr0type
== VR_ANTI_RANGE
894 && vr1type
== VR_RANGE
)
896 /* Choose the right gap if the left is empty. */
900 if (TREE_CODE (*vr0max
) != INTEGER_CST
)
902 else if (TYPE_PRECISION (TREE_TYPE (*vr0max
)) == 1
903 && !TYPE_UNSIGNED (TREE_TYPE (*vr0max
)))
905 = int_const_binop (MINUS_EXPR
, *vr0max
,
906 build_int_cst (TREE_TYPE (*vr0max
), -1));
909 = int_const_binop (PLUS_EXPR
, *vr0max
,
910 build_int_cst (TREE_TYPE (*vr0max
), 1));
913 /* Choose the left gap if the right is empty. */
917 if (TREE_CODE (*vr0min
) != INTEGER_CST
)
919 else if (TYPE_PRECISION (TREE_TYPE (*vr0min
)) == 1
920 && !TYPE_UNSIGNED (TREE_TYPE (*vr0min
)))
922 = int_const_binop (PLUS_EXPR
, *vr0min
,
923 build_int_cst (TREE_TYPE (*vr0min
), -1));
926 = int_const_binop (MINUS_EXPR
, *vr0min
,
927 build_int_cst (TREE_TYPE (*vr0min
), 1));
930 /* Choose the anti-range if the range is effectively varying. */
931 else if (vrp_val_is_min (vr1min
)
932 && vrp_val_is_max (vr1max
))
934 /* Choose the anti-range if it is ~[0,0], that range is special
935 enough to special case when vr1's range is relatively wide.
936 At least for types bigger than int - this covers pointers
937 and arguments to functions like ctz. */
938 else if (*vr0min
== *vr0max
939 && integer_zerop (*vr0min
)
940 && ((TYPE_PRECISION (TREE_TYPE (*vr0min
))
941 >= TYPE_PRECISION (integer_type_node
))
942 || POINTER_TYPE_P (TREE_TYPE (*vr0min
)))
943 && TREE_CODE (vr1max
) == INTEGER_CST
944 && TREE_CODE (vr1min
) == INTEGER_CST
945 && (wi::clz (wi::to_wide (vr1max
) - wi::to_wide (vr1min
))
946 < TYPE_PRECISION (TREE_TYPE (*vr0min
)) / 2))
948 /* Else choose the range. */
956 else if (*vr0type
== VR_ANTI_RANGE
957 && vr1type
== VR_ANTI_RANGE
)
959 /* If both are anti-ranges the result is the outer one. */
964 else if (vr1type
== VR_ANTI_RANGE
965 && *vr0type
== VR_RANGE
)
967 /* The intersection is empty. */
968 *vr0type
= VR_UNDEFINED
;
975 else if ((operand_less_p (vr1min
, *vr0max
) == 1
976 || operand_equal_p (vr1min
, *vr0max
, 0))
977 && operand_less_p (*vr0min
, vr1min
) == 1)
979 /* [ ( ] ) or [ ]( ) */
980 if (*vr0type
== VR_ANTI_RANGE
981 && vr1type
== VR_ANTI_RANGE
)
983 else if (*vr0type
== VR_RANGE
984 && vr1type
== VR_RANGE
)
986 else if (*vr0type
== VR_RANGE
987 && vr1type
== VR_ANTI_RANGE
)
989 if (TREE_CODE (vr1min
) == INTEGER_CST
)
990 *vr0max
= int_const_binop (MINUS_EXPR
, vr1min
,
991 build_int_cst (TREE_TYPE (vr1min
), 1));
995 else if (*vr0type
== VR_ANTI_RANGE
996 && vr1type
== VR_RANGE
)
999 if (TREE_CODE (*vr0max
) == INTEGER_CST
)
1000 *vr0min
= int_const_binop (PLUS_EXPR
, *vr0max
,
1001 build_int_cst (TREE_TYPE (*vr0max
), 1));
1009 else if ((operand_less_p (*vr0min
, vr1max
) == 1
1010 || operand_equal_p (*vr0min
, vr1max
, 0))
1011 && operand_less_p (vr1min
, *vr0min
) == 1)
1013 /* ( [ ) ] or ( )[ ] */
1014 if (*vr0type
== VR_ANTI_RANGE
1015 && vr1type
== VR_ANTI_RANGE
)
1017 else if (*vr0type
== VR_RANGE
1018 && vr1type
== VR_RANGE
)
1020 else if (*vr0type
== VR_RANGE
1021 && vr1type
== VR_ANTI_RANGE
)
1023 if (TREE_CODE (vr1max
) == INTEGER_CST
)
1024 *vr0min
= int_const_binop (PLUS_EXPR
, vr1max
,
1025 build_int_cst (TREE_TYPE (vr1max
), 1));
1029 else if (*vr0type
== VR_ANTI_RANGE
1030 && vr1type
== VR_RANGE
)
1032 *vr0type
= VR_RANGE
;
1033 if (TREE_CODE (*vr0min
) == INTEGER_CST
)
1034 *vr0max
= int_const_binop (MINUS_EXPR
, *vr0min
,
1035 build_int_cst (TREE_TYPE (*vr0min
), 1));
1044 /* If we know the intersection is empty, there's no need to
1045 conservatively add anything else to the set. */
1046 if (*vr0type
== VR_UNDEFINED
)
1049 /* As a fallback simply use { *VRTYPE, *VR0MIN, *VR0MAX } as
1050 result for the intersection. That's always a conservative
1051 correct estimate unless VR1 is a constant singleton range
1052 in which case we choose that. */
1053 if (vr1type
== VR_RANGE
1054 && is_gimple_min_invariant (vr1min
)
1055 && vrp_operand_equal_p (vr1min
, vr1max
))
1063 /* Helper for the intersection operation for value ranges. Given two
1064 ranges VR0 and VR1, set VR0 to the intersection of both ranges.
1065 This may not be the smallest possible such range. */
1068 irange::legacy_intersect (irange
*vr0
, const irange
*vr1
)
1070 gcc_checking_assert (vr0
->legacy_mode_p ());
1071 gcc_checking_assert (vr1
->legacy_mode_p ());
1072 /* If either range is VR_VARYING the other one wins. */
1073 if (vr1
->varying_p ())
1075 if (vr0
->varying_p ())
1077 vr0
->set (vr1
->min (), vr1
->max (), vr1
->kind ());
1081 /* When either range is VR_UNDEFINED the resulting range is
1082 VR_UNDEFINED, too. */
1083 if (vr0
->undefined_p ())
1085 if (vr1
->undefined_p ())
1087 vr0
->set_undefined ();
1091 value_range_kind vr0kind
= vr0
->kind ();
1092 tree vr0min
= vr0
->min ();
1093 tree vr0max
= vr0
->max ();
1095 intersect_ranges (&vr0kind
, &vr0min
, &vr0max
,
1096 vr1
->kind (), vr1
->min (), vr1
->max ());
1098 /* Make sure to canonicalize the result though as the inversion of a
1099 VR_RANGE can still be a VR_RANGE. */
1100 if (vr0kind
== VR_UNDEFINED
)
1101 vr0
->set_undefined ();
1102 else if (vr0kind
== VR_VARYING
)
1104 /* If we failed, use the original VR0. */
1108 vr0
->set (vr0min
, vr0max
, vr0kind
);
1111 /* Union the two value-ranges { *VR0TYPE, *VR0MIN, *VR0MAX } and
1112 { VR1TYPE, VR0MIN, VR0MAX } and store the result
1113 in { *VR0TYPE, *VR0MIN, *VR0MAX }. This may not be the smallest
1114 possible such range. The resulting range is not canonicalized. */
1117 union_ranges (enum value_range_kind
*vr0type
,
1118 tree
*vr0min
, tree
*vr0max
,
1119 enum value_range_kind vr1type
,
1120 tree vr1min
, tree vr1max
)
1122 int cmpmin
= compare_values (*vr0min
, vr1min
);
1123 int cmpmax
= compare_values (*vr0max
, vr1max
);
1124 bool mineq
= cmpmin
== 0;
1125 bool maxeq
= cmpmax
== 0;
1127 /* [] is vr0, () is vr1 in the following classification comments. */
1131 if (*vr0type
== vr1type
)
1132 /* Nothing to do for equal ranges. */
1134 else if ((*vr0type
== VR_RANGE
1135 && vr1type
== VR_ANTI_RANGE
)
1136 || (*vr0type
== VR_ANTI_RANGE
1137 && vr1type
== VR_RANGE
))
1139 /* For anti-range with range union the result is varying. */
1145 else if (operand_less_p (*vr0max
, vr1min
) == 1
1146 || operand_less_p (vr1max
, *vr0min
) == 1)
1148 /* [ ] ( ) or ( ) [ ]
1149 If the ranges have an empty intersection, result of the union
1150 operation is the anti-range or if both are anti-ranges
1152 if (*vr0type
== VR_ANTI_RANGE
1153 && vr1type
== VR_ANTI_RANGE
)
1155 else if (*vr0type
== VR_ANTI_RANGE
1156 && vr1type
== VR_RANGE
)
1158 else if (*vr0type
== VR_RANGE
1159 && vr1type
== VR_ANTI_RANGE
)
1165 else if (*vr0type
== VR_RANGE
1166 && vr1type
== VR_RANGE
)
1168 /* The result is the convex hull of both ranges. */
1169 if (operand_less_p (*vr0max
, vr1min
) == 1)
1171 /* If the result can be an anti-range, create one. */
1172 if (TREE_CODE (*vr0max
) == INTEGER_CST
1173 && TREE_CODE (vr1min
) == INTEGER_CST
1174 && vrp_val_is_min (*vr0min
)
1175 && vrp_val_is_max (vr1max
))
1177 tree min
= int_const_binop (PLUS_EXPR
,
1179 build_int_cst (TREE_TYPE (*vr0max
), 1));
1180 tree max
= int_const_binop (MINUS_EXPR
,
1182 build_int_cst (TREE_TYPE (vr1min
), 1));
1183 if (!operand_less_p (max
, min
))
1185 *vr0type
= VR_ANTI_RANGE
;
1197 /* If the result can be an anti-range, create one. */
1198 if (TREE_CODE (vr1max
) == INTEGER_CST
1199 && TREE_CODE (*vr0min
) == INTEGER_CST
1200 && vrp_val_is_min (vr1min
)
1201 && vrp_val_is_max (*vr0max
))
1203 tree min
= int_const_binop (PLUS_EXPR
,
1205 build_int_cst (TREE_TYPE (vr1max
), 1));
1206 tree max
= int_const_binop (MINUS_EXPR
,
1208 build_int_cst (TREE_TYPE (*vr0min
), 1));
1209 if (!operand_less_p (max
, min
))
1211 *vr0type
= VR_ANTI_RANGE
;
1225 else if ((maxeq
|| cmpmax
== 1)
1226 && (mineq
|| cmpmin
== -1))
1228 /* [ ( ) ] or [( ) ] or [ ( )] */
1229 if (*vr0type
== VR_RANGE
1230 && vr1type
== VR_RANGE
)
1232 else if (*vr0type
== VR_ANTI_RANGE
1233 && vr1type
== VR_ANTI_RANGE
)
1239 else if (*vr0type
== VR_ANTI_RANGE
1240 && vr1type
== VR_RANGE
)
1242 /* Arbitrarily choose the right or left gap. */
1243 if (!mineq
&& TREE_CODE (vr1min
) == INTEGER_CST
)
1244 *vr0max
= int_const_binop (MINUS_EXPR
, vr1min
,
1245 build_int_cst (TREE_TYPE (vr1min
), 1));
1246 else if (!maxeq
&& TREE_CODE (vr1max
) == INTEGER_CST
)
1247 *vr0min
= int_const_binop (PLUS_EXPR
, vr1max
,
1248 build_int_cst (TREE_TYPE (vr1max
), 1));
1252 else if (*vr0type
== VR_RANGE
1253 && vr1type
== VR_ANTI_RANGE
)
1254 /* The result covers everything. */
1259 else if ((maxeq
|| cmpmax
== -1)
1260 && (mineq
|| cmpmin
== 1))
1262 /* ( [ ] ) or ([ ] ) or ( [ ]) */
1263 if (*vr0type
== VR_RANGE
1264 && vr1type
== VR_RANGE
)
1270 else if (*vr0type
== VR_ANTI_RANGE
1271 && vr1type
== VR_ANTI_RANGE
)
1273 else if (*vr0type
== VR_RANGE
1274 && vr1type
== VR_ANTI_RANGE
)
1276 *vr0type
= VR_ANTI_RANGE
;
1277 if (!mineq
&& TREE_CODE (*vr0min
) == INTEGER_CST
)
1279 *vr0max
= int_const_binop (MINUS_EXPR
, *vr0min
,
1280 build_int_cst (TREE_TYPE (*vr0min
), 1));
1283 else if (!maxeq
&& TREE_CODE (*vr0max
) == INTEGER_CST
)
1285 *vr0min
= int_const_binop (PLUS_EXPR
, *vr0max
,
1286 build_int_cst (TREE_TYPE (*vr0max
), 1));
1292 else if (*vr0type
== VR_ANTI_RANGE
1293 && vr1type
== VR_RANGE
)
1294 /* The result covers everything. */
1299 else if (cmpmin
== -1
1301 && (operand_less_p (vr1min
, *vr0max
) == 1
1302 || operand_equal_p (vr1min
, *vr0max
, 0)))
1304 /* [ ( ] ) or [ ]( ) */
1305 if (*vr0type
== VR_RANGE
1306 && vr1type
== VR_RANGE
)
1308 else if (*vr0type
== VR_ANTI_RANGE
1309 && vr1type
== VR_ANTI_RANGE
)
1311 else if (*vr0type
== VR_ANTI_RANGE
1312 && vr1type
== VR_RANGE
)
1314 if (TREE_CODE (vr1min
) == INTEGER_CST
)
1315 *vr0max
= int_const_binop (MINUS_EXPR
, vr1min
,
1316 build_int_cst (TREE_TYPE (vr1min
), 1));
1320 else if (*vr0type
== VR_RANGE
1321 && vr1type
== VR_ANTI_RANGE
)
1323 if (TREE_CODE (*vr0max
) == INTEGER_CST
)
1326 *vr0min
= int_const_binop (PLUS_EXPR
, *vr0max
,
1327 build_int_cst (TREE_TYPE (*vr0max
), 1));
1336 else if (cmpmin
== 1
1338 && (operand_less_p (*vr0min
, vr1max
) == 1
1339 || operand_equal_p (*vr0min
, vr1max
, 0)))
1341 /* ( [ ) ] or ( )[ ] */
1342 if (*vr0type
== VR_RANGE
1343 && vr1type
== VR_RANGE
)
1345 else if (*vr0type
== VR_ANTI_RANGE
1346 && vr1type
== VR_ANTI_RANGE
)
1348 else if (*vr0type
== VR_ANTI_RANGE
1349 && vr1type
== VR_RANGE
)
1351 if (TREE_CODE (vr1max
) == INTEGER_CST
)
1352 *vr0min
= int_const_binop (PLUS_EXPR
, vr1max
,
1353 build_int_cst (TREE_TYPE (vr1max
), 1));
1357 else if (*vr0type
== VR_RANGE
1358 && vr1type
== VR_ANTI_RANGE
)
1360 if (TREE_CODE (*vr0min
) == INTEGER_CST
)
1363 *vr0max
= int_const_binop (MINUS_EXPR
, *vr0min
,
1364 build_int_cst (TREE_TYPE (*vr0min
), 1));
1379 *vr0type
= VR_VARYING
;
1380 *vr0min
= NULL_TREE
;
1381 *vr0max
= NULL_TREE
;
1384 /* Helper for meet operation for value ranges. Given two ranges VR0
1385 and VR1, set VR0 to the union of both ranges. This may not be the
1386 smallest possible such range. */
1389 irange::legacy_union (irange
*vr0
, const irange
*vr1
)
1391 gcc_checking_assert (vr0
->legacy_mode_p ());
1392 gcc_checking_assert (vr1
->legacy_mode_p ());
1394 /* VR0 has the resulting range if VR1 is undefined or VR0 is varying. */
1395 if (vr1
->undefined_p ()
1396 || vr0
->varying_p ())
1399 /* VR1 has the resulting range if VR0 is undefined or VR1 is varying. */
1400 if (vr0
->undefined_p ())
1402 vr0
->set (vr1
->min (), vr1
->max (), vr1
->kind ());
1406 if (vr1
->varying_p ())
1408 vr0
->set_varying (vr1
->type ());
1412 value_range_kind vr0kind
= vr0
->kind ();
1413 tree vr0min
= vr0
->min ();
1414 tree vr0max
= vr0
->max ();
1416 union_ranges (&vr0kind
, &vr0min
, &vr0max
,
1417 vr1
->kind (), vr1
->min (), vr1
->max ());
1419 if (vr0kind
== VR_UNDEFINED
)
1420 vr0
->set_undefined ();
1421 else if (vr0kind
== VR_VARYING
)
1423 /* Failed to find an efficient meet. Before giving up and
1424 setting the result to VARYING, see if we can at least derive
1425 a non-zero range. */
1426 if (range_includes_zero_p (vr0
) == 0
1427 && range_includes_zero_p (vr1
) == 0)
1428 vr0
->set_nonzero (vr0
->type ());
1430 vr0
->set_varying (vr0
->type ());
1433 vr0
->set (vr0min
, vr0max
, vr0kind
);
1436 /* Meet operation for value ranges. Given two value ranges VR0 and
1437 VR1, store in VR0 a range that contains both VR0 and VR1. This
1438 may not be the smallest possible such range. */
1441 irange::union_ (const irange
*other
)
1443 if (legacy_mode_p ())
1445 if (!other
->legacy_mode_p ())
1447 int_range
<1> tmp
= *other
;
1448 legacy_union (this, &tmp
);
1451 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1453 fprintf (dump_file
, "Meeting\n ");
1454 dump_value_range (dump_file
, this);
1455 fprintf (dump_file
, "\nand\n ");
1456 dump_value_range (dump_file
, other
);
1457 fprintf (dump_file
, "\n");
1460 legacy_union (this, other
);
1462 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1464 fprintf (dump_file
, "to\n ");
1465 dump_value_range (dump_file
, this);
1466 fprintf (dump_file
, "\n");
1471 if (other
->legacy_mode_p ())
1473 int_range
<2> wider
= *other
;
1474 irange_union (wider
);
1477 irange_union (*other
);
1481 irange::intersect (const irange
*other
)
1483 if (legacy_mode_p ())
1485 if (!other
->legacy_mode_p ())
1487 int_range
<1> tmp
= *other
;
1488 legacy_intersect (this, &tmp
);
1491 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1493 fprintf (dump_file
, "Intersecting\n ");
1494 dump_value_range (dump_file
, this);
1495 fprintf (dump_file
, "\nand\n ");
1496 dump_value_range (dump_file
, other
);
1497 fprintf (dump_file
, "\n");
1500 legacy_intersect (this, other
);
1502 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1504 fprintf (dump_file
, "to\n ");
1505 dump_value_range (dump_file
, this);
1506 fprintf (dump_file
, "\n");
1511 if (other
->legacy_mode_p ())
1515 irange_intersect (wider
);
1518 irange_intersect (*other
);
1521 // union_ for multi-ranges.
1524 irange::irange_union (const irange
&r
)
1526 gcc_checking_assert (!legacy_mode_p () && !r
.legacy_mode_p ());
1528 if (r
.undefined_p () || varying_p ())
1531 if (undefined_p () || r
.varying_p ())
1537 // Do not worry about merging and such by reserving twice as many
1538 // pairs as needed, and then simply sort the 2 ranges into this
1539 // intermediate form.
1541 // The intermediate result will have the property that the beginning
1542 // of each range is <= the beginning of the next range. There may
1543 // be overlapping ranges at this point. I.e. this would be valid
1544 // [-20, 10], [-10, 0], [0, 20], [40, 90] as it satisfies this
1545 // contraint : -20 < -10 < 0 < 40. When the range is rebuilt into r,
1546 // the merge is performed.
1548 // [Xi,Yi]..[Xn,Yn] U [Xj,Yj]..[Xm,Ym] --> [Xk,Yk]..[Xp,Yp]
1549 tree ttype
= r
.type ();
1550 signop sign
= TYPE_SIGN (ttype
);
1552 auto_vec
<tree
, 20> res
;
1554 wi::overflow_type ovf
;
1555 unsigned i
= 0, j
= 0, k
= 0;
1557 while (i
< m_num_ranges
* 2 && j
< r
.m_num_ranges
* 2)
1559 // lower of Xi and Xj is the lowest point.
1560 if (wi::le_p (wi::to_wide (m_base
[i
]), wi::to_wide (r
.m_base
[j
]), sign
))
1562 res
.safe_push (m_base
[i
]);
1563 res
.safe_push (m_base
[i
+ 1]);
1569 res
.safe_push (r
.m_base
[j
]);
1570 res
.safe_push (r
.m_base
[j
+ 1]);
1575 for ( ; i
< m_num_ranges
* 2; i
+= 2)
1577 res
.safe_push (m_base
[i
]);
1578 res
.safe_push (m_base
[i
+ 1]);
1581 for ( ; j
< r
.m_num_ranges
* 2; j
+= 2)
1583 res
.safe_push (r
.m_base
[j
]);
1584 res
.safe_push (r
.m_base
[j
+ 1]);
1588 // Now normalize the vector removing any overlaps.
1590 int prec
= TYPE_PRECISION (ttype
);
1591 wide_int max_val
= wi::max_value (prec
, sign
);
1592 for (j
= 2; j
< k
; j
+= 2)
1594 wide_int val_im1
= wi::to_wide (res
[i
- 1]);
1595 if (val_im1
== max_val
)
1597 u1
= wi::add (val_im1
, 1, sign
, &ovf
);
1599 // Overflow indicates we are at MAX already.
1600 // A wide int bug requires the previous max_val check
1601 // trigger: gcc.c-torture/compile/pr80443.c with -O3
1602 if (ovf
== wi::OVF_OVERFLOW
)
1605 wide_int val_j
= wi::to_wide (res
[j
]);
1606 wide_int val_jp1
= wi::to_wide (res
[j
+1]);
1607 // Current upper+1 is >= lower bound next pair, then we merge ranges.
1608 if (wi::ge_p (u1
, val_j
, sign
))
1610 // New upper bounds is greater of current or the next one.
1611 if (wi::gt_p (val_jp1
, val_im1
, sign
))
1612 res
[i
- 1] = res
[j
+ 1];
1616 // This is a new distinct range, but no point in copying it
1617 // if it is already in the right place.
1621 res
[i
++] = res
[j
+ 1];
1628 // At this point, the vector should have i ranges, none overlapping.
1629 // Now it simply needs to be copied, and if there are too many
1630 // ranges, merge some. We wont do any analysis as to what the
1631 // "best" merges are, simply combine the final ranges into one.
1632 if (i
> m_max_ranges
* 2)
1634 res
[m_max_ranges
* 2 - 1] = res
[i
- 1];
1635 i
= m_max_ranges
* 2;
1638 for (j
= 0; j
< i
; j
++)
1639 m_base
[j
] = res
[j
];
1640 m_num_ranges
= i
/ 2;
1646 // intersect for multi-ranges.
1649 irange::irange_intersect (const irange
&r
)
1651 gcc_checking_assert (!legacy_mode_p () && !r
.legacy_mode_p ());
1653 if (undefined_p () || r
.varying_p ())
1655 if (r
.undefined_p ())
1666 signop sign
= TYPE_SIGN (TREE_TYPE(m_base
[0]));
1667 unsigned bld_pair
= 0;
1668 unsigned bld_lim
= m_max_ranges
;
1669 int_range_max
r2 (*this);
1670 unsigned r2_lim
= r2
.num_pairs ();
1672 for (unsigned i
= 0; i
< r
.num_pairs (); )
1674 // If r1's upper is < r2's lower, we can skip r1's pair.
1675 tree ru
= r
.m_base
[i
* 2 + 1];
1676 tree r2l
= r2
.m_base
[i2
* 2];
1677 if (wi::lt_p (wi::to_wide (ru
), wi::to_wide (r2l
), sign
))
1682 // Likewise, skip r2's pair if its excluded.
1683 tree r2u
= r2
.m_base
[i2
* 2 + 1];
1684 tree rl
= r
.m_base
[i
* 2];
1685 if (wi::lt_p (wi::to_wide (r2u
), wi::to_wide (rl
), sign
))
1690 // No more r2, break.
1694 // Must be some overlap. Find the highest of the lower bounds,
1695 // and set it, unless the build limits lower bounds is already
1697 if (bld_pair
< bld_lim
)
1699 if (wi::ge_p (wi::to_wide (rl
), wi::to_wide (r2l
), sign
))
1700 m_base
[bld_pair
* 2] = rl
;
1702 m_base
[bld_pair
* 2] = r2l
;
1705 // Decrease and set a new upper.
1708 // ...and choose the lower of the upper bounds.
1709 if (wi::le_p (wi::to_wide (ru
), wi::to_wide (r2u
), sign
))
1711 m_base
[bld_pair
* 2 + 1] = ru
;
1713 // Move past the r1 pair and keep trying.
1719 m_base
[bld_pair
* 2 + 1] = r2u
;
1724 // No more r2, break.
1727 // r2 has the higher lower bound.
1730 // At the exit of this loop, it is one of 2 things:
1731 // ran out of r1, or r2, but either means we are done.
1732 m_num_ranges
= bld_pair
;
1737 // Signed 1-bits are strange. You can't subtract 1, because you can't
1738 // represent the number 1. This works around that for the invert routine.
1740 static wide_int
inline
1741 subtract_one (const wide_int
&x
, tree type
, wi::overflow_type
&overflow
)
1743 if (TYPE_SIGN (type
) == SIGNED
)
1744 return wi::add (x
, -1, SIGNED
, &overflow
);
1746 return wi::sub (x
, 1, UNSIGNED
, &overflow
);
1749 // The analogous function for adding 1.
1751 static wide_int
inline
1752 add_one (const wide_int
&x
, tree type
, wi::overflow_type
&overflow
)
1754 if (TYPE_SIGN (type
) == SIGNED
)
1755 return wi::sub (x
, -1, SIGNED
, &overflow
);
1757 return wi::add (x
, 1, UNSIGNED
, &overflow
);
1760 // Return the inverse of a range.
1765 if (legacy_mode_p ())
1767 // We can't just invert VR_RANGE and VR_ANTI_RANGE because we may
1768 // create non-canonical ranges. Use the constructors instead.
1769 if (m_kind
== VR_RANGE
)
1770 *this = value_range (min (), max (), VR_ANTI_RANGE
);
1771 else if (m_kind
== VR_ANTI_RANGE
)
1772 *this = value_range (min (), max ());
1778 gcc_assert (!undefined_p () && !varying_p ());
1780 // We always need one more set of bounds to represent an inverse, so
1781 // if we're at the limit, we can't properly represent things.
1783 // For instance, to represent the inverse of a 2 sub-range set
1784 // [5, 10][20, 30], we would need a 3 sub-range set
1785 // [-MIN, 4][11, 19][31, MAX].
1787 // In this case, return the most conservative thing.
1789 // However, if any of the extremes of the range are -MIN/+MAX, we
1790 // know we will not need an extra bound. For example:
1792 // INVERT([-MIN,20][30,40]) => [21,29][41,+MAX]
1793 // INVERT([-MIN,20][30,MAX]) => [21,29]
1794 tree ttype
= type ();
1795 unsigned prec
= TYPE_PRECISION (ttype
);
1796 signop sign
= TYPE_SIGN (ttype
);
1797 wide_int type_min
= wi::min_value (prec
, sign
);
1798 wide_int type_max
= wi::max_value (prec
, sign
);
1799 if (m_num_ranges
== m_max_ranges
1800 && lower_bound () != type_min
1801 && upper_bound () != type_max
)
1803 m_base
[1] = wide_int_to_tree (ttype
, type_max
);
1807 // The algorithm is as follows. To calculate INVERT ([a,b][c,d]), we
1808 // generate [-MIN, a-1][b+1, c-1][d+1, MAX].
1810 // If there is an over/underflow in the calculation for any
1811 // sub-range, we eliminate that subrange. This allows us to easily
1812 // calculate INVERT([-MIN, 5]) with: [-MIN, -MIN-1][6, MAX]. And since
1813 // we eliminate the underflow, only [6, MAX] remains.
1815 wi::overflow_type ovf
;
1816 // Construct leftmost range.
1817 int_range_max
orig_range (*this);
1818 unsigned nitems
= 0;
1820 // If this is going to underflow on the MINUS 1, don't even bother
1821 // checking. This also handles subtracting one from an unsigned 0,
1822 // which doesn't set the underflow bit.
1823 if (type_min
!= orig_range
.lower_bound ())
1825 m_base
[nitems
++] = wide_int_to_tree (ttype
, type_min
);
1826 tmp
= subtract_one (orig_range
.lower_bound (), ttype
, ovf
);
1827 m_base
[nitems
++] = wide_int_to_tree (ttype
, tmp
);
1832 // Construct middle ranges if applicable.
1833 if (orig_range
.num_pairs () > 1)
1836 for (; j
< (orig_range
.num_pairs () * 2) - 1; j
+= 2)
1838 // The middle ranges cannot have MAX/MIN, so there's no need
1839 // to check for unsigned overflow on the +1 and -1 here.
1840 tmp
= wi::add (wi::to_wide (orig_range
.m_base
[j
]), 1, sign
, &ovf
);
1841 m_base
[nitems
++] = wide_int_to_tree (ttype
, tmp
);
1842 tmp
= subtract_one (wi::to_wide (orig_range
.m_base
[j
+ 1]),
1844 m_base
[nitems
++] = wide_int_to_tree (ttype
, tmp
);
1850 // Construct rightmost range.
1852 // However, if this will overflow on the PLUS 1, don't even bother.
1853 // This also handles adding one to an unsigned MAX, which doesn't
1854 // set the overflow bit.
1855 if (type_max
!= wi::to_wide (orig_range
.m_base
[i
]))
1857 tmp
= add_one (wi::to_wide (orig_range
.m_base
[i
]), ttype
, ovf
);
1858 m_base
[nitems
++] = wide_int_to_tree (ttype
, tmp
);
1859 m_base
[nitems
++] = wide_int_to_tree (ttype
, type_max
);
1863 m_num_ranges
= nitems
/ 2;
1870 dump_bound_with_infinite_markers (FILE *file
, tree bound
)
1872 tree type
= TREE_TYPE (bound
);
1873 wide_int type_min
= wi::min_value (TYPE_PRECISION (type
), TYPE_SIGN (type
));
1874 wide_int type_max
= wi::max_value (TYPE_PRECISION (type
), TYPE_SIGN (type
));
1876 if (INTEGRAL_TYPE_P (type
)
1877 && !TYPE_UNSIGNED (type
)
1878 && TREE_CODE (bound
) == INTEGER_CST
1879 && wi::to_wide (bound
) == type_min
1880 && TYPE_PRECISION (type
) != 1)
1881 fprintf (file
, "-INF");
1882 else if (TREE_CODE (bound
) == INTEGER_CST
1883 && wi::to_wide (bound
) == type_max
1884 && TYPE_PRECISION (type
) != 1)
1885 fprintf (file
, "+INF");
1887 print_generic_expr (file
, bound
);
1891 irange::dump (FILE *file
) const
1895 fprintf (file
, "UNDEFINED");
1898 print_generic_expr (file
, type ());
1899 fprintf (file
, " ");
1902 fprintf (file
, "VARYING");
1905 if (legacy_mode_p ())
1907 fprintf (file
, "%s[", (m_kind
== VR_ANTI_RANGE
) ? "~" : "");
1908 dump_bound_with_infinite_markers (file
, min ());
1909 fprintf (file
, ", ");
1910 dump_bound_with_infinite_markers (file
, max ());
1911 fprintf (file
, "]");
1914 for (unsigned i
= 0; i
< m_num_ranges
; ++i
)
1916 tree lb
= m_base
[i
* 2];
1917 tree ub
= m_base
[i
* 2 + 1];
1918 fprintf (file
, "[");
1919 dump_bound_with_infinite_markers (file
, lb
);
1920 fprintf (file
, ", ");
1921 dump_bound_with_infinite_markers (file
, ub
);
1922 fprintf (file
, "]");
1927 dump_value_range (FILE *file
, const irange
*vr
)
1933 debug (const irange
*vr
)
1935 dump_value_range (stderr
, vr
);
1936 fprintf (stderr
, "\n");
1940 debug (const irange
&vr
)
1946 debug (const value_range
*vr
)
1948 dump_value_range (stderr
, vr
);
1949 fprintf (stderr
, "\n");
1953 debug (const value_range
&vr
)
1955 dump_value_range (stderr
, &vr
);
1956 fprintf (stderr
, "\n");
1959 /* Create two value-ranges in *VR0 and *VR1 from the anti-range *AR
1960 so that *VR0 U *VR1 == *AR. Returns true if that is possible,
1961 false otherwise. If *AR can be represented with a single range
1962 *VR1 will be VR_UNDEFINED. */
1965 ranges_from_anti_range (const value_range
*ar
,
1966 value_range
*vr0
, value_range
*vr1
)
1968 tree type
= ar
->type ();
1970 vr0
->set_undefined ();
1971 vr1
->set_undefined ();
1973 /* As a future improvement, we could handle ~[0, A] as: [-INF, -1] U
1974 [A+1, +INF]. Not sure if this helps in practice, though. */
1976 if (ar
->kind () != VR_ANTI_RANGE
1977 || TREE_CODE (ar
->min ()) != INTEGER_CST
1978 || TREE_CODE (ar
->max ()) != INTEGER_CST
1979 || !vrp_val_min (type
)
1980 || !vrp_val_max (type
))
1983 if (tree_int_cst_lt (vrp_val_min (type
), ar
->min ()))
1984 vr0
->set (vrp_val_min (type
),
1985 wide_int_to_tree (type
, wi::to_wide (ar
->min ()) - 1));
1986 if (tree_int_cst_lt (ar
->max (), vrp_val_max (type
)))
1987 vr1
->set (wide_int_to_tree (type
, wi::to_wide (ar
->max ()) + 1),
1988 vrp_val_max (type
));
1989 if (vr0
->undefined_p ())
1992 vr1
->set_undefined ();
1995 return !vr0
->undefined_p ();
1999 range_has_numeric_bounds_p (const irange
*vr
)
2001 return (!vr
->undefined_p ()
2002 && TREE_CODE (vr
->min ()) == INTEGER_CST
2003 && TREE_CODE (vr
->max ()) == INTEGER_CST
);
2006 /* Return whether VAL is equal to the maximum value of its type.
2007 We can't do a simple equality comparison with TYPE_MAX_VALUE because
2008 C typedefs and Ada subtypes can produce types whose TYPE_MAX_VALUE
2009 is not == to the integer constant with the same value in the type. */
2012 vrp_val_is_max (const_tree val
)
2014 tree type_max
= vrp_val_max (TREE_TYPE (val
));
2015 return (val
== type_max
2016 || (type_max
!= NULL_TREE
2017 && operand_equal_p (val
, type_max
, 0)));
2020 /* Return whether VAL is equal to the minimum value of its type. */
2023 vrp_val_is_min (const_tree val
)
2025 tree type_min
= vrp_val_min (TREE_TYPE (val
));
2026 return (val
== type_min
2027 || (type_min
!= NULL_TREE
2028 && operand_equal_p (val
, type_min
, 0)));
2031 /* Return true, if VAL1 and VAL2 are equal values for VRP purposes. */
2034 vrp_operand_equal_p (const_tree val1
, const_tree val2
)
2038 if (!val1
|| !val2
|| !operand_equal_p (val1
, val2
, 0))
2043 #define DEFINE_INT_RANGE_GC_STUBS(N) \
2045 gt_pch_nx (int_range<N> *&x) \
2047 for (unsigned i = 0; i < N; ++i) \
2049 gt_pch_nx (x->m_ranges[i * 2]); \
2050 gt_pch_nx (x->m_ranges[i * 2 + 1]); \
2055 gt_ggc_mx (int_range<N> *&x) \
2057 for (unsigned i = 0; i < N; ++i) \
2059 gt_ggc_mx (x->m_ranges[i * 2]); \
2060 gt_ggc_mx (x->m_ranges[i * 2 + 1]); \
2064 #define DEFINE_INT_RANGE_INSTANCE(N) \
2065 template int_range<N>::int_range(tree, tree, value_range_kind); \
2066 template int_range<N>::int_range(tree_node *, \
2069 value_range_kind); \
2070 template int_range<N>::int_range(tree); \
2071 template int_range<N>::int_range(const irange &); \
2072 template int_range<N>::int_range(const int_range &); \
2073 template int_range<N>& int_range<N>::operator= (const int_range &);
2075 DEFINE_INT_RANGE_INSTANCE(1)
2076 DEFINE_INT_RANGE_INSTANCE(2)
2077 DEFINE_INT_RANGE_INSTANCE(3)
2078 DEFINE_INT_RANGE_INSTANCE(255)
2079 DEFINE_INT_RANGE_GC_STUBS(1)
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 ());
2253 // Simulate -fstrict-enums where the domain of a type is less than the
2257 range_tests_strict_enum ()
2259 // The enum can only hold [0, 3].
2260 tree rtype
= copy_node (unsigned_type_node
);
2261 TYPE_MIN_VALUE (rtype
) = build_int_cstu (rtype
, 0);
2262 TYPE_MAX_VALUE (rtype
) = build_int_cstu (rtype
, 3);
2264 // Test that even though vr1 covers the strict enum domain ([0, 3]),
2265 // it does not cover the domain of the underlying type.
2266 int_range
<1> vr1 (build_int_cstu (rtype
, 0), build_int_cstu (rtype
, 1));
2267 int_range
<1> vr2 (build_int_cstu (rtype
, 2), build_int_cstu (rtype
, 3));
2269 ASSERT_TRUE (vr1
== int_range
<1> (build_int_cstu (rtype
, 0),
2270 build_int_cstu (rtype
, 3)));
2271 ASSERT_FALSE (vr1
.varying_p ());
2273 // Test that copying to a multi-range does not change things.
2274 int_range
<2> ir1 (vr1
);
2275 ASSERT_TRUE (ir1
== vr1
);
2276 ASSERT_FALSE (ir1
.varying_p ());
2278 // The same test as above, but using TYPE_{MIN,MAX}_VALUE instead of [0,3].
2279 vr1
= int_range
<1> (TYPE_MIN_VALUE (rtype
), TYPE_MAX_VALUE (rtype
));
2281 ASSERT_TRUE (ir1
== vr1
);
2282 ASSERT_FALSE (ir1
.varying_p ());
2288 tree u128_type
= build_nonstandard_integer_type (128, /*unsigned=*/1);
2289 int_range
<1> i1
, i2
, i3
;
2290 int_range
<1> r0
, r1
, rold
;
2292 // Test 1-bit signed integer union.
2293 // [-1,-1] U [0,0] = VARYING.
2294 tree one_bit_type
= build_nonstandard_integer_type (1, 0);
2295 tree one_bit_min
= vrp_val_min (one_bit_type
);
2296 tree one_bit_max
= vrp_val_max (one_bit_type
);
2298 int_range
<2> min (one_bit_min
, one_bit_min
);
2299 int_range
<2> max (one_bit_max
, one_bit_max
);
2301 ASSERT_TRUE (max
.varying_p ());
2304 // Test inversion of 1-bit signed integers.
2306 int_range
<2> min (one_bit_min
, one_bit_min
);
2307 int_range
<2> max (one_bit_max
, one_bit_max
);
2311 ASSERT_TRUE (t
== max
);
2314 ASSERT_TRUE (t
== min
);
2317 // Test that NOT(255) is [0..254] in 8-bit land.
2318 int_range
<1> not_255 (UCHAR (255), UCHAR (255), VR_ANTI_RANGE
);
2319 ASSERT_TRUE (not_255
== int_range
<1> (UCHAR (0), UCHAR (254)));
2321 // Test that NOT(0) is [1..255] in 8-bit land.
2322 int_range
<1> not_zero
= range_nonzero (unsigned_char_type_node
);
2323 ASSERT_TRUE (not_zero
== int_range
<1> (UCHAR (1), UCHAR (255)));
2325 // Check that [0,127][0x..ffffff80,0x..ffffff]
2326 // => ~[128, 0x..ffffff7f].
2327 r0
= int_range
<1> (UINT128 (0), UINT128 (127));
2328 tree high
= build_minus_one_cst (u128_type
);
2329 // low = -1 - 127 => 0x..ffffff80.
2330 tree low
= fold_build2 (MINUS_EXPR
, u128_type
, high
, UINT128(127));
2331 r1
= int_range
<1> (low
, high
); // [0x..ffffff80, 0x..ffffffff]
2332 // r0 = [0,127][0x..ffffff80,0x..fffffff].
2334 // r1 = [128, 0x..ffffff7f].
2335 r1
= int_range
<1> (UINT128(128),
2336 fold_build2 (MINUS_EXPR
, u128_type
,
2337 build_minus_one_cst (u128_type
),
2340 ASSERT_TRUE (r0
== r1
);
2342 r0
.set_varying (integer_type_node
);
2343 tree minint
= wide_int_to_tree (integer_type_node
, r0
.lower_bound ());
2344 tree maxint
= wide_int_to_tree (integer_type_node
, r0
.upper_bound ());
2346 r0
.set_varying (short_integer_type_node
);
2348 r0
.set_varying (unsigned_type_node
);
2349 tree maxuint
= wide_int_to_tree (unsigned_type_node
, r0
.upper_bound ());
2351 // Check that ~[0,5] => [6,MAX] for unsigned int.
2352 r0
= int_range
<1> (UINT (0), UINT (5));
2354 ASSERT_TRUE (r0
== int_range
<1> (UINT(6), maxuint
));
2356 // Check that ~[10,MAX] => [0,9] for unsigned int.
2357 r0
= int_range
<1> (UINT(10), maxuint
);
2359 ASSERT_TRUE (r0
== int_range
<1> (UINT (0), UINT (9)));
2361 // Check that ~[0,5] => [6,MAX] for unsigned 128-bit numbers.
2362 r0
= int_range
<1> (UINT128 (0), UINT128 (5), VR_ANTI_RANGE
);
2363 r1
= int_range
<1> (UINT128(6), build_minus_one_cst (u128_type
));
2364 ASSERT_TRUE (r0
== r1
);
2366 // Check that [~5] is really [-MIN,4][6,MAX].
2367 r0
= int_range
<1> (INT (5), INT (5), VR_ANTI_RANGE
);
2368 r1
= int_range
<1> (minint
, INT (4));
2369 r1
.union_ (int_range
<1> (INT (6), maxint
));
2370 ASSERT_FALSE (r1
.undefined_p ());
2371 ASSERT_TRUE (r0
== r1
);
2373 r1
= int_range
<1> (INT (5), INT (5));
2374 int_range
<1> r2 (r1
);
2375 ASSERT_TRUE (r1
== r2
);
2377 r1
= int_range
<1> (INT (5), INT (10));
2379 r1
= int_range
<1> (integer_type_node
,
2380 wi::to_wide (INT (5)), wi::to_wide (INT (10)));
2381 ASSERT_TRUE (r1
.contains_p (INT (7)));
2383 r1
= int_range
<1> (SCHAR (0), SCHAR (20));
2384 ASSERT_TRUE (r1
.contains_p (SCHAR(15)));
2385 ASSERT_FALSE (r1
.contains_p (SCHAR(300)));
2387 // NOT([10,20]) ==> [-MIN,9][21,MAX].
2388 r0
= r1
= int_range
<1> (INT (10), INT (20));
2389 r2
= int_range
<1> (minint
, INT(9));
2390 r2
.union_ (int_range
<1> (INT(21), maxint
));
2391 ASSERT_FALSE (r2
.undefined_p ());
2393 ASSERT_TRUE (r1
== r2
);
2394 // Test that NOT(NOT(x)) == x.
2396 ASSERT_TRUE (r0
== r2
);
2398 // Test that booleans and their inverse work as expected.
2399 r0
= range_zero (boolean_type_node
);
2400 ASSERT_TRUE (r0
== int_range
<1> (build_zero_cst (boolean_type_node
),
2401 build_zero_cst (boolean_type_node
)));
2403 ASSERT_TRUE (r0
== int_range
<1> (build_one_cst (boolean_type_node
),
2404 build_one_cst (boolean_type_node
)));
2406 // Make sure NULL and non-NULL of pointer types work, and that
2407 // inverses of them are consistent.
2408 tree voidp
= build_pointer_type (void_type_node
);
2409 r0
= range_zero (voidp
);
2413 ASSERT_TRUE (r0
== r1
);
2415 // [10,20] U [15, 30] => [10, 30].
2416 r0
= int_range
<1> (INT (10), INT (20));
2417 r1
= int_range
<1> (INT (15), INT (30));
2419 ASSERT_TRUE (r0
== int_range
<1> (INT (10), INT (30)));
2421 // [15,40] U [] => [15,40].
2422 r0
= int_range
<1> (INT (15), INT (40));
2423 r1
.set_undefined ();
2425 ASSERT_TRUE (r0
== int_range
<1> (INT (15), INT (40)));
2427 // [10,20] U [10,10] => [10,20].
2428 r0
= int_range
<1> (INT (10), INT (20));
2429 r1
= int_range
<1> (INT (10), INT (10));
2431 ASSERT_TRUE (r0
== int_range
<1> (INT (10), INT (20)));
2433 // [10,20] U [9,9] => [9,20].
2434 r0
= int_range
<1> (INT (10), INT (20));
2435 r1
= int_range
<1> (INT (9), INT (9));
2437 ASSERT_TRUE (r0
== int_range
<1> (INT (9), INT (20)));
2439 // [10,20] ^ [15,30] => [15,20].
2440 r0
= int_range
<1> (INT (10), INT (20));
2441 r1
= int_range
<1> (INT (15), INT (30));
2443 ASSERT_TRUE (r0
== int_range
<1> (INT (15), INT (20)));
2445 // Test the internal sanity of wide_int's wrt HWIs.
2446 ASSERT_TRUE (wi::max_value (TYPE_PRECISION (boolean_type_node
),
2447 TYPE_SIGN (boolean_type_node
))
2448 == wi::uhwi (1, TYPE_PRECISION (boolean_type_node
)));
2451 r0
= int_range
<1> (INT (0), INT (0));
2452 ASSERT_TRUE (r0
.zero_p ());
2454 // Test nonzero_p().
2455 r0
= int_range
<1> (INT (0), INT (0));
2457 ASSERT_TRUE (r0
.nonzero_p ());
2459 // test legacy interaction
2461 r0
= int_range
<1> (UINT (1), UINT (1), VR_ANTI_RANGE
);
2463 r1
= int_range
<1> (UINT (3), UINT (3), VR_ANTI_RANGE
);
2465 // vv = [0,0][2,2][4, MAX]
2466 int_range
<3> vv
= r0
;
2469 ASSERT_TRUE (vv
.contains_p (UINT (2)));
2470 ASSERT_TRUE (vv
.num_pairs () == 3);
2472 // create r0 as legacy [1,1]
2473 r0
= int_range
<1> (UINT (1), UINT (1));
2474 // And union it with [0,0][2,2][4,MAX] multi range
2476 // The result should be [0,2][4,MAX], or ~[3,3] but it must contain 2
2477 ASSERT_TRUE (r0
.contains_p (UINT (2)));
2483 range_tests_legacy ();
2484 range_tests_irange3 ();
2485 range_tests_int_range_max ();
2486 range_tests_strict_enum ();
2487 range_tests_misc ();
2490 } // namespace selftest
2492 #endif // CHECKING_P