1 /* Code for range operators.
2 Copyright (C) 2017-2023 Free Software Foundation, Inc.
3 Contributed by Andrew MacLeod <amacleod@redhat.com>
4 and Aldy Hernandez <aldyh@redhat.com>.
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify
9 it under the terms of the GNU General Public License as published by
10 the Free Software Foundation; either version 3, or (at your option)
13 GCC is distributed in the hope that it will be useful,
14 but WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 GNU General Public License for more details.
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
24 #include "coretypes.h"
26 #include "insn-codes.h"
31 #include "tree-pass.h"
33 #include "optabs-tree.h"
34 #include "gimple-pretty-print.h"
35 #include "diagnostic-core.h"
37 #include "fold-const.h"
38 #include "stor-layout.h"
41 #include "gimple-iterator.h"
42 #include "gimple-fold.h"
44 #include "gimple-walk.h"
47 #include "value-relation.h"
49 #include "tree-ssa-ccp.h"
51 // Convert irange bitmasks into a VALUE MASK pair suitable for calling CCP.
54 irange_to_masked_value (const irange
&r
, widest_int
&value
, widest_int
&mask
)
59 value
= widest_int::from (r
.lower_bound (), TYPE_SIGN (r
.type ()));
63 mask
= widest_int::from (r
.get_nonzero_bits (), TYPE_SIGN (r
.type ()));
68 // Update the known bitmasks in R when applying the operation CODE to
72 update_known_bitmask (irange
&r
, tree_code code
,
73 const irange
&lh
, const irange
&rh
)
75 if (r
.undefined_p () || lh
.undefined_p () || rh
.undefined_p ())
78 widest_int value
, mask
, lh_mask
, rh_mask
, lh_value
, rh_value
;
79 tree type
= r
.type ();
80 signop sign
= TYPE_SIGN (type
);
81 int prec
= TYPE_PRECISION (type
);
82 signop lh_sign
= TYPE_SIGN (lh
.type ());
83 signop rh_sign
= TYPE_SIGN (rh
.type ());
84 int lh_prec
= TYPE_PRECISION (lh
.type ());
85 int rh_prec
= TYPE_PRECISION (rh
.type ());
87 irange_to_masked_value (lh
, lh_value
, lh_mask
);
88 irange_to_masked_value (rh
, rh_value
, rh_mask
);
89 bit_value_binop (code
, sign
, prec
, &value
, &mask
,
90 lh_sign
, lh_prec
, lh_value
, lh_mask
,
91 rh_sign
, rh_prec
, rh_value
, rh_mask
);
92 r
.set_nonzero_bits (value
| mask
);
95 // Return the upper limit for a type.
97 static inline wide_int
98 max_limit (const_tree type
)
100 return wi::max_value (TYPE_PRECISION (type
) , TYPE_SIGN (type
));
103 // Return the lower limit for a type.
105 static inline wide_int
106 min_limit (const_tree type
)
108 return wi::min_value (TYPE_PRECISION (type
) , TYPE_SIGN (type
));
111 // Return false if shifting by OP is undefined behavior. Otherwise, return
112 // true and the range it is to be shifted by. This allows trimming out of
113 // undefined ranges, leaving only valid ranges if there are any.
116 get_shift_range (irange
&r
, tree type
, const irange
&op
)
118 if (op
.undefined_p ())
121 // Build valid range and intersect it with the shift range.
122 r
= value_range (build_int_cst_type (op
.type (), 0),
123 build_int_cst_type (op
.type (), TYPE_PRECISION (type
) - 1));
126 // If there are no valid ranges in the shift range, returned false.
127 if (r
.undefined_p ())
132 // Return TRUE if 0 is within [WMIN, WMAX].
135 wi_includes_zero_p (tree type
, const wide_int
&wmin
, const wide_int
&wmax
)
137 signop sign
= TYPE_SIGN (type
);
138 return wi::le_p (wmin
, 0, sign
) && wi::ge_p (wmax
, 0, sign
);
141 // Return TRUE if [WMIN, WMAX] is the singleton 0.
144 wi_zero_p (tree type
, const wide_int
&wmin
, const wide_int
&wmax
)
146 unsigned prec
= TYPE_PRECISION (type
);
147 return wmin
== wmax
&& wi::eq_p (wmin
, wi::zero (prec
));
150 // Default wide_int fold operation returns [MIN, MAX].
153 range_operator::wi_fold (irange
&r
, tree type
,
154 const wide_int
&lh_lb ATTRIBUTE_UNUSED
,
155 const wide_int
&lh_ub ATTRIBUTE_UNUSED
,
156 const wide_int
&rh_lb ATTRIBUTE_UNUSED
,
157 const wide_int
&rh_ub ATTRIBUTE_UNUSED
) const
159 gcc_checking_assert (r
.supports_type_p (type
));
160 r
.set_varying (type
);
163 // Call wi_fold when both op1 and op2 are equivalent. Further split small
164 // subranges into constants. This can provide better precision.
165 // For x + y, when x == y with a range of [0,4] instead of [0, 8] produce
166 // [0,0][2, 2][4,4][6, 6][8, 8]
167 // LIMIT is the maximum number of elements in range allowed before we
168 // do not processs them individually.
171 range_operator::wi_fold_in_parts_equiv (irange
&r
, tree type
,
172 const wide_int
&lh_lb
,
173 const wide_int
&lh_ub
,
174 unsigned limit
) const
177 widest_int lh_range
= wi::sub (widest_int::from (lh_ub
, TYPE_SIGN (type
)),
178 widest_int::from (lh_lb
, TYPE_SIGN (type
)));
179 // if there are 1 to 8 values in the LH range, split them up.
181 if (lh_range
>= 0 && lh_range
< limit
)
183 for (unsigned x
= 0; x
<= lh_range
; x
++)
185 wide_int val
= lh_lb
+ x
;
186 wi_fold (tmp
, type
, val
, val
, val
, val
);
190 // Otherwise just call wi_fold.
192 wi_fold (r
, type
, lh_lb
, lh_ub
, lh_lb
, lh_ub
);
195 // Call wi_fold, except further split small subranges into constants.
196 // This can provide better precision. For something 8 >> [0,1]
197 // Instead of [8, 16], we will produce [8,8][16,16]
200 range_operator::wi_fold_in_parts (irange
&r
, tree type
,
201 const wide_int
&lh_lb
,
202 const wide_int
&lh_ub
,
203 const wide_int
&rh_lb
,
204 const wide_int
&rh_ub
) const
207 widest_int rh_range
= wi::sub (widest_int::from (rh_ub
, TYPE_SIGN (type
)),
208 widest_int::from (rh_lb
, TYPE_SIGN (type
)));
209 widest_int lh_range
= wi::sub (widest_int::from (lh_ub
, TYPE_SIGN (type
)),
210 widest_int::from (lh_lb
, TYPE_SIGN (type
)));
211 // If there are 2, 3, or 4 values in the RH range, do them separately.
212 // Call wi_fold_in_parts to check the RH side.
213 if (rh_range
> 0 && rh_range
< 4)
215 wi_fold_in_parts (r
, type
, lh_lb
, lh_ub
, rh_lb
, rh_lb
);
218 wi_fold_in_parts (tmp
, type
, lh_lb
, lh_ub
, rh_lb
+ 1, rh_lb
+ 1);
222 wi_fold_in_parts (tmp
, type
, lh_lb
, lh_ub
, rh_lb
+ 2, rh_lb
+ 2);
226 wi_fold_in_parts (tmp
, type
, lh_lb
, lh_ub
, rh_ub
, rh_ub
);
229 // Otherise check for 2, 3, or 4 values in the LH range and split them up.
230 // The RH side has been checked, so no recursion needed.
231 else if (lh_range
> 0 && lh_range
< 4)
233 wi_fold (r
, type
, lh_lb
, lh_lb
, rh_lb
, rh_ub
);
236 wi_fold (tmp
, type
, lh_lb
+ 1, lh_lb
+ 1, rh_lb
, rh_ub
);
240 wi_fold (tmp
, type
, lh_lb
+ 2, lh_lb
+ 2, rh_lb
, rh_ub
);
244 wi_fold (tmp
, type
, lh_ub
, lh_ub
, rh_lb
, rh_ub
);
247 // Otherwise just call wi_fold.
249 wi_fold (r
, type
, lh_lb
, lh_ub
, rh_lb
, rh_ub
);
252 // The default for fold is to break all ranges into sub-ranges and
253 // invoke the wi_fold method on each sub-range pair.
256 range_operator::fold_range (irange
&r
, tree type
,
259 relation_trio trio
) const
261 gcc_checking_assert (r
.supports_type_p (type
));
262 if (empty_range_varying (r
, type
, lh
, rh
))
265 relation_kind rel
= trio
.op1_op2 ();
266 unsigned num_lh
= lh
.num_pairs ();
267 unsigned num_rh
= rh
.num_pairs ();
269 // If op1 and op2 are equivalences, then we don't need a complete cross
270 // product, just pairs of matching elements.
271 if (relation_equiv_p (rel
) && lh
== rh
)
275 for (unsigned x
= 0; x
< num_lh
; ++x
)
277 // If the number of subranges is too high, limit subrange creation.
278 unsigned limit
= (r
.num_pairs () > 32) ? 0 : 8;
279 wide_int lh_lb
= lh
.lower_bound (x
);
280 wide_int lh_ub
= lh
.upper_bound (x
);
281 wi_fold_in_parts_equiv (tmp
, type
, lh_lb
, lh_ub
, limit
);
286 op1_op2_relation_effect (r
, type
, lh
, rh
, rel
);
287 update_known_bitmask (r
, m_code
, lh
, rh
);
291 // If both ranges are single pairs, fold directly into the result range.
292 // If the number of subranges grows too high, produce a summary result as the
293 // loop becomes exponential with little benefit. See PR 103821.
294 if ((num_lh
== 1 && num_rh
== 1) || num_lh
* num_rh
> 12)
296 wi_fold_in_parts (r
, type
, lh
.lower_bound (), lh
.upper_bound (),
297 rh
.lower_bound (), rh
.upper_bound ());
298 op1_op2_relation_effect (r
, type
, lh
, rh
, rel
);
299 update_known_bitmask (r
, m_code
, lh
, rh
);
305 for (unsigned x
= 0; x
< num_lh
; ++x
)
306 for (unsigned y
= 0; y
< num_rh
; ++y
)
308 wide_int lh_lb
= lh
.lower_bound (x
);
309 wide_int lh_ub
= lh
.upper_bound (x
);
310 wide_int rh_lb
= rh
.lower_bound (y
);
311 wide_int rh_ub
= rh
.upper_bound (y
);
312 wi_fold_in_parts (tmp
, type
, lh_lb
, lh_ub
, rh_lb
, rh_ub
);
316 op1_op2_relation_effect (r
, type
, lh
, rh
, rel
);
317 update_known_bitmask (r
, m_code
, lh
, rh
);
321 op1_op2_relation_effect (r
, type
, lh
, rh
, rel
);
322 update_known_bitmask (r
, m_code
, lh
, rh
);
326 // The default for op1_range is to return false.
329 range_operator::op1_range (irange
&r ATTRIBUTE_UNUSED
,
330 tree type ATTRIBUTE_UNUSED
,
331 const irange
&lhs ATTRIBUTE_UNUSED
,
332 const irange
&op2 ATTRIBUTE_UNUSED
,
338 // The default for op2_range is to return false.
341 range_operator::op2_range (irange
&r ATTRIBUTE_UNUSED
,
342 tree type ATTRIBUTE_UNUSED
,
343 const irange
&lhs ATTRIBUTE_UNUSED
,
344 const irange
&op1 ATTRIBUTE_UNUSED
,
350 // The default relation routines return VREL_VARYING.
353 range_operator::lhs_op1_relation (const irange
&lhs ATTRIBUTE_UNUSED
,
354 const irange
&op1 ATTRIBUTE_UNUSED
,
355 const irange
&op2 ATTRIBUTE_UNUSED
,
356 relation_kind rel ATTRIBUTE_UNUSED
) const
362 range_operator::lhs_op2_relation (const irange
&lhs ATTRIBUTE_UNUSED
,
363 const irange
&op1 ATTRIBUTE_UNUSED
,
364 const irange
&op2 ATTRIBUTE_UNUSED
,
365 relation_kind rel ATTRIBUTE_UNUSED
) const
371 range_operator::op1_op2_relation (const irange
&lhs ATTRIBUTE_UNUSED
) const
376 // Default is no relation affects the LHS.
379 range_operator::op1_op2_relation_effect (irange
&lhs_range ATTRIBUTE_UNUSED
,
380 tree type ATTRIBUTE_UNUSED
,
381 const irange
&op1_range ATTRIBUTE_UNUSED
,
382 const irange
&op2_range ATTRIBUTE_UNUSED
,
383 relation_kind rel ATTRIBUTE_UNUSED
) const
388 // Create and return a range from a pair of wide-ints that are known
389 // to have overflowed (or underflowed).
392 value_range_from_overflowed_bounds (irange
&r
, tree type
,
393 const wide_int
&wmin
,
394 const wide_int
&wmax
)
396 const signop sgn
= TYPE_SIGN (type
);
397 const unsigned int prec
= TYPE_PRECISION (type
);
399 wide_int tmin
= wide_int::from (wmin
, prec
, sgn
);
400 wide_int tmax
= wide_int::from (wmax
, prec
, sgn
);
405 if (wi::cmp (tmin
, tmax
, sgn
) < 0)
408 if (wi::cmp (tmax
, tem
, sgn
) > 0)
411 // If the anti-range would cover nothing, drop to varying.
412 // Likewise if the anti-range bounds are outside of the types
414 if (covers
|| wi::cmp (tmin
, tmax
, sgn
) > 0)
415 r
.set_varying (type
);
418 tree tree_min
= wide_int_to_tree (type
, tmin
);
419 tree tree_max
= wide_int_to_tree (type
, tmax
);
420 r
.set (tree_min
, tree_max
, VR_ANTI_RANGE
);
424 // Create and return a range from a pair of wide-ints. MIN_OVF and
425 // MAX_OVF describe any overflow that might have occurred while
426 // calculating WMIN and WMAX respectively.
429 value_range_with_overflow (irange
&r
, tree type
,
430 const wide_int
&wmin
, const wide_int
&wmax
,
431 wi::overflow_type min_ovf
= wi::OVF_NONE
,
432 wi::overflow_type max_ovf
= wi::OVF_NONE
)
434 const signop sgn
= TYPE_SIGN (type
);
435 const unsigned int prec
= TYPE_PRECISION (type
);
436 const bool overflow_wraps
= TYPE_OVERFLOW_WRAPS (type
);
438 // For one bit precision if max != min, then the range covers all
440 if (prec
== 1 && wi::ne_p (wmax
, wmin
))
442 r
.set_varying (type
);
448 // If overflow wraps, truncate the values and adjust the range,
449 // kind, and bounds appropriately.
450 if ((min_ovf
!= wi::OVF_NONE
) == (max_ovf
!= wi::OVF_NONE
))
452 wide_int tmin
= wide_int::from (wmin
, prec
, sgn
);
453 wide_int tmax
= wide_int::from (wmax
, prec
, sgn
);
454 // If the limits are swapped, we wrapped around and cover
456 if (wi::gt_p (tmin
, tmax
, sgn
))
457 r
.set_varying (type
);
459 // No overflow or both overflow or underflow. The range
460 // kind stays normal.
461 r
.set (wide_int_to_tree (type
, tmin
),
462 wide_int_to_tree (type
, tmax
));
466 if ((min_ovf
== wi::OVF_UNDERFLOW
&& max_ovf
== wi::OVF_NONE
)
467 || (max_ovf
== wi::OVF_OVERFLOW
&& min_ovf
== wi::OVF_NONE
))
468 value_range_from_overflowed_bounds (r
, type
, wmin
, wmax
);
470 // Other underflow and/or overflow, drop to VR_VARYING.
471 r
.set_varying (type
);
475 // If both bounds either underflowed or overflowed, then the result
477 if ((min_ovf
== wi::OVF_OVERFLOW
&& max_ovf
== wi::OVF_OVERFLOW
)
478 || (min_ovf
== wi::OVF_UNDERFLOW
&& max_ovf
== wi::OVF_UNDERFLOW
))
484 // If overflow does not wrap, saturate to [MIN, MAX].
485 wide_int new_lb
, new_ub
;
486 if (min_ovf
== wi::OVF_UNDERFLOW
)
487 new_lb
= wi::min_value (prec
, sgn
);
488 else if (min_ovf
== wi::OVF_OVERFLOW
)
489 new_lb
= wi::max_value (prec
, sgn
);
493 if (max_ovf
== wi::OVF_UNDERFLOW
)
494 new_ub
= wi::min_value (prec
, sgn
);
495 else if (max_ovf
== wi::OVF_OVERFLOW
)
496 new_ub
= wi::max_value (prec
, sgn
);
500 r
.set (wide_int_to_tree (type
, new_lb
),
501 wide_int_to_tree (type
, new_ub
));
505 // Create and return a range from a pair of wide-ints. Canonicalize
506 // the case where the bounds are swapped. In which case, we transform
507 // [10,5] into [MIN,5][10,MAX].
510 create_possibly_reversed_range (irange
&r
, tree type
,
511 const wide_int
&new_lb
, const wide_int
&new_ub
)
513 signop s
= TYPE_SIGN (type
);
514 // If the bounds are swapped, treat the result as if an overflow occured.
515 if (wi::gt_p (new_lb
, new_ub
, s
))
516 value_range_from_overflowed_bounds (r
, type
, new_lb
, new_ub
);
518 // Otherwise it's just a normal range.
519 r
.set (wide_int_to_tree (type
, new_lb
), wide_int_to_tree (type
, new_ub
));
522 // Return the summary information about boolean range LHS. If EMPTY/FULL,
523 // return the equivalent range for TYPE in R; if FALSE/TRUE, do nothing.
526 get_bool_state (vrange
&r
, const vrange
&lhs
, tree val_type
)
528 // If there is no result, then this is unexecutable.
529 if (lhs
.undefined_p ())
538 // For TRUE, we can't just test for [1,1] because Ada can have
539 // multi-bit booleans, and TRUE values can be: [1, MAX], ~[0], etc.
540 if (lhs
.contains_p (build_zero_cst (lhs
.type ())))
542 r
.set_varying (val_type
);
550 class operator_equal
: public range_operator
552 using range_operator::fold_range
;
553 using range_operator::op1_range
;
554 using range_operator::op2_range
;
556 virtual bool fold_range (irange
&r
, tree type
,
559 relation_trio
= TRIO_VARYING
) const;
560 virtual bool op1_range (irange
&r
, tree type
,
563 relation_trio
= TRIO_VARYING
) const;
564 virtual bool op2_range (irange
&r
, tree type
,
567 relation_trio
= TRIO_VARYING
) const;
568 virtual relation_kind
op1_op2_relation (const irange
&lhs
) const;
571 // Check if the LHS range indicates a relation between OP1 and OP2.
574 equal_op1_op2_relation (const irange
&lhs
)
576 if (lhs
.undefined_p ())
577 return VREL_UNDEFINED
;
579 // FALSE = op1 == op2 indicates NE_EXPR.
583 // TRUE = op1 == op2 indicates EQ_EXPR.
584 if (!lhs
.contains_p (build_zero_cst (lhs
.type ())))
590 operator_equal::op1_op2_relation (const irange
&lhs
) const
592 return equal_op1_op2_relation (lhs
);
597 operator_equal::fold_range (irange
&r
, tree type
,
600 relation_trio rel
) const
602 if (relop_early_resolve (r
, type
, op1
, op2
, rel
, VREL_EQ
))
605 // We can be sure the values are always equal or not if both ranges
606 // consist of a single value, and then compare them.
607 if (wi::eq_p (op1
.lower_bound (), op1
.upper_bound ())
608 && wi::eq_p (op2
.lower_bound (), op2
.upper_bound ()))
610 if (wi::eq_p (op1
.lower_bound (), op2
.upper_bound()))
611 r
= range_true (type
);
613 r
= range_false (type
);
617 // If ranges do not intersect, we know the range is not equal,
618 // otherwise we don't know anything for sure.
619 int_range_max tmp
= op1
;
621 if (tmp
.undefined_p ())
622 r
= range_false (type
);
624 r
= range_true_and_false (type
);
630 operator_equal::op1_range (irange
&r
, tree type
,
635 switch (get_bool_state (r
, lhs
, type
))
638 // If it's true, the result is the same as OP2.
643 // If the result is false, the only time we know anything is
644 // if OP2 is a constant.
645 if (!op2
.undefined_p ()
646 && wi::eq_p (op2
.lower_bound(), op2
.upper_bound()))
652 r
.set_varying (type
);
662 operator_equal::op2_range (irange
&r
, tree type
,
665 relation_trio rel
) const
667 return operator_equal::op1_range (r
, type
, lhs
, op1
, rel
.swap_op1_op2 ());
670 class operator_not_equal
: public range_operator
672 using range_operator::fold_range
;
673 using range_operator::op1_range
;
674 using range_operator::op2_range
;
676 virtual bool fold_range (irange
&r
, tree type
,
679 relation_trio
= TRIO_VARYING
) const;
680 virtual bool op1_range (irange
&r
, tree type
,
683 relation_trio
= TRIO_VARYING
) const;
684 virtual bool op2_range (irange
&r
, tree type
,
687 relation_trio
= TRIO_VARYING
) const;
688 virtual relation_kind
op1_op2_relation (const irange
&lhs
) const;
691 // Check if the LHS range indicates a relation between OP1 and OP2.
694 not_equal_op1_op2_relation (const irange
&lhs
)
696 if (lhs
.undefined_p ())
697 return VREL_UNDEFINED
;
699 // FALSE = op1 != op2 indicates EQ_EXPR.
703 // TRUE = op1 != op2 indicates NE_EXPR.
704 if (!lhs
.contains_p (build_zero_cst (lhs
.type ())))
710 operator_not_equal::op1_op2_relation (const irange
&lhs
) const
712 return not_equal_op1_op2_relation (lhs
);
716 operator_not_equal::fold_range (irange
&r
, tree type
,
719 relation_trio rel
) const
721 if (relop_early_resolve (r
, type
, op1
, op2
, rel
, VREL_NE
))
724 // We can be sure the values are always equal or not if both ranges
725 // consist of a single value, and then compare them.
726 if (wi::eq_p (op1
.lower_bound (), op1
.upper_bound ())
727 && wi::eq_p (op2
.lower_bound (), op2
.upper_bound ()))
729 if (wi::ne_p (op1
.lower_bound (), op2
.upper_bound()))
730 r
= range_true (type
);
732 r
= range_false (type
);
736 // If ranges do not intersect, we know the range is not equal,
737 // otherwise we don't know anything for sure.
738 int_range_max tmp
= op1
;
740 if (tmp
.undefined_p ())
741 r
= range_true (type
);
743 r
= range_true_and_false (type
);
749 operator_not_equal::op1_range (irange
&r
, tree type
,
754 switch (get_bool_state (r
, lhs
, type
))
757 // If the result is true, the only time we know anything is if
758 // OP2 is a constant.
759 if (!op2
.undefined_p ()
760 && wi::eq_p (op2
.lower_bound(), op2
.upper_bound()))
766 r
.set_varying (type
);
770 // If it's false, the result is the same as OP2.
782 operator_not_equal::op2_range (irange
&r
, tree type
,
785 relation_trio rel
) const
787 return operator_not_equal::op1_range (r
, type
, lhs
, op1
, rel
.swap_op1_op2 ());
790 // (X < VAL) produces the range of [MIN, VAL - 1].
793 build_lt (irange
&r
, tree type
, const wide_int
&val
)
795 wi::overflow_type ov
;
797 signop sgn
= TYPE_SIGN (type
);
799 // Signed 1 bit cannot represent 1 for subtraction.
801 lim
= wi::add (val
, -1, sgn
, &ov
);
803 lim
= wi::sub (val
, 1, sgn
, &ov
);
805 // If val - 1 underflows, check if X < MIN, which is an empty range.
809 r
= int_range
<1> (type
, min_limit (type
), lim
);
812 // (X <= VAL) produces the range of [MIN, VAL].
815 build_le (irange
&r
, tree type
, const wide_int
&val
)
817 r
= int_range
<1> (type
, min_limit (type
), val
);
820 // (X > VAL) produces the range of [VAL + 1, MAX].
823 build_gt (irange
&r
, tree type
, const wide_int
&val
)
825 wi::overflow_type ov
;
827 signop sgn
= TYPE_SIGN (type
);
829 // Signed 1 bit cannot represent 1 for addition.
831 lim
= wi::sub (val
, -1, sgn
, &ov
);
833 lim
= wi::add (val
, 1, sgn
, &ov
);
834 // If val + 1 overflows, check is for X > MAX, which is an empty range.
838 r
= int_range
<1> (type
, lim
, max_limit (type
));
841 // (X >= val) produces the range of [VAL, MAX].
844 build_ge (irange
&r
, tree type
, const wide_int
&val
)
846 r
= int_range
<1> (type
, val
, max_limit (type
));
850 class operator_lt
: public range_operator
852 using range_operator::fold_range
;
853 using range_operator::op1_range
;
854 using range_operator::op2_range
;
856 virtual bool fold_range (irange
&r
, tree type
,
859 relation_trio
= TRIO_VARYING
) const;
860 virtual bool op1_range (irange
&r
, tree type
,
863 relation_trio
= TRIO_VARYING
) const;
864 virtual bool op2_range (irange
&r
, tree type
,
867 relation_trio
= TRIO_VARYING
) const;
868 virtual relation_kind
op1_op2_relation (const irange
&lhs
) const;
871 // Check if the LHS range indicates a relation between OP1 and OP2.
874 lt_op1_op2_relation (const irange
&lhs
)
876 if (lhs
.undefined_p ())
877 return VREL_UNDEFINED
;
879 // FALSE = op1 < op2 indicates GE_EXPR.
883 // TRUE = op1 < op2 indicates LT_EXPR.
884 if (!lhs
.contains_p (build_zero_cst (lhs
.type ())))
890 operator_lt::op1_op2_relation (const irange
&lhs
) const
892 return lt_op1_op2_relation (lhs
);
896 operator_lt::fold_range (irange
&r
, tree type
,
899 relation_trio rel
) const
901 if (relop_early_resolve (r
, type
, op1
, op2
, rel
, VREL_LT
))
904 signop sign
= TYPE_SIGN (op1
.type ());
905 gcc_checking_assert (sign
== TYPE_SIGN (op2
.type ()));
907 if (wi::lt_p (op1
.upper_bound (), op2
.lower_bound (), sign
))
908 r
= range_true (type
);
909 else if (!wi::lt_p (op1
.lower_bound (), op2
.upper_bound (), sign
))
910 r
= range_false (type
);
911 // Use nonzero bits to determine if < 0 is false.
912 else if (op2
.zero_p () && !wi::neg_p (op1
.get_nonzero_bits (), sign
))
913 r
= range_false (type
);
915 r
= range_true_and_false (type
);
920 operator_lt::op1_range (irange
&r
, tree type
,
925 if (op2
.undefined_p ())
928 switch (get_bool_state (r
, lhs
, type
))
931 build_lt (r
, type
, op2
.upper_bound ());
935 build_ge (r
, type
, op2
.lower_bound ());
945 operator_lt::op2_range (irange
&r
, tree type
,
950 if (op1
.undefined_p ())
953 switch (get_bool_state (r
, lhs
, type
))
956 build_gt (r
, type
, op1
.lower_bound ());
960 build_le (r
, type
, op1
.upper_bound ());
970 class operator_le
: public range_operator
972 using range_operator::fold_range
;
973 using range_operator::op1_range
;
974 using range_operator::op2_range
;
976 virtual bool fold_range (irange
&r
, tree type
,
979 relation_trio
= TRIO_VARYING
) const;
980 virtual bool op1_range (irange
&r
, tree type
,
983 relation_trio
= TRIO_VARYING
) const;
984 virtual bool op2_range (irange
&r
, tree type
,
987 relation_trio
= TRIO_VARYING
) const;
988 virtual relation_kind
op1_op2_relation (const irange
&lhs
) const;
991 // Check if the LHS range indicates a relation between OP1 and OP2.
994 le_op1_op2_relation (const irange
&lhs
)
996 if (lhs
.undefined_p ())
997 return VREL_UNDEFINED
;
999 // FALSE = op1 <= op2 indicates GT_EXPR.
1003 // TRUE = op1 <= op2 indicates LE_EXPR.
1004 if (!lhs
.contains_p (build_zero_cst (lhs
.type ())))
1006 return VREL_VARYING
;
1010 operator_le::op1_op2_relation (const irange
&lhs
) const
1012 return le_op1_op2_relation (lhs
);
1016 operator_le::fold_range (irange
&r
, tree type
,
1019 relation_trio rel
) const
1021 if (relop_early_resolve (r
, type
, op1
, op2
, rel
, VREL_LE
))
1024 signop sign
= TYPE_SIGN (op1
.type ());
1025 gcc_checking_assert (sign
== TYPE_SIGN (op2
.type ()));
1027 if (wi::le_p (op1
.upper_bound (), op2
.lower_bound (), sign
))
1028 r
= range_true (type
);
1029 else if (!wi::le_p (op1
.lower_bound (), op2
.upper_bound (), sign
))
1030 r
= range_false (type
);
1032 r
= range_true_and_false (type
);
1037 operator_le::op1_range (irange
&r
, tree type
,
1040 relation_trio
) const
1042 if (op2
.undefined_p ())
1045 switch (get_bool_state (r
, lhs
, type
))
1048 build_le (r
, type
, op2
.upper_bound ());
1052 build_gt (r
, type
, op2
.lower_bound ());
1062 operator_le::op2_range (irange
&r
, tree type
,
1065 relation_trio
) const
1067 if (op1
.undefined_p ())
1070 switch (get_bool_state (r
, lhs
, type
))
1073 build_ge (r
, type
, op1
.lower_bound ());
1077 build_lt (r
, type
, op1
.upper_bound ());
1087 class operator_gt
: public range_operator
1089 using range_operator::fold_range
;
1090 using range_operator::op1_range
;
1091 using range_operator::op2_range
;
1093 virtual bool fold_range (irange
&r
, tree type
,
1096 relation_trio
= TRIO_VARYING
) const;
1097 virtual bool op1_range (irange
&r
, tree type
,
1100 relation_trio
= TRIO_VARYING
) const;
1101 virtual bool op2_range (irange
&r
, tree type
,
1104 relation_trio
= TRIO_VARYING
) const;
1105 virtual relation_kind
op1_op2_relation (const irange
&lhs
) const;
1108 // Check if the LHS range indicates a relation between OP1 and OP2.
1111 gt_op1_op2_relation (const irange
&lhs
)
1113 if (lhs
.undefined_p ())
1114 return VREL_UNDEFINED
;
1116 // FALSE = op1 > op2 indicates LE_EXPR.
1120 // TRUE = op1 > op2 indicates GT_EXPR.
1121 if (!lhs
.contains_p (build_zero_cst (lhs
.type ())))
1123 return VREL_VARYING
;
1127 operator_gt::op1_op2_relation (const irange
&lhs
) const
1129 return gt_op1_op2_relation (lhs
);
1134 operator_gt::fold_range (irange
&r
, tree type
,
1135 const irange
&op1
, const irange
&op2
,
1136 relation_trio rel
) const
1138 if (relop_early_resolve (r
, type
, op1
, op2
, rel
, VREL_GT
))
1141 signop sign
= TYPE_SIGN (op1
.type ());
1142 gcc_checking_assert (sign
== TYPE_SIGN (op2
.type ()));
1144 if (wi::gt_p (op1
.lower_bound (), op2
.upper_bound (), sign
))
1145 r
= range_true (type
);
1146 else if (!wi::gt_p (op1
.upper_bound (), op2
.lower_bound (), sign
))
1147 r
= range_false (type
);
1149 r
= range_true_and_false (type
);
1154 operator_gt::op1_range (irange
&r
, tree type
,
1155 const irange
&lhs
, const irange
&op2
,
1156 relation_trio
) const
1158 if (op2
.undefined_p ())
1161 switch (get_bool_state (r
, lhs
, type
))
1164 build_gt (r
, type
, op2
.lower_bound ());
1168 build_le (r
, type
, op2
.upper_bound ());
1178 operator_gt::op2_range (irange
&r
, tree type
,
1181 relation_trio
) const
1183 if (op1
.undefined_p ())
1186 switch (get_bool_state (r
, lhs
, type
))
1189 build_lt (r
, type
, op1
.upper_bound ());
1193 build_ge (r
, type
, op1
.lower_bound ());
1203 class operator_ge
: public range_operator
1205 using range_operator::fold_range
;
1206 using range_operator::op1_range
;
1207 using range_operator::op2_range
;
1209 virtual bool fold_range (irange
&r
, tree type
,
1212 relation_trio
= TRIO_VARYING
) const;
1213 virtual bool op1_range (irange
&r
, tree type
,
1216 relation_trio
= TRIO_VARYING
) const;
1217 virtual bool op2_range (irange
&r
, tree type
,
1220 relation_trio
= TRIO_VARYING
) const;
1221 virtual relation_kind
op1_op2_relation (const irange
&lhs
) const;
1224 // Check if the LHS range indicates a relation between OP1 and OP2.
1227 ge_op1_op2_relation (const irange
&lhs
)
1229 if (lhs
.undefined_p ())
1230 return VREL_UNDEFINED
;
1232 // FALSE = op1 >= op2 indicates LT_EXPR.
1236 // TRUE = op1 >= op2 indicates GE_EXPR.
1237 if (!lhs
.contains_p (build_zero_cst (lhs
.type ())))
1239 return VREL_VARYING
;
1243 operator_ge::op1_op2_relation (const irange
&lhs
) const
1245 return ge_op1_op2_relation (lhs
);
1249 operator_ge::fold_range (irange
&r
, tree type
,
1252 relation_trio rel
) const
1254 if (relop_early_resolve (r
, type
, op1
, op2
, rel
, VREL_GE
))
1257 signop sign
= TYPE_SIGN (op1
.type ());
1258 gcc_checking_assert (sign
== TYPE_SIGN (op2
.type ()));
1260 if (wi::ge_p (op1
.lower_bound (), op2
.upper_bound (), sign
))
1261 r
= range_true (type
);
1262 else if (!wi::ge_p (op1
.upper_bound (), op2
.lower_bound (), sign
))
1263 r
= range_false (type
);
1265 r
= range_true_and_false (type
);
1270 operator_ge::op1_range (irange
&r
, tree type
,
1273 relation_trio
) const
1275 if (op2
.undefined_p ())
1278 switch (get_bool_state (r
, lhs
, type
))
1281 build_ge (r
, type
, op2
.lower_bound ());
1285 build_lt (r
, type
, op2
.upper_bound ());
1295 operator_ge::op2_range (irange
&r
, tree type
,
1298 relation_trio
) const
1300 if (op1
.undefined_p ())
1303 switch (get_bool_state (r
, lhs
, type
))
1306 build_le (r
, type
, op1
.upper_bound ());
1310 build_gt (r
, type
, op1
.lower_bound ());
1320 class operator_plus
: public range_operator
1322 using range_operator::op1_range
;
1323 using range_operator::op2_range
;
1324 using range_operator::lhs_op1_relation
;
1325 using range_operator::lhs_op2_relation
;
1327 virtual bool op1_range (irange
&r
, tree type
,
1330 relation_trio
) const;
1331 virtual bool op2_range (irange
&r
, tree type
,
1334 relation_trio
) const;
1335 virtual void wi_fold (irange
&r
, tree type
,
1336 const wide_int
&lh_lb
,
1337 const wide_int
&lh_ub
,
1338 const wide_int
&rh_lb
,
1339 const wide_int
&rh_ub
) const;
1340 virtual relation_kind
lhs_op1_relation (const irange
&lhs
, const irange
&op1
,
1342 relation_kind rel
) const;
1343 virtual relation_kind
lhs_op2_relation (const irange
&lhs
, const irange
&op1
,
1345 relation_kind rel
) const;
1348 // Check to see if the range of OP2 indicates anything about the relation
1349 // between LHS and OP1.
1352 operator_plus::lhs_op1_relation (const irange
&lhs
,
1355 relation_kind
) const
1357 if (lhs
.undefined_p () || op1
.undefined_p () || op2
.undefined_p ())
1358 return VREL_VARYING
;
1360 tree type
= lhs
.type ();
1361 unsigned prec
= TYPE_PRECISION (type
);
1362 wi::overflow_type ovf1
, ovf2
;
1363 signop sign
= TYPE_SIGN (type
);
1365 // LHS = OP1 + 0 indicates LHS == OP1.
1369 if (TYPE_OVERFLOW_WRAPS (type
))
1371 wi::add (op1
.lower_bound (), op2
.lower_bound (), sign
, &ovf1
);
1372 wi::add (op1
.upper_bound (), op2
.upper_bound (), sign
, &ovf2
);
1375 ovf1
= ovf2
= wi::OVF_NONE
;
1377 // Never wrapping additions.
1380 // Positive op2 means lhs > op1.
1381 if (wi::gt_p (op2
.lower_bound (), wi::zero (prec
), sign
))
1383 if (wi::ge_p (op2
.lower_bound (), wi::zero (prec
), sign
))
1386 // Negative op2 means lhs < op1.
1387 if (wi::lt_p (op2
.upper_bound (), wi::zero (prec
), sign
))
1389 if (wi::le_p (op2
.upper_bound (), wi::zero (prec
), sign
))
1392 // Always wrapping additions.
1393 else if (ovf1
&& ovf1
== ovf2
)
1395 // Positive op2 means lhs < op1.
1396 if (wi::gt_p (op2
.lower_bound (), wi::zero (prec
), sign
))
1398 if (wi::ge_p (op2
.lower_bound (), wi::zero (prec
), sign
))
1401 // Negative op2 means lhs > op1.
1402 if (wi::lt_p (op2
.upper_bound (), wi::zero (prec
), sign
))
1404 if (wi::le_p (op2
.upper_bound (), wi::zero (prec
), sign
))
1408 // If op2 does not contain 0, then LHS and OP1 can never be equal.
1409 if (!range_includes_zero_p (&op2
))
1412 return VREL_VARYING
;
1415 // PLUS is symmetrical, so we can simply call lhs_op1_relation with reversed
1419 operator_plus::lhs_op2_relation (const irange
&lhs
, const irange
&op1
,
1420 const irange
&op2
, relation_kind rel
) const
1422 return lhs_op1_relation (lhs
, op2
, op1
, rel
);
1426 operator_plus::wi_fold (irange
&r
, tree type
,
1427 const wide_int
&lh_lb
, const wide_int
&lh_ub
,
1428 const wide_int
&rh_lb
, const wide_int
&rh_ub
) const
1430 wi::overflow_type ov_lb
, ov_ub
;
1431 signop s
= TYPE_SIGN (type
);
1432 wide_int new_lb
= wi::add (lh_lb
, rh_lb
, s
, &ov_lb
);
1433 wide_int new_ub
= wi::add (lh_ub
, rh_ub
, s
, &ov_ub
);
1434 value_range_with_overflow (r
, type
, new_lb
, new_ub
, ov_lb
, ov_ub
);
1437 // Given addition or subtraction, determine the possible NORMAL ranges and
1438 // OVERFLOW ranges given an OFFSET range. ADD_P is true for addition.
1439 // Return the relation that exists between the LHS and OP1 in order for the
1440 // NORMAL range to apply.
1441 // a return value of VREL_VARYING means no ranges were applicable.
1443 static relation_kind
1444 plus_minus_ranges (irange
&r_ov
, irange
&r_normal
, const irange
&offset
,
1447 relation_kind kind
= VREL_VARYING
;
1448 // For now, only deal with constant adds. This could be extended to ranges
1449 // when someone is so motivated.
1450 if (!offset
.singleton_p () || offset
.zero_p ())
1453 // Always work with a positive offset. ie a+ -2 -> a-2 and a- -2 > a+2
1454 wide_int off
= offset
.lower_bound ();
1455 if (wi::neg_p (off
, SIGNED
))
1458 off
= wi::neg (off
);
1461 wi::overflow_type ov
;
1462 tree type
= offset
.type ();
1463 unsigned prec
= TYPE_PRECISION (type
);
1466 // calculate the normal range and relation for the operation.
1470 lb
= wi::zero (prec
);
1471 ub
= wi::sub (wi::to_wide (vrp_val_max (type
)), off
, UNSIGNED
, &ov
);
1478 ub
= wi::to_wide (vrp_val_max (type
));
1481 int_range
<2> normal_range (type
, lb
, ub
);
1482 int_range
<2> ov_range (type
, lb
, ub
, VR_ANTI_RANGE
);
1485 r_normal
= normal_range
;
1489 // Once op1 has been calculated by operator_plus or operator_minus, check
1490 // to see if the relation passed causes any part of the calculation to
1491 // be not possible. ie
1492 // a_2 = b_3 + 1 with a_2 < b_3 can refine the range of b_3 to [INF, INF]
1493 // and that further refines a_2 to [0, 0].
1494 // R is the value of op1, OP2 is the offset being added/subtracted, REL is the
1495 // relation between LHS relatoin OP1 and ADD_P is true for PLUS, false for
1496 // MINUS. IF any adjustment can be made, R will reflect it.
1499 adjust_op1_for_overflow (irange
&r
, const irange
&op2
, relation_kind rel
,
1502 if (r
.undefined_p ())
1504 tree type
= r
.type ();
1505 // Check for unsigned overflow and calculate the overflow part.
1506 signop s
= TYPE_SIGN (type
);
1507 if (!TYPE_OVERFLOW_WRAPS (type
) || s
== SIGNED
)
1510 // Only work with <, <=, >, >= relations.
1511 if (!relation_lt_le_gt_ge_p (rel
))
1514 // Get the ranges for this offset.
1515 int_range_max normal
, overflow
;
1516 relation_kind k
= plus_minus_ranges (overflow
, normal
, op2
, add_p
);
1518 // VREL_VARYING means there are no adjustments.
1519 if (k
== VREL_VARYING
)
1522 // If the relations match use the normal range, otherwise use overflow range.
1523 if (relation_intersect (k
, rel
) == k
)
1524 r
.intersect (normal
);
1526 r
.intersect (overflow
);
1531 operator_plus::op1_range (irange
&r
, tree type
,
1534 relation_trio trio
) const
1536 if (lhs
.undefined_p ())
1538 // Start with the default operation.
1539 range_op_handler
minus (MINUS_EXPR
, type
);
1542 bool res
= minus
.fold_range (r
, type
, lhs
, op2
);
1543 relation_kind rel
= trio
.lhs_op1 ();
1544 // Check for a relation refinement.
1546 adjust_op1_for_overflow (r
, op2
, rel
, true /* PLUS_EXPR */);
1551 operator_plus::op2_range (irange
&r
, tree type
,
1554 relation_trio rel
) const
1556 return op1_range (r
, type
, lhs
, op1
, rel
.swap_op1_op2 ());
1560 class operator_minus
: public range_operator
1562 using range_operator::fold_range
;
1563 using range_operator::op1_range
;
1564 using range_operator::op2_range
;
1566 virtual bool op1_range (irange
&r
, tree type
,
1569 relation_trio
) const;
1570 virtual bool op2_range (irange
&r
, tree type
,
1573 relation_trio
) const;
1574 virtual void wi_fold (irange
&r
, tree type
,
1575 const wide_int
&lh_lb
,
1576 const wide_int
&lh_ub
,
1577 const wide_int
&rh_lb
,
1578 const wide_int
&rh_ub
) const;
1579 virtual relation_kind
lhs_op1_relation (const irange
&lhs
,
1582 relation_kind rel
) const;
1583 virtual bool op1_op2_relation_effect (irange
&lhs_range
,
1585 const irange
&op1_range
,
1586 const irange
&op2_range
,
1587 relation_kind rel
) const;
1591 operator_minus::wi_fold (irange
&r
, tree type
,
1592 const wide_int
&lh_lb
, const wide_int
&lh_ub
,
1593 const wide_int
&rh_lb
, const wide_int
&rh_ub
) const
1595 wi::overflow_type ov_lb
, ov_ub
;
1596 signop s
= TYPE_SIGN (type
);
1597 wide_int new_lb
= wi::sub (lh_lb
, rh_ub
, s
, &ov_lb
);
1598 wide_int new_ub
= wi::sub (lh_ub
, rh_lb
, s
, &ov_ub
);
1599 value_range_with_overflow (r
, type
, new_lb
, new_ub
, ov_lb
, ov_ub
);
1603 // Return the relation between LHS and OP1 based on the relation between
1607 operator_minus::lhs_op1_relation (const irange
&, const irange
&op1
,
1608 const irange
&, relation_kind rel
) const
1610 if (!op1
.undefined_p () && TYPE_SIGN (op1
.type ()) == UNSIGNED
)
1619 return VREL_VARYING
;
1622 // Check to see if the relation REL between OP1 and OP2 has any effect on the
1623 // LHS of the expression. If so, apply it to LHS_RANGE. This is a helper
1624 // function for both MINUS_EXPR and POINTER_DIFF_EXPR.
1627 minus_op1_op2_relation_effect (irange
&lhs_range
, tree type
,
1628 const irange
&op1_range ATTRIBUTE_UNUSED
,
1629 const irange
&op2_range ATTRIBUTE_UNUSED
,
1632 if (rel
== VREL_VARYING
)
1635 int_range
<2> rel_range
;
1636 unsigned prec
= TYPE_PRECISION (type
);
1637 signop sgn
= TYPE_SIGN (type
);
1639 // == and != produce [0,0] and ~[0,0] regardless of wrapping.
1641 rel_range
= int_range
<2> (type
, wi::zero (prec
), wi::zero (prec
));
1642 else if (rel
== VREL_NE
)
1643 rel_range
= int_range
<2> (type
, wi::zero (prec
), wi::zero (prec
),
1645 else if (TYPE_OVERFLOW_WRAPS (type
))
1649 // For wrapping signed values and unsigned, if op1 > op2 or
1650 // op1 < op2, then op1 - op2 can be restricted to ~[0, 0].
1653 rel_range
= int_range
<2> (type
, wi::zero (prec
), wi::zero (prec
),
1664 // op1 > op2, op1 - op2 can be restricted to [1, +INF]
1666 rel_range
= int_range
<2> (type
, wi::one (prec
),
1667 wi::max_value (prec
, sgn
));
1669 // op1 >= op2, op1 - op2 can be restricted to [0, +INF]
1671 rel_range
= int_range
<2> (type
, wi::zero (prec
),
1672 wi::max_value (prec
, sgn
));
1674 // op1 < op2, op1 - op2 can be restricted to [-INF, -1]
1676 rel_range
= int_range
<2> (type
, wi::min_value (prec
, sgn
),
1677 wi::minus_one (prec
));
1679 // op1 <= op2, op1 - op2 can be restricted to [-INF, 0]
1681 rel_range
= int_range
<2> (type
, wi::min_value (prec
, sgn
),
1688 lhs_range
.intersect (rel_range
);
1693 operator_minus::op1_op2_relation_effect (irange
&lhs_range
, tree type
,
1694 const irange
&op1_range
,
1695 const irange
&op2_range
,
1696 relation_kind rel
) const
1698 return minus_op1_op2_relation_effect (lhs_range
, type
, op1_range
, op2_range
,
1703 operator_minus::op1_range (irange
&r
, tree type
,
1706 relation_trio trio
) const
1708 if (lhs
.undefined_p ())
1710 // Start with the default operation.
1711 range_op_handler
minus (PLUS_EXPR
, type
);
1714 bool res
= minus
.fold_range (r
, type
, lhs
, op2
);
1715 relation_kind rel
= trio
.lhs_op1 ();
1717 adjust_op1_for_overflow (r
, op2
, rel
, false /* PLUS_EXPR */);
1723 operator_minus::op2_range (irange
&r
, tree type
,
1726 relation_trio
) const
1728 if (lhs
.undefined_p ())
1730 return fold_range (r
, type
, op1
, lhs
);
1734 class operator_pointer_diff
: public range_operator
1736 virtual bool op1_op2_relation_effect (irange
&lhs_range
,
1738 const irange
&op1_range
,
1739 const irange
&op2_range
,
1740 relation_kind rel
) const;
1744 operator_pointer_diff::op1_op2_relation_effect (irange
&lhs_range
, tree type
,
1745 const irange
&op1_range
,
1746 const irange
&op2_range
,
1747 relation_kind rel
) const
1749 return minus_op1_op2_relation_effect (lhs_range
, type
, op1_range
, op2_range
,
1754 class operator_min
: public range_operator
1757 virtual void wi_fold (irange
&r
, tree type
,
1758 const wide_int
&lh_lb
,
1759 const wide_int
&lh_ub
,
1760 const wide_int
&rh_lb
,
1761 const wide_int
&rh_ub
) const;
1765 operator_min::wi_fold (irange
&r
, tree type
,
1766 const wide_int
&lh_lb
, const wide_int
&lh_ub
,
1767 const wide_int
&rh_lb
, const wide_int
&rh_ub
) const
1769 signop s
= TYPE_SIGN (type
);
1770 wide_int new_lb
= wi::min (lh_lb
, rh_lb
, s
);
1771 wide_int new_ub
= wi::min (lh_ub
, rh_ub
, s
);
1772 value_range_with_overflow (r
, type
, new_lb
, new_ub
);
1776 class operator_max
: public range_operator
1779 virtual void wi_fold (irange
&r
, tree type
,
1780 const wide_int
&lh_lb
,
1781 const wide_int
&lh_ub
,
1782 const wide_int
&rh_lb
,
1783 const wide_int
&rh_ub
) const;
1787 operator_max::wi_fold (irange
&r
, tree type
,
1788 const wide_int
&lh_lb
, const wide_int
&lh_ub
,
1789 const wide_int
&rh_lb
, const wide_int
&rh_ub
) const
1791 signop s
= TYPE_SIGN (type
);
1792 wide_int new_lb
= wi::max (lh_lb
, rh_lb
, s
);
1793 wide_int new_ub
= wi::max (lh_ub
, rh_ub
, s
);
1794 value_range_with_overflow (r
, type
, new_lb
, new_ub
);
1798 class cross_product_operator
: public range_operator
1801 // Perform an operation between two wide-ints and place the result
1802 // in R. Return true if the operation overflowed.
1803 virtual bool wi_op_overflows (wide_int
&r
,
1806 const wide_int
&) const = 0;
1808 // Calculate the cross product of two sets of sub-ranges and return it.
1809 void wi_cross_product (irange
&r
, tree type
,
1810 const wide_int
&lh_lb
,
1811 const wide_int
&lh_ub
,
1812 const wide_int
&rh_lb
,
1813 const wide_int
&rh_ub
) const;
1816 // Calculate the cross product of two sets of ranges and return it.
1818 // Multiplications, divisions and shifts are a bit tricky to handle,
1819 // depending on the mix of signs we have in the two ranges, we need to
1820 // operate on different values to get the minimum and maximum values
1821 // for the new range. One approach is to figure out all the
1822 // variations of range combinations and do the operations.
1824 // However, this involves several calls to compare_values and it is
1825 // pretty convoluted. It's simpler to do the 4 operations (MIN0 OP
1826 // MIN1, MIN0 OP MAX1, MAX0 OP MIN1 and MAX0 OP MAX0 OP MAX1) and then
1827 // figure the smallest and largest values to form the new range.
1830 cross_product_operator::wi_cross_product (irange
&r
, tree type
,
1831 const wide_int
&lh_lb
,
1832 const wide_int
&lh_ub
,
1833 const wide_int
&rh_lb
,
1834 const wide_int
&rh_ub
) const
1836 wide_int cp1
, cp2
, cp3
, cp4
;
1837 // Default to varying.
1838 r
.set_varying (type
);
1840 // Compute the 4 cross operations, bailing if we get an overflow we
1842 if (wi_op_overflows (cp1
, type
, lh_lb
, rh_lb
))
1844 if (wi::eq_p (lh_lb
, lh_ub
))
1846 else if (wi_op_overflows (cp3
, type
, lh_ub
, rh_lb
))
1848 if (wi::eq_p (rh_lb
, rh_ub
))
1850 else if (wi_op_overflows (cp2
, type
, lh_lb
, rh_ub
))
1852 if (wi::eq_p (lh_lb
, lh_ub
))
1854 else if (wi_op_overflows (cp4
, type
, lh_ub
, rh_ub
))
1858 signop sign
= TYPE_SIGN (type
);
1859 if (wi::gt_p (cp1
, cp2
, sign
))
1860 std::swap (cp1
, cp2
);
1861 if (wi::gt_p (cp3
, cp4
, sign
))
1862 std::swap (cp3
, cp4
);
1864 // Choose min and max from the ordered pairs.
1865 wide_int res_lb
= wi::min (cp1
, cp3
, sign
);
1866 wide_int res_ub
= wi::max (cp2
, cp4
, sign
);
1867 value_range_with_overflow (r
, type
, res_lb
, res_ub
);
1871 class operator_mult
: public cross_product_operator
1873 using range_operator::op1_range
;
1874 using range_operator::op2_range
;
1876 virtual void wi_fold (irange
&r
, tree type
,
1877 const wide_int
&lh_lb
,
1878 const wide_int
&lh_ub
,
1879 const wide_int
&rh_lb
,
1880 const wide_int
&rh_ub
) const final override
;
1881 virtual bool wi_op_overflows (wide_int
&res
, tree type
,
1882 const wide_int
&w0
, const wide_int
&w1
)
1883 const final override
;
1884 virtual bool op1_range (irange
&r
, tree type
,
1887 relation_trio
) const final override
;
1888 virtual bool op2_range (irange
&r
, tree type
,
1891 relation_trio
) const final override
;
1895 operator_mult::op1_range (irange
&r
, tree type
,
1896 const irange
&lhs
, const irange
&op2
,
1897 relation_trio
) const
1900 if (lhs
.undefined_p ())
1903 // We can't solve 0 = OP1 * N by dividing by N with a wrapping type.
1904 // For example: For 0 = OP1 * 2, OP1 could be 0, or MAXINT, whereas
1905 // for 4 = OP1 * 2, OP1 could be 2 or 130 (unsigned 8-bit)
1906 if (TYPE_OVERFLOW_WRAPS (type
))
1909 if (op2
.singleton_p (&offset
) && !integer_zerop (offset
))
1910 return range_op_handler (TRUNC_DIV_EXPR
, type
).fold_range (r
, type
,
1916 operator_mult::op2_range (irange
&r
, tree type
,
1917 const irange
&lhs
, const irange
&op1
,
1918 relation_trio rel
) const
1920 return operator_mult::op1_range (r
, type
, lhs
, op1
, rel
.swap_op1_op2 ());
1924 operator_mult::wi_op_overflows (wide_int
&res
, tree type
,
1925 const wide_int
&w0
, const wide_int
&w1
) const
1927 wi::overflow_type overflow
= wi::OVF_NONE
;
1928 signop sign
= TYPE_SIGN (type
);
1929 res
= wi::mul (w0
, w1
, sign
, &overflow
);
1930 if (overflow
&& TYPE_OVERFLOW_UNDEFINED (type
))
1932 // For multiplication, the sign of the overflow is given
1933 // by the comparison of the signs of the operands.
1934 if (sign
== UNSIGNED
|| w0
.sign_mask () == w1
.sign_mask ())
1935 res
= wi::max_value (w0
.get_precision (), sign
);
1937 res
= wi::min_value (w0
.get_precision (), sign
);
1944 operator_mult::wi_fold (irange
&r
, tree type
,
1945 const wide_int
&lh_lb
, const wide_int
&lh_ub
,
1946 const wide_int
&rh_lb
, const wide_int
&rh_ub
) const
1948 if (TYPE_OVERFLOW_UNDEFINED (type
))
1950 wi_cross_product (r
, type
, lh_lb
, lh_ub
, rh_lb
, rh_ub
);
1954 // Multiply the ranges when overflow wraps. This is basically fancy
1955 // code so we don't drop to varying with an unsigned
1958 // This test requires 2*prec bits if both operands are signed and
1959 // 2*prec + 2 bits if either is not. Therefore, extend the values
1960 // using the sign of the result to PREC2. From here on out,
1961 // everthing is just signed math no matter what the input types
1964 signop sign
= TYPE_SIGN (type
);
1965 unsigned prec
= TYPE_PRECISION (type
);
1966 widest2_int min0
= widest2_int::from (lh_lb
, sign
);
1967 widest2_int max0
= widest2_int::from (lh_ub
, sign
);
1968 widest2_int min1
= widest2_int::from (rh_lb
, sign
);
1969 widest2_int max1
= widest2_int::from (rh_ub
, sign
);
1970 widest2_int sizem1
= wi::mask
<widest2_int
> (prec
, false);
1971 widest2_int size
= sizem1
+ 1;
1973 // Canonicalize the intervals.
1974 if (sign
== UNSIGNED
)
1976 if (wi::ltu_p (size
, min0
+ max0
))
1981 if (wi::ltu_p (size
, min1
+ max1
))
1988 // Sort the 4 products so that min is in prod0 and max is in
1990 widest2_int prod0
= min0
* min1
;
1991 widest2_int prod1
= min0
* max1
;
1992 widest2_int prod2
= max0
* min1
;
1993 widest2_int prod3
= max0
* max1
;
1995 // min0min1 > max0max1
1997 std::swap (prod0
, prod3
);
1999 // min0max1 > max0min1
2001 std::swap (prod1
, prod2
);
2004 std::swap (prod0
, prod1
);
2007 std::swap (prod2
, prod3
);
2010 prod2
= prod3
- prod0
;
2011 if (wi::geu_p (prod2
, sizem1
))
2013 // Multiplying by X, where X is a power of 2 is [0,0][X,+INF].
2014 if (TYPE_UNSIGNED (type
) && rh_lb
== rh_ub
2015 && wi::exact_log2 (rh_lb
) != -1 && prec
> 1)
2017 r
.set (type
, rh_lb
, wi::max_value (prec
, sign
));
2019 zero
.set_zero (type
);
2023 // The range covers all values.
2024 r
.set_varying (type
);
2028 wide_int new_lb
= wide_int::from (prod0
, prec
, sign
);
2029 wide_int new_ub
= wide_int::from (prod3
, prec
, sign
);
2030 create_possibly_reversed_range (r
, type
, new_lb
, new_ub
);
2035 class operator_div
: public cross_product_operator
2038 virtual void wi_fold (irange
&r
, tree type
,
2039 const wide_int
&lh_lb
,
2040 const wide_int
&lh_ub
,
2041 const wide_int
&rh_lb
,
2042 const wide_int
&rh_ub
) const final override
;
2043 virtual bool wi_op_overflows (wide_int
&res
, tree type
,
2044 const wide_int
&, const wide_int
&)
2045 const final override
;
2049 operator_div::wi_op_overflows (wide_int
&res
, tree type
,
2050 const wide_int
&w0
, const wide_int
&w1
) const
2055 wi::overflow_type overflow
= wi::OVF_NONE
;
2056 signop sign
= TYPE_SIGN (type
);
2060 case EXACT_DIV_EXPR
:
2061 case TRUNC_DIV_EXPR
:
2062 res
= wi::div_trunc (w0
, w1
, sign
, &overflow
);
2064 case FLOOR_DIV_EXPR
:
2065 res
= wi::div_floor (w0
, w1
, sign
, &overflow
);
2067 case ROUND_DIV_EXPR
:
2068 res
= wi::div_round (w0
, w1
, sign
, &overflow
);
2071 res
= wi::div_ceil (w0
, w1
, sign
, &overflow
);
2077 if (overflow
&& TYPE_OVERFLOW_UNDEFINED (type
))
2079 // For division, the only case is -INF / -1 = +INF.
2080 res
= wi::max_value (w0
.get_precision (), sign
);
2087 operator_div::wi_fold (irange
&r
, tree type
,
2088 const wide_int
&lh_lb
, const wide_int
&lh_ub
,
2089 const wide_int
&rh_lb
, const wide_int
&rh_ub
) const
2091 const wide_int dividend_min
= lh_lb
;
2092 const wide_int dividend_max
= lh_ub
;
2093 const wide_int divisor_min
= rh_lb
;
2094 const wide_int divisor_max
= rh_ub
;
2095 signop sign
= TYPE_SIGN (type
);
2096 unsigned prec
= TYPE_PRECISION (type
);
2097 wide_int extra_min
, extra_max
;
2099 // If we know we won't divide by zero, just do the division.
2100 if (!wi_includes_zero_p (type
, divisor_min
, divisor_max
))
2102 wi_cross_product (r
, type
, dividend_min
, dividend_max
,
2103 divisor_min
, divisor_max
);
2107 // If we're definitely dividing by zero, there's nothing to do.
2108 if (wi_zero_p (type
, divisor_min
, divisor_max
))
2114 // Perform the division in 2 parts, [LB, -1] and [1, UB], which will
2115 // skip any division by zero.
2117 // First divide by the negative numbers, if any.
2118 if (wi::neg_p (divisor_min
, sign
))
2119 wi_cross_product (r
, type
, dividend_min
, dividend_max
,
2120 divisor_min
, wi::minus_one (prec
));
2124 // Then divide by the non-zero positive numbers, if any.
2125 if (wi::gt_p (divisor_max
, wi::zero (prec
), sign
))
2128 wi_cross_product (tmp
, type
, dividend_min
, dividend_max
,
2129 wi::one (prec
), divisor_max
);
2132 // We shouldn't still have undefined here.
2133 gcc_checking_assert (!r
.undefined_p ());
2137 class operator_exact_divide
: public operator_div
2139 using range_operator::op1_range
;
2141 virtual bool op1_range (irange
&r
, tree type
,
2144 relation_trio
) const;
2149 operator_exact_divide::op1_range (irange
&r
, tree type
,
2152 relation_trio
) const
2154 if (lhs
.undefined_p ())
2157 // [2, 4] = op1 / [3,3] since its exact divide, no need to worry about
2158 // remainders in the endpoints, so op1 = [2,4] * [3,3] = [6,12].
2159 // We wont bother trying to enumerate all the in between stuff :-P
2160 // TRUE accuraacy is [6,6][9,9][12,12]. This is unlikely to matter most of
2161 // the time however.
2162 // If op2 is a multiple of 2, we would be able to set some non-zero bits.
2163 if (op2
.singleton_p (&offset
)
2164 && !integer_zerop (offset
))
2165 return range_op_handler (MULT_EXPR
, type
).fold_range (r
, type
, lhs
, op2
);
2170 class operator_lshift
: public cross_product_operator
2172 using range_operator::fold_range
;
2173 using range_operator::op1_range
;
2175 virtual bool op1_range (irange
&r
, tree type
,
2178 relation_trio rel
= TRIO_VARYING
) const;
2179 virtual bool fold_range (irange
&r
, tree type
,
2182 relation_trio rel
= TRIO_VARYING
) const;
2184 virtual void wi_fold (irange
&r
, tree type
,
2185 const wide_int
&lh_lb
, const wide_int
&lh_ub
,
2186 const wide_int
&rh_lb
, const wide_int
&rh_ub
) const;
2187 virtual bool wi_op_overflows (wide_int
&res
,
2190 const wide_int
&) const;
2193 class operator_rshift
: public cross_product_operator
2195 using range_operator::fold_range
;
2196 using range_operator::op1_range
;
2197 using range_operator::lhs_op1_relation
;
2199 virtual bool fold_range (irange
&r
, tree type
,
2202 relation_trio rel
= TRIO_VARYING
) const;
2203 virtual void wi_fold (irange
&r
, tree type
,
2204 const wide_int
&lh_lb
,
2205 const wide_int
&lh_ub
,
2206 const wide_int
&rh_lb
,
2207 const wide_int
&rh_ub
) const;
2208 virtual bool wi_op_overflows (wide_int
&res
,
2211 const wide_int
&w1
) const;
2212 virtual bool op1_range (irange
&, tree type
,
2215 relation_trio rel
= TRIO_VARYING
) const;
2216 virtual relation_kind
lhs_op1_relation (const irange
&lhs
,
2219 relation_kind rel
) const;
2224 operator_rshift::lhs_op1_relation (const irange
&lhs ATTRIBUTE_UNUSED
,
2227 relation_kind
) const
2229 // If both operands range are >= 0, then the LHS <= op1.
2230 if (!op1
.undefined_p () && !op2
.undefined_p ()
2231 && wi::ge_p (op1
.lower_bound (), 0, TYPE_SIGN (op1
.type ()))
2232 && wi::ge_p (op2
.lower_bound (), 0, TYPE_SIGN (op2
.type ())))
2234 return VREL_VARYING
;
2238 operator_lshift::fold_range (irange
&r
, tree type
,
2241 relation_trio rel
) const
2243 int_range_max shift_range
;
2244 if (!get_shift_range (shift_range
, type
, op2
))
2246 if (op2
.undefined_p ())
2253 // Transform left shifts by constants into multiplies.
2254 if (shift_range
.singleton_p ())
2256 unsigned shift
= shift_range
.lower_bound ().to_uhwi ();
2257 wide_int tmp
= wi::set_bit_in_zero (shift
, TYPE_PRECISION (type
));
2258 int_range
<1> mult (type
, tmp
, tmp
);
2260 // Force wrapping multiplication.
2261 bool saved_flag_wrapv
= flag_wrapv
;
2262 bool saved_flag_wrapv_pointer
= flag_wrapv_pointer
;
2264 flag_wrapv_pointer
= 1;
2265 bool b
= op_mult
.fold_range (r
, type
, op1
, mult
);
2266 flag_wrapv
= saved_flag_wrapv
;
2267 flag_wrapv_pointer
= saved_flag_wrapv_pointer
;
2271 // Otherwise, invoke the generic fold routine.
2272 return range_operator::fold_range (r
, type
, op1
, shift_range
, rel
);
2276 operator_lshift::wi_fold (irange
&r
, tree type
,
2277 const wide_int
&lh_lb
, const wide_int
&lh_ub
,
2278 const wide_int
&rh_lb
, const wide_int
&rh_ub
) const
2280 signop sign
= TYPE_SIGN (type
);
2281 unsigned prec
= TYPE_PRECISION (type
);
2282 int overflow_pos
= sign
== SIGNED
? prec
- 1 : prec
;
2283 int bound_shift
= overflow_pos
- rh_ub
.to_shwi ();
2284 // If bound_shift == HOST_BITS_PER_WIDE_INT, the llshift can
2285 // overflow. However, for that to happen, rh.max needs to be zero,
2286 // which means rh is a singleton range of zero, which means we simply return
2287 // [lh_lb, lh_ub] as the range.
2288 if (wi::eq_p (rh_ub
, rh_lb
) && wi::eq_p (rh_ub
, 0))
2290 r
= int_range
<2> (type
, lh_lb
, lh_ub
);
2294 wide_int bound
= wi::set_bit_in_zero (bound_shift
, prec
);
2295 wide_int complement
= ~(bound
- 1);
2296 wide_int low_bound
, high_bound
;
2297 bool in_bounds
= false;
2299 if (sign
== UNSIGNED
)
2302 high_bound
= complement
;
2303 if (wi::ltu_p (lh_ub
, low_bound
))
2305 // [5, 6] << [1, 2] == [10, 24].
2306 // We're shifting out only zeroes, the value increases
2310 else if (wi::ltu_p (high_bound
, lh_lb
))
2312 // [0xffffff00, 0xffffffff] << [1, 2]
2313 // == [0xfffffc00, 0xfffffffe].
2314 // We're shifting out only ones, the value decreases
2321 // [-1, 1] << [1, 2] == [-4, 4]
2322 low_bound
= complement
;
2324 if (wi::lts_p (lh_ub
, high_bound
)
2325 && wi::lts_p (low_bound
, lh_lb
))
2327 // For non-negative numbers, we're shifting out only zeroes,
2328 // the value increases monotonically. For negative numbers,
2329 // we're shifting out only ones, the value decreases
2336 wi_cross_product (r
, type
, lh_lb
, lh_ub
, rh_lb
, rh_ub
);
2338 r
.set_varying (type
);
2342 operator_lshift::wi_op_overflows (wide_int
&res
, tree type
,
2343 const wide_int
&w0
, const wide_int
&w1
) const
2345 signop sign
= TYPE_SIGN (type
);
2348 // It's unclear from the C standard whether shifts can overflow.
2349 // The following code ignores overflow; perhaps a C standard
2350 // interpretation ruling is needed.
2351 res
= wi::rshift (w0
, -w1
, sign
);
2354 res
= wi::lshift (w0
, w1
);
2359 operator_lshift::op1_range (irange
&r
,
2363 relation_trio
) const
2365 if (lhs
.undefined_p ())
2369 if (!lhs
.contains_p (build_zero_cst (type
)))
2370 r
.set_nonzero (type
);
2372 r
.set_varying (type
);
2374 if (op2
.singleton_p (&shift_amount
))
2376 wide_int shift
= wi::to_wide (shift_amount
);
2377 if (wi::lt_p (shift
, 0, SIGNED
))
2379 if (wi::ge_p (shift
, wi::uhwi (TYPE_PRECISION (type
),
2380 TYPE_PRECISION (op2
.type ())),
2389 // Work completely in unsigned mode to start.
2391 int_range_max tmp_range
;
2392 if (TYPE_SIGN (type
) == SIGNED
)
2394 int_range_max tmp
= lhs
;
2395 utype
= unsigned_type_for (type
);
2396 range_cast (tmp
, utype
);
2397 op_rshift
.fold_range (tmp_range
, utype
, tmp
, op2
);
2400 op_rshift
.fold_range (tmp_range
, utype
, lhs
, op2
);
2402 // Start with ranges which can produce the LHS by right shifting the
2403 // result by the shift amount.
2404 // ie [0x08, 0xF0] = op1 << 2 will start with
2405 // [00001000, 11110000] = op1 << 2
2406 // [0x02, 0x4C] aka [00000010, 00111100]
2408 // Then create a range from the LB with the least significant upper bit
2409 // set, to the upper bound with all the bits set.
2410 // This would be [0x42, 0xFC] aka [01000010, 11111100].
2412 // Ideally we do this for each subrange, but just lump them all for now.
2413 unsigned low_bits
= TYPE_PRECISION (utype
)
2414 - TREE_INT_CST_LOW (shift_amount
);
2415 wide_int up_mask
= wi::mask (low_bits
, true, TYPE_PRECISION (utype
));
2416 wide_int new_ub
= wi::bit_or (up_mask
, tmp_range
.upper_bound ());
2417 wide_int new_lb
= wi::set_bit (tmp_range
.lower_bound (), low_bits
);
2418 int_range
<2> fill_range (utype
, new_lb
, new_ub
);
2419 tmp_range
.union_ (fill_range
);
2422 range_cast (tmp_range
, type
);
2424 r
.intersect (tmp_range
);
2428 return !r
.varying_p ();
2432 operator_rshift::op1_range (irange
&r
,
2436 relation_trio
) const
2439 if (lhs
.undefined_p ())
2441 if (op2
.singleton_p (&shift
))
2443 // Ignore nonsensical shifts.
2444 unsigned prec
= TYPE_PRECISION (type
);
2445 if (wi::ge_p (wi::to_wide (shift
),
2446 wi::uhwi (prec
, TYPE_PRECISION (TREE_TYPE (shift
))),
2449 if (wi::to_wide (shift
) == 0)
2455 // Folding the original operation may discard some impossible
2456 // ranges from the LHS.
2457 int_range_max lhs_refined
;
2458 op_rshift
.fold_range (lhs_refined
, type
, int_range
<1> (type
), op2
);
2459 lhs_refined
.intersect (lhs
);
2460 if (lhs_refined
.undefined_p ())
2465 int_range_max
shift_range (shift
, shift
);
2466 int_range_max lb
, ub
;
2467 op_lshift
.fold_range (lb
, type
, lhs_refined
, shift_range
);
2469 // 0000 0111 = OP1 >> 3
2471 // OP1 is anything from 0011 1000 to 0011 1111. That is, a
2472 // range from LHS<<3 plus a mask of the 3 bits we shifted on the
2473 // right hand side (0x07).
2474 tree mask
= fold_build1 (BIT_NOT_EXPR
, type
,
2475 fold_build2 (LSHIFT_EXPR
, type
,
2476 build_minus_one_cst (type
),
2478 int_range_max
mask_range (build_zero_cst (type
), mask
);
2479 op_plus
.fold_range (ub
, type
, lb
, mask_range
);
2482 if (!lhs_refined
.contains_p (build_zero_cst (type
)))
2484 mask_range
.invert ();
2485 r
.intersect (mask_range
);
2493 operator_rshift::wi_op_overflows (wide_int
&res
,
2496 const wide_int
&w1
) const
2498 signop sign
= TYPE_SIGN (type
);
2500 res
= wi::lshift (w0
, -w1
);
2503 // It's unclear from the C standard whether shifts can overflow.
2504 // The following code ignores overflow; perhaps a C standard
2505 // interpretation ruling is needed.
2506 res
= wi::rshift (w0
, w1
, sign
);
2512 operator_rshift::fold_range (irange
&r
, tree type
,
2515 relation_trio rel
) const
2517 int_range_max shift
;
2518 if (!get_shift_range (shift
, type
, op2
))
2520 if (op2
.undefined_p ())
2527 return range_operator::fold_range (r
, type
, op1
, shift
, rel
);
2531 operator_rshift::wi_fold (irange
&r
, tree type
,
2532 const wide_int
&lh_lb
, const wide_int
&lh_ub
,
2533 const wide_int
&rh_lb
, const wide_int
&rh_ub
) const
2535 wi_cross_product (r
, type
, lh_lb
, lh_ub
, rh_lb
, rh_ub
);
2539 class operator_cast
: public range_operator
2541 using range_operator::fold_range
;
2542 using range_operator::op1_range
;
2544 virtual bool fold_range (irange
&r
, tree type
,
2547 relation_trio rel
= TRIO_VARYING
) const;
2548 virtual bool op1_range (irange
&r
, tree type
,
2551 relation_trio rel
= TRIO_VARYING
) const;
2552 virtual relation_kind
lhs_op1_relation (const irange
&lhs
,
2555 relation_kind
) const;
2557 bool truncating_cast_p (const irange
&inner
, const irange
&outer
) const;
2558 bool inside_domain_p (const wide_int
&min
, const wide_int
&max
,
2559 const irange
&outer
) const;
2560 void fold_pair (irange
&r
, unsigned index
, const irange
&inner
,
2561 const irange
&outer
) const;
2564 // Add a partial equivalence between the LHS and op1 for casts.
2567 operator_cast::lhs_op1_relation (const irange
&lhs
,
2569 const irange
&op2 ATTRIBUTE_UNUSED
,
2570 relation_kind
) const
2572 if (lhs
.undefined_p () || op1
.undefined_p ())
2573 return VREL_VARYING
;
2574 unsigned lhs_prec
= TYPE_PRECISION (lhs
.type ());
2575 unsigned op1_prec
= TYPE_PRECISION (op1
.type ());
2576 // If the result gets sign extended into a larger type check first if this
2577 // qualifies as a partial equivalence.
2578 if (TYPE_SIGN (op1
.type ()) == SIGNED
&& lhs_prec
> op1_prec
)
2580 // If the result is sign extended, and the LHS is larger than op1,
2581 // check if op1's range can be negative as the sign extention will
2582 // cause the upper bits to be 1 instead of 0, invalidating the PE.
2583 int_range
<3> negs
= range_negatives (op1
.type ());
2584 negs
.intersect (op1
);
2585 if (!negs
.undefined_p ())
2586 return VREL_VARYING
;
2589 unsigned prec
= MIN (lhs_prec
, op1_prec
);
2590 return bits_to_pe (prec
);
2593 // Return TRUE if casting from INNER to OUTER is a truncating cast.
2596 operator_cast::truncating_cast_p (const irange
&inner
,
2597 const irange
&outer
) const
2599 return TYPE_PRECISION (outer
.type ()) < TYPE_PRECISION (inner
.type ());
2602 // Return TRUE if [MIN,MAX] is inside the domain of RANGE's type.
2605 operator_cast::inside_domain_p (const wide_int
&min
,
2606 const wide_int
&max
,
2607 const irange
&range
) const
2609 wide_int domain_min
= wi::to_wide (vrp_val_min (range
.type ()));
2610 wide_int domain_max
= wi::to_wide (vrp_val_max (range
.type ()));
2611 signop domain_sign
= TYPE_SIGN (range
.type ());
2612 return (wi::le_p (min
, domain_max
, domain_sign
)
2613 && wi::le_p (max
, domain_max
, domain_sign
)
2614 && wi::ge_p (min
, domain_min
, domain_sign
)
2615 && wi::ge_p (max
, domain_min
, domain_sign
));
2619 // Helper for fold_range which work on a pair at a time.
2622 operator_cast::fold_pair (irange
&r
, unsigned index
,
2623 const irange
&inner
,
2624 const irange
&outer
) const
2626 tree inner_type
= inner
.type ();
2627 tree outer_type
= outer
.type ();
2628 signop inner_sign
= TYPE_SIGN (inner_type
);
2629 unsigned outer_prec
= TYPE_PRECISION (outer_type
);
2631 // check to see if casting from INNER to OUTER is a conversion that
2632 // fits in the resulting OUTER type.
2633 wide_int inner_lb
= inner
.lower_bound (index
);
2634 wide_int inner_ub
= inner
.upper_bound (index
);
2635 if (truncating_cast_p (inner
, outer
))
2637 // We may be able to accomodate a truncating cast if the
2638 // resulting range can be represented in the target type...
2639 if (wi::rshift (wi::sub (inner_ub
, inner_lb
),
2640 wi::uhwi (outer_prec
, TYPE_PRECISION (inner
.type ())),
2643 r
.set_varying (outer_type
);
2647 // ...but we must still verify that the final range fits in the
2648 // domain. This catches -fstrict-enum restrictions where the domain
2649 // range is smaller than what fits in the underlying type.
2650 wide_int min
= wide_int::from (inner_lb
, outer_prec
, inner_sign
);
2651 wide_int max
= wide_int::from (inner_ub
, outer_prec
, inner_sign
);
2652 if (inside_domain_p (min
, max
, outer
))
2653 create_possibly_reversed_range (r
, outer_type
, min
, max
);
2655 r
.set_varying (outer_type
);
2660 operator_cast::fold_range (irange
&r
, tree type ATTRIBUTE_UNUSED
,
2661 const irange
&inner
,
2662 const irange
&outer
,
2663 relation_trio
) const
2665 if (empty_range_varying (r
, type
, inner
, outer
))
2668 gcc_checking_assert (outer
.varying_p ());
2669 gcc_checking_assert (inner
.num_pairs () > 0);
2671 // Avoid a temporary by folding the first pair directly into the result.
2672 fold_pair (r
, 0, inner
, outer
);
2674 // Then process any additonal pairs by unioning with their results.
2675 for (unsigned x
= 1; x
< inner
.num_pairs (); ++x
)
2678 fold_pair (tmp
, x
, inner
, outer
);
2684 // Update the nonzero mask. Truncating casts are problematic unless
2685 // the conversion fits in the resulting outer type.
2686 wide_int nz
= inner
.get_nonzero_bits ();
2687 if (truncating_cast_p (inner
, outer
)
2688 && wi::rshift (nz
, wi::uhwi (TYPE_PRECISION (outer
.type ()),
2689 TYPE_PRECISION (inner
.type ())),
2690 TYPE_SIGN (inner
.type ())) != 0)
2692 nz
= wide_int::from (nz
, TYPE_PRECISION (type
), TYPE_SIGN (inner
.type ()));
2693 r
.set_nonzero_bits (nz
);
2699 operator_cast::op1_range (irange
&r
, tree type
,
2702 relation_trio
) const
2704 if (lhs
.undefined_p ())
2706 tree lhs_type
= lhs
.type ();
2707 gcc_checking_assert (types_compatible_p (op2
.type(), type
));
2709 // If we are calculating a pointer, shortcut to what we really care about.
2710 if (POINTER_TYPE_P (type
))
2712 // Conversion from other pointers or a constant (including 0/NULL)
2713 // are straightforward.
2714 if (POINTER_TYPE_P (lhs
.type ())
2715 || (lhs
.singleton_p ()
2716 && TYPE_PRECISION (lhs
.type ()) >= TYPE_PRECISION (type
)))
2719 range_cast (r
, type
);
2723 // If the LHS is not a pointer nor a singleton, then it is
2724 // either VARYING or non-zero.
2725 if (!lhs
.contains_p (build_zero_cst (lhs
.type ())))
2726 r
.set_nonzero (type
);
2728 r
.set_varying (type
);
2734 if (truncating_cast_p (op2
, lhs
))
2736 if (lhs
.varying_p ())
2737 r
.set_varying (type
);
2740 // We want to insert the LHS as an unsigned value since it
2741 // would not trigger the signed bit of the larger type.
2742 int_range_max converted_lhs
= lhs
;
2743 range_cast (converted_lhs
, unsigned_type_for (lhs_type
));
2744 range_cast (converted_lhs
, type
);
2745 // Start by building the positive signed outer range for the type.
2746 wide_int lim
= wi::set_bit_in_zero (TYPE_PRECISION (lhs_type
),
2747 TYPE_PRECISION (type
));
2748 r
= int_range
<1> (type
, lim
, wi::max_value (TYPE_PRECISION (type
),
2750 // For the signed part, we need to simply union the 2 ranges now.
2751 r
.union_ (converted_lhs
);
2753 // Create maximal negative number outside of LHS bits.
2754 lim
= wi::mask (TYPE_PRECISION (lhs_type
), true,
2755 TYPE_PRECISION (type
));
2756 // Add this to the unsigned LHS range(s).
2757 int_range_max
lim_range (type
, lim
, lim
);
2758 int_range_max lhs_neg
;
2759 range_op_handler (PLUS_EXPR
, type
).fold_range (lhs_neg
, type
,
2762 // lhs_neg now has all the negative versions of the LHS.
2763 // Now union in all the values from SIGNED MIN (0x80000) to
2764 // lim-1 in order to fill in all the ranges with the upper
2767 // PR 97317. If the lhs has only 1 bit less precision than the rhs,
2768 // we don't need to create a range from min to lim-1
2769 // calculate neg range traps trying to create [lim, lim - 1].
2770 wide_int min_val
= wi::min_value (TYPE_PRECISION (type
), SIGNED
);
2773 int_range_max
neg (type
,
2774 wi::min_value (TYPE_PRECISION (type
),
2777 lhs_neg
.union_ (neg
);
2779 // And finally, munge the signed and unsigned portions.
2782 // And intersect with any known value passed in the extra operand.
2788 if (TYPE_PRECISION (lhs_type
) == TYPE_PRECISION (type
))
2792 // The cast is not truncating, and the range is restricted to
2793 // the range of the RHS by this assignment.
2795 // Cast the range of the RHS to the type of the LHS.
2796 fold_range (tmp
, lhs_type
, int_range
<1> (type
), int_range
<1> (lhs_type
));
2797 // Intersect this with the LHS range will produce the range,
2798 // which will be cast to the RHS type before returning.
2799 tmp
.intersect (lhs
);
2802 // Cast the calculated range to the type of the RHS.
2803 fold_range (r
, type
, tmp
, int_range
<1> (type
));
2808 class operator_logical_and
: public range_operator
2810 using range_operator::fold_range
;
2811 using range_operator::op1_range
;
2812 using range_operator::op2_range
;
2814 virtual bool fold_range (irange
&r
, tree type
,
2817 relation_trio rel
= TRIO_VARYING
) const;
2818 virtual bool op1_range (irange
&r
, tree type
,
2821 relation_trio rel
= TRIO_VARYING
) const;
2822 virtual bool op2_range (irange
&r
, tree type
,
2825 relation_trio rel
= TRIO_VARYING
) const;
2830 operator_logical_and::fold_range (irange
&r
, tree type
,
2833 relation_trio
) const
2835 if (empty_range_varying (r
, type
, lh
, rh
))
2838 // 0 && anything is 0.
2839 if ((wi::eq_p (lh
.lower_bound (), 0) && wi::eq_p (lh
.upper_bound (), 0))
2840 || (wi::eq_p (lh
.lower_bound (), 0) && wi::eq_p (rh
.upper_bound (), 0)))
2841 r
= range_false (type
);
2842 else if (lh
.contains_p (build_zero_cst (lh
.type ()))
2843 || rh
.contains_p (build_zero_cst (rh
.type ())))
2844 // To reach this point, there must be a logical 1 on each side, and
2845 // the only remaining question is whether there is a zero or not.
2846 r
= range_true_and_false (type
);
2848 r
= range_true (type
);
2853 operator_logical_and::op1_range (irange
&r
, tree type
,
2855 const irange
&op2 ATTRIBUTE_UNUSED
,
2856 relation_trio
) const
2858 switch (get_bool_state (r
, lhs
, type
))
2861 // A true result means both sides of the AND must be true.
2862 r
= range_true (type
);
2865 // Any other result means only one side has to be false, the
2866 // other side can be anything. So we cannot be sure of any
2868 r
= range_true_and_false (type
);
2875 operator_logical_and::op2_range (irange
&r
, tree type
,
2878 relation_trio
) const
2880 return operator_logical_and::op1_range (r
, type
, lhs
, op1
);
2884 class operator_bitwise_and
: public range_operator
2886 using range_operator::op1_range
;
2887 using range_operator::op2_range
;
2889 virtual bool op1_range (irange
&r
, tree type
,
2892 relation_trio rel
= TRIO_VARYING
) const;
2893 virtual bool op2_range (irange
&r
, tree type
,
2896 relation_trio rel
= TRIO_VARYING
) const;
2897 virtual void wi_fold (irange
&r
, tree type
,
2898 const wide_int
&lh_lb
,
2899 const wide_int
&lh_ub
,
2900 const wide_int
&rh_lb
,
2901 const wide_int
&rh_ub
) const;
2902 virtual relation_kind
lhs_op1_relation (const irange
&lhs
,
2905 relation_kind
) const;
2907 void simple_op1_range_solver (irange
&r
, tree type
,
2909 const irange
&op2
) const;
2913 // Optimize BIT_AND_EXPR, BIT_IOR_EXPR and BIT_XOR_EXPR of signed types
2914 // by considering the number of leading redundant sign bit copies.
2915 // clrsb (X op Y) = min (clrsb (X), clrsb (Y)), so for example
2916 // [-1, 0] op [-1, 0] is [-1, 0] (where nonzero_bits doesn't help).
2918 wi_optimize_signed_bitwise_op (irange
&r
, tree type
,
2919 const wide_int
&lh_lb
, const wide_int
&lh_ub
,
2920 const wide_int
&rh_lb
, const wide_int
&rh_ub
)
2922 int lh_clrsb
= MIN (wi::clrsb (lh_lb
), wi::clrsb (lh_ub
));
2923 int rh_clrsb
= MIN (wi::clrsb (rh_lb
), wi::clrsb (rh_ub
));
2924 int new_clrsb
= MIN (lh_clrsb
, rh_clrsb
);
2927 int type_prec
= TYPE_PRECISION (type
);
2928 int rprec
= (type_prec
- new_clrsb
) - 1;
2929 value_range_with_overflow (r
, type
,
2930 wi::mask (rprec
, true, type_prec
),
2931 wi::mask (rprec
, false, type_prec
));
2935 // An AND of 8,16, 32 or 64 bits can produce a partial equivalence between
2939 operator_bitwise_and::lhs_op1_relation (const irange
&lhs
,
2942 relation_kind
) const
2944 if (lhs
.undefined_p () || op1
.undefined_p () || op2
.undefined_p ())
2945 return VREL_VARYING
;
2946 if (!op2
.singleton_p ())
2947 return VREL_VARYING
;
2948 // if val == 0xff or 0xFFFF OR 0Xffffffff OR 0Xffffffffffffffff, return TRUE
2949 int prec1
= TYPE_PRECISION (op1
.type ());
2950 int prec2
= TYPE_PRECISION (op2
.type ());
2952 wide_int mask
= op2
.lower_bound ();
2953 if (wi::eq_p (mask
, wi::mask (8, false, prec2
)))
2955 else if (wi::eq_p (mask
, wi::mask (16, false, prec2
)))
2957 else if (wi::eq_p (mask
, wi::mask (32, false, prec2
)))
2959 else if (wi::eq_p (mask
, wi::mask (64, false, prec2
)))
2961 return bits_to_pe (MIN (prec1
, mask_prec
));
2964 // Optimize BIT_AND_EXPR and BIT_IOR_EXPR in terms of a mask if
2965 // possible. Basically, see if we can optimize:
2969 // [LB op Z, UB op Z]
2971 // If the optimization was successful, accumulate the range in R and
2975 wi_optimize_and_or (irange
&r
,
2976 enum tree_code code
,
2978 const wide_int
&lh_lb
, const wide_int
&lh_ub
,
2979 const wide_int
&rh_lb
, const wide_int
&rh_ub
)
2981 // Calculate the singleton mask among the ranges, if any.
2982 wide_int lower_bound
, upper_bound
, mask
;
2983 if (wi::eq_p (rh_lb
, rh_ub
))
2986 lower_bound
= lh_lb
;
2987 upper_bound
= lh_ub
;
2989 else if (wi::eq_p (lh_lb
, lh_ub
))
2992 lower_bound
= rh_lb
;
2993 upper_bound
= rh_ub
;
2998 // If Z is a constant which (for op | its bitwise not) has n
2999 // consecutive least significant bits cleared followed by m 1
3000 // consecutive bits set immediately above it and either
3001 // m + n == precision, or (x >> (m + n)) == (y >> (m + n)).
3003 // The least significant n bits of all the values in the range are
3004 // cleared or set, the m bits above it are preserved and any bits
3005 // above these are required to be the same for all values in the
3009 if (code
== BIT_IOR_EXPR
)
3011 if (wi::eq_p (w
, 0))
3012 n
= w
.get_precision ();
3016 w
= ~(w
| wi::mask (n
, false, w
.get_precision ()));
3017 if (wi::eq_p (w
, 0))
3018 m
= w
.get_precision () - n
;
3020 m
= wi::ctz (w
) - n
;
3022 wide_int new_mask
= wi::mask (m
+ n
, true, w
.get_precision ());
3023 if ((new_mask
& lower_bound
) != (new_mask
& upper_bound
))
3026 wide_int res_lb
, res_ub
;
3027 if (code
== BIT_AND_EXPR
)
3029 res_lb
= wi::bit_and (lower_bound
, mask
);
3030 res_ub
= wi::bit_and (upper_bound
, mask
);
3032 else if (code
== BIT_IOR_EXPR
)
3034 res_lb
= wi::bit_or (lower_bound
, mask
);
3035 res_ub
= wi::bit_or (upper_bound
, mask
);
3039 value_range_with_overflow (r
, type
, res_lb
, res_ub
);
3041 // Furthermore, if the mask is non-zero, an IOR cannot contain zero.
3042 if (code
== BIT_IOR_EXPR
&& wi::ne_p (mask
, 0))
3045 tmp
.set_nonzero (type
);
3051 // For range [LB, UB] compute two wide_int bit masks.
3053 // In the MAYBE_NONZERO bit mask, if some bit is unset, it means that
3054 // for all numbers in the range the bit is 0, otherwise it might be 0
3057 // In the MUSTBE_NONZERO bit mask, if some bit is set, it means that
3058 // for all numbers in the range the bit is 1, otherwise it might be 0
3062 wi_set_zero_nonzero_bits (tree type
,
3063 const wide_int
&lb
, const wide_int
&ub
,
3064 wide_int
&maybe_nonzero
,
3065 wide_int
&mustbe_nonzero
)
3067 signop sign
= TYPE_SIGN (type
);
3069 if (wi::eq_p (lb
, ub
))
3070 maybe_nonzero
= mustbe_nonzero
= lb
;
3071 else if (wi::ge_p (lb
, 0, sign
) || wi::lt_p (ub
, 0, sign
))
3073 wide_int xor_mask
= lb
^ ub
;
3074 maybe_nonzero
= lb
| ub
;
3075 mustbe_nonzero
= lb
& ub
;
3078 wide_int mask
= wi::mask (wi::floor_log2 (xor_mask
), false,
3079 maybe_nonzero
.get_precision ());
3080 maybe_nonzero
= maybe_nonzero
| mask
;
3081 mustbe_nonzero
= wi::bit_and_not (mustbe_nonzero
, mask
);
3086 maybe_nonzero
= wi::minus_one (lb
.get_precision ());
3087 mustbe_nonzero
= wi::zero (lb
.get_precision ());
3092 operator_bitwise_and::wi_fold (irange
&r
, tree type
,
3093 const wide_int
&lh_lb
,
3094 const wide_int
&lh_ub
,
3095 const wide_int
&rh_lb
,
3096 const wide_int
&rh_ub
) const
3098 if (wi_optimize_and_or (r
, BIT_AND_EXPR
, type
, lh_lb
, lh_ub
, rh_lb
, rh_ub
))
3101 wide_int maybe_nonzero_lh
, mustbe_nonzero_lh
;
3102 wide_int maybe_nonzero_rh
, mustbe_nonzero_rh
;
3103 wi_set_zero_nonzero_bits (type
, lh_lb
, lh_ub
,
3104 maybe_nonzero_lh
, mustbe_nonzero_lh
);
3105 wi_set_zero_nonzero_bits (type
, rh_lb
, rh_ub
,
3106 maybe_nonzero_rh
, mustbe_nonzero_rh
);
3108 wide_int new_lb
= mustbe_nonzero_lh
& mustbe_nonzero_rh
;
3109 wide_int new_ub
= maybe_nonzero_lh
& maybe_nonzero_rh
;
3110 signop sign
= TYPE_SIGN (type
);
3111 unsigned prec
= TYPE_PRECISION (type
);
3112 // If both input ranges contain only negative values, we can
3113 // truncate the result range maximum to the minimum of the
3114 // input range maxima.
3115 if (wi::lt_p (lh_ub
, 0, sign
) && wi::lt_p (rh_ub
, 0, sign
))
3117 new_ub
= wi::min (new_ub
, lh_ub
, sign
);
3118 new_ub
= wi::min (new_ub
, rh_ub
, sign
);
3120 // If either input range contains only non-negative values
3121 // we can truncate the result range maximum to the respective
3122 // maximum of the input range.
3123 if (wi::ge_p (lh_lb
, 0, sign
))
3124 new_ub
= wi::min (new_ub
, lh_ub
, sign
);
3125 if (wi::ge_p (rh_lb
, 0, sign
))
3126 new_ub
= wi::min (new_ub
, rh_ub
, sign
);
3127 // PR68217: In case of signed & sign-bit-CST should
3128 // result in [-INF, 0] instead of [-INF, INF].
3129 if (wi::gt_p (new_lb
, new_ub
, sign
))
3131 wide_int sign_bit
= wi::set_bit_in_zero (prec
- 1, prec
);
3133 && ((wi::eq_p (lh_lb
, lh_ub
)
3134 && !wi::cmps (lh_lb
, sign_bit
))
3135 || (wi::eq_p (rh_lb
, rh_ub
)
3136 && !wi::cmps (rh_lb
, sign_bit
))))
3138 new_lb
= wi::min_value (prec
, sign
);
3139 new_ub
= wi::zero (prec
);
3142 // If the limits got swapped around, return varying.
3143 if (wi::gt_p (new_lb
, new_ub
,sign
))
3146 && wi_optimize_signed_bitwise_op (r
, type
,
3150 r
.set_varying (type
);
3153 value_range_with_overflow (r
, type
, new_lb
, new_ub
);
3157 set_nonzero_range_from_mask (irange
&r
, tree type
, const irange
&lhs
)
3159 if (!lhs
.contains_p (build_zero_cst (type
)))
3160 r
= range_nonzero (type
);
3162 r
.set_varying (type
);
3165 /* Find out smallest RES where RES > VAL && (RES & MASK) == RES, if any
3166 (otherwise return VAL). VAL and MASK must be zero-extended for
3167 precision PREC. If SGNBIT is non-zero, first xor VAL with SGNBIT
3168 (to transform signed values into unsigned) and at the end xor
3172 masked_increment (const wide_int
&val_in
, const wide_int
&mask
,
3173 const wide_int
&sgnbit
, unsigned int prec
)
3175 wide_int bit
= wi::one (prec
), res
;
3178 wide_int val
= val_in
^ sgnbit
;
3179 for (i
= 0; i
< prec
; i
++, bit
+= bit
)
3182 if ((res
& bit
) == 0)
3185 res
= wi::bit_and_not (val
+ bit
, res
);
3187 if (wi::gtu_p (res
, val
))
3188 return res
^ sgnbit
;
3190 return val
^ sgnbit
;
3193 // This was shamelessly stolen from register_edge_assert_for_2 and
3194 // adjusted to work with iranges.
3197 operator_bitwise_and::simple_op1_range_solver (irange
&r
, tree type
,
3199 const irange
&op2
) const
3201 if (!op2
.singleton_p ())
3203 set_nonzero_range_from_mask (r
, type
, lhs
);
3206 unsigned int nprec
= TYPE_PRECISION (type
);
3207 wide_int cst2v
= op2
.lower_bound ();
3208 bool cst2n
= wi::neg_p (cst2v
, TYPE_SIGN (type
));
3211 sgnbit
= wi::set_bit_in_zero (nprec
- 1, nprec
);
3213 sgnbit
= wi::zero (nprec
);
3215 // Solve [lhs.lower_bound (), +INF] = x & MASK.
3217 // Minimum unsigned value for >= if (VAL & CST2) == VAL is VAL and
3218 // maximum unsigned value is ~0. For signed comparison, if CST2
3219 // doesn't have the most significant bit set, handle it similarly. If
3220 // CST2 has MSB set, the minimum is the same, and maximum is ~0U/2.
3221 wide_int valv
= lhs
.lower_bound ();
3222 wide_int minv
= valv
& cst2v
, maxv
;
3223 bool we_know_nothing
= false;
3226 // If (VAL & CST2) != VAL, X & CST2 can't be equal to VAL.
3227 minv
= masked_increment (valv
, cst2v
, sgnbit
, nprec
);
3230 // If we can't determine anything on this bound, fall
3231 // through and conservatively solve for the other end point.
3232 we_know_nothing
= true;
3235 maxv
= wi::mask (nprec
- (cst2n
? 1 : 0), false, nprec
);
3236 if (we_know_nothing
)
3237 r
.set_varying (type
);
3239 r
= int_range
<1> (type
, minv
, maxv
);
3241 // Solve [-INF, lhs.upper_bound ()] = x & MASK.
3243 // Minimum unsigned value for <= is 0 and maximum unsigned value is
3244 // VAL | ~CST2 if (VAL & CST2) == VAL. Otherwise, find smallest
3246 // VAL2 > VAL && (VAL2 & CST2) == VAL2 and use (VAL2 - 1) | ~CST2
3248 // For signed comparison, if CST2 doesn't have most significant bit
3249 // set, handle it similarly. If CST2 has MSB set, the maximum is
3250 // the same and minimum is INT_MIN.
3251 valv
= lhs
.upper_bound ();
3252 minv
= valv
& cst2v
;
3257 maxv
= masked_increment (valv
, cst2v
, sgnbit
, nprec
);
3260 // If we couldn't determine anything on either bound, return
3262 if (we_know_nothing
)
3270 int_range
<1> upper_bits (type
, minv
, maxv
);
3271 r
.intersect (upper_bits
);
3275 operator_bitwise_and::op1_range (irange
&r
, tree type
,
3278 relation_trio
) const
3280 if (lhs
.undefined_p ())
3282 if (types_compatible_p (type
, boolean_type_node
))
3283 return op_logical_and
.op1_range (r
, type
, lhs
, op2
);
3286 for (unsigned i
= 0; i
< lhs
.num_pairs (); ++i
)
3288 int_range_max
chunk (lhs
.type (),
3289 lhs
.lower_bound (i
),
3290 lhs
.upper_bound (i
));
3292 simple_op1_range_solver (res
, type
, chunk
, op2
);
3295 if (r
.undefined_p ())
3296 set_nonzero_range_from_mask (r
, type
, lhs
);
3298 // For 0 = op1 & MASK, op1 is ~MASK.
3299 if (lhs
.zero_p () && op2
.singleton_p ())
3301 wide_int nz
= wi::bit_not (op2
.get_nonzero_bits ());
3302 int_range
<2> tmp (type
);
3303 tmp
.set_nonzero_bits (nz
);
3310 operator_bitwise_and::op2_range (irange
&r
, tree type
,
3313 relation_trio
) const
3315 return operator_bitwise_and::op1_range (r
, type
, lhs
, op1
);
3319 class operator_logical_or
: public range_operator
3321 using range_operator::fold_range
;
3322 using range_operator::op1_range
;
3323 using range_operator::op2_range
;
3325 virtual bool fold_range (irange
&r
, tree type
,
3328 relation_trio rel
= TRIO_VARYING
) const;
3329 virtual bool op1_range (irange
&r
, tree type
,
3332 relation_trio rel
= TRIO_VARYING
) const;
3333 virtual bool op2_range (irange
&r
, tree type
,
3336 relation_trio rel
= TRIO_VARYING
) const;
3340 operator_logical_or::fold_range (irange
&r
, tree type ATTRIBUTE_UNUSED
,
3343 relation_trio
) const
3345 if (empty_range_varying (r
, type
, lh
, rh
))
3354 operator_logical_or::op1_range (irange
&r
, tree type
,
3356 const irange
&op2 ATTRIBUTE_UNUSED
,
3357 relation_trio
) const
3359 switch (get_bool_state (r
, lhs
, type
))
3362 // A false result means both sides of the OR must be false.
3363 r
= range_false (type
);
3366 // Any other result means only one side has to be true, the
3367 // other side can be anything. so we can't be sure of any result
3369 r
= range_true_and_false (type
);
3376 operator_logical_or::op2_range (irange
&r
, tree type
,
3379 relation_trio
) const
3381 return operator_logical_or::op1_range (r
, type
, lhs
, op1
);
3385 class operator_bitwise_or
: public range_operator
3387 using range_operator::op1_range
;
3388 using range_operator::op2_range
;
3390 virtual bool op1_range (irange
&r
, tree type
,
3393 relation_trio rel
= TRIO_VARYING
) const;
3394 virtual bool op2_range (irange
&r
, tree type
,
3397 relation_trio rel
= TRIO_VARYING
) const;
3398 virtual void wi_fold (irange
&r
, tree type
,
3399 const wide_int
&lh_lb
,
3400 const wide_int
&lh_ub
,
3401 const wide_int
&rh_lb
,
3402 const wide_int
&rh_ub
) const;
3406 operator_bitwise_or::wi_fold (irange
&r
, tree type
,
3407 const wide_int
&lh_lb
,
3408 const wide_int
&lh_ub
,
3409 const wide_int
&rh_lb
,
3410 const wide_int
&rh_ub
) const
3412 if (wi_optimize_and_or (r
, BIT_IOR_EXPR
, type
, lh_lb
, lh_ub
, rh_lb
, rh_ub
))
3415 wide_int maybe_nonzero_lh
, mustbe_nonzero_lh
;
3416 wide_int maybe_nonzero_rh
, mustbe_nonzero_rh
;
3417 wi_set_zero_nonzero_bits (type
, lh_lb
, lh_ub
,
3418 maybe_nonzero_lh
, mustbe_nonzero_lh
);
3419 wi_set_zero_nonzero_bits (type
, rh_lb
, rh_ub
,
3420 maybe_nonzero_rh
, mustbe_nonzero_rh
);
3421 wide_int new_lb
= mustbe_nonzero_lh
| mustbe_nonzero_rh
;
3422 wide_int new_ub
= maybe_nonzero_lh
| maybe_nonzero_rh
;
3423 signop sign
= TYPE_SIGN (type
);
3424 // If the input ranges contain only positive values we can
3425 // truncate the minimum of the result range to the maximum
3426 // of the input range minima.
3427 if (wi::ge_p (lh_lb
, 0, sign
)
3428 && wi::ge_p (rh_lb
, 0, sign
))
3430 new_lb
= wi::max (new_lb
, lh_lb
, sign
);
3431 new_lb
= wi::max (new_lb
, rh_lb
, sign
);
3433 // If either input range contains only negative values
3434 // we can truncate the minimum of the result range to the
3435 // respective minimum range.
3436 if (wi::lt_p (lh_ub
, 0, sign
))
3437 new_lb
= wi::max (new_lb
, lh_lb
, sign
);
3438 if (wi::lt_p (rh_ub
, 0, sign
))
3439 new_lb
= wi::max (new_lb
, rh_lb
, sign
);
3440 // If the limits got swapped around, return a conservative range.
3441 if (wi::gt_p (new_lb
, new_ub
, sign
))
3443 // Make sure that nonzero|X is nonzero.
3444 if (wi::gt_p (lh_lb
, 0, sign
)
3445 || wi::gt_p (rh_lb
, 0, sign
)
3446 || wi::lt_p (lh_ub
, 0, sign
)
3447 || wi::lt_p (rh_ub
, 0, sign
))
3448 r
.set_nonzero (type
);
3449 else if (sign
== SIGNED
3450 && wi_optimize_signed_bitwise_op (r
, type
,
3455 r
.set_varying (type
);
3458 value_range_with_overflow (r
, type
, new_lb
, new_ub
);
3462 operator_bitwise_or::op1_range (irange
&r
, tree type
,
3465 relation_trio
) const
3467 if (lhs
.undefined_p ())
3469 // If this is really a logical wi_fold, call that.
3470 if (types_compatible_p (type
, boolean_type_node
))
3471 return op_logical_or
.op1_range (r
, type
, lhs
, op2
);
3475 tree zero
= build_zero_cst (type
);
3476 r
= int_range
<1> (zero
, zero
);
3479 r
.set_varying (type
);
3484 operator_bitwise_or::op2_range (irange
&r
, tree type
,
3487 relation_trio
) const
3489 return operator_bitwise_or::op1_range (r
, type
, lhs
, op1
);
3493 class operator_bitwise_xor
: public range_operator
3495 using range_operator::op1_range
;
3496 using range_operator::op2_range
;
3498 virtual void wi_fold (irange
&r
, tree type
,
3499 const wide_int
&lh_lb
,
3500 const wide_int
&lh_ub
,
3501 const wide_int
&rh_lb
,
3502 const wide_int
&rh_ub
) const;
3503 virtual bool op1_range (irange
&r
, tree type
,
3506 relation_trio rel
= TRIO_VARYING
) const;
3507 virtual bool op2_range (irange
&r
, tree type
,
3510 relation_trio rel
= TRIO_VARYING
) const;
3511 virtual bool op1_op2_relation_effect (irange
&lhs_range
,
3513 const irange
&op1_range
,
3514 const irange
&op2_range
,
3515 relation_kind rel
) const;
3519 operator_bitwise_xor::wi_fold (irange
&r
, tree type
,
3520 const wide_int
&lh_lb
,
3521 const wide_int
&lh_ub
,
3522 const wide_int
&rh_lb
,
3523 const wide_int
&rh_ub
) const
3525 signop sign
= TYPE_SIGN (type
);
3526 wide_int maybe_nonzero_lh
, mustbe_nonzero_lh
;
3527 wide_int maybe_nonzero_rh
, mustbe_nonzero_rh
;
3528 wi_set_zero_nonzero_bits (type
, lh_lb
, lh_ub
,
3529 maybe_nonzero_lh
, mustbe_nonzero_lh
);
3530 wi_set_zero_nonzero_bits (type
, rh_lb
, rh_ub
,
3531 maybe_nonzero_rh
, mustbe_nonzero_rh
);
3533 wide_int result_zero_bits
= ((mustbe_nonzero_lh
& mustbe_nonzero_rh
)
3534 | ~(maybe_nonzero_lh
| maybe_nonzero_rh
));
3535 wide_int result_one_bits
3536 = (wi::bit_and_not (mustbe_nonzero_lh
, maybe_nonzero_rh
)
3537 | wi::bit_and_not (mustbe_nonzero_rh
, maybe_nonzero_lh
));
3538 wide_int new_ub
= ~result_zero_bits
;
3539 wide_int new_lb
= result_one_bits
;
3541 // If the range has all positive or all negative values, the result
3542 // is better than VARYING.
3543 if (wi::lt_p (new_lb
, 0, sign
) || wi::ge_p (new_ub
, 0, sign
))
3544 value_range_with_overflow (r
, type
, new_lb
, new_ub
);
3545 else if (sign
== SIGNED
3546 && wi_optimize_signed_bitwise_op (r
, type
,
3551 r
.set_varying (type
);
3553 /* Furthermore, XOR is non-zero if its arguments can't be equal. */
3554 if (wi::lt_p (lh_ub
, rh_lb
, sign
)
3555 || wi::lt_p (rh_ub
, lh_lb
, sign
)
3556 || wi::ne_p (result_one_bits
, 0))
3559 tmp
.set_nonzero (type
);
3565 operator_bitwise_xor::op1_op2_relation_effect (irange
&lhs_range
,
3569 relation_kind rel
) const
3571 if (rel
== VREL_VARYING
)
3574 int_range
<2> rel_range
;
3579 rel_range
.set_zero (type
);
3582 rel_range
.set_nonzero (type
);
3588 lhs_range
.intersect (rel_range
);
3593 operator_bitwise_xor::op1_range (irange
&r
, tree type
,
3596 relation_trio
) const
3598 if (lhs
.undefined_p () || lhs
.varying_p ())
3603 if (types_compatible_p (type
, boolean_type_node
))
3605 switch (get_bool_state (r
, lhs
, type
))
3608 if (op2
.varying_p ())
3609 r
.set_varying (type
);
3610 else if (op2
.zero_p ())
3611 r
= range_true (type
);
3612 // See get_bool_state for the rationale
3613 else if (op2
.contains_p (build_zero_cst (op2
.type ())))
3614 r
= range_true_and_false (type
);
3616 r
= range_false (type
);
3626 r
.set_varying (type
);
3631 operator_bitwise_xor::op2_range (irange
&r
, tree type
,
3634 relation_trio
) const
3636 return operator_bitwise_xor::op1_range (r
, type
, lhs
, op1
);
3639 class operator_trunc_mod
: public range_operator
3641 using range_operator::op1_range
;
3642 using range_operator::op2_range
;
3644 virtual void wi_fold (irange
&r
, tree type
,
3645 const wide_int
&lh_lb
,
3646 const wide_int
&lh_ub
,
3647 const wide_int
&rh_lb
,
3648 const wide_int
&rh_ub
) const;
3649 virtual bool op1_range (irange
&r
, tree type
,
3652 relation_trio
) const;
3653 virtual bool op2_range (irange
&r
, tree type
,
3656 relation_trio
) const;
3660 operator_trunc_mod::wi_fold (irange
&r
, tree type
,
3661 const wide_int
&lh_lb
,
3662 const wide_int
&lh_ub
,
3663 const wide_int
&rh_lb
,
3664 const wide_int
&rh_ub
) const
3666 wide_int new_lb
, new_ub
, tmp
;
3667 signop sign
= TYPE_SIGN (type
);
3668 unsigned prec
= TYPE_PRECISION (type
);
3670 // Mod 0 is undefined.
3671 if (wi_zero_p (type
, rh_lb
, rh_ub
))
3677 // Check for constant and try to fold.
3678 if (lh_lb
== lh_ub
&& rh_lb
== rh_ub
)
3680 wi::overflow_type ov
= wi::OVF_NONE
;
3681 tmp
= wi::mod_trunc (lh_lb
, rh_lb
, sign
, &ov
);
3682 if (ov
== wi::OVF_NONE
)
3684 r
= int_range
<2> (type
, tmp
, tmp
);
3689 // ABS (A % B) < ABS (B) and either 0 <= A % B <= A or A <= A % B <= 0.
3694 new_ub
= wi::smax (new_ub
, tmp
);
3697 if (sign
== UNSIGNED
)
3698 new_lb
= wi::zero (prec
);
3703 if (wi::gts_p (tmp
, 0))
3704 tmp
= wi::zero (prec
);
3705 new_lb
= wi::smax (new_lb
, tmp
);
3708 if (sign
== SIGNED
&& wi::neg_p (tmp
))
3709 tmp
= wi::zero (prec
);
3710 new_ub
= wi::min (new_ub
, tmp
, sign
);
3712 value_range_with_overflow (r
, type
, new_lb
, new_ub
);
3716 operator_trunc_mod::op1_range (irange
&r
, tree type
,
3719 relation_trio
) const
3721 if (lhs
.undefined_p ())
3724 signop sign
= TYPE_SIGN (type
);
3725 unsigned prec
= TYPE_PRECISION (type
);
3726 // (a % b) >= x && x > 0 , then a >= x.
3727 if (wi::gt_p (lhs
.lower_bound (), 0, sign
))
3729 r
= value_range (type
, lhs
.lower_bound (), wi::max_value (prec
, sign
));
3732 // (a % b) <= x && x < 0 , then a <= x.
3733 if (wi::lt_p (lhs
.upper_bound (), 0, sign
))
3735 r
= value_range (type
, wi::min_value (prec
, sign
), lhs
.upper_bound ());
3742 operator_trunc_mod::op2_range (irange
&r
, tree type
,
3745 relation_trio
) const
3747 if (lhs
.undefined_p ())
3750 signop sign
= TYPE_SIGN (type
);
3751 unsigned prec
= TYPE_PRECISION (type
);
3752 // (a % b) >= x && x > 0 , then b is in ~[-x, x] for signed
3753 // or b > x for unsigned.
3754 if (wi::gt_p (lhs
.lower_bound (), 0, sign
))
3757 r
= value_range (type
, wi::neg (lhs
.lower_bound ()),
3758 lhs
.lower_bound (), VR_ANTI_RANGE
);
3759 else if (wi::lt_p (lhs
.lower_bound (), wi::max_value (prec
, sign
),
3761 r
= value_range (type
, lhs
.lower_bound () + 1,
3762 wi::max_value (prec
, sign
));
3767 // (a % b) <= x && x < 0 , then b is in ~[x, -x].
3768 if (wi::lt_p (lhs
.upper_bound (), 0, sign
))
3770 if (wi::gt_p (lhs
.upper_bound (), wi::min_value (prec
, sign
), sign
))
3771 r
= value_range (type
, lhs
.upper_bound (),
3772 wi::neg (lhs
.upper_bound ()), VR_ANTI_RANGE
);
3781 class operator_logical_not
: public range_operator
3783 using range_operator::fold_range
;
3784 using range_operator::op1_range
;
3786 virtual bool fold_range (irange
&r
, tree type
,
3789 relation_trio rel
= TRIO_VARYING
) const;
3790 virtual bool op1_range (irange
&r
, tree type
,
3793 relation_trio rel
= TRIO_VARYING
) const;
3796 // Folding a logical NOT, oddly enough, involves doing nothing on the
3797 // forward pass through. During the initial walk backwards, the
3798 // logical NOT reversed the desired outcome on the way back, so on the
3799 // way forward all we do is pass the range forward.
3804 // to determine the TRUE branch, walking backward
3805 // if (b_3) if ([1,1])
3806 // b_3 = !b_2 [1,1] = ![0,0]
3807 // b_2 = x_1 < 20 [0,0] = x_1 < 20, false, so x_1 == [20, 255]
3808 // which is the result we are looking for.. so.. pass it through.
3811 operator_logical_not::fold_range (irange
&r
, tree type
,
3813 const irange
&rh ATTRIBUTE_UNUSED
,
3814 relation_trio
) const
3816 if (empty_range_varying (r
, type
, lh
, rh
))
3820 if (!lh
.varying_p () && !lh
.undefined_p ())
3827 operator_logical_not::op1_range (irange
&r
,
3831 relation_trio
) const
3833 // Logical NOT is involutary...do it again.
3834 return fold_range (r
, type
, lhs
, op2
);
3838 class operator_bitwise_not
: public range_operator
3840 using range_operator::fold_range
;
3841 using range_operator::op1_range
;
3843 virtual bool fold_range (irange
&r
, tree type
,
3846 relation_trio rel
= TRIO_VARYING
) const;
3847 virtual bool op1_range (irange
&r
, tree type
,
3850 relation_trio rel
= TRIO_VARYING
) const;
3854 operator_bitwise_not::fold_range (irange
&r
, tree type
,
3857 relation_trio
) const
3859 if (empty_range_varying (r
, type
, lh
, rh
))
3862 if (types_compatible_p (type
, boolean_type_node
))
3863 return op_logical_not
.fold_range (r
, type
, lh
, rh
);
3865 // ~X is simply -1 - X.
3866 int_range
<1> minusone (type
, wi::minus_one (TYPE_PRECISION (type
)),
3867 wi::minus_one (TYPE_PRECISION (type
)));
3868 return range_op_handler (MINUS_EXPR
, type
).fold_range (r
, type
, minusone
, lh
);
3872 operator_bitwise_not::op1_range (irange
&r
, tree type
,
3875 relation_trio
) const
3877 if (lhs
.undefined_p ())
3879 if (types_compatible_p (type
, boolean_type_node
))
3880 return op_logical_not
.op1_range (r
, type
, lhs
, op2
);
3882 // ~X is -1 - X and since bitwise NOT is involutary...do it again.
3883 return fold_range (r
, type
, lhs
, op2
);
3887 class operator_cst
: public range_operator
3889 using range_operator::fold_range
;
3891 virtual bool fold_range (irange
&r
, tree type
,
3894 relation_trio rel
= TRIO_VARYING
) const;
3898 operator_cst::fold_range (irange
&r
, tree type ATTRIBUTE_UNUSED
,
3900 const irange
&rh ATTRIBUTE_UNUSED
,
3901 relation_trio
) const
3908 class operator_identity
: public range_operator
3910 using range_operator::fold_range
;
3911 using range_operator::op1_range
;
3912 using range_operator::lhs_op1_relation
;
3914 virtual bool fold_range (irange
&r
, tree type
,
3917 relation_trio rel
= TRIO_VARYING
) const;
3918 virtual bool op1_range (irange
&r
, tree type
,
3921 relation_trio rel
= TRIO_VARYING
) const;
3922 virtual relation_kind
lhs_op1_relation (const irange
&lhs
,
3925 relation_kind rel
) const;
3928 // Determine if there is a relationship between LHS and OP1.
3931 operator_identity::lhs_op1_relation (const irange
&lhs
,
3932 const irange
&op1 ATTRIBUTE_UNUSED
,
3933 const irange
&op2 ATTRIBUTE_UNUSED
,
3934 relation_kind
) const
3936 if (lhs
.undefined_p ())
3937 return VREL_VARYING
;
3938 // Simply a copy, so they are equivalent.
3943 operator_identity::fold_range (irange
&r
, tree type ATTRIBUTE_UNUSED
,
3945 const irange
&rh ATTRIBUTE_UNUSED
,
3946 relation_trio
) const
3953 operator_identity::op1_range (irange
&r
, tree type ATTRIBUTE_UNUSED
,
3955 const irange
&op2 ATTRIBUTE_UNUSED
,
3956 relation_trio
) const
3963 class operator_unknown
: public range_operator
3965 using range_operator::fold_range
;
3967 virtual bool fold_range (irange
&r
, tree type
,
3970 relation_trio rel
= TRIO_VARYING
) const;
3974 operator_unknown::fold_range (irange
&r
, tree type
,
3975 const irange
&lh ATTRIBUTE_UNUSED
,
3976 const irange
&rh ATTRIBUTE_UNUSED
,
3977 relation_trio
) const
3979 r
.set_varying (type
);
3984 class operator_abs
: public range_operator
3986 using range_operator::op1_range
;
3988 virtual void wi_fold (irange
&r
, tree type
,
3989 const wide_int
&lh_lb
,
3990 const wide_int
&lh_ub
,
3991 const wide_int
&rh_lb
,
3992 const wide_int
&rh_ub
) const;
3993 virtual bool op1_range (irange
&r
, tree type
,
3996 relation_trio
) const;
4000 operator_abs::wi_fold (irange
&r
, tree type
,
4001 const wide_int
&lh_lb
, const wide_int
&lh_ub
,
4002 const wide_int
&rh_lb ATTRIBUTE_UNUSED
,
4003 const wide_int
&rh_ub ATTRIBUTE_UNUSED
) const
4006 signop sign
= TYPE_SIGN (type
);
4007 unsigned prec
= TYPE_PRECISION (type
);
4009 // Pass through LH for the easy cases.
4010 if (sign
== UNSIGNED
|| wi::ge_p (lh_lb
, 0, sign
))
4012 r
= int_range
<1> (type
, lh_lb
, lh_ub
);
4016 // -TYPE_MIN_VALUE = TYPE_MIN_VALUE with flag_wrapv so we can't get
4018 wide_int min_value
= wi::min_value (prec
, sign
);
4019 wide_int max_value
= wi::max_value (prec
, sign
);
4020 if (!TYPE_OVERFLOW_UNDEFINED (type
) && wi::eq_p (lh_lb
, min_value
))
4022 r
.set_varying (type
);
4026 // ABS_EXPR may flip the range around, if the original range
4027 // included negative values.
4028 if (wi::eq_p (lh_lb
, min_value
))
4030 // ABS ([-MIN, -MIN]) isn't representable, but we have traditionally
4031 // returned [-MIN,-MIN] so this preserves that behaviour. PR37078
4032 if (wi::eq_p (lh_ub
, min_value
))
4034 r
= int_range
<1> (type
, min_value
, min_value
);
4040 min
= wi::abs (lh_lb
);
4042 if (wi::eq_p (lh_ub
, min_value
))
4045 max
= wi::abs (lh_ub
);
4047 // If the range contains zero then we know that the minimum value in the
4048 // range will be zero.
4049 if (wi::le_p (lh_lb
, 0, sign
) && wi::ge_p (lh_ub
, 0, sign
))
4051 if (wi::gt_p (min
, max
, sign
))
4053 min
= wi::zero (prec
);
4057 // If the range was reversed, swap MIN and MAX.
4058 if (wi::gt_p (min
, max
, sign
))
4059 std::swap (min
, max
);
4062 // If the new range has its limits swapped around (MIN > MAX), then
4063 // the operation caused one of them to wrap around. The only thing
4064 // we know is that the result is positive.
4065 if (wi::gt_p (min
, max
, sign
))
4067 min
= wi::zero (prec
);
4070 r
= int_range
<1> (type
, min
, max
);
4074 operator_abs::op1_range (irange
&r
, tree type
,
4077 relation_trio
) const
4079 if (empty_range_varying (r
, type
, lhs
, op2
))
4081 if (TYPE_UNSIGNED (type
))
4086 // Start with the positives because negatives are an impossible result.
4087 int_range_max positives
= range_positives (type
);
4088 positives
.intersect (lhs
);
4090 // Then add the negative of each pair:
4091 // ABS(op1) = [5,20] would yield op1 => [-20,-5][5,20].
4092 for (unsigned i
= 0; i
< positives
.num_pairs (); ++i
)
4093 r
.union_ (int_range
<1> (type
,
4094 -positives
.upper_bound (i
),
4095 -positives
.lower_bound (i
)));
4096 // With flag_wrapv, -TYPE_MIN_VALUE = TYPE_MIN_VALUE which is
4097 // unrepresentable. Add -TYPE_MIN_VALUE in this case.
4098 wide_int min_value
= wi::min_value (TYPE_PRECISION (type
), TYPE_SIGN (type
));
4099 wide_int lb
= lhs
.lower_bound ();
4100 if (!TYPE_OVERFLOW_UNDEFINED (type
) && wi::eq_p (lb
, min_value
))
4101 r
.union_ (int_range
<2> (type
, lb
, lb
));
4106 class operator_absu
: public range_operator
4109 virtual void wi_fold (irange
&r
, tree type
,
4110 const wide_int
&lh_lb
, const wide_int
&lh_ub
,
4111 const wide_int
&rh_lb
, const wide_int
&rh_ub
) const;
4115 operator_absu::wi_fold (irange
&r
, tree type
,
4116 const wide_int
&lh_lb
, const wide_int
&lh_ub
,
4117 const wide_int
&rh_lb ATTRIBUTE_UNUSED
,
4118 const wide_int
&rh_ub ATTRIBUTE_UNUSED
) const
4120 wide_int new_lb
, new_ub
;
4122 // Pass through VR0 the easy cases.
4123 if (wi::ges_p (lh_lb
, 0))
4130 new_lb
= wi::abs (lh_lb
);
4131 new_ub
= wi::abs (lh_ub
);
4133 // If the range contains zero then we know that the minimum
4134 // value in the range will be zero.
4135 if (wi::ges_p (lh_ub
, 0))
4137 if (wi::gtu_p (new_lb
, new_ub
))
4139 new_lb
= wi::zero (TYPE_PRECISION (type
));
4142 std::swap (new_lb
, new_ub
);
4145 gcc_checking_assert (TYPE_UNSIGNED (type
));
4146 r
= int_range
<1> (type
, new_lb
, new_ub
);
4150 class operator_negate
: public range_operator
4152 using range_operator::fold_range
;
4153 using range_operator::op1_range
;
4155 virtual bool fold_range (irange
&r
, tree type
,
4158 relation_trio rel
= TRIO_VARYING
) const;
4159 virtual bool op1_range (irange
&r
, tree type
,
4162 relation_trio rel
= TRIO_VARYING
) const;
4166 operator_negate::fold_range (irange
&r
, tree type
,
4169 relation_trio
) const
4171 if (empty_range_varying (r
, type
, lh
, rh
))
4173 // -X is simply 0 - X.
4174 return range_op_handler (MINUS_EXPR
, type
).fold_range (r
, type
,
4175 range_zero (type
), lh
);
4179 operator_negate::op1_range (irange
&r
, tree type
,
4182 relation_trio
) const
4184 // NEGATE is involutory.
4185 return fold_range (r
, type
, lhs
, op2
);
4189 class operator_addr_expr
: public range_operator
4191 using range_operator::fold_range
;
4192 using range_operator::op1_range
;
4194 virtual bool fold_range (irange
&r
, tree type
,
4197 relation_trio rel
= TRIO_VARYING
) const;
4198 virtual bool op1_range (irange
&r
, tree type
,
4201 relation_trio rel
= TRIO_VARYING
) const;
4205 operator_addr_expr::fold_range (irange
&r
, tree type
,
4208 relation_trio
) const
4210 if (empty_range_varying (r
, type
, lh
, rh
))
4213 // Return a non-null pointer of the LHS type (passed in op2).
4215 r
= range_zero (type
);
4216 else if (!lh
.contains_p (build_zero_cst (lh
.type ())))
4217 r
= range_nonzero (type
);
4219 r
.set_varying (type
);
4224 operator_addr_expr::op1_range (irange
&r
, tree type
,
4227 relation_trio
) const
4229 return operator_addr_expr::fold_range (r
, type
, lhs
, op2
);
4233 class pointer_plus_operator
: public range_operator
4236 virtual void wi_fold (irange
&r
, tree type
,
4237 const wide_int
&lh_lb
,
4238 const wide_int
&lh_ub
,
4239 const wide_int
&rh_lb
,
4240 const wide_int
&rh_ub
) const;
4241 virtual bool op2_range (irange
&r
, tree type
,
4244 relation_trio
= TRIO_VARYING
) const;
4248 pointer_plus_operator::wi_fold (irange
&r
, tree type
,
4249 const wide_int
&lh_lb
,
4250 const wide_int
&lh_ub
,
4251 const wide_int
&rh_lb
,
4252 const wide_int
&rh_ub
) const
4254 // Check for [0,0] + const, and simply return the const.
4255 if (lh_lb
== 0 && lh_ub
== 0 && rh_lb
== rh_ub
)
4257 tree val
= wide_int_to_tree (type
, rh_lb
);
4262 // For pointer types, we are really only interested in asserting
4263 // whether the expression evaluates to non-NULL.
4265 // With -fno-delete-null-pointer-checks we need to be more
4266 // conservative. As some object might reside at address 0,
4267 // then some offset could be added to it and the same offset
4268 // subtracted again and the result would be NULL.
4270 // static int a[12]; where &a[0] is NULL and
4273 // ptr will be NULL here, even when there is POINTER_PLUS_EXPR
4274 // where the first range doesn't include zero and the second one
4275 // doesn't either. As the second operand is sizetype (unsigned),
4276 // consider all ranges where the MSB could be set as possible
4277 // subtractions where the result might be NULL.
4278 if ((!wi_includes_zero_p (type
, lh_lb
, lh_ub
)
4279 || !wi_includes_zero_p (type
, rh_lb
, rh_ub
))
4280 && !TYPE_OVERFLOW_WRAPS (type
)
4281 && (flag_delete_null_pointer_checks
4282 || !wi::sign_mask (rh_ub
)))
4283 r
= range_nonzero (type
);
4284 else if (lh_lb
== lh_ub
&& lh_lb
== 0
4285 && rh_lb
== rh_ub
&& rh_lb
== 0)
4286 r
= range_zero (type
);
4288 r
.set_varying (type
);
4292 pointer_plus_operator::op2_range (irange
&r
, tree type
,
4293 const irange
&lhs ATTRIBUTE_UNUSED
,
4294 const irange
&op1 ATTRIBUTE_UNUSED
,
4295 relation_trio trio
) const
4297 relation_kind rel
= trio
.lhs_op1 ();
4298 r
.set_varying (type
);
4300 // If the LHS and OP1 are equal, the op2 must be zero.
4303 // If the LHS and OP1 are not equal, the offset must be non-zero.
4304 else if (rel
== VREL_NE
)
4305 r
.set_nonzero (type
);
4311 class pointer_min_max_operator
: public range_operator
4314 virtual void wi_fold (irange
& r
, tree type
,
4315 const wide_int
&lh_lb
, const wide_int
&lh_ub
,
4316 const wide_int
&rh_lb
, const wide_int
&rh_ub
) const;
4320 pointer_min_max_operator::wi_fold (irange
&r
, tree type
,
4321 const wide_int
&lh_lb
,
4322 const wide_int
&lh_ub
,
4323 const wide_int
&rh_lb
,
4324 const wide_int
&rh_ub
) const
4326 // For MIN/MAX expressions with pointers, we only care about
4327 // nullness. If both are non null, then the result is nonnull.
4328 // If both are null, then the result is null. Otherwise they
4330 if (!wi_includes_zero_p (type
, lh_lb
, lh_ub
)
4331 && !wi_includes_zero_p (type
, rh_lb
, rh_ub
))
4332 r
= range_nonzero (type
);
4333 else if (wi_zero_p (type
, lh_lb
, lh_ub
) && wi_zero_p (type
, rh_lb
, rh_ub
))
4334 r
= range_zero (type
);
4336 r
.set_varying (type
);
4340 class pointer_and_operator
: public range_operator
4343 virtual void wi_fold (irange
&r
, tree type
,
4344 const wide_int
&lh_lb
, const wide_int
&lh_ub
,
4345 const wide_int
&rh_lb
, const wide_int
&rh_ub
) const;
4349 pointer_and_operator::wi_fold (irange
&r
, tree type
,
4350 const wide_int
&lh_lb
,
4351 const wide_int
&lh_ub
,
4352 const wide_int
&rh_lb ATTRIBUTE_UNUSED
,
4353 const wide_int
&rh_ub ATTRIBUTE_UNUSED
) const
4355 // For pointer types, we are really only interested in asserting
4356 // whether the expression evaluates to non-NULL.
4357 if (wi_zero_p (type
, lh_lb
, lh_ub
) || wi_zero_p (type
, lh_lb
, lh_ub
))
4358 r
= range_zero (type
);
4360 r
.set_varying (type
);
4364 class pointer_or_operator
: public range_operator
4366 using range_operator::op1_range
;
4367 using range_operator::op2_range
;
4369 virtual bool op1_range (irange
&r
, tree type
,
4372 relation_trio rel
= TRIO_VARYING
) const;
4373 virtual bool op2_range (irange
&r
, tree type
,
4376 relation_trio rel
= TRIO_VARYING
) const;
4377 virtual void wi_fold (irange
&r
, tree type
,
4378 const wide_int
&lh_lb
, const wide_int
&lh_ub
,
4379 const wide_int
&rh_lb
, const wide_int
&rh_ub
) const;
4383 pointer_or_operator::op1_range (irange
&r
, tree type
,
4385 const irange
&op2 ATTRIBUTE_UNUSED
,
4386 relation_trio
) const
4388 if (lhs
.undefined_p ())
4392 tree zero
= build_zero_cst (type
);
4393 r
= int_range
<1> (zero
, zero
);
4396 r
.set_varying (type
);
4401 pointer_or_operator::op2_range (irange
&r
, tree type
,
4404 relation_trio
) const
4406 return pointer_or_operator::op1_range (r
, type
, lhs
, op1
);
4410 pointer_or_operator::wi_fold (irange
&r
, tree type
,
4411 const wide_int
&lh_lb
,
4412 const wide_int
&lh_ub
,
4413 const wide_int
&rh_lb
,
4414 const wide_int
&rh_ub
) const
4416 // For pointer types, we are really only interested in asserting
4417 // whether the expression evaluates to non-NULL.
4418 if (!wi_includes_zero_p (type
, lh_lb
, lh_ub
)
4419 && !wi_includes_zero_p (type
, rh_lb
, rh_ub
))
4420 r
= range_nonzero (type
);
4421 else if (wi_zero_p (type
, lh_lb
, lh_ub
) && wi_zero_p (type
, rh_lb
, rh_ub
))
4422 r
= range_zero (type
);
4424 r
.set_varying (type
);
4427 // Return a pointer to the range_operator instance, if there is one
4428 // associated with tree_code CODE.
4431 range_op_table::operator[] (enum tree_code code
)
4433 gcc_checking_assert (code
> 0 && code
< MAX_TREE_CODES
);
4434 return m_range_tree
[code
];
4437 // Add OP to the handler table for CODE.
4440 range_op_table::set (enum tree_code code
, range_operator
&op
)
4442 gcc_checking_assert (m_range_tree
[code
] == NULL
);
4443 m_range_tree
[code
] = &op
;
4444 gcc_checking_assert (op
.m_code
== ERROR_MARK
|| op
.m_code
== code
);
4448 // Shared operators that require separate instantiations because they
4449 // do not share a common tree code.
4450 static operator_cast op_nop
, op_convert
;
4451 static operator_identity op_ssa
, op_paren
, op_obj_type
;
4452 static operator_unknown op_realpart
, op_imagpart
;
4453 static pointer_min_max_operator op_ptr_min
, op_ptr_max
;
4454 static operator_div op_trunc_div
;
4455 static operator_div op_floor_div
;
4456 static operator_div op_round_div
;
4457 static operator_div op_ceil_div
;
4459 // Instantiate a range op table for integral operations.
4461 class integral_table
: public range_op_table
4465 } integral_tree_table
;
4467 integral_table::integral_table ()
4469 set (EQ_EXPR
, op_equal
);
4470 set (NE_EXPR
, op_not_equal
);
4471 set (LT_EXPR
, op_lt
);
4472 set (LE_EXPR
, op_le
);
4473 set (GT_EXPR
, op_gt
);
4474 set (GE_EXPR
, op_ge
);
4475 set (PLUS_EXPR
, op_plus
);
4476 set (MINUS_EXPR
, op_minus
);
4477 set (MIN_EXPR
, op_min
);
4478 set (MAX_EXPR
, op_max
);
4479 set (MULT_EXPR
, op_mult
);
4480 set (TRUNC_DIV_EXPR
, op_trunc_div
);
4481 set (FLOOR_DIV_EXPR
, op_floor_div
);
4482 set (ROUND_DIV_EXPR
, op_round_div
);
4483 set (CEIL_DIV_EXPR
, op_ceil_div
);
4484 set (EXACT_DIV_EXPR
, op_exact_div
);
4485 set (LSHIFT_EXPR
, op_lshift
);
4486 set (RSHIFT_EXPR
, op_rshift
);
4487 set (NOP_EXPR
, op_nop
);
4488 set (CONVERT_EXPR
, op_convert
);
4489 set (TRUTH_AND_EXPR
, op_logical_and
);
4490 set (BIT_AND_EXPR
, op_bitwise_and
);
4491 set (TRUTH_OR_EXPR
, op_logical_or
);
4492 set (BIT_IOR_EXPR
, op_bitwise_or
);
4493 set (BIT_XOR_EXPR
, op_bitwise_xor
);
4494 set (TRUNC_MOD_EXPR
, op_trunc_mod
);
4495 set (TRUTH_NOT_EXPR
, op_logical_not
);
4496 set (BIT_NOT_EXPR
, op_bitwise_not
);
4497 set (INTEGER_CST
, op_integer_cst
);
4498 set (SSA_NAME
, op_ssa
);
4499 set (PAREN_EXPR
, op_paren
);
4500 set (OBJ_TYPE_REF
, op_obj_type
);
4501 set (IMAGPART_EXPR
, op_imagpart
);
4502 set (REALPART_EXPR
, op_realpart
);
4503 set (POINTER_DIFF_EXPR
, op_pointer_diff
);
4504 set (ABS_EXPR
, op_abs
);
4505 set (ABSU_EXPR
, op_absu
);
4506 set (NEGATE_EXPR
, op_negate
);
4507 set (ADDR_EXPR
, op_addr
);
4510 // Instantiate a range op table for pointer operations.
4512 class pointer_table
: public range_op_table
4516 } pointer_tree_table
;
4518 pointer_table::pointer_table ()
4520 set (BIT_AND_EXPR
, op_pointer_and
);
4521 set (BIT_IOR_EXPR
, op_pointer_or
);
4522 set (MIN_EXPR
, op_ptr_min
);
4523 set (MAX_EXPR
, op_ptr_max
);
4524 set (POINTER_PLUS_EXPR
, op_pointer_plus
);
4526 set (EQ_EXPR
, op_equal
);
4527 set (NE_EXPR
, op_not_equal
);
4528 set (LT_EXPR
, op_lt
);
4529 set (LE_EXPR
, op_le
);
4530 set (GT_EXPR
, op_gt
);
4531 set (GE_EXPR
, op_ge
);
4532 set (SSA_NAME
, op_ssa
);
4533 set (INTEGER_CST
, op_integer_cst
);
4534 set (ADDR_EXPR
, op_addr
);
4535 set (NOP_EXPR
, op_nop
);
4536 set (CONVERT_EXPR
, op_convert
);
4538 set (BIT_NOT_EXPR
, op_bitwise_not
);
4539 set (BIT_XOR_EXPR
, op_bitwise_xor
);
4542 // The tables are hidden and accessed via a simple extern function.
4544 static inline range_operator
*
4545 get_handler (enum tree_code code
, tree type
)
4547 // First check if there is a pointer specialization.
4548 if (POINTER_TYPE_P (type
))
4549 return pointer_tree_table
[code
];
4550 if (INTEGRAL_TYPE_P (type
))
4551 return integral_tree_table
[code
];
4555 // Return the floating point operator for CODE or NULL if none available.
4557 static inline range_operator_float
*
4558 get_float_handler (enum tree_code code
, tree
)
4560 return (*floating_tree_table
)[code
];
4564 range_op_handler::set_op_handler (tree_code code
, tree type
)
4566 if (irange::supports_p (type
))
4569 m_int
= get_handler (code
, type
);
4570 m_valid
= m_int
!= NULL
;
4572 else if (frange::supports_p (type
))
4575 m_float
= get_float_handler (code
, type
);
4576 m_valid
= m_float
!= NULL
;
4586 range_op_handler::range_op_handler ()
4593 range_op_handler::range_op_handler (tree_code code
, tree type
)
4595 set_op_handler (code
, type
);
4600 range_op_handler::fold_range (vrange
&r
, tree type
,
4603 relation_trio rel
) const
4605 gcc_checking_assert (m_valid
);
4607 return m_int
->fold_range (as_a
<irange
> (r
), type
,
4609 as_a
<irange
> (rh
), rel
);
4611 if (is_a
<irange
> (r
))
4613 if (is_a
<irange
> (rh
))
4614 return m_float
->fold_range (as_a
<irange
> (r
), type
,
4616 as_a
<irange
> (rh
), rel
);
4618 return m_float
->fold_range (as_a
<irange
> (r
), type
,
4620 as_a
<frange
> (rh
), rel
);
4622 return m_float
->fold_range (as_a
<frange
> (r
), type
,
4624 as_a
<frange
> (rh
), rel
);
4628 range_op_handler::op1_range (vrange
&r
, tree type
,
4631 relation_trio rel
) const
4633 gcc_checking_assert (m_valid
);
4635 if (lhs
.undefined_p ())
4638 return m_int
->op1_range (as_a
<irange
> (r
), type
,
4639 as_a
<irange
> (lhs
),
4640 as_a
<irange
> (op2
), rel
);
4642 if (is_a
<irange
> (lhs
))
4643 return m_float
->op1_range (as_a
<frange
> (r
), type
,
4644 as_a
<irange
> (lhs
),
4645 as_a
<frange
> (op2
), rel
);
4646 return m_float
->op1_range (as_a
<frange
> (r
), type
,
4647 as_a
<frange
> (lhs
),
4648 as_a
<frange
> (op2
), rel
);
4652 range_op_handler::op2_range (vrange
&r
, tree type
,
4655 relation_trio rel
) const
4657 gcc_checking_assert (m_valid
);
4658 if (lhs
.undefined_p ())
4661 return m_int
->op2_range (as_a
<irange
> (r
), type
,
4662 as_a
<irange
> (lhs
),
4663 as_a
<irange
> (op1
), rel
);
4665 if (is_a
<irange
> (lhs
))
4666 return m_float
->op2_range (as_a
<frange
> (r
), type
,
4667 as_a
<irange
> (lhs
),
4668 as_a
<frange
> (op1
), rel
);
4669 return m_float
->op2_range (as_a
<frange
> (r
), type
,
4670 as_a
<frange
> (lhs
),
4671 as_a
<frange
> (op1
), rel
);
4675 range_op_handler::lhs_op1_relation (const vrange
&lhs
,
4678 relation_kind rel
) const
4680 gcc_checking_assert (m_valid
);
4682 return m_int
->lhs_op1_relation (as_a
<irange
> (lhs
),
4683 as_a
<irange
> (op1
),
4684 as_a
<irange
> (op2
), rel
);
4686 if (is_a
<irange
> (lhs
))
4687 return m_float
->lhs_op1_relation (as_a
<irange
> (lhs
),
4688 as_a
<frange
> (op1
),
4689 as_a
<frange
> (op2
), rel
);
4690 return m_float
->lhs_op1_relation (as_a
<frange
> (lhs
),
4691 as_a
<frange
> (op1
),
4692 as_a
<frange
> (op2
), rel
);
4696 range_op_handler::lhs_op2_relation (const vrange
&lhs
,
4699 relation_kind rel
) const
4701 gcc_checking_assert (m_valid
);
4703 return m_int
->lhs_op2_relation (as_a
<irange
> (lhs
),
4704 as_a
<irange
> (op1
),
4705 as_a
<irange
> (op2
), rel
);
4707 if (is_a
<irange
> (lhs
))
4708 return m_float
->lhs_op2_relation (as_a
<irange
> (lhs
),
4709 as_a
<frange
> (op1
),
4710 as_a
<frange
> (op2
), rel
);
4711 return m_float
->lhs_op2_relation (as_a
<frange
> (lhs
),
4712 as_a
<frange
> (op1
),
4713 as_a
<frange
> (op2
), rel
);
4717 range_op_handler::op1_op2_relation (const vrange
&lhs
) const
4719 gcc_checking_assert (m_valid
);
4721 return m_int
->op1_op2_relation (as_a
<irange
> (lhs
));
4722 if (is_a
<irange
> (lhs
))
4723 return m_float
->op1_op2_relation (as_a
<irange
> (lhs
));
4724 return m_float
->op1_op2_relation (as_a
<frange
> (lhs
));
4727 // Cast the range in R to TYPE.
4730 range_cast (vrange
&r
, tree type
)
4732 Value_Range
tmp (r
);
4733 Value_Range
varying (type
);
4734 varying
.set_varying (type
);
4735 range_op_handler
op (CONVERT_EXPR
, type
);
4736 // Call op_convert, if it fails, the result is varying.
4737 if (!op
|| !op
.fold_range (r
, type
, tmp
, varying
))
4739 r
.set_varying (type
);
4746 #include "selftest.h"
4750 #define INT(N) build_int_cst (integer_type_node, (N))
4751 #define UINT(N) build_int_cstu (unsigned_type_node, (N))
4752 #define INT16(N) build_int_cst (short_integer_type_node, (N))
4753 #define UINT16(N) build_int_cstu (short_unsigned_type_node, (N))
4754 #define SCHAR(N) build_int_cst (signed_char_type_node, (N))
4755 #define UCHAR(N) build_int_cstu (unsigned_char_type_node, (N))
4758 range_op_cast_tests ()
4760 int_range
<1> r0
, r1
, r2
, rold
;
4761 r0
.set_varying (integer_type_node
);
4762 tree maxint
= wide_int_to_tree (integer_type_node
, r0
.upper_bound ());
4764 // If a range is in any way outside of the range for the converted
4765 // to range, default to the range for the new type.
4766 r0
.set_varying (short_integer_type_node
);
4767 tree minshort
= wide_int_to_tree (short_integer_type_node
, r0
.lower_bound ());
4768 tree maxshort
= wide_int_to_tree (short_integer_type_node
, r0
.upper_bound ());
4769 if (TYPE_PRECISION (TREE_TYPE (maxint
))
4770 > TYPE_PRECISION (short_integer_type_node
))
4772 r1
= int_range
<1> (integer_zero_node
, maxint
);
4773 range_cast (r1
, short_integer_type_node
);
4774 ASSERT_TRUE (r1
.lower_bound () == wi::to_wide (minshort
)
4775 && r1
.upper_bound() == wi::to_wide (maxshort
));
4778 // (unsigned char)[-5,-1] => [251,255].
4779 r0
= rold
= int_range
<1> (SCHAR (-5), SCHAR (-1));
4780 range_cast (r0
, unsigned_char_type_node
);
4781 ASSERT_TRUE (r0
== int_range
<1> (UCHAR (251), UCHAR (255)));
4782 range_cast (r0
, signed_char_type_node
);
4783 ASSERT_TRUE (r0
== rold
);
4785 // (signed char)[15, 150] => [-128,-106][15,127].
4786 r0
= rold
= int_range
<1> (UCHAR (15), UCHAR (150));
4787 range_cast (r0
, signed_char_type_node
);
4788 r1
= int_range
<1> (SCHAR (15), SCHAR (127));
4789 r2
= int_range
<1> (SCHAR (-128), SCHAR (-106));
4791 ASSERT_TRUE (r1
== r0
);
4792 range_cast (r0
, unsigned_char_type_node
);
4793 ASSERT_TRUE (r0
== rold
);
4795 // (unsigned char)[-5, 5] => [0,5][251,255].
4796 r0
= rold
= int_range
<1> (SCHAR (-5), SCHAR (5));
4797 range_cast (r0
, unsigned_char_type_node
);
4798 r1
= int_range
<1> (UCHAR (251), UCHAR (255));
4799 r2
= int_range
<1> (UCHAR (0), UCHAR (5));
4801 ASSERT_TRUE (r0
== r1
);
4802 range_cast (r0
, signed_char_type_node
);
4803 ASSERT_TRUE (r0
== rold
);
4805 // (unsigned char)[-5,5] => [0,5][251,255].
4806 r0
= int_range
<1> (INT (-5), INT (5));
4807 range_cast (r0
, unsigned_char_type_node
);
4808 r1
= int_range
<1> (UCHAR (0), UCHAR (5));
4809 r1
.union_ (int_range
<1> (UCHAR (251), UCHAR (255)));
4810 ASSERT_TRUE (r0
== r1
);
4812 // (unsigned char)[5U,1974U] => [0,255].
4813 r0
= int_range
<1> (UINT (5), UINT (1974));
4814 range_cast (r0
, unsigned_char_type_node
);
4815 ASSERT_TRUE (r0
== int_range
<1> (UCHAR (0), UCHAR (255)));
4816 range_cast (r0
, integer_type_node
);
4817 // Going to a wider range should not sign extend.
4818 ASSERT_TRUE (r0
== int_range
<1> (INT (0), INT (255)));
4820 // (unsigned char)[-350,15] => [0,255].
4821 r0
= int_range
<1> (INT (-350), INT (15));
4822 range_cast (r0
, unsigned_char_type_node
);
4823 ASSERT_TRUE (r0
== (int_range
<1>
4824 (TYPE_MIN_VALUE (unsigned_char_type_node
),
4825 TYPE_MAX_VALUE (unsigned_char_type_node
))));
4827 // Casting [-120,20] from signed char to unsigned short.
4828 // => [0, 20][0xff88, 0xffff].
4829 r0
= int_range
<1> (SCHAR (-120), SCHAR (20));
4830 range_cast (r0
, short_unsigned_type_node
);
4831 r1
= int_range
<1> (UINT16 (0), UINT16 (20));
4832 r2
= int_range
<1> (UINT16 (0xff88), UINT16 (0xffff));
4834 ASSERT_TRUE (r0
== r1
);
4835 // A truncating cast back to signed char will work because [-120, 20]
4836 // is representable in signed char.
4837 range_cast (r0
, signed_char_type_node
);
4838 ASSERT_TRUE (r0
== int_range
<1> (SCHAR (-120), SCHAR (20)));
4840 // unsigned char -> signed short
4841 // (signed short)[(unsigned char)25, (unsigned char)250]
4842 // => [(signed short)25, (signed short)250]
4843 r0
= rold
= int_range
<1> (UCHAR (25), UCHAR (250));
4844 range_cast (r0
, short_integer_type_node
);
4845 r1
= int_range
<1> (INT16 (25), INT16 (250));
4846 ASSERT_TRUE (r0
== r1
);
4847 range_cast (r0
, unsigned_char_type_node
);
4848 ASSERT_TRUE (r0
== rold
);
4850 // Test casting a wider signed [-MIN,MAX] to a nar`rower unsigned.
4851 r0
= int_range
<1> (TYPE_MIN_VALUE (long_long_integer_type_node
),
4852 TYPE_MAX_VALUE (long_long_integer_type_node
));
4853 range_cast (r0
, short_unsigned_type_node
);
4854 r1
= int_range
<1> (TYPE_MIN_VALUE (short_unsigned_type_node
),
4855 TYPE_MAX_VALUE (short_unsigned_type_node
));
4856 ASSERT_TRUE (r0
== r1
);
4858 // Casting NONZERO to a narrower type will wrap/overflow so
4859 // it's just the entire range for the narrower type.
4861 // "NOT 0 at signed 32-bits" ==> [-MIN_32,-1][1, +MAX_32]. This is
4862 // is outside of the range of a smaller range, return the full
4864 if (TYPE_PRECISION (integer_type_node
)
4865 > TYPE_PRECISION (short_integer_type_node
))
4867 r0
= range_nonzero (integer_type_node
);
4868 range_cast (r0
, short_integer_type_node
);
4869 r1
= int_range
<1> (TYPE_MIN_VALUE (short_integer_type_node
),
4870 TYPE_MAX_VALUE (short_integer_type_node
));
4871 ASSERT_TRUE (r0
== r1
);
4874 // Casting NONZERO from a narrower signed to a wider signed.
4876 // NONZERO signed 16-bits is [-MIN_16,-1][1, +MAX_16].
4877 // Converting this to 32-bits signed is [-MIN_16,-1][1, +MAX_16].
4878 r0
= range_nonzero (short_integer_type_node
);
4879 range_cast (r0
, integer_type_node
);
4880 r1
= int_range
<1> (INT (-32768), INT (-1));
4881 r2
= int_range
<1> (INT (1), INT (32767));
4883 ASSERT_TRUE (r0
== r1
);
4887 range_op_lshift_tests ()
4889 // Test that 0x808.... & 0x8.... still contains 0x8....
4890 // for a large set of numbers.
4893 tree big_type
= long_long_unsigned_type_node
;
4894 // big_num = 0x808,0000,0000,0000
4895 tree big_num
= fold_build2 (LSHIFT_EXPR
, big_type
,
4896 build_int_cst (big_type
, 0x808),
4897 build_int_cst (big_type
, 48));
4898 op_bitwise_and
.fold_range (res
, big_type
,
4899 int_range
<1> (big_type
),
4900 int_range
<1> (big_num
, big_num
));
4901 // val = 0x8,0000,0000,0000
4902 tree val
= fold_build2 (LSHIFT_EXPR
, big_type
,
4903 build_int_cst (big_type
, 0x8),
4904 build_int_cst (big_type
, 48));
4905 ASSERT_TRUE (res
.contains_p (val
));
4908 if (TYPE_PRECISION (unsigned_type_node
) > 31)
4910 // unsigned VARYING = op1 << 1 should be VARYING.
4911 int_range
<2> lhs (unsigned_type_node
);
4912 int_range
<2> shift (INT (1), INT (1));
4914 op_lshift
.op1_range (op1
, unsigned_type_node
, lhs
, shift
);
4915 ASSERT_TRUE (op1
.varying_p ());
4917 // 0 = op1 << 1 should be [0,0], [0x8000000, 0x8000000].
4918 int_range
<2> zero (UINT (0), UINT (0));
4919 op_lshift
.op1_range (op1
, unsigned_type_node
, zero
, shift
);
4920 ASSERT_TRUE (op1
.num_pairs () == 2);
4921 // Remove the [0,0] range.
4922 op1
.intersect (zero
);
4923 ASSERT_TRUE (op1
.num_pairs () == 1);
4924 // op1 << 1 should be [0x8000,0x8000] << 1,
4925 // which should result in [0,0].
4926 int_range_max result
;
4927 op_lshift
.fold_range (result
, unsigned_type_node
, op1
, shift
);
4928 ASSERT_TRUE (result
== zero
);
4930 // signed VARYING = op1 << 1 should be VARYING.
4931 if (TYPE_PRECISION (integer_type_node
) > 31)
4933 // unsigned VARYING = op1 << 1 hould be VARYING.
4934 int_range
<2> lhs (integer_type_node
);
4935 int_range
<2> shift (INT (1), INT (1));
4937 op_lshift
.op1_range (op1
, integer_type_node
, lhs
, shift
);
4938 ASSERT_TRUE (op1
.varying_p ());
4940 // 0 = op1 << 1 should be [0,0], [0x8000000, 0x8000000].
4941 int_range
<2> zero (INT (0), INT (0));
4942 op_lshift
.op1_range (op1
, integer_type_node
, zero
, shift
);
4943 ASSERT_TRUE (op1
.num_pairs () == 2);
4944 // Remove the [0,0] range.
4945 op1
.intersect (zero
);
4946 ASSERT_TRUE (op1
.num_pairs () == 1);
4947 // op1 << 1 shuould be [0x8000,0x8000] << 1,
4948 // which should result in [0,0].
4949 int_range_max result
;
4950 op_lshift
.fold_range (result
, unsigned_type_node
, op1
, shift
);
4951 ASSERT_TRUE (result
== zero
);
4956 range_op_rshift_tests ()
4958 // unsigned: [3, MAX] = OP1 >> 1
4960 int_range_max
lhs (build_int_cst (unsigned_type_node
, 3),
4961 TYPE_MAX_VALUE (unsigned_type_node
));
4962 int_range_max
one (build_one_cst (unsigned_type_node
),
4963 build_one_cst (unsigned_type_node
));
4965 op_rshift
.op1_range (op1
, unsigned_type_node
, lhs
, one
);
4966 ASSERT_FALSE (op1
.contains_p (UINT (3)));
4969 // signed: [3, MAX] = OP1 >> 1
4971 int_range_max
lhs (INT (3), TYPE_MAX_VALUE (integer_type_node
));
4972 int_range_max
one (INT (1), INT (1));
4974 op_rshift
.op1_range (op1
, integer_type_node
, lhs
, one
);
4975 ASSERT_FALSE (op1
.contains_p (INT (-2)));
4978 // This is impossible, so OP1 should be [].
4979 // signed: [MIN, MIN] = OP1 >> 1
4981 int_range_max
lhs (TYPE_MIN_VALUE (integer_type_node
),
4982 TYPE_MIN_VALUE (integer_type_node
));
4983 int_range_max
one (INT (1), INT (1));
4985 op_rshift
.op1_range (op1
, integer_type_node
, lhs
, one
);
4986 ASSERT_TRUE (op1
.undefined_p ());
4989 // signed: ~[-1] = OP1 >> 31
4990 if (TYPE_PRECISION (integer_type_node
) > 31)
4992 int_range_max
lhs (INT (-1), INT (-1), VR_ANTI_RANGE
);
4993 int_range_max
shift (INT (31), INT (31));
4995 op_rshift
.op1_range (op1
, integer_type_node
, lhs
, shift
);
4996 int_range_max negatives
= range_negatives (integer_type_node
);
4997 negatives
.intersect (op1
);
4998 ASSERT_TRUE (negatives
.undefined_p ());
5003 range_op_bitwise_and_tests ()
5006 tree min
= vrp_val_min (integer_type_node
);
5007 tree max
= vrp_val_max (integer_type_node
);
5008 tree tiny
= fold_build2 (PLUS_EXPR
, integer_type_node
, min
,
5009 build_one_cst (integer_type_node
));
5010 int_range_max
i1 (tiny
, max
);
5011 int_range_max
i2 (build_int_cst (integer_type_node
, 255),
5012 build_int_cst (integer_type_node
, 255));
5014 // [MIN+1, MAX] = OP1 & 255: OP1 is VARYING
5015 op_bitwise_and
.op1_range (res
, integer_type_node
, i1
, i2
);
5016 ASSERT_TRUE (res
== int_range
<1> (integer_type_node
));
5018 // VARYING = OP1 & 255: OP1 is VARYING
5019 i1
= int_range
<1> (integer_type_node
);
5020 op_bitwise_and
.op1_range (res
, integer_type_node
, i1
, i2
);
5021 ASSERT_TRUE (res
== int_range
<1> (integer_type_node
));
5023 // For 0 = x & MASK, x is ~MASK.
5025 int_range
<2> zero (integer_zero_node
, integer_zero_node
);
5026 int_range
<2> mask
= int_range
<2> (INT (7), INT (7));
5027 op_bitwise_and
.op1_range (res
, integer_type_node
, zero
, mask
);
5028 wide_int inv
= wi::shwi (~7U, TYPE_PRECISION (integer_type_node
));
5029 ASSERT_TRUE (res
.get_nonzero_bits () == inv
);
5032 // (NONZERO | X) is nonzero.
5033 i1
.set_nonzero (integer_type_node
);
5034 i2
.set_varying (integer_type_node
);
5035 op_bitwise_or
.fold_range (res
, integer_type_node
, i1
, i2
);
5036 ASSERT_TRUE (res
.nonzero_p ());
5038 // (NEGATIVE | X) is nonzero.
5039 i1
= int_range
<1> (INT (-5), INT (-3));
5040 i2
.set_varying (integer_type_node
);
5041 op_bitwise_or
.fold_range (res
, integer_type_node
, i1
, i2
);
5042 ASSERT_FALSE (res
.contains_p (INT (0)));
5046 range_relational_tests ()
5048 int_range
<2> lhs (unsigned_char_type_node
);
5049 int_range
<2> op1 (UCHAR (8), UCHAR (10));
5050 int_range
<2> op2 (UCHAR (20), UCHAR (20));
5052 // Never wrapping additions mean LHS > OP1.
5053 relation_kind code
= op_plus
.lhs_op1_relation (lhs
, op1
, op2
, VREL_VARYING
);
5054 ASSERT_TRUE (code
== VREL_GT
);
5056 // Most wrapping additions mean nothing...
5057 op1
= int_range
<2> (UCHAR (8), UCHAR (10));
5058 op2
= int_range
<2> (UCHAR (0), UCHAR (255));
5059 code
= op_plus
.lhs_op1_relation (lhs
, op1
, op2
, VREL_VARYING
);
5060 ASSERT_TRUE (code
== VREL_VARYING
);
5062 // However, always wrapping additions mean LHS < OP1.
5063 op1
= int_range
<2> (UCHAR (1), UCHAR (255));
5064 op2
= int_range
<2> (UCHAR (255), UCHAR (255));
5065 code
= op_plus
.lhs_op1_relation (lhs
, op1
, op2
, VREL_VARYING
);
5066 ASSERT_TRUE (code
== VREL_LT
);
5072 range_op_rshift_tests ();
5073 range_op_lshift_tests ();
5074 range_op_bitwise_and_tests ();
5075 range_op_cast_tests ();
5076 range_relational_tests ();
5078 extern void range_op_float_tests ();
5079 range_op_float_tests ();
5082 } // namespace selftest
5084 #endif // CHECKING_P