Line data Source code
1 : /* Code for range operators.
2 : Copyright (C) 2017-2026 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 : static const operator_equal op_equal;
55 : static const operator_not_equal op_not_equal;
56 : static const operator_lt op_lt;
57 : static const operator_le op_le;
58 : static const operator_gt op_gt;
59 : static const operator_ge op_ge;
60 : static const operator_identity op_ident;
61 : static const operator_cst op_cst;
62 : static const operator_cast op_cast;
63 : static const operator_view op_view;
64 : static const operator_plus op_plus;
65 : static const operator_abs op_abs;
66 : static const operator_minus op_minus;
67 : static const operator_negate op_negate;
68 : static const operator_mult op_mult;
69 : static const operator_addr_expr op_addr;
70 : static const operator_bitwise_not op_bitwise_not;
71 : static const operator_bitwise_xor op_bitwise_xor;
72 : static const operator_bitwise_and op_bitwise_and;
73 : static const operator_bitwise_or op_bitwise_or;
74 : static const operator_min op_min;
75 : static const operator_max op_max;
76 :
77 : // Instantiate a range operator table.
78 : static range_op_table operator_table;
79 :
80 : // Invoke the initialization routines for each class of range.
81 :
82 291201 : range_op_table::range_op_table ()
83 : {
84 291201 : initialize_integral_ops ();
85 291201 : initialize_pointer_ops ();
86 291201 : initialize_float_ops ();
87 :
88 291201 : set (EQ_EXPR, op_equal);
89 291201 : set (NE_EXPR, op_not_equal);
90 291201 : set (LT_EXPR, op_lt);
91 291201 : set (LE_EXPR, op_le);
92 291201 : set (GT_EXPR, op_gt);
93 291201 : set (GE_EXPR, op_ge);
94 291201 : set (SSA_NAME, op_ident);
95 291201 : set (PAREN_EXPR, op_ident);
96 291201 : set (OBJ_TYPE_REF, op_ident);
97 291201 : set (REAL_CST, op_cst);
98 291201 : set (INTEGER_CST, op_cst);
99 291201 : set (NOP_EXPR, op_cast);
100 291201 : set (CONVERT_EXPR, op_cast);
101 291201 : set (VIEW_CONVERT_EXPR, op_view);
102 291201 : set (FLOAT_EXPR, op_cast);
103 291201 : set (FIX_TRUNC_EXPR, op_cast);
104 291201 : set (PLUS_EXPR, op_plus);
105 291201 : set (ABS_EXPR, op_abs);
106 291201 : set (MINUS_EXPR, op_minus);
107 291201 : set (NEGATE_EXPR, op_negate);
108 291201 : set (MULT_EXPR, op_mult);
109 291201 : set (ADDR_EXPR, op_addr);
110 291201 : set (BIT_NOT_EXPR, op_bitwise_not);
111 291201 : set (BIT_XOR_EXPR, op_bitwise_xor);
112 291201 : set (BIT_AND_EXPR, op_bitwise_and);
113 291201 : set (BIT_IOR_EXPR, op_bitwise_or);
114 291201 : set (MIN_EXPR, op_min);
115 291201 : set (MAX_EXPR, op_max);
116 291201 : }
117 :
118 : // Instantiate a default range operator for opcodes with no entry.
119 :
120 : range_operator default_operator;
121 :
122 : // Create a default range_op_handler.
123 :
124 1794833563 : range_op_handler::range_op_handler ()
125 : {
126 1794833563 : m_operator = &default_operator;
127 1794833563 : }
128 :
129 : // Create a range_op_handler for CODE. Use a default operator if CODE
130 : // does not have an entry.
131 :
132 4293722741 : range_op_handler::range_op_handler (unsigned code)
133 : {
134 4293722741 : m_operator = operator_table[code];
135 4293722741 : if (!m_operator)
136 836112350 : m_operator = &default_operator;
137 4293722741 : }
138 :
139 : // Return TRUE if this handler has a non-default operator.
140 :
141 6323787155 : range_op_handler::operator bool () const
142 : {
143 6323787155 : return m_operator != &default_operator;
144 : }
145 :
146 : // Return a pointer to the range operator associated with this handler.
147 : // If it is a default operator, return nullptr.
148 : // This is the equivalent of indexing the range table.
149 :
150 : const range_operator *
151 1060309301 : range_op_handler::range_op () const
152 : {
153 1060309301 : if (m_operator != &default_operator)
154 1060309301 : return m_operator;
155 : return nullptr;
156 : }
157 :
158 : // Create a dispatch pattern for value range discriminators LHS, OP1, and OP2.
159 : // This is used to produce a unique value for each dispatch pattern. Shift
160 : // values are based on the size of the m_discriminator field in value_range.h.
161 :
162 : constexpr unsigned
163 651286416 : dispatch_trio (unsigned lhs, unsigned op1, unsigned op2)
164 : {
165 651286416 : return ((lhs << 8) + (op1 << 4) + (op2));
166 : }
167 :
168 : // These are the supported dispatch patterns. These map to the parameter list
169 : // of the routines in range_operator. Note the last 3 characters are
170 : // shorthand for the LHS, OP1, and OP2 range discriminator class.
171 : // Reminder, single operand instructions use the LHS type for op2, even if
172 : // unused. So FLOAT = INT would be RO_FIF.
173 :
174 : static const unsigned RO_III = dispatch_trio (VR_IRANGE, VR_IRANGE, VR_IRANGE);
175 : static const unsigned RO_IFI = dispatch_trio (VR_IRANGE, VR_FRANGE, VR_IRANGE);
176 : static const unsigned RO_IFF = dispatch_trio (VR_IRANGE, VR_FRANGE, VR_FRANGE);
177 : static const unsigned RO_FFF = dispatch_trio (VR_FRANGE, VR_FRANGE, VR_FRANGE);
178 : static const unsigned RO_FIF = dispatch_trio (VR_FRANGE, VR_IRANGE, VR_FRANGE);
179 : static const unsigned RO_FII = dispatch_trio (VR_FRANGE, VR_IRANGE, VR_IRANGE);
180 : static const unsigned RO_PPP = dispatch_trio (VR_PRANGE, VR_PRANGE, VR_PRANGE);
181 : static const unsigned RO_PPI = dispatch_trio (VR_PRANGE, VR_PRANGE, VR_IRANGE);
182 : static const unsigned RO_IPP = dispatch_trio (VR_IRANGE, VR_PRANGE, VR_PRANGE);
183 : static const unsigned RO_IPI = dispatch_trio (VR_IRANGE, VR_PRANGE, VR_IRANGE);
184 : static const unsigned RO_PIP = dispatch_trio (VR_PRANGE, VR_IRANGE, VR_PRANGE);
185 : static const unsigned RO_PII = dispatch_trio (VR_PRANGE, VR_IRANGE, VR_IRANGE);
186 :
187 : // Return a dispatch value for parameter types LHS, OP1 and OP2.
188 :
189 : unsigned
190 651286416 : range_op_handler::dispatch_kind (const vrange &lhs, const vrange &op1,
191 : const vrange& op2) const
192 : {
193 651286416 : return dispatch_trio (lhs.m_discriminator, op1.m_discriminator,
194 651286416 : op2.m_discriminator);
195 : }
196 :
197 : void
198 0 : range_op_handler::discriminator_fail (const vrange &r1,
199 : const vrange &r2,
200 : const vrange &r3) const
201 : {
202 0 : const char name[] = "IPF";
203 0 : gcc_checking_assert (r1.m_discriminator < sizeof (name) - 1);
204 0 : gcc_checking_assert (r2.m_discriminator < sizeof (name) - 1);
205 0 : gcc_checking_assert (r3.m_discriminator < sizeof (name) - 1);
206 0 : fprintf (stderr,
207 : "Unsupported operand combination in dispatch: RO_%c%c%c\n",
208 0 : name[r1.m_discriminator],
209 0 : name[r2.m_discriminator],
210 0 : name[r3.m_discriminator]);
211 0 : gcc_unreachable ();
212 : }
213 :
214 : static inline bool
215 : has_pointer_operand_p (const vrange &r1, const vrange &r2, const vrange &r3)
216 : {
217 : return is_a <prange> (r1) || is_a <prange> (r2) || is_a <prange> (r3);
218 : }
219 :
220 : // Dispatch a call to fold_range based on the types of R, LH and RH.
221 :
222 : bool
223 292864851 : range_op_handler::fold_range (vrange &r, tree type,
224 : const vrange &lh,
225 : const vrange &rh,
226 : relation_trio rel) const
227 : {
228 292864851 : gcc_checking_assert (m_operator);
229 : #if CHECKING_P
230 292864851 : if (!lh.undefined_p () && !rh.undefined_p ())
231 287175215 : gcc_assert (m_operator->operand_check_p (type, lh.type (), rh.type ()));
232 : #endif
233 292864851 : switch (dispatch_kind (r, lh, rh))
234 : {
235 222007872 : case RO_III:
236 222007872 : return m_operator->fold_range (as_a <irange> (r), type,
237 : as_a <irange> (lh),
238 222007872 : as_a <irange> (rh), rel);
239 356641 : case RO_IFI:
240 356641 : return m_operator->fold_range (as_a <irange> (r), type,
241 : as_a <frange> (lh),
242 356641 : as_a <irange> (rh), rel);
243 2657893 : case RO_IFF:
244 2657893 : return m_operator->fold_range (as_a <irange> (r), type,
245 : as_a <frange> (lh),
246 2657893 : as_a <frange> (rh), rel);
247 7173688 : case RO_FFF:
248 7173688 : return m_operator->fold_range (as_a <frange> (r), type,
249 : as_a <frange> (lh),
250 7173688 : as_a <frange> (rh), rel);
251 0 : case RO_FII:
252 0 : return m_operator->fold_range (as_a <frange> (r), type,
253 : as_a <irange> (lh),
254 0 : as_a <irange> (rh), rel);
255 894921 : case RO_FIF:
256 894921 : return m_operator->fold_range (as_a <frange> (r), type,
257 : as_a <irange> (lh),
258 894921 : as_a <frange> (rh), rel);
259 18922796 : case RO_PPP:
260 18922796 : return m_operator->fold_range (as_a <prange> (r), type,
261 : as_a <prange> (lh),
262 18922796 : as_a <prange> (rh), rel);
263 9011807 : case RO_PPI:
264 9011807 : return m_operator->fold_range (as_a <prange> (r), type,
265 : as_a <prange> (lh),
266 9011807 : as_a <irange> (rh), rel);
267 18654317 : case RO_IPP:
268 18654317 : return m_operator->fold_range (as_a <irange> (r), type,
269 : as_a <prange> (lh),
270 18654317 : as_a <prange> (rh), rel);
271 1994092 : case RO_PIP:
272 1994092 : return m_operator->fold_range (as_a <prange> (r), type,
273 : as_a <irange> (lh),
274 1994092 : as_a <prange> (rh), rel);
275 11190792 : case RO_IPI:
276 11190792 : return m_operator->fold_range (as_a <irange> (r), type,
277 : as_a <prange> (lh),
278 11190792 : as_a <irange> (rh), rel);
279 : default:
280 : return false;
281 : }
282 : }
283 :
284 : // Dispatch a call to op1_range based on the types of R, LHS and OP2.
285 :
286 : bool
287 93104515 : range_op_handler::op1_range (vrange &r, tree type,
288 : const vrange &lhs,
289 : const vrange &op2,
290 : relation_trio rel) const
291 : {
292 93104515 : gcc_checking_assert (m_operator);
293 93104515 : if (lhs.undefined_p ())
294 : return false;
295 : #if CHECKING_P
296 93103438 : if (!op2.undefined_p ())
297 93103254 : gcc_assert (m_operator->operand_check_p (lhs.type (), type, op2.type ()));
298 : #endif
299 93103438 : switch (dispatch_kind (r, lhs, op2))
300 : {
301 80290086 : case RO_III:
302 80290086 : return m_operator->op1_range (as_a <irange> (r), type,
303 : as_a <irange> (lhs),
304 80290086 : as_a <irange> (op2), rel);
305 215641 : case RO_IFI:
306 215641 : return m_operator->op1_range (as_a <irange> (r), type,
307 : as_a <frange> (lhs),
308 215641 : as_a <irange> (op2), rel);
309 868895 : case RO_PPP:
310 868895 : return m_operator->op1_range (as_a <prange> (r), type,
311 : as_a <prange> (lhs),
312 868895 : as_a <prange> (op2), rel);
313 8724169 : case RO_PIP:
314 8724169 : return m_operator->op1_range (as_a <prange> (r), type,
315 : as_a <irange> (lhs),
316 8724169 : as_a <prange> (op2), rel);
317 411215 : case RO_PPI:
318 411215 : return m_operator->op1_range (as_a <prange> (r), type,
319 : as_a <prange> (lhs),
320 411215 : as_a <irange> (op2), rel);
321 238119 : case RO_IPI:
322 238119 : return m_operator->op1_range (as_a <irange> (r), type,
323 : as_a <prange> (lhs),
324 238119 : as_a <irange> (op2), rel);
325 1476259 : case RO_FIF:
326 1476259 : return m_operator->op1_range (as_a <frange> (r), type,
327 : as_a <irange> (lhs),
328 1476259 : as_a <frange> (op2), rel);
329 879054 : case RO_FFF:
330 879054 : return m_operator->op1_range (as_a <frange> (r), type,
331 : as_a <frange> (lhs),
332 879054 : as_a <frange> (op2), rel);
333 : default:
334 : return false;
335 : }
336 : }
337 :
338 : // Dispatch a call to op2_range based on the types of R, LHS and OP1.
339 :
340 : bool
341 25783862 : range_op_handler::op2_range (vrange &r, tree type,
342 : const vrange &lhs,
343 : const vrange &op1,
344 : relation_trio rel) const
345 : {
346 25783862 : gcc_checking_assert (m_operator);
347 25783862 : if (lhs.undefined_p ())
348 : return false;
349 : #if CHECKING_P
350 25783840 : if (!op1.undefined_p ())
351 25783747 : gcc_assert (m_operator->operand_check_p (lhs.type (), op1.type (), type));
352 : #endif
353 25783840 : switch (dispatch_kind (r, lhs, op1))
354 : {
355 19818537 : case RO_III:
356 19818537 : return m_operator->op2_range (as_a <irange> (r), type,
357 : as_a <irange> (lhs),
358 19818537 : as_a <irange> (op1), rel);
359 4901926 : case RO_PIP:
360 4901926 : return m_operator->op2_range (as_a <prange> (r), type,
361 : as_a <irange> (lhs),
362 4901926 : as_a <prange> (op1), rel);
363 229158 : case RO_IPP:
364 229158 : return m_operator->op2_range (as_a <irange> (r), type,
365 : as_a <prange> (lhs),
366 229158 : as_a <prange> (op1), rel);
367 497577 : case RO_FIF:
368 497577 : return m_operator->op2_range (as_a <frange> (r), type,
369 : as_a <irange> (lhs),
370 497577 : as_a <frange> (op1), rel);
371 336506 : case RO_FFF:
372 336506 : return m_operator->op2_range (as_a <frange> (r), type,
373 : as_a <frange> (lhs),
374 336506 : as_a <frange> (op1), rel);
375 : default:
376 : return false;
377 : }
378 : }
379 :
380 : // Dispatch a call to lhs_op1_relation based on the types of LHS, OP1 and OP2.
381 :
382 : relation_kind
383 122484387 : range_op_handler::lhs_op1_relation (const vrange &lhs,
384 : const vrange &op1,
385 : const vrange &op2,
386 : relation_kind rel) const
387 : {
388 122484387 : gcc_checking_assert (m_operator);
389 122484387 : switch (dispatch_kind (lhs, op1, op2))
390 : {
391 98199685 : case RO_III:
392 98199685 : return m_operator->lhs_op1_relation (as_a <irange> (lhs),
393 : as_a <irange> (op1),
394 98199685 : as_a <irange> (op2), rel);
395 1442288 : case RO_PPP:
396 1442288 : return m_operator->lhs_op1_relation (as_a <prange> (lhs),
397 : as_a <prange> (op1),
398 1442288 : as_a <prange> (op2), rel);
399 6274280 : case RO_IPP:
400 6274280 : return m_operator->lhs_op1_relation (as_a <irange> (lhs),
401 : as_a <prange> (op1),
402 6274280 : as_a <prange> (op2), rel);
403 1482292 : case RO_PII:
404 1482292 : return m_operator->lhs_op1_relation (as_a <prange> (lhs),
405 : as_a <irange> (op1),
406 1482292 : as_a <irange> (op2), rel);
407 7724524 : case RO_PPI:
408 7724524 : return m_operator->lhs_op1_relation (as_a <prange> (lhs),
409 : as_a <prange> (op1),
410 7724524 : as_a <irange> (op2), rel);
411 1060419 : case RO_IFF:
412 1060419 : return m_operator->lhs_op1_relation (as_a <irange> (lhs),
413 : as_a <frange> (op1),
414 1060419 : as_a <frange> (op2), rel);
415 5406525 : case RO_FFF:
416 5406525 : return m_operator->lhs_op1_relation (as_a <frange> (lhs),
417 : as_a <frange> (op1),
418 5406525 : as_a <frange> (op2), rel);
419 : default:
420 : return VREL_VARYING;
421 : }
422 : }
423 :
424 : // Dispatch a call to lhs_op2_relation based on the types of LHS, OP1 and OP2.
425 :
426 : relation_kind
427 36812610 : range_op_handler::lhs_op2_relation (const vrange &lhs,
428 : const vrange &op1,
429 : const vrange &op2,
430 : relation_kind rel) const
431 : {
432 36812610 : gcc_checking_assert (m_operator);
433 36812610 : switch (dispatch_kind (lhs, op1, op2))
434 : {
435 25521139 : case RO_III:
436 25521139 : return m_operator->lhs_op2_relation (as_a <irange> (lhs),
437 : as_a <irange> (op1),
438 25521139 : as_a <irange> (op2), rel);
439 181814 : case RO_IFF:
440 181814 : return m_operator->lhs_op2_relation (as_a <irange> (lhs),
441 : as_a <frange> (op1),
442 181814 : as_a <frange> (op2), rel);
443 3279187 : case RO_FFF:
444 3279187 : return m_operator->lhs_op2_relation (as_a <frange> (lhs),
445 : as_a <frange> (op1),
446 3279187 : as_a <frange> (op2), rel);
447 : default:
448 : return VREL_VARYING;
449 : }
450 : }
451 :
452 : // Dispatch a call to op1_op2_relation based on the type of LHS.
453 :
454 : relation_kind
455 80192609 : range_op_handler::op1_op2_relation (const vrange &lhs,
456 : const vrange &op1,
457 : const vrange &op2) const
458 : {
459 80192609 : gcc_checking_assert (m_operator);
460 :
461 80192609 : switch (dispatch_kind (lhs, op1, op2))
462 : {
463 61908894 : case RO_III:
464 61908894 : return m_operator->op1_op2_relation (as_a <irange> (lhs),
465 : as_a <irange> (op1),
466 61908894 : as_a <irange> (op2));
467 :
468 15534162 : case RO_IPP:
469 15534162 : return m_operator->op1_op2_relation (as_a <irange> (lhs),
470 : as_a <prange> (op1),
471 15534162 : as_a <prange> (op2));
472 :
473 1784181 : case RO_IFF:
474 1784181 : return m_operator->op1_op2_relation (as_a <irange> (lhs),
475 : as_a <frange> (op1),
476 1784181 : as_a <frange> (op2));
477 :
478 621634 : case RO_FFF:
479 621634 : return m_operator->op1_op2_relation (as_a <frange> (lhs),
480 : as_a <frange> (op1),
481 621634 : as_a <frange> (op2));
482 :
483 : default:
484 : return VREL_VARYING;
485 : }
486 : }
487 :
488 : bool
489 44681 : range_op_handler::overflow_free_p (const vrange &lh,
490 : const vrange &rh,
491 : relation_trio rel) const
492 : {
493 44681 : gcc_checking_assert (m_operator);
494 44681 : switch (dispatch_kind (lh, lh, rh))
495 : {
496 44681 : case RO_III:
497 44681 : return m_operator->overflow_free_p(as_a <irange> (lh),
498 : as_a <irange> (rh),
499 44681 : rel);
500 : default:
501 : return false;
502 : }
503 : }
504 :
505 : bool
506 9579931 : range_op_handler::operand_check_p (tree t1, tree t2, tree t3) const
507 : {
508 9579931 : gcc_checking_assert (m_operator);
509 9579931 : return m_operator->operand_check_p (t1, t2, t3);
510 : }
511 :
512 : // Update the known bitmasks in R when applying the operation CODE to
513 : // LH and RH.
514 :
515 : void
516 171959868 : update_known_bitmask (vrange &r, tree_code code,
517 : const vrange &lh, const vrange &rh)
518 : {
519 171959868 : if (r.undefined_p () || lh.undefined_p () || rh.undefined_p ()
520 343915518 : || r.singleton_p ())
521 8359639 : return;
522 :
523 163600229 : widest_int widest_value, widest_mask;
524 163600229 : tree type = r.type ();
525 163600229 : signop sign = TYPE_SIGN (type);
526 163600229 : int prec = TYPE_PRECISION (type);
527 163600229 : irange_bitmask lh_bits = lh.get_bitmask ();
528 163600229 : irange_bitmask rh_bits = rh.get_bitmask ();
529 :
530 163600229 : switch (get_gimple_rhs_class (code))
531 : {
532 57719894 : case GIMPLE_UNARY_RHS:
533 57719894 : bit_value_unop (code, sign, prec, &widest_value, &widest_mask,
534 57719894 : TYPE_SIGN (lh.type ()),
535 57719894 : TYPE_PRECISION (lh.type ()),
536 115440278 : widest_int::from (lh_bits.value (),
537 57719894 : TYPE_SIGN (lh.type ())),
538 115439788 : widest_int::from (lh_bits.mask (),
539 57719894 : TYPE_SIGN (lh.type ())));
540 57719894 : break;
541 105880335 : case GIMPLE_BINARY_RHS:
542 211760670 : bit_value_binop (code, sign, prec, &widest_value, &widest_mask,
543 105880335 : TYPE_SIGN (lh.type ()),
544 105880335 : TYPE_PRECISION (lh.type ()),
545 211761628 : widest_int::from (lh_bits.value (), sign),
546 211761628 : widest_int::from (lh_bits.mask (), sign),
547 105880335 : TYPE_SIGN (rh.type ()),
548 105880335 : TYPE_PRECISION (rh.type ()),
549 211761595 : widest_int::from (rh_bits.value (), sign),
550 211760670 : widest_int::from (rh_bits.mask (), sign));
551 105880335 : break;
552 0 : default:
553 0 : gcc_unreachable ();
554 : }
555 :
556 163600229 : wide_int mask = wide_int::from (widest_mask, prec, sign);
557 327200458 : wide_int value = wide_int::from (widest_value, prec, sign);
558 : // Bitmasks must have the unknown value bits cleared.
559 163600229 : value &= ~mask;
560 327200458 : irange_bitmask bm (value, mask);
561 163600229 : r.update_bitmask (bm);
562 163601225 : }
563 :
564 : // Return the upper limit for a type.
565 :
566 : static inline wide_int
567 17564917 : max_limit (const_tree type)
568 : {
569 17564917 : return irange_val_max (type);
570 : }
571 :
572 : // Return the lower limit for a type.
573 :
574 : static inline wide_int
575 20036013 : min_limit (const_tree type)
576 : {
577 20036013 : return irange_val_min (type);
578 : }
579 :
580 : // Return false if shifting by OP is undefined behavior. Otherwise, return
581 : // true and the range it is to be shifted by. This allows trimming out of
582 : // undefined ranges, leaving only valid ranges if there are any.
583 :
584 : static inline bool
585 4771792 : get_shift_range (irange &r, tree type, const irange &op)
586 : {
587 4771792 : if (op.undefined_p ())
588 : return false;
589 :
590 : // Build valid range and intersect it with the shift range.
591 4771369 : r.set (op.type (),
592 9542738 : wi::shwi (0, TYPE_PRECISION (op.type ())),
593 4771369 : wi::shwi (TYPE_PRECISION (type) - 1, TYPE_PRECISION (op.type ())));
594 4771369 : r.intersect (op);
595 :
596 : // If there are no valid ranges in the shift range, returned false.
597 4771369 : if (r.undefined_p ())
598 : return false;
599 : return true;
600 : }
601 :
602 : // Default wide_int fold operation returns [MIN, MAX].
603 :
604 : void
605 0 : range_operator::wi_fold (irange &r, tree type,
606 : const wide_int &lh_lb ATTRIBUTE_UNUSED,
607 : const wide_int &lh_ub ATTRIBUTE_UNUSED,
608 : const wide_int &rh_lb ATTRIBUTE_UNUSED,
609 : const wide_int &rh_ub ATTRIBUTE_UNUSED) const
610 : {
611 0 : gcc_checking_assert (r.supports_type_p (type));
612 0 : r.set_varying (type);
613 0 : }
614 :
615 : // Call wi_fold when both op1 and op2 are equivalent. Further split small
616 : // subranges into constants. This can provide better precision.
617 : // For x + y, when x == y with a range of [0,4] instead of [0, 8] produce
618 : // [0,0][2, 2][4,4][6, 6][8, 8]
619 : // LIMIT is the maximum number of elements in range allowed before we
620 : // do not process them individually.
621 :
622 : void
623 52630 : range_operator::wi_fold_in_parts_equiv (irange &r, tree type,
624 : const wide_int &lh_lb,
625 : const wide_int &lh_ub,
626 : unsigned limit) const
627 : {
628 52630 : int_range_max tmp;
629 105260 : widest_int lh_range = wi::sub (widest_int::from (lh_ub, TYPE_SIGN (type)),
630 105260 : widest_int::from (lh_lb, TYPE_SIGN (type)));
631 : // if there are 1 to 8 values in the LH range, split them up.
632 52630 : r.set_undefined ();
633 105260 : if (lh_range >= 0 && lh_range < limit)
634 : {
635 16209 : for (unsigned x = 0; x <= lh_range; x++)
636 : {
637 11070 : wide_int val = lh_lb + x;
638 11070 : wi_fold (tmp, type, val, val, val, val);
639 11070 : r.union_ (tmp);
640 11070 : }
641 : }
642 : // Otherwise just call wi_fold.
643 : else
644 47491 : wi_fold (r, type, lh_lb, lh_ub, lh_lb, lh_ub);
645 52630 : }
646 :
647 : // Call wi_fold, except further split small subranges into constants.
648 : // This can provide better precision. For something 8 >> [0,1]
649 : // Instead of [8, 16], we will produce [8,8][16,16]
650 :
651 : void
652 140950420 : range_operator::wi_fold_in_parts (irange &r, tree type,
653 : const wide_int &lh_lb,
654 : const wide_int &lh_ub,
655 : const wide_int &rh_lb,
656 : const wide_int &rh_ub) const
657 : {
658 140950420 : int_range_max tmp;
659 281900840 : widest_int rh_range = wi::sub (widest_int::from (rh_ub, TYPE_SIGN (type)),
660 281900840 : widest_int::from (rh_lb, TYPE_SIGN (type)));
661 281900840 : widest_int lh_range = wi::sub (widest_int::from (lh_ub, TYPE_SIGN (type)),
662 281900840 : widest_int::from (lh_lb, TYPE_SIGN (type)));
663 : // If there are 2, 3, or 4 values in the RH range, do them separately.
664 : // Call wi_fold_in_parts to check the RH side.
665 140950420 : if (rh_range > 0 && rh_range < 4)
666 : {
667 5155784 : wi_fold_in_parts (r, type, lh_lb, lh_ub, rh_lb, rh_lb);
668 5155784 : if (rh_range > 1)
669 : {
670 606008 : wi_fold_in_parts (tmp, type, lh_lb, lh_ub, rh_lb + 1, rh_lb + 1);
671 606008 : r.union_ (tmp);
672 606008 : if (rh_range == 3)
673 : {
674 388325 : wi_fold_in_parts (tmp, type, lh_lb, lh_ub, rh_lb + 2, rh_lb + 2);
675 388325 : r.union_ (tmp);
676 : }
677 : }
678 5155784 : wi_fold_in_parts (tmp, type, lh_lb, lh_ub, rh_ub, rh_ub);
679 5155784 : r.union_ (tmp);
680 : }
681 : // Otherwise check for 2, 3, or 4 values in the LH range and split them up.
682 : // The RH side has been checked, so no recursion needed.
683 135794636 : else if (lh_range > 0 && lh_range < 4)
684 : {
685 9902798 : wi_fold (r, type, lh_lb, lh_lb, rh_lb, rh_ub);
686 9902798 : if (lh_range > 1)
687 : {
688 1630374 : wi_fold (tmp, type, lh_lb + 1, lh_lb + 1, rh_lb, rh_ub);
689 1630366 : r.union_ (tmp);
690 1630366 : if (lh_range == 3)
691 : {
692 700964 : wi_fold (tmp, type, lh_lb + 2, lh_lb + 2, rh_lb, rh_ub);
693 700960 : r.union_ (tmp);
694 : }
695 : }
696 9902798 : wi_fold (tmp, type, lh_ub, lh_ub, rh_lb, rh_ub);
697 9902798 : r.union_ (tmp);
698 : }
699 : // Otherwise just call wi_fold.
700 : else
701 125891838 : wi_fold (r, type, lh_lb, lh_ub, rh_lb, rh_ub);
702 140950779 : }
703 :
704 : // The default for fold is to break all ranges into sub-ranges and
705 : // invoke the wi_fold method on each sub-range pair.
706 :
707 : bool
708 98509956 : range_operator::fold_range (irange &r, tree type,
709 : const irange &lh,
710 : const irange &rh,
711 : relation_trio trio) const
712 : {
713 98509956 : gcc_checking_assert (r.supports_type_p (type));
714 98509956 : if (empty_range_varying (r, type, lh, rh))
715 46619 : return true;
716 :
717 98463337 : relation_kind rel = trio.op1_op2 ();
718 98463337 : unsigned num_lh = lh.num_pairs ();
719 98463337 : unsigned num_rh = rh.num_pairs ();
720 :
721 : // If op1 and op2 are equivalences, then we don't need a complete cross
722 : // product, just pairs of matching elements.
723 98464488 : if (relation_equiv_p (rel) && lh == rh)
724 : {
725 49303 : int_range_max tmp;
726 49303 : r.set_undefined ();
727 89607 : for (unsigned x = 0; x < num_lh; ++x)
728 : {
729 : // If the number of subranges is too high, limit subrange creation.
730 52630 : unsigned limit = (r.num_pairs () > 32) ? 0 : 8;
731 52630 : wide_int lh_lb = lh.lower_bound (x);
732 52630 : wide_int lh_ub = lh.upper_bound (x);
733 52630 : wi_fold_in_parts_equiv (tmp, type, lh_lb, lh_ub, limit);
734 52630 : r.union_ (tmp);
735 52630 : if (r.varying_p ())
736 : break;
737 52630 : }
738 49303 : op1_op2_relation_effect (r, type, lh, rh, rel);
739 49303 : update_bitmask (r, lh, rh);
740 49303 : return true;
741 49303 : }
742 :
743 : // If both ranges are single pairs, fold directly into the result range.
744 : // If the number of subranges grows too high, produce a summary result as the
745 : // loop becomes exponential with little benefit. See PR 103821.
746 98414034 : if ((num_lh == 1 && num_rh == 1) || num_lh * num_rh > 12)
747 : {
748 81574635 : wi_fold_in_parts (r, type, lh.lower_bound (), lh.upper_bound (),
749 163146810 : rh.lower_bound (), rh.upper_bound ());
750 81573405 : op1_op2_relation_effect (r, type, lh, rh, rel);
751 81573405 : update_bitmask (r, lh, rh);
752 81573405 : return true;
753 : }
754 :
755 16840629 : int_range_max tmp;
756 16840629 : r.set_undefined ();
757 52412333 : for (unsigned x = 0; x < num_lh; ++x)
758 83642818 : for (unsigned y = 0; y < num_rh; ++y)
759 : {
760 48071114 : wide_int lh_lb = lh.lower_bound (x);
761 48071114 : wide_int lh_ub = lh.upper_bound (x);
762 48071114 : wide_int rh_lb = rh.lower_bound (y);
763 48071114 : wide_int rh_ub = rh.upper_bound (y);
764 48071114 : wi_fold_in_parts (tmp, type, lh_lb, lh_ub, rh_lb, rh_ub);
765 48071114 : r.union_ (tmp);
766 48071114 : if (r.varying_p ())
767 : {
768 3954353 : op1_op2_relation_effect (r, type, lh, rh, rel);
769 3954353 : update_bitmask (r, lh, rh);
770 3954353 : return true;
771 : }
772 48072371 : }
773 12886276 : op1_op2_relation_effect (r, type, lh, rh, rel);
774 12886276 : update_bitmask (r, lh, rh);
775 12886276 : return true;
776 16840629 : }
777 :
778 :
779 : bool
780 71117 : range_operator::fold_range (frange &, tree, const irange &,
781 : const frange &, relation_trio) const
782 : {
783 71117 : return false;
784 : }
785 :
786 : bool
787 1265 : range_operator::op1_range (irange &, tree, const frange &,
788 : const irange &, relation_trio) const
789 : {
790 1265 : return false;
791 : }
792 :
793 :
794 :
795 : // The default for op1_range is to return false.
796 :
797 : bool
798 778729 : range_operator::op1_range (irange &r ATTRIBUTE_UNUSED,
799 : tree type ATTRIBUTE_UNUSED,
800 : const irange &lhs ATTRIBUTE_UNUSED,
801 : const irange &op2 ATTRIBUTE_UNUSED,
802 : relation_trio) const
803 : {
804 778729 : return false;
805 : }
806 :
807 : // The default for op2_range is to return false.
808 :
809 : bool
810 552569 : range_operator::op2_range (irange &r ATTRIBUTE_UNUSED,
811 : tree type ATTRIBUTE_UNUSED,
812 : const irange &lhs ATTRIBUTE_UNUSED,
813 : const irange &op1 ATTRIBUTE_UNUSED,
814 : relation_trio) const
815 : {
816 552569 : return false;
817 : }
818 :
819 : // The default relation routines return VREL_VARYING.
820 :
821 : relation_kind
822 24316630 : range_operator::lhs_op1_relation (const irange &lhs ATTRIBUTE_UNUSED,
823 : const irange &op1 ATTRIBUTE_UNUSED,
824 : const irange &op2 ATTRIBUTE_UNUSED,
825 : relation_kind rel ATTRIBUTE_UNUSED) const
826 : {
827 24316630 : return VREL_VARYING;
828 : }
829 :
830 : relation_kind
831 17497332 : range_operator::lhs_op2_relation (const irange &lhs ATTRIBUTE_UNUSED,
832 : const irange &op1 ATTRIBUTE_UNUSED,
833 : const irange &op2 ATTRIBUTE_UNUSED,
834 : relation_kind rel ATTRIBUTE_UNUSED) const
835 : {
836 17497332 : return VREL_VARYING;
837 : }
838 :
839 : relation_kind
840 14876331 : range_operator::op1_op2_relation (const irange &lhs ATTRIBUTE_UNUSED,
841 : const irange &op1 ATTRIBUTE_UNUSED,
842 : const irange &op2 ATTRIBUTE_UNUSED) const
843 : {
844 14876331 : return VREL_VARYING;
845 : }
846 :
847 : // Default is no relation affects the LHS.
848 :
849 : bool
850 66810726 : range_operator::op1_op2_relation_effect (irange &lhs_range ATTRIBUTE_UNUSED,
851 : tree type ATTRIBUTE_UNUSED,
852 : const irange &op1_range
853 : ATTRIBUTE_UNUSED,
854 : const irange &op2_range
855 : ATTRIBUTE_UNUSED,
856 : relation_kind rel
857 : ATTRIBUTE_UNUSED) const
858 : {
859 66810726 : return false;
860 : }
861 :
862 : bool
863 0 : range_operator::overflow_free_p (const irange &, const irange &,
864 : relation_trio) const
865 : {
866 0 : return false;
867 : }
868 :
869 : // Apply any known bitmask updates based on this operator.
870 :
871 : void
872 6189 : range_operator::update_bitmask (irange &, const irange &,
873 : const irange &) const
874 : {
875 6189 : }
876 :
877 : // Check that operand types are OK. Default to always OK.
878 :
879 : bool
880 127551632 : range_operator::operand_check_p (tree, tree, tree) const
881 : {
882 127551632 : return true;
883 : }
884 :
885 : // Create and return a range from a pair of wide-ints that are known
886 : // to have overflowed (or underflowed).
887 :
888 : static void
889 40083061 : value_range_from_overflowed_bounds (irange &r, tree type,
890 : const wide_int &wmin,
891 : const wide_int &wmax)
892 : {
893 40083061 : const signop sgn = TYPE_SIGN (type);
894 40083061 : const unsigned int prec = TYPE_PRECISION (type);
895 :
896 40083061 : wide_int tmin = wide_int::from (wmin, prec, sgn);
897 40083061 : wide_int tmax = wide_int::from (wmax, prec, sgn);
898 :
899 40083061 : bool covers = false;
900 40083061 : wide_int tem = tmin;
901 40083061 : tmin = tmax + 1;
902 40083061 : if (wi::cmp (tmin, tmax, sgn) < 0)
903 2555391 : covers = true;
904 40083061 : tmax = tem - 1;
905 40083061 : if (wi::cmp (tmax, tem, sgn) > 0)
906 : covers = true;
907 :
908 : // If the anti-range would cover nothing, drop to varying.
909 : // Likewise if the anti-range bounds are outside of the types
910 : // values.
911 37558016 : if (covers || wi::cmp (tmin, tmax, sgn) > 0)
912 27069412 : r.set_varying (type);
913 : else
914 13013649 : r.set (type, tmin, tmax, VR_ANTI_RANGE);
915 40083713 : }
916 :
917 : // Create and return a range from a pair of wide-ints. MIN_OVF and
918 : // MAX_OVF describe any overflow that might have occurred while
919 : // calculating WMIN and WMAX respectively.
920 :
921 : static void
922 136860085 : value_range_with_overflow (irange &r, tree type,
923 : const wide_int &wmin, const wide_int &wmax,
924 : wi::overflow_type min_ovf = wi::OVF_NONE,
925 : wi::overflow_type max_ovf = wi::OVF_NONE)
926 : {
927 136860085 : const signop sgn = TYPE_SIGN (type);
928 136860085 : const unsigned int prec = TYPE_PRECISION (type);
929 216143715 : const bool overflow_wraps = TYPE_OVERFLOW_WRAPS (type);
930 :
931 : // For one bit precision if max != min, then the range covers all
932 : // values.
933 151475834 : if (prec == 1 && wi::ne_p (wmax, wmin))
934 : {
935 0 : r.set_varying (type);
936 0 : return;
937 : }
938 :
939 136860085 : if (overflow_wraps)
940 : {
941 : // If overflow wraps, truncate the values and adjust the range,
942 : // kind, and bounds appropriately.
943 79283630 : if ((min_ovf != wi::OVF_NONE) == (max_ovf != wi::OVF_NONE))
944 : {
945 56198168 : wide_int tmin = wide_int::from (wmin, prec, sgn);
946 56198168 : wide_int tmax = wide_int::from (wmax, prec, sgn);
947 : // If the limits are swapped, we wrapped around and cover
948 : // the entire range.
949 56198168 : if (wi::gt_p (tmin, tmax, sgn))
950 532547 : r.set_varying (type);
951 : else
952 : // No overflow or both overflow or underflow. The range
953 : // kind stays normal.
954 55665621 : r.set (type, tmin, tmax);
955 56198168 : return;
956 56198379 : }
957 :
958 23085462 : if ((min_ovf == wi::OVF_UNDERFLOW && max_ovf == wi::OVF_NONE)
959 16015552 : || (max_ovf == wi::OVF_OVERFLOW && min_ovf == wi::OVF_NONE))
960 23085462 : value_range_from_overflowed_bounds (r, type, wmin, wmax);
961 : else
962 : // Other underflow and/or overflow, drop to VR_VARYING.
963 0 : r.set_varying (type);
964 : }
965 : else
966 : {
967 : // If both bounds either underflowed or overflowed, then the result
968 : // is undefined.
969 57576455 : if ((min_ovf == wi::OVF_OVERFLOW && max_ovf == wi::OVF_OVERFLOW)
970 57574352 : || (min_ovf == wi::OVF_UNDERFLOW && max_ovf == wi::OVF_UNDERFLOW))
971 : {
972 4626 : r.set_undefined ();
973 4626 : return;
974 : }
975 :
976 : // If overflow does not wrap, saturate to [MIN, MAX].
977 57571829 : wide_int new_lb, new_ub;
978 57571829 : if (min_ovf == wi::OVF_UNDERFLOW)
979 7280477 : new_lb = wi::min_value (prec, sgn);
980 50291550 : else if (min_ovf == wi::OVF_OVERFLOW)
981 0 : new_lb = wi::max_value (prec, sgn);
982 : else
983 50291550 : new_lb = wmin;
984 :
985 57571829 : if (max_ovf == wi::OVF_UNDERFLOW)
986 0 : new_ub = wi::min_value (prec, sgn);
987 57571829 : else if (max_ovf == wi::OVF_OVERFLOW)
988 12064317 : new_ub = wi::max_value (prec, sgn);
989 : else
990 45507752 : new_ub = wmax;
991 :
992 57571829 : r.set (type, new_lb, new_ub);
993 57572386 : }
994 : }
995 :
996 : // Create and return a range from a pair of wide-ints. Canonicalize
997 : // the case where the bounds are swapped. In which case, we transform
998 : // [10,5] into [MIN,5][10,MAX].
999 :
1000 : static inline void
1001 87087793 : create_possibly_reversed_range (irange &r, tree type,
1002 : const wide_int &new_lb, const wide_int &new_ub)
1003 : {
1004 87087793 : signop s = TYPE_SIGN (type);
1005 : // If the bounds are swapped, treat the result as if an overflow occurred.
1006 87087793 : if (wi::gt_p (new_lb, new_ub, s))
1007 16997599 : value_range_from_overflowed_bounds (r, type, new_lb, new_ub);
1008 : else
1009 : // Otherwise it's just a normal range.
1010 70090194 : r.set (type, new_lb, new_ub);
1011 87087793 : }
1012 :
1013 : // Return the summary information about boolean range LHS. If EMPTY/FULL,
1014 : // return the equivalent range for TYPE in R; if FALSE/TRUE, do nothing.
1015 :
1016 : bool_range_state
1017 84032152 : get_bool_state (vrange &r, const vrange &lhs, tree val_type)
1018 : {
1019 : // If there is no result, then this is unexecutable.
1020 84032152 : if (lhs.undefined_p ())
1021 : {
1022 0 : r.set_undefined ();
1023 0 : return BRS_EMPTY;
1024 : }
1025 :
1026 84032152 : if (lhs.zero_p ())
1027 : return BRS_FALSE;
1028 :
1029 : // For TRUE, we can't just test for [1,1] because Ada can have
1030 : // multi-bit booleans, and TRUE values can be: [1, MAX], ~[0], etc.
1031 41733086 : if (lhs.contains_p (build_zero_cst (lhs.type ())))
1032 : {
1033 157170 : r.set_varying (val_type);
1034 157170 : return BRS_FULL;
1035 : }
1036 :
1037 : return BRS_TRUE;
1038 : }
1039 :
1040 : // ------------------------------------------------------------------------
1041 :
1042 : void
1043 0 : operator_equal::update_bitmask (irange &r, const irange &lh,
1044 : const irange &rh) const
1045 : {
1046 0 : update_known_bitmask (r, EQ_EXPR, lh, rh);
1047 0 : }
1048 :
1049 : // Check if the LHS range indicates a relation between OP1 and OP2.
1050 :
1051 : relation_kind
1052 5715931 : operator_equal::op1_op2_relation (const irange &lhs, const irange &,
1053 : const irange &) const
1054 : {
1055 5715931 : if (lhs.undefined_p ())
1056 : return VREL_UNDEFINED;
1057 :
1058 : // FALSE = op1 == op2 indicates NE_EXPR.
1059 5715931 : if (lhs.zero_p ())
1060 : return VREL_NE;
1061 :
1062 : // TRUE = op1 == op2 indicates EQ_EXPR.
1063 3157977 : if (!contains_zero_p (lhs))
1064 3139954 : return VREL_EQ;
1065 : return VREL_VARYING;
1066 : }
1067 :
1068 : bool
1069 18180424 : operator_equal::fold_range (irange &r, tree type,
1070 : const irange &op1,
1071 : const irange &op2,
1072 : relation_trio rel) const
1073 : {
1074 18180424 : if (relop_early_resolve (r, type, op1, op2, rel, VREL_EQ))
1075 : return true;
1076 :
1077 : // We can be sure the values are always equal or not if both ranges
1078 : // consist of a single value, and then compare them.
1079 18139367 : bool op1_const = wi::eq_p (op1.lower_bound (), op1.upper_bound ());
1080 18139367 : bool op2_const = wi::eq_p (op2.lower_bound (), op2.upper_bound ());
1081 18139355 : if (op1_const && op2_const)
1082 : {
1083 294486 : if (wi::eq_p (op1.lower_bound (), op2.upper_bound()))
1084 152181 : r = range_true (type);
1085 : else
1086 142305 : r = range_false (type);
1087 : }
1088 : else
1089 : {
1090 : // If ranges do not intersect, we know the range is not equal,
1091 : // otherwise we don't know anything for sure.
1092 17844869 : int_range_max tmp = op1;
1093 17844869 : tmp.intersect (op2);
1094 17844869 : if (tmp.undefined_p ())
1095 248770 : r = range_false (type);
1096 : // Check if a constant cannot satisfy the bitmask requirements.
1097 32868978 : else if (op2_const && !op1.get_bitmask ().member_p (op2.lower_bound ()))
1098 0 : r = range_false (type);
1099 17649854 : else if (op1_const && !op2.get_bitmask ().member_p (op1.lower_bound ()))
1100 0 : r = range_false (type);
1101 : else
1102 17596099 : r = range_true_and_false (type);
1103 17844869 : }
1104 : return true;
1105 : }
1106 :
1107 : bool
1108 11808203 : operator_equal::op1_range (irange &r, tree type,
1109 : const irange &lhs,
1110 : const irange &op2,
1111 : relation_trio) const
1112 : {
1113 11808203 : switch (get_bool_state (r, lhs, type))
1114 : {
1115 3744383 : case BRS_TRUE:
1116 : // If it's true, the result is the same as OP2.
1117 3744383 : r = op2;
1118 3744383 : break;
1119 :
1120 8039085 : case BRS_FALSE:
1121 : // If the result is false, the only time we know anything is
1122 : // if OP2 is a constant.
1123 8039085 : if (!op2.undefined_p ()
1124 24117255 : && wi::eq_p (op2.lower_bound(), op2.upper_bound()))
1125 : {
1126 6519724 : r = op2;
1127 6519724 : r.invert ();
1128 : }
1129 : else
1130 1519361 : r.set_varying (type);
1131 : break;
1132 :
1133 : default:
1134 : break;
1135 : }
1136 11808203 : return true;
1137 : }
1138 :
1139 : bool
1140 1446910 : operator_equal::op2_range (irange &r, tree type,
1141 : const irange &lhs,
1142 : const irange &op1,
1143 : relation_trio rel) const
1144 : {
1145 1446910 : return operator_equal::op1_range (r, type, lhs, op1, rel.swap_op1_op2 ());
1146 : }
1147 :
1148 : // -------------------------------------------------------------------------
1149 :
1150 : void
1151 0 : operator_not_equal::update_bitmask (irange &r, const irange &lh,
1152 : const irange &rh) const
1153 : {
1154 0 : update_known_bitmask (r, NE_EXPR, lh, rh);
1155 0 : }
1156 :
1157 : // Check if the LHS range indicates a relation between OP1 and OP2.
1158 :
1159 : relation_kind
1160 9737148 : operator_not_equal::op1_op2_relation (const irange &lhs, const irange &,
1161 : const irange &) const
1162 : {
1163 9737148 : if (lhs.undefined_p ())
1164 : return VREL_UNDEFINED;
1165 :
1166 : // FALSE = op1 != op2 indicates EQ_EXPR.
1167 9737148 : if (lhs.zero_p ())
1168 : return VREL_EQ;
1169 :
1170 : // TRUE = op1 != op2 indicates NE_EXPR.
1171 4555788 : if (!contains_zero_p (lhs))
1172 4515854 : return VREL_NE;
1173 : return VREL_VARYING;
1174 : }
1175 :
1176 : bool
1177 26934918 : operator_not_equal::fold_range (irange &r, tree type,
1178 : const irange &op1,
1179 : const irange &op2,
1180 : relation_trio rel) const
1181 : {
1182 26934918 : if (relop_early_resolve (r, type, op1, op2, rel, VREL_NE))
1183 : return true;
1184 :
1185 : // We can be sure the values are always equal or not if both ranges
1186 : // consist of a single value, and then compare them.
1187 26913895 : bool op1_const = wi::eq_p (op1.lower_bound (), op1.upper_bound ());
1188 26913895 : bool op2_const = wi::eq_p (op2.lower_bound (), op2.upper_bound ());
1189 26913513 : if (op1_const && op2_const)
1190 : {
1191 1164698 : if (wi::ne_p (op1.lower_bound (), op2.upper_bound()))
1192 658630 : r = range_true (type);
1193 : else
1194 506066 : r = range_false (type);
1195 : }
1196 : else
1197 : {
1198 : // If ranges do not intersect, we know the range is not equal,
1199 : // otherwise we don't know anything for sure.
1200 25748817 : int_range_max tmp = op1;
1201 25748817 : tmp.intersect (op2);
1202 25748817 : if (tmp.undefined_p ())
1203 302864 : r = range_true (type);
1204 : // Check if a constant cannot satisfy the bitmask requirements.
1205 46502929 : else if (op2_const && !op1.get_bitmask ().member_p (op2.lower_bound ()))
1206 0 : r = range_true (type);
1207 25480607 : else if (op1_const && !op2.get_bitmask ().member_p (op1.lower_bound ()))
1208 0 : r = range_true (type);
1209 : else
1210 25445953 : r = range_true_and_false (type);
1211 25748817 : }
1212 : return true;
1213 : }
1214 :
1215 : bool
1216 20434632 : operator_not_equal::op1_range (irange &r, tree type,
1217 : const irange &lhs,
1218 : const irange &op2,
1219 : relation_trio) const
1220 : {
1221 20434632 : switch (get_bool_state (r, lhs, type))
1222 : {
1223 12366938 : case BRS_TRUE:
1224 : // If the result is true, the only time we know anything is if
1225 : // OP2 is a constant.
1226 12366938 : if (!op2.undefined_p ()
1227 37100814 : && wi::eq_p (op2.lower_bound(), op2.upper_bound()))
1228 : {
1229 10004685 : r = op2;
1230 10004685 : r.invert ();
1231 : }
1232 : else
1233 2362253 : r.set_varying (type);
1234 : break;
1235 :
1236 8045085 : case BRS_FALSE:
1237 : // If it's false, the result is the same as OP2.
1238 8045085 : r = op2;
1239 8045085 : break;
1240 :
1241 : default:
1242 : break;
1243 : }
1244 20434632 : return true;
1245 : }
1246 :
1247 :
1248 : bool
1249 2462752 : operator_not_equal::op2_range (irange &r, tree type,
1250 : const irange &lhs,
1251 : const irange &op1,
1252 : relation_trio rel) const
1253 : {
1254 2462752 : return operator_not_equal::op1_range (r, type, lhs, op1, rel.swap_op1_op2 ());
1255 : }
1256 :
1257 : // (X < VAL) produces the range of [MIN, VAL - 1].
1258 :
1259 : static void
1260 6245156 : build_lt (irange &r, tree type, const wide_int &val)
1261 : {
1262 6245156 : wi::overflow_type ov;
1263 6245156 : wide_int lim;
1264 6245156 : signop sgn = TYPE_SIGN (type);
1265 :
1266 : // Signed 1 bit cannot represent 1 for subtraction.
1267 6245156 : if (sgn == SIGNED)
1268 4208515 : lim = wi::add (val, -1, sgn, &ov);
1269 : else
1270 2036699 : lim = wi::sub (val, 1, sgn, &ov);
1271 :
1272 : // If val - 1 underflows, check if X < MIN, which is an empty range.
1273 6245156 : if (ov)
1274 274 : r.set_undefined ();
1275 : else
1276 6244940 : r = int_range<1> (type, min_limit (type), lim);
1277 6245156 : }
1278 :
1279 : // (X <= VAL) produces the range of [MIN, VAL].
1280 :
1281 : static void
1282 13791103 : build_le (irange &r, tree type, const wide_int &val)
1283 : {
1284 13791103 : r = int_range<1> (type, min_limit (type), val);
1285 13791103 : }
1286 :
1287 : // (X > VAL) produces the range of [VAL + 1, MAX].
1288 :
1289 : static void
1290 10514294 : build_gt (irange &r, tree type, const wide_int &val)
1291 : {
1292 10514294 : wi::overflow_type ov;
1293 10514294 : wide_int lim;
1294 10514294 : signop sgn = TYPE_SIGN (type);
1295 :
1296 : // Signed 1 bit cannot represent 1 for addition.
1297 10514294 : if (sgn == SIGNED)
1298 5837091 : lim = wi::sub (val, -1, sgn, &ov);
1299 : else
1300 4677290 : lim = wi::add (val, 1, sgn, &ov);
1301 : // If val + 1 overflows, check is for X > MAX, which is an empty range.
1302 10514294 : if (ov)
1303 0 : r.set_undefined ();
1304 : else
1305 10514381 : r = int_range<1> (type, lim, max_limit (type));
1306 10514294 : }
1307 :
1308 : // (X >= val) produces the range of [VAL, MAX].
1309 :
1310 : static void
1311 7050595 : build_ge (irange &r, tree type, const wide_int &val)
1312 : {
1313 7050595 : r = int_range<1> (type, val, max_limit (type));
1314 7050595 : }
1315 :
1316 :
1317 : void
1318 0 : operator_lt::update_bitmask (irange &r, const irange &lh,
1319 : const irange &rh) const
1320 : {
1321 0 : update_known_bitmask (r, LT_EXPR, lh, rh);
1322 0 : }
1323 :
1324 : // Check if the LHS range indicates a relation between OP1 and OP2.
1325 :
1326 : relation_kind
1327 11802959 : operator_lt::op1_op2_relation (const irange &lhs, const irange &,
1328 : const irange &) const
1329 : {
1330 11802959 : if (lhs.undefined_p ())
1331 : return VREL_UNDEFINED;
1332 :
1333 : // FALSE = op1 < op2 indicates GE_EXPR.
1334 11802959 : if (lhs.zero_p ())
1335 : return VREL_GE;
1336 :
1337 : // TRUE = op1 < op2 indicates LT_EXPR.
1338 5944400 : if (!contains_zero_p (lhs))
1339 5937254 : return VREL_LT;
1340 : return VREL_VARYING;
1341 : }
1342 :
1343 : bool
1344 6590260 : operator_lt::fold_range (irange &r, tree type,
1345 : const irange &op1,
1346 : const irange &op2,
1347 : relation_trio rel) const
1348 : {
1349 6590260 : if (relop_early_resolve (r, type, op1, op2, rel, VREL_LT))
1350 : return true;
1351 :
1352 6566654 : signop sign = TYPE_SIGN (op1.type ());
1353 6566654 : gcc_checking_assert (sign == TYPE_SIGN (op2.type ()));
1354 :
1355 6566690 : if (wi::lt_p (op1.upper_bound (), op2.lower_bound (), sign))
1356 21723 : r = range_true (type);
1357 6544967 : else if (!wi::lt_p (op1.lower_bound (), op2.upper_bound (), sign))
1358 60209 : r = range_false (type);
1359 : // Use nonzero bits to determine if < 0 is false.
1360 8544043 : else if (op2.zero_p () && !wi::neg_p (op1.get_nonzero_bits (), sign))
1361 0 : r = range_false (type);
1362 : else
1363 6484722 : r = range_true_and_false (type);
1364 : return true;
1365 : }
1366 :
1367 : bool
1368 5478597 : operator_lt::op1_range (irange &r, tree type,
1369 : const irange &lhs,
1370 : const irange &op2,
1371 : relation_trio) const
1372 : {
1373 5478597 : if (op2.undefined_p ())
1374 : return false;
1375 :
1376 5478597 : switch (get_bool_state (r, lhs, type))
1377 : {
1378 2359803 : case BRS_TRUE:
1379 2359803 : build_lt (r, type, op2.upper_bound ());
1380 2359803 : break;
1381 :
1382 3114450 : case BRS_FALSE:
1383 3114450 : build_ge (r, type, op2.lower_bound ());
1384 3114450 : break;
1385 :
1386 : default:
1387 : break;
1388 : }
1389 : return true;
1390 : }
1391 :
1392 : bool
1393 3807753 : operator_lt::op2_range (irange &r, tree type,
1394 : const irange &lhs,
1395 : const irange &op1,
1396 : relation_trio) const
1397 : {
1398 3807753 : if (op1.undefined_p ())
1399 : return false;
1400 :
1401 3807751 : switch (get_bool_state (r, lhs, type))
1402 : {
1403 1627966 : case BRS_TRUE:
1404 1627966 : build_gt (r, type, op1.lower_bound ());
1405 1627966 : break;
1406 :
1407 2176402 : case BRS_FALSE:
1408 2176402 : build_le (r, type, op1.upper_bound ());
1409 2176402 : break;
1410 :
1411 : default:
1412 : break;
1413 : }
1414 : return true;
1415 : }
1416 :
1417 :
1418 : void
1419 0 : operator_le::update_bitmask (irange &r, const irange &lh,
1420 : const irange &rh) const
1421 : {
1422 0 : update_known_bitmask (r, LE_EXPR, lh, rh);
1423 0 : }
1424 :
1425 : // Check if the LHS range indicates a relation between OP1 and OP2.
1426 :
1427 : relation_kind
1428 4327960 : operator_le::op1_op2_relation (const irange &lhs, const irange &,
1429 : const irange &) const
1430 : {
1431 4327960 : if (lhs.undefined_p ())
1432 : return VREL_UNDEFINED;
1433 :
1434 : // FALSE = op1 <= op2 indicates GT_EXPR.
1435 4327960 : if (lhs.zero_p ())
1436 : return VREL_GT;
1437 :
1438 : // TRUE = op1 <= op2 indicates LE_EXPR.
1439 2416223 : if (!contains_zero_p (lhs))
1440 2407324 : return VREL_LE;
1441 : return VREL_VARYING;
1442 : }
1443 :
1444 : bool
1445 5277222 : operator_le::fold_range (irange &r, tree type,
1446 : const irange &op1,
1447 : const irange &op2,
1448 : relation_trio rel) const
1449 : {
1450 5277222 : if (relop_early_resolve (r, type, op1, op2, rel, VREL_LE))
1451 : return true;
1452 :
1453 5265181 : signop sign = TYPE_SIGN (op1.type ());
1454 5265181 : gcc_checking_assert (sign == TYPE_SIGN (op2.type ()));
1455 :
1456 5265185 : if (wi::le_p (op1.upper_bound (), op2.lower_bound (), sign))
1457 139258 : r = range_true (type);
1458 5125927 : else if (!wi::le_p (op1.lower_bound (), op2.upper_bound (), sign))
1459 54473 : r = range_false (type);
1460 : else
1461 5071450 : r = range_true_and_false (type);
1462 : return true;
1463 : }
1464 :
1465 : bool
1466 6480105 : operator_le::op1_range (irange &r, tree type,
1467 : const irange &lhs,
1468 : const irange &op2,
1469 : relation_trio) const
1470 : {
1471 6480105 : if (op2.undefined_p ())
1472 : return false;
1473 :
1474 6480105 : switch (get_bool_state (r, lhs, type))
1475 : {
1476 3247829 : case BRS_TRUE:
1477 3247829 : build_le (r, type, op2.upper_bound ());
1478 3247829 : break;
1479 :
1480 3219846 : case BRS_FALSE:
1481 3219846 : build_gt (r, type, op2.lower_bound ());
1482 3219846 : break;
1483 :
1484 : default:
1485 : break;
1486 : }
1487 : return true;
1488 : }
1489 :
1490 : bool
1491 1111333 : operator_le::op2_range (irange &r, tree type,
1492 : const irange &lhs,
1493 : const irange &op1,
1494 : relation_trio) const
1495 : {
1496 1111333 : if (op1.undefined_p ())
1497 : return false;
1498 :
1499 1111333 : switch (get_bool_state (r, lhs, type))
1500 : {
1501 488187 : case BRS_TRUE:
1502 488187 : build_ge (r, type, op1.lower_bound ());
1503 488187 : break;
1504 :
1505 619334 : case BRS_FALSE:
1506 619334 : build_lt (r, type, op1.upper_bound ());
1507 619334 : break;
1508 :
1509 : default:
1510 : break;
1511 : }
1512 : return true;
1513 : }
1514 :
1515 :
1516 : void
1517 0 : operator_gt::update_bitmask (irange &r, const irange &lh,
1518 : const irange &rh) const
1519 : {
1520 0 : update_known_bitmask (r, GT_EXPR, lh, rh);
1521 0 : }
1522 :
1523 : // Check if the LHS range indicates a relation between OP1 and OP2.
1524 :
1525 : relation_kind
1526 11600024 : operator_gt::op1_op2_relation (const irange &lhs, const irange &,
1527 : const irange &) const
1528 : {
1529 11600024 : if (lhs.undefined_p ())
1530 : return VREL_UNDEFINED;
1531 :
1532 : // FALSE = op1 > op2 indicates LE_EXPR.
1533 11600024 : if (lhs.zero_p ())
1534 : return VREL_LE;
1535 :
1536 : // TRUE = op1 > op2 indicates GT_EXPR.
1537 6141355 : if (!contains_zero_p (lhs))
1538 6128107 : return VREL_GT;
1539 : return VREL_VARYING;
1540 : }
1541 :
1542 : bool
1543 11843797 : operator_gt::fold_range (irange &r, tree type,
1544 : const irange &op1, const irange &op2,
1545 : relation_trio rel) const
1546 : {
1547 11843797 : if (relop_early_resolve (r, type, op1, op2, rel, VREL_GT))
1548 : return true;
1549 :
1550 11793723 : signop sign = TYPE_SIGN (op1.type ());
1551 11793723 : gcc_checking_assert (sign == TYPE_SIGN (op2.type ()));
1552 :
1553 11793749 : if (wi::gt_p (op1.lower_bound (), op2.upper_bound (), sign))
1554 107368 : r = range_true (type);
1555 11686381 : else if (!wi::gt_p (op1.upper_bound (), op2.lower_bound (), sign))
1556 382991 : r = range_false (type);
1557 : else
1558 11303364 : r = range_true_and_false (type);
1559 : return true;
1560 : }
1561 :
1562 : bool
1563 12714554 : operator_gt::op1_range (irange &r, tree type,
1564 : const irange &lhs, const irange &op2,
1565 : relation_trio) const
1566 : {
1567 12714554 : if (op2.undefined_p ())
1568 : return false;
1569 :
1570 12714554 : switch (get_bool_state (r, lhs, type))
1571 : {
1572 5123530 : case BRS_TRUE:
1573 5123530 : build_gt (r, type, op2.lower_bound ());
1574 5123530 : break;
1575 :
1576 7581879 : case BRS_FALSE:
1577 7581879 : build_le (r, type, op2.upper_bound ());
1578 7581879 : break;
1579 :
1580 : default:
1581 : break;
1582 : }
1583 : return true;
1584 : }
1585 :
1586 : bool
1587 3559883 : operator_gt::op2_range (irange &r, tree type,
1588 : const irange &lhs,
1589 : const irange &op1,
1590 : relation_trio) const
1591 : {
1592 3559883 : if (op1.undefined_p ())
1593 : return false;
1594 :
1595 3559883 : switch (get_bool_state (r, lhs, type))
1596 : {
1597 2114944 : case BRS_TRUE:
1598 2114944 : build_lt (r, type, op1.upper_bound ());
1599 2114944 : break;
1600 :
1601 1436433 : case BRS_FALSE:
1602 1436433 : build_ge (r, type, op1.lower_bound ());
1603 1436433 : break;
1604 :
1605 : default:
1606 : break;
1607 : }
1608 : return true;
1609 : }
1610 :
1611 :
1612 : void
1613 0 : operator_ge::update_bitmask (irange &r, const irange &lh,
1614 : const irange &rh) const
1615 : {
1616 0 : update_known_bitmask (r, GE_EXPR, lh, rh);
1617 0 : }
1618 :
1619 : // Check if the LHS range indicates a relation between OP1 and OP2.
1620 :
1621 : relation_kind
1622 3848541 : operator_ge::op1_op2_relation (const irange &lhs, const irange &,
1623 : const irange &) const
1624 : {
1625 3848541 : if (lhs.undefined_p ())
1626 : return VREL_UNDEFINED;
1627 :
1628 : // FALSE = op1 >= op2 indicates LT_EXPR.
1629 3848541 : if (lhs.zero_p ())
1630 : return VREL_LT;
1631 :
1632 : // TRUE = op1 >= op2 indicates GE_EXPR.
1633 2053468 : if (!contains_zero_p (lhs))
1634 2047848 : return VREL_GE;
1635 : return VREL_VARYING;
1636 : }
1637 :
1638 : bool
1639 2639556 : operator_ge::fold_range (irange &r, tree type,
1640 : const irange &op1,
1641 : const irange &op2,
1642 : relation_trio rel) const
1643 : {
1644 2639556 : if (relop_early_resolve (r, type, op1, op2, rel, VREL_GE))
1645 : return true;
1646 :
1647 2627759 : signop sign = TYPE_SIGN (op1.type ());
1648 2627759 : gcc_checking_assert (sign == TYPE_SIGN (op2.type ()));
1649 :
1650 2627791 : if (wi::ge_p (op1.lower_bound (), op2.upper_bound (), sign))
1651 171345 : r = range_true (type);
1652 2456446 : else if (!wi::ge_p (op1.upper_bound (), op2.lower_bound (), sign))
1653 5847 : r = range_false (type);
1654 : else
1655 2450567 : r = range_true_and_false (type);
1656 : return true;
1657 : }
1658 :
1659 : bool
1660 3169486 : operator_ge::op1_range (irange &r, tree type,
1661 : const irange &lhs,
1662 : const irange &op2,
1663 : relation_trio) const
1664 : {
1665 3169486 : if (op2.undefined_p ())
1666 : return false;
1667 :
1668 3169486 : switch (get_bool_state (r, lhs, type))
1669 : {
1670 2011525 : case BRS_TRUE:
1671 2011525 : build_ge (r, type, op2.lower_bound ());
1672 2011525 : break;
1673 :
1674 1151075 : case BRS_FALSE:
1675 1151075 : build_lt (r, type, op2.upper_bound ());
1676 1151075 : break;
1677 :
1678 : default:
1679 : break;
1680 : }
1681 : return true;
1682 : }
1683 :
1684 : bool
1685 1330695 : operator_ge::op2_range (irange &r, tree type,
1686 : const irange &lhs,
1687 : const irange &op1,
1688 : relation_trio) const
1689 : {
1690 1330695 : if (op1.undefined_p ())
1691 : return false;
1692 :
1693 1330695 : switch (get_bool_state (r, lhs, type))
1694 : {
1695 784993 : case BRS_TRUE:
1696 784993 : build_le (r, type, op1.upper_bound ());
1697 784993 : break;
1698 :
1699 542952 : case BRS_FALSE:
1700 542952 : build_gt (r, type, op1.lower_bound ());
1701 542952 : break;
1702 :
1703 : default:
1704 : break;
1705 : }
1706 : return true;
1707 : }
1708 :
1709 :
1710 : void
1711 47453442 : operator_plus::update_bitmask (irange &r, const irange &lh,
1712 : const irange &rh) const
1713 : {
1714 47453442 : update_known_bitmask (r, PLUS_EXPR, lh, rh);
1715 47453442 : }
1716 :
1717 : // Check to see if the range of OP2 indicates anything about the relation
1718 : // between LHS and OP1.
1719 :
1720 : relation_kind
1721 43931376 : operator_plus::lhs_op1_relation (const irange &lhs,
1722 : const irange &op1,
1723 : const irange &op2,
1724 : relation_kind) const
1725 : {
1726 43931376 : if (lhs.undefined_p () || op1.undefined_p () || op2.undefined_p ())
1727 : return VREL_VARYING;
1728 :
1729 43903828 : tree type = lhs.type ();
1730 43903828 : unsigned prec = TYPE_PRECISION (type);
1731 43903828 : wi::overflow_type ovf1, ovf2;
1732 43903828 : signop sign = TYPE_SIGN (type);
1733 :
1734 : // LHS = OP1 + 0 indicates LHS == OP1.
1735 43903828 : if (op2.zero_p ())
1736 : return VREL_EQ;
1737 :
1738 43735096 : if (TYPE_OVERFLOW_WRAPS (type))
1739 : {
1740 24961329 : wi::add (op1.lower_bound (), op2.lower_bound (), sign, &ovf1);
1741 24961547 : wi::add (op1.upper_bound (), op2.upper_bound (), sign, &ovf2);
1742 : }
1743 : else
1744 18774203 : ovf1 = ovf2 = wi::OVF_NONE;
1745 :
1746 : // Never wrapping additions.
1747 43735096 : if (!ovf1 && !ovf2)
1748 : {
1749 : // Positive op2 means lhs > op1.
1750 26118246 : if (wi::gt_p (op2.lower_bound (), wi::zero (prec), sign))
1751 : return VREL_GT;
1752 10465862 : if (wi::ge_p (op2.lower_bound (), wi::zero (prec), sign))
1753 : return VREL_GE;
1754 :
1755 : // Negative op2 means lhs < op1.
1756 8428184 : if (wi::lt_p (op2.upper_bound (), wi::zero (prec), sign))
1757 : return VREL_LT;
1758 5212606 : if (wi::le_p (op2.upper_bound (), wi::zero (prec), sign))
1759 : return VREL_LE;
1760 : }
1761 : // Always wrapping additions.
1762 17617201 : else if (ovf1 && ovf1 == ovf2)
1763 : {
1764 : // Positive op2 means lhs < op1.
1765 709908 : if (wi::gt_p (op2.lower_bound (), wi::zero (prec), sign))
1766 : return VREL_LT;
1767 20 : if (wi::ge_p (op2.lower_bound (), wi::zero (prec), sign))
1768 : return VREL_LE;
1769 :
1770 : // Negative op2 means lhs > op1.
1771 20 : if (wi::lt_p (op2.upper_bound (), wi::zero (prec), sign))
1772 : return VREL_GT;
1773 0 : if (wi::le_p (op2.upper_bound (), wi::zero (prec), sign))
1774 : return VREL_GE;
1775 : }
1776 :
1777 : // If op2 does not contain 0, then LHS and OP1 can never be equal.
1778 22107091 : if (!range_includes_zero_p (op2))
1779 : return VREL_NE;
1780 :
1781 : return VREL_VARYING;
1782 : }
1783 :
1784 : // PLUS is symmetrical, so we can simply call lhs_op1_relation with reversed
1785 : // operands.
1786 :
1787 : relation_kind
1788 8023807 : operator_plus::lhs_op2_relation (const irange &lhs, const irange &op1,
1789 : const irange &op2, relation_kind rel) const
1790 : {
1791 8023807 : return lhs_op1_relation (lhs, op2, op1, rel);
1792 : }
1793 :
1794 : void
1795 70790283 : operator_plus::wi_fold (irange &r, tree type,
1796 : const wide_int &lh_lb, const wide_int &lh_ub,
1797 : const wide_int &rh_lb, const wide_int &rh_ub) const
1798 : {
1799 70790283 : wi::overflow_type ov_lb, ov_ub;
1800 70790283 : signop s = TYPE_SIGN (type);
1801 70790283 : wide_int new_lb = wi::add (lh_lb, rh_lb, s, &ov_lb);
1802 70790283 : wide_int new_ub = wi::add (lh_ub, rh_ub, s, &ov_ub);
1803 70790283 : value_range_with_overflow (r, type, new_lb, new_ub, ov_lb, ov_ub);
1804 70790283 : }
1805 :
1806 : // Given addition or subtraction, determine the possible NORMAL ranges and
1807 : // OVERFLOW ranges given an OFFSET range. ADD_P is true for addition.
1808 : // Return the relation that exists between the LHS and OP1 in order for the
1809 : // NORMAL range to apply.
1810 : // a return value of VREL_VARYING means no ranges were applicable.
1811 :
1812 : static relation_kind
1813 753744 : plus_minus_ranges (irange &r_ov, irange &r_normal, const irange &offset,
1814 : bool add_p)
1815 : {
1816 753744 : relation_kind kind = VREL_VARYING;
1817 : // For now, only deal with constant adds. This could be extended to ranges
1818 : // when someone is so motivated.
1819 753744 : if (!offset.singleton_p () || offset.zero_p ())
1820 739043 : return kind;
1821 :
1822 : // Always work with a positive offset. ie a+ -2 -> a-2 and a- -2 > a+2
1823 14701 : wide_int off = offset.lower_bound ();
1824 14701 : if (wi::neg_p (off, SIGNED))
1825 : {
1826 1215 : add_p = !add_p;
1827 1215 : off = wi::neg (off);
1828 : }
1829 :
1830 14701 : wi::overflow_type ov;
1831 14701 : tree type = offset.type ();
1832 14701 : unsigned prec = TYPE_PRECISION (type);
1833 14701 : wide_int ub;
1834 14701 : wide_int lb;
1835 : // calculate the normal range and relation for the operation.
1836 14701 : if (add_p)
1837 : {
1838 : // [ 0 , INF - OFF]
1839 13486 : lb = wi::zero (prec);
1840 13486 : ub = wi::sub (irange_val_max (type), off, UNSIGNED, &ov);
1841 13486 : kind = VREL_GT;
1842 : }
1843 : else
1844 : {
1845 : // [ OFF, INF ]
1846 1215 : lb = off;
1847 1215 : ub = irange_val_max (type);
1848 1215 : kind = VREL_LT;
1849 : }
1850 14701 : int_range<2> normal_range (type, lb, ub);
1851 14701 : int_range<2> ov_range (type, lb, ub, VR_ANTI_RANGE);
1852 :
1853 14701 : r_ov = ov_range;
1854 14701 : r_normal = normal_range;
1855 14701 : return kind;
1856 14701 : }
1857 :
1858 : // Once op1 has been calculated by operator_plus or operator_minus, check
1859 : // to see if the relation passed causes any part of the calculation to
1860 : // be not possible. ie
1861 : // a_2 = b_3 + 1 with a_2 < b_3 can refine the range of b_3 to [INF, INF]
1862 : // and that further refines a_2 to [0, 0].
1863 : // R is the value of op1, OP2 is the offset being added/subtracted, REL is the
1864 : // relation between LHS relation OP1 and ADD_P is true for PLUS, false for
1865 : // MINUS. IF any adjustment can be made, R will reflect it.
1866 :
1867 : static void
1868 10099659 : adjust_op1_for_overflow (irange &r, const irange &op2, relation_kind rel,
1869 : bool add_p)
1870 : {
1871 10099659 : if (r.undefined_p ())
1872 : return;
1873 10099657 : tree type = r.type ();
1874 : // Check for unsigned overflow and calculate the overflow part.
1875 10099657 : signop s = TYPE_SIGN (type);
1876 10099657 : if (!TYPE_OVERFLOW_WRAPS (type) || s == SIGNED)
1877 : return;
1878 :
1879 : // Only work with <, <=, >, >= relations.
1880 5106230 : if (!relation_lt_le_gt_ge_p (rel))
1881 : return;
1882 :
1883 : // Get the ranges for this offset.
1884 753744 : int_range_max normal, overflow;
1885 753744 : relation_kind k = plus_minus_ranges (overflow, normal, op2, add_p);
1886 :
1887 : // VREL_VARYING means there are no adjustments.
1888 753744 : if (k == VREL_VARYING)
1889 : return;
1890 :
1891 : // If the relations match use the normal range, otherwise use overflow range.
1892 14701 : if (relation_intersect (k, rel) == k)
1893 10618 : r.intersect (normal);
1894 : else
1895 4083 : r.intersect (overflow);
1896 : return;
1897 753744 : }
1898 :
1899 : bool
1900 9052426 : operator_plus::op1_range (irange &r, tree type,
1901 : const irange &lhs,
1902 : const irange &op2,
1903 : relation_trio trio) const
1904 : {
1905 9052426 : if (lhs.undefined_p ())
1906 : return false;
1907 : // Start with the default operation.
1908 9052426 : range_op_handler minus (MINUS_EXPR);
1909 9052426 : if (!minus)
1910 : return false;
1911 9052426 : bool res = minus.fold_range (r, type, lhs, op2);
1912 9052426 : relation_kind rel = trio.lhs_op1 ();
1913 : // Check for a relation refinement.
1914 9052426 : if (res)
1915 9052426 : adjust_op1_for_overflow (r, op2, rel, true /* PLUS_EXPR */);
1916 : return res;
1917 : }
1918 :
1919 : bool
1920 2097750 : operator_plus::op2_range (irange &r, tree type,
1921 : const irange &lhs,
1922 : const irange &op1,
1923 : relation_trio rel) const
1924 : {
1925 2097750 : return op1_range (r, type, lhs, op1, rel.swap_op1_op2 ());
1926 : }
1927 :
1928 : class operator_widen_plus_signed : public range_operator
1929 : {
1930 : public:
1931 : virtual void wi_fold (irange &r, tree type,
1932 : const wide_int &lh_lb,
1933 : const wide_int &lh_ub,
1934 : const wide_int &rh_lb,
1935 : const wide_int &rh_ub) const;
1936 : } op_widen_plus_signed;
1937 :
1938 : void
1939 0 : operator_widen_plus_signed::wi_fold (irange &r, tree type,
1940 : const wide_int &lh_lb,
1941 : const wide_int &lh_ub,
1942 : const wide_int &rh_lb,
1943 : const wide_int &rh_ub) const
1944 : {
1945 0 : wi::overflow_type ov_lb, ov_ub;
1946 0 : signop s = TYPE_SIGN (type);
1947 :
1948 0 : wide_int lh_wlb
1949 0 : = wide_int::from (lh_lb, wi::get_precision (lh_lb) * 2, SIGNED);
1950 0 : wide_int lh_wub
1951 0 : = wide_int::from (lh_ub, wi::get_precision (lh_ub) * 2, SIGNED);
1952 0 : wide_int rh_wlb = wide_int::from (rh_lb, wi::get_precision (rh_lb) * 2, s);
1953 0 : wide_int rh_wub = wide_int::from (rh_ub, wi::get_precision (rh_ub) * 2, s);
1954 :
1955 0 : wide_int new_lb = wi::add (lh_wlb, rh_wlb, s, &ov_lb);
1956 0 : wide_int new_ub = wi::add (lh_wub, rh_wub, s, &ov_ub);
1957 :
1958 0 : r = int_range<2> (type, new_lb, new_ub);
1959 0 : }
1960 :
1961 : class operator_widen_plus_unsigned : public range_operator
1962 : {
1963 : public:
1964 : virtual void wi_fold (irange &r, tree type,
1965 : const wide_int &lh_lb,
1966 : const wide_int &lh_ub,
1967 : const wide_int &rh_lb,
1968 : const wide_int &rh_ub) const;
1969 : } op_widen_plus_unsigned;
1970 :
1971 : void
1972 0 : operator_widen_plus_unsigned::wi_fold (irange &r, tree type,
1973 : const wide_int &lh_lb,
1974 : const wide_int &lh_ub,
1975 : const wide_int &rh_lb,
1976 : const wide_int &rh_ub) const
1977 : {
1978 0 : wi::overflow_type ov_lb, ov_ub;
1979 0 : signop s = TYPE_SIGN (type);
1980 :
1981 0 : wide_int lh_wlb
1982 0 : = wide_int::from (lh_lb, wi::get_precision (lh_lb) * 2, UNSIGNED);
1983 0 : wide_int lh_wub
1984 0 : = wide_int::from (lh_ub, wi::get_precision (lh_ub) * 2, UNSIGNED);
1985 0 : wide_int rh_wlb = wide_int::from (rh_lb, wi::get_precision (rh_lb) * 2, s);
1986 0 : wide_int rh_wub = wide_int::from (rh_ub, wi::get_precision (rh_ub) * 2, s);
1987 :
1988 0 : wide_int new_lb = wi::add (lh_wlb, rh_wlb, s, &ov_lb);
1989 0 : wide_int new_ub = wi::add (lh_wub, rh_wub, s, &ov_ub);
1990 :
1991 0 : r = int_range<2> (type, new_lb, new_ub);
1992 0 : }
1993 :
1994 : void
1995 17999499 : operator_minus::update_bitmask (irange &r, const irange &lh,
1996 : const irange &rh) const
1997 : {
1998 17999499 : update_known_bitmask (r, MINUS_EXPR, lh, rh);
1999 17999499 : }
2000 :
2001 : void
2002 25339739 : operator_minus::wi_fold (irange &r, tree type,
2003 : const wide_int &lh_lb, const wide_int &lh_ub,
2004 : const wide_int &rh_lb, const wide_int &rh_ub) const
2005 : {
2006 25339739 : wi::overflow_type ov_lb, ov_ub;
2007 25339739 : signop s = TYPE_SIGN (type);
2008 25339739 : wide_int new_lb = wi::sub (lh_lb, rh_ub, s, &ov_lb);
2009 25339739 : wide_int new_ub = wi::sub (lh_ub, rh_lb, s, &ov_ub);
2010 25339739 : value_range_with_overflow (r, type, new_lb, new_ub, ov_lb, ov_ub);
2011 25339739 : }
2012 :
2013 :
2014 : // Return the relation between LHS and OP1 based on the relation between
2015 : // OP1 and OP2.
2016 :
2017 : relation_kind
2018 4699128 : operator_minus::lhs_op1_relation (const irange &, const irange &op1,
2019 : const irange &, relation_kind rel) const
2020 : {
2021 4699128 : if (!op1.undefined_p () && TYPE_SIGN (op1.type ()) == UNSIGNED)
2022 2246486 : switch (rel)
2023 : {
2024 : case VREL_GT:
2025 : case VREL_GE:
2026 : return VREL_LE;
2027 : default:
2028 : break;
2029 : }
2030 : return VREL_VARYING;
2031 : }
2032 :
2033 : // Check to see if the relation REL between OP1 and OP2 has any effect on the
2034 : // LHS of the expression. If so, apply it to LHS_RANGE. This is a helper
2035 : // function for both MINUS_EXPR and POINTER_DIFF_EXPR.
2036 :
2037 : bool
2038 20735498 : minus_op1_op2_relation_effect (irange &lhs_range, tree type,
2039 : const irange &op1_range ATTRIBUTE_UNUSED,
2040 : const irange &op2_range ATTRIBUTE_UNUSED,
2041 : relation_kind rel)
2042 : {
2043 20735498 : if (rel == VREL_VARYING)
2044 : return false;
2045 :
2046 262455 : int_range<2> rel_range;
2047 262455 : unsigned prec = TYPE_PRECISION (type);
2048 262455 : signop sgn = TYPE_SIGN (type);
2049 :
2050 : // == and != produce [0,0] and ~[0,0] regardless of wrapping.
2051 262455 : if (rel == VREL_EQ)
2052 8323 : rel_range = int_range<2> (type, wi::zero (prec), wi::zero (prec));
2053 254132 : else if (rel == VREL_NE)
2054 104070 : rel_range = int_range<2> (type, wi::zero (prec), wi::zero (prec),
2055 52035 : VR_ANTI_RANGE);
2056 202097 : else if (TYPE_OVERFLOW_WRAPS (type))
2057 : {
2058 117588 : switch (rel)
2059 : {
2060 : // For wrapping signed values and unsigned, if op1 > op2 or
2061 : // op1 < op2, then op1 - op2 can be restricted to ~[0, 0].
2062 43138 : case VREL_GT:
2063 43138 : case VREL_LT:
2064 86276 : rel_range = int_range<2> (type, wi::zero (prec), wi::zero (prec),
2065 43138 : VR_ANTI_RANGE);
2066 43138 : break;
2067 : default:
2068 : return false;
2069 : }
2070 : }
2071 : else
2072 : {
2073 84509 : switch (rel)
2074 : {
2075 : // op1 > op2, op1 - op2 can be restricted to [1, +INF]
2076 22128 : case VREL_GT:
2077 44256 : rel_range = int_range<2> (type, wi::one (prec),
2078 44256 : wi::max_value (prec, sgn));
2079 22128 : break;
2080 : // op1 >= op2, op1 - op2 can be restricted to [0, +INF]
2081 61616 : case VREL_GE:
2082 123232 : rel_range = int_range<2> (type, wi::zero (prec),
2083 123232 : wi::max_value (prec, sgn));
2084 61616 : break;
2085 : // op1 < op2, op1 - op2 can be restricted to [-INF, -1]
2086 327 : case VREL_LT:
2087 654 : rel_range = int_range<2> (type, wi::min_value (prec, sgn),
2088 327 : wi::minus_one (prec));
2089 327 : break;
2090 : // op1 <= op2, op1 - op2 can be restricted to [-INF, 0]
2091 284 : case VREL_LE:
2092 568 : rel_range = int_range<2> (type, wi::min_value (prec, sgn),
2093 284 : wi::zero (prec));
2094 284 : break;
2095 : default:
2096 : return false;
2097 : }
2098 : }
2099 187851 : lhs_range.intersect (rel_range);
2100 187851 : return true;
2101 262455 : }
2102 :
2103 : bool
2104 17999499 : operator_minus::op1_op2_relation_effect (irange &lhs_range, tree type,
2105 : const irange &op1_range,
2106 : const irange &op2_range,
2107 : relation_kind rel) const
2108 : {
2109 17999499 : return minus_op1_op2_relation_effect (lhs_range, type, op1_range, op2_range,
2110 17999499 : rel);
2111 : }
2112 :
2113 : bool
2114 1047233 : operator_minus::op1_range (irange &r, tree type,
2115 : const irange &lhs,
2116 : const irange &op2,
2117 : relation_trio trio) const
2118 : {
2119 1047233 : if (lhs.undefined_p ())
2120 : return false;
2121 : // Start with the default operation.
2122 1047233 : range_op_handler minus (PLUS_EXPR);
2123 1047233 : if (!minus)
2124 : return false;
2125 1047233 : bool res = minus.fold_range (r, type, lhs, op2);
2126 1047233 : relation_kind rel = trio.lhs_op1 ();
2127 1047233 : if (res)
2128 1047233 : adjust_op1_for_overflow (r, op2, rel, false /* PLUS_EXPR */);
2129 : return res;
2130 :
2131 : }
2132 :
2133 : bool
2134 1749607 : operator_minus::op2_range (irange &r, tree type,
2135 : const irange &lhs,
2136 : const irange &op1,
2137 : relation_trio) const
2138 : {
2139 1749607 : if (lhs.undefined_p ())
2140 : return false;
2141 1749607 : return fold_range (r, type, op1, lhs);
2142 : }
2143 :
2144 : void
2145 928406 : operator_min::update_bitmask (irange &r, const irange &lh,
2146 : const irange &rh) const
2147 : {
2148 928406 : update_known_bitmask (r, MIN_EXPR, lh, rh);
2149 928406 : }
2150 :
2151 : void
2152 1432700 : operator_min::wi_fold (irange &r, tree type,
2153 : const wide_int &lh_lb, const wide_int &lh_ub,
2154 : const wide_int &rh_lb, const wide_int &rh_ub) const
2155 : {
2156 1432700 : signop s = TYPE_SIGN (type);
2157 1432700 : wide_int new_lb = wi::min (lh_lb, rh_lb, s);
2158 1432700 : wide_int new_ub = wi::min (lh_ub, rh_ub, s);
2159 1432700 : value_range_with_overflow (r, type, new_lb, new_ub);
2160 1432700 : }
2161 :
2162 :
2163 : void
2164 835172 : operator_max::update_bitmask (irange &r, const irange &lh,
2165 : const irange &rh) const
2166 : {
2167 835172 : update_known_bitmask (r, MAX_EXPR, lh, rh);
2168 835172 : }
2169 :
2170 : void
2171 1001988 : operator_max::wi_fold (irange &r, tree type,
2172 : const wide_int &lh_lb, const wide_int &lh_ub,
2173 : const wide_int &rh_lb, const wide_int &rh_ub) const
2174 : {
2175 1001988 : signop s = TYPE_SIGN (type);
2176 1001988 : wide_int new_lb = wi::max (lh_lb, rh_lb, s);
2177 1001988 : wide_int new_ub = wi::max (lh_ub, rh_ub, s);
2178 1001988 : value_range_with_overflow (r, type, new_lb, new_ub);
2179 1001988 : }
2180 :
2181 :
2182 : // Calculate the cross product of two sets of ranges and return it.
2183 : //
2184 : // Multiplications, divisions and shifts are a bit tricky to handle,
2185 : // depending on the mix of signs we have in the two ranges, we need to
2186 : // operate on different values to get the minimum and maximum values
2187 : // for the new range. One approach is to figure out all the
2188 : // variations of range combinations and do the operations.
2189 : //
2190 : // However, this involves several calls to compare_values and it is
2191 : // pretty convoluted. It's simpler to do the 4 operations (MIN0 OP
2192 : // MIN1, MIN0 OP MAX1, MAX0 OP MIN1 and MAX0 OP MAX0 OP MAX1) and then
2193 : // figure the smallest and largest values to form the new range.
2194 :
2195 : void
2196 14198055 : cross_product_operator::wi_cross_product (irange &r, tree type,
2197 : const wide_int &lh_lb,
2198 : const wide_int &lh_ub,
2199 : const wide_int &rh_lb,
2200 : const wide_int &rh_ub) const
2201 : {
2202 14198055 : wide_int cp1, cp2, cp3, cp4;
2203 : // Default to varying.
2204 14198055 : r.set_varying (type);
2205 :
2206 : // Compute the 4 cross operations, bailing if we get an overflow we
2207 : // can't handle.
2208 14198055 : if (wi_op_overflows (cp1, type, lh_lb, rh_lb))
2209 : return;
2210 14198017 : if (wi::eq_p (lh_lb, lh_ub))
2211 3865235 : cp3 = cp1;
2212 10332782 : else if (wi_op_overflows (cp3, type, lh_ub, rh_lb))
2213 : return;
2214 14198017 : if (wi::eq_p (rh_lb, rh_ub))
2215 10849588 : cp2 = cp1;
2216 3348429 : else if (wi_op_overflows (cp2, type, lh_lb, rh_ub))
2217 : return;
2218 14195768 : if (wi::eq_p (lh_lb, lh_ub))
2219 3865217 : cp4 = cp2;
2220 10330551 : else if (wi_op_overflows (cp4, type, lh_ub, rh_ub))
2221 : return;
2222 :
2223 : // Order pairs.
2224 14195768 : signop sign = TYPE_SIGN (type);
2225 14195768 : if (wi::gt_p (cp1, cp2, sign))
2226 1511570 : std::swap (cp1, cp2);
2227 14195768 : if (wi::gt_p (cp3, cp4, sign))
2228 1484228 : std::swap (cp3, cp4);
2229 :
2230 : // Choose min and max from the ordered pairs.
2231 14195768 : wide_int res_lb = wi::min (cp1, cp3, sign);
2232 14195768 : wide_int res_ub = wi::max (cp2, cp4, sign);
2233 14195768 : value_range_with_overflow (r, type, res_lb, res_ub);
2234 14199505 : }
2235 :
2236 :
2237 : void
2238 13564413 : operator_mult::update_bitmask (irange &r, const irange &lh,
2239 : const irange &rh) const
2240 : {
2241 13564413 : update_known_bitmask (r, MULT_EXPR, lh, rh);
2242 13564413 : }
2243 :
2244 : bool
2245 1174145 : operator_mult::op1_range (irange &r, tree type,
2246 : const irange &lhs, const irange &op2,
2247 : relation_trio) const
2248 : {
2249 1174145 : if (lhs.undefined_p ())
2250 : return false;
2251 :
2252 : // We can't solve 0 = OP1 * N by dividing by N with a wrapping type.
2253 : // For example: For 0 = OP1 * 2, OP1 could be 0, or MAXINT, whereas
2254 : // for 4 = OP1 * 2, OP1 could be 2 or 130 (unsigned 8-bit)
2255 1174145 : if (TYPE_OVERFLOW_WRAPS (type))
2256 : return false;
2257 :
2258 328831 : wide_int offset;
2259 328831 : if (op2.singleton_p (offset) && offset != 0)
2260 224397 : return range_op_handler (TRUNC_DIV_EXPR).fold_range (r, type, lhs, op2);
2261 :
2262 : // ~[0, 0] = op1 * op2 defines op1 and op2 as non-zero.
2263 104434 : if (!lhs.contains_p (wi::zero (TYPE_PRECISION (lhs.type ()))))
2264 : {
2265 24395 : r.set_nonzero (type);
2266 24395 : return true;
2267 : }
2268 : return false;
2269 328831 : }
2270 :
2271 : bool
2272 121335 : operator_mult::op2_range (irange &r, tree type,
2273 : const irange &lhs, const irange &op1,
2274 : relation_trio rel) const
2275 : {
2276 121335 : return operator_mult::op1_range (r, type, lhs, op1, rel.swap_op1_op2 ());
2277 : }
2278 :
2279 : bool
2280 14297817 : operator_mult::wi_op_overflows (wide_int &res, tree type,
2281 : const wide_int &w0, const wide_int &w1) const
2282 : {
2283 14297817 : wi::overflow_type overflow = wi::OVF_NONE;
2284 14297817 : signop sign = TYPE_SIGN (type);
2285 14297817 : res = wi::mul (w0, w1, sign, &overflow);
2286 14297817 : if (overflow && TYPE_OVERFLOW_UNDEFINED (type))
2287 : {
2288 : // For multiplication, the sign of the overflow is given
2289 : // by the comparison of the signs of the operands.
2290 6992728 : if (sign == UNSIGNED || w0.sign_mask () == w1.sign_mask ())
2291 3880125 : res = wi::max_value (w0.get_precision (), sign);
2292 : else
2293 3112775 : res = wi::min_value (w0.get_precision (), sign);
2294 6992728 : return false;
2295 : }
2296 7305089 : return overflow;
2297 : }
2298 :
2299 : void
2300 17294765 : operator_mult::wi_fold (irange &r, tree type,
2301 : const wide_int &lh_lb, const wide_int &lh_ub,
2302 : const wide_int &rh_lb, const wide_int &rh_ub) const
2303 : {
2304 17294765 : if (TYPE_OVERFLOW_UNDEFINED (type))
2305 : {
2306 5654077 : wi_cross_product (r, type, lh_lb, lh_ub, rh_lb, rh_ub);
2307 5654077 : return;
2308 : }
2309 :
2310 : // Multiply the ranges when overflow wraps. This is basically fancy
2311 : // code so we don't drop to varying with an unsigned
2312 : // [-3,-1]*[-3,-1].
2313 : //
2314 : // This test requires 2*prec bits if both operands are signed and
2315 : // 2*prec + 2 bits if either is not. Therefore, extend the values
2316 : // using the sign of the result to PREC2. From here on out,
2317 : // everything is just signed math no matter what the input types
2318 : // were.
2319 :
2320 11640688 : signop sign = TYPE_SIGN (type);
2321 11640688 : unsigned prec = TYPE_PRECISION (type);
2322 11640688 : widest2_int min0 = widest2_int::from (lh_lb, sign);
2323 11640688 : widest2_int max0 = widest2_int::from (lh_ub, sign);
2324 11640688 : widest2_int min1 = widest2_int::from (rh_lb, sign);
2325 11640688 : widest2_int max1 = widest2_int::from (rh_ub, sign);
2326 11640688 : widest2_int sizem1 = wi::mask <widest2_int> (prec, false);
2327 11640688 : widest2_int size = sizem1 + 1;
2328 :
2329 : // Canonicalize the intervals.
2330 11640688 : if (sign == UNSIGNED)
2331 : {
2332 11016188 : if (wi::ltu_p (size, min0 + max0))
2333 : {
2334 1585131 : min0 -= size;
2335 1585131 : max0 -= size;
2336 : }
2337 11016156 : if (wi::ltu_p (size, min1 + max1))
2338 : {
2339 166739 : min1 -= size;
2340 166739 : max1 -= size;
2341 : }
2342 : }
2343 :
2344 : // Sort the 4 products so that min is in prod0 and max is in
2345 : // prod3.
2346 11640688 : widest2_int prod0 = min0 * min1;
2347 11640688 : widest2_int prod1 = min0 * max1;
2348 11640688 : widest2_int prod2 = max0 * min1;
2349 11640688 : widest2_int prod3 = max0 * max1;
2350 :
2351 : // min0min1 > max0max1
2352 11640688 : if (prod0 > prod3)
2353 194884 : std::swap (prod0, prod3);
2354 :
2355 : // min0max1 > max0min1
2356 11640688 : if (prod1 > prod2)
2357 317144 : std::swap (prod1, prod2);
2358 :
2359 11640688 : if (prod0 > prod1)
2360 78344 : std::swap (prod0, prod1);
2361 :
2362 11640688 : if (prod2 > prod3)
2363 4044 : std::swap (prod2, prod3);
2364 :
2365 : // diff = max - min
2366 11640688 : prod2 = prod3 - prod0;
2367 11640688 : if (wi::geu_p (prod2, sizem1))
2368 : {
2369 : // Multiplying by X, where X is a power of 2 is [0,0][X,+INF].
2370 7833809 : if (TYPE_UNSIGNED (type) && rh_lb == rh_ub
2371 7234197 : && wi::exact_log2 (rh_lb) != -1 && prec > 1)
2372 : {
2373 2721009 : r.set (type, rh_lb, wi::max_value (prec, sign));
2374 2721009 : int_range<2> zero;
2375 2721009 : zero.set_zero (type);
2376 2721009 : r.union_ (zero);
2377 2721009 : }
2378 : else
2379 : // The range covers all values.
2380 1266686 : r.set_varying (type);
2381 : }
2382 : else
2383 : {
2384 7652993 : wide_int new_lb = wide_int::from (prod0, prec, sign);
2385 7652993 : wide_int new_ub = wide_int::from (prod3, prec, sign);
2386 7652993 : create_possibly_reversed_range (r, type, new_lb, new_ub);
2387 7653036 : }
2388 11641385 : }
2389 :
2390 : bool
2391 13564413 : operator_mult::op1_op2_relation_effect (irange &lhs_range, tree type,
2392 : const irange &,
2393 : const irange &,
2394 : relation_kind rel) const
2395 : {
2396 : // a*a is nonnegative without overflow.
2397 : // tree_binary_nonnegative_p handles this in a similar way.
2398 13564413 : if (rel == VREL_EQ
2399 13564413 : && TYPE_OVERFLOW_UNDEFINED (type))
2400 : {
2401 34566 : int_range<2> nonnegative;
2402 34566 : nonnegative.set_nonnegative (type);
2403 34566 : lhs_range.intersect (nonnegative);
2404 34566 : return true;
2405 34566 : }
2406 : return false;
2407 : }
2408 :
2409 : class operator_widen_mult_signed : public range_operator
2410 : {
2411 : public:
2412 : virtual void wi_fold (irange &r, tree type,
2413 : const wide_int &lh_lb,
2414 : const wide_int &lh_ub,
2415 : const wide_int &rh_lb,
2416 : const wide_int &rh_ub)
2417 : const;
2418 : } op_widen_mult_signed;
2419 :
2420 : void
2421 1347 : operator_widen_mult_signed::wi_fold (irange &r, tree type,
2422 : const wide_int &lh_lb,
2423 : const wide_int &lh_ub,
2424 : const wide_int &rh_lb,
2425 : const wide_int &rh_ub) const
2426 : {
2427 1347 : wide_int lh_wlb = wide_int::from (lh_lb, TYPE_PRECISION (type), SIGNED);
2428 1347 : wide_int lh_wub = wide_int::from (lh_ub, TYPE_PRECISION (type), SIGNED);
2429 1347 : wide_int rh_wlb = wide_int::from (rh_lb, TYPE_PRECISION (type), SIGNED);
2430 1347 : wide_int rh_wub = wide_int::from (rh_ub, TYPE_PRECISION (type), SIGNED);
2431 :
2432 : /* We don't expect a widening multiplication to be able to overflow but range
2433 : calculations for multiplications are complicated. After widening the
2434 : operands lets call the base class. */
2435 1347 : return op_mult.wi_fold (r, type, lh_wlb, lh_wub, rh_wlb, rh_wub);
2436 1347 : }
2437 :
2438 : class operator_widen_mult_unsigned : public range_operator
2439 : {
2440 : public:
2441 : virtual void wi_fold (irange &r, tree type,
2442 : const wide_int &lh_lb,
2443 : const wide_int &lh_ub,
2444 : const wide_int &rh_lb,
2445 : const wide_int &rh_ub)
2446 : const;
2447 : } op_widen_mult_unsigned;
2448 :
2449 : void
2450 5434 : operator_widen_mult_unsigned::wi_fold (irange &r, tree type,
2451 : const wide_int &lh_lb,
2452 : const wide_int &lh_ub,
2453 : const wide_int &rh_lb,
2454 : const wide_int &rh_ub) const
2455 : {
2456 5434 : wide_int lh_wlb = wide_int::from (lh_lb, TYPE_PRECISION (type), UNSIGNED);
2457 5434 : wide_int lh_wub = wide_int::from (lh_ub, TYPE_PRECISION (type), UNSIGNED);
2458 5434 : wide_int rh_wlb = wide_int::from (rh_lb, TYPE_PRECISION (type), UNSIGNED);
2459 5434 : wide_int rh_wub = wide_int::from (rh_ub, TYPE_PRECISION (type), UNSIGNED);
2460 :
2461 : /* We don't expect a widening multiplication to be able to overflow but range
2462 : calculations for multiplications are complicated. After widening the
2463 : operands lets call the base class. */
2464 5434 : return op_mult.wi_fold (r, type, lh_wlb, lh_wub, rh_wlb, rh_wub);
2465 5434 : }
2466 :
2467 : class operator_widen_mult_signed_unsigned : public range_operator
2468 : {
2469 : public:
2470 : virtual void wi_fold (irange &r, tree type,
2471 : const wide_int &lh_lb,
2472 : const wide_int &lh_ub,
2473 : const wide_int &rh_lb,
2474 : const wide_int &rh_ub)
2475 : const;
2476 : } op_widen_mult_signed_unsigned;
2477 :
2478 : void
2479 0 : operator_widen_mult_signed_unsigned::wi_fold (irange &r, tree type,
2480 : const wide_int &lh_lb,
2481 : const wide_int &lh_ub,
2482 : const wide_int &rh_lb,
2483 : const wide_int &rh_ub) const
2484 : {
2485 0 : wide_int lh_wlb = wide_int::from (lh_lb, TYPE_PRECISION (type), SIGNED);
2486 0 : wide_int lh_wub = wide_int::from (lh_ub, TYPE_PRECISION (type), SIGNED);
2487 0 : wide_int rh_wlb = wide_int::from (rh_lb, TYPE_PRECISION (type), UNSIGNED);
2488 0 : wide_int rh_wub = wide_int::from (rh_ub, TYPE_PRECISION (type), UNSIGNED);
2489 :
2490 : /* We don't expect a widening multiplication to be able to overflow but range
2491 : calculations for multiplications are complicated. After widening the
2492 : operands lets call the base class. */
2493 0 : return op_mult.wi_fold (r, type, lh_wlb, lh_wub, rh_wlb, rh_wub);
2494 0 : }
2495 :
2496 : class operator_div : public cross_product_operator
2497 : {
2498 : using range_operator::update_bitmask;
2499 : using range_operator::op2_range;
2500 : public:
2501 : operator_div (tree_code div_kind) { m_code = div_kind; }
2502 : bool op2_range (irange &r, tree type, const irange &lhs, const irange &,
2503 : relation_trio) const final override;
2504 : virtual void wi_fold (irange &r, tree type,
2505 : const wide_int &lh_lb,
2506 : const wide_int &lh_ub,
2507 : const wide_int &rh_lb,
2508 : const wide_int &rh_ub) const final override;
2509 : virtual bool wi_op_overflows (wide_int &res, tree type,
2510 : const wide_int &, const wide_int &)
2511 : const final override;
2512 2964614 : void update_bitmask (irange &r, const irange &lh, const irange &rh)
2513 : const final override
2514 2964614 : { update_known_bitmask (r, m_code, lh, rh); }
2515 : protected:
2516 : tree_code m_code;
2517 : };
2518 :
2519 : static const operator_div op_trunc_div (TRUNC_DIV_EXPR);
2520 : static const operator_div op_floor_div (FLOOR_DIV_EXPR);
2521 : static const operator_div op_round_div (ROUND_DIV_EXPR);
2522 : static const operator_div op_ceil_div (CEIL_DIV_EXPR);
2523 :
2524 : // Set OP2 to non-zero if the LHS isn't UNDEFINED.
2525 : bool
2526 35321 : operator_div::op2_range (irange &r, tree type, const irange &lhs,
2527 : const irange &, relation_trio) const
2528 : {
2529 35321 : if (!lhs.undefined_p ())
2530 : {
2531 35321 : r.set_nonzero (type);
2532 35321 : return true;
2533 : }
2534 : return false;
2535 : }
2536 :
2537 : bool
2538 12746150 : operator_div::wi_op_overflows (wide_int &res, tree type,
2539 : const wide_int &w0, const wide_int &w1) const
2540 : {
2541 12746150 : if (w1 == 0)
2542 : return true;
2543 :
2544 12746150 : wi::overflow_type overflow = wi::OVF_NONE;
2545 12746150 : signop sign = TYPE_SIGN (type);
2546 :
2547 12746150 : switch (m_code)
2548 : {
2549 12606947 : case EXACT_DIV_EXPR:
2550 12606947 : case TRUNC_DIV_EXPR:
2551 12606947 : res = wi::div_trunc (w0, w1, sign, &overflow);
2552 12606947 : break;
2553 128049 : case FLOOR_DIV_EXPR:
2554 128049 : res = wi::div_floor (w0, w1, sign, &overflow);
2555 128049 : break;
2556 288 : case ROUND_DIV_EXPR:
2557 288 : res = wi::div_round (w0, w1, sign, &overflow);
2558 288 : break;
2559 10866 : case CEIL_DIV_EXPR:
2560 10866 : res = wi::div_ceil (w0, w1, sign, &overflow);
2561 10866 : break;
2562 0 : default:
2563 0 : gcc_unreachable ();
2564 : }
2565 :
2566 12746150 : if (overflow && TYPE_OVERFLOW_UNDEFINED (type))
2567 : {
2568 : // For division, the only case is -INF / -1 = +INF.
2569 201713 : res = wi::max_value (w0.get_precision (), sign);
2570 201713 : return false;
2571 : }
2572 12544437 : return overflow;
2573 : }
2574 :
2575 : void
2576 4073901 : operator_div::wi_fold (irange &r, tree type,
2577 : const wide_int &lh_lb, const wide_int &lh_ub,
2578 : const wide_int &rh_lb, const wide_int &rh_ub) const
2579 : {
2580 4073901 : const wide_int dividend_min = lh_lb;
2581 4073901 : const wide_int dividend_max = lh_ub;
2582 4073901 : const wide_int divisor_min = rh_lb;
2583 4073901 : const wide_int divisor_max = rh_ub;
2584 4073901 : signop sign = TYPE_SIGN (type);
2585 4073901 : unsigned prec = TYPE_PRECISION (type);
2586 4073901 : wide_int extra_min, extra_max;
2587 :
2588 : // If we know we won't divide by zero, just do the division.
2589 4073901 : if (!wi_includes_zero_p (type, divisor_min, divisor_max))
2590 : {
2591 3382813 : wi_cross_product (r, type, dividend_min, dividend_max,
2592 : divisor_min, divisor_max);
2593 3382813 : return;
2594 : }
2595 :
2596 : // If we're definitely dividing by zero, there's nothing to do.
2597 691088 : if (wi_zero_p (type, divisor_min, divisor_max))
2598 : {
2599 17755 : r.set_undefined ();
2600 17755 : return;
2601 : }
2602 :
2603 : // Perform the division in 2 parts, [LB, -1] and [1, UB], which will
2604 : // skip any division by zero.
2605 :
2606 : // First divide by the negative numbers, if any.
2607 673333 : if (wi::neg_p (divisor_min, sign))
2608 895810 : wi_cross_product (r, type, dividend_min, dividend_max,
2609 895810 : divisor_min, wi::minus_one (prec));
2610 : else
2611 225428 : r.set_undefined ();
2612 :
2613 : // Then divide by the non-zero positive numbers, if any.
2614 673333 : if (wi::gt_p (divisor_max, wi::zero (prec), sign))
2615 : {
2616 672731 : int_range_max tmp;
2617 1345462 : wi_cross_product (tmp, type, dividend_min, dividend_max,
2618 672731 : wi::one (prec), divisor_max);
2619 672731 : r.union_ (tmp);
2620 672731 : }
2621 : // We shouldn't still have undefined here.
2622 673333 : gcc_checking_assert (!r.undefined_p ());
2623 4074513 : }
2624 :
2625 :
2626 : class operator_exact_divide : public operator_div
2627 : {
2628 : using range_operator::op1_range;
2629 : public:
2630 : operator_exact_divide () : operator_div (EXACT_DIV_EXPR) { }
2631 : virtual bool op1_range (irange &r, tree type,
2632 : const irange &lhs,
2633 : const irange &op2,
2634 : relation_trio) const;
2635 :
2636 : } op_exact_div;
2637 :
2638 : bool
2639 588435 : operator_exact_divide::op1_range (irange &r, tree type,
2640 : const irange &lhs,
2641 : const irange &op2,
2642 : relation_trio) const
2643 : {
2644 588435 : if (lhs.undefined_p ())
2645 : return false;
2646 588435 : wide_int offset;
2647 : // [2, 4] = op1 / [3,3] since its exact divide, no need to worry about
2648 : // remainders in the endpoints, so op1 = [2,4] * [3,3] = [6,12].
2649 : // We wont bother trying to enumerate all the in between stuff :-P
2650 : // TRUE accuracy is [6,6][9,9][12,12]. This is unlikely to matter most of
2651 : // the time however.
2652 : // If op2 is a multiple of 2, we would be able to set some non-zero bits.
2653 588435 : if (op2.singleton_p (offset) && offset != 0)
2654 588435 : return range_op_handler (MULT_EXPR).fold_range (r, type, lhs, op2);
2655 : return false;
2656 588435 : }
2657 :
2658 :
2659 : class operator_lshift : public cross_product_operator
2660 : {
2661 : using range_operator::fold_range;
2662 : using range_operator::op1_range;
2663 : using range_operator::update_bitmask;
2664 : public:
2665 : virtual bool op1_range (irange &r, tree type, const irange &lhs,
2666 : const irange &op2, relation_trio rel = TRIO_VARYING)
2667 : const final override;
2668 : virtual bool fold_range (irange &r, tree type, const irange &op1,
2669 : const irange &op2, relation_trio rel = TRIO_VARYING)
2670 : const final override;
2671 :
2672 : virtual void wi_fold (irange &r, tree type,
2673 : const wide_int &lh_lb, const wide_int &lh_ub,
2674 : const wide_int &rh_lb,
2675 : const wide_int &rh_ub) const final override;
2676 : virtual bool wi_op_overflows (wide_int &res,
2677 : tree type,
2678 : const wide_int &,
2679 : const wide_int &) const final override;
2680 451749 : void update_bitmask (irange &r, const irange &lh,
2681 : const irange &rh) const final override
2682 451749 : { update_known_bitmask (r, LSHIFT_EXPR, lh, rh); }
2683 : // Check compatibility of LHS and op1.
2684 1045339 : bool operand_check_p (tree t1, tree t2, tree) const final override
2685 1045339 : { return range_compatible_p (t1, t2); }
2686 : } op_lshift;
2687 :
2688 : class operator_rshift : public cross_product_operator
2689 : {
2690 : using range_operator::fold_range;
2691 : using range_operator::op1_range;
2692 : using range_operator::lhs_op1_relation;
2693 : using range_operator::update_bitmask;
2694 : public:
2695 : virtual bool fold_range (irange &r, tree type, const irange &op1,
2696 : const irange &op2, relation_trio rel = TRIO_VARYING)
2697 : const final override;
2698 : virtual void wi_fold (irange &r, tree type,
2699 : const wide_int &lh_lb,
2700 : const wide_int &lh_ub,
2701 : const wide_int &rh_lb,
2702 : const wide_int &rh_ub) const final override;
2703 : virtual bool wi_op_overflows (wide_int &res,
2704 : tree type,
2705 : const wide_int &w0,
2706 : const wide_int &w1) const final override;
2707 : virtual bool op1_range (irange &, tree type, const irange &lhs,
2708 : const irange &op2, relation_trio rel = TRIO_VARYING)
2709 : const final override;
2710 : virtual relation_kind lhs_op1_relation (const irange &lhs, const irange &op1,
2711 : const irange &op2, relation_kind rel)
2712 : const final override;
2713 3191463 : void update_bitmask (irange &r, const irange &lh,
2714 : const irange &rh) const final override
2715 3191463 : { update_known_bitmask (r, RSHIFT_EXPR, lh, rh); }
2716 : // Check compatibility of LHS and op1.
2717 3279642 : bool operand_check_p (tree t1, tree t2, tree) const final override
2718 3279642 : { return range_compatible_p (t1, t2); }
2719 : } op_rshift;
2720 :
2721 :
2722 : relation_kind
2723 2320470 : operator_rshift::lhs_op1_relation (const irange &lhs ATTRIBUTE_UNUSED,
2724 : const irange &op1,
2725 : const irange &op2,
2726 : relation_kind) const
2727 : {
2728 : // If both operands range are >= 0, then the LHS <= op1.
2729 2320470 : if (!op1.undefined_p () && !op2.undefined_p ()
2730 4640194 : && wi::ge_p (op1.lower_bound (), 0, TYPE_SIGN (op1.type ()))
2731 6715351 : && wi::ge_p (op2.lower_bound (), 0, TYPE_SIGN (op2.type ())))
2732 2047484 : return VREL_LE;
2733 : return VREL_VARYING;
2734 : }
2735 :
2736 : bool
2737 1579153 : operator_lshift::fold_range (irange &r, tree type,
2738 : const irange &op1,
2739 : const irange &op2,
2740 : relation_trio rel) const
2741 : {
2742 1579153 : int_range_max shift_range;
2743 1579153 : if (!get_shift_range (shift_range, type, op2))
2744 : {
2745 577 : if (op2.undefined_p ())
2746 225 : r.set_undefined ();
2747 : else
2748 352 : r.set_zero (type);
2749 577 : return true;
2750 : }
2751 :
2752 : // Transform left shifts by constants into multiplies.
2753 1578576 : if (shift_range.singleton_p ())
2754 : {
2755 1126800 : unsigned shift = shift_range.lower_bound ().to_uhwi ();
2756 1126800 : wide_int tmp = wi::set_bit_in_zero (shift, TYPE_PRECISION (type));
2757 1126800 : int_range<1> mult (type, tmp, tmp);
2758 :
2759 : // Force wrapping multiplication.
2760 1126800 : bool saved_flag_wrapv = flag_wrapv;
2761 1126800 : bool saved_flag_wrapv_pointer = flag_wrapv_pointer;
2762 1126800 : flag_wrapv = 1;
2763 1126800 : flag_wrapv_pointer = 1;
2764 1126800 : bool b = op_mult.fold_range (r, type, op1, mult);
2765 1126800 : flag_wrapv = saved_flag_wrapv;
2766 1126800 : flag_wrapv_pointer = saved_flag_wrapv_pointer;
2767 1126800 : return b;
2768 1126809 : }
2769 : else
2770 : // Otherwise, invoke the generic fold routine.
2771 451776 : return range_operator::fold_range (r, type, op1, shift_range, rel);
2772 1579153 : }
2773 :
2774 : void
2775 534291 : operator_lshift::wi_fold (irange &r, tree type,
2776 : const wide_int &lh_lb, const wide_int &lh_ub,
2777 : const wide_int &rh_lb, const wide_int &rh_ub) const
2778 : {
2779 534291 : signop sign = TYPE_SIGN (type);
2780 534291 : unsigned prec = TYPE_PRECISION (type);
2781 534291 : int overflow_pos = sign == SIGNED ? prec - 1 : prec;
2782 534291 : int bound_shift = overflow_pos - rh_ub.to_shwi ();
2783 : // If bound_shift == HOST_BITS_PER_WIDE_INT, the llshift can
2784 : // overflow. However, for that to happen, rh.max needs to be zero,
2785 : // which means rh is a singleton range of zero, which means we simply return
2786 : // [lh_lb, lh_ub] as the range.
2787 534291 : if (wi::eq_p (rh_ub, rh_lb) && wi::eq_p (rh_ub, 0))
2788 : {
2789 22340 : r = int_range<2> (type, lh_lb, lh_ub);
2790 22340 : return;
2791 : }
2792 :
2793 511951 : wide_int bound = wi::set_bit_in_zero (bound_shift, prec);
2794 511951 : wide_int complement = ~(bound - 1);
2795 511951 : wide_int low_bound, high_bound;
2796 511951 : bool in_bounds = false;
2797 :
2798 511951 : if (sign == UNSIGNED)
2799 : {
2800 256605 : low_bound = bound;
2801 256605 : high_bound = complement;
2802 256605 : if (wi::ltu_p (lh_ub, low_bound))
2803 : {
2804 : // [5, 6] << [1, 2] == [10, 24].
2805 : // We're shifting out only zeroes, the value increases
2806 : // monotonically.
2807 : in_bounds = true;
2808 : }
2809 82412 : else if (wi::ltu_p (high_bound, lh_lb))
2810 : {
2811 : // [0xffffff00, 0xffffffff] << [1, 2]
2812 : // == [0xfffffc00, 0xfffffffe].
2813 : // We're shifting out only ones, the value decreases
2814 : // monotonically.
2815 : in_bounds = true;
2816 : }
2817 : }
2818 : else
2819 : {
2820 : // [-1, 1] << [1, 2] == [-4, 4]
2821 255346 : low_bound = complement;
2822 255346 : high_bound = bound;
2823 255346 : if (wi::lts_p (lh_ub, high_bound)
2824 255346 : && wi::lts_p (low_bound, lh_lb))
2825 : {
2826 : // For non-negative numbers, we're shifting out only zeroes,
2827 : // the value increases monotonically. For negative numbers,
2828 : // we're shifting out only ones, the value decreases
2829 : // monotonically.
2830 : in_bounds = true;
2831 : }
2832 : }
2833 :
2834 : if (in_bounds)
2835 291285 : wi_cross_product (r, type, lh_lb, lh_ub, rh_lb, rh_ub);
2836 : else
2837 220666 : r.set_varying (type);
2838 511969 : }
2839 :
2840 : bool
2841 563261 : operator_lshift::wi_op_overflows (wide_int &res, tree type,
2842 : const wide_int &w0, const wide_int &w1) const
2843 : {
2844 563261 : signop sign = TYPE_SIGN (type);
2845 563261 : if (wi::neg_p (w1))
2846 : {
2847 : // It's unclear from the C standard whether shifts can overflow.
2848 : // The following code ignores overflow; perhaps a C standard
2849 : // interpretation ruling is needed.
2850 0 : res = wi::rshift (w0, -w1, sign);
2851 : }
2852 : else
2853 563261 : res = wi::lshift (w0, w1);
2854 563261 : return false;
2855 : }
2856 :
2857 : bool
2858 45433 : operator_lshift::op1_range (irange &r,
2859 : tree type,
2860 : const irange &lhs,
2861 : const irange &op2,
2862 : relation_trio) const
2863 : {
2864 45433 : if (lhs.undefined_p ())
2865 : return false;
2866 :
2867 45433 : if (!contains_zero_p (lhs))
2868 18560 : r.set_nonzero (type);
2869 : else
2870 26873 : r.set_varying (type);
2871 :
2872 45433 : wide_int shift;
2873 45433 : if (op2.singleton_p (shift))
2874 : {
2875 39929 : if (wi::lt_p (shift, 0, SIGNED))
2876 : return false;
2877 39929 : if (wi::ge_p (shift, wi::uhwi (TYPE_PRECISION (type),
2878 39929 : TYPE_PRECISION (op2.type ())),
2879 : UNSIGNED))
2880 : return false;
2881 39929 : if (shift == 0)
2882 : {
2883 6 : r.intersect (lhs);
2884 6 : return true;
2885 : }
2886 :
2887 : // Work completely in unsigned mode to start.
2888 39923 : tree utype = type;
2889 39923 : int_range_max tmp_range;
2890 39923 : if (TYPE_SIGN (type) == SIGNED)
2891 : {
2892 7709 : int_range_max tmp = lhs;
2893 7709 : utype = unsigned_type_for (type);
2894 7709 : range_cast (tmp, utype);
2895 7709 : op_rshift.fold_range (tmp_range, utype, tmp, op2);
2896 7709 : }
2897 : else
2898 32214 : op_rshift.fold_range (tmp_range, utype, lhs, op2);
2899 :
2900 : // Start with ranges which can produce the LHS by right shifting the
2901 : // result by the shift amount.
2902 : // ie [0x08, 0xF0] = op1 << 2 will start with
2903 : // [00001000, 11110000] = op1 << 2
2904 : // [0x02, 0x4C] aka [00000010, 00111100]
2905 :
2906 : // Then create a range from the LB with the least significant upper bit
2907 : // set, to the upper bound with all the bits set.
2908 : // This would be [0x42, 0xFC] aka [01000010, 11111100].
2909 :
2910 : // Ideally we do this for each subrange, but just lump them all for now.
2911 39923 : unsigned low_bits = TYPE_PRECISION (utype) - shift.to_uhwi ();
2912 39923 : wide_int up_mask = wi::mask (low_bits, true, TYPE_PRECISION (utype));
2913 39923 : wide_int new_ub = wi::bit_or (up_mask, tmp_range.upper_bound ());
2914 39923 : wide_int new_lb = wi::set_bit (tmp_range.lower_bound (), low_bits);
2915 39923 : int_range<2> fill_range (utype, new_lb, new_ub);
2916 39923 : tmp_range.union_ (fill_range);
2917 :
2918 39923 : if (utype != type)
2919 7709 : range_cast (tmp_range, type);
2920 :
2921 39923 : r.intersect (tmp_range);
2922 39923 : return true;
2923 39923 : }
2924 :
2925 5504 : return !r.varying_p ();
2926 45433 : }
2927 :
2928 : bool
2929 794336 : operator_rshift::op1_range (irange &r,
2930 : tree type,
2931 : const irange &lhs,
2932 : const irange &op2,
2933 : relation_trio) const
2934 : {
2935 794336 : if (lhs.undefined_p ())
2936 : return false;
2937 794336 : wide_int shift;
2938 794336 : if (op2.singleton_p (shift))
2939 : {
2940 : // Ignore nonsensical shifts.
2941 771590 : unsigned prec = TYPE_PRECISION (type);
2942 1543180 : if (wi::ge_p (shift,
2943 771590 : wi::uhwi (prec, TYPE_PRECISION (op2.type ())),
2944 : UNSIGNED))
2945 : return false;
2946 771590 : if (shift == 0)
2947 : {
2948 75 : r = lhs;
2949 75 : return true;
2950 : }
2951 :
2952 : // Folding the original operation may discard some impossible
2953 : // ranges from the LHS.
2954 771515 : int_range_max lhs_refined;
2955 771515 : op_rshift.fold_range (lhs_refined, type, int_range<1> (type), op2);
2956 771515 : lhs_refined.intersect (lhs);
2957 771515 : if (lhs_refined.undefined_p ())
2958 : {
2959 4 : r.set_undefined ();
2960 4 : return true;
2961 : }
2962 771511 : int_range_max shift_range (op2.type (), shift, shift);
2963 771511 : int_range_max lb, ub;
2964 771511 : op_lshift.fold_range (lb, type, lhs_refined, shift_range);
2965 : // LHS
2966 : // 0000 0111 = OP1 >> 3
2967 : //
2968 : // OP1 is anything from 0011 1000 to 0011 1111. That is, a
2969 : // range from LHS<<3 plus a mask of the 3 bits we shifted on the
2970 : // right hand side (0x07).
2971 771511 : wide_int mask = wi::mask (shift.to_uhwi (), false, prec);
2972 771511 : int_range_max mask_range (type,
2973 771511 : wi::zero (TYPE_PRECISION (type)),
2974 771511 : mask);
2975 771511 : op_plus.fold_range (ub, type, lb, mask_range);
2976 771511 : r = lb;
2977 771511 : r.union_ (ub);
2978 771511 : if (!contains_zero_p (lhs_refined))
2979 : {
2980 448541 : mask_range.invert ();
2981 448541 : r.intersect (mask_range);
2982 : }
2983 771511 : return true;
2984 771515 : }
2985 : return false;
2986 794336 : }
2987 :
2988 : bool
2989 10602589 : operator_rshift::wi_op_overflows (wide_int &res,
2990 : tree type,
2991 : const wide_int &w0,
2992 : const wide_int &w1) const
2993 : {
2994 10602589 : signop sign = TYPE_SIGN (type);
2995 10602589 : if (wi::neg_p (w1))
2996 0 : res = wi::lshift (w0, -w1);
2997 : else
2998 : {
2999 : // It's unclear from the C standard whether shifts can overflow.
3000 : // The following code ignores overflow; perhaps a C standard
3001 : // interpretation ruling is needed.
3002 10602680 : res = wi::rshift (w0, w1, sign);
3003 : }
3004 10602589 : return false;
3005 : }
3006 :
3007 : bool
3008 3192639 : operator_rshift::fold_range (irange &r, tree type,
3009 : const irange &op1,
3010 : const irange &op2,
3011 : relation_trio rel) const
3012 : {
3013 3192639 : int_range_max shift;
3014 3192639 : if (!get_shift_range (shift, type, op2))
3015 : {
3016 604 : if (op2.undefined_p ())
3017 198 : r.set_undefined ();
3018 : else
3019 406 : r.set_zero (type);
3020 604 : return true;
3021 : }
3022 :
3023 3192035 : return range_operator::fold_range (r, type, op1, shift, rel);
3024 3192639 : }
3025 :
3026 : void
3027 3749244 : operator_rshift::wi_fold (irange &r, tree type,
3028 : const wide_int &lh_lb, const wide_int &lh_ub,
3029 : const wide_int &rh_lb, const wide_int &rh_ub) const
3030 : {
3031 3749244 : wi_cross_product (r, type, lh_lb, lh_ub, rh_lb, rh_ub);
3032 3749244 : }
3033 :
3034 :
3035 : // Add a partial equivalence between the LHS and op1 for casts.
3036 :
3037 : relation_kind
3038 23425820 : operator_cast::lhs_op1_relation (const irange &lhs,
3039 : const irange &op1,
3040 : const irange &op2 ATTRIBUTE_UNUSED,
3041 : relation_kind) const
3042 : {
3043 23425820 : if (lhs.undefined_p () || op1.undefined_p ())
3044 : return VREL_VARYING;
3045 23404785 : unsigned lhs_prec = TYPE_PRECISION (lhs.type ());
3046 23404785 : unsigned op1_prec = TYPE_PRECISION (op1.type ());
3047 : // If the result gets sign extended into a larger type check first if this
3048 : // qualifies as a partial equivalence.
3049 23404785 : if (TYPE_SIGN (op1.type ()) == SIGNED && lhs_prec > op1_prec)
3050 : {
3051 : // If the result is sign extended, and the LHS is larger than op1,
3052 : // check if op1's range can be negative as the sign extension will
3053 : // cause the upper bits to be 1 instead of 0, invalidating the PE.
3054 3803794 : int_range<3> negs = range_negatives (op1.type ());
3055 3803794 : negs.intersect (op1);
3056 3803794 : if (!negs.undefined_p ())
3057 2638750 : return VREL_VARYING;
3058 3803794 : }
3059 :
3060 20766035 : unsigned prec = MIN (lhs_prec, op1_prec);
3061 20766035 : return bits_to_pe (prec);
3062 : }
3063 :
3064 : // Return TRUE if casting from INNER to OUTER is a truncating cast.
3065 :
3066 : inline bool
3067 84908821 : operator_cast::truncating_cast_p (const irange &inner,
3068 : const irange &outer) const
3069 : {
3070 84908821 : return TYPE_PRECISION (outer.type ()) < TYPE_PRECISION (inner.type ());
3071 : }
3072 :
3073 : // Return TRUE if [MIN,MAX] is inside the domain of RANGE's type.
3074 :
3075 : bool
3076 72950371 : operator_cast::inside_domain_p (const wide_int &min,
3077 : const wide_int &max,
3078 : const irange &range) const
3079 : {
3080 72950371 : wide_int domain_min = irange_val_min (range.type ());
3081 72950371 : wide_int domain_max = irange_val_max (range.type ());
3082 72950371 : signop domain_sign = TYPE_SIGN (range.type ());
3083 72950371 : return (wi::le_p (min, domain_max, domain_sign)
3084 72950371 : && wi::le_p (max, domain_max, domain_sign)
3085 72950371 : && wi::ge_p (min, domain_min, domain_sign)
3086 145900742 : && wi::ge_p (max, domain_min, domain_sign));
3087 72950371 : }
3088 :
3089 :
3090 : // Helper for fold_range which work on a pair at a time.
3091 :
3092 : void
3093 76168416 : operator_cast::fold_pair (irange &r, unsigned index,
3094 : const irange &inner,
3095 : const irange &outer) const
3096 : {
3097 76168416 : tree inner_type = inner.type ();
3098 76168416 : tree outer_type = outer.type ();
3099 76168416 : signop inner_sign = TYPE_SIGN (inner_type);
3100 76168416 : unsigned outer_prec = TYPE_PRECISION (outer_type);
3101 :
3102 : // check to see if casting from INNER to OUTER is a conversion that
3103 : // fits in the resulting OUTER type.
3104 76168416 : wide_int inner_lb = inner.lower_bound (index);
3105 76168416 : wide_int inner_ub = inner.upper_bound (index);
3106 76168416 : if (truncating_cast_p (inner, outer))
3107 : {
3108 : // We may be able to accommodate a truncating cast if the
3109 : // resulting range can be represented in the target type...
3110 15562276 : if (wi::rshift (wi::sub (inner_ub, inner_lb),
3111 7781138 : wi::uhwi (outer_prec, TYPE_PRECISION (inner.type ())),
3112 23343414 : inner_sign) != 0)
3113 : {
3114 3218045 : r.set_varying (outer_type);
3115 3218045 : return;
3116 : }
3117 : }
3118 : // ...but we must still verify that the final range fits in the
3119 : // domain. This catches -fstrict-enum restrictions where the domain
3120 : // range is smaller than what fits in the underlying type.
3121 72950371 : wide_int min = wide_int::from (inner_lb, outer_prec, inner_sign);
3122 72950371 : wide_int max = wide_int::from (inner_ub, outer_prec, inner_sign);
3123 72950371 : if (inside_domain_p (min, max, outer))
3124 72950371 : create_possibly_reversed_range (r, outer_type, min, max);
3125 : else
3126 0 : r.set_varying (outer_type);
3127 76171374 : }
3128 :
3129 :
3130 : bool
3131 61790407 : operator_cast::fold_range (irange &r, tree type ATTRIBUTE_UNUSED,
3132 : const irange &inner,
3133 : const irange &outer,
3134 : relation_trio) const
3135 : {
3136 61790407 : if (empty_range_varying (r, type, inner, outer))
3137 32813 : return true;
3138 :
3139 61757594 : gcc_checking_assert (outer.varying_p ());
3140 61757594 : gcc_checking_assert (inner.num_pairs () > 0);
3141 :
3142 : // Avoid a temporary by folding the first pair directly into the result.
3143 61757594 : fold_pair (r, 0, inner, outer);
3144 :
3145 : // Then process any additional pairs by unioning with their results.
3146 75503480 : for (unsigned x = 1; x < inner.num_pairs (); ++x)
3147 : {
3148 14410822 : int_range_max tmp;
3149 14410822 : fold_pair (tmp, x, inner, outer);
3150 14410822 : r.union_ (tmp);
3151 : // If we hit varying, go update the bitmask.
3152 14410822 : if (r.varying_p ())
3153 : break;
3154 14410822 : }
3155 :
3156 61757594 : update_bitmask (r, inner, outer);
3157 61757594 : return true;
3158 : }
3159 :
3160 : void
3161 61757594 : operator_cast::update_bitmask (irange &r, const irange &lh,
3162 : const irange &rh) const
3163 : {
3164 61757594 : update_known_bitmask (r, CONVERT_EXPR, lh, rh);
3165 61757594 : }
3166 :
3167 : bool
3168 8740405 : operator_cast::op1_range (irange &r, tree type,
3169 : const irange &lhs,
3170 : const irange &op2,
3171 : relation_trio) const
3172 : {
3173 8740405 : if (lhs.undefined_p ())
3174 : return false;
3175 8740405 : tree lhs_type = lhs.type ();
3176 8740405 : gcc_checking_assert (types_compatible_p (op2.type(), type));
3177 :
3178 : // If we are calculating a pointer, shortcut to what we really care about.
3179 8740405 : if (POINTER_TYPE_P (type))
3180 : {
3181 : // Conversion from other pointers or a constant (including 0/NULL)
3182 : // are straightforward.
3183 0 : if (POINTER_TYPE_P (lhs.type ())
3184 0 : || (lhs.singleton_p ()
3185 0 : && TYPE_PRECISION (lhs.type ()) >= TYPE_PRECISION (type)))
3186 : {
3187 0 : r = lhs;
3188 0 : range_cast (r, type);
3189 : }
3190 : else
3191 : {
3192 : // If the LHS is not a pointer nor a singleton, then it is
3193 : // either VARYING or non-zero.
3194 0 : if (!lhs.undefined_p () && !contains_zero_p (lhs))
3195 0 : r.set_nonzero (type);
3196 : else
3197 0 : r.set_varying (type);
3198 : }
3199 0 : r.intersect (op2);
3200 0 : return true;
3201 : }
3202 :
3203 8740405 : if (truncating_cast_p (op2, lhs))
3204 : {
3205 1309817 : if (lhs.varying_p ())
3206 139131 : r.set_varying (type);
3207 : else
3208 : {
3209 : // We want to insert the LHS as an unsigned value since it
3210 : // would not trigger the signed bit of the larger type.
3211 1170686 : int_range_max converted_lhs = lhs;
3212 1170686 : range_cast (converted_lhs, unsigned_type_for (lhs_type));
3213 1170686 : range_cast (converted_lhs, type);
3214 : // Start by building the positive signed outer range for the type.
3215 1170686 : wide_int lim = wi::set_bit_in_zero (TYPE_PRECISION (lhs_type),
3216 2341372 : TYPE_PRECISION (type));
3217 1170686 : create_possibly_reversed_range (r, type, lim,
3218 1170686 : wi::max_value (TYPE_PRECISION (type),
3219 : SIGNED));
3220 : // For the signed part, we need to simply union the 2 ranges now.
3221 1170686 : r.union_ (converted_lhs);
3222 :
3223 : // Create maximal negative number outside of LHS bits.
3224 1170686 : lim = wi::mask (TYPE_PRECISION (lhs_type), true,
3225 2341372 : TYPE_PRECISION (type));
3226 : // Add this to the unsigned LHS range(s).
3227 1170686 : int_range_max lim_range (type, lim, lim);
3228 1170686 : int_range_max lhs_neg;
3229 1170686 : range_op_handler (PLUS_EXPR).fold_range (lhs_neg, type,
3230 : converted_lhs, lim_range);
3231 : // lhs_neg now has all the negative versions of the LHS.
3232 : // Now union in all the values from SIGNED MIN (0x80000) to
3233 : // lim-1 in order to fill in all the ranges with the upper
3234 : // bits set.
3235 :
3236 : // PR 97317. If the lhs has only 1 bit less precision than the rhs,
3237 : // we don't need to create a range from min to lim-1
3238 : // calculate neg range traps trying to create [lim, lim - 1].
3239 1170686 : wide_int min_val = wi::min_value (TYPE_PRECISION (type), SIGNED);
3240 1170686 : if (lim != min_val)
3241 : {
3242 1169190 : int_range_max neg (type,
3243 2338380 : wi::min_value (TYPE_PRECISION (type),
3244 : SIGNED),
3245 2338380 : lim - 1);
3246 1169190 : lhs_neg.union_ (neg);
3247 1169190 : }
3248 : // And finally, munge the signed and unsigned portions.
3249 1170686 : r.union_ (lhs_neg);
3250 1170686 : }
3251 : // And intersect with any known value passed in the extra operand.
3252 1309817 : r.intersect (op2);
3253 1309817 : if (r.undefined_p ())
3254 : return true;
3255 :
3256 : // Now create a bitmask indicating that the lower bit must match the
3257 : // bits in the LHS. Zero-extend LHS bitmask to precision of op1.
3258 1309759 : irange_bitmask bm = lhs.get_bitmask ();
3259 2619518 : wide_int mask = wide_int::from (bm.mask (), TYPE_PRECISION (type),
3260 2619518 : UNSIGNED);
3261 2619518 : wide_int value = wide_int::from (bm.value (), TYPE_PRECISION (type),
3262 2619518 : UNSIGNED);
3263 :
3264 : // Set then additional unknown bits in mask.
3265 1309759 : wide_int lim = wi::mask (TYPE_PRECISION (lhs_type), true,
3266 2619518 : TYPE_PRECISION (type));
3267 1309759 : mask = mask | lim;
3268 :
3269 : // Now set the new bitmask for the range.
3270 1309759 : irange_bitmask new_bm (value, mask);
3271 1309759 : r.update_bitmask (new_bm);
3272 1309759 : return true;
3273 1309759 : }
3274 :
3275 7430588 : int_range_max tmp;
3276 7430588 : if (TYPE_PRECISION (lhs_type) == TYPE_PRECISION (type))
3277 5172513 : tmp = lhs;
3278 : else
3279 : {
3280 : // The cast is not truncating, and the range is restricted to
3281 : // the range of the RHS by this assignment.
3282 : //
3283 : // Cast the range of the RHS to the type of the LHS.
3284 2258075 : fold_range (tmp, lhs_type, int_range<1> (type), int_range<1> (lhs_type));
3285 : // Intersect this with the LHS range will produce the range,
3286 : // which will be cast to the RHS type before returning.
3287 2258075 : tmp.intersect (lhs);
3288 : }
3289 :
3290 : // Cast the calculated range to the type of the RHS.
3291 7430588 : fold_range (r, type, tmp, int_range<1> (type));
3292 7430588 : return true;
3293 7430588 : }
3294 :
3295 : // VIEW_CONVERT_EXPR works like a cast between integral values.
3296 : // If the number of bits are not the same, behaviour is undefined,
3297 : // so cast behaviour still works.
3298 :
3299 : bool
3300 282265 : operator_view::fold_range (irange &r, tree type,
3301 : const irange &op1, const irange &op2,
3302 : relation_trio rel) const
3303 : {
3304 282265 : return m_cast.fold_range (r, type, op1, op2, rel);
3305 : }
3306 :
3307 : bool
3308 0 : operator_view::fold_range (prange &r, tree type,
3309 : const prange &op1, const prange &op2,
3310 : relation_trio rel) const
3311 : {
3312 0 : return m_cast.fold_range (r, type, op1, op2, rel);
3313 : }
3314 : bool
3315 259205 : operator_view::fold_range (irange &r, tree type,
3316 : const prange &op1, const irange &op2,
3317 : relation_trio rel) const
3318 : {
3319 259205 : return m_cast.fold_range (r, type, op1, op2, rel);
3320 : }
3321 :
3322 : bool
3323 0 : operator_view::fold_range (prange &r, tree type,
3324 : const irange &op1, const prange &op2,
3325 : relation_trio rel) const
3326 : {
3327 0 : return m_cast.fold_range (r, type, op1, op2, rel);
3328 : }
3329 :
3330 : bool
3331 8844 : operator_view::op1_range (irange &r, tree type,
3332 : const irange &lhs, const irange &op2,
3333 : relation_trio rel) const
3334 : {
3335 8844 : return m_cast.op1_range (r, type, lhs, op2, rel);
3336 : }
3337 :
3338 : bool
3339 0 : operator_view::op1_range (prange &r, tree type,
3340 : const prange &lhs, const prange &op2,
3341 : relation_trio rel) const
3342 : {
3343 0 : return m_cast.op1_range (r, type, lhs, op2, rel);
3344 : }
3345 :
3346 : bool
3347 0 : operator_view::op1_range (irange &r, tree type,
3348 : const prange &lhs, const irange &op2,
3349 : relation_trio rel) const
3350 : {
3351 0 : return m_cast.op1_range (r, type, lhs, op2, rel);
3352 : }
3353 :
3354 : bool
3355 0 : operator_view::op1_range (prange &r, tree type,
3356 : const irange &lhs, const prange &op2,
3357 : relation_trio rel) const
3358 : {
3359 0 : return m_cast.op1_range (r, type, lhs, op2, rel);
3360 : }
3361 :
3362 : void
3363 0 : operator_view::update_bitmask (irange &r, const irange &lh,
3364 : const irange &rh) const
3365 : {
3366 0 : m_cast.update_bitmask (r, lh, rh);
3367 0 : }
3368 :
3369 :
3370 : class operator_logical_and : public range_operator
3371 : {
3372 : using range_operator::fold_range;
3373 : using range_operator::op1_range;
3374 : using range_operator::op2_range;
3375 : public:
3376 : bool fold_range (irange &r, tree type,
3377 : const irange &lh,
3378 : const irange &rh,
3379 : relation_trio rel = TRIO_VARYING) const final override;
3380 : bool op1_range (irange &r, tree type,
3381 : const irange &lhs,
3382 : const irange &op2,
3383 : relation_trio rel = TRIO_VARYING) const final override;
3384 : bool op2_range (irange &r, tree type,
3385 : const irange &lhs,
3386 : const irange &op1,
3387 : relation_trio rel = TRIO_VARYING) const final override;
3388 : // Check compatibility of all operands.
3389 0 : bool operand_check_p (tree t1, tree t2, tree t3) const final override
3390 0 : { return range_compatible_p (t1, t2) && range_compatible_p (t1, t3); }
3391 : } op_logical_and;
3392 :
3393 : bool
3394 0 : operator_logical_and::fold_range (irange &r, tree type,
3395 : const irange &lh,
3396 : const irange &rh,
3397 : relation_trio) const
3398 : {
3399 0 : if (empty_range_varying (r, type, lh, rh))
3400 0 : return true;
3401 :
3402 : // Precision of LHS and both operands must match.
3403 0 : if (TYPE_PRECISION (lh.type ()) != TYPE_PRECISION (type)
3404 0 : || TYPE_PRECISION (type) != TYPE_PRECISION (rh.type ()))
3405 0 : return false;
3406 :
3407 : // 0 && anything is 0.
3408 0 : if ((wi::eq_p (lh.lower_bound (), 0) && wi::eq_p (lh.upper_bound (), 0))
3409 0 : || (wi::eq_p (lh.lower_bound (), 0) && wi::eq_p (rh.upper_bound (), 0)))
3410 0 : r = range_false (type);
3411 0 : else if (contains_zero_p (lh) || contains_zero_p (rh))
3412 : // To reach this point, there must be a logical 1 on each side, and
3413 : // the only remaining question is whether there is a zero or not.
3414 0 : r = range_true_and_false (type);
3415 : else
3416 0 : r = range_true (type);
3417 : return true;
3418 : }
3419 :
3420 : bool
3421 814052 : operator_logical_and::op1_range (irange &r, tree type,
3422 : const irange &lhs,
3423 : const irange &op2 ATTRIBUTE_UNUSED,
3424 : relation_trio) const
3425 : {
3426 814052 : switch (get_bool_state (r, lhs, type))
3427 : {
3428 418568 : case BRS_TRUE:
3429 : // A true result means both sides of the AND must be true.
3430 418568 : r = range_true (type);
3431 418568 : break;
3432 395484 : default:
3433 : // Any other result means only one side has to be false, the
3434 : // other side can be anything. So we cannot be sure of any
3435 : // result here.
3436 395484 : r = range_true_and_false (type);
3437 395484 : break;
3438 : }
3439 814052 : return true;
3440 : }
3441 :
3442 : bool
3443 0 : operator_logical_and::op2_range (irange &r, tree type,
3444 : const irange &lhs,
3445 : const irange &op1,
3446 : relation_trio) const
3447 : {
3448 0 : return operator_logical_and::op1_range (r, type, lhs, op1);
3449 : }
3450 :
3451 :
3452 : void
3453 7308854 : operator_bitwise_and::update_bitmask (irange &r, const irange &lh,
3454 : const irange &rh) const
3455 : {
3456 7308854 : update_known_bitmask (r, BIT_AND_EXPR, lh, rh);
3457 7308854 : }
3458 :
3459 : // Optimize BIT_AND_EXPR, BIT_IOR_EXPR and BIT_XOR_EXPR of signed types
3460 : // by considering the number of leading redundant sign bit copies.
3461 : // clrsb (X op Y) = min (clrsb (X), clrsb (Y)), so for example
3462 : // [-1, 0] op [-1, 0] is [-1, 0] (where nonzero_bits doesn't help).
3463 : static bool
3464 183792 : wi_optimize_signed_bitwise_op (irange &r, tree type,
3465 : const wide_int &lh_lb, const wide_int &lh_ub,
3466 : const wide_int &rh_lb, const wide_int &rh_ub)
3467 : {
3468 367584 : int lh_clrsb = MIN (wi::clrsb (lh_lb), wi::clrsb (lh_ub));
3469 367584 : int rh_clrsb = MIN (wi::clrsb (rh_lb), wi::clrsb (rh_ub));
3470 183792 : int new_clrsb = MIN (lh_clrsb, rh_clrsb);
3471 183792 : if (new_clrsb == 0)
3472 : return false;
3473 12875 : int type_prec = TYPE_PRECISION (type);
3474 12875 : int rprec = (type_prec - new_clrsb) - 1;
3475 12875 : value_range_with_overflow (r, type,
3476 25750 : wi::mask (rprec, true, type_prec),
3477 12875 : wi::mask (rprec, false, type_prec));
3478 12875 : return true;
3479 : }
3480 :
3481 : // An AND of 8,16, 32 or 64 bits can produce a partial equivalence between
3482 : // the LHS and op1.
3483 :
3484 : relation_kind
3485 6619815 : operator_bitwise_and::lhs_op1_relation (const irange &lhs,
3486 : const irange &op1,
3487 : const irange &op2,
3488 : relation_kind) const
3489 : {
3490 6619815 : if (lhs.undefined_p () || op1.undefined_p () || op2.undefined_p ())
3491 : return VREL_VARYING;
3492 6615074 : if (!op2.singleton_p ())
3493 : return VREL_VARYING;
3494 : // if val == 0xff or 0xFFFF OR 0Xffffffff OR 0Xffffffffffffffff, return TRUE
3495 3686760 : int prec1 = TYPE_PRECISION (op1.type ());
3496 3686760 : int prec2 = TYPE_PRECISION (op2.type ());
3497 3686760 : int mask_prec = 0;
3498 3686760 : wide_int mask = op2.lower_bound ();
3499 3686760 : if (wi::eq_p (mask, wi::mask (8, false, prec2)))
3500 : mask_prec = 8;
3501 3602650 : else if (wi::eq_p (mask, wi::mask (16, false, prec2)))
3502 : mask_prec = 16;
3503 3586657 : else if (wi::eq_p (mask, wi::mask (32, false, prec2)))
3504 : mask_prec = 32;
3505 3403610 : else if (wi::eq_p (mask, wi::mask (64, false, prec2)))
3506 805 : mask_prec = 64;
3507 3686760 : return bits_to_pe (MIN (prec1, mask_prec));
3508 3686760 : }
3509 :
3510 : // Optimize BIT_AND_EXPR and BIT_IOR_EXPR in terms of a mask if
3511 : // possible. Basically, see if we can optimize:
3512 : //
3513 : // [LB, UB] op Z
3514 : // into:
3515 : // [LB op Z, UB op Z]
3516 : //
3517 : // If the optimization was successful, accumulate the range in R and
3518 : // return TRUE.
3519 :
3520 : static bool
3521 22775280 : wi_optimize_and_or (irange &r,
3522 : enum tree_code code,
3523 : tree type,
3524 : const wide_int &lh_lb, const wide_int &lh_ub,
3525 : const wide_int &rh_lb, const wide_int &rh_ub)
3526 : {
3527 : // Calculate the singleton mask among the ranges, if any.
3528 22775280 : wide_int lower_bound, upper_bound, mask;
3529 22775280 : if (wi::eq_p (rh_lb, rh_ub))
3530 : {
3531 21164016 : mask = rh_lb;
3532 21164016 : lower_bound = lh_lb;
3533 21164016 : upper_bound = lh_ub;
3534 : }
3535 1611264 : else if (wi::eq_p (lh_lb, lh_ub))
3536 : {
3537 333583 : mask = lh_lb;
3538 333583 : lower_bound = rh_lb;
3539 333583 : upper_bound = rh_ub;
3540 : }
3541 : else
3542 : return false;
3543 :
3544 : // If Z is a constant which (for op | its bitwise not) has n
3545 : // consecutive least significant bits cleared followed by m 1
3546 : // consecutive bits set immediately above it and either
3547 : // m + n == precision, or (x >> (m + n)) == (y >> (m + n)).
3548 : //
3549 : // The least significant n bits of all the values in the range are
3550 : // cleared or set, the m bits above it are preserved and any bits
3551 : // above these are required to be the same for all values in the
3552 : // range.
3553 21497599 : wide_int w = mask;
3554 21497599 : int m = 0, n = 0;
3555 21497599 : if (code == BIT_IOR_EXPR)
3556 6435906 : w = ~w;
3557 21497599 : if (wi::eq_p (w, 0))
3558 7375140 : n = w.get_precision ();
3559 : else
3560 : {
3561 14122459 : n = wi::ctz (w);
3562 14122465 : w = ~(w | wi::mask (n, false, w.get_precision ()));
3563 14122459 : if (wi::eq_p (w, 0))
3564 8568377 : m = w.get_precision () - n;
3565 : else
3566 5554082 : m = wi::ctz (w) - n;
3567 : }
3568 21497599 : wide_int new_mask = wi::mask (m + n, true, w.get_precision ());
3569 21497605 : if ((new_mask & lower_bound) != (new_mask & upper_bound))
3570 : return false;
3571 :
3572 16772223 : wide_int res_lb, res_ub;
3573 16772223 : if (code == BIT_AND_EXPR)
3574 : {
3575 10568062 : res_lb = wi::bit_and (lower_bound, mask);
3576 10568062 : res_ub = wi::bit_and (upper_bound, mask);
3577 : }
3578 6204161 : else if (code == BIT_IOR_EXPR)
3579 : {
3580 6204161 : res_lb = wi::bit_or (lower_bound, mask);
3581 6204161 : res_ub = wi::bit_or (upper_bound, mask);
3582 : }
3583 : else
3584 0 : gcc_unreachable ();
3585 16772223 : value_range_with_overflow (r, type, res_lb, res_ub);
3586 :
3587 : // Furthermore, if the mask is non-zero, an IOR cannot contain zero.
3588 16772223 : if (code == BIT_IOR_EXPR && wi::ne_p (mask, 0))
3589 : {
3590 3157081 : int_range<2> tmp;
3591 3157081 : tmp.set_nonzero (type);
3592 3157081 : r.intersect (tmp);
3593 3157081 : }
3594 16772223 : return true;
3595 61045108 : }
3596 :
3597 : // For range [LB, UB] compute two wide_int bit masks.
3598 : //
3599 : // In the MAYBE_NONZERO bit mask, if some bit is unset, it means that
3600 : // for all numbers in the range the bit is 0, otherwise it might be 0
3601 : // or 1.
3602 : //
3603 : // In the MUSTBE_NONZERO bit mask, if some bit is set, it means that
3604 : // for all numbers in the range the bit is 1, otherwise it might be 0
3605 : // or 1.
3606 :
3607 : void
3608 13028192 : wi_set_zero_nonzero_bits (tree type,
3609 : const wide_int &lb, const wide_int &ub,
3610 : wide_int &maybe_nonzero,
3611 : wide_int &mustbe_nonzero)
3612 : {
3613 13028192 : signop sign = TYPE_SIGN (type);
3614 :
3615 13028192 : if (wi::eq_p (lb, ub))
3616 5201588 : maybe_nonzero = mustbe_nonzero = lb;
3617 7826604 : else if (wi::ge_p (lb, 0, sign) || wi::lt_p (ub, 0, sign))
3618 : {
3619 7396455 : wide_int xor_mask = lb ^ ub;
3620 7396455 : maybe_nonzero = lb | ub;
3621 7396455 : mustbe_nonzero = lb & ub;
3622 7396455 : if (xor_mask != 0)
3623 : {
3624 7396455 : wide_int mask = wi::mask (wi::floor_log2 (xor_mask), false,
3625 14792910 : maybe_nonzero.get_precision ());
3626 7396455 : maybe_nonzero = maybe_nonzero | mask;
3627 7396460 : mustbe_nonzero = wi::bit_and_not (mustbe_nonzero, mask);
3628 7396455 : }
3629 7396455 : }
3630 : else
3631 : {
3632 430149 : maybe_nonzero = wi::minus_one (lb.get_precision ());
3633 430149 : mustbe_nonzero = wi::zero (lb.get_precision ());
3634 : }
3635 13028192 : }
3636 :
3637 : void
3638 16345528 : operator_bitwise_and::wi_fold (irange &r, tree type,
3639 : const wide_int &lh_lb,
3640 : const wide_int &lh_ub,
3641 : const wide_int &rh_lb,
3642 : const wide_int &rh_ub) const
3643 : {
3644 : // The AND algorithm does not handle complex signed operations well.
3645 : // If a signed range crosses the boundary between signed and unsigned
3646 : // process it as 2 ranges and union the results.
3647 16345528 : if (TYPE_SIGN (type) == SIGNED
3648 16345528 : && wi::neg_p (lh_lb, SIGNED) != wi::neg_p (lh_ub, SIGNED))
3649 : {
3650 618212 : int prec = TYPE_PRECISION (type);
3651 618212 : int_range_max tmp;
3652 : // Process [lh_lb, -1]
3653 618212 : wi_fold (tmp, type, lh_lb, wi::minus_one (prec), rh_lb, rh_ub);
3654 : // Now Process [0, rh_ub]
3655 618212 : wi_fold (r, type, wi::zero (prec), lh_ub, rh_lb, rh_ub);
3656 618212 : r.union_ (tmp);
3657 618212 : return;
3658 618212 : }
3659 :
3660 15727316 : if (wi_optimize_and_or (r, BIT_AND_EXPR, type, lh_lb, lh_ub, rh_lb, rh_ub))
3661 : return;
3662 :
3663 5159254 : wide_int maybe_nonzero_lh, mustbe_nonzero_lh;
3664 5159254 : wide_int maybe_nonzero_rh, mustbe_nonzero_rh;
3665 5159254 : wi_set_zero_nonzero_bits (type, lh_lb, lh_ub,
3666 : maybe_nonzero_lh, mustbe_nonzero_lh);
3667 5159254 : wi_set_zero_nonzero_bits (type, rh_lb, rh_ub,
3668 : maybe_nonzero_rh, mustbe_nonzero_rh);
3669 :
3670 5159254 : wide_int new_lb = mustbe_nonzero_lh & mustbe_nonzero_rh;
3671 5159254 : wide_int new_ub = maybe_nonzero_lh & maybe_nonzero_rh;
3672 5159254 : signop sign = TYPE_SIGN (type);
3673 5159254 : unsigned prec = TYPE_PRECISION (type);
3674 : // If both input ranges contain only negative values, we can
3675 : // truncate the result range maximum to the minimum of the
3676 : // input range maxima.
3677 5159254 : if (wi::lt_p (lh_ub, 0, sign) && wi::lt_p (rh_ub, 0, sign))
3678 : {
3679 46591 : new_ub = wi::min (new_ub, lh_ub, sign);
3680 46591 : new_ub = wi::min (new_ub, rh_ub, sign);
3681 : }
3682 : // If either input range contains only non-negative values
3683 : // we can truncate the result range maximum to the respective
3684 : // maximum of the input range.
3685 5159254 : if (wi::ge_p (lh_lb, 0, sign))
3686 4409786 : new_ub = wi::min (new_ub, lh_ub, sign);
3687 5159254 : if (wi::ge_p (rh_lb, 0, sign))
3688 4938994 : new_ub = wi::min (new_ub, rh_ub, sign);
3689 : // PR68217: In case of signed & sign-bit-CST should
3690 : // result in [-INF, 0] instead of [-INF, INF].
3691 5159254 : if (wi::gt_p (new_lb, new_ub, sign))
3692 : {
3693 55524 : wide_int sign_bit = wi::set_bit_in_zero (prec - 1, prec);
3694 55524 : if (sign == SIGNED
3695 55524 : && ((wi::eq_p (lh_lb, lh_ub)
3696 66 : && !wi::cmps (lh_lb, sign_bit))
3697 55524 : || (wi::eq_p (rh_lb, rh_ub)
3698 0 : && !wi::cmps (rh_lb, sign_bit))))
3699 : {
3700 0 : new_lb = wi::min_value (prec, sign);
3701 0 : new_ub = wi::zero (prec);
3702 : }
3703 55524 : }
3704 : // If the limits got swapped around, return varying.
3705 5159254 : if (wi::gt_p (new_lb, new_ub,sign))
3706 : {
3707 55524 : if (sign == SIGNED
3708 55524 : && wi_optimize_signed_bitwise_op (r, type,
3709 : lh_lb, lh_ub,
3710 : rh_lb, rh_ub))
3711 4145 : return;
3712 51379 : r.set_varying (type);
3713 : }
3714 : else
3715 5103730 : value_range_with_overflow (r, type, new_lb, new_ub);
3716 5159254 : }
3717 :
3718 : static void
3719 526789 : set_nonzero_range_from_mask (irange &r, tree type, const irange &lhs)
3720 : {
3721 526789 : if (lhs.undefined_p () || contains_zero_p (lhs))
3722 282892 : r.set_varying (type);
3723 : else
3724 243897 : r.set_nonzero (type);
3725 526789 : }
3726 :
3727 : /* Find out smallest RES where RES > VAL && (RES & MASK) == RES, if any
3728 : (otherwise return VAL). VAL and MASK must be zero-extended for
3729 : precision PREC. If SGNBIT is non-zero, first xor VAL with SGNBIT
3730 : (to transform signed values into unsigned) and at the end xor
3731 : SGNBIT back. */
3732 :
3733 : wide_int
3734 34993 : masked_increment (const wide_int &val_in, const wide_int &mask,
3735 : const wide_int &sgnbit, unsigned int prec)
3736 : {
3737 34993 : wide_int bit = wi::one (prec), res;
3738 34993 : unsigned int i;
3739 :
3740 34993 : wide_int val = val_in ^ sgnbit;
3741 629986 : for (i = 0; i < prec; i++, bit += bit)
3742 : {
3743 584802 : res = mask;
3744 584802 : if ((res & bit) == 0)
3745 502632 : continue;
3746 82170 : res = bit - 1;
3747 82170 : res = wi::bit_and_not (val + bit, res);
3748 82170 : res &= mask;
3749 82170 : if (wi::gtu_p (res, val))
3750 24802 : return res ^ sgnbit;
3751 : }
3752 10191 : return val ^ sgnbit;
3753 34993 : }
3754 :
3755 : // This was shamelessly stolen from register_edge_assert_for_2 and
3756 : // adjusted to work with iranges.
3757 :
3758 : void
3759 3187834 : operator_bitwise_and::simple_op1_range_solver (irange &r, tree type,
3760 : const irange &lhs,
3761 : const irange &op2) const
3762 : {
3763 3187834 : if (!op2.singleton_p ())
3764 : {
3765 525867 : set_nonzero_range_from_mask (r, type, lhs);
3766 1058128 : return;
3767 : }
3768 2661967 : unsigned int nprec = TYPE_PRECISION (type);
3769 2661967 : wide_int cst2v = op2.lower_bound ();
3770 2661967 : bool cst2n = wi::neg_p (cst2v, TYPE_SIGN (type));
3771 2661967 : wide_int sgnbit;
3772 2661967 : if (cst2n)
3773 538675 : sgnbit = wi::set_bit_in_zero (nprec - 1, nprec);
3774 : else
3775 2123292 : sgnbit = wi::zero (nprec);
3776 :
3777 : // Solve [lhs.lower_bound (), +INF] = x & MASK.
3778 : //
3779 : // Minimum unsigned value for >= if (VAL & CST2) == VAL is VAL and
3780 : // maximum unsigned value is ~0. For signed comparison, if CST2
3781 : // doesn't have the most significant bit set, handle it similarly. If
3782 : // CST2 has MSB set, the minimum is the same, and maximum is ~0U/2.
3783 2661967 : wide_int valv = lhs.lower_bound ();
3784 2661967 : wide_int minv = valv & cst2v, maxv;
3785 2661967 : bool we_know_nothing = false;
3786 2661967 : if (minv != valv)
3787 : {
3788 : // If (VAL & CST2) != VAL, X & CST2 can't be equal to VAL.
3789 7295 : minv = masked_increment (valv, cst2v, sgnbit, nprec);
3790 7295 : if (minv == valv)
3791 : {
3792 : // If we can't determine anything on this bound, fall
3793 : // through and conservatively solve for the other end point.
3794 2661967 : we_know_nothing = true;
3795 : }
3796 : }
3797 4785259 : maxv = wi::mask (nprec - (cst2n ? 1 : 0), false, nprec);
3798 2661967 : if (we_know_nothing)
3799 3797 : r.set_varying (type);
3800 : else
3801 2658170 : create_possibly_reversed_range (r, type, minv, maxv);
3802 :
3803 : // Solve [-INF, lhs.upper_bound ()] = x & MASK.
3804 : //
3805 : // Minimum unsigned value for <= is 0 and maximum unsigned value is
3806 : // VAL | ~CST2 if (VAL & CST2) == VAL. Otherwise, find smallest
3807 : // VAL2 where
3808 : // VAL2 > VAL && (VAL2 & CST2) == VAL2 and use (VAL2 - 1) | ~CST2
3809 : // as maximum.
3810 : // For signed comparison, if CST2 doesn't have most significant bit
3811 : // set, handle it similarly. If CST2 has MSB set, the maximum is
3812 : // the same and minimum is INT_MIN.
3813 2661967 : valv = lhs.upper_bound ();
3814 2661967 : minv = valv & cst2v;
3815 2661967 : if (minv == valv)
3816 2634269 : maxv = valv;
3817 : else
3818 : {
3819 27698 : maxv = masked_increment (valv, cst2v, sgnbit, nprec);
3820 27698 : if (maxv == valv)
3821 : {
3822 : // If we couldn't determine anything on either bound, return
3823 : // undefined.
3824 6394 : if (we_know_nothing)
3825 3211 : r.set_undefined ();
3826 6394 : return;
3827 : }
3828 21304 : maxv -= 1;
3829 : }
3830 2655573 : maxv |= ~cst2v;
3831 2655573 : minv = sgnbit;
3832 2655573 : int_range<2> upper_bits;
3833 2655573 : create_possibly_reversed_range (upper_bits, type, minv, maxv);
3834 2655573 : r.intersect (upper_bits);
3835 2661967 : }
3836 :
3837 : bool
3838 3308253 : operator_bitwise_and::op1_range (irange &r, tree type,
3839 : const irange &lhs,
3840 : const irange &op2,
3841 : relation_trio) const
3842 : {
3843 3308253 : if (lhs.undefined_p ())
3844 : return false;
3845 3308253 : if (types_compatible_p (type, boolean_type_node))
3846 814052 : return op_logical_and.op1_range (r, type, lhs, op2);
3847 :
3848 2494201 : r.set_undefined ();
3849 5682035 : for (unsigned i = 0; i < lhs.num_pairs (); ++i)
3850 : {
3851 6375668 : int_range_max chunk (lhs.type (),
3852 6375668 : lhs.lower_bound (i),
3853 6375668 : lhs.upper_bound (i));
3854 3187834 : int_range_max res;
3855 3187834 : simple_op1_range_solver (res, type, chunk, op2);
3856 3187834 : r.union_ (res);
3857 3187834 : }
3858 2494201 : if (r.undefined_p ())
3859 922 : set_nonzero_range_from_mask (r, type, lhs);
3860 :
3861 : // For MASK == op1 & MASK, all the bits in MASK must be set in op1.
3862 2494201 : wide_int mask;
3863 2494201 : if (lhs == op2 && lhs.singleton_p (mask))
3864 : {
3865 340899 : r.update_bitmask (irange_bitmask (mask, ~mask));
3866 340899 : return true;
3867 : }
3868 :
3869 2153302 : if (!op2.singleton_p (mask))
3870 : return true;
3871 :
3872 : // For 0 = op1 & MASK, op1 is ~MASK.
3873 1678778 : if (lhs.zero_p ())
3874 : {
3875 622518 : wide_int nz = wi::bit_not (op2.get_nonzero_bits ());
3876 622518 : int_range<2> tmp (type);
3877 622518 : tmp.set_nonzero_bits (nz);
3878 622518 : r.intersect (tmp);
3879 622518 : }
3880 :
3881 1678778 : irange_bitmask lhs_bm = lhs.get_bitmask ();
3882 : // given [5,7] mask 0x3 value 0x4 = N & [7, 7] mask 0x0 value 0x7
3883 : // Nothing is known about the bits not specified in the mask value (op2),
3884 : // Start with the mask, 1's will occur where values were masked.
3885 1678778 : wide_int op1_mask = ~mask;
3886 : // Any bits that are unknown on the LHS are also unknown in op1,
3887 : // so union the current mask with the LHS mask.
3888 1678778 : op1_mask |= lhs_bm.mask ();
3889 : // The resulting zeros correspond to known bits in the LHS mask, and
3890 : // the LHS value should tell us what they are. Mask off any
3891 : // extraneous values that are not covered by the mask.
3892 1678778 : wide_int op1_value = lhs_bm.value () & ~op1_mask;
3893 1678778 : irange_bitmask op1_bm (op1_value, op1_mask);
3894 : // Intersect this mask with anything already known about the value.
3895 : // A return valueof false indicated the bitmask is an UNDEFINED range.
3896 1678778 : if (op1_bm.intersect (r.get_bitmask ()))
3897 1678778 : r.update_bitmask (op1_bm);
3898 : else
3899 0 : r.set_undefined ();
3900 1678778 : return true;
3901 4172979 : }
3902 :
3903 : bool
3904 878697 : operator_bitwise_and::op2_range (irange &r, tree type,
3905 : const irange &lhs,
3906 : const irange &op1,
3907 : relation_trio) const
3908 : {
3909 878697 : return operator_bitwise_and::op1_range (r, type, lhs, op1);
3910 : }
3911 :
3912 :
3913 : class operator_logical_or : public range_operator
3914 : {
3915 : using range_operator::fold_range;
3916 : using range_operator::op1_range;
3917 : using range_operator::op2_range;
3918 : public:
3919 : bool fold_range (irange &r, tree type,
3920 : const irange &lh,
3921 : const irange &rh,
3922 : relation_trio rel = TRIO_VARYING) const final override;
3923 : bool op1_range (irange &r, tree type,
3924 : const irange &lhs,
3925 : const irange &op2,
3926 : relation_trio rel = TRIO_VARYING) const final override;
3927 : bool op2_range (irange &r, tree type,
3928 : const irange &lhs,
3929 : const irange &op1,
3930 : relation_trio rel = TRIO_VARYING) const final override;
3931 : // Check compatibility of all operands.
3932 0 : bool operand_check_p (tree t1, tree t2, tree t3) const final override
3933 0 : { return range_compatible_p (t1, t2) && range_compatible_p (t1, t3); }
3934 : } op_logical_or;
3935 :
3936 : bool
3937 0 : operator_logical_or::fold_range (irange &r, tree type ATTRIBUTE_UNUSED,
3938 : const irange &lh,
3939 : const irange &rh,
3940 : relation_trio) const
3941 : {
3942 0 : if (empty_range_varying (r, type, lh, rh))
3943 0 : return true;
3944 :
3945 0 : r = lh;
3946 0 : r.union_ (rh);
3947 0 : return true;
3948 : }
3949 :
3950 : bool
3951 344750 : operator_logical_or::op1_range (irange &r, tree type,
3952 : const irange &lhs,
3953 : const irange &op2 ATTRIBUTE_UNUSED,
3954 : relation_trio) const
3955 : {
3956 344750 : switch (get_bool_state (r, lhs, type))
3957 : {
3958 206897 : case BRS_FALSE:
3959 : // A false result means both sides of the OR must be false.
3960 206897 : r = range_false (type);
3961 206897 : break;
3962 137853 : default:
3963 : // Any other result means only one side has to be true, the
3964 : // other side can be anything. so we can't be sure of any result
3965 : // here.
3966 137853 : r = range_true_and_false (type);
3967 137853 : break;
3968 : }
3969 344750 : return true;
3970 : }
3971 :
3972 : bool
3973 0 : operator_logical_or::op2_range (irange &r, tree type,
3974 : const irange &lhs,
3975 : const irange &op1,
3976 : relation_trio) const
3977 : {
3978 0 : return operator_logical_or::op1_range (r, type, lhs, op1);
3979 : }
3980 :
3981 :
3982 : void
3983 2409798 : operator_bitwise_or::update_bitmask (irange &r, const irange &lh,
3984 : const irange &rh) const
3985 : {
3986 2409798 : update_known_bitmask (r, BIT_IOR_EXPR, lh, rh);
3987 2409798 : }
3988 :
3989 : void
3990 7047964 : operator_bitwise_or::wi_fold (irange &r, tree type,
3991 : const wide_int &lh_lb,
3992 : const wide_int &lh_ub,
3993 : const wide_int &rh_lb,
3994 : const wide_int &rh_ub) const
3995 : {
3996 7047964 : if (wi_optimize_and_or (r, BIT_IOR_EXPR, type, lh_lb, lh_ub, rh_lb, rh_ub))
3997 6386300 : return;
3998 :
3999 843803 : wide_int maybe_nonzero_lh, mustbe_nonzero_lh;
4000 843803 : wide_int maybe_nonzero_rh, mustbe_nonzero_rh;
4001 843803 : wi_set_zero_nonzero_bits (type, lh_lb, lh_ub,
4002 : maybe_nonzero_lh, mustbe_nonzero_lh);
4003 843803 : wi_set_zero_nonzero_bits (type, rh_lb, rh_ub,
4004 : maybe_nonzero_rh, mustbe_nonzero_rh);
4005 843803 : wide_int new_lb = mustbe_nonzero_lh | mustbe_nonzero_rh;
4006 843803 : wide_int new_ub = maybe_nonzero_lh | maybe_nonzero_rh;
4007 843803 : signop sign = TYPE_SIGN (type);
4008 : // If the input ranges contain only positive values we can
4009 : // truncate the minimum of the result range to the maximum
4010 : // of the input range minima.
4011 843803 : if (wi::ge_p (lh_lb, 0, sign)
4012 843803 : && wi::ge_p (rh_lb, 0, sign))
4013 : {
4014 632925 : new_lb = wi::max (new_lb, lh_lb, sign);
4015 632925 : new_lb = wi::max (new_lb, rh_lb, sign);
4016 : }
4017 : // If either input range contains only negative values
4018 : // we can truncate the minimum of the result range to the
4019 : // respective minimum range.
4020 843803 : if (wi::lt_p (lh_ub, 0, sign))
4021 20000 : new_lb = wi::max (new_lb, lh_lb, sign);
4022 843803 : if (wi::lt_p (rh_ub, 0, sign))
4023 9561 : new_lb = wi::max (new_lb, rh_lb, sign);
4024 : // If the limits got swapped around, return a conservative range.
4025 843803 : if (wi::gt_p (new_lb, new_ub, sign))
4026 : {
4027 : // Make sure that nonzero|X is nonzero.
4028 182139 : if (wi::gt_p (lh_lb, 0, sign)
4029 177773 : || wi::gt_p (rh_lb, 0, sign)
4030 120947 : || wi::lt_p (lh_ub, 0, sign)
4031 303086 : || wi::lt_p (rh_ub, 0, sign))
4032 61192 : r.set_nonzero (type);
4033 120947 : else if (sign == SIGNED
4034 120947 : && wi_optimize_signed_bitwise_op (r, type,
4035 : lh_lb, lh_ub,
4036 : rh_lb, rh_ub))
4037 : return;
4038 : else
4039 118479 : r.set_varying (type);
4040 179671 : return;
4041 : }
4042 661664 : value_range_with_overflow (r, type, new_lb, new_ub);
4043 843833 : }
4044 :
4045 : bool
4046 597319 : operator_bitwise_or::op1_range (irange &r, tree type,
4047 : const irange &lhs,
4048 : const irange &op2,
4049 : relation_trio) const
4050 : {
4051 597319 : if (lhs.undefined_p ())
4052 : return false;
4053 : // If this is really a logical wi_fold, call that.
4054 597319 : if (types_compatible_p (type, boolean_type_node))
4055 344750 : return op_logical_or.op1_range (r, type, lhs, op2);
4056 :
4057 252569 : if (lhs.zero_p ())
4058 : {
4059 79786 : r.set_zero (type);
4060 79786 : return true;
4061 : }
4062 :
4063 : // if (A < 0 && B < 0)
4064 : // Sometimes gets translated to
4065 : // _1 = A | B
4066 : // if (_1 < 0))
4067 : // It is useful for ranger to recognize a positive LHS means the RHS
4068 : // operands are also positive when dealing with the ELSE range..
4069 240321 : if (TYPE_SIGN (type) == SIGNED && wi::ge_p (lhs.lower_bound (), 0, SIGNED))
4070 : {
4071 26704 : unsigned prec = TYPE_PRECISION (type);
4072 26704 : r.set (type, wi::zero (prec), wi::max_value (prec, SIGNED));
4073 26704 : return true;
4074 : }
4075 146079 : r.set_varying (type);
4076 146079 : return true;
4077 : }
4078 :
4079 : bool
4080 298756 : operator_bitwise_or::op2_range (irange &r, tree type,
4081 : const irange &lhs,
4082 : const irange &op1,
4083 : relation_trio) const
4084 : {
4085 298756 : return operator_bitwise_or::op1_range (r, type, lhs, op1);
4086 : }
4087 :
4088 : void
4089 88699 : operator_bitwise_xor::update_bitmask (irange &r, const irange &lh,
4090 : const irange &rh) const
4091 : {
4092 88699 : update_known_bitmask (r, BIT_XOR_EXPR, lh, rh);
4093 88699 : }
4094 :
4095 : bool
4096 297799 : operator_bitwise_xor::fold_range (irange &r, tree type,
4097 : const irange &lh, const irange &rh,
4098 : relation_trio rel) const
4099 : {
4100 : // Handle X ^ UNDEFINED = UNDEFINED.
4101 297799 : if (lh.undefined_p () || rh.undefined_p ())
4102 : {
4103 392 : r.set_undefined ();
4104 392 : return true;
4105 : }
4106 :
4107 : // Next, handle X ^ X == [0, 0].
4108 297407 : if (rel.op1_op2 () == VREL_EQ)
4109 : {
4110 74 : r.set_zero (type);
4111 74 : return true;
4112 : }
4113 :
4114 : // If either operand is VARYING, the result is VARYING.
4115 297333 : if (lh.varying_p () || rh.varying_p ())
4116 : {
4117 : // If the operands are not equal, zero is not possible.
4118 206602 : if (rel.op1_op2 () != VREL_NE)
4119 205510 : r.set_varying (type);
4120 : else
4121 1092 : r.set_nonzero (type);
4122 206602 : return true;
4123 : }
4124 :
4125 : // Now deal with X ^ 0 == X.
4126 90731 : if (lh.zero_p ())
4127 : {
4128 1477 : r = rh;
4129 1477 : return true;
4130 : }
4131 89254 : if (rh.zero_p ())
4132 : {
4133 555 : r = lh;
4134 555 : return true;
4135 : }
4136 :
4137 : // Start with the legacy range. This can sometimes pick up values
4138 : // when there are a lot of subranges and fold_range aggregates them.
4139 88699 : bool res = range_operator::fold_range (r, type, lh, rh, rel);
4140 :
4141 : // Calculate the XOR identity : x ^ y = (x | y) & ~(x & y)
4142 : // AND and OR are already much better optimized.
4143 88699 : int_range_max tmp1, tmp2, tmp3, new_result;
4144 88699 : int_range<2> varying;
4145 88699 : varying.set_varying (type);
4146 :
4147 88699 : if (m_or.fold_range (tmp1, type, lh, rh, rel)
4148 88699 : && m_and.fold_range (tmp2, type, lh, rh, rel)
4149 88699 : && m_not.fold_range (tmp3, type, tmp2, varying, rel)
4150 177398 : && m_and.fold_range (new_result, type, tmp1, tmp3, rel))
4151 : {
4152 : // If the operands are not equal, or the LH does not contain any
4153 : // element of the RH, zero is not possible.
4154 88699 : tmp1 = lh;
4155 88699 : if (rel.op1_op2 () == VREL_NE
4156 88699 : || (tmp1.intersect (rh) && tmp1.undefined_p ()))
4157 : {
4158 32873 : tmp1.set_nonzero (type);
4159 32873 : new_result.intersect (tmp1);
4160 : }
4161 :
4162 : // Combine with the legacy range if there was one.
4163 88699 : if (res)
4164 88699 : r.intersect (new_result);
4165 : else
4166 0 : r = new_result;
4167 88699 : return true;
4168 : }
4169 : return res;
4170 88699 : }
4171 :
4172 : void
4173 174265 : operator_bitwise_xor::wi_fold (irange &r, tree type,
4174 : const wide_int &lh_lb,
4175 : const wide_int &lh_ub,
4176 : const wide_int &rh_lb,
4177 : const wide_int &rh_ub) const
4178 : {
4179 174265 : signop sign = TYPE_SIGN (type);
4180 174265 : wide_int maybe_nonzero_lh, mustbe_nonzero_lh;
4181 174265 : wide_int maybe_nonzero_rh, mustbe_nonzero_rh;
4182 174265 : wi_set_zero_nonzero_bits (type, lh_lb, lh_ub,
4183 : maybe_nonzero_lh, mustbe_nonzero_lh);
4184 174265 : wi_set_zero_nonzero_bits (type, rh_lb, rh_ub,
4185 : maybe_nonzero_rh, mustbe_nonzero_rh);
4186 :
4187 522795 : wide_int result_zero_bits = ((mustbe_nonzero_lh & mustbe_nonzero_rh)
4188 522795 : | ~(maybe_nonzero_lh | maybe_nonzero_rh));
4189 174265 : wide_int result_one_bits
4190 348530 : = (wi::bit_and_not (mustbe_nonzero_lh, maybe_nonzero_rh)
4191 348530 : | wi::bit_and_not (mustbe_nonzero_rh, maybe_nonzero_lh));
4192 174265 : wide_int new_ub = ~result_zero_bits;
4193 174265 : wide_int new_lb = result_one_bits;
4194 :
4195 : // If the range has all positive or all negative values, the result
4196 : // is better than VARYING.
4197 174265 : if (wi::lt_p (new_lb, 0, sign) || wi::ge_p (new_ub, 0, sign))
4198 166944 : value_range_with_overflow (r, type, new_lb, new_ub);
4199 7321 : else if (sign == SIGNED
4200 7321 : && wi_optimize_signed_bitwise_op (r, type,
4201 : lh_lb, lh_ub,
4202 : rh_lb, rh_ub))
4203 : ; /* Do nothing. */
4204 : else
4205 1059 : r.set_varying (type);
4206 :
4207 : /* Furthermore, XOR is non-zero if its arguments can't be equal. */
4208 174265 : if (wi::lt_p (lh_ub, rh_lb, sign)
4209 113211 : || wi::lt_p (rh_ub, lh_lb, sign)
4210 266387 : || wi::ne_p (result_one_bits, 0))
4211 : {
4212 82143 : int_range<2> tmp;
4213 82143 : tmp.set_nonzero (type);
4214 82143 : r.intersect (tmp);
4215 82143 : }
4216 174265 : }
4217 :
4218 : bool
4219 88699 : operator_bitwise_xor::op1_op2_relation_effect (irange &lhs_range,
4220 : tree type,
4221 : const irange &,
4222 : const irange &,
4223 : relation_kind rel) const
4224 : {
4225 88699 : if (rel == VREL_VARYING)
4226 : return false;
4227 :
4228 3636 : int_range<2> rel_range;
4229 :
4230 3636 : switch (rel)
4231 : {
4232 0 : case VREL_EQ:
4233 0 : rel_range.set_zero (type);
4234 0 : break;
4235 488 : case VREL_NE:
4236 488 : rel_range.set_nonzero (type);
4237 488 : break;
4238 : default:
4239 : return false;
4240 : }
4241 :
4242 488 : lhs_range.intersect (rel_range);
4243 488 : return true;
4244 3636 : }
4245 :
4246 : bool
4247 89194 : operator_bitwise_xor::op1_range (irange &r, tree type,
4248 : const irange &lhs,
4249 : const irange &op2,
4250 : relation_trio) const
4251 : {
4252 89194 : if (lhs.undefined_p () || lhs.varying_p ())
4253 : {
4254 7487 : r = lhs;
4255 7487 : return true;
4256 : }
4257 81707 : if (types_compatible_p (type, boolean_type_node))
4258 : {
4259 1802 : switch (get_bool_state (r, lhs, type))
4260 : {
4261 801 : case BRS_TRUE:
4262 801 : if (op2.varying_p ())
4263 769 : r.set_varying (type);
4264 32 : else if (op2.zero_p ())
4265 24 : r = range_true (type);
4266 : // See get_bool_state for the rationale
4267 8 : else if (op2.undefined_p () || contains_zero_p (op2))
4268 0 : r = range_true_and_false (type);
4269 : else
4270 8 : r = range_false (type);
4271 : break;
4272 1001 : case BRS_FALSE:
4273 1001 : r = op2;
4274 1001 : break;
4275 : default:
4276 : break;
4277 : }
4278 1802 : return true;
4279 : }
4280 79905 : r.set_varying (type);
4281 79905 : return true;
4282 : }
4283 :
4284 : bool
4285 37129 : operator_bitwise_xor::op2_range (irange &r, tree type,
4286 : const irange &lhs,
4287 : const irange &op1,
4288 : relation_trio) const
4289 : {
4290 37129 : return operator_bitwise_xor::op1_range (r, type, lhs, op1);
4291 : }
4292 :
4293 : class operator_trunc_mod : public range_operator
4294 : {
4295 : using range_operator::op1_range;
4296 : using range_operator::op2_range;
4297 : using range_operator::update_bitmask;
4298 : public:
4299 : virtual void wi_fold (irange &r, tree type,
4300 : const wide_int &lh_lb,
4301 : const wide_int &lh_ub,
4302 : const wide_int &rh_lb,
4303 : const wide_int &rh_ub) const;
4304 : virtual bool op1_range (irange &r, tree type,
4305 : const irange &lhs,
4306 : const irange &op2,
4307 : relation_trio) const;
4308 : virtual bool op2_range (irange &r, tree type,
4309 : const irange &lhs,
4310 : const irange &op1,
4311 : relation_trio) const;
4312 1144000 : void update_bitmask (irange &r, const irange &lh, const irange &rh) const
4313 1144000 : { update_known_bitmask (r, TRUNC_MOD_EXPR, lh, rh); }
4314 : } op_trunc_mod;
4315 :
4316 : void
4317 1413684 : operator_trunc_mod::wi_fold (irange &r, tree type,
4318 : const wide_int &lh_lb,
4319 : const wide_int &lh_ub,
4320 : const wide_int &rh_lb,
4321 : const wide_int &rh_ub) const
4322 : {
4323 1413684 : wide_int new_lb, new_ub, tmp;
4324 1413684 : signop sign = TYPE_SIGN (type);
4325 1413684 : unsigned prec = TYPE_PRECISION (type);
4326 :
4327 : // Mod 0 is undefined.
4328 1413684 : if (wi_zero_p (type, rh_lb, rh_ub))
4329 : {
4330 10122 : r.set_undefined ();
4331 10122 : return;
4332 : }
4333 :
4334 : // Check for constant and try to fold.
4335 1625166 : if (lh_lb == lh_ub && rh_lb == rh_ub)
4336 : {
4337 21417 : wi::overflow_type ov = wi::OVF_NONE;
4338 21417 : tmp = wi::mod_trunc (lh_lb, rh_lb, sign, &ov);
4339 21417 : if (ov == wi::OVF_NONE)
4340 : {
4341 21391 : r = int_range<2> (type, tmp, tmp);
4342 21391 : return;
4343 : }
4344 : }
4345 :
4346 : // ABS (A % B) < ABS (B) and either 0 <= A % B <= A or A <= A % B <= 0.
4347 1382171 : new_ub = rh_ub - 1;
4348 1382171 : if (sign == SIGNED)
4349 : {
4350 613910 : tmp = -1 - rh_lb;
4351 613910 : new_ub = wi::smax (new_ub, tmp);
4352 : }
4353 :
4354 1382171 : if (sign == UNSIGNED)
4355 768261 : new_lb = wi::zero (prec);
4356 : else
4357 : {
4358 613910 : new_lb = -new_ub;
4359 613910 : tmp = lh_lb;
4360 613910 : if (wi::gts_p (tmp, 0))
4361 141937 : tmp = wi::zero (prec);
4362 613952 : new_lb = wi::smax (new_lb, tmp);
4363 : }
4364 1382171 : tmp = lh_ub;
4365 1382171 : if (sign == SIGNED && wi::neg_p (tmp))
4366 33149 : tmp = wi::zero (prec);
4367 1382171 : new_ub = wi::min (new_ub, tmp, sign);
4368 :
4369 1382171 : value_range_with_overflow (r, type, new_lb, new_ub);
4370 :
4371 : // When all positive and all X/Y combinations produce the same quotient
4372 : // we can refine the result with X % Y == X - Q * Y.
4373 : // Ensure that division by 0 is not an option.
4374 1382171 : if (wi::gt_p (rh_lb, 0, sign) && wi::ge_p (lh_lb, 0, sign))
4375 : {
4376 334542 : wide_int q_lb = wi::div_trunc (lh_lb, rh_ub, sign);
4377 334542 : wide_int q_ub = wi::div_trunc (lh_ub, rh_lb, sign);
4378 :
4379 334542 : if (q_lb == q_ub)
4380 : {
4381 42406 : new_lb = lh_lb - q_lb * rh_ub;
4382 42406 : new_ub = lh_ub - q_lb * rh_lb;
4383 :
4384 42406 : int_range<2> refined (type, new_lb, new_ub);
4385 42406 : r.intersect (refined);
4386 42406 : }
4387 334586 : }
4388 1414000 : }
4389 :
4390 : bool
4391 520631 : operator_trunc_mod::op1_range (irange &r, tree type,
4392 : const irange &lhs,
4393 : const irange &,
4394 : relation_trio) const
4395 : {
4396 520631 : if (lhs.undefined_p ())
4397 : return false;
4398 : // PR 91029.
4399 520631 : signop sign = TYPE_SIGN (type);
4400 520631 : unsigned prec = TYPE_PRECISION (type);
4401 : // (a % b) >= x && x > 0 , then a >= x.
4402 520721 : if (wi::gt_p (lhs.lower_bound (), 0, sign))
4403 : {
4404 133839 : r.set (type, lhs.lower_bound (), wi::max_value (prec, sign));
4405 133806 : return true;
4406 : }
4407 : // (a % b) <= x && x < 0 , then a <= x.
4408 386882 : if (wi::lt_p (lhs.upper_bound (), 0, sign))
4409 : {
4410 8371 : r.set (type, wi::min_value (prec, sign), lhs.upper_bound ());
4411 8371 : return true;
4412 : }
4413 : return false;
4414 : }
4415 :
4416 : bool
4417 328047 : operator_trunc_mod::op2_range (irange &r, tree type,
4418 : const irange &lhs,
4419 : const irange &,
4420 : relation_trio) const
4421 : {
4422 328047 : if (lhs.undefined_p ())
4423 : return false;
4424 : // PR 91029.
4425 328047 : signop sign = TYPE_SIGN (type);
4426 328047 : unsigned prec = TYPE_PRECISION (type);
4427 : // (a % b) >= x && x > 0 , then b is in ~[-x, x] for signed
4428 : // or b > x for unsigned.
4429 328078 : if (wi::gt_p (lhs.lower_bound (), 0, sign))
4430 : {
4431 53317 : if (sign == SIGNED)
4432 1953 : r.set (type, wi::neg (lhs.lower_bound ()),
4433 3906 : lhs.lower_bound (), VR_ANTI_RANGE);
4434 51376 : else if (wi::lt_p (lhs.lower_bound (), wi::max_value (prec, sign),
4435 : sign))
4436 51382 : r.set (type, lhs.lower_bound () + 1, wi::max_value (prec, sign));
4437 : else
4438 : return false;
4439 53317 : return true;
4440 : }
4441 : // (a % b) <= x && x < 0 , then b is in ~[x, -x].
4442 274755 : if (wi::lt_p (lhs.upper_bound (), 0, sign))
4443 : {
4444 5278 : if (wi::gt_p (lhs.upper_bound (), wi::min_value (prec, sign), sign))
4445 5278 : r.set (type, lhs.upper_bound (),
4446 10556 : wi::neg (lhs.upper_bound ()), VR_ANTI_RANGE);
4447 : else
4448 : return false;
4449 5278 : return true;
4450 : }
4451 : return false;
4452 : }
4453 :
4454 :
4455 : class operator_logical_not : public range_operator
4456 : {
4457 : using range_operator::fold_range;
4458 : using range_operator::op1_range;
4459 : public:
4460 : bool fold_range (irange &r, tree type,
4461 : const irange &lh,
4462 : const irange &rh,
4463 : relation_trio rel = TRIO_VARYING) const final override;
4464 : bool op1_range (irange &r, tree type,
4465 : const irange &lhs,
4466 : const irange &op2,
4467 : relation_trio rel = TRIO_VARYING) const final override;
4468 : // Check compatibility of LHS and op1.
4469 0 : bool operand_check_p (tree t1, tree t2, tree) const final override
4470 0 : { return range_compatible_p (t1, t2); }
4471 : } op_logical_not;
4472 :
4473 : // Folding a logical NOT, oddly enough, involves doing nothing on the
4474 : // forward pass through. During the initial walk backwards, the
4475 : // logical NOT reversed the desired outcome on the way back, so on the
4476 : // way forward all we do is pass the range forward.
4477 : //
4478 : // b_2 = x_1 < 20
4479 : // b_3 = !b_2
4480 : // if (b_3)
4481 : // to determine the TRUE branch, walking backward
4482 : // if (b_3) if ([1,1])
4483 : // b_3 = !b_2 [1,1] = ![0,0]
4484 : // b_2 = x_1 < 20 [0,0] = x_1 < 20, false, so x_1 == [20, 255]
4485 : // which is the result we are looking for.. so.. pass it through.
4486 :
4487 : bool
4488 247437 : operator_logical_not::fold_range (irange &r, tree type,
4489 : const irange &lh,
4490 : const irange &rh ATTRIBUTE_UNUSED,
4491 : relation_trio) const
4492 : {
4493 247437 : if (empty_range_varying (r, type, lh, rh))
4494 0 : return true;
4495 :
4496 247437 : r = lh;
4497 247437 : if (!lh.varying_p () && !lh.undefined_p ())
4498 55135 : r.invert ();
4499 :
4500 : return true;
4501 : }
4502 :
4503 : bool
4504 29473 : operator_logical_not::op1_range (irange &r,
4505 : tree type,
4506 : const irange &lhs,
4507 : const irange &op2,
4508 : relation_trio) const
4509 : {
4510 : // Logical NOT is involutary...do it again.
4511 29473 : return fold_range (r, type, lhs, op2);
4512 : }
4513 :
4514 : bool
4515 623883 : operator_bitwise_not::fold_range (irange &r, tree type,
4516 : const irange &lh,
4517 : const irange &rh,
4518 : relation_trio) const
4519 : {
4520 623883 : if (empty_range_varying (r, type, lh, rh))
4521 121 : return true;
4522 :
4523 623762 : if (types_compatible_p (type, boolean_type_node))
4524 217964 : return op_logical_not.fold_range (r, type, lh, rh);
4525 :
4526 : // ~X is simply -1 - X.
4527 811596 : int_range<1> minusone (type, wi::minus_one (TYPE_PRECISION (type)),
4528 811596 : wi::minus_one (TYPE_PRECISION (type)));
4529 405798 : return range_op_handler (MINUS_EXPR).fold_range (r, type, minusone, lh);
4530 405798 : }
4531 :
4532 : bool
4533 53798 : operator_bitwise_not::op1_range (irange &r, tree type,
4534 : const irange &lhs,
4535 : const irange &op2,
4536 : relation_trio) const
4537 : {
4538 53798 : if (lhs.undefined_p ())
4539 : return false;
4540 53798 : if (types_compatible_p (type, boolean_type_node))
4541 29473 : return op_logical_not.op1_range (r, type, lhs, op2);
4542 :
4543 : // ~X is -1 - X and since bitwise NOT is involutary...do it again.
4544 24325 : return fold_range (r, type, lhs, op2);
4545 : }
4546 :
4547 : void
4548 0 : operator_bitwise_not::update_bitmask (irange &r, const irange &lh,
4549 : const irange &rh) const
4550 : {
4551 0 : update_known_bitmask (r, BIT_NOT_EXPR, lh, rh);
4552 0 : }
4553 :
4554 :
4555 : bool
4556 267969 : operator_cst::fold_range (irange &r, tree type ATTRIBUTE_UNUSED,
4557 : const irange &lh,
4558 : const irange &rh ATTRIBUTE_UNUSED,
4559 : relation_trio) const
4560 : {
4561 267969 : r = lh;
4562 267969 : return true;
4563 : }
4564 :
4565 :
4566 : // Determine if there is a relationship between LHS and OP1.
4567 :
4568 : relation_kind
4569 910265 : operator_identity::lhs_op1_relation (const irange &lhs,
4570 : const irange &op1 ATTRIBUTE_UNUSED,
4571 : const irange &op2 ATTRIBUTE_UNUSED,
4572 : relation_kind) const
4573 : {
4574 910265 : if (lhs.undefined_p ())
4575 576 : return VREL_VARYING;
4576 : // Simply a copy, so they are equivalent.
4577 : return VREL_EQ;
4578 : }
4579 :
4580 : bool
4581 910989 : operator_identity::fold_range (irange &r, tree type ATTRIBUTE_UNUSED,
4582 : const irange &lh,
4583 : const irange &rh ATTRIBUTE_UNUSED,
4584 : relation_trio) const
4585 : {
4586 910989 : r = lh;
4587 910989 : return true;
4588 : }
4589 :
4590 : bool
4591 293485 : operator_identity::op1_range (irange &r, tree type ATTRIBUTE_UNUSED,
4592 : const irange &lhs,
4593 : const irange &op2 ATTRIBUTE_UNUSED,
4594 : relation_trio) const
4595 : {
4596 293485 : r = lhs;
4597 293485 : return true;
4598 : }
4599 :
4600 :
4601 : class operator_unknown : public range_operator
4602 : {
4603 : using range_operator::fold_range;
4604 : public:
4605 : virtual bool fold_range (irange &r, tree type,
4606 : const irange &op1,
4607 : const irange &op2,
4608 : relation_trio rel = TRIO_VARYING) const;
4609 : } op_unknown;
4610 :
4611 : bool
4612 1332144 : operator_unknown::fold_range (irange &r, tree type,
4613 : const irange &lh ATTRIBUTE_UNUSED,
4614 : const irange &rh ATTRIBUTE_UNUSED,
4615 : relation_trio) const
4616 : {
4617 1332144 : r.set_varying (type);
4618 1332144 : return true;
4619 : }
4620 :
4621 :
4622 : void
4623 112405 : operator_abs::wi_fold (irange &r, tree type,
4624 : const wide_int &lh_lb, const wide_int &lh_ub,
4625 : const wide_int &rh_lb ATTRIBUTE_UNUSED,
4626 : const wide_int &rh_ub ATTRIBUTE_UNUSED) const
4627 : {
4628 112405 : wide_int min, max;
4629 112405 : signop sign = TYPE_SIGN (type);
4630 112405 : unsigned prec = TYPE_PRECISION (type);
4631 :
4632 : // Pass through LH for the easy cases.
4633 112405 : if (sign == UNSIGNED || wi::ge_p (lh_lb, 0, sign))
4634 : {
4635 11953 : r = int_range<1> (type, lh_lb, lh_ub);
4636 11953 : return;
4637 : }
4638 :
4639 : // -TYPE_MIN_VALUE = TYPE_MIN_VALUE with flag_wrapv so we can't get
4640 : // a useful range.
4641 100452 : wide_int min_value = wi::min_value (prec, sign);
4642 100452 : wide_int max_value = wi::max_value (prec, sign);
4643 100452 : if (!TYPE_OVERFLOW_UNDEFINED (type) && wi::eq_p (lh_lb, min_value))
4644 : {
4645 640 : r.set_varying (type);
4646 640 : return;
4647 : }
4648 :
4649 : // ABS_EXPR may flip the range around, if the original range
4650 : // included negative values.
4651 99812 : if (wi::eq_p (lh_lb, min_value))
4652 : {
4653 : // ABS ([-MIN, -MIN]) isn't representable, but we have traditionally
4654 : // returned [-MIN,-MIN] so this preserves that behavior. PR37078
4655 35572 : if (wi::eq_p (lh_ub, min_value))
4656 : {
4657 104 : r = int_range<1> (type, min_value, min_value);
4658 104 : return;
4659 : }
4660 35468 : min = max_value;
4661 : }
4662 : else
4663 64240 : min = wi::abs (lh_lb);
4664 :
4665 99708 : if (wi::eq_p (lh_ub, min_value))
4666 0 : max = max_value;
4667 : else
4668 99708 : max = wi::abs (lh_ub);
4669 :
4670 : // If the range contains zero then we know that the minimum value in the
4671 : // range will be zero.
4672 99708 : if (wi::le_p (lh_lb, 0, sign) && wi::ge_p (lh_ub, 0, sign))
4673 : {
4674 90015 : if (wi::gt_p (min, max, sign))
4675 52021 : max = min;
4676 90015 : min = wi::zero (prec);
4677 : }
4678 : else
4679 : {
4680 : // If the range was reversed, swap MIN and MAX.
4681 9693 : if (wi::gt_p (min, max, sign))
4682 9097 : std::swap (min, max);
4683 : }
4684 :
4685 : // If the new range has its limits swapped around (MIN > MAX), then
4686 : // the operation caused one of them to wrap around. The only thing
4687 : // we know is that the result is positive.
4688 99708 : if (wi::gt_p (min, max, sign))
4689 : {
4690 0 : min = wi::zero (prec);
4691 0 : max = max_value;
4692 : }
4693 99708 : r = int_range<1> (type, min, max);
4694 113149 : }
4695 :
4696 : bool
4697 96704 : operator_abs::op1_range (irange &r, tree type,
4698 : const irange &lhs,
4699 : const irange &op2,
4700 : relation_trio) const
4701 : {
4702 96704 : if (empty_range_varying (r, type, lhs, op2))
4703 0 : return true;
4704 96704 : if (TYPE_UNSIGNED (type))
4705 : {
4706 0 : r = lhs;
4707 0 : return true;
4708 : }
4709 : // Start with the positives because negatives are an impossible result.
4710 96704 : int_range_max positives = range_positives (type);
4711 96704 : positives.intersect (lhs);
4712 96704 : r = positives;
4713 : // Then add the negative of each pair:
4714 : // ABS(op1) = [5,20] would yield op1 => [-20,-5][5,20].
4715 194205 : for (unsigned i = 0; i < positives.num_pairs (); ++i)
4716 97501 : r.union_ (int_range<1> (type,
4717 195002 : -positives.upper_bound (i),
4718 292503 : -positives.lower_bound (i)));
4719 : // With flag_wrapv, -TYPE_MIN_VALUE = TYPE_MIN_VALUE which is
4720 : // unrepresentable. Add -TYPE_MIN_VALUE in this case.
4721 96704 : wide_int min_value = wi::min_value (TYPE_PRECISION (type), TYPE_SIGN (type));
4722 96704 : wide_int lb = lhs.lower_bound ();
4723 96704 : if (!TYPE_OVERFLOW_UNDEFINED (type) && wi::eq_p (lb, min_value))
4724 168 : r.union_ (int_range<2> (type, lb, lb));
4725 96704 : return true;
4726 96704 : }
4727 :
4728 : void
4729 105386 : operator_abs::update_bitmask (irange &r, const irange &lh,
4730 : const irange &rh) const
4731 : {
4732 105386 : update_known_bitmask (r, ABS_EXPR, lh, rh);
4733 105386 : }
4734 :
4735 : class operator_absu : public range_operator
4736 : {
4737 : using range_operator::update_bitmask;
4738 : public:
4739 : virtual void wi_fold (irange &r, tree type,
4740 : const wide_int &lh_lb, const wide_int &lh_ub,
4741 : const wide_int &rh_lb, const wide_int &rh_ub)
4742 : const final override;
4743 : virtual void update_bitmask (irange &r, const irange &lh,
4744 : const irange &rh) const final override;
4745 : } op_absu;
4746 :
4747 : void
4748 12988 : operator_absu::wi_fold (irange &r, tree type,
4749 : const wide_int &lh_lb, const wide_int &lh_ub,
4750 : const wide_int &rh_lb ATTRIBUTE_UNUSED,
4751 : const wide_int &rh_ub ATTRIBUTE_UNUSED) const
4752 : {
4753 12988 : wide_int new_lb, new_ub;
4754 :
4755 : // Pass through VR0 the easy cases.
4756 12988 : if (wi::ges_p (lh_lb, 0))
4757 : {
4758 2435 : new_lb = lh_lb;
4759 2435 : new_ub = lh_ub;
4760 : }
4761 : else
4762 : {
4763 10553 : new_lb = wi::abs (lh_lb);
4764 10553 : new_ub = wi::abs (lh_ub);
4765 :
4766 : // If the range contains zero then we know that the minimum
4767 : // value in the range will be zero.
4768 10553 : if (wi::ges_p (lh_ub, 0))
4769 : {
4770 8101 : if (wi::gtu_p (new_lb, new_ub))
4771 6808 : new_ub = new_lb;
4772 8101 : new_lb = wi::zero (TYPE_PRECISION (type));
4773 : }
4774 : else
4775 2452 : std::swap (new_lb, new_ub);
4776 : }
4777 :
4778 12988 : gcc_checking_assert (TYPE_UNSIGNED (type));
4779 12988 : r = int_range<1> (type, new_lb, new_ub);
4780 12988 : }
4781 :
4782 : void
4783 11653 : operator_absu::update_bitmask (irange &r, const irange &lh,
4784 : const irange &rh) const
4785 : {
4786 11653 : update_known_bitmask (r, ABSU_EXPR, lh, rh);
4787 11653 : }
4788 :
4789 :
4790 : bool
4791 565577 : operator_negate::fold_range (irange &r, tree type,
4792 : const irange &lh,
4793 : const irange &rh,
4794 : relation_trio) const
4795 : {
4796 565577 : if (empty_range_varying (r, type, lh, rh))
4797 887 : return true;
4798 :
4799 : // -X is simply 0 - X.
4800 564690 : int_range<1> zero;
4801 564690 : zero.set_zero (type);
4802 564690 : return range_op_handler (MINUS_EXPR).fold_range (r, type, zero, lh);
4803 564690 : }
4804 :
4805 : bool
4806 74481 : operator_negate::op1_range (irange &r, tree type,
4807 : const irange &lhs,
4808 : const irange &op2,
4809 : relation_trio) const
4810 : {
4811 : // NEGATE is involutory.
4812 74481 : return fold_range (r, type, lhs, op2);
4813 : }
4814 :
4815 :
4816 : bool
4817 0 : operator_addr_expr::fold_range (irange &r, tree type,
4818 : const irange &lh,
4819 : const irange &rh,
4820 : relation_trio) const
4821 : {
4822 0 : if (empty_range_varying (r, type, lh, rh))
4823 0 : return true;
4824 :
4825 : // Return a non-null pointer of the LHS type (passed in op2).
4826 0 : if (lh.zero_p ())
4827 0 : r.set_zero (type);
4828 0 : else if (lh.undefined_p () || contains_zero_p (lh))
4829 0 : r.set_varying (type);
4830 : else
4831 0 : r.set_nonzero (type);
4832 : return true;
4833 : }
4834 :
4835 : bool
4836 0 : operator_addr_expr::op1_range (irange &r, tree type,
4837 : const irange &lhs,
4838 : const irange &op2,
4839 : relation_trio) const
4840 : {
4841 0 : if (empty_range_varying (r, type, lhs, op2))
4842 0 : return true;
4843 :
4844 : // Return a non-null pointer of the LHS type (passed in op2), but only
4845 : // if we cant overflow, eitherwise a no-zero offset could wrap to zero.
4846 : // See PR 111009.
4847 0 : if (!lhs.undefined_p () && !contains_zero_p (lhs) && TYPE_OVERFLOW_UNDEFINED (type))
4848 0 : r.set_nonzero (type);
4849 : else
4850 0 : r.set_varying (type);
4851 : return true;
4852 : }
4853 :
4854 : // Initialize any integral operators to the primary table
4855 :
4856 : void
4857 291201 : range_op_table::initialize_integral_ops ()
4858 : {
4859 291201 : set (TRUNC_DIV_EXPR, op_trunc_div);
4860 291201 : set (FLOOR_DIV_EXPR, op_floor_div);
4861 291201 : set (ROUND_DIV_EXPR, op_round_div);
4862 291201 : set (CEIL_DIV_EXPR, op_ceil_div);
4863 291201 : set (EXACT_DIV_EXPR, op_exact_div);
4864 291201 : set (LSHIFT_EXPR, op_lshift);
4865 291201 : set (RSHIFT_EXPR, op_rshift);
4866 291201 : set (TRUTH_AND_EXPR, op_logical_and);
4867 291201 : set (TRUTH_OR_EXPR, op_logical_or);
4868 291201 : set (TRUNC_MOD_EXPR, op_trunc_mod);
4869 291201 : set (TRUTH_NOT_EXPR, op_logical_not);
4870 291201 : set (IMAGPART_EXPR, op_unknown);
4871 291201 : set (REALPART_EXPR, op_unknown);
4872 291201 : set (ABSU_EXPR, op_absu);
4873 291201 : set (OP_WIDEN_MULT_SIGNED, op_widen_mult_signed);
4874 291201 : set (OP_WIDEN_MULT_UNSIGNED, op_widen_mult_unsigned);
4875 291201 : set (OP_WIDEN_MULT_SIGNED_UNSIGNED, op_widen_mult_signed_unsigned);
4876 291201 : set (OP_WIDEN_PLUS_SIGNED, op_widen_plus_signed);
4877 291201 : set (OP_WIDEN_PLUS_UNSIGNED, op_widen_plus_unsigned);
4878 :
4879 291201 : }
4880 :
4881 : bool
4882 41510 : operator_plus::overflow_free_p (const irange &lh, const irange &rh,
4883 : relation_trio) const
4884 : {
4885 41510 : if (lh.undefined_p () || rh.undefined_p ())
4886 : return false;
4887 :
4888 41510 : tree type = lh.type ();
4889 41510 : if (TYPE_OVERFLOW_UNDEFINED (type))
4890 : return true;
4891 :
4892 10725 : wi::overflow_type ovf;
4893 10725 : signop sgn = TYPE_SIGN (type);
4894 10725 : wide_int wmax0 = lh.upper_bound ();
4895 10725 : wide_int wmax1 = rh.upper_bound ();
4896 10725 : wi::add (wmax0, wmax1, sgn, &ovf);
4897 10725 : if (ovf != wi::OVF_NONE)
4898 : return false;
4899 :
4900 1296 : if (TYPE_UNSIGNED (type))
4901 : return true;
4902 :
4903 372 : wide_int wmin0 = lh.lower_bound ();
4904 372 : wide_int wmin1 = rh.lower_bound ();
4905 372 : wi::add (wmin0, wmin1, sgn, &ovf);
4906 372 : if (ovf != wi::OVF_NONE)
4907 261 : return false;
4908 :
4909 : return true;
4910 11097 : }
4911 :
4912 : bool
4913 31 : operator_minus::overflow_free_p (const irange &lh, const irange &rh,
4914 : relation_trio) const
4915 : {
4916 31 : if (lh.undefined_p () || rh.undefined_p ())
4917 : return false;
4918 :
4919 31 : tree type = lh.type ();
4920 31 : if (TYPE_OVERFLOW_UNDEFINED (type))
4921 : return true;
4922 :
4923 10 : wi::overflow_type ovf;
4924 10 : signop sgn = TYPE_SIGN (type);
4925 10 : wide_int wmin0 = lh.lower_bound ();
4926 10 : wide_int wmax1 = rh.upper_bound ();
4927 10 : wi::sub (wmin0, wmax1, sgn, &ovf);
4928 10 : if (ovf != wi::OVF_NONE)
4929 : return false;
4930 :
4931 7 : if (TYPE_UNSIGNED (type))
4932 : return true;
4933 :
4934 6 : wide_int wmax0 = lh.upper_bound ();
4935 6 : wide_int wmin1 = rh.lower_bound ();
4936 6 : wi::sub (wmax0, wmin1, sgn, &ovf);
4937 6 : if (ovf != wi::OVF_NONE)
4938 0 : return false;
4939 :
4940 : return true;
4941 16 : }
4942 :
4943 : bool
4944 3140 : operator_mult::overflow_free_p (const irange &lh, const irange &rh,
4945 : relation_trio) const
4946 : {
4947 3140 : if (lh.undefined_p () || rh.undefined_p ())
4948 : return false;
4949 :
4950 3140 : tree type = lh.type ();
4951 3140 : if (TYPE_OVERFLOW_UNDEFINED (type))
4952 : return true;
4953 :
4954 2658 : wi::overflow_type ovf;
4955 2658 : signop sgn = TYPE_SIGN (type);
4956 2658 : wide_int wmax0 = lh.upper_bound ();
4957 2658 : wide_int wmax1 = rh.upper_bound ();
4958 2658 : wi::mul (wmax0, wmax1, sgn, &ovf);
4959 2658 : if (ovf != wi::OVF_NONE)
4960 : return false;
4961 :
4962 105 : if (TYPE_UNSIGNED (type))
4963 : return true;
4964 :
4965 22 : wide_int wmin0 = lh.lower_bound ();
4966 22 : wide_int wmin1 = rh.lower_bound ();
4967 22 : wi::mul (wmin0, wmin1, sgn, &ovf);
4968 22 : if (ovf != wi::OVF_NONE)
4969 : return false;
4970 :
4971 22 : wi::mul (wmin0, wmax1, sgn, &ovf);
4972 22 : if (ovf != wi::OVF_NONE)
4973 : return false;
4974 :
4975 22 : wi::mul (wmax0, wmin1, sgn, &ovf);
4976 22 : if (ovf != wi::OVF_NONE)
4977 : return false;
4978 :
4979 : return true;
4980 2680 : }
4981 :
4982 : #if CHECKING_P
4983 : #include "selftest.h"
4984 :
4985 : namespace selftest
4986 : {
4987 : #define INT(x) wi::shwi ((x), TYPE_PRECISION (integer_type_node))
4988 : #define UINT(x) wi::uhwi ((x), TYPE_PRECISION (unsigned_type_node))
4989 : #define INT16(x) wi::shwi ((x), TYPE_PRECISION (short_integer_type_node))
4990 : #define UINT16(x) wi::uhwi ((x), TYPE_PRECISION (short_unsigned_type_node))
4991 : #define SCHAR(x) wi::shwi ((x), TYPE_PRECISION (signed_char_type_node))
4992 : #define UCHAR(x) wi::uhwi ((x), TYPE_PRECISION (unsigned_char_type_node))
4993 :
4994 : static void
4995 4 : range_op_cast_tests ()
4996 : {
4997 4 : int_range<2> r0, r1, r2, rold;
4998 4 : r0.set_varying (integer_type_node);
4999 4 : wide_int maxint = r0.upper_bound ();
5000 :
5001 : // If a range is in any way outside of the range for the converted
5002 : // to range, default to the range for the new type.
5003 4 : r0.set_varying (short_integer_type_node);
5004 4 : wide_int minshort = r0.lower_bound ();
5005 4 : wide_int maxshort = r0.upper_bound ();
5006 4 : if (TYPE_PRECISION (integer_type_node)
5007 4 : > TYPE_PRECISION (short_integer_type_node))
5008 : {
5009 8 : r1 = int_range<1> (integer_type_node,
5010 4 : wi::zero (TYPE_PRECISION (integer_type_node)),
5011 8 : maxint);
5012 4 : range_cast (r1, short_integer_type_node);
5013 4 : ASSERT_TRUE (r1.lower_bound () == minshort
5014 : && r1.upper_bound() == maxshort);
5015 : }
5016 :
5017 : // (unsigned char)[-5,-1] => [251,255].
5018 4 : r0 = rold = int_range<1> (signed_char_type_node, SCHAR (-5), SCHAR (-1));
5019 4 : range_cast (r0, unsigned_char_type_node);
5020 4 : ASSERT_TRUE (r0 == int_range<1> (unsigned_char_type_node,
5021 : UCHAR (251), UCHAR (255)));
5022 4 : range_cast (r0, signed_char_type_node);
5023 4 : ASSERT_TRUE (r0 == rold);
5024 :
5025 : // (signed char)[15, 150] => [-128,-106][15,127].
5026 4 : r0 = rold = int_range<1> (unsigned_char_type_node, UCHAR (15), UCHAR (150));
5027 4 : range_cast (r0, signed_char_type_node);
5028 4 : r1 = int_range<1> (signed_char_type_node, SCHAR (15), SCHAR (127));
5029 4 : r2 = int_range<1> (signed_char_type_node, SCHAR (-128), SCHAR (-106));
5030 4 : r1.union_ (r2);
5031 4 : ASSERT_TRUE (r1 == r0);
5032 4 : range_cast (r0, unsigned_char_type_node);
5033 4 : ASSERT_TRUE (r0 == rold);
5034 :
5035 : // (unsigned char)[-5, 5] => [0,5][251,255].
5036 4 : r0 = rold = int_range<1> (signed_char_type_node, SCHAR (-5), SCHAR (5));
5037 4 : range_cast (r0, unsigned_char_type_node);
5038 4 : r1 = int_range<1> (unsigned_char_type_node, UCHAR (251), UCHAR (255));
5039 4 : r2 = int_range<1> (unsigned_char_type_node, UCHAR (0), UCHAR (5));
5040 4 : r1.union_ (r2);
5041 4 : ASSERT_TRUE (r0 == r1);
5042 4 : range_cast (r0, signed_char_type_node);
5043 4 : ASSERT_TRUE (r0 == rold);
5044 :
5045 : // (unsigned char)[-5,5] => [0,5][251,255].
5046 4 : r0 = int_range<1> (integer_type_node, INT (-5), INT (5));
5047 4 : range_cast (r0, unsigned_char_type_node);
5048 4 : r1 = int_range<1> (unsigned_char_type_node, UCHAR (0), UCHAR (5));
5049 4 : r1.union_ (int_range<1> (unsigned_char_type_node, UCHAR (251), UCHAR (255)));
5050 4 : ASSERT_TRUE (r0 == r1);
5051 :
5052 : // (unsigned char)[5U,1974U] => [0,255].
5053 4 : r0 = int_range<1> (unsigned_type_node, UINT (5), UINT (1974));
5054 4 : range_cast (r0, unsigned_char_type_node);
5055 4 : ASSERT_TRUE (r0 == int_range<1> (unsigned_char_type_node, UCHAR (0), UCHAR (255)));
5056 4 : range_cast (r0, integer_type_node);
5057 : // Going to a wider range should not sign extend.
5058 4 : ASSERT_TRUE (r0 == int_range<1> (integer_type_node, INT (0), INT (255)));
5059 :
5060 : // (unsigned char)[-350,15] => [0,255].
5061 4 : r0 = int_range<1> (integer_type_node, INT (-350), INT (15));
5062 4 : range_cast (r0, unsigned_char_type_node);
5063 4 : ASSERT_TRUE (r0 == (int_range<1>
5064 : (unsigned_char_type_node,
5065 : min_limit (unsigned_char_type_node),
5066 : max_limit (unsigned_char_type_node))));
5067 :
5068 : // Casting [-120,20] from signed char to unsigned short.
5069 : // => [0, 20][0xff88, 0xffff].
5070 4 : r0 = int_range<1> (signed_char_type_node, SCHAR (-120), SCHAR (20));
5071 4 : range_cast (r0, short_unsigned_type_node);
5072 4 : r1 = int_range<1> (short_unsigned_type_node, UINT16 (0), UINT16 (20));
5073 8 : r2 = int_range<1> (short_unsigned_type_node,
5074 12 : UINT16 (0xff88), UINT16 (0xffff));
5075 4 : r1.union_ (r2);
5076 4 : ASSERT_TRUE (r0 == r1);
5077 : // A truncating cast back to signed char will work because [-120, 20]
5078 : // is representable in signed char.
5079 4 : range_cast (r0, signed_char_type_node);
5080 4 : ASSERT_TRUE (r0 == int_range<1> (signed_char_type_node,
5081 : SCHAR (-120), SCHAR (20)));
5082 :
5083 : // unsigned char -> signed short
5084 : // (signed short)[(unsigned char)25, (unsigned char)250]
5085 : // => [(signed short)25, (signed short)250]
5086 4 : r0 = rold = int_range<1> (unsigned_char_type_node, UCHAR (25), UCHAR (250));
5087 4 : range_cast (r0, short_integer_type_node);
5088 4 : r1 = int_range<1> (short_integer_type_node, INT16 (25), INT16 (250));
5089 4 : ASSERT_TRUE (r0 == r1);
5090 4 : range_cast (r0, unsigned_char_type_node);
5091 4 : ASSERT_TRUE (r0 == rold);
5092 :
5093 : // Test casting a wider signed [-MIN,MAX] to a narrower unsigned.
5094 8 : r0 = int_range<1> (long_long_integer_type_node,
5095 4 : min_limit (long_long_integer_type_node),
5096 8 : max_limit (long_long_integer_type_node));
5097 4 : range_cast (r0, short_unsigned_type_node);
5098 8 : r1 = int_range<1> (short_unsigned_type_node,
5099 4 : min_limit (short_unsigned_type_node),
5100 8 : max_limit (short_unsigned_type_node));
5101 4 : ASSERT_TRUE (r0 == r1);
5102 :
5103 : // Casting NONZERO to a narrower type will wrap/overflow so
5104 : // it's just the entire range for the narrower type.
5105 : //
5106 : // "NOT 0 at signed 32-bits" ==> [-MIN_32,-1][1, +MAX_32]. This is
5107 : // is outside of the range of a smaller range, return the full
5108 : // smaller range.
5109 4 : if (TYPE_PRECISION (integer_type_node)
5110 4 : > TYPE_PRECISION (short_integer_type_node))
5111 : {
5112 4 : r0.set_nonzero (integer_type_node);
5113 4 : range_cast (r0, short_integer_type_node);
5114 8 : r1 = int_range<1> (short_integer_type_node,
5115 4 : min_limit (short_integer_type_node),
5116 8 : max_limit (short_integer_type_node));
5117 4 : ASSERT_TRUE (r0 == r1);
5118 : }
5119 :
5120 : // Casting NONZERO from a narrower signed to a wider signed.
5121 : //
5122 : // NONZERO signed 16-bits is [-MIN_16,-1][1, +MAX_16].
5123 : // Converting this to 32-bits signed is [-MIN_16,-1][1, +MAX_16].
5124 4 : r0.set_nonzero (short_integer_type_node);
5125 4 : range_cast (r0, integer_type_node);
5126 4 : r1 = int_range<1> (integer_type_node, INT (-32768), INT (-1));
5127 4 : r2 = int_range<1> (integer_type_node, INT (1), INT (32767));
5128 4 : r1.union_ (r2);
5129 4 : ASSERT_TRUE (r0 == r1);
5130 4 : }
5131 :
5132 : static void
5133 4 : range_op_lshift_tests ()
5134 : {
5135 : // Test that 0x808.... & 0x8.... still contains 0x8....
5136 : // for a large set of numbers.
5137 4 : {
5138 4 : int_range_max res;
5139 4 : tree big_type = long_long_unsigned_type_node;
5140 4 : unsigned big_prec = TYPE_PRECISION (big_type);
5141 : // big_num = 0x808,0000,0000,0000
5142 4 : wide_int big_num = wi::lshift (wi::uhwi (0x808, big_prec),
5143 8 : wi::uhwi (48, big_prec));
5144 8 : op_bitwise_and.fold_range (res, big_type,
5145 8 : int_range <1> (big_type),
5146 8 : int_range <1> (big_type, big_num, big_num));
5147 : // val = 0x8,0000,0000,0000
5148 4 : wide_int val = wi::lshift (wi::uhwi (8, big_prec),
5149 8 : wi::uhwi (48, big_prec));
5150 4 : ASSERT_TRUE (res.contains_p (val));
5151 4 : }
5152 :
5153 4 : if (TYPE_PRECISION (unsigned_type_node) > 31)
5154 : {
5155 : // unsigned VARYING = op1 << 1 should be VARYING.
5156 4 : int_range<2> lhs (unsigned_type_node);
5157 4 : int_range<2> shift (unsigned_type_node, INT (1), INT (1));
5158 4 : int_range_max op1;
5159 4 : op_lshift.op1_range (op1, unsigned_type_node, lhs, shift);
5160 4 : ASSERT_TRUE (op1.varying_p ());
5161 :
5162 : // 0 = op1 << 1 should be [0,0], [0x8000000, 0x8000000].
5163 4 : int_range<2> zero (unsigned_type_node, UINT (0), UINT (0));
5164 4 : op_lshift.op1_range (op1, unsigned_type_node, zero, shift);
5165 4 : ASSERT_TRUE (op1.num_pairs () == 2);
5166 : // Remove the [0,0] range.
5167 4 : op1.intersect (zero);
5168 4 : ASSERT_TRUE (op1.num_pairs () == 1);
5169 : // op1 << 1 should be [0x8000,0x8000] << 1,
5170 : // which should result in [0,0].
5171 4 : int_range_max result;
5172 4 : op_lshift.fold_range (result, unsigned_type_node, op1, shift);
5173 4 : ASSERT_TRUE (result == zero);
5174 4 : }
5175 : // signed VARYING = op1 << 1 should be VARYING.
5176 4 : if (TYPE_PRECISION (integer_type_node) > 31)
5177 : {
5178 : // unsigned VARYING = op1 << 1 should be VARYING.
5179 4 : int_range<2> lhs (integer_type_node);
5180 4 : int_range<2> shift (integer_type_node, INT (1), INT (1));
5181 4 : int_range_max op1;
5182 4 : op_lshift.op1_range (op1, integer_type_node, lhs, shift);
5183 4 : ASSERT_TRUE (op1.varying_p ());
5184 :
5185 : // 0 = op1 << 1 should be [0,0], [0x8000000, 0x8000000].
5186 4 : int_range<2> zero (integer_type_node, INT (0), INT (0));
5187 4 : op_lshift.op1_range (op1, integer_type_node, zero, shift);
5188 4 : ASSERT_TRUE (op1.num_pairs () == 2);
5189 : // Remove the [0,0] range.
5190 4 : op1.intersect (zero);
5191 4 : ASSERT_TRUE (op1.num_pairs () == 1);
5192 : // op1 << 1 should be [0x8000,0x8000] << 1,
5193 : // which should result in [0,0].
5194 4 : int_range_max result;
5195 4 : op_lshift.fold_range (result, unsigned_type_node, op1, shift);
5196 4 : ASSERT_TRUE (result == zero);
5197 4 : }
5198 4 : }
5199 :
5200 : static void
5201 4 : range_op_rshift_tests ()
5202 : {
5203 : // unsigned: [3, MAX] = OP1 >> 1
5204 4 : {
5205 4 : int_range_max lhs (unsigned_type_node,
5206 4 : UINT (3), max_limit (unsigned_type_node));
5207 4 : int_range_max one (unsigned_type_node,
5208 8 : wi::one (TYPE_PRECISION (unsigned_type_node)),
5209 8 : wi::one (TYPE_PRECISION (unsigned_type_node)));
5210 4 : int_range_max op1;
5211 4 : op_rshift.op1_range (op1, unsigned_type_node, lhs, one);
5212 4 : ASSERT_FALSE (op1.contains_p (UINT (3)));
5213 4 : }
5214 :
5215 : // signed: [3, MAX] = OP1 >> 1
5216 4 : {
5217 4 : int_range_max lhs (integer_type_node,
5218 4 : INT (3), max_limit (integer_type_node));
5219 4 : int_range_max one (integer_type_node, INT (1), INT (1));
5220 4 : int_range_max op1;
5221 4 : op_rshift.op1_range (op1, integer_type_node, lhs, one);
5222 4 : ASSERT_FALSE (op1.contains_p (INT (-2)));
5223 4 : }
5224 :
5225 : // This is impossible, so OP1 should be [].
5226 : // signed: [MIN, MIN] = OP1 >> 1
5227 4 : {
5228 4 : int_range_max lhs (integer_type_node,
5229 4 : min_limit (integer_type_node),
5230 4 : min_limit (integer_type_node));
5231 4 : int_range_max one (integer_type_node, INT (1), INT (1));
5232 4 : int_range_max op1;
5233 4 : op_rshift.op1_range (op1, integer_type_node, lhs, one);
5234 4 : ASSERT_TRUE (op1.undefined_p ());
5235 4 : }
5236 :
5237 : // signed: ~[-1] = OP1 >> 31
5238 4 : if (TYPE_PRECISION (integer_type_node) > 31)
5239 : {
5240 4 : int_range_max lhs (integer_type_node, INT (-1), INT (-1), VR_ANTI_RANGE);
5241 4 : int_range_max shift (integer_type_node, INT (31), INT (31));
5242 4 : int_range_max op1;
5243 4 : op_rshift.op1_range (op1, integer_type_node, lhs, shift);
5244 4 : int_range_max negatives = range_negatives (integer_type_node);
5245 4 : negatives.intersect (op1);
5246 4 : ASSERT_TRUE (negatives.undefined_p ());
5247 4 : }
5248 4 : }
5249 :
5250 : static void
5251 4 : range_op_bitwise_and_tests ()
5252 : {
5253 4 : int_range_max res;
5254 4 : wide_int min = min_limit (integer_type_node);
5255 4 : wide_int max = max_limit (integer_type_node);
5256 4 : wide_int tiny = wi::add (min, wi::one (TYPE_PRECISION (integer_type_node)));
5257 4 : int_range_max i1 (integer_type_node, tiny, max);
5258 4 : int_range_max i2 (integer_type_node, INT (255), INT (255));
5259 :
5260 : // [MIN+1, MAX] = OP1 & 255: OP1 is VARYING
5261 4 : op_bitwise_and.op1_range (res, integer_type_node, i1, i2);
5262 4 : ASSERT_TRUE (res == int_range<1> (integer_type_node));
5263 :
5264 : // VARYING = OP1 & 255: OP1 is VARYING
5265 4 : i1 = int_range<1> (integer_type_node);
5266 4 : op_bitwise_and.op1_range (res, integer_type_node, i1, i2);
5267 4 : ASSERT_TRUE (res == int_range<1> (integer_type_node));
5268 :
5269 : // For 0 = x & MASK, x is ~MASK.
5270 4 : {
5271 4 : int_range<2> zero (integer_type_node, INT (0), INT (0));
5272 4 : int_range<2> mask = int_range<2> (integer_type_node, INT (7), INT (7));
5273 4 : op_bitwise_and.op1_range (res, integer_type_node, zero, mask);
5274 4 : wide_int inv = wi::shwi (~7U, TYPE_PRECISION (integer_type_node));
5275 4 : ASSERT_TRUE (res.get_nonzero_bits () == inv);
5276 4 : }
5277 :
5278 : // (NONZERO | X) is nonzero.
5279 4 : i1.set_nonzero (integer_type_node);
5280 4 : i2.set_varying (integer_type_node);
5281 4 : op_bitwise_or.fold_range (res, integer_type_node, i1, i2);
5282 4 : ASSERT_TRUE (res.nonzero_p ());
5283 :
5284 : // (NEGATIVE | X) is nonzero.
5285 4 : i1 = int_range<1> (integer_type_node, INT (-5), INT (-3));
5286 4 : i2.set_varying (integer_type_node);
5287 4 : op_bitwise_or.fold_range (res, integer_type_node, i1, i2);
5288 4 : ASSERT_FALSE (res.contains_p (INT (0)));
5289 4 : }
5290 :
5291 : static void
5292 4 : range_relational_tests ()
5293 : {
5294 4 : int_range<2> lhs (unsigned_char_type_node);
5295 4 : int_range<2> op1 (unsigned_char_type_node, UCHAR (8), UCHAR (10));
5296 4 : int_range<2> op2 (unsigned_char_type_node, UCHAR (20), UCHAR (20));
5297 :
5298 : // Never wrapping additions mean LHS > OP1.
5299 4 : relation_kind code = op_plus.lhs_op1_relation (lhs, op1, op2, VREL_VARYING);
5300 4 : ASSERT_TRUE (code == VREL_GT);
5301 :
5302 : // Most wrapping additions mean nothing...
5303 4 : op1 = int_range<2> (unsigned_char_type_node, UCHAR (8), UCHAR (10));
5304 4 : op2 = int_range<2> (unsigned_char_type_node, UCHAR (0), UCHAR (255));
5305 4 : code = op_plus.lhs_op1_relation (lhs, op1, op2, VREL_VARYING);
5306 4 : ASSERT_TRUE (code == VREL_VARYING);
5307 :
5308 : // However, always wrapping additions mean LHS < OP1.
5309 4 : op1 = int_range<2> (unsigned_char_type_node, UCHAR (1), UCHAR (255));
5310 4 : op2 = int_range<2> (unsigned_char_type_node, UCHAR (255), UCHAR (255));
5311 4 : code = op_plus.lhs_op1_relation (lhs, op1, op2, VREL_VARYING);
5312 4 : ASSERT_TRUE (code == VREL_LT);
5313 4 : }
5314 :
5315 : void
5316 4 : range_op_tests ()
5317 : {
5318 4 : range_op_rshift_tests ();
5319 4 : range_op_lshift_tests ();
5320 4 : range_op_bitwise_and_tests ();
5321 4 : range_op_cast_tests ();
5322 4 : range_relational_tests ();
5323 :
5324 4 : extern void range_op_float_tests ();
5325 4 : range_op_float_tests ();
5326 4 : }
5327 :
5328 : } // namespace selftest
5329 :
5330 : #endif // CHECKING_P
|
