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-fold.h"
43 #include "gimple-iterator.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 (irange::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_kind rel
) const
184 gcc_checking_assert (irange::supports_type_p (type
));
185 if (empty_range_varying (r
, type
, lh
, rh
))
188 unsigned num_lh
= lh
.num_pairs ();
189 unsigned num_rh
= rh
.num_pairs ();
191 // If both ranges are single pairs, fold directly into the result range.
192 // If the number of subranges grows too high, produce a summary result as the
193 // loop becomes exponential with little benefit. See PR 103821.
194 if ((num_lh
== 1 && num_rh
== 1) || num_lh
* num_rh
> 12)
196 wi_fold_in_parts (r
, type
, lh
.lower_bound (), lh
.upper_bound (),
197 rh
.lower_bound (), rh
.upper_bound ());
198 op1_op2_relation_effect (r
, type
, lh
, rh
, rel
);
204 for (unsigned x
= 0; x
< num_lh
; ++x
)
205 for (unsigned y
= 0; y
< num_rh
; ++y
)
207 wide_int lh_lb
= lh
.lower_bound (x
);
208 wide_int lh_ub
= lh
.upper_bound (x
);
209 wide_int rh_lb
= rh
.lower_bound (y
);
210 wide_int rh_ub
= rh
.upper_bound (y
);
211 wi_fold_in_parts (tmp
, type
, lh_lb
, lh_ub
, rh_lb
, rh_ub
);
215 op1_op2_relation_effect (r
, type
, lh
, rh
, rel
);
219 op1_op2_relation_effect (r
, type
, lh
, rh
, rel
);
223 // The default for op1_range is to return false.
226 range_operator::op1_range (irange
&r ATTRIBUTE_UNUSED
,
227 tree type ATTRIBUTE_UNUSED
,
228 const irange
&lhs ATTRIBUTE_UNUSED
,
229 const irange
&op2 ATTRIBUTE_UNUSED
,
230 relation_kind rel ATTRIBUTE_UNUSED
) const
235 // The default for op2_range is to return false.
238 range_operator::op2_range (irange
&r ATTRIBUTE_UNUSED
,
239 tree type ATTRIBUTE_UNUSED
,
240 const irange
&lhs ATTRIBUTE_UNUSED
,
241 const irange
&op1 ATTRIBUTE_UNUSED
,
242 relation_kind rel ATTRIBUTE_UNUSED
) const
247 // The default relation routines return VREL_NONE.
250 range_operator::lhs_op1_relation (const irange
&lhs ATTRIBUTE_UNUSED
,
251 const irange
&op1 ATTRIBUTE_UNUSED
,
252 const irange
&op2 ATTRIBUTE_UNUSED
) const
258 range_operator::lhs_op2_relation (const irange
&lhs ATTRIBUTE_UNUSED
,
259 const irange
&op1 ATTRIBUTE_UNUSED
,
260 const irange
&op2 ATTRIBUTE_UNUSED
) const
266 range_operator::op1_op2_relation (const irange
&lhs ATTRIBUTE_UNUSED
) const
271 // Default is no relation affects the LHS.
274 range_operator::op1_op2_relation_effect (irange
&lhs_range ATTRIBUTE_UNUSED
,
275 tree type ATTRIBUTE_UNUSED
,
276 const irange
&op1_range ATTRIBUTE_UNUSED
,
277 const irange
&op2_range ATTRIBUTE_UNUSED
,
278 relation_kind rel ATTRIBUTE_UNUSED
) const
283 // Create and return a range from a pair of wide-ints that are known
284 // to have overflowed (or underflowed).
287 value_range_from_overflowed_bounds (irange
&r
, tree type
,
288 const wide_int
&wmin
,
289 const wide_int
&wmax
)
291 const signop sgn
= TYPE_SIGN (type
);
292 const unsigned int prec
= TYPE_PRECISION (type
);
294 wide_int tmin
= wide_int::from (wmin
, prec
, sgn
);
295 wide_int tmax
= wide_int::from (wmax
, prec
, sgn
);
300 if (wi::cmp (tmin
, tmax
, sgn
) < 0)
303 if (wi::cmp (tmax
, tem
, sgn
) > 0)
306 // If the anti-range would cover nothing, drop to varying.
307 // Likewise if the anti-range bounds are outside of the types
309 if (covers
|| wi::cmp (tmin
, tmax
, sgn
) > 0)
310 r
.set_varying (type
);
313 tree tree_min
= wide_int_to_tree (type
, tmin
);
314 tree tree_max
= wide_int_to_tree (type
, tmax
);
315 r
.set (tree_min
, tree_max
, VR_ANTI_RANGE
);
319 // Create and return a range from a pair of wide-ints. MIN_OVF and
320 // MAX_OVF describe any overflow that might have occurred while
321 // calculating WMIN and WMAX respectively.
324 value_range_with_overflow (irange
&r
, tree type
,
325 const wide_int
&wmin
, const wide_int
&wmax
,
326 wi::overflow_type min_ovf
= wi::OVF_NONE
,
327 wi::overflow_type max_ovf
= wi::OVF_NONE
)
329 const signop sgn
= TYPE_SIGN (type
);
330 const unsigned int prec
= TYPE_PRECISION (type
);
331 const bool overflow_wraps
= TYPE_OVERFLOW_WRAPS (type
);
333 // For one bit precision if max != min, then the range covers all
335 if (prec
== 1 && wi::ne_p (wmax
, wmin
))
337 r
.set_varying (type
);
343 // If overflow wraps, truncate the values and adjust the range,
344 // kind, and bounds appropriately.
345 if ((min_ovf
!= wi::OVF_NONE
) == (max_ovf
!= wi::OVF_NONE
))
347 wide_int tmin
= wide_int::from (wmin
, prec
, sgn
);
348 wide_int tmax
= wide_int::from (wmax
, prec
, sgn
);
349 // If the limits are swapped, we wrapped around and cover
351 if (wi::gt_p (tmin
, tmax
, sgn
))
352 r
.set_varying (type
);
354 // No overflow or both overflow or underflow. The range
355 // kind stays normal.
356 r
.set (wide_int_to_tree (type
, tmin
),
357 wide_int_to_tree (type
, tmax
));
361 if ((min_ovf
== wi::OVF_UNDERFLOW
&& max_ovf
== wi::OVF_NONE
)
362 || (max_ovf
== wi::OVF_OVERFLOW
&& min_ovf
== wi::OVF_NONE
))
363 value_range_from_overflowed_bounds (r
, type
, wmin
, wmax
);
365 // Other underflow and/or overflow, drop to VR_VARYING.
366 r
.set_varying (type
);
370 // If both bounds either underflowed or overflowed, then the result
372 if ((min_ovf
== wi::OVF_OVERFLOW
&& max_ovf
== wi::OVF_OVERFLOW
)
373 || (min_ovf
== wi::OVF_UNDERFLOW
&& max_ovf
== wi::OVF_UNDERFLOW
))
379 // If overflow does not wrap, saturate to [MIN, MAX].
380 wide_int new_lb
, new_ub
;
381 if (min_ovf
== wi::OVF_UNDERFLOW
)
382 new_lb
= wi::min_value (prec
, sgn
);
383 else if (min_ovf
== wi::OVF_OVERFLOW
)
384 new_lb
= wi::max_value (prec
, sgn
);
388 if (max_ovf
== wi::OVF_UNDERFLOW
)
389 new_ub
= wi::min_value (prec
, sgn
);
390 else if (max_ovf
== wi::OVF_OVERFLOW
)
391 new_ub
= wi::max_value (prec
, sgn
);
395 r
.set (wide_int_to_tree (type
, new_lb
),
396 wide_int_to_tree (type
, new_ub
));
400 // Create and return a range from a pair of wide-ints. Canonicalize
401 // the case where the bounds are swapped. In which case, we transform
402 // [10,5] into [MIN,5][10,MAX].
405 create_possibly_reversed_range (irange
&r
, tree type
,
406 const wide_int
&new_lb
, const wide_int
&new_ub
)
408 signop s
= TYPE_SIGN (type
);
409 // If the bounds are swapped, treat the result as if an overflow occured.
410 if (wi::gt_p (new_lb
, new_ub
, s
))
411 value_range_from_overflowed_bounds (r
, type
, new_lb
, new_ub
);
413 // Otherwise it's just a normal range.
414 r
.set (wide_int_to_tree (type
, new_lb
), wide_int_to_tree (type
, new_ub
));
417 // Return the summary information about boolean range LHS. If EMPTY/FULL,
418 // return the equivalent range for TYPE in R; if FALSE/TRUE, do nothing.
421 get_bool_state (irange
&r
, const irange
&lhs
, tree val_type
)
423 // If there is no result, then this is unexecutable.
424 if (lhs
.undefined_p ())
433 // For TRUE, we can't just test for [1,1] because Ada can have
434 // multi-bit booleans, and TRUE values can be: [1, MAX], ~[0], etc.
435 if (lhs
.contains_p (build_zero_cst (lhs
.type ())))
437 r
.set_varying (val_type
);
445 class operator_equal
: public range_operator
448 virtual bool fold_range (irange
&r
, tree type
,
451 relation_kind rel
= VREL_NONE
) const;
452 virtual bool op1_range (irange
&r
, tree type
,
455 relation_kind rel
= VREL_NONE
) const;
456 virtual bool op2_range (irange
&r
, tree type
,
459 relation_kind rel
= VREL_NONE
) const;
460 virtual enum tree_code
op1_op2_relation (const irange
&lhs
) const;
463 // Check if the LHS range indicates a relation between OP1 and OP2.
466 equal_op1_op2_relation (const irange
&lhs
)
468 if (lhs
.undefined_p ())
471 // FALSE = op1 == op2 indicates NE_EXPR.
475 // TRUE = op1 == op2 indicates EQ_EXPR.
476 if (!lhs
.contains_p (build_zero_cst (lhs
.type ())))
482 operator_equal::op1_op2_relation (const irange
&lhs
) const
484 return equal_op1_op2_relation (lhs
);
489 operator_equal::fold_range (irange
&r
, tree type
,
492 relation_kind rel
) const
494 if (relop_early_resolve (r
, type
, op1
, op2
, rel
, EQ_EXPR
))
497 // We can be sure the values are always equal or not if both ranges
498 // consist of a single value, and then compare them.
499 if (wi::eq_p (op1
.lower_bound (), op1
.upper_bound ())
500 && wi::eq_p (op2
.lower_bound (), op2
.upper_bound ()))
502 if (wi::eq_p (op1
.lower_bound (), op2
.upper_bound()))
503 r
= range_true (type
);
505 r
= range_false (type
);
509 // If ranges do not intersect, we know the range is not equal,
510 // otherwise we don't know anything for sure.
511 int_range_max tmp
= op1
;
513 if (tmp
.undefined_p ())
514 r
= range_false (type
);
516 r
= range_true_and_false (type
);
522 operator_equal::op1_range (irange
&r
, tree type
,
525 relation_kind rel ATTRIBUTE_UNUSED
) const
527 switch (get_bool_state (r
, lhs
, type
))
530 // If the result is false, the only time we know anything is
531 // if OP2 is a constant.
532 if (wi::eq_p (op2
.lower_bound(), op2
.upper_bound()))
538 r
.set_varying (type
);
542 // If it's true, the result is the same as OP2.
553 operator_equal::op2_range (irange
&r
, tree type
,
556 relation_kind rel
) const
558 return operator_equal::op1_range (r
, type
, lhs
, op1
, rel
);
561 class operator_not_equal
: public range_operator
564 virtual bool fold_range (irange
&r
, tree type
,
567 relation_kind rel
= VREL_NONE
) const;
568 virtual bool op1_range (irange
&r
, tree type
,
571 relation_kind rel
= VREL_NONE
) const;
572 virtual bool op2_range (irange
&r
, tree type
,
575 relation_kind rel
= VREL_NONE
) const;
576 virtual enum tree_code
op1_op2_relation (const irange
&lhs
) const;
579 // Check if the LHS range indicates a relation between OP1 and OP2.
582 not_equal_op1_op2_relation (const irange
&lhs
)
584 if (lhs
.undefined_p ())
587 // FALSE = op1 != op2 indicates EQ_EXPR.
591 // TRUE = op1 != op2 indicates NE_EXPR.
592 if (!lhs
.contains_p (build_zero_cst (lhs
.type ())))
598 operator_not_equal::op1_op2_relation (const irange
&lhs
) const
600 return not_equal_op1_op2_relation (lhs
);
604 operator_not_equal::fold_range (irange
&r
, tree type
,
607 relation_kind rel
) const
609 if (relop_early_resolve (r
, type
, op1
, op2
, rel
, NE_EXPR
))
612 // We can be sure the values are always equal or not if both ranges
613 // consist of a single value, and then compare them.
614 if (wi::eq_p (op1
.lower_bound (), op1
.upper_bound ())
615 && wi::eq_p (op2
.lower_bound (), op2
.upper_bound ()))
617 if (wi::ne_p (op1
.lower_bound (), op2
.upper_bound()))
618 r
= range_true (type
);
620 r
= range_false (type
);
624 // If ranges do not intersect, we know the range is not equal,
625 // otherwise we don't know anything for sure.
626 int_range_max tmp
= op1
;
628 if (tmp
.undefined_p ())
629 r
= range_true (type
);
631 r
= range_true_and_false (type
);
637 operator_not_equal::op1_range (irange
&r
, tree type
,
640 relation_kind rel ATTRIBUTE_UNUSED
) const
642 switch (get_bool_state (r
, lhs
, type
))
645 // If the result is true, the only time we know anything is if
646 // OP2 is a constant.
647 if (wi::eq_p (op2
.lower_bound(), op2
.upper_bound()))
653 r
.set_varying (type
);
657 // If it's false, the result is the same as OP2.
669 operator_not_equal::op2_range (irange
&r
, tree type
,
672 relation_kind rel
) const
674 return operator_not_equal::op1_range (r
, type
, lhs
, op1
, rel
);
677 // (X < VAL) produces the range of [MIN, VAL - 1].
680 build_lt (irange
&r
, tree type
, const wide_int
&val
)
682 wi::overflow_type ov
;
684 signop sgn
= TYPE_SIGN (type
);
686 // Signed 1 bit cannot represent 1 for subtraction.
688 lim
= wi::add (val
, -1, sgn
, &ov
);
690 lim
= wi::sub (val
, 1, sgn
, &ov
);
692 // If val - 1 underflows, check if X < MIN, which is an empty range.
696 r
= int_range
<1> (type
, min_limit (type
), lim
);
699 // (X <= VAL) produces the range of [MIN, VAL].
702 build_le (irange
&r
, tree type
, const wide_int
&val
)
704 r
= int_range
<1> (type
, min_limit (type
), val
);
707 // (X > VAL) produces the range of [VAL + 1, MAX].
710 build_gt (irange
&r
, tree type
, const wide_int
&val
)
712 wi::overflow_type ov
;
714 signop sgn
= TYPE_SIGN (type
);
716 // Signed 1 bit cannot represent 1 for addition.
718 lim
= wi::sub (val
, -1, sgn
, &ov
);
720 lim
= wi::add (val
, 1, sgn
, &ov
);
721 // If val + 1 overflows, check is for X > MAX, which is an empty range.
725 r
= int_range
<1> (type
, lim
, max_limit (type
));
728 // (X >= val) produces the range of [VAL, MAX].
731 build_ge (irange
&r
, tree type
, const wide_int
&val
)
733 r
= int_range
<1> (type
, val
, max_limit (type
));
737 class operator_lt
: public range_operator
740 virtual bool fold_range (irange
&r
, tree type
,
743 relation_kind rel
= VREL_NONE
) const;
744 virtual bool op1_range (irange
&r
, tree type
,
747 relation_kind rel
= VREL_NONE
) const;
748 virtual bool op2_range (irange
&r
, tree type
,
751 relation_kind rel
= VREL_NONE
) const;
752 virtual enum tree_code
op1_op2_relation (const irange
&lhs
) const;
755 // Check if the LHS range indicates a relation between OP1 and OP2.
758 lt_op1_op2_relation (const irange
&lhs
)
760 if (lhs
.undefined_p ())
763 // FALSE = op1 < op2 indicates GE_EXPR.
767 // TRUE = op1 < op2 indicates LT_EXPR.
768 if (!lhs
.contains_p (build_zero_cst (lhs
.type ())))
774 operator_lt::op1_op2_relation (const irange
&lhs
) const
776 return lt_op1_op2_relation (lhs
);
780 operator_lt::fold_range (irange
&r
, tree type
,
783 relation_kind rel
) const
785 if (relop_early_resolve (r
, type
, op1
, op2
, rel
, LT_EXPR
))
788 signop sign
= TYPE_SIGN (op1
.type ());
789 gcc_checking_assert (sign
== TYPE_SIGN (op2
.type ()));
791 if (wi::lt_p (op1
.upper_bound (), op2
.lower_bound (), sign
))
792 r
= range_true (type
);
793 else if (!wi::lt_p (op1
.lower_bound (), op2
.upper_bound (), sign
))
794 r
= range_false (type
);
796 r
= range_true_and_false (type
);
801 operator_lt::op1_range (irange
&r
, tree type
,
804 relation_kind rel ATTRIBUTE_UNUSED
) const
806 switch (get_bool_state (r
, lhs
, type
))
809 build_lt (r
, type
, op2
.upper_bound ());
813 build_ge (r
, type
, op2
.lower_bound ());
823 operator_lt::op2_range (irange
&r
, tree type
,
826 relation_kind rel ATTRIBUTE_UNUSED
) const
828 switch (get_bool_state (r
, lhs
, type
))
831 build_le (r
, type
, op1
.upper_bound ());
835 build_gt (r
, type
, op1
.lower_bound ());
845 class operator_le
: public range_operator
848 virtual bool fold_range (irange
&r
, tree type
,
851 relation_kind rel
= VREL_NONE
) const;
852 virtual bool op1_range (irange
&r
, tree type
,
855 relation_kind rel
= VREL_NONE
) const;
856 virtual bool op2_range (irange
&r
, tree type
,
859 relation_kind rel
= VREL_NONE
) const;
860 virtual enum tree_code
op1_op2_relation (const irange
&lhs
) const;
863 // Check if the LHS range indicates a relation between OP1 and OP2.
866 le_op1_op2_relation (const irange
&lhs
)
868 if (lhs
.undefined_p ())
871 // FALSE = op1 <= op2 indicates GT_EXPR.
875 // TRUE = op1 <= op2 indicates LE_EXPR.
876 if (!lhs
.contains_p (build_zero_cst (lhs
.type ())))
882 operator_le::op1_op2_relation (const irange
&lhs
) const
884 return le_op1_op2_relation (lhs
);
888 operator_le::fold_range (irange
&r
, tree type
,
891 relation_kind rel
) const
893 if (relop_early_resolve (r
, type
, op1
, op2
, rel
, LE_EXPR
))
896 signop sign
= TYPE_SIGN (op1
.type ());
897 gcc_checking_assert (sign
== TYPE_SIGN (op2
.type ()));
899 if (wi::le_p (op1
.upper_bound (), op2
.lower_bound (), sign
))
900 r
= range_true (type
);
901 else if (!wi::le_p (op1
.lower_bound (), op2
.upper_bound (), sign
))
902 r
= range_false (type
);
904 r
= range_true_and_false (type
);
909 operator_le::op1_range (irange
&r
, tree type
,
912 relation_kind rel ATTRIBUTE_UNUSED
) const
914 switch (get_bool_state (r
, lhs
, type
))
917 build_le (r
, type
, op2
.upper_bound ());
921 build_gt (r
, type
, op2
.lower_bound ());
931 operator_le::op2_range (irange
&r
, tree type
,
934 relation_kind rel ATTRIBUTE_UNUSED
) const
936 switch (get_bool_state (r
, lhs
, type
))
939 build_lt (r
, type
, op1
.upper_bound ());
943 build_ge (r
, type
, op1
.lower_bound ());
953 class operator_gt
: public range_operator
956 virtual bool fold_range (irange
&r
, tree type
,
959 relation_kind rel
= VREL_NONE
) const;
960 virtual bool op1_range (irange
&r
, tree type
,
963 relation_kind rel
= VREL_NONE
) const;
964 virtual bool op2_range (irange
&r
, tree type
,
967 relation_kind rel
= VREL_NONE
) const;
968 virtual enum tree_code
op1_op2_relation (const irange
&lhs
) const;
971 // Check if the LHS range indicates a relation between OP1 and OP2.
974 gt_op1_op2_relation (const irange
&lhs
)
976 if (lhs
.undefined_p ())
979 // FALSE = op1 > op2 indicates LE_EXPR.
983 // TRUE = op1 > op2 indicates GT_EXPR.
984 if (!lhs
.contains_p (build_zero_cst (lhs
.type ())))
990 operator_gt::op1_op2_relation (const irange
&lhs
) const
992 return gt_op1_op2_relation (lhs
);
997 operator_gt::fold_range (irange
&r
, tree type
,
998 const irange
&op1
, const irange
&op2
,
999 relation_kind rel
) const
1001 if (relop_early_resolve (r
, type
, op1
, op2
, rel
, GT_EXPR
))
1004 signop sign
= TYPE_SIGN (op1
.type ());
1005 gcc_checking_assert (sign
== TYPE_SIGN (op2
.type ()));
1007 if (wi::gt_p (op1
.lower_bound (), op2
.upper_bound (), sign
))
1008 r
= range_true (type
);
1009 else if (!wi::gt_p (op1
.upper_bound (), op2
.lower_bound (), sign
))
1010 r
= range_false (type
);
1012 r
= range_true_and_false (type
);
1017 operator_gt::op1_range (irange
&r
, tree type
,
1018 const irange
&lhs
, const irange
&op2
,
1019 relation_kind rel ATTRIBUTE_UNUSED
) const
1021 switch (get_bool_state (r
, lhs
, type
))
1024 build_gt (r
, type
, op2
.lower_bound ());
1028 build_le (r
, type
, op2
.upper_bound ());
1038 operator_gt::op2_range (irange
&r
, tree type
,
1041 relation_kind rel ATTRIBUTE_UNUSED
) const
1043 switch (get_bool_state (r
, lhs
, type
))
1046 build_ge (r
, type
, op1
.lower_bound ());
1050 build_lt (r
, type
, op1
.upper_bound ());
1060 class operator_ge
: public range_operator
1063 virtual bool fold_range (irange
&r
, tree type
,
1066 relation_kind rel
= VREL_NONE
) const;
1067 virtual bool op1_range (irange
&r
, tree type
,
1070 relation_kind rel
= VREL_NONE
) const;
1071 virtual bool op2_range (irange
&r
, tree type
,
1074 relation_kind rel
= VREL_NONE
) const;
1075 virtual enum tree_code
op1_op2_relation (const irange
&lhs
) const;
1078 // Check if the LHS range indicates a relation between OP1 and OP2.
1081 ge_op1_op2_relation (const irange
&lhs
)
1083 if (lhs
.undefined_p ())
1086 // FALSE = op1 >= op2 indicates LT_EXPR.
1090 // TRUE = op1 >= op2 indicates GE_EXPR.
1091 if (!lhs
.contains_p (build_zero_cst (lhs
.type ())))
1097 operator_ge::op1_op2_relation (const irange
&lhs
) const
1099 return ge_op1_op2_relation (lhs
);
1103 operator_ge::fold_range (irange
&r
, tree type
,
1106 relation_kind rel
) const
1108 if (relop_early_resolve (r
, type
, op1
, op2
, rel
, GE_EXPR
))
1111 signop sign
= TYPE_SIGN (op1
.type ());
1112 gcc_checking_assert (sign
== TYPE_SIGN (op2
.type ()));
1114 if (wi::ge_p (op1
.lower_bound (), op2
.upper_bound (), sign
))
1115 r
= range_true (type
);
1116 else if (!wi::ge_p (op1
.upper_bound (), op2
.lower_bound (), sign
))
1117 r
= range_false (type
);
1119 r
= range_true_and_false (type
);
1124 operator_ge::op1_range (irange
&r
, tree type
,
1127 relation_kind rel ATTRIBUTE_UNUSED
) const
1129 switch (get_bool_state (r
, lhs
, type
))
1132 build_ge (r
, type
, op2
.lower_bound ());
1136 build_lt (r
, type
, op2
.upper_bound ());
1146 operator_ge::op2_range (irange
&r
, tree type
,
1149 relation_kind rel ATTRIBUTE_UNUSED
) const
1151 switch (get_bool_state (r
, lhs
, type
))
1154 build_gt (r
, type
, op1
.lower_bound ());
1158 build_le (r
, type
, op1
.upper_bound ());
1168 class operator_plus
: public range_operator
1171 virtual bool op1_range (irange
&r
, tree type
,
1174 relation_kind rel ATTRIBUTE_UNUSED
) const;
1175 virtual bool op2_range (irange
&r
, tree type
,
1178 relation_kind rel ATTRIBUTE_UNUSED
) const;
1179 virtual void wi_fold (irange
&r
, tree type
,
1180 const wide_int
&lh_lb
,
1181 const wide_int
&lh_ub
,
1182 const wide_int
&rh_lb
,
1183 const wide_int
&rh_ub
) const;
1184 virtual enum tree_code
lhs_op1_relation (const irange
&lhs
, const irange
&op1
,
1185 const irange
&op2
) const;
1186 virtual enum tree_code
lhs_op2_relation (const irange
&lhs
, const irange
&op1
,
1187 const irange
&op2
) const;
1190 // Check to see if the range of OP2 indicates anything about the relation
1191 // between LHS and OP1.
1194 operator_plus::lhs_op1_relation (const irange
&lhs
,
1196 const irange
&op2
) const
1198 if (lhs
.undefined_p () || op1
.undefined_p () || op2
.undefined_p ())
1201 tree type
= lhs
.type ();
1202 unsigned prec
= TYPE_PRECISION (type
);
1203 wi::overflow_type ovf1
, ovf2
;
1204 signop sign
= TYPE_SIGN (type
);
1206 // LHS = OP1 + 0 indicates LHS == OP1.
1210 if (TYPE_OVERFLOW_WRAPS (type
))
1212 wi::add (op1
.lower_bound (), op2
.lower_bound (), sign
, &ovf1
);
1213 wi::add (op1
.upper_bound (), op2
.upper_bound (), sign
, &ovf2
);
1216 ovf1
= ovf2
= wi::OVF_NONE
;
1218 // Never wrapping additions.
1221 // Positive op2 means lhs > op1.
1222 if (wi::gt_p (op2
.lower_bound (), wi::zero (prec
), sign
))
1224 if (wi::ge_p (op2
.lower_bound (), wi::zero (prec
), sign
))
1227 // Negative op2 means lhs < op1.
1228 if (wi::lt_p (op2
.upper_bound (), wi::zero (prec
), sign
))
1230 if (wi::le_p (op2
.upper_bound (), wi::zero (prec
), sign
))
1233 // Always wrapping additions.
1234 else if (ovf1
&& ovf1
== ovf2
)
1236 // Positive op2 means lhs < op1.
1237 if (wi::gt_p (op2
.lower_bound (), wi::zero (prec
), sign
))
1239 if (wi::ge_p (op2
.lower_bound (), wi::zero (prec
), sign
))
1242 // Negative op2 means lhs > op1.
1243 if (wi::lt_p (op2
.upper_bound (), wi::zero (prec
), sign
))
1245 if (wi::le_p (op2
.upper_bound (), wi::zero (prec
), sign
))
1249 // If op2 does not contain 0, then LHS and OP1 can never be equal.
1250 if (!range_includes_zero_p (&op2
))
1256 // PLUS is symmetrical, so we can simply call lhs_op1_relation with reversed
1260 operator_plus::lhs_op2_relation (const irange
&lhs
, const irange
&op1
,
1261 const irange
&op2
) const
1263 return lhs_op1_relation (lhs
, op2
, op1
);
1267 operator_plus::wi_fold (irange
&r
, tree type
,
1268 const wide_int
&lh_lb
, const wide_int
&lh_ub
,
1269 const wide_int
&rh_lb
, const wide_int
&rh_ub
) const
1271 wi::overflow_type ov_lb
, ov_ub
;
1272 signop s
= TYPE_SIGN (type
);
1273 wide_int new_lb
= wi::add (lh_lb
, rh_lb
, s
, &ov_lb
);
1274 wide_int new_ub
= wi::add (lh_ub
, rh_ub
, s
, &ov_ub
);
1275 value_range_with_overflow (r
, type
, new_lb
, new_ub
, ov_lb
, ov_ub
);
1279 operator_plus::op1_range (irange
&r
, tree type
,
1282 relation_kind rel ATTRIBUTE_UNUSED
) const
1284 return range_op_handler (MINUS_EXPR
, type
)->fold_range (r
, type
, lhs
, op2
);
1288 operator_plus::op2_range (irange
&r
, tree type
,
1291 relation_kind rel ATTRIBUTE_UNUSED
) const
1293 return range_op_handler (MINUS_EXPR
, type
)->fold_range (r
, type
, lhs
, op1
);
1297 class operator_minus
: public range_operator
1300 virtual bool op1_range (irange
&r
, tree type
,
1303 relation_kind rel ATTRIBUTE_UNUSED
) const;
1304 virtual bool op2_range (irange
&r
, tree type
,
1307 relation_kind rel ATTRIBUTE_UNUSED
) const;
1308 virtual void wi_fold (irange
&r
, tree type
,
1309 const wide_int
&lh_lb
,
1310 const wide_int
&lh_ub
,
1311 const wide_int
&rh_lb
,
1312 const wide_int
&rh_ub
) const;
1313 virtual bool op1_op2_relation_effect (irange
&lhs_range
,
1315 const irange
&op1_range
,
1316 const irange
&op2_range
,
1317 relation_kind rel
) const;
1321 operator_minus::wi_fold (irange
&r
, tree type
,
1322 const wide_int
&lh_lb
, const wide_int
&lh_ub
,
1323 const wide_int
&rh_lb
, const wide_int
&rh_ub
) const
1325 wi::overflow_type ov_lb
, ov_ub
;
1326 signop s
= TYPE_SIGN (type
);
1327 wide_int new_lb
= wi::sub (lh_lb
, rh_ub
, s
, &ov_lb
);
1328 wide_int new_ub
= wi::sub (lh_ub
, rh_lb
, s
, &ov_ub
);
1329 value_range_with_overflow (r
, type
, new_lb
, new_ub
, ov_lb
, ov_ub
);
1332 // Check to see if the relation REL between OP1 and OP2 has any effect on the
1333 // LHS of the expression. If so, apply it to LHS_RANGE. This is a helper
1334 // function for both MINUS_EXPR and POINTER_DIFF_EXPR.
1337 minus_op1_op2_relation_effect (irange
&lhs_range
, tree type
,
1338 const irange
&op1_range ATTRIBUTE_UNUSED
,
1339 const irange
&op2_range ATTRIBUTE_UNUSED
,
1342 if (rel
== VREL_NONE
)
1345 int_range
<2> rel_range
;
1346 unsigned prec
= TYPE_PRECISION (type
);
1347 signop sgn
= TYPE_SIGN (type
);
1349 // == and != produce [0,0] and ~[0,0] regardless of wrapping.
1351 rel_range
= int_range
<2> (type
, wi::zero (prec
), wi::zero (prec
));
1352 else if (rel
== NE_EXPR
)
1353 rel_range
= int_range
<2> (type
, wi::zero (prec
), wi::zero (prec
),
1355 else if (TYPE_OVERFLOW_WRAPS (type
))
1359 // For wrapping signed values and unsigned, if op1 > op2 or
1360 // op1 < op2, then op1 - op2 can be restricted to ~[0, 0].
1363 rel_range
= int_range
<2> (type
, wi::zero (prec
), wi::zero (prec
),
1374 // op1 > op2, op1 - op2 can be restricted to [1, +INF]
1376 rel_range
= int_range
<2> (type
, wi::one (prec
),
1377 wi::max_value (prec
, sgn
));
1379 // op1 >= op2, op1 - op2 can be restricted to [0, +INF]
1381 rel_range
= int_range
<2> (type
, wi::zero (prec
),
1382 wi::max_value (prec
, sgn
));
1384 // op1 < op2, op1 - op2 can be restricted to [-INF, -1]
1386 rel_range
= int_range
<2> (type
, wi::min_value (prec
, sgn
),
1387 wi::minus_one (prec
));
1389 // op1 <= op2, op1 - op2 can be restricted to [-INF, 0]
1391 rel_range
= int_range
<2> (type
, wi::min_value (prec
, sgn
),
1398 lhs_range
.intersect (rel_range
);
1403 operator_minus::op1_op2_relation_effect (irange
&lhs_range
, tree type
,
1404 const irange
&op1_range
,
1405 const irange
&op2_range
,
1406 relation_kind rel
) const
1408 return minus_op1_op2_relation_effect (lhs_range
, type
, op1_range
, op2_range
,
1413 operator_minus::op1_range (irange
&r
, tree type
,
1416 relation_kind rel ATTRIBUTE_UNUSED
) const
1418 return range_op_handler (PLUS_EXPR
, type
)->fold_range (r
, type
, lhs
, op2
);
1422 operator_minus::op2_range (irange
&r
, tree type
,
1425 relation_kind rel ATTRIBUTE_UNUSED
) const
1427 return fold_range (r
, type
, op1
, lhs
);
1431 class operator_pointer_diff
: public range_operator
1433 virtual bool op1_op2_relation_effect (irange
&lhs_range
,
1435 const irange
&op1_range
,
1436 const irange
&op2_range
,
1437 relation_kind rel
) const;
1441 operator_pointer_diff::op1_op2_relation_effect (irange
&lhs_range
, tree type
,
1442 const irange
&op1_range
,
1443 const irange
&op2_range
,
1444 relation_kind rel
) const
1446 return minus_op1_op2_relation_effect (lhs_range
, type
, op1_range
, op2_range
,
1451 class operator_min
: public range_operator
1454 virtual void wi_fold (irange
&r
, tree type
,
1455 const wide_int
&lh_lb
,
1456 const wide_int
&lh_ub
,
1457 const wide_int
&rh_lb
,
1458 const wide_int
&rh_ub
) const;
1462 operator_min::wi_fold (irange
&r
, tree type
,
1463 const wide_int
&lh_lb
, const wide_int
&lh_ub
,
1464 const wide_int
&rh_lb
, const wide_int
&rh_ub
) const
1466 signop s
= TYPE_SIGN (type
);
1467 wide_int new_lb
= wi::min (lh_lb
, rh_lb
, s
);
1468 wide_int new_ub
= wi::min (lh_ub
, rh_ub
, s
);
1469 value_range_with_overflow (r
, type
, new_lb
, new_ub
);
1473 class operator_max
: public range_operator
1476 virtual void wi_fold (irange
&r
, tree type
,
1477 const wide_int
&lh_lb
,
1478 const wide_int
&lh_ub
,
1479 const wide_int
&rh_lb
,
1480 const wide_int
&rh_ub
) const;
1484 operator_max::wi_fold (irange
&r
, tree type
,
1485 const wide_int
&lh_lb
, const wide_int
&lh_ub
,
1486 const wide_int
&rh_lb
, const wide_int
&rh_ub
) const
1488 signop s
= TYPE_SIGN (type
);
1489 wide_int new_lb
= wi::max (lh_lb
, rh_lb
, s
);
1490 wide_int new_ub
= wi::max (lh_ub
, rh_ub
, s
);
1491 value_range_with_overflow (r
, type
, new_lb
, new_ub
);
1495 class cross_product_operator
: public range_operator
1498 // Perform an operation between two wide-ints and place the result
1499 // in R. Return true if the operation overflowed.
1500 virtual bool wi_op_overflows (wide_int
&r
,
1503 const wide_int
&) const = 0;
1505 // Calculate the cross product of two sets of sub-ranges and return it.
1506 void wi_cross_product (irange
&r
, tree type
,
1507 const wide_int
&lh_lb
,
1508 const wide_int
&lh_ub
,
1509 const wide_int
&rh_lb
,
1510 const wide_int
&rh_ub
) const;
1513 // Calculate the cross product of two sets of ranges and return it.
1515 // Multiplications, divisions and shifts are a bit tricky to handle,
1516 // depending on the mix of signs we have in the two ranges, we need to
1517 // operate on different values to get the minimum and maximum values
1518 // for the new range. One approach is to figure out all the
1519 // variations of range combinations and do the operations.
1521 // However, this involves several calls to compare_values and it is
1522 // pretty convoluted. It's simpler to do the 4 operations (MIN0 OP
1523 // MIN1, MIN0 OP MAX1, MAX0 OP MIN1 and MAX0 OP MAX0 OP MAX1) and then
1524 // figure the smallest and largest values to form the new range.
1527 cross_product_operator::wi_cross_product (irange
&r
, tree type
,
1528 const wide_int
&lh_lb
,
1529 const wide_int
&lh_ub
,
1530 const wide_int
&rh_lb
,
1531 const wide_int
&rh_ub
) const
1533 wide_int cp1
, cp2
, cp3
, cp4
;
1534 // Default to varying.
1535 r
.set_varying (type
);
1537 // Compute the 4 cross operations, bailing if we get an overflow we
1539 if (wi_op_overflows (cp1
, type
, lh_lb
, rh_lb
))
1541 if (wi::eq_p (lh_lb
, lh_ub
))
1543 else if (wi_op_overflows (cp3
, type
, lh_ub
, rh_lb
))
1545 if (wi::eq_p (rh_lb
, rh_ub
))
1547 else if (wi_op_overflows (cp2
, type
, lh_lb
, rh_ub
))
1549 if (wi::eq_p (lh_lb
, lh_ub
))
1551 else if (wi_op_overflows (cp4
, type
, lh_ub
, rh_ub
))
1555 signop sign
= TYPE_SIGN (type
);
1556 if (wi::gt_p (cp1
, cp2
, sign
))
1557 std::swap (cp1
, cp2
);
1558 if (wi::gt_p (cp3
, cp4
, sign
))
1559 std::swap (cp3
, cp4
);
1561 // Choose min and max from the ordered pairs.
1562 wide_int res_lb
= wi::min (cp1
, cp3
, sign
);
1563 wide_int res_ub
= wi::max (cp2
, cp4
, sign
);
1564 value_range_with_overflow (r
, type
, res_lb
, res_ub
);
1568 class operator_mult
: public cross_product_operator
1571 virtual void wi_fold (irange
&r
, tree type
,
1572 const wide_int
&lh_lb
,
1573 const wide_int
&lh_ub
,
1574 const wide_int
&rh_lb
,
1575 const wide_int
&rh_ub
) const;
1576 virtual bool wi_op_overflows (wide_int
&res
, tree type
,
1577 const wide_int
&w0
, const wide_int
&w1
) const;
1578 virtual bool op1_range (irange
&r
, tree type
,
1581 relation_kind rel ATTRIBUTE_UNUSED
) const;
1582 virtual bool op2_range (irange
&r
, tree type
,
1585 relation_kind rel ATTRIBUTE_UNUSED
) const;
1589 operator_mult::op1_range (irange
&r
, tree type
,
1590 const irange
&lhs
, const irange
&op2
,
1591 relation_kind rel ATTRIBUTE_UNUSED
) const
1595 // We can't solve 0 = OP1 * N by dividing by N with a wrapping type.
1596 // For example: For 0 = OP1 * 2, OP1 could be 0, or MAXINT, whereas
1597 // for 4 = OP1 * 2, OP1 could be 2 or 130 (unsigned 8-bit)
1598 if (TYPE_OVERFLOW_WRAPS (type
))
1601 if (op2
.singleton_p (&offset
) && !integer_zerop (offset
))
1602 return range_op_handler (TRUNC_DIV_EXPR
, type
)->fold_range (r
, type
,
1608 operator_mult::op2_range (irange
&r
, tree type
,
1609 const irange
&lhs
, const irange
&op1
,
1610 relation_kind rel
) const
1612 return operator_mult::op1_range (r
, type
, lhs
, op1
, rel
);
1616 operator_mult::wi_op_overflows (wide_int
&res
, tree type
,
1617 const wide_int
&w0
, const wide_int
&w1
) const
1619 wi::overflow_type overflow
= wi::OVF_NONE
;
1620 signop sign
= TYPE_SIGN (type
);
1621 res
= wi::mul (w0
, w1
, sign
, &overflow
);
1622 if (overflow
&& TYPE_OVERFLOW_UNDEFINED (type
))
1624 // For multiplication, the sign of the overflow is given
1625 // by the comparison of the signs of the operands.
1626 if (sign
== UNSIGNED
|| w0
.sign_mask () == w1
.sign_mask ())
1627 res
= wi::max_value (w0
.get_precision (), sign
);
1629 res
= wi::min_value (w0
.get_precision (), sign
);
1636 operator_mult::wi_fold (irange
&r
, tree type
,
1637 const wide_int
&lh_lb
, const wide_int
&lh_ub
,
1638 const wide_int
&rh_lb
, const wide_int
&rh_ub
) const
1640 if (TYPE_OVERFLOW_UNDEFINED (type
))
1642 wi_cross_product (r
, type
, lh_lb
, lh_ub
, rh_lb
, rh_ub
);
1646 // Multiply the ranges when overflow wraps. This is basically fancy
1647 // code so we don't drop to varying with an unsigned
1650 // This test requires 2*prec bits if both operands are signed and
1651 // 2*prec + 2 bits if either is not. Therefore, extend the values
1652 // using the sign of the result to PREC2. From here on out,
1653 // everthing is just signed math no matter what the input types
1656 signop sign
= TYPE_SIGN (type
);
1657 unsigned prec
= TYPE_PRECISION (type
);
1658 widest2_int min0
= widest2_int::from (lh_lb
, sign
);
1659 widest2_int max0
= widest2_int::from (lh_ub
, sign
);
1660 widest2_int min1
= widest2_int::from (rh_lb
, sign
);
1661 widest2_int max1
= widest2_int::from (rh_ub
, sign
);
1662 widest2_int sizem1
= wi::mask
<widest2_int
> (prec
, false);
1663 widest2_int size
= sizem1
+ 1;
1665 // Canonicalize the intervals.
1666 if (sign
== UNSIGNED
)
1668 if (wi::ltu_p (size
, min0
+ max0
))
1673 if (wi::ltu_p (size
, min1
+ max1
))
1680 // Sort the 4 products so that min is in prod0 and max is in
1682 widest2_int prod0
= min0
* min1
;
1683 widest2_int prod1
= min0
* max1
;
1684 widest2_int prod2
= max0
* min1
;
1685 widest2_int prod3
= max0
* max1
;
1687 // min0min1 > max0max1
1689 std::swap (prod0
, prod3
);
1691 // min0max1 > max0min1
1693 std::swap (prod1
, prod2
);
1696 std::swap (prod0
, prod1
);
1699 std::swap (prod2
, prod3
);
1702 prod2
= prod3
- prod0
;
1703 if (wi::geu_p (prod2
, sizem1
))
1704 // The range covers all values.
1705 r
.set_varying (type
);
1708 wide_int new_lb
= wide_int::from (prod0
, prec
, sign
);
1709 wide_int new_ub
= wide_int::from (prod3
, prec
, sign
);
1710 create_possibly_reversed_range (r
, type
, new_lb
, new_ub
);
1715 class operator_div
: public cross_product_operator
1718 operator_div (enum tree_code c
) { code
= c
; }
1719 virtual void wi_fold (irange
&r
, tree type
,
1720 const wide_int
&lh_lb
,
1721 const wide_int
&lh_ub
,
1722 const wide_int
&rh_lb
,
1723 const wide_int
&rh_ub
) const;
1724 virtual bool wi_op_overflows (wide_int
&res
, tree type
,
1725 const wide_int
&, const wide_int
&) const;
1727 enum tree_code code
;
1731 operator_div::wi_op_overflows (wide_int
&res
, tree type
,
1732 const wide_int
&w0
, const wide_int
&w1
) const
1737 wi::overflow_type overflow
= wi::OVF_NONE
;
1738 signop sign
= TYPE_SIGN (type
);
1742 case EXACT_DIV_EXPR
:
1743 // EXACT_DIV_EXPR is implemented as TRUNC_DIV_EXPR in
1744 // operator_exact_divide. No need to handle it here.
1747 case TRUNC_DIV_EXPR
:
1748 res
= wi::div_trunc (w0
, w1
, sign
, &overflow
);
1750 case FLOOR_DIV_EXPR
:
1751 res
= wi::div_floor (w0
, w1
, sign
, &overflow
);
1753 case ROUND_DIV_EXPR
:
1754 res
= wi::div_round (w0
, w1
, sign
, &overflow
);
1757 res
= wi::div_ceil (w0
, w1
, sign
, &overflow
);
1763 if (overflow
&& TYPE_OVERFLOW_UNDEFINED (type
))
1765 // For division, the only case is -INF / -1 = +INF.
1766 res
= wi::max_value (w0
.get_precision (), sign
);
1773 operator_div::wi_fold (irange
&r
, tree type
,
1774 const wide_int
&lh_lb
, const wide_int
&lh_ub
,
1775 const wide_int
&rh_lb
, const wide_int
&rh_ub
) const
1777 const wide_int dividend_min
= lh_lb
;
1778 const wide_int dividend_max
= lh_ub
;
1779 const wide_int divisor_min
= rh_lb
;
1780 const wide_int divisor_max
= rh_ub
;
1781 signop sign
= TYPE_SIGN (type
);
1782 unsigned prec
= TYPE_PRECISION (type
);
1783 wide_int extra_min
, extra_max
;
1785 // If we know we won't divide by zero, just do the division.
1786 if (!wi_includes_zero_p (type
, divisor_min
, divisor_max
))
1788 wi_cross_product (r
, type
, dividend_min
, dividend_max
,
1789 divisor_min
, divisor_max
);
1793 // If we're definitely dividing by zero, there's nothing to do.
1794 if (wi_zero_p (type
, divisor_min
, divisor_max
))
1800 // Perform the division in 2 parts, [LB, -1] and [1, UB], which will
1801 // skip any division by zero.
1803 // First divide by the negative numbers, if any.
1804 if (wi::neg_p (divisor_min
, sign
))
1805 wi_cross_product (r
, type
, dividend_min
, dividend_max
,
1806 divisor_min
, wi::minus_one (prec
));
1810 // Then divide by the non-zero positive numbers, if any.
1811 if (wi::gt_p (divisor_max
, wi::zero (prec
), sign
))
1814 wi_cross_product (tmp
, type
, dividend_min
, dividend_max
,
1815 wi::one (prec
), divisor_max
);
1818 // We shouldn't still have undefined here.
1819 gcc_checking_assert (!r
.undefined_p ());
1822 operator_div
op_trunc_div (TRUNC_DIV_EXPR
);
1823 operator_div
op_floor_div (FLOOR_DIV_EXPR
);
1824 operator_div
op_round_div (ROUND_DIV_EXPR
);
1825 operator_div
op_ceil_div (CEIL_DIV_EXPR
);
1828 class operator_exact_divide
: public operator_div
1831 operator_exact_divide () : operator_div (TRUNC_DIV_EXPR
) { }
1832 virtual bool op1_range (irange
&r
, tree type
,
1835 relation_kind rel ATTRIBUTE_UNUSED
) const;
1840 operator_exact_divide::op1_range (irange
&r
, tree type
,
1843 relation_kind rel ATTRIBUTE_UNUSED
) const
1846 // [2, 4] = op1 / [3,3] since its exact divide, no need to worry about
1847 // remainders in the endpoints, so op1 = [2,4] * [3,3] = [6,12].
1848 // We wont bother trying to enumerate all the in between stuff :-P
1849 // TRUE accuraacy is [6,6][9,9][12,12]. This is unlikely to matter most of
1850 // the time however.
1851 // If op2 is a multiple of 2, we would be able to set some non-zero bits.
1852 if (op2
.singleton_p (&offset
)
1853 && !integer_zerop (offset
))
1854 return range_op_handler (MULT_EXPR
, type
)->fold_range (r
, type
, lhs
, op2
);
1859 class operator_lshift
: public cross_product_operator
1862 virtual bool op1_range (irange
&r
, tree type
,
1865 relation_kind rel
= VREL_NONE
) const;
1866 virtual bool fold_range (irange
&r
, tree type
,
1869 relation_kind rel
= VREL_NONE
) const;
1871 virtual void wi_fold (irange
&r
, tree type
,
1872 const wide_int
&lh_lb
, const wide_int
&lh_ub
,
1873 const wide_int
&rh_lb
, const wide_int
&rh_ub
) const;
1874 virtual bool wi_op_overflows (wide_int
&res
,
1877 const wide_int
&) const;
1880 class operator_rshift
: public cross_product_operator
1883 virtual bool fold_range (irange
&r
, tree type
,
1886 relation_kind rel
= VREL_NONE
) const;
1887 virtual void wi_fold (irange
&r
, tree type
,
1888 const wide_int
&lh_lb
,
1889 const wide_int
&lh_ub
,
1890 const wide_int
&rh_lb
,
1891 const wide_int
&rh_ub
) const;
1892 virtual bool wi_op_overflows (wide_int
&res
,
1895 const wide_int
&w1
) const;
1896 virtual bool op1_range (irange
&, tree type
,
1899 relation_kind rel
= VREL_NONE
) const;
1900 virtual enum tree_code
lhs_op1_relation (const irange
&lhs
,
1902 const irange
&op2
) const;
1907 operator_rshift::lhs_op1_relation (const irange
&lhs ATTRIBUTE_UNUSED
,
1909 const irange
&op2
) const
1911 // If both operands range are >= 0, then the LHS <= op1.
1912 if (!op1
.undefined_p () && !op2
.undefined_p ()
1913 && wi::ge_p (op1
.lower_bound (), 0, TYPE_SIGN (op1
.type ()))
1914 && wi::ge_p (op2
.lower_bound (), 0, TYPE_SIGN (op2
.type ())))
1920 operator_lshift::fold_range (irange
&r
, tree type
,
1923 relation_kind rel
) const
1925 int_range_max shift_range
;
1926 if (!get_shift_range (shift_range
, type
, op2
))
1928 if (op2
.undefined_p ())
1931 r
.set_varying (type
);
1935 // Transform left shifts by constants into multiplies.
1936 if (shift_range
.singleton_p ())
1938 unsigned shift
= shift_range
.lower_bound ().to_uhwi ();
1939 wide_int tmp
= wi::set_bit_in_zero (shift
, TYPE_PRECISION (type
));
1940 int_range
<1> mult (type
, tmp
, tmp
);
1942 // Force wrapping multiplication.
1943 bool saved_flag_wrapv
= flag_wrapv
;
1944 bool saved_flag_wrapv_pointer
= flag_wrapv_pointer
;
1946 flag_wrapv_pointer
= 1;
1947 bool b
= op_mult
.fold_range (r
, type
, op1
, mult
);
1948 flag_wrapv
= saved_flag_wrapv
;
1949 flag_wrapv_pointer
= saved_flag_wrapv_pointer
;
1953 // Otherwise, invoke the generic fold routine.
1954 return range_operator::fold_range (r
, type
, op1
, shift_range
, rel
);
1958 operator_lshift::wi_fold (irange
&r
, tree type
,
1959 const wide_int
&lh_lb
, const wide_int
&lh_ub
,
1960 const wide_int
&rh_lb
, const wide_int
&rh_ub
) const
1962 signop sign
= TYPE_SIGN (type
);
1963 unsigned prec
= TYPE_PRECISION (type
);
1964 int overflow_pos
= sign
== SIGNED
? prec
- 1 : prec
;
1965 int bound_shift
= overflow_pos
- rh_ub
.to_shwi ();
1966 // If bound_shift == HOST_BITS_PER_WIDE_INT, the llshift can
1967 // overflow. However, for that to happen, rh.max needs to be zero,
1968 // which means rh is a singleton range of zero, which means we simply return
1969 // [lh_lb, lh_ub] as the range.
1970 if (wi::eq_p (rh_ub
, rh_lb
) && wi::eq_p (rh_ub
, 0))
1972 r
= int_range
<2> (type
, lh_lb
, lh_ub
);
1976 wide_int bound
= wi::set_bit_in_zero (bound_shift
, prec
);
1977 wide_int complement
= ~(bound
- 1);
1978 wide_int low_bound
, high_bound
;
1979 bool in_bounds
= false;
1981 if (sign
== UNSIGNED
)
1984 high_bound
= complement
;
1985 if (wi::ltu_p (lh_ub
, low_bound
))
1987 // [5, 6] << [1, 2] == [10, 24].
1988 // We're shifting out only zeroes, the value increases
1992 else if (wi::ltu_p (high_bound
, lh_lb
))
1994 // [0xffffff00, 0xffffffff] << [1, 2]
1995 // == [0xfffffc00, 0xfffffffe].
1996 // We're shifting out only ones, the value decreases
2003 // [-1, 1] << [1, 2] == [-4, 4]
2004 low_bound
= complement
;
2006 if (wi::lts_p (lh_ub
, high_bound
)
2007 && wi::lts_p (low_bound
, lh_lb
))
2009 // For non-negative numbers, we're shifting out only zeroes,
2010 // the value increases monotonically. For negative numbers,
2011 // we're shifting out only ones, the value decreases
2018 wi_cross_product (r
, type
, lh_lb
, lh_ub
, rh_lb
, rh_ub
);
2020 r
.set_varying (type
);
2024 operator_lshift::wi_op_overflows (wide_int
&res
, tree type
,
2025 const wide_int
&w0
, const wide_int
&w1
) const
2027 signop sign
= TYPE_SIGN (type
);
2030 // It's unclear from the C standard whether shifts can overflow.
2031 // The following code ignores overflow; perhaps a C standard
2032 // interpretation ruling is needed.
2033 res
= wi::rshift (w0
, -w1
, sign
);
2036 res
= wi::lshift (w0
, w1
);
2041 operator_lshift::op1_range (irange
&r
,
2045 relation_kind rel ATTRIBUTE_UNUSED
) const
2049 if (!lhs
.contains_p (build_zero_cst (type
)))
2050 r
.set_nonzero (type
);
2052 r
.set_varying (type
);
2054 if (op2
.singleton_p (&shift_amount
))
2056 wide_int shift
= wi::to_wide (shift_amount
);
2057 if (wi::lt_p (shift
, 0, SIGNED
))
2059 if (wi::ge_p (shift
, wi::uhwi (TYPE_PRECISION (type
),
2060 TYPE_PRECISION (op2
.type ())),
2069 // Work completely in unsigned mode to start.
2071 int_range_max tmp_range
;
2072 if (TYPE_SIGN (type
) == SIGNED
)
2074 int_range_max tmp
= lhs
;
2075 utype
= unsigned_type_for (type
);
2076 range_cast (tmp
, utype
);
2077 op_rshift
.fold_range (tmp_range
, utype
, tmp
, op2
);
2080 op_rshift
.fold_range (tmp_range
, utype
, lhs
, op2
);
2082 // Start with ranges which can produce the LHS by right shifting the
2083 // result by the shift amount.
2084 // ie [0x08, 0xF0] = op1 << 2 will start with
2085 // [00001000, 11110000] = op1 << 2
2086 // [0x02, 0x4C] aka [00000010, 00111100]
2088 // Then create a range from the LB with the least significant upper bit
2089 // set, to the upper bound with all the bits set.
2090 // This would be [0x42, 0xFC] aka [01000010, 11111100].
2092 // Ideally we do this for each subrange, but just lump them all for now.
2093 unsigned low_bits
= TYPE_PRECISION (utype
)
2094 - TREE_INT_CST_LOW (shift_amount
);
2095 wide_int up_mask
= wi::mask (low_bits
, true, TYPE_PRECISION (utype
));
2096 wide_int new_ub
= wi::bit_or (up_mask
, tmp_range
.upper_bound ());
2097 wide_int new_lb
= wi::set_bit (tmp_range
.lower_bound (), low_bits
);
2098 int_range
<2> fill_range (utype
, new_lb
, new_ub
);
2099 tmp_range
.union_ (fill_range
);
2102 range_cast (tmp_range
, type
);
2104 r
.intersect (tmp_range
);
2108 return !r
.varying_p ();
2112 operator_rshift::op1_range (irange
&r
,
2116 relation_kind rel ATTRIBUTE_UNUSED
) const
2119 if (op2
.singleton_p (&shift
))
2121 // Ignore nonsensical shifts.
2122 unsigned prec
= TYPE_PRECISION (type
);
2123 if (wi::ge_p (wi::to_wide (shift
),
2124 wi::uhwi (prec
, TYPE_PRECISION (TREE_TYPE (shift
))),
2127 if (wi::to_wide (shift
) == 0)
2133 // Folding the original operation may discard some impossible
2134 // ranges from the LHS.
2135 int_range_max lhs_refined
;
2136 op_rshift
.fold_range (lhs_refined
, type
, int_range
<1> (type
), op2
);
2137 lhs_refined
.intersect (lhs
);
2138 if (lhs_refined
.undefined_p ())
2143 int_range_max
shift_range (shift
, shift
);
2144 int_range_max lb
, ub
;
2145 op_lshift
.fold_range (lb
, type
, lhs_refined
, shift_range
);
2147 // 0000 0111 = OP1 >> 3
2149 // OP1 is anything from 0011 1000 to 0011 1111. That is, a
2150 // range from LHS<<3 plus a mask of the 3 bits we shifted on the
2151 // right hand side (0x07).
2152 tree mask
= fold_build1 (BIT_NOT_EXPR
, type
,
2153 fold_build2 (LSHIFT_EXPR
, type
,
2154 build_minus_one_cst (type
),
2156 int_range_max
mask_range (build_zero_cst (type
), mask
);
2157 op_plus
.fold_range (ub
, type
, lb
, mask_range
);
2160 if (!lhs_refined
.contains_p (build_zero_cst (type
)))
2162 mask_range
.invert ();
2163 r
.intersect (mask_range
);
2171 operator_rshift::wi_op_overflows (wide_int
&res
,
2174 const wide_int
&w1
) const
2176 signop sign
= TYPE_SIGN (type
);
2178 res
= wi::lshift (w0
, -w1
);
2181 // It's unclear from the C standard whether shifts can overflow.
2182 // The following code ignores overflow; perhaps a C standard
2183 // interpretation ruling is needed.
2184 res
= wi::rshift (w0
, w1
, sign
);
2190 operator_rshift::fold_range (irange
&r
, tree type
,
2193 relation_kind rel
) const
2195 int_range_max shift
;
2196 if (!get_shift_range (shift
, type
, op2
))
2198 if (op2
.undefined_p ())
2201 r
.set_varying (type
);
2205 return range_operator::fold_range (r
, type
, op1
, shift
, rel
);
2209 operator_rshift::wi_fold (irange
&r
, tree type
,
2210 const wide_int
&lh_lb
, const wide_int
&lh_ub
,
2211 const wide_int
&rh_lb
, const wide_int
&rh_ub
) const
2213 wi_cross_product (r
, type
, lh_lb
, lh_ub
, rh_lb
, rh_ub
);
2217 class operator_cast
: public range_operator
2220 virtual bool fold_range (irange
&r
, tree type
,
2223 relation_kind rel
= VREL_NONE
) const;
2224 virtual bool op1_range (irange
&r
, tree type
,
2227 relation_kind rel
= VREL_NONE
) const;
2229 bool truncating_cast_p (const irange
&inner
, const irange
&outer
) const;
2230 bool inside_domain_p (const wide_int
&min
, const wide_int
&max
,
2231 const irange
&outer
) const;
2232 void fold_pair (irange
&r
, unsigned index
, const irange
&inner
,
2233 const irange
&outer
) const;
2236 // Return TRUE if casting from INNER to OUTER is a truncating cast.
2239 operator_cast::truncating_cast_p (const irange
&inner
,
2240 const irange
&outer
) const
2242 return TYPE_PRECISION (outer
.type ()) < TYPE_PRECISION (inner
.type ());
2245 // Return TRUE if [MIN,MAX] is inside the domain of RANGE's type.
2248 operator_cast::inside_domain_p (const wide_int
&min
,
2249 const wide_int
&max
,
2250 const irange
&range
) const
2252 wide_int domain_min
= wi::to_wide (vrp_val_min (range
.type ()));
2253 wide_int domain_max
= wi::to_wide (vrp_val_max (range
.type ()));
2254 signop domain_sign
= TYPE_SIGN (range
.type ());
2255 return (wi::le_p (min
, domain_max
, domain_sign
)
2256 && wi::le_p (max
, domain_max
, domain_sign
)
2257 && wi::ge_p (min
, domain_min
, domain_sign
)
2258 && wi::ge_p (max
, domain_min
, domain_sign
));
2262 // Helper for fold_range which work on a pair at a time.
2265 operator_cast::fold_pair (irange
&r
, unsigned index
,
2266 const irange
&inner
,
2267 const irange
&outer
) const
2269 tree inner_type
= inner
.type ();
2270 tree outer_type
= outer
.type ();
2271 signop inner_sign
= TYPE_SIGN (inner_type
);
2272 unsigned outer_prec
= TYPE_PRECISION (outer_type
);
2274 // check to see if casting from INNER to OUTER is a conversion that
2275 // fits in the resulting OUTER type.
2276 wide_int inner_lb
= inner
.lower_bound (index
);
2277 wide_int inner_ub
= inner
.upper_bound (index
);
2278 if (truncating_cast_p (inner
, outer
))
2280 // We may be able to accomodate a truncating cast if the
2281 // resulting range can be represented in the target type...
2282 if (wi::rshift (wi::sub (inner_ub
, inner_lb
),
2283 wi::uhwi (outer_prec
, TYPE_PRECISION (inner
.type ())),
2286 r
.set_varying (outer_type
);
2290 // ...but we must still verify that the final range fits in the
2291 // domain. This catches -fstrict-enum restrictions where the domain
2292 // range is smaller than what fits in the underlying type.
2293 wide_int min
= wide_int::from (inner_lb
, outer_prec
, inner_sign
);
2294 wide_int max
= wide_int::from (inner_ub
, outer_prec
, inner_sign
);
2295 if (inside_domain_p (min
, max
, outer
))
2296 create_possibly_reversed_range (r
, outer_type
, min
, max
);
2298 r
.set_varying (outer_type
);
2303 operator_cast::fold_range (irange
&r
, tree type ATTRIBUTE_UNUSED
,
2304 const irange
&inner
,
2305 const irange
&outer
,
2306 relation_kind rel ATTRIBUTE_UNUSED
) const
2308 if (empty_range_varying (r
, type
, inner
, outer
))
2311 gcc_checking_assert (outer
.varying_p ());
2312 gcc_checking_assert (inner
.num_pairs () > 0);
2314 // Avoid a temporary by folding the first pair directly into the result.
2315 fold_pair (r
, 0, inner
, outer
);
2317 // Then process any additonal pairs by unioning with their results.
2318 for (unsigned x
= 1; x
< inner
.num_pairs (); ++x
)
2321 fold_pair (tmp
, x
, inner
, outer
);
2330 operator_cast::op1_range (irange
&r
, tree type
,
2333 relation_kind rel ATTRIBUTE_UNUSED
) const
2335 tree lhs_type
= lhs
.type ();
2336 gcc_checking_assert (types_compatible_p (op2
.type(), type
));
2338 // If we are calculating a pointer, shortcut to what we really care about.
2339 if (POINTER_TYPE_P (type
))
2341 // Conversion from other pointers or a constant (including 0/NULL)
2342 // are straightforward.
2343 if (POINTER_TYPE_P (lhs
.type ())
2344 || (lhs
.singleton_p ()
2345 && TYPE_PRECISION (lhs
.type ()) >= TYPE_PRECISION (type
)))
2348 range_cast (r
, type
);
2352 // If the LHS is not a pointer nor a singleton, then it is
2353 // either VARYING or non-zero.
2354 if (!lhs
.contains_p (build_zero_cst (lhs
.type ())))
2355 r
.set_nonzero (type
);
2357 r
.set_varying (type
);
2363 if (truncating_cast_p (op2
, lhs
))
2365 if (lhs
.varying_p ())
2366 r
.set_varying (type
);
2369 // We want to insert the LHS as an unsigned value since it
2370 // would not trigger the signed bit of the larger type.
2371 int_range_max converted_lhs
= lhs
;
2372 range_cast (converted_lhs
, unsigned_type_for (lhs_type
));
2373 range_cast (converted_lhs
, type
);
2374 // Start by building the positive signed outer range for the type.
2375 wide_int lim
= wi::set_bit_in_zero (TYPE_PRECISION (lhs_type
),
2376 TYPE_PRECISION (type
));
2377 r
= int_range
<1> (type
, lim
, wi::max_value (TYPE_PRECISION (type
),
2379 // For the signed part, we need to simply union the 2 ranges now.
2380 r
.union_ (converted_lhs
);
2382 // Create maximal negative number outside of LHS bits.
2383 lim
= wi::mask (TYPE_PRECISION (lhs_type
), true,
2384 TYPE_PRECISION (type
));
2385 // Add this to the unsigned LHS range(s).
2386 int_range_max
lim_range (type
, lim
, lim
);
2387 int_range_max lhs_neg
;
2388 range_op_handler (PLUS_EXPR
, type
)->fold_range (lhs_neg
,
2392 // lhs_neg now has all the negative versions of the LHS.
2393 // Now union in all the values from SIGNED MIN (0x80000) to
2394 // lim-1 in order to fill in all the ranges with the upper
2397 // PR 97317. If the lhs has only 1 bit less precision than the rhs,
2398 // we don't need to create a range from min to lim-1
2399 // calculate neg range traps trying to create [lim, lim - 1].
2400 wide_int min_val
= wi::min_value (TYPE_PRECISION (type
), SIGNED
);
2403 int_range_max
neg (type
,
2404 wi::min_value (TYPE_PRECISION (type
),
2407 lhs_neg
.union_ (neg
);
2409 // And finally, munge the signed and unsigned portions.
2412 // And intersect with any known value passed in the extra operand.
2418 if (TYPE_PRECISION (lhs_type
) == TYPE_PRECISION (type
))
2422 // The cast is not truncating, and the range is restricted to
2423 // the range of the RHS by this assignment.
2425 // Cast the range of the RHS to the type of the LHS.
2426 fold_range (tmp
, lhs_type
, int_range
<1> (type
), int_range
<1> (lhs_type
));
2427 // Intersect this with the LHS range will produce the range,
2428 // which will be cast to the RHS type before returning.
2429 tmp
.intersect (lhs
);
2432 // Cast the calculated range to the type of the RHS.
2433 fold_range (r
, type
, tmp
, int_range
<1> (type
));
2438 class operator_logical_and
: public range_operator
2441 virtual bool fold_range (irange
&r
, tree type
,
2444 relation_kind rel
= VREL_NONE
) const;
2445 virtual bool op1_range (irange
&r
, tree type
,
2448 relation_kind rel
= VREL_NONE
) const;
2449 virtual bool op2_range (irange
&r
, tree type
,
2452 relation_kind rel
= VREL_NONE
) const;
2457 operator_logical_and::fold_range (irange
&r
, tree type
,
2460 relation_kind rel ATTRIBUTE_UNUSED
) const
2462 if (empty_range_varying (r
, type
, lh
, rh
))
2465 // 0 && anything is 0.
2466 if ((wi::eq_p (lh
.lower_bound (), 0) && wi::eq_p (lh
.upper_bound (), 0))
2467 || (wi::eq_p (lh
.lower_bound (), 0) && wi::eq_p (rh
.upper_bound (), 0)))
2468 r
= range_false (type
);
2469 else if (lh
.contains_p (build_zero_cst (lh
.type ()))
2470 || rh
.contains_p (build_zero_cst (rh
.type ())))
2471 // To reach this point, there must be a logical 1 on each side, and
2472 // the only remaining question is whether there is a zero or not.
2473 r
= range_true_and_false (type
);
2475 r
= range_true (type
);
2480 operator_logical_and::op1_range (irange
&r
, tree type
,
2482 const irange
&op2 ATTRIBUTE_UNUSED
,
2483 relation_kind rel ATTRIBUTE_UNUSED
) const
2485 switch (get_bool_state (r
, lhs
, type
))
2488 // A true result means both sides of the AND must be true.
2489 r
= range_true (type
);
2492 // Any other result means only one side has to be false, the
2493 // other side can be anything. So we cannot be sure of any
2495 r
= range_true_and_false (type
);
2502 operator_logical_and::op2_range (irange
&r
, tree type
,
2505 relation_kind rel ATTRIBUTE_UNUSED
) const
2507 return operator_logical_and::op1_range (r
, type
, lhs
, op1
);
2511 class operator_bitwise_and
: public range_operator
2514 virtual bool fold_range (irange
&r
, tree type
,
2517 relation_kind rel
= VREL_NONE
) const;
2518 virtual bool op1_range (irange
&r
, tree type
,
2521 relation_kind rel
= VREL_NONE
) const;
2522 virtual bool op2_range (irange
&r
, tree type
,
2525 relation_kind rel
= VREL_NONE
) const;
2526 virtual void wi_fold (irange
&r
, tree type
,
2527 const wide_int
&lh_lb
,
2528 const wide_int
&lh_ub
,
2529 const wide_int
&rh_lb
,
2530 const wide_int
&rh_ub
) const;
2532 void simple_op1_range_solver (irange
&r
, tree type
,
2534 const irange
&op2
) const;
2535 void remove_impossible_ranges (irange
&r
, const irange
&rh
) const;
2539 unsigned_singleton_p (const irange
&op
)
2542 if (op
.singleton_p (&mask
))
2544 wide_int x
= wi::to_wide (mask
);
2545 return wi::ge_p (x
, 0, TYPE_SIGN (op
.type ()));
2550 // Remove any ranges from R that are known to be impossible when an
2551 // range is ANDed with MASK.
2554 operator_bitwise_and::remove_impossible_ranges (irange
&r
,
2555 const irange
&rmask
) const
2557 if (r
.undefined_p () || !unsigned_singleton_p (rmask
))
2560 wide_int mask
= rmask
.lower_bound ();
2561 tree type
= r
.type ();
2562 int prec
= TYPE_PRECISION (type
);
2563 int leading_zeros
= wi::clz (mask
);
2564 int_range_max impossible_ranges
;
2566 /* We know that starting at the most significant bit, any 0 in the
2567 mask means the resulting range cannot contain a 1 in that same
2568 position. This means the following ranges are impossible:
2572 01xx xxxx [0100 0000, 0111 1111]
2573 001x xxxx [0010 0000, 0011 1111]
2574 0000 01xx [0000 0100, 0000 0111]
2575 0000 0001 [0000 0001, 0000 0001]
2577 wide_int one
= wi::one (prec
);
2578 for (int i
= 0; i
< prec
- leading_zeros
- 1; ++i
)
2579 if (wi::bit_and (mask
, wi::lshift (one
, wi::uhwi (i
, prec
))) == 0)
2581 tree lb
= fold_build2 (LSHIFT_EXPR
, type
,
2582 build_one_cst (type
),
2583 build_int_cst (type
, i
));
2584 tree ub_left
= fold_build1 (BIT_NOT_EXPR
, type
,
2585 fold_build2 (LSHIFT_EXPR
, type
,
2586 build_minus_one_cst (type
),
2587 build_int_cst (type
, i
)));
2588 tree ub_right
= fold_build2 (LSHIFT_EXPR
, type
,
2589 build_one_cst (type
),
2590 build_int_cst (type
, i
));
2591 tree ub
= fold_build2 (BIT_IOR_EXPR
, type
, ub_left
, ub_right
);
2592 impossible_ranges
.union_ (int_range
<1> (lb
, ub
));
2594 if (!impossible_ranges
.undefined_p ())
2596 impossible_ranges
.invert ();
2597 r
.intersect (impossible_ranges
);
2602 operator_bitwise_and::fold_range (irange
&r
, tree type
,
2605 relation_kind rel ATTRIBUTE_UNUSED
) const
2607 if (range_operator::fold_range (r
, type
, lh
, rh
))
2609 // FIXME: This is temporarily disabled because, though it
2610 // generates better ranges, it's noticeably slower for evrp.
2611 // remove_impossible_ranges (r, rh);
2618 // Optimize BIT_AND_EXPR, BIT_IOR_EXPR and BIT_XOR_EXPR of signed types
2619 // by considering the number of leading redundant sign bit copies.
2620 // clrsb (X op Y) = min (clrsb (X), clrsb (Y)), so for example
2621 // [-1, 0] op [-1, 0] is [-1, 0] (where nonzero_bits doesn't help).
2623 wi_optimize_signed_bitwise_op (irange
&r
, tree type
,
2624 const wide_int
&lh_lb
, const wide_int
&lh_ub
,
2625 const wide_int
&rh_lb
, const wide_int
&rh_ub
)
2627 int lh_clrsb
= MIN (wi::clrsb (lh_lb
), wi::clrsb (lh_ub
));
2628 int rh_clrsb
= MIN (wi::clrsb (rh_lb
), wi::clrsb (rh_ub
));
2629 int new_clrsb
= MIN (lh_clrsb
, rh_clrsb
);
2632 int type_prec
= TYPE_PRECISION (type
);
2633 int rprec
= (type_prec
- new_clrsb
) - 1;
2634 value_range_with_overflow (r
, type
,
2635 wi::mask (rprec
, true, type_prec
),
2636 wi::mask (rprec
, false, type_prec
));
2641 // Optimize BIT_AND_EXPR and BIT_IOR_EXPR in terms of a mask if
2642 // possible. Basically, see if we can optimize:
2646 // [LB op Z, UB op Z]
2648 // If the optimization was successful, accumulate the range in R and
2652 wi_optimize_and_or (irange
&r
,
2653 enum tree_code code
,
2655 const wide_int
&lh_lb
, const wide_int
&lh_ub
,
2656 const wide_int
&rh_lb
, const wide_int
&rh_ub
)
2658 // Calculate the singleton mask among the ranges, if any.
2659 wide_int lower_bound
, upper_bound
, mask
;
2660 if (wi::eq_p (rh_lb
, rh_ub
))
2663 lower_bound
= lh_lb
;
2664 upper_bound
= lh_ub
;
2666 else if (wi::eq_p (lh_lb
, lh_ub
))
2669 lower_bound
= rh_lb
;
2670 upper_bound
= rh_ub
;
2675 // If Z is a constant which (for op | its bitwise not) has n
2676 // consecutive least significant bits cleared followed by m 1
2677 // consecutive bits set immediately above it and either
2678 // m + n == precision, or (x >> (m + n)) == (y >> (m + n)).
2680 // The least significant n bits of all the values in the range are
2681 // cleared or set, the m bits above it are preserved and any bits
2682 // above these are required to be the same for all values in the
2686 if (code
== BIT_IOR_EXPR
)
2688 if (wi::eq_p (w
, 0))
2689 n
= w
.get_precision ();
2693 w
= ~(w
| wi::mask (n
, false, w
.get_precision ()));
2694 if (wi::eq_p (w
, 0))
2695 m
= w
.get_precision () - n
;
2697 m
= wi::ctz (w
) - n
;
2699 wide_int new_mask
= wi::mask (m
+ n
, true, w
.get_precision ());
2700 if ((new_mask
& lower_bound
) != (new_mask
& upper_bound
))
2703 wide_int res_lb
, res_ub
;
2704 if (code
== BIT_AND_EXPR
)
2706 res_lb
= wi::bit_and (lower_bound
, mask
);
2707 res_ub
= wi::bit_and (upper_bound
, mask
);
2709 else if (code
== BIT_IOR_EXPR
)
2711 res_lb
= wi::bit_or (lower_bound
, mask
);
2712 res_ub
= wi::bit_or (upper_bound
, mask
);
2716 value_range_with_overflow (r
, type
, res_lb
, res_ub
);
2718 // Furthermore, if the mask is non-zero, an IOR cannot contain zero.
2719 if (code
== BIT_IOR_EXPR
&& wi::ne_p (mask
, 0))
2722 tmp
.set_nonzero (type
);
2728 // For range [LB, UB] compute two wide_int bit masks.
2730 // In the MAYBE_NONZERO bit mask, if some bit is unset, it means that
2731 // for all numbers in the range the bit is 0, otherwise it might be 0
2734 // In the MUSTBE_NONZERO bit mask, if some bit is set, it means that
2735 // for all numbers in the range the bit is 1, otherwise it might be 0
2739 wi_set_zero_nonzero_bits (tree type
,
2740 const wide_int
&lb
, const wide_int
&ub
,
2741 wide_int
&maybe_nonzero
,
2742 wide_int
&mustbe_nonzero
)
2744 signop sign
= TYPE_SIGN (type
);
2746 if (wi::eq_p (lb
, ub
))
2747 maybe_nonzero
= mustbe_nonzero
= lb
;
2748 else if (wi::ge_p (lb
, 0, sign
) || wi::lt_p (ub
, 0, sign
))
2750 wide_int xor_mask
= lb
^ ub
;
2751 maybe_nonzero
= lb
| ub
;
2752 mustbe_nonzero
= lb
& ub
;
2755 wide_int mask
= wi::mask (wi::floor_log2 (xor_mask
), false,
2756 maybe_nonzero
.get_precision ());
2757 maybe_nonzero
= maybe_nonzero
| mask
;
2758 mustbe_nonzero
= wi::bit_and_not (mustbe_nonzero
, mask
);
2763 maybe_nonzero
= wi::minus_one (lb
.get_precision ());
2764 mustbe_nonzero
= wi::zero (lb
.get_precision ());
2769 operator_bitwise_and::wi_fold (irange
&r
, tree type
,
2770 const wide_int
&lh_lb
,
2771 const wide_int
&lh_ub
,
2772 const wide_int
&rh_lb
,
2773 const wide_int
&rh_ub
) const
2775 if (wi_optimize_and_or (r
, BIT_AND_EXPR
, type
, lh_lb
, lh_ub
, rh_lb
, rh_ub
))
2778 wide_int maybe_nonzero_lh
, mustbe_nonzero_lh
;
2779 wide_int maybe_nonzero_rh
, mustbe_nonzero_rh
;
2780 wi_set_zero_nonzero_bits (type
, lh_lb
, lh_ub
,
2781 maybe_nonzero_lh
, mustbe_nonzero_lh
);
2782 wi_set_zero_nonzero_bits (type
, rh_lb
, rh_ub
,
2783 maybe_nonzero_rh
, mustbe_nonzero_rh
);
2785 wide_int new_lb
= mustbe_nonzero_lh
& mustbe_nonzero_rh
;
2786 wide_int new_ub
= maybe_nonzero_lh
& maybe_nonzero_rh
;
2787 signop sign
= TYPE_SIGN (type
);
2788 unsigned prec
= TYPE_PRECISION (type
);
2789 // If both input ranges contain only negative values, we can
2790 // truncate the result range maximum to the minimum of the
2791 // input range maxima.
2792 if (wi::lt_p (lh_ub
, 0, sign
) && wi::lt_p (rh_ub
, 0, sign
))
2794 new_ub
= wi::min (new_ub
, lh_ub
, sign
);
2795 new_ub
= wi::min (new_ub
, rh_ub
, sign
);
2797 // If either input range contains only non-negative values
2798 // we can truncate the result range maximum to the respective
2799 // maximum of the input range.
2800 if (wi::ge_p (lh_lb
, 0, sign
))
2801 new_ub
= wi::min (new_ub
, lh_ub
, sign
);
2802 if (wi::ge_p (rh_lb
, 0, sign
))
2803 new_ub
= wi::min (new_ub
, rh_ub
, sign
);
2804 // PR68217: In case of signed & sign-bit-CST should
2805 // result in [-INF, 0] instead of [-INF, INF].
2806 if (wi::gt_p (new_lb
, new_ub
, sign
))
2808 wide_int sign_bit
= wi::set_bit_in_zero (prec
- 1, prec
);
2810 && ((wi::eq_p (lh_lb
, lh_ub
)
2811 && !wi::cmps (lh_lb
, sign_bit
))
2812 || (wi::eq_p (rh_lb
, rh_ub
)
2813 && !wi::cmps (rh_lb
, sign_bit
))))
2815 new_lb
= wi::min_value (prec
, sign
);
2816 new_ub
= wi::zero (prec
);
2819 // If the limits got swapped around, return varying.
2820 if (wi::gt_p (new_lb
, new_ub
,sign
))
2823 && wi_optimize_signed_bitwise_op (r
, type
,
2827 r
.set_varying (type
);
2830 value_range_with_overflow (r
, type
, new_lb
, new_ub
);
2834 set_nonzero_range_from_mask (irange
&r
, tree type
, const irange
&lhs
)
2836 if (!lhs
.contains_p (build_zero_cst (type
)))
2837 r
= range_nonzero (type
);
2839 r
.set_varying (type
);
2842 // This was shamelessly stolen from register_edge_assert_for_2 and
2843 // adjusted to work with iranges.
2846 operator_bitwise_and::simple_op1_range_solver (irange
&r
, tree type
,
2848 const irange
&op2
) const
2850 if (!op2
.singleton_p ())
2852 set_nonzero_range_from_mask (r
, type
, lhs
);
2855 unsigned int nprec
= TYPE_PRECISION (type
);
2856 wide_int cst2v
= op2
.lower_bound ();
2857 bool cst2n
= wi::neg_p (cst2v
, TYPE_SIGN (type
));
2860 sgnbit
= wi::set_bit_in_zero (nprec
- 1, nprec
);
2862 sgnbit
= wi::zero (nprec
);
2864 // Solve [lhs.lower_bound (), +INF] = x & MASK.
2866 // Minimum unsigned value for >= if (VAL & CST2) == VAL is VAL and
2867 // maximum unsigned value is ~0. For signed comparison, if CST2
2868 // doesn't have the most significant bit set, handle it similarly. If
2869 // CST2 has MSB set, the minimum is the same, and maximum is ~0U/2.
2870 wide_int valv
= lhs
.lower_bound ();
2871 wide_int minv
= valv
& cst2v
, maxv
;
2872 bool we_know_nothing
= false;
2875 // If (VAL & CST2) != VAL, X & CST2 can't be equal to VAL.
2876 minv
= masked_increment (valv
, cst2v
, sgnbit
, nprec
);
2879 // If we can't determine anything on this bound, fall
2880 // through and conservatively solve for the other end point.
2881 we_know_nothing
= true;
2884 maxv
= wi::mask (nprec
- (cst2n
? 1 : 0), false, nprec
);
2885 if (we_know_nothing
)
2886 r
.set_varying (type
);
2888 r
= int_range
<1> (type
, minv
, maxv
);
2890 // Solve [-INF, lhs.upper_bound ()] = x & MASK.
2892 // Minimum unsigned value for <= is 0 and maximum unsigned value is
2893 // VAL | ~CST2 if (VAL & CST2) == VAL. Otherwise, find smallest
2895 // VAL2 > VAL && (VAL2 & CST2) == VAL2 and use (VAL2 - 1) | ~CST2
2897 // For signed comparison, if CST2 doesn't have most significant bit
2898 // set, handle it similarly. If CST2 has MSB set, the maximum is
2899 // the same and minimum is INT_MIN.
2900 valv
= lhs
.upper_bound ();
2901 minv
= valv
& cst2v
;
2906 maxv
= masked_increment (valv
, cst2v
, sgnbit
, nprec
);
2909 // If we couldn't determine anything on either bound, return
2911 if (we_know_nothing
)
2919 int_range
<1> upper_bits (type
, minv
, maxv
);
2920 r
.intersect (upper_bits
);
2924 operator_bitwise_and::op1_range (irange
&r
, tree type
,
2927 relation_kind rel ATTRIBUTE_UNUSED
) const
2929 if (types_compatible_p (type
, boolean_type_node
))
2930 return op_logical_and
.op1_range (r
, type
, lhs
, op2
);
2933 for (unsigned i
= 0; i
< lhs
.num_pairs (); ++i
)
2935 int_range_max
chunk (lhs
.type (),
2936 lhs
.lower_bound (i
),
2937 lhs
.upper_bound (i
));
2939 simple_op1_range_solver (res
, type
, chunk
, op2
);
2942 if (r
.undefined_p ())
2943 set_nonzero_range_from_mask (r
, type
, lhs
);
2948 operator_bitwise_and::op2_range (irange
&r
, tree type
,
2951 relation_kind rel ATTRIBUTE_UNUSED
) const
2953 return operator_bitwise_and::op1_range (r
, type
, lhs
, op1
);
2957 class operator_logical_or
: public range_operator
2960 virtual bool fold_range (irange
&r
, tree type
,
2963 relation_kind rel
= VREL_NONE
) const;
2964 virtual bool op1_range (irange
&r
, tree type
,
2967 relation_kind rel
= VREL_NONE
) const;
2968 virtual bool op2_range (irange
&r
, tree type
,
2971 relation_kind rel
= VREL_NONE
) const;
2975 operator_logical_or::fold_range (irange
&r
, tree type ATTRIBUTE_UNUSED
,
2978 relation_kind rel ATTRIBUTE_UNUSED
) const
2980 if (empty_range_varying (r
, type
, lh
, rh
))
2989 operator_logical_or::op1_range (irange
&r
, tree type
,
2991 const irange
&op2 ATTRIBUTE_UNUSED
,
2992 relation_kind rel ATTRIBUTE_UNUSED
) const
2994 switch (get_bool_state (r
, lhs
, type
))
2997 // A false result means both sides of the OR must be false.
2998 r
= range_false (type
);
3001 // Any other result means only one side has to be true, the
3002 // other side can be anything. so we can't be sure of any result
3004 r
= range_true_and_false (type
);
3011 operator_logical_or::op2_range (irange
&r
, tree type
,
3014 relation_kind rel ATTRIBUTE_UNUSED
) const
3016 return operator_logical_or::op1_range (r
, type
, lhs
, op1
);
3020 class operator_bitwise_or
: public range_operator
3023 virtual bool op1_range (irange
&r
, tree type
,
3026 relation_kind rel
= VREL_NONE
) const;
3027 virtual bool op2_range (irange
&r
, tree type
,
3030 relation_kind rel
= VREL_NONE
) const;
3031 virtual void wi_fold (irange
&r
, tree type
,
3032 const wide_int
&lh_lb
,
3033 const wide_int
&lh_ub
,
3034 const wide_int
&rh_lb
,
3035 const wide_int
&rh_ub
) const;
3039 operator_bitwise_or::wi_fold (irange
&r
, tree type
,
3040 const wide_int
&lh_lb
,
3041 const wide_int
&lh_ub
,
3042 const wide_int
&rh_lb
,
3043 const wide_int
&rh_ub
) const
3045 if (wi_optimize_and_or (r
, BIT_IOR_EXPR
, type
, lh_lb
, lh_ub
, rh_lb
, rh_ub
))
3048 wide_int maybe_nonzero_lh
, mustbe_nonzero_lh
;
3049 wide_int maybe_nonzero_rh
, mustbe_nonzero_rh
;
3050 wi_set_zero_nonzero_bits (type
, lh_lb
, lh_ub
,
3051 maybe_nonzero_lh
, mustbe_nonzero_lh
);
3052 wi_set_zero_nonzero_bits (type
, rh_lb
, rh_ub
,
3053 maybe_nonzero_rh
, mustbe_nonzero_rh
);
3054 wide_int new_lb
= mustbe_nonzero_lh
| mustbe_nonzero_rh
;
3055 wide_int new_ub
= maybe_nonzero_lh
| maybe_nonzero_rh
;
3056 signop sign
= TYPE_SIGN (type
);
3057 // If the input ranges contain only positive values we can
3058 // truncate the minimum of the result range to the maximum
3059 // of the input range minima.
3060 if (wi::ge_p (lh_lb
, 0, sign
)
3061 && wi::ge_p (rh_lb
, 0, sign
))
3063 new_lb
= wi::max (new_lb
, lh_lb
, sign
);
3064 new_lb
= wi::max (new_lb
, rh_lb
, sign
);
3066 // If either input range contains only negative values
3067 // we can truncate the minimum of the result range to the
3068 // respective minimum range.
3069 if (wi::lt_p (lh_ub
, 0, sign
))
3070 new_lb
= wi::max (new_lb
, lh_lb
, sign
);
3071 if (wi::lt_p (rh_ub
, 0, sign
))
3072 new_lb
= wi::max (new_lb
, rh_lb
, sign
);
3073 // If the limits got swapped around, return a conservative range.
3074 if (wi::gt_p (new_lb
, new_ub
, sign
))
3076 // Make sure that nonzero|X is nonzero.
3077 if (wi::gt_p (lh_lb
, 0, sign
)
3078 || wi::gt_p (rh_lb
, 0, sign
)
3079 || wi::lt_p (lh_ub
, 0, sign
)
3080 || wi::lt_p (rh_ub
, 0, sign
))
3081 r
.set_nonzero (type
);
3082 else if (sign
== SIGNED
3083 && wi_optimize_signed_bitwise_op (r
, type
,
3088 r
.set_varying (type
);
3091 value_range_with_overflow (r
, type
, new_lb
, new_ub
);
3095 operator_bitwise_or::op1_range (irange
&r
, tree type
,
3098 relation_kind rel ATTRIBUTE_UNUSED
) const
3100 // If this is really a logical wi_fold, call that.
3101 if (types_compatible_p (type
, boolean_type_node
))
3102 return op_logical_or
.op1_range (r
, type
, lhs
, op2
);
3106 tree zero
= build_zero_cst (type
);
3107 r
= int_range
<1> (zero
, zero
);
3110 r
.set_varying (type
);
3115 operator_bitwise_or::op2_range (irange
&r
, tree type
,
3118 relation_kind rel ATTRIBUTE_UNUSED
) const
3120 return operator_bitwise_or::op1_range (r
, type
, lhs
, op1
);
3124 class operator_bitwise_xor
: public range_operator
3127 virtual void wi_fold (irange
&r
, tree type
,
3128 const wide_int
&lh_lb
,
3129 const wide_int
&lh_ub
,
3130 const wide_int
&rh_lb
,
3131 const wide_int
&rh_ub
) const;
3132 virtual bool op1_range (irange
&r
, tree type
,
3135 relation_kind rel
= VREL_NONE
) const;
3136 virtual bool op2_range (irange
&r
, tree type
,
3139 relation_kind rel
= VREL_NONE
) const;
3140 virtual bool op1_op2_relation_effect (irange
&lhs_range
,
3142 const irange
&op1_range
,
3143 const irange
&op2_range
,
3144 relation_kind rel
) const;
3148 operator_bitwise_xor::wi_fold (irange
&r
, tree type
,
3149 const wide_int
&lh_lb
,
3150 const wide_int
&lh_ub
,
3151 const wide_int
&rh_lb
,
3152 const wide_int
&rh_ub
) const
3154 signop sign
= TYPE_SIGN (type
);
3155 wide_int maybe_nonzero_lh
, mustbe_nonzero_lh
;
3156 wide_int maybe_nonzero_rh
, mustbe_nonzero_rh
;
3157 wi_set_zero_nonzero_bits (type
, lh_lb
, lh_ub
,
3158 maybe_nonzero_lh
, mustbe_nonzero_lh
);
3159 wi_set_zero_nonzero_bits (type
, rh_lb
, rh_ub
,
3160 maybe_nonzero_rh
, mustbe_nonzero_rh
);
3162 wide_int result_zero_bits
= ((mustbe_nonzero_lh
& mustbe_nonzero_rh
)
3163 | ~(maybe_nonzero_lh
| maybe_nonzero_rh
));
3164 wide_int result_one_bits
3165 = (wi::bit_and_not (mustbe_nonzero_lh
, maybe_nonzero_rh
)
3166 | wi::bit_and_not (mustbe_nonzero_rh
, maybe_nonzero_lh
));
3167 wide_int new_ub
= ~result_zero_bits
;
3168 wide_int new_lb
= result_one_bits
;
3170 // If the range has all positive or all negative values, the result
3171 // is better than VARYING.
3172 if (wi::lt_p (new_lb
, 0, sign
) || wi::ge_p (new_ub
, 0, sign
))
3173 value_range_with_overflow (r
, type
, new_lb
, new_ub
);
3174 else if (sign
== SIGNED
3175 && wi_optimize_signed_bitwise_op (r
, type
,
3180 r
.set_varying (type
);
3182 /* Furthermore, XOR is non-zero if its arguments can't be equal. */
3183 if (wi::lt_p (lh_ub
, rh_lb
, sign
)
3184 || wi::lt_p (rh_ub
, lh_lb
, sign
)
3185 || wi::ne_p (result_one_bits
, 0))
3188 tmp
.set_nonzero (type
);
3194 operator_bitwise_xor::op1_op2_relation_effect (irange
&lhs_range
,
3198 relation_kind rel
) const
3200 if (rel
== VREL_NONE
)
3203 int_range
<2> rel_range
;
3208 rel_range
.set_zero (type
);
3211 rel_range
.set_nonzero (type
);
3217 lhs_range
.intersect (rel_range
);
3222 operator_bitwise_xor::op1_range (irange
&r
, tree type
,
3225 relation_kind rel ATTRIBUTE_UNUSED
) const
3227 if (lhs
.undefined_p () || lhs
.varying_p ())
3232 if (types_compatible_p (type
, boolean_type_node
))
3234 switch (get_bool_state (r
, lhs
, type
))
3237 if (op2
.varying_p ())
3238 r
.set_varying (type
);
3239 else if (op2
.zero_p ())
3240 r
= range_true (type
);
3242 r
= range_false (type
);
3252 r
.set_varying (type
);
3257 operator_bitwise_xor::op2_range (irange
&r
, tree type
,
3260 relation_kind rel ATTRIBUTE_UNUSED
) const
3262 return operator_bitwise_xor::op1_range (r
, type
, lhs
, op1
);
3265 class operator_trunc_mod
: public range_operator
3268 virtual void wi_fold (irange
&r
, tree type
,
3269 const wide_int
&lh_lb
,
3270 const wide_int
&lh_ub
,
3271 const wide_int
&rh_lb
,
3272 const wide_int
&rh_ub
) const;
3273 virtual bool op1_range (irange
&r
, tree type
,
3276 relation_kind rel ATTRIBUTE_UNUSED
) const;
3277 virtual bool op2_range (irange
&r
, tree type
,
3280 relation_kind rel ATTRIBUTE_UNUSED
) const;
3284 operator_trunc_mod::wi_fold (irange
&r
, tree type
,
3285 const wide_int
&lh_lb
,
3286 const wide_int
&lh_ub
,
3287 const wide_int
&rh_lb
,
3288 const wide_int
&rh_ub
) const
3290 wide_int new_lb
, new_ub
, tmp
;
3291 signop sign
= TYPE_SIGN (type
);
3292 unsigned prec
= TYPE_PRECISION (type
);
3294 // Mod 0 is undefined.
3295 if (wi_zero_p (type
, rh_lb
, rh_ub
))
3301 // Check for constant and try to fold.
3302 if (lh_lb
== lh_ub
&& rh_lb
== rh_ub
)
3304 wi::overflow_type ov
= wi::OVF_NONE
;
3305 tmp
= wi::mod_trunc (lh_lb
, rh_lb
, sign
, &ov
);
3306 if (ov
== wi::OVF_NONE
)
3308 r
= int_range
<2> (type
, tmp
, tmp
);
3313 // ABS (A % B) < ABS (B) and either 0 <= A % B <= A or A <= A % B <= 0.
3318 new_ub
= wi::smax (new_ub
, tmp
);
3321 if (sign
== UNSIGNED
)
3322 new_lb
= wi::zero (prec
);
3327 if (wi::gts_p (tmp
, 0))
3328 tmp
= wi::zero (prec
);
3329 new_lb
= wi::smax (new_lb
, tmp
);
3332 if (sign
== SIGNED
&& wi::neg_p (tmp
))
3333 tmp
= wi::zero (prec
);
3334 new_ub
= wi::min (new_ub
, tmp
, sign
);
3336 value_range_with_overflow (r
, type
, new_lb
, new_ub
);
3340 operator_trunc_mod::op1_range (irange
&r
, tree type
,
3343 relation_kind rel ATTRIBUTE_UNUSED
) const
3346 signop sign
= TYPE_SIGN (type
);
3347 unsigned prec
= TYPE_PRECISION (type
);
3348 // (a % b) >= x && x > 0 , then a >= x.
3349 if (wi::gt_p (lhs
.lower_bound (), 0, sign
))
3351 r
= value_range (type
, lhs
.lower_bound (), wi::max_value (prec
, sign
));
3354 // (a % b) <= x && x < 0 , then a <= x.
3355 if (wi::lt_p (lhs
.upper_bound (), 0, sign
))
3357 r
= value_range (type
, wi::min_value (prec
, sign
), lhs
.upper_bound ());
3364 operator_trunc_mod::op2_range (irange
&r
, tree type
,
3367 relation_kind rel ATTRIBUTE_UNUSED
) const
3370 signop sign
= TYPE_SIGN (type
);
3371 unsigned prec
= TYPE_PRECISION (type
);
3372 // (a % b) >= x && x > 0 , then b is in ~[-x, x] for signed
3373 // or b > x for unsigned.
3374 if (wi::gt_p (lhs
.lower_bound (), 0, sign
))
3377 r
= value_range (type
, wi::neg (lhs
.lower_bound ()),
3378 lhs
.lower_bound (), VR_ANTI_RANGE
);
3379 else if (wi::lt_p (lhs
.lower_bound (), wi::max_value (prec
, sign
),
3381 r
= value_range (type
, lhs
.lower_bound () + 1,
3382 wi::max_value (prec
, sign
));
3387 // (a % b) <= x && x < 0 , then b is in ~[x, -x].
3388 if (wi::lt_p (lhs
.upper_bound (), 0, sign
))
3390 if (wi::gt_p (lhs
.upper_bound (), wi::min_value (prec
, sign
), sign
))
3391 r
= value_range (type
, lhs
.upper_bound (),
3392 wi::neg (lhs
.upper_bound ()), VR_ANTI_RANGE
);
3401 class operator_logical_not
: public range_operator
3404 virtual bool fold_range (irange
&r
, tree type
,
3407 relation_kind rel
= VREL_NONE
) const;
3408 virtual bool op1_range (irange
&r
, tree type
,
3411 relation_kind rel
= VREL_NONE
) const;
3414 // Folding a logical NOT, oddly enough, involves doing nothing on the
3415 // forward pass through. During the initial walk backwards, the
3416 // logical NOT reversed the desired outcome on the way back, so on the
3417 // way forward all we do is pass the range forward.
3422 // to determine the TRUE branch, walking backward
3423 // if (b_3) if ([1,1])
3424 // b_3 = !b_2 [1,1] = ![0,0]
3425 // b_2 = x_1 < 20 [0,0] = x_1 < 20, false, so x_1 == [20, 255]
3426 // which is the result we are looking for.. so.. pass it through.
3429 operator_logical_not::fold_range (irange
&r
, tree type
,
3431 const irange
&rh ATTRIBUTE_UNUSED
,
3432 relation_kind rel ATTRIBUTE_UNUSED
) const
3434 if (empty_range_varying (r
, type
, lh
, rh
))
3438 if (!lh
.varying_p () && !lh
.undefined_p ())
3445 operator_logical_not::op1_range (irange
&r
,
3449 relation_kind rel ATTRIBUTE_UNUSED
) const
3451 // Logical NOT is involutary...do it again.
3452 return fold_range (r
, type
, lhs
, op2
);
3456 class operator_bitwise_not
: public range_operator
3459 virtual bool fold_range (irange
&r
, tree type
,
3462 relation_kind rel
= VREL_NONE
) const;
3463 virtual bool op1_range (irange
&r
, tree type
,
3466 relation_kind rel
= VREL_NONE
) const;
3470 operator_bitwise_not::fold_range (irange
&r
, tree type
,
3473 relation_kind rel ATTRIBUTE_UNUSED
) const
3475 if (empty_range_varying (r
, type
, lh
, rh
))
3478 if (types_compatible_p (type
, boolean_type_node
))
3479 return op_logical_not
.fold_range (r
, type
, lh
, rh
);
3481 // ~X is simply -1 - X.
3482 int_range
<1> minusone (type
, wi::minus_one (TYPE_PRECISION (type
)),
3483 wi::minus_one (TYPE_PRECISION (type
)));
3484 return range_op_handler (MINUS_EXPR
, type
)->fold_range (r
, type
, minusone
,
3489 operator_bitwise_not::op1_range (irange
&r
, tree type
,
3492 relation_kind rel ATTRIBUTE_UNUSED
) const
3494 if (types_compatible_p (type
, boolean_type_node
))
3495 return op_logical_not
.op1_range (r
, type
, lhs
, op2
);
3497 // ~X is -1 - X and since bitwise NOT is involutary...do it again.
3498 return fold_range (r
, type
, lhs
, op2
);
3502 class operator_cst
: public range_operator
3505 virtual bool fold_range (irange
&r
, tree type
,
3508 relation_kind rel
= VREL_NONE
) const;
3512 operator_cst::fold_range (irange
&r
, tree type ATTRIBUTE_UNUSED
,
3514 const irange
&rh ATTRIBUTE_UNUSED
,
3515 relation_kind rel ATTRIBUTE_UNUSED
) const
3522 class operator_identity
: public range_operator
3525 virtual bool fold_range (irange
&r
, tree type
,
3528 relation_kind rel
= VREL_NONE
) const;
3529 virtual bool op1_range (irange
&r
, tree type
,
3532 relation_kind rel
= VREL_NONE
) const;
3533 virtual enum tree_code
lhs_op1_relation (const irange
&lhs
,
3535 const irange
&op2
) const;
3538 // Determine if there is a relationship between LHS and OP1.
3541 operator_identity::lhs_op1_relation (const irange
&lhs
,
3542 const irange
&op1 ATTRIBUTE_UNUSED
,
3543 const irange
&op2 ATTRIBUTE_UNUSED
) const
3545 if (lhs
.undefined_p ())
3547 // Simply a copy, so they are equivalent.
3552 operator_identity::fold_range (irange
&r
, tree type ATTRIBUTE_UNUSED
,
3554 const irange
&rh ATTRIBUTE_UNUSED
,
3555 relation_kind rel ATTRIBUTE_UNUSED
) const
3562 operator_identity::op1_range (irange
&r
, tree type ATTRIBUTE_UNUSED
,
3564 const irange
&op2 ATTRIBUTE_UNUSED
,
3565 relation_kind rel ATTRIBUTE_UNUSED
) const
3572 class operator_unknown
: public range_operator
3575 virtual bool fold_range (irange
&r
, tree type
,
3578 relation_kind rel
= VREL_NONE
) const;
3582 operator_unknown::fold_range (irange
&r
, tree type
,
3583 const irange
&lh ATTRIBUTE_UNUSED
,
3584 const irange
&rh ATTRIBUTE_UNUSED
,
3585 relation_kind rel ATTRIBUTE_UNUSED
) const
3587 r
.set_varying (type
);
3592 class operator_abs
: public range_operator
3595 virtual void wi_fold (irange
&r
, tree type
,
3596 const wide_int
&lh_lb
,
3597 const wide_int
&lh_ub
,
3598 const wide_int
&rh_lb
,
3599 const wide_int
&rh_ub
) const;
3600 virtual bool op1_range (irange
&r
, tree type
,
3603 relation_kind rel ATTRIBUTE_UNUSED
) const;
3607 operator_abs::wi_fold (irange
&r
, tree type
,
3608 const wide_int
&lh_lb
, const wide_int
&lh_ub
,
3609 const wide_int
&rh_lb ATTRIBUTE_UNUSED
,
3610 const wide_int
&rh_ub ATTRIBUTE_UNUSED
) const
3613 signop sign
= TYPE_SIGN (type
);
3614 unsigned prec
= TYPE_PRECISION (type
);
3616 // Pass through LH for the easy cases.
3617 if (sign
== UNSIGNED
|| wi::ge_p (lh_lb
, 0, sign
))
3619 r
= int_range
<1> (type
, lh_lb
, lh_ub
);
3623 // -TYPE_MIN_VALUE = TYPE_MIN_VALUE with flag_wrapv so we can't get
3625 wide_int min_value
= wi::min_value (prec
, sign
);
3626 wide_int max_value
= wi::max_value (prec
, sign
);
3627 if (!TYPE_OVERFLOW_UNDEFINED (type
) && wi::eq_p (lh_lb
, min_value
))
3629 r
.set_varying (type
);
3633 // ABS_EXPR may flip the range around, if the original range
3634 // included negative values.
3635 if (wi::eq_p (lh_lb
, min_value
))
3637 // ABS ([-MIN, -MIN]) isn't representable, but we have traditionally
3638 // returned [-MIN,-MIN] so this preserves that behaviour. PR37078
3639 if (wi::eq_p (lh_ub
, min_value
))
3641 r
= int_range
<1> (type
, min_value
, min_value
);
3647 min
= wi::abs (lh_lb
);
3649 if (wi::eq_p (lh_ub
, min_value
))
3652 max
= wi::abs (lh_ub
);
3654 // If the range contains zero then we know that the minimum value in the
3655 // range will be zero.
3656 if (wi::le_p (lh_lb
, 0, sign
) && wi::ge_p (lh_ub
, 0, sign
))
3658 if (wi::gt_p (min
, max
, sign
))
3660 min
= wi::zero (prec
);
3664 // If the range was reversed, swap MIN and MAX.
3665 if (wi::gt_p (min
, max
, sign
))
3666 std::swap (min
, max
);
3669 // If the new range has its limits swapped around (MIN > MAX), then
3670 // the operation caused one of them to wrap around. The only thing
3671 // we know is that the result is positive.
3672 if (wi::gt_p (min
, max
, sign
))
3674 min
= wi::zero (prec
);
3677 r
= int_range
<1> (type
, min
, max
);
3681 operator_abs::op1_range (irange
&r
, tree type
,
3684 relation_kind rel ATTRIBUTE_UNUSED
) const
3686 if (empty_range_varying (r
, type
, lhs
, op2
))
3688 if (TYPE_UNSIGNED (type
))
3693 // Start with the positives because negatives are an impossible result.
3694 int_range_max positives
= range_positives (type
);
3695 positives
.intersect (lhs
);
3697 // Then add the negative of each pair:
3698 // ABS(op1) = [5,20] would yield op1 => [-20,-5][5,20].
3699 for (unsigned i
= 0; i
< positives
.num_pairs (); ++i
)
3700 r
.union_ (int_range
<1> (type
,
3701 -positives
.upper_bound (i
),
3702 -positives
.lower_bound (i
)));
3703 // With flag_wrapv, -TYPE_MIN_VALUE = TYPE_MIN_VALUE which is
3704 // unrepresentable. Add -TYPE_MIN_VALUE in this case.
3705 wide_int min_value
= wi::min_value (TYPE_PRECISION (type
), TYPE_SIGN (type
));
3706 wide_int lb
= lhs
.lower_bound ();
3707 if (!TYPE_OVERFLOW_UNDEFINED (type
) && wi::eq_p (lb
, min_value
))
3708 r
.union_ (int_range
<2> (type
, lb
, lb
));
3713 class operator_absu
: public range_operator
3716 virtual void wi_fold (irange
&r
, tree type
,
3717 const wide_int
&lh_lb
, const wide_int
&lh_ub
,
3718 const wide_int
&rh_lb
, const wide_int
&rh_ub
) const;
3722 operator_absu::wi_fold (irange
&r
, tree type
,
3723 const wide_int
&lh_lb
, const wide_int
&lh_ub
,
3724 const wide_int
&rh_lb ATTRIBUTE_UNUSED
,
3725 const wide_int
&rh_ub ATTRIBUTE_UNUSED
) const
3727 wide_int new_lb
, new_ub
;
3729 // Pass through VR0 the easy cases.
3730 if (wi::ges_p (lh_lb
, 0))
3737 new_lb
= wi::abs (lh_lb
);
3738 new_ub
= wi::abs (lh_ub
);
3740 // If the range contains zero then we know that the minimum
3741 // value in the range will be zero.
3742 if (wi::ges_p (lh_ub
, 0))
3744 if (wi::gtu_p (new_lb
, new_ub
))
3746 new_lb
= wi::zero (TYPE_PRECISION (type
));
3749 std::swap (new_lb
, new_ub
);
3752 gcc_checking_assert (TYPE_UNSIGNED (type
));
3753 r
= int_range
<1> (type
, new_lb
, new_ub
);
3757 class operator_negate
: public range_operator
3760 virtual bool fold_range (irange
&r
, tree type
,
3763 relation_kind rel
= VREL_NONE
) const;
3764 virtual bool op1_range (irange
&r
, tree type
,
3767 relation_kind rel
= VREL_NONE
) const;
3771 operator_negate::fold_range (irange
&r
, tree type
,
3774 relation_kind rel ATTRIBUTE_UNUSED
) const
3776 if (empty_range_varying (r
, type
, lh
, rh
))
3778 // -X is simply 0 - X.
3779 return range_op_handler (MINUS_EXPR
, type
)->fold_range (r
, type
,
3785 operator_negate::op1_range (irange
&r
, tree type
,
3788 relation_kind rel ATTRIBUTE_UNUSED
) const
3790 // NEGATE is involutory.
3791 return fold_range (r
, type
, lhs
, op2
);
3795 class operator_addr_expr
: public range_operator
3798 virtual bool fold_range (irange
&r
, tree type
,
3801 relation_kind rel
= VREL_NONE
) const;
3802 virtual bool op1_range (irange
&r
, tree type
,
3805 relation_kind rel
= VREL_NONE
) const;
3809 operator_addr_expr::fold_range (irange
&r
, tree type
,
3812 relation_kind rel ATTRIBUTE_UNUSED
) const
3814 if (empty_range_varying (r
, type
, lh
, rh
))
3817 // Return a non-null pointer of the LHS type (passed in op2).
3819 r
= range_zero (type
);
3820 else if (!lh
.contains_p (build_zero_cst (lh
.type ())))
3821 r
= range_nonzero (type
);
3823 r
.set_varying (type
);
3828 operator_addr_expr::op1_range (irange
&r
, tree type
,
3831 relation_kind rel ATTRIBUTE_UNUSED
) const
3833 return operator_addr_expr::fold_range (r
, type
, lhs
, op2
);
3837 class pointer_plus_operator
: public range_operator
3840 virtual void wi_fold (irange
&r
, tree type
,
3841 const wide_int
&lh_lb
,
3842 const wide_int
&lh_ub
,
3843 const wide_int
&rh_lb
,
3844 const wide_int
&rh_ub
) const;
3848 pointer_plus_operator::wi_fold (irange
&r
, tree type
,
3849 const wide_int
&lh_lb
,
3850 const wide_int
&lh_ub
,
3851 const wide_int
&rh_lb
,
3852 const wide_int
&rh_ub
) const
3854 // Check for [0,0] + const, and simply return the const.
3855 if (lh_lb
== 0 && lh_ub
== 0 && rh_lb
== rh_ub
)
3857 tree val
= wide_int_to_tree (type
, rh_lb
);
3862 // For pointer types, we are really only interested in asserting
3863 // whether the expression evaluates to non-NULL.
3865 // With -fno-delete-null-pointer-checks we need to be more
3866 // conservative. As some object might reside at address 0,
3867 // then some offset could be added to it and the same offset
3868 // subtracted again and the result would be NULL.
3870 // static int a[12]; where &a[0] is NULL and
3873 // ptr will be NULL here, even when there is POINTER_PLUS_EXPR
3874 // where the first range doesn't include zero and the second one
3875 // doesn't either. As the second operand is sizetype (unsigned),
3876 // consider all ranges where the MSB could be set as possible
3877 // subtractions where the result might be NULL.
3878 if ((!wi_includes_zero_p (type
, lh_lb
, lh_ub
)
3879 || !wi_includes_zero_p (type
, rh_lb
, rh_ub
))
3880 && !TYPE_OVERFLOW_WRAPS (type
)
3881 && (flag_delete_null_pointer_checks
3882 || !wi::sign_mask (rh_ub
)))
3883 r
= range_nonzero (type
);
3884 else if (lh_lb
== lh_ub
&& lh_lb
== 0
3885 && rh_lb
== rh_ub
&& rh_lb
== 0)
3886 r
= range_zero (type
);
3888 r
.set_varying (type
);
3892 class pointer_min_max_operator
: public range_operator
3895 virtual void wi_fold (irange
& r
, tree type
,
3896 const wide_int
&lh_lb
, const wide_int
&lh_ub
,
3897 const wide_int
&rh_lb
, const wide_int
&rh_ub
) const;
3901 pointer_min_max_operator::wi_fold (irange
&r
, tree type
,
3902 const wide_int
&lh_lb
,
3903 const wide_int
&lh_ub
,
3904 const wide_int
&rh_lb
,
3905 const wide_int
&rh_ub
) const
3907 // For MIN/MAX expressions with pointers, we only care about
3908 // nullness. If both are non null, then the result is nonnull.
3909 // If both are null, then the result is null. Otherwise they
3911 if (!wi_includes_zero_p (type
, lh_lb
, lh_ub
)
3912 && !wi_includes_zero_p (type
, rh_lb
, rh_ub
))
3913 r
= range_nonzero (type
);
3914 else if (wi_zero_p (type
, lh_lb
, lh_ub
) && wi_zero_p (type
, rh_lb
, rh_ub
))
3915 r
= range_zero (type
);
3917 r
.set_varying (type
);
3921 class pointer_and_operator
: public range_operator
3924 virtual void wi_fold (irange
&r
, tree type
,
3925 const wide_int
&lh_lb
, const wide_int
&lh_ub
,
3926 const wide_int
&rh_lb
, const wide_int
&rh_ub
) const;
3930 pointer_and_operator::wi_fold (irange
&r
, tree type
,
3931 const wide_int
&lh_lb
,
3932 const wide_int
&lh_ub
,
3933 const wide_int
&rh_lb ATTRIBUTE_UNUSED
,
3934 const wide_int
&rh_ub ATTRIBUTE_UNUSED
) const
3936 // For pointer types, we are really only interested in asserting
3937 // whether the expression evaluates to non-NULL.
3938 if (wi_zero_p (type
, lh_lb
, lh_ub
) || wi_zero_p (type
, lh_lb
, lh_ub
))
3939 r
= range_zero (type
);
3941 r
.set_varying (type
);
3945 class pointer_or_operator
: public range_operator
3948 virtual bool op1_range (irange
&r
, tree type
,
3951 relation_kind rel
= VREL_NONE
) const;
3952 virtual bool op2_range (irange
&r
, tree type
,
3955 relation_kind rel
= VREL_NONE
) const;
3956 virtual void wi_fold (irange
&r
, tree type
,
3957 const wide_int
&lh_lb
, const wide_int
&lh_ub
,
3958 const wide_int
&rh_lb
, const wide_int
&rh_ub
) const;
3962 pointer_or_operator::op1_range (irange
&r
, tree type
,
3964 const irange
&op2 ATTRIBUTE_UNUSED
,
3965 relation_kind rel ATTRIBUTE_UNUSED
) const
3969 tree zero
= build_zero_cst (type
);
3970 r
= int_range
<1> (zero
, zero
);
3973 r
.set_varying (type
);
3978 pointer_or_operator::op2_range (irange
&r
, tree type
,
3981 relation_kind rel ATTRIBUTE_UNUSED
) const
3983 return pointer_or_operator::op1_range (r
, type
, lhs
, op1
);
3987 pointer_or_operator::wi_fold (irange
&r
, tree type
,
3988 const wide_int
&lh_lb
,
3989 const wide_int
&lh_ub
,
3990 const wide_int
&rh_lb
,
3991 const wide_int
&rh_ub
) const
3993 // For pointer types, we are really only interested in asserting
3994 // whether the expression evaluates to non-NULL.
3995 if (!wi_includes_zero_p (type
, lh_lb
, lh_ub
)
3996 && !wi_includes_zero_p (type
, rh_lb
, rh_ub
))
3997 r
= range_nonzero (type
);
3998 else if (wi_zero_p (type
, lh_lb
, lh_ub
) && wi_zero_p (type
, rh_lb
, rh_ub
))
3999 r
= range_zero (type
);
4001 r
.set_varying (type
);
4004 // Return a pointer to the range_operator instance, if there is one
4005 // associated with tree_code CODE.
4008 range_op_table::operator[] (enum tree_code code
)
4010 gcc_checking_assert (code
> 0 && code
< MAX_TREE_CODES
);
4011 return m_range_tree
[code
];
4014 // Add OP to the handler table for CODE.
4017 range_op_table::set (enum tree_code code
, range_operator
&op
)
4019 gcc_checking_assert (m_range_tree
[code
] == NULL
);
4020 m_range_tree
[code
] = &op
;
4023 // Instantiate a range op table for integral operations.
4025 class integral_table
: public range_op_table
4029 } integral_tree_table
;
4031 integral_table::integral_table ()
4033 set (EQ_EXPR
, op_equal
);
4034 set (NE_EXPR
, op_not_equal
);
4035 set (LT_EXPR
, op_lt
);
4036 set (LE_EXPR
, op_le
);
4037 set (GT_EXPR
, op_gt
);
4038 set (GE_EXPR
, op_ge
);
4039 set (PLUS_EXPR
, op_plus
);
4040 set (MINUS_EXPR
, op_minus
);
4041 set (MIN_EXPR
, op_min
);
4042 set (MAX_EXPR
, op_max
);
4043 set (MULT_EXPR
, op_mult
);
4044 set (TRUNC_DIV_EXPR
, op_trunc_div
);
4045 set (FLOOR_DIV_EXPR
, op_floor_div
);
4046 set (ROUND_DIV_EXPR
, op_round_div
);
4047 set (CEIL_DIV_EXPR
, op_ceil_div
);
4048 set (EXACT_DIV_EXPR
, op_exact_div
);
4049 set (LSHIFT_EXPR
, op_lshift
);
4050 set (RSHIFT_EXPR
, op_rshift
);
4051 set (NOP_EXPR
, op_convert
);
4052 set (CONVERT_EXPR
, op_convert
);
4053 set (TRUTH_AND_EXPR
, op_logical_and
);
4054 set (BIT_AND_EXPR
, op_bitwise_and
);
4055 set (TRUTH_OR_EXPR
, op_logical_or
);
4056 set (BIT_IOR_EXPR
, op_bitwise_or
);
4057 set (BIT_XOR_EXPR
, op_bitwise_xor
);
4058 set (TRUNC_MOD_EXPR
, op_trunc_mod
);
4059 set (TRUTH_NOT_EXPR
, op_logical_not
);
4060 set (BIT_NOT_EXPR
, op_bitwise_not
);
4061 set (INTEGER_CST
, op_integer_cst
);
4062 set (SSA_NAME
, op_identity
);
4063 set (PAREN_EXPR
, op_identity
);
4064 set (OBJ_TYPE_REF
, op_identity
);
4065 set (IMAGPART_EXPR
, op_unknown
);
4066 set (REALPART_EXPR
, op_unknown
);
4067 set (POINTER_DIFF_EXPR
, op_pointer_diff
);
4068 set (ABS_EXPR
, op_abs
);
4069 set (ABSU_EXPR
, op_absu
);
4070 set (NEGATE_EXPR
, op_negate
);
4071 set (ADDR_EXPR
, op_addr
);
4074 // Instantiate a range op table for pointer operations.
4076 class pointer_table
: public range_op_table
4080 } pointer_tree_table
;
4082 pointer_table::pointer_table ()
4084 set (BIT_AND_EXPR
, op_pointer_and
);
4085 set (BIT_IOR_EXPR
, op_pointer_or
);
4086 set (MIN_EXPR
, op_ptr_min_max
);
4087 set (MAX_EXPR
, op_ptr_min_max
);
4088 set (POINTER_PLUS_EXPR
, op_pointer_plus
);
4090 set (EQ_EXPR
, op_equal
);
4091 set (NE_EXPR
, op_not_equal
);
4092 set (LT_EXPR
, op_lt
);
4093 set (LE_EXPR
, op_le
);
4094 set (GT_EXPR
, op_gt
);
4095 set (GE_EXPR
, op_ge
);
4096 set (SSA_NAME
, op_identity
);
4097 set (INTEGER_CST
, op_integer_cst
);
4098 set (ADDR_EXPR
, op_addr
);
4099 set (NOP_EXPR
, op_convert
);
4100 set (CONVERT_EXPR
, op_convert
);
4102 set (BIT_NOT_EXPR
, op_bitwise_not
);
4103 set (BIT_XOR_EXPR
, op_bitwise_xor
);
4106 // The tables are hidden and accessed via a simple extern function.
4109 range_op_handler (enum tree_code code
, tree type
)
4111 // First check if there is a pointer specialization.
4112 if (POINTER_TYPE_P (type
))
4113 return pointer_tree_table
[code
];
4114 if (INTEGRAL_TYPE_P (type
))
4115 return integral_tree_table
[code
];
4119 // Cast the range in R to TYPE.
4122 range_cast (irange
&r
, tree type
)
4124 int_range_max tmp
= r
;
4125 range_operator
*op
= range_op_handler (CONVERT_EXPR
, type
);
4126 // Call op_convert, if it fails, the result is varying.
4127 if (!op
->fold_range (r
, type
, tmp
, int_range
<1> (type
)))
4128 r
.set_varying (type
);
4132 #include "selftest.h"
4136 #define INT(N) build_int_cst (integer_type_node, (N))
4137 #define UINT(N) build_int_cstu (unsigned_type_node, (N))
4138 #define INT16(N) build_int_cst (short_integer_type_node, (N))
4139 #define UINT16(N) build_int_cstu (short_unsigned_type_node, (N))
4140 #define SCHAR(N) build_int_cst (signed_char_type_node, (N))
4141 #define UCHAR(N) build_int_cstu (unsigned_char_type_node, (N))
4144 range_op_cast_tests ()
4146 int_range
<1> r0
, r1
, r2
, rold
;
4147 r0
.set_varying (integer_type_node
);
4148 tree maxint
= wide_int_to_tree (integer_type_node
, r0
.upper_bound ());
4150 // If a range is in any way outside of the range for the converted
4151 // to range, default to the range for the new type.
4152 r0
.set_varying (short_integer_type_node
);
4153 tree minshort
= wide_int_to_tree (short_integer_type_node
, r0
.lower_bound ());
4154 tree maxshort
= wide_int_to_tree (short_integer_type_node
, r0
.upper_bound ());
4155 if (TYPE_PRECISION (TREE_TYPE (maxint
))
4156 > TYPE_PRECISION (short_integer_type_node
))
4158 r1
= int_range
<1> (integer_zero_node
, maxint
);
4159 range_cast (r1
, short_integer_type_node
);
4160 ASSERT_TRUE (r1
.lower_bound () == wi::to_wide (minshort
)
4161 && r1
.upper_bound() == wi::to_wide (maxshort
));
4164 // (unsigned char)[-5,-1] => [251,255].
4165 r0
= rold
= int_range
<1> (SCHAR (-5), SCHAR (-1));
4166 range_cast (r0
, unsigned_char_type_node
);
4167 ASSERT_TRUE (r0
== int_range
<1> (UCHAR (251), UCHAR (255)));
4168 range_cast (r0
, signed_char_type_node
);
4169 ASSERT_TRUE (r0
== rold
);
4171 // (signed char)[15, 150] => [-128,-106][15,127].
4172 r0
= rold
= int_range
<1> (UCHAR (15), UCHAR (150));
4173 range_cast (r0
, signed_char_type_node
);
4174 r1
= int_range
<1> (SCHAR (15), SCHAR (127));
4175 r2
= int_range
<1> (SCHAR (-128), SCHAR (-106));
4177 ASSERT_TRUE (r1
== r0
);
4178 range_cast (r0
, unsigned_char_type_node
);
4179 ASSERT_TRUE (r0
== rold
);
4181 // (unsigned char)[-5, 5] => [0,5][251,255].
4182 r0
= rold
= int_range
<1> (SCHAR (-5), SCHAR (5));
4183 range_cast (r0
, unsigned_char_type_node
);
4184 r1
= int_range
<1> (UCHAR (251), UCHAR (255));
4185 r2
= int_range
<1> (UCHAR (0), UCHAR (5));
4187 ASSERT_TRUE (r0
== r1
);
4188 range_cast (r0
, signed_char_type_node
);
4189 ASSERT_TRUE (r0
== rold
);
4191 // (unsigned char)[-5,5] => [0,5][251,255].
4192 r0
= int_range
<1> (INT (-5), INT (5));
4193 range_cast (r0
, unsigned_char_type_node
);
4194 r1
= int_range
<1> (UCHAR (0), UCHAR (5));
4195 r1
.union_ (int_range
<1> (UCHAR (251), UCHAR (255)));
4196 ASSERT_TRUE (r0
== r1
);
4198 // (unsigned char)[5U,1974U] => [0,255].
4199 r0
= int_range
<1> (UINT (5), UINT (1974));
4200 range_cast (r0
, unsigned_char_type_node
);
4201 ASSERT_TRUE (r0
== int_range
<1> (UCHAR (0), UCHAR (255)));
4202 range_cast (r0
, integer_type_node
);
4203 // Going to a wider range should not sign extend.
4204 ASSERT_TRUE (r0
== int_range
<1> (INT (0), INT (255)));
4206 // (unsigned char)[-350,15] => [0,255].
4207 r0
= int_range
<1> (INT (-350), INT (15));
4208 range_cast (r0
, unsigned_char_type_node
);
4209 ASSERT_TRUE (r0
== (int_range
<1>
4210 (TYPE_MIN_VALUE (unsigned_char_type_node
),
4211 TYPE_MAX_VALUE (unsigned_char_type_node
))));
4213 // Casting [-120,20] from signed char to unsigned short.
4214 // => [0, 20][0xff88, 0xffff].
4215 r0
= int_range
<1> (SCHAR (-120), SCHAR (20));
4216 range_cast (r0
, short_unsigned_type_node
);
4217 r1
= int_range
<1> (UINT16 (0), UINT16 (20));
4218 r2
= int_range
<1> (UINT16 (0xff88), UINT16 (0xffff));
4220 ASSERT_TRUE (r0
== r1
);
4221 // A truncating cast back to signed char will work because [-120, 20]
4222 // is representable in signed char.
4223 range_cast (r0
, signed_char_type_node
);
4224 ASSERT_TRUE (r0
== int_range
<1> (SCHAR (-120), SCHAR (20)));
4226 // unsigned char -> signed short
4227 // (signed short)[(unsigned char)25, (unsigned char)250]
4228 // => [(signed short)25, (signed short)250]
4229 r0
= rold
= int_range
<1> (UCHAR (25), UCHAR (250));
4230 range_cast (r0
, short_integer_type_node
);
4231 r1
= int_range
<1> (INT16 (25), INT16 (250));
4232 ASSERT_TRUE (r0
== r1
);
4233 range_cast (r0
, unsigned_char_type_node
);
4234 ASSERT_TRUE (r0
== rold
);
4236 // Test casting a wider signed [-MIN,MAX] to a nar`rower unsigned.
4237 r0
= int_range
<1> (TYPE_MIN_VALUE (long_long_integer_type_node
),
4238 TYPE_MAX_VALUE (long_long_integer_type_node
));
4239 range_cast (r0
, short_unsigned_type_node
);
4240 r1
= int_range
<1> (TYPE_MIN_VALUE (short_unsigned_type_node
),
4241 TYPE_MAX_VALUE (short_unsigned_type_node
));
4242 ASSERT_TRUE (r0
== r1
);
4244 // Casting NONZERO to a narrower type will wrap/overflow so
4245 // it's just the entire range for the narrower type.
4247 // "NOT 0 at signed 32-bits" ==> [-MIN_32,-1][1, +MAX_32]. This is
4248 // is outside of the range of a smaller range, return the full
4250 if (TYPE_PRECISION (integer_type_node
)
4251 > TYPE_PRECISION (short_integer_type_node
))
4253 r0
= range_nonzero (integer_type_node
);
4254 range_cast (r0
, short_integer_type_node
);
4255 r1
= int_range
<1> (TYPE_MIN_VALUE (short_integer_type_node
),
4256 TYPE_MAX_VALUE (short_integer_type_node
));
4257 ASSERT_TRUE (r0
== r1
);
4260 // Casting NONZERO from a narrower signed to a wider signed.
4262 // NONZERO signed 16-bits is [-MIN_16,-1][1, +MAX_16].
4263 // Converting this to 32-bits signed is [-MIN_16,-1][1, +MAX_16].
4264 r0
= range_nonzero (short_integer_type_node
);
4265 range_cast (r0
, integer_type_node
);
4266 r1
= int_range
<1> (INT (-32768), INT (-1));
4267 r2
= int_range
<1> (INT (1), INT (32767));
4269 ASSERT_TRUE (r0
== r1
);
4273 range_op_lshift_tests ()
4275 // Test that 0x808.... & 0x8.... still contains 0x8....
4276 // for a large set of numbers.
4279 tree big_type
= long_long_unsigned_type_node
;
4280 // big_num = 0x808,0000,0000,0000
4281 tree big_num
= fold_build2 (LSHIFT_EXPR
, big_type
,
4282 build_int_cst (big_type
, 0x808),
4283 build_int_cst (big_type
, 48));
4284 op_bitwise_and
.fold_range (res
, big_type
,
4285 int_range
<1> (big_type
),
4286 int_range
<1> (big_num
, big_num
));
4287 // val = 0x8,0000,0000,0000
4288 tree val
= fold_build2 (LSHIFT_EXPR
, big_type
,
4289 build_int_cst (big_type
, 0x8),
4290 build_int_cst (big_type
, 48));
4291 ASSERT_TRUE (res
.contains_p (val
));
4294 if (TYPE_PRECISION (unsigned_type_node
) > 31)
4296 // unsigned VARYING = op1 << 1 should be VARYING.
4297 int_range
<2> lhs (unsigned_type_node
);
4298 int_range
<2> shift (INT (1), INT (1));
4300 op_lshift
.op1_range (op1
, unsigned_type_node
, lhs
, shift
);
4301 ASSERT_TRUE (op1
.varying_p ());
4303 // 0 = op1 << 1 should be [0,0], [0x8000000, 0x8000000].
4304 int_range
<2> zero (UINT (0), UINT (0));
4305 op_lshift
.op1_range (op1
, unsigned_type_node
, zero
, shift
);
4306 ASSERT_TRUE (op1
.num_pairs () == 2);
4307 // Remove the [0,0] range.
4308 op1
.intersect (zero
);
4309 ASSERT_TRUE (op1
.num_pairs () == 1);
4310 // op1 << 1 should be [0x8000,0x8000] << 1,
4311 // which should result in [0,0].
4312 int_range_max result
;
4313 op_lshift
.fold_range (result
, unsigned_type_node
, op1
, shift
);
4314 ASSERT_TRUE (result
== zero
);
4316 // signed VARYING = op1 << 1 should be VARYING.
4317 if (TYPE_PRECISION (integer_type_node
) > 31)
4319 // unsigned VARYING = op1 << 1 hould be VARYING.
4320 int_range
<2> lhs (integer_type_node
);
4321 int_range
<2> shift (INT (1), INT (1));
4323 op_lshift
.op1_range (op1
, integer_type_node
, lhs
, shift
);
4324 ASSERT_TRUE (op1
.varying_p ());
4326 // 0 = op1 << 1 should be [0,0], [0x8000000, 0x8000000].
4327 int_range
<2> zero (INT (0), INT (0));
4328 op_lshift
.op1_range (op1
, integer_type_node
, zero
, shift
);
4329 ASSERT_TRUE (op1
.num_pairs () == 2);
4330 // Remove the [0,0] range.
4331 op1
.intersect (zero
);
4332 ASSERT_TRUE (op1
.num_pairs () == 1);
4333 // op1 << 1 shuould be [0x8000,0x8000] << 1,
4334 // which should result in [0,0].
4335 int_range_max result
;
4336 op_lshift
.fold_range (result
, unsigned_type_node
, op1
, shift
);
4337 ASSERT_TRUE (result
== zero
);
4342 range_op_rshift_tests ()
4344 // unsigned: [3, MAX] = OP1 >> 1
4346 int_range_max
lhs (build_int_cst (unsigned_type_node
, 3),
4347 TYPE_MAX_VALUE (unsigned_type_node
));
4348 int_range_max
one (build_one_cst (unsigned_type_node
),
4349 build_one_cst (unsigned_type_node
));
4351 op_rshift
.op1_range (op1
, unsigned_type_node
, lhs
, one
);
4352 ASSERT_FALSE (op1
.contains_p (UINT (3)));
4355 // signed: [3, MAX] = OP1 >> 1
4357 int_range_max
lhs (INT (3), TYPE_MAX_VALUE (integer_type_node
));
4358 int_range_max
one (INT (1), INT (1));
4360 op_rshift
.op1_range (op1
, integer_type_node
, lhs
, one
);
4361 ASSERT_FALSE (op1
.contains_p (INT (-2)));
4364 // This is impossible, so OP1 should be [].
4365 // signed: [MIN, MIN] = OP1 >> 1
4367 int_range_max
lhs (TYPE_MIN_VALUE (integer_type_node
),
4368 TYPE_MIN_VALUE (integer_type_node
));
4369 int_range_max
one (INT (1), INT (1));
4371 op_rshift
.op1_range (op1
, integer_type_node
, lhs
, one
);
4372 ASSERT_TRUE (op1
.undefined_p ());
4375 // signed: ~[-1] = OP1 >> 31
4376 if (TYPE_PRECISION (integer_type_node
) > 31)
4378 int_range_max
lhs (INT (-1), INT (-1), VR_ANTI_RANGE
);
4379 int_range_max
shift (INT (31), INT (31));
4381 op_rshift
.op1_range (op1
, integer_type_node
, lhs
, shift
);
4382 int_range_max negatives
= range_negatives (integer_type_node
);
4383 negatives
.intersect (op1
);
4384 ASSERT_TRUE (negatives
.undefined_p ());
4389 range_op_bitwise_and_tests ()
4392 tree min
= vrp_val_min (integer_type_node
);
4393 tree max
= vrp_val_max (integer_type_node
);
4394 tree tiny
= fold_build2 (PLUS_EXPR
, integer_type_node
, min
,
4395 build_one_cst (integer_type_node
));
4396 int_range_max
i1 (tiny
, max
);
4397 int_range_max
i2 (build_int_cst (integer_type_node
, 255),
4398 build_int_cst (integer_type_node
, 255));
4400 // [MIN+1, MAX] = OP1 & 255: OP1 is VARYING
4401 op_bitwise_and
.op1_range (res
, integer_type_node
, i1
, i2
);
4402 ASSERT_TRUE (res
== int_range
<1> (integer_type_node
));
4404 // VARYING = OP1 & 255: OP1 is VARYING
4405 i1
= int_range
<1> (integer_type_node
);
4406 op_bitwise_and
.op1_range (res
, integer_type_node
, i1
, i2
);
4407 ASSERT_TRUE (res
== int_range
<1> (integer_type_node
));
4409 // (NONZERO | X) is nonzero.
4410 i1
.set_nonzero (integer_type_node
);
4411 i2
.set_varying (integer_type_node
);
4412 op_bitwise_or
.fold_range (res
, integer_type_node
, i1
, i2
);
4413 ASSERT_TRUE (res
.nonzero_p ());
4415 // (NEGATIVE | X) is nonzero.
4416 i1
= int_range
<1> (INT (-5), INT (-3));
4417 i2
.set_varying (integer_type_node
);
4418 op_bitwise_or
.fold_range (res
, integer_type_node
, i1
, i2
);
4419 ASSERT_FALSE (res
.contains_p (INT (0)));
4423 range_relational_tests ()
4425 int_range
<2> lhs (unsigned_char_type_node
);
4426 int_range
<2> op1 (UCHAR (8), UCHAR (10));
4427 int_range
<2> op2 (UCHAR (20), UCHAR (20));
4429 // Never wrapping additions mean LHS > OP1.
4430 tree_code code
= op_plus
.lhs_op1_relation (lhs
, op1
, op2
);
4431 ASSERT_TRUE (code
== GT_EXPR
);
4433 // Most wrapping additions mean nothing...
4434 op1
= int_range
<2> (UCHAR (8), UCHAR (10));
4435 op2
= int_range
<2> (UCHAR (0), UCHAR (255));
4436 code
= op_plus
.lhs_op1_relation (lhs
, op1
, op2
);
4437 ASSERT_TRUE (code
== VREL_NONE
);
4439 // However, always wrapping additions mean LHS < OP1.
4440 op1
= int_range
<2> (UCHAR (1), UCHAR (255));
4441 op2
= int_range
<2> (UCHAR (255), UCHAR (255));
4442 code
= op_plus
.lhs_op1_relation (lhs
, op1
, op2
);
4443 ASSERT_TRUE (code
== LT_EXPR
);
4449 range_op_rshift_tests ();
4450 range_op_lshift_tests ();
4451 range_op_bitwise_and_tests ();
4452 range_op_cast_tests ();
4453 range_relational_tests ();
4456 } // namespace selftest
4458 #endif // CHECKING_P