1 /* Code for range operators.
2 Copyright (C) 2017-2023 Free Software Foundation, Inc.
3 Contributed by Andrew MacLeod <amacleod@redhat.com>
4 and Aldy Hernandez <aldyh@redhat.com>.
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify
9 it under the terms of the GNU General Public License as published by
10 the Free Software Foundation; either version 3, or (at your option)
13 GCC is distributed in the hope that it will be useful,
14 but WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 GNU General Public License for more details.
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
24 #include "coretypes.h"
26 #include "insn-codes.h"
31 #include "tree-pass.h"
33 #include "optabs-tree.h"
34 #include "gimple-pretty-print.h"
35 #include "diagnostic-core.h"
37 #include "fold-const.h"
38 #include "stor-layout.h"
41 #include "gimple-iterator.h"
42 #include "gimple-fold.h"
44 #include "gimple-walk.h"
47 #include "value-relation.h"
49 #include "tree-ssa-ccp.h"
50 #include "range-op-mixed.h"
52 // Instantiate the operators which apply to multiple types here.
54 operator_equal op_equal
;
55 operator_not_equal op_not_equal
;
60 operator_identity op_ident
;
62 operator_cast op_cast
;
63 operator_plus op_plus
;
65 operator_minus op_minus
;
66 operator_negate op_negate
;
67 operator_mult op_mult
;
68 operator_addr_expr op_addr
;
69 operator_bitwise_not op_bitwise_not
;
70 operator_bitwise_xor op_bitwise_xor
;
71 operator_bitwise_and op_bitwise_and
;
72 operator_bitwise_or op_bitwise_or
;
76 // Instantaite a range operator table.
77 range_op_table operator_table
;
79 // Invoke the initialization routines for each class of range.
81 range_op_table::range_op_table ()
83 initialize_integral_ops ();
84 initialize_pointer_ops ();
85 initialize_float_ops ();
87 set (EQ_EXPR
, op_equal
);
88 set (NE_EXPR
, op_not_equal
);
93 set (SSA_NAME
, op_ident
);
94 set (PAREN_EXPR
, op_ident
);
95 set (OBJ_TYPE_REF
, op_ident
);
96 set (REAL_CST
, op_cst
);
97 set (INTEGER_CST
, op_cst
);
98 set (NOP_EXPR
, op_cast
);
99 set (CONVERT_EXPR
, op_cast
);
100 set (PLUS_EXPR
, op_plus
);
101 set (ABS_EXPR
, op_abs
);
102 set (MINUS_EXPR
, op_minus
);
103 set (NEGATE_EXPR
, op_negate
);
104 set (MULT_EXPR
, op_mult
);
106 // Occur in both integer and pointer tables, but currently share
107 // integral implementation.
108 set (ADDR_EXPR
, op_addr
);
109 set (BIT_NOT_EXPR
, op_bitwise_not
);
110 set (BIT_XOR_EXPR
, op_bitwise_xor
);
112 // These are in both integer and pointer tables, but pointer has a different
114 // If commented out, there is a hybrid version in range-op-ptr.cc which
115 // is used until there is a pointer range class. Then we can simply
116 // uncomment the operator here and use the unified version.
118 // set (BIT_AND_EXPR, op_bitwise_and);
119 // set (BIT_IOR_EXPR, op_bitwise_or);
120 // set (MIN_EXPR, op_min);
121 // set (MAX_EXPR, op_max);
124 // Instantiate a default range operator for opcodes with no entry.
126 range_operator default_operator
;
128 // Create a default range_op_handler.
130 range_op_handler::range_op_handler ()
132 m_operator
= &default_operator
;
135 // Create a range_op_handler for CODE. Use a default operatoer if CODE
136 // does not have an entry.
138 range_op_handler::range_op_handler (unsigned code
)
140 m_operator
= operator_table
[code
];
142 m_operator
= &default_operator
;
145 // Return TRUE if this handler has a non-default operator.
147 range_op_handler::operator bool () const
149 return m_operator
!= &default_operator
;
152 // Return a pointer to the range operator assocaited with this handler.
153 // If it is a default operator, return NULL.
154 // This is the equivalent of indexing the range table.
157 range_op_handler::range_op () const
159 if (m_operator
!= &default_operator
)
164 // Create a dispatch pattern for value range discriminators LHS, OP1, and OP2.
165 // This is used to produce a unique value for each dispatch pattern. Shift
166 // values are based on the size of the m_discriminator field in value_range.h.
169 dispatch_trio (unsigned lhs
, unsigned op1
, unsigned op2
)
171 return ((lhs
<< 8) + (op1
<< 4) + (op2
));
174 // These are the supported dispatch patterns. These map to the parameter list
175 // of the routines in range_operator. Note the last 3 characters are
176 // shorthand for the LHS, OP1, and OP2 range discriminator class.
178 const unsigned RO_III
= dispatch_trio (VR_IRANGE
, VR_IRANGE
, VR_IRANGE
);
179 const unsigned RO_IFI
= dispatch_trio (VR_IRANGE
, VR_FRANGE
, VR_IRANGE
);
180 const unsigned RO_IFF
= dispatch_trio (VR_IRANGE
, VR_FRANGE
, VR_FRANGE
);
181 const unsigned RO_FFF
= dispatch_trio (VR_FRANGE
, VR_FRANGE
, VR_FRANGE
);
182 const unsigned RO_FIF
= dispatch_trio (VR_FRANGE
, VR_IRANGE
, VR_FRANGE
);
183 const unsigned RO_FII
= dispatch_trio (VR_FRANGE
, VR_IRANGE
, VR_IRANGE
);
185 // Return a dispatch value for parameter types LHS, OP1 and OP2.
188 range_op_handler::dispatch_kind (const vrange
&lhs
, const vrange
&op1
,
189 const vrange
& op2
) const
191 return dispatch_trio (lhs
.m_discriminator
, op1
.m_discriminator
,
192 op2
.m_discriminator
);
195 // Dispatch a call to fold_range based on the types of R, LH and RH.
198 range_op_handler::fold_range (vrange
&r
, tree type
,
201 relation_trio rel
) const
203 gcc_checking_assert (m_operator
);
204 switch (dispatch_kind (r
, lh
, rh
))
207 return m_operator
->fold_range (as_a
<irange
> (r
), type
,
209 as_a
<irange
> (rh
), rel
);
211 return m_operator
->fold_range (as_a
<irange
> (r
), type
,
213 as_a
<irange
> (rh
), rel
);
215 return m_operator
->fold_range (as_a
<irange
> (r
), type
,
217 as_a
<frange
> (rh
), rel
);
219 return m_operator
->fold_range (as_a
<frange
> (r
), type
,
221 as_a
<frange
> (rh
), rel
);
223 return m_operator
->fold_range (as_a
<frange
> (r
), type
,
225 as_a
<irange
> (rh
), rel
);
231 // Dispatch a call to op1_range based on the types of R, LHS and OP2.
234 range_op_handler::op1_range (vrange
&r
, tree type
,
237 relation_trio rel
) const
239 gcc_checking_assert (m_operator
);
241 if (lhs
.undefined_p ())
243 switch (dispatch_kind (r
, lhs
, op2
))
246 return m_operator
->op1_range (as_a
<irange
> (r
), type
,
248 as_a
<irange
> (op2
), rel
);
250 return m_operator
->op1_range (as_a
<frange
> (r
), type
,
252 as_a
<frange
> (op2
), rel
);
254 return m_operator
->op1_range (as_a
<frange
> (r
), type
,
256 as_a
<frange
> (op2
), rel
);
262 // Dispatch a call to op2_range based on the types of R, LHS and OP1.
265 range_op_handler::op2_range (vrange
&r
, tree type
,
268 relation_trio rel
) const
270 gcc_checking_assert (m_operator
);
271 if (lhs
.undefined_p ())
274 switch (dispatch_kind (r
, lhs
, op1
))
277 return m_operator
->op2_range (as_a
<irange
> (r
), type
,
279 as_a
<irange
> (op1
), rel
);
281 return m_operator
->op2_range (as_a
<frange
> (r
), type
,
283 as_a
<frange
> (op1
), rel
);
285 return m_operator
->op2_range (as_a
<frange
> (r
), type
,
287 as_a
<frange
> (op1
), rel
);
293 // Dispatch a call to lhs_op1_relation based on the types of LHS, OP1 and OP2.
296 range_op_handler::lhs_op1_relation (const vrange
&lhs
,
299 relation_kind rel
) const
301 gcc_checking_assert (m_operator
);
303 switch (dispatch_kind (lhs
, op1
, op2
))
306 return m_operator
->lhs_op1_relation (as_a
<irange
> (lhs
),
308 as_a
<irange
> (op2
), rel
);
310 return m_operator
->lhs_op1_relation (as_a
<irange
> (lhs
),
312 as_a
<frange
> (op2
), rel
);
314 return m_operator
->lhs_op1_relation (as_a
<frange
> (lhs
),
316 as_a
<frange
> (op2
), rel
);
322 // Dispatch a call to lhs_op2_relation based on the types of LHS, OP1 and OP2.
325 range_op_handler::lhs_op2_relation (const vrange
&lhs
,
328 relation_kind rel
) const
330 gcc_checking_assert (m_operator
);
331 switch (dispatch_kind (lhs
, op1
, op2
))
334 return m_operator
->lhs_op2_relation (as_a
<irange
> (lhs
),
336 as_a
<irange
> (op2
), rel
);
338 return m_operator
->lhs_op2_relation (as_a
<irange
> (lhs
),
340 as_a
<frange
> (op2
), rel
);
342 return m_operator
->lhs_op2_relation (as_a
<frange
> (lhs
),
344 as_a
<frange
> (op2
), rel
);
350 // Dispatch a call to op1_op2_relation based on the type of LHS.
353 range_op_handler::op1_op2_relation (const vrange
&lhs
,
355 const vrange
&op2
) const
357 gcc_checking_assert (m_operator
);
358 switch (dispatch_kind (lhs
, op1
, op2
))
361 return m_operator
->op1_op2_relation (as_a
<irange
> (lhs
),
363 as_a
<irange
> (op2
));
366 return m_operator
->op1_op2_relation (as_a
<irange
> (lhs
),
368 as_a
<frange
> (op2
));
371 return m_operator
->op1_op2_relation (as_a
<frange
> (lhs
),
373 as_a
<frange
> (op2
));
381 range_op_handler::overflow_free_p (const vrange
&lh
,
383 relation_trio rel
) const
385 gcc_checking_assert (m_operator
);
386 switch (dispatch_kind (lh
, lh
, rh
))
389 return m_operator
->overflow_free_p(as_a
<irange
> (lh
),
397 // Update the known bitmasks in R when applying the operation CODE to
401 update_known_bitmask (irange
&r
, tree_code code
,
402 const irange
&lh
, const irange
&rh
)
404 if (r
.undefined_p () || lh
.undefined_p () || rh
.undefined_p ()
408 widest_int widest_value
, widest_mask
;
409 tree type
= r
.type ();
410 signop sign
= TYPE_SIGN (type
);
411 int prec
= TYPE_PRECISION (type
);
412 irange_bitmask lh_bits
= lh
.get_bitmask ();
413 irange_bitmask rh_bits
= rh
.get_bitmask ();
415 switch (get_gimple_rhs_class (code
))
417 case GIMPLE_UNARY_RHS
:
418 bit_value_unop (code
, sign
, prec
, &widest_value
, &widest_mask
,
419 TYPE_SIGN (lh
.type ()),
420 TYPE_PRECISION (lh
.type ()),
421 widest_int::from (lh_bits
.value (), sign
),
422 widest_int::from (lh_bits
.mask (), sign
));
424 case GIMPLE_BINARY_RHS
:
425 bit_value_binop (code
, sign
, prec
, &widest_value
, &widest_mask
,
426 TYPE_SIGN (lh
.type ()),
427 TYPE_PRECISION (lh
.type ()),
428 widest_int::from (lh_bits
.value (), sign
),
429 widest_int::from (lh_bits
.mask (), sign
),
430 TYPE_SIGN (rh
.type ()),
431 TYPE_PRECISION (rh
.type ()),
432 widest_int::from (rh_bits
.value (), sign
),
433 widest_int::from (rh_bits
.mask (), sign
));
439 wide_int mask
= wide_int::from (widest_mask
, prec
, sign
);
440 wide_int value
= wide_int::from (widest_value
, prec
, sign
);
441 // Bitmasks must have the unknown value bits cleared.
443 irange_bitmask
bm (value
, mask
);
444 r
.update_bitmask (bm
);
447 // Return the upper limit for a type.
449 static inline wide_int
450 max_limit (const_tree type
)
452 return irange_val_max (type
);
455 // Return the lower limit for a type.
457 static inline wide_int
458 min_limit (const_tree type
)
460 return irange_val_min (type
);
463 // Return false if shifting by OP is undefined behavior. Otherwise, return
464 // true and the range it is to be shifted by. This allows trimming out of
465 // undefined ranges, leaving only valid ranges if there are any.
468 get_shift_range (irange
&r
, tree type
, const irange
&op
)
470 if (op
.undefined_p ())
473 // Build valid range and intersect it with the shift range.
474 r
= value_range (op
.type (),
475 wi::shwi (0, TYPE_PRECISION (op
.type ())),
476 wi::shwi (TYPE_PRECISION (type
) - 1, TYPE_PRECISION (op
.type ())));
479 // If there are no valid ranges in the shift range, returned false.
480 if (r
.undefined_p ())
485 // Default wide_int fold operation returns [MIN, MAX].
488 range_operator::wi_fold (irange
&r
, tree type
,
489 const wide_int
&lh_lb ATTRIBUTE_UNUSED
,
490 const wide_int
&lh_ub ATTRIBUTE_UNUSED
,
491 const wide_int
&rh_lb ATTRIBUTE_UNUSED
,
492 const wide_int
&rh_ub ATTRIBUTE_UNUSED
) const
494 gcc_checking_assert (r
.supports_type_p (type
));
495 r
.set_varying (type
);
498 // Call wi_fold when both op1 and op2 are equivalent. Further split small
499 // subranges into constants. This can provide better precision.
500 // For x + y, when x == y with a range of [0,4] instead of [0, 8] produce
501 // [0,0][2, 2][4,4][6, 6][8, 8]
502 // LIMIT is the maximum number of elements in range allowed before we
503 // do not process them individually.
506 range_operator::wi_fold_in_parts_equiv (irange
&r
, tree type
,
507 const wide_int
&lh_lb
,
508 const wide_int
&lh_ub
,
509 unsigned limit
) const
512 widest_int lh_range
= wi::sub (widest_int::from (lh_ub
, TYPE_SIGN (type
)),
513 widest_int::from (lh_lb
, TYPE_SIGN (type
)));
514 // if there are 1 to 8 values in the LH range, split them up.
516 if (lh_range
>= 0 && lh_range
< limit
)
518 for (unsigned x
= 0; x
<= lh_range
; x
++)
520 wide_int val
= lh_lb
+ x
;
521 wi_fold (tmp
, type
, val
, val
, val
, val
);
525 // Otherwise just call wi_fold.
527 wi_fold (r
, type
, lh_lb
, lh_ub
, lh_lb
, lh_ub
);
530 // Call wi_fold, except further split small subranges into constants.
531 // This can provide better precision. For something 8 >> [0,1]
532 // Instead of [8, 16], we will produce [8,8][16,16]
535 range_operator::wi_fold_in_parts (irange
&r
, tree type
,
536 const wide_int
&lh_lb
,
537 const wide_int
&lh_ub
,
538 const wide_int
&rh_lb
,
539 const wide_int
&rh_ub
) const
542 widest_int rh_range
= wi::sub (widest_int::from (rh_ub
, TYPE_SIGN (type
)),
543 widest_int::from (rh_lb
, TYPE_SIGN (type
)));
544 widest_int lh_range
= wi::sub (widest_int::from (lh_ub
, TYPE_SIGN (type
)),
545 widest_int::from (lh_lb
, TYPE_SIGN (type
)));
546 // If there are 2, 3, or 4 values in the RH range, do them separately.
547 // Call wi_fold_in_parts to check the RH side.
548 if (rh_range
> 0 && rh_range
< 4)
550 wi_fold_in_parts (r
, type
, lh_lb
, lh_ub
, rh_lb
, rh_lb
);
553 wi_fold_in_parts (tmp
, type
, lh_lb
, lh_ub
, rh_lb
+ 1, rh_lb
+ 1);
557 wi_fold_in_parts (tmp
, type
, lh_lb
, lh_ub
, rh_lb
+ 2, rh_lb
+ 2);
561 wi_fold_in_parts (tmp
, type
, lh_lb
, lh_ub
, rh_ub
, rh_ub
);
564 // Otherwise check for 2, 3, or 4 values in the LH range and split them up.
565 // The RH side has been checked, so no recursion needed.
566 else if (lh_range
> 0 && lh_range
< 4)
568 wi_fold (r
, type
, lh_lb
, lh_lb
, rh_lb
, rh_ub
);
571 wi_fold (tmp
, type
, lh_lb
+ 1, lh_lb
+ 1, rh_lb
, rh_ub
);
575 wi_fold (tmp
, type
, lh_lb
+ 2, lh_lb
+ 2, rh_lb
, rh_ub
);
579 wi_fold (tmp
, type
, lh_ub
, lh_ub
, rh_lb
, rh_ub
);
582 // Otherwise just call wi_fold.
584 wi_fold (r
, type
, lh_lb
, lh_ub
, rh_lb
, rh_ub
);
587 // The default for fold is to break all ranges into sub-ranges and
588 // invoke the wi_fold method on each sub-range pair.
591 range_operator::fold_range (irange
&r
, tree type
,
594 relation_trio trio
) const
596 gcc_checking_assert (r
.supports_type_p (type
));
597 if (empty_range_varying (r
, type
, lh
, rh
))
600 relation_kind rel
= trio
.op1_op2 ();
601 unsigned num_lh
= lh
.num_pairs ();
602 unsigned num_rh
= rh
.num_pairs ();
604 // If op1 and op2 are equivalences, then we don't need a complete cross
605 // product, just pairs of matching elements.
606 if (relation_equiv_p (rel
) && lh
== rh
)
610 for (unsigned x
= 0; x
< num_lh
; ++x
)
612 // If the number of subranges is too high, limit subrange creation.
613 unsigned limit
= (r
.num_pairs () > 32) ? 0 : 8;
614 wide_int lh_lb
= lh
.lower_bound (x
);
615 wide_int lh_ub
= lh
.upper_bound (x
);
616 wi_fold_in_parts_equiv (tmp
, type
, lh_lb
, lh_ub
, limit
);
621 op1_op2_relation_effect (r
, type
, lh
, rh
, rel
);
622 update_bitmask (r
, lh
, rh
);
626 // If both ranges are single pairs, fold directly into the result range.
627 // If the number of subranges grows too high, produce a summary result as the
628 // loop becomes exponential with little benefit. See PR 103821.
629 if ((num_lh
== 1 && num_rh
== 1) || num_lh
* num_rh
> 12)
631 wi_fold_in_parts (r
, type
, lh
.lower_bound (), lh
.upper_bound (),
632 rh
.lower_bound (), rh
.upper_bound ());
633 op1_op2_relation_effect (r
, type
, lh
, rh
, rel
);
634 update_bitmask (r
, lh
, rh
);
640 for (unsigned x
= 0; x
< num_lh
; ++x
)
641 for (unsigned y
= 0; y
< num_rh
; ++y
)
643 wide_int lh_lb
= lh
.lower_bound (x
);
644 wide_int lh_ub
= lh
.upper_bound (x
);
645 wide_int rh_lb
= rh
.lower_bound (y
);
646 wide_int rh_ub
= rh
.upper_bound (y
);
647 wi_fold_in_parts (tmp
, type
, lh_lb
, lh_ub
, rh_lb
, rh_ub
);
651 op1_op2_relation_effect (r
, type
, lh
, rh
, rel
);
652 update_bitmask (r
, lh
, rh
);
656 op1_op2_relation_effect (r
, type
, lh
, rh
, rel
);
657 update_bitmask (r
, lh
, rh
);
661 // The default for op1_range is to return false.
664 range_operator::op1_range (irange
&r ATTRIBUTE_UNUSED
,
665 tree type ATTRIBUTE_UNUSED
,
666 const irange
&lhs ATTRIBUTE_UNUSED
,
667 const irange
&op2 ATTRIBUTE_UNUSED
,
673 // The default for op2_range is to return false.
676 range_operator::op2_range (irange
&r ATTRIBUTE_UNUSED
,
677 tree type ATTRIBUTE_UNUSED
,
678 const irange
&lhs ATTRIBUTE_UNUSED
,
679 const irange
&op1 ATTRIBUTE_UNUSED
,
685 // The default relation routines return VREL_VARYING.
688 range_operator::lhs_op1_relation (const irange
&lhs ATTRIBUTE_UNUSED
,
689 const irange
&op1 ATTRIBUTE_UNUSED
,
690 const irange
&op2 ATTRIBUTE_UNUSED
,
691 relation_kind rel ATTRIBUTE_UNUSED
) const
697 range_operator::lhs_op2_relation (const irange
&lhs ATTRIBUTE_UNUSED
,
698 const irange
&op1 ATTRIBUTE_UNUSED
,
699 const irange
&op2 ATTRIBUTE_UNUSED
,
700 relation_kind rel ATTRIBUTE_UNUSED
) const
706 range_operator::op1_op2_relation (const irange
&lhs ATTRIBUTE_UNUSED
,
707 const irange
&op1 ATTRIBUTE_UNUSED
,
708 const irange
&op2 ATTRIBUTE_UNUSED
) const
713 // Default is no relation affects the LHS.
716 range_operator::op1_op2_relation_effect (irange
&lhs_range ATTRIBUTE_UNUSED
,
717 tree type ATTRIBUTE_UNUSED
,
718 const irange
&op1_range ATTRIBUTE_UNUSED
,
719 const irange
&op2_range ATTRIBUTE_UNUSED
,
720 relation_kind rel ATTRIBUTE_UNUSED
) const
726 range_operator::overflow_free_p (const irange
&, const irange
&,
732 // Apply any known bitmask updates based on this operator.
735 range_operator::update_bitmask (irange
&, const irange
&,
736 const irange
&) const
740 // Create and return a range from a pair of wide-ints that are known
741 // to have overflowed (or underflowed).
744 value_range_from_overflowed_bounds (irange
&r
, tree type
,
745 const wide_int
&wmin
,
746 const wide_int
&wmax
)
748 const signop sgn
= TYPE_SIGN (type
);
749 const unsigned int prec
= TYPE_PRECISION (type
);
751 wide_int tmin
= wide_int::from (wmin
, prec
, sgn
);
752 wide_int tmax
= wide_int::from (wmax
, prec
, sgn
);
757 if (wi::cmp (tmin
, tmax
, sgn
) < 0)
760 if (wi::cmp (tmax
, tem
, sgn
) > 0)
763 // If the anti-range would cover nothing, drop to varying.
764 // Likewise if the anti-range bounds are outside of the types
766 if (covers
|| wi::cmp (tmin
, tmax
, sgn
) > 0)
767 r
.set_varying (type
);
769 r
.set (type
, tmin
, tmax
, VR_ANTI_RANGE
);
772 // Create and return a range from a pair of wide-ints. MIN_OVF and
773 // MAX_OVF describe any overflow that might have occurred while
774 // calculating WMIN and WMAX respectively.
777 value_range_with_overflow (irange
&r
, tree type
,
778 const wide_int
&wmin
, const wide_int
&wmax
,
779 wi::overflow_type min_ovf
= wi::OVF_NONE
,
780 wi::overflow_type max_ovf
= wi::OVF_NONE
)
782 const signop sgn
= TYPE_SIGN (type
);
783 const unsigned int prec
= TYPE_PRECISION (type
);
784 const bool overflow_wraps
= TYPE_OVERFLOW_WRAPS (type
);
786 // For one bit precision if max != min, then the range covers all
788 if (prec
== 1 && wi::ne_p (wmax
, wmin
))
790 r
.set_varying (type
);
796 // If overflow wraps, truncate the values and adjust the range,
797 // kind, and bounds appropriately.
798 if ((min_ovf
!= wi::OVF_NONE
) == (max_ovf
!= wi::OVF_NONE
))
800 wide_int tmin
= wide_int::from (wmin
, prec
, sgn
);
801 wide_int tmax
= wide_int::from (wmax
, prec
, sgn
);
802 // If the limits are swapped, we wrapped around and cover
804 if (wi::gt_p (tmin
, tmax
, sgn
))
805 r
.set_varying (type
);
807 // No overflow or both overflow or underflow. The range
808 // kind stays normal.
809 r
.set (type
, tmin
, tmax
);
813 if ((min_ovf
== wi::OVF_UNDERFLOW
&& max_ovf
== wi::OVF_NONE
)
814 || (max_ovf
== wi::OVF_OVERFLOW
&& min_ovf
== wi::OVF_NONE
))
815 value_range_from_overflowed_bounds (r
, type
, wmin
, wmax
);
817 // Other underflow and/or overflow, drop to VR_VARYING.
818 r
.set_varying (type
);
822 // If both bounds either underflowed or overflowed, then the result
824 if ((min_ovf
== wi::OVF_OVERFLOW
&& max_ovf
== wi::OVF_OVERFLOW
)
825 || (min_ovf
== wi::OVF_UNDERFLOW
&& max_ovf
== wi::OVF_UNDERFLOW
))
831 // If overflow does not wrap, saturate to [MIN, MAX].
832 wide_int new_lb
, new_ub
;
833 if (min_ovf
== wi::OVF_UNDERFLOW
)
834 new_lb
= wi::min_value (prec
, sgn
);
835 else if (min_ovf
== wi::OVF_OVERFLOW
)
836 new_lb
= wi::max_value (prec
, sgn
);
840 if (max_ovf
== wi::OVF_UNDERFLOW
)
841 new_ub
= wi::min_value (prec
, sgn
);
842 else if (max_ovf
== wi::OVF_OVERFLOW
)
843 new_ub
= wi::max_value (prec
, sgn
);
847 r
.set (type
, new_lb
, new_ub
);
851 // Create and return a range from a pair of wide-ints. Canonicalize
852 // the case where the bounds are swapped. In which case, we transform
853 // [10,5] into [MIN,5][10,MAX].
856 create_possibly_reversed_range (irange
&r
, tree type
,
857 const wide_int
&new_lb
, const wide_int
&new_ub
)
859 signop s
= TYPE_SIGN (type
);
860 // If the bounds are swapped, treat the result as if an overflow occurred.
861 if (wi::gt_p (new_lb
, new_ub
, s
))
862 value_range_from_overflowed_bounds (r
, type
, new_lb
, new_ub
);
864 // Otherwise it's just a normal range.
865 r
.set (type
, new_lb
, new_ub
);
868 // Return the summary information about boolean range LHS. If EMPTY/FULL,
869 // return the equivalent range for TYPE in R; if FALSE/TRUE, do nothing.
872 get_bool_state (vrange
&r
, const vrange
&lhs
, tree val_type
)
874 // If there is no result, then this is unexecutable.
875 if (lhs
.undefined_p ())
884 // For TRUE, we can't just test for [1,1] because Ada can have
885 // multi-bit booleans, and TRUE values can be: [1, MAX], ~[0], etc.
886 if (lhs
.contains_p (build_zero_cst (lhs
.type ())))
888 r
.set_varying (val_type
);
895 // ------------------------------------------------------------------------
898 operator_equal::update_bitmask (irange
&r
, const irange
&lh
,
899 const irange
&rh
) const
901 update_known_bitmask (r
, EQ_EXPR
, lh
, rh
);
904 // Check if the LHS range indicates a relation between OP1 and OP2.
907 operator_equal::op1_op2_relation (const irange
&lhs
, const irange
&,
908 const irange
&) const
910 if (lhs
.undefined_p ())
911 return VREL_UNDEFINED
;
913 // FALSE = op1 == op2 indicates NE_EXPR.
917 // TRUE = op1 == op2 indicates EQ_EXPR.
918 if (!contains_zero_p (lhs
))
924 operator_equal::fold_range (irange
&r
, tree type
,
927 relation_trio rel
) const
929 if (relop_early_resolve (r
, type
, op1
, op2
, rel
, VREL_EQ
))
932 // We can be sure the values are always equal or not if both ranges
933 // consist of a single value, and then compare them.
934 bool op1_const
= wi::eq_p (op1
.lower_bound (), op1
.upper_bound ());
935 bool op2_const
= wi::eq_p (op2
.lower_bound (), op2
.upper_bound ());
936 if (op1_const
&& op2_const
)
938 if (wi::eq_p (op1
.lower_bound (), op2
.upper_bound()))
939 r
= range_true (type
);
941 r
= range_false (type
);
945 // If ranges do not intersect, we know the range is not equal,
946 // otherwise we don't know anything for sure.
947 int_range_max tmp
= op1
;
949 if (tmp
.undefined_p ())
950 r
= range_false (type
);
951 // Check if a constant cannot satisfy the bitmask requirements.
952 else if (op2_const
&& !op1
.get_bitmask ().member_p (op2
.lower_bound ()))
953 r
= range_false (type
);
954 else if (op1_const
&& !op2
.get_bitmask ().member_p (op1
.lower_bound ()))
955 r
= range_false (type
);
957 r
= range_true_and_false (type
);
963 operator_equal::op1_range (irange
&r
, tree type
,
968 switch (get_bool_state (r
, lhs
, type
))
971 // If it's true, the result is the same as OP2.
976 // If the result is false, the only time we know anything is
977 // if OP2 is a constant.
978 if (!op2
.undefined_p ()
979 && wi::eq_p (op2
.lower_bound(), op2
.upper_bound()))
985 r
.set_varying (type
);
995 operator_equal::op2_range (irange
&r
, tree type
,
998 relation_trio rel
) const
1000 return operator_equal::op1_range (r
, type
, lhs
, op1
, rel
.swap_op1_op2 ());
1003 // -------------------------------------------------------------------------
1006 operator_not_equal::update_bitmask (irange
&r
, const irange
&lh
,
1007 const irange
&rh
) const
1009 update_known_bitmask (r
, NE_EXPR
, lh
, rh
);
1012 // Check if the LHS range indicates a relation between OP1 and OP2.
1015 operator_not_equal::op1_op2_relation (const irange
&lhs
, const irange
&,
1016 const irange
&) const
1018 if (lhs
.undefined_p ())
1019 return VREL_UNDEFINED
;
1021 // FALSE = op1 != op2 indicates EQ_EXPR.
1025 // TRUE = op1 != op2 indicates NE_EXPR.
1026 if (!contains_zero_p (lhs
))
1028 return VREL_VARYING
;
1032 operator_not_equal::fold_range (irange
&r
, tree type
,
1035 relation_trio rel
) const
1037 if (relop_early_resolve (r
, type
, op1
, op2
, rel
, VREL_NE
))
1040 // We can be sure the values are always equal or not if both ranges
1041 // consist of a single value, and then compare them.
1042 bool op1_const
= wi::eq_p (op1
.lower_bound (), op1
.upper_bound ());
1043 bool op2_const
= wi::eq_p (op2
.lower_bound (), op2
.upper_bound ());
1044 if (op1_const
&& op2_const
)
1046 if (wi::ne_p (op1
.lower_bound (), op2
.upper_bound()))
1047 r
= range_true (type
);
1049 r
= range_false (type
);
1053 // If ranges do not intersect, we know the range is not equal,
1054 // otherwise we don't know anything for sure.
1055 int_range_max tmp
= op1
;
1056 tmp
.intersect (op2
);
1057 if (tmp
.undefined_p ())
1058 r
= range_true (type
);
1059 // Check if a constant cannot satisfy the bitmask requirements.
1060 else if (op2_const
&& !op1
.get_bitmask ().member_p (op2
.lower_bound ()))
1061 r
= range_true (type
);
1062 else if (op1_const
&& !op2
.get_bitmask ().member_p (op1
.lower_bound ()))
1063 r
= range_true (type
);
1065 r
= range_true_and_false (type
);
1071 operator_not_equal::op1_range (irange
&r
, tree type
,
1074 relation_trio
) const
1076 switch (get_bool_state (r
, lhs
, type
))
1079 // If the result is true, the only time we know anything is if
1080 // OP2 is a constant.
1081 if (!op2
.undefined_p ()
1082 && wi::eq_p (op2
.lower_bound(), op2
.upper_bound()))
1088 r
.set_varying (type
);
1092 // If it's false, the result is the same as OP2.
1104 operator_not_equal::op2_range (irange
&r
, tree type
,
1107 relation_trio rel
) const
1109 return operator_not_equal::op1_range (r
, type
, lhs
, op1
, rel
.swap_op1_op2 ());
1112 // (X < VAL) produces the range of [MIN, VAL - 1].
1115 build_lt (irange
&r
, tree type
, const wide_int
&val
)
1117 wi::overflow_type ov
;
1119 signop sgn
= TYPE_SIGN (type
);
1121 // Signed 1 bit cannot represent 1 for subtraction.
1123 lim
= wi::add (val
, -1, sgn
, &ov
);
1125 lim
= wi::sub (val
, 1, sgn
, &ov
);
1127 // If val - 1 underflows, check if X < MIN, which is an empty range.
1131 r
= int_range
<1> (type
, min_limit (type
), lim
);
1134 // (X <= VAL) produces the range of [MIN, VAL].
1137 build_le (irange
&r
, tree type
, const wide_int
&val
)
1139 r
= int_range
<1> (type
, min_limit (type
), val
);
1142 // (X > VAL) produces the range of [VAL + 1, MAX].
1145 build_gt (irange
&r
, tree type
, const wide_int
&val
)
1147 wi::overflow_type ov
;
1149 signop sgn
= TYPE_SIGN (type
);
1151 // Signed 1 bit cannot represent 1 for addition.
1153 lim
= wi::sub (val
, -1, sgn
, &ov
);
1155 lim
= wi::add (val
, 1, sgn
, &ov
);
1156 // If val + 1 overflows, check is for X > MAX, which is an empty range.
1160 r
= int_range
<1> (type
, lim
, max_limit (type
));
1163 // (X >= val) produces the range of [VAL, MAX].
1166 build_ge (irange
&r
, tree type
, const wide_int
&val
)
1168 r
= int_range
<1> (type
, val
, max_limit (type
));
1173 operator_lt::update_bitmask (irange
&r
, const irange
&lh
,
1174 const irange
&rh
) const
1176 update_known_bitmask (r
, LT_EXPR
, lh
, rh
);
1179 // Check if the LHS range indicates a relation between OP1 and OP2.
1182 operator_lt::op1_op2_relation (const irange
&lhs
, const irange
&,
1183 const irange
&) const
1185 if (lhs
.undefined_p ())
1186 return VREL_UNDEFINED
;
1188 // FALSE = op1 < op2 indicates GE_EXPR.
1192 // TRUE = op1 < op2 indicates LT_EXPR.
1193 if (!contains_zero_p (lhs
))
1195 return VREL_VARYING
;
1199 operator_lt::fold_range (irange
&r
, tree type
,
1202 relation_trio rel
) const
1204 if (relop_early_resolve (r
, type
, op1
, op2
, rel
, VREL_LT
))
1207 signop sign
= TYPE_SIGN (op1
.type ());
1208 gcc_checking_assert (sign
== TYPE_SIGN (op2
.type ()));
1210 if (wi::lt_p (op1
.upper_bound (), op2
.lower_bound (), sign
))
1211 r
= range_true (type
);
1212 else if (!wi::lt_p (op1
.lower_bound (), op2
.upper_bound (), sign
))
1213 r
= range_false (type
);
1214 // Use nonzero bits to determine if < 0 is false.
1215 else if (op2
.zero_p () && !wi::neg_p (op1
.get_nonzero_bits (), sign
))
1216 r
= range_false (type
);
1218 r
= range_true_and_false (type
);
1223 operator_lt::op1_range (irange
&r
, tree type
,
1226 relation_trio
) const
1228 if (op2
.undefined_p ())
1231 switch (get_bool_state (r
, lhs
, type
))
1234 build_lt (r
, type
, op2
.upper_bound ());
1238 build_ge (r
, type
, op2
.lower_bound ());
1248 operator_lt::op2_range (irange
&r
, tree type
,
1251 relation_trio
) const
1253 if (op1
.undefined_p ())
1256 switch (get_bool_state (r
, lhs
, type
))
1259 build_gt (r
, type
, op1
.lower_bound ());
1263 build_le (r
, type
, op1
.upper_bound ());
1274 operator_le::update_bitmask (irange
&r
, const irange
&lh
,
1275 const irange
&rh
) const
1277 update_known_bitmask (r
, LE_EXPR
, lh
, rh
);
1280 // Check if the LHS range indicates a relation between OP1 and OP2.
1283 operator_le::op1_op2_relation (const irange
&lhs
, const irange
&,
1284 const irange
&) const
1286 if (lhs
.undefined_p ())
1287 return VREL_UNDEFINED
;
1289 // FALSE = op1 <= op2 indicates GT_EXPR.
1293 // TRUE = op1 <= op2 indicates LE_EXPR.
1294 if (!contains_zero_p (lhs
))
1296 return VREL_VARYING
;
1300 operator_le::fold_range (irange
&r
, tree type
,
1303 relation_trio rel
) const
1305 if (relop_early_resolve (r
, type
, op1
, op2
, rel
, VREL_LE
))
1308 signop sign
= TYPE_SIGN (op1
.type ());
1309 gcc_checking_assert (sign
== TYPE_SIGN (op2
.type ()));
1311 if (wi::le_p (op1
.upper_bound (), op2
.lower_bound (), sign
))
1312 r
= range_true (type
);
1313 else if (!wi::le_p (op1
.lower_bound (), op2
.upper_bound (), sign
))
1314 r
= range_false (type
);
1316 r
= range_true_and_false (type
);
1321 operator_le::op1_range (irange
&r
, tree type
,
1324 relation_trio
) const
1326 if (op2
.undefined_p ())
1329 switch (get_bool_state (r
, lhs
, type
))
1332 build_le (r
, type
, op2
.upper_bound ());
1336 build_gt (r
, type
, op2
.lower_bound ());
1346 operator_le::op2_range (irange
&r
, tree type
,
1349 relation_trio
) const
1351 if (op1
.undefined_p ())
1354 switch (get_bool_state (r
, lhs
, type
))
1357 build_ge (r
, type
, op1
.lower_bound ());
1361 build_lt (r
, type
, op1
.upper_bound ());
1372 operator_gt::update_bitmask (irange
&r
, const irange
&lh
,
1373 const irange
&rh
) const
1375 update_known_bitmask (r
, GT_EXPR
, lh
, rh
);
1378 // Check if the LHS range indicates a relation between OP1 and OP2.
1381 operator_gt::op1_op2_relation (const irange
&lhs
, const irange
&,
1382 const irange
&) const
1384 if (lhs
.undefined_p ())
1385 return VREL_UNDEFINED
;
1387 // FALSE = op1 > op2 indicates LE_EXPR.
1391 // TRUE = op1 > op2 indicates GT_EXPR.
1392 if (!contains_zero_p (lhs
))
1394 return VREL_VARYING
;
1398 operator_gt::fold_range (irange
&r
, tree type
,
1399 const irange
&op1
, const irange
&op2
,
1400 relation_trio rel
) const
1402 if (relop_early_resolve (r
, type
, op1
, op2
, rel
, VREL_GT
))
1405 signop sign
= TYPE_SIGN (op1
.type ());
1406 gcc_checking_assert (sign
== TYPE_SIGN (op2
.type ()));
1408 if (wi::gt_p (op1
.lower_bound (), op2
.upper_bound (), sign
))
1409 r
= range_true (type
);
1410 else if (!wi::gt_p (op1
.upper_bound (), op2
.lower_bound (), sign
))
1411 r
= range_false (type
);
1413 r
= range_true_and_false (type
);
1418 operator_gt::op1_range (irange
&r
, tree type
,
1419 const irange
&lhs
, const irange
&op2
,
1420 relation_trio
) const
1422 if (op2
.undefined_p ())
1425 switch (get_bool_state (r
, lhs
, type
))
1428 build_gt (r
, type
, op2
.lower_bound ());
1432 build_le (r
, type
, op2
.upper_bound ());
1442 operator_gt::op2_range (irange
&r
, tree type
,
1445 relation_trio
) const
1447 if (op1
.undefined_p ())
1450 switch (get_bool_state (r
, lhs
, type
))
1453 build_lt (r
, type
, op1
.upper_bound ());
1457 build_ge (r
, type
, op1
.lower_bound ());
1468 operator_ge::update_bitmask (irange
&r
, const irange
&lh
,
1469 const irange
&rh
) const
1471 update_known_bitmask (r
, GE_EXPR
, lh
, rh
);
1474 // Check if the LHS range indicates a relation between OP1 and OP2.
1477 operator_ge::op1_op2_relation (const irange
&lhs
, const irange
&,
1478 const irange
&) const
1480 if (lhs
.undefined_p ())
1481 return VREL_UNDEFINED
;
1483 // FALSE = op1 >= op2 indicates LT_EXPR.
1487 // TRUE = op1 >= op2 indicates GE_EXPR.
1488 if (!contains_zero_p (lhs
))
1490 return VREL_VARYING
;
1494 operator_ge::fold_range (irange
&r
, tree type
,
1497 relation_trio rel
) const
1499 if (relop_early_resolve (r
, type
, op1
, op2
, rel
, VREL_GE
))
1502 signop sign
= TYPE_SIGN (op1
.type ());
1503 gcc_checking_assert (sign
== TYPE_SIGN (op2
.type ()));
1505 if (wi::ge_p (op1
.lower_bound (), op2
.upper_bound (), sign
))
1506 r
= range_true (type
);
1507 else if (!wi::ge_p (op1
.upper_bound (), op2
.lower_bound (), sign
))
1508 r
= range_false (type
);
1510 r
= range_true_and_false (type
);
1515 operator_ge::op1_range (irange
&r
, tree type
,
1518 relation_trio
) const
1520 if (op2
.undefined_p ())
1523 switch (get_bool_state (r
, lhs
, type
))
1526 build_ge (r
, type
, op2
.lower_bound ());
1530 build_lt (r
, type
, op2
.upper_bound ());
1540 operator_ge::op2_range (irange
&r
, tree type
,
1543 relation_trio
) const
1545 if (op1
.undefined_p ())
1548 switch (get_bool_state (r
, lhs
, type
))
1551 build_le (r
, type
, op1
.upper_bound ());
1555 build_gt (r
, type
, op1
.lower_bound ());
1566 operator_plus::update_bitmask (irange
&r
, const irange
&lh
,
1567 const irange
&rh
) const
1569 update_known_bitmask (r
, PLUS_EXPR
, lh
, rh
);
1572 // Check to see if the range of OP2 indicates anything about the relation
1573 // between LHS and OP1.
1576 operator_plus::lhs_op1_relation (const irange
&lhs
,
1579 relation_kind
) const
1581 if (lhs
.undefined_p () || op1
.undefined_p () || op2
.undefined_p ())
1582 return VREL_VARYING
;
1584 tree type
= lhs
.type ();
1585 unsigned prec
= TYPE_PRECISION (type
);
1586 wi::overflow_type ovf1
, ovf2
;
1587 signop sign
= TYPE_SIGN (type
);
1589 // LHS = OP1 + 0 indicates LHS == OP1.
1593 if (TYPE_OVERFLOW_WRAPS (type
))
1595 wi::add (op1
.lower_bound (), op2
.lower_bound (), sign
, &ovf1
);
1596 wi::add (op1
.upper_bound (), op2
.upper_bound (), sign
, &ovf2
);
1599 ovf1
= ovf2
= wi::OVF_NONE
;
1601 // Never wrapping additions.
1604 // Positive op2 means lhs > op1.
1605 if (wi::gt_p (op2
.lower_bound (), wi::zero (prec
), sign
))
1607 if (wi::ge_p (op2
.lower_bound (), wi::zero (prec
), sign
))
1610 // Negative op2 means lhs < op1.
1611 if (wi::lt_p (op2
.upper_bound (), wi::zero (prec
), sign
))
1613 if (wi::le_p (op2
.upper_bound (), wi::zero (prec
), sign
))
1616 // Always wrapping additions.
1617 else if (ovf1
&& ovf1
== ovf2
)
1619 // Positive op2 means lhs < op1.
1620 if (wi::gt_p (op2
.lower_bound (), wi::zero (prec
), sign
))
1622 if (wi::ge_p (op2
.lower_bound (), wi::zero (prec
), sign
))
1625 // Negative op2 means lhs > op1.
1626 if (wi::lt_p (op2
.upper_bound (), wi::zero (prec
), sign
))
1628 if (wi::le_p (op2
.upper_bound (), wi::zero (prec
), sign
))
1632 // If op2 does not contain 0, then LHS and OP1 can never be equal.
1633 if (!range_includes_zero_p (&op2
))
1636 return VREL_VARYING
;
1639 // PLUS is symmetrical, so we can simply call lhs_op1_relation with reversed
1643 operator_plus::lhs_op2_relation (const irange
&lhs
, const irange
&op1
,
1644 const irange
&op2
, relation_kind rel
) const
1646 return lhs_op1_relation (lhs
, op2
, op1
, rel
);
1650 operator_plus::wi_fold (irange
&r
, tree type
,
1651 const wide_int
&lh_lb
, const wide_int
&lh_ub
,
1652 const wide_int
&rh_lb
, const wide_int
&rh_ub
) const
1654 wi::overflow_type ov_lb
, ov_ub
;
1655 signop s
= TYPE_SIGN (type
);
1656 wide_int new_lb
= wi::add (lh_lb
, rh_lb
, s
, &ov_lb
);
1657 wide_int new_ub
= wi::add (lh_ub
, rh_ub
, s
, &ov_ub
);
1658 value_range_with_overflow (r
, type
, new_lb
, new_ub
, ov_lb
, ov_ub
);
1661 // Given addition or subtraction, determine the possible NORMAL ranges and
1662 // OVERFLOW ranges given an OFFSET range. ADD_P is true for addition.
1663 // Return the relation that exists between the LHS and OP1 in order for the
1664 // NORMAL range to apply.
1665 // a return value of VREL_VARYING means no ranges were applicable.
1667 static relation_kind
1668 plus_minus_ranges (irange
&r_ov
, irange
&r_normal
, const irange
&offset
,
1671 relation_kind kind
= VREL_VARYING
;
1672 // For now, only deal with constant adds. This could be extended to ranges
1673 // when someone is so motivated.
1674 if (!offset
.singleton_p () || offset
.zero_p ())
1677 // Always work with a positive offset. ie a+ -2 -> a-2 and a- -2 > a+2
1678 wide_int off
= offset
.lower_bound ();
1679 if (wi::neg_p (off
, SIGNED
))
1682 off
= wi::neg (off
);
1685 wi::overflow_type ov
;
1686 tree type
= offset
.type ();
1687 unsigned prec
= TYPE_PRECISION (type
);
1690 // calculate the normal range and relation for the operation.
1694 lb
= wi::zero (prec
);
1695 ub
= wi::sub (irange_val_max (type
), off
, UNSIGNED
, &ov
);
1702 ub
= irange_val_max (type
);
1705 int_range
<2> normal_range (type
, lb
, ub
);
1706 int_range
<2> ov_range (type
, lb
, ub
, VR_ANTI_RANGE
);
1709 r_normal
= normal_range
;
1713 // Once op1 has been calculated by operator_plus or operator_minus, check
1714 // to see if the relation passed causes any part of the calculation to
1715 // be not possible. ie
1716 // a_2 = b_3 + 1 with a_2 < b_3 can refine the range of b_3 to [INF, INF]
1717 // and that further refines a_2 to [0, 0].
1718 // R is the value of op1, OP2 is the offset being added/subtracted, REL is the
1719 // relation between LHS relation OP1 and ADD_P is true for PLUS, false for
1720 // MINUS. IF any adjustment can be made, R will reflect it.
1723 adjust_op1_for_overflow (irange
&r
, const irange
&op2
, relation_kind rel
,
1726 if (r
.undefined_p ())
1728 tree type
= r
.type ();
1729 // Check for unsigned overflow and calculate the overflow part.
1730 signop s
= TYPE_SIGN (type
);
1731 if (!TYPE_OVERFLOW_WRAPS (type
) || s
== SIGNED
)
1734 // Only work with <, <=, >, >= relations.
1735 if (!relation_lt_le_gt_ge_p (rel
))
1738 // Get the ranges for this offset.
1739 int_range_max normal
, overflow
;
1740 relation_kind k
= plus_minus_ranges (overflow
, normal
, op2
, add_p
);
1742 // VREL_VARYING means there are no adjustments.
1743 if (k
== VREL_VARYING
)
1746 // If the relations match use the normal range, otherwise use overflow range.
1747 if (relation_intersect (k
, rel
) == k
)
1748 r
.intersect (normal
);
1750 r
.intersect (overflow
);
1755 operator_plus::op1_range (irange
&r
, tree type
,
1758 relation_trio trio
) const
1760 if (lhs
.undefined_p ())
1762 // Start with the default operation.
1763 range_op_handler
minus (MINUS_EXPR
);
1766 bool res
= minus
.fold_range (r
, type
, lhs
, op2
);
1767 relation_kind rel
= trio
.lhs_op1 ();
1768 // Check for a relation refinement.
1770 adjust_op1_for_overflow (r
, op2
, rel
, true /* PLUS_EXPR */);
1775 operator_plus::op2_range (irange
&r
, tree type
,
1778 relation_trio rel
) const
1780 return op1_range (r
, type
, lhs
, op1
, rel
.swap_op1_op2 ());
1783 class operator_widen_plus_signed
: public range_operator
1786 virtual void wi_fold (irange
&r
, tree type
,
1787 const wide_int
&lh_lb
,
1788 const wide_int
&lh_ub
,
1789 const wide_int
&rh_lb
,
1790 const wide_int
&rh_ub
) const;
1791 } op_widen_plus_signed
;
1794 operator_widen_plus_signed::wi_fold (irange
&r
, tree type
,
1795 const wide_int
&lh_lb
,
1796 const wide_int
&lh_ub
,
1797 const wide_int
&rh_lb
,
1798 const wide_int
&rh_ub
) const
1800 wi::overflow_type ov_lb
, ov_ub
;
1801 signop s
= TYPE_SIGN (type
);
1804 = wide_int::from (lh_lb
, wi::get_precision (lh_lb
) * 2, SIGNED
);
1806 = wide_int::from (lh_ub
, wi::get_precision (lh_ub
) * 2, SIGNED
);
1807 wide_int rh_wlb
= wide_int::from (rh_lb
, wi::get_precision (rh_lb
) * 2, s
);
1808 wide_int rh_wub
= wide_int::from (rh_ub
, wi::get_precision (rh_ub
) * 2, s
);
1810 wide_int new_lb
= wi::add (lh_wlb
, rh_wlb
, s
, &ov_lb
);
1811 wide_int new_ub
= wi::add (lh_wub
, rh_wub
, s
, &ov_ub
);
1813 r
= int_range
<2> (type
, new_lb
, new_ub
);
1816 class operator_widen_plus_unsigned
: public range_operator
1819 virtual void wi_fold (irange
&r
, tree type
,
1820 const wide_int
&lh_lb
,
1821 const wide_int
&lh_ub
,
1822 const wide_int
&rh_lb
,
1823 const wide_int
&rh_ub
) const;
1824 } op_widen_plus_unsigned
;
1827 operator_widen_plus_unsigned::wi_fold (irange
&r
, tree type
,
1828 const wide_int
&lh_lb
,
1829 const wide_int
&lh_ub
,
1830 const wide_int
&rh_lb
,
1831 const wide_int
&rh_ub
) const
1833 wi::overflow_type ov_lb
, ov_ub
;
1834 signop s
= TYPE_SIGN (type
);
1837 = wide_int::from (lh_lb
, wi::get_precision (lh_lb
) * 2, UNSIGNED
);
1839 = wide_int::from (lh_ub
, wi::get_precision (lh_ub
) * 2, UNSIGNED
);
1840 wide_int rh_wlb
= wide_int::from (rh_lb
, wi::get_precision (rh_lb
) * 2, s
);
1841 wide_int rh_wub
= wide_int::from (rh_ub
, wi::get_precision (rh_ub
) * 2, s
);
1843 wide_int new_lb
= wi::add (lh_wlb
, rh_wlb
, s
, &ov_lb
);
1844 wide_int new_ub
= wi::add (lh_wub
, rh_wub
, s
, &ov_ub
);
1846 r
= int_range
<2> (type
, new_lb
, new_ub
);
1850 operator_minus::update_bitmask (irange
&r
, const irange
&lh
,
1851 const irange
&rh
) const
1853 update_known_bitmask (r
, MINUS_EXPR
, lh
, rh
);
1857 operator_minus::wi_fold (irange
&r
, tree type
,
1858 const wide_int
&lh_lb
, const wide_int
&lh_ub
,
1859 const wide_int
&rh_lb
, const wide_int
&rh_ub
) const
1861 wi::overflow_type ov_lb
, ov_ub
;
1862 signop s
= TYPE_SIGN (type
);
1863 wide_int new_lb
= wi::sub (lh_lb
, rh_ub
, s
, &ov_lb
);
1864 wide_int new_ub
= wi::sub (lh_ub
, rh_lb
, s
, &ov_ub
);
1865 value_range_with_overflow (r
, type
, new_lb
, new_ub
, ov_lb
, ov_ub
);
1869 // Return the relation between LHS and OP1 based on the relation between
1873 operator_minus::lhs_op1_relation (const irange
&, const irange
&op1
,
1874 const irange
&, relation_kind rel
) const
1876 if (!op1
.undefined_p () && TYPE_SIGN (op1
.type ()) == UNSIGNED
)
1885 return VREL_VARYING
;
1888 // Check to see if the relation REL between OP1 and OP2 has any effect on the
1889 // LHS of the expression. If so, apply it to LHS_RANGE. This is a helper
1890 // function for both MINUS_EXPR and POINTER_DIFF_EXPR.
1893 minus_op1_op2_relation_effect (irange
&lhs_range
, tree type
,
1894 const irange
&op1_range ATTRIBUTE_UNUSED
,
1895 const irange
&op2_range ATTRIBUTE_UNUSED
,
1898 if (rel
== VREL_VARYING
)
1901 int_range
<2> rel_range
;
1902 unsigned prec
= TYPE_PRECISION (type
);
1903 signop sgn
= TYPE_SIGN (type
);
1905 // == and != produce [0,0] and ~[0,0] regardless of wrapping.
1907 rel_range
= int_range
<2> (type
, wi::zero (prec
), wi::zero (prec
));
1908 else if (rel
== VREL_NE
)
1909 rel_range
= int_range
<2> (type
, wi::zero (prec
), wi::zero (prec
),
1911 else if (TYPE_OVERFLOW_WRAPS (type
))
1915 // For wrapping signed values and unsigned, if op1 > op2 or
1916 // op1 < op2, then op1 - op2 can be restricted to ~[0, 0].
1919 rel_range
= int_range
<2> (type
, wi::zero (prec
), wi::zero (prec
),
1930 // op1 > op2, op1 - op2 can be restricted to [1, +INF]
1932 rel_range
= int_range
<2> (type
, wi::one (prec
),
1933 wi::max_value (prec
, sgn
));
1935 // op1 >= op2, op1 - op2 can be restricted to [0, +INF]
1937 rel_range
= int_range
<2> (type
, wi::zero (prec
),
1938 wi::max_value (prec
, sgn
));
1940 // op1 < op2, op1 - op2 can be restricted to [-INF, -1]
1942 rel_range
= int_range
<2> (type
, wi::min_value (prec
, sgn
),
1943 wi::minus_one (prec
));
1945 // op1 <= op2, op1 - op2 can be restricted to [-INF, 0]
1947 rel_range
= int_range
<2> (type
, wi::min_value (prec
, sgn
),
1954 lhs_range
.intersect (rel_range
);
1959 operator_minus::op1_op2_relation_effect (irange
&lhs_range
, tree type
,
1960 const irange
&op1_range
,
1961 const irange
&op2_range
,
1962 relation_kind rel
) const
1964 return minus_op1_op2_relation_effect (lhs_range
, type
, op1_range
, op2_range
,
1969 operator_minus::op1_range (irange
&r
, tree type
,
1972 relation_trio trio
) const
1974 if (lhs
.undefined_p ())
1976 // Start with the default operation.
1977 range_op_handler
minus (PLUS_EXPR
);
1980 bool res
= minus
.fold_range (r
, type
, lhs
, op2
);
1981 relation_kind rel
= trio
.lhs_op1 ();
1983 adjust_op1_for_overflow (r
, op2
, rel
, false /* PLUS_EXPR */);
1989 operator_minus::op2_range (irange
&r
, tree type
,
1992 relation_trio
) const
1994 if (lhs
.undefined_p ())
1996 return fold_range (r
, type
, op1
, lhs
);
2000 operator_min::update_bitmask (irange
&r
, const irange
&lh
,
2001 const irange
&rh
) const
2003 update_known_bitmask (r
, MIN_EXPR
, lh
, rh
);
2007 operator_min::wi_fold (irange
&r
, tree type
,
2008 const wide_int
&lh_lb
, const wide_int
&lh_ub
,
2009 const wide_int
&rh_lb
, const wide_int
&rh_ub
) const
2011 signop s
= TYPE_SIGN (type
);
2012 wide_int new_lb
= wi::min (lh_lb
, rh_lb
, s
);
2013 wide_int new_ub
= wi::min (lh_ub
, rh_ub
, s
);
2014 value_range_with_overflow (r
, type
, new_lb
, new_ub
);
2019 operator_max::update_bitmask (irange
&r
, const irange
&lh
,
2020 const irange
&rh
) const
2022 update_known_bitmask (r
, MAX_EXPR
, lh
, rh
);
2026 operator_max::wi_fold (irange
&r
, tree type
,
2027 const wide_int
&lh_lb
, const wide_int
&lh_ub
,
2028 const wide_int
&rh_lb
, const wide_int
&rh_ub
) const
2030 signop s
= TYPE_SIGN (type
);
2031 wide_int new_lb
= wi::max (lh_lb
, rh_lb
, s
);
2032 wide_int new_ub
= wi::max (lh_ub
, rh_ub
, s
);
2033 value_range_with_overflow (r
, type
, new_lb
, new_ub
);
2037 // Calculate the cross product of two sets of ranges and return it.
2039 // Multiplications, divisions and shifts are a bit tricky to handle,
2040 // depending on the mix of signs we have in the two ranges, we need to
2041 // operate on different values to get the minimum and maximum values
2042 // for the new range. One approach is to figure out all the
2043 // variations of range combinations and do the operations.
2045 // However, this involves several calls to compare_values and it is
2046 // pretty convoluted. It's simpler to do the 4 operations (MIN0 OP
2047 // MIN1, MIN0 OP MAX1, MAX0 OP MIN1 and MAX0 OP MAX0 OP MAX1) and then
2048 // figure the smallest and largest values to form the new range.
2051 cross_product_operator::wi_cross_product (irange
&r
, tree type
,
2052 const wide_int
&lh_lb
,
2053 const wide_int
&lh_ub
,
2054 const wide_int
&rh_lb
,
2055 const wide_int
&rh_ub
) const
2057 wide_int cp1
, cp2
, cp3
, cp4
;
2058 // Default to varying.
2059 r
.set_varying (type
);
2061 // Compute the 4 cross operations, bailing if we get an overflow we
2063 if (wi_op_overflows (cp1
, type
, lh_lb
, rh_lb
))
2065 if (wi::eq_p (lh_lb
, lh_ub
))
2067 else if (wi_op_overflows (cp3
, type
, lh_ub
, rh_lb
))
2069 if (wi::eq_p (rh_lb
, rh_ub
))
2071 else if (wi_op_overflows (cp2
, type
, lh_lb
, rh_ub
))
2073 if (wi::eq_p (lh_lb
, lh_ub
))
2075 else if (wi_op_overflows (cp4
, type
, lh_ub
, rh_ub
))
2079 signop sign
= TYPE_SIGN (type
);
2080 if (wi::gt_p (cp1
, cp2
, sign
))
2081 std::swap (cp1
, cp2
);
2082 if (wi::gt_p (cp3
, cp4
, sign
))
2083 std::swap (cp3
, cp4
);
2085 // Choose min and max from the ordered pairs.
2086 wide_int res_lb
= wi::min (cp1
, cp3
, sign
);
2087 wide_int res_ub
= wi::max (cp2
, cp4
, sign
);
2088 value_range_with_overflow (r
, type
, res_lb
, res_ub
);
2093 operator_mult::update_bitmask (irange
&r
, const irange
&lh
,
2094 const irange
&rh
) const
2096 update_known_bitmask (r
, MULT_EXPR
, lh
, rh
);
2100 operator_mult::op1_range (irange
&r
, tree type
,
2101 const irange
&lhs
, const irange
&op2
,
2102 relation_trio
) const
2104 if (lhs
.undefined_p ())
2107 // We can't solve 0 = OP1 * N by dividing by N with a wrapping type.
2108 // For example: For 0 = OP1 * 2, OP1 could be 0, or MAXINT, whereas
2109 // for 4 = OP1 * 2, OP1 could be 2 or 130 (unsigned 8-bit)
2110 if (TYPE_OVERFLOW_WRAPS (type
))
2114 if (op2
.singleton_p (offset
) && offset
!= 0)
2115 return range_op_handler (TRUNC_DIV_EXPR
).fold_range (r
, type
, lhs
, op2
);
2120 operator_mult::op2_range (irange
&r
, tree type
,
2121 const irange
&lhs
, const irange
&op1
,
2122 relation_trio rel
) const
2124 return operator_mult::op1_range (r
, type
, lhs
, op1
, rel
.swap_op1_op2 ());
2128 operator_mult::wi_op_overflows (wide_int
&res
, tree type
,
2129 const wide_int
&w0
, const wide_int
&w1
) const
2131 wi::overflow_type overflow
= wi::OVF_NONE
;
2132 signop sign
= TYPE_SIGN (type
);
2133 res
= wi::mul (w0
, w1
, sign
, &overflow
);
2134 if (overflow
&& TYPE_OVERFLOW_UNDEFINED (type
))
2136 // For multiplication, the sign of the overflow is given
2137 // by the comparison of the signs of the operands.
2138 if (sign
== UNSIGNED
|| w0
.sign_mask () == w1
.sign_mask ())
2139 res
= wi::max_value (w0
.get_precision (), sign
);
2141 res
= wi::min_value (w0
.get_precision (), sign
);
2148 operator_mult::wi_fold (irange
&r
, tree type
,
2149 const wide_int
&lh_lb
, const wide_int
&lh_ub
,
2150 const wide_int
&rh_lb
, const wide_int
&rh_ub
) const
2152 if (TYPE_OVERFLOW_UNDEFINED (type
))
2154 wi_cross_product (r
, type
, lh_lb
, lh_ub
, rh_lb
, rh_ub
);
2158 // Multiply the ranges when overflow wraps. This is basically fancy
2159 // code so we don't drop to varying with an unsigned
2162 // This test requires 2*prec bits if both operands are signed and
2163 // 2*prec + 2 bits if either is not. Therefore, extend the values
2164 // using the sign of the result to PREC2. From here on out,
2165 // everything is just signed math no matter what the input types
2168 signop sign
= TYPE_SIGN (type
);
2169 unsigned prec
= TYPE_PRECISION (type
);
2170 widest2_int min0
= widest2_int::from (lh_lb
, sign
);
2171 widest2_int max0
= widest2_int::from (lh_ub
, sign
);
2172 widest2_int min1
= widest2_int::from (rh_lb
, sign
);
2173 widest2_int max1
= widest2_int::from (rh_ub
, sign
);
2174 widest2_int sizem1
= wi::mask
<widest2_int
> (prec
, false);
2175 widest2_int size
= sizem1
+ 1;
2177 // Canonicalize the intervals.
2178 if (sign
== UNSIGNED
)
2180 if (wi::ltu_p (size
, min0
+ max0
))
2185 if (wi::ltu_p (size
, min1
+ max1
))
2192 // Sort the 4 products so that min is in prod0 and max is in
2194 widest2_int prod0
= min0
* min1
;
2195 widest2_int prod1
= min0
* max1
;
2196 widest2_int prod2
= max0
* min1
;
2197 widest2_int prod3
= max0
* max1
;
2199 // min0min1 > max0max1
2201 std::swap (prod0
, prod3
);
2203 // min0max1 > max0min1
2205 std::swap (prod1
, prod2
);
2208 std::swap (prod0
, prod1
);
2211 std::swap (prod2
, prod3
);
2214 prod2
= prod3
- prod0
;
2215 if (wi::geu_p (prod2
, sizem1
))
2217 // Multiplying by X, where X is a power of 2 is [0,0][X,+INF].
2218 if (TYPE_UNSIGNED (type
) && rh_lb
== rh_ub
2219 && wi::exact_log2 (rh_lb
) != -1 && prec
> 1)
2221 r
.set (type
, rh_lb
, wi::max_value (prec
, sign
));
2223 zero
.set_zero (type
);
2227 // The range covers all values.
2228 r
.set_varying (type
);
2232 wide_int new_lb
= wide_int::from (prod0
, prec
, sign
);
2233 wide_int new_ub
= wide_int::from (prod3
, prec
, sign
);
2234 create_possibly_reversed_range (r
, type
, new_lb
, new_ub
);
2238 class operator_widen_mult_signed
: public range_operator
2241 virtual void wi_fold (irange
&r
, tree type
,
2242 const wide_int
&lh_lb
,
2243 const wide_int
&lh_ub
,
2244 const wide_int
&rh_lb
,
2245 const wide_int
&rh_ub
)
2247 } op_widen_mult_signed
;
2250 operator_widen_mult_signed::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 signop s
= TYPE_SIGN (type
);
2258 wide_int lh_wlb
= wide_int::from (lh_lb
, wi::get_precision (lh_lb
) * 2, SIGNED
);
2259 wide_int lh_wub
= wide_int::from (lh_ub
, wi::get_precision (lh_ub
) * 2, SIGNED
);
2260 wide_int rh_wlb
= wide_int::from (rh_lb
, wi::get_precision (rh_lb
) * 2, s
);
2261 wide_int rh_wub
= wide_int::from (rh_ub
, wi::get_precision (rh_ub
) * 2, s
);
2263 /* We don't expect a widening multiplication to be able to overflow but range
2264 calculations for multiplications are complicated. After widening the
2265 operands lets call the base class. */
2266 return op_mult
.wi_fold (r
, type
, lh_wlb
, lh_wub
, rh_wlb
, rh_wub
);
2270 class operator_widen_mult_unsigned
: public range_operator
2273 virtual void wi_fold (irange
&r
, tree type
,
2274 const wide_int
&lh_lb
,
2275 const wide_int
&lh_ub
,
2276 const wide_int
&rh_lb
,
2277 const wide_int
&rh_ub
)
2279 } op_widen_mult_unsigned
;
2282 operator_widen_mult_unsigned::wi_fold (irange
&r
, tree type
,
2283 const wide_int
&lh_lb
,
2284 const wide_int
&lh_ub
,
2285 const wide_int
&rh_lb
,
2286 const wide_int
&rh_ub
) const
2288 signop s
= TYPE_SIGN (type
);
2290 wide_int lh_wlb
= wide_int::from (lh_lb
, wi::get_precision (lh_lb
) * 2, UNSIGNED
);
2291 wide_int lh_wub
= wide_int::from (lh_ub
, wi::get_precision (lh_ub
) * 2, UNSIGNED
);
2292 wide_int rh_wlb
= wide_int::from (rh_lb
, wi::get_precision (rh_lb
) * 2, s
);
2293 wide_int rh_wub
= wide_int::from (rh_ub
, wi::get_precision (rh_ub
) * 2, s
);
2295 /* We don't expect a widening multiplication to be able to overflow but range
2296 calculations for multiplications are complicated. After widening the
2297 operands lets call the base class. */
2298 return op_mult
.wi_fold (r
, type
, lh_wlb
, lh_wub
, rh_wlb
, rh_wub
);
2301 class operator_div
: public cross_product_operator
2304 operator_div (tree_code div_kind
) { m_code
= div_kind
; }
2305 virtual void wi_fold (irange
&r
, tree type
,
2306 const wide_int
&lh_lb
,
2307 const wide_int
&lh_ub
,
2308 const wide_int
&rh_lb
,
2309 const wide_int
&rh_ub
) const final override
;
2310 virtual bool wi_op_overflows (wide_int
&res
, tree type
,
2311 const wide_int
&, const wide_int
&)
2312 const final override
;
2313 void update_bitmask (irange
&r
, const irange
&lh
, const irange
&rh
) const
2314 { update_known_bitmask (r
, m_code
, lh
, rh
); }
2319 static operator_div
op_trunc_div (TRUNC_DIV_EXPR
);
2320 static operator_div
op_floor_div (FLOOR_DIV_EXPR
);
2321 static operator_div
op_round_div (ROUND_DIV_EXPR
);
2322 static operator_div
op_ceil_div (CEIL_DIV_EXPR
);
2325 operator_div::wi_op_overflows (wide_int
&res
, tree type
,
2326 const wide_int
&w0
, const wide_int
&w1
) const
2331 wi::overflow_type overflow
= wi::OVF_NONE
;
2332 signop sign
= TYPE_SIGN (type
);
2336 case EXACT_DIV_EXPR
:
2337 case TRUNC_DIV_EXPR
:
2338 res
= wi::div_trunc (w0
, w1
, sign
, &overflow
);
2340 case FLOOR_DIV_EXPR
:
2341 res
= wi::div_floor (w0
, w1
, sign
, &overflow
);
2343 case ROUND_DIV_EXPR
:
2344 res
= wi::div_round (w0
, w1
, sign
, &overflow
);
2347 res
= wi::div_ceil (w0
, w1
, sign
, &overflow
);
2353 if (overflow
&& TYPE_OVERFLOW_UNDEFINED (type
))
2355 // For division, the only case is -INF / -1 = +INF.
2356 res
= wi::max_value (w0
.get_precision (), sign
);
2363 operator_div::wi_fold (irange
&r
, tree type
,
2364 const wide_int
&lh_lb
, const wide_int
&lh_ub
,
2365 const wide_int
&rh_lb
, const wide_int
&rh_ub
) const
2367 const wide_int dividend_min
= lh_lb
;
2368 const wide_int dividend_max
= lh_ub
;
2369 const wide_int divisor_min
= rh_lb
;
2370 const wide_int divisor_max
= rh_ub
;
2371 signop sign
= TYPE_SIGN (type
);
2372 unsigned prec
= TYPE_PRECISION (type
);
2373 wide_int extra_min
, extra_max
;
2375 // If we know we won't divide by zero, just do the division.
2376 if (!wi_includes_zero_p (type
, divisor_min
, divisor_max
))
2378 wi_cross_product (r
, type
, dividend_min
, dividend_max
,
2379 divisor_min
, divisor_max
);
2383 // If we're definitely dividing by zero, there's nothing to do.
2384 if (wi_zero_p (type
, divisor_min
, divisor_max
))
2390 // Perform the division in 2 parts, [LB, -1] and [1, UB], which will
2391 // skip any division by zero.
2393 // First divide by the negative numbers, if any.
2394 if (wi::neg_p (divisor_min
, sign
))
2395 wi_cross_product (r
, type
, dividend_min
, dividend_max
,
2396 divisor_min
, wi::minus_one (prec
));
2400 // Then divide by the non-zero positive numbers, if any.
2401 if (wi::gt_p (divisor_max
, wi::zero (prec
), sign
))
2404 wi_cross_product (tmp
, type
, dividend_min
, dividend_max
,
2405 wi::one (prec
), divisor_max
);
2408 // We shouldn't still have undefined here.
2409 gcc_checking_assert (!r
.undefined_p ());
2413 class operator_exact_divide
: public operator_div
2415 using range_operator::op1_range
;
2417 operator_exact_divide () : operator_div (EXACT_DIV_EXPR
) { }
2418 virtual bool op1_range (irange
&r
, tree type
,
2421 relation_trio
) const;
2426 operator_exact_divide::op1_range (irange
&r
, tree type
,
2429 relation_trio
) const
2431 if (lhs
.undefined_p ())
2434 // [2, 4] = op1 / [3,3] since its exact divide, no need to worry about
2435 // remainders in the endpoints, so op1 = [2,4] * [3,3] = [6,12].
2436 // We wont bother trying to enumerate all the in between stuff :-P
2437 // TRUE accuracy is [6,6][9,9][12,12]. This is unlikely to matter most of
2438 // the time however.
2439 // If op2 is a multiple of 2, we would be able to set some non-zero bits.
2440 if (op2
.singleton_p (offset
) && offset
!= 0)
2441 return range_op_handler (MULT_EXPR
).fold_range (r
, type
, lhs
, op2
);
2446 class operator_lshift
: public cross_product_operator
2448 using range_operator::fold_range
;
2449 using range_operator::op1_range
;
2451 virtual bool op1_range (irange
&r
, tree type
, const irange
&lhs
,
2452 const irange
&op2
, relation_trio rel
= TRIO_VARYING
)
2453 const final override
;
2454 virtual bool fold_range (irange
&r
, tree type
, const irange
&op1
,
2455 const irange
&op2
, relation_trio rel
= TRIO_VARYING
)
2456 const final override
;
2458 virtual void wi_fold (irange
&r
, tree type
,
2459 const wide_int
&lh_lb
, const wide_int
&lh_ub
,
2460 const wide_int
&rh_lb
,
2461 const wide_int
&rh_ub
) const final override
;
2462 virtual bool wi_op_overflows (wide_int
&res
,
2465 const wide_int
&) const final override
;
2466 void update_bitmask (irange
&r
, const irange
&lh
,
2467 const irange
&rh
) const final override
2468 { update_known_bitmask (r
, LSHIFT_EXPR
, lh
, rh
); }
2471 class operator_rshift
: public cross_product_operator
2473 using range_operator::fold_range
;
2474 using range_operator::op1_range
;
2475 using range_operator::lhs_op1_relation
;
2477 virtual bool fold_range (irange
&r
, tree type
, const irange
&op1
,
2478 const irange
&op2
, relation_trio rel
= TRIO_VARYING
)
2479 const final override
;
2480 virtual void wi_fold (irange
&r
, tree type
,
2481 const wide_int
&lh_lb
,
2482 const wide_int
&lh_ub
,
2483 const wide_int
&rh_lb
,
2484 const wide_int
&rh_ub
) const final override
;
2485 virtual bool wi_op_overflows (wide_int
&res
,
2488 const wide_int
&w1
) const final override
;
2489 virtual bool op1_range (irange
&, tree type
, const irange
&lhs
,
2490 const irange
&op2
, relation_trio rel
= TRIO_VARYING
)
2491 const final override
;
2492 virtual relation_kind
lhs_op1_relation (const irange
&lhs
, const irange
&op1
,
2493 const irange
&op2
, relation_kind rel
)
2494 const final override
;
2495 void update_bitmask (irange
&r
, const irange
&lh
,
2496 const irange
&rh
) const final override
2497 { update_known_bitmask (r
, RSHIFT_EXPR
, lh
, rh
); }
2502 operator_rshift::lhs_op1_relation (const irange
&lhs ATTRIBUTE_UNUSED
,
2505 relation_kind
) const
2507 // If both operands range are >= 0, then the LHS <= op1.
2508 if (!op1
.undefined_p () && !op2
.undefined_p ()
2509 && wi::ge_p (op1
.lower_bound (), 0, TYPE_SIGN (op1
.type ()))
2510 && wi::ge_p (op2
.lower_bound (), 0, TYPE_SIGN (op2
.type ())))
2512 return VREL_VARYING
;
2516 operator_lshift::fold_range (irange
&r
, tree type
,
2519 relation_trio rel
) const
2521 int_range_max shift_range
;
2522 if (!get_shift_range (shift_range
, type
, op2
))
2524 if (op2
.undefined_p ())
2531 // Transform left shifts by constants into multiplies.
2532 if (shift_range
.singleton_p ())
2534 unsigned shift
= shift_range
.lower_bound ().to_uhwi ();
2535 wide_int tmp
= wi::set_bit_in_zero (shift
, TYPE_PRECISION (type
));
2536 int_range
<1> mult (type
, tmp
, tmp
);
2538 // Force wrapping multiplication.
2539 bool saved_flag_wrapv
= flag_wrapv
;
2540 bool saved_flag_wrapv_pointer
= flag_wrapv_pointer
;
2542 flag_wrapv_pointer
= 1;
2543 bool b
= op_mult
.fold_range (r
, type
, op1
, mult
);
2544 flag_wrapv
= saved_flag_wrapv
;
2545 flag_wrapv_pointer
= saved_flag_wrapv_pointer
;
2549 // Otherwise, invoke the generic fold routine.
2550 return range_operator::fold_range (r
, type
, op1
, shift_range
, rel
);
2554 operator_lshift::wi_fold (irange
&r
, tree type
,
2555 const wide_int
&lh_lb
, const wide_int
&lh_ub
,
2556 const wide_int
&rh_lb
, const wide_int
&rh_ub
) const
2558 signop sign
= TYPE_SIGN (type
);
2559 unsigned prec
= TYPE_PRECISION (type
);
2560 int overflow_pos
= sign
== SIGNED
? prec
- 1 : prec
;
2561 int bound_shift
= overflow_pos
- rh_ub
.to_shwi ();
2562 // If bound_shift == HOST_BITS_PER_WIDE_INT, the llshift can
2563 // overflow. However, for that to happen, rh.max needs to be zero,
2564 // which means rh is a singleton range of zero, which means we simply return
2565 // [lh_lb, lh_ub] as the range.
2566 if (wi::eq_p (rh_ub
, rh_lb
) && wi::eq_p (rh_ub
, 0))
2568 r
= int_range
<2> (type
, lh_lb
, lh_ub
);
2572 wide_int bound
= wi::set_bit_in_zero (bound_shift
, prec
);
2573 wide_int complement
= ~(bound
- 1);
2574 wide_int low_bound
, high_bound
;
2575 bool in_bounds
= false;
2577 if (sign
== UNSIGNED
)
2580 high_bound
= complement
;
2581 if (wi::ltu_p (lh_ub
, low_bound
))
2583 // [5, 6] << [1, 2] == [10, 24].
2584 // We're shifting out only zeroes, the value increases
2588 else if (wi::ltu_p (high_bound
, lh_lb
))
2590 // [0xffffff00, 0xffffffff] << [1, 2]
2591 // == [0xfffffc00, 0xfffffffe].
2592 // We're shifting out only ones, the value decreases
2599 // [-1, 1] << [1, 2] == [-4, 4]
2600 low_bound
= complement
;
2602 if (wi::lts_p (lh_ub
, high_bound
)
2603 && wi::lts_p (low_bound
, lh_lb
))
2605 // For non-negative numbers, we're shifting out only zeroes,
2606 // the value increases monotonically. For negative numbers,
2607 // we're shifting out only ones, the value decreases
2614 wi_cross_product (r
, type
, lh_lb
, lh_ub
, rh_lb
, rh_ub
);
2616 r
.set_varying (type
);
2620 operator_lshift::wi_op_overflows (wide_int
&res
, tree type
,
2621 const wide_int
&w0
, const wide_int
&w1
) const
2623 signop sign
= TYPE_SIGN (type
);
2626 // It's unclear from the C standard whether shifts can overflow.
2627 // The following code ignores overflow; perhaps a C standard
2628 // interpretation ruling is needed.
2629 res
= wi::rshift (w0
, -w1
, sign
);
2632 res
= wi::lshift (w0
, w1
);
2637 operator_lshift::op1_range (irange
&r
,
2641 relation_trio
) const
2643 if (lhs
.undefined_p ())
2646 if (!contains_zero_p (lhs
))
2647 r
.set_nonzero (type
);
2649 r
.set_varying (type
);
2652 if (op2
.singleton_p (shift
))
2654 if (wi::lt_p (shift
, 0, SIGNED
))
2656 if (wi::ge_p (shift
, wi::uhwi (TYPE_PRECISION (type
),
2657 TYPE_PRECISION (op2
.type ())),
2666 // Work completely in unsigned mode to start.
2668 int_range_max tmp_range
;
2669 if (TYPE_SIGN (type
) == SIGNED
)
2671 int_range_max tmp
= lhs
;
2672 utype
= unsigned_type_for (type
);
2673 range_cast (tmp
, utype
);
2674 op_rshift
.fold_range (tmp_range
, utype
, tmp
, op2
);
2677 op_rshift
.fold_range (tmp_range
, utype
, lhs
, op2
);
2679 // Start with ranges which can produce the LHS by right shifting the
2680 // result by the shift amount.
2681 // ie [0x08, 0xF0] = op1 << 2 will start with
2682 // [00001000, 11110000] = op1 << 2
2683 // [0x02, 0x4C] aka [00000010, 00111100]
2685 // Then create a range from the LB with the least significant upper bit
2686 // set, to the upper bound with all the bits set.
2687 // This would be [0x42, 0xFC] aka [01000010, 11111100].
2689 // Ideally we do this for each subrange, but just lump them all for now.
2690 unsigned low_bits
= TYPE_PRECISION (utype
) - shift
.to_uhwi ();
2691 wide_int up_mask
= wi::mask (low_bits
, true, TYPE_PRECISION (utype
));
2692 wide_int new_ub
= wi::bit_or (up_mask
, tmp_range
.upper_bound ());
2693 wide_int new_lb
= wi::set_bit (tmp_range
.lower_bound (), low_bits
);
2694 int_range
<2> fill_range (utype
, new_lb
, new_ub
);
2695 tmp_range
.union_ (fill_range
);
2698 range_cast (tmp_range
, type
);
2700 r
.intersect (tmp_range
);
2704 return !r
.varying_p ();
2708 operator_rshift::op1_range (irange
&r
,
2712 relation_trio
) const
2714 if (lhs
.undefined_p ())
2717 if (op2
.singleton_p (shift
))
2719 // Ignore nonsensical shifts.
2720 unsigned prec
= TYPE_PRECISION (type
);
2721 if (wi::ge_p (shift
,
2722 wi::uhwi (prec
, TYPE_PRECISION (op2
.type ())),
2731 // Folding the original operation may discard some impossible
2732 // ranges from the LHS.
2733 int_range_max lhs_refined
;
2734 op_rshift
.fold_range (lhs_refined
, type
, int_range
<1> (type
), op2
);
2735 lhs_refined
.intersect (lhs
);
2736 if (lhs_refined
.undefined_p ())
2741 int_range_max
shift_range (op2
.type (), shift
, shift
);
2742 int_range_max lb
, ub
;
2743 op_lshift
.fold_range (lb
, type
, lhs_refined
, shift_range
);
2745 // 0000 0111 = OP1 >> 3
2747 // OP1 is anything from 0011 1000 to 0011 1111. That is, a
2748 // range from LHS<<3 plus a mask of the 3 bits we shifted on the
2749 // right hand side (0x07).
2750 wide_int mask
= wi::bit_not (wi::lshift (wi::minus_one (prec
), shift
));
2751 int_range_max
mask_range (type
,
2752 wi::zero (TYPE_PRECISION (type
)),
2754 op_plus
.fold_range (ub
, type
, lb
, mask_range
);
2757 if (!contains_zero_p (lhs_refined
))
2759 mask_range
.invert ();
2760 r
.intersect (mask_range
);
2768 operator_rshift::wi_op_overflows (wide_int
&res
,
2771 const wide_int
&w1
) const
2773 signop sign
= TYPE_SIGN (type
);
2775 res
= wi::lshift (w0
, -w1
);
2778 // It's unclear from the C standard whether shifts can overflow.
2779 // The following code ignores overflow; perhaps a C standard
2780 // interpretation ruling is needed.
2781 res
= wi::rshift (w0
, w1
, sign
);
2787 operator_rshift::fold_range (irange
&r
, tree type
,
2790 relation_trio rel
) const
2792 int_range_max shift
;
2793 if (!get_shift_range (shift
, type
, op2
))
2795 if (op2
.undefined_p ())
2802 return range_operator::fold_range (r
, type
, op1
, shift
, rel
);
2806 operator_rshift::wi_fold (irange
&r
, tree type
,
2807 const wide_int
&lh_lb
, const wide_int
&lh_ub
,
2808 const wide_int
&rh_lb
, const wide_int
&rh_ub
) const
2810 wi_cross_product (r
, type
, lh_lb
, lh_ub
, rh_lb
, rh_ub
);
2814 // Add a partial equivalence between the LHS and op1 for casts.
2817 operator_cast::lhs_op1_relation (const irange
&lhs
,
2819 const irange
&op2 ATTRIBUTE_UNUSED
,
2820 relation_kind
) const
2822 if (lhs
.undefined_p () || op1
.undefined_p ())
2823 return VREL_VARYING
;
2824 unsigned lhs_prec
= TYPE_PRECISION (lhs
.type ());
2825 unsigned op1_prec
= TYPE_PRECISION (op1
.type ());
2826 // If the result gets sign extended into a larger type check first if this
2827 // qualifies as a partial equivalence.
2828 if (TYPE_SIGN (op1
.type ()) == SIGNED
&& lhs_prec
> op1_prec
)
2830 // If the result is sign extended, and the LHS is larger than op1,
2831 // check if op1's range can be negative as the sign extension will
2832 // cause the upper bits to be 1 instead of 0, invalidating the PE.
2833 int_range
<3> negs
= range_negatives (op1
.type ());
2834 negs
.intersect (op1
);
2835 if (!negs
.undefined_p ())
2836 return VREL_VARYING
;
2839 unsigned prec
= MIN (lhs_prec
, op1_prec
);
2840 return bits_to_pe (prec
);
2843 // Return TRUE if casting from INNER to OUTER is a truncating cast.
2846 operator_cast::truncating_cast_p (const irange
&inner
,
2847 const irange
&outer
) const
2849 return TYPE_PRECISION (outer
.type ()) < TYPE_PRECISION (inner
.type ());
2852 // Return TRUE if [MIN,MAX] is inside the domain of RANGE's type.
2855 operator_cast::inside_domain_p (const wide_int
&min
,
2856 const wide_int
&max
,
2857 const irange
&range
) const
2859 wide_int domain_min
= irange_val_min (range
.type ());
2860 wide_int domain_max
= irange_val_max (range
.type ());
2861 signop domain_sign
= TYPE_SIGN (range
.type ());
2862 return (wi::le_p (min
, domain_max
, domain_sign
)
2863 && wi::le_p (max
, domain_max
, domain_sign
)
2864 && wi::ge_p (min
, domain_min
, domain_sign
)
2865 && wi::ge_p (max
, domain_min
, domain_sign
));
2869 // Helper for fold_range which work on a pair at a time.
2872 operator_cast::fold_pair (irange
&r
, unsigned index
,
2873 const irange
&inner
,
2874 const irange
&outer
) const
2876 tree inner_type
= inner
.type ();
2877 tree outer_type
= outer
.type ();
2878 signop inner_sign
= TYPE_SIGN (inner_type
);
2879 unsigned outer_prec
= TYPE_PRECISION (outer_type
);
2881 // check to see if casting from INNER to OUTER is a conversion that
2882 // fits in the resulting OUTER type.
2883 wide_int inner_lb
= inner
.lower_bound (index
);
2884 wide_int inner_ub
= inner
.upper_bound (index
);
2885 if (truncating_cast_p (inner
, outer
))
2887 // We may be able to accommodate a truncating cast if the
2888 // resulting range can be represented in the target type...
2889 if (wi::rshift (wi::sub (inner_ub
, inner_lb
),
2890 wi::uhwi (outer_prec
, TYPE_PRECISION (inner
.type ())),
2893 r
.set_varying (outer_type
);
2897 // ...but we must still verify that the final range fits in the
2898 // domain. This catches -fstrict-enum restrictions where the domain
2899 // range is smaller than what fits in the underlying type.
2900 wide_int min
= wide_int::from (inner_lb
, outer_prec
, inner_sign
);
2901 wide_int max
= wide_int::from (inner_ub
, outer_prec
, inner_sign
);
2902 if (inside_domain_p (min
, max
, outer
))
2903 create_possibly_reversed_range (r
, outer_type
, min
, max
);
2905 r
.set_varying (outer_type
);
2910 operator_cast::fold_range (irange
&r
, tree type ATTRIBUTE_UNUSED
,
2911 const irange
&inner
,
2912 const irange
&outer
,
2913 relation_trio
) const
2915 if (empty_range_varying (r
, type
, inner
, outer
))
2918 gcc_checking_assert (outer
.varying_p ());
2919 gcc_checking_assert (inner
.num_pairs () > 0);
2921 // Avoid a temporary by folding the first pair directly into the result.
2922 fold_pair (r
, 0, inner
, outer
);
2924 // Then process any additional pairs by unioning with their results.
2925 for (unsigned x
= 1; x
< inner
.num_pairs (); ++x
)
2928 fold_pair (tmp
, x
, inner
, outer
);
2934 update_bitmask (r
, inner
, outer
);
2939 operator_cast::update_bitmask (irange
&r
, const irange
&lh
,
2940 const irange
&rh
) const
2942 update_known_bitmask (r
, CONVERT_EXPR
, lh
, rh
);
2946 operator_cast::op1_range (irange
&r
, tree type
,
2949 relation_trio
) const
2951 if (lhs
.undefined_p ())
2953 tree lhs_type
= lhs
.type ();
2954 gcc_checking_assert (types_compatible_p (op2
.type(), type
));
2956 // If we are calculating a pointer, shortcut to what we really care about.
2957 if (POINTER_TYPE_P (type
))
2959 // Conversion from other pointers or a constant (including 0/NULL)
2960 // are straightforward.
2961 if (POINTER_TYPE_P (lhs
.type ())
2962 || (lhs
.singleton_p ()
2963 && TYPE_PRECISION (lhs
.type ()) >= TYPE_PRECISION (type
)))
2966 range_cast (r
, type
);
2970 // If the LHS is not a pointer nor a singleton, then it is
2971 // either VARYING or non-zero.
2972 if (!lhs
.undefined_p () && !contains_zero_p (lhs
))
2973 r
.set_nonzero (type
);
2975 r
.set_varying (type
);
2981 if (truncating_cast_p (op2
, lhs
))
2983 if (lhs
.varying_p ())
2984 r
.set_varying (type
);
2987 // We want to insert the LHS as an unsigned value since it
2988 // would not trigger the signed bit of the larger type.
2989 int_range_max converted_lhs
= lhs
;
2990 range_cast (converted_lhs
, unsigned_type_for (lhs_type
));
2991 range_cast (converted_lhs
, type
);
2992 // Start by building the positive signed outer range for the type.
2993 wide_int lim
= wi::set_bit_in_zero (TYPE_PRECISION (lhs_type
),
2994 TYPE_PRECISION (type
));
2995 create_possibly_reversed_range (r
, type
, lim
,
2996 wi::max_value (TYPE_PRECISION (type
),
2998 // For the signed part, we need to simply union the 2 ranges now.
2999 r
.union_ (converted_lhs
);
3001 // Create maximal negative number outside of LHS bits.
3002 lim
= wi::mask (TYPE_PRECISION (lhs_type
), true,
3003 TYPE_PRECISION (type
));
3004 // Add this to the unsigned LHS range(s).
3005 int_range_max
lim_range (type
, lim
, lim
);
3006 int_range_max lhs_neg
;
3007 range_op_handler (PLUS_EXPR
).fold_range (lhs_neg
, type
,
3008 converted_lhs
, lim_range
);
3009 // lhs_neg now has all the negative versions of the LHS.
3010 // Now union in all the values from SIGNED MIN (0x80000) to
3011 // lim-1 in order to fill in all the ranges with the upper
3014 // PR 97317. If the lhs has only 1 bit less precision than the rhs,
3015 // we don't need to create a range from min to lim-1
3016 // calculate neg range traps trying to create [lim, lim - 1].
3017 wide_int min_val
= wi::min_value (TYPE_PRECISION (type
), SIGNED
);
3020 int_range_max
neg (type
,
3021 wi::min_value (TYPE_PRECISION (type
),
3024 lhs_neg
.union_ (neg
);
3026 // And finally, munge the signed and unsigned portions.
3029 // And intersect with any known value passed in the extra operand.
3035 if (TYPE_PRECISION (lhs_type
) == TYPE_PRECISION (type
))
3039 // The cast is not truncating, and the range is restricted to
3040 // the range of the RHS by this assignment.
3042 // Cast the range of the RHS to the type of the LHS.
3043 fold_range (tmp
, lhs_type
, int_range
<1> (type
), int_range
<1> (lhs_type
));
3044 // Intersect this with the LHS range will produce the range,
3045 // which will be cast to the RHS type before returning.
3046 tmp
.intersect (lhs
);
3049 // Cast the calculated range to the type of the RHS.
3050 fold_range (r
, type
, tmp
, int_range
<1> (type
));
3055 class operator_logical_and
: public range_operator
3057 using range_operator::fold_range
;
3058 using range_operator::op1_range
;
3059 using range_operator::op2_range
;
3061 virtual bool fold_range (irange
&r
, tree type
,
3064 relation_trio rel
= TRIO_VARYING
) const;
3065 virtual bool op1_range (irange
&r
, tree type
,
3068 relation_trio rel
= TRIO_VARYING
) const;
3069 virtual bool op2_range (irange
&r
, tree type
,
3072 relation_trio rel
= TRIO_VARYING
) const;
3077 operator_logical_and::fold_range (irange
&r
, tree type
,
3080 relation_trio
) const
3082 if (empty_range_varying (r
, type
, lh
, rh
))
3085 // 0 && anything is 0.
3086 if ((wi::eq_p (lh
.lower_bound (), 0) && wi::eq_p (lh
.upper_bound (), 0))
3087 || (wi::eq_p (lh
.lower_bound (), 0) && wi::eq_p (rh
.upper_bound (), 0)))
3088 r
= range_false (type
);
3089 else if (contains_zero_p (lh
) || contains_zero_p (rh
))
3090 // To reach this point, there must be a logical 1 on each side, and
3091 // the only remaining question is whether there is a zero or not.
3092 r
= range_true_and_false (type
);
3094 r
= range_true (type
);
3099 operator_logical_and::op1_range (irange
&r
, tree type
,
3101 const irange
&op2 ATTRIBUTE_UNUSED
,
3102 relation_trio
) const
3104 switch (get_bool_state (r
, lhs
, type
))
3107 // A true result means both sides of the AND must be true.
3108 r
= range_true (type
);
3111 // Any other result means only one side has to be false, the
3112 // other side can be anything. So we cannot be sure of any
3114 r
= range_true_and_false (type
);
3121 operator_logical_and::op2_range (irange
&r
, tree type
,
3124 relation_trio
) const
3126 return operator_logical_and::op1_range (r
, type
, lhs
, op1
);
3131 operator_bitwise_and::update_bitmask (irange
&r
, const irange
&lh
,
3132 const irange
&rh
) const
3134 update_known_bitmask (r
, BIT_AND_EXPR
, lh
, rh
);
3137 // Optimize BIT_AND_EXPR, BIT_IOR_EXPR and BIT_XOR_EXPR of signed types
3138 // by considering the number of leading redundant sign bit copies.
3139 // clrsb (X op Y) = min (clrsb (X), clrsb (Y)), so for example
3140 // [-1, 0] op [-1, 0] is [-1, 0] (where nonzero_bits doesn't help).
3142 wi_optimize_signed_bitwise_op (irange
&r
, tree type
,
3143 const wide_int
&lh_lb
, const wide_int
&lh_ub
,
3144 const wide_int
&rh_lb
, const wide_int
&rh_ub
)
3146 int lh_clrsb
= MIN (wi::clrsb (lh_lb
), wi::clrsb (lh_ub
));
3147 int rh_clrsb
= MIN (wi::clrsb (rh_lb
), wi::clrsb (rh_ub
));
3148 int new_clrsb
= MIN (lh_clrsb
, rh_clrsb
);
3151 int type_prec
= TYPE_PRECISION (type
);
3152 int rprec
= (type_prec
- new_clrsb
) - 1;
3153 value_range_with_overflow (r
, type
,
3154 wi::mask (rprec
, true, type_prec
),
3155 wi::mask (rprec
, false, type_prec
));
3159 // An AND of 8,16, 32 or 64 bits can produce a partial equivalence between
3163 operator_bitwise_and::lhs_op1_relation (const irange
&lhs
,
3166 relation_kind
) const
3168 if (lhs
.undefined_p () || op1
.undefined_p () || op2
.undefined_p ())
3169 return VREL_VARYING
;
3170 if (!op2
.singleton_p ())
3171 return VREL_VARYING
;
3172 // if val == 0xff or 0xFFFF OR 0Xffffffff OR 0Xffffffffffffffff, return TRUE
3173 int prec1
= TYPE_PRECISION (op1
.type ());
3174 int prec2
= TYPE_PRECISION (op2
.type ());
3176 wide_int mask
= op2
.lower_bound ();
3177 if (wi::eq_p (mask
, wi::mask (8, false, prec2
)))
3179 else if (wi::eq_p (mask
, wi::mask (16, false, prec2
)))
3181 else if (wi::eq_p (mask
, wi::mask (32, false, prec2
)))
3183 else if (wi::eq_p (mask
, wi::mask (64, false, prec2
)))
3185 return bits_to_pe (MIN (prec1
, mask_prec
));
3188 // Optimize BIT_AND_EXPR and BIT_IOR_EXPR in terms of a mask if
3189 // possible. Basically, see if we can optimize:
3193 // [LB op Z, UB op Z]
3195 // If the optimization was successful, accumulate the range in R and
3199 wi_optimize_and_or (irange
&r
,
3200 enum tree_code code
,
3202 const wide_int
&lh_lb
, const wide_int
&lh_ub
,
3203 const wide_int
&rh_lb
, const wide_int
&rh_ub
)
3205 // Calculate the singleton mask among the ranges, if any.
3206 wide_int lower_bound
, upper_bound
, mask
;
3207 if (wi::eq_p (rh_lb
, rh_ub
))
3210 lower_bound
= lh_lb
;
3211 upper_bound
= lh_ub
;
3213 else if (wi::eq_p (lh_lb
, lh_ub
))
3216 lower_bound
= rh_lb
;
3217 upper_bound
= rh_ub
;
3222 // If Z is a constant which (for op | its bitwise not) has n
3223 // consecutive least significant bits cleared followed by m 1
3224 // consecutive bits set immediately above it and either
3225 // m + n == precision, or (x >> (m + n)) == (y >> (m + n)).
3227 // The least significant n bits of all the values in the range are
3228 // cleared or set, the m bits above it are preserved and any bits
3229 // above these are required to be the same for all values in the
3233 if (code
== BIT_IOR_EXPR
)
3235 if (wi::eq_p (w
, 0))
3236 n
= w
.get_precision ();
3240 w
= ~(w
| wi::mask (n
, false, w
.get_precision ()));
3241 if (wi::eq_p (w
, 0))
3242 m
= w
.get_precision () - n
;
3244 m
= wi::ctz (w
) - n
;
3246 wide_int new_mask
= wi::mask (m
+ n
, true, w
.get_precision ());
3247 if ((new_mask
& lower_bound
) != (new_mask
& upper_bound
))
3250 wide_int res_lb
, res_ub
;
3251 if (code
== BIT_AND_EXPR
)
3253 res_lb
= wi::bit_and (lower_bound
, mask
);
3254 res_ub
= wi::bit_and (upper_bound
, mask
);
3256 else if (code
== BIT_IOR_EXPR
)
3258 res_lb
= wi::bit_or (lower_bound
, mask
);
3259 res_ub
= wi::bit_or (upper_bound
, mask
);
3263 value_range_with_overflow (r
, type
, res_lb
, res_ub
);
3265 // Furthermore, if the mask is non-zero, an IOR cannot contain zero.
3266 if (code
== BIT_IOR_EXPR
&& wi::ne_p (mask
, 0))
3269 tmp
.set_nonzero (type
);
3275 // For range [LB, UB] compute two wide_int bit masks.
3277 // In the MAYBE_NONZERO bit mask, if some bit is unset, it means that
3278 // for all numbers in the range the bit is 0, otherwise it might be 0
3281 // In the MUSTBE_NONZERO bit mask, if some bit is set, it means that
3282 // for all numbers in the range the bit is 1, otherwise it might be 0
3286 wi_set_zero_nonzero_bits (tree type
,
3287 const wide_int
&lb
, const wide_int
&ub
,
3288 wide_int
&maybe_nonzero
,
3289 wide_int
&mustbe_nonzero
)
3291 signop sign
= TYPE_SIGN (type
);
3293 if (wi::eq_p (lb
, ub
))
3294 maybe_nonzero
= mustbe_nonzero
= lb
;
3295 else if (wi::ge_p (lb
, 0, sign
) || wi::lt_p (ub
, 0, sign
))
3297 wide_int xor_mask
= lb
^ ub
;
3298 maybe_nonzero
= lb
| ub
;
3299 mustbe_nonzero
= lb
& ub
;
3302 wide_int mask
= wi::mask (wi::floor_log2 (xor_mask
), false,
3303 maybe_nonzero
.get_precision ());
3304 maybe_nonzero
= maybe_nonzero
| mask
;
3305 mustbe_nonzero
= wi::bit_and_not (mustbe_nonzero
, mask
);
3310 maybe_nonzero
= wi::minus_one (lb
.get_precision ());
3311 mustbe_nonzero
= wi::zero (lb
.get_precision ());
3316 operator_bitwise_and::wi_fold (irange
&r
, tree type
,
3317 const wide_int
&lh_lb
,
3318 const wide_int
&lh_ub
,
3319 const wide_int
&rh_lb
,
3320 const wide_int
&rh_ub
) const
3322 if (wi_optimize_and_or (r
, BIT_AND_EXPR
, type
, lh_lb
, lh_ub
, rh_lb
, rh_ub
))
3325 wide_int maybe_nonzero_lh
, mustbe_nonzero_lh
;
3326 wide_int maybe_nonzero_rh
, mustbe_nonzero_rh
;
3327 wi_set_zero_nonzero_bits (type
, lh_lb
, lh_ub
,
3328 maybe_nonzero_lh
, mustbe_nonzero_lh
);
3329 wi_set_zero_nonzero_bits (type
, rh_lb
, rh_ub
,
3330 maybe_nonzero_rh
, mustbe_nonzero_rh
);
3332 wide_int new_lb
= mustbe_nonzero_lh
& mustbe_nonzero_rh
;
3333 wide_int new_ub
= maybe_nonzero_lh
& maybe_nonzero_rh
;
3334 signop sign
= TYPE_SIGN (type
);
3335 unsigned prec
= TYPE_PRECISION (type
);
3336 // If both input ranges contain only negative values, we can
3337 // truncate the result range maximum to the minimum of the
3338 // input range maxima.
3339 if (wi::lt_p (lh_ub
, 0, sign
) && wi::lt_p (rh_ub
, 0, sign
))
3341 new_ub
= wi::min (new_ub
, lh_ub
, sign
);
3342 new_ub
= wi::min (new_ub
, rh_ub
, sign
);
3344 // If either input range contains only non-negative values
3345 // we can truncate the result range maximum to the respective
3346 // maximum of the input range.
3347 if (wi::ge_p (lh_lb
, 0, sign
))
3348 new_ub
= wi::min (new_ub
, lh_ub
, sign
);
3349 if (wi::ge_p (rh_lb
, 0, sign
))
3350 new_ub
= wi::min (new_ub
, rh_ub
, sign
);
3351 // PR68217: In case of signed & sign-bit-CST should
3352 // result in [-INF, 0] instead of [-INF, INF].
3353 if (wi::gt_p (new_lb
, new_ub
, sign
))
3355 wide_int sign_bit
= wi::set_bit_in_zero (prec
- 1, prec
);
3357 && ((wi::eq_p (lh_lb
, lh_ub
)
3358 && !wi::cmps (lh_lb
, sign_bit
))
3359 || (wi::eq_p (rh_lb
, rh_ub
)
3360 && !wi::cmps (rh_lb
, sign_bit
))))
3362 new_lb
= wi::min_value (prec
, sign
);
3363 new_ub
= wi::zero (prec
);
3366 // If the limits got swapped around, return varying.
3367 if (wi::gt_p (new_lb
, new_ub
,sign
))
3370 && wi_optimize_signed_bitwise_op (r
, type
,
3374 r
.set_varying (type
);
3377 value_range_with_overflow (r
, type
, new_lb
, new_ub
);
3381 set_nonzero_range_from_mask (irange
&r
, tree type
, const irange
&lhs
)
3383 if (lhs
.undefined_p () || contains_zero_p (lhs
))
3384 r
.set_varying (type
);
3386 r
.set_nonzero (type
);
3389 /* Find out smallest RES where RES > VAL && (RES & MASK) == RES, if any
3390 (otherwise return VAL). VAL and MASK must be zero-extended for
3391 precision PREC. If SGNBIT is non-zero, first xor VAL with SGNBIT
3392 (to transform signed values into unsigned) and at the end xor
3396 masked_increment (const wide_int
&val_in
, const wide_int
&mask
,
3397 const wide_int
&sgnbit
, unsigned int prec
)
3399 wide_int bit
= wi::one (prec
), res
;
3402 wide_int val
= val_in
^ sgnbit
;
3403 for (i
= 0; i
< prec
; i
++, bit
+= bit
)
3406 if ((res
& bit
) == 0)
3409 res
= wi::bit_and_not (val
+ bit
, res
);
3411 if (wi::gtu_p (res
, val
))
3412 return res
^ sgnbit
;
3414 return val
^ sgnbit
;
3417 // This was shamelessly stolen from register_edge_assert_for_2 and
3418 // adjusted to work with iranges.
3421 operator_bitwise_and::simple_op1_range_solver (irange
&r
, tree type
,
3423 const irange
&op2
) const
3425 if (!op2
.singleton_p ())
3427 set_nonzero_range_from_mask (r
, type
, lhs
);
3430 unsigned int nprec
= TYPE_PRECISION (type
);
3431 wide_int cst2v
= op2
.lower_bound ();
3432 bool cst2n
= wi::neg_p (cst2v
, TYPE_SIGN (type
));
3435 sgnbit
= wi::set_bit_in_zero (nprec
- 1, nprec
);
3437 sgnbit
= wi::zero (nprec
);
3439 // Solve [lhs.lower_bound (), +INF] = x & MASK.
3441 // Minimum unsigned value for >= if (VAL & CST2) == VAL is VAL and
3442 // maximum unsigned value is ~0. For signed comparison, if CST2
3443 // doesn't have the most significant bit set, handle it similarly. If
3444 // CST2 has MSB set, the minimum is the same, and maximum is ~0U/2.
3445 wide_int valv
= lhs
.lower_bound ();
3446 wide_int minv
= valv
& cst2v
, maxv
;
3447 bool we_know_nothing
= false;
3450 // If (VAL & CST2) != VAL, X & CST2 can't be equal to VAL.
3451 minv
= masked_increment (valv
, cst2v
, sgnbit
, nprec
);
3454 // If we can't determine anything on this bound, fall
3455 // through and conservatively solve for the other end point.
3456 we_know_nothing
= true;
3459 maxv
= wi::mask (nprec
- (cst2n
? 1 : 0), false, nprec
);
3460 if (we_know_nothing
)
3461 r
.set_varying (type
);
3463 create_possibly_reversed_range (r
, type
, minv
, maxv
);
3465 // Solve [-INF, lhs.upper_bound ()] = x & MASK.
3467 // Minimum unsigned value for <= is 0 and maximum unsigned value is
3468 // VAL | ~CST2 if (VAL & CST2) == VAL. Otherwise, find smallest
3470 // VAL2 > VAL && (VAL2 & CST2) == VAL2 and use (VAL2 - 1) | ~CST2
3472 // For signed comparison, if CST2 doesn't have most significant bit
3473 // set, handle it similarly. If CST2 has MSB set, the maximum is
3474 // the same and minimum is INT_MIN.
3475 valv
= lhs
.upper_bound ();
3476 minv
= valv
& cst2v
;
3481 maxv
= masked_increment (valv
, cst2v
, sgnbit
, nprec
);
3484 // If we couldn't determine anything on either bound, return
3486 if (we_know_nothing
)
3494 int_range
<2> upper_bits
;
3495 create_possibly_reversed_range (upper_bits
, type
, minv
, maxv
);
3496 r
.intersect (upper_bits
);
3500 operator_bitwise_and::op1_range (irange
&r
, tree type
,
3503 relation_trio
) const
3505 if (lhs
.undefined_p ())
3507 if (types_compatible_p (type
, boolean_type_node
))
3508 return op_logical_and
.op1_range (r
, type
, lhs
, op2
);
3511 for (unsigned i
= 0; i
< lhs
.num_pairs (); ++i
)
3513 int_range_max
chunk (lhs
.type (),
3514 lhs
.lower_bound (i
),
3515 lhs
.upper_bound (i
));
3517 simple_op1_range_solver (res
, type
, chunk
, op2
);
3520 if (r
.undefined_p ())
3521 set_nonzero_range_from_mask (r
, type
, lhs
);
3523 // For MASK == op1 & MASK, all the bits in MASK must be set in op1.
3525 if (lhs
== op2
&& lhs
.singleton_p (mask
))
3527 r
.update_bitmask (irange_bitmask (mask
, ~mask
));
3531 // For 0 = op1 & MASK, op1 is ~MASK.
3532 if (lhs
.zero_p () && op2
.singleton_p ())
3534 wide_int nz
= wi::bit_not (op2
.get_nonzero_bits ());
3535 int_range
<2> tmp (type
);
3536 tmp
.set_nonzero_bits (nz
);
3543 operator_bitwise_and::op2_range (irange
&r
, tree type
,
3546 relation_trio
) const
3548 return operator_bitwise_and::op1_range (r
, type
, lhs
, op1
);
3552 class operator_logical_or
: public range_operator
3554 using range_operator::fold_range
;
3555 using range_operator::op1_range
;
3556 using range_operator::op2_range
;
3558 virtual bool fold_range (irange
&r
, tree type
,
3561 relation_trio rel
= TRIO_VARYING
) const;
3562 virtual bool op1_range (irange
&r
, tree type
,
3565 relation_trio rel
= TRIO_VARYING
) const;
3566 virtual bool op2_range (irange
&r
, tree type
,
3569 relation_trio rel
= TRIO_VARYING
) const;
3573 operator_logical_or::fold_range (irange
&r
, tree type ATTRIBUTE_UNUSED
,
3576 relation_trio
) const
3578 if (empty_range_varying (r
, type
, lh
, rh
))
3587 operator_logical_or::op1_range (irange
&r
, tree type
,
3589 const irange
&op2 ATTRIBUTE_UNUSED
,
3590 relation_trio
) const
3592 switch (get_bool_state (r
, lhs
, type
))
3595 // A false result means both sides of the OR must be false.
3596 r
= range_false (type
);
3599 // Any other result means only one side has to be true, the
3600 // other side can be anything. so we can't be sure of any result
3602 r
= range_true_and_false (type
);
3609 operator_logical_or::op2_range (irange
&r
, tree type
,
3612 relation_trio
) const
3614 return operator_logical_or::op1_range (r
, type
, lhs
, op1
);
3619 operator_bitwise_or::update_bitmask (irange
&r
, const irange
&lh
,
3620 const irange
&rh
) const
3622 update_known_bitmask (r
, BIT_IOR_EXPR
, lh
, rh
);
3626 operator_bitwise_or::wi_fold (irange
&r
, tree type
,
3627 const wide_int
&lh_lb
,
3628 const wide_int
&lh_ub
,
3629 const wide_int
&rh_lb
,
3630 const wide_int
&rh_ub
) const
3632 if (wi_optimize_and_or (r
, BIT_IOR_EXPR
, type
, lh_lb
, lh_ub
, rh_lb
, rh_ub
))
3635 wide_int maybe_nonzero_lh
, mustbe_nonzero_lh
;
3636 wide_int maybe_nonzero_rh
, mustbe_nonzero_rh
;
3637 wi_set_zero_nonzero_bits (type
, lh_lb
, lh_ub
,
3638 maybe_nonzero_lh
, mustbe_nonzero_lh
);
3639 wi_set_zero_nonzero_bits (type
, rh_lb
, rh_ub
,
3640 maybe_nonzero_rh
, mustbe_nonzero_rh
);
3641 wide_int new_lb
= mustbe_nonzero_lh
| mustbe_nonzero_rh
;
3642 wide_int new_ub
= maybe_nonzero_lh
| maybe_nonzero_rh
;
3643 signop sign
= TYPE_SIGN (type
);
3644 // If the input ranges contain only positive values we can
3645 // truncate the minimum of the result range to the maximum
3646 // of the input range minima.
3647 if (wi::ge_p (lh_lb
, 0, sign
)
3648 && wi::ge_p (rh_lb
, 0, sign
))
3650 new_lb
= wi::max (new_lb
, lh_lb
, sign
);
3651 new_lb
= wi::max (new_lb
, rh_lb
, sign
);
3653 // If either input range contains only negative values
3654 // we can truncate the minimum of the result range to the
3655 // respective minimum range.
3656 if (wi::lt_p (lh_ub
, 0, sign
))
3657 new_lb
= wi::max (new_lb
, lh_lb
, sign
);
3658 if (wi::lt_p (rh_ub
, 0, sign
))
3659 new_lb
= wi::max (new_lb
, rh_lb
, sign
);
3660 // If the limits got swapped around, return a conservative range.
3661 if (wi::gt_p (new_lb
, new_ub
, sign
))
3663 // Make sure that nonzero|X is nonzero.
3664 if (wi::gt_p (lh_lb
, 0, sign
)
3665 || wi::gt_p (rh_lb
, 0, sign
)
3666 || wi::lt_p (lh_ub
, 0, sign
)
3667 || wi::lt_p (rh_ub
, 0, sign
))
3668 r
.set_nonzero (type
);
3669 else if (sign
== SIGNED
3670 && wi_optimize_signed_bitwise_op (r
, type
,
3675 r
.set_varying (type
);
3678 value_range_with_overflow (r
, type
, new_lb
, new_ub
);
3682 operator_bitwise_or::op1_range (irange
&r
, tree type
,
3685 relation_trio
) const
3687 if (lhs
.undefined_p ())
3689 // If this is really a logical wi_fold, call that.
3690 if (types_compatible_p (type
, boolean_type_node
))
3691 return op_logical_or
.op1_range (r
, type
, lhs
, op2
);
3698 r
.set_varying (type
);
3703 operator_bitwise_or::op2_range (irange
&r
, tree type
,
3706 relation_trio
) const
3708 return operator_bitwise_or::op1_range (r
, type
, lhs
, op1
);
3712 operator_bitwise_xor::update_bitmask (irange
&r
, const irange
&lh
,
3713 const irange
&rh
) const
3715 update_known_bitmask (r
, BIT_XOR_EXPR
, lh
, rh
);
3719 operator_bitwise_xor::wi_fold (irange
&r
, tree type
,
3720 const wide_int
&lh_lb
,
3721 const wide_int
&lh_ub
,
3722 const wide_int
&rh_lb
,
3723 const wide_int
&rh_ub
) const
3725 signop sign
= TYPE_SIGN (type
);
3726 wide_int maybe_nonzero_lh
, mustbe_nonzero_lh
;
3727 wide_int maybe_nonzero_rh
, mustbe_nonzero_rh
;
3728 wi_set_zero_nonzero_bits (type
, lh_lb
, lh_ub
,
3729 maybe_nonzero_lh
, mustbe_nonzero_lh
);
3730 wi_set_zero_nonzero_bits (type
, rh_lb
, rh_ub
,
3731 maybe_nonzero_rh
, mustbe_nonzero_rh
);
3733 wide_int result_zero_bits
= ((mustbe_nonzero_lh
& mustbe_nonzero_rh
)
3734 | ~(maybe_nonzero_lh
| maybe_nonzero_rh
));
3735 wide_int result_one_bits
3736 = (wi::bit_and_not (mustbe_nonzero_lh
, maybe_nonzero_rh
)
3737 | wi::bit_and_not (mustbe_nonzero_rh
, maybe_nonzero_lh
));
3738 wide_int new_ub
= ~result_zero_bits
;
3739 wide_int new_lb
= result_one_bits
;
3741 // If the range has all positive or all negative values, the result
3742 // is better than VARYING.
3743 if (wi::lt_p (new_lb
, 0, sign
) || wi::ge_p (new_ub
, 0, sign
))
3744 value_range_with_overflow (r
, type
, new_lb
, new_ub
);
3745 else if (sign
== SIGNED
3746 && wi_optimize_signed_bitwise_op (r
, type
,
3751 r
.set_varying (type
);
3753 /* Furthermore, XOR is non-zero if its arguments can't be equal. */
3754 if (wi::lt_p (lh_ub
, rh_lb
, sign
)
3755 || wi::lt_p (rh_ub
, lh_lb
, sign
)
3756 || wi::ne_p (result_one_bits
, 0))
3759 tmp
.set_nonzero (type
);
3765 operator_bitwise_xor::op1_op2_relation_effect (irange
&lhs_range
,
3769 relation_kind rel
) const
3771 if (rel
== VREL_VARYING
)
3774 int_range
<2> rel_range
;
3779 rel_range
.set_zero (type
);
3782 rel_range
.set_nonzero (type
);
3788 lhs_range
.intersect (rel_range
);
3793 operator_bitwise_xor::op1_range (irange
&r
, tree type
,
3796 relation_trio
) const
3798 if (lhs
.undefined_p () || lhs
.varying_p ())
3803 if (types_compatible_p (type
, boolean_type_node
))
3805 switch (get_bool_state (r
, lhs
, type
))
3808 if (op2
.varying_p ())
3809 r
.set_varying (type
);
3810 else if (op2
.zero_p ())
3811 r
= range_true (type
);
3812 // See get_bool_state for the rationale
3813 else if (op2
.undefined_p () || contains_zero_p (op2
))
3814 r
= range_true_and_false (type
);
3816 r
= range_false (type
);
3826 r
.set_varying (type
);
3831 operator_bitwise_xor::op2_range (irange
&r
, tree type
,
3834 relation_trio
) const
3836 return operator_bitwise_xor::op1_range (r
, type
, lhs
, op1
);
3839 class operator_trunc_mod
: public range_operator
3841 using range_operator::op1_range
;
3842 using range_operator::op2_range
;
3844 virtual void wi_fold (irange
&r
, tree type
,
3845 const wide_int
&lh_lb
,
3846 const wide_int
&lh_ub
,
3847 const wide_int
&rh_lb
,
3848 const wide_int
&rh_ub
) const;
3849 virtual bool op1_range (irange
&r
, tree type
,
3852 relation_trio
) const;
3853 virtual bool op2_range (irange
&r
, tree type
,
3856 relation_trio
) const;
3857 void update_bitmask (irange
&r
, const irange
&lh
, const irange
&rh
) const
3858 { update_known_bitmask (r
, TRUNC_MOD_EXPR
, lh
, rh
); }
3862 operator_trunc_mod::wi_fold (irange
&r
, tree type
,
3863 const wide_int
&lh_lb
,
3864 const wide_int
&lh_ub
,
3865 const wide_int
&rh_lb
,
3866 const wide_int
&rh_ub
) const
3868 wide_int new_lb
, new_ub
, tmp
;
3869 signop sign
= TYPE_SIGN (type
);
3870 unsigned prec
= TYPE_PRECISION (type
);
3872 // Mod 0 is undefined.
3873 if (wi_zero_p (type
, rh_lb
, rh_ub
))
3879 // Check for constant and try to fold.
3880 if (lh_lb
== lh_ub
&& rh_lb
== rh_ub
)
3882 wi::overflow_type ov
= wi::OVF_NONE
;
3883 tmp
= wi::mod_trunc (lh_lb
, rh_lb
, sign
, &ov
);
3884 if (ov
== wi::OVF_NONE
)
3886 r
= int_range
<2> (type
, tmp
, tmp
);
3891 // ABS (A % B) < ABS (B) and either 0 <= A % B <= A or A <= A % B <= 0.
3896 new_ub
= wi::smax (new_ub
, tmp
);
3899 if (sign
== UNSIGNED
)
3900 new_lb
= wi::zero (prec
);
3905 if (wi::gts_p (tmp
, 0))
3906 tmp
= wi::zero (prec
);
3907 new_lb
= wi::smax (new_lb
, tmp
);
3910 if (sign
== SIGNED
&& wi::neg_p (tmp
))
3911 tmp
= wi::zero (prec
);
3912 new_ub
= wi::min (new_ub
, tmp
, sign
);
3914 value_range_with_overflow (r
, type
, new_lb
, new_ub
);
3918 operator_trunc_mod::op1_range (irange
&r
, tree type
,
3921 relation_trio
) const
3923 if (lhs
.undefined_p ())
3926 signop sign
= TYPE_SIGN (type
);
3927 unsigned prec
= TYPE_PRECISION (type
);
3928 // (a % b) >= x && x > 0 , then a >= x.
3929 if (wi::gt_p (lhs
.lower_bound (), 0, sign
))
3931 r
= value_range (type
, lhs
.lower_bound (), wi::max_value (prec
, sign
));
3934 // (a % b) <= x && x < 0 , then a <= x.
3935 if (wi::lt_p (lhs
.upper_bound (), 0, sign
))
3937 r
= value_range (type
, wi::min_value (prec
, sign
), lhs
.upper_bound ());
3944 operator_trunc_mod::op2_range (irange
&r
, tree type
,
3947 relation_trio
) const
3949 if (lhs
.undefined_p ())
3952 signop sign
= TYPE_SIGN (type
);
3953 unsigned prec
= TYPE_PRECISION (type
);
3954 // (a % b) >= x && x > 0 , then b is in ~[-x, x] for signed
3955 // or b > x for unsigned.
3956 if (wi::gt_p (lhs
.lower_bound (), 0, sign
))
3959 r
= value_range (type
, wi::neg (lhs
.lower_bound ()),
3960 lhs
.lower_bound (), VR_ANTI_RANGE
);
3961 else if (wi::lt_p (lhs
.lower_bound (), wi::max_value (prec
, sign
),
3963 r
= value_range (type
, lhs
.lower_bound () + 1,
3964 wi::max_value (prec
, sign
));
3969 // (a % b) <= x && x < 0 , then b is in ~[x, -x].
3970 if (wi::lt_p (lhs
.upper_bound (), 0, sign
))
3972 if (wi::gt_p (lhs
.upper_bound (), wi::min_value (prec
, sign
), sign
))
3973 r
= value_range (type
, lhs
.upper_bound (),
3974 wi::neg (lhs
.upper_bound ()), VR_ANTI_RANGE
);
3983 class operator_logical_not
: public range_operator
3985 using range_operator::fold_range
;
3986 using range_operator::op1_range
;
3988 virtual bool fold_range (irange
&r
, tree type
,
3991 relation_trio rel
= TRIO_VARYING
) const;
3992 virtual bool op1_range (irange
&r
, tree type
,
3995 relation_trio rel
= TRIO_VARYING
) const;
3998 // Folding a logical NOT, oddly enough, involves doing nothing on the
3999 // forward pass through. During the initial walk backwards, the
4000 // logical NOT reversed the desired outcome on the way back, so on the
4001 // way forward all we do is pass the range forward.
4006 // to determine the TRUE branch, walking backward
4007 // if (b_3) if ([1,1])
4008 // b_3 = !b_2 [1,1] = ![0,0]
4009 // b_2 = x_1 < 20 [0,0] = x_1 < 20, false, so x_1 == [20, 255]
4010 // which is the result we are looking for.. so.. pass it through.
4013 operator_logical_not::fold_range (irange
&r
, tree type
,
4015 const irange
&rh ATTRIBUTE_UNUSED
,
4016 relation_trio
) const
4018 if (empty_range_varying (r
, type
, lh
, rh
))
4022 if (!lh
.varying_p () && !lh
.undefined_p ())
4029 operator_logical_not::op1_range (irange
&r
,
4033 relation_trio
) const
4035 // Logical NOT is involutary...do it again.
4036 return fold_range (r
, type
, lhs
, op2
);
4041 operator_bitwise_not::fold_range (irange
&r
, tree type
,
4044 relation_trio
) const
4046 if (empty_range_varying (r
, type
, lh
, rh
))
4049 if (types_compatible_p (type
, boolean_type_node
))
4050 return op_logical_not
.fold_range (r
, type
, lh
, rh
);
4052 // ~X is simply -1 - X.
4053 int_range
<1> minusone (type
, wi::minus_one (TYPE_PRECISION (type
)),
4054 wi::minus_one (TYPE_PRECISION (type
)));
4055 return range_op_handler (MINUS_EXPR
).fold_range (r
, type
, minusone
, lh
);
4059 operator_bitwise_not::op1_range (irange
&r
, tree type
,
4062 relation_trio
) const
4064 if (lhs
.undefined_p ())
4066 if (types_compatible_p (type
, boolean_type_node
))
4067 return op_logical_not
.op1_range (r
, type
, lhs
, op2
);
4069 // ~X is -1 - X and since bitwise NOT is involutary...do it again.
4070 return fold_range (r
, type
, lhs
, op2
);
4074 operator_bitwise_not::update_bitmask (irange
&r
, const irange
&lh
,
4075 const irange
&rh
) const
4077 update_known_bitmask (r
, BIT_NOT_EXPR
, lh
, rh
);
4082 operator_cst::fold_range (irange
&r
, tree type ATTRIBUTE_UNUSED
,
4084 const irange
&rh ATTRIBUTE_UNUSED
,
4085 relation_trio
) const
4092 // Determine if there is a relationship between LHS and OP1.
4095 operator_identity::lhs_op1_relation (const irange
&lhs
,
4096 const irange
&op1 ATTRIBUTE_UNUSED
,
4097 const irange
&op2 ATTRIBUTE_UNUSED
,
4098 relation_kind
) const
4100 if (lhs
.undefined_p ())
4101 return VREL_VARYING
;
4102 // Simply a copy, so they are equivalent.
4107 operator_identity::fold_range (irange
&r
, tree type ATTRIBUTE_UNUSED
,
4109 const irange
&rh ATTRIBUTE_UNUSED
,
4110 relation_trio
) const
4117 operator_identity::op1_range (irange
&r
, tree type ATTRIBUTE_UNUSED
,
4119 const irange
&op2 ATTRIBUTE_UNUSED
,
4120 relation_trio
) const
4127 class operator_unknown
: public range_operator
4129 using range_operator::fold_range
;
4131 virtual bool fold_range (irange
&r
, tree type
,
4134 relation_trio rel
= TRIO_VARYING
) const;
4138 operator_unknown::fold_range (irange
&r
, tree type
,
4139 const irange
&lh ATTRIBUTE_UNUSED
,
4140 const irange
&rh ATTRIBUTE_UNUSED
,
4141 relation_trio
) const
4143 r
.set_varying (type
);
4149 operator_abs::wi_fold (irange
&r
, tree type
,
4150 const wide_int
&lh_lb
, const wide_int
&lh_ub
,
4151 const wide_int
&rh_lb ATTRIBUTE_UNUSED
,
4152 const wide_int
&rh_ub ATTRIBUTE_UNUSED
) const
4155 signop sign
= TYPE_SIGN (type
);
4156 unsigned prec
= TYPE_PRECISION (type
);
4158 // Pass through LH for the easy cases.
4159 if (sign
== UNSIGNED
|| wi::ge_p (lh_lb
, 0, sign
))
4161 r
= int_range
<1> (type
, lh_lb
, lh_ub
);
4165 // -TYPE_MIN_VALUE = TYPE_MIN_VALUE with flag_wrapv so we can't get
4167 wide_int min_value
= wi::min_value (prec
, sign
);
4168 wide_int max_value
= wi::max_value (prec
, sign
);
4169 if (!TYPE_OVERFLOW_UNDEFINED (type
) && wi::eq_p (lh_lb
, min_value
))
4171 r
.set_varying (type
);
4175 // ABS_EXPR may flip the range around, if the original range
4176 // included negative values.
4177 if (wi::eq_p (lh_lb
, min_value
))
4179 // ABS ([-MIN, -MIN]) isn't representable, but we have traditionally
4180 // returned [-MIN,-MIN] so this preserves that behavior. PR37078
4181 if (wi::eq_p (lh_ub
, min_value
))
4183 r
= int_range
<1> (type
, min_value
, min_value
);
4189 min
= wi::abs (lh_lb
);
4191 if (wi::eq_p (lh_ub
, min_value
))
4194 max
= wi::abs (lh_ub
);
4196 // If the range contains zero then we know that the minimum value in the
4197 // range will be zero.
4198 if (wi::le_p (lh_lb
, 0, sign
) && wi::ge_p (lh_ub
, 0, sign
))
4200 if (wi::gt_p (min
, max
, sign
))
4202 min
= wi::zero (prec
);
4206 // If the range was reversed, swap MIN and MAX.
4207 if (wi::gt_p (min
, max
, sign
))
4208 std::swap (min
, max
);
4211 // If the new range has its limits swapped around (MIN > MAX), then
4212 // the operation caused one of them to wrap around. The only thing
4213 // we know is that the result is positive.
4214 if (wi::gt_p (min
, max
, sign
))
4216 min
= wi::zero (prec
);
4219 r
= int_range
<1> (type
, min
, max
);
4223 operator_abs::op1_range (irange
&r
, tree type
,
4226 relation_trio
) const
4228 if (empty_range_varying (r
, type
, lhs
, op2
))
4230 if (TYPE_UNSIGNED (type
))
4235 // Start with the positives because negatives are an impossible result.
4236 int_range_max positives
= range_positives (type
);
4237 positives
.intersect (lhs
);
4239 // Then add the negative of each pair:
4240 // ABS(op1) = [5,20] would yield op1 => [-20,-5][5,20].
4241 for (unsigned i
= 0; i
< positives
.num_pairs (); ++i
)
4242 r
.union_ (int_range
<1> (type
,
4243 -positives
.upper_bound (i
),
4244 -positives
.lower_bound (i
)));
4245 // With flag_wrapv, -TYPE_MIN_VALUE = TYPE_MIN_VALUE which is
4246 // unrepresentable. Add -TYPE_MIN_VALUE in this case.
4247 wide_int min_value
= wi::min_value (TYPE_PRECISION (type
), TYPE_SIGN (type
));
4248 wide_int lb
= lhs
.lower_bound ();
4249 if (!TYPE_OVERFLOW_UNDEFINED (type
) && wi::eq_p (lb
, min_value
))
4250 r
.union_ (int_range
<2> (type
, lb
, lb
));
4255 operator_abs::update_bitmask (irange
&r
, const irange
&lh
,
4256 const irange
&rh
) const
4258 update_known_bitmask (r
, ABS_EXPR
, lh
, rh
);
4261 class operator_absu
: public range_operator
4264 virtual void wi_fold (irange
&r
, tree type
,
4265 const wide_int
&lh_lb
, const wide_int
&lh_ub
,
4266 const wide_int
&rh_lb
, const wide_int
&rh_ub
) const;
4267 virtual void update_bitmask (irange
&r
, const irange
&lh
,
4268 const irange
&rh
) const final override
;
4272 operator_absu::wi_fold (irange
&r
, tree type
,
4273 const wide_int
&lh_lb
, const wide_int
&lh_ub
,
4274 const wide_int
&rh_lb ATTRIBUTE_UNUSED
,
4275 const wide_int
&rh_ub ATTRIBUTE_UNUSED
) const
4277 wide_int new_lb
, new_ub
;
4279 // Pass through VR0 the easy cases.
4280 if (wi::ges_p (lh_lb
, 0))
4287 new_lb
= wi::abs (lh_lb
);
4288 new_ub
= wi::abs (lh_ub
);
4290 // If the range contains zero then we know that the minimum
4291 // value in the range will be zero.
4292 if (wi::ges_p (lh_ub
, 0))
4294 if (wi::gtu_p (new_lb
, new_ub
))
4296 new_lb
= wi::zero (TYPE_PRECISION (type
));
4299 std::swap (new_lb
, new_ub
);
4302 gcc_checking_assert (TYPE_UNSIGNED (type
));
4303 r
= int_range
<1> (type
, new_lb
, new_ub
);
4307 operator_absu::update_bitmask (irange
&r
, const irange
&lh
,
4308 const irange
&rh
) const
4310 update_known_bitmask (r
, ABSU_EXPR
, lh
, rh
);
4315 operator_negate::fold_range (irange
&r
, tree type
,
4318 relation_trio
) const
4320 if (empty_range_varying (r
, type
, lh
, rh
))
4322 // -X is simply 0 - X.
4323 return range_op_handler (MINUS_EXPR
).fold_range (r
, type
,
4324 range_zero (type
), lh
);
4328 operator_negate::op1_range (irange
&r
, tree type
,
4331 relation_trio
) const
4333 // NEGATE is involutory.
4334 return fold_range (r
, type
, lhs
, op2
);
4339 operator_addr_expr::fold_range (irange
&r
, tree type
,
4342 relation_trio
) const
4344 if (empty_range_varying (r
, type
, lh
, rh
))
4347 // Return a non-null pointer of the LHS type (passed in op2).
4349 r
= range_zero (type
);
4350 else if (lh
.undefined_p () || contains_zero_p (lh
))
4351 r
.set_varying (type
);
4353 r
.set_nonzero (type
);
4358 operator_addr_expr::op1_range (irange
&r
, tree type
,
4361 relation_trio
) const
4363 if (empty_range_varying (r
, type
, lhs
, op2
))
4366 // Return a non-null pointer of the LHS type (passed in op2), but only
4367 // if we cant overflow, eitherwise a no-zero offset could wrap to zero.
4369 if (!lhs
.undefined_p () && !contains_zero_p (lhs
) && TYPE_OVERFLOW_UNDEFINED (type
))
4370 r
.set_nonzero (type
);
4372 r
.set_varying (type
);
4376 // Initialize any integral operators to the primary table
4379 range_op_table::initialize_integral_ops ()
4381 set (TRUNC_DIV_EXPR
, op_trunc_div
);
4382 set (FLOOR_DIV_EXPR
, op_floor_div
);
4383 set (ROUND_DIV_EXPR
, op_round_div
);
4384 set (CEIL_DIV_EXPR
, op_ceil_div
);
4385 set (EXACT_DIV_EXPR
, op_exact_div
);
4386 set (LSHIFT_EXPR
, op_lshift
);
4387 set (RSHIFT_EXPR
, op_rshift
);
4388 set (TRUTH_AND_EXPR
, op_logical_and
);
4389 set (TRUTH_OR_EXPR
, op_logical_or
);
4390 set (TRUNC_MOD_EXPR
, op_trunc_mod
);
4391 set (TRUTH_NOT_EXPR
, op_logical_not
);
4392 set (IMAGPART_EXPR
, op_unknown
);
4393 set (REALPART_EXPR
, op_unknown
);
4394 set (ABSU_EXPR
, op_absu
);
4395 set (OP_WIDEN_MULT_SIGNED
, op_widen_mult_signed
);
4396 set (OP_WIDEN_MULT_UNSIGNED
, op_widen_mult_unsigned
);
4397 set (OP_WIDEN_PLUS_SIGNED
, op_widen_plus_signed
);
4398 set (OP_WIDEN_PLUS_UNSIGNED
, op_widen_plus_unsigned
);
4403 operator_plus::overflow_free_p (const irange
&lh
, const irange
&rh
,
4404 relation_trio
) const
4406 if (lh
.undefined_p () || rh
.undefined_p ())
4409 tree type
= lh
.type ();
4410 if (TYPE_OVERFLOW_UNDEFINED (type
))
4413 wi::overflow_type ovf
;
4414 signop sgn
= TYPE_SIGN (type
);
4415 wide_int wmax0
= lh
.upper_bound ();
4416 wide_int wmax1
= rh
.upper_bound ();
4417 wi::add (wmax0
, wmax1
, sgn
, &ovf
);
4418 if (ovf
!= wi::OVF_NONE
)
4421 if (TYPE_UNSIGNED (type
))
4424 wide_int wmin0
= lh
.lower_bound ();
4425 wide_int wmin1
= rh
.lower_bound ();
4426 wi::add (wmin0
, wmin1
, sgn
, &ovf
);
4427 if (ovf
!= wi::OVF_NONE
)
4434 operator_minus::overflow_free_p (const irange
&lh
, const irange
&rh
,
4435 relation_trio
) const
4437 if (lh
.undefined_p () || rh
.undefined_p ())
4440 tree type
= lh
.type ();
4441 if (TYPE_OVERFLOW_UNDEFINED (type
))
4444 wi::overflow_type ovf
;
4445 signop sgn
= TYPE_SIGN (type
);
4446 wide_int wmin0
= lh
.lower_bound ();
4447 wide_int wmax1
= rh
.upper_bound ();
4448 wi::sub (wmin0
, wmax1
, sgn
, &ovf
);
4449 if (ovf
!= wi::OVF_NONE
)
4452 if (TYPE_UNSIGNED (type
))
4455 wide_int wmax0
= lh
.upper_bound ();
4456 wide_int wmin1
= rh
.lower_bound ();
4457 wi::sub (wmax0
, wmin1
, sgn
, &ovf
);
4458 if (ovf
!= wi::OVF_NONE
)
4465 operator_mult::overflow_free_p (const irange
&lh
, const irange
&rh
,
4466 relation_trio
) const
4468 if (lh
.undefined_p () || rh
.undefined_p ())
4471 tree type
= lh
.type ();
4472 if (TYPE_OVERFLOW_UNDEFINED (type
))
4475 wi::overflow_type ovf
;
4476 signop sgn
= TYPE_SIGN (type
);
4477 wide_int wmax0
= lh
.upper_bound ();
4478 wide_int wmax1
= rh
.upper_bound ();
4479 wi::mul (wmax0
, wmax1
, sgn
, &ovf
);
4480 if (ovf
!= wi::OVF_NONE
)
4483 if (TYPE_UNSIGNED (type
))
4486 wide_int wmin0
= lh
.lower_bound ();
4487 wide_int wmin1
= rh
.lower_bound ();
4488 wi::mul (wmin0
, wmin1
, sgn
, &ovf
);
4489 if (ovf
!= wi::OVF_NONE
)
4492 wi::mul (wmin0
, wmax1
, sgn
, &ovf
);
4493 if (ovf
!= wi::OVF_NONE
)
4496 wi::mul (wmax0
, wmin1
, sgn
, &ovf
);
4497 if (ovf
!= wi::OVF_NONE
)
4504 #include "selftest.h"
4508 #define INT(x) wi::shwi ((x), TYPE_PRECISION (integer_type_node))
4509 #define UINT(x) wi::uhwi ((x), TYPE_PRECISION (unsigned_type_node))
4510 #define INT16(x) wi::shwi ((x), TYPE_PRECISION (short_integer_type_node))
4511 #define UINT16(x) wi::uhwi ((x), TYPE_PRECISION (short_unsigned_type_node))
4512 #define SCHAR(x) wi::shwi ((x), TYPE_PRECISION (signed_char_type_node))
4513 #define UCHAR(x) wi::uhwi ((x), TYPE_PRECISION (unsigned_char_type_node))
4516 range_op_cast_tests ()
4518 int_range
<2> r0
, r1
, r2
, rold
;
4519 r0
.set_varying (integer_type_node
);
4520 wide_int maxint
= r0
.upper_bound ();
4522 // If a range is in any way outside of the range for the converted
4523 // to range, default to the range for the new type.
4524 r0
.set_varying (short_integer_type_node
);
4525 wide_int minshort
= r0
.lower_bound ();
4526 wide_int maxshort
= r0
.upper_bound ();
4527 if (TYPE_PRECISION (integer_type_node
)
4528 > TYPE_PRECISION (short_integer_type_node
))
4530 r1
= int_range
<1> (integer_type_node
,
4531 wi::zero (TYPE_PRECISION (integer_type_node
)),
4533 range_cast (r1
, short_integer_type_node
);
4534 ASSERT_TRUE (r1
.lower_bound () == minshort
4535 && r1
.upper_bound() == maxshort
);
4538 // (unsigned char)[-5,-1] => [251,255].
4539 r0
= rold
= int_range
<1> (signed_char_type_node
, SCHAR (-5), SCHAR (-1));
4540 range_cast (r0
, unsigned_char_type_node
);
4541 ASSERT_TRUE (r0
== int_range
<1> (unsigned_char_type_node
,
4542 UCHAR (251), UCHAR (255)));
4543 range_cast (r0
, signed_char_type_node
);
4544 ASSERT_TRUE (r0
== rold
);
4546 // (signed char)[15, 150] => [-128,-106][15,127].
4547 r0
= rold
= int_range
<1> (unsigned_char_type_node
, UCHAR (15), UCHAR (150));
4548 range_cast (r0
, signed_char_type_node
);
4549 r1
= int_range
<1> (signed_char_type_node
, SCHAR (15), SCHAR (127));
4550 r2
= int_range
<1> (signed_char_type_node
, SCHAR (-128), SCHAR (-106));
4552 ASSERT_TRUE (r1
== r0
);
4553 range_cast (r0
, unsigned_char_type_node
);
4554 ASSERT_TRUE (r0
== rold
);
4556 // (unsigned char)[-5, 5] => [0,5][251,255].
4557 r0
= rold
= int_range
<1> (signed_char_type_node
, SCHAR (-5), SCHAR (5));
4558 range_cast (r0
, unsigned_char_type_node
);
4559 r1
= int_range
<1> (unsigned_char_type_node
, UCHAR (251), UCHAR (255));
4560 r2
= int_range
<1> (unsigned_char_type_node
, UCHAR (0), UCHAR (5));
4562 ASSERT_TRUE (r0
== r1
);
4563 range_cast (r0
, signed_char_type_node
);
4564 ASSERT_TRUE (r0
== rold
);
4566 // (unsigned char)[-5,5] => [0,5][251,255].
4567 r0
= int_range
<1> (integer_type_node
, INT (-5), INT (5));
4568 range_cast (r0
, unsigned_char_type_node
);
4569 r1
= int_range
<1> (unsigned_char_type_node
, UCHAR (0), UCHAR (5));
4570 r1
.union_ (int_range
<1> (unsigned_char_type_node
, UCHAR (251), UCHAR (255)));
4571 ASSERT_TRUE (r0
== r1
);
4573 // (unsigned char)[5U,1974U] => [0,255].
4574 r0
= int_range
<1> (unsigned_type_node
, UINT (5), UINT (1974));
4575 range_cast (r0
, unsigned_char_type_node
);
4576 ASSERT_TRUE (r0
== int_range
<1> (unsigned_char_type_node
, UCHAR (0), UCHAR (255)));
4577 range_cast (r0
, integer_type_node
);
4578 // Going to a wider range should not sign extend.
4579 ASSERT_TRUE (r0
== int_range
<1> (integer_type_node
, INT (0), INT (255)));
4581 // (unsigned char)[-350,15] => [0,255].
4582 r0
= int_range
<1> (integer_type_node
, INT (-350), INT (15));
4583 range_cast (r0
, unsigned_char_type_node
);
4584 ASSERT_TRUE (r0
== (int_range
<1>
4585 (unsigned_char_type_node
,
4586 min_limit (unsigned_char_type_node
),
4587 max_limit (unsigned_char_type_node
))));
4589 // Casting [-120,20] from signed char to unsigned short.
4590 // => [0, 20][0xff88, 0xffff].
4591 r0
= int_range
<1> (signed_char_type_node
, SCHAR (-120), SCHAR (20));
4592 range_cast (r0
, short_unsigned_type_node
);
4593 r1
= int_range
<1> (short_unsigned_type_node
, UINT16 (0), UINT16 (20));
4594 r2
= int_range
<1> (short_unsigned_type_node
,
4595 UINT16 (0xff88), UINT16 (0xffff));
4597 ASSERT_TRUE (r0
== r1
);
4598 // A truncating cast back to signed char will work because [-120, 20]
4599 // is representable in signed char.
4600 range_cast (r0
, signed_char_type_node
);
4601 ASSERT_TRUE (r0
== int_range
<1> (signed_char_type_node
,
4602 SCHAR (-120), SCHAR (20)));
4604 // unsigned char -> signed short
4605 // (signed short)[(unsigned char)25, (unsigned char)250]
4606 // => [(signed short)25, (signed short)250]
4607 r0
= rold
= int_range
<1> (unsigned_char_type_node
, UCHAR (25), UCHAR (250));
4608 range_cast (r0
, short_integer_type_node
);
4609 r1
= int_range
<1> (short_integer_type_node
, INT16 (25), INT16 (250));
4610 ASSERT_TRUE (r0
== r1
);
4611 range_cast (r0
, unsigned_char_type_node
);
4612 ASSERT_TRUE (r0
== rold
);
4614 // Test casting a wider signed [-MIN,MAX] to a narrower unsigned.
4615 r0
= int_range
<1> (long_long_integer_type_node
,
4616 min_limit (long_long_integer_type_node
),
4617 max_limit (long_long_integer_type_node
));
4618 range_cast (r0
, short_unsigned_type_node
);
4619 r1
= int_range
<1> (short_unsigned_type_node
,
4620 min_limit (short_unsigned_type_node
),
4621 max_limit (short_unsigned_type_node
));
4622 ASSERT_TRUE (r0
== r1
);
4624 // Casting NONZERO to a narrower type will wrap/overflow so
4625 // it's just the entire range for the narrower type.
4627 // "NOT 0 at signed 32-bits" ==> [-MIN_32,-1][1, +MAX_32]. This is
4628 // is outside of the range of a smaller range, return the full
4630 if (TYPE_PRECISION (integer_type_node
)
4631 > TYPE_PRECISION (short_integer_type_node
))
4633 r0
= range_nonzero (integer_type_node
);
4634 range_cast (r0
, short_integer_type_node
);
4635 r1
= int_range
<1> (short_integer_type_node
,
4636 min_limit (short_integer_type_node
),
4637 max_limit (short_integer_type_node
));
4638 ASSERT_TRUE (r0
== r1
);
4641 // Casting NONZERO from a narrower signed to a wider signed.
4643 // NONZERO signed 16-bits is [-MIN_16,-1][1, +MAX_16].
4644 // Converting this to 32-bits signed is [-MIN_16,-1][1, +MAX_16].
4645 r0
= range_nonzero (short_integer_type_node
);
4646 range_cast (r0
, integer_type_node
);
4647 r1
= int_range
<1> (integer_type_node
, INT (-32768), INT (-1));
4648 r2
= int_range
<1> (integer_type_node
, INT (1), INT (32767));
4650 ASSERT_TRUE (r0
== r1
);
4654 range_op_lshift_tests ()
4656 // Test that 0x808.... & 0x8.... still contains 0x8....
4657 // for a large set of numbers.
4660 tree big_type
= long_long_unsigned_type_node
;
4661 unsigned big_prec
= TYPE_PRECISION (big_type
);
4662 // big_num = 0x808,0000,0000,0000
4663 wide_int big_num
= wi::lshift (wi::uhwi (0x808, big_prec
),
4664 wi::uhwi (48, big_prec
));
4665 op_bitwise_and
.fold_range (res
, big_type
,
4666 int_range
<1> (big_type
),
4667 int_range
<1> (big_type
, big_num
, big_num
));
4668 // val = 0x8,0000,0000,0000
4669 wide_int val
= wi::lshift (wi::uhwi (8, big_prec
),
4670 wi::uhwi (48, big_prec
));
4671 ASSERT_TRUE (res
.contains_p (val
));
4674 if (TYPE_PRECISION (unsigned_type_node
) > 31)
4676 // unsigned VARYING = op1 << 1 should be VARYING.
4677 int_range
<2> lhs (unsigned_type_node
);
4678 int_range
<2> shift (unsigned_type_node
, INT (1), INT (1));
4680 op_lshift
.op1_range (op1
, unsigned_type_node
, lhs
, shift
);
4681 ASSERT_TRUE (op1
.varying_p ());
4683 // 0 = op1 << 1 should be [0,0], [0x8000000, 0x8000000].
4684 int_range
<2> zero (unsigned_type_node
, UINT (0), UINT (0));
4685 op_lshift
.op1_range (op1
, unsigned_type_node
, zero
, shift
);
4686 ASSERT_TRUE (op1
.num_pairs () == 2);
4687 // Remove the [0,0] range.
4688 op1
.intersect (zero
);
4689 ASSERT_TRUE (op1
.num_pairs () == 1);
4690 // op1 << 1 should be [0x8000,0x8000] << 1,
4691 // which should result in [0,0].
4692 int_range_max result
;
4693 op_lshift
.fold_range (result
, unsigned_type_node
, op1
, shift
);
4694 ASSERT_TRUE (result
== zero
);
4696 // signed VARYING = op1 << 1 should be VARYING.
4697 if (TYPE_PRECISION (integer_type_node
) > 31)
4699 // unsigned VARYING = op1 << 1 should be VARYING.
4700 int_range
<2> lhs (integer_type_node
);
4701 int_range
<2> shift (integer_type_node
, INT (1), INT (1));
4703 op_lshift
.op1_range (op1
, integer_type_node
, lhs
, shift
);
4704 ASSERT_TRUE (op1
.varying_p ());
4706 // 0 = op1 << 1 should be [0,0], [0x8000000, 0x8000000].
4707 int_range
<2> zero (integer_type_node
, INT (0), INT (0));
4708 op_lshift
.op1_range (op1
, integer_type_node
, zero
, shift
);
4709 ASSERT_TRUE (op1
.num_pairs () == 2);
4710 // Remove the [0,0] range.
4711 op1
.intersect (zero
);
4712 ASSERT_TRUE (op1
.num_pairs () == 1);
4713 // op1 << 1 should be [0x8000,0x8000] << 1,
4714 // which should result in [0,0].
4715 int_range_max result
;
4716 op_lshift
.fold_range (result
, unsigned_type_node
, op1
, shift
);
4717 ASSERT_TRUE (result
== zero
);
4722 range_op_rshift_tests ()
4724 // unsigned: [3, MAX] = OP1 >> 1
4726 int_range_max
lhs (unsigned_type_node
,
4727 UINT (3), max_limit (unsigned_type_node
));
4728 int_range_max
one (unsigned_type_node
,
4729 wi::one (TYPE_PRECISION (unsigned_type_node
)),
4730 wi::one (TYPE_PRECISION (unsigned_type_node
)));
4732 op_rshift
.op1_range (op1
, unsigned_type_node
, lhs
, one
);
4733 ASSERT_FALSE (op1
.contains_p (UINT (3)));
4736 // signed: [3, MAX] = OP1 >> 1
4738 int_range_max
lhs (integer_type_node
,
4739 INT (3), max_limit (integer_type_node
));
4740 int_range_max
one (integer_type_node
, INT (1), INT (1));
4742 op_rshift
.op1_range (op1
, integer_type_node
, lhs
, one
);
4743 ASSERT_FALSE (op1
.contains_p (INT (-2)));
4746 // This is impossible, so OP1 should be [].
4747 // signed: [MIN, MIN] = OP1 >> 1
4749 int_range_max
lhs (integer_type_node
,
4750 min_limit (integer_type_node
),
4751 min_limit (integer_type_node
));
4752 int_range_max
one (integer_type_node
, INT (1), INT (1));
4754 op_rshift
.op1_range (op1
, integer_type_node
, lhs
, one
);
4755 ASSERT_TRUE (op1
.undefined_p ());
4758 // signed: ~[-1] = OP1 >> 31
4759 if (TYPE_PRECISION (integer_type_node
) > 31)
4761 int_range_max
lhs (integer_type_node
, INT (-1), INT (-1), VR_ANTI_RANGE
);
4762 int_range_max
shift (integer_type_node
, INT (31), INT (31));
4764 op_rshift
.op1_range (op1
, integer_type_node
, lhs
, shift
);
4765 int_range_max negatives
= range_negatives (integer_type_node
);
4766 negatives
.intersect (op1
);
4767 ASSERT_TRUE (negatives
.undefined_p ());
4772 range_op_bitwise_and_tests ()
4775 wide_int min
= min_limit (integer_type_node
);
4776 wide_int max
= max_limit (integer_type_node
);
4777 wide_int tiny
= wi::add (min
, wi::one (TYPE_PRECISION (integer_type_node
)));
4778 int_range_max
i1 (integer_type_node
, tiny
, max
);
4779 int_range_max
i2 (integer_type_node
, INT (255), INT (255));
4781 // [MIN+1, MAX] = OP1 & 255: OP1 is VARYING
4782 op_bitwise_and
.op1_range (res
, integer_type_node
, i1
, i2
);
4783 ASSERT_TRUE (res
== int_range
<1> (integer_type_node
));
4785 // VARYING = OP1 & 255: OP1 is VARYING
4786 i1
= int_range
<1> (integer_type_node
);
4787 op_bitwise_and
.op1_range (res
, integer_type_node
, i1
, i2
);
4788 ASSERT_TRUE (res
== int_range
<1> (integer_type_node
));
4790 // For 0 = x & MASK, x is ~MASK.
4792 int_range
<2> zero (integer_type_node
, INT (0), INT (0));
4793 int_range
<2> mask
= int_range
<2> (integer_type_node
, INT (7), INT (7));
4794 op_bitwise_and
.op1_range (res
, integer_type_node
, zero
, mask
);
4795 wide_int inv
= wi::shwi (~7U, TYPE_PRECISION (integer_type_node
));
4796 ASSERT_TRUE (res
.get_nonzero_bits () == inv
);
4799 // (NONZERO | X) is nonzero.
4800 i1
.set_nonzero (integer_type_node
);
4801 i2
.set_varying (integer_type_node
);
4802 op_bitwise_or
.fold_range (res
, integer_type_node
, i1
, i2
);
4803 ASSERT_TRUE (res
.nonzero_p ());
4805 // (NEGATIVE | X) is nonzero.
4806 i1
= int_range
<1> (integer_type_node
, INT (-5), INT (-3));
4807 i2
.set_varying (integer_type_node
);
4808 op_bitwise_or
.fold_range (res
, integer_type_node
, i1
, i2
);
4809 ASSERT_FALSE (res
.contains_p (INT (0)));
4813 range_relational_tests ()
4815 int_range
<2> lhs (unsigned_char_type_node
);
4816 int_range
<2> op1 (unsigned_char_type_node
, UCHAR (8), UCHAR (10));
4817 int_range
<2> op2 (unsigned_char_type_node
, UCHAR (20), UCHAR (20));
4819 // Never wrapping additions mean LHS > OP1.
4820 relation_kind code
= op_plus
.lhs_op1_relation (lhs
, op1
, op2
, VREL_VARYING
);
4821 ASSERT_TRUE (code
== VREL_GT
);
4823 // Most wrapping additions mean nothing...
4824 op1
= int_range
<2> (unsigned_char_type_node
, UCHAR (8), UCHAR (10));
4825 op2
= int_range
<2> (unsigned_char_type_node
, UCHAR (0), UCHAR (255));
4826 code
= op_plus
.lhs_op1_relation (lhs
, op1
, op2
, VREL_VARYING
);
4827 ASSERT_TRUE (code
== VREL_VARYING
);
4829 // However, always wrapping additions mean LHS < OP1.
4830 op1
= int_range
<2> (unsigned_char_type_node
, UCHAR (1), UCHAR (255));
4831 op2
= int_range
<2> (unsigned_char_type_node
, UCHAR (255), UCHAR (255));
4832 code
= op_plus
.lhs_op1_relation (lhs
, op1
, op2
, VREL_VARYING
);
4833 ASSERT_TRUE (code
== VREL_LT
);
4839 range_op_rshift_tests ();
4840 range_op_lshift_tests ();
4841 range_op_bitwise_and_tests ();
4842 range_op_cast_tests ();
4843 range_relational_tests ();
4845 extern void range_op_float_tests ();
4846 range_op_float_tests ();
4849 } // namespace selftest
4851 #endif // CHECKING_P