1 /* Code for range operators.
2 Copyright (C) 2017-2021 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 // If the range of either op1 or op2 is undefined, set the result to
67 // varying and return TRUE. If the caller truely cares about a result,
68 // they should pass in a varying if it has an undefined that it wants
69 // treated as a varying.
72 empty_range_varying (irange
&r
, tree type
,
73 const irange
&op1
, const irange
& op2
)
75 if (op1
.undefined_p () || op2
.undefined_p ())
84 // Return false if shifting by OP is undefined behavior. Otherwise, return
85 // true and the range it is to be shifted by. This allows trimming out of
86 // undefined ranges, leaving only valid ranges if there are any.
89 get_shift_range (irange
&r
, tree type
, const irange
&op
)
91 if (op
.undefined_p ())
94 // Build valid range and intersect it with the shift range.
95 r
= value_range (build_int_cst_type (op
.type (), 0),
96 build_int_cst_type (op
.type (), TYPE_PRECISION (type
) - 1));
99 // If there are no valid ranges in the shift range, returned false.
100 if (r
.undefined_p ())
105 // Return TRUE if 0 is within [WMIN, WMAX].
108 wi_includes_zero_p (tree type
, const wide_int
&wmin
, const wide_int
&wmax
)
110 signop sign
= TYPE_SIGN (type
);
111 return wi::le_p (wmin
, 0, sign
) && wi::ge_p (wmax
, 0, sign
);
114 // Return TRUE if [WMIN, WMAX] is the singleton 0.
117 wi_zero_p (tree type
, const wide_int
&wmin
, const wide_int
&wmax
)
119 unsigned prec
= TYPE_PRECISION (type
);
120 return wmin
== wmax
&& wi::eq_p (wmin
, wi::zero (prec
));
123 // Default wide_int fold operation returns [MIN, MAX].
126 range_operator::wi_fold (irange
&r
, tree type
,
127 const wide_int
&lh_lb ATTRIBUTE_UNUSED
,
128 const wide_int
&lh_ub ATTRIBUTE_UNUSED
,
129 const wide_int
&rh_lb ATTRIBUTE_UNUSED
,
130 const wide_int
&rh_ub ATTRIBUTE_UNUSED
) const
132 gcc_checking_assert (irange::supports_type_p (type
));
133 r
.set_varying (type
);
136 // Call wi_fold, except further split small subranges into constants.
137 // This can provide better precision. For something 8 >> [0,1]
138 // Instead of [8, 16], we will produce [8,8][16,16]
141 range_operator::wi_fold_in_parts (irange
&r
, tree type
,
142 const wide_int
&lh_lb
,
143 const wide_int
&lh_ub
,
144 const wide_int
&rh_lb
,
145 const wide_int
&rh_ub
) const
147 wi::overflow_type ov_rh
, ov_lh
;
149 wide_int rh_range
= wi::sub (rh_ub
, rh_lb
, TYPE_SIGN (type
), &ov_rh
);
150 wide_int lh_range
= wi::sub (lh_ub
, lh_lb
, TYPE_SIGN (type
), &ov_lh
);
151 signop sign
= TYPE_SIGN (type
);;
152 // If there are 2, 3, or 4 values in the RH range, do them separately.
153 // Call wi_fold_in_parts to check the RH side.
154 if (wi::gt_p (rh_range
, 0, sign
) && wi::lt_p (rh_range
, 4, sign
)
155 && ov_rh
== wi::OVF_NONE
)
157 wi_fold_in_parts (r
, type
, lh_lb
, lh_ub
, rh_lb
, rh_lb
);
158 if (wi::gt_p (rh_range
, 1, sign
))
160 wi_fold_in_parts (tmp
, type
, lh_lb
, lh_ub
, rh_lb
+ 1, rh_lb
+ 1);
162 if (wi::eq_p (rh_range
, 3))
164 wi_fold_in_parts (tmp
, type
, lh_lb
, lh_ub
, rh_lb
+ 2, rh_lb
+ 2);
168 wi_fold_in_parts (tmp
, type
, lh_lb
, lh_ub
, rh_ub
, rh_ub
);
171 // Otherise check for 2, 3, or 4 values in the LH range and split them up.
172 // The RH side has been checked, so no recursion needed.
173 else if (wi::gt_p (lh_range
, 0, sign
) && wi::lt_p (lh_range
, 4, sign
)
174 && ov_lh
== wi::OVF_NONE
)
176 wi_fold (r
, type
, lh_lb
, lh_lb
, rh_lb
, rh_ub
);
177 if (wi::gt_p (lh_range
, 1, sign
))
179 wi_fold (tmp
, type
, lh_lb
+ 1, lh_lb
+ 1, rh_lb
, rh_ub
);
181 if (wi::eq_p (lh_range
, 3))
183 wi_fold (tmp
, type
, lh_lb
+ 2, lh_lb
+ 2, rh_lb
, rh_ub
);
187 wi_fold (tmp
, type
, lh_ub
, lh_ub
, rh_lb
, rh_ub
);
190 // Otherwise just call wi_fold.
192 wi_fold (r
, type
, lh_lb
, lh_ub
, rh_lb
, rh_ub
);
195 // The default for fold is to break all ranges into sub-ranges and
196 // invoke the wi_fold method on each sub-range pair.
199 range_operator::fold_range (irange
&r
, tree type
,
202 relation_kind rel
) const
204 gcc_checking_assert (irange::supports_type_p (type
));
205 if (empty_range_varying (r
, type
, lh
, rh
))
208 unsigned num_lh
= lh
.num_pairs ();
209 unsigned num_rh
= rh
.num_pairs ();
211 // If both ranges are single pairs, fold directly into the result range.
212 if (num_lh
== 1 && num_rh
== 1)
214 wi_fold_in_parts (r
, type
, lh
.lower_bound (0), lh
.upper_bound (0),
215 rh
.lower_bound (0), rh
.upper_bound (0));
216 op1_op2_relation_effect (r
, type
, lh
, rh
, rel
);
222 for (unsigned x
= 0; x
< num_lh
; ++x
)
223 for (unsigned y
= 0; y
< num_rh
; ++y
)
225 wide_int lh_lb
= lh
.lower_bound (x
);
226 wide_int lh_ub
= lh
.upper_bound (x
);
227 wide_int rh_lb
= rh
.lower_bound (y
);
228 wide_int rh_ub
= rh
.upper_bound (y
);
229 wi_fold_in_parts (tmp
, type
, lh_lb
, lh_ub
, rh_lb
, rh_ub
);
233 op1_op2_relation_effect (r
, type
, lh
, rh
, rel
);
237 op1_op2_relation_effect (r
, type
, lh
, rh
, rel
);
241 // The default for op1_range is to return false.
244 range_operator::op1_range (irange
&r ATTRIBUTE_UNUSED
,
245 tree type ATTRIBUTE_UNUSED
,
246 const irange
&lhs ATTRIBUTE_UNUSED
,
247 const irange
&op2 ATTRIBUTE_UNUSED
,
248 relation_kind rel ATTRIBUTE_UNUSED
) const
253 // The default for op2_range is to return false.
256 range_operator::op2_range (irange
&r ATTRIBUTE_UNUSED
,
257 tree type ATTRIBUTE_UNUSED
,
258 const irange
&lhs ATTRIBUTE_UNUSED
,
259 const irange
&op1 ATTRIBUTE_UNUSED
,
260 relation_kind rel ATTRIBUTE_UNUSED
) const
265 // The default relation routines return VREL_NONE.
268 range_operator::lhs_op1_relation (const irange
&lhs ATTRIBUTE_UNUSED
,
269 const irange
&op1 ATTRIBUTE_UNUSED
,
270 const irange
&op2 ATTRIBUTE_UNUSED
) const
276 range_operator::lhs_op2_relation (const irange
&lhs ATTRIBUTE_UNUSED
,
277 const irange
&op1 ATTRIBUTE_UNUSED
,
278 const irange
&op2 ATTRIBUTE_UNUSED
) const
284 range_operator::op1_op2_relation (const irange
&lhs ATTRIBUTE_UNUSED
) const
289 // Default is no relation affects the LHS.
292 range_operator::op1_op2_relation_effect (irange
&lhs_range ATTRIBUTE_UNUSED
,
293 tree type ATTRIBUTE_UNUSED
,
294 const irange
&op1_range ATTRIBUTE_UNUSED
,
295 const irange
&op2_range ATTRIBUTE_UNUSED
,
296 relation_kind rel ATTRIBUTE_UNUSED
) const
301 // Create and return a range from a pair of wide-ints that are known
302 // to have overflowed (or underflowed).
305 value_range_from_overflowed_bounds (irange
&r
, tree type
,
306 const wide_int
&wmin
,
307 const wide_int
&wmax
)
309 const signop sgn
= TYPE_SIGN (type
);
310 const unsigned int prec
= TYPE_PRECISION (type
);
312 wide_int tmin
= wide_int::from (wmin
, prec
, sgn
);
313 wide_int tmax
= wide_int::from (wmax
, prec
, sgn
);
318 if (wi::cmp (tmin
, tmax
, sgn
) < 0)
321 if (wi::cmp (tmax
, tem
, sgn
) > 0)
324 // If the anti-range would cover nothing, drop to varying.
325 // Likewise if the anti-range bounds are outside of the types
327 if (covers
|| wi::cmp (tmin
, tmax
, sgn
) > 0)
328 r
.set_varying (type
);
331 tree tree_min
= wide_int_to_tree (type
, tmin
);
332 tree tree_max
= wide_int_to_tree (type
, tmax
);
333 r
.set (tree_min
, tree_max
, VR_ANTI_RANGE
);
337 // Create and return a range from a pair of wide-ints. MIN_OVF and
338 // MAX_OVF describe any overflow that might have occurred while
339 // calculating WMIN and WMAX respectively.
342 value_range_with_overflow (irange
&r
, tree type
,
343 const wide_int
&wmin
, const wide_int
&wmax
,
344 wi::overflow_type min_ovf
= wi::OVF_NONE
,
345 wi::overflow_type max_ovf
= wi::OVF_NONE
)
347 const signop sgn
= TYPE_SIGN (type
);
348 const unsigned int prec
= TYPE_PRECISION (type
);
349 const bool overflow_wraps
= TYPE_OVERFLOW_WRAPS (type
);
351 // For one bit precision if max != min, then the range covers all
353 if (prec
== 1 && wi::ne_p (wmax
, wmin
))
355 r
.set_varying (type
);
361 // If overflow wraps, truncate the values and adjust the range,
362 // kind, and bounds appropriately.
363 if ((min_ovf
!= wi::OVF_NONE
) == (max_ovf
!= wi::OVF_NONE
))
365 wide_int tmin
= wide_int::from (wmin
, prec
, sgn
);
366 wide_int tmax
= wide_int::from (wmax
, prec
, sgn
);
367 // If the limits are swapped, we wrapped around and cover
369 if (wi::gt_p (tmin
, tmax
, sgn
))
370 r
.set_varying (type
);
372 // No overflow or both overflow or underflow. The range
373 // kind stays normal.
374 r
.set (wide_int_to_tree (type
, tmin
),
375 wide_int_to_tree (type
, tmax
));
379 if ((min_ovf
== wi::OVF_UNDERFLOW
&& max_ovf
== wi::OVF_NONE
)
380 || (max_ovf
== wi::OVF_OVERFLOW
&& min_ovf
== wi::OVF_NONE
))
381 value_range_from_overflowed_bounds (r
, type
, wmin
, wmax
);
383 // Other underflow and/or overflow, drop to VR_VARYING.
384 r
.set_varying (type
);
388 // If both bounds either underflowed or overflowed, then the result
390 if ((min_ovf
== wi::OVF_OVERFLOW
&& max_ovf
== wi::OVF_OVERFLOW
)
391 || (min_ovf
== wi::OVF_UNDERFLOW
&& max_ovf
== wi::OVF_UNDERFLOW
))
397 // If overflow does not wrap, saturate to [MIN, MAX].
398 wide_int new_lb
, new_ub
;
399 if (min_ovf
== wi::OVF_UNDERFLOW
)
400 new_lb
= wi::min_value (prec
, sgn
);
401 else if (min_ovf
== wi::OVF_OVERFLOW
)
402 new_lb
= wi::max_value (prec
, sgn
);
406 if (max_ovf
== wi::OVF_UNDERFLOW
)
407 new_ub
= wi::min_value (prec
, sgn
);
408 else if (max_ovf
== wi::OVF_OVERFLOW
)
409 new_ub
= wi::max_value (prec
, sgn
);
413 r
.set (wide_int_to_tree (type
, new_lb
),
414 wide_int_to_tree (type
, new_ub
));
418 // Create and return a range from a pair of wide-ints. Canonicalize
419 // the case where the bounds are swapped. In which case, we transform
420 // [10,5] into [MIN,5][10,MAX].
423 create_possibly_reversed_range (irange
&r
, tree type
,
424 const wide_int
&new_lb
, const wide_int
&new_ub
)
426 signop s
= TYPE_SIGN (type
);
427 // If the bounds are swapped, treat the result as if an overflow occured.
428 if (wi::gt_p (new_lb
, new_ub
, s
))
429 value_range_from_overflowed_bounds (r
, type
, new_lb
, new_ub
);
431 // Otherwise it's just a normal range.
432 r
.set (wide_int_to_tree (type
, new_lb
), wide_int_to_tree (type
, new_ub
));
435 // Return an irange instance that is a boolean TRUE.
437 static inline int_range
<1>
438 range_true (tree type
)
440 unsigned prec
= TYPE_PRECISION (type
);
441 return int_range
<1> (type
, wi::one (prec
), wi::one (prec
));
444 // Return an irange instance that is a boolean FALSE.
446 static inline int_range
<1>
447 range_false (tree type
)
449 unsigned prec
= TYPE_PRECISION (type
);
450 return int_range
<1> (type
, wi::zero (prec
), wi::zero (prec
));
453 // Return an irange that covers both true and false.
455 static inline int_range
<1>
456 range_true_and_false (tree type
)
458 unsigned prec
= TYPE_PRECISION (type
);
459 return int_range
<1> (type
, wi::zero (prec
), wi::one (prec
));
462 enum bool_range_state
{ BRS_FALSE
, BRS_TRUE
, BRS_EMPTY
, BRS_FULL
};
464 // Return the summary information about boolean range LHS. If EMPTY/FULL,
465 // return the equivalent range for TYPE in R; if FALSE/TRUE, do nothing.
467 static bool_range_state
468 get_bool_state (irange
&r
, const irange
&lhs
, tree val_type
)
470 // If there is no result, then this is unexecutable.
471 if (lhs
.undefined_p ())
480 // For TRUE, we can't just test for [1,1] because Ada can have
481 // multi-bit booleans, and TRUE values can be: [1, MAX], ~[0], etc.
482 if (lhs
.contains_p (build_zero_cst (lhs
.type ())))
484 r
.set_varying (val_type
);
491 // For relation opcodes, first try to see if the supplied relation
492 // forces a true or false result, and return that.
493 // Then check for undefined operands. If none of this applies,
497 relop_early_resolve (irange
&r
, tree type
, const irange
&op1
,
498 const irange
&op2
, relation_kind rel
,
499 relation_kind my_rel
)
501 // If known relation is a complete subset of this relation, always true.
502 if (relation_union (rel
, my_rel
) == my_rel
)
504 r
= range_true (type
);
508 // If known relation has no subset of this relation, always false.
509 if (relation_intersect (rel
, my_rel
) == VREL_EMPTY
)
511 r
= range_false (type
);
515 // If either operand is undefined, return VARYING.
516 if (empty_range_varying (r
, type
, op1
, op2
))
523 class operator_equal
: public range_operator
526 virtual bool fold_range (irange
&r
, tree type
,
529 relation_kind rel
= VREL_NONE
) const;
530 virtual bool op1_range (irange
&r
, tree type
,
533 relation_kind rel
= VREL_NONE
) const;
534 virtual bool op2_range (irange
&r
, tree type
,
537 relation_kind rel
= VREL_NONE
) const;
538 virtual enum tree_code
op1_op2_relation (const irange
&lhs
) const;
541 // Check if the LHS range indicates a relation between OP1 and OP2.
544 operator_equal::op1_op2_relation (const irange
&lhs
) const
546 if (lhs
.undefined_p ())
549 // FALSE = op1 == op2 indicates NE_EXPR.
553 // TRUE = op1 == op2 indicates EQ_EXPR.
554 if (!lhs
.contains_p (build_zero_cst (lhs
.type ())))
561 operator_equal::fold_range (irange
&r
, tree type
,
564 relation_kind rel
) const
566 if (relop_early_resolve (r
, type
, op1
, op2
, rel
, EQ_EXPR
))
569 // We can be sure the values are always equal or not if both ranges
570 // consist of a single value, and then compare them.
571 if (wi::eq_p (op1
.lower_bound (), op1
.upper_bound ())
572 && wi::eq_p (op2
.lower_bound (), op2
.upper_bound ()))
574 if (wi::eq_p (op1
.lower_bound (), op2
.upper_bound()))
575 r
= range_true (type
);
577 r
= range_false (type
);
581 // If ranges do not intersect, we know the range is not equal,
582 // otherwise we don't know anything for sure.
583 int_range_max tmp
= op1
;
585 if (tmp
.undefined_p ())
586 r
= range_false (type
);
588 r
= range_true_and_false (type
);
594 operator_equal::op1_range (irange
&r
, tree type
,
597 relation_kind rel ATTRIBUTE_UNUSED
) const
599 switch (get_bool_state (r
, lhs
, type
))
602 // If the result is false, the only time we know anything is
603 // if OP2 is a constant.
604 if (wi::eq_p (op2
.lower_bound(), op2
.upper_bound()))
610 r
.set_varying (type
);
614 // If it's true, the result is the same as OP2.
625 operator_equal::op2_range (irange
&r
, tree type
,
628 relation_kind rel
) const
630 return operator_equal::op1_range (r
, type
, lhs
, op1
, rel
);
633 class operator_not_equal
: public range_operator
636 virtual bool fold_range (irange
&r
, tree type
,
639 relation_kind rel
= VREL_NONE
) const;
640 virtual bool op1_range (irange
&r
, tree type
,
643 relation_kind rel
= VREL_NONE
) const;
644 virtual bool op2_range (irange
&r
, tree type
,
647 relation_kind rel
= VREL_NONE
) const;
648 virtual enum tree_code
op1_op2_relation (const irange
&lhs
) const;
651 // Check if the LHS range indicates a relation between OP1 and OP2.
654 operator_not_equal::op1_op2_relation (const irange
&lhs
) const
656 if (lhs
.undefined_p ())
659 // FALSE = op1 != op2 indicates EQ_EXPR.
663 // TRUE = op1 != op2 indicates NE_EXPR.
664 if (!lhs
.contains_p (build_zero_cst (lhs
.type ())))
670 operator_not_equal::fold_range (irange
&r
, tree type
,
673 relation_kind rel
) const
675 if (relop_early_resolve (r
, type
, op1
, op2
, rel
, NE_EXPR
))
678 // We can be sure the values are always equal or not if both ranges
679 // consist of a single value, and then compare them.
680 if (wi::eq_p (op1
.lower_bound (), op1
.upper_bound ())
681 && wi::eq_p (op2
.lower_bound (), op2
.upper_bound ()))
683 if (wi::ne_p (op1
.lower_bound (), op2
.upper_bound()))
684 r
= range_true (type
);
686 r
= range_false (type
);
690 // If ranges do not intersect, we know the range is not equal,
691 // otherwise we don't know anything for sure.
692 int_range_max tmp
= op1
;
694 if (tmp
.undefined_p ())
695 r
= range_true (type
);
697 r
= range_true_and_false (type
);
703 operator_not_equal::op1_range (irange
&r
, tree type
,
706 relation_kind rel ATTRIBUTE_UNUSED
) const
708 switch (get_bool_state (r
, lhs
, type
))
711 // If the result is true, the only time we know anything is if
712 // OP2 is a constant.
713 if (wi::eq_p (op2
.lower_bound(), op2
.upper_bound()))
719 r
.set_varying (type
);
723 // If it's false, the result is the same as OP2.
735 operator_not_equal::op2_range (irange
&r
, tree type
,
738 relation_kind rel
) const
740 return operator_not_equal::op1_range (r
, type
, lhs
, op1
, rel
);
743 // (X < VAL) produces the range of [MIN, VAL - 1].
746 build_lt (irange
&r
, tree type
, const wide_int
&val
)
748 wi::overflow_type ov
;
750 signop sgn
= TYPE_SIGN (type
);
752 // Signed 1 bit cannot represent 1 for subtraction.
754 lim
= wi::add (val
, -1, sgn
, &ov
);
756 lim
= wi::sub (val
, 1, sgn
, &ov
);
758 // If val - 1 underflows, check if X < MIN, which is an empty range.
762 r
= int_range
<1> (type
, min_limit (type
), lim
);
765 // (X <= VAL) produces the range of [MIN, VAL].
768 build_le (irange
&r
, tree type
, const wide_int
&val
)
770 r
= int_range
<1> (type
, min_limit (type
), val
);
773 // (X > VAL) produces the range of [VAL + 1, MAX].
776 build_gt (irange
&r
, tree type
, const wide_int
&val
)
778 wi::overflow_type ov
;
780 signop sgn
= TYPE_SIGN (type
);
782 // Signed 1 bit cannot represent 1 for addition.
784 lim
= wi::sub (val
, -1, sgn
, &ov
);
786 lim
= wi::add (val
, 1, sgn
, &ov
);
787 // If val + 1 overflows, check is for X > MAX, which is an empty range.
791 r
= int_range
<1> (type
, lim
, max_limit (type
));
794 // (X >= val) produces the range of [VAL, MAX].
797 build_ge (irange
&r
, tree type
, const wide_int
&val
)
799 r
= int_range
<1> (type
, val
, max_limit (type
));
803 class operator_lt
: public range_operator
806 virtual bool fold_range (irange
&r
, tree type
,
809 relation_kind rel
= VREL_NONE
) const;
810 virtual bool op1_range (irange
&r
, tree type
,
813 relation_kind rel
= VREL_NONE
) const;
814 virtual bool op2_range (irange
&r
, tree type
,
817 relation_kind rel
= VREL_NONE
) const;
818 virtual enum tree_code
op1_op2_relation (const irange
&lhs
) const;
821 // Check if the LHS range indicates a relation between OP1 and OP2.
824 operator_lt::op1_op2_relation (const irange
&lhs
) const
826 if (lhs
.undefined_p ())
829 // FALSE = op1 < op2 indicates GE_EXPR.
833 // TRUE = op1 < op2 indicates LT_EXPR.
834 if (!lhs
.contains_p (build_zero_cst (lhs
.type ())))
840 operator_lt::fold_range (irange
&r
, tree type
,
843 relation_kind rel
) const
845 if (relop_early_resolve (r
, type
, op1
, op2
, rel
, LT_EXPR
))
848 signop sign
= TYPE_SIGN (op1
.type ());
849 gcc_checking_assert (sign
== TYPE_SIGN (op2
.type ()));
851 if (wi::lt_p (op1
.upper_bound (), op2
.lower_bound (), sign
))
852 r
= range_true (type
);
853 else if (!wi::lt_p (op1
.lower_bound (), op2
.upper_bound (), sign
))
854 r
= range_false (type
);
856 r
= range_true_and_false (type
);
861 operator_lt::op1_range (irange
&r
, tree type
,
864 relation_kind rel ATTRIBUTE_UNUSED
) const
866 switch (get_bool_state (r
, lhs
, type
))
869 build_lt (r
, type
, op2
.upper_bound ());
873 build_ge (r
, type
, op2
.lower_bound ());
883 operator_lt::op2_range (irange
&r
, tree type
,
886 relation_kind rel ATTRIBUTE_UNUSED
) const
888 switch (get_bool_state (r
, lhs
, type
))
891 build_le (r
, type
, op1
.upper_bound ());
895 build_gt (r
, type
, op1
.lower_bound ());
905 class operator_le
: public range_operator
908 virtual bool fold_range (irange
&r
, tree type
,
911 relation_kind rel
= VREL_NONE
) const;
912 virtual bool op1_range (irange
&r
, tree type
,
915 relation_kind rel
= VREL_NONE
) const;
916 virtual bool op2_range (irange
&r
, tree type
,
919 relation_kind rel
= VREL_NONE
) const;
920 virtual enum tree_code
op1_op2_relation (const irange
&lhs
) const;
923 // Check if the LHS range indicates a relation between OP1 and OP2.
926 operator_le::op1_op2_relation (const irange
&lhs
) const
928 if (lhs
.undefined_p ())
931 // FALSE = op1 <= op2 indicates GT_EXPR.
935 // TRUE = op1 <= op2 indicates LE_EXPR.
936 if (!lhs
.contains_p (build_zero_cst (lhs
.type ())))
942 operator_le::fold_range (irange
&r
, tree type
,
945 relation_kind rel
) const
947 if (relop_early_resolve (r
, type
, op1
, op2
, rel
, LE_EXPR
))
950 signop sign
= TYPE_SIGN (op1
.type ());
951 gcc_checking_assert (sign
== TYPE_SIGN (op2
.type ()));
953 if (wi::le_p (op1
.upper_bound (), op2
.lower_bound (), sign
))
954 r
= range_true (type
);
955 else if (!wi::le_p (op1
.lower_bound (), op2
.upper_bound (), sign
))
956 r
= range_false (type
);
958 r
= range_true_and_false (type
);
963 operator_le::op1_range (irange
&r
, tree type
,
966 relation_kind rel ATTRIBUTE_UNUSED
) const
968 switch (get_bool_state (r
, lhs
, type
))
971 build_le (r
, type
, op2
.upper_bound ());
975 build_gt (r
, type
, op2
.lower_bound ());
985 operator_le::op2_range (irange
&r
, tree type
,
988 relation_kind rel ATTRIBUTE_UNUSED
) const
990 switch (get_bool_state (r
, lhs
, type
))
993 build_lt (r
, type
, op1
.upper_bound ());
997 build_ge (r
, type
, op1
.lower_bound ());
1007 class operator_gt
: public range_operator
1010 virtual bool fold_range (irange
&r
, tree type
,
1013 relation_kind rel
= VREL_NONE
) const;
1014 virtual bool op1_range (irange
&r
, tree type
,
1017 relation_kind rel
= VREL_NONE
) const;
1018 virtual bool op2_range (irange
&r
, tree type
,
1021 relation_kind rel
= VREL_NONE
) const;
1022 virtual enum tree_code
op1_op2_relation (const irange
&lhs
) const;
1025 // Check if the LHS range indicates a relation between OP1 and OP2.
1028 operator_gt::op1_op2_relation (const irange
&lhs
) const
1030 if (lhs
.undefined_p ())
1033 // FALSE = op1 > op2 indicates LE_EXPR.
1037 // TRUE = op1 > op2 indicates GT_EXPR.
1038 if (!lhs
.contains_p (build_zero_cst (lhs
.type ())))
1045 operator_gt::fold_range (irange
&r
, tree type
,
1046 const irange
&op1
, const irange
&op2
,
1047 relation_kind rel
) const
1049 if (relop_early_resolve (r
, type
, op1
, op2
, rel
, GT_EXPR
))
1052 signop sign
= TYPE_SIGN (op1
.type ());
1053 gcc_checking_assert (sign
== TYPE_SIGN (op2
.type ()));
1055 if (wi::gt_p (op1
.lower_bound (), op2
.upper_bound (), sign
))
1056 r
= range_true (type
);
1057 else if (!wi::gt_p (op1
.upper_bound (), op2
.lower_bound (), sign
))
1058 r
= range_false (type
);
1060 r
= range_true_and_false (type
);
1065 operator_gt::op1_range (irange
&r
, tree type
,
1066 const irange
&lhs
, const irange
&op2
,
1067 relation_kind rel ATTRIBUTE_UNUSED
) const
1069 switch (get_bool_state (r
, lhs
, type
))
1072 build_gt (r
, type
, op2
.lower_bound ());
1076 build_le (r
, type
, op2
.upper_bound ());
1086 operator_gt::op2_range (irange
&r
, tree type
,
1089 relation_kind rel ATTRIBUTE_UNUSED
) const
1091 switch (get_bool_state (r
, lhs
, type
))
1094 build_ge (r
, type
, op1
.lower_bound ());
1098 build_lt (r
, type
, op1
.upper_bound ());
1108 class operator_ge
: public range_operator
1111 virtual bool fold_range (irange
&r
, tree type
,
1114 relation_kind rel
= VREL_NONE
) const;
1115 virtual bool op1_range (irange
&r
, tree type
,
1118 relation_kind rel
= VREL_NONE
) const;
1119 virtual bool op2_range (irange
&r
, tree type
,
1122 relation_kind rel
= VREL_NONE
) const;
1123 virtual enum tree_code
op1_op2_relation (const irange
&lhs
) const;
1126 // Check if the LHS range indicates a relation between OP1 and OP2.
1129 operator_ge::op1_op2_relation (const irange
&lhs
) const
1131 if (lhs
.undefined_p ())
1134 // FALSE = op1 >= op2 indicates LT_EXPR.
1138 // TRUE = op1 >= op2 indicates GE_EXPR.
1139 if (!lhs
.contains_p (build_zero_cst (lhs
.type ())))
1145 operator_ge::fold_range (irange
&r
, tree type
,
1148 relation_kind rel
) const
1150 if (relop_early_resolve (r
, type
, op1
, op2
, rel
, GE_EXPR
))
1153 signop sign
= TYPE_SIGN (op1
.type ());
1154 gcc_checking_assert (sign
== TYPE_SIGN (op2
.type ()));
1156 if (wi::ge_p (op1
.lower_bound (), op2
.upper_bound (), sign
))
1157 r
= range_true (type
);
1158 else if (!wi::ge_p (op1
.upper_bound (), op2
.lower_bound (), sign
))
1159 r
= range_false (type
);
1161 r
= range_true_and_false (type
);
1166 operator_ge::op1_range (irange
&r
, tree type
,
1169 relation_kind rel ATTRIBUTE_UNUSED
) const
1171 switch (get_bool_state (r
, lhs
, type
))
1174 build_ge (r
, type
, op2
.lower_bound ());
1178 build_lt (r
, type
, op2
.upper_bound ());
1188 operator_ge::op2_range (irange
&r
, tree type
,
1191 relation_kind rel ATTRIBUTE_UNUSED
) const
1193 switch (get_bool_state (r
, lhs
, type
))
1196 build_gt (r
, type
, op1
.lower_bound ());
1200 build_le (r
, type
, op1
.upper_bound ());
1210 class operator_plus
: public range_operator
1213 virtual bool op1_range (irange
&r
, tree type
,
1216 relation_kind rel ATTRIBUTE_UNUSED
) const;
1217 virtual bool op2_range (irange
&r
, tree type
,
1220 relation_kind rel ATTRIBUTE_UNUSED
) const;
1221 virtual void wi_fold (irange
&r
, tree type
,
1222 const wide_int
&lh_lb
,
1223 const wide_int
&lh_ub
,
1224 const wide_int
&rh_lb
,
1225 const wide_int
&rh_ub
) const;
1226 virtual enum tree_code
lhs_op1_relation (const irange
&lhs
, const irange
&op1
,
1227 const irange
&op2
) const;
1228 virtual enum tree_code
lhs_op2_relation (const irange
&lhs
, const irange
&op1
,
1229 const irange
&op2
) const;
1232 // Check to see if the range of OP2 indicates anything about the relation
1233 // between LHS and OP1.
1236 operator_plus::lhs_op1_relation (const irange
&lhs
,
1238 const irange
&op2
) const
1240 if (lhs
.undefined_p () || op1
.undefined_p () || op2
.undefined_p ())
1243 tree type
= lhs
.type ();
1244 unsigned prec
= TYPE_PRECISION (type
);
1245 wi::overflow_type ovf1
, ovf2
;
1246 signop sign
= TYPE_SIGN (type
);
1248 // LHS = OP1 + 0 indicates LHS == OP1.
1252 if (TYPE_OVERFLOW_WRAPS (type
))
1254 wi::add (op1
.lower_bound (), op2
.lower_bound (), sign
, &ovf1
);
1255 wi::add (op1
.upper_bound (), op2
.upper_bound (), sign
, &ovf2
);
1258 ovf1
= ovf2
= wi::OVF_NONE
;
1260 // Never wrapping additions.
1263 // Positive op2 means lhs > op1.
1264 if (wi::gt_p (op2
.lower_bound (), wi::zero (prec
), sign
))
1266 if (wi::ge_p (op2
.lower_bound (), wi::zero (prec
), sign
))
1269 // Negative op2 means lhs < op1.
1270 if (wi::lt_p (op2
.upper_bound (), wi::zero (prec
), sign
))
1272 if (wi::le_p (op2
.upper_bound (), wi::zero (prec
), sign
))
1275 // Always wrapping additions.
1276 else if (ovf1
&& ovf1
== ovf2
)
1278 // Positive op2 means lhs < op1.
1279 if (wi::gt_p (op2
.lower_bound (), wi::zero (prec
), sign
))
1281 if (wi::ge_p (op2
.lower_bound (), wi::zero (prec
), sign
))
1284 // Negative op2 means lhs > op1.
1285 if (wi::lt_p (op2
.upper_bound (), wi::zero (prec
), sign
))
1287 if (wi::le_p (op2
.upper_bound (), wi::zero (prec
), sign
))
1291 // If op2 does not contain 0, then LHS and OP1 can never be equal.
1292 if (!range_includes_zero_p (&op2
))
1298 // PLUS is symmetrical, so we can simply call lhs_op1_relation with reversed
1302 operator_plus::lhs_op2_relation (const irange
&lhs
, const irange
&op1
,
1303 const irange
&op2
) const
1305 return lhs_op1_relation (lhs
, op2
, op1
);
1309 operator_plus::wi_fold (irange
&r
, tree type
,
1310 const wide_int
&lh_lb
, const wide_int
&lh_ub
,
1311 const wide_int
&rh_lb
, const wide_int
&rh_ub
) const
1313 wi::overflow_type ov_lb
, ov_ub
;
1314 signop s
= TYPE_SIGN (type
);
1315 wide_int new_lb
= wi::add (lh_lb
, rh_lb
, s
, &ov_lb
);
1316 wide_int new_ub
= wi::add (lh_ub
, rh_ub
, s
, &ov_ub
);
1317 value_range_with_overflow (r
, type
, new_lb
, new_ub
, ov_lb
, ov_ub
);
1321 operator_plus::op1_range (irange
&r
, tree type
,
1324 relation_kind rel ATTRIBUTE_UNUSED
) const
1326 return range_op_handler (MINUS_EXPR
, type
)->fold_range (r
, type
, lhs
, op2
);
1330 operator_plus::op2_range (irange
&r
, tree type
,
1333 relation_kind rel ATTRIBUTE_UNUSED
) const
1335 return range_op_handler (MINUS_EXPR
, type
)->fold_range (r
, type
, lhs
, op1
);
1339 class operator_minus
: public range_operator
1342 virtual bool op1_range (irange
&r
, tree type
,
1345 relation_kind rel ATTRIBUTE_UNUSED
) const;
1346 virtual bool op2_range (irange
&r
, tree type
,
1349 relation_kind rel ATTRIBUTE_UNUSED
) const;
1350 virtual void wi_fold (irange
&r
, tree type
,
1351 const wide_int
&lh_lb
,
1352 const wide_int
&lh_ub
,
1353 const wide_int
&rh_lb
,
1354 const wide_int
&rh_ub
) const;
1355 virtual bool op1_op2_relation_effect (irange
&lhs_range
,
1357 const irange
&op1_range
,
1358 const irange
&op2_range
,
1359 relation_kind rel
) const;
1363 operator_minus::wi_fold (irange
&r
, tree type
,
1364 const wide_int
&lh_lb
, const wide_int
&lh_ub
,
1365 const wide_int
&rh_lb
, const wide_int
&rh_ub
) const
1367 wi::overflow_type ov_lb
, ov_ub
;
1368 signop s
= TYPE_SIGN (type
);
1369 wide_int new_lb
= wi::sub (lh_lb
, rh_ub
, s
, &ov_lb
);
1370 wide_int new_ub
= wi::sub (lh_ub
, rh_lb
, s
, &ov_ub
);
1371 value_range_with_overflow (r
, type
, new_lb
, new_ub
, ov_lb
, ov_ub
);
1374 // Check to see if the relation REL between OP1 and OP2 has any effect on the
1375 // LHS of the expression. If so, apply it to LHS_RANGE.
1378 operator_minus::op1_op2_relation_effect (irange
&lhs_range
, tree type
,
1379 const irange
&op1_range ATTRIBUTE_UNUSED
,
1380 const irange
&op2_range ATTRIBUTE_UNUSED
,
1381 relation_kind rel
) const
1383 if (rel
== VREL_NONE
)
1386 int_range
<2> rel_range
;
1387 unsigned prec
= TYPE_PRECISION (type
);
1388 signop sgn
= TYPE_SIGN (type
);
1390 // == and != produce [0,0] and ~[0,0] regardless of wrapping.
1392 rel_range
= int_range
<2> (type
, wi::zero (prec
), wi::zero (prec
));
1393 else if (rel
== NE_EXPR
)
1394 rel_range
= int_range
<2> (type
, wi::zero (prec
), wi::zero (prec
),
1396 else if (TYPE_OVERFLOW_WRAPS (type
))
1400 // For wrapping signed values and unsigned, if op1 > op2 or
1401 // op1 < op2, then op1 - op2 can be restricted to ~[0, 0].
1404 rel_range
= int_range
<2> (type
, wi::zero (prec
), wi::zero (prec
),
1415 // op1 > op2, op1 - op2 can be restricted to [1, +INF]
1417 rel_range
= int_range
<2> (type
, wi::one (prec
),
1418 wi::max_value (prec
, sgn
));
1420 // op1 >= op2, op1 - op2 can be restricted to [0, +INF]
1422 rel_range
= int_range
<2> (type
, wi::zero (prec
),
1423 wi::max_value (prec
, sgn
));
1425 // op1 < op2, op1 - op2 can be restricted to [-INF, -1]
1427 rel_range
= int_range
<2> (type
, wi::min_value (prec
, sgn
),
1428 wi::minus_one (prec
));
1430 // op1 <= op2, op1 - op2 can be restricted to [-INF, 0]
1432 rel_range
= int_range
<2> (type
, wi::min_value (prec
, sgn
),
1439 lhs_range
.intersect (rel_range
);
1444 operator_minus::op1_range (irange
&r
, tree type
,
1447 relation_kind rel ATTRIBUTE_UNUSED
) const
1449 return range_op_handler (PLUS_EXPR
, type
)->fold_range (r
, type
, lhs
, op2
);
1453 operator_minus::op2_range (irange
&r
, tree type
,
1456 relation_kind rel ATTRIBUTE_UNUSED
) const
1458 return fold_range (r
, type
, op1
, lhs
);
1462 class operator_min
: public range_operator
1465 virtual void wi_fold (irange
&r
, tree type
,
1466 const wide_int
&lh_lb
,
1467 const wide_int
&lh_ub
,
1468 const wide_int
&rh_lb
,
1469 const wide_int
&rh_ub
) const;
1473 operator_min::wi_fold (irange
&r
, tree type
,
1474 const wide_int
&lh_lb
, const wide_int
&lh_ub
,
1475 const wide_int
&rh_lb
, const wide_int
&rh_ub
) const
1477 signop s
= TYPE_SIGN (type
);
1478 wide_int new_lb
= wi::min (lh_lb
, rh_lb
, s
);
1479 wide_int new_ub
= wi::min (lh_ub
, rh_ub
, s
);
1480 value_range_with_overflow (r
, type
, new_lb
, new_ub
);
1484 class operator_max
: public range_operator
1487 virtual void wi_fold (irange
&r
, tree type
,
1488 const wide_int
&lh_lb
,
1489 const wide_int
&lh_ub
,
1490 const wide_int
&rh_lb
,
1491 const wide_int
&rh_ub
) const;
1495 operator_max::wi_fold (irange
&r
, tree type
,
1496 const wide_int
&lh_lb
, const wide_int
&lh_ub
,
1497 const wide_int
&rh_lb
, const wide_int
&rh_ub
) const
1499 signop s
= TYPE_SIGN (type
);
1500 wide_int new_lb
= wi::max (lh_lb
, rh_lb
, s
);
1501 wide_int new_ub
= wi::max (lh_ub
, rh_ub
, s
);
1502 value_range_with_overflow (r
, type
, new_lb
, new_ub
);
1506 class cross_product_operator
: public range_operator
1509 // Perform an operation between two wide-ints and place the result
1510 // in R. Return true if the operation overflowed.
1511 virtual bool wi_op_overflows (wide_int
&r
,
1514 const wide_int
&) const = 0;
1516 // Calculate the cross product of two sets of sub-ranges and return it.
1517 void wi_cross_product (irange
&r
, tree type
,
1518 const wide_int
&lh_lb
,
1519 const wide_int
&lh_ub
,
1520 const wide_int
&rh_lb
,
1521 const wide_int
&rh_ub
) const;
1524 // Calculate the cross product of two sets of ranges and return it.
1526 // Multiplications, divisions and shifts are a bit tricky to handle,
1527 // depending on the mix of signs we have in the two ranges, we need to
1528 // operate on different values to get the minimum and maximum values
1529 // for the new range. One approach is to figure out all the
1530 // variations of range combinations and do the operations.
1532 // However, this involves several calls to compare_values and it is
1533 // pretty convoluted. It's simpler to do the 4 operations (MIN0 OP
1534 // MIN1, MIN0 OP MAX1, MAX0 OP MIN1 and MAX0 OP MAX0 OP MAX1) and then
1535 // figure the smallest and largest values to form the new range.
1538 cross_product_operator::wi_cross_product (irange
&r
, tree type
,
1539 const wide_int
&lh_lb
,
1540 const wide_int
&lh_ub
,
1541 const wide_int
&rh_lb
,
1542 const wide_int
&rh_ub
) const
1544 wide_int cp1
, cp2
, cp3
, cp4
;
1545 // Default to varying.
1546 r
.set_varying (type
);
1548 // Compute the 4 cross operations, bailing if we get an overflow we
1550 if (wi_op_overflows (cp1
, type
, lh_lb
, rh_lb
))
1552 if (wi::eq_p (lh_lb
, lh_ub
))
1554 else if (wi_op_overflows (cp3
, type
, lh_ub
, rh_lb
))
1556 if (wi::eq_p (rh_lb
, rh_ub
))
1558 else if (wi_op_overflows (cp2
, type
, lh_lb
, rh_ub
))
1560 if (wi::eq_p (lh_lb
, lh_ub
))
1562 else if (wi_op_overflows (cp4
, type
, lh_ub
, rh_ub
))
1566 signop sign
= TYPE_SIGN (type
);
1567 if (wi::gt_p (cp1
, cp2
, sign
))
1568 std::swap (cp1
, cp2
);
1569 if (wi::gt_p (cp3
, cp4
, sign
))
1570 std::swap (cp3
, cp4
);
1572 // Choose min and max from the ordered pairs.
1573 wide_int res_lb
= wi::min (cp1
, cp3
, sign
);
1574 wide_int res_ub
= wi::max (cp2
, cp4
, sign
);
1575 value_range_with_overflow (r
, type
, res_lb
, res_ub
);
1579 class operator_mult
: public cross_product_operator
1582 virtual void wi_fold (irange
&r
, tree type
,
1583 const wide_int
&lh_lb
,
1584 const wide_int
&lh_ub
,
1585 const wide_int
&rh_lb
,
1586 const wide_int
&rh_ub
) const;
1587 virtual bool wi_op_overflows (wide_int
&res
, tree type
,
1588 const wide_int
&w0
, const wide_int
&w1
) const;
1589 virtual bool op1_range (irange
&r
, tree type
,
1592 relation_kind rel ATTRIBUTE_UNUSED
) const;
1593 virtual bool op2_range (irange
&r
, tree type
,
1596 relation_kind rel ATTRIBUTE_UNUSED
) const;
1600 operator_mult::op1_range (irange
&r
, tree type
,
1601 const irange
&lhs
, const irange
&op2
,
1602 relation_kind rel ATTRIBUTE_UNUSED
) const
1606 // We can't solve 0 = OP1 * N by dividing by N with a wrapping type.
1607 // For example: For 0 = OP1 * 2, OP1 could be 0, or MAXINT, whereas
1608 // for 4 = OP1 * 2, OP1 could be 2 or 130 (unsigned 8-bit)
1609 if (TYPE_OVERFLOW_WRAPS (type
))
1612 if (op2
.singleton_p (&offset
) && !integer_zerop (offset
))
1613 return range_op_handler (TRUNC_DIV_EXPR
, type
)->fold_range (r
, type
,
1619 operator_mult::op2_range (irange
&r
, tree type
,
1620 const irange
&lhs
, const irange
&op1
,
1621 relation_kind rel
) const
1623 return operator_mult::op1_range (r
, type
, lhs
, op1
, rel
);
1627 operator_mult::wi_op_overflows (wide_int
&res
, tree type
,
1628 const wide_int
&w0
, const wide_int
&w1
) const
1630 wi::overflow_type overflow
= wi::OVF_NONE
;
1631 signop sign
= TYPE_SIGN (type
);
1632 res
= wi::mul (w0
, w1
, sign
, &overflow
);
1633 if (overflow
&& TYPE_OVERFLOW_UNDEFINED (type
))
1635 // For multiplication, the sign of the overflow is given
1636 // by the comparison of the signs of the operands.
1637 if (sign
== UNSIGNED
|| w0
.sign_mask () == w1
.sign_mask ())
1638 res
= wi::max_value (w0
.get_precision (), sign
);
1640 res
= wi::min_value (w0
.get_precision (), sign
);
1647 operator_mult::wi_fold (irange
&r
, tree type
,
1648 const wide_int
&lh_lb
, const wide_int
&lh_ub
,
1649 const wide_int
&rh_lb
, const wide_int
&rh_ub
) const
1651 if (TYPE_OVERFLOW_UNDEFINED (type
))
1653 wi_cross_product (r
, type
, lh_lb
, lh_ub
, rh_lb
, rh_ub
);
1657 // Multiply the ranges when overflow wraps. This is basically fancy
1658 // code so we don't drop to varying with an unsigned
1661 // This test requires 2*prec bits if both operands are signed and
1662 // 2*prec + 2 bits if either is not. Therefore, extend the values
1663 // using the sign of the result to PREC2. From here on out,
1664 // everthing is just signed math no matter what the input types
1667 signop sign
= TYPE_SIGN (type
);
1668 unsigned prec
= TYPE_PRECISION (type
);
1669 widest2_int min0
= widest2_int::from (lh_lb
, sign
);
1670 widest2_int max0
= widest2_int::from (lh_ub
, sign
);
1671 widest2_int min1
= widest2_int::from (rh_lb
, sign
);
1672 widest2_int max1
= widest2_int::from (rh_ub
, sign
);
1673 widest2_int sizem1
= wi::mask
<widest2_int
> (prec
, false);
1674 widest2_int size
= sizem1
+ 1;
1676 // Canonicalize the intervals.
1677 if (sign
== UNSIGNED
)
1679 if (wi::ltu_p (size
, min0
+ max0
))
1684 if (wi::ltu_p (size
, min1
+ max1
))
1691 // Sort the 4 products so that min is in prod0 and max is in
1693 widest2_int prod0
= min0
* min1
;
1694 widest2_int prod1
= min0
* max1
;
1695 widest2_int prod2
= max0
* min1
;
1696 widest2_int prod3
= max0
* max1
;
1698 // min0min1 > max0max1
1700 std::swap (prod0
, prod3
);
1702 // min0max1 > max0min1
1704 std::swap (prod1
, prod2
);
1707 std::swap (prod0
, prod1
);
1710 std::swap (prod2
, prod3
);
1713 prod2
= prod3
- prod0
;
1714 if (wi::geu_p (prod2
, sizem1
))
1715 // The range covers all values.
1716 r
.set_varying (type
);
1719 wide_int new_lb
= wide_int::from (prod0
, prec
, sign
);
1720 wide_int new_ub
= wide_int::from (prod3
, prec
, sign
);
1721 create_possibly_reversed_range (r
, type
, new_lb
, new_ub
);
1726 class operator_div
: public cross_product_operator
1729 operator_div (enum tree_code c
) { code
= c
; }
1730 virtual void wi_fold (irange
&r
, tree type
,
1731 const wide_int
&lh_lb
,
1732 const wide_int
&lh_ub
,
1733 const wide_int
&rh_lb
,
1734 const wide_int
&rh_ub
) const;
1735 virtual bool wi_op_overflows (wide_int
&res
, tree type
,
1736 const wide_int
&, const wide_int
&) const;
1738 enum tree_code code
;
1742 operator_div::wi_op_overflows (wide_int
&res
, tree type
,
1743 const wide_int
&w0
, const wide_int
&w1
) const
1748 wi::overflow_type overflow
= wi::OVF_NONE
;
1749 signop sign
= TYPE_SIGN (type
);
1753 case EXACT_DIV_EXPR
:
1754 // EXACT_DIV_EXPR is implemented as TRUNC_DIV_EXPR in
1755 // operator_exact_divide. No need to handle it here.
1758 case TRUNC_DIV_EXPR
:
1759 res
= wi::div_trunc (w0
, w1
, sign
, &overflow
);
1761 case FLOOR_DIV_EXPR
:
1762 res
= wi::div_floor (w0
, w1
, sign
, &overflow
);
1764 case ROUND_DIV_EXPR
:
1765 res
= wi::div_round (w0
, w1
, sign
, &overflow
);
1768 res
= wi::div_ceil (w0
, w1
, sign
, &overflow
);
1774 if (overflow
&& TYPE_OVERFLOW_UNDEFINED (type
))
1776 // For division, the only case is -INF / -1 = +INF.
1777 res
= wi::max_value (w0
.get_precision (), sign
);
1784 operator_div::wi_fold (irange
&r
, tree type
,
1785 const wide_int
&lh_lb
, const wide_int
&lh_ub
,
1786 const wide_int
&rh_lb
, const wide_int
&rh_ub
) const
1788 const wide_int dividend_min
= lh_lb
;
1789 const wide_int dividend_max
= lh_ub
;
1790 const wide_int divisor_min
= rh_lb
;
1791 const wide_int divisor_max
= rh_ub
;
1792 signop sign
= TYPE_SIGN (type
);
1793 unsigned prec
= TYPE_PRECISION (type
);
1794 wide_int extra_min
, extra_max
;
1796 // If we know we won't divide by zero, just do the division.
1797 if (!wi_includes_zero_p (type
, divisor_min
, divisor_max
))
1799 wi_cross_product (r
, type
, dividend_min
, dividend_max
,
1800 divisor_min
, divisor_max
);
1804 // If flag_non_call_exceptions, we must not eliminate a division by zero.
1805 if (cfun
->can_throw_non_call_exceptions
)
1807 r
.set_varying (type
);
1811 // If we're definitely dividing by zero, there's nothing to do.
1812 if (wi_zero_p (type
, divisor_min
, divisor_max
))
1818 // Perform the division in 2 parts, [LB, -1] and [1, UB], which will
1819 // skip any division by zero.
1821 // First divide by the negative numbers, if any.
1822 if (wi::neg_p (divisor_min
, sign
))
1823 wi_cross_product (r
, type
, dividend_min
, dividend_max
,
1824 divisor_min
, wi::minus_one (prec
));
1828 // Then divide by the non-zero positive numbers, if any.
1829 if (wi::gt_p (divisor_max
, wi::zero (prec
), sign
))
1832 wi_cross_product (tmp
, type
, dividend_min
, dividend_max
,
1833 wi::one (prec
), divisor_max
);
1836 // We shouldn't still have undefined here.
1837 gcc_checking_assert (!r
.undefined_p ());
1840 operator_div
op_trunc_div (TRUNC_DIV_EXPR
);
1841 operator_div
op_floor_div (FLOOR_DIV_EXPR
);
1842 operator_div
op_round_div (ROUND_DIV_EXPR
);
1843 operator_div
op_ceil_div (CEIL_DIV_EXPR
);
1846 class operator_exact_divide
: public operator_div
1849 operator_exact_divide () : operator_div (TRUNC_DIV_EXPR
) { }
1850 virtual bool op1_range (irange
&r
, tree type
,
1853 relation_kind rel ATTRIBUTE_UNUSED
) const;
1858 operator_exact_divide::op1_range (irange
&r
, tree type
,
1861 relation_kind rel ATTRIBUTE_UNUSED
) const
1864 // [2, 4] = op1 / [3,3] since its exact divide, no need to worry about
1865 // remainders in the endpoints, so op1 = [2,4] * [3,3] = [6,12].
1866 // We wont bother trying to enumerate all the in between stuff :-P
1867 // TRUE accuraacy is [6,6][9,9][12,12]. This is unlikely to matter most of
1868 // the time however.
1869 // If op2 is a multiple of 2, we would be able to set some non-zero bits.
1870 if (op2
.singleton_p (&offset
)
1871 && !integer_zerop (offset
))
1872 return range_op_handler (MULT_EXPR
, type
)->fold_range (r
, type
, lhs
, op2
);
1877 class operator_lshift
: public cross_product_operator
1880 virtual bool op1_range (irange
&r
, tree type
,
1883 relation_kind rel
= VREL_NONE
) const;
1884 virtual bool fold_range (irange
&r
, tree type
,
1887 relation_kind rel
= VREL_NONE
) const;
1889 virtual void wi_fold (irange
&r
, tree type
,
1890 const wide_int
&lh_lb
, const wide_int
&lh_ub
,
1891 const wide_int
&rh_lb
, const wide_int
&rh_ub
) const;
1892 virtual bool wi_op_overflows (wide_int
&res
,
1895 const wide_int
&) const;
1898 class operator_rshift
: public cross_product_operator
1901 virtual bool fold_range (irange
&r
, tree type
,
1904 relation_kind rel
= VREL_NONE
) const;
1905 virtual void wi_fold (irange
&r
, tree type
,
1906 const wide_int
&lh_lb
,
1907 const wide_int
&lh_ub
,
1908 const wide_int
&rh_lb
,
1909 const wide_int
&rh_ub
) const;
1910 virtual bool wi_op_overflows (wide_int
&res
,
1913 const wide_int
&w1
) const;
1914 virtual bool op1_range (irange
&, tree type
,
1917 relation_kind rel
= VREL_NONE
) const;
1922 operator_lshift::fold_range (irange
&r
, tree type
,
1925 relation_kind rel
) const
1927 int_range_max shift_range
;
1928 if (!get_shift_range (shift_range
, type
, op2
))
1930 if (op2
.undefined_p ())
1933 r
.set_varying (type
);
1937 // Transform left shifts by constants into multiplies.
1938 if (shift_range
.singleton_p ())
1940 unsigned shift
= shift_range
.lower_bound ().to_uhwi ();
1941 wide_int tmp
= wi::set_bit_in_zero (shift
, TYPE_PRECISION (type
));
1942 int_range
<1> mult (type
, tmp
, tmp
);
1944 // Force wrapping multiplication.
1945 bool saved_flag_wrapv
= flag_wrapv
;
1946 bool saved_flag_wrapv_pointer
= flag_wrapv_pointer
;
1948 flag_wrapv_pointer
= 1;
1949 bool b
= op_mult
.fold_range (r
, type
, op1
, mult
);
1950 flag_wrapv
= saved_flag_wrapv
;
1951 flag_wrapv_pointer
= saved_flag_wrapv_pointer
;
1955 // Otherwise, invoke the generic fold routine.
1956 return range_operator::fold_range (r
, type
, op1
, shift_range
, rel
);
1960 operator_lshift::wi_fold (irange
&r
, tree type
,
1961 const wide_int
&lh_lb
, const wide_int
&lh_ub
,
1962 const wide_int
&rh_lb
, const wide_int
&rh_ub
) const
1964 signop sign
= TYPE_SIGN (type
);
1965 unsigned prec
= TYPE_PRECISION (type
);
1966 int overflow_pos
= sign
== SIGNED
? prec
- 1 : prec
;
1967 int bound_shift
= overflow_pos
- rh_ub
.to_shwi ();
1968 // If bound_shift == HOST_BITS_PER_WIDE_INT, the llshift can
1969 // overflow. However, for that to happen, rh.max needs to be zero,
1970 // which means rh is a singleton range of zero, which means we simply return
1971 // [lh_lb, lh_ub] as the range.
1972 if (wi::eq_p (rh_ub
, rh_lb
) && wi::eq_p (rh_ub
, 0))
1974 r
= int_range
<2> (type
, lh_lb
, lh_ub
);
1978 wide_int bound
= wi::set_bit_in_zero (bound_shift
, prec
);
1979 wide_int complement
= ~(bound
- 1);
1980 wide_int low_bound
, high_bound
;
1981 bool in_bounds
= false;
1983 if (sign
== UNSIGNED
)
1986 high_bound
= complement
;
1987 if (wi::ltu_p (lh_ub
, low_bound
))
1989 // [5, 6] << [1, 2] == [10, 24].
1990 // We're shifting out only zeroes, the value increases
1994 else if (wi::ltu_p (high_bound
, lh_lb
))
1996 // [0xffffff00, 0xffffffff] << [1, 2]
1997 // == [0xfffffc00, 0xfffffffe].
1998 // We're shifting out only ones, the value decreases
2005 // [-1, 1] << [1, 2] == [-4, 4]
2006 low_bound
= complement
;
2008 if (wi::lts_p (lh_ub
, high_bound
)
2009 && wi::lts_p (low_bound
, lh_lb
))
2011 // For non-negative numbers, we're shifting out only zeroes,
2012 // the value increases monotonically. For negative numbers,
2013 // we're shifting out only ones, the value decreases
2020 wi_cross_product (r
, type
, lh_lb
, lh_ub
, rh_lb
, rh_ub
);
2022 r
.set_varying (type
);
2026 operator_lshift::wi_op_overflows (wide_int
&res
, tree type
,
2027 const wide_int
&w0
, const wide_int
&w1
) const
2029 signop sign
= TYPE_SIGN (type
);
2032 // It's unclear from the C standard whether shifts can overflow.
2033 // The following code ignores overflow; perhaps a C standard
2034 // interpretation ruling is needed.
2035 res
= wi::rshift (w0
, -w1
, sign
);
2038 res
= wi::lshift (w0
, w1
);
2043 operator_lshift::op1_range (irange
&r
,
2047 relation_kind rel ATTRIBUTE_UNUSED
) const
2050 if (op2
.singleton_p (&shift_amount
))
2052 wide_int shift
= wi::to_wide (shift_amount
);
2053 if (wi::lt_p (shift
, 0, SIGNED
))
2055 if (wi::ge_p (shift
, wi::uhwi (TYPE_PRECISION (type
),
2056 TYPE_PRECISION (op2
.type ())),
2065 // Work completely in unsigned mode to start.
2067 if (TYPE_SIGN (type
) == SIGNED
)
2069 int_range_max tmp
= lhs
;
2070 utype
= unsigned_type_for (type
);
2071 range_cast (tmp
, utype
);
2072 op_rshift
.fold_range (r
, utype
, tmp
, op2
);
2075 op_rshift
.fold_range (r
, utype
, lhs
, op2
);
2077 // Start with ranges which can produce the LHS by right shifting the
2078 // result by the shift amount.
2079 // ie [0x08, 0xF0] = op1 << 2 will start with
2080 // [00001000, 11110000] = op1 << 2
2081 // [0x02, 0x4C] aka [00000010, 00111100]
2083 // Then create a range from the LB with the least significant upper bit
2084 // set, to the upper bound with all the bits set.
2085 // This would be [0x42, 0xFC] aka [01000010, 11111100].
2087 // Ideally we do this for each subrange, but just lump them all for now.
2088 unsigned low_bits
= TYPE_PRECISION (utype
)
2089 - TREE_INT_CST_LOW (shift_amount
);
2090 wide_int up_mask
= wi::mask (low_bits
, true, TYPE_PRECISION (utype
));
2091 wide_int new_ub
= wi::bit_or (up_mask
, r
.upper_bound ());
2092 wide_int new_lb
= wi::set_bit (r
.lower_bound (), low_bits
);
2093 int_range
<2> fill_range (utype
, new_lb
, new_ub
);
2094 r
.union_ (fill_range
);
2097 range_cast (r
, type
);
2104 operator_rshift::op1_range (irange
&r
,
2108 relation_kind rel ATTRIBUTE_UNUSED
) const
2111 if (op2
.singleton_p (&shift
))
2113 // Ignore nonsensical shifts.
2114 unsigned prec
= TYPE_PRECISION (type
);
2115 if (wi::ge_p (wi::to_wide (shift
),
2116 wi::uhwi (prec
, TYPE_PRECISION (TREE_TYPE (shift
))),
2119 if (wi::to_wide (shift
) == 0)
2125 // Folding the original operation may discard some impossible
2126 // ranges from the LHS.
2127 int_range_max lhs_refined
;
2128 op_rshift
.fold_range (lhs_refined
, type
, int_range
<1> (type
), op2
);
2129 lhs_refined
.intersect (lhs
);
2130 if (lhs_refined
.undefined_p ())
2135 int_range_max
shift_range (shift
, shift
);
2136 int_range_max lb
, ub
;
2137 op_lshift
.fold_range (lb
, type
, lhs_refined
, shift_range
);
2139 // 0000 0111 = OP1 >> 3
2141 // OP1 is anything from 0011 1000 to 0011 1111. That is, a
2142 // range from LHS<<3 plus a mask of the 3 bits we shifted on the
2143 // right hand side (0x07).
2144 tree mask
= fold_build1 (BIT_NOT_EXPR
, type
,
2145 fold_build2 (LSHIFT_EXPR
, type
,
2146 build_minus_one_cst (type
),
2148 int_range_max
mask_range (build_zero_cst (type
), mask
);
2149 op_plus
.fold_range (ub
, type
, lb
, mask_range
);
2152 if (!lhs_refined
.contains_p (build_zero_cst (type
)))
2154 mask_range
.invert ();
2155 r
.intersect (mask_range
);
2163 operator_rshift::wi_op_overflows (wide_int
&res
,
2166 const wide_int
&w1
) const
2168 signop sign
= TYPE_SIGN (type
);
2170 res
= wi::lshift (w0
, -w1
);
2173 // It's unclear from the C standard whether shifts can overflow.
2174 // The following code ignores overflow; perhaps a C standard
2175 // interpretation ruling is needed.
2176 res
= wi::rshift (w0
, w1
, sign
);
2182 operator_rshift::fold_range (irange
&r
, tree type
,
2185 relation_kind rel
) const
2187 int_range_max shift
;
2188 if (!get_shift_range (shift
, type
, op2
))
2190 if (op2
.undefined_p ())
2193 r
.set_varying (type
);
2197 return range_operator::fold_range (r
, type
, op1
, shift
, rel
);
2201 operator_rshift::wi_fold (irange
&r
, tree type
,
2202 const wide_int
&lh_lb
, const wide_int
&lh_ub
,
2203 const wide_int
&rh_lb
, const wide_int
&rh_ub
) const
2205 wi_cross_product (r
, type
, lh_lb
, lh_ub
, rh_lb
, rh_ub
);
2209 class operator_cast
: public range_operator
2212 virtual bool fold_range (irange
&r
, tree type
,
2215 relation_kind rel
= VREL_NONE
) const;
2216 virtual bool op1_range (irange
&r
, tree type
,
2219 relation_kind rel
= VREL_NONE
) const;
2221 bool truncating_cast_p (const irange
&inner
, const irange
&outer
) const;
2222 bool inside_domain_p (const wide_int
&min
, const wide_int
&max
,
2223 const irange
&outer
) const;
2224 void fold_pair (irange
&r
, unsigned index
, const irange
&inner
,
2225 const irange
&outer
) const;
2228 // Return TRUE if casting from INNER to OUTER is a truncating cast.
2231 operator_cast::truncating_cast_p (const irange
&inner
,
2232 const irange
&outer
) const
2234 return TYPE_PRECISION (outer
.type ()) < TYPE_PRECISION (inner
.type ());
2237 // Return TRUE if [MIN,MAX] is inside the domain of RANGE's type.
2240 operator_cast::inside_domain_p (const wide_int
&min
,
2241 const wide_int
&max
,
2242 const irange
&range
) const
2244 wide_int domain_min
= wi::to_wide (vrp_val_min (range
.type ()));
2245 wide_int domain_max
= wi::to_wide (vrp_val_max (range
.type ()));
2246 signop domain_sign
= TYPE_SIGN (range
.type ());
2247 return (wi::le_p (min
, domain_max
, domain_sign
)
2248 && wi::le_p (max
, domain_max
, domain_sign
)
2249 && wi::ge_p (min
, domain_min
, domain_sign
)
2250 && wi::ge_p (max
, domain_min
, domain_sign
));
2254 // Helper for fold_range which work on a pair at a time.
2257 operator_cast::fold_pair (irange
&r
, unsigned index
,
2258 const irange
&inner
,
2259 const irange
&outer
) const
2261 tree inner_type
= inner
.type ();
2262 tree outer_type
= outer
.type ();
2263 signop inner_sign
= TYPE_SIGN (inner_type
);
2264 unsigned outer_prec
= TYPE_PRECISION (outer_type
);
2266 // check to see if casting from INNER to OUTER is a conversion that
2267 // fits in the resulting OUTER type.
2268 wide_int inner_lb
= inner
.lower_bound (index
);
2269 wide_int inner_ub
= inner
.upper_bound (index
);
2270 if (truncating_cast_p (inner
, outer
))
2272 // We may be able to accomodate a truncating cast if the
2273 // resulting range can be represented in the target type...
2274 if (wi::rshift (wi::sub (inner_ub
, inner_lb
),
2275 wi::uhwi (outer_prec
, TYPE_PRECISION (inner
.type ())),
2278 r
.set_varying (outer_type
);
2282 // ...but we must still verify that the final range fits in the
2283 // domain. This catches -fstrict-enum restrictions where the domain
2284 // range is smaller than what fits in the underlying type.
2285 wide_int min
= wide_int::from (inner_lb
, outer_prec
, inner_sign
);
2286 wide_int max
= wide_int::from (inner_ub
, outer_prec
, inner_sign
);
2287 if (inside_domain_p (min
, max
, outer
))
2288 create_possibly_reversed_range (r
, outer_type
, min
, max
);
2290 r
.set_varying (outer_type
);
2295 operator_cast::fold_range (irange
&r
, tree type ATTRIBUTE_UNUSED
,
2296 const irange
&inner
,
2297 const irange
&outer
,
2298 relation_kind rel ATTRIBUTE_UNUSED
) const
2300 if (empty_range_varying (r
, type
, inner
, outer
))
2303 gcc_checking_assert (outer
.varying_p ());
2304 gcc_checking_assert (inner
.num_pairs () > 0);
2306 // Avoid a temporary by folding the first pair directly into the result.
2307 fold_pair (r
, 0, inner
, outer
);
2309 // Then process any additonal pairs by unioning with their results.
2310 for (unsigned x
= 1; x
< inner
.num_pairs (); ++x
)
2313 fold_pair (tmp
, x
, inner
, outer
);
2322 operator_cast::op1_range (irange
&r
, tree type
,
2325 relation_kind rel ATTRIBUTE_UNUSED
) const
2327 tree lhs_type
= lhs
.type ();
2328 gcc_checking_assert (types_compatible_p (op2
.type(), type
));
2330 // If we are calculating a pointer, shortcut to what we really care about.
2331 if (POINTER_TYPE_P (type
))
2333 // Conversion from other pointers or a constant (including 0/NULL)
2334 // are straightforward.
2335 if (POINTER_TYPE_P (lhs
.type ())
2336 || (lhs
.singleton_p ()
2337 && TYPE_PRECISION (lhs
.type ()) >= TYPE_PRECISION (type
)))
2340 range_cast (r
, type
);
2344 // If the LHS is not a pointer nor a singleton, then it is
2345 // either VARYING or non-zero.
2346 if (!lhs
.contains_p (build_zero_cst (lhs
.type ())))
2347 r
.set_nonzero (type
);
2349 r
.set_varying (type
);
2355 if (truncating_cast_p (op2
, lhs
))
2357 if (lhs
.varying_p ())
2358 r
.set_varying (type
);
2361 // We want to insert the LHS as an unsigned value since it
2362 // would not trigger the signed bit of the larger type.
2363 int_range_max converted_lhs
= lhs
;
2364 range_cast (converted_lhs
, unsigned_type_for (lhs_type
));
2365 range_cast (converted_lhs
, type
);
2366 // Start by building the positive signed outer range for the type.
2367 wide_int lim
= wi::set_bit_in_zero (TYPE_PRECISION (lhs_type
),
2368 TYPE_PRECISION (type
));
2369 r
= int_range
<1> (type
, lim
, wi::max_value (TYPE_PRECISION (type
),
2371 // For the signed part, we need to simply union the 2 ranges now.
2372 r
.union_ (converted_lhs
);
2374 // Create maximal negative number outside of LHS bits.
2375 lim
= wi::mask (TYPE_PRECISION (lhs_type
), true,
2376 TYPE_PRECISION (type
));
2377 // Add this to the unsigned LHS range(s).
2378 int_range_max
lim_range (type
, lim
, lim
);
2379 int_range_max lhs_neg
;
2380 range_op_handler (PLUS_EXPR
, type
)->fold_range (lhs_neg
,
2384 // lhs_neg now has all the negative versions of the LHS.
2385 // Now union in all the values from SIGNED MIN (0x80000) to
2386 // lim-1 in order to fill in all the ranges with the upper
2389 // PR 97317. If the lhs has only 1 bit less precision than the rhs,
2390 // we don't need to create a range from min to lim-1
2391 // calculate neg range traps trying to create [lim, lim - 1].
2392 wide_int min_val
= wi::min_value (TYPE_PRECISION (type
), SIGNED
);
2395 int_range_max
neg (type
,
2396 wi::min_value (TYPE_PRECISION (type
),
2399 lhs_neg
.union_ (neg
);
2401 // And finally, munge the signed and unsigned portions.
2404 // And intersect with any known value passed in the extra operand.
2410 if (TYPE_PRECISION (lhs_type
) == TYPE_PRECISION (type
))
2414 // The cast is not truncating, and the range is restricted to
2415 // the range of the RHS by this assignment.
2417 // Cast the range of the RHS to the type of the LHS.
2418 fold_range (tmp
, lhs_type
, int_range
<1> (type
), int_range
<1> (lhs_type
));
2419 // Intersect this with the LHS range will produce the range,
2420 // which will be cast to the RHS type before returning.
2421 tmp
.intersect (lhs
);
2424 // Cast the calculated range to the type of the RHS.
2425 fold_range (r
, type
, tmp
, int_range
<1> (type
));
2430 class operator_logical_and
: public range_operator
2433 virtual bool fold_range (irange
&r
, tree type
,
2436 relation_kind rel
= VREL_NONE
) const;
2437 virtual bool op1_range (irange
&r
, tree type
,
2440 relation_kind rel
= VREL_NONE
) const;
2441 virtual bool op2_range (irange
&r
, tree type
,
2444 relation_kind rel
= VREL_NONE
) const;
2449 operator_logical_and::fold_range (irange
&r
, tree type
,
2452 relation_kind rel ATTRIBUTE_UNUSED
) const
2454 if (empty_range_varying (r
, type
, lh
, rh
))
2457 // 0 && anything is 0.
2458 if ((wi::eq_p (lh
.lower_bound (), 0) && wi::eq_p (lh
.upper_bound (), 0))
2459 || (wi::eq_p (lh
.lower_bound (), 0) && wi::eq_p (rh
.upper_bound (), 0)))
2460 r
= range_false (type
);
2461 else if (lh
.contains_p (build_zero_cst (lh
.type ()))
2462 || rh
.contains_p (build_zero_cst (rh
.type ())))
2463 // To reach this point, there must be a logical 1 on each side, and
2464 // the only remaining question is whether there is a zero or not.
2465 r
= range_true_and_false (type
);
2467 r
= range_true (type
);
2472 operator_logical_and::op1_range (irange
&r
, tree type
,
2474 const irange
&op2 ATTRIBUTE_UNUSED
,
2475 relation_kind rel ATTRIBUTE_UNUSED
) const
2477 switch (get_bool_state (r
, lhs
, type
))
2480 // A true result means both sides of the AND must be true.
2481 r
= range_true (type
);
2484 // Any other result means only one side has to be false, the
2485 // other side can be anything. So we cannott be sure of any
2487 r
= range_true_and_false (type
);
2494 operator_logical_and::op2_range (irange
&r
, tree type
,
2497 relation_kind rel ATTRIBUTE_UNUSED
) const
2499 return operator_logical_and::op1_range (r
, type
, lhs
, op1
);
2503 class operator_bitwise_and
: public range_operator
2506 virtual bool fold_range (irange
&r
, tree type
,
2509 relation_kind rel
= VREL_NONE
) const;
2510 virtual bool op1_range (irange
&r
, tree type
,
2513 relation_kind rel
= VREL_NONE
) const;
2514 virtual bool op2_range (irange
&r
, tree type
,
2517 relation_kind rel
= VREL_NONE
) const;
2518 virtual void wi_fold (irange
&r
, tree type
,
2519 const wide_int
&lh_lb
,
2520 const wide_int
&lh_ub
,
2521 const wide_int
&rh_lb
,
2522 const wide_int
&rh_ub
) const;
2524 void simple_op1_range_solver (irange
&r
, tree type
,
2526 const irange
&op2
) const;
2527 void remove_impossible_ranges (irange
&r
, const irange
&rh
) const;
2531 unsigned_singleton_p (const irange
&op
)
2534 if (op
.singleton_p (&mask
))
2536 wide_int x
= wi::to_wide (mask
);
2537 return wi::ge_p (x
, 0, TYPE_SIGN (op
.type ()));
2542 // Remove any ranges from R that are known to be impossible when an
2543 // range is ANDed with MASK.
2546 operator_bitwise_and::remove_impossible_ranges (irange
&r
,
2547 const irange
&rmask
) const
2549 if (r
.undefined_p () || !unsigned_singleton_p (rmask
))
2552 wide_int mask
= rmask
.lower_bound ();
2553 tree type
= r
.type ();
2554 int prec
= TYPE_PRECISION (type
);
2555 int leading_zeros
= wi::clz (mask
);
2556 int_range_max impossible_ranges
;
2558 /* We know that starting at the most significant bit, any 0 in the
2559 mask means the resulting range cannot contain a 1 in that same
2560 position. This means the following ranges are impossible:
2564 01xx xxxx [0100 0000, 0111 1111]
2565 001x xxxx [0010 0000, 0011 1111]
2566 0000 01xx [0000 0100, 0000 0111]
2567 0000 0001 [0000 0001, 0000 0001]
2569 wide_int one
= wi::one (prec
);
2570 for (int i
= 0; i
< prec
- leading_zeros
- 1; ++i
)
2571 if (wi::bit_and (mask
, wi::lshift (one
, wi::uhwi (i
, prec
))) == 0)
2573 tree lb
= fold_build2 (LSHIFT_EXPR
, type
,
2574 build_one_cst (type
),
2575 build_int_cst (type
, i
));
2576 tree ub_left
= fold_build1 (BIT_NOT_EXPR
, type
,
2577 fold_build2 (LSHIFT_EXPR
, type
,
2578 build_minus_one_cst (type
),
2579 build_int_cst (type
, i
)));
2580 tree ub_right
= fold_build2 (LSHIFT_EXPR
, type
,
2581 build_one_cst (type
),
2582 build_int_cst (type
, i
));
2583 tree ub
= fold_build2 (BIT_IOR_EXPR
, type
, ub_left
, ub_right
);
2584 impossible_ranges
.union_ (int_range
<1> (lb
, ub
));
2586 if (!impossible_ranges
.undefined_p ())
2588 impossible_ranges
.invert ();
2589 r
.intersect (impossible_ranges
);
2594 operator_bitwise_and::fold_range (irange
&r
, tree type
,
2597 relation_kind rel ATTRIBUTE_UNUSED
) const
2599 if (range_operator::fold_range (r
, type
, lh
, rh
))
2601 // FIXME: This is temporarily disabled because, though it
2602 // generates better ranges, it's noticeably slower for evrp.
2603 // remove_impossible_ranges (r, rh);
2610 // Optimize BIT_AND_EXPR and BIT_IOR_EXPR in terms of a mask if
2611 // possible. Basically, see if we can optimize:
2615 // [LB op Z, UB op Z]
2617 // If the optimization was successful, accumulate the range in R and
2621 wi_optimize_and_or (irange
&r
,
2622 enum tree_code code
,
2624 const wide_int
&lh_lb
, const wide_int
&lh_ub
,
2625 const wide_int
&rh_lb
, const wide_int
&rh_ub
)
2627 // Calculate the singleton mask among the ranges, if any.
2628 wide_int lower_bound
, upper_bound
, mask
;
2629 if (wi::eq_p (rh_lb
, rh_ub
))
2632 lower_bound
= lh_lb
;
2633 upper_bound
= lh_ub
;
2635 else if (wi::eq_p (lh_lb
, lh_ub
))
2638 lower_bound
= rh_lb
;
2639 upper_bound
= rh_ub
;
2644 // If Z is a constant which (for op | its bitwise not) has n
2645 // consecutive least significant bits cleared followed by m 1
2646 // consecutive bits set immediately above it and either
2647 // m + n == precision, or (x >> (m + n)) == (y >> (m + n)).
2649 // The least significant n bits of all the values in the range are
2650 // cleared or set, the m bits above it are preserved and any bits
2651 // above these are required to be the same for all values in the
2655 if (code
== BIT_IOR_EXPR
)
2657 if (wi::eq_p (w
, 0))
2658 n
= w
.get_precision ();
2662 w
= ~(w
| wi::mask (n
, false, w
.get_precision ()));
2663 if (wi::eq_p (w
, 0))
2664 m
= w
.get_precision () - n
;
2666 m
= wi::ctz (w
) - n
;
2668 wide_int new_mask
= wi::mask (m
+ n
, true, w
.get_precision ());
2669 if ((new_mask
& lower_bound
) != (new_mask
& upper_bound
))
2672 wide_int res_lb
, res_ub
;
2673 if (code
== BIT_AND_EXPR
)
2675 res_lb
= wi::bit_and (lower_bound
, mask
);
2676 res_ub
= wi::bit_and (upper_bound
, mask
);
2678 else if (code
== BIT_IOR_EXPR
)
2680 res_lb
= wi::bit_or (lower_bound
, mask
);
2681 res_ub
= wi::bit_or (upper_bound
, mask
);
2685 value_range_with_overflow (r
, type
, res_lb
, res_ub
);
2687 // Furthermore, if the mask is non-zero, an IOR cannot contain zero.
2688 if (code
== BIT_IOR_EXPR
&& wi::ne_p (mask
, 0))
2691 tmp
.set_nonzero (type
);
2697 // For range [LB, UB] compute two wide_int bit masks.
2699 // In the MAYBE_NONZERO bit mask, if some bit is unset, it means that
2700 // for all numbers in the range the bit is 0, otherwise it might be 0
2703 // In the MUSTBE_NONZERO bit mask, if some bit is set, it means that
2704 // for all numbers in the range the bit is 1, otherwise it might be 0
2708 wi_set_zero_nonzero_bits (tree type
,
2709 const wide_int
&lb
, const wide_int
&ub
,
2710 wide_int
&maybe_nonzero
,
2711 wide_int
&mustbe_nonzero
)
2713 signop sign
= TYPE_SIGN (type
);
2715 if (wi::eq_p (lb
, ub
))
2716 maybe_nonzero
= mustbe_nonzero
= lb
;
2717 else if (wi::ge_p (lb
, 0, sign
) || wi::lt_p (ub
, 0, sign
))
2719 wide_int xor_mask
= lb
^ ub
;
2720 maybe_nonzero
= lb
| ub
;
2721 mustbe_nonzero
= lb
& ub
;
2724 wide_int mask
= wi::mask (wi::floor_log2 (xor_mask
), false,
2725 maybe_nonzero
.get_precision ());
2726 maybe_nonzero
= maybe_nonzero
| mask
;
2727 mustbe_nonzero
= wi::bit_and_not (mustbe_nonzero
, mask
);
2732 maybe_nonzero
= wi::minus_one (lb
.get_precision ());
2733 mustbe_nonzero
= wi::zero (lb
.get_precision ());
2738 operator_bitwise_and::wi_fold (irange
&r
, tree type
,
2739 const wide_int
&lh_lb
,
2740 const wide_int
&lh_ub
,
2741 const wide_int
&rh_lb
,
2742 const wide_int
&rh_ub
) const
2744 if (wi_optimize_and_or (r
, BIT_AND_EXPR
, type
, lh_lb
, lh_ub
, rh_lb
, rh_ub
))
2747 wide_int maybe_nonzero_lh
, mustbe_nonzero_lh
;
2748 wide_int maybe_nonzero_rh
, mustbe_nonzero_rh
;
2749 wi_set_zero_nonzero_bits (type
, lh_lb
, lh_ub
,
2750 maybe_nonzero_lh
, mustbe_nonzero_lh
);
2751 wi_set_zero_nonzero_bits (type
, rh_lb
, rh_ub
,
2752 maybe_nonzero_rh
, mustbe_nonzero_rh
);
2754 wide_int new_lb
= mustbe_nonzero_lh
& mustbe_nonzero_rh
;
2755 wide_int new_ub
= maybe_nonzero_lh
& maybe_nonzero_rh
;
2756 signop sign
= TYPE_SIGN (type
);
2757 unsigned prec
= TYPE_PRECISION (type
);
2758 // If both input ranges contain only negative values, we can
2759 // truncate the result range maximum to the minimum of the
2760 // input range maxima.
2761 if (wi::lt_p (lh_ub
, 0, sign
) && wi::lt_p (rh_ub
, 0, sign
))
2763 new_ub
= wi::min (new_ub
, lh_ub
, sign
);
2764 new_ub
= wi::min (new_ub
, rh_ub
, sign
);
2766 // If either input range contains only non-negative values
2767 // we can truncate the result range maximum to the respective
2768 // maximum of the input range.
2769 if (wi::ge_p (lh_lb
, 0, sign
))
2770 new_ub
= wi::min (new_ub
, lh_ub
, sign
);
2771 if (wi::ge_p (rh_lb
, 0, sign
))
2772 new_ub
= wi::min (new_ub
, rh_ub
, sign
);
2773 // PR68217: In case of signed & sign-bit-CST should
2774 // result in [-INF, 0] instead of [-INF, INF].
2775 if (wi::gt_p (new_lb
, new_ub
, sign
))
2777 wide_int sign_bit
= wi::set_bit_in_zero (prec
- 1, prec
);
2779 && ((wi::eq_p (lh_lb
, lh_ub
)
2780 && !wi::cmps (lh_lb
, sign_bit
))
2781 || (wi::eq_p (rh_lb
, rh_ub
)
2782 && !wi::cmps (rh_lb
, sign_bit
))))
2784 new_lb
= wi::min_value (prec
, sign
);
2785 new_ub
= wi::zero (prec
);
2788 // If the limits got swapped around, return varying.
2789 if (wi::gt_p (new_lb
, new_ub
,sign
))
2790 r
.set_varying (type
);
2792 value_range_with_overflow (r
, type
, new_lb
, new_ub
);
2796 set_nonzero_range_from_mask (irange
&r
, tree type
, const irange
&lhs
)
2798 if (!lhs
.contains_p (build_zero_cst (type
)))
2799 r
= range_nonzero (type
);
2801 r
.set_varying (type
);
2804 // This was shamelessly stolen from register_edge_assert_for_2 and
2805 // adjusted to work with iranges.
2808 operator_bitwise_and::simple_op1_range_solver (irange
&r
, tree type
,
2810 const irange
&op2
) const
2812 if (!op2
.singleton_p ())
2814 set_nonzero_range_from_mask (r
, type
, lhs
);
2817 unsigned int nprec
= TYPE_PRECISION (type
);
2818 wide_int cst2v
= op2
.lower_bound ();
2819 bool cst2n
= wi::neg_p (cst2v
, TYPE_SIGN (type
));
2822 sgnbit
= wi::set_bit_in_zero (nprec
- 1, nprec
);
2824 sgnbit
= wi::zero (nprec
);
2826 // Solve [lhs.lower_bound (), +INF] = x & MASK.
2828 // Minimum unsigned value for >= if (VAL & CST2) == VAL is VAL and
2829 // maximum unsigned value is ~0. For signed comparison, if CST2
2830 // doesn't have the most significant bit set, handle it similarly. If
2831 // CST2 has MSB set, the minimum is the same, and maximum is ~0U/2.
2832 wide_int valv
= lhs
.lower_bound ();
2833 wide_int minv
= valv
& cst2v
, maxv
;
2834 bool we_know_nothing
= false;
2837 // If (VAL & CST2) != VAL, X & CST2 can't be equal to VAL.
2838 minv
= masked_increment (valv
, cst2v
, sgnbit
, nprec
);
2841 // If we can't determine anything on this bound, fall
2842 // through and conservatively solve for the other end point.
2843 we_know_nothing
= true;
2846 maxv
= wi::mask (nprec
- (cst2n
? 1 : 0), false, nprec
);
2847 if (we_know_nothing
)
2848 r
.set_varying (type
);
2850 r
= int_range
<1> (type
, minv
, maxv
);
2852 // Solve [-INF, lhs.upper_bound ()] = x & MASK.
2854 // Minimum unsigned value for <= is 0 and maximum unsigned value is
2855 // VAL | ~CST2 if (VAL & CST2) == VAL. Otherwise, find smallest
2857 // VAL2 > VAL && (VAL2 & CST2) == VAL2 and use (VAL2 - 1) | ~CST2
2859 // For signed comparison, if CST2 doesn't have most significant bit
2860 // set, handle it similarly. If CST2 has MSB set, the maximum is
2861 // the same and minimum is INT_MIN.
2862 valv
= lhs
.upper_bound ();
2863 minv
= valv
& cst2v
;
2868 maxv
= masked_increment (valv
, cst2v
, sgnbit
, nprec
);
2871 // If we couldn't determine anything on either bound, return
2873 if (we_know_nothing
)
2881 int_range
<1> upper_bits (type
, minv
, maxv
);
2882 r
.intersect (upper_bits
);
2886 operator_bitwise_and::op1_range (irange
&r
, tree type
,
2889 relation_kind rel ATTRIBUTE_UNUSED
) const
2891 if (types_compatible_p (type
, boolean_type_node
))
2892 return op_logical_and
.op1_range (r
, type
, lhs
, op2
);
2895 for (unsigned i
= 0; i
< lhs
.num_pairs (); ++i
)
2897 int_range_max
chunk (lhs
.type (),
2898 lhs
.lower_bound (i
),
2899 lhs
.upper_bound (i
));
2901 simple_op1_range_solver (res
, type
, chunk
, op2
);
2904 if (r
.undefined_p ())
2905 set_nonzero_range_from_mask (r
, type
, lhs
);
2910 operator_bitwise_and::op2_range (irange
&r
, tree type
,
2913 relation_kind rel ATTRIBUTE_UNUSED
) const
2915 return operator_bitwise_and::op1_range (r
, type
, lhs
, op1
);
2919 class operator_logical_or
: public range_operator
2922 virtual bool fold_range (irange
&r
, tree type
,
2925 relation_kind rel
= VREL_NONE
) const;
2926 virtual bool op1_range (irange
&r
, tree type
,
2929 relation_kind rel
= VREL_NONE
) const;
2930 virtual bool op2_range (irange
&r
, tree type
,
2933 relation_kind rel
= VREL_NONE
) const;
2937 operator_logical_or::fold_range (irange
&r
, tree type ATTRIBUTE_UNUSED
,
2940 relation_kind rel ATTRIBUTE_UNUSED
) const
2942 if (empty_range_varying (r
, type
, lh
, rh
))
2951 operator_logical_or::op1_range (irange
&r
, tree type
,
2953 const irange
&op2 ATTRIBUTE_UNUSED
,
2954 relation_kind rel ATTRIBUTE_UNUSED
) const
2956 switch (get_bool_state (r
, lhs
, type
))
2959 // A false result means both sides of the OR must be false.
2960 r
= range_false (type
);
2963 // Any other result means only one side has to be true, the
2964 // other side can be anything. so we can't be sure of any result
2966 r
= range_true_and_false (type
);
2973 operator_logical_or::op2_range (irange
&r
, tree type
,
2976 relation_kind rel ATTRIBUTE_UNUSED
) const
2978 return operator_logical_or::op1_range (r
, type
, lhs
, op1
);
2982 class operator_bitwise_or
: public range_operator
2985 virtual bool op1_range (irange
&r
, tree type
,
2988 relation_kind rel
= VREL_NONE
) const;
2989 virtual bool op2_range (irange
&r
, tree type
,
2992 relation_kind rel
= VREL_NONE
) const;
2993 virtual void wi_fold (irange
&r
, tree type
,
2994 const wide_int
&lh_lb
,
2995 const wide_int
&lh_ub
,
2996 const wide_int
&rh_lb
,
2997 const wide_int
&rh_ub
) const;
3001 operator_bitwise_or::wi_fold (irange
&r
, tree type
,
3002 const wide_int
&lh_lb
,
3003 const wide_int
&lh_ub
,
3004 const wide_int
&rh_lb
,
3005 const wide_int
&rh_ub
) const
3007 if (wi_optimize_and_or (r
, BIT_IOR_EXPR
, type
, lh_lb
, lh_ub
, rh_lb
, rh_ub
))
3010 wide_int maybe_nonzero_lh
, mustbe_nonzero_lh
;
3011 wide_int maybe_nonzero_rh
, mustbe_nonzero_rh
;
3012 wi_set_zero_nonzero_bits (type
, lh_lb
, lh_ub
,
3013 maybe_nonzero_lh
, mustbe_nonzero_lh
);
3014 wi_set_zero_nonzero_bits (type
, rh_lb
, rh_ub
,
3015 maybe_nonzero_rh
, mustbe_nonzero_rh
);
3016 wide_int new_lb
= mustbe_nonzero_lh
| mustbe_nonzero_rh
;
3017 wide_int new_ub
= maybe_nonzero_lh
| maybe_nonzero_rh
;
3018 signop sign
= TYPE_SIGN (type
);
3019 // If the input ranges contain only positive values we can
3020 // truncate the minimum of the result range to the maximum
3021 // of the input range minima.
3022 if (wi::ge_p (lh_lb
, 0, sign
)
3023 && wi::ge_p (rh_lb
, 0, sign
))
3025 new_lb
= wi::max (new_lb
, lh_lb
, sign
);
3026 new_lb
= wi::max (new_lb
, rh_lb
, sign
);
3028 // If either input range contains only negative values
3029 // we can truncate the minimum of the result range to the
3030 // respective minimum range.
3031 if (wi::lt_p (lh_ub
, 0, sign
))
3032 new_lb
= wi::max (new_lb
, lh_lb
, sign
);
3033 if (wi::lt_p (rh_ub
, 0, sign
))
3034 new_lb
= wi::max (new_lb
, rh_lb
, sign
);
3035 // If the limits got swapped around, return a conservative range.
3036 if (wi::gt_p (new_lb
, new_ub
, sign
))
3038 // Make sure that nonzero|X is nonzero.
3039 if (wi::gt_p (lh_lb
, 0, sign
)
3040 || wi::gt_p (rh_lb
, 0, sign
)
3041 || wi::lt_p (lh_ub
, 0, sign
)
3042 || wi::lt_p (rh_ub
, 0, sign
))
3043 r
.set_nonzero (type
);
3045 r
.set_varying (type
);
3048 value_range_with_overflow (r
, type
, new_lb
, new_ub
);
3052 operator_bitwise_or::op1_range (irange
&r
, tree type
,
3055 relation_kind rel ATTRIBUTE_UNUSED
) const
3057 // If this is really a logical wi_fold, call that.
3058 if (types_compatible_p (type
, boolean_type_node
))
3059 return op_logical_or
.op1_range (r
, type
, lhs
, op2
);
3063 tree zero
= build_zero_cst (type
);
3064 r
= int_range
<1> (zero
, zero
);
3067 r
.set_varying (type
);
3072 operator_bitwise_or::op2_range (irange
&r
, tree type
,
3075 relation_kind rel ATTRIBUTE_UNUSED
) const
3077 return operator_bitwise_or::op1_range (r
, type
, lhs
, op1
);
3081 class operator_bitwise_xor
: public range_operator
3084 virtual void wi_fold (irange
&r
, tree type
,
3085 const wide_int
&lh_lb
,
3086 const wide_int
&lh_ub
,
3087 const wide_int
&rh_lb
,
3088 const wide_int
&rh_ub
) const;
3089 virtual bool op1_range (irange
&r
, tree type
,
3092 relation_kind rel
= VREL_NONE
) const;
3093 virtual bool op2_range (irange
&r
, tree type
,
3096 relation_kind rel
= VREL_NONE
) const;
3097 virtual bool op1_op2_relation_effect (irange
&lhs_range
,
3099 const irange
&op1_range
,
3100 const irange
&op2_range
,
3101 relation_kind rel
) const;
3105 operator_bitwise_xor::wi_fold (irange
&r
, tree type
,
3106 const wide_int
&lh_lb
,
3107 const wide_int
&lh_ub
,
3108 const wide_int
&rh_lb
,
3109 const wide_int
&rh_ub
) const
3111 signop sign
= TYPE_SIGN (type
);
3112 wide_int maybe_nonzero_lh
, mustbe_nonzero_lh
;
3113 wide_int maybe_nonzero_rh
, mustbe_nonzero_rh
;
3114 wi_set_zero_nonzero_bits (type
, lh_lb
, lh_ub
,
3115 maybe_nonzero_lh
, mustbe_nonzero_lh
);
3116 wi_set_zero_nonzero_bits (type
, rh_lb
, rh_ub
,
3117 maybe_nonzero_rh
, mustbe_nonzero_rh
);
3119 wide_int result_zero_bits
= ((mustbe_nonzero_lh
& mustbe_nonzero_rh
)
3120 | ~(maybe_nonzero_lh
| maybe_nonzero_rh
));
3121 wide_int result_one_bits
3122 = (wi::bit_and_not (mustbe_nonzero_lh
, maybe_nonzero_rh
)
3123 | wi::bit_and_not (mustbe_nonzero_rh
, maybe_nonzero_lh
));
3124 wide_int new_ub
= ~result_zero_bits
;
3125 wide_int new_lb
= result_one_bits
;
3127 // If the range has all positive or all negative values, the result
3128 // is better than VARYING.
3129 if (wi::lt_p (new_lb
, 0, sign
) || wi::ge_p (new_ub
, 0, sign
))
3130 value_range_with_overflow (r
, type
, new_lb
, new_ub
);
3132 r
.set_varying (type
);
3136 operator_bitwise_xor::op1_op2_relation_effect (irange
&lhs_range
,
3140 relation_kind rel
) const
3142 if (rel
== VREL_NONE
)
3145 int_range
<2> rel_range
;
3150 rel_range
.set_zero (type
);
3153 rel_range
.set_nonzero (type
);
3159 lhs_range
.intersect (rel_range
);
3164 operator_bitwise_xor::op1_range (irange
&r
, tree type
,
3167 relation_kind rel ATTRIBUTE_UNUSED
) const
3169 if (lhs
.undefined_p () || lhs
.varying_p ())
3174 if (types_compatible_p (type
, boolean_type_node
))
3176 switch (get_bool_state (r
, lhs
, type
))
3179 if (op2
.varying_p ())
3180 r
.set_varying (type
);
3181 else if (op2
.zero_p ())
3182 r
= range_true (type
);
3184 r
= range_false (type
);
3194 r
.set_varying (type
);
3199 operator_bitwise_xor::op2_range (irange
&r
, tree type
,
3202 relation_kind rel ATTRIBUTE_UNUSED
) const
3204 return operator_bitwise_xor::op1_range (r
, type
, lhs
, op1
);
3207 class operator_trunc_mod
: public range_operator
3210 virtual void wi_fold (irange
&r
, tree type
,
3211 const wide_int
&lh_lb
,
3212 const wide_int
&lh_ub
,
3213 const wide_int
&rh_lb
,
3214 const wide_int
&rh_ub
) const;
3215 virtual bool op1_range (irange
&r
, tree type
,
3218 relation_kind rel ATTRIBUTE_UNUSED
) const;
3219 virtual bool op2_range (irange
&r
, tree type
,
3222 relation_kind rel ATTRIBUTE_UNUSED
) const;
3226 operator_trunc_mod::wi_fold (irange
&r
, tree type
,
3227 const wide_int
&lh_lb
,
3228 const wide_int
&lh_ub
,
3229 const wide_int
&rh_lb
,
3230 const wide_int
&rh_ub
) const
3232 wide_int new_lb
, new_ub
, tmp
;
3233 signop sign
= TYPE_SIGN (type
);
3234 unsigned prec
= TYPE_PRECISION (type
);
3236 // Mod 0 is undefined.
3237 if (wi_zero_p (type
, rh_lb
, rh_ub
))
3243 // Check for constant and try to fold.
3244 if (lh_lb
== lh_ub
&& rh_lb
== rh_ub
)
3246 wi::overflow_type ov
= wi::OVF_NONE
;
3247 tmp
= wi::mod_trunc (lh_lb
, rh_lb
, sign
, &ov
);
3248 if (ov
== wi::OVF_NONE
)
3250 r
= int_range
<2> (type
, tmp
, tmp
);
3255 // ABS (A % B) < ABS (B) and either 0 <= A % B <= A or A <= A % B <= 0.
3260 new_ub
= wi::smax (new_ub
, tmp
);
3263 if (sign
== UNSIGNED
)
3264 new_lb
= wi::zero (prec
);
3269 if (wi::gts_p (tmp
, 0))
3270 tmp
= wi::zero (prec
);
3271 new_lb
= wi::smax (new_lb
, tmp
);
3274 if (sign
== SIGNED
&& wi::neg_p (tmp
))
3275 tmp
= wi::zero (prec
);
3276 new_ub
= wi::min (new_ub
, tmp
, sign
);
3278 value_range_with_overflow (r
, type
, new_lb
, new_ub
);
3282 operator_trunc_mod::op1_range (irange
&r
, tree type
,
3285 relation_kind rel ATTRIBUTE_UNUSED
) const
3288 signop sign
= TYPE_SIGN (type
);
3289 unsigned prec
= TYPE_PRECISION (type
);
3290 // (a % b) >= x && x > 0 , then a >= x.
3291 if (wi::gt_p (lhs
.lower_bound (), 0, sign
))
3293 r
= value_range (type
, lhs
.lower_bound (), wi::max_value (prec
, sign
));
3296 // (a % b) <= x && x < 0 , then a <= x.
3297 if (wi::lt_p (lhs
.upper_bound (), 0, sign
))
3299 r
= value_range (type
, wi::min_value (prec
, sign
), lhs
.upper_bound ());
3306 operator_trunc_mod::op2_range (irange
&r
, tree type
,
3309 relation_kind rel ATTRIBUTE_UNUSED
) const
3312 signop sign
= TYPE_SIGN (type
);
3313 unsigned prec
= TYPE_PRECISION (type
);
3314 // (a % b) >= x && x > 0 , then b is in ~[-x, x] for signed
3315 // or b > x for unsigned.
3316 if (wi::gt_p (lhs
.lower_bound (), 0, sign
))
3319 r
= value_range (type
, wi::neg (lhs
.lower_bound ()),
3320 lhs
.lower_bound (), VR_ANTI_RANGE
);
3321 else if (wi::lt_p (lhs
.lower_bound (), wi::max_value (prec
, sign
),
3323 r
= value_range (type
, lhs
.lower_bound () + 1,
3324 wi::max_value (prec
, sign
));
3329 // (a % b) <= x && x < 0 , then b is in ~[x, -x].
3330 if (wi::lt_p (lhs
.upper_bound (), 0, sign
))
3332 if (wi::gt_p (lhs
.upper_bound (), wi::min_value (prec
, sign
), sign
))
3333 r
= value_range (type
, lhs
.upper_bound (),
3334 wi::neg (lhs
.upper_bound ()), VR_ANTI_RANGE
);
3343 class operator_logical_not
: public range_operator
3346 virtual bool fold_range (irange
&r
, tree type
,
3349 relation_kind rel
= VREL_NONE
) const;
3350 virtual bool op1_range (irange
&r
, tree type
,
3353 relation_kind rel
= VREL_NONE
) const;
3356 // Folding a logical NOT, oddly enough, involves doing nothing on the
3357 // forward pass through. During the initial walk backwards, the
3358 // logical NOT reversed the desired outcome on the way back, so on the
3359 // way forward all we do is pass the range forward.
3364 // to determine the TRUE branch, walking backward
3365 // if (b_3) if ([1,1])
3366 // b_3 = !b_2 [1,1] = ![0,0]
3367 // b_2 = x_1 < 20 [0,0] = x_1 < 20, false, so x_1 == [20, 255]
3368 // which is the result we are looking for.. so.. pass it through.
3371 operator_logical_not::fold_range (irange
&r
, tree type
,
3373 const irange
&rh ATTRIBUTE_UNUSED
,
3374 relation_kind rel ATTRIBUTE_UNUSED
) const
3376 if (empty_range_varying (r
, type
, lh
, rh
))
3380 if (!lh
.varying_p () && !lh
.undefined_p ())
3387 operator_logical_not::op1_range (irange
&r
,
3391 relation_kind rel ATTRIBUTE_UNUSED
) const
3393 // Logical NOT is involutary...do it again.
3394 return fold_range (r
, type
, lhs
, op2
);
3398 class operator_bitwise_not
: public range_operator
3401 virtual bool fold_range (irange
&r
, tree type
,
3404 relation_kind rel
= VREL_NONE
) const;
3405 virtual bool op1_range (irange
&r
, tree type
,
3408 relation_kind rel
= VREL_NONE
) const;
3412 operator_bitwise_not::fold_range (irange
&r
, tree type
,
3415 relation_kind rel ATTRIBUTE_UNUSED
) const
3417 if (empty_range_varying (r
, type
, lh
, rh
))
3420 if (types_compatible_p (type
, boolean_type_node
))
3421 return op_logical_not
.fold_range (r
, type
, lh
, rh
);
3423 // ~X is simply -1 - X.
3424 int_range
<1> minusone (type
, wi::minus_one (TYPE_PRECISION (type
)),
3425 wi::minus_one (TYPE_PRECISION (type
)));
3426 return range_op_handler (MINUS_EXPR
, type
)->fold_range (r
, type
, minusone
,
3431 operator_bitwise_not::op1_range (irange
&r
, tree type
,
3434 relation_kind rel ATTRIBUTE_UNUSED
) const
3436 if (types_compatible_p (type
, boolean_type_node
))
3437 return op_logical_not
.op1_range (r
, type
, lhs
, op2
);
3439 // ~X is -1 - X and since bitwise NOT is involutary...do it again.
3440 return fold_range (r
, type
, lhs
, op2
);
3444 class operator_cst
: public range_operator
3447 virtual bool fold_range (irange
&r
, tree type
,
3450 relation_kind rel
= VREL_NONE
) const;
3454 operator_cst::fold_range (irange
&r
, tree type ATTRIBUTE_UNUSED
,
3456 const irange
&rh ATTRIBUTE_UNUSED
,
3457 relation_kind rel ATTRIBUTE_UNUSED
) const
3464 class operator_identity
: public range_operator
3467 virtual bool fold_range (irange
&r
, tree type
,
3470 relation_kind rel
= VREL_NONE
) const;
3471 virtual bool op1_range (irange
&r
, tree type
,
3474 relation_kind rel
= VREL_NONE
) const;
3475 virtual enum tree_code
lhs_op1_relation (const irange
&lhs
,
3477 const irange
&op2
) const;
3480 // Determine if there is a relationship between LHS and OP1.
3483 operator_identity::lhs_op1_relation (const irange
&lhs
,
3484 const irange
&op1 ATTRIBUTE_UNUSED
,
3485 const irange
&op2 ATTRIBUTE_UNUSED
) const
3487 if (lhs
.undefined_p ())
3489 // Simply a copy, so they are equivalent.
3494 operator_identity::fold_range (irange
&r
, tree type ATTRIBUTE_UNUSED
,
3496 const irange
&rh ATTRIBUTE_UNUSED
,
3497 relation_kind rel ATTRIBUTE_UNUSED
) const
3504 operator_identity::op1_range (irange
&r
, tree type ATTRIBUTE_UNUSED
,
3506 const irange
&op2 ATTRIBUTE_UNUSED
,
3507 relation_kind rel ATTRIBUTE_UNUSED
) const
3514 class operator_unknown
: public range_operator
3517 virtual bool fold_range (irange
&r
, tree type
,
3520 relation_kind rel
= VREL_NONE
) const;
3524 operator_unknown::fold_range (irange
&r
, tree type
,
3525 const irange
&lh ATTRIBUTE_UNUSED
,
3526 const irange
&rh ATTRIBUTE_UNUSED
,
3527 relation_kind rel ATTRIBUTE_UNUSED
) const
3529 r
.set_varying (type
);
3534 class operator_abs
: public range_operator
3537 virtual void wi_fold (irange
&r
, tree type
,
3538 const wide_int
&lh_lb
,
3539 const wide_int
&lh_ub
,
3540 const wide_int
&rh_lb
,
3541 const wide_int
&rh_ub
) const;
3542 virtual bool op1_range (irange
&r
, tree type
,
3545 relation_kind rel ATTRIBUTE_UNUSED
) const;
3549 operator_abs::wi_fold (irange
&r
, tree type
,
3550 const wide_int
&lh_lb
, const wide_int
&lh_ub
,
3551 const wide_int
&rh_lb ATTRIBUTE_UNUSED
,
3552 const wide_int
&rh_ub ATTRIBUTE_UNUSED
) const
3555 signop sign
= TYPE_SIGN (type
);
3556 unsigned prec
= TYPE_PRECISION (type
);
3558 // Pass through LH for the easy cases.
3559 if (sign
== UNSIGNED
|| wi::ge_p (lh_lb
, 0, sign
))
3561 r
= int_range
<1> (type
, lh_lb
, lh_ub
);
3565 // -TYPE_MIN_VALUE = TYPE_MIN_VALUE with flag_wrapv so we can't get
3567 wide_int min_value
= wi::min_value (prec
, sign
);
3568 wide_int max_value
= wi::max_value (prec
, sign
);
3569 if (!TYPE_OVERFLOW_UNDEFINED (type
) && wi::eq_p (lh_lb
, min_value
))
3571 r
.set_varying (type
);
3575 // ABS_EXPR may flip the range around, if the original range
3576 // included negative values.
3577 if (wi::eq_p (lh_lb
, min_value
))
3579 // ABS ([-MIN, -MIN]) isn't representable, but we have traditionally
3580 // returned [-MIN,-MIN] so this preserves that behaviour. PR37078
3581 if (wi::eq_p (lh_ub
, min_value
))
3583 r
= int_range
<1> (type
, min_value
, min_value
);
3589 min
= wi::abs (lh_lb
);
3591 if (wi::eq_p (lh_ub
, min_value
))
3594 max
= wi::abs (lh_ub
);
3596 // If the range contains zero then we know that the minimum value in the
3597 // range will be zero.
3598 if (wi::le_p (lh_lb
, 0, sign
) && wi::ge_p (lh_ub
, 0, sign
))
3600 if (wi::gt_p (min
, max
, sign
))
3602 min
= wi::zero (prec
);
3606 // If the range was reversed, swap MIN and MAX.
3607 if (wi::gt_p (min
, max
, sign
))
3608 std::swap (min
, max
);
3611 // If the new range has its limits swapped around (MIN > MAX), then
3612 // the operation caused one of them to wrap around. The only thing
3613 // we know is that the result is positive.
3614 if (wi::gt_p (min
, max
, sign
))
3616 min
= wi::zero (prec
);
3619 r
= int_range
<1> (type
, min
, max
);
3623 operator_abs::op1_range (irange
&r
, tree type
,
3626 relation_kind rel ATTRIBUTE_UNUSED
) const
3628 if (empty_range_varying (r
, type
, lhs
, op2
))
3630 if (TYPE_UNSIGNED (type
))
3635 // Start with the positives because negatives are an impossible result.
3636 int_range_max positives
= range_positives (type
);
3637 positives
.intersect (lhs
);
3639 // Then add the negative of each pair:
3640 // ABS(op1) = [5,20] would yield op1 => [-20,-5][5,20].
3641 for (unsigned i
= 0; i
< positives
.num_pairs (); ++i
)
3642 r
.union_ (int_range
<1> (type
,
3643 -positives
.upper_bound (i
),
3644 -positives
.lower_bound (i
)));
3645 // With flag_wrapv, -TYPE_MIN_VALUE = TYPE_MIN_VALUE which is
3646 // unrepresentable. Add -TYPE_MIN_VALUE in this case.
3647 wide_int min_value
= wi::min_value (TYPE_PRECISION (type
), TYPE_SIGN (type
));
3648 wide_int lb
= lhs
.lower_bound ();
3649 if (!TYPE_OVERFLOW_UNDEFINED (type
) && wi::eq_p (lb
, min_value
))
3650 r
.union_ (int_range
<2> (type
, lb
, lb
));
3655 class operator_absu
: public range_operator
3658 virtual void wi_fold (irange
&r
, tree type
,
3659 const wide_int
&lh_lb
, const wide_int
&lh_ub
,
3660 const wide_int
&rh_lb
, const wide_int
&rh_ub
) const;
3664 operator_absu::wi_fold (irange
&r
, tree type
,
3665 const wide_int
&lh_lb
, const wide_int
&lh_ub
,
3666 const wide_int
&rh_lb ATTRIBUTE_UNUSED
,
3667 const wide_int
&rh_ub ATTRIBUTE_UNUSED
) const
3669 wide_int new_lb
, new_ub
;
3671 // Pass through VR0 the easy cases.
3672 if (wi::ges_p (lh_lb
, 0))
3679 new_lb
= wi::abs (lh_lb
);
3680 new_ub
= wi::abs (lh_ub
);
3682 // If the range contains zero then we know that the minimum
3683 // value in the range will be zero.
3684 if (wi::ges_p (lh_ub
, 0))
3686 if (wi::gtu_p (new_lb
, new_ub
))
3688 new_lb
= wi::zero (TYPE_PRECISION (type
));
3691 std::swap (new_lb
, new_ub
);
3694 gcc_checking_assert (TYPE_UNSIGNED (type
));
3695 r
= int_range
<1> (type
, new_lb
, new_ub
);
3699 class operator_negate
: public range_operator
3702 virtual bool fold_range (irange
&r
, tree type
,
3705 relation_kind rel
= VREL_NONE
) const;
3706 virtual bool op1_range (irange
&r
, tree type
,
3709 relation_kind rel
= VREL_NONE
) const;
3713 operator_negate::fold_range (irange
&r
, tree type
,
3716 relation_kind rel ATTRIBUTE_UNUSED
) const
3718 if (empty_range_varying (r
, type
, lh
, rh
))
3720 // -X is simply 0 - X.
3721 return range_op_handler (MINUS_EXPR
, type
)->fold_range (r
, type
,
3727 operator_negate::op1_range (irange
&r
, tree type
,
3730 relation_kind rel ATTRIBUTE_UNUSED
) const
3732 // NEGATE is involutory.
3733 return fold_range (r
, type
, lhs
, op2
);
3737 class operator_addr_expr
: public range_operator
3740 virtual bool fold_range (irange
&r
, tree type
,
3743 relation_kind rel
= VREL_NONE
) const;
3744 virtual bool op1_range (irange
&r
, tree type
,
3747 relation_kind rel
= VREL_NONE
) const;
3751 operator_addr_expr::fold_range (irange
&r
, tree type
,
3754 relation_kind rel ATTRIBUTE_UNUSED
) const
3756 if (empty_range_varying (r
, type
, lh
, rh
))
3759 // Return a non-null pointer of the LHS type (passed in op2).
3761 r
= range_zero (type
);
3762 else if (!lh
.contains_p (build_zero_cst (lh
.type ())))
3763 r
= range_nonzero (type
);
3765 r
.set_varying (type
);
3770 operator_addr_expr::op1_range (irange
&r
, tree type
,
3773 relation_kind rel ATTRIBUTE_UNUSED
) const
3775 return operator_addr_expr::fold_range (r
, type
, lhs
, op2
);
3779 class pointer_plus_operator
: public range_operator
3782 virtual void wi_fold (irange
&r
, tree type
,
3783 const wide_int
&lh_lb
,
3784 const wide_int
&lh_ub
,
3785 const wide_int
&rh_lb
,
3786 const wide_int
&rh_ub
) const;
3790 pointer_plus_operator::wi_fold (irange
&r
, tree type
,
3791 const wide_int
&lh_lb
,
3792 const wide_int
&lh_ub
,
3793 const wide_int
&rh_lb
,
3794 const wide_int
&rh_ub
) const
3796 // Check for [0,0] + const, and simply return the const.
3797 if (lh_lb
== 0 && lh_ub
== 0 && rh_lb
== rh_ub
)
3799 tree val
= wide_int_to_tree (type
, rh_lb
);
3804 // For pointer types, we are really only interested in asserting
3805 // whether the expression evaluates to non-NULL.
3807 // With -fno-delete-null-pointer-checks we need to be more
3808 // conservative. As some object might reside at address 0,
3809 // then some offset could be added to it and the same offset
3810 // subtracted again and the result would be NULL.
3812 // static int a[12]; where &a[0] is NULL and
3815 // ptr will be NULL here, even when there is POINTER_PLUS_EXPR
3816 // where the first range doesn't include zero and the second one
3817 // doesn't either. As the second operand is sizetype (unsigned),
3818 // consider all ranges where the MSB could be set as possible
3819 // subtractions where the result might be NULL.
3820 if ((!wi_includes_zero_p (type
, lh_lb
, lh_ub
)
3821 || !wi_includes_zero_p (type
, rh_lb
, rh_ub
))
3822 && !TYPE_OVERFLOW_WRAPS (type
)
3823 && (flag_delete_null_pointer_checks
3824 || !wi::sign_mask (rh_ub
)))
3825 r
= range_nonzero (type
);
3826 else if (lh_lb
== lh_ub
&& lh_lb
== 0
3827 && rh_lb
== rh_ub
&& rh_lb
== 0)
3828 r
= range_zero (type
);
3830 r
.set_varying (type
);
3834 class pointer_min_max_operator
: public range_operator
3837 virtual void wi_fold (irange
& r
, tree type
,
3838 const wide_int
&lh_lb
, const wide_int
&lh_ub
,
3839 const wide_int
&rh_lb
, const wide_int
&rh_ub
) const;
3843 pointer_min_max_operator::wi_fold (irange
&r
, tree type
,
3844 const wide_int
&lh_lb
,
3845 const wide_int
&lh_ub
,
3846 const wide_int
&rh_lb
,
3847 const wide_int
&rh_ub
) const
3849 // For MIN/MAX expressions with pointers, we only care about
3850 // nullness. If both are non null, then the result is nonnull.
3851 // If both are null, then the result is null. Otherwise they
3853 if (!wi_includes_zero_p (type
, lh_lb
, lh_ub
)
3854 && !wi_includes_zero_p (type
, rh_lb
, rh_ub
))
3855 r
= range_nonzero (type
);
3856 else if (wi_zero_p (type
, lh_lb
, lh_ub
) && wi_zero_p (type
, rh_lb
, rh_ub
))
3857 r
= range_zero (type
);
3859 r
.set_varying (type
);
3863 class pointer_and_operator
: public range_operator
3866 virtual void wi_fold (irange
&r
, tree type
,
3867 const wide_int
&lh_lb
, const wide_int
&lh_ub
,
3868 const wide_int
&rh_lb
, const wide_int
&rh_ub
) const;
3872 pointer_and_operator::wi_fold (irange
&r
, tree type
,
3873 const wide_int
&lh_lb
,
3874 const wide_int
&lh_ub
,
3875 const wide_int
&rh_lb ATTRIBUTE_UNUSED
,
3876 const wide_int
&rh_ub ATTRIBUTE_UNUSED
) const
3878 // For pointer types, we are really only interested in asserting
3879 // whether the expression evaluates to non-NULL.
3880 if (wi_zero_p (type
, lh_lb
, lh_ub
) || wi_zero_p (type
, lh_lb
, lh_ub
))
3881 r
= range_zero (type
);
3883 r
.set_varying (type
);
3887 class pointer_or_operator
: public range_operator
3890 virtual bool op1_range (irange
&r
, tree type
,
3893 relation_kind rel
= VREL_NONE
) const;
3894 virtual bool op2_range (irange
&r
, tree type
,
3897 relation_kind rel
= VREL_NONE
) const;
3898 virtual void wi_fold (irange
&r
, tree type
,
3899 const wide_int
&lh_lb
, const wide_int
&lh_ub
,
3900 const wide_int
&rh_lb
, const wide_int
&rh_ub
) const;
3904 pointer_or_operator::op1_range (irange
&r
, tree type
,
3906 const irange
&op2 ATTRIBUTE_UNUSED
,
3907 relation_kind rel ATTRIBUTE_UNUSED
) const
3911 tree zero
= build_zero_cst (type
);
3912 r
= int_range
<1> (zero
, zero
);
3915 r
.set_varying (type
);
3920 pointer_or_operator::op2_range (irange
&r
, tree type
,
3923 relation_kind rel ATTRIBUTE_UNUSED
) const
3925 return pointer_or_operator::op1_range (r
, type
, lhs
, op1
);
3929 pointer_or_operator::wi_fold (irange
&r
, tree type
,
3930 const wide_int
&lh_lb
,
3931 const wide_int
&lh_ub
,
3932 const wide_int
&rh_lb
,
3933 const wide_int
&rh_ub
) const
3935 // For pointer types, we are really only interested in asserting
3936 // whether the expression evaluates to non-NULL.
3937 if (!wi_includes_zero_p (type
, lh_lb
, lh_ub
)
3938 && !wi_includes_zero_p (type
, rh_lb
, rh_ub
))
3939 r
= range_nonzero (type
);
3940 else if (wi_zero_p (type
, lh_lb
, lh_ub
) && wi_zero_p (type
, rh_lb
, rh_ub
))
3941 r
= range_zero (type
);
3943 r
.set_varying (type
);
3946 // This implements the range operator tables as local objects in this file.
3948 class range_op_table
3951 inline range_operator
*operator[] (enum tree_code code
);
3953 void set (enum tree_code code
, range_operator
&op
);
3955 range_operator
*m_range_tree
[MAX_TREE_CODES
];
3958 // Return a pointer to the range_operator instance, if there is one
3959 // associated with tree_code CODE.
3962 range_op_table::operator[] (enum tree_code code
)
3964 gcc_checking_assert (code
> 0 && code
< MAX_TREE_CODES
);
3965 return m_range_tree
[code
];
3968 // Add OP to the handler table for CODE.
3971 range_op_table::set (enum tree_code code
, range_operator
&op
)
3973 gcc_checking_assert (m_range_tree
[code
] == NULL
);
3974 m_range_tree
[code
] = &op
;
3977 // Instantiate a range op table for integral operations.
3979 class integral_table
: public range_op_table
3983 } integral_tree_table
;
3985 integral_table::integral_table ()
3987 set (EQ_EXPR
, op_equal
);
3988 set (NE_EXPR
, op_not_equal
);
3989 set (LT_EXPR
, op_lt
);
3990 set (LE_EXPR
, op_le
);
3991 set (GT_EXPR
, op_gt
);
3992 set (GE_EXPR
, op_ge
);
3993 set (PLUS_EXPR
, op_plus
);
3994 set (MINUS_EXPR
, op_minus
);
3995 set (MIN_EXPR
, op_min
);
3996 set (MAX_EXPR
, op_max
);
3997 set (MULT_EXPR
, op_mult
);
3998 set (TRUNC_DIV_EXPR
, op_trunc_div
);
3999 set (FLOOR_DIV_EXPR
, op_floor_div
);
4000 set (ROUND_DIV_EXPR
, op_round_div
);
4001 set (CEIL_DIV_EXPR
, op_ceil_div
);
4002 set (EXACT_DIV_EXPR
, op_exact_div
);
4003 set (LSHIFT_EXPR
, op_lshift
);
4004 set (RSHIFT_EXPR
, op_rshift
);
4005 set (NOP_EXPR
, op_convert
);
4006 set (CONVERT_EXPR
, op_convert
);
4007 set (TRUTH_AND_EXPR
, op_logical_and
);
4008 set (BIT_AND_EXPR
, op_bitwise_and
);
4009 set (TRUTH_OR_EXPR
, op_logical_or
);
4010 set (BIT_IOR_EXPR
, op_bitwise_or
);
4011 set (BIT_XOR_EXPR
, op_bitwise_xor
);
4012 set (TRUNC_MOD_EXPR
, op_trunc_mod
);
4013 set (TRUTH_NOT_EXPR
, op_logical_not
);
4014 set (BIT_NOT_EXPR
, op_bitwise_not
);
4015 set (INTEGER_CST
, op_integer_cst
);
4016 set (SSA_NAME
, op_identity
);
4017 set (PAREN_EXPR
, op_identity
);
4018 set (OBJ_TYPE_REF
, op_identity
);
4019 set (IMAGPART_EXPR
, op_unknown
);
4020 set (POINTER_DIFF_EXPR
, op_unknown
);
4021 set (ABS_EXPR
, op_abs
);
4022 set (ABSU_EXPR
, op_absu
);
4023 set (NEGATE_EXPR
, op_negate
);
4024 set (ADDR_EXPR
, op_addr
);
4027 // Instantiate a range op table for pointer operations.
4029 class pointer_table
: public range_op_table
4033 } pointer_tree_table
;
4035 pointer_table::pointer_table ()
4037 set (BIT_AND_EXPR
, op_pointer_and
);
4038 set (BIT_IOR_EXPR
, op_pointer_or
);
4039 set (MIN_EXPR
, op_ptr_min_max
);
4040 set (MAX_EXPR
, op_ptr_min_max
);
4041 set (POINTER_PLUS_EXPR
, op_pointer_plus
);
4043 set (EQ_EXPR
, op_equal
);
4044 set (NE_EXPR
, op_not_equal
);
4045 set (LT_EXPR
, op_lt
);
4046 set (LE_EXPR
, op_le
);
4047 set (GT_EXPR
, op_gt
);
4048 set (GE_EXPR
, op_ge
);
4049 set (SSA_NAME
, op_identity
);
4050 set (INTEGER_CST
, op_integer_cst
);
4051 set (ADDR_EXPR
, op_addr
);
4052 set (NOP_EXPR
, op_convert
);
4053 set (CONVERT_EXPR
, op_convert
);
4055 set (BIT_NOT_EXPR
, op_bitwise_not
);
4056 set (BIT_XOR_EXPR
, op_bitwise_xor
);
4059 // The tables are hidden and accessed via a simple extern function.
4062 range_op_handler (enum tree_code code
, tree type
)
4064 // First check if there is a pointer specialization.
4065 if (POINTER_TYPE_P (type
))
4066 return pointer_tree_table
[code
];
4067 if (INTEGRAL_TYPE_P (type
))
4068 return integral_tree_table
[code
];
4072 // Cast the range in R to TYPE.
4075 range_cast (irange
&r
, tree type
)
4077 int_range_max tmp
= r
;
4078 range_operator
*op
= range_op_handler (CONVERT_EXPR
, type
);
4079 // Call op_convert, if it fails, the result is varying.
4080 if (!op
->fold_range (r
, type
, tmp
, int_range
<1> (type
)))
4081 r
.set_varying (type
);
4085 #include "selftest.h"
4089 #define INT(N) build_int_cst (integer_type_node, (N))
4090 #define UINT(N) build_int_cstu (unsigned_type_node, (N))
4091 #define INT16(N) build_int_cst (short_integer_type_node, (N))
4092 #define UINT16(N) build_int_cstu (short_unsigned_type_node, (N))
4093 #define SCHAR(N) build_int_cst (signed_char_type_node, (N))
4094 #define UCHAR(N) build_int_cstu (unsigned_char_type_node, (N))
4097 range_op_cast_tests ()
4099 int_range
<1> r0
, r1
, r2
, rold
;
4100 r0
.set_varying (integer_type_node
);
4101 tree maxint
= wide_int_to_tree (integer_type_node
, r0
.upper_bound ());
4103 // If a range is in any way outside of the range for the converted
4104 // to range, default to the range for the new type.
4105 r0
.set_varying (short_integer_type_node
);
4106 tree minshort
= wide_int_to_tree (short_integer_type_node
, r0
.lower_bound ());
4107 tree maxshort
= wide_int_to_tree (short_integer_type_node
, r0
.upper_bound ());
4108 if (TYPE_PRECISION (TREE_TYPE (maxint
))
4109 > TYPE_PRECISION (short_integer_type_node
))
4111 r1
= int_range
<1> (integer_zero_node
, maxint
);
4112 range_cast (r1
, short_integer_type_node
);
4113 ASSERT_TRUE (r1
.lower_bound () == wi::to_wide (minshort
)
4114 && r1
.upper_bound() == wi::to_wide (maxshort
));
4117 // (unsigned char)[-5,-1] => [251,255].
4118 r0
= rold
= int_range
<1> (SCHAR (-5), SCHAR (-1));
4119 range_cast (r0
, unsigned_char_type_node
);
4120 ASSERT_TRUE (r0
== int_range
<1> (UCHAR (251), UCHAR (255)));
4121 range_cast (r0
, signed_char_type_node
);
4122 ASSERT_TRUE (r0
== rold
);
4124 // (signed char)[15, 150] => [-128,-106][15,127].
4125 r0
= rold
= int_range
<1> (UCHAR (15), UCHAR (150));
4126 range_cast (r0
, signed_char_type_node
);
4127 r1
= int_range
<1> (SCHAR (15), SCHAR (127));
4128 r2
= int_range
<1> (SCHAR (-128), SCHAR (-106));
4130 ASSERT_TRUE (r1
== r0
);
4131 range_cast (r0
, unsigned_char_type_node
);
4132 ASSERT_TRUE (r0
== rold
);
4134 // (unsigned char)[-5, 5] => [0,5][251,255].
4135 r0
= rold
= int_range
<1> (SCHAR (-5), SCHAR (5));
4136 range_cast (r0
, unsigned_char_type_node
);
4137 r1
= int_range
<1> (UCHAR (251), UCHAR (255));
4138 r2
= int_range
<1> (UCHAR (0), UCHAR (5));
4140 ASSERT_TRUE (r0
== r1
);
4141 range_cast (r0
, signed_char_type_node
);
4142 ASSERT_TRUE (r0
== rold
);
4144 // (unsigned char)[-5,5] => [0,5][251,255].
4145 r0
= int_range
<1> (INT (-5), INT (5));
4146 range_cast (r0
, unsigned_char_type_node
);
4147 r1
= int_range
<1> (UCHAR (0), UCHAR (5));
4148 r1
.union_ (int_range
<1> (UCHAR (251), UCHAR (255)));
4149 ASSERT_TRUE (r0
== r1
);
4151 // (unsigned char)[5U,1974U] => [0,255].
4152 r0
= int_range
<1> (UINT (5), UINT (1974));
4153 range_cast (r0
, unsigned_char_type_node
);
4154 ASSERT_TRUE (r0
== int_range
<1> (UCHAR (0), UCHAR (255)));
4155 range_cast (r0
, integer_type_node
);
4156 // Going to a wider range should not sign extend.
4157 ASSERT_TRUE (r0
== int_range
<1> (INT (0), INT (255)));
4159 // (unsigned char)[-350,15] => [0,255].
4160 r0
= int_range
<1> (INT (-350), INT (15));
4161 range_cast (r0
, unsigned_char_type_node
);
4162 ASSERT_TRUE (r0
== (int_range
<1>
4163 (TYPE_MIN_VALUE (unsigned_char_type_node
),
4164 TYPE_MAX_VALUE (unsigned_char_type_node
))));
4166 // Casting [-120,20] from signed char to unsigned short.
4167 // => [0, 20][0xff88, 0xffff].
4168 r0
= int_range
<1> (SCHAR (-120), SCHAR (20));
4169 range_cast (r0
, short_unsigned_type_node
);
4170 r1
= int_range
<1> (UINT16 (0), UINT16 (20));
4171 r2
= int_range
<1> (UINT16 (0xff88), UINT16 (0xffff));
4173 ASSERT_TRUE (r0
== r1
);
4174 // A truncating cast back to signed char will work because [-120, 20]
4175 // is representable in signed char.
4176 range_cast (r0
, signed_char_type_node
);
4177 ASSERT_TRUE (r0
== int_range
<1> (SCHAR (-120), SCHAR (20)));
4179 // unsigned char -> signed short
4180 // (signed short)[(unsigned char)25, (unsigned char)250]
4181 // => [(signed short)25, (signed short)250]
4182 r0
= rold
= int_range
<1> (UCHAR (25), UCHAR (250));
4183 range_cast (r0
, short_integer_type_node
);
4184 r1
= int_range
<1> (INT16 (25), INT16 (250));
4185 ASSERT_TRUE (r0
== r1
);
4186 range_cast (r0
, unsigned_char_type_node
);
4187 ASSERT_TRUE (r0
== rold
);
4189 // Test casting a wider signed [-MIN,MAX] to a nar`rower unsigned.
4190 r0
= int_range
<1> (TYPE_MIN_VALUE (long_long_integer_type_node
),
4191 TYPE_MAX_VALUE (long_long_integer_type_node
));
4192 range_cast (r0
, short_unsigned_type_node
);
4193 r1
= int_range
<1> (TYPE_MIN_VALUE (short_unsigned_type_node
),
4194 TYPE_MAX_VALUE (short_unsigned_type_node
));
4195 ASSERT_TRUE (r0
== r1
);
4197 // Casting NONZERO to a narrower type will wrap/overflow so
4198 // it's just the entire range for the narrower type.
4200 // "NOT 0 at signed 32-bits" ==> [-MIN_32,-1][1, +MAX_32]. This is
4201 // is outside of the range of a smaller range, return the full
4203 if (TYPE_PRECISION (integer_type_node
)
4204 > TYPE_PRECISION (short_integer_type_node
))
4206 r0
= range_nonzero (integer_type_node
);
4207 range_cast (r0
, short_integer_type_node
);
4208 r1
= int_range
<1> (TYPE_MIN_VALUE (short_integer_type_node
),
4209 TYPE_MAX_VALUE (short_integer_type_node
));
4210 ASSERT_TRUE (r0
== r1
);
4213 // Casting NONZERO from a narrower signed to a wider signed.
4215 // NONZERO signed 16-bits is [-MIN_16,-1][1, +MAX_16].
4216 // Converting this to 32-bits signed is [-MIN_16,-1][1, +MAX_16].
4217 r0
= range_nonzero (short_integer_type_node
);
4218 range_cast (r0
, integer_type_node
);
4219 r1
= int_range
<1> (INT (-32768), INT (-1));
4220 r2
= int_range
<1> (INT (1), INT (32767));
4222 ASSERT_TRUE (r0
== r1
);
4226 range_op_lshift_tests ()
4228 // Test that 0x808.... & 0x8.... still contains 0x8....
4229 // for a large set of numbers.
4232 tree big_type
= long_long_unsigned_type_node
;
4233 // big_num = 0x808,0000,0000,0000
4234 tree big_num
= fold_build2 (LSHIFT_EXPR
, big_type
,
4235 build_int_cst (big_type
, 0x808),
4236 build_int_cst (big_type
, 48));
4237 op_bitwise_and
.fold_range (res
, big_type
,
4238 int_range
<1> (big_type
),
4239 int_range
<1> (big_num
, big_num
));
4240 // val = 0x8,0000,0000,0000
4241 tree val
= fold_build2 (LSHIFT_EXPR
, big_type
,
4242 build_int_cst (big_type
, 0x8),
4243 build_int_cst (big_type
, 48));
4244 ASSERT_TRUE (res
.contains_p (val
));
4247 if (TYPE_PRECISION (unsigned_type_node
) > 31)
4249 // unsigned VARYING = op1 << 1 should be VARYING.
4250 int_range
<2> lhs (unsigned_type_node
);
4251 int_range
<2> shift (INT (1), INT (1));
4253 op_lshift
.op1_range (op1
, unsigned_type_node
, lhs
, shift
);
4254 ASSERT_TRUE (op1
.varying_p ());
4256 // 0 = op1 << 1 should be [0,0], [0x8000000, 0x8000000].
4257 int_range
<2> zero (UINT (0), UINT (0));
4258 op_lshift
.op1_range (op1
, unsigned_type_node
, zero
, shift
);
4259 ASSERT_TRUE (op1
.num_pairs () == 2);
4260 // Remove the [0,0] range.
4261 op1
.intersect (zero
);
4262 ASSERT_TRUE (op1
.num_pairs () == 1);
4263 // op1 << 1 should be [0x8000,0x8000] << 1,
4264 // which should result in [0,0].
4265 int_range_max result
;
4266 op_lshift
.fold_range (result
, unsigned_type_node
, op1
, shift
);
4267 ASSERT_TRUE (result
== zero
);
4269 // signed VARYING = op1 << 1 should be VARYING.
4270 if (TYPE_PRECISION (integer_type_node
) > 31)
4272 // unsigned VARYING = op1 << 1 hould be VARYING.
4273 int_range
<2> lhs (integer_type_node
);
4274 int_range
<2> shift (INT (1), INT (1));
4276 op_lshift
.op1_range (op1
, integer_type_node
, lhs
, shift
);
4277 ASSERT_TRUE (op1
.varying_p ());
4279 // 0 = op1 << 1 should be [0,0], [0x8000000, 0x8000000].
4280 int_range
<2> zero (INT (0), INT (0));
4281 op_lshift
.op1_range (op1
, integer_type_node
, zero
, shift
);
4282 ASSERT_TRUE (op1
.num_pairs () == 2);
4283 // Remove the [0,0] range.
4284 op1
.intersect (zero
);
4285 ASSERT_TRUE (op1
.num_pairs () == 1);
4286 // op1 << 1 shuould be [0x8000,0x8000] << 1,
4287 // which should result in [0,0].
4288 int_range_max result
;
4289 op_lshift
.fold_range (result
, unsigned_type_node
, op1
, shift
);
4290 ASSERT_TRUE (result
== zero
);
4295 range_op_rshift_tests ()
4297 // unsigned: [3, MAX] = OP1 >> 1
4299 int_range_max
lhs (build_int_cst (unsigned_type_node
, 3),
4300 TYPE_MAX_VALUE (unsigned_type_node
));
4301 int_range_max
one (build_one_cst (unsigned_type_node
),
4302 build_one_cst (unsigned_type_node
));
4304 op_rshift
.op1_range (op1
, unsigned_type_node
, lhs
, one
);
4305 ASSERT_FALSE (op1
.contains_p (UINT (3)));
4308 // signed: [3, MAX] = OP1 >> 1
4310 int_range_max
lhs (INT (3), TYPE_MAX_VALUE (integer_type_node
));
4311 int_range_max
one (INT (1), INT (1));
4313 op_rshift
.op1_range (op1
, integer_type_node
, lhs
, one
);
4314 ASSERT_FALSE (op1
.contains_p (INT (-2)));
4317 // This is impossible, so OP1 should be [].
4318 // signed: [MIN, MIN] = OP1 >> 1
4320 int_range_max
lhs (TYPE_MIN_VALUE (integer_type_node
),
4321 TYPE_MIN_VALUE (integer_type_node
));
4322 int_range_max
one (INT (1), INT (1));
4324 op_rshift
.op1_range (op1
, integer_type_node
, lhs
, one
);
4325 ASSERT_TRUE (op1
.undefined_p ());
4328 // signed: ~[-1] = OP1 >> 31
4329 if (TYPE_PRECISION (integer_type_node
) > 31)
4331 int_range_max
lhs (INT (-1), INT (-1), VR_ANTI_RANGE
);
4332 int_range_max
shift (INT (31), INT (31));
4334 op_rshift
.op1_range (op1
, integer_type_node
, lhs
, shift
);
4335 int_range_max negatives
= range_negatives (integer_type_node
);
4336 negatives
.intersect (op1
);
4337 ASSERT_TRUE (negatives
.undefined_p ());
4342 range_op_bitwise_and_tests ()
4345 tree min
= vrp_val_min (integer_type_node
);
4346 tree max
= vrp_val_max (integer_type_node
);
4347 tree tiny
= fold_build2 (PLUS_EXPR
, integer_type_node
, min
,
4348 build_one_cst (integer_type_node
));
4349 int_range_max
i1 (tiny
, max
);
4350 int_range_max
i2 (build_int_cst (integer_type_node
, 255),
4351 build_int_cst (integer_type_node
, 255));
4353 // [MIN+1, MAX] = OP1 & 255: OP1 is VARYING
4354 op_bitwise_and
.op1_range (res
, integer_type_node
, i1
, i2
);
4355 ASSERT_TRUE (res
== int_range
<1> (integer_type_node
));
4357 // VARYING = OP1 & 255: OP1 is VARYING
4358 i1
= int_range
<1> (integer_type_node
);
4359 op_bitwise_and
.op1_range (res
, integer_type_node
, i1
, i2
);
4360 ASSERT_TRUE (res
== int_range
<1> (integer_type_node
));
4362 // (NONZERO | X) is nonzero.
4363 i1
.set_nonzero (integer_type_node
);
4364 i2
.set_varying (integer_type_node
);
4365 op_bitwise_or
.fold_range (res
, integer_type_node
, i1
, i2
);
4366 ASSERT_TRUE (res
.nonzero_p ());
4368 // (NEGATIVE | X) is nonzero.
4369 i1
= int_range
<1> (INT (-5), INT (-3));
4370 i2
.set_varying (integer_type_node
);
4371 op_bitwise_or
.fold_range (res
, integer_type_node
, i1
, i2
);
4372 ASSERT_FALSE (res
.contains_p (INT (0)));
4376 range_relational_tests ()
4378 int_range
<2> lhs (unsigned_char_type_node
);
4379 int_range
<2> op1 (UCHAR (8), UCHAR (10));
4380 int_range
<2> op2 (UCHAR (20), UCHAR (20));
4382 // Never wrapping additions mean LHS > OP1.
4383 tree_code code
= op_plus
.lhs_op1_relation (lhs
, op1
, op2
);
4384 ASSERT_TRUE (code
== GT_EXPR
);
4386 // Most wrapping additions mean nothing...
4387 op1
= int_range
<2> (UCHAR (8), UCHAR (10));
4388 op2
= int_range
<2> (UCHAR (0), UCHAR (255));
4389 code
= op_plus
.lhs_op1_relation (lhs
, op1
, op2
);
4390 ASSERT_TRUE (code
== VREL_NONE
);
4392 // However, always wrapping additions mean LHS < OP1.
4393 op1
= int_range
<2> (UCHAR (1), UCHAR (255));
4394 op2
= int_range
<2> (UCHAR (255), UCHAR (255));
4395 code
= op_plus
.lhs_op1_relation (lhs
, op1
, op2
);
4396 ASSERT_TRUE (code
== LT_EXPR
);
4402 range_op_rshift_tests ();
4403 range_op_lshift_tests ();
4404 range_op_bitwise_and_tests ();
4405 range_op_cast_tests ();
4406 range_relational_tests ();
4409 } // namespace selftest
4411 #endif // CHECKING_P