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