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 : operator_equal op_equal;
55 : operator_not_equal op_not_equal;
56 : operator_lt op_lt;
57 : operator_le op_le;
58 : operator_gt op_gt;
59 : operator_ge op_ge;
60 : operator_identity op_ident;
61 : operator_cst op_cst;
62 : operator_cast op_cast;
63 : operator_view op_view;
64 : operator_plus op_plus;
65 : operator_abs op_abs;
66 : operator_minus op_minus;
67 : operator_negate op_negate;
68 : operator_mult op_mult;
69 : operator_addr_expr op_addr;
70 : operator_bitwise_not op_bitwise_not;
71 : operator_bitwise_xor op_bitwise_xor;
72 : operator_bitwise_and op_bitwise_and;
73 : operator_bitwise_or op_bitwise_or;
74 : operator_min op_min;
75 : operator_max op_max;
76 :
77 : // Instantaite a range operator table.
78 : range_op_table operator_table;
79 :
80 : // Invoke the initialization routines for each class of range.
81 :
82 284591 : range_op_table::range_op_table ()
83 : {
84 284591 : initialize_integral_ops ();
85 284591 : initialize_pointer_ops ();
86 284591 : initialize_float_ops ();
87 :
88 284591 : set (EQ_EXPR, op_equal);
89 284591 : set (NE_EXPR, op_not_equal);
90 284591 : set (LT_EXPR, op_lt);
91 284591 : set (LE_EXPR, op_le);
92 284591 : set (GT_EXPR, op_gt);
93 284591 : set (GE_EXPR, op_ge);
94 284591 : set (SSA_NAME, op_ident);
95 284591 : set (PAREN_EXPR, op_ident);
96 284591 : set (OBJ_TYPE_REF, op_ident);
97 284591 : set (REAL_CST, op_cst);
98 284591 : set (INTEGER_CST, op_cst);
99 284591 : set (NOP_EXPR, op_cast);
100 284591 : set (CONVERT_EXPR, op_cast);
101 284591 : set (VIEW_CONVERT_EXPR, op_view);
102 284591 : set (FLOAT_EXPR, op_cast);
103 284591 : set (FIX_TRUNC_EXPR, op_cast);
104 284591 : set (PLUS_EXPR, op_plus);
105 284591 : set (ABS_EXPR, op_abs);
106 284591 : set (MINUS_EXPR, op_minus);
107 284591 : set (NEGATE_EXPR, op_negate);
108 284591 : set (MULT_EXPR, op_mult);
109 284591 : set (ADDR_EXPR, op_addr);
110 284591 : set (BIT_NOT_EXPR, op_bitwise_not);
111 284591 : set (BIT_XOR_EXPR, op_bitwise_xor);
112 284591 : set (BIT_AND_EXPR, op_bitwise_and);
113 284591 : set (BIT_IOR_EXPR, op_bitwise_or);
114 284591 : set (MIN_EXPR, op_min);
115 284591 : set (MAX_EXPR, op_max);
116 284591 : }
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 1684823172 : range_op_handler::range_op_handler ()
125 : {
126 1684823172 : m_operator = &default_operator;
127 1684823172 : }
128 :
129 : // Create a range_op_handler for CODE. Use a default operatoer if CODE
130 : // does not have an entry.
131 :
132 4078624931 : range_op_handler::range_op_handler (unsigned code)
133 : {
134 4078624931 : m_operator = operator_table[code];
135 4078624931 : if (!m_operator)
136 806522277 : m_operator = &default_operator;
137 4078624931 : }
138 :
139 : // Return TRUE if this handler has a non-default operator.
140 :
141 5904181358 : range_op_handler::operator bool () const
142 : {
143 5904181358 : return m_operator != &default_operator;
144 : }
145 :
146 : // Return a pointer to the range operator assocaited with this handler.
147 : // If it is a default operator, return NULL.
148 : // This is the equivalent of indexing the range table.
149 :
150 : range_operator *
151 986816889 : range_op_handler::range_op () const
152 : {
153 986816889 : if (m_operator != &default_operator)
154 986816889 : return m_operator;
155 : return NULL;
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 661655799 : dispatch_trio (unsigned lhs, unsigned op1, unsigned op2)
164 : {
165 661655799 : 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 : const unsigned RO_III = dispatch_trio (VR_IRANGE, VR_IRANGE, VR_IRANGE);
175 : const unsigned RO_IFI = dispatch_trio (VR_IRANGE, VR_FRANGE, VR_IRANGE);
176 : const unsigned RO_IFF = dispatch_trio (VR_IRANGE, VR_FRANGE, VR_FRANGE);
177 : const unsigned RO_FFF = dispatch_trio (VR_FRANGE, VR_FRANGE, VR_FRANGE);
178 : const unsigned RO_FIF = dispatch_trio (VR_FRANGE, VR_IRANGE, VR_FRANGE);
179 : const unsigned RO_FII = dispatch_trio (VR_FRANGE, VR_IRANGE, VR_IRANGE);
180 : const unsigned RO_PPP = dispatch_trio (VR_PRANGE, VR_PRANGE, VR_PRANGE);
181 : const unsigned RO_PPI = dispatch_trio (VR_PRANGE, VR_PRANGE, VR_IRANGE);
182 : const unsigned RO_IPP = dispatch_trio (VR_IRANGE, VR_PRANGE, VR_PRANGE);
183 : const unsigned RO_IPI = dispatch_trio (VR_IRANGE, VR_PRANGE, VR_IRANGE);
184 : const unsigned RO_PIP = dispatch_trio (VR_PRANGE, VR_IRANGE, VR_PRANGE);
185 : 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 661655799 : range_op_handler::dispatch_kind (const vrange &lhs, const vrange &op1,
191 : const vrange& op2) const
192 : {
193 661655799 : return dispatch_trio (lhs.m_discriminator, op1.m_discriminator,
194 661655799 : 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 294611723 : range_op_handler::fold_range (vrange &r, tree type,
224 : const vrange &lh,
225 : const vrange &rh,
226 : relation_trio rel) const
227 : {
228 294611723 : gcc_checking_assert (m_operator);
229 : #if CHECKING_P
230 294611723 : if (!lh.undefined_p () && !rh.undefined_p ())
231 289145907 : gcc_assert (m_operator->operand_check_p (type, lh.type (), rh.type ()));
232 : #endif
233 294611723 : switch (dispatch_kind (r, lh, rh))
234 : {
235 224409286 : case RO_III:
236 224409286 : return m_operator->fold_range (as_a <irange> (r), type,
237 : as_a <irange> (lh),
238 224409286 : as_a <irange> (rh), rel);
239 355278 : case RO_IFI:
240 355278 : return m_operator->fold_range (as_a <irange> (r), type,
241 : as_a <frange> (lh),
242 355278 : as_a <irange> (rh), rel);
243 2630079 : case RO_IFF:
244 2630079 : return m_operator->fold_range (as_a <irange> (r), type,
245 : as_a <frange> (lh),
246 2630079 : as_a <frange> (rh), rel);
247 7565534 : case RO_FFF:
248 7565534 : return m_operator->fold_range (as_a <frange> (r), type,
249 : as_a <frange> (lh),
250 7565534 : 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 912380 : case RO_FIF:
256 912380 : return m_operator->fold_range (as_a <frange> (r), type,
257 : as_a <irange> (lh),
258 912380 : as_a <frange> (rh), rel);
259 17941192 : case RO_PPP:
260 17941192 : return m_operator->fold_range (as_a <prange> (r), type,
261 : as_a <prange> (lh),
262 17941192 : as_a <prange> (rh), rel);
263 9673438 : case RO_PPI:
264 9673438 : return m_operator->fold_range (as_a <prange> (r), type,
265 : as_a <prange> (lh),
266 9673438 : as_a <irange> (rh), rel);
267 18371126 : case RO_IPP:
268 18371126 : return m_operator->fold_range (as_a <irange> (r), type,
269 : as_a <prange> (lh),
270 18371126 : as_a <prange> (rh), rel);
271 1930430 : case RO_PIP:
272 1930430 : return m_operator->fold_range (as_a <prange> (r), type,
273 : as_a <irange> (lh),
274 1930430 : as_a <prange> (rh), rel);
275 10822948 : case RO_IPI:
276 10822948 : return m_operator->fold_range (as_a <irange> (r), type,
277 : as_a <prange> (lh),
278 10822948 : 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 93104010 : range_op_handler::op1_range (vrange &r, tree type,
288 : const vrange &lhs,
289 : const vrange &op2,
290 : relation_trio rel) const
291 : {
292 93104010 : gcc_checking_assert (m_operator);
293 93104010 : if (lhs.undefined_p ())
294 : return false;
295 : #if CHECKING_P
296 93102779 : if (!op2.undefined_p ())
297 93102663 : gcc_assert (m_operator->operand_check_p (lhs.type (), type, op2.type ()));
298 : #endif
299 93102779 : switch (dispatch_kind (r, lhs, op2))
300 : {
301 80244513 : case RO_III:
302 80244513 : return m_operator->op1_range (as_a <irange> (r), type,
303 : as_a <irange> (lhs),
304 80244513 : as_a <irange> (op2), rel);
305 244832 : case RO_IFI:
306 244832 : return m_operator->op1_range (as_a <irange> (r), type,
307 : as_a <frange> (lhs),
308 244832 : as_a <irange> (op2), rel);
309 833782 : case RO_PPP:
310 833782 : return m_operator->op1_range (as_a <prange> (r), type,
311 : as_a <prange> (lhs),
312 833782 : as_a <prange> (op2), rel);
313 8647430 : case RO_PIP:
314 8647430 : return m_operator->op1_range (as_a <prange> (r), type,
315 : as_a <irange> (lhs),
316 8647430 : as_a <prange> (op2), rel);
317 489352 : case RO_PPI:
318 489352 : return m_operator->op1_range (as_a <prange> (r), type,
319 : as_a <prange> (lhs),
320 489352 : as_a <irange> (op2), rel);
321 247092 : case RO_IPI:
322 247092 : return m_operator->op1_range (as_a <irange> (r), type,
323 : as_a <prange> (lhs),
324 247092 : as_a <irange> (op2), rel);
325 1484663 : case RO_FIF:
326 1484663 : return m_operator->op1_range (as_a <frange> (r), type,
327 : as_a <irange> (lhs),
328 1484663 : as_a <frange> (op2), rel);
329 911115 : case RO_FFF:
330 911115 : return m_operator->op1_range (as_a <frange> (r), type,
331 : as_a <frange> (lhs),
332 911115 : 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 27076154 : range_op_handler::op2_range (vrange &r, tree type,
342 : const vrange &lhs,
343 : const vrange &op1,
344 : relation_trio rel) const
345 : {
346 27076154 : gcc_checking_assert (m_operator);
347 27076154 : if (lhs.undefined_p ())
348 : return false;
349 : #if CHECKING_P
350 27076136 : if (!op1.undefined_p ())
351 27076018 : gcc_assert (m_operator->operand_check_p (lhs.type (), op1.type (), type));
352 : #endif
353 27076136 : switch (dispatch_kind (r, lhs, op1))
354 : {
355 20919887 : case RO_III:
356 20919887 : return m_operator->op2_range (as_a <irange> (r), type,
357 : as_a <irange> (lhs),
358 20919887 : as_a <irange> (op1), rel);
359 5006549 : case RO_PIP:
360 5006549 : return m_operator->op2_range (as_a <prange> (r), type,
361 : as_a <irange> (lhs),
362 5006549 : as_a <prange> (op1), rel);
363 216584 : case RO_IPP:
364 216584 : return m_operator->op2_range (as_a <irange> (r), type,
365 : as_a <prange> (lhs),
366 216584 : as_a <prange> (op1), rel);
367 560160 : case RO_FIF:
368 560160 : return m_operator->op2_range (as_a <frange> (r), type,
369 : as_a <irange> (lhs),
370 560160 : as_a <frange> (op1), rel);
371 372812 : case RO_FFF:
372 372812 : return m_operator->op2_range (as_a <frange> (r), type,
373 : as_a <frange> (lhs),
374 372812 : 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 126612710 : range_op_handler::lhs_op1_relation (const vrange &lhs,
384 : const vrange &op1,
385 : const vrange &op2,
386 : relation_kind rel) const
387 : {
388 126612710 : gcc_checking_assert (m_operator);
389 126612710 : switch (dispatch_kind (lhs, op1, op2))
390 : {
391 101454062 : case RO_III:
392 101454062 : return m_operator->lhs_op1_relation (as_a <irange> (lhs),
393 : as_a <irange> (op1),
394 101454062 : as_a <irange> (op2), rel);
395 1448061 : case RO_PPP:
396 1448061 : return m_operator->lhs_op1_relation (as_a <prange> (lhs),
397 : as_a <prange> (op1),
398 1448061 : as_a <prange> (op2), rel);
399 6123065 : case RO_IPP:
400 6123065 : return m_operator->lhs_op1_relation (as_a <irange> (lhs),
401 : as_a <prange> (op1),
402 6123065 : as_a <prange> (op2), rel);
403 1442620 : case RO_PII:
404 1442620 : return m_operator->lhs_op1_relation (as_a <prange> (lhs),
405 : as_a <irange> (op1),
406 1442620 : as_a <irange> (op2), rel);
407 8414161 : case RO_PPI:
408 8414161 : return m_operator->lhs_op1_relation (as_a <prange> (lhs),
409 : as_a <prange> (op1),
410 8414161 : as_a <irange> (op2), rel);
411 1032708 : case RO_IFF:
412 1032708 : return m_operator->lhs_op1_relation (as_a <irange> (lhs),
413 : as_a <frange> (op1),
414 1032708 : as_a <frange> (op2), rel);
415 5786196 : case RO_FFF:
416 5786196 : return m_operator->lhs_op1_relation (as_a <frange> (lhs),
417 : as_a <frange> (op1),
418 5786196 : 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 37082581 : range_op_handler::lhs_op2_relation (const vrange &lhs,
428 : const vrange &op1,
429 : const vrange &op2,
430 : relation_kind rel) const
431 : {
432 37082581 : gcc_checking_assert (m_operator);
433 37082581 : switch (dispatch_kind (lhs, op1, op2))
434 : {
435 25454230 : case RO_III:
436 25454230 : return m_operator->lhs_op2_relation (as_a <irange> (lhs),
437 : as_a <irange> (op1),
438 25454230 : as_a <irange> (op2), rel);
439 169745 : case RO_IFF:
440 169745 : return m_operator->lhs_op2_relation (as_a <irange> (lhs),
441 : as_a <frange> (op1),
442 169745 : as_a <frange> (op2), rel);
443 3632923 : case RO_FFF:
444 3632923 : return m_operator->lhs_op2_relation (as_a <frange> (lhs),
445 : as_a <frange> (op1),
446 3632923 : 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 83125060 : range_op_handler::op1_op2_relation (const vrange &lhs,
456 : const vrange &op1,
457 : const vrange &op2) const
458 : {
459 83125060 : gcc_checking_assert (m_operator);
460 :
461 83125060 : switch (dispatch_kind (lhs, op1, op2))
462 : {
463 64430407 : case RO_III:
464 64430407 : return m_operator->op1_op2_relation (as_a <irange> (lhs),
465 : as_a <irange> (op1),
466 64430407 : as_a <irange> (op2));
467 :
468 15823813 : case RO_IPP:
469 15823813 : return m_operator->op1_op2_relation (as_a <irange> (lhs),
470 : as_a <prange> (op1),
471 15823813 : as_a <prange> (op2));
472 :
473 1884377 : case RO_IFF:
474 1884377 : return m_operator->op1_op2_relation (as_a <irange> (lhs),
475 : as_a <frange> (op1),
476 1884377 : as_a <frange> (op2));
477 :
478 656035 : case RO_FFF:
479 656035 : return m_operator->op1_op2_relation (as_a <frange> (lhs),
480 : as_a <frange> (op1),
481 656035 : as_a <frange> (op2));
482 :
483 : default:
484 : return VREL_VARYING;
485 : }
486 : }
487 :
488 : bool
489 44810 : range_op_handler::overflow_free_p (const vrange &lh,
490 : const vrange &rh,
491 : relation_trio rel) const
492 : {
493 44810 : gcc_checking_assert (m_operator);
494 44810 : switch (dispatch_kind (lh, lh, rh))
495 : {
496 44810 : case RO_III:
497 44810 : return m_operator->overflow_free_p(as_a <irange> (lh),
498 : as_a <irange> (rh),
499 44810 : rel);
500 : default:
501 : return false;
502 : }
503 : }
504 :
505 : bool
506 9043271 : range_op_handler::operand_check_p (tree t1, tree t2, tree t3) const
507 : {
508 9043271 : gcc_checking_assert (m_operator);
509 9043271 : 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 174352494 : update_known_bitmask (vrange &r, tree_code code,
517 : const vrange &lh, const vrange &rh)
518 : {
519 174352494 : if (r.undefined_p () || lh.undefined_p () || rh.undefined_p ()
520 348700297 : || r.singleton_p ())
521 9376010 : return;
522 :
523 164976484 : widest_int widest_value, widest_mask;
524 164976484 : tree type = r.type ();
525 164976484 : signop sign = TYPE_SIGN (type);
526 164976484 : int prec = TYPE_PRECISION (type);
527 164976484 : irange_bitmask lh_bits = lh.get_bitmask ();
528 164976484 : irange_bitmask rh_bits = rh.get_bitmask ();
529 :
530 164976484 : switch (get_gimple_rhs_class (code))
531 : {
532 54678522 : case GIMPLE_UNARY_RHS:
533 54678522 : bit_value_unop (code, sign, prec, &widest_value, &widest_mask,
534 54678522 : TYPE_SIGN (lh.type ()),
535 54678522 : TYPE_PRECISION (lh.type ()),
536 109357507 : widest_int::from (lh_bits.value (),
537 54678522 : TYPE_SIGN (lh.type ())),
538 109357044 : widest_int::from (lh_bits.mask (),
539 54678522 : TYPE_SIGN (lh.type ())));
540 54678522 : break;
541 110297962 : case GIMPLE_BINARY_RHS:
542 220595924 : bit_value_binop (code, sign, prec, &widest_value, &widest_mask,
543 110297962 : TYPE_SIGN (lh.type ()),
544 110297962 : TYPE_PRECISION (lh.type ()),
545 220596811 : widest_int::from (lh_bits.value (), sign),
546 220596811 : widest_int::from (lh_bits.mask (), sign),
547 110297962 : TYPE_SIGN (rh.type ()),
548 110297962 : TYPE_PRECISION (rh.type ()),
549 220596781 : widest_int::from (rh_bits.value (), sign),
550 220595924 : widest_int::from (rh_bits.mask (), sign));
551 110297962 : break;
552 0 : default:
553 0 : gcc_unreachable ();
554 : }
555 :
556 164976484 : wide_int mask = wide_int::from (widest_mask, prec, sign);
557 329952968 : wide_int value = wide_int::from (widest_value, prec, sign);
558 : // Bitmasks must have the unknown value bits cleared.
559 164976484 : value &= ~mask;
560 329952968 : irange_bitmask bm (value, mask);
561 164976484 : r.update_bitmask (bm);
562 164977421 : }
563 :
564 : // Return the upper limit for a type.
565 :
566 : static inline wide_int
567 17298057 : max_limit (const_tree type)
568 : {
569 17298057 : return irange_val_max (type);
570 : }
571 :
572 : // Return the lower limit for a type.
573 :
574 : static inline wide_int
575 20242619 : min_limit (const_tree type)
576 : {
577 20242619 : 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 4919012 : get_shift_range (irange &r, tree type, const irange &op)
586 : {
587 4919012 : if (op.undefined_p ())
588 : return false;
589 :
590 : // Build valid range and intersect it with the shift range.
591 4918531 : r.set (op.type (),
592 9837062 : wi::shwi (0, TYPE_PRECISION (op.type ())),
593 4918531 : wi::shwi (TYPE_PRECISION (type) - 1, TYPE_PRECISION (op.type ())));
594 4918531 : r.intersect (op);
595 :
596 : // If there are no valid ranges in the shift range, returned false.
597 4918531 : 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 53827 : 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 53827 : int_range_max tmp;
629 107654 : widest_int lh_range = wi::sub (widest_int::from (lh_ub, TYPE_SIGN (type)),
630 107654 : widest_int::from (lh_lb, TYPE_SIGN (type)));
631 : // if there are 1 to 8 values in the LH range, split them up.
632 53827 : r.set_undefined ();
633 107654 : if (lh_range >= 0 && lh_range < limit)
634 : {
635 15929 : for (unsigned x = 0; x <= lh_range; x++)
636 : {
637 10875 : wide_int val = lh_lb + x;
638 10875 : wi_fold (tmp, type, val, val, val, val);
639 10875 : r.union_ (tmp);
640 10875 : }
641 : }
642 : // Otherwise just call wi_fold.
643 : else
644 48773 : wi_fold (r, type, lh_lb, lh_ub, lh_lb, lh_ub);
645 53827 : }
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 147133510 : 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 147133510 : int_range_max tmp;
659 294267020 : widest_int rh_range = wi::sub (widest_int::from (rh_ub, TYPE_SIGN (type)),
660 294267020 : widest_int::from (rh_lb, TYPE_SIGN (type)));
661 294267020 : widest_int lh_range = wi::sub (widest_int::from (lh_ub, TYPE_SIGN (type)),
662 294267020 : 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 147133510 : if (rh_range > 0 && rh_range < 4)
666 : {
667 5053960 : wi_fold_in_parts (r, type, lh_lb, lh_ub, rh_lb, rh_lb);
668 5053960 : if (rh_range > 1)
669 : {
670 569230 : wi_fold_in_parts (tmp, type, lh_lb, lh_ub, rh_lb + 1, rh_lb + 1);
671 569230 : r.union_ (tmp);
672 569230 : if (rh_range == 3)
673 : {
674 347345 : wi_fold_in_parts (tmp, type, lh_lb, lh_ub, rh_lb + 2, rh_lb + 2);
675 347345 : r.union_ (tmp);
676 : }
677 : }
678 5053960 : wi_fold_in_parts (tmp, type, lh_lb, lh_ub, rh_ub, rh_ub);
679 5053960 : 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 142079550 : else if (lh_range > 0 && lh_range < 4)
684 : {
685 9977566 : wi_fold (r, type, lh_lb, lh_lb, rh_lb, rh_ub);
686 9977566 : if (lh_range > 1)
687 : {
688 1817210 : wi_fold (tmp, type, lh_lb + 1, lh_lb + 1, rh_lb, rh_ub);
689 1817202 : r.union_ (tmp);
690 1817202 : if (lh_range == 3)
691 : {
692 773789 : wi_fold (tmp, type, lh_lb + 2, lh_lb + 2, rh_lb, rh_ub);
693 773785 : r.union_ (tmp);
694 : }
695 : }
696 9977566 : wi_fold (tmp, type, lh_ub, lh_ub, rh_lb, rh_ub);
697 9977566 : r.union_ (tmp);
698 : }
699 : // Otherwise just call wi_fold.
700 : else
701 132101984 : wi_fold (r, type, lh_lb, lh_ub, rh_lb, rh_ub);
702 147133858 : }
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 103467121 : range_operator::fold_range (irange &r, tree type,
709 : const irange &lh,
710 : const irange &rh,
711 : relation_trio trio) const
712 : {
713 103467121 : gcc_checking_assert (r.supports_type_p (type));
714 103467121 : if (empty_range_varying (r, type, lh, rh))
715 46348 : return true;
716 :
717 103420773 : relation_kind rel = trio.op1_op2 ();
718 103420773 : unsigned num_lh = lh.num_pairs ();
719 103420773 : 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 103421143 : if (relation_equiv_p (rel) && lh == rh)
724 : {
725 50762 : int_range_max tmp;
726 50762 : r.set_undefined ();
727 89888 : for (unsigned x = 0; x < num_lh; ++x)
728 : {
729 : // If the number of subranges is too high, limit subrange creation.
730 53827 : unsigned limit = (r.num_pairs () > 32) ? 0 : 8;
731 53827 : wide_int lh_lb = lh.lower_bound (x);
732 53827 : wide_int lh_ub = lh.upper_bound (x);
733 53827 : wi_fold_in_parts_equiv (tmp, type, lh_lb, lh_ub, limit);
734 53827 : r.union_ (tmp);
735 53827 : if (r.varying_p ())
736 : break;
737 53827 : }
738 50762 : op1_op2_relation_effect (r, type, lh, rh, rel);
739 50762 : update_bitmask (r, lh, rh);
740 50762 : return true;
741 50762 : }
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 103370011 : if ((num_lh == 1 && num_rh == 1) || num_lh * num_rh > 12)
747 : {
748 85592546 : wi_fold_in_parts (r, type, lh.lower_bound (), lh.upper_bound (),
749 171182816 : rh.lower_bound (), rh.upper_bound ());
750 85591408 : op1_op2_relation_effect (r, type, lh, rh, rel);
751 85591408 : update_bitmask (r, lh, rh);
752 85591408 : return true;
753 : }
754 :
755 17778603 : int_range_max tmp;
756 17778603 : r.set_undefined ();
757 55772035 : for (unsigned x = 0; x < num_lh; ++x)
758 88511039 : for (unsigned y = 0; y < num_rh; ++y)
759 : {
760 50517607 : wide_int lh_lb = lh.lower_bound (x);
761 50517607 : wide_int lh_ub = lh.upper_bound (x);
762 50517607 : wide_int rh_lb = rh.lower_bound (y);
763 50517607 : wide_int rh_ub = rh.upper_bound (y);
764 50517607 : wi_fold_in_parts (tmp, type, lh_lb, lh_ub, rh_lb, rh_ub);
765 50517607 : r.union_ (tmp);
766 50517607 : if (r.varying_p ())
767 : {
768 4035648 : op1_op2_relation_effect (r, type, lh, rh, rel);
769 4035648 : update_bitmask (r, lh, rh);
770 4035648 : return true;
771 : }
772 50518696 : }
773 13742955 : op1_op2_relation_effect (r, type, lh, rh, rel);
774 13742955 : update_bitmask (r, lh, rh);
775 13742955 : return true;
776 17778603 : }
777 :
778 :
779 : bool
780 71439 : range_operator::fold_range (frange &, tree, const irange &,
781 : const frange &, relation_trio) const
782 : {
783 71439 : return false;
784 : }
785 :
786 : bool
787 1553 : range_operator::op1_range (irange &, tree, const frange &,
788 : const irange &, relation_trio) const
789 : {
790 1553 : return false;
791 : }
792 :
793 :
794 :
795 : // The default for op1_range is to return false.
796 :
797 : bool
798 713048 : 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 713048 : return false;
805 : }
806 :
807 : // The default for op2_range is to return false.
808 :
809 : bool
810 573192 : 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 573192 : return false;
817 : }
818 :
819 : // The default relation routines return VREL_VARYING.
820 :
821 : relation_kind
822 23486619 : 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 23486619 : return VREL_VARYING;
828 : }
829 :
830 : relation_kind
831 17225829 : 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 17225829 : return VREL_VARYING;
837 : }
838 :
839 : relation_kind
840 14545719 : 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 14545719 : return VREL_VARYING;
845 : }
846 :
847 : // Default is no relation affects the LHS.
848 :
849 : bool
850 84683728 : 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 84683728 : 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 6281 : range_operator::update_bitmask (irange &, const irange &,
873 : const irange &) const
874 : {
875 6281 : }
876 :
877 : // Check that operand types are OK. Default to always OK.
878 :
879 : bool
880 122862549 : range_operator::operand_check_p (tree, tree, tree) const
881 : {
882 122862549 : 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 42475968 : value_range_from_overflowed_bounds (irange &r, tree type,
890 : const wide_int &wmin,
891 : const wide_int &wmax)
892 : {
893 42475968 : const signop sgn = TYPE_SIGN (type);
894 42475968 : const unsigned int prec = TYPE_PRECISION (type);
895 :
896 42475968 : wide_int tmin = wide_int::from (wmin, prec, sgn);
897 42475968 : wide_int tmax = wide_int::from (wmax, prec, sgn);
898 :
899 42475968 : bool covers = false;
900 42475968 : wide_int tem = tmin;
901 42475968 : tmin = tmax + 1;
902 42475968 : if (wi::cmp (tmin, tmax, sgn) < 0)
903 2779911 : covers = true;
904 42475968 : tmax = tem - 1;
905 42475968 : 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 39742963 : if (covers || wi::cmp (tmin, tmax, sgn) > 0)
912 28895605 : r.set_varying (type);
913 : else
914 13580363 : r.set (type, tmin, tmax, VR_ANTI_RANGE);
915 42476562 : }
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 143334356 : 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 143334356 : const signop sgn = TYPE_SIGN (type);
928 143334356 : const unsigned int prec = TYPE_PRECISION (type);
929 226956621 : 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 157555955 : if (prec == 1 && wi::ne_p (wmax, wmin))
934 : {
935 0 : r.set_varying (type);
936 0 : return;
937 : }
938 :
939 143334356 : if (overflow_wraps)
940 : {
941 : // If overflow wraps, truncate the values and adjust the range,
942 : // kind, and bounds appropriately.
943 83622265 : if ((min_ovf != wi::OVF_NONE) == (max_ovf != wi::OVF_NONE))
944 : {
945 58160144 : wide_int tmin = wide_int::from (wmin, prec, sgn);
946 58160144 : 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 58160144 : if (wi::gt_p (tmin, tmax, sgn))
950 539552 : r.set_varying (type);
951 : else
952 : // No overflow or both overflow or underflow. The range
953 : // kind stays normal.
954 57620592 : r.set (type, tmin, tmax);
955 58160144 : return;
956 58160282 : }
957 :
958 25462121 : if ((min_ovf == wi::OVF_UNDERFLOW && max_ovf == wi::OVF_NONE)
959 17829570 : || (max_ovf == wi::OVF_OVERFLOW && min_ovf == wi::OVF_NONE))
960 25462121 : 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 59712091 : if ((min_ovf == wi::OVF_OVERFLOW && max_ovf == wi::OVF_OVERFLOW)
970 59709737 : || (min_ovf == wi::OVF_UNDERFLOW && max_ovf == wi::OVF_UNDERFLOW))
971 : {
972 3883 : r.set_undefined ();
973 3883 : return;
974 : }
975 :
976 : // If overflow does not wrap, saturate to [MIN, MAX].
977 59708208 : wide_int new_lb, new_ub;
978 59708208 : if (min_ovf == wi::OVF_UNDERFLOW)
979 7270308 : new_lb = wi::min_value (prec, sgn);
980 52438110 : else if (min_ovf == wi::OVF_OVERFLOW)
981 0 : new_lb = wi::max_value (prec, sgn);
982 : else
983 52438110 : new_lb = wmin;
984 :
985 59708208 : if (max_ovf == wi::OVF_UNDERFLOW)
986 0 : new_ub = wi::min_value (prec, sgn);
987 59708208 : else if (max_ovf == wi::OVF_OVERFLOW)
988 12237815 : new_ub = wi::max_value (prec, sgn);
989 : else
990 47470647 : new_ub = wmax;
991 :
992 59708208 : r.set (type, new_lb, new_ub);
993 59708779 : }
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 84516794 : create_possibly_reversed_range (irange &r, tree type,
1002 : const wide_int &new_lb, const wide_int &new_ub)
1003 : {
1004 84516794 : signop s = TYPE_SIGN (type);
1005 : // If the bounds are swapped, treat the result as if an overflow occurred.
1006 84516794 : if (wi::gt_p (new_lb, new_ub, s))
1007 17013847 : value_range_from_overflowed_bounds (r, type, new_lb, new_ub);
1008 : else
1009 : // Otherwise it's just a normal range.
1010 67502947 : r.set (type, new_lb, new_ub);
1011 84516794 : }
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 85440429 : get_bool_state (vrange &r, const vrange &lhs, tree val_type)
1018 : {
1019 : // If there is no result, then this is unexecutable.
1020 85440429 : if (lhs.undefined_p ())
1021 : {
1022 0 : r.set_undefined ();
1023 0 : return BRS_EMPTY;
1024 : }
1025 :
1026 85440429 : 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 43660435 : if (lhs.contains_p (build_zero_cst (lhs.type ())))
1032 : {
1033 168442 : r.set_varying (val_type);
1034 168442 : 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 5908167 : operator_equal::op1_op2_relation (const irange &lhs, const irange &,
1053 : const irange &) const
1054 : {
1055 5908167 : if (lhs.undefined_p ())
1056 : return VREL_UNDEFINED;
1057 :
1058 : // FALSE = op1 == op2 indicates NE_EXPR.
1059 5908167 : if (lhs.zero_p ())
1060 : return VREL_NE;
1061 :
1062 : // TRUE = op1 == op2 indicates EQ_EXPR.
1063 3070705 : if (!contains_zero_p (lhs))
1064 3044584 : return VREL_EQ;
1065 : return VREL_VARYING;
1066 : }
1067 :
1068 : bool
1069 18071967 : operator_equal::fold_range (irange &r, tree type,
1070 : const irange &op1,
1071 : const irange &op2,
1072 : relation_trio rel) const
1073 : {
1074 18071967 : 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 18041898 : bool op1_const = wi::eq_p (op1.lower_bound (), op1.upper_bound ());
1080 18041898 : bool op2_const = wi::eq_p (op2.lower_bound (), op2.upper_bound ());
1081 18041888 : if (op1_const && op2_const)
1082 : {
1083 290768 : if (wi::eq_p (op1.lower_bound (), op2.upper_bound()))
1084 151688 : r = range_true (type);
1085 : else
1086 139080 : 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 17751120 : int_range_max tmp = op1;
1093 17751120 : tmp.intersect (op2);
1094 17751120 : if (tmp.undefined_p ())
1095 251309 : r = range_false (type);
1096 : // Check if a constant cannot satisfy the bitmask requirements.
1097 32624249 : else if (op2_const && !op1.get_bitmask ().member_p (op2.lower_bound ()))
1098 0 : r = range_false (type);
1099 17559427 : else if (op1_const && !op2.get_bitmask ().member_p (op1.lower_bound ()))
1100 0 : r = range_false (type);
1101 : else
1102 17499811 : r = range_true_and_false (type);
1103 17751120 : }
1104 : return true;
1105 : }
1106 :
1107 : bool
1108 11583147 : operator_equal::op1_range (irange &r, tree type,
1109 : const irange &lhs,
1110 : const irange &op2,
1111 : relation_trio) const
1112 : {
1113 11583147 : switch (get_bool_state (r, lhs, type))
1114 : {
1115 3464863 : case BRS_TRUE:
1116 : // If it's true, the result is the same as OP2.
1117 3464863 : r = op2;
1118 3464863 : break;
1119 :
1120 8086606 : case BRS_FALSE:
1121 : // If the result is false, the only time we know anything is
1122 : // if OP2 is a constant.
1123 8086606 : if (!op2.undefined_p ()
1124 24259818 : && wi::eq_p (op2.lower_bound(), op2.upper_bound()))
1125 : {
1126 6371429 : r = op2;
1127 6371429 : r.invert ();
1128 : }
1129 : else
1130 1715177 : r.set_varying (type);
1131 : break;
1132 :
1133 : default:
1134 : break;
1135 : }
1136 11583147 : return true;
1137 : }
1138 :
1139 : bool
1140 1547091 : operator_equal::op2_range (irange &r, tree type,
1141 : const irange &lhs,
1142 : const irange &op1,
1143 : relation_trio rel) const
1144 : {
1145 1547091 : 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 10973647 : operator_not_equal::op1_op2_relation (const irange &lhs, const irange &,
1161 : const irange &) const
1162 : {
1163 10973647 : if (lhs.undefined_p ())
1164 : return VREL_UNDEFINED;
1165 :
1166 : // FALSE = op1 != op2 indicates EQ_EXPR.
1167 10973647 : if (lhs.zero_p ())
1168 : return VREL_EQ;
1169 :
1170 : // TRUE = op1 != op2 indicates NE_EXPR.
1171 5552446 : if (!contains_zero_p (lhs))
1172 5512986 : return VREL_NE;
1173 : return VREL_VARYING;
1174 : }
1175 :
1176 : bool
1177 27082410 : operator_not_equal::fold_range (irange &r, tree type,
1178 : const irange &op1,
1179 : const irange &op2,
1180 : relation_trio rel) const
1181 : {
1182 27082410 : 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 27061571 : bool op1_const = wi::eq_p (op1.lower_bound (), op1.upper_bound ());
1188 27061571 : bool op2_const = wi::eq_p (op2.lower_bound (), op2.upper_bound ());
1189 27061233 : if (op1_const && op2_const)
1190 : {
1191 1108266 : if (wi::ne_p (op1.lower_bound (), op2.upper_bound()))
1192 627604 : r = range_true (type);
1193 : else
1194 480660 : 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 25952969 : int_range_max tmp = op1;
1201 25952969 : tmp.intersect (op2);
1202 25952969 : if (tmp.undefined_p ())
1203 243623 : r = range_true (type);
1204 : // Check if a constant cannot satisfy the bitmask requirements.
1205 46845799 : else if (op2_const && !op1.get_bitmask ().member_p (op2.lower_bound ()))
1206 0 : r = range_true (type);
1207 25745534 : else if (op1_const && !op2.get_bitmask ().member_p (op1.lower_bound ()))
1208 0 : r = range_true (type);
1209 : else
1210 25709346 : r = range_true_and_false (type);
1211 25952969 : }
1212 : return true;
1213 : }
1214 :
1215 : bool
1216 21854515 : operator_not_equal::op1_range (irange &r, tree type,
1217 : const irange &lhs,
1218 : const irange &op2,
1219 : relation_trio) const
1220 : {
1221 21854515 : switch (get_bool_state (r, lhs, type))
1222 : {
1223 13856769 : case BRS_TRUE:
1224 : // If the result is true, the only time we know anything is if
1225 : // OP2 is a constant.
1226 13856769 : if (!op2.undefined_p ()
1227 41570307 : && wi::eq_p (op2.lower_bound(), op2.upper_bound()))
1228 : {
1229 10808808 : r = op2;
1230 10808808 : r.invert ();
1231 : }
1232 : else
1233 3047961 : r.set_varying (type);
1234 : break;
1235 :
1236 7971967 : case BRS_FALSE:
1237 : // If it's false, the result is the same as OP2.
1238 7971967 : r = op2;
1239 7971967 : break;
1240 :
1241 : default:
1242 : break;
1243 : }
1244 21854515 : return true;
1245 : }
1246 :
1247 :
1248 : bool
1249 2790131 : operator_not_equal::op2_range (irange &r, tree type,
1250 : const irange &lhs,
1251 : const irange &op1,
1252 : relation_trio rel) const
1253 : {
1254 2790131 : 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 6617845 : build_lt (irange &r, tree type, const wide_int &val)
1261 : {
1262 6617845 : wi::overflow_type ov;
1263 6617845 : wide_int lim;
1264 6617845 : signop sgn = TYPE_SIGN (type);
1265 :
1266 : // Signed 1 bit cannot represent 1 for subtraction.
1267 6617845 : if (sgn == SIGNED)
1268 4448165 : lim = wi::add (val, -1, sgn, &ov);
1269 : else
1270 2169738 : lim = wi::sub (val, 1, sgn, &ov);
1271 :
1272 : // If val - 1 underflows, check if X < MIN, which is an empty range.
1273 6617845 : if (ov)
1274 355 : r.set_undefined ();
1275 : else
1276 6617548 : r = int_range<1> (type, min_limit (type), lim);
1277 6617845 : }
1278 :
1279 : // (X <= VAL) produces the range of [MIN, VAL].
1280 :
1281 : static void
1282 13625101 : build_le (irange &r, tree type, const wide_int &val)
1283 : {
1284 13625101 : r = int_range<1> (type, min_limit (type), val);
1285 13625101 : }
1286 :
1287 : // (X > VAL) produces the range of [VAL + 1, MAX].
1288 :
1289 : static void
1290 10222818 : build_gt (irange &r, tree type, const wide_int &val)
1291 : {
1292 10222818 : wi::overflow_type ov;
1293 10222818 : wide_int lim;
1294 10222818 : signop sgn = TYPE_SIGN (type);
1295 :
1296 : // Signed 1 bit cannot represent 1 for addition.
1297 10222818 : if (sgn == SIGNED)
1298 5284846 : lim = wi::sub (val, -1, sgn, &ov);
1299 : else
1300 4938058 : lim = wi::add (val, 1, sgn, &ov);
1301 : // If val + 1 overflows, check is for X > MAX, which is an empty range.
1302 10222818 : if (ov)
1303 0 : r.set_undefined ();
1304 : else
1305 10222904 : r = int_range<1> (type, lim, max_limit (type));
1306 10222818 : }
1307 :
1308 : // (X >= val) produces the range of [VAL, MAX].
1309 :
1310 : static void
1311 7075211 : build_ge (irange &r, tree type, const wide_int &val)
1312 : {
1313 7075211 : r = int_range<1> (type, val, max_limit (type));
1314 7075211 : }
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 12348050 : operator_lt::op1_op2_relation (const irange &lhs, const irange &,
1328 : const irange &) const
1329 : {
1330 12348050 : if (lhs.undefined_p ())
1331 : return VREL_UNDEFINED;
1332 :
1333 : // FALSE = op1 < op2 indicates GE_EXPR.
1334 12348050 : if (lhs.zero_p ())
1335 : return VREL_GE;
1336 :
1337 : // TRUE = op1 < op2 indicates LT_EXPR.
1338 6320155 : if (!contains_zero_p (lhs))
1339 6312553 : return VREL_LT;
1340 : return VREL_VARYING;
1341 : }
1342 :
1343 : bool
1344 6519604 : operator_lt::fold_range (irange &r, tree type,
1345 : const irange &op1,
1346 : const irange &op2,
1347 : relation_trio rel) const
1348 : {
1349 6519604 : if (relop_early_resolve (r, type, op1, op2, rel, VREL_LT))
1350 : return true;
1351 :
1352 6496756 : signop sign = TYPE_SIGN (op1.type ());
1353 6496756 : gcc_checking_assert (sign == TYPE_SIGN (op2.type ()));
1354 :
1355 6496792 : if (wi::lt_p (op1.upper_bound (), op2.lower_bound (), sign))
1356 22738 : r = range_true (type);
1357 6474054 : else if (!wi::lt_p (op1.lower_bound (), op2.upper_bound (), sign))
1358 80077 : r = range_false (type);
1359 : // Use nonzero bits to determine if < 0 is false.
1360 8390148 : else if (op2.zero_p () && !wi::neg_p (op1.get_nonzero_bits (), sign))
1361 0 : r = range_false (type);
1362 : else
1363 6393941 : r = range_true_and_false (type);
1364 : return true;
1365 : }
1366 :
1367 : bool
1368 5530902 : operator_lt::op1_range (irange &r, tree type,
1369 : const irange &lhs,
1370 : const irange &op2,
1371 : relation_trio) const
1372 : {
1373 5530902 : if (op2.undefined_p ())
1374 : return false;
1375 :
1376 5530902 : switch (get_bool_state (r, lhs, type))
1377 : {
1378 2447760 : case BRS_TRUE:
1379 2447760 : build_lt (r, type, op2.upper_bound ());
1380 2447760 : break;
1381 :
1382 3078360 : case BRS_FALSE:
1383 3078360 : build_ge (r, type, op2.lower_bound ());
1384 3078360 : break;
1385 :
1386 : default:
1387 : break;
1388 : }
1389 : return true;
1390 : }
1391 :
1392 : bool
1393 4113897 : operator_lt::op2_range (irange &r, tree type,
1394 : const irange &lhs,
1395 : const irange &op1,
1396 : relation_trio) const
1397 : {
1398 4113897 : if (op1.undefined_p ())
1399 : return false;
1400 :
1401 4113895 : switch (get_bool_state (r, lhs, type))
1402 : {
1403 1860679 : case BRS_TRUE:
1404 1860679 : build_gt (r, type, op1.lower_bound ());
1405 1860679 : break;
1406 :
1407 2249706 : case BRS_FALSE:
1408 2249706 : build_le (r, type, op1.upper_bound ());
1409 2249706 : 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 4422285 : operator_le::op1_op2_relation (const irange &lhs, const irange &,
1429 : const irange &) const
1430 : {
1431 4422285 : if (lhs.undefined_p ())
1432 : return VREL_UNDEFINED;
1433 :
1434 : // FALSE = op1 <= op2 indicates GT_EXPR.
1435 4422285 : if (lhs.zero_p ())
1436 : return VREL_GT;
1437 :
1438 : // TRUE = op1 <= op2 indicates LE_EXPR.
1439 2550802 : if (!contains_zero_p (lhs))
1440 2541438 : return VREL_LE;
1441 : return VREL_VARYING;
1442 : }
1443 :
1444 : bool
1445 5195352 : operator_le::fold_range (irange &r, tree type,
1446 : const irange &op1,
1447 : const irange &op2,
1448 : relation_trio rel) const
1449 : {
1450 5195352 : if (relop_early_resolve (r, type, op1, op2, rel, VREL_LE))
1451 : return true;
1452 :
1453 5182247 : signop sign = TYPE_SIGN (op1.type ());
1454 5182247 : gcc_checking_assert (sign == TYPE_SIGN (op2.type ()));
1455 :
1456 5182251 : if (wi::le_p (op1.upper_bound (), op2.lower_bound (), sign))
1457 113279 : r = range_true (type);
1458 5068972 : else if (!wi::le_p (op1.lower_bound (), op2.upper_bound (), sign))
1459 81692 : r = range_false (type);
1460 : else
1461 4987276 : r = range_true_and_false (type);
1462 : return true;
1463 : }
1464 :
1465 : bool
1466 6086326 : operator_le::op1_range (irange &r, tree type,
1467 : const irange &lhs,
1468 : const irange &op2,
1469 : relation_trio) const
1470 : {
1471 6086326 : if (op2.undefined_p ())
1472 : return false;
1473 :
1474 6086326 : switch (get_bool_state (r, lhs, type))
1475 : {
1476 3248590 : case BRS_TRUE:
1477 3248590 : build_le (r, type, op2.upper_bound ());
1478 3248590 : break;
1479 :
1480 2824753 : case BRS_FALSE:
1481 2824753 : build_gt (r, type, op2.lower_bound ());
1482 2824753 : break;
1483 :
1484 : default:
1485 : break;
1486 : }
1487 : return true;
1488 : }
1489 :
1490 : bool
1491 1118875 : operator_le::op2_range (irange &r, tree type,
1492 : const irange &lhs,
1493 : const irange &op1,
1494 : relation_trio) const
1495 : {
1496 1118875 : if (op1.undefined_p ())
1497 : return false;
1498 :
1499 1118875 : switch (get_bool_state (r, lhs, type))
1500 : {
1501 500946 : case BRS_TRUE:
1502 500946 : build_ge (r, type, op1.lower_bound ());
1503 500946 : break;
1504 :
1505 614075 : case BRS_FALSE:
1506 614075 : build_lt (r, type, op1.upper_bound ());
1507 614075 : 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 12118814 : operator_gt::op1_op2_relation (const irange &lhs, const irange &,
1527 : const irange &) const
1528 : {
1529 12118814 : if (lhs.undefined_p ())
1530 : return VREL_UNDEFINED;
1531 :
1532 : // FALSE = op1 > op2 indicates LE_EXPR.
1533 12118814 : if (lhs.zero_p ())
1534 : return VREL_LE;
1535 :
1536 : // TRUE = op1 > op2 indicates GT_EXPR.
1537 6607841 : if (!contains_zero_p (lhs))
1538 6594333 : return VREL_GT;
1539 : return VREL_VARYING;
1540 : }
1541 :
1542 : bool
1543 11619786 : operator_gt::fold_range (irange &r, tree type,
1544 : const irange &op1, const irange &op2,
1545 : relation_trio rel) const
1546 : {
1547 11619786 : if (relop_early_resolve (r, type, op1, op2, rel, VREL_GT))
1548 : return true;
1549 :
1550 11560562 : signop sign = TYPE_SIGN (op1.type ());
1551 11560562 : gcc_checking_assert (sign == TYPE_SIGN (op2.type ()));
1552 :
1553 11560588 : if (wi::gt_p (op1.lower_bound (), op2.upper_bound (), sign))
1554 97146 : r = range_true (type);
1555 11463442 : else if (!wi::gt_p (op1.upper_bound (), op2.lower_bound (), sign))
1556 378891 : r = range_false (type);
1557 : else
1558 11084525 : r = range_true_and_false (type);
1559 : return true;
1560 : }
1561 :
1562 : bool
1563 12272720 : operator_gt::op1_range (irange &r, tree type,
1564 : const irange &lhs, const irange &op2,
1565 : relation_trio) const
1566 : {
1567 12272720 : if (op2.undefined_p ())
1568 : return false;
1569 :
1570 12272720 : switch (get_bool_state (r, lhs, type))
1571 : {
1572 4974815 : case BRS_TRUE:
1573 4974815 : build_gt (r, type, op2.lower_bound ());
1574 4974815 : break;
1575 :
1576 7288582 : case BRS_FALSE:
1577 7288582 : build_le (r, type, op2.upper_bound ());
1578 7288582 : break;
1579 :
1580 : default:
1581 : break;
1582 : }
1583 : return true;
1584 : }
1585 :
1586 : bool
1587 3853147 : operator_gt::op2_range (irange &r, tree type,
1588 : const irange &lhs,
1589 : const irange &op1,
1590 : relation_trio) const
1591 : {
1592 3853147 : if (op1.undefined_p ())
1593 : return false;
1594 :
1595 3853147 : switch (get_bool_state (r, lhs, type))
1596 : {
1597 2363782 : case BRS_TRUE:
1598 2363782 : build_lt (r, type, op1.upper_bound ());
1599 2363782 : break;
1600 :
1601 1480773 : case BRS_FALSE:
1602 1480773 : build_ge (r, type, op1.lower_bound ());
1603 1480773 : 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 4113725 : operator_ge::op1_op2_relation (const irange &lhs, const irange &,
1623 : const irange &) const
1624 : {
1625 4113725 : if (lhs.undefined_p ())
1626 : return VREL_UNDEFINED;
1627 :
1628 : // FALSE = op1 >= op2 indicates LT_EXPR.
1629 4113725 : if (lhs.zero_p ())
1630 : return VREL_LT;
1631 :
1632 : // TRUE = op1 >= op2 indicates GE_EXPR.
1633 2216641 : if (!contains_zero_p (lhs))
1634 2210989 : return VREL_GE;
1635 : return VREL_VARYING;
1636 : }
1637 :
1638 : bool
1639 2691807 : operator_ge::fold_range (irange &r, tree type,
1640 : const irange &op1,
1641 : const irange &op2,
1642 : relation_trio rel) const
1643 : {
1644 2691807 : if (relop_early_resolve (r, type, op1, op2, rel, VREL_GE))
1645 : return true;
1646 :
1647 2679950 : signop sign = TYPE_SIGN (op1.type ());
1648 2679950 : gcc_checking_assert (sign == TYPE_SIGN (op2.type ()));
1649 :
1650 2679982 : if (wi::ge_p (op1.lower_bound (), op2.upper_bound (), sign))
1651 172059 : r = range_true (type);
1652 2507923 : else if (!wi::ge_p (op1.upper_bound (), op2.lower_bound (), sign))
1653 6261 : r = range_false (type);
1654 : else
1655 2501630 : r = range_true_and_false (type);
1656 : return true;
1657 : }
1658 :
1659 : bool
1660 3213775 : operator_ge::op1_range (irange &r, tree type,
1661 : const irange &lhs,
1662 : const irange &op2,
1663 : relation_trio) const
1664 : {
1665 3213775 : if (op2.undefined_p ())
1666 : return false;
1667 :
1668 3213775 : switch (get_bool_state (r, lhs, type))
1669 : {
1670 2015132 : case BRS_TRUE:
1671 2015132 : build_ge (r, type, op2.lower_bound ());
1672 2015132 : break;
1673 :
1674 1192228 : case BRS_FALSE:
1675 1192228 : build_lt (r, type, op2.upper_bound ());
1676 1192228 : break;
1677 :
1678 : default:
1679 : break;
1680 : }
1681 : return true;
1682 : }
1683 :
1684 : bool
1685 1403588 : operator_ge::op2_range (irange &r, tree type,
1686 : const irange &lhs,
1687 : const irange &op1,
1688 : relation_trio) const
1689 : {
1690 1403588 : if (op1.undefined_p ())
1691 : return false;
1692 :
1693 1403588 : switch (get_bool_state (r, lhs, type))
1694 : {
1695 838223 : case BRS_TRUE:
1696 838223 : build_le (r, type, op1.upper_bound ());
1697 838223 : break;
1698 :
1699 562571 : case BRS_FALSE:
1700 562571 : build_gt (r, type, op1.lower_bound ());
1701 562571 : break;
1702 :
1703 : default:
1704 : break;
1705 : }
1706 : return true;
1707 : }
1708 :
1709 :
1710 : void
1711 51631850 : operator_plus::update_bitmask (irange &r, const irange &lh,
1712 : const irange &rh) const
1713 : {
1714 51631850 : update_known_bitmask (r, PLUS_EXPR, lh, rh);
1715 51631850 : }
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 47903297 : operator_plus::lhs_op1_relation (const irange &lhs,
1722 : const irange &op1,
1723 : const irange &op2,
1724 : relation_kind) const
1725 : {
1726 47903297 : if (lhs.undefined_p () || op1.undefined_p () || op2.undefined_p ())
1727 : return VREL_VARYING;
1728 :
1729 47875470 : tree type = lhs.type ();
1730 47875470 : unsigned prec = TYPE_PRECISION (type);
1731 47875470 : wi::overflow_type ovf1, ovf2;
1732 47875470 : signop sign = TYPE_SIGN (type);
1733 :
1734 : // LHS = OP1 + 0 indicates LHS == OP1.
1735 47875470 : if (op2.zero_p ())
1736 : return VREL_EQ;
1737 :
1738 47705461 : if (TYPE_OVERFLOW_WRAPS (type))
1739 : {
1740 27417215 : wi::add (op1.lower_bound (), op2.lower_bound (), sign, &ovf1);
1741 27417434 : wi::add (op1.upper_bound (), op2.upper_bound (), sign, &ovf2);
1742 : }
1743 : else
1744 20288684 : ovf1 = ovf2 = wi::OVF_NONE;
1745 :
1746 : // Never wrapping additions.
1747 47705461 : if (!ovf1 && !ovf2)
1748 : {
1749 : // Positive op2 means lhs > op1.
1750 27882842 : if (wi::gt_p (op2.lower_bound (), wi::zero (prec), sign))
1751 : return VREL_GT;
1752 10411532 : if (wi::ge_p (op2.lower_bound (), wi::zero (prec), sign))
1753 : return VREL_GE;
1754 :
1755 : // Negative op2 means lhs < op1.
1756 8529638 : if (wi::lt_p (op2.upper_bound (), wi::zero (prec), sign))
1757 : return VREL_LT;
1758 5241534 : if (wi::le_p (op2.upper_bound (), wi::zero (prec), sign))
1759 : return VREL_LE;
1760 : }
1761 : // Always wrapping additions.
1762 19822997 : else if (ovf1 && ovf1 == ovf2)
1763 : {
1764 : // Positive op2 means lhs < op1.
1765 802285 : 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 24249935 : 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 8228401 : operator_plus::lhs_op2_relation (const irange &lhs, const irange &op1,
1789 : const irange &op2, relation_kind rel) const
1790 : {
1791 8228401 : return lhs_op1_relation (lhs, op2, op1, rel);
1792 : }
1793 :
1794 : void
1795 76456190 : 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 76456190 : wi::overflow_type ov_lb, ov_ub;
1800 76456190 : signop s = TYPE_SIGN (type);
1801 76456190 : wide_int new_lb = wi::add (lh_lb, rh_lb, s, &ov_lb);
1802 76456190 : wide_int new_ub = wi::add (lh_ub, rh_ub, s, &ov_ub);
1803 76456190 : value_range_with_overflow (r, type, new_lb, new_ub, ov_lb, ov_ub);
1804 76456190 : }
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 769149 : plus_minus_ranges (irange &r_ov, irange &r_normal, const irange &offset,
1814 : bool add_p)
1815 : {
1816 769149 : 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 769149 : if (!offset.singleton_p () || offset.zero_p ())
1820 751850 : return kind;
1821 :
1822 : // Always work with a positive offset. ie a+ -2 -> a-2 and a- -2 > a+2
1823 17299 : wide_int off = offset.lower_bound ();
1824 17299 : if (wi::neg_p (off, SIGNED))
1825 : {
1826 1190 : add_p = !add_p;
1827 1190 : off = wi::neg (off);
1828 : }
1829 :
1830 17299 : wi::overflow_type ov;
1831 17299 : tree type = offset.type ();
1832 17299 : unsigned prec = TYPE_PRECISION (type);
1833 17299 : wide_int ub;
1834 17299 : wide_int lb;
1835 : // calculate the normal range and relation for the operation.
1836 17299 : if (add_p)
1837 : {
1838 : // [ 0 , INF - OFF]
1839 16109 : lb = wi::zero (prec);
1840 16109 : ub = wi::sub (irange_val_max (type), off, UNSIGNED, &ov);
1841 16109 : kind = VREL_GT;
1842 : }
1843 : else
1844 : {
1845 : // [ OFF, INF ]
1846 1190 : lb = off;
1847 1190 : ub = irange_val_max (type);
1848 1190 : kind = VREL_LT;
1849 : }
1850 17299 : int_range<2> normal_range (type, lb, ub);
1851 17299 : int_range<2> ov_range (type, lb, ub, VR_ANTI_RANGE);
1852 :
1853 17299 : r_ov = ov_range;
1854 17299 : r_normal = normal_range;
1855 17299 : return kind;
1856 17299 : }
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 10870345 : adjust_op1_for_overflow (irange &r, const irange &op2, relation_kind rel,
1869 : bool add_p)
1870 : {
1871 10870345 : if (r.undefined_p ())
1872 : return;
1873 10870343 : tree type = r.type ();
1874 : // Check for unsigned overflow and calculate the overflow part.
1875 10870343 : signop s = TYPE_SIGN (type);
1876 10870343 : if (!TYPE_OVERFLOW_WRAPS (type) || s == SIGNED)
1877 : return;
1878 :
1879 : // Only work with <, <=, >, >= relations.
1880 5684963 : if (!relation_lt_le_gt_ge_p (rel))
1881 : return;
1882 :
1883 : // Get the ranges for this offset.
1884 769149 : int_range_max normal, overflow;
1885 769149 : relation_kind k = plus_minus_ranges (overflow, normal, op2, add_p);
1886 :
1887 : // VREL_VARYING means there are no adjustments.
1888 769149 : if (k == VREL_VARYING)
1889 : return;
1890 :
1891 : // If the relations match use the normal range, otherwise use overflow range.
1892 17299 : if (relation_intersect (k, rel) == k)
1893 12423 : r.intersect (normal);
1894 : else
1895 4876 : r.intersect (overflow);
1896 : return;
1897 769149 : }
1898 :
1899 : bool
1900 9758327 : operator_plus::op1_range (irange &r, tree type,
1901 : const irange &lhs,
1902 : const irange &op2,
1903 : relation_trio trio) const
1904 : {
1905 9758327 : if (lhs.undefined_p ())
1906 : return false;
1907 : // Start with the default operation.
1908 9758327 : range_op_handler minus (MINUS_EXPR);
1909 9758327 : if (!minus)
1910 : return false;
1911 9758327 : bool res = minus.fold_range (r, type, lhs, op2);
1912 9758327 : relation_kind rel = trio.lhs_op1 ();
1913 : // Check for a relation refinement.
1914 9758327 : if (res)
1915 9758327 : adjust_op1_for_overflow (r, op2, rel, true /* PLUS_EXPR */);
1916 : return res;
1917 : }
1918 :
1919 : bool
1920 2077551 : operator_plus::op2_range (irange &r, tree type,
1921 : const irange &lhs,
1922 : const irange &op1,
1923 : relation_trio rel) const
1924 : {
1925 2077551 : 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 18653939 : operator_minus::update_bitmask (irange &r, const irange &lh,
1996 : const irange &rh) const
1997 : {
1998 18653939 : update_known_bitmask (r, MINUS_EXPR, lh, rh);
1999 18653939 : }
2000 :
2001 : void
2002 26465712 : 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 26465712 : wi::overflow_type ov_lb, ov_ub;
2007 26465712 : signop s = TYPE_SIGN (type);
2008 26465712 : wide_int new_lb = wi::sub (lh_lb, rh_ub, s, &ov_lb);
2009 26465712 : wide_int new_ub = wi::sub (lh_ub, rh_lb, s, &ov_ub);
2010 26465712 : value_range_with_overflow (r, type, new_lb, new_ub, ov_lb, ov_ub);
2011 26465712 : }
2012 :
2013 :
2014 : // Return the relation between LHS and OP1 based on the relation between
2015 : // OP1 and OP2.
2016 :
2017 : relation_kind
2018 4812467 : operator_minus::lhs_op1_relation (const irange &, const irange &op1,
2019 : const irange &, relation_kind rel) const
2020 : {
2021 4812467 : if (!op1.undefined_p () && TYPE_SIGN (op1.type ()) == UNSIGNED)
2022 2429158 : 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 21282442 : 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 21282442 : if (rel == VREL_VARYING)
2044 : return false;
2045 :
2046 252678 : int_range<2> rel_range;
2047 252678 : unsigned prec = TYPE_PRECISION (type);
2048 252678 : signop sgn = TYPE_SIGN (type);
2049 :
2050 : // == and != produce [0,0] and ~[0,0] regardless of wrapping.
2051 252678 : if (rel == VREL_EQ)
2052 8406 : rel_range = int_range<2> (type, wi::zero (prec), wi::zero (prec));
2053 244272 : else if (rel == VREL_NE)
2054 99016 : rel_range = int_range<2> (type, wi::zero (prec), wi::zero (prec),
2055 49508 : VR_ANTI_RANGE);
2056 194764 : else if (TYPE_OVERFLOW_WRAPS (type))
2057 : {
2058 126160 : 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 46796 : case VREL_GT:
2063 46796 : case VREL_LT:
2064 93592 : rel_range = int_range<2> (type, wi::zero (prec), wi::zero (prec),
2065 46796 : VR_ANTI_RANGE);
2066 46796 : break;
2067 : default:
2068 : return false;
2069 : }
2070 : }
2071 : else
2072 : {
2073 68604 : switch (rel)
2074 : {
2075 : // op1 > op2, op1 - op2 can be restricted to [1, +INF]
2076 21730 : case VREL_GT:
2077 43460 : rel_range = int_range<2> (type, wi::one (prec),
2078 43460 : wi::max_value (prec, sgn));
2079 21730 : break;
2080 : // op1 >= op2, op1 - op2 can be restricted to [0, +INF]
2081 46149 : case VREL_GE:
2082 92298 : rel_range = int_range<2> (type, wi::zero (prec),
2083 92298 : wi::max_value (prec, sgn));
2084 46149 : break;
2085 : // op1 < op2, op1 - op2 can be restricted to [-INF, -1]
2086 287 : case VREL_LT:
2087 574 : rel_range = int_range<2> (type, wi::min_value (prec, sgn),
2088 287 : wi::minus_one (prec));
2089 287 : 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 173160 : lhs_range.intersect (rel_range);
2100 173160 : return true;
2101 252678 : }
2102 :
2103 : bool
2104 18653939 : 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 18653939 : return minus_op1_op2_relation_effect (lhs_range, type, op1_range, op2_range,
2110 18653939 : rel);
2111 : }
2112 :
2113 : bool
2114 1112018 : operator_minus::op1_range (irange &r, tree type,
2115 : const irange &lhs,
2116 : const irange &op2,
2117 : relation_trio trio) const
2118 : {
2119 1112018 : if (lhs.undefined_p ())
2120 : return false;
2121 : // Start with the default operation.
2122 1112018 : range_op_handler minus (PLUS_EXPR);
2123 1112018 : if (!minus)
2124 : return false;
2125 1112018 : bool res = minus.fold_range (r, type, lhs, op2);
2126 1112018 : relation_kind rel = trio.lhs_op1 ();
2127 1112018 : if (res)
2128 1112018 : adjust_op1_for_overflow (r, op2, rel, false /* PLUS_EXPR */);
2129 : return res;
2130 :
2131 : }
2132 :
2133 : bool
2134 1738776 : operator_minus::op2_range (irange &r, tree type,
2135 : const irange &lhs,
2136 : const irange &op1,
2137 : relation_trio) const
2138 : {
2139 1738776 : if (lhs.undefined_p ())
2140 : return false;
2141 1738776 : return fold_range (r, type, op1, lhs);
2142 : }
2143 :
2144 : void
2145 911927 : operator_min::update_bitmask (irange &r, const irange &lh,
2146 : const irange &rh) const
2147 : {
2148 911927 : update_known_bitmask (r, MIN_EXPR, lh, rh);
2149 911927 : }
2150 :
2151 : void
2152 1424788 : 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 1424788 : signop s = TYPE_SIGN (type);
2157 1424788 : wide_int new_lb = wi::min (lh_lb, rh_lb, s);
2158 1424788 : wide_int new_ub = wi::min (lh_ub, rh_ub, s);
2159 1424788 : value_range_with_overflow (r, type, new_lb, new_ub);
2160 1424788 : }
2161 :
2162 :
2163 : void
2164 713958 : operator_max::update_bitmask (irange &r, const irange &lh,
2165 : const irange &rh) const
2166 : {
2167 713958 : update_known_bitmask (r, MAX_EXPR, lh, rh);
2168 713958 : }
2169 :
2170 : void
2171 853556 : 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 853556 : signop s = TYPE_SIGN (type);
2176 853556 : wide_int new_lb = wi::max (lh_lb, rh_lb, s);
2177 853556 : wide_int new_ub = wi::max (lh_ub, rh_ub, s);
2178 853556 : value_range_with_overflow (r, type, new_lb, new_ub);
2179 853556 : }
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 14438877 : 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 14438877 : wide_int cp1, cp2, cp3, cp4;
2203 : // Default to varying.
2204 14438877 : r.set_varying (type);
2205 :
2206 : // Compute the 4 cross operations, bailing if we get an overflow we
2207 : // can't handle.
2208 14438877 : if (wi_op_overflows (cp1, type, lh_lb, rh_lb))
2209 : return;
2210 14438873 : if (wi::eq_p (lh_lb, lh_ub))
2211 4348849 : cp3 = cp1;
2212 10090024 : else if (wi_op_overflows (cp3, type, lh_ub, rh_lb))
2213 : return;
2214 14438873 : if (wi::eq_p (rh_lb, rh_ub))
2215 11144174 : cp2 = cp1;
2216 3294699 : else if (wi_op_overflows (cp2, type, lh_lb, rh_ub))
2217 : return;
2218 14436595 : if (wi::eq_p (lh_lb, lh_ub))
2219 4348829 : cp4 = cp2;
2220 10087766 : else if (wi_op_overflows (cp4, type, lh_ub, rh_ub))
2221 : return;
2222 :
2223 : // Order pairs.
2224 14436595 : signop sign = TYPE_SIGN (type);
2225 14436595 : if (wi::gt_p (cp1, cp2, sign))
2226 1512619 : std::swap (cp1, cp2);
2227 14436595 : if (wi::gt_p (cp3, cp4, sign))
2228 1480328 : std::swap (cp3, cp4);
2229 :
2230 : // Choose min and max from the ordered pairs.
2231 14436595 : wide_int res_lb = wi::min (cp1, cp3, sign);
2232 14436595 : wide_int res_ub = wi::max (cp2, cp4, sign);
2233 14436595 : value_range_with_overflow (r, type, res_lb, res_ub);
2234 14440427 : }
2235 :
2236 :
2237 : void
2238 13948519 : operator_mult::update_bitmask (irange &r, const irange &lh,
2239 : const irange &rh) const
2240 : {
2241 13948519 : update_known_bitmask (r, MULT_EXPR, lh, rh);
2242 13948519 : }
2243 :
2244 : bool
2245 1270372 : operator_mult::op1_range (irange &r, tree type,
2246 : const irange &lhs, const irange &op2,
2247 : relation_trio) const
2248 : {
2249 1270372 : 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 1270372 : if (TYPE_OVERFLOW_WRAPS (type))
2256 : return false;
2257 :
2258 339211 : wide_int offset;
2259 339211 : if (op2.singleton_p (offset) && offset != 0)
2260 230713 : 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 108498 : if (!lhs.contains_p (wi::zero (TYPE_PRECISION (lhs.type ()))))
2264 : {
2265 22213 : r.set_nonzero (type);
2266 22213 : return true;
2267 : }
2268 : return false;
2269 339211 : }
2270 :
2271 : bool
2272 131401 : operator_mult::op2_range (irange &r, tree type,
2273 : const irange &lhs, const irange &op1,
2274 : relation_trio rel) const
2275 : {
2276 131401 : return operator_mult::op1_range (r, type, lhs, op1, rel.swap_op1_op2 ());
2277 : }
2278 :
2279 : bool
2280 14057691 : operator_mult::wi_op_overflows (wide_int &res, tree type,
2281 : const wide_int &w0, const wide_int &w1) const
2282 : {
2283 14057691 : wi::overflow_type overflow = wi::OVF_NONE;
2284 14057691 : signop sign = TYPE_SIGN (type);
2285 14057691 : res = wi::mul (w0, w1, sign, &overflow);
2286 14057691 : 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 6735244 : if (sign == UNSIGNED || w0.sign_mask () == w1.sign_mask ())
2291 3714912 : res = wi::max_value (w0.get_precision (), sign);
2292 : else
2293 3020512 : res = wi::min_value (w0.get_precision (), sign);
2294 6735244 : return false;
2295 : }
2296 7322447 : return overflow;
2297 : }
2298 :
2299 : void
2300 17672689 : 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 17672689 : if (TYPE_OVERFLOW_UNDEFINED (type))
2305 : {
2306 5879320 : wi_cross_product (r, type, lh_lb, lh_ub, rh_lb, rh_ub);
2307 5879320 : 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 11793369 : signop sign = TYPE_SIGN (type);
2321 11793369 : unsigned prec = TYPE_PRECISION (type);
2322 11793369 : widest2_int min0 = widest2_int::from (lh_lb, sign);
2323 11793369 : widest2_int max0 = widest2_int::from (lh_ub, sign);
2324 11793369 : widest2_int min1 = widest2_int::from (rh_lb, sign);
2325 11793369 : widest2_int max1 = widest2_int::from (rh_ub, sign);
2326 11793369 : widest2_int sizem1 = wi::mask <widest2_int> (prec, false);
2327 11793369 : widest2_int size = sizem1 + 1;
2328 :
2329 : // Canonicalize the intervals.
2330 11793369 : if (sign == UNSIGNED)
2331 : {
2332 11091843 : if (wi::ltu_p (size, min0 + max0))
2333 : {
2334 1570647 : min0 -= size;
2335 1570647 : max0 -= size;
2336 : }
2337 11091811 : if (wi::ltu_p (size, min1 + max1))
2338 : {
2339 157364 : min1 -= size;
2340 157364 : max1 -= size;
2341 : }
2342 : }
2343 :
2344 : // Sort the 4 products so that min is in prod0 and max is in
2345 : // prod3.
2346 11793369 : widest2_int prod0 = min0 * min1;
2347 11793369 : widest2_int prod1 = min0 * max1;
2348 11793369 : widest2_int prod2 = max0 * min1;
2349 11793369 : widest2_int prod3 = max0 * max1;
2350 :
2351 : // min0min1 > max0max1
2352 11793369 : if (prod0 > prod3)
2353 188727 : std::swap (prod0, prod3);
2354 :
2355 : // min0max1 > max0min1
2356 11793369 : if (prod1 > prod2)
2357 299884 : std::swap (prod1, prod2);
2358 :
2359 11793369 : if (prod0 > prod1)
2360 79972 : std::swap (prod0, prod1);
2361 :
2362 11793369 : if (prod2 > prod3)
2363 3940 : std::swap (prod2, prod3);
2364 :
2365 : // diff = max - min
2366 11793369 : prod2 = prod3 - prod0;
2367 11793369 : if (wi::geu_p (prod2, sizem1))
2368 : {
2369 : // Multiplying by X, where X is a power of 2 is [0,0][X,+INF].
2370 7787788 : if (TYPE_UNSIGNED (type) && rh_lb == rh_ub
2371 7185731 : && wi::exact_log2 (rh_lb) != -1 && prec > 1)
2372 : {
2373 2690786 : r.set (type, rh_lb, wi::max_value (prec, sign));
2374 2690786 : int_range<2> zero;
2375 2690786 : zero.set_zero (type);
2376 2690786 : r.union_ (zero);
2377 2690786 : }
2378 : else
2379 : // The range covers all values.
2380 1273183 : r.set_varying (type);
2381 : }
2382 : else
2383 : {
2384 7829400 : wide_int new_lb = wide_int::from (prod0, prec, sign);
2385 7829400 : wide_int new_ub = wide_int::from (prod3, prec, sign);
2386 7829400 : create_possibly_reversed_range (r, type, new_lb, new_ub);
2387 7829443 : }
2388 11793969 : }
2389 :
2390 : class operator_widen_mult_signed : public range_operator
2391 : {
2392 : public:
2393 : virtual void wi_fold (irange &r, tree type,
2394 : const wide_int &lh_lb,
2395 : const wide_int &lh_ub,
2396 : const wide_int &rh_lb,
2397 : const wide_int &rh_ub)
2398 : const;
2399 : } op_widen_mult_signed;
2400 :
2401 : void
2402 1347 : operator_widen_mult_signed::wi_fold (irange &r, tree type,
2403 : const wide_int &lh_lb,
2404 : const wide_int &lh_ub,
2405 : const wide_int &rh_lb,
2406 : const wide_int &rh_ub) const
2407 : {
2408 1347 : wide_int lh_wlb = wide_int::from (lh_lb, TYPE_PRECISION (type), SIGNED);
2409 1347 : wide_int lh_wub = wide_int::from (lh_ub, TYPE_PRECISION (type), SIGNED);
2410 1347 : wide_int rh_wlb = wide_int::from (rh_lb, TYPE_PRECISION (type), SIGNED);
2411 1347 : wide_int rh_wub = wide_int::from (rh_ub, TYPE_PRECISION (type), SIGNED);
2412 :
2413 : /* We don't expect a widening multiplication to be able to overflow but range
2414 : calculations for multiplications are complicated. After widening the
2415 : operands lets call the base class. */
2416 1347 : return op_mult.wi_fold (r, type, lh_wlb, lh_wub, rh_wlb, rh_wub);
2417 1347 : }
2418 :
2419 : class operator_widen_mult_unsigned : public range_operator
2420 : {
2421 : public:
2422 : virtual void wi_fold (irange &r, tree type,
2423 : const wide_int &lh_lb,
2424 : const wide_int &lh_ub,
2425 : const wide_int &rh_lb,
2426 : const wide_int &rh_ub)
2427 : const;
2428 : } op_widen_mult_unsigned;
2429 :
2430 : void
2431 5540 : operator_widen_mult_unsigned::wi_fold (irange &r, tree type,
2432 : const wide_int &lh_lb,
2433 : const wide_int &lh_ub,
2434 : const wide_int &rh_lb,
2435 : const wide_int &rh_ub) const
2436 : {
2437 5540 : wide_int lh_wlb = wide_int::from (lh_lb, TYPE_PRECISION (type), UNSIGNED);
2438 5540 : wide_int lh_wub = wide_int::from (lh_ub, TYPE_PRECISION (type), UNSIGNED);
2439 5540 : wide_int rh_wlb = wide_int::from (rh_lb, TYPE_PRECISION (type), UNSIGNED);
2440 5540 : wide_int rh_wub = wide_int::from (rh_ub, TYPE_PRECISION (type), UNSIGNED);
2441 :
2442 : /* We don't expect a widening multiplication to be able to overflow but range
2443 : calculations for multiplications are complicated. After widening the
2444 : operands lets call the base class. */
2445 5540 : return op_mult.wi_fold (r, type, lh_wlb, lh_wub, rh_wlb, rh_wub);
2446 5540 : }
2447 :
2448 : class operator_widen_mult_signed_unsigned : public range_operator
2449 : {
2450 : public:
2451 : virtual void wi_fold (irange &r, tree type,
2452 : const wide_int &lh_lb,
2453 : const wide_int &lh_ub,
2454 : const wide_int &rh_lb,
2455 : const wide_int &rh_ub)
2456 : const;
2457 : } op_widen_mult_signed_unsigned;
2458 :
2459 : void
2460 0 : operator_widen_mult_signed_unsigned::wi_fold (irange &r, tree type,
2461 : const wide_int &lh_lb,
2462 : const wide_int &lh_ub,
2463 : const wide_int &rh_lb,
2464 : const wide_int &rh_ub) const
2465 : {
2466 0 : wide_int lh_wlb = wide_int::from (lh_lb, TYPE_PRECISION (type), SIGNED);
2467 0 : wide_int lh_wub = wide_int::from (lh_ub, TYPE_PRECISION (type), SIGNED);
2468 0 : wide_int rh_wlb = wide_int::from (rh_lb, TYPE_PRECISION (type), UNSIGNED);
2469 0 : wide_int rh_wub = wide_int::from (rh_ub, TYPE_PRECISION (type), UNSIGNED);
2470 :
2471 : /* We don't expect a widening multiplication to be able to overflow but range
2472 : calculations for multiplications are complicated. After widening the
2473 : operands lets call the base class. */
2474 0 : return op_mult.wi_fold (r, type, lh_wlb, lh_wub, rh_wlb, rh_wub);
2475 0 : }
2476 :
2477 : class operator_div : public cross_product_operator
2478 : {
2479 : using range_operator::update_bitmask;
2480 : using range_operator::op2_range;
2481 : public:
2482 : operator_div (tree_code div_kind) { m_code = div_kind; }
2483 : bool op2_range (irange &r, tree type, const irange &lhs, const irange &,
2484 : relation_trio) const final override;
2485 : virtual void wi_fold (irange &r, tree type,
2486 : const wide_int &lh_lb,
2487 : const wide_int &lh_ub,
2488 : const wide_int &rh_lb,
2489 : const wide_int &rh_ub) const final override;
2490 : virtual bool wi_op_overflows (wide_int &res, tree type,
2491 : const wide_int &, const wide_int &)
2492 : const final override;
2493 2840439 : void update_bitmask (irange &r, const irange &lh, const irange &rh)
2494 : const final override
2495 2840439 : { update_known_bitmask (r, m_code, lh, rh); }
2496 : protected:
2497 : tree_code m_code;
2498 : };
2499 :
2500 : static operator_div op_trunc_div (TRUNC_DIV_EXPR);
2501 : static operator_div op_floor_div (FLOOR_DIV_EXPR);
2502 : static operator_div op_round_div (ROUND_DIV_EXPR);
2503 : static operator_div op_ceil_div (CEIL_DIV_EXPR);
2504 :
2505 : // Set OP2 to non-zero if the LHS isn't UNDEFINED.
2506 : bool
2507 37212 : operator_div::op2_range (irange &r, tree type, const irange &lhs,
2508 : const irange &, relation_trio) const
2509 : {
2510 37212 : if (!lhs.undefined_p ())
2511 : {
2512 37212 : r.set_nonzero (type);
2513 37212 : return true;
2514 : }
2515 : return false;
2516 : }
2517 :
2518 : bool
2519 12308148 : operator_div::wi_op_overflows (wide_int &res, tree type,
2520 : const wide_int &w0, const wide_int &w1) const
2521 : {
2522 12308148 : if (w1 == 0)
2523 : return true;
2524 :
2525 12308148 : wi::overflow_type overflow = wi::OVF_NONE;
2526 12308148 : signop sign = TYPE_SIGN (type);
2527 :
2528 12308148 : switch (m_code)
2529 : {
2530 12170758 : case EXACT_DIV_EXPR:
2531 12170758 : case TRUNC_DIV_EXPR:
2532 12170758 : res = wi::div_trunc (w0, w1, sign, &overflow);
2533 12170758 : break;
2534 125655 : case FLOOR_DIV_EXPR:
2535 125655 : res = wi::div_floor (w0, w1, sign, &overflow);
2536 125655 : break;
2537 288 : case ROUND_DIV_EXPR:
2538 288 : res = wi::div_round (w0, w1, sign, &overflow);
2539 288 : break;
2540 11447 : case CEIL_DIV_EXPR:
2541 11447 : res = wi::div_ceil (w0, w1, sign, &overflow);
2542 11447 : break;
2543 0 : default:
2544 0 : gcc_unreachable ();
2545 : }
2546 :
2547 12308148 : if (overflow && TYPE_OVERFLOW_UNDEFINED (type))
2548 : {
2549 : // For division, the only case is -INF / -1 = +INF.
2550 210937 : res = wi::max_value (w0.get_precision (), sign);
2551 210937 : return false;
2552 : }
2553 12097211 : return overflow;
2554 : }
2555 :
2556 : void
2557 3977022 : operator_div::wi_fold (irange &r, tree type,
2558 : const wide_int &lh_lb, const wide_int &lh_ub,
2559 : const wide_int &rh_lb, const wide_int &rh_ub) const
2560 : {
2561 3977022 : const wide_int dividend_min = lh_lb;
2562 3977022 : const wide_int dividend_max = lh_ub;
2563 3977022 : const wide_int divisor_min = rh_lb;
2564 3977022 : const wide_int divisor_max = rh_ub;
2565 3977022 : signop sign = TYPE_SIGN (type);
2566 3977022 : unsigned prec = TYPE_PRECISION (type);
2567 3977022 : wide_int extra_min, extra_max;
2568 :
2569 : // If we know we won't divide by zero, just do the division.
2570 3977022 : if (!wi_includes_zero_p (type, divisor_min, divisor_max))
2571 : {
2572 3285899 : wi_cross_product (r, type, dividend_min, dividend_max,
2573 : divisor_min, divisor_max);
2574 3285899 : return;
2575 : }
2576 :
2577 : // If we're definitely dividing by zero, there's nothing to do.
2578 691123 : if (wi_zero_p (type, divisor_min, divisor_max))
2579 : {
2580 19136 : r.set_undefined ();
2581 19136 : return;
2582 : }
2583 :
2584 : // Perform the division in 2 parts, [LB, -1] and [1, UB], which will
2585 : // skip any division by zero.
2586 :
2587 : // First divide by the negative numbers, if any.
2588 671987 : if (wi::neg_p (divisor_min, sign))
2589 870930 : wi_cross_product (r, type, dividend_min, dividend_max,
2590 870930 : divisor_min, wi::minus_one (prec));
2591 : else
2592 236522 : r.set_undefined ();
2593 :
2594 : // Then divide by the non-zero positive numbers, if any.
2595 671987 : if (wi::gt_p (divisor_max, wi::zero (prec), sign))
2596 : {
2597 671231 : int_range_max tmp;
2598 1342462 : wi_cross_product (tmp, type, dividend_min, dividend_max,
2599 671231 : wi::one (prec), divisor_max);
2600 671231 : r.union_ (tmp);
2601 671231 : }
2602 : // We shouldn't still have undefined here.
2603 671987 : gcc_checking_assert (!r.undefined_p ());
2604 3977674 : }
2605 :
2606 :
2607 : class operator_exact_divide : public operator_div
2608 : {
2609 : using range_operator::op1_range;
2610 : public:
2611 : operator_exact_divide () : operator_div (EXACT_DIV_EXPR) { }
2612 : virtual bool op1_range (irange &r, tree type,
2613 : const irange &lhs,
2614 : const irange &op2,
2615 : relation_trio) const;
2616 :
2617 : } op_exact_div;
2618 :
2619 : bool
2620 512945 : operator_exact_divide::op1_range (irange &r, tree type,
2621 : const irange &lhs,
2622 : const irange &op2,
2623 : relation_trio) const
2624 : {
2625 512945 : if (lhs.undefined_p ())
2626 : return false;
2627 512945 : wide_int offset;
2628 : // [2, 4] = op1 / [3,3] since its exact divide, no need to worry about
2629 : // remainders in the endpoints, so op1 = [2,4] * [3,3] = [6,12].
2630 : // We wont bother trying to enumerate all the in between stuff :-P
2631 : // TRUE accuracy is [6,6][9,9][12,12]. This is unlikely to matter most of
2632 : // the time however.
2633 : // If op2 is a multiple of 2, we would be able to set some non-zero bits.
2634 512945 : if (op2.singleton_p (offset) && offset != 0)
2635 512945 : return range_op_handler (MULT_EXPR).fold_range (r, type, lhs, op2);
2636 : return false;
2637 512945 : }
2638 :
2639 :
2640 : class operator_lshift : public cross_product_operator
2641 : {
2642 : using range_operator::fold_range;
2643 : using range_operator::op1_range;
2644 : using range_operator::update_bitmask;
2645 : public:
2646 : virtual bool op1_range (irange &r, tree type, const irange &lhs,
2647 : const irange &op2, relation_trio rel = TRIO_VARYING)
2648 : const final override;
2649 : virtual bool fold_range (irange &r, tree type, const irange &op1,
2650 : const irange &op2, relation_trio rel = TRIO_VARYING)
2651 : const final override;
2652 :
2653 : virtual void wi_fold (irange &r, tree type,
2654 : const wide_int &lh_lb, const wide_int &lh_ub,
2655 : const wide_int &rh_lb,
2656 : const wide_int &rh_ub) const final override;
2657 : virtual bool wi_op_overflows (wide_int &res,
2658 : tree type,
2659 : const wide_int &,
2660 : const wide_int &) const final override;
2661 463585 : void update_bitmask (irange &r, const irange &lh,
2662 : const irange &rh) const final override
2663 463585 : { update_known_bitmask (r, LSHIFT_EXPR, lh, rh); }
2664 : // Check compatibility of LHS and op1.
2665 1078307 : bool operand_check_p (tree t1, tree t2, tree) const final override
2666 1078307 : { return range_compatible_p (t1, t2); }
2667 : } op_lshift;
2668 :
2669 : class operator_rshift : public cross_product_operator
2670 : {
2671 : using range_operator::fold_range;
2672 : using range_operator::op1_range;
2673 : using range_operator::lhs_op1_relation;
2674 : using range_operator::update_bitmask;
2675 : public:
2676 : virtual bool fold_range (irange &r, tree type, const irange &op1,
2677 : const irange &op2, relation_trio rel = TRIO_VARYING)
2678 : const final override;
2679 : virtual void wi_fold (irange &r, tree type,
2680 : const wide_int &lh_lb,
2681 : const wide_int &lh_ub,
2682 : const wide_int &rh_lb,
2683 : const wide_int &rh_ub) const final override;
2684 : virtual bool wi_op_overflows (wide_int &res,
2685 : tree type,
2686 : const wide_int &w0,
2687 : const wide_int &w1) const final override;
2688 : virtual bool op1_range (irange &, tree type, const irange &lhs,
2689 : const irange &op2, relation_trio rel = TRIO_VARYING)
2690 : const final override;
2691 : virtual relation_kind lhs_op1_relation (const irange &lhs, const irange &op1,
2692 : const irange &op2, relation_kind rel)
2693 : const final override;
2694 3297862 : void update_bitmask (irange &r, const irange &lh,
2695 : const irange &rh) const final override
2696 3297862 : { update_known_bitmask (r, RSHIFT_EXPR, lh, rh); }
2697 : // Check compatibility of LHS and op1.
2698 3393038 : bool operand_check_p (tree t1, tree t2, tree) const final override
2699 3393038 : { return range_compatible_p (t1, t2); }
2700 : } op_rshift;
2701 :
2702 :
2703 : relation_kind
2704 2397099 : operator_rshift::lhs_op1_relation (const irange &lhs ATTRIBUTE_UNUSED,
2705 : const irange &op1,
2706 : const irange &op2,
2707 : relation_kind) const
2708 : {
2709 : // If both operands range are >= 0, then the LHS <= op1.
2710 2397099 : if (!op1.undefined_p () && !op2.undefined_p ()
2711 4793423 : && wi::ge_p (op1.lower_bound (), 0, TYPE_SIGN (op1.type ()))
2712 6987272 : && wi::ge_p (op2.lower_bound (), 0, TYPE_SIGN (op2.type ())))
2713 2166948 : return VREL_LE;
2714 : return VREL_VARYING;
2715 : }
2716 :
2717 : bool
2718 1619927 : operator_lshift::fold_range (irange &r, tree type,
2719 : const irange &op1,
2720 : const irange &op2,
2721 : relation_trio rel) const
2722 : {
2723 1619927 : int_range_max shift_range;
2724 1619927 : if (!get_shift_range (shift_range, type, op2))
2725 : {
2726 575 : if (op2.undefined_p ())
2727 230 : r.set_undefined ();
2728 : else
2729 345 : r.set_zero (type);
2730 575 : return true;
2731 : }
2732 :
2733 : // Transform left shifts by constants into multiplies.
2734 1619352 : if (shift_range.singleton_p ())
2735 : {
2736 1155740 : unsigned shift = shift_range.lower_bound ().to_uhwi ();
2737 1155740 : wide_int tmp = wi::set_bit_in_zero (shift, TYPE_PRECISION (type));
2738 1155740 : int_range<1> mult (type, tmp, tmp);
2739 :
2740 : // Force wrapping multiplication.
2741 1155740 : bool saved_flag_wrapv = flag_wrapv;
2742 1155740 : bool saved_flag_wrapv_pointer = flag_wrapv_pointer;
2743 1155740 : flag_wrapv = 1;
2744 1155740 : flag_wrapv_pointer = 1;
2745 1155740 : bool b = op_mult.fold_range (r, type, op1, mult);
2746 1155740 : flag_wrapv = saved_flag_wrapv;
2747 1155740 : flag_wrapv_pointer = saved_flag_wrapv_pointer;
2748 1155740 : return b;
2749 1155749 : }
2750 : else
2751 : // Otherwise, invoke the generic fold routine.
2752 463612 : return range_operator::fold_range (r, type, op1, shift_range, rel);
2753 1619927 : }
2754 :
2755 : void
2756 555018 : operator_lshift::wi_fold (irange &r, tree type,
2757 : const wide_int &lh_lb, const wide_int &lh_ub,
2758 : const wide_int &rh_lb, const wide_int &rh_ub) const
2759 : {
2760 555018 : signop sign = TYPE_SIGN (type);
2761 555018 : unsigned prec = TYPE_PRECISION (type);
2762 555018 : int overflow_pos = sign == SIGNED ? prec - 1 : prec;
2763 555018 : int bound_shift = overflow_pos - rh_ub.to_shwi ();
2764 : // If bound_shift == HOST_BITS_PER_WIDE_INT, the llshift can
2765 : // overflow. However, for that to happen, rh.max needs to be zero,
2766 : // which means rh is a singleton range of zero, which means we simply return
2767 : // [lh_lb, lh_ub] as the range.
2768 555018 : if (wi::eq_p (rh_ub, rh_lb) && wi::eq_p (rh_ub, 0))
2769 : {
2770 24733 : r = int_range<2> (type, lh_lb, lh_ub);
2771 24733 : return;
2772 : }
2773 :
2774 530285 : wide_int bound = wi::set_bit_in_zero (bound_shift, prec);
2775 530285 : wide_int complement = ~(bound - 1);
2776 530285 : wide_int low_bound, high_bound;
2777 530285 : bool in_bounds = false;
2778 :
2779 530285 : if (sign == UNSIGNED)
2780 : {
2781 269494 : low_bound = bound;
2782 269494 : high_bound = complement;
2783 269494 : if (wi::ltu_p (lh_ub, low_bound))
2784 : {
2785 : // [5, 6] << [1, 2] == [10, 24].
2786 : // We're shifting out only zeroes, the value increases
2787 : // monotonically.
2788 : in_bounds = true;
2789 : }
2790 84933 : else if (wi::ltu_p (high_bound, lh_lb))
2791 : {
2792 : // [0xffffff00, 0xffffffff] << [1, 2]
2793 : // == [0xfffffc00, 0xfffffffe].
2794 : // We're shifting out only ones, the value decreases
2795 : // monotonically.
2796 : in_bounds = true;
2797 : }
2798 : }
2799 : else
2800 : {
2801 : // [-1, 1] << [1, 2] == [-4, 4]
2802 260791 : low_bound = complement;
2803 260791 : high_bound = bound;
2804 260791 : if (wi::lts_p (lh_ub, high_bound)
2805 260791 : && wi::lts_p (low_bound, lh_lb))
2806 : {
2807 : // For non-negative numbers, we're shifting out only zeroes,
2808 : // the value increases monotonically. For negative numbers,
2809 : // we're shifting out only ones, the value decreases
2810 : // monotonically.
2811 : in_bounds = true;
2812 : }
2813 : }
2814 :
2815 : if (in_bounds)
2816 310215 : wi_cross_product (r, type, lh_lb, lh_ub, rh_lb, rh_ub);
2817 : else
2818 220070 : r.set_varying (type);
2819 530294 : }
2820 :
2821 : bool
2822 594714 : operator_lshift::wi_op_overflows (wide_int &res, tree type,
2823 : const wide_int &w0, const wide_int &w1) const
2824 : {
2825 594714 : signop sign = TYPE_SIGN (type);
2826 594714 : if (wi::neg_p (w1))
2827 : {
2828 : // It's unclear from the C standard whether shifts can overflow.
2829 : // The following code ignores overflow; perhaps a C standard
2830 : // interpretation ruling is needed.
2831 0 : res = wi::rshift (w0, -w1, sign);
2832 : }
2833 : else
2834 594714 : res = wi::lshift (w0, w1);
2835 594714 : return false;
2836 : }
2837 :
2838 : bool
2839 49338 : operator_lshift::op1_range (irange &r,
2840 : tree type,
2841 : const irange &lhs,
2842 : const irange &op2,
2843 : relation_trio) const
2844 : {
2845 49338 : if (lhs.undefined_p ())
2846 : return false;
2847 :
2848 49338 : if (!contains_zero_p (lhs))
2849 21286 : r.set_nonzero (type);
2850 : else
2851 28052 : r.set_varying (type);
2852 :
2853 49338 : wide_int shift;
2854 49338 : if (op2.singleton_p (shift))
2855 : {
2856 43701 : if (wi::lt_p (shift, 0, SIGNED))
2857 : return false;
2858 43701 : if (wi::ge_p (shift, wi::uhwi (TYPE_PRECISION (type),
2859 43701 : TYPE_PRECISION (op2.type ())),
2860 : UNSIGNED))
2861 : return false;
2862 43701 : if (shift == 0)
2863 : {
2864 6 : r.intersect (lhs);
2865 6 : return true;
2866 : }
2867 :
2868 : // Work completely in unsigned mode to start.
2869 43695 : tree utype = type;
2870 43695 : int_range_max tmp_range;
2871 43695 : if (TYPE_SIGN (type) == SIGNED)
2872 : {
2873 7249 : int_range_max tmp = lhs;
2874 7249 : utype = unsigned_type_for (type);
2875 7249 : range_cast (tmp, utype);
2876 7249 : op_rshift.fold_range (tmp_range, utype, tmp, op2);
2877 7249 : }
2878 : else
2879 36446 : op_rshift.fold_range (tmp_range, utype, lhs, op2);
2880 :
2881 : // Start with ranges which can produce the LHS by right shifting the
2882 : // result by the shift amount.
2883 : // ie [0x08, 0xF0] = op1 << 2 will start with
2884 : // [00001000, 11110000] = op1 << 2
2885 : // [0x02, 0x4C] aka [00000010, 00111100]
2886 :
2887 : // Then create a range from the LB with the least significant upper bit
2888 : // set, to the upper bound with all the bits set.
2889 : // This would be [0x42, 0xFC] aka [01000010, 11111100].
2890 :
2891 : // Ideally we do this for each subrange, but just lump them all for now.
2892 43695 : unsigned low_bits = TYPE_PRECISION (utype) - shift.to_uhwi ();
2893 43695 : wide_int up_mask = wi::mask (low_bits, true, TYPE_PRECISION (utype));
2894 43695 : wide_int new_ub = wi::bit_or (up_mask, tmp_range.upper_bound ());
2895 43695 : wide_int new_lb = wi::set_bit (tmp_range.lower_bound (), low_bits);
2896 43695 : int_range<2> fill_range (utype, new_lb, new_ub);
2897 43695 : tmp_range.union_ (fill_range);
2898 :
2899 43695 : if (utype != type)
2900 7249 : range_cast (tmp_range, type);
2901 :
2902 43695 : r.intersect (tmp_range);
2903 43695 : return true;
2904 43695 : }
2905 :
2906 5637 : return !r.varying_p ();
2907 49338 : }
2908 :
2909 : bool
2910 814126 : operator_rshift::op1_range (irange &r,
2911 : tree type,
2912 : const irange &lhs,
2913 : const irange &op2,
2914 : relation_trio) const
2915 : {
2916 814126 : if (lhs.undefined_p ())
2917 : return false;
2918 814126 : wide_int shift;
2919 814126 : if (op2.singleton_p (shift))
2920 : {
2921 : // Ignore nonsensical shifts.
2922 788949 : unsigned prec = TYPE_PRECISION (type);
2923 1577898 : if (wi::ge_p (shift,
2924 788949 : wi::uhwi (prec, TYPE_PRECISION (op2.type ())),
2925 : UNSIGNED))
2926 : return false;
2927 788949 : if (shift == 0)
2928 : {
2929 75 : r = lhs;
2930 75 : return true;
2931 : }
2932 :
2933 : // Folding the original operation may discard some impossible
2934 : // ranges from the LHS.
2935 788874 : int_range_max lhs_refined;
2936 788874 : op_rshift.fold_range (lhs_refined, type, int_range<1> (type), op2);
2937 788874 : lhs_refined.intersect (lhs);
2938 788874 : if (lhs_refined.undefined_p ())
2939 : {
2940 4 : r.set_undefined ();
2941 4 : return true;
2942 : }
2943 788870 : int_range_max shift_range (op2.type (), shift, shift);
2944 788870 : int_range_max lb, ub;
2945 788870 : op_lshift.fold_range (lb, type, lhs_refined, shift_range);
2946 : // LHS
2947 : // 0000 0111 = OP1 >> 3
2948 : //
2949 : // OP1 is anything from 0011 1000 to 0011 1111. That is, a
2950 : // range from LHS<<3 plus a mask of the 3 bits we shifted on the
2951 : // right hand side (0x07).
2952 788870 : wide_int mask = wi::mask (shift.to_uhwi (), false, prec);
2953 788870 : int_range_max mask_range (type,
2954 788870 : wi::zero (TYPE_PRECISION (type)),
2955 788870 : mask);
2956 788870 : op_plus.fold_range (ub, type, lb, mask_range);
2957 788870 : r = lb;
2958 788870 : r.union_ (ub);
2959 788870 : if (!contains_zero_p (lhs_refined))
2960 : {
2961 455178 : mask_range.invert ();
2962 455178 : r.intersect (mask_range);
2963 : }
2964 788870 : return true;
2965 788874 : }
2966 : return false;
2967 814126 : }
2968 :
2969 : bool
2970 10950813 : operator_rshift::wi_op_overflows (wide_int &res,
2971 : tree type,
2972 : const wide_int &w0,
2973 : const wide_int &w1) const
2974 : {
2975 10950813 : signop sign = TYPE_SIGN (type);
2976 10950813 : if (wi::neg_p (w1))
2977 0 : res = wi::lshift (w0, -w1);
2978 : else
2979 : {
2980 : // It's unclear from the C standard whether shifts can overflow.
2981 : // The following code ignores overflow; perhaps a C standard
2982 : // interpretation ruling is needed.
2983 10950904 : res = wi::rshift (w0, w1, sign);
2984 : }
2985 10950813 : return false;
2986 : }
2987 :
2988 : bool
2989 3299085 : operator_rshift::fold_range (irange &r, tree type,
2990 : const irange &op1,
2991 : const irange &op2,
2992 : relation_trio rel) const
2993 : {
2994 3299085 : int_range_max shift;
2995 3299085 : if (!get_shift_range (shift, type, op2))
2996 : {
2997 664 : if (op2.undefined_p ())
2998 251 : r.set_undefined ();
2999 : else
3000 413 : r.set_zero (type);
3001 664 : return true;
3002 : }
3003 :
3004 3298421 : return range_operator::fold_range (r, type, op1, shift, rel);
3005 3299085 : }
3006 :
3007 : void
3008 3856747 : operator_rshift::wi_fold (irange &r, tree type,
3009 : const wide_int &lh_lb, const wide_int &lh_ub,
3010 : const wide_int &rh_lb, const wide_int &rh_ub) const
3011 : {
3012 3856747 : wi_cross_product (r, type, lh_lb, lh_ub, rh_lb, rh_ub);
3013 3856747 : }
3014 :
3015 :
3016 : // Add a partial equivalence between the LHS and op1 for casts.
3017 :
3018 : relation_kind
3019 23476755 : operator_cast::lhs_op1_relation (const irange &lhs,
3020 : const irange &op1,
3021 : const irange &op2 ATTRIBUTE_UNUSED,
3022 : relation_kind) const
3023 : {
3024 23476755 : if (lhs.undefined_p () || op1.undefined_p ())
3025 : return VREL_VARYING;
3026 23454834 : unsigned lhs_prec = TYPE_PRECISION (lhs.type ());
3027 23454834 : unsigned op1_prec = TYPE_PRECISION (op1.type ());
3028 : // If the result gets sign extended into a larger type check first if this
3029 : // qualifies as a partial equivalence.
3030 23454834 : if (TYPE_SIGN (op1.type ()) == SIGNED && lhs_prec > op1_prec)
3031 : {
3032 : // If the result is sign extended, and the LHS is larger than op1,
3033 : // check if op1's range can be negative as the sign extension will
3034 : // cause the upper bits to be 1 instead of 0, invalidating the PE.
3035 3663175 : int_range<3> negs = range_negatives (op1.type ());
3036 3663175 : negs.intersect (op1);
3037 3663175 : if (!negs.undefined_p ())
3038 2582364 : return VREL_VARYING;
3039 3663175 : }
3040 :
3041 20872470 : unsigned prec = MIN (lhs_prec, op1_prec);
3042 20872470 : return bits_to_pe (prec);
3043 : }
3044 :
3045 : // Return TRUE if casting from INNER to OUTER is a truncating cast.
3046 :
3047 : inline bool
3048 80944515 : operator_cast::truncating_cast_p (const irange &inner,
3049 : const irange &outer) const
3050 : {
3051 80944515 : return TYPE_PRECISION (outer.type ()) < TYPE_PRECISION (inner.type ());
3052 : }
3053 :
3054 : // Return TRUE if [MIN,MAX] is inside the domain of RANGE's type.
3055 :
3056 : bool
3057 69974419 : operator_cast::inside_domain_p (const wide_int &min,
3058 : const wide_int &max,
3059 : const irange &range) const
3060 : {
3061 69974419 : wide_int domain_min = irange_val_min (range.type ());
3062 69974419 : wide_int domain_max = irange_val_max (range.type ());
3063 69974419 : signop domain_sign = TYPE_SIGN (range.type ());
3064 69974419 : return (wi::le_p (min, domain_max, domain_sign)
3065 69974419 : && wi::le_p (max, domain_max, domain_sign)
3066 69974419 : && wi::ge_p (min, domain_min, domain_sign)
3067 139948838 : && wi::ge_p (max, domain_min, domain_sign));
3068 69974419 : }
3069 :
3070 :
3071 : // Helper for fold_range which work on a pair at a time.
3072 :
3073 : void
3074 73020950 : operator_cast::fold_pair (irange &r, unsigned index,
3075 : const irange &inner,
3076 : const irange &outer) const
3077 : {
3078 73020950 : tree inner_type = inner.type ();
3079 73020950 : tree outer_type = outer.type ();
3080 73020950 : signop inner_sign = TYPE_SIGN (inner_type);
3081 73020950 : unsigned outer_prec = TYPE_PRECISION (outer_type);
3082 :
3083 : // check to see if casting from INNER to OUTER is a conversion that
3084 : // fits in the resulting OUTER type.
3085 73020950 : wide_int inner_lb = inner.lower_bound (index);
3086 73020950 : wide_int inner_ub = inner.upper_bound (index);
3087 73020950 : if (truncating_cast_p (inner, outer))
3088 : {
3089 : // We may be able to accommodate a truncating cast if the
3090 : // resulting range can be represented in the target type...
3091 14081978 : if (wi::rshift (wi::sub (inner_ub, inner_lb),
3092 7040989 : wi::uhwi (outer_prec, TYPE_PRECISION (inner.type ())),
3093 21122967 : inner_sign) != 0)
3094 : {
3095 3046531 : r.set_varying (outer_type);
3096 3046531 : return;
3097 : }
3098 : }
3099 : // ...but we must still verify that the final range fits in the
3100 : // domain. This catches -fstrict-enum restrictions where the domain
3101 : // range is smaller than what fits in the underlying type.
3102 69974419 : wide_int min = wide_int::from (inner_lb, outer_prec, inner_sign);
3103 69974419 : wide_int max = wide_int::from (inner_ub, outer_prec, inner_sign);
3104 69974419 : if (inside_domain_p (min, max, outer))
3105 69974419 : create_possibly_reversed_range (r, outer_type, min, max);
3106 : else
3107 0 : r.set_varying (outer_type);
3108 73023382 : }
3109 :
3110 :
3111 : bool
3112 58671477 : operator_cast::fold_range (irange &r, tree type ATTRIBUTE_UNUSED,
3113 : const irange &inner,
3114 : const irange &outer,
3115 : relation_trio) const
3116 : {
3117 58671477 : if (empty_range_varying (r, type, inner, outer))
3118 32070 : return true;
3119 :
3120 58639407 : gcc_checking_assert (outer.varying_p ());
3121 58639407 : gcc_checking_assert (inner.num_pairs () > 0);
3122 :
3123 : // Avoid a temporary by folding the first pair directly into the result.
3124 58639407 : fold_pair (r, 0, inner, outer);
3125 :
3126 : // Then process any additional pairs by unioning with their results.
3127 72344288 : for (unsigned x = 1; x < inner.num_pairs (); ++x)
3128 : {
3129 14381543 : int_range_max tmp;
3130 14381543 : fold_pair (tmp, x, inner, outer);
3131 14381543 : r.union_ (tmp);
3132 : // If we hit varying, go update the bitmask.
3133 14381543 : if (r.varying_p ())
3134 : break;
3135 14381543 : }
3136 :
3137 58639407 : update_bitmask (r, inner, outer);
3138 58639407 : return true;
3139 : }
3140 :
3141 : void
3142 58639407 : operator_cast::update_bitmask (irange &r, const irange &lh,
3143 : const irange &rh) const
3144 : {
3145 58639407 : update_known_bitmask (r, CONVERT_EXPR, lh, rh);
3146 58639407 : }
3147 :
3148 : bool
3149 7923565 : operator_cast::op1_range (irange &r, tree type,
3150 : const irange &lhs,
3151 : const irange &op2,
3152 : relation_trio) const
3153 : {
3154 7923565 : if (lhs.undefined_p ())
3155 : return false;
3156 7923565 : tree lhs_type = lhs.type ();
3157 7923565 : gcc_checking_assert (types_compatible_p (op2.type(), type));
3158 :
3159 : // If we are calculating a pointer, shortcut to what we really care about.
3160 7923565 : if (POINTER_TYPE_P (type))
3161 : {
3162 : // Conversion from other pointers or a constant (including 0/NULL)
3163 : // are straightforward.
3164 0 : if (POINTER_TYPE_P (lhs.type ())
3165 0 : || (lhs.singleton_p ()
3166 0 : && TYPE_PRECISION (lhs.type ()) >= TYPE_PRECISION (type)))
3167 : {
3168 0 : r = lhs;
3169 0 : range_cast (r, type);
3170 : }
3171 : else
3172 : {
3173 : // If the LHS is not a pointer nor a singleton, then it is
3174 : // either VARYING or non-zero.
3175 0 : if (!lhs.undefined_p () && !contains_zero_p (lhs))
3176 0 : r.set_nonzero (type);
3177 : else
3178 0 : r.set_varying (type);
3179 : }
3180 0 : r.intersect (op2);
3181 0 : return true;
3182 : }
3183 :
3184 7923565 : if (truncating_cast_p (op2, lhs))
3185 : {
3186 1340163 : if (lhs.varying_p ())
3187 163949 : r.set_varying (type);
3188 : else
3189 : {
3190 : // We want to insert the LHS as an unsigned value since it
3191 : // would not trigger the signed bit of the larger type.
3192 1176214 : int_range_max converted_lhs = lhs;
3193 1176214 : range_cast (converted_lhs, unsigned_type_for (lhs_type));
3194 1176214 : range_cast (converted_lhs, type);
3195 : // Start by building the positive signed outer range for the type.
3196 1176214 : wide_int lim = wi::set_bit_in_zero (TYPE_PRECISION (lhs_type),
3197 2352428 : TYPE_PRECISION (type));
3198 1176214 : create_possibly_reversed_range (r, type, lim,
3199 1176214 : wi::max_value (TYPE_PRECISION (type),
3200 : SIGNED));
3201 : // For the signed part, we need to simply union the 2 ranges now.
3202 1176214 : r.union_ (converted_lhs);
3203 :
3204 : // Create maximal negative number outside of LHS bits.
3205 1176214 : lim = wi::mask (TYPE_PRECISION (lhs_type), true,
3206 2352428 : TYPE_PRECISION (type));
3207 : // Add this to the unsigned LHS range(s).
3208 1176214 : int_range_max lim_range (type, lim, lim);
3209 1176214 : int_range_max lhs_neg;
3210 1176214 : range_op_handler (PLUS_EXPR).fold_range (lhs_neg, type,
3211 : converted_lhs, lim_range);
3212 : // lhs_neg now has all the negative versions of the LHS.
3213 : // Now union in all the values from SIGNED MIN (0x80000) to
3214 : // lim-1 in order to fill in all the ranges with the upper
3215 : // bits set.
3216 :
3217 : // PR 97317. If the lhs has only 1 bit less precision than the rhs,
3218 : // we don't need to create a range from min to lim-1
3219 : // calculate neg range traps trying to create [lim, lim - 1].
3220 1176214 : wide_int min_val = wi::min_value (TYPE_PRECISION (type), SIGNED);
3221 1176214 : if (lim != min_val)
3222 : {
3223 1174522 : int_range_max neg (type,
3224 2349044 : wi::min_value (TYPE_PRECISION (type),
3225 : SIGNED),
3226 2349044 : lim - 1);
3227 1174522 : lhs_neg.union_ (neg);
3228 1174522 : }
3229 : // And finally, munge the signed and unsigned portions.
3230 1176214 : r.union_ (lhs_neg);
3231 1176214 : }
3232 : // And intersect with any known value passed in the extra operand.
3233 1340163 : r.intersect (op2);
3234 1340163 : if (r.undefined_p ())
3235 : return true;
3236 :
3237 : // Now create a bitmask indicating that the lower bit must match the
3238 : // bits in the LHS. Zero-extend LHS bitmask to precision of op1.
3239 1340104 : irange_bitmask bm = lhs.get_bitmask ();
3240 2680208 : wide_int mask = wide_int::from (bm.mask (), TYPE_PRECISION (type),
3241 2680208 : UNSIGNED);
3242 2680208 : wide_int value = wide_int::from (bm.value (), TYPE_PRECISION (type),
3243 2680208 : UNSIGNED);
3244 :
3245 : // Set then additonal unknown bits in mask.
3246 1340104 : wide_int lim = wi::mask (TYPE_PRECISION (lhs_type), true,
3247 2680208 : TYPE_PRECISION (type));
3248 1340104 : mask = mask | lim;
3249 :
3250 : // Now set the new bitmask for the range.
3251 1340104 : irange_bitmask new_bm (value, mask);
3252 1340104 : r.update_bitmask (new_bm);
3253 1340104 : return true;
3254 1340104 : }
3255 :
3256 6583402 : int_range_max tmp;
3257 6583402 : if (TYPE_PRECISION (lhs_type) == TYPE_PRECISION (type))
3258 4956666 : tmp = lhs;
3259 : else
3260 : {
3261 : // The cast is not truncating, and the range is restricted to
3262 : // the range of the RHS by this assignment.
3263 : //
3264 : // Cast the range of the RHS to the type of the LHS.
3265 1626736 : fold_range (tmp, lhs_type, int_range<1> (type), int_range<1> (lhs_type));
3266 : // Intersect this with the LHS range will produce the range,
3267 : // which will be cast to the RHS type before returning.
3268 1626736 : tmp.intersect (lhs);
3269 : }
3270 :
3271 : // Cast the calculated range to the type of the RHS.
3272 6583402 : fold_range (r, type, tmp, int_range<1> (type));
3273 6583402 : return true;
3274 6583402 : }
3275 :
3276 : // VIEW_CONVERT_EXPR works like a cast between integral values.
3277 : // If the number of bits are not the same, behaviour is undefined,
3278 : // so cast behaviour still works.
3279 :
3280 : bool
3281 268177 : operator_view::fold_range (irange &r, tree type,
3282 : const irange &op1, const irange &op2,
3283 : relation_trio rel) const
3284 : {
3285 268177 : return m_cast.fold_range (r, type, op1, op2, rel);
3286 : }
3287 :
3288 : bool
3289 0 : operator_view::fold_range (prange &r, tree type,
3290 : const prange &op1, const prange &op2,
3291 : relation_trio rel) const
3292 : {
3293 0 : return m_cast.fold_range (r, type, op1, op2, rel);
3294 : }
3295 : bool
3296 254882 : operator_view::fold_range (irange &r, tree type,
3297 : const prange &op1, const irange &op2,
3298 : relation_trio rel) const
3299 : {
3300 254882 : return m_cast.fold_range (r, type, op1, op2, rel);
3301 : }
3302 :
3303 : bool
3304 0 : operator_view::fold_range (prange &r, tree type,
3305 : const irange &op1, const prange &op2,
3306 : relation_trio rel) const
3307 : {
3308 0 : return m_cast.fold_range (r, type, op1, op2, rel);
3309 : }
3310 :
3311 : bool
3312 11150 : operator_view::op1_range (irange &r, tree type,
3313 : const irange &lhs, const irange &op2,
3314 : relation_trio rel) const
3315 : {
3316 11150 : return m_cast.op1_range (r, type, lhs, op2, rel);
3317 : }
3318 :
3319 : bool
3320 0 : operator_view::op1_range (prange &r, tree type,
3321 : const prange &lhs, const prange &op2,
3322 : relation_trio rel) const
3323 : {
3324 0 : return m_cast.op1_range (r, type, lhs, op2, rel);
3325 : }
3326 :
3327 : bool
3328 0 : operator_view::op1_range (irange &r, tree type,
3329 : const prange &lhs, const irange &op2,
3330 : relation_trio rel) const
3331 : {
3332 0 : return m_cast.op1_range (r, type, lhs, op2, rel);
3333 : }
3334 :
3335 : bool
3336 0 : operator_view::op1_range (prange &r, tree type,
3337 : const irange &lhs, const prange &op2,
3338 : relation_trio rel) const
3339 : {
3340 0 : return m_cast.op1_range (r, type, lhs, op2, rel);
3341 : }
3342 :
3343 : void
3344 0 : operator_view::update_bitmask (irange &r, const irange &lh,
3345 : const irange &rh) const
3346 : {
3347 0 : m_cast.update_bitmask (r, lh, rh);
3348 0 : }
3349 :
3350 :
3351 : class operator_logical_and : public range_operator
3352 : {
3353 : using range_operator::fold_range;
3354 : using range_operator::op1_range;
3355 : using range_operator::op2_range;
3356 : public:
3357 : bool fold_range (irange &r, tree type,
3358 : const irange &lh,
3359 : const irange &rh,
3360 : relation_trio rel = TRIO_VARYING) const final override;
3361 : bool op1_range (irange &r, tree type,
3362 : const irange &lhs,
3363 : const irange &op2,
3364 : relation_trio rel = TRIO_VARYING) const final override;
3365 : bool op2_range (irange &r, tree type,
3366 : const irange &lhs,
3367 : const irange &op1,
3368 : relation_trio rel = TRIO_VARYING) const final override;
3369 : // Check compatibility of all operands.
3370 0 : bool operand_check_p (tree t1, tree t2, tree t3) const final override
3371 0 : { return range_compatible_p (t1, t2) && range_compatible_p (t1, t3); }
3372 : } op_logical_and;
3373 :
3374 : bool
3375 0 : operator_logical_and::fold_range (irange &r, tree type,
3376 : const irange &lh,
3377 : const irange &rh,
3378 : relation_trio) const
3379 : {
3380 0 : if (empty_range_varying (r, type, lh, rh))
3381 0 : return true;
3382 :
3383 : // Precision of LHS and both operands must match.
3384 0 : if (TYPE_PRECISION (lh.type ()) != TYPE_PRECISION (type)
3385 0 : || TYPE_PRECISION (type) != TYPE_PRECISION (rh.type ()))
3386 0 : return false;
3387 :
3388 : // 0 && anything is 0.
3389 0 : if ((wi::eq_p (lh.lower_bound (), 0) && wi::eq_p (lh.upper_bound (), 0))
3390 0 : || (wi::eq_p (lh.lower_bound (), 0) && wi::eq_p (rh.upper_bound (), 0)))
3391 0 : r = range_false (type);
3392 0 : else if (contains_zero_p (lh) || contains_zero_p (rh))
3393 : // To reach this point, there must be a logical 1 on each side, and
3394 : // the only remaining question is whether there is a zero or not.
3395 0 : r = range_true_and_false (type);
3396 : else
3397 0 : r = range_true (type);
3398 : return true;
3399 : }
3400 :
3401 : bool
3402 797464 : operator_logical_and::op1_range (irange &r, tree type,
3403 : const irange &lhs,
3404 : const irange &op2 ATTRIBUTE_UNUSED,
3405 : relation_trio) const
3406 : {
3407 797464 : switch (get_bool_state (r, lhs, type))
3408 : {
3409 408614 : case BRS_TRUE:
3410 : // A true result means both sides of the AND must be true.
3411 408614 : r = range_true (type);
3412 408614 : break;
3413 388850 : default:
3414 : // Any other result means only one side has to be false, the
3415 : // other side can be anything. So we cannot be sure of any
3416 : // result here.
3417 388850 : r = range_true_and_false (type);
3418 388850 : break;
3419 : }
3420 797464 : return true;
3421 : }
3422 :
3423 : bool
3424 0 : operator_logical_and::op2_range (irange &r, tree type,
3425 : const irange &lhs,
3426 : const irange &op1,
3427 : relation_trio) const
3428 : {
3429 0 : return operator_logical_and::op1_range (r, type, lhs, op1);
3430 : }
3431 :
3432 :
3433 : void
3434 7399256 : operator_bitwise_and::update_bitmask (irange &r, const irange &lh,
3435 : const irange &rh) const
3436 : {
3437 7399256 : update_known_bitmask (r, BIT_AND_EXPR, lh, rh);
3438 7399256 : }
3439 :
3440 : // Optimize BIT_AND_EXPR, BIT_IOR_EXPR and BIT_XOR_EXPR of signed types
3441 : // by considering the number of leading redundant sign bit copies.
3442 : // clrsb (X op Y) = min (clrsb (X), clrsb (Y)), so for example
3443 : // [-1, 0] op [-1, 0] is [-1, 0] (where nonzero_bits doesn't help).
3444 : static bool
3445 182244 : wi_optimize_signed_bitwise_op (irange &r, tree type,
3446 : const wide_int &lh_lb, const wide_int &lh_ub,
3447 : const wide_int &rh_lb, const wide_int &rh_ub)
3448 : {
3449 364488 : int lh_clrsb = MIN (wi::clrsb (lh_lb), wi::clrsb (lh_ub));
3450 364488 : int rh_clrsb = MIN (wi::clrsb (rh_lb), wi::clrsb (rh_ub));
3451 182244 : int new_clrsb = MIN (lh_clrsb, rh_clrsb);
3452 182244 : if (new_clrsb == 0)
3453 : return false;
3454 11758 : int type_prec = TYPE_PRECISION (type);
3455 11758 : int rprec = (type_prec - new_clrsb) - 1;
3456 11758 : value_range_with_overflow (r, type,
3457 23516 : wi::mask (rprec, true, type_prec),
3458 11758 : wi::mask (rprec, false, type_prec));
3459 11758 : return true;
3460 : }
3461 :
3462 : // An AND of 8,16, 32 or 64 bits can produce a partial equivalence between
3463 : // the LHS and op1.
3464 :
3465 : relation_kind
3466 6700910 : operator_bitwise_and::lhs_op1_relation (const irange &lhs,
3467 : const irange &op1,
3468 : const irange &op2,
3469 : relation_kind) const
3470 : {
3471 6700910 : if (lhs.undefined_p () || op1.undefined_p () || op2.undefined_p ())
3472 : return VREL_VARYING;
3473 6696675 : if (!op2.singleton_p ())
3474 : return VREL_VARYING;
3475 : // if val == 0xff or 0xFFFF OR 0Xffffffff OR 0Xffffffffffffffff, return TRUE
3476 3797552 : int prec1 = TYPE_PRECISION (op1.type ());
3477 3797552 : int prec2 = TYPE_PRECISION (op2.type ());
3478 3797552 : int mask_prec = 0;
3479 3797552 : wide_int mask = op2.lower_bound ();
3480 3797552 : if (wi::eq_p (mask, wi::mask (8, false, prec2)))
3481 : mask_prec = 8;
3482 3714445 : else if (wi::eq_p (mask, wi::mask (16, false, prec2)))
3483 : mask_prec = 16;
3484 3699227 : else if (wi::eq_p (mask, wi::mask (32, false, prec2)))
3485 : mask_prec = 32;
3486 3515000 : else if (wi::eq_p (mask, wi::mask (64, false, prec2)))
3487 798 : mask_prec = 64;
3488 3797552 : return bits_to_pe (MIN (prec1, mask_prec));
3489 3797552 : }
3490 :
3491 : // Optimize BIT_AND_EXPR and BIT_IOR_EXPR in terms of a mask if
3492 : // possible. Basically, see if we can optimize:
3493 : //
3494 : // [LB, UB] op Z
3495 : // into:
3496 : // [LB op Z, UB op Z]
3497 : //
3498 : // If the optimization was successful, accumulate the range in R and
3499 : // return TRUE.
3500 :
3501 : static bool
3502 22524887 : wi_optimize_and_or (irange &r,
3503 : enum tree_code code,
3504 : tree type,
3505 : const wide_int &lh_lb, const wide_int &lh_ub,
3506 : const wide_int &rh_lb, const wide_int &rh_ub)
3507 : {
3508 : // Calculate the singleton mask among the ranges, if any.
3509 22524887 : wide_int lower_bound, upper_bound, mask;
3510 22524887 : if (wi::eq_p (rh_lb, rh_ub))
3511 : {
3512 20868376 : mask = rh_lb;
3513 20868376 : lower_bound = lh_lb;
3514 20868376 : upper_bound = lh_ub;
3515 : }
3516 1656511 : else if (wi::eq_p (lh_lb, lh_ub))
3517 : {
3518 359964 : mask = lh_lb;
3519 359964 : lower_bound = rh_lb;
3520 359964 : upper_bound = rh_ub;
3521 : }
3522 : else
3523 : return false;
3524 :
3525 : // If Z is a constant which (for op | its bitwise not) has n
3526 : // consecutive least significant bits cleared followed by m 1
3527 : // consecutive bits set immediately above it and either
3528 : // m + n == precision, or (x >> (m + n)) == (y >> (m + n)).
3529 : //
3530 : // The least significant n bits of all the values in the range are
3531 : // cleared or set, the m bits above it are preserved and any bits
3532 : // above these are required to be the same for all values in the
3533 : // range.
3534 21228340 : wide_int w = mask;
3535 21228340 : int m = 0, n = 0;
3536 21228340 : if (code == BIT_IOR_EXPR)
3537 6177797 : w = ~w;
3538 21228340 : if (wi::eq_p (w, 0))
3539 7179210 : n = w.get_precision ();
3540 : else
3541 : {
3542 14049130 : n = wi::ctz (w);
3543 14049136 : w = ~(w | wi::mask (n, false, w.get_precision ()));
3544 14049130 : if (wi::eq_p (w, 0))
3545 8357363 : m = w.get_precision () - n;
3546 : else
3547 5691767 : m = wi::ctz (w) - n;
3548 : }
3549 21228340 : wide_int new_mask = wi::mask (m + n, true, w.get_precision ());
3550 21228346 : if ((new_mask & lower_bound) != (new_mask & upper_bound))
3551 : return false;
3552 :
3553 16357984 : wide_int res_lb, res_ub;
3554 16357984 : if (code == BIT_AND_EXPR)
3555 : {
3556 10412377 : res_lb = wi::bit_and (lower_bound, mask);
3557 10412377 : res_ub = wi::bit_and (upper_bound, mask);
3558 : }
3559 5945607 : else if (code == BIT_IOR_EXPR)
3560 : {
3561 5945607 : res_lb = wi::bit_or (lower_bound, mask);
3562 5945607 : res_ub = wi::bit_or (upper_bound, mask);
3563 : }
3564 : else
3565 0 : gcc_unreachable ();
3566 16357984 : value_range_with_overflow (r, type, res_lb, res_ub);
3567 :
3568 : // Furthermore, if the mask is non-zero, an IOR cannot contain zero.
3569 16357984 : if (code == BIT_IOR_EXPR && wi::ne_p (mask, 0))
3570 : {
3571 3020828 : int_range<2> tmp;
3572 3020828 : tmp.set_nonzero (type);
3573 3020828 : r.intersect (tmp);
3574 3020828 : }
3575 16357984 : return true;
3576 60111217 : }
3577 :
3578 : // For range [LB, UB] compute two wide_int bit masks.
3579 : //
3580 : // In the MAYBE_NONZERO bit mask, if some bit is unset, it means that
3581 : // for all numbers in the range the bit is 0, otherwise it might be 0
3582 : // or 1.
3583 : //
3584 : // In the MUSTBE_NONZERO bit mask, if some bit is set, it means that
3585 : // for all numbers in the range the bit is 1, otherwise it might be 0
3586 : // or 1.
3587 :
3588 : void
3589 13334793 : wi_set_zero_nonzero_bits (tree type,
3590 : const wide_int &lb, const wide_int &ub,
3591 : wide_int &maybe_nonzero,
3592 : wide_int &mustbe_nonzero)
3593 : {
3594 13334793 : signop sign = TYPE_SIGN (type);
3595 :
3596 13334793 : if (wi::eq_p (lb, ub))
3597 5333809 : maybe_nonzero = mustbe_nonzero = lb;
3598 8000984 : else if (wi::ge_p (lb, 0, sign) || wi::lt_p (ub, 0, sign))
3599 : {
3600 7577665 : wide_int xor_mask = lb ^ ub;
3601 7577665 : maybe_nonzero = lb | ub;
3602 7577665 : mustbe_nonzero = lb & ub;
3603 7577665 : if (xor_mask != 0)
3604 : {
3605 7577665 : wide_int mask = wi::mask (wi::floor_log2 (xor_mask), false,
3606 15155330 : maybe_nonzero.get_precision ());
3607 7577665 : maybe_nonzero = maybe_nonzero | mask;
3608 7577670 : mustbe_nonzero = wi::bit_and_not (mustbe_nonzero, mask);
3609 7577665 : }
3610 7577665 : }
3611 : else
3612 : {
3613 423319 : maybe_nonzero = wi::minus_one (lb.get_precision ());
3614 423319 : mustbe_nonzero = wi::zero (lb.get_precision ());
3615 : }
3616 13334793 : }
3617 :
3618 : void
3619 16319342 : operator_bitwise_and::wi_fold (irange &r, tree type,
3620 : const wide_int &lh_lb,
3621 : const wide_int &lh_ub,
3622 : const wide_int &rh_lb,
3623 : const wide_int &rh_ub) const
3624 : {
3625 : // The AND algorithm does not handle complex signed operations well.
3626 : // If a signed range crosses the boundry between signed and unsigned
3627 : // proces sit as 2 ranges and union the results.
3628 16319342 : if (TYPE_SIGN (type) == SIGNED
3629 16319342 : && wi::neg_p (lh_lb, SIGNED) != wi::neg_p (lh_ub, SIGNED))
3630 : {
3631 603559 : int prec = TYPE_PRECISION (type);
3632 603559 : int_range_max tmp;
3633 : // Process [lh_lb, -1]
3634 603559 : wi_fold (tmp, type, lh_lb, wi::minus_one (prec), rh_lb, rh_ub);
3635 : // Now Process [0, rh_ub]
3636 603559 : wi_fold (r, type, wi::zero (prec), lh_ub, rh_lb, rh_ub);
3637 603559 : r.union_ (tmp);
3638 603559 : return;
3639 603559 : }
3640 :
3641 15715783 : if (wi_optimize_and_or (r, BIT_AND_EXPR, type, lh_lb, lh_ub, rh_lb, rh_ub))
3642 : return;
3643 :
3644 5303406 : wide_int maybe_nonzero_lh, mustbe_nonzero_lh;
3645 5303406 : wide_int maybe_nonzero_rh, mustbe_nonzero_rh;
3646 5303406 : wi_set_zero_nonzero_bits (type, lh_lb, lh_ub,
3647 : maybe_nonzero_lh, mustbe_nonzero_lh);
3648 5303406 : wi_set_zero_nonzero_bits (type, rh_lb, rh_ub,
3649 : maybe_nonzero_rh, mustbe_nonzero_rh);
3650 :
3651 5303406 : wide_int new_lb = mustbe_nonzero_lh & mustbe_nonzero_rh;
3652 5303406 : wide_int new_ub = maybe_nonzero_lh & maybe_nonzero_rh;
3653 5303406 : signop sign = TYPE_SIGN (type);
3654 5303406 : unsigned prec = TYPE_PRECISION (type);
3655 : // If both input ranges contain only negative values, we can
3656 : // truncate the result range maximum to the minimum of the
3657 : // input range maxima.
3658 5303406 : if (wi::lt_p (lh_ub, 0, sign) && wi::lt_p (rh_ub, 0, sign))
3659 : {
3660 47412 : new_ub = wi::min (new_ub, lh_ub, sign);
3661 47412 : new_ub = wi::min (new_ub, rh_ub, sign);
3662 : }
3663 : // If either input range contains only non-negative values
3664 : // we can truncate the result range maximum to the respective
3665 : // maximum of the input range.
3666 5303406 : if (wi::ge_p (lh_lb, 0, sign))
3667 4568351 : new_ub = wi::min (new_ub, lh_ub, sign);
3668 5303406 : if (wi::ge_p (rh_lb, 0, sign))
3669 5083157 : new_ub = wi::min (new_ub, rh_ub, sign);
3670 : // PR68217: In case of signed & sign-bit-CST should
3671 : // result in [-INF, 0] instead of [-INF, INF].
3672 5303406 : if (wi::gt_p (new_lb, new_ub, sign))
3673 : {
3674 55880 : wide_int sign_bit = wi::set_bit_in_zero (prec - 1, prec);
3675 55880 : if (sign == SIGNED
3676 55880 : && ((wi::eq_p (lh_lb, lh_ub)
3677 66 : && !wi::cmps (lh_lb, sign_bit))
3678 55880 : || (wi::eq_p (rh_lb, rh_ub)
3679 0 : && !wi::cmps (rh_lb, sign_bit))))
3680 : {
3681 0 : new_lb = wi::min_value (prec, sign);
3682 0 : new_ub = wi::zero (prec);
3683 : }
3684 55880 : }
3685 : // If the limits got swapped around, return varying.
3686 5303406 : if (wi::gt_p (new_lb, new_ub,sign))
3687 : {
3688 55880 : if (sign == SIGNED
3689 55880 : && wi_optimize_signed_bitwise_op (r, type,
3690 : lh_lb, lh_ub,
3691 : rh_lb, rh_ub))
3692 3794 : return;
3693 52086 : r.set_varying (type);
3694 : }
3695 : else
3696 5247526 : value_range_with_overflow (r, type, new_lb, new_ub);
3697 5303406 : }
3698 :
3699 : static void
3700 531494 : set_nonzero_range_from_mask (irange &r, tree type, const irange &lhs)
3701 : {
3702 531494 : if (lhs.undefined_p () || contains_zero_p (lhs))
3703 282572 : r.set_varying (type);
3704 : else
3705 248922 : r.set_nonzero (type);
3706 531494 : }
3707 :
3708 : /* Find out smallest RES where RES > VAL && (RES & MASK) == RES, if any
3709 : (otherwise return VAL). VAL and MASK must be zero-extended for
3710 : precision PREC. If SGNBIT is non-zero, first xor VAL with SGNBIT
3711 : (to transform signed values into unsigned) and at the end xor
3712 : SGNBIT back. */
3713 :
3714 : wide_int
3715 36286 : masked_increment (const wide_int &val_in, const wide_int &mask,
3716 : const wide_int &sgnbit, unsigned int prec)
3717 : {
3718 36286 : wide_int bit = wi::one (prec), res;
3719 36286 : unsigned int i;
3720 :
3721 36286 : wide_int val = val_in ^ sgnbit;
3722 651075 : for (i = 0; i < prec; i++, bit += bit)
3723 : {
3724 604024 : res = mask;
3725 604024 : if ((res & bit) == 0)
3726 516834 : continue;
3727 87190 : res = bit - 1;
3728 87190 : res = wi::bit_and_not (val + bit, res);
3729 87190 : res &= mask;
3730 87190 : if (wi::gtu_p (res, val))
3731 25521 : return res ^ sgnbit;
3732 : }
3733 10765 : return val ^ sgnbit;
3734 36286 : }
3735 :
3736 : // This was shamelessly stolen from register_edge_assert_for_2 and
3737 : // adjusted to work with iranges.
3738 :
3739 : void
3740 3304334 : operator_bitwise_and::simple_op1_range_solver (irange &r, tree type,
3741 : const irange &lhs,
3742 : const irange &op2) const
3743 : {
3744 3304334 : if (!op2.singleton_p ())
3745 : {
3746 530571 : set_nonzero_range_from_mask (r, type, lhs);
3747 1067817 : return;
3748 : }
3749 2773763 : unsigned int nprec = TYPE_PRECISION (type);
3750 2773763 : wide_int cst2v = op2.lower_bound ();
3751 2773763 : bool cst2n = wi::neg_p (cst2v, TYPE_SIGN (type));
3752 2773763 : wide_int sgnbit;
3753 2773763 : if (cst2n)
3754 567296 : sgnbit = wi::set_bit_in_zero (nprec - 1, nprec);
3755 : else
3756 2206467 : sgnbit = wi::zero (nprec);
3757 :
3758 : // Solve [lhs.lower_bound (), +INF] = x & MASK.
3759 : //
3760 : // Minimum unsigned value for >= if (VAL & CST2) == VAL is VAL and
3761 : // maximum unsigned value is ~0. For signed comparison, if CST2
3762 : // doesn't have the most significant bit set, handle it similarly. If
3763 : // CST2 has MSB set, the minimum is the same, and maximum is ~0U/2.
3764 2773763 : wide_int valv = lhs.lower_bound ();
3765 2773763 : wide_int minv = valv & cst2v, maxv;
3766 2773763 : bool we_know_nothing = false;
3767 2773763 : if (minv != valv)
3768 : {
3769 : // If (VAL & CST2) != VAL, X & CST2 can't be equal to VAL.
3770 8361 : minv = masked_increment (valv, cst2v, sgnbit, nprec);
3771 8361 : if (minv == valv)
3772 : {
3773 : // If we can't determine anything on this bound, fall
3774 : // through and conservatively solve for the other end point.
3775 2773763 : we_know_nothing = true;
3776 : }
3777 : }
3778 4980230 : maxv = wi::mask (nprec - (cst2n ? 1 : 0), false, nprec);
3779 2773763 : if (we_know_nothing)
3780 4090 : r.set_varying (type);
3781 : else
3782 2769673 : create_possibly_reversed_range (r, type, minv, maxv);
3783 :
3784 : // Solve [-INF, lhs.upper_bound ()] = x & MASK.
3785 : //
3786 : // Minimum unsigned value for <= is 0 and maximum unsigned value is
3787 : // VAL | ~CST2 if (VAL & CST2) == VAL. Otherwise, find smallest
3788 : // VAL2 where
3789 : // VAL2 > VAL && (VAL2 & CST2) == VAL2 and use (VAL2 - 1) | ~CST2
3790 : // as maximum.
3791 : // For signed comparison, if CST2 doesn't have most significant bit
3792 : // set, handle it similarly. If CST2 has MSB set, the maximum is
3793 : // the same and minimum is INT_MIN.
3794 2773763 : valv = lhs.upper_bound ();
3795 2773763 : minv = valv & cst2v;
3796 2773763 : if (minv == valv)
3797 2745838 : maxv = valv;
3798 : else
3799 : {
3800 27925 : maxv = masked_increment (valv, cst2v, sgnbit, nprec);
3801 27925 : if (maxv == valv)
3802 : {
3803 : // If we couldn't determine anything on either bound, return
3804 : // undefined.
3805 6675 : if (we_know_nothing)
3806 3117 : r.set_undefined ();
3807 6675 : return;
3808 : }
3809 21250 : maxv -= 1;
3810 : }
3811 2767088 : maxv |= ~cst2v;
3812 2767088 : minv = sgnbit;
3813 2767088 : int_range<2> upper_bits;
3814 2767088 : create_possibly_reversed_range (upper_bits, type, minv, maxv);
3815 2767088 : r.intersect (upper_bits);
3816 2773763 : }
3817 :
3818 : bool
3819 3372360 : operator_bitwise_and::op1_range (irange &r, tree type,
3820 : const irange &lhs,
3821 : const irange &op2,
3822 : relation_trio) const
3823 : {
3824 3372360 : if (lhs.undefined_p ())
3825 : return false;
3826 3372360 : if (types_compatible_p (type, boolean_type_node))
3827 797464 : return op_logical_and.op1_range (r, type, lhs, op2);
3828 :
3829 2574896 : r.set_undefined ();
3830 5879230 : for (unsigned i = 0; i < lhs.num_pairs (); ++i)
3831 : {
3832 6608668 : int_range_max chunk (lhs.type (),
3833 6608668 : lhs.lower_bound (i),
3834 6608668 : lhs.upper_bound (i));
3835 3304334 : int_range_max res;
3836 3304334 : simple_op1_range_solver (res, type, chunk, op2);
3837 3304334 : r.union_ (res);
3838 3304334 : }
3839 2574896 : if (r.undefined_p ())
3840 923 : set_nonzero_range_from_mask (r, type, lhs);
3841 :
3842 : // For MASK == op1 & MASK, all the bits in MASK must be set in op1.
3843 2574896 : wide_int mask;
3844 2574896 : if (lhs == op2 && lhs.singleton_p (mask))
3845 : {
3846 347519 : r.update_bitmask (irange_bitmask (mask, ~mask));
3847 347519 : return true;
3848 : }
3849 :
3850 2227377 : if (!op2.singleton_p (mask))
3851 : return true;
3852 :
3853 : // For 0 = op1 & MASK, op1 is ~MASK.
3854 1749478 : if (lhs.zero_p ())
3855 : {
3856 638917 : wide_int nz = wi::bit_not (op2.get_nonzero_bits ());
3857 638917 : int_range<2> tmp (type);
3858 638917 : tmp.set_nonzero_bits (nz);
3859 638917 : r.intersect (tmp);
3860 638917 : }
3861 :
3862 1749478 : irange_bitmask lhs_bm = lhs.get_bitmask ();
3863 : // given [5,7] mask 0x3 value 0x4 = N & [7, 7] mask 0x0 value 0x7
3864 : // Nothing is known about the bits not specified in the mask value (op2),
3865 : // Start with the mask, 1's will occur where values were masked.
3866 1749478 : wide_int op1_mask = ~mask;
3867 : // Any bits that are unknown on the LHS are also unknown in op1,
3868 : // so union the current mask with the LHS mask.
3869 1749478 : op1_mask |= lhs_bm.mask ();
3870 : // The resulting zeros correspond to known bits in the LHS mask, and
3871 : // the LHS value should tell us what they are. Mask off any
3872 : // extraneous values thats are not convered by the mask.
3873 1749478 : wide_int op1_value = lhs_bm.value () & ~op1_mask;
3874 1749478 : irange_bitmask op1_bm (op1_value, op1_mask);
3875 : // Intersect this mask with anything already known about the value.
3876 : // A return valueof false indicated the bitmask is an UNDEFINED range.
3877 1749478 : if (op1_bm.intersect (r.get_bitmask ()))
3878 1749478 : r.update_bitmask (op1_bm);
3879 : else
3880 0 : r.set_undefined ();
3881 1749478 : return true;
3882 4324374 : }
3883 :
3884 : bool
3885 875811 : operator_bitwise_and::op2_range (irange &r, tree type,
3886 : const irange &lhs,
3887 : const irange &op1,
3888 : relation_trio) const
3889 : {
3890 875811 : return operator_bitwise_and::op1_range (r, type, lhs, op1);
3891 : }
3892 :
3893 :
3894 : class operator_logical_or : public range_operator
3895 : {
3896 : using range_operator::fold_range;
3897 : using range_operator::op1_range;
3898 : using range_operator::op2_range;
3899 : public:
3900 : bool fold_range (irange &r, tree type,
3901 : const irange &lh,
3902 : const irange &rh,
3903 : relation_trio rel = TRIO_VARYING) const final override;
3904 : bool op1_range (irange &r, tree type,
3905 : const irange &lhs,
3906 : const irange &op2,
3907 : relation_trio rel = TRIO_VARYING) const final override;
3908 : bool op2_range (irange &r, tree type,
3909 : const irange &lhs,
3910 : const irange &op1,
3911 : relation_trio rel = TRIO_VARYING) const final override;
3912 : // Check compatibility of all operands.
3913 0 : bool operand_check_p (tree t1, tree t2, tree t3) const final override
3914 0 : { return range_compatible_p (t1, t2) && range_compatible_p (t1, t3); }
3915 : } op_logical_or;
3916 :
3917 : bool
3918 0 : operator_logical_or::fold_range (irange &r, tree type ATTRIBUTE_UNUSED,
3919 : const irange &lh,
3920 : const irange &rh,
3921 : relation_trio) const
3922 : {
3923 0 : if (empty_range_varying (r, type, lh, rh))
3924 0 : return true;
3925 :
3926 0 : r = lh;
3927 0 : r.union_ (rh);
3928 0 : return true;
3929 : }
3930 :
3931 : bool
3932 302659 : operator_logical_or::op1_range (irange &r, tree type,
3933 : const irange &lhs,
3934 : const irange &op2 ATTRIBUTE_UNUSED,
3935 : relation_trio) const
3936 : {
3937 302659 : switch (get_bool_state (r, lhs, type))
3938 : {
3939 183174 : case BRS_FALSE:
3940 : // A false result means both sides of the OR must be false.
3941 183174 : r = range_false (type);
3942 183174 : break;
3943 119485 : default:
3944 : // Any other result means only one side has to be true, the
3945 : // other side can be anything. so we can't be sure of any result
3946 : // here.
3947 119485 : r = range_true_and_false (type);
3948 119485 : break;
3949 : }
3950 302659 : return true;
3951 : }
3952 :
3953 : bool
3954 0 : operator_logical_or::op2_range (irange &r, tree type,
3955 : const irange &lhs,
3956 : const irange &op1,
3957 : relation_trio) const
3958 : {
3959 0 : return operator_logical_or::op1_range (r, type, lhs, op1);
3960 : }
3961 :
3962 :
3963 : void
3964 2355597 : operator_bitwise_or::update_bitmask (irange &r, const irange &lh,
3965 : const irange &rh) const
3966 : {
3967 2355597 : update_known_bitmask (r, BIT_IOR_EXPR, lh, rh);
3968 2355597 : }
3969 :
3970 : void
3971 6809104 : operator_bitwise_or::wi_fold (irange &r, tree type,
3972 : const wide_int &lh_lb,
3973 : const wide_int &lh_ub,
3974 : const wide_int &rh_lb,
3975 : const wide_int &rh_ub) const
3976 : {
3977 6809104 : if (wi_optimize_and_or (r, BIT_IOR_EXPR, type, lh_lb, lh_ub, rh_lb, rh_ub))
3978 6123371 : return;
3979 :
3980 863497 : wide_int maybe_nonzero_lh, mustbe_nonzero_lh;
3981 863497 : wide_int maybe_nonzero_rh, mustbe_nonzero_rh;
3982 863497 : wi_set_zero_nonzero_bits (type, lh_lb, lh_ub,
3983 : maybe_nonzero_lh, mustbe_nonzero_lh);
3984 863497 : wi_set_zero_nonzero_bits (type, rh_lb, rh_ub,
3985 : maybe_nonzero_rh, mustbe_nonzero_rh);
3986 863497 : wide_int new_lb = mustbe_nonzero_lh | mustbe_nonzero_rh;
3987 863497 : wide_int new_ub = maybe_nonzero_lh | maybe_nonzero_rh;
3988 863497 : signop sign = TYPE_SIGN (type);
3989 : // If the input ranges contain only positive values we can
3990 : // truncate the minimum of the result range to the maximum
3991 : // of the input range minima.
3992 863497 : if (wi::ge_p (lh_lb, 0, sign)
3993 863497 : && wi::ge_p (rh_lb, 0, sign))
3994 : {
3995 656604 : new_lb = wi::max (new_lb, lh_lb, sign);
3996 656604 : new_lb = wi::max (new_lb, rh_lb, sign);
3997 : }
3998 : // If either input range contains only negative values
3999 : // we can truncate the minimum of the result range to the
4000 : // respective minimum range.
4001 863497 : if (wi::lt_p (lh_ub, 0, sign))
4002 19979 : new_lb = wi::max (new_lb, lh_lb, sign);
4003 863497 : if (wi::lt_p (rh_ub, 0, sign))
4004 10152 : new_lb = wi::max (new_lb, rh_lb, sign);
4005 : // If the limits got swapped around, return a conservative range.
4006 863497 : if (wi::gt_p (new_lb, new_ub, sign))
4007 : {
4008 : // Make sure that nonzero|X is nonzero.
4009 177764 : if (wi::gt_p (lh_lb, 0, sign)
4010 173201 : || wi::gt_p (rh_lb, 0, sign)
4011 119956 : || wi::lt_p (lh_ub, 0, sign)
4012 297720 : || wi::lt_p (rh_ub, 0, sign))
4013 57808 : r.set_nonzero (type);
4014 119956 : else if (sign == SIGNED
4015 119956 : && wi_optimize_signed_bitwise_op (r, type,
4016 : lh_lb, lh_ub,
4017 : rh_lb, rh_ub))
4018 : return;
4019 : else
4020 117505 : r.set_varying (type);
4021 175313 : return;
4022 : }
4023 685733 : value_range_with_overflow (r, type, new_lb, new_ub);
4024 863527 : }
4025 :
4026 : bool
4027 553768 : operator_bitwise_or::op1_range (irange &r, tree type,
4028 : const irange &lhs,
4029 : const irange &op2,
4030 : relation_trio) const
4031 : {
4032 553768 : if (lhs.undefined_p ())
4033 : return false;
4034 : // If this is really a logical wi_fold, call that.
4035 553768 : if (types_compatible_p (type, boolean_type_node))
4036 302659 : return op_logical_or.op1_range (r, type, lhs, op2);
4037 :
4038 251109 : if (lhs.zero_p ())
4039 : {
4040 77807 : r.set_zero (type);
4041 77807 : return true;
4042 : }
4043 :
4044 : // if (A < 0 && B < 0)
4045 : // Sometimes gets translated to
4046 : // _1 = A | B
4047 : // if (_1 < 0))
4048 : // It is useful for ranger to recognize a positive LHS means the RHS
4049 : // operands are also positive when dealing with the ELSE range..
4050 242183 : if (TYPE_SIGN (type) == SIGNED && wi::ge_p (lhs.lower_bound (), 0, SIGNED))
4051 : {
4052 27386 : unsigned prec = TYPE_PRECISION (type);
4053 27386 : r.set (type, wi::zero (prec), wi::max_value (prec, SIGNED));
4054 27386 : return true;
4055 : }
4056 145916 : r.set_varying (type);
4057 145916 : return true;
4058 : }
4059 :
4060 : bool
4061 275730 : operator_bitwise_or::op2_range (irange &r, tree type,
4062 : const irange &lhs,
4063 : const irange &op1,
4064 : relation_trio) const
4065 : {
4066 275730 : return operator_bitwise_or::op1_range (r, type, lhs, op1);
4067 : }
4068 :
4069 : void
4070 83106 : operator_bitwise_xor::update_bitmask (irange &r, const irange &lh,
4071 : const irange &rh) const
4072 : {
4073 83106 : update_known_bitmask (r, BIT_XOR_EXPR, lh, rh);
4074 83106 : }
4075 :
4076 : bool
4077 284582 : operator_bitwise_xor::fold_range (irange &r, tree type,
4078 : const irange &lh, const irange &rh,
4079 : relation_trio rel) const
4080 : {
4081 : // Handle X ^ UNDEFINED = UNDEFINED.
4082 284582 : if (lh.undefined_p () || rh.undefined_p ())
4083 : {
4084 396 : r.set_undefined ();
4085 396 : return true;
4086 : }
4087 :
4088 : // Next, handle X ^ X == [0, 0].
4089 284186 : if (rel.op1_op2 () == VREL_EQ)
4090 : {
4091 40 : r.set_zero (type);
4092 40 : return true;
4093 : }
4094 :
4095 : // If either operand is VARYING, the result is VARYING.
4096 284146 : if (lh.varying_p () || rh.varying_p ())
4097 : {
4098 : // If the operands are not equal, zero is not possible.
4099 199124 : if (rel.op1_op2 () != VREL_NE)
4100 198155 : r.set_varying (type);
4101 : else
4102 969 : r.set_nonzero (type);
4103 199124 : return true;
4104 : }
4105 :
4106 : // Now deal with X ^ 0 == X.
4107 85022 : if (lh.zero_p ())
4108 : {
4109 1485 : r = rh;
4110 1485 : return true;
4111 : }
4112 83537 : if (rh.zero_p ())
4113 : {
4114 431 : r = lh;
4115 431 : return true;
4116 : }
4117 :
4118 : // Start with the legacy range. This can sometimes pick up values
4119 : // when there are a lot of subranges and fold_range aggregates them.
4120 83106 : bool res = range_operator::fold_range (r, type, lh, rh, rel);
4121 :
4122 : // Calculate the XOR identity : x ^ y = (x | y) & ~(x & y)
4123 : // AND and OR are already much better optimized.
4124 83106 : int_range_max tmp1, tmp2, tmp3, new_result;
4125 83106 : int_range<2> varying;
4126 83106 : varying.set_varying (type);
4127 :
4128 83106 : if (m_or.fold_range (tmp1, type, lh, rh, rel)
4129 83106 : && m_and.fold_range (tmp2, type, lh, rh, rel)
4130 83106 : && m_not.fold_range (tmp3, type, tmp2, varying, rel)
4131 166212 : && m_and.fold_range (new_result, type, tmp1, tmp3, rel))
4132 : {
4133 : // If the operands are not equal, or the LH does not contain any
4134 : // element of the RH, zero is not possible.
4135 83106 : tmp1 = lh;
4136 83106 : if (rel.op1_op2 () == VREL_NE
4137 83106 : || (tmp1.intersect (rh) && tmp1.undefined_p ()))
4138 : {
4139 32303 : tmp1.set_nonzero (type);
4140 32303 : new_result.intersect (tmp1);
4141 : }
4142 :
4143 : // Combine with the legacy range if there was one.
4144 83106 : if (res)
4145 83106 : r.intersect (new_result);
4146 : else
4147 0 : r = new_result;
4148 83106 : return true;
4149 : }
4150 : return res;
4151 83106 : }
4152 :
4153 : void
4154 165061 : operator_bitwise_xor::wi_fold (irange &r, tree type,
4155 : const wide_int &lh_lb,
4156 : const wide_int &lh_ub,
4157 : const wide_int &rh_lb,
4158 : const wide_int &rh_ub) const
4159 : {
4160 165061 : signop sign = TYPE_SIGN (type);
4161 165061 : wide_int maybe_nonzero_lh, mustbe_nonzero_lh;
4162 165061 : wide_int maybe_nonzero_rh, mustbe_nonzero_rh;
4163 165061 : wi_set_zero_nonzero_bits (type, lh_lb, lh_ub,
4164 : maybe_nonzero_lh, mustbe_nonzero_lh);
4165 165061 : wi_set_zero_nonzero_bits (type, rh_lb, rh_ub,
4166 : maybe_nonzero_rh, mustbe_nonzero_rh);
4167 :
4168 495183 : wide_int result_zero_bits = ((mustbe_nonzero_lh & mustbe_nonzero_rh)
4169 495183 : | ~(maybe_nonzero_lh | maybe_nonzero_rh));
4170 165061 : wide_int result_one_bits
4171 330122 : = (wi::bit_and_not (mustbe_nonzero_lh, maybe_nonzero_rh)
4172 330122 : | wi::bit_and_not (mustbe_nonzero_rh, maybe_nonzero_lh));
4173 165061 : wide_int new_ub = ~result_zero_bits;
4174 165061 : wide_int new_lb = result_one_bits;
4175 :
4176 : // If the range has all positive or all negative values, the result
4177 : // is better than VARYING.
4178 165061 : if (wi::lt_p (new_lb, 0, sign) || wi::ge_p (new_ub, 0, sign))
4179 158653 : value_range_with_overflow (r, type, new_lb, new_ub);
4180 6408 : else if (sign == SIGNED
4181 6408 : && wi_optimize_signed_bitwise_op (r, type,
4182 : lh_lb, lh_ub,
4183 : rh_lb, rh_ub))
4184 : ; /* Do nothing. */
4185 : else
4186 895 : r.set_varying (type);
4187 :
4188 : /* Furthermore, XOR is non-zero if its arguments can't be equal. */
4189 165061 : if (wi::lt_p (lh_ub, rh_lb, sign)
4190 107971 : || wi::lt_p (rh_ub, lh_lb, sign)
4191 252626 : || wi::ne_p (result_one_bits, 0))
4192 : {
4193 77496 : int_range<2> tmp;
4194 77496 : tmp.set_nonzero (type);
4195 77496 : r.intersect (tmp);
4196 77496 : }
4197 165061 : }
4198 :
4199 : bool
4200 83106 : operator_bitwise_xor::op1_op2_relation_effect (irange &lhs_range,
4201 : tree type,
4202 : const irange &,
4203 : const irange &,
4204 : relation_kind rel) const
4205 : {
4206 83106 : if (rel == VREL_VARYING)
4207 : return false;
4208 :
4209 3738 : int_range<2> rel_range;
4210 :
4211 3738 : switch (rel)
4212 : {
4213 0 : case VREL_EQ:
4214 0 : rel_range.set_zero (type);
4215 0 : break;
4216 407 : case VREL_NE:
4217 407 : rel_range.set_nonzero (type);
4218 407 : break;
4219 : default:
4220 : return false;
4221 : }
4222 :
4223 407 : lhs_range.intersect (rel_range);
4224 407 : return true;
4225 3738 : }
4226 :
4227 : bool
4228 74328 : operator_bitwise_xor::op1_range (irange &r, tree type,
4229 : const irange &lhs,
4230 : const irange &op2,
4231 : relation_trio) const
4232 : {
4233 74328 : if (lhs.undefined_p () || lhs.varying_p ())
4234 : {
4235 7642 : r = lhs;
4236 7642 : return true;
4237 : }
4238 66686 : if (types_compatible_p (type, boolean_type_node))
4239 : {
4240 1699 : switch (get_bool_state (r, lhs, type))
4241 : {
4242 761 : case BRS_TRUE:
4243 761 : if (op2.varying_p ())
4244 729 : r.set_varying (type);
4245 32 : else if (op2.zero_p ())
4246 24 : r = range_true (type);
4247 : // See get_bool_state for the rationale
4248 8 : else if (op2.undefined_p () || contains_zero_p (op2))
4249 0 : r = range_true_and_false (type);
4250 : else
4251 8 : r = range_false (type);
4252 : break;
4253 938 : case BRS_FALSE:
4254 938 : r = op2;
4255 938 : break;
4256 : default:
4257 : break;
4258 : }
4259 1699 : return true;
4260 : }
4261 64987 : r.set_varying (type);
4262 64987 : return true;
4263 : }
4264 :
4265 : bool
4266 32434 : operator_bitwise_xor::op2_range (irange &r, tree type,
4267 : const irange &lhs,
4268 : const irange &op1,
4269 : relation_trio) const
4270 : {
4271 32434 : return operator_bitwise_xor::op1_range (r, type, lhs, op1);
4272 : }
4273 :
4274 : class operator_trunc_mod : public range_operator
4275 : {
4276 : using range_operator::op1_range;
4277 : using range_operator::op2_range;
4278 : using range_operator::update_bitmask;
4279 : public:
4280 : virtual void wi_fold (irange &r, tree type,
4281 : const wide_int &lh_lb,
4282 : const wide_int &lh_ub,
4283 : const wide_int &rh_lb,
4284 : const wide_int &rh_ub) const;
4285 : virtual bool op1_range (irange &r, tree type,
4286 : const irange &lhs,
4287 : const irange &op2,
4288 : relation_trio) const;
4289 : virtual bool op2_range (irange &r, tree type,
4290 : const irange &lhs,
4291 : const irange &op1,
4292 : relation_trio) const;
4293 1029057 : void update_bitmask (irange &r, const irange &lh, const irange &rh) const
4294 1029057 : { update_known_bitmask (r, TRUNC_MOD_EXPR, lh, rh); }
4295 : } op_trunc_mod;
4296 :
4297 : void
4298 1265905 : operator_trunc_mod::wi_fold (irange &r, tree type,
4299 : const wide_int &lh_lb,
4300 : const wide_int &lh_ub,
4301 : const wide_int &rh_lb,
4302 : const wide_int &rh_ub) const
4303 : {
4304 1265905 : wide_int new_lb, new_ub, tmp;
4305 1265905 : signop sign = TYPE_SIGN (type);
4306 1265905 : unsigned prec = TYPE_PRECISION (type);
4307 :
4308 : // Mod 0 is undefined.
4309 1265905 : if (wi_zero_p (type, rh_lb, rh_ub))
4310 : {
4311 8692 : r.set_undefined ();
4312 8692 : return;
4313 : }
4314 :
4315 : // Check for constant and try to fold.
4316 1468095 : if (lh_lb == lh_ub && rh_lb == rh_ub)
4317 : {
4318 21352 : wi::overflow_type ov = wi::OVF_NONE;
4319 21352 : tmp = wi::mod_trunc (lh_lb, rh_lb, sign, &ov);
4320 21352 : if (ov == wi::OVF_NONE)
4321 : {
4322 21352 : r = int_range<2> (type, tmp, tmp);
4323 21352 : return;
4324 : }
4325 : }
4326 :
4327 : // ABS (A % B) < ABS (B) and either 0 <= A % B <= A or A <= A % B <= 0.
4328 1235861 : new_ub = rh_ub - 1;
4329 1235861 : if (sign == SIGNED)
4330 : {
4331 528616 : tmp = -1 - rh_lb;
4332 528616 : new_ub = wi::smax (new_ub, tmp);
4333 : }
4334 :
4335 1235861 : if (sign == UNSIGNED)
4336 707245 : new_lb = wi::zero (prec);
4337 : else
4338 : {
4339 528616 : new_lb = -new_ub;
4340 528616 : tmp = lh_lb;
4341 528616 : if (wi::gts_p (tmp, 0))
4342 131221 : tmp = wi::zero (prec);
4343 528640 : new_lb = wi::smax (new_lb, tmp);
4344 : }
4345 1235861 : tmp = lh_ub;
4346 1235861 : if (sign == SIGNED && wi::neg_p (tmp))
4347 26762 : tmp = wi::zero (prec);
4348 1235861 : new_ub = wi::min (new_ub, tmp, sign);
4349 :
4350 1235861 : value_range_with_overflow (r, type, new_lb, new_ub);
4351 1266029 : }
4352 :
4353 : bool
4354 535535 : operator_trunc_mod::op1_range (irange &r, tree type,
4355 : const irange &lhs,
4356 : const irange &,
4357 : relation_trio) const
4358 : {
4359 535535 : if (lhs.undefined_p ())
4360 : return false;
4361 : // PR 91029.
4362 535535 : signop sign = TYPE_SIGN (type);
4363 535535 : unsigned prec = TYPE_PRECISION (type);
4364 : // (a % b) >= x && x > 0 , then a >= x.
4365 535627 : if (wi::gt_p (lhs.lower_bound (), 0, sign))
4366 : {
4367 134552 : r.set (type, lhs.lower_bound (), wi::max_value (prec, sign));
4368 134519 : return true;
4369 : }
4370 : // (a % b) <= x && x < 0 , then a <= x.
4371 401075 : if (wi::lt_p (lhs.upper_bound (), 0, sign))
4372 : {
4373 5447 : r.set (type, wi::min_value (prec, sign), lhs.upper_bound ());
4374 5447 : return true;
4375 : }
4376 : return false;
4377 : }
4378 :
4379 : bool
4380 351051 : operator_trunc_mod::op2_range (irange &r, tree type,
4381 : const irange &lhs,
4382 : const irange &,
4383 : relation_trio) const
4384 : {
4385 351051 : if (lhs.undefined_p ())
4386 : return false;
4387 : // PR 91029.
4388 351051 : signop sign = TYPE_SIGN (type);
4389 351051 : unsigned prec = TYPE_PRECISION (type);
4390 : // (a % b) >= x && x > 0 , then b is in ~[-x, x] for signed
4391 : // or b > x for unsigned.
4392 351084 : if (wi::gt_p (lhs.lower_bound (), 0, sign))
4393 : {
4394 54104 : if (sign == SIGNED)
4395 2181 : r.set (type, wi::neg (lhs.lower_bound ()),
4396 4362 : lhs.lower_bound (), VR_ANTI_RANGE);
4397 51935 : else if (wi::lt_p (lhs.lower_bound (), wi::max_value (prec, sign),
4398 : sign))
4399 51941 : r.set (type, lhs.lower_bound () + 1, wi::max_value (prec, sign));
4400 : else
4401 : return false;
4402 54104 : return true;
4403 : }
4404 : // (a % b) <= x && x < 0 , then b is in ~[x, -x].
4405 296974 : if (wi::lt_p (lhs.upper_bound (), 0, sign))
4406 : {
4407 5288 : if (wi::gt_p (lhs.upper_bound (), wi::min_value (prec, sign), sign))
4408 5288 : r.set (type, lhs.upper_bound (),
4409 10576 : wi::neg (lhs.upper_bound ()), VR_ANTI_RANGE);
4410 : else
4411 : return false;
4412 5288 : return true;
4413 : }
4414 : return false;
4415 : }
4416 :
4417 :
4418 : class operator_logical_not : public range_operator
4419 : {
4420 : using range_operator::fold_range;
4421 : using range_operator::op1_range;
4422 : public:
4423 : bool fold_range (irange &r, tree type,
4424 : const irange &lh,
4425 : const irange &rh,
4426 : relation_trio rel = TRIO_VARYING) const final override;
4427 : bool op1_range (irange &r, tree type,
4428 : const irange &lhs,
4429 : const irange &op2,
4430 : relation_trio rel = TRIO_VARYING) const final override;
4431 : // Check compatibility of LHS and op1.
4432 0 : bool operand_check_p (tree t1, tree t2, tree) const final override
4433 0 : { return range_compatible_p (t1, t2); }
4434 : } op_logical_not;
4435 :
4436 : // Folding a logical NOT, oddly enough, involves doing nothing on the
4437 : // forward pass through. During the initial walk backwards, the
4438 : // logical NOT reversed the desired outcome on the way back, so on the
4439 : // way forward all we do is pass the range forward.
4440 : //
4441 : // b_2 = x_1 < 20
4442 : // b_3 = !b_2
4443 : // if (b_3)
4444 : // to determine the TRUE branch, walking backward
4445 : // if (b_3) if ([1,1])
4446 : // b_3 = !b_2 [1,1] = ![0,0]
4447 : // b_2 = x_1 < 20 [0,0] = x_1 < 20, false, so x_1 == [20, 255]
4448 : // which is the result we are looking for.. so.. pass it through.
4449 :
4450 : bool
4451 241697 : operator_logical_not::fold_range (irange &r, tree type,
4452 : const irange &lh,
4453 : const irange &rh ATTRIBUTE_UNUSED,
4454 : relation_trio) const
4455 : {
4456 241697 : if (empty_range_varying (r, type, lh, rh))
4457 0 : return true;
4458 :
4459 241697 : r = lh;
4460 241697 : if (!lh.varying_p () && !lh.undefined_p ())
4461 50926 : r.invert ();
4462 :
4463 : return true;
4464 : }
4465 :
4466 : bool
4467 26162 : operator_logical_not::op1_range (irange &r,
4468 : tree type,
4469 : const irange &lhs,
4470 : const irange &op2,
4471 : relation_trio) const
4472 : {
4473 : // Logical NOT is involutary...do it again.
4474 26162 : return fold_range (r, type, lhs, op2);
4475 : }
4476 :
4477 : bool
4478 600495 : operator_bitwise_not::fold_range (irange &r, tree type,
4479 : const irange &lh,
4480 : const irange &rh,
4481 : relation_trio) const
4482 : {
4483 600495 : if (empty_range_varying (r, type, lh, rh))
4484 97 : return true;
4485 :
4486 600398 : if (types_compatible_p (type, boolean_type_node))
4487 215535 : return op_logical_not.fold_range (r, type, lh, rh);
4488 :
4489 : // ~X is simply -1 - X.
4490 769726 : int_range<1> minusone (type, wi::minus_one (TYPE_PRECISION (type)),
4491 769726 : wi::minus_one (TYPE_PRECISION (type)));
4492 384863 : return range_op_handler (MINUS_EXPR).fold_range (r, type, minusone, lh);
4493 384863 : }
4494 :
4495 : bool
4496 52040 : operator_bitwise_not::op1_range (irange &r, tree type,
4497 : const irange &lhs,
4498 : const irange &op2,
4499 : relation_trio) const
4500 : {
4501 52040 : if (lhs.undefined_p ())
4502 : return false;
4503 52040 : if (types_compatible_p (type, boolean_type_node))
4504 26162 : return op_logical_not.op1_range (r, type, lhs, op2);
4505 :
4506 : // ~X is -1 - X and since bitwise NOT is involutary...do it again.
4507 25878 : return fold_range (r, type, lhs, op2);
4508 : }
4509 :
4510 : void
4511 0 : operator_bitwise_not::update_bitmask (irange &r, const irange &lh,
4512 : const irange &rh) const
4513 : {
4514 0 : update_known_bitmask (r, BIT_NOT_EXPR, lh, rh);
4515 0 : }
4516 :
4517 :
4518 : bool
4519 306137 : operator_cst::fold_range (irange &r, tree type ATTRIBUTE_UNUSED,
4520 : const irange &lh,
4521 : const irange &rh ATTRIBUTE_UNUSED,
4522 : relation_trio) const
4523 : {
4524 306137 : r = lh;
4525 306137 : return true;
4526 : }
4527 :
4528 :
4529 : // Determine if there is a relationship between LHS and OP1.
4530 :
4531 : relation_kind
4532 905328 : operator_identity::lhs_op1_relation (const irange &lhs,
4533 : const irange &op1 ATTRIBUTE_UNUSED,
4534 : const irange &op2 ATTRIBUTE_UNUSED,
4535 : relation_kind) const
4536 : {
4537 905328 : if (lhs.undefined_p ())
4538 473 : return VREL_VARYING;
4539 : // Simply a copy, so they are equivalent.
4540 : return VREL_EQ;
4541 : }
4542 :
4543 : bool
4544 906047 : operator_identity::fold_range (irange &r, tree type ATTRIBUTE_UNUSED,
4545 : const irange &lh,
4546 : const irange &rh ATTRIBUTE_UNUSED,
4547 : relation_trio) const
4548 : {
4549 906047 : r = lh;
4550 906047 : return true;
4551 : }
4552 :
4553 : bool
4554 292197 : operator_identity::op1_range (irange &r, tree type ATTRIBUTE_UNUSED,
4555 : const irange &lhs,
4556 : const irange &op2 ATTRIBUTE_UNUSED,
4557 : relation_trio) const
4558 : {
4559 292197 : r = lhs;
4560 292197 : return true;
4561 : }
4562 :
4563 :
4564 : class operator_unknown : public range_operator
4565 : {
4566 : using range_operator::fold_range;
4567 : public:
4568 : virtual bool fold_range (irange &r, tree type,
4569 : const irange &op1,
4570 : const irange &op2,
4571 : relation_trio rel = TRIO_VARYING) const;
4572 : } op_unknown;
4573 :
4574 : bool
4575 810635 : operator_unknown::fold_range (irange &r, tree type,
4576 : const irange &lh ATTRIBUTE_UNUSED,
4577 : const irange &rh ATTRIBUTE_UNUSED,
4578 : relation_trio) const
4579 : {
4580 810635 : r.set_varying (type);
4581 810635 : return true;
4582 : }
4583 :
4584 :
4585 : void
4586 80604 : operator_abs::wi_fold (irange &r, tree type,
4587 : const wide_int &lh_lb, const wide_int &lh_ub,
4588 : const wide_int &rh_lb ATTRIBUTE_UNUSED,
4589 : const wide_int &rh_ub ATTRIBUTE_UNUSED) const
4590 : {
4591 80604 : wide_int min, max;
4592 80604 : signop sign = TYPE_SIGN (type);
4593 80604 : unsigned prec = TYPE_PRECISION (type);
4594 :
4595 : // Pass through LH for the easy cases.
4596 80604 : if (sign == UNSIGNED || wi::ge_p (lh_lb, 0, sign))
4597 : {
4598 11782 : r = int_range<1> (type, lh_lb, lh_ub);
4599 11782 : return;
4600 : }
4601 :
4602 : // -TYPE_MIN_VALUE = TYPE_MIN_VALUE with flag_wrapv so we can't get
4603 : // a useful range.
4604 68822 : wide_int min_value = wi::min_value (prec, sign);
4605 68822 : wide_int max_value = wi::max_value (prec, sign);
4606 68822 : if (!TYPE_OVERFLOW_UNDEFINED (type) && wi::eq_p (lh_lb, min_value))
4607 : {
4608 640 : r.set_varying (type);
4609 640 : return;
4610 : }
4611 :
4612 : // ABS_EXPR may flip the range around, if the original range
4613 : // included negative values.
4614 68182 : if (wi::eq_p (lh_lb, min_value))
4615 : {
4616 : // ABS ([-MIN, -MIN]) isn't representable, but we have traditionally
4617 : // returned [-MIN,-MIN] so this preserves that behavior. PR37078
4618 35134 : if (wi::eq_p (lh_ub, min_value))
4619 : {
4620 113 : r = int_range<1> (type, min_value, min_value);
4621 113 : return;
4622 : }
4623 35021 : min = max_value;
4624 : }
4625 : else
4626 33048 : min = wi::abs (lh_lb);
4627 :
4628 68069 : if (wi::eq_p (lh_ub, min_value))
4629 0 : max = max_value;
4630 : else
4631 68069 : max = wi::abs (lh_ub);
4632 :
4633 : // If the range contains zero then we know that the minimum value in the
4634 : // range will be zero.
4635 68069 : if (wi::le_p (lh_lb, 0, sign) && wi::ge_p (lh_ub, 0, sign))
4636 : {
4637 58443 : if (wi::gt_p (min, max, sign))
4638 22147 : max = min;
4639 58443 : min = wi::zero (prec);
4640 : }
4641 : else
4642 : {
4643 : // If the range was reversed, swap MIN and MAX.
4644 9626 : if (wi::gt_p (min, max, sign))
4645 9019 : std::swap (min, max);
4646 : }
4647 :
4648 : // If the new range has its limits swapped around (MIN > MAX), then
4649 : // the operation caused one of them to wrap around. The only thing
4650 : // we know is that the result is positive.
4651 68069 : if (wi::gt_p (min, max, sign))
4652 : {
4653 0 : min = wi::zero (prec);
4654 0 : max = max_value;
4655 : }
4656 68069 : r = int_range<1> (type, min, max);
4657 81357 : }
4658 :
4659 : bool
4660 59988 : operator_abs::op1_range (irange &r, tree type,
4661 : const irange &lhs,
4662 : const irange &op2,
4663 : relation_trio) const
4664 : {
4665 59988 : if (empty_range_varying (r, type, lhs, op2))
4666 0 : return true;
4667 59988 : if (TYPE_UNSIGNED (type))
4668 : {
4669 0 : r = lhs;
4670 0 : return true;
4671 : }
4672 : // Start with the positives because negatives are an impossible result.
4673 59988 : int_range_max positives = range_positives (type);
4674 59988 : positives.intersect (lhs);
4675 59988 : r = positives;
4676 : // Then add the negative of each pair:
4677 : // ABS(op1) = [5,20] would yield op1 => [-20,-5][5,20].
4678 120765 : for (unsigned i = 0; i < positives.num_pairs (); ++i)
4679 60777 : r.union_ (int_range<1> (type,
4680 121554 : -positives.upper_bound (i),
4681 182331 : -positives.lower_bound (i)));
4682 : // With flag_wrapv, -TYPE_MIN_VALUE = TYPE_MIN_VALUE which is
4683 : // unrepresentable. Add -TYPE_MIN_VALUE in this case.
4684 59988 : wide_int min_value = wi::min_value (TYPE_PRECISION (type), TYPE_SIGN (type));
4685 59988 : wide_int lb = lhs.lower_bound ();
4686 59988 : if (!TYPE_OVERFLOW_UNDEFINED (type) && wi::eq_p (lb, min_value))
4687 169 : r.union_ (int_range<2> (type, lb, lb));
4688 59988 : return true;
4689 59988 : }
4690 :
4691 : void
4692 73644 : operator_abs::update_bitmask (irange &r, const irange &lh,
4693 : const irange &rh) const
4694 : {
4695 73644 : update_known_bitmask (r, ABS_EXPR, lh, rh);
4696 73644 : }
4697 :
4698 : class operator_absu : public range_operator
4699 : {
4700 : using range_operator::update_bitmask;
4701 : public:
4702 : virtual void wi_fold (irange &r, tree type,
4703 : const wide_int &lh_lb, const wide_int &lh_ub,
4704 : const wide_int &rh_lb, const wide_int &rh_ub)
4705 : const final override;
4706 : virtual void update_bitmask (irange &r, const irange &lh,
4707 : const irange &rh) const final override;
4708 : } op_absu;
4709 :
4710 : void
4711 13131 : operator_absu::wi_fold (irange &r, tree type,
4712 : const wide_int &lh_lb, const wide_int &lh_ub,
4713 : const wide_int &rh_lb ATTRIBUTE_UNUSED,
4714 : const wide_int &rh_ub ATTRIBUTE_UNUSED) const
4715 : {
4716 13131 : wide_int new_lb, new_ub;
4717 :
4718 : // Pass through VR0 the easy cases.
4719 13131 : if (wi::ges_p (lh_lb, 0))
4720 : {
4721 2473 : new_lb = lh_lb;
4722 2473 : new_ub = lh_ub;
4723 : }
4724 : else
4725 : {
4726 10658 : new_lb = wi::abs (lh_lb);
4727 10658 : new_ub = wi::abs (lh_ub);
4728 :
4729 : // If the range contains zero then we know that the minimum
4730 : // value in the range will be zero.
4731 10658 : if (wi::ges_p (lh_ub, 0))
4732 : {
4733 8195 : if (wi::gtu_p (new_lb, new_ub))
4734 6901 : new_ub = new_lb;
4735 8195 : new_lb = wi::zero (TYPE_PRECISION (type));
4736 : }
4737 : else
4738 2463 : std::swap (new_lb, new_ub);
4739 : }
4740 :
4741 13131 : gcc_checking_assert (TYPE_UNSIGNED (type));
4742 13131 : r = int_range<1> (type, new_lb, new_ub);
4743 13131 : }
4744 :
4745 : void
4746 11753 : operator_absu::update_bitmask (irange &r, const irange &lh,
4747 : const irange &rh) const
4748 : {
4749 11753 : update_known_bitmask (r, ABSU_EXPR, lh, rh);
4750 11753 : }
4751 :
4752 :
4753 : bool
4754 581749 : operator_negate::fold_range (irange &r, tree type,
4755 : const irange &lh,
4756 : const irange &rh,
4757 : relation_trio) const
4758 : {
4759 581749 : if (empty_range_varying (r, type, lh, rh))
4760 932 : return true;
4761 :
4762 : // -X is simply 0 - X.
4763 580817 : int_range<1> zero;
4764 580817 : zero.set_zero (type);
4765 580817 : return range_op_handler (MINUS_EXPR).fold_range (r, type, zero, lh);
4766 580817 : }
4767 :
4768 : bool
4769 72613 : operator_negate::op1_range (irange &r, tree type,
4770 : const irange &lhs,
4771 : const irange &op2,
4772 : relation_trio) const
4773 : {
4774 : // NEGATE is involutory.
4775 72613 : return fold_range (r, type, lhs, op2);
4776 : }
4777 :
4778 :
4779 : bool
4780 0 : operator_addr_expr::fold_range (irange &r, tree type,
4781 : const irange &lh,
4782 : const irange &rh,
4783 : relation_trio) const
4784 : {
4785 0 : if (empty_range_varying (r, type, lh, rh))
4786 0 : return true;
4787 :
4788 : // Return a non-null pointer of the LHS type (passed in op2).
4789 0 : if (lh.zero_p ())
4790 0 : r.set_zero (type);
4791 0 : else if (lh.undefined_p () || contains_zero_p (lh))
4792 0 : r.set_varying (type);
4793 : else
4794 0 : r.set_nonzero (type);
4795 : return true;
4796 : }
4797 :
4798 : bool
4799 0 : operator_addr_expr::op1_range (irange &r, tree type,
4800 : const irange &lhs,
4801 : const irange &op2,
4802 : relation_trio) const
4803 : {
4804 0 : if (empty_range_varying (r, type, lhs, op2))
4805 0 : return true;
4806 :
4807 : // Return a non-null pointer of the LHS type (passed in op2), but only
4808 : // if we cant overflow, eitherwise a no-zero offset could wrap to zero.
4809 : // See PR 111009.
4810 0 : if (!lhs.undefined_p () && !contains_zero_p (lhs) && TYPE_OVERFLOW_UNDEFINED (type))
4811 0 : r.set_nonzero (type);
4812 : else
4813 0 : r.set_varying (type);
4814 : return true;
4815 : }
4816 :
4817 : // Initialize any integral operators to the primary table
4818 :
4819 : void
4820 284591 : range_op_table::initialize_integral_ops ()
4821 : {
4822 284591 : set (TRUNC_DIV_EXPR, op_trunc_div);
4823 284591 : set (FLOOR_DIV_EXPR, op_floor_div);
4824 284591 : set (ROUND_DIV_EXPR, op_round_div);
4825 284591 : set (CEIL_DIV_EXPR, op_ceil_div);
4826 284591 : set (EXACT_DIV_EXPR, op_exact_div);
4827 284591 : set (LSHIFT_EXPR, op_lshift);
4828 284591 : set (RSHIFT_EXPR, op_rshift);
4829 284591 : set (TRUTH_AND_EXPR, op_logical_and);
4830 284591 : set (TRUTH_OR_EXPR, op_logical_or);
4831 284591 : set (TRUNC_MOD_EXPR, op_trunc_mod);
4832 284591 : set (TRUTH_NOT_EXPR, op_logical_not);
4833 284591 : set (IMAGPART_EXPR, op_unknown);
4834 284591 : set (REALPART_EXPR, op_unknown);
4835 284591 : set (ABSU_EXPR, op_absu);
4836 284591 : set (OP_WIDEN_MULT_SIGNED, op_widen_mult_signed);
4837 284591 : set (OP_WIDEN_MULT_UNSIGNED, op_widen_mult_unsigned);
4838 284591 : set (OP_WIDEN_MULT_SIGNED_UNSIGNED, op_widen_mult_signed_unsigned);
4839 284591 : set (OP_WIDEN_PLUS_SIGNED, op_widen_plus_signed);
4840 284591 : set (OP_WIDEN_PLUS_UNSIGNED, op_widen_plus_unsigned);
4841 :
4842 284591 : }
4843 :
4844 : bool
4845 41519 : operator_plus::overflow_free_p (const irange &lh, const irange &rh,
4846 : relation_trio) const
4847 : {
4848 41519 : if (lh.undefined_p () || rh.undefined_p ())
4849 : return false;
4850 :
4851 41519 : tree type = lh.type ();
4852 41519 : if (TYPE_OVERFLOW_UNDEFINED (type))
4853 : return true;
4854 :
4855 10712 : wi::overflow_type ovf;
4856 10712 : signop sgn = TYPE_SIGN (type);
4857 10712 : wide_int wmax0 = lh.upper_bound ();
4858 10712 : wide_int wmax1 = rh.upper_bound ();
4859 10712 : wi::add (wmax0, wmax1, sgn, &ovf);
4860 10712 : if (ovf != wi::OVF_NONE)
4861 : return false;
4862 :
4863 1288 : if (TYPE_UNSIGNED (type))
4864 : return true;
4865 :
4866 372 : wide_int wmin0 = lh.lower_bound ();
4867 372 : wide_int wmin1 = rh.lower_bound ();
4868 372 : wi::add (wmin0, wmin1, sgn, &ovf);
4869 372 : if (ovf != wi::OVF_NONE)
4870 261 : return false;
4871 :
4872 : return true;
4873 11084 : }
4874 :
4875 : bool
4876 31 : operator_minus::overflow_free_p (const irange &lh, const irange &rh,
4877 : relation_trio) const
4878 : {
4879 31 : if (lh.undefined_p () || rh.undefined_p ())
4880 : return false;
4881 :
4882 31 : tree type = lh.type ();
4883 31 : if (TYPE_OVERFLOW_UNDEFINED (type))
4884 : return true;
4885 :
4886 10 : wi::overflow_type ovf;
4887 10 : signop sgn = TYPE_SIGN (type);
4888 10 : wide_int wmin0 = lh.lower_bound ();
4889 10 : wide_int wmax1 = rh.upper_bound ();
4890 10 : wi::sub (wmin0, wmax1, sgn, &ovf);
4891 10 : if (ovf != wi::OVF_NONE)
4892 : return false;
4893 :
4894 7 : if (TYPE_UNSIGNED (type))
4895 : return true;
4896 :
4897 6 : wide_int wmax0 = lh.upper_bound ();
4898 6 : wide_int wmin1 = rh.lower_bound ();
4899 6 : wi::sub (wmax0, wmin1, sgn, &ovf);
4900 6 : if (ovf != wi::OVF_NONE)
4901 0 : return false;
4902 :
4903 : return true;
4904 16 : }
4905 :
4906 : bool
4907 3260 : operator_mult::overflow_free_p (const irange &lh, const irange &rh,
4908 : relation_trio) const
4909 : {
4910 3260 : if (lh.undefined_p () || rh.undefined_p ())
4911 : return false;
4912 :
4913 3260 : tree type = lh.type ();
4914 3260 : if (TYPE_OVERFLOW_UNDEFINED (type))
4915 : return true;
4916 :
4917 2778 : wi::overflow_type ovf;
4918 2778 : signop sgn = TYPE_SIGN (type);
4919 2778 : wide_int wmax0 = lh.upper_bound ();
4920 2778 : wide_int wmax1 = rh.upper_bound ();
4921 2778 : wi::mul (wmax0, wmax1, sgn, &ovf);
4922 2778 : if (ovf != wi::OVF_NONE)
4923 : return false;
4924 :
4925 105 : if (TYPE_UNSIGNED (type))
4926 : return true;
4927 :
4928 22 : wide_int wmin0 = lh.lower_bound ();
4929 22 : wide_int wmin1 = rh.lower_bound ();
4930 22 : wi::mul (wmin0, wmin1, sgn, &ovf);
4931 22 : if (ovf != wi::OVF_NONE)
4932 : return false;
4933 :
4934 22 : wi::mul (wmin0, wmax1, sgn, &ovf);
4935 22 : if (ovf != wi::OVF_NONE)
4936 : return false;
4937 :
4938 22 : wi::mul (wmax0, wmin1, sgn, &ovf);
4939 22 : if (ovf != wi::OVF_NONE)
4940 : return false;
4941 :
4942 : return true;
4943 2800 : }
4944 :
4945 : #if CHECKING_P
4946 : #include "selftest.h"
4947 :
4948 : namespace selftest
4949 : {
4950 : #define INT(x) wi::shwi ((x), TYPE_PRECISION (integer_type_node))
4951 : #define UINT(x) wi::uhwi ((x), TYPE_PRECISION (unsigned_type_node))
4952 : #define INT16(x) wi::shwi ((x), TYPE_PRECISION (short_integer_type_node))
4953 : #define UINT16(x) wi::uhwi ((x), TYPE_PRECISION (short_unsigned_type_node))
4954 : #define SCHAR(x) wi::shwi ((x), TYPE_PRECISION (signed_char_type_node))
4955 : #define UCHAR(x) wi::uhwi ((x), TYPE_PRECISION (unsigned_char_type_node))
4956 :
4957 : static void
4958 4 : range_op_cast_tests ()
4959 : {
4960 4 : int_range<2> r0, r1, r2, rold;
4961 4 : r0.set_varying (integer_type_node);
4962 4 : wide_int maxint = r0.upper_bound ();
4963 :
4964 : // If a range is in any way outside of the range for the converted
4965 : // to range, default to the range for the new type.
4966 4 : r0.set_varying (short_integer_type_node);
4967 4 : wide_int minshort = r0.lower_bound ();
4968 4 : wide_int maxshort = r0.upper_bound ();
4969 4 : if (TYPE_PRECISION (integer_type_node)
4970 4 : > TYPE_PRECISION (short_integer_type_node))
4971 : {
4972 8 : r1 = int_range<1> (integer_type_node,
4973 4 : wi::zero (TYPE_PRECISION (integer_type_node)),
4974 8 : maxint);
4975 4 : range_cast (r1, short_integer_type_node);
4976 4 : ASSERT_TRUE (r1.lower_bound () == minshort
4977 : && r1.upper_bound() == maxshort);
4978 : }
4979 :
4980 : // (unsigned char)[-5,-1] => [251,255].
4981 4 : r0 = rold = int_range<1> (signed_char_type_node, SCHAR (-5), SCHAR (-1));
4982 4 : range_cast (r0, unsigned_char_type_node);
4983 4 : ASSERT_TRUE (r0 == int_range<1> (unsigned_char_type_node,
4984 : UCHAR (251), UCHAR (255)));
4985 4 : range_cast (r0, signed_char_type_node);
4986 4 : ASSERT_TRUE (r0 == rold);
4987 :
4988 : // (signed char)[15, 150] => [-128,-106][15,127].
4989 4 : r0 = rold = int_range<1> (unsigned_char_type_node, UCHAR (15), UCHAR (150));
4990 4 : range_cast (r0, signed_char_type_node);
4991 4 : r1 = int_range<1> (signed_char_type_node, SCHAR (15), SCHAR (127));
4992 4 : r2 = int_range<1> (signed_char_type_node, SCHAR (-128), SCHAR (-106));
4993 4 : r1.union_ (r2);
4994 4 : ASSERT_TRUE (r1 == r0);
4995 4 : range_cast (r0, unsigned_char_type_node);
4996 4 : ASSERT_TRUE (r0 == rold);
4997 :
4998 : // (unsigned char)[-5, 5] => [0,5][251,255].
4999 4 : r0 = rold = int_range<1> (signed_char_type_node, SCHAR (-5), SCHAR (5));
5000 4 : range_cast (r0, unsigned_char_type_node);
5001 4 : r1 = int_range<1> (unsigned_char_type_node, UCHAR (251), UCHAR (255));
5002 4 : r2 = int_range<1> (unsigned_char_type_node, UCHAR (0), UCHAR (5));
5003 4 : r1.union_ (r2);
5004 4 : ASSERT_TRUE (r0 == r1);
5005 4 : range_cast (r0, signed_char_type_node);
5006 4 : ASSERT_TRUE (r0 == rold);
5007 :
5008 : // (unsigned char)[-5,5] => [0,5][251,255].
5009 4 : r0 = int_range<1> (integer_type_node, INT (-5), INT (5));
5010 4 : range_cast (r0, unsigned_char_type_node);
5011 4 : r1 = int_range<1> (unsigned_char_type_node, UCHAR (0), UCHAR (5));
5012 4 : r1.union_ (int_range<1> (unsigned_char_type_node, UCHAR (251), UCHAR (255)));
5013 4 : ASSERT_TRUE (r0 == r1);
5014 :
5015 : // (unsigned char)[5U,1974U] => [0,255].
5016 4 : r0 = int_range<1> (unsigned_type_node, UINT (5), UINT (1974));
5017 4 : range_cast (r0, unsigned_char_type_node);
5018 4 : ASSERT_TRUE (r0 == int_range<1> (unsigned_char_type_node, UCHAR (0), UCHAR (255)));
5019 4 : range_cast (r0, integer_type_node);
5020 : // Going to a wider range should not sign extend.
5021 4 : ASSERT_TRUE (r0 == int_range<1> (integer_type_node, INT (0), INT (255)));
5022 :
5023 : // (unsigned char)[-350,15] => [0,255].
5024 4 : r0 = int_range<1> (integer_type_node, INT (-350), INT (15));
5025 4 : range_cast (r0, unsigned_char_type_node);
5026 4 : ASSERT_TRUE (r0 == (int_range<1>
5027 : (unsigned_char_type_node,
5028 : min_limit (unsigned_char_type_node),
5029 : max_limit (unsigned_char_type_node))));
5030 :
5031 : // Casting [-120,20] from signed char to unsigned short.
5032 : // => [0, 20][0xff88, 0xffff].
5033 4 : r0 = int_range<1> (signed_char_type_node, SCHAR (-120), SCHAR (20));
5034 4 : range_cast (r0, short_unsigned_type_node);
5035 4 : r1 = int_range<1> (short_unsigned_type_node, UINT16 (0), UINT16 (20));
5036 8 : r2 = int_range<1> (short_unsigned_type_node,
5037 12 : UINT16 (0xff88), UINT16 (0xffff));
5038 4 : r1.union_ (r2);
5039 4 : ASSERT_TRUE (r0 == r1);
5040 : // A truncating cast back to signed char will work because [-120, 20]
5041 : // is representable in signed char.
5042 4 : range_cast (r0, signed_char_type_node);
5043 4 : ASSERT_TRUE (r0 == int_range<1> (signed_char_type_node,
5044 : SCHAR (-120), SCHAR (20)));
5045 :
5046 : // unsigned char -> signed short
5047 : // (signed short)[(unsigned char)25, (unsigned char)250]
5048 : // => [(signed short)25, (signed short)250]
5049 4 : r0 = rold = int_range<1> (unsigned_char_type_node, UCHAR (25), UCHAR (250));
5050 4 : range_cast (r0, short_integer_type_node);
5051 4 : r1 = int_range<1> (short_integer_type_node, INT16 (25), INT16 (250));
5052 4 : ASSERT_TRUE (r0 == r1);
5053 4 : range_cast (r0, unsigned_char_type_node);
5054 4 : ASSERT_TRUE (r0 == rold);
5055 :
5056 : // Test casting a wider signed [-MIN,MAX] to a narrower unsigned.
5057 8 : r0 = int_range<1> (long_long_integer_type_node,
5058 4 : min_limit (long_long_integer_type_node),
5059 8 : max_limit (long_long_integer_type_node));
5060 4 : range_cast (r0, short_unsigned_type_node);
5061 8 : r1 = int_range<1> (short_unsigned_type_node,
5062 4 : min_limit (short_unsigned_type_node),
5063 8 : max_limit (short_unsigned_type_node));
5064 4 : ASSERT_TRUE (r0 == r1);
5065 :
5066 : // Casting NONZERO to a narrower type will wrap/overflow so
5067 : // it's just the entire range for the narrower type.
5068 : //
5069 : // "NOT 0 at signed 32-bits" ==> [-MIN_32,-1][1, +MAX_32]. This is
5070 : // is outside of the range of a smaller range, return the full
5071 : // smaller range.
5072 4 : if (TYPE_PRECISION (integer_type_node)
5073 4 : > TYPE_PRECISION (short_integer_type_node))
5074 : {
5075 4 : r0.set_nonzero (integer_type_node);
5076 4 : range_cast (r0, short_integer_type_node);
5077 8 : r1 = int_range<1> (short_integer_type_node,
5078 4 : min_limit (short_integer_type_node),
5079 8 : max_limit (short_integer_type_node));
5080 4 : ASSERT_TRUE (r0 == r1);
5081 : }
5082 :
5083 : // Casting NONZERO from a narrower signed to a wider signed.
5084 : //
5085 : // NONZERO signed 16-bits is [-MIN_16,-1][1, +MAX_16].
5086 : // Converting this to 32-bits signed is [-MIN_16,-1][1, +MAX_16].
5087 4 : r0.set_nonzero (short_integer_type_node);
5088 4 : range_cast (r0, integer_type_node);
5089 4 : r1 = int_range<1> (integer_type_node, INT (-32768), INT (-1));
5090 4 : r2 = int_range<1> (integer_type_node, INT (1), INT (32767));
5091 4 : r1.union_ (r2);
5092 4 : ASSERT_TRUE (r0 == r1);
5093 4 : }
5094 :
5095 : static void
5096 4 : range_op_lshift_tests ()
5097 : {
5098 : // Test that 0x808.... & 0x8.... still contains 0x8....
5099 : // for a large set of numbers.
5100 4 : {
5101 4 : int_range_max res;
5102 4 : tree big_type = long_long_unsigned_type_node;
5103 4 : unsigned big_prec = TYPE_PRECISION (big_type);
5104 : // big_num = 0x808,0000,0000,0000
5105 4 : wide_int big_num = wi::lshift (wi::uhwi (0x808, big_prec),
5106 8 : wi::uhwi (48, big_prec));
5107 8 : op_bitwise_and.fold_range (res, big_type,
5108 8 : int_range <1> (big_type),
5109 8 : int_range <1> (big_type, big_num, big_num));
5110 : // val = 0x8,0000,0000,0000
5111 4 : wide_int val = wi::lshift (wi::uhwi (8, big_prec),
5112 8 : wi::uhwi (48, big_prec));
5113 4 : ASSERT_TRUE (res.contains_p (val));
5114 4 : }
5115 :
5116 4 : if (TYPE_PRECISION (unsigned_type_node) > 31)
5117 : {
5118 : // unsigned VARYING = op1 << 1 should be VARYING.
5119 4 : int_range<2> lhs (unsigned_type_node);
5120 4 : int_range<2> shift (unsigned_type_node, INT (1), INT (1));
5121 4 : int_range_max op1;
5122 4 : op_lshift.op1_range (op1, unsigned_type_node, lhs, shift);
5123 4 : ASSERT_TRUE (op1.varying_p ());
5124 :
5125 : // 0 = op1 << 1 should be [0,0], [0x8000000, 0x8000000].
5126 4 : int_range<2> zero (unsigned_type_node, UINT (0), UINT (0));
5127 4 : op_lshift.op1_range (op1, unsigned_type_node, zero, shift);
5128 4 : ASSERT_TRUE (op1.num_pairs () == 2);
5129 : // Remove the [0,0] range.
5130 4 : op1.intersect (zero);
5131 4 : ASSERT_TRUE (op1.num_pairs () == 1);
5132 : // op1 << 1 should be [0x8000,0x8000] << 1,
5133 : // which should result in [0,0].
5134 4 : int_range_max result;
5135 4 : op_lshift.fold_range (result, unsigned_type_node, op1, shift);
5136 4 : ASSERT_TRUE (result == zero);
5137 4 : }
5138 : // signed VARYING = op1 << 1 should be VARYING.
5139 4 : if (TYPE_PRECISION (integer_type_node) > 31)
5140 : {
5141 : // unsigned VARYING = op1 << 1 should be VARYING.
5142 4 : int_range<2> lhs (integer_type_node);
5143 4 : int_range<2> shift (integer_type_node, INT (1), INT (1));
5144 4 : int_range_max op1;
5145 4 : op_lshift.op1_range (op1, integer_type_node, lhs, shift);
5146 4 : ASSERT_TRUE (op1.varying_p ());
5147 :
5148 : // 0 = op1 << 1 should be [0,0], [0x8000000, 0x8000000].
5149 4 : int_range<2> zero (integer_type_node, INT (0), INT (0));
5150 4 : op_lshift.op1_range (op1, integer_type_node, zero, shift);
5151 4 : ASSERT_TRUE (op1.num_pairs () == 2);
5152 : // Remove the [0,0] range.
5153 4 : op1.intersect (zero);
5154 4 : ASSERT_TRUE (op1.num_pairs () == 1);
5155 : // op1 << 1 should be [0x8000,0x8000] << 1,
5156 : // which should result in [0,0].
5157 4 : int_range_max result;
5158 4 : op_lshift.fold_range (result, unsigned_type_node, op1, shift);
5159 4 : ASSERT_TRUE (result == zero);
5160 4 : }
5161 4 : }
5162 :
5163 : static void
5164 4 : range_op_rshift_tests ()
5165 : {
5166 : // unsigned: [3, MAX] = OP1 >> 1
5167 4 : {
5168 4 : int_range_max lhs (unsigned_type_node,
5169 4 : UINT (3), max_limit (unsigned_type_node));
5170 4 : int_range_max one (unsigned_type_node,
5171 8 : wi::one (TYPE_PRECISION (unsigned_type_node)),
5172 8 : wi::one (TYPE_PRECISION (unsigned_type_node)));
5173 4 : int_range_max op1;
5174 4 : op_rshift.op1_range (op1, unsigned_type_node, lhs, one);
5175 4 : ASSERT_FALSE (op1.contains_p (UINT (3)));
5176 4 : }
5177 :
5178 : // signed: [3, MAX] = OP1 >> 1
5179 4 : {
5180 4 : int_range_max lhs (integer_type_node,
5181 4 : INT (3), max_limit (integer_type_node));
5182 4 : int_range_max one (integer_type_node, INT (1), INT (1));
5183 4 : int_range_max op1;
5184 4 : op_rshift.op1_range (op1, integer_type_node, lhs, one);
5185 4 : ASSERT_FALSE (op1.contains_p (INT (-2)));
5186 4 : }
5187 :
5188 : // This is impossible, so OP1 should be [].
5189 : // signed: [MIN, MIN] = OP1 >> 1
5190 4 : {
5191 4 : int_range_max lhs (integer_type_node,
5192 4 : min_limit (integer_type_node),
5193 4 : min_limit (integer_type_node));
5194 4 : int_range_max one (integer_type_node, INT (1), INT (1));
5195 4 : int_range_max op1;
5196 4 : op_rshift.op1_range (op1, integer_type_node, lhs, one);
5197 4 : ASSERT_TRUE (op1.undefined_p ());
5198 4 : }
5199 :
5200 : // signed: ~[-1] = OP1 >> 31
5201 4 : if (TYPE_PRECISION (integer_type_node) > 31)
5202 : {
5203 4 : int_range_max lhs (integer_type_node, INT (-1), INT (-1), VR_ANTI_RANGE);
5204 4 : int_range_max shift (integer_type_node, INT (31), INT (31));
5205 4 : int_range_max op1;
5206 4 : op_rshift.op1_range (op1, integer_type_node, lhs, shift);
5207 4 : int_range_max negatives = range_negatives (integer_type_node);
5208 4 : negatives.intersect (op1);
5209 4 : ASSERT_TRUE (negatives.undefined_p ());
5210 4 : }
5211 4 : }
5212 :
5213 : static void
5214 4 : range_op_bitwise_and_tests ()
5215 : {
5216 4 : int_range_max res;
5217 4 : wide_int min = min_limit (integer_type_node);
5218 4 : wide_int max = max_limit (integer_type_node);
5219 4 : wide_int tiny = wi::add (min, wi::one (TYPE_PRECISION (integer_type_node)));
5220 4 : int_range_max i1 (integer_type_node, tiny, max);
5221 4 : int_range_max i2 (integer_type_node, INT (255), INT (255));
5222 :
5223 : // [MIN+1, MAX] = OP1 & 255: OP1 is VARYING
5224 4 : op_bitwise_and.op1_range (res, integer_type_node, i1, i2);
5225 4 : ASSERT_TRUE (res == int_range<1> (integer_type_node));
5226 :
5227 : // VARYING = OP1 & 255: OP1 is VARYING
5228 4 : i1 = int_range<1> (integer_type_node);
5229 4 : op_bitwise_and.op1_range (res, integer_type_node, i1, i2);
5230 4 : ASSERT_TRUE (res == int_range<1> (integer_type_node));
5231 :
5232 : // For 0 = x & MASK, x is ~MASK.
5233 4 : {
5234 4 : int_range<2> zero (integer_type_node, INT (0), INT (0));
5235 4 : int_range<2> mask = int_range<2> (integer_type_node, INT (7), INT (7));
5236 4 : op_bitwise_and.op1_range (res, integer_type_node, zero, mask);
5237 4 : wide_int inv = wi::shwi (~7U, TYPE_PRECISION (integer_type_node));
5238 4 : ASSERT_TRUE (res.get_nonzero_bits () == inv);
5239 4 : }
5240 :
5241 : // (NONZERO | X) is nonzero.
5242 4 : i1.set_nonzero (integer_type_node);
5243 4 : i2.set_varying (integer_type_node);
5244 4 : op_bitwise_or.fold_range (res, integer_type_node, i1, i2);
5245 4 : ASSERT_TRUE (res.nonzero_p ());
5246 :
5247 : // (NEGATIVE | X) is nonzero.
5248 4 : i1 = int_range<1> (integer_type_node, INT (-5), INT (-3));
5249 4 : i2.set_varying (integer_type_node);
5250 4 : op_bitwise_or.fold_range (res, integer_type_node, i1, i2);
5251 4 : ASSERT_FALSE (res.contains_p (INT (0)));
5252 4 : }
5253 :
5254 : static void
5255 4 : range_relational_tests ()
5256 : {
5257 4 : int_range<2> lhs (unsigned_char_type_node);
5258 4 : int_range<2> op1 (unsigned_char_type_node, UCHAR (8), UCHAR (10));
5259 4 : int_range<2> op2 (unsigned_char_type_node, UCHAR (20), UCHAR (20));
5260 :
5261 : // Never wrapping additions mean LHS > OP1.
5262 4 : relation_kind code = op_plus.lhs_op1_relation (lhs, op1, op2, VREL_VARYING);
5263 4 : ASSERT_TRUE (code == VREL_GT);
5264 :
5265 : // Most wrapping additions mean nothing...
5266 4 : op1 = int_range<2> (unsigned_char_type_node, UCHAR (8), UCHAR (10));
5267 4 : op2 = int_range<2> (unsigned_char_type_node, UCHAR (0), UCHAR (255));
5268 4 : code = op_plus.lhs_op1_relation (lhs, op1, op2, VREL_VARYING);
5269 4 : ASSERT_TRUE (code == VREL_VARYING);
5270 :
5271 : // However, always wrapping additions mean LHS < OP1.
5272 4 : op1 = int_range<2> (unsigned_char_type_node, UCHAR (1), UCHAR (255));
5273 4 : op2 = int_range<2> (unsigned_char_type_node, UCHAR (255), UCHAR (255));
5274 4 : code = op_plus.lhs_op1_relation (lhs, op1, op2, VREL_VARYING);
5275 4 : ASSERT_TRUE (code == VREL_LT);
5276 4 : }
5277 :
5278 : void
5279 4 : range_op_tests ()
5280 : {
5281 4 : range_op_rshift_tests ();
5282 4 : range_op_lshift_tests ();
5283 4 : range_op_bitwise_and_tests ();
5284 4 : range_op_cast_tests ();
5285 4 : range_relational_tests ();
5286 :
5287 4 : extern void range_op_float_tests ();
5288 4 : range_op_float_tests ();
5289 4 : }
5290 :
5291 : } // namespace selftest
5292 :
5293 : #endif // CHECKING_P
|
