]>
gcc.gnu.org Git - gcc.git/blob - gcc/value-range.cc
1 /* Support routines for value ranges.
2 Copyright (C) 2019-2022 Free Software Foundation, Inc.
3 Major hacks by Aldy Hernandez <aldyh@redhat.com> and
4 Andrew MacLeod <amacleod@redhat.com>.
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify
9 it under the terms of the GNU General Public License as published by
10 the Free Software Foundation; either version 3, or (at your option)
13 GCC is distributed in the hope that it will be useful,
14 but WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 GNU General Public License for more details.
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
24 #include "coretypes.h"
29 #include "tree-pretty-print.h"
30 #include "value-range-pretty-print.h"
31 #include "fold-const.h"
32 #include "gimple-range.h"
35 irange::accept (const vrange_visitor
&v
) const
41 unsupported_range::accept (const vrange_visitor
&v
) const
46 // Convenience function only available for integers and pointers.
49 Value_Range::lower_bound () const
51 if (is_a
<irange
> (*m_vrange
))
52 return as_a
<irange
> (*m_vrange
).lower_bound ();
56 // Convenience function only available for integers and pointers.
59 Value_Range::upper_bound () const
61 if (is_a
<irange
> (*m_vrange
))
62 return as_a
<irange
> (*m_vrange
).upper_bound ();
67 Value_Range::dump (FILE *out
) const
72 fprintf (out
, "NULL");
76 debug (const Value_Range
&r
)
79 fprintf (stderr
, "\n");
82 // Default vrange definitions.
85 vrange::contains_p (tree
) const
91 vrange::singleton_p (tree
*) const
97 vrange::set (tree
, tree
, value_range_kind
)
102 vrange::type () const
104 return void_type_node
;
108 vrange::supports_type_p (tree
) const
114 vrange::set_undefined ()
116 m_kind
= VR_UNDEFINED
;
120 vrange::set_varying (tree
)
126 vrange::union_ (const vrange
&r
)
128 if (r
.undefined_p () || varying_p ())
130 if (undefined_p () || r
.varying_p ())
140 vrange::intersect (const vrange
&r
)
142 if (undefined_p () || r
.varying_p ())
144 if (r
.undefined_p ())
159 vrange::zero_p () const
165 vrange::nonzero_p () const
171 vrange::set_nonzero (tree
)
176 vrange::set_zero (tree
)
181 vrange::set_nonnegative (tree
)
186 vrange::fits_p (const vrange
&) const
191 // Assignment operator for generic ranges. Copying incompatible types
195 vrange::operator= (const vrange
&src
)
197 if (is_a
<irange
> (src
))
199 as_a
<irange
> (*this) = as_a
<irange
> (src
);
206 // Equality operator for generic ranges.
209 vrange::operator== (const vrange
&src
) const
211 if (is_a
<irange
> (src
))
212 return as_a
<irange
> (*this) == as_a
<irange
> (src
);
216 // Wrapper for vrange_printer to dump a range to a file.
219 vrange::dump (FILE *file
) const
221 pretty_printer buffer
;
222 pp_needs_newline (&buffer
) = true;
223 buffer
.buffer
->stream
= file
;
224 vrange_printer
vrange_pp (&buffer
);
225 this->accept (vrange_pp
);
230 irange::supports_type_p (tree type
) const
232 return supports_p (type
);
235 // Return TRUE if R fits in THIS.
238 irange::fits_p (const vrange
&r
) const
240 return m_max_ranges
>= as_a
<irange
> (r
).num_pairs ();
244 irange::set_nonnegative (tree type
)
246 set (build_int_cst (type
, 0), TYPE_MAX_VALUE (type
));
249 unsupported_range::unsupported_range ()
251 m_discriminator
= VR_UNKNOWN
;
255 // Here we copy between any two irange's. The ranges can be legacy or
256 // multi-ranges, and copying between any combination works correctly.
259 irange::operator= (const irange
&src
)
261 if (legacy_mode_p ())
263 copy_to_legacy (src
);
266 if (src
.legacy_mode_p ())
268 copy_legacy_to_multi_range (src
);
273 unsigned lim
= src
.m_num_ranges
;
274 if (lim
> m_max_ranges
)
277 for (x
= 0; x
< lim
* 2; ++x
)
278 m_base
[x
] = src
.m_base
[x
];
280 // If the range didn't fit, the last range should cover the rest.
281 if (lim
!= src
.m_num_ranges
)
282 m_base
[x
- 1] = src
.m_base
[src
.m_num_ranges
* 2 - 1];
286 m_nonzero_mask
= src
.m_nonzero_mask
;
292 // Return TRUE if range is a multi-range that can be represented as a
296 irange::maybe_anti_range () const
298 tree ttype
= type ();
299 unsigned int precision
= TYPE_PRECISION (ttype
);
300 signop sign
= TYPE_SIGN (ttype
);
301 return (num_pairs () > 1
303 && lower_bound () == wi::min_value (precision
, sign
)
304 && upper_bound () == wi::max_value (precision
, sign
));
308 irange::copy_legacy_to_multi_range (const irange
&src
)
310 gcc_checking_assert (src
.legacy_mode_p ());
311 gcc_checking_assert (!legacy_mode_p ());
312 if (src
.undefined_p ())
314 else if (src
.varying_p ())
315 set_varying (src
.type ());
318 if (range_has_numeric_bounds_p (&src
))
319 set (src
.min (), src
.max (), src
.kind ());
322 value_range
cst (src
);
323 cst
.normalize_symbolics ();
324 gcc_checking_assert (cst
.varying_p () || cst
.kind () == VR_RANGE
);
325 set (cst
.min (), cst
.max ());
330 // Copy any type of irange into a legacy.
333 irange::copy_to_legacy (const irange
&src
)
335 gcc_checking_assert (legacy_mode_p ());
336 // Handle legacy to legacy and other things that are easy to copy.
337 if (src
.legacy_mode_p () || src
.varying_p () || src
.undefined_p ())
339 m_num_ranges
= src
.m_num_ranges
;
340 m_base
[0] = src
.m_base
[0];
341 m_base
[1] = src
.m_base
[1];
343 m_nonzero_mask
= src
.m_nonzero_mask
;
346 // Copy multi-range to legacy.
347 if (src
.maybe_anti_range ())
349 int_range
<3> r (src
);
351 // Use tree variants to save on tree -> wi -> tree conversions.
352 set (r
.tree_lower_bound (0), r
.tree_upper_bound (0), VR_ANTI_RANGE
);
355 set (src
.tree_lower_bound (), src
.tree_upper_bound ());
358 // Swap MIN/MAX if they are out of order and adjust KIND appropriately.
361 swap_out_of_order_endpoints (tree
&min
, tree
&max
, value_range_kind
&kind
)
363 gcc_checking_assert (kind
!= VR_UNDEFINED
);
364 if (kind
== VR_VARYING
)
366 /* Wrong order for min and max, to swap them and the VR type we need
368 if (tree_int_cst_lt (max
, min
))
372 /* For one bit precision if max < min, then the swapped
373 range covers all values, so for VR_RANGE it is varying and
374 for VR_ANTI_RANGE empty range, so drop to varying as well. */
375 if (TYPE_PRECISION (TREE_TYPE (min
)) == 1)
381 one
= build_int_cst (TREE_TYPE (min
), 1);
382 tmp
= int_const_binop (PLUS_EXPR
, max
, one
);
383 max
= int_const_binop (MINUS_EXPR
, min
, one
);
386 /* There's one corner case, if we had [C+1, C] before we now have
387 that again. But this represents an empty value range, so drop
388 to varying in this case. */
389 if (tree_int_cst_lt (max
, min
))
394 kind
= kind
== VR_RANGE
? VR_ANTI_RANGE
: VR_RANGE
;
399 irange::irange_set (tree min
, tree max
)
401 gcc_checking_assert (!POLY_INT_CST_P (min
));
402 gcc_checking_assert (!POLY_INT_CST_P (max
));
408 m_nonzero_mask
= NULL
;
416 irange::irange_set_1bit_anti_range (tree min
, tree max
)
418 tree type
= TREE_TYPE (min
);
419 gcc_checking_assert (TYPE_PRECISION (type
) == 1);
421 if (operand_equal_p (min
, max
))
423 // Since these are 1-bit quantities, they can only be [MIN,MIN]
425 if (vrp_val_is_min (min
))
426 min
= max
= vrp_val_max (type
);
428 min
= max
= vrp_val_min (type
);
433 // The only alternative is [MIN,MAX], which is the empty range.
434 gcc_checking_assert (vrp_val_is_min (min
));
435 gcc_checking_assert (vrp_val_is_max (max
));
443 irange::irange_set_anti_range (tree min
, tree max
)
445 gcc_checking_assert (!POLY_INT_CST_P (min
));
446 gcc_checking_assert (!POLY_INT_CST_P (max
));
448 if (TYPE_PRECISION (TREE_TYPE (min
)) == 1)
450 irange_set_1bit_anti_range (min
, max
);
455 tree type
= TREE_TYPE (min
);
456 signop sign
= TYPE_SIGN (type
);
457 int_range
<2> type_range (type
);
458 // Calculate INVERSE([I,J]) as [-MIN, I-1][J+1, +MAX].
460 wi::overflow_type ovf
;
462 wide_int w_min
= wi::to_wide (min
);
463 if (wi::ne_p (w_min
, type_range
.lower_bound ()))
465 wide_int lim1
= wi::sub (w_min
, 1, sign
, &ovf
);
466 gcc_checking_assert (ovf
!= wi::OVF_OVERFLOW
);
467 m_base
[0] = type_range
.tree_lower_bound (0);
468 m_base
[1] = wide_int_to_tree (type
, lim1
);
471 wide_int w_max
= wi::to_wide (max
);
472 if (wi::ne_p (w_max
, type_range
.upper_bound ()))
474 wide_int lim2
= wi::add (w_max
, 1, sign
, &ovf
);
475 gcc_checking_assert (ovf
!= wi::OVF_OVERFLOW
);
476 m_base
[m_num_ranges
* 2] = wide_int_to_tree (type
, lim2
);
477 m_base
[m_num_ranges
* 2 + 1] = type_range
.tree_upper_bound (0);
482 m_nonzero_mask
= NULL
;
489 /* Set value range to the canonical form of {VRTYPE, MIN, MAX, EQUIV}.
490 This means adjusting VRTYPE, MIN and MAX representing the case of a
491 wrapping range with MAX < MIN covering [MIN, type_max] U [type_min, MAX]
492 as anti-rage ~[MAX+1, MIN-1]. Likewise for wrapping anti-ranges.
493 In corner cases where MAX+1 or MIN-1 wraps this will fall back
495 This routine exists to ease canonicalization in the case where we
496 extract ranges from var + CST op limit. */
499 irange::set (tree min
, tree max
, value_range_kind kind
)
501 if (kind
!= VR_UNDEFINED
)
503 if (TREE_OVERFLOW_P (min
))
504 min
= drop_tree_overflow (min
);
505 if (TREE_OVERFLOW_P (max
))
506 max
= drop_tree_overflow (max
);
509 if (!legacy_mode_p ())
511 if (kind
== VR_RANGE
)
512 irange_set (min
, max
);
515 gcc_checking_assert (kind
== VR_ANTI_RANGE
);
516 irange_set_anti_range (min
, max
);
520 if (kind
== VR_UNDEFINED
)
522 irange::set_undefined ();
526 if (kind
== VR_VARYING
527 || POLY_INT_CST_P (min
)
528 || POLY_INT_CST_P (max
))
530 set_varying (TREE_TYPE (min
));
534 // Nothing to canonicalize for symbolic ranges.
535 if (TREE_CODE (min
) != INTEGER_CST
536 || TREE_CODE (max
) != INTEGER_CST
)
542 m_nonzero_mask
= NULL
;
546 swap_out_of_order_endpoints (min
, max
, kind
);
547 if (kind
== VR_VARYING
)
549 set_varying (TREE_TYPE (min
));
553 // Anti-ranges that can be represented as ranges should be so.
554 if (kind
== VR_ANTI_RANGE
)
556 bool is_min
= vrp_val_is_min (min
);
557 bool is_max
= vrp_val_is_max (max
);
559 if (is_min
&& is_max
)
561 // Fall through. This will either be normalized as
562 // VR_UNDEFINED if the anti-range spans the entire
563 // precision, or it will remain an VR_ANTI_RANGE in the case
564 // of an -fstrict-enum where [MIN,MAX] is less than the span
565 // of underlying precision.
567 else if (TYPE_PRECISION (TREE_TYPE (min
)) == 1)
569 irange_set_1bit_anti_range (min
, max
);
574 tree one
= build_int_cst (TREE_TYPE (max
), 1);
575 min
= int_const_binop (PLUS_EXPR
, max
, one
);
576 max
= vrp_val_max (TREE_TYPE (max
));
581 tree one
= build_int_cst (TREE_TYPE (min
), 1);
582 max
= int_const_binop (MINUS_EXPR
, min
, one
);
583 min
= vrp_val_min (TREE_TYPE (min
));
592 m_nonzero_mask
= NULL
;
598 // Check the validity of the range.
601 irange::verify_range ()
603 gcc_checking_assert (m_discriminator
== VR_IRANGE
);
604 if (m_kind
== VR_UNDEFINED
)
606 gcc_checking_assert (m_num_ranges
== 0);
607 gcc_checking_assert (!m_nonzero_mask
);
611 gcc_checking_assert (wi::to_wide (m_nonzero_mask
) != -1);
612 if (m_kind
== VR_VARYING
)
614 gcc_checking_assert (!m_nonzero_mask
);
615 gcc_checking_assert (m_num_ranges
== 1);
616 gcc_checking_assert (varying_compatible_p ());
619 if (!legacy_mode_p ())
621 gcc_checking_assert (m_num_ranges
!= 0);
622 gcc_checking_assert (!varying_compatible_p ());
623 for (unsigned i
= 0; i
< m_num_ranges
; ++i
)
625 tree lb
= tree_lower_bound (i
);
626 tree ub
= tree_upper_bound (i
);
627 int c
= compare_values (lb
, ub
);
628 gcc_checking_assert (c
== 0 || c
== -1);
632 if (m_kind
== VR_RANGE
|| m_kind
== VR_ANTI_RANGE
)
634 gcc_checking_assert (m_num_ranges
== 1);
635 int cmp
= compare_values (tree_lower_bound (0), tree_upper_bound (0));
636 gcc_checking_assert (cmp
== 0 || cmp
== -1 || cmp
== -2);
640 // Return the lower bound for a sub-range. PAIR is the sub-range in
644 irange::legacy_lower_bound (unsigned pair
) const
646 gcc_checking_assert (legacy_mode_p ());
649 value_range
numeric_range (*this);
650 numeric_range
.normalize_symbolics ();
651 return numeric_range
.legacy_lower_bound (pair
);
653 gcc_checking_assert (m_num_ranges
> 0);
654 gcc_checking_assert (pair
+ 1 <= num_pairs ());
655 if (m_kind
== VR_ANTI_RANGE
)
657 tree typ
= type (), t
;
658 if (pair
== 1 || vrp_val_is_min (min ()))
659 t
= wide_int_to_tree (typ
, wi::to_wide (max ()) + 1);
661 t
= vrp_val_min (typ
);
662 return wi::to_wide (t
);
664 return wi::to_wide (tree_lower_bound (pair
));
667 // Return the upper bound for a sub-range. PAIR is the sub-range in
671 irange::legacy_upper_bound (unsigned pair
) const
673 gcc_checking_assert (legacy_mode_p ());
676 value_range
numeric_range (*this);
677 numeric_range
.normalize_symbolics ();
678 return numeric_range
.legacy_upper_bound (pair
);
680 gcc_checking_assert (m_num_ranges
> 0);
681 gcc_checking_assert (pair
+ 1 <= num_pairs ());
682 if (m_kind
== VR_ANTI_RANGE
)
684 tree typ
= type (), t
;
685 if (pair
== 1 || vrp_val_is_min (min ()))
686 t
= vrp_val_max (typ
);
688 t
= wide_int_to_tree (typ
, wi::to_wide (min ()) - 1);
689 return wi::to_wide (t
);
691 return wi::to_wide (tree_upper_bound (pair
));
695 irange::legacy_equal_p (const irange
&other
) const
697 gcc_checking_assert (legacy_mode_p () && other
.legacy_mode_p ());
699 if (m_kind
!= other
.m_kind
)
701 if (m_kind
== VR_UNDEFINED
)
703 if (m_kind
== VR_VARYING
)
705 return (range_compatible_p (type (), other
.type ())
706 && vrp_operand_equal_p (m_nonzero_mask
, other
.m_nonzero_mask
));
708 return (vrp_operand_equal_p (tree_lower_bound (0),
709 other
.tree_lower_bound (0))
710 && vrp_operand_equal_p (tree_upper_bound (0),
711 other
.tree_upper_bound (0))
712 && vrp_operand_equal_p (m_nonzero_mask
, other
.m_nonzero_mask
));
716 irange::operator== (const irange
&other
) const
718 if (legacy_mode_p ())
720 if (other
.legacy_mode_p ())
721 return legacy_equal_p (other
);
722 value_range
tmp (other
);
723 return legacy_equal_p (tmp
);
725 if (other
.legacy_mode_p ())
727 value_range
tmp2 (*this);
728 return tmp2
.legacy_equal_p (other
);
731 if (m_num_ranges
!= other
.m_num_ranges
)
734 for (unsigned i
= 0; i
< m_num_ranges
; ++i
)
736 tree lb
= tree_lower_bound (i
);
737 tree ub
= tree_upper_bound (i
);
738 tree lb_other
= other
.tree_lower_bound (i
);
739 tree ub_other
= other
.tree_upper_bound (i
);
740 if (!operand_equal_p (lb
, lb_other
, 0)
741 || !operand_equal_p (ub
, ub_other
, 0))
744 return vrp_operand_equal_p (m_nonzero_mask
, other
.m_nonzero_mask
);
747 /* Return TRUE if this is a symbolic range. */
750 irange::symbolic_p () const
752 return (m_num_ranges
> 0
753 && (!is_gimple_min_invariant (min ())
754 || !is_gimple_min_invariant (max ())));
757 /* Return TRUE if this is a constant range. */
760 irange::constant_p () const
762 return (m_num_ranges
> 0
763 && TREE_CODE (min ()) == INTEGER_CST
764 && TREE_CODE (max ()) == INTEGER_CST
);
767 /* If range is a singleton, place it in RESULT and return TRUE.
768 Note: A singleton can be any gimple invariant, not just constants.
769 So, [&x, &x] counts as a singleton. */
772 irange::singleton_p (tree
*result
) const
774 if (!legacy_mode_p ())
776 if (num_pairs () == 1 && (wi::to_wide (tree_lower_bound ())
777 == wi::to_wide (tree_upper_bound ())))
780 *result
= tree_lower_bound ();
785 if (m_kind
== VR_ANTI_RANGE
)
789 if (TYPE_PRECISION (type ()) == 1)
797 if (num_pairs () == 1)
799 value_range vr0
, vr1
;
800 ranges_from_anti_range ((const value_range
*) this, &vr0
, &vr1
);
801 return vr0
.singleton_p (result
);
804 // Catches non-numeric extremes as well.
805 if (m_kind
== VR_RANGE
806 && vrp_operand_equal_p (min (), max ())
807 && is_gimple_min_invariant (min ()))
816 /* Return 1 if VAL is inside value range.
817 0 if VAL is not inside value range.
818 -2 if we cannot tell either way.
820 Benchmark compile/20001226-1.c compilation time after changing this
824 irange::value_inside_range (tree val
) const
832 if (!legacy_mode_p () && TREE_CODE (val
) == INTEGER_CST
)
833 return contains_p (val
);
835 int cmp1
= operand_less_p (val
, min ());
839 return m_kind
!= VR_RANGE
;
841 int cmp2
= operand_less_p (max (), val
);
845 if (m_kind
== VR_RANGE
)
851 /* Return TRUE if it is possible that range contains VAL. */
854 irange::may_contain_p (tree val
) const
856 return value_inside_range (val
) != 0;
859 /* Return TRUE if range contains INTEGER_CST. */
860 /* Return 1 if VAL is inside value range.
861 0 if VAL is not inside value range.
863 Benchmark compile/20001226-1.c compilation time after changing this
868 irange::contains_p (tree cst
) const
873 if (legacy_mode_p ())
875 gcc_checking_assert (TREE_CODE (cst
) == INTEGER_CST
);
878 value_range
numeric_range (*this);
879 numeric_range
.normalize_symbolics ();
880 return numeric_range
.contains_p (cst
);
882 return value_inside_range (cst
) == 1;
885 gcc_checking_assert (TREE_CODE (cst
) == INTEGER_CST
);
889 wide_int cstw
= wi::to_wide (cst
);
890 if (cstw
!= 0 && wi::bit_and (wi::to_wide (m_nonzero_mask
), cstw
) == 0)
894 signop sign
= TYPE_SIGN (TREE_TYPE (cst
));
895 wide_int v
= wi::to_wide (cst
);
896 for (unsigned r
= 0; r
< m_num_ranges
; ++r
)
898 if (wi::lt_p (v
, lower_bound (r
), sign
))
900 if (wi::le_p (v
, upper_bound (r
), sign
))
908 /* Normalize addresses into constants. */
911 irange::normalize_addresses ()
916 if (!POINTER_TYPE_P (type ()) || range_has_numeric_bounds_p (this))
919 if (!range_includes_zero_p (this))
921 gcc_checking_assert (TREE_CODE (min ()) == ADDR_EXPR
922 || TREE_CODE (max ()) == ADDR_EXPR
);
923 set_nonzero (type ());
926 set_varying (type ());
929 /* Normalize symbolics and addresses into constants. */
932 irange::normalize_symbolics ()
934 if (varying_p () || undefined_p ())
937 tree ttype
= type ();
938 bool min_symbolic
= !is_gimple_min_invariant (min ());
939 bool max_symbolic
= !is_gimple_min_invariant (max ());
940 if (!min_symbolic
&& !max_symbolic
)
942 normalize_addresses ();
946 // [SYM, SYM] -> VARYING
947 if (min_symbolic
&& max_symbolic
)
952 if (kind () == VR_RANGE
)
954 // [SYM, NUM] -> [-MIN, NUM]
957 set (vrp_val_min (ttype
), max ());
960 // [NUM, SYM] -> [NUM, +MAX]
961 set (min (), vrp_val_max (ttype
));
964 gcc_checking_assert (kind () == VR_ANTI_RANGE
);
965 // ~[SYM, NUM] -> [NUM + 1, +MAX]
968 if (!vrp_val_is_max (max ()))
970 tree n
= wide_int_to_tree (ttype
, wi::to_wide (max ()) + 1);
971 set (n
, vrp_val_max (ttype
));
977 // ~[NUM, SYM] -> [-MIN, NUM - 1]
978 if (!vrp_val_is_min (min ()))
980 tree n
= wide_int_to_tree (ttype
, wi::to_wide (min ()) - 1);
981 set (vrp_val_min (ttype
), n
);
987 /* Intersect the two value-ranges { *VR0TYPE, *VR0MIN, *VR0MAX } and
988 { VR1TYPE, VR0MIN, VR0MAX } and store the result
989 in { *VR0TYPE, *VR0MIN, *VR0MAX }. This may not be the smallest
990 possible such range. The resulting range is not canonicalized. */
993 intersect_ranges (enum value_range_kind
*vr0type
,
994 tree
*vr0min
, tree
*vr0max
,
995 enum value_range_kind vr1type
,
996 tree vr1min
, tree vr1max
)
998 bool mineq
= vrp_operand_equal_p (*vr0min
, vr1min
);
999 bool maxeq
= vrp_operand_equal_p (*vr0max
, vr1max
);
1001 /* [] is vr0, () is vr1 in the following classification comments. */
1005 if (*vr0type
== vr1type
)
1006 /* Nothing to do for equal ranges. */
1008 else if ((*vr0type
== VR_RANGE
1009 && vr1type
== VR_ANTI_RANGE
)
1010 || (*vr0type
== VR_ANTI_RANGE
1011 && vr1type
== VR_RANGE
))
1013 /* For anti-range with range intersection the result is empty. */
1014 *vr0type
= VR_UNDEFINED
;
1015 *vr0min
= NULL_TREE
;
1016 *vr0max
= NULL_TREE
;
1021 else if (operand_less_p (*vr0max
, vr1min
) == 1
1022 || operand_less_p (vr1max
, *vr0min
) == 1)
1024 /* [ ] ( ) or ( ) [ ]
1025 If the ranges have an empty intersection, the result of the
1026 intersect operation is the range for intersecting an
1027 anti-range with a range or empty when intersecting two ranges. */
1028 if (*vr0type
== VR_RANGE
1029 && vr1type
== VR_ANTI_RANGE
)
1031 else if (*vr0type
== VR_ANTI_RANGE
1032 && vr1type
== VR_RANGE
)
1038 else if (*vr0type
== VR_RANGE
1039 && vr1type
== VR_RANGE
)
1041 *vr0type
= VR_UNDEFINED
;
1042 *vr0min
= NULL_TREE
;
1043 *vr0max
= NULL_TREE
;
1045 else if (*vr0type
== VR_ANTI_RANGE
1046 && vr1type
== VR_ANTI_RANGE
)
1048 /* If the anti-ranges are adjacent to each other merge them. */
1049 if (TREE_CODE (*vr0max
) == INTEGER_CST
1050 && TREE_CODE (vr1min
) == INTEGER_CST
1051 && operand_less_p (*vr0max
, vr1min
) == 1
1052 && integer_onep (int_const_binop (MINUS_EXPR
,
1055 else if (TREE_CODE (vr1max
) == INTEGER_CST
1056 && TREE_CODE (*vr0min
) == INTEGER_CST
1057 && operand_less_p (vr1max
, *vr0min
) == 1
1058 && integer_onep (int_const_binop (MINUS_EXPR
,
1061 /* Else arbitrarily take VR0. */
1064 else if ((maxeq
|| operand_less_p (vr1max
, *vr0max
) == 1)
1065 && (mineq
|| operand_less_p (*vr0min
, vr1min
) == 1))
1067 /* [ ( ) ] or [( ) ] or [ ( )] */
1068 if (*vr0type
== VR_RANGE
1069 && vr1type
== VR_RANGE
)
1071 /* If both are ranges the result is the inner one. */
1076 else if (*vr0type
== VR_RANGE
1077 && vr1type
== VR_ANTI_RANGE
)
1079 /* Choose the right gap if the left one is empty. */
1082 if (TREE_CODE (vr1max
) != INTEGER_CST
)
1084 else if (TYPE_PRECISION (TREE_TYPE (vr1max
)) == 1
1085 && !TYPE_UNSIGNED (TREE_TYPE (vr1max
)))
1087 = int_const_binop (MINUS_EXPR
, vr1max
,
1088 build_int_cst (TREE_TYPE (vr1max
), -1));
1091 = int_const_binop (PLUS_EXPR
, vr1max
,
1092 build_int_cst (TREE_TYPE (vr1max
), 1));
1094 /* Choose the left gap if the right one is empty. */
1097 if (TREE_CODE (vr1min
) != INTEGER_CST
)
1099 else if (TYPE_PRECISION (TREE_TYPE (vr1min
)) == 1
1100 && !TYPE_UNSIGNED (TREE_TYPE (vr1min
)))
1102 = int_const_binop (PLUS_EXPR
, vr1min
,
1103 build_int_cst (TREE_TYPE (vr1min
), -1));
1106 = int_const_binop (MINUS_EXPR
, vr1min
,
1107 build_int_cst (TREE_TYPE (vr1min
), 1));
1109 /* Choose the anti-range if the range is effectively varying. */
1110 else if (vrp_val_is_min (*vr0min
)
1111 && vrp_val_is_max (*vr0max
))
1117 /* Else choose the range. */
1119 else if (*vr0type
== VR_ANTI_RANGE
1120 && vr1type
== VR_ANTI_RANGE
)
1121 /* If both are anti-ranges the result is the outer one. */
1123 else if (*vr0type
== VR_ANTI_RANGE
1124 && vr1type
== VR_RANGE
)
1126 /* The intersection is empty. */
1127 *vr0type
= VR_UNDEFINED
;
1128 *vr0min
= NULL_TREE
;
1129 *vr0max
= NULL_TREE
;
1134 else if ((maxeq
|| operand_less_p (*vr0max
, vr1max
) == 1)
1135 && (mineq
|| operand_less_p (vr1min
, *vr0min
) == 1))
1137 /* ( [ ] ) or ([ ] ) or ( [ ]) */
1138 if (*vr0type
== VR_RANGE
1139 && vr1type
== VR_RANGE
)
1140 /* Choose the inner range. */
1142 else if (*vr0type
== VR_ANTI_RANGE
1143 && vr1type
== VR_RANGE
)
1145 /* Choose the right gap if the left is empty. */
1148 *vr0type
= VR_RANGE
;
1149 if (TREE_CODE (*vr0max
) != INTEGER_CST
)
1151 else if (TYPE_PRECISION (TREE_TYPE (*vr0max
)) == 1
1152 && !TYPE_UNSIGNED (TREE_TYPE (*vr0max
)))
1154 = int_const_binop (MINUS_EXPR
, *vr0max
,
1155 build_int_cst (TREE_TYPE (*vr0max
), -1));
1158 = int_const_binop (PLUS_EXPR
, *vr0max
,
1159 build_int_cst (TREE_TYPE (*vr0max
), 1));
1162 /* Choose the left gap if the right is empty. */
1165 *vr0type
= VR_RANGE
;
1166 if (TREE_CODE (*vr0min
) != INTEGER_CST
)
1168 else if (TYPE_PRECISION (TREE_TYPE (*vr0min
)) == 1
1169 && !TYPE_UNSIGNED (TREE_TYPE (*vr0min
)))
1171 = int_const_binop (PLUS_EXPR
, *vr0min
,
1172 build_int_cst (TREE_TYPE (*vr0min
), -1));
1175 = int_const_binop (MINUS_EXPR
, *vr0min
,
1176 build_int_cst (TREE_TYPE (*vr0min
), 1));
1179 /* Choose the anti-range if the range is effectively varying. */
1180 else if (vrp_val_is_min (vr1min
)
1181 && vrp_val_is_max (vr1max
))
1183 /* Choose the anti-range if it is ~[0,0], that range is special
1184 enough to special case when vr1's range is relatively wide.
1185 At least for types bigger than int - this covers pointers
1186 and arguments to functions like ctz. */
1187 else if (*vr0min
== *vr0max
1188 && integer_zerop (*vr0min
)
1189 && ((TYPE_PRECISION (TREE_TYPE (*vr0min
))
1190 >= TYPE_PRECISION (integer_type_node
))
1191 || POINTER_TYPE_P (TREE_TYPE (*vr0min
)))
1192 && TREE_CODE (vr1max
) == INTEGER_CST
1193 && TREE_CODE (vr1min
) == INTEGER_CST
1194 && (wi::clz (wi::to_wide (vr1max
) - wi::to_wide (vr1min
))
1195 < TYPE_PRECISION (TREE_TYPE (*vr0min
)) / 2))
1197 /* Else choose the range. */
1205 else if (*vr0type
== VR_ANTI_RANGE
1206 && vr1type
== VR_ANTI_RANGE
)
1208 /* If both are anti-ranges the result is the outer one. */
1213 else if (vr1type
== VR_ANTI_RANGE
1214 && *vr0type
== VR_RANGE
)
1216 /* The intersection is empty. */
1217 *vr0type
= VR_UNDEFINED
;
1218 *vr0min
= NULL_TREE
;
1219 *vr0max
= NULL_TREE
;
1224 else if ((operand_less_p (vr1min
, *vr0max
) == 1
1225 || operand_equal_p (vr1min
, *vr0max
, 0))
1226 && operand_less_p (*vr0min
, vr1min
) == 1
1227 && operand_less_p (*vr0max
, vr1max
) == 1)
1229 /* [ ( ] ) or [ ]( ) */
1230 if (*vr0type
== VR_ANTI_RANGE
1231 && vr1type
== VR_ANTI_RANGE
)
1233 else if (*vr0type
== VR_RANGE
1234 && vr1type
== VR_RANGE
)
1236 else if (*vr0type
== VR_RANGE
1237 && vr1type
== VR_ANTI_RANGE
)
1239 if (TREE_CODE (vr1min
) == INTEGER_CST
)
1240 *vr0max
= int_const_binop (MINUS_EXPR
, vr1min
,
1241 build_int_cst (TREE_TYPE (vr1min
), 1));
1245 else if (*vr0type
== VR_ANTI_RANGE
1246 && vr1type
== VR_RANGE
)
1248 *vr0type
= VR_RANGE
;
1249 if (TREE_CODE (*vr0max
) == INTEGER_CST
)
1250 *vr0min
= int_const_binop (PLUS_EXPR
, *vr0max
,
1251 build_int_cst (TREE_TYPE (*vr0max
), 1));
1259 else if ((operand_less_p (*vr0min
, vr1max
) == 1
1260 || operand_equal_p (*vr0min
, vr1max
, 0))
1261 && operand_less_p (vr1min
, *vr0min
) == 1
1262 && operand_less_p (vr1max
, *vr0max
) == 1)
1264 /* ( [ ) ] or ( )[ ] */
1265 if (*vr0type
== VR_ANTI_RANGE
1266 && vr1type
== VR_ANTI_RANGE
)
1268 else if (*vr0type
== VR_RANGE
1269 && vr1type
== VR_RANGE
)
1271 else if (*vr0type
== VR_RANGE
1272 && vr1type
== VR_ANTI_RANGE
)
1274 if (TREE_CODE (vr1max
) == INTEGER_CST
)
1275 *vr0min
= int_const_binop (PLUS_EXPR
, vr1max
,
1276 build_int_cst (TREE_TYPE (vr1max
), 1));
1280 else if (*vr0type
== VR_ANTI_RANGE
1281 && vr1type
== VR_RANGE
)
1283 *vr0type
= VR_RANGE
;
1284 if (TREE_CODE (*vr0min
) == INTEGER_CST
)
1285 *vr0max
= int_const_binop (MINUS_EXPR
, *vr0min
,
1286 build_int_cst (TREE_TYPE (*vr0min
), 1));
1295 /* If we know the intersection is empty, there's no need to
1296 conservatively add anything else to the set. */
1297 if (*vr0type
== VR_UNDEFINED
)
1300 /* As a fallback simply use { *VRTYPE, *VR0MIN, *VR0MAX } as
1301 result for the intersection. That's always a conservative
1302 correct estimate unless VR1 is a constant singleton range
1303 in which case we choose that. */
1304 if (vr1type
== VR_RANGE
1305 && is_gimple_min_invariant (vr1min
)
1306 && vrp_operand_equal_p (vr1min
, vr1max
))
1314 /* Helper for the intersection operation for value ranges. Given two
1315 ranges VR0 and VR1, set VR0 to the intersection of both ranges.
1316 This may not be the smallest possible such range. */
1319 irange::legacy_intersect (irange
*vr0
, const irange
*vr1
)
1321 gcc_checking_assert (vr0
->legacy_mode_p ());
1322 gcc_checking_assert (vr1
->legacy_mode_p ());
1323 /* If either range is VR_VARYING the other one wins. */
1324 if (vr1
->varying_p ())
1326 if (vr0
->varying_p ())
1328 vr0
->set (vr1
->min (), vr1
->max (), vr1
->kind ());
1332 /* When either range is VR_UNDEFINED the resulting range is
1333 VR_UNDEFINED, too. */
1334 if (vr0
->undefined_p ())
1336 if (vr1
->undefined_p ())
1338 vr0
->set_undefined ();
1342 value_range_kind vr0kind
= vr0
->kind ();
1343 tree vr0min
= vr0
->min ();
1344 tree vr0max
= vr0
->max ();
1346 intersect_ranges (&vr0kind
, &vr0min
, &vr0max
,
1347 vr1
->kind (), vr1
->min (), vr1
->max ());
1349 // Pessimize nonzero masks, as we don't support them.
1350 m_nonzero_mask
= NULL
;
1352 /* Make sure to canonicalize the result though as the inversion of a
1353 VR_RANGE can still be a VR_RANGE. */
1354 if (vr0kind
== VR_UNDEFINED
)
1355 vr0
->set_undefined ();
1356 else if (vr0kind
== VR_VARYING
)
1358 /* If we failed, use the original VR0. */
1362 vr0
->set (vr0min
, vr0max
, vr0kind
);
1365 /* Union the two value-ranges { *VR0TYPE, *VR0MIN, *VR0MAX } and
1366 { VR1TYPE, VR0MIN, VR0MAX } and store the result
1367 in { *VR0TYPE, *VR0MIN, *VR0MAX }. This may not be the smallest
1368 possible such range. The resulting range is not canonicalized. */
1371 union_ranges (enum value_range_kind
*vr0type
,
1372 tree
*vr0min
, tree
*vr0max
,
1373 enum value_range_kind vr1type
,
1374 tree vr1min
, tree vr1max
)
1376 int cmpmin
= compare_values (*vr0min
, vr1min
);
1377 int cmpmax
= compare_values (*vr0max
, vr1max
);
1378 bool mineq
= cmpmin
== 0;
1379 bool maxeq
= cmpmax
== 0;
1381 /* [] is vr0, () is vr1 in the following classification comments. */
1385 if (*vr0type
== vr1type
)
1386 /* Nothing to do for equal ranges. */
1388 else if ((*vr0type
== VR_RANGE
1389 && vr1type
== VR_ANTI_RANGE
)
1390 || (*vr0type
== VR_ANTI_RANGE
1391 && vr1type
== VR_RANGE
))
1393 /* For anti-range with range union the result is varying. */
1399 else if (operand_less_p (*vr0max
, vr1min
) == 1
1400 || operand_less_p (vr1max
, *vr0min
) == 1)
1402 /* [ ] ( ) or ( ) [ ]
1403 If the ranges have an empty intersection, result of the union
1404 operation is the anti-range or if both are anti-ranges
1406 if (*vr0type
== VR_ANTI_RANGE
1407 && vr1type
== VR_ANTI_RANGE
)
1409 else if (*vr0type
== VR_ANTI_RANGE
1410 && vr1type
== VR_RANGE
)
1412 else if (*vr0type
== VR_RANGE
1413 && vr1type
== VR_ANTI_RANGE
)
1419 else if (*vr0type
== VR_RANGE
1420 && vr1type
== VR_RANGE
)
1422 /* The result is the convex hull of both ranges. */
1423 if (operand_less_p (*vr0max
, vr1min
) == 1)
1425 /* If the result can be an anti-range, create one. */
1426 if (TREE_CODE (*vr0max
) == INTEGER_CST
1427 && TREE_CODE (vr1min
) == INTEGER_CST
1428 && vrp_val_is_min (*vr0min
)
1429 && vrp_val_is_max (vr1max
))
1431 tree min
= int_const_binop (PLUS_EXPR
,
1433 build_int_cst (TREE_TYPE (*vr0max
), 1));
1434 tree max
= int_const_binop (MINUS_EXPR
,
1436 build_int_cst (TREE_TYPE (vr1min
), 1));
1437 if (!operand_less_p (max
, min
))
1439 *vr0type
= VR_ANTI_RANGE
;
1451 /* If the result can be an anti-range, create one. */
1452 if (TREE_CODE (vr1max
) == INTEGER_CST
1453 && TREE_CODE (*vr0min
) == INTEGER_CST
1454 && vrp_val_is_min (vr1min
)
1455 && vrp_val_is_max (*vr0max
))
1457 tree min
= int_const_binop (PLUS_EXPR
,
1459 build_int_cst (TREE_TYPE (vr1max
), 1));
1460 tree max
= int_const_binop (MINUS_EXPR
,
1462 build_int_cst (TREE_TYPE (*vr0min
), 1));
1463 if (!operand_less_p (max
, min
))
1465 *vr0type
= VR_ANTI_RANGE
;
1479 else if ((maxeq
|| cmpmax
== 1)
1480 && (mineq
|| cmpmin
== -1))
1482 /* [ ( ) ] or [( ) ] or [ ( )] */
1483 if (*vr0type
== VR_RANGE
1484 && vr1type
== VR_RANGE
)
1486 else if (*vr0type
== VR_ANTI_RANGE
1487 && vr1type
== VR_ANTI_RANGE
)
1493 else if (*vr0type
== VR_ANTI_RANGE
1494 && vr1type
== VR_RANGE
)
1496 /* Arbitrarily choose the right or left gap. */
1497 if (!mineq
&& TREE_CODE (vr1min
) == INTEGER_CST
)
1498 *vr0max
= int_const_binop (MINUS_EXPR
, vr1min
,
1499 build_int_cst (TREE_TYPE (vr1min
), 1));
1500 else if (!maxeq
&& TREE_CODE (vr1max
) == INTEGER_CST
)
1501 *vr0min
= int_const_binop (PLUS_EXPR
, vr1max
,
1502 build_int_cst (TREE_TYPE (vr1max
), 1));
1506 else if (*vr0type
== VR_RANGE
1507 && vr1type
== VR_ANTI_RANGE
)
1508 /* The result covers everything. */
1513 else if ((maxeq
|| cmpmax
== -1)
1514 && (mineq
|| cmpmin
== 1))
1516 /* ( [ ] ) or ([ ] ) or ( [ ]) */
1517 if (*vr0type
== VR_RANGE
1518 && vr1type
== VR_RANGE
)
1524 else if (*vr0type
== VR_ANTI_RANGE
1525 && vr1type
== VR_ANTI_RANGE
)
1527 else if (*vr0type
== VR_RANGE
1528 && vr1type
== VR_ANTI_RANGE
)
1530 *vr0type
= VR_ANTI_RANGE
;
1531 if (!mineq
&& TREE_CODE (*vr0min
) == INTEGER_CST
)
1533 *vr0max
= int_const_binop (MINUS_EXPR
, *vr0min
,
1534 build_int_cst (TREE_TYPE (*vr0min
), 1));
1537 else if (!maxeq
&& TREE_CODE (*vr0max
) == INTEGER_CST
)
1539 *vr0min
= int_const_binop (PLUS_EXPR
, *vr0max
,
1540 build_int_cst (TREE_TYPE (*vr0max
), 1));
1546 else if (*vr0type
== VR_ANTI_RANGE
1547 && vr1type
== VR_RANGE
)
1548 /* The result covers everything. */
1553 else if (cmpmin
== -1
1555 && (operand_less_p (vr1min
, *vr0max
) == 1
1556 || operand_equal_p (vr1min
, *vr0max
, 0)))
1558 /* [ ( ] ) or [ ]( ) */
1559 if (*vr0type
== VR_RANGE
1560 && vr1type
== VR_RANGE
)
1562 else if (*vr0type
== VR_ANTI_RANGE
1563 && vr1type
== VR_ANTI_RANGE
)
1565 else if (*vr0type
== VR_ANTI_RANGE
1566 && vr1type
== VR_RANGE
)
1568 if (TREE_CODE (vr1min
) == INTEGER_CST
)
1569 *vr0max
= int_const_binop (MINUS_EXPR
, vr1min
,
1570 build_int_cst (TREE_TYPE (vr1min
), 1));
1574 else if (*vr0type
== VR_RANGE
1575 && vr1type
== VR_ANTI_RANGE
)
1577 if (TREE_CODE (*vr0max
) == INTEGER_CST
)
1580 *vr0min
= int_const_binop (PLUS_EXPR
, *vr0max
,
1581 build_int_cst (TREE_TYPE (*vr0max
), 1));
1590 else if (cmpmin
== 1
1592 && (operand_less_p (*vr0min
, vr1max
) == 1
1593 || operand_equal_p (*vr0min
, vr1max
, 0)))
1595 /* ( [ ) ] or ( )[ ] */
1596 if (*vr0type
== VR_RANGE
1597 && vr1type
== VR_RANGE
)
1599 else if (*vr0type
== VR_ANTI_RANGE
1600 && vr1type
== VR_ANTI_RANGE
)
1602 else if (*vr0type
== VR_ANTI_RANGE
1603 && vr1type
== VR_RANGE
)
1605 if (TREE_CODE (vr1max
) == INTEGER_CST
)
1606 *vr0min
= int_const_binop (PLUS_EXPR
, vr1max
,
1607 build_int_cst (TREE_TYPE (vr1max
), 1));
1611 else if (*vr0type
== VR_RANGE
1612 && vr1type
== VR_ANTI_RANGE
)
1614 if (TREE_CODE (*vr0min
) == INTEGER_CST
)
1617 *vr0max
= int_const_binop (MINUS_EXPR
, *vr0min
,
1618 build_int_cst (TREE_TYPE (*vr0min
), 1));
1633 *vr0type
= VR_VARYING
;
1634 *vr0min
= NULL_TREE
;
1635 *vr0max
= NULL_TREE
;
1638 /* Helper for meet operation for value ranges. Given two ranges VR0
1639 and VR1, set VR0 to the union of both ranges. This may not be the
1640 smallest possible such range. */
1643 irange::legacy_union (irange
*vr0
, const irange
*vr1
)
1645 gcc_checking_assert (vr0
->legacy_mode_p ());
1646 gcc_checking_assert (vr1
->legacy_mode_p ());
1648 /* VR0 has the resulting range if VR1 is undefined or VR0 is varying. */
1649 if (vr1
->undefined_p ()
1650 || vr0
->varying_p ())
1653 /* VR1 has the resulting range if VR0 is undefined or VR1 is varying. */
1654 if (vr0
->undefined_p ())
1656 vr0
->set (vr1
->min (), vr1
->max (), vr1
->kind ());
1660 if (vr1
->varying_p ())
1662 vr0
->set_varying (vr1
->type ());
1666 value_range_kind vr0kind
= vr0
->kind ();
1667 tree vr0min
= vr0
->min ();
1668 tree vr0max
= vr0
->max ();
1670 union_ranges (&vr0kind
, &vr0min
, &vr0max
,
1671 vr1
->kind (), vr1
->min (), vr1
->max ());
1673 // Pessimize nonzero masks, as we don't support them.
1674 m_nonzero_mask
= NULL
;
1676 if (vr0kind
== VR_UNDEFINED
)
1677 vr0
->set_undefined ();
1678 else if (vr0kind
== VR_VARYING
)
1680 /* Failed to find an efficient meet. Before giving up and
1681 setting the result to VARYING, see if we can at least derive
1682 a non-zero range. */
1683 if (range_includes_zero_p (vr0
) == 0
1684 && range_includes_zero_p (vr1
) == 0)
1685 vr0
->set_nonzero (vr0
->type ());
1687 vr0
->set_varying (vr0
->type ());
1690 vr0
->set (vr0min
, vr0max
, vr0kind
);
1693 /* Meet operation for value ranges. Given two value ranges VR0 and
1694 VR1, store in VR0 a range that contains both VR0 and VR1. This
1695 may not be the smallest possible such range.
1696 Return TRUE if the original value changes. */
1699 irange::legacy_verbose_union_ (const irange
*other
)
1701 if (legacy_mode_p ())
1703 if (!other
->legacy_mode_p ())
1705 int_range
<1> tmp
= *other
;
1706 legacy_union (this, &tmp
);
1709 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1711 fprintf (dump_file
, "Meeting\n ");
1712 dump_value_range (dump_file
, this);
1713 fprintf (dump_file
, "\nand\n ");
1714 dump_value_range (dump_file
, other
);
1715 fprintf (dump_file
, "\n");
1718 legacy_union (this, other
);
1720 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1722 fprintf (dump_file
, "to\n ");
1723 dump_value_range (dump_file
, this);
1724 fprintf (dump_file
, "\n");
1729 if (other
->legacy_mode_p ())
1731 int_range
<2> wider
= *other
;
1732 return irange_union (wider
);
1735 return irange_union (*other
);
1739 irange::legacy_verbose_intersect (const irange
*other
)
1741 if (legacy_mode_p ())
1743 if (!other
->legacy_mode_p ())
1745 int_range
<1> tmp
= *other
;
1746 legacy_intersect (this, &tmp
);
1749 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1751 fprintf (dump_file
, "Intersecting\n ");
1752 dump_value_range (dump_file
, this);
1753 fprintf (dump_file
, "\nand\n ");
1754 dump_value_range (dump_file
, other
);
1755 fprintf (dump_file
, "\n");
1758 legacy_intersect (this, other
);
1760 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1762 fprintf (dump_file
, "to\n ");
1763 dump_value_range (dump_file
, this);
1764 fprintf (dump_file
, "\n");
1769 if (other
->legacy_mode_p ())
1773 return irange_intersect (wider
);
1776 return irange_intersect (*other
);
1779 // Perform an efficient union with R when both ranges have only a single pair.
1780 // Excluded are VARYING and UNDEFINED ranges.
1782 // NOTE: It is the caller's responsibility to set the nonzero mask.
1785 irange::irange_single_pair_union (const irange
&r
)
1787 gcc_checking_assert (!undefined_p () && !varying_p ());
1788 gcc_checking_assert (!r
.undefined_p () && !varying_p ());
1790 signop sign
= TYPE_SIGN (TREE_TYPE (m_base
[0]));
1791 // Check if current lower bound is also the new lower bound.
1792 if (wi::le_p (wi::to_wide (m_base
[0]), wi::to_wide (r
.m_base
[0]), sign
))
1794 // If current upper bound is new upper bound, we're done.
1795 if (wi::le_p (wi::to_wide (r
.m_base
[1]), wi::to_wide (m_base
[1]), sign
))
1797 // Otherwise R has the new upper bound.
1798 // Check for overlap/touching ranges, or single target range.
1799 if (m_max_ranges
== 1
1800 || wi::to_widest (m_base
[1]) + 1 >= wi::to_widest (r
.m_base
[0]))
1801 m_base
[1] = r
.m_base
[1];
1804 // This is a dual range result.
1805 m_base
[2] = r
.m_base
[0];
1806 m_base
[3] = r
.m_base
[1];
1809 if (varying_compatible_p ())
1810 m_kind
= VR_VARYING
;
1814 // Set the new lower bound to R's lower bound.
1815 tree lb
= m_base
[0];
1816 m_base
[0] = r
.m_base
[0];
1818 // If R fully contains THIS range, just set the upper bound.
1819 if (wi::ge_p (wi::to_wide (r
.m_base
[1]), wi::to_wide (m_base
[1]), sign
))
1820 m_base
[1] = r
.m_base
[1];
1821 // Check for overlapping ranges, or target limited to a single range.
1822 else if (m_max_ranges
== 1
1823 || wi::to_widest (r
.m_base
[1]) + 1 >= wi::to_widest (lb
))
1825 // This has the new upper bound, just check for varying.
1826 if (varying_compatible_p ())
1827 m_kind
= VR_VARYING
;
1831 // Left with 2 pairs.
1834 m_base
[3] = m_base
[1];
1835 m_base
[1] = r
.m_base
[1];
1837 if (varying_compatible_p ())
1838 m_kind
= VR_VARYING
;
1842 // union_ for multi-ranges.
1845 irange::irange_union (const irange
&r
)
1847 gcc_checking_assert (!legacy_mode_p () && !r
.legacy_mode_p ());
1849 if (r
.undefined_p ())
1865 set_varying (type ());
1869 // Save the nonzero mask in case the set operations below clobber it.
1870 bool ret_nz
= union_nonzero_bits (r
);
1871 tree saved_nz
= m_nonzero_mask
;
1873 // The union_nonzero_bits may have turned things into a varying.
1877 // Special case one range union one range.
1878 if (m_num_ranges
== 1 && r
.m_num_ranges
== 1)
1880 bool ret
= irange_single_pair_union (r
);
1881 set_nonzero_bits (saved_nz
);
1884 return ret
|| ret_nz
;
1887 // If this ranges fully contains R, then we need do nothing.
1888 if (irange_contains_p (r
))
1891 // Do not worry about merging and such by reserving twice as many
1892 // pairs as needed, and then simply sort the 2 ranges into this
1893 // intermediate form.
1895 // The intermediate result will have the property that the beginning
1896 // of each range is <= the beginning of the next range. There may
1897 // be overlapping ranges at this point. I.e. this would be valid
1898 // [-20, 10], [-10, 0], [0, 20], [40, 90] as it satisfies this
1899 // contraint : -20 < -10 < 0 < 40. When the range is rebuilt into r,
1900 // the merge is performed.
1902 // [Xi,Yi]..[Xn,Yn] U [Xj,Yj]..[Xm,Ym] --> [Xk,Yk]..[Xp,Yp]
1903 auto_vec
<tree
, 20> res (m_num_ranges
* 2 + r
.m_num_ranges
* 2);
1904 unsigned i
= 0, j
= 0, k
= 0;
1906 while (i
< m_num_ranges
* 2 && j
< r
.m_num_ranges
* 2)
1908 // lower of Xi and Xj is the lowest point.
1909 if (wi::to_widest (m_base
[i
]) <= wi::to_widest (r
.m_base
[j
]))
1911 res
.quick_push (m_base
[i
]);
1912 res
.quick_push (m_base
[i
+ 1]);
1918 res
.quick_push (r
.m_base
[j
]);
1919 res
.quick_push (r
.m_base
[j
+ 1]);
1924 for ( ; i
< m_num_ranges
* 2; i
+= 2)
1926 res
.quick_push (m_base
[i
]);
1927 res
.quick_push (m_base
[i
+ 1]);
1930 for ( ; j
< r
.m_num_ranges
* 2; j
+= 2)
1932 res
.quick_push (r
.m_base
[j
]);
1933 res
.quick_push (r
.m_base
[j
+ 1]);
1937 // Now normalize the vector removing any overlaps.
1939 for (j
= 2; j
< k
; j
+= 2)
1941 // Current upper+1 is >= lower bound next pair, then we merge ranges.
1942 if (wi::to_widest (res
[i
- 1]) + 1 >= wi::to_widest (res
[j
]))
1944 // New upper bounds is greater of current or the next one.
1945 if (wi::to_widest (res
[j
+ 1]) > wi::to_widest (res
[i
- 1]))
1946 res
[i
- 1] = res
[j
+ 1];
1950 // This is a new distinct range, but no point in copying it
1951 // if it is already in the right place.
1955 res
[i
++] = res
[j
+ 1];
1962 // At this point, the vector should have i ranges, none overlapping.
1963 // Now it simply needs to be copied, and if there are too many
1964 // ranges, merge some. We wont do any analysis as to what the
1965 // "best" merges are, simply combine the final ranges into one.
1966 if (i
> m_max_ranges
* 2)
1968 res
[m_max_ranges
* 2 - 1] = res
[i
- 1];
1969 i
= m_max_ranges
* 2;
1972 for (j
= 0; j
< i
; j
++)
1973 m_base
[j
] = res
[j
];
1974 m_num_ranges
= i
/ 2;
1977 m_nonzero_mask
= saved_nz
;
1985 // Return TRUE if THIS fully contains R. No undefined or varying cases.
1988 irange::irange_contains_p (const irange
&r
) const
1990 gcc_checking_assert (!undefined_p () && !varying_p ());
1991 gcc_checking_assert (!r
.undefined_p () && !varying_p ());
1993 // In order for THIS to fully contain R, all of the pairs within R must
1994 // be fully contained by the pairs in this object.
1995 signop sign
= TYPE_SIGN (TREE_TYPE(m_base
[0]));
1998 tree rl
= r
.m_base
[0];
1999 tree ru
= r
.m_base
[1];
2004 // If r is contained within this range, move to the next R
2005 if (wi::ge_p (wi::to_wide (rl
), wi::to_wide (l
), sign
)
2006 && wi::le_p (wi::to_wide (ru
), wi::to_wide (u
), sign
))
2008 // This pair is OK, Either done, or bump to the next.
2009 if (++ri
>= r
.num_pairs ())
2011 rl
= r
.m_base
[ri
* 2];
2012 ru
= r
.m_base
[ri
* 2 + 1];
2015 // Otherwise, check if this's pair occurs before R's.
2016 if (wi::lt_p (wi::to_wide (u
), wi::to_wide (rl
), sign
))
2018 // THere's still at leats one pair of R left.
2019 if (++i
>= num_pairs ())
2022 u
= m_base
[i
* 2 + 1];
2031 // Intersect for multi-ranges. Return TRUE if anything changes.
2034 irange::irange_intersect (const irange
&r
)
2036 gcc_checking_assert (!legacy_mode_p () && !r
.legacy_mode_p ());
2037 gcc_checking_assert (undefined_p () || r
.undefined_p ()
2038 || range_compatible_p (type (), r
.type ()));
2042 if (r
.undefined_p ())
2048 // Save the nonzero mask in case the set operations below clobber it.
2049 bool ret_nz
= intersect_nonzero_bits (r
);
2050 tree saved_nz
= m_nonzero_mask
;
2059 set_nonzero_bits (saved_nz
);
2065 if (r
.num_pairs () == 1)
2067 bool res
= intersect (r
.lower_bound (), r
.upper_bound ());
2071 set_nonzero_bits (saved_nz
);
2072 return res
|| saved_nz
;
2075 // If R fully contains this, then intersection will change nothing.
2076 if (r
.irange_contains_p (*this))
2079 signop sign
= TYPE_SIGN (TREE_TYPE(m_base
[0]));
2080 unsigned bld_pair
= 0;
2081 unsigned bld_lim
= m_max_ranges
;
2082 int_range_max
r2 (*this);
2083 unsigned r2_lim
= r2
.num_pairs ();
2085 for (unsigned i
= 0; i
< r
.num_pairs (); )
2087 // If r1's upper is < r2's lower, we can skip r1's pair.
2088 tree ru
= r
.m_base
[i
* 2 + 1];
2089 tree r2l
= r2
.m_base
[i2
* 2];
2090 if (wi::lt_p (wi::to_wide (ru
), wi::to_wide (r2l
), sign
))
2095 // Likewise, skip r2's pair if its excluded.
2096 tree r2u
= r2
.m_base
[i2
* 2 + 1];
2097 tree rl
= r
.m_base
[i
* 2];
2098 if (wi::lt_p (wi::to_wide (r2u
), wi::to_wide (rl
), sign
))
2103 // No more r2, break.
2107 // Must be some overlap. Find the highest of the lower bounds,
2108 // and set it, unless the build limits lower bounds is already
2110 if (bld_pair
< bld_lim
)
2112 if (wi::ge_p (wi::to_wide (rl
), wi::to_wide (r2l
), sign
))
2113 m_base
[bld_pair
* 2] = rl
;
2115 m_base
[bld_pair
* 2] = r2l
;
2118 // Decrease and set a new upper.
2121 // ...and choose the lower of the upper bounds.
2122 if (wi::le_p (wi::to_wide (ru
), wi::to_wide (r2u
), sign
))
2124 m_base
[bld_pair
* 2 + 1] = ru
;
2126 // Move past the r1 pair and keep trying.
2132 m_base
[bld_pair
* 2 + 1] = r2u
;
2137 // No more r2, break.
2140 // r2 has the higher lower bound.
2143 // At the exit of this loop, it is one of 2 things:
2144 // ran out of r1, or r2, but either means we are done.
2145 m_num_ranges
= bld_pair
;
2148 if (!undefined_p ())
2149 m_nonzero_mask
= saved_nz
;
2159 // Multirange intersect for a specified wide_int [lb, ub] range.
2160 // Return TRUE if intersect changed anything.
2162 // NOTE: It is the caller's responsibility to intersect the nonzero masks.
2165 irange::intersect (const wide_int
& lb
, const wide_int
& ub
)
2167 // Undefined remains undefined.
2171 if (legacy_mode_p ())
2173 intersect (int_range
<1> (type (), lb
, ub
));
2177 tree range_type
= type();
2178 signop sign
= TYPE_SIGN (range_type
);
2180 gcc_checking_assert (TYPE_PRECISION (range_type
) == wi::get_precision (lb
));
2181 gcc_checking_assert (TYPE_PRECISION (range_type
) == wi::get_precision (ub
));
2183 // If this range is fuly contained, then intersection will do nothing.
2184 if (wi::ge_p (lower_bound (), lb
, sign
)
2185 && wi::le_p (upper_bound (), ub
, sign
))
2188 unsigned bld_index
= 0;
2189 unsigned pair_lim
= num_pairs ();
2190 for (unsigned i
= 0; i
< pair_lim
; i
++)
2192 tree pairl
= m_base
[i
* 2];
2193 tree pairu
= m_base
[i
* 2 + 1];
2194 // Once UB is less than a pairs lower bound, we're done.
2195 if (wi::lt_p (ub
, wi::to_wide (pairl
), sign
))
2197 // if LB is greater than this pairs upper, this pair is excluded.
2198 if (wi::lt_p (wi::to_wide (pairu
), lb
, sign
))
2201 // Must be some overlap. Find the highest of the lower bounds,
2203 if (wi::gt_p (lb
, wi::to_wide (pairl
), sign
))
2204 m_base
[bld_index
* 2] = wide_int_to_tree (range_type
, lb
);
2206 m_base
[bld_index
* 2] = pairl
;
2208 // ...and choose the lower of the upper bounds and if the base pair
2209 // has the lower upper bound, need to check next pair too.
2210 if (wi::lt_p (ub
, wi::to_wide (pairu
), sign
))
2212 m_base
[bld_index
++ * 2 + 1] = wide_int_to_tree (range_type
, ub
);
2216 m_base
[bld_index
++ * 2 + 1] = pairu
;
2219 m_num_ranges
= bld_index
;
2230 // Signed 1-bits are strange. You can't subtract 1, because you can't
2231 // represent the number 1. This works around that for the invert routine.
2233 static wide_int
inline
2234 subtract_one (const wide_int
&x
, tree type
, wi::overflow_type
&overflow
)
2236 if (TYPE_SIGN (type
) == SIGNED
)
2237 return wi::add (x
, -1, SIGNED
, &overflow
);
2239 return wi::sub (x
, 1, UNSIGNED
, &overflow
);
2242 // The analogous function for adding 1.
2244 static wide_int
inline
2245 add_one (const wide_int
&x
, tree type
, wi::overflow_type
&overflow
)
2247 if (TYPE_SIGN (type
) == SIGNED
)
2248 return wi::sub (x
, -1, SIGNED
, &overflow
);
2250 return wi::add (x
, 1, UNSIGNED
, &overflow
);
2253 // Return the inverse of a range.
2258 if (legacy_mode_p ())
2260 // We can't just invert VR_RANGE and VR_ANTI_RANGE because we may
2261 // create non-canonical ranges. Use the constructors instead.
2262 if (m_kind
== VR_RANGE
)
2263 *this = value_range (min (), max (), VR_ANTI_RANGE
);
2264 else if (m_kind
== VR_ANTI_RANGE
)
2265 *this = value_range (min (), max ());
2271 gcc_checking_assert (!undefined_p () && !varying_p ());
2272 m_nonzero_mask
= NULL
;
2274 // We always need one more set of bounds to represent an inverse, so
2275 // if we're at the limit, we can't properly represent things.
2277 // For instance, to represent the inverse of a 2 sub-range set
2278 // [5, 10][20, 30], we would need a 3 sub-range set
2279 // [-MIN, 4][11, 19][31, MAX].
2281 // In this case, return the most conservative thing.
2283 // However, if any of the extremes of the range are -MIN/+MAX, we
2284 // know we will not need an extra bound. For example:
2286 // INVERT([-MIN,20][30,40]) => [21,29][41,+MAX]
2287 // INVERT([-MIN,20][30,MAX]) => [21,29]
2288 tree ttype
= type ();
2289 unsigned prec
= TYPE_PRECISION (ttype
);
2290 signop sign
= TYPE_SIGN (ttype
);
2291 wide_int type_min
= wi::min_value (prec
, sign
);
2292 wide_int type_max
= wi::max_value (prec
, sign
);
2293 if (m_num_ranges
== m_max_ranges
2294 && lower_bound () != type_min
2295 && upper_bound () != type_max
)
2297 m_base
[1] = wide_int_to_tree (ttype
, type_max
);
2301 // The algorithm is as follows. To calculate INVERT ([a,b][c,d]), we
2302 // generate [-MIN, a-1][b+1, c-1][d+1, MAX].
2304 // If there is an over/underflow in the calculation for any
2305 // sub-range, we eliminate that subrange. This allows us to easily
2306 // calculate INVERT([-MIN, 5]) with: [-MIN, -MIN-1][6, MAX]. And since
2307 // we eliminate the underflow, only [6, MAX] remains.
2309 wi::overflow_type ovf
;
2310 // Construct leftmost range.
2311 int_range_max
orig_range (*this);
2312 unsigned nitems
= 0;
2314 // If this is going to underflow on the MINUS 1, don't even bother
2315 // checking. This also handles subtracting one from an unsigned 0,
2316 // which doesn't set the underflow bit.
2317 if (type_min
!= orig_range
.lower_bound ())
2319 m_base
[nitems
++] = wide_int_to_tree (ttype
, type_min
);
2320 tmp
= subtract_one (orig_range
.lower_bound (), ttype
, ovf
);
2321 m_base
[nitems
++] = wide_int_to_tree (ttype
, tmp
);
2326 // Construct middle ranges if applicable.
2327 if (orig_range
.num_pairs () > 1)
2330 for (; j
< (orig_range
.num_pairs () * 2) - 1; j
+= 2)
2332 // The middle ranges cannot have MAX/MIN, so there's no need
2333 // to check for unsigned overflow on the +1 and -1 here.
2334 tmp
= wi::add (wi::to_wide (orig_range
.m_base
[j
]), 1, sign
, &ovf
);
2335 m_base
[nitems
++] = wide_int_to_tree (ttype
, tmp
);
2336 tmp
= subtract_one (wi::to_wide (orig_range
.m_base
[j
+ 1]),
2338 m_base
[nitems
++] = wide_int_to_tree (ttype
, tmp
);
2344 // Construct rightmost range.
2346 // However, if this will overflow on the PLUS 1, don't even bother.
2347 // This also handles adding one to an unsigned MAX, which doesn't
2348 // set the overflow bit.
2349 if (type_max
!= wi::to_wide (orig_range
.m_base
[i
]))
2351 tmp
= add_one (wi::to_wide (orig_range
.m_base
[i
]), ttype
, ovf
);
2352 m_base
[nitems
++] = wide_int_to_tree (ttype
, tmp
);
2353 m_base
[nitems
++] = wide_int_to_tree (ttype
, type_max
);
2357 m_num_ranges
= nitems
/ 2;
2359 // We disallow undefined or varying coming in, so the result can
2360 // only be a VR_RANGE.
2361 gcc_checking_assert (m_kind
== VR_RANGE
);
2368 irange::set_nonzero_bits (tree mask
)
2370 gcc_checking_assert (!undefined_p ());
2376 m_nonzero_mask
= NULL
;
2377 // Clearing the mask may have turned a range into VARYING.
2382 m_nonzero_mask
= mask
;
2383 // Setting the mask may have turned a VARYING into a range.
2384 if (m_kind
== VR_VARYING
)
2392 irange::set_nonzero_bits (const wide_int_ref
&bits
)
2394 gcc_checking_assert (!undefined_p ());
2398 set_nonzero_bits (NULL
);
2401 set_nonzero_bits (wide_int_to_tree (type (), bits
));
2405 irange::get_nonzero_bits () const
2407 gcc_checking_assert (!undefined_p ());
2409 // Calculate the nonzero bits inherent in the range.
2410 wide_int min
= lower_bound ();
2411 wide_int max
= upper_bound ();
2412 wide_int xorv
= min
^ max
;
2415 unsigned prec
= TYPE_PRECISION (type ());
2416 xorv
= wi::mask (prec
- wi::clz (xorv
), false, prec
);
2418 wide_int mask
= min
| xorv
;
2420 // Return the nonzero bits augmented by the range.
2422 return mask
& wi::to_wide (m_nonzero_mask
);
2427 // Intersect the nonzero bits in R into THIS.
2430 irange::intersect_nonzero_bits (const irange
&r
)
2432 gcc_checking_assert (!undefined_p () && !r
.undefined_p ());
2434 if (m_nonzero_mask
|| r
.m_nonzero_mask
)
2436 wide_int nz
= wi::bit_and (get_nonzero_bits (),
2437 r
.get_nonzero_bits ());
2438 set_nonzero_bits (nz
);
2444 // Union the nonzero bits in R into THIS.
2447 irange::union_nonzero_bits (const irange
&r
)
2449 gcc_checking_assert (!undefined_p () && !r
.undefined_p ());
2451 if (m_nonzero_mask
|| r
.m_nonzero_mask
)
2453 wide_int nz
= wi::bit_or (get_nonzero_bits (),
2454 r
.get_nonzero_bits ());
2455 set_nonzero_bits (nz
);
2462 dump_value_range (FILE *file
, const vrange
*vr
)
2468 debug (const vrange
*vr
)
2470 dump_value_range (stderr
, vr
);
2471 fprintf (stderr
, "\n");
2475 debug (const vrange
&vr
)
2481 debug (const value_range
*vr
)
2483 dump_value_range (stderr
, vr
);
2484 fprintf (stderr
, "\n");
2488 debug (const value_range
&vr
)
2490 dump_value_range (stderr
, &vr
);
2491 fprintf (stderr
, "\n");
2494 /* Create two value-ranges in *VR0 and *VR1 from the anti-range *AR
2495 so that *VR0 U *VR1 == *AR. Returns true if that is possible,
2496 false otherwise. If *AR can be represented with a single range
2497 *VR1 will be VR_UNDEFINED. */
2500 ranges_from_anti_range (const value_range
*ar
,
2501 value_range
*vr0
, value_range
*vr1
)
2503 tree type
= ar
->type ();
2505 vr0
->set_undefined ();
2506 vr1
->set_undefined ();
2508 /* As a future improvement, we could handle ~[0, A] as: [-INF, -1] U
2509 [A+1, +INF]. Not sure if this helps in practice, though. */
2511 if (ar
->kind () != VR_ANTI_RANGE
2512 || TREE_CODE (ar
->min ()) != INTEGER_CST
2513 || TREE_CODE (ar
->max ()) != INTEGER_CST
2514 || !vrp_val_min (type
)
2515 || !vrp_val_max (type
))
2518 if (tree_int_cst_lt (vrp_val_min (type
), ar
->min ()))
2519 vr0
->set (vrp_val_min (type
),
2520 wide_int_to_tree (type
, wi::to_wide (ar
->min ()) - 1));
2521 if (tree_int_cst_lt (ar
->max (), vrp_val_max (type
)))
2522 vr1
->set (wide_int_to_tree (type
, wi::to_wide (ar
->max ()) + 1),
2523 vrp_val_max (type
));
2524 if (vr0
->undefined_p ())
2527 vr1
->set_undefined ();
2530 return !vr0
->undefined_p ();
2534 range_has_numeric_bounds_p (const irange
*vr
)
2536 return (!vr
->undefined_p ()
2537 && TREE_CODE (vr
->min ()) == INTEGER_CST
2538 && TREE_CODE (vr
->max ()) == INTEGER_CST
);
2541 /* Return whether VAL is equal to the maximum value of its type.
2542 We can't do a simple equality comparison with TYPE_MAX_VALUE because
2543 C typedefs and Ada subtypes can produce types whose TYPE_MAX_VALUE
2544 is not == to the integer constant with the same value in the type. */
2547 vrp_val_is_max (const_tree val
)
2549 tree type_max
= vrp_val_max (TREE_TYPE (val
));
2550 return (val
== type_max
2551 || (type_max
!= NULL_TREE
2552 && operand_equal_p (val
, type_max
, 0)));
2555 /* Return whether VAL is equal to the minimum value of its type. */
2558 vrp_val_is_min (const_tree val
)
2560 tree type_min
= vrp_val_min (TREE_TYPE (val
));
2561 return (val
== type_min
2562 || (type_min
!= NULL_TREE
2563 && operand_equal_p (val
, type_min
, 0)));
2566 /* Return true, if VAL1 and VAL2 are equal values for VRP purposes. */
2569 vrp_operand_equal_p (const_tree val1
, const_tree val2
)
2573 if (!val1
|| !val2
|| !operand_equal_p (val1
, val2
, 0))
2578 // ?? These stubs are for ipa-prop.cc which use a value_range in a
2579 // hash_traits. hash-traits.h defines an extern of gt_ggc_mx (T &)
2580 // instead of picking up the gt_ggc_mx (T *) version.
2582 gt_pch_nx (int_range
<1> *&x
)
2584 return gt_pch_nx ((irange
*) x
);
2588 gt_ggc_mx (int_range
<1> *&x
)
2590 return gt_ggc_mx ((irange
*) x
);
2593 #define DEFINE_INT_RANGE_INSTANCE(N) \
2594 template int_range<N>::int_range(tree, tree, value_range_kind); \
2595 template int_range<N>::int_range(tree_node *, \
2598 value_range_kind); \
2599 template int_range<N>::int_range(tree); \
2600 template int_range<N>::int_range(const irange &); \
2601 template int_range<N>::int_range(const int_range &); \
2602 template int_range<N>& int_range<N>::operator= (const int_range &);
2604 DEFINE_INT_RANGE_INSTANCE(1)
2605 DEFINE_INT_RANGE_INSTANCE(2)
2606 DEFINE_INT_RANGE_INSTANCE(3)
2607 DEFINE_INT_RANGE_INSTANCE(255)
2610 #include "selftest.h"
2614 #define INT(N) build_int_cst (integer_type_node, (N))
2615 #define UINT(N) build_int_cstu (unsigned_type_node, (N))
2616 #define UINT128(N) build_int_cstu (u128_type, (N))
2617 #define UCHAR(N) build_int_cstu (unsigned_char_type_node, (N))
2618 #define SCHAR(N) build_int_cst (signed_char_type_node, (N))
2621 build_range3 (int a
, int b
, int c
, int d
, int e
, int f
)
2623 int_range
<3> i1 (INT (a
), INT (b
));
2624 int_range
<3> i2 (INT (c
), INT (d
));
2625 int_range
<3> i3 (INT (e
), INT (f
));
2632 range_tests_irange3 ()
2634 typedef int_range
<3> int_range3
;
2635 int_range3 r0
, r1
, r2
;
2636 int_range3 i1
, i2
, i3
;
2638 // ([10,20] U [5,8]) U [1,3] ==> [1,3][5,8][10,20].
2639 r0
= int_range3 (INT (10), INT (20));
2640 r1
= int_range3 (INT (5), INT (8));
2642 r1
= int_range3 (INT (1), INT (3));
2644 ASSERT_TRUE (r0
== build_range3 (1, 3, 5, 8, 10, 20));
2646 // [1,3][5,8][10,20] U [-5,0] => [-5,3][5,8][10,20].
2647 r1
= int_range3 (INT (-5), INT (0));
2649 ASSERT_TRUE (r0
== build_range3 (-5, 3, 5, 8, 10, 20));
2651 // [10,20][30,40] U [50,60] ==> [10,20][30,40][50,60].
2652 r1
= int_range3 (INT (50), INT (60));
2653 r0
= int_range3 (INT (10), INT (20));
2654 r0
.union_ (int_range3 (INT (30), INT (40)));
2656 ASSERT_TRUE (r0
== build_range3 (10, 20, 30, 40, 50, 60));
2657 // [10,20][30,40][50,60] U [70, 80] ==> [10,20][30,40][50,60][70,80].
2658 r1
= int_range3 (INT (70), INT (80));
2661 r2
= build_range3 (10, 20, 30, 40, 50, 60);
2662 r2
.union_ (int_range3 (INT (70), INT (80)));
2663 ASSERT_TRUE (r0
== r2
);
2665 // [10,20][30,40][50,60] U [6,35] => [6,40][50,60].
2666 r0
= build_range3 (10, 20, 30, 40, 50, 60);
2667 r1
= int_range3 (INT (6), INT (35));
2669 r1
= int_range3 (INT (6), INT (40));
2670 r1
.union_ (int_range3 (INT (50), INT (60)));
2671 ASSERT_TRUE (r0
== r1
);
2673 // [10,20][30,40][50,60] U [6,60] => [6,60].
2674 r0
= build_range3 (10, 20, 30, 40, 50, 60);
2675 r1
= int_range3 (INT (6), INT (60));
2677 ASSERT_TRUE (r0
== int_range3 (INT (6), INT (60)));
2679 // [10,20][30,40][50,60] U [6,70] => [6,70].
2680 r0
= build_range3 (10, 20, 30, 40, 50, 60);
2681 r1
= int_range3 (INT (6), INT (70));
2683 ASSERT_TRUE (r0
== int_range3 (INT (6), INT (70)));
2685 // [10,20][30,40][50,60] U [35,70] => [10,20][30,70].
2686 r0
= build_range3 (10, 20, 30, 40, 50, 60);
2687 r1
= int_range3 (INT (35), INT (70));
2689 r1
= int_range3 (INT (10), INT (20));
2690 r1
.union_ (int_range3 (INT (30), INT (70)));
2691 ASSERT_TRUE (r0
== r1
);
2693 // [10,20][30,40][50,60] U [15,35] => [10,40][50,60].
2694 r0
= build_range3 (10, 20, 30, 40, 50, 60);
2695 r1
= int_range3 (INT (15), INT (35));
2697 r1
= int_range3 (INT (10), INT (40));
2698 r1
.union_ (int_range3 (INT (50), INT (60)));
2699 ASSERT_TRUE (r0
== r1
);
2701 // [10,20][30,40][50,60] U [35,35] => [10,20][30,40][50,60].
2702 r0
= build_range3 (10, 20, 30, 40, 50, 60);
2703 r1
= int_range3 (INT (35), INT (35));
2705 ASSERT_TRUE (r0
== build_range3 (10, 20, 30, 40, 50, 60));
2709 range_tests_int_range_max ()
2712 unsigned int nrange
;
2714 // Build a huge multi-range range.
2715 for (nrange
= 0; nrange
< 50; ++nrange
)
2717 int_range
<1> tmp (INT (nrange
*10), INT (nrange
*10 + 5));
2720 ASSERT_TRUE (big
.num_pairs () == nrange
);
2722 // Verify that we can copy it without loosing precision.
2723 int_range_max
copy (big
);
2724 ASSERT_TRUE (copy
.num_pairs () == nrange
);
2726 // Inverting it should produce one more sub-range.
2728 ASSERT_TRUE (big
.num_pairs () == nrange
+ 1);
2730 int_range
<1> tmp (INT (5), INT (37));
2731 big
.intersect (tmp
);
2732 ASSERT_TRUE (big
.num_pairs () == 4);
2734 // Test that [10,10][20,20] does NOT contain 15.
2736 int_range_max
i1 (build_int_cst (integer_type_node
, 10),
2737 build_int_cst (integer_type_node
, 10));
2738 int_range_max
i2 (build_int_cst (integer_type_node
, 20),
2739 build_int_cst (integer_type_node
, 20));
2741 ASSERT_FALSE (i1
.contains_p (build_int_cst (integer_type_node
, 15)));
2746 range_tests_legacy ()
2748 // Test truncating copy to int_range<1>.
2749 int_range
<3> big
= build_range3 (10, 20, 30, 40, 50, 60);
2750 int_range
<1> small
= big
;
2751 ASSERT_TRUE (small
== int_range
<1> (INT (10), INT (60)));
2753 // Test truncating copy to int_range<2>.
2754 int_range
<2> medium
= big
;
2755 ASSERT_TRUE (!medium
.undefined_p ());
2757 // Test that a truncating copy of [MIN,20][22,40][80,MAX]
2758 // ends up as a conservative anti-range of ~[21,21].
2759 big
= int_range
<3> (vrp_val_min (integer_type_node
), INT (20));
2760 big
.union_ (int_range
<1> (INT (22), INT (40)));
2761 big
.union_ (int_range
<1> (INT (80), vrp_val_max (integer_type_node
)));
2763 ASSERT_TRUE (small
== int_range
<1> (INT (21), INT (21), VR_ANTI_RANGE
));
2765 // Copying a legacy symbolic to an int_range should normalize the
2766 // symbolic at copy time.
2768 tree ssa
= make_ssa_name (integer_type_node
);
2769 value_range
legacy_range (ssa
, INT (25));
2770 int_range
<2> copy
= legacy_range
;
2771 ASSERT_TRUE (copy
== int_range
<2> (vrp_val_min (integer_type_node
),
2774 // Test that copying ~[abc_23, abc_23] to a multi-range yields varying.
2775 legacy_range
= value_range (ssa
, ssa
, VR_ANTI_RANGE
);
2776 copy
= legacy_range
;
2777 ASSERT_TRUE (copy
.varying_p ());
2780 // VARYING of different sizes should not be equal.
2781 tree big_type
= build_nonstandard_integer_type (32, 1);
2782 tree small_type
= build_nonstandard_integer_type (16, 1);
2783 int_range_max
r0 (big_type
);
2784 int_range_max
r1 (small_type
);
2785 ASSERT_TRUE (r0
!= r1
);
2786 value_range
vr0 (big_type
);
2787 int_range_max
vr1 (small_type
);
2788 ASSERT_TRUE (vr0
!= vr1
);
2791 // Simulate -fstrict-enums where the domain of a type is less than the
2795 range_tests_strict_enum ()
2797 // The enum can only hold [0, 3].
2798 tree rtype
= copy_node (unsigned_type_node
);
2799 TYPE_MIN_VALUE (rtype
) = build_int_cstu (rtype
, 0);
2800 TYPE_MAX_VALUE (rtype
) = build_int_cstu (rtype
, 3);
2802 // Test that even though vr1 covers the strict enum domain ([0, 3]),
2803 // it does not cover the domain of the underlying type.
2804 int_range
<1> vr1 (build_int_cstu (rtype
, 0), build_int_cstu (rtype
, 1));
2805 int_range
<1> vr2 (build_int_cstu (rtype
, 2), build_int_cstu (rtype
, 3));
2807 ASSERT_TRUE (vr1
== int_range
<1> (build_int_cstu (rtype
, 0),
2808 build_int_cstu (rtype
, 3)));
2809 ASSERT_FALSE (vr1
.varying_p ());
2811 // Test that copying to a multi-range does not change things.
2812 int_range
<2> ir1 (vr1
);
2813 ASSERT_TRUE (ir1
== vr1
);
2814 ASSERT_FALSE (ir1
.varying_p ());
2816 // The same test as above, but using TYPE_{MIN,MAX}_VALUE instead of [0,3].
2817 vr1
= int_range
<1> (TYPE_MIN_VALUE (rtype
), TYPE_MAX_VALUE (rtype
));
2819 ASSERT_TRUE (ir1
== vr1
);
2820 ASSERT_FALSE (ir1
.varying_p ());
2826 tree u128_type
= build_nonstandard_integer_type (128, /*unsigned=*/1);
2827 int_range
<1> i1
, i2
, i3
;
2828 int_range
<1> r0
, r1
, rold
;
2830 // Test 1-bit signed integer union.
2831 // [-1,-1] U [0,0] = VARYING.
2832 tree one_bit_type
= build_nonstandard_integer_type (1, 0);
2833 tree one_bit_min
= vrp_val_min (one_bit_type
);
2834 tree one_bit_max
= vrp_val_max (one_bit_type
);
2836 int_range
<2> min (one_bit_min
, one_bit_min
);
2837 int_range
<2> max (one_bit_max
, one_bit_max
);
2839 ASSERT_TRUE (max
.varying_p ());
2842 // Test inversion of 1-bit signed integers.
2844 int_range
<2> min (one_bit_min
, one_bit_min
);
2845 int_range
<2> max (one_bit_max
, one_bit_max
);
2849 ASSERT_TRUE (t
== max
);
2852 ASSERT_TRUE (t
== min
);
2855 // Test that NOT(255) is [0..254] in 8-bit land.
2856 int_range
<1> not_255 (UCHAR (255), UCHAR (255), VR_ANTI_RANGE
);
2857 ASSERT_TRUE (not_255
== int_range
<1> (UCHAR (0), UCHAR (254)));
2859 // Test that NOT(0) is [1..255] in 8-bit land.
2860 int_range
<1> not_zero
= range_nonzero (unsigned_char_type_node
);
2861 ASSERT_TRUE (not_zero
== int_range
<1> (UCHAR (1), UCHAR (255)));
2863 // Check that [0,127][0x..ffffff80,0x..ffffff]
2864 // => ~[128, 0x..ffffff7f].
2865 r0
= int_range
<1> (UINT128 (0), UINT128 (127));
2866 tree high
= build_minus_one_cst (u128_type
);
2867 // low = -1 - 127 => 0x..ffffff80.
2868 tree low
= fold_build2 (MINUS_EXPR
, u128_type
, high
, UINT128(127));
2869 r1
= int_range
<1> (low
, high
); // [0x..ffffff80, 0x..ffffffff]
2870 // r0 = [0,127][0x..ffffff80,0x..fffffff].
2872 // r1 = [128, 0x..ffffff7f].
2873 r1
= int_range
<1> (UINT128(128),
2874 fold_build2 (MINUS_EXPR
, u128_type
,
2875 build_minus_one_cst (u128_type
),
2878 ASSERT_TRUE (r0
== r1
);
2880 r0
.set_varying (integer_type_node
);
2881 tree minint
= wide_int_to_tree (integer_type_node
, r0
.lower_bound ());
2882 tree maxint
= wide_int_to_tree (integer_type_node
, r0
.upper_bound ());
2884 r0
.set_varying (short_integer_type_node
);
2886 r0
.set_varying (unsigned_type_node
);
2887 tree maxuint
= wide_int_to_tree (unsigned_type_node
, r0
.upper_bound ());
2889 // Check that ~[0,5] => [6,MAX] for unsigned int.
2890 r0
= int_range
<1> (UINT (0), UINT (5));
2892 ASSERT_TRUE (r0
== int_range
<1> (UINT(6), maxuint
));
2894 // Check that ~[10,MAX] => [0,9] for unsigned int.
2895 r0
= int_range
<1> (UINT(10), maxuint
);
2897 ASSERT_TRUE (r0
== int_range
<1> (UINT (0), UINT (9)));
2899 // Check that ~[0,5] => [6,MAX] for unsigned 128-bit numbers.
2900 r0
= int_range
<1> (UINT128 (0), UINT128 (5), VR_ANTI_RANGE
);
2901 r1
= int_range
<1> (UINT128(6), build_minus_one_cst (u128_type
));
2902 ASSERT_TRUE (r0
== r1
);
2904 // Check that [~5] is really [-MIN,4][6,MAX].
2905 r0
= int_range
<1> (INT (5), INT (5), VR_ANTI_RANGE
);
2906 r1
= int_range
<1> (minint
, INT (4));
2907 r1
.union_ (int_range
<1> (INT (6), maxint
));
2908 ASSERT_FALSE (r1
.undefined_p ());
2909 ASSERT_TRUE (r0
== r1
);
2911 r1
= int_range
<1> (INT (5), INT (5));
2912 int_range
<1> r2 (r1
);
2913 ASSERT_TRUE (r1
== r2
);
2915 r1
= int_range
<1> (INT (5), INT (10));
2917 r1
= int_range
<1> (integer_type_node
,
2918 wi::to_wide (INT (5)), wi::to_wide (INT (10)));
2919 ASSERT_TRUE (r1
.contains_p (INT (7)));
2921 r1
= int_range
<1> (SCHAR (0), SCHAR (20));
2922 ASSERT_TRUE (r1
.contains_p (SCHAR(15)));
2923 ASSERT_FALSE (r1
.contains_p (SCHAR(300)));
2925 // NOT([10,20]) ==> [-MIN,9][21,MAX].
2926 r0
= r1
= int_range
<1> (INT (10), INT (20));
2927 r2
= int_range
<1> (minint
, INT(9));
2928 r2
.union_ (int_range
<1> (INT(21), maxint
));
2929 ASSERT_FALSE (r2
.undefined_p ());
2931 ASSERT_TRUE (r1
== r2
);
2932 // Test that NOT(NOT(x)) == x.
2934 ASSERT_TRUE (r0
== r2
);
2936 // Test that booleans and their inverse work as expected.
2937 r0
= range_zero (boolean_type_node
);
2938 ASSERT_TRUE (r0
== int_range
<1> (build_zero_cst (boolean_type_node
),
2939 build_zero_cst (boolean_type_node
)));
2941 ASSERT_TRUE (r0
== int_range
<1> (build_one_cst (boolean_type_node
),
2942 build_one_cst (boolean_type_node
)));
2944 // Make sure NULL and non-NULL of pointer types work, and that
2945 // inverses of them are consistent.
2946 tree voidp
= build_pointer_type (void_type_node
);
2947 r0
= range_zero (voidp
);
2951 ASSERT_TRUE (r0
== r1
);
2953 // [10,20] U [15, 30] => [10, 30].
2954 r0
= int_range
<1> (INT (10), INT (20));
2955 r1
= int_range
<1> (INT (15), INT (30));
2957 ASSERT_TRUE (r0
== int_range
<1> (INT (10), INT (30)));
2959 // [15,40] U [] => [15,40].
2960 r0
= int_range
<1> (INT (15), INT (40));
2961 r1
.set_undefined ();
2963 ASSERT_TRUE (r0
== int_range
<1> (INT (15), INT (40)));
2965 // [10,20] U [10,10] => [10,20].
2966 r0
= int_range
<1> (INT (10), INT (20));
2967 r1
= int_range
<1> (INT (10), INT (10));
2969 ASSERT_TRUE (r0
== int_range
<1> (INT (10), INT (20)));
2971 // [10,20] U [9,9] => [9,20].
2972 r0
= int_range
<1> (INT (10), INT (20));
2973 r1
= int_range
<1> (INT (9), INT (9));
2975 ASSERT_TRUE (r0
== int_range
<1> (INT (9), INT (20)));
2977 // [10,20] ^ [15,30] => [15,20].
2978 r0
= int_range
<1> (INT (10), INT (20));
2979 r1
= int_range
<1> (INT (15), INT (30));
2981 ASSERT_TRUE (r0
== int_range
<1> (INT (15), INT (20)));
2983 // Test the internal sanity of wide_int's wrt HWIs.
2984 ASSERT_TRUE (wi::max_value (TYPE_PRECISION (boolean_type_node
),
2985 TYPE_SIGN (boolean_type_node
))
2986 == wi::uhwi (1, TYPE_PRECISION (boolean_type_node
)));
2989 r0
= int_range
<1> (INT (0), INT (0));
2990 ASSERT_TRUE (r0
.zero_p ());
2992 // Test nonzero_p().
2993 r0
= int_range
<1> (INT (0), INT (0));
2995 ASSERT_TRUE (r0
.nonzero_p ());
2997 // test legacy interaction
2999 r0
= int_range
<1> (UINT (1), UINT (1), VR_ANTI_RANGE
);
3001 r1
= int_range
<1> (UINT (3), UINT (3), VR_ANTI_RANGE
);
3003 // vv = [0,0][2,2][4, MAX]
3004 int_range
<3> vv
= r0
;
3007 ASSERT_TRUE (vv
.contains_p (UINT (2)));
3008 ASSERT_TRUE (vv
.num_pairs () == 3);
3010 // create r0 as legacy [1,1]
3011 r0
= int_range
<1> (UINT (1), UINT (1));
3012 // And union it with [0,0][2,2][4,MAX] multi range
3014 // The result should be [0,2][4,MAX], or ~[3,3] but it must contain 2
3015 ASSERT_TRUE (r0
.contains_p (UINT (2)));
3019 range_tests_nonzero_bits ()
3021 int_range
<2> r0
, r1
;
3023 // Adding nonzero bits to a varying drops the varying.
3024 r0
.set_varying (integer_type_node
);
3025 r0
.set_nonzero_bits (255);
3026 ASSERT_TRUE (!r0
.varying_p ());
3027 // Dropping the nonzero bits brings us back to varying.
3028 r0
.set_nonzero_bits (-1);
3029 ASSERT_TRUE (r0
.varying_p ());
3031 // Test contains_p with nonzero bits.
3032 r0
.set_zero (integer_type_node
);
3033 ASSERT_TRUE (r0
.contains_p (INT (0)));
3034 ASSERT_FALSE (r0
.contains_p (INT (1)));
3035 r0
.set_nonzero_bits (0xfe);
3036 ASSERT_FALSE (r0
.contains_p (INT (0x100)));
3037 ASSERT_FALSE (r0
.contains_p (INT (0x3)));
3039 // Union of nonzero bits.
3040 r0
.set_varying (integer_type_node
);
3041 r0
.set_nonzero_bits (0xf0);
3042 r1
.set_varying (integer_type_node
);
3043 r1
.set_nonzero_bits (0xf);
3045 ASSERT_TRUE (r0
.get_nonzero_bits () == 0xff);
3047 // Union where the mask of nonzero bits is implicit from the range.
3048 r0
.set_varying (integer_type_node
);
3049 r0
.set_nonzero_bits (0xf00);
3050 r1
.set_zero (integer_type_node
); // nonzero mask is implicitly 0
3052 ASSERT_TRUE (r0
.get_nonzero_bits () == 0xf00);
3054 // Intersect of nonzero bits.
3055 r0
.set (INT (0), INT (255));
3056 r0
.set_nonzero_bits (0xfe);
3057 r1
.set_varying (integer_type_node
);
3058 r1
.set_nonzero_bits (0xf0);
3060 ASSERT_TRUE (r0
.get_nonzero_bits () == 0xf0);
3062 // Intersect where the mask of nonzero bits is implicit from the range.
3063 r0
.set_varying (integer_type_node
);
3064 r1
.set (INT (0), INT (255));
3066 ASSERT_TRUE (r0
.get_nonzero_bits () == 0xff);
3068 // The union of a mask of 0xff..ffff00 with a mask of 0xff spans the
3069 // entire domain, and makes the range a varying.
3070 r0
.set_varying (integer_type_node
);
3071 wide_int x
= wi::shwi (0xff, TYPE_PRECISION (integer_type_node
));
3072 x
= wi::bit_not (x
);
3073 r0
.set_nonzero_bits (x
); // 0xff..ff00
3074 r1
.set_varying (integer_type_node
);
3075 r1
.set_nonzero_bits (0xff);
3077 ASSERT_TRUE (r0
.varying_p ());
3083 range_tests_legacy ();
3084 range_tests_irange3 ();
3085 range_tests_int_range_max ();
3086 range_tests_strict_enum ();
3087 range_tests_nonzero_bits ();
3088 range_tests_misc ();
3091 } // namespace selftest
3093 #endif // CHECKING_P
This page took 0.17862 seconds and 6 git commands to generate.