Branch data Line data Source code
1 : : /* Code for range operators.
2 : : Copyright (C) 2017-2024 Free Software Foundation, Inc.
3 : : Contributed by Andrew MacLeod <amacleod@redhat.com>
4 : : and Aldy Hernandez <aldyh@redhat.com>.
5 : :
6 : : This file is part of GCC.
7 : :
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)
11 : : any later version.
12 : :
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.
17 : :
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/>. */
21 : :
22 : : #include "config.h"
23 : : #include "system.h"
24 : : #include "coretypes.h"
25 : : #include "backend.h"
26 : : #include "insn-codes.h"
27 : : #include "rtl.h"
28 : : #include "tree.h"
29 : : #include "gimple.h"
30 : : #include "cfghooks.h"
31 : : #include "tree-pass.h"
32 : : #include "ssa.h"
33 : : #include "optabs-tree.h"
34 : : #include "gimple-pretty-print.h"
35 : : #include "diagnostic-core.h"
36 : : #include "flags.h"
37 : : #include "fold-const.h"
38 : : #include "stor-layout.h"
39 : : #include "calls.h"
40 : : #include "cfganal.h"
41 : : #include "gimple-iterator.h"
42 : : #include "gimple-fold.h"
43 : : #include "tree-eh.h"
44 : : #include "gimple-walk.h"
45 : : #include "tree-cfg.h"
46 : : #include "wide-int.h"
47 : : #include "value-relation.h"
48 : : #include "range-op.h"
49 : : #include "tree-ssa-ccp.h"
50 : : #include "range-op-mixed.h"
51 : :
52 : : // Instantiate the operators which apply to multiple types here.
53 : :
54 : : operator_equal op_equal;
55 : : operator_not_equal op_not_equal;
56 : : operator_lt op_lt;
57 : : operator_le op_le;
58 : : operator_gt op_gt;
59 : : operator_ge op_ge;
60 : : operator_identity op_ident;
61 : : operator_cst op_cst;
62 : : operator_cast op_cast;
63 : : operator_plus op_plus;
64 : : operator_abs op_abs;
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;
73 : : operator_min op_min;
74 : : operator_max op_max;
75 : :
76 : : // Instantaite a range operator table.
77 : : range_op_table operator_table;
78 : :
79 : : // Invoke the initialization routines for each class of range.
80 : :
81 : 280913 : range_op_table::range_op_table ()
82 : : {
83 : 280913 : initialize_integral_ops ();
84 : 280913 : initialize_pointer_ops ();
85 : 280913 : initialize_float_ops ();
86 : :
87 : 280913 : set (EQ_EXPR, op_equal);
88 : 280913 : set (NE_EXPR, op_not_equal);
89 : 280913 : set (LT_EXPR, op_lt);
90 : 280913 : set (LE_EXPR, op_le);
91 : 280913 : set (GT_EXPR, op_gt);
92 : 280913 : set (GE_EXPR, op_ge);
93 : 280913 : set (SSA_NAME, op_ident);
94 : 280913 : set (PAREN_EXPR, op_ident);
95 : 280913 : set (OBJ_TYPE_REF, op_ident);
96 : 280913 : set (REAL_CST, op_cst);
97 : 280913 : set (INTEGER_CST, op_cst);
98 : 280913 : set (NOP_EXPR, op_cast);
99 : 280913 : set (CONVERT_EXPR, op_cast);
100 : 280913 : set (PLUS_EXPR, op_plus);
101 : 280913 : set (ABS_EXPR, op_abs);
102 : 280913 : set (MINUS_EXPR, op_minus);
103 : 280913 : set (NEGATE_EXPR, op_negate);
104 : 280913 : set (MULT_EXPR, op_mult);
105 : :
106 : : // Occur in both integer and pointer tables, but currently share
107 : : // integral implementation.
108 : 280913 : set (ADDR_EXPR, op_addr);
109 : 280913 : set (BIT_NOT_EXPR, op_bitwise_not);
110 : 280913 : set (BIT_XOR_EXPR, op_bitwise_xor);
111 : :
112 : : // These are in both integer and pointer tables, but pointer has a different
113 : : // implementation.
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.
117 : :
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);
122 : 280913 : }
123 : :
124 : : // Instantiate a default range operator for opcodes with no entry.
125 : :
126 : : range_operator default_operator;
127 : :
128 : : // Create a default range_op_handler.
129 : :
130 : 696554813 : range_op_handler::range_op_handler ()
131 : : {
132 : 696554813 : m_operator = &default_operator;
133 : 696554813 : }
134 : :
135 : : // Create a range_op_handler for CODE. Use a default operatoer if CODE
136 : : // does not have an entry.
137 : :
138 : 1535323357 : range_op_handler::range_op_handler (unsigned code)
139 : : {
140 : 1535323357 : m_operator = operator_table[code];
141 : 1535323357 : if (!m_operator)
142 : 379504708 : m_operator = &default_operator;
143 : 1535323357 : }
144 : :
145 : : // Return TRUE if this handler has a non-default operator.
146 : :
147 : 2344056711 : range_op_handler::operator bool () const
148 : : {
149 : 2344056711 : return m_operator != &default_operator;
150 : : }
151 : :
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.
155 : :
156 : : range_operator *
157 : 407230350 : range_op_handler::range_op () const
158 : : {
159 : 407230350 : if (m_operator != &default_operator)
160 : 407230350 : return m_operator;
161 : : return NULL;
162 : : }
163 : :
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.
167 : :
168 : : constexpr unsigned
169 : 480486129 : dispatch_trio (unsigned lhs, unsigned op1, unsigned op2)
170 : : {
171 : 480486129 : return ((lhs << 8) + (op1 << 4) + (op2));
172 : : }
173 : :
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.
177 : :
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);
184 : :
185 : : // Return a dispatch value for parameter types LHS, OP1 and OP2.
186 : :
187 : : unsigned
188 : 480486129 : range_op_handler::dispatch_kind (const vrange &lhs, const vrange &op1,
189 : : const vrange& op2) const
190 : : {
191 : 480486129 : return dispatch_trio (lhs.m_discriminator, op1.m_discriminator,
192 : 480486129 : op2.m_discriminator);
193 : : }
194 : :
195 : : // Dispatch a call to fold_range based on the types of R, LH and RH.
196 : :
197 : : bool
198 : 219398725 : range_op_handler::fold_range (vrange &r, tree type,
199 : : const vrange &lh,
200 : : const vrange &rh,
201 : : relation_trio rel) const
202 : : {
203 : 219398725 : gcc_checking_assert (m_operator);
204 : : #if CHECKING_P
205 : 219398725 : if (!lh.undefined_p () && !rh.undefined_p ())
206 : 219248319 : gcc_assert (m_operator->operand_check_p (type, lh.type (), rh.type ()));
207 : : #endif
208 : 219398725 : switch (dispatch_kind (r, lh, rh))
209 : : {
210 : 209262757 : case RO_III:
211 : 209262757 : return m_operator->fold_range (as_a <irange> (r), type,
212 : : as_a <irange> (lh),
213 : 209262757 : as_a <irange> (rh), rel);
214 : 40643 : case RO_IFI:
215 : 40643 : return m_operator->fold_range (as_a <irange> (r), type,
216 : : as_a <frange> (lh),
217 : 40643 : as_a <irange> (rh), rel);
218 : 3390632 : case RO_IFF:
219 : 3390632 : return m_operator->fold_range (as_a <irange> (r), type,
220 : : as_a <frange> (lh),
221 : 3390632 : as_a <frange> (rh), rel);
222 : 6704693 : case RO_FFF:
223 : 6704693 : return m_operator->fold_range (as_a <frange> (r), type,
224 : : as_a <frange> (lh),
225 : 6704693 : as_a <frange> (rh), rel);
226 : 0 : case RO_FII:
227 : 0 : return m_operator->fold_range (as_a <frange> (r), type,
228 : : as_a <irange> (lh),
229 : 0 : as_a <irange> (rh), rel);
230 : : default:
231 : : return false;
232 : : }
233 : : }
234 : :
235 : : // Dispatch a call to op1_range based on the types of R, LHS and OP2.
236 : :
237 : : bool
238 : 62508886 : range_op_handler::op1_range (vrange &r, tree type,
239 : : const vrange &lhs,
240 : : const vrange &op2,
241 : : relation_trio rel) const
242 : : {
243 : 62508886 : gcc_checking_assert (m_operator);
244 : 62508886 : if (lhs.undefined_p ())
245 : : return false;
246 : : #if CHECKING_P
247 : 62508865 : if (!op2.undefined_p ())
248 : 62508815 : gcc_assert (m_operator->operand_check_p (lhs.type (), type, op2.type ()));
249 : : #endif
250 : 62508865 : switch (dispatch_kind (r, lhs, op2))
251 : : {
252 : 60910522 : case RO_III:
253 : 60910522 : return m_operator->op1_range (as_a <irange> (r), type,
254 : : as_a <irange> (lhs),
255 : 60910522 : as_a <irange> (op2), rel);
256 : 1132610 : case RO_FIF:
257 : 1132610 : return m_operator->op1_range (as_a <frange> (r), type,
258 : : as_a <irange> (lhs),
259 : 1132610 : as_a <frange> (op2), rel);
260 : 465733 : case RO_FFF:
261 : 465733 : return m_operator->op1_range (as_a <frange> (r), type,
262 : : as_a <frange> (lhs),
263 : 465733 : as_a <frange> (op2), rel);
264 : : default:
265 : : return false;
266 : : }
267 : : }
268 : :
269 : : // Dispatch a call to op2_range based on the types of R, LHS and OP1.
270 : :
271 : : bool
272 : 17898591 : range_op_handler::op2_range (vrange &r, tree type,
273 : : const vrange &lhs,
274 : : const vrange &op1,
275 : : relation_trio rel) const
276 : : {
277 : 17898591 : gcc_checking_assert (m_operator);
278 : 17898591 : if (lhs.undefined_p ())
279 : : return false;
280 : : #if CHECKING_P
281 : 17898583 : if (!op1.undefined_p ())
282 : 17898555 : gcc_assert (m_operator->operand_check_p (lhs.type (), op1.type (), type));
283 : : #endif
284 : 17898583 : switch (dispatch_kind (r, lhs, op1))
285 : : {
286 : 17477442 : case RO_III:
287 : 17477442 : return m_operator->op2_range (as_a <irange> (r), type,
288 : : as_a <irange> (lhs),
289 : 17477442 : as_a <irange> (op1), rel);
290 : 285082 : case RO_FIF:
291 : 285082 : return m_operator->op2_range (as_a <frange> (r), type,
292 : : as_a <irange> (lhs),
293 : 285082 : as_a <frange> (op1), rel);
294 : 136059 : case RO_FFF:
295 : 136059 : return m_operator->op2_range (as_a <frange> (r), type,
296 : : as_a <frange> (lhs),
297 : 136059 : as_a <frange> (op1), rel);
298 : : default:
299 : : return false;
300 : : }
301 : : }
302 : :
303 : : // Dispatch a call to lhs_op1_relation based on the types of LHS, OP1 and OP2.
304 : :
305 : : relation_kind
306 : 94363111 : range_op_handler::lhs_op1_relation (const vrange &lhs,
307 : : const vrange &op1,
308 : : const vrange &op2,
309 : : relation_kind rel) const
310 : : {
311 : 94363111 : gcc_checking_assert (m_operator);
312 : :
313 : 94363111 : switch (dispatch_kind (lhs, op1, op2))
314 : : {
315 : 87929500 : case RO_III:
316 : 87929500 : return m_operator->lhs_op1_relation (as_a <irange> (lhs),
317 : : as_a <irange> (op1),
318 : 87929500 : as_a <irange> (op2), rel);
319 : 1117725 : case RO_IFF:
320 : 1117725 : return m_operator->lhs_op1_relation (as_a <irange> (lhs),
321 : : as_a <frange> (op1),
322 : 1117725 : as_a <frange> (op2), rel);
323 : 5315886 : case RO_FFF:
324 : 5315886 : return m_operator->lhs_op1_relation (as_a <frange> (lhs),
325 : : as_a <frange> (op1),
326 : 5315886 : as_a <frange> (op2), rel);
327 : : default:
328 : : return VREL_VARYING;
329 : : }
330 : : }
331 : :
332 : : // Dispatch a call to lhs_op2_relation based on the types of LHS, OP1 and OP2.
333 : :
334 : : relation_kind
335 : 28277906 : range_op_handler::lhs_op2_relation (const vrange &lhs,
336 : : const vrange &op1,
337 : : const vrange &op2,
338 : : relation_kind rel) const
339 : : {
340 : 28277906 : gcc_checking_assert (m_operator);
341 : 28277906 : switch (dispatch_kind (lhs, op1, op2))
342 : : {
343 : 24856790 : case RO_III:
344 : 24856790 : return m_operator->lhs_op2_relation (as_a <irange> (lhs),
345 : : as_a <irange> (op1),
346 : 24856790 : as_a <irange> (op2), rel);
347 : 156089 : case RO_IFF:
348 : 156089 : return m_operator->lhs_op2_relation (as_a <irange> (lhs),
349 : : as_a <frange> (op1),
350 : 156089 : as_a <frange> (op2), rel);
351 : 3265027 : case RO_FFF:
352 : 3265027 : return m_operator->lhs_op2_relation (as_a <frange> (lhs),
353 : : as_a <frange> (op1),
354 : 3265027 : as_a <frange> (op2), rel);
355 : : default:
356 : : return VREL_VARYING;
357 : : }
358 : : }
359 : :
360 : : // Dispatch a call to op1_op2_relation based on the type of LHS.
361 : :
362 : : relation_kind
363 : 57931440 : range_op_handler::op1_op2_relation (const vrange &lhs,
364 : : const vrange &op1,
365 : : const vrange &op2) const
366 : : {
367 : 57931440 : gcc_checking_assert (m_operator);
368 : 57931440 : switch (dispatch_kind (lhs, op1, op2))
369 : : {
370 : 56386114 : case RO_III:
371 : 56386114 : return m_operator->op1_op2_relation (as_a <irange> (lhs),
372 : : as_a <irange> (op1),
373 : 56386114 : as_a <irange> (op2));
374 : :
375 : 1244287 : case RO_IFF:
376 : 1244287 : return m_operator->op1_op2_relation (as_a <irange> (lhs),
377 : : as_a <frange> (op1),
378 : 1244287 : as_a <frange> (op2));
379 : :
380 : 301039 : case RO_FFF:
381 : 301039 : return m_operator->op1_op2_relation (as_a <frange> (lhs),
382 : : as_a <frange> (op1),
383 : 301039 : as_a <frange> (op2));
384 : :
385 : : default:
386 : : return VREL_VARYING;
387 : : }
388 : : }
389 : :
390 : : bool
391 : 107499 : range_op_handler::overflow_free_p (const vrange &lh,
392 : : const vrange &rh,
393 : : relation_trio rel) const
394 : : {
395 : 107499 : gcc_checking_assert (m_operator);
396 : 107499 : switch (dispatch_kind (lh, lh, rh))
397 : : {
398 : 107499 : case RO_III:
399 : 107499 : return m_operator->overflow_free_p(as_a <irange> (lh),
400 : : as_a <irange> (rh),
401 : 107499 : rel);
402 : : default:
403 : : return false;
404 : : }
405 : : }
406 : :
407 : : bool
408 : 7099803 : range_op_handler::operand_check_p (tree t1, tree t2, tree t3) const
409 : : {
410 : 7099803 : gcc_checking_assert (m_operator);
411 : 7099803 : return m_operator->operand_check_p (t1, t2, t3);
412 : : }
413 : :
414 : : // Update the known bitmasks in R when applying the operation CODE to
415 : : // LH and RH.
416 : :
417 : : void
418 : 141840962 : update_known_bitmask (irange &r, tree_code code,
419 : : const irange &lh, const irange &rh)
420 : : {
421 : 141840962 : if (r.undefined_p () || lh.undefined_p () || rh.undefined_p ()
422 : 283678529 : || r.singleton_p ())
423 : 9440120 : return;
424 : :
425 : 132400842 : widest_int widest_value, widest_mask;
426 : 132400842 : tree type = r.type ();
427 : 132400842 : signop sign = TYPE_SIGN (type);
428 : 132400842 : int prec = TYPE_PRECISION (type);
429 : 132400842 : irange_bitmask lh_bits = lh.get_bitmask ();
430 : 132400842 : irange_bitmask rh_bits = rh.get_bitmask ();
431 : :
432 : 132400842 : switch (get_gimple_rhs_class (code))
433 : : {
434 : 55473931 : case GIMPLE_UNARY_RHS:
435 : 55473931 : bit_value_unop (code, sign, prec, &widest_value, &widest_mask,
436 : 55473931 : TYPE_SIGN (lh.type ()),
437 : 55473931 : TYPE_PRECISION (lh.type ()),
438 : 110948316 : widest_int::from (lh_bits.value (),
439 : 55473931 : TYPE_SIGN (lh.type ())),
440 : 110947862 : widest_int::from (lh_bits.mask (),
441 : 55473931 : TYPE_SIGN (lh.type ())));
442 : 55473931 : break;
443 : 76926911 : case GIMPLE_BINARY_RHS:
444 : 153853822 : bit_value_binop (code, sign, prec, &widest_value, &widest_mask,
445 : 76926911 : TYPE_SIGN (lh.type ()),
446 : 76926911 : TYPE_PRECISION (lh.type ()),
447 : 153854541 : widest_int::from (lh_bits.value (), sign),
448 : 153854541 : widest_int::from (lh_bits.mask (), sign),
449 : 76926911 : TYPE_SIGN (rh.type ()),
450 : 76926911 : TYPE_PRECISION (rh.type ()),
451 : 153854528 : widest_int::from (rh_bits.value (), sign),
452 : 153853822 : widest_int::from (rh_bits.mask (), sign));
453 : 76926911 : break;
454 : 0 : default:
455 : 0 : gcc_unreachable ();
456 : : }
457 : :
458 : 132400842 : wide_int mask = wide_int::from (widest_mask, prec, sign);
459 : 264801684 : wide_int value = wide_int::from (widest_value, prec, sign);
460 : : // Bitmasks must have the unknown value bits cleared.
461 : 132400842 : value &= ~mask;
462 : 264801684 : irange_bitmask bm (value, mask);
463 : 132400842 : r.update_bitmask (bm);
464 : 132401761 : }
465 : :
466 : : // Return the upper limit for a type.
467 : :
468 : : static inline wide_int
469 : 11637811 : max_limit (const_tree type)
470 : : {
471 : 11637811 : return irange_val_max (type);
472 : : }
473 : :
474 : : // Return the lower limit for a type.
475 : :
476 : : static inline wide_int
477 : 13052158 : min_limit (const_tree type)
478 : : {
479 : 13052158 : return irange_val_min (type);
480 : : }
481 : :
482 : : // Return false if shifting by OP is undefined behavior. Otherwise, return
483 : : // true and the range it is to be shifted by. This allows trimming out of
484 : : // undefined ranges, leaving only valid ranges if there are any.
485 : :
486 : : static inline bool
487 : 3865675 : get_shift_range (irange &r, tree type, const irange &op)
488 : : {
489 : 3865675 : if (op.undefined_p ())
490 : : return false;
491 : :
492 : : // Build valid range and intersect it with the shift range.
493 : 7730712 : r = value_range (op.type (),
494 : 7730712 : wi::shwi (0, TYPE_PRECISION (op.type ())),
495 : 7730712 : wi::shwi (TYPE_PRECISION (type) - 1, TYPE_PRECISION (op.type ())));
496 : 3865356 : r.intersect (op);
497 : :
498 : : // If there are no valid ranges in the shift range, returned false.
499 : 3865356 : if (r.undefined_p ())
500 : : return false;
501 : : return true;
502 : : }
503 : :
504 : : // Default wide_int fold operation returns [MIN, MAX].
505 : :
506 : : void
507 : 1655782 : range_operator::wi_fold (irange &r, tree type,
508 : : const wide_int &lh_lb ATTRIBUTE_UNUSED,
509 : : const wide_int &lh_ub ATTRIBUTE_UNUSED,
510 : : const wide_int &rh_lb ATTRIBUTE_UNUSED,
511 : : const wide_int &rh_ub ATTRIBUTE_UNUSED) const
512 : : {
513 : 1655782 : gcc_checking_assert (r.supports_type_p (type));
514 : 1655782 : r.set_varying (type);
515 : 1655782 : }
516 : :
517 : : // Call wi_fold when both op1 and op2 are equivalent. Further split small
518 : : // subranges into constants. This can provide better precision.
519 : : // For x + y, when x == y with a range of [0,4] instead of [0, 8] produce
520 : : // [0,0][2, 2][4,4][6, 6][8, 8]
521 : : // LIMIT is the maximum number of elements in range allowed before we
522 : : // do not process them individually.
523 : :
524 : : void
525 : 46714 : range_operator::wi_fold_in_parts_equiv (irange &r, tree type,
526 : : const wide_int &lh_lb,
527 : : const wide_int &lh_ub,
528 : : unsigned limit) const
529 : : {
530 : 46714 : int_range_max tmp;
531 : 93428 : widest_int lh_range = wi::sub (widest_int::from (lh_ub, TYPE_SIGN (type)),
532 : 93428 : widest_int::from (lh_lb, TYPE_SIGN (type)));
533 : : // if there are 1 to 8 values in the LH range, split them up.
534 : 46714 : r.set_undefined ();
535 : 91439 : if (lh_range >= 0 && lh_range < limit)
536 : : {
537 : 12124 : for (unsigned x = 0; x <= lh_range; x++)
538 : : {
539 : 8406 : wide_int val = lh_lb + x;
540 : 8406 : wi_fold (tmp, type, val, val, val, val);
541 : 8406 : r.union_ (tmp);
542 : 8406 : }
543 : : }
544 : : // Otherwise just call wi_fold.
545 : : else
546 : 42996 : wi_fold (r, type, lh_lb, lh_ub, lh_lb, lh_ub);
547 : 46714 : }
548 : :
549 : : // Call wi_fold, except further split small subranges into constants.
550 : : // This can provide better precision. For something 8 >> [0,1]
551 : : // Instead of [8, 16], we will produce [8,8][16,16]
552 : :
553 : : void
554 : 106594826 : range_operator::wi_fold_in_parts (irange &r, tree type,
555 : : const wide_int &lh_lb,
556 : : const wide_int &lh_ub,
557 : : const wide_int &rh_lb,
558 : : const wide_int &rh_ub) const
559 : : {
560 : 106594826 : int_range_max tmp;
561 : 213189652 : widest_int rh_range = wi::sub (widest_int::from (rh_ub, TYPE_SIGN (type)),
562 : 213189652 : widest_int::from (rh_lb, TYPE_SIGN (type)));
563 : 213189652 : widest_int lh_range = wi::sub (widest_int::from (lh_ub, TYPE_SIGN (type)),
564 : 213189652 : widest_int::from (lh_lb, TYPE_SIGN (type)));
565 : : // If there are 2, 3, or 4 values in the RH range, do them separately.
566 : : // Call wi_fold_in_parts to check the RH side.
567 : 106594826 : if (rh_range > 0 && rh_range < 4)
568 : : {
569 : 4085398 : wi_fold_in_parts (r, type, lh_lb, lh_ub, rh_lb, rh_lb);
570 : 4085398 : if (rh_range > 1)
571 : : {
572 : 379295 : wi_fold_in_parts (tmp, type, lh_lb, lh_ub, rh_lb + 1, rh_lb + 1);
573 : 379295 : r.union_ (tmp);
574 : 379295 : if (rh_range == 3)
575 : : {
576 : 249300 : wi_fold_in_parts (tmp, type, lh_lb, lh_ub, rh_lb + 2, rh_lb + 2);
577 : 249300 : r.union_ (tmp);
578 : : }
579 : : }
580 : 4085398 : wi_fold_in_parts (tmp, type, lh_lb, lh_ub, rh_ub, rh_ub);
581 : 4085398 : r.union_ (tmp);
582 : : }
583 : : // Otherwise check for 2, 3, or 4 values in the LH range and split them up.
584 : : // The RH side has been checked, so no recursion needed.
585 : 102509428 : else if (lh_range > 0 && lh_range < 4)
586 : : {
587 : 8538078 : wi_fold (r, type, lh_lb, lh_lb, rh_lb, rh_ub);
588 : 8538078 : if (lh_range > 1)
589 : : {
590 : 1417724 : wi_fold (tmp, type, lh_lb + 1, lh_lb + 1, rh_lb, rh_ub);
591 : 1417712 : r.union_ (tmp);
592 : 1417712 : if (lh_range == 3)
593 : : {
594 : 577920 : wi_fold (tmp, type, lh_lb + 2, lh_lb + 2, rh_lb, rh_ub);
595 : 577914 : r.union_ (tmp);
596 : : }
597 : : }
598 : 8538078 : wi_fold (tmp, type, lh_ub, lh_ub, rh_lb, rh_ub);
599 : 8538078 : r.union_ (tmp);
600 : : }
601 : : // Otherwise just call wi_fold.
602 : : else
603 : 93971350 : wi_fold (r, type, lh_lb, lh_ub, rh_lb, rh_ub);
604 : 106595047 : }
605 : :
606 : : // The default for fold is to break all ranges into sub-ranges and
607 : : // invoke the wi_fold method on each sub-range pair.
608 : :
609 : : bool
610 : 83357079 : range_operator::fold_range (irange &r, tree type,
611 : : const irange &lh,
612 : : const irange &rh,
613 : : relation_trio trio) const
614 : : {
615 : 83357079 : gcc_checking_assert (r.supports_type_p (type));
616 : 83357079 : if (empty_range_varying (r, type, lh, rh))
617 : 38479 : return true;
618 : :
619 : 83318600 : relation_kind rel = trio.op1_op2 ();
620 : 83318600 : unsigned num_lh = lh.num_pairs ();
621 : 83318600 : unsigned num_rh = rh.num_pairs ();
622 : :
623 : : // If op1 and op2 are equivalences, then we don't need a complete cross
624 : : // product, just pairs of matching elements.
625 : 83318928 : if (relation_equiv_p (rel) && lh == rh)
626 : : {
627 : 43862 : int_range_max tmp;
628 : 43862 : r.set_undefined ();
629 : 78181 : for (unsigned x = 0; x < num_lh; ++x)
630 : : {
631 : : // If the number of subranges is too high, limit subrange creation.
632 : 46714 : unsigned limit = (r.num_pairs () > 32) ? 0 : 8;
633 : 46714 : wide_int lh_lb = lh.lower_bound (x);
634 : 46714 : wide_int lh_ub = lh.upper_bound (x);
635 : 46714 : wi_fold_in_parts_equiv (tmp, type, lh_lb, lh_ub, limit);
636 : 46714 : r.union_ (tmp);
637 : 46714 : if (r.varying_p ())
638 : : break;
639 : 46714 : }
640 : 43862 : op1_op2_relation_effect (r, type, lh, rh, rel);
641 : 43862 : update_bitmask (r, lh, rh);
642 : 43862 : return true;
643 : 43862 : }
644 : :
645 : : // If both ranges are single pairs, fold directly into the result range.
646 : : // If the number of subranges grows too high, produce a summary result as the
647 : : // loop becomes exponential with little benefit. See PR 103821.
648 : 83274738 : if ((num_lh == 1 && num_rh == 1) || num_lh * num_rh > 12)
649 : : {
650 : 71697239 : wi_fold_in_parts (r, type, lh.lower_bound (), lh.upper_bound (),
651 : 143392830 : rh.lower_bound (), rh.upper_bound ());
652 : 71696415 : op1_op2_relation_effect (r, type, lh, rh, rel);
653 : 71696415 : update_bitmask (r, lh, rh);
654 : 71696415 : return true;
655 : : }
656 : :
657 : 11578323 : int_range_max tmp;
658 : 11578323 : r.set_undefined ();
659 : 29857973 : for (unsigned x = 0; x < num_lh; ++x)
660 : 44378670 : for (unsigned y = 0; y < num_rh; ++y)
661 : : {
662 : 26099020 : wide_int lh_lb = lh.lower_bound (x);
663 : 26099020 : wide_int lh_ub = lh.upper_bound (x);
664 : 26099020 : wide_int rh_lb = rh.lower_bound (y);
665 : 26099020 : wide_int rh_ub = rh.upper_bound (y);
666 : 26099020 : wi_fold_in_parts (tmp, type, lh_lb, lh_ub, rh_lb, rh_ub);
667 : 26099020 : r.union_ (tmp);
668 : 26099020 : if (r.varying_p ())
669 : : {
670 : 3577580 : op1_op2_relation_effect (r, type, lh, rh, rel);
671 : 3577580 : update_bitmask (r, lh, rh);
672 : 3577580 : return true;
673 : : }
674 : 26100058 : }
675 : 8000743 : op1_op2_relation_effect (r, type, lh, rh, rel);
676 : 8000743 : update_bitmask (r, lh, rh);
677 : 8000743 : return true;
678 : 11578323 : }
679 : :
680 : : // The default for op1_range is to return false.
681 : :
682 : : bool
683 : 1181366 : range_operator::op1_range (irange &r ATTRIBUTE_UNUSED,
684 : : tree type ATTRIBUTE_UNUSED,
685 : : const irange &lhs ATTRIBUTE_UNUSED,
686 : : const irange &op2 ATTRIBUTE_UNUSED,
687 : : relation_trio) const
688 : : {
689 : 1181366 : return false;
690 : : }
691 : :
692 : : // The default for op2_range is to return false.
693 : :
694 : : bool
695 : 1063277 : range_operator::op2_range (irange &r ATTRIBUTE_UNUSED,
696 : : tree type ATTRIBUTE_UNUSED,
697 : : const irange &lhs ATTRIBUTE_UNUSED,
698 : : const irange &op1 ATTRIBUTE_UNUSED,
699 : : relation_trio) const
700 : : {
701 : 1063277 : return false;
702 : : }
703 : :
704 : : // The default relation routines return VREL_VARYING.
705 : :
706 : : relation_kind
707 : 28056872 : range_operator::lhs_op1_relation (const irange &lhs ATTRIBUTE_UNUSED,
708 : : const irange &op1 ATTRIBUTE_UNUSED,
709 : : const irange &op2 ATTRIBUTE_UNUSED,
710 : : relation_kind rel ATTRIBUTE_UNUSED) const
711 : : {
712 : 28056872 : return VREL_VARYING;
713 : : }
714 : :
715 : : relation_kind
716 : 19298944 : range_operator::lhs_op2_relation (const irange &lhs ATTRIBUTE_UNUSED,
717 : : const irange &op1 ATTRIBUTE_UNUSED,
718 : : const irange &op2 ATTRIBUTE_UNUSED,
719 : : relation_kind rel ATTRIBUTE_UNUSED) const
720 : : {
721 : 19298944 : return VREL_VARYING;
722 : : }
723 : :
724 : : relation_kind
725 : 11772479 : range_operator::op1_op2_relation (const irange &lhs ATTRIBUTE_UNUSED,
726 : : const irange &op1 ATTRIBUTE_UNUSED,
727 : : const irange &op2 ATTRIBUTE_UNUSED) const
728 : : {
729 : 11772479 : return VREL_VARYING;
730 : : }
731 : :
732 : : // Default is no relation affects the LHS.
733 : :
734 : : bool
735 : 70535037 : range_operator::op1_op2_relation_effect (irange &lhs_range ATTRIBUTE_UNUSED,
736 : : tree type ATTRIBUTE_UNUSED,
737 : : const irange &op1_range ATTRIBUTE_UNUSED,
738 : : const irange &op2_range ATTRIBUTE_UNUSED,
739 : : relation_kind rel ATTRIBUTE_UNUSED) const
740 : : {
741 : 70535037 : return false;
742 : : }
743 : :
744 : : bool
745 : 0 : range_operator::overflow_free_p (const irange &, const irange &,
746 : : relation_trio) const
747 : : {
748 : 0 : return false;
749 : : }
750 : :
751 : : // Apply any known bitmask updates based on this operator.
752 : :
753 : : void
754 : 14 : range_operator::update_bitmask (irange &, const irange &,
755 : : const irange &) const
756 : : {
757 : 14 : }
758 : :
759 : : // Check that operand types are OK. Default to always OK.
760 : :
761 : : bool
762 : 88650051 : range_operator::operand_check_p (tree, tree, tree) const
763 : : {
764 : 88650051 : return true;
765 : : }
766 : :
767 : : // Create and return a range from a pair of wide-ints that are known
768 : : // to have overflowed (or underflowed).
769 : :
770 : : static void
771 : 31601230 : value_range_from_overflowed_bounds (irange &r, tree type,
772 : : const wide_int &wmin,
773 : : const wide_int &wmax)
774 : : {
775 : 31601230 : const signop sgn = TYPE_SIGN (type);
776 : 31601230 : const unsigned int prec = TYPE_PRECISION (type);
777 : :
778 : 31601230 : wide_int tmin = wide_int::from (wmin, prec, sgn);
779 : 31601230 : wide_int tmax = wide_int::from (wmax, prec, sgn);
780 : :
781 : 31601230 : bool covers = false;
782 : 31601230 : wide_int tem = tmin;
783 : 31601230 : tmin = tmax + 1;
784 : 31601230 : if (wi::cmp (tmin, tmax, sgn) < 0)
785 : 1885211 : covers = true;
786 : 31601230 : tmax = tem - 1;
787 : 31601230 : if (wi::cmp (tmax, tem, sgn) > 0)
788 : : covers = true;
789 : :
790 : : // If the anti-range would cover nothing, drop to varying.
791 : : // Likewise if the anti-range bounds are outside of the types
792 : : // values.
793 : 29608342 : if (covers || wi::cmp (tmin, tmax, sgn) > 0)
794 : 21200693 : r.set_varying (type);
795 : : else
796 : 10400537 : r.set (type, tmin, tmax, VR_ANTI_RANGE);
797 : 31601742 : }
798 : :
799 : : // Create and return a range from a pair of wide-ints. MIN_OVF and
800 : : // MAX_OVF describe any overflow that might have occurred while
801 : : // calculating WMIN and WMAX respectively.
802 : :
803 : : static void
804 : 93921155 : value_range_with_overflow (irange &r, tree type,
805 : : const wide_int &wmin, const wide_int &wmax,
806 : : wi::overflow_type min_ovf = wi::OVF_NONE,
807 : : wi::overflow_type max_ovf = wi::OVF_NONE)
808 : : {
809 : 93921155 : const signop sgn = TYPE_SIGN (type);
810 : 93921155 : const unsigned int prec = TYPE_PRECISION (type);
811 : 150705596 : const bool overflow_wraps = TYPE_OVERFLOW_WRAPS (type);
812 : :
813 : : // For one bit precision if max != min, then the range covers all
814 : : // values.
815 : 106516427 : if (prec == 1 && wi::ne_p (wmax, wmin))
816 : : {
817 : 0 : r.set_varying (type);
818 : 0 : return;
819 : : }
820 : :
821 : 93921155 : if (overflow_wraps)
822 : : {
823 : : // If overflow wraps, truncate the values and adjust the range,
824 : : // kind, and bounds appropriately.
825 : 56784441 : if ((min_ovf != wi::OVF_NONE) == (max_ovf != wi::OVF_NONE))
826 : : {
827 : 39510726 : wide_int tmin = wide_int::from (wmin, prec, sgn);
828 : 39510726 : wide_int tmax = wide_int::from (wmax, prec, sgn);
829 : : // If the limits are swapped, we wrapped around and cover
830 : : // the entire range.
831 : 39510726 : if (wi::gt_p (tmin, tmax, sgn))
832 : 514701 : r.set_varying (type);
833 : : else
834 : : // No overflow or both overflow or underflow. The range
835 : : // kind stays normal.
836 : 38996025 : r.set (type, tmin, tmax);
837 : 39510726 : return;
838 : 39510825 : }
839 : :
840 : 17273715 : if ((min_ovf == wi::OVF_UNDERFLOW && max_ovf == wi::OVF_NONE)
841 : 12485108 : || (max_ovf == wi::OVF_OVERFLOW && min_ovf == wi::OVF_NONE))
842 : 17273715 : value_range_from_overflowed_bounds (r, type, wmin, wmax);
843 : : else
844 : : // Other underflow and/or overflow, drop to VR_VARYING.
845 : 0 : r.set_varying (type);
846 : : }
847 : : else
848 : : {
849 : : // If both bounds either underflowed or overflowed, then the result
850 : : // is undefined.
851 : 37136714 : if ((min_ovf == wi::OVF_OVERFLOW && max_ovf == wi::OVF_OVERFLOW)
852 : 37135198 : || (min_ovf == wi::OVF_UNDERFLOW && max_ovf == wi::OVF_UNDERFLOW))
853 : : {
854 : 3606 : r.set_undefined ();
855 : 3606 : return;
856 : : }
857 : :
858 : : // If overflow does not wrap, saturate to [MIN, MAX].
859 : 37133108 : wide_int new_lb, new_ub;
860 : 37133108 : if (min_ovf == wi::OVF_UNDERFLOW)
861 : 4979865 : new_lb = wi::min_value (prec, sgn);
862 : 32153390 : else if (min_ovf == wi::OVF_OVERFLOW)
863 : 0 : new_lb = wi::max_value (prec, sgn);
864 : : else
865 : 32153390 : new_lb = wmin;
866 : :
867 : 37133108 : if (max_ovf == wi::OVF_UNDERFLOW)
868 : 0 : new_ub = wi::min_value (prec, sgn);
869 : 37133108 : else if (max_ovf == wi::OVF_OVERFLOW)
870 : 9029890 : new_ub = wi::max_value (prec, sgn);
871 : : else
872 : 28103411 : new_ub = wmax;
873 : :
874 : 37133108 : r.set (type, new_lb, new_ub);
875 : 37133585 : }
876 : : }
877 : :
878 : : // Create and return a range from a pair of wide-ints. Canonicalize
879 : : // the case where the bounds are swapped. In which case, we transform
880 : : // [10,5] into [MIN,5][10,MAX].
881 : :
882 : : static inline void
883 : 74615815 : create_possibly_reversed_range (irange &r, tree type,
884 : : const wide_int &new_lb, const wide_int &new_ub)
885 : : {
886 : 74615815 : signop s = TYPE_SIGN (type);
887 : : // If the bounds are swapped, treat the result as if an overflow occurred.
888 : 74615815 : if (wi::gt_p (new_lb, new_ub, s))
889 : 14327515 : value_range_from_overflowed_bounds (r, type, new_lb, new_ub);
890 : : else
891 : : // Otherwise it's just a normal range.
892 : 60288300 : r.set (type, new_lb, new_ub);
893 : 74615815 : }
894 : :
895 : : // Return the summary information about boolean range LHS. If EMPTY/FULL,
896 : : // return the equivalent range for TYPE in R; if FALSE/TRUE, do nothing.
897 : :
898 : : bool_range_state
899 : 58560174 : get_bool_state (vrange &r, const vrange &lhs, tree val_type)
900 : : {
901 : : // If there is no result, then this is unexecutable.
902 : 58560174 : if (lhs.undefined_p ())
903 : : {
904 : 0 : r.set_undefined ();
905 : 0 : return BRS_EMPTY;
906 : : }
907 : :
908 : 58560174 : if (lhs.zero_p ())
909 : : return BRS_FALSE;
910 : :
911 : : // For TRUE, we can't just test for [1,1] because Ada can have
912 : : // multi-bit booleans, and TRUE values can be: [1, MAX], ~[0], etc.
913 : 29413181 : if (lhs.contains_p (build_zero_cst (lhs.type ())))
914 : : {
915 : 144685 : r.set_varying (val_type);
916 : 144685 : return BRS_FULL;
917 : : }
918 : :
919 : : return BRS_TRUE;
920 : : }
921 : :
922 : : // ------------------------------------------------------------------------
923 : :
924 : : void
925 : 0 : operator_equal::update_bitmask (irange &r, const irange &lh,
926 : : const irange &rh) const
927 : : {
928 : 0 : update_known_bitmask (r, EQ_EXPR, lh, rh);
929 : 0 : }
930 : :
931 : : // Check if the LHS range indicates a relation between OP1 and OP2.
932 : :
933 : : relation_kind
934 : 8129828 : operator_equal::op1_op2_relation (const irange &lhs, const irange &,
935 : : const irange &) const
936 : : {
937 : 8129828 : if (lhs.undefined_p ())
938 : : return VREL_UNDEFINED;
939 : :
940 : : // FALSE = op1 == op2 indicates NE_EXPR.
941 : 8129828 : if (lhs.zero_p ())
942 : : return VREL_NE;
943 : :
944 : : // TRUE = op1 == op2 indicates EQ_EXPR.
945 : 3922153 : if (!contains_zero_p (lhs))
946 : 3899837 : return VREL_EQ;
947 : : return VREL_VARYING;
948 : : }
949 : :
950 : : bool
951 : 20965778 : operator_equal::fold_range (irange &r, tree type,
952 : : const irange &op1,
953 : : const irange &op2,
954 : : relation_trio rel) const
955 : : {
956 : 20965778 : if (relop_early_resolve (r, type, op1, op2, rel, VREL_EQ))
957 : : return true;
958 : :
959 : : // We can be sure the values are always equal or not if both ranges
960 : : // consist of a single value, and then compare them.
961 : 20931984 : bool op1_const = wi::eq_p (op1.lower_bound (), op1.upper_bound ());
962 : 20931984 : bool op2_const = wi::eq_p (op2.lower_bound (), op2.upper_bound ());
963 : 20931975 : if (op1_const && op2_const)
964 : : {
965 : 265104 : if (wi::eq_p (op1.lower_bound (), op2.upper_bound()))
966 : 146896 : r = range_true (type);
967 : : else
968 : 118208 : r = range_false (type);
969 : : }
970 : : else
971 : : {
972 : : // If ranges do not intersect, we know the range is not equal,
973 : : // otherwise we don't know anything for sure.
974 : 20666871 : int_range_max tmp = op1;
975 : 20666871 : tmp.intersect (op2);
976 : 20666871 : if (tmp.undefined_p ())
977 : 335632 : r = range_false (type);
978 : : // Check if a constant cannot satisfy the bitmask requirements.
979 : 51475989 : else if (op2_const && !op1.get_bitmask ().member_p (op2.lower_bound ()))
980 : 1140 : r = range_false (type);
981 : 20460645 : else if (op1_const && !op2.get_bitmask ().member_p (op1.lower_bound ()))
982 : 14 : r = range_false (type);
983 : : else
984 : 20330085 : r = range_true_and_false (type);
985 : 20666871 : }
986 : : return true;
987 : : }
988 : :
989 : : bool
990 : 11633270 : operator_equal::op1_range (irange &r, tree type,
991 : : const irange &lhs,
992 : : const irange &op2,
993 : : relation_trio) const
994 : : {
995 : 11633270 : switch (get_bool_state (r, lhs, type))
996 : : {
997 : 3231838 : case BRS_TRUE:
998 : : // If it's true, the result is the same as OP2.
999 : 3231838 : r = op2;
1000 : 3231838 : break;
1001 : :
1002 : 8368550 : case BRS_FALSE:
1003 : : // If the result is false, the only time we know anything is
1004 : : // if OP2 is a constant.
1005 : 8368550 : if (!op2.undefined_p ()
1006 : 25105650 : && wi::eq_p (op2.lower_bound(), op2.upper_bound()))
1007 : : {
1008 : 5643385 : r = op2;
1009 : 5643385 : r.invert ();
1010 : : }
1011 : : else
1012 : 2725165 : r.set_varying (type);
1013 : : break;
1014 : :
1015 : : default:
1016 : : break;
1017 : : }
1018 : 11633270 : return true;
1019 : : }
1020 : :
1021 : : bool
1022 : 2479042 : operator_equal::op2_range (irange &r, tree type,
1023 : : const irange &lhs,
1024 : : const irange &op1,
1025 : : relation_trio rel) const
1026 : : {
1027 : 2479042 : return operator_equal::op1_range (r, type, lhs, op1, rel.swap_op1_op2 ());
1028 : : }
1029 : :
1030 : : // -------------------------------------------------------------------------
1031 : :
1032 : : void
1033 : 0 : operator_not_equal::update_bitmask (irange &r, const irange &lh,
1034 : : const irange &rh) const
1035 : : {
1036 : 0 : update_known_bitmask (r, NE_EXPR, lh, rh);
1037 : 0 : }
1038 : :
1039 : : // Check if the LHS range indicates a relation between OP1 and OP2.
1040 : :
1041 : : relation_kind
1042 : 11910511 : operator_not_equal::op1_op2_relation (const irange &lhs, const irange &,
1043 : : const irange &) const
1044 : : {
1045 : 11910511 : if (lhs.undefined_p ())
1046 : : return VREL_UNDEFINED;
1047 : :
1048 : : // FALSE = op1 != op2 indicates EQ_EXPR.
1049 : 11910511 : if (lhs.zero_p ())
1050 : : return VREL_EQ;
1051 : :
1052 : : // TRUE = op1 != op2 indicates NE_EXPR.
1053 : 6336281 : if (!contains_zero_p (lhs))
1054 : 6298051 : return VREL_NE;
1055 : : return VREL_VARYING;
1056 : : }
1057 : :
1058 : : bool
1059 : 30822589 : operator_not_equal::fold_range (irange &r, tree type,
1060 : : const irange &op1,
1061 : : const irange &op2,
1062 : : relation_trio rel) const
1063 : : {
1064 : 30822589 : if (relop_early_resolve (r, type, op1, op2, rel, VREL_NE))
1065 : : return true;
1066 : :
1067 : : // We can be sure the values are always equal or not if both ranges
1068 : : // consist of a single value, and then compare them.
1069 : 30791023 : bool op1_const = wi::eq_p (op1.lower_bound (), op1.upper_bound ());
1070 : 30791023 : bool op2_const = wi::eq_p (op2.lower_bound (), op2.upper_bound ());
1071 : 30790907 : if (op1_const && op2_const)
1072 : : {
1073 : 956987 : if (wi::ne_p (op1.lower_bound (), op2.upper_bound()))
1074 : 528668 : r = range_true (type);
1075 : : else
1076 : 428317 : r = range_false (type);
1077 : : }
1078 : : else
1079 : : {
1080 : : // If ranges do not intersect, we know the range is not equal,
1081 : : // otherwise we don't know anything for sure.
1082 : 29833922 : int_range_max tmp = op1;
1083 : 29833922 : tmp.intersect (op2);
1084 : 29833922 : if (tmp.undefined_p ())
1085 : 315045 : r = range_true (type);
1086 : : // Check if a constant cannot satisfy the bitmask requirements.
1087 : 75511442 : else if (op2_const && !op1.get_bitmask ().member_p (op2.lower_bound ()))
1088 : 1545 : r = range_true (type);
1089 : 29589758 : else if (op1_const && !op2.get_bitmask ().member_p (op1.lower_bound ()))
1090 : 6 : r = range_true (type);
1091 : : else
1092 : 29517326 : r = range_true_and_false (type);
1093 : 29833922 : }
1094 : : return true;
1095 : : }
1096 : :
1097 : : bool
1098 : 19657474 : operator_not_equal::op1_range (irange &r, tree type,
1099 : : const irange &lhs,
1100 : : const irange &op2,
1101 : : relation_trio) const
1102 : : {
1103 : 19657474 : switch (get_bool_state (r, lhs, type))
1104 : : {
1105 : 12479050 : case BRS_TRUE:
1106 : : // If the result is true, the only time we know anything is if
1107 : : // OP2 is a constant.
1108 : 12479050 : if (!op2.undefined_p ()
1109 : 37437150 : && wi::eq_p (op2.lower_bound(), op2.upper_bound()))
1110 : : {
1111 : 9005506 : r = op2;
1112 : 9005506 : r.invert ();
1113 : : }
1114 : : else
1115 : 3473544 : r.set_varying (type);
1116 : : break;
1117 : :
1118 : 7147638 : case BRS_FALSE:
1119 : : // If it's false, the result is the same as OP2.
1120 : 7147638 : r = op2;
1121 : 7147638 : break;
1122 : :
1123 : : default:
1124 : : break;
1125 : : }
1126 : 19657474 : return true;
1127 : : }
1128 : :
1129 : :
1130 : : bool
1131 : 2931763 : operator_not_equal::op2_range (irange &r, tree type,
1132 : : const irange &lhs,
1133 : : const irange &op1,
1134 : : relation_trio rel) const
1135 : : {
1136 : 2931763 : return operator_not_equal::op1_range (r, type, lhs, op1, rel.swap_op1_op2 ());
1137 : : }
1138 : :
1139 : : // (X < VAL) produces the range of [MIN, VAL - 1].
1140 : :
1141 : : static void
1142 : 4513758 : build_lt (irange &r, tree type, const wide_int &val)
1143 : : {
1144 : 4513758 : wi::overflow_type ov;
1145 : 4513758 : wide_int lim;
1146 : 4513758 : signop sgn = TYPE_SIGN (type);
1147 : :
1148 : : // Signed 1 bit cannot represent 1 for subtraction.
1149 : 4513758 : if (sgn == SIGNED)
1150 : 3014812 : lim = wi::add (val, -1, sgn, &ov);
1151 : : else
1152 : 1498991 : lim = wi::sub (val, 1, sgn, &ov);
1153 : :
1154 : : // If val - 1 underflows, check if X < MIN, which is an empty range.
1155 : 4513758 : if (ov)
1156 : 181 : r.set_undefined ();
1157 : : else
1158 : 4513622 : r = int_range<1> (type, min_limit (type), lim);
1159 : 4513758 : }
1160 : :
1161 : : // (X <= VAL) produces the range of [MIN, VAL].
1162 : :
1163 : : static void
1164 : 8538553 : build_le (irange &r, tree type, const wide_int &val)
1165 : : {
1166 : 8538553 : r = int_range<1> (type, min_limit (type), val);
1167 : 8538553 : }
1168 : :
1169 : : // (X > VAL) produces the range of [VAL + 1, MAX].
1170 : :
1171 : : static void
1172 : 6785073 : build_gt (irange &r, tree type, const wide_int &val)
1173 : : {
1174 : 6785073 : wi::overflow_type ov;
1175 : 6785073 : wide_int lim;
1176 : 6785073 : signop sgn = TYPE_SIGN (type);
1177 : :
1178 : : // Signed 1 bit cannot represent 1 for addition.
1179 : 6785073 : if (sgn == SIGNED)
1180 : 3640971 : lim = wi::sub (val, -1, sgn, &ov);
1181 : : else
1182 : 3144171 : lim = wi::add (val, 1, sgn, &ov);
1183 : : // If val + 1 overflows, check is for X > MAX, which is an empty range.
1184 : 6785073 : if (ov)
1185 : 0 : r.set_undefined ();
1186 : : else
1187 : 6785142 : r = int_range<1> (type, lim, max_limit (type));
1188 : 6785073 : }
1189 : :
1190 : : // (X >= val) produces the range of [VAL, MAX].
1191 : :
1192 : : static void
1193 : 4852710 : build_ge (irange &r, tree type, const wide_int &val)
1194 : : {
1195 : 4852710 : r = int_range<1> (type, val, max_limit (type));
1196 : 4852710 : }
1197 : :
1198 : :
1199 : : void
1200 : 0 : operator_lt::update_bitmask (irange &r, const irange &lh,
1201 : : const irange &rh) const
1202 : : {
1203 : 0 : update_known_bitmask (r, LT_EXPR, lh, rh);
1204 : 0 : }
1205 : :
1206 : : // Check if the LHS range indicates a relation between OP1 and OP2.
1207 : :
1208 : : relation_kind
1209 : 9100566 : operator_lt::op1_op2_relation (const irange &lhs, const irange &,
1210 : : const irange &) const
1211 : : {
1212 : 9100566 : if (lhs.undefined_p ())
1213 : : return VREL_UNDEFINED;
1214 : :
1215 : : // FALSE = op1 < op2 indicates GE_EXPR.
1216 : 9100566 : if (lhs.zero_p ())
1217 : : return VREL_GE;
1218 : :
1219 : : // TRUE = op1 < op2 indicates LT_EXPR.
1220 : 4545027 : if (!contains_zero_p (lhs))
1221 : 4535569 : return VREL_LT;
1222 : : return VREL_VARYING;
1223 : : }
1224 : :
1225 : : bool
1226 : 4403751 : operator_lt::fold_range (irange &r, tree type,
1227 : : const irange &op1,
1228 : : const irange &op2,
1229 : : relation_trio rel) const
1230 : : {
1231 : 4403751 : if (relop_early_resolve (r, type, op1, op2, rel, VREL_LT))
1232 : : return true;
1233 : :
1234 : 4383046 : signop sign = TYPE_SIGN (op1.type ());
1235 : 4383046 : gcc_checking_assert (sign == TYPE_SIGN (op2.type ()));
1236 : :
1237 : 4383082 : if (wi::lt_p (op1.upper_bound (), op2.lower_bound (), sign))
1238 : 20901 : r = range_true (type);
1239 : 4362181 : else if (!wi::lt_p (op1.lower_bound (), op2.upper_bound (), sign))
1240 : 35137 : r = range_false (type);
1241 : : // Use nonzero bits to determine if < 0 is false.
1242 : 5178526 : else if (op2.zero_p () && !wi::neg_p (op1.get_nonzero_bits (), sign))
1243 : 1581 : r = range_false (type);
1244 : : else
1245 : 4325427 : r = range_true_and_false (type);
1246 : : return true;
1247 : : }
1248 : :
1249 : : bool
1250 : 3497647 : operator_lt::op1_range (irange &r, tree type,
1251 : : const irange &lhs,
1252 : : const irange &op2,
1253 : : relation_trio) const
1254 : : {
1255 : 3497647 : if (op2.undefined_p ())
1256 : : return false;
1257 : :
1258 : 3497647 : switch (get_bool_state (r, lhs, type))
1259 : : {
1260 : 1704251 : case BRS_TRUE:
1261 : 1704251 : build_lt (r, type, op2.upper_bound ());
1262 : 1704251 : break;
1263 : :
1264 : 1788024 : case BRS_FALSE:
1265 : 1788024 : build_ge (r, type, op2.lower_bound ());
1266 : 1788024 : break;
1267 : :
1268 : : default:
1269 : : break;
1270 : : }
1271 : : return true;
1272 : : }
1273 : :
1274 : : bool
1275 : 2754416 : operator_lt::op2_range (irange &r, tree type,
1276 : : const irange &lhs,
1277 : : const irange &op1,
1278 : : relation_trio) const
1279 : : {
1280 : 2754416 : if (op1.undefined_p ())
1281 : : return false;
1282 : :
1283 : 2754414 : switch (get_bool_state (r, lhs, type))
1284 : : {
1285 : 1157169 : case BRS_TRUE:
1286 : 1157169 : build_gt (r, type, op1.lower_bound ());
1287 : 1157169 : break;
1288 : :
1289 : 1592555 : case BRS_FALSE:
1290 : 1592555 : build_le (r, type, op1.upper_bound ());
1291 : 1592555 : break;
1292 : :
1293 : : default:
1294 : : break;
1295 : : }
1296 : : return true;
1297 : : }
1298 : :
1299 : :
1300 : : void
1301 : 0 : operator_le::update_bitmask (irange &r, const irange &lh,
1302 : : const irange &rh) const
1303 : : {
1304 : 0 : update_known_bitmask (r, LE_EXPR, lh, rh);
1305 : 0 : }
1306 : :
1307 : : // Check if the LHS range indicates a relation between OP1 and OP2.
1308 : :
1309 : : relation_kind
1310 : 3396579 : operator_le::op1_op2_relation (const irange &lhs, const irange &,
1311 : : const irange &) const
1312 : : {
1313 : 3396579 : if (lhs.undefined_p ())
1314 : : return VREL_UNDEFINED;
1315 : :
1316 : : // FALSE = op1 <= op2 indicates GT_EXPR.
1317 : 3396579 : if (lhs.zero_p ())
1318 : : return VREL_GT;
1319 : :
1320 : : // TRUE = op1 <= op2 indicates LE_EXPR.
1321 : 1949524 : if (!contains_zero_p (lhs))
1322 : 1941291 : return VREL_LE;
1323 : : return VREL_VARYING;
1324 : : }
1325 : :
1326 : : bool
1327 : 4017074 : operator_le::fold_range (irange &r, tree type,
1328 : : const irange &op1,
1329 : : const irange &op2,
1330 : : relation_trio rel) const
1331 : : {
1332 : 4017074 : if (relop_early_resolve (r, type, op1, op2, rel, VREL_LE))
1333 : : return true;
1334 : :
1335 : 4007204 : signop sign = TYPE_SIGN (op1.type ());
1336 : 4007204 : gcc_checking_assert (sign == TYPE_SIGN (op2.type ()));
1337 : :
1338 : 4007204 : if (wi::le_p (op1.upper_bound (), op2.lower_bound (), sign))
1339 : 71566 : r = range_true (type);
1340 : 3935638 : else if (!wi::le_p (op1.lower_bound (), op2.upper_bound (), sign))
1341 : 36312 : r = range_false (type);
1342 : : else
1343 : 3899326 : r = range_true_and_false (type);
1344 : : return true;
1345 : : }
1346 : :
1347 : : bool
1348 : 3917666 : operator_le::op1_range (irange &r, tree type,
1349 : : const irange &lhs,
1350 : : const irange &op2,
1351 : : relation_trio) const
1352 : : {
1353 : 3917666 : if (op2.undefined_p ())
1354 : : return false;
1355 : :
1356 : 3917666 : switch (get_bool_state (r, lhs, type))
1357 : : {
1358 : 2136057 : case BRS_TRUE:
1359 : 2136057 : build_le (r, type, op2.upper_bound ());
1360 : 2136057 : break;
1361 : :
1362 : 1771218 : case BRS_FALSE:
1363 : 1771218 : build_gt (r, type, op2.lower_bound ());
1364 : 1771218 : break;
1365 : :
1366 : : default:
1367 : : break;
1368 : : }
1369 : : return true;
1370 : : }
1371 : :
1372 : : bool
1373 : 879653 : operator_le::op2_range (irange &r, tree type,
1374 : : const irange &lhs,
1375 : : const irange &op1,
1376 : : relation_trio) const
1377 : : {
1378 : 879653 : if (op1.undefined_p ())
1379 : : return false;
1380 : :
1381 : 879653 : switch (get_bool_state (r, lhs, type))
1382 : : {
1383 : 409503 : case BRS_TRUE:
1384 : 409503 : build_ge (r, type, op1.lower_bound ());
1385 : 409503 : break;
1386 : :
1387 : 466525 : case BRS_FALSE:
1388 : 466525 : build_lt (r, type, op1.upper_bound ());
1389 : 466525 : break;
1390 : :
1391 : : default:
1392 : : break;
1393 : : }
1394 : : return true;
1395 : : }
1396 : :
1397 : :
1398 : : void
1399 : 0 : operator_gt::update_bitmask (irange &r, const irange &lh,
1400 : : const irange &rh) const
1401 : : {
1402 : 0 : update_known_bitmask (r, GT_EXPR, lh, rh);
1403 : 0 : }
1404 : :
1405 : : // Check if the LHS range indicates a relation between OP1 and OP2.
1406 : :
1407 : : relation_kind
1408 : 8952435 : operator_gt::op1_op2_relation (const irange &lhs, const irange &,
1409 : : const irange &) const
1410 : : {
1411 : 8952435 : if (lhs.undefined_p ())
1412 : : return VREL_UNDEFINED;
1413 : :
1414 : : // FALSE = op1 > op2 indicates LE_EXPR.
1415 : 8952435 : if (lhs.zero_p ())
1416 : : return VREL_LE;
1417 : :
1418 : : // TRUE = op1 > op2 indicates GT_EXPR.
1419 : 4664583 : if (!contains_zero_p (lhs))
1420 : 4651563 : return VREL_GT;
1421 : : return VREL_VARYING;
1422 : : }
1423 : :
1424 : : bool
1425 : 8996719 : operator_gt::fold_range (irange &r, tree type,
1426 : : const irange &op1, const irange &op2,
1427 : : relation_trio rel) const
1428 : : {
1429 : 8996719 : if (relop_early_resolve (r, type, op1, op2, rel, VREL_GT))
1430 : : return true;
1431 : :
1432 : 8956193 : signop sign = TYPE_SIGN (op1.type ());
1433 : 8956193 : gcc_checking_assert (sign == TYPE_SIGN (op2.type ()));
1434 : :
1435 : 8956219 : if (wi::gt_p (op1.lower_bound (), op2.upper_bound (), sign))
1436 : 71107 : r = range_true (type);
1437 : 8885112 : else if (!wi::gt_p (op1.upper_bound (), op2.lower_bound (), sign))
1438 : 150838 : r = range_false (type);
1439 : : else
1440 : 8734248 : r = range_true_and_false (type);
1441 : : return true;
1442 : : }
1443 : :
1444 : : bool
1445 : 7659913 : operator_gt::op1_range (irange &r, tree type,
1446 : : const irange &lhs, const irange &op2,
1447 : : relation_trio) const
1448 : : {
1449 : 7659913 : if (op2.undefined_p ())
1450 : : return false;
1451 : :
1452 : 7659913 : switch (get_bool_state (r, lhs, type))
1453 : : {
1454 : 3434523 : case BRS_TRUE:
1455 : 3434523 : build_gt (r, type, op2.lower_bound ());
1456 : 3434523 : break;
1457 : :
1458 : 4216116 : case BRS_FALSE:
1459 : 4216116 : build_le (r, type, op2.upper_bound ());
1460 : 4216116 : break;
1461 : :
1462 : : default:
1463 : : break;
1464 : : }
1465 : : return true;
1466 : : }
1467 : :
1468 : : bool
1469 : 2664944 : operator_gt::op2_range (irange &r, tree type,
1470 : : const irange &lhs,
1471 : : const irange &op1,
1472 : : relation_trio) const
1473 : : {
1474 : 2664944 : if (op1.undefined_p ())
1475 : : return false;
1476 : :
1477 : 2664944 : switch (get_bool_state (r, lhs, type))
1478 : : {
1479 : 1502896 : case BRS_TRUE:
1480 : 1502896 : build_lt (r, type, op1.upper_bound ());
1481 : 1502896 : break;
1482 : :
1483 : 1153477 : case BRS_FALSE:
1484 : 1153477 : build_ge (r, type, op1.lower_bound ());
1485 : 1153477 : break;
1486 : :
1487 : : default:
1488 : : break;
1489 : : }
1490 : : return true;
1491 : : }
1492 : :
1493 : :
1494 : : void
1495 : 0 : operator_ge::update_bitmask (irange &r, const irange &lh,
1496 : : const irange &rh) const
1497 : : {
1498 : 0 : update_known_bitmask (r, GE_EXPR, lh, rh);
1499 : 0 : }
1500 : :
1501 : : // Check if the LHS range indicates a relation between OP1 and OP2.
1502 : :
1503 : : relation_kind
1504 : 3123716 : operator_ge::op1_op2_relation (const irange &lhs, const irange &,
1505 : : const irange &) const
1506 : : {
1507 : 3123716 : if (lhs.undefined_p ())
1508 : : return VREL_UNDEFINED;
1509 : :
1510 : : // FALSE = op1 >= op2 indicates LT_EXPR.
1511 : 3123716 : if (lhs.zero_p ())
1512 : : return VREL_LT;
1513 : :
1514 : : // TRUE = op1 >= op2 indicates GE_EXPR.
1515 : 1635768 : if (!contains_zero_p (lhs))
1516 : 1627174 : return VREL_GE;
1517 : : return VREL_VARYING;
1518 : : }
1519 : :
1520 : : bool
1521 : 2543154 : operator_ge::fold_range (irange &r, tree type,
1522 : : const irange &op1,
1523 : : const irange &op2,
1524 : : relation_trio rel) const
1525 : : {
1526 : 2543154 : if (relop_early_resolve (r, type, op1, op2, rel, VREL_GE))
1527 : : return true;
1528 : :
1529 : 2531779 : signop sign = TYPE_SIGN (op1.type ());
1530 : 2531779 : gcc_checking_assert (sign == TYPE_SIGN (op2.type ()));
1531 : :
1532 : 2531811 : if (wi::ge_p (op1.lower_bound (), op2.upper_bound (), sign))
1533 : 152401 : r = range_true (type);
1534 : 2379410 : else if (!wi::ge_p (op1.upper_bound (), op2.lower_bound (), sign))
1535 : 5295 : r = range_false (type);
1536 : : else
1537 : 2374083 : r = range_true_and_false (type);
1538 : : return true;
1539 : : }
1540 : :
1541 : : bool
1542 : 2348426 : operator_ge::op1_range (irange &r, tree type,
1543 : : const irange &lhs,
1544 : : const irange &op2,
1545 : : relation_trio) const
1546 : : {
1547 : 2348426 : if (op2.undefined_p ())
1548 : : return false;
1549 : :
1550 : 2348426 : switch (get_bool_state (r, lhs, type))
1551 : : {
1552 : 1501706 : case BRS_TRUE:
1553 : 1501706 : build_ge (r, type, op2.lower_bound ());
1554 : 1501706 : break;
1555 : :
1556 : 840086 : case BRS_FALSE:
1557 : 840086 : build_lt (r, type, op2.upper_bound ());
1558 : 840086 : break;
1559 : :
1560 : : default:
1561 : : break;
1562 : : }
1563 : : return true;
1564 : : }
1565 : :
1566 : : bool
1567 : 1020335 : operator_ge::op2_range (irange &r, tree type,
1568 : : const irange &lhs,
1569 : : const irange &op1,
1570 : : relation_trio) const
1571 : : {
1572 : 1020335 : if (op1.undefined_p ())
1573 : : return false;
1574 : :
1575 : 1020335 : switch (get_bool_state (r, lhs, type))
1576 : : {
1577 : 593825 : case BRS_TRUE:
1578 : 593825 : build_le (r, type, op1.upper_bound ());
1579 : 593825 : break;
1580 : :
1581 : 422163 : case BRS_FALSE:
1582 : 422163 : build_gt (r, type, op1.lower_bound ());
1583 : 422163 : break;
1584 : :
1585 : : default:
1586 : : break;
1587 : : }
1588 : : return true;
1589 : : }
1590 : :
1591 : :
1592 : : void
1593 : 36299932 : operator_plus::update_bitmask (irange &r, const irange &lh,
1594 : : const irange &rh) const
1595 : : {
1596 : 36299932 : update_known_bitmask (r, PLUS_EXPR, lh, rh);
1597 : 36299932 : }
1598 : :
1599 : : // Check to see if the range of OP2 indicates anything about the relation
1600 : : // between LHS and OP1.
1601 : :
1602 : : relation_kind
1603 : 32160674 : operator_plus::lhs_op1_relation (const irange &lhs,
1604 : : const irange &op1,
1605 : : const irange &op2,
1606 : : relation_kind) const
1607 : : {
1608 : 32160674 : if (lhs.undefined_p () || op1.undefined_p () || op2.undefined_p ())
1609 : : return VREL_VARYING;
1610 : :
1611 : 32139427 : tree type = lhs.type ();
1612 : 32139427 : unsigned prec = TYPE_PRECISION (type);
1613 : 32139427 : wi::overflow_type ovf1, ovf2;
1614 : 32139427 : signop sign = TYPE_SIGN (type);
1615 : :
1616 : : // LHS = OP1 + 0 indicates LHS == OP1.
1617 : 32139427 : if (op2.zero_p ())
1618 : : return VREL_EQ;
1619 : :
1620 : 32008619 : if (TYPE_OVERFLOW_WRAPS (type))
1621 : : {
1622 : 18260123 : wi::add (op1.lower_bound (), op2.lower_bound (), sign, &ovf1);
1623 : 18260273 : wi::add (op1.upper_bound (), op2.upper_bound (), sign, &ovf2);
1624 : : }
1625 : : else
1626 : 13748796 : ovf1 = ovf2 = wi::OVF_NONE;
1627 : :
1628 : : // Never wrapping additions.
1629 : 32008619 : if (!ovf1 && !ovf2)
1630 : : {
1631 : : // Positive op2 means lhs > op1.
1632 : 18305416 : if (wi::gt_p (op2.lower_bound (), wi::zero (prec), sign))
1633 : : return VREL_GT;
1634 : 6960145 : if (wi::ge_p (op2.lower_bound (), wi::zero (prec), sign))
1635 : : return VREL_GE;
1636 : :
1637 : : // Negative op2 means lhs < op1.
1638 : 5907210 : if (wi::lt_p (op2.upper_bound (), wi::zero (prec), sign))
1639 : : return VREL_LT;
1640 : 3800936 : if (wi::le_p (op2.upper_bound (), wi::zero (prec), sign))
1641 : : return VREL_LE;
1642 : : }
1643 : : // Always wrapping additions.
1644 : 13703481 : else if (ovf1 && ovf1 == ovf2)
1645 : : {
1646 : : // Positive op2 means lhs < op1.
1647 : 447594 : if (wi::gt_p (op2.lower_bound (), wi::zero (prec), sign))
1648 : : return VREL_LT;
1649 : 20 : if (wi::ge_p (op2.lower_bound (), wi::zero (prec), sign))
1650 : : return VREL_LE;
1651 : :
1652 : : // Negative op2 means lhs > op1.
1653 : 20 : if (wi::lt_p (op2.upper_bound (), wi::zero (prec), sign))
1654 : : return VREL_GT;
1655 : 0 : if (wi::le_p (op2.upper_bound (), wi::zero (prec), sign))
1656 : : return VREL_GE;
1657 : : }
1658 : :
1659 : : // If op2 does not contain 0, then LHS and OP1 can never be equal.
1660 : 17047563 : if (!range_includes_zero_p (&op2))
1661 : : return VREL_NE;
1662 : :
1663 : : return VREL_VARYING;
1664 : : }
1665 : :
1666 : : // PLUS is symmetrical, so we can simply call lhs_op1_relation with reversed
1667 : : // operands.
1668 : :
1669 : : relation_kind
1670 : 5557846 : operator_plus::lhs_op2_relation (const irange &lhs, const irange &op1,
1671 : : const irange &op2, relation_kind rel) const
1672 : : {
1673 : 5557846 : return lhs_op1_relation (lhs, op2, op1, rel);
1674 : : }
1675 : :
1676 : : void
1677 : 47914398 : operator_plus::wi_fold (irange &r, tree type,
1678 : : const wide_int &lh_lb, const wide_int &lh_ub,
1679 : : const wide_int &rh_lb, const wide_int &rh_ub) const
1680 : : {
1681 : 47914398 : wi::overflow_type ov_lb, ov_ub;
1682 : 47914398 : signop s = TYPE_SIGN (type);
1683 : 47914398 : wide_int new_lb = wi::add (lh_lb, rh_lb, s, &ov_lb);
1684 : 47914398 : wide_int new_ub = wi::add (lh_ub, rh_ub, s, &ov_ub);
1685 : 47914398 : value_range_with_overflow (r, type, new_lb, new_ub, ov_lb, ov_ub);
1686 : 47914398 : }
1687 : :
1688 : : // Given addition or subtraction, determine the possible NORMAL ranges and
1689 : : // OVERFLOW ranges given an OFFSET range. ADD_P is true for addition.
1690 : : // Return the relation that exists between the LHS and OP1 in order for the
1691 : : // NORMAL range to apply.
1692 : : // a return value of VREL_VARYING means no ranges were applicable.
1693 : :
1694 : : static relation_kind
1695 : 714908 : plus_minus_ranges (irange &r_ov, irange &r_normal, const irange &offset,
1696 : : bool add_p)
1697 : : {
1698 : 714908 : relation_kind kind = VREL_VARYING;
1699 : : // For now, only deal with constant adds. This could be extended to ranges
1700 : : // when someone is so motivated.
1701 : 714908 : if (!offset.singleton_p () || offset.zero_p ())
1702 : 703687 : return kind;
1703 : :
1704 : : // Always work with a positive offset. ie a+ -2 -> a-2 and a- -2 > a+2
1705 : 11221 : wide_int off = offset.lower_bound ();
1706 : 11221 : if (wi::neg_p (off, SIGNED))
1707 : : {
1708 : 1057 : add_p = !add_p;
1709 : 1057 : off = wi::neg (off);
1710 : : }
1711 : :
1712 : 11221 : wi::overflow_type ov;
1713 : 11221 : tree type = offset.type ();
1714 : 11221 : unsigned prec = TYPE_PRECISION (type);
1715 : 11221 : wide_int ub;
1716 : 11221 : wide_int lb;
1717 : : // calculate the normal range and relation for the operation.
1718 : 11221 : if (add_p)
1719 : : {
1720 : : // [ 0 , INF - OFF]
1721 : 10164 : lb = wi::zero (prec);
1722 : 10164 : ub = wi::sub (irange_val_max (type), off, UNSIGNED, &ov);
1723 : 10164 : kind = VREL_GT;
1724 : : }
1725 : : else
1726 : : {
1727 : : // [ OFF, INF ]
1728 : 1057 : lb = off;
1729 : 1057 : ub = irange_val_max (type);
1730 : 1057 : kind = VREL_LT;
1731 : : }
1732 : 11221 : int_range<2> normal_range (type, lb, ub);
1733 : 11221 : int_range<2> ov_range (type, lb, ub, VR_ANTI_RANGE);
1734 : :
1735 : 11221 : r_ov = ov_range;
1736 : 11221 : r_normal = normal_range;
1737 : 11221 : return kind;
1738 : 11221 : }
1739 : :
1740 : : // Once op1 has been calculated by operator_plus or operator_minus, check
1741 : : // to see if the relation passed causes any part of the calculation to
1742 : : // be not possible. ie
1743 : : // a_2 = b_3 + 1 with a_2 < b_3 can refine the range of b_3 to [INF, INF]
1744 : : // and that further refines a_2 to [0, 0].
1745 : : // R is the value of op1, OP2 is the offset being added/subtracted, REL is the
1746 : : // relation between LHS relation OP1 and ADD_P is true for PLUS, false for
1747 : : // MINUS. IF any adjustment can be made, R will reflect it.
1748 : :
1749 : : static void
1750 : 6127845 : adjust_op1_for_overflow (irange &r, const irange &op2, relation_kind rel,
1751 : : bool add_p)
1752 : : {
1753 : 6127845 : if (r.undefined_p ())
1754 : : return;
1755 : 6127844 : tree type = r.type ();
1756 : : // Check for unsigned overflow and calculate the overflow part.
1757 : 6127844 : signop s = TYPE_SIGN (type);
1758 : 6127844 : if (!TYPE_OVERFLOW_WRAPS (type) || s == SIGNED)
1759 : : return;
1760 : :
1761 : : // Only work with <, <=, >, >= relations.
1762 : 3247362 : if (!relation_lt_le_gt_ge_p (rel))
1763 : : return;
1764 : :
1765 : : // Get the ranges for this offset.
1766 : 714908 : int_range_max normal, overflow;
1767 : 714908 : relation_kind k = plus_minus_ranges (overflow, normal, op2, add_p);
1768 : :
1769 : : // VREL_VARYING means there are no adjustments.
1770 : 714908 : if (k == VREL_VARYING)
1771 : : return;
1772 : :
1773 : : // If the relations match use the normal range, otherwise use overflow range.
1774 : 11221 : if (relation_intersect (k, rel) == k)
1775 : 8265 : r.intersect (normal);
1776 : : else
1777 : 2956 : r.intersect (overflow);
1778 : : return;
1779 : 714908 : }
1780 : :
1781 : : bool
1782 : 5531825 : operator_plus::op1_range (irange &r, tree type,
1783 : : const irange &lhs,
1784 : : const irange &op2,
1785 : : relation_trio trio) const
1786 : : {
1787 : 5531825 : if (lhs.undefined_p ())
1788 : : return false;
1789 : : // Start with the default operation.
1790 : 5531825 : range_op_handler minus (MINUS_EXPR);
1791 : 5531825 : if (!minus)
1792 : : return false;
1793 : 5531825 : bool res = minus.fold_range (r, type, lhs, op2);
1794 : 5531825 : relation_kind rel = trio.lhs_op1 ();
1795 : : // Check for a relation refinement.
1796 : 5531825 : if (res)
1797 : 5531825 : adjust_op1_for_overflow (r, op2, rel, true /* PLUS_EXPR */);
1798 : : return res;
1799 : : }
1800 : :
1801 : : bool
1802 : 1394106 : operator_plus::op2_range (irange &r, tree type,
1803 : : const irange &lhs,
1804 : : const irange &op1,
1805 : : relation_trio rel) const
1806 : : {
1807 : 1394106 : return op1_range (r, type, lhs, op1, rel.swap_op1_op2 ());
1808 : : }
1809 : :
1810 : : class operator_widen_plus_signed : public range_operator
1811 : : {
1812 : : public:
1813 : : virtual void wi_fold (irange &r, tree type,
1814 : : const wide_int &lh_lb,
1815 : : const wide_int &lh_ub,
1816 : : const wide_int &rh_lb,
1817 : : const wide_int &rh_ub) const;
1818 : : } op_widen_plus_signed;
1819 : :
1820 : : void
1821 : 0 : operator_widen_plus_signed::wi_fold (irange &r, tree type,
1822 : : const wide_int &lh_lb,
1823 : : const wide_int &lh_ub,
1824 : : const wide_int &rh_lb,
1825 : : const wide_int &rh_ub) const
1826 : : {
1827 : 0 : wi::overflow_type ov_lb, ov_ub;
1828 : 0 : signop s = TYPE_SIGN (type);
1829 : :
1830 : 0 : wide_int lh_wlb
1831 : 0 : = wide_int::from (lh_lb, wi::get_precision (lh_lb) * 2, SIGNED);
1832 : 0 : wide_int lh_wub
1833 : 0 : = wide_int::from (lh_ub, wi::get_precision (lh_ub) * 2, SIGNED);
1834 : 0 : wide_int rh_wlb = wide_int::from (rh_lb, wi::get_precision (rh_lb) * 2, s);
1835 : 0 : wide_int rh_wub = wide_int::from (rh_ub, wi::get_precision (rh_ub) * 2, s);
1836 : :
1837 : 0 : wide_int new_lb = wi::add (lh_wlb, rh_wlb, s, &ov_lb);
1838 : 0 : wide_int new_ub = wi::add (lh_wub, rh_wub, s, &ov_ub);
1839 : :
1840 : 0 : r = int_range<2> (type, new_lb, new_ub);
1841 : 0 : }
1842 : :
1843 : : class operator_widen_plus_unsigned : public range_operator
1844 : : {
1845 : : public:
1846 : : virtual void wi_fold (irange &r, tree type,
1847 : : const wide_int &lh_lb,
1848 : : const wide_int &lh_ub,
1849 : : const wide_int &rh_lb,
1850 : : const wide_int &rh_ub) const;
1851 : : } op_widen_plus_unsigned;
1852 : :
1853 : : void
1854 : 0 : operator_widen_plus_unsigned::wi_fold (irange &r, tree type,
1855 : : const wide_int &lh_lb,
1856 : : const wide_int &lh_ub,
1857 : : const wide_int &rh_lb,
1858 : : const wide_int &rh_ub) const
1859 : : {
1860 : 0 : wi::overflow_type ov_lb, ov_ub;
1861 : 0 : signop s = TYPE_SIGN (type);
1862 : :
1863 : 0 : wide_int lh_wlb
1864 : 0 : = wide_int::from (lh_lb, wi::get_precision (lh_lb) * 2, UNSIGNED);
1865 : 0 : wide_int lh_wub
1866 : 0 : = wide_int::from (lh_ub, wi::get_precision (lh_ub) * 2, UNSIGNED);
1867 : 0 : wide_int rh_wlb = wide_int::from (rh_lb, wi::get_precision (rh_lb) * 2, s);
1868 : 0 : wide_int rh_wub = wide_int::from (rh_ub, wi::get_precision (rh_ub) * 2, s);
1869 : :
1870 : 0 : wide_int new_lb = wi::add (lh_wlb, rh_wlb, s, &ov_lb);
1871 : 0 : wide_int new_ub = wi::add (lh_wub, rh_wub, s, &ov_ub);
1872 : :
1873 : 0 : r = int_range<2> (type, new_lb, new_ub);
1874 : 0 : }
1875 : :
1876 : : void
1877 : 10930839 : operator_minus::update_bitmask (irange &r, const irange &lh,
1878 : : const irange &rh) const
1879 : : {
1880 : 10930839 : update_known_bitmask (r, MINUS_EXPR, lh, rh);
1881 : 10930839 : }
1882 : :
1883 : : void
1884 : 14779609 : operator_minus::wi_fold (irange &r, tree type,
1885 : : const wide_int &lh_lb, const wide_int &lh_ub,
1886 : : const wide_int &rh_lb, const wide_int &rh_ub) const
1887 : : {
1888 : 14779609 : wi::overflow_type ov_lb, ov_ub;
1889 : 14779609 : signop s = TYPE_SIGN (type);
1890 : 14779609 : wide_int new_lb = wi::sub (lh_lb, rh_ub, s, &ov_lb);
1891 : 14779609 : wide_int new_ub = wi::sub (lh_ub, rh_lb, s, &ov_ub);
1892 : 14779609 : value_range_with_overflow (r, type, new_lb, new_ub, ov_lb, ov_ub);
1893 : 14779609 : }
1894 : :
1895 : :
1896 : : // Return the relation between LHS and OP1 based on the relation between
1897 : : // OP1 and OP2.
1898 : :
1899 : : relation_kind
1900 : 3066152 : operator_minus::lhs_op1_relation (const irange &, const irange &op1,
1901 : : const irange &, relation_kind rel) const
1902 : : {
1903 : 3066152 : if (!op1.undefined_p () && TYPE_SIGN (op1.type ()) == UNSIGNED)
1904 : 1399519 : switch (rel)
1905 : : {
1906 : : case VREL_GT:
1907 : : case VREL_GE:
1908 : : return VREL_LE;
1909 : : default:
1910 : : break;
1911 : : }
1912 : : return VREL_VARYING;
1913 : : }
1914 : :
1915 : : // Check to see if the relation REL between OP1 and OP2 has any effect on the
1916 : : // LHS of the expression. If so, apply it to LHS_RANGE. This is a helper
1917 : : // function for both MINUS_EXPR and POINTER_DIFF_EXPR.
1918 : :
1919 : : bool
1920 : 12586177 : minus_op1_op2_relation_effect (irange &lhs_range, tree type,
1921 : : const irange &op1_range ATTRIBUTE_UNUSED,
1922 : : const irange &op2_range ATTRIBUTE_UNUSED,
1923 : : relation_kind rel)
1924 : : {
1925 : 12586177 : if (rel == VREL_VARYING)
1926 : : return false;
1927 : :
1928 : 204915 : int_range<2> rel_range;
1929 : 204915 : unsigned prec = TYPE_PRECISION (type);
1930 : 204915 : signop sgn = TYPE_SIGN (type);
1931 : :
1932 : : // == and != produce [0,0] and ~[0,0] regardless of wrapping.
1933 : 204915 : if (rel == VREL_EQ)
1934 : 7397 : rel_range = int_range<2> (type, wi::zero (prec), wi::zero (prec));
1935 : 197518 : else if (rel == VREL_NE)
1936 : 91154 : rel_range = int_range<2> (type, wi::zero (prec), wi::zero (prec),
1937 : 45577 : VR_ANTI_RANGE);
1938 : 151941 : else if (TYPE_OVERFLOW_WRAPS (type))
1939 : : {
1940 : 110933 : switch (rel)
1941 : : {
1942 : : // For wrapping signed values and unsigned, if op1 > op2 or
1943 : : // op1 < op2, then op1 - op2 can be restricted to ~[0, 0].
1944 : 37054 : case VREL_GT:
1945 : 37054 : case VREL_LT:
1946 : 74108 : rel_range = int_range<2> (type, wi::zero (prec), wi::zero (prec),
1947 : 37054 : VR_ANTI_RANGE);
1948 : 37054 : break;
1949 : : default:
1950 : : return false;
1951 : : }
1952 : : }
1953 : : else
1954 : : {
1955 : 41008 : switch (rel)
1956 : : {
1957 : : // op1 > op2, op1 - op2 can be restricted to [1, +INF]
1958 : 17803 : case VREL_GT:
1959 : 35606 : rel_range = int_range<2> (type, wi::one (prec),
1960 : 35606 : wi::max_value (prec, sgn));
1961 : 17803 : break;
1962 : : // op1 >= op2, op1 - op2 can be restricted to [0, +INF]
1963 : 22496 : case VREL_GE:
1964 : 44992 : rel_range = int_range<2> (type, wi::zero (prec),
1965 : 44992 : wi::max_value (prec, sgn));
1966 : 22496 : break;
1967 : : // op1 < op2, op1 - op2 can be restricted to [-INF, -1]
1968 : 254 : case VREL_LT:
1969 : 762 : rel_range = int_range<2> (type, wi::min_value (prec, sgn),
1970 : 508 : wi::minus_one (prec));
1971 : 254 : break;
1972 : : // op1 <= op2, op1 - op2 can be restricted to [-INF, 0]
1973 : 262 : case VREL_LE:
1974 : 786 : rel_range = int_range<2> (type, wi::min_value (prec, sgn),
1975 : 524 : wi::zero (prec));
1976 : 262 : break;
1977 : : default:
1978 : : return false;
1979 : : }
1980 : : }
1981 : 130843 : lhs_range.intersect (rel_range);
1982 : 130843 : return true;
1983 : 204915 : }
1984 : :
1985 : : bool
1986 : 10930839 : operator_minus::op1_op2_relation_effect (irange &lhs_range, tree type,
1987 : : const irange &op1_range,
1988 : : const irange &op2_range,
1989 : : relation_kind rel) const
1990 : : {
1991 : 10930839 : return minus_op1_op2_relation_effect (lhs_range, type, op1_range, op2_range,
1992 : 10930839 : rel);
1993 : : }
1994 : :
1995 : : bool
1996 : 596020 : operator_minus::op1_range (irange &r, tree type,
1997 : : const irange &lhs,
1998 : : const irange &op2,
1999 : : relation_trio trio) const
2000 : : {
2001 : 596020 : if (lhs.undefined_p ())
2002 : : return false;
2003 : : // Start with the default operation.
2004 : 596020 : range_op_handler minus (PLUS_EXPR);
2005 : 596020 : if (!minus)
2006 : : return false;
2007 : 596020 : bool res = minus.fold_range (r, type, lhs, op2);
2008 : 596020 : relation_kind rel = trio.lhs_op1 ();
2009 : 596020 : if (res)
2010 : 596020 : adjust_op1_for_overflow (r, op2, rel, false /* PLUS_EXPR */);
2011 : : return res;
2012 : :
2013 : : }
2014 : :
2015 : : bool
2016 : 892408 : operator_minus::op2_range (irange &r, tree type,
2017 : : const irange &lhs,
2018 : : const irange &op1,
2019 : : relation_trio) const
2020 : : {
2021 : 892408 : if (lhs.undefined_p ())
2022 : : return false;
2023 : 892408 : return fold_range (r, type, op1, lhs);
2024 : : }
2025 : :
2026 : : void
2027 : 571353 : operator_min::update_bitmask (irange &r, const irange &lh,
2028 : : const irange &rh) const
2029 : : {
2030 : 571353 : update_known_bitmask (r, MIN_EXPR, lh, rh);
2031 : 571353 : }
2032 : :
2033 : : void
2034 : 733823 : operator_min::wi_fold (irange &r, tree type,
2035 : : const wide_int &lh_lb, const wide_int &lh_ub,
2036 : : const wide_int &rh_lb, const wide_int &rh_ub) const
2037 : : {
2038 : 733823 : signop s = TYPE_SIGN (type);
2039 : 733823 : wide_int new_lb = wi::min (lh_lb, rh_lb, s);
2040 : 733823 : wide_int new_ub = wi::min (lh_ub, rh_ub, s);
2041 : 733823 : value_range_with_overflow (r, type, new_lb, new_ub);
2042 : 733823 : }
2043 : :
2044 : :
2045 : : void
2046 : 499472 : operator_max::update_bitmask (irange &r, const irange &lh,
2047 : : const irange &rh) const
2048 : : {
2049 : 499472 : update_known_bitmask (r, MAX_EXPR, lh, rh);
2050 : 499472 : }
2051 : :
2052 : : void
2053 : 597185 : operator_max::wi_fold (irange &r, tree type,
2054 : : const wide_int &lh_lb, const wide_int &lh_ub,
2055 : : const wide_int &rh_lb, const wide_int &rh_ub) const
2056 : : {
2057 : 597185 : signop s = TYPE_SIGN (type);
2058 : 597185 : wide_int new_lb = wi::max (lh_lb, rh_lb, s);
2059 : 597185 : wide_int new_ub = wi::max (lh_ub, rh_ub, s);
2060 : 597185 : value_range_with_overflow (r, type, new_lb, new_ub);
2061 : 597185 : }
2062 : :
2063 : :
2064 : : // Calculate the cross product of two sets of ranges and return it.
2065 : : //
2066 : : // Multiplications, divisions and shifts are a bit tricky to handle,
2067 : : // depending on the mix of signs we have in the two ranges, we need to
2068 : : // operate on different values to get the minimum and maximum values
2069 : : // for the new range. One approach is to figure out all the
2070 : : // variations of range combinations and do the operations.
2071 : : //
2072 : : // However, this involves several calls to compare_values and it is
2073 : : // pretty convoluted. It's simpler to do the 4 operations (MIN0 OP
2074 : : // MIN1, MIN0 OP MAX1, MAX0 OP MIN1 and MAX0 OP MAX0 OP MAX1) and then
2075 : : // figure the smallest and largest values to form the new range.
2076 : :
2077 : : void
2078 : 10863532 : cross_product_operator::wi_cross_product (irange &r, tree type,
2079 : : const wide_int &lh_lb,
2080 : : const wide_int &lh_ub,
2081 : : const wide_int &rh_lb,
2082 : : const wide_int &rh_ub) const
2083 : : {
2084 : 10863532 : wide_int cp1, cp2, cp3, cp4;
2085 : : // Default to varying.
2086 : 10863532 : r.set_varying (type);
2087 : :
2088 : : // Compute the 4 cross operations, bailing if we get an overflow we
2089 : : // can't handle.
2090 : 10863532 : if (wi_op_overflows (cp1, type, lh_lb, rh_lb))
2091 : : return;
2092 : 10863530 : if (wi::eq_p (lh_lb, lh_ub))
2093 : 3554609 : cp3 = cp1;
2094 : 7308921 : else if (wi_op_overflows (cp3, type, lh_ub, rh_lb))
2095 : : return;
2096 : 10863530 : if (wi::eq_p (rh_lb, rh_ub))
2097 : 8362852 : cp2 = cp1;
2098 : 2500678 : else if (wi_op_overflows (cp2, type, lh_lb, rh_ub))
2099 : : return;
2100 : 10861465 : if (wi::eq_p (lh_lb, lh_ub))
2101 : 3554579 : cp4 = cp2;
2102 : 7306886 : else if (wi_op_overflows (cp4, type, lh_ub, rh_ub))
2103 : : return;
2104 : :
2105 : : // Order pairs.
2106 : 10861465 : signop sign = TYPE_SIGN (type);
2107 : 10861465 : if (wi::gt_p (cp1, cp2, sign))
2108 : 1080868 : std::swap (cp1, cp2);
2109 : 10861465 : if (wi::gt_p (cp3, cp4, sign))
2110 : 1035161 : std::swap (cp3, cp4);
2111 : :
2112 : : // Choose min and max from the ordered pairs.
2113 : 10861465 : wide_int res_lb = wi::min (cp1, cp3, sign);
2114 : 10861465 : wide_int res_ub = wi::max (cp2, cp4, sign);
2115 : 10861465 : value_range_with_overflow (r, type, res_lb, res_ub);
2116 : 10864772 : }
2117 : :
2118 : :
2119 : : void
2120 : 11832929 : operator_mult::update_bitmask (irange &r, const irange &lh,
2121 : : const irange &rh) const
2122 : : {
2123 : 11832929 : update_known_bitmask (r, MULT_EXPR, lh, rh);
2124 : 11832929 : }
2125 : :
2126 : : bool
2127 : 690710 : operator_mult::op1_range (irange &r, tree type,
2128 : : const irange &lhs, const irange &op2,
2129 : : relation_trio) const
2130 : : {
2131 : 690710 : if (lhs.undefined_p ())
2132 : : return false;
2133 : :
2134 : : // We can't solve 0 = OP1 * N by dividing by N with a wrapping type.
2135 : : // For example: For 0 = OP1 * 2, OP1 could be 0, or MAXINT, whereas
2136 : : // for 4 = OP1 * 2, OP1 could be 2 or 130 (unsigned 8-bit)
2137 : 690710 : if (TYPE_OVERFLOW_WRAPS (type))
2138 : : return false;
2139 : :
2140 : 191472 : wide_int offset;
2141 : 191472 : if (op2.singleton_p (offset) && offset != 0)
2142 : 132867 : return range_op_handler (TRUNC_DIV_EXPR).fold_range (r, type, lhs, op2);
2143 : : return false;
2144 : 191472 : }
2145 : :
2146 : : bool
2147 : 80773 : operator_mult::op2_range (irange &r, tree type,
2148 : : const irange &lhs, const irange &op1,
2149 : : relation_trio rel) const
2150 : : {
2151 : 80773 : return operator_mult::op1_range (r, type, lhs, op1, rel.swap_op1_op2 ());
2152 : : }
2153 : :
2154 : : bool
2155 : 11777045 : operator_mult::wi_op_overflows (wide_int &res, tree type,
2156 : : const wide_int &w0, const wide_int &w1) const
2157 : : {
2158 : 11777045 : wi::overflow_type overflow = wi::OVF_NONE;
2159 : 11777045 : signop sign = TYPE_SIGN (type);
2160 : 11777045 : res = wi::mul (w0, w1, sign, &overflow);
2161 : 11777045 : if (overflow && TYPE_OVERFLOW_UNDEFINED (type))
2162 : : {
2163 : : // For multiplication, the sign of the overflow is given
2164 : : // by the comparison of the signs of the operands.
2165 : 5510751 : if (sign == UNSIGNED || w0.sign_mask () == w1.sign_mask ())
2166 : 3079608 : res = wi::max_value (w0.get_precision (), sign);
2167 : : else
2168 : 2431296 : res = wi::min_value (w0.get_precision (), sign);
2169 : 5510751 : return false;
2170 : : }
2171 : 6266294 : return overflow;
2172 : : }
2173 : :
2174 : : void
2175 : 14195342 : operator_mult::wi_fold (irange &r, tree type,
2176 : : const wide_int &lh_lb, const wide_int &lh_ub,
2177 : : const wide_int &rh_lb, const wide_int &rh_ub) const
2178 : : {
2179 : 14195342 : if (TYPE_OVERFLOW_UNDEFINED (type))
2180 : : {
2181 : 5355333 : wi_cross_product (r, type, lh_lb, lh_ub, rh_lb, rh_ub);
2182 : 5355333 : return;
2183 : : }
2184 : :
2185 : : // Multiply the ranges when overflow wraps. This is basically fancy
2186 : : // code so we don't drop to varying with an unsigned
2187 : : // [-3,-1]*[-3,-1].
2188 : : //
2189 : : // This test requires 2*prec bits if both operands are signed and
2190 : : // 2*prec + 2 bits if either is not. Therefore, extend the values
2191 : : // using the sign of the result to PREC2. From here on out,
2192 : : // everything is just signed math no matter what the input types
2193 : : // were.
2194 : :
2195 : 8840009 : signop sign = TYPE_SIGN (type);
2196 : 8840009 : unsigned prec = TYPE_PRECISION (type);
2197 : 8840009 : widest2_int min0 = widest2_int::from (lh_lb, sign);
2198 : 8840009 : widest2_int max0 = widest2_int::from (lh_ub, sign);
2199 : 8840009 : widest2_int min1 = widest2_int::from (rh_lb, sign);
2200 : 8840009 : widest2_int max1 = widest2_int::from (rh_ub, sign);
2201 : 8840009 : widest2_int sizem1 = wi::mask <widest2_int> (prec, false);
2202 : 8840009 : widest2_int size = sizem1 + 1;
2203 : :
2204 : : // Canonicalize the intervals.
2205 : 8840009 : if (sign == UNSIGNED)
2206 : : {
2207 : 8179266 : if (wi::ltu_p (size, min0 + max0))
2208 : : {
2209 : 1140828 : min0 -= size;
2210 : 1140828 : max0 -= size;
2211 : : }
2212 : 8179236 : if (wi::ltu_p (size, min1 + max1))
2213 : : {
2214 : 114336 : min1 -= size;
2215 : 114336 : max1 -= size;
2216 : : }
2217 : : }
2218 : :
2219 : : // Sort the 4 products so that min is in prod0 and max is in
2220 : : // prod3.
2221 : 8840009 : widest2_int prod0 = min0 * min1;
2222 : 8840009 : widest2_int prod1 = min0 * max1;
2223 : 8840009 : widest2_int prod2 = max0 * min1;
2224 : 8840009 : widest2_int prod3 = max0 * max1;
2225 : :
2226 : : // min0min1 > max0max1
2227 : 8840009 : if (prod0 > prod3)
2228 : 149165 : std::swap (prod0, prod3);
2229 : :
2230 : : // min0max1 > max0min1
2231 : 8840009 : if (prod1 > prod2)
2232 : 226143 : std::swap (prod1, prod2);
2233 : :
2234 : 8840009 : if (prod0 > prod1)
2235 : 66180 : std::swap (prod0, prod1);
2236 : :
2237 : 8840009 : if (prod2 > prod3)
2238 : 2301 : std::swap (prod2, prod3);
2239 : :
2240 : : // diff = max - min
2241 : 8840009 : prod2 = prod3 - prod0;
2242 : 8840009 : if (wi::geu_p (prod2, sizem1))
2243 : : {
2244 : : // Multiplying by X, where X is a power of 2 is [0,0][X,+INF].
2245 : 6827132 : if (TYPE_UNSIGNED (type) && rh_lb == rh_ub
2246 : 6379808 : && wi::exact_log2 (rh_lb) != -1 && prec > 1)
2247 : : {
2248 : 2447925 : r.set (type, rh_lb, wi::max_value (prec, sign));
2249 : 2447925 : int_range<2> zero;
2250 : 2447925 : zero.set_zero (type);
2251 : 2447925 : r.union_ (zero);
2252 : 2447925 : }
2253 : : else
2254 : : // The range covers all values.
2255 : 1032732 : r.set_varying (type);
2256 : : }
2257 : : else
2258 : : {
2259 : 5359352 : wide_int new_lb = wide_int::from (prod0, prec, sign);
2260 : 5359352 : wide_int new_ub = wide_int::from (prod3, prec, sign);
2261 : 5359352 : create_possibly_reversed_range (r, type, new_lb, new_ub);
2262 : 5359409 : }
2263 : 8840609 : }
2264 : :
2265 : : class operator_widen_mult_signed : public range_operator
2266 : : {
2267 : : public:
2268 : : virtual void wi_fold (irange &r, tree type,
2269 : : const wide_int &lh_lb,
2270 : : const wide_int &lh_ub,
2271 : : const wide_int &rh_lb,
2272 : : const wide_int &rh_ub)
2273 : : const;
2274 : : } op_widen_mult_signed;
2275 : :
2276 : : void
2277 : 3 : operator_widen_mult_signed::wi_fold (irange &r, tree type,
2278 : : const wide_int &lh_lb,
2279 : : const wide_int &lh_ub,
2280 : : const wide_int &rh_lb,
2281 : : const wide_int &rh_ub) const
2282 : : {
2283 : 3 : signop s = TYPE_SIGN (type);
2284 : :
2285 : 3 : wide_int lh_wlb = wide_int::from (lh_lb, wi::get_precision (lh_lb) * 2, SIGNED);
2286 : 3 : wide_int lh_wub = wide_int::from (lh_ub, wi::get_precision (lh_ub) * 2, SIGNED);
2287 : 3 : wide_int rh_wlb = wide_int::from (rh_lb, wi::get_precision (rh_lb) * 2, s);
2288 : 3 : wide_int rh_wub = wide_int::from (rh_ub, wi::get_precision (rh_ub) * 2, s);
2289 : :
2290 : : /* We don't expect a widening multiplication to be able to overflow but range
2291 : : calculations for multiplications are complicated. After widening the
2292 : : operands lets call the base class. */
2293 : 3 : return op_mult.wi_fold (r, type, lh_wlb, lh_wub, rh_wlb, rh_wub);
2294 : 3 : }
2295 : :
2296 : :
2297 : : class operator_widen_mult_unsigned : public range_operator
2298 : : {
2299 : : public:
2300 : : virtual void wi_fold (irange &r, tree type,
2301 : : const wide_int &lh_lb,
2302 : : const wide_int &lh_ub,
2303 : : const wide_int &rh_lb,
2304 : : const wide_int &rh_ub)
2305 : : const;
2306 : : } op_widen_mult_unsigned;
2307 : :
2308 : : void
2309 : 13 : operator_widen_mult_unsigned::wi_fold (irange &r, tree type,
2310 : : const wide_int &lh_lb,
2311 : : const wide_int &lh_ub,
2312 : : const wide_int &rh_lb,
2313 : : const wide_int &rh_ub) const
2314 : : {
2315 : 13 : signop s = TYPE_SIGN (type);
2316 : :
2317 : 13 : wide_int lh_wlb = wide_int::from (lh_lb, wi::get_precision (lh_lb) * 2, UNSIGNED);
2318 : 13 : wide_int lh_wub = wide_int::from (lh_ub, wi::get_precision (lh_ub) * 2, UNSIGNED);
2319 : 13 : wide_int rh_wlb = wide_int::from (rh_lb, wi::get_precision (rh_lb) * 2, s);
2320 : 13 : wide_int rh_wub = wide_int::from (rh_ub, wi::get_precision (rh_ub) * 2, s);
2321 : :
2322 : : /* We don't expect a widening multiplication to be able to overflow but range
2323 : : calculations for multiplications are complicated. After widening the
2324 : : operands lets call the base class. */
2325 : 13 : return op_mult.wi_fold (r, type, lh_wlb, lh_wub, rh_wlb, rh_wub);
2326 : 13 : }
2327 : :
2328 : : class operator_div : public cross_product_operator
2329 : : {
2330 : : public:
2331 : : operator_div (tree_code div_kind) { m_code = div_kind; }
2332 : : virtual void wi_fold (irange &r, tree type,
2333 : : const wide_int &lh_lb,
2334 : : const wide_int &lh_ub,
2335 : : const wide_int &rh_lb,
2336 : : const wide_int &rh_ub) const final override;
2337 : : virtual bool wi_op_overflows (wide_int &res, tree type,
2338 : : const wide_int &, const wide_int &)
2339 : : const final override;
2340 : 1937175 : void update_bitmask (irange &r, const irange &lh, const irange &rh) const
2341 : 1937175 : { update_known_bitmask (r, m_code, lh, rh); }
2342 : : protected:
2343 : : tree_code m_code;
2344 : : };
2345 : :
2346 : : static operator_div op_trunc_div (TRUNC_DIV_EXPR);
2347 : : static operator_div op_floor_div (FLOOR_DIV_EXPR);
2348 : : static operator_div op_round_div (ROUND_DIV_EXPR);
2349 : : static operator_div op_ceil_div (CEIL_DIV_EXPR);
2350 : :
2351 : : bool
2352 : 7883991 : operator_div::wi_op_overflows (wide_int &res, tree type,
2353 : : const wide_int &w0, const wide_int &w1) const
2354 : : {
2355 : 7883991 : if (w1 == 0)
2356 : : return true;
2357 : :
2358 : 7883991 : wi::overflow_type overflow = wi::OVF_NONE;
2359 : 7883991 : signop sign = TYPE_SIGN (type);
2360 : :
2361 : 7883991 : switch (m_code)
2362 : : {
2363 : 7836261 : case EXACT_DIV_EXPR:
2364 : 7836261 : case TRUNC_DIV_EXPR:
2365 : 7836261 : res = wi::div_trunc (w0, w1, sign, &overflow);
2366 : 7836261 : break;
2367 : 42096 : case FLOOR_DIV_EXPR:
2368 : 42096 : res = wi::div_floor (w0, w1, sign, &overflow);
2369 : 42096 : break;
2370 : 0 : case ROUND_DIV_EXPR:
2371 : 0 : res = wi::div_round (w0, w1, sign, &overflow);
2372 : 0 : break;
2373 : 5634 : case CEIL_DIV_EXPR:
2374 : 5634 : res = wi::div_ceil (w0, w1, sign, &overflow);
2375 : 5634 : break;
2376 : 0 : default:
2377 : 0 : gcc_unreachable ();
2378 : : }
2379 : :
2380 : 7883991 : if (overflow && TYPE_OVERFLOW_UNDEFINED (type))
2381 : : {
2382 : : // For division, the only case is -INF / -1 = +INF.
2383 : 155385 : res = wi::max_value (w0.get_precision (), sign);
2384 : 155385 : return false;
2385 : : }
2386 : 7728606 : return overflow;
2387 : : }
2388 : :
2389 : : void
2390 : 2312810 : operator_div::wi_fold (irange &r, tree type,
2391 : : const wide_int &lh_lb, const wide_int &lh_ub,
2392 : : const wide_int &rh_lb, const wide_int &rh_ub) const
2393 : : {
2394 : 2312810 : const wide_int dividend_min = lh_lb;
2395 : 2312810 : const wide_int dividend_max = lh_ub;
2396 : 2312810 : const wide_int divisor_min = rh_lb;
2397 : 2312810 : const wide_int divisor_max = rh_ub;
2398 : 2312810 : signop sign = TYPE_SIGN (type);
2399 : 2312810 : unsigned prec = TYPE_PRECISION (type);
2400 : 2312810 : wide_int extra_min, extra_max;
2401 : :
2402 : : // If we know we won't divide by zero, just do the division.
2403 : 2312810 : if (!wi_includes_zero_p (type, divisor_min, divisor_max))
2404 : : {
2405 : 1844582 : wi_cross_product (r, type, dividend_min, dividend_max,
2406 : : divisor_min, divisor_max);
2407 : 1844582 : return;
2408 : : }
2409 : :
2410 : : // If we're definitely dividing by zero, there's nothing to do.
2411 : 468228 : if (wi_zero_p (type, divisor_min, divisor_max))
2412 : : {
2413 : 3842 : r.set_undefined ();
2414 : 3842 : return;
2415 : : }
2416 : :
2417 : : // Perform the division in 2 parts, [LB, -1] and [1, UB], which will
2418 : : // skip any division by zero.
2419 : :
2420 : : // First divide by the negative numbers, if any.
2421 : 464386 : if (wi::neg_p (divisor_min, sign))
2422 : 564336 : wi_cross_product (r, type, dividend_min, dividend_max,
2423 : 564336 : divisor_min, wi::minus_one (prec));
2424 : : else
2425 : 182218 : r.set_undefined ();
2426 : :
2427 : : // Then divide by the non-zero positive numbers, if any.
2428 : 464386 : if (wi::gt_p (divisor_max, wi::zero (prec), sign))
2429 : : {
2430 : 462944 : int_range_max tmp;
2431 : 925888 : wi_cross_product (tmp, type, dividend_min, dividend_max,
2432 : 462944 : wi::one (prec), divisor_max);
2433 : 462944 : r.union_ (tmp);
2434 : 462944 : }
2435 : : // We shouldn't still have undefined here.
2436 : 464386 : gcc_checking_assert (!r.undefined_p ());
2437 : 2313350 : }
2438 : :
2439 : :
2440 : : class operator_exact_divide : public operator_div
2441 : : {
2442 : : using range_operator::op1_range;
2443 : : public:
2444 : : operator_exact_divide () : operator_div (EXACT_DIV_EXPR) { }
2445 : : virtual bool op1_range (irange &r, tree type,
2446 : : const irange &lhs,
2447 : : const irange &op2,
2448 : : relation_trio) const;
2449 : :
2450 : : } op_exact_div;
2451 : :
2452 : : bool
2453 : 395147 : operator_exact_divide::op1_range (irange &r, tree type,
2454 : : const irange &lhs,
2455 : : const irange &op2,
2456 : : relation_trio) const
2457 : : {
2458 : 395147 : if (lhs.undefined_p ())
2459 : : return false;
2460 : 395147 : wide_int offset;
2461 : : // [2, 4] = op1 / [3,3] since its exact divide, no need to worry about
2462 : : // remainders in the endpoints, so op1 = [2,4] * [3,3] = [6,12].
2463 : : // We wont bother trying to enumerate all the in between stuff :-P
2464 : : // TRUE accuracy is [6,6][9,9][12,12]. This is unlikely to matter most of
2465 : : // the time however.
2466 : : // If op2 is a multiple of 2, we would be able to set some non-zero bits.
2467 : 395147 : if (op2.singleton_p (offset) && offset != 0)
2468 : 395147 : return range_op_handler (MULT_EXPR).fold_range (r, type, lhs, op2);
2469 : : return false;
2470 : 395147 : }
2471 : :
2472 : :
2473 : : class operator_lshift : public cross_product_operator
2474 : : {
2475 : : using range_operator::fold_range;
2476 : : using range_operator::op1_range;
2477 : : public:
2478 : : virtual bool op1_range (irange &r, tree type, const irange &lhs,
2479 : : const irange &op2, relation_trio rel = TRIO_VARYING)
2480 : : const final override;
2481 : : virtual bool fold_range (irange &r, tree type, const irange &op1,
2482 : : const irange &op2, relation_trio rel = TRIO_VARYING)
2483 : : const final override;
2484 : :
2485 : : virtual void wi_fold (irange &r, tree type,
2486 : : const wide_int &lh_lb, const wide_int &lh_ub,
2487 : : const wide_int &rh_lb,
2488 : : const wide_int &rh_ub) const final override;
2489 : : virtual bool wi_op_overflows (wide_int &res,
2490 : : tree type,
2491 : : const wide_int &,
2492 : : const wide_int &) const final override;
2493 : 379629 : void update_bitmask (irange &r, const irange &lh,
2494 : : const irange &rh) const final override
2495 : 379629 : { update_known_bitmask (r, LSHIFT_EXPR, lh, rh); }
2496 : : // Check compatibility of LHS and op1.
2497 : 1016727 : bool operand_check_p (tree t1, tree t2, tree) const final override
2498 : 1016727 : { return range_compatible_p (t1, t2); }
2499 : : } op_lshift;
2500 : :
2501 : : class operator_rshift : public cross_product_operator
2502 : : {
2503 : : using range_operator::fold_range;
2504 : : using range_operator::op1_range;
2505 : : using range_operator::lhs_op1_relation;
2506 : : public:
2507 : : virtual bool fold_range (irange &r, tree type, const irange &op1,
2508 : : const irange &op2, relation_trio rel = TRIO_VARYING)
2509 : : const final override;
2510 : : virtual void wi_fold (irange &r, tree type,
2511 : : const wide_int &lh_lb,
2512 : : const wide_int &lh_ub,
2513 : : const wide_int &rh_lb,
2514 : : const wide_int &rh_ub) const final override;
2515 : : virtual bool wi_op_overflows (wide_int &res,
2516 : : tree type,
2517 : : const wide_int &w0,
2518 : : const wide_int &w1) const final override;
2519 : : virtual bool op1_range (irange &, tree type, const irange &lhs,
2520 : : const irange &op2, relation_trio rel = TRIO_VARYING)
2521 : : const final override;
2522 : : virtual relation_kind lhs_op1_relation (const irange &lhs, const irange &op1,
2523 : : const irange &op2, relation_kind rel)
2524 : : const final override;
2525 : 2446652 : void update_bitmask (irange &r, const irange &lh,
2526 : : const irange &rh) const final override
2527 : 2446652 : { update_known_bitmask (r, RSHIFT_EXPR, lh, rh); }
2528 : : // Check compatibility of LHS and op1.
2529 : 2506040 : bool operand_check_p (tree t1, tree t2, tree) const final override
2530 : 2506040 : { return range_compatible_p (t1, t2); }
2531 : : } op_rshift;
2532 : :
2533 : :
2534 : : relation_kind
2535 : 1738750 : operator_rshift::lhs_op1_relation (const irange &lhs ATTRIBUTE_UNUSED,
2536 : : const irange &op1,
2537 : : const irange &op2,
2538 : : relation_kind) const
2539 : : {
2540 : : // If both operands range are >= 0, then the LHS <= op1.
2541 : 1738750 : if (!op1.undefined_p () && !op2.undefined_p ()
2542 : 3476966 : && wi::ge_p (op1.lower_bound (), 0, TYPE_SIGN (op1.type ()))
2543 : 5036501 : && wi::ge_p (op2.lower_bound (), 0, TYPE_SIGN (op2.type ())))
2544 : 1536781 : return VREL_LE;
2545 : : return VREL_VARYING;
2546 : : }
2547 : :
2548 : : bool
2549 : 1418091 : operator_lshift::fold_range (irange &r, tree type,
2550 : : const irange &op1,
2551 : : const irange &op2,
2552 : : relation_trio rel) const
2553 : : {
2554 : 1418091 : int_range_max shift_range;
2555 : 1418091 : if (!get_shift_range (shift_range, type, op2))
2556 : : {
2557 : 488 : if (op2.undefined_p ())
2558 : 154 : r.set_undefined ();
2559 : : else
2560 : 334 : r.set_zero (type);
2561 : 488 : return true;
2562 : : }
2563 : :
2564 : : // Transform left shifts by constants into multiplies.
2565 : 1417603 : if (shift_range.singleton_p ())
2566 : : {
2567 : 1037947 : unsigned shift = shift_range.lower_bound ().to_uhwi ();
2568 : 1037947 : wide_int tmp = wi::set_bit_in_zero (shift, TYPE_PRECISION (type));
2569 : 1037947 : int_range<1> mult (type, tmp, tmp);
2570 : :
2571 : : // Force wrapping multiplication.
2572 : 1037947 : bool saved_flag_wrapv = flag_wrapv;
2573 : 1037947 : bool saved_flag_wrapv_pointer = flag_wrapv_pointer;
2574 : 1037947 : flag_wrapv = 1;
2575 : 1037947 : flag_wrapv_pointer = 1;
2576 : 1037947 : bool b = op_mult.fold_range (r, type, op1, mult);
2577 : 1037947 : flag_wrapv = saved_flag_wrapv;
2578 : 1037947 : flag_wrapv_pointer = saved_flag_wrapv_pointer;
2579 : 1037947 : return b;
2580 : 1037955 : }
2581 : : else
2582 : : // Otherwise, invoke the generic fold routine.
2583 : 379656 : return range_operator::fold_range (r, type, op1, shift_range, rel);
2584 : 1418091 : }
2585 : :
2586 : : void
2587 : 437037 : operator_lshift::wi_fold (irange &r, tree type,
2588 : : const wide_int &lh_lb, const wide_int &lh_ub,
2589 : : const wide_int &rh_lb, const wide_int &rh_ub) const
2590 : : {
2591 : 437037 : signop sign = TYPE_SIGN (type);
2592 : 437037 : unsigned prec = TYPE_PRECISION (type);
2593 : 437037 : int overflow_pos = sign == SIGNED ? prec - 1 : prec;
2594 : 437037 : int bound_shift = overflow_pos - rh_ub.to_shwi ();
2595 : : // If bound_shift == HOST_BITS_PER_WIDE_INT, the llshift can
2596 : : // overflow. However, for that to happen, rh.max needs to be zero,
2597 : : // which means rh is a singleton range of zero, which means we simply return
2598 : : // [lh_lb, lh_ub] as the range.
2599 : 437037 : if (wi::eq_p (rh_ub, rh_lb) && wi::eq_p (rh_ub, 0))
2600 : : {
2601 : 17293 : r = int_range<2> (type, lh_lb, lh_ub);
2602 : 17293 : return;
2603 : : }
2604 : :
2605 : 419744 : wide_int bound = wi::set_bit_in_zero (bound_shift, prec);
2606 : 419744 : wide_int complement = ~(bound - 1);
2607 : 419744 : wide_int low_bound, high_bound;
2608 : 419744 : bool in_bounds = false;
2609 : :
2610 : 419744 : if (sign == UNSIGNED)
2611 : : {
2612 : 191369 : low_bound = bound;
2613 : 191369 : high_bound = complement;
2614 : 191369 : if (wi::ltu_p (lh_ub, low_bound))
2615 : : {
2616 : : // [5, 6] << [1, 2] == [10, 24].
2617 : : // We're shifting out only zeroes, the value increases
2618 : : // monotonically.
2619 : : in_bounds = true;
2620 : : }
2621 : 72506 : else if (wi::ltu_p (high_bound, lh_lb))
2622 : : {
2623 : : // [0xffffff00, 0xffffffff] << [1, 2]
2624 : : // == [0xfffffc00, 0xfffffffe].
2625 : : // We're shifting out only ones, the value decreases
2626 : : // monotonically.
2627 : : in_bounds = true;
2628 : : }
2629 : : }
2630 : : else
2631 : : {
2632 : : // [-1, 1] << [1, 2] == [-4, 4]
2633 : 228375 : low_bound = complement;
2634 : 228375 : high_bound = bound;
2635 : 228375 : if (wi::lts_p (lh_ub, high_bound)
2636 : 228375 : && wi::lts_p (low_bound, lh_lb))
2637 : : {
2638 : : // For non-negative numbers, we're shifting out only zeroes,
2639 : : // the value increases monotonically. For negative numbers,
2640 : : // we're shifting out only ones, the value decreases
2641 : : // monotonically.
2642 : : in_bounds = true;
2643 : : }
2644 : : }
2645 : :
2646 : : if (in_bounds)
2647 : 236242 : wi_cross_product (r, type, lh_lb, lh_ub, rh_lb, rh_ub);
2648 : : else
2649 : 183502 : r.set_varying (type);
2650 : 419753 : }
2651 : :
2652 : : bool
2653 : 469173 : operator_lshift::wi_op_overflows (wide_int &res, tree type,
2654 : : const wide_int &w0, const wide_int &w1) const
2655 : : {
2656 : 469173 : signop sign = TYPE_SIGN (type);
2657 : 469173 : if (wi::neg_p (w1))
2658 : : {
2659 : : // It's unclear from the C standard whether shifts can overflow.
2660 : : // The following code ignores overflow; perhaps a C standard
2661 : : // interpretation ruling is needed.
2662 : 0 : res = wi::rshift (w0, -w1, sign);
2663 : : }
2664 : : else
2665 : 469173 : res = wi::lshift (w0, w1);
2666 : 469173 : return false;
2667 : : }
2668 : :
2669 : : bool
2670 : 45573 : operator_lshift::op1_range (irange &r,
2671 : : tree type,
2672 : : const irange &lhs,
2673 : : const irange &op2,
2674 : : relation_trio) const
2675 : : {
2676 : 45573 : if (lhs.undefined_p ())
2677 : : return false;
2678 : :
2679 : 45573 : if (!contains_zero_p (lhs))
2680 : 22315 : r.set_nonzero (type);
2681 : : else
2682 : 23258 : r.set_varying (type);
2683 : :
2684 : 45573 : wide_int shift;
2685 : 45573 : if (op2.singleton_p (shift))
2686 : : {
2687 : 41481 : if (wi::lt_p (shift, 0, SIGNED))
2688 : : return false;
2689 : 41481 : if (wi::ge_p (shift, wi::uhwi (TYPE_PRECISION (type),
2690 : 41481 : TYPE_PRECISION (op2.type ())),
2691 : : UNSIGNED))
2692 : : return false;
2693 : 41481 : if (shift == 0)
2694 : : {
2695 : 9 : r.intersect (lhs);
2696 : 9 : return true;
2697 : : }
2698 : :
2699 : : // Work completely in unsigned mode to start.
2700 : 41472 : tree utype = type;
2701 : 41472 : int_range_max tmp_range;
2702 : 41472 : if (TYPE_SIGN (type) == SIGNED)
2703 : : {
2704 : 5329 : int_range_max tmp = lhs;
2705 : 5329 : utype = unsigned_type_for (type);
2706 : 5329 : range_cast (tmp, utype);
2707 : 5329 : op_rshift.fold_range (tmp_range, utype, tmp, op2);
2708 : 5329 : }
2709 : : else
2710 : 36143 : op_rshift.fold_range (tmp_range, utype, lhs, op2);
2711 : :
2712 : : // Start with ranges which can produce the LHS by right shifting the
2713 : : // result by the shift amount.
2714 : : // ie [0x08, 0xF0] = op1 << 2 will start with
2715 : : // [00001000, 11110000] = op1 << 2
2716 : : // [0x02, 0x4C] aka [00000010, 00111100]
2717 : :
2718 : : // Then create a range from the LB with the least significant upper bit
2719 : : // set, to the upper bound with all the bits set.
2720 : : // This would be [0x42, 0xFC] aka [01000010, 11111100].
2721 : :
2722 : : // Ideally we do this for each subrange, but just lump them all for now.
2723 : 41472 : unsigned low_bits = TYPE_PRECISION (utype) - shift.to_uhwi ();
2724 : 41472 : wide_int up_mask = wi::mask (low_bits, true, TYPE_PRECISION (utype));
2725 : 41472 : wide_int new_ub = wi::bit_or (up_mask, tmp_range.upper_bound ());
2726 : 41472 : wide_int new_lb = wi::set_bit (tmp_range.lower_bound (), low_bits);
2727 : 41472 : int_range<2> fill_range (utype, new_lb, new_ub);
2728 : 41472 : tmp_range.union_ (fill_range);
2729 : :
2730 : 41472 : if (utype != type)
2731 : 5329 : range_cast (tmp_range, type);
2732 : :
2733 : 41472 : r.intersect (tmp_range);
2734 : 41472 : return true;
2735 : 41472 : }
2736 : :
2737 : 4092 : return !r.varying_p ();
2738 : 45573 : }
2739 : :
2740 : : bool
2741 : 627467 : operator_rshift::op1_range (irange &r,
2742 : : tree type,
2743 : : const irange &lhs,
2744 : : const irange &op2,
2745 : : relation_trio) const
2746 : : {
2747 : 627467 : if (lhs.undefined_p ())
2748 : : return false;
2749 : 627467 : wide_int shift;
2750 : 627467 : if (op2.singleton_p (shift))
2751 : : {
2752 : : // Ignore nonsensical shifts.
2753 : 608748 : unsigned prec = TYPE_PRECISION (type);
2754 : 1217496 : if (wi::ge_p (shift,
2755 : 608748 : wi::uhwi (prec, TYPE_PRECISION (op2.type ())),
2756 : : UNSIGNED))
2757 : : return false;
2758 : 608748 : if (shift == 0)
2759 : : {
2760 : 100 : r = lhs;
2761 : 100 : return true;
2762 : : }
2763 : :
2764 : : // Folding the original operation may discard some impossible
2765 : : // ranges from the LHS.
2766 : 608648 : int_range_max lhs_refined;
2767 : 608648 : op_rshift.fold_range (lhs_refined, type, int_range<1> (type), op2);
2768 : 608648 : lhs_refined.intersect (lhs);
2769 : 608648 : if (lhs_refined.undefined_p ())
2770 : : {
2771 : 4 : r.set_undefined ();
2772 : 4 : return true;
2773 : : }
2774 : 608644 : int_range_max shift_range (op2.type (), shift, shift);
2775 : 608644 : int_range_max lb, ub;
2776 : 608644 : op_lshift.fold_range (lb, type, lhs_refined, shift_range);
2777 : : // LHS
2778 : : // 0000 0111 = OP1 >> 3
2779 : : //
2780 : : // OP1 is anything from 0011 1000 to 0011 1111. That is, a
2781 : : // range from LHS<<3 plus a mask of the 3 bits we shifted on the
2782 : : // right hand side (0x07).
2783 : 608644 : wide_int mask = wi::bit_not (wi::lshift (wi::minus_one (prec), shift));
2784 : 608644 : int_range_max mask_range (type,
2785 : 608644 : wi::zero (TYPE_PRECISION (type)),
2786 : 608644 : mask);
2787 : 608644 : op_plus.fold_range (ub, type, lb, mask_range);
2788 : 608644 : r = lb;
2789 : 608644 : r.union_ (ub);
2790 : 608644 : if (!contains_zero_p (lhs_refined))
2791 : : {
2792 : 333352 : mask_range.invert ();
2793 : 333352 : r.intersect (mask_range);
2794 : : }
2795 : 608644 : return true;
2796 : 608648 : }
2797 : : return false;
2798 : 627467 : }
2799 : :
2800 : : bool
2801 : 7849808 : operator_rshift::wi_op_overflows (wide_int &res,
2802 : : tree type,
2803 : : const wide_int &w0,
2804 : : const wide_int &w1) const
2805 : : {
2806 : 7849808 : signop sign = TYPE_SIGN (type);
2807 : 7849808 : if (wi::neg_p (w1))
2808 : 0 : res = wi::lshift (w0, -w1);
2809 : : else
2810 : : {
2811 : : // It's unclear from the C standard whether shifts can overflow.
2812 : : // The following code ignores overflow; perhaps a C standard
2813 : : // interpretation ruling is needed.
2814 : 7849848 : res = wi::rshift (w0, w1, sign);
2815 : : }
2816 : 7849808 : return false;
2817 : : }
2818 : :
2819 : : bool
2820 : 2447584 : operator_rshift::fold_range (irange &r, tree type,
2821 : : const irange &op1,
2822 : : const irange &op2,
2823 : : relation_trio rel) const
2824 : : {
2825 : 2447584 : int_range_max shift;
2826 : 2447584 : if (!get_shift_range (shift, type, op2))
2827 : : {
2828 : 551 : if (op2.undefined_p ())
2829 : 165 : r.set_undefined ();
2830 : : else
2831 : 386 : r.set_zero (type);
2832 : 551 : return true;
2833 : : }
2834 : :
2835 : 2447033 : return range_operator::fold_range (r, type, op1, shift, rel);
2836 : 2447584 : }
2837 : :
2838 : : void
2839 : 2682263 : operator_rshift::wi_fold (irange &r, tree type,
2840 : : const wide_int &lh_lb, const wide_int &lh_ub,
2841 : : const wide_int &rh_lb, const wide_int &rh_ub) const
2842 : : {
2843 : 2682263 : wi_cross_product (r, type, lh_lb, lh_ub, rh_lb, rh_ub);
2844 : 2682263 : }
2845 : :
2846 : :
2847 : : // Add a partial equivalence between the LHS and op1 for casts.
2848 : :
2849 : : relation_kind
2850 : 21448909 : operator_cast::lhs_op1_relation (const irange &lhs,
2851 : : const irange &op1,
2852 : : const irange &op2 ATTRIBUTE_UNUSED,
2853 : : relation_kind) const
2854 : : {
2855 : 21448909 : if (lhs.undefined_p () || op1.undefined_p ())
2856 : : return VREL_VARYING;
2857 : 21428023 : unsigned lhs_prec = TYPE_PRECISION (lhs.type ());
2858 : 21428023 : unsigned op1_prec = TYPE_PRECISION (op1.type ());
2859 : : // If the result gets sign extended into a larger type check first if this
2860 : : // qualifies as a partial equivalence.
2861 : 21428023 : if (TYPE_SIGN (op1.type ()) == SIGNED && lhs_prec > op1_prec)
2862 : : {
2863 : : // If the result is sign extended, and the LHS is larger than op1,
2864 : : // check if op1's range can be negative as the sign extension will
2865 : : // cause the upper bits to be 1 instead of 0, invalidating the PE.
2866 : 2967508 : int_range<3> negs = range_negatives (op1.type ());
2867 : 2967508 : negs.intersect (op1);
2868 : 2967508 : if (!negs.undefined_p ())
2869 : 2028337 : return VREL_VARYING;
2870 : 2967508 : }
2871 : :
2872 : 19399686 : unsigned prec = MIN (lhs_prec, op1_prec);
2873 : 19399686 : return bits_to_pe (prec);
2874 : : }
2875 : :
2876 : : // Return TRUE if casting from INNER to OUTER is a truncating cast.
2877 : :
2878 : : inline bool
2879 : 72867451 : operator_cast::truncating_cast_p (const irange &inner,
2880 : : const irange &outer) const
2881 : : {
2882 : 72867451 : return TYPE_PRECISION (outer.type ()) < TYPE_PRECISION (inner.type ());
2883 : : }
2884 : :
2885 : : // Return TRUE if [MIN,MAX] is inside the domain of RANGE's type.
2886 : :
2887 : : bool
2888 : 64825520 : operator_cast::inside_domain_p (const wide_int &min,
2889 : : const wide_int &max,
2890 : : const irange &range) const
2891 : : {
2892 : 64825520 : wide_int domain_min = irange_val_min (range.type ());
2893 : 64825520 : wide_int domain_max = irange_val_max (range.type ());
2894 : 64825520 : signop domain_sign = TYPE_SIGN (range.type ());
2895 : 64825520 : return (wi::le_p (min, domain_max, domain_sign)
2896 : 64825520 : && wi::le_p (max, domain_max, domain_sign)
2897 : 64825520 : && wi::ge_p (min, domain_min, domain_sign)
2898 : 129651040 : && wi::ge_p (max, domain_min, domain_sign));
2899 : 64825520 : }
2900 : :
2901 : :
2902 : : // Helper for fold_range which work on a pair at a time.
2903 : :
2904 : : void
2905 : 67012664 : operator_cast::fold_pair (irange &r, unsigned index,
2906 : : const irange &inner,
2907 : : const irange &outer) const
2908 : : {
2909 : 67012664 : tree inner_type = inner.type ();
2910 : 67012664 : tree outer_type = outer.type ();
2911 : 67012664 : signop inner_sign = TYPE_SIGN (inner_type);
2912 : 67012664 : unsigned outer_prec = TYPE_PRECISION (outer_type);
2913 : :
2914 : : // check to see if casting from INNER to OUTER is a conversion that
2915 : : // fits in the resulting OUTER type.
2916 : 67012664 : wide_int inner_lb = inner.lower_bound (index);
2917 : 67012664 : wide_int inner_ub = inner.upper_bound (index);
2918 : 67012664 : if (truncating_cast_p (inner, outer))
2919 : : {
2920 : : // We may be able to accommodate a truncating cast if the
2921 : : // resulting range can be represented in the target type...
2922 : 10084864 : if (wi::rshift (wi::sub (inner_ub, inner_lb),
2923 : 5042432 : wi::uhwi (outer_prec, TYPE_PRECISION (inner.type ())),
2924 : 15127296 : inner_sign) != 0)
2925 : : {
2926 : 2187144 : r.set_varying (outer_type);
2927 : 2187144 : return;
2928 : : }
2929 : : }
2930 : : // ...but we must still verify that the final range fits in the
2931 : : // domain. This catches -fstrict-enum restrictions where the domain
2932 : : // range is smaller than what fits in the underlying type.
2933 : 64825520 : wide_int min = wide_int::from (inner_lb, outer_prec, inner_sign);
2934 : 64825520 : wide_int max = wide_int::from (inner_ub, outer_prec, inner_sign);
2935 : 64825520 : if (inside_domain_p (min, max, outer))
2936 : 64825520 : create_possibly_reversed_range (r, outer_type, min, max);
2937 : : else
2938 : 0 : r.set_varying (outer_type);
2939 : 67015220 : }
2940 : :
2941 : :
2942 : : bool
2943 : 59004321 : operator_cast::fold_range (irange &r, tree type ATTRIBUTE_UNUSED,
2944 : : const irange &inner,
2945 : : const irange &outer,
2946 : : relation_trio) const
2947 : : {
2948 : 59004321 : if (empty_range_varying (r, type, inner, outer))
2949 : 28857 : return true;
2950 : :
2951 : 58975464 : gcc_checking_assert (outer.varying_p ());
2952 : 58975464 : gcc_checking_assert (inner.num_pairs () > 0);
2953 : :
2954 : : // Avoid a temporary by folding the first pair directly into the result.
2955 : 58975464 : fold_pair (r, 0, inner, outer);
2956 : :
2957 : : // Then process any additional pairs by unioning with their results.
2958 : 66561873 : for (unsigned x = 1; x < inner.num_pairs (); ++x)
2959 : : {
2960 : 8037200 : int_range_max tmp;
2961 : 8037200 : fold_pair (tmp, x, inner, outer);
2962 : 8037200 : r.union_ (tmp);
2963 : 8037200 : if (r.varying_p ())
2964 : 450791 : return true;
2965 : 8037200 : }
2966 : :
2967 : 58524673 : update_bitmask (r, inner, outer);
2968 : 58524673 : return true;
2969 : : }
2970 : :
2971 : : void
2972 : 58524673 : operator_cast::update_bitmask (irange &r, const irange &lh,
2973 : : const irange &rh) const
2974 : : {
2975 : 58524673 : update_known_bitmask (r, CONVERT_EXPR, lh, rh);
2976 : 58524673 : }
2977 : :
2978 : : bool
2979 : 6147782 : operator_cast::op1_range (irange &r, tree type,
2980 : : const irange &lhs,
2981 : : const irange &op2,
2982 : : relation_trio) const
2983 : : {
2984 : 6147782 : if (lhs.undefined_p ())
2985 : : return false;
2986 : 6147782 : tree lhs_type = lhs.type ();
2987 : 6147782 : gcc_checking_assert (types_compatible_p (op2.type(), type));
2988 : :
2989 : : // If we are calculating a pointer, shortcut to what we really care about.
2990 : 6147782 : if (POINTER_TYPE_P (type))
2991 : : {
2992 : : // Conversion from other pointers or a constant (including 0/NULL)
2993 : : // are straightforward.
2994 : 585931 : if (POINTER_TYPE_P (lhs.type ())
2995 : 585931 : || (lhs.singleton_p ()
2996 : 865 : && TYPE_PRECISION (lhs.type ()) >= TYPE_PRECISION (type)))
2997 : : {
2998 : 918 : r = lhs;
2999 : 918 : range_cast (r, type);
3000 : : }
3001 : : else
3002 : : {
3003 : : // If the LHS is not a pointer nor a singleton, then it is
3004 : : // either VARYING or non-zero.
3005 : 292077 : if (!lhs.undefined_p () && !contains_zero_p (lhs))
3006 : 163609 : r.set_nonzero (type);
3007 : : else
3008 : 128468 : r.set_varying (type);
3009 : : }
3010 : 292995 : r.intersect (op2);
3011 : 292995 : return true;
3012 : : }
3013 : :
3014 : 5854787 : if (truncating_cast_p (op2, lhs))
3015 : : {
3016 : 881028 : if (lhs.varying_p ())
3017 : 106612 : r.set_varying (type);
3018 : : else
3019 : : {
3020 : : // We want to insert the LHS as an unsigned value since it
3021 : : // would not trigger the signed bit of the larger type.
3022 : 774416 : int_range_max converted_lhs = lhs;
3023 : 774416 : range_cast (converted_lhs, unsigned_type_for (lhs_type));
3024 : 774416 : range_cast (converted_lhs, type);
3025 : : // Start by building the positive signed outer range for the type.
3026 : 774416 : wide_int lim = wi::set_bit_in_zero (TYPE_PRECISION (lhs_type),
3027 : 1548832 : TYPE_PRECISION (type));
3028 : 774416 : create_possibly_reversed_range (r, type, lim,
3029 : 774416 : wi::max_value (TYPE_PRECISION (type),
3030 : : SIGNED));
3031 : : // For the signed part, we need to simply union the 2 ranges now.
3032 : 774416 : r.union_ (converted_lhs);
3033 : :
3034 : : // Create maximal negative number outside of LHS bits.
3035 : 774416 : lim = wi::mask (TYPE_PRECISION (lhs_type), true,
3036 : 1548832 : TYPE_PRECISION (type));
3037 : : // Add this to the unsigned LHS range(s).
3038 : 774416 : int_range_max lim_range (type, lim, lim);
3039 : 774416 : int_range_max lhs_neg;
3040 : 774416 : range_op_handler (PLUS_EXPR).fold_range (lhs_neg, type,
3041 : : converted_lhs, lim_range);
3042 : : // lhs_neg now has all the negative versions of the LHS.
3043 : : // Now union in all the values from SIGNED MIN (0x80000) to
3044 : : // lim-1 in order to fill in all the ranges with the upper
3045 : : // bits set.
3046 : :
3047 : : // PR 97317. If the lhs has only 1 bit less precision than the rhs,
3048 : : // we don't need to create a range from min to lim-1
3049 : : // calculate neg range traps trying to create [lim, lim - 1].
3050 : 774416 : wide_int min_val = wi::min_value (TYPE_PRECISION (type), SIGNED);
3051 : 774416 : if (lim != min_val)
3052 : : {
3053 : 772723 : int_range_max neg (type,
3054 : 1545446 : wi::min_value (TYPE_PRECISION (type),
3055 : : SIGNED),
3056 : 1545446 : lim - 1);
3057 : 772723 : lhs_neg.union_ (neg);
3058 : 772723 : }
3059 : : // And finally, munge the signed and unsigned portions.
3060 : 774416 : r.union_ (lhs_neg);
3061 : 774416 : }
3062 : : // And intersect with any known value passed in the extra operand.
3063 : 881028 : r.intersect (op2);
3064 : 881028 : return true;
3065 : : }
3066 : :
3067 : 4973759 : int_range_max tmp;
3068 : 4973759 : if (TYPE_PRECISION (lhs_type) == TYPE_PRECISION (type))
3069 : 3913894 : tmp = lhs;
3070 : : else
3071 : : {
3072 : : // The cast is not truncating, and the range is restricted to
3073 : : // the range of the RHS by this assignment.
3074 : : //
3075 : : // Cast the range of the RHS to the type of the LHS.
3076 : 1059865 : fold_range (tmp, lhs_type, int_range<1> (type), int_range<1> (lhs_type));
3077 : : // Intersect this with the LHS range will produce the range,
3078 : : // which will be cast to the RHS type before returning.
3079 : 1059865 : tmp.intersect (lhs);
3080 : : }
3081 : :
3082 : : // Cast the calculated range to the type of the RHS.
3083 : 4973759 : fold_range (r, type, tmp, int_range<1> (type));
3084 : 4973759 : return true;
3085 : 4973759 : }
3086 : :
3087 : :
3088 : : class operator_logical_and : public range_operator
3089 : : {
3090 : : using range_operator::fold_range;
3091 : : using range_operator::op1_range;
3092 : : using range_operator::op2_range;
3093 : : public:
3094 : : virtual bool fold_range (irange &r, tree type,
3095 : : const irange &lh,
3096 : : const irange &rh,
3097 : : relation_trio rel = TRIO_VARYING) const;
3098 : : virtual bool op1_range (irange &r, tree type,
3099 : : const irange &lhs,
3100 : : const irange &op2,
3101 : : relation_trio rel = TRIO_VARYING) const;
3102 : : virtual bool op2_range (irange &r, tree type,
3103 : : const irange &lhs,
3104 : : const irange &op1,
3105 : : relation_trio rel = TRIO_VARYING) const;
3106 : : // Check compatibility of all operands.
3107 : 0 : bool operand_check_p (tree t1, tree t2, tree t3) const final override
3108 : 0 : { return range_compatible_p (t1, t2) && range_compatible_p (t1, t3); }
3109 : : } op_logical_and;
3110 : :
3111 : : bool
3112 : 0 : operator_logical_and::fold_range (irange &r, tree type,
3113 : : const irange &lh,
3114 : : const irange &rh,
3115 : : relation_trio) const
3116 : : {
3117 : 0 : if (empty_range_varying (r, type, lh, rh))
3118 : 0 : return true;
3119 : :
3120 : : // Precision of LHS and both operands must match.
3121 : 0 : if (TYPE_PRECISION (lh.type ()) != TYPE_PRECISION (type)
3122 : 0 : || TYPE_PRECISION (type) != TYPE_PRECISION (rh.type ()))
3123 : 0 : return false;
3124 : :
3125 : : // 0 && anything is 0.
3126 : 0 : if ((wi::eq_p (lh.lower_bound (), 0) && wi::eq_p (lh.upper_bound (), 0))
3127 : 0 : || (wi::eq_p (lh.lower_bound (), 0) && wi::eq_p (rh.upper_bound (), 0)))
3128 : 0 : r = range_false (type);
3129 : 0 : else if (contains_zero_p (lh) || contains_zero_p (rh))
3130 : : // To reach this point, there must be a logical 1 on each side, and
3131 : : // the only remaining question is whether there is a zero or not.
3132 : 0 : r = range_true_and_false (type);
3133 : : else
3134 : 0 : r = range_true (type);
3135 : : return true;
3136 : : }
3137 : :
3138 : : bool
3139 : 791507 : operator_logical_and::op1_range (irange &r, tree type,
3140 : : const irange &lhs,
3141 : : const irange &op2 ATTRIBUTE_UNUSED,
3142 : : relation_trio) const
3143 : : {
3144 : 791507 : switch (get_bool_state (r, lhs, type))
3145 : : {
3146 : 418095 : case BRS_TRUE:
3147 : : // A true result means both sides of the AND must be true.
3148 : 418095 : r = range_true (type);
3149 : 418095 : break;
3150 : 373412 : default:
3151 : : // Any other result means only one side has to be false, the
3152 : : // other side can be anything. So we cannot be sure of any
3153 : : // result here.
3154 : 373412 : r = range_true_and_false (type);
3155 : 373412 : break;
3156 : : }
3157 : 791507 : return true;
3158 : : }
3159 : :
3160 : : bool
3161 : 0 : operator_logical_and::op2_range (irange &r, tree type,
3162 : : const irange &lhs,
3163 : : const irange &op1,
3164 : : relation_trio) const
3165 : : {
3166 : 0 : return operator_logical_and::op1_range (r, type, lhs, op1);
3167 : : }
3168 : :
3169 : :
3170 : : void
3171 : 5812255 : operator_bitwise_and::update_bitmask (irange &r, const irange &lh,
3172 : : const irange &rh) const
3173 : : {
3174 : 5812255 : update_known_bitmask (r, BIT_AND_EXPR, lh, rh);
3175 : 5812255 : }
3176 : :
3177 : : // Optimize BIT_AND_EXPR, BIT_IOR_EXPR and BIT_XOR_EXPR of signed types
3178 : : // by considering the number of leading redundant sign bit copies.
3179 : : // clrsb (X op Y) = min (clrsb (X), clrsb (Y)), so for example
3180 : : // [-1, 0] op [-1, 0] is [-1, 0] (where nonzero_bits doesn't help).
3181 : : static bool
3182 : 219663 : wi_optimize_signed_bitwise_op (irange &r, tree type,
3183 : : const wide_int &lh_lb, const wide_int &lh_ub,
3184 : : const wide_int &rh_lb, const wide_int &rh_ub)
3185 : : {
3186 : 439326 : int lh_clrsb = MIN (wi::clrsb (lh_lb), wi::clrsb (lh_ub));
3187 : 439326 : int rh_clrsb = MIN (wi::clrsb (rh_lb), wi::clrsb (rh_ub));
3188 : 219663 : int new_clrsb = MIN (lh_clrsb, rh_clrsb);
3189 : 219663 : if (new_clrsb == 0)
3190 : : return false;
3191 : 6928 : int type_prec = TYPE_PRECISION (type);
3192 : 6928 : int rprec = (type_prec - new_clrsb) - 1;
3193 : 6928 : value_range_with_overflow (r, type,
3194 : 13856 : wi::mask (rprec, true, type_prec),
3195 : 6928 : wi::mask (rprec, false, type_prec));
3196 : 6928 : return true;
3197 : : }
3198 : :
3199 : : // An AND of 8,16, 32 or 64 bits can produce a partial equivalence between
3200 : : // the LHS and op1.
3201 : :
3202 : : relation_kind
3203 : 5684544 : operator_bitwise_and::lhs_op1_relation (const irange &lhs,
3204 : : const irange &op1,
3205 : : const irange &op2,
3206 : : relation_kind) const
3207 : : {
3208 : 5684544 : if (lhs.undefined_p () || op1.undefined_p () || op2.undefined_p ())
3209 : : return VREL_VARYING;
3210 : 5680564 : if (!op2.singleton_p ())
3211 : : return VREL_VARYING;
3212 : : // if val == 0xff or 0xFFFF OR 0Xffffffff OR 0Xffffffffffffffff, return TRUE
3213 : 3301852 : int prec1 = TYPE_PRECISION (op1.type ());
3214 : 3301852 : int prec2 = TYPE_PRECISION (op2.type ());
3215 : 3301852 : int mask_prec = 0;
3216 : 3301852 : wide_int mask = op2.lower_bound ();
3217 : 3301852 : if (wi::eq_p (mask, wi::mask (8, false, prec2)))
3218 : : mask_prec = 8;
3219 : 3212559 : else if (wi::eq_p (mask, wi::mask (16, false, prec2)))
3220 : : mask_prec = 16;
3221 : 3189289 : else if (wi::eq_p (mask, wi::mask (32, false, prec2)))
3222 : : mask_prec = 32;
3223 : 3019509 : else if (wi::eq_p (mask, wi::mask (64, false, prec2)))
3224 : 673 : mask_prec = 64;
3225 : 3301852 : return bits_to_pe (MIN (prec1, mask_prec));
3226 : 3301852 : }
3227 : :
3228 : : // Optimize BIT_AND_EXPR and BIT_IOR_EXPR in terms of a mask if
3229 : : // possible. Basically, see if we can optimize:
3230 : : //
3231 : : // [LB, UB] op Z
3232 : : // into:
3233 : : // [LB op Z, UB op Z]
3234 : : //
3235 : : // If the optimization was successful, accumulate the range in R and
3236 : : // return TRUE.
3237 : :
3238 : : static bool
3239 : 18064364 : wi_optimize_and_or (irange &r,
3240 : : enum tree_code code,
3241 : : tree type,
3242 : : const wide_int &lh_lb, const wide_int &lh_ub,
3243 : : const wide_int &rh_lb, const wide_int &rh_ub)
3244 : : {
3245 : : // Calculate the singleton mask among the ranges, if any.
3246 : 18064364 : wide_int lower_bound, upper_bound, mask;
3247 : 18064364 : if (wi::eq_p (rh_lb, rh_ub))
3248 : : {
3249 : 16953574 : mask = rh_lb;
3250 : 16953574 : lower_bound = lh_lb;
3251 : 16953574 : upper_bound = lh_ub;
3252 : : }
3253 : 1110790 : else if (wi::eq_p (lh_lb, lh_ub))
3254 : : {
3255 : 153961 : mask = lh_lb;
3256 : 153961 : lower_bound = rh_lb;
3257 : 153961 : upper_bound = rh_ub;
3258 : : }
3259 : : else
3260 : : return false;
3261 : :
3262 : : // If Z is a constant which (for op | its bitwise not) has n
3263 : : // consecutive least significant bits cleared followed by m 1
3264 : : // consecutive bits set immediately above it and either
3265 : : // m + n == precision, or (x >> (m + n)) == (y >> (m + n)).
3266 : : //
3267 : : // The least significant n bits of all the values in the range are
3268 : : // cleared or set, the m bits above it are preserved and any bits
3269 : : // above these are required to be the same for all values in the
3270 : : // range.
3271 : 17107535 : wide_int w = mask;
3272 : 17107535 : int m = 0, n = 0;
3273 : 17107535 : if (code == BIT_IOR_EXPR)
3274 : 5676214 : w = ~w;
3275 : 17107535 : if (wi::eq_p (w, 0))
3276 : 6253799 : n = w.get_precision ();
3277 : : else
3278 : : {
3279 : 10853736 : n = wi::ctz (w);
3280 : 10853744 : w = ~(w | wi::mask (n, false, w.get_precision ()));
3281 : 10853736 : if (wi::eq_p (w, 0))
3282 : 6951107 : m = w.get_precision () - n;
3283 : : else
3284 : 3902629 : m = wi::ctz (w) - n;
3285 : : }
3286 : 17107535 : wide_int new_mask = wi::mask (m + n, true, w.get_precision ());
3287 : 17107543 : if ((new_mask & lower_bound) != (new_mask & upper_bound))
3288 : : return false;
3289 : :
3290 : 13669714 : wide_int res_lb, res_ub;
3291 : 13669714 : if (code == BIT_AND_EXPR)
3292 : : {
3293 : 8182519 : res_lb = wi::bit_and (lower_bound, mask);
3294 : 8182519 : res_ub = wi::bit_and (upper_bound, mask);
3295 : : }
3296 : 5487195 : else if (code == BIT_IOR_EXPR)
3297 : : {
3298 : 5487195 : res_lb = wi::bit_or (lower_bound, mask);
3299 : 5487195 : res_ub = wi::bit_or (upper_bound, mask);
3300 : : }
3301 : : else
3302 : 0 : gcc_unreachable ();
3303 : 13669714 : value_range_with_overflow (r, type, res_lb, res_ub);
3304 : :
3305 : : // Furthermore, if the mask is non-zero, an IOR cannot contain zero.
3306 : 13669714 : if (code == BIT_IOR_EXPR && wi::ne_p (mask, 0))
3307 : : {
3308 : 2794836 : int_range<2> tmp;
3309 : 2794836 : tmp.set_nonzero (type);
3310 : 2794836 : r.intersect (tmp);
3311 : 2794836 : }
3312 : 13669714 : return true;
3313 : 48841621 : }
3314 : :
3315 : : // For range [LB, UB] compute two wide_int bit masks.
3316 : : //
3317 : : // In the MAYBE_NONZERO bit mask, if some bit is unset, it means that
3318 : : // for all numbers in the range the bit is 0, otherwise it might be 0
3319 : : // or 1.
3320 : : //
3321 : : // In the MUSTBE_NONZERO bit mask, if some bit is set, it means that
3322 : : // for all numbers in the range the bit is 1, otherwise it might be 0
3323 : : // or 1.
3324 : :
3325 : : void
3326 : 10021085 : wi_set_zero_nonzero_bits (tree type,
3327 : : const wide_int &lb, const wide_int &ub,
3328 : : wide_int &maybe_nonzero,
3329 : : wide_int &mustbe_nonzero)
3330 : : {
3331 : 10021085 : signop sign = TYPE_SIGN (type);
3332 : :
3333 : 10021085 : if (wi::eq_p (lb, ub))
3334 : 3985582 : maybe_nonzero = mustbe_nonzero = lb;
3335 : 6035503 : else if (wi::ge_p (lb, 0, sign) || wi::lt_p (ub, 0, sign))
3336 : : {
3337 : 5059403 : wide_int xor_mask = lb ^ ub;
3338 : 5059403 : maybe_nonzero = lb | ub;
3339 : 5059403 : mustbe_nonzero = lb & ub;
3340 : 5059403 : if (xor_mask != 0)
3341 : : {
3342 : 5059403 : wide_int mask = wi::mask (wi::floor_log2 (xor_mask), false,
3343 : 10118806 : maybe_nonzero.get_precision ());
3344 : 5059403 : maybe_nonzero = maybe_nonzero | mask;
3345 : 5059406 : mustbe_nonzero = wi::bit_and_not (mustbe_nonzero, mask);
3346 : 5059403 : }
3347 : 5059403 : }
3348 : : else
3349 : : {
3350 : 976100 : maybe_nonzero = wi::minus_one (lb.get_precision ());
3351 : 976100 : mustbe_nonzero = wi::zero (lb.get_precision ());
3352 : : }
3353 : 10021085 : }
3354 : :
3355 : : void
3356 : 11868016 : operator_bitwise_and::wi_fold (irange &r, tree type,
3357 : : const wide_int &lh_lb,
3358 : : const wide_int &lh_ub,
3359 : : const wide_int &rh_lb,
3360 : : const wide_int &rh_ub) const
3361 : : {
3362 : 11868016 : if (wi_optimize_and_or (r, BIT_AND_EXPR, type, lh_lb, lh_ub, rh_lb, rh_ub))
3363 : 8183272 : return;
3364 : :
3365 : 3685497 : wide_int maybe_nonzero_lh, mustbe_nonzero_lh;
3366 : 3685497 : wide_int maybe_nonzero_rh, mustbe_nonzero_rh;
3367 : 3685497 : wi_set_zero_nonzero_bits (type, lh_lb, lh_ub,
3368 : : maybe_nonzero_lh, mustbe_nonzero_lh);
3369 : 3685497 : wi_set_zero_nonzero_bits (type, rh_lb, rh_ub,
3370 : : maybe_nonzero_rh, mustbe_nonzero_rh);
3371 : :
3372 : 3685497 : wide_int new_lb = mustbe_nonzero_lh & mustbe_nonzero_rh;
3373 : 3685497 : wide_int new_ub = maybe_nonzero_lh & maybe_nonzero_rh;
3374 : 3685497 : signop sign = TYPE_SIGN (type);
3375 : 3685497 : unsigned prec = TYPE_PRECISION (type);
3376 : : // If both input ranges contain only negative values, we can
3377 : : // truncate the result range maximum to the minimum of the
3378 : : // input range maxima.
3379 : 3685497 : if (wi::lt_p (lh_ub, 0, sign) && wi::lt_p (rh_ub, 0, sign))
3380 : : {
3381 : 5549 : new_ub = wi::min (new_ub, lh_ub, sign);
3382 : 5549 : new_ub = wi::min (new_ub, rh_ub, sign);
3383 : : }
3384 : : // If either input range contains only non-negative values
3385 : : // we can truncate the result range maximum to the respective
3386 : : // maximum of the input range.
3387 : 3685497 : if (wi::ge_p (lh_lb, 0, sign))
3388 : 3006779 : new_ub = wi::min (new_ub, lh_ub, sign);
3389 : 3685497 : if (wi::ge_p (rh_lb, 0, sign))
3390 : 3559651 : new_ub = wi::min (new_ub, rh_ub, sign);
3391 : : // PR68217: In case of signed & sign-bit-CST should
3392 : : // result in [-INF, 0] instead of [-INF, INF].
3393 : 3685497 : if (wi::gt_p (new_lb, new_ub, sign))
3394 : : {
3395 : 75353 : wide_int sign_bit = wi::set_bit_in_zero (prec - 1, prec);
3396 : 75353 : if (sign == SIGNED
3397 : 75353 : && ((wi::eq_p (lh_lb, lh_ub)
3398 : 0 : && !wi::cmps (lh_lb, sign_bit))
3399 : 75353 : || (wi::eq_p (rh_lb, rh_ub)
3400 : 20392 : && !wi::cmps (rh_lb, sign_bit))))
3401 : : {
3402 : 0 : new_lb = wi::min_value (prec, sign);
3403 : 0 : new_ub = wi::zero (prec);
3404 : : }
3405 : 75353 : }
3406 : : // If the limits got swapped around, return varying.
3407 : 3685497 : if (wi::gt_p (new_lb, new_ub,sign))
3408 : : {
3409 : 75353 : if (sign == SIGNED
3410 : 75353 : && wi_optimize_signed_bitwise_op (r, type,
3411 : : lh_lb, lh_ub,
3412 : : rh_lb, rh_ub))
3413 : 753 : return;
3414 : 74600 : r.set_varying (type);
3415 : : }
3416 : : else
3417 : 3610144 : value_range_with_overflow (r, type, new_lb, new_ub);
3418 : 3685497 : }
3419 : :
3420 : : static void
3421 : 431012 : set_nonzero_range_from_mask (irange &r, tree type, const irange &lhs)
3422 : : {
3423 : 431012 : if (lhs.undefined_p () || contains_zero_p (lhs))
3424 : 240718 : r.set_varying (type);
3425 : : else
3426 : 190294 : r.set_nonzero (type);
3427 : 431012 : }
3428 : :
3429 : : /* Find out smallest RES where RES > VAL && (RES & MASK) == RES, if any
3430 : : (otherwise return VAL). VAL and MASK must be zero-extended for
3431 : : precision PREC. If SGNBIT is non-zero, first xor VAL with SGNBIT
3432 : : (to transform signed values into unsigned) and at the end xor
3433 : : SGNBIT back. */
3434 : :
3435 : : wide_int
3436 : 204452 : masked_increment (const wide_int &val_in, const wide_int &mask,
3437 : : const wide_int &sgnbit, unsigned int prec)
3438 : : {
3439 : 204452 : wide_int bit = wi::one (prec), res;
3440 : 204452 : unsigned int i;
3441 : :
3442 : 204452 : wide_int val = val_in ^ sgnbit;
3443 : 3977767 : for (i = 0; i < prec; i++, bit += bit)
3444 : : {
3445 : 3762376 : res = mask;
3446 : 3762376 : if ((res & bit) == 0)
3447 : 3363857 : continue;
3448 : 398519 : res = bit - 1;
3449 : 398519 : res = wi::bit_and_not (val + bit, res);
3450 : 398519 : res &= mask;
3451 : 398519 : if (wi::gtu_p (res, val))
3452 : 193513 : return res ^ sgnbit;
3453 : : }
3454 : 10939 : return val ^ sgnbit;
3455 : 204452 : }
3456 : :
3457 : : // This was shamelessly stolen from register_edge_assert_for_2 and
3458 : : // adjusted to work with iranges.
3459 : :
3460 : : void
3461 : 2264711 : operator_bitwise_and::simple_op1_range_solver (irange &r, tree type,
3462 : : const irange &lhs,
3463 : : const irange &op2) const
3464 : : {
3465 : 2264711 : if (!op2.singleton_p ())
3466 : : {
3467 : 430978 : set_nonzero_range_from_mask (r, type, lhs);
3468 : 871361 : return;
3469 : : }
3470 : 1833733 : unsigned int nprec = TYPE_PRECISION (type);
3471 : 1833733 : wide_int cst2v = op2.lower_bound ();
3472 : 1833733 : bool cst2n = wi::neg_p (cst2v, TYPE_SIGN (type));
3473 : 1833733 : wide_int sgnbit;
3474 : 1833733 : if (cst2n)
3475 : 202630 : sgnbit = wi::set_bit_in_zero (nprec - 1, nprec);
3476 : : else
3477 : 1631103 : sgnbit = wi::zero (nprec);
3478 : :
3479 : : // Solve [lhs.lower_bound (), +INF] = x & MASK.
3480 : : //
3481 : : // Minimum unsigned value for >= if (VAL & CST2) == VAL is VAL and
3482 : : // maximum unsigned value is ~0. For signed comparison, if CST2
3483 : : // doesn't have the most significant bit set, handle it similarly. If
3484 : : // CST2 has MSB set, the minimum is the same, and maximum is ~0U/2.
3485 : 1833733 : wide_int valv = lhs.lower_bound ();
3486 : 1833733 : wide_int minv = valv & cst2v, maxv;
3487 : 1833733 : bool we_know_nothing = false;
3488 : 1833733 : if (minv != valv)
3489 : : {
3490 : : // If (VAL & CST2) != VAL, X & CST2 can't be equal to VAL.
3491 : 65873 : minv = masked_increment (valv, cst2v, sgnbit, nprec);
3492 : 65873 : if (minv == valv)
3493 : : {
3494 : : // If we can't determine anything on this bound, fall
3495 : : // through and conservatively solve for the other end point.
3496 : 1833733 : we_know_nothing = true;
3497 : : }
3498 : : }
3499 : 3464836 : maxv = wi::mask (nprec - (cst2n ? 1 : 0), false, nprec);
3500 : 1833733 : if (we_know_nothing)
3501 : 1534 : r.set_varying (type);
3502 : : else
3503 : 1832199 : create_possibly_reversed_range (r, type, minv, maxv);
3504 : :
3505 : : // Solve [-INF, lhs.upper_bound ()] = x & MASK.
3506 : : //
3507 : : // Minimum unsigned value for <= is 0 and maximum unsigned value is
3508 : : // VAL | ~CST2 if (VAL & CST2) == VAL. Otherwise, find smallest
3509 : : // VAL2 where
3510 : : // VAL2 > VAL && (VAL2 & CST2) == VAL2 and use (VAL2 - 1) | ~CST2
3511 : : // as maximum.
3512 : : // For signed comparison, if CST2 doesn't have most significant bit
3513 : : // set, handle it similarly. If CST2 has MSB set, the maximum is
3514 : : // the same and minimum is INT_MIN.
3515 : 1833733 : valv = lhs.upper_bound ();
3516 : 1833733 : minv = valv & cst2v;
3517 : 1833733 : if (minv == valv)
3518 : 1695154 : maxv = valv;
3519 : : else
3520 : : {
3521 : 138579 : maxv = masked_increment (valv, cst2v, sgnbit, nprec);
3522 : 138579 : if (maxv == valv)
3523 : : {
3524 : : // If we couldn't determine anything on either bound, return
3525 : : // undefined.
3526 : 9405 : if (we_know_nothing)
3527 : 1364 : r.set_undefined ();
3528 : 9405 : return;
3529 : : }
3530 : 129174 : maxv -= 1;
3531 : : }
3532 : 1824328 : maxv |= ~cst2v;
3533 : 1824328 : minv = sgnbit;
3534 : 1824328 : int_range<2> upper_bits;
3535 : 1824328 : create_possibly_reversed_range (upper_bits, type, minv, maxv);
3536 : 1824328 : r.intersect (upper_bits);
3537 : 1833733 : }
3538 : :
3539 : : bool
3540 : 2766008 : operator_bitwise_and::op1_range (irange &r, tree type,
3541 : : const irange &lhs,
3542 : : const irange &op2,
3543 : : relation_trio) const
3544 : : {
3545 : 2766008 : if (lhs.undefined_p ())
3546 : : return false;
3547 : 2766008 : if (types_compatible_p (type, boolean_type_node))
3548 : 791507 : return op_logical_and.op1_range (r, type, lhs, op2);
3549 : :
3550 : 1974501 : r.set_undefined ();
3551 : 4239212 : for (unsigned i = 0; i < lhs.num_pairs (); ++i)
3552 : : {
3553 : 4529422 : int_range_max chunk (lhs.type (),
3554 : 4529422 : lhs.lower_bound (i),
3555 : 4529422 : lhs.upper_bound (i));
3556 : 2264711 : int_range_max res;
3557 : 2264711 : simple_op1_range_solver (res, type, chunk, op2);
3558 : 2264711 : r.union_ (res);
3559 : 2264711 : }
3560 : 1974501 : if (r.undefined_p ())
3561 : 34 : set_nonzero_range_from_mask (r, type, lhs);
3562 : :
3563 : : // For MASK == op1 & MASK, all the bits in MASK must be set in op1.
3564 : 1974501 : wide_int mask;
3565 : 1974501 : if (lhs == op2 && lhs.singleton_p (mask))
3566 : : {
3567 : 264959 : r.update_bitmask (irange_bitmask (mask, ~mask));
3568 : 264959 : return true;
3569 : : }
3570 : :
3571 : : // For 0 = op1 & MASK, op1 is ~MASK.
3572 : 1709542 : if (lhs.zero_p () && op2.singleton_p ())
3573 : : {
3574 : 503901 : wide_int nz = wi::bit_not (op2.get_nonzero_bits ());
3575 : 503901 : int_range<2> tmp (type);
3576 : 503901 : tmp.set_nonzero_bits (nz);
3577 : 503901 : r.intersect (tmp);
3578 : 503901 : }
3579 : : return true;
3580 : 1974501 : }
3581 : :
3582 : : bool
3583 : 689099 : operator_bitwise_and::op2_range (irange &r, tree type,
3584 : : const irange &lhs,
3585 : : const irange &op1,
3586 : : relation_trio) const
3587 : : {
3588 : 689099 : return operator_bitwise_and::op1_range (r, type, lhs, op1);
3589 : : }
3590 : :
3591 : :
3592 : : class operator_logical_or : public range_operator
3593 : : {
3594 : : using range_operator::fold_range;
3595 : : using range_operator::op1_range;
3596 : : using range_operator::op2_range;
3597 : : public:
3598 : : virtual bool fold_range (irange &r, tree type,
3599 : : const irange &lh,
3600 : : const irange &rh,
3601 : : relation_trio rel = TRIO_VARYING) const;
3602 : : virtual bool op1_range (irange &r, tree type,
3603 : : const irange &lhs,
3604 : : const irange &op2,
3605 : : relation_trio rel = TRIO_VARYING) const;
3606 : : virtual bool op2_range (irange &r, tree type,
3607 : : const irange &lhs,
3608 : : const irange &op1,
3609 : : relation_trio rel = TRIO_VARYING) const;
3610 : : // Check compatibility of all operands.
3611 : 0 : bool operand_check_p (tree t1, tree t2, tree t3) const final override
3612 : 0 : { return range_compatible_p (t1, t2) && range_compatible_p (t1, t3); }
3613 : : } op_logical_or;
3614 : :
3615 : : bool
3616 : 0 : operator_logical_or::fold_range (irange &r, tree type ATTRIBUTE_UNUSED,
3617 : : const irange &lh,
3618 : : const irange &rh,
3619 : : relation_trio) const
3620 : : {
3621 : 0 : if (empty_range_varying (r, type, lh, rh))
3622 : 0 : return true;
3623 : :
3624 : 0 : r = lh;
3625 : 0 : r.union_ (rh);
3626 : 0 : return true;
3627 : : }
3628 : :
3629 : : bool
3630 : 330085 : operator_logical_or::op1_range (irange &r, tree type,
3631 : : const irange &lhs,
3632 : : const irange &op2 ATTRIBUTE_UNUSED,
3633 : : relation_trio) const
3634 : : {
3635 : 330085 : switch (get_bool_state (r, lhs, type))
3636 : : {
3637 : 195407 : case BRS_FALSE:
3638 : : // A false result means both sides of the OR must be false.
3639 : 195407 : r = range_false (type);
3640 : 195407 : break;
3641 : 134678 : default:
3642 : : // Any other result means only one side has to be true, the
3643 : : // other side can be anything. so we can't be sure of any result
3644 : : // here.
3645 : 134678 : r = range_true_and_false (type);
3646 : 134678 : break;
3647 : : }
3648 : 330085 : return true;
3649 : : }
3650 : :
3651 : : bool
3652 : 0 : operator_logical_or::op2_range (irange &r, tree type,
3653 : : const irange &lhs,
3654 : : const irange &op1,
3655 : : relation_trio) const
3656 : : {
3657 : 0 : return operator_logical_or::op1_range (r, type, lhs, op1);
3658 : : }
3659 : :
3660 : :
3661 : : void
3662 : 2146501 : operator_bitwise_or::update_bitmask (irange &r, const irange &lh,
3663 : : const irange &rh) const
3664 : : {
3665 : 2146501 : update_known_bitmask (r, BIT_IOR_EXPR, lh, rh);
3666 : 2146501 : }
3667 : :
3668 : : void
3669 : 6196348 : operator_bitwise_or::wi_fold (irange &r, tree type,
3670 : : const wide_int &lh_lb,
3671 : : const wide_int &lh_ub,
3672 : : const wide_int &rh_lb,
3673 : : const wide_int &rh_ub) const
3674 : : {
3675 : 6196348 : if (wi_optimize_and_or (r, BIT_IOR_EXPR, type, lh_lb, lh_ub, rh_lb, rh_ub))
3676 : 5658805 : return;
3677 : :
3678 : 709153 : wide_int maybe_nonzero_lh, mustbe_nonzero_lh;
3679 : 709153 : wide_int maybe_nonzero_rh, mustbe_nonzero_rh;
3680 : 709153 : wi_set_zero_nonzero_bits (type, lh_lb, lh_ub,
3681 : : maybe_nonzero_lh, mustbe_nonzero_lh);
3682 : 709153 : wi_set_zero_nonzero_bits (type, rh_lb, rh_ub,
3683 : : maybe_nonzero_rh, mustbe_nonzero_rh);
3684 : 709153 : wide_int new_lb = mustbe_nonzero_lh | mustbe_nonzero_rh;
3685 : 709153 : wide_int new_ub = maybe_nonzero_lh | maybe_nonzero_rh;
3686 : 709153 : signop sign = TYPE_SIGN (type);
3687 : : // If the input ranges contain only positive values we can
3688 : : // truncate the minimum of the result range to the maximum
3689 : : // of the input range minima.
3690 : 709153 : if (wi::ge_p (lh_lb, 0, sign)
3691 : 709153 : && wi::ge_p (rh_lb, 0, sign))
3692 : : {
3693 : 528142 : new_lb = wi::max (new_lb, lh_lb, sign);
3694 : 528142 : new_lb = wi::max (new_lb, rh_lb, sign);
3695 : : }
3696 : : // If either input range contains only negative values
3697 : : // we can truncate the minimum of the result range to the
3698 : : // respective minimum range.
3699 : 709153 : if (wi::lt_p (lh_ub, 0, sign))
3700 : 5095 : new_lb = wi::max (new_lb, lh_lb, sign);
3701 : 709153 : if (wi::lt_p (rh_ub, 0, sign))
3702 : 4412 : new_lb = wi::max (new_lb, rh_lb, sign);
3703 : : // If the limits got swapped around, return a conservative range.
3704 : 709153 : if (wi::gt_p (new_lb, new_ub, sign))
3705 : : {
3706 : : // Make sure that nonzero|X is nonzero.
3707 : 171610 : if (wi::gt_p (lh_lb, 0, sign)
3708 : 167643 : || wi::gt_p (rh_lb, 0, sign)
3709 : 108366 : || wi::lt_p (lh_ub, 0, sign)
3710 : 279976 : || wi::lt_p (rh_ub, 0, sign))
3711 : 63244 : r.set_nonzero (type);
3712 : 108366 : else if (sign == SIGNED
3713 : 108366 : && wi_optimize_signed_bitwise_op (r, type,
3714 : : lh_lb, lh_ub,
3715 : : rh_lb, rh_ub))
3716 : : return;
3717 : : else
3718 : 106951 : r.set_varying (type);
3719 : 170195 : return;
3720 : : }
3721 : 537543 : value_range_with_overflow (r, type, new_lb, new_ub);
3722 : 709173 : }
3723 : :
3724 : : bool
3725 : 495313 : operator_bitwise_or::op1_range (irange &r, tree type,
3726 : : const irange &lhs,
3727 : : const irange &op2,
3728 : : relation_trio) const
3729 : : {
3730 : 495313 : if (lhs.undefined_p ())
3731 : : return false;
3732 : : // If this is really a logical wi_fold, call that.
3733 : 495313 : if (types_compatible_p (type, boolean_type_node))
3734 : 330085 : return op_logical_or.op1_range (r, type, lhs, op2);
3735 : :
3736 : 165228 : if (lhs.zero_p ())
3737 : : {
3738 : 49889 : r.set_zero (type);
3739 : 49889 : return true;
3740 : : }
3741 : 115339 : r.set_varying (type);
3742 : 115339 : return true;
3743 : : }
3744 : :
3745 : : bool
3746 : 247486 : operator_bitwise_or::op2_range (irange &r, tree type,
3747 : : const irange &lhs,
3748 : : const irange &op1,
3749 : : relation_trio) const
3750 : : {
3751 : 247486 : return operator_bitwise_or::op1_range (r, type, lhs, op1);
3752 : : }
3753 : :
3754 : : void
3755 : 197386 : operator_bitwise_xor::update_bitmask (irange &r, const irange &lh,
3756 : : const irange &rh) const
3757 : : {
3758 : 197386 : update_known_bitmask (r, BIT_XOR_EXPR, lh, rh);
3759 : 197386 : }
3760 : :
3761 : : void
3762 : 303458 : operator_bitwise_xor::wi_fold (irange &r, tree type,
3763 : : const wide_int &lh_lb,
3764 : : const wide_int &lh_ub,
3765 : : const wide_int &rh_lb,
3766 : : const wide_int &rh_ub) const
3767 : : {
3768 : 303458 : signop sign = TYPE_SIGN (type);
3769 : 303458 : wide_int maybe_nonzero_lh, mustbe_nonzero_lh;
3770 : 303458 : wide_int maybe_nonzero_rh, mustbe_nonzero_rh;
3771 : 303458 : wi_set_zero_nonzero_bits (type, lh_lb, lh_ub,
3772 : : maybe_nonzero_lh, mustbe_nonzero_lh);
3773 : 303458 : wi_set_zero_nonzero_bits (type, rh_lb, rh_ub,
3774 : : maybe_nonzero_rh, mustbe_nonzero_rh);
3775 : :
3776 : 910374 : wide_int result_zero_bits = ((mustbe_nonzero_lh & mustbe_nonzero_rh)
3777 : 910374 : | ~(maybe_nonzero_lh | maybe_nonzero_rh));
3778 : 303458 : wide_int result_one_bits
3779 : 606916 : = (wi::bit_and_not (mustbe_nonzero_lh, maybe_nonzero_rh)
3780 : 606916 : | wi::bit_and_not (mustbe_nonzero_rh, maybe_nonzero_lh));
3781 : 303458 : wide_int new_ub = ~result_zero_bits;
3782 : 303458 : wide_int new_lb = result_one_bits;
3783 : :
3784 : : // If the range has all positive or all negative values, the result
3785 : : // is better than VARYING.
3786 : 303458 : if (wi::lt_p (new_lb, 0, sign) || wi::ge_p (new_ub, 0, sign))
3787 : 267514 : value_range_with_overflow (r, type, new_lb, new_ub);
3788 : 35944 : else if (sign == SIGNED
3789 : 35944 : && wi_optimize_signed_bitwise_op (r, type,
3790 : : lh_lb, lh_ub,
3791 : : rh_lb, rh_ub))
3792 : : ; /* Do nothing. */
3793 : : else
3794 : 31184 : r.set_varying (type);
3795 : :
3796 : : /* Furthermore, XOR is non-zero if its arguments can't be equal. */
3797 : 303458 : if (wi::lt_p (lh_ub, rh_lb, sign)
3798 : 256012 : || wi::lt_p (rh_ub, lh_lb, sign)
3799 : 529735 : || wi::ne_p (result_one_bits, 0))
3800 : : {
3801 : 77181 : int_range<2> tmp;
3802 : 77181 : tmp.set_nonzero (type);
3803 : 77181 : r.intersect (tmp);
3804 : 77181 : }
3805 : 303476 : }
3806 : :
3807 : : bool
3808 : 197386 : operator_bitwise_xor::op1_op2_relation_effect (irange &lhs_range,
3809 : : tree type,
3810 : : const irange &,
3811 : : const irange &,
3812 : : relation_kind rel) const
3813 : : {
3814 : 197386 : if (rel == VREL_VARYING)
3815 : : return false;
3816 : :
3817 : 10780 : int_range<2> rel_range;
3818 : :
3819 : 10780 : switch (rel)
3820 : : {
3821 : 11 : case VREL_EQ:
3822 : 11 : rel_range.set_zero (type);
3823 : 11 : break;
3824 : 919 : case VREL_NE:
3825 : 919 : rel_range.set_nonzero (type);
3826 : 919 : break;
3827 : : default:
3828 : : return false;
3829 : : }
3830 : :
3831 : 930 : lhs_range.intersect (rel_range);
3832 : 930 : return true;
3833 : 10780 : }
3834 : :
3835 : : bool
3836 : 30197 : operator_bitwise_xor::op1_range (irange &r, tree type,
3837 : : const irange &lhs,
3838 : : const irange &op2,
3839 : : relation_trio) const
3840 : : {
3841 : 30197 : if (lhs.undefined_p () || lhs.varying_p ())
3842 : : {
3843 : 4281 : r = lhs;
3844 : 4281 : return true;
3845 : : }
3846 : 25916 : if (types_compatible_p (type, boolean_type_node))
3847 : : {
3848 : 439 : switch (get_bool_state (r, lhs, type))
3849 : : {
3850 : 187 : case BRS_TRUE:
3851 : 187 : if (op2.varying_p ())
3852 : 123 : r.set_varying (type);
3853 : 64 : else if (op2.zero_p ())
3854 : 48 : r = range_true (type);
3855 : : // See get_bool_state for the rationale
3856 : 16 : else if (op2.undefined_p () || contains_zero_p (op2))
3857 : 0 : r = range_true_and_false (type);
3858 : : else
3859 : 16 : r = range_false (type);
3860 : : break;
3861 : 252 : case BRS_FALSE:
3862 : 252 : r = op2;
3863 : 252 : break;
3864 : : default:
3865 : : break;
3866 : : }
3867 : 439 : return true;
3868 : : }
3869 : 25477 : r.set_varying (type);
3870 : 25477 : return true;
3871 : : }
3872 : :
3873 : : bool
3874 : 11836 : operator_bitwise_xor::op2_range (irange &r, tree type,
3875 : : const irange &lhs,
3876 : : const irange &op1,
3877 : : relation_trio) const
3878 : : {
3879 : 11836 : return operator_bitwise_xor::op1_range (r, type, lhs, op1);
3880 : : }
3881 : :
3882 : : class operator_trunc_mod : public range_operator
3883 : : {
3884 : : using range_operator::op1_range;
3885 : : using range_operator::op2_range;
3886 : : public:
3887 : : virtual void wi_fold (irange &r, tree type,
3888 : : const wide_int &lh_lb,
3889 : : const wide_int &lh_ub,
3890 : : const wide_int &rh_lb,
3891 : : const wide_int &rh_ub) const;
3892 : : virtual bool op1_range (irange &r, tree type,
3893 : : const irange &lhs,
3894 : : const irange &op2,
3895 : : relation_trio) const;
3896 : : virtual bool op2_range (irange &r, tree type,
3897 : : const irange &lhs,
3898 : : const irange &op1,
3899 : : relation_trio) const;
3900 : 786550 : void update_bitmask (irange &r, const irange &lh, const irange &rh) const
3901 : 786550 : { update_known_bitmask (r, TRUNC_MOD_EXPR, lh, rh); }
3902 : : } op_trunc_mod;
3903 : :
3904 : : void
3905 : 959770 : operator_trunc_mod::wi_fold (irange &r, tree type,
3906 : : const wide_int &lh_lb,
3907 : : const wide_int &lh_ub,
3908 : : const wide_int &rh_lb,
3909 : : const wide_int &rh_ub) const
3910 : : {
3911 : 959770 : wide_int new_lb, new_ub, tmp;
3912 : 959770 : signop sign = TYPE_SIGN (type);
3913 : 959770 : unsigned prec = TYPE_PRECISION (type);
3914 : :
3915 : : // Mod 0 is undefined.
3916 : 959770 : if (wi_zero_p (type, rh_lb, rh_ub))
3917 : : {
3918 : 4446 : r.set_undefined ();
3919 : 4446 : return;
3920 : : }
3921 : :
3922 : : // Check for constant and try to fold.
3923 : 1070333 : if (lh_lb == lh_ub && rh_lb == rh_ub)
3924 : : {
3925 : 12492 : wi::overflow_type ov = wi::OVF_NONE;
3926 : 12492 : tmp = wi::mod_trunc (lh_lb, rh_lb, sign, &ov);
3927 : 12492 : if (ov == wi::OVF_NONE)
3928 : : {
3929 : 12492 : r = int_range<2> (type, tmp, tmp);
3930 : 12492 : return;
3931 : : }
3932 : : }
3933 : :
3934 : : // ABS (A % B) < ABS (B) and either 0 <= A % B <= A or A <= A % B <= 0.
3935 : 942832 : new_ub = rh_ub - 1;
3936 : 942832 : if (sign == SIGNED)
3937 : : {
3938 : 363483 : tmp = -1 - rh_lb;
3939 : 363509 : new_ub = wi::smax (new_ub, tmp);
3940 : : }
3941 : :
3942 : 942832 : if (sign == UNSIGNED)
3943 : 579349 : new_lb = wi::zero (prec);
3944 : : else
3945 : : {
3946 : 363483 : new_lb = -new_ub;
3947 : 363483 : tmp = lh_lb;
3948 : 363483 : if (wi::gts_p (tmp, 0))
3949 : 72402 : tmp = wi::zero (prec);
3950 : 363509 : new_lb = wi::smax (new_lb, tmp);
3951 : : }
3952 : 942832 : tmp = lh_ub;
3953 : 942832 : if (sign == SIGNED && wi::neg_p (tmp))
3954 : 11639 : tmp = wi::zero (prec);
3955 : 942832 : new_ub = wi::min (new_ub, tmp, sign);
3956 : :
3957 : 942832 : value_range_with_overflow (r, type, new_lb, new_ub);
3958 : 959878 : }
3959 : :
3960 : : bool
3961 : 387668 : operator_trunc_mod::op1_range (irange &r, tree type,
3962 : : const irange &lhs,
3963 : : const irange &,
3964 : : relation_trio) const
3965 : : {
3966 : 387668 : if (lhs.undefined_p ())
3967 : : return false;
3968 : : // PR 91029.
3969 : 387668 : signop sign = TYPE_SIGN (type);
3970 : 387668 : unsigned prec = TYPE_PRECISION (type);
3971 : : // (a % b) >= x && x > 0 , then a >= x.
3972 : 387742 : if (wi::gt_p (lhs.lower_bound (), 0, sign))
3973 : : {
3974 : 93124 : r = value_range (type, lhs.lower_bound (), wi::max_value (prec, sign));
3975 : 93101 : return true;
3976 : : }
3977 : : // (a % b) <= x && x < 0 , then a <= x.
3978 : 294618 : if (wi::lt_p (lhs.upper_bound (), 0, sign))
3979 : : {
3980 : 5071 : r = value_range (type, wi::min_value (prec, sign), lhs.upper_bound ());
3981 : 5071 : return true;
3982 : : }
3983 : : return false;
3984 : : }
3985 : :
3986 : : bool
3987 : 240657 : operator_trunc_mod::op2_range (irange &r, tree type,
3988 : : const irange &lhs,
3989 : : const irange &,
3990 : : relation_trio) const
3991 : : {
3992 : 240657 : if (lhs.undefined_p ())
3993 : : return false;
3994 : : // PR 91029.
3995 : 240657 : signop sign = TYPE_SIGN (type);
3996 : 240657 : unsigned prec = TYPE_PRECISION (type);
3997 : : // (a % b) >= x && x > 0 , then b is in ~[-x, x] for signed
3998 : : // or b > x for unsigned.
3999 : 240686 : if (wi::gt_p (lhs.lower_bound (), 0, sign))
4000 : : {
4001 : 38251 : if (sign == SIGNED)
4002 : 3558 : r = value_range (type, wi::neg (lhs.lower_bound ()),
4003 : 5337 : lhs.lower_bound (), VR_ANTI_RANGE);
4004 : 36482 : else if (wi::lt_p (lhs.lower_bound (), wi::max_value (prec, sign),
4005 : : sign))
4006 : 72954 : r = value_range (type, lhs.lower_bound () + 1,
4007 : 109416 : wi::max_value (prec, sign));
4008 : : else
4009 : : return false;
4010 : 38251 : return true;
4011 : : }
4012 : : // (a % b) <= x && x < 0 , then b is in ~[x, -x].
4013 : 202430 : if (wi::lt_p (lhs.upper_bound (), 0, sign))
4014 : : {
4015 : 3443 : if (wi::gt_p (lhs.upper_bound (), wi::min_value (prec, sign), sign))
4016 : 6886 : r = value_range (type, lhs.upper_bound (),
4017 : 10329 : wi::neg (lhs.upper_bound ()), VR_ANTI_RANGE);
4018 : : else
4019 : : return false;
4020 : 3443 : return true;
4021 : : }
4022 : : return false;
4023 : : }
4024 : :
4025 : :
4026 : : class operator_logical_not : public range_operator
4027 : : {
4028 : : using range_operator::fold_range;
4029 : : using range_operator::op1_range;
4030 : : public:
4031 : : virtual bool fold_range (irange &r, tree type,
4032 : : const irange &lh,
4033 : : const irange &rh,
4034 : : relation_trio rel = TRIO_VARYING) const;
4035 : : virtual bool op1_range (irange &r, tree type,
4036 : : const irange &lhs,
4037 : : const irange &op2,
4038 : : relation_trio rel = TRIO_VARYING) const;
4039 : : // Check compatibility of LHS and op1.
4040 : 0 : bool operand_check_p (tree t1, tree t2, tree) const final override
4041 : 0 : { return range_compatible_p (t1, t2); }
4042 : : } op_logical_not;
4043 : :
4044 : : // Folding a logical NOT, oddly enough, involves doing nothing on the
4045 : : // forward pass through. During the initial walk backwards, the
4046 : : // logical NOT reversed the desired outcome on the way back, so on the
4047 : : // way forward all we do is pass the range forward.
4048 : : //
4049 : : // b_2 = x_1 < 20
4050 : : // b_3 = !b_2
4051 : : // if (b_3)
4052 : : // to determine the TRUE branch, walking backward
4053 : : // if (b_3) if ([1,1])
4054 : : // b_3 = !b_2 [1,1] = ![0,0]
4055 : : // b_2 = x_1 < 20 [0,0] = x_1 < 20, false, so x_1 == [20, 255]
4056 : : // which is the result we are looking for.. so.. pass it through.
4057 : :
4058 : : bool
4059 : 298612 : operator_logical_not::fold_range (irange &r, tree type,
4060 : : const irange &lh,
4061 : : const irange &rh ATTRIBUTE_UNUSED,
4062 : : relation_trio) const
4063 : : {
4064 : 298612 : if (empty_range_varying (r, type, lh, rh))
4065 : 0 : return true;
4066 : :
4067 : 298612 : r = lh;
4068 : 298612 : if (!lh.varying_p () && !lh.undefined_p ())
4069 : 53864 : r.invert ();
4070 : :
4071 : : return true;
4072 : : }
4073 : :
4074 : : bool
4075 : 26350 : operator_logical_not::op1_range (irange &r,
4076 : : tree type,
4077 : : const irange &lhs,
4078 : : const irange &op2,
4079 : : relation_trio) const
4080 : : {
4081 : : // Logical NOT is involutary...do it again.
4082 : 26350 : return fold_range (r, type, lhs, op2);
4083 : : }
4084 : :
4085 : : bool
4086 : 485182 : operator_bitwise_not::fold_range (irange &r, tree type,
4087 : : const irange &lh,
4088 : : const irange &rh,
4089 : : relation_trio) const
4090 : : {
4091 : 485182 : if (empty_range_varying (r, type, lh, rh))
4092 : 64 : return true;
4093 : :
4094 : 485118 : if (types_compatible_p (type, boolean_type_node))
4095 : 272262 : return op_logical_not.fold_range (r, type, lh, rh);
4096 : :
4097 : : // ~X is simply -1 - X.
4098 : 212856 : int_range<1> minusone (type, wi::minus_one (TYPE_PRECISION (type)),
4099 : 425712 : wi::minus_one (TYPE_PRECISION (type)));
4100 : 212856 : return range_op_handler (MINUS_EXPR).fold_range (r, type, minusone, lh);
4101 : 212856 : }
4102 : :
4103 : : bool
4104 : 43207 : operator_bitwise_not::op1_range (irange &r, tree type,
4105 : : const irange &lhs,
4106 : : const irange &op2,
4107 : : relation_trio) const
4108 : : {
4109 : 43207 : if (lhs.undefined_p ())
4110 : : return false;
4111 : 43207 : if (types_compatible_p (type, boolean_type_node))
4112 : 26350 : return op_logical_not.op1_range (r, type, lhs, op2);
4113 : :
4114 : : // ~X is -1 - X and since bitwise NOT is involutary...do it again.
4115 : 16857 : return fold_range (r, type, lhs, op2);
4116 : : }
4117 : :
4118 : : void
4119 : 0 : operator_bitwise_not::update_bitmask (irange &r, const irange &lh,
4120 : : const irange &rh) const
4121 : : {
4122 : 0 : update_known_bitmask (r, BIT_NOT_EXPR, lh, rh);
4123 : 0 : }
4124 : :
4125 : :
4126 : : bool
4127 : 207654 : operator_cst::fold_range (irange &r, tree type ATTRIBUTE_UNUSED,
4128 : : const irange &lh,
4129 : : const irange &rh ATTRIBUTE_UNUSED,
4130 : : relation_trio) const
4131 : : {
4132 : 207654 : r = lh;
4133 : 207654 : return true;
4134 : : }
4135 : :
4136 : :
4137 : : // Determine if there is a relationship between LHS and OP1.
4138 : :
4139 : : relation_kind
4140 : 1330705 : operator_identity::lhs_op1_relation (const irange &lhs,
4141 : : const irange &op1 ATTRIBUTE_UNUSED,
4142 : : const irange &op2 ATTRIBUTE_UNUSED,
4143 : : relation_kind) const
4144 : : {
4145 : 1330705 : if (lhs.undefined_p ())
4146 : 649 : return VREL_VARYING;
4147 : : // Simply a copy, so they are equivalent.
4148 : : return VREL_EQ;
4149 : : }
4150 : :
4151 : : bool
4152 : 1400032 : operator_identity::fold_range (irange &r, tree type ATTRIBUTE_UNUSED,
4153 : : const irange &lh,
4154 : : const irange &rh ATTRIBUTE_UNUSED,
4155 : : relation_trio) const
4156 : : {
4157 : 1400032 : r = lh;
4158 : 1400032 : return true;
4159 : : }
4160 : :
4161 : : bool
4162 : 321834 : operator_identity::op1_range (irange &r, tree type ATTRIBUTE_UNUSED,
4163 : : const irange &lhs,
4164 : : const irange &op2 ATTRIBUTE_UNUSED,
4165 : : relation_trio) const
4166 : : {
4167 : 321834 : r = lhs;
4168 : 321834 : return true;
4169 : : }
4170 : :
4171 : :
4172 : : class operator_unknown : public range_operator
4173 : : {
4174 : : using range_operator::fold_range;
4175 : : public:
4176 : : virtual bool fold_range (irange &r, tree type,
4177 : : const irange &op1,
4178 : : const irange &op2,
4179 : : relation_trio rel = TRIO_VARYING) const;
4180 : : } op_unknown;
4181 : :
4182 : : bool
4183 : 713222 : operator_unknown::fold_range (irange &r, tree type,
4184 : : const irange &lh ATTRIBUTE_UNUSED,
4185 : : const irange &rh ATTRIBUTE_UNUSED,
4186 : : relation_trio) const
4187 : : {
4188 : 713222 : r.set_varying (type);
4189 : 713222 : return true;
4190 : : }
4191 : :
4192 : :
4193 : : void
4194 : 49574 : operator_abs::wi_fold (irange &r, tree type,
4195 : : const wide_int &lh_lb, const wide_int &lh_ub,
4196 : : const wide_int &rh_lb ATTRIBUTE_UNUSED,
4197 : : const wide_int &rh_ub ATTRIBUTE_UNUSED) const
4198 : : {
4199 : 49574 : wide_int min, max;
4200 : 49574 : signop sign = TYPE_SIGN (type);
4201 : 49574 : unsigned prec = TYPE_PRECISION (type);
4202 : :
4203 : : // Pass through LH for the easy cases.
4204 : 49574 : if (sign == UNSIGNED || wi::ge_p (lh_lb, 0, sign))
4205 : : {
4206 : 7800 : r = int_range<1> (type, lh_lb, lh_ub);
4207 : 7800 : return;
4208 : : }
4209 : :
4210 : : // -TYPE_MIN_VALUE = TYPE_MIN_VALUE with flag_wrapv so we can't get
4211 : : // a useful range.
4212 : 41774 : wide_int min_value = wi::min_value (prec, sign);
4213 : 41774 : wide_int max_value = wi::max_value (prec, sign);
4214 : 41774 : if (!TYPE_OVERFLOW_UNDEFINED (type) && wi::eq_p (lh_lb, min_value))
4215 : : {
4216 : 640 : r.set_varying (type);
4217 : 640 : return;
4218 : : }
4219 : :
4220 : : // ABS_EXPR may flip the range around, if the original range
4221 : : // included negative values.
4222 : 41134 : if (wi::eq_p (lh_lb, min_value))
4223 : : {
4224 : : // ABS ([-MIN, -MIN]) isn't representable, but we have traditionally
4225 : : // returned [-MIN,-MIN] so this preserves that behavior. PR37078
4226 : 29239 : if (wi::eq_p (lh_ub, min_value))
4227 : : {
4228 : 5 : r = int_range<1> (type, min_value, min_value);
4229 : 5 : return;
4230 : : }
4231 : 29234 : min = max_value;
4232 : : }
4233 : : else
4234 : 11895 : min = wi::abs (lh_lb);
4235 : :
4236 : 41129 : if (wi::eq_p (lh_ub, min_value))
4237 : 0 : max = max_value;
4238 : : else
4239 : 41129 : max = wi::abs (lh_ub);
4240 : :
4241 : : // If the range contains zero then we know that the minimum value in the
4242 : : // range will be zero.
4243 : 41129 : if (wi::le_p (lh_lb, 0, sign) && wi::ge_p (lh_ub, 0, sign))
4244 : : {
4245 : 33613 : if (wi::gt_p (min, max, sign))
4246 : 5792 : max = min;
4247 : 33613 : min = wi::zero (prec);
4248 : : }
4249 : : else
4250 : : {
4251 : : // If the range was reversed, swap MIN and MAX.
4252 : 7516 : if (wi::gt_p (min, max, sign))
4253 : 7463 : std::swap (min, max);
4254 : : }
4255 : :
4256 : : // If the new range has its limits swapped around (MIN > MAX), then
4257 : : // the operation caused one of them to wrap around. The only thing
4258 : : // we know is that the result is positive.
4259 : 41129 : if (wi::gt_p (min, max, sign))
4260 : : {
4261 : 0 : min = wi::zero (prec);
4262 : 0 : max = max_value;
4263 : : }
4264 : 41129 : r = int_range<1> (type, min, max);
4265 : 50219 : }
4266 : :
4267 : : bool
4268 : 20107 : operator_abs::op1_range (irange &r, tree type,
4269 : : const irange &lhs,
4270 : : const irange &op2,
4271 : : relation_trio) const
4272 : : {
4273 : 20107 : if (empty_range_varying (r, type, lhs, op2))
4274 : 0 : return true;
4275 : 20107 : if (TYPE_UNSIGNED (type))
4276 : : {
4277 : 0 : r = lhs;
4278 : 0 : return true;
4279 : : }
4280 : : // Start with the positives because negatives are an impossible result.
4281 : 20107 : int_range_max positives = range_positives (type);
4282 : 20107 : positives.intersect (lhs);
4283 : 20107 : r = positives;
4284 : : // Then add the negative of each pair:
4285 : : // ABS(op1) = [5,20] would yield op1 => [-20,-5][5,20].
4286 : 41053 : for (unsigned i = 0; i < positives.num_pairs (); ++i)
4287 : 20946 : r.union_ (int_range<1> (type,
4288 : 41892 : -positives.upper_bound (i),
4289 : 41892 : -positives.lower_bound (i)));
4290 : : // With flag_wrapv, -TYPE_MIN_VALUE = TYPE_MIN_VALUE which is
4291 : : // unrepresentable. Add -TYPE_MIN_VALUE in this case.
4292 : 20107 : wide_int min_value = wi::min_value (TYPE_PRECISION (type), TYPE_SIGN (type));
4293 : 20107 : wide_int lb = lhs.lower_bound ();
4294 : 20107 : if (!TYPE_OVERFLOW_UNDEFINED (type) && wi::eq_p (lb, min_value))
4295 : 211 : r.union_ (int_range<2> (type, lb, lb));
4296 : 20107 : return true;
4297 : 20107 : }
4298 : :
4299 : : void
4300 : 45376 : operator_abs::update_bitmask (irange &r, const irange &lh,
4301 : : const irange &rh) const
4302 : : {
4303 : 45376 : update_known_bitmask (r, ABS_EXPR, lh, rh);
4304 : 45376 : }
4305 : :
4306 : : class operator_absu : public range_operator
4307 : : {
4308 : : public:
4309 : : virtual void wi_fold (irange &r, tree type,
4310 : : const wide_int &lh_lb, const wide_int &lh_ub,
4311 : : const wide_int &rh_lb, const wide_int &rh_ub) const;
4312 : : virtual void update_bitmask (irange &r, const irange &lh,
4313 : : const irange &rh) const final override;
4314 : : } op_absu;
4315 : :
4316 : : void
4317 : 14693 : operator_absu::wi_fold (irange &r, tree type,
4318 : : const wide_int &lh_lb, const wide_int &lh_ub,
4319 : : const wide_int &rh_lb ATTRIBUTE_UNUSED,
4320 : : const wide_int &rh_ub ATTRIBUTE_UNUSED) const
4321 : : {
4322 : 14693 : wide_int new_lb, new_ub;
4323 : :
4324 : : // Pass through VR0 the easy cases.
4325 : 14693 : if (wi::ges_p (lh_lb, 0))
4326 : : {
4327 : 3987 : new_lb = lh_lb;
4328 : 3987 : new_ub = lh_ub;
4329 : : }
4330 : : else
4331 : : {
4332 : 10706 : new_lb = wi::abs (lh_lb);
4333 : 10706 : new_ub = wi::abs (lh_ub);
4334 : :
4335 : : // If the range contains zero then we know that the minimum
4336 : : // value in the range will be zero.
4337 : 10706 : if (wi::ges_p (lh_ub, 0))
4338 : : {
4339 : 5716 : if (wi::gtu_p (new_lb, new_ub))
4340 : 4734 : new_ub = new_lb;
4341 : 5716 : new_lb = wi::zero (TYPE_PRECISION (type));
4342 : : }
4343 : : else
4344 : 4990 : std::swap (new_lb, new_ub);
4345 : : }
4346 : :
4347 : 14693 : gcc_checking_assert (TYPE_UNSIGNED (type));
4348 : 14693 : r = int_range<1> (type, new_lb, new_ub);
4349 : 14693 : }
4350 : :
4351 : : void
4352 : 13672 : operator_absu::update_bitmask (irange &r, const irange &lh,
4353 : : const irange &rh) const
4354 : : {
4355 : 13672 : update_known_bitmask (r, ABSU_EXPR, lh, rh);
4356 : 13672 : }
4357 : :
4358 : :
4359 : : bool
4360 : 445851 : operator_negate::fold_range (irange &r, tree type,
4361 : : const irange &lh,
4362 : : const irange &rh,
4363 : : relation_trio) const
4364 : : {
4365 : 445851 : if (empty_range_varying (r, type, lh, rh))
4366 : 845 : return true;
4367 : : // -X is simply 0 - X.
4368 : 445006 : return range_op_handler (MINUS_EXPR).fold_range (r, type,
4369 : 890012 : range_zero (type), lh);
4370 : : }
4371 : :
4372 : : bool
4373 : 49302 : operator_negate::op1_range (irange &r, tree type,
4374 : : const irange &lhs,
4375 : : const irange &op2,
4376 : : relation_trio) const
4377 : : {
4378 : : // NEGATE is involutory.
4379 : 49302 : return fold_range (r, type, lhs, op2);
4380 : : }
4381 : :
4382 : :
4383 : : bool
4384 : 0 : operator_addr_expr::fold_range (irange &r, tree type,
4385 : : const irange &lh,
4386 : : const irange &rh,
4387 : : relation_trio) const
4388 : : {
4389 : 0 : if (empty_range_varying (r, type, lh, rh))
4390 : 0 : return true;
4391 : :
4392 : : // Return a non-null pointer of the LHS type (passed in op2).
4393 : 0 : if (lh.zero_p ())
4394 : 0 : r = range_zero (type);
4395 : 0 : else if (lh.undefined_p () || contains_zero_p (lh))
4396 : 0 : r.set_varying (type);
4397 : : else
4398 : 0 : r.set_nonzero (type);
4399 : : return true;
4400 : : }
4401 : :
4402 : : bool
4403 : 473800 : operator_addr_expr::op1_range (irange &r, tree type,
4404 : : const irange &lhs,
4405 : : const irange &op2,
4406 : : relation_trio) const
4407 : : {
4408 : 473800 : if (empty_range_varying (r, type, lhs, op2))
4409 : 0 : return true;
4410 : :
4411 : : // Return a non-null pointer of the LHS type (passed in op2), but only
4412 : : // if we cant overflow, eitherwise a no-zero offset could wrap to zero.
4413 : : // See PR 111009.
4414 : 473800 : if (!lhs.undefined_p () && !contains_zero_p (lhs) && TYPE_OVERFLOW_UNDEFINED (type))
4415 : 468173 : r.set_nonzero (type);
4416 : : else
4417 : 5627 : r.set_varying (type);
4418 : : return true;
4419 : : }
4420 : :
4421 : : // Initialize any integral operators to the primary table
4422 : :
4423 : : void
4424 : 280913 : range_op_table::initialize_integral_ops ()
4425 : : {
4426 : 280913 : set (TRUNC_DIV_EXPR, op_trunc_div);
4427 : 280913 : set (FLOOR_DIV_EXPR, op_floor_div);
4428 : 280913 : set (ROUND_DIV_EXPR, op_round_div);
4429 : 280913 : set (CEIL_DIV_EXPR, op_ceil_div);
4430 : 280913 : set (EXACT_DIV_EXPR, op_exact_div);
4431 : 280913 : set (LSHIFT_EXPR, op_lshift);
4432 : 280913 : set (RSHIFT_EXPR, op_rshift);
4433 : 280913 : set (TRUTH_AND_EXPR, op_logical_and);
4434 : 280913 : set (TRUTH_OR_EXPR, op_logical_or);
4435 : 280913 : set (TRUNC_MOD_EXPR, op_trunc_mod);
4436 : 280913 : set (TRUTH_NOT_EXPR, op_logical_not);
4437 : 280913 : set (IMAGPART_EXPR, op_unknown);
4438 : 280913 : set (REALPART_EXPR, op_unknown);
4439 : 280913 : set (ABSU_EXPR, op_absu);
4440 : 280913 : set (OP_WIDEN_MULT_SIGNED, op_widen_mult_signed);
4441 : 280913 : set (OP_WIDEN_MULT_UNSIGNED, op_widen_mult_unsigned);
4442 : 280913 : set (OP_WIDEN_PLUS_SIGNED, op_widen_plus_signed);
4443 : 280913 : set (OP_WIDEN_PLUS_UNSIGNED, op_widen_plus_unsigned);
4444 : :
4445 : 280913 : }
4446 : :
4447 : : bool
4448 : 32160 : operator_plus::overflow_free_p (const irange &lh, const irange &rh,
4449 : : relation_trio) const
4450 : : {
4451 : 32160 : if (lh.undefined_p () || rh.undefined_p ())
4452 : : return false;
4453 : :
4454 : 32156 : tree type = lh.type ();
4455 : 32156 : if (TYPE_OVERFLOW_UNDEFINED (type))
4456 : : return true;
4457 : :
4458 : 12612 : wi::overflow_type ovf;
4459 : 12612 : signop sgn = TYPE_SIGN (type);
4460 : 12612 : wide_int wmax0 = lh.upper_bound ();
4461 : 12612 : wide_int wmax1 = rh.upper_bound ();
4462 : 12612 : wi::add (wmax0, wmax1, sgn, &ovf);
4463 : 12612 : if (ovf != wi::OVF_NONE)
4464 : : return false;
4465 : :
4466 : 1277 : if (TYPE_UNSIGNED (type))
4467 : : return true;
4468 : :
4469 : 400 : wide_int wmin0 = lh.lower_bound ();
4470 : 400 : wide_int wmin1 = rh.lower_bound ();
4471 : 400 : wi::add (wmin0, wmin1, sgn, &ovf);
4472 : 400 : if (ovf != wi::OVF_NONE)
4473 : 323 : return false;
4474 : :
4475 : : return true;
4476 : 13012 : }
4477 : :
4478 : : bool
4479 : 30 : operator_minus::overflow_free_p (const irange &lh, const irange &rh,
4480 : : relation_trio) const
4481 : : {
4482 : 30 : if (lh.undefined_p () || rh.undefined_p ())
4483 : : return false;
4484 : :
4485 : 30 : tree type = lh.type ();
4486 : 30 : if (TYPE_OVERFLOW_UNDEFINED (type))
4487 : : return true;
4488 : :
4489 : 10 : wi::overflow_type ovf;
4490 : 10 : signop sgn = TYPE_SIGN (type);
4491 : 10 : wide_int wmin0 = lh.lower_bound ();
4492 : 10 : wide_int wmax1 = rh.upper_bound ();
4493 : 10 : wi::sub (wmin0, wmax1, sgn, &ovf);
4494 : 10 : if (ovf != wi::OVF_NONE)
4495 : : return false;
4496 : :
4497 : 7 : if (TYPE_UNSIGNED (type))
4498 : : return true;
4499 : :
4500 : 6 : wide_int wmax0 = lh.upper_bound ();
4501 : 6 : wide_int wmin1 = rh.lower_bound ();
4502 : 6 : wi::sub (wmax0, wmin1, sgn, &ovf);
4503 : 6 : if (ovf != wi::OVF_NONE)
4504 : 0 : return false;
4505 : :
4506 : : return true;
4507 : 16 : }
4508 : :
4509 : : bool
4510 : 75309 : operator_mult::overflow_free_p (const irange &lh, const irange &rh,
4511 : : relation_trio) const
4512 : : {
4513 : 75309 : if (lh.undefined_p () || rh.undefined_p ())
4514 : : return false;
4515 : :
4516 : 75309 : tree type = lh.type ();
4517 : 75309 : if (TYPE_OVERFLOW_UNDEFINED (type))
4518 : : return true;
4519 : :
4520 : 74791 : wi::overflow_type ovf;
4521 : 74791 : signop sgn = TYPE_SIGN (type);
4522 : 74791 : wide_int wmax0 = lh.upper_bound ();
4523 : 74791 : wide_int wmax1 = rh.upper_bound ();
4524 : 74791 : wi::mul (wmax0, wmax1, sgn, &ovf);
4525 : 74791 : if (ovf != wi::OVF_NONE)
4526 : : return false;
4527 : :
4528 : 138 : if (TYPE_UNSIGNED (type))
4529 : : return true;
4530 : :
4531 : 20 : wide_int wmin0 = lh.lower_bound ();
4532 : 20 : wide_int wmin1 = rh.lower_bound ();
4533 : 20 : wi::mul (wmin0, wmin1, sgn, &ovf);
4534 : 20 : if (ovf != wi::OVF_NONE)
4535 : : return false;
4536 : :
4537 : 20 : wi::mul (wmin0, wmax1, sgn, &ovf);
4538 : 20 : if (ovf != wi::OVF_NONE)
4539 : : return false;
4540 : :
4541 : 20 : wi::mul (wmax0, wmin1, sgn, &ovf);
4542 : 20 : if (ovf != wi::OVF_NONE)
4543 : : return false;
4544 : :
4545 : : return true;
4546 : 74811 : }
4547 : :
4548 : : #if CHECKING_P
4549 : : #include "selftest.h"
4550 : :
4551 : : namespace selftest
4552 : : {
4553 : : #define INT(x) wi::shwi ((x), TYPE_PRECISION (integer_type_node))
4554 : : #define UINT(x) wi::uhwi ((x), TYPE_PRECISION (unsigned_type_node))
4555 : : #define INT16(x) wi::shwi ((x), TYPE_PRECISION (short_integer_type_node))
4556 : : #define UINT16(x) wi::uhwi ((x), TYPE_PRECISION (short_unsigned_type_node))
4557 : : #define SCHAR(x) wi::shwi ((x), TYPE_PRECISION (signed_char_type_node))
4558 : : #define UCHAR(x) wi::uhwi ((x), TYPE_PRECISION (unsigned_char_type_node))
4559 : :
4560 : : static void
4561 : 4 : range_op_cast_tests ()
4562 : : {
4563 : 4 : int_range<2> r0, r1, r2, rold;
4564 : 4 : r0.set_varying (integer_type_node);
4565 : 4 : wide_int maxint = r0.upper_bound ();
4566 : :
4567 : : // If a range is in any way outside of the range for the converted
4568 : : // to range, default to the range for the new type.
4569 : 4 : r0.set_varying (short_integer_type_node);
4570 : 4 : wide_int minshort = r0.lower_bound ();
4571 : 4 : wide_int maxshort = r0.upper_bound ();
4572 : 4 : if (TYPE_PRECISION (integer_type_node)
4573 : 4 : > TYPE_PRECISION (short_integer_type_node))
4574 : : {
4575 : 8 : r1 = int_range<1> (integer_type_node,
4576 : 4 : wi::zero (TYPE_PRECISION (integer_type_node)),
4577 : 4 : maxint);
4578 : 4 : range_cast (r1, short_integer_type_node);
4579 : 4 : ASSERT_TRUE (r1.lower_bound () == minshort
4580 : : && r1.upper_bound() == maxshort);
4581 : : }
4582 : :
4583 : : // (unsigned char)[-5,-1] => [251,255].
4584 : 4 : r0 = rold = int_range<1> (signed_char_type_node, SCHAR (-5), SCHAR (-1));
4585 : 4 : range_cast (r0, unsigned_char_type_node);
4586 : 4 : ASSERT_TRUE (r0 == int_range<1> (unsigned_char_type_node,
4587 : : UCHAR (251), UCHAR (255)));
4588 : 4 : range_cast (r0, signed_char_type_node);
4589 : 4 : ASSERT_TRUE (r0 == rold);
4590 : :
4591 : : // (signed char)[15, 150] => [-128,-106][15,127].
4592 : 4 : r0 = rold = int_range<1> (unsigned_char_type_node, UCHAR (15), UCHAR (150));
4593 : 4 : range_cast (r0, signed_char_type_node);
4594 : 4 : r1 = int_range<1> (signed_char_type_node, SCHAR (15), SCHAR (127));
4595 : 4 : r2 = int_range<1> (signed_char_type_node, SCHAR (-128), SCHAR (-106));
4596 : 4 : r1.union_ (r2);
4597 : 4 : ASSERT_TRUE (r1 == r0);
4598 : 4 : range_cast (r0, unsigned_char_type_node);
4599 : 4 : ASSERT_TRUE (r0 == rold);
4600 : :
4601 : : // (unsigned char)[-5, 5] => [0,5][251,255].
4602 : 4 : r0 = rold = int_range<1> (signed_char_type_node, SCHAR (-5), SCHAR (5));
4603 : 4 : range_cast (r0, unsigned_char_type_node);
4604 : 4 : r1 = int_range<1> (unsigned_char_type_node, UCHAR (251), UCHAR (255));
4605 : 4 : r2 = int_range<1> (unsigned_char_type_node, UCHAR (0), UCHAR (5));
4606 : 4 : r1.union_ (r2);
4607 : 4 : ASSERT_TRUE (r0 == r1);
4608 : 4 : range_cast (r0, signed_char_type_node);
4609 : 4 : ASSERT_TRUE (r0 == rold);
4610 : :
4611 : : // (unsigned char)[-5,5] => [0,5][251,255].
4612 : 4 : r0 = int_range<1> (integer_type_node, INT (-5), INT (5));
4613 : 4 : range_cast (r0, unsigned_char_type_node);
4614 : 4 : r1 = int_range<1> (unsigned_char_type_node, UCHAR (0), UCHAR (5));
4615 : 4 : r1.union_ (int_range<1> (unsigned_char_type_node, UCHAR (251), UCHAR (255)));
4616 : 4 : ASSERT_TRUE (r0 == r1);
4617 : :
4618 : : // (unsigned char)[5U,1974U] => [0,255].
4619 : 4 : r0 = int_range<1> (unsigned_type_node, UINT (5), UINT (1974));
4620 : 4 : range_cast (r0, unsigned_char_type_node);
4621 : 4 : ASSERT_TRUE (r0 == int_range<1> (unsigned_char_type_node, UCHAR (0), UCHAR (255)));
4622 : 4 : range_cast (r0, integer_type_node);
4623 : : // Going to a wider range should not sign extend.
4624 : 4 : ASSERT_TRUE (r0 == int_range<1> (integer_type_node, INT (0), INT (255)));
4625 : :
4626 : : // (unsigned char)[-350,15] => [0,255].
4627 : 4 : r0 = int_range<1> (integer_type_node, INT (-350), INT (15));
4628 : 4 : range_cast (r0, unsigned_char_type_node);
4629 : 4 : ASSERT_TRUE (r0 == (int_range<1>
4630 : : (unsigned_char_type_node,
4631 : : min_limit (unsigned_char_type_node),
4632 : : max_limit (unsigned_char_type_node))));
4633 : :
4634 : : // Casting [-120,20] from signed char to unsigned short.
4635 : : // => [0, 20][0xff88, 0xffff].
4636 : 4 : r0 = int_range<1> (signed_char_type_node, SCHAR (-120), SCHAR (20));
4637 : 4 : range_cast (r0, short_unsigned_type_node);
4638 : 4 : r1 = int_range<1> (short_unsigned_type_node, UINT16 (0), UINT16 (20));
4639 : 8 : r2 = int_range<1> (short_unsigned_type_node,
4640 : 12 : UINT16 (0xff88), UINT16 (0xffff));
4641 : 4 : r1.union_ (r2);
4642 : 4 : ASSERT_TRUE (r0 == r1);
4643 : : // A truncating cast back to signed char will work because [-120, 20]
4644 : : // is representable in signed char.
4645 : 4 : range_cast (r0, signed_char_type_node);
4646 : 4 : ASSERT_TRUE (r0 == int_range<1> (signed_char_type_node,
4647 : : SCHAR (-120), SCHAR (20)));
4648 : :
4649 : : // unsigned char -> signed short
4650 : : // (signed short)[(unsigned char)25, (unsigned char)250]
4651 : : // => [(signed short)25, (signed short)250]
4652 : 4 : r0 = rold = int_range<1> (unsigned_char_type_node, UCHAR (25), UCHAR (250));
4653 : 4 : range_cast (r0, short_integer_type_node);
4654 : 4 : r1 = int_range<1> (short_integer_type_node, INT16 (25), INT16 (250));
4655 : 4 : ASSERT_TRUE (r0 == r1);
4656 : 4 : range_cast (r0, unsigned_char_type_node);
4657 : 4 : ASSERT_TRUE (r0 == rold);
4658 : :
4659 : : // Test casting a wider signed [-MIN,MAX] to a narrower unsigned.
4660 : 4 : r0 = int_range<1> (long_long_integer_type_node,
4661 : 8 : min_limit (long_long_integer_type_node),
4662 : 8 : max_limit (long_long_integer_type_node));
4663 : 4 : range_cast (r0, short_unsigned_type_node);
4664 : 4 : r1 = int_range<1> (short_unsigned_type_node,
4665 : 8 : min_limit (short_unsigned_type_node),
4666 : 8 : max_limit (short_unsigned_type_node));
4667 : 4 : ASSERT_TRUE (r0 == r1);
4668 : :
4669 : : // Casting NONZERO to a narrower type will wrap/overflow so
4670 : : // it's just the entire range for the narrower type.
4671 : : //
4672 : : // "NOT 0 at signed 32-bits" ==> [-MIN_32,-1][1, +MAX_32]. This is
4673 : : // is outside of the range of a smaller range, return the full
4674 : : // smaller range.
4675 : 4 : if (TYPE_PRECISION (integer_type_node)
4676 : 4 : > TYPE_PRECISION (short_integer_type_node))
4677 : : {
4678 : 4 : r0 = range_nonzero (integer_type_node);
4679 : 4 : range_cast (r0, short_integer_type_node);
4680 : 4 : r1 = int_range<1> (short_integer_type_node,
4681 : 8 : min_limit (short_integer_type_node),
4682 : 8 : max_limit (short_integer_type_node));
4683 : 4 : ASSERT_TRUE (r0 == r1);
4684 : : }
4685 : :
4686 : : // Casting NONZERO from a narrower signed to a wider signed.
4687 : : //
4688 : : // NONZERO signed 16-bits is [-MIN_16,-1][1, +MAX_16].
4689 : : // Converting this to 32-bits signed is [-MIN_16,-1][1, +MAX_16].
4690 : 4 : r0 = range_nonzero (short_integer_type_node);
4691 : 4 : range_cast (r0, integer_type_node);
4692 : 4 : r1 = int_range<1> (integer_type_node, INT (-32768), INT (-1));
4693 : 4 : r2 = int_range<1> (integer_type_node, INT (1), INT (32767));
4694 : 4 : r1.union_ (r2);
4695 : 4 : ASSERT_TRUE (r0 == r1);
4696 : 4 : }
4697 : :
4698 : : static void
4699 : 4 : range_op_lshift_tests ()
4700 : : {
4701 : : // Test that 0x808.... & 0x8.... still contains 0x8....
4702 : : // for a large set of numbers.
4703 : 4 : {
4704 : 4 : int_range_max res;
4705 : 4 : tree big_type = long_long_unsigned_type_node;
4706 : 4 : unsigned big_prec = TYPE_PRECISION (big_type);
4707 : : // big_num = 0x808,0000,0000,0000
4708 : 4 : wide_int big_num = wi::lshift (wi::uhwi (0x808, big_prec),
4709 : 8 : wi::uhwi (48, big_prec));
4710 : 8 : op_bitwise_and.fold_range (res, big_type,
4711 : 8 : int_range <1> (big_type),
4712 : 8 : int_range <1> (big_type, big_num, big_num));
4713 : : // val = 0x8,0000,0000,0000
4714 : 4 : wide_int val = wi::lshift (wi::uhwi (8, big_prec),
4715 : 8 : wi::uhwi (48, big_prec));
4716 : 4 : ASSERT_TRUE (res.contains_p (val));
4717 : 4 : }
4718 : :
4719 : 4 : if (TYPE_PRECISION (unsigned_type_node) > 31)
4720 : : {
4721 : : // unsigned VARYING = op1 << 1 should be VARYING.
4722 : 4 : int_range<2> lhs (unsigned_type_node);
4723 : 4 : int_range<2> shift (unsigned_type_node, INT (1), INT (1));
4724 : 4 : int_range_max op1;
4725 : 4 : op_lshift.op1_range (op1, unsigned_type_node, lhs, shift);
4726 : 4 : ASSERT_TRUE (op1.varying_p ());
4727 : :
4728 : : // 0 = op1 << 1 should be [0,0], [0x8000000, 0x8000000].
4729 : 4 : int_range<2> zero (unsigned_type_node, UINT (0), UINT (0));
4730 : 4 : op_lshift.op1_range (op1, unsigned_type_node, zero, shift);
4731 : 4 : ASSERT_TRUE (op1.num_pairs () == 2);
4732 : : // Remove the [0,0] range.
4733 : 4 : op1.intersect (zero);
4734 : 4 : ASSERT_TRUE (op1.num_pairs () == 1);
4735 : : // op1 << 1 should be [0x8000,0x8000] << 1,
4736 : : // which should result in [0,0].
4737 : 4 : int_range_max result;
4738 : 4 : op_lshift.fold_range (result, unsigned_type_node, op1, shift);
4739 : 4 : ASSERT_TRUE (result == zero);
4740 : 4 : }
4741 : : // signed VARYING = op1 << 1 should be VARYING.
4742 : 4 : if (TYPE_PRECISION (integer_type_node) > 31)
4743 : : {
4744 : : // unsigned VARYING = op1 << 1 should be VARYING.
4745 : 4 : int_range<2> lhs (integer_type_node);
4746 : 4 : int_range<2> shift (integer_type_node, INT (1), INT (1));
4747 : 4 : int_range_max op1;
4748 : 4 : op_lshift.op1_range (op1, integer_type_node, lhs, shift);
4749 : 4 : ASSERT_TRUE (op1.varying_p ());
4750 : :
4751 : : // 0 = op1 << 1 should be [0,0], [0x8000000, 0x8000000].
4752 : 4 : int_range<2> zero (integer_type_node, INT (0), INT (0));
4753 : 4 : op_lshift.op1_range (op1, integer_type_node, zero, shift);
4754 : 4 : ASSERT_TRUE (op1.num_pairs () == 2);
4755 : : // Remove the [0,0] range.
4756 : 4 : op1.intersect (zero);
4757 : 4 : ASSERT_TRUE (op1.num_pairs () == 1);
4758 : : // op1 << 1 should be [0x8000,0x8000] << 1,
4759 : : // which should result in [0,0].
4760 : 4 : int_range_max result;
4761 : 4 : op_lshift.fold_range (result, unsigned_type_node, op1, shift);
4762 : 4 : ASSERT_TRUE (result == zero);
4763 : 4 : }
4764 : 4 : }
4765 : :
4766 : : static void
4767 : 4 : range_op_rshift_tests ()
4768 : : {
4769 : : // unsigned: [3, MAX] = OP1 >> 1
4770 : 4 : {
4771 : 4 : int_range_max lhs (unsigned_type_node,
4772 : 4 : UINT (3), max_limit (unsigned_type_node));
4773 : 4 : int_range_max one (unsigned_type_node,
4774 : 4 : wi::one (TYPE_PRECISION (unsigned_type_node)),
4775 : 8 : wi::one (TYPE_PRECISION (unsigned_type_node)));
4776 : 4 : int_range_max op1;
4777 : 4 : op_rshift.op1_range (op1, unsigned_type_node, lhs, one);
4778 : 4 : ASSERT_FALSE (op1.contains_p (UINT (3)));
4779 : 4 : }
4780 : :
4781 : : // signed: [3, MAX] = OP1 >> 1
4782 : 4 : {
4783 : 4 : int_range_max lhs (integer_type_node,
4784 : 4 : INT (3), max_limit (integer_type_node));
4785 : 4 : int_range_max one (integer_type_node, INT (1), INT (1));
4786 : 4 : int_range_max op1;
4787 : 4 : op_rshift.op1_range (op1, integer_type_node, lhs, one);
4788 : 4 : ASSERT_FALSE (op1.contains_p (INT (-2)));
4789 : 4 : }
4790 : :
4791 : : // This is impossible, so OP1 should be [].
4792 : : // signed: [MIN, MIN] = OP1 >> 1
4793 : 4 : {
4794 : 4 : int_range_max lhs (integer_type_node,
4795 : 4 : min_limit (integer_type_node),
4796 : 4 : min_limit (integer_type_node));
4797 : 4 : int_range_max one (integer_type_node, INT (1), INT (1));
4798 : 4 : int_range_max op1;
4799 : 4 : op_rshift.op1_range (op1, integer_type_node, lhs, one);
4800 : 4 : ASSERT_TRUE (op1.undefined_p ());
4801 : 4 : }
4802 : :
4803 : : // signed: ~[-1] = OP1 >> 31
4804 : 4 : if (TYPE_PRECISION (integer_type_node) > 31)
4805 : : {
4806 : 4 : int_range_max lhs (integer_type_node, INT (-1), INT (-1), VR_ANTI_RANGE);
4807 : 4 : int_range_max shift (integer_type_node, INT (31), INT (31));
4808 : 4 : int_range_max op1;
4809 : 4 : op_rshift.op1_range (op1, integer_type_node, lhs, shift);
4810 : 4 : int_range_max negatives = range_negatives (integer_type_node);
4811 : 4 : negatives.intersect (op1);
4812 : 4 : ASSERT_TRUE (negatives.undefined_p ());
4813 : 4 : }
4814 : 4 : }
4815 : :
4816 : : static void
4817 : 4 : range_op_bitwise_and_tests ()
4818 : : {
4819 : 4 : int_range_max res;
4820 : 4 : wide_int min = min_limit (integer_type_node);
4821 : 4 : wide_int max = max_limit (integer_type_node);
4822 : 4 : wide_int tiny = wi::add (min, wi::one (TYPE_PRECISION (integer_type_node)));
4823 : 4 : int_range_max i1 (integer_type_node, tiny, max);
4824 : 4 : int_range_max i2 (integer_type_node, INT (255), INT (255));
4825 : :
4826 : : // [MIN+1, MAX] = OP1 & 255: OP1 is VARYING
4827 : 4 : op_bitwise_and.op1_range (res, integer_type_node, i1, i2);
4828 : 4 : ASSERT_TRUE (res == int_range<1> (integer_type_node));
4829 : :
4830 : : // VARYING = OP1 & 255: OP1 is VARYING
4831 : 4 : i1 = int_range<1> (integer_type_node);
4832 : 4 : op_bitwise_and.op1_range (res, integer_type_node, i1, i2);
4833 : 4 : ASSERT_TRUE (res == int_range<1> (integer_type_node));
4834 : :
4835 : : // For 0 = x & MASK, x is ~MASK.
4836 : 4 : {
4837 : 4 : int_range<2> zero (integer_type_node, INT (0), INT (0));
4838 : 4 : int_range<2> mask = int_range<2> (integer_type_node, INT (7), INT (7));
4839 : 4 : op_bitwise_and.op1_range (res, integer_type_node, zero, mask);
4840 : 4 : wide_int inv = wi::shwi (~7U, TYPE_PRECISION (integer_type_node));
4841 : 4 : ASSERT_TRUE (res.get_nonzero_bits () == inv);
4842 : 4 : }
4843 : :
4844 : : // (NONZERO | X) is nonzero.
4845 : 4 : i1.set_nonzero (integer_type_node);
4846 : 4 : i2.set_varying (integer_type_node);
4847 : 4 : op_bitwise_or.fold_range (res, integer_type_node, i1, i2);
4848 : 4 : ASSERT_TRUE (res.nonzero_p ());
4849 : :
4850 : : // (NEGATIVE | X) is nonzero.
4851 : 4 : i1 = int_range<1> (integer_type_node, INT (-5), INT (-3));
4852 : 4 : i2.set_varying (integer_type_node);
4853 : 4 : op_bitwise_or.fold_range (res, integer_type_node, i1, i2);
4854 : 4 : ASSERT_FALSE (res.contains_p (INT (0)));
4855 : 4 : }
4856 : :
4857 : : static void
4858 : 4 : range_relational_tests ()
4859 : : {
4860 : 4 : int_range<2> lhs (unsigned_char_type_node);
4861 : 4 : int_range<2> op1 (unsigned_char_type_node, UCHAR (8), UCHAR (10));
4862 : 4 : int_range<2> op2 (unsigned_char_type_node, UCHAR (20), UCHAR (20));
4863 : :
4864 : : // Never wrapping additions mean LHS > OP1.
4865 : 4 : relation_kind code = op_plus.lhs_op1_relation (lhs, op1, op2, VREL_VARYING);
4866 : 4 : ASSERT_TRUE (code == VREL_GT);
4867 : :
4868 : : // Most wrapping additions mean nothing...
4869 : 4 : op1 = int_range<2> (unsigned_char_type_node, UCHAR (8), UCHAR (10));
4870 : 4 : op2 = int_range<2> (unsigned_char_type_node, UCHAR (0), UCHAR (255));
4871 : 4 : code = op_plus.lhs_op1_relation (lhs, op1, op2, VREL_VARYING);
4872 : 4 : ASSERT_TRUE (code == VREL_VARYING);
4873 : :
4874 : : // However, always wrapping additions mean LHS < OP1.
4875 : 4 : op1 = int_range<2> (unsigned_char_type_node, UCHAR (1), UCHAR (255));
4876 : 4 : op2 = int_range<2> (unsigned_char_type_node, UCHAR (255), UCHAR (255));
4877 : 4 : code = op_plus.lhs_op1_relation (lhs, op1, op2, VREL_VARYING);
4878 : 4 : ASSERT_TRUE (code == VREL_LT);
4879 : 4 : }
4880 : :
4881 : : void
4882 : 4 : range_op_tests ()
4883 : : {
4884 : 4 : range_op_rshift_tests ();
4885 : 4 : range_op_lshift_tests ();
4886 : 4 : range_op_bitwise_and_tests ();
4887 : 4 : range_op_cast_tests ();
4888 : 4 : range_relational_tests ();
4889 : :
4890 : 4 : extern void range_op_float_tests ();
4891 : 4 : range_op_float_tests ();
4892 : 4 : }
4893 : :
4894 : : } // namespace selftest
4895 : :
4896 : : #endif // CHECKING_P
|
