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
)
43 if (src
.legacy_mode_p ())
45 copy_legacy_to_multi_range (src
);
50 unsigned lim
= src
.m_num_ranges
;
51 if (lim
> m_max_ranges
)
54 for (x
= 0; x
< lim
* 2; ++x
)
55 m_base
[x
] = src
.m_base
[x
];
57 // If the range didn't fit, the last range should cover the rest.
58 if (lim
!= src
.m_num_ranges
)
59 m_base
[x
- 1] = src
.m_base
[src
.m_num_ranges
* 2 - 1];
65 // Return TRUE if range is a multi-range that can be represented as a
69 irange::maybe_anti_range () const
72 unsigned int precision
= TYPE_PRECISION (ttype
);
73 signop sign
= TYPE_SIGN (ttype
);
74 return (num_pairs () > 1
76 && lower_bound () == wi::min_value (precision
, sign
)
77 && upper_bound () == wi::max_value (precision
, sign
));
81 irange::copy_legacy_to_multi_range (const irange
&src
)
83 gcc_checking_assert (src
.legacy_mode_p ());
84 gcc_checking_assert (!legacy_mode_p ());
85 if (src
.undefined_p ())
87 else if (src
.varying_p ())
88 set_varying (src
.type ());
91 if (range_has_numeric_bounds_p (&src
))
92 set (src
.min (), src
.max (), src
.kind ());
95 value_range
cst (src
);
96 cst
.normalize_symbolics ();
97 gcc_checking_assert (cst
.varying_p () || cst
.kind () == VR_RANGE
);
98 set (cst
.min (), cst
.max ());
103 // Copy any type of irange into a legacy.
106 irange::copy_to_legacy (const irange
&src
)
108 gcc_checking_assert (legacy_mode_p ());
109 // Copy legacy to legacy.
110 if (src
.legacy_mode_p ())
112 m_num_ranges
= src
.m_num_ranges
;
113 m_base
[0] = src
.m_base
[0];
114 m_base
[1] = src
.m_base
[1];
118 // Copy multi-range to legacy.
119 if (src
.undefined_p ())
121 else if (src
.varying_p ())
122 set_varying (src
.type ());
123 else if (src
.maybe_anti_range ())
125 int_range
<3> r (src
);
127 // Use tree variants to save on tree -> wi -> tree conversions.
128 set (r
.tree_lower_bound (0), r
.tree_upper_bound (0), VR_ANTI_RANGE
);
131 set (src
.tree_lower_bound (), src
.tree_upper_bound ());
134 // Swap min/max if they are out of order. Return TRUE if further
135 // processing of the range is necessary, FALSE otherwise.
138 irange::swap_out_of_order_endpoints (tree
&min
, tree
&max
,
139 value_range_kind
&kind
)
141 /* Wrong order for min and max, to swap them and the VR type we need
143 if (tree_int_cst_lt (max
, min
))
147 /* For one bit precision if max < min, then the swapped
148 range covers all values, so for VR_RANGE it is varying and
149 for VR_ANTI_RANGE empty range, so drop to varying as well. */
150 if (TYPE_PRECISION (TREE_TYPE (min
)) == 1)
152 set_varying (TREE_TYPE (min
));
156 one
= build_int_cst (TREE_TYPE (min
), 1);
157 tmp
= int_const_binop (PLUS_EXPR
, max
, one
);
158 max
= int_const_binop (MINUS_EXPR
, min
, one
);
161 /* There's one corner case, if we had [C+1, C] before we now have
162 that again. But this represents an empty value range, so drop
163 to varying in this case. */
164 if (tree_int_cst_lt (max
, min
))
166 set_varying (TREE_TYPE (min
));
169 kind
= kind
== VR_RANGE
? VR_ANTI_RANGE
: VR_RANGE
;
175 irange::irange_set (tree min
, tree max
)
177 gcc_checking_assert (!POLY_INT_CST_P (min
));
178 gcc_checking_assert (!POLY_INT_CST_P (max
));
188 irange::irange_set_anti_range (tree min
, tree max
)
190 gcc_checking_assert (!POLY_INT_CST_P (min
));
191 gcc_checking_assert (!POLY_INT_CST_P (max
));
194 tree type
= TREE_TYPE (min
);
195 signop sign
= TYPE_SIGN (type
);
196 int_range
<2> type_range (type
);
197 // Calculate INVERSE([I,J]) as [-MIN, I-1][J+1, +MAX].
199 wi::overflow_type ovf
;
201 wide_int w_min
= wi::to_wide (min
);
202 if (wi::ne_p (w_min
, type_range
.lower_bound ()))
204 wide_int lim1
= wi::sub (w_min
, 1, sign
, &ovf
);
205 gcc_checking_assert (ovf
!= wi::OVF_OVERFLOW
);
206 m_base
[0] = type_range
.tree_lower_bound (0);
207 m_base
[1] = wide_int_to_tree (type
, lim1
);
210 wide_int w_max
= wi::to_wide (max
);
211 if (wi::ne_p (w_max
, type_range
.upper_bound ()))
213 wide_int lim2
= wi::add (w_max
, 1, sign
, &ovf
);
214 gcc_checking_assert (ovf
!= wi::OVF_OVERFLOW
);
215 m_base
[m_num_ranges
* 2] = wide_int_to_tree (type
, lim2
);
216 m_base
[m_num_ranges
* 2 + 1] = type_range
.tree_upper_bound (0);
223 /* Set value range to the canonical form of {VRTYPE, MIN, MAX, EQUIV}.
224 This means adjusting VRTYPE, MIN and MAX representing the case of a
225 wrapping range with MAX < MIN covering [MIN, type_max] U [type_min, MAX]
226 as anti-rage ~[MAX+1, MIN-1]. Likewise for wrapping anti-ranges.
227 In corner cases where MAX+1 or MIN-1 wraps this will fall back
229 This routine exists to ease canonicalization in the case where we
230 extract ranges from var + CST op limit. */
233 irange::set (tree min
, tree max
, value_range_kind kind
)
235 if (!legacy_mode_p ())
237 if (kind
== VR_RANGE
)
238 irange_set (min
, max
);
241 gcc_checking_assert (kind
== VR_ANTI_RANGE
);
242 irange_set_anti_range (min
, max
);
246 if (kind
== VR_UNDEFINED
)
251 if (kind
== VR_RANGE
)
253 /* Convert POLY_INT_CST bounds into worst-case INTEGER_CST bounds. */
254 if (POLY_INT_CST_P (min
))
256 tree type_min
= vrp_val_min (TREE_TYPE (min
));
258 = constant_lower_bound_with_limit (wi::to_poly_widest (min
),
259 wi::to_widest (type_min
));
260 min
= wide_int_to_tree (TREE_TYPE (min
), lb
);
262 if (POLY_INT_CST_P (max
))
264 tree type_max
= vrp_val_max (TREE_TYPE (max
));
266 = constant_upper_bound_with_limit (wi::to_poly_widest (max
),
267 wi::to_widest (type_max
));
268 max
= wide_int_to_tree (TREE_TYPE (max
), ub
);
271 else if (kind
!= VR_VARYING
)
273 if (POLY_INT_CST_P (min
) || POLY_INT_CST_P (max
))
276 if (kind
== VR_VARYING
)
278 set_varying (TREE_TYPE (min
));
282 tree type
= TREE_TYPE (min
);
283 // Nothing to canonicalize for symbolic ranges.
284 if (TREE_CODE (min
) != INTEGER_CST
285 || TREE_CODE (max
) != INTEGER_CST
)
293 if (!swap_out_of_order_endpoints (min
, max
, kind
))
296 // Anti-ranges that can be represented as ranges should be so.
297 if (kind
== VR_ANTI_RANGE
)
299 /* For -fstrict-enums we may receive out-of-range ranges so consider
300 values < -INF and values > INF as -INF/INF as well. */
301 bool is_min
= vrp_val_is_min (min
);
302 bool is_max
= vrp_val_is_max (max
);
304 if (is_min
&& is_max
)
306 /* We cannot deal with empty ranges, drop to varying.
307 ??? This could be VR_UNDEFINED instead. */
311 else if (TYPE_PRECISION (TREE_TYPE (min
)) == 1
312 && (is_min
|| is_max
))
314 /* Non-empty boolean ranges can always be represented
315 as a singleton range. */
317 min
= max
= vrp_val_max (TREE_TYPE (min
));
319 min
= max
= vrp_val_min (TREE_TYPE (min
));
324 tree one
= build_int_cst (TREE_TYPE (max
), 1);
325 min
= int_const_binop (PLUS_EXPR
, max
, one
);
326 max
= vrp_val_max (TREE_TYPE (max
));
331 tree one
= build_int_cst (TREE_TYPE (min
), 1);
332 max
= int_const_binop (MINUS_EXPR
, min
, one
);
333 min
= vrp_val_min (TREE_TYPE (min
));
337 else if (!swap_out_of_order_endpoints (min
, max
, kind
))
340 /* Do not drop [-INF(OVF), +INF(OVF)] to varying. (OVF) has to be sticky
341 to make sure VRP iteration terminates, otherwise we can get into
343 if (!normalize_min_max (type
, min
, max
, kind
))
354 // Avoid using TYPE_{MIN,MAX}_VALUE because -fstrict-enums can
355 // restrict those to a subset of what actually fits in the type.
356 // Instead use the extremes of the type precision
357 unsigned prec
= TYPE_PRECISION (type
);
358 signop sign
= TYPE_SIGN (type
);
359 if (wi::eq_p (wi::to_wide (min
), wi::min_value (prec
, sign
))
360 && wi::eq_p (wi::to_wide (max
), wi::max_value (prec
, sign
)))
362 else if (undefined_p ())
363 m_kind
= VR_UNDEFINED
;
368 /* Check the validity of the range. */
371 irange::verify_range ()
373 if (!legacy_mode_p ())
375 gcc_checking_assert (m_kind
== VR_RANGE
);
376 for (unsigned i
= 0; i
< m_num_ranges
; ++i
)
378 tree lb
= tree_lower_bound (i
);
379 tree ub
= tree_upper_bound (i
);
380 int c
= compare_values (lb
, ub
);
381 gcc_assert (c
== 0 || c
== -1);
389 gcc_assert (m_num_ranges
== 0);
393 gcc_assert (m_num_ranges
== 1);
399 gcc_assert (m_num_ranges
== 1);
400 int cmp
= compare_values (tree_lower_bound (0), tree_upper_bound (0));
401 gcc_assert (cmp
== 0 || cmp
== -1 || cmp
== -2);
411 irange::legacy_num_pairs () const
413 gcc_checking_assert (legacy_mode_p ());
419 // Inlined symbolic_p for performance:
420 if (!is_gimple_min_invariant (min ()) || !is_gimple_min_invariant (max ()))
422 value_range
numeric_range (*this);
423 numeric_range
.normalize_symbolics ();
424 return numeric_range
.num_pairs ();
426 if (m_kind
== VR_ANTI_RANGE
)
428 // ~[MIN, X] has one sub-range of [X+1, MAX], and
429 // ~[X, MAX] has one sub-range of [MIN, X-1].
430 if (vrp_val_is_min (min ()) || vrp_val_is_max (max ()))
434 gcc_checking_assert (m_num_ranges
== 1);
438 // Return the lower bound for a sub-range. PAIR is the sub-range in
442 irange::legacy_lower_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_lower_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
= wide_int_to_tree (typ
, wi::to_wide (max ()) + 1);
459 t
= vrp_val_min (typ
);
460 return wi::to_wide (t
);
462 return wi::to_wide (tree_lower_bound (pair
));
465 // Return the upper bound for a sub-range. PAIR is the sub-range in
469 irange::legacy_upper_bound (unsigned pair
) const
471 gcc_checking_assert (legacy_mode_p ());
474 value_range
numeric_range (*this);
475 numeric_range
.normalize_symbolics ();
476 return numeric_range
.legacy_upper_bound (pair
);
478 gcc_checking_assert (!undefined_p ());
479 gcc_checking_assert (pair
+ 1 <= num_pairs ());
480 if (m_kind
== VR_ANTI_RANGE
)
482 tree typ
= type (), t
;
483 if (pair
== 1 || vrp_val_is_min (min ()))
484 t
= vrp_val_max (typ
);
486 t
= wide_int_to_tree (typ
, wi::to_wide (min ()) - 1);
487 return wi::to_wide (t
);
489 return wi::to_wide (tree_upper_bound (pair
));
493 irange::legacy_equal_p (const irange
&other
) const
495 gcc_checking_assert (legacy_mode_p () && other
.legacy_mode_p ());
497 if (m_kind
!= other
.m_kind
)
499 if (m_kind
== VR_UNDEFINED
|| m_kind
== VR_VARYING
)
501 return (vrp_operand_equal_p (tree_lower_bound (0),
502 other
.tree_lower_bound (0))
503 && vrp_operand_equal_p (tree_upper_bound (0),
504 other
.tree_upper_bound (0)));
508 irange::equal_p (const irange
&other
) const
510 if (legacy_mode_p ())
512 if (other
.legacy_mode_p ())
513 return legacy_equal_p (other
);
514 value_range
tmp (other
);
515 return legacy_equal_p (tmp
);
517 if (other
.legacy_mode_p ())
519 value_range
tmp2 (*this);
520 return tmp2
.legacy_equal_p (other
);
523 if (m_num_ranges
!= other
.m_num_ranges
)
526 for (unsigned i
= 0; i
< m_num_ranges
; ++i
)
528 tree lb
= tree_lower_bound (i
);
529 tree ub
= tree_upper_bound (i
);
530 tree lb_other
= other
.tree_lower_bound (i
);
531 tree ub_other
= other
.tree_upper_bound (i
);
532 if (!operand_equal_p (lb
, lb_other
, 0)
533 || !operand_equal_p (ub
, ub_other
, 0))
539 /* Return TRUE if this is a symbolic range. */
542 irange::symbolic_p () const
544 return (!varying_p ()
546 && (!is_gimple_min_invariant (min ())
547 || !is_gimple_min_invariant (max ())));
550 /* NOTE: This is not the inverse of symbolic_p because the range
551 could also be varying or undefined. Ideally they should be inverse
552 of each other, with varying only applying to symbolics. Varying of
553 constants would be represented as [-MIN, +MAX]. */
556 irange::constant_p () const
558 return (!varying_p ()
560 && TREE_CODE (min ()) == INTEGER_CST
561 && TREE_CODE (max ()) == INTEGER_CST
);
564 /* If range is a singleton, place it in RESULT and return TRUE.
565 Note: A singleton can be any gimple invariant, not just constants.
566 So, [&x, &x] counts as a singleton. */
569 irange::singleton_p (tree
*result
) const
571 if (!legacy_mode_p ())
573 if (num_pairs () == 1 && (wi::to_wide (tree_lower_bound ())
574 == wi::to_wide (tree_upper_bound ())))
577 *result
= tree_lower_bound ();
582 if (m_kind
== VR_ANTI_RANGE
)
586 if (TYPE_PRECISION (type ()) == 1)
594 if (num_pairs () == 1)
596 value_range vr0
, vr1
;
597 ranges_from_anti_range ((const value_range
*) this, &vr0
, &vr1
);
598 return vr0
.singleton_p (result
);
601 // Catches non-numeric extremes as well.
602 if (m_kind
== VR_RANGE
603 && vrp_operand_equal_p (min (), max ())
604 && is_gimple_min_invariant (min ()))
613 /* Return 1 if VAL is inside value range.
614 0 if VAL is not inside value range.
615 -2 if we cannot tell either way.
617 Benchmark compile/20001226-1.c compilation time after changing this
621 irange::value_inside_range (tree val
) const
629 if (!legacy_mode_p () && TREE_CODE (val
) == INTEGER_CST
)
630 return contains_p (val
);
632 int cmp1
= operand_less_p (val
, min ());
636 return m_kind
!= VR_RANGE
;
638 int cmp2
= operand_less_p (max (), val
);
642 if (m_kind
== VR_RANGE
)
648 /* Return TRUE if it is possible that range contains VAL. */
651 irange::may_contain_p (tree val
) const
653 return value_inside_range (val
) != 0;
656 /* Return TRUE if range contains INTEGER_CST. */
657 /* Return 1 if VAL is inside value range.
658 0 if VAL is not inside value range.
660 Benchmark compile/20001226-1.c compilation time after changing this
665 irange::contains_p (tree cst
) const
670 if (legacy_mode_p ())
672 gcc_checking_assert (TREE_CODE (cst
) == INTEGER_CST
);
675 value_range
numeric_range (*this);
676 numeric_range
.normalize_symbolics ();
677 return numeric_range
.contains_p (cst
);
679 return value_inside_range (cst
) == 1;
682 gcc_checking_assert (TREE_CODE (cst
) == INTEGER_CST
);
683 signop sign
= TYPE_SIGN (TREE_TYPE (cst
));
684 wide_int v
= wi::to_wide (cst
);
685 for (unsigned r
= 0; r
< m_num_ranges
; ++r
)
687 if (wi::lt_p (v
, lower_bound (r
), sign
))
689 if (wi::le_p (v
, upper_bound (r
), sign
))
697 /* Normalize addresses into constants. */
700 irange::normalize_addresses ()
705 if (!POINTER_TYPE_P (type ()) || range_has_numeric_bounds_p (this))
708 if (!range_includes_zero_p (this))
710 gcc_checking_assert (TREE_CODE (min ()) == ADDR_EXPR
711 || TREE_CODE (max ()) == ADDR_EXPR
);
712 set_nonzero (type ());
715 set_varying (type ());
718 /* Normalize symbolics and addresses into constants. */
721 irange::normalize_symbolics ()
723 if (varying_p () || undefined_p ())
726 tree ttype
= type ();
727 bool min_symbolic
= !is_gimple_min_invariant (min ());
728 bool max_symbolic
= !is_gimple_min_invariant (max ());
729 if (!min_symbolic
&& !max_symbolic
)
731 normalize_addresses ();
735 // [SYM, SYM] -> VARYING
736 if (min_symbolic
&& max_symbolic
)
741 if (kind () == VR_RANGE
)
743 // [SYM, NUM] -> [-MIN, NUM]
746 set (vrp_val_min (ttype
), max ());
749 // [NUM, SYM] -> [NUM, +MAX]
750 set (min (), vrp_val_max (ttype
));
753 gcc_checking_assert (kind () == VR_ANTI_RANGE
);
754 // ~[SYM, NUM] -> [NUM + 1, +MAX]
757 if (!vrp_val_is_max (max ()))
759 tree n
= wide_int_to_tree (ttype
, wi::to_wide (max ()) + 1);
760 set (n
, vrp_val_max (ttype
));
766 // ~[NUM, SYM] -> [-MIN, NUM - 1]
767 if (!vrp_val_is_min (min ()))
769 tree n
= wide_int_to_tree (ttype
, wi::to_wide (min ()) - 1);
770 set (vrp_val_min (ttype
), n
);
776 /* Intersect the two value-ranges { *VR0TYPE, *VR0MIN, *VR0MAX } and
777 { VR1TYPE, VR0MIN, VR0MAX } and store the result
778 in { *VR0TYPE, *VR0MIN, *VR0MAX }. This may not be the smallest
779 possible such range. The resulting range is not canonicalized. */
782 intersect_ranges (enum value_range_kind
*vr0type
,
783 tree
*vr0min
, tree
*vr0max
,
784 enum value_range_kind vr1type
,
785 tree vr1min
, tree vr1max
)
787 bool mineq
= vrp_operand_equal_p (*vr0min
, vr1min
);
788 bool maxeq
= vrp_operand_equal_p (*vr0max
, vr1max
);
790 /* [] is vr0, () is vr1 in the following classification comments. */
794 if (*vr0type
== vr1type
)
795 /* Nothing to do for equal ranges. */
797 else if ((*vr0type
== VR_RANGE
798 && vr1type
== VR_ANTI_RANGE
)
799 || (*vr0type
== VR_ANTI_RANGE
800 && vr1type
== VR_RANGE
))
802 /* For anti-range with range intersection the result is empty. */
803 *vr0type
= VR_UNDEFINED
;
810 else if (operand_less_p (*vr0max
, vr1min
) == 1
811 || operand_less_p (vr1max
, *vr0min
) == 1)
813 /* [ ] ( ) or ( ) [ ]
814 If the ranges have an empty intersection, the result of the
815 intersect operation is the range for intersecting an
816 anti-range with a range or empty when intersecting two ranges. */
817 if (*vr0type
== VR_RANGE
818 && vr1type
== VR_ANTI_RANGE
)
820 else if (*vr0type
== VR_ANTI_RANGE
821 && vr1type
== VR_RANGE
)
827 else if (*vr0type
== VR_RANGE
828 && vr1type
== VR_RANGE
)
830 *vr0type
= VR_UNDEFINED
;
834 else if (*vr0type
== VR_ANTI_RANGE
835 && vr1type
== VR_ANTI_RANGE
)
837 /* If the anti-ranges are adjacent to each other merge them. */
838 if (TREE_CODE (*vr0max
) == INTEGER_CST
839 && TREE_CODE (vr1min
) == INTEGER_CST
840 && operand_less_p (*vr0max
, vr1min
) == 1
841 && integer_onep (int_const_binop (MINUS_EXPR
,
844 else if (TREE_CODE (vr1max
) == INTEGER_CST
845 && TREE_CODE (*vr0min
) == INTEGER_CST
846 && operand_less_p (vr1max
, *vr0min
) == 1
847 && integer_onep (int_const_binop (MINUS_EXPR
,
850 /* Else arbitrarily take VR0. */
853 else if ((maxeq
|| operand_less_p (vr1max
, *vr0max
) == 1)
854 && (mineq
|| operand_less_p (*vr0min
, vr1min
) == 1))
856 /* [ ( ) ] or [( ) ] or [ ( )] */
857 if (*vr0type
== VR_RANGE
858 && vr1type
== VR_RANGE
)
860 /* If both are ranges the result is the inner one. */
865 else if (*vr0type
== VR_RANGE
866 && vr1type
== VR_ANTI_RANGE
)
868 /* Choose the right gap if the left one is empty. */
871 if (TREE_CODE (vr1max
) != INTEGER_CST
)
873 else if (TYPE_PRECISION (TREE_TYPE (vr1max
)) == 1
874 && !TYPE_UNSIGNED (TREE_TYPE (vr1max
)))
876 = int_const_binop (MINUS_EXPR
, vr1max
,
877 build_int_cst (TREE_TYPE (vr1max
), -1));
880 = int_const_binop (PLUS_EXPR
, vr1max
,
881 build_int_cst (TREE_TYPE (vr1max
), 1));
883 /* Choose the left gap if the right one is empty. */
886 if (TREE_CODE (vr1min
) != INTEGER_CST
)
888 else if (TYPE_PRECISION (TREE_TYPE (vr1min
)) == 1
889 && !TYPE_UNSIGNED (TREE_TYPE (vr1min
)))
891 = int_const_binop (PLUS_EXPR
, vr1min
,
892 build_int_cst (TREE_TYPE (vr1min
), -1));
895 = int_const_binop (MINUS_EXPR
, vr1min
,
896 build_int_cst (TREE_TYPE (vr1min
), 1));
898 /* Choose the anti-range if the range is effectively varying. */
899 else if (vrp_val_is_min (*vr0min
)
900 && vrp_val_is_max (*vr0max
))
906 /* Else choose the range. */
908 else if (*vr0type
== VR_ANTI_RANGE
909 && vr1type
== VR_ANTI_RANGE
)
910 /* If both are anti-ranges the result is the outer one. */
912 else if (*vr0type
== VR_ANTI_RANGE
913 && vr1type
== VR_RANGE
)
915 /* The intersection is empty. */
916 *vr0type
= VR_UNDEFINED
;
923 else if ((maxeq
|| operand_less_p (*vr0max
, vr1max
) == 1)
924 && (mineq
|| operand_less_p (vr1min
, *vr0min
) == 1))
926 /* ( [ ] ) or ([ ] ) or ( [ ]) */
927 if (*vr0type
== VR_RANGE
928 && vr1type
== VR_RANGE
)
929 /* Choose the inner range. */
931 else if (*vr0type
== VR_ANTI_RANGE
932 && vr1type
== VR_RANGE
)
934 /* Choose the right gap if the left is empty. */
938 if (TREE_CODE (*vr0max
) != INTEGER_CST
)
940 else if (TYPE_PRECISION (TREE_TYPE (*vr0max
)) == 1
941 && !TYPE_UNSIGNED (TREE_TYPE (*vr0max
)))
943 = int_const_binop (MINUS_EXPR
, *vr0max
,
944 build_int_cst (TREE_TYPE (*vr0max
), -1));
947 = int_const_binop (PLUS_EXPR
, *vr0max
,
948 build_int_cst (TREE_TYPE (*vr0max
), 1));
951 /* Choose the left gap if the right is empty. */
955 if (TREE_CODE (*vr0min
) != INTEGER_CST
)
957 else if (TYPE_PRECISION (TREE_TYPE (*vr0min
)) == 1
958 && !TYPE_UNSIGNED (TREE_TYPE (*vr0min
)))
960 = int_const_binop (PLUS_EXPR
, *vr0min
,
961 build_int_cst (TREE_TYPE (*vr0min
), -1));
964 = int_const_binop (MINUS_EXPR
, *vr0min
,
965 build_int_cst (TREE_TYPE (*vr0min
), 1));
968 /* Choose the anti-range if the range is effectively varying. */
969 else if (vrp_val_is_min (vr1min
)
970 && vrp_val_is_max (vr1max
))
972 /* Choose the anti-range if it is ~[0,0], that range is special
973 enough to special case when vr1's range is relatively wide.
974 At least for types bigger than int - this covers pointers
975 and arguments to functions like ctz. */
976 else if (*vr0min
== *vr0max
977 && integer_zerop (*vr0min
)
978 && ((TYPE_PRECISION (TREE_TYPE (*vr0min
))
979 >= TYPE_PRECISION (integer_type_node
))
980 || POINTER_TYPE_P (TREE_TYPE (*vr0min
)))
981 && TREE_CODE (vr1max
) == INTEGER_CST
982 && TREE_CODE (vr1min
) == INTEGER_CST
983 && (wi::clz (wi::to_wide (vr1max
) - wi::to_wide (vr1min
))
984 < TYPE_PRECISION (TREE_TYPE (*vr0min
)) / 2))
986 /* Else choose the range. */
994 else if (*vr0type
== VR_ANTI_RANGE
995 && vr1type
== VR_ANTI_RANGE
)
997 /* If both are anti-ranges the result is the outer one. */
1002 else if (vr1type
== VR_ANTI_RANGE
1003 && *vr0type
== VR_RANGE
)
1005 /* The intersection is empty. */
1006 *vr0type
= VR_UNDEFINED
;
1007 *vr0min
= NULL_TREE
;
1008 *vr0max
= NULL_TREE
;
1013 else if ((operand_less_p (vr1min
, *vr0max
) == 1
1014 || operand_equal_p (vr1min
, *vr0max
, 0))
1015 && operand_less_p (*vr0min
, vr1min
) == 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 (vr1min
) == INTEGER_CST
)
1028 *vr0max
= int_const_binop (MINUS_EXPR
, vr1min
,
1029 build_int_cst (TREE_TYPE (vr1min
), 1));
1033 else if (*vr0type
== VR_ANTI_RANGE
1034 && vr1type
== VR_RANGE
)
1036 *vr0type
= VR_RANGE
;
1037 if (TREE_CODE (*vr0max
) == INTEGER_CST
)
1038 *vr0min
= int_const_binop (PLUS_EXPR
, *vr0max
,
1039 build_int_cst (TREE_TYPE (*vr0max
), 1));
1047 else if ((operand_less_p (*vr0min
, vr1max
) == 1
1048 || operand_equal_p (*vr0min
, vr1max
, 0))
1049 && operand_less_p (vr1min
, *vr0min
) == 1)
1051 /* ( [ ) ] or ( )[ ] */
1052 if (*vr0type
== VR_ANTI_RANGE
1053 && vr1type
== VR_ANTI_RANGE
)
1055 else if (*vr0type
== VR_RANGE
1056 && vr1type
== VR_RANGE
)
1058 else if (*vr0type
== VR_RANGE
1059 && vr1type
== VR_ANTI_RANGE
)
1061 if (TREE_CODE (vr1max
) == INTEGER_CST
)
1062 *vr0min
= int_const_binop (PLUS_EXPR
, vr1max
,
1063 build_int_cst (TREE_TYPE (vr1max
), 1));
1067 else if (*vr0type
== VR_ANTI_RANGE
1068 && vr1type
== VR_RANGE
)
1070 *vr0type
= VR_RANGE
;
1071 if (TREE_CODE (*vr0min
) == INTEGER_CST
)
1072 *vr0max
= int_const_binop (MINUS_EXPR
, *vr0min
,
1073 build_int_cst (TREE_TYPE (*vr0min
), 1));
1082 /* If we know the intersection is empty, there's no need to
1083 conservatively add anything else to the set. */
1084 if (*vr0type
== VR_UNDEFINED
)
1087 /* As a fallback simply use { *VRTYPE, *VR0MIN, *VR0MAX } as
1088 result for the intersection. That's always a conservative
1089 correct estimate unless VR1 is a constant singleton range
1090 in which case we choose that. */
1091 if (vr1type
== VR_RANGE
1092 && is_gimple_min_invariant (vr1min
)
1093 && vrp_operand_equal_p (vr1min
, vr1max
))
1101 /* Helper for the intersection operation for value ranges. Given two
1102 ranges VR0 and VR1, set VR0 to the intersection of both ranges.
1103 This may not be the smallest possible such range. */
1106 irange::legacy_intersect (irange
*vr0
, const irange
*vr1
)
1108 gcc_checking_assert (vr0
->legacy_mode_p ());
1109 gcc_checking_assert (vr1
->legacy_mode_p ());
1110 /* If either range is VR_VARYING the other one wins. */
1111 if (vr1
->varying_p ())
1113 if (vr0
->varying_p ())
1115 vr0
->set (vr1
->min (), vr1
->max (), vr1
->kind ());
1119 /* When either range is VR_UNDEFINED the resulting range is
1120 VR_UNDEFINED, too. */
1121 if (vr0
->undefined_p ())
1123 if (vr1
->undefined_p ())
1125 vr0
->set_undefined ();
1129 value_range_kind vr0kind
= vr0
->kind ();
1130 tree vr0min
= vr0
->min ();
1131 tree vr0max
= vr0
->max ();
1133 intersect_ranges (&vr0kind
, &vr0min
, &vr0max
,
1134 vr1
->kind (), vr1
->min (), vr1
->max ());
1136 /* Make sure to canonicalize the result though as the inversion of a
1137 VR_RANGE can still be a VR_RANGE. */
1138 if (vr0kind
== VR_UNDEFINED
)
1139 vr0
->set_undefined ();
1140 else if (vr0kind
== VR_VARYING
)
1142 /* If we failed, use the original VR0. */
1146 vr0
->set (vr0min
, vr0max
, vr0kind
);
1149 /* Union the two value-ranges { *VR0TYPE, *VR0MIN, *VR0MAX } and
1150 { VR1TYPE, VR0MIN, VR0MAX } and store the result
1151 in { *VR0TYPE, *VR0MIN, *VR0MAX }. This may not be the smallest
1152 possible such range. The resulting range is not canonicalized. */
1155 union_ranges (enum value_range_kind
*vr0type
,
1156 tree
*vr0min
, tree
*vr0max
,
1157 enum value_range_kind vr1type
,
1158 tree vr1min
, tree vr1max
)
1160 int cmpmin
= compare_values (*vr0min
, vr1min
);
1161 int cmpmax
= compare_values (*vr0max
, vr1max
);
1162 bool mineq
= cmpmin
== 0;
1163 bool maxeq
= cmpmax
== 0;
1165 /* [] is vr0, () is vr1 in the following classification comments. */
1169 if (*vr0type
== vr1type
)
1170 /* Nothing to do for equal ranges. */
1172 else if ((*vr0type
== VR_RANGE
1173 && vr1type
== VR_ANTI_RANGE
)
1174 || (*vr0type
== VR_ANTI_RANGE
1175 && vr1type
== VR_RANGE
))
1177 /* For anti-range with range union the result is varying. */
1183 else if (operand_less_p (*vr0max
, vr1min
) == 1
1184 || operand_less_p (vr1max
, *vr0min
) == 1)
1186 /* [ ] ( ) or ( ) [ ]
1187 If the ranges have an empty intersection, result of the union
1188 operation is the anti-range or if both are anti-ranges
1190 if (*vr0type
== VR_ANTI_RANGE
1191 && vr1type
== VR_ANTI_RANGE
)
1193 else if (*vr0type
== VR_ANTI_RANGE
1194 && vr1type
== VR_RANGE
)
1196 else if (*vr0type
== VR_RANGE
1197 && vr1type
== VR_ANTI_RANGE
)
1203 else if (*vr0type
== VR_RANGE
1204 && vr1type
== VR_RANGE
)
1206 /* The result is the convex hull of both ranges. */
1207 if (operand_less_p (*vr0max
, vr1min
) == 1)
1209 /* If the result can be an anti-range, create one. */
1210 if (TREE_CODE (*vr0max
) == INTEGER_CST
1211 && TREE_CODE (vr1min
) == INTEGER_CST
1212 && vrp_val_is_min (*vr0min
)
1213 && vrp_val_is_max (vr1max
))
1215 tree min
= int_const_binop (PLUS_EXPR
,
1217 build_int_cst (TREE_TYPE (*vr0max
), 1));
1218 tree max
= int_const_binop (MINUS_EXPR
,
1220 build_int_cst (TREE_TYPE (vr1min
), 1));
1221 if (!operand_less_p (max
, min
))
1223 *vr0type
= VR_ANTI_RANGE
;
1235 /* If the result can be an anti-range, create one. */
1236 if (TREE_CODE (vr1max
) == INTEGER_CST
1237 && TREE_CODE (*vr0min
) == INTEGER_CST
1238 && vrp_val_is_min (vr1min
)
1239 && vrp_val_is_max (*vr0max
))
1241 tree min
= int_const_binop (PLUS_EXPR
,
1243 build_int_cst (TREE_TYPE (vr1max
), 1));
1244 tree max
= int_const_binop (MINUS_EXPR
,
1246 build_int_cst (TREE_TYPE (*vr0min
), 1));
1247 if (!operand_less_p (max
, min
))
1249 *vr0type
= VR_ANTI_RANGE
;
1263 else if ((maxeq
|| cmpmax
== 1)
1264 && (mineq
|| cmpmin
== -1))
1266 /* [ ( ) ] or [( ) ] or [ ( )] */
1267 if (*vr0type
== VR_RANGE
1268 && vr1type
== VR_RANGE
)
1270 else if (*vr0type
== VR_ANTI_RANGE
1271 && vr1type
== VR_ANTI_RANGE
)
1277 else if (*vr0type
== VR_ANTI_RANGE
1278 && vr1type
== VR_RANGE
)
1280 /* Arbitrarily choose the right or left gap. */
1281 if (!mineq
&& TREE_CODE (vr1min
) == INTEGER_CST
)
1282 *vr0max
= int_const_binop (MINUS_EXPR
, vr1min
,
1283 build_int_cst (TREE_TYPE (vr1min
), 1));
1284 else if (!maxeq
&& TREE_CODE (vr1max
) == INTEGER_CST
)
1285 *vr0min
= int_const_binop (PLUS_EXPR
, vr1max
,
1286 build_int_cst (TREE_TYPE (vr1max
), 1));
1290 else if (*vr0type
== VR_RANGE
1291 && vr1type
== VR_ANTI_RANGE
)
1292 /* The result covers everything. */
1297 else if ((maxeq
|| cmpmax
== -1)
1298 && (mineq
|| cmpmin
== 1))
1300 /* ( [ ] ) or ([ ] ) or ( [ ]) */
1301 if (*vr0type
== VR_RANGE
1302 && vr1type
== VR_RANGE
)
1308 else if (*vr0type
== VR_ANTI_RANGE
1309 && vr1type
== VR_ANTI_RANGE
)
1311 else if (*vr0type
== VR_RANGE
1312 && vr1type
== VR_ANTI_RANGE
)
1314 *vr0type
= VR_ANTI_RANGE
;
1315 if (!mineq
&& TREE_CODE (*vr0min
) == INTEGER_CST
)
1317 *vr0max
= int_const_binop (MINUS_EXPR
, *vr0min
,
1318 build_int_cst (TREE_TYPE (*vr0min
), 1));
1321 else if (!maxeq
&& TREE_CODE (*vr0max
) == INTEGER_CST
)
1323 *vr0min
= int_const_binop (PLUS_EXPR
, *vr0max
,
1324 build_int_cst (TREE_TYPE (*vr0max
), 1));
1330 else if (*vr0type
== VR_ANTI_RANGE
1331 && vr1type
== VR_RANGE
)
1332 /* The result covers everything. */
1337 else if (cmpmin
== -1
1339 && (operand_less_p (vr1min
, *vr0max
) == 1
1340 || operand_equal_p (vr1min
, *vr0max
, 0)))
1342 /* [ ( ] ) or [ ]( ) */
1343 if (*vr0type
== VR_RANGE
1344 && vr1type
== VR_RANGE
)
1346 else if (*vr0type
== VR_ANTI_RANGE
1347 && vr1type
== VR_ANTI_RANGE
)
1349 else if (*vr0type
== VR_ANTI_RANGE
1350 && vr1type
== VR_RANGE
)
1352 if (TREE_CODE (vr1min
) == INTEGER_CST
)
1353 *vr0max
= int_const_binop (MINUS_EXPR
, vr1min
,
1354 build_int_cst (TREE_TYPE (vr1min
), 1));
1358 else if (*vr0type
== VR_RANGE
1359 && vr1type
== VR_ANTI_RANGE
)
1361 if (TREE_CODE (*vr0max
) == INTEGER_CST
)
1364 *vr0min
= int_const_binop (PLUS_EXPR
, *vr0max
,
1365 build_int_cst (TREE_TYPE (*vr0max
), 1));
1374 else if (cmpmin
== 1
1376 && (operand_less_p (*vr0min
, vr1max
) == 1
1377 || operand_equal_p (*vr0min
, vr1max
, 0)))
1379 /* ( [ ) ] or ( )[ ] */
1380 if (*vr0type
== VR_RANGE
1381 && vr1type
== VR_RANGE
)
1383 else if (*vr0type
== VR_ANTI_RANGE
1384 && vr1type
== VR_ANTI_RANGE
)
1386 else if (*vr0type
== VR_ANTI_RANGE
1387 && vr1type
== VR_RANGE
)
1389 if (TREE_CODE (vr1max
) == INTEGER_CST
)
1390 *vr0min
= int_const_binop (PLUS_EXPR
, vr1max
,
1391 build_int_cst (TREE_TYPE (vr1max
), 1));
1395 else if (*vr0type
== VR_RANGE
1396 && vr1type
== VR_ANTI_RANGE
)
1398 if (TREE_CODE (*vr0min
) == INTEGER_CST
)
1401 *vr0max
= int_const_binop (MINUS_EXPR
, *vr0min
,
1402 build_int_cst (TREE_TYPE (*vr0min
), 1));
1417 *vr0type
= VR_VARYING
;
1418 *vr0min
= NULL_TREE
;
1419 *vr0max
= NULL_TREE
;
1422 /* Helper for meet operation for value ranges. Given two ranges VR0
1423 and VR1, set VR0 to the union of both ranges. This may not be the
1424 smallest possible such range. */
1427 irange::legacy_union (irange
*vr0
, const irange
*vr1
)
1429 gcc_checking_assert (vr0
->legacy_mode_p ());
1430 gcc_checking_assert (vr1
->legacy_mode_p ());
1432 /* VR0 has the resulting range if VR1 is undefined or VR0 is varying. */
1433 if (vr1
->undefined_p ()
1434 || vr0
->varying_p ())
1437 /* VR1 has the resulting range if VR0 is undefined or VR1 is varying. */
1438 if (vr0
->undefined_p ())
1440 vr0
->set (vr1
->min (), vr1
->max (), vr1
->kind ());
1444 if (vr1
->varying_p ())
1446 vr0
->set_varying (vr1
->type ());
1450 value_range_kind vr0kind
= vr0
->kind ();
1451 tree vr0min
= vr0
->min ();
1452 tree vr0max
= vr0
->max ();
1454 union_ranges (&vr0kind
, &vr0min
, &vr0max
,
1455 vr1
->kind (), vr1
->min (), vr1
->max ());
1457 if (vr0kind
== VR_UNDEFINED
)
1458 vr0
->set_undefined ();
1459 else if (vr0kind
== VR_VARYING
)
1461 /* Failed to find an efficient meet. Before giving up and
1462 setting the result to VARYING, see if we can at least derive
1463 a non-zero range. */
1464 if (range_includes_zero_p (vr0
) == 0
1465 && range_includes_zero_p (vr1
) == 0)
1466 vr0
->set_nonzero (vr0
->type ());
1468 vr0
->set_varying (vr0
->type ());
1471 vr0
->set (vr0min
, vr0max
, vr0kind
);
1474 /* Meet operation for value ranges. Given two value ranges VR0 and
1475 VR1, store in VR0 a range that contains both VR0 and VR1. This
1476 may not be the smallest possible such range. */
1479 irange::union_ (const irange
*other
)
1481 if (legacy_mode_p ())
1483 if (!other
->legacy_mode_p ())
1485 int_range
<1> tmp
= *other
;
1486 legacy_union (this, &tmp
);
1489 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1491 fprintf (dump_file
, "Meeting\n ");
1492 dump_value_range (dump_file
, this);
1493 fprintf (dump_file
, "\nand\n ");
1494 dump_value_range (dump_file
, other
);
1495 fprintf (dump_file
, "\n");
1498 legacy_union (this, other
);
1500 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1502 fprintf (dump_file
, "to\n ");
1503 dump_value_range (dump_file
, this);
1504 fprintf (dump_file
, "\n");
1509 if (other
->legacy_mode_p ())
1511 int_range
<2> wider
= *other
;
1512 irange_union (wider
);
1515 irange_union (*other
);
1519 irange::intersect (const irange
*other
)
1521 if (legacy_mode_p ())
1523 if (!other
->legacy_mode_p ())
1525 int_range
<1> tmp
= *other
;
1526 legacy_intersect (this, &tmp
);
1529 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1531 fprintf (dump_file
, "Intersecting\n ");
1532 dump_value_range (dump_file
, this);
1533 fprintf (dump_file
, "\nand\n ");
1534 dump_value_range (dump_file
, other
);
1535 fprintf (dump_file
, "\n");
1538 legacy_intersect (this, other
);
1540 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1542 fprintf (dump_file
, "to\n ");
1543 dump_value_range (dump_file
, this);
1544 fprintf (dump_file
, "\n");
1549 if (other
->legacy_mode_p ())
1553 irange_intersect (wider
);
1556 irange_intersect (*other
);
1559 // union_ for multi-ranges.
1562 irange::irange_union (const irange
&r
)
1564 gcc_checking_assert (!legacy_mode_p () && !r
.legacy_mode_p ());
1566 if (r
.undefined_p () || varying_p ())
1569 if (undefined_p () || r
.varying_p ())
1575 // Do not worry about merging and such by reserving twice as many
1576 // pairs as needed, and then simply sort the 2 ranges into this
1577 // intermediate form.
1579 // The intermediate result will have the property that the beginning
1580 // of each range is <= the beginning of the next range. There may
1581 // be overlapping ranges at this point. I.e. this would be valid
1582 // [-20, 10], [-10, 0], [0, 20], [40, 90] as it satisfies this
1583 // contraint : -20 < -10 < 0 < 40. When the range is rebuilt into r,
1584 // the merge is performed.
1586 // [Xi,Yi]..[Xn,Yn] U [Xj,Yj]..[Xm,Ym] --> [Xk,Yk]..[Xp,Yp]
1587 tree ttype
= r
.type ();
1588 signop sign
= TYPE_SIGN (ttype
);
1590 auto_vec
<tree
, 20> res
;
1592 wi::overflow_type ovf
;
1593 unsigned i
= 0, j
= 0, k
= 0;
1595 while (i
< m_num_ranges
* 2 && j
< r
.m_num_ranges
* 2)
1597 // lower of Xi and Xj is the lowest point.
1598 if (wi::le_p (wi::to_wide (m_base
[i
]), wi::to_wide (r
.m_base
[j
]), sign
))
1600 res
.safe_push (m_base
[i
]);
1601 res
.safe_push (m_base
[i
+ 1]);
1607 res
.safe_push (r
.m_base
[j
]);
1608 res
.safe_push (r
.m_base
[j
+ 1]);
1613 for ( ; i
< m_num_ranges
* 2; i
+= 2)
1615 res
.safe_push (m_base
[i
]);
1616 res
.safe_push (m_base
[i
+ 1]);
1619 for ( ; j
< r
.m_num_ranges
* 2; j
+= 2)
1621 res
.safe_push (r
.m_base
[j
]);
1622 res
.safe_push (r
.m_base
[j
+ 1]);
1626 // Now normalize the vector removing any overlaps.
1628 int prec
= TYPE_PRECISION (ttype
);
1629 wide_int max_val
= wi::max_value (prec
, sign
);
1630 for (j
= 2; j
< k
; j
+= 2)
1632 wide_int val_im1
= wi::to_wide (res
[i
- 1]);
1633 if (val_im1
== max_val
)
1635 u1
= wi::add (val_im1
, 1, sign
, &ovf
);
1637 // Overflow indicates we are at MAX already.
1638 // A wide int bug requires the previous max_val check
1639 // trigger: gcc.c-torture/compile/pr80443.c with -O3
1640 if (ovf
== wi::OVF_OVERFLOW
)
1643 wide_int val_j
= wi::to_wide (res
[j
]);
1644 wide_int val_jp1
= wi::to_wide (res
[j
+1]);
1645 // Current upper+1 is >= lower bound next pair, then we merge ranges.
1646 if (wi::ge_p (u1
, val_j
, sign
))
1648 // New upper bounds is greater of current or the next one.
1649 if (wi::gt_p (val_jp1
, val_im1
, sign
))
1650 res
[i
- 1] = res
[j
+ 1];
1654 // This is a new distinct range, but no point in copying it
1655 // if it is already in the right place.
1659 res
[i
++] = res
[j
+ 1];
1666 // At this point, the vector should have i ranges, none overlapping.
1667 // Now it simply needs to be copied, and if there are too many
1668 // ranges, merge some. We wont do any analysis as to what the
1669 // "best" merges are, simply combine the final ranges into one.
1670 if (i
> m_max_ranges
* 2)
1672 res
[m_max_ranges
* 2 - 1] = res
[i
- 1];
1673 i
= m_max_ranges
* 2;
1676 for (j
= 0; j
< i
; j
++)
1677 m_base
[j
] = res
[j
];
1678 m_num_ranges
= i
/ 2;
1684 // intersect for multi-ranges.
1687 irange::irange_intersect (const irange
&r
)
1689 gcc_checking_assert (!legacy_mode_p () && !r
.legacy_mode_p ());
1691 if (undefined_p () || r
.varying_p ())
1693 if (r
.undefined_p ())
1704 signop sign
= TYPE_SIGN (TREE_TYPE(m_base
[0]));
1705 unsigned bld_pair
= 0;
1706 unsigned bld_lim
= m_max_ranges
;
1707 int_range_max
r2 (*this);
1708 unsigned r2_lim
= r2
.num_pairs ();
1710 for (unsigned i
= 0; i
< r
.num_pairs (); )
1712 // If r1's upper is < r2's lower, we can skip r1's pair.
1713 tree ru
= r
.m_base
[i
* 2 + 1];
1714 tree r2l
= r2
.m_base
[i2
* 2];
1715 if (wi::lt_p (wi::to_wide (ru
), wi::to_wide (r2l
), sign
))
1720 // Likewise, skip r2's pair if its excluded.
1721 tree r2u
= r2
.m_base
[i2
* 2 + 1];
1722 tree rl
= r
.m_base
[i
* 2];
1723 if (wi::lt_p (wi::to_wide (r2u
), wi::to_wide (rl
), sign
))
1728 // No more r2, break.
1732 // Must be some overlap. Find the highest of the lower bounds,
1733 // and set it, unless the build limits lower bounds is already
1735 if (bld_pair
< bld_lim
)
1737 if (wi::ge_p (wi::to_wide (rl
), wi::to_wide (r2l
), sign
))
1738 m_base
[bld_pair
* 2] = rl
;
1740 m_base
[bld_pair
* 2] = r2l
;
1743 // Decrease and set a new upper.
1746 // ...and choose the lower of the upper bounds.
1747 if (wi::le_p (wi::to_wide (ru
), wi::to_wide (r2u
), sign
))
1749 m_base
[bld_pair
* 2 + 1] = ru
;
1751 // Move past the r1 pair and keep trying.
1757 m_base
[bld_pair
* 2 + 1] = r2u
;
1762 // No more r2, break.
1765 // r2 has the higher lower bound.
1768 // At the exit of this loop, it is one of 2 things:
1769 // ran out of r1, or r2, but either means we are done.
1770 m_num_ranges
= bld_pair
;
1775 static wide_int
inline
1776 subtract_one (const wide_int
&x
, tree type
, wi::overflow_type
&overflow
)
1778 // A signed 1-bit bit-field, has a range of [-1,0] so subtracting +1
1779 // overflows, since +1 is unrepresentable. This is why we have an
1780 // addition of -1 here.
1781 if (TYPE_SIGN (type
) == SIGNED
)
1782 return wi::add (x
, -1 , SIGNED
, &overflow
);
1784 return wi::sub (x
, 1, UNSIGNED
, &overflow
);
1787 /* Return the inverse of a range. */
1792 if (legacy_mode_p ())
1794 // We can't just invert VR_RANGE and VR_ANTI_RANGE because we may
1795 // create non-canonical ranges. Use the constructors instead.
1796 if (m_kind
== VR_RANGE
)
1797 *this = value_range (min (), max (), VR_ANTI_RANGE
);
1798 else if (m_kind
== VR_ANTI_RANGE
)
1799 *this = value_range (min (), max ());
1805 gcc_assert (!undefined_p () && !varying_p ());
1807 // We always need one more set of bounds to represent an inverse, so
1808 // if we're at the limit, we can't properly represent things.
1810 // For instance, to represent the inverse of a 2 sub-range set
1811 // [5, 10][20, 30], we would need a 3 sub-range set
1812 // [-MIN, 4][11, 19][31, MAX].
1814 // In this case, return the most conservative thing.
1816 // However, if any of the extremes of the range are -MIN/+MAX, we
1817 // know we will not need an extra bound. For example:
1819 // INVERT([-MIN,20][30,40]) => [21,29][41,+MAX]
1820 // INVERT([-MIN,20][30,MAX]) => [21,29]
1821 tree ttype
= type ();
1822 unsigned prec
= TYPE_PRECISION (ttype
);
1823 signop sign
= TYPE_SIGN (ttype
);
1824 wide_int type_min
= wi::min_value (prec
, sign
);
1825 wide_int type_max
= wi::max_value (prec
, sign
);
1826 if (m_num_ranges
== m_max_ranges
1827 && lower_bound () != type_min
1828 && upper_bound () != type_max
)
1830 m_base
[1] = wide_int_to_tree (ttype
, type_max
);
1834 // The algorithm is as follows. To calculate INVERT ([a,b][c,d]), we
1835 // generate [-MIN, a-1][b+1, c-1][d+1, MAX].
1837 // If there is an over/underflow in the calculation for any
1838 // sub-range, we eliminate that subrange. This allows us to easily
1839 // calculate INVERT([-MIN, 5]) with: [-MIN, -MIN-1][6, MAX]. And since
1840 // we eliminate the underflow, only [6, MAX] remains.
1842 wi::overflow_type ovf
;
1843 // Construct leftmost range.
1844 int_range_max
orig_range (*this);
1845 unsigned nitems
= 0;
1847 // If this is going to underflow on the MINUS 1, don't even bother
1848 // checking. This also handles subtracting one from an unsigned 0,
1849 // which doesn't set the underflow bit.
1850 if (type_min
!= orig_range
.lower_bound ())
1852 m_base
[nitems
++] = wide_int_to_tree (ttype
, type_min
);
1853 tmp
= subtract_one (orig_range
.lower_bound (), ttype
, ovf
);
1854 m_base
[nitems
++] = wide_int_to_tree (ttype
, tmp
);
1859 // Construct middle ranges if applicable.
1860 if (orig_range
.num_pairs () > 1)
1863 for (; j
< (orig_range
.num_pairs () * 2) - 1; j
+= 2)
1865 // The middle ranges cannot have MAX/MIN, so there's no need
1866 // to check for unsigned overflow on the +1 and -1 here.
1867 tmp
= wi::add (wi::to_wide (orig_range
.m_base
[j
]), 1, sign
, &ovf
);
1868 m_base
[nitems
++] = wide_int_to_tree (ttype
, tmp
);
1869 tmp
= subtract_one (wi::to_wide (orig_range
.m_base
[j
+ 1]),
1871 m_base
[nitems
++] = wide_int_to_tree (ttype
, tmp
);
1877 // Construct rightmost range.
1879 // However, if this will overflow on the PLUS 1, don't even bother.
1880 // This also handles adding one to an unsigned MAX, which doesn't
1881 // set the overflow bit.
1882 if (type_max
!= wi::to_wide (orig_range
.m_base
[i
]))
1884 tmp
= wi::add (wi::to_wide (orig_range
.m_base
[i
]), 1, sign
, &ovf
);
1885 m_base
[nitems
++] = wide_int_to_tree (ttype
, tmp
);
1886 m_base
[nitems
++] = wide_int_to_tree (ttype
, type_max
);
1890 m_num_ranges
= nitems
/ 2;
1897 dump_bound_with_infinite_markers (FILE *file
, tree bound
)
1899 tree type
= TREE_TYPE (bound
);
1900 if (INTEGRAL_TYPE_P (type
)
1901 && !TYPE_UNSIGNED (type
)
1902 && vrp_val_is_min (bound
)
1903 && TYPE_PRECISION (type
) != 1)
1904 fprintf (file
, "-INF");
1905 else if (vrp_val_is_max (bound
)
1906 && TYPE_PRECISION (type
) != 1)
1907 fprintf (file
, "+INF");
1909 print_generic_expr (file
, bound
);
1913 irange::dump (FILE *file
) const
1917 fprintf (file
, "UNDEFINED");
1920 print_generic_expr (file
, type ());
1921 fprintf (file
, " ");
1924 fprintf (file
, "VARYING");
1927 if (legacy_mode_p ())
1929 fprintf (file
, "%s[", (m_kind
== VR_ANTI_RANGE
) ? "~" : "");
1930 dump_bound_with_infinite_markers (file
, min ());
1931 fprintf (file
, ", ");
1932 dump_bound_with_infinite_markers (file
, max ());
1933 fprintf (file
, "]");
1936 for (unsigned i
= 0; i
< m_num_ranges
; ++i
)
1938 tree lb
= m_base
[i
* 2];
1939 tree ub
= m_base
[i
* 2 + 1];
1940 fprintf (file
, "[");
1941 dump_bound_with_infinite_markers (file
, lb
);
1942 fprintf (file
, ", ");
1943 dump_bound_with_infinite_markers (file
, ub
);
1944 fprintf (file
, "]");
1949 dump_value_range (FILE *file
, const irange
*vr
)
1955 debug (const irange
*vr
)
1957 dump_value_range (stderr
, vr
);
1958 fprintf (stderr
, "\n");
1962 debug (const irange
&vr
)
1968 debug (const value_range
*vr
)
1970 dump_value_range (stderr
, vr
);
1971 fprintf (stderr
, "\n");
1975 debug (const value_range
&vr
)
1977 dump_value_range (stderr
, &vr
);
1978 fprintf (stderr
, "\n");
1981 /* Create two value-ranges in *VR0 and *VR1 from the anti-range *AR
1982 so that *VR0 U *VR1 == *AR. Returns true if that is possible,
1983 false otherwise. If *AR can be represented with a single range
1984 *VR1 will be VR_UNDEFINED. */
1987 ranges_from_anti_range (const value_range
*ar
,
1988 value_range
*vr0
, value_range
*vr1
)
1990 tree type
= ar
->type ();
1992 vr0
->set_undefined ();
1993 vr1
->set_undefined ();
1995 /* As a future improvement, we could handle ~[0, A] as: [-INF, -1] U
1996 [A+1, +INF]. Not sure if this helps in practice, though. */
1998 if (ar
->kind () != VR_ANTI_RANGE
1999 || TREE_CODE (ar
->min ()) != INTEGER_CST
2000 || TREE_CODE (ar
->max ()) != INTEGER_CST
2001 || !vrp_val_min (type
)
2002 || !vrp_val_max (type
))
2005 if (tree_int_cst_lt (vrp_val_min (type
), ar
->min ()))
2006 vr0
->set (vrp_val_min (type
),
2007 wide_int_to_tree (type
, wi::to_wide (ar
->min ()) - 1));
2008 if (tree_int_cst_lt (ar
->max (), vrp_val_max (type
)))
2009 vr1
->set (wide_int_to_tree (type
, wi::to_wide (ar
->max ()) + 1),
2010 vrp_val_max (type
));
2011 if (vr0
->undefined_p ())
2014 vr1
->set_undefined ();
2017 return !vr0
->undefined_p ();
2021 range_has_numeric_bounds_p (const irange
*vr
)
2023 return (!vr
->undefined_p ()
2024 && TREE_CODE (vr
->min ()) == INTEGER_CST
2025 && TREE_CODE (vr
->max ()) == INTEGER_CST
);
2028 /* Return whether VAL is equal to the maximum value of its type.
2029 We can't do a simple equality comparison with TYPE_MAX_VALUE because
2030 C typedefs and Ada subtypes can produce types whose TYPE_MAX_VALUE
2031 is not == to the integer constant with the same value in the type. */
2034 vrp_val_is_max (const_tree val
)
2036 tree type_max
= vrp_val_max (TREE_TYPE (val
));
2037 return (val
== type_max
2038 || (type_max
!= NULL_TREE
2039 && operand_equal_p (val
, type_max
, 0)));
2042 /* Return whether VAL is equal to the minimum value of its type. */
2045 vrp_val_is_min (const_tree val
)
2047 tree type_min
= vrp_val_min (TREE_TYPE (val
));
2048 return (val
== type_min
2049 || (type_min
!= NULL_TREE
2050 && operand_equal_p (val
, type_min
, 0)));
2053 /* Return true, if VAL1 and VAL2 are equal values for VRP purposes. */
2056 vrp_operand_equal_p (const_tree val1
, const_tree val2
)
2060 if (!val1
|| !val2
|| !operand_equal_p (val1
, val2
, 0))
2065 #define DEFINE_INT_RANGE_GC_STUBS(N) \
2067 gt_pch_nx (int_range<N> *&x) \
2069 for (unsigned i = 0; i < N; ++i) \
2071 gt_pch_nx (x->m_ranges[i * 2]); \
2072 gt_pch_nx (x->m_ranges[i * 2 + 1]); \
2077 gt_ggc_mx (int_range<N> *&x) \
2079 for (unsigned i = 0; i < N; ++i) \
2081 gt_ggc_mx (x->m_ranges[i * 2]); \
2082 gt_ggc_mx (x->m_ranges[i * 2 + 1]); \
2086 #define DEFINE_INT_RANGE_INSTANCE(N) \
2087 template int_range<N>::int_range(tree, tree, value_range_kind); \
2088 template int_range<N>::int_range(tree_node *, \
2091 value_range_kind); \
2092 template int_range<N>::int_range(tree); \
2093 template int_range<N>::int_range(const irange &); \
2094 template int_range<N>::int_range(const int_range &); \
2095 template int_range<N>& int_range<N>::operator= (const int_range &);
2097 DEFINE_INT_RANGE_INSTANCE(1)
2098 DEFINE_INT_RANGE_INSTANCE(2)
2099 DEFINE_INT_RANGE_INSTANCE(3)
2100 DEFINE_INT_RANGE_INSTANCE(255)
2101 DEFINE_INT_RANGE_GC_STUBS(1)