1 /* Code for range operators.
2 Copyright (C) 2017-2021 Free Software Foundation, Inc.
3 Contributed by Andrew MacLeod <amacleod@redhat.com>
4 and Aldy Hernandez <aldyh@redhat.com>.
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify
9 it under the terms of the GNU General Public License as published by
10 the Free Software Foundation; either version 3, or (at your option)
13 GCC is distributed in the hope that it will be useful,
14 but WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 GNU General Public License for more details.
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
24 #include "coretypes.h"
26 #include "insn-codes.h"
31 #include "tree-pass.h"
33 #include "optabs-tree.h"
34 #include "gimple-pretty-print.h"
35 #include "diagnostic-core.h"
37 #include "fold-const.h"
38 #include "stor-layout.h"
41 #include "gimple-fold.h"
43 #include "gimple-iterator.h"
44 #include "gimple-walk.h"
49 // Return the upper limit for a type.
51 static inline wide_int
52 max_limit (const_tree type
)
54 return wi::max_value (TYPE_PRECISION (type
) , TYPE_SIGN (type
));
57 // Return the lower limit for a type.
59 static inline wide_int
60 min_limit (const_tree type
)
62 return wi::min_value (TYPE_PRECISION (type
) , TYPE_SIGN (type
));
65 // If the range of either op1 or op2 is undefined, set the result to
66 // varying and return TRUE. If the caller truely cares about a result,
67 // they should pass in a varying if it has an undefined that it wants
68 // treated as a varying.
71 empty_range_varying (irange
&r
, tree type
,
72 const irange
&op1
, const irange
& op2
)
74 if (op1
.undefined_p () || op2
.undefined_p ())
83 // Return false if shifting by OP is undefined behavior. Otherwise, return
84 // true and the range it is to be shifted by. This allows trimming out of
85 // undefined ranges, leaving only valid ranges if there are any.
88 get_shift_range (irange
&r
, tree type
, const irange
&op
)
90 if (op
.undefined_p ())
93 // Build valid range and intersect it with the shift range.
94 r
= value_range (build_int_cst_type (op
.type (), 0),
95 build_int_cst_type (op
.type (), TYPE_PRECISION (type
) - 1));
98 // If there are no valid ranges in the shift range, returned false.
104 // Return TRUE if 0 is within [WMIN, WMAX].
107 wi_includes_zero_p (tree type
, const wide_int
&wmin
, const wide_int
&wmax
)
109 signop sign
= TYPE_SIGN (type
);
110 return wi::le_p (wmin
, 0, sign
) && wi::ge_p (wmax
, 0, sign
);
113 // Return TRUE if [WMIN, WMAX] is the singleton 0.
116 wi_zero_p (tree type
, const wide_int
&wmin
, const wide_int
&wmax
)
118 unsigned prec
= TYPE_PRECISION (type
);
119 return wmin
== wmax
&& wi::eq_p (wmin
, wi::zero (prec
));
122 // Default wide_int fold operation returns [MIN, MAX].
125 range_operator::wi_fold (irange
&r
, tree type
,
126 const wide_int
&lh_lb ATTRIBUTE_UNUSED
,
127 const wide_int
&lh_ub ATTRIBUTE_UNUSED
,
128 const wide_int
&rh_lb ATTRIBUTE_UNUSED
,
129 const wide_int
&rh_ub ATTRIBUTE_UNUSED
) const
131 gcc_checking_assert (irange::supports_type_p (type
));
132 r
.set_varying (type
);
135 // The default for fold is to break all ranges into sub-ranges and
136 // invoke the wi_fold method on each sub-range pair.
139 range_operator::fold_range (irange
&r
, tree type
,
141 const irange
&rh
) const
143 gcc_checking_assert (irange::supports_type_p (type
));
144 if (empty_range_varying (r
, type
, lh
, rh
))
147 unsigned num_lh
= lh
.num_pairs ();
148 unsigned num_rh
= rh
.num_pairs ();
150 // If both ranges are single pairs, fold directly into the result range.
151 if (num_lh
== 1 && num_rh
== 1)
153 wi_fold (r
, type
, lh
.lower_bound (0), lh
.upper_bound (0),
154 rh
.lower_bound (0), rh
.upper_bound (0));
160 for (unsigned x
= 0; x
< num_lh
; ++x
)
161 for (unsigned y
= 0; y
< num_rh
; ++y
)
163 wide_int lh_lb
= lh
.lower_bound (x
);
164 wide_int lh_ub
= lh
.upper_bound (x
);
165 wide_int rh_lb
= rh
.lower_bound (y
);
166 wide_int rh_ub
= rh
.upper_bound (y
);
167 wi_fold (tmp
, type
, lh_lb
, lh_ub
, rh_lb
, rh_ub
);
175 // The default for op1_range is to return false.
178 range_operator::op1_range (irange
&r ATTRIBUTE_UNUSED
,
179 tree type ATTRIBUTE_UNUSED
,
180 const irange
&lhs ATTRIBUTE_UNUSED
,
181 const irange
&op2 ATTRIBUTE_UNUSED
) const
186 // The default for op2_range is to return false.
189 range_operator::op2_range (irange
&r ATTRIBUTE_UNUSED
,
190 tree type ATTRIBUTE_UNUSED
,
191 const irange
&lhs ATTRIBUTE_UNUSED
,
192 const irange
&op1 ATTRIBUTE_UNUSED
) const
198 // Create and return a range from a pair of wide-ints that are known
199 // to have overflowed (or underflowed).
202 value_range_from_overflowed_bounds (irange
&r
, tree type
,
203 const wide_int
&wmin
,
204 const wide_int
&wmax
)
206 const signop sgn
= TYPE_SIGN (type
);
207 const unsigned int prec
= TYPE_PRECISION (type
);
209 wide_int tmin
= wide_int::from (wmin
, prec
, sgn
);
210 wide_int tmax
= wide_int::from (wmax
, prec
, sgn
);
215 if (wi::cmp (tmin
, tmax
, sgn
) < 0)
218 if (wi::cmp (tmax
, tem
, sgn
) > 0)
221 // If the anti-range would cover nothing, drop to varying.
222 // Likewise if the anti-range bounds are outside of the types
224 if (covers
|| wi::cmp (tmin
, tmax
, sgn
) > 0)
225 r
.set_varying (type
);
228 tree tree_min
= wide_int_to_tree (type
, tmin
);
229 tree tree_max
= wide_int_to_tree (type
, tmax
);
230 r
.set (tree_min
, tree_max
, VR_ANTI_RANGE
);
234 // Create and return a range from a pair of wide-ints. MIN_OVF and
235 // MAX_OVF describe any overflow that might have occurred while
236 // calculating WMIN and WMAX respectively.
239 value_range_with_overflow (irange
&r
, tree type
,
240 const wide_int
&wmin
, const wide_int
&wmax
,
241 wi::overflow_type min_ovf
= wi::OVF_NONE
,
242 wi::overflow_type max_ovf
= wi::OVF_NONE
)
244 const signop sgn
= TYPE_SIGN (type
);
245 const unsigned int prec
= TYPE_PRECISION (type
);
246 const bool overflow_wraps
= TYPE_OVERFLOW_WRAPS (type
);
248 // For one bit precision if max != min, then the range covers all
250 if (prec
== 1 && wi::ne_p (wmax
, wmin
))
252 r
.set_varying (type
);
258 // If overflow wraps, truncate the values and adjust the range,
259 // kind, and bounds appropriately.
260 if ((min_ovf
!= wi::OVF_NONE
) == (max_ovf
!= wi::OVF_NONE
))
262 wide_int tmin
= wide_int::from (wmin
, prec
, sgn
);
263 wide_int tmax
= wide_int::from (wmax
, prec
, sgn
);
264 // If the limits are swapped, we wrapped around and cover
266 if (wi::gt_p (tmin
, tmax
, sgn
))
267 r
.set_varying (type
);
269 // No overflow or both overflow or underflow. The range
270 // kind stays normal.
271 r
.set (wide_int_to_tree (type
, tmin
),
272 wide_int_to_tree (type
, tmax
));
276 if ((min_ovf
== wi::OVF_UNDERFLOW
&& max_ovf
== wi::OVF_NONE
)
277 || (max_ovf
== wi::OVF_OVERFLOW
&& min_ovf
== wi::OVF_NONE
))
278 value_range_from_overflowed_bounds (r
, type
, wmin
, wmax
);
280 // Other underflow and/or overflow, drop to VR_VARYING.
281 r
.set_varying (type
);
285 // If both bounds either underflowed or overflowed, then the result
287 if ((min_ovf
== wi::OVF_OVERFLOW
&& max_ovf
== wi::OVF_OVERFLOW
)
288 || (min_ovf
== wi::OVF_UNDERFLOW
&& max_ovf
== wi::OVF_UNDERFLOW
))
294 // If overflow does not wrap, saturate to [MIN, MAX].
295 wide_int new_lb
, new_ub
;
296 if (min_ovf
== wi::OVF_UNDERFLOW
)
297 new_lb
= wi::min_value (prec
, sgn
);
298 else if (min_ovf
== wi::OVF_OVERFLOW
)
299 new_lb
= wi::max_value (prec
, sgn
);
303 if (max_ovf
== wi::OVF_UNDERFLOW
)
304 new_ub
= wi::min_value (prec
, sgn
);
305 else if (max_ovf
== wi::OVF_OVERFLOW
)
306 new_ub
= wi::max_value (prec
, sgn
);
310 r
.set (wide_int_to_tree (type
, new_lb
),
311 wide_int_to_tree (type
, new_ub
));
315 // Create and return a range from a pair of wide-ints. Canonicalize
316 // the case where the bounds are swapped. In which case, we transform
317 // [10,5] into [MIN,5][10,MAX].
320 create_possibly_reversed_range (irange
&r
, tree type
,
321 const wide_int
&new_lb
, const wide_int
&new_ub
)
323 signop s
= TYPE_SIGN (type
);
324 // If the bounds are swapped, treat the result as if an overflow occured.
325 if (wi::gt_p (new_lb
, new_ub
, s
))
326 value_range_from_overflowed_bounds (r
, type
, new_lb
, new_ub
);
328 // Otherwise it's just a normal range.
329 r
.set (wide_int_to_tree (type
, new_lb
), wide_int_to_tree (type
, new_ub
));
332 // Return an irange instance that is a boolean TRUE.
334 static inline int_range
<1>
335 range_true (tree type
)
337 unsigned prec
= TYPE_PRECISION (type
);
338 return int_range
<1> (type
, wi::one (prec
), wi::one (prec
));
341 // Return an irange instance that is a boolean FALSE.
343 static inline int_range
<1>
344 range_false (tree type
)
346 unsigned prec
= TYPE_PRECISION (type
);
347 return int_range
<1> (type
, wi::zero (prec
), wi::zero (prec
));
350 // Return an irange that covers both true and false.
352 static inline int_range
<1>
353 range_true_and_false (tree type
)
355 unsigned prec
= TYPE_PRECISION (type
);
356 return int_range
<1> (type
, wi::zero (prec
), wi::one (prec
));
359 enum bool_range_state
{ BRS_FALSE
, BRS_TRUE
, BRS_EMPTY
, BRS_FULL
};
361 // Return the summary information about boolean range LHS. If EMPTY/FULL,
362 // return the equivalent range for TYPE in R; if FALSE/TRUE, do nothing.
364 static bool_range_state
365 get_bool_state (irange
&r
, const irange
&lhs
, tree val_type
)
367 // If there is no result, then this is unexecutable.
368 if (lhs
.undefined_p ())
377 // For TRUE, we can't just test for [1,1] because Ada can have
378 // multi-bit booleans, and TRUE values can be: [1, MAX], ~[0], etc.
379 if (lhs
.contains_p (build_zero_cst (lhs
.type ())))
381 r
.set_varying (val_type
);
389 class operator_equal
: public range_operator
392 virtual bool fold_range (irange
&r
, tree type
,
394 const irange
&op2
) const;
395 virtual bool op1_range (irange
&r
, tree type
,
397 const irange
&val
) const;
398 virtual bool op2_range (irange
&r
, tree type
,
400 const irange
&val
) const;
404 operator_equal::fold_range (irange
&r
, tree type
,
406 const irange
&op2
) const
408 if (empty_range_varying (r
, type
, op1
, op2
))
411 // We can be sure the values are always equal or not if both ranges
412 // consist of a single value, and then compare them.
413 if (wi::eq_p (op1
.lower_bound (), op1
.upper_bound ())
414 && wi::eq_p (op2
.lower_bound (), op2
.upper_bound ()))
416 if (wi::eq_p (op1
.lower_bound (), op2
.upper_bound()))
417 r
= range_true (type
);
419 r
= range_false (type
);
423 // If ranges do not intersect, we know the range is not equal,
424 // otherwise we don't know anything for sure.
425 int_range_max tmp
= op1
;
427 if (tmp
.undefined_p ())
428 r
= range_false (type
);
430 r
= range_true_and_false (type
);
436 operator_equal::op1_range (irange
&r
, tree type
,
438 const irange
&op2
) const
440 switch (get_bool_state (r
, lhs
, type
))
443 // If the result is false, the only time we know anything is
444 // if OP2 is a constant.
445 if (wi::eq_p (op2
.lower_bound(), op2
.upper_bound()))
451 r
.set_varying (type
);
455 // If it's true, the result is the same as OP2.
466 operator_equal::op2_range (irange
&r
, tree type
,
468 const irange
&op1
) const
470 return operator_equal::op1_range (r
, type
, lhs
, op1
);
474 class operator_not_equal
: public range_operator
477 virtual bool fold_range (irange
&r
, tree type
,
479 const irange
&op2
) const;
480 virtual bool op1_range (irange
&r
, tree type
,
482 const irange
&op2
) const;
483 virtual bool op2_range (irange
&r
, tree type
,
485 const irange
&op1
) const;
489 operator_not_equal::fold_range (irange
&r
, tree type
,
491 const irange
&op2
) const
493 if (empty_range_varying (r
, type
, op1
, op2
))
496 // We can be sure the values are always equal or not if both ranges
497 // consist of a single value, and then compare them.
498 if (wi::eq_p (op1
.lower_bound (), op1
.upper_bound ())
499 && wi::eq_p (op2
.lower_bound (), op2
.upper_bound ()))
501 if (wi::ne_p (op1
.lower_bound (), op2
.upper_bound()))
502 r
= range_true (type
);
504 r
= range_false (type
);
508 // If ranges do not intersect, we know the range is not equal,
509 // otherwise we don't know anything for sure.
510 int_range_max tmp
= op1
;
512 if (tmp
.undefined_p ())
513 r
= range_true (type
);
515 r
= range_true_and_false (type
);
521 operator_not_equal::op1_range (irange
&r
, tree type
,
523 const irange
&op2
) const
525 switch (get_bool_state (r
, lhs
, type
))
528 // If the result is true, the only time we know anything is if
529 // OP2 is a constant.
530 if (wi::eq_p (op2
.lower_bound(), op2
.upper_bound()))
536 r
.set_varying (type
);
540 // If it's false, the result is the same as OP2.
552 operator_not_equal::op2_range (irange
&r
, tree type
,
554 const irange
&op1
) const
556 return operator_not_equal::op1_range (r
, type
, lhs
, op1
);
559 // (X < VAL) produces the range of [MIN, VAL - 1].
562 build_lt (irange
&r
, tree type
, const wide_int
&val
)
564 wi::overflow_type ov
;
565 wide_int lim
= wi::sub (val
, 1, TYPE_SIGN (type
), &ov
);
567 // If val - 1 underflows, check if X < MIN, which is an empty range.
571 r
= int_range
<1> (type
, min_limit (type
), lim
);
574 // (X <= VAL) produces the range of [MIN, VAL].
577 build_le (irange
&r
, tree type
, const wide_int
&val
)
579 r
= int_range
<1> (type
, min_limit (type
), val
);
582 // (X > VAL) produces the range of [VAL + 1, MAX].
585 build_gt (irange
&r
, tree type
, const wide_int
&val
)
587 wi::overflow_type ov
;
588 wide_int lim
= wi::add (val
, 1, TYPE_SIGN (type
), &ov
);
589 // If val + 1 overflows, check is for X > MAX, which is an empty range.
593 r
= int_range
<1> (type
, lim
, max_limit (type
));
596 // (X >= val) produces the range of [VAL, MAX].
599 build_ge (irange
&r
, tree type
, const wide_int
&val
)
601 r
= int_range
<1> (type
, val
, max_limit (type
));
605 class operator_lt
: public range_operator
608 virtual bool fold_range (irange
&r
, tree type
,
610 const irange
&op2
) const;
611 virtual bool op1_range (irange
&r
, tree type
,
613 const irange
&op2
) const;
614 virtual bool op2_range (irange
&r
, tree type
,
616 const irange
&op1
) const;
620 operator_lt::fold_range (irange
&r
, tree type
,
622 const irange
&op2
) const
624 if (empty_range_varying (r
, type
, op1
, op2
))
627 signop sign
= TYPE_SIGN (op1
.type ());
628 gcc_checking_assert (sign
== TYPE_SIGN (op2
.type ()));
630 if (wi::lt_p (op1
.upper_bound (), op2
.lower_bound (), sign
))
631 r
= range_true (type
);
632 else if (!wi::lt_p (op1
.lower_bound (), op2
.upper_bound (), sign
))
633 r
= range_false (type
);
635 r
= range_true_and_false (type
);
640 operator_lt::op1_range (irange
&r
, tree type
,
642 const irange
&op2
) const
644 switch (get_bool_state (r
, lhs
, type
))
647 build_lt (r
, type
, op2
.upper_bound ());
651 build_ge (r
, type
, op2
.lower_bound ());
661 operator_lt::op2_range (irange
&r
, tree type
,
663 const irange
&op1
) const
665 switch (get_bool_state (r
, lhs
, type
))
668 build_le (r
, type
, op1
.upper_bound ());
672 build_gt (r
, type
, op1
.lower_bound ());
682 class operator_le
: public range_operator
685 virtual bool fold_range (irange
&r
, tree type
,
687 const irange
&op2
) const;
688 virtual bool op1_range (irange
&r
, tree type
,
690 const irange
&op2
) const;
691 virtual bool op2_range (irange
&r
, tree type
,
693 const irange
&op1
) const;
697 operator_le::fold_range (irange
&r
, tree type
,
699 const irange
&op2
) const
701 if (empty_range_varying (r
, type
, op1
, op2
))
704 signop sign
= TYPE_SIGN (op1
.type ());
705 gcc_checking_assert (sign
== TYPE_SIGN (op2
.type ()));
707 if (wi::le_p (op1
.upper_bound (), op2
.lower_bound (), sign
))
708 r
= range_true (type
);
709 else if (!wi::le_p (op1
.lower_bound (), op2
.upper_bound (), sign
))
710 r
= range_false (type
);
712 r
= range_true_and_false (type
);
717 operator_le::op1_range (irange
&r
, tree type
,
719 const irange
&op2
) const
721 switch (get_bool_state (r
, lhs
, type
))
724 build_le (r
, type
, op2
.upper_bound ());
728 build_gt (r
, type
, op2
.lower_bound ());
738 operator_le::op2_range (irange
&r
, tree type
,
740 const irange
&op1
) const
742 switch (get_bool_state (r
, lhs
, type
))
745 build_lt (r
, type
, op1
.upper_bound ());
749 build_ge (r
, type
, op1
.lower_bound ());
759 class operator_gt
: public range_operator
762 virtual bool fold_range (irange
&r
, tree type
,
764 const irange
&op2
) const;
765 virtual bool op1_range (irange
&r
, tree type
,
767 const irange
&op2
) const;
768 virtual bool op2_range (irange
&r
, tree type
,
770 const irange
&op1
) const;
774 operator_gt::fold_range (irange
&r
, tree type
,
775 const irange
&op1
, const irange
&op2
) const
777 if (empty_range_varying (r
, type
, op1
, op2
))
780 signop sign
= TYPE_SIGN (op1
.type ());
781 gcc_checking_assert (sign
== TYPE_SIGN (op2
.type ()));
783 if (wi::gt_p (op1
.lower_bound (), op2
.upper_bound (), sign
))
784 r
= range_true (type
);
785 else if (!wi::gt_p (op1
.upper_bound (), op2
.lower_bound (), sign
))
786 r
= range_false (type
);
788 r
= range_true_and_false (type
);
793 operator_gt::op1_range (irange
&r
, tree type
,
794 const irange
&lhs
, const irange
&op2
) const
796 switch (get_bool_state (r
, lhs
, type
))
799 build_gt (r
, type
, op2
.lower_bound ());
803 build_le (r
, type
, op2
.upper_bound ());
813 operator_gt::op2_range (irange
&r
, tree type
,
815 const irange
&op1
) const
817 switch (get_bool_state (r
, lhs
, type
))
820 build_ge (r
, type
, op1
.lower_bound ());
824 build_lt (r
, type
, op1
.upper_bound ());
834 class operator_ge
: public range_operator
837 virtual bool fold_range (irange
&r
, tree type
,
839 const irange
&op2
) const;
840 virtual bool op1_range (irange
&r
, tree type
,
842 const irange
&op2
) const;
843 virtual bool op2_range (irange
&r
, tree type
,
845 const irange
&op1
) const;
849 operator_ge::fold_range (irange
&r
, tree type
,
851 const irange
&op2
) const
853 if (empty_range_varying (r
, type
, op1
, op2
))
856 signop sign
= TYPE_SIGN (op1
.type ());
857 gcc_checking_assert (sign
== TYPE_SIGN (op2
.type ()));
859 if (wi::ge_p (op1
.lower_bound (), op2
.upper_bound (), sign
))
860 r
= range_true (type
);
861 else if (!wi::ge_p (op1
.upper_bound (), op2
.lower_bound (), sign
))
862 r
= range_false (type
);
864 r
= range_true_and_false (type
);
869 operator_ge::op1_range (irange
&r
, tree type
,
871 const irange
&op2
) const
873 switch (get_bool_state (r
, lhs
, type
))
876 build_ge (r
, type
, op2
.lower_bound ());
880 build_lt (r
, type
, op2
.upper_bound ());
890 operator_ge::op2_range (irange
&r
, tree type
,
892 const irange
&op1
) const
894 switch (get_bool_state (r
, lhs
, type
))
897 build_gt (r
, type
, op1
.lower_bound ());
901 build_le (r
, type
, op1
.upper_bound ());
911 class operator_plus
: public range_operator
914 virtual bool op1_range (irange
&r
, tree type
,
916 const irange
&op2
) const;
917 virtual bool op2_range (irange
&r
, tree type
,
919 const irange
&op1
) const;
920 virtual void wi_fold (irange
&r
, tree type
,
921 const wide_int
&lh_lb
,
922 const wide_int
&lh_ub
,
923 const wide_int
&rh_lb
,
924 const wide_int
&rh_ub
) const;
928 operator_plus::wi_fold (irange
&r
, tree type
,
929 const wide_int
&lh_lb
, const wide_int
&lh_ub
,
930 const wide_int
&rh_lb
, const wide_int
&rh_ub
) const
932 wi::overflow_type ov_lb
, ov_ub
;
933 signop s
= TYPE_SIGN (type
);
934 wide_int new_lb
= wi::add (lh_lb
, rh_lb
, s
, &ov_lb
);
935 wide_int new_ub
= wi::add (lh_ub
, rh_ub
, s
, &ov_ub
);
936 value_range_with_overflow (r
, type
, new_lb
, new_ub
, ov_lb
, ov_ub
);
940 operator_plus::op1_range (irange
&r
, tree type
,
942 const irange
&op2
) const
944 return range_op_handler (MINUS_EXPR
, type
)->fold_range (r
, type
, lhs
, op2
);
948 operator_plus::op2_range (irange
&r
, tree type
,
950 const irange
&op1
) const
952 return range_op_handler (MINUS_EXPR
, type
)->fold_range (r
, type
, lhs
, op1
);
956 class operator_minus
: public range_operator
959 virtual bool op1_range (irange
&r
, tree type
,
961 const irange
&op2
) const;
962 virtual bool op2_range (irange
&r
, tree type
,
964 const irange
&op1
) const;
965 virtual void wi_fold (irange
&r
, tree type
,
966 const wide_int
&lh_lb
,
967 const wide_int
&lh_ub
,
968 const wide_int
&rh_lb
,
969 const wide_int
&rh_ub
) const;
973 operator_minus::wi_fold (irange
&r
, tree type
,
974 const wide_int
&lh_lb
, const wide_int
&lh_ub
,
975 const wide_int
&rh_lb
, const wide_int
&rh_ub
) const
977 wi::overflow_type ov_lb
, ov_ub
;
978 signop s
= TYPE_SIGN (type
);
979 wide_int new_lb
= wi::sub (lh_lb
, rh_ub
, s
, &ov_lb
);
980 wide_int new_ub
= wi::sub (lh_ub
, rh_lb
, s
, &ov_ub
);
981 value_range_with_overflow (r
, type
, new_lb
, new_ub
, ov_lb
, ov_ub
);
985 operator_minus::op1_range (irange
&r
, tree type
,
987 const irange
&op2
) const
989 return range_op_handler (PLUS_EXPR
, type
)->fold_range (r
, type
, lhs
, op2
);
993 operator_minus::op2_range (irange
&r
, tree type
,
995 const irange
&op1
) const
997 return fold_range (r
, type
, op1
, lhs
);
1001 class operator_min
: public range_operator
1004 virtual void wi_fold (irange
&r
, tree type
,
1005 const wide_int
&lh_lb
,
1006 const wide_int
&lh_ub
,
1007 const wide_int
&rh_lb
,
1008 const wide_int
&rh_ub
) const;
1012 operator_min::wi_fold (irange
&r
, tree type
,
1013 const wide_int
&lh_lb
, const wide_int
&lh_ub
,
1014 const wide_int
&rh_lb
, const wide_int
&rh_ub
) const
1016 signop s
= TYPE_SIGN (type
);
1017 wide_int new_lb
= wi::min (lh_lb
, rh_lb
, s
);
1018 wide_int new_ub
= wi::min (lh_ub
, rh_ub
, s
);
1019 value_range_with_overflow (r
, type
, new_lb
, new_ub
);
1023 class operator_max
: public range_operator
1026 virtual void wi_fold (irange
&r
, tree type
,
1027 const wide_int
&lh_lb
,
1028 const wide_int
&lh_ub
,
1029 const wide_int
&rh_lb
,
1030 const wide_int
&rh_ub
) const;
1034 operator_max::wi_fold (irange
&r
, tree type
,
1035 const wide_int
&lh_lb
, const wide_int
&lh_ub
,
1036 const wide_int
&rh_lb
, const wide_int
&rh_ub
) const
1038 signop s
= TYPE_SIGN (type
);
1039 wide_int new_lb
= wi::max (lh_lb
, rh_lb
, s
);
1040 wide_int new_ub
= wi::max (lh_ub
, rh_ub
, s
);
1041 value_range_with_overflow (r
, type
, new_lb
, new_ub
);
1045 class cross_product_operator
: public range_operator
1048 // Perform an operation between two wide-ints and place the result
1049 // in R. Return true if the operation overflowed.
1050 virtual bool wi_op_overflows (wide_int
&r
,
1053 const wide_int
&) const = 0;
1055 // Calculate the cross product of two sets of sub-ranges and return it.
1056 void wi_cross_product (irange
&r
, tree type
,
1057 const wide_int
&lh_lb
,
1058 const wide_int
&lh_ub
,
1059 const wide_int
&rh_lb
,
1060 const wide_int
&rh_ub
) const;
1063 // Calculate the cross product of two sets of ranges and return it.
1065 // Multiplications, divisions and shifts are a bit tricky to handle,
1066 // depending on the mix of signs we have in the two ranges, we need to
1067 // operate on different values to get the minimum and maximum values
1068 // for the new range. One approach is to figure out all the
1069 // variations of range combinations and do the operations.
1071 // However, this involves several calls to compare_values and it is
1072 // pretty convoluted. It's simpler to do the 4 operations (MIN0 OP
1073 // MIN1, MIN0 OP MAX1, MAX0 OP MIN1 and MAX0 OP MAX0 OP MAX1) and then
1074 // figure the smallest and largest values to form the new range.
1077 cross_product_operator::wi_cross_product (irange
&r
, tree type
,
1078 const wide_int
&lh_lb
,
1079 const wide_int
&lh_ub
,
1080 const wide_int
&rh_lb
,
1081 const wide_int
&rh_ub
) const
1083 wide_int cp1
, cp2
, cp3
, cp4
;
1084 // Default to varying.
1085 r
.set_varying (type
);
1087 // Compute the 4 cross operations, bailing if we get an overflow we
1089 if (wi_op_overflows (cp1
, type
, lh_lb
, rh_lb
))
1091 if (wi::eq_p (lh_lb
, lh_ub
))
1093 else if (wi_op_overflows (cp3
, type
, lh_ub
, rh_lb
))
1095 if (wi::eq_p (rh_lb
, rh_ub
))
1097 else if (wi_op_overflows (cp2
, type
, lh_lb
, rh_ub
))
1099 if (wi::eq_p (lh_lb
, lh_ub
))
1101 else if (wi_op_overflows (cp4
, type
, lh_ub
, rh_ub
))
1105 signop sign
= TYPE_SIGN (type
);
1106 if (wi::gt_p (cp1
, cp2
, sign
))
1107 std::swap (cp1
, cp2
);
1108 if (wi::gt_p (cp3
, cp4
, sign
))
1109 std::swap (cp3
, cp4
);
1111 // Choose min and max from the ordered pairs.
1112 wide_int res_lb
= wi::min (cp1
, cp3
, sign
);
1113 wide_int res_ub
= wi::max (cp2
, cp4
, sign
);
1114 value_range_with_overflow (r
, type
, res_lb
, res_ub
);
1118 class operator_mult
: public cross_product_operator
1121 virtual void wi_fold (irange
&r
, tree type
,
1122 const wide_int
&lh_lb
,
1123 const wide_int
&lh_ub
,
1124 const wide_int
&rh_lb
,
1125 const wide_int
&rh_ub
) const;
1126 virtual bool wi_op_overflows (wide_int
&res
, tree type
,
1127 const wide_int
&w0
, const wide_int
&w1
) const;
1128 virtual bool op1_range (irange
&r
, tree type
,
1130 const irange
&op2
) const;
1131 virtual bool op2_range (irange
&r
, tree type
,
1133 const irange
&op1
) const;
1137 operator_mult::op1_range (irange
&r
, tree type
,
1138 const irange
&lhs
, const irange
&op2
) const
1142 // We can't solve 0 = OP1 * N by dividing by N with a wrapping type.
1143 // For example: For 0 = OP1 * 2, OP1 could be 0, or MAXINT, whereas
1144 // for 4 = OP1 * 2, OP1 could be 2 or 130 (unsigned 8-bit)
1145 if (TYPE_OVERFLOW_WRAPS (type
))
1148 if (op2
.singleton_p (&offset
) && !integer_zerop (offset
))
1149 return range_op_handler (TRUNC_DIV_EXPR
, type
)->fold_range (r
, type
,
1155 operator_mult::op2_range (irange
&r
, tree type
,
1156 const irange
&lhs
, const irange
&op1
) const
1158 return operator_mult::op1_range (r
, type
, lhs
, op1
);
1162 operator_mult::wi_op_overflows (wide_int
&res
, tree type
,
1163 const wide_int
&w0
, const wide_int
&w1
) const
1165 wi::overflow_type overflow
= wi::OVF_NONE
;
1166 signop sign
= TYPE_SIGN (type
);
1167 res
= wi::mul (w0
, w1
, sign
, &overflow
);
1168 if (overflow
&& TYPE_OVERFLOW_UNDEFINED (type
))
1170 // For multiplication, the sign of the overflow is given
1171 // by the comparison of the signs of the operands.
1172 if (sign
== UNSIGNED
|| w0
.sign_mask () == w1
.sign_mask ())
1173 res
= wi::max_value (w0
.get_precision (), sign
);
1175 res
= wi::min_value (w0
.get_precision (), sign
);
1182 operator_mult::wi_fold (irange
&r
, tree type
,
1183 const wide_int
&lh_lb
, const wide_int
&lh_ub
,
1184 const wide_int
&rh_lb
, const wide_int
&rh_ub
) const
1186 if (TYPE_OVERFLOW_UNDEFINED (type
))
1188 wi_cross_product (r
, type
, lh_lb
, lh_ub
, rh_lb
, rh_ub
);
1192 // Multiply the ranges when overflow wraps. This is basically fancy
1193 // code so we don't drop to varying with an unsigned
1196 // This test requires 2*prec bits if both operands are signed and
1197 // 2*prec + 2 bits if either is not. Therefore, extend the values
1198 // using the sign of the result to PREC2. From here on out,
1199 // everthing is just signed math no matter what the input types
1202 signop sign
= TYPE_SIGN (type
);
1203 unsigned prec
= TYPE_PRECISION (type
);
1204 widest2_int min0
= widest2_int::from (lh_lb
, sign
);
1205 widest2_int max0
= widest2_int::from (lh_ub
, sign
);
1206 widest2_int min1
= widest2_int::from (rh_lb
, sign
);
1207 widest2_int max1
= widest2_int::from (rh_ub
, sign
);
1208 widest2_int sizem1
= wi::mask
<widest2_int
> (prec
, false);
1209 widest2_int size
= sizem1
+ 1;
1211 // Canonicalize the intervals.
1212 if (sign
== UNSIGNED
)
1214 if (wi::ltu_p (size
, min0
+ max0
))
1219 if (wi::ltu_p (size
, min1
+ max1
))
1226 // Sort the 4 products so that min is in prod0 and max is in
1228 widest2_int prod0
= min0
* min1
;
1229 widest2_int prod1
= min0
* max1
;
1230 widest2_int prod2
= max0
* min1
;
1231 widest2_int prod3
= max0
* max1
;
1233 // min0min1 > max0max1
1235 std::swap (prod0
, prod3
);
1237 // min0max1 > max0min1
1239 std::swap (prod1
, prod2
);
1242 std::swap (prod0
, prod1
);
1245 std::swap (prod2
, prod3
);
1248 prod2
= prod3
- prod0
;
1249 if (wi::geu_p (prod2
, sizem1
))
1250 // The range covers all values.
1251 r
.set_varying (type
);
1254 wide_int new_lb
= wide_int::from (prod0
, prec
, sign
);
1255 wide_int new_ub
= wide_int::from (prod3
, prec
, sign
);
1256 create_possibly_reversed_range (r
, type
, new_lb
, new_ub
);
1261 class operator_div
: public cross_product_operator
1264 operator_div (enum tree_code c
) { code
= c
; }
1265 virtual void wi_fold (irange
&r
, tree type
,
1266 const wide_int
&lh_lb
,
1267 const wide_int
&lh_ub
,
1268 const wide_int
&rh_lb
,
1269 const wide_int
&rh_ub
) const;
1270 virtual bool wi_op_overflows (wide_int
&res
, tree type
,
1271 const wide_int
&, const wide_int
&) const;
1273 enum tree_code code
;
1277 operator_div::wi_op_overflows (wide_int
&res
, tree type
,
1278 const wide_int
&w0
, const wide_int
&w1
) const
1283 wi::overflow_type overflow
= wi::OVF_NONE
;
1284 signop sign
= TYPE_SIGN (type
);
1288 case EXACT_DIV_EXPR
:
1289 // EXACT_DIV_EXPR is implemented as TRUNC_DIV_EXPR in
1290 // operator_exact_divide. No need to handle it here.
1293 case TRUNC_DIV_EXPR
:
1294 res
= wi::div_trunc (w0
, w1
, sign
, &overflow
);
1296 case FLOOR_DIV_EXPR
:
1297 res
= wi::div_floor (w0
, w1
, sign
, &overflow
);
1299 case ROUND_DIV_EXPR
:
1300 res
= wi::div_round (w0
, w1
, sign
, &overflow
);
1303 res
= wi::div_ceil (w0
, w1
, sign
, &overflow
);
1309 if (overflow
&& TYPE_OVERFLOW_UNDEFINED (type
))
1311 // For division, the only case is -INF / -1 = +INF.
1312 res
= wi::max_value (w0
.get_precision (), sign
);
1319 operator_div::wi_fold (irange
&r
, tree type
,
1320 const wide_int
&lh_lb
, const wide_int
&lh_ub
,
1321 const wide_int
&rh_lb
, const wide_int
&rh_ub
) const
1323 // If we know we will divide by zero...
1324 if (rh_lb
== 0 && rh_ub
== 0)
1326 r
.set_varying (type
);
1330 const wide_int dividend_min
= lh_lb
;
1331 const wide_int dividend_max
= lh_ub
;
1332 const wide_int divisor_min
= rh_lb
;
1333 const wide_int divisor_max
= rh_ub
;
1334 signop sign
= TYPE_SIGN (type
);
1335 unsigned prec
= TYPE_PRECISION (type
);
1336 wide_int extra_min
, extra_max
;
1338 // If we know we won't divide by zero, just do the division.
1339 if (!wi_includes_zero_p (type
, divisor_min
, divisor_max
))
1341 wi_cross_product (r
, type
, dividend_min
, dividend_max
,
1342 divisor_min
, divisor_max
);
1346 // If flag_non_call_exceptions, we must not eliminate a division by zero.
1347 if (cfun
->can_throw_non_call_exceptions
)
1349 r
.set_varying (type
);
1353 // If we're definitely dividing by zero, there's nothing to do.
1354 if (wi_zero_p (type
, divisor_min
, divisor_max
))
1356 r
.set_varying (type
);
1360 // Perform the division in 2 parts, [LB, -1] and [1, UB], which will
1361 // skip any division by zero.
1363 // First divide by the negative numbers, if any.
1364 if (wi::neg_p (divisor_min
, sign
))
1365 wi_cross_product (r
, type
, dividend_min
, dividend_max
,
1366 divisor_min
, wi::minus_one (prec
));
1370 // Then divide by the non-zero positive numbers, if any.
1371 if (wi::gt_p (divisor_max
, wi::zero (prec
), sign
))
1374 wi_cross_product (tmp
, type
, dividend_min
, dividend_max
,
1375 wi::one (prec
), divisor_max
);
1378 // We shouldn't still have undefined here.
1379 gcc_checking_assert (!r
.undefined_p ());
1382 operator_div
op_trunc_div (TRUNC_DIV_EXPR
);
1383 operator_div
op_floor_div (FLOOR_DIV_EXPR
);
1384 operator_div
op_round_div (ROUND_DIV_EXPR
);
1385 operator_div
op_ceil_div (CEIL_DIV_EXPR
);
1388 class operator_exact_divide
: public operator_div
1391 operator_exact_divide () : operator_div (TRUNC_DIV_EXPR
) { }
1392 virtual bool op1_range (irange
&r
, tree type
,
1394 const irange
&op2
) const;
1399 operator_exact_divide::op1_range (irange
&r
, tree type
,
1401 const irange
&op2
) const
1404 // [2, 4] = op1 / [3,3] since its exact divide, no need to worry about
1405 // remainders in the endpoints, so op1 = [2,4] * [3,3] = [6,12].
1406 // We wont bother trying to enumerate all the in between stuff :-P
1407 // TRUE accuraacy is [6,6][9,9][12,12]. This is unlikely to matter most of
1408 // the time however.
1409 // If op2 is a multiple of 2, we would be able to set some non-zero bits.
1410 if (op2
.singleton_p (&offset
)
1411 && !integer_zerop (offset
))
1412 return range_op_handler (MULT_EXPR
, type
)->fold_range (r
, type
, lhs
, op2
);
1417 class operator_lshift
: public cross_product_operator
1420 virtual bool op1_range (irange
&r
, tree type
,
1422 const irange
&op2
) const;
1423 virtual bool fold_range (irange
&r
, tree type
,
1425 const irange
&op2
) const;
1427 virtual void wi_fold (irange
&r
, tree type
,
1428 const wide_int
&lh_lb
, const wide_int
&lh_ub
,
1429 const wide_int
&rh_lb
, const wide_int
&rh_ub
) const;
1430 virtual bool wi_op_overflows (wide_int
&res
,
1433 const wide_int
&) const;
1436 class operator_rshift
: public cross_product_operator
1439 virtual bool fold_range (irange
&r
, tree type
,
1441 const irange
&op2
) const;
1442 virtual void wi_fold (irange
&r
, tree type
,
1443 const wide_int
&lh_lb
,
1444 const wide_int
&lh_ub
,
1445 const wide_int
&rh_lb
,
1446 const wide_int
&rh_ub
) const;
1447 virtual bool wi_op_overflows (wide_int
&res
,
1450 const wide_int
&w1
) const;
1451 virtual bool op1_range (irange
&, tree type
,
1453 const irange
&op2
) const;
1458 operator_lshift::fold_range (irange
&r
, tree type
,
1460 const irange
&op2
) const
1462 int_range_max shift_range
;
1463 if (!get_shift_range (shift_range
, type
, op2
))
1465 if (op2
.undefined_p ())
1468 r
.set_varying (type
);
1472 // Transform left shifts by constants into multiplies.
1473 if (shift_range
.singleton_p ())
1475 unsigned shift
= shift_range
.lower_bound ().to_uhwi ();
1476 wide_int tmp
= wi::set_bit_in_zero (shift
, TYPE_PRECISION (type
));
1477 int_range
<1> mult (type
, tmp
, tmp
);
1479 // Force wrapping multiplication.
1480 bool saved_flag_wrapv
= flag_wrapv
;
1481 bool saved_flag_wrapv_pointer
= flag_wrapv_pointer
;
1483 flag_wrapv_pointer
= 1;
1484 bool b
= op_mult
.fold_range (r
, type
, op1
, mult
);
1485 flag_wrapv
= saved_flag_wrapv
;
1486 flag_wrapv_pointer
= saved_flag_wrapv_pointer
;
1490 // Otherwise, invoke the generic fold routine.
1491 return range_operator::fold_range (r
, type
, op1
, shift_range
);
1495 operator_lshift::wi_fold (irange
&r
, tree type
,
1496 const wide_int
&lh_lb
, const wide_int
&lh_ub
,
1497 const wide_int
&rh_lb
, const wide_int
&rh_ub
) const
1499 signop sign
= TYPE_SIGN (type
);
1500 unsigned prec
= TYPE_PRECISION (type
);
1501 int overflow_pos
= sign
== SIGNED
? prec
- 1 : prec
;
1502 int bound_shift
= overflow_pos
- rh_ub
.to_shwi ();
1503 // If bound_shift == HOST_BITS_PER_WIDE_INT, the llshift can
1504 // overflow. However, for that to happen, rh.max needs to be zero,
1505 // which means rh is a singleton range of zero, which means it
1506 // should be handled by the lshift fold_range above.
1507 wide_int bound
= wi::set_bit_in_zero (bound_shift
, prec
);
1508 wide_int complement
= ~(bound
- 1);
1509 wide_int low_bound
, high_bound
;
1510 bool in_bounds
= false;
1512 if (sign
== UNSIGNED
)
1515 high_bound
= complement
;
1516 if (wi::ltu_p (lh_ub
, low_bound
))
1518 // [5, 6] << [1, 2] == [10, 24].
1519 // We're shifting out only zeroes, the value increases
1523 else if (wi::ltu_p (high_bound
, lh_lb
))
1525 // [0xffffff00, 0xffffffff] << [1, 2]
1526 // == [0xfffffc00, 0xfffffffe].
1527 // We're shifting out only ones, the value decreases
1534 // [-1, 1] << [1, 2] == [-4, 4]
1535 low_bound
= complement
;
1537 if (wi::lts_p (lh_ub
, high_bound
)
1538 && wi::lts_p (low_bound
, lh_lb
))
1540 // For non-negative numbers, we're shifting out only zeroes,
1541 // the value increases monotonically. For negative numbers,
1542 // we're shifting out only ones, the value decreases
1549 wi_cross_product (r
, type
, lh_lb
, lh_ub
, rh_lb
, rh_ub
);
1551 r
.set_varying (type
);
1555 operator_lshift::wi_op_overflows (wide_int
&res
, tree type
,
1556 const wide_int
&w0
, const wide_int
&w1
) const
1558 signop sign
= TYPE_SIGN (type
);
1561 // It's unclear from the C standard whether shifts can overflow.
1562 // The following code ignores overflow; perhaps a C standard
1563 // interpretation ruling is needed.
1564 res
= wi::rshift (w0
, -w1
, sign
);
1567 res
= wi::lshift (w0
, w1
);
1572 operator_lshift::op1_range (irange
&r
,
1575 const irange
&op2
) const
1578 if (op2
.singleton_p (&shift_amount
))
1580 wide_int shift
= wi::to_wide (shift_amount
);
1581 if (wi::lt_p (shift
, 0, SIGNED
))
1583 if (wi::ge_p (shift
, wi::uhwi (TYPE_PRECISION (type
),
1584 TYPE_PRECISION (op2
.type ())),
1593 // Work completely in unsigned mode to start.
1595 if (TYPE_SIGN (type
) == SIGNED
)
1597 int_range_max tmp
= lhs
;
1598 utype
= unsigned_type_for (type
);
1599 range_cast (tmp
, utype
);
1600 op_rshift
.fold_range (r
, utype
, tmp
, op2
);
1603 op_rshift
.fold_range (r
, utype
, lhs
, op2
);
1605 // Start with ranges which can produce the LHS by right shifting the
1606 // result by the shift amount.
1607 // ie [0x08, 0xF0] = op1 << 2 will start with
1608 // [00001000, 11110000] = op1 << 2
1609 // [0x02, 0x4C] aka [00000010, 00111100]
1611 // Then create a range from the LB with the least significant upper bit
1612 // set, to the upper bound with all the bits set.
1613 // This would be [0x42, 0xFC] aka [01000010, 11111100].
1615 // Ideally we do this for each subrange, but just lump them all for now.
1616 unsigned low_bits
= TYPE_PRECISION (utype
)
1617 - TREE_INT_CST_LOW (shift_amount
);
1618 wide_int up_mask
= wi::mask (low_bits
, true, TYPE_PRECISION (utype
));
1619 wide_int new_ub
= wi::bit_or (up_mask
, r
.upper_bound ());
1620 wide_int new_lb
= wi::set_bit (r
.lower_bound (), low_bits
);
1621 int_range
<2> fill_range (utype
, new_lb
, new_ub
);
1622 r
.union_ (fill_range
);
1625 range_cast (r
, type
);
1632 operator_rshift::op1_range (irange
&r
,
1635 const irange
&op2
) const
1638 if (op2
.singleton_p (&shift
))
1640 // Ignore nonsensical shifts.
1641 unsigned prec
= TYPE_PRECISION (type
);
1642 if (wi::ge_p (wi::to_wide (shift
),
1643 wi::uhwi (prec
, TYPE_PRECISION (TREE_TYPE (shift
))),
1646 if (wi::to_wide (shift
) == 0)
1652 // Folding the original operation may discard some impossible
1653 // ranges from the LHS.
1654 int_range_max lhs_refined
;
1655 op_rshift
.fold_range (lhs_refined
, type
, int_range
<1> (type
), op2
);
1656 lhs_refined
.intersect (lhs
);
1657 if (lhs_refined
.undefined_p ())
1662 int_range_max
shift_range (shift
, shift
);
1663 int_range_max lb
, ub
;
1664 op_lshift
.fold_range (lb
, type
, lhs_refined
, shift_range
);
1666 // 0000 0111 = OP1 >> 3
1668 // OP1 is anything from 0011 1000 to 0011 1111. That is, a
1669 // range from LHS<<3 plus a mask of the 3 bits we shifted on the
1670 // right hand side (0x07).
1671 tree mask
= fold_build1 (BIT_NOT_EXPR
, type
,
1672 fold_build2 (LSHIFT_EXPR
, type
,
1673 build_minus_one_cst (type
),
1675 int_range_max
mask_range (build_zero_cst (type
), mask
);
1676 op_plus
.fold_range (ub
, type
, lb
, mask_range
);
1679 if (!lhs_refined
.contains_p (build_zero_cst (type
)))
1681 mask_range
.invert ();
1682 r
.intersect (mask_range
);
1690 operator_rshift::wi_op_overflows (wide_int
&res
,
1693 const wide_int
&w1
) const
1695 signop sign
= TYPE_SIGN (type
);
1697 res
= wi::lshift (w0
, -w1
);
1700 // It's unclear from the C standard whether shifts can overflow.
1701 // The following code ignores overflow; perhaps a C standard
1702 // interpretation ruling is needed.
1703 res
= wi::rshift (w0
, w1
, sign
);
1709 operator_rshift::fold_range (irange
&r
, tree type
,
1711 const irange
&op2
) const
1713 int_range_max shift
;
1714 if (!get_shift_range (shift
, type
, op2
))
1716 if (op2
.undefined_p ())
1719 r
.set_varying (type
);
1723 return range_operator::fold_range (r
, type
, op1
, shift
);
1727 operator_rshift::wi_fold (irange
&r
, tree type
,
1728 const wide_int
&lh_lb
, const wide_int
&lh_ub
,
1729 const wide_int
&rh_lb
, const wide_int
&rh_ub
) const
1731 wi_cross_product (r
, type
, lh_lb
, lh_ub
, rh_lb
, rh_ub
);
1735 class operator_cast
: public range_operator
1738 virtual bool fold_range (irange
&r
, tree type
,
1740 const irange
&op2
) const;
1741 virtual bool op1_range (irange
&r
, tree type
,
1743 const irange
&op2
) const;
1745 bool truncating_cast_p (const irange
&inner
, const irange
&outer
) const;
1746 bool inside_domain_p (const wide_int
&min
, const wide_int
&max
,
1747 const irange
&outer
) const;
1748 void fold_pair (irange
&r
, unsigned index
, const irange
&inner
,
1749 const irange
&outer
) const;
1752 // Return TRUE if casting from INNER to OUTER is a truncating cast.
1755 operator_cast::truncating_cast_p (const irange
&inner
,
1756 const irange
&outer
) const
1758 return TYPE_PRECISION (outer
.type ()) < TYPE_PRECISION (inner
.type ());
1761 // Return TRUE if [MIN,MAX] is inside the domain of RANGE's type.
1764 operator_cast::inside_domain_p (const wide_int
&min
,
1765 const wide_int
&max
,
1766 const irange
&range
) const
1768 wide_int domain_min
= wi::to_wide (vrp_val_min (range
.type ()));
1769 wide_int domain_max
= wi::to_wide (vrp_val_max (range
.type ()));
1770 signop domain_sign
= TYPE_SIGN (range
.type ());
1771 return (wi::le_p (min
, domain_max
, domain_sign
)
1772 && wi::le_p (max
, domain_max
, domain_sign
)
1773 && wi::ge_p (min
, domain_min
, domain_sign
)
1774 && wi::ge_p (max
, domain_min
, domain_sign
));
1778 // Helper for fold_range which work on a pair at a time.
1781 operator_cast::fold_pair (irange
&r
, unsigned index
,
1782 const irange
&inner
,
1783 const irange
&outer
) const
1785 tree inner_type
= inner
.type ();
1786 tree outer_type
= outer
.type ();
1787 signop inner_sign
= TYPE_SIGN (inner_type
);
1788 unsigned outer_prec
= TYPE_PRECISION (outer_type
);
1790 // check to see if casting from INNER to OUTER is a conversion that
1791 // fits in the resulting OUTER type.
1792 wide_int inner_lb
= inner
.lower_bound (index
);
1793 wide_int inner_ub
= inner
.upper_bound (index
);
1794 if (truncating_cast_p (inner
, outer
))
1796 // We may be able to accomodate a truncating cast if the
1797 // resulting range can be represented in the target type...
1798 if (wi::rshift (wi::sub (inner_ub
, inner_lb
),
1799 wi::uhwi (outer_prec
, TYPE_PRECISION (inner
.type ())),
1802 r
.set_varying (outer_type
);
1806 // ...but we must still verify that the final range fits in the
1807 // domain. This catches -fstrict-enum restrictions where the domain
1808 // range is smaller than what fits in the underlying type.
1809 wide_int min
= wide_int::from (inner_lb
, outer_prec
, inner_sign
);
1810 wide_int max
= wide_int::from (inner_ub
, outer_prec
, inner_sign
);
1811 if (inside_domain_p (min
, max
, outer
))
1812 create_possibly_reversed_range (r
, outer_type
, min
, max
);
1814 r
.set_varying (outer_type
);
1819 operator_cast::fold_range (irange
&r
, tree type ATTRIBUTE_UNUSED
,
1820 const irange
&inner
,
1821 const irange
&outer
) const
1823 if (empty_range_varying (r
, type
, inner
, outer
))
1826 gcc_checking_assert (outer
.varying_p ());
1827 gcc_checking_assert (inner
.num_pairs () > 0);
1829 // Avoid a temporary by folding the first pair directly into the result.
1830 fold_pair (r
, 0, inner
, outer
);
1832 // Then process any additonal pairs by unioning with their results.
1833 for (unsigned x
= 1; x
< inner
.num_pairs (); ++x
)
1836 fold_pair (tmp
, x
, inner
, outer
);
1845 operator_cast::op1_range (irange
&r
, tree type
,
1847 const irange
&op2
) const
1849 tree lhs_type
= lhs
.type ();
1850 gcc_checking_assert (types_compatible_p (op2
.type(), type
));
1852 // If we are calculating a pointer, shortcut to what we really care about.
1853 if (POINTER_TYPE_P (type
))
1855 // Conversion from other pointers or a constant (including 0/NULL)
1856 // are straightforward.
1857 if (POINTER_TYPE_P (lhs
.type ())
1858 || (lhs
.singleton_p ()
1859 && TYPE_PRECISION (lhs
.type ()) >= TYPE_PRECISION (type
)))
1862 range_cast (r
, type
);
1866 // If the LHS is not a pointer nor a singleton, then it is
1867 // either VARYING or non-zero.
1868 if (!lhs
.contains_p (build_zero_cst (lhs
.type ())))
1869 r
.set_nonzero (type
);
1871 r
.set_varying (type
);
1877 if (truncating_cast_p (op2
, lhs
))
1879 if (lhs
.varying_p ())
1880 r
.set_varying (type
);
1883 // We want to insert the LHS as an unsigned value since it
1884 // would not trigger the signed bit of the larger type.
1885 int_range_max converted_lhs
= lhs
;
1886 range_cast (converted_lhs
, unsigned_type_for (lhs_type
));
1887 range_cast (converted_lhs
, type
);
1888 // Start by building the positive signed outer range for the type.
1889 wide_int lim
= wi::set_bit_in_zero (TYPE_PRECISION (lhs_type
),
1890 TYPE_PRECISION (type
));
1891 r
= int_range
<1> (type
, lim
, wi::max_value (TYPE_PRECISION (type
),
1893 // For the signed part, we need to simply union the 2 ranges now.
1894 r
.union_ (converted_lhs
);
1896 // Create maximal negative number outside of LHS bits.
1897 lim
= wi::mask (TYPE_PRECISION (lhs_type
), true,
1898 TYPE_PRECISION (type
));
1899 // Add this to the unsigned LHS range(s).
1900 int_range_max
lim_range (type
, lim
, lim
);
1901 int_range_max lhs_neg
;
1902 range_op_handler (PLUS_EXPR
, type
)->fold_range (lhs_neg
,
1906 // lhs_neg now has all the negative versions of the LHS.
1907 // Now union in all the values from SIGNED MIN (0x80000) to
1908 // lim-1 in order to fill in all the ranges with the upper
1911 // PR 97317. If the lhs has only 1 bit less precision than the rhs,
1912 // we don't need to create a range from min to lim-1
1913 // calculate neg range traps trying to create [lim, lim - 1].
1914 wide_int min_val
= wi::min_value (TYPE_PRECISION (type
), SIGNED
);
1917 int_range_max
neg (type
,
1918 wi::min_value (TYPE_PRECISION (type
),
1921 lhs_neg
.union_ (neg
);
1923 // And finally, munge the signed and unsigned portions.
1926 // And intersect with any known value passed in the extra operand.
1932 if (TYPE_PRECISION (lhs_type
) == TYPE_PRECISION (type
))
1936 // The cast is not truncating, and the range is restricted to
1937 // the range of the RHS by this assignment.
1939 // Cast the range of the RHS to the type of the LHS.
1940 fold_range (tmp
, lhs_type
, int_range
<1> (type
), int_range
<1> (lhs_type
));
1941 // Intersect this with the LHS range will produce the range,
1942 // which will be cast to the RHS type before returning.
1943 tmp
.intersect (lhs
);
1946 // Cast the calculated range to the type of the RHS.
1947 fold_range (r
, type
, tmp
, int_range
<1> (type
));
1952 class operator_logical_and
: public range_operator
1955 virtual bool fold_range (irange
&r
, tree type
,
1957 const irange
&rh
) const;
1958 virtual bool op1_range (irange
&r
, tree type
,
1960 const irange
&op2
) const;
1961 virtual bool op2_range (irange
&r
, tree type
,
1963 const irange
&op1
) const;
1968 operator_logical_and::fold_range (irange
&r
, tree type
,
1970 const irange
&rh
) const
1972 if (empty_range_varying (r
, type
, lh
, rh
))
1975 // 0 && anything is 0.
1976 if ((wi::eq_p (lh
.lower_bound (), 0) && wi::eq_p (lh
.upper_bound (), 0))
1977 || (wi::eq_p (lh
.lower_bound (), 0) && wi::eq_p (rh
.upper_bound (), 0)))
1978 r
= range_false (type
);
1979 else if (lh
.contains_p (build_zero_cst (lh
.type ()))
1980 || rh
.contains_p (build_zero_cst (rh
.type ())))
1981 // To reach this point, there must be a logical 1 on each side, and
1982 // the only remaining question is whether there is a zero or not.
1983 r
= range_true_and_false (type
);
1985 r
= range_true (type
);
1990 operator_logical_and::op1_range (irange
&r
, tree type
,
1992 const irange
&op2 ATTRIBUTE_UNUSED
) const
1994 switch (get_bool_state (r
, lhs
, type
))
1997 // A true result means both sides of the AND must be true.
1998 r
= range_true (type
);
2001 // Any other result means only one side has to be false, the
2002 // other side can be anything. So we cannott be sure of any
2004 r
= range_true_and_false (type
);
2011 operator_logical_and::op2_range (irange
&r
, tree type
,
2013 const irange
&op1
) const
2015 return operator_logical_and::op1_range (r
, type
, lhs
, op1
);
2019 class operator_bitwise_and
: public range_operator
2022 virtual bool fold_range (irange
&r
, tree type
,
2024 const irange
&rh
) const;
2025 virtual bool op1_range (irange
&r
, tree type
,
2027 const irange
&op2
) const;
2028 virtual bool op2_range (irange
&r
, tree type
,
2030 const irange
&op1
) const;
2031 virtual void wi_fold (irange
&r
, tree type
,
2032 const wide_int
&lh_lb
,
2033 const wide_int
&lh_ub
,
2034 const wide_int
&rh_lb
,
2035 const wide_int
&rh_ub
) const;
2037 void simple_op1_range_solver (irange
&r
, tree type
,
2039 const irange
&op2
) const;
2040 void remove_impossible_ranges (irange
&r
, const irange
&rh
) const;
2044 unsigned_singleton_p (const irange
&op
)
2047 if (op
.singleton_p (&mask
))
2049 wide_int x
= wi::to_wide (mask
);
2050 return wi::ge_p (x
, 0, TYPE_SIGN (op
.type ()));
2055 // Remove any ranges from R that are known to be impossible when an
2056 // range is ANDed with MASK.
2059 operator_bitwise_and::remove_impossible_ranges (irange
&r
,
2060 const irange
&rmask
) const
2062 if (r
.undefined_p () || !unsigned_singleton_p (rmask
))
2065 wide_int mask
= rmask
.lower_bound ();
2066 tree type
= r
.type ();
2067 int prec
= TYPE_PRECISION (type
);
2068 int leading_zeros
= wi::clz (mask
);
2069 int_range_max impossible_ranges
;
2071 /* We know that starting at the most significant bit, any 0 in the
2072 mask means the resulting range cannot contain a 1 in that same
2073 position. This means the following ranges are impossible:
2077 01xx xxxx [0100 0000, 0111 1111]
2078 001x xxxx [0010 0000, 0011 1111]
2079 0000 01xx [0000 0100, 0000 0111]
2080 0000 0001 [0000 0001, 0000 0001]
2082 wide_int one
= wi::one (prec
);
2083 for (int i
= 0; i
< prec
- leading_zeros
- 1; ++i
)
2084 if (wi::bit_and (mask
, wi::lshift (one
, wi::uhwi (i
, prec
))) == 0)
2086 tree lb
= fold_build2 (LSHIFT_EXPR
, type
,
2087 build_one_cst (type
),
2088 build_int_cst (type
, i
));
2089 tree ub_left
= fold_build1 (BIT_NOT_EXPR
, type
,
2090 fold_build2 (LSHIFT_EXPR
, type
,
2091 build_minus_one_cst (type
),
2092 build_int_cst (type
, i
)));
2093 tree ub_right
= fold_build2 (LSHIFT_EXPR
, type
,
2094 build_one_cst (type
),
2095 build_int_cst (type
, i
));
2096 tree ub
= fold_build2 (BIT_IOR_EXPR
, type
, ub_left
, ub_right
);
2097 impossible_ranges
.union_ (int_range
<1> (lb
, ub
));
2099 if (!impossible_ranges
.undefined_p ())
2101 impossible_ranges
.invert ();
2102 r
.intersect (impossible_ranges
);
2107 operator_bitwise_and::fold_range (irange
&r
, tree type
,
2109 const irange
&rh
) const
2111 if (range_operator::fold_range (r
, type
, lh
, rh
))
2113 // FIXME: This is temporarily disabled because, though it
2114 // generates better ranges, it's noticeably slower for evrp.
2115 // remove_impossible_ranges (r, rh);
2122 // Optimize BIT_AND_EXPR and BIT_IOR_EXPR in terms of a mask if
2123 // possible. Basically, see if we can optimize:
2127 // [LB op Z, UB op Z]
2129 // If the optimization was successful, accumulate the range in R and
2133 wi_optimize_and_or (irange
&r
,
2134 enum tree_code code
,
2136 const wide_int
&lh_lb
, const wide_int
&lh_ub
,
2137 const wide_int
&rh_lb
, const wide_int
&rh_ub
)
2139 // Calculate the singleton mask among the ranges, if any.
2140 wide_int lower_bound
, upper_bound
, mask
;
2141 if (wi::eq_p (rh_lb
, rh_ub
))
2144 lower_bound
= lh_lb
;
2145 upper_bound
= lh_ub
;
2147 else if (wi::eq_p (lh_lb
, lh_ub
))
2150 lower_bound
= rh_lb
;
2151 upper_bound
= rh_ub
;
2156 // If Z is a constant which (for op | its bitwise not) has n
2157 // consecutive least significant bits cleared followed by m 1
2158 // consecutive bits set immediately above it and either
2159 // m + n == precision, or (x >> (m + n)) == (y >> (m + n)).
2161 // The least significant n bits of all the values in the range are
2162 // cleared or set, the m bits above it are preserved and any bits
2163 // above these are required to be the same for all values in the
2167 if (code
== BIT_IOR_EXPR
)
2169 if (wi::eq_p (w
, 0))
2170 n
= w
.get_precision ();
2174 w
= ~(w
| wi::mask (n
, false, w
.get_precision ()));
2175 if (wi::eq_p (w
, 0))
2176 m
= w
.get_precision () - n
;
2178 m
= wi::ctz (w
) - n
;
2180 wide_int new_mask
= wi::mask (m
+ n
, true, w
.get_precision ());
2181 if ((new_mask
& lower_bound
) != (new_mask
& upper_bound
))
2184 wide_int res_lb
, res_ub
;
2185 if (code
== BIT_AND_EXPR
)
2187 res_lb
= wi::bit_and (lower_bound
, mask
);
2188 res_ub
= wi::bit_and (upper_bound
, mask
);
2190 else if (code
== BIT_IOR_EXPR
)
2192 res_lb
= wi::bit_or (lower_bound
, mask
);
2193 res_ub
= wi::bit_or (upper_bound
, mask
);
2197 value_range_with_overflow (r
, type
, res_lb
, res_ub
);
2199 // Furthermore, if the mask is non-zero, an IOR cannot contain zero.
2200 if (code
== BIT_IOR_EXPR
&& wi::ne_p (mask
, 0))
2203 tmp
.set_nonzero (type
);
2209 // For range [LB, UB] compute two wide_int bit masks.
2211 // In the MAYBE_NONZERO bit mask, if some bit is unset, it means that
2212 // for all numbers in the range the bit is 0, otherwise it might be 0
2215 // In the MUSTBE_NONZERO bit mask, if some bit is set, it means that
2216 // for all numbers in the range the bit is 1, otherwise it might be 0
2220 wi_set_zero_nonzero_bits (tree type
,
2221 const wide_int
&lb
, const wide_int
&ub
,
2222 wide_int
&maybe_nonzero
,
2223 wide_int
&mustbe_nonzero
)
2225 signop sign
= TYPE_SIGN (type
);
2227 if (wi::eq_p (lb
, ub
))
2228 maybe_nonzero
= mustbe_nonzero
= lb
;
2229 else if (wi::ge_p (lb
, 0, sign
) || wi::lt_p (ub
, 0, sign
))
2231 wide_int xor_mask
= lb
^ ub
;
2232 maybe_nonzero
= lb
| ub
;
2233 mustbe_nonzero
= lb
& ub
;
2236 wide_int mask
= wi::mask (wi::floor_log2 (xor_mask
), false,
2237 maybe_nonzero
.get_precision ());
2238 maybe_nonzero
= maybe_nonzero
| mask
;
2239 mustbe_nonzero
= wi::bit_and_not (mustbe_nonzero
, mask
);
2244 maybe_nonzero
= wi::minus_one (lb
.get_precision ());
2245 mustbe_nonzero
= wi::zero (lb
.get_precision ());
2250 operator_bitwise_and::wi_fold (irange
&r
, tree type
,
2251 const wide_int
&lh_lb
,
2252 const wide_int
&lh_ub
,
2253 const wide_int
&rh_lb
,
2254 const wide_int
&rh_ub
) const
2256 if (wi_optimize_and_or (r
, BIT_AND_EXPR
, type
, lh_lb
, lh_ub
, rh_lb
, rh_ub
))
2259 wide_int maybe_nonzero_lh
, mustbe_nonzero_lh
;
2260 wide_int maybe_nonzero_rh
, mustbe_nonzero_rh
;
2261 wi_set_zero_nonzero_bits (type
, lh_lb
, lh_ub
,
2262 maybe_nonzero_lh
, mustbe_nonzero_lh
);
2263 wi_set_zero_nonzero_bits (type
, rh_lb
, rh_ub
,
2264 maybe_nonzero_rh
, mustbe_nonzero_rh
);
2266 wide_int new_lb
= mustbe_nonzero_lh
& mustbe_nonzero_rh
;
2267 wide_int new_ub
= maybe_nonzero_lh
& maybe_nonzero_rh
;
2268 signop sign
= TYPE_SIGN (type
);
2269 unsigned prec
= TYPE_PRECISION (type
);
2270 // If both input ranges contain only negative values, we can
2271 // truncate the result range maximum to the minimum of the
2272 // input range maxima.
2273 if (wi::lt_p (lh_ub
, 0, sign
) && wi::lt_p (rh_ub
, 0, sign
))
2275 new_ub
= wi::min (new_ub
, lh_ub
, sign
);
2276 new_ub
= wi::min (new_ub
, rh_ub
, sign
);
2278 // If either input range contains only non-negative values
2279 // we can truncate the result range maximum to the respective
2280 // maximum of the input range.
2281 if (wi::ge_p (lh_lb
, 0, sign
))
2282 new_ub
= wi::min (new_ub
, lh_ub
, sign
);
2283 if (wi::ge_p (rh_lb
, 0, sign
))
2284 new_ub
= wi::min (new_ub
, rh_ub
, sign
);
2285 // PR68217: In case of signed & sign-bit-CST should
2286 // result in [-INF, 0] instead of [-INF, INF].
2287 if (wi::gt_p (new_lb
, new_ub
, sign
))
2289 wide_int sign_bit
= wi::set_bit_in_zero (prec
- 1, prec
);
2291 && ((wi::eq_p (lh_lb
, lh_ub
)
2292 && !wi::cmps (lh_lb
, sign_bit
))
2293 || (wi::eq_p (rh_lb
, rh_ub
)
2294 && !wi::cmps (rh_lb
, sign_bit
))))
2296 new_lb
= wi::min_value (prec
, sign
);
2297 new_ub
= wi::zero (prec
);
2300 // If the limits got swapped around, return varying.
2301 if (wi::gt_p (new_lb
, new_ub
,sign
))
2302 r
.set_varying (type
);
2304 value_range_with_overflow (r
, type
, new_lb
, new_ub
);
2308 set_nonzero_range_from_mask (irange
&r
, tree type
, const irange
&lhs
)
2310 if (!lhs
.contains_p (build_zero_cst (type
)))
2311 r
= range_nonzero (type
);
2313 r
.set_varying (type
);
2316 // This was shamelessly stolen from register_edge_assert_for_2 and
2317 // adjusted to work with iranges.
2320 operator_bitwise_and::simple_op1_range_solver (irange
&r
, tree type
,
2322 const irange
&op2
) const
2324 if (!op2
.singleton_p ())
2326 set_nonzero_range_from_mask (r
, type
, lhs
);
2329 unsigned int nprec
= TYPE_PRECISION (type
);
2330 wide_int cst2v
= op2
.lower_bound ();
2331 bool cst2n
= wi::neg_p (cst2v
, TYPE_SIGN (type
));
2334 sgnbit
= wi::set_bit_in_zero (nprec
- 1, nprec
);
2336 sgnbit
= wi::zero (nprec
);
2338 // Solve [lhs.lower_bound (), +INF] = x & MASK.
2340 // Minimum unsigned value for >= if (VAL & CST2) == VAL is VAL and
2341 // maximum unsigned value is ~0. For signed comparison, if CST2
2342 // doesn't have the most significant bit set, handle it similarly. If
2343 // CST2 has MSB set, the minimum is the same, and maximum is ~0U/2.
2344 wide_int valv
= lhs
.lower_bound ();
2345 wide_int minv
= valv
& cst2v
, maxv
;
2346 bool we_know_nothing
= false;
2349 // If (VAL & CST2) != VAL, X & CST2 can't be equal to VAL.
2350 minv
= masked_increment (valv
, cst2v
, sgnbit
, nprec
);
2353 // If we can't determine anything on this bound, fall
2354 // through and conservatively solve for the other end point.
2355 we_know_nothing
= true;
2358 maxv
= wi::mask (nprec
- (cst2n
? 1 : 0), false, nprec
);
2359 if (we_know_nothing
)
2360 r
.set_varying (type
);
2362 r
= int_range
<1> (type
, minv
, maxv
);
2364 // Solve [-INF, lhs.upper_bound ()] = x & MASK.
2366 // Minimum unsigned value for <= is 0 and maximum unsigned value is
2367 // VAL | ~CST2 if (VAL & CST2) == VAL. Otherwise, find smallest
2369 // VAL2 > VAL && (VAL2 & CST2) == VAL2 and use (VAL2 - 1) | ~CST2
2371 // For signed comparison, if CST2 doesn't have most significant bit
2372 // set, handle it similarly. If CST2 has MSB set, the maximum is
2373 // the same and minimum is INT_MIN.
2374 valv
= lhs
.upper_bound ();
2375 minv
= valv
& cst2v
;
2380 maxv
= masked_increment (valv
, cst2v
, sgnbit
, nprec
);
2383 // If we couldn't determine anything on either bound, return
2385 if (we_know_nothing
)
2393 int_range
<1> upper_bits (type
, minv
, maxv
);
2394 r
.intersect (upper_bits
);
2398 operator_bitwise_and::op1_range (irange
&r
, tree type
,
2400 const irange
&op2
) const
2402 if (types_compatible_p (type
, boolean_type_node
))
2403 return op_logical_and
.op1_range (r
, type
, lhs
, op2
);
2406 for (unsigned i
= 0; i
< lhs
.num_pairs (); ++i
)
2408 int_range_max
chunk (lhs
.type (),
2409 lhs
.lower_bound (i
),
2410 lhs
.upper_bound (i
));
2412 simple_op1_range_solver (res
, type
, chunk
, op2
);
2415 if (r
.undefined_p ())
2416 set_nonzero_range_from_mask (r
, type
, lhs
);
2421 operator_bitwise_and::op2_range (irange
&r
, tree type
,
2423 const irange
&op1
) const
2425 return operator_bitwise_and::op1_range (r
, type
, lhs
, op1
);
2429 class operator_logical_or
: public range_operator
2432 virtual bool fold_range (irange
&r
, tree type
,
2434 const irange
&rh
) const;
2435 virtual bool op1_range (irange
&r
, tree type
,
2437 const irange
&op2
) const;
2438 virtual bool op2_range (irange
&r
, tree type
,
2440 const irange
&op1
) const;
2444 operator_logical_or::fold_range (irange
&r
, tree type ATTRIBUTE_UNUSED
,
2446 const irange
&rh
) const
2448 if (empty_range_varying (r
, type
, lh
, rh
))
2457 operator_logical_or::op1_range (irange
&r
, tree type
,
2459 const irange
&op2 ATTRIBUTE_UNUSED
) const
2461 switch (get_bool_state (r
, lhs
, type
))
2464 // A false result means both sides of the OR must be false.
2465 r
= range_false (type
);
2468 // Any other result means only one side has to be true, the
2469 // other side can be anything. so we can't be sure of any result
2471 r
= range_true_and_false (type
);
2478 operator_logical_or::op2_range (irange
&r
, tree type
,
2480 const irange
&op1
) const
2482 return operator_logical_or::op1_range (r
, type
, lhs
, op1
);
2486 class operator_bitwise_or
: public range_operator
2489 virtual bool op1_range (irange
&r
, tree type
,
2491 const irange
&op2
) const;
2492 virtual bool op2_range (irange
&r
, tree type
,
2494 const irange
&op1
) const;
2495 virtual void wi_fold (irange
&r
, tree type
,
2496 const wide_int
&lh_lb
,
2497 const wide_int
&lh_ub
,
2498 const wide_int
&rh_lb
,
2499 const wide_int
&rh_ub
) const;
2503 operator_bitwise_or::wi_fold (irange
&r
, tree type
,
2504 const wide_int
&lh_lb
,
2505 const wide_int
&lh_ub
,
2506 const wide_int
&rh_lb
,
2507 const wide_int
&rh_ub
) const
2509 if (wi_optimize_and_or (r
, BIT_IOR_EXPR
, type
, lh_lb
, lh_ub
, rh_lb
, rh_ub
))
2512 wide_int maybe_nonzero_lh
, mustbe_nonzero_lh
;
2513 wide_int maybe_nonzero_rh
, mustbe_nonzero_rh
;
2514 wi_set_zero_nonzero_bits (type
, lh_lb
, lh_ub
,
2515 maybe_nonzero_lh
, mustbe_nonzero_lh
);
2516 wi_set_zero_nonzero_bits (type
, rh_lb
, rh_ub
,
2517 maybe_nonzero_rh
, mustbe_nonzero_rh
);
2518 wide_int new_lb
= mustbe_nonzero_lh
| mustbe_nonzero_rh
;
2519 wide_int new_ub
= maybe_nonzero_lh
| maybe_nonzero_rh
;
2520 signop sign
= TYPE_SIGN (type
);
2521 // If the input ranges contain only positive values we can
2522 // truncate the minimum of the result range to the maximum
2523 // of the input range minima.
2524 if (wi::ge_p (lh_lb
, 0, sign
)
2525 && wi::ge_p (rh_lb
, 0, sign
))
2527 new_lb
= wi::max (new_lb
, lh_lb
, sign
);
2528 new_lb
= wi::max (new_lb
, rh_lb
, sign
);
2530 // If either input range contains only negative values
2531 // we can truncate the minimum of the result range to the
2532 // respective minimum range.
2533 if (wi::lt_p (lh_ub
, 0, sign
))
2534 new_lb
= wi::max (new_lb
, lh_lb
, sign
);
2535 if (wi::lt_p (rh_ub
, 0, sign
))
2536 new_lb
= wi::max (new_lb
, rh_lb
, sign
);
2537 // If the limits got swapped around, return varying.
2538 if (wi::gt_p (new_lb
, new_ub
,sign
))
2539 r
.set_varying (type
);
2541 value_range_with_overflow (r
, type
, new_lb
, new_ub
);
2545 operator_bitwise_or::op1_range (irange
&r
, tree type
,
2547 const irange
&op2
) const
2549 // If this is really a logical wi_fold, call that.
2550 if (types_compatible_p (type
, boolean_type_node
))
2551 return op_logical_or
.op1_range (r
, type
, lhs
, op2
);
2555 tree zero
= build_zero_cst (type
);
2556 r
= int_range
<1> (zero
, zero
);
2559 r
.set_varying (type
);
2564 operator_bitwise_or::op2_range (irange
&r
, tree type
,
2566 const irange
&op1
) const
2568 return operator_bitwise_or::op1_range (r
, type
, lhs
, op1
);
2572 class operator_bitwise_xor
: public range_operator
2575 virtual void wi_fold (irange
&r
, tree type
,
2576 const wide_int
&lh_lb
,
2577 const wide_int
&lh_ub
,
2578 const wide_int
&rh_lb
,
2579 const wide_int
&rh_ub
) const;
2580 virtual bool op1_range (irange
&r
, tree type
,
2582 const irange
&op2
) const;
2583 virtual bool op2_range (irange
&r
, tree type
,
2585 const irange
&op1
) const;
2589 operator_bitwise_xor::wi_fold (irange
&r
, tree type
,
2590 const wide_int
&lh_lb
,
2591 const wide_int
&lh_ub
,
2592 const wide_int
&rh_lb
,
2593 const wide_int
&rh_ub
) const
2595 signop sign
= TYPE_SIGN (type
);
2596 wide_int maybe_nonzero_lh
, mustbe_nonzero_lh
;
2597 wide_int maybe_nonzero_rh
, mustbe_nonzero_rh
;
2598 wi_set_zero_nonzero_bits (type
, lh_lb
, lh_ub
,
2599 maybe_nonzero_lh
, mustbe_nonzero_lh
);
2600 wi_set_zero_nonzero_bits (type
, rh_lb
, rh_ub
,
2601 maybe_nonzero_rh
, mustbe_nonzero_rh
);
2603 wide_int result_zero_bits
= ((mustbe_nonzero_lh
& mustbe_nonzero_rh
)
2604 | ~(maybe_nonzero_lh
| maybe_nonzero_rh
));
2605 wide_int result_one_bits
2606 = (wi::bit_and_not (mustbe_nonzero_lh
, maybe_nonzero_rh
)
2607 | wi::bit_and_not (mustbe_nonzero_rh
, maybe_nonzero_lh
));
2608 wide_int new_ub
= ~result_zero_bits
;
2609 wide_int new_lb
= result_one_bits
;
2611 // If the range has all positive or all negative values, the result
2612 // is better than VARYING.
2613 if (wi::lt_p (new_lb
, 0, sign
) || wi::ge_p (new_ub
, 0, sign
))
2614 value_range_with_overflow (r
, type
, new_lb
, new_ub
);
2616 r
.set_varying (type
);
2620 operator_bitwise_xor::op1_range (irange
&r
, tree type
,
2622 const irange
&op2
) const
2624 if (lhs
.undefined_p () || lhs
.varying_p ())
2629 if (types_compatible_p (type
, boolean_type_node
))
2631 switch (get_bool_state (r
, lhs
, type
))
2634 if (op2
.varying_p ())
2635 r
.set_varying (type
);
2636 else if (op2
.zero_p ())
2637 r
= range_true (type
);
2639 r
= range_false (type
);
2649 r
.set_varying (type
);
2654 operator_bitwise_xor::op2_range (irange
&r
, tree type
,
2656 const irange
&op1
) const
2658 return operator_bitwise_xor::op1_range (r
, type
, lhs
, op1
);
2661 class operator_trunc_mod
: public range_operator
2664 virtual void wi_fold (irange
&r
, tree type
,
2665 const wide_int
&lh_lb
,
2666 const wide_int
&lh_ub
,
2667 const wide_int
&rh_lb
,
2668 const wide_int
&rh_ub
) const;
2669 virtual bool op1_range (irange
&r
, tree type
,
2671 const irange
&op2
) const;
2672 virtual bool op2_range (irange
&r
, tree type
,
2674 const irange
&op1
) const;
2678 operator_trunc_mod::wi_fold (irange
&r
, tree type
,
2679 const wide_int
&lh_lb
,
2680 const wide_int
&lh_ub
,
2681 const wide_int
&rh_lb
,
2682 const wide_int
&rh_ub
) const
2684 wide_int new_lb
, new_ub
, tmp
;
2685 signop sign
= TYPE_SIGN (type
);
2686 unsigned prec
= TYPE_PRECISION (type
);
2688 // Mod 0 is undefined.
2689 if (wi_zero_p (type
, rh_lb
, rh_ub
))
2695 // ABS (A % B) < ABS (B) and either 0 <= A % B <= A or A <= A % B <= 0.
2700 new_ub
= wi::smax (new_ub
, tmp
);
2703 if (sign
== UNSIGNED
)
2704 new_lb
= wi::zero (prec
);
2709 if (wi::gts_p (tmp
, 0))
2710 tmp
= wi::zero (prec
);
2711 new_lb
= wi::smax (new_lb
, tmp
);
2714 if (sign
== SIGNED
&& wi::neg_p (tmp
))
2715 tmp
= wi::zero (prec
);
2716 new_ub
= wi::min (new_ub
, tmp
, sign
);
2718 value_range_with_overflow (r
, type
, new_lb
, new_ub
);
2722 operator_trunc_mod::op1_range (irange
&r
, tree type
,
2724 const irange
&) const
2727 signop sign
= TYPE_SIGN (type
);
2728 unsigned prec
= TYPE_PRECISION (type
);
2729 // (a % b) >= x && x > 0 , then a >= x.
2730 if (wi::gt_p (lhs
.lower_bound (), 0, sign
))
2732 r
= value_range (type
, lhs
.lower_bound (), wi::max_value (prec
, sign
));
2735 // (a % b) <= x && x < 0 , then a <= x.
2736 if (wi::lt_p (lhs
.upper_bound (), 0, sign
))
2738 r
= value_range (type
, wi::min_value (prec
, sign
), lhs
.upper_bound ());
2745 operator_trunc_mod::op2_range (irange
&r
, tree type
,
2747 const irange
&) const
2750 signop sign
= TYPE_SIGN (type
);
2751 unsigned prec
= TYPE_PRECISION (type
);
2752 // (a % b) >= x && x > 0 , then b is in ~[-x, x] for signed
2753 // or b > x for unsigned.
2754 if (wi::gt_p (lhs
.lower_bound (), 0, sign
))
2757 r
= value_range (type
, wi::neg (lhs
.lower_bound ()),
2758 lhs
.lower_bound (), VR_ANTI_RANGE
);
2759 else if (wi::lt_p (lhs
.lower_bound (), wi::max_value (prec
, sign
),
2761 r
= value_range (type
, lhs
.lower_bound () + 1,
2762 wi::max_value (prec
, sign
));
2767 // (a % b) <= x && x < 0 , then b is in ~[x, -x].
2768 if (wi::lt_p (lhs
.upper_bound (), 0, sign
))
2770 if (wi::gt_p (lhs
.upper_bound (), wi::min_value (prec
, sign
), sign
))
2771 r
= value_range (type
, lhs
.upper_bound (),
2772 wi::neg (lhs
.upper_bound ()), VR_ANTI_RANGE
);
2781 class operator_logical_not
: public range_operator
2784 virtual bool fold_range (irange
&r
, tree type
,
2786 const irange
&rh
) const;
2787 virtual bool op1_range (irange
&r
, tree type
,
2789 const irange
&op2
) const;
2792 // Folding a logical NOT, oddly enough, involves doing nothing on the
2793 // forward pass through. During the initial walk backwards, the
2794 // logical NOT reversed the desired outcome on the way back, so on the
2795 // way forward all we do is pass the range forward.
2800 // to determine the TRUE branch, walking backward
2801 // if (b_3) if ([1,1])
2802 // b_3 = !b_2 [1,1] = ![0,0]
2803 // b_2 = x_1 < 20 [0,0] = x_1 < 20, false, so x_1 == [20, 255]
2804 // which is the result we are looking for.. so.. pass it through.
2807 operator_logical_not::fold_range (irange
&r
, tree type
,
2809 const irange
&rh ATTRIBUTE_UNUSED
) const
2811 if (empty_range_varying (r
, type
, lh
, rh
))
2815 if (!lh
.varying_p () && !lh
.undefined_p ())
2822 operator_logical_not::op1_range (irange
&r
,
2825 const irange
&op2
) const
2827 // Logical NOT is involutary...do it again.
2828 return fold_range (r
, type
, lhs
, op2
);
2832 class operator_bitwise_not
: public range_operator
2835 virtual bool fold_range (irange
&r
, tree type
,
2837 const irange
&rh
) const;
2838 virtual bool op1_range (irange
&r
, tree type
,
2840 const irange
&op2
) const;
2844 operator_bitwise_not::fold_range (irange
&r
, tree type
,
2846 const irange
&rh
) const
2848 if (empty_range_varying (r
, type
, lh
, rh
))
2851 if (types_compatible_p (type
, boolean_type_node
))
2852 return op_logical_not
.fold_range (r
, type
, lh
, rh
);
2854 // ~X is simply -1 - X.
2855 int_range
<1> minusone (type
, wi::minus_one (TYPE_PRECISION (type
)),
2856 wi::minus_one (TYPE_PRECISION (type
)));
2857 return range_op_handler (MINUS_EXPR
, type
)->fold_range (r
, type
, minusone
,
2862 operator_bitwise_not::op1_range (irange
&r
, tree type
,
2864 const irange
&op2
) const
2866 if (types_compatible_p (type
, boolean_type_node
))
2867 return op_logical_not
.op1_range (r
, type
, lhs
, op2
);
2869 // ~X is -1 - X and since bitwise NOT is involutary...do it again.
2870 return fold_range (r
, type
, lhs
, op2
);
2874 class operator_cst
: public range_operator
2877 virtual bool fold_range (irange
&r
, tree type
,
2879 const irange
&op2
) const;
2883 operator_cst::fold_range (irange
&r
, tree type ATTRIBUTE_UNUSED
,
2885 const irange
&rh ATTRIBUTE_UNUSED
) const
2892 class operator_identity
: public range_operator
2895 virtual bool fold_range (irange
&r
, tree type
,
2897 const irange
&op2
) const;
2898 virtual bool op1_range (irange
&r
, tree type
,
2900 const irange
&op2
) const;
2904 operator_identity::fold_range (irange
&r
, tree type ATTRIBUTE_UNUSED
,
2906 const irange
&rh ATTRIBUTE_UNUSED
) const
2913 operator_identity::op1_range (irange
&r
, tree type ATTRIBUTE_UNUSED
,
2915 const irange
&op2 ATTRIBUTE_UNUSED
) const
2922 class operator_unknown
: public range_operator
2925 virtual bool fold_range (irange
&r
, tree type
,
2927 const irange
&op2
) const;
2931 operator_unknown::fold_range (irange
&r
, tree type
,
2932 const irange
&lh ATTRIBUTE_UNUSED
,
2933 const irange
&rh ATTRIBUTE_UNUSED
) const
2935 r
.set_varying (type
);
2940 class operator_abs
: public range_operator
2943 virtual void wi_fold (irange
&r
, tree type
,
2944 const wide_int
&lh_lb
,
2945 const wide_int
&lh_ub
,
2946 const wide_int
&rh_lb
,
2947 const wide_int
&rh_ub
) const;
2948 virtual bool op1_range (irange
&r
, tree type
,
2950 const irange
&op2
) const;
2954 operator_abs::wi_fold (irange
&r
, tree type
,
2955 const wide_int
&lh_lb
, const wide_int
&lh_ub
,
2956 const wide_int
&rh_lb ATTRIBUTE_UNUSED
,
2957 const wide_int
&rh_ub ATTRIBUTE_UNUSED
) const
2960 signop sign
= TYPE_SIGN (type
);
2961 unsigned prec
= TYPE_PRECISION (type
);
2963 // Pass through LH for the easy cases.
2964 if (sign
== UNSIGNED
|| wi::ge_p (lh_lb
, 0, sign
))
2966 r
= int_range
<1> (type
, lh_lb
, lh_ub
);
2970 // -TYPE_MIN_VALUE = TYPE_MIN_VALUE with flag_wrapv so we can't get
2972 wide_int min_value
= wi::min_value (prec
, sign
);
2973 wide_int max_value
= wi::max_value (prec
, sign
);
2974 if (!TYPE_OVERFLOW_UNDEFINED (type
) && wi::eq_p (lh_lb
, min_value
))
2976 r
.set_varying (type
);
2980 // ABS_EXPR may flip the range around, if the original range
2981 // included negative values.
2982 if (wi::eq_p (lh_lb
, min_value
))
2984 // ABS ([-MIN, -MIN]) isn't representable, but we have traditionally
2985 // returned [-MIN,-MIN] so this preserves that behaviour. PR37078
2986 if (wi::eq_p (lh_ub
, min_value
))
2988 r
= int_range
<1> (type
, min_value
, min_value
);
2994 min
= wi::abs (lh_lb
);
2996 if (wi::eq_p (lh_ub
, min_value
))
2999 max
= wi::abs (lh_ub
);
3001 // If the range contains zero then we know that the minimum value in the
3002 // range will be zero.
3003 if (wi::le_p (lh_lb
, 0, sign
) && wi::ge_p (lh_ub
, 0, sign
))
3005 if (wi::gt_p (min
, max
, sign
))
3007 min
= wi::zero (prec
);
3011 // If the range was reversed, swap MIN and MAX.
3012 if (wi::gt_p (min
, max
, sign
))
3013 std::swap (min
, max
);
3016 // If the new range has its limits swapped around (MIN > MAX), then
3017 // the operation caused one of them to wrap around. The only thing
3018 // we know is that the result is positive.
3019 if (wi::gt_p (min
, max
, sign
))
3021 min
= wi::zero (prec
);
3024 r
= int_range
<1> (type
, min
, max
);
3028 operator_abs::op1_range (irange
&r
, tree type
,
3030 const irange
&op2
) const
3032 if (empty_range_varying (r
, type
, lhs
, op2
))
3034 if (TYPE_UNSIGNED (type
))
3039 // Start with the positives because negatives are an impossible result.
3040 int_range_max positives
= range_positives (type
);
3041 positives
.intersect (lhs
);
3043 // Then add the negative of each pair:
3044 // ABS(op1) = [5,20] would yield op1 => [-20,-5][5,20].
3045 for (unsigned i
= 0; i
< positives
.num_pairs (); ++i
)
3046 r
.union_ (int_range
<1> (type
,
3047 -positives
.upper_bound (i
),
3048 -positives
.lower_bound (i
)));
3053 class operator_absu
: public range_operator
3056 virtual void wi_fold (irange
&r
, tree type
,
3057 const wide_int
&lh_lb
, const wide_int
&lh_ub
,
3058 const wide_int
&rh_lb
, const wide_int
&rh_ub
) const;
3062 operator_absu::wi_fold (irange
&r
, tree type
,
3063 const wide_int
&lh_lb
, const wide_int
&lh_ub
,
3064 const wide_int
&rh_lb ATTRIBUTE_UNUSED
,
3065 const wide_int
&rh_ub ATTRIBUTE_UNUSED
) const
3067 wide_int new_lb
, new_ub
;
3069 // Pass through VR0 the easy cases.
3070 if (wi::ges_p (lh_lb
, 0))
3077 new_lb
= wi::abs (lh_lb
);
3078 new_ub
= wi::abs (lh_ub
);
3080 // If the range contains zero then we know that the minimum
3081 // value in the range will be zero.
3082 if (wi::ges_p (lh_ub
, 0))
3084 if (wi::gtu_p (new_lb
, new_ub
))
3086 new_lb
= wi::zero (TYPE_PRECISION (type
));
3089 std::swap (new_lb
, new_ub
);
3092 gcc_checking_assert (TYPE_UNSIGNED (type
));
3093 r
= int_range
<1> (type
, new_lb
, new_ub
);
3097 class operator_negate
: public range_operator
3100 virtual bool fold_range (irange
&r
, tree type
,
3102 const irange
&op2
) const;
3103 virtual bool op1_range (irange
&r
, tree type
,
3105 const irange
&op2
) const;
3109 operator_negate::fold_range (irange
&r
, tree type
,
3111 const irange
&rh
) const
3113 if (empty_range_varying (r
, type
, lh
, rh
))
3115 // -X is simply 0 - X.
3116 return range_op_handler (MINUS_EXPR
, type
)->fold_range (r
, type
,
3122 operator_negate::op1_range (irange
&r
, tree type
,
3124 const irange
&op2
) const
3126 // NEGATE is involutory.
3127 return fold_range (r
, type
, lhs
, op2
);
3131 class operator_addr_expr
: public range_operator
3134 virtual bool fold_range (irange
&r
, tree type
,
3136 const irange
&op2
) const;
3137 virtual bool op1_range (irange
&r
, tree type
,
3139 const irange
&op2
) const;
3143 operator_addr_expr::fold_range (irange
&r
, tree type
,
3145 const irange
&rh
) const
3147 if (empty_range_varying (r
, type
, lh
, rh
))
3150 // Return a non-null pointer of the LHS type (passed in op2).
3152 r
= range_zero (type
);
3153 else if (!lh
.contains_p (build_zero_cst (lh
.type ())))
3154 r
= range_nonzero (type
);
3156 r
.set_varying (type
);
3161 operator_addr_expr::op1_range (irange
&r
, tree type
,
3163 const irange
&op2
) const
3165 return operator_addr_expr::fold_range (r
, type
, lhs
, op2
);
3169 class pointer_plus_operator
: public range_operator
3172 virtual void wi_fold (irange
&r
, tree type
,
3173 const wide_int
&lh_lb
,
3174 const wide_int
&lh_ub
,
3175 const wide_int
&rh_lb
,
3176 const wide_int
&rh_ub
) const;
3180 pointer_plus_operator::wi_fold (irange
&r
, tree type
,
3181 const wide_int
&lh_lb
,
3182 const wide_int
&lh_ub
,
3183 const wide_int
&rh_lb
,
3184 const wide_int
&rh_ub
) const
3186 // Check for [0,0] + const, and simply return the const.
3187 if (lh_lb
== 0 && lh_ub
== 0 && rh_lb
== rh_ub
)
3189 tree val
= wide_int_to_tree (type
, rh_lb
);
3194 // For pointer types, we are really only interested in asserting
3195 // whether the expression evaluates to non-NULL.
3197 // With -fno-delete-null-pointer-checks we need to be more
3198 // conservative. As some object might reside at address 0,
3199 // then some offset could be added to it and the same offset
3200 // subtracted again and the result would be NULL.
3202 // static int a[12]; where &a[0] is NULL and
3205 // ptr will be NULL here, even when there is POINTER_PLUS_EXPR
3206 // where the first range doesn't include zero and the second one
3207 // doesn't either. As the second operand is sizetype (unsigned),
3208 // consider all ranges where the MSB could be set as possible
3209 // subtractions where the result might be NULL.
3210 if ((!wi_includes_zero_p (type
, lh_lb
, lh_ub
)
3211 || !wi_includes_zero_p (type
, rh_lb
, rh_ub
))
3212 && !TYPE_OVERFLOW_WRAPS (type
)
3213 && (flag_delete_null_pointer_checks
3214 || !wi::sign_mask (rh_ub
)))
3215 r
= range_nonzero (type
);
3216 else if (lh_lb
== lh_ub
&& lh_lb
== 0
3217 && rh_lb
== rh_ub
&& rh_lb
== 0)
3218 r
= range_zero (type
);
3220 r
.set_varying (type
);
3224 class pointer_min_max_operator
: public range_operator
3227 virtual void wi_fold (irange
& r
, tree type
,
3228 const wide_int
&lh_lb
, const wide_int
&lh_ub
,
3229 const wide_int
&rh_lb
, const wide_int
&rh_ub
) const;
3233 pointer_min_max_operator::wi_fold (irange
&r
, tree type
,
3234 const wide_int
&lh_lb
,
3235 const wide_int
&lh_ub
,
3236 const wide_int
&rh_lb
,
3237 const wide_int
&rh_ub
) const
3239 // For MIN/MAX expressions with pointers, we only care about
3240 // nullness. If both are non null, then the result is nonnull.
3241 // If both are null, then the result is null. Otherwise they
3243 if (!wi_includes_zero_p (type
, lh_lb
, lh_ub
)
3244 && !wi_includes_zero_p (type
, rh_lb
, rh_ub
))
3245 r
= range_nonzero (type
);
3246 else if (wi_zero_p (type
, lh_lb
, lh_ub
) && wi_zero_p (type
, rh_lb
, rh_ub
))
3247 r
= range_zero (type
);
3249 r
.set_varying (type
);
3253 class pointer_and_operator
: public range_operator
3256 virtual void wi_fold (irange
&r
, tree type
,
3257 const wide_int
&lh_lb
, const wide_int
&lh_ub
,
3258 const wide_int
&rh_lb
, const wide_int
&rh_ub
) const;
3262 pointer_and_operator::wi_fold (irange
&r
, tree type
,
3263 const wide_int
&lh_lb
,
3264 const wide_int
&lh_ub
,
3265 const wide_int
&rh_lb ATTRIBUTE_UNUSED
,
3266 const wide_int
&rh_ub ATTRIBUTE_UNUSED
) const
3268 // For pointer types, we are really only interested in asserting
3269 // whether the expression evaluates to non-NULL.
3270 if (wi_zero_p (type
, lh_lb
, lh_ub
) || wi_zero_p (type
, lh_lb
, lh_ub
))
3271 r
= range_zero (type
);
3273 r
.set_varying (type
);
3277 class pointer_or_operator
: public range_operator
3280 virtual bool op1_range (irange
&r
, tree type
,
3282 const irange
&op2
) const;
3283 virtual bool op2_range (irange
&r
, tree type
,
3285 const irange
&op1
) const;
3286 virtual void wi_fold (irange
&r
, tree type
,
3287 const wide_int
&lh_lb
, const wide_int
&lh_ub
,
3288 const wide_int
&rh_lb
, const wide_int
&rh_ub
) const;
3292 pointer_or_operator::op1_range (irange
&r
, tree type
,
3294 const irange
&op2 ATTRIBUTE_UNUSED
) const
3298 tree zero
= build_zero_cst (type
);
3299 r
= int_range
<1> (zero
, zero
);
3302 r
.set_varying (type
);
3307 pointer_or_operator::op2_range (irange
&r
, tree type
,
3309 const irange
&op1
) const
3311 return pointer_or_operator::op1_range (r
, type
, lhs
, op1
);
3315 pointer_or_operator::wi_fold (irange
&r
, tree type
,
3316 const wide_int
&lh_lb
,
3317 const wide_int
&lh_ub
,
3318 const wide_int
&rh_lb
,
3319 const wide_int
&rh_ub
) const
3321 // For pointer types, we are really only interested in asserting
3322 // whether the expression evaluates to non-NULL.
3323 if (!wi_includes_zero_p (type
, lh_lb
, lh_ub
)
3324 && !wi_includes_zero_p (type
, rh_lb
, rh_ub
))
3325 r
= range_nonzero (type
);
3326 else if (wi_zero_p (type
, lh_lb
, lh_ub
) && wi_zero_p (type
, rh_lb
, rh_ub
))
3327 r
= range_zero (type
);
3329 r
.set_varying (type
);
3332 // This implements the range operator tables as local objects in this file.
3334 class range_op_table
3337 inline range_operator
*operator[] (enum tree_code code
);
3339 void set (enum tree_code code
, range_operator
&op
);
3341 range_operator
*m_range_tree
[MAX_TREE_CODES
];
3344 // Return a pointer to the range_operator instance, if there is one
3345 // associated with tree_code CODE.
3348 range_op_table::operator[] (enum tree_code code
)
3350 gcc_checking_assert (code
> 0 && code
< MAX_TREE_CODES
);
3351 return m_range_tree
[code
];
3354 // Add OP to the handler table for CODE.
3357 range_op_table::set (enum tree_code code
, range_operator
&op
)
3359 gcc_checking_assert (m_range_tree
[code
] == NULL
);
3360 m_range_tree
[code
] = &op
;
3363 // Instantiate a range op table for integral operations.
3365 class integral_table
: public range_op_table
3369 } integral_tree_table
;
3371 integral_table::integral_table ()
3373 set (EQ_EXPR
, op_equal
);
3374 set (NE_EXPR
, op_not_equal
);
3375 set (LT_EXPR
, op_lt
);
3376 set (LE_EXPR
, op_le
);
3377 set (GT_EXPR
, op_gt
);
3378 set (GE_EXPR
, op_ge
);
3379 set (PLUS_EXPR
, op_plus
);
3380 set (MINUS_EXPR
, op_minus
);
3381 set (MIN_EXPR
, op_min
);
3382 set (MAX_EXPR
, op_max
);
3383 set (MULT_EXPR
, op_mult
);
3384 set (TRUNC_DIV_EXPR
, op_trunc_div
);
3385 set (FLOOR_DIV_EXPR
, op_floor_div
);
3386 set (ROUND_DIV_EXPR
, op_round_div
);
3387 set (CEIL_DIV_EXPR
, op_ceil_div
);
3388 set (EXACT_DIV_EXPR
, op_exact_div
);
3389 set (LSHIFT_EXPR
, op_lshift
);
3390 set (RSHIFT_EXPR
, op_rshift
);
3391 set (NOP_EXPR
, op_convert
);
3392 set (CONVERT_EXPR
, op_convert
);
3393 set (TRUTH_AND_EXPR
, op_logical_and
);
3394 set (BIT_AND_EXPR
, op_bitwise_and
);
3395 set (TRUTH_OR_EXPR
, op_logical_or
);
3396 set (BIT_IOR_EXPR
, op_bitwise_or
);
3397 set (BIT_XOR_EXPR
, op_bitwise_xor
);
3398 set (TRUNC_MOD_EXPR
, op_trunc_mod
);
3399 set (TRUTH_NOT_EXPR
, op_logical_not
);
3400 set (BIT_NOT_EXPR
, op_bitwise_not
);
3401 set (INTEGER_CST
, op_integer_cst
);
3402 set (SSA_NAME
, op_identity
);
3403 set (PAREN_EXPR
, op_identity
);
3404 set (OBJ_TYPE_REF
, op_identity
);
3405 set (IMAGPART_EXPR
, op_unknown
);
3406 set (POINTER_DIFF_EXPR
, op_unknown
);
3407 set (ABS_EXPR
, op_abs
);
3408 set (ABSU_EXPR
, op_absu
);
3409 set (NEGATE_EXPR
, op_negate
);
3410 set (ADDR_EXPR
, op_addr
);
3413 // Instantiate a range op table for pointer operations.
3415 class pointer_table
: public range_op_table
3419 } pointer_tree_table
;
3421 pointer_table::pointer_table ()
3423 set (BIT_AND_EXPR
, op_pointer_and
);
3424 set (BIT_IOR_EXPR
, op_pointer_or
);
3425 set (MIN_EXPR
, op_ptr_min_max
);
3426 set (MAX_EXPR
, op_ptr_min_max
);
3427 set (POINTER_PLUS_EXPR
, op_pointer_plus
);
3429 set (EQ_EXPR
, op_equal
);
3430 set (NE_EXPR
, op_not_equal
);
3431 set (LT_EXPR
, op_lt
);
3432 set (LE_EXPR
, op_le
);
3433 set (GT_EXPR
, op_gt
);
3434 set (GE_EXPR
, op_ge
);
3435 set (SSA_NAME
, op_identity
);
3436 set (INTEGER_CST
, op_integer_cst
);
3437 set (ADDR_EXPR
, op_addr
);
3438 set (NOP_EXPR
, op_convert
);
3439 set (CONVERT_EXPR
, op_convert
);
3441 set (BIT_NOT_EXPR
, op_bitwise_not
);
3442 set (BIT_XOR_EXPR
, op_bitwise_xor
);
3445 // The tables are hidden and accessed via a simple extern function.
3448 range_op_handler (enum tree_code code
, tree type
)
3450 // First check if there is a pointer specialization.
3451 if (POINTER_TYPE_P (type
))
3452 return pointer_tree_table
[code
];
3453 if (INTEGRAL_TYPE_P (type
))
3454 return integral_tree_table
[code
];
3458 // Cast the range in R to TYPE.
3461 range_cast (irange
&r
, tree type
)
3463 int_range_max tmp
= r
;
3464 range_operator
*op
= range_op_handler (CONVERT_EXPR
, type
);
3465 // Call op_convert, if it fails, the result is varying.
3466 if (!op
->fold_range (r
, type
, tmp
, int_range
<1> (type
)))
3467 r
.set_varying (type
);
3471 #include "selftest.h"
3475 #define INT(N) build_int_cst (integer_type_node, (N))
3476 #define UINT(N) build_int_cstu (unsigned_type_node, (N))
3477 #define INT16(N) build_int_cst (short_integer_type_node, (N))
3478 #define UINT16(N) build_int_cstu (short_unsigned_type_node, (N))
3479 #define SCHAR(N) build_int_cst (signed_char_type_node, (N))
3480 #define UCHAR(N) build_int_cstu (unsigned_char_type_node, (N))
3483 range_op_cast_tests ()
3485 int_range
<1> r0
, r1
, r2
, rold
;
3486 r0
.set_varying (integer_type_node
);
3487 tree maxint
= wide_int_to_tree (integer_type_node
, r0
.upper_bound ());
3489 // If a range is in any way outside of the range for the converted
3490 // to range, default to the range for the new type.
3491 r0
.set_varying (short_integer_type_node
);
3492 tree minshort
= wide_int_to_tree (short_integer_type_node
, r0
.lower_bound ());
3493 tree maxshort
= wide_int_to_tree (short_integer_type_node
, r0
.upper_bound ());
3494 if (TYPE_PRECISION (TREE_TYPE (maxint
))
3495 > TYPE_PRECISION (short_integer_type_node
))
3497 r1
= int_range
<1> (integer_zero_node
, maxint
);
3498 range_cast (r1
, short_integer_type_node
);
3499 ASSERT_TRUE (r1
.lower_bound () == wi::to_wide (minshort
)
3500 && r1
.upper_bound() == wi::to_wide (maxshort
));
3503 // (unsigned char)[-5,-1] => [251,255].
3504 r0
= rold
= int_range
<1> (SCHAR (-5), SCHAR (-1));
3505 range_cast (r0
, unsigned_char_type_node
);
3506 ASSERT_TRUE (r0
== int_range
<1> (UCHAR (251), UCHAR (255)));
3507 range_cast (r0
, signed_char_type_node
);
3508 ASSERT_TRUE (r0
== rold
);
3510 // (signed char)[15, 150] => [-128,-106][15,127].
3511 r0
= rold
= int_range
<1> (UCHAR (15), UCHAR (150));
3512 range_cast (r0
, signed_char_type_node
);
3513 r1
= int_range
<1> (SCHAR (15), SCHAR (127));
3514 r2
= int_range
<1> (SCHAR (-128), SCHAR (-106));
3516 ASSERT_TRUE (r1
== r0
);
3517 range_cast (r0
, unsigned_char_type_node
);
3518 ASSERT_TRUE (r0
== rold
);
3520 // (unsigned char)[-5, 5] => [0,5][251,255].
3521 r0
= rold
= int_range
<1> (SCHAR (-5), SCHAR (5));
3522 range_cast (r0
, unsigned_char_type_node
);
3523 r1
= int_range
<1> (UCHAR (251), UCHAR (255));
3524 r2
= int_range
<1> (UCHAR (0), UCHAR (5));
3526 ASSERT_TRUE (r0
== r1
);
3527 range_cast (r0
, signed_char_type_node
);
3528 ASSERT_TRUE (r0
== rold
);
3530 // (unsigned char)[-5,5] => [0,5][251,255].
3531 r0
= int_range
<1> (INT (-5), INT (5));
3532 range_cast (r0
, unsigned_char_type_node
);
3533 r1
= int_range
<1> (UCHAR (0), UCHAR (5));
3534 r1
.union_ (int_range
<1> (UCHAR (251), UCHAR (255)));
3535 ASSERT_TRUE (r0
== r1
);
3537 // (unsigned char)[5U,1974U] => [0,255].
3538 r0
= int_range
<1> (UINT (5), UINT (1974));
3539 range_cast (r0
, unsigned_char_type_node
);
3540 ASSERT_TRUE (r0
== int_range
<1> (UCHAR (0), UCHAR (255)));
3541 range_cast (r0
, integer_type_node
);
3542 // Going to a wider range should not sign extend.
3543 ASSERT_TRUE (r0
== int_range
<1> (INT (0), INT (255)));
3545 // (unsigned char)[-350,15] => [0,255].
3546 r0
= int_range
<1> (INT (-350), INT (15));
3547 range_cast (r0
, unsigned_char_type_node
);
3548 ASSERT_TRUE (r0
== (int_range
<1>
3549 (TYPE_MIN_VALUE (unsigned_char_type_node
),
3550 TYPE_MAX_VALUE (unsigned_char_type_node
))));
3552 // Casting [-120,20] from signed char to unsigned short.
3553 // => [0, 20][0xff88, 0xffff].
3554 r0
= int_range
<1> (SCHAR (-120), SCHAR (20));
3555 range_cast (r0
, short_unsigned_type_node
);
3556 r1
= int_range
<1> (UINT16 (0), UINT16 (20));
3557 r2
= int_range
<1> (UINT16 (0xff88), UINT16 (0xffff));
3559 ASSERT_TRUE (r0
== r1
);
3560 // A truncating cast back to signed char will work because [-120, 20]
3561 // is representable in signed char.
3562 range_cast (r0
, signed_char_type_node
);
3563 ASSERT_TRUE (r0
== int_range
<1> (SCHAR (-120), SCHAR (20)));
3565 // unsigned char -> signed short
3566 // (signed short)[(unsigned char)25, (unsigned char)250]
3567 // => [(signed short)25, (signed short)250]
3568 r0
= rold
= int_range
<1> (UCHAR (25), UCHAR (250));
3569 range_cast (r0
, short_integer_type_node
);
3570 r1
= int_range
<1> (INT16 (25), INT16 (250));
3571 ASSERT_TRUE (r0
== r1
);
3572 range_cast (r0
, unsigned_char_type_node
);
3573 ASSERT_TRUE (r0
== rold
);
3575 // Test casting a wider signed [-MIN,MAX] to a nar`rower unsigned.
3576 r0
= int_range
<1> (TYPE_MIN_VALUE (long_long_integer_type_node
),
3577 TYPE_MAX_VALUE (long_long_integer_type_node
));
3578 range_cast (r0
, short_unsigned_type_node
);
3579 r1
= int_range
<1> (TYPE_MIN_VALUE (short_unsigned_type_node
),
3580 TYPE_MAX_VALUE (short_unsigned_type_node
));
3581 ASSERT_TRUE (r0
== r1
);
3583 // Casting NONZERO to a narrower type will wrap/overflow so
3584 // it's just the entire range for the narrower type.
3586 // "NOT 0 at signed 32-bits" ==> [-MIN_32,-1][1, +MAX_32]. This is
3587 // is outside of the range of a smaller range, return the full
3589 if (TYPE_PRECISION (integer_type_node
)
3590 > TYPE_PRECISION (short_integer_type_node
))
3592 r0
= range_nonzero (integer_type_node
);
3593 range_cast (r0
, short_integer_type_node
);
3594 r1
= int_range
<1> (TYPE_MIN_VALUE (short_integer_type_node
),
3595 TYPE_MAX_VALUE (short_integer_type_node
));
3596 ASSERT_TRUE (r0
== r1
);
3599 // Casting NONZERO from a narrower signed to a wider signed.
3601 // NONZERO signed 16-bits is [-MIN_16,-1][1, +MAX_16].
3602 // Converting this to 32-bits signed is [-MIN_16,-1][1, +MAX_16].
3603 r0
= range_nonzero (short_integer_type_node
);
3604 range_cast (r0
, integer_type_node
);
3605 r1
= int_range
<1> (INT (-32768), INT (-1));
3606 r2
= int_range
<1> (INT (1), INT (32767));
3608 ASSERT_TRUE (r0
== r1
);
3612 range_op_lshift_tests ()
3614 // Test that 0x808.... & 0x8.... still contains 0x8....
3615 // for a large set of numbers.
3618 tree big_type
= long_long_unsigned_type_node
;
3619 // big_num = 0x808,0000,0000,0000
3620 tree big_num
= fold_build2 (LSHIFT_EXPR
, big_type
,
3621 build_int_cst (big_type
, 0x808),
3622 build_int_cst (big_type
, 48));
3623 op_bitwise_and
.fold_range (res
, big_type
,
3624 int_range
<1> (big_type
),
3625 int_range
<1> (big_num
, big_num
));
3626 // val = 0x8,0000,0000,0000
3627 tree val
= fold_build2 (LSHIFT_EXPR
, big_type
,
3628 build_int_cst (big_type
, 0x8),
3629 build_int_cst (big_type
, 48));
3630 ASSERT_TRUE (res
.contains_p (val
));
3633 if (TYPE_PRECISION (unsigned_type_node
) > 31)
3635 // unsigned VARYING = op1 << 1 should be VARYING.
3636 int_range
<2> lhs (unsigned_type_node
);
3637 int_range
<2> shift (INT (1), INT (1));
3639 op_lshift
.op1_range (op1
, unsigned_type_node
, lhs
, shift
);
3640 ASSERT_TRUE (op1
.varying_p ());
3642 // 0 = op1 << 1 should be [0,0], [0x8000000, 0x8000000].
3643 int_range
<2> zero (UINT (0), UINT (0));
3644 op_lshift
.op1_range (op1
, unsigned_type_node
, zero
, shift
);
3645 ASSERT_TRUE (op1
.num_pairs () == 2);
3646 // Remove the [0,0] range.
3647 op1
.intersect (zero
);
3648 ASSERT_TRUE (op1
.num_pairs () == 1);
3649 // op1 << 1 should be [0x8000,0x8000] << 1,
3650 // which should result in [0,0].
3651 int_range_max result
;
3652 op_lshift
.fold_range (result
, unsigned_type_node
, op1
, shift
);
3653 ASSERT_TRUE (result
== zero
);
3655 // signed VARYING = op1 << 1 should be VARYING.
3656 if (TYPE_PRECISION (integer_type_node
) > 31)
3658 // unsigned VARYING = op1 << 1 hould be VARYING.
3659 int_range
<2> lhs (integer_type_node
);
3660 int_range
<2> shift (INT (1), INT (1));
3662 op_lshift
.op1_range (op1
, integer_type_node
, lhs
, shift
);
3663 ASSERT_TRUE (op1
.varying_p ());
3665 // 0 = op1 << 1 should be [0,0], [0x8000000, 0x8000000].
3666 int_range
<2> zero (INT (0), INT (0));
3667 op_lshift
.op1_range (op1
, integer_type_node
, zero
, shift
);
3668 ASSERT_TRUE (op1
.num_pairs () == 2);
3669 // Remove the [0,0] range.
3670 op1
.intersect (zero
);
3671 ASSERT_TRUE (op1
.num_pairs () == 1);
3672 // op1 << 1 shuould be [0x8000,0x8000] << 1,
3673 // which should result in [0,0].
3674 int_range_max result
;
3675 op_lshift
.fold_range (result
, unsigned_type_node
, op1
, shift
);
3676 ASSERT_TRUE (result
== zero
);
3681 range_op_rshift_tests ()
3683 // unsigned: [3, MAX] = OP1 >> 1
3685 int_range_max
lhs (build_int_cst (unsigned_type_node
, 3),
3686 TYPE_MAX_VALUE (unsigned_type_node
));
3687 int_range_max
one (build_one_cst (unsigned_type_node
),
3688 build_one_cst (unsigned_type_node
));
3690 op_rshift
.op1_range (op1
, unsigned_type_node
, lhs
, one
);
3691 ASSERT_FALSE (op1
.contains_p (UINT (3)));
3694 // signed: [3, MAX] = OP1 >> 1
3696 int_range_max
lhs (INT (3), TYPE_MAX_VALUE (integer_type_node
));
3697 int_range_max
one (INT (1), INT (1));
3699 op_rshift
.op1_range (op1
, integer_type_node
, lhs
, one
);
3700 ASSERT_FALSE (op1
.contains_p (INT (-2)));
3703 // This is impossible, so OP1 should be [].
3704 // signed: [MIN, MIN] = OP1 >> 1
3706 int_range_max
lhs (TYPE_MIN_VALUE (integer_type_node
),
3707 TYPE_MIN_VALUE (integer_type_node
));
3708 int_range_max
one (INT (1), INT (1));
3710 op_rshift
.op1_range (op1
, integer_type_node
, lhs
, one
);
3711 ASSERT_TRUE (op1
.undefined_p ());
3714 // signed: ~[-1] = OP1 >> 31
3715 if (TYPE_PRECISION (integer_type_node
) > 31)
3717 int_range_max
lhs (INT (-1), INT (-1), VR_ANTI_RANGE
);
3718 int_range_max
shift (INT (31), INT (31));
3720 op_rshift
.op1_range (op1
, integer_type_node
, lhs
, shift
);
3721 int_range_max negatives
= range_negatives (integer_type_node
);
3722 negatives
.intersect (op1
);
3723 ASSERT_TRUE (negatives
.undefined_p ());
3728 range_op_bitwise_and_tests ()
3731 tree min
= vrp_val_min (integer_type_node
);
3732 tree max
= vrp_val_max (integer_type_node
);
3733 tree tiny
= fold_build2 (PLUS_EXPR
, integer_type_node
, min
,
3734 build_one_cst (integer_type_node
));
3735 int_range_max
i1 (tiny
, max
);
3736 int_range_max
i2 (build_int_cst (integer_type_node
, 255),
3737 build_int_cst (integer_type_node
, 255));
3739 // [MIN+1, MAX] = OP1 & 255: OP1 is VARYING
3740 op_bitwise_and
.op1_range (res
, integer_type_node
, i1
, i2
);
3741 ASSERT_TRUE (res
== int_range
<1> (integer_type_node
));
3743 // VARYING = OP1 & 255: OP1 is VARYING
3744 i1
= int_range
<1> (integer_type_node
);
3745 op_bitwise_and
.op1_range (res
, integer_type_node
, i1
, i2
);
3746 ASSERT_TRUE (res
== int_range
<1> (integer_type_node
));
3752 range_op_rshift_tests ();
3753 range_op_lshift_tests ();
3754 range_op_bitwise_and_tests ();
3755 range_op_cast_tests ();
3758 } // namespace selftest
3760 #endif // CHECKING_P