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 292658 : range_op_table::range_op_table ()
83 : {
84 292658 : initialize_integral_ops ();
85 292658 : initialize_pointer_ops ();
86 292658 : initialize_float_ops ();
87 :
88 292658 : set (EQ_EXPR, op_equal);
89 292658 : set (NE_EXPR, op_not_equal);
90 292658 : set (LT_EXPR, op_lt);
91 292658 : set (LE_EXPR, op_le);
92 292658 : set (GT_EXPR, op_gt);
93 292658 : set (GE_EXPR, op_ge);
94 292658 : set (SSA_NAME, op_ident);
95 292658 : set (PAREN_EXPR, op_ident);
96 292658 : set (OBJ_TYPE_REF, op_ident);
97 292658 : set (REAL_CST, op_cst);
98 292658 : set (INTEGER_CST, op_cst);
99 292658 : set (NOP_EXPR, op_cast);
100 292658 : set (CONVERT_EXPR, op_cast);
101 292658 : set (VIEW_CONVERT_EXPR, op_view);
102 292658 : set (FLOAT_EXPR, op_cast);
103 292658 : set (FIX_TRUNC_EXPR, op_cast);
104 292658 : set (PLUS_EXPR, op_plus);
105 292658 : set (ABS_EXPR, op_abs);
106 292658 : set (MINUS_EXPR, op_minus);
107 292658 : set (NEGATE_EXPR, op_negate);
108 292658 : set (MULT_EXPR, op_mult);
109 292658 : set (ADDR_EXPR, op_addr);
110 292658 : set (BIT_NOT_EXPR, op_bitwise_not);
111 292658 : set (BIT_XOR_EXPR, op_bitwise_xor);
112 292658 : set (BIT_AND_EXPR, op_bitwise_and);
113 292658 : set (BIT_IOR_EXPR, op_bitwise_or);
114 292658 : set (MIN_EXPR, op_min);
115 292658 : set (MAX_EXPR, op_max);
116 292658 : }
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 1804100204 : range_op_handler::range_op_handler ()
125 : {
126 1804100204 : m_operator = &default_operator;
127 1804100204 : }
128 :
129 : // Create a range_op_handler for CODE. Use a default operator if CODE
130 : // does not have an entry.
131 :
132 4313730757 : range_op_handler::range_op_handler (unsigned code)
133 : {
134 4313730757 : m_operator = operator_table[code];
135 4313730757 : if (!m_operator)
136 840018165 : m_operator = &default_operator;
137 4313730757 : }
138 :
139 : // Return TRUE if this handler has a non-default operator.
140 :
141 6352434986 : range_op_handler::operator bool () const
142 : {
143 6352434986 : 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 1064697924 : range_op_handler::range_op () const
152 : {
153 1064697924 : if (m_operator != &default_operator)
154 1064697924 : 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 647051583 : dispatch_trio (unsigned lhs, unsigned op1, unsigned op2)
164 : {
165 647051583 : 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 647051583 : range_op_handler::dispatch_kind (const vrange &lhs, const vrange &op1,
191 : const vrange& op2) const
192 : {
193 647051583 : return dispatch_trio (lhs.m_discriminator, op1.m_discriminator,
194 647051583 : 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 290599385 : range_op_handler::fold_range (vrange &r, tree type,
224 : const vrange &lh,
225 : const vrange &rh,
226 : relation_trio rel) const
227 : {
228 290599385 : gcc_checking_assert (m_operator);
229 : #if CHECKING_P
230 290599385 : if (!lh.undefined_p () && !rh.undefined_p ())
231 284925785 : gcc_assert (m_operator->operand_check_p (type, lh.type (), rh.type ()));
232 : #endif
233 290599385 : switch (dispatch_kind (r, lh, rh))
234 : {
235 220662540 : case RO_III:
236 220662540 : return m_operator->fold_range (as_a <irange> (r), type,
237 : as_a <irange> (lh),
238 220662540 : as_a <irange> (rh), rel);
239 356674 : case RO_IFI:
240 356674 : return m_operator->fold_range (as_a <irange> (r), type,
241 : as_a <frange> (lh),
242 356674 : as_a <irange> (rh), rel);
243 2670636 : case RO_IFF:
244 2670636 : return m_operator->fold_range (as_a <irange> (r), type,
245 : as_a <frange> (lh),
246 2670636 : as_a <frange> (rh), rel);
247 7140328 : case RO_FFF:
248 7140328 : return m_operator->fold_range (as_a <frange> (r), type,
249 : as_a <frange> (lh),
250 7140328 : 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 894207 : case RO_FIF:
256 894207 : return m_operator->fold_range (as_a <frange> (r), type,
257 : as_a <irange> (lh),
258 894207 : as_a <frange> (rh), rel);
259 18409959 : case RO_PPP:
260 18409959 : return m_operator->fold_range (as_a <prange> (r), type,
261 : as_a <prange> (lh),
262 18409959 : as_a <prange> (rh), rel);
263 9094694 : case RO_PPI:
264 9094694 : return m_operator->fold_range (as_a <prange> (r), type,
265 : as_a <prange> (lh),
266 9094694 : as_a <irange> (rh), rel);
267 18329984 : case RO_IPP:
268 18329984 : return m_operator->fold_range (as_a <irange> (r), type,
269 : as_a <prange> (lh),
270 18329984 : as_a <prange> (rh), rel);
271 1955223 : case RO_PIP:
272 1955223 : return m_operator->fold_range (as_a <prange> (r), type,
273 : as_a <irange> (lh),
274 1955223 : as_a <prange> (rh), rel);
275 11085108 : case RO_IPI:
276 11085108 : return m_operator->fold_range (as_a <irange> (r), type,
277 : as_a <prange> (lh),
278 11085108 : 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 92243182 : range_op_handler::op1_range (vrange &r, tree type,
288 : const vrange &lhs,
289 : const vrange &op2,
290 : relation_trio rel) const
291 : {
292 92243182 : gcc_checking_assert (m_operator);
293 92243182 : if (lhs.undefined_p ())
294 : return false;
295 : #if CHECKING_P
296 92242105 : if (!op2.undefined_p ())
297 92241921 : gcc_assert (m_operator->operand_check_p (lhs.type (), type, op2.type ()));
298 : #endif
299 92242105 : switch (dispatch_kind (r, lhs, op2))
300 : {
301 79729916 : case RO_III:
302 79729916 : return m_operator->op1_range (as_a <irange> (r), type,
303 : as_a <irange> (lhs),
304 79729916 : as_a <irange> (op2), rel);
305 214431 : case RO_IFI:
306 214431 : return m_operator->op1_range (as_a <irange> (r), type,
307 : as_a <frange> (lhs),
308 214431 : as_a <irange> (op2), rel);
309 776808 : case RO_PPP:
310 776808 : return m_operator->op1_range (as_a <prange> (r), type,
311 : as_a <prange> (lhs),
312 776808 : as_a <prange> (op2), rel);
313 8534775 : case RO_PIP:
314 8534775 : return m_operator->op1_range (as_a <prange> (r), type,
315 : as_a <irange> (lhs),
316 8534775 : as_a <prange> (op2), rel);
317 407866 : case RO_PPI:
318 407866 : return m_operator->op1_range (as_a <prange> (r), type,
319 : as_a <prange> (lhs),
320 407866 : as_a <irange> (op2), rel);
321 236776 : case RO_IPI:
322 236776 : return m_operator->op1_range (as_a <irange> (r), type,
323 : as_a <prange> (lhs),
324 236776 : as_a <irange> (op2), rel);
325 1476577 : case RO_FIF:
326 1476577 : return m_operator->op1_range (as_a <frange> (r), type,
327 : as_a <irange> (lhs),
328 1476577 : as_a <frange> (op2), rel);
329 864956 : case RO_FFF:
330 864956 : return m_operator->op1_range (as_a <frange> (r), type,
331 : as_a <frange> (lhs),
332 864956 : 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 25611056 : range_op_handler::op2_range (vrange &r, tree type,
342 : const vrange &lhs,
343 : const vrange &op1,
344 : relation_trio rel) const
345 : {
346 25611056 : gcc_checking_assert (m_operator);
347 25611056 : if (lhs.undefined_p ())
348 : return false;
349 : #if CHECKING_P
350 25611034 : if (!op1.undefined_p ())
351 25610941 : gcc_assert (m_operator->operand_check_p (lhs.type (), op1.type (), type));
352 : #endif
353 25611034 : switch (dispatch_kind (r, lhs, op1))
354 : {
355 19799223 : case RO_III:
356 19799223 : return m_operator->op2_range (as_a <irange> (r), type,
357 : as_a <irange> (lhs),
358 19799223 : as_a <irange> (op1), rel);
359 4753356 : case RO_PIP:
360 4753356 : return m_operator->op2_range (as_a <prange> (r), type,
361 : as_a <irange> (lhs),
362 4753356 : as_a <prange> (op1), rel);
363 227088 : case RO_IPP:
364 227088 : return m_operator->op2_range (as_a <irange> (r), type,
365 : as_a <prange> (lhs),
366 227088 : as_a <prange> (op1), rel);
367 500573 : case RO_FIF:
368 500573 : return m_operator->op2_range (as_a <frange> (r), type,
369 : as_a <irange> (lhs),
370 500573 : as_a <frange> (op1), rel);
371 330658 : case RO_FFF:
372 330658 : return m_operator->op2_range (as_a <frange> (r), type,
373 : as_a <frange> (lhs),
374 330658 : 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 122142955 : range_op_handler::lhs_op1_relation (const vrange &lhs,
384 : const vrange &op1,
385 : const vrange &op2,
386 : relation_kind rel) const
387 : {
388 122142955 : gcc_checking_assert (m_operator);
389 122142955 : switch (dispatch_kind (lhs, op1, op2))
390 : {
391 97840737 : case RO_III:
392 97840737 : return m_operator->lhs_op1_relation (as_a <irange> (lhs),
393 : as_a <irange> (op1),
394 97840737 : as_a <irange> (op2), rel);
395 1461879 : case RO_PPP:
396 1461879 : return m_operator->lhs_op1_relation (as_a <prange> (lhs),
397 : as_a <prange> (op1),
398 1461879 : as_a <prange> (op2), rel);
399 6203772 : case RO_IPP:
400 6203772 : return m_operator->lhs_op1_relation (as_a <irange> (lhs),
401 : as_a <prange> (op1),
402 6203772 : as_a <prange> (op2), rel);
403 1461631 : case RO_PII:
404 1461631 : return m_operator->lhs_op1_relation (as_a <prange> (lhs),
405 : as_a <irange> (op1),
406 1461631 : as_a <irange> (op2), rel);
407 7820162 : case RO_PPI:
408 7820162 : return m_operator->lhs_op1_relation (as_a <prange> (lhs),
409 : as_a <prange> (op1),
410 7820162 : as_a <irange> (op2), rel);
411 1073832 : case RO_IFF:
412 1073832 : return m_operator->lhs_op1_relation (as_a <irange> (lhs),
413 : as_a <frange> (op1),
414 1073832 : as_a <frange> (op2), rel);
415 5387282 : case RO_FFF:
416 5387282 : return m_operator->lhs_op1_relation (as_a <frange> (lhs),
417 : as_a <frange> (op1),
418 5387282 : 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 36874010 : range_op_handler::lhs_op2_relation (const vrange &lhs,
428 : const vrange &op1,
429 : const vrange &op2,
430 : relation_kind rel) const
431 : {
432 36874010 : gcc_checking_assert (m_operator);
433 36874010 : switch (dispatch_kind (lhs, op1, op2))
434 : {
435 25521841 : case RO_III:
436 25521841 : return m_operator->lhs_op2_relation (as_a <irange> (lhs),
437 : as_a <irange> (op1),
438 25521841 : as_a <irange> (op2), rel);
439 195182 : case RO_IFF:
440 195182 : return m_operator->lhs_op2_relation (as_a <irange> (lhs),
441 : as_a <frange> (op1),
442 195182 : as_a <frange> (op2), rel);
443 3265487 : case RO_FFF:
444 3265487 : return m_operator->lhs_op2_relation (as_a <frange> (lhs),
445 : as_a <frange> (op1),
446 3265487 : 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 79537210 : range_op_handler::op1_op2_relation (const vrange &lhs,
456 : const vrange &op1,
457 : const vrange &op2) const
458 : {
459 79537210 : gcc_checking_assert (m_operator);
460 :
461 79537210 : switch (dispatch_kind (lhs, op1, op2))
462 : {
463 61717899 : case RO_III:
464 61717899 : return m_operator->op1_op2_relation (as_a <irange> (lhs),
465 : as_a <irange> (op1),
466 61717899 : as_a <irange> (op2));
467 :
468 15078186 : case RO_IPP:
469 15078186 : return m_operator->op1_op2_relation (as_a <irange> (lhs),
470 : as_a <prange> (op1),
471 15078186 : as_a <prange> (op2));
472 :
473 1790698 : case RO_IFF:
474 1790698 : return m_operator->op1_op2_relation (as_a <irange> (lhs),
475 : as_a <frange> (op1),
476 1790698 : as_a <frange> (op2));
477 :
478 607646 : case RO_FFF:
479 607646 : return m_operator->op1_op2_relation (as_a <frange> (lhs),
480 : as_a <frange> (op1),
481 607646 : as_a <frange> (op2));
482 :
483 : default:
484 : return VREL_VARYING;
485 : }
486 : }
487 :
488 : bool
489 44884 : range_op_handler::overflow_free_p (const vrange &lh,
490 : const vrange &rh,
491 : relation_trio rel) const
492 : {
493 44884 : gcc_checking_assert (m_operator);
494 44884 : switch (dispatch_kind (lh, lh, rh))
495 : {
496 44884 : case RO_III:
497 44884 : return m_operator->overflow_free_p(as_a <irange> (lh),
498 : as_a <irange> (rh),
499 44884 : rel);
500 : default:
501 : return false;
502 : }
503 : }
504 :
505 : bool
506 9246550 : range_op_handler::operand_check_p (tree t1, tree t2, tree t3) const
507 : {
508 9246550 : gcc_checking_assert (m_operator);
509 9246550 : 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 171013485 : update_known_bitmask (vrange &r, tree_code code,
517 : const vrange &lh, const vrange &rh)
518 : {
519 171013485 : if (r.undefined_p () || lh.undefined_p () || rh.undefined_p ()
520 342022794 : || r.singleton_p ())
521 8352326 : return;
522 :
523 162661159 : widest_int widest_value, widest_mask;
524 162661159 : tree type = r.type ();
525 162661159 : signop sign = TYPE_SIGN (type);
526 162661159 : int prec = TYPE_PRECISION (type);
527 162661159 : irange_bitmask lh_bits = lh.get_bitmask ();
528 162661159 : irange_bitmask rh_bits = rh.get_bitmask ();
529 :
530 162661159 : switch (get_gimple_rhs_class (code))
531 : {
532 57277188 : case GIMPLE_UNARY_RHS:
533 57277188 : bit_value_unop (code, sign, prec, &widest_value, &widest_mask,
534 57277188 : TYPE_SIGN (lh.type ()),
535 57277188 : TYPE_PRECISION (lh.type ()),
536 114554888 : widest_int::from (lh_bits.value (),
537 57277188 : TYPE_SIGN (lh.type ())),
538 114554376 : widest_int::from (lh_bits.mask (),
539 57277188 : TYPE_SIGN (lh.type ())));
540 57277188 : break;
541 105383971 : case GIMPLE_BINARY_RHS:
542 210767942 : bit_value_binop (code, sign, prec, &widest_value, &widest_mask,
543 105383971 : TYPE_SIGN (lh.type ()),
544 105383971 : TYPE_PRECISION (lh.type ()),
545 210768929 : widest_int::from (lh_bits.value (), sign),
546 210768929 : widest_int::from (lh_bits.mask (), sign),
547 105383971 : TYPE_SIGN (rh.type ()),
548 105383971 : TYPE_PRECISION (rh.type ()),
549 210768896 : widest_int::from (rh_bits.value (), sign),
550 210767942 : widest_int::from (rh_bits.mask (), sign));
551 105383971 : break;
552 0 : default:
553 0 : gcc_unreachable ();
554 : }
555 :
556 162661159 : wide_int mask = wide_int::from (widest_mask, prec, sign);
557 325322318 : wide_int value = wide_int::from (widest_value, prec, sign);
558 : // Bitmasks must have the unknown value bits cleared.
559 162661159 : value &= ~mask;
560 325322318 : irange_bitmask bm (value, mask);
561 162661159 : r.update_bitmask (bm);
562 162662167 : }
563 :
564 : // Return the upper limit for a type.
565 :
566 : static inline wide_int
567 17490102 : max_limit (const_tree type)
568 : {
569 17490102 : return irange_val_max (type);
570 : }
571 :
572 : // Return the lower limit for a type.
573 :
574 : static inline wide_int
575 19846133 : min_limit (const_tree type)
576 : {
577 19846133 : 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 4786727 : get_shift_range (irange &r, tree type, const irange &op)
586 : {
587 4786727 : if (op.undefined_p ())
588 : return false;
589 :
590 : // Build valid range and intersect it with the shift range.
591 4786304 : r.set (op.type (),
592 9572608 : wi::shwi (0, TYPE_PRECISION (op.type ())),
593 4786304 : wi::shwi (TYPE_PRECISION (type) - 1, TYPE_PRECISION (op.type ())));
594 4786304 : r.intersect (op);
595 :
596 : // If there are no valid ranges in the shift range, returned false.
597 4786304 : if (r.undefined_p ())
598 : return false;
599 : return true;
600 : }
601 :
602 : // Default wide_int fold operation returns [MIN, MAX].
603 :
604 : void
605 0 : range_operator::wi_fold (irange &r, tree type,
606 : const wide_int &lh_lb ATTRIBUTE_UNUSED,
607 : const wide_int &lh_ub ATTRIBUTE_UNUSED,
608 : const wide_int &rh_lb ATTRIBUTE_UNUSED,
609 : const wide_int &rh_ub ATTRIBUTE_UNUSED) const
610 : {
611 0 : gcc_checking_assert (r.supports_type_p (type));
612 0 : r.set_varying (type);
613 0 : }
614 :
615 : // Call wi_fold when both op1 and op2 are equivalent. Further split small
616 : // subranges into constants. This can provide better precision.
617 : // For x + y, when x == y with a range of [0,4] instead of [0, 8] produce
618 : // [0,0][2, 2][4,4][6, 6][8, 8]
619 : // LIMIT is the maximum number of elements in range allowed before we
620 : // do not process them individually.
621 :
622 : void
623 53866 : 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 53866 : int_range_max tmp;
629 107732 : widest_int lh_range = wi::sub (widest_int::from (lh_ub, TYPE_SIGN (type)),
630 107732 : widest_int::from (lh_lb, TYPE_SIGN (type)));
631 : // if there are 1 to 8 values in the LH range, split them up.
632 53866 : r.set_undefined ();
633 107732 : if (lh_range >= 0 && lh_range < limit)
634 : {
635 16847 : for (unsigned x = 0; x <= lh_range; x++)
636 : {
637 11443 : wide_int val = lh_lb + x;
638 11443 : wi_fold (tmp, type, val, val, val, val);
639 11443 : r.union_ (tmp);
640 11443 : }
641 : }
642 : // Otherwise just call wi_fold.
643 : else
644 48462 : wi_fold (r, type, lh_lb, lh_ub, lh_lb, lh_ub);
645 53866 : }
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 139860921 : 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 139860921 : int_range_max tmp;
659 279721842 : widest_int rh_range = wi::sub (widest_int::from (rh_ub, TYPE_SIGN (type)),
660 279721842 : widest_int::from (rh_lb, TYPE_SIGN (type)));
661 279721842 : widest_int lh_range = wi::sub (widest_int::from (lh_ub, TYPE_SIGN (type)),
662 279721842 : 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 139860921 : if (rh_range > 0 && rh_range < 4)
666 : {
667 5129853 : wi_fold_in_parts (r, type, lh_lb, lh_ub, rh_lb, rh_lb);
668 5129853 : if (rh_range > 1)
669 : {
670 605913 : wi_fold_in_parts (tmp, type, lh_lb, lh_ub, rh_lb + 1, rh_lb + 1);
671 605913 : r.union_ (tmp);
672 605913 : if (rh_range == 3)
673 : {
674 389161 : wi_fold_in_parts (tmp, type, lh_lb, lh_ub, rh_lb + 2, rh_lb + 2);
675 389161 : r.union_ (tmp);
676 : }
677 : }
678 5129853 : wi_fold_in_parts (tmp, type, lh_lb, lh_ub, rh_ub, rh_ub);
679 5129853 : 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 134731068 : else if (lh_range > 0 && lh_range < 4)
684 : {
685 9851679 : wi_fold (r, type, lh_lb, lh_lb, rh_lb, rh_ub);
686 9851679 : if (lh_range > 1)
687 : {
688 1629644 : wi_fold (tmp, type, lh_lb + 1, lh_lb + 1, rh_lb, rh_ub);
689 1629636 : r.union_ (tmp);
690 1629636 : if (lh_range == 3)
691 : {
692 700476 : wi_fold (tmp, type, lh_lb + 2, lh_lb + 2, rh_lb, rh_ub);
693 700472 : r.union_ (tmp);
694 : }
695 : }
696 9851679 : wi_fold (tmp, type, lh_ub, lh_ub, rh_lb, rh_ub);
697 9851679 : r.union_ (tmp);
698 : }
699 : // Otherwise just call wi_fold.
700 : else
701 124879389 : wi_fold (r, type, lh_lb, lh_ub, rh_lb, rh_ub);
702 139861280 : }
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 97937496 : range_operator::fold_range (irange &r, tree type,
709 : const irange &lh,
710 : const irange &rh,
711 : relation_trio trio) const
712 : {
713 97937496 : gcc_checking_assert (r.supports_type_p (type));
714 97937496 : if (empty_range_varying (r, type, lh, rh))
715 46692 : return true;
716 :
717 97890804 : relation_kind rel = trio.op1_op2 ();
718 97890804 : unsigned num_lh = lh.num_pairs ();
719 97890804 : 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 97892052 : if (relation_equiv_p (rel) && lh == rh)
724 : {
725 50465 : int_range_max tmp;
726 50465 : r.set_undefined ();
727 91997 : for (unsigned x = 0; x < num_lh; ++x)
728 : {
729 : // If the number of subranges is too high, limit subrange creation.
730 53866 : unsigned limit = (r.num_pairs () > 32) ? 0 : 8;
731 53866 : wide_int lh_lb = lh.lower_bound (x);
732 53866 : wide_int lh_ub = lh.upper_bound (x);
733 53866 : wi_fold_in_parts_equiv (tmp, type, lh_lb, lh_ub, limit);
734 53866 : r.union_ (tmp);
735 53866 : if (r.varying_p ())
736 : break;
737 53866 : }
738 50465 : op1_op2_relation_effect (r, type, lh, rh, rel);
739 50465 : update_bitmask (r, lh, rh);
740 50465 : return true;
741 50465 : }
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 97840339 : if ((num_lh == 1 && num_rh == 1) || num_lh * num_rh > 12)
747 : {
748 81220118 : wi_fold_in_parts (r, type, lh.lower_bound (), lh.upper_bound (),
749 162437684 : rh.lower_bound (), rh.upper_bound ());
750 81218842 : op1_op2_relation_effect (r, type, lh, rh, rel);
751 81218842 : update_bitmask (r, lh, rh);
752 81218842 : return true;
753 : }
754 :
755 16621497 : int_range_max tmp;
756 16621497 : r.set_undefined ();
757 51545919 : for (unsigned x = 0; x < num_lh; ++x)
758 82311721 : for (unsigned y = 0; y < num_rh; ++y)
759 : {
760 47387299 : wide_int lh_lb = lh.lower_bound (x);
761 47387299 : wide_int lh_ub = lh.upper_bound (x);
762 47387299 : wide_int rh_lb = rh.lower_bound (y);
763 47387299 : wide_int rh_ub = rh.upper_bound (y);
764 47387299 : wi_fold_in_parts (tmp, type, lh_lb, lh_ub, rh_lb, rh_ub);
765 47387299 : r.union_ (tmp);
766 47387299 : if (r.varying_p ())
767 : {
768 3941081 : op1_op2_relation_effect (r, type, lh, rh, rel);
769 3941081 : update_bitmask (r, lh, rh);
770 3941081 : return true;
771 : }
772 47388592 : }
773 12680416 : op1_op2_relation_effect (r, type, lh, rh, rel);
774 12680416 : update_bitmask (r, lh, rh);
775 12680416 : return true;
776 16621497 : }
777 :
778 :
779 : bool
780 71117 : range_operator::fold_range (frange &, tree, const irange &,
781 : const frange &, relation_trio) const
782 : {
783 71117 : return false;
784 : }
785 :
786 : bool
787 1265 : range_operator::op1_range (irange &, tree, const frange &,
788 : const irange &, relation_trio) const
789 : {
790 1265 : return false;
791 : }
792 :
793 :
794 :
795 : // The default for op1_range is to return false.
796 :
797 : bool
798 783453 : 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 783453 : return false;
805 : }
806 :
807 : // The default for op2_range is to return false.
808 :
809 : bool
810 553813 : 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 553813 : return false;
817 : }
818 :
819 : // The default relation routines return VREL_VARYING.
820 :
821 : relation_kind
822 24286686 : 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 24286686 : return VREL_VARYING;
828 : }
829 :
830 : relation_kind
831 17528952 : 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 17528952 : return VREL_VARYING;
837 : }
838 :
839 : relation_kind
840 14860301 : 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 14860301 : return VREL_VARYING;
845 : }
846 :
847 : // Default is no relation affects the LHS.
848 :
849 : bool
850 66477114 : 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 66477114 : 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 6147 : range_operator::update_bitmask (irange &, const irange &,
873 : const irange &) const
874 : {
875 6147 : }
876 :
877 : // Check that operand types are OK. Default to always OK.
878 :
879 : bool
880 126054511 : range_operator::operand_check_p (tree, tree, tree) const
881 : {
882 126054511 : 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 39669924 : value_range_from_overflowed_bounds (irange &r, tree type,
890 : const wide_int &wmin,
891 : const wide_int &wmax)
892 : {
893 39669924 : const signop sgn = TYPE_SIGN (type);
894 39669924 : const unsigned int prec = TYPE_PRECISION (type);
895 :
896 39669924 : wide_int tmin = wide_int::from (wmin, prec, sgn);
897 39669924 : wide_int tmax = wide_int::from (wmax, prec, sgn);
898 :
899 39669924 : bool covers = false;
900 39669924 : wide_int tem = tmin;
901 39669924 : tmin = tmax + 1;
902 39669924 : if (wi::cmp (tmin, tmax, sgn) < 0)
903 2532776 : covers = true;
904 39669924 : tmax = tem - 1;
905 39669924 : 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 37154402 : if (covers || wi::cmp (tmin, tmax, sgn) > 0)
912 26842770 : r.set_varying (type);
913 : else
914 12827154 : r.set (type, tmin, tmax, VR_ANTI_RANGE);
915 39670582 : }
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 135910356 : 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 135910356 : const signop sgn = TYPE_SIGN (type);
928 135910356 : const unsigned int prec = TYPE_PRECISION (type);
929 214191819 : 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 150409312 : if (prec == 1 && wi::ne_p (wmax, wmin))
934 : {
935 0 : r.set_varying (type);
936 0 : return;
937 : }
938 :
939 135910356 : if (overflow_wraps)
940 : {
941 : // If overflow wraps, truncate the values and adjust the range,
942 : // kind, and bounds appropriately.
943 78281463 : if ((min_ovf != wi::OVF_NONE) == (max_ovf != wi::OVF_NONE))
944 : {
945 55526289 : wide_int tmin = wide_int::from (wmin, prec, sgn);
946 55526289 : 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 55526289 : if (wi::gt_p (tmin, tmax, sgn))
950 532683 : r.set_varying (type);
951 : else
952 : // No overflow or both overflow or underflow. The range
953 : // kind stays normal.
954 54993606 : r.set (type, tmin, tmax);
955 55526289 : return;
956 55526500 : }
957 :
958 22755174 : if ((min_ovf == wi::OVF_UNDERFLOW && max_ovf == wi::OVF_NONE)
959 15805782 : || (max_ovf == wi::OVF_OVERFLOW && min_ovf == wi::OVF_NONE))
960 22755174 : 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 57628893 : if ((min_ovf == wi::OVF_OVERFLOW && max_ovf == wi::OVF_OVERFLOW)
970 57626401 : || (min_ovf == wi::OVF_UNDERFLOW && max_ovf == wi::OVF_UNDERFLOW))
971 : {
972 5047 : r.set_undefined ();
973 5047 : return;
974 : }
975 :
976 : // If overflow does not wrap, saturate to [MIN, MAX].
977 57623846 : wide_int new_lb, new_ub;
978 57623846 : if (min_ovf == wi::OVF_UNDERFLOW)
979 7249299 : new_lb = wi::min_value (prec, sgn);
980 50374745 : else if (min_ovf == wi::OVF_OVERFLOW)
981 0 : new_lb = wi::max_value (prec, sgn);
982 : else
983 50374745 : new_lb = wmin;
984 :
985 57623846 : if (max_ovf == wi::OVF_UNDERFLOW)
986 0 : new_ub = wi::min_value (prec, sgn);
987 57623846 : else if (max_ovf == wi::OVF_OVERFLOW)
988 12030579 : new_ub = wi::max_value (prec, sgn);
989 : else
990 45593507 : new_ub = wmax;
991 :
992 57623846 : r.set (type, new_lb, new_ub);
993 57624426 : }
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 85727741 : create_possibly_reversed_range (irange &r, tree type,
1002 : const wide_int &new_lb, const wide_int &new_ub)
1003 : {
1004 85727741 : signop s = TYPE_SIGN (type);
1005 : // If the bounds are swapped, treat the result as if an overflow occurred.
1006 85727741 : if (wi::gt_p (new_lb, new_ub, s))
1007 16914750 : value_range_from_overflowed_bounds (r, type, new_lb, new_ub);
1008 : else
1009 : // Otherwise it's just a normal range.
1010 68812991 : r.set (type, new_lb, new_ub);
1011 85727741 : }
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 83550751 : get_bool_state (vrange &r, const vrange &lhs, tree val_type)
1018 : {
1019 : // If there is no result, then this is unexecutable.
1020 83550751 : if (lhs.undefined_p ())
1021 : {
1022 0 : r.set_undefined ();
1023 0 : return BRS_EMPTY;
1024 : }
1025 :
1026 83550751 : 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 41448484 : if (lhs.contains_p (build_zero_cst (lhs.type ())))
1032 : {
1033 185698 : r.set_varying (val_type);
1034 185698 : 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 5701893 : operator_equal::op1_op2_relation (const irange &lhs, const irange &,
1053 : const irange &) const
1054 : {
1055 5701893 : if (lhs.undefined_p ())
1056 : return VREL_UNDEFINED;
1057 :
1058 : // FALSE = op1 == op2 indicates NE_EXPR.
1059 5701893 : if (lhs.zero_p ())
1060 : return VREL_NE;
1061 :
1062 : // TRUE = op1 == op2 indicates EQ_EXPR.
1063 3151547 : if (!contains_zero_p (lhs))
1064 3131623 : return VREL_EQ;
1065 : return VREL_VARYING;
1066 : }
1067 :
1068 : bool
1069 18059554 : operator_equal::fold_range (irange &r, tree type,
1070 : const irange &op1,
1071 : const irange &op2,
1072 : relation_trio rel) const
1073 : {
1074 18059554 : 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 18018582 : bool op1_const = wi::eq_p (op1.lower_bound (), op1.upper_bound ());
1080 18018582 : bool op2_const = wi::eq_p (op2.lower_bound (), op2.upper_bound ());
1081 18018570 : if (op1_const && op2_const)
1082 : {
1083 293096 : if (wi::eq_p (op1.lower_bound (), op2.upper_bound()))
1084 150971 : r = range_true (type);
1085 : else
1086 142125 : 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 17725474 : int_range_max tmp = op1;
1093 17725474 : tmp.intersect (op2);
1094 17725474 : if (tmp.undefined_p ())
1095 244282 : r = range_false (type);
1096 : // Check if a constant cannot satisfy the bitmask requirements.
1097 32644800 : else if (op2_const && !op1.get_bitmask ().member_p (op2.lower_bound ()))
1098 0 : r = range_false (type);
1099 17534742 : else if (op1_const && !op2.get_bitmask ().member_p (op1.lower_bound ()))
1100 0 : r = range_false (type);
1101 : else
1102 17481192 : r = range_true_and_false (type);
1103 17725474 : }
1104 : return true;
1105 : }
1106 :
1107 : bool
1108 11732613 : operator_equal::op1_range (irange &r, tree type,
1109 : const irange &lhs,
1110 : const irange &op2,
1111 : relation_trio) const
1112 : {
1113 11732613 : switch (get_bool_state (r, lhs, type))
1114 : {
1115 3725989 : case BRS_TRUE:
1116 : // If it's true, the result is the same as OP2.
1117 3725989 : r = op2;
1118 3725989 : break;
1119 :
1120 7981511 : case BRS_FALSE:
1121 : // If the result is false, the only time we know anything is
1122 : // if OP2 is a constant.
1123 7981511 : if (!op2.undefined_p ()
1124 23944533 : && wi::eq_p (op2.lower_bound(), op2.upper_bound()))
1125 : {
1126 6464894 : r = op2;
1127 6464894 : r.invert ();
1128 : }
1129 : else
1130 1516617 : r.set_varying (type);
1131 : break;
1132 :
1133 : default:
1134 : break;
1135 : }
1136 11732613 : return true;
1137 : }
1138 :
1139 : bool
1140 1454878 : operator_equal::op2_range (irange &r, tree type,
1141 : const irange &lhs,
1142 : const irange &op1,
1143 : relation_trio rel) const
1144 : {
1145 1454878 : return operator_equal::op1_range (r, type, lhs, op1, rel.swap_op1_op2 ());
1146 : }
1147 :
1148 : // -------------------------------------------------------------------------
1149 :
1150 : void
1151 0 : operator_not_equal::update_bitmask (irange &r, const irange &lh,
1152 : const irange &rh) const
1153 : {
1154 0 : update_known_bitmask (r, NE_EXPR, lh, rh);
1155 0 : }
1156 :
1157 : // Check if the LHS range indicates a relation between OP1 and OP2.
1158 :
1159 : relation_kind
1160 9792749 : operator_not_equal::op1_op2_relation (const irange &lhs, const irange &,
1161 : const irange &) const
1162 : {
1163 9792749 : if (lhs.undefined_p ())
1164 : return VREL_UNDEFINED;
1165 :
1166 : // FALSE = op1 != op2 indicates EQ_EXPR.
1167 9792749 : if (lhs.zero_p ())
1168 : return VREL_EQ;
1169 :
1170 : // TRUE = op1 != op2 indicates NE_EXPR.
1171 4555200 : if (!contains_zero_p (lhs))
1172 4513947 : return VREL_NE;
1173 : return VREL_VARYING;
1174 : }
1175 :
1176 : bool
1177 26823449 : operator_not_equal::fold_range (irange &r, tree type,
1178 : const irange &op1,
1179 : const irange &op2,
1180 : relation_trio rel) const
1181 : {
1182 26823449 : if (relop_early_resolve (r, type, op1, op2, rel, VREL_NE))
1183 : return true;
1184 :
1185 : // We can be sure the values are always equal or not if both ranges
1186 : // consist of a single value, and then compare them.
1187 26802357 : bool op1_const = wi::eq_p (op1.lower_bound (), op1.upper_bound ());
1188 26802357 : bool op2_const = wi::eq_p (op2.lower_bound (), op2.upper_bound ());
1189 26801975 : if (op1_const && op2_const)
1190 : {
1191 1156493 : if (wi::ne_p (op1.lower_bound (), op2.upper_bound()))
1192 655541 : r = range_true (type);
1193 : else
1194 500950 : r = range_false (type);
1195 : }
1196 : else
1197 : {
1198 : // If ranges do not intersect, we know the range is not equal,
1199 : // otherwise we don't know anything for sure.
1200 25645484 : int_range_max tmp = op1;
1201 25645484 : tmp.intersect (op2);
1202 25645484 : if (tmp.undefined_p ())
1203 295660 : r = range_true (type);
1204 : // Check if a constant cannot satisfy the bitmask requirements.
1205 46307677 : else if (op2_const && !op1.get_bitmask ().member_p (op2.lower_bound ()))
1206 0 : r = range_true (type);
1207 25383953 : else if (op1_const && !op2.get_bitmask ().member_p (op1.lower_bound ()))
1208 0 : r = range_true (type);
1209 : else
1210 25349824 : r = range_true_and_false (type);
1211 25645484 : }
1212 : return true;
1213 : }
1214 :
1215 : bool
1216 20532360 : operator_not_equal::op1_range (irange &r, tree type,
1217 : const irange &lhs,
1218 : const irange &op2,
1219 : relation_trio) const
1220 : {
1221 20532360 : switch (get_bool_state (r, lhs, type))
1222 : {
1223 12319851 : case BRS_TRUE:
1224 : // If the result is true, the only time we know anything is if
1225 : // OP2 is a constant.
1226 12319851 : if (!op2.undefined_p ()
1227 36959553 : && wi::eq_p (op2.lower_bound(), op2.upper_bound()))
1228 : {
1229 9958348 : r = op2;
1230 9958348 : r.invert ();
1231 : }
1232 : else
1233 2361503 : r.set_varying (type);
1234 : break;
1235 :
1236 8188331 : case BRS_FALSE:
1237 : // If it's false, the result is the same as OP2.
1238 8188331 : r = op2;
1239 8188331 : break;
1240 :
1241 : default:
1242 : break;
1243 : }
1244 20532360 : return true;
1245 : }
1246 :
1247 :
1248 : bool
1249 2507897 : operator_not_equal::op2_range (irange &r, tree type,
1250 : const irange &lhs,
1251 : const irange &op1,
1252 : relation_trio rel) const
1253 : {
1254 2507897 : return operator_not_equal::op1_range (r, type, lhs, op1, rel.swap_op1_op2 ());
1255 : }
1256 :
1257 : // (X < VAL) produces the range of [MIN, VAL - 1].
1258 :
1259 : static void
1260 6196443 : build_lt (irange &r, tree type, const wide_int &val)
1261 : {
1262 6196443 : wi::overflow_type ov;
1263 6196443 : wide_int lim;
1264 6196443 : signop sgn = TYPE_SIGN (type);
1265 :
1266 : // Signed 1 bit cannot represent 1 for subtraction.
1267 6196443 : if (sgn == SIGNED)
1268 4179456 : lim = wi::add (val, -1, sgn, &ov);
1269 : else
1270 2017045 : lim = wi::sub (val, 1, sgn, &ov);
1271 :
1272 : // If val - 1 underflows, check if X < MIN, which is an empty range.
1273 6196443 : if (ov)
1274 274 : r.set_undefined ();
1275 : else
1276 6196227 : r = int_range<1> (type, min_limit (type), lim);
1277 6196443 : }
1278 :
1279 : // (X <= VAL) produces the range of [MIN, VAL].
1280 :
1281 : static void
1282 13649936 : build_le (irange &r, tree type, const wide_int &val)
1283 : {
1284 13649936 : r = int_range<1> (type, min_limit (type), val);
1285 13649936 : }
1286 :
1287 : // (X > VAL) produces the range of [VAL + 1, MAX].
1288 :
1289 : static void
1290 10394970 : build_gt (irange &r, tree type, const wide_int &val)
1291 : {
1292 10394970 : wi::overflow_type ov;
1293 10394970 : wide_int lim;
1294 10394970 : signop sgn = TYPE_SIGN (type);
1295 :
1296 : // Signed 1 bit cannot represent 1 for addition.
1297 10394970 : if (sgn == SIGNED)
1298 5800255 : lim = wi::sub (val, -1, sgn, &ov);
1299 : else
1300 4594802 : lim = wi::add (val, 1, sgn, &ov);
1301 : // If val + 1 overflows, check is for X > MAX, which is an empty range.
1302 10394970 : if (ov)
1303 0 : r.set_undefined ();
1304 : else
1305 10395057 : r = int_range<1> (type, lim, max_limit (type));
1306 10394970 : }
1307 :
1308 : // (X >= val) produces the range of [VAL, MAX].
1309 :
1310 : static void
1311 7095104 : build_ge (irange &r, tree type, const wide_int &val)
1312 : {
1313 7095104 : r = int_range<1> (type, val, max_limit (type));
1314 7095104 : }
1315 :
1316 :
1317 : void
1318 0 : operator_lt::update_bitmask (irange &r, const irange &lh,
1319 : const irange &rh) const
1320 : {
1321 0 : update_known_bitmask (r, LT_EXPR, lh, rh);
1322 0 : }
1323 :
1324 : // Check if the LHS range indicates a relation between OP1 and OP2.
1325 :
1326 : relation_kind
1327 11765910 : operator_lt::op1_op2_relation (const irange &lhs, const irange &,
1328 : const irange &) const
1329 : {
1330 11765910 : if (lhs.undefined_p ())
1331 : return VREL_UNDEFINED;
1332 :
1333 : // FALSE = op1 < op2 indicates GE_EXPR.
1334 11765910 : if (lhs.zero_p ())
1335 : return VREL_GE;
1336 :
1337 : // TRUE = op1 < op2 indicates LT_EXPR.
1338 5896496 : if (!contains_zero_p (lhs))
1339 5888355 : return VREL_LT;
1340 : return VREL_VARYING;
1341 : }
1342 :
1343 : bool
1344 6591635 : operator_lt::fold_range (irange &r, tree type,
1345 : const irange &op1,
1346 : const irange &op2,
1347 : relation_trio rel) const
1348 : {
1349 6591635 : if (relop_early_resolve (r, type, op1, op2, rel, VREL_LT))
1350 : return true;
1351 :
1352 6567338 : signop sign = TYPE_SIGN (op1.type ());
1353 6567338 : gcc_checking_assert (sign == TYPE_SIGN (op2.type ()));
1354 :
1355 6567374 : if (wi::lt_p (op1.upper_bound (), op2.lower_bound (), sign))
1356 21822 : r = range_true (type);
1357 6545552 : else if (!wi::lt_p (op1.lower_bound (), op2.upper_bound (), sign))
1358 58731 : r = range_false (type);
1359 : // Use nonzero bits to determine if < 0 is false.
1360 8550213 : else if (op2.zero_p () && !wi::neg_p (op1.get_nonzero_bits (), sign))
1361 0 : r = range_false (type);
1362 : else
1363 6486785 : r = range_true_and_false (type);
1364 : return true;
1365 : }
1366 :
1367 : bool
1368 5520957 : operator_lt::op1_range (irange &r, tree type,
1369 : const irange &lhs,
1370 : const irange &op2,
1371 : relation_trio) const
1372 : {
1373 5520957 : if (op2.undefined_p ())
1374 : return false;
1375 :
1376 5520957 : switch (get_bool_state (r, lhs, type))
1377 : {
1378 2348730 : case BRS_TRUE:
1379 2348730 : build_lt (r, type, op2.upper_bound ());
1380 2348730 : break;
1381 :
1382 3167656 : case BRS_FALSE:
1383 3167656 : build_ge (r, type, op2.lower_bound ());
1384 3167656 : break;
1385 :
1386 : default:
1387 : break;
1388 : }
1389 : return true;
1390 : }
1391 :
1392 : bool
1393 3829613 : operator_lt::op2_range (irange &r, tree type,
1394 : const irange &lhs,
1395 : const irange &op1,
1396 : relation_trio) const
1397 : {
1398 3829613 : if (op1.undefined_p ())
1399 : return false;
1400 :
1401 3829611 : switch (get_bool_state (r, lhs, type))
1402 : {
1403 1619277 : case BRS_TRUE:
1404 1619277 : build_gt (r, type, op1.lower_bound ());
1405 1619277 : break;
1406 :
1407 2206773 : case BRS_FALSE:
1408 2206773 : build_le (r, type, op1.upper_bound ());
1409 2206773 : break;
1410 :
1411 : default:
1412 : break;
1413 : }
1414 : return true;
1415 : }
1416 :
1417 :
1418 : void
1419 0 : operator_le::update_bitmask (irange &r, const irange &lh,
1420 : const irange &rh) const
1421 : {
1422 0 : update_known_bitmask (r, LE_EXPR, lh, rh);
1423 0 : }
1424 :
1425 : // Check if the LHS range indicates a relation between OP1 and OP2.
1426 :
1427 : relation_kind
1428 4218628 : operator_le::op1_op2_relation (const irange &lhs, const irange &,
1429 : const irange &) const
1430 : {
1431 4218628 : if (lhs.undefined_p ())
1432 : return VREL_UNDEFINED;
1433 :
1434 : // FALSE = op1 <= op2 indicates GT_EXPR.
1435 4218628 : if (lhs.zero_p ())
1436 : return VREL_GT;
1437 :
1438 : // TRUE = op1 <= op2 indicates LE_EXPR.
1439 2373905 : if (!contains_zero_p (lhs))
1440 2363418 : return VREL_LE;
1441 : return VREL_VARYING;
1442 : }
1443 :
1444 : bool
1445 5257727 : operator_le::fold_range (irange &r, tree type,
1446 : const irange &op1,
1447 : const irange &op2,
1448 : relation_trio rel) const
1449 : {
1450 5257727 : if (relop_early_resolve (r, type, op1, op2, rel, VREL_LE))
1451 : return true;
1452 :
1453 5245290 : signop sign = TYPE_SIGN (op1.type ());
1454 5245290 : gcc_checking_assert (sign == TYPE_SIGN (op2.type ()));
1455 :
1456 5245294 : if (wi::le_p (op1.upper_bound (), op2.lower_bound (), sign))
1457 136937 : r = range_true (type);
1458 5108357 : else if (!wi::le_p (op1.lower_bound (), op2.upper_bound (), sign))
1459 53771 : r = range_false (type);
1460 : else
1461 5054582 : r = range_true_and_false (type);
1462 : return true;
1463 : }
1464 :
1465 : bool
1466 6415543 : operator_le::op1_range (irange &r, tree type,
1467 : const irange &lhs,
1468 : const irange &op2,
1469 : relation_trio) const
1470 : {
1471 6415543 : if (op2.undefined_p ())
1472 : return false;
1473 :
1474 6415543 : switch (get_bool_state (r, lhs, type))
1475 : {
1476 3224912 : case BRS_TRUE:
1477 3224912 : build_le (r, type, op2.upper_bound ());
1478 3224912 : break;
1479 :
1480 3178015 : case BRS_FALSE:
1481 3178015 : build_gt (r, type, op2.lower_bound ());
1482 3178015 : break;
1483 :
1484 : default:
1485 : break;
1486 : }
1487 : return true;
1488 : }
1489 :
1490 : bool
1491 1071787 : operator_le::op2_range (irange &r, tree type,
1492 : const irange &lhs,
1493 : const irange &op1,
1494 : relation_trio) const
1495 : {
1496 1071787 : if (op1.undefined_p ())
1497 : return false;
1498 :
1499 1071787 : switch (get_bool_state (r, lhs, type))
1500 : {
1501 476530 : case BRS_TRUE:
1502 476530 : build_ge (r, type, op1.lower_bound ());
1503 476530 : break;
1504 :
1505 591382 : case BRS_FALSE:
1506 591382 : build_lt (r, type, op1.upper_bound ());
1507 591382 : break;
1508 :
1509 : default:
1510 : break;
1511 : }
1512 : return true;
1513 : }
1514 :
1515 :
1516 : void
1517 0 : operator_gt::update_bitmask (irange &r, const irange &lh,
1518 : const irange &rh) const
1519 : {
1520 0 : update_known_bitmask (r, GT_EXPR, lh, rh);
1521 0 : }
1522 :
1523 : // Check if the LHS range indicates a relation between OP1 and OP2.
1524 :
1525 : relation_kind
1526 11576525 : operator_gt::op1_op2_relation (const irange &lhs, const irange &,
1527 : const irange &) const
1528 : {
1529 11576525 : if (lhs.undefined_p ())
1530 : return VREL_UNDEFINED;
1531 :
1532 : // FALSE = op1 > op2 indicates LE_EXPR.
1533 11576525 : if (lhs.zero_p ())
1534 : return VREL_LE;
1535 :
1536 : // TRUE = op1 > op2 indicates GT_EXPR.
1537 6122720 : if (!contains_zero_p (lhs))
1538 6107243 : return VREL_GT;
1539 : return VREL_VARYING;
1540 : }
1541 :
1542 : bool
1543 11650107 : operator_gt::fold_range (irange &r, tree type,
1544 : const irange &op1, const irange &op2,
1545 : relation_trio rel) const
1546 : {
1547 11650107 : if (relop_early_resolve (r, type, op1, op2, rel, VREL_GT))
1548 : return true;
1549 :
1550 11599836 : signop sign = TYPE_SIGN (op1.type ());
1551 11599836 : gcc_checking_assert (sign == TYPE_SIGN (op2.type ()));
1552 :
1553 11599862 : if (wi::gt_p (op1.lower_bound (), op2.upper_bound (), sign))
1554 106364 : r = range_true (type);
1555 11493498 : else if (!wi::gt_p (op1.upper_bound (), op2.lower_bound (), sign))
1556 369731 : r = range_false (type);
1557 : else
1558 11123741 : r = range_true_and_false (type);
1559 : return true;
1560 : }
1561 :
1562 : bool
1563 12535212 : operator_gt::op1_range (irange &r, tree type,
1564 : const irange &lhs, const irange &op2,
1565 : relation_trio) const
1566 : {
1567 12535212 : if (op2.undefined_p ())
1568 : return false;
1569 :
1570 12535212 : switch (get_bool_state (r, lhs, type))
1571 : {
1572 5080135 : case BRS_TRUE:
1573 5080135 : build_gt (r, type, op2.lower_bound ());
1574 5080135 : break;
1575 :
1576 7445812 : case BRS_FALSE:
1577 7445812 : build_le (r, type, op2.upper_bound ());
1578 7445812 : break;
1579 :
1580 : default:
1581 : break;
1582 : }
1583 : return true;
1584 : }
1585 :
1586 : bool
1587 3567848 : operator_gt::op2_range (irange &r, tree type,
1588 : const irange &lhs,
1589 : const irange &op1,
1590 : relation_trio) const
1591 : {
1592 3567848 : if (op1.undefined_p ())
1593 : return false;
1594 :
1595 3567848 : switch (get_bool_state (r, lhs, type))
1596 : {
1597 2113987 : case BRS_TRUE:
1598 2113987 : build_lt (r, type, op1.upper_bound ());
1599 2113987 : break;
1600 :
1601 1445327 : case BRS_FALSE:
1602 1445327 : build_ge (r, type, op1.lower_bound ());
1603 1445327 : break;
1604 :
1605 : default:
1606 : break;
1607 : }
1608 : return true;
1609 : }
1610 :
1611 :
1612 : void
1613 0 : operator_ge::update_bitmask (irange &r, const irange &lh,
1614 : const irange &rh) const
1615 : {
1616 0 : update_known_bitmask (r, GE_EXPR, lh, rh);
1617 0 : }
1618 :
1619 : // Check if the LHS range indicates a relation between OP1 and OP2.
1620 :
1621 : relation_kind
1622 3801893 : operator_ge::op1_op2_relation (const irange &lhs, const irange &,
1623 : const irange &) const
1624 : {
1625 3801893 : if (lhs.undefined_p ())
1626 : return VREL_UNDEFINED;
1627 :
1628 : // FALSE = op1 >= op2 indicates LT_EXPR.
1629 3801893 : if (lhs.zero_p ())
1630 : return VREL_LT;
1631 :
1632 : // TRUE = op1 >= op2 indicates GE_EXPR.
1633 2037652 : if (!contains_zero_p (lhs))
1634 2030255 : return VREL_GE;
1635 : return VREL_VARYING;
1636 : }
1637 :
1638 : bool
1639 2651065 : operator_ge::fold_range (irange &r, tree type,
1640 : const irange &op1,
1641 : const irange &op2,
1642 : relation_trio rel) const
1643 : {
1644 2651065 : if (relop_early_resolve (r, type, op1, op2, rel, VREL_GE))
1645 : return true;
1646 :
1647 2639075 : signop sign = TYPE_SIGN (op1.type ());
1648 2639075 : gcc_checking_assert (sign == TYPE_SIGN (op2.type ()));
1649 :
1650 2639107 : if (wi::ge_p (op1.lower_bound (), op2.upper_bound (), sign))
1651 173946 : r = range_true (type);
1652 2465161 : else if (!wi::ge_p (op1.upper_bound (), op2.lower_bound (), sign))
1653 5849 : r = range_false (type);
1654 : else
1655 2459280 : r = range_true_and_false (type);
1656 : return true;
1657 : }
1658 :
1659 : bool
1660 3154972 : operator_ge::op1_range (irange &r, tree type,
1661 : const irange &lhs,
1662 : const irange &op2,
1663 : relation_trio) const
1664 : {
1665 3154972 : if (op2.undefined_p ())
1666 : return false;
1667 :
1668 3154972 : switch (get_bool_state (r, lhs, type))
1669 : {
1670 2005591 : case BRS_TRUE:
1671 2005591 : build_ge (r, type, op2.lower_bound ());
1672 2005591 : break;
1673 :
1674 1142344 : case BRS_FALSE:
1675 1142344 : build_lt (r, type, op2.upper_bound ());
1676 1142344 : break;
1677 :
1678 : default:
1679 : break;
1680 : }
1681 : return true;
1682 : }
1683 :
1684 : bool
1685 1292804 : operator_ge::op2_range (irange &r, tree type,
1686 : const irange &lhs,
1687 : const irange &op1,
1688 : relation_trio) const
1689 : {
1690 1292804 : if (op1.undefined_p ())
1691 : return false;
1692 :
1693 1292804 : switch (get_bool_state (r, lhs, type))
1694 : {
1695 772439 : case BRS_TRUE:
1696 772439 : build_le (r, type, op1.upper_bound ());
1697 772439 : break;
1698 :
1699 517543 : case BRS_FALSE:
1700 517543 : build_gt (r, type, op1.lower_bound ());
1701 517543 : break;
1702 :
1703 : default:
1704 : break;
1705 : }
1706 : return true;
1707 : }
1708 :
1709 :
1710 : void
1711 47128999 : operator_plus::update_bitmask (irange &r, const irange &lh,
1712 : const irange &rh) const
1713 : {
1714 47128999 : update_known_bitmask (r, PLUS_EXPR, lh, rh);
1715 47128999 : }
1716 :
1717 : // Check to see if the range of OP2 indicates anything about the relation
1718 : // between LHS and OP1.
1719 :
1720 : relation_kind
1721 43642117 : operator_plus::lhs_op1_relation (const irange &lhs,
1722 : const irange &op1,
1723 : const irange &op2,
1724 : relation_kind) const
1725 : {
1726 43642117 : if (lhs.undefined_p () || op1.undefined_p () || op2.undefined_p ())
1727 : return VREL_VARYING;
1728 :
1729 43614549 : tree type = lhs.type ();
1730 43614549 : unsigned prec = TYPE_PRECISION (type);
1731 43614549 : wi::overflow_type ovf1, ovf2;
1732 43614549 : signop sign = TYPE_SIGN (type);
1733 :
1734 : // LHS = OP1 + 0 indicates LHS == OP1.
1735 43614549 : if (op2.zero_p ())
1736 : return VREL_EQ;
1737 :
1738 43446261 : if (TYPE_OVERFLOW_WRAPS (type))
1739 : {
1740 24678640 : wi::add (op1.lower_bound (), op2.lower_bound (), sign, &ovf1);
1741 24678858 : wi::add (op1.upper_bound (), op2.upper_bound (), sign, &ovf2);
1742 : }
1743 : else
1744 18768057 : ovf1 = ovf2 = wi::OVF_NONE;
1745 :
1746 : // Never wrapping additions.
1747 43446261 : if (!ovf1 && !ovf2)
1748 : {
1749 : // Positive op2 means lhs > op1.
1750 26055154 : if (wi::gt_p (op2.lower_bound (), wi::zero (prec), sign))
1751 : return VREL_GT;
1752 10420217 : if (wi::ge_p (op2.lower_bound (), wi::zero (prec), sign))
1753 : return VREL_GE;
1754 :
1755 : // Negative op2 means lhs < op1.
1756 8390454 : if (wi::lt_p (op2.upper_bound (), wi::zero (prec), sign))
1757 : return VREL_LT;
1758 5182028 : if (wi::le_p (op2.upper_bound (), wi::zero (prec), sign))
1759 : return VREL_LE;
1760 : }
1761 : // Always wrapping additions.
1762 17391458 : else if (ovf1 && ovf1 == ovf2)
1763 : {
1764 : // Positive op2 means lhs < op1.
1765 693000 : if (wi::gt_p (op2.lower_bound (), wi::zero (prec), sign))
1766 : return VREL_LT;
1767 21 : if (wi::ge_p (op2.lower_bound (), wi::zero (prec), sign))
1768 : return VREL_LE;
1769 :
1770 : // Negative op2 means lhs > op1.
1771 21 : if (wi::lt_p (op2.upper_bound (), wi::zero (prec), sign))
1772 : return VREL_GT;
1773 0 : if (wi::le_p (op2.upper_bound (), wi::zero (prec), sign))
1774 : return VREL_GE;
1775 : }
1776 :
1777 : // If op2 does not contain 0, then LHS and OP1 can never be equal.
1778 21867356 : if (!range_includes_zero_p (op2))
1779 : return VREL_NE;
1780 :
1781 : return VREL_VARYING;
1782 : }
1783 :
1784 : // PLUS is symmetrical, so we can simply call lhs_op1_relation with reversed
1785 : // operands.
1786 :
1787 : relation_kind
1788 7992889 : operator_plus::lhs_op2_relation (const irange &lhs, const irange &op1,
1789 : const irange &op2, relation_kind rel) const
1790 : {
1791 7992889 : return lhs_op1_relation (lhs, op2, op1, rel);
1792 : }
1793 :
1794 : void
1795 70222054 : operator_plus::wi_fold (irange &r, tree type,
1796 : const wide_int &lh_lb, const wide_int &lh_ub,
1797 : const wide_int &rh_lb, const wide_int &rh_ub) const
1798 : {
1799 70222054 : wi::overflow_type ov_lb, ov_ub;
1800 70222054 : signop s = TYPE_SIGN (type);
1801 70222054 : wide_int new_lb = wi::add (lh_lb, rh_lb, s, &ov_lb);
1802 70222054 : wide_int new_ub = wi::add (lh_ub, rh_ub, s, &ov_ub);
1803 70222054 : value_range_with_overflow (r, type, new_lb, new_ub, ov_lb, ov_ub);
1804 70222054 : }
1805 :
1806 : // Given addition or subtraction, determine the possible NORMAL ranges and
1807 : // OVERFLOW ranges given an OFFSET range. ADD_P is true for addition.
1808 : // Return the relation that exists between the LHS and OP1 in order for the
1809 : // NORMAL range to apply.
1810 : // a return value of VREL_VARYING means no ranges were applicable.
1811 :
1812 : static relation_kind
1813 755052 : plus_minus_ranges (irange &r_ov, irange &r_normal, const irange &offset,
1814 : bool add_p)
1815 : {
1816 755052 : relation_kind kind = VREL_VARYING;
1817 : // For now, only deal with constant adds. This could be extended to ranges
1818 : // when someone is so motivated.
1819 755052 : if (!offset.singleton_p () || offset.zero_p ())
1820 740351 : return kind;
1821 :
1822 : // Always work with a positive offset. ie a+ -2 -> a-2 and a- -2 > a+2
1823 14701 : wide_int off = offset.lower_bound ();
1824 14701 : if (wi::neg_p (off, SIGNED))
1825 : {
1826 1215 : add_p = !add_p;
1827 1215 : off = wi::neg (off);
1828 : }
1829 :
1830 14701 : wi::overflow_type ov;
1831 14701 : tree type = offset.type ();
1832 14701 : unsigned prec = TYPE_PRECISION (type);
1833 14701 : wide_int ub;
1834 14701 : wide_int lb;
1835 : // calculate the normal range and relation for the operation.
1836 14701 : if (add_p)
1837 : {
1838 : // [ 0 , INF - OFF]
1839 13486 : lb = wi::zero (prec);
1840 13486 : ub = wi::sub (irange_val_max (type), off, UNSIGNED, &ov);
1841 13486 : kind = VREL_GT;
1842 : }
1843 : else
1844 : {
1845 : // [ OFF, INF ]
1846 1215 : lb = off;
1847 1215 : ub = irange_val_max (type);
1848 1215 : kind = VREL_LT;
1849 : }
1850 14701 : int_range<2> normal_range (type, lb, ub);
1851 14701 : int_range<2> ov_range (type, lb, ub, VR_ANTI_RANGE);
1852 :
1853 14701 : r_ov = ov_range;
1854 14701 : r_normal = normal_range;
1855 14701 : return kind;
1856 14701 : }
1857 :
1858 : // Once op1 has been calculated by operator_plus or operator_minus, check
1859 : // to see if the relation passed causes any part of the calculation to
1860 : // be not possible. ie
1861 : // a_2 = b_3 + 1 with a_2 < b_3 can refine the range of b_3 to [INF, INF]
1862 : // and that further refines a_2 to [0, 0].
1863 : // R is the value of op1, OP2 is the offset being added/subtracted, REL is the
1864 : // relation between LHS relation OP1 and ADD_P is true for PLUS, false for
1865 : // MINUS. IF any adjustment can be made, R will reflect it.
1866 :
1867 : static void
1868 9968511 : adjust_op1_for_overflow (irange &r, const irange &op2, relation_kind rel,
1869 : bool add_p)
1870 : {
1871 9968511 : if (r.undefined_p ())
1872 : return;
1873 9968509 : tree type = r.type ();
1874 : // Check for unsigned overflow and calculate the overflow part.
1875 9968509 : signop s = TYPE_SIGN (type);
1876 9968509 : if (!TYPE_OVERFLOW_WRAPS (type) || s == SIGNED)
1877 : return;
1878 :
1879 : // Only work with <, <=, >, >= relations.
1880 4994321 : if (!relation_lt_le_gt_ge_p (rel))
1881 : return;
1882 :
1883 : // Get the ranges for this offset.
1884 755052 : int_range_max normal, overflow;
1885 755052 : relation_kind k = plus_minus_ranges (overflow, normal, op2, add_p);
1886 :
1887 : // VREL_VARYING means there are no adjustments.
1888 755052 : if (k == VREL_VARYING)
1889 : return;
1890 :
1891 : // If the relations match use the normal range, otherwise use overflow range.
1892 14701 : if (relation_intersect (k, rel) == k)
1893 10618 : r.intersect (normal);
1894 : else
1895 4083 : r.intersect (overflow);
1896 : return;
1897 755052 : }
1898 :
1899 : bool
1900 8976357 : operator_plus::op1_range (irange &r, tree type,
1901 : const irange &lhs,
1902 : const irange &op2,
1903 : relation_trio trio) const
1904 : {
1905 8976357 : if (lhs.undefined_p ())
1906 : return false;
1907 : // Start with the default operation.
1908 8976357 : range_op_handler minus (MINUS_EXPR);
1909 8976357 : if (!minus)
1910 : return false;
1911 8976357 : bool res = minus.fold_range (r, type, lhs, op2);
1912 8976357 : relation_kind rel = trio.lhs_op1 ();
1913 : // Check for a relation refinement.
1914 8976357 : if (res)
1915 8976357 : adjust_op1_for_overflow (r, op2, rel, true /* PLUS_EXPR */);
1916 : return res;
1917 : }
1918 :
1919 : bool
1920 2067355 : operator_plus::op2_range (irange &r, tree type,
1921 : const irange &lhs,
1922 : const irange &op1,
1923 : relation_trio rel) const
1924 : {
1925 2067355 : return op1_range (r, type, lhs, op1, rel.swap_op1_op2 ());
1926 : }
1927 :
1928 : class operator_widen_plus_signed : public range_operator
1929 : {
1930 : public:
1931 : virtual void wi_fold (irange &r, tree type,
1932 : const wide_int &lh_lb,
1933 : const wide_int &lh_ub,
1934 : const wide_int &rh_lb,
1935 : const wide_int &rh_ub) const;
1936 : } op_widen_plus_signed;
1937 :
1938 : void
1939 0 : operator_widen_plus_signed::wi_fold (irange &r, tree type,
1940 : const wide_int &lh_lb,
1941 : const wide_int &lh_ub,
1942 : const wide_int &rh_lb,
1943 : const wide_int &rh_ub) const
1944 : {
1945 0 : wi::overflow_type ov_lb, ov_ub;
1946 0 : signop s = TYPE_SIGN (type);
1947 :
1948 0 : wide_int lh_wlb
1949 0 : = wide_int::from (lh_lb, wi::get_precision (lh_lb) * 2, SIGNED);
1950 0 : wide_int lh_wub
1951 0 : = wide_int::from (lh_ub, wi::get_precision (lh_ub) * 2, SIGNED);
1952 0 : wide_int rh_wlb = wide_int::from (rh_lb, wi::get_precision (rh_lb) * 2, s);
1953 0 : wide_int rh_wub = wide_int::from (rh_ub, wi::get_precision (rh_ub) * 2, s);
1954 :
1955 0 : wide_int new_lb = wi::add (lh_wlb, rh_wlb, s, &ov_lb);
1956 0 : wide_int new_ub = wi::add (lh_wub, rh_wub, s, &ov_ub);
1957 :
1958 0 : r = int_range<2> (type, new_lb, new_ub);
1959 0 : }
1960 :
1961 : class operator_widen_plus_unsigned : public range_operator
1962 : {
1963 : public:
1964 : virtual void wi_fold (irange &r, tree type,
1965 : const wide_int &lh_lb,
1966 : const wide_int &lh_ub,
1967 : const wide_int &rh_lb,
1968 : const wide_int &rh_ub) const;
1969 : } op_widen_plus_unsigned;
1970 :
1971 : void
1972 0 : operator_widen_plus_unsigned::wi_fold (irange &r, tree type,
1973 : const wide_int &lh_lb,
1974 : const wide_int &lh_ub,
1975 : const wide_int &rh_lb,
1976 : const wide_int &rh_ub) const
1977 : {
1978 0 : wi::overflow_type ov_lb, ov_ub;
1979 0 : signop s = TYPE_SIGN (type);
1980 :
1981 0 : wide_int lh_wlb
1982 0 : = wide_int::from (lh_lb, wi::get_precision (lh_lb) * 2, UNSIGNED);
1983 0 : wide_int lh_wub
1984 0 : = wide_int::from (lh_ub, wi::get_precision (lh_ub) * 2, UNSIGNED);
1985 0 : wide_int rh_wlb = wide_int::from (rh_lb, wi::get_precision (rh_lb) * 2, s);
1986 0 : wide_int rh_wub = wide_int::from (rh_ub, wi::get_precision (rh_ub) * 2, s);
1987 :
1988 0 : wide_int new_lb = wi::add (lh_wlb, rh_wlb, s, &ov_lb);
1989 0 : wide_int new_ub = wi::add (lh_wub, rh_wub, s, &ov_ub);
1990 :
1991 0 : r = int_range<2> (type, new_lb, new_ub);
1992 0 : }
1993 :
1994 : void
1995 17844554 : operator_minus::update_bitmask (irange &r, const irange &lh,
1996 : const irange &rh) const
1997 : {
1998 17844554 : update_known_bitmask (r, MINUS_EXPR, lh, rh);
1999 17844554 : }
2000 :
2001 : void
2002 25033793 : operator_minus::wi_fold (irange &r, tree type,
2003 : const wide_int &lh_lb, const wide_int &lh_ub,
2004 : const wide_int &rh_lb, const wide_int &rh_ub) const
2005 : {
2006 25033793 : wi::overflow_type ov_lb, ov_ub;
2007 25033793 : signop s = TYPE_SIGN (type);
2008 25033793 : wide_int new_lb = wi::sub (lh_lb, rh_ub, s, &ov_lb);
2009 25033793 : wide_int new_ub = wi::sub (lh_ub, rh_lb, s, &ov_ub);
2010 25033793 : value_range_with_overflow (r, type, new_lb, new_ub, ov_lb, ov_ub);
2011 25033793 : }
2012 :
2013 :
2014 : // Return the relation between LHS and OP1 based on the relation between
2015 : // OP1 and OP2.
2016 :
2017 : relation_kind
2018 4678971 : operator_minus::lhs_op1_relation (const irange &, const irange &op1,
2019 : const irange &, relation_kind rel) const
2020 : {
2021 4678971 : if (!op1.undefined_p () && TYPE_SIGN (op1.type ()) == UNSIGNED)
2022 2207339 : switch (rel)
2023 : {
2024 : case VREL_GT:
2025 : case VREL_GE:
2026 : return VREL_LE;
2027 : default:
2028 : break;
2029 : }
2030 : return VREL_VARYING;
2031 : }
2032 :
2033 : // Check to see if the relation REL between OP1 and OP2 has any effect on the
2034 : // LHS of the expression. If so, apply it to LHS_RANGE. This is a helper
2035 : // function for both MINUS_EXPR and POINTER_DIFF_EXPR.
2036 :
2037 : bool
2038 20572483 : minus_op1_op2_relation_effect (irange &lhs_range, tree type,
2039 : const irange &op1_range ATTRIBUTE_UNUSED,
2040 : const irange &op2_range ATTRIBUTE_UNUSED,
2041 : relation_kind rel)
2042 : {
2043 20572483 : if (rel == VREL_VARYING)
2044 : return false;
2045 :
2046 275521 : int_range<2> rel_range;
2047 275521 : unsigned prec = TYPE_PRECISION (type);
2048 275521 : signop sgn = TYPE_SIGN (type);
2049 :
2050 : // == and != produce [0,0] and ~[0,0] regardless of wrapping.
2051 275521 : if (rel == VREL_EQ)
2052 8904 : rel_range = int_range<2> (type, wi::zero (prec), wi::zero (prec));
2053 266617 : else if (rel == VREL_NE)
2054 106174 : rel_range = int_range<2> (type, wi::zero (prec), wi::zero (prec),
2055 53087 : VR_ANTI_RANGE);
2056 213530 : else if (TYPE_OVERFLOW_WRAPS (type))
2057 : {
2058 120796 : switch (rel)
2059 : {
2060 : // For wrapping signed values and unsigned, if op1 > op2 or
2061 : // op1 < op2, then op1 - op2 can be restricted to ~[0, 0].
2062 43289 : case VREL_GT:
2063 43289 : case VREL_LT:
2064 86578 : rel_range = int_range<2> (type, wi::zero (prec), wi::zero (prec),
2065 43289 : VR_ANTI_RANGE);
2066 43289 : break;
2067 : default:
2068 : return false;
2069 : }
2070 : }
2071 : else
2072 : {
2073 92734 : switch (rel)
2074 : {
2075 : // op1 > op2, op1 - op2 can be restricted to [1, +INF]
2076 23073 : case VREL_GT:
2077 46146 : rel_range = int_range<2> (type, wi::one (prec),
2078 46146 : wi::max_value (prec, sgn));
2079 23073 : break;
2080 : // op1 >= op2, op1 - op2 can be restricted to [0, +INF]
2081 68851 : case VREL_GE:
2082 137702 : rel_range = int_range<2> (type, wi::zero (prec),
2083 137702 : wi::max_value (prec, sgn));
2084 68851 : break;
2085 : // op1 < op2, op1 - op2 can be restricted to [-INF, -1]
2086 372 : case VREL_LT:
2087 744 : rel_range = int_range<2> (type, wi::min_value (prec, sgn),
2088 372 : wi::minus_one (prec));
2089 372 : break;
2090 : // op1 <= op2, op1 - op2 can be restricted to [-INF, 0]
2091 284 : case VREL_LE:
2092 568 : rel_range = int_range<2> (type, wi::min_value (prec, sgn),
2093 284 : wi::zero (prec));
2094 284 : break;
2095 : default:
2096 : return false;
2097 : }
2098 : }
2099 197860 : lhs_range.intersect (rel_range);
2100 197860 : return true;
2101 275521 : }
2102 :
2103 : bool
2104 17844554 : operator_minus::op1_op2_relation_effect (irange &lhs_range, tree type,
2105 : const irange &op1_range,
2106 : const irange &op2_range,
2107 : relation_kind rel) const
2108 : {
2109 17844554 : return minus_op1_op2_relation_effect (lhs_range, type, op1_range, op2_range,
2110 17844554 : rel);
2111 : }
2112 :
2113 : bool
2114 992154 : operator_minus::op1_range (irange &r, tree type,
2115 : const irange &lhs,
2116 : const irange &op2,
2117 : relation_trio trio) const
2118 : {
2119 992154 : if (lhs.undefined_p ())
2120 : return false;
2121 : // Start with the default operation.
2122 992154 : range_op_handler minus (PLUS_EXPR);
2123 992154 : if (!minus)
2124 : return false;
2125 992154 : bool res = minus.fold_range (r, type, lhs, op2);
2126 992154 : relation_kind rel = trio.lhs_op1 ();
2127 992154 : if (res)
2128 992154 : adjust_op1_for_overflow (r, op2, rel, false /* PLUS_EXPR */);
2129 : return res;
2130 :
2131 : }
2132 :
2133 : bool
2134 1729957 : operator_minus::op2_range (irange &r, tree type,
2135 : const irange &lhs,
2136 : const irange &op1,
2137 : relation_trio) const
2138 : {
2139 1729957 : if (lhs.undefined_p ())
2140 : return false;
2141 1729957 : return fold_range (r, type, op1, lhs);
2142 : }
2143 :
2144 : void
2145 930777 : operator_min::update_bitmask (irange &r, const irange &lh,
2146 : const irange &rh) const
2147 : {
2148 930777 : update_known_bitmask (r, MIN_EXPR, lh, rh);
2149 930777 : }
2150 :
2151 : void
2152 1437815 : operator_min::wi_fold (irange &r, tree type,
2153 : const wide_int &lh_lb, const wide_int &lh_ub,
2154 : const wide_int &rh_lb, const wide_int &rh_ub) const
2155 : {
2156 1437815 : signop s = TYPE_SIGN (type);
2157 1437815 : wide_int new_lb = wi::min (lh_lb, rh_lb, s);
2158 1437815 : wide_int new_ub = wi::min (lh_ub, rh_ub, s);
2159 1437815 : value_range_with_overflow (r, type, new_lb, new_ub);
2160 1437815 : }
2161 :
2162 :
2163 : void
2164 838675 : operator_max::update_bitmask (irange &r, const irange &lh,
2165 : const irange &rh) const
2166 : {
2167 838675 : update_known_bitmask (r, MAX_EXPR, lh, rh);
2168 838675 : }
2169 :
2170 : void
2171 1008018 : operator_max::wi_fold (irange &r, tree type,
2172 : const wide_int &lh_lb, const wide_int &lh_ub,
2173 : const wide_int &rh_lb, const wide_int &rh_ub) const
2174 : {
2175 1008018 : signop s = TYPE_SIGN (type);
2176 1008018 : wide_int new_lb = wi::max (lh_lb, rh_lb, s);
2177 1008018 : wide_int new_ub = wi::max (lh_ub, rh_ub, s);
2178 1008018 : value_range_with_overflow (r, type, new_lb, new_ub);
2179 1008018 : }
2180 :
2181 :
2182 : // Calculate the cross product of two sets of ranges and return it.
2183 : //
2184 : // Multiplications, divisions and shifts are a bit tricky to handle,
2185 : // depending on the mix of signs we have in the two ranges, we need to
2186 : // operate on different values to get the minimum and maximum values
2187 : // for the new range. One approach is to figure out all the
2188 : // variations of range combinations and do the operations.
2189 : //
2190 : // However, this involves several calls to compare_values and it is
2191 : // pretty convoluted. It's simpler to do the 4 operations (MIN0 OP
2192 : // MIN1, MIN0 OP MAX1, MAX0 OP MIN1 and MAX0 OP MAX0 OP MAX1) and then
2193 : // figure the smallest and largest values to form the new range.
2194 :
2195 : void
2196 14228952 : cross_product_operator::wi_cross_product (irange &r, tree type,
2197 : const wide_int &lh_lb,
2198 : const wide_int &lh_ub,
2199 : const wide_int &rh_lb,
2200 : const wide_int &rh_ub) const
2201 : {
2202 14228952 : wide_int cp1, cp2, cp3, cp4;
2203 : // Default to varying.
2204 14228952 : r.set_varying (type);
2205 :
2206 : // Compute the 4 cross operations, bailing if we get an overflow we
2207 : // can't handle.
2208 14228952 : if (wi_op_overflows (cp1, type, lh_lb, rh_lb))
2209 : return;
2210 14228914 : if (wi::eq_p (lh_lb, lh_ub))
2211 3870451 : cp3 = cp1;
2212 10358463 : else if (wi_op_overflows (cp3, type, lh_ub, rh_lb))
2213 : return;
2214 14228914 : if (wi::eq_p (rh_lb, rh_ub))
2215 10873427 : cp2 = cp1;
2216 3355487 : else if (wi_op_overflows (cp2, type, lh_lb, rh_ub))
2217 : return;
2218 14226665 : if (wi::eq_p (lh_lb, lh_ub))
2219 3870433 : cp4 = cp2;
2220 10356232 : else if (wi_op_overflows (cp4, type, lh_ub, rh_ub))
2221 : return;
2222 :
2223 : // Order pairs.
2224 14226665 : signop sign = TYPE_SIGN (type);
2225 14226665 : if (wi::gt_p (cp1, cp2, sign))
2226 1517417 : std::swap (cp1, cp2);
2227 14226665 : if (wi::gt_p (cp3, cp4, sign))
2228 1489330 : std::swap (cp3, cp4);
2229 :
2230 : // Choose min and max from the ordered pairs.
2231 14226665 : wide_int res_lb = wi::min (cp1, cp3, sign);
2232 14226665 : wide_int res_ub = wi::max (cp2, cp4, sign);
2233 14226665 : value_range_with_overflow (r, type, res_lb, res_ub);
2234 14230402 : }
2235 :
2236 :
2237 : void
2238 13480352 : operator_mult::update_bitmask (irange &r, const irange &lh,
2239 : const irange &rh) const
2240 : {
2241 13480352 : update_known_bitmask (r, MULT_EXPR, lh, rh);
2242 13480352 : }
2243 :
2244 : bool
2245 1053974 : operator_mult::op1_range (irange &r, tree type,
2246 : const irange &lhs, const irange &op2,
2247 : relation_trio) const
2248 : {
2249 1053974 : if (lhs.undefined_p ())
2250 : return false;
2251 :
2252 : // We can't solve 0 = OP1 * N by dividing by N with a wrapping type.
2253 : // For example: For 0 = OP1 * 2, OP1 could be 0, or MAXINT, whereas
2254 : // for 4 = OP1 * 2, OP1 could be 2 or 130 (unsigned 8-bit)
2255 1053974 : if (TYPE_OVERFLOW_WRAPS (type))
2256 : return false;
2257 :
2258 331570 : wide_int offset;
2259 331570 : if (op2.singleton_p (offset) && offset != 0)
2260 225534 : return range_op_handler (TRUNC_DIV_EXPR).fold_range (r, type, lhs, op2);
2261 :
2262 : // ~[0, 0] = op1 * op2 defines op1 and op2 as non-zero.
2263 106036 : if (!lhs.contains_p (wi::zero (TYPE_PRECISION (lhs.type ()))))
2264 : {
2265 25844 : r.set_nonzero (type);
2266 25844 : return true;
2267 : }
2268 : return false;
2269 331570 : }
2270 :
2271 : bool
2272 121722 : operator_mult::op2_range (irange &r, tree type,
2273 : const irange &lhs, const irange &op1,
2274 : relation_trio rel) const
2275 : {
2276 121722 : return operator_mult::op1_range (r, type, lhs, op1, rel.swap_op1_op2 ());
2277 : }
2278 :
2279 : bool
2280 14330876 : operator_mult::wi_op_overflows (wide_int &res, tree type,
2281 : const wide_int &w0, const wide_int &w1) const
2282 : {
2283 14330876 : wi::overflow_type overflow = wi::OVF_NONE;
2284 14330876 : signop sign = TYPE_SIGN (type);
2285 14330876 : res = wi::mul (w0, w1, sign, &overflow);
2286 14330876 : if (overflow && TYPE_OVERFLOW_UNDEFINED (type))
2287 : {
2288 : // For multiplication, the sign of the overflow is given
2289 : // by the comparison of the signs of the operands.
2290 7019070 : if (sign == UNSIGNED || w0.sign_mask () == w1.sign_mask ())
2291 3897181 : res = wi::max_value (w0.get_precision (), sign);
2292 : else
2293 3122061 : res = wi::min_value (w0.get_precision (), sign);
2294 7019070 : return false;
2295 : }
2296 7311806 : return overflow;
2297 : }
2298 :
2299 : void
2300 17140838 : operator_mult::wi_fold (irange &r, tree type,
2301 : const wide_int &lh_lb, const wide_int &lh_ub,
2302 : const wide_int &rh_lb, const wide_int &rh_ub) const
2303 : {
2304 17140838 : if (TYPE_OVERFLOW_UNDEFINED (type))
2305 : {
2306 5664546 : wi_cross_product (r, type, lh_lb, lh_ub, rh_lb, rh_ub);
2307 5664546 : return;
2308 : }
2309 :
2310 : // Multiply the ranges when overflow wraps. This is basically fancy
2311 : // code so we don't drop to varying with an unsigned
2312 : // [-3,-1]*[-3,-1].
2313 : //
2314 : // This test requires 2*prec bits if both operands are signed and
2315 : // 2*prec + 2 bits if either is not. Therefore, extend the values
2316 : // using the sign of the result to PREC2. From here on out,
2317 : // everything is just signed math no matter what the input types
2318 : // were.
2319 :
2320 11476292 : signop sign = TYPE_SIGN (type);
2321 11476292 : unsigned prec = TYPE_PRECISION (type);
2322 11476292 : widest2_int min0 = widest2_int::from (lh_lb, sign);
2323 11476292 : widest2_int max0 = widest2_int::from (lh_ub, sign);
2324 11476292 : widest2_int min1 = widest2_int::from (rh_lb, sign);
2325 11476292 : widest2_int max1 = widest2_int::from (rh_ub, sign);
2326 11476292 : widest2_int sizem1 = wi::mask <widest2_int> (prec, false);
2327 11476292 : widest2_int size = sizem1 + 1;
2328 :
2329 : // Canonicalize the intervals.
2330 11476292 : if (sign == UNSIGNED)
2331 : {
2332 10850905 : if (wi::ltu_p (size, min0 + max0))
2333 : {
2334 1512271 : min0 -= size;
2335 1512271 : max0 -= size;
2336 : }
2337 10850867 : if (wi::ltu_p (size, min1 + max1))
2338 : {
2339 166543 : min1 -= size;
2340 166543 : max1 -= size;
2341 : }
2342 : }
2343 :
2344 : // Sort the 4 products so that min is in prod0 and max is in
2345 : // prod3.
2346 11476292 : widest2_int prod0 = min0 * min1;
2347 11476292 : widest2_int prod1 = min0 * max1;
2348 11476292 : widest2_int prod2 = max0 * min1;
2349 11476292 : widest2_int prod3 = max0 * max1;
2350 :
2351 : // min0min1 > max0max1
2352 11476292 : if (prod0 > prod3)
2353 194824 : std::swap (prod0, prod3);
2354 :
2355 : // min0max1 > max0min1
2356 11476292 : if (prod1 > prod2)
2357 317838 : std::swap (prod1, prod2);
2358 :
2359 11476292 : if (prod0 > prod1)
2360 78235 : std::swap (prod0, prod1);
2361 :
2362 11476292 : if (prod2 > prod3)
2363 4041 : std::swap (prod2, prod3);
2364 :
2365 : // diff = max - min
2366 11476292 : prod2 = prod3 - prod0;
2367 11476292 : if (wi::geu_p (prod2, sizem1))
2368 : {
2369 : // Multiplying by X, where X is a power of 2 is [0,0][X,+INF].
2370 7819598 : if (TYPE_UNSIGNED (type) && rh_lb == rh_ub
2371 7219469 : && wi::exact_log2 (rh_lb) != -1 && prec > 1)
2372 : {
2373 2714782 : r.set (type, rh_lb, wi::max_value (prec, sign));
2374 2714782 : int_range<2> zero;
2375 2714782 : zero.set_zero (type);
2376 2714782 : r.union_ (zero);
2377 2714782 : }
2378 : else
2379 : // The range covers all values.
2380 1265803 : r.set_varying (type);
2381 : }
2382 : else
2383 : {
2384 7495707 : wide_int new_lb = wide_int::from (prod0, prec, sign);
2385 7495707 : wide_int new_ub = wide_int::from (prod3, prec, sign);
2386 7495707 : create_possibly_reversed_range (r, type, new_lb, new_ub);
2387 7495762 : }
2388 11477013 : }
2389 :
2390 : bool
2391 13480352 : operator_mult::op1_op2_relation_effect (irange &lhs_range, tree type,
2392 : const irange &,
2393 : const irange &,
2394 : relation_kind rel) const
2395 : {
2396 : // a*a is nonnegative without overflow.
2397 : // tree_binary_nonnegative_p handles this in a similar way.
2398 13480352 : if (rel == VREL_EQ
2399 13480352 : && TYPE_OVERFLOW_UNDEFINED (type))
2400 : {
2401 34566 : int_range<2> nonnegative;
2402 34566 : nonnegative.set_nonnegative (type);
2403 34566 : lhs_range.intersect (nonnegative);
2404 34566 : return true;
2405 34566 : }
2406 : return false;
2407 : }
2408 :
2409 : class operator_widen_mult_signed : public range_operator
2410 : {
2411 : public:
2412 : virtual void wi_fold (irange &r, tree type,
2413 : const wide_int &lh_lb,
2414 : const wide_int &lh_ub,
2415 : const wide_int &rh_lb,
2416 : const wide_int &rh_ub)
2417 : const;
2418 : } op_widen_mult_signed;
2419 :
2420 : void
2421 1323 : operator_widen_mult_signed::wi_fold (irange &r, tree type,
2422 : const wide_int &lh_lb,
2423 : const wide_int &lh_ub,
2424 : const wide_int &rh_lb,
2425 : const wide_int &rh_ub) const
2426 : {
2427 1323 : wide_int lh_wlb = wide_int::from (lh_lb, TYPE_PRECISION (type), SIGNED);
2428 1323 : wide_int lh_wub = wide_int::from (lh_ub, TYPE_PRECISION (type), SIGNED);
2429 1323 : wide_int rh_wlb = wide_int::from (rh_lb, TYPE_PRECISION (type), SIGNED);
2430 1323 : wide_int rh_wub = wide_int::from (rh_ub, TYPE_PRECISION (type), SIGNED);
2431 :
2432 : /* We don't expect a widening multiplication to be able to overflow but range
2433 : calculations for multiplications are complicated. After widening the
2434 : operands lets call the base class. */
2435 1323 : return op_mult.wi_fold (r, type, lh_wlb, lh_wub, rh_wlb, rh_wub);
2436 1323 : }
2437 :
2438 : class operator_widen_mult_unsigned : public range_operator
2439 : {
2440 : public:
2441 : virtual void wi_fold (irange &r, tree type,
2442 : const wide_int &lh_lb,
2443 : const wide_int &lh_ub,
2444 : const wide_int &rh_lb,
2445 : const wide_int &rh_ub)
2446 : const;
2447 : } op_widen_mult_unsigned;
2448 :
2449 : void
2450 5416 : operator_widen_mult_unsigned::wi_fold (irange &r, tree type,
2451 : const wide_int &lh_lb,
2452 : const wide_int &lh_ub,
2453 : const wide_int &rh_lb,
2454 : const wide_int &rh_ub) const
2455 : {
2456 5416 : wide_int lh_wlb = wide_int::from (lh_lb, TYPE_PRECISION (type), UNSIGNED);
2457 5416 : wide_int lh_wub = wide_int::from (lh_ub, TYPE_PRECISION (type), UNSIGNED);
2458 5416 : wide_int rh_wlb = wide_int::from (rh_lb, TYPE_PRECISION (type), UNSIGNED);
2459 5416 : wide_int rh_wub = wide_int::from (rh_ub, TYPE_PRECISION (type), UNSIGNED);
2460 :
2461 : /* We don't expect a widening multiplication to be able to overflow but range
2462 : calculations for multiplications are complicated. After widening the
2463 : operands lets call the base class. */
2464 5416 : return op_mult.wi_fold (r, type, lh_wlb, lh_wub, rh_wlb, rh_wub);
2465 5416 : }
2466 :
2467 : class operator_widen_mult_signed_unsigned : public range_operator
2468 : {
2469 : public:
2470 : virtual void wi_fold (irange &r, tree type,
2471 : const wide_int &lh_lb,
2472 : const wide_int &lh_ub,
2473 : const wide_int &rh_lb,
2474 : const wide_int &rh_ub)
2475 : const;
2476 : } op_widen_mult_signed_unsigned;
2477 :
2478 : void
2479 0 : operator_widen_mult_signed_unsigned::wi_fold (irange &r, tree type,
2480 : const wide_int &lh_lb,
2481 : const wide_int &lh_ub,
2482 : const wide_int &rh_lb,
2483 : const wide_int &rh_ub) const
2484 : {
2485 0 : wide_int lh_wlb = wide_int::from (lh_lb, TYPE_PRECISION (type), SIGNED);
2486 0 : wide_int lh_wub = wide_int::from (lh_ub, TYPE_PRECISION (type), SIGNED);
2487 0 : wide_int rh_wlb = wide_int::from (rh_lb, TYPE_PRECISION (type), UNSIGNED);
2488 0 : wide_int rh_wub = wide_int::from (rh_ub, TYPE_PRECISION (type), UNSIGNED);
2489 :
2490 : /* We don't expect a widening multiplication to be able to overflow but range
2491 : calculations for multiplications are complicated. After widening the
2492 : operands lets call the base class. */
2493 0 : return op_mult.wi_fold (r, type, lh_wlb, lh_wub, rh_wlb, rh_wub);
2494 0 : }
2495 :
2496 : class operator_div : public cross_product_operator
2497 : {
2498 : using range_operator::update_bitmask;
2499 : using range_operator::op2_range;
2500 : public:
2501 : operator_div (tree_code div_kind) { m_code = div_kind; }
2502 : bool op2_range (irange &r, tree type, const irange &lhs, const irange &,
2503 : relation_trio) const final override;
2504 : virtual void wi_fold (irange &r, tree type,
2505 : const wide_int &lh_lb,
2506 : const wide_int &lh_ub,
2507 : const wide_int &rh_lb,
2508 : const wide_int &rh_ub) const final override;
2509 : virtual bool wi_op_overflows (wide_int &res, tree type,
2510 : const wide_int &, const wide_int &)
2511 : const final override;
2512 2970629 : void update_bitmask (irange &r, const irange &lh, const irange &rh)
2513 : const final override
2514 2970629 : { update_known_bitmask (r, m_code, lh, rh); }
2515 : protected:
2516 : tree_code m_code;
2517 : };
2518 :
2519 : static const operator_div op_trunc_div (TRUNC_DIV_EXPR);
2520 : static const operator_div op_floor_div (FLOOR_DIV_EXPR);
2521 : static const operator_div op_round_div (ROUND_DIV_EXPR);
2522 : static const operator_div op_ceil_div (CEIL_DIV_EXPR);
2523 :
2524 : // Set OP2 to non-zero if the LHS isn't UNDEFINED.
2525 : bool
2526 35141 : operator_div::op2_range (irange &r, tree type, const irange &lhs,
2527 : const irange &, relation_trio) const
2528 : {
2529 35141 : if (!lhs.undefined_p ())
2530 : {
2531 35141 : r.set_nonzero (type);
2532 35141 : return true;
2533 : }
2534 : return false;
2535 : }
2536 :
2537 : bool
2538 12769136 : operator_div::wi_op_overflows (wide_int &res, tree type,
2539 : const wide_int &w0, const wide_int &w1) const
2540 : {
2541 12769136 : if (w1 == 0)
2542 : return true;
2543 :
2544 12769136 : wi::overflow_type overflow = wi::OVF_NONE;
2545 12769136 : signop sign = TYPE_SIGN (type);
2546 :
2547 12769136 : switch (m_code)
2548 : {
2549 12629930 : case EXACT_DIV_EXPR:
2550 12629930 : case TRUNC_DIV_EXPR:
2551 12629930 : res = wi::div_trunc (w0, w1, sign, &overflow);
2552 12629930 : break;
2553 128052 : case FLOOR_DIV_EXPR:
2554 128052 : res = wi::div_floor (w0, w1, sign, &overflow);
2555 128052 : break;
2556 288 : case ROUND_DIV_EXPR:
2557 288 : res = wi::div_round (w0, w1, sign, &overflow);
2558 288 : break;
2559 10866 : case CEIL_DIV_EXPR:
2560 10866 : res = wi::div_ceil (w0, w1, sign, &overflow);
2561 10866 : break;
2562 0 : default:
2563 0 : gcc_unreachable ();
2564 : }
2565 :
2566 12769136 : if (overflow && TYPE_OVERFLOW_UNDEFINED (type))
2567 : {
2568 : // For division, the only case is -INF / -1 = +INF.
2569 202001 : res = wi::max_value (w0.get_precision (), sign);
2570 202001 : return false;
2571 : }
2572 12567135 : return overflow;
2573 : }
2574 :
2575 : void
2576 4080458 : operator_div::wi_fold (irange &r, tree type,
2577 : const wide_int &lh_lb, const wide_int &lh_ub,
2578 : const wide_int &rh_lb, const wide_int &rh_ub) const
2579 : {
2580 4080458 : const wide_int dividend_min = lh_lb;
2581 4080458 : const wide_int dividend_max = lh_ub;
2582 4080458 : const wide_int divisor_min = rh_lb;
2583 4080458 : const wide_int divisor_max = rh_ub;
2584 4080458 : signop sign = TYPE_SIGN (type);
2585 4080458 : unsigned prec = TYPE_PRECISION (type);
2586 4080458 : wide_int extra_min, extra_max;
2587 :
2588 : // If we know we won't divide by zero, just do the division.
2589 4080458 : if (!wi_includes_zero_p (type, divisor_min, divisor_max))
2590 : {
2591 3387490 : wi_cross_product (r, type, dividend_min, dividend_max,
2592 : divisor_min, divisor_max);
2593 3387490 : return;
2594 : }
2595 :
2596 : // If we're definitely dividing by zero, there's nothing to do.
2597 692968 : if (wi_zero_p (type, divisor_min, divisor_max))
2598 : {
2599 17755 : r.set_undefined ();
2600 17755 : return;
2601 : }
2602 :
2603 : // Perform the division in 2 parts, [LB, -1] and [1, UB], which will
2604 : // skip any division by zero.
2605 :
2606 : // First divide by the negative numbers, if any.
2607 675213 : if (wi::neg_p (divisor_min, sign))
2608 899286 : wi_cross_product (r, type, dividend_min, dividend_max,
2609 899286 : divisor_min, wi::minus_one (prec));
2610 : else
2611 225570 : r.set_undefined ();
2612 :
2613 : // Then divide by the non-zero positive numbers, if any.
2614 675213 : if (wi::gt_p (divisor_max, wi::zero (prec), sign))
2615 : {
2616 674611 : int_range_max tmp;
2617 1349222 : wi_cross_product (tmp, type, dividend_min, dividend_max,
2618 674611 : wi::one (prec), divisor_max);
2619 674611 : r.union_ (tmp);
2620 674611 : }
2621 : // We shouldn't still have undefined here.
2622 675213 : gcc_checking_assert (!r.undefined_p ());
2623 4081070 : }
2624 :
2625 :
2626 : class operator_exact_divide : public operator_div
2627 : {
2628 : using range_operator::op1_range;
2629 : public:
2630 : operator_exact_divide () : operator_div (EXACT_DIV_EXPR) { }
2631 : virtual bool op1_range (irange &r, tree type,
2632 : const irange &lhs,
2633 : const irange &op2,
2634 : relation_trio) const;
2635 :
2636 : } op_exact_div;
2637 :
2638 : bool
2639 590397 : operator_exact_divide::op1_range (irange &r, tree type,
2640 : const irange &lhs,
2641 : const irange &op2,
2642 : relation_trio) const
2643 : {
2644 590397 : if (lhs.undefined_p ())
2645 : return false;
2646 590397 : wide_int offset;
2647 : // [2, 4] = op1 / [3,3] since its exact divide, no need to worry about
2648 : // remainders in the endpoints, so op1 = [2,4] * [3,3] = [6,12].
2649 : // We wont bother trying to enumerate all the in between stuff :-P
2650 : // TRUE accuracy is [6,6][9,9][12,12]. This is unlikely to matter most of
2651 : // the time however.
2652 : // If op2 is a multiple of 2, we would be able to set some non-zero bits.
2653 590397 : if (op2.singleton_p (offset) && offset != 0)
2654 590397 : return range_op_handler (MULT_EXPR).fold_range (r, type, lhs, op2);
2655 : return false;
2656 590397 : }
2657 :
2658 :
2659 : class operator_lshift : public cross_product_operator
2660 : {
2661 : using range_operator::fold_range;
2662 : using range_operator::op1_range;
2663 : using range_operator::update_bitmask;
2664 : public:
2665 : virtual bool op1_range (irange &r, tree type, const irange &lhs,
2666 : const irange &op2, relation_trio rel = TRIO_VARYING)
2667 : const final override;
2668 : virtual bool fold_range (irange &r, tree type, const irange &op1,
2669 : const irange &op2, relation_trio rel = TRIO_VARYING)
2670 : const final override;
2671 :
2672 : virtual void wi_fold (irange &r, tree type,
2673 : const wide_int &lh_lb, const wide_int &lh_ub,
2674 : const wide_int &rh_lb,
2675 : const wide_int &rh_ub) const final override;
2676 : virtual bool wi_op_overflows (wide_int &res,
2677 : tree type,
2678 : const wide_int &,
2679 : const wide_int &) const final override;
2680 452070 : void update_bitmask (irange &r, const irange &lh,
2681 : const irange &rh) const final override
2682 452070 : { update_known_bitmask (r, LSHIFT_EXPR, lh, rh); }
2683 : // Check compatibility of LHS and op1.
2684 1047023 : bool operand_check_p (tree t1, tree t2, tree) const final override
2685 1047023 : { return range_compatible_p (t1, t2); }
2686 : } op_lshift;
2687 :
2688 : class operator_rshift : public cross_product_operator
2689 : {
2690 : using range_operator::fold_range;
2691 : using range_operator::op1_range;
2692 : using range_operator::lhs_op1_relation;
2693 : using range_operator::update_bitmask;
2694 : public:
2695 : virtual bool fold_range (irange &r, tree type, const irange &op1,
2696 : const irange &op2, relation_trio rel = TRIO_VARYING)
2697 : const final override;
2698 : virtual void wi_fold (irange &r, tree type,
2699 : const wide_int &lh_lb,
2700 : const wide_int &lh_ub,
2701 : const wide_int &rh_lb,
2702 : const wide_int &rh_ub) const final override;
2703 : virtual bool wi_op_overflows (wide_int &res,
2704 : tree type,
2705 : const wide_int &w0,
2706 : const wide_int &w1) const final override;
2707 : virtual bool op1_range (irange &, tree type, const irange &lhs,
2708 : const irange &op2, relation_trio rel = TRIO_VARYING)
2709 : const final override;
2710 : virtual relation_kind lhs_op1_relation (const irange &lhs, const irange &op1,
2711 : const irange &op2, relation_kind rel)
2712 : const final override;
2713 3201460 : void update_bitmask (irange &r, const irange &lh,
2714 : const irange &rh) const final override
2715 3201460 : { update_known_bitmask (r, RSHIFT_EXPR, lh, rh); }
2716 : // Check compatibility of LHS and op1.
2717 3290234 : bool operand_check_p (tree t1, tree t2, tree) const final override
2718 3290234 : { return range_compatible_p (t1, t2); }
2719 : } op_rshift;
2720 :
2721 :
2722 : relation_kind
2723 2324614 : operator_rshift::lhs_op1_relation (const irange &lhs ATTRIBUTE_UNUSED,
2724 : const irange &op1,
2725 : const irange &op2,
2726 : relation_kind) const
2727 : {
2728 : // If both operands range are >= 0, then the LHS <= op1.
2729 2324614 : if (!op1.undefined_p () && !op2.undefined_p ()
2730 4648475 : && wi::ge_p (op1.lower_bound (), 0, TYPE_SIGN (op1.type ()))
2731 6727059 : && wi::ge_p (op2.lower_bound (), 0, TYPE_SIGN (op2.type ())))
2732 2050702 : return VREL_LE;
2733 : return VREL_VARYING;
2734 : }
2735 :
2736 : bool
2737 1584132 : operator_lshift::fold_range (irange &r, tree type,
2738 : const irange &op1,
2739 : const irange &op2,
2740 : relation_trio rel) const
2741 : {
2742 1584132 : int_range_max shift_range;
2743 1584132 : if (!get_shift_range (shift_range, type, op2))
2744 : {
2745 557 : if (op2.undefined_p ())
2746 225 : r.set_undefined ();
2747 : else
2748 332 : r.set_zero (type);
2749 557 : return true;
2750 : }
2751 :
2752 : // Transform left shifts by constants into multiplies.
2753 1583575 : if (shift_range.singleton_p ())
2754 : {
2755 1131478 : unsigned shift = shift_range.lower_bound ().to_uhwi ();
2756 1131478 : wide_int tmp = wi::set_bit_in_zero (shift, TYPE_PRECISION (type));
2757 1131478 : int_range<1> mult (type, tmp, tmp);
2758 :
2759 : // Force wrapping multiplication.
2760 1131478 : bool saved_flag_wrapv = flag_wrapv;
2761 1131478 : bool saved_flag_wrapv_pointer = flag_wrapv_pointer;
2762 1131478 : flag_wrapv = 1;
2763 1131478 : flag_wrapv_pointer = 1;
2764 1131478 : bool b = op_mult.fold_range (r, type, op1, mult);
2765 1131478 : flag_wrapv = saved_flag_wrapv;
2766 1131478 : flag_wrapv_pointer = saved_flag_wrapv_pointer;
2767 1131478 : return b;
2768 1131487 : }
2769 : else
2770 : // Otherwise, invoke the generic fold routine.
2771 452097 : return range_operator::fold_range (r, type, op1, shift_range, rel);
2772 1584132 : }
2773 :
2774 : void
2775 534624 : operator_lshift::wi_fold (irange &r, tree type,
2776 : const wide_int &lh_lb, const wide_int &lh_ub,
2777 : const wide_int &rh_lb, const wide_int &rh_ub) const
2778 : {
2779 534624 : signop sign = TYPE_SIGN (type);
2780 534624 : unsigned prec = TYPE_PRECISION (type);
2781 534624 : int overflow_pos = sign == SIGNED ? prec - 1 : prec;
2782 534624 : int bound_shift = overflow_pos - rh_ub.to_shwi ();
2783 : // If bound_shift == HOST_BITS_PER_WIDE_INT, the llshift can
2784 : // overflow. However, for that to happen, rh.max needs to be zero,
2785 : // which means rh is a singleton range of zero, which means we simply return
2786 : // [lh_lb, lh_ub] as the range.
2787 534624 : if (wi::eq_p (rh_ub, rh_lb) && wi::eq_p (rh_ub, 0))
2788 : {
2789 22420 : r = int_range<2> (type, lh_lb, lh_ub);
2790 22420 : return;
2791 : }
2792 :
2793 512204 : wide_int bound = wi::set_bit_in_zero (bound_shift, prec);
2794 512204 : wide_int complement = ~(bound - 1);
2795 512204 : wide_int low_bound, high_bound;
2796 512204 : bool in_bounds = false;
2797 :
2798 512204 : if (sign == UNSIGNED)
2799 : {
2800 256759 : low_bound = bound;
2801 256759 : high_bound = complement;
2802 256759 : if (wi::ltu_p (lh_ub, low_bound))
2803 : {
2804 : // [5, 6] << [1, 2] == [10, 24].
2805 : // We're shifting out only zeroes, the value increases
2806 : // monotonically.
2807 : in_bounds = true;
2808 : }
2809 82391 : else if (wi::ltu_p (high_bound, lh_lb))
2810 : {
2811 : // [0xffffff00, 0xffffffff] << [1, 2]
2812 : // == [0xfffffc00, 0xfffffffe].
2813 : // We're shifting out only ones, the value decreases
2814 : // monotonically.
2815 : in_bounds = true;
2816 : }
2817 : }
2818 : else
2819 : {
2820 : // [-1, 1] << [1, 2] == [-4, 4]
2821 255445 : low_bound = complement;
2822 255445 : high_bound = bound;
2823 255445 : if (wi::lts_p (lh_ub, high_bound)
2824 255445 : && wi::lts_p (low_bound, lh_lb))
2825 : {
2826 : // For non-negative numbers, we're shifting out only zeroes,
2827 : // the value increases monotonically. For negative numbers,
2828 : // we're shifting out only ones, the value decreases
2829 : // monotonically.
2830 : in_bounds = true;
2831 : }
2832 : }
2833 :
2834 : if (in_bounds)
2835 291296 : wi_cross_product (r, type, lh_lb, lh_ub, rh_lb, rh_ub);
2836 : else
2837 220908 : r.set_varying (type);
2838 512222 : }
2839 :
2840 : bool
2841 563210 : operator_lshift::wi_op_overflows (wide_int &res, tree type,
2842 : const wide_int &w0, const wide_int &w1) const
2843 : {
2844 563210 : signop sign = TYPE_SIGN (type);
2845 563210 : if (wi::neg_p (w1))
2846 : {
2847 : // It's unclear from the C standard whether shifts can overflow.
2848 : // The following code ignores overflow; perhaps a C standard
2849 : // interpretation ruling is needed.
2850 0 : res = wi::rshift (w0, -w1, sign);
2851 : }
2852 : else
2853 563210 : res = wi::lshift (w0, w1);
2854 563210 : return false;
2855 : }
2856 :
2857 : bool
2858 45903 : operator_lshift::op1_range (irange &r,
2859 : tree type,
2860 : const irange &lhs,
2861 : const irange &op2,
2862 : relation_trio) const
2863 : {
2864 45903 : if (lhs.undefined_p ())
2865 : return false;
2866 :
2867 45903 : if (!contains_zero_p (lhs))
2868 18580 : r.set_nonzero (type);
2869 : else
2870 27323 : r.set_varying (type);
2871 :
2872 45903 : wide_int shift;
2873 45903 : if (op2.singleton_p (shift))
2874 : {
2875 40107 : if (wi::lt_p (shift, 0, SIGNED))
2876 : return false;
2877 40107 : if (wi::ge_p (shift, wi::uhwi (TYPE_PRECISION (type),
2878 40107 : TYPE_PRECISION (op2.type ())),
2879 : UNSIGNED))
2880 : return false;
2881 40107 : if (shift == 0)
2882 : {
2883 6 : r.intersect (lhs);
2884 6 : return true;
2885 : }
2886 :
2887 : // Work completely in unsigned mode to start.
2888 40101 : tree utype = type;
2889 40101 : int_range_max tmp_range;
2890 40101 : if (TYPE_SIGN (type) == SIGNED)
2891 : {
2892 7741 : int_range_max tmp = lhs;
2893 7741 : utype = unsigned_type_for (type);
2894 7741 : range_cast (tmp, utype);
2895 7741 : op_rshift.fold_range (tmp_range, utype, tmp, op2);
2896 7741 : }
2897 : else
2898 32360 : op_rshift.fold_range (tmp_range, utype, lhs, op2);
2899 :
2900 : // Start with ranges which can produce the LHS by right shifting the
2901 : // result by the shift amount.
2902 : // ie [0x08, 0xF0] = op1 << 2 will start with
2903 : // [00001000, 11110000] = op1 << 2
2904 : // [0x02, 0x4C] aka [00000010, 00111100]
2905 :
2906 : // Then create a range from the LB with the least significant upper bit
2907 : // set, to the upper bound with all the bits set.
2908 : // This would be [0x42, 0xFC] aka [01000010, 11111100].
2909 :
2910 : // Ideally we do this for each subrange, but just lump them all for now.
2911 40101 : unsigned low_bits = TYPE_PRECISION (utype) - shift.to_uhwi ();
2912 40101 : wide_int up_mask = wi::mask (low_bits, true, TYPE_PRECISION (utype));
2913 40101 : wide_int new_ub = wi::bit_or (up_mask, tmp_range.upper_bound ());
2914 40101 : wide_int new_lb = wi::set_bit (tmp_range.lower_bound (), low_bits);
2915 40101 : int_range<2> fill_range (utype, new_lb, new_ub);
2916 40101 : tmp_range.union_ (fill_range);
2917 :
2918 40101 : if (utype != type)
2919 7741 : range_cast (tmp_range, type);
2920 :
2921 40101 : r.intersect (tmp_range);
2922 40101 : return true;
2923 40101 : }
2924 :
2925 5796 : return !r.varying_p ();
2926 45903 : }
2927 :
2928 : bool
2929 798012 : operator_rshift::op1_range (irange &r,
2930 : tree type,
2931 : const irange &lhs,
2932 : const irange &op2,
2933 : relation_trio) const
2934 : {
2935 798012 : if (lhs.undefined_p ())
2936 : return false;
2937 798012 : wide_int shift;
2938 798012 : if (op2.singleton_p (shift))
2939 : {
2940 : // Ignore nonsensical shifts.
2941 775312 : unsigned prec = TYPE_PRECISION (type);
2942 1550624 : if (wi::ge_p (shift,
2943 775312 : wi::uhwi (prec, TYPE_PRECISION (op2.type ())),
2944 : UNSIGNED))
2945 : return false;
2946 775312 : if (shift == 0)
2947 : {
2948 75 : r = lhs;
2949 75 : return true;
2950 : }
2951 :
2952 : // Folding the original operation may discard some impossible
2953 : // ranges from the LHS.
2954 775237 : int_range_max lhs_refined;
2955 775237 : op_rshift.fold_range (lhs_refined, type, int_range<1> (type), op2);
2956 775237 : lhs_refined.intersect (lhs);
2957 775237 : if (lhs_refined.undefined_p ())
2958 : {
2959 4 : r.set_undefined ();
2960 4 : return true;
2961 : }
2962 775233 : int_range_max shift_range (op2.type (), shift, shift);
2963 775233 : int_range_max lb, ub;
2964 775233 : op_lshift.fold_range (lb, type, lhs_refined, shift_range);
2965 : // LHS
2966 : // 0000 0111 = OP1 >> 3
2967 : //
2968 : // OP1 is anything from 0011 1000 to 0011 1111. That is, a
2969 : // range from LHS<<3 plus a mask of the 3 bits we shifted on the
2970 : // right hand side (0x07).
2971 775233 : wide_int mask = wi::mask (shift.to_uhwi (), false, prec);
2972 775233 : int_range_max mask_range (type,
2973 775233 : wi::zero (TYPE_PRECISION (type)),
2974 775233 : mask);
2975 775233 : op_plus.fold_range (ub, type, lb, mask_range);
2976 775233 : r = lb;
2977 775233 : r.union_ (ub);
2978 775233 : if (!contains_zero_p (lhs_refined))
2979 : {
2980 449085 : mask_range.invert ();
2981 449085 : r.intersect (mask_range);
2982 : }
2983 775233 : return true;
2984 775237 : }
2985 : return false;
2986 798012 : }
2987 :
2988 : bool
2989 10635912 : operator_rshift::wi_op_overflows (wide_int &res,
2990 : tree type,
2991 : const wide_int &w0,
2992 : const wide_int &w1) const
2993 : {
2994 10635912 : signop sign = TYPE_SIGN (type);
2995 10635912 : if (wi::neg_p (w1))
2996 0 : res = wi::lshift (w0, -w1);
2997 : else
2998 : {
2999 : // It's unclear from the C standard whether shifts can overflow.
3000 : // The following code ignores overflow; perhaps a C standard
3001 : // interpretation ruling is needed.
3002 10636003 : res = wi::rshift (w0, w1, sign);
3003 : }
3004 10635912 : return false;
3005 : }
3006 :
3007 : bool
3008 3202595 : operator_rshift::fold_range (irange &r, tree type,
3009 : const irange &op1,
3010 : const irange &op2,
3011 : relation_trio rel) const
3012 : {
3013 3202595 : int_range_max shift;
3014 3202595 : if (!get_shift_range (shift, type, op2))
3015 : {
3016 556 : if (op2.undefined_p ())
3017 198 : r.set_undefined ();
3018 : else
3019 358 : r.set_zero (type);
3020 556 : return true;
3021 : }
3022 :
3023 3202039 : return range_operator::fold_range (r, type, op1, shift, rel);
3024 3202595 : }
3025 :
3026 : void
3027 3761366 : operator_rshift::wi_fold (irange &r, tree type,
3028 : const wide_int &lh_lb, const wide_int &lh_ub,
3029 : const wide_int &rh_lb, const wide_int &rh_ub) const
3030 : {
3031 3761366 : wi_cross_product (r, type, lh_lb, lh_ub, rh_lb, rh_ub);
3032 3761366 : }
3033 :
3034 :
3035 : // Add a partial equivalence between the LHS and op1 for casts.
3036 :
3037 : relation_kind
3038 23373330 : operator_cast::lhs_op1_relation (const irange &lhs,
3039 : const irange &op1,
3040 : const irange &op2 ATTRIBUTE_UNUSED,
3041 : relation_kind) const
3042 : {
3043 23373330 : if (lhs.undefined_p () || op1.undefined_p ())
3044 : return VREL_VARYING;
3045 23352217 : unsigned lhs_prec = TYPE_PRECISION (lhs.type ());
3046 23352217 : unsigned op1_prec = TYPE_PRECISION (op1.type ());
3047 : // If the result gets sign extended into a larger type check first if this
3048 : // qualifies as a partial equivalence.
3049 23352217 : if (TYPE_SIGN (op1.type ()) == SIGNED && lhs_prec > op1_prec)
3050 : {
3051 : // If the result is sign extended, and the LHS is larger than op1,
3052 : // check if op1's range can be negative as the sign extension will
3053 : // cause the upper bits to be 1 instead of 0, invalidating the PE.
3054 3811521 : int_range<3> negs = range_negatives (op1.type ());
3055 3811521 : negs.intersect (op1);
3056 3811521 : if (!negs.undefined_p ())
3057 2654131 : return VREL_VARYING;
3058 3811521 : }
3059 :
3060 20698086 : unsigned prec = MIN (lhs_prec, op1_prec);
3061 20698086 : return bits_to_pe (prec);
3062 : }
3063 :
3064 : // Return TRUE if casting from INNER to OUTER is a truncating cast.
3065 :
3066 : inline bool
3067 83557921 : operator_cast::truncating_cast_p (const irange &inner,
3068 : const irange &outer) const
3069 : {
3070 83557921 : return TYPE_PRECISION (outer.type ()) < TYPE_PRECISION (inner.type ());
3071 : }
3072 :
3073 : // Return TRUE if [MIN,MAX] is inside the domain of RANGE's type.
3074 :
3075 : bool
3076 71725153 : operator_cast::inside_domain_p (const wide_int &min,
3077 : const wide_int &max,
3078 : const irange &range) const
3079 : {
3080 71725153 : wide_int domain_min = irange_val_min (range.type ());
3081 71725153 : wide_int domain_max = irange_val_max (range.type ());
3082 71725153 : signop domain_sign = TYPE_SIGN (range.type ());
3083 71725153 : return (wi::le_p (min, domain_max, domain_sign)
3084 71725153 : && wi::le_p (max, domain_max, domain_sign)
3085 71725153 : && wi::ge_p (min, domain_min, domain_sign)
3086 143450306 : && wi::ge_p (max, domain_min, domain_sign));
3087 71725153 : }
3088 :
3089 :
3090 : // Helper for fold_range which work on a pair at a time.
3091 :
3092 : void
3093 74952004 : operator_cast::fold_pair (irange &r, unsigned index,
3094 : const irange &inner,
3095 : const irange &outer) const
3096 : {
3097 74952004 : tree inner_type = inner.type ();
3098 74952004 : tree outer_type = outer.type ();
3099 74952004 : signop inner_sign = TYPE_SIGN (inner_type);
3100 74952004 : unsigned outer_prec = TYPE_PRECISION (outer_type);
3101 :
3102 : // check to see if casting from INNER to OUTER is a conversion that
3103 : // fits in the resulting OUTER type.
3104 74952004 : wide_int inner_lb = inner.lower_bound (index);
3105 74952004 : wide_int inner_ub = inner.upper_bound (index);
3106 74952004 : if (truncating_cast_p (inner, outer))
3107 : {
3108 : // We may be able to accommodate a truncating cast if the
3109 : // resulting range can be represented in the target type...
3110 15652928 : if (wi::rshift (wi::sub (inner_ub, inner_lb),
3111 7826464 : wi::uhwi (outer_prec, TYPE_PRECISION (inner.type ())),
3112 23479392 : inner_sign) != 0)
3113 : {
3114 3226851 : r.set_varying (outer_type);
3115 3226851 : return;
3116 : }
3117 : }
3118 : // ...but we must still verify that the final range fits in the
3119 : // domain. This catches -fstrict-enum restrictions where the domain
3120 : // range is smaller than what fits in the underlying type.
3121 71725153 : wide_int min = wide_int::from (inner_lb, outer_prec, inner_sign);
3122 71725153 : wide_int max = wide_int::from (inner_ub, outer_prec, inner_sign);
3123 71725153 : if (inside_domain_p (min, max, outer))
3124 71725153 : create_possibly_reversed_range (r, outer_type, min, max);
3125 : else
3126 0 : r.set_varying (outer_type);
3127 74955053 : }
3128 :
3129 :
3130 : bool
3131 61341679 : operator_cast::fold_range (irange &r, tree type ATTRIBUTE_UNUSED,
3132 : const irange &inner,
3133 : const irange &outer,
3134 : relation_trio) const
3135 : {
3136 61341679 : if (empty_range_varying (r, type, inner, outer))
3137 32818 : return true;
3138 :
3139 61308861 : gcc_checking_assert (outer.varying_p ());
3140 61308861 : gcc_checking_assert (inner.num_pairs () > 0);
3141 :
3142 : // Avoid a temporary by folding the first pair directly into the result.
3143 61308861 : fold_pair (r, 0, inner, outer);
3144 :
3145 : // Then process any additional pairs by unioning with their results.
3146 74285049 : for (unsigned x = 1; x < inner.num_pairs (); ++x)
3147 : {
3148 13643143 : int_range_max tmp;
3149 13643143 : fold_pair (tmp, x, inner, outer);
3150 13643143 : r.union_ (tmp);
3151 : // If we hit varying, go update the bitmask.
3152 13643143 : if (r.varying_p ())
3153 : break;
3154 13643143 : }
3155 :
3156 61308861 : update_bitmask (r, inner, outer);
3157 61308861 : return true;
3158 : }
3159 :
3160 : void
3161 61308861 : operator_cast::update_bitmask (irange &r, const irange &lh,
3162 : const irange &rh) const
3163 : {
3164 61308861 : update_known_bitmask (r, CONVERT_EXPR, lh, rh);
3165 61308861 : }
3166 :
3167 : bool
3168 8605917 : operator_cast::op1_range (irange &r, tree type,
3169 : const irange &lhs,
3170 : const irange &op2,
3171 : relation_trio) const
3172 : {
3173 8605917 : if (lhs.undefined_p ())
3174 : return false;
3175 8605917 : tree lhs_type = lhs.type ();
3176 8605917 : gcc_checking_assert (types_compatible_p (op2.type(), type));
3177 :
3178 : // If we are calculating a pointer, shortcut to what we really care about.
3179 8605917 : if (POINTER_TYPE_P (type))
3180 : {
3181 : // Conversion from other pointers or a constant (including 0/NULL)
3182 : // are straightforward.
3183 0 : if (POINTER_TYPE_P (lhs.type ())
3184 0 : || (lhs.singleton_p ()
3185 0 : && TYPE_PRECISION (lhs.type ()) >= TYPE_PRECISION (type)))
3186 : {
3187 0 : r = lhs;
3188 0 : range_cast (r, type);
3189 : }
3190 : else
3191 : {
3192 : // If the LHS is not a pointer nor a singleton, then it is
3193 : // either VARYING or non-zero.
3194 0 : if (!lhs.undefined_p () && !contains_zero_p (lhs))
3195 0 : r.set_nonzero (type);
3196 : else
3197 0 : r.set_varying (type);
3198 : }
3199 0 : r.intersect (op2);
3200 0 : return true;
3201 : }
3202 :
3203 8605917 : if (truncating_cast_p (op2, lhs))
3204 : {
3205 1317920 : if (lhs.varying_p ())
3206 139679 : r.set_varying (type);
3207 : else
3208 : {
3209 : // We want to insert the LHS as an unsigned value since it
3210 : // would not trigger the signed bit of the larger type.
3211 1178241 : int_range_max converted_lhs = lhs;
3212 1178241 : range_cast (converted_lhs, unsigned_type_for (lhs_type));
3213 1178241 : range_cast (converted_lhs, type);
3214 : // Start by building the positive signed outer range for the type.
3215 1178241 : wide_int lim = wi::set_bit_in_zero (TYPE_PRECISION (lhs_type),
3216 2356482 : TYPE_PRECISION (type));
3217 1178241 : create_possibly_reversed_range (r, type, lim,
3218 1178241 : wi::max_value (TYPE_PRECISION (type),
3219 : SIGNED));
3220 : // For the signed part, we need to simply union the 2 ranges now.
3221 1178241 : r.union_ (converted_lhs);
3222 :
3223 : // Create maximal negative number outside of LHS bits.
3224 1178241 : lim = wi::mask (TYPE_PRECISION (lhs_type), true,
3225 2356482 : TYPE_PRECISION (type));
3226 : // Add this to the unsigned LHS range(s).
3227 1178241 : int_range_max lim_range (type, lim, lim);
3228 1178241 : int_range_max lhs_neg;
3229 1178241 : range_op_handler (PLUS_EXPR).fold_range (lhs_neg, type,
3230 : converted_lhs, lim_range);
3231 : // lhs_neg now has all the negative versions of the LHS.
3232 : // Now union in all the values from SIGNED MIN (0x80000) to
3233 : // lim-1 in order to fill in all the ranges with the upper
3234 : // bits set.
3235 :
3236 : // PR 97317. If the lhs has only 1 bit less precision than the rhs,
3237 : // we don't need to create a range from min to lim-1
3238 : // calculate neg range traps trying to create [lim, lim - 1].
3239 1178241 : wide_int min_val = wi::min_value (TYPE_PRECISION (type), SIGNED);
3240 1178241 : if (lim != min_val)
3241 : {
3242 1176745 : int_range_max neg (type,
3243 2353490 : wi::min_value (TYPE_PRECISION (type),
3244 : SIGNED),
3245 2353490 : lim - 1);
3246 1176745 : lhs_neg.union_ (neg);
3247 1176745 : }
3248 : // And finally, munge the signed and unsigned portions.
3249 1178241 : r.union_ (lhs_neg);
3250 1178241 : }
3251 : // And intersect with any known value passed in the extra operand.
3252 1317920 : r.intersect (op2);
3253 1317920 : if (r.undefined_p ())
3254 : return true;
3255 :
3256 : // Now create a bitmask indicating that the lower bit must match the
3257 : // bits in the LHS. Zero-extend LHS bitmask to precision of op1.
3258 1317862 : irange_bitmask bm = lhs.get_bitmask ();
3259 2635724 : wide_int mask = wide_int::from (bm.mask (), TYPE_PRECISION (type),
3260 2635724 : UNSIGNED);
3261 2635724 : wide_int value = wide_int::from (bm.value (), TYPE_PRECISION (type),
3262 2635724 : UNSIGNED);
3263 :
3264 : // Set then additional unknown bits in mask.
3265 1317862 : wide_int lim = wi::mask (TYPE_PRECISION (lhs_type), true,
3266 2635724 : TYPE_PRECISION (type));
3267 1317862 : mask = mask | lim;
3268 :
3269 : // Now set the new bitmask for the range.
3270 1317862 : irange_bitmask new_bm (value, mask);
3271 1317862 : r.update_bitmask (new_bm);
3272 1317862 : return true;
3273 1317862 : }
3274 :
3275 7287997 : int_range_max tmp;
3276 7287997 : if (TYPE_PRECISION (lhs_type) == TYPE_PRECISION (type))
3277 4997364 : tmp = lhs;
3278 : else
3279 : {
3280 : // The cast is not truncating, and the range is restricted to
3281 : // the range of the RHS by this assignment.
3282 : //
3283 : // Cast the range of the RHS to the type of the LHS.
3284 2290633 : fold_range (tmp, lhs_type, int_range<1> (type), int_range<1> (lhs_type));
3285 : // Intersect this with the LHS range will produce the range,
3286 : // which will be cast to the RHS type before returning.
3287 2290633 : tmp.intersect (lhs);
3288 : }
3289 :
3290 : // Cast the calculated range to the type of the RHS.
3291 7287997 : fold_range (r, type, tmp, int_range<1> (type));
3292 7287997 : return true;
3293 7287997 : }
3294 :
3295 : // VIEW_CONVERT_EXPR works like a cast between integral values.
3296 : // If the number of bits are not the same, behaviour is undefined,
3297 : // so cast behaviour still works.
3298 :
3299 : bool
3300 282444 : operator_view::fold_range (irange &r, tree type,
3301 : const irange &op1, const irange &op2,
3302 : relation_trio rel) const
3303 : {
3304 282444 : return m_cast.fold_range (r, type, op1, op2, rel);
3305 : }
3306 :
3307 : bool
3308 0 : operator_view::fold_range (prange &r, tree type,
3309 : const prange &op1, const prange &op2,
3310 : relation_trio rel) const
3311 : {
3312 0 : return m_cast.fold_range (r, type, op1, op2, rel);
3313 : }
3314 : bool
3315 259620 : operator_view::fold_range (irange &r, tree type,
3316 : const prange &op1, const irange &op2,
3317 : relation_trio rel) const
3318 : {
3319 259620 : return m_cast.fold_range (r, type, op1, op2, rel);
3320 : }
3321 :
3322 : bool
3323 0 : operator_view::fold_range (prange &r, tree type,
3324 : const irange &op1, const prange &op2,
3325 : relation_trio rel) const
3326 : {
3327 0 : return m_cast.fold_range (r, type, op1, op2, rel);
3328 : }
3329 :
3330 : bool
3331 8812 : operator_view::op1_range (irange &r, tree type,
3332 : const irange &lhs, const irange &op2,
3333 : relation_trio rel) const
3334 : {
3335 8812 : return m_cast.op1_range (r, type, lhs, op2, rel);
3336 : }
3337 :
3338 : bool
3339 0 : operator_view::op1_range (prange &r, tree type,
3340 : const prange &lhs, const prange &op2,
3341 : relation_trio rel) const
3342 : {
3343 0 : return m_cast.op1_range (r, type, lhs, op2, rel);
3344 : }
3345 :
3346 : bool
3347 0 : operator_view::op1_range (irange &r, tree type,
3348 : const prange &lhs, const irange &op2,
3349 : relation_trio rel) const
3350 : {
3351 0 : return m_cast.op1_range (r, type, lhs, op2, rel);
3352 : }
3353 :
3354 : bool
3355 0 : operator_view::op1_range (prange &r, tree type,
3356 : const irange &lhs, const prange &op2,
3357 : relation_trio rel) const
3358 : {
3359 0 : return m_cast.op1_range (r, type, lhs, op2, rel);
3360 : }
3361 :
3362 : void
3363 0 : operator_view::update_bitmask (irange &r, const irange &lh,
3364 : const irange &rh) const
3365 : {
3366 0 : m_cast.update_bitmask (r, lh, rh);
3367 0 : }
3368 :
3369 :
3370 : class operator_logical_and : public range_operator
3371 : {
3372 : using range_operator::fold_range;
3373 : using range_operator::op1_range;
3374 : using range_operator::op2_range;
3375 : public:
3376 : bool fold_range (irange &r, tree type,
3377 : const irange &lh,
3378 : const irange &rh,
3379 : relation_trio rel = TRIO_VARYING) const final override;
3380 : bool op1_range (irange &r, tree type,
3381 : const irange &lhs,
3382 : const irange &op2,
3383 : relation_trio rel = TRIO_VARYING) const final override;
3384 : bool op2_range (irange &r, tree type,
3385 : const irange &lhs,
3386 : const irange &op1,
3387 : relation_trio rel = TRIO_VARYING) const final override;
3388 : // Check compatibility of all operands.
3389 0 : bool operand_check_p (tree t1, tree t2, tree t3) const final override
3390 0 : { return range_compatible_p (t1, t2) && range_compatible_p (t1, t3); }
3391 : } op_logical_and;
3392 :
3393 : bool
3394 0 : operator_logical_and::fold_range (irange &r, tree type,
3395 : const irange &lh,
3396 : const irange &rh,
3397 : relation_trio) const
3398 : {
3399 0 : if (empty_range_varying (r, type, lh, rh))
3400 0 : return true;
3401 :
3402 : // Precision of LHS and both operands must match.
3403 0 : if (TYPE_PRECISION (lh.type ()) != TYPE_PRECISION (type)
3404 0 : || TYPE_PRECISION (type) != TYPE_PRECISION (rh.type ()))
3405 0 : return false;
3406 :
3407 : // 0 && anything is 0.
3408 0 : if ((wi::eq_p (lh.lower_bound (), 0) && wi::eq_p (lh.upper_bound (), 0))
3409 0 : || (wi::eq_p (lh.lower_bound (), 0) && wi::eq_p (rh.upper_bound (), 0)))
3410 0 : r = range_false (type);
3411 0 : else if (contains_zero_p (lh) || contains_zero_p (rh))
3412 : // To reach this point, there must be a logical 1 on each side, and
3413 : // the only remaining question is whether there is a zero or not.
3414 0 : r = range_true_and_false (type);
3415 : else
3416 0 : r = range_true (type);
3417 : return true;
3418 : }
3419 :
3420 : bool
3421 836256 : operator_logical_and::op1_range (irange &r, tree type,
3422 : const irange &lhs,
3423 : const irange &op2,
3424 : relation_trio) const
3425 : {
3426 836256 : switch (get_bool_state (r, lhs, type))
3427 : {
3428 434097 : case BRS_TRUE:
3429 : // A TRUE result means both sides of the AND must be true.
3430 434097 : r = range_true (type);
3431 434097 : return true;
3432 :
3433 400970 : case BRS_FALSE:
3434 : // A FALSE result when op2 is TRUE, must have op1 FALSE.
3435 400970 : if (!op2.contains_p (wi::zero (TYPE_PRECISION (op2.type ()))))
3436 : {
3437 6670 : r = range_false (type);
3438 6670 : return true;
3439 : }
3440 : break;
3441 :
3442 : default:
3443 : break;
3444 : }
3445 :
3446 : // Any other result means we cannot be sure of any result.
3447 395489 : r = range_true_and_false (type);
3448 395489 : return true;
3449 : }
3450 :
3451 : bool
3452 0 : operator_logical_and::op2_range (irange &r, tree type,
3453 : const irange &lhs,
3454 : const irange &op1,
3455 : relation_trio) const
3456 : {
3457 0 : return operator_logical_and::op1_range (r, type, lhs, op1);
3458 : }
3459 :
3460 :
3461 : void
3462 7294060 : operator_bitwise_and::update_bitmask (irange &r, const irange &lh,
3463 : const irange &rh) const
3464 : {
3465 7294060 : update_known_bitmask (r, BIT_AND_EXPR, lh, rh);
3466 7294060 : }
3467 :
3468 : // Optimize BIT_AND_EXPR, BIT_IOR_EXPR and BIT_XOR_EXPR of signed types
3469 : // by considering the number of leading redundant sign bit copies.
3470 : // clrsb (X op Y) = min (clrsb (X), clrsb (Y)), so for example
3471 : // [-1, 0] op [-1, 0] is [-1, 0] (where nonzero_bits doesn't help).
3472 : static bool
3473 184501 : wi_optimize_signed_bitwise_op (irange &r, tree type,
3474 : const wide_int &lh_lb, const wide_int &lh_ub,
3475 : const wide_int &rh_lb, const wide_int &rh_ub)
3476 : {
3477 369002 : int lh_clrsb = MIN (wi::clrsb (lh_lb), wi::clrsb (lh_ub));
3478 369002 : int rh_clrsb = MIN (wi::clrsb (rh_lb), wi::clrsb (rh_ub));
3479 184501 : int new_clrsb = MIN (lh_clrsb, rh_clrsb);
3480 184501 : if (new_clrsb == 0)
3481 : return false;
3482 12755 : int type_prec = TYPE_PRECISION (type);
3483 12755 : int rprec = (type_prec - new_clrsb) - 1;
3484 12755 : value_range_with_overflow (r, type,
3485 25510 : wi::mask (rprec, true, type_prec),
3486 12755 : wi::mask (rprec, false, type_prec));
3487 12755 : return true;
3488 : }
3489 :
3490 : // An AND of 8,16, 32 or 64 bits can produce a partial equivalence between
3491 : // the LHS and op1.
3492 :
3493 : relation_kind
3494 6615886 : operator_bitwise_and::lhs_op1_relation (const irange &lhs,
3495 : const irange &op1,
3496 : const irange &op2,
3497 : relation_kind) const
3498 : {
3499 6615886 : if (lhs.undefined_p () || op1.undefined_p () || op2.undefined_p ())
3500 : return VREL_VARYING;
3501 6611117 : if (!op2.singleton_p ())
3502 : return VREL_VARYING;
3503 : // if val == 0xff or 0xFFFF OR 0Xffffffff OR 0Xffffffffffffffff, return TRUE
3504 3693330 : int prec1 = TYPE_PRECISION (op1.type ());
3505 3693330 : int prec2 = TYPE_PRECISION (op2.type ());
3506 3693330 : int mask_prec = 0;
3507 3693330 : wide_int mask = op2.lower_bound ();
3508 3693330 : if (wi::eq_p (mask, wi::mask (8, false, prec2)))
3509 : mask_prec = 8;
3510 3609980 : else if (wi::eq_p (mask, wi::mask (16, false, prec2)))
3511 : mask_prec = 16;
3512 3594250 : else if (wi::eq_p (mask, wi::mask (32, false, prec2)))
3513 : mask_prec = 32;
3514 3410748 : else if (wi::eq_p (mask, wi::mask (64, false, prec2)))
3515 805 : mask_prec = 64;
3516 3693330 : return bits_to_pe (MIN (prec1, mask_prec));
3517 3693330 : }
3518 :
3519 : // Optimize BIT_AND_EXPR and BIT_IOR_EXPR in terms of a mask if
3520 : // possible. Basically, see if we can optimize:
3521 : //
3522 : // [LB, UB] op Z
3523 : // into:
3524 : // [LB op Z, UB op Z]
3525 : //
3526 : // If the optimization was successful, accumulate the range in R and
3527 : // return TRUE.
3528 :
3529 : static bool
3530 22659276 : wi_optimize_and_or (irange &r,
3531 : enum tree_code code,
3532 : tree type,
3533 : const wide_int &lh_lb, const wide_int &lh_ub,
3534 : const wide_int &rh_lb, const wide_int &rh_ub)
3535 : {
3536 : // Calculate the singleton mask among the ranges, if any.
3537 22659276 : wide_int lower_bound, upper_bound, mask;
3538 22659276 : if (wi::eq_p (rh_lb, rh_ub))
3539 : {
3540 21044231 : mask = rh_lb;
3541 21044231 : lower_bound = lh_lb;
3542 21044231 : upper_bound = lh_ub;
3543 : }
3544 1615045 : else if (wi::eq_p (lh_lb, lh_ub))
3545 : {
3546 336448 : mask = lh_lb;
3547 336448 : lower_bound = rh_lb;
3548 336448 : upper_bound = rh_ub;
3549 : }
3550 : else
3551 : return false;
3552 :
3553 : // If Z is a constant which (for op | its bitwise not) has n
3554 : // consecutive least significant bits cleared followed by m 1
3555 : // consecutive bits set immediately above it and either
3556 : // m + n == precision, or (x >> (m + n)) == (y >> (m + n)).
3557 : //
3558 : // The least significant n bits of all the values in the range are
3559 : // cleared or set, the m bits above it are preserved and any bits
3560 : // above these are required to be the same for all values in the
3561 : // range.
3562 21380679 : wide_int w = mask;
3563 21380679 : int m = 0, n = 0;
3564 21380679 : if (code == BIT_IOR_EXPR)
3565 6361573 : w = ~w;
3566 21380679 : if (wi::eq_p (w, 0))
3567 7317263 : n = w.get_precision ();
3568 : else
3569 : {
3570 14063416 : n = wi::ctz (w);
3571 14063422 : w = ~(w | wi::mask (n, false, w.get_precision ()));
3572 14063416 : if (wi::eq_p (w, 0))
3573 8511503 : m = w.get_precision () - n;
3574 : else
3575 5551913 : m = wi::ctz (w) - n;
3576 : }
3577 21380679 : wide_int new_mask = wi::mask (m + n, true, w.get_precision ());
3578 21380685 : if ((new_mask & lower_bound) != (new_mask & upper_bound))
3579 : return false;
3580 :
3581 16658931 : wide_int res_lb, res_ub;
3582 16658931 : if (code == BIT_AND_EXPR)
3583 : {
3584 10529539 : res_lb = wi::bit_and (lower_bound, mask);
3585 10529539 : res_ub = wi::bit_and (upper_bound, mask);
3586 : }
3587 6129392 : else if (code == BIT_IOR_EXPR)
3588 : {
3589 6129392 : res_lb = wi::bit_or (lower_bound, mask);
3590 6129392 : res_ub = wi::bit_or (upper_bound, mask);
3591 : }
3592 : else
3593 0 : gcc_unreachable ();
3594 16658931 : value_range_with_overflow (r, type, res_lb, res_ub);
3595 :
3596 : // Furthermore, if the mask is non-zero, an IOR cannot contain zero.
3597 16658931 : if (code == BIT_IOR_EXPR && wi::ne_p (mask, 0))
3598 : {
3599 3119220 : int_range<2> tmp;
3600 3119220 : tmp.set_nonzero (type);
3601 3119220 : r.intersect (tmp);
3602 3119220 : }
3603 16658931 : return true;
3604 60698892 : }
3605 :
3606 : // For range [LB, UB] compute two wide_int bit masks.
3607 : //
3608 : // In the MAYBE_NONZERO bit mask, if some bit is unset, it means that
3609 : // for all numbers in the range the bit is 0, otherwise it might be 0
3610 : // or 1.
3611 : //
3612 : // In the MUSTBE_NONZERO bit mask, if some bit is set, it means that
3613 : // for all numbers in the range the bit is 1, otherwise it might be 0
3614 : // or 1.
3615 :
3616 : void
3617 13024144 : wi_set_zero_nonzero_bits (tree type,
3618 : const wide_int &lb, const wide_int &ub,
3619 : wide_int &maybe_nonzero,
3620 : wide_int &mustbe_nonzero)
3621 : {
3622 13024144 : signop sign = TYPE_SIGN (type);
3623 :
3624 13024144 : if (wi::eq_p (lb, ub))
3625 5198831 : maybe_nonzero = mustbe_nonzero = lb;
3626 7825313 : else if (wi::ge_p (lb, 0, sign) || wi::lt_p (ub, 0, sign))
3627 : {
3628 7393279 : wide_int xor_mask = lb ^ ub;
3629 7393279 : maybe_nonzero = lb | ub;
3630 7393279 : mustbe_nonzero = lb & ub;
3631 7393279 : if (xor_mask != 0)
3632 : {
3633 7393279 : wide_int mask = wi::mask (wi::floor_log2 (xor_mask), false,
3634 14786558 : maybe_nonzero.get_precision ());
3635 7393279 : maybe_nonzero = maybe_nonzero | mask;
3636 7393284 : mustbe_nonzero = wi::bit_and_not (mustbe_nonzero, mask);
3637 7393279 : }
3638 7393279 : }
3639 : else
3640 : {
3641 432034 : maybe_nonzero = wi::minus_one (lb.get_precision ());
3642 432034 : mustbe_nonzero = wi::zero (lb.get_precision ());
3643 : }
3644 13024144 : }
3645 :
3646 : void
3647 16303570 : operator_bitwise_and::wi_fold (irange &r, tree type,
3648 : const wide_int &lh_lb,
3649 : const wide_int &lh_ub,
3650 : const wide_int &rh_lb,
3651 : const wide_int &rh_ub) const
3652 : {
3653 : // The AND algorithm does not handle complex signed operations well.
3654 : // If a signed range crosses the boundary between signed and unsigned
3655 : // process it as 2 ranges and union the results.
3656 16303570 : if (TYPE_SIGN (type) == SIGNED
3657 16303570 : && wi::neg_p (lh_lb, SIGNED) != wi::neg_p (lh_ub, SIGNED))
3658 : {
3659 618721 : int prec = TYPE_PRECISION (type);
3660 618721 : int_range_max tmp;
3661 : // Process [lh_lb, -1]
3662 618721 : wi_fold (tmp, type, lh_lb, wi::minus_one (prec), rh_lb, rh_ub);
3663 : // Now Process [0, rh_ub]
3664 618721 : wi_fold (r, type, wi::zero (prec), lh_ub, rh_lb, rh_ub);
3665 618721 : r.union_ (tmp);
3666 618721 : return;
3667 618721 : }
3668 :
3669 15684849 : if (wi_optimize_and_or (r, BIT_AND_EXPR, type, lh_lb, lh_ub, rh_lb, rh_ub))
3670 : return;
3671 :
3672 5155310 : wide_int maybe_nonzero_lh, mustbe_nonzero_lh;
3673 5155310 : wide_int maybe_nonzero_rh, mustbe_nonzero_rh;
3674 5155310 : wi_set_zero_nonzero_bits (type, lh_lb, lh_ub,
3675 : maybe_nonzero_lh, mustbe_nonzero_lh);
3676 5155310 : wi_set_zero_nonzero_bits (type, rh_lb, rh_ub,
3677 : maybe_nonzero_rh, mustbe_nonzero_rh);
3678 :
3679 5155310 : wide_int new_lb = mustbe_nonzero_lh & mustbe_nonzero_rh;
3680 5155310 : wide_int new_ub = maybe_nonzero_lh & maybe_nonzero_rh;
3681 5155310 : signop sign = TYPE_SIGN (type);
3682 5155310 : unsigned prec = TYPE_PRECISION (type);
3683 : // If both input ranges contain only negative values, we can
3684 : // truncate the result range maximum to the minimum of the
3685 : // input range maxima.
3686 5155310 : if (wi::lt_p (lh_ub, 0, sign) && wi::lt_p (rh_ub, 0, sign))
3687 : {
3688 46682 : new_ub = wi::min (new_ub, lh_ub, sign);
3689 46682 : new_ub = wi::min (new_ub, rh_ub, sign);
3690 : }
3691 : // If either input range contains only non-negative values
3692 : // we can truncate the result range maximum to the respective
3693 : // maximum of the input range.
3694 5155310 : if (wi::ge_p (lh_lb, 0, sign))
3695 4405556 : new_ub = wi::min (new_ub, lh_ub, sign);
3696 5155310 : if (wi::ge_p (rh_lb, 0, sign))
3697 4935112 : new_ub = wi::min (new_ub, rh_ub, sign);
3698 : // PR68217: In case of signed & sign-bit-CST should
3699 : // result in [-INF, 0] instead of [-INF, INF].
3700 5155310 : if (wi::gt_p (new_lb, new_ub, sign))
3701 : {
3702 55425 : wide_int sign_bit = wi::set_bit_in_zero (prec - 1, prec);
3703 55425 : if (sign == SIGNED
3704 55425 : && ((wi::eq_p (lh_lb, lh_ub)
3705 66 : && !wi::cmps (lh_lb, sign_bit))
3706 55425 : || (wi::eq_p (rh_lb, rh_ub)
3707 0 : && !wi::cmps (rh_lb, sign_bit))))
3708 : {
3709 0 : new_lb = wi::min_value (prec, sign);
3710 0 : new_ub = wi::zero (prec);
3711 : }
3712 55425 : }
3713 : // If the limits got swapped around, return varying.
3714 5155310 : if (wi::gt_p (new_lb, new_ub,sign))
3715 : {
3716 55425 : if (sign == SIGNED
3717 55425 : && wi_optimize_signed_bitwise_op (r, type,
3718 : lh_lb, lh_ub,
3719 : rh_lb, rh_ub))
3720 4145 : return;
3721 51280 : r.set_varying (type);
3722 : }
3723 : else
3724 5099885 : value_range_with_overflow (r, type, new_lb, new_ub);
3725 5155310 : }
3726 :
3727 : static void
3728 527980 : set_nonzero_range_from_mask (irange &r, tree type, const irange &lhs)
3729 : {
3730 527980 : if (lhs.undefined_p () || contains_zero_p (lhs))
3731 284090 : r.set_varying (type);
3732 : else
3733 243890 : r.set_nonzero (type);
3734 527980 : }
3735 :
3736 : /* Find out smallest RES where RES > VAL && (RES & MASK) == RES, if any
3737 : (otherwise return VAL). VAL and MASK must be zero-extended for
3738 : precision PREC. If SGNBIT is non-zero, first xor VAL with SGNBIT
3739 : (to transform signed values into unsigned) and at the end xor
3740 : SGNBIT back. */
3741 :
3742 : wide_int
3743 34999 : masked_increment (const wide_int &val_in, const wide_int &mask,
3744 : const wide_int &sgnbit, unsigned int prec)
3745 : {
3746 34999 : wide_int bit = wi::one (prec), res;
3747 34999 : unsigned int i;
3748 :
3749 34999 : wide_int val = val_in ^ sgnbit;
3750 630190 : for (i = 0; i < prec; i++, bit += bit)
3751 : {
3752 584997 : res = mask;
3753 584997 : if ((res & bit) == 0)
3754 502794 : continue;
3755 82203 : res = bit - 1;
3756 82203 : res = wi::bit_and_not (val + bit, res);
3757 82203 : res &= mask;
3758 82203 : if (wi::gtu_p (res, val))
3759 24805 : return res ^ sgnbit;
3760 : }
3761 10194 : return val ^ sgnbit;
3762 34999 : }
3763 :
3764 : // This was shamelessly stolen from register_edge_assert_for_2 and
3765 : // adjusted to work with iranges.
3766 :
3767 : void
3768 3196475 : operator_bitwise_and::simple_op1_range_solver (irange &r, tree type,
3769 : const irange &lhs,
3770 : const irange &op2) const
3771 : {
3772 3196475 : if (!op2.singleton_p ())
3773 : {
3774 527058 : set_nonzero_range_from_mask (r, type, lhs);
3775 1060513 : return;
3776 : }
3777 2669417 : unsigned int nprec = TYPE_PRECISION (type);
3778 2669417 : wide_int cst2v = op2.lower_bound ();
3779 2669417 : bool cst2n = wi::neg_p (cst2v, TYPE_SIGN (type));
3780 2669417 : wide_int sgnbit;
3781 2669417 : if (cst2n)
3782 538648 : sgnbit = wi::set_bit_in_zero (nprec - 1, nprec);
3783 : else
3784 2130769 : sgnbit = wi::zero (nprec);
3785 :
3786 : // Solve [lhs.lower_bound (), +INF] = x & MASK.
3787 : //
3788 : // Minimum unsigned value for >= if (VAL & CST2) == VAL is VAL and
3789 : // maximum unsigned value is ~0. For signed comparison, if CST2
3790 : // doesn't have the most significant bit set, handle it similarly. If
3791 : // CST2 has MSB set, the minimum is the same, and maximum is ~0U/2.
3792 2669417 : wide_int valv = lhs.lower_bound ();
3793 2669417 : wide_int minv = valv & cst2v, maxv;
3794 2669417 : bool we_know_nothing = false;
3795 2669417 : if (minv != valv)
3796 : {
3797 : // If (VAL & CST2) != VAL, X & CST2 can't be equal to VAL.
3798 7295 : minv = masked_increment (valv, cst2v, sgnbit, nprec);
3799 7295 : if (minv == valv)
3800 : {
3801 : // If we can't determine anything on this bound, fall
3802 : // through and conservatively solve for the other end point.
3803 2669417 : we_know_nothing = true;
3804 : }
3805 : }
3806 4800186 : maxv = wi::mask (nprec - (cst2n ? 1 : 0), false, nprec);
3807 2669417 : if (we_know_nothing)
3808 3797 : r.set_varying (type);
3809 : else
3810 2665620 : create_possibly_reversed_range (r, type, minv, maxv);
3811 :
3812 : // Solve [-INF, lhs.upper_bound ()] = x & MASK.
3813 : //
3814 : // Minimum unsigned value for <= is 0 and maximum unsigned value is
3815 : // VAL | ~CST2 if (VAL & CST2) == VAL. Otherwise, find smallest
3816 : // VAL2 where
3817 : // VAL2 > VAL && (VAL2 & CST2) == VAL2 and use (VAL2 - 1) | ~CST2
3818 : // as maximum.
3819 : // For signed comparison, if CST2 doesn't have most significant bit
3820 : // set, handle it similarly. If CST2 has MSB set, the maximum is
3821 : // the same and minimum is INT_MIN.
3822 2669417 : valv = lhs.upper_bound ();
3823 2669417 : minv = valv & cst2v;
3824 2669417 : if (minv == valv)
3825 2641713 : maxv = valv;
3826 : else
3827 : {
3828 27704 : maxv = masked_increment (valv, cst2v, sgnbit, nprec);
3829 27704 : if (maxv == valv)
3830 : {
3831 : // If we couldn't determine anything on either bound, return
3832 : // undefined.
3833 6397 : if (we_know_nothing)
3834 3211 : r.set_undefined ();
3835 6397 : return;
3836 : }
3837 21307 : maxv -= 1;
3838 : }
3839 2663020 : maxv |= ~cst2v;
3840 2663020 : minv = sgnbit;
3841 2663020 : int_range<2> upper_bits;
3842 2663020 : create_possibly_reversed_range (upper_bits, type, minv, maxv);
3843 2663020 : r.intersect (upper_bits);
3844 2669417 : }
3845 :
3846 : bool
3847 3337865 : operator_bitwise_and::op1_range (irange &r, tree type,
3848 : const irange &lhs,
3849 : const irange &op2,
3850 : relation_trio) const
3851 : {
3852 3337865 : if (lhs.undefined_p ())
3853 : return false;
3854 3337865 : if (types_compatible_p (type, boolean_type_node))
3855 836256 : return op_logical_and.op1_range (r, type, lhs, op2);
3856 :
3857 2501609 : r.set_undefined ();
3858 5698084 : for (unsigned i = 0; i < lhs.num_pairs (); ++i)
3859 : {
3860 6392950 : int_range_max chunk (lhs.type (),
3861 6392950 : lhs.lower_bound (i),
3862 6392950 : lhs.upper_bound (i));
3863 3196475 : int_range_max res;
3864 3196475 : simple_op1_range_solver (res, type, chunk, op2);
3865 3196475 : r.union_ (res);
3866 3196475 : }
3867 2501609 : if (r.undefined_p ())
3868 922 : set_nonzero_range_from_mask (r, type, lhs);
3869 :
3870 : // For MASK == op1 & MASK, all the bits in MASK must be set in op1.
3871 2501609 : wide_int mask;
3872 2501609 : if (lhs == op2 && lhs.singleton_p (mask))
3873 : {
3874 342055 : r.update_bitmask (irange_bitmask (mask, ~mask));
3875 342055 : return true;
3876 : }
3877 :
3878 2159554 : if (!op2.singleton_p (mask))
3879 : return true;
3880 :
3881 : // For 0 = op1 & MASK, op1 is ~MASK.
3882 1683842 : if (lhs.zero_p ())
3883 : {
3884 625074 : wide_int nz = wi::bit_not (op2.get_nonzero_bits ());
3885 625074 : int_range<2> tmp (type);
3886 625074 : tmp.set_nonzero_bits (nz);
3887 625074 : r.intersect (tmp);
3888 625074 : }
3889 :
3890 1683842 : irange_bitmask lhs_bm = lhs.get_bitmask ();
3891 : // given [5,7] mask 0x3 value 0x4 = N & [7, 7] mask 0x0 value 0x7
3892 : // Nothing is known about the bits not specified in the mask value (op2),
3893 : // Start with the mask, 1's will occur where values were masked.
3894 1683842 : wide_int op1_mask = ~mask;
3895 : // Any bits that are unknown on the LHS are also unknown in op1,
3896 : // so union the current mask with the LHS mask.
3897 1683842 : op1_mask |= lhs_bm.mask ();
3898 : // The resulting zeros correspond to known bits in the LHS mask, and
3899 : // the LHS value should tell us what they are. Mask off any
3900 : // extraneous values that are not covered by the mask.
3901 1683842 : wide_int op1_value = lhs_bm.value () & ~op1_mask;
3902 1683842 : irange_bitmask op1_bm (op1_value, op1_mask);
3903 : // Intersect this mask with anything already known about the value.
3904 : // A return valueof false indicated the bitmask is an UNDEFINED range.
3905 1683842 : if (op1_bm.intersect (r.get_bitmask ()))
3906 1683842 : r.update_bitmask (op1_bm);
3907 : else
3908 0 : r.set_undefined ();
3909 1683842 : return true;
3910 4185451 : }
3911 :
3912 : bool
3913 891972 : operator_bitwise_and::op2_range (irange &r, tree type,
3914 : const irange &lhs,
3915 : const irange &op1,
3916 : relation_trio) const
3917 : {
3918 891972 : return operator_bitwise_and::op1_range (r, type, lhs, op1);
3919 : }
3920 :
3921 :
3922 : class operator_logical_or : public range_operator
3923 : {
3924 : using range_operator::fold_range;
3925 : using range_operator::op1_range;
3926 : using range_operator::op2_range;
3927 : public:
3928 : bool fold_range (irange &r, tree type,
3929 : const irange &lh,
3930 : const irange &rh,
3931 : relation_trio rel = TRIO_VARYING) const final override;
3932 : bool op1_range (irange &r, tree type,
3933 : const irange &lhs,
3934 : const irange &op2,
3935 : relation_trio rel = TRIO_VARYING) const final override;
3936 : bool op2_range (irange &r, tree type,
3937 : const irange &lhs,
3938 : const irange &op1,
3939 : relation_trio rel = TRIO_VARYING) const final override;
3940 : // Check compatibility of all operands.
3941 0 : bool operand_check_p (tree t1, tree t2, tree t3) const final override
3942 0 : { return range_compatible_p (t1, t2) && range_compatible_p (t1, t3); }
3943 : } op_logical_or;
3944 :
3945 : bool
3946 0 : operator_logical_or::fold_range (irange &r, tree type ATTRIBUTE_UNUSED,
3947 : const irange &lh,
3948 : const irange &rh,
3949 : relation_trio) const
3950 : {
3951 0 : if (empty_range_varying (r, type, lh, rh))
3952 0 : return true;
3953 :
3954 0 : r = lh;
3955 0 : r.union_ (rh);
3956 0 : return true;
3957 : }
3958 :
3959 : bool
3960 365984 : operator_logical_or::op1_range (irange &r, tree type,
3961 : const irange &lhs,
3962 : const irange &op2,
3963 : relation_trio) const
3964 : {
3965 365984 : switch (get_bool_state (r, lhs, type))
3966 : {
3967 226087 : case BRS_FALSE:
3968 : // A false result means both sides of the OR must be false.
3969 226087 : r = range_false (type);
3970 226087 : return true;
3971 :
3972 138139 : case BRS_TRUE:
3973 : // A TRUE result when op2 is FALSE must have op1 TRUE.
3974 138139 : if (op2.zero_p ())
3975 : {
3976 903 : r = range_true (type);
3977 903 : return true;
3978 : }
3979 : break;
3980 :
3981 : default:
3982 : break;
3983 : }
3984 :
3985 : // Any other result means we cannot be sure of any result.
3986 138994 : r = range_true_and_false (type);
3987 138994 : return true;
3988 : }
3989 :
3990 : bool
3991 0 : operator_logical_or::op2_range (irange &r, tree type,
3992 : const irange &lhs,
3993 : const irange &op1,
3994 : relation_trio) const
3995 : {
3996 0 : return operator_logical_or::op1_range (r, type, lhs, op1);
3997 : }
3998 :
3999 :
4000 : void
4001 2392450 : operator_bitwise_or::update_bitmask (irange &r, const irange &lh,
4002 : const irange &rh) const
4003 : {
4004 2392450 : update_known_bitmask (r, BIT_IOR_EXPR, lh, rh);
4005 2392450 : }
4006 :
4007 : void
4008 6974427 : operator_bitwise_or::wi_fold (irange &r, tree type,
4009 : const wide_int &lh_lb,
4010 : const wide_int &lh_ub,
4011 : const wide_int &rh_lb,
4012 : const wide_int &rh_ub) const
4013 : {
4014 6974427 : if (wi_optimize_and_or (r, BIT_IOR_EXPR, type, lh_lb, lh_ub, rh_lb, rh_ub))
4015 6312673 : return;
4016 :
4017 845035 : wide_int maybe_nonzero_lh, mustbe_nonzero_lh;
4018 845035 : wide_int maybe_nonzero_rh, mustbe_nonzero_rh;
4019 845035 : wi_set_zero_nonzero_bits (type, lh_lb, lh_ub,
4020 : maybe_nonzero_lh, mustbe_nonzero_lh);
4021 845035 : wi_set_zero_nonzero_bits (type, rh_lb, rh_ub,
4022 : maybe_nonzero_rh, mustbe_nonzero_rh);
4023 845035 : wide_int new_lb = mustbe_nonzero_lh | mustbe_nonzero_rh;
4024 845035 : wide_int new_ub = maybe_nonzero_lh | maybe_nonzero_rh;
4025 845035 : signop sign = TYPE_SIGN (type);
4026 : // If the input ranges contain only positive values we can
4027 : // truncate the minimum of the result range to the maximum
4028 : // of the input range minima.
4029 845035 : if (wi::ge_p (lh_lb, 0, sign)
4030 845035 : && wi::ge_p (rh_lb, 0, sign))
4031 : {
4032 633038 : new_lb = wi::max (new_lb, lh_lb, sign);
4033 633038 : new_lb = wi::max (new_lb, rh_lb, sign);
4034 : }
4035 : // If either input range contains only negative values
4036 : // we can truncate the minimum of the result range to the
4037 : // respective minimum range.
4038 845035 : if (wi::lt_p (lh_ub, 0, sign))
4039 20028 : new_lb = wi::max (new_lb, lh_lb, sign);
4040 845035 : if (wi::lt_p (rh_ub, 0, sign))
4041 9503 : new_lb = wi::max (new_lb, rh_lb, sign);
4042 : // If the limits got swapped around, return a conservative range.
4043 845035 : if (wi::gt_p (new_lb, new_ub, sign))
4044 : {
4045 : // Make sure that nonzero|X is nonzero.
4046 183281 : if (wi::gt_p (lh_lb, 0, sign)
4047 178898 : || wi::gt_p (rh_lb, 0, sign)
4048 121755 : || wi::lt_p (lh_ub, 0, sign)
4049 305036 : || wi::lt_p (rh_ub, 0, sign))
4050 61526 : r.set_nonzero (type);
4051 121755 : else if (sign == SIGNED
4052 121755 : && wi_optimize_signed_bitwise_op (r, type,
4053 : lh_lb, lh_ub,
4054 : rh_lb, rh_ub))
4055 : return;
4056 : else
4057 119407 : r.set_varying (type);
4058 180933 : return;
4059 : }
4060 661754 : value_range_with_overflow (r, type, new_lb, new_ub);
4061 845065 : }
4062 :
4063 : bool
4064 620919 : operator_bitwise_or::op1_range (irange &r, tree type,
4065 : const irange &lhs,
4066 : const irange &op2,
4067 : relation_trio) const
4068 : {
4069 620919 : if (lhs.undefined_p ())
4070 : return false;
4071 : // If this is really a logical wi_fold, call that.
4072 620919 : if (types_compatible_p (type, boolean_type_node))
4073 365984 : return op_logical_or.op1_range (r, type, lhs, op2);
4074 :
4075 254935 : if (lhs.zero_p ())
4076 : {
4077 79098 : r.set_zero (type);
4078 79098 : return true;
4079 : }
4080 :
4081 : // if (A < 0 && B < 0)
4082 : // Sometimes gets translated to
4083 : // _1 = A | B
4084 : // if (_1 < 0))
4085 : // It is useful for ranger to recognize a positive LHS means the RHS
4086 : // operands are also positive when dealing with the ELSE range..
4087 246390 : if (TYPE_SIGN (type) == SIGNED && wi::ge_p (lhs.lower_bound (), 0, SIGNED))
4088 : {
4089 28280 : unsigned prec = TYPE_PRECISION (type);
4090 28280 : r.set (type, wi::zero (prec), wi::max_value (prec, SIGNED));
4091 28280 : return true;
4092 : }
4093 147557 : r.set_varying (type);
4094 147557 : return true;
4095 : }
4096 :
4097 : bool
4098 307440 : operator_bitwise_or::op2_range (irange &r, tree type,
4099 : const irange &lhs,
4100 : const irange &op1,
4101 : relation_trio) const
4102 : {
4103 307440 : return operator_bitwise_or::op1_range (r, type, lhs, op1);
4104 : }
4105 :
4106 : void
4107 88784 : operator_bitwise_xor::update_bitmask (irange &r, const irange &lh,
4108 : const irange &rh) const
4109 : {
4110 88784 : update_known_bitmask (r, BIT_XOR_EXPR, lh, rh);
4111 88784 : }
4112 :
4113 : bool
4114 300031 : operator_bitwise_xor::fold_range (irange &r, tree type,
4115 : const irange &lh, const irange &rh,
4116 : relation_trio rel) const
4117 : {
4118 : // Handle X ^ UNDEFINED = UNDEFINED.
4119 300031 : if (lh.undefined_p () || rh.undefined_p ())
4120 : {
4121 392 : r.set_undefined ();
4122 392 : return true;
4123 : }
4124 :
4125 : // Next, handle X ^ X == [0, 0].
4126 299639 : if (rel.op1_op2 () == VREL_EQ)
4127 : {
4128 74 : r.set_zero (type);
4129 74 : return true;
4130 : }
4131 :
4132 : // If either operand is VARYING, the result is VARYING.
4133 299565 : if (lh.varying_p () || rh.varying_p ())
4134 : {
4135 : // If the operands are not equal, zero is not possible.
4136 208732 : if (rel.op1_op2 () != VREL_NE)
4137 207640 : r.set_varying (type);
4138 : else
4139 1092 : r.set_nonzero (type);
4140 208732 : return true;
4141 : }
4142 :
4143 : // Now deal with X ^ 0 == X.
4144 90833 : if (lh.zero_p ())
4145 : {
4146 1528 : r = rh;
4147 1528 : return true;
4148 : }
4149 89305 : if (rh.zero_p ())
4150 : {
4151 521 : r = lh;
4152 521 : return true;
4153 : }
4154 :
4155 : // Start with the legacy range. This can sometimes pick up values
4156 : // when there are a lot of subranges and fold_range aggregates them.
4157 88784 : bool res = range_operator::fold_range (r, type, lh, rh, rel);
4158 :
4159 : // Calculate the XOR identity : x ^ y = (x | y) & ~(x & y)
4160 : // AND and OR are already much better optimized.
4161 88784 : int_range_max tmp1, tmp2, tmp3, new_result;
4162 88784 : int_range<2> varying;
4163 88784 : varying.set_varying (type);
4164 :
4165 88784 : if (m_or.fold_range (tmp1, type, lh, rh, rel)
4166 88784 : && m_and.fold_range (tmp2, type, lh, rh, rel)
4167 88784 : && m_not.fold_range (tmp3, type, tmp2, varying, rel)
4168 177568 : && m_and.fold_range (new_result, type, tmp1, tmp3, rel))
4169 : {
4170 : // If the operands are not equal, or the LH does not contain any
4171 : // element of the RH, zero is not possible.
4172 88784 : tmp1 = lh;
4173 88784 : if (rel.op1_op2 () == VREL_NE
4174 88784 : || (tmp1.intersect (rh) && tmp1.undefined_p ()))
4175 : {
4176 32841 : tmp1.set_nonzero (type);
4177 32841 : new_result.intersect (tmp1);
4178 : }
4179 :
4180 : // Combine with the legacy range if there was one.
4181 88784 : if (res)
4182 88784 : r.intersect (new_result);
4183 : else
4184 0 : r = new_result;
4185 88784 : return true;
4186 : }
4187 : return res;
4188 88784 : }
4189 :
4190 : void
4191 174490 : operator_bitwise_xor::wi_fold (irange &r, tree type,
4192 : const wide_int &lh_lb,
4193 : const wide_int &lh_ub,
4194 : const wide_int &rh_lb,
4195 : const wide_int &rh_ub) const
4196 : {
4197 174490 : signop sign = TYPE_SIGN (type);
4198 174490 : wide_int maybe_nonzero_lh, mustbe_nonzero_lh;
4199 174490 : wide_int maybe_nonzero_rh, mustbe_nonzero_rh;
4200 174490 : wi_set_zero_nonzero_bits (type, lh_lb, lh_ub,
4201 : maybe_nonzero_lh, mustbe_nonzero_lh);
4202 174490 : wi_set_zero_nonzero_bits (type, rh_lb, rh_ub,
4203 : maybe_nonzero_rh, mustbe_nonzero_rh);
4204 :
4205 523470 : wide_int result_zero_bits = ((mustbe_nonzero_lh & mustbe_nonzero_rh)
4206 523470 : | ~(maybe_nonzero_lh | maybe_nonzero_rh));
4207 174490 : wide_int result_one_bits
4208 348980 : = (wi::bit_and_not (mustbe_nonzero_lh, maybe_nonzero_rh)
4209 348980 : | wi::bit_and_not (mustbe_nonzero_rh, maybe_nonzero_lh));
4210 174490 : wide_int new_ub = ~result_zero_bits;
4211 174490 : wide_int new_lb = result_one_bits;
4212 :
4213 : // If the range has all positive or all negative values, the result
4214 : // is better than VARYING.
4215 174490 : if (wi::lt_p (new_lb, 0, sign) || wi::ge_p (new_ub, 0, sign))
4216 167169 : value_range_with_overflow (r, type, new_lb, new_ub);
4217 7321 : else if (sign == SIGNED
4218 7321 : && wi_optimize_signed_bitwise_op (r, type,
4219 : lh_lb, lh_ub,
4220 : rh_lb, rh_ub))
4221 : ; /* Do nothing. */
4222 : else
4223 1059 : r.set_varying (type);
4224 :
4225 : /* Furthermore, XOR is non-zero if its arguments can't be equal. */
4226 174490 : if (wi::lt_p (lh_ub, rh_lb, sign)
4227 113315 : || wi::lt_p (rh_ub, lh_lb, sign)
4228 267015 : || wi::ne_p (result_one_bits, 0))
4229 : {
4230 81965 : int_range<2> tmp;
4231 81965 : tmp.set_nonzero (type);
4232 81965 : r.intersect (tmp);
4233 81965 : }
4234 174490 : }
4235 :
4236 : bool
4237 88784 : operator_bitwise_xor::op1_op2_relation_effect (irange &lhs_range,
4238 : tree type,
4239 : const irange &,
4240 : const irange &,
4241 : relation_kind rel) const
4242 : {
4243 88784 : if (rel == VREL_VARYING)
4244 : return false;
4245 :
4246 3592 : int_range<2> rel_range;
4247 :
4248 3592 : switch (rel)
4249 : {
4250 0 : case VREL_EQ:
4251 0 : rel_range.set_zero (type);
4252 0 : break;
4253 488 : case VREL_NE:
4254 488 : rel_range.set_nonzero (type);
4255 488 : break;
4256 : default:
4257 : return false;
4258 : }
4259 :
4260 488 : lhs_range.intersect (rel_range);
4261 488 : return true;
4262 3592 : }
4263 :
4264 : bool
4265 89945 : operator_bitwise_xor::op1_range (irange &r, tree type,
4266 : const irange &lhs,
4267 : const irange &op2,
4268 : relation_trio) const
4269 : {
4270 89945 : if (lhs.undefined_p () || lhs.varying_p ())
4271 : {
4272 7532 : r = lhs;
4273 7532 : return true;
4274 : }
4275 82413 : if (types_compatible_p (type, boolean_type_node))
4276 : {
4277 1802 : switch (get_bool_state (r, lhs, type))
4278 : {
4279 801 : case BRS_TRUE:
4280 801 : if (op2.varying_p ())
4281 769 : r.set_varying (type);
4282 32 : else if (op2.zero_p ())
4283 24 : r = range_true (type);
4284 : // See get_bool_state for the rationale
4285 8 : else if (op2.undefined_p () || contains_zero_p (op2))
4286 0 : r = range_true_and_false (type);
4287 : else
4288 8 : r = range_false (type);
4289 : break;
4290 1001 : case BRS_FALSE:
4291 1001 : r = op2;
4292 1001 : break;
4293 : default:
4294 : break;
4295 : }
4296 1802 : return true;
4297 : }
4298 80611 : r.set_varying (type);
4299 80611 : return true;
4300 : }
4301 :
4302 : bool
4303 37464 : operator_bitwise_xor::op2_range (irange &r, tree type,
4304 : const irange &lhs,
4305 : const irange &op1,
4306 : relation_trio) const
4307 : {
4308 37464 : return operator_bitwise_xor::op1_range (r, type, lhs, op1);
4309 : }
4310 :
4311 : class operator_trunc_mod : public range_operator
4312 : {
4313 : using range_operator::op1_range;
4314 : using range_operator::op2_range;
4315 : using range_operator::update_bitmask;
4316 : public:
4317 : virtual void wi_fold (irange &r, tree type,
4318 : const wide_int &lh_lb,
4319 : const wide_int &lh_ub,
4320 : const wide_int &rh_lb,
4321 : const wide_int &rh_ub) const;
4322 : virtual bool op1_range (irange &r, tree type,
4323 : const irange &lhs,
4324 : const irange &op2,
4325 : relation_trio) const;
4326 : virtual bool op2_range (irange &r, tree type,
4327 : const irange &lhs,
4328 : const irange &op1,
4329 : relation_trio) const;
4330 1143385 : void update_bitmask (irange &r, const irange &lh, const irange &rh) const
4331 1143385 : { update_known_bitmask (r, TRUNC_MOD_EXPR, lh, rh); }
4332 : } op_trunc_mod;
4333 :
4334 : void
4335 1412760 : operator_trunc_mod::wi_fold (irange &r, tree type,
4336 : const wide_int &lh_lb,
4337 : const wide_int &lh_ub,
4338 : const wide_int &rh_lb,
4339 : const wide_int &rh_ub) const
4340 : {
4341 1412760 : wide_int new_lb, new_ub, tmp;
4342 1412760 : signop sign = TYPE_SIGN (type);
4343 1412760 : unsigned prec = TYPE_PRECISION (type);
4344 :
4345 : // Mod 0 is undefined.
4346 1412760 : if (wi_zero_p (type, rh_lb, rh_ub))
4347 : {
4348 10124 : r.set_undefined ();
4349 10124 : return;
4350 : }
4351 :
4352 : // Check for constant and try to fold.
4353 1626060 : if (lh_lb == lh_ub && rh_lb == rh_ub)
4354 : {
4355 21145 : wi::overflow_type ov = wi::OVF_NONE;
4356 21145 : tmp = wi::mod_trunc (lh_lb, rh_lb, sign, &ov);
4357 21145 : if (ov == wi::OVF_NONE)
4358 : {
4359 21119 : r = int_range<2> (type, tmp, tmp);
4360 21119 : return;
4361 : }
4362 : }
4363 :
4364 : // ABS (A % B) < ABS (B) and either 0 <= A % B <= A or A <= A % B <= 0.
4365 1381517 : new_ub = rh_ub - 1;
4366 1381517 : if (sign == SIGNED)
4367 : {
4368 617042 : tmp = -1 - rh_lb;
4369 617042 : new_ub = wi::smax (new_ub, tmp);
4370 : }
4371 :
4372 1381517 : if (sign == UNSIGNED)
4373 764475 : new_lb = wi::zero (prec);
4374 : else
4375 : {
4376 617042 : new_lb = -new_ub;
4377 617042 : tmp = lh_lb;
4378 617042 : if (wi::gts_p (tmp, 0))
4379 143700 : tmp = wi::zero (prec);
4380 617084 : new_lb = wi::smax (new_lb, tmp);
4381 : }
4382 1381517 : tmp = lh_ub;
4383 1381517 : if (sign == SIGNED && wi::neg_p (tmp))
4384 33214 : tmp = wi::zero (prec);
4385 1381517 : new_ub = wi::min (new_ub, tmp, sign);
4386 :
4387 1381517 : value_range_with_overflow (r, type, new_lb, new_ub);
4388 :
4389 : // When all positive and all X/Y combinations produce the same quotient
4390 : // we can refine the result with X % Y == X - Q * Y.
4391 : // Ensure that division by 0 is not an option.
4392 1381517 : if (wi::gt_p (rh_lb, 0, sign) && wi::ge_p (lh_lb, 0, sign))
4393 : {
4394 334740 : wide_int q_lb = wi::div_trunc (lh_lb, rh_ub, sign);
4395 334740 : wide_int q_ub = wi::div_trunc (lh_ub, rh_lb, sign);
4396 :
4397 334740 : if (q_lb == q_ub)
4398 : {
4399 42417 : new_lb = lh_lb - q_lb * rh_ub;
4400 42417 : new_ub = lh_ub - q_lb * rh_lb;
4401 :
4402 42417 : int_range<2> refined (type, new_lb, new_ub);
4403 42417 : r.intersect (refined);
4404 42417 : }
4405 334784 : }
4406 1413076 : }
4407 :
4408 : bool
4409 520549 : operator_trunc_mod::op1_range (irange &r, tree type,
4410 : const irange &lhs,
4411 : const irange &,
4412 : relation_trio) const
4413 : {
4414 520549 : if (lhs.undefined_p ())
4415 : return false;
4416 : // PR 91029.
4417 520549 : signop sign = TYPE_SIGN (type);
4418 520549 : unsigned prec = TYPE_PRECISION (type);
4419 : // (a % b) >= x && x > 0 , then a >= x.
4420 520639 : if (wi::gt_p (lhs.lower_bound (), 0, sign))
4421 : {
4422 133881 : r.set (type, lhs.lower_bound (), wi::max_value (prec, sign));
4423 133848 : return true;
4424 : }
4425 : // (a % b) <= x && x < 0 , then a <= x.
4426 386758 : if (wi::lt_p (lhs.upper_bound (), 0, sign))
4427 : {
4428 8401 : r.set (type, wi::min_value (prec, sign), lhs.upper_bound ());
4429 8401 : return true;
4430 : }
4431 : return false;
4432 : }
4433 :
4434 : bool
4435 329532 : operator_trunc_mod::op2_range (irange &r, tree type,
4436 : const irange &lhs,
4437 : const irange &,
4438 : relation_trio) const
4439 : {
4440 329532 : if (lhs.undefined_p ())
4441 : return false;
4442 : // PR 91029.
4443 329532 : signop sign = TYPE_SIGN (type);
4444 329532 : unsigned prec = TYPE_PRECISION (type);
4445 : // (a % b) >= x && x > 0 , then b is in ~[-x, x] for signed
4446 : // or b > x for unsigned.
4447 329563 : if (wi::gt_p (lhs.lower_bound (), 0, sign))
4448 : {
4449 53447 : if (sign == SIGNED)
4450 1951 : r.set (type, wi::neg (lhs.lower_bound ()),
4451 3902 : lhs.lower_bound (), VR_ANTI_RANGE);
4452 51508 : else if (wi::lt_p (lhs.lower_bound (), wi::max_value (prec, sign),
4453 : sign))
4454 51514 : r.set (type, lhs.lower_bound () + 1, wi::max_value (prec, sign));
4455 : else
4456 : return false;
4457 53447 : return true;
4458 : }
4459 : // (a % b) <= x && x < 0 , then b is in ~[x, -x].
4460 276110 : if (wi::lt_p (lhs.upper_bound (), 0, sign))
4461 : {
4462 5278 : if (wi::gt_p (lhs.upper_bound (), wi::min_value (prec, sign), sign))
4463 5278 : r.set (type, lhs.upper_bound (),
4464 10556 : wi::neg (lhs.upper_bound ()), VR_ANTI_RANGE);
4465 : else
4466 : return false;
4467 5278 : return true;
4468 : }
4469 : return false;
4470 : }
4471 :
4472 :
4473 : class operator_logical_not : public range_operator
4474 : {
4475 : using range_operator::fold_range;
4476 : using range_operator::op1_range;
4477 : public:
4478 : bool fold_range (irange &r, tree type,
4479 : const irange &lh,
4480 : const irange &rh,
4481 : relation_trio rel = TRIO_VARYING) const final override;
4482 : bool op1_range (irange &r, tree type,
4483 : const irange &lhs,
4484 : const irange &op2,
4485 : relation_trio rel = TRIO_VARYING) const final override;
4486 : // Check compatibility of LHS and op1.
4487 0 : bool operand_check_p (tree t1, tree t2, tree) const final override
4488 0 : { return range_compatible_p (t1, t2); }
4489 : } op_logical_not;
4490 :
4491 : // Folding a logical NOT, oddly enough, involves doing nothing on the
4492 : // forward pass through. During the initial walk backwards, the
4493 : // logical NOT reversed the desired outcome on the way back, so on the
4494 : // way forward all we do is pass the range forward.
4495 : //
4496 : // b_2 = x_1 < 20
4497 : // b_3 = !b_2
4498 : // if (b_3)
4499 : // to determine the TRUE branch, walking backward
4500 : // if (b_3) if ([1,1])
4501 : // b_3 = !b_2 [1,1] = ![0,0]
4502 : // b_2 = x_1 < 20 [0,0] = x_1 < 20, false, so x_1 == [20, 255]
4503 : // which is the result we are looking for.. so.. pass it through.
4504 :
4505 : bool
4506 245220 : operator_logical_not::fold_range (irange &r, tree type,
4507 : const irange &lh,
4508 : const irange &rh ATTRIBUTE_UNUSED,
4509 : relation_trio) const
4510 : {
4511 245220 : if (empty_range_varying (r, type, lh, rh))
4512 0 : return true;
4513 :
4514 245220 : r = lh;
4515 245220 : if (!lh.varying_p () && !lh.undefined_p ())
4516 53747 : r.invert ();
4517 :
4518 : return true;
4519 : }
4520 :
4521 : bool
4522 29491 : operator_logical_not::op1_range (irange &r,
4523 : tree type,
4524 : const irange &lhs,
4525 : const irange &op2,
4526 : relation_trio) const
4527 : {
4528 : // Logical NOT is involutary...do it again.
4529 29491 : return fold_range (r, type, lhs, op2);
4530 : }
4531 :
4532 : bool
4533 621670 : operator_bitwise_not::fold_range (irange &r, tree type,
4534 : const irange &lh,
4535 : const irange &rh,
4536 : relation_trio) const
4537 : {
4538 621670 : if (empty_range_varying (r, type, lh, rh))
4539 105 : return true;
4540 :
4541 621565 : if (types_compatible_p (type, boolean_type_node))
4542 215729 : return op_logical_not.fold_range (r, type, lh, rh);
4543 :
4544 : // ~X is simply -1 - X.
4545 811672 : int_range<1> minusone (type, wi::minus_one (TYPE_PRECISION (type)),
4546 811672 : wi::minus_one (TYPE_PRECISION (type)));
4547 405836 : return range_op_handler (MINUS_EXPR).fold_range (r, type, minusone, lh);
4548 405836 : }
4549 :
4550 : bool
4551 53673 : operator_bitwise_not::op1_range (irange &r, tree type,
4552 : const irange &lhs,
4553 : const irange &op2,
4554 : relation_trio) const
4555 : {
4556 53673 : if (lhs.undefined_p ())
4557 : return false;
4558 53673 : if (types_compatible_p (type, boolean_type_node))
4559 29491 : return op_logical_not.op1_range (r, type, lhs, op2);
4560 :
4561 : // ~X is -1 - X and since bitwise NOT is involutary...do it again.
4562 24182 : return fold_range (r, type, lhs, op2);
4563 : }
4564 :
4565 : void
4566 0 : operator_bitwise_not::update_bitmask (irange &r, const irange &lh,
4567 : const irange &rh) const
4568 : {
4569 0 : update_known_bitmask (r, BIT_NOT_EXPR, lh, rh);
4570 0 : }
4571 :
4572 :
4573 : bool
4574 269434 : operator_cst::fold_range (irange &r, tree type ATTRIBUTE_UNUSED,
4575 : const irange &lh,
4576 : const irange &rh ATTRIBUTE_UNUSED,
4577 : relation_trio) const
4578 : {
4579 269434 : r = lh;
4580 269434 : return true;
4581 : }
4582 :
4583 :
4584 : // Determine if there is a relationship between LHS and OP1.
4585 :
4586 : relation_kind
4587 912034 : operator_identity::lhs_op1_relation (const irange &lhs,
4588 : const irange &op1 ATTRIBUTE_UNUSED,
4589 : const irange &op2 ATTRIBUTE_UNUSED,
4590 : relation_kind) const
4591 : {
4592 912034 : if (lhs.undefined_p ())
4593 597 : return VREL_VARYING;
4594 : // Simply a copy, so they are equivalent.
4595 : return VREL_EQ;
4596 : }
4597 :
4598 : bool
4599 912763 : operator_identity::fold_range (irange &r, tree type ATTRIBUTE_UNUSED,
4600 : const irange &lh,
4601 : const irange &rh ATTRIBUTE_UNUSED,
4602 : relation_trio) const
4603 : {
4604 912763 : r = lh;
4605 912763 : return true;
4606 : }
4607 :
4608 : bool
4609 295961 : operator_identity::op1_range (irange &r, tree type ATTRIBUTE_UNUSED,
4610 : const irange &lhs,
4611 : const irange &op2 ATTRIBUTE_UNUSED,
4612 : relation_trio) const
4613 : {
4614 295961 : r = lhs;
4615 295961 : return true;
4616 : }
4617 :
4618 :
4619 : class operator_unknown : public range_operator
4620 : {
4621 : using range_operator::fold_range;
4622 : public:
4623 : virtual bool fold_range (irange &r, tree type,
4624 : const irange &op1,
4625 : const irange &op2,
4626 : relation_trio rel = TRIO_VARYING) const;
4627 : } op_unknown;
4628 :
4629 : bool
4630 1335152 : operator_unknown::fold_range (irange &r, tree type,
4631 : const irange &lh ATTRIBUTE_UNUSED,
4632 : const irange &rh ATTRIBUTE_UNUSED,
4633 : relation_trio) const
4634 : {
4635 1335152 : r.set_varying (type);
4636 1335152 : return true;
4637 : }
4638 :
4639 :
4640 : void
4641 115005 : operator_abs::wi_fold (irange &r, tree type,
4642 : const wide_int &lh_lb, const wide_int &lh_ub,
4643 : const wide_int &rh_lb ATTRIBUTE_UNUSED,
4644 : const wide_int &rh_ub ATTRIBUTE_UNUSED) const
4645 : {
4646 115005 : wide_int min, max;
4647 115005 : signop sign = TYPE_SIGN (type);
4648 115005 : unsigned prec = TYPE_PRECISION (type);
4649 :
4650 : // Pass through LH for the easy cases.
4651 115005 : if (sign == UNSIGNED || wi::ge_p (lh_lb, 0, sign))
4652 : {
4653 11936 : r = int_range<1> (type, lh_lb, lh_ub);
4654 11936 : return;
4655 : }
4656 :
4657 : // -TYPE_MIN_VALUE = TYPE_MIN_VALUE with flag_wrapv so we can't get
4658 : // a useful range.
4659 103069 : wide_int min_value = wi::min_value (prec, sign);
4660 103069 : wide_int max_value = wi::max_value (prec, sign);
4661 103069 : if (!TYPE_OVERFLOW_UNDEFINED (type) && wi::eq_p (lh_lb, min_value))
4662 : {
4663 640 : r.set_varying (type);
4664 640 : return;
4665 : }
4666 :
4667 : // ABS_EXPR may flip the range around, if the original range
4668 : // included negative values.
4669 102429 : if (wi::eq_p (lh_lb, min_value))
4670 : {
4671 : // ABS ([-MIN, -MIN]) isn't representable, but we have traditionally
4672 : // returned [-MIN,-MIN] so this preserves that behavior. PR37078
4673 35340 : if (wi::eq_p (lh_ub, min_value))
4674 : {
4675 104 : r = int_range<1> (type, min_value, min_value);
4676 104 : return;
4677 : }
4678 35236 : min = max_value;
4679 : }
4680 : else
4681 67089 : min = wi::abs (lh_lb);
4682 :
4683 102325 : if (wi::eq_p (lh_ub, min_value))
4684 0 : max = max_value;
4685 : else
4686 102325 : max = wi::abs (lh_ub);
4687 :
4688 : // If the range contains zero then we know that the minimum value in the
4689 : // range will be zero.
4690 102325 : if (wi::le_p (lh_lb, 0, sign) && wi::ge_p (lh_ub, 0, sign))
4691 : {
4692 92691 : if (wi::gt_p (min, max, sign))
4693 55018 : max = min;
4694 92691 : min = wi::zero (prec);
4695 : }
4696 : else
4697 : {
4698 : // If the range was reversed, swap MIN and MAX.
4699 9634 : if (wi::gt_p (min, max, sign))
4700 9027 : std::swap (min, max);
4701 : }
4702 :
4703 : // If the new range has its limits swapped around (MIN > MAX), then
4704 : // the operation caused one of them to wrap around. The only thing
4705 : // we know is that the result is positive.
4706 102325 : if (wi::gt_p (min, max, sign))
4707 : {
4708 0 : min = wi::zero (prec);
4709 0 : max = max_value;
4710 : }
4711 102325 : r = int_range<1> (type, min, max);
4712 115749 : }
4713 :
4714 : bool
4715 98518 : operator_abs::op1_range (irange &r, tree type,
4716 : const irange &lhs,
4717 : const irange &op2,
4718 : relation_trio) const
4719 : {
4720 98518 : if (empty_range_varying (r, type, lhs, op2))
4721 0 : return true;
4722 98518 : if (TYPE_UNSIGNED (type))
4723 : {
4724 0 : r = lhs;
4725 0 : return true;
4726 : }
4727 : // Start with the positives because negatives are an impossible result.
4728 98518 : int_range_max positives = range_positives (type);
4729 98518 : positives.intersect (lhs);
4730 98518 : r = positives;
4731 : // Then add the negative of each pair:
4732 : // ABS(op1) = [5,20] would yield op1 => [-20,-5][5,20].
4733 197837 : for (unsigned i = 0; i < positives.num_pairs (); ++i)
4734 99319 : r.union_ (int_range<1> (type,
4735 198638 : -positives.upper_bound (i),
4736 297957 : -positives.lower_bound (i)));
4737 : // With flag_wrapv, -TYPE_MIN_VALUE = TYPE_MIN_VALUE which is
4738 : // unrepresentable. Add -TYPE_MIN_VALUE in this case.
4739 98518 : wide_int min_value = wi::min_value (TYPE_PRECISION (type), TYPE_SIGN (type));
4740 98518 : wide_int lb = lhs.lower_bound ();
4741 98518 : if (!TYPE_OVERFLOW_UNDEFINED (type) && wi::eq_p (lb, min_value))
4742 168 : r.union_ (int_range<2> (type, lb, lb));
4743 98518 : return true;
4744 98518 : }
4745 :
4746 : void
4747 108001 : operator_abs::update_bitmask (irange &r, const irange &lh,
4748 : const irange &rh) const
4749 : {
4750 108001 : update_known_bitmask (r, ABS_EXPR, lh, rh);
4751 108001 : }
4752 :
4753 : class operator_absu : public range_operator
4754 : {
4755 : using range_operator::update_bitmask;
4756 : public:
4757 : virtual void wi_fold (irange &r, tree type,
4758 : const wide_int &lh_lb, const wide_int &lh_ub,
4759 : const wide_int &rh_lb, const wide_int &rh_ub)
4760 : const final override;
4761 : virtual void update_bitmask (irange &r, const irange &lh,
4762 : const irange &rh) const final override;
4763 : } op_absu;
4764 :
4765 : void
4766 10984 : operator_absu::wi_fold (irange &r, tree type,
4767 : const wide_int &lh_lb, const wide_int &lh_ub,
4768 : const wide_int &rh_lb ATTRIBUTE_UNUSED,
4769 : const wide_int &rh_ub ATTRIBUTE_UNUSED) const
4770 : {
4771 10984 : wide_int new_lb, new_ub;
4772 :
4773 : // Pass through VR0 the easy cases.
4774 10984 : if (wi::ges_p (lh_lb, 0))
4775 : {
4776 1445 : new_lb = lh_lb;
4777 1445 : new_ub = lh_ub;
4778 : }
4779 : else
4780 : {
4781 9539 : new_lb = wi::abs (lh_lb);
4782 9539 : new_ub = wi::abs (lh_ub);
4783 :
4784 : // If the range contains zero then we know that the minimum
4785 : // value in the range will be zero.
4786 9539 : if (wi::ges_p (lh_ub, 0))
4787 : {
4788 8093 : if (wi::gtu_p (new_lb, new_ub))
4789 6850 : new_ub = new_lb;
4790 8093 : new_lb = wi::zero (TYPE_PRECISION (type));
4791 : }
4792 : else
4793 1446 : std::swap (new_lb, new_ub);
4794 : }
4795 :
4796 10984 : gcc_checking_assert (TYPE_UNSIGNED (type));
4797 10984 : r = int_range<1> (type, new_lb, new_ub);
4798 10984 : }
4799 :
4800 : void
4801 10461 : operator_absu::update_bitmask (irange &r, const irange &lh,
4802 : const irange &rh) const
4803 : {
4804 10461 : update_known_bitmask (r, ABSU_EXPR, lh, rh);
4805 10461 : }
4806 :
4807 :
4808 : bool
4809 553109 : operator_negate::fold_range (irange &r, tree type,
4810 : const irange &lh,
4811 : const irange &rh,
4812 : relation_trio) const
4813 : {
4814 553109 : if (empty_range_varying (r, type, lh, rh))
4815 887 : return true;
4816 :
4817 : // -X is simply 0 - X.
4818 552222 : int_range<1> zero;
4819 552222 : zero.set_zero (type);
4820 552222 : return range_op_handler (MINUS_EXPR).fold_range (r, type, zero, lh);
4821 552222 : }
4822 :
4823 : bool
4824 74228 : operator_negate::op1_range (irange &r, tree type,
4825 : const irange &lhs,
4826 : const irange &op2,
4827 : relation_trio) const
4828 : {
4829 : // NEGATE is involutory.
4830 74228 : return fold_range (r, type, lhs, op2);
4831 : }
4832 :
4833 :
4834 : bool
4835 0 : operator_addr_expr::fold_range (irange &r, tree type,
4836 : const irange &lh,
4837 : const irange &rh,
4838 : relation_trio) const
4839 : {
4840 0 : if (empty_range_varying (r, type, lh, rh))
4841 0 : return true;
4842 :
4843 : // Return a non-null pointer of the LHS type (passed in op2).
4844 0 : if (lh.zero_p ())
4845 0 : r.set_zero (type);
4846 0 : else if (lh.undefined_p () || contains_zero_p (lh))
4847 0 : r.set_varying (type);
4848 : else
4849 0 : r.set_nonzero (type);
4850 : return true;
4851 : }
4852 :
4853 : bool
4854 0 : operator_addr_expr::op1_range (irange &r, tree type,
4855 : const irange &lhs,
4856 : const irange &op2,
4857 : relation_trio) const
4858 : {
4859 0 : if (empty_range_varying (r, type, lhs, op2))
4860 0 : return true;
4861 :
4862 : // Return a non-null pointer of the LHS type (passed in op2), but only
4863 : // if we cant overflow, eitherwise a no-zero offset could wrap to zero.
4864 : // See PR 111009.
4865 0 : if (!lhs.undefined_p () && !contains_zero_p (lhs) && TYPE_OVERFLOW_UNDEFINED (type))
4866 0 : r.set_nonzero (type);
4867 : else
4868 0 : r.set_varying (type);
4869 : return true;
4870 : }
4871 :
4872 : // Initialize any integral operators to the primary table
4873 :
4874 : void
4875 292658 : range_op_table::initialize_integral_ops ()
4876 : {
4877 292658 : set (TRUNC_DIV_EXPR, op_trunc_div);
4878 292658 : set (FLOOR_DIV_EXPR, op_floor_div);
4879 292658 : set (ROUND_DIV_EXPR, op_round_div);
4880 292658 : set (CEIL_DIV_EXPR, op_ceil_div);
4881 292658 : set (EXACT_DIV_EXPR, op_exact_div);
4882 292658 : set (LSHIFT_EXPR, op_lshift);
4883 292658 : set (RSHIFT_EXPR, op_rshift);
4884 292658 : set (TRUTH_AND_EXPR, op_logical_and);
4885 292658 : set (TRUTH_OR_EXPR, op_logical_or);
4886 292658 : set (TRUNC_MOD_EXPR, op_trunc_mod);
4887 292658 : set (TRUTH_NOT_EXPR, op_logical_not);
4888 292658 : set (IMAGPART_EXPR, op_unknown);
4889 292658 : set (REALPART_EXPR, op_unknown);
4890 292658 : set (ABSU_EXPR, op_absu);
4891 292658 : set (OP_WIDEN_MULT_SIGNED, op_widen_mult_signed);
4892 292658 : set (OP_WIDEN_MULT_UNSIGNED, op_widen_mult_unsigned);
4893 292658 : set (OP_WIDEN_MULT_SIGNED_UNSIGNED, op_widen_mult_signed_unsigned);
4894 292658 : set (OP_WIDEN_PLUS_SIGNED, op_widen_plus_signed);
4895 292658 : set (OP_WIDEN_PLUS_UNSIGNED, op_widen_plus_unsigned);
4896 :
4897 292658 : }
4898 :
4899 : bool
4900 41593 : operator_plus::overflow_free_p (const irange &lh, const irange &rh,
4901 : relation_trio) const
4902 : {
4903 41593 : if (lh.undefined_p () || rh.undefined_p ())
4904 : return false;
4905 :
4906 41593 : tree type = lh.type ();
4907 41593 : if (TYPE_OVERFLOW_UNDEFINED (type))
4908 : return true;
4909 :
4910 10783 : wi::overflow_type ovf;
4911 10783 : signop sgn = TYPE_SIGN (type);
4912 10783 : wide_int wmax0 = lh.upper_bound ();
4913 10783 : wide_int wmax1 = rh.upper_bound ();
4914 10783 : wi::add (wmax0, wmax1, sgn, &ovf);
4915 10783 : if (ovf != wi::OVF_NONE)
4916 : return false;
4917 :
4918 1290 : if (TYPE_UNSIGNED (type))
4919 : return true;
4920 :
4921 372 : wide_int wmin0 = lh.lower_bound ();
4922 372 : wide_int wmin1 = rh.lower_bound ();
4923 372 : wi::add (wmin0, wmin1, sgn, &ovf);
4924 372 : if (ovf != wi::OVF_NONE)
4925 261 : return false;
4926 :
4927 : return true;
4928 11155 : }
4929 :
4930 : bool
4931 31 : operator_minus::overflow_free_p (const irange &lh, const irange &rh,
4932 : relation_trio) const
4933 : {
4934 31 : if (lh.undefined_p () || rh.undefined_p ())
4935 : return false;
4936 :
4937 31 : tree type = lh.type ();
4938 31 : if (TYPE_OVERFLOW_UNDEFINED (type))
4939 : return true;
4940 :
4941 10 : wi::overflow_type ovf;
4942 10 : signop sgn = TYPE_SIGN (type);
4943 10 : wide_int wmin0 = lh.lower_bound ();
4944 10 : wide_int wmax1 = rh.upper_bound ();
4945 10 : wi::sub (wmin0, wmax1, sgn, &ovf);
4946 10 : if (ovf != wi::OVF_NONE)
4947 : return false;
4948 :
4949 7 : if (TYPE_UNSIGNED (type))
4950 : return true;
4951 :
4952 6 : wide_int wmax0 = lh.upper_bound ();
4953 6 : wide_int wmin1 = rh.lower_bound ();
4954 6 : wi::sub (wmax0, wmin1, sgn, &ovf);
4955 6 : if (ovf != wi::OVF_NONE)
4956 0 : return false;
4957 :
4958 : return true;
4959 16 : }
4960 :
4961 : bool
4962 3260 : operator_mult::overflow_free_p (const irange &lh, const irange &rh,
4963 : relation_trio) const
4964 : {
4965 3260 : if (lh.undefined_p () || rh.undefined_p ())
4966 : return false;
4967 :
4968 3260 : tree type = lh.type ();
4969 3260 : if (TYPE_OVERFLOW_UNDEFINED (type))
4970 : return true;
4971 :
4972 2778 : wi::overflow_type ovf;
4973 2778 : signop sgn = TYPE_SIGN (type);
4974 2778 : wide_int wmax0 = lh.upper_bound ();
4975 2778 : wide_int wmax1 = rh.upper_bound ();
4976 2778 : wi::mul (wmax0, wmax1, sgn, &ovf);
4977 2778 : if (ovf != wi::OVF_NONE)
4978 : return false;
4979 :
4980 105 : if (TYPE_UNSIGNED (type))
4981 : return true;
4982 :
4983 22 : wide_int wmin0 = lh.lower_bound ();
4984 22 : wide_int wmin1 = rh.lower_bound ();
4985 22 : wi::mul (wmin0, wmin1, sgn, &ovf);
4986 22 : if (ovf != wi::OVF_NONE)
4987 : return false;
4988 :
4989 22 : wi::mul (wmin0, wmax1, sgn, &ovf);
4990 22 : if (ovf != wi::OVF_NONE)
4991 : return false;
4992 :
4993 22 : wi::mul (wmax0, wmin1, sgn, &ovf);
4994 22 : if (ovf != wi::OVF_NONE)
4995 : return false;
4996 :
4997 : return true;
4998 2800 : }
4999 :
5000 : #if CHECKING_P
5001 : #include "selftest.h"
5002 :
5003 : namespace selftest
5004 : {
5005 : #define INT(x) wi::shwi ((x), TYPE_PRECISION (integer_type_node))
5006 : #define UINT(x) wi::uhwi ((x), TYPE_PRECISION (unsigned_type_node))
5007 : #define INT16(x) wi::shwi ((x), TYPE_PRECISION (short_integer_type_node))
5008 : #define UINT16(x) wi::uhwi ((x), TYPE_PRECISION (short_unsigned_type_node))
5009 : #define SCHAR(x) wi::shwi ((x), TYPE_PRECISION (signed_char_type_node))
5010 : #define UCHAR(x) wi::uhwi ((x), TYPE_PRECISION (unsigned_char_type_node))
5011 :
5012 : static void
5013 4 : range_op_cast_tests ()
5014 : {
5015 4 : int_range<2> r0, r1, r2, rold;
5016 4 : r0.set_varying (integer_type_node);
5017 4 : wide_int maxint = r0.upper_bound ();
5018 :
5019 : // If a range is in any way outside of the range for the converted
5020 : // to range, default to the range for the new type.
5021 4 : r0.set_varying (short_integer_type_node);
5022 4 : wide_int minshort = r0.lower_bound ();
5023 4 : wide_int maxshort = r0.upper_bound ();
5024 4 : if (TYPE_PRECISION (integer_type_node)
5025 4 : > TYPE_PRECISION (short_integer_type_node))
5026 : {
5027 8 : r1 = int_range<1> (integer_type_node,
5028 4 : wi::zero (TYPE_PRECISION (integer_type_node)),
5029 8 : maxint);
5030 4 : range_cast (r1, short_integer_type_node);
5031 4 : ASSERT_TRUE (r1.lower_bound () == minshort
5032 : && r1.upper_bound() == maxshort);
5033 : }
5034 :
5035 : // (unsigned char)[-5,-1] => [251,255].
5036 4 : r0 = rold = int_range<1> (signed_char_type_node, SCHAR (-5), SCHAR (-1));
5037 4 : range_cast (r0, unsigned_char_type_node);
5038 4 : ASSERT_TRUE (r0 == int_range<1> (unsigned_char_type_node,
5039 : UCHAR (251), UCHAR (255)));
5040 4 : range_cast (r0, signed_char_type_node);
5041 4 : ASSERT_TRUE (r0 == rold);
5042 :
5043 : // (signed char)[15, 150] => [-128,-106][15,127].
5044 4 : r0 = rold = int_range<1> (unsigned_char_type_node, UCHAR (15), UCHAR (150));
5045 4 : range_cast (r0, signed_char_type_node);
5046 4 : r1 = int_range<1> (signed_char_type_node, SCHAR (15), SCHAR (127));
5047 4 : r2 = int_range<1> (signed_char_type_node, SCHAR (-128), SCHAR (-106));
5048 4 : r1.union_ (r2);
5049 4 : ASSERT_TRUE (r1 == r0);
5050 4 : range_cast (r0, unsigned_char_type_node);
5051 4 : ASSERT_TRUE (r0 == rold);
5052 :
5053 : // (unsigned char)[-5, 5] => [0,5][251,255].
5054 4 : r0 = rold = int_range<1> (signed_char_type_node, SCHAR (-5), SCHAR (5));
5055 4 : range_cast (r0, unsigned_char_type_node);
5056 4 : r1 = int_range<1> (unsigned_char_type_node, UCHAR (251), UCHAR (255));
5057 4 : r2 = int_range<1> (unsigned_char_type_node, UCHAR (0), UCHAR (5));
5058 4 : r1.union_ (r2);
5059 4 : ASSERT_TRUE (r0 == r1);
5060 4 : range_cast (r0, signed_char_type_node);
5061 4 : ASSERT_TRUE (r0 == rold);
5062 :
5063 : // (unsigned char)[-5,5] => [0,5][251,255].
5064 4 : r0 = int_range<1> (integer_type_node, INT (-5), INT (5));
5065 4 : range_cast (r0, unsigned_char_type_node);
5066 4 : r1 = int_range<1> (unsigned_char_type_node, UCHAR (0), UCHAR (5));
5067 4 : r1.union_ (int_range<1> (unsigned_char_type_node, UCHAR (251), UCHAR (255)));
5068 4 : ASSERT_TRUE (r0 == r1);
5069 :
5070 : // (unsigned char)[5U,1974U] => [0,255].
5071 4 : r0 = int_range<1> (unsigned_type_node, UINT (5), UINT (1974));
5072 4 : range_cast (r0, unsigned_char_type_node);
5073 4 : ASSERT_TRUE (r0 == int_range<1> (unsigned_char_type_node, UCHAR (0), UCHAR (255)));
5074 4 : range_cast (r0, integer_type_node);
5075 : // Going to a wider range should not sign extend.
5076 4 : ASSERT_TRUE (r0 == int_range<1> (integer_type_node, INT (0), INT (255)));
5077 :
5078 : // (unsigned char)[-350,15] => [0,255].
5079 4 : r0 = int_range<1> (integer_type_node, INT (-350), INT (15));
5080 4 : range_cast (r0, unsigned_char_type_node);
5081 4 : ASSERT_TRUE (r0 == (int_range<1>
5082 : (unsigned_char_type_node,
5083 : min_limit (unsigned_char_type_node),
5084 : max_limit (unsigned_char_type_node))));
5085 :
5086 : // Casting [-120,20] from signed char to unsigned short.
5087 : // => [0, 20][0xff88, 0xffff].
5088 4 : r0 = int_range<1> (signed_char_type_node, SCHAR (-120), SCHAR (20));
5089 4 : range_cast (r0, short_unsigned_type_node);
5090 4 : r1 = int_range<1> (short_unsigned_type_node, UINT16 (0), UINT16 (20));
5091 8 : r2 = int_range<1> (short_unsigned_type_node,
5092 12 : UINT16 (0xff88), UINT16 (0xffff));
5093 4 : r1.union_ (r2);
5094 4 : ASSERT_TRUE (r0 == r1);
5095 : // A truncating cast back to signed char will work because [-120, 20]
5096 : // is representable in signed char.
5097 4 : range_cast (r0, signed_char_type_node);
5098 4 : ASSERT_TRUE (r0 == int_range<1> (signed_char_type_node,
5099 : SCHAR (-120), SCHAR (20)));
5100 :
5101 : // unsigned char -> signed short
5102 : // (signed short)[(unsigned char)25, (unsigned char)250]
5103 : // => [(signed short)25, (signed short)250]
5104 4 : r0 = rold = int_range<1> (unsigned_char_type_node, UCHAR (25), UCHAR (250));
5105 4 : range_cast (r0, short_integer_type_node);
5106 4 : r1 = int_range<1> (short_integer_type_node, INT16 (25), INT16 (250));
5107 4 : ASSERT_TRUE (r0 == r1);
5108 4 : range_cast (r0, unsigned_char_type_node);
5109 4 : ASSERT_TRUE (r0 == rold);
5110 :
5111 : // Test casting a wider signed [-MIN,MAX] to a narrower unsigned.
5112 8 : r0 = int_range<1> (long_long_integer_type_node,
5113 4 : min_limit (long_long_integer_type_node),
5114 8 : max_limit (long_long_integer_type_node));
5115 4 : range_cast (r0, short_unsigned_type_node);
5116 8 : r1 = int_range<1> (short_unsigned_type_node,
5117 4 : min_limit (short_unsigned_type_node),
5118 8 : max_limit (short_unsigned_type_node));
5119 4 : ASSERT_TRUE (r0 == r1);
5120 :
5121 : // Casting NONZERO to a narrower type will wrap/overflow so
5122 : // it's just the entire range for the narrower type.
5123 : //
5124 : // "NOT 0 at signed 32-bits" ==> [-MIN_32,-1][1, +MAX_32]. This is
5125 : // is outside of the range of a smaller range, return the full
5126 : // smaller range.
5127 4 : if (TYPE_PRECISION (integer_type_node)
5128 4 : > TYPE_PRECISION (short_integer_type_node))
5129 : {
5130 4 : r0.set_nonzero (integer_type_node);
5131 4 : range_cast (r0, short_integer_type_node);
5132 8 : r1 = int_range<1> (short_integer_type_node,
5133 4 : min_limit (short_integer_type_node),
5134 8 : max_limit (short_integer_type_node));
5135 4 : ASSERT_TRUE (r0 == r1);
5136 : }
5137 :
5138 : // Casting NONZERO from a narrower signed to a wider signed.
5139 : //
5140 : // NONZERO signed 16-bits is [-MIN_16,-1][1, +MAX_16].
5141 : // Converting this to 32-bits signed is [-MIN_16,-1][1, +MAX_16].
5142 4 : r0.set_nonzero (short_integer_type_node);
5143 4 : range_cast (r0, integer_type_node);
5144 4 : r1 = int_range<1> (integer_type_node, INT (-32768), INT (-1));
5145 4 : r2 = int_range<1> (integer_type_node, INT (1), INT (32767));
5146 4 : r1.union_ (r2);
5147 4 : ASSERT_TRUE (r0 == r1);
5148 4 : }
5149 :
5150 : static void
5151 4 : range_op_lshift_tests ()
5152 : {
5153 : // Test that 0x808.... & 0x8.... still contains 0x8....
5154 : // for a large set of numbers.
5155 4 : {
5156 4 : int_range_max res;
5157 4 : tree big_type = long_long_unsigned_type_node;
5158 4 : unsigned big_prec = TYPE_PRECISION (big_type);
5159 : // big_num = 0x808,0000,0000,0000
5160 4 : wide_int big_num = wi::lshift (wi::uhwi (0x808, big_prec),
5161 8 : wi::uhwi (48, big_prec));
5162 8 : op_bitwise_and.fold_range (res, big_type,
5163 8 : int_range <1> (big_type),
5164 8 : int_range <1> (big_type, big_num, big_num));
5165 : // val = 0x8,0000,0000,0000
5166 4 : wide_int val = wi::lshift (wi::uhwi (8, big_prec),
5167 8 : wi::uhwi (48, big_prec));
5168 4 : ASSERT_TRUE (res.contains_p (val));
5169 4 : }
5170 :
5171 4 : if (TYPE_PRECISION (unsigned_type_node) > 31)
5172 : {
5173 : // unsigned VARYING = op1 << 1 should be VARYING.
5174 4 : int_range<2> lhs (unsigned_type_node);
5175 4 : int_range<2> shift (unsigned_type_node, INT (1), INT (1));
5176 4 : int_range_max op1;
5177 4 : op_lshift.op1_range (op1, unsigned_type_node, lhs, shift);
5178 4 : ASSERT_TRUE (op1.varying_p ());
5179 :
5180 : // 0 = op1 << 1 should be [0,0], [0x8000000, 0x8000000].
5181 4 : int_range<2> zero (unsigned_type_node, UINT (0), UINT (0));
5182 4 : op_lshift.op1_range (op1, unsigned_type_node, zero, shift);
5183 4 : ASSERT_TRUE (op1.num_pairs () == 2);
5184 : // Remove the [0,0] range.
5185 4 : op1.intersect (zero);
5186 4 : ASSERT_TRUE (op1.num_pairs () == 1);
5187 : // op1 << 1 should be [0x8000,0x8000] << 1,
5188 : // which should result in [0,0].
5189 4 : int_range_max result;
5190 4 : op_lshift.fold_range (result, unsigned_type_node, op1, shift);
5191 4 : ASSERT_TRUE (result == zero);
5192 4 : }
5193 : // signed VARYING = op1 << 1 should be VARYING.
5194 4 : if (TYPE_PRECISION (integer_type_node) > 31)
5195 : {
5196 : // unsigned VARYING = op1 << 1 should be VARYING.
5197 4 : int_range<2> lhs (integer_type_node);
5198 4 : int_range<2> shift (integer_type_node, INT (1), INT (1));
5199 4 : int_range_max op1;
5200 4 : op_lshift.op1_range (op1, integer_type_node, lhs, shift);
5201 4 : ASSERT_TRUE (op1.varying_p ());
5202 :
5203 : // 0 = op1 << 1 should be [0,0], [0x8000000, 0x8000000].
5204 4 : int_range<2> zero (integer_type_node, INT (0), INT (0));
5205 4 : op_lshift.op1_range (op1, integer_type_node, zero, shift);
5206 4 : ASSERT_TRUE (op1.num_pairs () == 2);
5207 : // Remove the [0,0] range.
5208 4 : op1.intersect (zero);
5209 4 : ASSERT_TRUE (op1.num_pairs () == 1);
5210 : // op1 << 1 should be [0x8000,0x8000] << 1,
5211 : // which should result in [0,0].
5212 4 : int_range_max result;
5213 4 : op_lshift.fold_range (result, unsigned_type_node, op1, shift);
5214 4 : ASSERT_TRUE (result == zero);
5215 4 : }
5216 4 : }
5217 :
5218 : static void
5219 4 : range_op_rshift_tests ()
5220 : {
5221 : // unsigned: [3, MAX] = OP1 >> 1
5222 4 : {
5223 4 : int_range_max lhs (unsigned_type_node,
5224 4 : UINT (3), max_limit (unsigned_type_node));
5225 4 : int_range_max one (unsigned_type_node,
5226 8 : wi::one (TYPE_PRECISION (unsigned_type_node)),
5227 8 : wi::one (TYPE_PRECISION (unsigned_type_node)));
5228 4 : int_range_max op1;
5229 4 : op_rshift.op1_range (op1, unsigned_type_node, lhs, one);
5230 4 : ASSERT_FALSE (op1.contains_p (UINT (3)));
5231 4 : }
5232 :
5233 : // signed: [3, MAX] = OP1 >> 1
5234 4 : {
5235 4 : int_range_max lhs (integer_type_node,
5236 4 : INT (3), max_limit (integer_type_node));
5237 4 : int_range_max one (integer_type_node, INT (1), INT (1));
5238 4 : int_range_max op1;
5239 4 : op_rshift.op1_range (op1, integer_type_node, lhs, one);
5240 4 : ASSERT_FALSE (op1.contains_p (INT (-2)));
5241 4 : }
5242 :
5243 : // This is impossible, so OP1 should be [].
5244 : // signed: [MIN, MIN] = OP1 >> 1
5245 4 : {
5246 4 : int_range_max lhs (integer_type_node,
5247 4 : min_limit (integer_type_node),
5248 4 : min_limit (integer_type_node));
5249 4 : int_range_max one (integer_type_node, INT (1), INT (1));
5250 4 : int_range_max op1;
5251 4 : op_rshift.op1_range (op1, integer_type_node, lhs, one);
5252 4 : ASSERT_TRUE (op1.undefined_p ());
5253 4 : }
5254 :
5255 : // signed: ~[-1] = OP1 >> 31
5256 4 : if (TYPE_PRECISION (integer_type_node) > 31)
5257 : {
5258 4 : int_range_max lhs (integer_type_node, INT (-1), INT (-1), VR_ANTI_RANGE);
5259 4 : int_range_max shift (integer_type_node, INT (31), INT (31));
5260 4 : int_range_max op1;
5261 4 : op_rshift.op1_range (op1, integer_type_node, lhs, shift);
5262 4 : int_range_max negatives = range_negatives (integer_type_node);
5263 4 : negatives.intersect (op1);
5264 4 : ASSERT_TRUE (negatives.undefined_p ());
5265 4 : }
5266 4 : }
5267 :
5268 : static void
5269 4 : range_op_bitwise_and_tests ()
5270 : {
5271 4 : int_range_max res;
5272 4 : wide_int min = min_limit (integer_type_node);
5273 4 : wide_int max = max_limit (integer_type_node);
5274 4 : wide_int tiny = wi::add (min, wi::one (TYPE_PRECISION (integer_type_node)));
5275 4 : int_range_max i1 (integer_type_node, tiny, max);
5276 4 : int_range_max i2 (integer_type_node, INT (255), INT (255));
5277 :
5278 : // [MIN+1, MAX] = OP1 & 255: OP1 is VARYING
5279 4 : op_bitwise_and.op1_range (res, integer_type_node, i1, i2);
5280 4 : ASSERT_TRUE (res == int_range<1> (integer_type_node));
5281 :
5282 : // VARYING = OP1 & 255: OP1 is VARYING
5283 4 : i1 = int_range<1> (integer_type_node);
5284 4 : op_bitwise_and.op1_range (res, integer_type_node, i1, i2);
5285 4 : ASSERT_TRUE (res == int_range<1> (integer_type_node));
5286 :
5287 : // For 0 = x & MASK, x is ~MASK.
5288 4 : {
5289 4 : int_range<2> zero (integer_type_node, INT (0), INT (0));
5290 4 : int_range<2> mask = int_range<2> (integer_type_node, INT (7), INT (7));
5291 4 : op_bitwise_and.op1_range (res, integer_type_node, zero, mask);
5292 4 : wide_int inv = wi::shwi (~7U, TYPE_PRECISION (integer_type_node));
5293 4 : ASSERT_TRUE (res.get_nonzero_bits () == inv);
5294 4 : }
5295 :
5296 : // (NONZERO | X) is nonzero.
5297 4 : i1.set_nonzero (integer_type_node);
5298 4 : i2.set_varying (integer_type_node);
5299 4 : op_bitwise_or.fold_range (res, integer_type_node, i1, i2);
5300 4 : ASSERT_TRUE (res.nonzero_p ());
5301 :
5302 : // (NEGATIVE | X) is nonzero.
5303 4 : i1 = int_range<1> (integer_type_node, INT (-5), INT (-3));
5304 4 : i2.set_varying (integer_type_node);
5305 4 : op_bitwise_or.fold_range (res, integer_type_node, i1, i2);
5306 4 : ASSERT_FALSE (res.contains_p (INT (0)));
5307 4 : }
5308 :
5309 : static void
5310 4 : range_relational_tests ()
5311 : {
5312 4 : int_range<2> lhs (unsigned_char_type_node);
5313 4 : int_range<2> op1 (unsigned_char_type_node, UCHAR (8), UCHAR (10));
5314 4 : int_range<2> op2 (unsigned_char_type_node, UCHAR (20), UCHAR (20));
5315 :
5316 : // Never wrapping additions mean LHS > OP1.
5317 4 : relation_kind code = op_plus.lhs_op1_relation (lhs, op1, op2, VREL_VARYING);
5318 4 : ASSERT_TRUE (code == VREL_GT);
5319 :
5320 : // Most wrapping additions mean nothing...
5321 4 : op1 = int_range<2> (unsigned_char_type_node, UCHAR (8), UCHAR (10));
5322 4 : op2 = int_range<2> (unsigned_char_type_node, UCHAR (0), UCHAR (255));
5323 4 : code = op_plus.lhs_op1_relation (lhs, op1, op2, VREL_VARYING);
5324 4 : ASSERT_TRUE (code == VREL_VARYING);
5325 :
5326 : // However, always wrapping additions mean LHS < OP1.
5327 4 : op1 = int_range<2> (unsigned_char_type_node, UCHAR (1), UCHAR (255));
5328 4 : op2 = int_range<2> (unsigned_char_type_node, UCHAR (255), UCHAR (255));
5329 4 : code = op_plus.lhs_op1_relation (lhs, op1, op2, VREL_VARYING);
5330 4 : ASSERT_TRUE (code == VREL_LT);
5331 4 : }
5332 :
5333 : void
5334 4 : range_op_tests ()
5335 : {
5336 4 : range_op_rshift_tests ();
5337 4 : range_op_lshift_tests ();
5338 4 : range_op_bitwise_and_tests ();
5339 4 : range_op_cast_tests ();
5340 4 : range_relational_tests ();
5341 :
5342 4 : extern void range_op_float_tests ();
5343 4 : range_op_float_tests ();
5344 4 : }
5345 :
5346 : } // namespace selftest
5347 :
5348 : #endif // CHECKING_P
|
