1 /* Support routines for value ranges.
2 Copyright (C) 2019-2020 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
)
38 if (legacy_mode_p () != src
.legacy_mode_p ())
40 copy_legacy_range (src
);
45 gcc_checking_assert (src
.legacy_mode_p ());
46 m_num_ranges
= src
.m_num_ranges
;
47 m_base
[0] = src
.m_base
[0];
48 m_base
[1] = src
.m_base
[1];
54 unsigned lim
= src
.m_num_ranges
;
55 if (lim
> m_max_ranges
)
58 for (x
= 0; x
< lim
* 2; ++x
)
59 m_base
[x
] = src
.m_base
[x
];
61 // If the range didn't fit, the last range should cover the rest.
62 if (lim
!= src
.m_num_ranges
)
63 m_base
[x
- 1] = src
.m_base
[src
.m_num_ranges
* 2 - 1];
69 // Return TRUE if range is a multi-range that can be represented as a
73 irange::maybe_anti_range () const
76 unsigned int precision
= TYPE_PRECISION (ttype
);
77 signop sign
= TYPE_SIGN (ttype
);
78 return (num_pairs () > 1
80 && lower_bound () == wi::min_value (precision
, sign
)
81 && upper_bound () == wi::max_value (precision
, sign
));
84 // Copy between a legacy and a multi-range, or vice-versa.
87 irange::copy_legacy_range (const irange
&src
)
89 gcc_checking_assert (src
.legacy_mode_p () != legacy_mode_p ());
90 if (src
.undefined_p ())
92 else if (src
.varying_p ())
93 set_varying (src
.type ());
94 else if (src
.kind () == VR_ANTI_RANGE
)
95 set (src
.min (), src
.max (), VR_ANTI_RANGE
);
96 else if (legacy_mode_p () && src
.maybe_anti_range ())
98 int_range
<3> tmp (src
);
100 set (tmp
.min (), wide_int_to_tree (src
.type (), tmp
.upper_bound (0)),
104 set (src
.min (), src
.max (), VR_RANGE
);
107 // Swap min/max if they are out of order. Return TRUE if further
108 // processing of the range is necessary, FALSE otherwise.
111 irange::swap_out_of_order_endpoints (tree
&min
, tree
&max
,
112 value_range_kind
&kind
)
114 /* Wrong order for min and max, to swap them and the VR type we need
116 if (tree_int_cst_lt (max
, min
))
120 /* For one bit precision if max < min, then the swapped
121 range covers all values, so for VR_RANGE it is varying and
122 for VR_ANTI_RANGE empty range, so drop to varying as well. */
123 if (TYPE_PRECISION (TREE_TYPE (min
)) == 1)
125 set_varying (TREE_TYPE (min
));
129 one
= build_int_cst (TREE_TYPE (min
), 1);
130 tmp
= int_const_binop (PLUS_EXPR
, max
, one
);
131 max
= int_const_binop (MINUS_EXPR
, min
, one
);
134 /* There's one corner case, if we had [C+1, C] before we now have
135 that again. But this represents an empty value range, so drop
136 to varying in this case. */
137 if (tree_int_cst_lt (max
, min
))
139 set_varying (TREE_TYPE (min
));
142 kind
= kind
== VR_RANGE
? VR_ANTI_RANGE
: VR_RANGE
;
148 irange::irange_set (tree min
, tree max
)
150 gcc_checking_assert (!POLY_INT_CST_P (min
));
151 gcc_checking_assert (!POLY_INT_CST_P (max
));
161 irange::irange_set_anti_range (tree min
, tree max
)
163 gcc_checking_assert (!POLY_INT_CST_P (min
));
164 gcc_checking_assert (!POLY_INT_CST_P (max
));
167 tree type
= TREE_TYPE (min
);
168 signop sign
= TYPE_SIGN (type
);
169 int_range
<2> type_range (type
);
170 // Calculate INVERSE([I,J]) as [-MIN, I-1][J+1, +MAX].
172 wi::overflow_type ovf
;
174 wide_int w_min
= wi::to_wide (min
);
175 if (wi::ne_p (w_min
, type_range
.lower_bound ()))
177 wide_int lim1
= wi::sub (w_min
, 1, sign
, &ovf
);
178 gcc_checking_assert (ovf
!= wi::OVF_OVERFLOW
);
179 m_base
[0] = type_range
.tree_lower_bound (0);
180 m_base
[1] = wide_int_to_tree (type
, lim1
);
183 wide_int w_max
= wi::to_wide (max
);
184 if (wi::ne_p (w_max
, type_range
.upper_bound ()))
186 wide_int lim2
= wi::add (w_max
, 1, sign
, &ovf
);
187 gcc_checking_assert (ovf
!= wi::OVF_OVERFLOW
);
188 m_base
[m_num_ranges
* 2] = wide_int_to_tree (type
, lim2
);
189 m_base
[m_num_ranges
* 2 + 1] = type_range
.tree_upper_bound (0);
196 /* Set value range to the canonical form of {VRTYPE, MIN, MAX, EQUIV}.
197 This means adjusting VRTYPE, MIN and MAX representing the case of a
198 wrapping range with MAX < MIN covering [MIN, type_max] U [type_min, MAX]
199 as anti-rage ~[MAX+1, MIN-1]. Likewise for wrapping anti-ranges.
200 In corner cases where MAX+1 or MIN-1 wraps this will fall back
202 This routine exists to ease canonicalization in the case where we
203 extract ranges from var + CST op limit. */
206 irange::set (tree min
, tree max
, value_range_kind kind
)
208 if (!legacy_mode_p ())
210 if (kind
== VR_RANGE
)
211 irange_set (min
, max
);
214 gcc_checking_assert (kind
== VR_ANTI_RANGE
);
215 irange_set_anti_range (min
, max
);
219 if (kind
== VR_UNDEFINED
)
224 if (kind
== VR_RANGE
)
226 /* Convert POLY_INT_CST bounds into worst-case INTEGER_CST bounds. */
227 if (POLY_INT_CST_P (min
))
229 tree type_min
= vrp_val_min (TREE_TYPE (min
));
231 = constant_lower_bound_with_limit (wi::to_poly_widest (min
),
232 wi::to_widest (type_min
));
233 min
= wide_int_to_tree (TREE_TYPE (min
), lb
);
235 if (POLY_INT_CST_P (max
))
237 tree type_max
= vrp_val_max (TREE_TYPE (max
));
239 = constant_upper_bound_with_limit (wi::to_poly_widest (max
),
240 wi::to_widest (type_max
));
241 max
= wide_int_to_tree (TREE_TYPE (max
), ub
);
244 else if (kind
!= VR_VARYING
)
246 if (POLY_INT_CST_P (min
) || POLY_INT_CST_P (max
))
249 if (kind
== VR_VARYING
)
251 set_varying (TREE_TYPE (min
));
255 tree type
= TREE_TYPE (min
);
256 // Nothing to canonicalize for symbolic ranges.
257 if (TREE_CODE (min
) != INTEGER_CST
258 || TREE_CODE (max
) != INTEGER_CST
)
266 if (!swap_out_of_order_endpoints (min
, max
, kind
))
269 // Anti-ranges that can be represented as ranges should be so.
270 if (kind
== VR_ANTI_RANGE
)
272 /* For -fstrict-enums we may receive out-of-range ranges so consider
273 values < -INF and values > INF as -INF/INF as well. */
274 bool is_min
= vrp_val_is_min (min
);
275 bool is_max
= vrp_val_is_max (max
);
277 if (is_min
&& is_max
)
279 /* We cannot deal with empty ranges, drop to varying.
280 ??? This could be VR_UNDEFINED instead. */
284 else if (TYPE_PRECISION (TREE_TYPE (min
)) == 1
285 && (is_min
|| is_max
))
287 /* Non-empty boolean ranges can always be represented
288 as a singleton range. */
290 min
= max
= vrp_val_max (TREE_TYPE (min
));
292 min
= max
= vrp_val_min (TREE_TYPE (min
));
297 tree one
= build_int_cst (TREE_TYPE (max
), 1);
298 min
= int_const_binop (PLUS_EXPR
, max
, one
);
299 max
= vrp_val_max (TREE_TYPE (max
));
304 tree one
= build_int_cst (TREE_TYPE (min
), 1);
305 max
= int_const_binop (MINUS_EXPR
, min
, one
);
306 min
= vrp_val_min (TREE_TYPE (min
));
310 else if (!swap_out_of_order_endpoints (min
, max
, kind
))
313 /* Do not drop [-INF(OVF), +INF(OVF)] to varying. (OVF) has to be sticky
314 to make sure VRP iteration terminates, otherwise we can get into
316 if (!normalize_min_max (type
, min
, max
, kind
))
327 // Avoid using TYPE_{MIN,MAX}_VALUE because -fstrict-enums can
328 // restrict those to a subset of what actually fits in the type.
329 // Instead use the extremes of the type precision
330 unsigned prec
= TYPE_PRECISION (type
);
331 signop sign
= TYPE_SIGN (type
);
332 if (wi::eq_p (wi::to_wide (min
), wi::min_value (prec
, sign
))
333 && wi::eq_p (wi::to_wide (max
), wi::max_value (prec
, sign
)))
335 else if (undefined_p ())
336 m_kind
= VR_UNDEFINED
;
341 /* Check the validity of the range. */
344 irange::verify_range ()
346 if (!legacy_mode_p ())
348 gcc_checking_assert (m_kind
== VR_RANGE
);
349 for (unsigned i
= 0; i
< m_num_ranges
; ++i
)
351 tree lb
= tree_lower_bound (i
);
352 tree ub
= tree_upper_bound (i
);
353 int c
= compare_values (lb
, ub
);
354 gcc_assert (c
== 0 || c
== -1);
362 gcc_assert (m_num_ranges
== 0);
366 gcc_assert (m_num_ranges
== 1);
372 gcc_assert (m_num_ranges
== 1);
373 int cmp
= compare_values (tree_lower_bound (0), tree_upper_bound (0));
374 gcc_assert (cmp
== 0 || cmp
== -1 || cmp
== -2);
384 irange::legacy_num_pairs () const
386 gcc_checking_assert (legacy_mode_p ());
392 // Inlined symbolic_p for performance:
393 if (!is_gimple_min_invariant (min ()) || !is_gimple_min_invariant (max ()))
395 value_range
numeric_range (*this);
396 numeric_range
.normalize_symbolics ();
397 return numeric_range
.num_pairs ();
399 if (m_kind
== VR_ANTI_RANGE
)
401 // ~[MIN, X] has one sub-range of [X+1, MAX], and
402 // ~[X, MAX] has one sub-range of [MIN, X-1].
403 if (vrp_val_is_min (min ()) || vrp_val_is_max (max ()))
407 gcc_checking_assert (m_num_ranges
== 1);
411 // Return the lower bound for a sub-range. PAIR is the sub-range in
415 irange::legacy_lower_bound (unsigned pair
) const
417 gcc_checking_assert (legacy_mode_p ());
420 value_range
numeric_range (*this);
421 numeric_range
.normalize_symbolics ();
422 return numeric_range
.legacy_lower_bound (pair
);
424 gcc_checking_assert (!undefined_p ());
425 gcc_checking_assert (pair
+ 1 <= num_pairs ());
426 if (m_kind
== VR_ANTI_RANGE
)
428 tree typ
= type (), t
;
429 if (pair
== 1 || vrp_val_is_min (min ()))
430 t
= wide_int_to_tree (typ
, wi::to_wide (max ()) + 1);
432 t
= vrp_val_min (typ
);
433 return wi::to_wide (t
);
435 return wi::to_wide (tree_lower_bound (pair
));
438 // Return the upper bound for a sub-range. PAIR is the sub-range in
442 irange::legacy_upper_bound (unsigned pair
) const
444 gcc_checking_assert (legacy_mode_p ());
447 value_range
numeric_range (*this);
448 numeric_range
.normalize_symbolics ();
449 return numeric_range
.legacy_upper_bound (pair
);
451 gcc_checking_assert (!undefined_p ());
452 gcc_checking_assert (pair
+ 1 <= num_pairs ());
453 if (m_kind
== VR_ANTI_RANGE
)
455 tree typ
= type (), t
;
456 if (pair
== 1 || vrp_val_is_min (min ()))
457 t
= vrp_val_max (typ
);
459 t
= wide_int_to_tree (typ
, wi::to_wide (min ()) - 1);
460 return wi::to_wide (t
);
462 return wi::to_wide (tree_upper_bound (pair
));
466 irange::legacy_equal_p (const irange
&other
) const
468 gcc_checking_assert (legacy_mode_p () && other
.legacy_mode_p ());
470 if (m_kind
!= other
.m_kind
)
472 if (m_kind
== VR_UNDEFINED
|| m_kind
== VR_VARYING
)
474 return (vrp_operand_equal_p (tree_lower_bound (0),
475 other
.tree_lower_bound (0))
476 && vrp_operand_equal_p (tree_upper_bound (0),
477 other
.tree_upper_bound (0)));
481 irange::equal_p (const irange
&other
) const
483 if (legacy_mode_p ())
485 if (other
.legacy_mode_p ())
486 return legacy_equal_p (other
);
487 value_range
tmp (other
);
488 return legacy_equal_p (tmp
);
490 if (other
.legacy_mode_p ())
492 value_range
tmp2 (*this);
493 return tmp2
.legacy_equal_p (other
);
496 if (m_num_ranges
!= other
.m_num_ranges
)
499 for (unsigned i
= 0; i
< m_num_ranges
; ++i
)
501 tree lb
= tree_lower_bound (i
);
502 tree ub
= tree_upper_bound (i
);
503 tree lb_other
= other
.tree_lower_bound (i
);
504 tree ub_other
= other
.tree_upper_bound (i
);
505 if (!operand_equal_p (lb
, lb_other
, 0)
506 || !operand_equal_p (ub
, ub_other
, 0))
512 /* Return TRUE if this is a symbolic range. */
515 irange::symbolic_p () const
517 return (!varying_p ()
519 && (!is_gimple_min_invariant (min ())
520 || !is_gimple_min_invariant (max ())));
523 /* NOTE: This is not the inverse of symbolic_p because the range
524 could also be varying or undefined. Ideally they should be inverse
525 of each other, with varying only applying to symbolics. Varying of
526 constants would be represented as [-MIN, +MAX]. */
529 irange::constant_p () const
531 return (!varying_p ()
533 && TREE_CODE (min ()) == INTEGER_CST
534 && TREE_CODE (max ()) == INTEGER_CST
);
537 /* If range is a singleton, place it in RESULT and return TRUE.
538 Note: A singleton can be any gimple invariant, not just constants.
539 So, [&x, &x] counts as a singleton. */
542 irange::singleton_p (tree
*result
) const
544 if (!legacy_mode_p ())
546 if (num_pairs () == 1 && (wi::to_wide (tree_lower_bound ())
547 == wi::to_wide (tree_upper_bound ())))
550 *result
= tree_lower_bound ();
555 if (m_kind
== VR_ANTI_RANGE
)
559 if (TYPE_PRECISION (type ()) == 1)
567 if (num_pairs () == 1)
569 value_range vr0
, vr1
;
570 ranges_from_anti_range ((const value_range
*) this, &vr0
, &vr1
);
571 return vr0
.singleton_p (result
);
574 // Catches non-numeric extremes as well.
575 if (m_kind
== VR_RANGE
576 && vrp_operand_equal_p (min (), max ())
577 && is_gimple_min_invariant (min ()))
586 /* Return 1 if VAL is inside value range.
587 0 if VAL is not inside value range.
588 -2 if we cannot tell either way.
590 Benchmark compile/20001226-1.c compilation time after changing this
594 irange::value_inside_range (tree val
) const
602 if (!legacy_mode_p () && TREE_CODE (val
) == INTEGER_CST
)
603 return contains_p (val
);
605 int cmp1
= operand_less_p (val
, min ());
609 return m_kind
!= VR_RANGE
;
611 int cmp2
= operand_less_p (max (), val
);
615 if (m_kind
== VR_RANGE
)
621 /* Return TRUE if it is possible that range contains VAL. */
624 irange::may_contain_p (tree val
) const
626 return value_inside_range (val
) != 0;
629 /* Return TRUE if range contains INTEGER_CST. */
630 /* Return 1 if VAL is inside value range.
631 0 if VAL is not inside value range.
633 Benchmark compile/20001226-1.c compilation time after changing this
638 irange::contains_p (tree cst
) const
643 if (legacy_mode_p ())
645 gcc_checking_assert (TREE_CODE (cst
) == INTEGER_CST
);
648 value_range
numeric_range (*this);
649 numeric_range
.normalize_symbolics ();
650 return numeric_range
.contains_p (cst
);
652 return value_inside_range (cst
) == 1;
655 gcc_checking_assert (TREE_CODE (cst
) == INTEGER_CST
);
656 signop sign
= TYPE_SIGN (TREE_TYPE (cst
));
657 wide_int v
= wi::to_wide (cst
);
658 for (unsigned r
= 0; r
< m_num_ranges
; ++r
)
660 if (wi::lt_p (v
, lower_bound (r
), sign
))
662 if (wi::le_p (v
, upper_bound (r
), sign
))
670 /* Normalize addresses into constants. */
673 irange::normalize_addresses ()
678 if (!POINTER_TYPE_P (type ()) || range_has_numeric_bounds_p (this))
681 if (!range_includes_zero_p (this))
683 gcc_checking_assert (TREE_CODE (min ()) == ADDR_EXPR
684 || TREE_CODE (max ()) == ADDR_EXPR
);
685 set_nonzero (type ());
688 set_varying (type ());
691 /* Normalize symbolics and addresses into constants. */
694 irange::normalize_symbolics ()
696 if (varying_p () || undefined_p ())
699 tree ttype
= type ();
700 bool min_symbolic
= !is_gimple_min_invariant (min ());
701 bool max_symbolic
= !is_gimple_min_invariant (max ());
702 if (!min_symbolic
&& !max_symbolic
)
704 normalize_addresses ();
708 // [SYM, SYM] -> VARYING
709 if (min_symbolic
&& max_symbolic
)
714 if (kind () == VR_RANGE
)
716 // [SYM, NUM] -> [-MIN, NUM]
719 set (vrp_val_min (ttype
), max ());
722 // [NUM, SYM] -> [NUM, +MAX]
723 set (min (), vrp_val_max (ttype
));
726 gcc_checking_assert (kind () == VR_ANTI_RANGE
);
727 // ~[SYM, NUM] -> [NUM + 1, +MAX]
730 if (!vrp_val_is_max (max ()))
732 tree n
= wide_int_to_tree (ttype
, wi::to_wide (max ()) + 1);
733 set (n
, vrp_val_max (ttype
));
739 // ~[NUM, SYM] -> [-MIN, NUM - 1]
740 if (!vrp_val_is_min (min ()))
742 tree n
= wide_int_to_tree (ttype
, wi::to_wide (min ()) - 1);
743 set (vrp_val_min (ttype
), n
);
749 /* Intersect the two value-ranges { *VR0TYPE, *VR0MIN, *VR0MAX } and
750 { VR1TYPE, VR0MIN, VR0MAX } and store the result
751 in { *VR0TYPE, *VR0MIN, *VR0MAX }. This may not be the smallest
752 possible such range. The resulting range is not canonicalized. */
755 intersect_ranges (enum value_range_kind
*vr0type
,
756 tree
*vr0min
, tree
*vr0max
,
757 enum value_range_kind vr1type
,
758 tree vr1min
, tree vr1max
)
760 bool mineq
= vrp_operand_equal_p (*vr0min
, vr1min
);
761 bool maxeq
= vrp_operand_equal_p (*vr0max
, vr1max
);
763 /* [] is vr0, () is vr1 in the following classification comments. */
767 if (*vr0type
== vr1type
)
768 /* Nothing to do for equal ranges. */
770 else if ((*vr0type
== VR_RANGE
771 && vr1type
== VR_ANTI_RANGE
)
772 || (*vr0type
== VR_ANTI_RANGE
773 && vr1type
== VR_RANGE
))
775 /* For anti-range with range intersection the result is empty. */
776 *vr0type
= VR_UNDEFINED
;
783 else if (operand_less_p (*vr0max
, vr1min
) == 1
784 || operand_less_p (vr1max
, *vr0min
) == 1)
786 /* [ ] ( ) or ( ) [ ]
787 If the ranges have an empty intersection, the result of the
788 intersect operation is the range for intersecting an
789 anti-range with a range or empty when intersecting two ranges. */
790 if (*vr0type
== VR_RANGE
791 && vr1type
== VR_ANTI_RANGE
)
793 else if (*vr0type
== VR_ANTI_RANGE
794 && vr1type
== VR_RANGE
)
800 else if (*vr0type
== VR_RANGE
801 && vr1type
== VR_RANGE
)
803 *vr0type
= VR_UNDEFINED
;
807 else if (*vr0type
== VR_ANTI_RANGE
808 && vr1type
== VR_ANTI_RANGE
)
810 /* If the anti-ranges are adjacent to each other merge them. */
811 if (TREE_CODE (*vr0max
) == INTEGER_CST
812 && TREE_CODE (vr1min
) == INTEGER_CST
813 && operand_less_p (*vr0max
, vr1min
) == 1
814 && integer_onep (int_const_binop (MINUS_EXPR
,
817 else if (TREE_CODE (vr1max
) == INTEGER_CST
818 && TREE_CODE (*vr0min
) == INTEGER_CST
819 && operand_less_p (vr1max
, *vr0min
) == 1
820 && integer_onep (int_const_binop (MINUS_EXPR
,
823 /* Else arbitrarily take VR0. */
826 else if ((maxeq
|| operand_less_p (vr1max
, *vr0max
) == 1)
827 && (mineq
|| operand_less_p (*vr0min
, vr1min
) == 1))
829 /* [ ( ) ] or [( ) ] or [ ( )] */
830 if (*vr0type
== VR_RANGE
831 && vr1type
== VR_RANGE
)
833 /* If both are ranges the result is the inner one. */
838 else if (*vr0type
== VR_RANGE
839 && vr1type
== VR_ANTI_RANGE
)
841 /* Choose the right gap if the left one is empty. */
844 if (TREE_CODE (vr1max
) != INTEGER_CST
)
846 else if (TYPE_PRECISION (TREE_TYPE (vr1max
)) == 1
847 && !TYPE_UNSIGNED (TREE_TYPE (vr1max
)))
849 = int_const_binop (MINUS_EXPR
, vr1max
,
850 build_int_cst (TREE_TYPE (vr1max
), -1));
853 = int_const_binop (PLUS_EXPR
, vr1max
,
854 build_int_cst (TREE_TYPE (vr1max
), 1));
856 /* Choose the left gap if the right one is empty. */
859 if (TREE_CODE (vr1min
) != INTEGER_CST
)
861 else if (TYPE_PRECISION (TREE_TYPE (vr1min
)) == 1
862 && !TYPE_UNSIGNED (TREE_TYPE (vr1min
)))
864 = int_const_binop (PLUS_EXPR
, vr1min
,
865 build_int_cst (TREE_TYPE (vr1min
), -1));
868 = int_const_binop (MINUS_EXPR
, vr1min
,
869 build_int_cst (TREE_TYPE (vr1min
), 1));
871 /* Choose the anti-range if the range is effectively varying. */
872 else if (vrp_val_is_min (*vr0min
)
873 && vrp_val_is_max (*vr0max
))
879 /* Else choose the range. */
881 else if (*vr0type
== VR_ANTI_RANGE
882 && vr1type
== VR_ANTI_RANGE
)
883 /* If both are anti-ranges the result is the outer one. */
885 else if (*vr0type
== VR_ANTI_RANGE
886 && vr1type
== VR_RANGE
)
888 /* The intersection is empty. */
889 *vr0type
= VR_UNDEFINED
;
896 else if ((maxeq
|| operand_less_p (*vr0max
, vr1max
) == 1)
897 && (mineq
|| operand_less_p (vr1min
, *vr0min
) == 1))
899 /* ( [ ] ) or ([ ] ) or ( [ ]) */
900 if (*vr0type
== VR_RANGE
901 && vr1type
== VR_RANGE
)
902 /* Choose the inner range. */
904 else if (*vr0type
== VR_ANTI_RANGE
905 && vr1type
== VR_RANGE
)
907 /* Choose the right gap if the left is empty. */
911 if (TREE_CODE (*vr0max
) != INTEGER_CST
)
913 else if (TYPE_PRECISION (TREE_TYPE (*vr0max
)) == 1
914 && !TYPE_UNSIGNED (TREE_TYPE (*vr0max
)))
916 = int_const_binop (MINUS_EXPR
, *vr0max
,
917 build_int_cst (TREE_TYPE (*vr0max
), -1));
920 = int_const_binop (PLUS_EXPR
, *vr0max
,
921 build_int_cst (TREE_TYPE (*vr0max
), 1));
924 /* Choose the left gap if the right is empty. */
928 if (TREE_CODE (*vr0min
) != INTEGER_CST
)
930 else if (TYPE_PRECISION (TREE_TYPE (*vr0min
)) == 1
931 && !TYPE_UNSIGNED (TREE_TYPE (*vr0min
)))
933 = int_const_binop (PLUS_EXPR
, *vr0min
,
934 build_int_cst (TREE_TYPE (*vr0min
), -1));
937 = int_const_binop (MINUS_EXPR
, *vr0min
,
938 build_int_cst (TREE_TYPE (*vr0min
), 1));
941 /* Choose the anti-range if the range is effectively varying. */
942 else if (vrp_val_is_min (vr1min
)
943 && vrp_val_is_max (vr1max
))
945 /* Choose the anti-range if it is ~[0,0], that range is special
946 enough to special case when vr1's range is relatively wide.
947 At least for types bigger than int - this covers pointers
948 and arguments to functions like ctz. */
949 else if (*vr0min
== *vr0max
950 && integer_zerop (*vr0min
)
951 && ((TYPE_PRECISION (TREE_TYPE (*vr0min
))
952 >= TYPE_PRECISION (integer_type_node
))
953 || POINTER_TYPE_P (TREE_TYPE (*vr0min
)))
954 && TREE_CODE (vr1max
) == INTEGER_CST
955 && TREE_CODE (vr1min
) == INTEGER_CST
956 && (wi::clz (wi::to_wide (vr1max
) - wi::to_wide (vr1min
))
957 < TYPE_PRECISION (TREE_TYPE (*vr0min
)) / 2))
959 /* Else choose the range. */
967 else if (*vr0type
== VR_ANTI_RANGE
968 && vr1type
== VR_ANTI_RANGE
)
970 /* If both are anti-ranges the result is the outer one. */
975 else if (vr1type
== VR_ANTI_RANGE
976 && *vr0type
== VR_RANGE
)
978 /* The intersection is empty. */
979 *vr0type
= VR_UNDEFINED
;
986 else if ((operand_less_p (vr1min
, *vr0max
) == 1
987 || operand_equal_p (vr1min
, *vr0max
, 0))
988 && operand_less_p (*vr0min
, vr1min
) == 1)
990 /* [ ( ] ) or [ ]( ) */
991 if (*vr0type
== VR_ANTI_RANGE
992 && vr1type
== VR_ANTI_RANGE
)
994 else if (*vr0type
== VR_RANGE
995 && vr1type
== VR_RANGE
)
997 else if (*vr0type
== VR_RANGE
998 && vr1type
== VR_ANTI_RANGE
)
1000 if (TREE_CODE (vr1min
) == INTEGER_CST
)
1001 *vr0max
= int_const_binop (MINUS_EXPR
, vr1min
,
1002 build_int_cst (TREE_TYPE (vr1min
), 1));
1006 else if (*vr0type
== VR_ANTI_RANGE
1007 && vr1type
== VR_RANGE
)
1009 *vr0type
= VR_RANGE
;
1010 if (TREE_CODE (*vr0max
) == INTEGER_CST
)
1011 *vr0min
= int_const_binop (PLUS_EXPR
, *vr0max
,
1012 build_int_cst (TREE_TYPE (*vr0max
), 1));
1020 else if ((operand_less_p (*vr0min
, vr1max
) == 1
1021 || operand_equal_p (*vr0min
, vr1max
, 0))
1022 && operand_less_p (vr1min
, *vr0min
) == 1)
1024 /* ( [ ) ] or ( )[ ] */
1025 if (*vr0type
== VR_ANTI_RANGE
1026 && vr1type
== VR_ANTI_RANGE
)
1028 else if (*vr0type
== VR_RANGE
1029 && vr1type
== VR_RANGE
)
1031 else if (*vr0type
== VR_RANGE
1032 && vr1type
== VR_ANTI_RANGE
)
1034 if (TREE_CODE (vr1max
) == INTEGER_CST
)
1035 *vr0min
= int_const_binop (PLUS_EXPR
, vr1max
,
1036 build_int_cst (TREE_TYPE (vr1max
), 1));
1040 else if (*vr0type
== VR_ANTI_RANGE
1041 && vr1type
== VR_RANGE
)
1043 *vr0type
= VR_RANGE
;
1044 if (TREE_CODE (*vr0min
) == INTEGER_CST
)
1045 *vr0max
= int_const_binop (MINUS_EXPR
, *vr0min
,
1046 build_int_cst (TREE_TYPE (*vr0min
), 1));
1055 /* If we know the intersection is empty, there's no need to
1056 conservatively add anything else to the set. */
1057 if (*vr0type
== VR_UNDEFINED
)
1060 /* As a fallback simply use { *VRTYPE, *VR0MIN, *VR0MAX } as
1061 result for the intersection. That's always a conservative
1062 correct estimate unless VR1 is a constant singleton range
1063 in which case we choose that. */
1064 if (vr1type
== VR_RANGE
1065 && is_gimple_min_invariant (vr1min
)
1066 && vrp_operand_equal_p (vr1min
, vr1max
))
1074 /* Helper for the intersection operation for value ranges. Given two
1075 ranges VR0 and VR1, set VR0 to the intersection of both ranges.
1076 This may not be the smallest possible such range. */
1079 irange::legacy_intersect (irange
*vr0
, const irange
*vr1
)
1081 /* If either range is VR_VARYING the other one wins. */
1082 if (vr1
->varying_p ())
1084 if (vr0
->varying_p ())
1086 /* Avoid the full copy if we already know both sides are simple
1087 and can be trivially copied. */
1088 if (vr1
->legacy_mode_p ())
1090 vr0
->set (vr1
->min (), vr1
->max (), vr1
->kind ());
1097 /* When either range is VR_UNDEFINED the resulting range is
1098 VR_UNDEFINED, too. */
1099 if (vr0
->undefined_p ())
1101 if (vr1
->undefined_p ())
1103 vr0
->set_undefined ();
1107 value_range_kind vr0kind
= vr0
->kind ();
1108 tree vr0min
= vr0
->min ();
1109 tree vr0max
= vr0
->max ();
1110 /* Handle multi-ranges that can be represented as anti-ranges. */
1111 if (!vr1
->legacy_mode_p () && vr1
->maybe_anti_range ())
1113 int_range
<3> tmp (*vr1
);
1115 intersect_ranges (&vr0kind
, &vr0min
, &vr0max
,
1116 VR_ANTI_RANGE
, tmp
.min (), tmp
.max ());
1119 intersect_ranges (&vr0kind
, &vr0min
, &vr0max
,
1120 vr1
->kind (), vr1
->min (), vr1
->max ());
1122 /* Make sure to canonicalize the result though as the inversion of a
1123 VR_RANGE can still be a VR_RANGE. */
1124 if (vr0kind
== VR_UNDEFINED
)
1125 vr0
->set_undefined ();
1126 else if (vr0kind
== VR_VARYING
)
1128 /* If we failed, use the original VR0. */
1132 vr0
->set (vr0min
, vr0max
, vr0kind
);
1135 /* Union the two value-ranges { *VR0TYPE, *VR0MIN, *VR0MAX } and
1136 { VR1TYPE, VR0MIN, VR0MAX } and store the result
1137 in { *VR0TYPE, *VR0MIN, *VR0MAX }. This may not be the smallest
1138 possible such range. The resulting range is not canonicalized. */
1141 union_ranges (enum value_range_kind
*vr0type
,
1142 tree
*vr0min
, tree
*vr0max
,
1143 enum value_range_kind vr1type
,
1144 tree vr1min
, tree vr1max
)
1146 int cmpmin
= compare_values (*vr0min
, vr1min
);
1147 int cmpmax
= compare_values (*vr0max
, vr1max
);
1148 bool mineq
= cmpmin
== 0;
1149 bool maxeq
= cmpmax
== 0;
1151 /* [] is vr0, () is vr1 in the following classification comments. */
1155 if (*vr0type
== vr1type
)
1156 /* Nothing to do for equal ranges. */
1158 else if ((*vr0type
== VR_RANGE
1159 && vr1type
== VR_ANTI_RANGE
)
1160 || (*vr0type
== VR_ANTI_RANGE
1161 && vr1type
== VR_RANGE
))
1163 /* For anti-range with range union the result is varying. */
1169 else if (operand_less_p (*vr0max
, vr1min
) == 1
1170 || operand_less_p (vr1max
, *vr0min
) == 1)
1172 /* [ ] ( ) or ( ) [ ]
1173 If the ranges have an empty intersection, result of the union
1174 operation is the anti-range or if both are anti-ranges
1176 if (*vr0type
== VR_ANTI_RANGE
1177 && vr1type
== VR_ANTI_RANGE
)
1179 else if (*vr0type
== VR_ANTI_RANGE
1180 && vr1type
== VR_RANGE
)
1182 else if (*vr0type
== VR_RANGE
1183 && vr1type
== VR_ANTI_RANGE
)
1189 else if (*vr0type
== VR_RANGE
1190 && vr1type
== VR_RANGE
)
1192 /* The result is the convex hull of both ranges. */
1193 if (operand_less_p (*vr0max
, vr1min
) == 1)
1195 /* If the result can be an anti-range, create one. */
1196 if (TREE_CODE (*vr0max
) == INTEGER_CST
1197 && TREE_CODE (vr1min
) == INTEGER_CST
1198 && vrp_val_is_min (*vr0min
)
1199 && vrp_val_is_max (vr1max
))
1201 tree min
= int_const_binop (PLUS_EXPR
,
1203 build_int_cst (TREE_TYPE (*vr0max
), 1));
1204 tree max
= int_const_binop (MINUS_EXPR
,
1206 build_int_cst (TREE_TYPE (vr1min
), 1));
1207 if (!operand_less_p (max
, min
))
1209 *vr0type
= VR_ANTI_RANGE
;
1221 /* If the result can be an anti-range, create one. */
1222 if (TREE_CODE (vr1max
) == INTEGER_CST
1223 && TREE_CODE (*vr0min
) == INTEGER_CST
1224 && vrp_val_is_min (vr1min
)
1225 && vrp_val_is_max (*vr0max
))
1227 tree min
= int_const_binop (PLUS_EXPR
,
1229 build_int_cst (TREE_TYPE (vr1max
), 1));
1230 tree max
= int_const_binop (MINUS_EXPR
,
1232 build_int_cst (TREE_TYPE (*vr0min
), 1));
1233 if (!operand_less_p (max
, min
))
1235 *vr0type
= VR_ANTI_RANGE
;
1249 else if ((maxeq
|| cmpmax
== 1)
1250 && (mineq
|| cmpmin
== -1))
1252 /* [ ( ) ] or [( ) ] or [ ( )] */
1253 if (*vr0type
== VR_RANGE
1254 && vr1type
== VR_RANGE
)
1256 else if (*vr0type
== VR_ANTI_RANGE
1257 && vr1type
== VR_ANTI_RANGE
)
1263 else if (*vr0type
== VR_ANTI_RANGE
1264 && vr1type
== VR_RANGE
)
1266 /* Arbitrarily choose the right or left gap. */
1267 if (!mineq
&& TREE_CODE (vr1min
) == INTEGER_CST
)
1268 *vr0max
= int_const_binop (MINUS_EXPR
, vr1min
,
1269 build_int_cst (TREE_TYPE (vr1min
), 1));
1270 else if (!maxeq
&& TREE_CODE (vr1max
) == INTEGER_CST
)
1271 *vr0min
= int_const_binop (PLUS_EXPR
, vr1max
,
1272 build_int_cst (TREE_TYPE (vr1max
), 1));
1276 else if (*vr0type
== VR_RANGE
1277 && vr1type
== VR_ANTI_RANGE
)
1278 /* The result covers everything. */
1283 else if ((maxeq
|| cmpmax
== -1)
1284 && (mineq
|| cmpmin
== 1))
1286 /* ( [ ] ) or ([ ] ) or ( [ ]) */
1287 if (*vr0type
== VR_RANGE
1288 && vr1type
== VR_RANGE
)
1294 else if (*vr0type
== VR_ANTI_RANGE
1295 && vr1type
== VR_ANTI_RANGE
)
1297 else if (*vr0type
== VR_RANGE
1298 && vr1type
== VR_ANTI_RANGE
)
1300 *vr0type
= VR_ANTI_RANGE
;
1301 if (!mineq
&& TREE_CODE (*vr0min
) == INTEGER_CST
)
1303 *vr0max
= int_const_binop (MINUS_EXPR
, *vr0min
,
1304 build_int_cst (TREE_TYPE (*vr0min
), 1));
1307 else if (!maxeq
&& TREE_CODE (*vr0max
) == INTEGER_CST
)
1309 *vr0min
= int_const_binop (PLUS_EXPR
, *vr0max
,
1310 build_int_cst (TREE_TYPE (*vr0max
), 1));
1316 else if (*vr0type
== VR_ANTI_RANGE
1317 && vr1type
== VR_RANGE
)
1318 /* The result covers everything. */
1323 else if (cmpmin
== -1
1325 && (operand_less_p (vr1min
, *vr0max
) == 1
1326 || operand_equal_p (vr1min
, *vr0max
, 0)))
1328 /* [ ( ] ) or [ ]( ) */
1329 if (*vr0type
== VR_RANGE
1330 && vr1type
== VR_RANGE
)
1332 else if (*vr0type
== VR_ANTI_RANGE
1333 && vr1type
== VR_ANTI_RANGE
)
1335 else if (*vr0type
== VR_ANTI_RANGE
1336 && vr1type
== VR_RANGE
)
1338 if (TREE_CODE (vr1min
) == INTEGER_CST
)
1339 *vr0max
= int_const_binop (MINUS_EXPR
, vr1min
,
1340 build_int_cst (TREE_TYPE (vr1min
), 1));
1344 else if (*vr0type
== VR_RANGE
1345 && vr1type
== VR_ANTI_RANGE
)
1347 if (TREE_CODE (*vr0max
) == INTEGER_CST
)
1350 *vr0min
= int_const_binop (PLUS_EXPR
, *vr0max
,
1351 build_int_cst (TREE_TYPE (*vr0max
), 1));
1360 else if (cmpmin
== 1
1362 && (operand_less_p (*vr0min
, vr1max
) == 1
1363 || operand_equal_p (*vr0min
, vr1max
, 0)))
1365 /* ( [ ) ] or ( )[ ] */
1366 if (*vr0type
== VR_RANGE
1367 && vr1type
== VR_RANGE
)
1369 else if (*vr0type
== VR_ANTI_RANGE
1370 && vr1type
== VR_ANTI_RANGE
)
1372 else if (*vr0type
== VR_ANTI_RANGE
1373 && vr1type
== VR_RANGE
)
1375 if (TREE_CODE (vr1max
) == INTEGER_CST
)
1376 *vr0min
= int_const_binop (PLUS_EXPR
, vr1max
,
1377 build_int_cst (TREE_TYPE (vr1max
), 1));
1381 else if (*vr0type
== VR_RANGE
1382 && vr1type
== VR_ANTI_RANGE
)
1384 if (TREE_CODE (*vr0min
) == INTEGER_CST
)
1387 *vr0max
= int_const_binop (MINUS_EXPR
, *vr0min
,
1388 build_int_cst (TREE_TYPE (*vr0min
), 1));
1403 *vr0type
= VR_VARYING
;
1404 *vr0min
= NULL_TREE
;
1405 *vr0max
= NULL_TREE
;
1408 /* Helper for meet operation for value ranges. Given two ranges VR0
1409 and VR1, set VR0 to the union of both ranges. This may not be the
1410 smallest possible such range. */
1413 irange::legacy_union (irange
*vr0
, const irange
*vr1
)
1415 /* VR0 has the resulting range if VR1 is undefined or VR0 is varying. */
1416 if (vr1
->undefined_p ()
1417 || vr0
->varying_p ())
1420 /* VR1 has the resulting range if VR0 is undefined or VR1 is varying. */
1421 if (vr0
->undefined_p ())
1423 /* Avoid the full copy if we already know both sides are simple
1424 and can be trivially copied. */
1425 if (vr1
->legacy_mode_p ())
1427 vr0
->set (vr1
->min (), vr1
->max (), vr1
->kind ());
1433 if (vr1
->varying_p ())
1435 vr0
->set_varying (vr1
->type ());
1439 value_range_kind vr0kind
= vr0
->kind ();
1440 tree vr0min
= vr0
->min ();
1441 tree vr0max
= vr0
->max ();
1442 /* Handle multi-ranges that can be represented as anti-ranges. */
1443 if (!vr1
->legacy_mode_p () && vr1
->maybe_anti_range ())
1445 int_range
<3> tmp (*vr1
);
1447 union_ranges (&vr0kind
, &vr0min
, &vr0max
,
1448 VR_ANTI_RANGE
, tmp
.min (), tmp
.max ());
1451 union_ranges (&vr0kind
, &vr0min
, &vr0max
,
1452 vr1
->kind (), vr1
->min (), vr1
->max ());
1454 if (vr0kind
== VR_UNDEFINED
)
1455 vr0
->set_undefined ();
1456 else if (vr0kind
== VR_VARYING
)
1458 /* Failed to find an efficient meet. Before giving up and
1459 setting the result to VARYING, see if we can at least derive
1460 a non-zero range. */
1461 if (range_includes_zero_p (vr0
) == 0
1462 && range_includes_zero_p (vr1
) == 0)
1463 vr0
->set_nonzero (vr0
->type ());
1465 vr0
->set_varying (vr0
->type ());
1468 vr0
->set (vr0min
, vr0max
, vr0kind
);
1471 /* Meet operation for value ranges. Given two value ranges VR0 and
1472 VR1, store in VR0 a range that contains both VR0 and VR1. This
1473 may not be the smallest possible such range. */
1476 irange::union_ (const irange
*other
)
1478 if (legacy_mode_p ())
1480 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1482 fprintf (dump_file
, "Meeting\n ");
1483 dump_value_range (dump_file
, this);
1484 fprintf (dump_file
, "\nand\n ");
1485 dump_value_range (dump_file
, other
);
1486 fprintf (dump_file
, "\n");
1489 legacy_union (this, other
);
1491 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1493 fprintf (dump_file
, "to\n ");
1494 dump_value_range (dump_file
, this);
1495 fprintf (dump_file
, "\n");
1500 if (other
->legacy_mode_p ())
1504 irange_union (wider
);
1507 irange_union (*other
);
1511 irange::intersect (const irange
*other
)
1513 if (legacy_mode_p ())
1515 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1517 fprintf (dump_file
, "Intersecting\n ");
1518 dump_value_range (dump_file
, this);
1519 fprintf (dump_file
, "\nand\n ");
1520 dump_value_range (dump_file
, other
);
1521 fprintf (dump_file
, "\n");
1524 legacy_intersect (this, other
);
1526 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1528 fprintf (dump_file
, "to\n ");
1529 dump_value_range (dump_file
, this);
1530 fprintf (dump_file
, "\n");
1535 if (other
->legacy_mode_p ())
1539 irange_intersect (wider
);
1542 irange_intersect (*other
);
1545 // union_ for multi-ranges.
1548 irange::irange_union (const irange
&r
)
1550 gcc_checking_assert (!legacy_mode_p () && !r
.legacy_mode_p ());
1552 if (r
.undefined_p () || varying_p ())
1555 if (undefined_p () || r
.varying_p ())
1561 // Do not worry about merging and such by reserving twice as many
1562 // pairs as needed, and then simply sort the 2 ranges into this
1563 // intermediate form.
1565 // The intermediate result will have the property that the beginning
1566 // of each range is <= the beginning of the next range. There may
1567 // be overlapping ranges at this point. I.e. this would be valid
1568 // [-20, 10], [-10, 0], [0, 20], [40, 90] as it satisfies this
1569 // contraint : -20 < -10 < 0 < 40. When the range is rebuilt into r,
1570 // the merge is performed.
1572 // [Xi,Yi]..[Xn,Yn] U [Xj,Yj]..[Xm,Ym] --> [Xk,Yk]..[Xp,Yp]
1573 tree ttype
= r
.type ();
1574 signop sign
= TYPE_SIGN (ttype
);
1576 auto_vec
<tree
, 20> res
;
1578 wi::overflow_type ovf
;
1579 unsigned i
= 0, j
= 0, k
= 0;
1581 while (i
< m_num_ranges
* 2 && j
< r
.m_num_ranges
* 2)
1583 // lower of Xi and Xj is the lowest point.
1584 if (wi::le_p (wi::to_wide (m_base
[i
]), wi::to_wide (r
.m_base
[j
]), sign
))
1586 res
.safe_push (m_base
[i
]);
1587 res
.safe_push (m_base
[i
+ 1]);
1593 res
.safe_push (r
.m_base
[j
]);
1594 res
.safe_push (r
.m_base
[j
+ 1]);
1599 for ( ; i
< m_num_ranges
* 2; i
+= 2)
1601 res
.safe_push (m_base
[i
]);
1602 res
.safe_push (m_base
[i
+ 1]);
1605 for ( ; j
< r
.m_num_ranges
* 2; j
+= 2)
1607 res
.safe_push (r
.m_base
[j
]);
1608 res
.safe_push (r
.m_base
[j
+ 1]);
1612 // Now normalize the vector removing any overlaps.
1614 int prec
= TYPE_PRECISION (ttype
);
1615 wide_int max_val
= wi::max_value (prec
, sign
);
1616 for (j
= 2; j
< k
; j
+= 2)
1618 wide_int val_im1
= wi::to_wide (res
[i
- 1]);
1619 if (val_im1
== max_val
)
1621 u1
= wi::add (val_im1
, 1, sign
, &ovf
);
1623 // Overflow indicates we are at MAX already.
1624 // A wide int bug requires the previous max_val check
1625 // trigger: gcc.c-torture/compile/pr80443.c with -O3
1626 if (ovf
== wi::OVF_OVERFLOW
)
1629 wide_int val_j
= wi::to_wide (res
[j
]);
1630 wide_int val_jp1
= wi::to_wide (res
[j
+1]);
1631 // Current upper+1 is >= lower bound next pair, then we merge ranges.
1632 if (wi::ge_p (u1
, val_j
, sign
))
1634 // New upper bounds is greater of current or the next one.
1635 if (wi::gt_p (val_jp1
, val_im1
, sign
))
1636 res
[i
- 1] = res
[j
+ 1];
1640 // This is a new distinct range, but no point in copying it
1641 // if it is already in the right place.
1645 res
[i
++] = res
[j
+ 1];
1652 // At this point, the vector should have i ranges, none overlapping.
1653 // Now it simply needs to be copied, and if there are too many
1654 // ranges, merge some. We wont do any analysis as to what the
1655 // "best" merges are, simply combine the final ranges into one.
1656 if (i
> m_max_ranges
* 2)
1658 res
[m_max_ranges
* 2 - 1] = res
[i
- 1];
1659 i
= m_max_ranges
* 2;
1662 for (j
= 0; j
< i
; j
++)
1663 m_base
[j
] = res
[j
];
1664 m_num_ranges
= i
/ 2;
1670 // intersect for multi-ranges.
1673 irange::irange_intersect (const irange
&r
)
1675 gcc_checking_assert (!legacy_mode_p () && !r
.legacy_mode_p ());
1677 if (undefined_p () || r
.varying_p ())
1679 if (r
.undefined_p ())
1690 signop sign
= TYPE_SIGN (TREE_TYPE(m_base
[0]));
1691 unsigned bld_pair
= 0;
1692 unsigned bld_lim
= m_max_ranges
;
1693 widest_irange
r2 (*this);
1694 unsigned r2_lim
= r2
.num_pairs ();
1696 for (unsigned i
= 0; i
< r
.num_pairs (); )
1698 // If r1's upper is < r2's lower, we can skip r1's pair.
1699 tree ru
= r
.m_base
[i
* 2 + 1];
1700 tree r2l
= r2
.m_base
[i2
* 2];
1701 if (wi::lt_p (wi::to_wide (ru
), wi::to_wide (r2l
), sign
))
1706 // Likewise, skip r2's pair if its excluded.
1707 tree r2u
= r2
.m_base
[i2
* 2 + 1];
1708 tree rl
= r
.m_base
[i
* 2];
1709 if (wi::lt_p (wi::to_wide (r2u
), wi::to_wide (rl
), sign
))
1714 // No more r2, break.
1718 // Must be some overlap. Find the highest of the lower bounds,
1719 // and set it, unless the build limits lower bounds is already
1721 if (bld_pair
< bld_lim
)
1723 if (wi::ge_p (wi::to_wide (rl
), wi::to_wide (r2l
), sign
))
1724 m_base
[bld_pair
* 2] = rl
;
1726 m_base
[bld_pair
* 2] = r2l
;
1729 // Decrease and set a new upper.
1732 // ...and choose the lower of the upper bounds.
1733 if (wi::le_p (wi::to_wide (ru
), wi::to_wide (r2u
), sign
))
1735 m_base
[bld_pair
* 2 + 1] = ru
;
1737 // Move past the r1 pair and keep trying.
1743 m_base
[bld_pair
* 2 + 1] = r2u
;
1748 // No more r2, break.
1751 // r2 has the higher lower bound.
1754 // At the exit of this loop, it is one of 2 things:
1755 // ran out of r1, or r2, but either means we are done.
1756 m_num_ranges
= bld_pair
;
1761 static wide_int
inline
1762 subtract_one (const wide_int
&x
, tree type
, wi::overflow_type
&overflow
)
1764 // A signed 1-bit bit-field, has a range of [-1,0] so subtracting +1
1765 // overflows, since +1 is unrepresentable. This is why we have an
1766 // addition of -1 here.
1767 if (TYPE_SIGN (type
) == SIGNED
)
1768 return wi::add (x
, -1 , SIGNED
, &overflow
);
1770 return wi::sub (x
, 1, UNSIGNED
, &overflow
);
1773 /* Return the inverse of a range. */
1778 if (legacy_mode_p ())
1780 // We can't just invert VR_RANGE and VR_ANTI_RANGE because we may
1781 // create non-canonical ranges. Use the constructors instead.
1782 if (m_kind
== VR_RANGE
)
1783 *this = value_range (min (), max (), VR_ANTI_RANGE
);
1784 else if (m_kind
== VR_ANTI_RANGE
)
1785 *this = value_range (min (), max ());
1791 gcc_assert (!undefined_p () && !varying_p ());
1793 // We always need one more set of bounds to represent an inverse, so
1794 // if we're at the limit, we can't properly represent things.
1796 // For instance, to represent the inverse of a 2 sub-range set
1797 // [5, 10][20, 30], we would need a 3 sub-range set
1798 // [-MIN, 4][11, 19][31, MAX].
1800 // In this case, return the most conservative thing.
1802 // However, if any of the extremes of the range are -MIN/+MAX, we
1803 // know we will not need an extra bound. For example:
1805 // INVERT([-MIN,20][30,40]) => [21,29][41,+MAX]
1806 // INVERT([-MIN,20][30,MAX]) => [21,29]
1807 tree ttype
= type ();
1808 unsigned prec
= TYPE_PRECISION (ttype
);
1809 signop sign
= TYPE_SIGN (ttype
);
1810 wide_int type_min
= wi::min_value (prec
, sign
);
1811 wide_int type_max
= wi::max_value (prec
, sign
);
1812 if (m_num_ranges
== m_max_ranges
1813 && lower_bound () != type_min
1814 && upper_bound () != type_max
)
1816 m_base
[1] = wide_int_to_tree (ttype
, type_max
);
1820 // The algorithm is as follows. To calculate INVERT ([a,b][c,d]), we
1821 // generate [-MIN, a-1][b+1, c-1][d+1, MAX].
1823 // If there is an over/underflow in the calculation for any
1824 // sub-range, we eliminate that subrange. This allows us to easily
1825 // calculate INVERT([-MIN, 5]) with: [-MIN, -MIN-1][6, MAX]. And since
1826 // we eliminate the underflow, only [6, MAX] remains.
1828 wi::overflow_type ovf
;
1829 // Construct leftmost range.
1830 widest_irange
orig_range (*this);
1831 unsigned nitems
= 0;
1833 // If this is going to underflow on the MINUS 1, don't even bother
1834 // checking. This also handles subtracting one from an unsigned 0,
1835 // which doesn't set the underflow bit.
1836 if (type_min
!= orig_range
.lower_bound ())
1838 m_base
[nitems
++] = wide_int_to_tree (ttype
, type_min
);
1839 tmp
= subtract_one (orig_range
.lower_bound (), ttype
, ovf
);
1840 m_base
[nitems
++] = wide_int_to_tree (ttype
, tmp
);
1845 // Construct middle ranges if applicable.
1846 if (orig_range
.num_pairs () > 1)
1849 for (; j
< (orig_range
.num_pairs () * 2) - 1; j
+= 2)
1851 // The middle ranges cannot have MAX/MIN, so there's no need
1852 // to check for unsigned overflow on the +1 and -1 here.
1853 tmp
= wi::add (wi::to_wide (orig_range
.m_base
[j
]), 1, sign
, &ovf
);
1854 m_base
[nitems
++] = wide_int_to_tree (ttype
, tmp
);
1855 tmp
= subtract_one (wi::to_wide (orig_range
.m_base
[j
+ 1]),
1857 m_base
[nitems
++] = wide_int_to_tree (ttype
, tmp
);
1863 // Construct rightmost range.
1865 // However, if this will overflow on the PLUS 1, don't even bother.
1866 // This also handles adding one to an unsigned MAX, which doesn't
1867 // set the overflow bit.
1868 if (type_max
!= wi::to_wide (orig_range
.m_base
[i
]))
1870 tmp
= wi::add (wi::to_wide (orig_range
.m_base
[i
]), 1, sign
, &ovf
);
1871 m_base
[nitems
++] = wide_int_to_tree (ttype
, tmp
);
1872 m_base
[nitems
++] = wide_int_to_tree (ttype
, type_max
);
1876 m_num_ranges
= nitems
/ 2;
1883 dump_bound_with_infinite_markers (FILE *file
, tree bound
)
1885 tree type
= TREE_TYPE (bound
);
1886 if (INTEGRAL_TYPE_P (type
)
1887 && !TYPE_UNSIGNED (type
)
1888 && vrp_val_is_min (bound
)
1889 && TYPE_PRECISION (type
) != 1)
1890 fprintf (file
, "-INF");
1891 else if (vrp_val_is_max (bound
)
1892 && TYPE_PRECISION (type
) != 1)
1893 fprintf (file
, "+INF");
1895 print_generic_expr (file
, bound
);
1899 irange::dump (FILE *file
) const
1903 fprintf (file
, "UNDEFINED");
1906 print_generic_expr (file
, type ());
1907 fprintf (file
, " ");
1910 fprintf (file
, "VARYING");
1913 if (legacy_mode_p ())
1915 fprintf (file
, "%s[", (m_kind
== VR_ANTI_RANGE
) ? "~" : "");
1916 dump_bound_with_infinite_markers (file
, min ());
1917 fprintf (file
, ", ");
1918 dump_bound_with_infinite_markers (file
, max ());
1919 fprintf (file
, "]");
1922 for (unsigned i
= 0; i
< m_num_ranges
; ++i
)
1924 tree lb
= m_base
[i
* 2];
1925 tree ub
= m_base
[i
* 2 + 1];
1926 fprintf (file
, "[");
1927 dump_bound_with_infinite_markers (file
, lb
);
1928 fprintf (file
, ", ");
1929 dump_bound_with_infinite_markers (file
, ub
);
1930 fprintf (file
, "]");
1935 dump_value_range (FILE *file
, const irange
*vr
)
1941 debug (const irange
*vr
)
1943 dump_value_range (stderr
, vr
);
1944 fprintf (stderr
, "\n");
1948 debug (const irange
&vr
)
1954 debug (const value_range
*vr
)
1956 dump_value_range (stderr
, vr
);
1957 fprintf (stderr
, "\n");
1961 debug (const value_range
&vr
)
1963 dump_value_range (stderr
, &vr
);
1964 fprintf (stderr
, "\n");
1967 /* Create two value-ranges in *VR0 and *VR1 from the anti-range *AR
1968 so that *VR0 U *VR1 == *AR. Returns true if that is possible,
1969 false otherwise. If *AR can be represented with a single range
1970 *VR1 will be VR_UNDEFINED. */
1973 ranges_from_anti_range (const value_range
*ar
,
1974 value_range
*vr0
, value_range
*vr1
)
1976 tree type
= ar
->type ();
1978 vr0
->set_undefined ();
1979 vr1
->set_undefined ();
1981 /* As a future improvement, we could handle ~[0, A] as: [-INF, -1] U
1982 [A+1, +INF]. Not sure if this helps in practice, though. */
1984 if (ar
->kind () != VR_ANTI_RANGE
1985 || TREE_CODE (ar
->min ()) != INTEGER_CST
1986 || TREE_CODE (ar
->max ()) != INTEGER_CST
1987 || !vrp_val_min (type
)
1988 || !vrp_val_max (type
))
1991 if (tree_int_cst_lt (vrp_val_min (type
), ar
->min ()))
1992 vr0
->set (vrp_val_min (type
),
1993 wide_int_to_tree (type
, wi::to_wide (ar
->min ()) - 1));
1994 if (tree_int_cst_lt (ar
->max (), vrp_val_max (type
)))
1995 vr1
->set (wide_int_to_tree (type
, wi::to_wide (ar
->max ()) + 1),
1996 vrp_val_max (type
));
1997 if (vr0
->undefined_p ())
2000 vr1
->set_undefined ();
2003 return !vr0
->undefined_p ();
2007 range_has_numeric_bounds_p (const irange
*vr
)
2009 return (!vr
->undefined_p ()
2010 && TREE_CODE (vr
->min ()) == INTEGER_CST
2011 && TREE_CODE (vr
->max ()) == INTEGER_CST
);
2014 /* Return whether VAL is equal to the maximum value of its type.
2015 We can't do a simple equality comparison with TYPE_MAX_VALUE because
2016 C typedefs and Ada subtypes can produce types whose TYPE_MAX_VALUE
2017 is not == to the integer constant with the same value in the type. */
2020 vrp_val_is_max (const_tree val
)
2022 tree type_max
= vrp_val_max (TREE_TYPE (val
));
2023 return (val
== type_max
2024 || (type_max
!= NULL_TREE
2025 && operand_equal_p (val
, type_max
, 0)));
2028 /* Return whether VAL is equal to the minimum value of its type. */
2031 vrp_val_is_min (const_tree val
)
2033 tree type_min
= vrp_val_min (TREE_TYPE (val
));
2034 return (val
== type_min
2035 || (type_min
!= NULL_TREE
2036 && operand_equal_p (val
, type_min
, 0)));
2039 /* Return true, if VAL1 and VAL2 are equal values for VRP purposes. */
2042 vrp_operand_equal_p (const_tree val1
, const_tree val2
)
2046 if (!val1
|| !val2
|| !operand_equal_p (val1
, val2
, 0))
2051 #define DEFINE_INT_RANGE_GC_STUBS(N) \
2053 gt_pch_nx (int_range<N> *&x) \
2055 for (unsigned i = 0; i < N; ++i) \
2057 gt_pch_nx (x->m_ranges[i * 2]); \
2058 gt_pch_nx (x->m_ranges[i * 2 + 1]); \
2063 gt_ggc_mx (int_range<N> *&x) \
2065 for (unsigned i = 0; i < N; ++i) \
2067 gt_ggc_mx (x->m_ranges[i * 2]); \
2068 gt_ggc_mx (x->m_ranges[i * 2 + 1]); \
2072 #define DEFINE_INT_RANGE_INSTANCE(N) \
2073 template int_range<N>::int_range(tree, tree, value_range_kind); \
2074 template int_range<N>::int_range(tree_node *, \
2077 value_range_kind); \
2078 template int_range<N>::int_range(tree); \
2079 template int_range<N>::int_range(const irange &); \
2080 template int_range<N>::int_range(const int_range &); \
2081 template int_range<N>& int_range<N>::operator= (const int_range &);
2083 DEFINE_INT_RANGE_INSTANCE(1)
2084 DEFINE_INT_RANGE_INSTANCE(2)
2085 DEFINE_INT_RANGE_INSTANCE(3)
2086 DEFINE_INT_RANGE_INSTANCE(255)
2087 DEFINE_INT_RANGE_GC_STUBS(1)