1 /* Support routines for value ranges.
2 Copyright (C) 2019-2022 Free Software Foundation, Inc.
3 Major hacks by Aldy Hernandez <aldyh@redhat.com> and
4 Andrew MacLeod <amacleod@redhat.com>.
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify
9 it under the terms of the GNU General Public License as published by
10 the Free Software Foundation; either version 3, or (at your option)
13 GCC is distributed in the hope that it will be useful,
14 but WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 GNU General Public License for more details.
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
24 #include "coretypes.h"
29 #include "tree-pretty-print.h"
30 #include "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 (kind
!= VR_UNDEFINED
)
275 if (TREE_OVERFLOW_P (min
))
276 min
= drop_tree_overflow (min
);
277 if (TREE_OVERFLOW_P (max
))
278 max
= drop_tree_overflow (max
);
281 if (!legacy_mode_p ())
283 if (kind
== VR_RANGE
)
284 irange_set (min
, max
);
287 gcc_checking_assert (kind
== VR_ANTI_RANGE
);
288 irange_set_anti_range (min
, max
);
292 if (kind
== VR_UNDEFINED
)
298 if (kind
== VR_VARYING
299 || POLY_INT_CST_P (min
)
300 || POLY_INT_CST_P (max
))
302 set_varying (TREE_TYPE (min
));
306 // Nothing to canonicalize for symbolic ranges.
307 if (TREE_CODE (min
) != INTEGER_CST
308 || TREE_CODE (max
) != INTEGER_CST
)
317 swap_out_of_order_endpoints (min
, max
, kind
);
318 if (kind
== VR_VARYING
)
320 set_varying (TREE_TYPE (min
));
324 // Anti-ranges that can be represented as ranges should be so.
325 if (kind
== VR_ANTI_RANGE
)
327 bool is_min
= vrp_val_is_min (min
);
328 bool is_max
= vrp_val_is_max (max
);
330 if (is_min
&& is_max
)
332 // Fall through. This will either be normalized as
333 // VR_UNDEFINED if the anti-range spans the entire
334 // precision, or it will remain an VR_ANTI_RANGE in the case
335 // of an -fstrict-enum where [MIN,MAX] is less than the span
336 // of underlying precision.
338 else if (TYPE_PRECISION (TREE_TYPE (min
)) == 1)
340 irange_set_1bit_anti_range (min
, max
);
345 tree one
= build_int_cst (TREE_TYPE (max
), 1);
346 min
= int_const_binop (PLUS_EXPR
, max
, one
);
347 max
= vrp_val_max (TREE_TYPE (max
));
352 tree one
= build_int_cst (TREE_TYPE (min
), 1);
353 max
= int_const_binop (MINUS_EXPR
, min
, one
);
354 min
= vrp_val_min (TREE_TYPE (min
));
368 // Check the validity of the range.
371 irange::verify_range ()
373 if (m_kind
== VR_UNDEFINED
)
375 gcc_checking_assert (m_num_ranges
== 0);
378 if (m_kind
== VR_VARYING
)
380 gcc_checking_assert (m_num_ranges
== 1);
381 gcc_checking_assert (varying_compatible_p ());
384 if (!legacy_mode_p ())
386 gcc_checking_assert (m_num_ranges
!= 0);
387 gcc_checking_assert (!varying_compatible_p ());
388 for (unsigned i
= 0; i
< m_num_ranges
; ++i
)
390 tree lb
= tree_lower_bound (i
);
391 tree ub
= tree_upper_bound (i
);
392 int c
= compare_values (lb
, ub
);
393 gcc_checking_assert (c
== 0 || c
== -1);
397 if (m_kind
== VR_RANGE
|| m_kind
== VR_ANTI_RANGE
)
399 gcc_checking_assert (m_num_ranges
== 1);
400 int cmp
= compare_values (tree_lower_bound (0), tree_upper_bound (0));
401 gcc_checking_assert (cmp
== 0 || cmp
== -1 || cmp
== -2);
405 // Return the lower bound for a sub-range. PAIR is the sub-range in
409 irange::legacy_lower_bound (unsigned pair
) const
411 gcc_checking_assert (legacy_mode_p ());
414 value_range
numeric_range (*this);
415 numeric_range
.normalize_symbolics ();
416 return numeric_range
.legacy_lower_bound (pair
);
418 gcc_checking_assert (m_num_ranges
> 0);
419 gcc_checking_assert (pair
+ 1 <= num_pairs ());
420 if (m_kind
== VR_ANTI_RANGE
)
422 tree typ
= type (), t
;
423 if (pair
== 1 || vrp_val_is_min (min ()))
424 t
= wide_int_to_tree (typ
, wi::to_wide (max ()) + 1);
426 t
= vrp_val_min (typ
);
427 return wi::to_wide (t
);
429 return wi::to_wide (tree_lower_bound (pair
));
432 // Return the upper bound for a sub-range. PAIR is the sub-range in
436 irange::legacy_upper_bound (unsigned pair
) const
438 gcc_checking_assert (legacy_mode_p ());
441 value_range
numeric_range (*this);
442 numeric_range
.normalize_symbolics ();
443 return numeric_range
.legacy_upper_bound (pair
);
445 gcc_checking_assert (m_num_ranges
> 0);
446 gcc_checking_assert (pair
+ 1 <= num_pairs ());
447 if (m_kind
== VR_ANTI_RANGE
)
449 tree typ
= type (), t
;
450 if (pair
== 1 || vrp_val_is_min (min ()))
451 t
= vrp_val_max (typ
);
453 t
= wide_int_to_tree (typ
, wi::to_wide (min ()) - 1);
454 return wi::to_wide (t
);
456 return wi::to_wide (tree_upper_bound (pair
));
460 irange::legacy_equal_p (const irange
&other
) const
462 gcc_checking_assert (legacy_mode_p () && other
.legacy_mode_p ());
464 if (m_kind
!= other
.m_kind
)
466 if (m_kind
== VR_UNDEFINED
)
468 if (m_kind
== VR_VARYING
)
469 return range_compatible_p (type (), other
.type ());
470 return (vrp_operand_equal_p (tree_lower_bound (0),
471 other
.tree_lower_bound (0))
472 && vrp_operand_equal_p (tree_upper_bound (0),
473 other
.tree_upper_bound (0)));
477 irange::equal_p (const irange
&other
) const
479 if (legacy_mode_p ())
481 if (other
.legacy_mode_p ())
482 return legacy_equal_p (other
);
483 value_range
tmp (other
);
484 return legacy_equal_p (tmp
);
486 if (other
.legacy_mode_p ())
488 value_range
tmp2 (*this);
489 return tmp2
.legacy_equal_p (other
);
492 if (m_num_ranges
!= other
.m_num_ranges
)
495 for (unsigned i
= 0; i
< m_num_ranges
; ++i
)
497 tree lb
= tree_lower_bound (i
);
498 tree ub
= tree_upper_bound (i
);
499 tree lb_other
= other
.tree_lower_bound (i
);
500 tree ub_other
= other
.tree_upper_bound (i
);
501 if (!operand_equal_p (lb
, lb_other
, 0)
502 || !operand_equal_p (ub
, ub_other
, 0))
508 /* Return TRUE if this is a symbolic range. */
511 irange::symbolic_p () const
513 return (m_num_ranges
> 0
514 && (!is_gimple_min_invariant (min ())
515 || !is_gimple_min_invariant (max ())));
518 /* Return TRUE if this is a constant range. */
521 irange::constant_p () const
523 return (m_num_ranges
> 0
524 && TREE_CODE (min ()) == INTEGER_CST
525 && TREE_CODE (max ()) == INTEGER_CST
);
528 /* If range is a singleton, place it in RESULT and return TRUE.
529 Note: A singleton can be any gimple invariant, not just constants.
530 So, [&x, &x] counts as a singleton. */
533 irange::singleton_p (tree
*result
) const
535 if (!legacy_mode_p ())
537 if (num_pairs () == 1 && (wi::to_wide (tree_lower_bound ())
538 == wi::to_wide (tree_upper_bound ())))
541 *result
= tree_lower_bound ();
546 if (m_kind
== VR_ANTI_RANGE
)
550 if (TYPE_PRECISION (type ()) == 1)
558 if (num_pairs () == 1)
560 value_range vr0
, vr1
;
561 ranges_from_anti_range ((const value_range
*) this, &vr0
, &vr1
);
562 return vr0
.singleton_p (result
);
565 // Catches non-numeric extremes as well.
566 if (m_kind
== VR_RANGE
567 && vrp_operand_equal_p (min (), max ())
568 && is_gimple_min_invariant (min ()))
577 /* Return 1 if VAL is inside value range.
578 0 if VAL is not inside value range.
579 -2 if we cannot tell either way.
581 Benchmark compile/20001226-1.c compilation time after changing this
585 irange::value_inside_range (tree val
) const
593 if (!legacy_mode_p () && TREE_CODE (val
) == INTEGER_CST
)
594 return contains_p (val
);
596 int cmp1
= operand_less_p (val
, min ());
600 return m_kind
!= VR_RANGE
;
602 int cmp2
= operand_less_p (max (), val
);
606 if (m_kind
== VR_RANGE
)
612 /* Return TRUE if it is possible that range contains VAL. */
615 irange::may_contain_p (tree val
) const
617 return value_inside_range (val
) != 0;
620 /* Return TRUE if range contains INTEGER_CST. */
621 /* Return 1 if VAL is inside value range.
622 0 if VAL is not inside value range.
624 Benchmark compile/20001226-1.c compilation time after changing this
629 irange::contains_p (tree cst
) const
634 if (legacy_mode_p ())
636 gcc_checking_assert (TREE_CODE (cst
) == INTEGER_CST
);
639 value_range
numeric_range (*this);
640 numeric_range
.normalize_symbolics ();
641 return numeric_range
.contains_p (cst
);
643 return value_inside_range (cst
) == 1;
646 gcc_checking_assert (TREE_CODE (cst
) == INTEGER_CST
);
647 signop sign
= TYPE_SIGN (TREE_TYPE (cst
));
648 wide_int v
= wi::to_wide (cst
);
649 for (unsigned r
= 0; r
< m_num_ranges
; ++r
)
651 if (wi::lt_p (v
, lower_bound (r
), sign
))
653 if (wi::le_p (v
, upper_bound (r
), sign
))
661 /* Normalize addresses into constants. */
664 irange::normalize_addresses ()
669 if (!POINTER_TYPE_P (type ()) || range_has_numeric_bounds_p (this))
672 if (!range_includes_zero_p (this))
674 gcc_checking_assert (TREE_CODE (min ()) == ADDR_EXPR
675 || TREE_CODE (max ()) == ADDR_EXPR
);
676 set_nonzero (type ());
679 set_varying (type ());
682 /* Normalize symbolics and addresses into constants. */
685 irange::normalize_symbolics ()
687 if (varying_p () || undefined_p ())
690 tree ttype
= type ();
691 bool min_symbolic
= !is_gimple_min_invariant (min ());
692 bool max_symbolic
= !is_gimple_min_invariant (max ());
693 if (!min_symbolic
&& !max_symbolic
)
695 normalize_addresses ();
699 // [SYM, SYM] -> VARYING
700 if (min_symbolic
&& max_symbolic
)
705 if (kind () == VR_RANGE
)
707 // [SYM, NUM] -> [-MIN, NUM]
710 set (vrp_val_min (ttype
), max ());
713 // [NUM, SYM] -> [NUM, +MAX]
714 set (min (), vrp_val_max (ttype
));
717 gcc_checking_assert (kind () == VR_ANTI_RANGE
);
718 // ~[SYM, NUM] -> [NUM + 1, +MAX]
721 if (!vrp_val_is_max (max ()))
723 tree n
= wide_int_to_tree (ttype
, wi::to_wide (max ()) + 1);
724 set (n
, vrp_val_max (ttype
));
730 // ~[NUM, SYM] -> [-MIN, NUM - 1]
731 if (!vrp_val_is_min (min ()))
733 tree n
= wide_int_to_tree (ttype
, wi::to_wide (min ()) - 1);
734 set (vrp_val_min (ttype
), n
);
740 /* Intersect the two value-ranges { *VR0TYPE, *VR0MIN, *VR0MAX } and
741 { VR1TYPE, VR0MIN, VR0MAX } and store the result
742 in { *VR0TYPE, *VR0MIN, *VR0MAX }. This may not be the smallest
743 possible such range. The resulting range is not canonicalized. */
746 intersect_ranges (enum value_range_kind
*vr0type
,
747 tree
*vr0min
, tree
*vr0max
,
748 enum value_range_kind vr1type
,
749 tree vr1min
, tree vr1max
)
751 bool mineq
= vrp_operand_equal_p (*vr0min
, vr1min
);
752 bool maxeq
= vrp_operand_equal_p (*vr0max
, vr1max
);
754 /* [] is vr0, () is vr1 in the following classification comments. */
758 if (*vr0type
== vr1type
)
759 /* Nothing to do for equal ranges. */
761 else if ((*vr0type
== VR_RANGE
762 && vr1type
== VR_ANTI_RANGE
)
763 || (*vr0type
== VR_ANTI_RANGE
764 && vr1type
== VR_RANGE
))
766 /* For anti-range with range intersection the result is empty. */
767 *vr0type
= VR_UNDEFINED
;
774 else if (operand_less_p (*vr0max
, vr1min
) == 1
775 || operand_less_p (vr1max
, *vr0min
) == 1)
777 /* [ ] ( ) or ( ) [ ]
778 If the ranges have an empty intersection, the result of the
779 intersect operation is the range for intersecting an
780 anti-range with a range or empty when intersecting two ranges. */
781 if (*vr0type
== VR_RANGE
782 && vr1type
== VR_ANTI_RANGE
)
784 else if (*vr0type
== VR_ANTI_RANGE
785 && vr1type
== VR_RANGE
)
791 else if (*vr0type
== VR_RANGE
792 && vr1type
== VR_RANGE
)
794 *vr0type
= VR_UNDEFINED
;
798 else if (*vr0type
== VR_ANTI_RANGE
799 && vr1type
== VR_ANTI_RANGE
)
801 /* If the anti-ranges are adjacent to each other merge them. */
802 if (TREE_CODE (*vr0max
) == INTEGER_CST
803 && TREE_CODE (vr1min
) == INTEGER_CST
804 && operand_less_p (*vr0max
, vr1min
) == 1
805 && integer_onep (int_const_binop (MINUS_EXPR
,
808 else if (TREE_CODE (vr1max
) == INTEGER_CST
809 && TREE_CODE (*vr0min
) == INTEGER_CST
810 && operand_less_p (vr1max
, *vr0min
) == 1
811 && integer_onep (int_const_binop (MINUS_EXPR
,
814 /* Else arbitrarily take VR0. */
817 else if ((maxeq
|| operand_less_p (vr1max
, *vr0max
) == 1)
818 && (mineq
|| operand_less_p (*vr0min
, vr1min
) == 1))
820 /* [ ( ) ] or [( ) ] or [ ( )] */
821 if (*vr0type
== VR_RANGE
822 && vr1type
== VR_RANGE
)
824 /* If both are ranges the result is the inner one. */
829 else if (*vr0type
== VR_RANGE
830 && vr1type
== VR_ANTI_RANGE
)
832 /* Choose the right gap if the left one is empty. */
835 if (TREE_CODE (vr1max
) != INTEGER_CST
)
837 else if (TYPE_PRECISION (TREE_TYPE (vr1max
)) == 1
838 && !TYPE_UNSIGNED (TREE_TYPE (vr1max
)))
840 = int_const_binop (MINUS_EXPR
, vr1max
,
841 build_int_cst (TREE_TYPE (vr1max
), -1));
844 = int_const_binop (PLUS_EXPR
, vr1max
,
845 build_int_cst (TREE_TYPE (vr1max
), 1));
847 /* Choose the left gap if the right one is empty. */
850 if (TREE_CODE (vr1min
) != INTEGER_CST
)
852 else if (TYPE_PRECISION (TREE_TYPE (vr1min
)) == 1
853 && !TYPE_UNSIGNED (TREE_TYPE (vr1min
)))
855 = int_const_binop (PLUS_EXPR
, vr1min
,
856 build_int_cst (TREE_TYPE (vr1min
), -1));
859 = int_const_binop (MINUS_EXPR
, vr1min
,
860 build_int_cst (TREE_TYPE (vr1min
), 1));
862 /* Choose the anti-range if the range is effectively varying. */
863 else if (vrp_val_is_min (*vr0min
)
864 && vrp_val_is_max (*vr0max
))
870 /* Else choose the range. */
872 else if (*vr0type
== VR_ANTI_RANGE
873 && vr1type
== VR_ANTI_RANGE
)
874 /* If both are anti-ranges the result is the outer one. */
876 else if (*vr0type
== VR_ANTI_RANGE
877 && vr1type
== VR_RANGE
)
879 /* The intersection is empty. */
880 *vr0type
= VR_UNDEFINED
;
887 else if ((maxeq
|| operand_less_p (*vr0max
, vr1max
) == 1)
888 && (mineq
|| operand_less_p (vr1min
, *vr0min
) == 1))
890 /* ( [ ] ) or ([ ] ) or ( [ ]) */
891 if (*vr0type
== VR_RANGE
892 && vr1type
== VR_RANGE
)
893 /* Choose the inner range. */
895 else if (*vr0type
== VR_ANTI_RANGE
896 && vr1type
== VR_RANGE
)
898 /* Choose the right gap if the left is empty. */
902 if (TREE_CODE (*vr0max
) != INTEGER_CST
)
904 else if (TYPE_PRECISION (TREE_TYPE (*vr0max
)) == 1
905 && !TYPE_UNSIGNED (TREE_TYPE (*vr0max
)))
907 = int_const_binop (MINUS_EXPR
, *vr0max
,
908 build_int_cst (TREE_TYPE (*vr0max
), -1));
911 = int_const_binop (PLUS_EXPR
, *vr0max
,
912 build_int_cst (TREE_TYPE (*vr0max
), 1));
915 /* Choose the left gap if the right is empty. */
919 if (TREE_CODE (*vr0min
) != INTEGER_CST
)
921 else if (TYPE_PRECISION (TREE_TYPE (*vr0min
)) == 1
922 && !TYPE_UNSIGNED (TREE_TYPE (*vr0min
)))
924 = int_const_binop (PLUS_EXPR
, *vr0min
,
925 build_int_cst (TREE_TYPE (*vr0min
), -1));
928 = int_const_binop (MINUS_EXPR
, *vr0min
,
929 build_int_cst (TREE_TYPE (*vr0min
), 1));
932 /* Choose the anti-range if the range is effectively varying. */
933 else if (vrp_val_is_min (vr1min
)
934 && vrp_val_is_max (vr1max
))
936 /* Choose the anti-range if it is ~[0,0], that range is special
937 enough to special case when vr1's range is relatively wide.
938 At least for types bigger than int - this covers pointers
939 and arguments to functions like ctz. */
940 else if (*vr0min
== *vr0max
941 && integer_zerop (*vr0min
)
942 && ((TYPE_PRECISION (TREE_TYPE (*vr0min
))
943 >= TYPE_PRECISION (integer_type_node
))
944 || POINTER_TYPE_P (TREE_TYPE (*vr0min
)))
945 && TREE_CODE (vr1max
) == INTEGER_CST
946 && TREE_CODE (vr1min
) == INTEGER_CST
947 && (wi::clz (wi::to_wide (vr1max
) - wi::to_wide (vr1min
))
948 < TYPE_PRECISION (TREE_TYPE (*vr0min
)) / 2))
950 /* Else choose the range. */
958 else if (*vr0type
== VR_ANTI_RANGE
959 && vr1type
== VR_ANTI_RANGE
)
961 /* If both are anti-ranges the result is the outer one. */
966 else if (vr1type
== VR_ANTI_RANGE
967 && *vr0type
== VR_RANGE
)
969 /* The intersection is empty. */
970 *vr0type
= VR_UNDEFINED
;
977 else if ((operand_less_p (vr1min
, *vr0max
) == 1
978 || operand_equal_p (vr1min
, *vr0max
, 0))
979 && operand_less_p (*vr0min
, vr1min
) == 1
980 && operand_less_p (*vr0max
, vr1max
) == 1)
982 /* [ ( ] ) or [ ]( ) */
983 if (*vr0type
== VR_ANTI_RANGE
984 && vr1type
== VR_ANTI_RANGE
)
986 else if (*vr0type
== VR_RANGE
987 && vr1type
== VR_RANGE
)
989 else if (*vr0type
== VR_RANGE
990 && vr1type
== VR_ANTI_RANGE
)
992 if (TREE_CODE (vr1min
) == INTEGER_CST
)
993 *vr0max
= int_const_binop (MINUS_EXPR
, vr1min
,
994 build_int_cst (TREE_TYPE (vr1min
), 1));
998 else if (*vr0type
== VR_ANTI_RANGE
999 && vr1type
== VR_RANGE
)
1001 *vr0type
= VR_RANGE
;
1002 if (TREE_CODE (*vr0max
) == INTEGER_CST
)
1003 *vr0min
= int_const_binop (PLUS_EXPR
, *vr0max
,
1004 build_int_cst (TREE_TYPE (*vr0max
), 1));
1012 else if ((operand_less_p (*vr0min
, vr1max
) == 1
1013 || operand_equal_p (*vr0min
, vr1max
, 0))
1014 && operand_less_p (vr1min
, *vr0min
) == 1
1015 && operand_less_p (vr1max
, *vr0max
) == 1)
1017 /* ( [ ) ] or ( )[ ] */
1018 if (*vr0type
== VR_ANTI_RANGE
1019 && vr1type
== VR_ANTI_RANGE
)
1021 else if (*vr0type
== VR_RANGE
1022 && vr1type
== VR_RANGE
)
1024 else if (*vr0type
== VR_RANGE
1025 && vr1type
== VR_ANTI_RANGE
)
1027 if (TREE_CODE (vr1max
) == INTEGER_CST
)
1028 *vr0min
= int_const_binop (PLUS_EXPR
, vr1max
,
1029 build_int_cst (TREE_TYPE (vr1max
), 1));
1033 else if (*vr0type
== VR_ANTI_RANGE
1034 && vr1type
== VR_RANGE
)
1036 *vr0type
= VR_RANGE
;
1037 if (TREE_CODE (*vr0min
) == INTEGER_CST
)
1038 *vr0max
= int_const_binop (MINUS_EXPR
, *vr0min
,
1039 build_int_cst (TREE_TYPE (*vr0min
), 1));
1048 /* If we know the intersection is empty, there's no need to
1049 conservatively add anything else to the set. */
1050 if (*vr0type
== VR_UNDEFINED
)
1053 /* As a fallback simply use { *VRTYPE, *VR0MIN, *VR0MAX } as
1054 result for the intersection. That's always a conservative
1055 correct estimate unless VR1 is a constant singleton range
1056 in which case we choose that. */
1057 if (vr1type
== VR_RANGE
1058 && is_gimple_min_invariant (vr1min
)
1059 && vrp_operand_equal_p (vr1min
, vr1max
))
1067 /* Helper for the intersection operation for value ranges. Given two
1068 ranges VR0 and VR1, set VR0 to the intersection of both ranges.
1069 This may not be the smallest possible such range. */
1072 irange::legacy_intersect (irange
*vr0
, const irange
*vr1
)
1074 gcc_checking_assert (vr0
->legacy_mode_p ());
1075 gcc_checking_assert (vr1
->legacy_mode_p ());
1076 /* If either range is VR_VARYING the other one wins. */
1077 if (vr1
->varying_p ())
1079 if (vr0
->varying_p ())
1081 vr0
->set (vr1
->min (), vr1
->max (), vr1
->kind ());
1085 /* When either range is VR_UNDEFINED the resulting range is
1086 VR_UNDEFINED, too. */
1087 if (vr0
->undefined_p ())
1089 if (vr1
->undefined_p ())
1091 vr0
->set_undefined ();
1095 value_range_kind vr0kind
= vr0
->kind ();
1096 tree vr0min
= vr0
->min ();
1097 tree vr0max
= vr0
->max ();
1099 intersect_ranges (&vr0kind
, &vr0min
, &vr0max
,
1100 vr1
->kind (), vr1
->min (), vr1
->max ());
1102 /* Make sure to canonicalize the result though as the inversion of a
1103 VR_RANGE can still be a VR_RANGE. */
1104 if (vr0kind
== VR_UNDEFINED
)
1105 vr0
->set_undefined ();
1106 else if (vr0kind
== VR_VARYING
)
1108 /* If we failed, use the original VR0. */
1112 vr0
->set (vr0min
, vr0max
, vr0kind
);
1115 /* Union the two value-ranges { *VR0TYPE, *VR0MIN, *VR0MAX } and
1116 { VR1TYPE, VR0MIN, VR0MAX } and store the result
1117 in { *VR0TYPE, *VR0MIN, *VR0MAX }. This may not be the smallest
1118 possible such range. The resulting range is not canonicalized. */
1121 union_ranges (enum value_range_kind
*vr0type
,
1122 tree
*vr0min
, tree
*vr0max
,
1123 enum value_range_kind vr1type
,
1124 tree vr1min
, tree vr1max
)
1126 int cmpmin
= compare_values (*vr0min
, vr1min
);
1127 int cmpmax
= compare_values (*vr0max
, vr1max
);
1128 bool mineq
= cmpmin
== 0;
1129 bool maxeq
= cmpmax
== 0;
1131 /* [] is vr0, () is vr1 in the following classification comments. */
1135 if (*vr0type
== vr1type
)
1136 /* Nothing to do for equal ranges. */
1138 else if ((*vr0type
== VR_RANGE
1139 && vr1type
== VR_ANTI_RANGE
)
1140 || (*vr0type
== VR_ANTI_RANGE
1141 && vr1type
== VR_RANGE
))
1143 /* For anti-range with range union the result is varying. */
1149 else if (operand_less_p (*vr0max
, vr1min
) == 1
1150 || operand_less_p (vr1max
, *vr0min
) == 1)
1152 /* [ ] ( ) or ( ) [ ]
1153 If the ranges have an empty intersection, result of the union
1154 operation is the anti-range or if both are anti-ranges
1156 if (*vr0type
== VR_ANTI_RANGE
1157 && vr1type
== VR_ANTI_RANGE
)
1159 else if (*vr0type
== VR_ANTI_RANGE
1160 && vr1type
== VR_RANGE
)
1162 else if (*vr0type
== VR_RANGE
1163 && vr1type
== VR_ANTI_RANGE
)
1169 else if (*vr0type
== VR_RANGE
1170 && vr1type
== VR_RANGE
)
1172 /* The result is the convex hull of both ranges. */
1173 if (operand_less_p (*vr0max
, vr1min
) == 1)
1175 /* If the result can be an anti-range, create one. */
1176 if (TREE_CODE (*vr0max
) == INTEGER_CST
1177 && TREE_CODE (vr1min
) == INTEGER_CST
1178 && vrp_val_is_min (*vr0min
)
1179 && vrp_val_is_max (vr1max
))
1181 tree min
= int_const_binop (PLUS_EXPR
,
1183 build_int_cst (TREE_TYPE (*vr0max
), 1));
1184 tree max
= int_const_binop (MINUS_EXPR
,
1186 build_int_cst (TREE_TYPE (vr1min
), 1));
1187 if (!operand_less_p (max
, min
))
1189 *vr0type
= VR_ANTI_RANGE
;
1201 /* If the result can be an anti-range, create one. */
1202 if (TREE_CODE (vr1max
) == INTEGER_CST
1203 && TREE_CODE (*vr0min
) == INTEGER_CST
1204 && vrp_val_is_min (vr1min
)
1205 && vrp_val_is_max (*vr0max
))
1207 tree min
= int_const_binop (PLUS_EXPR
,
1209 build_int_cst (TREE_TYPE (vr1max
), 1));
1210 tree max
= int_const_binop (MINUS_EXPR
,
1212 build_int_cst (TREE_TYPE (*vr0min
), 1));
1213 if (!operand_less_p (max
, min
))
1215 *vr0type
= VR_ANTI_RANGE
;
1229 else if ((maxeq
|| cmpmax
== 1)
1230 && (mineq
|| cmpmin
== -1))
1232 /* [ ( ) ] or [( ) ] or [ ( )] */
1233 if (*vr0type
== VR_RANGE
1234 && vr1type
== VR_RANGE
)
1236 else if (*vr0type
== VR_ANTI_RANGE
1237 && vr1type
== VR_ANTI_RANGE
)
1243 else if (*vr0type
== VR_ANTI_RANGE
1244 && vr1type
== VR_RANGE
)
1246 /* Arbitrarily choose the right or left gap. */
1247 if (!mineq
&& TREE_CODE (vr1min
) == INTEGER_CST
)
1248 *vr0max
= int_const_binop (MINUS_EXPR
, vr1min
,
1249 build_int_cst (TREE_TYPE (vr1min
), 1));
1250 else if (!maxeq
&& TREE_CODE (vr1max
) == INTEGER_CST
)
1251 *vr0min
= int_const_binop (PLUS_EXPR
, vr1max
,
1252 build_int_cst (TREE_TYPE (vr1max
), 1));
1256 else if (*vr0type
== VR_RANGE
1257 && vr1type
== VR_ANTI_RANGE
)
1258 /* The result covers everything. */
1263 else if ((maxeq
|| cmpmax
== -1)
1264 && (mineq
|| cmpmin
== 1))
1266 /* ( [ ] ) or ([ ] ) or ( [ ]) */
1267 if (*vr0type
== VR_RANGE
1268 && vr1type
== VR_RANGE
)
1274 else if (*vr0type
== VR_ANTI_RANGE
1275 && vr1type
== VR_ANTI_RANGE
)
1277 else if (*vr0type
== VR_RANGE
1278 && vr1type
== VR_ANTI_RANGE
)
1280 *vr0type
= VR_ANTI_RANGE
;
1281 if (!mineq
&& TREE_CODE (*vr0min
) == INTEGER_CST
)
1283 *vr0max
= int_const_binop (MINUS_EXPR
, *vr0min
,
1284 build_int_cst (TREE_TYPE (*vr0min
), 1));
1287 else if (!maxeq
&& TREE_CODE (*vr0max
) == INTEGER_CST
)
1289 *vr0min
= int_const_binop (PLUS_EXPR
, *vr0max
,
1290 build_int_cst (TREE_TYPE (*vr0max
), 1));
1296 else if (*vr0type
== VR_ANTI_RANGE
1297 && vr1type
== VR_RANGE
)
1298 /* The result covers everything. */
1303 else if (cmpmin
== -1
1305 && (operand_less_p (vr1min
, *vr0max
) == 1
1306 || operand_equal_p (vr1min
, *vr0max
, 0)))
1308 /* [ ( ] ) or [ ]( ) */
1309 if (*vr0type
== VR_RANGE
1310 && vr1type
== VR_RANGE
)
1312 else if (*vr0type
== VR_ANTI_RANGE
1313 && vr1type
== VR_ANTI_RANGE
)
1315 else if (*vr0type
== VR_ANTI_RANGE
1316 && vr1type
== VR_RANGE
)
1318 if (TREE_CODE (vr1min
) == INTEGER_CST
)
1319 *vr0max
= int_const_binop (MINUS_EXPR
, vr1min
,
1320 build_int_cst (TREE_TYPE (vr1min
), 1));
1324 else if (*vr0type
== VR_RANGE
1325 && vr1type
== VR_ANTI_RANGE
)
1327 if (TREE_CODE (*vr0max
) == INTEGER_CST
)
1330 *vr0min
= int_const_binop (PLUS_EXPR
, *vr0max
,
1331 build_int_cst (TREE_TYPE (*vr0max
), 1));
1340 else if (cmpmin
== 1
1342 && (operand_less_p (*vr0min
, vr1max
) == 1
1343 || operand_equal_p (*vr0min
, vr1max
, 0)))
1345 /* ( [ ) ] or ( )[ ] */
1346 if (*vr0type
== VR_RANGE
1347 && vr1type
== VR_RANGE
)
1349 else if (*vr0type
== VR_ANTI_RANGE
1350 && vr1type
== VR_ANTI_RANGE
)
1352 else if (*vr0type
== VR_ANTI_RANGE
1353 && vr1type
== VR_RANGE
)
1355 if (TREE_CODE (vr1max
) == INTEGER_CST
)
1356 *vr0min
= int_const_binop (PLUS_EXPR
, vr1max
,
1357 build_int_cst (TREE_TYPE (vr1max
), 1));
1361 else if (*vr0type
== VR_RANGE
1362 && vr1type
== VR_ANTI_RANGE
)
1364 if (TREE_CODE (*vr0min
) == INTEGER_CST
)
1367 *vr0max
= int_const_binop (MINUS_EXPR
, *vr0min
,
1368 build_int_cst (TREE_TYPE (*vr0min
), 1));
1383 *vr0type
= VR_VARYING
;
1384 *vr0min
= NULL_TREE
;
1385 *vr0max
= NULL_TREE
;
1388 /* Helper for meet operation for value ranges. Given two ranges VR0
1389 and VR1, set VR0 to the union of both ranges. This may not be the
1390 smallest possible such range. */
1393 irange::legacy_union (irange
*vr0
, const irange
*vr1
)
1395 gcc_checking_assert (vr0
->legacy_mode_p ());
1396 gcc_checking_assert (vr1
->legacy_mode_p ());
1398 /* VR0 has the resulting range if VR1 is undefined or VR0 is varying. */
1399 if (vr1
->undefined_p ()
1400 || vr0
->varying_p ())
1403 /* VR1 has the resulting range if VR0 is undefined or VR1 is varying. */
1404 if (vr0
->undefined_p ())
1406 vr0
->set (vr1
->min (), vr1
->max (), vr1
->kind ());
1410 if (vr1
->varying_p ())
1412 vr0
->set_varying (vr1
->type ());
1416 value_range_kind vr0kind
= vr0
->kind ();
1417 tree vr0min
= vr0
->min ();
1418 tree vr0max
= vr0
->max ();
1420 union_ranges (&vr0kind
, &vr0min
, &vr0max
,
1421 vr1
->kind (), vr1
->min (), vr1
->max ());
1423 if (vr0kind
== VR_UNDEFINED
)
1424 vr0
->set_undefined ();
1425 else if (vr0kind
== VR_VARYING
)
1427 /* Failed to find an efficient meet. Before giving up and
1428 setting the result to VARYING, see if we can at least derive
1429 a non-zero range. */
1430 if (range_includes_zero_p (vr0
) == 0
1431 && range_includes_zero_p (vr1
) == 0)
1432 vr0
->set_nonzero (vr0
->type ());
1434 vr0
->set_varying (vr0
->type ());
1437 vr0
->set (vr0min
, vr0max
, vr0kind
);
1440 /* Meet operation for value ranges. Given two value ranges VR0 and
1441 VR1, store in VR0 a range that contains both VR0 and VR1. This
1442 may not be the smallest possible such range. */
1445 irange::legacy_verbose_union_ (const irange
*other
)
1447 if (legacy_mode_p ())
1449 if (!other
->legacy_mode_p ())
1451 int_range
<1> tmp
= *other
;
1452 legacy_union (this, &tmp
);
1455 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1457 fprintf (dump_file
, "Meeting\n ");
1458 dump_value_range (dump_file
, this);
1459 fprintf (dump_file
, "\nand\n ");
1460 dump_value_range (dump_file
, other
);
1461 fprintf (dump_file
, "\n");
1464 legacy_union (this, other
);
1466 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1468 fprintf (dump_file
, "to\n ");
1469 dump_value_range (dump_file
, this);
1470 fprintf (dump_file
, "\n");
1475 if (other
->legacy_mode_p ())
1477 int_range
<2> wider
= *other
;
1478 irange_union (wider
);
1481 irange_union (*other
);
1485 irange::legacy_verbose_intersect (const irange
*other
)
1487 if (legacy_mode_p ())
1489 if (!other
->legacy_mode_p ())
1491 int_range
<1> tmp
= *other
;
1492 legacy_intersect (this, &tmp
);
1495 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1497 fprintf (dump_file
, "Intersecting\n ");
1498 dump_value_range (dump_file
, this);
1499 fprintf (dump_file
, "\nand\n ");
1500 dump_value_range (dump_file
, other
);
1501 fprintf (dump_file
, "\n");
1504 legacy_intersect (this, other
);
1506 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1508 fprintf (dump_file
, "to\n ");
1509 dump_value_range (dump_file
, this);
1510 fprintf (dump_file
, "\n");
1515 if (other
->legacy_mode_p ())
1519 irange_intersect (wider
);
1522 irange_intersect (*other
);
1525 // union_ for multi-ranges.
1528 irange::irange_union (const irange
&r
)
1530 gcc_checking_assert (!legacy_mode_p () && !r
.legacy_mode_p ());
1532 if (r
.undefined_p () || varying_p ())
1535 if (undefined_p () || r
.varying_p ())
1541 // Do not worry about merging and such by reserving twice as many
1542 // pairs as needed, and then simply sort the 2 ranges into this
1543 // intermediate form.
1545 // The intermediate result will have the property that the beginning
1546 // of each range is <= the beginning of the next range. There may
1547 // be overlapping ranges at this point. I.e. this would be valid
1548 // [-20, 10], [-10, 0], [0, 20], [40, 90] as it satisfies this
1549 // contraint : -20 < -10 < 0 < 40. When the range is rebuilt into r,
1550 // the merge is performed.
1552 // [Xi,Yi]..[Xn,Yn] U [Xj,Yj]..[Xm,Ym] --> [Xk,Yk]..[Xp,Yp]
1553 auto_vec
<tree
, 20> res (m_num_ranges
* 2 + r
.m_num_ranges
* 2);
1554 unsigned i
= 0, j
= 0, k
= 0;
1556 while (i
< m_num_ranges
* 2 && j
< r
.m_num_ranges
* 2)
1558 // lower of Xi and Xj is the lowest point.
1559 if (wi::to_widest (m_base
[i
]) <= wi::to_widest (r
.m_base
[j
]))
1561 res
.quick_push (m_base
[i
]);
1562 res
.quick_push (m_base
[i
+ 1]);
1568 res
.quick_push (r
.m_base
[j
]);
1569 res
.quick_push (r
.m_base
[j
+ 1]);
1574 for ( ; i
< m_num_ranges
* 2; i
+= 2)
1576 res
.quick_push (m_base
[i
]);
1577 res
.quick_push (m_base
[i
+ 1]);
1580 for ( ; j
< r
.m_num_ranges
* 2; j
+= 2)
1582 res
.quick_push (r
.m_base
[j
]);
1583 res
.quick_push (r
.m_base
[j
+ 1]);
1587 // Now normalize the vector removing any overlaps.
1589 for (j
= 2; j
< k
; j
+= 2)
1591 // Current upper+1 is >= lower bound next pair, then we merge ranges.
1592 if (wi::to_widest (res
[i
- 1]) + 1 >= wi::to_widest (res
[j
]))
1594 // New upper bounds is greater of current or the next one.
1595 if (wi::to_widest (res
[j
+ 1]) > wi::to_widest (res
[i
- 1]))
1596 res
[i
- 1] = res
[j
+ 1];
1600 // This is a new distinct range, but no point in copying it
1601 // if it is already in the right place.
1605 res
[i
++] = res
[j
+ 1];
1612 // At this point, the vector should have i ranges, none overlapping.
1613 // Now it simply needs to be copied, and if there are too many
1614 // ranges, merge some. We wont do any analysis as to what the
1615 // "best" merges are, simply combine the final ranges into one.
1616 if (i
> m_max_ranges
* 2)
1618 res
[m_max_ranges
* 2 - 1] = res
[i
- 1];
1619 i
= m_max_ranges
* 2;
1622 for (j
= 0; j
< i
; j
++)
1623 m_base
[j
] = res
[j
];
1624 m_num_ranges
= i
/ 2;
1633 // intersect for multi-ranges.
1636 irange::irange_intersect (const irange
&r
)
1638 gcc_checking_assert (!legacy_mode_p () && !r
.legacy_mode_p ());
1639 gcc_checking_assert (undefined_p () || r
.undefined_p ()
1640 || range_compatible_p (type (), r
.type ()));
1642 if (undefined_p () || r
.varying_p ())
1644 if (r
.undefined_p ())
1655 if (r
.num_pairs () == 1)
1657 // R cannot be undefined, use more efficent pair routine.
1658 intersect (r
.lower_bound(), r
.upper_bound ());
1662 signop sign
= TYPE_SIGN (TREE_TYPE(m_base
[0]));
1663 unsigned bld_pair
= 0;
1664 unsigned bld_lim
= m_max_ranges
;
1665 int_range_max
r2 (*this);
1666 unsigned r2_lim
= r2
.num_pairs ();
1668 for (unsigned i
= 0; i
< r
.num_pairs (); )
1670 // If r1's upper is < r2's lower, we can skip r1's pair.
1671 tree ru
= r
.m_base
[i
* 2 + 1];
1672 tree r2l
= r2
.m_base
[i2
* 2];
1673 if (wi::lt_p (wi::to_wide (ru
), wi::to_wide (r2l
), sign
))
1678 // Likewise, skip r2's pair if its excluded.
1679 tree r2u
= r2
.m_base
[i2
* 2 + 1];
1680 tree rl
= r
.m_base
[i
* 2];
1681 if (wi::lt_p (wi::to_wide (r2u
), wi::to_wide (rl
), sign
))
1686 // No more r2, break.
1690 // Must be some overlap. Find the highest of the lower bounds,
1691 // and set it, unless the build limits lower bounds is already
1693 if (bld_pair
< bld_lim
)
1695 if (wi::ge_p (wi::to_wide (rl
), wi::to_wide (r2l
), sign
))
1696 m_base
[bld_pair
* 2] = rl
;
1698 m_base
[bld_pair
* 2] = r2l
;
1701 // Decrease and set a new upper.
1704 // ...and choose the lower of the upper bounds.
1705 if (wi::le_p (wi::to_wide (ru
), wi::to_wide (r2u
), sign
))
1707 m_base
[bld_pair
* 2 + 1] = ru
;
1709 // Move past the r1 pair and keep trying.
1715 m_base
[bld_pair
* 2 + 1] = r2u
;
1720 // No more r2, break.
1723 // r2 has the higher lower bound.
1726 // At the exit of this loop, it is one of 2 things:
1727 // ran out of r1, or r2, but either means we are done.
1728 m_num_ranges
= bld_pair
;
1737 // Multirange intersect for a specified wide_int [lb, ub] range.
1740 irange::intersect (const wide_int
& lb
, const wide_int
& ub
)
1742 // Undefined remains undefined.
1746 if (legacy_mode_p ())
1748 intersect (int_range
<1> (type (), lb
, ub
));
1752 tree range_type
= type();
1753 signop sign
= TYPE_SIGN (range_type
);
1755 gcc_checking_assert (TYPE_PRECISION (range_type
) == wi::get_precision (lb
));
1756 gcc_checking_assert (TYPE_PRECISION (range_type
) == wi::get_precision (ub
));
1758 unsigned bld_index
= 0;
1759 unsigned pair_lim
= num_pairs ();
1760 for (unsigned i
= 0; i
< pair_lim
; i
++)
1762 tree pairl
= m_base
[i
* 2];
1763 tree pairu
= m_base
[i
* 2 + 1];
1764 // Once UB is less than a pairs lower bound, we're done.
1765 if (wi::lt_p (ub
, wi::to_wide (pairl
), sign
))
1767 // if LB is greater than this pairs upper, this pair is excluded.
1768 if (wi::lt_p (wi::to_wide (pairu
), lb
, sign
))
1771 // Must be some overlap. Find the highest of the lower bounds,
1773 if (wi::gt_p (lb
, wi::to_wide (pairl
), sign
))
1774 m_base
[bld_index
* 2] = wide_int_to_tree (range_type
, lb
);
1776 m_base
[bld_index
* 2] = pairl
;
1778 // ...and choose the lower of the upper bounds and if the base pair
1779 // has the lower upper bound, need to check next pair too.
1780 if (wi::lt_p (ub
, wi::to_wide (pairu
), sign
))
1782 m_base
[bld_index
++ * 2 + 1] = wide_int_to_tree (range_type
, ub
);
1786 m_base
[bld_index
++ * 2 + 1] = pairu
;
1789 m_num_ranges
= bld_index
;
1797 // Signed 1-bits are strange. You can't subtract 1, because you can't
1798 // represent the number 1. This works around that for the invert routine.
1800 static wide_int
inline
1801 subtract_one (const wide_int
&x
, tree type
, wi::overflow_type
&overflow
)
1803 if (TYPE_SIGN (type
) == SIGNED
)
1804 return wi::add (x
, -1, SIGNED
, &overflow
);
1806 return wi::sub (x
, 1, UNSIGNED
, &overflow
);
1809 // The analogous function for adding 1.
1811 static wide_int
inline
1812 add_one (const wide_int
&x
, tree type
, wi::overflow_type
&overflow
)
1814 if (TYPE_SIGN (type
) == SIGNED
)
1815 return wi::sub (x
, -1, SIGNED
, &overflow
);
1817 return wi::add (x
, 1, UNSIGNED
, &overflow
);
1820 // Return the inverse of a range.
1825 if (legacy_mode_p ())
1827 // We can't just invert VR_RANGE and VR_ANTI_RANGE because we may
1828 // create non-canonical ranges. Use the constructors instead.
1829 if (m_kind
== VR_RANGE
)
1830 *this = value_range (min (), max (), VR_ANTI_RANGE
);
1831 else if (m_kind
== VR_ANTI_RANGE
)
1832 *this = value_range (min (), max ());
1838 gcc_checking_assert (!undefined_p () && !varying_p ());
1840 // We always need one more set of bounds to represent an inverse, so
1841 // if we're at the limit, we can't properly represent things.
1843 // For instance, to represent the inverse of a 2 sub-range set
1844 // [5, 10][20, 30], we would need a 3 sub-range set
1845 // [-MIN, 4][11, 19][31, MAX].
1847 // In this case, return the most conservative thing.
1849 // However, if any of the extremes of the range are -MIN/+MAX, we
1850 // know we will not need an extra bound. For example:
1852 // INVERT([-MIN,20][30,40]) => [21,29][41,+MAX]
1853 // INVERT([-MIN,20][30,MAX]) => [21,29]
1854 tree ttype
= type ();
1855 unsigned prec
= TYPE_PRECISION (ttype
);
1856 signop sign
= TYPE_SIGN (ttype
);
1857 wide_int type_min
= wi::min_value (prec
, sign
);
1858 wide_int type_max
= wi::max_value (prec
, sign
);
1859 if (m_num_ranges
== m_max_ranges
1860 && lower_bound () != type_min
1861 && upper_bound () != type_max
)
1863 m_base
[1] = wide_int_to_tree (ttype
, type_max
);
1867 // The algorithm is as follows. To calculate INVERT ([a,b][c,d]), we
1868 // generate [-MIN, a-1][b+1, c-1][d+1, MAX].
1870 // If there is an over/underflow in the calculation for any
1871 // sub-range, we eliminate that subrange. This allows us to easily
1872 // calculate INVERT([-MIN, 5]) with: [-MIN, -MIN-1][6, MAX]. And since
1873 // we eliminate the underflow, only [6, MAX] remains.
1875 wi::overflow_type ovf
;
1876 // Construct leftmost range.
1877 int_range_max
orig_range (*this);
1878 unsigned nitems
= 0;
1880 // If this is going to underflow on the MINUS 1, don't even bother
1881 // checking. This also handles subtracting one from an unsigned 0,
1882 // which doesn't set the underflow bit.
1883 if (type_min
!= orig_range
.lower_bound ())
1885 m_base
[nitems
++] = wide_int_to_tree (ttype
, type_min
);
1886 tmp
= subtract_one (orig_range
.lower_bound (), ttype
, ovf
);
1887 m_base
[nitems
++] = wide_int_to_tree (ttype
, tmp
);
1892 // Construct middle ranges if applicable.
1893 if (orig_range
.num_pairs () > 1)
1896 for (; j
< (orig_range
.num_pairs () * 2) - 1; j
+= 2)
1898 // The middle ranges cannot have MAX/MIN, so there's no need
1899 // to check for unsigned overflow on the +1 and -1 here.
1900 tmp
= wi::add (wi::to_wide (orig_range
.m_base
[j
]), 1, sign
, &ovf
);
1901 m_base
[nitems
++] = wide_int_to_tree (ttype
, tmp
);
1902 tmp
= subtract_one (wi::to_wide (orig_range
.m_base
[j
+ 1]),
1904 m_base
[nitems
++] = wide_int_to_tree (ttype
, tmp
);
1910 // Construct rightmost range.
1912 // However, if this will overflow on the PLUS 1, don't even bother.
1913 // This also handles adding one to an unsigned MAX, which doesn't
1914 // set the overflow bit.
1915 if (type_max
!= wi::to_wide (orig_range
.m_base
[i
]))
1917 tmp
= add_one (wi::to_wide (orig_range
.m_base
[i
]), ttype
, ovf
);
1918 m_base
[nitems
++] = wide_int_to_tree (ttype
, tmp
);
1919 m_base
[nitems
++] = wide_int_to_tree (ttype
, type_max
);
1923 m_num_ranges
= nitems
/ 2;
1925 // We disallow undefined or varying coming in, so the result can
1926 // only be a VR_RANGE.
1927 gcc_checking_assert (m_kind
== VR_RANGE
);
1934 dump_bound_with_infinite_markers (FILE *file
, tree bound
)
1936 tree type
= TREE_TYPE (bound
);
1937 wide_int type_min
= wi::min_value (TYPE_PRECISION (type
), TYPE_SIGN (type
));
1938 wide_int type_max
= wi::max_value (TYPE_PRECISION (type
), TYPE_SIGN (type
));
1940 if (INTEGRAL_TYPE_P (type
)
1941 && !TYPE_UNSIGNED (type
)
1942 && TREE_CODE (bound
) == INTEGER_CST
1943 && wi::to_wide (bound
) == type_min
1944 && TYPE_PRECISION (type
) != 1)
1945 fprintf (file
, "-INF");
1946 else if (TREE_CODE (bound
) == INTEGER_CST
1947 && wi::to_wide (bound
) == type_max
1948 && TYPE_PRECISION (type
) != 1)
1949 fprintf (file
, "+INF");
1951 print_generic_expr (file
, bound
);
1955 irange::dump (FILE *file
) const
1959 fprintf (file
, "UNDEFINED");
1962 print_generic_expr (file
, type ());
1963 fprintf (file
, " ");
1966 fprintf (file
, "VARYING");
1969 if (legacy_mode_p ())
1971 fprintf (file
, "%s[", (m_kind
== VR_ANTI_RANGE
) ? "~" : "");
1972 dump_bound_with_infinite_markers (file
, min ());
1973 fprintf (file
, ", ");
1974 dump_bound_with_infinite_markers (file
, max ());
1975 fprintf (file
, "]");
1978 for (unsigned i
= 0; i
< m_num_ranges
; ++i
)
1980 tree lb
= m_base
[i
* 2];
1981 tree ub
= m_base
[i
* 2 + 1];
1982 fprintf (file
, "[");
1983 dump_bound_with_infinite_markers (file
, lb
);
1984 fprintf (file
, ", ");
1985 dump_bound_with_infinite_markers (file
, ub
);
1986 fprintf (file
, "]");
1991 irange::debug () const
1994 fprintf (stderr
, "\n");
1998 dump_value_range (FILE *file
, const irange
*vr
)
2004 debug (const irange
*vr
)
2006 dump_value_range (stderr
, vr
);
2007 fprintf (stderr
, "\n");
2011 debug (const irange
&vr
)
2017 debug (const value_range
*vr
)
2019 dump_value_range (stderr
, vr
);
2020 fprintf (stderr
, "\n");
2024 debug (const value_range
&vr
)
2026 dump_value_range (stderr
, &vr
);
2027 fprintf (stderr
, "\n");
2030 /* Create two value-ranges in *VR0 and *VR1 from the anti-range *AR
2031 so that *VR0 U *VR1 == *AR. Returns true if that is possible,
2032 false otherwise. If *AR can be represented with a single range
2033 *VR1 will be VR_UNDEFINED. */
2036 ranges_from_anti_range (const value_range
*ar
,
2037 value_range
*vr0
, value_range
*vr1
)
2039 tree type
= ar
->type ();
2041 vr0
->set_undefined ();
2042 vr1
->set_undefined ();
2044 /* As a future improvement, we could handle ~[0, A] as: [-INF, -1] U
2045 [A+1, +INF]. Not sure if this helps in practice, though. */
2047 if (ar
->kind () != VR_ANTI_RANGE
2048 || TREE_CODE (ar
->min ()) != INTEGER_CST
2049 || TREE_CODE (ar
->max ()) != INTEGER_CST
2050 || !vrp_val_min (type
)
2051 || !vrp_val_max (type
))
2054 if (tree_int_cst_lt (vrp_val_min (type
), ar
->min ()))
2055 vr0
->set (vrp_val_min (type
),
2056 wide_int_to_tree (type
, wi::to_wide (ar
->min ()) - 1));
2057 if (tree_int_cst_lt (ar
->max (), vrp_val_max (type
)))
2058 vr1
->set (wide_int_to_tree (type
, wi::to_wide (ar
->max ()) + 1),
2059 vrp_val_max (type
));
2060 if (vr0
->undefined_p ())
2063 vr1
->set_undefined ();
2066 return !vr0
->undefined_p ();
2070 range_has_numeric_bounds_p (const irange
*vr
)
2072 return (!vr
->undefined_p ()
2073 && TREE_CODE (vr
->min ()) == INTEGER_CST
2074 && TREE_CODE (vr
->max ()) == INTEGER_CST
);
2077 /* Return whether VAL is equal to the maximum value of its type.
2078 We can't do a simple equality comparison with TYPE_MAX_VALUE because
2079 C typedefs and Ada subtypes can produce types whose TYPE_MAX_VALUE
2080 is not == to the integer constant with the same value in the type. */
2083 vrp_val_is_max (const_tree val
)
2085 tree type_max
= vrp_val_max (TREE_TYPE (val
));
2086 return (val
== type_max
2087 || (type_max
!= NULL_TREE
2088 && operand_equal_p (val
, type_max
, 0)));
2091 /* Return whether VAL is equal to the minimum value of its type. */
2094 vrp_val_is_min (const_tree val
)
2096 tree type_min
= vrp_val_min (TREE_TYPE (val
));
2097 return (val
== type_min
2098 || (type_min
!= NULL_TREE
2099 && operand_equal_p (val
, type_min
, 0)));
2102 /* Return true, if VAL1 and VAL2 are equal values for VRP purposes. */
2105 vrp_operand_equal_p (const_tree val1
, const_tree val2
)
2109 if (!val1
|| !val2
|| !operand_equal_p (val1
, val2
, 0))
2114 // ?? These stubs are for ipa-prop.cc which use a value_range in a
2115 // hash_traits. hash-traits.h defines an extern of gt_ggc_mx (T &)
2116 // instead of picking up the gt_ggc_mx (T *) version.
2118 gt_pch_nx (int_range
<1> *&x
)
2120 return gt_pch_nx ((irange
*) x
);
2124 gt_ggc_mx (int_range
<1> *&x
)
2126 return gt_ggc_mx ((irange
*) x
);
2129 #define DEFINE_INT_RANGE_INSTANCE(N) \
2130 template int_range<N>::int_range(tree, tree, value_range_kind); \
2131 template int_range<N>::int_range(tree_node *, \
2134 value_range_kind); \
2135 template int_range<N>::int_range(tree); \
2136 template int_range<N>::int_range(const irange &); \
2137 template int_range<N>::int_range(const int_range &); \
2138 template int_range<N>& int_range<N>::operator= (const int_range &);
2140 DEFINE_INT_RANGE_INSTANCE(1)
2141 DEFINE_INT_RANGE_INSTANCE(2)
2142 DEFINE_INT_RANGE_INSTANCE(3)
2143 DEFINE_INT_RANGE_INSTANCE(255)
2146 #include "selftest.h"
2150 #define INT(N) build_int_cst (integer_type_node, (N))
2151 #define UINT(N) build_int_cstu (unsigned_type_node, (N))
2152 #define UINT128(N) build_int_cstu (u128_type, (N))
2153 #define UCHAR(N) build_int_cstu (unsigned_char_type_node, (N))
2154 #define SCHAR(N) build_int_cst (signed_char_type_node, (N))
2157 build_range3 (int a
, int b
, int c
, int d
, int e
, int f
)
2159 int_range
<3> i1 (INT (a
), INT (b
));
2160 int_range
<3> i2 (INT (c
), INT (d
));
2161 int_range
<3> i3 (INT (e
), INT (f
));
2168 range_tests_irange3 ()
2170 typedef int_range
<3> int_range3
;
2171 int_range3 r0
, r1
, r2
;
2172 int_range3 i1
, i2
, i3
;
2174 // ([10,20] U [5,8]) U [1,3] ==> [1,3][5,8][10,20].
2175 r0
= int_range3 (INT (10), INT (20));
2176 r1
= int_range3 (INT (5), INT (8));
2178 r1
= int_range3 (INT (1), INT (3));
2180 ASSERT_TRUE (r0
== build_range3 (1, 3, 5, 8, 10, 20));
2182 // [1,3][5,8][10,20] U [-5,0] => [-5,3][5,8][10,20].
2183 r1
= int_range3 (INT (-5), INT (0));
2185 ASSERT_TRUE (r0
== build_range3 (-5, 3, 5, 8, 10, 20));
2187 // [10,20][30,40] U [50,60] ==> [10,20][30,40][50,60].
2188 r1
= int_range3 (INT (50), INT (60));
2189 r0
= int_range3 (INT (10), INT (20));
2190 r0
.union_ (int_range3 (INT (30), INT (40)));
2192 ASSERT_TRUE (r0
== build_range3 (10, 20, 30, 40, 50, 60));
2193 // [10,20][30,40][50,60] U [70, 80] ==> [10,20][30,40][50,60][70,80].
2194 r1
= int_range3 (INT (70), INT (80));
2197 r2
= build_range3 (10, 20, 30, 40, 50, 60);
2198 r2
.union_ (int_range3 (INT (70), INT (80)));
2199 ASSERT_TRUE (r0
== r2
);
2201 // [10,20][30,40][50,60] U [6,35] => [6,40][50,60].
2202 r0
= build_range3 (10, 20, 30, 40, 50, 60);
2203 r1
= int_range3 (INT (6), INT (35));
2205 r1
= int_range3 (INT (6), INT (40));
2206 r1
.union_ (int_range3 (INT (50), INT (60)));
2207 ASSERT_TRUE (r0
== r1
);
2209 // [10,20][30,40][50,60] U [6,60] => [6,60].
2210 r0
= build_range3 (10, 20, 30, 40, 50, 60);
2211 r1
= int_range3 (INT (6), INT (60));
2213 ASSERT_TRUE (r0
== int_range3 (INT (6), INT (60)));
2215 // [10,20][30,40][50,60] U [6,70] => [6,70].
2216 r0
= build_range3 (10, 20, 30, 40, 50, 60);
2217 r1
= int_range3 (INT (6), INT (70));
2219 ASSERT_TRUE (r0
== int_range3 (INT (6), INT (70)));
2221 // [10,20][30,40][50,60] U [35,70] => [10,20][30,70].
2222 r0
= build_range3 (10, 20, 30, 40, 50, 60);
2223 r1
= int_range3 (INT (35), INT (70));
2225 r1
= int_range3 (INT (10), INT (20));
2226 r1
.union_ (int_range3 (INT (30), INT (70)));
2227 ASSERT_TRUE (r0
== r1
);
2229 // [10,20][30,40][50,60] U [15,35] => [10,40][50,60].
2230 r0
= build_range3 (10, 20, 30, 40, 50, 60);
2231 r1
= int_range3 (INT (15), INT (35));
2233 r1
= int_range3 (INT (10), INT (40));
2234 r1
.union_ (int_range3 (INT (50), INT (60)));
2235 ASSERT_TRUE (r0
== r1
);
2237 // [10,20][30,40][50,60] U [35,35] => [10,20][30,40][50,60].
2238 r0
= build_range3 (10, 20, 30, 40, 50, 60);
2239 r1
= int_range3 (INT (35), INT (35));
2241 ASSERT_TRUE (r0
== build_range3 (10, 20, 30, 40, 50, 60));
2245 range_tests_int_range_max ()
2248 unsigned int nrange
;
2250 // Build a huge multi-range range.
2251 for (nrange
= 0; nrange
< 50; ++nrange
)
2253 int_range
<1> tmp (INT (nrange
*10), INT (nrange
*10 + 5));
2256 ASSERT_TRUE (big
.num_pairs () == nrange
);
2258 // Verify that we can copy it without loosing precision.
2259 int_range_max
copy (big
);
2260 ASSERT_TRUE (copy
.num_pairs () == nrange
);
2262 // Inverting it should produce one more sub-range.
2264 ASSERT_TRUE (big
.num_pairs () == nrange
+ 1);
2266 int_range
<1> tmp (INT (5), INT (37));
2267 big
.intersect (tmp
);
2268 ASSERT_TRUE (big
.num_pairs () == 4);
2270 // Test that [10,10][20,20] does NOT contain 15.
2272 int_range_max
i1 (build_int_cst (integer_type_node
, 10),
2273 build_int_cst (integer_type_node
, 10));
2274 int_range_max
i2 (build_int_cst (integer_type_node
, 20),
2275 build_int_cst (integer_type_node
, 20));
2277 ASSERT_FALSE (i1
.contains_p (build_int_cst (integer_type_node
, 15)));
2282 range_tests_legacy ()
2284 // Test truncating copy to int_range<1>.
2285 int_range
<3> big
= build_range3 (10, 20, 30, 40, 50, 60);
2286 int_range
<1> small
= big
;
2287 ASSERT_TRUE (small
== int_range
<1> (INT (10), INT (60)));
2289 // Test truncating copy to int_range<2>.
2290 int_range
<2> medium
= big
;
2291 ASSERT_TRUE (!medium
.undefined_p ());
2293 // Test that a truncating copy of [MIN,20][22,40][80,MAX]
2294 // ends up as a conservative anti-range of ~[21,21].
2295 big
= int_range
<3> (vrp_val_min (integer_type_node
), INT (20));
2296 big
.union_ (int_range
<1> (INT (22), INT (40)));
2297 big
.union_ (int_range
<1> (INT (80), vrp_val_max (integer_type_node
)));
2299 ASSERT_TRUE (small
== int_range
<1> (INT (21), INT (21), VR_ANTI_RANGE
));
2301 // Copying a legacy symbolic to an int_range should normalize the
2302 // symbolic at copy time.
2304 tree ssa
= make_ssa_name (integer_type_node
);
2305 value_range
legacy_range (ssa
, INT (25));
2306 int_range
<2> copy
= legacy_range
;
2307 ASSERT_TRUE (copy
== int_range
<2> (vrp_val_min (integer_type_node
),
2310 // Test that copying ~[abc_23, abc_23] to a multi-range yields varying.
2311 legacy_range
= value_range (ssa
, ssa
, VR_ANTI_RANGE
);
2312 copy
= legacy_range
;
2313 ASSERT_TRUE (copy
.varying_p ());
2316 // VARYING of different sizes should not be equal.
2317 tree big_type
= build_nonstandard_integer_type (32, 1);
2318 tree small_type
= build_nonstandard_integer_type (16, 1);
2319 int_range_max
r0 (big_type
);
2320 int_range_max
r1 (small_type
);
2321 ASSERT_TRUE (r0
!= r1
);
2322 value_range
vr0 (big_type
);
2323 int_range_max
vr1 (small_type
);
2324 ASSERT_TRUE (vr0
!= vr1
);
2327 // Simulate -fstrict-enums where the domain of a type is less than the
2331 range_tests_strict_enum ()
2333 // The enum can only hold [0, 3].
2334 tree rtype
= copy_node (unsigned_type_node
);
2335 TYPE_MIN_VALUE (rtype
) = build_int_cstu (rtype
, 0);
2336 TYPE_MAX_VALUE (rtype
) = build_int_cstu (rtype
, 3);
2338 // Test that even though vr1 covers the strict enum domain ([0, 3]),
2339 // it does not cover the domain of the underlying type.
2340 int_range
<1> vr1 (build_int_cstu (rtype
, 0), build_int_cstu (rtype
, 1));
2341 int_range
<1> vr2 (build_int_cstu (rtype
, 2), build_int_cstu (rtype
, 3));
2343 ASSERT_TRUE (vr1
== int_range
<1> (build_int_cstu (rtype
, 0),
2344 build_int_cstu (rtype
, 3)));
2345 ASSERT_FALSE (vr1
.varying_p ());
2347 // Test that copying to a multi-range does not change things.
2348 int_range
<2> ir1 (vr1
);
2349 ASSERT_TRUE (ir1
== vr1
);
2350 ASSERT_FALSE (ir1
.varying_p ());
2352 // The same test as above, but using TYPE_{MIN,MAX}_VALUE instead of [0,3].
2353 vr1
= int_range
<1> (TYPE_MIN_VALUE (rtype
), TYPE_MAX_VALUE (rtype
));
2355 ASSERT_TRUE (ir1
== vr1
);
2356 ASSERT_FALSE (ir1
.varying_p ());
2362 tree u128_type
= build_nonstandard_integer_type (128, /*unsigned=*/1);
2363 int_range
<1> i1
, i2
, i3
;
2364 int_range
<1> r0
, r1
, rold
;
2366 // Test 1-bit signed integer union.
2367 // [-1,-1] U [0,0] = VARYING.
2368 tree one_bit_type
= build_nonstandard_integer_type (1, 0);
2369 tree one_bit_min
= vrp_val_min (one_bit_type
);
2370 tree one_bit_max
= vrp_val_max (one_bit_type
);
2372 int_range
<2> min (one_bit_min
, one_bit_min
);
2373 int_range
<2> max (one_bit_max
, one_bit_max
);
2375 ASSERT_TRUE (max
.varying_p ());
2378 // Test inversion of 1-bit signed integers.
2380 int_range
<2> min (one_bit_min
, one_bit_min
);
2381 int_range
<2> max (one_bit_max
, one_bit_max
);
2385 ASSERT_TRUE (t
== max
);
2388 ASSERT_TRUE (t
== min
);
2391 // Test that NOT(255) is [0..254] in 8-bit land.
2392 int_range
<1> not_255 (UCHAR (255), UCHAR (255), VR_ANTI_RANGE
);
2393 ASSERT_TRUE (not_255
== int_range
<1> (UCHAR (0), UCHAR (254)));
2395 // Test that NOT(0) is [1..255] in 8-bit land.
2396 int_range
<1> not_zero
= range_nonzero (unsigned_char_type_node
);
2397 ASSERT_TRUE (not_zero
== int_range
<1> (UCHAR (1), UCHAR (255)));
2399 // Check that [0,127][0x..ffffff80,0x..ffffff]
2400 // => ~[128, 0x..ffffff7f].
2401 r0
= int_range
<1> (UINT128 (0), UINT128 (127));
2402 tree high
= build_minus_one_cst (u128_type
);
2403 // low = -1 - 127 => 0x..ffffff80.
2404 tree low
= fold_build2 (MINUS_EXPR
, u128_type
, high
, UINT128(127));
2405 r1
= int_range
<1> (low
, high
); // [0x..ffffff80, 0x..ffffffff]
2406 // r0 = [0,127][0x..ffffff80,0x..fffffff].
2408 // r1 = [128, 0x..ffffff7f].
2409 r1
= int_range
<1> (UINT128(128),
2410 fold_build2 (MINUS_EXPR
, u128_type
,
2411 build_minus_one_cst (u128_type
),
2414 ASSERT_TRUE (r0
== r1
);
2416 r0
.set_varying (integer_type_node
);
2417 tree minint
= wide_int_to_tree (integer_type_node
, r0
.lower_bound ());
2418 tree maxint
= wide_int_to_tree (integer_type_node
, r0
.upper_bound ());
2420 r0
.set_varying (short_integer_type_node
);
2422 r0
.set_varying (unsigned_type_node
);
2423 tree maxuint
= wide_int_to_tree (unsigned_type_node
, r0
.upper_bound ());
2425 // Check that ~[0,5] => [6,MAX] for unsigned int.
2426 r0
= int_range
<1> (UINT (0), UINT (5));
2428 ASSERT_TRUE (r0
== int_range
<1> (UINT(6), maxuint
));
2430 // Check that ~[10,MAX] => [0,9] for unsigned int.
2431 r0
= int_range
<1> (UINT(10), maxuint
);
2433 ASSERT_TRUE (r0
== int_range
<1> (UINT (0), UINT (9)));
2435 // Check that ~[0,5] => [6,MAX] for unsigned 128-bit numbers.
2436 r0
= int_range
<1> (UINT128 (0), UINT128 (5), VR_ANTI_RANGE
);
2437 r1
= int_range
<1> (UINT128(6), build_minus_one_cst (u128_type
));
2438 ASSERT_TRUE (r0
== r1
);
2440 // Check that [~5] is really [-MIN,4][6,MAX].
2441 r0
= int_range
<1> (INT (5), INT (5), VR_ANTI_RANGE
);
2442 r1
= int_range
<1> (minint
, INT (4));
2443 r1
.union_ (int_range
<1> (INT (6), maxint
));
2444 ASSERT_FALSE (r1
.undefined_p ());
2445 ASSERT_TRUE (r0
== r1
);
2447 r1
= int_range
<1> (INT (5), INT (5));
2448 int_range
<1> r2 (r1
);
2449 ASSERT_TRUE (r1
== r2
);
2451 r1
= int_range
<1> (INT (5), INT (10));
2453 r1
= int_range
<1> (integer_type_node
,
2454 wi::to_wide (INT (5)), wi::to_wide (INT (10)));
2455 ASSERT_TRUE (r1
.contains_p (INT (7)));
2457 r1
= int_range
<1> (SCHAR (0), SCHAR (20));
2458 ASSERT_TRUE (r1
.contains_p (SCHAR(15)));
2459 ASSERT_FALSE (r1
.contains_p (SCHAR(300)));
2461 // NOT([10,20]) ==> [-MIN,9][21,MAX].
2462 r0
= r1
= int_range
<1> (INT (10), INT (20));
2463 r2
= int_range
<1> (minint
, INT(9));
2464 r2
.union_ (int_range
<1> (INT(21), maxint
));
2465 ASSERT_FALSE (r2
.undefined_p ());
2467 ASSERT_TRUE (r1
== r2
);
2468 // Test that NOT(NOT(x)) == x.
2470 ASSERT_TRUE (r0
== r2
);
2472 // Test that booleans and their inverse work as expected.
2473 r0
= range_zero (boolean_type_node
);
2474 ASSERT_TRUE (r0
== int_range
<1> (build_zero_cst (boolean_type_node
),
2475 build_zero_cst (boolean_type_node
)));
2477 ASSERT_TRUE (r0
== int_range
<1> (build_one_cst (boolean_type_node
),
2478 build_one_cst (boolean_type_node
)));
2480 // Make sure NULL and non-NULL of pointer types work, and that
2481 // inverses of them are consistent.
2482 tree voidp
= build_pointer_type (void_type_node
);
2483 r0
= range_zero (voidp
);
2487 ASSERT_TRUE (r0
== r1
);
2489 // [10,20] U [15, 30] => [10, 30].
2490 r0
= int_range
<1> (INT (10), INT (20));
2491 r1
= int_range
<1> (INT (15), INT (30));
2493 ASSERT_TRUE (r0
== int_range
<1> (INT (10), INT (30)));
2495 // [15,40] U [] => [15,40].
2496 r0
= int_range
<1> (INT (15), INT (40));
2497 r1
.set_undefined ();
2499 ASSERT_TRUE (r0
== int_range
<1> (INT (15), INT (40)));
2501 // [10,20] U [10,10] => [10,20].
2502 r0
= int_range
<1> (INT (10), INT (20));
2503 r1
= int_range
<1> (INT (10), INT (10));
2505 ASSERT_TRUE (r0
== int_range
<1> (INT (10), INT (20)));
2507 // [10,20] U [9,9] => [9,20].
2508 r0
= int_range
<1> (INT (10), INT (20));
2509 r1
= int_range
<1> (INT (9), INT (9));
2511 ASSERT_TRUE (r0
== int_range
<1> (INT (9), INT (20)));
2513 // [10,20] ^ [15,30] => [15,20].
2514 r0
= int_range
<1> (INT (10), INT (20));
2515 r1
= int_range
<1> (INT (15), INT (30));
2517 ASSERT_TRUE (r0
== int_range
<1> (INT (15), INT (20)));
2519 // Test the internal sanity of wide_int's wrt HWIs.
2520 ASSERT_TRUE (wi::max_value (TYPE_PRECISION (boolean_type_node
),
2521 TYPE_SIGN (boolean_type_node
))
2522 == wi::uhwi (1, TYPE_PRECISION (boolean_type_node
)));
2525 r0
= int_range
<1> (INT (0), INT (0));
2526 ASSERT_TRUE (r0
.zero_p ());
2528 // Test nonzero_p().
2529 r0
= int_range
<1> (INT (0), INT (0));
2531 ASSERT_TRUE (r0
.nonzero_p ());
2533 // test legacy interaction
2535 r0
= int_range
<1> (UINT (1), UINT (1), VR_ANTI_RANGE
);
2537 r1
= int_range
<1> (UINT (3), UINT (3), VR_ANTI_RANGE
);
2539 // vv = [0,0][2,2][4, MAX]
2540 int_range
<3> vv
= r0
;
2543 ASSERT_TRUE (vv
.contains_p (UINT (2)));
2544 ASSERT_TRUE (vv
.num_pairs () == 3);
2546 // create r0 as legacy [1,1]
2547 r0
= int_range
<1> (UINT (1), UINT (1));
2548 // And union it with [0,0][2,2][4,MAX] multi range
2550 // The result should be [0,2][4,MAX], or ~[3,3] but it must contain 2
2551 ASSERT_TRUE (r0
.contains_p (UINT (2)));
2557 range_tests_legacy ();
2558 range_tests_irange3 ();
2559 range_tests_int_range_max ();
2560 range_tests_strict_enum ();
2561 range_tests_misc ();
2564 } // namespace selftest
2566 #endif // CHECKING_P