1 /* Code for range operators.
2 Copyright (C) 2017-2022 Free Software Foundation, Inc.
3 Contributed by Andrew MacLeod <amacleod@redhat.com>
4 and Aldy Hernandez <aldyh@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"
26 #include "insn-codes.h"
31 #include "tree-pass.h"
33 #include "optabs-tree.h"
34 #include "gimple-pretty-print.h"
35 #include "diagnostic-core.h"
37 #include "fold-const.h"
38 #include "stor-layout.h"
41 #include "gimple-iterator.h"
42 #include "gimple-fold.h"
44 #include "gimple-walk.h"
47 #include "value-relation.h"
50 // Return the upper limit for a type.
52 static inline wide_int
53 max_limit (const_tree type
)
55 return wi::max_value (TYPE_PRECISION (type
) , TYPE_SIGN (type
));
58 // Return the lower limit for a type.
60 static inline wide_int
61 min_limit (const_tree type
)
63 return wi::min_value (TYPE_PRECISION (type
) , TYPE_SIGN (type
));
66 // Return false if shifting by OP is undefined behavior. Otherwise, return
67 // true and the range it is to be shifted by. This allows trimming out of
68 // undefined ranges, leaving only valid ranges if there are any.
71 get_shift_range (irange
&r
, tree type
, const irange
&op
)
73 if (op
.undefined_p ())
76 // Build valid range and intersect it with the shift range.
77 r
= value_range (build_int_cst_type (op
.type (), 0),
78 build_int_cst_type (op
.type (), TYPE_PRECISION (type
) - 1));
81 // If there are no valid ranges in the shift range, returned false.
87 // Return TRUE if 0 is within [WMIN, WMAX].
90 wi_includes_zero_p (tree type
, const wide_int
&wmin
, const wide_int
&wmax
)
92 signop sign
= TYPE_SIGN (type
);
93 return wi::le_p (wmin
, 0, sign
) && wi::ge_p (wmax
, 0, sign
);
96 // Return TRUE if [WMIN, WMAX] is the singleton 0.
99 wi_zero_p (tree type
, const wide_int
&wmin
, const wide_int
&wmax
)
101 unsigned prec
= TYPE_PRECISION (type
);
102 return wmin
== wmax
&& wi::eq_p (wmin
, wi::zero (prec
));
105 // Default wide_int fold operation returns [MIN, MAX].
108 range_operator::wi_fold (irange
&r
, tree type
,
109 const wide_int
&lh_lb ATTRIBUTE_UNUSED
,
110 const wide_int
&lh_ub ATTRIBUTE_UNUSED
,
111 const wide_int
&rh_lb ATTRIBUTE_UNUSED
,
112 const wide_int
&rh_ub ATTRIBUTE_UNUSED
) const
114 gcc_checking_assert (r
.supports_type_p (type
));
115 r
.set_varying (type
);
118 // Call wi_fold, except further split small subranges into constants.
119 // This can provide better precision. For something 8 >> [0,1]
120 // Instead of [8, 16], we will produce [8,8][16,16]
123 range_operator::wi_fold_in_parts (irange
&r
, tree type
,
124 const wide_int
&lh_lb
,
125 const wide_int
&lh_ub
,
126 const wide_int
&rh_lb
,
127 const wide_int
&rh_ub
) const
130 widest_int rh_range
= wi::sub (widest_int::from (rh_ub
, TYPE_SIGN (type
)),
131 widest_int::from (rh_lb
, TYPE_SIGN (type
)));
132 widest_int lh_range
= wi::sub (widest_int::from (lh_ub
, TYPE_SIGN (type
)),
133 widest_int::from (lh_lb
, TYPE_SIGN (type
)));
134 // If there are 2, 3, or 4 values in the RH range, do them separately.
135 // Call wi_fold_in_parts to check the RH side.
136 if (rh_range
> 0 && rh_range
< 4)
138 wi_fold_in_parts (r
, type
, lh_lb
, lh_ub
, rh_lb
, rh_lb
);
141 wi_fold_in_parts (tmp
, type
, lh_lb
, lh_ub
, rh_lb
+ 1, rh_lb
+ 1);
145 wi_fold_in_parts (tmp
, type
, lh_lb
, lh_ub
, rh_lb
+ 2, rh_lb
+ 2);
149 wi_fold_in_parts (tmp
, type
, lh_lb
, lh_ub
, rh_ub
, rh_ub
);
152 // Otherise check for 2, 3, or 4 values in the LH range and split them up.
153 // The RH side has been checked, so no recursion needed.
154 else if (lh_range
> 0 && lh_range
< 4)
156 wi_fold (r
, type
, lh_lb
, lh_lb
, rh_lb
, rh_ub
);
159 wi_fold (tmp
, type
, lh_lb
+ 1, lh_lb
+ 1, rh_lb
, rh_ub
);
163 wi_fold (tmp
, type
, lh_lb
+ 2, lh_lb
+ 2, rh_lb
, rh_ub
);
167 wi_fold (tmp
, type
, lh_ub
, lh_ub
, rh_lb
, rh_ub
);
170 // Otherwise just call wi_fold.
172 wi_fold (r
, type
, lh_lb
, lh_ub
, rh_lb
, rh_ub
);
175 // The default for fold is to break all ranges into sub-ranges and
176 // invoke the wi_fold method on each sub-range pair.
179 range_operator::fold_range (irange
&r
, tree type
,
182 relation_trio trio
) const
184 gcc_checking_assert (r
.supports_type_p (type
));
185 if (empty_range_varying (r
, type
, lh
, rh
))
188 relation_kind rel
= trio
.op1_op2 ();
189 unsigned num_lh
= lh
.num_pairs ();
190 unsigned num_rh
= rh
.num_pairs ();
192 // If both ranges are single pairs, fold directly into the result range.
193 // If the number of subranges grows too high, produce a summary result as the
194 // loop becomes exponential with little benefit. See PR 103821.
195 if ((num_lh
== 1 && num_rh
== 1) || num_lh
* num_rh
> 12)
197 wi_fold_in_parts (r
, type
, lh
.lower_bound (), lh
.upper_bound (),
198 rh
.lower_bound (), rh
.upper_bound ());
199 op1_op2_relation_effect (r
, type
, lh
, rh
, rel
);
205 for (unsigned x
= 0; x
< num_lh
; ++x
)
206 for (unsigned y
= 0; y
< num_rh
; ++y
)
208 wide_int lh_lb
= lh
.lower_bound (x
);
209 wide_int lh_ub
= lh
.upper_bound (x
);
210 wide_int rh_lb
= rh
.lower_bound (y
);
211 wide_int rh_ub
= rh
.upper_bound (y
);
212 wi_fold_in_parts (tmp
, type
, lh_lb
, lh_ub
, rh_lb
, rh_ub
);
216 op1_op2_relation_effect (r
, type
, lh
, rh
, rel
);
220 op1_op2_relation_effect (r
, type
, lh
, rh
, rel
);
224 // The default for op1_range is to return false.
227 range_operator::op1_range (irange
&r ATTRIBUTE_UNUSED
,
228 tree type ATTRIBUTE_UNUSED
,
229 const irange
&lhs ATTRIBUTE_UNUSED
,
230 const irange
&op2 ATTRIBUTE_UNUSED
,
236 // The default for op2_range is to return false.
239 range_operator::op2_range (irange
&r ATTRIBUTE_UNUSED
,
240 tree type ATTRIBUTE_UNUSED
,
241 const irange
&lhs ATTRIBUTE_UNUSED
,
242 const irange
&op1 ATTRIBUTE_UNUSED
,
248 // The default relation routines return VREL_VARYING.
251 range_operator::lhs_op1_relation (const irange
&lhs ATTRIBUTE_UNUSED
,
252 const irange
&op1 ATTRIBUTE_UNUSED
,
253 const irange
&op2 ATTRIBUTE_UNUSED
,
254 relation_kind rel ATTRIBUTE_UNUSED
) const
260 range_operator::lhs_op2_relation (const irange
&lhs ATTRIBUTE_UNUSED
,
261 const irange
&op1 ATTRIBUTE_UNUSED
,
262 const irange
&op2 ATTRIBUTE_UNUSED
,
263 relation_kind rel ATTRIBUTE_UNUSED
) const
269 range_operator::op1_op2_relation (const irange
&lhs ATTRIBUTE_UNUSED
) const
274 // Default is no relation affects the LHS.
277 range_operator::op1_op2_relation_effect (irange
&lhs_range ATTRIBUTE_UNUSED
,
278 tree type ATTRIBUTE_UNUSED
,
279 const irange
&op1_range ATTRIBUTE_UNUSED
,
280 const irange
&op2_range ATTRIBUTE_UNUSED
,
281 relation_kind rel ATTRIBUTE_UNUSED
) const
286 // Create and return a range from a pair of wide-ints that are known
287 // to have overflowed (or underflowed).
290 value_range_from_overflowed_bounds (irange
&r
, tree type
,
291 const wide_int
&wmin
,
292 const wide_int
&wmax
)
294 const signop sgn
= TYPE_SIGN (type
);
295 const unsigned int prec
= TYPE_PRECISION (type
);
297 wide_int tmin
= wide_int::from (wmin
, prec
, sgn
);
298 wide_int tmax
= wide_int::from (wmax
, prec
, sgn
);
303 if (wi::cmp (tmin
, tmax
, sgn
) < 0)
306 if (wi::cmp (tmax
, tem
, sgn
) > 0)
309 // If the anti-range would cover nothing, drop to varying.
310 // Likewise if the anti-range bounds are outside of the types
312 if (covers
|| wi::cmp (tmin
, tmax
, sgn
) > 0)
313 r
.set_varying (type
);
316 tree tree_min
= wide_int_to_tree (type
, tmin
);
317 tree tree_max
= wide_int_to_tree (type
, tmax
);
318 r
.set (tree_min
, tree_max
, VR_ANTI_RANGE
);
322 // Create and return a range from a pair of wide-ints. MIN_OVF and
323 // MAX_OVF describe any overflow that might have occurred while
324 // calculating WMIN and WMAX respectively.
327 value_range_with_overflow (irange
&r
, tree type
,
328 const wide_int
&wmin
, const wide_int
&wmax
,
329 wi::overflow_type min_ovf
= wi::OVF_NONE
,
330 wi::overflow_type max_ovf
= wi::OVF_NONE
)
332 const signop sgn
= TYPE_SIGN (type
);
333 const unsigned int prec
= TYPE_PRECISION (type
);
334 const bool overflow_wraps
= TYPE_OVERFLOW_WRAPS (type
);
336 // For one bit precision if max != min, then the range covers all
338 if (prec
== 1 && wi::ne_p (wmax
, wmin
))
340 r
.set_varying (type
);
346 // If overflow wraps, truncate the values and adjust the range,
347 // kind, and bounds appropriately.
348 if ((min_ovf
!= wi::OVF_NONE
) == (max_ovf
!= wi::OVF_NONE
))
350 wide_int tmin
= wide_int::from (wmin
, prec
, sgn
);
351 wide_int tmax
= wide_int::from (wmax
, prec
, sgn
);
352 // If the limits are swapped, we wrapped around and cover
354 if (wi::gt_p (tmin
, tmax
, sgn
))
355 r
.set_varying (type
);
357 // No overflow or both overflow or underflow. The range
358 // kind stays normal.
359 r
.set (wide_int_to_tree (type
, tmin
),
360 wide_int_to_tree (type
, tmax
));
364 if ((min_ovf
== wi::OVF_UNDERFLOW
&& max_ovf
== wi::OVF_NONE
)
365 || (max_ovf
== wi::OVF_OVERFLOW
&& min_ovf
== wi::OVF_NONE
))
366 value_range_from_overflowed_bounds (r
, type
, wmin
, wmax
);
368 // Other underflow and/or overflow, drop to VR_VARYING.
369 r
.set_varying (type
);
373 // If both bounds either underflowed or overflowed, then the result
375 if ((min_ovf
== wi::OVF_OVERFLOW
&& max_ovf
== wi::OVF_OVERFLOW
)
376 || (min_ovf
== wi::OVF_UNDERFLOW
&& max_ovf
== wi::OVF_UNDERFLOW
))
382 // If overflow does not wrap, saturate to [MIN, MAX].
383 wide_int new_lb
, new_ub
;
384 if (min_ovf
== wi::OVF_UNDERFLOW
)
385 new_lb
= wi::min_value (prec
, sgn
);
386 else if (min_ovf
== wi::OVF_OVERFLOW
)
387 new_lb
= wi::max_value (prec
, sgn
);
391 if (max_ovf
== wi::OVF_UNDERFLOW
)
392 new_ub
= wi::min_value (prec
, sgn
);
393 else if (max_ovf
== wi::OVF_OVERFLOW
)
394 new_ub
= wi::max_value (prec
, sgn
);
398 r
.set (wide_int_to_tree (type
, new_lb
),
399 wide_int_to_tree (type
, new_ub
));
403 // Create and return a range from a pair of wide-ints. Canonicalize
404 // the case where the bounds are swapped. In which case, we transform
405 // [10,5] into [MIN,5][10,MAX].
408 create_possibly_reversed_range (irange
&r
, tree type
,
409 const wide_int
&new_lb
, const wide_int
&new_ub
)
411 signop s
= TYPE_SIGN (type
);
412 // If the bounds are swapped, treat the result as if an overflow occured.
413 if (wi::gt_p (new_lb
, new_ub
, s
))
414 value_range_from_overflowed_bounds (r
, type
, new_lb
, new_ub
);
416 // Otherwise it's just a normal range.
417 r
.set (wide_int_to_tree (type
, new_lb
), wide_int_to_tree (type
, new_ub
));
420 // Return the summary information about boolean range LHS. If EMPTY/FULL,
421 // return the equivalent range for TYPE in R; if FALSE/TRUE, do nothing.
424 get_bool_state (vrange
&r
, const vrange
&lhs
, tree val_type
)
426 // If there is no result, then this is unexecutable.
427 if (lhs
.undefined_p ())
436 // For TRUE, we can't just test for [1,1] because Ada can have
437 // multi-bit booleans, and TRUE values can be: [1, MAX], ~[0], etc.
438 if (lhs
.contains_p (build_zero_cst (lhs
.type ())))
440 r
.set_varying (val_type
);
448 class operator_equal
: public range_operator
450 using range_operator::fold_range
;
451 using range_operator::op1_range
;
452 using range_operator::op2_range
;
454 virtual bool fold_range (irange
&r
, tree type
,
457 relation_trio
= TRIO_VARYING
) const;
458 virtual bool op1_range (irange
&r
, tree type
,
461 relation_trio
= TRIO_VARYING
) const;
462 virtual bool op2_range (irange
&r
, tree type
,
465 relation_trio
= TRIO_VARYING
) const;
466 virtual relation_kind
op1_op2_relation (const irange
&lhs
) const;
469 // Check if the LHS range indicates a relation between OP1 and OP2.
472 equal_op1_op2_relation (const irange
&lhs
)
474 if (lhs
.undefined_p ())
475 return VREL_UNDEFINED
;
477 // FALSE = op1 == op2 indicates NE_EXPR.
481 // TRUE = op1 == op2 indicates EQ_EXPR.
482 if (!lhs
.contains_p (build_zero_cst (lhs
.type ())))
488 operator_equal::op1_op2_relation (const irange
&lhs
) const
490 return equal_op1_op2_relation (lhs
);
495 operator_equal::fold_range (irange
&r
, tree type
,
498 relation_trio rel
) const
500 if (relop_early_resolve (r
, type
, op1
, op2
, rel
, VREL_EQ
))
503 // We can be sure the values are always equal or not if both ranges
504 // consist of a single value, and then compare them.
505 if (wi::eq_p (op1
.lower_bound (), op1
.upper_bound ())
506 && wi::eq_p (op2
.lower_bound (), op2
.upper_bound ()))
508 if (wi::eq_p (op1
.lower_bound (), op2
.upper_bound()))
509 r
= range_true (type
);
511 r
= range_false (type
);
515 // If ranges do not intersect, we know the range is not equal,
516 // otherwise we don't know anything for sure.
517 int_range_max tmp
= op1
;
519 if (tmp
.undefined_p ())
520 r
= range_false (type
);
522 r
= range_true_and_false (type
);
528 operator_equal::op1_range (irange
&r
, tree type
,
533 switch (get_bool_state (r
, lhs
, type
))
536 // If it's true, the result is the same as OP2.
541 // If the result is false, the only time we know anything is
542 // if OP2 is a constant.
543 if (wi::eq_p (op2
.lower_bound(), op2
.upper_bound()))
549 r
.set_varying (type
);
559 operator_equal::op2_range (irange
&r
, tree type
,
562 relation_trio rel
) const
564 return operator_equal::op1_range (r
, type
, lhs
, op1
, rel
.swap_op1_op2 ());
567 class operator_not_equal
: public range_operator
569 using range_operator::fold_range
;
570 using range_operator::op1_range
;
571 using range_operator::op2_range
;
573 virtual bool fold_range (irange
&r
, tree type
,
576 relation_trio
= TRIO_VARYING
) const;
577 virtual bool op1_range (irange
&r
, tree type
,
580 relation_trio
= TRIO_VARYING
) const;
581 virtual bool op2_range (irange
&r
, tree type
,
584 relation_trio
= TRIO_VARYING
) const;
585 virtual relation_kind
op1_op2_relation (const irange
&lhs
) const;
588 // Check if the LHS range indicates a relation between OP1 and OP2.
591 not_equal_op1_op2_relation (const irange
&lhs
)
593 if (lhs
.undefined_p ())
594 return VREL_UNDEFINED
;
596 // FALSE = op1 != op2 indicates EQ_EXPR.
600 // TRUE = op1 != op2 indicates NE_EXPR.
601 if (!lhs
.contains_p (build_zero_cst (lhs
.type ())))
607 operator_not_equal::op1_op2_relation (const irange
&lhs
) const
609 return not_equal_op1_op2_relation (lhs
);
613 operator_not_equal::fold_range (irange
&r
, tree type
,
616 relation_trio rel
) const
618 if (relop_early_resolve (r
, type
, op1
, op2
, rel
, VREL_NE
))
621 // We can be sure the values are always equal or not if both ranges
622 // consist of a single value, and then compare them.
623 if (wi::eq_p (op1
.lower_bound (), op1
.upper_bound ())
624 && wi::eq_p (op2
.lower_bound (), op2
.upper_bound ()))
626 if (wi::ne_p (op1
.lower_bound (), op2
.upper_bound()))
627 r
= range_true (type
);
629 r
= range_false (type
);
633 // If ranges do not intersect, we know the range is not equal,
634 // otherwise we don't know anything for sure.
635 int_range_max tmp
= op1
;
637 if (tmp
.undefined_p ())
638 r
= range_true (type
);
640 r
= range_true_and_false (type
);
646 operator_not_equal::op1_range (irange
&r
, tree type
,
651 switch (get_bool_state (r
, lhs
, type
))
654 // If the result is true, the only time we know anything is if
655 // OP2 is a constant.
656 if (wi::eq_p (op2
.lower_bound(), op2
.upper_bound()))
662 r
.set_varying (type
);
666 // If it's false, the result is the same as OP2.
678 operator_not_equal::op2_range (irange
&r
, tree type
,
681 relation_trio rel
) const
683 return operator_not_equal::op1_range (r
, type
, lhs
, op1
, rel
.swap_op1_op2 ());
686 // (X < VAL) produces the range of [MIN, VAL - 1].
689 build_lt (irange
&r
, tree type
, const wide_int
&val
)
691 wi::overflow_type ov
;
693 signop sgn
= TYPE_SIGN (type
);
695 // Signed 1 bit cannot represent 1 for subtraction.
697 lim
= wi::add (val
, -1, sgn
, &ov
);
699 lim
= wi::sub (val
, 1, sgn
, &ov
);
701 // If val - 1 underflows, check if X < MIN, which is an empty range.
705 r
= int_range
<1> (type
, min_limit (type
), lim
);
708 // (X <= VAL) produces the range of [MIN, VAL].
711 build_le (irange
&r
, tree type
, const wide_int
&val
)
713 r
= int_range
<1> (type
, min_limit (type
), val
);
716 // (X > VAL) produces the range of [VAL + 1, MAX].
719 build_gt (irange
&r
, tree type
, const wide_int
&val
)
721 wi::overflow_type ov
;
723 signop sgn
= TYPE_SIGN (type
);
725 // Signed 1 bit cannot represent 1 for addition.
727 lim
= wi::sub (val
, -1, sgn
, &ov
);
729 lim
= wi::add (val
, 1, sgn
, &ov
);
730 // If val + 1 overflows, check is for X > MAX, which is an empty range.
734 r
= int_range
<1> (type
, lim
, max_limit (type
));
737 // (X >= val) produces the range of [VAL, MAX].
740 build_ge (irange
&r
, tree type
, const wide_int
&val
)
742 r
= int_range
<1> (type
, val
, max_limit (type
));
746 class operator_lt
: public range_operator
748 using range_operator::fold_range
;
749 using range_operator::op1_range
;
750 using range_operator::op2_range
;
752 virtual bool fold_range (irange
&r
, tree type
,
755 relation_trio
= TRIO_VARYING
) const;
756 virtual bool op1_range (irange
&r
, tree type
,
759 relation_trio
= TRIO_VARYING
) const;
760 virtual bool op2_range (irange
&r
, tree type
,
763 relation_trio
= TRIO_VARYING
) const;
764 virtual relation_kind
op1_op2_relation (const irange
&lhs
) const;
767 // Check if the LHS range indicates a relation between OP1 and OP2.
770 lt_op1_op2_relation (const irange
&lhs
)
772 if (lhs
.undefined_p ())
773 return VREL_UNDEFINED
;
775 // FALSE = op1 < op2 indicates GE_EXPR.
779 // TRUE = op1 < op2 indicates LT_EXPR.
780 if (!lhs
.contains_p (build_zero_cst (lhs
.type ())))
786 operator_lt::op1_op2_relation (const irange
&lhs
) const
788 return lt_op1_op2_relation (lhs
);
792 operator_lt::fold_range (irange
&r
, tree type
,
795 relation_trio rel
) const
797 if (relop_early_resolve (r
, type
, op1
, op2
, rel
, VREL_LT
))
800 signop sign
= TYPE_SIGN (op1
.type ());
801 gcc_checking_assert (sign
== TYPE_SIGN (op2
.type ()));
803 if (wi::lt_p (op1
.upper_bound (), op2
.lower_bound (), sign
))
804 r
= range_true (type
);
805 else if (!wi::lt_p (op1
.lower_bound (), op2
.upper_bound (), sign
))
806 r
= range_false (type
);
807 // Use nonzero bits to determine if < 0 is false.
808 else if (op2
.zero_p () && !wi::neg_p (op1
.get_nonzero_bits (), sign
))
809 r
= range_false (type
);
811 r
= range_true_and_false (type
);
816 operator_lt::op1_range (irange
&r
, tree type
,
821 switch (get_bool_state (r
, lhs
, type
))
824 build_lt (r
, type
, op2
.upper_bound ());
828 build_ge (r
, type
, op2
.lower_bound ());
838 operator_lt::op2_range (irange
&r
, tree type
,
843 switch (get_bool_state (r
, lhs
, type
))
846 build_gt (r
, type
, op1
.lower_bound ());
850 build_le (r
, type
, op1
.upper_bound ());
860 class operator_le
: public range_operator
862 using range_operator::fold_range
;
863 using range_operator::op1_range
;
864 using range_operator::op2_range
;
866 virtual bool fold_range (irange
&r
, tree type
,
869 relation_trio
= TRIO_VARYING
) const;
870 virtual bool op1_range (irange
&r
, tree type
,
873 relation_trio
= TRIO_VARYING
) const;
874 virtual bool op2_range (irange
&r
, tree type
,
877 relation_trio
= TRIO_VARYING
) const;
878 virtual relation_kind
op1_op2_relation (const irange
&lhs
) const;
881 // Check if the LHS range indicates a relation between OP1 and OP2.
884 le_op1_op2_relation (const irange
&lhs
)
886 if (lhs
.undefined_p ())
887 return VREL_UNDEFINED
;
889 // FALSE = op1 <= op2 indicates GT_EXPR.
893 // TRUE = op1 <= op2 indicates LE_EXPR.
894 if (!lhs
.contains_p (build_zero_cst (lhs
.type ())))
900 operator_le::op1_op2_relation (const irange
&lhs
) const
902 return le_op1_op2_relation (lhs
);
906 operator_le::fold_range (irange
&r
, tree type
,
909 relation_trio rel
) const
911 if (relop_early_resolve (r
, type
, op1
, op2
, rel
, VREL_LE
))
914 signop sign
= TYPE_SIGN (op1
.type ());
915 gcc_checking_assert (sign
== TYPE_SIGN (op2
.type ()));
917 if (wi::le_p (op1
.upper_bound (), op2
.lower_bound (), sign
))
918 r
= range_true (type
);
919 else if (!wi::le_p (op1
.lower_bound (), op2
.upper_bound (), sign
))
920 r
= range_false (type
);
922 r
= range_true_and_false (type
);
927 operator_le::op1_range (irange
&r
, tree type
,
932 switch (get_bool_state (r
, lhs
, type
))
935 build_le (r
, type
, op2
.upper_bound ());
939 build_gt (r
, type
, op2
.lower_bound ());
949 operator_le::op2_range (irange
&r
, tree type
,
954 switch (get_bool_state (r
, lhs
, type
))
957 build_ge (r
, type
, op1
.lower_bound ());
961 build_lt (r
, type
, op1
.upper_bound ());
971 class operator_gt
: public range_operator
973 using range_operator::fold_range
;
974 using range_operator::op1_range
;
975 using range_operator::op2_range
;
977 virtual bool fold_range (irange
&r
, tree type
,
980 relation_trio
= TRIO_VARYING
) const;
981 virtual bool op1_range (irange
&r
, tree type
,
984 relation_trio
= TRIO_VARYING
) const;
985 virtual bool op2_range (irange
&r
, tree type
,
988 relation_trio
= TRIO_VARYING
) const;
989 virtual relation_kind
op1_op2_relation (const irange
&lhs
) const;
992 // Check if the LHS range indicates a relation between OP1 and OP2.
995 gt_op1_op2_relation (const irange
&lhs
)
997 if (lhs
.undefined_p ())
998 return VREL_UNDEFINED
;
1000 // FALSE = op1 > op2 indicates LE_EXPR.
1004 // TRUE = op1 > op2 indicates GT_EXPR.
1005 if (!lhs
.contains_p (build_zero_cst (lhs
.type ())))
1007 return VREL_VARYING
;
1011 operator_gt::op1_op2_relation (const irange
&lhs
) const
1013 return gt_op1_op2_relation (lhs
);
1018 operator_gt::fold_range (irange
&r
, tree type
,
1019 const irange
&op1
, const irange
&op2
,
1020 relation_trio rel
) const
1022 if (relop_early_resolve (r
, type
, op1
, op2
, rel
, VREL_GT
))
1025 signop sign
= TYPE_SIGN (op1
.type ());
1026 gcc_checking_assert (sign
== TYPE_SIGN (op2
.type ()));
1028 if (wi::gt_p (op1
.lower_bound (), op2
.upper_bound (), sign
))
1029 r
= range_true (type
);
1030 else if (!wi::gt_p (op1
.upper_bound (), op2
.lower_bound (), sign
))
1031 r
= range_false (type
);
1033 r
= range_true_and_false (type
);
1038 operator_gt::op1_range (irange
&r
, tree type
,
1039 const irange
&lhs
, const irange
&op2
,
1040 relation_trio
) const
1042 switch (get_bool_state (r
, lhs
, type
))
1045 build_gt (r
, type
, op2
.lower_bound ());
1049 build_le (r
, type
, op2
.upper_bound ());
1059 operator_gt::op2_range (irange
&r
, tree type
,
1062 relation_trio
) const
1064 switch (get_bool_state (r
, lhs
, type
))
1067 build_lt (r
, type
, op1
.upper_bound ());
1071 build_ge (r
, type
, op1
.lower_bound ());
1081 class operator_ge
: public range_operator
1083 using range_operator::fold_range
;
1084 using range_operator::op1_range
;
1085 using range_operator::op2_range
;
1087 virtual bool fold_range (irange
&r
, tree type
,
1090 relation_trio
= TRIO_VARYING
) const;
1091 virtual bool op1_range (irange
&r
, tree type
,
1094 relation_trio
= TRIO_VARYING
) const;
1095 virtual bool op2_range (irange
&r
, tree type
,
1098 relation_trio
= TRIO_VARYING
) const;
1099 virtual relation_kind
op1_op2_relation (const irange
&lhs
) const;
1102 // Check if the LHS range indicates a relation between OP1 and OP2.
1105 ge_op1_op2_relation (const irange
&lhs
)
1107 if (lhs
.undefined_p ())
1108 return VREL_UNDEFINED
;
1110 // FALSE = op1 >= op2 indicates LT_EXPR.
1114 // TRUE = op1 >= op2 indicates GE_EXPR.
1115 if (!lhs
.contains_p (build_zero_cst (lhs
.type ())))
1117 return VREL_VARYING
;
1121 operator_ge::op1_op2_relation (const irange
&lhs
) const
1123 return ge_op1_op2_relation (lhs
);
1127 operator_ge::fold_range (irange
&r
, tree type
,
1130 relation_trio rel
) const
1132 if (relop_early_resolve (r
, type
, op1
, op2
, rel
, VREL_GE
))
1135 signop sign
= TYPE_SIGN (op1
.type ());
1136 gcc_checking_assert (sign
== TYPE_SIGN (op2
.type ()));
1138 if (wi::ge_p (op1
.lower_bound (), op2
.upper_bound (), sign
))
1139 r
= range_true (type
);
1140 else if (!wi::ge_p (op1
.upper_bound (), op2
.lower_bound (), sign
))
1141 r
= range_false (type
);
1143 r
= range_true_and_false (type
);
1148 operator_ge::op1_range (irange
&r
, tree type
,
1151 relation_trio
) const
1153 switch (get_bool_state (r
, lhs
, type
))
1156 build_ge (r
, type
, op2
.lower_bound ());
1160 build_lt (r
, type
, op2
.upper_bound ());
1170 operator_ge::op2_range (irange
&r
, tree type
,
1173 relation_trio
) const
1175 switch (get_bool_state (r
, lhs
, type
))
1178 build_le (r
, type
, op1
.upper_bound ());
1182 build_gt (r
, type
, op1
.lower_bound ());
1192 class operator_plus
: public range_operator
1194 using range_operator::op1_range
;
1195 using range_operator::op2_range
;
1196 using range_operator::lhs_op1_relation
;
1197 using range_operator::lhs_op2_relation
;
1199 virtual bool op1_range (irange
&r
, tree type
,
1202 relation_trio
) const;
1203 virtual bool op2_range (irange
&r
, tree type
,
1206 relation_trio
) const;
1207 virtual void wi_fold (irange
&r
, tree type
,
1208 const wide_int
&lh_lb
,
1209 const wide_int
&lh_ub
,
1210 const wide_int
&rh_lb
,
1211 const wide_int
&rh_ub
) const;
1212 virtual relation_kind
lhs_op1_relation (const irange
&lhs
, const irange
&op1
,
1214 relation_kind rel
) const;
1215 virtual relation_kind
lhs_op2_relation (const irange
&lhs
, const irange
&op1
,
1217 relation_kind rel
) const;
1220 // Check to see if the range of OP2 indicates anything about the relation
1221 // between LHS and OP1.
1224 operator_plus::lhs_op1_relation (const irange
&lhs
,
1227 relation_kind
) const
1229 if (lhs
.undefined_p () || op1
.undefined_p () || op2
.undefined_p ())
1230 return VREL_VARYING
;
1232 tree type
= lhs
.type ();
1233 unsigned prec
= TYPE_PRECISION (type
);
1234 wi::overflow_type ovf1
, ovf2
;
1235 signop sign
= TYPE_SIGN (type
);
1237 // LHS = OP1 + 0 indicates LHS == OP1.
1241 if (TYPE_OVERFLOW_WRAPS (type
))
1243 wi::add (op1
.lower_bound (), op2
.lower_bound (), sign
, &ovf1
);
1244 wi::add (op1
.upper_bound (), op2
.upper_bound (), sign
, &ovf2
);
1247 ovf1
= ovf2
= wi::OVF_NONE
;
1249 // Never wrapping additions.
1252 // Positive op2 means lhs > op1.
1253 if (wi::gt_p (op2
.lower_bound (), wi::zero (prec
), sign
))
1255 if (wi::ge_p (op2
.lower_bound (), wi::zero (prec
), sign
))
1258 // Negative op2 means lhs < op1.
1259 if (wi::lt_p (op2
.upper_bound (), wi::zero (prec
), sign
))
1261 if (wi::le_p (op2
.upper_bound (), wi::zero (prec
), sign
))
1264 // Always wrapping additions.
1265 else if (ovf1
&& ovf1
== ovf2
)
1267 // Positive op2 means lhs < op1.
1268 if (wi::gt_p (op2
.lower_bound (), wi::zero (prec
), sign
))
1270 if (wi::ge_p (op2
.lower_bound (), wi::zero (prec
), sign
))
1273 // Negative op2 means lhs > op1.
1274 if (wi::lt_p (op2
.upper_bound (), wi::zero (prec
), sign
))
1276 if (wi::le_p (op2
.upper_bound (), wi::zero (prec
), sign
))
1280 // If op2 does not contain 0, then LHS and OP1 can never be equal.
1281 if (!range_includes_zero_p (&op2
))
1284 return VREL_VARYING
;
1287 // PLUS is symmetrical, so we can simply call lhs_op1_relation with reversed
1291 operator_plus::lhs_op2_relation (const irange
&lhs
, const irange
&op1
,
1292 const irange
&op2
, relation_kind rel
) const
1294 return lhs_op1_relation (lhs
, op2
, op1
, rel
);
1298 operator_plus::wi_fold (irange
&r
, tree type
,
1299 const wide_int
&lh_lb
, const wide_int
&lh_ub
,
1300 const wide_int
&rh_lb
, const wide_int
&rh_ub
) const
1302 wi::overflow_type ov_lb
, ov_ub
;
1303 signop s
= TYPE_SIGN (type
);
1304 wide_int new_lb
= wi::add (lh_lb
, rh_lb
, s
, &ov_lb
);
1305 wide_int new_ub
= wi::add (lh_ub
, rh_ub
, s
, &ov_ub
);
1306 value_range_with_overflow (r
, type
, new_lb
, new_ub
, ov_lb
, ov_ub
);
1309 // Given addition or subtraction, determine the possible NORMAL ranges and
1310 // OVERFLOW ranges given an OFFSET range. ADD_P is true for addition.
1311 // Return the relation that exists between the LHS and OP1 in order for the
1312 // NORMAL range to apply.
1313 // a return value of VREL_VARYING means no ranges were applicable.
1315 static relation_kind
1316 plus_minus_ranges (irange
&r_ov
, irange
&r_normal
, const irange
&offset
,
1319 relation_kind kind
= VREL_VARYING
;
1320 // For now, only deal with constant adds. This could be extended to ranges
1321 // when someone is so motivated.
1322 if (!offset
.singleton_p () || offset
.zero_p ())
1325 // Always work with a positive offset. ie a+ -2 -> a-2 and a- -2 > a+2
1326 wide_int off
= offset
.lower_bound ();
1327 if (wi::neg_p (off
, SIGNED
))
1330 off
= wi::neg (off
);
1333 wi::overflow_type ov
;
1334 tree type
= offset
.type ();
1335 unsigned prec
= TYPE_PRECISION (type
);
1338 // calculate the normal range and relation for the operation.
1342 lb
= wi::zero (prec
);
1343 ub
= wi::sub (wi::to_wide (vrp_val_max (type
)), off
, UNSIGNED
, &ov
);
1350 ub
= wi::to_wide (vrp_val_max (type
));
1353 int_range
<2> normal_range (type
, lb
, ub
);
1354 int_range
<2> ov_range (type
, lb
, ub
, VR_ANTI_RANGE
);
1357 r_normal
= normal_range
;
1361 // Once op1 has been calculated by operator_plus or operator_minus, check
1362 // to see if the relation passed causes any part of the calculation to
1363 // be not possible. ie
1364 // a_2 = b_3 + 1 with a_2 < b_3 can refine the range of b_3 to [INF, INF]
1365 // and that further refines a_2 to [0, 0].
1366 // R is the value of op1, OP2 is the offset being added/subtracted, REL is the
1367 // relation between LHS relatoin OP1 and ADD_P is true for PLUS, false for
1368 // MINUS. IF any adjustment can be made, R will reflect it.
1371 adjust_op1_for_overflow (irange
&r
, const irange
&op2
, relation_kind rel
,
1374 if (r
.undefined_p ())
1376 tree type
= r
.type ();
1377 // Check for unsigned overflow and calculate the overflow part.
1378 signop s
= TYPE_SIGN (type
);
1379 if (!TYPE_OVERFLOW_WRAPS (type
) || s
== SIGNED
)
1382 // Only work with <, <=, >, >= relations.
1383 if (!relation_lt_le_gt_ge_p (rel
))
1386 // Get the ranges for this offset.
1387 int_range_max normal
, overflow
;
1388 relation_kind k
= plus_minus_ranges (overflow
, normal
, op2
, add_p
);
1390 // VREL_VARYING means there are no adjustments.
1391 if (k
== VREL_VARYING
)
1394 // If the relations match use the normal range, otherwise use overflow range.
1395 if (relation_intersect (k
, rel
) == k
)
1396 r
.intersect (normal
);
1398 r
.intersect (overflow
);
1403 operator_plus::op1_range (irange
&r
, tree type
,
1406 relation_trio trio
) const
1408 if (lhs
.undefined_p ())
1410 // Start with the default operation.
1411 range_op_handler
minus (MINUS_EXPR
, type
);
1414 bool res
= minus
.fold_range (r
, type
, lhs
, op2
);
1415 relation_kind rel
= trio
.lhs_op2 ();
1416 // Check for a relation refinement.
1418 adjust_op1_for_overflow (r
, op2
, rel
, true /* PLUS_EXPR */);
1423 operator_plus::op2_range (irange
&r
, tree type
,
1426 relation_trio rel
) const
1428 return op1_range (r
, type
, lhs
, op1
, rel
.swap_op1_op2 ());
1432 class operator_minus
: public range_operator
1434 using range_operator::fold_range
;
1435 using range_operator::op1_range
;
1436 using range_operator::op2_range
;
1438 virtual bool op1_range (irange
&r
, tree type
,
1441 relation_trio
) const;
1442 virtual bool op2_range (irange
&r
, tree type
,
1445 relation_trio
) const;
1446 virtual void wi_fold (irange
&r
, tree type
,
1447 const wide_int
&lh_lb
,
1448 const wide_int
&lh_ub
,
1449 const wide_int
&rh_lb
,
1450 const wide_int
&rh_ub
) const;
1451 virtual relation_kind
lhs_op1_relation (const irange
&lhs
,
1454 relation_kind rel
) const;
1455 virtual bool op1_op2_relation_effect (irange
&lhs_range
,
1457 const irange
&op1_range
,
1458 const irange
&op2_range
,
1459 relation_kind rel
) const;
1463 operator_minus::wi_fold (irange
&r
, tree type
,
1464 const wide_int
&lh_lb
, const wide_int
&lh_ub
,
1465 const wide_int
&rh_lb
, const wide_int
&rh_ub
) const
1467 wi::overflow_type ov_lb
, ov_ub
;
1468 signop s
= TYPE_SIGN (type
);
1469 wide_int new_lb
= wi::sub (lh_lb
, rh_ub
, s
, &ov_lb
);
1470 wide_int new_ub
= wi::sub (lh_ub
, rh_lb
, s
, &ov_ub
);
1471 value_range_with_overflow (r
, type
, new_lb
, new_ub
, ov_lb
, ov_ub
);
1475 // Return the relation between LHS and OP1 based on the relation between
1479 operator_minus::lhs_op1_relation (const irange
&, const irange
&op1
,
1480 const irange
&, relation_kind rel
) const
1482 if (!op1
.undefined_p () && TYPE_SIGN (op1
.type ()) == UNSIGNED
)
1491 return VREL_VARYING
;
1494 // Check to see if the relation REL between OP1 and OP2 has any effect on the
1495 // LHS of the expression. If so, apply it to LHS_RANGE. This is a helper
1496 // function for both MINUS_EXPR and POINTER_DIFF_EXPR.
1499 minus_op1_op2_relation_effect (irange
&lhs_range
, tree type
,
1500 const irange
&op1_range ATTRIBUTE_UNUSED
,
1501 const irange
&op2_range ATTRIBUTE_UNUSED
,
1504 if (rel
== VREL_VARYING
)
1507 int_range
<2> rel_range
;
1508 unsigned prec
= TYPE_PRECISION (type
);
1509 signop sgn
= TYPE_SIGN (type
);
1511 // == and != produce [0,0] and ~[0,0] regardless of wrapping.
1513 rel_range
= int_range
<2> (type
, wi::zero (prec
), wi::zero (prec
));
1514 else if (rel
== VREL_NE
)
1515 rel_range
= int_range
<2> (type
, wi::zero (prec
), wi::zero (prec
),
1517 else if (TYPE_OVERFLOW_WRAPS (type
))
1521 // For wrapping signed values and unsigned, if op1 > op2 or
1522 // op1 < op2, then op1 - op2 can be restricted to ~[0, 0].
1525 rel_range
= int_range
<2> (type
, wi::zero (prec
), wi::zero (prec
),
1536 // op1 > op2, op1 - op2 can be restricted to [1, +INF]
1538 rel_range
= int_range
<2> (type
, wi::one (prec
),
1539 wi::max_value (prec
, sgn
));
1541 // op1 >= op2, op1 - op2 can be restricted to [0, +INF]
1543 rel_range
= int_range
<2> (type
, wi::zero (prec
),
1544 wi::max_value (prec
, sgn
));
1546 // op1 < op2, op1 - op2 can be restricted to [-INF, -1]
1548 rel_range
= int_range
<2> (type
, wi::min_value (prec
, sgn
),
1549 wi::minus_one (prec
));
1551 // op1 <= op2, op1 - op2 can be restricted to [-INF, 0]
1553 rel_range
= int_range
<2> (type
, wi::min_value (prec
, sgn
),
1560 lhs_range
.intersect (rel_range
);
1565 operator_minus::op1_op2_relation_effect (irange
&lhs_range
, tree type
,
1566 const irange
&op1_range
,
1567 const irange
&op2_range
,
1568 relation_kind rel
) const
1570 return minus_op1_op2_relation_effect (lhs_range
, type
, op1_range
, op2_range
,
1575 operator_minus::op1_range (irange
&r
, tree type
,
1578 relation_trio trio
) const
1580 if (lhs
.undefined_p ())
1582 // Start with the default operation.
1583 range_op_handler
minus (PLUS_EXPR
, type
);
1586 bool res
= minus
.fold_range (r
, type
, lhs
, op2
);
1587 relation_kind rel
= trio
.lhs_op2 ();
1589 adjust_op1_for_overflow (r
, op2
, rel
, false /* PLUS_EXPR */);
1595 operator_minus::op2_range (irange
&r
, tree type
,
1598 relation_trio
) const
1600 if (lhs
.undefined_p ())
1602 return fold_range (r
, type
, op1
, lhs
);
1606 class operator_pointer_diff
: public range_operator
1608 virtual bool op1_op2_relation_effect (irange
&lhs_range
,
1610 const irange
&op1_range
,
1611 const irange
&op2_range
,
1612 relation_kind rel
) const;
1616 operator_pointer_diff::op1_op2_relation_effect (irange
&lhs_range
, tree type
,
1617 const irange
&op1_range
,
1618 const irange
&op2_range
,
1619 relation_kind rel
) const
1621 return minus_op1_op2_relation_effect (lhs_range
, type
, op1_range
, op2_range
,
1626 class operator_min
: public range_operator
1629 virtual void wi_fold (irange
&r
, tree type
,
1630 const wide_int
&lh_lb
,
1631 const wide_int
&lh_ub
,
1632 const wide_int
&rh_lb
,
1633 const wide_int
&rh_ub
) const;
1637 operator_min::wi_fold (irange
&r
, tree type
,
1638 const wide_int
&lh_lb
, const wide_int
&lh_ub
,
1639 const wide_int
&rh_lb
, const wide_int
&rh_ub
) const
1641 signop s
= TYPE_SIGN (type
);
1642 wide_int new_lb
= wi::min (lh_lb
, rh_lb
, s
);
1643 wide_int new_ub
= wi::min (lh_ub
, rh_ub
, s
);
1644 value_range_with_overflow (r
, type
, new_lb
, new_ub
);
1648 class operator_max
: public range_operator
1651 virtual void wi_fold (irange
&r
, tree type
,
1652 const wide_int
&lh_lb
,
1653 const wide_int
&lh_ub
,
1654 const wide_int
&rh_lb
,
1655 const wide_int
&rh_ub
) const;
1659 operator_max::wi_fold (irange
&r
, tree type
,
1660 const wide_int
&lh_lb
, const wide_int
&lh_ub
,
1661 const wide_int
&rh_lb
, const wide_int
&rh_ub
) const
1663 signop s
= TYPE_SIGN (type
);
1664 wide_int new_lb
= wi::max (lh_lb
, rh_lb
, s
);
1665 wide_int new_ub
= wi::max (lh_ub
, rh_ub
, s
);
1666 value_range_with_overflow (r
, type
, new_lb
, new_ub
);
1670 class cross_product_operator
: public range_operator
1673 // Perform an operation between two wide-ints and place the result
1674 // in R. Return true if the operation overflowed.
1675 virtual bool wi_op_overflows (wide_int
&r
,
1678 const wide_int
&) const = 0;
1680 // Calculate the cross product of two sets of sub-ranges and return it.
1681 void wi_cross_product (irange
&r
, tree type
,
1682 const wide_int
&lh_lb
,
1683 const wide_int
&lh_ub
,
1684 const wide_int
&rh_lb
,
1685 const wide_int
&rh_ub
) const;
1688 // Calculate the cross product of two sets of ranges and return it.
1690 // Multiplications, divisions and shifts are a bit tricky to handle,
1691 // depending on the mix of signs we have in the two ranges, we need to
1692 // operate on different values to get the minimum and maximum values
1693 // for the new range. One approach is to figure out all the
1694 // variations of range combinations and do the operations.
1696 // However, this involves several calls to compare_values and it is
1697 // pretty convoluted. It's simpler to do the 4 operations (MIN0 OP
1698 // MIN1, MIN0 OP MAX1, MAX0 OP MIN1 and MAX0 OP MAX0 OP MAX1) and then
1699 // figure the smallest and largest values to form the new range.
1702 cross_product_operator::wi_cross_product (irange
&r
, tree type
,
1703 const wide_int
&lh_lb
,
1704 const wide_int
&lh_ub
,
1705 const wide_int
&rh_lb
,
1706 const wide_int
&rh_ub
) const
1708 wide_int cp1
, cp2
, cp3
, cp4
;
1709 // Default to varying.
1710 r
.set_varying (type
);
1712 // Compute the 4 cross operations, bailing if we get an overflow we
1714 if (wi_op_overflows (cp1
, type
, lh_lb
, rh_lb
))
1716 if (wi::eq_p (lh_lb
, lh_ub
))
1718 else if (wi_op_overflows (cp3
, type
, lh_ub
, rh_lb
))
1720 if (wi::eq_p (rh_lb
, rh_ub
))
1722 else if (wi_op_overflows (cp2
, type
, lh_lb
, rh_ub
))
1724 if (wi::eq_p (lh_lb
, lh_ub
))
1726 else if (wi_op_overflows (cp4
, type
, lh_ub
, rh_ub
))
1730 signop sign
= TYPE_SIGN (type
);
1731 if (wi::gt_p (cp1
, cp2
, sign
))
1732 std::swap (cp1
, cp2
);
1733 if (wi::gt_p (cp3
, cp4
, sign
))
1734 std::swap (cp3
, cp4
);
1736 // Choose min and max from the ordered pairs.
1737 wide_int res_lb
= wi::min (cp1
, cp3
, sign
);
1738 wide_int res_ub
= wi::max (cp2
, cp4
, sign
);
1739 value_range_with_overflow (r
, type
, res_lb
, res_ub
);
1743 class operator_mult
: public cross_product_operator
1745 using range_operator::op1_range
;
1746 using range_operator::op2_range
;
1748 virtual void wi_fold (irange
&r
, tree type
,
1749 const wide_int
&lh_lb
,
1750 const wide_int
&lh_ub
,
1751 const wide_int
&rh_lb
,
1752 const wide_int
&rh_ub
) const;
1753 virtual bool wi_op_overflows (wide_int
&res
, tree type
,
1754 const wide_int
&w0
, const wide_int
&w1
) const;
1755 virtual bool op1_range (irange
&r
, tree type
,
1758 relation_trio
) const;
1759 virtual bool op2_range (irange
&r
, tree type
,
1762 relation_trio
) const;
1766 operator_mult::op1_range (irange
&r
, tree type
,
1767 const irange
&lhs
, const irange
&op2
,
1768 relation_trio
) const
1771 if (lhs
.undefined_p ())
1774 // We can't solve 0 = OP1 * N by dividing by N with a wrapping type.
1775 // For example: For 0 = OP1 * 2, OP1 could be 0, or MAXINT, whereas
1776 // for 4 = OP1 * 2, OP1 could be 2 or 130 (unsigned 8-bit)
1777 if (TYPE_OVERFLOW_WRAPS (type
))
1780 if (op2
.singleton_p (&offset
) && !integer_zerop (offset
))
1781 return range_op_handler (TRUNC_DIV_EXPR
, type
).fold_range (r
, type
,
1787 operator_mult::op2_range (irange
&r
, tree type
,
1788 const irange
&lhs
, const irange
&op1
,
1789 relation_trio rel
) const
1791 return operator_mult::op1_range (r
, type
, lhs
, op1
, rel
.swap_op1_op2 ());
1795 operator_mult::wi_op_overflows (wide_int
&res
, tree type
,
1796 const wide_int
&w0
, const wide_int
&w1
) const
1798 wi::overflow_type overflow
= wi::OVF_NONE
;
1799 signop sign
= TYPE_SIGN (type
);
1800 res
= wi::mul (w0
, w1
, sign
, &overflow
);
1801 if (overflow
&& TYPE_OVERFLOW_UNDEFINED (type
))
1803 // For multiplication, the sign of the overflow is given
1804 // by the comparison of the signs of the operands.
1805 if (sign
== UNSIGNED
|| w0
.sign_mask () == w1
.sign_mask ())
1806 res
= wi::max_value (w0
.get_precision (), sign
);
1808 res
= wi::min_value (w0
.get_precision (), sign
);
1815 operator_mult::wi_fold (irange
&r
, tree type
,
1816 const wide_int
&lh_lb
, const wide_int
&lh_ub
,
1817 const wide_int
&rh_lb
, const wide_int
&rh_ub
) const
1819 if (TYPE_OVERFLOW_UNDEFINED (type
))
1821 wi_cross_product (r
, type
, lh_lb
, lh_ub
, rh_lb
, rh_ub
);
1825 // Multiply the ranges when overflow wraps. This is basically fancy
1826 // code so we don't drop to varying with an unsigned
1829 // This test requires 2*prec bits if both operands are signed and
1830 // 2*prec + 2 bits if either is not. Therefore, extend the values
1831 // using the sign of the result to PREC2. From here on out,
1832 // everthing is just signed math no matter what the input types
1835 signop sign
= TYPE_SIGN (type
);
1836 unsigned prec
= TYPE_PRECISION (type
);
1837 widest2_int min0
= widest2_int::from (lh_lb
, sign
);
1838 widest2_int max0
= widest2_int::from (lh_ub
, sign
);
1839 widest2_int min1
= widest2_int::from (rh_lb
, sign
);
1840 widest2_int max1
= widest2_int::from (rh_ub
, sign
);
1841 widest2_int sizem1
= wi::mask
<widest2_int
> (prec
, false);
1842 widest2_int size
= sizem1
+ 1;
1844 // Canonicalize the intervals.
1845 if (sign
== UNSIGNED
)
1847 if (wi::ltu_p (size
, min0
+ max0
))
1852 if (wi::ltu_p (size
, min1
+ max1
))
1859 // Sort the 4 products so that min is in prod0 and max is in
1861 widest2_int prod0
= min0
* min1
;
1862 widest2_int prod1
= min0
* max1
;
1863 widest2_int prod2
= max0
* min1
;
1864 widest2_int prod3
= max0
* max1
;
1866 // min0min1 > max0max1
1868 std::swap (prod0
, prod3
);
1870 // min0max1 > max0min1
1872 std::swap (prod1
, prod2
);
1875 std::swap (prod0
, prod1
);
1878 std::swap (prod2
, prod3
);
1881 prod2
= prod3
- prod0
;
1882 if (wi::geu_p (prod2
, sizem1
))
1883 // The range covers all values.
1884 r
.set_varying (type
);
1887 wide_int new_lb
= wide_int::from (prod0
, prec
, sign
);
1888 wide_int new_ub
= wide_int::from (prod3
, prec
, sign
);
1889 create_possibly_reversed_range (r
, type
, new_lb
, new_ub
);
1894 class operator_div
: public cross_product_operator
1897 operator_div (enum tree_code c
) { code
= c
; }
1898 virtual void wi_fold (irange
&r
, tree type
,
1899 const wide_int
&lh_lb
,
1900 const wide_int
&lh_ub
,
1901 const wide_int
&rh_lb
,
1902 const wide_int
&rh_ub
) const;
1903 virtual bool wi_op_overflows (wide_int
&res
, tree type
,
1904 const wide_int
&, const wide_int
&) const;
1906 enum tree_code code
;
1910 operator_div::wi_op_overflows (wide_int
&res
, tree type
,
1911 const wide_int
&w0
, const wide_int
&w1
) const
1916 wi::overflow_type overflow
= wi::OVF_NONE
;
1917 signop sign
= TYPE_SIGN (type
);
1921 case EXACT_DIV_EXPR
:
1922 // EXACT_DIV_EXPR is implemented as TRUNC_DIV_EXPR in
1923 // operator_exact_divide. No need to handle it here.
1926 case TRUNC_DIV_EXPR
:
1927 res
= wi::div_trunc (w0
, w1
, sign
, &overflow
);
1929 case FLOOR_DIV_EXPR
:
1930 res
= wi::div_floor (w0
, w1
, sign
, &overflow
);
1932 case ROUND_DIV_EXPR
:
1933 res
= wi::div_round (w0
, w1
, sign
, &overflow
);
1936 res
= wi::div_ceil (w0
, w1
, sign
, &overflow
);
1942 if (overflow
&& TYPE_OVERFLOW_UNDEFINED (type
))
1944 // For division, the only case is -INF / -1 = +INF.
1945 res
= wi::max_value (w0
.get_precision (), sign
);
1952 operator_div::wi_fold (irange
&r
, tree type
,
1953 const wide_int
&lh_lb
, const wide_int
&lh_ub
,
1954 const wide_int
&rh_lb
, const wide_int
&rh_ub
) const
1956 const wide_int dividend_min
= lh_lb
;
1957 const wide_int dividend_max
= lh_ub
;
1958 const wide_int divisor_min
= rh_lb
;
1959 const wide_int divisor_max
= rh_ub
;
1960 signop sign
= TYPE_SIGN (type
);
1961 unsigned prec
= TYPE_PRECISION (type
);
1962 wide_int extra_min
, extra_max
;
1964 // If we know we won't divide by zero, just do the division.
1965 if (!wi_includes_zero_p (type
, divisor_min
, divisor_max
))
1967 wi_cross_product (r
, type
, dividend_min
, dividend_max
,
1968 divisor_min
, divisor_max
);
1972 // If we're definitely dividing by zero, there's nothing to do.
1973 if (wi_zero_p (type
, divisor_min
, divisor_max
))
1979 // Perform the division in 2 parts, [LB, -1] and [1, UB], which will
1980 // skip any division by zero.
1982 // First divide by the negative numbers, if any.
1983 if (wi::neg_p (divisor_min
, sign
))
1984 wi_cross_product (r
, type
, dividend_min
, dividend_max
,
1985 divisor_min
, wi::minus_one (prec
));
1989 // Then divide by the non-zero positive numbers, if any.
1990 if (wi::gt_p (divisor_max
, wi::zero (prec
), sign
))
1993 wi_cross_product (tmp
, type
, dividend_min
, dividend_max
,
1994 wi::one (prec
), divisor_max
);
1997 // We shouldn't still have undefined here.
1998 gcc_checking_assert (!r
.undefined_p ());
2001 operator_div
op_trunc_div (TRUNC_DIV_EXPR
);
2002 operator_div
op_floor_div (FLOOR_DIV_EXPR
);
2003 operator_div
op_round_div (ROUND_DIV_EXPR
);
2004 operator_div
op_ceil_div (CEIL_DIV_EXPR
);
2007 class operator_exact_divide
: public operator_div
2009 using range_operator::op1_range
;
2011 operator_exact_divide () : operator_div (TRUNC_DIV_EXPR
) { }
2012 virtual bool op1_range (irange
&r
, tree type
,
2015 relation_trio
) const;
2020 operator_exact_divide::op1_range (irange
&r
, tree type
,
2023 relation_trio
) const
2025 if (lhs
.undefined_p ())
2028 // [2, 4] = op1 / [3,3] since its exact divide, no need to worry about
2029 // remainders in the endpoints, so op1 = [2,4] * [3,3] = [6,12].
2030 // We wont bother trying to enumerate all the in between stuff :-P
2031 // TRUE accuraacy is [6,6][9,9][12,12]. This is unlikely to matter most of
2032 // the time however.
2033 // If op2 is a multiple of 2, we would be able to set some non-zero bits.
2034 if (op2
.singleton_p (&offset
)
2035 && !integer_zerop (offset
))
2036 return range_op_handler (MULT_EXPR
, type
).fold_range (r
, type
, lhs
, op2
);
2041 class operator_lshift
: public cross_product_operator
2043 using range_operator::fold_range
;
2044 using range_operator::op1_range
;
2046 virtual bool op1_range (irange
&r
, tree type
,
2049 relation_trio rel
= TRIO_VARYING
) const;
2050 virtual bool fold_range (irange
&r
, tree type
,
2053 relation_trio rel
= TRIO_VARYING
) const;
2055 virtual void wi_fold (irange
&r
, tree type
,
2056 const wide_int
&lh_lb
, const wide_int
&lh_ub
,
2057 const wide_int
&rh_lb
, const wide_int
&rh_ub
) const;
2058 virtual bool wi_op_overflows (wide_int
&res
,
2061 const wide_int
&) const;
2064 class operator_rshift
: public cross_product_operator
2066 using range_operator::fold_range
;
2067 using range_operator::op1_range
;
2068 using range_operator::lhs_op1_relation
;
2070 virtual bool fold_range (irange
&r
, tree type
,
2073 relation_trio rel
= TRIO_VARYING
) const;
2074 virtual void wi_fold (irange
&r
, tree type
,
2075 const wide_int
&lh_lb
,
2076 const wide_int
&lh_ub
,
2077 const wide_int
&rh_lb
,
2078 const wide_int
&rh_ub
) const;
2079 virtual bool wi_op_overflows (wide_int
&res
,
2082 const wide_int
&w1
) const;
2083 virtual bool op1_range (irange
&, tree type
,
2086 relation_trio rel
= TRIO_VARYING
) const;
2087 virtual relation_kind
lhs_op1_relation (const irange
&lhs
,
2090 relation_kind rel
) const;
2095 operator_rshift::lhs_op1_relation (const irange
&lhs ATTRIBUTE_UNUSED
,
2098 relation_kind
) const
2100 // If both operands range are >= 0, then the LHS <= op1.
2101 if (!op1
.undefined_p () && !op2
.undefined_p ()
2102 && wi::ge_p (op1
.lower_bound (), 0, TYPE_SIGN (op1
.type ()))
2103 && wi::ge_p (op2
.lower_bound (), 0, TYPE_SIGN (op2
.type ())))
2105 return VREL_VARYING
;
2109 operator_lshift::fold_range (irange
&r
, tree type
,
2112 relation_trio rel
) const
2114 int_range_max shift_range
;
2115 if (!get_shift_range (shift_range
, type
, op2
))
2117 if (op2
.undefined_p ())
2120 r
.set_varying (type
);
2124 // Transform left shifts by constants into multiplies.
2125 if (shift_range
.singleton_p ())
2127 unsigned shift
= shift_range
.lower_bound ().to_uhwi ();
2128 wide_int tmp
= wi::set_bit_in_zero (shift
, TYPE_PRECISION (type
));
2129 int_range
<1> mult (type
, tmp
, tmp
);
2131 // Force wrapping multiplication.
2132 bool saved_flag_wrapv
= flag_wrapv
;
2133 bool saved_flag_wrapv_pointer
= flag_wrapv_pointer
;
2135 flag_wrapv_pointer
= 1;
2136 bool b
= op_mult
.fold_range (r
, type
, op1
, mult
);
2137 flag_wrapv
= saved_flag_wrapv
;
2138 flag_wrapv_pointer
= saved_flag_wrapv_pointer
;
2142 // Otherwise, invoke the generic fold routine.
2143 return range_operator::fold_range (r
, type
, op1
, shift_range
, rel
);
2147 operator_lshift::wi_fold (irange
&r
, tree type
,
2148 const wide_int
&lh_lb
, const wide_int
&lh_ub
,
2149 const wide_int
&rh_lb
, const wide_int
&rh_ub
) const
2151 signop sign
= TYPE_SIGN (type
);
2152 unsigned prec
= TYPE_PRECISION (type
);
2153 int overflow_pos
= sign
== SIGNED
? prec
- 1 : prec
;
2154 int bound_shift
= overflow_pos
- rh_ub
.to_shwi ();
2155 // If bound_shift == HOST_BITS_PER_WIDE_INT, the llshift can
2156 // overflow. However, for that to happen, rh.max needs to be zero,
2157 // which means rh is a singleton range of zero, which means we simply return
2158 // [lh_lb, lh_ub] as the range.
2159 if (wi::eq_p (rh_ub
, rh_lb
) && wi::eq_p (rh_ub
, 0))
2161 r
= int_range
<2> (type
, lh_lb
, lh_ub
);
2165 wide_int bound
= wi::set_bit_in_zero (bound_shift
, prec
);
2166 wide_int complement
= ~(bound
- 1);
2167 wide_int low_bound
, high_bound
;
2168 bool in_bounds
= false;
2170 if (sign
== UNSIGNED
)
2173 high_bound
= complement
;
2174 if (wi::ltu_p (lh_ub
, low_bound
))
2176 // [5, 6] << [1, 2] == [10, 24].
2177 // We're shifting out only zeroes, the value increases
2181 else if (wi::ltu_p (high_bound
, lh_lb
))
2183 // [0xffffff00, 0xffffffff] << [1, 2]
2184 // == [0xfffffc00, 0xfffffffe].
2185 // We're shifting out only ones, the value decreases
2192 // [-1, 1] << [1, 2] == [-4, 4]
2193 low_bound
= complement
;
2195 if (wi::lts_p (lh_ub
, high_bound
)
2196 && wi::lts_p (low_bound
, lh_lb
))
2198 // For non-negative numbers, we're shifting out only zeroes,
2199 // the value increases monotonically. For negative numbers,
2200 // we're shifting out only ones, the value decreases
2207 wi_cross_product (r
, type
, lh_lb
, lh_ub
, rh_lb
, rh_ub
);
2209 r
.set_varying (type
);
2213 operator_lshift::wi_op_overflows (wide_int
&res
, tree type
,
2214 const wide_int
&w0
, const wide_int
&w1
) const
2216 signop sign
= TYPE_SIGN (type
);
2219 // It's unclear from the C standard whether shifts can overflow.
2220 // The following code ignores overflow; perhaps a C standard
2221 // interpretation ruling is needed.
2222 res
= wi::rshift (w0
, -w1
, sign
);
2225 res
= wi::lshift (w0
, w1
);
2230 operator_lshift::op1_range (irange
&r
,
2234 relation_trio
) const
2236 if (lhs
.undefined_p ())
2240 if (!lhs
.contains_p (build_zero_cst (type
)))
2241 r
.set_nonzero (type
);
2243 r
.set_varying (type
);
2245 if (op2
.singleton_p (&shift_amount
))
2247 wide_int shift
= wi::to_wide (shift_amount
);
2248 if (wi::lt_p (shift
, 0, SIGNED
))
2250 if (wi::ge_p (shift
, wi::uhwi (TYPE_PRECISION (type
),
2251 TYPE_PRECISION (op2
.type ())),
2260 // Work completely in unsigned mode to start.
2262 int_range_max tmp_range
;
2263 if (TYPE_SIGN (type
) == SIGNED
)
2265 int_range_max tmp
= lhs
;
2266 utype
= unsigned_type_for (type
);
2267 range_cast (tmp
, utype
);
2268 op_rshift
.fold_range (tmp_range
, utype
, tmp
, op2
);
2271 op_rshift
.fold_range (tmp_range
, utype
, lhs
, op2
);
2273 // Start with ranges which can produce the LHS by right shifting the
2274 // result by the shift amount.
2275 // ie [0x08, 0xF0] = op1 << 2 will start with
2276 // [00001000, 11110000] = op1 << 2
2277 // [0x02, 0x4C] aka [00000010, 00111100]
2279 // Then create a range from the LB with the least significant upper bit
2280 // set, to the upper bound with all the bits set.
2281 // This would be [0x42, 0xFC] aka [01000010, 11111100].
2283 // Ideally we do this for each subrange, but just lump them all for now.
2284 unsigned low_bits
= TYPE_PRECISION (utype
)
2285 - TREE_INT_CST_LOW (shift_amount
);
2286 wide_int up_mask
= wi::mask (low_bits
, true, TYPE_PRECISION (utype
));
2287 wide_int new_ub
= wi::bit_or (up_mask
, tmp_range
.upper_bound ());
2288 wide_int new_lb
= wi::set_bit (tmp_range
.lower_bound (), low_bits
);
2289 int_range
<2> fill_range (utype
, new_lb
, new_ub
);
2290 tmp_range
.union_ (fill_range
);
2293 range_cast (tmp_range
, type
);
2295 r
.intersect (tmp_range
);
2299 return !r
.varying_p ();
2303 operator_rshift::op1_range (irange
&r
,
2307 relation_trio
) const
2310 if (lhs
.undefined_p ())
2312 if (op2
.singleton_p (&shift
))
2314 // Ignore nonsensical shifts.
2315 unsigned prec
= TYPE_PRECISION (type
);
2316 if (wi::ge_p (wi::to_wide (shift
),
2317 wi::uhwi (prec
, TYPE_PRECISION (TREE_TYPE (shift
))),
2320 if (wi::to_wide (shift
) == 0)
2326 // Folding the original operation may discard some impossible
2327 // ranges from the LHS.
2328 int_range_max lhs_refined
;
2329 op_rshift
.fold_range (lhs_refined
, type
, int_range
<1> (type
), op2
);
2330 lhs_refined
.intersect (lhs
);
2331 if (lhs_refined
.undefined_p ())
2336 int_range_max
shift_range (shift
, shift
);
2337 int_range_max lb
, ub
;
2338 op_lshift
.fold_range (lb
, type
, lhs_refined
, shift_range
);
2340 // 0000 0111 = OP1 >> 3
2342 // OP1 is anything from 0011 1000 to 0011 1111. That is, a
2343 // range from LHS<<3 plus a mask of the 3 bits we shifted on the
2344 // right hand side (0x07).
2345 tree mask
= fold_build1 (BIT_NOT_EXPR
, type
,
2346 fold_build2 (LSHIFT_EXPR
, type
,
2347 build_minus_one_cst (type
),
2349 int_range_max
mask_range (build_zero_cst (type
), mask
);
2350 op_plus
.fold_range (ub
, type
, lb
, mask_range
);
2353 if (!lhs_refined
.contains_p (build_zero_cst (type
)))
2355 mask_range
.invert ();
2356 r
.intersect (mask_range
);
2364 operator_rshift::wi_op_overflows (wide_int
&res
,
2367 const wide_int
&w1
) const
2369 signop sign
= TYPE_SIGN (type
);
2371 res
= wi::lshift (w0
, -w1
);
2374 // It's unclear from the C standard whether shifts can overflow.
2375 // The following code ignores overflow; perhaps a C standard
2376 // interpretation ruling is needed.
2377 res
= wi::rshift (w0
, w1
, sign
);
2383 operator_rshift::fold_range (irange
&r
, tree type
,
2386 relation_trio rel
) const
2388 int_range_max shift
;
2389 if (!get_shift_range (shift
, type
, op2
))
2391 if (op2
.undefined_p ())
2394 r
.set_varying (type
);
2398 return range_operator::fold_range (r
, type
, op1
, shift
, rel
);
2402 operator_rshift::wi_fold (irange
&r
, tree type
,
2403 const wide_int
&lh_lb
, const wide_int
&lh_ub
,
2404 const wide_int
&rh_lb
, const wide_int
&rh_ub
) const
2406 wi_cross_product (r
, type
, lh_lb
, lh_ub
, rh_lb
, rh_ub
);
2410 class operator_cast
: public range_operator
2412 using range_operator::fold_range
;
2413 using range_operator::op1_range
;
2415 virtual bool fold_range (irange
&r
, tree type
,
2418 relation_trio rel
= TRIO_VARYING
) const;
2419 virtual bool op1_range (irange
&r
, tree type
,
2422 relation_trio rel
= TRIO_VARYING
) const;
2423 virtual relation_kind
lhs_op1_relation (const irange
&lhs
,
2426 relation_kind
) const;
2428 bool truncating_cast_p (const irange
&inner
, const irange
&outer
) const;
2429 bool inside_domain_p (const wide_int
&min
, const wide_int
&max
,
2430 const irange
&outer
) const;
2431 void fold_pair (irange
&r
, unsigned index
, const irange
&inner
,
2432 const irange
&outer
) const;
2435 // Add a partial equivalence between the LHS and op1 for casts.
2438 operator_cast::lhs_op1_relation (const irange
&lhs
,
2440 const irange
&op2 ATTRIBUTE_UNUSED
,
2441 relation_kind
) const
2443 if (lhs
.undefined_p () || op1
.undefined_p ())
2444 return VREL_VARYING
;
2445 unsigned lhs_prec
= TYPE_PRECISION (lhs
.type ());
2446 unsigned op1_prec
= TYPE_PRECISION (op1
.type ());
2447 // If the result gets sign extended into a larger type check first if this
2448 // qualifies as a partial equivalence.
2449 if (TYPE_SIGN (op1
.type ()) == SIGNED
&& lhs_prec
> op1_prec
)
2451 // If the result is sign extended, and the LHS is larger than op1,
2452 // check if op1's range can be negative as the sign extention will
2453 // cause the upper bits to be 1 instead of 0, invalidating the PE.
2454 int_range
<3> negs
= range_negatives (op1
.type ());
2455 negs
.intersect (op1
);
2456 if (!negs
.undefined_p ())
2457 return VREL_VARYING
;
2460 unsigned prec
= MIN (lhs_prec
, op1_prec
);
2461 return bits_to_pe (prec
);
2464 // Return TRUE if casting from INNER to OUTER is a truncating cast.
2467 operator_cast::truncating_cast_p (const irange
&inner
,
2468 const irange
&outer
) const
2470 return TYPE_PRECISION (outer
.type ()) < TYPE_PRECISION (inner
.type ());
2473 // Return TRUE if [MIN,MAX] is inside the domain of RANGE's type.
2476 operator_cast::inside_domain_p (const wide_int
&min
,
2477 const wide_int
&max
,
2478 const irange
&range
) const
2480 wide_int domain_min
= wi::to_wide (vrp_val_min (range
.type ()));
2481 wide_int domain_max
= wi::to_wide (vrp_val_max (range
.type ()));
2482 signop domain_sign
= TYPE_SIGN (range
.type ());
2483 return (wi::le_p (min
, domain_max
, domain_sign
)
2484 && wi::le_p (max
, domain_max
, domain_sign
)
2485 && wi::ge_p (min
, domain_min
, domain_sign
)
2486 && wi::ge_p (max
, domain_min
, domain_sign
));
2490 // Helper for fold_range which work on a pair at a time.
2493 operator_cast::fold_pair (irange
&r
, unsigned index
,
2494 const irange
&inner
,
2495 const irange
&outer
) const
2497 tree inner_type
= inner
.type ();
2498 tree outer_type
= outer
.type ();
2499 signop inner_sign
= TYPE_SIGN (inner_type
);
2500 unsigned outer_prec
= TYPE_PRECISION (outer_type
);
2502 // check to see if casting from INNER to OUTER is a conversion that
2503 // fits in the resulting OUTER type.
2504 wide_int inner_lb
= inner
.lower_bound (index
);
2505 wide_int inner_ub
= inner
.upper_bound (index
);
2506 if (truncating_cast_p (inner
, outer
))
2508 // We may be able to accomodate a truncating cast if the
2509 // resulting range can be represented in the target type...
2510 if (wi::rshift (wi::sub (inner_ub
, inner_lb
),
2511 wi::uhwi (outer_prec
, TYPE_PRECISION (inner
.type ())),
2514 r
.set_varying (outer_type
);
2518 // ...but we must still verify that the final range fits in the
2519 // domain. This catches -fstrict-enum restrictions where the domain
2520 // range is smaller than what fits in the underlying type.
2521 wide_int min
= wide_int::from (inner_lb
, outer_prec
, inner_sign
);
2522 wide_int max
= wide_int::from (inner_ub
, outer_prec
, inner_sign
);
2523 if (inside_domain_p (min
, max
, outer
))
2524 create_possibly_reversed_range (r
, outer_type
, min
, max
);
2526 r
.set_varying (outer_type
);
2531 operator_cast::fold_range (irange
&r
, tree type ATTRIBUTE_UNUSED
,
2532 const irange
&inner
,
2533 const irange
&outer
,
2534 relation_trio
) const
2536 if (empty_range_varying (r
, type
, inner
, outer
))
2539 gcc_checking_assert (outer
.varying_p ());
2540 gcc_checking_assert (inner
.num_pairs () > 0);
2542 // Avoid a temporary by folding the first pair directly into the result.
2543 fold_pair (r
, 0, inner
, outer
);
2545 // Then process any additonal pairs by unioning with their results.
2546 for (unsigned x
= 1; x
< inner
.num_pairs (); ++x
)
2549 fold_pair (tmp
, x
, inner
, outer
);
2555 // Update the nonzero mask. Truncating casts are problematic unless
2556 // the conversion fits in the resulting outer type.
2557 wide_int nz
= inner
.get_nonzero_bits ();
2558 if (truncating_cast_p (inner
, outer
)
2559 && wi::rshift (nz
, wi::uhwi (TYPE_PRECISION (outer
.type ()),
2560 TYPE_PRECISION (inner
.type ())),
2561 TYPE_SIGN (inner
.type ())) != 0)
2563 nz
= wide_int::from (nz
, TYPE_PRECISION (type
), TYPE_SIGN (inner
.type ()));
2564 r
.set_nonzero_bits (nz
);
2570 operator_cast::op1_range (irange
&r
, tree type
,
2573 relation_trio
) const
2575 if (lhs
.undefined_p ())
2577 tree lhs_type
= lhs
.type ();
2578 gcc_checking_assert (types_compatible_p (op2
.type(), type
));
2580 // If we are calculating a pointer, shortcut to what we really care about.
2581 if (POINTER_TYPE_P (type
))
2583 // Conversion from other pointers or a constant (including 0/NULL)
2584 // are straightforward.
2585 if (POINTER_TYPE_P (lhs
.type ())
2586 || (lhs
.singleton_p ()
2587 && TYPE_PRECISION (lhs
.type ()) >= TYPE_PRECISION (type
)))
2590 range_cast (r
, type
);
2594 // If the LHS is not a pointer nor a singleton, then it is
2595 // either VARYING or non-zero.
2596 if (!lhs
.contains_p (build_zero_cst (lhs
.type ())))
2597 r
.set_nonzero (type
);
2599 r
.set_varying (type
);
2605 if (truncating_cast_p (op2
, lhs
))
2607 if (lhs
.varying_p ())
2608 r
.set_varying (type
);
2611 // We want to insert the LHS as an unsigned value since it
2612 // would not trigger the signed bit of the larger type.
2613 int_range_max converted_lhs
= lhs
;
2614 range_cast (converted_lhs
, unsigned_type_for (lhs_type
));
2615 range_cast (converted_lhs
, type
);
2616 // Start by building the positive signed outer range for the type.
2617 wide_int lim
= wi::set_bit_in_zero (TYPE_PRECISION (lhs_type
),
2618 TYPE_PRECISION (type
));
2619 r
= int_range
<1> (type
, lim
, wi::max_value (TYPE_PRECISION (type
),
2621 // For the signed part, we need to simply union the 2 ranges now.
2622 r
.union_ (converted_lhs
);
2624 // Create maximal negative number outside of LHS bits.
2625 lim
= wi::mask (TYPE_PRECISION (lhs_type
), true,
2626 TYPE_PRECISION (type
));
2627 // Add this to the unsigned LHS range(s).
2628 int_range_max
lim_range (type
, lim
, lim
);
2629 int_range_max lhs_neg
;
2630 range_op_handler (PLUS_EXPR
, type
).fold_range (lhs_neg
, type
,
2633 // lhs_neg now has all the negative versions of the LHS.
2634 // Now union in all the values from SIGNED MIN (0x80000) to
2635 // lim-1 in order to fill in all the ranges with the upper
2638 // PR 97317. If the lhs has only 1 bit less precision than the rhs,
2639 // we don't need to create a range from min to lim-1
2640 // calculate neg range traps trying to create [lim, lim - 1].
2641 wide_int min_val
= wi::min_value (TYPE_PRECISION (type
), SIGNED
);
2644 int_range_max
neg (type
,
2645 wi::min_value (TYPE_PRECISION (type
),
2648 lhs_neg
.union_ (neg
);
2650 // And finally, munge the signed and unsigned portions.
2653 // And intersect with any known value passed in the extra operand.
2659 if (TYPE_PRECISION (lhs_type
) == TYPE_PRECISION (type
))
2663 // The cast is not truncating, and the range is restricted to
2664 // the range of the RHS by this assignment.
2666 // Cast the range of the RHS to the type of the LHS.
2667 fold_range (tmp
, lhs_type
, int_range
<1> (type
), int_range
<1> (lhs_type
));
2668 // Intersect this with the LHS range will produce the range,
2669 // which will be cast to the RHS type before returning.
2670 tmp
.intersect (lhs
);
2673 // Cast the calculated range to the type of the RHS.
2674 fold_range (r
, type
, tmp
, int_range
<1> (type
));
2679 class operator_logical_and
: public range_operator
2681 using range_operator::fold_range
;
2682 using range_operator::op1_range
;
2683 using range_operator::op2_range
;
2685 virtual bool fold_range (irange
&r
, tree type
,
2688 relation_trio rel
= TRIO_VARYING
) const;
2689 virtual bool op1_range (irange
&r
, tree type
,
2692 relation_trio rel
= TRIO_VARYING
) const;
2693 virtual bool op2_range (irange
&r
, tree type
,
2696 relation_trio rel
= TRIO_VARYING
) const;
2701 operator_logical_and::fold_range (irange
&r
, tree type
,
2704 relation_trio
) const
2706 if (empty_range_varying (r
, type
, lh
, rh
))
2709 // 0 && anything is 0.
2710 if ((wi::eq_p (lh
.lower_bound (), 0) && wi::eq_p (lh
.upper_bound (), 0))
2711 || (wi::eq_p (lh
.lower_bound (), 0) && wi::eq_p (rh
.upper_bound (), 0)))
2712 r
= range_false (type
);
2713 else if (lh
.contains_p (build_zero_cst (lh
.type ()))
2714 || rh
.contains_p (build_zero_cst (rh
.type ())))
2715 // To reach this point, there must be a logical 1 on each side, and
2716 // the only remaining question is whether there is a zero or not.
2717 r
= range_true_and_false (type
);
2719 r
= range_true (type
);
2724 operator_logical_and::op1_range (irange
&r
, tree type
,
2726 const irange
&op2 ATTRIBUTE_UNUSED
,
2727 relation_trio
) const
2729 switch (get_bool_state (r
, lhs
, type
))
2732 // A true result means both sides of the AND must be true.
2733 r
= range_true (type
);
2736 // Any other result means only one side has to be false, the
2737 // other side can be anything. So we cannot be sure of any
2739 r
= range_true_and_false (type
);
2746 operator_logical_and::op2_range (irange
&r
, tree type
,
2749 relation_trio
) const
2751 return operator_logical_and::op1_range (r
, type
, lhs
, op1
);
2755 class operator_bitwise_and
: public range_operator
2757 using range_operator::fold_range
;
2758 using range_operator::op1_range
;
2759 using range_operator::op2_range
;
2761 virtual bool fold_range (irange
&r
, tree type
,
2764 relation_trio rel
= TRIO_VARYING
) const;
2765 virtual bool op1_range (irange
&r
, tree type
,
2768 relation_trio rel
= TRIO_VARYING
) const;
2769 virtual bool op2_range (irange
&r
, tree type
,
2772 relation_trio rel
= TRIO_VARYING
) const;
2773 virtual void wi_fold (irange
&r
, tree type
,
2774 const wide_int
&lh_lb
,
2775 const wide_int
&lh_ub
,
2776 const wide_int
&rh_lb
,
2777 const wide_int
&rh_ub
) const;
2778 virtual relation_kind
lhs_op1_relation (const irange
&lhs
,
2781 relation_kind
) const;
2783 void simple_op1_range_solver (irange
&r
, tree type
,
2785 const irange
&op2
) const;
2789 operator_bitwise_and::fold_range (irange
&r
, tree type
,
2792 relation_trio
) const
2794 if (range_operator::fold_range (r
, type
, lh
, rh
))
2796 if (!lh
.undefined_p () && !rh
.undefined_p ())
2797 r
.set_nonzero_bits (wi::bit_and (lh
.get_nonzero_bits (),
2798 rh
.get_nonzero_bits ()));
2805 // Optimize BIT_AND_EXPR, BIT_IOR_EXPR and BIT_XOR_EXPR of signed types
2806 // by considering the number of leading redundant sign bit copies.
2807 // clrsb (X op Y) = min (clrsb (X), clrsb (Y)), so for example
2808 // [-1, 0] op [-1, 0] is [-1, 0] (where nonzero_bits doesn't help).
2810 wi_optimize_signed_bitwise_op (irange
&r
, tree type
,
2811 const wide_int
&lh_lb
, const wide_int
&lh_ub
,
2812 const wide_int
&rh_lb
, const wide_int
&rh_ub
)
2814 int lh_clrsb
= MIN (wi::clrsb (lh_lb
), wi::clrsb (lh_ub
));
2815 int rh_clrsb
= MIN (wi::clrsb (rh_lb
), wi::clrsb (rh_ub
));
2816 int new_clrsb
= MIN (lh_clrsb
, rh_clrsb
);
2819 int type_prec
= TYPE_PRECISION (type
);
2820 int rprec
= (type_prec
- new_clrsb
) - 1;
2821 value_range_with_overflow (r
, type
,
2822 wi::mask (rprec
, true, type_prec
),
2823 wi::mask (rprec
, false, type_prec
));
2827 // An AND of 8,16, 32 or 64 bits can produce a partial equivalence between
2831 operator_bitwise_and::lhs_op1_relation (const irange
&lhs
,
2834 relation_kind
) const
2836 if (lhs
.undefined_p () || op1
.undefined_p () || op2
.undefined_p ())
2837 return VREL_VARYING
;
2838 if (!op2
.singleton_p ())
2839 return VREL_VARYING
;
2840 // if val == 0xff or 0xFFFF OR 0Xffffffff OR 0Xffffffffffffffff, return TRUE
2841 int prec1
= TYPE_PRECISION (op1
.type ());
2842 int prec2
= TYPE_PRECISION (op2
.type ());
2844 wide_int mask
= op2
.lower_bound ();
2845 if (wi::eq_p (mask
, wi::mask (8, false, prec2
)))
2847 else if (wi::eq_p (mask
, wi::mask (16, false, prec2
)))
2849 else if (wi::eq_p (mask
, wi::mask (32, false, prec2
)))
2851 else if (wi::eq_p (mask
, wi::mask (64, false, prec2
)))
2853 return bits_to_pe (MIN (prec1
, mask_prec
));
2856 // Optimize BIT_AND_EXPR and BIT_IOR_EXPR in terms of a mask if
2857 // possible. Basically, see if we can optimize:
2861 // [LB op Z, UB op Z]
2863 // If the optimization was successful, accumulate the range in R and
2867 wi_optimize_and_or (irange
&r
,
2868 enum tree_code code
,
2870 const wide_int
&lh_lb
, const wide_int
&lh_ub
,
2871 const wide_int
&rh_lb
, const wide_int
&rh_ub
)
2873 // Calculate the singleton mask among the ranges, if any.
2874 wide_int lower_bound
, upper_bound
, mask
;
2875 if (wi::eq_p (rh_lb
, rh_ub
))
2878 lower_bound
= lh_lb
;
2879 upper_bound
= lh_ub
;
2881 else if (wi::eq_p (lh_lb
, lh_ub
))
2884 lower_bound
= rh_lb
;
2885 upper_bound
= rh_ub
;
2890 // If Z is a constant which (for op | its bitwise not) has n
2891 // consecutive least significant bits cleared followed by m 1
2892 // consecutive bits set immediately above it and either
2893 // m + n == precision, or (x >> (m + n)) == (y >> (m + n)).
2895 // The least significant n bits of all the values in the range are
2896 // cleared or set, the m bits above it are preserved and any bits
2897 // above these are required to be the same for all values in the
2901 if (code
== BIT_IOR_EXPR
)
2903 if (wi::eq_p (w
, 0))
2904 n
= w
.get_precision ();
2908 w
= ~(w
| wi::mask (n
, false, w
.get_precision ()));
2909 if (wi::eq_p (w
, 0))
2910 m
= w
.get_precision () - n
;
2912 m
= wi::ctz (w
) - n
;
2914 wide_int new_mask
= wi::mask (m
+ n
, true, w
.get_precision ());
2915 if ((new_mask
& lower_bound
) != (new_mask
& upper_bound
))
2918 wide_int res_lb
, res_ub
;
2919 if (code
== BIT_AND_EXPR
)
2921 res_lb
= wi::bit_and (lower_bound
, mask
);
2922 res_ub
= wi::bit_and (upper_bound
, mask
);
2924 else if (code
== BIT_IOR_EXPR
)
2926 res_lb
= wi::bit_or (lower_bound
, mask
);
2927 res_ub
= wi::bit_or (upper_bound
, mask
);
2931 value_range_with_overflow (r
, type
, res_lb
, res_ub
);
2933 // Furthermore, if the mask is non-zero, an IOR cannot contain zero.
2934 if (code
== BIT_IOR_EXPR
&& wi::ne_p (mask
, 0))
2937 tmp
.set_nonzero (type
);
2943 // For range [LB, UB] compute two wide_int bit masks.
2945 // In the MAYBE_NONZERO bit mask, if some bit is unset, it means that
2946 // for all numbers in the range the bit is 0, otherwise it might be 0
2949 // In the MUSTBE_NONZERO bit mask, if some bit is set, it means that
2950 // for all numbers in the range the bit is 1, otherwise it might be 0
2954 wi_set_zero_nonzero_bits (tree type
,
2955 const wide_int
&lb
, const wide_int
&ub
,
2956 wide_int
&maybe_nonzero
,
2957 wide_int
&mustbe_nonzero
)
2959 signop sign
= TYPE_SIGN (type
);
2961 if (wi::eq_p (lb
, ub
))
2962 maybe_nonzero
= mustbe_nonzero
= lb
;
2963 else if (wi::ge_p (lb
, 0, sign
) || wi::lt_p (ub
, 0, sign
))
2965 wide_int xor_mask
= lb
^ ub
;
2966 maybe_nonzero
= lb
| ub
;
2967 mustbe_nonzero
= lb
& ub
;
2970 wide_int mask
= wi::mask (wi::floor_log2 (xor_mask
), false,
2971 maybe_nonzero
.get_precision ());
2972 maybe_nonzero
= maybe_nonzero
| mask
;
2973 mustbe_nonzero
= wi::bit_and_not (mustbe_nonzero
, mask
);
2978 maybe_nonzero
= wi::minus_one (lb
.get_precision ());
2979 mustbe_nonzero
= wi::zero (lb
.get_precision ());
2984 operator_bitwise_and::wi_fold (irange
&r
, tree type
,
2985 const wide_int
&lh_lb
,
2986 const wide_int
&lh_ub
,
2987 const wide_int
&rh_lb
,
2988 const wide_int
&rh_ub
) const
2990 if (wi_optimize_and_or (r
, BIT_AND_EXPR
, type
, lh_lb
, lh_ub
, rh_lb
, rh_ub
))
2993 wide_int maybe_nonzero_lh
, mustbe_nonzero_lh
;
2994 wide_int maybe_nonzero_rh
, mustbe_nonzero_rh
;
2995 wi_set_zero_nonzero_bits (type
, lh_lb
, lh_ub
,
2996 maybe_nonzero_lh
, mustbe_nonzero_lh
);
2997 wi_set_zero_nonzero_bits (type
, rh_lb
, rh_ub
,
2998 maybe_nonzero_rh
, mustbe_nonzero_rh
);
3000 wide_int new_lb
= mustbe_nonzero_lh
& mustbe_nonzero_rh
;
3001 wide_int new_ub
= maybe_nonzero_lh
& maybe_nonzero_rh
;
3002 signop sign
= TYPE_SIGN (type
);
3003 unsigned prec
= TYPE_PRECISION (type
);
3004 // If both input ranges contain only negative values, we can
3005 // truncate the result range maximum to the minimum of the
3006 // input range maxima.
3007 if (wi::lt_p (lh_ub
, 0, sign
) && wi::lt_p (rh_ub
, 0, sign
))
3009 new_ub
= wi::min (new_ub
, lh_ub
, sign
);
3010 new_ub
= wi::min (new_ub
, rh_ub
, sign
);
3012 // If either input range contains only non-negative values
3013 // we can truncate the result range maximum to the respective
3014 // maximum of the input range.
3015 if (wi::ge_p (lh_lb
, 0, sign
))
3016 new_ub
= wi::min (new_ub
, lh_ub
, sign
);
3017 if (wi::ge_p (rh_lb
, 0, sign
))
3018 new_ub
= wi::min (new_ub
, rh_ub
, sign
);
3019 // PR68217: In case of signed & sign-bit-CST should
3020 // result in [-INF, 0] instead of [-INF, INF].
3021 if (wi::gt_p (new_lb
, new_ub
, sign
))
3023 wide_int sign_bit
= wi::set_bit_in_zero (prec
- 1, prec
);
3025 && ((wi::eq_p (lh_lb
, lh_ub
)
3026 && !wi::cmps (lh_lb
, sign_bit
))
3027 || (wi::eq_p (rh_lb
, rh_ub
)
3028 && !wi::cmps (rh_lb
, sign_bit
))))
3030 new_lb
= wi::min_value (prec
, sign
);
3031 new_ub
= wi::zero (prec
);
3034 // If the limits got swapped around, return varying.
3035 if (wi::gt_p (new_lb
, new_ub
,sign
))
3038 && wi_optimize_signed_bitwise_op (r
, type
,
3042 r
.set_varying (type
);
3045 value_range_with_overflow (r
, type
, new_lb
, new_ub
);
3049 set_nonzero_range_from_mask (irange
&r
, tree type
, const irange
&lhs
)
3051 if (!lhs
.contains_p (build_zero_cst (type
)))
3052 r
= range_nonzero (type
);
3054 r
.set_varying (type
);
3057 // This was shamelessly stolen from register_edge_assert_for_2 and
3058 // adjusted to work with iranges.
3061 operator_bitwise_and::simple_op1_range_solver (irange
&r
, tree type
,
3063 const irange
&op2
) const
3065 if (!op2
.singleton_p ())
3067 set_nonzero_range_from_mask (r
, type
, lhs
);
3070 unsigned int nprec
= TYPE_PRECISION (type
);
3071 wide_int cst2v
= op2
.lower_bound ();
3072 bool cst2n
= wi::neg_p (cst2v
, TYPE_SIGN (type
));
3075 sgnbit
= wi::set_bit_in_zero (nprec
- 1, nprec
);
3077 sgnbit
= wi::zero (nprec
);
3079 // Solve [lhs.lower_bound (), +INF] = x & MASK.
3081 // Minimum unsigned value for >= if (VAL & CST2) == VAL is VAL and
3082 // maximum unsigned value is ~0. For signed comparison, if CST2
3083 // doesn't have the most significant bit set, handle it similarly. If
3084 // CST2 has MSB set, the minimum is the same, and maximum is ~0U/2.
3085 wide_int valv
= lhs
.lower_bound ();
3086 wide_int minv
= valv
& cst2v
, maxv
;
3087 bool we_know_nothing
= false;
3090 // If (VAL & CST2) != VAL, X & CST2 can't be equal to VAL.
3091 minv
= masked_increment (valv
, cst2v
, sgnbit
, nprec
);
3094 // If we can't determine anything on this bound, fall
3095 // through and conservatively solve for the other end point.
3096 we_know_nothing
= true;
3099 maxv
= wi::mask (nprec
- (cst2n
? 1 : 0), false, nprec
);
3100 if (we_know_nothing
)
3101 r
.set_varying (type
);
3103 r
= int_range
<1> (type
, minv
, maxv
);
3105 // Solve [-INF, lhs.upper_bound ()] = x & MASK.
3107 // Minimum unsigned value for <= is 0 and maximum unsigned value is
3108 // VAL | ~CST2 if (VAL & CST2) == VAL. Otherwise, find smallest
3110 // VAL2 > VAL && (VAL2 & CST2) == VAL2 and use (VAL2 - 1) | ~CST2
3112 // For signed comparison, if CST2 doesn't have most significant bit
3113 // set, handle it similarly. If CST2 has MSB set, the maximum is
3114 // the same and minimum is INT_MIN.
3115 valv
= lhs
.upper_bound ();
3116 minv
= valv
& cst2v
;
3121 maxv
= masked_increment (valv
, cst2v
, sgnbit
, nprec
);
3124 // If we couldn't determine anything on either bound, return
3126 if (we_know_nothing
)
3134 int_range
<1> upper_bits (type
, minv
, maxv
);
3135 r
.intersect (upper_bits
);
3139 operator_bitwise_and::op1_range (irange
&r
, tree type
,
3142 relation_trio
) const
3144 if (lhs
.undefined_p ())
3146 if (types_compatible_p (type
, boolean_type_node
))
3147 return op_logical_and
.op1_range (r
, type
, lhs
, op2
);
3150 for (unsigned i
= 0; i
< lhs
.num_pairs (); ++i
)
3152 int_range_max
chunk (lhs
.type (),
3153 lhs
.lower_bound (i
),
3154 lhs
.upper_bound (i
));
3156 simple_op1_range_solver (res
, type
, chunk
, op2
);
3159 if (r
.undefined_p ())
3160 set_nonzero_range_from_mask (r
, type
, lhs
);
3162 // For 0 = op1 & MASK, op1 is ~MASK.
3163 if (lhs
.zero_p () && op2
.singleton_p ())
3165 wide_int nz
= wi::bit_not (op2
.get_nonzero_bits ());
3166 int_range
<2> tmp (type
);
3167 tmp
.set_nonzero_bits (nz
);
3174 operator_bitwise_and::op2_range (irange
&r
, tree type
,
3177 relation_trio
) const
3179 return operator_bitwise_and::op1_range (r
, type
, lhs
, op1
);
3183 class operator_logical_or
: public range_operator
3185 using range_operator::fold_range
;
3186 using range_operator::op1_range
;
3187 using range_operator::op2_range
;
3189 virtual bool fold_range (irange
&r
, tree type
,
3192 relation_trio rel
= TRIO_VARYING
) const;
3193 virtual bool op1_range (irange
&r
, tree type
,
3196 relation_trio rel
= TRIO_VARYING
) const;
3197 virtual bool op2_range (irange
&r
, tree type
,
3200 relation_trio rel
= TRIO_VARYING
) const;
3204 operator_logical_or::fold_range (irange
&r
, tree type ATTRIBUTE_UNUSED
,
3207 relation_trio
) const
3209 if (empty_range_varying (r
, type
, lh
, rh
))
3218 operator_logical_or::op1_range (irange
&r
, tree type
,
3220 const irange
&op2 ATTRIBUTE_UNUSED
,
3221 relation_trio
) const
3223 switch (get_bool_state (r
, lhs
, type
))
3226 // A false result means both sides of the OR must be false.
3227 r
= range_false (type
);
3230 // Any other result means only one side has to be true, the
3231 // other side can be anything. so we can't be sure of any result
3233 r
= range_true_and_false (type
);
3240 operator_logical_or::op2_range (irange
&r
, tree type
,
3243 relation_trio
) const
3245 return operator_logical_or::op1_range (r
, type
, lhs
, op1
);
3249 class operator_bitwise_or
: public range_operator
3251 using range_operator::op1_range
;
3252 using range_operator::op2_range
;
3254 virtual bool op1_range (irange
&r
, tree type
,
3257 relation_trio rel
= TRIO_VARYING
) const;
3258 virtual bool op2_range (irange
&r
, tree type
,
3261 relation_trio rel
= TRIO_VARYING
) const;
3262 virtual void wi_fold (irange
&r
, tree type
,
3263 const wide_int
&lh_lb
,
3264 const wide_int
&lh_ub
,
3265 const wide_int
&rh_lb
,
3266 const wide_int
&rh_ub
) const;
3270 operator_bitwise_or::wi_fold (irange
&r
, tree type
,
3271 const wide_int
&lh_lb
,
3272 const wide_int
&lh_ub
,
3273 const wide_int
&rh_lb
,
3274 const wide_int
&rh_ub
) const
3276 if (wi_optimize_and_or (r
, BIT_IOR_EXPR
, type
, lh_lb
, lh_ub
, rh_lb
, rh_ub
))
3279 wide_int maybe_nonzero_lh
, mustbe_nonzero_lh
;
3280 wide_int maybe_nonzero_rh
, mustbe_nonzero_rh
;
3281 wi_set_zero_nonzero_bits (type
, lh_lb
, lh_ub
,
3282 maybe_nonzero_lh
, mustbe_nonzero_lh
);
3283 wi_set_zero_nonzero_bits (type
, rh_lb
, rh_ub
,
3284 maybe_nonzero_rh
, mustbe_nonzero_rh
);
3285 wide_int new_lb
= mustbe_nonzero_lh
| mustbe_nonzero_rh
;
3286 wide_int new_ub
= maybe_nonzero_lh
| maybe_nonzero_rh
;
3287 signop sign
= TYPE_SIGN (type
);
3288 // If the input ranges contain only positive values we can
3289 // truncate the minimum of the result range to the maximum
3290 // of the input range minima.
3291 if (wi::ge_p (lh_lb
, 0, sign
)
3292 && wi::ge_p (rh_lb
, 0, sign
))
3294 new_lb
= wi::max (new_lb
, lh_lb
, sign
);
3295 new_lb
= wi::max (new_lb
, rh_lb
, sign
);
3297 // If either input range contains only negative values
3298 // we can truncate the minimum of the result range to the
3299 // respective minimum range.
3300 if (wi::lt_p (lh_ub
, 0, sign
))
3301 new_lb
= wi::max (new_lb
, lh_lb
, sign
);
3302 if (wi::lt_p (rh_ub
, 0, sign
))
3303 new_lb
= wi::max (new_lb
, rh_lb
, sign
);
3304 // If the limits got swapped around, return a conservative range.
3305 if (wi::gt_p (new_lb
, new_ub
, sign
))
3307 // Make sure that nonzero|X is nonzero.
3308 if (wi::gt_p (lh_lb
, 0, sign
)
3309 || wi::gt_p (rh_lb
, 0, sign
)
3310 || wi::lt_p (lh_ub
, 0, sign
)
3311 || wi::lt_p (rh_ub
, 0, sign
))
3312 r
.set_nonzero (type
);
3313 else if (sign
== SIGNED
3314 && wi_optimize_signed_bitwise_op (r
, type
,
3319 r
.set_varying (type
);
3322 value_range_with_overflow (r
, type
, new_lb
, new_ub
);
3326 operator_bitwise_or::op1_range (irange
&r
, tree type
,
3329 relation_trio
) const
3331 if (lhs
.undefined_p ())
3333 // If this is really a logical wi_fold, call that.
3334 if (types_compatible_p (type
, boolean_type_node
))
3335 return op_logical_or
.op1_range (r
, type
, lhs
, op2
);
3339 tree zero
= build_zero_cst (type
);
3340 r
= int_range
<1> (zero
, zero
);
3343 r
.set_varying (type
);
3348 operator_bitwise_or::op2_range (irange
&r
, tree type
,
3351 relation_trio
) const
3353 return operator_bitwise_or::op1_range (r
, type
, lhs
, op1
);
3357 class operator_bitwise_xor
: public range_operator
3359 using range_operator::op1_range
;
3360 using range_operator::op2_range
;
3362 virtual void wi_fold (irange
&r
, tree type
,
3363 const wide_int
&lh_lb
,
3364 const wide_int
&lh_ub
,
3365 const wide_int
&rh_lb
,
3366 const wide_int
&rh_ub
) const;
3367 virtual bool op1_range (irange
&r
, tree type
,
3370 relation_trio rel
= TRIO_VARYING
) const;
3371 virtual bool op2_range (irange
&r
, tree type
,
3374 relation_trio rel
= TRIO_VARYING
) const;
3375 virtual bool op1_op2_relation_effect (irange
&lhs_range
,
3377 const irange
&op1_range
,
3378 const irange
&op2_range
,
3379 relation_kind rel
) const;
3383 operator_bitwise_xor::wi_fold (irange
&r
, tree type
,
3384 const wide_int
&lh_lb
,
3385 const wide_int
&lh_ub
,
3386 const wide_int
&rh_lb
,
3387 const wide_int
&rh_ub
) const
3389 signop sign
= TYPE_SIGN (type
);
3390 wide_int maybe_nonzero_lh
, mustbe_nonzero_lh
;
3391 wide_int maybe_nonzero_rh
, mustbe_nonzero_rh
;
3392 wi_set_zero_nonzero_bits (type
, lh_lb
, lh_ub
,
3393 maybe_nonzero_lh
, mustbe_nonzero_lh
);
3394 wi_set_zero_nonzero_bits (type
, rh_lb
, rh_ub
,
3395 maybe_nonzero_rh
, mustbe_nonzero_rh
);
3397 wide_int result_zero_bits
= ((mustbe_nonzero_lh
& mustbe_nonzero_rh
)
3398 | ~(maybe_nonzero_lh
| maybe_nonzero_rh
));
3399 wide_int result_one_bits
3400 = (wi::bit_and_not (mustbe_nonzero_lh
, maybe_nonzero_rh
)
3401 | wi::bit_and_not (mustbe_nonzero_rh
, maybe_nonzero_lh
));
3402 wide_int new_ub
= ~result_zero_bits
;
3403 wide_int new_lb
= result_one_bits
;
3405 // If the range has all positive or all negative values, the result
3406 // is better than VARYING.
3407 if (wi::lt_p (new_lb
, 0, sign
) || wi::ge_p (new_ub
, 0, sign
))
3408 value_range_with_overflow (r
, type
, new_lb
, new_ub
);
3409 else if (sign
== SIGNED
3410 && wi_optimize_signed_bitwise_op (r
, type
,
3415 r
.set_varying (type
);
3417 /* Furthermore, XOR is non-zero if its arguments can't be equal. */
3418 if (wi::lt_p (lh_ub
, rh_lb
, sign
)
3419 || wi::lt_p (rh_ub
, lh_lb
, sign
)
3420 || wi::ne_p (result_one_bits
, 0))
3423 tmp
.set_nonzero (type
);
3429 operator_bitwise_xor::op1_op2_relation_effect (irange
&lhs_range
,
3433 relation_kind rel
) const
3435 if (rel
== VREL_VARYING
)
3438 int_range
<2> rel_range
;
3443 rel_range
.set_zero (type
);
3446 rel_range
.set_nonzero (type
);
3452 lhs_range
.intersect (rel_range
);
3457 operator_bitwise_xor::op1_range (irange
&r
, tree type
,
3460 relation_trio
) const
3462 if (lhs
.undefined_p () || lhs
.varying_p ())
3467 if (types_compatible_p (type
, boolean_type_node
))
3469 switch (get_bool_state (r
, lhs
, type
))
3472 if (op2
.varying_p ())
3473 r
.set_varying (type
);
3474 else if (op2
.zero_p ())
3475 r
= range_true (type
);
3477 r
= range_false (type
);
3487 r
.set_varying (type
);
3492 operator_bitwise_xor::op2_range (irange
&r
, tree type
,
3495 relation_trio
) const
3497 return operator_bitwise_xor::op1_range (r
, type
, lhs
, op1
);
3500 class operator_trunc_mod
: public range_operator
3502 using range_operator::op1_range
;
3503 using range_operator::op2_range
;
3505 virtual void wi_fold (irange
&r
, tree type
,
3506 const wide_int
&lh_lb
,
3507 const wide_int
&lh_ub
,
3508 const wide_int
&rh_lb
,
3509 const wide_int
&rh_ub
) const;
3510 virtual bool op1_range (irange
&r
, tree type
,
3513 relation_trio
) const;
3514 virtual bool op2_range (irange
&r
, tree type
,
3517 relation_trio
) const;
3521 operator_trunc_mod::wi_fold (irange
&r
, tree type
,
3522 const wide_int
&lh_lb
,
3523 const wide_int
&lh_ub
,
3524 const wide_int
&rh_lb
,
3525 const wide_int
&rh_ub
) const
3527 wide_int new_lb
, new_ub
, tmp
;
3528 signop sign
= TYPE_SIGN (type
);
3529 unsigned prec
= TYPE_PRECISION (type
);
3531 // Mod 0 is undefined.
3532 if (wi_zero_p (type
, rh_lb
, rh_ub
))
3538 // Check for constant and try to fold.
3539 if (lh_lb
== lh_ub
&& rh_lb
== rh_ub
)
3541 wi::overflow_type ov
= wi::OVF_NONE
;
3542 tmp
= wi::mod_trunc (lh_lb
, rh_lb
, sign
, &ov
);
3543 if (ov
== wi::OVF_NONE
)
3545 r
= int_range
<2> (type
, tmp
, tmp
);
3550 // ABS (A % B) < ABS (B) and either 0 <= A % B <= A or A <= A % B <= 0.
3555 new_ub
= wi::smax (new_ub
, tmp
);
3558 if (sign
== UNSIGNED
)
3559 new_lb
= wi::zero (prec
);
3564 if (wi::gts_p (tmp
, 0))
3565 tmp
= wi::zero (prec
);
3566 new_lb
= wi::smax (new_lb
, tmp
);
3569 if (sign
== SIGNED
&& wi::neg_p (tmp
))
3570 tmp
= wi::zero (prec
);
3571 new_ub
= wi::min (new_ub
, tmp
, sign
);
3573 value_range_with_overflow (r
, type
, new_lb
, new_ub
);
3577 operator_trunc_mod::op1_range (irange
&r
, tree type
,
3580 relation_trio
) const
3582 if (lhs
.undefined_p ())
3585 signop sign
= TYPE_SIGN (type
);
3586 unsigned prec
= TYPE_PRECISION (type
);
3587 // (a % b) >= x && x > 0 , then a >= x.
3588 if (wi::gt_p (lhs
.lower_bound (), 0, sign
))
3590 r
= value_range (type
, lhs
.lower_bound (), wi::max_value (prec
, sign
));
3593 // (a % b) <= x && x < 0 , then a <= x.
3594 if (wi::lt_p (lhs
.upper_bound (), 0, sign
))
3596 r
= value_range (type
, wi::min_value (prec
, sign
), lhs
.upper_bound ());
3603 operator_trunc_mod::op2_range (irange
&r
, tree type
,
3606 relation_trio
) const
3608 if (lhs
.undefined_p ())
3611 signop sign
= TYPE_SIGN (type
);
3612 unsigned prec
= TYPE_PRECISION (type
);
3613 // (a % b) >= x && x > 0 , then b is in ~[-x, x] for signed
3614 // or b > x for unsigned.
3615 if (wi::gt_p (lhs
.lower_bound (), 0, sign
))
3618 r
= value_range (type
, wi::neg (lhs
.lower_bound ()),
3619 lhs
.lower_bound (), VR_ANTI_RANGE
);
3620 else if (wi::lt_p (lhs
.lower_bound (), wi::max_value (prec
, sign
),
3622 r
= value_range (type
, lhs
.lower_bound () + 1,
3623 wi::max_value (prec
, sign
));
3628 // (a % b) <= x && x < 0 , then b is in ~[x, -x].
3629 if (wi::lt_p (lhs
.upper_bound (), 0, sign
))
3631 if (wi::gt_p (lhs
.upper_bound (), wi::min_value (prec
, sign
), sign
))
3632 r
= value_range (type
, lhs
.upper_bound (),
3633 wi::neg (lhs
.upper_bound ()), VR_ANTI_RANGE
);
3642 class operator_logical_not
: public range_operator
3644 using range_operator::fold_range
;
3645 using range_operator::op1_range
;
3647 virtual bool fold_range (irange
&r
, tree type
,
3650 relation_trio rel
= TRIO_VARYING
) const;
3651 virtual bool op1_range (irange
&r
, tree type
,
3654 relation_trio rel
= TRIO_VARYING
) const;
3657 // Folding a logical NOT, oddly enough, involves doing nothing on the
3658 // forward pass through. During the initial walk backwards, the
3659 // logical NOT reversed the desired outcome on the way back, so on the
3660 // way forward all we do is pass the range forward.
3665 // to determine the TRUE branch, walking backward
3666 // if (b_3) if ([1,1])
3667 // b_3 = !b_2 [1,1] = ![0,0]
3668 // b_2 = x_1 < 20 [0,0] = x_1 < 20, false, so x_1 == [20, 255]
3669 // which is the result we are looking for.. so.. pass it through.
3672 operator_logical_not::fold_range (irange
&r
, tree type
,
3674 const irange
&rh ATTRIBUTE_UNUSED
,
3675 relation_trio
) const
3677 if (empty_range_varying (r
, type
, lh
, rh
))
3681 if (!lh
.varying_p () && !lh
.undefined_p ())
3688 operator_logical_not::op1_range (irange
&r
,
3692 relation_trio
) const
3694 // Logical NOT is involutary...do it again.
3695 return fold_range (r
, type
, lhs
, op2
);
3699 class operator_bitwise_not
: public range_operator
3701 using range_operator::fold_range
;
3702 using range_operator::op1_range
;
3704 virtual bool fold_range (irange
&r
, tree type
,
3707 relation_trio rel
= TRIO_VARYING
) const;
3708 virtual bool op1_range (irange
&r
, tree type
,
3711 relation_trio rel
= TRIO_VARYING
) const;
3715 operator_bitwise_not::fold_range (irange
&r
, tree type
,
3718 relation_trio
) const
3720 if (empty_range_varying (r
, type
, lh
, rh
))
3723 if (types_compatible_p (type
, boolean_type_node
))
3724 return op_logical_not
.fold_range (r
, type
, lh
, rh
);
3726 // ~X is simply -1 - X.
3727 int_range
<1> minusone (type
, wi::minus_one (TYPE_PRECISION (type
)),
3728 wi::minus_one (TYPE_PRECISION (type
)));
3729 return range_op_handler (MINUS_EXPR
, type
).fold_range (r
, type
, minusone
, lh
);
3733 operator_bitwise_not::op1_range (irange
&r
, tree type
,
3736 relation_trio
) const
3738 if (lhs
.undefined_p ())
3740 if (types_compatible_p (type
, boolean_type_node
))
3741 return op_logical_not
.op1_range (r
, type
, lhs
, op2
);
3743 // ~X is -1 - X and since bitwise NOT is involutary...do it again.
3744 return fold_range (r
, type
, lhs
, op2
);
3748 class operator_cst
: public range_operator
3750 using range_operator::fold_range
;
3752 virtual bool fold_range (irange
&r
, tree type
,
3755 relation_trio rel
= TRIO_VARYING
) const;
3759 operator_cst::fold_range (irange
&r
, tree type ATTRIBUTE_UNUSED
,
3761 const irange
&rh ATTRIBUTE_UNUSED
,
3762 relation_trio
) const
3769 class operator_identity
: public range_operator
3771 using range_operator::fold_range
;
3772 using range_operator::op1_range
;
3773 using range_operator::lhs_op1_relation
;
3775 virtual bool fold_range (irange
&r
, tree type
,
3778 relation_trio rel
= TRIO_VARYING
) const;
3779 virtual bool op1_range (irange
&r
, tree type
,
3782 relation_trio rel
= TRIO_VARYING
) const;
3783 virtual relation_kind
lhs_op1_relation (const irange
&lhs
,
3786 relation_kind rel
) const;
3789 // Determine if there is a relationship between LHS and OP1.
3792 operator_identity::lhs_op1_relation (const irange
&lhs
,
3793 const irange
&op1 ATTRIBUTE_UNUSED
,
3794 const irange
&op2 ATTRIBUTE_UNUSED
,
3795 relation_kind
) const
3797 if (lhs
.undefined_p ())
3798 return VREL_VARYING
;
3799 // Simply a copy, so they are equivalent.
3804 operator_identity::fold_range (irange
&r
, tree type ATTRIBUTE_UNUSED
,
3806 const irange
&rh ATTRIBUTE_UNUSED
,
3807 relation_trio
) const
3814 operator_identity::op1_range (irange
&r
, tree type ATTRIBUTE_UNUSED
,
3816 const irange
&op2 ATTRIBUTE_UNUSED
,
3817 relation_trio
) const
3824 class operator_unknown
: public range_operator
3826 using range_operator::fold_range
;
3828 virtual bool fold_range (irange
&r
, tree type
,
3831 relation_trio rel
= TRIO_VARYING
) const;
3835 operator_unknown::fold_range (irange
&r
, tree type
,
3836 const irange
&lh ATTRIBUTE_UNUSED
,
3837 const irange
&rh ATTRIBUTE_UNUSED
,
3838 relation_trio
) const
3840 r
.set_varying (type
);
3845 class operator_abs
: public range_operator
3847 using range_operator::op1_range
;
3849 virtual void wi_fold (irange
&r
, tree type
,
3850 const wide_int
&lh_lb
,
3851 const wide_int
&lh_ub
,
3852 const wide_int
&rh_lb
,
3853 const wide_int
&rh_ub
) const;
3854 virtual bool op1_range (irange
&r
, tree type
,
3857 relation_trio
) const;
3861 operator_abs::wi_fold (irange
&r
, tree type
,
3862 const wide_int
&lh_lb
, const wide_int
&lh_ub
,
3863 const wide_int
&rh_lb ATTRIBUTE_UNUSED
,
3864 const wide_int
&rh_ub ATTRIBUTE_UNUSED
) const
3867 signop sign
= TYPE_SIGN (type
);
3868 unsigned prec
= TYPE_PRECISION (type
);
3870 // Pass through LH for the easy cases.
3871 if (sign
== UNSIGNED
|| wi::ge_p (lh_lb
, 0, sign
))
3873 r
= int_range
<1> (type
, lh_lb
, lh_ub
);
3877 // -TYPE_MIN_VALUE = TYPE_MIN_VALUE with flag_wrapv so we can't get
3879 wide_int min_value
= wi::min_value (prec
, sign
);
3880 wide_int max_value
= wi::max_value (prec
, sign
);
3881 if (!TYPE_OVERFLOW_UNDEFINED (type
) && wi::eq_p (lh_lb
, min_value
))
3883 r
.set_varying (type
);
3887 // ABS_EXPR may flip the range around, if the original range
3888 // included negative values.
3889 if (wi::eq_p (lh_lb
, min_value
))
3891 // ABS ([-MIN, -MIN]) isn't representable, but we have traditionally
3892 // returned [-MIN,-MIN] so this preserves that behaviour. PR37078
3893 if (wi::eq_p (lh_ub
, min_value
))
3895 r
= int_range
<1> (type
, min_value
, min_value
);
3901 min
= wi::abs (lh_lb
);
3903 if (wi::eq_p (lh_ub
, min_value
))
3906 max
= wi::abs (lh_ub
);
3908 // If the range contains zero then we know that the minimum value in the
3909 // range will be zero.
3910 if (wi::le_p (lh_lb
, 0, sign
) && wi::ge_p (lh_ub
, 0, sign
))
3912 if (wi::gt_p (min
, max
, sign
))
3914 min
= wi::zero (prec
);
3918 // If the range was reversed, swap MIN and MAX.
3919 if (wi::gt_p (min
, max
, sign
))
3920 std::swap (min
, max
);
3923 // If the new range has its limits swapped around (MIN > MAX), then
3924 // the operation caused one of them to wrap around. The only thing
3925 // we know is that the result is positive.
3926 if (wi::gt_p (min
, max
, sign
))
3928 min
= wi::zero (prec
);
3931 r
= int_range
<1> (type
, min
, max
);
3935 operator_abs::op1_range (irange
&r
, tree type
,
3938 relation_trio
) const
3940 if (empty_range_varying (r
, type
, lhs
, op2
))
3942 if (TYPE_UNSIGNED (type
))
3947 // Start with the positives because negatives are an impossible result.
3948 int_range_max positives
= range_positives (type
);
3949 positives
.intersect (lhs
);
3951 // Then add the negative of each pair:
3952 // ABS(op1) = [5,20] would yield op1 => [-20,-5][5,20].
3953 for (unsigned i
= 0; i
< positives
.num_pairs (); ++i
)
3954 r
.union_ (int_range
<1> (type
,
3955 -positives
.upper_bound (i
),
3956 -positives
.lower_bound (i
)));
3957 // With flag_wrapv, -TYPE_MIN_VALUE = TYPE_MIN_VALUE which is
3958 // unrepresentable. Add -TYPE_MIN_VALUE in this case.
3959 wide_int min_value
= wi::min_value (TYPE_PRECISION (type
), TYPE_SIGN (type
));
3960 wide_int lb
= lhs
.lower_bound ();
3961 if (!TYPE_OVERFLOW_UNDEFINED (type
) && wi::eq_p (lb
, min_value
))
3962 r
.union_ (int_range
<2> (type
, lb
, lb
));
3967 class operator_absu
: public range_operator
3970 virtual void wi_fold (irange
&r
, tree type
,
3971 const wide_int
&lh_lb
, const wide_int
&lh_ub
,
3972 const wide_int
&rh_lb
, const wide_int
&rh_ub
) const;
3976 operator_absu::wi_fold (irange
&r
, tree type
,
3977 const wide_int
&lh_lb
, const wide_int
&lh_ub
,
3978 const wide_int
&rh_lb ATTRIBUTE_UNUSED
,
3979 const wide_int
&rh_ub ATTRIBUTE_UNUSED
) const
3981 wide_int new_lb
, new_ub
;
3983 // Pass through VR0 the easy cases.
3984 if (wi::ges_p (lh_lb
, 0))
3991 new_lb
= wi::abs (lh_lb
);
3992 new_ub
= wi::abs (lh_ub
);
3994 // If the range contains zero then we know that the minimum
3995 // value in the range will be zero.
3996 if (wi::ges_p (lh_ub
, 0))
3998 if (wi::gtu_p (new_lb
, new_ub
))
4000 new_lb
= wi::zero (TYPE_PRECISION (type
));
4003 std::swap (new_lb
, new_ub
);
4006 gcc_checking_assert (TYPE_UNSIGNED (type
));
4007 r
= int_range
<1> (type
, new_lb
, new_ub
);
4011 class operator_negate
: public range_operator
4013 using range_operator::fold_range
;
4014 using range_operator::op1_range
;
4016 virtual bool fold_range (irange
&r
, tree type
,
4019 relation_trio rel
= TRIO_VARYING
) const;
4020 virtual bool op1_range (irange
&r
, tree type
,
4023 relation_trio rel
= TRIO_VARYING
) const;
4027 operator_negate::fold_range (irange
&r
, tree type
,
4030 relation_trio
) const
4032 if (empty_range_varying (r
, type
, lh
, rh
))
4034 // -X is simply 0 - X.
4035 return range_op_handler (MINUS_EXPR
, type
).fold_range (r
, type
,
4036 range_zero (type
), lh
);
4040 operator_negate::op1_range (irange
&r
, tree type
,
4043 relation_trio
) const
4045 // NEGATE is involutory.
4046 return fold_range (r
, type
, lhs
, op2
);
4050 class operator_addr_expr
: public range_operator
4052 using range_operator::fold_range
;
4053 using range_operator::op1_range
;
4055 virtual bool fold_range (irange
&r
, tree type
,
4058 relation_trio rel
= TRIO_VARYING
) const;
4059 virtual bool op1_range (irange
&r
, tree type
,
4062 relation_trio rel
= TRIO_VARYING
) const;
4066 operator_addr_expr::fold_range (irange
&r
, tree type
,
4069 relation_trio
) const
4071 if (empty_range_varying (r
, type
, lh
, rh
))
4074 // Return a non-null pointer of the LHS type (passed in op2).
4076 r
= range_zero (type
);
4077 else if (!lh
.contains_p (build_zero_cst (lh
.type ())))
4078 r
= range_nonzero (type
);
4080 r
.set_varying (type
);
4085 operator_addr_expr::op1_range (irange
&r
, tree type
,
4088 relation_trio
) const
4090 return operator_addr_expr::fold_range (r
, type
, lhs
, op2
);
4094 class pointer_plus_operator
: public range_operator
4097 virtual void wi_fold (irange
&r
, tree type
,
4098 const wide_int
&lh_lb
,
4099 const wide_int
&lh_ub
,
4100 const wide_int
&rh_lb
,
4101 const wide_int
&rh_ub
) const;
4105 pointer_plus_operator::wi_fold (irange
&r
, tree type
,
4106 const wide_int
&lh_lb
,
4107 const wide_int
&lh_ub
,
4108 const wide_int
&rh_lb
,
4109 const wide_int
&rh_ub
) const
4111 // Check for [0,0] + const, and simply return the const.
4112 if (lh_lb
== 0 && lh_ub
== 0 && rh_lb
== rh_ub
)
4114 tree val
= wide_int_to_tree (type
, rh_lb
);
4119 // For pointer types, we are really only interested in asserting
4120 // whether the expression evaluates to non-NULL.
4122 // With -fno-delete-null-pointer-checks we need to be more
4123 // conservative. As some object might reside at address 0,
4124 // then some offset could be added to it and the same offset
4125 // subtracted again and the result would be NULL.
4127 // static int a[12]; where &a[0] is NULL and
4130 // ptr will be NULL here, even when there is POINTER_PLUS_EXPR
4131 // where the first range doesn't include zero and the second one
4132 // doesn't either. As the second operand is sizetype (unsigned),
4133 // consider all ranges where the MSB could be set as possible
4134 // subtractions where the result might be NULL.
4135 if ((!wi_includes_zero_p (type
, lh_lb
, lh_ub
)
4136 || !wi_includes_zero_p (type
, rh_lb
, rh_ub
))
4137 && !TYPE_OVERFLOW_WRAPS (type
)
4138 && (flag_delete_null_pointer_checks
4139 || !wi::sign_mask (rh_ub
)))
4140 r
= range_nonzero (type
);
4141 else if (lh_lb
== lh_ub
&& lh_lb
== 0
4142 && rh_lb
== rh_ub
&& rh_lb
== 0)
4143 r
= range_zero (type
);
4145 r
.set_varying (type
);
4149 class pointer_min_max_operator
: public range_operator
4152 virtual void wi_fold (irange
& r
, tree type
,
4153 const wide_int
&lh_lb
, const wide_int
&lh_ub
,
4154 const wide_int
&rh_lb
, const wide_int
&rh_ub
) const;
4158 pointer_min_max_operator::wi_fold (irange
&r
, tree type
,
4159 const wide_int
&lh_lb
,
4160 const wide_int
&lh_ub
,
4161 const wide_int
&rh_lb
,
4162 const wide_int
&rh_ub
) const
4164 // For MIN/MAX expressions with pointers, we only care about
4165 // nullness. If both are non null, then the result is nonnull.
4166 // If both are null, then the result is null. Otherwise they
4168 if (!wi_includes_zero_p (type
, lh_lb
, lh_ub
)
4169 && !wi_includes_zero_p (type
, rh_lb
, rh_ub
))
4170 r
= range_nonzero (type
);
4171 else if (wi_zero_p (type
, lh_lb
, lh_ub
) && wi_zero_p (type
, rh_lb
, rh_ub
))
4172 r
= range_zero (type
);
4174 r
.set_varying (type
);
4178 class pointer_and_operator
: public range_operator
4181 virtual void wi_fold (irange
&r
, tree type
,
4182 const wide_int
&lh_lb
, const wide_int
&lh_ub
,
4183 const wide_int
&rh_lb
, const wide_int
&rh_ub
) const;
4187 pointer_and_operator::wi_fold (irange
&r
, tree type
,
4188 const wide_int
&lh_lb
,
4189 const wide_int
&lh_ub
,
4190 const wide_int
&rh_lb ATTRIBUTE_UNUSED
,
4191 const wide_int
&rh_ub ATTRIBUTE_UNUSED
) const
4193 // For pointer types, we are really only interested in asserting
4194 // whether the expression evaluates to non-NULL.
4195 if (wi_zero_p (type
, lh_lb
, lh_ub
) || wi_zero_p (type
, lh_lb
, lh_ub
))
4196 r
= range_zero (type
);
4198 r
.set_varying (type
);
4202 class pointer_or_operator
: public range_operator
4204 using range_operator::op1_range
;
4205 using range_operator::op2_range
;
4207 virtual bool op1_range (irange
&r
, tree type
,
4210 relation_trio rel
= TRIO_VARYING
) const;
4211 virtual bool op2_range (irange
&r
, tree type
,
4214 relation_trio rel
= TRIO_VARYING
) const;
4215 virtual void wi_fold (irange
&r
, tree type
,
4216 const wide_int
&lh_lb
, const wide_int
&lh_ub
,
4217 const wide_int
&rh_lb
, const wide_int
&rh_ub
) const;
4221 pointer_or_operator::op1_range (irange
&r
, tree type
,
4223 const irange
&op2 ATTRIBUTE_UNUSED
,
4224 relation_trio
) const
4226 if (lhs
.undefined_p ())
4230 tree zero
= build_zero_cst (type
);
4231 r
= int_range
<1> (zero
, zero
);
4234 r
.set_varying (type
);
4239 pointer_or_operator::op2_range (irange
&r
, tree type
,
4242 relation_trio
) const
4244 return pointer_or_operator::op1_range (r
, type
, lhs
, op1
);
4248 pointer_or_operator::wi_fold (irange
&r
, tree type
,
4249 const wide_int
&lh_lb
,
4250 const wide_int
&lh_ub
,
4251 const wide_int
&rh_lb
,
4252 const wide_int
&rh_ub
) const
4254 // For pointer types, we are really only interested in asserting
4255 // whether the expression evaluates to non-NULL.
4256 if (!wi_includes_zero_p (type
, lh_lb
, lh_ub
)
4257 && !wi_includes_zero_p (type
, rh_lb
, rh_ub
))
4258 r
= range_nonzero (type
);
4259 else if (wi_zero_p (type
, lh_lb
, lh_ub
) && wi_zero_p (type
, rh_lb
, rh_ub
))
4260 r
= range_zero (type
);
4262 r
.set_varying (type
);
4265 // Return a pointer to the range_operator instance, if there is one
4266 // associated with tree_code CODE.
4269 range_op_table::operator[] (enum tree_code code
)
4271 gcc_checking_assert (code
> 0 && code
< MAX_TREE_CODES
);
4272 return m_range_tree
[code
];
4275 // Add OP to the handler table for CODE.
4278 range_op_table::set (enum tree_code code
, range_operator
&op
)
4280 gcc_checking_assert (m_range_tree
[code
] == NULL
);
4281 m_range_tree
[code
] = &op
;
4284 // Instantiate a range op table for integral operations.
4286 class integral_table
: public range_op_table
4290 } integral_tree_table
;
4292 integral_table::integral_table ()
4294 set (EQ_EXPR
, op_equal
);
4295 set (NE_EXPR
, op_not_equal
);
4296 set (LT_EXPR
, op_lt
);
4297 set (LE_EXPR
, op_le
);
4298 set (GT_EXPR
, op_gt
);
4299 set (GE_EXPR
, op_ge
);
4300 set (PLUS_EXPR
, op_plus
);
4301 set (MINUS_EXPR
, op_minus
);
4302 set (MIN_EXPR
, op_min
);
4303 set (MAX_EXPR
, op_max
);
4304 set (MULT_EXPR
, op_mult
);
4305 set (TRUNC_DIV_EXPR
, op_trunc_div
);
4306 set (FLOOR_DIV_EXPR
, op_floor_div
);
4307 set (ROUND_DIV_EXPR
, op_round_div
);
4308 set (CEIL_DIV_EXPR
, op_ceil_div
);
4309 set (EXACT_DIV_EXPR
, op_exact_div
);
4310 set (LSHIFT_EXPR
, op_lshift
);
4311 set (RSHIFT_EXPR
, op_rshift
);
4312 set (NOP_EXPR
, op_convert
);
4313 set (CONVERT_EXPR
, op_convert
);
4314 set (TRUTH_AND_EXPR
, op_logical_and
);
4315 set (BIT_AND_EXPR
, op_bitwise_and
);
4316 set (TRUTH_OR_EXPR
, op_logical_or
);
4317 set (BIT_IOR_EXPR
, op_bitwise_or
);
4318 set (BIT_XOR_EXPR
, op_bitwise_xor
);
4319 set (TRUNC_MOD_EXPR
, op_trunc_mod
);
4320 set (TRUTH_NOT_EXPR
, op_logical_not
);
4321 set (BIT_NOT_EXPR
, op_bitwise_not
);
4322 set (INTEGER_CST
, op_integer_cst
);
4323 set (SSA_NAME
, op_identity
);
4324 set (PAREN_EXPR
, op_identity
);
4325 set (OBJ_TYPE_REF
, op_identity
);
4326 set (IMAGPART_EXPR
, op_unknown
);
4327 set (REALPART_EXPR
, op_unknown
);
4328 set (POINTER_DIFF_EXPR
, op_pointer_diff
);
4329 set (ABS_EXPR
, op_abs
);
4330 set (ABSU_EXPR
, op_absu
);
4331 set (NEGATE_EXPR
, op_negate
);
4332 set (ADDR_EXPR
, op_addr
);
4335 // Instantiate a range op table for pointer operations.
4337 class pointer_table
: public range_op_table
4341 } pointer_tree_table
;
4343 pointer_table::pointer_table ()
4345 set (BIT_AND_EXPR
, op_pointer_and
);
4346 set (BIT_IOR_EXPR
, op_pointer_or
);
4347 set (MIN_EXPR
, op_ptr_min_max
);
4348 set (MAX_EXPR
, op_ptr_min_max
);
4349 set (POINTER_PLUS_EXPR
, op_pointer_plus
);
4351 set (EQ_EXPR
, op_equal
);
4352 set (NE_EXPR
, op_not_equal
);
4353 set (LT_EXPR
, op_lt
);
4354 set (LE_EXPR
, op_le
);
4355 set (GT_EXPR
, op_gt
);
4356 set (GE_EXPR
, op_ge
);
4357 set (SSA_NAME
, op_identity
);
4358 set (INTEGER_CST
, op_integer_cst
);
4359 set (ADDR_EXPR
, op_addr
);
4360 set (NOP_EXPR
, op_convert
);
4361 set (CONVERT_EXPR
, op_convert
);
4363 set (BIT_NOT_EXPR
, op_bitwise_not
);
4364 set (BIT_XOR_EXPR
, op_bitwise_xor
);
4367 // The tables are hidden and accessed via a simple extern function.
4369 static inline range_operator
*
4370 get_handler (enum tree_code code
, tree type
)
4372 // First check if there is a pointer specialization.
4373 if (POINTER_TYPE_P (type
))
4374 return pointer_tree_table
[code
];
4375 if (INTEGRAL_TYPE_P (type
))
4376 return integral_tree_table
[code
];
4380 // Return the floating point operator for CODE or NULL if none available.
4382 static inline range_operator_float
*
4383 get_float_handler (enum tree_code code
, tree
)
4385 return (*floating_tree_table
)[code
];
4389 range_op_handler::set_op_handler (tree_code code
, tree type
)
4391 if (irange::supports_p (type
))
4394 m_int
= get_handler (code
, type
);
4395 m_valid
= m_int
!= NULL
;
4397 else if (frange::supports_p (type
))
4400 m_float
= get_float_handler (code
, type
);
4401 m_valid
= m_float
!= NULL
;
4411 range_op_handler::range_op_handler ()
4418 range_op_handler::range_op_handler (tree_code code
, tree type
)
4420 set_op_handler (code
, type
);
4425 range_op_handler::fold_range (vrange
&r
, tree type
,
4428 relation_trio rel
) const
4430 gcc_checking_assert (m_valid
);
4432 return m_int
->fold_range (as_a
<irange
> (r
), type
,
4434 as_a
<irange
> (rh
), rel
);
4436 if (is_a
<irange
> (r
))
4438 if (is_a
<irange
> (rh
))
4439 return m_float
->fold_range (as_a
<irange
> (r
), type
,
4441 as_a
<irange
> (rh
), rel
);
4443 return m_float
->fold_range (as_a
<irange
> (r
), type
,
4445 as_a
<frange
> (rh
), rel
);
4447 return m_float
->fold_range (as_a
<frange
> (r
), type
,
4449 as_a
<frange
> (rh
), rel
);
4453 range_op_handler::op1_range (vrange
&r
, tree type
,
4456 relation_trio rel
) const
4458 gcc_checking_assert (m_valid
);
4460 if (lhs
.undefined_p ())
4463 return m_int
->op1_range (as_a
<irange
> (r
), type
,
4464 as_a
<irange
> (lhs
),
4465 as_a
<irange
> (op2
), rel
);
4467 if (is_a
<irange
> (lhs
))
4468 return m_float
->op1_range (as_a
<frange
> (r
), type
,
4469 as_a
<irange
> (lhs
),
4470 as_a
<frange
> (op2
), rel
);
4471 return m_float
->op1_range (as_a
<frange
> (r
), type
,
4472 as_a
<frange
> (lhs
),
4473 as_a
<frange
> (op2
), rel
);
4477 range_op_handler::op2_range (vrange
&r
, tree type
,
4480 relation_trio rel
) const
4482 gcc_checking_assert (m_valid
);
4483 if (lhs
.undefined_p ())
4486 return m_int
->op2_range (as_a
<irange
> (r
), type
,
4487 as_a
<irange
> (lhs
),
4488 as_a
<irange
> (op1
), rel
);
4490 if (is_a
<irange
> (lhs
))
4491 return m_float
->op2_range (as_a
<frange
> (r
), type
,
4492 as_a
<irange
> (lhs
),
4493 as_a
<frange
> (op1
), rel
);
4494 return m_float
->op2_range (as_a
<frange
> (r
), type
,
4495 as_a
<frange
> (lhs
),
4496 as_a
<frange
> (op1
), rel
);
4500 range_op_handler::lhs_op1_relation (const vrange
&lhs
,
4503 relation_kind rel
) const
4505 gcc_checking_assert (m_valid
);
4507 return m_int
->lhs_op1_relation (as_a
<irange
> (lhs
),
4508 as_a
<irange
> (op1
),
4509 as_a
<irange
> (op2
), rel
);
4511 if (is_a
<irange
> (lhs
))
4512 return m_float
->lhs_op1_relation (as_a
<irange
> (lhs
),
4513 as_a
<frange
> (op1
),
4514 as_a
<frange
> (op2
), rel
);
4515 return m_float
->lhs_op1_relation (as_a
<frange
> (lhs
),
4516 as_a
<frange
> (op1
),
4517 as_a
<frange
> (op2
), rel
);
4521 range_op_handler::lhs_op2_relation (const vrange
&lhs
,
4524 relation_kind rel
) const
4526 gcc_checking_assert (m_valid
);
4528 return m_int
->lhs_op2_relation (as_a
<irange
> (lhs
),
4529 as_a
<irange
> (op1
),
4530 as_a
<irange
> (op2
), rel
);
4532 if (is_a
<irange
> (lhs
))
4533 return m_float
->lhs_op2_relation (as_a
<irange
> (lhs
),
4534 as_a
<frange
> (op1
),
4535 as_a
<frange
> (op2
), rel
);
4536 return m_float
->lhs_op2_relation (as_a
<frange
> (lhs
),
4537 as_a
<frange
> (op1
),
4538 as_a
<frange
> (op2
), rel
);
4542 range_op_handler::op1_op2_relation (const vrange
&lhs
) const
4544 gcc_checking_assert (m_valid
);
4546 return m_int
->op1_op2_relation (as_a
<irange
> (lhs
));
4547 if (is_a
<irange
> (lhs
))
4548 return m_float
->op1_op2_relation (as_a
<irange
> (lhs
));
4549 return m_float
->op1_op2_relation (as_a
<frange
> (lhs
));
4552 // Cast the range in R to TYPE.
4555 range_cast (vrange
&r
, tree type
)
4557 Value_Range
tmp (r
);
4558 Value_Range
varying (type
);
4559 varying
.set_varying (type
);
4560 range_op_handler
op (CONVERT_EXPR
, type
);
4561 // Call op_convert, if it fails, the result is varying.
4562 if (!op
|| !op
.fold_range (r
, type
, tmp
, varying
))
4564 r
.set_varying (type
);
4571 #include "selftest.h"
4575 #define INT(N) build_int_cst (integer_type_node, (N))
4576 #define UINT(N) build_int_cstu (unsigned_type_node, (N))
4577 #define INT16(N) build_int_cst (short_integer_type_node, (N))
4578 #define UINT16(N) build_int_cstu (short_unsigned_type_node, (N))
4579 #define SCHAR(N) build_int_cst (signed_char_type_node, (N))
4580 #define UCHAR(N) build_int_cstu (unsigned_char_type_node, (N))
4583 range_op_cast_tests ()
4585 int_range
<1> r0
, r1
, r2
, rold
;
4586 r0
.set_varying (integer_type_node
);
4587 tree maxint
= wide_int_to_tree (integer_type_node
, r0
.upper_bound ());
4589 // If a range is in any way outside of the range for the converted
4590 // to range, default to the range for the new type.
4591 r0
.set_varying (short_integer_type_node
);
4592 tree minshort
= wide_int_to_tree (short_integer_type_node
, r0
.lower_bound ());
4593 tree maxshort
= wide_int_to_tree (short_integer_type_node
, r0
.upper_bound ());
4594 if (TYPE_PRECISION (TREE_TYPE (maxint
))
4595 > TYPE_PRECISION (short_integer_type_node
))
4597 r1
= int_range
<1> (integer_zero_node
, maxint
);
4598 range_cast (r1
, short_integer_type_node
);
4599 ASSERT_TRUE (r1
.lower_bound () == wi::to_wide (minshort
)
4600 && r1
.upper_bound() == wi::to_wide (maxshort
));
4603 // (unsigned char)[-5,-1] => [251,255].
4604 r0
= rold
= int_range
<1> (SCHAR (-5), SCHAR (-1));
4605 range_cast (r0
, unsigned_char_type_node
);
4606 ASSERT_TRUE (r0
== int_range
<1> (UCHAR (251), UCHAR (255)));
4607 range_cast (r0
, signed_char_type_node
);
4608 ASSERT_TRUE (r0
== rold
);
4610 // (signed char)[15, 150] => [-128,-106][15,127].
4611 r0
= rold
= int_range
<1> (UCHAR (15), UCHAR (150));
4612 range_cast (r0
, signed_char_type_node
);
4613 r1
= int_range
<1> (SCHAR (15), SCHAR (127));
4614 r2
= int_range
<1> (SCHAR (-128), SCHAR (-106));
4616 ASSERT_TRUE (r1
== r0
);
4617 range_cast (r0
, unsigned_char_type_node
);
4618 ASSERT_TRUE (r0
== rold
);
4620 // (unsigned char)[-5, 5] => [0,5][251,255].
4621 r0
= rold
= int_range
<1> (SCHAR (-5), SCHAR (5));
4622 range_cast (r0
, unsigned_char_type_node
);
4623 r1
= int_range
<1> (UCHAR (251), UCHAR (255));
4624 r2
= int_range
<1> (UCHAR (0), UCHAR (5));
4626 ASSERT_TRUE (r0
== r1
);
4627 range_cast (r0
, signed_char_type_node
);
4628 ASSERT_TRUE (r0
== rold
);
4630 // (unsigned char)[-5,5] => [0,5][251,255].
4631 r0
= int_range
<1> (INT (-5), INT (5));
4632 range_cast (r0
, unsigned_char_type_node
);
4633 r1
= int_range
<1> (UCHAR (0), UCHAR (5));
4634 r1
.union_ (int_range
<1> (UCHAR (251), UCHAR (255)));
4635 ASSERT_TRUE (r0
== r1
);
4637 // (unsigned char)[5U,1974U] => [0,255].
4638 r0
= int_range
<1> (UINT (5), UINT (1974));
4639 range_cast (r0
, unsigned_char_type_node
);
4640 ASSERT_TRUE (r0
== int_range
<1> (UCHAR (0), UCHAR (255)));
4641 range_cast (r0
, integer_type_node
);
4642 // Going to a wider range should not sign extend.
4643 ASSERT_TRUE (r0
== int_range
<1> (INT (0), INT (255)));
4645 // (unsigned char)[-350,15] => [0,255].
4646 r0
= int_range
<1> (INT (-350), INT (15));
4647 range_cast (r0
, unsigned_char_type_node
);
4648 ASSERT_TRUE (r0
== (int_range
<1>
4649 (TYPE_MIN_VALUE (unsigned_char_type_node
),
4650 TYPE_MAX_VALUE (unsigned_char_type_node
))));
4652 // Casting [-120,20] from signed char to unsigned short.
4653 // => [0, 20][0xff88, 0xffff].
4654 r0
= int_range
<1> (SCHAR (-120), SCHAR (20));
4655 range_cast (r0
, short_unsigned_type_node
);
4656 r1
= int_range
<1> (UINT16 (0), UINT16 (20));
4657 r2
= int_range
<1> (UINT16 (0xff88), UINT16 (0xffff));
4659 ASSERT_TRUE (r0
== r1
);
4660 // A truncating cast back to signed char will work because [-120, 20]
4661 // is representable in signed char.
4662 range_cast (r0
, signed_char_type_node
);
4663 ASSERT_TRUE (r0
== int_range
<1> (SCHAR (-120), SCHAR (20)));
4665 // unsigned char -> signed short
4666 // (signed short)[(unsigned char)25, (unsigned char)250]
4667 // => [(signed short)25, (signed short)250]
4668 r0
= rold
= int_range
<1> (UCHAR (25), UCHAR (250));
4669 range_cast (r0
, short_integer_type_node
);
4670 r1
= int_range
<1> (INT16 (25), INT16 (250));
4671 ASSERT_TRUE (r0
== r1
);
4672 range_cast (r0
, unsigned_char_type_node
);
4673 ASSERT_TRUE (r0
== rold
);
4675 // Test casting a wider signed [-MIN,MAX] to a nar`rower unsigned.
4676 r0
= int_range
<1> (TYPE_MIN_VALUE (long_long_integer_type_node
),
4677 TYPE_MAX_VALUE (long_long_integer_type_node
));
4678 range_cast (r0
, short_unsigned_type_node
);
4679 r1
= int_range
<1> (TYPE_MIN_VALUE (short_unsigned_type_node
),
4680 TYPE_MAX_VALUE (short_unsigned_type_node
));
4681 ASSERT_TRUE (r0
== r1
);
4683 // Casting NONZERO to a narrower type will wrap/overflow so
4684 // it's just the entire range for the narrower type.
4686 // "NOT 0 at signed 32-bits" ==> [-MIN_32,-1][1, +MAX_32]. This is
4687 // is outside of the range of a smaller range, return the full
4689 if (TYPE_PRECISION (integer_type_node
)
4690 > TYPE_PRECISION (short_integer_type_node
))
4692 r0
= range_nonzero (integer_type_node
);
4693 range_cast (r0
, short_integer_type_node
);
4694 r1
= int_range
<1> (TYPE_MIN_VALUE (short_integer_type_node
),
4695 TYPE_MAX_VALUE (short_integer_type_node
));
4696 ASSERT_TRUE (r0
== r1
);
4699 // Casting NONZERO from a narrower signed to a wider signed.
4701 // NONZERO signed 16-bits is [-MIN_16,-1][1, +MAX_16].
4702 // Converting this to 32-bits signed is [-MIN_16,-1][1, +MAX_16].
4703 r0
= range_nonzero (short_integer_type_node
);
4704 range_cast (r0
, integer_type_node
);
4705 r1
= int_range
<1> (INT (-32768), INT (-1));
4706 r2
= int_range
<1> (INT (1), INT (32767));
4708 ASSERT_TRUE (r0
== r1
);
4712 range_op_lshift_tests ()
4714 // Test that 0x808.... & 0x8.... still contains 0x8....
4715 // for a large set of numbers.
4718 tree big_type
= long_long_unsigned_type_node
;
4719 // big_num = 0x808,0000,0000,0000
4720 tree big_num
= fold_build2 (LSHIFT_EXPR
, big_type
,
4721 build_int_cst (big_type
, 0x808),
4722 build_int_cst (big_type
, 48));
4723 op_bitwise_and
.fold_range (res
, big_type
,
4724 int_range
<1> (big_type
),
4725 int_range
<1> (big_num
, big_num
));
4726 // val = 0x8,0000,0000,0000
4727 tree val
= fold_build2 (LSHIFT_EXPR
, big_type
,
4728 build_int_cst (big_type
, 0x8),
4729 build_int_cst (big_type
, 48));
4730 ASSERT_TRUE (res
.contains_p (val
));
4733 if (TYPE_PRECISION (unsigned_type_node
) > 31)
4735 // unsigned VARYING = op1 << 1 should be VARYING.
4736 int_range
<2> lhs (unsigned_type_node
);
4737 int_range
<2> shift (INT (1), INT (1));
4739 op_lshift
.op1_range (op1
, unsigned_type_node
, lhs
, shift
);
4740 ASSERT_TRUE (op1
.varying_p ());
4742 // 0 = op1 << 1 should be [0,0], [0x8000000, 0x8000000].
4743 int_range
<2> zero (UINT (0), UINT (0));
4744 op_lshift
.op1_range (op1
, unsigned_type_node
, zero
, shift
);
4745 ASSERT_TRUE (op1
.num_pairs () == 2);
4746 // Remove the [0,0] range.
4747 op1
.intersect (zero
);
4748 ASSERT_TRUE (op1
.num_pairs () == 1);
4749 // op1 << 1 should be [0x8000,0x8000] << 1,
4750 // which should result in [0,0].
4751 int_range_max result
;
4752 op_lshift
.fold_range (result
, unsigned_type_node
, op1
, shift
);
4753 ASSERT_TRUE (result
== zero
);
4755 // signed VARYING = op1 << 1 should be VARYING.
4756 if (TYPE_PRECISION (integer_type_node
) > 31)
4758 // unsigned VARYING = op1 << 1 hould be VARYING.
4759 int_range
<2> lhs (integer_type_node
);
4760 int_range
<2> shift (INT (1), INT (1));
4762 op_lshift
.op1_range (op1
, integer_type_node
, lhs
, shift
);
4763 ASSERT_TRUE (op1
.varying_p ());
4765 // 0 = op1 << 1 should be [0,0], [0x8000000, 0x8000000].
4766 int_range
<2> zero (INT (0), INT (0));
4767 op_lshift
.op1_range (op1
, integer_type_node
, zero
, shift
);
4768 ASSERT_TRUE (op1
.num_pairs () == 2);
4769 // Remove the [0,0] range.
4770 op1
.intersect (zero
);
4771 ASSERT_TRUE (op1
.num_pairs () == 1);
4772 // op1 << 1 shuould be [0x8000,0x8000] << 1,
4773 // which should result in [0,0].
4774 int_range_max result
;
4775 op_lshift
.fold_range (result
, unsigned_type_node
, op1
, shift
);
4776 ASSERT_TRUE (result
== zero
);
4781 range_op_rshift_tests ()
4783 // unsigned: [3, MAX] = OP1 >> 1
4785 int_range_max
lhs (build_int_cst (unsigned_type_node
, 3),
4786 TYPE_MAX_VALUE (unsigned_type_node
));
4787 int_range_max
one (build_one_cst (unsigned_type_node
),
4788 build_one_cst (unsigned_type_node
));
4790 op_rshift
.op1_range (op1
, unsigned_type_node
, lhs
, one
);
4791 ASSERT_FALSE (op1
.contains_p (UINT (3)));
4794 // signed: [3, MAX] = OP1 >> 1
4796 int_range_max
lhs (INT (3), TYPE_MAX_VALUE (integer_type_node
));
4797 int_range_max
one (INT (1), INT (1));
4799 op_rshift
.op1_range (op1
, integer_type_node
, lhs
, one
);
4800 ASSERT_FALSE (op1
.contains_p (INT (-2)));
4803 // This is impossible, so OP1 should be [].
4804 // signed: [MIN, MIN] = OP1 >> 1
4806 int_range_max
lhs (TYPE_MIN_VALUE (integer_type_node
),
4807 TYPE_MIN_VALUE (integer_type_node
));
4808 int_range_max
one (INT (1), INT (1));
4810 op_rshift
.op1_range (op1
, integer_type_node
, lhs
, one
);
4811 ASSERT_TRUE (op1
.undefined_p ());
4814 // signed: ~[-1] = OP1 >> 31
4815 if (TYPE_PRECISION (integer_type_node
) > 31)
4817 int_range_max
lhs (INT (-1), INT (-1), VR_ANTI_RANGE
);
4818 int_range_max
shift (INT (31), INT (31));
4820 op_rshift
.op1_range (op1
, integer_type_node
, lhs
, shift
);
4821 int_range_max negatives
= range_negatives (integer_type_node
);
4822 negatives
.intersect (op1
);
4823 ASSERT_TRUE (negatives
.undefined_p ());
4828 range_op_bitwise_and_tests ()
4831 tree min
= vrp_val_min (integer_type_node
);
4832 tree max
= vrp_val_max (integer_type_node
);
4833 tree tiny
= fold_build2 (PLUS_EXPR
, integer_type_node
, min
,
4834 build_one_cst (integer_type_node
));
4835 int_range_max
i1 (tiny
, max
);
4836 int_range_max
i2 (build_int_cst (integer_type_node
, 255),
4837 build_int_cst (integer_type_node
, 255));
4839 // [MIN+1, MAX] = OP1 & 255: OP1 is VARYING
4840 op_bitwise_and
.op1_range (res
, integer_type_node
, i1
, i2
);
4841 ASSERT_TRUE (res
== int_range
<1> (integer_type_node
));
4843 // VARYING = OP1 & 255: OP1 is VARYING
4844 i1
= int_range
<1> (integer_type_node
);
4845 op_bitwise_and
.op1_range (res
, integer_type_node
, i1
, i2
);
4846 ASSERT_TRUE (res
== int_range
<1> (integer_type_node
));
4848 // For 0 = x & MASK, x is ~MASK.
4850 int_range
<2> zero (integer_zero_node
, integer_zero_node
);
4851 int_range
<2> mask
= int_range
<2> (INT (7), INT (7));
4852 op_bitwise_and
.op1_range (res
, integer_type_node
, zero
, mask
);
4853 wide_int inv
= wi::shwi (~7U, TYPE_PRECISION (integer_type_node
));
4854 ASSERT_TRUE (res
.get_nonzero_bits () == inv
);
4857 // (NONZERO | X) is nonzero.
4858 i1
.set_nonzero (integer_type_node
);
4859 i2
.set_varying (integer_type_node
);
4860 op_bitwise_or
.fold_range (res
, integer_type_node
, i1
, i2
);
4861 ASSERT_TRUE (res
.nonzero_p ());
4863 // (NEGATIVE | X) is nonzero.
4864 i1
= int_range
<1> (INT (-5), INT (-3));
4865 i2
.set_varying (integer_type_node
);
4866 op_bitwise_or
.fold_range (res
, integer_type_node
, i1
, i2
);
4867 ASSERT_FALSE (res
.contains_p (INT (0)));
4871 range_relational_tests ()
4873 int_range
<2> lhs (unsigned_char_type_node
);
4874 int_range
<2> op1 (UCHAR (8), UCHAR (10));
4875 int_range
<2> op2 (UCHAR (20), UCHAR (20));
4877 // Never wrapping additions mean LHS > OP1.
4878 relation_kind code
= op_plus
.lhs_op1_relation (lhs
, op1
, op2
, VREL_VARYING
);
4879 ASSERT_TRUE (code
== VREL_GT
);
4881 // Most wrapping additions mean nothing...
4882 op1
= int_range
<2> (UCHAR (8), UCHAR (10));
4883 op2
= int_range
<2> (UCHAR (0), UCHAR (255));
4884 code
= op_plus
.lhs_op1_relation (lhs
, op1
, op2
, VREL_VARYING
);
4885 ASSERT_TRUE (code
== VREL_VARYING
);
4887 // However, always wrapping additions mean LHS < OP1.
4888 op1
= int_range
<2> (UCHAR (1), UCHAR (255));
4889 op2
= int_range
<2> (UCHAR (255), UCHAR (255));
4890 code
= op_plus
.lhs_op1_relation (lhs
, op1
, op2
, VREL_VARYING
);
4891 ASSERT_TRUE (code
== VREL_LT
);
4897 range_op_rshift_tests ();
4898 range_op_lshift_tests ();
4899 range_op_bitwise_and_tests ();
4900 range_op_cast_tests ();
4901 range_relational_tests ();
4903 extern void range_op_float_tests ();
4904 range_op_float_tests ();
4907 } // namespace selftest
4909 #endif // CHECKING_P