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