1 /* Code for range operators.
2 Copyright (C) 2017-2022 Free Software Foundation, Inc.
3 Contributed by Andrew MacLeod <amacleod@redhat.com>
4 and Aldy Hernandez <aldyh@redhat.com>.
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify
9 it under the terms of the GNU General Public License as published by
10 the Free Software Foundation; either version 3, or (at your option)
13 GCC is distributed in the hope that it will be useful,
14 but WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 GNU General Public License for more details.
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
24 #include "coretypes.h"
26 #include "insn-codes.h"
31 #include "tree-pass.h"
33 #include "optabs-tree.h"
34 #include "gimple-pretty-print.h"
35 #include "diagnostic-core.h"
37 #include "fold-const.h"
38 #include "stor-layout.h"
41 #include "gimple-fold.h"
43 #include "gimple-iterator.h"
44 #include "gimple-walk.h"
47 #include "value-relation.h"
50 // Return the upper limit for a type.
52 static inline wide_int
53 max_limit (const_tree type
)
55 return wi::max_value (TYPE_PRECISION (type
) , TYPE_SIGN (type
));
58 // Return the lower limit for a type.
60 static inline wide_int
61 min_limit (const_tree type
)
63 return wi::min_value (TYPE_PRECISION (type
) , TYPE_SIGN (type
));
66 // If the range of either op1 or op2 is undefined, set the result to
67 // varying and return TRUE. If the caller truely cares about a result,
68 // they should pass in a varying if it has an undefined that it wants
69 // treated as a varying.
72 empty_range_varying (irange
&r
, tree type
,
73 const irange
&op1
, const irange
& op2
)
75 if (op1
.undefined_p () || op2
.undefined_p ())
84 // Return false if shifting by OP is undefined behavior. Otherwise, return
85 // true and the range it is to be shifted by. This allows trimming out of
86 // undefined ranges, leaving only valid ranges if there are any.
89 get_shift_range (irange
&r
, tree type
, const irange
&op
)
91 if (op
.undefined_p ())
94 // Build valid range and intersect it with the shift range.
95 r
= value_range (build_int_cst_type (op
.type (), 0),
96 build_int_cst_type (op
.type (), TYPE_PRECISION (type
) - 1));
99 // If there are no valid ranges in the shift range, returned false.
100 if (r
.undefined_p ())
105 // Return TRUE if 0 is within [WMIN, WMAX].
108 wi_includes_zero_p (tree type
, const wide_int
&wmin
, const wide_int
&wmax
)
110 signop sign
= TYPE_SIGN (type
);
111 return wi::le_p (wmin
, 0, sign
) && wi::ge_p (wmax
, 0, sign
);
114 // Return TRUE if [WMIN, WMAX] is the singleton 0.
117 wi_zero_p (tree type
, const wide_int
&wmin
, const wide_int
&wmax
)
119 unsigned prec
= TYPE_PRECISION (type
);
120 return wmin
== wmax
&& wi::eq_p (wmin
, wi::zero (prec
));
123 // Default wide_int fold operation returns [MIN, MAX].
126 range_operator::wi_fold (irange
&r
, tree type
,
127 const wide_int
&lh_lb ATTRIBUTE_UNUSED
,
128 const wide_int
&lh_ub ATTRIBUTE_UNUSED
,
129 const wide_int
&rh_lb ATTRIBUTE_UNUSED
,
130 const wide_int
&rh_ub ATTRIBUTE_UNUSED
) const
132 gcc_checking_assert (irange::supports_type_p (type
));
133 r
.set_varying (type
);
136 // Call wi_fold, except further split small subranges into constants.
137 // This can provide better precision. For something 8 >> [0,1]
138 // Instead of [8, 16], we will produce [8,8][16,16]
141 range_operator::wi_fold_in_parts (irange
&r
, tree type
,
142 const wide_int
&lh_lb
,
143 const wide_int
&lh_ub
,
144 const wide_int
&rh_lb
,
145 const wide_int
&rh_ub
) const
147 wi::overflow_type ov_rh
, ov_lh
;
149 wide_int rh_range
= wi::sub (rh_ub
, rh_lb
, TYPE_SIGN (type
), &ov_rh
);
150 wide_int lh_range
= wi::sub (lh_ub
, lh_lb
, TYPE_SIGN (type
), &ov_lh
);
151 signop sign
= TYPE_SIGN (type
);;
152 // If there are 2, 3, or 4 values in the RH range, do them separately.
153 // Call wi_fold_in_parts to check the RH side.
154 if (wi::gt_p (rh_range
, 0, sign
) && wi::lt_p (rh_range
, 4, sign
)
155 && ov_rh
== wi::OVF_NONE
)
157 wi_fold_in_parts (r
, type
, lh_lb
, lh_ub
, rh_lb
, rh_lb
);
158 if (wi::gt_p (rh_range
, 1, sign
))
160 wi_fold_in_parts (tmp
, type
, lh_lb
, lh_ub
, rh_lb
+ 1, rh_lb
+ 1);
162 if (wi::eq_p (rh_range
, 3))
164 wi_fold_in_parts (tmp
, type
, lh_lb
, lh_ub
, rh_lb
+ 2, rh_lb
+ 2);
168 wi_fold_in_parts (tmp
, type
, lh_lb
, lh_ub
, rh_ub
, rh_ub
);
171 // Otherise check for 2, 3, or 4 values in the LH range and split them up.
172 // The RH side has been checked, so no recursion needed.
173 else if (wi::gt_p (lh_range
, 0, sign
) && wi::lt_p (lh_range
, 4, sign
)
174 && ov_lh
== wi::OVF_NONE
)
176 wi_fold (r
, type
, lh_lb
, lh_lb
, rh_lb
, rh_ub
);
177 if (wi::gt_p (lh_range
, 1, sign
))
179 wi_fold (tmp
, type
, lh_lb
+ 1, lh_lb
+ 1, rh_lb
, rh_ub
);
181 if (wi::eq_p (lh_range
, 3))
183 wi_fold (tmp
, type
, lh_lb
+ 2, lh_lb
+ 2, rh_lb
, rh_ub
);
187 wi_fold (tmp
, type
, lh_ub
, lh_ub
, rh_lb
, rh_ub
);
190 // Otherwise just call wi_fold.
192 wi_fold (r
, type
, lh_lb
, lh_ub
, rh_lb
, rh_ub
);
195 // The default for fold is to break all ranges into sub-ranges and
196 // invoke the wi_fold method on each sub-range pair.
199 range_operator::fold_range (irange
&r
, tree type
,
202 relation_kind rel
) const
204 gcc_checking_assert (irange::supports_type_p (type
));
205 if (empty_range_varying (r
, type
, lh
, rh
))
208 unsigned num_lh
= lh
.num_pairs ();
209 unsigned num_rh
= rh
.num_pairs ();
211 // If both ranges are single pairs, fold directly into the result range.
212 // If the number of subranges grows too high, produce a summary result as the
213 // loop becomes exponential with little benefit. See PR 103821.
214 if ((num_lh
== 1 && num_rh
== 1) || num_lh
* num_rh
> 12)
216 wi_fold_in_parts (r
, type
, lh
.lower_bound (), lh
.upper_bound (),
217 rh
.lower_bound (), rh
.upper_bound ());
218 op1_op2_relation_effect (r
, type
, lh
, rh
, rel
);
224 for (unsigned x
= 0; x
< num_lh
; ++x
)
225 for (unsigned y
= 0; y
< num_rh
; ++y
)
227 wide_int lh_lb
= lh
.lower_bound (x
);
228 wide_int lh_ub
= lh
.upper_bound (x
);
229 wide_int rh_lb
= rh
.lower_bound (y
);
230 wide_int rh_ub
= rh
.upper_bound (y
);
231 wi_fold_in_parts (tmp
, type
, lh_lb
, lh_ub
, rh_lb
, rh_ub
);
235 op1_op2_relation_effect (r
, type
, lh
, rh
, rel
);
239 op1_op2_relation_effect (r
, type
, lh
, rh
, rel
);
243 // The default for op1_range is to return false.
246 range_operator::op1_range (irange
&r ATTRIBUTE_UNUSED
,
247 tree type ATTRIBUTE_UNUSED
,
248 const irange
&lhs ATTRIBUTE_UNUSED
,
249 const irange
&op2 ATTRIBUTE_UNUSED
,
250 relation_kind rel ATTRIBUTE_UNUSED
) const
255 // The default for op2_range is to return false.
258 range_operator::op2_range (irange
&r ATTRIBUTE_UNUSED
,
259 tree type ATTRIBUTE_UNUSED
,
260 const irange
&lhs ATTRIBUTE_UNUSED
,
261 const irange
&op1 ATTRIBUTE_UNUSED
,
262 relation_kind rel ATTRIBUTE_UNUSED
) const
267 // The default relation routines return VREL_NONE.
270 range_operator::lhs_op1_relation (const irange
&lhs ATTRIBUTE_UNUSED
,
271 const irange
&op1 ATTRIBUTE_UNUSED
,
272 const irange
&op2 ATTRIBUTE_UNUSED
) const
278 range_operator::lhs_op2_relation (const irange
&lhs ATTRIBUTE_UNUSED
,
279 const irange
&op1 ATTRIBUTE_UNUSED
,
280 const irange
&op2 ATTRIBUTE_UNUSED
) const
286 range_operator::op1_op2_relation (const irange
&lhs ATTRIBUTE_UNUSED
) const
291 // Default is no relation affects the LHS.
294 range_operator::op1_op2_relation_effect (irange
&lhs_range ATTRIBUTE_UNUSED
,
295 tree type ATTRIBUTE_UNUSED
,
296 const irange
&op1_range ATTRIBUTE_UNUSED
,
297 const irange
&op2_range ATTRIBUTE_UNUSED
,
298 relation_kind rel ATTRIBUTE_UNUSED
) const
303 // Create and return a range from a pair of wide-ints that are known
304 // to have overflowed (or underflowed).
307 value_range_from_overflowed_bounds (irange
&r
, tree type
,
308 const wide_int
&wmin
,
309 const wide_int
&wmax
)
311 const signop sgn
= TYPE_SIGN (type
);
312 const unsigned int prec
= TYPE_PRECISION (type
);
314 wide_int tmin
= wide_int::from (wmin
, prec
, sgn
);
315 wide_int tmax
= wide_int::from (wmax
, prec
, sgn
);
320 if (wi::cmp (tmin
, tmax
, sgn
) < 0)
323 if (wi::cmp (tmax
, tem
, sgn
) > 0)
326 // If the anti-range would cover nothing, drop to varying.
327 // Likewise if the anti-range bounds are outside of the types
329 if (covers
|| wi::cmp (tmin
, tmax
, sgn
) > 0)
330 r
.set_varying (type
);
333 tree tree_min
= wide_int_to_tree (type
, tmin
);
334 tree tree_max
= wide_int_to_tree (type
, tmax
);
335 r
.set (tree_min
, tree_max
, VR_ANTI_RANGE
);
339 // Create and return a range from a pair of wide-ints. MIN_OVF and
340 // MAX_OVF describe any overflow that might have occurred while
341 // calculating WMIN and WMAX respectively.
344 value_range_with_overflow (irange
&r
, tree type
,
345 const wide_int
&wmin
, const wide_int
&wmax
,
346 wi::overflow_type min_ovf
= wi::OVF_NONE
,
347 wi::overflow_type max_ovf
= wi::OVF_NONE
)
349 const signop sgn
= TYPE_SIGN (type
);
350 const unsigned int prec
= TYPE_PRECISION (type
);
351 const bool overflow_wraps
= TYPE_OVERFLOW_WRAPS (type
);
353 // For one bit precision if max != min, then the range covers all
355 if (prec
== 1 && wi::ne_p (wmax
, wmin
))
357 r
.set_varying (type
);
363 // If overflow wraps, truncate the values and adjust the range,
364 // kind, and bounds appropriately.
365 if ((min_ovf
!= wi::OVF_NONE
) == (max_ovf
!= wi::OVF_NONE
))
367 wide_int tmin
= wide_int::from (wmin
, prec
, sgn
);
368 wide_int tmax
= wide_int::from (wmax
, prec
, sgn
);
369 // If the limits are swapped, we wrapped around and cover
371 if (wi::gt_p (tmin
, tmax
, sgn
))
372 r
.set_varying (type
);
374 // No overflow or both overflow or underflow. The range
375 // kind stays normal.
376 r
.set (wide_int_to_tree (type
, tmin
),
377 wide_int_to_tree (type
, tmax
));
381 if ((min_ovf
== wi::OVF_UNDERFLOW
&& max_ovf
== wi::OVF_NONE
)
382 || (max_ovf
== wi::OVF_OVERFLOW
&& min_ovf
== wi::OVF_NONE
))
383 value_range_from_overflowed_bounds (r
, type
, wmin
, wmax
);
385 // Other underflow and/or overflow, drop to VR_VARYING.
386 r
.set_varying (type
);
390 // If both bounds either underflowed or overflowed, then the result
392 if ((min_ovf
== wi::OVF_OVERFLOW
&& max_ovf
== wi::OVF_OVERFLOW
)
393 || (min_ovf
== wi::OVF_UNDERFLOW
&& max_ovf
== wi::OVF_UNDERFLOW
))
399 // If overflow does not wrap, saturate to [MIN, MAX].
400 wide_int new_lb
, new_ub
;
401 if (min_ovf
== wi::OVF_UNDERFLOW
)
402 new_lb
= wi::min_value (prec
, sgn
);
403 else if (min_ovf
== wi::OVF_OVERFLOW
)
404 new_lb
= wi::max_value (prec
, sgn
);
408 if (max_ovf
== wi::OVF_UNDERFLOW
)
409 new_ub
= wi::min_value (prec
, sgn
);
410 else if (max_ovf
== wi::OVF_OVERFLOW
)
411 new_ub
= wi::max_value (prec
, sgn
);
415 r
.set (wide_int_to_tree (type
, new_lb
),
416 wide_int_to_tree (type
, new_ub
));
420 // Create and return a range from a pair of wide-ints. Canonicalize
421 // the case where the bounds are swapped. In which case, we transform
422 // [10,5] into [MIN,5][10,MAX].
425 create_possibly_reversed_range (irange
&r
, tree type
,
426 const wide_int
&new_lb
, const wide_int
&new_ub
)
428 signop s
= TYPE_SIGN (type
);
429 // If the bounds are swapped, treat the result as if an overflow occured.
430 if (wi::gt_p (new_lb
, new_ub
, s
))
431 value_range_from_overflowed_bounds (r
, type
, new_lb
, new_ub
);
433 // Otherwise it's just a normal range.
434 r
.set (wide_int_to_tree (type
, new_lb
), wide_int_to_tree (type
, new_ub
));
437 // Return an irange instance that is a boolean TRUE.
439 static inline int_range
<1>
440 range_true (tree type
)
442 unsigned prec
= TYPE_PRECISION (type
);
443 return int_range
<1> (type
, wi::one (prec
), wi::one (prec
));
446 // Return an irange instance that is a boolean FALSE.
448 static inline int_range
<1>
449 range_false (tree type
)
451 unsigned prec
= TYPE_PRECISION (type
);
452 return int_range
<1> (type
, wi::zero (prec
), wi::zero (prec
));
455 // Return an irange that covers both true and false.
457 static inline int_range
<1>
458 range_true_and_false (tree type
)
460 unsigned prec
= TYPE_PRECISION (type
);
461 return int_range
<1> (type
, wi::zero (prec
), wi::one (prec
));
464 enum bool_range_state
{ BRS_FALSE
, BRS_TRUE
, BRS_EMPTY
, BRS_FULL
};
466 // Return the summary information about boolean range LHS. If EMPTY/FULL,
467 // return the equivalent range for TYPE in R; if FALSE/TRUE, do nothing.
469 static bool_range_state
470 get_bool_state (irange
&r
, const irange
&lhs
, tree val_type
)
472 // If there is no result, then this is unexecutable.
473 if (lhs
.undefined_p ())
482 // For TRUE, we can't just test for [1,1] because Ada can have
483 // multi-bit booleans, and TRUE values can be: [1, MAX], ~[0], etc.
484 if (lhs
.contains_p (build_zero_cst (lhs
.type ())))
486 r
.set_varying (val_type
);
493 // For relation opcodes, first try to see if the supplied relation
494 // forces a true or false result, and return that.
495 // Then check for undefined operands. If none of this applies,
499 relop_early_resolve (irange
&r
, tree type
, const irange
&op1
,
500 const irange
&op2
, relation_kind rel
,
501 relation_kind my_rel
)
503 // If known relation is a complete subset of this relation, always true.
504 if (relation_union (rel
, my_rel
) == my_rel
)
506 r
= range_true (type
);
510 // If known relation has no subset of this relation, always false.
511 if (relation_intersect (rel
, my_rel
) == VREL_EMPTY
)
513 r
= range_false (type
);
517 // If either operand is undefined, return VARYING.
518 if (empty_range_varying (r
, type
, op1
, op2
))
525 class operator_equal
: public range_operator
528 virtual bool fold_range (irange
&r
, tree type
,
531 relation_kind rel
= VREL_NONE
) const;
532 virtual bool op1_range (irange
&r
, tree type
,
535 relation_kind rel
= VREL_NONE
) const;
536 virtual bool op2_range (irange
&r
, tree type
,
539 relation_kind rel
= VREL_NONE
) const;
540 virtual enum tree_code
op1_op2_relation (const irange
&lhs
) const;
543 // Check if the LHS range indicates a relation between OP1 and OP2.
546 operator_equal::op1_op2_relation (const irange
&lhs
) const
548 if (lhs
.undefined_p ())
551 // FALSE = op1 == op2 indicates NE_EXPR.
555 // TRUE = op1 == op2 indicates EQ_EXPR.
556 if (!lhs
.contains_p (build_zero_cst (lhs
.type ())))
563 operator_equal::fold_range (irange
&r
, tree type
,
566 relation_kind rel
) const
568 if (relop_early_resolve (r
, type
, op1
, op2
, rel
, EQ_EXPR
))
571 // We can be sure the values are always equal or not if both ranges
572 // consist of a single value, and then compare them.
573 if (wi::eq_p (op1
.lower_bound (), op1
.upper_bound ())
574 && wi::eq_p (op2
.lower_bound (), op2
.upper_bound ()))
576 if (wi::eq_p (op1
.lower_bound (), op2
.upper_bound()))
577 r
= range_true (type
);
579 r
= range_false (type
);
583 // If ranges do not intersect, we know the range is not equal,
584 // otherwise we don't know anything for sure.
585 int_range_max tmp
= op1
;
587 if (tmp
.undefined_p ())
588 r
= range_false (type
);
590 r
= range_true_and_false (type
);
596 operator_equal::op1_range (irange
&r
, tree type
,
599 relation_kind rel ATTRIBUTE_UNUSED
) const
601 switch (get_bool_state (r
, lhs
, type
))
604 // If the result is false, the only time we know anything is
605 // if OP2 is a constant.
606 if (wi::eq_p (op2
.lower_bound(), op2
.upper_bound()))
612 r
.set_varying (type
);
616 // If it's true, the result is the same as OP2.
627 operator_equal::op2_range (irange
&r
, tree type
,
630 relation_kind rel
) const
632 return operator_equal::op1_range (r
, type
, lhs
, op1
, rel
);
635 class operator_not_equal
: public range_operator
638 virtual bool fold_range (irange
&r
, tree type
,
641 relation_kind rel
= VREL_NONE
) const;
642 virtual bool op1_range (irange
&r
, tree type
,
645 relation_kind rel
= VREL_NONE
) const;
646 virtual bool op2_range (irange
&r
, tree type
,
649 relation_kind rel
= VREL_NONE
) const;
650 virtual enum tree_code
op1_op2_relation (const irange
&lhs
) const;
653 // Check if the LHS range indicates a relation between OP1 and OP2.
656 operator_not_equal::op1_op2_relation (const irange
&lhs
) const
658 if (lhs
.undefined_p ())
661 // FALSE = op1 != op2 indicates EQ_EXPR.
665 // TRUE = op1 != op2 indicates NE_EXPR.
666 if (!lhs
.contains_p (build_zero_cst (lhs
.type ())))
672 operator_not_equal::fold_range (irange
&r
, tree type
,
675 relation_kind rel
) const
677 if (relop_early_resolve (r
, type
, op1
, op2
, rel
, NE_EXPR
))
680 // We can be sure the values are always equal or not if both ranges
681 // consist of a single value, and then compare them.
682 if (wi::eq_p (op1
.lower_bound (), op1
.upper_bound ())
683 && wi::eq_p (op2
.lower_bound (), op2
.upper_bound ()))
685 if (wi::ne_p (op1
.lower_bound (), op2
.upper_bound()))
686 r
= range_true (type
);
688 r
= range_false (type
);
692 // If ranges do not intersect, we know the range is not equal,
693 // otherwise we don't know anything for sure.
694 int_range_max tmp
= op1
;
696 if (tmp
.undefined_p ())
697 r
= range_true (type
);
699 r
= range_true_and_false (type
);
705 operator_not_equal::op1_range (irange
&r
, tree type
,
708 relation_kind rel ATTRIBUTE_UNUSED
) const
710 switch (get_bool_state (r
, lhs
, type
))
713 // If the result is true, the only time we know anything is if
714 // OP2 is a constant.
715 if (wi::eq_p (op2
.lower_bound(), op2
.upper_bound()))
721 r
.set_varying (type
);
725 // If it's false, the result is the same as OP2.
737 operator_not_equal::op2_range (irange
&r
, tree type
,
740 relation_kind rel
) const
742 return operator_not_equal::op1_range (r
, type
, lhs
, op1
, rel
);
745 // (X < VAL) produces the range of [MIN, VAL - 1].
748 build_lt (irange
&r
, tree type
, const wide_int
&val
)
750 wi::overflow_type ov
;
752 signop sgn
= TYPE_SIGN (type
);
754 // Signed 1 bit cannot represent 1 for subtraction.
756 lim
= wi::add (val
, -1, sgn
, &ov
);
758 lim
= wi::sub (val
, 1, sgn
, &ov
);
760 // If val - 1 underflows, check if X < MIN, which is an empty range.
764 r
= int_range
<1> (type
, min_limit (type
), lim
);
767 // (X <= VAL) produces the range of [MIN, VAL].
770 build_le (irange
&r
, tree type
, const wide_int
&val
)
772 r
= int_range
<1> (type
, min_limit (type
), val
);
775 // (X > VAL) produces the range of [VAL + 1, MAX].
778 build_gt (irange
&r
, tree type
, const wide_int
&val
)
780 wi::overflow_type ov
;
782 signop sgn
= TYPE_SIGN (type
);
784 // Signed 1 bit cannot represent 1 for addition.
786 lim
= wi::sub (val
, -1, sgn
, &ov
);
788 lim
= wi::add (val
, 1, sgn
, &ov
);
789 // If val + 1 overflows, check is for X > MAX, which is an empty range.
793 r
= int_range
<1> (type
, lim
, max_limit (type
));
796 // (X >= val) produces the range of [VAL, MAX].
799 build_ge (irange
&r
, tree type
, const wide_int
&val
)
801 r
= int_range
<1> (type
, val
, max_limit (type
));
805 class operator_lt
: public range_operator
808 virtual bool fold_range (irange
&r
, tree type
,
811 relation_kind rel
= VREL_NONE
) const;
812 virtual bool op1_range (irange
&r
, tree type
,
815 relation_kind rel
= VREL_NONE
) const;
816 virtual bool op2_range (irange
&r
, tree type
,
819 relation_kind rel
= VREL_NONE
) const;
820 virtual enum tree_code
op1_op2_relation (const irange
&lhs
) const;
823 // Check if the LHS range indicates a relation between OP1 and OP2.
826 operator_lt::op1_op2_relation (const irange
&lhs
) const
828 if (lhs
.undefined_p ())
831 // FALSE = op1 < op2 indicates GE_EXPR.
835 // TRUE = op1 < op2 indicates LT_EXPR.
836 if (!lhs
.contains_p (build_zero_cst (lhs
.type ())))
842 operator_lt::fold_range (irange
&r
, tree type
,
845 relation_kind rel
) const
847 if (relop_early_resolve (r
, type
, op1
, op2
, rel
, LT_EXPR
))
850 signop sign
= TYPE_SIGN (op1
.type ());
851 gcc_checking_assert (sign
== TYPE_SIGN (op2
.type ()));
853 if (wi::lt_p (op1
.upper_bound (), op2
.lower_bound (), sign
))
854 r
= range_true (type
);
855 else if (!wi::lt_p (op1
.lower_bound (), op2
.upper_bound (), sign
))
856 r
= range_false (type
);
858 r
= range_true_and_false (type
);
863 operator_lt::op1_range (irange
&r
, tree type
,
866 relation_kind rel ATTRIBUTE_UNUSED
) const
868 switch (get_bool_state (r
, lhs
, type
))
871 build_lt (r
, type
, op2
.upper_bound ());
875 build_ge (r
, type
, op2
.lower_bound ());
885 operator_lt::op2_range (irange
&r
, tree type
,
888 relation_kind rel ATTRIBUTE_UNUSED
) const
890 switch (get_bool_state (r
, lhs
, type
))
893 build_le (r
, type
, op1
.upper_bound ());
897 build_gt (r
, type
, op1
.lower_bound ());
907 class operator_le
: public range_operator
910 virtual bool fold_range (irange
&r
, tree type
,
913 relation_kind rel
= VREL_NONE
) const;
914 virtual bool op1_range (irange
&r
, tree type
,
917 relation_kind rel
= VREL_NONE
) const;
918 virtual bool op2_range (irange
&r
, tree type
,
921 relation_kind rel
= VREL_NONE
) const;
922 virtual enum tree_code
op1_op2_relation (const irange
&lhs
) const;
925 // Check if the LHS range indicates a relation between OP1 and OP2.
928 operator_le::op1_op2_relation (const irange
&lhs
) const
930 if (lhs
.undefined_p ())
933 // FALSE = op1 <= op2 indicates GT_EXPR.
937 // TRUE = op1 <= op2 indicates LE_EXPR.
938 if (!lhs
.contains_p (build_zero_cst (lhs
.type ())))
944 operator_le::fold_range (irange
&r
, tree type
,
947 relation_kind rel
) const
949 if (relop_early_resolve (r
, type
, op1
, op2
, rel
, LE_EXPR
))
952 signop sign
= TYPE_SIGN (op1
.type ());
953 gcc_checking_assert (sign
== TYPE_SIGN (op2
.type ()));
955 if (wi::le_p (op1
.upper_bound (), op2
.lower_bound (), sign
))
956 r
= range_true (type
);
957 else if (!wi::le_p (op1
.lower_bound (), op2
.upper_bound (), sign
))
958 r
= range_false (type
);
960 r
= range_true_and_false (type
);
965 operator_le::op1_range (irange
&r
, tree type
,
968 relation_kind rel ATTRIBUTE_UNUSED
) const
970 switch (get_bool_state (r
, lhs
, type
))
973 build_le (r
, type
, op2
.upper_bound ());
977 build_gt (r
, type
, op2
.lower_bound ());
987 operator_le::op2_range (irange
&r
, tree type
,
990 relation_kind rel ATTRIBUTE_UNUSED
) const
992 switch (get_bool_state (r
, lhs
, type
))
995 build_lt (r
, type
, op1
.upper_bound ());
999 build_ge (r
, type
, op1
.lower_bound ());
1009 class operator_gt
: public range_operator
1012 virtual bool fold_range (irange
&r
, tree type
,
1015 relation_kind rel
= VREL_NONE
) const;
1016 virtual bool op1_range (irange
&r
, tree type
,
1019 relation_kind rel
= VREL_NONE
) const;
1020 virtual bool op2_range (irange
&r
, tree type
,
1023 relation_kind rel
= VREL_NONE
) const;
1024 virtual enum tree_code
op1_op2_relation (const irange
&lhs
) const;
1027 // Check if the LHS range indicates a relation between OP1 and OP2.
1030 operator_gt::op1_op2_relation (const irange
&lhs
) const
1032 if (lhs
.undefined_p ())
1035 // FALSE = op1 > op2 indicates LE_EXPR.
1039 // TRUE = op1 > op2 indicates GT_EXPR.
1040 if (!lhs
.contains_p (build_zero_cst (lhs
.type ())))
1047 operator_gt::fold_range (irange
&r
, tree type
,
1048 const irange
&op1
, const irange
&op2
,
1049 relation_kind rel
) const
1051 if (relop_early_resolve (r
, type
, op1
, op2
, rel
, GT_EXPR
))
1054 signop sign
= TYPE_SIGN (op1
.type ());
1055 gcc_checking_assert (sign
== TYPE_SIGN (op2
.type ()));
1057 if (wi::gt_p (op1
.lower_bound (), op2
.upper_bound (), sign
))
1058 r
= range_true (type
);
1059 else if (!wi::gt_p (op1
.upper_bound (), op2
.lower_bound (), sign
))
1060 r
= range_false (type
);
1062 r
= range_true_and_false (type
);
1067 operator_gt::op1_range (irange
&r
, tree type
,
1068 const irange
&lhs
, const irange
&op2
,
1069 relation_kind rel ATTRIBUTE_UNUSED
) const
1071 switch (get_bool_state (r
, lhs
, type
))
1074 build_gt (r
, type
, op2
.lower_bound ());
1078 build_le (r
, type
, op2
.upper_bound ());
1088 operator_gt::op2_range (irange
&r
, tree type
,
1091 relation_kind rel ATTRIBUTE_UNUSED
) const
1093 switch (get_bool_state (r
, lhs
, type
))
1096 build_ge (r
, type
, op1
.lower_bound ());
1100 build_lt (r
, type
, op1
.upper_bound ());
1110 class operator_ge
: public range_operator
1113 virtual bool fold_range (irange
&r
, tree type
,
1116 relation_kind rel
= VREL_NONE
) const;
1117 virtual bool op1_range (irange
&r
, tree type
,
1120 relation_kind rel
= VREL_NONE
) const;
1121 virtual bool op2_range (irange
&r
, tree type
,
1124 relation_kind rel
= VREL_NONE
) const;
1125 virtual enum tree_code
op1_op2_relation (const irange
&lhs
) const;
1128 // Check if the LHS range indicates a relation between OP1 and OP2.
1131 operator_ge::op1_op2_relation (const irange
&lhs
) const
1133 if (lhs
.undefined_p ())
1136 // FALSE = op1 >= op2 indicates LT_EXPR.
1140 // TRUE = op1 >= op2 indicates GE_EXPR.
1141 if (!lhs
.contains_p (build_zero_cst (lhs
.type ())))
1147 operator_ge::fold_range (irange
&r
, tree type
,
1150 relation_kind rel
) const
1152 if (relop_early_resolve (r
, type
, op1
, op2
, rel
, GE_EXPR
))
1155 signop sign
= TYPE_SIGN (op1
.type ());
1156 gcc_checking_assert (sign
== TYPE_SIGN (op2
.type ()));
1158 if (wi::ge_p (op1
.lower_bound (), op2
.upper_bound (), sign
))
1159 r
= range_true (type
);
1160 else if (!wi::ge_p (op1
.upper_bound (), op2
.lower_bound (), sign
))
1161 r
= range_false (type
);
1163 r
= range_true_and_false (type
);
1168 operator_ge::op1_range (irange
&r
, tree type
,
1171 relation_kind rel ATTRIBUTE_UNUSED
) const
1173 switch (get_bool_state (r
, lhs
, type
))
1176 build_ge (r
, type
, op2
.lower_bound ());
1180 build_lt (r
, type
, op2
.upper_bound ());
1190 operator_ge::op2_range (irange
&r
, tree type
,
1193 relation_kind rel ATTRIBUTE_UNUSED
) const
1195 switch (get_bool_state (r
, lhs
, type
))
1198 build_gt (r
, type
, op1
.lower_bound ());
1202 build_le (r
, type
, op1
.upper_bound ());
1212 class operator_plus
: public range_operator
1215 virtual bool op1_range (irange
&r
, tree type
,
1218 relation_kind rel ATTRIBUTE_UNUSED
) const;
1219 virtual bool op2_range (irange
&r
, tree type
,
1222 relation_kind rel ATTRIBUTE_UNUSED
) const;
1223 virtual void wi_fold (irange
&r
, tree type
,
1224 const wide_int
&lh_lb
,
1225 const wide_int
&lh_ub
,
1226 const wide_int
&rh_lb
,
1227 const wide_int
&rh_ub
) const;
1228 virtual enum tree_code
lhs_op1_relation (const irange
&lhs
, const irange
&op1
,
1229 const irange
&op2
) const;
1230 virtual enum tree_code
lhs_op2_relation (const irange
&lhs
, const irange
&op1
,
1231 const irange
&op2
) const;
1234 // Check to see if the range of OP2 indicates anything about the relation
1235 // between LHS and OP1.
1238 operator_plus::lhs_op1_relation (const irange
&lhs
,
1240 const irange
&op2
) const
1242 if (lhs
.undefined_p () || op1
.undefined_p () || op2
.undefined_p ())
1245 tree type
= lhs
.type ();
1246 unsigned prec
= TYPE_PRECISION (type
);
1247 wi::overflow_type ovf1
, ovf2
;
1248 signop sign
= TYPE_SIGN (type
);
1250 // LHS = OP1 + 0 indicates LHS == OP1.
1254 if (TYPE_OVERFLOW_WRAPS (type
))
1256 wi::add (op1
.lower_bound (), op2
.lower_bound (), sign
, &ovf1
);
1257 wi::add (op1
.upper_bound (), op2
.upper_bound (), sign
, &ovf2
);
1260 ovf1
= ovf2
= wi::OVF_NONE
;
1262 // Never wrapping additions.
1265 // Positive op2 means lhs > op1.
1266 if (wi::gt_p (op2
.lower_bound (), wi::zero (prec
), sign
))
1268 if (wi::ge_p (op2
.lower_bound (), wi::zero (prec
), sign
))
1271 // Negative op2 means lhs < op1.
1272 if (wi::lt_p (op2
.upper_bound (), wi::zero (prec
), sign
))
1274 if (wi::le_p (op2
.upper_bound (), wi::zero (prec
), sign
))
1277 // Always wrapping additions.
1278 else if (ovf1
&& ovf1
== ovf2
)
1280 // Positive op2 means lhs < op1.
1281 if (wi::gt_p (op2
.lower_bound (), wi::zero (prec
), sign
))
1283 if (wi::ge_p (op2
.lower_bound (), wi::zero (prec
), sign
))
1286 // Negative op2 means lhs > op1.
1287 if (wi::lt_p (op2
.upper_bound (), wi::zero (prec
), sign
))
1289 if (wi::le_p (op2
.upper_bound (), wi::zero (prec
), sign
))
1293 // If op2 does not contain 0, then LHS and OP1 can never be equal.
1294 if (!range_includes_zero_p (&op2
))
1300 // PLUS is symmetrical, so we can simply call lhs_op1_relation with reversed
1304 operator_plus::lhs_op2_relation (const irange
&lhs
, const irange
&op1
,
1305 const irange
&op2
) const
1307 return lhs_op1_relation (lhs
, op2
, op1
);
1311 operator_plus::wi_fold (irange
&r
, tree type
,
1312 const wide_int
&lh_lb
, const wide_int
&lh_ub
,
1313 const wide_int
&rh_lb
, const wide_int
&rh_ub
) const
1315 wi::overflow_type ov_lb
, ov_ub
;
1316 signop s
= TYPE_SIGN (type
);
1317 wide_int new_lb
= wi::add (lh_lb
, rh_lb
, s
, &ov_lb
);
1318 wide_int new_ub
= wi::add (lh_ub
, rh_ub
, s
, &ov_ub
);
1319 value_range_with_overflow (r
, type
, new_lb
, new_ub
, ov_lb
, ov_ub
);
1323 operator_plus::op1_range (irange
&r
, tree type
,
1326 relation_kind rel ATTRIBUTE_UNUSED
) const
1328 return range_op_handler (MINUS_EXPR
, type
)->fold_range (r
, type
, lhs
, op2
);
1332 operator_plus::op2_range (irange
&r
, tree type
,
1335 relation_kind rel ATTRIBUTE_UNUSED
) const
1337 return range_op_handler (MINUS_EXPR
, type
)->fold_range (r
, type
, lhs
, op1
);
1341 class operator_minus
: public range_operator
1344 virtual bool op1_range (irange
&r
, tree type
,
1347 relation_kind rel ATTRIBUTE_UNUSED
) const;
1348 virtual bool op2_range (irange
&r
, tree type
,
1351 relation_kind rel ATTRIBUTE_UNUSED
) const;
1352 virtual void wi_fold (irange
&r
, tree type
,
1353 const wide_int
&lh_lb
,
1354 const wide_int
&lh_ub
,
1355 const wide_int
&rh_lb
,
1356 const wide_int
&rh_ub
) const;
1357 virtual bool op1_op2_relation_effect (irange
&lhs_range
,
1359 const irange
&op1_range
,
1360 const irange
&op2_range
,
1361 relation_kind rel
) const;
1365 operator_minus::wi_fold (irange
&r
, tree type
,
1366 const wide_int
&lh_lb
, const wide_int
&lh_ub
,
1367 const wide_int
&rh_lb
, const wide_int
&rh_ub
) const
1369 wi::overflow_type ov_lb
, ov_ub
;
1370 signop s
= TYPE_SIGN (type
);
1371 wide_int new_lb
= wi::sub (lh_lb
, rh_ub
, s
, &ov_lb
);
1372 wide_int new_ub
= wi::sub (lh_ub
, rh_lb
, s
, &ov_ub
);
1373 value_range_with_overflow (r
, type
, new_lb
, new_ub
, ov_lb
, ov_ub
);
1376 // Check to see if the relation REL between OP1 and OP2 has any effect on the
1377 // LHS of the expression. If so, apply it to LHS_RANGE. This is a helper
1378 // function for both MINUS_EXPR and POINTER_DIFF_EXPR.
1381 minus_op1_op2_relation_effect (irange
&lhs_range
, tree type
,
1382 const irange
&op1_range ATTRIBUTE_UNUSED
,
1383 const irange
&op2_range ATTRIBUTE_UNUSED
,
1386 if (rel
== VREL_NONE
)
1389 int_range
<2> rel_range
;
1390 unsigned prec
= TYPE_PRECISION (type
);
1391 signop sgn
= TYPE_SIGN (type
);
1393 // == and != produce [0,0] and ~[0,0] regardless of wrapping.
1395 rel_range
= int_range
<2> (type
, wi::zero (prec
), wi::zero (prec
));
1396 else if (rel
== NE_EXPR
)
1397 rel_range
= int_range
<2> (type
, wi::zero (prec
), wi::zero (prec
),
1399 else if (TYPE_OVERFLOW_WRAPS (type
))
1403 // For wrapping signed values and unsigned, if op1 > op2 or
1404 // op1 < op2, then op1 - op2 can be restricted to ~[0, 0].
1407 rel_range
= int_range
<2> (type
, wi::zero (prec
), wi::zero (prec
),
1418 // op1 > op2, op1 - op2 can be restricted to [1, +INF]
1420 rel_range
= int_range
<2> (type
, wi::one (prec
),
1421 wi::max_value (prec
, sgn
));
1423 // op1 >= op2, op1 - op2 can be restricted to [0, +INF]
1425 rel_range
= int_range
<2> (type
, wi::zero (prec
),
1426 wi::max_value (prec
, sgn
));
1428 // op1 < op2, op1 - op2 can be restricted to [-INF, -1]
1430 rel_range
= int_range
<2> (type
, wi::min_value (prec
, sgn
),
1431 wi::minus_one (prec
));
1433 // op1 <= op2, op1 - op2 can be restricted to [-INF, 0]
1435 rel_range
= int_range
<2> (type
, wi::min_value (prec
, sgn
),
1442 lhs_range
.intersect (rel_range
);
1447 operator_minus::op1_op2_relation_effect (irange
&lhs_range
, tree type
,
1448 const irange
&op1_range
,
1449 const irange
&op2_range
,
1450 relation_kind rel
) const
1452 return minus_op1_op2_relation_effect (lhs_range
, type
, op1_range
, op2_range
,
1457 operator_minus::op1_range (irange
&r
, tree type
,
1460 relation_kind rel ATTRIBUTE_UNUSED
) const
1462 return range_op_handler (PLUS_EXPR
, type
)->fold_range (r
, type
, lhs
, op2
);
1466 operator_minus::op2_range (irange
&r
, tree type
,
1469 relation_kind rel ATTRIBUTE_UNUSED
) const
1471 return fold_range (r
, type
, op1
, lhs
);
1475 class operator_pointer_diff
: public range_operator
1477 virtual bool op1_op2_relation_effect (irange
&lhs_range
,
1479 const irange
&op1_range
,
1480 const irange
&op2_range
,
1481 relation_kind rel
) const;
1485 operator_pointer_diff::op1_op2_relation_effect (irange
&lhs_range
, tree type
,
1486 const irange
&op1_range
,
1487 const irange
&op2_range
,
1488 relation_kind rel
) const
1490 return minus_op1_op2_relation_effect (lhs_range
, type
, op1_range
, op2_range
,
1495 class operator_min
: public range_operator
1498 virtual void wi_fold (irange
&r
, tree type
,
1499 const wide_int
&lh_lb
,
1500 const wide_int
&lh_ub
,
1501 const wide_int
&rh_lb
,
1502 const wide_int
&rh_ub
) const;
1506 operator_min::wi_fold (irange
&r
, tree type
,
1507 const wide_int
&lh_lb
, const wide_int
&lh_ub
,
1508 const wide_int
&rh_lb
, const wide_int
&rh_ub
) const
1510 signop s
= TYPE_SIGN (type
);
1511 wide_int new_lb
= wi::min (lh_lb
, rh_lb
, s
);
1512 wide_int new_ub
= wi::min (lh_ub
, rh_ub
, s
);
1513 value_range_with_overflow (r
, type
, new_lb
, new_ub
);
1517 class operator_max
: public range_operator
1520 virtual void wi_fold (irange
&r
, tree type
,
1521 const wide_int
&lh_lb
,
1522 const wide_int
&lh_ub
,
1523 const wide_int
&rh_lb
,
1524 const wide_int
&rh_ub
) const;
1528 operator_max::wi_fold (irange
&r
, tree type
,
1529 const wide_int
&lh_lb
, const wide_int
&lh_ub
,
1530 const wide_int
&rh_lb
, const wide_int
&rh_ub
) const
1532 signop s
= TYPE_SIGN (type
);
1533 wide_int new_lb
= wi::max (lh_lb
, rh_lb
, s
);
1534 wide_int new_ub
= wi::max (lh_ub
, rh_ub
, s
);
1535 value_range_with_overflow (r
, type
, new_lb
, new_ub
);
1539 class cross_product_operator
: public range_operator
1542 // Perform an operation between two wide-ints and place the result
1543 // in R. Return true if the operation overflowed.
1544 virtual bool wi_op_overflows (wide_int
&r
,
1547 const wide_int
&) const = 0;
1549 // Calculate the cross product of two sets of sub-ranges and return it.
1550 void wi_cross_product (irange
&r
, tree type
,
1551 const wide_int
&lh_lb
,
1552 const wide_int
&lh_ub
,
1553 const wide_int
&rh_lb
,
1554 const wide_int
&rh_ub
) const;
1557 // Calculate the cross product of two sets of ranges and return it.
1559 // Multiplications, divisions and shifts are a bit tricky to handle,
1560 // depending on the mix of signs we have in the two ranges, we need to
1561 // operate on different values to get the minimum and maximum values
1562 // for the new range. One approach is to figure out all the
1563 // variations of range combinations and do the operations.
1565 // However, this involves several calls to compare_values and it is
1566 // pretty convoluted. It's simpler to do the 4 operations (MIN0 OP
1567 // MIN1, MIN0 OP MAX1, MAX0 OP MIN1 and MAX0 OP MAX0 OP MAX1) and then
1568 // figure the smallest and largest values to form the new range.
1571 cross_product_operator::wi_cross_product (irange
&r
, tree type
,
1572 const wide_int
&lh_lb
,
1573 const wide_int
&lh_ub
,
1574 const wide_int
&rh_lb
,
1575 const wide_int
&rh_ub
) const
1577 wide_int cp1
, cp2
, cp3
, cp4
;
1578 // Default to varying.
1579 r
.set_varying (type
);
1581 // Compute the 4 cross operations, bailing if we get an overflow we
1583 if (wi_op_overflows (cp1
, type
, lh_lb
, rh_lb
))
1585 if (wi::eq_p (lh_lb
, lh_ub
))
1587 else if (wi_op_overflows (cp3
, type
, lh_ub
, rh_lb
))
1589 if (wi::eq_p (rh_lb
, rh_ub
))
1591 else if (wi_op_overflows (cp2
, type
, lh_lb
, rh_ub
))
1593 if (wi::eq_p (lh_lb
, lh_ub
))
1595 else if (wi_op_overflows (cp4
, type
, lh_ub
, rh_ub
))
1599 signop sign
= TYPE_SIGN (type
);
1600 if (wi::gt_p (cp1
, cp2
, sign
))
1601 std::swap (cp1
, cp2
);
1602 if (wi::gt_p (cp3
, cp4
, sign
))
1603 std::swap (cp3
, cp4
);
1605 // Choose min and max from the ordered pairs.
1606 wide_int res_lb
= wi::min (cp1
, cp3
, sign
);
1607 wide_int res_ub
= wi::max (cp2
, cp4
, sign
);
1608 value_range_with_overflow (r
, type
, res_lb
, res_ub
);
1612 class operator_mult
: public cross_product_operator
1615 virtual void wi_fold (irange
&r
, tree type
,
1616 const wide_int
&lh_lb
,
1617 const wide_int
&lh_ub
,
1618 const wide_int
&rh_lb
,
1619 const wide_int
&rh_ub
) const;
1620 virtual bool wi_op_overflows (wide_int
&res
, tree type
,
1621 const wide_int
&w0
, const wide_int
&w1
) const;
1622 virtual bool op1_range (irange
&r
, tree type
,
1625 relation_kind rel ATTRIBUTE_UNUSED
) const;
1626 virtual bool op2_range (irange
&r
, tree type
,
1629 relation_kind rel ATTRIBUTE_UNUSED
) const;
1633 operator_mult::op1_range (irange
&r
, tree type
,
1634 const irange
&lhs
, const irange
&op2
,
1635 relation_kind rel ATTRIBUTE_UNUSED
) const
1639 // We can't solve 0 = OP1 * N by dividing by N with a wrapping type.
1640 // For example: For 0 = OP1 * 2, OP1 could be 0, or MAXINT, whereas
1641 // for 4 = OP1 * 2, OP1 could be 2 or 130 (unsigned 8-bit)
1642 if (TYPE_OVERFLOW_WRAPS (type
))
1645 if (op2
.singleton_p (&offset
) && !integer_zerop (offset
))
1646 return range_op_handler (TRUNC_DIV_EXPR
, type
)->fold_range (r
, type
,
1652 operator_mult::op2_range (irange
&r
, tree type
,
1653 const irange
&lhs
, const irange
&op1
,
1654 relation_kind rel
) const
1656 return operator_mult::op1_range (r
, type
, lhs
, op1
, rel
);
1660 operator_mult::wi_op_overflows (wide_int
&res
, tree type
,
1661 const wide_int
&w0
, const wide_int
&w1
) const
1663 wi::overflow_type overflow
= wi::OVF_NONE
;
1664 signop sign
= TYPE_SIGN (type
);
1665 res
= wi::mul (w0
, w1
, sign
, &overflow
);
1666 if (overflow
&& TYPE_OVERFLOW_UNDEFINED (type
))
1668 // For multiplication, the sign of the overflow is given
1669 // by the comparison of the signs of the operands.
1670 if (sign
== UNSIGNED
|| w0
.sign_mask () == w1
.sign_mask ())
1671 res
= wi::max_value (w0
.get_precision (), sign
);
1673 res
= wi::min_value (w0
.get_precision (), sign
);
1680 operator_mult::wi_fold (irange
&r
, tree type
,
1681 const wide_int
&lh_lb
, const wide_int
&lh_ub
,
1682 const wide_int
&rh_lb
, const wide_int
&rh_ub
) const
1684 if (TYPE_OVERFLOW_UNDEFINED (type
))
1686 wi_cross_product (r
, type
, lh_lb
, lh_ub
, rh_lb
, rh_ub
);
1690 // Multiply the ranges when overflow wraps. This is basically fancy
1691 // code so we don't drop to varying with an unsigned
1694 // This test requires 2*prec bits if both operands are signed and
1695 // 2*prec + 2 bits if either is not. Therefore, extend the values
1696 // using the sign of the result to PREC2. From here on out,
1697 // everthing is just signed math no matter what the input types
1700 signop sign
= TYPE_SIGN (type
);
1701 unsigned prec
= TYPE_PRECISION (type
);
1702 widest2_int min0
= widest2_int::from (lh_lb
, sign
);
1703 widest2_int max0
= widest2_int::from (lh_ub
, sign
);
1704 widest2_int min1
= widest2_int::from (rh_lb
, sign
);
1705 widest2_int max1
= widest2_int::from (rh_ub
, sign
);
1706 widest2_int sizem1
= wi::mask
<widest2_int
> (prec
, false);
1707 widest2_int size
= sizem1
+ 1;
1709 // Canonicalize the intervals.
1710 if (sign
== UNSIGNED
)
1712 if (wi::ltu_p (size
, min0
+ max0
))
1717 if (wi::ltu_p (size
, min1
+ max1
))
1724 // Sort the 4 products so that min is in prod0 and max is in
1726 widest2_int prod0
= min0
* min1
;
1727 widest2_int prod1
= min0
* max1
;
1728 widest2_int prod2
= max0
* min1
;
1729 widest2_int prod3
= max0
* max1
;
1731 // min0min1 > max0max1
1733 std::swap (prod0
, prod3
);
1735 // min0max1 > max0min1
1737 std::swap (prod1
, prod2
);
1740 std::swap (prod0
, prod1
);
1743 std::swap (prod2
, prod3
);
1746 prod2
= prod3
- prod0
;
1747 if (wi::geu_p (prod2
, sizem1
))
1748 // The range covers all values.
1749 r
.set_varying (type
);
1752 wide_int new_lb
= wide_int::from (prod0
, prec
, sign
);
1753 wide_int new_ub
= wide_int::from (prod3
, prec
, sign
);
1754 create_possibly_reversed_range (r
, type
, new_lb
, new_ub
);
1759 class operator_div
: public cross_product_operator
1762 operator_div (enum tree_code c
) { code
= c
; }
1763 virtual void wi_fold (irange
&r
, tree type
,
1764 const wide_int
&lh_lb
,
1765 const wide_int
&lh_ub
,
1766 const wide_int
&rh_lb
,
1767 const wide_int
&rh_ub
) const;
1768 virtual bool wi_op_overflows (wide_int
&res
, tree type
,
1769 const wide_int
&, const wide_int
&) const;
1771 enum tree_code code
;
1775 operator_div::wi_op_overflows (wide_int
&res
, tree type
,
1776 const wide_int
&w0
, const wide_int
&w1
) const
1781 wi::overflow_type overflow
= wi::OVF_NONE
;
1782 signop sign
= TYPE_SIGN (type
);
1786 case EXACT_DIV_EXPR
:
1787 // EXACT_DIV_EXPR is implemented as TRUNC_DIV_EXPR in
1788 // operator_exact_divide. No need to handle it here.
1791 case TRUNC_DIV_EXPR
:
1792 res
= wi::div_trunc (w0
, w1
, sign
, &overflow
);
1794 case FLOOR_DIV_EXPR
:
1795 res
= wi::div_floor (w0
, w1
, sign
, &overflow
);
1797 case ROUND_DIV_EXPR
:
1798 res
= wi::div_round (w0
, w1
, sign
, &overflow
);
1801 res
= wi::div_ceil (w0
, w1
, sign
, &overflow
);
1807 if (overflow
&& TYPE_OVERFLOW_UNDEFINED (type
))
1809 // For division, the only case is -INF / -1 = +INF.
1810 res
= wi::max_value (w0
.get_precision (), sign
);
1817 operator_div::wi_fold (irange
&r
, tree type
,
1818 const wide_int
&lh_lb
, const wide_int
&lh_ub
,
1819 const wide_int
&rh_lb
, const wide_int
&rh_ub
) const
1821 const wide_int dividend_min
= lh_lb
;
1822 const wide_int dividend_max
= lh_ub
;
1823 const wide_int divisor_min
= rh_lb
;
1824 const wide_int divisor_max
= rh_ub
;
1825 signop sign
= TYPE_SIGN (type
);
1826 unsigned prec
= TYPE_PRECISION (type
);
1827 wide_int extra_min
, extra_max
;
1829 // If we know we won't divide by zero, just do the division.
1830 if (!wi_includes_zero_p (type
, divisor_min
, divisor_max
))
1832 wi_cross_product (r
, type
, dividend_min
, dividend_max
,
1833 divisor_min
, divisor_max
);
1837 // If we're definitely dividing by zero, there's nothing to do.
1838 if (wi_zero_p (type
, divisor_min
, divisor_max
))
1844 // Perform the division in 2 parts, [LB, -1] and [1, UB], which will
1845 // skip any division by zero.
1847 // First divide by the negative numbers, if any.
1848 if (wi::neg_p (divisor_min
, sign
))
1849 wi_cross_product (r
, type
, dividend_min
, dividend_max
,
1850 divisor_min
, wi::minus_one (prec
));
1854 // Then divide by the non-zero positive numbers, if any.
1855 if (wi::gt_p (divisor_max
, wi::zero (prec
), sign
))
1858 wi_cross_product (tmp
, type
, dividend_min
, dividend_max
,
1859 wi::one (prec
), divisor_max
);
1862 // We shouldn't still have undefined here.
1863 gcc_checking_assert (!r
.undefined_p ());
1866 operator_div
op_trunc_div (TRUNC_DIV_EXPR
);
1867 operator_div
op_floor_div (FLOOR_DIV_EXPR
);
1868 operator_div
op_round_div (ROUND_DIV_EXPR
);
1869 operator_div
op_ceil_div (CEIL_DIV_EXPR
);
1872 class operator_exact_divide
: public operator_div
1875 operator_exact_divide () : operator_div (TRUNC_DIV_EXPR
) { }
1876 virtual bool op1_range (irange
&r
, tree type
,
1879 relation_kind rel ATTRIBUTE_UNUSED
) const;
1884 operator_exact_divide::op1_range (irange
&r
, tree type
,
1887 relation_kind rel ATTRIBUTE_UNUSED
) const
1890 // [2, 4] = op1 / [3,3] since its exact divide, no need to worry about
1891 // remainders in the endpoints, so op1 = [2,4] * [3,3] = [6,12].
1892 // We wont bother trying to enumerate all the in between stuff :-P
1893 // TRUE accuraacy is [6,6][9,9][12,12]. This is unlikely to matter most of
1894 // the time however.
1895 // If op2 is a multiple of 2, we would be able to set some non-zero bits.
1896 if (op2
.singleton_p (&offset
)
1897 && !integer_zerop (offset
))
1898 return range_op_handler (MULT_EXPR
, type
)->fold_range (r
, type
, lhs
, op2
);
1903 class operator_lshift
: public cross_product_operator
1906 virtual bool op1_range (irange
&r
, tree type
,
1909 relation_kind rel
= VREL_NONE
) const;
1910 virtual bool fold_range (irange
&r
, tree type
,
1913 relation_kind rel
= VREL_NONE
) const;
1915 virtual void wi_fold (irange
&r
, tree type
,
1916 const wide_int
&lh_lb
, const wide_int
&lh_ub
,
1917 const wide_int
&rh_lb
, const wide_int
&rh_ub
) const;
1918 virtual bool wi_op_overflows (wide_int
&res
,
1921 const wide_int
&) const;
1924 class operator_rshift
: public cross_product_operator
1927 virtual bool fold_range (irange
&r
, tree type
,
1930 relation_kind rel
= VREL_NONE
) const;
1931 virtual void wi_fold (irange
&r
, tree type
,
1932 const wide_int
&lh_lb
,
1933 const wide_int
&lh_ub
,
1934 const wide_int
&rh_lb
,
1935 const wide_int
&rh_ub
) const;
1936 virtual bool wi_op_overflows (wide_int
&res
,
1939 const wide_int
&w1
) const;
1940 virtual bool op1_range (irange
&, tree type
,
1943 relation_kind rel
= VREL_NONE
) const;
1944 virtual enum tree_code
lhs_op1_relation (const irange
&lhs
,
1946 const irange
&op2
) const;
1951 operator_rshift::lhs_op1_relation (const irange
&lhs ATTRIBUTE_UNUSED
,
1953 const irange
&op2
) const
1955 // If both operands range are >= 0, then the LHS <= op1.
1956 if (!op1
.undefined_p () && !op2
.undefined_p ()
1957 && wi::ge_p (op1
.lower_bound (), 0, TYPE_SIGN (op1
.type ()))
1958 && wi::ge_p (op2
.lower_bound (), 0, TYPE_SIGN (op2
.type ())))
1964 operator_lshift::fold_range (irange
&r
, tree type
,
1967 relation_kind rel
) const
1969 int_range_max shift_range
;
1970 if (!get_shift_range (shift_range
, type
, op2
))
1972 if (op2
.undefined_p ())
1975 r
.set_varying (type
);
1979 // Transform left shifts by constants into multiplies.
1980 if (shift_range
.singleton_p ())
1982 unsigned shift
= shift_range
.lower_bound ().to_uhwi ();
1983 wide_int tmp
= wi::set_bit_in_zero (shift
, TYPE_PRECISION (type
));
1984 int_range
<1> mult (type
, tmp
, tmp
);
1986 // Force wrapping multiplication.
1987 bool saved_flag_wrapv
= flag_wrapv
;
1988 bool saved_flag_wrapv_pointer
= flag_wrapv_pointer
;
1990 flag_wrapv_pointer
= 1;
1991 bool b
= op_mult
.fold_range (r
, type
, op1
, mult
);
1992 flag_wrapv
= saved_flag_wrapv
;
1993 flag_wrapv_pointer
= saved_flag_wrapv_pointer
;
1997 // Otherwise, invoke the generic fold routine.
1998 return range_operator::fold_range (r
, type
, op1
, shift_range
, rel
);
2002 operator_lshift::wi_fold (irange
&r
, tree type
,
2003 const wide_int
&lh_lb
, const wide_int
&lh_ub
,
2004 const wide_int
&rh_lb
, const wide_int
&rh_ub
) const
2006 signop sign
= TYPE_SIGN (type
);
2007 unsigned prec
= TYPE_PRECISION (type
);
2008 int overflow_pos
= sign
== SIGNED
? prec
- 1 : prec
;
2009 int bound_shift
= overflow_pos
- rh_ub
.to_shwi ();
2010 // If bound_shift == HOST_BITS_PER_WIDE_INT, the llshift can
2011 // overflow. However, for that to happen, rh.max needs to be zero,
2012 // which means rh is a singleton range of zero, which means we simply return
2013 // [lh_lb, lh_ub] as the range.
2014 if (wi::eq_p (rh_ub
, rh_lb
) && wi::eq_p (rh_ub
, 0))
2016 r
= int_range
<2> (type
, lh_lb
, lh_ub
);
2020 wide_int bound
= wi::set_bit_in_zero (bound_shift
, prec
);
2021 wide_int complement
= ~(bound
- 1);
2022 wide_int low_bound
, high_bound
;
2023 bool in_bounds
= false;
2025 if (sign
== UNSIGNED
)
2028 high_bound
= complement
;
2029 if (wi::ltu_p (lh_ub
, low_bound
))
2031 // [5, 6] << [1, 2] == [10, 24].
2032 // We're shifting out only zeroes, the value increases
2036 else if (wi::ltu_p (high_bound
, lh_lb
))
2038 // [0xffffff00, 0xffffffff] << [1, 2]
2039 // == [0xfffffc00, 0xfffffffe].
2040 // We're shifting out only ones, the value decreases
2047 // [-1, 1] << [1, 2] == [-4, 4]
2048 low_bound
= complement
;
2050 if (wi::lts_p (lh_ub
, high_bound
)
2051 && wi::lts_p (low_bound
, lh_lb
))
2053 // For non-negative numbers, we're shifting out only zeroes,
2054 // the value increases monotonically. For negative numbers,
2055 // we're shifting out only ones, the value decreases
2062 wi_cross_product (r
, type
, lh_lb
, lh_ub
, rh_lb
, rh_ub
);
2064 r
.set_varying (type
);
2068 operator_lshift::wi_op_overflows (wide_int
&res
, tree type
,
2069 const wide_int
&w0
, const wide_int
&w1
) const
2071 signop sign
= TYPE_SIGN (type
);
2074 // It's unclear from the C standard whether shifts can overflow.
2075 // The following code ignores overflow; perhaps a C standard
2076 // interpretation ruling is needed.
2077 res
= wi::rshift (w0
, -w1
, sign
);
2080 res
= wi::lshift (w0
, w1
);
2085 operator_lshift::op1_range (irange
&r
,
2089 relation_kind rel ATTRIBUTE_UNUSED
) const
2093 if (!lhs
.contains_p (build_zero_cst (type
)))
2094 r
.set_nonzero (type
);
2096 r
.set_varying (type
);
2098 if (op2
.singleton_p (&shift_amount
))
2100 wide_int shift
= wi::to_wide (shift_amount
);
2101 if (wi::lt_p (shift
, 0, SIGNED
))
2103 if (wi::ge_p (shift
, wi::uhwi (TYPE_PRECISION (type
),
2104 TYPE_PRECISION (op2
.type ())),
2113 // Work completely in unsigned mode to start.
2115 int_range_max tmp_range
;
2116 if (TYPE_SIGN (type
) == SIGNED
)
2118 int_range_max tmp
= lhs
;
2119 utype
= unsigned_type_for (type
);
2120 range_cast (tmp
, utype
);
2121 op_rshift
.fold_range (tmp_range
, utype
, tmp
, op2
);
2124 op_rshift
.fold_range (tmp_range
, utype
, lhs
, op2
);
2126 // Start with ranges which can produce the LHS by right shifting the
2127 // result by the shift amount.
2128 // ie [0x08, 0xF0] = op1 << 2 will start with
2129 // [00001000, 11110000] = op1 << 2
2130 // [0x02, 0x4C] aka [00000010, 00111100]
2132 // Then create a range from the LB with the least significant upper bit
2133 // set, to the upper bound with all the bits set.
2134 // This would be [0x42, 0xFC] aka [01000010, 11111100].
2136 // Ideally we do this for each subrange, but just lump them all for now.
2137 unsigned low_bits
= TYPE_PRECISION (utype
)
2138 - TREE_INT_CST_LOW (shift_amount
);
2139 wide_int up_mask
= wi::mask (low_bits
, true, TYPE_PRECISION (utype
));
2140 wide_int new_ub
= wi::bit_or (up_mask
, tmp_range
.upper_bound ());
2141 wide_int new_lb
= wi::set_bit (tmp_range
.lower_bound (), low_bits
);
2142 int_range
<2> fill_range (utype
, new_lb
, new_ub
);
2143 tmp_range
.union_ (fill_range
);
2146 range_cast (tmp_range
, type
);
2148 r
.intersect (tmp_range
);
2152 return !r
.varying_p ();
2156 operator_rshift::op1_range (irange
&r
,
2160 relation_kind rel ATTRIBUTE_UNUSED
) const
2163 if (op2
.singleton_p (&shift
))
2165 // Ignore nonsensical shifts.
2166 unsigned prec
= TYPE_PRECISION (type
);
2167 if (wi::ge_p (wi::to_wide (shift
),
2168 wi::uhwi (prec
, TYPE_PRECISION (TREE_TYPE (shift
))),
2171 if (wi::to_wide (shift
) == 0)
2177 // Folding the original operation may discard some impossible
2178 // ranges from the LHS.
2179 int_range_max lhs_refined
;
2180 op_rshift
.fold_range (lhs_refined
, type
, int_range
<1> (type
), op2
);
2181 lhs_refined
.intersect (lhs
);
2182 if (lhs_refined
.undefined_p ())
2187 int_range_max
shift_range (shift
, shift
);
2188 int_range_max lb
, ub
;
2189 op_lshift
.fold_range (lb
, type
, lhs_refined
, shift_range
);
2191 // 0000 0111 = OP1 >> 3
2193 // OP1 is anything from 0011 1000 to 0011 1111. That is, a
2194 // range from LHS<<3 plus a mask of the 3 bits we shifted on the
2195 // right hand side (0x07).
2196 tree mask
= fold_build1 (BIT_NOT_EXPR
, type
,
2197 fold_build2 (LSHIFT_EXPR
, type
,
2198 build_minus_one_cst (type
),
2200 int_range_max
mask_range (build_zero_cst (type
), mask
);
2201 op_plus
.fold_range (ub
, type
, lb
, mask_range
);
2204 if (!lhs_refined
.contains_p (build_zero_cst (type
)))
2206 mask_range
.invert ();
2207 r
.intersect (mask_range
);
2215 operator_rshift::wi_op_overflows (wide_int
&res
,
2218 const wide_int
&w1
) const
2220 signop sign
= TYPE_SIGN (type
);
2222 res
= wi::lshift (w0
, -w1
);
2225 // It's unclear from the C standard whether shifts can overflow.
2226 // The following code ignores overflow; perhaps a C standard
2227 // interpretation ruling is needed.
2228 res
= wi::rshift (w0
, w1
, sign
);
2234 operator_rshift::fold_range (irange
&r
, tree type
,
2237 relation_kind rel
) const
2239 int_range_max shift
;
2240 if (!get_shift_range (shift
, type
, op2
))
2242 if (op2
.undefined_p ())
2245 r
.set_varying (type
);
2249 return range_operator::fold_range (r
, type
, op1
, shift
, rel
);
2253 operator_rshift::wi_fold (irange
&r
, tree type
,
2254 const wide_int
&lh_lb
, const wide_int
&lh_ub
,
2255 const wide_int
&rh_lb
, const wide_int
&rh_ub
) const
2257 wi_cross_product (r
, type
, lh_lb
, lh_ub
, rh_lb
, rh_ub
);
2261 class operator_cast
: public range_operator
2264 virtual bool fold_range (irange
&r
, tree type
,
2267 relation_kind rel
= VREL_NONE
) const;
2268 virtual bool op1_range (irange
&r
, tree type
,
2271 relation_kind rel
= VREL_NONE
) const;
2273 bool truncating_cast_p (const irange
&inner
, const irange
&outer
) const;
2274 bool inside_domain_p (const wide_int
&min
, const wide_int
&max
,
2275 const irange
&outer
) const;
2276 void fold_pair (irange
&r
, unsigned index
, const irange
&inner
,
2277 const irange
&outer
) const;
2280 // Return TRUE if casting from INNER to OUTER is a truncating cast.
2283 operator_cast::truncating_cast_p (const irange
&inner
,
2284 const irange
&outer
) const
2286 return TYPE_PRECISION (outer
.type ()) < TYPE_PRECISION (inner
.type ());
2289 // Return TRUE if [MIN,MAX] is inside the domain of RANGE's type.
2292 operator_cast::inside_domain_p (const wide_int
&min
,
2293 const wide_int
&max
,
2294 const irange
&range
) const
2296 wide_int domain_min
= wi::to_wide (vrp_val_min (range
.type ()));
2297 wide_int domain_max
= wi::to_wide (vrp_val_max (range
.type ()));
2298 signop domain_sign
= TYPE_SIGN (range
.type ());
2299 return (wi::le_p (min
, domain_max
, domain_sign
)
2300 && wi::le_p (max
, domain_max
, domain_sign
)
2301 && wi::ge_p (min
, domain_min
, domain_sign
)
2302 && wi::ge_p (max
, domain_min
, domain_sign
));
2306 // Helper for fold_range which work on a pair at a time.
2309 operator_cast::fold_pair (irange
&r
, unsigned index
,
2310 const irange
&inner
,
2311 const irange
&outer
) const
2313 tree inner_type
= inner
.type ();
2314 tree outer_type
= outer
.type ();
2315 signop inner_sign
= TYPE_SIGN (inner_type
);
2316 unsigned outer_prec
= TYPE_PRECISION (outer_type
);
2318 // check to see if casting from INNER to OUTER is a conversion that
2319 // fits in the resulting OUTER type.
2320 wide_int inner_lb
= inner
.lower_bound (index
);
2321 wide_int inner_ub
= inner
.upper_bound (index
);
2322 if (truncating_cast_p (inner
, outer
))
2324 // We may be able to accomodate a truncating cast if the
2325 // resulting range can be represented in the target type...
2326 if (wi::rshift (wi::sub (inner_ub
, inner_lb
),
2327 wi::uhwi (outer_prec
, TYPE_PRECISION (inner
.type ())),
2330 r
.set_varying (outer_type
);
2334 // ...but we must still verify that the final range fits in the
2335 // domain. This catches -fstrict-enum restrictions where the domain
2336 // range is smaller than what fits in the underlying type.
2337 wide_int min
= wide_int::from (inner_lb
, outer_prec
, inner_sign
);
2338 wide_int max
= wide_int::from (inner_ub
, outer_prec
, inner_sign
);
2339 if (inside_domain_p (min
, max
, outer
))
2340 create_possibly_reversed_range (r
, outer_type
, min
, max
);
2342 r
.set_varying (outer_type
);
2347 operator_cast::fold_range (irange
&r
, tree type ATTRIBUTE_UNUSED
,
2348 const irange
&inner
,
2349 const irange
&outer
,
2350 relation_kind rel ATTRIBUTE_UNUSED
) const
2352 if (empty_range_varying (r
, type
, inner
, outer
))
2355 gcc_checking_assert (outer
.varying_p ());
2356 gcc_checking_assert (inner
.num_pairs () > 0);
2358 // Avoid a temporary by folding the first pair directly into the result.
2359 fold_pair (r
, 0, inner
, outer
);
2361 // Then process any additonal pairs by unioning with their results.
2362 for (unsigned x
= 1; x
< inner
.num_pairs (); ++x
)
2365 fold_pair (tmp
, x
, inner
, outer
);
2374 operator_cast::op1_range (irange
&r
, tree type
,
2377 relation_kind rel ATTRIBUTE_UNUSED
) const
2379 tree lhs_type
= lhs
.type ();
2380 gcc_checking_assert (types_compatible_p (op2
.type(), type
));
2382 // If we are calculating a pointer, shortcut to what we really care about.
2383 if (POINTER_TYPE_P (type
))
2385 // Conversion from other pointers or a constant (including 0/NULL)
2386 // are straightforward.
2387 if (POINTER_TYPE_P (lhs
.type ())
2388 || (lhs
.singleton_p ()
2389 && TYPE_PRECISION (lhs
.type ()) >= TYPE_PRECISION (type
)))
2392 range_cast (r
, type
);
2396 // If the LHS is not a pointer nor a singleton, then it is
2397 // either VARYING or non-zero.
2398 if (!lhs
.contains_p (build_zero_cst (lhs
.type ())))
2399 r
.set_nonzero (type
);
2401 r
.set_varying (type
);
2407 if (truncating_cast_p (op2
, lhs
))
2409 if (lhs
.varying_p ())
2410 r
.set_varying (type
);
2413 // We want to insert the LHS as an unsigned value since it
2414 // would not trigger the signed bit of the larger type.
2415 int_range_max converted_lhs
= lhs
;
2416 range_cast (converted_lhs
, unsigned_type_for (lhs_type
));
2417 range_cast (converted_lhs
, type
);
2418 // Start by building the positive signed outer range for the type.
2419 wide_int lim
= wi::set_bit_in_zero (TYPE_PRECISION (lhs_type
),
2420 TYPE_PRECISION (type
));
2421 r
= int_range
<1> (type
, lim
, wi::max_value (TYPE_PRECISION (type
),
2423 // For the signed part, we need to simply union the 2 ranges now.
2424 r
.union_ (converted_lhs
);
2426 // Create maximal negative number outside of LHS bits.
2427 lim
= wi::mask (TYPE_PRECISION (lhs_type
), true,
2428 TYPE_PRECISION (type
));
2429 // Add this to the unsigned LHS range(s).
2430 int_range_max
lim_range (type
, lim
, lim
);
2431 int_range_max lhs_neg
;
2432 range_op_handler (PLUS_EXPR
, type
)->fold_range (lhs_neg
,
2436 // lhs_neg now has all the negative versions of the LHS.
2437 // Now union in all the values from SIGNED MIN (0x80000) to
2438 // lim-1 in order to fill in all the ranges with the upper
2441 // PR 97317. If the lhs has only 1 bit less precision than the rhs,
2442 // we don't need to create a range from min to lim-1
2443 // calculate neg range traps trying to create [lim, lim - 1].
2444 wide_int min_val
= wi::min_value (TYPE_PRECISION (type
), SIGNED
);
2447 int_range_max
neg (type
,
2448 wi::min_value (TYPE_PRECISION (type
),
2451 lhs_neg
.union_ (neg
);
2453 // And finally, munge the signed and unsigned portions.
2456 // And intersect with any known value passed in the extra operand.
2462 if (TYPE_PRECISION (lhs_type
) == TYPE_PRECISION (type
))
2466 // The cast is not truncating, and the range is restricted to
2467 // the range of the RHS by this assignment.
2469 // Cast the range of the RHS to the type of the LHS.
2470 fold_range (tmp
, lhs_type
, int_range
<1> (type
), int_range
<1> (lhs_type
));
2471 // Intersect this with the LHS range will produce the range,
2472 // which will be cast to the RHS type before returning.
2473 tmp
.intersect (lhs
);
2476 // Cast the calculated range to the type of the RHS.
2477 fold_range (r
, type
, tmp
, int_range
<1> (type
));
2482 class operator_logical_and
: public range_operator
2485 virtual bool fold_range (irange
&r
, tree type
,
2488 relation_kind rel
= VREL_NONE
) const;
2489 virtual bool op1_range (irange
&r
, tree type
,
2492 relation_kind rel
= VREL_NONE
) const;
2493 virtual bool op2_range (irange
&r
, tree type
,
2496 relation_kind rel
= VREL_NONE
) const;
2501 operator_logical_and::fold_range (irange
&r
, tree type
,
2504 relation_kind rel ATTRIBUTE_UNUSED
) const
2506 if (empty_range_varying (r
, type
, lh
, rh
))
2509 // 0 && anything is 0.
2510 if ((wi::eq_p (lh
.lower_bound (), 0) && wi::eq_p (lh
.upper_bound (), 0))
2511 || (wi::eq_p (lh
.lower_bound (), 0) && wi::eq_p (rh
.upper_bound (), 0)))
2512 r
= range_false (type
);
2513 else if (lh
.contains_p (build_zero_cst (lh
.type ()))
2514 || rh
.contains_p (build_zero_cst (rh
.type ())))
2515 // To reach this point, there must be a logical 1 on each side, and
2516 // the only remaining question is whether there is a zero or not.
2517 r
= range_true_and_false (type
);
2519 r
= range_true (type
);
2524 operator_logical_and::op1_range (irange
&r
, tree type
,
2526 const irange
&op2 ATTRIBUTE_UNUSED
,
2527 relation_kind rel ATTRIBUTE_UNUSED
) const
2529 switch (get_bool_state (r
, lhs
, type
))
2532 // A true result means both sides of the AND must be true.
2533 r
= range_true (type
);
2536 // Any other result means only one side has to be false, the
2537 // other side can be anything. So we cannott be sure of any
2539 r
= range_true_and_false (type
);
2546 operator_logical_and::op2_range (irange
&r
, tree type
,
2549 relation_kind rel ATTRIBUTE_UNUSED
) const
2551 return operator_logical_and::op1_range (r
, type
, lhs
, op1
);
2555 class operator_bitwise_and
: public range_operator
2558 virtual bool fold_range (irange
&r
, tree type
,
2561 relation_kind rel
= VREL_NONE
) const;
2562 virtual bool op1_range (irange
&r
, tree type
,
2565 relation_kind rel
= VREL_NONE
) const;
2566 virtual bool op2_range (irange
&r
, tree type
,
2569 relation_kind rel
= VREL_NONE
) const;
2570 virtual void wi_fold (irange
&r
, tree type
,
2571 const wide_int
&lh_lb
,
2572 const wide_int
&lh_ub
,
2573 const wide_int
&rh_lb
,
2574 const wide_int
&rh_ub
) const;
2576 void simple_op1_range_solver (irange
&r
, tree type
,
2578 const irange
&op2
) const;
2579 void remove_impossible_ranges (irange
&r
, const irange
&rh
) const;
2583 unsigned_singleton_p (const irange
&op
)
2586 if (op
.singleton_p (&mask
))
2588 wide_int x
= wi::to_wide (mask
);
2589 return wi::ge_p (x
, 0, TYPE_SIGN (op
.type ()));
2594 // Remove any ranges from R that are known to be impossible when an
2595 // range is ANDed with MASK.
2598 operator_bitwise_and::remove_impossible_ranges (irange
&r
,
2599 const irange
&rmask
) const
2601 if (r
.undefined_p () || !unsigned_singleton_p (rmask
))
2604 wide_int mask
= rmask
.lower_bound ();
2605 tree type
= r
.type ();
2606 int prec
= TYPE_PRECISION (type
);
2607 int leading_zeros
= wi::clz (mask
);
2608 int_range_max impossible_ranges
;
2610 /* We know that starting at the most significant bit, any 0 in the
2611 mask means the resulting range cannot contain a 1 in that same
2612 position. This means the following ranges are impossible:
2616 01xx xxxx [0100 0000, 0111 1111]
2617 001x xxxx [0010 0000, 0011 1111]
2618 0000 01xx [0000 0100, 0000 0111]
2619 0000 0001 [0000 0001, 0000 0001]
2621 wide_int one
= wi::one (prec
);
2622 for (int i
= 0; i
< prec
- leading_zeros
- 1; ++i
)
2623 if (wi::bit_and (mask
, wi::lshift (one
, wi::uhwi (i
, prec
))) == 0)
2625 tree lb
= fold_build2 (LSHIFT_EXPR
, type
,
2626 build_one_cst (type
),
2627 build_int_cst (type
, i
));
2628 tree ub_left
= fold_build1 (BIT_NOT_EXPR
, type
,
2629 fold_build2 (LSHIFT_EXPR
, type
,
2630 build_minus_one_cst (type
),
2631 build_int_cst (type
, i
)));
2632 tree ub_right
= fold_build2 (LSHIFT_EXPR
, type
,
2633 build_one_cst (type
),
2634 build_int_cst (type
, i
));
2635 tree ub
= fold_build2 (BIT_IOR_EXPR
, type
, ub_left
, ub_right
);
2636 impossible_ranges
.union_ (int_range
<1> (lb
, ub
));
2638 if (!impossible_ranges
.undefined_p ())
2640 impossible_ranges
.invert ();
2641 r
.intersect (impossible_ranges
);
2646 operator_bitwise_and::fold_range (irange
&r
, tree type
,
2649 relation_kind rel ATTRIBUTE_UNUSED
) const
2651 if (range_operator::fold_range (r
, type
, lh
, rh
))
2653 // FIXME: This is temporarily disabled because, though it
2654 // generates better ranges, it's noticeably slower for evrp.
2655 // remove_impossible_ranges (r, rh);
2662 // Optimize BIT_AND_EXPR and BIT_IOR_EXPR in terms of a mask if
2663 // possible. Basically, see if we can optimize:
2667 // [LB op Z, UB op Z]
2669 // If the optimization was successful, accumulate the range in R and
2673 wi_optimize_and_or (irange
&r
,
2674 enum tree_code code
,
2676 const wide_int
&lh_lb
, const wide_int
&lh_ub
,
2677 const wide_int
&rh_lb
, const wide_int
&rh_ub
)
2679 // Calculate the singleton mask among the ranges, if any.
2680 wide_int lower_bound
, upper_bound
, mask
;
2681 if (wi::eq_p (rh_lb
, rh_ub
))
2684 lower_bound
= lh_lb
;
2685 upper_bound
= lh_ub
;
2687 else if (wi::eq_p (lh_lb
, lh_ub
))
2690 lower_bound
= rh_lb
;
2691 upper_bound
= rh_ub
;
2696 // If Z is a constant which (for op | its bitwise not) has n
2697 // consecutive least significant bits cleared followed by m 1
2698 // consecutive bits set immediately above it and either
2699 // m + n == precision, or (x >> (m + n)) == (y >> (m + n)).
2701 // The least significant n bits of all the values in the range are
2702 // cleared or set, the m bits above it are preserved and any bits
2703 // above these are required to be the same for all values in the
2707 if (code
== BIT_IOR_EXPR
)
2709 if (wi::eq_p (w
, 0))
2710 n
= w
.get_precision ();
2714 w
= ~(w
| wi::mask (n
, false, w
.get_precision ()));
2715 if (wi::eq_p (w
, 0))
2716 m
= w
.get_precision () - n
;
2718 m
= wi::ctz (w
) - n
;
2720 wide_int new_mask
= wi::mask (m
+ n
, true, w
.get_precision ());
2721 if ((new_mask
& lower_bound
) != (new_mask
& upper_bound
))
2724 wide_int res_lb
, res_ub
;
2725 if (code
== BIT_AND_EXPR
)
2727 res_lb
= wi::bit_and (lower_bound
, mask
);
2728 res_ub
= wi::bit_and (upper_bound
, mask
);
2730 else if (code
== BIT_IOR_EXPR
)
2732 res_lb
= wi::bit_or (lower_bound
, mask
);
2733 res_ub
= wi::bit_or (upper_bound
, mask
);
2737 value_range_with_overflow (r
, type
, res_lb
, res_ub
);
2739 // Furthermore, if the mask is non-zero, an IOR cannot contain zero.
2740 if (code
== BIT_IOR_EXPR
&& wi::ne_p (mask
, 0))
2743 tmp
.set_nonzero (type
);
2749 // For range [LB, UB] compute two wide_int bit masks.
2751 // In the MAYBE_NONZERO bit mask, if some bit is unset, it means that
2752 // for all numbers in the range the bit is 0, otherwise it might be 0
2755 // In the MUSTBE_NONZERO bit mask, if some bit is set, it means that
2756 // for all numbers in the range the bit is 1, otherwise it might be 0
2760 wi_set_zero_nonzero_bits (tree type
,
2761 const wide_int
&lb
, const wide_int
&ub
,
2762 wide_int
&maybe_nonzero
,
2763 wide_int
&mustbe_nonzero
)
2765 signop sign
= TYPE_SIGN (type
);
2767 if (wi::eq_p (lb
, ub
))
2768 maybe_nonzero
= mustbe_nonzero
= lb
;
2769 else if (wi::ge_p (lb
, 0, sign
) || wi::lt_p (ub
, 0, sign
))
2771 wide_int xor_mask
= lb
^ ub
;
2772 maybe_nonzero
= lb
| ub
;
2773 mustbe_nonzero
= lb
& ub
;
2776 wide_int mask
= wi::mask (wi::floor_log2 (xor_mask
), false,
2777 maybe_nonzero
.get_precision ());
2778 maybe_nonzero
= maybe_nonzero
| mask
;
2779 mustbe_nonzero
= wi::bit_and_not (mustbe_nonzero
, mask
);
2784 maybe_nonzero
= wi::minus_one (lb
.get_precision ());
2785 mustbe_nonzero
= wi::zero (lb
.get_precision ());
2790 operator_bitwise_and::wi_fold (irange
&r
, tree type
,
2791 const wide_int
&lh_lb
,
2792 const wide_int
&lh_ub
,
2793 const wide_int
&rh_lb
,
2794 const wide_int
&rh_ub
) const
2796 if (wi_optimize_and_or (r
, BIT_AND_EXPR
, type
, lh_lb
, lh_ub
, rh_lb
, rh_ub
))
2799 wide_int maybe_nonzero_lh
, mustbe_nonzero_lh
;
2800 wide_int maybe_nonzero_rh
, mustbe_nonzero_rh
;
2801 wi_set_zero_nonzero_bits (type
, lh_lb
, lh_ub
,
2802 maybe_nonzero_lh
, mustbe_nonzero_lh
);
2803 wi_set_zero_nonzero_bits (type
, rh_lb
, rh_ub
,
2804 maybe_nonzero_rh
, mustbe_nonzero_rh
);
2806 wide_int new_lb
= mustbe_nonzero_lh
& mustbe_nonzero_rh
;
2807 wide_int new_ub
= maybe_nonzero_lh
& maybe_nonzero_rh
;
2808 signop sign
= TYPE_SIGN (type
);
2809 unsigned prec
= TYPE_PRECISION (type
);
2810 // If both input ranges contain only negative values, we can
2811 // truncate the result range maximum to the minimum of the
2812 // input range maxima.
2813 if (wi::lt_p (lh_ub
, 0, sign
) && wi::lt_p (rh_ub
, 0, sign
))
2815 new_ub
= wi::min (new_ub
, lh_ub
, sign
);
2816 new_ub
= wi::min (new_ub
, rh_ub
, sign
);
2818 // If either input range contains only non-negative values
2819 // we can truncate the result range maximum to the respective
2820 // maximum of the input range.
2821 if (wi::ge_p (lh_lb
, 0, sign
))
2822 new_ub
= wi::min (new_ub
, lh_ub
, sign
);
2823 if (wi::ge_p (rh_lb
, 0, sign
))
2824 new_ub
= wi::min (new_ub
, rh_ub
, sign
);
2825 // PR68217: In case of signed & sign-bit-CST should
2826 // result in [-INF, 0] instead of [-INF, INF].
2827 if (wi::gt_p (new_lb
, new_ub
, sign
))
2829 wide_int sign_bit
= wi::set_bit_in_zero (prec
- 1, prec
);
2831 && ((wi::eq_p (lh_lb
, lh_ub
)
2832 && !wi::cmps (lh_lb
, sign_bit
))
2833 || (wi::eq_p (rh_lb
, rh_ub
)
2834 && !wi::cmps (rh_lb
, sign_bit
))))
2836 new_lb
= wi::min_value (prec
, sign
);
2837 new_ub
= wi::zero (prec
);
2840 // If the limits got swapped around, return varying.
2841 if (wi::gt_p (new_lb
, new_ub
,sign
))
2842 r
.set_varying (type
);
2844 value_range_with_overflow (r
, type
, new_lb
, new_ub
);
2848 set_nonzero_range_from_mask (irange
&r
, tree type
, const irange
&lhs
)
2850 if (!lhs
.contains_p (build_zero_cst (type
)))
2851 r
= range_nonzero (type
);
2853 r
.set_varying (type
);
2856 // This was shamelessly stolen from register_edge_assert_for_2 and
2857 // adjusted to work with iranges.
2860 operator_bitwise_and::simple_op1_range_solver (irange
&r
, tree type
,
2862 const irange
&op2
) const
2864 if (!op2
.singleton_p ())
2866 set_nonzero_range_from_mask (r
, type
, lhs
);
2869 unsigned int nprec
= TYPE_PRECISION (type
);
2870 wide_int cst2v
= op2
.lower_bound ();
2871 bool cst2n
= wi::neg_p (cst2v
, TYPE_SIGN (type
));
2874 sgnbit
= wi::set_bit_in_zero (nprec
- 1, nprec
);
2876 sgnbit
= wi::zero (nprec
);
2878 // Solve [lhs.lower_bound (), +INF] = x & MASK.
2880 // Minimum unsigned value for >= if (VAL & CST2) == VAL is VAL and
2881 // maximum unsigned value is ~0. For signed comparison, if CST2
2882 // doesn't have the most significant bit set, handle it similarly. If
2883 // CST2 has MSB set, the minimum is the same, and maximum is ~0U/2.
2884 wide_int valv
= lhs
.lower_bound ();
2885 wide_int minv
= valv
& cst2v
, maxv
;
2886 bool we_know_nothing
= false;
2889 // If (VAL & CST2) != VAL, X & CST2 can't be equal to VAL.
2890 minv
= masked_increment (valv
, cst2v
, sgnbit
, nprec
);
2893 // If we can't determine anything on this bound, fall
2894 // through and conservatively solve for the other end point.
2895 we_know_nothing
= true;
2898 maxv
= wi::mask (nprec
- (cst2n
? 1 : 0), false, nprec
);
2899 if (we_know_nothing
)
2900 r
.set_varying (type
);
2902 r
= int_range
<1> (type
, minv
, maxv
);
2904 // Solve [-INF, lhs.upper_bound ()] = x & MASK.
2906 // Minimum unsigned value for <= is 0 and maximum unsigned value is
2907 // VAL | ~CST2 if (VAL & CST2) == VAL. Otherwise, find smallest
2909 // VAL2 > VAL && (VAL2 & CST2) == VAL2 and use (VAL2 - 1) | ~CST2
2911 // For signed comparison, if CST2 doesn't have most significant bit
2912 // set, handle it similarly. If CST2 has MSB set, the maximum is
2913 // the same and minimum is INT_MIN.
2914 valv
= lhs
.upper_bound ();
2915 minv
= valv
& cst2v
;
2920 maxv
= masked_increment (valv
, cst2v
, sgnbit
, nprec
);
2923 // If we couldn't determine anything on either bound, return
2925 if (we_know_nothing
)
2933 int_range
<1> upper_bits (type
, minv
, maxv
);
2934 r
.intersect (upper_bits
);
2938 operator_bitwise_and::op1_range (irange
&r
, tree type
,
2941 relation_kind rel ATTRIBUTE_UNUSED
) const
2943 if (types_compatible_p (type
, boolean_type_node
))
2944 return op_logical_and
.op1_range (r
, type
, lhs
, op2
);
2947 for (unsigned i
= 0; i
< lhs
.num_pairs (); ++i
)
2949 int_range_max
chunk (lhs
.type (),
2950 lhs
.lower_bound (i
),
2951 lhs
.upper_bound (i
));
2953 simple_op1_range_solver (res
, type
, chunk
, op2
);
2956 if (r
.undefined_p ())
2957 set_nonzero_range_from_mask (r
, type
, lhs
);
2962 operator_bitwise_and::op2_range (irange
&r
, tree type
,
2965 relation_kind rel ATTRIBUTE_UNUSED
) const
2967 return operator_bitwise_and::op1_range (r
, type
, lhs
, op1
);
2971 class operator_logical_or
: public range_operator
2974 virtual bool fold_range (irange
&r
, tree type
,
2977 relation_kind rel
= VREL_NONE
) const;
2978 virtual bool op1_range (irange
&r
, tree type
,
2981 relation_kind rel
= VREL_NONE
) const;
2982 virtual bool op2_range (irange
&r
, tree type
,
2985 relation_kind rel
= VREL_NONE
) const;
2989 operator_logical_or::fold_range (irange
&r
, tree type ATTRIBUTE_UNUSED
,
2992 relation_kind rel ATTRIBUTE_UNUSED
) const
2994 if (empty_range_varying (r
, type
, lh
, rh
))
3003 operator_logical_or::op1_range (irange
&r
, tree type
,
3005 const irange
&op2 ATTRIBUTE_UNUSED
,
3006 relation_kind rel ATTRIBUTE_UNUSED
) const
3008 switch (get_bool_state (r
, lhs
, type
))
3011 // A false result means both sides of the OR must be false.
3012 r
= range_false (type
);
3015 // Any other result means only one side has to be true, the
3016 // other side can be anything. so we can't be sure of any result
3018 r
= range_true_and_false (type
);
3025 operator_logical_or::op2_range (irange
&r
, tree type
,
3028 relation_kind rel ATTRIBUTE_UNUSED
) const
3030 return operator_logical_or::op1_range (r
, type
, lhs
, op1
);
3034 class operator_bitwise_or
: public range_operator
3037 virtual bool op1_range (irange
&r
, tree type
,
3040 relation_kind rel
= VREL_NONE
) const;
3041 virtual bool op2_range (irange
&r
, tree type
,
3044 relation_kind rel
= VREL_NONE
) const;
3045 virtual void wi_fold (irange
&r
, tree type
,
3046 const wide_int
&lh_lb
,
3047 const wide_int
&lh_ub
,
3048 const wide_int
&rh_lb
,
3049 const wide_int
&rh_ub
) const;
3053 operator_bitwise_or::wi_fold (irange
&r
, tree type
,
3054 const wide_int
&lh_lb
,
3055 const wide_int
&lh_ub
,
3056 const wide_int
&rh_lb
,
3057 const wide_int
&rh_ub
) const
3059 if (wi_optimize_and_or (r
, BIT_IOR_EXPR
, type
, lh_lb
, lh_ub
, rh_lb
, rh_ub
))
3062 wide_int maybe_nonzero_lh
, mustbe_nonzero_lh
;
3063 wide_int maybe_nonzero_rh
, mustbe_nonzero_rh
;
3064 wi_set_zero_nonzero_bits (type
, lh_lb
, lh_ub
,
3065 maybe_nonzero_lh
, mustbe_nonzero_lh
);
3066 wi_set_zero_nonzero_bits (type
, rh_lb
, rh_ub
,
3067 maybe_nonzero_rh
, mustbe_nonzero_rh
);
3068 wide_int new_lb
= mustbe_nonzero_lh
| mustbe_nonzero_rh
;
3069 wide_int new_ub
= maybe_nonzero_lh
| maybe_nonzero_rh
;
3070 signop sign
= TYPE_SIGN (type
);
3071 // If the input ranges contain only positive values we can
3072 // truncate the minimum of the result range to the maximum
3073 // of the input range minima.
3074 if (wi::ge_p (lh_lb
, 0, sign
)
3075 && wi::ge_p (rh_lb
, 0, sign
))
3077 new_lb
= wi::max (new_lb
, lh_lb
, sign
);
3078 new_lb
= wi::max (new_lb
, rh_lb
, sign
);
3080 // If either input range contains only negative values
3081 // we can truncate the minimum of the result range to the
3082 // respective minimum range.
3083 if (wi::lt_p (lh_ub
, 0, sign
))
3084 new_lb
= wi::max (new_lb
, lh_lb
, sign
);
3085 if (wi::lt_p (rh_ub
, 0, sign
))
3086 new_lb
= wi::max (new_lb
, rh_lb
, sign
);
3087 // If the limits got swapped around, return a conservative range.
3088 if (wi::gt_p (new_lb
, new_ub
, sign
))
3090 // Make sure that nonzero|X is nonzero.
3091 if (wi::gt_p (lh_lb
, 0, sign
)
3092 || wi::gt_p (rh_lb
, 0, sign
)
3093 || wi::lt_p (lh_ub
, 0, sign
)
3094 || wi::lt_p (rh_ub
, 0, sign
))
3095 r
.set_nonzero (type
);
3097 r
.set_varying (type
);
3100 value_range_with_overflow (r
, type
, new_lb
, new_ub
);
3104 operator_bitwise_or::op1_range (irange
&r
, tree type
,
3107 relation_kind rel ATTRIBUTE_UNUSED
) const
3109 // If this is really a logical wi_fold, call that.
3110 if (types_compatible_p (type
, boolean_type_node
))
3111 return op_logical_or
.op1_range (r
, type
, lhs
, op2
);
3115 tree zero
= build_zero_cst (type
);
3116 r
= int_range
<1> (zero
, zero
);
3119 r
.set_varying (type
);
3124 operator_bitwise_or::op2_range (irange
&r
, tree type
,
3127 relation_kind rel ATTRIBUTE_UNUSED
) const
3129 return operator_bitwise_or::op1_range (r
, type
, lhs
, op1
);
3133 class operator_bitwise_xor
: public range_operator
3136 virtual void wi_fold (irange
&r
, tree type
,
3137 const wide_int
&lh_lb
,
3138 const wide_int
&lh_ub
,
3139 const wide_int
&rh_lb
,
3140 const wide_int
&rh_ub
) const;
3141 virtual bool op1_range (irange
&r
, tree type
,
3144 relation_kind rel
= VREL_NONE
) const;
3145 virtual bool op2_range (irange
&r
, tree type
,
3148 relation_kind rel
= VREL_NONE
) const;
3149 virtual bool op1_op2_relation_effect (irange
&lhs_range
,
3151 const irange
&op1_range
,
3152 const irange
&op2_range
,
3153 relation_kind rel
) const;
3157 operator_bitwise_xor::wi_fold (irange
&r
, tree type
,
3158 const wide_int
&lh_lb
,
3159 const wide_int
&lh_ub
,
3160 const wide_int
&rh_lb
,
3161 const wide_int
&rh_ub
) const
3163 signop sign
= TYPE_SIGN (type
);
3164 wide_int maybe_nonzero_lh
, mustbe_nonzero_lh
;
3165 wide_int maybe_nonzero_rh
, mustbe_nonzero_rh
;
3166 wi_set_zero_nonzero_bits (type
, lh_lb
, lh_ub
,
3167 maybe_nonzero_lh
, mustbe_nonzero_lh
);
3168 wi_set_zero_nonzero_bits (type
, rh_lb
, rh_ub
,
3169 maybe_nonzero_rh
, mustbe_nonzero_rh
);
3171 wide_int result_zero_bits
= ((mustbe_nonzero_lh
& mustbe_nonzero_rh
)
3172 | ~(maybe_nonzero_lh
| maybe_nonzero_rh
));
3173 wide_int result_one_bits
3174 = (wi::bit_and_not (mustbe_nonzero_lh
, maybe_nonzero_rh
)
3175 | wi::bit_and_not (mustbe_nonzero_rh
, maybe_nonzero_lh
));
3176 wide_int new_ub
= ~result_zero_bits
;
3177 wide_int new_lb
= result_one_bits
;
3179 // If the range has all positive or all negative values, the result
3180 // is better than VARYING.
3181 if (wi::lt_p (new_lb
, 0, sign
) || wi::ge_p (new_ub
, 0, sign
))
3182 value_range_with_overflow (r
, type
, new_lb
, new_ub
);
3184 r
.set_varying (type
);
3188 operator_bitwise_xor::op1_op2_relation_effect (irange
&lhs_range
,
3192 relation_kind rel
) const
3194 if (rel
== VREL_NONE
)
3197 int_range
<2> rel_range
;
3202 rel_range
.set_zero (type
);
3205 rel_range
.set_nonzero (type
);
3211 lhs_range
.intersect (rel_range
);
3216 operator_bitwise_xor::op1_range (irange
&r
, tree type
,
3219 relation_kind rel ATTRIBUTE_UNUSED
) const
3221 if (lhs
.undefined_p () || lhs
.varying_p ())
3226 if (types_compatible_p (type
, boolean_type_node
))
3228 switch (get_bool_state (r
, lhs
, type
))
3231 if (op2
.varying_p ())
3232 r
.set_varying (type
);
3233 else if (op2
.zero_p ())
3234 r
= range_true (type
);
3236 r
= range_false (type
);
3246 r
.set_varying (type
);
3251 operator_bitwise_xor::op2_range (irange
&r
, tree type
,
3254 relation_kind rel ATTRIBUTE_UNUSED
) const
3256 return operator_bitwise_xor::op1_range (r
, type
, lhs
, op1
);
3259 class operator_trunc_mod
: public range_operator
3262 virtual void wi_fold (irange
&r
, tree type
,
3263 const wide_int
&lh_lb
,
3264 const wide_int
&lh_ub
,
3265 const wide_int
&rh_lb
,
3266 const wide_int
&rh_ub
) const;
3267 virtual bool op1_range (irange
&r
, tree type
,
3270 relation_kind rel ATTRIBUTE_UNUSED
) const;
3271 virtual bool op2_range (irange
&r
, tree type
,
3274 relation_kind rel ATTRIBUTE_UNUSED
) const;
3278 operator_trunc_mod::wi_fold (irange
&r
, tree type
,
3279 const wide_int
&lh_lb
,
3280 const wide_int
&lh_ub
,
3281 const wide_int
&rh_lb
,
3282 const wide_int
&rh_ub
) const
3284 wide_int new_lb
, new_ub
, tmp
;
3285 signop sign
= TYPE_SIGN (type
);
3286 unsigned prec
= TYPE_PRECISION (type
);
3288 // Mod 0 is undefined.
3289 if (wi_zero_p (type
, rh_lb
, rh_ub
))
3295 // Check for constant and try to fold.
3296 if (lh_lb
== lh_ub
&& rh_lb
== rh_ub
)
3298 wi::overflow_type ov
= wi::OVF_NONE
;
3299 tmp
= wi::mod_trunc (lh_lb
, rh_lb
, sign
, &ov
);
3300 if (ov
== wi::OVF_NONE
)
3302 r
= int_range
<2> (type
, tmp
, tmp
);
3307 // ABS (A % B) < ABS (B) and either 0 <= A % B <= A or A <= A % B <= 0.
3312 new_ub
= wi::smax (new_ub
, tmp
);
3315 if (sign
== UNSIGNED
)
3316 new_lb
= wi::zero (prec
);
3321 if (wi::gts_p (tmp
, 0))
3322 tmp
= wi::zero (prec
);
3323 new_lb
= wi::smax (new_lb
, tmp
);
3326 if (sign
== SIGNED
&& wi::neg_p (tmp
))
3327 tmp
= wi::zero (prec
);
3328 new_ub
= wi::min (new_ub
, tmp
, sign
);
3330 value_range_with_overflow (r
, type
, new_lb
, new_ub
);
3334 operator_trunc_mod::op1_range (irange
&r
, tree type
,
3337 relation_kind rel ATTRIBUTE_UNUSED
) const
3340 signop sign
= TYPE_SIGN (type
);
3341 unsigned prec
= TYPE_PRECISION (type
);
3342 // (a % b) >= x && x > 0 , then a >= x.
3343 if (wi::gt_p (lhs
.lower_bound (), 0, sign
))
3345 r
= value_range (type
, lhs
.lower_bound (), wi::max_value (prec
, sign
));
3348 // (a % b) <= x && x < 0 , then a <= x.
3349 if (wi::lt_p (lhs
.upper_bound (), 0, sign
))
3351 r
= value_range (type
, wi::min_value (prec
, sign
), lhs
.upper_bound ());
3358 operator_trunc_mod::op2_range (irange
&r
, tree type
,
3361 relation_kind rel ATTRIBUTE_UNUSED
) const
3364 signop sign
= TYPE_SIGN (type
);
3365 unsigned prec
= TYPE_PRECISION (type
);
3366 // (a % b) >= x && x > 0 , then b is in ~[-x, x] for signed
3367 // or b > x for unsigned.
3368 if (wi::gt_p (lhs
.lower_bound (), 0, sign
))
3371 r
= value_range (type
, wi::neg (lhs
.lower_bound ()),
3372 lhs
.lower_bound (), VR_ANTI_RANGE
);
3373 else if (wi::lt_p (lhs
.lower_bound (), wi::max_value (prec
, sign
),
3375 r
= value_range (type
, lhs
.lower_bound () + 1,
3376 wi::max_value (prec
, sign
));
3381 // (a % b) <= x && x < 0 , then b is in ~[x, -x].
3382 if (wi::lt_p (lhs
.upper_bound (), 0, sign
))
3384 if (wi::gt_p (lhs
.upper_bound (), wi::min_value (prec
, sign
), sign
))
3385 r
= value_range (type
, lhs
.upper_bound (),
3386 wi::neg (lhs
.upper_bound ()), VR_ANTI_RANGE
);
3395 class operator_logical_not
: public range_operator
3398 virtual bool fold_range (irange
&r
, tree type
,
3401 relation_kind rel
= VREL_NONE
) const;
3402 virtual bool op1_range (irange
&r
, tree type
,
3405 relation_kind rel
= VREL_NONE
) const;
3408 // Folding a logical NOT, oddly enough, involves doing nothing on the
3409 // forward pass through. During the initial walk backwards, the
3410 // logical NOT reversed the desired outcome on the way back, so on the
3411 // way forward all we do is pass the range forward.
3416 // to determine the TRUE branch, walking backward
3417 // if (b_3) if ([1,1])
3418 // b_3 = !b_2 [1,1] = ![0,0]
3419 // b_2 = x_1 < 20 [0,0] = x_1 < 20, false, so x_1 == [20, 255]
3420 // which is the result we are looking for.. so.. pass it through.
3423 operator_logical_not::fold_range (irange
&r
, tree type
,
3425 const irange
&rh ATTRIBUTE_UNUSED
,
3426 relation_kind rel ATTRIBUTE_UNUSED
) const
3428 if (empty_range_varying (r
, type
, lh
, rh
))
3432 if (!lh
.varying_p () && !lh
.undefined_p ())
3439 operator_logical_not::op1_range (irange
&r
,
3443 relation_kind rel ATTRIBUTE_UNUSED
) const
3445 // Logical NOT is involutary...do it again.
3446 return fold_range (r
, type
, lhs
, op2
);
3450 class operator_bitwise_not
: public range_operator
3453 virtual bool fold_range (irange
&r
, tree type
,
3456 relation_kind rel
= VREL_NONE
) const;
3457 virtual bool op1_range (irange
&r
, tree type
,
3460 relation_kind rel
= VREL_NONE
) const;
3464 operator_bitwise_not::fold_range (irange
&r
, tree type
,
3467 relation_kind rel ATTRIBUTE_UNUSED
) const
3469 if (empty_range_varying (r
, type
, lh
, rh
))
3472 if (types_compatible_p (type
, boolean_type_node
))
3473 return op_logical_not
.fold_range (r
, type
, lh
, rh
);
3475 // ~X is simply -1 - X.
3476 int_range
<1> minusone (type
, wi::minus_one (TYPE_PRECISION (type
)),
3477 wi::minus_one (TYPE_PRECISION (type
)));
3478 return range_op_handler (MINUS_EXPR
, type
)->fold_range (r
, type
, minusone
,
3483 operator_bitwise_not::op1_range (irange
&r
, tree type
,
3486 relation_kind rel ATTRIBUTE_UNUSED
) const
3488 if (types_compatible_p (type
, boolean_type_node
))
3489 return op_logical_not
.op1_range (r
, type
, lhs
, op2
);
3491 // ~X is -1 - X and since bitwise NOT is involutary...do it again.
3492 return fold_range (r
, type
, lhs
, op2
);
3496 class operator_cst
: public range_operator
3499 virtual bool fold_range (irange
&r
, tree type
,
3502 relation_kind rel
= VREL_NONE
) const;
3506 operator_cst::fold_range (irange
&r
, tree type ATTRIBUTE_UNUSED
,
3508 const irange
&rh ATTRIBUTE_UNUSED
,
3509 relation_kind rel ATTRIBUTE_UNUSED
) const
3516 class operator_identity
: public range_operator
3519 virtual bool fold_range (irange
&r
, tree type
,
3522 relation_kind rel
= VREL_NONE
) const;
3523 virtual bool op1_range (irange
&r
, tree type
,
3526 relation_kind rel
= VREL_NONE
) const;
3527 virtual enum tree_code
lhs_op1_relation (const irange
&lhs
,
3529 const irange
&op2
) const;
3532 // Determine if there is a relationship between LHS and OP1.
3535 operator_identity::lhs_op1_relation (const irange
&lhs
,
3536 const irange
&op1 ATTRIBUTE_UNUSED
,
3537 const irange
&op2 ATTRIBUTE_UNUSED
) const
3539 if (lhs
.undefined_p ())
3541 // Simply a copy, so they are equivalent.
3546 operator_identity::fold_range (irange
&r
, tree type ATTRIBUTE_UNUSED
,
3548 const irange
&rh ATTRIBUTE_UNUSED
,
3549 relation_kind rel ATTRIBUTE_UNUSED
) const
3556 operator_identity::op1_range (irange
&r
, tree type ATTRIBUTE_UNUSED
,
3558 const irange
&op2 ATTRIBUTE_UNUSED
,
3559 relation_kind rel ATTRIBUTE_UNUSED
) const
3566 class operator_unknown
: public range_operator
3569 virtual bool fold_range (irange
&r
, tree type
,
3572 relation_kind rel
= VREL_NONE
) const;
3576 operator_unknown::fold_range (irange
&r
, tree type
,
3577 const irange
&lh ATTRIBUTE_UNUSED
,
3578 const irange
&rh ATTRIBUTE_UNUSED
,
3579 relation_kind rel ATTRIBUTE_UNUSED
) const
3581 r
.set_varying (type
);
3586 class operator_abs
: public range_operator
3589 virtual void wi_fold (irange
&r
, tree type
,
3590 const wide_int
&lh_lb
,
3591 const wide_int
&lh_ub
,
3592 const wide_int
&rh_lb
,
3593 const wide_int
&rh_ub
) const;
3594 virtual bool op1_range (irange
&r
, tree type
,
3597 relation_kind rel ATTRIBUTE_UNUSED
) const;
3601 operator_abs::wi_fold (irange
&r
, tree type
,
3602 const wide_int
&lh_lb
, const wide_int
&lh_ub
,
3603 const wide_int
&rh_lb ATTRIBUTE_UNUSED
,
3604 const wide_int
&rh_ub ATTRIBUTE_UNUSED
) const
3607 signop sign
= TYPE_SIGN (type
);
3608 unsigned prec
= TYPE_PRECISION (type
);
3610 // Pass through LH for the easy cases.
3611 if (sign
== UNSIGNED
|| wi::ge_p (lh_lb
, 0, sign
))
3613 r
= int_range
<1> (type
, lh_lb
, lh_ub
);
3617 // -TYPE_MIN_VALUE = TYPE_MIN_VALUE with flag_wrapv so we can't get
3619 wide_int min_value
= wi::min_value (prec
, sign
);
3620 wide_int max_value
= wi::max_value (prec
, sign
);
3621 if (!TYPE_OVERFLOW_UNDEFINED (type
) && wi::eq_p (lh_lb
, min_value
))
3623 r
.set_varying (type
);
3627 // ABS_EXPR may flip the range around, if the original range
3628 // included negative values.
3629 if (wi::eq_p (lh_lb
, min_value
))
3631 // ABS ([-MIN, -MIN]) isn't representable, but we have traditionally
3632 // returned [-MIN,-MIN] so this preserves that behaviour. PR37078
3633 if (wi::eq_p (lh_ub
, min_value
))
3635 r
= int_range
<1> (type
, min_value
, min_value
);
3641 min
= wi::abs (lh_lb
);
3643 if (wi::eq_p (lh_ub
, min_value
))
3646 max
= wi::abs (lh_ub
);
3648 // If the range contains zero then we know that the minimum value in the
3649 // range will be zero.
3650 if (wi::le_p (lh_lb
, 0, sign
) && wi::ge_p (lh_ub
, 0, sign
))
3652 if (wi::gt_p (min
, max
, sign
))
3654 min
= wi::zero (prec
);
3658 // If the range was reversed, swap MIN and MAX.
3659 if (wi::gt_p (min
, max
, sign
))
3660 std::swap (min
, max
);
3663 // If the new range has its limits swapped around (MIN > MAX), then
3664 // the operation caused one of them to wrap around. The only thing
3665 // we know is that the result is positive.
3666 if (wi::gt_p (min
, max
, sign
))
3668 min
= wi::zero (prec
);
3671 r
= int_range
<1> (type
, min
, max
);
3675 operator_abs::op1_range (irange
&r
, tree type
,
3678 relation_kind rel ATTRIBUTE_UNUSED
) const
3680 if (empty_range_varying (r
, type
, lhs
, op2
))
3682 if (TYPE_UNSIGNED (type
))
3687 // Start with the positives because negatives are an impossible result.
3688 int_range_max positives
= range_positives (type
);
3689 positives
.intersect (lhs
);
3691 // Then add the negative of each pair:
3692 // ABS(op1) = [5,20] would yield op1 => [-20,-5][5,20].
3693 for (unsigned i
= 0; i
< positives
.num_pairs (); ++i
)
3694 r
.union_ (int_range
<1> (type
,
3695 -positives
.upper_bound (i
),
3696 -positives
.lower_bound (i
)));
3697 // With flag_wrapv, -TYPE_MIN_VALUE = TYPE_MIN_VALUE which is
3698 // unrepresentable. Add -TYPE_MIN_VALUE in this case.
3699 wide_int min_value
= wi::min_value (TYPE_PRECISION (type
), TYPE_SIGN (type
));
3700 wide_int lb
= lhs
.lower_bound ();
3701 if (!TYPE_OVERFLOW_UNDEFINED (type
) && wi::eq_p (lb
, min_value
))
3702 r
.union_ (int_range
<2> (type
, lb
, lb
));
3707 class operator_absu
: public range_operator
3710 virtual void wi_fold (irange
&r
, tree type
,
3711 const wide_int
&lh_lb
, const wide_int
&lh_ub
,
3712 const wide_int
&rh_lb
, const wide_int
&rh_ub
) const;
3716 operator_absu::wi_fold (irange
&r
, tree type
,
3717 const wide_int
&lh_lb
, const wide_int
&lh_ub
,
3718 const wide_int
&rh_lb ATTRIBUTE_UNUSED
,
3719 const wide_int
&rh_ub ATTRIBUTE_UNUSED
) const
3721 wide_int new_lb
, new_ub
;
3723 // Pass through VR0 the easy cases.
3724 if (wi::ges_p (lh_lb
, 0))
3731 new_lb
= wi::abs (lh_lb
);
3732 new_ub
= wi::abs (lh_ub
);
3734 // If the range contains zero then we know that the minimum
3735 // value in the range will be zero.
3736 if (wi::ges_p (lh_ub
, 0))
3738 if (wi::gtu_p (new_lb
, new_ub
))
3740 new_lb
= wi::zero (TYPE_PRECISION (type
));
3743 std::swap (new_lb
, new_ub
);
3746 gcc_checking_assert (TYPE_UNSIGNED (type
));
3747 r
= int_range
<1> (type
, new_lb
, new_ub
);
3751 class operator_negate
: public range_operator
3754 virtual bool fold_range (irange
&r
, tree type
,
3757 relation_kind rel
= VREL_NONE
) const;
3758 virtual bool op1_range (irange
&r
, tree type
,
3761 relation_kind rel
= VREL_NONE
) const;
3765 operator_negate::fold_range (irange
&r
, tree type
,
3768 relation_kind rel ATTRIBUTE_UNUSED
) const
3770 if (empty_range_varying (r
, type
, lh
, rh
))
3772 // -X is simply 0 - X.
3773 return range_op_handler (MINUS_EXPR
, type
)->fold_range (r
, type
,
3779 operator_negate::op1_range (irange
&r
, tree type
,
3782 relation_kind rel ATTRIBUTE_UNUSED
) const
3784 // NEGATE is involutory.
3785 return fold_range (r
, type
, lhs
, op2
);
3789 class operator_addr_expr
: public range_operator
3792 virtual bool fold_range (irange
&r
, tree type
,
3795 relation_kind rel
= VREL_NONE
) const;
3796 virtual bool op1_range (irange
&r
, tree type
,
3799 relation_kind rel
= VREL_NONE
) const;
3803 operator_addr_expr::fold_range (irange
&r
, tree type
,
3806 relation_kind rel ATTRIBUTE_UNUSED
) const
3808 if (empty_range_varying (r
, type
, lh
, rh
))
3811 // Return a non-null pointer of the LHS type (passed in op2).
3813 r
= range_zero (type
);
3814 else if (!lh
.contains_p (build_zero_cst (lh
.type ())))
3815 r
= range_nonzero (type
);
3817 r
.set_varying (type
);
3822 operator_addr_expr::op1_range (irange
&r
, tree type
,
3825 relation_kind rel ATTRIBUTE_UNUSED
) const
3827 return operator_addr_expr::fold_range (r
, type
, lhs
, op2
);
3831 class pointer_plus_operator
: public range_operator
3834 virtual void wi_fold (irange
&r
, tree type
,
3835 const wide_int
&lh_lb
,
3836 const wide_int
&lh_ub
,
3837 const wide_int
&rh_lb
,
3838 const wide_int
&rh_ub
) const;
3842 pointer_plus_operator::wi_fold (irange
&r
, tree type
,
3843 const wide_int
&lh_lb
,
3844 const wide_int
&lh_ub
,
3845 const wide_int
&rh_lb
,
3846 const wide_int
&rh_ub
) const
3848 // Check for [0,0] + const, and simply return the const.
3849 if (lh_lb
== 0 && lh_ub
== 0 && rh_lb
== rh_ub
)
3851 tree val
= wide_int_to_tree (type
, rh_lb
);
3856 // For pointer types, we are really only interested in asserting
3857 // whether the expression evaluates to non-NULL.
3859 // With -fno-delete-null-pointer-checks we need to be more
3860 // conservative. As some object might reside at address 0,
3861 // then some offset could be added to it and the same offset
3862 // subtracted again and the result would be NULL.
3864 // static int a[12]; where &a[0] is NULL and
3867 // ptr will be NULL here, even when there is POINTER_PLUS_EXPR
3868 // where the first range doesn't include zero and the second one
3869 // doesn't either. As the second operand is sizetype (unsigned),
3870 // consider all ranges where the MSB could be set as possible
3871 // subtractions where the result might be NULL.
3872 if ((!wi_includes_zero_p (type
, lh_lb
, lh_ub
)
3873 || !wi_includes_zero_p (type
, rh_lb
, rh_ub
))
3874 && !TYPE_OVERFLOW_WRAPS (type
)
3875 && (flag_delete_null_pointer_checks
3876 || !wi::sign_mask (rh_ub
)))
3877 r
= range_nonzero (type
);
3878 else if (lh_lb
== lh_ub
&& lh_lb
== 0
3879 && rh_lb
== rh_ub
&& rh_lb
== 0)
3880 r
= range_zero (type
);
3882 r
.set_varying (type
);
3886 class pointer_min_max_operator
: public range_operator
3889 virtual void wi_fold (irange
& r
, tree type
,
3890 const wide_int
&lh_lb
, const wide_int
&lh_ub
,
3891 const wide_int
&rh_lb
, const wide_int
&rh_ub
) const;
3895 pointer_min_max_operator::wi_fold (irange
&r
, tree type
,
3896 const wide_int
&lh_lb
,
3897 const wide_int
&lh_ub
,
3898 const wide_int
&rh_lb
,
3899 const wide_int
&rh_ub
) const
3901 // For MIN/MAX expressions with pointers, we only care about
3902 // nullness. If both are non null, then the result is nonnull.
3903 // If both are null, then the result is null. Otherwise they
3905 if (!wi_includes_zero_p (type
, lh_lb
, lh_ub
)
3906 && !wi_includes_zero_p (type
, rh_lb
, rh_ub
))
3907 r
= range_nonzero (type
);
3908 else if (wi_zero_p (type
, lh_lb
, lh_ub
) && wi_zero_p (type
, rh_lb
, rh_ub
))
3909 r
= range_zero (type
);
3911 r
.set_varying (type
);
3915 class pointer_and_operator
: public range_operator
3918 virtual void wi_fold (irange
&r
, tree type
,
3919 const wide_int
&lh_lb
, const wide_int
&lh_ub
,
3920 const wide_int
&rh_lb
, const wide_int
&rh_ub
) const;
3924 pointer_and_operator::wi_fold (irange
&r
, tree type
,
3925 const wide_int
&lh_lb
,
3926 const wide_int
&lh_ub
,
3927 const wide_int
&rh_lb ATTRIBUTE_UNUSED
,
3928 const wide_int
&rh_ub ATTRIBUTE_UNUSED
) const
3930 // For pointer types, we are really only interested in asserting
3931 // whether the expression evaluates to non-NULL.
3932 if (wi_zero_p (type
, lh_lb
, lh_ub
) || wi_zero_p (type
, lh_lb
, lh_ub
))
3933 r
= range_zero (type
);
3935 r
.set_varying (type
);
3939 class pointer_or_operator
: public range_operator
3942 virtual bool op1_range (irange
&r
, tree type
,
3945 relation_kind rel
= VREL_NONE
) const;
3946 virtual bool op2_range (irange
&r
, tree type
,
3949 relation_kind rel
= VREL_NONE
) const;
3950 virtual void wi_fold (irange
&r
, tree type
,
3951 const wide_int
&lh_lb
, const wide_int
&lh_ub
,
3952 const wide_int
&rh_lb
, const wide_int
&rh_ub
) const;
3956 pointer_or_operator::op1_range (irange
&r
, tree type
,
3958 const irange
&op2 ATTRIBUTE_UNUSED
,
3959 relation_kind rel ATTRIBUTE_UNUSED
) const
3963 tree zero
= build_zero_cst (type
);
3964 r
= int_range
<1> (zero
, zero
);
3967 r
.set_varying (type
);
3972 pointer_or_operator::op2_range (irange
&r
, tree type
,
3975 relation_kind rel ATTRIBUTE_UNUSED
) const
3977 return pointer_or_operator::op1_range (r
, type
, lhs
, op1
);
3981 pointer_or_operator::wi_fold (irange
&r
, tree type
,
3982 const wide_int
&lh_lb
,
3983 const wide_int
&lh_ub
,
3984 const wide_int
&rh_lb
,
3985 const wide_int
&rh_ub
) const
3987 // For pointer types, we are really only interested in asserting
3988 // whether the expression evaluates to non-NULL.
3989 if (!wi_includes_zero_p (type
, lh_lb
, lh_ub
)
3990 && !wi_includes_zero_p (type
, rh_lb
, rh_ub
))
3991 r
= range_nonzero (type
);
3992 else if (wi_zero_p (type
, lh_lb
, lh_ub
) && wi_zero_p (type
, rh_lb
, rh_ub
))
3993 r
= range_zero (type
);
3995 r
.set_varying (type
);
3998 // This implements the range operator tables as local objects in this file.
4000 class range_op_table
4003 inline range_operator
*operator[] (enum tree_code code
);
4005 void set (enum tree_code code
, range_operator
&op
);
4007 range_operator
*m_range_tree
[MAX_TREE_CODES
];
4010 // Return a pointer to the range_operator instance, if there is one
4011 // associated with tree_code CODE.
4014 range_op_table::operator[] (enum tree_code code
)
4016 gcc_checking_assert (code
> 0 && code
< MAX_TREE_CODES
);
4017 return m_range_tree
[code
];
4020 // Add OP to the handler table for CODE.
4023 range_op_table::set (enum tree_code code
, range_operator
&op
)
4025 gcc_checking_assert (m_range_tree
[code
] == NULL
);
4026 m_range_tree
[code
] = &op
;
4029 // Instantiate a range op table for integral operations.
4031 class integral_table
: public range_op_table
4035 } integral_tree_table
;
4037 integral_table::integral_table ()
4039 set (EQ_EXPR
, op_equal
);
4040 set (NE_EXPR
, op_not_equal
);
4041 set (LT_EXPR
, op_lt
);
4042 set (LE_EXPR
, op_le
);
4043 set (GT_EXPR
, op_gt
);
4044 set (GE_EXPR
, op_ge
);
4045 set (PLUS_EXPR
, op_plus
);
4046 set (MINUS_EXPR
, op_minus
);
4047 set (MIN_EXPR
, op_min
);
4048 set (MAX_EXPR
, op_max
);
4049 set (MULT_EXPR
, op_mult
);
4050 set (TRUNC_DIV_EXPR
, op_trunc_div
);
4051 set (FLOOR_DIV_EXPR
, op_floor_div
);
4052 set (ROUND_DIV_EXPR
, op_round_div
);
4053 set (CEIL_DIV_EXPR
, op_ceil_div
);
4054 set (EXACT_DIV_EXPR
, op_exact_div
);
4055 set (LSHIFT_EXPR
, op_lshift
);
4056 set (RSHIFT_EXPR
, op_rshift
);
4057 set (NOP_EXPR
, op_convert
);
4058 set (CONVERT_EXPR
, op_convert
);
4059 set (TRUTH_AND_EXPR
, op_logical_and
);
4060 set (BIT_AND_EXPR
, op_bitwise_and
);
4061 set (TRUTH_OR_EXPR
, op_logical_or
);
4062 set (BIT_IOR_EXPR
, op_bitwise_or
);
4063 set (BIT_XOR_EXPR
, op_bitwise_xor
);
4064 set (TRUNC_MOD_EXPR
, op_trunc_mod
);
4065 set (TRUTH_NOT_EXPR
, op_logical_not
);
4066 set (BIT_NOT_EXPR
, op_bitwise_not
);
4067 set (INTEGER_CST
, op_integer_cst
);
4068 set (SSA_NAME
, op_identity
);
4069 set (PAREN_EXPR
, op_identity
);
4070 set (OBJ_TYPE_REF
, op_identity
);
4071 set (IMAGPART_EXPR
, op_unknown
);
4072 set (REALPART_EXPR
, op_unknown
);
4073 set (POINTER_DIFF_EXPR
, op_pointer_diff
);
4074 set (ABS_EXPR
, op_abs
);
4075 set (ABSU_EXPR
, op_absu
);
4076 set (NEGATE_EXPR
, op_negate
);
4077 set (ADDR_EXPR
, op_addr
);
4080 // Instantiate a range op table for pointer operations.
4082 class pointer_table
: public range_op_table
4086 } pointer_tree_table
;
4088 pointer_table::pointer_table ()
4090 set (BIT_AND_EXPR
, op_pointer_and
);
4091 set (BIT_IOR_EXPR
, op_pointer_or
);
4092 set (MIN_EXPR
, op_ptr_min_max
);
4093 set (MAX_EXPR
, op_ptr_min_max
);
4094 set (POINTER_PLUS_EXPR
, op_pointer_plus
);
4096 set (EQ_EXPR
, op_equal
);
4097 set (NE_EXPR
, op_not_equal
);
4098 set (LT_EXPR
, op_lt
);
4099 set (LE_EXPR
, op_le
);
4100 set (GT_EXPR
, op_gt
);
4101 set (GE_EXPR
, op_ge
);
4102 set (SSA_NAME
, op_identity
);
4103 set (INTEGER_CST
, op_integer_cst
);
4104 set (ADDR_EXPR
, op_addr
);
4105 set (NOP_EXPR
, op_convert
);
4106 set (CONVERT_EXPR
, op_convert
);
4108 set (BIT_NOT_EXPR
, op_bitwise_not
);
4109 set (BIT_XOR_EXPR
, op_bitwise_xor
);
4112 // The tables are hidden and accessed via a simple extern function.
4115 range_op_handler (enum tree_code code
, tree type
)
4117 // First check if there is a pointer specialization.
4118 if (POINTER_TYPE_P (type
))
4119 return pointer_tree_table
[code
];
4120 if (INTEGRAL_TYPE_P (type
))
4121 return integral_tree_table
[code
];
4125 // Cast the range in R to TYPE.
4128 range_cast (irange
&r
, tree type
)
4130 int_range_max tmp
= r
;
4131 range_operator
*op
= range_op_handler (CONVERT_EXPR
, type
);
4132 // Call op_convert, if it fails, the result is varying.
4133 if (!op
->fold_range (r
, type
, tmp
, int_range
<1> (type
)))
4134 r
.set_varying (type
);
4138 #include "selftest.h"
4142 #define INT(N) build_int_cst (integer_type_node, (N))
4143 #define UINT(N) build_int_cstu (unsigned_type_node, (N))
4144 #define INT16(N) build_int_cst (short_integer_type_node, (N))
4145 #define UINT16(N) build_int_cstu (short_unsigned_type_node, (N))
4146 #define SCHAR(N) build_int_cst (signed_char_type_node, (N))
4147 #define UCHAR(N) build_int_cstu (unsigned_char_type_node, (N))
4150 range_op_cast_tests ()
4152 int_range
<1> r0
, r1
, r2
, rold
;
4153 r0
.set_varying (integer_type_node
);
4154 tree maxint
= wide_int_to_tree (integer_type_node
, r0
.upper_bound ());
4156 // If a range is in any way outside of the range for the converted
4157 // to range, default to the range for the new type.
4158 r0
.set_varying (short_integer_type_node
);
4159 tree minshort
= wide_int_to_tree (short_integer_type_node
, r0
.lower_bound ());
4160 tree maxshort
= wide_int_to_tree (short_integer_type_node
, r0
.upper_bound ());
4161 if (TYPE_PRECISION (TREE_TYPE (maxint
))
4162 > TYPE_PRECISION (short_integer_type_node
))
4164 r1
= int_range
<1> (integer_zero_node
, maxint
);
4165 range_cast (r1
, short_integer_type_node
);
4166 ASSERT_TRUE (r1
.lower_bound () == wi::to_wide (minshort
)
4167 && r1
.upper_bound() == wi::to_wide (maxshort
));
4170 // (unsigned char)[-5,-1] => [251,255].
4171 r0
= rold
= int_range
<1> (SCHAR (-5), SCHAR (-1));
4172 range_cast (r0
, unsigned_char_type_node
);
4173 ASSERT_TRUE (r0
== int_range
<1> (UCHAR (251), UCHAR (255)));
4174 range_cast (r0
, signed_char_type_node
);
4175 ASSERT_TRUE (r0
== rold
);
4177 // (signed char)[15, 150] => [-128,-106][15,127].
4178 r0
= rold
= int_range
<1> (UCHAR (15), UCHAR (150));
4179 range_cast (r0
, signed_char_type_node
);
4180 r1
= int_range
<1> (SCHAR (15), SCHAR (127));
4181 r2
= int_range
<1> (SCHAR (-128), SCHAR (-106));
4183 ASSERT_TRUE (r1
== r0
);
4184 range_cast (r0
, unsigned_char_type_node
);
4185 ASSERT_TRUE (r0
== rold
);
4187 // (unsigned char)[-5, 5] => [0,5][251,255].
4188 r0
= rold
= int_range
<1> (SCHAR (-5), SCHAR (5));
4189 range_cast (r0
, unsigned_char_type_node
);
4190 r1
= int_range
<1> (UCHAR (251), UCHAR (255));
4191 r2
= int_range
<1> (UCHAR (0), UCHAR (5));
4193 ASSERT_TRUE (r0
== r1
);
4194 range_cast (r0
, signed_char_type_node
);
4195 ASSERT_TRUE (r0
== rold
);
4197 // (unsigned char)[-5,5] => [0,5][251,255].
4198 r0
= int_range
<1> (INT (-5), INT (5));
4199 range_cast (r0
, unsigned_char_type_node
);
4200 r1
= int_range
<1> (UCHAR (0), UCHAR (5));
4201 r1
.union_ (int_range
<1> (UCHAR (251), UCHAR (255)));
4202 ASSERT_TRUE (r0
== r1
);
4204 // (unsigned char)[5U,1974U] => [0,255].
4205 r0
= int_range
<1> (UINT (5), UINT (1974));
4206 range_cast (r0
, unsigned_char_type_node
);
4207 ASSERT_TRUE (r0
== int_range
<1> (UCHAR (0), UCHAR (255)));
4208 range_cast (r0
, integer_type_node
);
4209 // Going to a wider range should not sign extend.
4210 ASSERT_TRUE (r0
== int_range
<1> (INT (0), INT (255)));
4212 // (unsigned char)[-350,15] => [0,255].
4213 r0
= int_range
<1> (INT (-350), INT (15));
4214 range_cast (r0
, unsigned_char_type_node
);
4215 ASSERT_TRUE (r0
== (int_range
<1>
4216 (TYPE_MIN_VALUE (unsigned_char_type_node
),
4217 TYPE_MAX_VALUE (unsigned_char_type_node
))));
4219 // Casting [-120,20] from signed char to unsigned short.
4220 // => [0, 20][0xff88, 0xffff].
4221 r0
= int_range
<1> (SCHAR (-120), SCHAR (20));
4222 range_cast (r0
, short_unsigned_type_node
);
4223 r1
= int_range
<1> (UINT16 (0), UINT16 (20));
4224 r2
= int_range
<1> (UINT16 (0xff88), UINT16 (0xffff));
4226 ASSERT_TRUE (r0
== r1
);
4227 // A truncating cast back to signed char will work because [-120, 20]
4228 // is representable in signed char.
4229 range_cast (r0
, signed_char_type_node
);
4230 ASSERT_TRUE (r0
== int_range
<1> (SCHAR (-120), SCHAR (20)));
4232 // unsigned char -> signed short
4233 // (signed short)[(unsigned char)25, (unsigned char)250]
4234 // => [(signed short)25, (signed short)250]
4235 r0
= rold
= int_range
<1> (UCHAR (25), UCHAR (250));
4236 range_cast (r0
, short_integer_type_node
);
4237 r1
= int_range
<1> (INT16 (25), INT16 (250));
4238 ASSERT_TRUE (r0
== r1
);
4239 range_cast (r0
, unsigned_char_type_node
);
4240 ASSERT_TRUE (r0
== rold
);
4242 // Test casting a wider signed [-MIN,MAX] to a nar`rower unsigned.
4243 r0
= int_range
<1> (TYPE_MIN_VALUE (long_long_integer_type_node
),
4244 TYPE_MAX_VALUE (long_long_integer_type_node
));
4245 range_cast (r0
, short_unsigned_type_node
);
4246 r1
= int_range
<1> (TYPE_MIN_VALUE (short_unsigned_type_node
),
4247 TYPE_MAX_VALUE (short_unsigned_type_node
));
4248 ASSERT_TRUE (r0
== r1
);
4250 // Casting NONZERO to a narrower type will wrap/overflow so
4251 // it's just the entire range for the narrower type.
4253 // "NOT 0 at signed 32-bits" ==> [-MIN_32,-1][1, +MAX_32]. This is
4254 // is outside of the range of a smaller range, return the full
4256 if (TYPE_PRECISION (integer_type_node
)
4257 > TYPE_PRECISION (short_integer_type_node
))
4259 r0
= range_nonzero (integer_type_node
);
4260 range_cast (r0
, short_integer_type_node
);
4261 r1
= int_range
<1> (TYPE_MIN_VALUE (short_integer_type_node
),
4262 TYPE_MAX_VALUE (short_integer_type_node
));
4263 ASSERT_TRUE (r0
== r1
);
4266 // Casting NONZERO from a narrower signed to a wider signed.
4268 // NONZERO signed 16-bits is [-MIN_16,-1][1, +MAX_16].
4269 // Converting this to 32-bits signed is [-MIN_16,-1][1, +MAX_16].
4270 r0
= range_nonzero (short_integer_type_node
);
4271 range_cast (r0
, integer_type_node
);
4272 r1
= int_range
<1> (INT (-32768), INT (-1));
4273 r2
= int_range
<1> (INT (1), INT (32767));
4275 ASSERT_TRUE (r0
== r1
);
4279 range_op_lshift_tests ()
4281 // Test that 0x808.... & 0x8.... still contains 0x8....
4282 // for a large set of numbers.
4285 tree big_type
= long_long_unsigned_type_node
;
4286 // big_num = 0x808,0000,0000,0000
4287 tree big_num
= fold_build2 (LSHIFT_EXPR
, big_type
,
4288 build_int_cst (big_type
, 0x808),
4289 build_int_cst (big_type
, 48));
4290 op_bitwise_and
.fold_range (res
, big_type
,
4291 int_range
<1> (big_type
),
4292 int_range
<1> (big_num
, big_num
));
4293 // val = 0x8,0000,0000,0000
4294 tree val
= fold_build2 (LSHIFT_EXPR
, big_type
,
4295 build_int_cst (big_type
, 0x8),
4296 build_int_cst (big_type
, 48));
4297 ASSERT_TRUE (res
.contains_p (val
));
4300 if (TYPE_PRECISION (unsigned_type_node
) > 31)
4302 // unsigned VARYING = op1 << 1 should be VARYING.
4303 int_range
<2> lhs (unsigned_type_node
);
4304 int_range
<2> shift (INT (1), INT (1));
4306 op_lshift
.op1_range (op1
, unsigned_type_node
, lhs
, shift
);
4307 ASSERT_TRUE (op1
.varying_p ());
4309 // 0 = op1 << 1 should be [0,0], [0x8000000, 0x8000000].
4310 int_range
<2> zero (UINT (0), UINT (0));
4311 op_lshift
.op1_range (op1
, unsigned_type_node
, zero
, shift
);
4312 ASSERT_TRUE (op1
.num_pairs () == 2);
4313 // Remove the [0,0] range.
4314 op1
.intersect (zero
);
4315 ASSERT_TRUE (op1
.num_pairs () == 1);
4316 // op1 << 1 should be [0x8000,0x8000] << 1,
4317 // which should result in [0,0].
4318 int_range_max result
;
4319 op_lshift
.fold_range (result
, unsigned_type_node
, op1
, shift
);
4320 ASSERT_TRUE (result
== zero
);
4322 // signed VARYING = op1 << 1 should be VARYING.
4323 if (TYPE_PRECISION (integer_type_node
) > 31)
4325 // unsigned VARYING = op1 << 1 hould be VARYING.
4326 int_range
<2> lhs (integer_type_node
);
4327 int_range
<2> shift (INT (1), INT (1));
4329 op_lshift
.op1_range (op1
, integer_type_node
, lhs
, shift
);
4330 ASSERT_TRUE (op1
.varying_p ());
4332 // 0 = op1 << 1 should be [0,0], [0x8000000, 0x8000000].
4333 int_range
<2> zero (INT (0), INT (0));
4334 op_lshift
.op1_range (op1
, integer_type_node
, zero
, shift
);
4335 ASSERT_TRUE (op1
.num_pairs () == 2);
4336 // Remove the [0,0] range.
4337 op1
.intersect (zero
);
4338 ASSERT_TRUE (op1
.num_pairs () == 1);
4339 // op1 << 1 shuould be [0x8000,0x8000] << 1,
4340 // which should result in [0,0].
4341 int_range_max result
;
4342 op_lshift
.fold_range (result
, unsigned_type_node
, op1
, shift
);
4343 ASSERT_TRUE (result
== zero
);
4348 range_op_rshift_tests ()
4350 // unsigned: [3, MAX] = OP1 >> 1
4352 int_range_max
lhs (build_int_cst (unsigned_type_node
, 3),
4353 TYPE_MAX_VALUE (unsigned_type_node
));
4354 int_range_max
one (build_one_cst (unsigned_type_node
),
4355 build_one_cst (unsigned_type_node
));
4357 op_rshift
.op1_range (op1
, unsigned_type_node
, lhs
, one
);
4358 ASSERT_FALSE (op1
.contains_p (UINT (3)));
4361 // signed: [3, MAX] = OP1 >> 1
4363 int_range_max
lhs (INT (3), TYPE_MAX_VALUE (integer_type_node
));
4364 int_range_max
one (INT (1), INT (1));
4366 op_rshift
.op1_range (op1
, integer_type_node
, lhs
, one
);
4367 ASSERT_FALSE (op1
.contains_p (INT (-2)));
4370 // This is impossible, so OP1 should be [].
4371 // signed: [MIN, MIN] = OP1 >> 1
4373 int_range_max
lhs (TYPE_MIN_VALUE (integer_type_node
),
4374 TYPE_MIN_VALUE (integer_type_node
));
4375 int_range_max
one (INT (1), INT (1));
4377 op_rshift
.op1_range (op1
, integer_type_node
, lhs
, one
);
4378 ASSERT_TRUE (op1
.undefined_p ());
4381 // signed: ~[-1] = OP1 >> 31
4382 if (TYPE_PRECISION (integer_type_node
) > 31)
4384 int_range_max
lhs (INT (-1), INT (-1), VR_ANTI_RANGE
);
4385 int_range_max
shift (INT (31), INT (31));
4387 op_rshift
.op1_range (op1
, integer_type_node
, lhs
, shift
);
4388 int_range_max negatives
= range_negatives (integer_type_node
);
4389 negatives
.intersect (op1
);
4390 ASSERT_TRUE (negatives
.undefined_p ());
4395 range_op_bitwise_and_tests ()
4398 tree min
= vrp_val_min (integer_type_node
);
4399 tree max
= vrp_val_max (integer_type_node
);
4400 tree tiny
= fold_build2 (PLUS_EXPR
, integer_type_node
, min
,
4401 build_one_cst (integer_type_node
));
4402 int_range_max
i1 (tiny
, max
);
4403 int_range_max
i2 (build_int_cst (integer_type_node
, 255),
4404 build_int_cst (integer_type_node
, 255));
4406 // [MIN+1, MAX] = OP1 & 255: OP1 is VARYING
4407 op_bitwise_and
.op1_range (res
, integer_type_node
, i1
, i2
);
4408 ASSERT_TRUE (res
== int_range
<1> (integer_type_node
));
4410 // VARYING = OP1 & 255: OP1 is VARYING
4411 i1
= int_range
<1> (integer_type_node
);
4412 op_bitwise_and
.op1_range (res
, integer_type_node
, i1
, i2
);
4413 ASSERT_TRUE (res
== int_range
<1> (integer_type_node
));
4415 // (NONZERO | X) is nonzero.
4416 i1
.set_nonzero (integer_type_node
);
4417 i2
.set_varying (integer_type_node
);
4418 op_bitwise_or
.fold_range (res
, integer_type_node
, i1
, i2
);
4419 ASSERT_TRUE (res
.nonzero_p ());
4421 // (NEGATIVE | X) is nonzero.
4422 i1
= int_range
<1> (INT (-5), INT (-3));
4423 i2
.set_varying (integer_type_node
);
4424 op_bitwise_or
.fold_range (res
, integer_type_node
, i1
, i2
);
4425 ASSERT_FALSE (res
.contains_p (INT (0)));
4429 range_relational_tests ()
4431 int_range
<2> lhs (unsigned_char_type_node
);
4432 int_range
<2> op1 (UCHAR (8), UCHAR (10));
4433 int_range
<2> op2 (UCHAR (20), UCHAR (20));
4435 // Never wrapping additions mean LHS > OP1.
4436 tree_code code
= op_plus
.lhs_op1_relation (lhs
, op1
, op2
);
4437 ASSERT_TRUE (code
== GT_EXPR
);
4439 // Most wrapping additions mean nothing...
4440 op1
= int_range
<2> (UCHAR (8), UCHAR (10));
4441 op2
= int_range
<2> (UCHAR (0), UCHAR (255));
4442 code
= op_plus
.lhs_op1_relation (lhs
, op1
, op2
);
4443 ASSERT_TRUE (code
== VREL_NONE
);
4445 // However, always wrapping additions mean LHS < OP1.
4446 op1
= int_range
<2> (UCHAR (1), UCHAR (255));
4447 op2
= int_range
<2> (UCHAR (255), UCHAR (255));
4448 code
= op_plus
.lhs_op1_relation (lhs
, op1
, op2
);
4449 ASSERT_TRUE (code
== LT_EXPR
);
4455 range_op_rshift_tests ();
4456 range_op_lshift_tests ();
4457 range_op_bitwise_and_tests ();
4458 range_op_cast_tests ();
4459 range_relational_tests ();
4462 } // namespace selftest
4464 #endif // CHECKING_P