Line data Source code
1 : /* Code for range operators.
2 : Copyright (C) 2017-2026 Free Software Foundation, Inc.
3 : Contributed by Andrew MacLeod <amacleod@redhat.com>
4 : and Aldy Hernandez <aldyh@redhat.com>.
5 :
6 : This file is part of GCC.
7 :
8 : GCC is free software; you can redistribute it and/or modify
9 : it under the terms of the GNU General Public License as published by
10 : the Free Software Foundation; either version 3, or (at your option)
11 : any later version.
12 :
13 : GCC is distributed in the hope that it will be useful,
14 : but WITHOUT ANY WARRANTY; without even the implied warranty of
15 : MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 : GNU General Public License for more details.
17 :
18 : You should have received a copy of the GNU General Public License
19 : along with GCC; see the file COPYING3. If not see
20 : <http://www.gnu.org/licenses/>. */
21 :
22 : #include "config.h"
23 : #include "system.h"
24 : #include "coretypes.h"
25 : #include "backend.h"
26 : #include "insn-codes.h"
27 : #include "rtl.h"
28 : #include "tree.h"
29 : #include "gimple.h"
30 : #include "cfghooks.h"
31 : #include "tree-pass.h"
32 : #include "ssa.h"
33 : #include "optabs-tree.h"
34 : #include "gimple-pretty-print.h"
35 : #include "diagnostic-core.h"
36 : #include "flags.h"
37 : #include "fold-const.h"
38 : #include "stor-layout.h"
39 : #include "calls.h"
40 : #include "cfganal.h"
41 : #include "gimple-iterator.h"
42 : #include "gimple-fold.h"
43 : #include "tree-eh.h"
44 : #include "gimple-walk.h"
45 : #include "tree-cfg.h"
46 : #include "wide-int.h"
47 : #include "value-relation.h"
48 : #include "range-op.h"
49 : #include "tree-ssa-ccp.h"
50 : #include "range-op-mixed.h"
51 :
52 : // Instantiate the operators which apply to multiple types here.
53 :
54 : static const operator_equal op_equal;
55 : static const operator_not_equal op_not_equal;
56 : static const operator_lt op_lt;
57 : static const operator_le op_le;
58 : static const operator_gt op_gt;
59 : static const operator_ge op_ge;
60 : static const operator_identity op_ident;
61 : static const operator_cst op_cst;
62 : static const operator_cast op_cast;
63 : static const operator_view op_view;
64 : static const operator_plus op_plus;
65 : static const operator_abs op_abs;
66 : static const operator_minus op_minus;
67 : static const operator_negate op_negate;
68 : static const operator_mult op_mult;
69 : static const operator_addr_expr op_addr;
70 : static const operator_bitwise_not op_bitwise_not;
71 : static const operator_bitwise_xor op_bitwise_xor;
72 : static const operator_bitwise_and op_bitwise_and;
73 : static const operator_bitwise_or op_bitwise_or;
74 : static const operator_min op_min;
75 : static const operator_max op_max;
76 :
77 : // Instantiate a range operator table.
78 : static range_op_table operator_table;
79 :
80 : // Invoke the initialization routines for each class of range.
81 :
82 297658 : range_op_table::range_op_table ()
83 : {
84 297658 : initialize_integral_ops ();
85 297658 : initialize_pointer_ops ();
86 297658 : initialize_float_ops ();
87 :
88 297658 : set (EQ_EXPR, op_equal);
89 297658 : set (NE_EXPR, op_not_equal);
90 297658 : set (LT_EXPR, op_lt);
91 297658 : set (LE_EXPR, op_le);
92 297658 : set (GT_EXPR, op_gt);
93 297658 : set (GE_EXPR, op_ge);
94 297658 : set (SSA_NAME, op_ident);
95 297658 : set (PAREN_EXPR, op_ident);
96 297658 : set (OBJ_TYPE_REF, op_ident);
97 297658 : set (REAL_CST, op_cst);
98 297658 : set (INTEGER_CST, op_cst);
99 297658 : set (NOP_EXPR, op_cast);
100 297658 : set (CONVERT_EXPR, op_cast);
101 297658 : set (VIEW_CONVERT_EXPR, op_view);
102 297658 : set (FLOAT_EXPR, op_cast);
103 297658 : set (FIX_TRUNC_EXPR, op_cast);
104 297658 : set (PLUS_EXPR, op_plus);
105 297658 : set (ABS_EXPR, op_abs);
106 297658 : set (MINUS_EXPR, op_minus);
107 297658 : set (NEGATE_EXPR, op_negate);
108 297658 : set (MULT_EXPR, op_mult);
109 297658 : set (ADDR_EXPR, op_addr);
110 297658 : set (BIT_NOT_EXPR, op_bitwise_not);
111 297658 : set (BIT_XOR_EXPR, op_bitwise_xor);
112 297658 : set (BIT_AND_EXPR, op_bitwise_and);
113 297658 : set (BIT_IOR_EXPR, op_bitwise_or);
114 297658 : set (MIN_EXPR, op_min);
115 297658 : set (MAX_EXPR, op_max);
116 297658 : }
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 1691880845 : range_op_handler::range_op_handler ()
125 : {
126 1691880845 : m_operator = &default_operator;
127 1691880845 : }
128 :
129 : // Create a range_op_handler for CODE. Use a default operator if CODE
130 : // does not have an entry.
131 :
132 4067648479 : range_op_handler::range_op_handler (unsigned code)
133 : {
134 4067648479 : m_operator = operator_table[code];
135 4067648479 : if (!m_operator)
136 800748175 : m_operator = &default_operator;
137 4067648479 : }
138 :
139 : // Return TRUE if this handler has a non-default operator.
140 :
141 5890568179 : range_op_handler::operator bool () const
142 : {
143 5890568179 : return m_operator != &default_operator;
144 : }
145 :
146 : // Return a pointer to the range operator associated with this handler.
147 : // If it is a default operator, return nullptr.
148 : // This is the equivalent of indexing the range table.
149 :
150 : const range_operator *
151 996719785 : range_op_handler::range_op () const
152 : {
153 996719785 : if (m_operator != &default_operator)
154 996719785 : return m_operator;
155 : return nullptr;
156 : }
157 :
158 : // Create a dispatch pattern for value range discriminators LHS, OP1, and OP2.
159 : // This is used to produce a unique value for each dispatch pattern. Shift
160 : // values are based on the size of the m_discriminator field in value_range.h.
161 :
162 : constexpr unsigned
163 641576888 : dispatch_trio (unsigned lhs, unsigned op1, unsigned op2)
164 : {
165 641576888 : return ((lhs << 8) + (op1 << 4) + (op2));
166 : }
167 :
168 : // These are the supported dispatch patterns. These map to the parameter list
169 : // of the routines in range_operator. Note the last 3 characters are
170 : // shorthand for the LHS, OP1, and OP2 range discriminator class.
171 : // Reminder, single operand instructions use the LHS type for op2, even if
172 : // unused. So FLOAT = INT would be RO_FIF.
173 :
174 : static const unsigned RO_III = dispatch_trio (VR_IRANGE, VR_IRANGE, VR_IRANGE);
175 : static const unsigned RO_IFI = dispatch_trio (VR_IRANGE, VR_FRANGE, VR_IRANGE);
176 : static const unsigned RO_IFF = dispatch_trio (VR_IRANGE, VR_FRANGE, VR_FRANGE);
177 : static const unsigned RO_FFF = dispatch_trio (VR_FRANGE, VR_FRANGE, VR_FRANGE);
178 : static const unsigned RO_FIF = dispatch_trio (VR_FRANGE, VR_IRANGE, VR_FRANGE);
179 : static const unsigned RO_FII = dispatch_trio (VR_FRANGE, VR_IRANGE, VR_IRANGE);
180 : static const unsigned RO_PPP = dispatch_trio (VR_PRANGE, VR_PRANGE, VR_PRANGE);
181 : static const unsigned RO_PPI = dispatch_trio (VR_PRANGE, VR_PRANGE, VR_IRANGE);
182 : static const unsigned RO_IPP = dispatch_trio (VR_IRANGE, VR_PRANGE, VR_PRANGE);
183 : static const unsigned RO_IPI = dispatch_trio (VR_IRANGE, VR_PRANGE, VR_IRANGE);
184 : static const unsigned RO_PIP = dispatch_trio (VR_PRANGE, VR_IRANGE, VR_PRANGE);
185 : static const unsigned RO_PII = dispatch_trio (VR_PRANGE, VR_IRANGE, VR_IRANGE);
186 :
187 : // Return a dispatch value for parameter types LHS, OP1 and OP2.
188 :
189 : unsigned
190 641576888 : range_op_handler::dispatch_kind (const vrange &lhs, const vrange &op1,
191 : const vrange& op2) const
192 : {
193 641576888 : return dispatch_trio (lhs.m_discriminator, op1.m_discriminator,
194 641576888 : 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 289297259 : range_op_handler::fold_range (vrange &r, tree type,
224 : const vrange &lh,
225 : const vrange &rh,
226 : relation_trio rel) const
227 : {
228 289297259 : gcc_checking_assert (m_operator);
229 : #if CHECKING_P
230 289297259 : if (!lh.undefined_p () && !rh.undefined_p ())
231 283922075 : gcc_assert (m_operator->operand_check_p (type, lh.type (), rh.type ()));
232 : #endif
233 289297259 : switch (dispatch_kind (r, lh, rh))
234 : {
235 220662358 : case RO_III:
236 220662358 : return m_operator->fold_range (as_a <irange> (r), type,
237 : as_a <irange> (lh),
238 220662358 : as_a <irange> (rh), rel);
239 348911 : case RO_IFI:
240 348911 : return m_operator->fold_range (as_a <irange> (r), type,
241 : as_a <frange> (lh),
242 348911 : as_a <irange> (rh), rel);
243 2596090 : case RO_IFF:
244 2596090 : return m_operator->fold_range (as_a <irange> (r), type,
245 : as_a <frange> (lh),
246 2596090 : as_a <frange> (rh), rel);
247 7450525 : case RO_FFF:
248 7450525 : return m_operator->fold_range (as_a <frange> (r), type,
249 : as_a <frange> (lh),
250 7450525 : 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 889528 : case RO_FIF:
256 889528 : return m_operator->fold_range (as_a <frange> (r), type,
257 : as_a <irange> (lh),
258 889528 : as_a <frange> (rh), rel);
259 17740097 : case RO_PPP:
260 17740097 : return m_operator->fold_range (as_a <prange> (r), type,
261 : as_a <prange> (lh),
262 17740097 : as_a <prange> (rh), rel);
263 9171140 : case RO_PPI:
264 9171140 : return m_operator->fold_range (as_a <prange> (r), type,
265 : as_a <prange> (lh),
266 9171140 : as_a <irange> (rh), rel);
267 17759726 : case RO_IPP:
268 17759726 : return m_operator->fold_range (as_a <irange> (r), type,
269 : as_a <prange> (lh),
270 17759726 : as_a <prange> (rh), rel);
271 1867259 : case RO_PIP:
272 1867259 : return m_operator->fold_range (as_a <prange> (r), type,
273 : as_a <irange> (lh),
274 1867259 : as_a <prange> (rh), rel);
275 10811593 : case RO_IPI:
276 10811593 : return m_operator->fold_range (as_a <irange> (r), type,
277 : as_a <prange> (lh),
278 10811593 : 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 88968346 : range_op_handler::op1_range (vrange &r, tree type,
288 : const vrange &lhs,
289 : const vrange &op2,
290 : relation_trio rel) const
291 : {
292 88968346 : gcc_checking_assert (m_operator);
293 88968346 : if (lhs.undefined_p ())
294 : return false;
295 : #if CHECKING_P
296 88967223 : if (!op2.undefined_p ())
297 88967051 : gcc_assert (m_operator->operand_check_p (lhs.type (), type, op2.type ()));
298 : #endif
299 88967223 : switch (dispatch_kind (r, lhs, op2))
300 : {
301 76787630 : case RO_III:
302 76787630 : return m_operator->op1_range (as_a <irange> (r), type,
303 : as_a <irange> (lhs),
304 76787630 : as_a <irange> (op2), rel);
305 213726 : case RO_IFI:
306 213726 : return m_operator->op1_range (as_a <irange> (r), type,
307 : as_a <frange> (lhs),
308 213726 : as_a <irange> (op2), rel);
309 758517 : case RO_PPP:
310 758517 : return m_operator->op1_range (as_a <prange> (r), type,
311 : as_a <prange> (lhs),
312 758517 : as_a <prange> (op2), rel);
313 8276984 : case RO_PIP:
314 8276984 : return m_operator->op1_range (as_a <prange> (r), type,
315 : as_a <irange> (lhs),
316 8276984 : as_a <prange> (op2), rel);
317 399343 : case RO_PPI:
318 399343 : return m_operator->op1_range (as_a <prange> (r), type,
319 : as_a <prange> (lhs),
320 399343 : as_a <irange> (op2), rel);
321 228654 : case RO_IPI:
322 228654 : return m_operator->op1_range (as_a <irange> (r), type,
323 : as_a <prange> (lhs),
324 228654 : as_a <irange> (op2), rel);
325 1448890 : case RO_FIF:
326 1448890 : return m_operator->op1_range (as_a <frange> (r), type,
327 : as_a <irange> (lhs),
328 1448890 : as_a <frange> (op2), rel);
329 853479 : case RO_FFF:
330 853479 : return m_operator->op1_range (as_a <frange> (r), type,
331 : as_a <frange> (lhs),
332 853479 : 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 25476736 : range_op_handler::op2_range (vrange &r, tree type,
342 : const vrange &lhs,
343 : const vrange &op1,
344 : relation_trio rel) const
345 : {
346 25476736 : gcc_checking_assert (m_operator);
347 25476736 : if (lhs.undefined_p ())
348 : return false;
349 : #if CHECKING_P
350 25476704 : if (!op1.undefined_p ())
351 25476555 : gcc_assert (m_operator->operand_check_p (lhs.type (), op1.type (), type));
352 : #endif
353 25476704 : switch (dispatch_kind (r, lhs, op1))
354 : {
355 19867483 : case RO_III:
356 19867483 : return m_operator->op2_range (as_a <irange> (r), type,
357 : as_a <irange> (lhs),
358 19867483 : as_a <irange> (op1), rel);
359 4567937 : case RO_PIP:
360 4567937 : return m_operator->op2_range (as_a <prange> (r), type,
361 : as_a <irange> (lhs),
362 4567937 : as_a <prange> (op1), rel);
363 225851 : case RO_IPP:
364 225851 : return m_operator->op2_range (as_a <irange> (r), type,
365 : as_a <prange> (lhs),
366 225851 : as_a <prange> (op1), rel);
367 488694 : case RO_FIF:
368 488694 : return m_operator->op2_range (as_a <frange> (r), type,
369 : as_a <irange> (lhs),
370 488694 : as_a <frange> (op1), rel);
371 326603 : case RO_FFF:
372 326603 : return m_operator->op2_range (as_a <frange> (r), type,
373 : as_a <frange> (lhs),
374 326603 : 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 122818106 : range_op_handler::lhs_op1_relation (const vrange &lhs,
384 : const vrange &op1,
385 : const vrange &op2,
386 : relation_kind rel) const
387 : {
388 122818106 : gcc_checking_assert (m_operator);
389 122818106 : switch (dispatch_kind (lhs, op1, op2))
390 : {
391 98525381 : case RO_III:
392 98525381 : return m_operator->lhs_op1_relation (as_a <irange> (lhs),
393 : as_a <irange> (op1),
394 98525381 : as_a <irange> (op2), rel);
395 1381828 : case RO_PPP:
396 1381828 : return m_operator->lhs_op1_relation (as_a <prange> (lhs),
397 : as_a <prange> (op1),
398 1381828 : as_a <prange> (op2), rel);
399 5961997 : case RO_IPP:
400 5961997 : return m_operator->lhs_op1_relation (as_a <irange> (lhs),
401 : as_a <prange> (op1),
402 5961997 : as_a <prange> (op2), rel);
403 1386651 : case RO_PII:
404 1386651 : return m_operator->lhs_op1_relation (as_a <prange> (lhs),
405 : as_a <irange> (op1),
406 1386651 : as_a <irange> (op2), rel);
407 7929526 : case RO_PPI:
408 7929526 : return m_operator->lhs_op1_relation (as_a <prange> (lhs),
409 : as_a <prange> (op1),
410 7929526 : as_a <irange> (op2), rel);
411 1028308 : case RO_IFF:
412 1028308 : return m_operator->lhs_op1_relation (as_a <irange> (lhs),
413 : as_a <frange> (op1),
414 1028308 : as_a <frange> (op2), rel);
415 5715434 : case RO_FFF:
416 5715434 : return m_operator->lhs_op1_relation (as_a <frange> (lhs),
417 : as_a <frange> (op1),
418 5715434 : 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 36770370 : range_op_handler::lhs_op2_relation (const vrange &lhs,
428 : const vrange &op1,
429 : const vrange &op2,
430 : relation_kind rel) const
431 : {
432 36770370 : gcc_checking_assert (m_operator);
433 36770370 : switch (dispatch_kind (lhs, op1, op2))
434 : {
435 25340944 : case RO_III:
436 25340944 : return m_operator->lhs_op2_relation (as_a <irange> (lhs),
437 : as_a <irange> (op1),
438 25340944 : as_a <irange> (op2), rel);
439 169225 : case RO_IFF:
440 169225 : return m_operator->lhs_op2_relation (as_a <irange> (lhs),
441 : as_a <frange> (op1),
442 169225 : as_a <frange> (op2), rel);
443 3617973 : case RO_FFF:
444 3617973 : return m_operator->lhs_op2_relation (as_a <frange> (lhs),
445 : as_a <frange> (op1),
446 3617973 : 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 78202447 : range_op_handler::op1_op2_relation (const vrange &lhs,
456 : const vrange &op1,
457 : const vrange &op2) const
458 : {
459 78202447 : gcc_checking_assert (m_operator);
460 :
461 78202447 : switch (dispatch_kind (lhs, op1, op2))
462 : {
463 60989464 : case RO_III:
464 60989464 : return m_operator->op1_op2_relation (as_a <irange> (lhs),
465 : as_a <irange> (op1),
466 60989464 : as_a <irange> (op2));
467 :
468 14521380 : case RO_IPP:
469 14521380 : return m_operator->op1_op2_relation (as_a <irange> (lhs),
470 : as_a <prange> (op1),
471 14521380 : as_a <prange> (op2));
472 :
473 1752132 : case RO_IFF:
474 1752132 : return m_operator->op1_op2_relation (as_a <irange> (lhs),
475 : as_a <frange> (op1),
476 1752132 : as_a <frange> (op2));
477 :
478 600438 : case RO_FFF:
479 600438 : return m_operator->op1_op2_relation (as_a <frange> (lhs),
480 : as_a <frange> (op1),
481 600438 : as_a <frange> (op2));
482 :
483 : default:
484 : return VREL_VARYING;
485 : }
486 : }
487 :
488 : bool
489 44779 : range_op_handler::overflow_free_p (const vrange &lh,
490 : const vrange &rh,
491 : relation_trio rel) const
492 : {
493 44779 : gcc_checking_assert (m_operator);
494 44779 : switch (dispatch_kind (lh, lh, rh))
495 : {
496 44779 : case RO_III:
497 44779 : return m_operator->overflow_free_p(as_a <irange> (lh),
498 : as_a <irange> (rh),
499 44779 : rel);
500 : default:
501 : return false;
502 : }
503 : }
504 :
505 : bool
506 8922685 : range_op_handler::operand_check_p (tree t1, tree t2, tree t3) const
507 : {
508 8922685 : gcc_checking_assert (m_operator);
509 8922685 : 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 172250318 : update_known_bitmask (vrange &r, tree_code code,
517 : const vrange &lh, const vrange &rh)
518 : {
519 172250318 : if (r.undefined_p () || lh.undefined_p () || rh.undefined_p ()
520 344496266 : || r.singleton_p ())
521 9344404 : return;
522 :
523 162905914 : widest_int widest_value, widest_mask;
524 162905914 : tree type = r.type ();
525 162905914 : signop sign = TYPE_SIGN (type);
526 162905914 : int prec = TYPE_PRECISION (type);
527 162905914 : irange_bitmask lh_bits = lh.get_bitmask ();
528 162905914 : irange_bitmask rh_bits = rh.get_bitmask ();
529 :
530 162905914 : switch (get_gimple_rhs_class (code))
531 : {
532 55944379 : case GIMPLE_UNARY_RHS:
533 55944379 : bit_value_unop (code, sign, prec, &widest_value, &widest_mask,
534 55944379 : TYPE_SIGN (lh.type ()),
535 55944379 : TYPE_PRECISION (lh.type ()),
536 111889236 : widest_int::from (lh_bits.value (),
537 55944379 : TYPE_SIGN (lh.type ())),
538 111888758 : widest_int::from (lh_bits.mask (),
539 55944379 : TYPE_SIGN (lh.type ())));
540 55944379 : break;
541 106961535 : case GIMPLE_BINARY_RHS:
542 213923070 : bit_value_binop (code, sign, prec, &widest_value, &widest_mask,
543 106961535 : TYPE_SIGN (lh.type ()),
544 106961535 : TYPE_PRECISION (lh.type ()),
545 213923988 : widest_int::from (lh_bits.value (), sign),
546 213923988 : widest_int::from (lh_bits.mask (), sign),
547 106961535 : TYPE_SIGN (rh.type ()),
548 106961535 : TYPE_PRECISION (rh.type ()),
549 213923955 : widest_int::from (rh_bits.value (), sign),
550 213923070 : widest_int::from (rh_bits.mask (), sign));
551 106961535 : break;
552 0 : default:
553 0 : gcc_unreachable ();
554 : }
555 :
556 162905914 : wide_int mask = wide_int::from (widest_mask, prec, sign);
557 325811828 : wide_int value = wide_int::from (widest_value, prec, sign);
558 : // Bitmasks must have the unknown value bits cleared.
559 162905914 : value &= ~mask;
560 325811828 : irange_bitmask bm (value, mask);
561 162905914 : r.update_bitmask (bm);
562 162906888 : }
563 :
564 : // Return the upper limit for a type.
565 :
566 : static inline wide_int
567 16878303 : max_limit (const_tree type)
568 : {
569 16878303 : return irange_val_max (type);
570 : }
571 :
572 : // Return the lower limit for a type.
573 :
574 : static inline wide_int
575 19570291 : min_limit (const_tree type)
576 : {
577 19570291 : 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 4794486 : get_shift_range (irange &r, tree type, const irange &op)
586 : {
587 4794486 : if (op.undefined_p ())
588 : return false;
589 :
590 : // Build valid range and intersect it with the shift range.
591 4794004 : r.set (op.type (),
592 9588008 : wi::shwi (0, TYPE_PRECISION (op.type ())),
593 4794004 : wi::shwi (TYPE_PRECISION (type) - 1, TYPE_PRECISION (op.type ())));
594 4794004 : r.intersect (op);
595 :
596 : // If there are no valid ranges in the shift range, returned false.
597 4794004 : 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 53751 : 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 53751 : int_range_max tmp;
629 107502 : widest_int lh_range = wi::sub (widest_int::from (lh_ub, TYPE_SIGN (type)),
630 107502 : widest_int::from (lh_lb, TYPE_SIGN (type)));
631 : // if there are 1 to 8 values in the LH range, split them up.
632 53751 : r.set_undefined ();
633 107502 : if (lh_range >= 0 && lh_range < limit)
634 : {
635 16025 : for (unsigned x = 0; x <= lh_range; x++)
636 : {
637 10979 : wide_int val = lh_lb + x;
638 10979 : wi_fold (tmp, type, val, val, val, val);
639 10979 : r.union_ (tmp);
640 10979 : }
641 : }
642 : // Otherwise just call wi_fold.
643 : else
644 48705 : wi_fold (r, type, lh_lb, lh_ub, lh_lb, lh_ub);
645 53751 : }
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 142836614 : 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 142836614 : int_range_max tmp;
659 285673228 : widest_int rh_range = wi::sub (widest_int::from (rh_ub, TYPE_SIGN (type)),
660 285673228 : widest_int::from (rh_lb, TYPE_SIGN (type)));
661 285673228 : widest_int lh_range = wi::sub (widest_int::from (lh_ub, TYPE_SIGN (type)),
662 285673228 : 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 142836614 : if (rh_range > 0 && rh_range < 4)
666 : {
667 4949952 : wi_fold_in_parts (r, type, lh_lb, lh_ub, rh_lb, rh_lb);
668 4949952 : if (rh_range > 1)
669 : {
670 589476 : wi_fold_in_parts (tmp, type, lh_lb, lh_ub, rh_lb + 1, rh_lb + 1);
671 589476 : r.union_ (tmp);
672 589476 : if (rh_range == 3)
673 : {
674 369687 : wi_fold_in_parts (tmp, type, lh_lb, lh_ub, rh_lb + 2, rh_lb + 2);
675 369687 : r.union_ (tmp);
676 : }
677 : }
678 4949952 : wi_fold_in_parts (tmp, type, lh_lb, lh_ub, rh_ub, rh_ub);
679 4949952 : 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 137886662 : else if (lh_range > 0 && lh_range < 4)
684 : {
685 9678305 : wi_fold (r, type, lh_lb, lh_lb, rh_lb, rh_ub);
686 9678305 : if (lh_range > 1)
687 : {
688 1753993 : wi_fold (tmp, type, lh_lb + 1, lh_lb + 1, rh_lb, rh_ub);
689 1753985 : r.union_ (tmp);
690 1753985 : if (lh_range == 3)
691 : {
692 747015 : wi_fold (tmp, type, lh_lb + 2, lh_lb + 2, rh_lb, rh_ub);
693 747011 : r.union_ (tmp);
694 : }
695 : }
696 9678305 : wi_fold (tmp, type, lh_ub, lh_ub, rh_lb, rh_ub);
697 9678305 : r.union_ (tmp);
698 : }
699 : // Otherwise just call wi_fold.
700 : else
701 128208357 : wi_fold (r, type, lh_lb, lh_ub, rh_lb, rh_ub);
702 142836969 : }
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 100710465 : range_operator::fold_range (irange &r, tree type,
709 : const irange &lh,
710 : const irange &rh,
711 : relation_trio trio) const
712 : {
713 100710465 : gcc_checking_assert (r.supports_type_p (type));
714 100710465 : if (empty_range_varying (r, type, lh, rh))
715 45992 : return true;
716 :
717 100664473 : relation_kind rel = trio.op1_op2 ();
718 100664473 : unsigned num_lh = lh.num_pairs ();
719 100664473 : 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 100665620 : if (relation_equiv_p (rel) && lh == rh)
724 : {
725 50397 : int_range_max tmp;
726 50397 : r.set_undefined ();
727 90252 : for (unsigned x = 0; x < num_lh; ++x)
728 : {
729 : // If the number of subranges is too high, limit subrange creation.
730 53751 : unsigned limit = (r.num_pairs () > 32) ? 0 : 8;
731 53751 : wide_int lh_lb = lh.lower_bound (x);
732 53751 : wide_int lh_ub = lh.upper_bound (x);
733 53751 : wi_fold_in_parts_equiv (tmp, type, lh_lb, lh_ub, limit);
734 53751 : r.union_ (tmp);
735 53751 : if (r.varying_p ())
736 : break;
737 53751 : }
738 50397 : op1_op2_relation_effect (r, type, lh, rh, rel);
739 50397 : update_bitmask (r, lh, rh);
740 50397 : return true;
741 50397 : }
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 100614076 : if ((num_lh == 1 && num_rh == 1) || num_lh * num_rh > 12)
747 : {
748 83622773 : wi_fold_in_parts (r, type, lh.lower_bound (), lh.upper_bound (),
749 167243146 : rh.lower_bound (), rh.upper_bound ());
750 83621573 : op1_op2_relation_effect (r, type, lh, rh, rel);
751 83621573 : update_bitmask (r, lh, rh);
752 83621573 : return true;
753 : }
754 :
755 16992503 : int_range_max tmp;
756 16992503 : r.set_undefined ();
757 52814965 : for (unsigned x = 0; x < num_lh; ++x)
758 84178436 : for (unsigned y = 0; y < num_rh; ++y)
759 : {
760 48355974 : wide_int lh_lb = lh.lower_bound (x);
761 48355974 : wide_int lh_ub = lh.upper_bound (x);
762 48355974 : wide_int rh_lb = rh.lower_bound (y);
763 48355974 : wide_int rh_ub = rh.upper_bound (y);
764 48355974 : wi_fold_in_parts (tmp, type, lh_lb, lh_ub, rh_lb, rh_ub);
765 48355974 : r.union_ (tmp);
766 48355974 : if (r.varying_p ())
767 : {
768 4004595 : op1_op2_relation_effect (r, type, lh, rh, rel);
769 4004595 : update_bitmask (r, lh, rh);
770 4004595 : return true;
771 : }
772 48357063 : }
773 12987908 : op1_op2_relation_effect (r, type, lh, rh, rel);
774 12987908 : update_bitmask (r, lh, rh);
775 12987908 : return true;
776 16992503 : }
777 :
778 :
779 : bool
780 71163 : range_operator::fold_range (frange &, tree, const irange &,
781 : const frange &, relation_trio) const
782 : {
783 71163 : return false;
784 : }
785 :
786 : bool
787 1317 : range_operator::op1_range (irange &, tree, const frange &,
788 : const irange &, relation_trio) const
789 : {
790 1317 : return false;
791 : }
792 :
793 :
794 :
795 : // The default for op1_range is to return false.
796 :
797 : bool
798 736938 : 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 736938 : return false;
805 : }
806 :
807 : // The default for op2_range is to return false.
808 :
809 : bool
810 559162 : 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 559162 : return false;
817 : }
818 :
819 : // The default relation routines return VREL_VARYING.
820 :
821 : relation_kind
822 23715716 : 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 23715716 : return VREL_VARYING;
828 : }
829 :
830 : relation_kind
831 17094586 : 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 17094586 : return VREL_VARYING;
837 : }
838 :
839 : relation_kind
840 14429085 : 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 14429085 : return VREL_VARYING;
845 : }
846 :
847 : // Default is no relation affects the LHS.
848 :
849 : bool
850 68627462 : 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 68627462 : 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 6240 : range_operator::update_bitmask (irange &, const irange &,
873 : const irange &) const
874 : {
875 6240 : }
876 :
877 : // Check that operand types are OK. Default to always OK.
878 :
879 : bool
880 122890836 : range_operator::operand_check_p (tree, tree, tree) const
881 : {
882 122890836 : 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 40536495 : value_range_from_overflowed_bounds (irange &r, tree type,
890 : const wide_int &wmin,
891 : const wide_int &wmax)
892 : {
893 40536495 : const signop sgn = TYPE_SIGN (type);
894 40536495 : const unsigned int prec = TYPE_PRECISION (type);
895 :
896 40536495 : wide_int tmin = wide_int::from (wmin, prec, sgn);
897 40536495 : wide_int tmax = wide_int::from (wmax, prec, sgn);
898 :
899 40536495 : bool covers = false;
900 40536495 : wide_int tem = tmin;
901 40536495 : tmin = tmax + 1;
902 40536495 : if (wi::cmp (tmin, tmax, sgn) < 0)
903 2531297 : covers = true;
904 40536495 : tmax = tem - 1;
905 40536495 : 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 37918513 : if (covers || wi::cmp (tmin, tmax, sgn) > 0)
912 27451814 : r.set_varying (type);
913 : else
914 13084681 : r.set (type, tmin, tmax, VR_ANTI_RANGE);
915 40537124 : }
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 138702499 : 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 138702499 : const signop sgn = TYPE_SIGN (type);
928 138702499 : const unsigned int prec = TYPE_PRECISION (type);
929 218054200 : 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 152507304 : if (prec == 1 && wi::ne_p (wmax, wmin))
934 : {
935 0 : r.set_varying (type);
936 0 : return;
937 : }
938 :
939 138702499 : if (overflow_wraps)
940 : {
941 : // If overflow wraps, truncate the values and adjust the range,
942 : // kind, and bounds appropriately.
943 79351701 : if ((min_ovf != wi::OVF_NONE) == (max_ovf != wi::OVF_NONE))
944 : {
945 55884970 : wide_int tmin = wide_int::from (wmin, prec, sgn);
946 55884970 : 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 55884970 : if (wi::gt_p (tmin, tmax, sgn))
950 541523 : r.set_varying (type);
951 : else
952 : // No overflow or both overflow or underflow. The range
953 : // kind stays normal.
954 55343447 : r.set (type, tmin, tmax);
955 55884970 : return;
956 55885110 : }
957 :
958 23466731 : if ((min_ovf == wi::OVF_UNDERFLOW && max_ovf == wi::OVF_NONE)
959 16519904 : || (max_ovf == wi::OVF_OVERFLOW && min_ovf == wi::OVF_NONE))
960 23466731 : 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 59350798 : if ((min_ovf == wi::OVF_OVERFLOW && max_ovf == wi::OVF_OVERFLOW)
970 59348402 : || (min_ovf == wi::OVF_UNDERFLOW && max_ovf == wi::OVF_UNDERFLOW))
971 : {
972 4824 : r.set_undefined ();
973 4824 : return;
974 : }
975 :
976 : // If overflow does not wrap, saturate to [MIN, MAX].
977 59345974 : wide_int new_lb, new_ub;
978 59345974 : if (min_ovf == wi::OVF_UNDERFLOW)
979 7408773 : new_lb = wi::min_value (prec, sgn);
980 51937411 : else if (min_ovf == wi::OVF_OVERFLOW)
981 0 : new_lb = wi::max_value (prec, sgn);
982 : else
983 51937411 : new_lb = wmin;
984 :
985 59345974 : if (max_ovf == wi::OVF_UNDERFLOW)
986 0 : new_ub = wi::min_value (prec, sgn);
987 59345974 : else if (max_ovf == wi::OVF_OVERFLOW)
988 12179951 : new_ub = wi::max_value (prec, sgn);
989 : else
990 47166277 : new_ub = wmax;
991 :
992 59345974 : r.set (type, new_lb, new_ub);
993 59346545 : }
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 85256818 : create_possibly_reversed_range (irange &r, tree type,
1002 : const wide_int &new_lb, const wide_int &new_ub)
1003 : {
1004 85256818 : signop s = TYPE_SIGN (type);
1005 : // If the bounds are swapped, treat the result as if an overflow occurred.
1006 85256818 : if (wi::gt_p (new_lb, new_ub, s))
1007 17069764 : value_range_from_overflowed_bounds (r, type, new_lb, new_ub);
1008 : else
1009 : // Otherwise it's just a normal range.
1010 68187054 : r.set (type, new_lb, new_ub);
1011 85256818 : }
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 80768382 : get_bool_state (vrange &r, const vrange &lhs, tree val_type)
1018 : {
1019 : // If there is no result, then this is unexecutable.
1020 80768382 : if (lhs.undefined_p ())
1021 : {
1022 0 : r.set_undefined ();
1023 0 : return BRS_EMPTY;
1024 : }
1025 :
1026 80768382 : 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 40461809 : if (lhs.contains_p (build_zero_cst (lhs.type ())))
1032 : {
1033 160531 : r.set_varying (val_type);
1034 160531 : 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 5558010 : operator_equal::op1_op2_relation (const irange &lhs, const irange &,
1053 : const irange &) const
1054 : {
1055 5558010 : if (lhs.undefined_p ())
1056 : return VREL_UNDEFINED;
1057 :
1058 : // FALSE = op1 == op2 indicates NE_EXPR.
1059 5558010 : if (lhs.zero_p ())
1060 : return VREL_NE;
1061 :
1062 : // TRUE = op1 == op2 indicates EQ_EXPR.
1063 3021759 : if (!contains_zero_p (lhs))
1064 3004134 : return VREL_EQ;
1065 : return VREL_VARYING;
1066 : }
1067 :
1068 : bool
1069 17481691 : operator_equal::fold_range (irange &r, tree type,
1070 : const irange &op1,
1071 : const irange &op2,
1072 : relation_trio rel) const
1073 : {
1074 17481691 : 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 17447995 : bool op1_const = wi::eq_p (op1.lower_bound (), op1.upper_bound ());
1080 17447995 : bool op2_const = wi::eq_p (op2.lower_bound (), op2.upper_bound ());
1081 17447983 : if (op1_const && op2_const)
1082 : {
1083 282199 : if (wi::eq_p (op1.lower_bound (), op2.upper_bound()))
1084 144587 : r = range_true (type);
1085 : else
1086 137612 : 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 17165784 : int_range_max tmp = op1;
1093 17165784 : tmp.intersect (op2);
1094 17165784 : if (tmp.undefined_p ())
1095 235299 : r = range_false (type);
1096 : // Check if a constant cannot satisfy the bitmask requirements.
1097 31582200 : else if (op2_const && !op1.get_bitmask ().member_p (op2.lower_bound ()))
1098 0 : r = range_false (type);
1099 16983242 : else if (op1_const && !op2.get_bitmask ().member_p (op1.lower_bound ()))
1100 0 : r = range_false (type);
1101 : else
1102 16930485 : r = range_true_and_false (type);
1103 17165784 : }
1104 : return true;
1105 : }
1106 :
1107 : bool
1108 11070803 : operator_equal::op1_range (irange &r, tree type,
1109 : const irange &lhs,
1110 : const irange &op2,
1111 : relation_trio) const
1112 : {
1113 11070803 : switch (get_bool_state (r, lhs, type))
1114 : {
1115 3459608 : case BRS_TRUE:
1116 : // If it's true, the result is the same as OP2.
1117 3459608 : r = op2;
1118 3459608 : break;
1119 :
1120 7586757 : case BRS_FALSE:
1121 : // If the result is false, the only time we know anything is
1122 : // if OP2 is a constant.
1123 7586757 : if (!op2.undefined_p ()
1124 22760271 : && wi::eq_p (op2.lower_bound(), op2.upper_bound()))
1125 : {
1126 6061086 : r = op2;
1127 6061086 : r.invert ();
1128 : }
1129 : else
1130 1525671 : r.set_varying (type);
1131 : break;
1132 :
1133 : default:
1134 : break;
1135 : }
1136 11070803 : return true;
1137 : }
1138 :
1139 : bool
1140 1474596 : operator_equal::op2_range (irange &r, tree type,
1141 : const irange &lhs,
1142 : const irange &op1,
1143 : relation_trio rel) const
1144 : {
1145 1474596 : 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 9645874 : operator_not_equal::op1_op2_relation (const irange &lhs, const irange &,
1161 : const irange &) const
1162 : {
1163 9645874 : if (lhs.undefined_p ())
1164 : return VREL_UNDEFINED;
1165 :
1166 : // FALSE = op1 != op2 indicates EQ_EXPR.
1167 9645874 : if (lhs.zero_p ())
1168 : return VREL_EQ;
1169 :
1170 : // TRUE = op1 != op2 indicates NE_EXPR.
1171 4501325 : if (!contains_zero_p (lhs))
1172 4461821 : return VREL_NE;
1173 : return VREL_VARYING;
1174 : }
1175 :
1176 : bool
1177 26188777 : operator_not_equal::fold_range (irange &r, tree type,
1178 : const irange &op1,
1179 : const irange &op2,
1180 : relation_trio rel) const
1181 : {
1182 26188777 : 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 26167849 : bool op1_const = wi::eq_p (op1.lower_bound (), op1.upper_bound ());
1188 26167849 : bool op2_const = wi::eq_p (op2.lower_bound (), op2.upper_bound ());
1189 26167467 : if (op1_const && op2_const)
1190 : {
1191 1108558 : if (wi::ne_p (op1.lower_bound (), op2.upper_bound()))
1192 636940 : r = range_true (type);
1193 : else
1194 471616 : 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 25058911 : int_range_max tmp = op1;
1201 25058911 : tmp.intersect (op2);
1202 25058911 : if (tmp.undefined_p ())
1203 287289 : r = range_true (type);
1204 : // Check if a constant cannot satisfy the bitmask requirements.
1205 45207327 : else if (op2_const && !op1.get_bitmask ().member_p (op2.lower_bound ()))
1206 0 : r = range_true (type);
1207 24806574 : else if (op1_const && !op2.get_bitmask ().member_p (op1.lower_bound ()))
1208 0 : r = range_true (type);
1209 : else
1210 24771622 : r = range_true_and_false (type);
1211 25058911 : }
1212 : return true;
1213 : }
1214 :
1215 : bool
1216 19771347 : operator_not_equal::op1_range (irange &r, tree type,
1217 : const irange &lhs,
1218 : const irange &op2,
1219 : relation_trio) const
1220 : {
1221 19771347 : switch (get_bool_state (r, lhs, type))
1222 : {
1223 11994350 : case BRS_TRUE:
1224 : // If the result is true, the only time we know anything is if
1225 : // OP2 is a constant.
1226 11994350 : if (!op2.undefined_p ()
1227 35983050 : && wi::eq_p (op2.lower_bound(), op2.upper_bound()))
1228 : {
1229 9662316 : r = op2;
1230 9662316 : r.invert ();
1231 : }
1232 : else
1233 2332034 : r.set_varying (type);
1234 : break;
1235 :
1236 7752314 : case BRS_FALSE:
1237 : // If it's false, the result is the same as OP2.
1238 7752314 : r = op2;
1239 7752314 : break;
1240 :
1241 : default:
1242 : break;
1243 : }
1244 19771347 : return true;
1245 : }
1246 :
1247 :
1248 : bool
1249 2443366 : operator_not_equal::op2_range (irange &r, tree type,
1250 : const irange &lhs,
1251 : const irange &op1,
1252 : relation_trio rel) const
1253 : {
1254 2443366 : 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 6229203 : build_lt (irange &r, tree type, const wide_int &val)
1261 : {
1262 6229203 : wi::overflow_type ov;
1263 6229203 : wide_int lim;
1264 6229203 : signop sgn = TYPE_SIGN (type);
1265 :
1266 : // Signed 1 bit cannot represent 1 for subtraction.
1267 6229203 : if (sgn == SIGNED)
1268 4227295 : lim = wi::add (val, -1, sgn, &ov);
1269 : else
1270 2001966 : lim = wi::sub (val, 1, sgn, &ov);
1271 :
1272 : // If val - 1 underflows, check if X < MIN, which is an empty range.
1273 6229203 : if (ov)
1274 289 : r.set_undefined ();
1275 : else
1276 6228972 : r = int_range<1> (type, min_limit (type), lim);
1277 6229203 : }
1278 :
1279 : // (X <= VAL) produces the range of [MIN, VAL].
1280 :
1281 : static void
1282 13341349 : build_le (irange &r, tree type, const wide_int &val)
1283 : {
1284 13341349 : r = int_range<1> (type, min_limit (type), val);
1285 13341349 : }
1286 :
1287 : // (X > VAL) produces the range of [VAL + 1, MAX].
1288 :
1289 : static void
1290 9901729 : build_gt (irange &r, tree type, const wide_int &val)
1291 : {
1292 9901729 : wi::overflow_type ov;
1293 9901729 : wide_int lim;
1294 9901729 : signop sgn = TYPE_SIGN (type);
1295 :
1296 : // Signed 1 bit cannot represent 1 for addition.
1297 9901729 : if (sgn == SIGNED)
1298 5401707 : lim = wi::sub (val, -1, sgn, &ov);
1299 : else
1300 4500109 : lim = wi::add (val, 1, sgn, &ov);
1301 : // If val + 1 overflows, check is for X > MAX, which is an empty range.
1302 9901729 : if (ov)
1303 0 : r.set_undefined ();
1304 : else
1305 9901816 : r = int_range<1> (type, lim, max_limit (type));
1306 9901729 : }
1307 :
1308 : // (X >= val) produces the range of [VAL, MAX].
1309 :
1310 : static void
1311 6976546 : build_ge (irange &r, tree type, const wide_int &val)
1312 : {
1313 6976546 : r = int_range<1> (type, val, max_limit (type));
1314 6976546 : }
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 11743116 : operator_lt::op1_op2_relation (const irange &lhs, const irange &,
1328 : const irange &) const
1329 : {
1330 11743116 : if (lhs.undefined_p ())
1331 : return VREL_UNDEFINED;
1332 :
1333 : // FALSE = op1 < op2 indicates GE_EXPR.
1334 11743116 : if (lhs.zero_p ())
1335 : return VREL_GE;
1336 :
1337 : // TRUE = op1 < op2 indicates LT_EXPR.
1338 5910099 : if (!contains_zero_p (lhs))
1339 5902814 : return VREL_LT;
1340 : return VREL_VARYING;
1341 : }
1342 :
1343 : bool
1344 6468017 : operator_lt::fold_range (irange &r, tree type,
1345 : const irange &op1,
1346 : const irange &op2,
1347 : relation_trio rel) const
1348 : {
1349 6468017 : if (relop_early_resolve (r, type, op1, op2, rel, VREL_LT))
1350 : return true;
1351 :
1352 6445485 : signop sign = TYPE_SIGN (op1.type ());
1353 6445485 : gcc_checking_assert (sign == TYPE_SIGN (op2.type ()));
1354 :
1355 6445521 : if (wi::lt_p (op1.upper_bound (), op2.lower_bound (), sign))
1356 20856 : r = range_true (type);
1357 6424665 : else if (!wi::lt_p (op1.lower_bound (), op2.upper_bound (), sign))
1358 56546 : r = range_false (type);
1359 : // Use nonzero bits to determine if < 0 is false.
1360 8370580 : else if (op2.zero_p () && !wi::neg_p (op1.get_nonzero_bits (), sign))
1361 0 : r = range_false (type);
1362 : else
1363 6368083 : r = range_true_and_false (type);
1364 : return true;
1365 : }
1366 :
1367 : bool
1368 5405955 : operator_lt::op1_range (irange &r, tree type,
1369 : const irange &lhs,
1370 : const irange &op2,
1371 : relation_trio) const
1372 : {
1373 5405955 : if (op2.undefined_p ())
1374 : return false;
1375 :
1376 5405955 : switch (get_bool_state (r, lhs, type))
1377 : {
1378 2366715 : case BRS_TRUE:
1379 2366715 : build_lt (r, type, op2.upper_bound ());
1380 2366715 : break;
1381 :
1382 3034598 : case BRS_FALSE:
1383 3034598 : build_ge (r, type, op2.lower_bound ());
1384 3034598 : break;
1385 :
1386 : default:
1387 : break;
1388 : }
1389 : return true;
1390 : }
1391 :
1392 : bool
1393 3813688 : operator_lt::op2_range (irange &r, tree type,
1394 : const irange &lhs,
1395 : const irange &op1,
1396 : relation_trio) const
1397 : {
1398 3813688 : if (op1.undefined_p ())
1399 : return false;
1400 :
1401 3813686 : switch (get_bool_state (r, lhs, type))
1402 : {
1403 1629329 : case BRS_TRUE:
1404 1629329 : build_gt (r, type, op1.lower_bound ());
1405 1629329 : break;
1406 :
1407 2180943 : case BRS_FALSE:
1408 2180943 : build_le (r, type, op1.upper_bound ());
1409 2180943 : 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 4240932 : operator_le::op1_op2_relation (const irange &lhs, const irange &,
1429 : const irange &) const
1430 : {
1431 4240932 : if (lhs.undefined_p ())
1432 : return VREL_UNDEFINED;
1433 :
1434 : // FALSE = op1 <= op2 indicates GT_EXPR.
1435 4240932 : if (lhs.zero_p ())
1436 : return VREL_GT;
1437 :
1438 : // TRUE = op1 <= op2 indicates LE_EXPR.
1439 2371699 : if (!contains_zero_p (lhs))
1440 2362410 : return VREL_LE;
1441 : return VREL_VARYING;
1442 : }
1443 :
1444 : bool
1445 5035557 : operator_le::fold_range (irange &r, tree type,
1446 : const irange &op1,
1447 : const irange &op2,
1448 : relation_trio rel) const
1449 : {
1450 5035557 : if (relop_early_resolve (r, type, op1, op2, rel, VREL_LE))
1451 : return true;
1452 :
1453 5023980 : signop sign = TYPE_SIGN (op1.type ());
1454 5023980 : gcc_checking_assert (sign == TYPE_SIGN (op2.type ()));
1455 :
1456 5023984 : if (wi::le_p (op1.upper_bound (), op2.lower_bound (), sign))
1457 132571 : r = range_true (type);
1458 4891413 : else if (!wi::le_p (op1.lower_bound (), op2.upper_bound (), sign))
1459 50358 : r = range_false (type);
1460 : else
1461 4841051 : r = range_true_and_false (type);
1462 : return true;
1463 : }
1464 :
1465 : bool
1466 5918255 : operator_le::op1_range (irange &r, tree type,
1467 : const irange &lhs,
1468 : const irange &op2,
1469 : relation_trio) const
1470 : {
1471 5918255 : if (op2.undefined_p ())
1472 : return false;
1473 :
1474 5918255 : switch (get_bool_state (r, lhs, type))
1475 : {
1476 3153900 : case BRS_TRUE:
1477 3153900 : build_le (r, type, op2.upper_bound ());
1478 3153900 : break;
1479 :
1480 2751501 : case BRS_FALSE:
1481 2751501 : build_gt (r, type, op2.lower_bound ());
1482 2751501 : break;
1483 :
1484 : default:
1485 : break;
1486 : }
1487 : return true;
1488 : }
1489 :
1490 : bool
1491 1097644 : operator_le::op2_range (irange &r, tree type,
1492 : const irange &lhs,
1493 : const irange &op1,
1494 : relation_trio) const
1495 : {
1496 1097644 : if (op1.undefined_p ())
1497 : return false;
1498 :
1499 1097644 : switch (get_bool_state (r, lhs, type))
1500 : {
1501 484360 : case BRS_TRUE:
1502 484360 : build_ge (r, type, op1.lower_bound ());
1503 484360 : break;
1504 :
1505 609454 : case BRS_FALSE:
1506 609454 : build_lt (r, type, op1.upper_bound ());
1507 609454 : 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 11502443 : operator_gt::op1_op2_relation (const irange &lhs, const irange &,
1527 : const irange &) const
1528 : {
1529 11502443 : if (lhs.undefined_p ())
1530 : return VREL_UNDEFINED;
1531 :
1532 : // FALSE = op1 > op2 indicates LE_EXPR.
1533 11502443 : if (lhs.zero_p ())
1534 : return VREL_LE;
1535 :
1536 : // TRUE = op1 > op2 indicates GT_EXPR.
1537 6070922 : if (!contains_zero_p (lhs))
1538 6057523 : return VREL_GT;
1539 : return VREL_VARYING;
1540 : }
1541 :
1542 : bool
1543 11351947 : operator_gt::fold_range (irange &r, tree type,
1544 : const irange &op1, const irange &op2,
1545 : relation_trio rel) const
1546 : {
1547 11351947 : if (relop_early_resolve (r, type, op1, op2, rel, VREL_GT))
1548 : return true;
1549 :
1550 11303008 : signop sign = TYPE_SIGN (op1.type ());
1551 11303008 : gcc_checking_assert (sign == TYPE_SIGN (op2.type ()));
1552 :
1553 11303034 : if (wi::gt_p (op1.lower_bound (), op2.upper_bound (), sign))
1554 95368 : r = range_true (type);
1555 11207666 : else if (!wi::gt_p (op1.upper_bound (), op2.lower_bound (), sign))
1556 351764 : r = range_false (type);
1557 : else
1558 10855876 : r = range_true_and_false (type);
1559 : return true;
1560 : }
1561 :
1562 : bool
1563 12183889 : operator_gt::op1_range (irange &r, tree type,
1564 : const irange &lhs, const irange &op2,
1565 : relation_trio) const
1566 : {
1567 12183889 : if (op2.undefined_p ())
1568 : return false;
1569 :
1570 12183889 : switch (get_bool_state (r, lhs, type))
1571 : {
1572 4962079 : case BRS_TRUE:
1573 4962079 : build_gt (r, type, op2.lower_bound ());
1574 4962079 : break;
1575 :
1576 7212254 : case BRS_FALSE:
1577 7212254 : build_le (r, type, op2.upper_bound ());
1578 7212254 : break;
1579 :
1580 : default:
1581 : break;
1582 : }
1583 : return true;
1584 : }
1585 :
1586 : bool
1587 3567540 : operator_gt::op2_range (irange &r, tree type,
1588 : const irange &lhs,
1589 : const irange &op1,
1590 : relation_trio) const
1591 : {
1592 3567540 : if (op1.undefined_p ())
1593 : return false;
1594 :
1595 3567540 : switch (get_bool_state (r, lhs, type))
1596 : {
1597 2105514 : case BRS_TRUE:
1598 2105514 : build_lt (r, type, op1.upper_bound ());
1599 2105514 : break;
1600 :
1601 1453430 : case BRS_FALSE:
1602 1453430 : build_ge (r, type, op1.lower_bound ());
1603 1453430 : 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 3870004 : operator_ge::op1_op2_relation (const irange &lhs, const irange &,
1623 : const irange &) const
1624 : {
1625 3870004 : if (lhs.undefined_p ())
1626 : return VREL_UNDEFINED;
1627 :
1628 : // FALSE = op1 >= op2 indicates LT_EXPR.
1629 3870004 : if (lhs.zero_p ())
1630 : return VREL_LT;
1631 :
1632 : // TRUE = op1 >= op2 indicates GE_EXPR.
1633 2062082 : if (!contains_zero_p (lhs))
1634 2056427 : return VREL_GE;
1635 : return VREL_VARYING;
1636 : }
1637 :
1638 : bool
1639 2632930 : operator_ge::fold_range (irange &r, tree type,
1640 : const irange &op1,
1641 : const irange &op2,
1642 : relation_trio rel) const
1643 : {
1644 2632930 : if (relop_early_resolve (r, type, op1, op2, rel, VREL_GE))
1645 : return true;
1646 :
1647 2621076 : signop sign = TYPE_SIGN (op1.type ());
1648 2621076 : gcc_checking_assert (sign == TYPE_SIGN (op2.type ()));
1649 :
1650 2621108 : if (wi::ge_p (op1.lower_bound (), op2.upper_bound (), sign))
1651 170975 : r = range_true (type);
1652 2450133 : else if (!wi::ge_p (op1.upper_bound (), op2.lower_bound (), sign))
1653 5786 : r = range_false (type);
1654 : else
1655 2444315 : r = range_true_and_false (type);
1656 : return true;
1657 : }
1658 :
1659 : bool
1660 3158355 : operator_ge::op1_range (irange &r, tree type,
1661 : const irange &lhs,
1662 : const irange &op2,
1663 : relation_trio) const
1664 : {
1665 3158355 : if (op2.undefined_p ())
1666 : return false;
1667 :
1668 3158355 : switch (get_bool_state (r, lhs, type))
1669 : {
1670 2004158 : case BRS_TRUE:
1671 2004158 : build_ge (r, type, op2.lower_bound ());
1672 2004158 : break;
1673 :
1674 1147520 : case BRS_FALSE:
1675 1147520 : build_lt (r, type, op2.upper_bound ());
1676 1147520 : break;
1677 :
1678 : default:
1679 : break;
1680 : }
1681 : return true;
1682 : }
1683 :
1684 : bool
1685 1355856 : operator_ge::op2_range (irange &r, tree type,
1686 : const irange &lhs,
1687 : const irange &op1,
1688 : relation_trio) const
1689 : {
1690 1355856 : if (op1.undefined_p ())
1691 : return false;
1692 :
1693 1355856 : switch (get_bool_state (r, lhs, type))
1694 : {
1695 794252 : case BRS_TRUE:
1696 794252 : build_le (r, type, op1.upper_bound ());
1697 794252 : break;
1698 :
1699 558820 : case BRS_FALSE:
1700 558820 : build_gt (r, type, op1.lower_bound ());
1701 558820 : break;
1702 :
1703 : default:
1704 : break;
1705 : }
1706 : return true;
1707 : }
1708 :
1709 :
1710 : void
1711 49679028 : operator_plus::update_bitmask (irange &r, const irange &lh,
1712 : const irange &rh) const
1713 : {
1714 49679028 : update_known_bitmask (r, PLUS_EXPR, lh, rh);
1715 49679028 : }
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 45610758 : operator_plus::lhs_op1_relation (const irange &lhs,
1722 : const irange &op1,
1723 : const irange &op2,
1724 : relation_kind) const
1725 : {
1726 45610758 : if (lhs.undefined_p () || op1.undefined_p () || op2.undefined_p ())
1727 : return VREL_VARYING;
1728 :
1729 45583500 : tree type = lhs.type ();
1730 45583500 : unsigned prec = TYPE_PRECISION (type);
1731 45583500 : wi::overflow_type ovf1, ovf2;
1732 45583500 : signop sign = TYPE_SIGN (type);
1733 :
1734 : // LHS = OP1 + 0 indicates LHS == OP1.
1735 45583500 : if (op2.zero_p ())
1736 : return VREL_EQ;
1737 :
1738 45414782 : if (TYPE_OVERFLOW_WRAPS (type))
1739 : {
1740 25677391 : wi::add (op1.lower_bound (), op2.lower_bound (), sign, &ovf1);
1741 25677616 : wi::add (op1.upper_bound (), op2.upper_bound (), sign, &ovf2);
1742 : }
1743 : else
1744 19737841 : ovf1 = ovf2 = wi::OVF_NONE;
1745 :
1746 : // Never wrapping additions.
1747 45414782 : if (!ovf1 && !ovf2)
1748 : {
1749 : // Positive op2 means lhs > op1.
1750 27219027 : if (wi::gt_p (op2.lower_bound (), wi::zero (prec), sign))
1751 : return VREL_GT;
1752 10633203 : if (wi::ge_p (op2.lower_bound (), wi::zero (prec), sign))
1753 : return VREL_GE;
1754 :
1755 : // Negative op2 means lhs < op1.
1756 8581373 : if (wi::lt_p (op2.upper_bound (), wi::zero (prec), sign))
1757 : return VREL_LT;
1758 5292241 : if (wi::le_p (op2.upper_bound (), wi::zero (prec), sign))
1759 : return VREL_LE;
1760 : }
1761 : // Always wrapping additions.
1762 18196133 : else if (ovf1 && ovf1 == ovf2)
1763 : {
1764 : // Positive op2 means lhs < op1.
1765 721472 : 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 22753811 : 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 8246358 : operator_plus::lhs_op2_relation (const irange &lhs, const irange &op1,
1789 : const irange &op2, relation_kind rel) const
1790 : {
1791 8246358 : return lhs_op1_relation (lhs, op2, op1, rel);
1792 : }
1793 :
1794 : void
1795 73496599 : 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 73496599 : wi::overflow_type ov_lb, ov_ub;
1800 73496599 : signop s = TYPE_SIGN (type);
1801 73496599 : wide_int new_lb = wi::add (lh_lb, rh_lb, s, &ov_lb);
1802 73496599 : wide_int new_ub = wi::add (lh_ub, rh_ub, s, &ov_ub);
1803 73496599 : value_range_with_overflow (r, type, new_lb, new_ub, ov_lb, ov_ub);
1804 73496599 : }
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 760680 : plus_minus_ranges (irange &r_ov, irange &r_normal, const irange &offset,
1814 : bool add_p)
1815 : {
1816 760680 : 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 760680 : if (!offset.singleton_p () || offset.zero_p ())
1820 746062 : return kind;
1821 :
1822 : // Always work with a positive offset. ie a+ -2 -> a-2 and a- -2 > a+2
1823 14618 : wide_int off = offset.lower_bound ();
1824 14618 : if (wi::neg_p (off, SIGNED))
1825 : {
1826 1213 : add_p = !add_p;
1827 1213 : off = wi::neg (off);
1828 : }
1829 :
1830 14618 : wi::overflow_type ov;
1831 14618 : tree type = offset.type ();
1832 14618 : unsigned prec = TYPE_PRECISION (type);
1833 14618 : wide_int ub;
1834 14618 : wide_int lb;
1835 : // calculate the normal range and relation for the operation.
1836 14618 : if (add_p)
1837 : {
1838 : // [ 0 , INF - OFF]
1839 13405 : lb = wi::zero (prec);
1840 13405 : ub = wi::sub (irange_val_max (type), off, UNSIGNED, &ov);
1841 13405 : kind = VREL_GT;
1842 : }
1843 : else
1844 : {
1845 : // [ OFF, INF ]
1846 1213 : lb = off;
1847 1213 : ub = irange_val_max (type);
1848 1213 : kind = VREL_LT;
1849 : }
1850 14618 : int_range<2> normal_range (type, lb, ub);
1851 14618 : int_range<2> ov_range (type, lb, ub, VR_ANTI_RANGE);
1852 :
1853 14618 : r_ov = ov_range;
1854 14618 : r_normal = normal_range;
1855 14618 : return kind;
1856 14618 : }
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 10038976 : adjust_op1_for_overflow (irange &r, const irange &op2, relation_kind rel,
1869 : bool add_p)
1870 : {
1871 10038976 : if (r.undefined_p ())
1872 : return;
1873 10038974 : tree type = r.type ();
1874 : // Check for unsigned overflow and calculate the overflow part.
1875 10038974 : signop s = TYPE_SIGN (type);
1876 10038974 : if (!TYPE_OVERFLOW_WRAPS (type) || s == SIGNED)
1877 : return;
1878 :
1879 : // Only work with <, <=, >, >= relations.
1880 5055613 : if (!relation_lt_le_gt_ge_p (rel))
1881 : return;
1882 :
1883 : // Get the ranges for this offset.
1884 760680 : int_range_max normal, overflow;
1885 760680 : relation_kind k = plus_minus_ranges (overflow, normal, op2, add_p);
1886 :
1887 : // VREL_VARYING means there are no adjustments.
1888 760680 : if (k == VREL_VARYING)
1889 : return;
1890 :
1891 : // If the relations match use the normal range, otherwise use overflow range.
1892 14618 : if (relation_intersect (k, rel) == k)
1893 10483 : r.intersect (normal);
1894 : else
1895 4135 : r.intersect (overflow);
1896 : return;
1897 760680 : }
1898 :
1899 : bool
1900 9012939 : operator_plus::op1_range (irange &r, tree type,
1901 : const irange &lhs,
1902 : const irange &op2,
1903 : relation_trio trio) const
1904 : {
1905 9012939 : if (lhs.undefined_p ())
1906 : return false;
1907 : // Start with the default operation.
1908 9012939 : range_op_handler minus (MINUS_EXPR);
1909 9012939 : if (!minus)
1910 : return false;
1911 9012939 : bool res = minus.fold_range (r, type, lhs, op2);
1912 9012939 : relation_kind rel = trio.lhs_op1 ();
1913 : // Check for a relation refinement.
1914 9012939 : if (res)
1915 9012939 : adjust_op1_for_overflow (r, op2, rel, true /* PLUS_EXPR */);
1916 : return res;
1917 : }
1918 :
1919 : bool
1920 2141271 : operator_plus::op2_range (irange &r, tree type,
1921 : const irange &lhs,
1922 : const irange &op1,
1923 : relation_trio rel) const
1924 : {
1925 2141271 : 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 17780436 : operator_minus::update_bitmask (irange &r, const irange &lh,
1996 : const irange &rh) const
1997 : {
1998 17780436 : update_known_bitmask (r, MINUS_EXPR, lh, rh);
1999 17780436 : }
2000 :
2001 : void
2002 25045053 : 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 25045053 : wi::overflow_type ov_lb, ov_ub;
2007 25045053 : signop s = TYPE_SIGN (type);
2008 25045053 : wide_int new_lb = wi::sub (lh_lb, rh_ub, s, &ov_lb);
2009 25045053 : wide_int new_ub = wi::sub (lh_ub, rh_lb, s, &ov_ub);
2010 25045053 : value_range_with_overflow (r, type, new_lb, new_ub, ov_lb, ov_ub);
2011 25045053 : }
2012 :
2013 :
2014 : // Return the relation between LHS and OP1 based on the relation between
2015 : // OP1 and OP2.
2016 :
2017 : relation_kind
2018 4607862 : operator_minus::lhs_op1_relation (const irange &, const irange &op1,
2019 : const irange &, relation_kind rel) const
2020 : {
2021 4607862 : if (!op1.undefined_p () && TYPE_SIGN (op1.type ()) == UNSIGNED)
2022 2185364 : 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 20364898 : 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 20364898 : if (rel == VREL_VARYING)
2044 : return false;
2045 :
2046 247477 : int_range<2> rel_range;
2047 247477 : unsigned prec = TYPE_PRECISION (type);
2048 247477 : signop sgn = TYPE_SIGN (type);
2049 :
2050 : // == and != produce [0,0] and ~[0,0] regardless of wrapping.
2051 247477 : if (rel == VREL_EQ)
2052 8130 : rel_range = int_range<2> (type, wi::zero (prec), wi::zero (prec));
2053 239347 : else if (rel == VREL_NE)
2054 100878 : rel_range = int_range<2> (type, wi::zero (prec), wi::zero (prec),
2055 50439 : VR_ANTI_RANGE);
2056 188908 : else if (TYPE_OVERFLOW_WRAPS (type))
2057 : {
2058 120237 : 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 43322 : case VREL_GT:
2063 43322 : case VREL_LT:
2064 86644 : rel_range = int_range<2> (type, wi::zero (prec), wi::zero (prec),
2065 43322 : VR_ANTI_RANGE);
2066 43322 : break;
2067 : default:
2068 : return false;
2069 : }
2070 : }
2071 : else
2072 : {
2073 68671 : switch (rel)
2074 : {
2075 : // op1 > op2, op1 - op2 can be restricted to [1, +INF]
2076 21847 : case VREL_GT:
2077 43694 : rel_range = int_range<2> (type, wi::one (prec),
2078 43694 : wi::max_value (prec, sgn));
2079 21847 : break;
2080 : // op1 >= op2, op1 - op2 can be restricted to [0, +INF]
2081 46075 : case VREL_GE:
2082 92150 : rel_range = int_range<2> (type, wi::zero (prec),
2083 92150 : wi::max_value (prec, sgn));
2084 46075 : break;
2085 : // op1 < op2, op1 - op2 can be restricted to [-INF, -1]
2086 311 : case VREL_LT:
2087 622 : rel_range = int_range<2> (type, wi::min_value (prec, sgn),
2088 311 : wi::minus_one (prec));
2089 311 : 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 170408 : lhs_range.intersect (rel_range);
2100 170408 : return true;
2101 247477 : }
2102 :
2103 : bool
2104 17780436 : 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 17780436 : return minus_op1_op2_relation_effect (lhs_range, type, op1_range, op2_range,
2110 17780436 : rel);
2111 : }
2112 :
2113 : bool
2114 1026037 : operator_minus::op1_range (irange &r, tree type,
2115 : const irange &lhs,
2116 : const irange &op2,
2117 : relation_trio trio) const
2118 : {
2119 1026037 : if (lhs.undefined_p ())
2120 : return false;
2121 : // Start with the default operation.
2122 1026037 : range_op_handler minus (PLUS_EXPR);
2123 1026037 : if (!minus)
2124 : return false;
2125 1026037 : bool res = minus.fold_range (r, type, lhs, op2);
2126 1026037 : relation_kind rel = trio.lhs_op1 ();
2127 1026037 : if (res)
2128 1026037 : adjust_op1_for_overflow (r, op2, rel, false /* PLUS_EXPR */);
2129 : return res;
2130 :
2131 : }
2132 :
2133 : bool
2134 1712156 : operator_minus::op2_range (irange &r, tree type,
2135 : const irange &lhs,
2136 : const irange &op1,
2137 : relation_trio) const
2138 : {
2139 1712156 : if (lhs.undefined_p ())
2140 : return false;
2141 1712156 : return fold_range (r, type, op1, lhs);
2142 : }
2143 :
2144 : void
2145 947072 : operator_min::update_bitmask (irange &r, const irange &lh,
2146 : const irange &rh) const
2147 : {
2148 947072 : update_known_bitmask (r, MIN_EXPR, lh, rh);
2149 947072 : }
2150 :
2151 : void
2152 1468517 : 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 1468517 : signop s = TYPE_SIGN (type);
2157 1468517 : wide_int new_lb = wi::min (lh_lb, rh_lb, s);
2158 1468517 : wide_int new_ub = wi::min (lh_ub, rh_ub, s);
2159 1468517 : value_range_with_overflow (r, type, new_lb, new_ub);
2160 1468517 : }
2161 :
2162 :
2163 : void
2164 789017 : operator_max::update_bitmask (irange &r, const irange &lh,
2165 : const irange &rh) const
2166 : {
2167 789017 : update_known_bitmask (r, MAX_EXPR, lh, rh);
2168 789017 : }
2169 :
2170 : void
2171 954392 : 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 954392 : signop s = TYPE_SIGN (type);
2176 954392 : wide_int new_lb = wi::max (lh_lb, rh_lb, s);
2177 954392 : wide_int new_ub = wi::max (lh_ub, rh_ub, s);
2178 954392 : value_range_with_overflow (r, type, new_lb, new_ub);
2179 954392 : }
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 14608548 : 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 14608548 : wide_int cp1, cp2, cp3, cp4;
2203 : // Default to varying.
2204 14608548 : r.set_varying (type);
2205 :
2206 : // Compute the 4 cross operations, bailing if we get an overflow we
2207 : // can't handle.
2208 14608548 : if (wi_op_overflows (cp1, type, lh_lb, rh_lb))
2209 : return;
2210 14608510 : if (wi::eq_p (lh_lb, lh_ub))
2211 4354971 : cp3 = cp1;
2212 10253539 : else if (wi_op_overflows (cp3, type, lh_ub, rh_lb))
2213 : return;
2214 14608510 : if (wi::eq_p (rh_lb, rh_ub))
2215 11300365 : cp2 = cp1;
2216 3308145 : else if (wi_op_overflows (cp2, type, lh_lb, rh_ub))
2217 : return;
2218 14606226 : if (wi::eq_p (lh_lb, lh_ub))
2219 4354951 : cp4 = cp2;
2220 10251275 : else if (wi_op_overflows (cp4, type, lh_ub, rh_ub))
2221 : return;
2222 :
2223 : // Order pairs.
2224 14606226 : signop sign = TYPE_SIGN (type);
2225 14606226 : if (wi::gt_p (cp1, cp2, sign))
2226 1535845 : std::swap (cp1, cp2);
2227 14606226 : if (wi::gt_p (cp3, cp4, sign))
2228 1466672 : std::swap (cp3, cp4);
2229 :
2230 : // Choose min and max from the ordered pairs.
2231 14606226 : wide_int res_lb = wi::min (cp1, cp3, sign);
2232 14606226 : wide_int res_ub = wi::max (cp2, cp4, sign);
2233 14606226 : value_range_with_overflow (r, type, res_lb, res_ub);
2234 14610098 : }
2235 :
2236 :
2237 : void
2238 14168922 : operator_mult::update_bitmask (irange &r, const irange &lh,
2239 : const irange &rh) const
2240 : {
2241 14168922 : update_known_bitmask (r, MULT_EXPR, lh, rh);
2242 14168922 : }
2243 :
2244 : bool
2245 1200479 : operator_mult::op1_range (irange &r, tree type,
2246 : const irange &lhs, const irange &op2,
2247 : relation_trio) const
2248 : {
2249 1200479 : 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 1200479 : if (TYPE_OVERFLOW_WRAPS (type))
2256 : return false;
2257 :
2258 341988 : wide_int offset;
2259 341988 : if (op2.singleton_p (offset) && offset != 0)
2260 230311 : 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 111677 : if (!lhs.contains_p (wi::zero (TYPE_PRECISION (lhs.type ()))))
2264 : {
2265 23232 : r.set_nonzero (type);
2266 23232 : return true;
2267 : }
2268 : return false;
2269 341988 : }
2270 :
2271 : bool
2272 128005 : operator_mult::op2_range (irange &r, tree type,
2273 : const irange &lhs, const irange &op1,
2274 : relation_trio rel) const
2275 : {
2276 128005 : return operator_mult::op1_range (r, type, lhs, op1, rel.swap_op1_op2 ());
2277 : }
2278 :
2279 : bool
2280 14695387 : operator_mult::wi_op_overflows (wide_int &res, tree type,
2281 : const wide_int &w0, const wide_int &w1) const
2282 : {
2283 14695387 : wi::overflow_type overflow = wi::OVF_NONE;
2284 14695387 : signop sign = TYPE_SIGN (type);
2285 14695387 : res = wi::mul (w0, w1, sign, &overflow);
2286 14695387 : 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 7035901 : if (sign == UNSIGNED || w0.sign_mask () == w1.sign_mask ())
2291 3890478 : res = wi::max_value (w0.get_precision (), sign);
2292 : else
2293 3145603 : res = wi::min_value (w0.get_precision (), sign);
2294 7035901 : return false;
2295 : }
2296 7659486 : return overflow;
2297 : }
2298 :
2299 : void
2300 17910570 : 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 17910570 : if (TYPE_OVERFLOW_UNDEFINED (type))
2305 : {
2306 6098173 : wi_cross_product (r, type, lh_lb, lh_ub, rh_lb, rh_ub);
2307 6098173 : 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 11812397 : signop sign = TYPE_SIGN (type);
2321 11812397 : unsigned prec = TYPE_PRECISION (type);
2322 11812397 : widest2_int min0 = widest2_int::from (lh_lb, sign);
2323 11812397 : widest2_int max0 = widest2_int::from (lh_ub, sign);
2324 11812397 : widest2_int min1 = widest2_int::from (rh_lb, sign);
2325 11812397 : widest2_int max1 = widest2_int::from (rh_ub, sign);
2326 11812397 : widest2_int sizem1 = wi::mask <widest2_int> (prec, false);
2327 11812397 : widest2_int size = sizem1 + 1;
2328 :
2329 : // Canonicalize the intervals.
2330 11812397 : if (sign == UNSIGNED)
2331 : {
2332 11111114 : if (wi::ltu_p (size, min0 + max0))
2333 : {
2334 1607100 : min0 -= size;
2335 1607100 : max0 -= size;
2336 : }
2337 11111082 : if (wi::ltu_p (size, min1 + max1))
2338 : {
2339 166100 : min1 -= size;
2340 166100 : max1 -= size;
2341 : }
2342 : }
2343 :
2344 : // Sort the 4 products so that min is in prod0 and max is in
2345 : // prod3.
2346 11812397 : widest2_int prod0 = min0 * min1;
2347 11812397 : widest2_int prod1 = min0 * max1;
2348 11812397 : widest2_int prod2 = max0 * min1;
2349 11812397 : widest2_int prod3 = max0 * max1;
2350 :
2351 : // min0min1 > max0max1
2352 11812397 : if (prod0 > prod3)
2353 198972 : std::swap (prod0, prod3);
2354 :
2355 : // min0max1 > max0min1
2356 11812397 : if (prod1 > prod2)
2357 329646 : std::swap (prod1, prod2);
2358 :
2359 11812397 : if (prod0 > prod1)
2360 80390 : std::swap (prod0, prod1);
2361 :
2362 11812397 : if (prod2 > prod3)
2363 3885 : std::swap (prod2, prod3);
2364 :
2365 : // diff = max - min
2366 11812397 : prod2 = prod3 - prod0;
2367 11812397 : if (wi::geu_p (prod2, sizem1))
2368 : {
2369 : // Multiplying by X, where X is a power of 2 is [0,0][X,+INF].
2370 7903531 : if (TYPE_UNSIGNED (type) && rh_lb == rh_ub
2371 7285802 : && wi::exact_log2 (rh_lb) != -1 && prec > 1)
2372 : {
2373 2724405 : r.set (type, rh_lb, wi::max_value (prec, sign));
2374 2724405 : int_range<2> zero;
2375 2724405 : zero.set_zero (type);
2376 2724405 : r.union_ (zero);
2377 2724405 : }
2378 : else
2379 : // The range covers all values.
2380 1299038 : r.set_varying (type);
2381 : }
2382 : else
2383 : {
2384 7788954 : wide_int new_lb = wide_int::from (prod0, prec, sign);
2385 7788954 : wide_int new_ub = wide_int::from (prod3, prec, sign);
2386 7788954 : create_possibly_reversed_range (r, type, new_lb, new_ub);
2387 7788997 : }
2388 11813044 : }
2389 :
2390 : bool
2391 14168922 : operator_mult::op1_op2_relation_effect (irange &lhs_range, tree type,
2392 : const irange &,
2393 : const irange &,
2394 : relation_kind rel) const
2395 : {
2396 : // a*a is nonnegative without overflow.
2397 : // tree_binary_nonnegative_p handles this in a similar way.
2398 14168922 : if (rel == VREL_EQ
2399 14168922 : && TYPE_OVERFLOW_UNDEFINED (type))
2400 : {
2401 34655 : int_range<2> nonnegative;
2402 34655 : nonnegative.set_nonnegative (type);
2403 34655 : lhs_range.intersect (nonnegative);
2404 34655 : return true;
2405 34655 : }
2406 : return false;
2407 : }
2408 :
2409 : class operator_widen_mult_signed : public range_operator
2410 : {
2411 : public:
2412 : virtual void wi_fold (irange &r, tree type,
2413 : const wide_int &lh_lb,
2414 : const wide_int &lh_ub,
2415 : const wide_int &rh_lb,
2416 : const wide_int &rh_ub)
2417 : const;
2418 : } op_widen_mult_signed;
2419 :
2420 : void
2421 1347 : operator_widen_mult_signed::wi_fold (irange &r, tree type,
2422 : const wide_int &lh_lb,
2423 : const wide_int &lh_ub,
2424 : const wide_int &rh_lb,
2425 : const wide_int &rh_ub) const
2426 : {
2427 1347 : wide_int lh_wlb = wide_int::from (lh_lb, TYPE_PRECISION (type), SIGNED);
2428 1347 : wide_int lh_wub = wide_int::from (lh_ub, TYPE_PRECISION (type), SIGNED);
2429 1347 : wide_int rh_wlb = wide_int::from (rh_lb, TYPE_PRECISION (type), SIGNED);
2430 1347 : wide_int rh_wub = wide_int::from (rh_ub, TYPE_PRECISION (type), SIGNED);
2431 :
2432 : /* We don't expect a widening multiplication to be able to overflow but range
2433 : calculations for multiplications are complicated. After widening the
2434 : operands lets call the base class. */
2435 1347 : return op_mult.wi_fold (r, type, lh_wlb, lh_wub, rh_wlb, rh_wub);
2436 1347 : }
2437 :
2438 : class operator_widen_mult_unsigned : public range_operator
2439 : {
2440 : public:
2441 : virtual void wi_fold (irange &r, tree type,
2442 : const wide_int &lh_lb,
2443 : const wide_int &lh_ub,
2444 : const wide_int &rh_lb,
2445 : const wide_int &rh_ub)
2446 : const;
2447 : } op_widen_mult_unsigned;
2448 :
2449 : void
2450 5484 : operator_widen_mult_unsigned::wi_fold (irange &r, tree type,
2451 : const wide_int &lh_lb,
2452 : const wide_int &lh_ub,
2453 : const wide_int &rh_lb,
2454 : const wide_int &rh_ub) const
2455 : {
2456 5484 : wide_int lh_wlb = wide_int::from (lh_lb, TYPE_PRECISION (type), UNSIGNED);
2457 5484 : wide_int lh_wub = wide_int::from (lh_ub, TYPE_PRECISION (type), UNSIGNED);
2458 5484 : wide_int rh_wlb = wide_int::from (rh_lb, TYPE_PRECISION (type), UNSIGNED);
2459 5484 : wide_int rh_wub = wide_int::from (rh_ub, TYPE_PRECISION (type), UNSIGNED);
2460 :
2461 : /* We don't expect a widening multiplication to be able to overflow but range
2462 : calculations for multiplications are complicated. After widening the
2463 : operands lets call the base class. */
2464 5484 : return op_mult.wi_fold (r, type, lh_wlb, lh_wub, rh_wlb, rh_wub);
2465 5484 : }
2466 :
2467 : class operator_widen_mult_signed_unsigned : public range_operator
2468 : {
2469 : public:
2470 : virtual void wi_fold (irange &r, tree type,
2471 : const wide_int &lh_lb,
2472 : const wide_int &lh_ub,
2473 : const wide_int &rh_lb,
2474 : const wide_int &rh_ub)
2475 : const;
2476 : } op_widen_mult_signed_unsigned;
2477 :
2478 : void
2479 0 : operator_widen_mult_signed_unsigned::wi_fold (irange &r, tree type,
2480 : const wide_int &lh_lb,
2481 : const wide_int &lh_ub,
2482 : const wide_int &rh_lb,
2483 : const wide_int &rh_ub) const
2484 : {
2485 0 : wide_int lh_wlb = wide_int::from (lh_lb, TYPE_PRECISION (type), SIGNED);
2486 0 : wide_int lh_wub = wide_int::from (lh_ub, TYPE_PRECISION (type), SIGNED);
2487 0 : wide_int rh_wlb = wide_int::from (rh_lb, TYPE_PRECISION (type), UNSIGNED);
2488 0 : wide_int rh_wub = wide_int::from (rh_ub, TYPE_PRECISION (type), UNSIGNED);
2489 :
2490 : /* We don't expect a widening multiplication to be able to overflow but range
2491 : calculations for multiplications are complicated. After widening the
2492 : operands lets call the base class. */
2493 0 : return op_mult.wi_fold (r, type, lh_wlb, lh_wub, rh_wlb, rh_wub);
2494 0 : }
2495 :
2496 : class operator_div : public cross_product_operator
2497 : {
2498 : using range_operator::update_bitmask;
2499 : using range_operator::op2_range;
2500 : public:
2501 : operator_div (tree_code div_kind) { m_code = div_kind; }
2502 : bool op2_range (irange &r, tree type, const irange &lhs, const irange &,
2503 : relation_trio) const final override;
2504 : virtual void wi_fold (irange &r, tree type,
2505 : const wide_int &lh_lb,
2506 : const wide_int &lh_ub,
2507 : const wide_int &rh_lb,
2508 : const wide_int &rh_ub) const final override;
2509 : virtual bool wi_op_overflows (wide_int &res, tree type,
2510 : const wide_int &, const wide_int &)
2511 : const final override;
2512 2905454 : void update_bitmask (irange &r, const irange &lh, const irange &rh)
2513 : const final override
2514 2905454 : { update_known_bitmask (r, m_code, lh, rh); }
2515 : protected:
2516 : tree_code m_code;
2517 : };
2518 :
2519 : static const operator_div op_trunc_div (TRUNC_DIV_EXPR);
2520 : static const operator_div op_floor_div (FLOOR_DIV_EXPR);
2521 : static const operator_div op_round_div (ROUND_DIV_EXPR);
2522 : static const operator_div op_ceil_div (CEIL_DIV_EXPR);
2523 :
2524 : // Set OP2 to non-zero if the LHS isn't UNDEFINED.
2525 : bool
2526 37346 : operator_div::op2_range (irange &r, tree type, const irange &lhs,
2527 : const irange &, relation_trio) const
2528 : {
2529 37346 : if (!lhs.undefined_p ())
2530 : {
2531 37346 : r.set_nonzero (type);
2532 37346 : return true;
2533 : }
2534 : return false;
2535 : }
2536 :
2537 : bool
2538 12496062 : operator_div::wi_op_overflows (wide_int &res, tree type,
2539 : const wide_int &w0, const wide_int &w1) const
2540 : {
2541 12496062 : if (w1 == 0)
2542 : return true;
2543 :
2544 12496062 : wi::overflow_type overflow = wi::OVF_NONE;
2545 12496062 : signop sign = TYPE_SIGN (type);
2546 :
2547 12496062 : switch (m_code)
2548 : {
2549 12348558 : case EXACT_DIV_EXPR:
2550 12348558 : case TRUNC_DIV_EXPR:
2551 12348558 : res = wi::div_trunc (w0, w1, sign, &overflow);
2552 12348558 : break;
2553 135725 : case FLOOR_DIV_EXPR:
2554 135725 : res = wi::div_floor (w0, w1, sign, &overflow);
2555 135725 : break;
2556 288 : case ROUND_DIV_EXPR:
2557 288 : res = wi::div_round (w0, w1, sign, &overflow);
2558 288 : break;
2559 11491 : case CEIL_DIV_EXPR:
2560 11491 : res = wi::div_ceil (w0, w1, sign, &overflow);
2561 11491 : break;
2562 0 : default:
2563 0 : gcc_unreachable ();
2564 : }
2565 :
2566 12496062 : if (overflow && TYPE_OVERFLOW_UNDEFINED (type))
2567 : {
2568 : // For division, the only case is -INF / -1 = +INF.
2569 210038 : res = wi::max_value (w0.get_precision (), sign);
2570 210038 : return false;
2571 : }
2572 12286024 : return overflow;
2573 : }
2574 :
2575 : void
2576 4032732 : operator_div::wi_fold (irange &r, tree type,
2577 : const wide_int &lh_lb, const wide_int &lh_ub,
2578 : const wide_int &rh_lb, const wide_int &rh_ub) const
2579 : {
2580 4032732 : const wide_int dividend_min = lh_lb;
2581 4032732 : const wide_int dividend_max = lh_ub;
2582 4032732 : const wide_int divisor_min = rh_lb;
2583 4032732 : const wide_int divisor_max = rh_ub;
2584 4032732 : signop sign = TYPE_SIGN (type);
2585 4032732 : unsigned prec = TYPE_PRECISION (type);
2586 4032732 : wide_int extra_min, extra_max;
2587 :
2588 : // If we know we won't divide by zero, just do the division.
2589 4032732 : if (!wi_includes_zero_p (type, divisor_min, divisor_max))
2590 : {
2591 3347213 : wi_cross_product (r, type, dividend_min, dividend_max,
2592 : divisor_min, divisor_max);
2593 3347213 : return;
2594 : }
2595 :
2596 : // If we're definitely dividing by zero, there's nothing to do.
2597 685519 : if (wi_zero_p (type, divisor_min, divisor_max))
2598 : {
2599 18928 : r.set_undefined ();
2600 18928 : return;
2601 : }
2602 :
2603 : // Perform the division in 2 parts, [LB, -1] and [1, UB], which will
2604 : // skip any division by zero.
2605 :
2606 : // First divide by the negative numbers, if any.
2607 666591 : if (wi::neg_p (divisor_min, sign))
2608 865654 : wi_cross_product (r, type, dividend_min, dividend_max,
2609 865654 : divisor_min, wi::minus_one (prec));
2610 : else
2611 233764 : r.set_undefined ();
2612 :
2613 : // Then divide by the non-zero positive numbers, if any.
2614 666591 : if (wi::gt_p (divisor_max, wi::zero (prec), sign))
2615 : {
2616 665828 : int_range_max tmp;
2617 1331656 : wi_cross_product (tmp, type, dividend_min, dividend_max,
2618 665828 : wi::one (prec), divisor_max);
2619 665828 : r.union_ (tmp);
2620 665828 : }
2621 : // We shouldn't still have undefined here.
2622 666591 : gcc_checking_assert (!r.undefined_p ());
2623 4033384 : }
2624 :
2625 :
2626 : class operator_exact_divide : public operator_div
2627 : {
2628 : using range_operator::op1_range;
2629 : public:
2630 : operator_exact_divide () : operator_div (EXACT_DIV_EXPR) { }
2631 : virtual bool op1_range (irange &r, tree type,
2632 : const irange &lhs,
2633 : const irange &op2,
2634 : relation_trio) const;
2635 :
2636 : } op_exact_div;
2637 :
2638 : bool
2639 571628 : operator_exact_divide::op1_range (irange &r, tree type,
2640 : const irange &lhs,
2641 : const irange &op2,
2642 : relation_trio) const
2643 : {
2644 571628 : if (lhs.undefined_p ())
2645 : return false;
2646 571628 : wide_int offset;
2647 : // [2, 4] = op1 / [3,3] since its exact divide, no need to worry about
2648 : // remainders in the endpoints, so op1 = [2,4] * [3,3] = [6,12].
2649 : // We wont bother trying to enumerate all the in between stuff :-P
2650 : // TRUE accuracy is [6,6][9,9][12,12]. This is unlikely to matter most of
2651 : // the time however.
2652 : // If op2 is a multiple of 2, we would be able to set some non-zero bits.
2653 571628 : if (op2.singleton_p (offset) && offset != 0)
2654 571628 : return range_op_handler (MULT_EXPR).fold_range (r, type, lhs, op2);
2655 : return false;
2656 571628 : }
2657 :
2658 :
2659 : class operator_lshift : public cross_product_operator
2660 : {
2661 : using range_operator::fold_range;
2662 : using range_operator::op1_range;
2663 : using range_operator::update_bitmask;
2664 : public:
2665 : virtual bool op1_range (irange &r, tree type, const irange &lhs,
2666 : const irange &op2, relation_trio rel = TRIO_VARYING)
2667 : const final override;
2668 : virtual bool fold_range (irange &r, tree type, const irange &op1,
2669 : const irange &op2, relation_trio rel = TRIO_VARYING)
2670 : const final override;
2671 :
2672 : virtual void wi_fold (irange &r, tree type,
2673 : const wide_int &lh_lb, const wide_int &lh_ub,
2674 : const wide_int &rh_lb,
2675 : const wide_int &rh_ub) const final override;
2676 : virtual bool wi_op_overflows (wide_int &res,
2677 : tree type,
2678 : const wide_int &,
2679 : const wide_int &) const final override;
2680 457452 : void update_bitmask (irange &r, const irange &lh,
2681 : const irange &rh) const final override
2682 457452 : { update_known_bitmask (r, LSHIFT_EXPR, lh, rh); }
2683 : // Check compatibility of LHS and op1.
2684 1069399 : bool operand_check_p (tree t1, tree t2, tree) const final override
2685 1069399 : { return range_compatible_p (t1, t2); }
2686 : } op_lshift;
2687 :
2688 : class operator_rshift : public cross_product_operator
2689 : {
2690 : using range_operator::fold_range;
2691 : using range_operator::op1_range;
2692 : using range_operator::lhs_op1_relation;
2693 : using range_operator::update_bitmask;
2694 : public:
2695 : virtual bool fold_range (irange &r, tree type, const irange &op1,
2696 : const irange &op2, relation_trio rel = TRIO_VARYING)
2697 : const final override;
2698 : virtual void wi_fold (irange &r, tree type,
2699 : const wide_int &lh_lb,
2700 : const wide_int &lh_ub,
2701 : const wide_int &rh_lb,
2702 : const wide_int &rh_ub) const final override;
2703 : virtual bool wi_op_overflows (wide_int &res,
2704 : tree type,
2705 : const wide_int &w0,
2706 : const wide_int &w1) const final override;
2707 : virtual bool op1_range (irange &, tree type, const irange &lhs,
2708 : const irange &op2, relation_trio rel = TRIO_VARYING)
2709 : const final override;
2710 : virtual relation_kind lhs_op1_relation (const irange &lhs, const irange &op1,
2711 : const irange &op2, relation_kind rel)
2712 : const final override;
2713 3202431 : void update_bitmask (irange &r, const irange &lh,
2714 : const irange &rh) const final override
2715 3202431 : { update_known_bitmask (r, RSHIFT_EXPR, lh, rh); }
2716 : // Check compatibility of LHS and op1.
2717 3288253 : bool operand_check_p (tree t1, tree t2, tree) const final override
2718 3288253 : { return range_compatible_p (t1, t2); }
2719 : } op_rshift;
2720 :
2721 :
2722 : relation_kind
2723 2332281 : operator_rshift::lhs_op1_relation (const irange &lhs ATTRIBUTE_UNUSED,
2724 : const irange &op1,
2725 : const irange &op2,
2726 : relation_kind) const
2727 : {
2728 : // If both operands range are >= 0, then the LHS <= op1.
2729 2332281 : if (!op1.undefined_p () && !op2.undefined_p ()
2730 4663911 : && wi::ge_p (op1.lower_bound (), 0, TYPE_SIGN (op1.type ()))
2731 6763709 : && wi::ge_p (op2.lower_bound (), 0, TYPE_SIGN (op2.type ())))
2732 2072258 : return VREL_LE;
2733 : return VREL_VARYING;
2734 : }
2735 :
2736 : bool
2737 1590911 : operator_lshift::fold_range (irange &r, tree type,
2738 : const irange &op1,
2739 : const irange &op2,
2740 : relation_trio rel) const
2741 : {
2742 1590911 : int_range_max shift_range;
2743 1590911 : if (!get_shift_range (shift_range, type, op2))
2744 : {
2745 578 : if (op2.undefined_p ())
2746 228 : r.set_undefined ();
2747 : else
2748 350 : r.set_zero (type);
2749 578 : return true;
2750 : }
2751 :
2752 : // Transform left shifts by constants into multiplies.
2753 1590333 : if (shift_range.singleton_p ())
2754 : {
2755 1132854 : unsigned shift = shift_range.lower_bound ().to_uhwi ();
2756 1132854 : wide_int tmp = wi::set_bit_in_zero (shift, TYPE_PRECISION (type));
2757 1132854 : int_range<1> mult (type, tmp, tmp);
2758 :
2759 : // Force wrapping multiplication.
2760 1132854 : bool saved_flag_wrapv = flag_wrapv;
2761 1132854 : bool saved_flag_wrapv_pointer = flag_wrapv_pointer;
2762 1132854 : flag_wrapv = 1;
2763 1132854 : flag_wrapv_pointer = 1;
2764 1132854 : bool b = op_mult.fold_range (r, type, op1, mult);
2765 1132854 : flag_wrapv = saved_flag_wrapv;
2766 1132854 : flag_wrapv_pointer = saved_flag_wrapv_pointer;
2767 1132854 : return b;
2768 1132863 : }
2769 : else
2770 : // Otherwise, invoke the generic fold routine.
2771 457479 : return range_operator::fold_range (r, type, op1, shift_range, rel);
2772 1590911 : }
2773 :
2774 : void
2775 541578 : operator_lshift::wi_fold (irange &r, tree type,
2776 : const wide_int &lh_lb, const wide_int &lh_ub,
2777 : const wide_int &rh_lb, const wide_int &rh_ub) const
2778 : {
2779 541578 : signop sign = TYPE_SIGN (type);
2780 541578 : unsigned prec = TYPE_PRECISION (type);
2781 541578 : int overflow_pos = sign == SIGNED ? prec - 1 : prec;
2782 541578 : int bound_shift = overflow_pos - rh_ub.to_shwi ();
2783 : // If bound_shift == HOST_BITS_PER_WIDE_INT, the llshift can
2784 : // overflow. However, for that to happen, rh.max needs to be zero,
2785 : // which means rh is a singleton range of zero, which means we simply return
2786 : // [lh_lb, lh_ub] as the range.
2787 541578 : if (wi::eq_p (rh_ub, rh_lb) && wi::eq_p (rh_ub, 0))
2788 : {
2789 22835 : r = int_range<2> (type, lh_lb, lh_ub);
2790 22835 : return;
2791 : }
2792 :
2793 518743 : wide_int bound = wi::set_bit_in_zero (bound_shift, prec);
2794 518743 : wide_int complement = ~(bound - 1);
2795 518743 : wide_int low_bound, high_bound;
2796 518743 : bool in_bounds = false;
2797 :
2798 518743 : if (sign == UNSIGNED)
2799 : {
2800 261786 : low_bound = bound;
2801 261786 : high_bound = complement;
2802 261786 : if (wi::ltu_p (lh_ub, low_bound))
2803 : {
2804 : // [5, 6] << [1, 2] == [10, 24].
2805 : // We're shifting out only zeroes, the value increases
2806 : // monotonically.
2807 : in_bounds = true;
2808 : }
2809 85411 : else if (wi::ltu_p (high_bound, lh_lb))
2810 : {
2811 : // [0xffffff00, 0xffffffff] << [1, 2]
2812 : // == [0xfffffc00, 0xfffffffe].
2813 : // We're shifting out only ones, the value decreases
2814 : // monotonically.
2815 : in_bounds = true;
2816 : }
2817 : }
2818 : else
2819 : {
2820 : // [-1, 1] << [1, 2] == [-4, 4]
2821 256957 : low_bound = complement;
2822 256957 : high_bound = bound;
2823 256957 : if (wi::lts_p (lh_ub, high_bound)
2824 256957 : && wi::lts_p (low_bound, lh_lb))
2825 : {
2826 : // For non-negative numbers, we're shifting out only zeroes,
2827 : // the value increases monotonically. For negative numbers,
2828 : // we're shifting out only ones, the value decreases
2829 : // monotonically.
2830 : in_bounds = true;
2831 : }
2832 : }
2833 :
2834 : if (in_bounds)
2835 295741 : wi_cross_product (r, type, lh_lb, lh_ub, rh_lb, rh_ub);
2836 : else
2837 223002 : r.set_varying (type);
2838 518761 : }
2839 :
2840 : bool
2841 572776 : operator_lshift::wi_op_overflows (wide_int &res, tree type,
2842 : const wide_int &w0, const wide_int &w1) const
2843 : {
2844 572776 : signop sign = TYPE_SIGN (type);
2845 572776 : if (wi::neg_p (w1))
2846 : {
2847 : // It's unclear from the C standard whether shifts can overflow.
2848 : // The following code ignores overflow; perhaps a C standard
2849 : // interpretation ruling is needed.
2850 0 : res = wi::rshift (w0, -w1, sign);
2851 : }
2852 : else
2853 572776 : res = wi::lshift (w0, w1);
2854 572776 : return false;
2855 : }
2856 :
2857 : bool
2858 47867 : operator_lshift::op1_range (irange &r,
2859 : tree type,
2860 : const irange &lhs,
2861 : const irange &op2,
2862 : relation_trio) const
2863 : {
2864 47867 : if (lhs.undefined_p ())
2865 : return false;
2866 :
2867 47867 : if (!contains_zero_p (lhs))
2868 21204 : r.set_nonzero (type);
2869 : else
2870 26663 : r.set_varying (type);
2871 :
2872 47867 : wide_int shift;
2873 47867 : if (op2.singleton_p (shift))
2874 : {
2875 42323 : if (wi::lt_p (shift, 0, SIGNED))
2876 : return false;
2877 42323 : if (wi::ge_p (shift, wi::uhwi (TYPE_PRECISION (type),
2878 42323 : TYPE_PRECISION (op2.type ())),
2879 : UNSIGNED))
2880 : return false;
2881 42323 : if (shift == 0)
2882 : {
2883 6 : r.intersect (lhs);
2884 6 : return true;
2885 : }
2886 :
2887 : // Work completely in unsigned mode to start.
2888 42317 : tree utype = type;
2889 42317 : int_range_max tmp_range;
2890 42317 : if (TYPE_SIGN (type) == SIGNED)
2891 : {
2892 7296 : int_range_max tmp = lhs;
2893 7296 : utype = unsigned_type_for (type);
2894 7296 : range_cast (tmp, utype);
2895 7296 : op_rshift.fold_range (tmp_range, utype, tmp, op2);
2896 7296 : }
2897 : else
2898 35021 : op_rshift.fold_range (tmp_range, utype, lhs, op2);
2899 :
2900 : // Start with ranges which can produce the LHS by right shifting the
2901 : // result by the shift amount.
2902 : // ie [0x08, 0xF0] = op1 << 2 will start with
2903 : // [00001000, 11110000] = op1 << 2
2904 : // [0x02, 0x4C] aka [00000010, 00111100]
2905 :
2906 : // Then create a range from the LB with the least significant upper bit
2907 : // set, to the upper bound with all the bits set.
2908 : // This would be [0x42, 0xFC] aka [01000010, 11111100].
2909 :
2910 : // Ideally we do this for each subrange, but just lump them all for now.
2911 42317 : unsigned low_bits = TYPE_PRECISION (utype) - shift.to_uhwi ();
2912 42317 : wide_int up_mask = wi::mask (low_bits, true, TYPE_PRECISION (utype));
2913 42317 : wide_int new_ub = wi::bit_or (up_mask, tmp_range.upper_bound ());
2914 42317 : wide_int new_lb = wi::set_bit (tmp_range.lower_bound (), low_bits);
2915 42317 : int_range<2> fill_range (utype, new_lb, new_ub);
2916 42317 : tmp_range.union_ (fill_range);
2917 :
2918 42317 : if (utype != type)
2919 7296 : range_cast (tmp_range, type);
2920 :
2921 42317 : r.intersect (tmp_range);
2922 42317 : return true;
2923 42317 : }
2924 :
2925 5544 : return !r.varying_p ();
2926 47867 : }
2927 :
2928 : bool
2929 790968 : operator_rshift::op1_range (irange &r,
2930 : tree type,
2931 : const irange &lhs,
2932 : const irange &op2,
2933 : relation_trio) const
2934 : {
2935 790968 : if (lhs.undefined_p ())
2936 : return false;
2937 790968 : wide_int shift;
2938 790968 : if (op2.singleton_p (shift))
2939 : {
2940 : // Ignore nonsensical shifts.
2941 768169 : unsigned prec = TYPE_PRECISION (type);
2942 1536338 : if (wi::ge_p (shift,
2943 768169 : wi::uhwi (prec, TYPE_PRECISION (op2.type ())),
2944 : UNSIGNED))
2945 : return false;
2946 768169 : if (shift == 0)
2947 : {
2948 75 : r = lhs;
2949 75 : return true;
2950 : }
2951 :
2952 : // Folding the original operation may discard some impossible
2953 : // ranges from the LHS.
2954 768094 : int_range_max lhs_refined;
2955 768094 : op_rshift.fold_range (lhs_refined, type, int_range<1> (type), op2);
2956 768094 : lhs_refined.intersect (lhs);
2957 768094 : if (lhs_refined.undefined_p ())
2958 : {
2959 4 : r.set_undefined ();
2960 4 : return true;
2961 : }
2962 768090 : int_range_max shift_range (op2.type (), shift, shift);
2963 768090 : int_range_max lb, ub;
2964 768090 : op_lshift.fold_range (lb, type, lhs_refined, shift_range);
2965 : // LHS
2966 : // 0000 0111 = OP1 >> 3
2967 : //
2968 : // OP1 is anything from 0011 1000 to 0011 1111. That is, a
2969 : // range from LHS<<3 plus a mask of the 3 bits we shifted on the
2970 : // right hand side (0x07).
2971 768090 : wide_int mask = wi::mask (shift.to_uhwi (), false, prec);
2972 768090 : int_range_max mask_range (type,
2973 768090 : wi::zero (TYPE_PRECISION (type)),
2974 768090 : mask);
2975 768090 : op_plus.fold_range (ub, type, lb, mask_range);
2976 768090 : r = lb;
2977 768090 : r.union_ (ub);
2978 768090 : if (!contains_zero_p (lhs_refined))
2979 : {
2980 444405 : mask_range.invert ();
2981 444405 : r.intersect (mask_range);
2982 : }
2983 768090 : return true;
2984 768094 : }
2985 : return false;
2986 790968 : }
2987 :
2988 : bool
2989 10657282 : operator_rshift::wi_op_overflows (wide_int &res,
2990 : tree type,
2991 : const wide_int &w0,
2992 : const wide_int &w1) const
2993 : {
2994 10657282 : signop sign = TYPE_SIGN (type);
2995 10657282 : if (wi::neg_p (w1))
2996 0 : res = wi::lshift (w0, -w1);
2997 : else
2998 : {
2999 : // It's unclear from the C standard whether shifts can overflow.
3000 : // The following code ignores overflow; perhaps a C standard
3001 : // interpretation ruling is needed.
3002 10657373 : res = wi::rshift (w0, w1, sign);
3003 : }
3004 10657282 : return false;
3005 : }
3006 :
3007 : bool
3008 3203575 : operator_rshift::fold_range (irange &r, tree type,
3009 : const irange &op1,
3010 : const irange &op2,
3011 : relation_trio rel) const
3012 : {
3013 3203575 : int_range_max shift;
3014 3203575 : if (!get_shift_range (shift, type, op2))
3015 : {
3016 667 : if (op2.undefined_p ())
3017 254 : r.set_undefined ();
3018 : else
3019 413 : r.set_zero (type);
3020 667 : return true;
3021 : }
3022 :
3023 3202908 : return range_operator::fold_range (r, type, op1, shift, rel);
3024 3203575 : }
3025 :
3026 : void
3027 3768766 : operator_rshift::wi_fold (irange &r, tree type,
3028 : const wide_int &lh_lb, const wide_int &lh_ub,
3029 : const wide_int &rh_lb, const wide_int &rh_ub) const
3030 : {
3031 3768766 : wi_cross_product (r, type, lh_lb, lh_ub, rh_lb, rh_ub);
3032 3768766 : }
3033 :
3034 :
3035 : // Add a partial equivalence between the LHS and op1 for casts.
3036 :
3037 : relation_kind
3038 23186244 : operator_cast::lhs_op1_relation (const irange &lhs,
3039 : const irange &op1,
3040 : const irange &op2 ATTRIBUTE_UNUSED,
3041 : relation_kind) const
3042 : {
3043 23186244 : if (lhs.undefined_p () || op1.undefined_p ())
3044 : return VREL_VARYING;
3045 23165138 : unsigned lhs_prec = TYPE_PRECISION (lhs.type ());
3046 23165138 : unsigned op1_prec = TYPE_PRECISION (op1.type ());
3047 : // If the result gets sign extended into a larger type check first if this
3048 : // qualifies as a partial equivalence.
3049 23165138 : if (TYPE_SIGN (op1.type ()) == SIGNED && lhs_prec > op1_prec)
3050 : {
3051 : // If the result is sign extended, and the LHS is larger than op1,
3052 : // check if op1's range can be negative as the sign extension will
3053 : // cause the upper bits to be 1 instead of 0, invalidating the PE.
3054 3746600 : int_range<3> negs = range_negatives (op1.type ());
3055 3746600 : negs.intersect (op1);
3056 3746600 : if (!negs.undefined_p ())
3057 2653684 : return VREL_VARYING;
3058 3746600 : }
3059 :
3060 20511454 : unsigned prec = MIN (lhs_prec, op1_prec);
3061 20511454 : return bits_to_pe (prec);
3062 : }
3063 :
3064 : // Return TRUE if casting from INNER to OUTER is a truncating cast.
3065 :
3066 : inline bool
3067 82175618 : operator_cast::truncating_cast_p (const irange &inner,
3068 : const irange &outer) const
3069 : {
3070 82175618 : return TYPE_PRECISION (outer.type ()) < TYPE_PRECISION (inner.type ());
3071 : }
3072 :
3073 : // Return TRUE if [MIN,MAX] is inside the domain of RANGE's type.
3074 :
3075 : bool
3076 70997569 : operator_cast::inside_domain_p (const wide_int &min,
3077 : const wide_int &max,
3078 : const irange &range) const
3079 : {
3080 70997569 : wide_int domain_min = irange_val_min (range.type ());
3081 70997569 : wide_int domain_max = irange_val_max (range.type ());
3082 70997569 : signop domain_sign = TYPE_SIGN (range.type ());
3083 70997569 : return (wi::le_p (min, domain_max, domain_sign)
3084 70997569 : && wi::le_p (max, domain_max, domain_sign)
3085 70997569 : && wi::ge_p (min, domain_min, domain_sign)
3086 141995138 : && wi::ge_p (max, domain_min, domain_sign));
3087 70997569 : }
3088 :
3089 :
3090 : // Helper for fold_range which work on a pair at a time.
3091 :
3092 : void
3093 74143955 : operator_cast::fold_pair (irange &r, unsigned index,
3094 : const irange &inner,
3095 : const irange &outer) const
3096 : {
3097 74143955 : tree inner_type = inner.type ();
3098 74143955 : tree outer_type = outer.type ();
3099 74143955 : signop inner_sign = TYPE_SIGN (inner_type);
3100 74143955 : unsigned outer_prec = TYPE_PRECISION (outer_type);
3101 :
3102 : // check to see if casting from INNER to OUTER is a conversion that
3103 : // fits in the resulting OUTER type.
3104 74143955 : wide_int inner_lb = inner.lower_bound (index);
3105 74143955 : wide_int inner_ub = inner.upper_bound (index);
3106 74143955 : if (truncating_cast_p (inner, outer))
3107 : {
3108 : // We may be able to accommodate a truncating cast if the
3109 : // resulting range can be represented in the target type...
3110 14115632 : if (wi::rshift (wi::sub (inner_ub, inner_lb),
3111 7057816 : wi::uhwi (outer_prec, TYPE_PRECISION (inner.type ())),
3112 21173448 : inner_sign) != 0)
3113 : {
3114 3146386 : r.set_varying (outer_type);
3115 3146386 : return;
3116 : }
3117 : }
3118 : // ...but we must still verify that the final range fits in the
3119 : // domain. This catches -fstrict-enum restrictions where the domain
3120 : // range is smaller than what fits in the underlying type.
3121 70997569 : wide_int min = wide_int::from (inner_lb, outer_prec, inner_sign);
3122 70997569 : wide_int max = wide_int::from (inner_ub, outer_prec, inner_sign);
3123 70997569 : if (inside_domain_p (min, max, outer))
3124 70997569 : create_possibly_reversed_range (r, outer_type, min, max);
3125 : else
3126 0 : r.set_varying (outer_type);
3127 74146889 : }
3128 :
3129 :
3130 : bool
3131 59872639 : operator_cast::fold_range (irange &r, tree type ATTRIBUTE_UNUSED,
3132 : const irange &inner,
3133 : const irange &outer,
3134 : relation_trio) const
3135 : {
3136 59872639 : if (empty_range_varying (r, type, inner, outer))
3137 33082 : return true;
3138 :
3139 59839557 : gcc_checking_assert (outer.varying_p ());
3140 59839557 : gcc_checking_assert (inner.num_pairs () > 0);
3141 :
3142 : // Avoid a temporary by folding the first pair directly into the result.
3143 59839557 : fold_pair (r, 0, inner, outer);
3144 :
3145 : // Then process any additional pairs by unioning with their results.
3146 73508324 : for (unsigned x = 1; x < inner.num_pairs (); ++x)
3147 : {
3148 14304398 : int_range_max tmp;
3149 14304398 : fold_pair (tmp, x, inner, outer);
3150 14304398 : r.union_ (tmp);
3151 : // If we hit varying, go update the bitmask.
3152 14304398 : if (r.varying_p ())
3153 : break;
3154 14304398 : }
3155 :
3156 59839557 : update_bitmask (r, inner, outer);
3157 59839557 : return true;
3158 : }
3159 :
3160 : void
3161 59839557 : operator_cast::update_bitmask (irange &r, const irange &lh,
3162 : const irange &rh) const
3163 : {
3164 59839557 : update_known_bitmask (r, CONVERT_EXPR, lh, rh);
3165 59839557 : }
3166 :
3167 : bool
3168 8031663 : operator_cast::op1_range (irange &r, tree type,
3169 : const irange &lhs,
3170 : const irange &op2,
3171 : relation_trio) const
3172 : {
3173 8031663 : if (lhs.undefined_p ())
3174 : return false;
3175 8031663 : tree lhs_type = lhs.type ();
3176 8031663 : gcc_checking_assert (types_compatible_p (op2.type(), type));
3177 :
3178 : // If we are calculating a pointer, shortcut to what we really care about.
3179 8031663 : if (POINTER_TYPE_P (type))
3180 : {
3181 : // Conversion from other pointers or a constant (including 0/NULL)
3182 : // are straightforward.
3183 0 : if (POINTER_TYPE_P (lhs.type ())
3184 0 : || (lhs.singleton_p ()
3185 0 : && TYPE_PRECISION (lhs.type ()) >= TYPE_PRECISION (type)))
3186 : {
3187 0 : r = lhs;
3188 0 : range_cast (r, type);
3189 : }
3190 : else
3191 : {
3192 : // If the LHS is not a pointer nor a singleton, then it is
3193 : // either VARYING or non-zero.
3194 0 : if (!lhs.undefined_p () && !contains_zero_p (lhs))
3195 0 : r.set_nonzero (type);
3196 : else
3197 0 : r.set_varying (type);
3198 : }
3199 0 : r.intersect (op2);
3200 0 : return true;
3201 : }
3202 :
3203 8031663 : if (truncating_cast_p (op2, lhs))
3204 : {
3205 1277405 : if (lhs.varying_p ())
3206 145980 : r.set_varying (type);
3207 : else
3208 : {
3209 : // We want to insert the LHS as an unsigned value since it
3210 : // would not trigger the signed bit of the larger type.
3211 1131425 : int_range_max converted_lhs = lhs;
3212 1131425 : range_cast (converted_lhs, unsigned_type_for (lhs_type));
3213 1131425 : range_cast (converted_lhs, type);
3214 : // Start by building the positive signed outer range for the type.
3215 1131425 : wide_int lim = wi::set_bit_in_zero (TYPE_PRECISION (lhs_type),
3216 2262850 : TYPE_PRECISION (type));
3217 1131425 : create_possibly_reversed_range (r, type, lim,
3218 1131425 : wi::max_value (TYPE_PRECISION (type),
3219 : SIGNED));
3220 : // For the signed part, we need to simply union the 2 ranges now.
3221 1131425 : r.union_ (converted_lhs);
3222 :
3223 : // Create maximal negative number outside of LHS bits.
3224 1131425 : lim = wi::mask (TYPE_PRECISION (lhs_type), true,
3225 2262850 : TYPE_PRECISION (type));
3226 : // Add this to the unsigned LHS range(s).
3227 1131425 : int_range_max lim_range (type, lim, lim);
3228 1131425 : int_range_max lhs_neg;
3229 1131425 : range_op_handler (PLUS_EXPR).fold_range (lhs_neg, type,
3230 : converted_lhs, lim_range);
3231 : // lhs_neg now has all the negative versions of the LHS.
3232 : // Now union in all the values from SIGNED MIN (0x80000) to
3233 : // lim-1 in order to fill in all the ranges with the upper
3234 : // bits set.
3235 :
3236 : // PR 97317. If the lhs has only 1 bit less precision than the rhs,
3237 : // we don't need to create a range from min to lim-1
3238 : // calculate neg range traps trying to create [lim, lim - 1].
3239 1131425 : wide_int min_val = wi::min_value (TYPE_PRECISION (type), SIGNED);
3240 1131425 : if (lim != min_val)
3241 : {
3242 1129733 : int_range_max neg (type,
3243 2259466 : wi::min_value (TYPE_PRECISION (type),
3244 : SIGNED),
3245 2259466 : lim - 1);
3246 1129733 : lhs_neg.union_ (neg);
3247 1129733 : }
3248 : // And finally, munge the signed and unsigned portions.
3249 1131425 : r.union_ (lhs_neg);
3250 1131425 : }
3251 : // And intersect with any known value passed in the extra operand.
3252 1277405 : r.intersect (op2);
3253 1277405 : if (r.undefined_p ())
3254 : return true;
3255 :
3256 : // Now create a bitmask indicating that the lower bit must match the
3257 : // bits in the LHS. Zero-extend LHS bitmask to precision of op1.
3258 1277346 : irange_bitmask bm = lhs.get_bitmask ();
3259 2554692 : wide_int mask = wide_int::from (bm.mask (), TYPE_PRECISION (type),
3260 2554692 : UNSIGNED);
3261 2554692 : wide_int value = wide_int::from (bm.value (), TYPE_PRECISION (type),
3262 2554692 : UNSIGNED);
3263 :
3264 : // Set then additional unknown bits in mask.
3265 1277346 : wide_int lim = wi::mask (TYPE_PRECISION (lhs_type), true,
3266 2554692 : TYPE_PRECISION (type));
3267 1277346 : mask = mask | lim;
3268 :
3269 : // Now set the new bitmask for the range.
3270 1277346 : irange_bitmask new_bm (value, mask);
3271 1277346 : r.update_bitmask (new_bm);
3272 1277346 : return true;
3273 1277346 : }
3274 :
3275 6754258 : int_range_max tmp;
3276 6754258 : if (TYPE_PRECISION (lhs_type) == TYPE_PRECISION (type))
3277 5064536 : tmp = lhs;
3278 : else
3279 : {
3280 : // The cast is not truncating, and the range is restricted to
3281 : // the range of the RHS by this assignment.
3282 : //
3283 : // Cast the range of the RHS to the type of the LHS.
3284 1689722 : fold_range (tmp, lhs_type, int_range<1> (type), int_range<1> (lhs_type));
3285 : // Intersect this with the LHS range will produce the range,
3286 : // which will be cast to the RHS type before returning.
3287 1689722 : tmp.intersect (lhs);
3288 : }
3289 :
3290 : // Cast the calculated range to the type of the RHS.
3291 6754258 : fold_range (r, type, tmp, int_range<1> (type));
3292 6754258 : return true;
3293 6754258 : }
3294 :
3295 : // VIEW_CONVERT_EXPR works like a cast between integral values.
3296 : // If the number of bits are not the same, behaviour is undefined,
3297 : // so cast behaviour still works.
3298 :
3299 : bool
3300 269639 : operator_view::fold_range (irange &r, tree type,
3301 : const irange &op1, const irange &op2,
3302 : relation_trio rel) const
3303 : {
3304 269639 : return m_cast.fold_range (r, type, op1, op2, rel);
3305 : }
3306 :
3307 : bool
3308 0 : operator_view::fold_range (prange &r, tree type,
3309 : const prange &op1, const prange &op2,
3310 : relation_trio rel) const
3311 : {
3312 0 : return m_cast.fold_range (r, type, op1, op2, rel);
3313 : }
3314 : bool
3315 255774 : operator_view::fold_range (irange &r, tree type,
3316 : const prange &op1, const irange &op2,
3317 : relation_trio rel) const
3318 : {
3319 255774 : return m_cast.fold_range (r, type, op1, op2, rel);
3320 : }
3321 :
3322 : bool
3323 0 : operator_view::fold_range (prange &r, tree type,
3324 : const irange &op1, const prange &op2,
3325 : relation_trio rel) const
3326 : {
3327 0 : return m_cast.fold_range (r, type, op1, op2, rel);
3328 : }
3329 :
3330 : bool
3331 8861 : operator_view::op1_range (irange &r, tree type,
3332 : const irange &lhs, const irange &op2,
3333 : relation_trio rel) const
3334 : {
3335 8861 : return m_cast.op1_range (r, type, lhs, op2, rel);
3336 : }
3337 :
3338 : bool
3339 0 : operator_view::op1_range (prange &r, tree type,
3340 : const prange &lhs, const prange &op2,
3341 : relation_trio rel) const
3342 : {
3343 0 : return m_cast.op1_range (r, type, lhs, op2, rel);
3344 : }
3345 :
3346 : bool
3347 0 : operator_view::op1_range (irange &r, tree type,
3348 : const prange &lhs, const irange &op2,
3349 : relation_trio rel) const
3350 : {
3351 0 : return m_cast.op1_range (r, type, lhs, op2, rel);
3352 : }
3353 :
3354 : bool
3355 0 : operator_view::op1_range (prange &r, tree type,
3356 : const irange &lhs, const prange &op2,
3357 : relation_trio rel) const
3358 : {
3359 0 : return m_cast.op1_range (r, type, lhs, op2, rel);
3360 : }
3361 :
3362 : void
3363 0 : operator_view::update_bitmask (irange &r, const irange &lh,
3364 : const irange &rh) const
3365 : {
3366 0 : m_cast.update_bitmask (r, lh, rh);
3367 0 : }
3368 :
3369 :
3370 : class operator_logical_and : public range_operator
3371 : {
3372 : using range_operator::fold_range;
3373 : using range_operator::op1_range;
3374 : using range_operator::op2_range;
3375 : public:
3376 : bool fold_range (irange &r, tree type,
3377 : const irange &lh,
3378 : const irange &rh,
3379 : relation_trio rel = TRIO_VARYING) const final override;
3380 : bool op1_range (irange &r, tree type,
3381 : const irange &lhs,
3382 : const irange &op2,
3383 : relation_trio rel = TRIO_VARYING) const final override;
3384 : bool op2_range (irange &r, tree type,
3385 : const irange &lhs,
3386 : const irange &op1,
3387 : relation_trio rel = TRIO_VARYING) const final override;
3388 : // Check compatibility of all operands.
3389 0 : bool operand_check_p (tree t1, tree t2, tree t3) const final override
3390 0 : { return range_compatible_p (t1, t2) && range_compatible_p (t1, t3); }
3391 : } op_logical_and;
3392 :
3393 : bool
3394 0 : operator_logical_and::fold_range (irange &r, tree type,
3395 : const irange &lh,
3396 : const irange &rh,
3397 : relation_trio) const
3398 : {
3399 0 : if (empty_range_varying (r, type, lh, rh))
3400 0 : return true;
3401 :
3402 : // Precision of LHS and both operands must match.
3403 0 : if (TYPE_PRECISION (lh.type ()) != TYPE_PRECISION (type)
3404 0 : || TYPE_PRECISION (type) != TYPE_PRECISION (rh.type ()))
3405 0 : return false;
3406 :
3407 : // 0 && anything is 0.
3408 0 : if ((wi::eq_p (lh.lower_bound (), 0) && wi::eq_p (lh.upper_bound (), 0))
3409 0 : || (wi::eq_p (lh.lower_bound (), 0) && wi::eq_p (rh.upper_bound (), 0)))
3410 0 : r = range_false (type);
3411 0 : else if (contains_zero_p (lh) || contains_zero_p (rh))
3412 : // To reach this point, there must be a logical 1 on each side, and
3413 : // the only remaining question is whether there is a zero or not.
3414 0 : r = range_true_and_false (type);
3415 : else
3416 0 : r = range_true (type);
3417 : return true;
3418 : }
3419 :
3420 : bool
3421 782581 : operator_logical_and::op1_range (irange &r, tree type,
3422 : const irange &lhs,
3423 : const irange &op2 ATTRIBUTE_UNUSED,
3424 : relation_trio) const
3425 : {
3426 782581 : switch (get_bool_state (r, lhs, type))
3427 : {
3428 401652 : case BRS_TRUE:
3429 : // A true result means both sides of the AND must be true.
3430 401652 : r = range_true (type);
3431 401652 : break;
3432 380929 : default:
3433 : // Any other result means only one side has to be false, the
3434 : // other side can be anything. So we cannot be sure of any
3435 : // result here.
3436 380929 : r = range_true_and_false (type);
3437 380929 : break;
3438 : }
3439 782581 : return true;
3440 : }
3441 :
3442 : bool
3443 0 : operator_logical_and::op2_range (irange &r, tree type,
3444 : const irange &lhs,
3445 : const irange &op1,
3446 : relation_trio) const
3447 : {
3448 0 : return operator_logical_and::op1_range (r, type, lhs, op1);
3449 : }
3450 :
3451 :
3452 : void
3453 7131617 : operator_bitwise_and::update_bitmask (irange &r, const irange &lh,
3454 : const irange &rh) const
3455 : {
3456 7131617 : update_known_bitmask (r, BIT_AND_EXPR, lh, rh);
3457 7131617 : }
3458 :
3459 : // Optimize BIT_AND_EXPR, BIT_IOR_EXPR and BIT_XOR_EXPR of signed types
3460 : // by considering the number of leading redundant sign bit copies.
3461 : // clrsb (X op Y) = min (clrsb (X), clrsb (Y)), so for example
3462 : // [-1, 0] op [-1, 0] is [-1, 0] (where nonzero_bits doesn't help).
3463 : static bool
3464 182407 : wi_optimize_signed_bitwise_op (irange &r, tree type,
3465 : const wide_int &lh_lb, const wide_int &lh_ub,
3466 : const wide_int &rh_lb, const wide_int &rh_ub)
3467 : {
3468 364814 : int lh_clrsb = MIN (wi::clrsb (lh_lb), wi::clrsb (lh_ub));
3469 364814 : int rh_clrsb = MIN (wi::clrsb (rh_lb), wi::clrsb (rh_ub));
3470 182407 : int new_clrsb = MIN (lh_clrsb, rh_clrsb);
3471 182407 : if (new_clrsb == 0)
3472 : return false;
3473 12039 : int type_prec = TYPE_PRECISION (type);
3474 12039 : int rprec = (type_prec - new_clrsb) - 1;
3475 12039 : value_range_with_overflow (r, type,
3476 24078 : wi::mask (rprec, true, type_prec),
3477 12039 : wi::mask (rprec, false, type_prec));
3478 12039 : return true;
3479 : }
3480 :
3481 : // An AND of 8,16, 32 or 64 bits can produce a partial equivalence between
3482 : // the LHS and op1.
3483 :
3484 : relation_kind
3485 6461943 : operator_bitwise_and::lhs_op1_relation (const irange &lhs,
3486 : const irange &op1,
3487 : const irange &op2,
3488 : relation_kind) const
3489 : {
3490 6461943 : if (lhs.undefined_p () || op1.undefined_p () || op2.undefined_p ())
3491 : return VREL_VARYING;
3492 6457475 : if (!op2.singleton_p ())
3493 : return VREL_VARYING;
3494 : // if val == 0xff or 0xFFFF OR 0Xffffffff OR 0Xffffffffffffffff, return TRUE
3495 3680613 : int prec1 = TYPE_PRECISION (op1.type ());
3496 3680613 : int prec2 = TYPE_PRECISION (op2.type ());
3497 3680613 : int mask_prec = 0;
3498 3680613 : wide_int mask = op2.lower_bound ();
3499 3680613 : if (wi::eq_p (mask, wi::mask (8, false, prec2)))
3500 : mask_prec = 8;
3501 3599635 : else if (wi::eq_p (mask, wi::mask (16, false, prec2)))
3502 : mask_prec = 16;
3503 3583755 : else if (wi::eq_p (mask, wi::mask (32, false, prec2)))
3504 : mask_prec = 32;
3505 3399343 : else if (wi::eq_p (mask, wi::mask (64, false, prec2)))
3506 820 : mask_prec = 64;
3507 3680613 : return bits_to_pe (MIN (prec1, mask_prec));
3508 3680613 : }
3509 :
3510 : // Optimize BIT_AND_EXPR and BIT_IOR_EXPR in terms of a mask if
3511 : // possible. Basically, see if we can optimize:
3512 : //
3513 : // [LB, UB] op Z
3514 : // into:
3515 : // [LB op Z, UB op Z]
3516 : //
3517 : // If the optimization was successful, accumulate the range in R and
3518 : // return TRUE.
3519 :
3520 : static bool
3521 21969239 : wi_optimize_and_or (irange &r,
3522 : enum tree_code code,
3523 : tree type,
3524 : const wide_int &lh_lb, const wide_int &lh_ub,
3525 : const wide_int &rh_lb, const wide_int &rh_ub)
3526 : {
3527 : // Calculate the singleton mask among the ranges, if any.
3528 21969239 : wide_int lower_bound, upper_bound, mask;
3529 21969239 : if (wi::eq_p (rh_lb, rh_ub))
3530 : {
3531 20318749 : mask = rh_lb;
3532 20318749 : lower_bound = lh_lb;
3533 20318749 : upper_bound = lh_ub;
3534 : }
3535 1650490 : else if (wi::eq_p (lh_lb, lh_ub))
3536 : {
3537 345251 : mask = lh_lb;
3538 345251 : lower_bound = rh_lb;
3539 345251 : upper_bound = rh_ub;
3540 : }
3541 : else
3542 : return false;
3543 :
3544 : // If Z is a constant which (for op | its bitwise not) has n
3545 : // consecutive least significant bits cleared followed by m 1
3546 : // consecutive bits set immediately above it and either
3547 : // m + n == precision, or (x >> (m + n)) == (y >> (m + n)).
3548 : //
3549 : // The least significant n bits of all the values in the range are
3550 : // cleared or set, the m bits above it are preserved and any bits
3551 : // above these are required to be the same for all values in the
3552 : // range.
3553 20664000 : wide_int w = mask;
3554 20664000 : int m = 0, n = 0;
3555 20664000 : if (code == BIT_IOR_EXPR)
3556 6245147 : w = ~w;
3557 20664000 : if (wi::eq_p (w, 0))
3558 6973705 : n = w.get_precision ();
3559 : else
3560 : {
3561 13690295 : n = wi::ctz (w);
3562 13690301 : w = ~(w | wi::mask (n, false, w.get_precision ()));
3563 13690295 : if (wi::eq_p (w, 0))
3564 8168052 : m = w.get_precision () - n;
3565 : else
3566 5522243 : m = wi::ctz (w) - n;
3567 : }
3568 20664000 : wide_int new_mask = wi::mask (m + n, true, w.get_precision ());
3569 20664006 : if ((new_mask & lower_bound) != (new_mask & upper_bound))
3570 : return false;
3571 :
3572 15962451 : wide_int res_lb, res_ub;
3573 15962451 : if (code == BIT_AND_EXPR)
3574 : {
3575 9954156 : res_lb = wi::bit_and (lower_bound, mask);
3576 9954156 : res_ub = wi::bit_and (upper_bound, mask);
3577 : }
3578 6008295 : else if (code == BIT_IOR_EXPR)
3579 : {
3580 6008295 : res_lb = wi::bit_or (lower_bound, mask);
3581 6008295 : res_ub = wi::bit_or (upper_bound, mask);
3582 : }
3583 : else
3584 0 : gcc_unreachable ();
3585 15962451 : value_range_with_overflow (r, type, res_lb, res_ub);
3586 :
3587 : // Furthermore, if the mask is non-zero, an IOR cannot contain zero.
3588 15962451 : if (code == BIT_IOR_EXPR && wi::ne_p (mask, 0))
3589 : {
3590 3054784 : int_range<2> tmp;
3591 3054784 : tmp.set_nonzero (type);
3592 3054784 : r.intersect (tmp);
3593 3054784 : }
3594 15962451 : return true;
3595 58595696 : }
3596 :
3597 : // For range [LB, UB] compute two wide_int bit masks.
3598 : //
3599 : // In the MAYBE_NONZERO bit mask, if some bit is unset, it means that
3600 : // for all numbers in the range the bit is 0, otherwise it might be 0
3601 : // or 1.
3602 : //
3603 : // In the MUSTBE_NONZERO bit mask, if some bit is set, it means that
3604 : // for all numbers in the range the bit is 1, otherwise it might be 0
3605 : // or 1.
3606 :
3607 : void
3608 13026255 : wi_set_zero_nonzero_bits (tree type,
3609 : const wide_int &lb, const wide_int &ub,
3610 : wide_int &maybe_nonzero,
3611 : wide_int &mustbe_nonzero)
3612 : {
3613 13026255 : signop sign = TYPE_SIGN (type);
3614 :
3615 13026255 : if (wi::eq_p (lb, ub))
3616 5170599 : maybe_nonzero = mustbe_nonzero = lb;
3617 7855656 : else if (wi::ge_p (lb, 0, sign) || wi::lt_p (ub, 0, sign))
3618 : {
3619 7428611 : wide_int xor_mask = lb ^ ub;
3620 7428611 : maybe_nonzero = lb | ub;
3621 7428611 : mustbe_nonzero = lb & ub;
3622 7428611 : if (xor_mask != 0)
3623 : {
3624 7428611 : wide_int mask = wi::mask (wi::floor_log2 (xor_mask), false,
3625 14857222 : maybe_nonzero.get_precision ());
3626 7428611 : maybe_nonzero = maybe_nonzero | mask;
3627 7428616 : mustbe_nonzero = wi::bit_and_not (mustbe_nonzero, mask);
3628 7428611 : }
3629 7428611 : }
3630 : else
3631 : {
3632 427045 : maybe_nonzero = wi::minus_one (lb.get_precision ());
3633 427045 : mustbe_nonzero = wi::zero (lb.get_precision ());
3634 : }
3635 13026255 : }
3636 :
3637 : void
3638 15700854 : operator_bitwise_and::wi_fold (irange &r, tree type,
3639 : const wide_int &lh_lb,
3640 : const wide_int &lh_ub,
3641 : const wide_int &rh_lb,
3642 : const wide_int &rh_ub) const
3643 : {
3644 : // The AND algorithm does not handle complex signed operations well.
3645 : // If a signed range crosses the boundary between signed and unsigned
3646 : // process it as 2 ranges and union the results.
3647 15700854 : if (TYPE_SIGN (type) == SIGNED
3648 15700854 : && wi::neg_p (lh_lb, SIGNED) != wi::neg_p (lh_ub, SIGNED))
3649 : {
3650 610555 : int prec = TYPE_PRECISION (type);
3651 610555 : int_range_max tmp;
3652 : // Process [lh_lb, -1]
3653 610555 : wi_fold (tmp, type, lh_lb, wi::minus_one (prec), rh_lb, rh_ub);
3654 : // Now Process [0, rh_ub]
3655 610555 : wi_fold (r, type, wi::zero (prec), lh_ub, rh_lb, rh_ub);
3656 610555 : r.union_ (tmp);
3657 610555 : return;
3658 610555 : }
3659 :
3660 15090299 : if (wi_optimize_and_or (r, BIT_AND_EXPR, type, lh_lb, lh_ub, rh_lb, rh_ub))
3661 : return;
3662 :
3663 5136143 : wide_int maybe_nonzero_lh, mustbe_nonzero_lh;
3664 5136143 : wide_int maybe_nonzero_rh, mustbe_nonzero_rh;
3665 5136143 : wi_set_zero_nonzero_bits (type, lh_lb, lh_ub,
3666 : maybe_nonzero_lh, mustbe_nonzero_lh);
3667 5136143 : wi_set_zero_nonzero_bits (type, rh_lb, rh_ub,
3668 : maybe_nonzero_rh, mustbe_nonzero_rh);
3669 :
3670 5136143 : wide_int new_lb = mustbe_nonzero_lh & mustbe_nonzero_rh;
3671 5136143 : wide_int new_ub = maybe_nonzero_lh & maybe_nonzero_rh;
3672 5136143 : signop sign = TYPE_SIGN (type);
3673 5136143 : unsigned prec = TYPE_PRECISION (type);
3674 : // If both input ranges contain only negative values, we can
3675 : // truncate the result range maximum to the minimum of the
3676 : // input range maxima.
3677 5136143 : if (wi::lt_p (lh_ub, 0, sign) && wi::lt_p (rh_ub, 0, sign))
3678 : {
3679 47042 : new_ub = wi::min (new_ub, lh_ub, sign);
3680 47042 : new_ub = wi::min (new_ub, rh_ub, sign);
3681 : }
3682 : // If either input range contains only non-negative values
3683 : // we can truncate the result range maximum to the respective
3684 : // maximum of the input range.
3685 5136143 : if (wi::ge_p (lh_lb, 0, sign))
3686 4394330 : new_ub = wi::min (new_ub, lh_ub, sign);
3687 5136143 : if (wi::ge_p (rh_lb, 0, sign))
3688 4917234 : new_ub = wi::min (new_ub, rh_ub, sign);
3689 : // PR68217: In case of signed & sign-bit-CST should
3690 : // result in [-INF, 0] instead of [-INF, INF].
3691 5136143 : if (wi::gt_p (new_lb, new_ub, sign))
3692 : {
3693 54602 : wide_int sign_bit = wi::set_bit_in_zero (prec - 1, prec);
3694 54602 : if (sign == SIGNED
3695 54602 : && ((wi::eq_p (lh_lb, lh_ub)
3696 66 : && !wi::cmps (lh_lb, sign_bit))
3697 54602 : || (wi::eq_p (rh_lb, rh_ub)
3698 0 : && !wi::cmps (rh_lb, sign_bit))))
3699 : {
3700 0 : new_lb = wi::min_value (prec, sign);
3701 0 : new_ub = wi::zero (prec);
3702 : }
3703 54602 : }
3704 : // If the limits got swapped around, return varying.
3705 5136143 : if (wi::gt_p (new_lb, new_ub,sign))
3706 : {
3707 54602 : if (sign == SIGNED
3708 54602 : && wi_optimize_signed_bitwise_op (r, type,
3709 : lh_lb, lh_ub,
3710 : rh_lb, rh_ub))
3711 3842 : return;
3712 50760 : r.set_varying (type);
3713 : }
3714 : else
3715 5081541 : value_range_with_overflow (r, type, new_lb, new_ub);
3716 5136143 : }
3717 :
3718 : static void
3719 540894 : set_nonzero_range_from_mask (irange &r, tree type, const irange &lhs)
3720 : {
3721 540894 : if (lhs.undefined_p () || contains_zero_p (lhs))
3722 290394 : r.set_varying (type);
3723 : else
3724 250500 : r.set_nonzero (type);
3725 540894 : }
3726 :
3727 : /* Find out smallest RES where RES > VAL && (RES & MASK) == RES, if any
3728 : (otherwise return VAL). VAL and MASK must be zero-extended for
3729 : precision PREC. If SGNBIT is non-zero, first xor VAL with SGNBIT
3730 : (to transform signed values into unsigned) and at the end xor
3731 : SGNBIT back. */
3732 :
3733 : wide_int
3734 35040 : masked_increment (const wide_int &val_in, const wide_int &mask,
3735 : const wide_int &sgnbit, unsigned int prec)
3736 : {
3737 35040 : wide_int bit = wi::one (prec), res;
3738 35040 : unsigned int i;
3739 :
3740 35040 : wide_int val = val_in ^ sgnbit;
3741 636792 : for (i = 0; i < prec; i++, bit += bit)
3742 : {
3743 591404 : res = mask;
3744 591404 : if ((res & bit) == 0)
3745 508122 : continue;
3746 83282 : res = bit - 1;
3747 83282 : res = wi::bit_and_not (val + bit, res);
3748 83282 : res &= mask;
3749 83282 : if (wi::gtu_p (res, val))
3750 24692 : return res ^ sgnbit;
3751 : }
3752 10348 : return val ^ sgnbit;
3753 35040 : }
3754 :
3755 : // This was shamelessly stolen from register_edge_assert_for_2 and
3756 : // adjusted to work with iranges.
3757 :
3758 : void
3759 3214580 : operator_bitwise_and::simple_op1_range_solver (irange &r, tree type,
3760 : const irange &lhs,
3761 : const irange &op2) const
3762 : {
3763 3214580 : if (!op2.singleton_p ())
3764 : {
3765 539971 : set_nonzero_range_from_mask (r, type, lhs);
3766 1086418 : return;
3767 : }
3768 2674609 : unsigned int nprec = TYPE_PRECISION (type);
3769 2674609 : wide_int cst2v = op2.lower_bound ();
3770 2674609 : bool cst2n = wi::neg_p (cst2v, TYPE_SIGN (type));
3771 2674609 : wide_int sgnbit;
3772 2674609 : if (cst2n)
3773 552799 : sgnbit = wi::set_bit_in_zero (nprec - 1, nprec);
3774 : else
3775 2121810 : sgnbit = wi::zero (nprec);
3776 :
3777 : // Solve [lhs.lower_bound (), +INF] = x & MASK.
3778 : //
3779 : // Minimum unsigned value for >= if (VAL & CST2) == VAL is VAL and
3780 : // maximum unsigned value is ~0. For signed comparison, if CST2
3781 : // doesn't have the most significant bit set, handle it similarly. If
3782 : // CST2 has MSB set, the minimum is the same, and maximum is ~0U/2.
3783 2674609 : wide_int valv = lhs.lower_bound ();
3784 2674609 : wide_int minv = valv & cst2v, maxv;
3785 2674609 : bool we_know_nothing = false;
3786 2674609 : if (minv != valv)
3787 : {
3788 : // If (VAL & CST2) != VAL, X & CST2 can't be equal to VAL.
3789 7509 : minv = masked_increment (valv, cst2v, sgnbit, nprec);
3790 7509 : if (minv == valv)
3791 : {
3792 : // If we can't determine anything on this bound, fall
3793 : // through and conservatively solve for the other end point.
3794 2674609 : we_know_nothing = true;
3795 : }
3796 : }
3797 4796419 : maxv = wi::mask (nprec - (cst2n ? 1 : 0), false, nprec);
3798 2674609 : if (we_know_nothing)
3799 3872 : r.set_varying (type);
3800 : else
3801 2670737 : create_possibly_reversed_range (r, type, minv, maxv);
3802 :
3803 : // Solve [-INF, lhs.upper_bound ()] = x & MASK.
3804 : //
3805 : // Minimum unsigned value for <= is 0 and maximum unsigned value is
3806 : // VAL | ~CST2 if (VAL & CST2) == VAL. Otherwise, find smallest
3807 : // VAL2 where
3808 : // VAL2 > VAL && (VAL2 & CST2) == VAL2 and use (VAL2 - 1) | ~CST2
3809 : // as maximum.
3810 : // For signed comparison, if CST2 doesn't have most significant bit
3811 : // set, handle it similarly. If CST2 has MSB set, the maximum is
3812 : // the same and minimum is INT_MIN.
3813 2674609 : valv = lhs.upper_bound ();
3814 2674609 : minv = valv & cst2v;
3815 2674609 : if (minv == valv)
3816 2647078 : maxv = valv;
3817 : else
3818 : {
3819 27531 : maxv = masked_increment (valv, cst2v, sgnbit, nprec);
3820 27531 : if (maxv == valv)
3821 : {
3822 : // If we couldn't determine anything on either bound, return
3823 : // undefined.
3824 6476 : if (we_know_nothing)
3825 3237 : r.set_undefined ();
3826 6476 : return;
3827 : }
3828 21055 : maxv -= 1;
3829 : }
3830 2668133 : maxv |= ~cst2v;
3831 2668133 : minv = sgnbit;
3832 2668133 : int_range<2> upper_bits;
3833 2668133 : create_possibly_reversed_range (upper_bits, type, minv, maxv);
3834 2668133 : r.intersect (upper_bits);
3835 2674609 : }
3836 :
3837 : bool
3838 3292915 : operator_bitwise_and::op1_range (irange &r, tree type,
3839 : const irange &lhs,
3840 : const irange &op2,
3841 : relation_trio) const
3842 : {
3843 3292915 : if (lhs.undefined_p ())
3844 : return false;
3845 3292915 : if (types_compatible_p (type, boolean_type_node))
3846 782581 : return op_logical_and.op1_range (r, type, lhs, op2);
3847 :
3848 2510334 : r.set_undefined ();
3849 5724914 : for (unsigned i = 0; i < lhs.num_pairs (); ++i)
3850 : {
3851 6429160 : int_range_max chunk (lhs.type (),
3852 6429160 : lhs.lower_bound (i),
3853 6429160 : lhs.upper_bound (i));
3854 3214580 : int_range_max res;
3855 3214580 : simple_op1_range_solver (res, type, chunk, op2);
3856 3214580 : r.union_ (res);
3857 3214580 : }
3858 2510334 : if (r.undefined_p ())
3859 923 : set_nonzero_range_from_mask (r, type, lhs);
3860 :
3861 : // For MASK == op1 & MASK, all the bits in MASK must be set in op1.
3862 2510334 : wide_int mask;
3863 2510334 : if (lhs == op2 && lhs.singleton_p (mask))
3864 : {
3865 340121 : r.update_bitmask (irange_bitmask (mask, ~mask));
3866 340121 : return true;
3867 : }
3868 :
3869 2170213 : if (!op2.singleton_p (mask))
3870 : return true;
3871 :
3872 : // For 0 = op1 & MASK, op1 is ~MASK.
3873 1682645 : if (lhs.zero_p ())
3874 : {
3875 621075 : wide_int nz = wi::bit_not (op2.get_nonzero_bits ());
3876 621075 : int_range<2> tmp (type);
3877 621075 : tmp.set_nonzero_bits (nz);
3878 621075 : r.intersect (tmp);
3879 621075 : }
3880 :
3881 1682645 : irange_bitmask lhs_bm = lhs.get_bitmask ();
3882 : // given [5,7] mask 0x3 value 0x4 = N & [7, 7] mask 0x0 value 0x7
3883 : // Nothing is known about the bits not specified in the mask value (op2),
3884 : // Start with the mask, 1's will occur where values were masked.
3885 1682645 : wide_int op1_mask = ~mask;
3886 : // Any bits that are unknown on the LHS are also unknown in op1,
3887 : // so union the current mask with the LHS mask.
3888 1682645 : op1_mask |= lhs_bm.mask ();
3889 : // The resulting zeros correspond to known bits in the LHS mask, and
3890 : // the LHS value should tell us what they are. Mask off any
3891 : // extraneous values that are not covered by the mask.
3892 1682645 : wide_int op1_value = lhs_bm.value () & ~op1_mask;
3893 1682645 : irange_bitmask op1_bm (op1_value, op1_mask);
3894 : // Intersect this mask with anything already known about the value.
3895 : // A return valueof false indicated the bitmask is an UNDEFINED range.
3896 1682645 : if (op1_bm.intersect (r.get_bitmask ()))
3897 1682645 : r.update_bitmask (op1_bm);
3898 : else
3899 0 : r.set_undefined ();
3900 1682645 : return true;
3901 4192979 : }
3902 :
3903 : bool
3904 870953 : operator_bitwise_and::op2_range (irange &r, tree type,
3905 : const irange &lhs,
3906 : const irange &op1,
3907 : relation_trio) const
3908 : {
3909 870953 : return operator_bitwise_and::op1_range (r, type, lhs, op1);
3910 : }
3911 :
3912 :
3913 : class operator_logical_or : public range_operator
3914 : {
3915 : using range_operator::fold_range;
3916 : using range_operator::op1_range;
3917 : using range_operator::op2_range;
3918 : public:
3919 : bool fold_range (irange &r, tree type,
3920 : const irange &lh,
3921 : const irange &rh,
3922 : relation_trio rel = TRIO_VARYING) const final override;
3923 : bool op1_range (irange &r, tree type,
3924 : const irange &lhs,
3925 : const irange &op2,
3926 : relation_trio rel = TRIO_VARYING) const final override;
3927 : bool op2_range (irange &r, tree type,
3928 : const irange &lhs,
3929 : const irange &op1,
3930 : relation_trio rel = TRIO_VARYING) const final override;
3931 : // Check compatibility of all operands.
3932 0 : bool operand_check_p (tree t1, tree t2, tree t3) const final override
3933 0 : { return range_compatible_p (t1, t2) && range_compatible_p (t1, t3); }
3934 : } op_logical_or;
3935 :
3936 : bool
3937 0 : operator_logical_or::fold_range (irange &r, tree type ATTRIBUTE_UNUSED,
3938 : const irange &lh,
3939 : const irange &rh,
3940 : relation_trio) const
3941 : {
3942 0 : if (empty_range_varying (r, type, lh, rh))
3943 0 : return true;
3944 :
3945 0 : r = lh;
3946 0 : r.union_ (rh);
3947 0 : return true;
3948 : }
3949 :
3950 : bool
3951 308594 : operator_logical_or::op1_range (irange &r, tree type,
3952 : const irange &lhs,
3953 : const irange &op2 ATTRIBUTE_UNUSED,
3954 : relation_trio) const
3955 : {
3956 308594 : switch (get_bool_state (r, lhs, type))
3957 : {
3958 185096 : case BRS_FALSE:
3959 : // A false result means both sides of the OR must be false.
3960 185096 : r = range_false (type);
3961 185096 : break;
3962 123498 : default:
3963 : // Any other result means only one side has to be true, the
3964 : // other side can be anything. so we can't be sure of any result
3965 : // here.
3966 123498 : r = range_true_and_false (type);
3967 123498 : break;
3968 : }
3969 308594 : return true;
3970 : }
3971 :
3972 : bool
3973 0 : operator_logical_or::op2_range (irange &r, tree type,
3974 : const irange &lhs,
3975 : const irange &op1,
3976 : relation_trio) const
3977 : {
3978 0 : return operator_logical_or::op1_range (r, type, lhs, op1);
3979 : }
3980 :
3981 :
3982 : void
3983 2375026 : operator_bitwise_or::update_bitmask (irange &r, const irange &lh,
3984 : const irange &rh) const
3985 : {
3986 2375026 : update_known_bitmask (r, BIT_IOR_EXPR, lh, rh);
3987 2375026 : }
3988 :
3989 : void
3990 6878940 : operator_bitwise_or::wi_fold (irange &r, tree type,
3991 : const wide_int &lh_lb,
3992 : const wide_int &lh_ub,
3993 : const wide_int &rh_lb,
3994 : const wide_int &rh_ub) const
3995 : {
3996 6878940 : if (wi_optimize_and_or (r, BIT_IOR_EXPR, type, lh_lb, lh_ub, rh_lb, rh_ub))
3997 6190280 : return;
3998 :
3999 870645 : wide_int maybe_nonzero_lh, mustbe_nonzero_lh;
4000 870645 : wide_int maybe_nonzero_rh, mustbe_nonzero_rh;
4001 870645 : wi_set_zero_nonzero_bits (type, lh_lb, lh_ub,
4002 : maybe_nonzero_lh, mustbe_nonzero_lh);
4003 870645 : wi_set_zero_nonzero_bits (type, rh_lb, rh_ub,
4004 : maybe_nonzero_rh, mustbe_nonzero_rh);
4005 870645 : wide_int new_lb = mustbe_nonzero_lh | mustbe_nonzero_rh;
4006 870645 : wide_int new_ub = maybe_nonzero_lh | maybe_nonzero_rh;
4007 870645 : signop sign = TYPE_SIGN (type);
4008 : // If the input ranges contain only positive values we can
4009 : // truncate the minimum of the result range to the maximum
4010 : // of the input range minima.
4011 870645 : if (wi::ge_p (lh_lb, 0, sign)
4012 870645 : && wi::ge_p (rh_lb, 0, sign))
4013 : {
4014 659318 : new_lb = wi::max (new_lb, lh_lb, sign);
4015 659318 : new_lb = wi::max (new_lb, rh_lb, sign);
4016 : }
4017 : // If either input range contains only negative values
4018 : // we can truncate the minimum of the result range to the
4019 : // respective minimum range.
4020 870645 : if (wi::lt_p (lh_ub, 0, sign))
4021 20197 : new_lb = wi::max (new_lb, lh_lb, sign);
4022 870645 : if (wi::lt_p (rh_ub, 0, sign))
4023 10133 : new_lb = wi::max (new_lb, rh_lb, sign);
4024 : // If the limits got swapped around, return a conservative range.
4025 870645 : if (wi::gt_p (new_lb, new_ub, sign))
4026 : {
4027 : // Make sure that nonzero|X is nonzero.
4028 181985 : if (wi::gt_p (lh_lb, 0, sign)
4029 177588 : || wi::gt_p (rh_lb, 0, sign)
4030 121125 : || wi::lt_p (lh_ub, 0, sign)
4031 303110 : || wi::lt_p (rh_ub, 0, sign))
4032 60860 : r.set_nonzero (type);
4033 121125 : else if (sign == SIGNED
4034 121125 : && wi_optimize_signed_bitwise_op (r, type,
4035 : lh_lb, lh_ub,
4036 : rh_lb, rh_ub))
4037 : return;
4038 : else
4039 118610 : r.set_varying (type);
4040 179470 : return;
4041 : }
4042 688660 : value_range_with_overflow (r, type, new_lb, new_ub);
4043 870675 : }
4044 :
4045 : bool
4046 560397 : operator_bitwise_or::op1_range (irange &r, tree type,
4047 : const irange &lhs,
4048 : const irange &op2,
4049 : relation_trio) const
4050 : {
4051 560397 : if (lhs.undefined_p ())
4052 : return false;
4053 : // If this is really a logical wi_fold, call that.
4054 560397 : if (types_compatible_p (type, boolean_type_node))
4055 308594 : return op_logical_or.op1_range (r, type, lhs, op2);
4056 :
4057 251803 : if (lhs.zero_p ())
4058 : {
4059 79706 : r.set_zero (type);
4060 79706 : return true;
4061 : }
4062 :
4063 : // if (A < 0 && B < 0)
4064 : // Sometimes gets translated to
4065 : // _1 = A | B
4066 : // if (_1 < 0))
4067 : // It is useful for ranger to recognize a positive LHS means the RHS
4068 : // operands are also positive when dealing with the ELSE range..
4069 240132 : if (TYPE_SIGN (type) == SIGNED && wi::ge_p (lhs.lower_bound (), 0, SIGNED))
4070 : {
4071 27196 : unsigned prec = TYPE_PRECISION (type);
4072 27196 : r.set (type, wi::zero (prec), wi::max_value (prec, SIGNED));
4073 27196 : return true;
4074 : }
4075 144901 : r.set_varying (type);
4076 144901 : return true;
4077 : }
4078 :
4079 : bool
4080 282257 : operator_bitwise_or::op2_range (irange &r, tree type,
4081 : const irange &lhs,
4082 : const irange &op1,
4083 : relation_trio) const
4084 : {
4085 282257 : return operator_bitwise_or::op1_range (r, type, lhs, op1);
4086 : }
4087 :
4088 : void
4089 87653 : operator_bitwise_xor::update_bitmask (irange &r, const irange &lh,
4090 : const irange &rh) const
4091 : {
4092 87653 : update_known_bitmask (r, BIT_XOR_EXPR, lh, rh);
4093 87653 : }
4094 :
4095 : bool
4096 300915 : operator_bitwise_xor::fold_range (irange &r, tree type,
4097 : const irange &lh, const irange &rh,
4098 : relation_trio rel) const
4099 : {
4100 : // Handle X ^ UNDEFINED = UNDEFINED.
4101 300915 : if (lh.undefined_p () || rh.undefined_p ())
4102 : {
4103 397 : r.set_undefined ();
4104 397 : return true;
4105 : }
4106 :
4107 : // Next, handle X ^ X == [0, 0].
4108 300518 : if (rel.op1_op2 () == VREL_EQ)
4109 : {
4110 66 : r.set_zero (type);
4111 66 : return true;
4112 : }
4113 :
4114 : // If either operand is VARYING, the result is VARYING.
4115 300452 : if (lh.varying_p () || rh.varying_p ())
4116 : {
4117 : // If the operands are not equal, zero is not possible.
4118 210820 : if (rel.op1_op2 () != VREL_NE)
4119 209725 : r.set_varying (type);
4120 : else
4121 1095 : r.set_nonzero (type);
4122 210820 : return true;
4123 : }
4124 :
4125 : // Now deal with X ^ 0 == X.
4126 89632 : if (lh.zero_p ())
4127 : {
4128 1443 : r = rh;
4129 1443 : return true;
4130 : }
4131 88189 : if (rh.zero_p ())
4132 : {
4133 536 : r = lh;
4134 536 : return true;
4135 : }
4136 :
4137 : // Start with the legacy range. This can sometimes pick up values
4138 : // when there are a lot of subranges and fold_range aggregates them.
4139 87653 : bool res = range_operator::fold_range (r, type, lh, rh, rel);
4140 :
4141 : // Calculate the XOR identity : x ^ y = (x | y) & ~(x & y)
4142 : // AND and OR are already much better optimized.
4143 87653 : int_range_max tmp1, tmp2, tmp3, new_result;
4144 87653 : int_range<2> varying;
4145 87653 : varying.set_varying (type);
4146 :
4147 87653 : if (m_or.fold_range (tmp1, type, lh, rh, rel)
4148 87653 : && m_and.fold_range (tmp2, type, lh, rh, rel)
4149 87653 : && m_not.fold_range (tmp3, type, tmp2, varying, rel)
4150 175306 : && m_and.fold_range (new_result, type, tmp1, tmp3, rel))
4151 : {
4152 : // If the operands are not equal, or the LH does not contain any
4153 : // element of the RH, zero is not possible.
4154 87653 : tmp1 = lh;
4155 87653 : if (rel.op1_op2 () == VREL_NE
4156 87653 : || (tmp1.intersect (rh) && tmp1.undefined_p ()))
4157 : {
4158 32776 : tmp1.set_nonzero (type);
4159 32776 : new_result.intersect (tmp1);
4160 : }
4161 :
4162 : // Combine with the legacy range if there was one.
4163 87653 : if (res)
4164 87653 : r.intersect (new_result);
4165 : else
4166 0 : r = new_result;
4167 87653 : return true;
4168 : }
4169 : return res;
4170 87653 : }
4171 :
4172 : void
4173 173638 : operator_bitwise_xor::wi_fold (irange &r, tree type,
4174 : const wide_int &lh_lb,
4175 : const wide_int &lh_ub,
4176 : const wide_int &rh_lb,
4177 : const wide_int &rh_ub) const
4178 : {
4179 173638 : signop sign = TYPE_SIGN (type);
4180 173638 : wide_int maybe_nonzero_lh, mustbe_nonzero_lh;
4181 173638 : wide_int maybe_nonzero_rh, mustbe_nonzero_rh;
4182 173638 : wi_set_zero_nonzero_bits (type, lh_lb, lh_ub,
4183 : maybe_nonzero_lh, mustbe_nonzero_lh);
4184 173638 : wi_set_zero_nonzero_bits (type, rh_lb, rh_ub,
4185 : maybe_nonzero_rh, mustbe_nonzero_rh);
4186 :
4187 520914 : wide_int result_zero_bits = ((mustbe_nonzero_lh & mustbe_nonzero_rh)
4188 520914 : | ~(maybe_nonzero_lh | maybe_nonzero_rh));
4189 173638 : wide_int result_one_bits
4190 347276 : = (wi::bit_and_not (mustbe_nonzero_lh, maybe_nonzero_rh)
4191 347276 : | wi::bit_and_not (mustbe_nonzero_rh, maybe_nonzero_lh));
4192 173638 : wide_int new_ub = ~result_zero_bits;
4193 173638 : wide_int new_lb = result_one_bits;
4194 :
4195 : // If the range has all positive or all negative values, the result
4196 : // is better than VARYING.
4197 173638 : if (wi::lt_p (new_lb, 0, sign) || wi::ge_p (new_ub, 0, sign))
4198 166958 : value_range_with_overflow (r, type, new_lb, new_ub);
4199 6680 : else if (sign == SIGNED
4200 6680 : && wi_optimize_signed_bitwise_op (r, type,
4201 : lh_lb, lh_ub,
4202 : rh_lb, rh_ub))
4203 : ; /* Do nothing. */
4204 : else
4205 998 : r.set_varying (type);
4206 :
4207 : /* Furthermore, XOR is non-zero if its arguments can't be equal. */
4208 173638 : if (wi::lt_p (lh_ub, rh_lb, sign)
4209 114337 : || wi::lt_p (rh_ub, lh_lb, sign)
4210 266192 : || wi::ne_p (result_one_bits, 0))
4211 : {
4212 81084 : int_range<2> tmp;
4213 81084 : tmp.set_nonzero (type);
4214 81084 : r.intersect (tmp);
4215 81084 : }
4216 173638 : }
4217 :
4218 : bool
4219 87653 : operator_bitwise_xor::op1_op2_relation_effect (irange &lhs_range,
4220 : tree type,
4221 : const irange &,
4222 : const irange &,
4223 : relation_kind rel) const
4224 : {
4225 87653 : if (rel == VREL_VARYING)
4226 : return false;
4227 :
4228 4287 : int_range<2> rel_range;
4229 :
4230 4287 : switch (rel)
4231 : {
4232 0 : case VREL_EQ:
4233 0 : rel_range.set_zero (type);
4234 0 : break;
4235 488 : case VREL_NE:
4236 488 : rel_range.set_nonzero (type);
4237 488 : break;
4238 : default:
4239 : return false;
4240 : }
4241 :
4242 488 : lhs_range.intersect (rel_range);
4243 488 : return true;
4244 4287 : }
4245 :
4246 : bool
4247 86237 : operator_bitwise_xor::op1_range (irange &r, tree type,
4248 : const irange &lhs,
4249 : const irange &op2,
4250 : relation_trio) const
4251 : {
4252 86237 : if (lhs.undefined_p () || lhs.varying_p ())
4253 : {
4254 7478 : r = lhs;
4255 7478 : return true;
4256 : }
4257 78759 : if (types_compatible_p (type, boolean_type_node))
4258 : {
4259 1708 : switch (get_bool_state (r, lhs, type))
4260 : {
4261 761 : case BRS_TRUE:
4262 761 : if (op2.varying_p ())
4263 729 : r.set_varying (type);
4264 32 : else if (op2.zero_p ())
4265 24 : r = range_true (type);
4266 : // See get_bool_state for the rationale
4267 8 : else if (op2.undefined_p () || contains_zero_p (op2))
4268 0 : r = range_true_and_false (type);
4269 : else
4270 8 : r = range_false (type);
4271 : break;
4272 947 : case BRS_FALSE:
4273 947 : r = op2;
4274 947 : break;
4275 : default:
4276 : break;
4277 : }
4278 1708 : return true;
4279 : }
4280 77051 : r.set_varying (type);
4281 77051 : return true;
4282 : }
4283 :
4284 : bool
4285 36978 : operator_bitwise_xor::op2_range (irange &r, tree type,
4286 : const irange &lhs,
4287 : const irange &op1,
4288 : relation_trio) const
4289 : {
4290 36978 : return operator_bitwise_xor::op1_range (r, type, lhs, op1);
4291 : }
4292 :
4293 : class operator_trunc_mod : public range_operator
4294 : {
4295 : using range_operator::op1_range;
4296 : using range_operator::op2_range;
4297 : using range_operator::update_bitmask;
4298 : public:
4299 : virtual void wi_fold (irange &r, tree type,
4300 : const wide_int &lh_lb,
4301 : const wide_int &lh_ub,
4302 : const wide_int &rh_lb,
4303 : const wide_int &rh_ub) const;
4304 : virtual bool op1_range (irange &r, tree type,
4305 : const irange &lhs,
4306 : const irange &op2,
4307 : relation_trio) const;
4308 : virtual bool op2_range (irange &r, tree type,
4309 : const irange &lhs,
4310 : const irange &op1,
4311 : relation_trio) const;
4312 1018288 : void update_bitmask (irange &r, const irange &lh, const irange &rh) const
4313 1018288 : { update_known_bitmask (r, TRUNC_MOD_EXPR, lh, rh); }
4314 : } op_trunc_mod;
4315 :
4316 : void
4317 1250789 : operator_trunc_mod::wi_fold (irange &r, tree type,
4318 : const wide_int &lh_lb,
4319 : const wide_int &lh_ub,
4320 : const wide_int &rh_lb,
4321 : const wide_int &rh_ub) const
4322 : {
4323 1250789 : wide_int new_lb, new_ub, tmp;
4324 1250789 : signop sign = TYPE_SIGN (type);
4325 1250789 : unsigned prec = TYPE_PRECISION (type);
4326 :
4327 : // Mod 0 is undefined.
4328 1250789 : if (wi_zero_p (type, rh_lb, rh_ub))
4329 : {
4330 9236 : r.set_undefined ();
4331 9236 : return;
4332 : }
4333 :
4334 : // Check for constant and try to fold.
4335 1450875 : if (lh_lb == lh_ub && rh_lb == rh_ub)
4336 : {
4337 21516 : wi::overflow_type ov = wi::OVF_NONE;
4338 21516 : tmp = wi::mod_trunc (lh_lb, rh_lb, sign, &ov);
4339 21516 : if (ov == wi::OVF_NONE)
4340 : {
4341 21490 : r = int_range<2> (type, tmp, tmp);
4342 21490 : return;
4343 : }
4344 : }
4345 :
4346 : // ABS (A % B) < ABS (B) and either 0 <= A % B <= A or A <= A % B <= 0.
4347 1220063 : new_ub = rh_ub - 1;
4348 1220063 : if (sign == SIGNED)
4349 : {
4350 533814 : tmp = -1 - rh_lb;
4351 533814 : new_ub = wi::smax (new_ub, tmp);
4352 : }
4353 :
4354 1220063 : if (sign == UNSIGNED)
4355 686249 : new_lb = wi::zero (prec);
4356 : else
4357 : {
4358 533814 : new_lb = -new_ub;
4359 533814 : tmp = lh_lb;
4360 533814 : if (wi::gts_p (tmp, 0))
4361 130445 : tmp = wi::zero (prec);
4362 533838 : new_lb = wi::smax (new_lb, tmp);
4363 : }
4364 1220063 : tmp = lh_ub;
4365 1220063 : if (sign == SIGNED && wi::neg_p (tmp))
4366 26471 : tmp = wi::zero (prec);
4367 1220063 : new_ub = wi::min (new_ub, tmp, sign);
4368 :
4369 1220063 : value_range_with_overflow (r, type, new_lb, new_ub);
4370 :
4371 : // When all positive and all X/Y combinations produce the same quotient
4372 : // we can refine the result with X % Y == X - Q * Y.
4373 : // Ensure that division by 0 is not an option.
4374 1220063 : if (wi::gt_p (rh_lb, 0, sign) && wi::ge_p (lh_lb, 0, sign))
4375 : {
4376 311629 : wide_int q_lb = wi::div_trunc (lh_lb, rh_ub, sign);
4377 311629 : wide_int q_ub = wi::div_trunc (lh_ub, rh_lb, sign);
4378 :
4379 311629 : if (q_lb == q_ub)
4380 : {
4381 38737 : new_lb = lh_lb - q_lb * rh_ub;
4382 38737 : new_ub = lh_ub - q_lb * rh_lb;
4383 :
4384 38737 : int_range<2> refined (type, new_lb, new_ub);
4385 38737 : r.intersect (refined);
4386 38737 : }
4387 311642 : }
4388 1250913 : }
4389 :
4390 : bool
4391 521770 : operator_trunc_mod::op1_range (irange &r, tree type,
4392 : const irange &lhs,
4393 : const irange &,
4394 : relation_trio) const
4395 : {
4396 521770 : if (lhs.undefined_p ())
4397 : return false;
4398 : // PR 91029.
4399 521770 : signop sign = TYPE_SIGN (type);
4400 521770 : unsigned prec = TYPE_PRECISION (type);
4401 : // (a % b) >= x && x > 0 , then a >= x.
4402 521862 : if (wi::gt_p (lhs.lower_bound (), 0, sign))
4403 : {
4404 133238 : r.set (type, lhs.lower_bound (), wi::max_value (prec, sign));
4405 133205 : return true;
4406 : }
4407 : // (a % b) <= x && x < 0 , then a <= x.
4408 388624 : if (wi::lt_p (lhs.upper_bound (), 0, sign))
4409 : {
4410 8101 : r.set (type, wi::min_value (prec, sign), lhs.upper_bound ());
4411 8101 : return true;
4412 : }
4413 : return false;
4414 : }
4415 :
4416 : bool
4417 346665 : operator_trunc_mod::op2_range (irange &r, tree type,
4418 : const irange &lhs,
4419 : const irange &,
4420 : relation_trio) const
4421 : {
4422 346665 : if (lhs.undefined_p ())
4423 : return false;
4424 : // PR 91029.
4425 346665 : signop sign = TYPE_SIGN (type);
4426 346665 : unsigned prec = TYPE_PRECISION (type);
4427 : // (a % b) >= x && x > 0 , then b is in ~[-x, x] for signed
4428 : // or b > x for unsigned.
4429 346698 : if (wi::gt_p (lhs.lower_bound (), 0, sign))
4430 : {
4431 53232 : if (sign == SIGNED)
4432 2096 : r.set (type, wi::neg (lhs.lower_bound ()),
4433 4192 : lhs.lower_bound (), VR_ANTI_RANGE);
4434 51148 : else if (wi::lt_p (lhs.lower_bound (), wi::max_value (prec, sign),
4435 : sign))
4436 51154 : r.set (type, lhs.lower_bound () + 1, wi::max_value (prec, sign));
4437 : else
4438 : return false;
4439 53232 : return true;
4440 : }
4441 : // (a % b) <= x && x < 0 , then b is in ~[x, -x].
4442 293460 : if (wi::lt_p (lhs.upper_bound (), 0, sign))
4443 : {
4444 5348 : if (wi::gt_p (lhs.upper_bound (), wi::min_value (prec, sign), sign))
4445 5348 : r.set (type, lhs.upper_bound (),
4446 10696 : wi::neg (lhs.upper_bound ()), VR_ANTI_RANGE);
4447 : else
4448 : return false;
4449 5348 : return true;
4450 : }
4451 : return false;
4452 : }
4453 :
4454 :
4455 : class operator_logical_not : public range_operator
4456 : {
4457 : using range_operator::fold_range;
4458 : using range_operator::op1_range;
4459 : public:
4460 : bool fold_range (irange &r, tree type,
4461 : const irange &lh,
4462 : const irange &rh,
4463 : relation_trio rel = TRIO_VARYING) const final override;
4464 : bool op1_range (irange &r, tree type,
4465 : const irange &lhs,
4466 : const irange &op2,
4467 : relation_trio rel = TRIO_VARYING) const final override;
4468 : // Check compatibility of LHS and op1.
4469 0 : bool operand_check_p (tree t1, tree t2, tree) const final override
4470 0 : { return range_compatible_p (t1, t2); }
4471 : } op_logical_not;
4472 :
4473 : // Folding a logical NOT, oddly enough, involves doing nothing on the
4474 : // forward pass through. During the initial walk backwards, the
4475 : // logical NOT reversed the desired outcome on the way back, so on the
4476 : // way forward all we do is pass the range forward.
4477 : //
4478 : // b_2 = x_1 < 20
4479 : // b_3 = !b_2
4480 : // if (b_3)
4481 : // to determine the TRUE branch, walking backward
4482 : // if (b_3) if ([1,1])
4483 : // b_3 = !b_2 [1,1] = ![0,0]
4484 : // b_2 = x_1 < 20 [0,0] = x_1 < 20, false, so x_1 == [20, 255]
4485 : // which is the result we are looking for.. so.. pass it through.
4486 :
4487 : bool
4488 238382 : operator_logical_not::fold_range (irange &r, tree type,
4489 : const irange &lh,
4490 : const irange &rh ATTRIBUTE_UNUSED,
4491 : relation_trio) const
4492 : {
4493 238382 : if (empty_range_varying (r, type, lh, rh))
4494 0 : return true;
4495 :
4496 238382 : r = lh;
4497 238382 : if (!lh.varying_p () && !lh.undefined_p ())
4498 49915 : r.invert ();
4499 :
4500 : return true;
4501 : }
4502 :
4503 : bool
4504 26443 : operator_logical_not::op1_range (irange &r,
4505 : tree type,
4506 : const irange &lhs,
4507 : const irange &op2,
4508 : relation_trio) const
4509 : {
4510 : // Logical NOT is involutary...do it again.
4511 26443 : return fold_range (r, type, lhs, op2);
4512 : }
4513 :
4514 : bool
4515 614470 : operator_bitwise_not::fold_range (irange &r, tree type,
4516 : const irange &lh,
4517 : const irange &rh,
4518 : relation_trio) const
4519 : {
4520 614470 : if (empty_range_varying (r, type, lh, rh))
4521 121 : return true;
4522 :
4523 614349 : if (types_compatible_p (type, boolean_type_node))
4524 211939 : return op_logical_not.fold_range (r, type, lh, rh);
4525 :
4526 : // ~X is simply -1 - X.
4527 804820 : int_range<1> minusone (type, wi::minus_one (TYPE_PRECISION (type)),
4528 804820 : wi::minus_one (TYPE_PRECISION (type)));
4529 402410 : return range_op_handler (MINUS_EXPR).fold_range (r, type, minusone, lh);
4530 402410 : }
4531 :
4532 : bool
4533 51975 : operator_bitwise_not::op1_range (irange &r, tree type,
4534 : const irange &lhs,
4535 : const irange &op2,
4536 : relation_trio) const
4537 : {
4538 51975 : if (lhs.undefined_p ())
4539 : return false;
4540 51975 : if (types_compatible_p (type, boolean_type_node))
4541 26443 : return op_logical_not.op1_range (r, type, lhs, op2);
4542 :
4543 : // ~X is -1 - X and since bitwise NOT is involutary...do it again.
4544 25532 : return fold_range (r, type, lhs, op2);
4545 : }
4546 :
4547 : void
4548 0 : operator_bitwise_not::update_bitmask (irange &r, const irange &lh,
4549 : const irange &rh) const
4550 : {
4551 0 : update_known_bitmask (r, BIT_NOT_EXPR, lh, rh);
4552 0 : }
4553 :
4554 :
4555 : bool
4556 311597 : operator_cst::fold_range (irange &r, tree type ATTRIBUTE_UNUSED,
4557 : const irange &lh,
4558 : const irange &rh ATTRIBUTE_UNUSED,
4559 : relation_trio) const
4560 : {
4561 311597 : r = lh;
4562 311597 : return true;
4563 : }
4564 :
4565 :
4566 : // Determine if there is a relationship between LHS and OP1.
4567 :
4568 : relation_kind
4569 856947 : operator_identity::lhs_op1_relation (const irange &lhs,
4570 : const irange &op1 ATTRIBUTE_UNUSED,
4571 : const irange &op2 ATTRIBUTE_UNUSED,
4572 : relation_kind) const
4573 : {
4574 856947 : if (lhs.undefined_p ())
4575 527 : return VREL_VARYING;
4576 : // Simply a copy, so they are equivalent.
4577 : return VREL_EQ;
4578 : }
4579 :
4580 : bool
4581 857671 : operator_identity::fold_range (irange &r, tree type ATTRIBUTE_UNUSED,
4582 : const irange &lh,
4583 : const irange &rh ATTRIBUTE_UNUSED,
4584 : relation_trio) const
4585 : {
4586 857671 : r = lh;
4587 857671 : return true;
4588 : }
4589 :
4590 : bool
4591 275695 : operator_identity::op1_range (irange &r, tree type ATTRIBUTE_UNUSED,
4592 : const irange &lhs,
4593 : const irange &op2 ATTRIBUTE_UNUSED,
4594 : relation_trio) const
4595 : {
4596 275695 : r = lhs;
4597 275695 : return true;
4598 : }
4599 :
4600 :
4601 : class operator_unknown : public range_operator
4602 : {
4603 : using range_operator::fold_range;
4604 : public:
4605 : virtual bool fold_range (irange &r, tree type,
4606 : const irange &op1,
4607 : const irange &op2,
4608 : relation_trio rel = TRIO_VARYING) const;
4609 : } op_unknown;
4610 :
4611 : bool
4612 789732 : operator_unknown::fold_range (irange &r, tree type,
4613 : const irange &lh ATTRIBUTE_UNUSED,
4614 : const irange &rh ATTRIBUTE_UNUSED,
4615 : relation_trio) const
4616 : {
4617 789732 : r.set_varying (type);
4618 789732 : return true;
4619 : }
4620 :
4621 :
4622 : void
4623 111381 : operator_abs::wi_fold (irange &r, tree type,
4624 : const wide_int &lh_lb, const wide_int &lh_ub,
4625 : const wide_int &rh_lb ATTRIBUTE_UNUSED,
4626 : const wide_int &rh_ub ATTRIBUTE_UNUSED) const
4627 : {
4628 111381 : wide_int min, max;
4629 111381 : signop sign = TYPE_SIGN (type);
4630 111381 : unsigned prec = TYPE_PRECISION (type);
4631 :
4632 : // Pass through LH for the easy cases.
4633 111381 : if (sign == UNSIGNED || wi::ge_p (lh_lb, 0, sign))
4634 : {
4635 12028 : r = int_range<1> (type, lh_lb, lh_ub);
4636 12028 : return;
4637 : }
4638 :
4639 : // -TYPE_MIN_VALUE = TYPE_MIN_VALUE with flag_wrapv so we can't get
4640 : // a useful range.
4641 99353 : wide_int min_value = wi::min_value (prec, sign);
4642 99353 : wide_int max_value = wi::max_value (prec, sign);
4643 99353 : if (!TYPE_OVERFLOW_UNDEFINED (type) && wi::eq_p (lh_lb, min_value))
4644 : {
4645 640 : r.set_varying (type);
4646 640 : return;
4647 : }
4648 :
4649 : // ABS_EXPR may flip the range around, if the original range
4650 : // included negative values.
4651 98713 : if (wi::eq_p (lh_lb, min_value))
4652 : {
4653 : // ABS ([-MIN, -MIN]) isn't representable, but we have traditionally
4654 : // returned [-MIN,-MIN] so this preserves that behavior. PR37078
4655 35347 : if (wi::eq_p (lh_ub, min_value))
4656 : {
4657 104 : r = int_range<1> (type, min_value, min_value);
4658 104 : return;
4659 : }
4660 35243 : min = max_value;
4661 : }
4662 : else
4663 63366 : min = wi::abs (lh_lb);
4664 :
4665 98609 : if (wi::eq_p (lh_ub, min_value))
4666 0 : max = max_value;
4667 : else
4668 98609 : max = wi::abs (lh_ub);
4669 :
4670 : // If the range contains zero then we know that the minimum value in the
4671 : // range will be zero.
4672 98609 : if (wi::le_p (lh_lb, 0, sign) && wi::ge_p (lh_ub, 0, sign))
4673 : {
4674 88841 : if (wi::gt_p (min, max, sign))
4675 51819 : max = min;
4676 88841 : min = wi::zero (prec);
4677 : }
4678 : else
4679 : {
4680 : // If the range was reversed, swap MIN and MAX.
4681 9768 : if (wi::gt_p (min, max, sign))
4682 9161 : std::swap (min, max);
4683 : }
4684 :
4685 : // If the new range has its limits swapped around (MIN > MAX), then
4686 : // the operation caused one of them to wrap around. The only thing
4687 : // we know is that the result is positive.
4688 98609 : if (wi::gt_p (min, max, sign))
4689 : {
4690 0 : min = wi::zero (prec);
4691 0 : max = max_value;
4692 : }
4693 98609 : r = int_range<1> (type, min, max);
4694 112125 : }
4695 :
4696 : bool
4697 96368 : operator_abs::op1_range (irange &r, tree type,
4698 : const irange &lhs,
4699 : const irange &op2,
4700 : relation_trio) const
4701 : {
4702 96368 : if (empty_range_varying (r, type, lhs, op2))
4703 0 : return true;
4704 96368 : if (TYPE_UNSIGNED (type))
4705 : {
4706 0 : r = lhs;
4707 0 : return true;
4708 : }
4709 : // Start with the positives because negatives are an impossible result.
4710 96368 : int_range_max positives = range_positives (type);
4711 96368 : positives.intersect (lhs);
4712 96368 : r = positives;
4713 : // Then add the negative of each pair:
4714 : // ABS(op1) = [5,20] would yield op1 => [-20,-5][5,20].
4715 193525 : for (unsigned i = 0; i < positives.num_pairs (); ++i)
4716 97157 : r.union_ (int_range<1> (type,
4717 194314 : -positives.upper_bound (i),
4718 291471 : -positives.lower_bound (i)));
4719 : // With flag_wrapv, -TYPE_MIN_VALUE = TYPE_MIN_VALUE which is
4720 : // unrepresentable. Add -TYPE_MIN_VALUE in this case.
4721 96368 : wide_int min_value = wi::min_value (TYPE_PRECISION (type), TYPE_SIGN (type));
4722 96368 : wide_int lb = lhs.lower_bound ();
4723 96368 : if (!TYPE_OVERFLOW_UNDEFINED (type) && wi::eq_p (lb, min_value))
4724 168 : r.union_ (int_range<2> (type, lb, lb));
4725 96368 : return true;
4726 96368 : }
4727 :
4728 : void
4729 104273 : operator_abs::update_bitmask (irange &r, const irange &lh,
4730 : const irange &rh) const
4731 : {
4732 104273 : update_known_bitmask (r, ABS_EXPR, lh, rh);
4733 104273 : }
4734 :
4735 : class operator_absu : public range_operator
4736 : {
4737 : using range_operator::update_bitmask;
4738 : public:
4739 : virtual void wi_fold (irange &r, tree type,
4740 : const wide_int &lh_lb, const wide_int &lh_ub,
4741 : const wide_int &rh_lb, const wide_int &rh_ub)
4742 : const final override;
4743 : virtual void update_bitmask (irange &r, const irange &lh,
4744 : const irange &rh) const final override;
4745 : } op_absu;
4746 :
4747 : void
4748 12948 : operator_absu::wi_fold (irange &r, tree type,
4749 : const wide_int &lh_lb, const wide_int &lh_ub,
4750 : const wide_int &rh_lb ATTRIBUTE_UNUSED,
4751 : const wide_int &rh_ub ATTRIBUTE_UNUSED) const
4752 : {
4753 12948 : wide_int new_lb, new_ub;
4754 :
4755 : // Pass through VR0 the easy cases.
4756 12948 : if (wi::ges_p (lh_lb, 0))
4757 : {
4758 2485 : new_lb = lh_lb;
4759 2485 : new_ub = lh_ub;
4760 : }
4761 : else
4762 : {
4763 10463 : new_lb = wi::abs (lh_lb);
4764 10463 : new_ub = wi::abs (lh_ub);
4765 :
4766 : // If the range contains zero then we know that the minimum
4767 : // value in the range will be zero.
4768 10463 : if (wi::ges_p (lh_ub, 0))
4769 : {
4770 7996 : if (wi::gtu_p (new_lb, new_ub))
4771 6700 : new_ub = new_lb;
4772 7996 : new_lb = wi::zero (TYPE_PRECISION (type));
4773 : }
4774 : else
4775 2467 : std::swap (new_lb, new_ub);
4776 : }
4777 :
4778 12948 : gcc_checking_assert (TYPE_UNSIGNED (type));
4779 12948 : r = int_range<1> (type, new_lb, new_ub);
4780 12948 : }
4781 :
4782 : void
4783 11564 : operator_absu::update_bitmask (irange &r, const irange &lh,
4784 : const irange &rh) const
4785 : {
4786 11564 : update_known_bitmask (r, ABSU_EXPR, lh, rh);
4787 11564 : }
4788 :
4789 :
4790 : bool
4791 572689 : operator_negate::fold_range (irange &r, tree type,
4792 : const irange &lh,
4793 : const irange &rh,
4794 : relation_trio) const
4795 : {
4796 572689 : if (empty_range_varying (r, type, lh, rh))
4797 890 : return true;
4798 :
4799 : // -X is simply 0 - X.
4800 571799 : int_range<1> zero;
4801 571799 : zero.set_zero (type);
4802 571799 : return range_op_handler (MINUS_EXPR).fold_range (r, type, zero, lh);
4803 571799 : }
4804 :
4805 : bool
4806 71325 : operator_negate::op1_range (irange &r, tree type,
4807 : const irange &lhs,
4808 : const irange &op2,
4809 : relation_trio) const
4810 : {
4811 : // NEGATE is involutory.
4812 71325 : return fold_range (r, type, lhs, op2);
4813 : }
4814 :
4815 :
4816 : bool
4817 0 : operator_addr_expr::fold_range (irange &r, tree type,
4818 : const irange &lh,
4819 : const irange &rh,
4820 : relation_trio) const
4821 : {
4822 0 : if (empty_range_varying (r, type, lh, rh))
4823 0 : return true;
4824 :
4825 : // Return a non-null pointer of the LHS type (passed in op2).
4826 0 : if (lh.zero_p ())
4827 0 : r.set_zero (type);
4828 0 : else if (lh.undefined_p () || contains_zero_p (lh))
4829 0 : r.set_varying (type);
4830 : else
4831 0 : r.set_nonzero (type);
4832 : return true;
4833 : }
4834 :
4835 : bool
4836 0 : operator_addr_expr::op1_range (irange &r, tree type,
4837 : const irange &lhs,
4838 : const irange &op2,
4839 : relation_trio) const
4840 : {
4841 0 : if (empty_range_varying (r, type, lhs, op2))
4842 0 : return true;
4843 :
4844 : // Return a non-null pointer of the LHS type (passed in op2), but only
4845 : // if we cant overflow, eitherwise a no-zero offset could wrap to zero.
4846 : // See PR 111009.
4847 0 : if (!lhs.undefined_p () && !contains_zero_p (lhs) && TYPE_OVERFLOW_UNDEFINED (type))
4848 0 : r.set_nonzero (type);
4849 : else
4850 0 : r.set_varying (type);
4851 : return true;
4852 : }
4853 :
4854 : // Initialize any integral operators to the primary table
4855 :
4856 : void
4857 297658 : range_op_table::initialize_integral_ops ()
4858 : {
4859 297658 : set (TRUNC_DIV_EXPR, op_trunc_div);
4860 297658 : set (FLOOR_DIV_EXPR, op_floor_div);
4861 297658 : set (ROUND_DIV_EXPR, op_round_div);
4862 297658 : set (CEIL_DIV_EXPR, op_ceil_div);
4863 297658 : set (EXACT_DIV_EXPR, op_exact_div);
4864 297658 : set (LSHIFT_EXPR, op_lshift);
4865 297658 : set (RSHIFT_EXPR, op_rshift);
4866 297658 : set (TRUTH_AND_EXPR, op_logical_and);
4867 297658 : set (TRUTH_OR_EXPR, op_logical_or);
4868 297658 : set (TRUNC_MOD_EXPR, op_trunc_mod);
4869 297658 : set (TRUTH_NOT_EXPR, op_logical_not);
4870 297658 : set (IMAGPART_EXPR, op_unknown);
4871 297658 : set (REALPART_EXPR, op_unknown);
4872 297658 : set (ABSU_EXPR, op_absu);
4873 297658 : set (OP_WIDEN_MULT_SIGNED, op_widen_mult_signed);
4874 297658 : set (OP_WIDEN_MULT_UNSIGNED, op_widen_mult_unsigned);
4875 297658 : set (OP_WIDEN_MULT_SIGNED_UNSIGNED, op_widen_mult_signed_unsigned);
4876 297658 : set (OP_WIDEN_PLUS_SIGNED, op_widen_plus_signed);
4877 297658 : set (OP_WIDEN_PLUS_UNSIGNED, op_widen_plus_unsigned);
4878 :
4879 297658 : }
4880 :
4881 : bool
4882 41488 : operator_plus::overflow_free_p (const irange &lh, const irange &rh,
4883 : relation_trio) const
4884 : {
4885 41488 : if (lh.undefined_p () || rh.undefined_p ())
4886 : return false;
4887 :
4888 41488 : tree type = lh.type ();
4889 41488 : if (TYPE_OVERFLOW_UNDEFINED (type))
4890 : return true;
4891 :
4892 10802 : wi::overflow_type ovf;
4893 10802 : signop sgn = TYPE_SIGN (type);
4894 10802 : wide_int wmax0 = lh.upper_bound ();
4895 10802 : wide_int wmax1 = rh.upper_bound ();
4896 10802 : wi::add (wmax0, wmax1, sgn, &ovf);
4897 10802 : if (ovf != wi::OVF_NONE)
4898 : return false;
4899 :
4900 1288 : if (TYPE_UNSIGNED (type))
4901 : return true;
4902 :
4903 372 : wide_int wmin0 = lh.lower_bound ();
4904 372 : wide_int wmin1 = rh.lower_bound ();
4905 372 : wi::add (wmin0, wmin1, sgn, &ovf);
4906 372 : if (ovf != wi::OVF_NONE)
4907 261 : return false;
4908 :
4909 : return true;
4910 11174 : }
4911 :
4912 : bool
4913 31 : operator_minus::overflow_free_p (const irange &lh, const irange &rh,
4914 : relation_trio) const
4915 : {
4916 31 : if (lh.undefined_p () || rh.undefined_p ())
4917 : return false;
4918 :
4919 31 : tree type = lh.type ();
4920 31 : if (TYPE_OVERFLOW_UNDEFINED (type))
4921 : return true;
4922 :
4923 10 : wi::overflow_type ovf;
4924 10 : signop sgn = TYPE_SIGN (type);
4925 10 : wide_int wmin0 = lh.lower_bound ();
4926 10 : wide_int wmax1 = rh.upper_bound ();
4927 10 : wi::sub (wmin0, wmax1, sgn, &ovf);
4928 10 : if (ovf != wi::OVF_NONE)
4929 : return false;
4930 :
4931 7 : if (TYPE_UNSIGNED (type))
4932 : return true;
4933 :
4934 6 : wide_int wmax0 = lh.upper_bound ();
4935 6 : wide_int wmin1 = rh.lower_bound ();
4936 6 : wi::sub (wmax0, wmin1, sgn, &ovf);
4937 6 : if (ovf != wi::OVF_NONE)
4938 0 : return false;
4939 :
4940 : return true;
4941 16 : }
4942 :
4943 : bool
4944 3260 : operator_mult::overflow_free_p (const irange &lh, const irange &rh,
4945 : relation_trio) const
4946 : {
4947 3260 : if (lh.undefined_p () || rh.undefined_p ())
4948 : return false;
4949 :
4950 3260 : tree type = lh.type ();
4951 3260 : if (TYPE_OVERFLOW_UNDEFINED (type))
4952 : return true;
4953 :
4954 2778 : wi::overflow_type ovf;
4955 2778 : signop sgn = TYPE_SIGN (type);
4956 2778 : wide_int wmax0 = lh.upper_bound ();
4957 2778 : wide_int wmax1 = rh.upper_bound ();
4958 2778 : wi::mul (wmax0, wmax1, sgn, &ovf);
4959 2778 : if (ovf != wi::OVF_NONE)
4960 : return false;
4961 :
4962 105 : if (TYPE_UNSIGNED (type))
4963 : return true;
4964 :
4965 22 : wide_int wmin0 = lh.lower_bound ();
4966 22 : wide_int wmin1 = rh.lower_bound ();
4967 22 : wi::mul (wmin0, wmin1, sgn, &ovf);
4968 22 : if (ovf != wi::OVF_NONE)
4969 : return false;
4970 :
4971 22 : wi::mul (wmin0, wmax1, sgn, &ovf);
4972 22 : if (ovf != wi::OVF_NONE)
4973 : return false;
4974 :
4975 22 : wi::mul (wmax0, wmin1, sgn, &ovf);
4976 22 : if (ovf != wi::OVF_NONE)
4977 : return false;
4978 :
4979 : return true;
4980 2800 : }
4981 :
4982 : #if CHECKING_P
4983 : #include "selftest.h"
4984 :
4985 : namespace selftest
4986 : {
4987 : #define INT(x) wi::shwi ((x), TYPE_PRECISION (integer_type_node))
4988 : #define UINT(x) wi::uhwi ((x), TYPE_PRECISION (unsigned_type_node))
4989 : #define INT16(x) wi::shwi ((x), TYPE_PRECISION (short_integer_type_node))
4990 : #define UINT16(x) wi::uhwi ((x), TYPE_PRECISION (short_unsigned_type_node))
4991 : #define SCHAR(x) wi::shwi ((x), TYPE_PRECISION (signed_char_type_node))
4992 : #define UCHAR(x) wi::uhwi ((x), TYPE_PRECISION (unsigned_char_type_node))
4993 :
4994 : static void
4995 4 : range_op_cast_tests ()
4996 : {
4997 4 : int_range<2> r0, r1, r2, rold;
4998 4 : r0.set_varying (integer_type_node);
4999 4 : wide_int maxint = r0.upper_bound ();
5000 :
5001 : // If a range is in any way outside of the range for the converted
5002 : // to range, default to the range for the new type.
5003 4 : r0.set_varying (short_integer_type_node);
5004 4 : wide_int minshort = r0.lower_bound ();
5005 4 : wide_int maxshort = r0.upper_bound ();
5006 4 : if (TYPE_PRECISION (integer_type_node)
5007 4 : > TYPE_PRECISION (short_integer_type_node))
5008 : {
5009 8 : r1 = int_range<1> (integer_type_node,
5010 4 : wi::zero (TYPE_PRECISION (integer_type_node)),
5011 8 : maxint);
5012 4 : range_cast (r1, short_integer_type_node);
5013 4 : ASSERT_TRUE (r1.lower_bound () == minshort
5014 : && r1.upper_bound() == maxshort);
5015 : }
5016 :
5017 : // (unsigned char)[-5,-1] => [251,255].
5018 4 : r0 = rold = int_range<1> (signed_char_type_node, SCHAR (-5), SCHAR (-1));
5019 4 : range_cast (r0, unsigned_char_type_node);
5020 4 : ASSERT_TRUE (r0 == int_range<1> (unsigned_char_type_node,
5021 : UCHAR (251), UCHAR (255)));
5022 4 : range_cast (r0, signed_char_type_node);
5023 4 : ASSERT_TRUE (r0 == rold);
5024 :
5025 : // (signed char)[15, 150] => [-128,-106][15,127].
5026 4 : r0 = rold = int_range<1> (unsigned_char_type_node, UCHAR (15), UCHAR (150));
5027 4 : range_cast (r0, signed_char_type_node);
5028 4 : r1 = int_range<1> (signed_char_type_node, SCHAR (15), SCHAR (127));
5029 4 : r2 = int_range<1> (signed_char_type_node, SCHAR (-128), SCHAR (-106));
5030 4 : r1.union_ (r2);
5031 4 : ASSERT_TRUE (r1 == r0);
5032 4 : range_cast (r0, unsigned_char_type_node);
5033 4 : ASSERT_TRUE (r0 == rold);
5034 :
5035 : // (unsigned char)[-5, 5] => [0,5][251,255].
5036 4 : r0 = rold = int_range<1> (signed_char_type_node, SCHAR (-5), SCHAR (5));
5037 4 : range_cast (r0, unsigned_char_type_node);
5038 4 : r1 = int_range<1> (unsigned_char_type_node, UCHAR (251), UCHAR (255));
5039 4 : r2 = int_range<1> (unsigned_char_type_node, UCHAR (0), UCHAR (5));
5040 4 : r1.union_ (r2);
5041 4 : ASSERT_TRUE (r0 == r1);
5042 4 : range_cast (r0, signed_char_type_node);
5043 4 : ASSERT_TRUE (r0 == rold);
5044 :
5045 : // (unsigned char)[-5,5] => [0,5][251,255].
5046 4 : r0 = int_range<1> (integer_type_node, INT (-5), INT (5));
5047 4 : range_cast (r0, unsigned_char_type_node);
5048 4 : r1 = int_range<1> (unsigned_char_type_node, UCHAR (0), UCHAR (5));
5049 4 : r1.union_ (int_range<1> (unsigned_char_type_node, UCHAR (251), UCHAR (255)));
5050 4 : ASSERT_TRUE (r0 == r1);
5051 :
5052 : // (unsigned char)[5U,1974U] => [0,255].
5053 4 : r0 = int_range<1> (unsigned_type_node, UINT (5), UINT (1974));
5054 4 : range_cast (r0, unsigned_char_type_node);
5055 4 : ASSERT_TRUE (r0 == int_range<1> (unsigned_char_type_node, UCHAR (0), UCHAR (255)));
5056 4 : range_cast (r0, integer_type_node);
5057 : // Going to a wider range should not sign extend.
5058 4 : ASSERT_TRUE (r0 == int_range<1> (integer_type_node, INT (0), INT (255)));
5059 :
5060 : // (unsigned char)[-350,15] => [0,255].
5061 4 : r0 = int_range<1> (integer_type_node, INT (-350), INT (15));
5062 4 : range_cast (r0, unsigned_char_type_node);
5063 4 : ASSERT_TRUE (r0 == (int_range<1>
5064 : (unsigned_char_type_node,
5065 : min_limit (unsigned_char_type_node),
5066 : max_limit (unsigned_char_type_node))));
5067 :
5068 : // Casting [-120,20] from signed char to unsigned short.
5069 : // => [0, 20][0xff88, 0xffff].
5070 4 : r0 = int_range<1> (signed_char_type_node, SCHAR (-120), SCHAR (20));
5071 4 : range_cast (r0, short_unsigned_type_node);
5072 4 : r1 = int_range<1> (short_unsigned_type_node, UINT16 (0), UINT16 (20));
5073 8 : r2 = int_range<1> (short_unsigned_type_node,
5074 12 : UINT16 (0xff88), UINT16 (0xffff));
5075 4 : r1.union_ (r2);
5076 4 : ASSERT_TRUE (r0 == r1);
5077 : // A truncating cast back to signed char will work because [-120, 20]
5078 : // is representable in signed char.
5079 4 : range_cast (r0, signed_char_type_node);
5080 4 : ASSERT_TRUE (r0 == int_range<1> (signed_char_type_node,
5081 : SCHAR (-120), SCHAR (20)));
5082 :
5083 : // unsigned char -> signed short
5084 : // (signed short)[(unsigned char)25, (unsigned char)250]
5085 : // => [(signed short)25, (signed short)250]
5086 4 : r0 = rold = int_range<1> (unsigned_char_type_node, UCHAR (25), UCHAR (250));
5087 4 : range_cast (r0, short_integer_type_node);
5088 4 : r1 = int_range<1> (short_integer_type_node, INT16 (25), INT16 (250));
5089 4 : ASSERT_TRUE (r0 == r1);
5090 4 : range_cast (r0, unsigned_char_type_node);
5091 4 : ASSERT_TRUE (r0 == rold);
5092 :
5093 : // Test casting a wider signed [-MIN,MAX] to a narrower unsigned.
5094 8 : r0 = int_range<1> (long_long_integer_type_node,
5095 4 : min_limit (long_long_integer_type_node),
5096 8 : max_limit (long_long_integer_type_node));
5097 4 : range_cast (r0, short_unsigned_type_node);
5098 8 : r1 = int_range<1> (short_unsigned_type_node,
5099 4 : min_limit (short_unsigned_type_node),
5100 8 : max_limit (short_unsigned_type_node));
5101 4 : ASSERT_TRUE (r0 == r1);
5102 :
5103 : // Casting NONZERO to a narrower type will wrap/overflow so
5104 : // it's just the entire range for the narrower type.
5105 : //
5106 : // "NOT 0 at signed 32-bits" ==> [-MIN_32,-1][1, +MAX_32]. This is
5107 : // is outside of the range of a smaller range, return the full
5108 : // smaller range.
5109 4 : if (TYPE_PRECISION (integer_type_node)
5110 4 : > TYPE_PRECISION (short_integer_type_node))
5111 : {
5112 4 : r0.set_nonzero (integer_type_node);
5113 4 : range_cast (r0, short_integer_type_node);
5114 8 : r1 = int_range<1> (short_integer_type_node,
5115 4 : min_limit (short_integer_type_node),
5116 8 : max_limit (short_integer_type_node));
5117 4 : ASSERT_TRUE (r0 == r1);
5118 : }
5119 :
5120 : // Casting NONZERO from a narrower signed to a wider signed.
5121 : //
5122 : // NONZERO signed 16-bits is [-MIN_16,-1][1, +MAX_16].
5123 : // Converting this to 32-bits signed is [-MIN_16,-1][1, +MAX_16].
5124 4 : r0.set_nonzero (short_integer_type_node);
5125 4 : range_cast (r0, integer_type_node);
5126 4 : r1 = int_range<1> (integer_type_node, INT (-32768), INT (-1));
5127 4 : r2 = int_range<1> (integer_type_node, INT (1), INT (32767));
5128 4 : r1.union_ (r2);
5129 4 : ASSERT_TRUE (r0 == r1);
5130 4 : }
5131 :
5132 : static void
5133 4 : range_op_lshift_tests ()
5134 : {
5135 : // Test that 0x808.... & 0x8.... still contains 0x8....
5136 : // for a large set of numbers.
5137 4 : {
5138 4 : int_range_max res;
5139 4 : tree big_type = long_long_unsigned_type_node;
5140 4 : unsigned big_prec = TYPE_PRECISION (big_type);
5141 : // big_num = 0x808,0000,0000,0000
5142 4 : wide_int big_num = wi::lshift (wi::uhwi (0x808, big_prec),
5143 8 : wi::uhwi (48, big_prec));
5144 8 : op_bitwise_and.fold_range (res, big_type,
5145 8 : int_range <1> (big_type),
5146 8 : int_range <1> (big_type, big_num, big_num));
5147 : // val = 0x8,0000,0000,0000
5148 4 : wide_int val = wi::lshift (wi::uhwi (8, big_prec),
5149 8 : wi::uhwi (48, big_prec));
5150 4 : ASSERT_TRUE (res.contains_p (val));
5151 4 : }
5152 :
5153 4 : if (TYPE_PRECISION (unsigned_type_node) > 31)
5154 : {
5155 : // unsigned VARYING = op1 << 1 should be VARYING.
5156 4 : int_range<2> lhs (unsigned_type_node);
5157 4 : int_range<2> shift (unsigned_type_node, INT (1), INT (1));
5158 4 : int_range_max op1;
5159 4 : op_lshift.op1_range (op1, unsigned_type_node, lhs, shift);
5160 4 : ASSERT_TRUE (op1.varying_p ());
5161 :
5162 : // 0 = op1 << 1 should be [0,0], [0x8000000, 0x8000000].
5163 4 : int_range<2> zero (unsigned_type_node, UINT (0), UINT (0));
5164 4 : op_lshift.op1_range (op1, unsigned_type_node, zero, shift);
5165 4 : ASSERT_TRUE (op1.num_pairs () == 2);
5166 : // Remove the [0,0] range.
5167 4 : op1.intersect (zero);
5168 4 : ASSERT_TRUE (op1.num_pairs () == 1);
5169 : // op1 << 1 should be [0x8000,0x8000] << 1,
5170 : // which should result in [0,0].
5171 4 : int_range_max result;
5172 4 : op_lshift.fold_range (result, unsigned_type_node, op1, shift);
5173 4 : ASSERT_TRUE (result == zero);
5174 4 : }
5175 : // signed VARYING = op1 << 1 should be VARYING.
5176 4 : if (TYPE_PRECISION (integer_type_node) > 31)
5177 : {
5178 : // unsigned VARYING = op1 << 1 should be VARYING.
5179 4 : int_range<2> lhs (integer_type_node);
5180 4 : int_range<2> shift (integer_type_node, INT (1), INT (1));
5181 4 : int_range_max op1;
5182 4 : op_lshift.op1_range (op1, integer_type_node, lhs, shift);
5183 4 : ASSERT_TRUE (op1.varying_p ());
5184 :
5185 : // 0 = op1 << 1 should be [0,0], [0x8000000, 0x8000000].
5186 4 : int_range<2> zero (integer_type_node, INT (0), INT (0));
5187 4 : op_lshift.op1_range (op1, integer_type_node, zero, shift);
5188 4 : ASSERT_TRUE (op1.num_pairs () == 2);
5189 : // Remove the [0,0] range.
5190 4 : op1.intersect (zero);
5191 4 : ASSERT_TRUE (op1.num_pairs () == 1);
5192 : // op1 << 1 should be [0x8000,0x8000] << 1,
5193 : // which should result in [0,0].
5194 4 : int_range_max result;
5195 4 : op_lshift.fold_range (result, unsigned_type_node, op1, shift);
5196 4 : ASSERT_TRUE (result == zero);
5197 4 : }
5198 4 : }
5199 :
5200 : static void
5201 4 : range_op_rshift_tests ()
5202 : {
5203 : // unsigned: [3, MAX] = OP1 >> 1
5204 4 : {
5205 4 : int_range_max lhs (unsigned_type_node,
5206 4 : UINT (3), max_limit (unsigned_type_node));
5207 4 : int_range_max one (unsigned_type_node,
5208 8 : wi::one (TYPE_PRECISION (unsigned_type_node)),
5209 8 : wi::one (TYPE_PRECISION (unsigned_type_node)));
5210 4 : int_range_max op1;
5211 4 : op_rshift.op1_range (op1, unsigned_type_node, lhs, one);
5212 4 : ASSERT_FALSE (op1.contains_p (UINT (3)));
5213 4 : }
5214 :
5215 : // signed: [3, MAX] = OP1 >> 1
5216 4 : {
5217 4 : int_range_max lhs (integer_type_node,
5218 4 : INT (3), max_limit (integer_type_node));
5219 4 : int_range_max one (integer_type_node, INT (1), INT (1));
5220 4 : int_range_max op1;
5221 4 : op_rshift.op1_range (op1, integer_type_node, lhs, one);
5222 4 : ASSERT_FALSE (op1.contains_p (INT (-2)));
5223 4 : }
5224 :
5225 : // This is impossible, so OP1 should be [].
5226 : // signed: [MIN, MIN] = OP1 >> 1
5227 4 : {
5228 4 : int_range_max lhs (integer_type_node,
5229 4 : min_limit (integer_type_node),
5230 4 : min_limit (integer_type_node));
5231 4 : int_range_max one (integer_type_node, INT (1), INT (1));
5232 4 : int_range_max op1;
5233 4 : op_rshift.op1_range (op1, integer_type_node, lhs, one);
5234 4 : ASSERT_TRUE (op1.undefined_p ());
5235 4 : }
5236 :
5237 : // signed: ~[-1] = OP1 >> 31
5238 4 : if (TYPE_PRECISION (integer_type_node) > 31)
5239 : {
5240 4 : int_range_max lhs (integer_type_node, INT (-1), INT (-1), VR_ANTI_RANGE);
5241 4 : int_range_max shift (integer_type_node, INT (31), INT (31));
5242 4 : int_range_max op1;
5243 4 : op_rshift.op1_range (op1, integer_type_node, lhs, shift);
5244 4 : int_range_max negatives = range_negatives (integer_type_node);
5245 4 : negatives.intersect (op1);
5246 4 : ASSERT_TRUE (negatives.undefined_p ());
5247 4 : }
5248 4 : }
5249 :
5250 : static void
5251 4 : range_op_bitwise_and_tests ()
5252 : {
5253 4 : int_range_max res;
5254 4 : wide_int min = min_limit (integer_type_node);
5255 4 : wide_int max = max_limit (integer_type_node);
5256 4 : wide_int tiny = wi::add (min, wi::one (TYPE_PRECISION (integer_type_node)));
5257 4 : int_range_max i1 (integer_type_node, tiny, max);
5258 4 : int_range_max i2 (integer_type_node, INT (255), INT (255));
5259 :
5260 : // [MIN+1, MAX] = OP1 & 255: OP1 is VARYING
5261 4 : op_bitwise_and.op1_range (res, integer_type_node, i1, i2);
5262 4 : ASSERT_TRUE (res == int_range<1> (integer_type_node));
5263 :
5264 : // VARYING = OP1 & 255: OP1 is VARYING
5265 4 : i1 = int_range<1> (integer_type_node);
5266 4 : op_bitwise_and.op1_range (res, integer_type_node, i1, i2);
5267 4 : ASSERT_TRUE (res == int_range<1> (integer_type_node));
5268 :
5269 : // For 0 = x & MASK, x is ~MASK.
5270 4 : {
5271 4 : int_range<2> zero (integer_type_node, INT (0), INT (0));
5272 4 : int_range<2> mask = int_range<2> (integer_type_node, INT (7), INT (7));
5273 4 : op_bitwise_and.op1_range (res, integer_type_node, zero, mask);
5274 4 : wide_int inv = wi::shwi (~7U, TYPE_PRECISION (integer_type_node));
5275 4 : ASSERT_TRUE (res.get_nonzero_bits () == inv);
5276 4 : }
5277 :
5278 : // (NONZERO | X) is nonzero.
5279 4 : i1.set_nonzero (integer_type_node);
5280 4 : i2.set_varying (integer_type_node);
5281 4 : op_bitwise_or.fold_range (res, integer_type_node, i1, i2);
5282 4 : ASSERT_TRUE (res.nonzero_p ());
5283 :
5284 : // (NEGATIVE | X) is nonzero.
5285 4 : i1 = int_range<1> (integer_type_node, INT (-5), INT (-3));
5286 4 : i2.set_varying (integer_type_node);
5287 4 : op_bitwise_or.fold_range (res, integer_type_node, i1, i2);
5288 4 : ASSERT_FALSE (res.contains_p (INT (0)));
5289 4 : }
5290 :
5291 : static void
5292 4 : range_relational_tests ()
5293 : {
5294 4 : int_range<2> lhs (unsigned_char_type_node);
5295 4 : int_range<2> op1 (unsigned_char_type_node, UCHAR (8), UCHAR (10));
5296 4 : int_range<2> op2 (unsigned_char_type_node, UCHAR (20), UCHAR (20));
5297 :
5298 : // Never wrapping additions mean LHS > OP1.
5299 4 : relation_kind code = op_plus.lhs_op1_relation (lhs, op1, op2, VREL_VARYING);
5300 4 : ASSERT_TRUE (code == VREL_GT);
5301 :
5302 : // Most wrapping additions mean nothing...
5303 4 : op1 = int_range<2> (unsigned_char_type_node, UCHAR (8), UCHAR (10));
5304 4 : op2 = int_range<2> (unsigned_char_type_node, UCHAR (0), UCHAR (255));
5305 4 : code = op_plus.lhs_op1_relation (lhs, op1, op2, VREL_VARYING);
5306 4 : ASSERT_TRUE (code == VREL_VARYING);
5307 :
5308 : // However, always wrapping additions mean LHS < OP1.
5309 4 : op1 = int_range<2> (unsigned_char_type_node, UCHAR (1), UCHAR (255));
5310 4 : op2 = int_range<2> (unsigned_char_type_node, UCHAR (255), UCHAR (255));
5311 4 : code = op_plus.lhs_op1_relation (lhs, op1, op2, VREL_VARYING);
5312 4 : ASSERT_TRUE (code == VREL_LT);
5313 4 : }
5314 :
5315 : void
5316 4 : range_op_tests ()
5317 : {
5318 4 : range_op_rshift_tests ();
5319 4 : range_op_lshift_tests ();
5320 4 : range_op_bitwise_and_tests ();
5321 4 : range_op_cast_tests ();
5322 4 : range_relational_tests ();
5323 :
5324 4 : extern void range_op_float_tests ();
5325 4 : range_op_float_tests ();
5326 4 : }
5327 :
5328 : } // namespace selftest
5329 :
5330 : #endif // CHECKING_P
|
