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 293366 : range_op_table::range_op_table ()
83 : {
84 293366 : initialize_integral_ops ();
85 293366 : initialize_pointer_ops ();
86 293366 : initialize_float_ops ();
87 :
88 293366 : set (EQ_EXPR, op_equal);
89 293366 : set (NE_EXPR, op_not_equal);
90 293366 : set (LT_EXPR, op_lt);
91 293366 : set (LE_EXPR, op_le);
92 293366 : set (GT_EXPR, op_gt);
93 293366 : set (GE_EXPR, op_ge);
94 293366 : set (SSA_NAME, op_ident);
95 293366 : set (PAREN_EXPR, op_ident);
96 293366 : set (OBJ_TYPE_REF, op_ident);
97 293366 : set (REAL_CST, op_cst);
98 293366 : set (INTEGER_CST, op_cst);
99 293366 : set (NOP_EXPR, op_cast);
100 293366 : set (CONVERT_EXPR, op_cast);
101 293366 : set (VIEW_CONVERT_EXPR, op_view);
102 293366 : set (FLOAT_EXPR, op_cast);
103 293366 : set (FIX_TRUNC_EXPR, op_cast);
104 293366 : set (PLUS_EXPR, op_plus);
105 293366 : set (ABS_EXPR, op_abs);
106 293366 : set (MINUS_EXPR, op_minus);
107 293366 : set (NEGATE_EXPR, op_negate);
108 293366 : set (MULT_EXPR, op_mult);
109 293366 : set (ADDR_EXPR, op_addr);
110 293366 : set (BIT_NOT_EXPR, op_bitwise_not);
111 293366 : set (BIT_XOR_EXPR, op_bitwise_xor);
112 293366 : set (BIT_AND_EXPR, op_bitwise_and);
113 293366 : set (BIT_IOR_EXPR, op_bitwise_or);
114 293366 : set (MIN_EXPR, op_min);
115 293366 : set (MAX_EXPR, op_max);
116 293366 : }
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 2108006605 : range_op_handler::range_op_handler ()
125 : {
126 2108006605 : m_operator = &default_operator;
127 2108006605 : }
128 :
129 : // Create a range_op_handler for CODE. Use a default operator if CODE
130 : // does not have an entry.
131 :
132 5118639196 : range_op_handler::range_op_handler (unsigned code)
133 : {
134 5118639196 : m_operator = operator_table[code];
135 5118639196 : if (!m_operator)
136 969365545 : m_operator = &default_operator;
137 5118639196 : }
138 :
139 : // Return TRUE if this handler has a non-default operator.
140 :
141 7375765755 : range_op_handler::operator bool () const
142 : {
143 7375765755 : 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 1246597246 : range_op_handler::range_op () const
152 : {
153 1246597246 : if (m_operator != &default_operator)
154 1246597246 : 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 752706671 : dispatch_trio (unsigned lhs, unsigned op1, unsigned op2)
164 : {
165 752706671 : 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 752706671 : range_op_handler::dispatch_kind (const vrange &lhs, const vrange &op1,
191 : const vrange& op2) const
192 : {
193 752706671 : return dispatch_trio (lhs.m_discriminator, op1.m_discriminator,
194 752706671 : 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 323178347 : range_op_handler::fold_range (vrange &r, tree type,
224 : const vrange &lh,
225 : const vrange &rh,
226 : relation_trio rel) const
227 : {
228 323178347 : gcc_checking_assert (m_operator);
229 : #if CHECKING_P
230 323178347 : if (!lh.undefined_p () && !rh.undefined_p ())
231 316776030 : gcc_assert (m_operator->operand_check_p (type, lh.type (), rh.type ()));
232 : #endif
233 323178347 : switch (dispatch_kind (r, lh, rh))
234 : {
235 247895749 : case RO_III:
236 247895749 : return m_operator->fold_range (as_a <irange> (r), type,
237 : as_a <irange> (lh),
238 247895749 : as_a <irange> (rh), rel);
239 373264 : case RO_IFI:
240 373264 : return m_operator->fold_range (as_a <irange> (r), type,
241 : as_a <frange> (lh),
242 373264 : as_a <irange> (rh), rel);
243 2692430 : case RO_IFF:
244 2692430 : return m_operator->fold_range (as_a <irange> (r), type,
245 : as_a <frange> (lh),
246 2692430 : as_a <frange> (rh), rel);
247 7479148 : case RO_FFF:
248 7479148 : return m_operator->fold_range (as_a <frange> (r), type,
249 : as_a <frange> (lh),
250 7479148 : 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 946964 : case RO_FIF:
256 946964 : return m_operator->fold_range (as_a <frange> (r), type,
257 : as_a <irange> (lh),
258 946964 : as_a <frange> (rh), rel);
259 20486608 : case RO_PPP:
260 20486608 : return m_operator->fold_range (as_a <prange> (r), type,
261 : as_a <prange> (lh),
262 20486608 : as_a <prange> (rh), rel);
263 9429512 : case RO_PPI:
264 9429512 : return m_operator->fold_range (as_a <prange> (r), type,
265 : as_a <prange> (lh),
266 9429512 : as_a <irange> (rh), rel);
267 19611041 : case RO_IPP:
268 19611041 : return m_operator->fold_range (as_a <irange> (r), type,
269 : as_a <prange> (lh),
270 19611041 : as_a <prange> (rh), rel);
271 1994849 : case RO_PIP:
272 1994849 : return m_operator->fold_range (as_a <prange> (r), type,
273 : as_a <irange> (lh),
274 1994849 : as_a <prange> (rh), rel);
275 12268752 : case RO_IPI:
276 12268752 : return m_operator->fold_range (as_a <irange> (r), type,
277 : as_a <prange> (lh),
278 12268752 : 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 116080258 : range_op_handler::op1_range (vrange &r, tree type,
288 : const vrange &lhs,
289 : const vrange &op2,
290 : relation_trio rel) const
291 : {
292 116080258 : gcc_checking_assert (m_operator);
293 116080258 : if (lhs.undefined_p ())
294 : return false;
295 : #if CHECKING_P
296 116079441 : if (!op2.undefined_p ())
297 116079263 : gcc_assert (m_operator->operand_check_p (lhs.type (), type, op2.type ()));
298 : #endif
299 116079441 : switch (dispatch_kind (r, lhs, op2))
300 : {
301 102254681 : case RO_III:
302 102254681 : return m_operator->op1_range (as_a <irange> (r), type,
303 : as_a <irange> (lhs),
304 102254681 : as_a <irange> (op2), rel);
305 248716 : case RO_IFI:
306 248716 : return m_operator->op1_range (as_a <irange> (r), type,
307 : as_a <frange> (lhs),
308 248716 : as_a <irange> (op2), rel);
309 898289 : case RO_PPP:
310 898289 : return m_operator->op1_range (as_a <prange> (r), type,
311 : as_a <prange> (lhs),
312 898289 : as_a <prange> (op2), rel);
313 9494711 : case RO_PIP:
314 9494711 : return m_operator->op1_range (as_a <prange> (r), type,
315 : as_a <irange> (lhs),
316 9494711 : as_a <prange> (op2), rel);
317 416465 : case RO_PPI:
318 416465 : return m_operator->op1_range (as_a <prange> (r), type,
319 : as_a <prange> (lhs),
320 416465 : as_a <irange> (op2), rel);
321 284026 : case RO_IPI:
322 284026 : return m_operator->op1_range (as_a <irange> (r), type,
323 : as_a <prange> (lhs),
324 284026 : as_a <irange> (op2), rel);
325 1519835 : case RO_FIF:
326 1519835 : return m_operator->op1_range (as_a <frange> (r), type,
327 : as_a <irange> (lhs),
328 1519835 : as_a <frange> (op2), rel);
329 962718 : case RO_FFF:
330 962718 : return m_operator->op1_range (as_a <frange> (r), type,
331 : as_a <frange> (lhs),
332 962718 : 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 33800334 : range_op_handler::op2_range (vrange &r, tree type,
342 : const vrange &lhs,
343 : const vrange &op1,
344 : relation_trio rel) const
345 : {
346 33800334 : gcc_checking_assert (m_operator);
347 33800334 : if (lhs.undefined_p ())
348 : return false;
349 : #if CHECKING_P
350 33800156 : if (!op1.undefined_p ())
351 33800041 : gcc_assert (m_operator->operand_check_p (lhs.type (), op1.type (), type));
352 : #endif
353 33800156 : switch (dispatch_kind (r, lhs, op1))
354 : {
355 27198016 : case RO_III:
356 27198016 : return m_operator->op2_range (as_a <irange> (r), type,
357 : as_a <irange> (lhs),
358 27198016 : as_a <irange> (op1), rel);
359 5367534 : case RO_PIP:
360 5367534 : return m_operator->op2_range (as_a <prange> (r), type,
361 : as_a <irange> (lhs),
362 5367534 : as_a <prange> (op1), rel);
363 333666 : case RO_IPP:
364 333666 : return m_operator->op2_range (as_a <irange> (r), type,
365 : as_a <prange> (lhs),
366 333666 : as_a <prange> (op1), rel);
367 526191 : case RO_FIF:
368 526191 : return m_operator->op2_range (as_a <frange> (r), type,
369 : as_a <irange> (lhs),
370 526191 : as_a <frange> (op1), rel);
371 374355 : case RO_FFF:
372 374355 : return m_operator->op2_range (as_a <frange> (r), type,
373 : as_a <frange> (lhs),
374 374355 : 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 133866626 : range_op_handler::lhs_op1_relation (const vrange &lhs,
384 : const vrange &op1,
385 : const vrange &op2,
386 : relation_kind rel) const
387 : {
388 133866626 : gcc_checking_assert (m_operator);
389 133866626 : switch (dispatch_kind (lhs, op1, op2))
390 : {
391 107445243 : case RO_III:
392 107445243 : return m_operator->lhs_op1_relation (as_a <irange> (lhs),
393 : as_a <irange> (op1),
394 107445243 : as_a <irange> (op2), rel);
395 2327200 : case RO_PPP:
396 2327200 : return m_operator->lhs_op1_relation (as_a <prange> (lhs),
397 : as_a <prange> (op1),
398 2327200 : as_a <prange> (op2), rel);
399 6820370 : case RO_IPP:
400 6820370 : return m_operator->lhs_op1_relation (as_a <irange> (lhs),
401 : as_a <prange> (op1),
402 6820370 : as_a <prange> (op2), rel);
403 1502902 : case RO_PII:
404 1502902 : return m_operator->lhs_op1_relation (as_a <prange> (lhs),
405 : as_a <irange> (op1),
406 1502902 : as_a <irange> (op2), rel);
407 8142797 : case RO_PPI:
408 8142797 : return m_operator->lhs_op1_relation (as_a <prange> (lhs),
409 : as_a <prange> (op1),
410 8142797 : as_a <irange> (op2), rel);
411 1072166 : case RO_IFF:
412 1072166 : return m_operator->lhs_op1_relation (as_a <irange> (lhs),
413 : as_a <frange> (op1),
414 1072166 : as_a <frange> (op2), rel);
415 5609502 : case RO_FFF:
416 5609502 : return m_operator->lhs_op1_relation (as_a <frange> (lhs),
417 : as_a <frange> (op1),
418 5609502 : 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 39084285 : range_op_handler::lhs_op2_relation (const vrange &lhs,
428 : const vrange &op1,
429 : const vrange &op2,
430 : relation_kind rel) const
431 : {
432 39084285 : gcc_checking_assert (m_operator);
433 39084285 : switch (dispatch_kind (lhs, op1, op2))
434 : {
435 27436257 : case RO_III:
436 27436257 : return m_operator->lhs_op2_relation (as_a <irange> (lhs),
437 : as_a <irange> (op1),
438 27436257 : as_a <irange> (op2), rel);
439 184546 : case RO_IFF:
440 184546 : return m_operator->lhs_op2_relation (as_a <irange> (lhs),
441 : as_a <frange> (op1),
442 184546 : as_a <frange> (op2), rel);
443 3337910 : case RO_FFF:
444 3337910 : return m_operator->lhs_op2_relation (as_a <frange> (lhs),
445 : as_a <frange> (op1),
446 3337910 : 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 106585618 : range_op_handler::op1_op2_relation (const vrange &lhs,
456 : const vrange &op1,
457 : const vrange &op2) const
458 : {
459 106585618 : gcc_checking_assert (m_operator);
460 :
461 106585618 : switch (dispatch_kind (lhs, op1, op2))
462 : {
463 84318595 : case RO_III:
464 84318595 : return m_operator->op1_op2_relation (as_a <irange> (lhs),
465 : as_a <irange> (op1),
466 84318595 : as_a <irange> (op2));
467 :
468 19208117 : case RO_IPP:
469 19208117 : return m_operator->op1_op2_relation (as_a <irange> (lhs),
470 : as_a <prange> (op1),
471 19208117 : as_a <prange> (op2));
472 :
473 1874029 : case RO_IFF:
474 1874029 : return m_operator->op1_op2_relation (as_a <irange> (lhs),
475 : as_a <frange> (op1),
476 1874029 : as_a <frange> (op2));
477 :
478 698304 : case RO_FFF:
479 698304 : return m_operator->op1_op2_relation (as_a <frange> (lhs),
480 : as_a <frange> (op1),
481 698304 : as_a <frange> (op2));
482 :
483 : default:
484 : return VREL_VARYING;
485 : }
486 : }
487 :
488 : bool
489 112198 : range_op_handler::overflow_free_p (const vrange &lh,
490 : const vrange &rh,
491 : relation_trio rel) const
492 : {
493 112198 : gcc_checking_assert (m_operator);
494 112198 : switch (dispatch_kind (lh, lh, rh))
495 : {
496 112198 : case RO_III:
497 112198 : return m_operator->overflow_free_p(as_a <irange> (lh),
498 : as_a <irange> (rh),
499 112198 : rel);
500 : default:
501 : return false;
502 : }
503 : }
504 :
505 : bool
506 10059894 : range_op_handler::operand_check_p (tree t1, tree t2, tree t3) const
507 : {
508 10059894 : gcc_checking_assert (m_operator);
509 10059894 : 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 198229687 : update_known_bitmask (vrange &r, tree_code code,
517 : const vrange &lh, const vrange &rh)
518 : {
519 198229687 : if (r.undefined_p () || lh.undefined_p () || rh.undefined_p ()
520 396453390 : || r.singleton_p ())
521 11670286 : return;
522 :
523 186559401 : widest_int widest_value, widest_mask;
524 186559401 : tree type = r.type ();
525 186559401 : signop sign = TYPE_SIGN (type);
526 186559401 : int prec = TYPE_PRECISION (type);
527 186559401 : irange_bitmask lh_bits = lh.get_bitmask ();
528 186559401 : irange_bitmask rh_bits = rh.get_bitmask ();
529 :
530 186559401 : switch (get_gimple_rhs_class (code))
531 : {
532 63833250 : case GIMPLE_UNARY_RHS:
533 63833250 : bit_value_unop (code, sign, prec, &widest_value, &widest_mask,
534 63833250 : TYPE_SIGN (lh.type ()),
535 63833250 : TYPE_PRECISION (lh.type ()),
536 127667019 : widest_int::from (lh_bits.value (),
537 63833250 : TYPE_SIGN (lh.type ())),
538 127666500 : widest_int::from (lh_bits.mask (),
539 63833250 : TYPE_SIGN (lh.type ())));
540 63833250 : break;
541 122726151 : case GIMPLE_BINARY_RHS:
542 245452302 : bit_value_binop (code, sign, prec, &widest_value, &widest_mask,
543 122726151 : TYPE_SIGN (lh.type ()),
544 122726151 : TYPE_PRECISION (lh.type ()),
545 245453808 : widest_int::from (lh_bits.value (), sign),
546 245453808 : widest_int::from (lh_bits.mask (), sign),
547 122726151 : TYPE_SIGN (rh.type ()),
548 122726151 : TYPE_PRECISION (rh.type ()),
549 245453775 : widest_int::from (rh_bits.value (), sign),
550 245452302 : widest_int::from (rh_bits.mask (), sign));
551 122726151 : break;
552 0 : default:
553 0 : gcc_unreachable ();
554 : }
555 :
556 186559401 : wide_int mask = wide_int::from (widest_mask, prec, sign);
557 373118802 : wide_int value = wide_int::from (widest_value, prec, sign);
558 : // Bitmasks must have the unknown value bits cleared.
559 186559401 : value &= ~mask;
560 373118802 : irange_bitmask bm (value, mask);
561 186559401 : r.update_bitmask (bm);
562 186560498 : }
563 :
564 : // Return the upper limit for a type.
565 :
566 : static inline wide_int
567 23066119 : max_limit (const_tree type)
568 : {
569 23066119 : return irange_val_max (type);
570 : }
571 :
572 : // Return the lower limit for a type.
573 :
574 : static inline wide_int
575 24702184 : min_limit (const_tree type)
576 : {
577 24702184 : 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 6272992 : get_shift_range (irange &r, tree type, const irange &op)
586 : {
587 6272992 : if (op.undefined_p ())
588 : return false;
589 :
590 : // Build valid range and intersect it with the shift range.
591 6271844 : r.set (op.type (),
592 12543688 : wi::shwi (0, TYPE_PRECISION (op.type ())),
593 6271844 : wi::shwi (TYPE_PRECISION (type) - 1, TYPE_PRECISION (op.type ())));
594 6271844 : r.intersect (op);
595 :
596 : // If there are no valid ranges in the shift range, returned false.
597 6271844 : if (r.undefined_p ())
598 630 : 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 55374 : 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 55374 : int_range_max tmp;
629 110748 : widest_int lh_range = wi::sub (widest_int::from (lh_ub, TYPE_SIGN (type)),
630 110748 : widest_int::from (lh_lb, TYPE_SIGN (type)));
631 : // if there are 1 to 8 values in the LH range, split them up.
632 55374 : r.set_undefined ();
633 110748 : if (lh_range >= 0 && lh_range < limit)
634 : {
635 17533 : for (unsigned x = 0; x <= lh_range; x++)
636 : {
637 12481 : wide_int val = lh_lb + x;
638 12481 : wi_fold (tmp, type, val, val, val, val);
639 12481 : r.union_ (tmp);
640 12481 : }
641 : }
642 : // Otherwise just call wi_fold.
643 : else
644 50322 : wi_fold (r, type, lh_lb, lh_ub, lh_lb, lh_ub);
645 55374 : }
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 166334161 : 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 166334161 : int_range_max tmp;
659 332668322 : widest_int rh_range = wi::sub (widest_int::from (rh_ub, TYPE_SIGN (type)),
660 332668322 : widest_int::from (rh_lb, TYPE_SIGN (type)));
661 332668322 : widest_int lh_range = wi::sub (widest_int::from (lh_ub, TYPE_SIGN (type)),
662 332668322 : 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 166334161 : if (rh_range > 0 && rh_range < 4)
666 : {
667 5784261 : wi_fold_in_parts (r, type, lh_lb, lh_ub, rh_lb, rh_lb);
668 5784261 : if (rh_range > 1)
669 : {
670 809424 : wi_fold_in_parts (tmp, type, lh_lb, lh_ub, rh_lb + 1, rh_lb + 1);
671 809424 : r.union_ (tmp);
672 809424 : if (rh_range == 3)
673 : {
674 560606 : wi_fold_in_parts (tmp, type, lh_lb, lh_ub, rh_lb + 2, rh_lb + 2);
675 560606 : r.union_ (tmp);
676 : }
677 : }
678 5784261 : wi_fold_in_parts (tmp, type, lh_lb, lh_ub, rh_ub, rh_ub);
679 5784261 : 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 160549900 : else if (lh_range > 0 && lh_range < 4)
684 : {
685 10474994 : wi_fold (r, type, lh_lb, lh_lb, rh_lb, rh_ub);
686 10474994 : if (lh_range > 1)
687 : {
688 1868377 : wi_fold (tmp, type, lh_lb + 1, lh_lb + 1, rh_lb, rh_ub);
689 1868365 : r.union_ (tmp);
690 1868365 : if (lh_range == 3)
691 : {
692 787265 : wi_fold (tmp, type, lh_lb + 2, lh_lb + 2, rh_lb, rh_ub);
693 787259 : r.union_ (tmp);
694 : }
695 : }
696 10474994 : wi_fold (tmp, type, lh_ub, lh_ub, rh_lb, rh_ub);
697 10474994 : r.union_ (tmp);
698 : }
699 : // Otherwise just call wi_fold.
700 : else
701 150074906 : wi_fold (r, type, lh_lb, lh_ub, rh_lb, rh_ub);
702 166334733 : }
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 116728735 : range_operator::fold_range (irange &r, tree type,
709 : const irange &lh,
710 : const irange &rh,
711 : relation_trio trio) const
712 : {
713 116728735 : gcc_checking_assert (r.supports_type_p (type));
714 116728735 : if (empty_range_varying (r, type, lh, rh))
715 58403 : return true;
716 :
717 116670332 : relation_kind rel = trio.op1_op2 ();
718 116670332 : unsigned num_lh = lh.num_pairs ();
719 116670332 : 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 116670780 : if (relation_equiv_p (rel) && lh == rh)
724 : {
725 52807 : int_range_max tmp;
726 52807 : r.set_undefined ();
727 146567 : for (unsigned x = 0; x < num_lh; ++x)
728 : {
729 : // If the number of subranges is too high, limit subrange creation.
730 55374 : unsigned limit = (r.num_pairs () > 32) ? 0 : 8;
731 55374 : wide_int lh_lb = lh.lower_bound (x);
732 55374 : wide_int lh_ub = lh.upper_bound (x);
733 55374 : wi_fold_in_parts_equiv (tmp, type, lh_lb, lh_ub, limit);
734 55374 : r.union_ (tmp);
735 55374 : if (r.varying_p ())
736 : break;
737 55374 : }
738 52807 : op1_op2_relation_effect (r, type, lh, rh, rel);
739 52807 : update_bitmask (r, lh, rh);
740 52807 : return true;
741 52807 : }
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 116617525 : if ((num_lh == 1 && num_rh == 1) || num_lh * num_rh > 12)
747 : {
748 96881034 : wi_fold_in_parts (r, type, lh.lower_bound (), lh.upper_bound (),
749 193758468 : rh.lower_bound (), rh.upper_bound ());
750 96879234 : op1_op2_relation_effect (r, type, lh, rh, rel);
751 96879234 : update_bitmask (r, lh, rh);
752 96879234 : return true;
753 : }
754 :
755 19738291 : int_range_max tmp;
756 19738291 : r.set_undefined ();
757 80850609 : for (unsigned x = 0; x < num_lh; ++x)
758 97890402 : for (unsigned y = 0; y < num_rh; ++y)
759 : {
760 56516375 : wide_int lh_lb = lh.lower_bound (x);
761 56516375 : wide_int lh_ub = lh.upper_bound (x);
762 56516375 : wide_int rh_lb = rh.lower_bound (y);
763 56516375 : wide_int rh_ub = rh.upper_bound (y);
764 56516375 : wi_fold_in_parts (tmp, type, lh_lb, lh_ub, rh_lb, rh_ub);
765 56516375 : r.union_ (tmp);
766 56516375 : if (r.varying_p ())
767 : {
768 4807719 : op1_op2_relation_effect (r, type, lh, rh, rel);
769 4807719 : update_bitmask (r, lh, rh);
770 4807719 : return true;
771 : }
772 56520383 : }
773 14930572 : op1_op2_relation_effect (r, type, lh, rh, rel);
774 14930572 : update_bitmask (r, lh, rh);
775 14930572 : return true;
776 19738291 : }
777 :
778 :
779 : bool
780 69345 : range_operator::fold_range (frange &, tree, const irange &,
781 : const frange &, relation_trio) const
782 : {
783 69345 : return false;
784 : }
785 :
786 : bool
787 1823 : range_operator::op1_range (irange &, tree, const frange &,
788 : const irange &, relation_trio) const
789 : {
790 1823 : return false;
791 : }
792 :
793 :
794 :
795 : // The default for op1_range is to return false.
796 :
797 : bool
798 1220734 : 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 1220734 : return false;
805 : }
806 :
807 : // The default for op2_range is to return false.
808 :
809 : bool
810 691430 : 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 691430 : return false;
817 : }
818 :
819 : // The default relation routines return VREL_VARYING.
820 :
821 : relation_kind
822 21282081 : 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 21282081 : return VREL_VARYING;
828 : }
829 :
830 : relation_kind
831 18151462 : 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 18151462 : return VREL_VARYING;
837 : }
838 :
839 : relation_kind
840 20923909 : 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 20923909 : return VREL_VARYING;
845 : }
846 :
847 : // Default is no relation affects the LHS.
848 :
849 : bool
850 68543883 : 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 68543883 : 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 8034 : range_operator::update_bitmask (irange &, const irange &,
873 : const irange &) const
874 : {
875 8034 : }
876 :
877 : // Check that operand types are OK. Default to always OK.
878 :
879 : bool
880 141174016 : range_operator::operand_check_p (tree, tree, tree) const
881 : {
882 141174016 : 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 47229335 : value_range_from_overflowed_bounds (irange &r, tree type,
890 : const wide_int &wmin,
891 : const wide_int &wmax)
892 : {
893 47229335 : const signop sgn = TYPE_SIGN (type);
894 47229335 : const unsigned int prec = TYPE_PRECISION (type);
895 :
896 47229335 : wide_int tmin = wide_int::from (wmin, prec, sgn);
897 47229335 : wide_int tmax = wide_int::from (wmax, prec, sgn);
898 :
899 47229335 : bool covers = false;
900 47229335 : wide_int tem = tmin;
901 47229335 : tmin = tmax + 1;
902 47229335 : if (wi::cmp (tmin, tmax, sgn) < 0)
903 3942673 : covers = true;
904 47229335 : tmax = tem - 1;
905 47229335 : 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 44078134 : if (covers || wi::cmp (tmin, tmax, sgn) > 0)
912 31745974 : r.set_varying (type);
913 : else
914 15483361 : r.set (type, tmin, tmax, VR_ANTI_RANGE);
915 47230081 : }
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 161338003 : 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 161338003 : const signop sgn = TYPE_SIGN (type);
928 161338003 : const unsigned int prec = TYPE_PRECISION (type);
929 253106900 : 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 176374710 : if (prec == 1 && wi::ne_p (wmax, wmin))
934 : {
935 0 : r.set_varying (type);
936 0 : return;
937 : }
938 :
939 161338003 : if (overflow_wraps)
940 : {
941 : // If overflow wraps, truncate the values and adjust the range,
942 : // kind, and bounds appropriately.
943 91768897 : if ((min_ovf != wi::OVF_NONE) == (max_ovf != wi::OVF_NONE))
944 : {
945 63197443 : wide_int tmin = wide_int::from (wmin, prec, sgn);
946 63197443 : 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 63197443 : if (wi::gt_p (tmin, tmax, sgn))
950 592183 : r.set_varying (type);
951 : else
952 : // No overflow or both overflow or underflow. The range
953 : // kind stays normal.
954 62605260 : r.set (type, tmin, tmax);
955 63197443 : return;
956 63197661 : }
957 :
958 28571454 : if ((min_ovf == wi::OVF_UNDERFLOW && max_ovf == wi::OVF_NONE)
959 18361504 : || (max_ovf == wi::OVF_OVERFLOW && min_ovf == wi::OVF_NONE))
960 28571454 : 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 69569106 : if ((min_ovf == wi::OVF_OVERFLOW && max_ovf == wi::OVF_OVERFLOW)
970 69566487 : || (min_ovf == wi::OVF_UNDERFLOW && max_ovf == wi::OVF_UNDERFLOW))
971 : {
972 5081 : r.set_undefined ();
973 5081 : return;
974 : }
975 :
976 : // If overflow does not wrap, saturate to [MIN, MAX].
977 69564025 : wide_int new_lb, new_ub;
978 69564025 : if (min_ovf == wi::OVF_UNDERFLOW)
979 9435600 : new_lb = wi::min_value (prec, sgn);
980 60128752 : else if (min_ovf == wi::OVF_OVERFLOW)
981 0 : new_lb = wi::max_value (prec, sgn);
982 : else
983 60128752 : new_lb = wmin;
984 :
985 69564025 : if (max_ovf == wi::OVF_UNDERFLOW)
986 0 : new_ub = wi::min_value (prec, sgn);
987 69564025 : else if (max_ovf == wi::OVF_OVERFLOW)
988 14172487 : new_ub = wi::max_value (prec, sgn);
989 : else
990 55391913 : new_ub = wmax;
991 :
992 69564025 : r.set (type, new_lb, new_ub);
993 69565684 : }
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 98976129 : create_possibly_reversed_range (irange &r, tree type,
1002 : const wide_int &new_lb, const wide_int &new_ub)
1003 : {
1004 98976129 : signop s = TYPE_SIGN (type);
1005 : // If the bounds are swapped, treat the result as if an overflow occurred.
1006 98976129 : if (wi::gt_p (new_lb, new_ub, s))
1007 18657881 : value_range_from_overflowed_bounds (r, type, new_lb, new_ub);
1008 : else
1009 : // Otherwise it's just a normal range.
1010 80318248 : r.set (type, new_lb, new_ub);
1011 98976129 : }
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 101923899 : get_bool_state (vrange &r, const vrange &lhs, tree val_type)
1018 : {
1019 : // If there is no result, then this is unexecutable.
1020 101923899 : if (lhs.undefined_p ())
1021 : {
1022 0 : r.set_undefined ();
1023 0 : return BRS_EMPTY;
1024 : }
1025 :
1026 101923899 : 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 50871957 : if (lhs.contains_p (build_zero_cst (lhs.type ())))
1032 : {
1033 249042 : r.set_varying (val_type);
1034 249042 : 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 6965872 : operator_equal::op1_op2_relation (const irange &lhs, const irange &,
1053 : const irange &) const
1054 : {
1055 6965872 : if (lhs.undefined_p ())
1056 : return VREL_UNDEFINED;
1057 :
1058 : // FALSE = op1 == op2 indicates NE_EXPR.
1059 6965872 : if (lhs.zero_p ())
1060 : return VREL_NE;
1061 :
1062 : // TRUE = op1 == op2 indicates EQ_EXPR.
1063 3784044 : if (!lhs.contains_zero_p ())
1064 3756497 : return VREL_EQ;
1065 : return VREL_VARYING;
1066 : }
1067 :
1068 : bool
1069 18805379 : operator_equal::fold_range (irange &r, tree type,
1070 : const irange &op1,
1071 : const irange &op2,
1072 : relation_trio rel) const
1073 : {
1074 18805379 : 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 18760898 : bool op1_const = wi::eq_p (op1.lower_bound (), op1.upper_bound ());
1080 18760898 : bool op2_const = wi::eq_p (op2.lower_bound (), op2.upper_bound ());
1081 18760884 : if (op1_const && op2_const)
1082 : {
1083 462578 : if (wi::eq_p (op1.lower_bound (), op2.upper_bound()))
1084 190443 : r = range_true (type);
1085 : else
1086 272135 : 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 18298306 : int_range_max tmp = op1;
1093 18298306 : tmp.intersect (op2);
1094 18298306 : if (tmp.undefined_p ())
1095 273249 : r = range_false (type);
1096 : // Check if a constant cannot satisfy the bitmask requirements.
1097 33552548 : else if (op2_const && !op1.get_bitmask ().member_p (op2.lower_bound ()))
1098 0 : r = range_false (type);
1099 18111043 : else if (op1_const && !op2.get_bitmask ().member_p (op1.lower_bound ()))
1100 0 : r = range_false (type);
1101 : else
1102 18025057 : r = range_true_and_false (type);
1103 18298306 : }
1104 : return true;
1105 : }
1106 :
1107 : bool
1108 14216789 : operator_equal::op1_range (irange &r, tree type,
1109 : const irange &lhs,
1110 : const irange &op2,
1111 : relation_trio) const
1112 : {
1113 14216789 : switch (get_bool_state (r, lhs, type))
1114 : {
1115 4853504 : case BRS_TRUE:
1116 : // If it's true, the result is the same as OP2.
1117 4853504 : r = op2;
1118 4853504 : break;
1119 :
1120 9331083 : case BRS_FALSE:
1121 : // If the result is false, the only time we know anything is
1122 : // if OP2 is a constant.
1123 9331083 : if (!op2.undefined_p ()
1124 27993249 : && wi::eq_p (op2.lower_bound(), op2.upper_bound()))
1125 : {
1126 7380009 : r = op2;
1127 7380009 : if (!r.invert ())
1128 : return false;
1129 : }
1130 : else
1131 1951074 : r.set_varying (type);
1132 : break;
1133 :
1134 : default:
1135 : break;
1136 : }
1137 : return true;
1138 : }
1139 :
1140 : bool
1141 1926232 : operator_equal::op2_range (irange &r, tree type,
1142 : const irange &lhs,
1143 : const irange &op1,
1144 : relation_trio rel) const
1145 : {
1146 1926232 : return operator_equal::op1_range (r, type, lhs, op1, rel.swap_op1_op2 ());
1147 : }
1148 :
1149 : // -------------------------------------------------------------------------
1150 :
1151 : void
1152 0 : operator_not_equal::update_bitmask (irange &r, const irange &lh,
1153 : const irange &rh) const
1154 : {
1155 0 : update_known_bitmask (r, NE_EXPR, lh, rh);
1156 0 : }
1157 :
1158 : // Check if the LHS range indicates a relation between OP1 and OP2.
1159 :
1160 : relation_kind
1161 12105768 : operator_not_equal::op1_op2_relation (const irange &lhs, const irange &,
1162 : const irange &) const
1163 : {
1164 12105768 : if (lhs.undefined_p ())
1165 : return VREL_UNDEFINED;
1166 :
1167 : // FALSE = op1 != op2 indicates EQ_EXPR.
1168 12105768 : if (lhs.zero_p ())
1169 : return VREL_EQ;
1170 :
1171 : // TRUE = op1 != op2 indicates NE_EXPR.
1172 5674132 : if (!lhs.contains_zero_p ())
1173 5623891 : return VREL_NE;
1174 : return VREL_VARYING;
1175 : }
1176 :
1177 : bool
1178 28576702 : operator_not_equal::fold_range (irange &r, tree type,
1179 : const irange &op1,
1180 : const irange &op2,
1181 : relation_trio rel) const
1182 : {
1183 28576702 : if (relop_early_resolve (r, type, op1, op2, rel, VREL_NE))
1184 : return true;
1185 :
1186 : // We can be sure the values are always equal or not if both ranges
1187 : // consist of a single value, and then compare them.
1188 28553977 : bool op1_const = wi::eq_p (op1.lower_bound (), op1.upper_bound ());
1189 28553977 : bool op2_const = wi::eq_p (op2.lower_bound (), op2.upper_bound ());
1190 28553593 : if (op1_const && op2_const)
1191 : {
1192 2055043 : if (wi::ne_p (op1.lower_bound (), op2.upper_bound()))
1193 1376265 : r = range_true (type);
1194 : else
1195 678774 : r = range_false (type);
1196 : }
1197 : else
1198 : {
1199 : // If ranges do not intersect, we know the range is not equal,
1200 : // otherwise we don't know anything for sure.
1201 26498554 : int_range_max tmp = op1;
1202 26498554 : tmp.intersect (op2);
1203 26498554 : if (tmp.undefined_p ())
1204 334358 : r = range_true (type);
1205 : // Check if a constant cannot satisfy the bitmask requirements.
1206 47492235 : else if (op2_const && !op1.get_bitmask ().member_p (op2.lower_bound ()))
1207 0 : r = range_true (type);
1208 26311411 : else if (op1_const && !op2.get_bitmask ().member_p (op1.lower_bound ()))
1209 0 : r = range_true (type);
1210 : else
1211 26164196 : r = range_true_and_false (type);
1212 26498554 : }
1213 : return true;
1214 : }
1215 :
1216 : bool
1217 24527359 : operator_not_equal::op1_range (irange &r, tree type,
1218 : const irange &lhs,
1219 : const irange &op2,
1220 : relation_trio) const
1221 : {
1222 24527359 : switch (get_bool_state (r, lhs, type))
1223 : {
1224 14638566 : case BRS_TRUE:
1225 : // If the result is true, the only time we know anything is if
1226 : // OP2 is a constant.
1227 14638566 : if (!op2.undefined_p ()
1228 43915698 : && wi::eq_p (op2.lower_bound(), op2.upper_bound()))
1229 : {
1230 11687156 : r = op2;
1231 11687156 : if (!r.invert ())
1232 : return false;
1233 : }
1234 : else
1235 2951410 : r.set_varying (type);
1236 : break;
1237 :
1238 9837917 : case BRS_FALSE:
1239 : // If it's false, the result is the same as OP2.
1240 9837917 : r = op2;
1241 9837917 : break;
1242 :
1243 : default:
1244 : break;
1245 : }
1246 : return true;
1247 : }
1248 :
1249 :
1250 : bool
1251 3418027 : operator_not_equal::op2_range (irange &r, tree type,
1252 : const irange &lhs,
1253 : const irange &op1,
1254 : relation_trio rel) const
1255 : {
1256 3418027 : return operator_not_equal::op1_range (r, type, lhs, op1, rel.swap_op1_op2 ());
1257 : }
1258 :
1259 : // (X < VAL) produces the range of [MIN, VAL - 1].
1260 :
1261 : static void
1262 7834891 : build_lt (irange &r, tree type, const wide_int &val)
1263 : {
1264 7834891 : wi::overflow_type ov;
1265 7834891 : wide_int lim;
1266 7834891 : signop sgn = TYPE_SIGN (type);
1267 :
1268 : // Signed 1 bit cannot represent 1 for subtraction.
1269 7834891 : if (sgn == SIGNED)
1270 5164369 : lim = wi::add (val, -1, sgn, &ov);
1271 : else
1272 2670596 : lim = wi::sub (val, 1, sgn, &ov);
1273 :
1274 : // If val - 1 underflows, check if X < MIN, which is an empty range.
1275 7834891 : if (ov)
1276 245 : r.set_undefined ();
1277 : else
1278 7834720 : r = int_range<1> (type, min_limit (type), lim);
1279 7834891 : }
1280 :
1281 : // (X <= VAL) produces the range of [MIN, VAL].
1282 :
1283 : static void
1284 16867510 : build_le (irange &r, tree type, const wide_int &val)
1285 : {
1286 16867510 : r = int_range<1> (type, min_limit (type), val);
1287 16867510 : }
1288 :
1289 : // (X > VAL) produces the range of [VAL + 1, MAX].
1290 :
1291 : static void
1292 14113835 : build_gt (irange &r, tree type, const wide_int &val)
1293 : {
1294 14113835 : wi::overflow_type ov;
1295 14113835 : wide_int lim;
1296 14113835 : signop sgn = TYPE_SIGN (type);
1297 :
1298 : // Signed 1 bit cannot represent 1 for addition.
1299 14113835 : if (sgn == SIGNED)
1300 7446618 : lim = wi::sub (val, -1, sgn, &ov);
1301 : else
1302 6667380 : lim = wi::add (val, 1, sgn, &ov);
1303 : // If val + 1 overflows, check is for X > MAX, which is an empty range.
1304 14113835 : if (ov)
1305 4 : r.set_undefined ();
1306 : else
1307 14113994 : r = int_range<1> (type, lim, max_limit (type));
1308 14113835 : }
1309 :
1310 : // (X >= val) produces the range of [VAL, MAX].
1311 :
1312 : static void
1313 8952260 : build_ge (irange &r, tree type, const wide_int &val)
1314 : {
1315 8952260 : r = int_range<1> (type, val, max_limit (type));
1316 8952260 : }
1317 :
1318 :
1319 : void
1320 0 : operator_lt::update_bitmask (irange &r, const irange &lh,
1321 : const irange &rh) const
1322 : {
1323 0 : update_known_bitmask (r, LT_EXPR, lh, rh);
1324 0 : }
1325 :
1326 : // Check if the LHS range indicates a relation between OP1 and OP2.
1327 :
1328 : relation_kind
1329 14398793 : operator_lt::op1_op2_relation (const irange &lhs, const irange &,
1330 : const irange &) const
1331 : {
1332 14398793 : if (lhs.undefined_p ())
1333 : return VREL_UNDEFINED;
1334 :
1335 : // FALSE = op1 < op2 indicates GE_EXPR.
1336 14398793 : if (lhs.zero_p ())
1337 : return VREL_GE;
1338 :
1339 : // TRUE = op1 < op2 indicates LT_EXPR.
1340 7349176 : if (!lhs.contains_zero_p ())
1341 7336119 : return VREL_LT;
1342 : return VREL_VARYING;
1343 : }
1344 :
1345 : bool
1346 6946229 : operator_lt::fold_range (irange &r, tree type,
1347 : const irange &op1,
1348 : const irange &op2,
1349 : relation_trio rel) const
1350 : {
1351 6946229 : if (relop_early_resolve (r, type, op1, op2, rel, VREL_LT))
1352 : return true;
1353 :
1354 6904416 : signop sign = TYPE_SIGN (op1.type ());
1355 6904416 : gcc_checking_assert (sign == TYPE_SIGN (op2.type ()));
1356 :
1357 6904452 : if (wi::lt_p (op1.upper_bound (), op2.lower_bound (), sign))
1358 51544 : r = range_true (type);
1359 6852908 : else if (!wi::lt_p (op1.lower_bound (), op2.upper_bound (), sign))
1360 87554 : r = range_false (type);
1361 : // Use nonzero bits to determine if < 0 is false.
1362 8840305 : else if (op2.zero_p () && !wi::neg_p (op1.get_nonzero_bits (), sign))
1363 0 : r = range_false (type);
1364 : else
1365 6765318 : r = range_true_and_false (type);
1366 : return true;
1367 : }
1368 :
1369 : bool
1370 7063293 : operator_lt::op1_range (irange &r, tree type,
1371 : const irange &lhs,
1372 : const irange &op2,
1373 : relation_trio) const
1374 : {
1375 7063293 : if (op2.undefined_p ())
1376 : return false;
1377 :
1378 7063293 : switch (get_bool_state (r, lhs, type))
1379 : {
1380 2953063 : case BRS_TRUE:
1381 2953063 : build_lt (r, type, op2.upper_bound ());
1382 2953063 : break;
1383 :
1384 4103579 : case BRS_FALSE:
1385 4103579 : build_ge (r, type, op2.lower_bound ());
1386 4103579 : break;
1387 :
1388 : default:
1389 : break;
1390 : }
1391 : return true;
1392 : }
1393 :
1394 : bool
1395 4917362 : operator_lt::op2_range (irange &r, tree type,
1396 : const irange &lhs,
1397 : const irange &op1,
1398 : relation_trio) const
1399 : {
1400 4917362 : if (op1.undefined_p ())
1401 : return false;
1402 :
1403 4917362 : switch (get_bool_state (r, lhs, type))
1404 : {
1405 2255728 : case BRS_TRUE:
1406 2255728 : build_gt (r, type, op1.lower_bound ());
1407 2255728 : break;
1408 :
1409 2655986 : case BRS_FALSE:
1410 2655986 : build_le (r, type, op1.upper_bound ());
1411 2655986 : break;
1412 :
1413 : default:
1414 : break;
1415 : }
1416 : return true;
1417 : }
1418 :
1419 :
1420 : void
1421 0 : operator_le::update_bitmask (irange &r, const irange &lh,
1422 : const irange &rh) const
1423 : {
1424 0 : update_known_bitmask (r, LE_EXPR, lh, rh);
1425 0 : }
1426 :
1427 : // Check if the LHS range indicates a relation between OP1 and OP2.
1428 :
1429 : relation_kind
1430 5342670 : operator_le::op1_op2_relation (const irange &lhs, const irange &,
1431 : const irange &) const
1432 : {
1433 5342670 : if (lhs.undefined_p ())
1434 : return VREL_UNDEFINED;
1435 :
1436 : // FALSE = op1 <= op2 indicates GT_EXPR.
1437 5342670 : if (lhs.zero_p ())
1438 : return VREL_GT;
1439 :
1440 : // TRUE = op1 <= op2 indicates LE_EXPR.
1441 3013694 : if (!lhs.contains_zero_p ())
1442 3001092 : return VREL_LE;
1443 : return VREL_VARYING;
1444 : }
1445 :
1446 : bool
1447 5667277 : operator_le::fold_range (irange &r, tree type,
1448 : const irange &op1,
1449 : const irange &op2,
1450 : relation_trio rel) const
1451 : {
1452 5667277 : if (relop_early_resolve (r, type, op1, op2, rel, VREL_LE))
1453 : return true;
1454 :
1455 5652428 : signop sign = TYPE_SIGN (op1.type ());
1456 5652428 : gcc_checking_assert (sign == TYPE_SIGN (op2.type ()));
1457 :
1458 5652432 : if (wi::le_p (op1.upper_bound (), op2.lower_bound (), sign))
1459 297426 : r = range_true (type);
1460 5355006 : else if (!wi::le_p (op1.lower_bound (), op2.upper_bound (), sign))
1461 60146 : r = range_false (type);
1462 : else
1463 5294856 : r = range_true_and_false (type);
1464 : return true;
1465 : }
1466 :
1467 : bool
1468 8251481 : operator_le::op1_range (irange &r, tree type,
1469 : const irange &lhs,
1470 : const irange &op2,
1471 : relation_trio) const
1472 : {
1473 8251481 : if (op2.undefined_p ())
1474 : return false;
1475 :
1476 8251481 : switch (get_bool_state (r, lhs, type))
1477 : {
1478 4001617 : case BRS_TRUE:
1479 4001617 : build_le (r, type, op2.upper_bound ());
1480 4001617 : break;
1481 :
1482 4234824 : case BRS_FALSE:
1483 4234824 : build_gt (r, type, op2.lower_bound ());
1484 4234824 : break;
1485 :
1486 : default:
1487 : break;
1488 : }
1489 : return true;
1490 : }
1491 :
1492 : bool
1493 1385361 : operator_le::op2_range (irange &r, tree type,
1494 : const irange &lhs,
1495 : const irange &op1,
1496 : relation_trio) const
1497 : {
1498 1385361 : if (op1.undefined_p ())
1499 : return false;
1500 :
1501 1385361 : switch (get_bool_state (r, lhs, type))
1502 : {
1503 642047 : case BRS_TRUE:
1504 642047 : build_ge (r, type, op1.lower_bound ());
1505 642047 : break;
1506 :
1507 738108 : case BRS_FALSE:
1508 738108 : build_lt (r, type, op1.upper_bound ());
1509 738108 : break;
1510 :
1511 : default:
1512 : break;
1513 : }
1514 : return true;
1515 : }
1516 :
1517 :
1518 : void
1519 0 : operator_gt::update_bitmask (irange &r, const irange &lh,
1520 : const irange &rh) const
1521 : {
1522 0 : update_known_bitmask (r, GT_EXPR, lh, rh);
1523 0 : }
1524 :
1525 : // Check if the LHS range indicates a relation between OP1 and OP2.
1526 :
1527 : relation_kind
1528 14567830 : operator_gt::op1_op2_relation (const irange &lhs, const irange &,
1529 : const irange &) const
1530 : {
1531 14567830 : if (lhs.undefined_p ())
1532 : return VREL_UNDEFINED;
1533 :
1534 : // FALSE = op1 > op2 indicates LE_EXPR.
1535 14567830 : if (lhs.zero_p ())
1536 : return VREL_LE;
1537 :
1538 : // TRUE = op1 > op2 indicates GT_EXPR.
1539 7937893 : if (!lhs.contains_zero_p ())
1540 7889457 : return VREL_GT;
1541 : return VREL_VARYING;
1542 : }
1543 :
1544 : bool
1545 12565511 : operator_gt::fold_range (irange &r, tree type,
1546 : const irange &op1, const irange &op2,
1547 : relation_trio rel) const
1548 : {
1549 12565511 : if (relop_early_resolve (r, type, op1, op2, rel, VREL_GT))
1550 : return true;
1551 :
1552 12501793 : signop sign = TYPE_SIGN (op1.type ());
1553 12501793 : gcc_checking_assert (sign == TYPE_SIGN (op2.type ()));
1554 :
1555 12501819 : if (wi::gt_p (op1.lower_bound (), op2.upper_bound (), sign))
1556 145843 : r = range_true (type);
1557 12355976 : else if (!wi::gt_p (op1.upper_bound (), op2.lower_bound (), sign))
1558 514011 : r = range_false (type);
1559 : else
1560 11841939 : r = range_true_and_false (type);
1561 : return true;
1562 : }
1563 :
1564 : bool
1565 15997900 : operator_gt::op1_range (irange &r, tree type,
1566 : const irange &lhs, const irange &op2,
1567 : relation_trio) const
1568 : {
1569 15997900 : if (op2.undefined_p ())
1570 : return false;
1571 :
1572 15997900 : switch (get_bool_state (r, lhs, type))
1573 : {
1574 6738811 : case BRS_TRUE:
1575 6738811 : build_gt (r, type, op2.lower_bound ());
1576 6738811 : break;
1577 :
1578 9238807 : case BRS_FALSE:
1579 9238807 : build_le (r, type, op2.upper_bound ());
1580 9238807 : break;
1581 :
1582 : default:
1583 : break;
1584 : }
1585 : return true;
1586 : }
1587 :
1588 : bool
1589 4414471 : operator_gt::op2_range (irange &r, tree type,
1590 : const irange &lhs,
1591 : const irange &op1,
1592 : relation_trio) const
1593 : {
1594 4414471 : if (op1.undefined_p ())
1595 : return false;
1596 :
1597 4414471 : switch (get_bool_state (r, lhs, type))
1598 : {
1599 2630485 : case BRS_TRUE:
1600 2630485 : build_lt (r, type, op1.upper_bound ());
1601 2630485 : break;
1602 :
1603 1766273 : case BRS_FALSE:
1604 1766273 : build_ge (r, type, op1.lower_bound ());
1605 1766273 : break;
1606 :
1607 : default:
1608 : break;
1609 : }
1610 : return true;
1611 : }
1612 :
1613 :
1614 : void
1615 0 : operator_ge::update_bitmask (irange &r, const irange &lh,
1616 : const irange &rh) const
1617 : {
1618 0 : update_known_bitmask (r, GE_EXPR, lh, rh);
1619 0 : }
1620 :
1621 : // Check if the LHS range indicates a relation between OP1 and OP2.
1622 :
1623 : relation_kind
1624 5037106 : operator_ge::op1_op2_relation (const irange &lhs, const irange &,
1625 : const irange &) const
1626 : {
1627 5037106 : if (lhs.undefined_p ())
1628 : return VREL_UNDEFINED;
1629 :
1630 : // FALSE = op1 >= op2 indicates LT_EXPR.
1631 5037106 : if (lhs.zero_p ())
1632 : return VREL_LT;
1633 :
1634 : // TRUE = op1 >= op2 indicates GE_EXPR.
1635 2579357 : if (!lhs.contains_zero_p ())
1636 2565801 : return VREL_GE;
1637 : return VREL_VARYING;
1638 : }
1639 :
1640 : bool
1641 2851413 : operator_ge::fold_range (irange &r, tree type,
1642 : const irange &op1,
1643 : const irange &op2,
1644 : relation_trio rel) const
1645 : {
1646 2851413 : if (relop_early_resolve (r, type, op1, op2, rel, VREL_GE))
1647 : return true;
1648 :
1649 2838422 : signop sign = TYPE_SIGN (op1.type ());
1650 2838422 : gcc_checking_assert (sign == TYPE_SIGN (op2.type ()));
1651 :
1652 2838454 : if (wi::ge_p (op1.lower_bound (), op2.upper_bound (), sign))
1653 238431 : r = range_true (type);
1654 2600023 : else if (!wi::ge_p (op1.upper_bound (), op2.lower_bound (), sign))
1655 7142 : r = range_false (type);
1656 : else
1657 2592849 : r = range_true_and_false (type);
1658 : return true;
1659 : }
1660 :
1661 : bool
1662 3964138 : operator_ge::op1_range (irange &r, tree type,
1663 : const irange &lhs,
1664 : const irange &op2,
1665 : relation_trio) const
1666 : {
1667 3964138 : if (op2.undefined_p ())
1668 : return false;
1669 :
1670 3964138 : switch (get_bool_state (r, lhs, type))
1671 : {
1672 2440361 : case BRS_TRUE:
1673 2440361 : build_ge (r, type, op2.lower_bound ());
1674 2440361 : break;
1675 :
1676 1513235 : case BRS_FALSE:
1677 1513235 : build_lt (r, type, op2.upper_bound ());
1678 1513235 : break;
1679 :
1680 : default:
1681 : break;
1682 : }
1683 : return true;
1684 : }
1685 :
1686 : bool
1687 1862187 : operator_ge::op2_range (irange &r, tree type,
1688 : const irange &lhs,
1689 : const irange &op1,
1690 : relation_trio) const
1691 : {
1692 1862187 : if (op1.undefined_p ())
1693 : return false;
1694 :
1695 1862187 : switch (get_bool_state (r, lhs, type))
1696 : {
1697 971100 : case BRS_TRUE:
1698 971100 : build_le (r, type, op1.upper_bound ());
1699 971100 : break;
1700 :
1701 884472 : case BRS_FALSE:
1702 884472 : build_gt (r, type, op1.lower_bound ());
1703 884472 : break;
1704 :
1705 : default:
1706 : break;
1707 : }
1708 : return true;
1709 : }
1710 :
1711 :
1712 : void
1713 54173222 : operator_plus::update_bitmask (irange &r, const irange &lh,
1714 : const irange &rh) const
1715 : {
1716 54173222 : update_known_bitmask (r, PLUS_EXPR, lh, rh);
1717 54173222 : }
1718 :
1719 : // Check to see if the range of OP2 indicates anything about the relation
1720 : // between LHS and OP1.
1721 :
1722 : relation_kind
1723 48518822 : operator_plus::lhs_op1_relation (const irange &lhs,
1724 : const irange &op1,
1725 : const irange &op2,
1726 : relation_kind) const
1727 : {
1728 48518822 : if (lhs.undefined_p () || op1.undefined_p () || op2.undefined_p ())
1729 : return VREL_VARYING;
1730 :
1731 48482804 : tree type = lhs.type ();
1732 48482804 : unsigned prec = TYPE_PRECISION (type);
1733 48482804 : wi::overflow_type ovf1, ovf2;
1734 48482804 : signop sign = TYPE_SIGN (type);
1735 :
1736 : // LHS = OP1 + 0 indicates LHS == OP1.
1737 48482804 : if (op2.zero_p ())
1738 : return VREL_EQ;
1739 :
1740 48255778 : if (TYPE_OVERFLOW_WRAPS (type))
1741 : {
1742 27361912 : wi::add (op1.lower_bound (), op2.lower_bound (), sign, &ovf1);
1743 27362134 : wi::add (op1.upper_bound (), op2.upper_bound (), sign, &ovf2);
1744 : }
1745 : else
1746 20894310 : ovf1 = ovf2 = wi::OVF_NONE;
1747 :
1748 : // Never wrapping additions.
1749 48255778 : if (!ovf1 && !ovf2)
1750 : {
1751 : // Positive op2 means lhs > op1.
1752 28709180 : if (wi::gt_p (op2.lower_bound (), wi::zero (prec), sign))
1753 : return VREL_GT;
1754 10868256 : if (wi::ge_p (op2.lower_bound (), wi::zero (prec), sign))
1755 : return VREL_GE;
1756 :
1757 : // Negative op2 means lhs < op1.
1758 9145375 : if (wi::lt_p (op2.upper_bound (), wi::zero (prec), sign))
1759 : return VREL_LT;
1760 5565409 : if (wi::le_p (op2.upper_bound (), wi::zero (prec), sign))
1761 : return VREL_LE;
1762 : }
1763 : // Always wrapping additions.
1764 19546989 : else if (ovf1 && ovf1 == ovf2)
1765 : {
1766 : // Positive op2 means lhs < op1.
1767 749951 : if (wi::gt_p (op2.lower_bound (), wi::zero (prec), sign))
1768 : return VREL_LT;
1769 20 : if (wi::ge_p (op2.lower_bound (), wi::zero (prec), sign))
1770 : return VREL_LE;
1771 :
1772 : // Negative op2 means lhs > op1.
1773 20 : if (wi::lt_p (op2.upper_bound (), wi::zero (prec), sign))
1774 : return VREL_GT;
1775 0 : if (wi::le_p (op2.upper_bound (), wi::zero (prec), sign))
1776 : return VREL_GE;
1777 : }
1778 :
1779 : // If op2 does not contain 0, then LHS and OP1 can never be equal.
1780 24349113 : if (!range_includes_zero_p (op2))
1781 12208859 : return VREL_NE;
1782 :
1783 : return VREL_VARYING;
1784 : }
1785 :
1786 : // PLUS is symmetrical, so we can simply call lhs_op1_relation with reversed
1787 : // operands.
1788 :
1789 : relation_kind
1790 8598287 : operator_plus::lhs_op2_relation (const irange &lhs, const irange &op1,
1791 : const irange &op2, relation_kind rel) const
1792 : {
1793 8598287 : return lhs_op1_relation (lhs, op2, op1, rel);
1794 : }
1795 :
1796 : void
1797 81359439 : operator_plus::wi_fold (irange &r, tree type,
1798 : const wide_int &lh_lb, const wide_int &lh_ub,
1799 : const wide_int &rh_lb, const wide_int &rh_ub) const
1800 : {
1801 81359439 : wi::overflow_type ov_lb, ov_ub;
1802 81359439 : signop s = TYPE_SIGN (type);
1803 81359439 : wide_int new_lb = wi::add (lh_lb, rh_lb, s, &ov_lb);
1804 81359439 : wide_int new_ub = wi::add (lh_ub, rh_ub, s, &ov_ub);
1805 81359439 : value_range_with_overflow (r, type, new_lb, new_ub, ov_lb, ov_ub);
1806 81359439 : }
1807 :
1808 : // Given addition or subtraction, determine the possible NORMAL ranges and
1809 : // OVERFLOW ranges given an OFFSET range. ADD_P is true for addition.
1810 : // Return the relation that exists between the LHS and OP1 in order for the
1811 : // NORMAL range to apply.
1812 : // a return value of VREL_VARYING means no ranges were applicable.
1813 :
1814 : static relation_kind
1815 1605084 : plus_minus_ranges (irange &r_ov, irange &r_normal, const irange &offset,
1816 : bool add_p)
1817 : {
1818 1605084 : relation_kind kind = VREL_VARYING;
1819 : // For now, only deal with constant adds. This could be extended to ranges
1820 : // when someone is so motivated.
1821 1605084 : if (!offset.singleton_p () || offset.zero_p ())
1822 : return kind;
1823 :
1824 : // Always work with a positive offset. ie a+ -2 -> a-2 and a- -2 > a+2
1825 16953 : wide_int off = offset.lower_bound ();
1826 16953 : if (wi::neg_p (off, SIGNED))
1827 : {
1828 1341 : add_p = !add_p;
1829 1341 : off = wi::neg (off);
1830 : }
1831 :
1832 16953 : wi::overflow_type ov;
1833 16953 : tree type = offset.type ();
1834 16953 : unsigned prec = TYPE_PRECISION (type);
1835 16953 : wide_int ub;
1836 16953 : wide_int lb;
1837 : // calculate the normal range and relation for the operation.
1838 16953 : if (add_p)
1839 : {
1840 : // [ 0 , INF - OFF]
1841 15642 : lb = wi::zero (prec);
1842 15642 : ub = wi::sub (irange_val_max (type), off, UNSIGNED, &ov);
1843 15642 : kind = VREL_GT;
1844 : }
1845 : else
1846 : {
1847 : // [ OFF, INF ]
1848 1311 : lb = off;
1849 1311 : ub = irange_val_max (type);
1850 1311 : kind = VREL_LT;
1851 : }
1852 16953 : int_range<2> normal_range (type, lb, ub);
1853 16953 : int_range<2> ov_range (type, lb, ub, VR_ANTI_RANGE);
1854 :
1855 16953 : r_ov = ov_range;
1856 16953 : r_normal = normal_range;
1857 16953 : return kind;
1858 16953 : }
1859 :
1860 : // Once op1 has been calculated by operator_plus or operator_minus, check
1861 : // to see if the relation passed causes any part of the calculation to
1862 : // be not possible. ie
1863 : // a_2 = b_3 + 1 with a_2 < b_3 can refine the range of b_3 to [INF, INF]
1864 : // and that further refines a_2 to [0, 0].
1865 : // R is the value of op1, OP2 is the offset being added/subtracted, REL is the
1866 : // relation between LHS relation OP1 and ADD_P is true for PLUS, false for
1867 : // MINUS. IF any adjustment can be made, R will reflect it.
1868 :
1869 : static void
1870 15918320 : adjust_op1_for_overflow (irange &r, const irange &op2, relation_kind rel,
1871 : bool add_p)
1872 : {
1873 15918320 : if (r.undefined_p ())
1874 : return;
1875 15918316 : tree type = r.type ();
1876 : // Check for unsigned overflow and calculate the overflow part.
1877 15918316 : signop s = TYPE_SIGN (type);
1878 15918316 : if (!TYPE_OVERFLOW_WRAPS (type) || s == SIGNED)
1879 : return;
1880 :
1881 : // Only work with <, <=, >, >= relations.
1882 8348349 : if (!relation_lt_le_gt_ge_p (rel))
1883 : return;
1884 :
1885 : // Get the ranges for this offset.
1886 1605084 : int_range_max normal, overflow;
1887 1605084 : relation_kind k = plus_minus_ranges (overflow, normal, op2, add_p);
1888 :
1889 : // VREL_VARYING means there are no adjustments.
1890 1605084 : if (k == VREL_VARYING)
1891 : return;
1892 :
1893 : // If the relations match use the normal range, otherwise use overflow range.
1894 16953 : if (relation_intersect (k, rel) == k)
1895 12523 : r.intersect (normal);
1896 : else
1897 4430 : r.intersect (overflow);
1898 : return;
1899 1605084 : }
1900 :
1901 : bool
1902 14453604 : operator_plus::op1_range (irange &r, tree type,
1903 : const irange &lhs,
1904 : const irange &op2,
1905 : relation_trio trio) const
1906 : {
1907 14453604 : if (lhs.undefined_p ())
1908 : return false;
1909 : // Start with the default operation.
1910 14453604 : range_op_handler minus (MINUS_EXPR);
1911 14453604 : if (!minus)
1912 : return false;
1913 14453604 : bool res = minus.fold_range (r, type, lhs, op2);
1914 14453604 : relation_kind rel = trio.lhs_op1 ();
1915 : // Check for a relation refinement.
1916 14453604 : if (res)
1917 14453604 : adjust_op1_for_overflow (r, op2, rel, true /* PLUS_EXPR */);
1918 : return res;
1919 : }
1920 :
1921 : bool
1922 4358693 : operator_plus::op2_range (irange &r, tree type,
1923 : const irange &lhs,
1924 : const irange &op1,
1925 : relation_trio rel) const
1926 : {
1927 4358693 : return op1_range (r, type, lhs, op1, rel.swap_op1_op2 ());
1928 : }
1929 :
1930 : class operator_widen_plus_signed : public range_operator
1931 : {
1932 : public:
1933 : virtual void wi_fold (irange &r, tree type,
1934 : const wide_int &lh_lb,
1935 : const wide_int &lh_ub,
1936 : const wide_int &rh_lb,
1937 : const wide_int &rh_ub) const;
1938 : } op_widen_plus_signed;
1939 :
1940 : void
1941 0 : operator_widen_plus_signed::wi_fold (irange &r, tree type,
1942 : const wide_int &lh_lb,
1943 : const wide_int &lh_ub,
1944 : const wide_int &rh_lb,
1945 : const wide_int &rh_ub) const
1946 : {
1947 0 : wi::overflow_type ov_lb, ov_ub;
1948 0 : signop s = TYPE_SIGN (type);
1949 :
1950 0 : wide_int lh_wlb
1951 0 : = wide_int::from (lh_lb, wi::get_precision (lh_lb) * 2, SIGNED);
1952 0 : wide_int lh_wub
1953 0 : = wide_int::from (lh_ub, wi::get_precision (lh_ub) * 2, SIGNED);
1954 0 : wide_int rh_wlb = wide_int::from (rh_lb, wi::get_precision (rh_lb) * 2, s);
1955 0 : wide_int rh_wub = wide_int::from (rh_ub, wi::get_precision (rh_ub) * 2, s);
1956 :
1957 0 : wide_int new_lb = wi::add (lh_wlb, rh_wlb, s, &ov_lb);
1958 0 : wide_int new_ub = wi::add (lh_wub, rh_wub, s, &ov_ub);
1959 :
1960 0 : r = int_range<2> (type, new_lb, new_ub);
1961 0 : }
1962 :
1963 : class operator_widen_plus_unsigned : public range_operator
1964 : {
1965 : public:
1966 : virtual void wi_fold (irange &r, tree type,
1967 : const wide_int &lh_lb,
1968 : const wide_int &lh_ub,
1969 : const wide_int &rh_lb,
1970 : const wide_int &rh_ub) const;
1971 : } op_widen_plus_unsigned;
1972 :
1973 : void
1974 0 : operator_widen_plus_unsigned::wi_fold (irange &r, tree type,
1975 : const wide_int &lh_lb,
1976 : const wide_int &lh_ub,
1977 : const wide_int &rh_lb,
1978 : const wide_int &rh_ub) const
1979 : {
1980 0 : wi::overflow_type ov_lb, ov_ub;
1981 0 : signop s = TYPE_SIGN (type);
1982 :
1983 0 : wide_int lh_wlb
1984 0 : = wide_int::from (lh_lb, wi::get_precision (lh_lb) * 2, UNSIGNED);
1985 0 : wide_int lh_wub
1986 0 : = wide_int::from (lh_ub, wi::get_precision (lh_ub) * 2, UNSIGNED);
1987 0 : wide_int rh_wlb = wide_int::from (rh_lb, wi::get_precision (rh_lb) * 2, s);
1988 0 : wide_int rh_wub = wide_int::from (rh_ub, wi::get_precision (rh_ub) * 2, s);
1989 :
1990 0 : wide_int new_lb = wi::add (lh_wlb, rh_wlb, s, &ov_lb);
1991 0 : wide_int new_ub = wi::add (lh_wub, rh_wub, s, &ov_ub);
1992 :
1993 0 : r = int_range<2> (type, new_lb, new_ub);
1994 0 : }
1995 :
1996 : void
1997 25165649 : operator_minus::update_bitmask (irange &r, const irange &lh,
1998 : const irange &rh) const
1999 : {
2000 25165649 : update_known_bitmask (r, MINUS_EXPR, lh, rh);
2001 25165649 : }
2002 :
2003 : void
2004 34662683 : operator_minus::wi_fold (irange &r, tree type,
2005 : const wide_int &lh_lb, const wide_int &lh_ub,
2006 : const wide_int &rh_lb, const wide_int &rh_ub) const
2007 : {
2008 34662683 : wi::overflow_type ov_lb, ov_ub;
2009 34662683 : signop s = TYPE_SIGN (type);
2010 34662683 : wide_int new_lb = wi::sub (lh_lb, rh_ub, s, &ov_lb);
2011 34662683 : wide_int new_ub = wi::sub (lh_ub, rh_lb, s, &ov_ub);
2012 34662683 : value_range_with_overflow (r, type, new_lb, new_ub, ov_lb, ov_ub);
2013 34662683 : }
2014 :
2015 :
2016 : // Return the relation between LHS and OP1 based on the relation between
2017 : // OP1 and OP2.
2018 :
2019 : relation_kind
2020 5518787 : operator_minus::lhs_op1_relation (const irange &, const irange &op1,
2021 : const irange &, relation_kind rel) const
2022 : {
2023 5518787 : if (!op1.undefined_p () && TYPE_SIGN (op1.type ()) == UNSIGNED)
2024 2687268 : switch (rel)
2025 : {
2026 73587 : case VREL_GT:
2027 73587 : case VREL_GE:
2028 73587 : return VREL_LE;
2029 : default:
2030 : break;
2031 : }
2032 : return VREL_VARYING;
2033 : }
2034 :
2035 : // Check to see if the relation REL between OP1 and OP2 has any effect on the
2036 : // LHS of the expression. If so, apply it to LHS_RANGE. This is a helper
2037 : // function for both MINUS_EXPR and POINTER_DIFF_EXPR.
2038 :
2039 : bool
2040 28226589 : minus_op1_op2_relation_effect (irange &lhs_range, tree type,
2041 : const irange &op1_range ATTRIBUTE_UNUSED,
2042 : const irange &op2_range ATTRIBUTE_UNUSED,
2043 : relation_kind rel)
2044 : {
2045 28226589 : if (rel == VREL_VARYING)
2046 : return false;
2047 :
2048 327277 : int_range<2> rel_range;
2049 327277 : unsigned prec = TYPE_PRECISION (type);
2050 327277 : signop sgn = TYPE_SIGN (type);
2051 :
2052 : // == and != produce [0,0] and ~[0,0] regardless of wrapping.
2053 327277 : if (rel == VREL_EQ)
2054 10295 : rel_range = int_range<2> (type, wi::zero (prec), wi::zero (prec));
2055 316982 : else if (rel == VREL_NE)
2056 125124 : rel_range = int_range<2> (type, wi::zero (prec), wi::zero (prec),
2057 62562 : VR_ANTI_RANGE);
2058 254420 : else if (TYPE_OVERFLOW_WRAPS (type))
2059 : {
2060 153403 : switch (rel)
2061 : {
2062 : // For wrapping signed values and unsigned, if op1 > op2 or
2063 : // op1 < op2, then op1 - op2 can be restricted to ~[0, 0].
2064 61169 : case VREL_GT:
2065 61169 : case VREL_LT:
2066 122338 : rel_range = int_range<2> (type, wi::zero (prec), wi::zero (prec),
2067 61169 : VR_ANTI_RANGE);
2068 61169 : break;
2069 : default:
2070 : return false;
2071 : }
2072 : }
2073 : else
2074 : {
2075 101017 : switch (rel)
2076 : {
2077 : // op1 > op2, op1 - op2 can be restricted to [1, +INF]
2078 25205 : case VREL_GT:
2079 50410 : rel_range = int_range<2> (type, wi::one (prec),
2080 50410 : wi::max_value (prec, sgn));
2081 25205 : break;
2082 : // op1 >= op2, op1 - op2 can be restricted to [0, +INF]
2083 75011 : case VREL_GE:
2084 150022 : rel_range = int_range<2> (type, wi::zero (prec),
2085 150022 : wi::max_value (prec, sgn));
2086 75011 : break;
2087 : // op1 < op2, op1 - op2 can be restricted to [-INF, -1]
2088 429 : case VREL_LT:
2089 858 : rel_range = int_range<2> (type, wi::min_value (prec, sgn),
2090 429 : wi::minus_one (prec));
2091 429 : break;
2092 : // op1 <= op2, op1 - op2 can be restricted to [-INF, 0]
2093 311 : case VREL_LE:
2094 622 : rel_range = int_range<2> (type, wi::min_value (prec, sgn),
2095 311 : wi::zero (prec));
2096 311 : break;
2097 : default:
2098 : return false;
2099 : }
2100 : }
2101 234982 : lhs_range.intersect (rel_range);
2102 234982 : return true;
2103 327277 : }
2104 :
2105 : // Check if the LHS range indicates a relation between OP1 and OP2.
2106 : // OP1 - OP2 == 0 implies OP1 == OP2 even with wrapping arithmetic.
2107 :
2108 : relation_kind
2109 4976647 : operator_minus::op1_op2_relation (const irange &lhs, const irange &,
2110 : const irange &) const
2111 : {
2112 4976647 : if (lhs.undefined_p ())
2113 : return VREL_UNDEFINED;
2114 :
2115 4976647 : if (lhs.zero_p ())
2116 : return VREL_EQ;
2117 :
2118 4869565 : if (!lhs.contains_zero_p ())
2119 2118293 : return VREL_NE;
2120 :
2121 : return VREL_VARYING;
2122 : }
2123 :
2124 : bool
2125 25165649 : operator_minus::op1_op2_relation_effect (irange &lhs_range, tree type,
2126 : const irange &op1_range,
2127 : const irange &op2_range,
2128 : relation_kind rel) const
2129 : {
2130 25165649 : return minus_op1_op2_relation_effect (lhs_range, type, op1_range, op2_range,
2131 25165649 : rel);
2132 : }
2133 :
2134 : bool
2135 1464716 : operator_minus::op1_range (irange &r, tree type,
2136 : const irange &lhs,
2137 : const irange &op2,
2138 : relation_trio trio) const
2139 : {
2140 1464716 : if (lhs.undefined_p ())
2141 : return false;
2142 : // Start with the default operation.
2143 1464716 : range_op_handler minus (PLUS_EXPR);
2144 1464716 : if (!minus)
2145 : return false;
2146 1464716 : bool res = minus.fold_range (r, type, lhs, op2);
2147 1464716 : relation_kind rel = trio.lhs_op1 ();
2148 1464716 : if (res)
2149 1464716 : adjust_op1_for_overflow (r, op2, rel, false /* PLUS_EXPR */);
2150 : return res;
2151 :
2152 : }
2153 :
2154 : bool
2155 2158964 : operator_minus::op2_range (irange &r, tree type,
2156 : const irange &lhs,
2157 : const irange &op1,
2158 : relation_trio) const
2159 : {
2160 2158964 : if (lhs.undefined_p ())
2161 : return false;
2162 2158964 : return fold_range (r, type, op1, lhs);
2163 : }
2164 :
2165 : void
2166 987135 : operator_min::update_bitmask (irange &r, const irange &lh,
2167 : const irange &rh) const
2168 : {
2169 987135 : update_known_bitmask (r, MIN_EXPR, lh, rh);
2170 987135 : }
2171 :
2172 : void
2173 1551314 : operator_min::wi_fold (irange &r, tree type,
2174 : const wide_int &lh_lb, const wide_int &lh_ub,
2175 : const wide_int &rh_lb, const wide_int &rh_ub) const
2176 : {
2177 1551314 : signop s = TYPE_SIGN (type);
2178 1551314 : wide_int new_lb = wi::min (lh_lb, rh_lb, s);
2179 1551314 : wide_int new_ub = wi::min (lh_ub, rh_ub, s);
2180 1551314 : value_range_with_overflow (r, type, new_lb, new_ub);
2181 1551314 : }
2182 :
2183 : // When op1 <= op2, MIN (op1, op2) is op1.
2184 :
2185 : relation_kind
2186 987268 : operator_min::lhs_op1_relation (const irange &lhs, const irange &op1,
2187 : const irange &op2, relation_kind rel) const
2188 : {
2189 987268 : if (lhs.undefined_p () || op1.undefined_p () || op2.undefined_p ())
2190 : return VREL_VARYING;
2191 1973354 : if (rel == VREL_LE || rel == VREL_LT || rel == VREL_EQ
2192 3932134 : || wi::le_p (op1.upper_bound (), op2.lower_bound (),
2193 981819 : TYPE_SIGN (op1.type ())))
2194 20367 : return VREL_EQ;
2195 : return VREL_VARYING;
2196 : }
2197 :
2198 : // Same as above, but for op2.
2199 :
2200 : relation_kind
2201 633540 : operator_min::lhs_op2_relation (const irange &lhs, const irange &op1,
2202 : const irange &op2, relation_kind rel) const
2203 : {
2204 633540 : if (lhs.undefined_p () || op1.undefined_p () || op2.undefined_p ())
2205 : return VREL_VARYING;
2206 1266098 : if (rel == VREL_GE || rel == VREL_GT || rel == VREL_EQ
2207 2526076 : || wi::le_p (op2.upper_bound (), op1.lower_bound (),
2208 631009 : TYPE_SIGN (op1.type ())))
2209 4177 : return VREL_EQ;
2210 : return VREL_VARYING;
2211 : }
2212 :
2213 :
2214 : void
2215 841505 : operator_max::update_bitmask (irange &r, const irange &lh,
2216 : const irange &rh) const
2217 : {
2218 841505 : update_known_bitmask (r, MAX_EXPR, lh, rh);
2219 841505 : }
2220 :
2221 : void
2222 1038689 : operator_max::wi_fold (irange &r, tree type,
2223 : const wide_int &lh_lb, const wide_int &lh_ub,
2224 : const wide_int &rh_lb, const wide_int &rh_ub) const
2225 : {
2226 1038689 : signop s = TYPE_SIGN (type);
2227 1038689 : wide_int new_lb = wi::max (lh_lb, rh_lb, s);
2228 1038689 : wide_int new_ub = wi::max (lh_ub, rh_ub, s);
2229 1038689 : value_range_with_overflow (r, type, new_lb, new_ub);
2230 1038689 : }
2231 :
2232 : // When op1 >= op2, MAX (op1, op2) is op1.
2233 :
2234 : relation_kind
2235 841950 : operator_max::lhs_op1_relation (const irange &lhs, const irange &op1,
2236 : const irange &op2, relation_kind rel) const
2237 : {
2238 841950 : if (lhs.undefined_p () || op1.undefined_p () || op2.undefined_p ())
2239 : return VREL_VARYING;
2240 1682618 : if (rel == VREL_GE || rel == VREL_GT || rel == VREL_EQ
2241 3364783 : || wi::ge_p (op1.lower_bound (), op2.upper_bound (),
2242 841158 : TYPE_SIGN (op1.type ())))
2243 128473 : return VREL_EQ;
2244 : return VREL_VARYING;
2245 : }
2246 :
2247 : // Same as above, but for op2.
2248 :
2249 : relation_kind
2250 52968 : operator_max::lhs_op2_relation (const irange &lhs, const irange &op1,
2251 : const irange &op2, relation_kind rel) const
2252 : {
2253 52968 : if (lhs.undefined_p () || op1.undefined_p () || op2.undefined_p ())
2254 : return VREL_VARYING;
2255 105922 : if (rel == VREL_LE || rel == VREL_LT || rel == VREL_EQ
2256 211319 : || wi::ge_p (op2.lower_bound (), op1.upper_bound (),
2257 52786 : TYPE_SIGN (op1.type ())))
2258 268 : return VREL_EQ;
2259 : return VREL_VARYING;
2260 : }
2261 :
2262 :
2263 : // Calculate the cross product of two sets of ranges and return it.
2264 : //
2265 : // Multiplications, divisions and shifts are a bit tricky to handle,
2266 : // depending on the mix of signs we have in the two ranges, we need to
2267 : // operate on different values to get the minimum and maximum values
2268 : // for the new range. One approach is to figure out all the
2269 : // variations of range combinations and do the operations.
2270 : //
2271 : // However, this involves several calls to compare_values and it is
2272 : // pretty convoluted. It's simpler to do the 4 operations (MIN0 OP
2273 : // MIN1, MIN0 OP MAX1, MAX0 OP MIN1 and MAX0 OP MAX0 OP MAX1) and then
2274 : // figure the smallest and largest values to form the new range.
2275 :
2276 : void
2277 17594826 : cross_product_operator::wi_cross_product (irange &r, tree type,
2278 : const wide_int &lh_lb,
2279 : const wide_int &lh_ub,
2280 : const wide_int &rh_lb,
2281 : const wide_int &rh_ub) const
2282 : {
2283 17594826 : wide_int cp1, cp2, cp3, cp4;
2284 : // Default to varying.
2285 17594826 : r.set_varying (type);
2286 :
2287 : // Compute the 4 cross operations, bailing if we get an overflow we
2288 : // can't handle.
2289 17594826 : if (wi_op_overflows (cp1, type, lh_lb, rh_lb))
2290 : return;
2291 17594788 : if (wi::eq_p (lh_lb, lh_ub))
2292 4936747 : cp3 = cp1;
2293 12658041 : else if (wi_op_overflows (cp3, type, lh_ub, rh_lb))
2294 : return;
2295 17594788 : if (wi::eq_p (rh_lb, rh_ub))
2296 13967465 : cp2 = cp1;
2297 3627323 : else if (wi_op_overflows (cp2, type, lh_lb, rh_ub))
2298 : return;
2299 17592689 : if (wi::eq_p (lh_lb, lh_ub))
2300 4936729 : cp4 = cp2;
2301 12655960 : else if (wi_op_overflows (cp4, type, lh_ub, rh_ub))
2302 : return;
2303 :
2304 : // Order pairs.
2305 17592689 : signop sign = TYPE_SIGN (type);
2306 17592689 : if (wi::gt_p (cp1, cp2, sign))
2307 1669992 : std::swap (cp1, cp2);
2308 17592689 : if (wi::gt_p (cp3, cp4, sign))
2309 1619800 : std::swap (cp3, cp4);
2310 :
2311 : // Choose min and max from the ordered pairs.
2312 17592689 : wide_int res_lb = wi::min (cp1, cp3, sign);
2313 17592689 : wide_int res_ub = wi::max (cp2, cp4, sign);
2314 17592689 : value_range_with_overflow (r, type, res_lb, res_ub);
2315 17600911 : }
2316 :
2317 :
2318 : void
2319 15838081 : operator_mult::update_bitmask (irange &r, const irange &lh,
2320 : const irange &rh) const
2321 : {
2322 15838081 : update_known_bitmask (r, MULT_EXPR, lh, rh);
2323 15838081 : }
2324 :
2325 : bool
2326 1854485 : operator_mult::op1_range (irange &r, tree type,
2327 : const irange &lhs, const irange &op2,
2328 : relation_trio) const
2329 : {
2330 1854485 : if (lhs.undefined_p ())
2331 : return false;
2332 :
2333 : // We can't solve 0 = OP1 * N by dividing by N with a wrapping type.
2334 : // For example: For 0 = OP1 * 2, OP1 could be 0, or MAXINT, whereas
2335 : // for 4 = OP1 * 2, OP1 could be 2 or 130 (unsigned 8-bit)
2336 1854485 : if (TYPE_OVERFLOW_WRAPS (type))
2337 : return false;
2338 :
2339 623369 : wide_int offset;
2340 623369 : if (op2.singleton_p (offset) && offset != 0)
2341 448520 : return range_op_handler (TRUNC_DIV_EXPR).fold_range (r, type, lhs, op2);
2342 :
2343 : // ~[0, 0] = op1 * op2 defines op1 and op2 as non-zero.
2344 174849 : if (!lhs.contains_p (wi::zero (TYPE_PRECISION (lhs.type ()))))
2345 : {
2346 50888 : r.set_nonzero (type);
2347 50888 : return true;
2348 : }
2349 : return false;
2350 623369 : }
2351 :
2352 : bool
2353 217340 : operator_mult::op2_range (irange &r, tree type,
2354 : const irange &lhs, const irange &op1,
2355 : relation_trio rel) const
2356 : {
2357 217340 : return operator_mult::op1_range (r, type, lhs, op1, rel.swap_op1_op2 ());
2358 : }
2359 :
2360 : bool
2361 17394697 : operator_mult::wi_op_overflows (wide_int &res, tree type,
2362 : const wide_int &w0, const wide_int &w1) const
2363 : {
2364 17394697 : wi::overflow_type overflow = wi::OVF_NONE;
2365 17394697 : signop sign = TYPE_SIGN (type);
2366 17394697 : res = wi::mul (w0, w1, sign, &overflow);
2367 17394697 : if (overflow && TYPE_OVERFLOW_UNDEFINED (type))
2368 : {
2369 : // For multiplication, the sign of the overflow is given
2370 : // by the comparison of the signs of the operands.
2371 7549859 : if (sign == UNSIGNED || w0.sign_mask () == w1.sign_mask ())
2372 4175783 : res = wi::max_value (w0.get_precision (), sign);
2373 : else
2374 3374306 : res = wi::min_value (w0.get_precision (), sign);
2375 : return false;
2376 : }
2377 9844838 : return overflow;
2378 : }
2379 :
2380 : void
2381 19836477 : operator_mult::wi_fold (irange &r, tree type,
2382 : const wide_int &lh_lb, const wide_int &lh_ub,
2383 : const wide_int &rh_lb, const wide_int &rh_ub) const
2384 : {
2385 19836477 : if (TYPE_OVERFLOW_UNDEFINED (type))
2386 : {
2387 6993246 : wi_cross_product (r, type, lh_lb, lh_ub, rh_lb, rh_ub);
2388 6993246 : return;
2389 : }
2390 :
2391 : // Multiply the ranges when overflow wraps. This is basically fancy
2392 : // code so we don't drop to varying with an unsigned
2393 : // [-3,-1]*[-3,-1].
2394 : //
2395 : // This test requires 2*prec bits if both operands are signed and
2396 : // 2*prec + 2 bits if either is not. Therefore, extend the values
2397 : // using the sign of the result to PREC2. From here on out,
2398 : // everything is just signed math no matter what the input types
2399 : // were.
2400 :
2401 12843231 : signop sign = TYPE_SIGN (type);
2402 12843231 : unsigned prec = TYPE_PRECISION (type);
2403 12843231 : widest2_int min0 = widest2_int::from (lh_lb, sign);
2404 12843231 : widest2_int max0 = widest2_int::from (lh_ub, sign);
2405 12843231 : widest2_int min1 = widest2_int::from (rh_lb, sign);
2406 12843231 : widest2_int max1 = widest2_int::from (rh_ub, sign);
2407 12843231 : widest2_int sizem1 = wi::mask <widest2_int> (prec, false);
2408 12843231 : widest2_int size = sizem1 + 1;
2409 :
2410 : // Canonicalize the intervals.
2411 12843231 : if (sign == UNSIGNED)
2412 : {
2413 12046124 : if (wi::ltu_p (size, min0 + max0))
2414 : {
2415 1546917 : min0 -= size;
2416 1546917 : max0 -= size;
2417 : }
2418 12046087 : if (wi::ltu_p (size, min1 + max1))
2419 : {
2420 172540 : min1 -= size;
2421 172540 : max1 -= size;
2422 : }
2423 : }
2424 :
2425 : // Sort the 4 products so that min is in prod0 and max is in
2426 : // prod3.
2427 12843231 : widest2_int prod0 = min0 * min1;
2428 12843231 : widest2_int prod1 = min0 * max1;
2429 12843231 : widest2_int prod2 = max0 * min1;
2430 12843231 : widest2_int prod3 = max0 * max1;
2431 :
2432 : // min0min1 > max0max1
2433 12843231 : if (prod0 > prod3)
2434 201331 : std::swap (prod0, prod3);
2435 :
2436 : // min0max1 > max0min1
2437 12843231 : if (prod1 > prod2)
2438 333652 : std::swap (prod1, prod2);
2439 :
2440 12843231 : if (prod0 > prod1)
2441 81027 : std::swap (prod0, prod1);
2442 :
2443 12843231 : if (prod2 > prod3)
2444 4894 : std::swap (prod2, prod3);
2445 :
2446 : // diff = max - min
2447 12843231 : prod2 = prod3 - prod0;
2448 12843231 : if (wi::geu_p (prod2, sizem1))
2449 : {
2450 : // Multiplying by X, where X is a power of 2 is [0,0][X,+INF].
2451 8056084 : if (TYPE_UNSIGNED (type) && rh_lb == rh_ub
2452 7394610 : && wi::exact_log2 (rh_lb) != -1 && prec > 1)
2453 : {
2454 2769696 : r.set (type, rh_lb, wi::max_value (prec, sign));
2455 2769696 : int_range<2> zero;
2456 2769696 : zero.set_zero (type);
2457 2769696 : r.union_ (zero);
2458 2769696 : }
2459 : else
2460 : // The range covers all values.
2461 1333317 : r.set_varying (type);
2462 : }
2463 : else
2464 : {
2465 8740218 : wide_int new_lb = wide_int::from (prod0, prec, sign);
2466 8740218 : wide_int new_ub = wide_int::from (prod3, prec, sign);
2467 8740218 : create_possibly_reversed_range (r, type, new_lb, new_ub);
2468 8740287 : }
2469 12844104 : }
2470 :
2471 : bool
2472 15838081 : operator_mult::op1_op2_relation_effect (irange &lhs_range, tree type,
2473 : const irange &,
2474 : const irange &,
2475 : relation_kind rel) const
2476 : {
2477 : // a*a is nonnegative without overflow.
2478 : // tree_binary_nonnegative_p handles this in a similar way.
2479 15838081 : if (rel == VREL_EQ
2480 15838081 : && TYPE_OVERFLOW_UNDEFINED (type))
2481 : {
2482 35465 : int_range<2> nonnegative;
2483 35465 : nonnegative.set_nonnegative (type);
2484 35465 : lhs_range.intersect (nonnegative);
2485 35465 : return true;
2486 35465 : }
2487 : return false;
2488 : }
2489 :
2490 : class operator_widen_mult_signed : public range_operator
2491 : {
2492 : public:
2493 : virtual void wi_fold (irange &r, tree type,
2494 : const wide_int &lh_lb,
2495 : const wide_int &lh_ub,
2496 : const wide_int &rh_lb,
2497 : const wide_int &rh_ub)
2498 : const;
2499 : } op_widen_mult_signed;
2500 :
2501 : void
2502 1331 : operator_widen_mult_signed::wi_fold (irange &r, tree type,
2503 : const wide_int &lh_lb,
2504 : const wide_int &lh_ub,
2505 : const wide_int &rh_lb,
2506 : const wide_int &rh_ub) const
2507 : {
2508 1331 : wide_int lh_wlb = wide_int::from (lh_lb, TYPE_PRECISION (type), SIGNED);
2509 1331 : wide_int lh_wub = wide_int::from (lh_ub, TYPE_PRECISION (type), SIGNED);
2510 1331 : wide_int rh_wlb = wide_int::from (rh_lb, TYPE_PRECISION (type), SIGNED);
2511 1331 : wide_int rh_wub = wide_int::from (rh_ub, TYPE_PRECISION (type), SIGNED);
2512 :
2513 : /* We don't expect a widening multiplication to be able to overflow but range
2514 : calculations for multiplications are complicated. After widening the
2515 : operands lets call the base class. */
2516 1331 : return op_mult.wi_fold (r, type, lh_wlb, lh_wub, rh_wlb, rh_wub);
2517 1331 : }
2518 :
2519 : class operator_widen_mult_unsigned : public range_operator
2520 : {
2521 : public:
2522 : virtual void wi_fold (irange &r, tree type,
2523 : const wide_int &lh_lb,
2524 : const wide_int &lh_ub,
2525 : const wide_int &rh_lb,
2526 : const wide_int &rh_ub)
2527 : const;
2528 : } op_widen_mult_unsigned;
2529 :
2530 : void
2531 7524 : operator_widen_mult_unsigned::wi_fold (irange &r, tree type,
2532 : const wide_int &lh_lb,
2533 : const wide_int &lh_ub,
2534 : const wide_int &rh_lb,
2535 : const wide_int &rh_ub) const
2536 : {
2537 7524 : wide_int lh_wlb = wide_int::from (lh_lb, TYPE_PRECISION (type), UNSIGNED);
2538 7524 : wide_int lh_wub = wide_int::from (lh_ub, TYPE_PRECISION (type), UNSIGNED);
2539 7524 : wide_int rh_wlb = wide_int::from (rh_lb, TYPE_PRECISION (type), UNSIGNED);
2540 7524 : wide_int rh_wub = wide_int::from (rh_ub, TYPE_PRECISION (type), UNSIGNED);
2541 :
2542 : /* We don't expect a widening multiplication to be able to overflow but range
2543 : calculations for multiplications are complicated. After widening the
2544 : operands lets call the base class. */
2545 7524 : return op_mult.wi_fold (r, type, lh_wlb, lh_wub, rh_wlb, rh_wub);
2546 7524 : }
2547 :
2548 : class operator_widen_mult_signed_unsigned : public range_operator
2549 : {
2550 : public:
2551 : virtual void wi_fold (irange &r, tree type,
2552 : const wide_int &lh_lb,
2553 : const wide_int &lh_ub,
2554 : const wide_int &rh_lb,
2555 : const wide_int &rh_ub)
2556 : const;
2557 : } op_widen_mult_signed_unsigned;
2558 :
2559 : void
2560 0 : operator_widen_mult_signed_unsigned::wi_fold (irange &r, tree type,
2561 : const wide_int &lh_lb,
2562 : const wide_int &lh_ub,
2563 : const wide_int &rh_lb,
2564 : const wide_int &rh_ub) const
2565 : {
2566 0 : wide_int lh_wlb = wide_int::from (lh_lb, TYPE_PRECISION (type), SIGNED);
2567 0 : wide_int lh_wub = wide_int::from (lh_ub, TYPE_PRECISION (type), SIGNED);
2568 0 : wide_int rh_wlb = wide_int::from (rh_lb, TYPE_PRECISION (type), UNSIGNED);
2569 0 : wide_int rh_wub = wide_int::from (rh_ub, TYPE_PRECISION (type), UNSIGNED);
2570 :
2571 : /* We don't expect a widening multiplication to be able to overflow but range
2572 : calculations for multiplications are complicated. After widening the
2573 : operands lets call the base class. */
2574 0 : return op_mult.wi_fold (r, type, lh_wlb, lh_wub, rh_wlb, rh_wub);
2575 0 : }
2576 :
2577 : class operator_div : public cross_product_operator
2578 : {
2579 : using range_operator::update_bitmask;
2580 : using range_operator::op2_range;
2581 : using range_operator::op1_op2_relation_effect;
2582 : public:
2583 : operator_div (tree_code div_kind) { m_code = div_kind; }
2584 : bool op2_range (irange &r, tree type, const irange &lhs, const irange &,
2585 : relation_trio) const final override;
2586 : virtual void wi_fold (irange &r, tree type,
2587 : const wide_int &lh_lb,
2588 : const wide_int &lh_ub,
2589 : const wide_int &rh_lb,
2590 : const wide_int &rh_ub) const final override;
2591 : virtual bool wi_op_overflows (wide_int &res, tree type,
2592 : const wide_int &, const wide_int &)
2593 : const final override;
2594 : bool op1_op2_relation_effect (irange &lhs_range,
2595 : tree type,
2596 : const irange &op1_range,
2597 : const irange &op2_range,
2598 : relation_kind rel) const final override;
2599 3300472 : void update_bitmask (irange &r, const irange &lh, const irange &rh)
2600 : const final override
2601 3300472 : { update_known_bitmask (r, m_code, lh, rh); }
2602 : protected:
2603 : tree_code m_code;
2604 : };
2605 :
2606 : static const operator_div op_trunc_div (TRUNC_DIV_EXPR);
2607 : static const operator_div op_floor_div (FLOOR_DIV_EXPR);
2608 : static const operator_div op_round_div (ROUND_DIV_EXPR);
2609 : static const operator_div op_ceil_div (CEIL_DIV_EXPR);
2610 :
2611 : // Set OP2 to non-zero if the LHS isn't UNDEFINED.
2612 : bool
2613 43438 : operator_div::op2_range (irange &r, tree type, const irange &lhs,
2614 : const irange &, relation_trio) const
2615 : {
2616 43438 : if (!lhs.undefined_p ())
2617 : {
2618 43438 : r.set_nonzero (type);
2619 43438 : return true;
2620 : }
2621 : return false;
2622 : }
2623 :
2624 : bool
2625 14700599 : operator_div::wi_op_overflows (wide_int &res, tree type,
2626 : const wide_int &w0, const wide_int &w1) const
2627 : {
2628 14700599 : if (w1 == 0)
2629 : return true;
2630 :
2631 14700599 : wi::overflow_type overflow = wi::OVF_NONE;
2632 14700599 : signop sign = TYPE_SIGN (type);
2633 :
2634 14700599 : switch (m_code)
2635 : {
2636 14555922 : case EXACT_DIV_EXPR:
2637 14555922 : case TRUNC_DIV_EXPR:
2638 14555922 : res = wi::div_trunc (w0, w1, sign, &overflow);
2639 14555922 : break;
2640 133726 : case FLOOR_DIV_EXPR:
2641 133726 : res = wi::div_floor (w0, w1, sign, &overflow);
2642 133726 : break;
2643 288 : case ROUND_DIV_EXPR:
2644 288 : res = wi::div_round (w0, w1, sign, &overflow);
2645 288 : break;
2646 10663 : case CEIL_DIV_EXPR:
2647 10663 : res = wi::div_ceil (w0, w1, sign, &overflow);
2648 10663 : break;
2649 0 : default:
2650 0 : gcc_unreachable ();
2651 : }
2652 :
2653 14700599 : if (overflow && TYPE_OVERFLOW_UNDEFINED (type))
2654 : {
2655 : // For division, the only case is -INF / -1 = +INF.
2656 219162 : res = wi::max_value (w0.get_precision (), sign);
2657 219162 : return false;
2658 : }
2659 14481437 : return overflow;
2660 : }
2661 :
2662 : void
2663 4809078 : operator_div::wi_fold (irange &r, tree type,
2664 : const wide_int &lh_lb, const wide_int &lh_ub,
2665 : const wide_int &rh_lb, const wide_int &rh_ub) const
2666 : {
2667 4809078 : const wide_int dividend_min = lh_lb;
2668 4809078 : const wide_int dividend_max = lh_ub;
2669 4809078 : const wide_int divisor_min = rh_lb;
2670 4809078 : const wide_int divisor_max = rh_ub;
2671 4809078 : signop sign = TYPE_SIGN (type);
2672 4809078 : unsigned prec = TYPE_PRECISION (type);
2673 4809078 : wide_int extra_min, extra_max;
2674 :
2675 : // If we know we won't divide by zero, just do the division.
2676 4809078 : if (!wi_includes_zero_p (type, divisor_min, divisor_max))
2677 : {
2678 4056250 : wi_cross_product (r, type, dividend_min, dividend_max,
2679 : divisor_min, divisor_max);
2680 4056250 : return;
2681 : }
2682 :
2683 : // If we're definitely dividing by zero, there's nothing to do.
2684 752828 : if (wi_zero_p (type, divisor_min, divisor_max))
2685 : {
2686 18368 : r.set_undefined ();
2687 18368 : return;
2688 : }
2689 :
2690 : // Perform the division in 2 parts, [LB, -1] and [1, UB], which will
2691 : // skip any division by zero.
2692 :
2693 : // First divide by the negative numbers, if any.
2694 734460 : if (wi::neg_p (divisor_min, sign))
2695 987970 : wi_cross_product (r, type, dividend_min, dividend_max,
2696 987970 : divisor_min, wi::minus_one (prec));
2697 : else
2698 240475 : r.set_undefined ();
2699 :
2700 : // Then divide by the non-zero positive numbers, if any.
2701 734460 : if (wi::gt_p (divisor_max, wi::zero (prec), sign))
2702 : {
2703 733609 : int_range_max tmp;
2704 1467218 : wi_cross_product (tmp, type, dividend_min, dividend_max,
2705 733609 : wi::one (prec), divisor_max);
2706 733609 : r.union_ (tmp);
2707 733609 : }
2708 : // We shouldn't still have undefined here.
2709 734460 : gcc_checking_assert (!r.undefined_p ());
2710 4809714 : }
2711 :
2712 : bool
2713 3300472 : operator_div::op1_op2_relation_effect (irange &lhs_range,
2714 : tree type,
2715 : const irange &op1_range,
2716 : const irange &op2_range,
2717 : relation_kind rel) const
2718 : {
2719 3300472 : if (rel == VREL_VARYING)
2720 : return false;
2721 :
2722 2723 : int_range<2> rel_range;
2723 :
2724 2723 : switch (rel)
2725 : {
2726 : /* op1/op2 = 0 if op1 < op2 and both op1 and op2
2727 : are known positives. */
2728 125 : case VREL_LT:
2729 : // Exact, and truncate division will produce 0 for this case.
2730 : // Floor division will be treated similar to truncate div as rounding towards
2731 : // to 0 is the same as rounding towards -inf for positive values.
2732 125 : if (m_code != EXACT_DIV_EXPR
2733 125 : && m_code != TRUNC_DIV_EXPR
2734 4 : && m_code != FLOOR_DIV_EXPR)
2735 : return false;
2736 121 : if (!op1_range.nonnegative_p ()
2737 121 : || !op2_range.nonnegative_p ())
2738 : return false;
2739 84 : rel_range.set_zero (type);
2740 84 : break;
2741 3 : case VREL_EQ:
2742 3 : {
2743 3 : wide_int one = wi::one (TYPE_PRECISION (type));
2744 3 : rel_range.set (type, one, one);
2745 3 : break;
2746 3 : }
2747 : default:
2748 : return false;
2749 : }
2750 :
2751 87 : lhs_range.intersect (rel_range);
2752 87 : return true;
2753 2723 : }
2754 :
2755 : class operator_exact_divide : public operator_div
2756 : {
2757 : using range_operator::op1_range;
2758 : public:
2759 : operator_exact_divide () : operator_div (EXACT_DIV_EXPR) { }
2760 : virtual bool op1_range (irange &r, tree type,
2761 : const irange &lhs,
2762 : const irange &op2,
2763 : relation_trio) const;
2764 :
2765 : } op_exact_div;
2766 :
2767 : bool
2768 1141660 : operator_exact_divide::op1_range (irange &r, tree type,
2769 : const irange &lhs,
2770 : const irange &op2,
2771 : relation_trio) const
2772 : {
2773 1141660 : if (lhs.undefined_p ())
2774 : return false;
2775 1141660 : wide_int offset;
2776 : // [2, 4] = op1 / [3,3] since its exact divide, no need to worry about
2777 : // remainders in the endpoints, so op1 = [2,4] * [3,3] = [6,12].
2778 : // We wont bother trying to enumerate all the in between stuff :-P
2779 : // TRUE accuracy is [6,6][9,9][12,12]. This is unlikely to matter most of
2780 : // the time however.
2781 : // If op2 is a multiple of 2, we would be able to set some non-zero bits.
2782 1141660 : if (op2.singleton_p (offset) && offset != 0)
2783 1141660 : return range_op_handler (MULT_EXPR).fold_range (r, type, lhs, op2);
2784 : return false;
2785 1141660 : }
2786 :
2787 :
2788 : class operator_lshift : public cross_product_operator
2789 : {
2790 : using range_operator::fold_range;
2791 : using range_operator::op1_range;
2792 : using range_operator::update_bitmask;
2793 : public:
2794 : virtual bool op1_range (irange &r, tree type, const irange &lhs,
2795 : const irange &op2, relation_trio rel = TRIO_VARYING)
2796 : const final override;
2797 : virtual bool fold_range (irange &r, tree type, const irange &op1,
2798 : const irange &op2, relation_trio rel = TRIO_VARYING)
2799 : const final override;
2800 :
2801 : virtual void wi_fold (irange &r, tree type,
2802 : const wide_int &lh_lb, const wide_int &lh_ub,
2803 : const wide_int &rh_lb,
2804 : const wide_int &rh_ub) const final override;
2805 : virtual bool wi_op_overflows (wide_int &res,
2806 : tree type,
2807 : const wide_int &,
2808 : const wide_int &) const final override;
2809 488738 : void update_bitmask (irange &r, const irange &lh,
2810 : const irange &rh) const final override
2811 488738 : { update_known_bitmask (r, LSHIFT_EXPR, lh, rh); }
2812 : // Check compatibility of LHS and op1.
2813 1272327 : bool operand_check_p (tree t1, tree t2, tree) const final override
2814 1272327 : { return range_compatible_p (t1, t2); }
2815 : } op_lshift;
2816 :
2817 : class operator_rshift : public cross_product_operator
2818 : {
2819 : using range_operator::fold_range;
2820 : using range_operator::op1_range;
2821 : using range_operator::lhs_op1_relation;
2822 : using range_operator::update_bitmask;
2823 : public:
2824 : virtual bool fold_range (irange &r, tree type, const irange &op1,
2825 : const irange &op2, relation_trio rel = TRIO_VARYING)
2826 : const final override;
2827 : virtual void wi_fold (irange &r, tree type,
2828 : const wide_int &lh_lb,
2829 : const wide_int &lh_ub,
2830 : const wide_int &rh_lb,
2831 : const wide_int &rh_ub) const final override;
2832 : virtual bool wi_op_overflows (wide_int &res,
2833 : tree type,
2834 : const wide_int &w0,
2835 : const wide_int &w1) const final override;
2836 : virtual bool op1_range (irange &, tree type, const irange &lhs,
2837 : const irange &op2, relation_trio rel = TRIO_VARYING)
2838 : const final override;
2839 : virtual relation_kind lhs_op1_relation (const irange &lhs, const irange &op1,
2840 : const irange &op2, relation_kind rel)
2841 : const final override;
2842 4164749 : void update_bitmask (irange &r, const irange &lh,
2843 : const irange &rh) const final override
2844 4164749 : { update_known_bitmask (r, RSHIFT_EXPR, lh, rh); }
2845 : // Check compatibility of LHS and op1.
2846 4147622 : bool operand_check_p (tree t1, tree t2, tree) const final override
2847 4147622 : { return range_compatible_p (t1, t2); }
2848 : } op_rshift;
2849 :
2850 :
2851 : relation_kind
2852 2719008 : operator_rshift::lhs_op1_relation (const irange &lhs ATTRIBUTE_UNUSED,
2853 : const irange &op1,
2854 : const irange &op2,
2855 : relation_kind) const
2856 : {
2857 : // If both operands range are >= 0, then the LHS <= op1.
2858 2719008 : if (!op1.undefined_p () && !op2.undefined_p ()
2859 5436852 : && wi::ge_p (op1.lower_bound (), 0, TYPE_SIGN (op1.type ()))
2860 7894184 : && wi::ge_p (op2.lower_bound (), 0, TYPE_SIGN (op2.type ())))
2861 2428786 : return VREL_LE;
2862 : return VREL_VARYING;
2863 : }
2864 :
2865 : bool
2866 2106740 : operator_lshift::fold_range (irange &r, tree type,
2867 : const irange &op1,
2868 : const irange &op2,
2869 : relation_trio rel) const
2870 : {
2871 2106740 : int_range_max shift_range;
2872 2106740 : if (!get_shift_range (shift_range, type, op2))
2873 : {
2874 1261 : if (op2.undefined_p ())
2875 932 : r.set_undefined ();
2876 : else
2877 329 : r.set_zero (type);
2878 : return true;
2879 : }
2880 :
2881 : // Transform left shifts by constants into multiplies.
2882 2105479 : if (shift_range.singleton_p ())
2883 : {
2884 1616715 : unsigned shift = shift_range.lower_bound ().to_uhwi ();
2885 1616715 : wide_int tmp = wi::set_bit_in_zero (shift, TYPE_PRECISION (type));
2886 1616715 : int_range<1> mult (type, tmp, tmp);
2887 :
2888 : // Force wrapping multiplication.
2889 1616715 : bool saved_flag_wrapv = flag_wrapv;
2890 1616715 : bool saved_flag_wrapv_pointer = flag_wrapv_pointer;
2891 1616715 : flag_wrapv = 1;
2892 1616715 : flag_wrapv_pointer = 1;
2893 1616715 : bool b = op_mult.fold_range (r, type, op1, mult);
2894 1616715 : flag_wrapv = saved_flag_wrapv;
2895 1616715 : flag_wrapv_pointer = saved_flag_wrapv_pointer;
2896 1616715 : return b;
2897 1616724 : }
2898 : else
2899 : // Otherwise, invoke the generic fold routine.
2900 488764 : return range_operator::fold_range (r, type, op1, shift_range, rel);
2901 2106740 : }
2902 :
2903 : void
2904 570253 : operator_lshift::wi_fold (irange &r, tree type,
2905 : const wide_int &lh_lb, const wide_int &lh_ub,
2906 : const wide_int &rh_lb, const wide_int &rh_ub) const
2907 : {
2908 570253 : signop sign = TYPE_SIGN (type);
2909 570253 : unsigned prec = TYPE_PRECISION (type);
2910 570253 : int overflow_pos = sign == SIGNED ? prec - 1 : prec;
2911 570253 : int bound_shift = overflow_pos - rh_ub.to_shwi ();
2912 : // If bound_shift == HOST_BITS_PER_WIDE_INT, the llshift can
2913 : // overflow. However, for that to happen, rh.max needs to be zero,
2914 : // which means rh is a singleton range of zero, which means we simply return
2915 : // [lh_lb, lh_ub] as the range.
2916 570253 : if (wi::eq_p (rh_ub, rh_lb) && wi::eq_p (rh_ub, 0))
2917 : {
2918 21485 : r = int_range<2> (type, lh_lb, lh_ub);
2919 21485 : return;
2920 : }
2921 :
2922 548768 : wide_int bound = wi::set_bit_in_zero (bound_shift, prec);
2923 548768 : wide_int complement = ~(bound - 1);
2924 548768 : wide_int low_bound, high_bound;
2925 548768 : bool in_bounds = false;
2926 :
2927 548768 : if (sign == UNSIGNED)
2928 : {
2929 264384 : low_bound = bound;
2930 264384 : high_bound = complement;
2931 264384 : if (wi::ltu_p (lh_ub, low_bound))
2932 : {
2933 : // [5, 6] << [1, 2] == [10, 24].
2934 : // We're shifting out only zeroes, the value increases
2935 : // monotonically.
2936 : in_bounds = true;
2937 : }
2938 86285 : else if (wi::ltu_p (high_bound, lh_lb))
2939 : {
2940 : // [0xffffff00, 0xffffffff] << [1, 2]
2941 : // == [0xfffffc00, 0xfffffffe].
2942 : // We're shifting out only ones, the value decreases
2943 : // monotonically.
2944 : in_bounds = true;
2945 : }
2946 : }
2947 : else
2948 : {
2949 : // [-1, 1] << [1, 2] == [-4, 4]
2950 284384 : low_bound = complement;
2951 284384 : high_bound = bound;
2952 284384 : if (wi::lts_p (lh_ub, high_bound)
2953 284384 : && wi::lts_p (low_bound, lh_lb))
2954 : {
2955 : // For non-negative numbers, we're shifting out only zeroes,
2956 : // the value increases monotonically. For negative numbers,
2957 : // we're shifting out only ones, the value decreases
2958 : // monotonically.
2959 : in_bounds = true;
2960 : }
2961 : }
2962 :
2963 : if (in_bounds)
2964 296269 : wi_cross_product (r, type, lh_lb, lh_ub, rh_lb, rh_ub);
2965 : else
2966 252499 : r.set_varying (type);
2967 548786 : }
2968 :
2969 : bool
2970 578691 : operator_lshift::wi_op_overflows (wide_int &res, tree type,
2971 : const wide_int &w0, const wide_int &w1) const
2972 : {
2973 578691 : signop sign = TYPE_SIGN (type);
2974 578691 : if (wi::neg_p (w1))
2975 : {
2976 : // It's unclear from the C standard whether shifts can overflow.
2977 : // The following code ignores overflow; perhaps a C standard
2978 : // interpretation ruling is needed.
2979 0 : res = wi::rshift (w0, -w1, sign);
2980 : }
2981 : else
2982 578691 : res = wi::lshift (w0, w1);
2983 578691 : return false;
2984 : }
2985 :
2986 : bool
2987 167906 : operator_lshift::op1_range (irange &r,
2988 : tree type,
2989 : const irange &lhs,
2990 : const irange &op2,
2991 : relation_trio) const
2992 : {
2993 167906 : if (lhs.undefined_p ())
2994 : return false;
2995 :
2996 167906 : if (!lhs.contains_zero_p ())
2997 25661 : r.set_nonzero (type);
2998 : else
2999 142245 : r.set_varying (type);
3000 :
3001 167906 : wide_int shift;
3002 167906 : if (op2.singleton_p (shift))
3003 : {
3004 160378 : if (wi::lt_p (shift, 0, SIGNED))
3005 : return false;
3006 160378 : if (wi::ge_p (shift, wi::uhwi (TYPE_PRECISION (type),
3007 160378 : TYPE_PRECISION (op2.type ())),
3008 : UNSIGNED))
3009 : return false;
3010 160378 : if (shift == 0)
3011 : {
3012 150 : r.intersect (lhs);
3013 150 : return true;
3014 : }
3015 :
3016 : // Work completely in unsigned mode to start.
3017 160228 : tree utype = type;
3018 160228 : int_range_max tmp_range;
3019 160228 : if (TYPE_SIGN (type) == SIGNED)
3020 : {
3021 10742 : int_range_max tmp = lhs;
3022 10742 : utype = unsigned_type_for (type);
3023 10742 : range_cast (tmp, utype);
3024 10742 : op_rshift.fold_range (tmp_range, utype, tmp, op2);
3025 10742 : }
3026 : else
3027 149486 : op_rshift.fold_range (tmp_range, utype, lhs, op2);
3028 :
3029 : // If no valid range is found, abort the calculation and return falae.
3030 160228 : if (tmp_range.undefined_p ())
3031 : return false;
3032 :
3033 : // Start with ranges which can produce the LHS by right shifting the
3034 : // result by the shift amount.
3035 : // ie [0x08, 0xF0] = op1 << 2 will start with
3036 : // [00001000, 11110000] = op1 << 2
3037 : // [0x02, 0x4C] aka [00000010, 00111100]
3038 :
3039 : // Then create a range from the LB with the least significant upper bit
3040 : // set, to the upper bound with all the bits set.
3041 : // This would be [0x42, 0xFC] aka [01000010, 11111100].
3042 :
3043 : // Ideally we do this for each subrange, but just lump them all for now.
3044 160228 : unsigned low_bits = TYPE_PRECISION (utype) - shift.to_uhwi ();
3045 160228 : wide_int up_mask = wi::mask (low_bits, true, TYPE_PRECISION (utype));
3046 160228 : wide_int new_ub = wi::bit_or (up_mask, tmp_range.upper_bound ());
3047 160228 : wide_int new_lb = wi::set_bit (tmp_range.lower_bound (), low_bits);
3048 160228 : int_range<2> fill_range (utype, new_lb, new_ub);
3049 160228 : tmp_range.union_ (fill_range);
3050 :
3051 160228 : if (utype != type)
3052 10742 : range_cast (tmp_range, type);
3053 :
3054 160228 : r.intersect (tmp_range);
3055 160228 : return true;
3056 160228 : }
3057 :
3058 7528 : return !r.varying_p ();
3059 167906 : }
3060 :
3061 : bool
3062 1248425 : operator_rshift::op1_range (irange &r,
3063 : tree type,
3064 : const irange &lhs,
3065 : const irange &op2,
3066 : relation_trio) const
3067 : {
3068 1248425 : if (lhs.undefined_p ())
3069 : return false;
3070 1248425 : wide_int shift;
3071 1248425 : if (op2.singleton_p (shift))
3072 : {
3073 : // Ignore nonsensical shifts.
3074 1219564 : unsigned prec = TYPE_PRECISION (type);
3075 2439128 : if (wi::ge_p (shift,
3076 1219564 : wi::uhwi (prec, TYPE_PRECISION (op2.type ())),
3077 : UNSIGNED))
3078 : return false;
3079 1219564 : if (shift == 0)
3080 : {
3081 151 : r = lhs;
3082 151 : return true;
3083 : }
3084 :
3085 : // Folding the original operation may discard some impossible
3086 : // ranges from the LHS.
3087 1219413 : int_range_max lhs_refined;
3088 1219413 : op_rshift.fold_range (lhs_refined, type, int_range<1> (type), op2);
3089 1219413 : lhs_refined.intersect (lhs);
3090 1219413 : if (lhs_refined.undefined_p ())
3091 : {
3092 4 : r.set_undefined ();
3093 4 : return true;
3094 : }
3095 1219409 : int_range_max shift_range (op2.type (), shift, shift);
3096 1219409 : int_range_max lb, ub;
3097 1219409 : op_lshift.fold_range (lb, type, lhs_refined, shift_range);
3098 : // LHS
3099 : // 0000 0111 = OP1 >> 3
3100 : //
3101 : // OP1 is anything from 0011 1000 to 0011 1111. That is, a
3102 : // range from LHS<<3 plus a mask of the 3 bits we shifted on the
3103 : // right hand side (0x07).
3104 1219409 : wide_int mask = wi::mask (shift.to_uhwi (), false, prec);
3105 1219409 : int_range_max mask_range (type,
3106 1219409 : wi::zero (TYPE_PRECISION (type)),
3107 1219409 : mask);
3108 1219409 : op_plus.fold_range (ub, type, lb, mask_range);
3109 1219409 : r = lb;
3110 1219409 : r.union_ (ub);
3111 1219409 : if (!lhs_refined.contains_zero_p ())
3112 : {
3113 640928 : if (!mask_range.invert ())
3114 : return false;
3115 640928 : r.intersect (mask_range);
3116 : }
3117 : return true;
3118 1219413 : }
3119 : return false;
3120 1248425 : }
3121 :
3122 : bool
3123 13862163 : operator_rshift::wi_op_overflows (wide_int &res,
3124 : tree type,
3125 : const wide_int &w0,
3126 : const wide_int &w1) const
3127 : {
3128 13862163 : signop sign = TYPE_SIGN (type);
3129 13862163 : if (wi::neg_p (w1))
3130 0 : res = wi::lshift (w0, -w1);
3131 : else
3132 : {
3133 : // It's unclear from the C standard whether shifts can overflow.
3134 : // The following code ignores overflow; perhaps a C standard
3135 : // interpretation ruling is needed.
3136 13862254 : res = wi::rshift (w0, w1, sign);
3137 : }
3138 13862163 : return false;
3139 : }
3140 :
3141 : bool
3142 4166252 : operator_rshift::fold_range (irange &r, tree type,
3143 : const irange &op1,
3144 : const irange &op2,
3145 : relation_trio rel) const
3146 : {
3147 4166252 : int_range_max shift;
3148 4166252 : if (!get_shift_range (shift, type, op2))
3149 : {
3150 517 : if (op2.undefined_p ())
3151 216 : r.set_undefined ();
3152 : else
3153 301 : r.set_zero (type);
3154 : return true;
3155 : }
3156 :
3157 4165735 : return range_operator::fold_range (r, type, op1, shift, rel);
3158 4166252 : }
3159 :
3160 : void
3161 5021467 : operator_rshift::wi_fold (irange &r, tree type,
3162 : const wide_int &lh_lb, const wide_int &lh_ub,
3163 : const wide_int &rh_lb, const wide_int &rh_ub) const
3164 : {
3165 5021467 : wi_cross_product (r, type, lh_lb, lh_ub, rh_lb, rh_ub);
3166 5021467 : }
3167 :
3168 :
3169 : // Add a partial equivalence between the LHS and op1 for casts.
3170 :
3171 : relation_kind
3172 25350213 : operator_cast::lhs_op1_relation (const irange &lhs,
3173 : const irange &op1,
3174 : const irange &op2 ATTRIBUTE_UNUSED,
3175 : relation_kind) const
3176 : {
3177 25350213 : if (lhs.undefined_p () || op1.undefined_p ())
3178 : return VREL_VARYING;
3179 25325678 : unsigned lhs_prec = TYPE_PRECISION (lhs.type ());
3180 25325678 : unsigned op1_prec = TYPE_PRECISION (op1.type ());
3181 : // If the result gets sign extended into a larger type check first if this
3182 : // qualifies as a partial equivalence.
3183 25325678 : if (TYPE_SIGN (op1.type ()) == SIGNED && lhs_prec > op1_prec)
3184 : {
3185 : // If the result is sign extended, and the LHS is larger than op1,
3186 : // check if op1's range can be negative as the sign extension will
3187 : // cause the upper bits to be 1 instead of 0, invalidating the PE.
3188 4116020 : int_range<3> negs = range_negatives (op1.type ());
3189 4116020 : negs.intersect (op1);
3190 4116020 : if (!negs.undefined_p ())
3191 2845210 : return VREL_VARYING;
3192 4116020 : }
3193 :
3194 22480468 : unsigned prec = MIN (lhs_prec, op1_prec);
3195 22480468 : return bits_to_pe (prec);
3196 : }
3197 :
3198 : // Return TRUE if casting from INNER to OUTER is a truncating cast.
3199 :
3200 : inline bool
3201 96915017 : operator_cast::truncating_cast_p (const irange &inner,
3202 : const irange &outer) const
3203 : {
3204 96915017 : return TYPE_PRECISION (outer.type ()) < TYPE_PRECISION (inner.type ());
3205 : }
3206 :
3207 : // Return TRUE if [MIN,MAX] is inside the domain of RANGE's type.
3208 :
3209 : bool
3210 82005566 : operator_cast::inside_domain_p (const wide_int &min,
3211 : const wide_int &max,
3212 : const irange &range) const
3213 : {
3214 82005566 : wide_int domain_min = irange_val_min (range.type ());
3215 82005566 : wide_int domain_max = irange_val_max (range.type ());
3216 82005566 : signop domain_sign = TYPE_SIGN (range.type ());
3217 82005566 : return (wi::le_p (min, domain_max, domain_sign)
3218 82005566 : && wi::le_p (max, domain_max, domain_sign)
3219 82005566 : && wi::ge_p (min, domain_min, domain_sign)
3220 164011132 : && wi::ge_p (max, domain_min, domain_sign));
3221 82005566 : }
3222 :
3223 :
3224 : // Helper for fold_range which work on a pair at a time.
3225 :
3226 : void
3227 85372269 : operator_cast::fold_pair (irange &r, unsigned index,
3228 : const irange &inner,
3229 : const irange &outer) const
3230 : {
3231 85372269 : tree inner_type = inner.type ();
3232 85372269 : tree outer_type = outer.type ();
3233 85372269 : signop inner_sign = TYPE_SIGN (inner_type);
3234 85372269 : unsigned outer_prec = TYPE_PRECISION (outer_type);
3235 :
3236 : // check to see if casting from INNER to OUTER is a conversion that
3237 : // fits in the resulting OUTER type.
3238 85372269 : wide_int inner_lb = inner.lower_bound (index);
3239 85372269 : wide_int inner_ub = inner.upper_bound (index);
3240 85372269 : if (truncating_cast_p (inner, outer))
3241 : {
3242 : // We may be able to accommodate a truncating cast if the
3243 : // resulting range can be represented in the target type...
3244 17348926 : if (wi::rshift (wi::sub (inner_ub, inner_lb),
3245 8674463 : wi::uhwi (outer_prec, TYPE_PRECISION (inner.type ())),
3246 26023389 : inner_sign) != 0)
3247 : {
3248 3366703 : r.set_varying (outer_type);
3249 3366703 : return;
3250 : }
3251 : }
3252 : // ...but we must still verify that the final range fits in the
3253 : // domain. This catches -fstrict-enum restrictions where the domain
3254 : // range is smaller than what fits in the underlying type.
3255 82005566 : wide_int min = wide_int::from (inner_lb, outer_prec, inner_sign);
3256 82005566 : wide_int max = wide_int::from (inner_ub, outer_prec, inner_sign);
3257 82005566 : if (inside_domain_p (min, max, outer))
3258 82005566 : create_possibly_reversed_range (r, outer_type, min, max);
3259 : else
3260 0 : r.set_varying (outer_type);
3261 85375343 : }
3262 :
3263 :
3264 : bool
3265 69117140 : operator_cast::fold_range (irange &r, tree type ATTRIBUTE_UNUSED,
3266 : const irange &inner,
3267 : const irange &outer,
3268 : relation_trio) const
3269 : {
3270 69117140 : if (empty_range_varying (r, type, inner, outer))
3271 36481 : return true;
3272 :
3273 69080659 : gcc_checking_assert (outer.varying_p ());
3274 69080659 : gcc_checking_assert (inner.num_pairs () > 0);
3275 :
3276 : // Avoid a temporary by folding the first pair directly into the result.
3277 69080659 : fold_pair (r, 0, inner, outer);
3278 :
3279 : // Then process any additional pairs by unioning with their results.
3280 153706461 : for (unsigned x = 1; x < inner.num_pairs (); ++x)
3281 : {
3282 16291610 : int_range_max tmp;
3283 16291610 : fold_pair (tmp, x, inner, outer);
3284 16291610 : r.union_ (tmp);
3285 : // If we hit varying, go update the bitmask.
3286 16291610 : if (r.varying_p ())
3287 : break;
3288 16291610 : }
3289 :
3290 69080659 : update_bitmask (r, inner, outer);
3291 69080659 : return true;
3292 : }
3293 :
3294 : void
3295 69080659 : operator_cast::update_bitmask (irange &r, const irange &lh,
3296 : const irange &rh) const
3297 : {
3298 69080659 : update_known_bitmask (r, CONVERT_EXPR, lh, rh);
3299 69080659 : }
3300 :
3301 : bool
3302 11542748 : operator_cast::op1_range (irange &r, tree type,
3303 : const irange &lhs,
3304 : const irange &op2,
3305 : relation_trio) const
3306 : {
3307 11542748 : if (lhs.undefined_p ())
3308 : return false;
3309 11542748 : tree lhs_type = lhs.type ();
3310 11542748 : gcc_checking_assert (types_compatible_p (op2.type(), type));
3311 :
3312 : // If we are calculating a pointer, shortcut to what we really care about.
3313 11542748 : if (POINTER_TYPE_P (type))
3314 : {
3315 : // Conversion from other pointers or a constant (including 0/NULL)
3316 : // are straightforward.
3317 0 : if (POINTER_TYPE_P (lhs.type ())
3318 0 : || (lhs.singleton_p ()
3319 0 : && TYPE_PRECISION (lhs.type ()) >= TYPE_PRECISION (type)))
3320 : {
3321 0 : r = lhs;
3322 0 : range_cast (r, type);
3323 : }
3324 : else
3325 : {
3326 : // If the LHS is not a pointer nor a singleton, then it is
3327 : // either VARYING or non-zero.
3328 0 : if (!lhs.undefined_p () && !lhs.contains_zero_p ())
3329 0 : r.set_nonzero (type);
3330 : else
3331 0 : r.set_varying (type);
3332 : }
3333 0 : r.intersect (op2);
3334 0 : return true;
3335 : }
3336 :
3337 11542748 : if (truncating_cast_p (op2, lhs))
3338 : {
3339 1619019 : if (lhs.varying_p ())
3340 160663 : r.set_varying (type);
3341 : else
3342 : {
3343 : // We want to insert the LHS as an unsigned value since it
3344 : // would not trigger the signed bit of the larger type.
3345 1458356 : int_range_max converted_lhs = lhs;
3346 1458356 : range_cast (converted_lhs, unsigned_type_for (lhs_type));
3347 1458356 : range_cast (converted_lhs, type);
3348 : // Start by building the positive signed outer range for the type.
3349 1458356 : wide_int lim = wi::set_bit_in_zero (TYPE_PRECISION (lhs_type),
3350 2916712 : TYPE_PRECISION (type));
3351 1458356 : create_possibly_reversed_range (r, type, lim,
3352 1458356 : wi::max_value (TYPE_PRECISION (type),
3353 : SIGNED));
3354 : // For the signed part, we need to simply union the 2 ranges now.
3355 1458356 : r.union_ (converted_lhs);
3356 :
3357 : // Create maximal negative number outside of LHS bits.
3358 1458356 : lim = wi::mask (TYPE_PRECISION (lhs_type), true,
3359 2916712 : TYPE_PRECISION (type));
3360 : // Add this to the unsigned LHS range(s).
3361 1458356 : int_range_max lim_range (type, lim, lim);
3362 1458356 : int_range_max lhs_neg;
3363 1458356 : range_op_handler (PLUS_EXPR).fold_range (lhs_neg, type,
3364 : converted_lhs, lim_range);
3365 : // lhs_neg now has all the negative versions of the LHS.
3366 : // Now union in all the values from SIGNED MIN (0x80000) to
3367 : // lim-1 in order to fill in all the ranges with the upper
3368 : // bits set.
3369 :
3370 : // PR 97317. If the lhs has only 1 bit less precision than the rhs,
3371 : // we don't need to create a range from min to lim-1
3372 : // calculate neg range traps trying to create [lim, lim - 1].
3373 1458356 : wide_int min_val = wi::min_value (TYPE_PRECISION (type), SIGNED);
3374 1458356 : if (lim != min_val)
3375 : {
3376 1456412 : int_range_max neg (type,
3377 2912824 : wi::min_value (TYPE_PRECISION (type),
3378 : SIGNED),
3379 2912824 : lim - 1);
3380 1456412 : lhs_neg.union_ (neg);
3381 1456412 : }
3382 : // And finally, munge the signed and unsigned portions.
3383 1458356 : r.union_ (lhs_neg);
3384 1458359 : }
3385 : // And intersect with any known value passed in the extra operand.
3386 1619019 : r.intersect (op2);
3387 1619019 : if (r.undefined_p ())
3388 : return true;
3389 :
3390 : // Now create a bitmask indicating that the lower bit must match the
3391 : // bits in the LHS. Zero-extend LHS bitmask to precision of op1.
3392 1618907 : irange_bitmask bm = lhs.get_bitmask ();
3393 3237814 : wide_int mask = wide_int::from (bm.mask (), TYPE_PRECISION (type),
3394 3237814 : UNSIGNED);
3395 3237814 : wide_int value = wide_int::from (bm.value (), TYPE_PRECISION (type),
3396 3237814 : UNSIGNED);
3397 :
3398 : // Set then additional unknown bits in mask.
3399 1618907 : wide_int lim = wi::mask (TYPE_PRECISION (lhs_type), true,
3400 3237814 : TYPE_PRECISION (type));
3401 1618907 : mask = mask | lim;
3402 :
3403 : // Now set the new bitmask for the range.
3404 1618907 : irange_bitmask new_bm (value, mask);
3405 1618907 : r.update_bitmask (new_bm);
3406 1618907 : return true;
3407 1618916 : }
3408 :
3409 9923729 : int_range_max tmp;
3410 9923729 : if (TYPE_PRECISION (lhs_type) == TYPE_PRECISION (type))
3411 7319512 : tmp = lhs;
3412 : else
3413 : {
3414 : // The cast is not truncating, and the range is restricted to
3415 : // the range of the RHS by this assignment.
3416 : //
3417 : // Cast the range of the RHS to the type of the LHS.
3418 2604217 : fold_range (tmp, lhs_type, int_range<1> (type), int_range<1> (lhs_type));
3419 : // Intersect this with the LHS range will produce the range,
3420 : // which will be cast to the RHS type before returning.
3421 2604217 : tmp.intersect (lhs);
3422 : }
3423 :
3424 : // Cast the calculated range to the type of the RHS.
3425 9923729 : fold_range (r, type, tmp, int_range<1> (type));
3426 9923729 : return true;
3427 9923729 : }
3428 :
3429 : // VIEW_CONVERT_EXPR works like a cast between integral values.
3430 : // If the number of bits are not the same, behaviour is undefined,
3431 : // so cast behaviour still works.
3432 :
3433 : bool
3434 272303 : operator_view::fold_range (irange &r, tree type,
3435 : const irange &op1, const irange &op2,
3436 : relation_trio rel) const
3437 : {
3438 272303 : return m_cast.fold_range (r, type, op1, op2, rel);
3439 : }
3440 :
3441 : bool
3442 0 : operator_view::fold_range (prange &r, tree type,
3443 : const prange &op1, const prange &op2,
3444 : relation_trio rel) const
3445 : {
3446 0 : return m_cast.fold_range (r, type, op1, op2, rel);
3447 : }
3448 : bool
3449 261423 : operator_view::fold_range (irange &r, tree type,
3450 : const prange &op1, const irange &op2,
3451 : relation_trio rel) const
3452 : {
3453 261423 : return m_cast.fold_range (r, type, op1, op2, rel);
3454 : }
3455 :
3456 : bool
3457 0 : operator_view::fold_range (prange &r, tree type,
3458 : const irange &op1, const prange &op2,
3459 : relation_trio rel) const
3460 : {
3461 0 : return m_cast.fold_range (r, type, op1, op2, rel);
3462 : }
3463 :
3464 : bool
3465 10223 : operator_view::op1_range (irange &r, tree type,
3466 : const irange &lhs, const irange &op2,
3467 : relation_trio rel) const
3468 : {
3469 10223 : return m_cast.op1_range (r, type, lhs, op2, rel);
3470 : }
3471 :
3472 : bool
3473 0 : operator_view::op1_range (prange &r, tree type,
3474 : const prange &lhs, const prange &op2,
3475 : relation_trio rel) const
3476 : {
3477 0 : return m_cast.op1_range (r, type, lhs, op2, rel);
3478 : }
3479 :
3480 : bool
3481 0 : operator_view::op1_range (irange &r, tree type,
3482 : const prange &lhs, const irange &op2,
3483 : relation_trio rel) const
3484 : {
3485 0 : return m_cast.op1_range (r, type, lhs, op2, rel);
3486 : }
3487 :
3488 : bool
3489 0 : operator_view::op1_range (prange &r, tree type,
3490 : const irange &lhs, const prange &op2,
3491 : relation_trio rel) const
3492 : {
3493 0 : return m_cast.op1_range (r, type, lhs, op2, rel);
3494 : }
3495 :
3496 : void
3497 0 : operator_view::update_bitmask (irange &r, const irange &lh,
3498 : const irange &rh) const
3499 : {
3500 0 : m_cast.update_bitmask (r, lh, rh);
3501 0 : }
3502 :
3503 :
3504 : class operator_logical_and : public range_operator
3505 : {
3506 : using range_operator::fold_range;
3507 : using range_operator::op1_range;
3508 : using range_operator::op2_range;
3509 : public:
3510 : bool fold_range (irange &r, tree type,
3511 : const irange &lh,
3512 : const irange &rh,
3513 : relation_trio rel = TRIO_VARYING) const final override;
3514 : bool op1_range (irange &r, tree type,
3515 : const irange &lhs,
3516 : const irange &op2,
3517 : relation_trio rel = TRIO_VARYING) const final override;
3518 : bool op2_range (irange &r, tree type,
3519 : const irange &lhs,
3520 : const irange &op1,
3521 : relation_trio rel = TRIO_VARYING) const final override;
3522 : // Check compatibility of all operands.
3523 0 : bool operand_check_p (tree t1, tree t2, tree t3) const final override
3524 0 : { return range_compatible_p (t1, t2) && range_compatible_p (t1, t3); }
3525 : } op_logical_and;
3526 :
3527 : bool
3528 0 : operator_logical_and::fold_range (irange &r, tree type,
3529 : const irange &lh,
3530 : const irange &rh,
3531 : relation_trio) const
3532 : {
3533 0 : if (empty_range_varying (r, type, lh, rh))
3534 0 : return true;
3535 :
3536 : // Precision of LHS and both operands must match.
3537 0 : if (TYPE_PRECISION (lh.type ()) != TYPE_PRECISION (type)
3538 0 : || TYPE_PRECISION (type) != TYPE_PRECISION (rh.type ()))
3539 : return false;
3540 :
3541 : // 0 && anything is 0.
3542 0 : if ((wi::eq_p (lh.lower_bound (), 0) && wi::eq_p (lh.upper_bound (), 0))
3543 0 : || (wi::eq_p (lh.lower_bound (), 0) && wi::eq_p (rh.upper_bound (), 0)))
3544 0 : r = range_false (type);
3545 0 : else if (lh.contains_zero_p () || rh.contains_zero_p ())
3546 : // To reach this point, there must be a logical 1 on each side, and
3547 : // the only remaining question is whether there is a zero or not.
3548 0 : r = range_true_and_false (type);
3549 : else
3550 0 : r = range_true (type);
3551 : return true;
3552 : }
3553 :
3554 : bool
3555 965346 : operator_logical_and::op1_range (irange &r, tree type,
3556 : const irange &lhs,
3557 : const irange &op2,
3558 : relation_trio) const
3559 : {
3560 965346 : switch (get_bool_state (r, lhs, type))
3561 : {
3562 552905 : case BRS_TRUE:
3563 : // A TRUE result means both sides of the AND must be true.
3564 552905 : r = range_true (type);
3565 552905 : return true;
3566 :
3567 411369 : case BRS_FALSE:
3568 : // A FALSE result when op2 is TRUE, must have op1 FALSE.
3569 411369 : if (!op2.contains_p (wi::zero (TYPE_PRECISION (op2.type ()))))
3570 : {
3571 9980 : r = range_false (type);
3572 9980 : return true;
3573 : }
3574 : break;
3575 :
3576 : default:
3577 : break;
3578 : }
3579 :
3580 : // Any other result means we cannot be sure of any result.
3581 402461 : r = range_true_and_false (type);
3582 402461 : return true;
3583 : }
3584 :
3585 : bool
3586 0 : operator_logical_and::op2_range (irange &r, tree type,
3587 : const irange &lhs,
3588 : const irange &op1,
3589 : relation_trio) const
3590 : {
3591 0 : return operator_logical_and::op1_range (r, type, lhs, op1);
3592 : }
3593 :
3594 :
3595 : void
3596 7767913 : operator_bitwise_and::update_bitmask (irange &r, const irange &lh,
3597 : const irange &rh) const
3598 : {
3599 7767913 : update_known_bitmask (r, BIT_AND_EXPR, lh, rh);
3600 7767913 : }
3601 :
3602 : // Optimize BIT_AND_EXPR, BIT_IOR_EXPR and BIT_XOR_EXPR of signed types
3603 : // by considering the number of leading redundant sign bit copies.
3604 : // clrsb (X op Y) = min (clrsb (X), clrsb (Y)), so for example
3605 : // [-1, 0] op [-1, 0] is [-1, 0] (where nonzero_bits doesn't help).
3606 : static bool
3607 195667 : wi_optimize_signed_bitwise_op (irange &r, tree type,
3608 : const wide_int &lh_lb, const wide_int &lh_ub,
3609 : const wide_int &rh_lb, const wide_int &rh_ub)
3610 : {
3611 391334 : int lh_clrsb = MIN (wi::clrsb (lh_lb), wi::clrsb (lh_ub));
3612 391334 : int rh_clrsb = MIN (wi::clrsb (rh_lb), wi::clrsb (rh_ub));
3613 195667 : int new_clrsb = MIN (lh_clrsb, rh_clrsb);
3614 195667 : if (new_clrsb == 0)
3615 : return false;
3616 13899 : int type_prec = TYPE_PRECISION (type);
3617 13899 : int rprec = (type_prec - new_clrsb) - 1;
3618 13899 : value_range_with_overflow (r, type,
3619 27798 : wi::mask (rprec, true, type_prec),
3620 13899 : wi::mask (rprec, false, type_prec));
3621 13899 : return true;
3622 : }
3623 :
3624 : // An AND of 8,16, 32 or 64 bits can produce a partial equivalence between
3625 : // the LHS and op1.
3626 :
3627 : relation_kind
3628 6947571 : operator_bitwise_and::lhs_op1_relation (const irange &lhs,
3629 : const irange &op1,
3630 : const irange &op2,
3631 : relation_kind rel) const
3632 : {
3633 6947571 : if (lhs.undefined_p () || op1.undefined_p () || op2.undefined_p ())
3634 : return VREL_VARYING;
3635 : // When x == y, x & y is x.
3636 6941836 : if (rel == VREL_EQ)
3637 : return VREL_EQ;
3638 6941833 : if (!op2.singleton_p ())
3639 : return VREL_VARYING;
3640 : // if val == 0xff or 0xFFFF OR 0Xffffffff OR 0Xffffffffffffffff, return TRUE
3641 3867779 : int prec1 = TYPE_PRECISION (op1.type ());
3642 3867779 : int prec2 = TYPE_PRECISION (op2.type ());
3643 3867779 : int mask_prec = 0;
3644 3867779 : wide_int mask = op2.lower_bound ();
3645 3867779 : if (wi::eq_p (mask, wi::mask (8, false, prec2)))
3646 : mask_prec = 8;
3647 3774532 : else if (wi::eq_p (mask, wi::mask (16, false, prec2)))
3648 : mask_prec = 16;
3649 3756896 : else if (wi::eq_p (mask, wi::mask (32, false, prec2)))
3650 : mask_prec = 32;
3651 3581166 : else if (wi::eq_p (mask, wi::mask (64, false, prec2)))
3652 : mask_prec = 64;
3653 3867779 : return bits_to_pe (MIN (prec1, mask_prec));
3654 3867779 : }
3655 :
3656 : // Optimize BIT_AND_EXPR and BIT_IOR_EXPR in terms of a mask if
3657 : // possible. Basically, see if we can optimize:
3658 : //
3659 : // [LB, UB] op Z
3660 : // into:
3661 : // [LB op Z, UB op Z]
3662 : //
3663 : // If the optimization was successful, accumulate the range in R and
3664 : // return TRUE.
3665 :
3666 : static bool
3667 23719437 : wi_optimize_and_or (irange &r,
3668 : enum tree_code code,
3669 : tree type,
3670 : const wide_int &lh_lb, const wide_int &lh_ub,
3671 : const wide_int &rh_lb, const wide_int &rh_ub)
3672 : {
3673 : // Calculate the singleton mask among the ranges, if any.
3674 23719437 : wide_int lower_bound, upper_bound, mask;
3675 23719437 : if (wi::eq_p (rh_lb, rh_ub))
3676 : {
3677 21954899 : mask = rh_lb;
3678 21954899 : lower_bound = lh_lb;
3679 21954899 : upper_bound = lh_ub;
3680 : }
3681 1764538 : else if (wi::eq_p (lh_lb, lh_ub))
3682 : {
3683 358592 : mask = lh_lb;
3684 358592 : lower_bound = rh_lb;
3685 358592 : upper_bound = rh_ub;
3686 : }
3687 : else
3688 : return false;
3689 :
3690 : // If Z is a constant which (for op | its bitwise not) has n
3691 : // consecutive least significant bits cleared followed by m 1
3692 : // consecutive bits set immediately above it and either
3693 : // m + n == precision, or (x >> (m + n)) == (y >> (m + n)).
3694 : //
3695 : // The least significant n bits of all the values in the range are
3696 : // cleared or set, the m bits above it are preserved and any bits
3697 : // above these are required to be the same for all values in the
3698 : // range.
3699 22313491 : wide_int w = mask;
3700 22313491 : int m = 0, n = 0;
3701 22313491 : if (code == BIT_IOR_EXPR)
3702 6495331 : w = ~w;
3703 22313491 : if (wi::eq_p (w, 0))
3704 7595507 : n = w.get_precision ();
3705 : else
3706 : {
3707 14717984 : n = wi::ctz (w);
3708 14717990 : w = ~(w | wi::mask (n, false, w.get_precision ()));
3709 14717984 : if (wi::eq_p (w, 0))
3710 8931727 : m = w.get_precision () - n;
3711 : else
3712 5786257 : m = wi::ctz (w) - n;
3713 : }
3714 22313491 : wide_int new_mask = wi::mask (m + n, true, w.get_precision ());
3715 22313497 : if ((new_mask & lower_bound) != (new_mask & upper_bound))
3716 : return false;
3717 :
3718 17390585 : wide_int res_lb, res_ub;
3719 17390585 : if (code == BIT_AND_EXPR)
3720 : {
3721 11121471 : res_lb = wi::bit_and (lower_bound, mask);
3722 11121471 : res_ub = wi::bit_and (upper_bound, mask);
3723 : }
3724 6269114 : else if (code == BIT_IOR_EXPR)
3725 : {
3726 6269114 : res_lb = wi::bit_or (lower_bound, mask);
3727 6269114 : res_ub = wi::bit_or (upper_bound, mask);
3728 : }
3729 : else
3730 0 : gcc_unreachable ();
3731 17390585 : value_range_with_overflow (r, type, res_lb, res_ub);
3732 :
3733 : // Furthermore, if the mask is non-zero, an IOR cannot contain zero.
3734 17390585 : if (code == BIT_IOR_EXPR && wi::ne_p (mask, 0))
3735 : {
3736 3178147 : int_range<2> tmp;
3737 3178147 : tmp.set_nonzero (type);
3738 3178147 : r.intersect (tmp);
3739 3178147 : }
3740 17390585 : return true;
3741 63423519 : }
3742 :
3743 : // For range [LB, UB] compute two wide_int bit masks.
3744 : //
3745 : // In the MAYBE_NONZERO bit mask, if some bit is unset, it means that
3746 : // for all numbers in the range the bit is 0, otherwise it might be 0
3747 : // or 1.
3748 : //
3749 : // In the MUSTBE_NONZERO bit mask, if some bit is set, it means that
3750 : // for all numbers in the range the bit is 1, otherwise it might be 0
3751 : // or 1.
3752 :
3753 : void
3754 13713317 : wi_set_zero_nonzero_bits (tree type,
3755 : const wide_int &lb, const wide_int &ub,
3756 : wide_int &maybe_nonzero,
3757 : wide_int &mustbe_nonzero)
3758 : {
3759 13713317 : signop sign = TYPE_SIGN (type);
3760 :
3761 13713317 : if (wi::eq_p (lb, ub))
3762 5414883 : maybe_nonzero = mustbe_nonzero = lb;
3763 8298434 : else if (wi::ge_p (lb, 0, sign) || wi::lt_p (ub, 0, sign))
3764 : {
3765 7842199 : wide_int xor_mask = lb ^ ub;
3766 7842199 : maybe_nonzero = lb | ub;
3767 7842199 : mustbe_nonzero = lb & ub;
3768 7842199 : if (xor_mask != 0)
3769 : {
3770 7842199 : wide_int mask = wi::mask (wi::floor_log2 (xor_mask), false,
3771 15684398 : maybe_nonzero.get_precision ());
3772 7842199 : maybe_nonzero = maybe_nonzero | mask;
3773 7842204 : mustbe_nonzero = wi::bit_and_not (mustbe_nonzero, mask);
3774 7842199 : }
3775 7842199 : }
3776 : else
3777 : {
3778 456235 : maybe_nonzero = wi::minus_one (lb.get_precision ());
3779 456235 : mustbe_nonzero = wi::zero (lb.get_precision ());
3780 : }
3781 13713317 : }
3782 :
3783 : void
3784 17181054 : operator_bitwise_and::wi_fold (irange &r, tree type,
3785 : const wide_int &lh_lb,
3786 : const wide_int &lh_ub,
3787 : const wide_int &rh_lb,
3788 : const wide_int &rh_ub) const
3789 : {
3790 : // The AND algorithm does not handle complex signed operations well.
3791 : // If a signed range crosses the boundary between signed and unsigned
3792 : // process it as 2 ranges and union the results.
3793 17181054 : if (TYPE_SIGN (type) == SIGNED
3794 17181054 : && wi::neg_p (lh_lb, SIGNED) != wi::neg_p (lh_ub, SIGNED))
3795 : {
3796 641824 : int prec = TYPE_PRECISION (type);
3797 641824 : int_range_max tmp;
3798 : // Process [lh_lb, -1]
3799 641824 : wi_fold (tmp, type, lh_lb, wi::minus_one (prec), rh_lb, rh_ub);
3800 : // Now Process [0, rh_ub]
3801 641824 : wi_fold (r, type, wi::zero (prec), lh_ub, rh_lb, rh_ub);
3802 641824 : r.union_ (tmp);
3803 641824 : return;
3804 641824 : }
3805 :
3806 16539230 : if (wi_optimize_and_or (r, BIT_AND_EXPR, type, lh_lb, lh_ub, rh_lb, rh_ub))
3807 : return;
3808 :
3809 5417759 : wide_int maybe_nonzero_lh, mustbe_nonzero_lh;
3810 5417759 : wide_int maybe_nonzero_rh, mustbe_nonzero_rh;
3811 5417759 : wi_set_zero_nonzero_bits (type, lh_lb, lh_ub,
3812 : maybe_nonzero_lh, mustbe_nonzero_lh);
3813 5417759 : wi_set_zero_nonzero_bits (type, rh_lb, rh_ub,
3814 : maybe_nonzero_rh, mustbe_nonzero_rh);
3815 :
3816 5417759 : wide_int new_lb = mustbe_nonzero_lh & mustbe_nonzero_rh;
3817 5417759 : wide_int new_ub = maybe_nonzero_lh & maybe_nonzero_rh;
3818 5417759 : signop sign = TYPE_SIGN (type);
3819 5417759 : unsigned prec = TYPE_PRECISION (type);
3820 : // If both input ranges contain only negative values, we can
3821 : // truncate the result range maximum to the minimum of the
3822 : // input range maxima.
3823 5417759 : if (wi::lt_p (lh_ub, 0, sign) && wi::lt_p (rh_ub, 0, sign))
3824 : {
3825 46149 : new_ub = wi::min (new_ub, lh_ub, sign);
3826 46149 : new_ub = wi::min (new_ub, rh_ub, sign);
3827 : }
3828 : // If either input range contains only non-negative values
3829 : // we can truncate the result range maximum to the respective
3830 : // maximum of the input range.
3831 5417759 : if (wi::ge_p (lh_lb, 0, sign))
3832 4640201 : new_ub = wi::min (new_ub, lh_ub, sign);
3833 5417759 : if (wi::ge_p (rh_lb, 0, sign))
3834 5196043 : new_ub = wi::min (new_ub, rh_ub, sign);
3835 : // PR68217: In case of signed & sign-bit-CST should
3836 : // result in [-INF, 0] instead of [-INF, INF].
3837 5417759 : if (wi::gt_p (new_lb, new_ub, sign))
3838 : {
3839 56079 : wide_int sign_bit = wi::set_bit_in_zero (prec - 1, prec);
3840 56079 : if (sign == SIGNED
3841 56079 : && ((wi::eq_p (lh_lb, lh_ub)
3842 78 : && !wi::cmps (lh_lb, sign_bit))
3843 56079 : || (wi::eq_p (rh_lb, rh_ub)
3844 0 : && !wi::cmps (rh_lb, sign_bit))))
3845 : {
3846 0 : new_lb = wi::min_value (prec, sign);
3847 0 : new_ub = wi::zero (prec);
3848 : }
3849 56079 : }
3850 : // If the limits got swapped around, return varying.
3851 5417759 : if (wi::gt_p (new_lb, new_ub,sign))
3852 : {
3853 56079 : if (sign == SIGNED
3854 56079 : && wi_optimize_signed_bitwise_op (r, type,
3855 : lh_lb, lh_ub,
3856 : rh_lb, rh_ub))
3857 4861 : return;
3858 51218 : r.set_varying (type);
3859 : }
3860 : else
3861 5361680 : value_range_with_overflow (r, type, new_lb, new_ub);
3862 5417759 : }
3863 :
3864 : static void
3865 662929 : set_nonzero_range_from_mask (irange &r, tree type, const irange &lhs)
3866 : {
3867 662929 : if (lhs.undefined_p () || lhs.contains_zero_p ())
3868 327029 : r.set_varying (type);
3869 : else
3870 335900 : r.set_nonzero (type);
3871 662929 : }
3872 :
3873 : /* Find out smallest RES where RES > VAL && (RES & MASK) == RES, if any
3874 : (otherwise return VAL). VAL and MASK must be zero-extended for
3875 : precision PREC. If SGNBIT is non-zero, first xor VAL with SGNBIT
3876 : (to transform signed values into unsigned) and at the end xor
3877 : SGNBIT back. */
3878 :
3879 : wide_int
3880 35107 : masked_increment (const wide_int &val_in, const wide_int &mask,
3881 : const wide_int &sgnbit, unsigned int prec)
3882 : {
3883 35107 : wide_int bit = wi::one (prec), res;
3884 35107 : unsigned int i;
3885 :
3886 35107 : wide_int val = val_in ^ sgnbit;
3887 595581 : for (i = 0; i < prec; i++, bit += bit)
3888 : {
3889 550609 : res = mask;
3890 550609 : if ((res & bit) == 0)
3891 466866 : continue;
3892 83743 : res = bit - 1;
3893 83743 : res = wi::bit_and_not (val + bit, res);
3894 83743 : res &= mask;
3895 83743 : if (wi::gtu_p (res, val))
3896 25242 : return res ^ sgnbit;
3897 : }
3898 9865 : return val ^ sgnbit;
3899 35107 : }
3900 :
3901 : // This was shamelessly stolen from register_edge_assert_for_2 and
3902 : // adjusted to work with iranges.
3903 :
3904 : void
3905 4052932 : operator_bitwise_and::simple_op1_range_solver (irange &r, tree type,
3906 : const irange &lhs,
3907 : const irange &op2) const
3908 : {
3909 4052932 : if (!op2.singleton_p ())
3910 : {
3911 662005 : set_nonzero_range_from_mask (r, type, lhs);
3912 1330158 : return;
3913 : }
3914 3390927 : unsigned int nprec = TYPE_PRECISION (type);
3915 3390927 : wide_int cst2v = op2.lower_bound ();
3916 3390927 : bool cst2n = wi::neg_p (cst2v, TYPE_SIGN (type));
3917 3390927 : wide_int sgnbit;
3918 3390927 : if (cst2n)
3919 872838 : sgnbit = wi::set_bit_in_zero (nprec - 1, nprec);
3920 : else
3921 2518089 : sgnbit = wi::zero (nprec);
3922 :
3923 : // Solve [lhs.lower_bound (), +INF] = x & MASK.
3924 : //
3925 : // Minimum unsigned value for >= if (VAL & CST2) == VAL is VAL and
3926 : // maximum unsigned value is ~0. For signed comparison, if CST2
3927 : // doesn't have the most significant bit set, handle it similarly. If
3928 : // CST2 has MSB set, the minimum is the same, and maximum is ~0U/2.
3929 3390927 : wide_int valv = lhs.lower_bound ();
3930 3390927 : wide_int minv = valv & cst2v, maxv;
3931 3390927 : bool we_know_nothing = false;
3932 3390927 : if (minv != valv)
3933 : {
3934 : // If (VAL & CST2) != VAL, X & CST2 can't be equal to VAL.
3935 7564 : minv = masked_increment (valv, cst2v, sgnbit, nprec);
3936 7564 : if (minv == valv)
3937 : {
3938 : // If we can't determine anything on this bound, fall
3939 : // through and conservatively solve for the other end point.
3940 3390927 : we_know_nothing = true;
3941 : }
3942 : }
3943 5909016 : maxv = wi::mask (nprec - (cst2n ? 1 : 0), false, nprec);
3944 3390927 : if (we_know_nothing)
3945 3717 : r.set_varying (type);
3946 : else
3947 3387210 : create_possibly_reversed_range (r, type, minv, maxv);
3948 :
3949 : // Solve [-INF, lhs.upper_bound ()] = x & MASK.
3950 : //
3951 : // Minimum unsigned value for <= is 0 and maximum unsigned value is
3952 : // VAL | ~CST2 if (VAL & CST2) == VAL. Otherwise, find smallest
3953 : // VAL2 where
3954 : // VAL2 > VAL && (VAL2 & CST2) == VAL2 and use (VAL2 - 1) | ~CST2
3955 : // as maximum.
3956 : // For signed comparison, if CST2 doesn't have most significant bit
3957 : // set, handle it similarly. If CST2 has MSB set, the maximum is
3958 : // the same and minimum is INT_MIN.
3959 3390927 : valv = lhs.upper_bound ();
3960 3390927 : minv = valv & cst2v;
3961 3390927 : if (minv == valv)
3962 3363384 : maxv = valv;
3963 : else
3964 : {
3965 27543 : maxv = masked_increment (valv, cst2v, sgnbit, nprec);
3966 27543 : if (maxv == valv)
3967 : {
3968 : // If we couldn't determine anything on either bound, return
3969 : // undefined.
3970 6148 : if (we_know_nothing)
3971 3100 : r.set_undefined ();
3972 6148 : return;
3973 : }
3974 21395 : maxv -= 1;
3975 : }
3976 3384779 : maxv |= ~cst2v;
3977 3384779 : minv = sgnbit;
3978 3384779 : int_range<2> upper_bits;
3979 3384779 : create_possibly_reversed_range (upper_bits, type, minv, maxv);
3980 3384779 : r.intersect (upper_bits);
3981 3390927 : }
3982 :
3983 : bool
3984 4080624 : operator_bitwise_and::op1_range (irange &r, tree type,
3985 : const irange &lhs,
3986 : const irange &op2,
3987 : relation_trio) const
3988 : {
3989 4080624 : if (lhs.undefined_p ())
3990 : return false;
3991 4080624 : if (types_compatible_p (type, boolean_type_node))
3992 965346 : return op_logical_and.op1_range (r, type, lhs, op2);
3993 :
3994 3115278 : r.set_undefined ();
3995 10283488 : for (unsigned i = 0; i < lhs.num_pairs (); ++i)
3996 : {
3997 8105864 : int_range_max chunk (lhs.type (),
3998 8105864 : lhs.lower_bound (i),
3999 8105864 : lhs.upper_bound (i));
4000 4052932 : int_range_max res;
4001 4052932 : simple_op1_range_solver (res, type, chunk, op2);
4002 4052932 : r.union_ (res);
4003 4052932 : }
4004 3115278 : if (r.undefined_p ())
4005 924 : set_nonzero_range_from_mask (r, type, lhs);
4006 :
4007 : // For MASK == op1 & MASK, all the bits in MASK must be set in op1.
4008 3115278 : wide_int mask;
4009 3115278 : if (lhs == op2 && lhs.singleton_p (mask))
4010 : {
4011 396143 : r.update_bitmask (irange_bitmask (mask, ~mask));
4012 396143 : return true;
4013 : }
4014 :
4015 2719135 : if (!op2.singleton_p (mask))
4016 : return true;
4017 :
4018 : // For 0 = op1 & MASK, op1 is ~MASK.
4019 2115353 : if (lhs.zero_p ())
4020 : {
4021 712625 : wide_int nz = wi::bit_not (op2.get_nonzero_bits ());
4022 712625 : int_range<2> tmp (type);
4023 712625 : tmp.set_nonzero_bits (nz);
4024 712625 : r.intersect (tmp);
4025 712625 : }
4026 :
4027 2115353 : irange_bitmask lhs_bm = lhs.get_bitmask ();
4028 : // given [5,7] mask 0x3 value 0x4 = N & [7, 7] mask 0x0 value 0x7
4029 : // Nothing is known about the bits not specified in the mask value (op2),
4030 : // Start with the mask, 1's will occur where values were masked.
4031 2115353 : wide_int op1_mask = ~mask;
4032 : // Any bits that are unknown on the LHS are also unknown in op1,
4033 : // so union the current mask with the LHS mask.
4034 2115353 : op1_mask |= lhs_bm.mask ();
4035 : // The resulting zeros correspond to known bits in the LHS mask, and
4036 : // the LHS value should tell us what they are. Mask off any
4037 : // extraneous values that are not covered by the mask.
4038 2115353 : wide_int op1_value = lhs_bm.value () & ~op1_mask;
4039 2115353 : irange_bitmask op1_bm (op1_value, op1_mask);
4040 : // Intersect this mask with anything already known about the value.
4041 : // A return valueof false indicated the bitmask is an UNDEFINED range.
4042 2115353 : if (op1_bm.intersect (r.get_bitmask ()))
4043 2115353 : r.update_bitmask (op1_bm);
4044 : else
4045 0 : r.set_undefined ();
4046 2115353 : return true;
4047 5230631 : }
4048 :
4049 : bool
4050 1047735 : operator_bitwise_and::op2_range (irange &r, tree type,
4051 : const irange &lhs,
4052 : const irange &op1,
4053 : relation_trio) const
4054 : {
4055 1047735 : return operator_bitwise_and::op1_range (r, type, lhs, op1);
4056 : }
4057 :
4058 :
4059 : class operator_logical_or : public range_operator
4060 : {
4061 : using range_operator::fold_range;
4062 : using range_operator::op1_range;
4063 : using range_operator::op2_range;
4064 : public:
4065 : bool fold_range (irange &r, tree type,
4066 : const irange &lh,
4067 : const irange &rh,
4068 : relation_trio rel = TRIO_VARYING) const final override;
4069 : bool op1_range (irange &r, tree type,
4070 : const irange &lhs,
4071 : const irange &op2,
4072 : relation_trio rel = TRIO_VARYING) const final override;
4073 : bool op2_range (irange &r, tree type,
4074 : const irange &lhs,
4075 : const irange &op1,
4076 : relation_trio rel = TRIO_VARYING) const final override;
4077 : // Check compatibility of all operands.
4078 0 : bool operand_check_p (tree t1, tree t2, tree t3) const final override
4079 0 : { return range_compatible_p (t1, t2) && range_compatible_p (t1, t3); }
4080 : } op_logical_or;
4081 :
4082 : bool
4083 0 : operator_logical_or::fold_range (irange &r, tree type ATTRIBUTE_UNUSED,
4084 : const irange &lh,
4085 : const irange &rh,
4086 : relation_trio) const
4087 : {
4088 0 : if (empty_range_varying (r, type, lh, rh))
4089 0 : return true;
4090 :
4091 0 : r = lh;
4092 0 : r.union_ (rh);
4093 0 : return true;
4094 : }
4095 :
4096 : bool
4097 352674 : operator_logical_or::op1_range (irange &r, tree type,
4098 : const irange &lhs,
4099 : const irange &op2,
4100 : relation_trio) const
4101 : {
4102 352674 : switch (get_bool_state (r, lhs, type))
4103 : {
4104 202580 : case BRS_FALSE:
4105 : // A false result means both sides of the OR must be false.
4106 202580 : r = range_false (type);
4107 202580 : return true;
4108 :
4109 148320 : case BRS_TRUE:
4110 : // A TRUE result when op2 is FALSE must have op1 TRUE.
4111 148320 : if (op2.zero_p ())
4112 : {
4113 988 : r = range_true (type);
4114 988 : return true;
4115 : }
4116 : break;
4117 :
4118 : default:
4119 : break;
4120 : }
4121 :
4122 : // Any other result means we cannot be sure of any result.
4123 149106 : r = range_true_and_false (type);
4124 149106 : return true;
4125 : }
4126 :
4127 : bool
4128 0 : operator_logical_or::op2_range (irange &r, tree type,
4129 : const irange &lhs,
4130 : const irange &op1,
4131 : relation_trio) const
4132 : {
4133 0 : return operator_logical_or::op1_range (r, type, lhs, op1);
4134 : }
4135 :
4136 :
4137 : void
4138 2504718 : operator_bitwise_or::update_bitmask (irange &r, const irange &lh,
4139 : const irange &rh) const
4140 : {
4141 2504718 : update_known_bitmask (r, BIT_IOR_EXPR, lh, rh);
4142 2504718 : }
4143 :
4144 : void
4145 7180207 : operator_bitwise_or::wi_fold (irange &r, tree type,
4146 : const wide_int &lh_lb,
4147 : const wide_int &lh_ub,
4148 : const wide_int &rh_lb,
4149 : const wide_int &rh_ub) const
4150 : {
4151 7180207 : if (wi_optimize_and_or (r, BIT_IOR_EXPR, type, lh_lb, lh_ub, rh_lb, rh_ub))
4152 6466454 : return;
4153 :
4154 911093 : wide_int maybe_nonzero_lh, mustbe_nonzero_lh;
4155 911093 : wide_int maybe_nonzero_rh, mustbe_nonzero_rh;
4156 911093 : wi_set_zero_nonzero_bits (type, lh_lb, lh_ub,
4157 : maybe_nonzero_lh, mustbe_nonzero_lh);
4158 911093 : wi_set_zero_nonzero_bits (type, rh_lb, rh_ub,
4159 : maybe_nonzero_rh, mustbe_nonzero_rh);
4160 911093 : wide_int new_lb = mustbe_nonzero_lh | mustbe_nonzero_rh;
4161 911093 : wide_int new_ub = maybe_nonzero_lh | maybe_nonzero_rh;
4162 911093 : signop sign = TYPE_SIGN (type);
4163 : // If the input ranges contain only positive values we can
4164 : // truncate the minimum of the result range to the maximum
4165 : // of the input range minima.
4166 911093 : if (wi::ge_p (lh_lb, 0, sign)
4167 911093 : && wi::ge_p (rh_lb, 0, sign))
4168 : {
4169 683521 : new_lb = wi::max (new_lb, lh_lb, sign);
4170 683521 : new_lb = wi::max (new_lb, rh_lb, sign);
4171 : }
4172 : // If either input range contains only negative values
4173 : // we can truncate the minimum of the result range to the
4174 : // respective minimum range.
4175 911093 : if (wi::lt_p (lh_ub, 0, sign))
4176 20437 : new_lb = wi::max (new_lb, lh_lb, sign);
4177 911093 : if (wi::lt_p (rh_ub, 0, sign))
4178 10678 : new_lb = wi::max (new_lb, rh_lb, sign);
4179 : // If the limits got swapped around, return a conservative range.
4180 911093 : if (wi::gt_p (new_lb, new_ub, sign))
4181 : {
4182 : // Make sure that nonzero|X is nonzero.
4183 197340 : if (wi::gt_p (lh_lb, 0, sign)
4184 192359 : || wi::gt_p (rh_lb, 0, sign)
4185 132209 : || wi::lt_p (lh_ub, 0, sign)
4186 389699 : || wi::lt_p (rh_ub, 0, sign))
4187 65131 : r.set_nonzero (type);
4188 132209 : else if (sign == SIGNED
4189 132209 : && wi_optimize_signed_bitwise_op (r, type,
4190 : lh_lb, lh_ub,
4191 : rh_lb, rh_ub))
4192 : return;
4193 : else
4194 129383 : r.set_varying (type);
4195 : return;
4196 : }
4197 713753 : value_range_with_overflow (r, type, new_lb, new_ub);
4198 911123 : }
4199 :
4200 : // When x == y, x | y is x.
4201 :
4202 : relation_kind
4203 2404019 : operator_bitwise_or::lhs_op1_relation (const irange &lhs,
4204 : const irange &op1,
4205 : const irange &op2,
4206 : relation_kind rel) const
4207 : {
4208 2404019 : if (lhs.undefined_p () || op1.undefined_p () || op2.undefined_p ())
4209 : return VREL_VARYING;
4210 2402809 : if (rel == VREL_EQ)
4211 23 : return VREL_EQ;
4212 : return VREL_VARYING;
4213 : }
4214 :
4215 : bool
4216 2504718 : operator_bitwise_or::op1_op2_relation_effect (irange &lhs_range,
4217 : tree type,
4218 : const irange &,
4219 : const irange &,
4220 : relation_kind rel) const
4221 : {
4222 2504718 : if (rel == VREL_VARYING)
4223 : return false;
4224 :
4225 6156 : int_range<2> rel_range;
4226 :
4227 6156 : switch (rel)
4228 : {
4229 853 : case VREL_NE:
4230 853 : rel_range.set_nonzero (type);
4231 853 : break;
4232 : default:
4233 : return false;
4234 : }
4235 :
4236 853 : lhs_range.intersect (rel_range);
4237 853 : return true;
4238 6156 : }
4239 :
4240 : bool
4241 749319 : operator_bitwise_or::op1_range (irange &r, tree type,
4242 : const irange &lhs,
4243 : const irange &op2,
4244 : relation_trio) const
4245 : {
4246 749319 : if (lhs.undefined_p ())
4247 : return false;
4248 : // If this is really a logical wi_fold, call that.
4249 749319 : if (types_compatible_p (type, boolean_type_node))
4250 352674 : return op_logical_or.op1_range (r, type, lhs, op2);
4251 :
4252 396645 : if (lhs.zero_p ())
4253 : {
4254 128924 : r.set_zero (type);
4255 128924 : return true;
4256 : }
4257 :
4258 : // if (A < 0 && B < 0)
4259 : // Sometimes gets translated to
4260 : // _1 = A | B
4261 : // if (_1 < 0))
4262 : // It is useful for ranger to recognize a positive LHS means the RHS
4263 : // operands are also positive when dealing with the ELSE range..
4264 380408 : if (TYPE_SIGN (type) == SIGNED && wi::ge_p (lhs.lower_bound (), 0, SIGNED))
4265 : {
4266 42330 : unsigned prec = TYPE_PRECISION (type);
4267 42330 : r.set (type, wi::zero (prec), wi::max_value (prec, SIGNED));
4268 42330 : return true;
4269 : }
4270 225391 : r.set_varying (type);
4271 225391 : return true;
4272 : }
4273 :
4274 : bool
4275 358097 : operator_bitwise_or::op2_range (irange &r, tree type,
4276 : const irange &lhs,
4277 : const irange &op1,
4278 : relation_trio) const
4279 : {
4280 358097 : return operator_bitwise_or::op1_range (r, type, lhs, op1);
4281 : }
4282 :
4283 : void
4284 95578 : operator_bitwise_xor::update_bitmask (irange &r, const irange &lh,
4285 : const irange &rh) const
4286 : {
4287 95578 : update_known_bitmask (r, BIT_XOR_EXPR, lh, rh);
4288 95578 : }
4289 :
4290 : bool
4291 327972 : operator_bitwise_xor::fold_range (irange &r, tree type,
4292 : const irange &lh, const irange &rh,
4293 : relation_trio rel) const
4294 : {
4295 : // Handle X ^ UNDEFINED = UNDEFINED.
4296 327972 : if (lh.undefined_p () || rh.undefined_p ())
4297 : {
4298 471 : r.set_undefined ();
4299 471 : return true;
4300 : }
4301 :
4302 : // Next, handle X ^ X == [0, 0].
4303 327501 : if (rel.op1_op2 () == VREL_EQ)
4304 : {
4305 131 : r.set_zero (type);
4306 131 : return true;
4307 : }
4308 :
4309 : // If either operand is VARYING, the result is VARYING.
4310 327370 : if (lh.varying_p () || rh.varying_p ())
4311 : {
4312 : // If the operands are not equal, zero is not possible.
4313 228883 : if (rel.op1_op2 () != VREL_NE)
4314 227768 : r.set_varying (type);
4315 : else
4316 1115 : r.set_nonzero (type);
4317 : return true;
4318 : }
4319 :
4320 : // Now deal with X ^ 0 == X.
4321 98487 : if (lh.zero_p ())
4322 : {
4323 2305 : r = rh;
4324 2305 : return true;
4325 : }
4326 96182 : if (rh.zero_p ())
4327 : {
4328 604 : r = lh;
4329 604 : return true;
4330 : }
4331 :
4332 : // Start with the legacy range. This can sometimes pick up values
4333 : // when there are a lot of subranges and fold_range aggregates them.
4334 95578 : bool res = range_operator::fold_range (r, type, lh, rh, rel);
4335 :
4336 : // Calculate the XOR identity : x ^ y = (x | y) & ~(x & y)
4337 : // AND and OR are already much better optimized.
4338 95578 : int_range_max tmp1, tmp2, tmp3, new_result;
4339 95578 : int_range<2> varying;
4340 95578 : varying.set_varying (type);
4341 :
4342 95578 : if (m_or.fold_range (tmp1, type, lh, rh, rel)
4343 95578 : && m_and.fold_range (tmp2, type, lh, rh, rel)
4344 95578 : && m_not.fold_range (tmp3, type, tmp2, varying, rel)
4345 191156 : && m_and.fold_range (new_result, type, tmp1, tmp3, rel))
4346 : {
4347 : // If the operands are not equal, or the LH does not contain any
4348 : // element of the RH, zero is not possible.
4349 95578 : tmp1 = lh;
4350 95578 : if (rel.op1_op2 () == VREL_NE
4351 95578 : || (tmp1.intersect (rh) && tmp1.undefined_p ()))
4352 : {
4353 34638 : tmp1.set_nonzero (type);
4354 34638 : new_result.intersect (tmp1);
4355 : }
4356 :
4357 : // Combine with the legacy range if there was one.
4358 95578 : if (res)
4359 95578 : r.intersect (new_result);
4360 : else
4361 0 : r = new_result;
4362 : return true;
4363 : }
4364 : return res;
4365 95578 : }
4366 :
4367 : void
4368 188330 : operator_bitwise_xor::wi_fold (irange &r, tree type,
4369 : const wide_int &lh_lb,
4370 : const wide_int &lh_ub,
4371 : const wide_int &rh_lb,
4372 : const wide_int &rh_ub) const
4373 : {
4374 188330 : signop sign = TYPE_SIGN (type);
4375 188330 : wide_int maybe_nonzero_lh, mustbe_nonzero_lh;
4376 188330 : wide_int maybe_nonzero_rh, mustbe_nonzero_rh;
4377 188330 : wi_set_zero_nonzero_bits (type, lh_lb, lh_ub,
4378 : maybe_nonzero_lh, mustbe_nonzero_lh);
4379 188330 : wi_set_zero_nonzero_bits (type, rh_lb, rh_ub,
4380 : maybe_nonzero_rh, mustbe_nonzero_rh);
4381 :
4382 564990 : wide_int result_zero_bits = ((mustbe_nonzero_lh & mustbe_nonzero_rh)
4383 564990 : | ~(maybe_nonzero_lh | maybe_nonzero_rh));
4384 188330 : wide_int result_one_bits
4385 376660 : = (wi::bit_and_not (mustbe_nonzero_lh, maybe_nonzero_rh)
4386 376660 : | wi::bit_and_not (mustbe_nonzero_rh, maybe_nonzero_lh));
4387 188330 : wide_int new_ub = ~result_zero_bits;
4388 188330 : wide_int new_lb = result_one_bits;
4389 :
4390 : // If the range has all positive or all negative values, the result
4391 : // is better than VARYING.
4392 188330 : if (wi::lt_p (new_lb, 0, sign) || wi::ge_p (new_ub, 0, sign))
4393 180951 : value_range_with_overflow (r, type, new_lb, new_ub);
4394 7379 : else if (sign == SIGNED
4395 7379 : && wi_optimize_signed_bitwise_op (r, type,
4396 : lh_lb, lh_ub,
4397 : rh_lb, rh_ub))
4398 : ; /* Do nothing. */
4399 : else
4400 1167 : r.set_varying (type);
4401 :
4402 : /* Furthermore, XOR is non-zero if its arguments can't be equal. */
4403 188330 : if (wi::lt_p (lh_ub, rh_lb, sign)
4404 123341 : || wi::lt_p (rh_ub, lh_lb, sign)
4405 311671 : || wi::ne_p (result_one_bits, 0))
4406 : {
4407 86717 : int_range<2> tmp;
4408 86717 : tmp.set_nonzero (type);
4409 86717 : r.intersect (tmp);
4410 86717 : }
4411 188330 : }
4412 :
4413 : bool
4414 95578 : operator_bitwise_xor::op1_op2_relation_effect (irange &lhs_range,
4415 : tree type,
4416 : const irange &,
4417 : const irange &,
4418 : relation_kind rel) const
4419 : {
4420 95578 : if (rel == VREL_VARYING)
4421 : return false;
4422 :
4423 4864 : int_range<2> rel_range;
4424 :
4425 4864 : switch (rel)
4426 : {
4427 0 : case VREL_EQ:
4428 0 : rel_range.set_zero (type);
4429 0 : break;
4430 600 : case VREL_NE:
4431 600 : rel_range.set_nonzero (type);
4432 600 : break;
4433 : default:
4434 : return false;
4435 : }
4436 :
4437 600 : lhs_range.intersect (rel_range);
4438 600 : return true;
4439 4864 : }
4440 :
4441 : bool
4442 99616 : operator_bitwise_xor::op1_range (irange &r, tree type,
4443 : const irange &lhs,
4444 : const irange &op2,
4445 : relation_trio) const
4446 : {
4447 99616 : if (lhs.undefined_p () || lhs.varying_p ())
4448 : {
4449 4111 : r = lhs;
4450 4111 : return true;
4451 : }
4452 95505 : if (types_compatible_p (type, boolean_type_node))
4453 : {
4454 2449 : switch (get_bool_state (r, lhs, type))
4455 : {
4456 1035 : case BRS_TRUE:
4457 1035 : if (op2.varying_p ())
4458 1003 : r.set_varying (type);
4459 32 : else if (op2.zero_p ())
4460 24 : r = range_true (type);
4461 : // See get_bool_state for the rationale
4462 8 : else if (op2.undefined_p () || op2.contains_zero_p ())
4463 0 : r = range_true_and_false (type);
4464 : else
4465 8 : r = range_false (type);
4466 : break;
4467 1414 : case BRS_FALSE:
4468 1414 : r = op2;
4469 1414 : break;
4470 : default:
4471 : break;
4472 : }
4473 : return true;
4474 : }
4475 93056 : r.set_varying (type);
4476 93056 : return true;
4477 : }
4478 :
4479 : bool
4480 41171 : operator_bitwise_xor::op2_range (irange &r, tree type,
4481 : const irange &lhs,
4482 : const irange &op1,
4483 : relation_trio) const
4484 : {
4485 41171 : return operator_bitwise_xor::op1_range (r, type, lhs, op1);
4486 : }
4487 :
4488 : class operator_trunc_mod : public range_operator
4489 : {
4490 : using range_operator::op1_range;
4491 : using range_operator::op2_range;
4492 : using range_operator::update_bitmask;
4493 : using range_operator::op1_op2_relation_effect;
4494 : public:
4495 : virtual void wi_fold (irange &r, tree type,
4496 : const wide_int &lh_lb,
4497 : const wide_int &lh_ub,
4498 : const wide_int &rh_lb,
4499 : const wide_int &rh_ub) const override;
4500 : virtual bool op1_range (irange &r, tree type,
4501 : const irange &lhs,
4502 : const irange &op2,
4503 : relation_trio) const override;
4504 : virtual bool op2_range (irange &r, tree type,
4505 : const irange &lhs,
4506 : const irange &op1,
4507 : relation_trio) const override;
4508 1221951 : void update_bitmask (irange &r, const irange &lh,
4509 : const irange &rh) const override
4510 1221951 : { update_known_bitmask (r, TRUNC_MOD_EXPR, lh, rh); }
4511 : bool op1_op2_relation_effect (irange &lhs_range,
4512 : tree type,
4513 : const irange &op1_range,
4514 : const irange &op2_range,
4515 : relation_kind rel) const final override;
4516 : protected:
4517 : bool same_quotient (wide_int &lb, wide_int &ub, const wide_int &x_lb,
4518 : const wide_int &x_ub, const wide_int &y_lb,
4519 : const wide_int &y_ub, signop sign) const;
4520 : } op_trunc_mod;
4521 :
4522 :
4523 : bool
4524 1472321 : operator_trunc_mod::same_quotient (wide_int &lb, wide_int &ub,
4525 : const wide_int &x_lb, const wide_int &x_ub,
4526 : const wide_int &y_lb, const wide_int &y_ub,
4527 : signop sign) const
4528 : {
4529 : // Y must not contain zero.
4530 1472321 : if (wi::ge_p (y_ub, 0, sign) && wi::le_p (y_lb, 0, sign))
4531 974499 : return false;
4532 :
4533 : // If all endpoints do not have the same quotient, nothing further.
4534 497822 : wide_int q = wi::div_trunc (x_lb, y_lb, sign);
4535 497870 : if (q != wi::div_trunc (x_lb, y_ub, sign))
4536 : return false;
4537 454305 : if (q != wi::div_trunc (x_ub, y_lb, sign))
4538 : return false;
4539 47797 : if (q != wi::div_trunc (x_ub, y_ub, sign))
4540 : return false;
4541 :
4542 : // Compute the range extremes.
4543 47392 : wide_int v1 = x_lb - q * y_lb;
4544 47392 : wide_int v2 = x_lb - q * y_ub;
4545 47392 : wide_int v3 = x_ub - q * y_lb;
4546 47392 : wide_int v4 = x_ub - q * y_ub;
4547 :
4548 : // And choose the minimum and maximum
4549 47392 : lb = wi::min (v1, v2, sign);
4550 47392 : lb = wi::min (lb, v3, sign);
4551 47392 : lb = wi::min (lb, v4, sign);
4552 :
4553 47392 : ub = wi::max (v1, v2, sign);
4554 47392 : ub = wi::max (ub, v3, sign);
4555 47392 : ub = wi::max (ub, v4, sign);
4556 :
4557 47392 : return true;
4558 545214 : }
4559 :
4560 : void
4561 1507909 : operator_trunc_mod::wi_fold (irange &r, tree type,
4562 : const wide_int &lh_lb,
4563 : const wide_int &lh_ub,
4564 : const wide_int &rh_lb,
4565 : const wide_int &rh_ub) const
4566 : {
4567 1507909 : wide_int new_lb, new_ub, tmp;
4568 1507909 : signop sign = TYPE_SIGN (type);
4569 1507909 : unsigned prec = TYPE_PRECISION (type);
4570 :
4571 : // Mod 0 is undefined.
4572 1507909 : if (wi_zero_p (type, rh_lb, rh_ub))
4573 : {
4574 10923 : r.set_undefined ();
4575 10923 : return;
4576 : }
4577 :
4578 : // Check for constant and try to fold.
4579 1753169 : if (lh_lb == lh_ub && rh_lb == rh_ub)
4580 : {
4581 24691 : wi::overflow_type ov = wi::OVF_NONE;
4582 24691 : tmp = wi::mod_trunc (lh_lb, rh_lb, sign, &ov);
4583 24691 : if (ov == wi::OVF_NONE)
4584 : {
4585 24665 : r = int_range<2> (type, tmp, tmp);
4586 24665 : return;
4587 : }
4588 : }
4589 :
4590 : // ABS (A % B) < ABS (B) and either 0 <= A % B <= A or A <= A % B <= 0.
4591 1472321 : new_ub = rh_ub - 1;
4592 1472321 : if (sign == SIGNED)
4593 : {
4594 662205 : tmp = -1 - rh_lb;
4595 662205 : new_ub = wi::smax (new_ub, tmp);
4596 : }
4597 :
4598 662205 : if (sign == UNSIGNED)
4599 810116 : new_lb = wi::zero (prec);
4600 : else
4601 : {
4602 662205 : new_lb = -new_ub;
4603 662205 : tmp = lh_lb;
4604 662205 : if (wi::gts_p (tmp, 0))
4605 168361 : tmp = wi::zero (prec);
4606 662254 : new_lb = wi::smax (new_lb, tmp);
4607 : }
4608 1472321 : tmp = lh_ub;
4609 1472321 : if (sign == SIGNED && wi::neg_p (tmp))
4610 35793 : tmp = wi::zero (prec);
4611 1472321 : new_ub = wi::min (new_ub, tmp, sign);
4612 :
4613 1472321 : value_range_with_overflow (r, type, new_lb, new_ub);
4614 :
4615 : // If all X/Y combinations have the same quotient, refine using
4616 : // X % Y == X - Q * Y.
4617 1472321 : if (same_quotient (new_lb, new_ub, lh_lb, lh_ub, rh_lb, rh_ub, sign))
4618 : {
4619 47392 : int_range<2> refined (type, new_lb, new_ub);
4620 47392 : r.intersect (refined);
4621 47392 : }
4622 1508239 : }
4623 :
4624 : bool
4625 663065 : operator_trunc_mod::op1_range (irange &r, tree type,
4626 : const irange &lhs,
4627 : const irange &,
4628 : relation_trio) const
4629 : {
4630 663065 : if (lhs.undefined_p ())
4631 : return false;
4632 : // PR 91029.
4633 663065 : signop sign = TYPE_SIGN (type);
4634 663065 : unsigned prec = TYPE_PRECISION (type);
4635 : // (a % b) >= x && x > 0 , then a >= x.
4636 663175 : if (wi::gt_p (lhs.lower_bound (), 0, sign))
4637 : {
4638 180158 : r.set (type, lhs.lower_bound (), wi::max_value (prec, sign));
4639 180113 : return true;
4640 : }
4641 : // (a % b) <= x && x < 0 , then a <= x.
4642 483017 : if (wi::lt_p (lhs.upper_bound (), 0, sign))
4643 : {
4644 13047 : r.set (type, wi::min_value (prec, sign), lhs.upper_bound ());
4645 13047 : return true;
4646 : }
4647 : return false;
4648 : }
4649 :
4650 : bool
4651 357508 : operator_trunc_mod::op2_range (irange &r, tree type,
4652 : const irange &lhs,
4653 : const irange &,
4654 : relation_trio) const
4655 : {
4656 357508 : if (lhs.undefined_p ())
4657 : return false;
4658 : // PR 91029.
4659 357508 : signop sign = TYPE_SIGN (type);
4660 357508 : unsigned prec = TYPE_PRECISION (type);
4661 : // (a % b) >= x && x > 0 , then b is in ~[-x, x] for signed
4662 : // or b > x for unsigned.
4663 357543 : if (wi::gt_p (lhs.lower_bound (), 0, sign))
4664 : {
4665 58402 : if (sign == SIGNED)
4666 2303 : r.set (type, wi::neg (lhs.lower_bound ()),
4667 4606 : lhs.lower_bound (), VR_ANTI_RANGE);
4668 56111 : else if (wi::lt_p (lhs.lower_bound (), wi::max_value (prec, sign),
4669 : sign))
4670 56117 : r.set (type, lhs.lower_bound () + 1, wi::max_value (prec, sign));
4671 : else
4672 : return false;
4673 : return true;
4674 : }
4675 : // (a % b) <= x && x < 0 , then b is in ~[x, -x].
4676 299135 : if (wi::lt_p (lhs.upper_bound (), 0, sign))
4677 : {
4678 5812 : if (wi::gt_p (lhs.upper_bound (), wi::min_value (prec, sign), sign))
4679 5812 : r.set (type, lhs.upper_bound (),
4680 11624 : wi::neg (lhs.upper_bound ()), VR_ANTI_RANGE);
4681 : else
4682 : return false;
4683 5812 : return true;
4684 : }
4685 : return false;
4686 : }
4687 :
4688 : bool
4689 1221951 : operator_trunc_mod::op1_op2_relation_effect (irange &lhs_range,
4690 : tree type,
4691 : const irange &,
4692 : const irange &,
4693 : relation_kind rel) const
4694 : {
4695 1221951 : if (rel == VREL_VARYING)
4696 : return false;
4697 :
4698 7870 : int_range<2> rel_range;
4699 :
4700 7870 : switch (rel)
4701 : {
4702 19 : case VREL_EQ:
4703 19 : rel_range.set_zero (type);
4704 19 : break;
4705 : default:
4706 : return false;
4707 : }
4708 :
4709 19 : lhs_range.intersect (rel_range);
4710 19 : return true;
4711 7870 : }
4712 :
4713 :
4714 : class operator_logical_not : public range_operator
4715 : {
4716 : using range_operator::fold_range;
4717 : using range_operator::op1_range;
4718 : public:
4719 : bool fold_range (irange &r, tree type,
4720 : const irange &lh,
4721 : const irange &rh,
4722 : relation_trio rel = TRIO_VARYING) const final override;
4723 : bool op1_range (irange &r, tree type,
4724 : const irange &lhs,
4725 : const irange &op2,
4726 : relation_trio rel = TRIO_VARYING) const final override;
4727 : // Check compatibility of LHS and op1.
4728 0 : bool operand_check_p (tree t1, tree t2, tree) const final override
4729 0 : { return range_compatible_p (t1, t2); }
4730 : } op_logical_not;
4731 :
4732 : // Folding a logical NOT, oddly enough, involves doing nothing on the
4733 : // forward pass through. During the initial walk backwards, the
4734 : // logical NOT reversed the desired outcome on the way back, so on the
4735 : // way forward all we do is pass the range forward.
4736 : //
4737 : // b_2 = x_1 < 20
4738 : // b_3 = !b_2
4739 : // if (b_3)
4740 : // to determine the TRUE branch, walking backward
4741 : // if (b_3) if ([1,1])
4742 : // b_3 = !b_2 [1,1] = ![0,0]
4743 : // b_2 = x_1 < 20 [0,0] = x_1 < 20, false, so x_1 == [20, 255]
4744 : // which is the result we are looking for.. so.. pass it through.
4745 :
4746 : bool
4747 250636 : operator_logical_not::fold_range (irange &r, tree type,
4748 : const irange &lh,
4749 : const irange &rh ATTRIBUTE_UNUSED,
4750 : relation_trio) const
4751 : {
4752 250636 : if (empty_range_varying (r, type, lh, rh))
4753 0 : return true;
4754 :
4755 250636 : r = lh;
4756 250636 : if (!lh.varying_p () && !lh.undefined_p ())
4757 : {
4758 56928 : if (!r.invert ())
4759 : return false;
4760 : }
4761 : return true;
4762 : }
4763 :
4764 : bool
4765 30879 : operator_logical_not::op1_range (irange &r,
4766 : tree type,
4767 : const irange &lhs,
4768 : const irange &op2,
4769 : relation_trio) const
4770 : {
4771 : // Logical NOT is involutary...do it again.
4772 30879 : return fold_range (r, type, lhs, op2);
4773 : }
4774 :
4775 : bool
4776 640776 : operator_bitwise_not::fold_range (irange &r, tree type,
4777 : const irange &lh,
4778 : const irange &rh,
4779 : relation_trio) const
4780 : {
4781 640776 : if (empty_range_varying (r, type, lh, rh))
4782 108 : return true;
4783 :
4784 640668 : if (types_compatible_p (type, boolean_type_node))
4785 219757 : return op_logical_not.fold_range (r, type, lh, rh);
4786 :
4787 : // ~X is simply -1 - X.
4788 841822 : int_range<1> minusone (type, wi::minus_one (TYPE_PRECISION (type)),
4789 841822 : wi::minus_one (TYPE_PRECISION (type)));
4790 420911 : return range_op_handler (MINUS_EXPR).fold_range (r, type, minusone, lh);
4791 420911 : }
4792 :
4793 : bool
4794 61685 : operator_bitwise_not::op1_range (irange &r, tree type,
4795 : const irange &lhs,
4796 : const irange &op2,
4797 : relation_trio) const
4798 : {
4799 61685 : if (lhs.undefined_p ())
4800 : return false;
4801 61685 : if (types_compatible_p (type, boolean_type_node))
4802 30879 : return op_logical_not.op1_range (r, type, lhs, op2);
4803 :
4804 : // ~X is -1 - X and since bitwise NOT is involutary...do it again.
4805 30806 : return fold_range (r, type, lhs, op2);
4806 : }
4807 :
4808 : void
4809 0 : operator_bitwise_not::update_bitmask (irange &r, const irange &lh,
4810 : const irange &rh) const
4811 : {
4812 0 : update_known_bitmask (r, BIT_NOT_EXPR, lh, rh);
4813 0 : }
4814 :
4815 :
4816 : bool
4817 697514 : operator_cst::fold_range (irange &r, tree type ATTRIBUTE_UNUSED,
4818 : const irange &lh,
4819 : const irange &rh ATTRIBUTE_UNUSED,
4820 : relation_trio) const
4821 : {
4822 697514 : r = lh;
4823 697514 : return true;
4824 : }
4825 :
4826 :
4827 : // Determine if there is a relationship between LHS and OP1.
4828 :
4829 : relation_kind
4830 1473823 : operator_identity::lhs_op1_relation (const irange &lhs,
4831 : const irange &op1 ATTRIBUTE_UNUSED,
4832 : const irange &op2 ATTRIBUTE_UNUSED,
4833 : relation_kind) const
4834 : {
4835 1473823 : if (lhs.undefined_p ())
4836 9359 : return VREL_VARYING;
4837 : // Simply a copy, so they are equivalent.
4838 : return VREL_EQ;
4839 : }
4840 :
4841 : bool
4842 1473823 : operator_identity::fold_range (irange &r, tree type ATTRIBUTE_UNUSED,
4843 : const irange &lh,
4844 : const irange &rh ATTRIBUTE_UNUSED,
4845 : relation_trio) const
4846 : {
4847 1473823 : r = lh;
4848 1473823 : return true;
4849 : }
4850 :
4851 : bool
4852 327603 : operator_identity::op1_range (irange &r, tree type ATTRIBUTE_UNUSED,
4853 : const irange &lhs,
4854 : const irange &op2 ATTRIBUTE_UNUSED,
4855 : relation_trio) const
4856 : {
4857 327603 : r = lhs;
4858 327603 : return true;
4859 : }
4860 :
4861 :
4862 : class operator_unknown : public range_operator
4863 : {
4864 : using range_operator::fold_range;
4865 : public:
4866 : virtual bool fold_range (irange &r, tree type,
4867 : const irange &op1,
4868 : const irange &op2,
4869 : relation_trio rel = TRIO_VARYING) const;
4870 : } op_unknown;
4871 :
4872 : bool
4873 1412122 : operator_unknown::fold_range (irange &r, tree type,
4874 : const irange &lh ATTRIBUTE_UNUSED,
4875 : const irange &rh ATTRIBUTE_UNUSED,
4876 : relation_trio) const
4877 : {
4878 1412122 : r.set_varying (type);
4879 1412122 : return true;
4880 : }
4881 :
4882 :
4883 : void
4884 110132 : operator_abs::wi_fold (irange &r, tree type,
4885 : const wide_int &lh_lb, const wide_int &lh_ub,
4886 : const wide_int &rh_lb ATTRIBUTE_UNUSED,
4887 : const wide_int &rh_ub ATTRIBUTE_UNUSED) const
4888 : {
4889 110132 : wide_int min, max;
4890 110132 : signop sign = TYPE_SIGN (type);
4891 110132 : unsigned prec = TYPE_PRECISION (type);
4892 :
4893 : // Pass through LH for the easy cases.
4894 110132 : if (sign == UNSIGNED || wi::ge_p (lh_lb, 0, sign))
4895 : {
4896 10364 : r = int_range<1> (type, lh_lb, lh_ub);
4897 10364 : return;
4898 : }
4899 :
4900 : // -TYPE_MIN_VALUE = TYPE_MIN_VALUE with flag_wrapv so we can't get
4901 : // a useful range.
4902 99768 : wide_int min_value = wi::min_value (prec, sign);
4903 99768 : wide_int max_value = wi::max_value (prec, sign);
4904 99768 : if (!TYPE_OVERFLOW_UNDEFINED (type) && wi::eq_p (lh_lb, min_value))
4905 : {
4906 549 : r.set_varying (type);
4907 549 : return;
4908 : }
4909 :
4910 : // ABS_EXPR may flip the range around, if the original range
4911 : // included negative values.
4912 99219 : if (wi::eq_p (lh_lb, min_value))
4913 : {
4914 : // ABS ([-MIN, -MIN]) isn't representable, but we have traditionally
4915 : // returned [-MIN,-MIN] so this preserves that behavior. PR37078
4916 34362 : if (wi::eq_p (lh_ub, min_value))
4917 : {
4918 60 : r = int_range<1> (type, min_value, min_value);
4919 60 : return;
4920 : }
4921 34302 : min = max_value;
4922 : }
4923 : else
4924 64857 : min = wi::abs (lh_lb);
4925 :
4926 99159 : if (wi::eq_p (lh_ub, min_value))
4927 0 : max = max_value;
4928 : else
4929 99159 : max = wi::abs (lh_ub);
4930 :
4931 : // If the range contains zero then we know that the minimum value in the
4932 : // range will be zero.
4933 99159 : if (wi::le_p (lh_lb, 0, sign) && wi::ge_p (lh_ub, 0, sign))
4934 : {
4935 88477 : if (wi::gt_p (min, max, sign))
4936 54200 : max = min;
4937 88477 : min = wi::zero (prec);
4938 : }
4939 : else
4940 : {
4941 : // If the range was reversed, swap MIN and MAX.
4942 10682 : if (wi::gt_p (min, max, sign))
4943 10520 : std::swap (min, max);
4944 : }
4945 :
4946 : // If the new range has its limits swapped around (MIN > MAX), then
4947 : // the operation caused one of them to wrap around. The only thing
4948 : // we know is that the result is positive.
4949 99159 : if (wi::gt_p (min, max, sign))
4950 : {
4951 0 : min = wi::zero (prec);
4952 0 : max = max_value;
4953 : }
4954 99159 : r = int_range<1> (type, min, max);
4955 110741 : }
4956 :
4957 : bool
4958 121777 : operator_abs::op1_range (irange &r, tree type,
4959 : const irange &lhs,
4960 : const irange &op2,
4961 : relation_trio) const
4962 : {
4963 121777 : if (empty_range_varying (r, type, lhs, op2))
4964 0 : return true;
4965 121777 : if (TYPE_UNSIGNED (type))
4966 : {
4967 0 : r = lhs;
4968 0 : return true;
4969 : }
4970 : // Start with the positives because negatives are an impossible result.
4971 121777 : int_range_max positives = range_positives (type);
4972 121777 : positives.intersect (lhs);
4973 121777 : r = positives;
4974 : // Then add the negative of each pair:
4975 : // ABS(op1) = [5,20] would yield op1 => [-20,-5][5,20].
4976 366081 : for (unsigned i = 0; i < positives.num_pairs (); ++i)
4977 122527 : r.union_ (int_range<1> (type,
4978 245054 : -positives.upper_bound (i),
4979 367581 : -positives.lower_bound (i)));
4980 : // With flag_wrapv, -TYPE_MIN_VALUE = TYPE_MIN_VALUE which is
4981 : // unrepresentable. Add -TYPE_MIN_VALUE in this case.
4982 121777 : wide_int min_value = wi::min_value (TYPE_PRECISION (type), TYPE_SIGN (type));
4983 121777 : wide_int lb = lhs.lower_bound ();
4984 121777 : if (!TYPE_OVERFLOW_UNDEFINED (type) && wi::eq_p (lb, min_value))
4985 178 : r.union_ (int_range<2> (type, lb, lb));
4986 121777 : return true;
4987 121777 : }
4988 :
4989 : void
4990 102994 : operator_abs::update_bitmask (irange &r, const irange &lh,
4991 : const irange &rh) const
4992 : {
4993 102994 : update_known_bitmask (r, ABS_EXPR, lh, rh);
4994 102994 : }
4995 :
4996 : class operator_absu : public range_operator
4997 : {
4998 : using range_operator::update_bitmask;
4999 : public:
5000 : virtual void wi_fold (irange &r, tree type,
5001 : const wide_int &lh_lb, const wide_int &lh_ub,
5002 : const wide_int &rh_lb, const wide_int &rh_ub)
5003 : const final override;
5004 : virtual void update_bitmask (irange &r, const irange &lh,
5005 : const irange &rh) const final override;
5006 : } op_absu;
5007 :
5008 : void
5009 9937 : operator_absu::wi_fold (irange &r, tree type,
5010 : const wide_int &lh_lb, const wide_int &lh_ub,
5011 : const wide_int &rh_lb ATTRIBUTE_UNUSED,
5012 : const wide_int &rh_ub ATTRIBUTE_UNUSED) const
5013 : {
5014 9937 : wide_int new_lb, new_ub;
5015 :
5016 : // Pass through VR0 the easy cases.
5017 9937 : if (wi::ges_p (lh_lb, 0))
5018 : {
5019 381 : new_lb = lh_lb;
5020 381 : new_ub = lh_ub;
5021 : }
5022 : else
5023 : {
5024 9556 : new_lb = wi::abs (lh_lb);
5025 9556 : new_ub = wi::abs (lh_ub);
5026 :
5027 : // If the range contains zero then we know that the minimum
5028 : // value in the range will be zero.
5029 9556 : if (wi::ges_p (lh_ub, 0))
5030 : {
5031 8265 : if (wi::gtu_p (new_lb, new_ub))
5032 6941 : new_ub = new_lb;
5033 8265 : new_lb = wi::zero (TYPE_PRECISION (type));
5034 : }
5035 : else
5036 1291 : std::swap (new_lb, new_ub);
5037 : }
5038 :
5039 9937 : gcc_checking_assert (TYPE_UNSIGNED (type));
5040 9937 : r = int_range<1> (type, new_lb, new_ub);
5041 9937 : }
5042 :
5043 : void
5044 9593 : operator_absu::update_bitmask (irange &r, const irange &lh,
5045 : const irange &rh) const
5046 : {
5047 9593 : update_known_bitmask (r, ABSU_EXPR, lh, rh);
5048 9593 : }
5049 :
5050 :
5051 : bool
5052 610926 : operator_negate::fold_range (irange &r, tree type,
5053 : const irange &lh,
5054 : const irange &rh,
5055 : relation_trio) const
5056 : {
5057 610926 : if (empty_range_varying (r, type, lh, rh))
5058 965 : return true;
5059 :
5060 : // -X is simply 0 - X.
5061 609961 : int_range<1> zero;
5062 609961 : zero.set_zero (type);
5063 609961 : return range_op_handler (MINUS_EXPR).fold_range (r, type, zero, lh);
5064 609961 : }
5065 :
5066 : bool
5067 89841 : operator_negate::op1_range (irange &r, tree type,
5068 : const irange &lhs,
5069 : const irange &op2,
5070 : relation_trio) const
5071 : {
5072 : // NEGATE is involutory.
5073 89841 : return fold_range (r, type, lhs, op2);
5074 : }
5075 :
5076 :
5077 : bool
5078 0 : operator_addr_expr::fold_range (irange &r, tree type,
5079 : const irange &lh,
5080 : const irange &rh,
5081 : relation_trio) const
5082 : {
5083 0 : if (empty_range_varying (r, type, lh, rh))
5084 0 : return true;
5085 :
5086 : // Return a non-null pointer of the LHS type (passed in op2).
5087 0 : if (lh.zero_p ())
5088 0 : r.set_zero (type);
5089 0 : else if (lh.undefined_p () || lh.contains_zero_p ())
5090 0 : r.set_varying (type);
5091 : else
5092 0 : r.set_nonzero (type);
5093 : return true;
5094 : }
5095 :
5096 : bool
5097 0 : operator_addr_expr::op1_range (irange &r, tree type,
5098 : const irange &lhs,
5099 : const irange &op2,
5100 : relation_trio) const
5101 : {
5102 0 : if (empty_range_varying (r, type, lhs, op2))
5103 0 : return true;
5104 :
5105 : // Return a non-null pointer of the LHS type (passed in op2), but only
5106 : // if we cant overflow, eitherwise a no-zero offset could wrap to zero.
5107 : // See PR 111009.
5108 0 : if (!lhs.undefined_p () && !lhs.contains_zero_p () && TYPE_OVERFLOW_UNDEFINED (type))
5109 0 : r.set_nonzero (type);
5110 : else
5111 0 : r.set_varying (type);
5112 : return true;
5113 : }
5114 :
5115 : // Initialize any integral operators to the primary table
5116 :
5117 : void
5118 293366 : range_op_table::initialize_integral_ops ()
5119 : {
5120 293366 : set (TRUNC_DIV_EXPR, op_trunc_div);
5121 293366 : set (FLOOR_DIV_EXPR, op_floor_div);
5122 293366 : set (ROUND_DIV_EXPR, op_round_div);
5123 293366 : set (CEIL_DIV_EXPR, op_ceil_div);
5124 293366 : set (EXACT_DIV_EXPR, op_exact_div);
5125 293366 : set (LSHIFT_EXPR, op_lshift);
5126 293366 : set (RSHIFT_EXPR, op_rshift);
5127 293366 : set (TRUTH_AND_EXPR, op_logical_and);
5128 293366 : set (TRUTH_OR_EXPR, op_logical_or);
5129 293366 : set (TRUNC_MOD_EXPR, op_trunc_mod);
5130 293366 : set (TRUTH_NOT_EXPR, op_logical_not);
5131 293366 : set (IMAGPART_EXPR, op_unknown);
5132 293366 : set (REALPART_EXPR, op_unknown);
5133 293366 : set (ABSU_EXPR, op_absu);
5134 293366 : set (OP_WIDEN_MULT_SIGNED, op_widen_mult_signed);
5135 293366 : set (OP_WIDEN_MULT_UNSIGNED, op_widen_mult_unsigned);
5136 293366 : set (OP_WIDEN_MULT_SIGNED_UNSIGNED, op_widen_mult_signed_unsigned);
5137 293366 : set (OP_WIDEN_PLUS_SIGNED, op_widen_plus_signed);
5138 293366 : set (OP_WIDEN_PLUS_UNSIGNED, op_widen_plus_unsigned);
5139 :
5140 293366 : }
5141 :
5142 : bool
5143 68621 : operator_plus::overflow_free_p (const irange &lh, const irange &rh,
5144 : relation_trio) const
5145 : {
5146 68621 : if (lh.undefined_p () || rh.undefined_p ())
5147 : return false;
5148 :
5149 68621 : tree type = lh.type ();
5150 68621 : if (TYPE_OVERFLOW_UNDEFINED (type))
5151 : return true;
5152 :
5153 37126 : wi::overflow_type ovf;
5154 37126 : signop sgn = TYPE_SIGN (type);
5155 37126 : wide_int wmax0 = lh.upper_bound ();
5156 37126 : wide_int wmax1 = rh.upper_bound ();
5157 37126 : wi::add (wmax0, wmax1, sgn, &ovf);
5158 37126 : if (ovf != wi::OVF_NONE)
5159 : return false;
5160 :
5161 26178 : if (TYPE_UNSIGNED (type))
5162 : return true;
5163 :
5164 346 : wide_int wmin0 = lh.lower_bound ();
5165 346 : wide_int wmin1 = rh.lower_bound ();
5166 346 : wi::add (wmin0, wmin1, sgn, &ovf);
5167 346 : if (ovf != wi::OVF_NONE)
5168 237 : return false;
5169 :
5170 : return true;
5171 37472 : }
5172 :
5173 : bool
5174 39485 : operator_minus::overflow_free_p (const irange &lh, const irange &rh,
5175 : relation_trio) const
5176 : {
5177 39485 : if (lh.undefined_p () || rh.undefined_p ())
5178 : return false;
5179 :
5180 39485 : tree type = lh.type ();
5181 39485 : if (TYPE_OVERFLOW_UNDEFINED (type))
5182 : return true;
5183 :
5184 39368 : wi::overflow_type ovf;
5185 39368 : signop sgn = TYPE_SIGN (type);
5186 39368 : wide_int wmin0 = lh.lower_bound ();
5187 39368 : wide_int wmax1 = rh.upper_bound ();
5188 39368 : wi::sub (wmin0, wmax1, sgn, &ovf);
5189 39368 : if (ovf != wi::OVF_NONE)
5190 : return false;
5191 :
5192 21207 : if (TYPE_UNSIGNED (type))
5193 : return true;
5194 :
5195 37 : wide_int wmax0 = lh.upper_bound ();
5196 37 : wide_int wmin1 = rh.lower_bound ();
5197 37 : wi::sub (wmax0, wmin1, sgn, &ovf);
5198 37 : if (ovf != wi::OVF_NONE)
5199 29 : return false;
5200 :
5201 : return true;
5202 39405 : }
5203 :
5204 : bool
5205 4092 : operator_mult::overflow_free_p (const irange &lh, const irange &rh,
5206 : relation_trio) const
5207 : {
5208 4092 : if (lh.undefined_p () || rh.undefined_p ())
5209 : return false;
5210 :
5211 4092 : tree type = lh.type ();
5212 4092 : if (TYPE_OVERFLOW_UNDEFINED (type))
5213 : return true;
5214 :
5215 3420 : wi::overflow_type ovf;
5216 3420 : signop sgn = TYPE_SIGN (type);
5217 3420 : wide_int wmax0 = lh.upper_bound ();
5218 3420 : wide_int wmax1 = rh.upper_bound ();
5219 3420 : wi::mul (wmax0, wmax1, sgn, &ovf);
5220 3420 : if (ovf != wi::OVF_NONE)
5221 : return false;
5222 :
5223 100 : if (TYPE_UNSIGNED (type))
5224 : return true;
5225 :
5226 22 : wide_int wmin0 = lh.lower_bound ();
5227 22 : wide_int wmin1 = rh.lower_bound ();
5228 22 : wi::mul (wmin0, wmin1, sgn, &ovf);
5229 22 : if (ovf != wi::OVF_NONE)
5230 : return false;
5231 :
5232 22 : wi::mul (wmin0, wmax1, sgn, &ovf);
5233 22 : if (ovf != wi::OVF_NONE)
5234 : return false;
5235 :
5236 22 : wi::mul (wmax0, wmin1, sgn, &ovf);
5237 22 : if (ovf != wi::OVF_NONE)
5238 0 : return false;
5239 :
5240 : return true;
5241 3442 : }
5242 :
5243 : #if CHECKING_P
5244 : #include "selftest.h"
5245 :
5246 : namespace selftest
5247 : {
5248 : #define INT(x) wi::shwi ((x), TYPE_PRECISION (integer_type_node))
5249 : #define UINT(x) wi::uhwi ((x), TYPE_PRECISION (unsigned_type_node))
5250 : #define INT16(x) wi::shwi ((x), TYPE_PRECISION (short_integer_type_node))
5251 : #define UINT16(x) wi::uhwi ((x), TYPE_PRECISION (short_unsigned_type_node))
5252 : #define SCHAR(x) wi::shwi ((x), TYPE_PRECISION (signed_char_type_node))
5253 : #define UCHAR(x) wi::uhwi ((x), TYPE_PRECISION (unsigned_char_type_node))
5254 :
5255 : static void
5256 4 : range_op_cast_tests ()
5257 : {
5258 4 : int_range<2> r0, r1, r2, rold;
5259 4 : r0.set_varying (integer_type_node);
5260 4 : wide_int maxint = r0.upper_bound ();
5261 :
5262 : // If a range is in any way outside of the range for the converted
5263 : // to range, default to the range for the new type.
5264 4 : r0.set_varying (short_integer_type_node);
5265 4 : wide_int minshort = r0.lower_bound ();
5266 4 : wide_int maxshort = r0.upper_bound ();
5267 4 : if (TYPE_PRECISION (integer_type_node)
5268 4 : > TYPE_PRECISION (short_integer_type_node))
5269 : {
5270 8 : r1 = int_range<1> (integer_type_node,
5271 4 : wi::zero (TYPE_PRECISION (integer_type_node)),
5272 8 : maxint);
5273 4 : range_cast (r1, short_integer_type_node);
5274 4 : ASSERT_TRUE (r1.lower_bound () == minshort
5275 : && r1.upper_bound() == maxshort);
5276 : }
5277 :
5278 : // (unsigned char)[-5,-1] => [251,255].
5279 4 : r0 = rold = int_range<1> (signed_char_type_node, SCHAR (-5), SCHAR (-1));
5280 4 : range_cast (r0, unsigned_char_type_node);
5281 4 : ASSERT_TRUE (r0 == int_range<1> (unsigned_char_type_node,
5282 : UCHAR (251), UCHAR (255)));
5283 4 : range_cast (r0, signed_char_type_node);
5284 4 : ASSERT_TRUE (r0 == rold);
5285 :
5286 : // (signed char)[15, 150] => [-128,-106][15,127].
5287 4 : r0 = rold = int_range<1> (unsigned_char_type_node, UCHAR (15), UCHAR (150));
5288 4 : range_cast (r0, signed_char_type_node);
5289 4 : r1 = int_range<1> (signed_char_type_node, SCHAR (15), SCHAR (127));
5290 4 : r2 = int_range<1> (signed_char_type_node, SCHAR (-128), SCHAR (-106));
5291 4 : r1.union_ (r2);
5292 4 : ASSERT_TRUE (r1 == r0);
5293 4 : range_cast (r0, unsigned_char_type_node);
5294 4 : ASSERT_TRUE (r0 == rold);
5295 :
5296 : // (unsigned char)[-5, 5] => [0,5][251,255].
5297 4 : r0 = rold = int_range<1> (signed_char_type_node, SCHAR (-5), SCHAR (5));
5298 4 : range_cast (r0, unsigned_char_type_node);
5299 4 : r1 = int_range<1> (unsigned_char_type_node, UCHAR (251), UCHAR (255));
5300 4 : r2 = int_range<1> (unsigned_char_type_node, UCHAR (0), UCHAR (5));
5301 4 : r1.union_ (r2);
5302 4 : ASSERT_TRUE (r0 == r1);
5303 4 : range_cast (r0, signed_char_type_node);
5304 4 : ASSERT_TRUE (r0 == rold);
5305 :
5306 : // (unsigned char)[-5,5] => [0,5][251,255].
5307 4 : r0 = int_range<1> (integer_type_node, INT (-5), INT (5));
5308 4 : range_cast (r0, unsigned_char_type_node);
5309 4 : r1 = int_range<1> (unsigned_char_type_node, UCHAR (0), UCHAR (5));
5310 4 : r1.union_ (int_range<1> (unsigned_char_type_node, UCHAR (251), UCHAR (255)));
5311 4 : ASSERT_TRUE (r0 == r1);
5312 :
5313 : // (unsigned char)[5U,1974U] => [0,255].
5314 4 : r0 = int_range<1> (unsigned_type_node, UINT (5), UINT (1974));
5315 4 : range_cast (r0, unsigned_char_type_node);
5316 4 : ASSERT_TRUE (r0 == int_range<1> (unsigned_char_type_node, UCHAR (0), UCHAR (255)));
5317 4 : range_cast (r0, integer_type_node);
5318 : // Going to a wider range should not sign extend.
5319 4 : ASSERT_TRUE (r0 == int_range<1> (integer_type_node, INT (0), INT (255)));
5320 :
5321 : // (unsigned char)[-350,15] => [0,255].
5322 4 : r0 = int_range<1> (integer_type_node, INT (-350), INT (15));
5323 4 : range_cast (r0, unsigned_char_type_node);
5324 4 : ASSERT_TRUE (r0 == (int_range<1>
5325 : (unsigned_char_type_node,
5326 : min_limit (unsigned_char_type_node),
5327 : max_limit (unsigned_char_type_node))));
5328 :
5329 : // Casting [-120,20] from signed char to unsigned short.
5330 : // => [0, 20][0xff88, 0xffff].
5331 4 : r0 = int_range<1> (signed_char_type_node, SCHAR (-120), SCHAR (20));
5332 4 : range_cast (r0, short_unsigned_type_node);
5333 4 : r1 = int_range<1> (short_unsigned_type_node, UINT16 (0), UINT16 (20));
5334 8 : r2 = int_range<1> (short_unsigned_type_node,
5335 12 : UINT16 (0xff88), UINT16 (0xffff));
5336 4 : r1.union_ (r2);
5337 4 : ASSERT_TRUE (r0 == r1);
5338 : // A truncating cast back to signed char will work because [-120, 20]
5339 : // is representable in signed char.
5340 4 : range_cast (r0, signed_char_type_node);
5341 4 : ASSERT_TRUE (r0 == int_range<1> (signed_char_type_node,
5342 : SCHAR (-120), SCHAR (20)));
5343 :
5344 : // unsigned char -> signed short
5345 : // (signed short)[(unsigned char)25, (unsigned char)250]
5346 : // => [(signed short)25, (signed short)250]
5347 4 : r0 = rold = int_range<1> (unsigned_char_type_node, UCHAR (25), UCHAR (250));
5348 4 : range_cast (r0, short_integer_type_node);
5349 4 : r1 = int_range<1> (short_integer_type_node, INT16 (25), INT16 (250));
5350 4 : ASSERT_TRUE (r0 == r1);
5351 4 : range_cast (r0, unsigned_char_type_node);
5352 4 : ASSERT_TRUE (r0 == rold);
5353 :
5354 : // Test casting a wider signed [-MIN,MAX] to a narrower unsigned.
5355 8 : r0 = int_range<1> (long_long_integer_type_node,
5356 4 : min_limit (long_long_integer_type_node),
5357 8 : max_limit (long_long_integer_type_node));
5358 4 : range_cast (r0, short_unsigned_type_node);
5359 8 : r1 = int_range<1> (short_unsigned_type_node,
5360 4 : min_limit (short_unsigned_type_node),
5361 8 : max_limit (short_unsigned_type_node));
5362 4 : ASSERT_TRUE (r0 == r1);
5363 :
5364 : // Casting NONZERO to a narrower type will wrap/overflow so
5365 : // it's just the entire range for the narrower type.
5366 : //
5367 : // "NOT 0 at signed 32-bits" ==> [-MIN_32,-1][1, +MAX_32]. This is
5368 : // is outside of the range of a smaller range, return the full
5369 : // smaller range.
5370 4 : if (TYPE_PRECISION (integer_type_node)
5371 4 : > TYPE_PRECISION (short_integer_type_node))
5372 : {
5373 4 : r0.set_nonzero (integer_type_node);
5374 4 : range_cast (r0, short_integer_type_node);
5375 8 : r1 = int_range<1> (short_integer_type_node,
5376 4 : min_limit (short_integer_type_node),
5377 8 : max_limit (short_integer_type_node));
5378 4 : ASSERT_TRUE (r0 == r1);
5379 : }
5380 :
5381 : // Casting NONZERO from a narrower signed to a wider signed.
5382 : //
5383 : // NONZERO signed 16-bits is [-MIN_16,-1][1, +MAX_16].
5384 : // Converting this to 32-bits signed is [-MIN_16,-1][1, +MAX_16].
5385 4 : r0.set_nonzero (short_integer_type_node);
5386 4 : range_cast (r0, integer_type_node);
5387 4 : r1 = int_range<1> (integer_type_node, INT (-32768), INT (-1));
5388 4 : r2 = int_range<1> (integer_type_node, INT (1), INT (32767));
5389 4 : r1.union_ (r2);
5390 4 : ASSERT_TRUE (r0 == r1);
5391 4 : }
5392 :
5393 : static void
5394 4 : range_op_lshift_tests ()
5395 : {
5396 : // Test that 0x808.... & 0x8.... still contains 0x8....
5397 : // for a large set of numbers.
5398 4 : {
5399 4 : int_range_max res;
5400 4 : tree big_type = long_long_unsigned_type_node;
5401 4 : unsigned big_prec = TYPE_PRECISION (big_type);
5402 : // big_num = 0x808,0000,0000,0000
5403 4 : wide_int big_num = wi::lshift (wi::uhwi (0x808, big_prec),
5404 8 : wi::uhwi (48, big_prec));
5405 8 : op_bitwise_and.fold_range (res, big_type,
5406 8 : int_range <1> (big_type),
5407 8 : int_range <1> (big_type, big_num, big_num));
5408 : // val = 0x8,0000,0000,0000
5409 4 : wide_int val = wi::lshift (wi::uhwi (8, big_prec),
5410 8 : wi::uhwi (48, big_prec));
5411 4 : ASSERT_TRUE (res.contains_p (val));
5412 4 : }
5413 :
5414 4 : if (TYPE_PRECISION (unsigned_type_node) > 31)
5415 : {
5416 : // unsigned VARYING = op1 << 1 should be VARYING.
5417 4 : int_range<2> lhs (unsigned_type_node);
5418 4 : int_range<2> shift (unsigned_type_node, INT (1), INT (1));
5419 4 : int_range_max op1;
5420 4 : op_lshift.op1_range (op1, unsigned_type_node, lhs, shift);
5421 4 : ASSERT_TRUE (op1.varying_p ());
5422 :
5423 : // 0 = op1 << 1 should be [0,0], [0x8000000, 0x8000000].
5424 4 : int_range<2> zero (unsigned_type_node, UINT (0), UINT (0));
5425 4 : op_lshift.op1_range (op1, unsigned_type_node, zero, shift);
5426 4 : ASSERT_TRUE (op1.num_pairs () == 2);
5427 : // Remove the [0,0] range.
5428 4 : op1.intersect (zero);
5429 4 : ASSERT_TRUE (op1.num_pairs () == 1);
5430 : // op1 << 1 should be [0x8000,0x8000] << 1,
5431 : // which should result in [0,0].
5432 4 : int_range_max result;
5433 4 : op_lshift.fold_range (result, unsigned_type_node, op1, shift);
5434 4 : ASSERT_TRUE (result == zero);
5435 4 : }
5436 : // signed VARYING = op1 << 1 should be VARYING.
5437 4 : if (TYPE_PRECISION (integer_type_node) > 31)
5438 : {
5439 : // unsigned VARYING = op1 << 1 should be VARYING.
5440 4 : int_range<2> lhs (integer_type_node);
5441 4 : int_range<2> shift (integer_type_node, INT (1), INT (1));
5442 4 : int_range_max op1;
5443 4 : op_lshift.op1_range (op1, integer_type_node, lhs, shift);
5444 4 : ASSERT_TRUE (op1.varying_p ());
5445 :
5446 : // 0 = op1 << 1 should be [0,0], [0x8000000, 0x8000000].
5447 4 : int_range<2> zero (integer_type_node, INT (0), INT (0));
5448 4 : op_lshift.op1_range (op1, integer_type_node, zero, shift);
5449 4 : ASSERT_TRUE (op1.num_pairs () == 2);
5450 : // Remove the [0,0] range.
5451 4 : op1.intersect (zero);
5452 4 : ASSERT_TRUE (op1.num_pairs () == 1);
5453 : // op1 << 1 should be [0x8000,0x8000] << 1,
5454 : // which should result in [0,0].
5455 4 : int_range_max result;
5456 4 : op_lshift.fold_range (result, unsigned_type_node, op1, shift);
5457 4 : ASSERT_TRUE (result == zero);
5458 4 : }
5459 4 : }
5460 :
5461 : static void
5462 4 : range_op_rshift_tests ()
5463 : {
5464 : // unsigned: [3, MAX] = OP1 >> 1
5465 4 : {
5466 4 : int_range_max lhs (unsigned_type_node,
5467 4 : UINT (3), max_limit (unsigned_type_node));
5468 4 : int_range_max one (unsigned_type_node,
5469 8 : wi::one (TYPE_PRECISION (unsigned_type_node)),
5470 8 : wi::one (TYPE_PRECISION (unsigned_type_node)));
5471 4 : int_range_max op1;
5472 4 : op_rshift.op1_range (op1, unsigned_type_node, lhs, one);
5473 4 : ASSERT_FALSE (op1.contains_p (UINT (3)));
5474 4 : }
5475 :
5476 : // signed: [3, MAX] = OP1 >> 1
5477 4 : {
5478 4 : int_range_max lhs (integer_type_node,
5479 4 : INT (3), max_limit (integer_type_node));
5480 4 : int_range_max one (integer_type_node, INT (1), INT (1));
5481 4 : int_range_max op1;
5482 4 : op_rshift.op1_range (op1, integer_type_node, lhs, one);
5483 4 : ASSERT_FALSE (op1.contains_p (INT (-2)));
5484 4 : }
5485 :
5486 : // This is impossible, so OP1 should be [].
5487 : // signed: [MIN, MIN] = OP1 >> 1
5488 4 : {
5489 4 : int_range_max lhs (integer_type_node,
5490 4 : min_limit (integer_type_node),
5491 4 : min_limit (integer_type_node));
5492 4 : int_range_max one (integer_type_node, INT (1), INT (1));
5493 4 : int_range_max op1;
5494 4 : op_rshift.op1_range (op1, integer_type_node, lhs, one);
5495 4 : ASSERT_TRUE (op1.undefined_p ());
5496 4 : }
5497 :
5498 : // signed: ~[-1] = OP1 >> 31
5499 4 : if (TYPE_PRECISION (integer_type_node) > 31)
5500 : {
5501 4 : int_range_max lhs (integer_type_node, INT (-1), INT (-1), VR_ANTI_RANGE);
5502 4 : int_range_max shift (integer_type_node, INT (31), INT (31));
5503 4 : int_range_max op1;
5504 4 : op_rshift.op1_range (op1, integer_type_node, lhs, shift);
5505 4 : int_range_max negatives = range_negatives (integer_type_node);
5506 4 : negatives.intersect (op1);
5507 4 : ASSERT_TRUE (negatives.undefined_p ());
5508 4 : }
5509 4 : }
5510 :
5511 : static void
5512 4 : range_op_bitwise_and_tests ()
5513 : {
5514 4 : int_range_max res;
5515 4 : wide_int min = min_limit (integer_type_node);
5516 4 : wide_int max = max_limit (integer_type_node);
5517 4 : wide_int tiny = wi::add (min, wi::one (TYPE_PRECISION (integer_type_node)));
5518 4 : int_range_max i1 (integer_type_node, tiny, max);
5519 4 : int_range_max i2 (integer_type_node, INT (255), INT (255));
5520 :
5521 : // [MIN+1, MAX] = OP1 & 255: OP1 is VARYING
5522 4 : op_bitwise_and.op1_range (res, integer_type_node, i1, i2);
5523 4 : ASSERT_TRUE (res == int_range<1> (integer_type_node));
5524 :
5525 : // VARYING = OP1 & 255: OP1 is VARYING
5526 4 : i1 = int_range<1> (integer_type_node);
5527 4 : op_bitwise_and.op1_range (res, integer_type_node, i1, i2);
5528 4 : ASSERT_TRUE (res == int_range<1> (integer_type_node));
5529 :
5530 : // For 0 = x & MASK, x is ~MASK.
5531 4 : {
5532 4 : int_range<2> zero (integer_type_node, INT (0), INT (0));
5533 4 : int_range<2> mask = int_range<2> (integer_type_node, INT (7), INT (7));
5534 4 : op_bitwise_and.op1_range (res, integer_type_node, zero, mask);
5535 4 : wide_int inv = wi::shwi (~7U, TYPE_PRECISION (integer_type_node));
5536 4 : ASSERT_TRUE (res.get_nonzero_bits () == inv);
5537 4 : }
5538 :
5539 : // (NONZERO | X) is nonzero.
5540 4 : i1.set_nonzero (integer_type_node);
5541 4 : i2.set_varying (integer_type_node);
5542 4 : op_bitwise_or.fold_range (res, integer_type_node, i1, i2);
5543 4 : ASSERT_FALSE (res.contains_zero_p ());
5544 :
5545 : // (NEGATIVE | X) is nonzero.
5546 4 : i1 = int_range<1> (integer_type_node, INT (-5), INT (-3));
5547 4 : i2.set_varying (integer_type_node);
5548 4 : op_bitwise_or.fold_range (res, integer_type_node, i1, i2);
5549 4 : ASSERT_FALSE (res.contains_p (INT (0)));
5550 4 : }
5551 :
5552 : static void
5553 4 : range_relational_tests ()
5554 : {
5555 4 : int_range<2> lhs (unsigned_char_type_node);
5556 4 : int_range<2> op1 (unsigned_char_type_node, UCHAR (8), UCHAR (10));
5557 4 : int_range<2> op2 (unsigned_char_type_node, UCHAR (20), UCHAR (20));
5558 :
5559 : // Never wrapping additions mean LHS > OP1.
5560 4 : relation_kind code = op_plus.lhs_op1_relation (lhs, op1, op2, VREL_VARYING);
5561 4 : ASSERT_TRUE (code == VREL_GT);
5562 :
5563 : // Most wrapping additions mean nothing...
5564 4 : op1 = int_range<2> (unsigned_char_type_node, UCHAR (8), UCHAR (10));
5565 4 : op2 = int_range<2> (unsigned_char_type_node, UCHAR (0), UCHAR (255));
5566 4 : code = op_plus.lhs_op1_relation (lhs, op1, op2, VREL_VARYING);
5567 4 : ASSERT_TRUE (code == VREL_VARYING);
5568 :
5569 : // However, always wrapping additions mean LHS < OP1.
5570 4 : op1 = int_range<2> (unsigned_char_type_node, UCHAR (1), UCHAR (255));
5571 4 : op2 = int_range<2> (unsigned_char_type_node, UCHAR (255), UCHAR (255));
5572 4 : code = op_plus.lhs_op1_relation (lhs, op1, op2, VREL_VARYING);
5573 4 : ASSERT_TRUE (code == VREL_LT);
5574 4 : }
5575 :
5576 : void
5577 4 : range_op_tests ()
5578 : {
5579 4 : range_op_rshift_tests ();
5580 4 : range_op_lshift_tests ();
5581 4 : range_op_bitwise_and_tests ();
5582 4 : range_op_cast_tests ();
5583 4 : range_relational_tests ();
5584 :
5585 4 : extern void range_op_float_tests ();
5586 4 : range_op_float_tests ();
5587 4 : }
5588 :
5589 : } // namespace selftest
5590 :
5591 : #endif // CHECKING_P
|
