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 293417 : range_op_table::range_op_table ()
83 : {
84 293417 : initialize_integral_ops ();
85 293417 : initialize_pointer_ops ();
86 293417 : initialize_float_ops ();
87 :
88 293417 : set (EQ_EXPR, op_equal);
89 293417 : set (NE_EXPR, op_not_equal);
90 293417 : set (LT_EXPR, op_lt);
91 293417 : set (LE_EXPR, op_le);
92 293417 : set (GT_EXPR, op_gt);
93 293417 : set (GE_EXPR, op_ge);
94 293417 : set (SSA_NAME, op_ident);
95 293417 : set (PAREN_EXPR, op_ident);
96 293417 : set (OBJ_TYPE_REF, op_ident);
97 293417 : set (REAL_CST, op_cst);
98 293417 : set (INTEGER_CST, op_cst);
99 293417 : set (NOP_EXPR, op_cast);
100 293417 : set (CONVERT_EXPR, op_cast);
101 293417 : set (VIEW_CONVERT_EXPR, op_view);
102 293417 : set (FLOAT_EXPR, op_cast);
103 293417 : set (FIX_TRUNC_EXPR, op_cast);
104 293417 : set (PLUS_EXPR, op_plus);
105 293417 : set (ABS_EXPR, op_abs);
106 293417 : set (MINUS_EXPR, op_minus);
107 293417 : set (NEGATE_EXPR, op_negate);
108 293417 : set (MULT_EXPR, op_mult);
109 293417 : set (ADDR_EXPR, op_addr);
110 293417 : set (BIT_NOT_EXPR, op_bitwise_not);
111 293417 : set (BIT_XOR_EXPR, op_bitwise_xor);
112 293417 : set (BIT_AND_EXPR, op_bitwise_and);
113 293417 : set (BIT_IOR_EXPR, op_bitwise_or);
114 293417 : set (MIN_EXPR, op_min);
115 293417 : set (MAX_EXPR, op_max);
116 293417 : }
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 1918399181 : range_op_handler::range_op_handler ()
125 : {
126 1918399181 : m_operator = &default_operator;
127 1918399181 : }
128 :
129 : // Create a range_op_handler for CODE. Use a default operator if CODE
130 : // does not have an entry.
131 :
132 4678839725 : range_op_handler::range_op_handler (unsigned code)
133 : {
134 4678839725 : m_operator = operator_table[code];
135 4678839725 : if (!m_operator)
136 888814048 : m_operator = &default_operator;
137 4678839725 : }
138 :
139 : // Return TRUE if this handler has a non-default operator.
140 :
141 6738646045 : range_op_handler::operator bool () const
142 : {
143 6738646045 : 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 1132925505 : range_op_handler::range_op () const
152 : {
153 1132925505 : if (m_operator != &default_operator)
154 1132925505 : 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 680633296 : dispatch_trio (unsigned lhs, unsigned op1, unsigned op2)
164 : {
165 680633296 : 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 680633296 : range_op_handler::dispatch_kind (const vrange &lhs, const vrange &op1,
191 : const vrange& op2) const
192 : {
193 680633296 : return dispatch_trio (lhs.m_discriminator, op1.m_discriminator,
194 680633296 : 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 305727707 : range_op_handler::fold_range (vrange &r, tree type,
224 : const vrange &lh,
225 : const vrange &rh,
226 : relation_trio rel) const
227 : {
228 305727707 : gcc_checking_assert (m_operator);
229 : #if CHECKING_P
230 305727707 : if (!lh.undefined_p () && !rh.undefined_p ())
231 299652597 : gcc_assert (m_operator->operand_check_p (type, lh.type (), rh.type ()));
232 : #endif
233 305727707 : switch (dispatch_kind (r, lh, rh))
234 : {
235 232242732 : case RO_III:
236 232242732 : return m_operator->fold_range (as_a <irange> (r), type,
237 : as_a <irange> (lh),
238 232242732 : as_a <irange> (rh), rel);
239 372042 : case RO_IFI:
240 372042 : return m_operator->fold_range (as_a <irange> (r), type,
241 : as_a <frange> (lh),
242 372042 : as_a <irange> (rh), rel);
243 2685002 : case RO_IFF:
244 2685002 : return m_operator->fold_range (as_a <irange> (r), type,
245 : as_a <frange> (lh),
246 2685002 : as_a <frange> (rh), rel);
247 7439445 : case RO_FFF:
248 7439445 : return m_operator->fold_range (as_a <frange> (r), type,
249 : as_a <frange> (lh),
250 7439445 : 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 932188 : case RO_FIF:
256 932188 : return m_operator->fold_range (as_a <frange> (r), type,
257 : as_a <irange> (lh),
258 932188 : as_a <frange> (rh), rel);
259 19441342 : case RO_PPP:
260 19441342 : return m_operator->fold_range (as_a <prange> (r), type,
261 : as_a <prange> (lh),
262 19441342 : as_a <prange> (rh), rel);
263 9607332 : case RO_PPI:
264 9607332 : return m_operator->fold_range (as_a <prange> (r), type,
265 : as_a <prange> (lh),
266 9607332 : as_a <irange> (rh), rel);
267 19201876 : case RO_IPP:
268 19201876 : return m_operator->fold_range (as_a <irange> (r), type,
269 : as_a <prange> (lh),
270 19201876 : as_a <prange> (rh), rel);
271 2059275 : case RO_PIP:
272 2059275 : return m_operator->fold_range (as_a <prange> (r), type,
273 : as_a <irange> (lh),
274 2059275 : as_a <prange> (rh), rel);
275 11746441 : case RO_IPI:
276 11746441 : return m_operator->fold_range (as_a <irange> (r), type,
277 : as_a <prange> (lh),
278 11746441 : 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 95940975 : range_op_handler::op1_range (vrange &r, tree type,
288 : const vrange &lhs,
289 : const vrange &op2,
290 : relation_trio rel) const
291 : {
292 95940975 : gcc_checking_assert (m_operator);
293 95940975 : if (lhs.undefined_p ())
294 : return false;
295 : #if CHECKING_P
296 95940171 : if (!op2.undefined_p ())
297 95940036 : gcc_assert (m_operator->operand_check_p (lhs.type (), type, op2.type ()));
298 : #endif
299 95940171 : switch (dispatch_kind (r, lhs, op2))
300 : {
301 82752927 : case RO_III:
302 82752927 : return m_operator->op1_range (as_a <irange> (r), type,
303 : as_a <irange> (lhs),
304 82752927 : as_a <irange> (op2), rel);
305 228118 : case RO_IFI:
306 228118 : return m_operator->op1_range (as_a <irange> (r), type,
307 : as_a <frange> (lhs),
308 228118 : as_a <irange> (op2), rel);
309 886407 : case RO_PPP:
310 886407 : return m_operator->op1_range (as_a <prange> (r), type,
311 : as_a <prange> (lhs),
312 886407 : as_a <prange> (op2), rel);
313 9042271 : case RO_PIP:
314 9042271 : return m_operator->op1_range (as_a <prange> (r), type,
315 : as_a <irange> (lhs),
316 9042271 : as_a <prange> (op2), rel);
317 378410 : case RO_PPI:
318 378410 : return m_operator->op1_range (as_a <prange> (r), type,
319 : as_a <prange> (lhs),
320 378410 : as_a <irange> (op2), rel);
321 232940 : case RO_IPI:
322 232940 : return m_operator->op1_range (as_a <irange> (r), type,
323 : as_a <prange> (lhs),
324 232940 : as_a <irange> (op2), rel);
325 1493619 : case RO_FIF:
326 1493619 : return m_operator->op1_range (as_a <frange> (r), type,
327 : as_a <irange> (lhs),
328 1493619 : as_a <frange> (op2), rel);
329 925479 : case RO_FFF:
330 925479 : return m_operator->op1_range (as_a <frange> (r), type,
331 : as_a <frange> (lhs),
332 925479 : 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 26676020 : range_op_handler::op2_range (vrange &r, tree type,
342 : const vrange &lhs,
343 : const vrange &op1,
344 : relation_trio rel) const
345 : {
346 26676020 : gcc_checking_assert (m_operator);
347 26676020 : if (lhs.undefined_p ())
348 : return false;
349 : #if CHECKING_P
350 26676005 : if (!op1.undefined_p ())
351 26675931 : gcc_assert (m_operator->operand_check_p (lhs.type (), op1.type (), type));
352 : #endif
353 26676005 : switch (dispatch_kind (r, lhs, op1))
354 : {
355 20487164 : case RO_III:
356 20487164 : return m_operator->op2_range (as_a <irange> (r), type,
357 : as_a <irange> (lhs),
358 20487164 : as_a <irange> (op1), rel);
359 5110212 : case RO_PIP:
360 5110212 : return m_operator->op2_range (as_a <prange> (r), type,
361 : as_a <irange> (lhs),
362 5110212 : as_a <prange> (op1), rel);
363 206731 : case RO_IPP:
364 206731 : return m_operator->op2_range (as_a <irange> (r), type,
365 : as_a <prange> (lhs),
366 206731 : as_a <prange> (op1), rel);
367 513016 : case RO_FIF:
368 513016 : return m_operator->op2_range (as_a <frange> (r), type,
369 : as_a <irange> (lhs),
370 513016 : as_a <frange> (op1), rel);
371 358746 : case RO_FFF:
372 358746 : return m_operator->op2_range (as_a <frange> (r), type,
373 : as_a <frange> (lhs),
374 358746 : 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 128670009 : range_op_handler::lhs_op1_relation (const vrange &lhs,
384 : const vrange &op1,
385 : const vrange &op2,
386 : relation_kind rel) const
387 : {
388 128670009 : gcc_checking_assert (m_operator);
389 128670009 : switch (dispatch_kind (lhs, op1, op2))
390 : {
391 102992241 : case RO_III:
392 102992241 : return m_operator->lhs_op1_relation (as_a <irange> (lhs),
393 : as_a <irange> (op1),
394 102992241 : as_a <irange> (op2), rel);
395 1660274 : case RO_PPP:
396 1660274 : return m_operator->lhs_op1_relation (as_a <prange> (lhs),
397 : as_a <prange> (op1),
398 1660274 : as_a <prange> (op2), rel);
399 6553031 : case RO_IPP:
400 6553031 : return m_operator->lhs_op1_relation (as_a <irange> (lhs),
401 : as_a <prange> (op1),
402 6553031 : as_a <prange> (op2), rel);
403 1543857 : case RO_PII:
404 1543857 : return m_operator->lhs_op1_relation (as_a <prange> (lhs),
405 : as_a <irange> (op1),
406 1543857 : as_a <irange> (op2), rel);
407 8303670 : case RO_PPI:
408 8303670 : return m_operator->lhs_op1_relation (as_a <prange> (lhs),
409 : as_a <prange> (op1),
410 8303670 : as_a <irange> (op2), rel);
411 1076576 : case RO_IFF:
412 1076576 : return m_operator->lhs_op1_relation (as_a <irange> (lhs),
413 : as_a <frange> (op1),
414 1076576 : as_a <frange> (op2), rel);
415 5608706 : case RO_FFF:
416 5608706 : return m_operator->lhs_op1_relation (as_a <frange> (lhs),
417 : as_a <frange> (op1),
418 5608706 : 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 37815516 : range_op_handler::lhs_op2_relation (const vrange &lhs,
428 : const vrange &op1,
429 : const vrange &op2,
430 : relation_kind rel) const
431 : {
432 37815516 : gcc_checking_assert (m_operator);
433 37815516 : switch (dispatch_kind (lhs, op1, op2))
434 : {
435 26063565 : case RO_III:
436 26063565 : return m_operator->lhs_op2_relation (as_a <irange> (lhs),
437 : as_a <irange> (op1),
438 26063565 : as_a <irange> (op2), rel);
439 190242 : case RO_IFF:
440 190242 : return m_operator->lhs_op2_relation (as_a <irange> (lhs),
441 : as_a <frange> (op1),
442 190242 : as_a <frange> (op2), rel);
443 3351109 : case RO_FFF:
444 3351109 : return m_operator->lhs_op2_relation (as_a <frange> (lhs),
445 : as_a <frange> (op1),
446 3351109 : 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 85717322 : range_op_handler::op1_op2_relation (const vrange &lhs,
456 : const vrange &op1,
457 : const vrange &op2) const
458 : {
459 85717322 : gcc_checking_assert (m_operator);
460 :
461 85717322 : switch (dispatch_kind (lhs, op1, op2))
462 : {
463 66186870 : case RO_III:
464 66186870 : return m_operator->op1_op2_relation (as_a <irange> (lhs),
465 : as_a <irange> (op1),
466 66186870 : as_a <irange> (op2));
467 :
468 16701478 : case RO_IPP:
469 16701478 : return m_operator->op1_op2_relation (as_a <irange> (lhs),
470 : as_a <prange> (op1),
471 16701478 : as_a <prange> (op2));
472 :
473 1842893 : case RO_IFF:
474 1842893 : return m_operator->op1_op2_relation (as_a <irange> (lhs),
475 : as_a <frange> (op1),
476 1842893 : as_a <frange> (op2));
477 :
478 659006 : case RO_FFF:
479 659006 : return m_operator->op1_op2_relation (as_a <frange> (lhs),
480 : as_a <frange> (op1),
481 659006 : as_a <frange> (op2));
482 :
483 : default:
484 : return VREL_VARYING;
485 : }
486 : }
487 :
488 : bool
489 86566 : range_op_handler::overflow_free_p (const vrange &lh,
490 : const vrange &rh,
491 : relation_trio rel) const
492 : {
493 86566 : gcc_checking_assert (m_operator);
494 86566 : switch (dispatch_kind (lh, lh, rh))
495 : {
496 86566 : case RO_III:
497 86566 : return m_operator->overflow_free_p(as_a <irange> (lh),
498 : as_a <irange> (rh),
499 86566 : rel);
500 : default:
501 : return false;
502 : }
503 : }
504 :
505 : bool
506 9683089 : range_op_handler::operand_check_p (tree t1, tree t2, tree t3) const
507 : {
508 9683089 : gcc_checking_assert (m_operator);
509 9683089 : 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 180059929 : update_known_bitmask (vrange &r, tree_code code,
517 : const vrange &lh, const vrange &rh)
518 : {
519 180059929 : if (r.undefined_p () || lh.undefined_p () || rh.undefined_p ()
520 360115004 : || r.singleton_p ())
521 10555939 : return;
522 :
523 169503990 : widest_int widest_value, widest_mask;
524 169503990 : tree type = r.type ();
525 169503990 : signop sign = TYPE_SIGN (type);
526 169503990 : int prec = TYPE_PRECISION (type);
527 169503990 : irange_bitmask lh_bits = lh.get_bitmask ();
528 169503990 : irange_bitmask rh_bits = rh.get_bitmask ();
529 :
530 169503990 : switch (get_gimple_rhs_class (code))
531 : {
532 59339824 : case GIMPLE_UNARY_RHS:
533 59339824 : bit_value_unop (code, sign, prec, &widest_value, &widest_mask,
534 59339824 : TYPE_SIGN (lh.type ()),
535 59339824 : TYPE_PRECISION (lh.type ()),
536 118680165 : widest_int::from (lh_bits.value (),
537 59339824 : TYPE_SIGN (lh.type ())),
538 118679648 : widest_int::from (lh_bits.mask (),
539 59339824 : TYPE_SIGN (lh.type ())));
540 59339824 : break;
541 110164166 : case GIMPLE_BINARY_RHS:
542 220328332 : bit_value_binop (code, sign, prec, &widest_value, &widest_mask,
543 110164166 : TYPE_SIGN (lh.type ()),
544 110164166 : TYPE_PRECISION (lh.type ()),
545 220329627 : widest_int::from (lh_bits.value (), sign),
546 220329627 : widest_int::from (lh_bits.mask (), sign),
547 110164166 : TYPE_SIGN (rh.type ()),
548 110164166 : TYPE_PRECISION (rh.type ()),
549 220329594 : widest_int::from (rh_bits.value (), sign),
550 220328332 : widest_int::from (rh_bits.mask (), sign));
551 110164166 : break;
552 0 : default:
553 0 : gcc_unreachable ();
554 : }
555 :
556 169503990 : wide_int mask = wide_int::from (widest_mask, prec, sign);
557 339007980 : wide_int value = wide_int::from (widest_value, prec, sign);
558 : // Bitmasks must have the unknown value bits cleared.
559 169503990 : value &= ~mask;
560 339007980 : irange_bitmask bm (value, mask);
561 169503990 : r.update_bitmask (bm);
562 169504998 : }
563 :
564 : // Return the upper limit for a type.
565 :
566 : static inline wide_int
567 18253286 : max_limit (const_tree type)
568 : {
569 18253286 : return irange_val_max (type);
570 : }
571 :
572 : // Return the lower limit for a type.
573 :
574 : static inline wide_int
575 20581440 : min_limit (const_tree type)
576 : {
577 20581440 : 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 5269184 : get_shift_range (irange &r, tree type, const irange &op)
586 : {
587 5269184 : if (op.undefined_p ())
588 : return false;
589 :
590 : // Build valid range and intersect it with the shift range.
591 5268031 : r.set (op.type (),
592 10536062 : wi::shwi (0, TYPE_PRECISION (op.type ())),
593 5268031 : wi::shwi (TYPE_PRECISION (type) - 1, TYPE_PRECISION (op.type ())));
594 5268031 : r.intersect (op);
595 :
596 : // If there are no valid ranges in the shift range, returned false.
597 5268031 : if (r.undefined_p ())
598 677 : 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 56686 : 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 56686 : int_range_max tmp;
629 113372 : widest_int lh_range = wi::sub (widest_int::from (lh_ub, TYPE_SIGN (type)),
630 113372 : widest_int::from (lh_lb, TYPE_SIGN (type)));
631 : // if there are 1 to 8 values in the LH range, split them up.
632 56686 : r.set_undefined ();
633 113372 : if (lh_range >= 0 && lh_range < limit)
634 : {
635 20202 : for (unsigned x = 0; x <= lh_range; x++)
636 : {
637 13807 : wide_int val = lh_lb + x;
638 13807 : wi_fold (tmp, type, val, val, val, val);
639 13807 : r.union_ (tmp);
640 13807 : }
641 : }
642 : // Otherwise just call wi_fold.
643 : else
644 50291 : wi_fold (r, type, lh_lb, lh_ub, lh_lb, lh_ub);
645 56686 : }
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 147603836 : 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 147603836 : int_range_max tmp;
659 295207672 : widest_int rh_range = wi::sub (widest_int::from (rh_ub, TYPE_SIGN (type)),
660 295207672 : widest_int::from (rh_lb, TYPE_SIGN (type)));
661 295207672 : widest_int lh_range = wi::sub (widest_int::from (lh_ub, TYPE_SIGN (type)),
662 295207672 : 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 147603836 : if (rh_range > 0 && rh_range < 4)
666 : {
667 5329959 : wi_fold_in_parts (r, type, lh_lb, lh_ub, rh_lb, rh_lb);
668 5329959 : if (rh_range > 1)
669 : {
670 658404 : wi_fold_in_parts (tmp, type, lh_lb, lh_ub, rh_lb + 1, rh_lb + 1);
671 658404 : r.union_ (tmp);
672 658404 : if (rh_range == 3)
673 : {
674 432541 : wi_fold_in_parts (tmp, type, lh_lb, lh_ub, rh_lb + 2, rh_lb + 2);
675 432541 : r.union_ (tmp);
676 : }
677 : }
678 5329959 : wi_fold_in_parts (tmp, type, lh_lb, lh_ub, rh_ub, rh_ub);
679 5329959 : 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 142273877 : else if (lh_range > 0 && lh_range < 4)
684 : {
685 10160535 : wi_fold (r, type, lh_lb, lh_lb, rh_lb, rh_ub);
686 10160535 : if (lh_range > 1)
687 : {
688 1707176 : wi_fold (tmp, type, lh_lb + 1, lh_lb + 1, rh_lb, rh_ub);
689 1707168 : r.union_ (tmp);
690 1707168 : if (lh_range == 3)
691 : {
692 730440 : wi_fold (tmp, type, lh_lb + 2, lh_lb + 2, rh_lb, rh_ub);
693 730436 : r.union_ (tmp);
694 : }
695 : }
696 10160535 : wi_fold (tmp, type, lh_ub, lh_ub, rh_lb, rh_ub);
697 10160535 : r.union_ (tmp);
698 : }
699 : // Otherwise just call wi_fold.
700 : else
701 132113342 : wi_fold (r, type, lh_lb, lh_ub, rh_lb, rh_ub);
702 147604218 : }
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 103806242 : range_operator::fold_range (irange &r, tree type,
709 : const irange &lh,
710 : const irange &rh,
711 : relation_trio trio) const
712 : {
713 103806242 : gcc_checking_assert (r.supports_type_p (type));
714 103806242 : if (empty_range_varying (r, type, lh, rh))
715 56424 : return true;
716 :
717 103749818 : relation_kind rel = trio.op1_op2 ();
718 103749818 : unsigned num_lh = lh.num_pairs ();
719 103749818 : 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 103750983 : if (relation_equiv_p (rel) && lh == rh)
724 : {
725 52709 : int_range_max tmp;
726 52709 : r.set_undefined ();
727 148985 : for (unsigned x = 0; x < num_lh; ++x)
728 : {
729 : // If the number of subranges is too high, limit subrange creation.
730 56686 : unsigned limit = (r.num_pairs () > 32) ? 0 : 8;
731 56686 : wide_int lh_lb = lh.lower_bound (x);
732 56686 : wide_int lh_ub = lh.upper_bound (x);
733 56686 : wi_fold_in_parts_equiv (tmp, type, lh_lb, lh_ub, limit);
734 56686 : r.union_ (tmp);
735 56686 : if (r.varying_p ())
736 : break;
737 56686 : }
738 52709 : op1_op2_relation_effect (r, type, lh, rh, rel);
739 52709 : update_bitmask (r, lh, rh);
740 52709 : return true;
741 52709 : }
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 103697109 : if ((num_lh == 1 && num_rh == 1) || num_lh * num_rh > 12)
747 : {
748 86311105 : wi_fold_in_parts (r, type, lh.lower_bound (), lh.upper_bound (),
749 172619462 : rh.lower_bound (), rh.upper_bound ());
750 86309731 : op1_op2_relation_effect (r, type, lh, rh, rel);
751 86309731 : update_bitmask (r, lh, rh);
752 86309731 : return true;
753 : }
754 :
755 17387378 : int_range_max tmp;
756 17387378 : r.set_undefined ();
757 71424260 : for (unsigned x = 0; x < num_lh; ++x)
758 86192746 : for (unsigned y = 0; y < num_rh; ++y)
759 : {
760 49543242 : wide_int lh_lb = lh.lower_bound (x);
761 49543242 : wide_int lh_ub = lh.upper_bound (x);
762 49543242 : wide_int rh_lb = rh.lower_bound (y);
763 49543242 : wide_int rh_ub = rh.upper_bound (y);
764 49543242 : wi_fold_in_parts (tmp, type, lh_lb, lh_ub, rh_lb, rh_ub);
765 49543242 : r.union_ (tmp);
766 49543242 : if (r.varying_p ())
767 : {
768 4060373 : op1_op2_relation_effect (r, type, lh, rh, rel);
769 4060373 : update_bitmask (r, lh, rh);
770 4060373 : return true;
771 : }
772 49547238 : }
773 13327005 : op1_op2_relation_effect (r, type, lh, rh, rel);
774 13327005 : update_bitmask (r, lh, rh);
775 13327005 : return true;
776 17387378 : }
777 :
778 :
779 : bool
780 71620 : range_operator::fold_range (frange &, tree, const irange &,
781 : const frange &, relation_trio) const
782 : {
783 71620 : return false;
784 : }
785 :
786 : bool
787 1501 : range_operator::op1_range (irange &, tree, const frange &,
788 : const irange &, relation_trio) const
789 : {
790 1501 : return false;
791 : }
792 :
793 :
794 :
795 : // The default for op1_range is to return false.
796 :
797 : bool
798 786920 : 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 786920 : return false;
805 : }
806 :
807 : // The default for op2_range is to return false.
808 :
809 : bool
810 573100 : 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 573100 : return false;
817 : }
818 :
819 : // The default relation routines return VREL_VARYING.
820 :
821 : relation_kind
822 24886937 : 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 24886937 : return VREL_VARYING;
828 : }
829 :
830 : relation_kind
831 17946483 : 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 17946483 : return VREL_VARYING;
837 : }
838 :
839 : relation_kind
840 15198724 : 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 15198724 : return VREL_VARYING;
845 : }
846 :
847 : // Default is no relation affects the LHS.
848 :
849 : bool
850 63722088 : 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 63722088 : 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 8112 : range_operator::update_bitmask (irange &, const irange &,
873 : const irange &) const
874 : {
875 8112 : }
876 :
877 : // Check that operand types are OK. Default to always OK.
878 :
879 : bool
880 131724145 : range_operator::operand_check_p (tree, tree, tree) const
881 : {
882 131724145 : 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 41634372 : value_range_from_overflowed_bounds (irange &r, tree type,
890 : const wide_int &wmin,
891 : const wide_int &wmax)
892 : {
893 41634372 : const signop sgn = TYPE_SIGN (type);
894 41634372 : const unsigned int prec = TYPE_PRECISION (type);
895 :
896 41634372 : wide_int tmin = wide_int::from (wmin, prec, sgn);
897 41634372 : wide_int tmax = wide_int::from (wmax, prec, sgn);
898 :
899 41634372 : bool covers = false;
900 41634372 : wide_int tem = tmin;
901 41634372 : tmin = tmax + 1;
902 41634372 : if (wi::cmp (tmin, tmax, sgn) < 0)
903 2689860 : covers = true;
904 41634372 : tmax = tem - 1;
905 41634372 : 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 39002987 : if (covers || wi::cmp (tmin, tmax, sgn) > 0)
912 28211003 : r.set_varying (type);
913 : else
914 13423369 : r.set (type, tmin, tmax, VR_ANTI_RANGE);
915 41635030 : }
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 143284524 : 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 143284524 : const signop sgn = TYPE_SIGN (type);
928 143284524 : const unsigned int prec = TYPE_PRECISION (type);
929 225371577 : 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 158177002 : if (prec == 1 && wi::ne_p (wmax, wmin))
934 : {
935 0 : r.set_varying (type);
936 0 : return;
937 : }
938 :
939 143284524 : if (overflow_wraps)
940 : {
941 : // If overflow wraps, truncate the values and adjust the range,
942 : // kind, and bounds appropriately.
943 82087053 : if ((min_ovf != wi::OVF_NONE) == (max_ovf != wi::OVF_NONE))
944 : {
945 57966059 : wide_int tmin = wide_int::from (wmin, prec, sgn);
946 57966059 : 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 57966059 : if (wi::gt_p (tmin, tmax, sgn))
950 543277 : r.set_varying (type);
951 : else
952 : // No overflow or both overflow or underflow. The range
953 : // kind stays normal.
954 57422782 : r.set (type, tmin, tmax);
955 57966059 : return;
956 57966270 : }
957 :
958 24120994 : if ((min_ovf == wi::OVF_UNDERFLOW && max_ovf == wi::OVF_NONE)
959 16918861 : || (max_ovf == wi::OVF_OVERFLOW && min_ovf == wi::OVF_NONE))
960 24120994 : 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 61197471 : if ((min_ovf == wi::OVF_OVERFLOW && max_ovf == wi::OVF_OVERFLOW)
970 61194895 : || (min_ovf == wi::OVF_UNDERFLOW && max_ovf == wi::OVF_UNDERFLOW))
971 : {
972 5427 : r.set_undefined ();
973 5427 : return;
974 : }
975 :
976 : // If overflow does not wrap, saturate to [MIN, MAX].
977 61192044 : wide_int new_lb, new_ub;
978 61192044 : if (min_ovf == wi::OVF_UNDERFLOW)
979 7890309 : new_lb = wi::min_value (prec, sgn);
980 53301946 : else if (min_ovf == wi::OVF_OVERFLOW)
981 0 : new_lb = wi::max_value (prec, sgn);
982 : else
983 53301946 : new_lb = wmin;
984 :
985 61192044 : if (max_ovf == wi::OVF_UNDERFLOW)
986 0 : new_ub = wi::min_value (prec, sgn);
987 61192044 : else if (max_ovf == wi::OVF_OVERFLOW)
988 12387372 : new_ub = wi::max_value (prec, sgn);
989 : else
990 48804931 : new_ub = wmax;
991 :
992 61192044 : r.set (type, new_lb, new_ub);
993 61193579 : }
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 89531260 : create_possibly_reversed_range (irange &r, tree type,
1002 : const wide_int &new_lb, const wide_int &new_ub)
1003 : {
1004 89531260 : signop s = TYPE_SIGN (type);
1005 : // If the bounds are swapped, treat the result as if an overflow occurred.
1006 89531260 : if (wi::gt_p (new_lb, new_ub, s))
1007 17513378 : value_range_from_overflowed_bounds (r, type, new_lb, new_ub);
1008 : else
1009 : // Otherwise it's just a normal range.
1010 72017882 : r.set (type, new_lb, new_ub);
1011 89531260 : }
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 86915960 : get_bool_state (vrange &r, const vrange &lhs, tree val_type)
1018 : {
1019 : // If there is no result, then this is unexecutable.
1020 86915960 : if (lhs.undefined_p ())
1021 : {
1022 0 : r.set_undefined ();
1023 0 : return BRS_EMPTY;
1024 : }
1025 :
1026 86915960 : 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 43158530 : if (lhs.contains_p (build_zero_cst (lhs.type ())))
1032 : {
1033 210891 : r.set_varying (val_type);
1034 210891 : 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 6221419 : operator_equal::op1_op2_relation (const irange &lhs, const irange &,
1053 : const irange &) const
1054 : {
1055 6221419 : if (lhs.undefined_p ())
1056 : return VREL_UNDEFINED;
1057 :
1058 : // FALSE = op1 == op2 indicates NE_EXPR.
1059 6221419 : if (lhs.zero_p ())
1060 : return VREL_NE;
1061 :
1062 : // TRUE = op1 == op2 indicates EQ_EXPR.
1063 3448587 : if (!lhs.contains_zero_p ())
1064 3423311 : return VREL_EQ;
1065 : return VREL_VARYING;
1066 : }
1067 :
1068 : bool
1069 18645060 : operator_equal::fold_range (irange &r, tree type,
1070 : const irange &op1,
1071 : const irange &op2,
1072 : relation_trio rel) const
1073 : {
1074 18645060 : 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 18601616 : bool op1_const = wi::eq_p (op1.lower_bound (), op1.upper_bound ());
1080 18601616 : bool op2_const = wi::eq_p (op2.lower_bound (), op2.upper_bound ());
1081 18601602 : if (op1_const && op2_const)
1082 : {
1083 460179 : if (wi::eq_p (op1.lower_bound (), op2.upper_bound()))
1084 188769 : r = range_true (type);
1085 : else
1086 271410 : 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 18141423 : int_range_max tmp = op1;
1093 18141423 : tmp.intersect (op2);
1094 18141423 : if (tmp.undefined_p ())
1095 262143 : r = range_false (type);
1096 : // Check if a constant cannot satisfy the bitmask requirements.
1097 33293105 : else if (op2_const && !op1.get_bitmask ().member_p (op2.lower_bound ()))
1098 0 : r = range_false (type);
1099 17962997 : else if (op1_const && !op2.get_bitmask ().member_p (op1.lower_bound ()))
1100 0 : r = range_false (type);
1101 : else
1102 17879280 : r = range_true_and_false (type);
1103 18141423 : }
1104 : return true;
1105 : }
1106 :
1107 : bool
1108 12088824 : operator_equal::op1_range (irange &r, tree type,
1109 : const irange &lhs,
1110 : const irange &op2,
1111 : relation_trio) const
1112 : {
1113 12088824 : switch (get_bool_state (r, lhs, type))
1114 : {
1115 3911480 : case BRS_TRUE:
1116 : // If it's true, the result is the same as OP2.
1117 3911480 : r = op2;
1118 3911480 : break;
1119 :
1120 8146834 : case BRS_FALSE:
1121 : // If the result is false, the only time we know anything is
1122 : // if OP2 is a constant.
1123 8146834 : if (!op2.undefined_p ()
1124 24440502 : && wi::eq_p (op2.lower_bound(), op2.upper_bound()))
1125 : {
1126 6575766 : r = op2;
1127 6575766 : if (!r.invert ())
1128 : return false;
1129 : }
1130 : else
1131 1571068 : r.set_varying (type);
1132 : break;
1133 :
1134 : default:
1135 : break;
1136 : }
1137 : return true;
1138 : }
1139 :
1140 : bool
1141 1523607 : operator_equal::op2_range (irange &r, tree type,
1142 : const irange &lhs,
1143 : const irange &op1,
1144 : relation_trio rel) const
1145 : {
1146 1523607 : 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 10777075 : operator_not_equal::op1_op2_relation (const irange &lhs, const irange &,
1162 : const irange &) const
1163 : {
1164 10777075 : if (lhs.undefined_p ())
1165 : return VREL_UNDEFINED;
1166 :
1167 : // FALSE = op1 != op2 indicates EQ_EXPR.
1168 10777075 : if (lhs.zero_p ())
1169 : return VREL_EQ;
1170 :
1171 : // TRUE = op1 != op2 indicates NE_EXPR.
1172 5056080 : if (!lhs.contains_zero_p ())
1173 5013434 : return VREL_NE;
1174 : return VREL_VARYING;
1175 : }
1176 :
1177 : bool
1178 28192262 : operator_not_equal::fold_range (irange &r, tree type,
1179 : const irange &op1,
1180 : const irange &op2,
1181 : relation_trio rel) const
1182 : {
1183 28192262 : 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 28169762 : bool op1_const = wi::eq_p (op1.lower_bound (), op1.upper_bound ());
1189 28169762 : bool op2_const = wi::eq_p (op2.lower_bound (), op2.upper_bound ());
1190 28169378 : if (op1_const && op2_const)
1191 : {
1192 1964762 : if (wi::ne_p (op1.lower_bound (), op2.upper_bound()))
1193 1332826 : r = range_true (type);
1194 : else
1195 631932 : 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 26204620 : int_range_max tmp = op1;
1202 26204620 : tmp.intersect (op2);
1203 26204620 : if (tmp.undefined_p ())
1204 328087 : r = range_true (type);
1205 : // Check if a constant cannot satisfy the bitmask requirements.
1206 47004124 : else if (op2_const && !op1.get_bitmask ().member_p (op2.lower_bound ()))
1207 0 : r = range_true (type);
1208 26010539 : else if (op1_const && !op2.get_bitmask ().member_p (op1.lower_bound ()))
1209 0 : r = range_true (type);
1210 : else
1211 25876533 : r = range_true_and_false (type);
1212 26204620 : }
1213 : return true;
1214 : }
1215 :
1216 : bool
1217 21269364 : operator_not_equal::op1_range (irange &r, tree type,
1218 : const irange &lhs,
1219 : const irange &op2,
1220 : relation_trio) const
1221 : {
1222 21269364 : switch (get_bool_state (r, lhs, type))
1223 : {
1224 12754164 : case BRS_TRUE:
1225 : // If the result is true, the only time we know anything is if
1226 : // OP2 is a constant.
1227 12754164 : if (!op2.undefined_p ()
1228 38262492 : && wi::eq_p (op2.lower_bound(), op2.upper_bound()))
1229 : {
1230 10327932 : r = op2;
1231 10327932 : if (!r.invert ())
1232 : return false;
1233 : }
1234 : else
1235 2426232 : r.set_varying (type);
1236 : break;
1237 :
1238 8486790 : case BRS_FALSE:
1239 : // If it's false, the result is the same as OP2.
1240 8486790 : r = op2;
1241 8486790 : break;
1242 :
1243 : default:
1244 : break;
1245 : }
1246 : return true;
1247 : }
1248 :
1249 :
1250 : bool
1251 2628044 : operator_not_equal::op2_range (irange &r, tree type,
1252 : const irange &lhs,
1253 : const irange &op1,
1254 : relation_trio rel) const
1255 : {
1256 2628044 : 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 6443279 : build_lt (irange &r, tree type, const wide_int &val)
1263 : {
1264 6443279 : wi::overflow_type ov;
1265 6443279 : wide_int lim;
1266 6443279 : signop sgn = TYPE_SIGN (type);
1267 :
1268 : // Signed 1 bit cannot represent 1 for subtraction.
1269 6443279 : if (sgn == SIGNED)
1270 4318783 : lim = wi::add (val, -1, sgn, &ov);
1271 : else
1272 2124559 : lim = wi::sub (val, 1, sgn, &ov);
1273 :
1274 : // If val - 1 underflows, check if X < MIN, which is an empty range.
1275 6443279 : if (ov)
1276 197 : r.set_undefined ();
1277 : else
1278 6443145 : r = int_range<1> (type, min_limit (type), lim);
1279 6443279 : }
1280 :
1281 : // (X <= VAL) produces the range of [MIN, VAL].
1282 :
1283 : static void
1284 14138330 : build_le (irange &r, tree type, const wide_int &val)
1285 : {
1286 14138330 : r = int_range<1> (type, min_limit (type), val);
1287 14138330 : }
1288 :
1289 : // (X > VAL) produces the range of [VAL + 1, MAX].
1290 :
1291 : static void
1292 11071724 : build_gt (irange &r, tree type, const wide_int &val)
1293 : {
1294 11071724 : wi::overflow_type ov;
1295 11071724 : wide_int lim;
1296 11071724 : signop sgn = TYPE_SIGN (type);
1297 :
1298 : // Signed 1 bit cannot represent 1 for addition.
1299 11071724 : if (sgn == SIGNED)
1300 6058908 : lim = wi::sub (val, -1, sgn, &ov);
1301 : else
1302 5012906 : lim = wi::add (val, 1, sgn, &ov);
1303 : // If val + 1 overflows, check is for X > MAX, which is an empty range.
1304 11071724 : if (ov)
1305 0 : r.set_undefined ();
1306 : else
1307 11071814 : r = int_range<1> (type, lim, max_limit (type));
1308 11071724 : }
1309 :
1310 : // (X >= val) produces the range of [VAL, MAX].
1311 :
1312 : static void
1313 7181534 : build_ge (irange &r, tree type, const wide_int &val)
1314 : {
1315 7181534 : r = int_range<1> (type, val, max_limit (type));
1316 7181534 : }
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 12807899 : operator_lt::op1_op2_relation (const irange &lhs, const irange &,
1330 : const irange &) const
1331 : {
1332 12807899 : if (lhs.undefined_p ())
1333 : return VREL_UNDEFINED;
1334 :
1335 : // FALSE = op1 < op2 indicates GE_EXPR.
1336 12807899 : if (lhs.zero_p ())
1337 : return VREL_GE;
1338 :
1339 : // TRUE = op1 < op2 indicates LT_EXPR.
1340 6469137 : if (!lhs.contains_zero_p ())
1341 6456798 : return VREL_LT;
1342 : return VREL_VARYING;
1343 : }
1344 :
1345 : bool
1346 6990501 : operator_lt::fold_range (irange &r, tree type,
1347 : const irange &op1,
1348 : const irange &op2,
1349 : relation_trio rel) const
1350 : {
1351 6990501 : if (relop_early_resolve (r, type, op1, op2, rel, VREL_LT))
1352 : return true;
1353 :
1354 6961726 : signop sign = TYPE_SIGN (op1.type ());
1355 6961726 : gcc_checking_assert (sign == TYPE_SIGN (op2.type ()));
1356 :
1357 6961762 : if (wi::lt_p (op1.upper_bound (), op2.lower_bound (), sign))
1358 50900 : r = range_true (type);
1359 6910862 : else if (!wi::lt_p (op1.lower_bound (), op2.upper_bound (), sign))
1360 67745 : r = range_false (type);
1361 : // Use nonzero bits to determine if < 0 is false.
1362 8885767 : else if (op2.zero_p () && !wi::neg_p (op1.get_nonzero_bits (), sign))
1363 0 : r = range_false (type);
1364 : else
1365 6843081 : r = range_true_and_false (type);
1366 : return true;
1367 : }
1368 :
1369 : bool
1370 5719450 : operator_lt::op1_range (irange &r, tree type,
1371 : const irange &lhs,
1372 : const irange &op2,
1373 : relation_trio) const
1374 : {
1375 5719450 : if (op2.undefined_p ())
1376 : return false;
1377 :
1378 5719450 : switch (get_bool_state (r, lhs, type))
1379 : {
1380 2449514 : case BRS_TRUE:
1381 2449514 : build_lt (r, type, op2.upper_bound ());
1382 2449514 : break;
1383 :
1384 3263731 : case BRS_FALSE:
1385 3263731 : build_ge (r, type, op2.lower_bound ());
1386 3263731 : break;
1387 :
1388 : default:
1389 : break;
1390 : }
1391 : return true;
1392 : }
1393 :
1394 : bool
1395 3964221 : operator_lt::op2_range (irange &r, tree type,
1396 : const irange &lhs,
1397 : const irange &op1,
1398 : relation_trio) const
1399 : {
1400 3964221 : if (op1.undefined_p ())
1401 : return false;
1402 :
1403 3964221 : switch (get_bool_state (r, lhs, type))
1404 : {
1405 1676957 : case BRS_TRUE:
1406 1676957 : build_gt (r, type, op1.lower_bound ());
1407 1676957 : break;
1408 :
1409 2281607 : case BRS_FALSE:
1410 2281607 : build_le (r, type, op1.upper_bound ());
1411 2281607 : 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 4467040 : operator_le::op1_op2_relation (const irange &lhs, const irange &,
1431 : const irange &) const
1432 : {
1433 4467040 : if (lhs.undefined_p ())
1434 : return VREL_UNDEFINED;
1435 :
1436 : // FALSE = op1 <= op2 indicates GT_EXPR.
1437 4467040 : if (lhs.zero_p ())
1438 : return VREL_GT;
1439 :
1440 : // TRUE = op1 <= op2 indicates LE_EXPR.
1441 2486877 : if (!lhs.contains_zero_p ())
1442 2474165 : return VREL_LE;
1443 : return VREL_VARYING;
1444 : }
1445 :
1446 : bool
1447 5639560 : operator_le::fold_range (irange &r, tree type,
1448 : const irange &op1,
1449 : const irange &op2,
1450 : relation_trio rel) const
1451 : {
1452 5639560 : if (relop_early_resolve (r, type, op1, op2, rel, VREL_LE))
1453 : return true;
1454 :
1455 5625054 : signop sign = TYPE_SIGN (op1.type ());
1456 5625054 : gcc_checking_assert (sign == TYPE_SIGN (op2.type ()));
1457 :
1458 5625058 : if (wi::le_p (op1.upper_bound (), op2.lower_bound (), sign))
1459 293963 : r = range_true (type);
1460 5331095 : else if (!wi::le_p (op1.lower_bound (), op2.upper_bound (), sign))
1461 64892 : r = range_false (type);
1462 : else
1463 5266199 : r = range_true_and_false (type);
1464 : return true;
1465 : }
1466 :
1467 : bool
1468 6826829 : operator_le::op1_range (irange &r, tree type,
1469 : const irange &lhs,
1470 : const irange &op2,
1471 : relation_trio) const
1472 : {
1473 6826829 : if (op2.undefined_p ())
1474 : return false;
1475 :
1476 6826829 : switch (get_bool_state (r, lhs, type))
1477 : {
1478 3320276 : case BRS_TRUE:
1479 3320276 : build_le (r, type, op2.upper_bound ());
1480 3320276 : break;
1481 :
1482 3493121 : case BRS_FALSE:
1483 3493121 : build_gt (r, type, op2.lower_bound ());
1484 3493121 : break;
1485 :
1486 : default:
1487 : break;
1488 : }
1489 : return true;
1490 : }
1491 :
1492 : bool
1493 1116863 : operator_le::op2_range (irange &r, tree type,
1494 : const irange &lhs,
1495 : const irange &op1,
1496 : relation_trio) const
1497 : {
1498 1116863 : if (op1.undefined_p ())
1499 : return false;
1500 :
1501 1116863 : switch (get_bool_state (r, lhs, type))
1502 : {
1503 490593 : case BRS_TRUE:
1504 490593 : build_ge (r, type, op1.lower_bound ());
1505 490593 : break;
1506 :
1507 621106 : case BRS_FALSE:
1508 621106 : build_lt (r, type, op1.upper_bound ());
1509 621106 : 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 12718062 : operator_gt::op1_op2_relation (const irange &lhs, const irange &,
1529 : const irange &) const
1530 : {
1531 12718062 : if (lhs.undefined_p ())
1532 : return VREL_UNDEFINED;
1533 :
1534 : // FALSE = op1 > op2 indicates LE_EXPR.
1535 12718062 : if (lhs.zero_p ())
1536 : return VREL_LE;
1537 :
1538 : // TRUE = op1 > op2 indicates GT_EXPR.
1539 6814882 : if (!lhs.contains_zero_p ())
1540 6795460 : return VREL_GT;
1541 : return VREL_VARYING;
1542 : }
1543 :
1544 : bool
1545 12532069 : operator_gt::fold_range (irange &r, tree type,
1546 : const irange &op1, const irange &op2,
1547 : relation_trio rel) const
1548 : {
1549 12532069 : if (relop_early_resolve (r, type, op1, op2, rel, VREL_GT))
1550 : return true;
1551 :
1552 12474805 : signop sign = TYPE_SIGN (op1.type ());
1553 12474805 : gcc_checking_assert (sign == TYPE_SIGN (op2.type ()));
1554 :
1555 12474831 : if (wi::gt_p (op1.lower_bound (), op2.upper_bound (), sign))
1556 148631 : r = range_true (type);
1557 12326200 : else if (!wi::gt_p (op1.upper_bound (), op2.lower_bound (), sign))
1558 507751 : r = range_false (type);
1559 : else
1560 11818423 : r = range_true_and_false (type);
1561 : return true;
1562 : }
1563 :
1564 : bool
1565 13112102 : operator_gt::op1_range (irange &r, tree type,
1566 : const irange &lhs, const irange &op2,
1567 : relation_trio) const
1568 : {
1569 13112102 : if (op2.undefined_p ())
1570 : return false;
1571 :
1572 13112102 : switch (get_bool_state (r, lhs, type))
1573 : {
1574 5358553 : case BRS_TRUE:
1575 5358553 : build_gt (r, type, op2.lower_bound ());
1576 5358553 : break;
1577 :
1578 7741934 : case BRS_FALSE:
1579 7741934 : build_le (r, type, op2.upper_bound ());
1580 7741934 : break;
1581 :
1582 : default:
1583 : break;
1584 : }
1585 : return true;
1586 : }
1587 :
1588 : bool
1589 3700835 : operator_gt::op2_range (irange &r, tree type,
1590 : const irange &lhs,
1591 : const irange &op1,
1592 : relation_trio) const
1593 : {
1594 3700835 : if (op1.undefined_p ())
1595 : return false;
1596 :
1597 3700835 : switch (get_bool_state (r, lhs, type))
1598 : {
1599 2213746 : case BRS_TRUE:
1600 2213746 : build_lt (r, type, op1.upper_bound ());
1601 2213746 : break;
1602 :
1603 1476837 : case BRS_FALSE:
1604 1476837 : build_ge (r, type, op1.lower_bound ());
1605 1476837 : 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 3996651 : operator_ge::op1_op2_relation (const irange &lhs, const irange &,
1625 : const irange &) const
1626 : {
1627 3996651 : if (lhs.undefined_p ())
1628 : return VREL_UNDEFINED;
1629 :
1630 : // FALSE = op1 >= op2 indicates LT_EXPR.
1631 3996651 : if (lhs.zero_p ())
1632 : return VREL_LT;
1633 :
1634 : // TRUE = op1 >= op2 indicates GE_EXPR.
1635 2137367 : if (!lhs.contains_zero_p ())
1636 2125347 : return VREL_GE;
1637 : return VREL_VARYING;
1638 : }
1639 :
1640 : bool
1641 2720132 : operator_ge::fold_range (irange &r, tree type,
1642 : const irange &op1,
1643 : const irange &op2,
1644 : relation_trio rel) const
1645 : {
1646 2720132 : if (relop_early_resolve (r, type, op1, op2, rel, VREL_GE))
1647 : return true;
1648 :
1649 2707244 : signop sign = TYPE_SIGN (op1.type ());
1650 2707244 : gcc_checking_assert (sign == TYPE_SIGN (op2.type ()));
1651 :
1652 2707276 : if (wi::ge_p (op1.lower_bound (), op2.upper_bound (), sign))
1653 191024 : r = range_true (type);
1654 2516252 : else if (!wi::ge_p (op1.upper_bound (), op2.lower_bound (), sign))
1655 7012 : r = range_false (type);
1656 : else
1657 2509208 : r = range_true_and_false (type);
1658 : return true;
1659 : }
1660 :
1661 : bool
1662 3118503 : operator_ge::op1_range (irange &r, tree type,
1663 : const irange &lhs,
1664 : const irange &op2,
1665 : relation_trio) const
1666 : {
1667 3118503 : if (op2.undefined_p ())
1668 : return false;
1669 :
1670 3118503 : switch (get_bool_state (r, lhs, type))
1671 : {
1672 1950373 : case BRS_TRUE:
1673 1950373 : build_ge (r, type, op2.lower_bound ());
1674 1950373 : break;
1675 :
1676 1158913 : case BRS_FALSE:
1677 1158913 : build_lt (r, type, op2.upper_bound ());
1678 1158913 : break;
1679 :
1680 : default:
1681 : break;
1682 : }
1683 : return true;
1684 : }
1685 :
1686 : bool
1687 1343106 : operator_ge::op2_range (irange &r, tree type,
1688 : const irange &lhs,
1689 : const irange &op1,
1690 : relation_trio) const
1691 : {
1692 1343106 : if (op1.undefined_p ())
1693 : return false;
1694 :
1695 1343106 : switch (get_bool_state (r, lhs, type))
1696 : {
1697 794513 : case BRS_TRUE:
1698 794513 : build_le (r, type, op1.upper_bound ());
1699 794513 : break;
1700 :
1701 543093 : case BRS_FALSE:
1702 543093 : build_gt (r, type, op1.lower_bound ());
1703 543093 : break;
1704 :
1705 : default:
1706 : break;
1707 : }
1708 : return true;
1709 : }
1710 :
1711 :
1712 : void
1713 50173361 : operator_plus::update_bitmask (irange &r, const irange &lh,
1714 : const irange &rh) const
1715 : {
1716 50173361 : update_known_bitmask (r, PLUS_EXPR, lh, rh);
1717 50173361 : }
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 46194351 : operator_plus::lhs_op1_relation (const irange &lhs,
1724 : const irange &op1,
1725 : const irange &op2,
1726 : relation_kind) const
1727 : {
1728 46194351 : if (lhs.undefined_p () || op1.undefined_p () || op2.undefined_p ())
1729 : return VREL_VARYING;
1730 :
1731 46159041 : tree type = lhs.type ();
1732 46159041 : unsigned prec = TYPE_PRECISION (type);
1733 46159041 : wi::overflow_type ovf1, ovf2;
1734 46159041 : signop sign = TYPE_SIGN (type);
1735 :
1736 : // LHS = OP1 + 0 indicates LHS == OP1.
1737 46159041 : if (op2.zero_p ())
1738 : return VREL_EQ;
1739 :
1740 45952269 : if (TYPE_OVERFLOW_WRAPS (type))
1741 : {
1742 26217714 : wi::add (op1.lower_bound (), op2.lower_bound (), sign, &ovf1);
1743 26217932 : wi::add (op1.upper_bound (), op2.upper_bound (), sign, &ovf2);
1744 : }
1745 : else
1746 19734991 : ovf1 = ovf2 = wi::OVF_NONE;
1747 :
1748 : // Never wrapping additions.
1749 45952269 : if (!ovf1 && !ovf2)
1750 : {
1751 : // Positive op2 means lhs > op1.
1752 27276895 : if (wi::gt_p (op2.lower_bound (), wi::zero (prec), sign))
1753 : return VREL_GT;
1754 10483195 : if (wi::ge_p (op2.lower_bound (), wi::zero (prec), sign))
1755 : return VREL_GE;
1756 :
1757 : // Negative op2 means lhs < op1.
1758 8796741 : if (wi::lt_p (op2.upper_bound (), wi::zero (prec), sign))
1759 : return VREL_LT;
1760 5402358 : if (wi::le_p (op2.upper_bound (), wi::zero (prec), sign))
1761 : return VREL_LE;
1762 : }
1763 : // Always wrapping additions.
1764 18675749 : else if (ovf1 && ovf1 == ovf2)
1765 : {
1766 : // Positive op2 means lhs < op1.
1767 730260 : 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 23334548 : if (!range_includes_zero_p (op2))
1781 11758222 : 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 8117082 : operator_plus::lhs_op2_relation (const irange &lhs, const irange &op1,
1791 : const irange &op2, relation_kind rel) const
1792 : {
1793 8117082 : return lhs_op1_relation (lhs, op2, op1, rel);
1794 : }
1795 :
1796 : void
1797 74322249 : 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 74322249 : wi::overflow_type ov_lb, ov_ub;
1802 74322249 : signop s = TYPE_SIGN (type);
1803 74322249 : wide_int new_lb = wi::add (lh_lb, rh_lb, s, &ov_lb);
1804 74322249 : wide_int new_ub = wi::add (lh_ub, rh_ub, s, &ov_ub);
1805 74322249 : value_range_with_overflow (r, type, new_lb, new_ub, ov_lb, ov_ub);
1806 74322249 : }
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 788817 : plus_minus_ranges (irange &r_ov, irange &r_normal, const irange &offset,
1816 : bool add_p)
1817 : {
1818 788817 : 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 788817 : 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 14150 : wide_int off = offset.lower_bound ();
1826 14150 : if (wi::neg_p (off, SIGNED))
1827 : {
1828 1196 : add_p = !add_p;
1829 1196 : off = wi::neg (off);
1830 : }
1831 :
1832 14150 : wi::overflow_type ov;
1833 14150 : tree type = offset.type ();
1834 14150 : unsigned prec = TYPE_PRECISION (type);
1835 14150 : wide_int ub;
1836 14150 : wide_int lb;
1837 : // calculate the normal range and relation for the operation.
1838 14150 : if (add_p)
1839 : {
1840 : // [ 0 , INF - OFF]
1841 12954 : lb = wi::zero (prec);
1842 12954 : ub = wi::sub (irange_val_max (type), off, UNSIGNED, &ov);
1843 12954 : kind = VREL_GT;
1844 : }
1845 : else
1846 : {
1847 : // [ OFF, INF ]
1848 1196 : lb = off;
1849 1196 : ub = irange_val_max (type);
1850 1196 : kind = VREL_LT;
1851 : }
1852 14150 : int_range<2> normal_range (type, lb, ub);
1853 14150 : int_range<2> ov_range (type, lb, ub, VR_ANTI_RANGE);
1854 :
1855 14150 : r_ov = ov_range;
1856 14150 : r_normal = normal_range;
1857 14150 : return kind;
1858 14150 : }
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 10269006 : adjust_op1_for_overflow (irange &r, const irange &op2, relation_kind rel,
1871 : bool add_p)
1872 : {
1873 10269006 : if (r.undefined_p ())
1874 : return;
1875 10269004 : tree type = r.type ();
1876 : // Check for unsigned overflow and calculate the overflow part.
1877 10269004 : signop s = TYPE_SIGN (type);
1878 10269004 : if (!TYPE_OVERFLOW_WRAPS (type) || s == SIGNED)
1879 : return;
1880 :
1881 : // Only work with <, <=, >, >= relations.
1882 5198937 : if (!relation_lt_le_gt_ge_p (rel))
1883 : return;
1884 :
1885 : // Get the ranges for this offset.
1886 788817 : int_range_max normal, overflow;
1887 788817 : relation_kind k = plus_minus_ranges (overflow, normal, op2, add_p);
1888 :
1889 : // VREL_VARYING means there are no adjustments.
1890 788817 : if (k == VREL_VARYING)
1891 : return;
1892 :
1893 : // If the relations match use the normal range, otherwise use overflow range.
1894 14150 : if (relation_intersect (k, rel) == k)
1895 10090 : r.intersect (normal);
1896 : else
1897 4060 : r.intersect (overflow);
1898 : return;
1899 788817 : }
1900 :
1901 : bool
1902 9235464 : operator_plus::op1_range (irange &r, tree type,
1903 : const irange &lhs,
1904 : const irange &op2,
1905 : relation_trio trio) const
1906 : {
1907 9235464 : if (lhs.undefined_p ())
1908 : return false;
1909 : // Start with the default operation.
1910 9235464 : range_op_handler minus (MINUS_EXPR);
1911 9235464 : if (!minus)
1912 : return false;
1913 9235464 : bool res = minus.fold_range (r, type, lhs, op2);
1914 9235464 : relation_kind rel = trio.lhs_op1 ();
1915 : // Check for a relation refinement.
1916 9235464 : if (res)
1917 9235464 : adjust_op1_for_overflow (r, op2, rel, true /* PLUS_EXPR */);
1918 : return res;
1919 : }
1920 :
1921 : bool
1922 2075539 : operator_plus::op2_range (irange &r, tree type,
1923 : const irange &lhs,
1924 : const irange &op1,
1925 : relation_trio rel) const
1926 : {
1927 2075539 : 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 18834766 : operator_minus::update_bitmask (irange &r, const irange &lh,
1998 : const irange &rh) const
1999 : {
2000 18834766 : update_known_bitmask (r, MINUS_EXPR, lh, rh);
2001 18834766 : }
2002 :
2003 : void
2004 26410767 : 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 26410767 : wi::overflow_type ov_lb, ov_ub;
2009 26410767 : signop s = TYPE_SIGN (type);
2010 26410767 : wide_int new_lb = wi::sub (lh_lb, rh_ub, s, &ov_lb);
2011 26410767 : wide_int new_ub = wi::sub (lh_ub, rh_lb, s, &ov_ub);
2012 26410767 : value_range_with_overflow (r, type, new_lb, new_ub, ov_lb, ov_ub);
2013 26410767 : }
2014 :
2015 :
2016 : // Return the relation between LHS and OP1 based on the relation between
2017 : // OP1 and OP2.
2018 :
2019 : relation_kind
2020 4962077 : operator_minus::lhs_op1_relation (const irange &, const irange &op1,
2021 : const irange &, relation_kind rel) const
2022 : {
2023 4962077 : if (!op1.undefined_p () && TYPE_SIGN (op1.type ()) == UNSIGNED)
2024 2393923 : switch (rel)
2025 : {
2026 57412 : case VREL_GT:
2027 57412 : case VREL_GE:
2028 57412 : 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 21739596 : 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 21739596 : if (rel == VREL_VARYING)
2046 : return false;
2047 :
2048 283472 : int_range<2> rel_range;
2049 283472 : unsigned prec = TYPE_PRECISION (type);
2050 283472 : signop sgn = TYPE_SIGN (type);
2051 :
2052 : // == and != produce [0,0] and ~[0,0] regardless of wrapping.
2053 283472 : if (rel == VREL_EQ)
2054 9806 : rel_range = int_range<2> (type, wi::zero (prec), wi::zero (prec));
2055 273666 : else if (rel == VREL_NE)
2056 111096 : rel_range = int_range<2> (type, wi::zero (prec), wi::zero (prec),
2057 55548 : VR_ANTI_RANGE);
2058 218118 : else if (TYPE_OVERFLOW_WRAPS (type))
2059 : {
2060 123897 : 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 45181 : case VREL_GT:
2065 45181 : case VREL_LT:
2066 90362 : rel_range = int_range<2> (type, wi::zero (prec), wi::zero (prec),
2067 45181 : VR_ANTI_RANGE);
2068 45181 : break;
2069 : default:
2070 : return false;
2071 : }
2072 : }
2073 : else
2074 : {
2075 94221 : switch (rel)
2076 : {
2077 : // op1 > op2, op1 - op2 can be restricted to [1, +INF]
2078 24089 : case VREL_GT:
2079 48178 : rel_range = int_range<2> (type, wi::one (prec),
2080 48178 : wi::max_value (prec, sgn));
2081 24089 : break;
2082 : // op1 >= op2, op1 - op2 can be restricted to [0, +INF]
2083 69348 : case VREL_GE:
2084 138696 : rel_range = int_range<2> (type, wi::zero (prec),
2085 138696 : wi::max_value (prec, sgn));
2086 69348 : break;
2087 : // op1 < op2, op1 - op2 can be restricted to [-INF, -1]
2088 424 : case VREL_LT:
2089 848 : rel_range = int_range<2> (type, wi::min_value (prec, sgn),
2090 424 : wi::minus_one (prec));
2091 424 : 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 204700 : lhs_range.intersect (rel_range);
2102 204700 : return true;
2103 283472 : }
2104 :
2105 : bool
2106 18834766 : 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 18834766 : return minus_op1_op2_relation_effect (lhs_range, type, op1_range, op2_range,
2112 18834766 : rel);
2113 : }
2114 :
2115 : bool
2116 1033542 : operator_minus::op1_range (irange &r, tree type,
2117 : const irange &lhs,
2118 : const irange &op2,
2119 : relation_trio trio) const
2120 : {
2121 1033542 : if (lhs.undefined_p ())
2122 : return false;
2123 : // Start with the default operation.
2124 1033542 : range_op_handler minus (PLUS_EXPR);
2125 1033542 : if (!minus)
2126 : return false;
2127 1033542 : bool res = minus.fold_range (r, type, lhs, op2);
2128 1033542 : relation_kind rel = trio.lhs_op1 ();
2129 1033542 : if (res)
2130 1033542 : adjust_op1_for_overflow (r, op2, rel, false /* PLUS_EXPR */);
2131 : return res;
2132 :
2133 : }
2134 :
2135 : bool
2136 1784160 : operator_minus::op2_range (irange &r, tree type,
2137 : const irange &lhs,
2138 : const irange &op1,
2139 : relation_trio) const
2140 : {
2141 1784160 : if (lhs.undefined_p ())
2142 : return false;
2143 1784160 : return fold_range (r, type, op1, lhs);
2144 : }
2145 :
2146 : void
2147 1001867 : operator_min::update_bitmask (irange &r, const irange &lh,
2148 : const irange &rh) const
2149 : {
2150 1001867 : update_known_bitmask (r, MIN_EXPR, lh, rh);
2151 1001867 : }
2152 :
2153 : void
2154 1533405 : 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 1533405 : signop s = TYPE_SIGN (type);
2159 1533405 : wide_int new_lb = wi::min (lh_lb, rh_lb, s);
2160 1533405 : wide_int new_ub = wi::min (lh_ub, rh_ub, s);
2161 1533405 : value_range_with_overflow (r, type, new_lb, new_ub);
2162 1533405 : }
2163 :
2164 :
2165 : void
2166 834366 : operator_max::update_bitmask (irange &r, const irange &lh,
2167 : const irange &rh) const
2168 : {
2169 834366 : update_known_bitmask (r, MAX_EXPR, lh, rh);
2170 834366 : }
2171 :
2172 : void
2173 1032392 : 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 1032392 : signop s = TYPE_SIGN (type);
2178 1032392 : wide_int new_lb = wi::max (lh_lb, rh_lb, s);
2179 1032392 : wide_int new_ub = wi::max (lh_ub, rh_ub, s);
2180 1032392 : value_range_with_overflow (r, type, new_lb, new_ub);
2181 1032392 : }
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 15341835 : 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 15341835 : wide_int cp1, cp2, cp3, cp4;
2205 : // Default to varying.
2206 15341835 : r.set_varying (type);
2207 :
2208 : // Compute the 4 cross operations, bailing if we get an overflow we
2209 : // can't handle.
2210 15341835 : if (wi_op_overflows (cp1, type, lh_lb, rh_lb))
2211 : return;
2212 15341797 : if (wi::eq_p (lh_lb, lh_ub))
2213 4415626 : cp3 = cp1;
2214 10926171 : else if (wi_op_overflows (cp3, type, lh_ub, rh_lb))
2215 : return;
2216 15341797 : if (wi::eq_p (rh_lb, rh_ub))
2217 11861151 : cp2 = cp1;
2218 3480646 : else if (wi_op_overflows (cp2, type, lh_lb, rh_ub))
2219 : return;
2220 15339540 : if (wi::eq_p (lh_lb, lh_ub))
2221 4415608 : cp4 = cp2;
2222 10923932 : else if (wi_op_overflows (cp4, type, lh_ub, rh_ub))
2223 : return;
2224 :
2225 : // Order pairs.
2226 15339540 : signop sign = TYPE_SIGN (type);
2227 15339540 : if (wi::gt_p (cp1, cp2, sign))
2228 1589325 : std::swap (cp1, cp2);
2229 15339540 : if (wi::gt_p (cp3, cp4, sign))
2230 1553920 : std::swap (cp3, cp4);
2231 :
2232 : // Choose min and max from the ordered pairs.
2233 15339540 : wide_int res_lb = wi::min (cp1, cp3, sign);
2234 15339540 : wide_int res_ub = wi::max (cp2, cp4, sign);
2235 15339540 : value_range_with_overflow (r, type, res_lb, res_ub);
2236 15347890 : }
2237 :
2238 :
2239 : void
2240 14441112 : operator_mult::update_bitmask (irange &r, const irange &lh,
2241 : const irange &rh) const
2242 : {
2243 14441112 : update_known_bitmask (r, MULT_EXPR, lh, rh);
2244 14441112 : }
2245 :
2246 : bool
2247 1197653 : operator_mult::op1_range (irange &r, tree type,
2248 : const irange &lhs, const irange &op2,
2249 : relation_trio) const
2250 : {
2251 1197653 : 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 1197653 : if (TYPE_OVERFLOW_WRAPS (type))
2258 : return false;
2259 :
2260 339827 : wide_int offset;
2261 339827 : if (op2.singleton_p (offset) && offset != 0)
2262 232993 : 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 106834 : if (!lhs.contains_p (wi::zero (TYPE_PRECISION (lhs.type ()))))
2266 : {
2267 25741 : r.set_nonzero (type);
2268 25741 : return true;
2269 : }
2270 : return false;
2271 339827 : }
2272 :
2273 : bool
2274 131550 : operator_mult::op2_range (irange &r, tree type,
2275 : const irange &lhs, const irange &op1,
2276 : relation_trio rel) const
2277 : {
2278 131550 : return operator_mult::op1_range (r, type, lhs, op1, rel.swap_op1_op2 ());
2279 : }
2280 :
2281 : bool
2282 15058910 : operator_mult::wi_op_overflows (wide_int &res, tree type,
2283 : const wide_int &w0, const wide_int &w1) const
2284 : {
2285 15058910 : wi::overflow_type overflow = wi::OVF_NONE;
2286 15058910 : signop sign = TYPE_SIGN (type);
2287 15058910 : res = wi::mul (w0, w1, sign, &overflow);
2288 15058910 : 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 7275332 : if (sign == UNSIGNED || w0.sign_mask () == w1.sign_mask ())
2293 4035888 : res = wi::max_value (w0.get_precision (), sign);
2294 : else
2295 3239658 : res = wi::min_value (w0.get_precision (), sign);
2296 : return false;
2297 : }
2298 7783578 : return overflow;
2299 : }
2300 :
2301 : void
2302 18215577 : 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 18215577 : if (TYPE_OVERFLOW_UNDEFINED (type))
2307 : {
2308 6137191 : wi_cross_product (r, type, lh_lb, lh_ub, rh_lb, rh_ub);
2309 6137191 : 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 12078386 : signop sign = TYPE_SIGN (type);
2323 12078386 : unsigned prec = TYPE_PRECISION (type);
2324 12078386 : widest2_int min0 = widest2_int::from (lh_lb, sign);
2325 12078386 : widest2_int max0 = widest2_int::from (lh_ub, sign);
2326 12078386 : widest2_int min1 = widest2_int::from (rh_lb, sign);
2327 12078386 : widest2_int max1 = widest2_int::from (rh_ub, sign);
2328 12078386 : widest2_int sizem1 = wi::mask <widest2_int> (prec, false);
2329 12078386 : widest2_int size = sizem1 + 1;
2330 :
2331 : // Canonicalize the intervals.
2332 12078386 : if (sign == UNSIGNED)
2333 : {
2334 11342957 : if (wi::ltu_p (size, min0 + max0))
2335 : {
2336 1537968 : min0 -= size;
2337 1537968 : max0 -= size;
2338 : }
2339 11342919 : if (wi::ltu_p (size, min1 + max1))
2340 : {
2341 164877 : min1 -= size;
2342 164877 : max1 -= size;
2343 : }
2344 : }
2345 :
2346 : // Sort the 4 products so that min is in prod0 and max is in
2347 : // prod3.
2348 12078386 : widest2_int prod0 = min0 * min1;
2349 12078386 : widest2_int prod1 = min0 * max1;
2350 12078386 : widest2_int prod2 = max0 * min1;
2351 12078386 : widest2_int prod3 = max0 * max1;
2352 :
2353 : // min0min1 > max0max1
2354 12078386 : if (prod0 > prod3)
2355 197234 : std::swap (prod0, prod3);
2356 :
2357 : // min0max1 > max0min1
2358 12078386 : if (prod1 > prod2)
2359 320323 : std::swap (prod1, prod2);
2360 :
2361 12078386 : if (prod0 > prod1)
2362 80034 : std::swap (prod0, prod1);
2363 :
2364 12078386 : if (prod2 > prod3)
2365 4116 : std::swap (prod2, prod3);
2366 :
2367 : // diff = max - min
2368 12078386 : prod2 = prod3 - prod0;
2369 12078386 : if (wi::geu_p (prod2, sizem1))
2370 : {
2371 : // Multiplying by X, where X is a power of 2 is [0,0][X,+INF].
2372 7971483 : if (TYPE_UNSIGNED (type) && rh_lb == rh_ub
2373 7336492 : && wi::exact_log2 (rh_lb) != -1 && prec > 1)
2374 : {
2375 2741154 : r.set (type, rh_lb, wi::max_value (prec, sign));
2376 2741154 : int_range<2> zero;
2377 2741154 : zero.set_zero (type);
2378 2741154 : r.union_ (zero);
2379 2741154 : }
2380 : else
2381 : // The range covers all values.
2382 1317165 : r.set_varying (type);
2383 : }
2384 : else
2385 : {
2386 8020067 : wide_int new_lb = wide_int::from (prod0, prec, sign);
2387 8020067 : wide_int new_ub = wide_int::from (prod3, prec, sign);
2388 8020067 : create_possibly_reversed_range (r, type, new_lb, new_ub);
2389 8020122 : }
2390 12079231 : }
2391 :
2392 : bool
2393 14441112 : 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 14441112 : if (rel == VREL_EQ
2401 14441112 : && TYPE_OVERFLOW_UNDEFINED (type))
2402 : {
2403 36203 : int_range<2> nonnegative;
2404 36203 : nonnegative.set_nonnegative (type);
2405 36203 : lhs_range.intersect (nonnegative);
2406 36203 : return true;
2407 36203 : }
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 1331 : 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 1331 : wide_int lh_wlb = wide_int::from (lh_lb, TYPE_PRECISION (type), SIGNED);
2430 1331 : wide_int lh_wub = wide_int::from (lh_ub, TYPE_PRECISION (type), SIGNED);
2431 1331 : wide_int rh_wlb = wide_int::from (rh_lb, TYPE_PRECISION (type), SIGNED);
2432 1331 : 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 1331 : return op_mult.wi_fold (r, type, lh_wlb, lh_wub, rh_wlb, rh_wub);
2438 1331 : }
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 7512 : 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 7512 : wide_int lh_wlb = wide_int::from (lh_lb, TYPE_PRECISION (type), UNSIGNED);
2459 7512 : wide_int lh_wub = wide_int::from (lh_ub, TYPE_PRECISION (type), UNSIGNED);
2460 7512 : wide_int rh_wlb = wide_int::from (rh_lb, TYPE_PRECISION (type), UNSIGNED);
2461 7512 : 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 7512 : return op_mult.wi_fold (r, type, lh_wlb, lh_wub, rh_wlb, rh_wub);
2467 7512 : }
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 3008486 : void update_bitmask (irange &r, const irange &lh, const irange &rh)
2521 : const final override
2522 3008486 : { 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 36660 : operator_div::op2_range (irange &r, tree type, const irange &lhs,
2535 : const irange &, relation_trio) const
2536 : {
2537 36660 : if (!lhs.undefined_p ())
2538 : {
2539 36660 : r.set_nonzero (type);
2540 36660 : return true;
2541 : }
2542 : return false;
2543 : }
2544 :
2545 : bool
2546 13032473 : operator_div::wi_op_overflows (wide_int &res, tree type,
2547 : const wide_int &w0, const wide_int &w1) const
2548 : {
2549 13032473 : if (w1 == 0)
2550 : return true;
2551 :
2552 13032473 : wi::overflow_type overflow = wi::OVF_NONE;
2553 13032473 : signop sign = TYPE_SIGN (type);
2554 :
2555 13032473 : switch (m_code)
2556 : {
2557 12889239 : case EXACT_DIV_EXPR:
2558 12889239 : case TRUNC_DIV_EXPR:
2559 12889239 : res = wi::div_trunc (w0, w1, sign, &overflow);
2560 12889239 : break;
2561 132358 : case FLOOR_DIV_EXPR:
2562 132358 : res = wi::div_floor (w0, w1, sign, &overflow);
2563 132358 : break;
2564 288 : case ROUND_DIV_EXPR:
2565 288 : res = wi::div_round (w0, w1, sign, &overflow);
2566 288 : break;
2567 10588 : case CEIL_DIV_EXPR:
2568 10588 : res = wi::div_ceil (w0, w1, sign, &overflow);
2569 10588 : break;
2570 0 : default:
2571 0 : gcc_unreachable ();
2572 : }
2573 :
2574 13032473 : if (overflow && TYPE_OVERFLOW_UNDEFINED (type))
2575 : {
2576 : // For division, the only case is -INF / -1 = +INF.
2577 209170 : res = wi::max_value (w0.get_precision (), sign);
2578 209170 : return false;
2579 : }
2580 12823303 : return overflow;
2581 : }
2582 :
2583 : void
2584 4148297 : 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 4148297 : const wide_int dividend_min = lh_lb;
2589 4148297 : const wide_int dividend_max = lh_ub;
2590 4148297 : const wide_int divisor_min = rh_lb;
2591 4148297 : const wide_int divisor_max = rh_ub;
2592 4148297 : signop sign = TYPE_SIGN (type);
2593 4148297 : unsigned prec = TYPE_PRECISION (type);
2594 4148297 : wide_int extra_min, extra_max;
2595 :
2596 : // If we know we won't divide by zero, just do the division.
2597 4148297 : if (!wi_includes_zero_p (type, divisor_min, divisor_max))
2598 : {
2599 3424464 : wi_cross_product (r, type, dividend_min, dividend_max,
2600 : divisor_min, divisor_max);
2601 3424464 : return;
2602 : }
2603 :
2604 : // If we're definitely dividing by zero, there's nothing to do.
2605 723833 : if (wi_zero_p (type, divisor_min, divisor_max))
2606 : {
2607 18470 : r.set_undefined ();
2608 18470 : 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 705363 : if (wi::neg_p (divisor_min, sign))
2616 945578 : wi_cross_product (r, type, dividend_min, dividend_max,
2617 945578 : divisor_min, wi::minus_one (prec));
2618 : else
2619 232574 : r.set_undefined ();
2620 :
2621 : // Then divide by the non-zero positive numbers, if any.
2622 705363 : if (wi::gt_p (divisor_max, wi::zero (prec), sign))
2623 : {
2624 704776 : int_range_max tmp;
2625 1409552 : wi_cross_product (tmp, type, dividend_min, dividend_max,
2626 704776 : wi::one (prec), divisor_max);
2627 704776 : r.union_ (tmp);
2628 704776 : }
2629 : // We shouldn't still have undefined here.
2630 705363 : gcc_checking_assert (!r.undefined_p ());
2631 4148929 : }
2632 :
2633 : bool
2634 3008486 : 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 3008486 : if (rel == VREL_VARYING)
2641 : return false;
2642 :
2643 2595 : int_range<2> rel_range;
2644 :
2645 2595 : switch (rel)
2646 : {
2647 : /* op1/op2 = 0 if op1 < op2 and both op1 and op2
2648 : are known positives. */
2649 125 : case VREL_LT:
2650 : // Exact, and truncate division will produce 0 for this case.
2651 : // Floor division will be treated similar to truncate div as rounding towards
2652 : // to 0 is the same as rounding towards -inf for positive values.
2653 125 : if (m_code != EXACT_DIV_EXPR
2654 125 : && m_code != TRUNC_DIV_EXPR
2655 4 : && m_code != FLOOR_DIV_EXPR)
2656 : return false;
2657 121 : if (!op1_range.nonnegative_p ()
2658 121 : || !op2_range.nonnegative_p ())
2659 : return false;
2660 84 : rel_range.set_zero (type);
2661 84 : break;
2662 2 : case VREL_EQ:
2663 2 : {
2664 2 : wide_int one = wi::one (TYPE_PRECISION (type));
2665 2 : rel_range.set (type, one, one);
2666 2 : break;
2667 2 : }
2668 : default:
2669 : return false;
2670 : }
2671 :
2672 86 : lhs_range.intersect (rel_range);
2673 86 : return true;
2674 2595 : }
2675 :
2676 : class operator_exact_divide : public operator_div
2677 : {
2678 : using range_operator::op1_range;
2679 : public:
2680 : operator_exact_divide () : operator_div (EXACT_DIV_EXPR) { }
2681 : virtual bool op1_range (irange &r, tree type,
2682 : const irange &lhs,
2683 : const irange &op2,
2684 : relation_trio) const;
2685 :
2686 : } op_exact_div;
2687 :
2688 : bool
2689 582323 : operator_exact_divide::op1_range (irange &r, tree type,
2690 : const irange &lhs,
2691 : const irange &op2,
2692 : relation_trio) const
2693 : {
2694 582323 : if (lhs.undefined_p ())
2695 : return false;
2696 582323 : wide_int offset;
2697 : // [2, 4] = op1 / [3,3] since its exact divide, no need to worry about
2698 : // remainders in the endpoints, so op1 = [2,4] * [3,3] = [6,12].
2699 : // We wont bother trying to enumerate all the in between stuff :-P
2700 : // TRUE accuracy is [6,6][9,9][12,12]. This is unlikely to matter most of
2701 : // the time however.
2702 : // If op2 is a multiple of 2, we would be able to set some non-zero bits.
2703 582323 : if (op2.singleton_p (offset) && offset != 0)
2704 582323 : return range_op_handler (MULT_EXPR).fold_range (r, type, lhs, op2);
2705 : return false;
2706 582323 : }
2707 :
2708 :
2709 : class operator_lshift : public cross_product_operator
2710 : {
2711 : using range_operator::fold_range;
2712 : using range_operator::op1_range;
2713 : using range_operator::update_bitmask;
2714 : public:
2715 : virtual bool op1_range (irange &r, tree type, const irange &lhs,
2716 : const irange &op2, relation_trio rel = TRIO_VARYING)
2717 : const final override;
2718 : virtual bool fold_range (irange &r, tree type, const irange &op1,
2719 : const irange &op2, relation_trio rel = TRIO_VARYING)
2720 : const final override;
2721 :
2722 : virtual void wi_fold (irange &r, tree type,
2723 : const wide_int &lh_lb, const wide_int &lh_ub,
2724 : const wide_int &rh_lb,
2725 : const wide_int &rh_ub) const final override;
2726 : virtual bool wi_op_overflows (wide_int &res,
2727 : tree type,
2728 : const wide_int &,
2729 : const wide_int &) const final override;
2730 474139 : void update_bitmask (irange &r, const irange &lh,
2731 : const irange &rh) const final override
2732 474139 : { update_known_bitmask (r, LSHIFT_EXPR, lh, rh); }
2733 : // Check compatibility of LHS and op1.
2734 1123282 : bool operand_check_p (tree t1, tree t2, tree) const final override
2735 1123282 : { return range_compatible_p (t1, t2); }
2736 : } op_lshift;
2737 :
2738 : class operator_rshift : public cross_product_operator
2739 : {
2740 : using range_operator::fold_range;
2741 : using range_operator::op1_range;
2742 : using range_operator::lhs_op1_relation;
2743 : using range_operator::update_bitmask;
2744 : public:
2745 : virtual bool fold_range (irange &r, tree type, const irange &op1,
2746 : const irange &op2, relation_trio rel = TRIO_VARYING)
2747 : const final override;
2748 : virtual void wi_fold (irange &r, tree type,
2749 : const wide_int &lh_lb,
2750 : const wide_int &lh_ub,
2751 : const wide_int &rh_lb,
2752 : const wide_int &rh_ub) const final override;
2753 : virtual bool wi_op_overflows (wide_int &res,
2754 : tree type,
2755 : const wide_int &w0,
2756 : const wide_int &w1) const final override;
2757 : virtual bool op1_range (irange &, tree type, const irange &lhs,
2758 : const irange &op2, relation_trio rel = TRIO_VARYING)
2759 : const final override;
2760 : virtual relation_kind lhs_op1_relation (const irange &lhs, const irange &op1,
2761 : const irange &op2, relation_kind rel)
2762 : const final override;
2763 3598652 : void update_bitmask (irange &r, const irange &lh,
2764 : const irange &rh) const final override
2765 3598652 : { update_known_bitmask (r, RSHIFT_EXPR, lh, rh); }
2766 : // Check compatibility of LHS and op1.
2767 3687456 : bool operand_check_p (tree t1, tree t2, tree) const final override
2768 3687456 : { return range_compatible_p (t1, t2); }
2769 : } op_rshift;
2770 :
2771 :
2772 : relation_kind
2773 2682552 : operator_rshift::lhs_op1_relation (const irange &lhs ATTRIBUTE_UNUSED,
2774 : const irange &op1,
2775 : const irange &op2,
2776 : relation_kind) const
2777 : {
2778 : // If both operands range are >= 0, then the LHS <= op1.
2779 2682552 : if (!op1.undefined_p () && !op2.undefined_p ()
2780 5363939 : && wi::ge_p (op1.lower_bound (), 0, TYPE_SIGN (op1.type ()))
2781 7782154 : && wi::ge_p (op2.lower_bound (), 0, TYPE_SIGN (op2.type ())))
2782 2389779 : return VREL_LE;
2783 : return VREL_VARYING;
2784 : }
2785 :
2786 : bool
2787 1668984 : operator_lshift::fold_range (irange &r, tree type,
2788 : const irange &op1,
2789 : const irange &op2,
2790 : relation_trio rel) const
2791 : {
2792 1668984 : int_range_max shift_range;
2793 1668984 : if (!get_shift_range (shift_range, type, op2))
2794 : {
2795 1269 : if (op2.undefined_p ())
2796 933 : r.set_undefined ();
2797 : else
2798 336 : r.set_zero (type);
2799 : return true;
2800 : }
2801 :
2802 : // Transform left shifts by constants into multiplies.
2803 1667715 : if (shift_range.singleton_p ())
2804 : {
2805 1193549 : unsigned shift = shift_range.lower_bound ().to_uhwi ();
2806 1193549 : wide_int tmp = wi::set_bit_in_zero (shift, TYPE_PRECISION (type));
2807 1193549 : int_range<1> mult (type, tmp, tmp);
2808 :
2809 : // Force wrapping multiplication.
2810 1193549 : bool saved_flag_wrapv = flag_wrapv;
2811 1193549 : bool saved_flag_wrapv_pointer = flag_wrapv_pointer;
2812 1193549 : flag_wrapv = 1;
2813 1193549 : flag_wrapv_pointer = 1;
2814 1193549 : bool b = op_mult.fold_range (r, type, op1, mult);
2815 1193549 : flag_wrapv = saved_flag_wrapv;
2816 1193549 : flag_wrapv_pointer = saved_flag_wrapv_pointer;
2817 1193549 : return b;
2818 1193558 : }
2819 : else
2820 : // Otherwise, invoke the generic fold routine.
2821 474166 : return range_operator::fold_range (r, type, op1, shift_range, rel);
2822 1668984 : }
2823 :
2824 : void
2825 554222 : operator_lshift::wi_fold (irange &r, tree type,
2826 : const wide_int &lh_lb, const wide_int &lh_ub,
2827 : const wide_int &rh_lb, const wide_int &rh_ub) const
2828 : {
2829 554222 : signop sign = TYPE_SIGN (type);
2830 554222 : unsigned prec = TYPE_PRECISION (type);
2831 554222 : int overflow_pos = sign == SIGNED ? prec - 1 : prec;
2832 554222 : int bound_shift = overflow_pos - rh_ub.to_shwi ();
2833 : // If bound_shift == HOST_BITS_PER_WIDE_INT, the llshift can
2834 : // overflow. However, for that to happen, rh.max needs to be zero,
2835 : // which means rh is a singleton range of zero, which means we simply return
2836 : // [lh_lb, lh_ub] as the range.
2837 554222 : if (wi::eq_p (rh_ub, rh_lb) && wi::eq_p (rh_ub, 0))
2838 : {
2839 21489 : r = int_range<2> (type, lh_lb, lh_ub);
2840 21489 : return;
2841 : }
2842 :
2843 532733 : wide_int bound = wi::set_bit_in_zero (bound_shift, prec);
2844 532733 : wide_int complement = ~(bound - 1);
2845 532733 : wide_int low_bound, high_bound;
2846 532733 : bool in_bounds = false;
2847 :
2848 532733 : if (sign == UNSIGNED)
2849 : {
2850 262208 : low_bound = bound;
2851 262208 : high_bound = complement;
2852 262208 : if (wi::ltu_p (lh_ub, low_bound))
2853 : {
2854 : // [5, 6] << [1, 2] == [10, 24].
2855 : // We're shifting out only zeroes, the value increases
2856 : // monotonically.
2857 : in_bounds = true;
2858 : }
2859 84521 : else if (wi::ltu_p (high_bound, lh_lb))
2860 : {
2861 : // [0xffffff00, 0xffffffff] << [1, 2]
2862 : // == [0xfffffc00, 0xfffffffe].
2863 : // We're shifting out only ones, the value decreases
2864 : // monotonically.
2865 : in_bounds = true;
2866 : }
2867 : }
2868 : else
2869 : {
2870 : // [-1, 1] << [1, 2] == [-4, 4]
2871 270525 : low_bound = complement;
2872 270525 : high_bound = bound;
2873 270525 : if (wi::lts_p (lh_ub, high_bound)
2874 270525 : && wi::lts_p (low_bound, lh_lb))
2875 : {
2876 : // For non-negative numbers, we're shifting out only zeroes,
2877 : // the value increases monotonically. For negative numbers,
2878 : // we're shifting out only ones, the value decreases
2879 : // monotonically.
2880 : in_bounds = true;
2881 : }
2882 : }
2883 :
2884 : if (in_bounds)
2885 292911 : wi_cross_product (r, type, lh_lb, lh_ub, rh_lb, rh_ub);
2886 : else
2887 239822 : r.set_varying (type);
2888 532751 : }
2889 :
2890 : bool
2891 570688 : operator_lshift::wi_op_overflows (wide_int &res, tree type,
2892 : const wide_int &w0, const wide_int &w1) const
2893 : {
2894 570688 : signop sign = TYPE_SIGN (type);
2895 570688 : if (wi::neg_p (w1))
2896 : {
2897 : // It's unclear from the C standard whether shifts can overflow.
2898 : // The following code ignores overflow; perhaps a C standard
2899 : // interpretation ruling is needed.
2900 0 : res = wi::rshift (w0, -w1, sign);
2901 : }
2902 : else
2903 570688 : res = wi::lshift (w0, w1);
2904 570688 : return false;
2905 : }
2906 :
2907 : bool
2908 49463 : operator_lshift::op1_range (irange &r,
2909 : tree type,
2910 : const irange &lhs,
2911 : const irange &op2,
2912 : relation_trio) const
2913 : {
2914 49463 : if (lhs.undefined_p ())
2915 : return false;
2916 :
2917 49463 : if (!lhs.contains_zero_p ())
2918 18769 : r.set_nonzero (type);
2919 : else
2920 30694 : r.set_varying (type);
2921 :
2922 49463 : wide_int shift;
2923 49463 : if (op2.singleton_p (shift))
2924 : {
2925 43687 : if (wi::lt_p (shift, 0, SIGNED))
2926 : return false;
2927 43687 : if (wi::ge_p (shift, wi::uhwi (TYPE_PRECISION (type),
2928 43687 : TYPE_PRECISION (op2.type ())),
2929 : UNSIGNED))
2930 : return false;
2931 43687 : if (shift == 0)
2932 : {
2933 76 : r.intersect (lhs);
2934 76 : return true;
2935 : }
2936 :
2937 : // Work completely in unsigned mode to start.
2938 43611 : tree utype = type;
2939 43611 : int_range_max tmp_range;
2940 43611 : if (TYPE_SIGN (type) == SIGNED)
2941 : {
2942 7993 : int_range_max tmp = lhs;
2943 7993 : utype = unsigned_type_for (type);
2944 7993 : range_cast (tmp, utype);
2945 7993 : op_rshift.fold_range (tmp_range, utype, tmp, op2);
2946 7993 : }
2947 : else
2948 35618 : op_rshift.fold_range (tmp_range, utype, lhs, op2);
2949 :
2950 : // If no valid range is found, abort the calculation and return falae.
2951 43611 : if (tmp_range.undefined_p ())
2952 : return false;
2953 :
2954 : // Start with ranges which can produce the LHS by right shifting the
2955 : // result by the shift amount.
2956 : // ie [0x08, 0xF0] = op1 << 2 will start with
2957 : // [00001000, 11110000] = op1 << 2
2958 : // [0x02, 0x4C] aka [00000010, 00111100]
2959 :
2960 : // Then create a range from the LB with the least significant upper bit
2961 : // set, to the upper bound with all the bits set.
2962 : // This would be [0x42, 0xFC] aka [01000010, 11111100].
2963 :
2964 : // Ideally we do this for each subrange, but just lump them all for now.
2965 43611 : unsigned low_bits = TYPE_PRECISION (utype) - shift.to_uhwi ();
2966 43611 : wide_int up_mask = wi::mask (low_bits, true, TYPE_PRECISION (utype));
2967 43611 : wide_int new_ub = wi::bit_or (up_mask, tmp_range.upper_bound ());
2968 43611 : wide_int new_lb = wi::set_bit (tmp_range.lower_bound (), low_bits);
2969 43611 : int_range<2> fill_range (utype, new_lb, new_ub);
2970 43611 : tmp_range.union_ (fill_range);
2971 :
2972 43611 : if (utype != type)
2973 7993 : range_cast (tmp_range, type);
2974 :
2975 43611 : r.intersect (tmp_range);
2976 43611 : return true;
2977 43611 : }
2978 :
2979 5776 : return !r.varying_p ();
2980 49463 : }
2981 :
2982 : bool
2983 831313 : operator_rshift::op1_range (irange &r,
2984 : tree type,
2985 : const irange &lhs,
2986 : const irange &op2,
2987 : relation_trio) const
2988 : {
2989 831313 : if (lhs.undefined_p ())
2990 : return false;
2991 831313 : wide_int shift;
2992 831313 : if (op2.singleton_p (shift))
2993 : {
2994 : // Ignore nonsensical shifts.
2995 807883 : unsigned prec = TYPE_PRECISION (type);
2996 1615766 : if (wi::ge_p (shift,
2997 807883 : wi::uhwi (prec, TYPE_PRECISION (op2.type ())),
2998 : UNSIGNED))
2999 : return false;
3000 807883 : if (shift == 0)
3001 : {
3002 75 : r = lhs;
3003 75 : return true;
3004 : }
3005 :
3006 : // Folding the original operation may discard some impossible
3007 : // ranges from the LHS.
3008 807808 : int_range_max lhs_refined;
3009 807808 : op_rshift.fold_range (lhs_refined, type, int_range<1> (type), op2);
3010 807808 : lhs_refined.intersect (lhs);
3011 807808 : if (lhs_refined.undefined_p ())
3012 : {
3013 4 : r.set_undefined ();
3014 4 : return true;
3015 : }
3016 807804 : int_range_max shift_range (op2.type (), shift, shift);
3017 807804 : int_range_max lb, ub;
3018 807804 : op_lshift.fold_range (lb, type, lhs_refined, shift_range);
3019 : // LHS
3020 : // 0000 0111 = OP1 >> 3
3021 : //
3022 : // OP1 is anything from 0011 1000 to 0011 1111. That is, a
3023 : // range from LHS<<3 plus a mask of the 3 bits we shifted on the
3024 : // right hand side (0x07).
3025 807804 : wide_int mask = wi::mask (shift.to_uhwi (), false, prec);
3026 807804 : int_range_max mask_range (type,
3027 807804 : wi::zero (TYPE_PRECISION (type)),
3028 807804 : mask);
3029 807804 : op_plus.fold_range (ub, type, lb, mask_range);
3030 807804 : r = lb;
3031 807804 : r.union_ (ub);
3032 807804 : if (!lhs_refined.contains_zero_p ())
3033 : {
3034 456342 : if (!mask_range.invert ())
3035 : return false;
3036 456342 : r.intersect (mask_range);
3037 : }
3038 : return true;
3039 807808 : }
3040 : return false;
3041 831313 : }
3042 :
3043 : bool
3044 12010513 : operator_rshift::wi_op_overflows (wide_int &res,
3045 : tree type,
3046 : const wide_int &w0,
3047 : const wide_int &w1) const
3048 : {
3049 12010513 : signop sign = TYPE_SIGN (type);
3050 12010513 : if (wi::neg_p (w1))
3051 0 : res = wi::lshift (w0, -w1);
3052 : else
3053 : {
3054 : // It's unclear from the C standard whether shifts can overflow.
3055 : // The following code ignores overflow; perhaps a C standard
3056 : // interpretation ruling is needed.
3057 12010604 : res = wi::rshift (w0, w1, sign);
3058 : }
3059 12010513 : return false;
3060 : }
3061 :
3062 : bool
3063 3600200 : operator_rshift::fold_range (irange &r, tree type,
3064 : const irange &op1,
3065 : const irange &op2,
3066 : relation_trio rel) const
3067 : {
3068 3600200 : int_range_max shift;
3069 3600200 : if (!get_shift_range (shift, type, op2))
3070 : {
3071 561 : if (op2.undefined_p ())
3072 220 : r.set_undefined ();
3073 : else
3074 341 : r.set_zero (type);
3075 : return true;
3076 : }
3077 :
3078 3599639 : return range_operator::fold_range (r, type, op1, shift, rel);
3079 3600200 : }
3080 :
3081 : void
3082 4309704 : operator_rshift::wi_fold (irange &r, tree type,
3083 : const wide_int &lh_lb, const wide_int &lh_ub,
3084 : const wide_int &rh_lb, const wide_int &rh_ub) const
3085 : {
3086 4309704 : wi_cross_product (r, type, lh_lb, lh_ub, rh_lb, rh_ub);
3087 4309704 : }
3088 :
3089 :
3090 : // Add a partial equivalence between the LHS and op1 for casts.
3091 :
3092 : relation_kind
3093 24631080 : operator_cast::lhs_op1_relation (const irange &lhs,
3094 : const irange &op1,
3095 : const irange &op2 ATTRIBUTE_UNUSED,
3096 : relation_kind) const
3097 : {
3098 24631080 : if (lhs.undefined_p () || op1.undefined_p ())
3099 : return VREL_VARYING;
3100 24608176 : unsigned lhs_prec = TYPE_PRECISION (lhs.type ());
3101 24608176 : unsigned op1_prec = TYPE_PRECISION (op1.type ());
3102 : // If the result gets sign extended into a larger type check first if this
3103 : // qualifies as a partial equivalence.
3104 24608176 : if (TYPE_SIGN (op1.type ()) == SIGNED && lhs_prec > op1_prec)
3105 : {
3106 : // If the result is sign extended, and the LHS is larger than op1,
3107 : // check if op1's range can be negative as the sign extension will
3108 : // cause the upper bits to be 1 instead of 0, invalidating the PE.
3109 3978869 : int_range<3> negs = range_negatives (op1.type ());
3110 3978869 : negs.intersect (op1);
3111 3978869 : if (!negs.undefined_p ())
3112 2759341 : return VREL_VARYING;
3113 3978869 : }
3114 :
3115 21848835 : unsigned prec = MIN (lhs_prec, op1_prec);
3116 21848835 : return bits_to_pe (prec);
3117 : }
3118 :
3119 : // Return TRUE if casting from INNER to OUTER is a truncating cast.
3120 :
3121 : inline bool
3122 86948304 : operator_cast::truncating_cast_p (const irange &inner,
3123 : const irange &outer) const
3124 : {
3125 86948304 : return TYPE_PRECISION (outer.type ()) < TYPE_PRECISION (inner.type ());
3126 : }
3127 :
3128 : // Return TRUE if [MIN,MAX] is inside the domain of RANGE's type.
3129 :
3130 : bool
3131 74679214 : operator_cast::inside_domain_p (const wide_int &min,
3132 : const wide_int &max,
3133 : const irange &range) const
3134 : {
3135 74679214 : wide_int domain_min = irange_val_min (range.type ());
3136 74679214 : wide_int domain_max = irange_val_max (range.type ());
3137 74679214 : signop domain_sign = TYPE_SIGN (range.type ());
3138 74679214 : return (wi::le_p (min, domain_max, domain_sign)
3139 74679214 : && wi::le_p (max, domain_max, domain_sign)
3140 74679214 : && wi::ge_p (min, domain_min, domain_sign)
3141 149358428 : && wi::ge_p (max, domain_min, domain_sign));
3142 74679214 : }
3143 :
3144 :
3145 : // Helper for fold_range which work on a pair at a time.
3146 :
3147 : void
3148 77966157 : operator_cast::fold_pair (irange &r, unsigned index,
3149 : const irange &inner,
3150 : const irange &outer) const
3151 : {
3152 77966157 : tree inner_type = inner.type ();
3153 77966157 : tree outer_type = outer.type ();
3154 77966157 : signop inner_sign = TYPE_SIGN (inner_type);
3155 77966157 : unsigned outer_prec = TYPE_PRECISION (outer_type);
3156 :
3157 : // check to see if casting from INNER to OUTER is a conversion that
3158 : // fits in the resulting OUTER type.
3159 77966157 : wide_int inner_lb = inner.lower_bound (index);
3160 77966157 : wide_int inner_ub = inner.upper_bound (index);
3161 77966157 : if (truncating_cast_p (inner, outer))
3162 : {
3163 : // We may be able to accommodate a truncating cast if the
3164 : // resulting range can be represented in the target type...
3165 16415666 : if (wi::rshift (wi::sub (inner_ub, inner_lb),
3166 8207833 : wi::uhwi (outer_prec, TYPE_PRECISION (inner.type ())),
3167 24623499 : inner_sign) != 0)
3168 : {
3169 3286943 : r.set_varying (outer_type);
3170 3286943 : return;
3171 : }
3172 : }
3173 : // ...but we must still verify that the final range fits in the
3174 : // domain. This catches -fstrict-enum restrictions where the domain
3175 : // range is smaller than what fits in the underlying type.
3176 74679214 : wide_int min = wide_int::from (inner_lb, outer_prec, inner_sign);
3177 74679214 : wide_int max = wide_int::from (inner_ub, outer_prec, inner_sign);
3178 74679214 : if (inside_domain_p (min, max, outer))
3179 74679214 : create_possibly_reversed_range (r, outer_type, min, max);
3180 : else
3181 0 : r.set_varying (outer_type);
3182 77969221 : }
3183 :
3184 :
3185 : bool
3186 63843396 : operator_cast::fold_range (irange &r, tree type ATTRIBUTE_UNUSED,
3187 : const irange &inner,
3188 : const irange &outer,
3189 : relation_trio) const
3190 : {
3191 63843396 : if (empty_range_varying (r, type, inner, outer))
3192 34383 : return true;
3193 :
3194 63809013 : gcc_checking_assert (outer.varying_p ());
3195 63809013 : gcc_checking_assert (inner.num_pairs () > 0);
3196 :
3197 : // Avoid a temporary by folding the first pair directly into the result.
3198 63809013 : fold_pair (r, 0, inner, outer);
3199 :
3200 : // Then process any additional pairs by unioning with their results.
3201 141107657 : for (unsigned x = 1; x < inner.num_pairs (); ++x)
3202 : {
3203 14157144 : int_range_max tmp;
3204 14157144 : fold_pair (tmp, x, inner, outer);
3205 14157144 : r.union_ (tmp);
3206 : // If we hit varying, go update the bitmask.
3207 14157144 : if (r.varying_p ())
3208 : break;
3209 14157144 : }
3210 :
3211 63809013 : update_bitmask (r, inner, outer);
3212 63809013 : return true;
3213 : }
3214 :
3215 : void
3216 63809013 : operator_cast::update_bitmask (irange &r, const irange &lh,
3217 : const irange &rh) const
3218 : {
3219 63809013 : update_known_bitmask (r, CONVERT_EXPR, lh, rh);
3220 63809013 : }
3221 :
3222 : bool
3223 8982147 : operator_cast::op1_range (irange &r, tree type,
3224 : const irange &lhs,
3225 : const irange &op2,
3226 : relation_trio) const
3227 : {
3228 8982147 : if (lhs.undefined_p ())
3229 : return false;
3230 8982147 : tree lhs_type = lhs.type ();
3231 8982147 : gcc_checking_assert (types_compatible_p (op2.type(), type));
3232 :
3233 : // If we are calculating a pointer, shortcut to what we really care about.
3234 8982147 : if (POINTER_TYPE_P (type))
3235 : {
3236 : // Conversion from other pointers or a constant (including 0/NULL)
3237 : // are straightforward.
3238 0 : if (POINTER_TYPE_P (lhs.type ())
3239 0 : || (lhs.singleton_p ()
3240 0 : && TYPE_PRECISION (lhs.type ()) >= TYPE_PRECISION (type)))
3241 : {
3242 0 : r = lhs;
3243 0 : range_cast (r, type);
3244 : }
3245 : else
3246 : {
3247 : // If the LHS is not a pointer nor a singleton, then it is
3248 : // either VARYING or non-zero.
3249 0 : if (!lhs.undefined_p () && !lhs.contains_zero_p ())
3250 0 : r.set_nonzero (type);
3251 : else
3252 0 : r.set_varying (type);
3253 : }
3254 0 : r.intersect (op2);
3255 0 : return true;
3256 : }
3257 :
3258 8982147 : if (truncating_cast_p (op2, lhs))
3259 : {
3260 1360060 : if (lhs.varying_p ())
3261 144826 : r.set_varying (type);
3262 : else
3263 : {
3264 : // We want to insert the LHS as an unsigned value since it
3265 : // would not trigger the signed bit of the larger type.
3266 1215234 : int_range_max converted_lhs = lhs;
3267 1215234 : range_cast (converted_lhs, unsigned_type_for (lhs_type));
3268 1215234 : range_cast (converted_lhs, type);
3269 : // Start by building the positive signed outer range for the type.
3270 1215234 : wide_int lim = wi::set_bit_in_zero (TYPE_PRECISION (lhs_type),
3271 2430468 : TYPE_PRECISION (type));
3272 1215234 : create_possibly_reversed_range (r, type, lim,
3273 1215234 : wi::max_value (TYPE_PRECISION (type),
3274 : SIGNED));
3275 : // For the signed part, we need to simply union the 2 ranges now.
3276 1215234 : r.union_ (converted_lhs);
3277 :
3278 : // Create maximal negative number outside of LHS bits.
3279 1215234 : lim = wi::mask (TYPE_PRECISION (lhs_type), true,
3280 2430468 : TYPE_PRECISION (type));
3281 : // Add this to the unsigned LHS range(s).
3282 1215234 : int_range_max lim_range (type, lim, lim);
3283 1215234 : int_range_max lhs_neg;
3284 1215234 : range_op_handler (PLUS_EXPR).fold_range (lhs_neg, type,
3285 : converted_lhs, lim_range);
3286 : // lhs_neg now has all the negative versions of the LHS.
3287 : // Now union in all the values from SIGNED MIN (0x80000) to
3288 : // lim-1 in order to fill in all the ranges with the upper
3289 : // bits set.
3290 :
3291 : // PR 97317. If the lhs has only 1 bit less precision than the rhs,
3292 : // we don't need to create a range from min to lim-1
3293 : // calculate neg range traps trying to create [lim, lim - 1].
3294 1215234 : wide_int min_val = wi::min_value (TYPE_PRECISION (type), SIGNED);
3295 1215234 : if (lim != min_val)
3296 : {
3297 1213662 : int_range_max neg (type,
3298 2427324 : wi::min_value (TYPE_PRECISION (type),
3299 : SIGNED),
3300 2427324 : lim - 1);
3301 1213662 : lhs_neg.union_ (neg);
3302 1213662 : }
3303 : // And finally, munge the signed and unsigned portions.
3304 1215234 : r.union_ (lhs_neg);
3305 1215234 : }
3306 : // And intersect with any known value passed in the extra operand.
3307 1360060 : r.intersect (op2);
3308 1360060 : if (r.undefined_p ())
3309 : return true;
3310 :
3311 : // Now create a bitmask indicating that the lower bit must match the
3312 : // bits in the LHS. Zero-extend LHS bitmask to precision of op1.
3313 1359956 : irange_bitmask bm = lhs.get_bitmask ();
3314 2719912 : wide_int mask = wide_int::from (bm.mask (), TYPE_PRECISION (type),
3315 2719912 : UNSIGNED);
3316 2719912 : wide_int value = wide_int::from (bm.value (), TYPE_PRECISION (type),
3317 2719912 : UNSIGNED);
3318 :
3319 : // Set then additional unknown bits in mask.
3320 1359956 : wide_int lim = wi::mask (TYPE_PRECISION (lhs_type), true,
3321 2719912 : TYPE_PRECISION (type));
3322 1359956 : mask = mask | lim;
3323 :
3324 : // Now set the new bitmask for the range.
3325 1359956 : irange_bitmask new_bm (value, mask);
3326 1359956 : r.update_bitmask (new_bm);
3327 1359956 : return true;
3328 1359956 : }
3329 :
3330 7622087 : int_range_max tmp;
3331 7622087 : if (TYPE_PRECISION (lhs_type) == TYPE_PRECISION (type))
3332 5246268 : tmp = lhs;
3333 : else
3334 : {
3335 : // The cast is not truncating, and the range is restricted to
3336 : // the range of the RHS by this assignment.
3337 : //
3338 : // Cast the range of the RHS to the type of the LHS.
3339 2375819 : fold_range (tmp, lhs_type, int_range<1> (type), int_range<1> (lhs_type));
3340 : // Intersect this with the LHS range will produce the range,
3341 : // which will be cast to the RHS type before returning.
3342 2375819 : tmp.intersect (lhs);
3343 : }
3344 :
3345 : // Cast the calculated range to the type of the RHS.
3346 7622087 : fold_range (r, type, tmp, int_range<1> (type));
3347 7622087 : return true;
3348 7622087 : }
3349 :
3350 : // VIEW_CONVERT_EXPR works like a cast between integral values.
3351 : // If the number of bits are not the same, behaviour is undefined,
3352 : // so cast behaviour still works.
3353 :
3354 : bool
3355 291730 : operator_view::fold_range (irange &r, tree type,
3356 : const irange &op1, const irange &op2,
3357 : relation_trio rel) const
3358 : {
3359 291730 : return m_cast.fold_range (r, type, op1, op2, rel);
3360 : }
3361 :
3362 : bool
3363 0 : operator_view::fold_range (prange &r, tree type,
3364 : const prange &op1, const prange &op2,
3365 : relation_trio rel) const
3366 : {
3367 0 : return m_cast.fold_range (r, type, op1, op2, rel);
3368 : }
3369 : bool
3370 262970 : operator_view::fold_range (irange &r, tree type,
3371 : const prange &op1, const irange &op2,
3372 : relation_trio rel) const
3373 : {
3374 262970 : return m_cast.fold_range (r, type, op1, op2, rel);
3375 : }
3376 :
3377 : bool
3378 0 : operator_view::fold_range (prange &r, tree type,
3379 : const irange &op1, const prange &op2,
3380 : relation_trio rel) const
3381 : {
3382 0 : return m_cast.fold_range (r, type, op1, op2, rel);
3383 : }
3384 :
3385 : bool
3386 11124 : operator_view::op1_range (irange &r, tree type,
3387 : const irange &lhs, const irange &op2,
3388 : relation_trio rel) const
3389 : {
3390 11124 : return m_cast.op1_range (r, type, lhs, op2, rel);
3391 : }
3392 :
3393 : bool
3394 0 : operator_view::op1_range (prange &r, tree type,
3395 : const prange &lhs, const prange &op2,
3396 : relation_trio rel) const
3397 : {
3398 0 : return m_cast.op1_range (r, type, lhs, op2, rel);
3399 : }
3400 :
3401 : bool
3402 0 : operator_view::op1_range (irange &r, tree type,
3403 : const prange &lhs, const irange &op2,
3404 : relation_trio rel) const
3405 : {
3406 0 : return m_cast.op1_range (r, type, lhs, op2, rel);
3407 : }
3408 :
3409 : bool
3410 0 : operator_view::op1_range (prange &r, tree type,
3411 : const irange &lhs, const prange &op2,
3412 : relation_trio rel) const
3413 : {
3414 0 : return m_cast.op1_range (r, type, lhs, op2, rel);
3415 : }
3416 :
3417 : void
3418 0 : operator_view::update_bitmask (irange &r, const irange &lh,
3419 : const irange &rh) const
3420 : {
3421 0 : m_cast.update_bitmask (r, lh, rh);
3422 0 : }
3423 :
3424 :
3425 : class operator_logical_and : public range_operator
3426 : {
3427 : using range_operator::fold_range;
3428 : using range_operator::op1_range;
3429 : using range_operator::op2_range;
3430 : public:
3431 : bool fold_range (irange &r, tree type,
3432 : const irange &lh,
3433 : const irange &rh,
3434 : relation_trio rel = TRIO_VARYING) const final override;
3435 : bool op1_range (irange &r, tree type,
3436 : const irange &lhs,
3437 : const irange &op2,
3438 : relation_trio rel = TRIO_VARYING) const final override;
3439 : bool op2_range (irange &r, tree type,
3440 : const irange &lhs,
3441 : const irange &op1,
3442 : relation_trio rel = TRIO_VARYING) const final override;
3443 : // Check compatibility of all operands.
3444 0 : bool operand_check_p (tree t1, tree t2, tree t3) const final override
3445 0 : { return range_compatible_p (t1, t2) && range_compatible_p (t1, t3); }
3446 : } op_logical_and;
3447 :
3448 : bool
3449 0 : operator_logical_and::fold_range (irange &r, tree type,
3450 : const irange &lh,
3451 : const irange &rh,
3452 : relation_trio) const
3453 : {
3454 0 : if (empty_range_varying (r, type, lh, rh))
3455 0 : return true;
3456 :
3457 : // Precision of LHS and both operands must match.
3458 0 : if (TYPE_PRECISION (lh.type ()) != TYPE_PRECISION (type)
3459 0 : || TYPE_PRECISION (type) != TYPE_PRECISION (rh.type ()))
3460 : return false;
3461 :
3462 : // 0 && anything is 0.
3463 0 : if ((wi::eq_p (lh.lower_bound (), 0) && wi::eq_p (lh.upper_bound (), 0))
3464 0 : || (wi::eq_p (lh.lower_bound (), 0) && wi::eq_p (rh.upper_bound (), 0)))
3465 0 : r = range_false (type);
3466 0 : else if (lh.contains_zero_p () || rh.contains_zero_p ())
3467 : // To reach this point, there must be a logical 1 on each side, and
3468 : // the only remaining question is whether there is a zero or not.
3469 0 : r = range_true_and_false (type);
3470 : else
3471 0 : r = range_true (type);
3472 : return true;
3473 : }
3474 :
3475 : bool
3476 858926 : operator_logical_and::op1_range (irange &r, tree type,
3477 : const irange &lhs,
3478 : const irange &op2,
3479 : relation_trio) const
3480 : {
3481 858926 : switch (get_bool_state (r, lhs, type))
3482 : {
3483 446483 : case BRS_TRUE:
3484 : // A TRUE result means both sides of the AND must be true.
3485 446483 : r = range_true (type);
3486 446483 : return true;
3487 :
3488 411380 : case BRS_FALSE:
3489 : // A FALSE result when op2 is TRUE, must have op1 FALSE.
3490 411380 : if (!op2.contains_p (wi::zero (TYPE_PRECISION (op2.type ()))))
3491 : {
3492 10052 : r = range_false (type);
3493 10052 : return true;
3494 : }
3495 : break;
3496 :
3497 : default:
3498 : break;
3499 : }
3500 :
3501 : // Any other result means we cannot be sure of any result.
3502 402391 : r = range_true_and_false (type);
3503 402391 : return true;
3504 : }
3505 :
3506 : bool
3507 0 : operator_logical_and::op2_range (irange &r, tree type,
3508 : const irange &lhs,
3509 : const irange &op1,
3510 : relation_trio) const
3511 : {
3512 0 : return operator_logical_and::op1_range (r, type, lhs, op1);
3513 : }
3514 :
3515 :
3516 : void
3517 7521541 : operator_bitwise_and::update_bitmask (irange &r, const irange &lh,
3518 : const irange &rh) const
3519 : {
3520 7521541 : update_known_bitmask (r, BIT_AND_EXPR, lh, rh);
3521 7521541 : }
3522 :
3523 : // Optimize BIT_AND_EXPR, BIT_IOR_EXPR and BIT_XOR_EXPR of signed types
3524 : // by considering the number of leading redundant sign bit copies.
3525 : // clrsb (X op Y) = min (clrsb (X), clrsb (Y)), so for example
3526 : // [-1, 0] op [-1, 0] is [-1, 0] (where nonzero_bits doesn't help).
3527 : static bool
3528 184401 : wi_optimize_signed_bitwise_op (irange &r, tree type,
3529 : const wide_int &lh_lb, const wide_int &lh_ub,
3530 : const wide_int &rh_lb, const wide_int &rh_ub)
3531 : {
3532 368802 : int lh_clrsb = MIN (wi::clrsb (lh_lb), wi::clrsb (lh_ub));
3533 368802 : int rh_clrsb = MIN (wi::clrsb (rh_lb), wi::clrsb (rh_ub));
3534 184401 : int new_clrsb = MIN (lh_clrsb, rh_clrsb);
3535 184401 : if (new_clrsb == 0)
3536 : return false;
3537 12582 : int type_prec = TYPE_PRECISION (type);
3538 12582 : int rprec = (type_prec - new_clrsb) - 1;
3539 12582 : value_range_with_overflow (r, type,
3540 25164 : wi::mask (rprec, true, type_prec),
3541 12582 : wi::mask (rprec, false, type_prec));
3542 12582 : return true;
3543 : }
3544 :
3545 : // An AND of 8,16, 32 or 64 bits can produce a partial equivalence between
3546 : // the LHS and op1.
3547 :
3548 : relation_kind
3549 6795339 : operator_bitwise_and::lhs_op1_relation (const irange &lhs,
3550 : const irange &op1,
3551 : const irange &op2,
3552 : relation_kind) const
3553 : {
3554 6795339 : if (lhs.undefined_p () || op1.undefined_p () || op2.undefined_p ())
3555 : return VREL_VARYING;
3556 6789809 : if (!op2.singleton_p ())
3557 : return VREL_VARYING;
3558 : // if val == 0xff or 0xFFFF OR 0Xffffffff OR 0Xffffffffffffffff, return TRUE
3559 3798782 : int prec1 = TYPE_PRECISION (op1.type ());
3560 3798782 : int prec2 = TYPE_PRECISION (op2.type ());
3561 3798782 : int mask_prec = 0;
3562 3798782 : wide_int mask = op2.lower_bound ();
3563 3798782 : if (wi::eq_p (mask, wi::mask (8, false, prec2)))
3564 : mask_prec = 8;
3565 3708527 : else if (wi::eq_p (mask, wi::mask (16, false, prec2)))
3566 : mask_prec = 16;
3567 3691922 : else if (wi::eq_p (mask, wi::mask (32, false, prec2)))
3568 : mask_prec = 32;
3569 3533643 : else if (wi::eq_p (mask, wi::mask (64, false, prec2)))
3570 : mask_prec = 64;
3571 3798782 : return bits_to_pe (MIN (prec1, mask_prec));
3572 3798782 : }
3573 :
3574 : // Optimize BIT_AND_EXPR and BIT_IOR_EXPR in terms of a mask if
3575 : // possible. Basically, see if we can optimize:
3576 : //
3577 : // [LB, UB] op Z
3578 : // into:
3579 : // [LB op Z, UB op Z]
3580 : //
3581 : // If the optimization was successful, accumulate the range in R and
3582 : // return TRUE.
3583 :
3584 : static bool
3585 23277311 : wi_optimize_and_or (irange &r,
3586 : enum tree_code code,
3587 : tree type,
3588 : const wide_int &lh_lb, const wide_int &lh_ub,
3589 : const wide_int &rh_lb, const wide_int &rh_ub)
3590 : {
3591 : // Calculate the singleton mask among the ranges, if any.
3592 23277311 : wide_int lower_bound, upper_bound, mask;
3593 23277311 : if (wi::eq_p (rh_lb, rh_ub))
3594 : {
3595 21620789 : mask = rh_lb;
3596 21620789 : lower_bound = lh_lb;
3597 21620789 : upper_bound = lh_ub;
3598 : }
3599 1656522 : else if (wi::eq_p (lh_lb, lh_ub))
3600 : {
3601 353387 : mask = lh_lb;
3602 353387 : lower_bound = rh_lb;
3603 353387 : upper_bound = rh_ub;
3604 : }
3605 : else
3606 : return false;
3607 :
3608 : // If Z is a constant which (for op | its bitwise not) has n
3609 : // consecutive least significant bits cleared followed by m 1
3610 : // consecutive bits set immediately above it and either
3611 : // m + n == precision, or (x >> (m + n)) == (y >> (m + n)).
3612 : //
3613 : // The least significant n bits of all the values in the range are
3614 : // cleared or set, the m bits above it are preserved and any bits
3615 : // above these are required to be the same for all values in the
3616 : // range.
3617 21974176 : wide_int w = mask;
3618 21974176 : int m = 0, n = 0;
3619 21974176 : if (code == BIT_IOR_EXPR)
3620 6561253 : w = ~w;
3621 21974176 : if (wi::eq_p (w, 0))
3622 7514816 : n = w.get_precision ();
3623 : else
3624 : {
3625 14459360 : n = wi::ctz (w);
3626 14459366 : w = ~(w | wi::mask (n, false, w.get_precision ()));
3627 14459360 : if (wi::eq_p (w, 0))
3628 8772385 : m = w.get_precision () - n;
3629 : else
3630 5686975 : m = wi::ctz (w) - n;
3631 : }
3632 21974176 : wide_int new_mask = wi::mask (m + n, true, w.get_precision ());
3633 21974182 : if ((new_mask & lower_bound) != (new_mask & upper_bound))
3634 : return false;
3635 :
3636 17155330 : wide_int res_lb, res_ub;
3637 17155330 : if (code == BIT_AND_EXPR)
3638 : {
3639 10826341 : res_lb = wi::bit_and (lower_bound, mask);
3640 10826341 : res_ub = wi::bit_and (upper_bound, mask);
3641 : }
3642 6328989 : else if (code == BIT_IOR_EXPR)
3643 : {
3644 6328989 : res_lb = wi::bit_or (lower_bound, mask);
3645 6328989 : res_ub = wi::bit_or (upper_bound, mask);
3646 : }
3647 : else
3648 0 : gcc_unreachable ();
3649 17155330 : value_range_with_overflow (r, type, res_lb, res_ub);
3650 :
3651 : // Furthermore, if the mask is non-zero, an IOR cannot contain zero.
3652 17155330 : if (code == BIT_IOR_EXPR && wi::ne_p (mask, 0))
3653 : {
3654 3216274 : int_range<2> tmp;
3655 3216274 : tmp.set_nonzero (type);
3656 3216274 : r.intersect (tmp);
3657 3216274 : }
3658 17155330 : return true;
3659 62406823 : }
3660 :
3661 : // For range [LB, UB] compute two wide_int bit masks.
3662 : //
3663 : // In the MAYBE_NONZERO bit mask, if some bit is unset, it means that
3664 : // for all numbers in the range the bit is 0, otherwise it might be 0
3665 : // or 1.
3666 : //
3667 : // In the MUSTBE_NONZERO bit mask, if some bit is set, it means that
3668 : // for all numbers in the range the bit is 1, otherwise it might be 0
3669 : // or 1.
3670 :
3671 : void
3672 13272083 : wi_set_zero_nonzero_bits (tree type,
3673 : const wide_int &lb, const wide_int &ub,
3674 : wide_int &maybe_nonzero,
3675 : wide_int &mustbe_nonzero)
3676 : {
3677 13272083 : signop sign = TYPE_SIGN (type);
3678 :
3679 13272083 : if (wi::eq_p (lb, ub))
3680 5298741 : maybe_nonzero = mustbe_nonzero = lb;
3681 7973342 : else if (wi::ge_p (lb, 0, sign) || wi::lt_p (ub, 0, sign))
3682 : {
3683 7539893 : wide_int xor_mask = lb ^ ub;
3684 7539893 : maybe_nonzero = lb | ub;
3685 7539893 : mustbe_nonzero = lb & ub;
3686 7539893 : if (xor_mask != 0)
3687 : {
3688 7539893 : wide_int mask = wi::mask (wi::floor_log2 (xor_mask), false,
3689 15079786 : maybe_nonzero.get_precision ());
3690 7539893 : maybe_nonzero = maybe_nonzero | mask;
3691 7539898 : mustbe_nonzero = wi::bit_and_not (mustbe_nonzero, mask);
3692 7539893 : }
3693 7539893 : }
3694 : else
3695 : {
3696 433449 : maybe_nonzero = wi::minus_one (lb.get_precision ());
3697 433449 : mustbe_nonzero = wi::zero (lb.get_precision ());
3698 : }
3699 13272083 : }
3700 :
3701 : void
3702 16710767 : operator_bitwise_and::wi_fold (irange &r, tree type,
3703 : const wide_int &lh_lb,
3704 : const wide_int &lh_ub,
3705 : const wide_int &rh_lb,
3706 : const wide_int &rh_ub) const
3707 : {
3708 : // The AND algorithm does not handle complex signed operations well.
3709 : // If a signed range crosses the boundary between signed and unsigned
3710 : // process it as 2 ranges and union the results.
3711 16710767 : if (TYPE_SIGN (type) == SIGNED
3712 16710767 : && wi::neg_p (lh_lb, SIGNED) != wi::neg_p (lh_ub, SIGNED))
3713 : {
3714 623678 : int prec = TYPE_PRECISION (type);
3715 623678 : int_range_max tmp;
3716 : // Process [lh_lb, -1]
3717 623678 : wi_fold (tmp, type, lh_lb, wi::minus_one (prec), rh_lb, rh_ub);
3718 : // Now Process [0, rh_ub]
3719 623678 : wi_fold (r, type, wi::zero (prec), lh_ub, rh_lb, rh_ub);
3720 623678 : r.union_ (tmp);
3721 623678 : return;
3722 623678 : }
3723 :
3724 16087089 : if (wi_optimize_and_or (r, BIT_AND_EXPR, type, lh_lb, lh_ub, rh_lb, rh_ub))
3725 : return;
3726 :
3727 5260748 : wide_int maybe_nonzero_lh, mustbe_nonzero_lh;
3728 5260748 : wide_int maybe_nonzero_rh, mustbe_nonzero_rh;
3729 5260748 : wi_set_zero_nonzero_bits (type, lh_lb, lh_ub,
3730 : maybe_nonzero_lh, mustbe_nonzero_lh);
3731 5260748 : wi_set_zero_nonzero_bits (type, rh_lb, rh_ub,
3732 : maybe_nonzero_rh, mustbe_nonzero_rh);
3733 :
3734 5260748 : wide_int new_lb = mustbe_nonzero_lh & mustbe_nonzero_rh;
3735 5260748 : wide_int new_ub = maybe_nonzero_lh & maybe_nonzero_rh;
3736 5260748 : signop sign = TYPE_SIGN (type);
3737 5260748 : unsigned prec = TYPE_PRECISION (type);
3738 : // If both input ranges contain only negative values, we can
3739 : // truncate the result range maximum to the minimum of the
3740 : // input range maxima.
3741 5260748 : if (wi::lt_p (lh_ub, 0, sign) && wi::lt_p (rh_ub, 0, sign))
3742 : {
3743 46553 : new_ub = wi::min (new_ub, lh_ub, sign);
3744 46553 : new_ub = wi::min (new_ub, rh_ub, sign);
3745 : }
3746 : // If either input range contains only non-negative values
3747 : // we can truncate the result range maximum to the respective
3748 : // maximum of the input range.
3749 5260748 : if (wi::ge_p (lh_lb, 0, sign))
3750 4502659 : new_ub = wi::min (new_ub, lh_ub, sign);
3751 5260748 : if (wi::ge_p (rh_lb, 0, sign))
3752 5046263 : new_ub = wi::min (new_ub, rh_ub, sign);
3753 : // PR68217: In case of signed & sign-bit-CST should
3754 : // result in [-INF, 0] instead of [-INF, INF].
3755 5260748 : if (wi::gt_p (new_lb, new_ub, sign))
3756 : {
3757 52366 : wide_int sign_bit = wi::set_bit_in_zero (prec - 1, prec);
3758 52366 : if (sign == SIGNED
3759 52366 : && ((wi::eq_p (lh_lb, lh_ub)
3760 78 : && !wi::cmps (lh_lb, sign_bit))
3761 52366 : || (wi::eq_p (rh_lb, rh_ub)
3762 0 : && !wi::cmps (rh_lb, sign_bit))))
3763 : {
3764 0 : new_lb = wi::min_value (prec, sign);
3765 0 : new_ub = wi::zero (prec);
3766 : }
3767 52366 : }
3768 : // If the limits got swapped around, return varying.
3769 5260748 : if (wi::gt_p (new_lb, new_ub,sign))
3770 : {
3771 52366 : if (sign == SIGNED
3772 52366 : && wi_optimize_signed_bitwise_op (r, type,
3773 : lh_lb, lh_ub,
3774 : rh_lb, rh_ub))
3775 4336 : return;
3776 48030 : r.set_varying (type);
3777 : }
3778 : else
3779 5208382 : value_range_with_overflow (r, type, new_lb, new_ub);
3780 5260748 : }
3781 :
3782 : static void
3783 562858 : set_nonzero_range_from_mask (irange &r, tree type, const irange &lhs)
3784 : {
3785 562858 : if (lhs.undefined_p () || lhs.contains_zero_p ())
3786 296180 : r.set_varying (type);
3787 : else
3788 266678 : r.set_nonzero (type);
3789 562858 : }
3790 :
3791 : /* Find out smallest RES where RES > VAL && (RES & MASK) == RES, if any
3792 : (otherwise return VAL). VAL and MASK must be zero-extended for
3793 : precision PREC. If SGNBIT is non-zero, first xor VAL with SGNBIT
3794 : (to transform signed values into unsigned) and at the end xor
3795 : SGNBIT back. */
3796 :
3797 : wide_int
3798 35440 : masked_increment (const wide_int &val_in, const wide_int &mask,
3799 : const wide_int &sgnbit, unsigned int prec)
3800 : {
3801 35440 : wide_int bit = wi::one (prec), res;
3802 35440 : unsigned int i;
3803 :
3804 35440 : wide_int val = val_in ^ sgnbit;
3805 638327 : for (i = 0; i < prec; i++, bit += bit)
3806 : {
3807 592394 : res = mask;
3808 592394 : if ((res & bit) == 0)
3809 509850 : continue;
3810 82544 : res = bit - 1;
3811 82544 : res = wi::bit_and_not (val + bit, res);
3812 82544 : res &= mask;
3813 82544 : if (wi::gtu_p (res, val))
3814 24947 : return res ^ sgnbit;
3815 : }
3816 10493 : return val ^ sgnbit;
3817 35440 : }
3818 :
3819 : // This was shamelessly stolen from register_edge_assert_for_2 and
3820 : // adjusted to work with iranges.
3821 :
3822 : void
3823 3375555 : operator_bitwise_and::simple_op1_range_solver (irange &r, tree type,
3824 : const irange &lhs,
3825 : const irange &op2) const
3826 : {
3827 3375555 : if (!op2.singleton_p ())
3828 : {
3829 561936 : set_nonzero_range_from_mask (r, type, lhs);
3830 1130441 : return;
3831 : }
3832 2813619 : unsigned int nprec = TYPE_PRECISION (type);
3833 2813619 : wide_int cst2v = op2.lower_bound ();
3834 2813619 : bool cst2n = wi::neg_p (cst2v, TYPE_SIGN (type));
3835 2813619 : wide_int sgnbit;
3836 2813619 : if (cst2n)
3837 629168 : sgnbit = wi::set_bit_in_zero (nprec - 1, nprec);
3838 : else
3839 2184451 : sgnbit = wi::zero (nprec);
3840 :
3841 : // Solve [lhs.lower_bound (), +INF] = x & MASK.
3842 : //
3843 : // Minimum unsigned value for >= if (VAL & CST2) == VAL is VAL and
3844 : // maximum unsigned value is ~0. For signed comparison, if CST2
3845 : // doesn't have the most significant bit set, handle it similarly. If
3846 : // CST2 has MSB set, the minimum is the same, and maximum is ~0U/2.
3847 2813619 : wide_int valv = lhs.lower_bound ();
3848 2813619 : wide_int minv = valv & cst2v, maxv;
3849 2813619 : bool we_know_nothing = false;
3850 2813619 : if (minv != valv)
3851 : {
3852 : // If (VAL & CST2) != VAL, X & CST2 can't be equal to VAL.
3853 7735 : minv = masked_increment (valv, cst2v, sgnbit, nprec);
3854 7735 : if (minv == valv)
3855 : {
3856 : // If we can't determine anything on this bound, fall
3857 : // through and conservatively solve for the other end point.
3858 2813619 : we_know_nothing = true;
3859 : }
3860 : }
3861 4998070 : maxv = wi::mask (nprec - (cst2n ? 1 : 0), false, nprec);
3862 2813619 : if (we_know_nothing)
3863 3924 : r.set_varying (type);
3864 : else
3865 2809695 : create_possibly_reversed_range (r, type, minv, maxv);
3866 :
3867 : // Solve [-INF, lhs.upper_bound ()] = x & MASK.
3868 : //
3869 : // Minimum unsigned value for <= is 0 and maximum unsigned value is
3870 : // VAL | ~CST2 if (VAL & CST2) == VAL. Otherwise, find smallest
3871 : // VAL2 where
3872 : // VAL2 > VAL && (VAL2 & CST2) == VAL2 and use (VAL2 - 1) | ~CST2
3873 : // as maximum.
3874 : // For signed comparison, if CST2 doesn't have most significant bit
3875 : // set, handle it similarly. If CST2 has MSB set, the maximum is
3876 : // the same and minimum is INT_MIN.
3877 2813619 : valv = lhs.upper_bound ();
3878 2813619 : minv = valv & cst2v;
3879 2813619 : if (minv == valv)
3880 2785914 : maxv = valv;
3881 : else
3882 : {
3883 27705 : maxv = masked_increment (valv, cst2v, sgnbit, nprec);
3884 27705 : if (maxv == valv)
3885 : {
3886 : // If we couldn't determine anything on either bound, return
3887 : // undefined.
3888 6569 : if (we_know_nothing)
3889 3307 : r.set_undefined ();
3890 6569 : return;
3891 : }
3892 21136 : maxv -= 1;
3893 : }
3894 2807050 : maxv |= ~cst2v;
3895 2807050 : minv = sgnbit;
3896 2807050 : int_range<2> upper_bits;
3897 2807050 : create_possibly_reversed_range (upper_bits, type, minv, maxv);
3898 2807050 : r.intersect (upper_bits);
3899 2813619 : }
3900 :
3901 : bool
3902 3482924 : operator_bitwise_and::op1_range (irange &r, tree type,
3903 : const irange &lhs,
3904 : const irange &op2,
3905 : relation_trio) const
3906 : {
3907 3482924 : if (lhs.undefined_p ())
3908 : return false;
3909 3482924 : if (types_compatible_p (type, boolean_type_node))
3910 858926 : return op_logical_and.op1_range (r, type, lhs, op2);
3911 :
3912 2623998 : r.set_undefined ();
3913 8623551 : for (unsigned i = 0; i < lhs.num_pairs (); ++i)
3914 : {
3915 6751110 : int_range_max chunk (lhs.type (),
3916 6751110 : lhs.lower_bound (i),
3917 6751110 : lhs.upper_bound (i));
3918 3375555 : int_range_max res;
3919 3375555 : simple_op1_range_solver (res, type, chunk, op2);
3920 3375555 : r.union_ (res);
3921 3375555 : }
3922 2623998 : if (r.undefined_p ())
3923 922 : set_nonzero_range_from_mask (r, type, lhs);
3924 :
3925 : // For MASK == op1 & MASK, all the bits in MASK must be set in op1.
3926 2623998 : wide_int mask;
3927 2623998 : if (lhs == op2 && lhs.singleton_p (mask))
3928 : {
3929 351915 : r.update_bitmask (irange_bitmask (mask, ~mask));
3930 351915 : return true;
3931 : }
3932 :
3933 2272083 : if (!op2.singleton_p (mask))
3934 : return true;
3935 :
3936 : // For 0 = op1 & MASK, op1 is ~MASK.
3937 1761615 : if (lhs.zero_p ())
3938 : {
3939 638864 : wide_int nz = wi::bit_not (op2.get_nonzero_bits ());
3940 638864 : int_range<2> tmp (type);
3941 638864 : tmp.set_nonzero_bits (nz);
3942 638864 : r.intersect (tmp);
3943 638864 : }
3944 :
3945 1761615 : irange_bitmask lhs_bm = lhs.get_bitmask ();
3946 : // given [5,7] mask 0x3 value 0x4 = N & [7, 7] mask 0x0 value 0x7
3947 : // Nothing is known about the bits not specified in the mask value (op2),
3948 : // Start with the mask, 1's will occur where values were masked.
3949 1761615 : wide_int op1_mask = ~mask;
3950 : // Any bits that are unknown on the LHS are also unknown in op1,
3951 : // so union the current mask with the LHS mask.
3952 1761615 : op1_mask |= lhs_bm.mask ();
3953 : // The resulting zeros correspond to known bits in the LHS mask, and
3954 : // the LHS value should tell us what they are. Mask off any
3955 : // extraneous values that are not covered by the mask.
3956 1761615 : wide_int op1_value = lhs_bm.value () & ~op1_mask;
3957 1761615 : irange_bitmask op1_bm (op1_value, op1_mask);
3958 : // Intersect this mask with anything already known about the value.
3959 : // A return valueof false indicated the bitmask is an UNDEFINED range.
3960 1761615 : if (op1_bm.intersect (r.get_bitmask ()))
3961 1761615 : r.update_bitmask (op1_bm);
3962 : else
3963 0 : r.set_undefined ();
3964 1761615 : return true;
3965 4385613 : }
3966 :
3967 : bool
3968 920936 : operator_bitwise_and::op2_range (irange &r, tree type,
3969 : const irange &lhs,
3970 : const irange &op1,
3971 : relation_trio) const
3972 : {
3973 920936 : return operator_bitwise_and::op1_range (r, type, lhs, op1);
3974 : }
3975 :
3976 :
3977 : class operator_logical_or : public range_operator
3978 : {
3979 : using range_operator::fold_range;
3980 : using range_operator::op1_range;
3981 : using range_operator::op2_range;
3982 : public:
3983 : bool fold_range (irange &r, tree type,
3984 : const irange &lh,
3985 : const irange &rh,
3986 : relation_trio rel = TRIO_VARYING) const final override;
3987 : bool op1_range (irange &r, tree type,
3988 : const irange &lhs,
3989 : const irange &op2,
3990 : relation_trio rel = TRIO_VARYING) const final override;
3991 : bool op2_range (irange &r, tree type,
3992 : const irange &lhs,
3993 : const irange &op1,
3994 : relation_trio rel = TRIO_VARYING) const final override;
3995 : // Check compatibility of all operands.
3996 0 : bool operand_check_p (tree t1, tree t2, tree t3) const final override
3997 0 : { return range_compatible_p (t1, t2) && range_compatible_p (t1, t3); }
3998 : } op_logical_or;
3999 :
4000 : bool
4001 0 : operator_logical_or::fold_range (irange &r, tree type ATTRIBUTE_UNUSED,
4002 : const irange &lh,
4003 : const irange &rh,
4004 : relation_trio) const
4005 : {
4006 0 : if (empty_range_varying (r, type, lh, rh))
4007 0 : return true;
4008 :
4009 0 : r = lh;
4010 0 : r.union_ (rh);
4011 0 : return true;
4012 : }
4013 :
4014 : bool
4015 386916 : operator_logical_or::op1_range (irange &r, tree type,
4016 : const irange &lhs,
4017 : const irange &op2,
4018 : relation_trio) const
4019 : {
4020 386916 : switch (get_bool_state (r, lhs, type))
4021 : {
4022 236398 : case BRS_FALSE:
4023 : // A false result means both sides of the OR must be false.
4024 236398 : r = range_false (type);
4025 236398 : return true;
4026 :
4027 148769 : case BRS_TRUE:
4028 : // A TRUE result when op2 is FALSE must have op1 TRUE.
4029 148769 : if (op2.zero_p ())
4030 : {
4031 920 : r = range_true (type);
4032 920 : return true;
4033 : }
4034 : break;
4035 :
4036 : default:
4037 : break;
4038 : }
4039 :
4040 : // Any other result means we cannot be sure of any result.
4041 149598 : r = range_true_and_false (type);
4042 149598 : return true;
4043 : }
4044 :
4045 : bool
4046 0 : operator_logical_or::op2_range (irange &r, tree type,
4047 : const irange &lhs,
4048 : const irange &op1,
4049 : relation_trio) const
4050 : {
4051 0 : return operator_logical_or::op1_range (r, type, lhs, op1);
4052 : }
4053 :
4054 :
4055 : void
4056 2467429 : operator_bitwise_or::update_bitmask (irange &r, const irange &lh,
4057 : const irange &rh) const
4058 : {
4059 2467429 : update_known_bitmask (r, BIT_IOR_EXPR, lh, rh);
4060 2467429 : }
4061 :
4062 : void
4063 7190222 : operator_bitwise_or::wi_fold (irange &r, tree type,
4064 : const wide_int &lh_lb,
4065 : const wide_int &lh_ub,
4066 : const wide_int &rh_lb,
4067 : const wide_int &rh_ub) const
4068 : {
4069 7190222 : if (wi_optimize_and_or (r, BIT_IOR_EXPR, type, lh_lb, lh_ub, rh_lb, rh_ub))
4070 6517505 : return;
4071 :
4072 861233 : wide_int maybe_nonzero_lh, mustbe_nonzero_lh;
4073 861233 : wide_int maybe_nonzero_rh, mustbe_nonzero_rh;
4074 861233 : wi_set_zero_nonzero_bits (type, lh_lb, lh_ub,
4075 : maybe_nonzero_lh, mustbe_nonzero_lh);
4076 861233 : wi_set_zero_nonzero_bits (type, rh_lb, rh_ub,
4077 : maybe_nonzero_rh, mustbe_nonzero_rh);
4078 861233 : wide_int new_lb = mustbe_nonzero_lh | mustbe_nonzero_rh;
4079 861233 : wide_int new_ub = maybe_nonzero_lh | maybe_nonzero_rh;
4080 861233 : signop sign = TYPE_SIGN (type);
4081 : // If the input ranges contain only positive values we can
4082 : // truncate the minimum of the result range to the maximum
4083 : // of the input range minima.
4084 861233 : if (wi::ge_p (lh_lb, 0, sign)
4085 861233 : && wi::ge_p (rh_lb, 0, sign))
4086 : {
4087 643183 : new_lb = wi::max (new_lb, lh_lb, sign);
4088 643183 : new_lb = wi::max (new_lb, rh_lb, sign);
4089 : }
4090 : // If either input range contains only negative values
4091 : // we can truncate the minimum of the result range to the
4092 : // respective minimum range.
4093 861233 : if (wi::lt_p (lh_ub, 0, sign))
4094 20203 : new_lb = wi::max (new_lb, lh_lb, sign);
4095 861233 : if (wi::lt_p (rh_ub, 0, sign))
4096 10159 : new_lb = wi::max (new_lb, rh_lb, sign);
4097 : // If the limits got swapped around, return a conservative range.
4098 861233 : if (wi::gt_p (new_lb, new_ub, sign))
4099 : {
4100 : // Make sure that nonzero|X is nonzero.
4101 188516 : if (wi::gt_p (lh_lb, 0, sign)
4102 184018 : || wi::gt_p (rh_lb, 0, sign)
4103 125271 : || wi::lt_p (lh_ub, 0, sign)
4104 372534 : || wi::lt_p (rh_ub, 0, sign))
4105 63245 : r.set_nonzero (type);
4106 125271 : else if (sign == SIGNED
4107 125271 : && wi_optimize_signed_bitwise_op (r, type,
4108 : lh_lb, lh_ub,
4109 : rh_lb, rh_ub))
4110 : return;
4111 : else
4112 122668 : r.set_varying (type);
4113 : return;
4114 : }
4115 672717 : value_range_with_overflow (r, type, new_lb, new_ub);
4116 861263 : }
4117 :
4118 : bool
4119 2467429 : operator_bitwise_or::op1_op2_relation_effect (irange &lhs_range,
4120 : tree type,
4121 : const irange &,
4122 : const irange &,
4123 : relation_kind rel) const
4124 : {
4125 2467429 : if (rel == VREL_VARYING)
4126 : return false;
4127 :
4128 4636 : int_range<2> rel_range;
4129 :
4130 4636 : switch (rel)
4131 : {
4132 729 : case VREL_NE:
4133 729 : rel_range.set_nonzero (type);
4134 729 : break;
4135 : default:
4136 : return false;
4137 : }
4138 :
4139 729 : lhs_range.intersect (rel_range);
4140 729 : return true;
4141 4636 : }
4142 :
4143 : bool
4144 658217 : operator_bitwise_or::op1_range (irange &r, tree type,
4145 : const irange &lhs,
4146 : const irange &op2,
4147 : relation_trio) const
4148 : {
4149 658217 : if (lhs.undefined_p ())
4150 : return false;
4151 : // If this is really a logical wi_fold, call that.
4152 658217 : if (types_compatible_p (type, boolean_type_node))
4153 386916 : return op_logical_or.op1_range (r, type, lhs, op2);
4154 :
4155 271301 : if (lhs.zero_p ())
4156 : {
4157 80398 : r.set_zero (type);
4158 80398 : return true;
4159 : }
4160 :
4161 : // if (A < 0 && B < 0)
4162 : // Sometimes gets translated to
4163 : // _1 = A | B
4164 : // if (_1 < 0))
4165 : // It is useful for ranger to recognize a positive LHS means the RHS
4166 : // operands are also positive when dealing with the ELSE range..
4167 275835 : if (TYPE_SIGN (type) == SIGNED && wi::ge_p (lhs.lower_bound (), 0, SIGNED))
4168 : {
4169 28915 : unsigned prec = TYPE_PRECISION (type);
4170 28915 : r.set (type, wi::zero (prec), wi::max_value (prec, SIGNED));
4171 28915 : return true;
4172 : }
4173 161988 : r.set_varying (type);
4174 161988 : return true;
4175 : }
4176 :
4177 : bool
4178 322398 : operator_bitwise_or::op2_range (irange &r, tree type,
4179 : const irange &lhs,
4180 : const irange &op1,
4181 : relation_trio) const
4182 : {
4183 322398 : return operator_bitwise_or::op1_range (r, type, lhs, op1);
4184 : }
4185 :
4186 : void
4187 89883 : operator_bitwise_xor::update_bitmask (irange &r, const irange &lh,
4188 : const irange &rh) const
4189 : {
4190 89883 : update_known_bitmask (r, BIT_XOR_EXPR, lh, rh);
4191 89883 : }
4192 :
4193 : bool
4194 311694 : operator_bitwise_xor::fold_range (irange &r, tree type,
4195 : const irange &lh, const irange &rh,
4196 : relation_trio rel) const
4197 : {
4198 : // Handle X ^ UNDEFINED = UNDEFINED.
4199 311694 : if (lh.undefined_p () || rh.undefined_p ())
4200 : {
4201 473 : r.set_undefined ();
4202 473 : return true;
4203 : }
4204 :
4205 : // Next, handle X ^ X == [0, 0].
4206 311221 : if (rel.op1_op2 () == VREL_EQ)
4207 : {
4208 74 : r.set_zero (type);
4209 74 : return true;
4210 : }
4211 :
4212 : // If either operand is VARYING, the result is VARYING.
4213 311147 : if (lh.varying_p () || rh.varying_p ())
4214 : {
4215 : // If the operands are not equal, zero is not possible.
4216 218454 : if (rel.op1_op2 () != VREL_NE)
4217 217404 : r.set_varying (type);
4218 : else
4219 1050 : r.set_nonzero (type);
4220 : return true;
4221 : }
4222 :
4223 : // Now deal with X ^ 0 == X.
4224 92693 : if (lh.zero_p ())
4225 : {
4226 2231 : r = rh;
4227 2231 : return true;
4228 : }
4229 90462 : if (rh.zero_p ())
4230 : {
4231 579 : r = lh;
4232 579 : return true;
4233 : }
4234 :
4235 : // Start with the legacy range. This can sometimes pick up values
4236 : // when there are a lot of subranges and fold_range aggregates them.
4237 89883 : bool res = range_operator::fold_range (r, type, lh, rh, rel);
4238 :
4239 : // Calculate the XOR identity : x ^ y = (x | y) & ~(x & y)
4240 : // AND and OR are already much better optimized.
4241 89883 : int_range_max tmp1, tmp2, tmp3, new_result;
4242 89883 : int_range<2> varying;
4243 89883 : varying.set_varying (type);
4244 :
4245 89883 : if (m_or.fold_range (tmp1, type, lh, rh, rel)
4246 89883 : && m_and.fold_range (tmp2, type, lh, rh, rel)
4247 89883 : && m_not.fold_range (tmp3, type, tmp2, varying, rel)
4248 179766 : && m_and.fold_range (new_result, type, tmp1, tmp3, rel))
4249 : {
4250 : // If the operands are not equal, or the LH does not contain any
4251 : // element of the RH, zero is not possible.
4252 89883 : tmp1 = lh;
4253 89883 : if (rel.op1_op2 () == VREL_NE
4254 89883 : || (tmp1.intersect (rh) && tmp1.undefined_p ()))
4255 : {
4256 33078 : tmp1.set_nonzero (type);
4257 33078 : new_result.intersect (tmp1);
4258 : }
4259 :
4260 : // Combine with the legacy range if there was one.
4261 89883 : if (res)
4262 89883 : r.intersect (new_result);
4263 : else
4264 0 : r = new_result;
4265 : return true;
4266 : }
4267 : return res;
4268 89883 : }
4269 :
4270 : void
4271 176885 : operator_bitwise_xor::wi_fold (irange &r, tree type,
4272 : const wide_int &lh_lb,
4273 : const wide_int &lh_ub,
4274 : const wide_int &rh_lb,
4275 : const wide_int &rh_ub) const
4276 : {
4277 176885 : signop sign = TYPE_SIGN (type);
4278 176885 : wide_int maybe_nonzero_lh, mustbe_nonzero_lh;
4279 176885 : wide_int maybe_nonzero_rh, mustbe_nonzero_rh;
4280 176885 : wi_set_zero_nonzero_bits (type, lh_lb, lh_ub,
4281 : maybe_nonzero_lh, mustbe_nonzero_lh);
4282 176885 : wi_set_zero_nonzero_bits (type, rh_lb, rh_ub,
4283 : maybe_nonzero_rh, mustbe_nonzero_rh);
4284 :
4285 530655 : wide_int result_zero_bits = ((mustbe_nonzero_lh & mustbe_nonzero_rh)
4286 530655 : | ~(maybe_nonzero_lh | maybe_nonzero_rh));
4287 176885 : wide_int result_one_bits
4288 353770 : = (wi::bit_and_not (mustbe_nonzero_lh, maybe_nonzero_rh)
4289 353770 : | wi::bit_and_not (mustbe_nonzero_rh, maybe_nonzero_lh));
4290 176885 : wide_int new_ub = ~result_zero_bits;
4291 176885 : wide_int new_lb = result_one_bits;
4292 :
4293 : // If the range has all positive or all negative values, the result
4294 : // is better than VARYING.
4295 176885 : if (wi::lt_p (new_lb, 0, sign) || wi::ge_p (new_ub, 0, sign))
4296 170121 : value_range_with_overflow (r, type, new_lb, new_ub);
4297 6764 : else if (sign == SIGNED
4298 6764 : && wi_optimize_signed_bitwise_op (r, type,
4299 : lh_lb, lh_ub,
4300 : rh_lb, rh_ub))
4301 : ; /* Do nothing. */
4302 : else
4303 1121 : r.set_varying (type);
4304 :
4305 : /* Furthermore, XOR is non-zero if its arguments can't be equal. */
4306 176885 : if (wi::lt_p (lh_ub, rh_lb, sign)
4307 114378 : || wi::lt_p (rh_ub, lh_lb, sign)
4308 291263 : || wi::ne_p (result_one_bits, 0))
4309 : {
4310 83871 : int_range<2> tmp;
4311 83871 : tmp.set_nonzero (type);
4312 83871 : r.intersect (tmp);
4313 83871 : }
4314 176885 : }
4315 :
4316 : bool
4317 89883 : operator_bitwise_xor::op1_op2_relation_effect (irange &lhs_range,
4318 : tree type,
4319 : const irange &,
4320 : const irange &,
4321 : relation_kind rel) const
4322 : {
4323 89883 : if (rel == VREL_VARYING)
4324 : return false;
4325 :
4326 3568 : int_range<2> rel_range;
4327 :
4328 3568 : switch (rel)
4329 : {
4330 0 : case VREL_EQ:
4331 0 : rel_range.set_zero (type);
4332 0 : break;
4333 480 : case VREL_NE:
4334 480 : rel_range.set_nonzero (type);
4335 480 : break;
4336 : default:
4337 : return false;
4338 : }
4339 :
4340 480 : lhs_range.intersect (rel_range);
4341 480 : return true;
4342 3568 : }
4343 :
4344 : bool
4345 84519 : operator_bitwise_xor::op1_range (irange &r, tree type,
4346 : const irange &lhs,
4347 : const irange &op2,
4348 : relation_trio) const
4349 : {
4350 84519 : if (lhs.undefined_p () || lhs.varying_p ())
4351 : {
4352 2057 : r = lhs;
4353 2057 : return true;
4354 : }
4355 82462 : if (types_compatible_p (type, boolean_type_node))
4356 : {
4357 1833 : switch (get_bool_state (r, lhs, type))
4358 : {
4359 805 : case BRS_TRUE:
4360 805 : if (op2.varying_p ())
4361 773 : r.set_varying (type);
4362 32 : else if (op2.zero_p ())
4363 24 : r = range_true (type);
4364 : // See get_bool_state for the rationale
4365 8 : else if (op2.undefined_p () || op2.contains_zero_p ())
4366 0 : r = range_true_and_false (type);
4367 : else
4368 8 : r = range_false (type);
4369 : break;
4370 1028 : case BRS_FALSE:
4371 1028 : r = op2;
4372 1028 : break;
4373 : default:
4374 : break;
4375 : }
4376 : return true;
4377 : }
4378 80629 : r.set_varying (type);
4379 80629 : return true;
4380 : }
4381 :
4382 : bool
4383 34431 : operator_bitwise_xor::op2_range (irange &r, tree type,
4384 : const irange &lhs,
4385 : const irange &op1,
4386 : relation_trio) const
4387 : {
4388 34431 : return operator_bitwise_xor::op1_range (r, type, lhs, op1);
4389 : }
4390 :
4391 : class operator_trunc_mod : public range_operator
4392 : {
4393 : using range_operator::op1_range;
4394 : using range_operator::op2_range;
4395 : using range_operator::update_bitmask;
4396 : using range_operator::op1_op2_relation_effect;
4397 : public:
4398 : virtual void wi_fold (irange &r, tree type,
4399 : const wide_int &lh_lb,
4400 : const wide_int &lh_ub,
4401 : const wide_int &rh_lb,
4402 : const wide_int &rh_ub) const;
4403 : virtual bool op1_range (irange &r, tree type,
4404 : const irange &lhs,
4405 : const irange &op2,
4406 : relation_trio) const;
4407 : virtual bool op2_range (irange &r, tree type,
4408 : const irange &lhs,
4409 : const irange &op1,
4410 : relation_trio) const;
4411 1186054 : void update_bitmask (irange &r, const irange &lh, const irange &rh) const
4412 1186054 : { update_known_bitmask (r, TRUNC_MOD_EXPR, lh, rh); }
4413 : bool op1_op2_relation_effect (irange &lhs_range,
4414 : tree type,
4415 : const irange &op1_range,
4416 : const irange &op2_range,
4417 : relation_kind rel) const final override;
4418 : protected:
4419 : bool same_quotient (wide_int &lb, wide_int &ub, const wide_int &x_lb,
4420 : const wide_int &x_ub, const wide_int &y_lb,
4421 : const wide_int &y_ub, signop sign) const;
4422 : } op_trunc_mod;
4423 :
4424 :
4425 : bool
4426 1427039 : operator_trunc_mod::same_quotient (wide_int &lb, wide_int &ub,
4427 : const wide_int &x_lb, const wide_int &x_ub,
4428 : const wide_int &y_lb, const wide_int &y_ub,
4429 : signop sign) const
4430 : {
4431 : // Y must not contain zero.
4432 1427039 : if (wi::ge_p (y_ub, 0, sign) && wi::le_p (y_lb, 0, sign))
4433 940552 : return false;
4434 :
4435 : // If all endpoints do not have the same quotient, nothing further.
4436 486487 : wide_int q = wi::div_trunc (x_lb, y_lb, sign);
4437 486534 : if (q != wi::div_trunc (x_lb, y_ub, sign))
4438 : return false;
4439 446586 : if (q != wi::div_trunc (x_ub, y_lb, sign))
4440 : return false;
4441 46239 : if (q != wi::div_trunc (x_ub, y_ub, sign))
4442 : return false;
4443 :
4444 : // Compute the range extremes.
4445 45840 : wide_int v1 = x_lb - q * y_lb;
4446 45840 : wide_int v2 = x_lb - q * y_ub;
4447 45840 : wide_int v3 = x_ub - q * y_lb;
4448 45840 : wide_int v4 = x_ub - q * y_ub;
4449 :
4450 : // And choose the minimum and maximum
4451 45840 : lb = wi::min (v1, v2, sign);
4452 45840 : lb = wi::min (lb, v3, sign);
4453 45840 : lb = wi::min (lb, v4, sign);
4454 :
4455 45840 : ub = wi::max (v1, v2, sign);
4456 45840 : ub = wi::max (ub, v3, sign);
4457 45840 : ub = wi::max (ub, v4, sign);
4458 :
4459 45840 : return true;
4460 532327 : }
4461 :
4462 : void
4463 1461554 : operator_trunc_mod::wi_fold (irange &r, tree type,
4464 : const wide_int &lh_lb,
4465 : const wide_int &lh_ub,
4466 : const wide_int &rh_lb,
4467 : const wide_int &rh_ub) const
4468 : {
4469 1461554 : wide_int new_lb, new_ub, tmp;
4470 1461554 : signop sign = TYPE_SIGN (type);
4471 1461554 : unsigned prec = TYPE_PRECISION (type);
4472 :
4473 : // Mod 0 is undefined.
4474 1461554 : if (wi_zero_p (type, rh_lb, rh_ub))
4475 : {
4476 10239 : r.set_undefined ();
4477 10239 : return;
4478 : }
4479 :
4480 : // Check for constant and try to fold.
4481 1693408 : if (lh_lb == lh_ub && rh_lb == rh_ub)
4482 : {
4483 24302 : wi::overflow_type ov = wi::OVF_NONE;
4484 24302 : tmp = wi::mod_trunc (lh_lb, rh_lb, sign, &ov);
4485 24302 : if (ov == wi::OVF_NONE)
4486 : {
4487 24276 : r = int_range<2> (type, tmp, tmp);
4488 24276 : return;
4489 : }
4490 : }
4491 :
4492 : // ABS (A % B) < ABS (B) and either 0 <= A % B <= A or A <= A % B <= 0.
4493 1427039 : new_ub = rh_ub - 1;
4494 1427039 : if (sign == SIGNED)
4495 : {
4496 627961 : tmp = -1 - rh_lb;
4497 627961 : new_ub = wi::smax (new_ub, tmp);
4498 : }
4499 :
4500 627961 : if (sign == UNSIGNED)
4501 799078 : new_lb = wi::zero (prec);
4502 : else
4503 : {
4504 627961 : new_lb = -new_ub;
4505 627961 : tmp = lh_lb;
4506 627961 : if (wi::gts_p (tmp, 0))
4507 157609 : tmp = wi::zero (prec);
4508 628015 : new_lb = wi::smax (new_lb, tmp);
4509 : }
4510 1427039 : tmp = lh_ub;
4511 1427039 : if (sign == SIGNED && wi::neg_p (tmp))
4512 33287 : tmp = wi::zero (prec);
4513 1427039 : new_ub = wi::min (new_ub, tmp, sign);
4514 :
4515 1427039 : value_range_with_overflow (r, type, new_lb, new_ub);
4516 :
4517 : // If all X/Y combinations have the same quotient, refine using
4518 : // X % Y == X - Q * Y.
4519 1427039 : if (same_quotient (new_lb, new_ub, lh_lb, lh_ub, rh_lb, rh_ub, sign))
4520 : {
4521 45840 : int_range<2> refined (type, new_lb, new_ub);
4522 45840 : r.intersect (refined);
4523 45840 : }
4524 1461894 : }
4525 :
4526 : bool
4527 514661 : operator_trunc_mod::op1_range (irange &r, tree type,
4528 : const irange &lhs,
4529 : const irange &,
4530 : relation_trio) const
4531 : {
4532 514661 : if (lhs.undefined_p ())
4533 : return false;
4534 : // PR 91029.
4535 514661 : signop sign = TYPE_SIGN (type);
4536 514661 : unsigned prec = TYPE_PRECISION (type);
4537 : // (a % b) >= x && x > 0 , then a >= x.
4538 514754 : if (wi::gt_p (lhs.lower_bound (), 0, sign))
4539 : {
4540 134952 : r.set (type, lhs.lower_bound (), wi::max_value (prec, sign));
4541 134919 : return true;
4542 : }
4543 : // (a % b) <= x && x < 0 , then a <= x.
4544 379802 : if (wi::lt_p (lhs.upper_bound (), 0, sign))
4545 : {
4546 8645 : r.set (type, wi::min_value (prec, sign), lhs.upper_bound ());
4547 8645 : return true;
4548 : }
4549 : return false;
4550 : }
4551 :
4552 : bool
4553 331714 : operator_trunc_mod::op2_range (irange &r, tree type,
4554 : const irange &lhs,
4555 : const irange &,
4556 : relation_trio) const
4557 : {
4558 331714 : if (lhs.undefined_p ())
4559 : return false;
4560 : // PR 91029.
4561 331714 : signop sign = TYPE_SIGN (type);
4562 331714 : unsigned prec = TYPE_PRECISION (type);
4563 : // (a % b) >= x && x > 0 , then b is in ~[-x, x] for signed
4564 : // or b > x for unsigned.
4565 331748 : if (wi::gt_p (lhs.lower_bound (), 0, sign))
4566 : {
4567 54369 : if (sign == SIGNED)
4568 1995 : r.set (type, wi::neg (lhs.lower_bound ()),
4569 3990 : lhs.lower_bound (), VR_ANTI_RANGE);
4570 52386 : else if (wi::lt_p (lhs.lower_bound (), wi::max_value (prec, sign),
4571 : sign))
4572 52392 : r.set (type, lhs.lower_bound () + 1, wi::max_value (prec, sign));
4573 : else
4574 : return false;
4575 : return true;
4576 : }
4577 : // (a % b) <= x && x < 0 , then b is in ~[x, -x].
4578 277373 : if (wi::lt_p (lhs.upper_bound (), 0, sign))
4579 : {
4580 5384 : if (wi::gt_p (lhs.upper_bound (), wi::min_value (prec, sign), sign))
4581 5384 : r.set (type, lhs.upper_bound (),
4582 10768 : wi::neg (lhs.upper_bound ()), VR_ANTI_RANGE);
4583 : else
4584 : return false;
4585 5384 : return true;
4586 : }
4587 : return false;
4588 : }
4589 :
4590 : bool
4591 1186054 : operator_trunc_mod::op1_op2_relation_effect (irange &lhs_range,
4592 : tree type,
4593 : const irange &,
4594 : const irange &,
4595 : relation_kind rel) const
4596 : {
4597 1186054 : if (rel == VREL_VARYING)
4598 : return false;
4599 :
4600 6361 : int_range<2> rel_range;
4601 :
4602 6361 : switch (rel)
4603 : {
4604 12 : case VREL_EQ:
4605 12 : rel_range.set_zero (type);
4606 12 : break;
4607 : default:
4608 : return false;
4609 : }
4610 :
4611 12 : lhs_range.intersect (rel_range);
4612 12 : return true;
4613 6361 : }
4614 :
4615 :
4616 : class operator_logical_not : public range_operator
4617 : {
4618 : using range_operator::fold_range;
4619 : using range_operator::op1_range;
4620 : public:
4621 : bool fold_range (irange &r, tree type,
4622 : const irange &lh,
4623 : const irange &rh,
4624 : relation_trio rel = TRIO_VARYING) const final override;
4625 : bool op1_range (irange &r, tree type,
4626 : const irange &lhs,
4627 : const irange &op2,
4628 : relation_trio rel = TRIO_VARYING) const final override;
4629 : // Check compatibility of LHS and op1.
4630 0 : bool operand_check_p (tree t1, tree t2, tree) const final override
4631 0 : { return range_compatible_p (t1, t2); }
4632 : } op_logical_not;
4633 :
4634 : // Folding a logical NOT, oddly enough, involves doing nothing on the
4635 : // forward pass through. During the initial walk backwards, the
4636 : // logical NOT reversed the desired outcome on the way back, so on the
4637 : // way forward all we do is pass the range forward.
4638 : //
4639 : // b_2 = x_1 < 20
4640 : // b_3 = !b_2
4641 : // if (b_3)
4642 : // to determine the TRUE branch, walking backward
4643 : // if (b_3) if ([1,1])
4644 : // b_3 = !b_2 [1,1] = ![0,0]
4645 : // b_2 = x_1 < 20 [0,0] = x_1 < 20, false, so x_1 == [20, 255]
4646 : // which is the result we are looking for.. so.. pass it through.
4647 :
4648 : bool
4649 248587 : operator_logical_not::fold_range (irange &r, tree type,
4650 : const irange &lh,
4651 : const irange &rh ATTRIBUTE_UNUSED,
4652 : relation_trio) const
4653 : {
4654 248587 : if (empty_range_varying (r, type, lh, rh))
4655 0 : return true;
4656 :
4657 248587 : r = lh;
4658 248587 : if (!lh.varying_p () && !lh.undefined_p ())
4659 : {
4660 55755 : if (!r.invert ())
4661 : return false;
4662 : }
4663 : return true;
4664 : }
4665 :
4666 : bool
4667 29840 : operator_logical_not::op1_range (irange &r,
4668 : tree type,
4669 : const irange &lhs,
4670 : const irange &op2,
4671 : relation_trio) const
4672 : {
4673 : // Logical NOT is involutary...do it again.
4674 29840 : return fold_range (r, type, lhs, op2);
4675 : }
4676 :
4677 : bool
4678 624352 : operator_bitwise_not::fold_range (irange &r, tree type,
4679 : const irange &lh,
4680 : const irange &rh,
4681 : relation_trio) const
4682 : {
4683 624352 : if (empty_range_varying (r, type, lh, rh))
4684 103 : return true;
4685 :
4686 624249 : if (types_compatible_p (type, boolean_type_node))
4687 218747 : return op_logical_not.fold_range (r, type, lh, rh);
4688 :
4689 : // ~X is simply -1 - X.
4690 811004 : int_range<1> minusone (type, wi::minus_one (TYPE_PRECISION (type)),
4691 811004 : wi::minus_one (TYPE_PRECISION (type)));
4692 405502 : return range_op_handler (MINUS_EXPR).fold_range (r, type, minusone, lh);
4693 405502 : }
4694 :
4695 : bool
4696 53190 : operator_bitwise_not::op1_range (irange &r, tree type,
4697 : const irange &lhs,
4698 : const irange &op2,
4699 : relation_trio) const
4700 : {
4701 53190 : if (lhs.undefined_p ())
4702 : return false;
4703 53190 : if (types_compatible_p (type, boolean_type_node))
4704 29840 : return op_logical_not.op1_range (r, type, lhs, op2);
4705 :
4706 : // ~X is -1 - X and since bitwise NOT is involutary...do it again.
4707 23350 : return fold_range (r, type, lhs, op2);
4708 : }
4709 :
4710 : void
4711 0 : operator_bitwise_not::update_bitmask (irange &r, const irange &lh,
4712 : const irange &rh) const
4713 : {
4714 0 : update_known_bitmask (r, BIT_NOT_EXPR, lh, rh);
4715 0 : }
4716 :
4717 :
4718 : bool
4719 292331 : operator_cst::fold_range (irange &r, tree type ATTRIBUTE_UNUSED,
4720 : const irange &lh,
4721 : const irange &rh ATTRIBUTE_UNUSED,
4722 : relation_trio) const
4723 : {
4724 292331 : r = lh;
4725 292331 : return true;
4726 : }
4727 :
4728 :
4729 : // Determine if there is a relationship between LHS and OP1.
4730 :
4731 : relation_kind
4732 956999 : operator_identity::lhs_op1_relation (const irange &lhs,
4733 : const irange &op1 ATTRIBUTE_UNUSED,
4734 : const irange &op2 ATTRIBUTE_UNUSED,
4735 : relation_kind) const
4736 : {
4737 956999 : if (lhs.undefined_p ())
4738 607 : return VREL_VARYING;
4739 : // Simply a copy, so they are equivalent.
4740 : return VREL_EQ;
4741 : }
4742 :
4743 : bool
4744 956999 : operator_identity::fold_range (irange &r, tree type ATTRIBUTE_UNUSED,
4745 : const irange &lh,
4746 : const irange &rh ATTRIBUTE_UNUSED,
4747 : relation_trio) const
4748 : {
4749 956999 : r = lh;
4750 956999 : return true;
4751 : }
4752 :
4753 : bool
4754 298718 : operator_identity::op1_range (irange &r, tree type ATTRIBUTE_UNUSED,
4755 : const irange &lhs,
4756 : const irange &op2 ATTRIBUTE_UNUSED,
4757 : relation_trio) const
4758 : {
4759 298718 : r = lhs;
4760 298718 : return true;
4761 : }
4762 :
4763 :
4764 : class operator_unknown : public range_operator
4765 : {
4766 : using range_operator::fold_range;
4767 : public:
4768 : virtual bool fold_range (irange &r, tree type,
4769 : const irange &op1,
4770 : const irange &op2,
4771 : relation_trio rel = TRIO_VARYING) const;
4772 : } op_unknown;
4773 :
4774 : bool
4775 1381706 : operator_unknown::fold_range (irange &r, tree type,
4776 : const irange &lh ATTRIBUTE_UNUSED,
4777 : const irange &rh ATTRIBUTE_UNUSED,
4778 : relation_trio) const
4779 : {
4780 1381706 : r.set_varying (type);
4781 1381706 : return true;
4782 : }
4783 :
4784 :
4785 : void
4786 107508 : operator_abs::wi_fold (irange &r, tree type,
4787 : const wide_int &lh_lb, const wide_int &lh_ub,
4788 : const wide_int &rh_lb ATTRIBUTE_UNUSED,
4789 : const wide_int &rh_ub ATTRIBUTE_UNUSED) const
4790 : {
4791 107508 : wide_int min, max;
4792 107508 : signop sign = TYPE_SIGN (type);
4793 107508 : unsigned prec = TYPE_PRECISION (type);
4794 :
4795 : // Pass through LH for the easy cases.
4796 107508 : if (sign == UNSIGNED || wi::ge_p (lh_lb, 0, sign))
4797 : {
4798 10254 : r = int_range<1> (type, lh_lb, lh_ub);
4799 10254 : return;
4800 : }
4801 :
4802 : // -TYPE_MIN_VALUE = TYPE_MIN_VALUE with flag_wrapv so we can't get
4803 : // a useful range.
4804 97254 : wide_int min_value = wi::min_value (prec, sign);
4805 97254 : wide_int max_value = wi::max_value (prec, sign);
4806 97254 : if (!TYPE_OVERFLOW_UNDEFINED (type) && wi::eq_p (lh_lb, min_value))
4807 : {
4808 612 : r.set_varying (type);
4809 612 : return;
4810 : }
4811 :
4812 : // ABS_EXPR may flip the range around, if the original range
4813 : // included negative values.
4814 96642 : if (wi::eq_p (lh_lb, min_value))
4815 : {
4816 : // ABS ([-MIN, -MIN]) isn't representable, but we have traditionally
4817 : // returned [-MIN,-MIN] so this preserves that behavior. PR37078
4818 34120 : if (wi::eq_p (lh_ub, min_value))
4819 : {
4820 104 : r = int_range<1> (type, min_value, min_value);
4821 104 : return;
4822 : }
4823 34016 : min = max_value;
4824 : }
4825 : else
4826 62522 : min = wi::abs (lh_lb);
4827 :
4828 96538 : if (wi::eq_p (lh_ub, min_value))
4829 0 : max = max_value;
4830 : else
4831 96538 : max = wi::abs (lh_ub);
4832 :
4833 : // If the range contains zero then we know that the minimum value in the
4834 : // range will be zero.
4835 96538 : if (wi::le_p (lh_lb, 0, sign) && wi::ge_p (lh_ub, 0, sign))
4836 : {
4837 86196 : if (wi::gt_p (min, max, sign))
4838 52344 : max = min;
4839 86196 : min = wi::zero (prec);
4840 : }
4841 : else
4842 : {
4843 : // If the range was reversed, swap MIN and MAX.
4844 10342 : if (wi::gt_p (min, max, sign))
4845 10180 : std::swap (min, max);
4846 : }
4847 :
4848 : // If the new range has its limits swapped around (MIN > MAX), then
4849 : // the operation caused one of them to wrap around. The only thing
4850 : // we know is that the result is positive.
4851 96538 : if (wi::gt_p (min, max, sign))
4852 : {
4853 0 : min = wi::zero (prec);
4854 0 : max = max_value;
4855 : }
4856 96538 : r = int_range<1> (type, min, max);
4857 108224 : }
4858 :
4859 : bool
4860 88856 : operator_abs::op1_range (irange &r, tree type,
4861 : const irange &lhs,
4862 : const irange &op2,
4863 : relation_trio) const
4864 : {
4865 88856 : if (empty_range_varying (r, type, lhs, op2))
4866 0 : return true;
4867 88856 : if (TYPE_UNSIGNED (type))
4868 : {
4869 0 : r = lhs;
4870 0 : return true;
4871 : }
4872 : // Start with the positives because negatives are an impossible result.
4873 88856 : int_range_max positives = range_positives (type);
4874 88856 : positives.intersect (lhs);
4875 88856 : r = positives;
4876 : // Then add the negative of each pair:
4877 : // ABS(op1) = [5,20] would yield op1 => [-20,-5][5,20].
4878 267235 : for (unsigned i = 0; i < positives.num_pairs (); ++i)
4879 89523 : r.union_ (int_range<1> (type,
4880 179046 : -positives.upper_bound (i),
4881 268569 : -positives.lower_bound (i)));
4882 : // With flag_wrapv, -TYPE_MIN_VALUE = TYPE_MIN_VALUE which is
4883 : // unrepresentable. Add -TYPE_MIN_VALUE in this case.
4884 88856 : wide_int min_value = wi::min_value (TYPE_PRECISION (type), TYPE_SIGN (type));
4885 88856 : wide_int lb = lhs.lower_bound ();
4886 88856 : if (!TYPE_OVERFLOW_UNDEFINED (type) && wi::eq_p (lb, min_value))
4887 164 : r.union_ (int_range<2> (type, lb, lb));
4888 88856 : return true;
4889 88856 : }
4890 :
4891 : void
4892 100471 : operator_abs::update_bitmask (irange &r, const irange &lh,
4893 : const irange &rh) const
4894 : {
4895 100471 : update_known_bitmask (r, ABS_EXPR, lh, rh);
4896 100471 : }
4897 :
4898 : class operator_absu : public range_operator
4899 : {
4900 : using range_operator::update_bitmask;
4901 : public:
4902 : virtual void wi_fold (irange &r, tree type,
4903 : const wide_int &lh_lb, const wide_int &lh_ub,
4904 : const wide_int &rh_lb, const wide_int &rh_ub)
4905 : const final override;
4906 : virtual void update_bitmask (irange &r, const irange &lh,
4907 : const irange &rh) const final override;
4908 : } op_absu;
4909 :
4910 : void
4911 9921 : operator_absu::wi_fold (irange &r, tree type,
4912 : const wide_int &lh_lb, const wide_int &lh_ub,
4913 : const wide_int &rh_lb ATTRIBUTE_UNUSED,
4914 : const wide_int &rh_ub ATTRIBUTE_UNUSED) const
4915 : {
4916 9921 : wide_int new_lb, new_ub;
4917 :
4918 : // Pass through VR0 the easy cases.
4919 9921 : if (wi::ges_p (lh_lb, 0))
4920 : {
4921 380 : new_lb = lh_lb;
4922 380 : new_ub = lh_ub;
4923 : }
4924 : else
4925 : {
4926 9541 : new_lb = wi::abs (lh_lb);
4927 9541 : new_ub = wi::abs (lh_ub);
4928 :
4929 : // If the range contains zero then we know that the minimum
4930 : // value in the range will be zero.
4931 9541 : if (wi::ges_p (lh_ub, 0))
4932 : {
4933 8252 : if (wi::gtu_p (new_lb, new_ub))
4934 6941 : new_ub = new_lb;
4935 8252 : new_lb = wi::zero (TYPE_PRECISION (type));
4936 : }
4937 : else
4938 1289 : std::swap (new_lb, new_ub);
4939 : }
4940 :
4941 9921 : gcc_checking_assert (TYPE_UNSIGNED (type));
4942 9921 : r = int_range<1> (type, new_lb, new_ub);
4943 9921 : }
4944 :
4945 : void
4946 9579 : operator_absu::update_bitmask (irange &r, const irange &lh,
4947 : const irange &rh) const
4948 : {
4949 9579 : update_known_bitmask (r, ABSU_EXPR, lh, rh);
4950 9579 : }
4951 :
4952 :
4953 : bool
4954 542342 : operator_negate::fold_range (irange &r, tree type,
4955 : const irange &lh,
4956 : const irange &rh,
4957 : relation_trio) const
4958 : {
4959 542342 : if (empty_range_varying (r, type, lh, rh))
4960 979 : return true;
4961 :
4962 : // -X is simply 0 - X.
4963 541363 : int_range<1> zero;
4964 541363 : zero.set_zero (type);
4965 541363 : return range_op_handler (MINUS_EXPR).fold_range (r, type, zero, lh);
4966 541363 : }
4967 :
4968 : bool
4969 78074 : operator_negate::op1_range (irange &r, tree type,
4970 : const irange &lhs,
4971 : const irange &op2,
4972 : relation_trio) const
4973 : {
4974 : // NEGATE is involutory.
4975 78074 : return fold_range (r, type, lhs, op2);
4976 : }
4977 :
4978 :
4979 : bool
4980 0 : operator_addr_expr::fold_range (irange &r, tree type,
4981 : const irange &lh,
4982 : const irange &rh,
4983 : relation_trio) const
4984 : {
4985 0 : if (empty_range_varying (r, type, lh, rh))
4986 0 : return true;
4987 :
4988 : // Return a non-null pointer of the LHS type (passed in op2).
4989 0 : if (lh.zero_p ())
4990 0 : r.set_zero (type);
4991 0 : else if (lh.undefined_p () || lh.contains_zero_p ())
4992 0 : r.set_varying (type);
4993 : else
4994 0 : r.set_nonzero (type);
4995 : return true;
4996 : }
4997 :
4998 : bool
4999 0 : operator_addr_expr::op1_range (irange &r, tree type,
5000 : const irange &lhs,
5001 : const irange &op2,
5002 : relation_trio) const
5003 : {
5004 0 : if (empty_range_varying (r, type, lhs, op2))
5005 0 : return true;
5006 :
5007 : // Return a non-null pointer of the LHS type (passed in op2), but only
5008 : // if we cant overflow, eitherwise a no-zero offset could wrap to zero.
5009 : // See PR 111009.
5010 0 : if (!lhs.undefined_p () && !lhs.contains_zero_p () && TYPE_OVERFLOW_UNDEFINED (type))
5011 0 : r.set_nonzero (type);
5012 : else
5013 0 : r.set_varying (type);
5014 : return true;
5015 : }
5016 :
5017 : // Initialize any integral operators to the primary table
5018 :
5019 : void
5020 293417 : range_op_table::initialize_integral_ops ()
5021 : {
5022 293417 : set (TRUNC_DIV_EXPR, op_trunc_div);
5023 293417 : set (FLOOR_DIV_EXPR, op_floor_div);
5024 293417 : set (ROUND_DIV_EXPR, op_round_div);
5025 293417 : set (CEIL_DIV_EXPR, op_ceil_div);
5026 293417 : set (EXACT_DIV_EXPR, op_exact_div);
5027 293417 : set (LSHIFT_EXPR, op_lshift);
5028 293417 : set (RSHIFT_EXPR, op_rshift);
5029 293417 : set (TRUTH_AND_EXPR, op_logical_and);
5030 293417 : set (TRUTH_OR_EXPR, op_logical_or);
5031 293417 : set (TRUNC_MOD_EXPR, op_trunc_mod);
5032 293417 : set (TRUTH_NOT_EXPR, op_logical_not);
5033 293417 : set (IMAGPART_EXPR, op_unknown);
5034 293417 : set (REALPART_EXPR, op_unknown);
5035 293417 : set (ABSU_EXPR, op_absu);
5036 293417 : set (OP_WIDEN_MULT_SIGNED, op_widen_mult_signed);
5037 293417 : set (OP_WIDEN_MULT_UNSIGNED, op_widen_mult_unsigned);
5038 293417 : set (OP_WIDEN_MULT_SIGNED_UNSIGNED, op_widen_mult_signed_unsigned);
5039 293417 : set (OP_WIDEN_PLUS_SIGNED, op_widen_plus_signed);
5040 293417 : set (OP_WIDEN_PLUS_UNSIGNED, op_widen_plus_unsigned);
5041 :
5042 293417 : }
5043 :
5044 : bool
5045 82246 : operator_plus::overflow_free_p (const irange &lh, const irange &rh,
5046 : relation_trio) const
5047 : {
5048 82246 : if (lh.undefined_p () || rh.undefined_p ())
5049 : return false;
5050 :
5051 82246 : tree type = lh.type ();
5052 82246 : if (TYPE_OVERFLOW_UNDEFINED (type))
5053 : return true;
5054 :
5055 50692 : wi::overflow_type ovf;
5056 50692 : signop sgn = TYPE_SIGN (type);
5057 50692 : wide_int wmax0 = lh.upper_bound ();
5058 50692 : wide_int wmax1 = rh.upper_bound ();
5059 50692 : wi::add (wmax0, wmax1, sgn, &ovf);
5060 50692 : if (ovf != wi::OVF_NONE)
5061 : return false;
5062 :
5063 26056 : if (TYPE_UNSIGNED (type))
5064 : return true;
5065 :
5066 346 : wide_int wmin0 = lh.lower_bound ();
5067 346 : wide_int wmin1 = rh.lower_bound ();
5068 346 : wi::add (wmin0, wmin1, sgn, &ovf);
5069 346 : if (ovf != wi::OVF_NONE)
5070 237 : return false;
5071 :
5072 : return true;
5073 51038 : }
5074 :
5075 : bool
5076 223 : operator_minus::overflow_free_p (const irange &lh, const irange &rh,
5077 : relation_trio) const
5078 : {
5079 223 : if (lh.undefined_p () || rh.undefined_p ())
5080 : return false;
5081 :
5082 223 : tree type = lh.type ();
5083 223 : if (TYPE_OVERFLOW_UNDEFINED (type))
5084 : return true;
5085 :
5086 106 : wi::overflow_type ovf;
5087 106 : signop sgn = TYPE_SIGN (type);
5088 106 : wide_int wmin0 = lh.lower_bound ();
5089 106 : wide_int wmax1 = rh.upper_bound ();
5090 106 : wi::sub (wmin0, wmax1, sgn, &ovf);
5091 106 : if (ovf != wi::OVF_NONE)
5092 : return false;
5093 :
5094 38 : if (TYPE_UNSIGNED (type))
5095 : return true;
5096 :
5097 37 : wide_int wmax0 = lh.upper_bound ();
5098 37 : wide_int wmin1 = rh.lower_bound ();
5099 37 : wi::sub (wmax0, wmin1, sgn, &ovf);
5100 37 : if (ovf != wi::OVF_NONE)
5101 29 : return false;
5102 :
5103 : return true;
5104 143 : }
5105 :
5106 : bool
5107 4097 : operator_mult::overflow_free_p (const irange &lh, const irange &rh,
5108 : relation_trio) const
5109 : {
5110 4097 : if (lh.undefined_p () || rh.undefined_p ())
5111 : return false;
5112 :
5113 4097 : tree type = lh.type ();
5114 4097 : if (TYPE_OVERFLOW_UNDEFINED (type))
5115 : return true;
5116 :
5117 3419 : wi::overflow_type ovf;
5118 3419 : signop sgn = TYPE_SIGN (type);
5119 3419 : wide_int wmax0 = lh.upper_bound ();
5120 3419 : wide_int wmax1 = rh.upper_bound ();
5121 3419 : wi::mul (wmax0, wmax1, sgn, &ovf);
5122 3419 : if (ovf != wi::OVF_NONE)
5123 : return false;
5124 :
5125 99 : if (TYPE_UNSIGNED (type))
5126 : return true;
5127 :
5128 21 : wide_int wmin0 = lh.lower_bound ();
5129 21 : wide_int wmin1 = rh.lower_bound ();
5130 21 : wi::mul (wmin0, wmin1, sgn, &ovf);
5131 21 : if (ovf != wi::OVF_NONE)
5132 : return false;
5133 :
5134 21 : wi::mul (wmin0, wmax1, sgn, &ovf);
5135 21 : if (ovf != wi::OVF_NONE)
5136 : return false;
5137 :
5138 21 : wi::mul (wmax0, wmin1, sgn, &ovf);
5139 21 : if (ovf != wi::OVF_NONE)
5140 0 : return false;
5141 :
5142 : return true;
5143 3440 : }
5144 :
5145 : #if CHECKING_P
5146 : #include "selftest.h"
5147 :
5148 : namespace selftest
5149 : {
5150 : #define INT(x) wi::shwi ((x), TYPE_PRECISION (integer_type_node))
5151 : #define UINT(x) wi::uhwi ((x), TYPE_PRECISION (unsigned_type_node))
5152 : #define INT16(x) wi::shwi ((x), TYPE_PRECISION (short_integer_type_node))
5153 : #define UINT16(x) wi::uhwi ((x), TYPE_PRECISION (short_unsigned_type_node))
5154 : #define SCHAR(x) wi::shwi ((x), TYPE_PRECISION (signed_char_type_node))
5155 : #define UCHAR(x) wi::uhwi ((x), TYPE_PRECISION (unsigned_char_type_node))
5156 :
5157 : static void
5158 4 : range_op_cast_tests ()
5159 : {
5160 4 : int_range<2> r0, r1, r2, rold;
5161 4 : r0.set_varying (integer_type_node);
5162 4 : wide_int maxint = r0.upper_bound ();
5163 :
5164 : // If a range is in any way outside of the range for the converted
5165 : // to range, default to the range for the new type.
5166 4 : r0.set_varying (short_integer_type_node);
5167 4 : wide_int minshort = r0.lower_bound ();
5168 4 : wide_int maxshort = r0.upper_bound ();
5169 4 : if (TYPE_PRECISION (integer_type_node)
5170 4 : > TYPE_PRECISION (short_integer_type_node))
5171 : {
5172 8 : r1 = int_range<1> (integer_type_node,
5173 4 : wi::zero (TYPE_PRECISION (integer_type_node)),
5174 8 : maxint);
5175 4 : range_cast (r1, short_integer_type_node);
5176 4 : ASSERT_TRUE (r1.lower_bound () == minshort
5177 : && r1.upper_bound() == maxshort);
5178 : }
5179 :
5180 : // (unsigned char)[-5,-1] => [251,255].
5181 4 : r0 = rold = int_range<1> (signed_char_type_node, SCHAR (-5), SCHAR (-1));
5182 4 : range_cast (r0, unsigned_char_type_node);
5183 4 : ASSERT_TRUE (r0 == int_range<1> (unsigned_char_type_node,
5184 : UCHAR (251), UCHAR (255)));
5185 4 : range_cast (r0, signed_char_type_node);
5186 4 : ASSERT_TRUE (r0 == rold);
5187 :
5188 : // (signed char)[15, 150] => [-128,-106][15,127].
5189 4 : r0 = rold = int_range<1> (unsigned_char_type_node, UCHAR (15), UCHAR (150));
5190 4 : range_cast (r0, signed_char_type_node);
5191 4 : r1 = int_range<1> (signed_char_type_node, SCHAR (15), SCHAR (127));
5192 4 : r2 = int_range<1> (signed_char_type_node, SCHAR (-128), SCHAR (-106));
5193 4 : r1.union_ (r2);
5194 4 : ASSERT_TRUE (r1 == r0);
5195 4 : range_cast (r0, unsigned_char_type_node);
5196 4 : ASSERT_TRUE (r0 == rold);
5197 :
5198 : // (unsigned char)[-5, 5] => [0,5][251,255].
5199 4 : r0 = rold = int_range<1> (signed_char_type_node, SCHAR (-5), SCHAR (5));
5200 4 : range_cast (r0, unsigned_char_type_node);
5201 4 : r1 = int_range<1> (unsigned_char_type_node, UCHAR (251), UCHAR (255));
5202 4 : r2 = int_range<1> (unsigned_char_type_node, UCHAR (0), UCHAR (5));
5203 4 : r1.union_ (r2);
5204 4 : ASSERT_TRUE (r0 == r1);
5205 4 : range_cast (r0, signed_char_type_node);
5206 4 : ASSERT_TRUE (r0 == rold);
5207 :
5208 : // (unsigned char)[-5,5] => [0,5][251,255].
5209 4 : r0 = int_range<1> (integer_type_node, INT (-5), INT (5));
5210 4 : range_cast (r0, unsigned_char_type_node);
5211 4 : r1 = int_range<1> (unsigned_char_type_node, UCHAR (0), UCHAR (5));
5212 4 : r1.union_ (int_range<1> (unsigned_char_type_node, UCHAR (251), UCHAR (255)));
5213 4 : ASSERT_TRUE (r0 == r1);
5214 :
5215 : // (unsigned char)[5U,1974U] => [0,255].
5216 4 : r0 = int_range<1> (unsigned_type_node, UINT (5), UINT (1974));
5217 4 : range_cast (r0, unsigned_char_type_node);
5218 4 : ASSERT_TRUE (r0 == int_range<1> (unsigned_char_type_node, UCHAR (0), UCHAR (255)));
5219 4 : range_cast (r0, integer_type_node);
5220 : // Going to a wider range should not sign extend.
5221 4 : ASSERT_TRUE (r0 == int_range<1> (integer_type_node, INT (0), INT (255)));
5222 :
5223 : // (unsigned char)[-350,15] => [0,255].
5224 4 : r0 = int_range<1> (integer_type_node, INT (-350), INT (15));
5225 4 : range_cast (r0, unsigned_char_type_node);
5226 4 : ASSERT_TRUE (r0 == (int_range<1>
5227 : (unsigned_char_type_node,
5228 : min_limit (unsigned_char_type_node),
5229 : max_limit (unsigned_char_type_node))));
5230 :
5231 : // Casting [-120,20] from signed char to unsigned short.
5232 : // => [0, 20][0xff88, 0xffff].
5233 4 : r0 = int_range<1> (signed_char_type_node, SCHAR (-120), SCHAR (20));
5234 4 : range_cast (r0, short_unsigned_type_node);
5235 4 : r1 = int_range<1> (short_unsigned_type_node, UINT16 (0), UINT16 (20));
5236 8 : r2 = int_range<1> (short_unsigned_type_node,
5237 12 : UINT16 (0xff88), UINT16 (0xffff));
5238 4 : r1.union_ (r2);
5239 4 : ASSERT_TRUE (r0 == r1);
5240 : // A truncating cast back to signed char will work because [-120, 20]
5241 : // is representable in signed char.
5242 4 : range_cast (r0, signed_char_type_node);
5243 4 : ASSERT_TRUE (r0 == int_range<1> (signed_char_type_node,
5244 : SCHAR (-120), SCHAR (20)));
5245 :
5246 : // unsigned char -> signed short
5247 : // (signed short)[(unsigned char)25, (unsigned char)250]
5248 : // => [(signed short)25, (signed short)250]
5249 4 : r0 = rold = int_range<1> (unsigned_char_type_node, UCHAR (25), UCHAR (250));
5250 4 : range_cast (r0, short_integer_type_node);
5251 4 : r1 = int_range<1> (short_integer_type_node, INT16 (25), INT16 (250));
5252 4 : ASSERT_TRUE (r0 == r1);
5253 4 : range_cast (r0, unsigned_char_type_node);
5254 4 : ASSERT_TRUE (r0 == rold);
5255 :
5256 : // Test casting a wider signed [-MIN,MAX] to a narrower unsigned.
5257 8 : r0 = int_range<1> (long_long_integer_type_node,
5258 4 : min_limit (long_long_integer_type_node),
5259 8 : max_limit (long_long_integer_type_node));
5260 4 : range_cast (r0, short_unsigned_type_node);
5261 8 : r1 = int_range<1> (short_unsigned_type_node,
5262 4 : min_limit (short_unsigned_type_node),
5263 8 : max_limit (short_unsigned_type_node));
5264 4 : ASSERT_TRUE (r0 == r1);
5265 :
5266 : // Casting NONZERO to a narrower type will wrap/overflow so
5267 : // it's just the entire range for the narrower type.
5268 : //
5269 : // "NOT 0 at signed 32-bits" ==> [-MIN_32,-1][1, +MAX_32]. This is
5270 : // is outside of the range of a smaller range, return the full
5271 : // smaller range.
5272 4 : if (TYPE_PRECISION (integer_type_node)
5273 4 : > TYPE_PRECISION (short_integer_type_node))
5274 : {
5275 4 : r0.set_nonzero (integer_type_node);
5276 4 : range_cast (r0, short_integer_type_node);
5277 8 : r1 = int_range<1> (short_integer_type_node,
5278 4 : min_limit (short_integer_type_node),
5279 8 : max_limit (short_integer_type_node));
5280 4 : ASSERT_TRUE (r0 == r1);
5281 : }
5282 :
5283 : // Casting NONZERO from a narrower signed to a wider signed.
5284 : //
5285 : // NONZERO signed 16-bits is [-MIN_16,-1][1, +MAX_16].
5286 : // Converting this to 32-bits signed is [-MIN_16,-1][1, +MAX_16].
5287 4 : r0.set_nonzero (short_integer_type_node);
5288 4 : range_cast (r0, integer_type_node);
5289 4 : r1 = int_range<1> (integer_type_node, INT (-32768), INT (-1));
5290 4 : r2 = int_range<1> (integer_type_node, INT (1), INT (32767));
5291 4 : r1.union_ (r2);
5292 4 : ASSERT_TRUE (r0 == r1);
5293 4 : }
5294 :
5295 : static void
5296 4 : range_op_lshift_tests ()
5297 : {
5298 : // Test that 0x808.... & 0x8.... still contains 0x8....
5299 : // for a large set of numbers.
5300 4 : {
5301 4 : int_range_max res;
5302 4 : tree big_type = long_long_unsigned_type_node;
5303 4 : unsigned big_prec = TYPE_PRECISION (big_type);
5304 : // big_num = 0x808,0000,0000,0000
5305 4 : wide_int big_num = wi::lshift (wi::uhwi (0x808, big_prec),
5306 8 : wi::uhwi (48, big_prec));
5307 8 : op_bitwise_and.fold_range (res, big_type,
5308 8 : int_range <1> (big_type),
5309 8 : int_range <1> (big_type, big_num, big_num));
5310 : // val = 0x8,0000,0000,0000
5311 4 : wide_int val = wi::lshift (wi::uhwi (8, big_prec),
5312 8 : wi::uhwi (48, big_prec));
5313 4 : ASSERT_TRUE (res.contains_p (val));
5314 4 : }
5315 :
5316 4 : if (TYPE_PRECISION (unsigned_type_node) > 31)
5317 : {
5318 : // unsigned VARYING = op1 << 1 should be VARYING.
5319 4 : int_range<2> lhs (unsigned_type_node);
5320 4 : int_range<2> shift (unsigned_type_node, INT (1), INT (1));
5321 4 : int_range_max op1;
5322 4 : op_lshift.op1_range (op1, unsigned_type_node, lhs, shift);
5323 4 : ASSERT_TRUE (op1.varying_p ());
5324 :
5325 : // 0 = op1 << 1 should be [0,0], [0x8000000, 0x8000000].
5326 4 : int_range<2> zero (unsigned_type_node, UINT (0), UINT (0));
5327 4 : op_lshift.op1_range (op1, unsigned_type_node, zero, shift);
5328 4 : ASSERT_TRUE (op1.num_pairs () == 2);
5329 : // Remove the [0,0] range.
5330 4 : op1.intersect (zero);
5331 4 : ASSERT_TRUE (op1.num_pairs () == 1);
5332 : // op1 << 1 should be [0x8000,0x8000] << 1,
5333 : // which should result in [0,0].
5334 4 : int_range_max result;
5335 4 : op_lshift.fold_range (result, unsigned_type_node, op1, shift);
5336 4 : ASSERT_TRUE (result == zero);
5337 4 : }
5338 : // signed VARYING = op1 << 1 should be VARYING.
5339 4 : if (TYPE_PRECISION (integer_type_node) > 31)
5340 : {
5341 : // unsigned VARYING = op1 << 1 should be VARYING.
5342 4 : int_range<2> lhs (integer_type_node);
5343 4 : int_range<2> shift (integer_type_node, INT (1), INT (1));
5344 4 : int_range_max op1;
5345 4 : op_lshift.op1_range (op1, integer_type_node, lhs, shift);
5346 4 : ASSERT_TRUE (op1.varying_p ());
5347 :
5348 : // 0 = op1 << 1 should be [0,0], [0x8000000, 0x8000000].
5349 4 : int_range<2> zero (integer_type_node, INT (0), INT (0));
5350 4 : op_lshift.op1_range (op1, integer_type_node, zero, shift);
5351 4 : ASSERT_TRUE (op1.num_pairs () == 2);
5352 : // Remove the [0,0] range.
5353 4 : op1.intersect (zero);
5354 4 : ASSERT_TRUE (op1.num_pairs () == 1);
5355 : // op1 << 1 should be [0x8000,0x8000] << 1,
5356 : // which should result in [0,0].
5357 4 : int_range_max result;
5358 4 : op_lshift.fold_range (result, unsigned_type_node, op1, shift);
5359 4 : ASSERT_TRUE (result == zero);
5360 4 : }
5361 4 : }
5362 :
5363 : static void
5364 4 : range_op_rshift_tests ()
5365 : {
5366 : // unsigned: [3, MAX] = OP1 >> 1
5367 4 : {
5368 4 : int_range_max lhs (unsigned_type_node,
5369 4 : UINT (3), max_limit (unsigned_type_node));
5370 4 : int_range_max one (unsigned_type_node,
5371 8 : wi::one (TYPE_PRECISION (unsigned_type_node)),
5372 8 : wi::one (TYPE_PRECISION (unsigned_type_node)));
5373 4 : int_range_max op1;
5374 4 : op_rshift.op1_range (op1, unsigned_type_node, lhs, one);
5375 4 : ASSERT_FALSE (op1.contains_p (UINT (3)));
5376 4 : }
5377 :
5378 : // signed: [3, MAX] = OP1 >> 1
5379 4 : {
5380 4 : int_range_max lhs (integer_type_node,
5381 4 : INT (3), max_limit (integer_type_node));
5382 4 : int_range_max one (integer_type_node, INT (1), INT (1));
5383 4 : int_range_max op1;
5384 4 : op_rshift.op1_range (op1, integer_type_node, lhs, one);
5385 4 : ASSERT_FALSE (op1.contains_p (INT (-2)));
5386 4 : }
5387 :
5388 : // This is impossible, so OP1 should be [].
5389 : // signed: [MIN, MIN] = OP1 >> 1
5390 4 : {
5391 4 : int_range_max lhs (integer_type_node,
5392 4 : min_limit (integer_type_node),
5393 4 : min_limit (integer_type_node));
5394 4 : int_range_max one (integer_type_node, INT (1), INT (1));
5395 4 : int_range_max op1;
5396 4 : op_rshift.op1_range (op1, integer_type_node, lhs, one);
5397 4 : ASSERT_TRUE (op1.undefined_p ());
5398 4 : }
5399 :
5400 : // signed: ~[-1] = OP1 >> 31
5401 4 : if (TYPE_PRECISION (integer_type_node) > 31)
5402 : {
5403 4 : int_range_max lhs (integer_type_node, INT (-1), INT (-1), VR_ANTI_RANGE);
5404 4 : int_range_max shift (integer_type_node, INT (31), INT (31));
5405 4 : int_range_max op1;
5406 4 : op_rshift.op1_range (op1, integer_type_node, lhs, shift);
5407 4 : int_range_max negatives = range_negatives (integer_type_node);
5408 4 : negatives.intersect (op1);
5409 4 : ASSERT_TRUE (negatives.undefined_p ());
5410 4 : }
5411 4 : }
5412 :
5413 : static void
5414 4 : range_op_bitwise_and_tests ()
5415 : {
5416 4 : int_range_max res;
5417 4 : wide_int min = min_limit (integer_type_node);
5418 4 : wide_int max = max_limit (integer_type_node);
5419 4 : wide_int tiny = wi::add (min, wi::one (TYPE_PRECISION (integer_type_node)));
5420 4 : int_range_max i1 (integer_type_node, tiny, max);
5421 4 : int_range_max i2 (integer_type_node, INT (255), INT (255));
5422 :
5423 : // [MIN+1, MAX] = OP1 & 255: OP1 is VARYING
5424 4 : op_bitwise_and.op1_range (res, integer_type_node, i1, i2);
5425 4 : ASSERT_TRUE (res == int_range<1> (integer_type_node));
5426 :
5427 : // VARYING = OP1 & 255: OP1 is VARYING
5428 4 : i1 = int_range<1> (integer_type_node);
5429 4 : op_bitwise_and.op1_range (res, integer_type_node, i1, i2);
5430 4 : ASSERT_TRUE (res == int_range<1> (integer_type_node));
5431 :
5432 : // For 0 = x & MASK, x is ~MASK.
5433 4 : {
5434 4 : int_range<2> zero (integer_type_node, INT (0), INT (0));
5435 4 : int_range<2> mask = int_range<2> (integer_type_node, INT (7), INT (7));
5436 4 : op_bitwise_and.op1_range (res, integer_type_node, zero, mask);
5437 4 : wide_int inv = wi::shwi (~7U, TYPE_PRECISION (integer_type_node));
5438 4 : ASSERT_TRUE (res.get_nonzero_bits () == inv);
5439 4 : }
5440 :
5441 : // (NONZERO | X) is nonzero.
5442 4 : i1.set_nonzero (integer_type_node);
5443 4 : i2.set_varying (integer_type_node);
5444 4 : op_bitwise_or.fold_range (res, integer_type_node, i1, i2);
5445 4 : ASSERT_FALSE (res.contains_zero_p ());
5446 :
5447 : // (NEGATIVE | X) is nonzero.
5448 4 : i1 = int_range<1> (integer_type_node, INT (-5), INT (-3));
5449 4 : i2.set_varying (integer_type_node);
5450 4 : op_bitwise_or.fold_range (res, integer_type_node, i1, i2);
5451 4 : ASSERT_FALSE (res.contains_p (INT (0)));
5452 4 : }
5453 :
5454 : static void
5455 4 : range_relational_tests ()
5456 : {
5457 4 : int_range<2> lhs (unsigned_char_type_node);
5458 4 : int_range<2> op1 (unsigned_char_type_node, UCHAR (8), UCHAR (10));
5459 4 : int_range<2> op2 (unsigned_char_type_node, UCHAR (20), UCHAR (20));
5460 :
5461 : // Never wrapping additions mean LHS > OP1.
5462 4 : relation_kind code = op_plus.lhs_op1_relation (lhs, op1, op2, VREL_VARYING);
5463 4 : ASSERT_TRUE (code == VREL_GT);
5464 :
5465 : // Most wrapping additions mean nothing...
5466 4 : op1 = int_range<2> (unsigned_char_type_node, UCHAR (8), UCHAR (10));
5467 4 : op2 = int_range<2> (unsigned_char_type_node, UCHAR (0), UCHAR (255));
5468 4 : code = op_plus.lhs_op1_relation (lhs, op1, op2, VREL_VARYING);
5469 4 : ASSERT_TRUE (code == VREL_VARYING);
5470 :
5471 : // However, always wrapping additions mean LHS < OP1.
5472 4 : op1 = int_range<2> (unsigned_char_type_node, UCHAR (1), UCHAR (255));
5473 4 : op2 = int_range<2> (unsigned_char_type_node, UCHAR (255), UCHAR (255));
5474 4 : code = op_plus.lhs_op1_relation (lhs, op1, op2, VREL_VARYING);
5475 4 : ASSERT_TRUE (code == VREL_LT);
5476 4 : }
5477 :
5478 : void
5479 4 : range_op_tests ()
5480 : {
5481 4 : range_op_rshift_tests ();
5482 4 : range_op_lshift_tests ();
5483 4 : range_op_bitwise_and_tests ();
5484 4 : range_op_cast_tests ();
5485 4 : range_relational_tests ();
5486 :
5487 4 : extern void range_op_float_tests ();
5488 4 : range_op_float_tests ();
5489 4 : }
5490 :
5491 : } // namespace selftest
5492 :
5493 : #endif // CHECKING_P
|
