Branch data Line data Source code
1 : : /* Code for range operators.
2 : : Copyright (C) 2017-2025 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 : : operator_equal op_equal;
55 : : operator_not_equal op_not_equal;
56 : : operator_lt op_lt;
57 : : operator_le op_le;
58 : : operator_gt op_gt;
59 : : operator_ge op_ge;
60 : : operator_identity op_ident;
61 : : operator_cst op_cst;
62 : : operator_cast op_cast;
63 : : operator_plus op_plus;
64 : : operator_abs op_abs;
65 : : operator_minus op_minus;
66 : : operator_negate op_negate;
67 : : operator_mult op_mult;
68 : : operator_addr_expr op_addr;
69 : : operator_bitwise_not op_bitwise_not;
70 : : operator_bitwise_xor op_bitwise_xor;
71 : : operator_bitwise_and op_bitwise_and;
72 : : operator_bitwise_or op_bitwise_or;
73 : : operator_min op_min;
74 : : operator_max op_max;
75 : :
76 : : // Instantaite a range operator table.
77 : : range_op_table operator_table;
78 : :
79 : : // Invoke the initialization routines for each class of range.
80 : :
81 : 285621 : range_op_table::range_op_table ()
82 : : {
83 : 285621 : initialize_integral_ops ();
84 : 285621 : initialize_pointer_ops ();
85 : 285621 : initialize_float_ops ();
86 : :
87 : 285621 : set (EQ_EXPR, op_equal);
88 : 285621 : set (NE_EXPR, op_not_equal);
89 : 285621 : set (LT_EXPR, op_lt);
90 : 285621 : set (LE_EXPR, op_le);
91 : 285621 : set (GT_EXPR, op_gt);
92 : 285621 : set (GE_EXPR, op_ge);
93 : 285621 : set (SSA_NAME, op_ident);
94 : 285621 : set (PAREN_EXPR, op_ident);
95 : 285621 : set (OBJ_TYPE_REF, op_ident);
96 : 285621 : set (REAL_CST, op_cst);
97 : 285621 : set (INTEGER_CST, op_cst);
98 : 285621 : set (NOP_EXPR, op_cast);
99 : 285621 : set (CONVERT_EXPR, op_cast);
100 : 285621 : set (FLOAT_EXPR, op_cast);
101 : 285621 : set (FIX_TRUNC_EXPR, op_cast);
102 : 285621 : set (PLUS_EXPR, op_plus);
103 : 285621 : set (ABS_EXPR, op_abs);
104 : 285621 : set (MINUS_EXPR, op_minus);
105 : 285621 : set (NEGATE_EXPR, op_negate);
106 : 285621 : set (MULT_EXPR, op_mult);
107 : 285621 : set (ADDR_EXPR, op_addr);
108 : 285621 : set (BIT_NOT_EXPR, op_bitwise_not);
109 : 285621 : set (BIT_XOR_EXPR, op_bitwise_xor);
110 : 285621 : set (BIT_AND_EXPR, op_bitwise_and);
111 : 285621 : set (BIT_IOR_EXPR, op_bitwise_or);
112 : 285621 : set (MIN_EXPR, op_min);
113 : 285621 : set (MAX_EXPR, op_max);
114 : 285621 : }
115 : :
116 : : // Instantiate a default range operator for opcodes with no entry.
117 : :
118 : : range_operator default_operator;
119 : :
120 : : // Create a default range_op_handler.
121 : :
122 : 835456711 : range_op_handler::range_op_handler ()
123 : : {
124 : 835456711 : m_operator = &default_operator;
125 : 835456711 : }
126 : :
127 : : // Create a range_op_handler for CODE. Use a default operatoer if CODE
128 : : // does not have an entry.
129 : :
130 : 1851994055 : range_op_handler::range_op_handler (unsigned code)
131 : : {
132 : 1851994055 : m_operator = operator_table[code];
133 : 1851994055 : if (!m_operator)
134 : 446229672 : m_operator = &default_operator;
135 : 1851994055 : }
136 : :
137 : : // Return TRUE if this handler has a non-default operator.
138 : :
139 : 2817522862 : range_op_handler::operator bool () const
140 : : {
141 : 2817522862 : return m_operator != &default_operator;
142 : : }
143 : :
144 : : // Return a pointer to the range operator assocaited with this handler.
145 : : // If it is a default operator, return NULL.
146 : : // This is the equivalent of indexing the range table.
147 : :
148 : : range_operator *
149 : 494842730 : range_op_handler::range_op () const
150 : : {
151 : 494842730 : if (m_operator != &default_operator)
152 : 494842730 : return m_operator;
153 : : return NULL;
154 : : }
155 : :
156 : : // Create a dispatch pattern for value range discriminators LHS, OP1, and OP2.
157 : : // This is used to produce a unique value for each dispatch pattern. Shift
158 : : // values are based on the size of the m_discriminator field in value_range.h.
159 : :
160 : : constexpr unsigned
161 : 598658649 : dispatch_trio (unsigned lhs, unsigned op1, unsigned op2)
162 : : {
163 : 598658649 : return ((lhs << 8) + (op1 << 4) + (op2));
164 : : }
165 : :
166 : : // These are the supported dispatch patterns. These map to the parameter list
167 : : // of the routines in range_operator. Note the last 3 characters are
168 : : // shorthand for the LHS, OP1, and OP2 range discriminator class.
169 : : // Reminder, single operand instructions use the LHS type for op2, even if
170 : : // unused. So FLOAT = INT would be RO_FIF.
171 : :
172 : : const unsigned RO_III = dispatch_trio (VR_IRANGE, VR_IRANGE, VR_IRANGE);
173 : : const unsigned RO_IFI = dispatch_trio (VR_IRANGE, VR_FRANGE, VR_IRANGE);
174 : : const unsigned RO_IFF = dispatch_trio (VR_IRANGE, VR_FRANGE, VR_FRANGE);
175 : : const unsigned RO_FFF = dispatch_trio (VR_FRANGE, VR_FRANGE, VR_FRANGE);
176 : : const unsigned RO_FIF = dispatch_trio (VR_FRANGE, VR_IRANGE, VR_FRANGE);
177 : : const unsigned RO_FII = dispatch_trio (VR_FRANGE, VR_IRANGE, VR_IRANGE);
178 : : const unsigned RO_PPP = dispatch_trio (VR_PRANGE, VR_PRANGE, VR_PRANGE);
179 : : const unsigned RO_PPI = dispatch_trio (VR_PRANGE, VR_PRANGE, VR_IRANGE);
180 : : const unsigned RO_IPP = dispatch_trio (VR_IRANGE, VR_PRANGE, VR_PRANGE);
181 : : const unsigned RO_IPI = dispatch_trio (VR_IRANGE, VR_PRANGE, VR_IRANGE);
182 : : const unsigned RO_PIP = dispatch_trio (VR_PRANGE, VR_IRANGE, VR_PRANGE);
183 : : const unsigned RO_PII = dispatch_trio (VR_PRANGE, VR_IRANGE, VR_IRANGE);
184 : :
185 : : // Return a dispatch value for parameter types LHS, OP1 and OP2.
186 : :
187 : : unsigned
188 : 598658649 : range_op_handler::dispatch_kind (const vrange &lhs, const vrange &op1,
189 : : const vrange& op2) const
190 : : {
191 : 598658649 : return dispatch_trio (lhs.m_discriminator, op1.m_discriminator,
192 : 598658649 : op2.m_discriminator);
193 : : }
194 : :
195 : : void
196 : 0 : range_op_handler::discriminator_fail (const vrange &r1,
197 : : const vrange &r2,
198 : : const vrange &r3) const
199 : : {
200 : 0 : const char name[] = "IPF";
201 : 0 : gcc_checking_assert (r1.m_discriminator < sizeof (name) - 1);
202 : 0 : gcc_checking_assert (r2.m_discriminator < sizeof (name) - 1);
203 : 0 : gcc_checking_assert (r3.m_discriminator < sizeof (name) - 1);
204 : 0 : fprintf (stderr,
205 : : "Unsupported operand combination in dispatch: RO_%c%c%c\n",
206 : 0 : name[r1.m_discriminator],
207 : 0 : name[r2.m_discriminator],
208 : 0 : name[r3.m_discriminator]);
209 : 0 : gcc_unreachable ();
210 : : }
211 : :
212 : : static inline bool
213 : : has_pointer_operand_p (const vrange &r1, const vrange &r2, const vrange &r3)
214 : : {
215 : : return is_a <prange> (r1) || is_a <prange> (r2) || is_a <prange> (r3);
216 : : }
217 : :
218 : : // Dispatch a call to fold_range based on the types of R, LH and RH.
219 : :
220 : : bool
221 : 267889432 : range_op_handler::fold_range (vrange &r, tree type,
222 : : const vrange &lh,
223 : : const vrange &rh,
224 : : relation_trio rel) const
225 : : {
226 : 267889432 : gcc_checking_assert (m_operator);
227 : : #if CHECKING_P
228 : 267889432 : if (!lh.undefined_p () && !rh.undefined_p ())
229 : 262702798 : gcc_assert (m_operator->operand_check_p (type, lh.type (), rh.type ()));
230 : : #endif
231 : 267889432 : switch (dispatch_kind (r, lh, rh))
232 : : {
233 : 202231071 : case RO_III:
234 : 202231071 : return m_operator->fold_range (as_a <irange> (r), type,
235 : : as_a <irange> (lh),
236 : 202231071 : as_a <irange> (rh), rel);
237 : 259202 : case RO_IFI:
238 : 259202 : return m_operator->fold_range (as_a <irange> (r), type,
239 : : as_a <frange> (lh),
240 : 259202 : as_a <irange> (rh), rel);
241 : 2571924 : case RO_IFF:
242 : 2571924 : return m_operator->fold_range (as_a <irange> (r), type,
243 : : as_a <frange> (lh),
244 : 2571924 : as_a <frange> (rh), rel);
245 : 7475469 : case RO_FFF:
246 : 7475469 : return m_operator->fold_range (as_a <frange> (r), type,
247 : : as_a <frange> (lh),
248 : 7475469 : as_a <frange> (rh), rel);
249 : 0 : case RO_FII:
250 : 0 : return m_operator->fold_range (as_a <frange> (r), type,
251 : : as_a <irange> (lh),
252 : 0 : as_a <irange> (rh), rel);
253 : 814954 : case RO_FIF:
254 : 814954 : return m_operator->fold_range (as_a <frange> (r), type,
255 : : as_a <irange> (lh),
256 : 814954 : as_a <frange> (rh), rel);
257 : 16972738 : case RO_PPP:
258 : 16972738 : return m_operator->fold_range (as_a <prange> (r), type,
259 : : as_a <prange> (lh),
260 : 16972738 : as_a <prange> (rh), rel);
261 : 9166081 : case RO_PPI:
262 : 9166081 : return m_operator->fold_range (as_a <prange> (r), type,
263 : : as_a <prange> (lh),
264 : 9166081 : as_a <irange> (rh), rel);
265 : 17363827 : case RO_IPP:
266 : 17363827 : return m_operator->fold_range (as_a <irange> (r), type,
267 : : as_a <prange> (lh),
268 : 17363827 : as_a <prange> (rh), rel);
269 : 1782628 : case RO_PIP:
270 : 1782628 : return m_operator->fold_range (as_a <prange> (r), type,
271 : : as_a <irange> (lh),
272 : 1782628 : as_a <prange> (rh), rel);
273 : 9251536 : case RO_IPI:
274 : 9251536 : return m_operator->fold_range (as_a <irange> (r), type,
275 : : as_a <prange> (lh),
276 : 9251536 : as_a <irange> (rh), rel);
277 : : default:
278 : : return false;
279 : : }
280 : : }
281 : :
282 : : // Dispatch a call to op1_range based on the types of R, LHS and OP2.
283 : :
284 : : bool
285 : 82952942 : range_op_handler::op1_range (vrange &r, tree type,
286 : : const vrange &lhs,
287 : : const vrange &op2,
288 : : relation_trio rel) const
289 : : {
290 : 82952942 : gcc_checking_assert (m_operator);
291 : 82952942 : if (lhs.undefined_p ())
292 : : return false;
293 : : #if CHECKING_P
294 : 82952917 : if (!op2.undefined_p ())
295 : 82952811 : gcc_assert (m_operator->operand_check_p (lhs.type (), type, op2.type ()));
296 : : #endif
297 : 82952917 : switch (dispatch_kind (r, lhs, op2))
298 : : {
299 : 71331415 : case RO_III:
300 : 71331415 : return m_operator->op1_range (as_a <irange> (r), type,
301 : : as_a <irange> (lhs),
302 : 71331415 : as_a <irange> (op2), rel);
303 : 231670 : case RO_IFI:
304 : 231670 : return m_operator->op1_range (as_a <irange> (r), type,
305 : : as_a <frange> (lhs),
306 : 231670 : as_a <irange> (op2), rel);
307 : 651555 : case RO_PPP:
308 : 651555 : return m_operator->op1_range (as_a <prange> (r), type,
309 : : as_a <prange> (lhs),
310 : 651555 : as_a <prange> (op2), rel);
311 : 7809012 : case RO_PIP:
312 : 7809012 : return m_operator->op1_range (as_a <prange> (r), type,
313 : : as_a <irange> (lhs),
314 : 7809012 : as_a <prange> (op2), rel);
315 : 429927 : case RO_PPI:
316 : 429927 : return m_operator->op1_range (as_a <prange> (r), type,
317 : : as_a <prange> (lhs),
318 : 429927 : as_a <irange> (op2), rel);
319 : 243611 : case RO_IPI:
320 : 243611 : return m_operator->op1_range (as_a <irange> (r), type,
321 : : as_a <prange> (lhs),
322 : 243611 : as_a <irange> (op2), rel);
323 : 1385767 : case RO_FIF:
324 : 1385767 : return m_operator->op1_range (as_a <frange> (r), type,
325 : : as_a <irange> (lhs),
326 : 1385767 : as_a <frange> (op2), rel);
327 : 869960 : case RO_FFF:
328 : 869960 : return m_operator->op1_range (as_a <frange> (r), type,
329 : : as_a <frange> (lhs),
330 : 869960 : as_a <frange> (op2), rel);
331 : : default:
332 : : return false;
333 : : }
334 : : }
335 : :
336 : : // Dispatch a call to op2_range based on the types of R, LHS and OP1.
337 : :
338 : : bool
339 : 23620885 : range_op_handler::op2_range (vrange &r, tree type,
340 : : const vrange &lhs,
341 : : const vrange &op1,
342 : : relation_trio rel) const
343 : : {
344 : 23620885 : gcc_checking_assert (m_operator);
345 : 23620885 : if (lhs.undefined_p ())
346 : : return false;
347 : : #if CHECKING_P
348 : 23620864 : if (!op1.undefined_p ())
349 : 23620737 : gcc_assert (m_operator->operand_check_p (lhs.type (), op1.type (), type));
350 : : #endif
351 : 23620864 : switch (dispatch_kind (r, lhs, op1))
352 : : {
353 : 18102088 : case RO_III:
354 : 18102088 : return m_operator->op2_range (as_a <irange> (r), type,
355 : : as_a <irange> (lhs),
356 : 18102088 : as_a <irange> (op1), rel);
357 : 4441954 : case RO_PIP:
358 : 4441954 : return m_operator->op2_range (as_a <prange> (r), type,
359 : : as_a <irange> (lhs),
360 : 4441954 : as_a <prange> (op1), rel);
361 : 178505 : case RO_IPP:
362 : 178505 : return m_operator->op2_range (as_a <irange> (r), type,
363 : : as_a <prange> (lhs),
364 : 178505 : as_a <prange> (op1), rel);
365 : 532371 : case RO_FIF:
366 : 532371 : return m_operator->op2_range (as_a <frange> (r), type,
367 : : as_a <irange> (lhs),
368 : 532371 : as_a <frange> (op1), rel);
369 : 365820 : case RO_FFF:
370 : 365820 : return m_operator->op2_range (as_a <frange> (r), type,
371 : : as_a <frange> (lhs),
372 : 365820 : as_a <frange> (op1), rel);
373 : : default:
374 : : return false;
375 : : }
376 : : }
377 : :
378 : : // Dispatch a call to lhs_op1_relation based on the types of LHS, OP1 and OP2.
379 : :
380 : : relation_kind
381 : 114650446 : range_op_handler::lhs_op1_relation (const vrange &lhs,
382 : : const vrange &op1,
383 : : const vrange &op2,
384 : : relation_kind rel) const
385 : : {
386 : 114650446 : gcc_checking_assert (m_operator);
387 : 114650446 : switch (dispatch_kind (lhs, op1, op2))
388 : : {
389 : 90932410 : case RO_III:
390 : 90932410 : return m_operator->lhs_op1_relation (as_a <irange> (lhs),
391 : : as_a <irange> (op1),
392 : 90932410 : as_a <irange> (op2), rel);
393 : 1359112 : case RO_PPP:
394 : 1359112 : return m_operator->lhs_op1_relation (as_a <prange> (lhs),
395 : : as_a <prange> (op1),
396 : 1359112 : as_a <prange> (op2), rel);
397 : 5614683 : case RO_IPP:
398 : 5614683 : return m_operator->lhs_op1_relation (as_a <irange> (lhs),
399 : : as_a <prange> (op1),
400 : 5614683 : as_a <prange> (op2), rel);
401 : 1360592 : case RO_PII:
402 : 1360592 : return m_operator->lhs_op1_relation (as_a <prange> (lhs),
403 : : as_a <irange> (op1),
404 : 1360592 : as_a <irange> (op2), rel);
405 : 7923223 : case RO_PPI:
406 : 7923223 : return m_operator->lhs_op1_relation (as_a <prange> (lhs),
407 : : as_a <prange> (op1),
408 : 7923223 : as_a <irange> (op2), rel);
409 : 926853 : case RO_IFF:
410 : 926853 : return m_operator->lhs_op1_relation (as_a <irange> (lhs),
411 : : as_a <frange> (op1),
412 : 926853 : as_a <frange> (op2), rel);
413 : 5719160 : case RO_FFF:
414 : 5719160 : return m_operator->lhs_op1_relation (as_a <frange> (lhs),
415 : : as_a <frange> (op1),
416 : 5719160 : as_a <frange> (op2), rel);
417 : : default:
418 : : return VREL_VARYING;
419 : : }
420 : : }
421 : :
422 : : // Dispatch a call to lhs_op2_relation based on the types of LHS, OP1 and OP2.
423 : :
424 : : relation_kind
425 : 34087727 : range_op_handler::lhs_op2_relation (const vrange &lhs,
426 : : const vrange &op1,
427 : : const vrange &op2,
428 : : relation_kind rel) const
429 : : {
430 : 34087727 : gcc_checking_assert (m_operator);
431 : 34087727 : switch (dispatch_kind (lhs, op1, op2))
432 : : {
433 : 22812637 : case RO_III:
434 : 22812637 : return m_operator->lhs_op2_relation (as_a <irange> (lhs),
435 : : as_a <irange> (op1),
436 : 22812637 : as_a <irange> (op2), rel);
437 : 157263 : case RO_IFF:
438 : 157263 : return m_operator->lhs_op2_relation (as_a <irange> (lhs),
439 : : as_a <frange> (op1),
440 : 157263 : as_a <frange> (op2), rel);
441 : 3602410 : case RO_FFF:
442 : 3602410 : return m_operator->lhs_op2_relation (as_a <frange> (lhs),
443 : : as_a <frange> (op1),
444 : 3602410 : as_a <frange> (op2), rel);
445 : : default:
446 : : return VREL_VARYING;
447 : : }
448 : : }
449 : :
450 : : // Dispatch a call to op1_op2_relation based on the type of LHS.
451 : :
452 : : relation_kind
453 : 75411899 : range_op_handler::op1_op2_relation (const vrange &lhs,
454 : : const vrange &op1,
455 : : const vrange &op2) const
456 : : {
457 : 75411899 : gcc_checking_assert (m_operator);
458 : :
459 : 75411899 : switch (dispatch_kind (lhs, op1, op2))
460 : : {
461 : 58688613 : case RO_III:
462 : 58688613 : return m_operator->op1_op2_relation (as_a <irange> (lhs),
463 : : as_a <irange> (op1),
464 : 58688613 : as_a <irange> (op2));
465 : :
466 : 14072424 : case RO_IPP:
467 : 14072424 : return m_operator->op1_op2_relation (as_a <irange> (lhs),
468 : : as_a <prange> (op1),
469 : 14072424 : as_a <prange> (op2));
470 : :
471 : 1734488 : case RO_IFF:
472 : 1734488 : return m_operator->op1_op2_relation (as_a <irange> (lhs),
473 : : as_a <frange> (op1),
474 : 1734488 : as_a <frange> (op2));
475 : :
476 : 640747 : case RO_FFF:
477 : 640747 : return m_operator->op1_op2_relation (as_a <frange> (lhs),
478 : : as_a <frange> (op1),
479 : 640747 : as_a <frange> (op2));
480 : :
481 : : default:
482 : : return VREL_VARYING;
483 : : }
484 : : }
485 : :
486 : : bool
487 : 45364 : range_op_handler::overflow_free_p (const vrange &lh,
488 : : const vrange &rh,
489 : : relation_trio rel) const
490 : : {
491 : 45364 : gcc_checking_assert (m_operator);
492 : 45364 : switch (dispatch_kind (lh, lh, rh))
493 : : {
494 : 45364 : case RO_III:
495 : 45364 : return m_operator->overflow_free_p(as_a <irange> (lh),
496 : : as_a <irange> (rh),
497 : 45364 : rel);
498 : : default:
499 : : return false;
500 : : }
501 : : }
502 : :
503 : : bool
504 : 8611070 : range_op_handler::operand_check_p (tree t1, tree t2, tree t3) const
505 : : {
506 : 8611070 : gcc_checking_assert (m_operator);
507 : 8611070 : return m_operator->operand_check_p (t1, t2, t3);
508 : : }
509 : :
510 : : // Update the known bitmasks in R when applying the operation CODE to
511 : : // LH and RH.
512 : :
513 : : void
514 : 153823207 : update_known_bitmask (vrange &r, tree_code code,
515 : : const vrange &lh, const vrange &rh)
516 : : {
517 : 153823207 : if (r.undefined_p () || lh.undefined_p () || rh.undefined_p ()
518 : 307636718 : || r.singleton_p ())
519 : 8883870 : return;
520 : :
521 : 144939337 : widest_int widest_value, widest_mask;
522 : 144939337 : tree type = r.type ();
523 : 144939337 : signop sign = TYPE_SIGN (type);
524 : 144939337 : int prec = TYPE_PRECISION (type);
525 : 144939337 : irange_bitmask lh_bits = lh.get_bitmask ();
526 : 144939337 : irange_bitmask rh_bits = rh.get_bitmask ();
527 : :
528 : 144939337 : switch (get_gimple_rhs_class (code))
529 : : {
530 : 48299782 : case GIMPLE_UNARY_RHS:
531 : 48299782 : bit_value_unop (code, sign, prec, &widest_value, &widest_mask,
532 : 48299782 : TYPE_SIGN (lh.type ()),
533 : 48299782 : TYPE_PRECISION (lh.type ()),
534 : 96600002 : widest_int::from (lh_bits.value (),
535 : 48299782 : TYPE_SIGN (lh.type ())),
536 : 96599564 : widest_int::from (lh_bits.mask (),
537 : 48299782 : TYPE_SIGN (lh.type ())));
538 : 48299782 : break;
539 : 96639555 : case GIMPLE_BINARY_RHS:
540 : 193279110 : bit_value_binop (code, sign, prec, &widest_value, &widest_mask,
541 : 96639555 : TYPE_SIGN (lh.type ()),
542 : 96639555 : TYPE_PRECISION (lh.type ()),
543 : 193279940 : widest_int::from (lh_bits.value (), sign),
544 : 193279940 : widest_int::from (lh_bits.mask (), sign),
545 : 96639555 : TYPE_SIGN (rh.type ()),
546 : 96639555 : TYPE_PRECISION (rh.type ()),
547 : 193279913 : widest_int::from (rh_bits.value (), sign),
548 : 193279110 : widest_int::from (rh_bits.mask (), sign));
549 : 96639555 : break;
550 : 0 : default:
551 : 0 : gcc_unreachable ();
552 : : }
553 : :
554 : 144939337 : wide_int mask = wide_int::from (widest_mask, prec, sign);
555 : 289878674 : wide_int value = wide_int::from (widest_value, prec, sign);
556 : : // Bitmasks must have the unknown value bits cleared.
557 : 144939337 : value &= ~mask;
558 : 289878674 : irange_bitmask bm (value, mask);
559 : 144939337 : r.update_bitmask (bm);
560 : 144940258 : }
561 : :
562 : : // Return the upper limit for a type.
563 : :
564 : : static inline wide_int
565 : 14483481 : max_limit (const_tree type)
566 : : {
567 : 14483481 : return irange_val_max (type);
568 : : }
569 : :
570 : : // Return the lower limit for a type.
571 : :
572 : : static inline wide_int
573 : 17503935 : min_limit (const_tree type)
574 : : {
575 : 17503935 : return irange_val_min (type);
576 : : }
577 : :
578 : : // Return false if shifting by OP is undefined behavior. Otherwise, return
579 : : // true and the range it is to be shifted by. This allows trimming out of
580 : : // undefined ranges, leaving only valid ranges if there are any.
581 : :
582 : : static inline bool
583 : 4514136 : get_shift_range (irange &r, tree type, const irange &op)
584 : : {
585 : 4514136 : if (op.undefined_p ())
586 : : return false;
587 : :
588 : : // Build valid range and intersect it with the shift range.
589 : 4513722 : r.set (op.type (),
590 : 9027444 : wi::shwi (0, TYPE_PRECISION (op.type ())),
591 : 4513722 : wi::shwi (TYPE_PRECISION (type) - 1, TYPE_PRECISION (op.type ())));
592 : 4513722 : r.intersect (op);
593 : :
594 : : // If there are no valid ranges in the shift range, returned false.
595 : 4513722 : if (r.undefined_p ())
596 : : return false;
597 : : return true;
598 : : }
599 : :
600 : : // Default wide_int fold operation returns [MIN, MAX].
601 : :
602 : : void
603 : 0 : range_operator::wi_fold (irange &r, tree type,
604 : : const wide_int &lh_lb ATTRIBUTE_UNUSED,
605 : : const wide_int &lh_ub ATTRIBUTE_UNUSED,
606 : : const wide_int &rh_lb ATTRIBUTE_UNUSED,
607 : : const wide_int &rh_ub ATTRIBUTE_UNUSED) const
608 : : {
609 : 0 : gcc_checking_assert (r.supports_type_p (type));
610 : 0 : r.set_varying (type);
611 : 0 : }
612 : :
613 : : // Call wi_fold when both op1 and op2 are equivalent. Further split small
614 : : // subranges into constants. This can provide better precision.
615 : : // For x + y, when x == y with a range of [0,4] instead of [0, 8] produce
616 : : // [0,0][2, 2][4,4][6, 6][8, 8]
617 : : // LIMIT is the maximum number of elements in range allowed before we
618 : : // do not process them individually.
619 : :
620 : : void
621 : 54695 : range_operator::wi_fold_in_parts_equiv (irange &r, tree type,
622 : : const wide_int &lh_lb,
623 : : const wide_int &lh_ub,
624 : : unsigned limit) const
625 : : {
626 : 54695 : int_range_max tmp;
627 : 109390 : widest_int lh_range = wi::sub (widest_int::from (lh_ub, TYPE_SIGN (type)),
628 : 109390 : widest_int::from (lh_lb, TYPE_SIGN (type)));
629 : : // if there are 1 to 8 values in the LH range, split them up.
630 : 54695 : r.set_undefined ();
631 : 109390 : if (lh_range >= 0 && lh_range < limit)
632 : : {
633 : 17155 : for (unsigned x = 0; x <= lh_range; x++)
634 : : {
635 : 11530 : wide_int val = lh_lb + x;
636 : 11530 : wi_fold (tmp, type, val, val, val, val);
637 : 11530 : r.union_ (tmp);
638 : 11530 : }
639 : : }
640 : : // Otherwise just call wi_fold.
641 : : else
642 : 49070 : wi_fold (r, type, lh_lb, lh_ub, lh_lb, lh_ub);
643 : 54695 : }
644 : :
645 : : // Call wi_fold, except further split small subranges into constants.
646 : : // This can provide better precision. For something 8 >> [0,1]
647 : : // Instead of [8, 16], we will produce [8,8][16,16]
648 : :
649 : : void
650 : 124969208 : range_operator::wi_fold_in_parts (irange &r, tree type,
651 : : const wide_int &lh_lb,
652 : : const wide_int &lh_ub,
653 : : const wide_int &rh_lb,
654 : : const wide_int &rh_ub) const
655 : : {
656 : 124969208 : int_range_max tmp;
657 : 249938416 : widest_int rh_range = wi::sub (widest_int::from (rh_ub, TYPE_SIGN (type)),
658 : 249938416 : widest_int::from (rh_lb, TYPE_SIGN (type)));
659 : 249938416 : widest_int lh_range = wi::sub (widest_int::from (lh_ub, TYPE_SIGN (type)),
660 : 249938416 : widest_int::from (lh_lb, TYPE_SIGN (type)));
661 : : // If there are 2, 3, or 4 values in the RH range, do them separately.
662 : : // Call wi_fold_in_parts to check the RH side.
663 : 124969208 : if (rh_range > 0 && rh_range < 4)
664 : : {
665 : 4712677 : wi_fold_in_parts (r, type, lh_lb, lh_ub, rh_lb, rh_lb);
666 : 4712677 : if (rh_range > 1)
667 : : {
668 : 491593 : wi_fold_in_parts (tmp, type, lh_lb, lh_ub, rh_lb + 1, rh_lb + 1);
669 : 491593 : r.union_ (tmp);
670 : 491593 : if (rh_range == 3)
671 : : {
672 : 307059 : wi_fold_in_parts (tmp, type, lh_lb, lh_ub, rh_lb + 2, rh_lb + 2);
673 : 307059 : r.union_ (tmp);
674 : : }
675 : : }
676 : 4712677 : wi_fold_in_parts (tmp, type, lh_lb, lh_ub, rh_ub, rh_ub);
677 : 4712677 : r.union_ (tmp);
678 : : }
679 : : // Otherwise check for 2, 3, or 4 values in the LH range and split them up.
680 : : // The RH side has been checked, so no recursion needed.
681 : 120256531 : else if (lh_range > 0 && lh_range < 4)
682 : : {
683 : 9692792 : wi_fold (r, type, lh_lb, lh_lb, rh_lb, rh_ub);
684 : 9692792 : if (lh_range > 1)
685 : : {
686 : 1799777 : wi_fold (tmp, type, lh_lb + 1, lh_lb + 1, rh_lb, rh_ub);
687 : 1799769 : r.union_ (tmp);
688 : 1799769 : if (lh_range == 3)
689 : : {
690 : 774826 : wi_fold (tmp, type, lh_lb + 2, lh_lb + 2, rh_lb, rh_ub);
691 : 774822 : r.union_ (tmp);
692 : : }
693 : : }
694 : 9692792 : wi_fold (tmp, type, lh_ub, lh_ub, rh_lb, rh_ub);
695 : 9692792 : r.union_ (tmp);
696 : : }
697 : : // Otherwise just call wi_fold.
698 : : else
699 : 110563739 : wi_fold (r, type, lh_lb, lh_ub, rh_lb, rh_ub);
700 : 124969510 : }
701 : :
702 : : // The default for fold is to break all ranges into sub-ranges and
703 : : // invoke the wi_fold method on each sub-range pair.
704 : :
705 : : bool
706 : 90142735 : range_operator::fold_range (irange &r, tree type,
707 : : const irange &lh,
708 : : const irange &rh,
709 : : relation_trio trio) const
710 : : {
711 : 90142735 : gcc_checking_assert (r.supports_type_p (type));
712 : 90142735 : if (empty_range_varying (r, type, lh, rh))
713 : 43650 : return true;
714 : :
715 : 90099085 : relation_kind rel = trio.op1_op2 ();
716 : 90099085 : unsigned num_lh = lh.num_pairs ();
717 : 90099085 : unsigned num_rh = rh.num_pairs ();
718 : :
719 : : // If op1 and op2 are equivalences, then we don't need a complete cross
720 : : // product, just pairs of matching elements.
721 : 90099460 : if (relation_equiv_p (rel) && lh == rh)
722 : : {
723 : 50941 : int_range_max tmp;
724 : 50941 : r.set_undefined ();
725 : 90713 : for (unsigned x = 0; x < num_lh; ++x)
726 : : {
727 : : // If the number of subranges is too high, limit subrange creation.
728 : 54695 : unsigned limit = (r.num_pairs () > 32) ? 0 : 8;
729 : 54695 : wide_int lh_lb = lh.lower_bound (x);
730 : 54695 : wide_int lh_ub = lh.upper_bound (x);
731 : 54695 : wi_fold_in_parts_equiv (tmp, type, lh_lb, lh_ub, limit);
732 : 54695 : r.union_ (tmp);
733 : 54695 : if (r.varying_p ())
734 : : break;
735 : 54695 : }
736 : 50941 : op1_op2_relation_effect (r, type, lh, rh, rel);
737 : 50941 : update_bitmask (r, lh, rh);
738 : 50941 : return true;
739 : 50941 : }
740 : :
741 : : // If both ranges are single pairs, fold directly into the result range.
742 : : // If the number of subranges grows too high, produce a summary result as the
743 : : // loop becomes exponential with little benefit. See PR 103821.
744 : 90048144 : if ((num_lh == 1 && num_rh == 1) || num_lh * num_rh > 12)
745 : : {
746 : 75070830 : wi_fold_in_parts (r, type, lh.lower_bound (), lh.upper_bound (),
747 : 150139600 : rh.lower_bound (), rh.upper_bound ());
748 : 75069800 : op1_op2_relation_effect (r, type, lh, rh, rel);
749 : 75069800 : update_bitmask (r, lh, rh);
750 : 75069800 : return true;
751 : : }
752 : :
753 : 14978344 : int_range_max tmp;
754 : 14978344 : r.set_undefined ();
755 : 45096877 : for (unsigned x = 0; x < num_lh; ++x)
756 : 69793935 : for (unsigned y = 0; y < num_rh; ++y)
757 : : {
758 : 39675402 : wide_int lh_lb = lh.lower_bound (x);
759 : 39675402 : wide_int lh_ub = lh.upper_bound (x);
760 : 39675402 : wide_int rh_lb = rh.lower_bound (y);
761 : 39675402 : wide_int rh_ub = rh.upper_bound (y);
762 : 39675402 : wi_fold_in_parts (tmp, type, lh_lb, lh_ub, rh_lb, rh_ub);
763 : 39675402 : r.union_ (tmp);
764 : 39675402 : if (r.varying_p ())
765 : : {
766 : 3650190 : op1_op2_relation_effect (r, type, lh, rh, rel);
767 : 3650190 : update_bitmask (r, lh, rh);
768 : 3650190 : return true;
769 : : }
770 : 39676479 : }
771 : 11328154 : op1_op2_relation_effect (r, type, lh, rh, rel);
772 : 11328154 : update_bitmask (r, lh, rh);
773 : 11328154 : return true;
774 : 14978344 : }
775 : :
776 : :
777 : : bool
778 : 0 : range_operator::fold_range (frange &, tree, const irange &,
779 : : const frange &, relation_trio) const
780 : : {
781 : 0 : return false;
782 : : }
783 : :
784 : : bool
785 : 0 : range_operator::op1_range (irange &, tree, const frange &,
786 : : const irange &, relation_trio) const
787 : : {
788 : 0 : return false;
789 : : }
790 : :
791 : :
792 : :
793 : : // The default for op1_range is to return false.
794 : :
795 : : bool
796 : 648430 : range_operator::op1_range (irange &r ATTRIBUTE_UNUSED,
797 : : tree type ATTRIBUTE_UNUSED,
798 : : const irange &lhs ATTRIBUTE_UNUSED,
799 : : const irange &op2 ATTRIBUTE_UNUSED,
800 : : relation_trio) const
801 : : {
802 : 648430 : return false;
803 : : }
804 : :
805 : : // The default for op2_range is to return false.
806 : :
807 : : bool
808 : 531330 : range_operator::op2_range (irange &r ATTRIBUTE_UNUSED,
809 : : tree type ATTRIBUTE_UNUSED,
810 : : const irange &lhs ATTRIBUTE_UNUSED,
811 : : const irange &op1 ATTRIBUTE_UNUSED,
812 : : relation_trio) const
813 : : {
814 : 531330 : return false;
815 : : }
816 : :
817 : : // The default relation routines return VREL_VARYING.
818 : :
819 : : relation_kind
820 : 21214209 : range_operator::lhs_op1_relation (const irange &lhs ATTRIBUTE_UNUSED,
821 : : const irange &op1 ATTRIBUTE_UNUSED,
822 : : const irange &op2 ATTRIBUTE_UNUSED,
823 : : relation_kind rel ATTRIBUTE_UNUSED) const
824 : : {
825 : 21214209 : return VREL_VARYING;
826 : : }
827 : :
828 : : relation_kind
829 : 15821655 : range_operator::lhs_op2_relation (const irange &lhs ATTRIBUTE_UNUSED,
830 : : const irange &op1 ATTRIBUTE_UNUSED,
831 : : const irange &op2 ATTRIBUTE_UNUSED,
832 : : relation_kind rel ATTRIBUTE_UNUSED) const
833 : : {
834 : 15821655 : return VREL_VARYING;
835 : : }
836 : :
837 : : relation_kind
838 : 13108897 : range_operator::op1_op2_relation (const irange &lhs ATTRIBUTE_UNUSED,
839 : : const irange &op1 ATTRIBUTE_UNUSED,
840 : : const irange &op2 ATTRIBUTE_UNUSED) const
841 : : {
842 : 13108897 : return VREL_VARYING;
843 : : }
844 : :
845 : : // Default is no relation affects the LHS.
846 : :
847 : : bool
848 : 74660934 : range_operator::op1_op2_relation_effect (irange &lhs_range ATTRIBUTE_UNUSED,
849 : : tree type ATTRIBUTE_UNUSED,
850 : : const irange &op1_range
851 : : ATTRIBUTE_UNUSED,
852 : : const irange &op2_range
853 : : ATTRIBUTE_UNUSED,
854 : : relation_kind rel
855 : : ATTRIBUTE_UNUSED) const
856 : : {
857 : 74660934 : return false;
858 : : }
859 : :
860 : : bool
861 : 0 : range_operator::overflow_free_p (const irange &, const irange &,
862 : : relation_trio) const
863 : : {
864 : 0 : return false;
865 : : }
866 : :
867 : : // Apply any known bitmask updates based on this operator.
868 : :
869 : : void
870 : 4276 : range_operator::update_bitmask (irange &, const irange &,
871 : : const irange &) const
872 : : {
873 : 4276 : }
874 : :
875 : : // Check that operand types are OK. Default to always OK.
876 : :
877 : : bool
878 : 111689899 : range_operator::operand_check_p (tree, tree, tree) const
879 : : {
880 : 111689899 : return true;
881 : : }
882 : :
883 : : // Create and return a range from a pair of wide-ints that are known
884 : : // to have overflowed (or underflowed).
885 : :
886 : : static void
887 : 37664700 : value_range_from_overflowed_bounds (irange &r, tree type,
888 : : const wide_int &wmin,
889 : : const wide_int &wmax)
890 : : {
891 : 37664700 : const signop sgn = TYPE_SIGN (type);
892 : 37664700 : const unsigned int prec = TYPE_PRECISION (type);
893 : :
894 : 37664700 : wide_int tmin = wide_int::from (wmin, prec, sgn);
895 : 37664700 : wide_int tmax = wide_int::from (wmax, prec, sgn);
896 : :
897 : 37664700 : bool covers = false;
898 : 37664700 : wide_int tem = tmin;
899 : 37664700 : tmin = tmax + 1;
900 : 37664700 : if (wi::cmp (tmin, tmax, sgn) < 0)
901 : 2182347 : covers = true;
902 : 37664700 : tmax = tem - 1;
903 : 37664700 : if (wi::cmp (tmax, tem, sgn) > 0)
904 : : covers = true;
905 : :
906 : : // If the anti-range would cover nothing, drop to varying.
907 : : // Likewise if the anti-range bounds are outside of the types
908 : : // values.
909 : 35409835 : if (covers || wi::cmp (tmin, tmax, sgn) > 0)
910 : 25602488 : r.set_varying (type);
911 : : else
912 : 12062212 : r.set (type, tmin, tmax, VR_ANTI_RANGE);
913 : 37665280 : }
914 : :
915 : : // Create and return a range from a pair of wide-ints. MIN_OVF and
916 : : // MAX_OVF describe any overflow that might have occurred while
917 : : // calculating WMIN and WMAX respectively.
918 : :
919 : : static void
920 : 121978520 : value_range_with_overflow (irange &r, tree type,
921 : : const wide_int &wmin, const wide_int &wmax,
922 : : wi::overflow_type min_ovf = wi::OVF_NONE,
923 : : wi::overflow_type max_ovf = wi::OVF_NONE)
924 : : {
925 : 121978520 : const signop sgn = TYPE_SIGN (type);
926 : 121978520 : const unsigned int prec = TYPE_PRECISION (type);
927 : 194334096 : const bool overflow_wraps = TYPE_OVERFLOW_WRAPS (type);
928 : :
929 : : // For one bit precision if max != min, then the range covers all
930 : : // values.
931 : 135750555 : if (prec == 1 && wi::ne_p (wmax, wmin))
932 : : {
933 : 0 : r.set_varying (type);
934 : 0 : return;
935 : : }
936 : :
937 : 121978520 : if (overflow_wraps)
938 : : {
939 : : // If overflow wraps, truncate the values and adjust the range,
940 : : // kind, and bounds appropriately.
941 : 72355576 : if ((min_ovf != wi::OVF_NONE) == (max_ovf != wi::OVF_NONE))
942 : : {
943 : 50177159 : wide_int tmin = wide_int::from (wmin, prec, sgn);
944 : 50177159 : wide_int tmax = wide_int::from (wmax, prec, sgn);
945 : : // If the limits are swapped, we wrapped around and cover
946 : : // the entire range.
947 : 50177159 : if (wi::gt_p (tmin, tmax, sgn))
948 : 503799 : r.set_varying (type);
949 : : else
950 : : // No overflow or both overflow or underflow. The range
951 : : // kind stays normal.
952 : 49673360 : r.set (type, tmin, tmax);
953 : 50177159 : return;
954 : 50177283 : }
955 : :
956 : 22178417 : if ((min_ovf == wi::OVF_UNDERFLOW && max_ovf == wi::OVF_NONE)
957 : 15898602 : || (max_ovf == wi::OVF_OVERFLOW && min_ovf == wi::OVF_NONE))
958 : 22178417 : value_range_from_overflowed_bounds (r, type, wmin, wmax);
959 : : else
960 : : // Other underflow and/or overflow, drop to VR_VARYING.
961 : 0 : r.set_varying (type);
962 : : }
963 : : else
964 : : {
965 : : // If both bounds either underflowed or overflowed, then the result
966 : : // is undefined.
967 : 49622944 : if ((min_ovf == wi::OVF_OVERFLOW && max_ovf == wi::OVF_OVERFLOW)
968 : 49615400 : || (min_ovf == wi::OVF_UNDERFLOW && max_ovf == wi::OVF_UNDERFLOW))
969 : : {
970 : 8773 : r.set_undefined ();
971 : 8773 : return;
972 : : }
973 : :
974 : : // If overflow does not wrap, saturate to [MIN, MAX].
975 : 49614171 : wide_int new_lb, new_ub;
976 : 49614171 : if (min_ovf == wi::OVF_UNDERFLOW)
977 : 6205086 : new_lb = wi::min_value (prec, sgn);
978 : 43409270 : else if (min_ovf == wi::OVF_OVERFLOW)
979 : 0 : new_lb = wi::max_value (prec, sgn);
980 : : else
981 : 43409270 : new_lb = wmin;
982 : :
983 : 49614171 : if (max_ovf == wi::OVF_UNDERFLOW)
984 : 0 : new_ub = wi::min_value (prec, sgn);
985 : 49614171 : else if (max_ovf == wi::OVF_OVERFLOW)
986 : 10842131 : new_ub = wi::max_value (prec, sgn);
987 : : else
988 : 38772270 : new_ub = wmax;
989 : :
990 : 49614171 : r.set (type, new_lb, new_ub);
991 : 49614701 : }
992 : : }
993 : :
994 : : // Create and return a range from a pair of wide-ints. Canonicalize
995 : : // the case where the bounds are swapped. In which case, we transform
996 : : // [10,5] into [MIN,5][10,MAX].
997 : :
998 : : static inline void
999 : 74710430 : create_possibly_reversed_range (irange &r, tree type,
1000 : : const wide_int &new_lb, const wide_int &new_ub)
1001 : : {
1002 : 74710430 : signop s = TYPE_SIGN (type);
1003 : : // If the bounds are swapped, treat the result as if an overflow occurred.
1004 : 74710430 : if (wi::gt_p (new_lb, new_ub, s))
1005 : 15486283 : value_range_from_overflowed_bounds (r, type, new_lb, new_ub);
1006 : : else
1007 : : // Otherwise it's just a normal range.
1008 : 59224147 : r.set (type, new_lb, new_ub);
1009 : 74710430 : }
1010 : :
1011 : : // Return the summary information about boolean range LHS. If EMPTY/FULL,
1012 : : // return the equivalent range for TYPE in R; if FALSE/TRUE, do nothing.
1013 : :
1014 : : bool_range_state
1015 : 76921527 : get_bool_state (vrange &r, const vrange &lhs, tree val_type)
1016 : : {
1017 : : // If there is no result, then this is unexecutable.
1018 : 76921527 : if (lhs.undefined_p ())
1019 : : {
1020 : 0 : r.set_undefined ();
1021 : 0 : return BRS_EMPTY;
1022 : : }
1023 : :
1024 : 76921527 : if (lhs.zero_p ())
1025 : : return BRS_FALSE;
1026 : :
1027 : : // For TRUE, we can't just test for [1,1] because Ada can have
1028 : : // multi-bit booleans, and TRUE values can be: [1, MAX], ~[0], etc.
1029 : 38365473 : if (lhs.contains_p (build_zero_cst (lhs.type ())))
1030 : : {
1031 : 167510 : r.set_varying (val_type);
1032 : 167510 : return BRS_FULL;
1033 : : }
1034 : :
1035 : : return BRS_TRUE;
1036 : : }
1037 : :
1038 : : // ------------------------------------------------------------------------
1039 : :
1040 : : void
1041 : 0 : operator_equal::update_bitmask (irange &r, const irange &lh,
1042 : : const irange &rh) const
1043 : : {
1044 : 0 : update_known_bitmask (r, EQ_EXPR, lh, rh);
1045 : 0 : }
1046 : :
1047 : : // Check if the LHS range indicates a relation between OP1 and OP2.
1048 : :
1049 : : relation_kind
1050 : 5690376 : operator_equal::op1_op2_relation (const irange &lhs, const irange &,
1051 : : const irange &) const
1052 : : {
1053 : 5690376 : if (lhs.undefined_p ())
1054 : : return VREL_UNDEFINED;
1055 : :
1056 : : // FALSE = op1 == op2 indicates NE_EXPR.
1057 : 5690376 : if (lhs.zero_p ())
1058 : : return VREL_NE;
1059 : :
1060 : : // TRUE = op1 == op2 indicates EQ_EXPR.
1061 : 2889845 : if (!contains_zero_p (lhs))
1062 : 2858650 : return VREL_EQ;
1063 : : return VREL_VARYING;
1064 : : }
1065 : :
1066 : : bool
1067 : 17386643 : operator_equal::fold_range (irange &r, tree type,
1068 : : const irange &op1,
1069 : : const irange &op2,
1070 : : relation_trio rel) const
1071 : : {
1072 : 17386643 : if (relop_early_resolve (r, type, op1, op2, rel, VREL_EQ))
1073 : : return true;
1074 : :
1075 : : // We can be sure the values are always equal or not if both ranges
1076 : : // consist of a single value, and then compare them.
1077 : 17353991 : bool op1_const = wi::eq_p (op1.lower_bound (), op1.upper_bound ());
1078 : 17353991 : bool op2_const = wi::eq_p (op2.lower_bound (), op2.upper_bound ());
1079 : 17353982 : if (op1_const && op2_const)
1080 : : {
1081 : 284630 : if (wi::eq_p (op1.lower_bound (), op2.upper_bound()))
1082 : 149939 : r = range_true (type);
1083 : : else
1084 : 134691 : r = range_false (type);
1085 : : }
1086 : : else
1087 : : {
1088 : : // If ranges do not intersect, we know the range is not equal,
1089 : : // otherwise we don't know anything for sure.
1090 : 17069352 : int_range_max tmp = op1;
1091 : 17069352 : tmp.intersect (op2);
1092 : 17069352 : if (tmp.undefined_p ())
1093 : 205743 : r = range_false (type);
1094 : : // Check if a constant cannot satisfy the bitmask requirements.
1095 : 31411081 : else if (op2_const && !op1.get_bitmask ().member_p (op2.lower_bound ()))
1096 : 681 : r = range_false (type);
1097 : 16920629 : else if (op1_const && !op2.get_bitmask ().member_p (op1.lower_bound ()))
1098 : 0 : r = range_false (type);
1099 : : else
1100 : 16862928 : r = range_true_and_false (type);
1101 : 17069352 : }
1102 : : return true;
1103 : : }
1104 : :
1105 : : bool
1106 : 10905361 : operator_equal::op1_range (irange &r, tree type,
1107 : : const irange &lhs,
1108 : : const irange &op2,
1109 : : relation_trio) const
1110 : : {
1111 : 10905361 : switch (get_bool_state (r, lhs, type))
1112 : : {
1113 : 3048742 : case BRS_TRUE:
1114 : : // If it's true, the result is the same as OP2.
1115 : 3048742 : r = op2;
1116 : 3048742 : break;
1117 : :
1118 : 7820619 : case BRS_FALSE:
1119 : : // If the result is false, the only time we know anything is
1120 : : // if OP2 is a constant.
1121 : 7820619 : if (!op2.undefined_p ()
1122 : 23461857 : && wi::eq_p (op2.lower_bound(), op2.upper_bound()))
1123 : : {
1124 : 6121446 : r = op2;
1125 : 6121446 : r.invert ();
1126 : : }
1127 : : else
1128 : 1699173 : r.set_varying (type);
1129 : : break;
1130 : :
1131 : : default:
1132 : : break;
1133 : : }
1134 : 10905361 : return true;
1135 : : }
1136 : :
1137 : : bool
1138 : 1465946 : operator_equal::op2_range (irange &r, tree type,
1139 : : const irange &lhs,
1140 : : const irange &op1,
1141 : : relation_trio rel) const
1142 : : {
1143 : 1465946 : return operator_equal::op1_range (r, type, lhs, op1, rel.swap_op1_op2 ());
1144 : : }
1145 : :
1146 : : // -------------------------------------------------------------------------
1147 : :
1148 : : void
1149 : 0 : operator_not_equal::update_bitmask (irange &r, const irange &lh,
1150 : : const irange &rh) const
1151 : : {
1152 : 0 : update_known_bitmask (r, NE_EXPR, lh, rh);
1153 : 0 : }
1154 : :
1155 : : // Check if the LHS range indicates a relation between OP1 and OP2.
1156 : :
1157 : : relation_kind
1158 : 10563075 : operator_not_equal::op1_op2_relation (const irange &lhs, const irange &,
1159 : : const irange &) const
1160 : : {
1161 : 10563075 : if (lhs.undefined_p ())
1162 : : return VREL_UNDEFINED;
1163 : :
1164 : : // FALSE = op1 != op2 indicates EQ_EXPR.
1165 : 10563075 : if (lhs.zero_p ())
1166 : : return VREL_EQ;
1167 : :
1168 : : // TRUE = op1 != op2 indicates NE_EXPR.
1169 : 5328489 : if (!contains_zero_p (lhs))
1170 : 5289174 : return VREL_NE;
1171 : : return VREL_VARYING;
1172 : : }
1173 : :
1174 : : bool
1175 : 26684498 : operator_not_equal::fold_range (irange &r, tree type,
1176 : : const irange &op1,
1177 : : const irange &op2,
1178 : : relation_trio rel) const
1179 : : {
1180 : 26684498 : if (relop_early_resolve (r, type, op1, op2, rel, VREL_NE))
1181 : : return true;
1182 : :
1183 : : // We can be sure the values are always equal or not if both ranges
1184 : : // consist of a single value, and then compare them.
1185 : 26663684 : bool op1_const = wi::eq_p (op1.lower_bound (), op1.upper_bound ());
1186 : 26663684 : bool op2_const = wi::eq_p (op2.lower_bound (), op2.upper_bound ());
1187 : 26663358 : if (op1_const && op2_const)
1188 : : {
1189 : 1072895 : if (wi::ne_p (op1.lower_bound (), op2.upper_bound()))
1190 : 594772 : r = range_true (type);
1191 : : else
1192 : 478121 : r = range_false (type);
1193 : : }
1194 : : else
1195 : : {
1196 : : // If ranges do not intersect, we know the range is not equal,
1197 : : // otherwise we don't know anything for sure.
1198 : 25590465 : int_range_max tmp = op1;
1199 : 25590465 : tmp.intersect (op2);
1200 : 25590465 : if (tmp.undefined_p ())
1201 : 175213 : r = range_true (type);
1202 : : // Check if a constant cannot satisfy the bitmask requirements.
1203 : 46305532 : else if (op2_const && !op1.get_bitmask ().member_p (op2.lower_bound ()))
1204 : 804 : r = range_true (type);
1205 : 25455261 : else if (op1_const && !op2.get_bitmask ().member_p (op1.lower_bound ()))
1206 : 0 : r = range_true (type);
1207 : : else
1208 : 25414448 : r = range_true_and_false (type);
1209 : 25590465 : }
1210 : : return true;
1211 : : }
1212 : :
1213 : : bool
1214 : 20645034 : operator_not_equal::op1_range (irange &r, tree type,
1215 : : const irange &lhs,
1216 : : const irange &op2,
1217 : : relation_trio) const
1218 : : {
1219 : 20645034 : switch (get_bool_state (r, lhs, type))
1220 : : {
1221 : 12874854 : case BRS_TRUE:
1222 : : // If the result is true, the only time we know anything is if
1223 : : // OP2 is a constant.
1224 : 12874854 : if (!op2.undefined_p ()
1225 : 38624562 : && wi::eq_p (op2.lower_bound(), op2.upper_bound()))
1226 : : {
1227 : 10052163 : r = op2;
1228 : 10052163 : r.invert ();
1229 : : }
1230 : : else
1231 : 2822691 : r.set_varying (type);
1232 : : break;
1233 : :
1234 : 7744871 : case BRS_FALSE:
1235 : : // If it's false, the result is the same as OP2.
1236 : 7744871 : r = op2;
1237 : 7744871 : break;
1238 : :
1239 : : default:
1240 : : break;
1241 : : }
1242 : 20645034 : return true;
1243 : : }
1244 : :
1245 : :
1246 : : bool
1247 : 2590279 : operator_not_equal::op2_range (irange &r, tree type,
1248 : : const irange &lhs,
1249 : : const irange &op1,
1250 : : relation_trio rel) const
1251 : : {
1252 : 2590279 : return operator_not_equal::op1_range (r, type, lhs, op1, rel.swap_op1_op2 ());
1253 : : }
1254 : :
1255 : : // (X < VAL) produces the range of [MIN, VAL - 1].
1256 : :
1257 : : static void
1258 : 5692788 : build_lt (irange &r, tree type, const wide_int &val)
1259 : : {
1260 : 5692788 : wi::overflow_type ov;
1261 : 5692788 : wide_int lim;
1262 : 5692788 : signop sgn = TYPE_SIGN (type);
1263 : :
1264 : : // Signed 1 bit cannot represent 1 for subtraction.
1265 : 5692788 : if (sgn == SIGNED)
1266 : 3886403 : lim = wi::add (val, -1, sgn, &ov);
1267 : : else
1268 : 1806434 : lim = wi::sub (val, 1, sgn, &ov);
1269 : :
1270 : : // If val - 1 underflows, check if X < MIN, which is an empty range.
1271 : 5692788 : if (ov)
1272 : 289 : r.set_undefined ();
1273 : : else
1274 : 5692548 : r = int_range<1> (type, min_limit (type), lim);
1275 : 5692788 : }
1276 : :
1277 : : // (X <= VAL) produces the range of [MIN, VAL].
1278 : :
1279 : : static void
1280 : 11811408 : build_le (irange &r, tree type, const wide_int &val)
1281 : : {
1282 : 11811408 : r = int_range<1> (type, min_limit (type), val);
1283 : 11811408 : }
1284 : :
1285 : : // (X > VAL) produces the range of [VAL + 1, MAX].
1286 : :
1287 : : static void
1288 : 8430853 : build_gt (irange &r, tree type, const wide_int &val)
1289 : : {
1290 : 8430853 : wi::overflow_type ov;
1291 : 8430853 : wide_int lim;
1292 : 8430853 : signop sgn = TYPE_SIGN (type);
1293 : :
1294 : : // Signed 1 bit cannot represent 1 for addition.
1295 : 8430853 : if (sgn == SIGNED)
1296 : 4473355 : lim = wi::sub (val, -1, sgn, &ov);
1297 : : else
1298 : 3957574 : lim = wi::add (val, 1, sgn, &ov);
1299 : : // If val + 1 overflows, check is for X > MAX, which is an empty range.
1300 : 8430853 : if (ov)
1301 : 0 : r.set_undefined ();
1302 : : else
1303 : 8430929 : r = int_range<1> (type, lim, max_limit (type));
1304 : 8430853 : }
1305 : :
1306 : : // (X >= val) produces the range of [VAL, MAX].
1307 : :
1308 : : static void
1309 : 6052600 : build_ge (irange &r, tree type, const wide_int &val)
1310 : : {
1311 : 6052600 : r = int_range<1> (type, val, max_limit (type));
1312 : 6052600 : }
1313 : :
1314 : :
1315 : : void
1316 : 0 : operator_lt::update_bitmask (irange &r, const irange &lh,
1317 : : const irange &rh) const
1318 : : {
1319 : 0 : update_known_bitmask (r, LT_EXPR, lh, rh);
1320 : 0 : }
1321 : :
1322 : : // Check if the LHS range indicates a relation between OP1 and OP2.
1323 : :
1324 : : relation_kind
1325 : 10833591 : operator_lt::op1_op2_relation (const irange &lhs, const irange &,
1326 : : const irange &) const
1327 : : {
1328 : 10833591 : if (lhs.undefined_p ())
1329 : : return VREL_UNDEFINED;
1330 : :
1331 : : // FALSE = op1 < op2 indicates GE_EXPR.
1332 : 10833591 : if (lhs.zero_p ())
1333 : : return VREL_GE;
1334 : :
1335 : : // TRUE = op1 < op2 indicates LT_EXPR.
1336 : 5405255 : if (!contains_zero_p (lhs))
1337 : 5397981 : return VREL_LT;
1338 : : return VREL_VARYING;
1339 : : }
1340 : :
1341 : : bool
1342 : 4904851 : operator_lt::fold_range (irange &r, tree type,
1343 : : const irange &op1,
1344 : : const irange &op2,
1345 : : relation_trio rel) const
1346 : : {
1347 : 4904851 : if (relop_early_resolve (r, type, op1, op2, rel, VREL_LT))
1348 : : return true;
1349 : :
1350 : 4883417 : signop sign = TYPE_SIGN (op1.type ());
1351 : 4883417 : gcc_checking_assert (sign == TYPE_SIGN (op2.type ()));
1352 : :
1353 : 4883453 : if (wi::lt_p (op1.upper_bound (), op2.lower_bound (), sign))
1354 : 21421 : r = range_true (type);
1355 : 4862032 : else if (!wi::lt_p (op1.lower_bound (), op2.upper_bound (), sign))
1356 : 46661 : r = range_false (type);
1357 : : // Use nonzero bits to determine if < 0 is false.
1358 : 5880454 : else if (op2.zero_p () && !wi::neg_p (op1.get_nonzero_bits (), sign))
1359 : 12 : r = range_false (type);
1360 : : else
1361 : 4815323 : r = range_true_and_false (type);
1362 : : return true;
1363 : : }
1364 : :
1365 : : bool
1366 : 4616834 : operator_lt::op1_range (irange &r, tree type,
1367 : : const irange &lhs,
1368 : : const irange &op2,
1369 : : relation_trio) const
1370 : : {
1371 : 4616834 : if (op2.undefined_p ())
1372 : : return false;
1373 : :
1374 : 4616834 : switch (get_bool_state (r, lhs, type))
1375 : : {
1376 : 2123044 : case BRS_TRUE:
1377 : 2123044 : build_lt (r, type, op2.upper_bound ());
1378 : 2123044 : break;
1379 : :
1380 : 2489435 : case BRS_FALSE:
1381 : 2489435 : build_ge (r, type, op2.lower_bound ());
1382 : 2489435 : break;
1383 : :
1384 : : default:
1385 : : break;
1386 : : }
1387 : : return true;
1388 : : }
1389 : :
1390 : : bool
1391 : 3407986 : operator_lt::op2_range (irange &r, tree type,
1392 : : const irange &lhs,
1393 : : const irange &op1,
1394 : : relation_trio) const
1395 : : {
1396 : 3407986 : if (op1.undefined_p ())
1397 : : return false;
1398 : :
1399 : 3407984 : switch (get_bool_state (r, lhs, type))
1400 : : {
1401 : 1409018 : case BRS_TRUE:
1402 : 1409018 : build_gt (r, type, op1.lower_bound ());
1403 : 1409018 : break;
1404 : :
1405 : 1995568 : case BRS_FALSE:
1406 : 1995568 : build_le (r, type, op1.upper_bound ());
1407 : 1995568 : break;
1408 : :
1409 : : default:
1410 : : break;
1411 : : }
1412 : : return true;
1413 : : }
1414 : :
1415 : :
1416 : : void
1417 : 0 : operator_le::update_bitmask (irange &r, const irange &lh,
1418 : : const irange &rh) const
1419 : : {
1420 : 0 : update_known_bitmask (r, LE_EXPR, lh, rh);
1421 : 0 : }
1422 : :
1423 : : // Check if the LHS range indicates a relation between OP1 and OP2.
1424 : :
1425 : : relation_kind
1426 : 3660650 : operator_le::op1_op2_relation (const irange &lhs, const irange &,
1427 : : const irange &) const
1428 : : {
1429 : 3660650 : if (lhs.undefined_p ())
1430 : : return VREL_UNDEFINED;
1431 : :
1432 : : // FALSE = op1 <= op2 indicates GT_EXPR.
1433 : 3660650 : if (lhs.zero_p ())
1434 : : return VREL_GT;
1435 : :
1436 : : // TRUE = op1 <= op2 indicates LE_EXPR.
1437 : 2126624 : if (!contains_zero_p (lhs))
1438 : 2118536 : return VREL_LE;
1439 : : return VREL_VARYING;
1440 : : }
1441 : :
1442 : : bool
1443 : 4547721 : operator_le::fold_range (irange &r, tree type,
1444 : : const irange &op1,
1445 : : const irange &op2,
1446 : : relation_trio rel) const
1447 : : {
1448 : 4547721 : if (relop_early_resolve (r, type, op1, op2, rel, VREL_LE))
1449 : : return true;
1450 : :
1451 : 4534031 : signop sign = TYPE_SIGN (op1.type ());
1452 : 4534031 : gcc_checking_assert (sign == TYPE_SIGN (op2.type ()));
1453 : :
1454 : 4534031 : if (wi::le_p (op1.upper_bound (), op2.lower_bound (), sign))
1455 : 104265 : r = range_true (type);
1456 : 4429766 : else if (!wi::le_p (op1.lower_bound (), op2.upper_bound (), sign))
1457 : 44535 : r = range_false (type);
1458 : : else
1459 : 4385231 : r = range_true_and_false (type);
1460 : : return true;
1461 : : }
1462 : :
1463 : : bool
1464 : 5167547 : operator_le::op1_range (irange &r, tree type,
1465 : : const irange &lhs,
1466 : : const irange &op2,
1467 : : relation_trio) const
1468 : : {
1469 : 5167547 : if (op2.undefined_p ())
1470 : : return false;
1471 : :
1472 : 5167547 : switch (get_bool_state (r, lhs, type))
1473 : : {
1474 : 2772517 : case BRS_TRUE:
1475 : 2772517 : build_le (r, type, op2.upper_bound ());
1476 : 2772517 : break;
1477 : :
1478 : 2383469 : case BRS_FALSE:
1479 : 2383469 : build_gt (r, type, op2.lower_bound ());
1480 : 2383469 : break;
1481 : :
1482 : : default:
1483 : : break;
1484 : : }
1485 : : return true;
1486 : : }
1487 : :
1488 : : bool
1489 : 909700 : operator_le::op2_range (irange &r, tree type,
1490 : : const irange &lhs,
1491 : : const irange &op1,
1492 : : relation_trio) const
1493 : : {
1494 : 909700 : if (op1.undefined_p ())
1495 : : return false;
1496 : :
1497 : 909700 : switch (get_bool_state (r, lhs, type))
1498 : : {
1499 : 415867 : case BRS_TRUE:
1500 : 415867 : build_ge (r, type, op1.lower_bound ());
1501 : 415867 : break;
1502 : :
1503 : 490337 : case BRS_FALSE:
1504 : 490337 : build_lt (r, type, op1.upper_bound ());
1505 : 490337 : break;
1506 : :
1507 : : default:
1508 : : break;
1509 : : }
1510 : : return true;
1511 : : }
1512 : :
1513 : :
1514 : : void
1515 : 0 : operator_gt::update_bitmask (irange &r, const irange &lh,
1516 : : const irange &rh) const
1517 : : {
1518 : 0 : update_known_bitmask (r, GT_EXPR, lh, rh);
1519 : 0 : }
1520 : :
1521 : : // Check if the LHS range indicates a relation between OP1 and OP2.
1522 : :
1523 : : relation_kind
1524 : 11155610 : operator_gt::op1_op2_relation (const irange &lhs, const irange &,
1525 : : const irange &) const
1526 : : {
1527 : 11155610 : if (lhs.undefined_p ())
1528 : : return VREL_UNDEFINED;
1529 : :
1530 : : // FALSE = op1 > op2 indicates LE_EXPR.
1531 : 11155610 : if (lhs.zero_p ())
1532 : : return VREL_LE;
1533 : :
1534 : : // TRUE = op1 > op2 indicates GT_EXPR.
1535 : 5975955 : if (!contains_zero_p (lhs))
1536 : 5962778 : return VREL_GT;
1537 : : return VREL_VARYING;
1538 : : }
1539 : :
1540 : : bool
1541 : 10802416 : operator_gt::fold_range (irange &r, tree type,
1542 : : const irange &op1, const irange &op2,
1543 : : relation_trio rel) const
1544 : : {
1545 : 10802416 : if (relop_early_resolve (r, type, op1, op2, rel, VREL_GT))
1546 : : return true;
1547 : :
1548 : 10751722 : signop sign = TYPE_SIGN (op1.type ());
1549 : 10751722 : gcc_checking_assert (sign == TYPE_SIGN (op2.type ()));
1550 : :
1551 : 10751748 : if (wi::gt_p (op1.lower_bound (), op2.upper_bound (), sign))
1552 : 82021 : r = range_true (type);
1553 : 10669727 : else if (!wi::gt_p (op1.upper_bound (), op2.lower_bound (), sign))
1554 : 343493 : r = range_false (type);
1555 : : else
1556 : 10326208 : r = range_true_and_false (type);
1557 : : return true;
1558 : : }
1559 : :
1560 : : bool
1561 : 10435122 : operator_gt::op1_range (irange &r, tree type,
1562 : : const irange &lhs, const irange &op2,
1563 : : relation_trio) const
1564 : : {
1565 : 10435122 : if (op2.undefined_p ())
1566 : : return false;
1567 : :
1568 : 10435122 : switch (get_bool_state (r, lhs, type))
1569 : : {
1570 : 4137729 : case BRS_TRUE:
1571 : 4137729 : build_gt (r, type, op2.lower_bound ());
1572 : 4137729 : break;
1573 : :
1574 : 6288647 : case BRS_FALSE:
1575 : 6288647 : build_le (r, type, op2.upper_bound ());
1576 : 6288647 : break;
1577 : :
1578 : : default:
1579 : : break;
1580 : : }
1581 : : return true;
1582 : : }
1583 : :
1584 : : bool
1585 : 3446512 : operator_gt::op2_range (irange &r, tree type,
1586 : : const irange &lhs,
1587 : : const irange &op1,
1588 : : relation_trio) const
1589 : : {
1590 : 3446512 : if (op1.undefined_p ())
1591 : : return false;
1592 : :
1593 : 3446512 : switch (get_bool_state (r, lhs, type))
1594 : : {
1595 : 2072981 : case BRS_TRUE:
1596 : 2072981 : build_lt (r, type, op1.upper_bound ());
1597 : 2072981 : break;
1598 : :
1599 : 1364983 : case BRS_FALSE:
1600 : 1364983 : build_ge (r, type, op1.lower_bound ());
1601 : 1364983 : break;
1602 : :
1603 : : default:
1604 : : break;
1605 : : }
1606 : : return true;
1607 : : }
1608 : :
1609 : :
1610 : : void
1611 : 0 : operator_ge::update_bitmask (irange &r, const irange &lh,
1612 : : const irange &rh) const
1613 : : {
1614 : 0 : update_known_bitmask (r, GE_EXPR, lh, rh);
1615 : 0 : }
1616 : :
1617 : : // Check if the LHS range indicates a relation between OP1 and OP2.
1618 : :
1619 : : relation_kind
1620 : 3676414 : operator_ge::op1_op2_relation (const irange &lhs, const irange &,
1621 : : const irange &) const
1622 : : {
1623 : 3676414 : if (lhs.undefined_p ())
1624 : : return VREL_UNDEFINED;
1625 : :
1626 : : // FALSE = op1 >= op2 indicates LT_EXPR.
1627 : 3676414 : if (lhs.zero_p ())
1628 : : return VREL_LT;
1629 : :
1630 : : // TRUE = op1 >= op2 indicates GE_EXPR.
1631 : 1986975 : if (!contains_zero_p (lhs))
1632 : 1981338 : return VREL_GE;
1633 : : return VREL_VARYING;
1634 : : }
1635 : :
1636 : : bool
1637 : 2575726 : operator_ge::fold_range (irange &r, tree type,
1638 : : const irange &op1,
1639 : : const irange &op2,
1640 : : relation_trio rel) const
1641 : : {
1642 : 2575726 : if (relop_early_resolve (r, type, op1, op2, rel, VREL_GE))
1643 : : return true;
1644 : :
1645 : 2564368 : signop sign = TYPE_SIGN (op1.type ());
1646 : 2564368 : gcc_checking_assert (sign == TYPE_SIGN (op2.type ()));
1647 : :
1648 : 2564400 : if (wi::ge_p (op1.lower_bound (), op2.upper_bound (), sign))
1649 : 155857 : r = range_true (type);
1650 : 2408543 : else if (!wi::ge_p (op1.upper_bound (), op2.lower_bound (), sign))
1651 : 6148 : r = range_false (type);
1652 : : else
1653 : 2402363 : r = range_true_and_false (type);
1654 : : return true;
1655 : : }
1656 : :
1657 : : bool
1658 : 2794280 : operator_ge::op1_range (irange &r, tree type,
1659 : : const irange &lhs,
1660 : : const irange &op2,
1661 : : relation_trio) const
1662 : : {
1663 : 2794280 : if (op2.undefined_p ())
1664 : : return false;
1665 : :
1666 : 2794280 : switch (get_bool_state (r, lhs, type))
1667 : : {
1668 : 1782315 : case BRS_TRUE:
1669 : 1782315 : build_ge (r, type, op2.lower_bound ());
1670 : 1782315 : break;
1671 : :
1672 : 1006426 : case BRS_FALSE:
1673 : 1006426 : build_lt (r, type, op2.upper_bound ());
1674 : 1006426 : break;
1675 : :
1676 : : default:
1677 : : break;
1678 : : }
1679 : : return true;
1680 : : }
1681 : :
1682 : : bool
1683 : 1258045 : operator_ge::op2_range (irange &r, tree type,
1684 : : const irange &lhs,
1685 : : const irange &op1,
1686 : : relation_trio) const
1687 : : {
1688 : 1258045 : if (op1.undefined_p ())
1689 : : return false;
1690 : :
1691 : 1258045 : switch (get_bool_state (r, lhs, type))
1692 : : {
1693 : 754676 : case BRS_TRUE:
1694 : 754676 : build_le (r, type, op1.upper_bound ());
1695 : 754676 : break;
1696 : :
1697 : 500637 : case BRS_FALSE:
1698 : 500637 : build_gt (r, type, op1.lower_bound ());
1699 : 500637 : break;
1700 : :
1701 : : default:
1702 : : break;
1703 : : }
1704 : : return true;
1705 : : }
1706 : :
1707 : :
1708 : : void
1709 : 45123185 : operator_plus::update_bitmask (irange &r, const irange &lh,
1710 : : const irange &rh) const
1711 : : {
1712 : 45123185 : update_known_bitmask (r, PLUS_EXPR, lh, rh);
1713 : 45123185 : }
1714 : :
1715 : : // Check to see if the range of OP2 indicates anything about the relation
1716 : : // between LHS and OP1.
1717 : :
1718 : : relation_kind
1719 : 41696669 : operator_plus::lhs_op1_relation (const irange &lhs,
1720 : : const irange &op1,
1721 : : const irange &op2,
1722 : : relation_kind) const
1723 : : {
1724 : 41696669 : if (lhs.undefined_p () || op1.undefined_p () || op2.undefined_p ())
1725 : : return VREL_VARYING;
1726 : :
1727 : 41667423 : tree type = lhs.type ();
1728 : 41667423 : unsigned prec = TYPE_PRECISION (type);
1729 : 41667423 : wi::overflow_type ovf1, ovf2;
1730 : 41667423 : signop sign = TYPE_SIGN (type);
1731 : :
1732 : : // LHS = OP1 + 0 indicates LHS == OP1.
1733 : 41667423 : if (op2.zero_p ())
1734 : : return VREL_EQ;
1735 : :
1736 : 41514955 : if (TYPE_OVERFLOW_WRAPS (type))
1737 : : {
1738 : 23538282 : wi::add (op1.lower_bound (), op2.lower_bound (), sign, &ovf1);
1739 : 23538496 : wi::add (op1.upper_bound (), op2.upper_bound (), sign, &ovf2);
1740 : : }
1741 : : else
1742 : 17977101 : ovf1 = ovf2 = wi::OVF_NONE;
1743 : :
1744 : : // Never wrapping additions.
1745 : 41514955 : if (!ovf1 && !ovf2)
1746 : : {
1747 : : // Positive op2 means lhs > op1.
1748 : 24009460 : if (wi::gt_p (op2.lower_bound (), wi::zero (prec), sign))
1749 : : return VREL_GT;
1750 : 9062283 : if (wi::ge_p (op2.lower_bound (), wi::zero (prec), sign))
1751 : : return VREL_GE;
1752 : :
1753 : : // Negative op2 means lhs < op1.
1754 : 7503064 : if (wi::lt_p (op2.upper_bound (), wi::zero (prec), sign))
1755 : : return VREL_LT;
1756 : 4740909 : if (wi::le_p (op2.upper_bound (), wi::zero (prec), sign))
1757 : : return VREL_LE;
1758 : : }
1759 : : // Always wrapping additions.
1760 : 17505840 : else if (ovf1 && ovf1 == ovf2)
1761 : : {
1762 : : // Positive op2 means lhs < op1.
1763 : 616999 : if (wi::gt_p (op2.lower_bound (), wi::zero (prec), sign))
1764 : : return VREL_LT;
1765 : 20 : if (wi::ge_p (op2.lower_bound (), wi::zero (prec), sign))
1766 : : return VREL_LE;
1767 : :
1768 : : // Negative op2 means lhs > op1.
1769 : 20 : if (wi::lt_p (op2.upper_bound (), wi::zero (prec), sign))
1770 : : return VREL_GT;
1771 : 0 : if (wi::le_p (op2.upper_bound (), wi::zero (prec), sign))
1772 : : return VREL_GE;
1773 : : }
1774 : :
1775 : : // If op2 does not contain 0, then LHS and OP1 can never be equal.
1776 : 21618543 : if (!range_includes_zero_p (op2))
1777 : : return VREL_NE;
1778 : :
1779 : : return VREL_VARYING;
1780 : : }
1781 : :
1782 : : // PLUS is symmetrical, so we can simply call lhs_op1_relation with reversed
1783 : : // operands.
1784 : :
1785 : : relation_kind
1786 : 6990982 : operator_plus::lhs_op2_relation (const irange &lhs, const irange &op1,
1787 : : const irange &op2, relation_kind rel) const
1788 : : {
1789 : 6990982 : return lhs_op1_relation (lhs, op2, op1, rel);
1790 : : }
1791 : :
1792 : : void
1793 : 65099061 : operator_plus::wi_fold (irange &r, tree type,
1794 : : const wide_int &lh_lb, const wide_int &lh_ub,
1795 : : const wide_int &rh_lb, const wide_int &rh_ub) const
1796 : : {
1797 : 65099061 : wi::overflow_type ov_lb, ov_ub;
1798 : 65099061 : signop s = TYPE_SIGN (type);
1799 : 65099061 : wide_int new_lb = wi::add (lh_lb, rh_lb, s, &ov_lb);
1800 : 65099061 : wide_int new_ub = wi::add (lh_ub, rh_ub, s, &ov_ub);
1801 : 65099061 : value_range_with_overflow (r, type, new_lb, new_ub, ov_lb, ov_ub);
1802 : 65099061 : }
1803 : :
1804 : : // Given addition or subtraction, determine the possible NORMAL ranges and
1805 : : // OVERFLOW ranges given an OFFSET range. ADD_P is true for addition.
1806 : : // Return the relation that exists between the LHS and OP1 in order for the
1807 : : // NORMAL range to apply.
1808 : : // a return value of VREL_VARYING means no ranges were applicable.
1809 : :
1810 : : static relation_kind
1811 : 650526 : plus_minus_ranges (irange &r_ov, irange &r_normal, const irange &offset,
1812 : : bool add_p)
1813 : : {
1814 : 650526 : relation_kind kind = VREL_VARYING;
1815 : : // For now, only deal with constant adds. This could be extended to ranges
1816 : : // when someone is so motivated.
1817 : 650526 : if (!offset.singleton_p () || offset.zero_p ())
1818 : 635721 : return kind;
1819 : :
1820 : : // Always work with a positive offset. ie a+ -2 -> a-2 and a- -2 > a+2
1821 : 14805 : wide_int off = offset.lower_bound ();
1822 : 14805 : if (wi::neg_p (off, SIGNED))
1823 : : {
1824 : 748 : add_p = !add_p;
1825 : 748 : off = wi::neg (off);
1826 : : }
1827 : :
1828 : 14805 : wi::overflow_type ov;
1829 : 14805 : tree type = offset.type ();
1830 : 14805 : unsigned prec = TYPE_PRECISION (type);
1831 : 14805 : wide_int ub;
1832 : 14805 : wide_int lb;
1833 : : // calculate the normal range and relation for the operation.
1834 : 14805 : if (add_p)
1835 : : {
1836 : : // [ 0 , INF - OFF]
1837 : 14057 : lb = wi::zero (prec);
1838 : 14057 : ub = wi::sub (irange_val_max (type), off, UNSIGNED, &ov);
1839 : 14057 : kind = VREL_GT;
1840 : : }
1841 : : else
1842 : : {
1843 : : // [ OFF, INF ]
1844 : 748 : lb = off;
1845 : 748 : ub = irange_val_max (type);
1846 : 748 : kind = VREL_LT;
1847 : : }
1848 : 14805 : int_range<2> normal_range (type, lb, ub);
1849 : 14805 : int_range<2> ov_range (type, lb, ub, VR_ANTI_RANGE);
1850 : :
1851 : 14805 : r_ov = ov_range;
1852 : 14805 : r_normal = normal_range;
1853 : 14805 : return kind;
1854 : 14805 : }
1855 : :
1856 : : // Once op1 has been calculated by operator_plus or operator_minus, check
1857 : : // to see if the relation passed causes any part of the calculation to
1858 : : // be not possible. ie
1859 : : // a_2 = b_3 + 1 with a_2 < b_3 can refine the range of b_3 to [INF, INF]
1860 : : // and that further refines a_2 to [0, 0].
1861 : : // R is the value of op1, OP2 is the offset being added/subtracted, REL is the
1862 : : // relation between LHS relation OP1 and ADD_P is true for PLUS, false for
1863 : : // MINUS. IF any adjustment can be made, R will reflect it.
1864 : :
1865 : : static void
1866 : 8861979 : adjust_op1_for_overflow (irange &r, const irange &op2, relation_kind rel,
1867 : : bool add_p)
1868 : : {
1869 : 8861979 : if (r.undefined_p ())
1870 : : return;
1871 : 8861978 : tree type = r.type ();
1872 : : // Check for unsigned overflow and calculate the overflow part.
1873 : 8861978 : signop s = TYPE_SIGN (type);
1874 : 8861978 : if (!TYPE_OVERFLOW_WRAPS (type) || s == SIGNED)
1875 : : return;
1876 : :
1877 : : // Only work with <, <=, >, >= relations.
1878 : 4708279 : if (!relation_lt_le_gt_ge_p (rel))
1879 : : return;
1880 : :
1881 : : // Get the ranges for this offset.
1882 : 650526 : int_range_max normal, overflow;
1883 : 650526 : relation_kind k = plus_minus_ranges (overflow, normal, op2, add_p);
1884 : :
1885 : : // VREL_VARYING means there are no adjustments.
1886 : 650526 : if (k == VREL_VARYING)
1887 : : return;
1888 : :
1889 : : // If the relations match use the normal range, otherwise use overflow range.
1890 : 14805 : if (relation_intersect (k, rel) == k)
1891 : 10824 : r.intersect (normal);
1892 : : else
1893 : 3981 : r.intersect (overflow);
1894 : : return;
1895 : 650526 : }
1896 : :
1897 : : bool
1898 : 7984208 : operator_plus::op1_range (irange &r, tree type,
1899 : : const irange &lhs,
1900 : : const irange &op2,
1901 : : relation_trio trio) const
1902 : : {
1903 : 7984208 : if (lhs.undefined_p ())
1904 : : return false;
1905 : : // Start with the default operation.
1906 : 7984208 : range_op_handler minus (MINUS_EXPR);
1907 : 7984208 : if (!minus)
1908 : : return false;
1909 : 7984208 : bool res = minus.fold_range (r, type, lhs, op2);
1910 : 7984208 : relation_kind rel = trio.lhs_op1 ();
1911 : : // Check for a relation refinement.
1912 : 7984208 : if (res)
1913 : 7984208 : adjust_op1_for_overflow (r, op2, rel, true /* PLUS_EXPR */);
1914 : : return res;
1915 : : }
1916 : :
1917 : : bool
1918 : 1716428 : operator_plus::op2_range (irange &r, tree type,
1919 : : const irange &lhs,
1920 : : const irange &op1,
1921 : : relation_trio rel) const
1922 : : {
1923 : 1716428 : return op1_range (r, type, lhs, op1, rel.swap_op1_op2 ());
1924 : : }
1925 : :
1926 : : class operator_widen_plus_signed : public range_operator
1927 : : {
1928 : : public:
1929 : : virtual void wi_fold (irange &r, tree type,
1930 : : const wide_int &lh_lb,
1931 : : const wide_int &lh_ub,
1932 : : const wide_int &rh_lb,
1933 : : const wide_int &rh_ub) const;
1934 : : } op_widen_plus_signed;
1935 : :
1936 : : void
1937 : 0 : operator_widen_plus_signed::wi_fold (irange &r, tree type,
1938 : : const wide_int &lh_lb,
1939 : : const wide_int &lh_ub,
1940 : : const wide_int &rh_lb,
1941 : : const wide_int &rh_ub) const
1942 : : {
1943 : 0 : wi::overflow_type ov_lb, ov_ub;
1944 : 0 : signop s = TYPE_SIGN (type);
1945 : :
1946 : 0 : wide_int lh_wlb
1947 : 0 : = wide_int::from (lh_lb, wi::get_precision (lh_lb) * 2, SIGNED);
1948 : 0 : wide_int lh_wub
1949 : 0 : = wide_int::from (lh_ub, wi::get_precision (lh_ub) * 2, SIGNED);
1950 : 0 : wide_int rh_wlb = wide_int::from (rh_lb, wi::get_precision (rh_lb) * 2, s);
1951 : 0 : wide_int rh_wub = wide_int::from (rh_ub, wi::get_precision (rh_ub) * 2, s);
1952 : :
1953 : 0 : wide_int new_lb = wi::add (lh_wlb, rh_wlb, s, &ov_lb);
1954 : 0 : wide_int new_ub = wi::add (lh_wub, rh_wub, s, &ov_ub);
1955 : :
1956 : 0 : r = int_range<2> (type, new_lb, new_ub);
1957 : 0 : }
1958 : :
1959 : : class operator_widen_plus_unsigned : public range_operator
1960 : : {
1961 : : public:
1962 : : virtual void wi_fold (irange &r, tree type,
1963 : : const wide_int &lh_lb,
1964 : : const wide_int &lh_ub,
1965 : : const wide_int &rh_lb,
1966 : : const wide_int &rh_ub) const;
1967 : : } op_widen_plus_unsigned;
1968 : :
1969 : : void
1970 : 0 : operator_widen_plus_unsigned::wi_fold (irange &r, tree type,
1971 : : const wide_int &lh_lb,
1972 : : const wide_int &lh_ub,
1973 : : const wide_int &rh_lb,
1974 : : const wide_int &rh_ub) const
1975 : : {
1976 : 0 : wi::overflow_type ov_lb, ov_ub;
1977 : 0 : signop s = TYPE_SIGN (type);
1978 : :
1979 : 0 : wide_int lh_wlb
1980 : 0 : = wide_int::from (lh_lb, wi::get_precision (lh_lb) * 2, UNSIGNED);
1981 : 0 : wide_int lh_wub
1982 : 0 : = wide_int::from (lh_ub, wi::get_precision (lh_ub) * 2, UNSIGNED);
1983 : 0 : wide_int rh_wlb = wide_int::from (rh_lb, wi::get_precision (rh_lb) * 2, s);
1984 : 0 : wide_int rh_wub = wide_int::from (rh_ub, wi::get_precision (rh_ub) * 2, s);
1985 : :
1986 : 0 : wide_int new_lb = wi::add (lh_wlb, rh_wlb, s, &ov_lb);
1987 : 0 : wide_int new_ub = wi::add (lh_wub, rh_wub, s, &ov_ub);
1988 : :
1989 : 0 : r = int_range<2> (type, new_lb, new_ub);
1990 : 0 : }
1991 : :
1992 : : void
1993 : 15169193 : operator_minus::update_bitmask (irange &r, const irange &lh,
1994 : : const irange &rh) const
1995 : : {
1996 : 15169193 : update_known_bitmask (r, MINUS_EXPR, lh, rh);
1997 : 15169193 : }
1998 : :
1999 : : void
2000 : 20895554 : operator_minus::wi_fold (irange &r, tree type,
2001 : : const wide_int &lh_lb, const wide_int &lh_ub,
2002 : : const wide_int &rh_lb, const wide_int &rh_ub) const
2003 : : {
2004 : 20895554 : wi::overflow_type ov_lb, ov_ub;
2005 : 20895554 : signop s = TYPE_SIGN (type);
2006 : 20895554 : wide_int new_lb = wi::sub (lh_lb, rh_ub, s, &ov_lb);
2007 : 20895554 : wide_int new_ub = wi::sub (lh_ub, rh_lb, s, &ov_ub);
2008 : 20895554 : value_range_with_overflow (r, type, new_lb, new_ub, ov_lb, ov_ub);
2009 : 20895554 : }
2010 : :
2011 : :
2012 : : // Return the relation between LHS and OP1 based on the relation between
2013 : : // OP1 and OP2.
2014 : :
2015 : : relation_kind
2016 : 4082245 : operator_minus::lhs_op1_relation (const irange &, const irange &op1,
2017 : : const irange &, relation_kind rel) const
2018 : : {
2019 : 4082245 : if (!op1.undefined_p () && TYPE_SIGN (op1.type ()) == UNSIGNED)
2020 : 2018310 : switch (rel)
2021 : : {
2022 : : case VREL_GT:
2023 : : case VREL_GE:
2024 : : return VREL_LE;
2025 : : default:
2026 : : break;
2027 : : }
2028 : : return VREL_VARYING;
2029 : : }
2030 : :
2031 : : // Check to see if the relation REL between OP1 and OP2 has any effect on the
2032 : : // LHS of the expression. If so, apply it to LHS_RANGE. This is a helper
2033 : : // function for both MINUS_EXPR and POINTER_DIFF_EXPR.
2034 : :
2035 : : bool
2036 : 17668515 : minus_op1_op2_relation_effect (irange &lhs_range, tree type,
2037 : : const irange &op1_range ATTRIBUTE_UNUSED,
2038 : : const irange &op2_range ATTRIBUTE_UNUSED,
2039 : : relation_kind rel)
2040 : : {
2041 : 17668515 : if (rel == VREL_VARYING)
2042 : : return false;
2043 : :
2044 : 234892 : int_range<2> rel_range;
2045 : 234892 : unsigned prec = TYPE_PRECISION (type);
2046 : 234892 : signop sgn = TYPE_SIGN (type);
2047 : :
2048 : : // == and != produce [0,0] and ~[0,0] regardless of wrapping.
2049 : 234892 : if (rel == VREL_EQ)
2050 : 7440 : rel_range = int_range<2> (type, wi::zero (prec), wi::zero (prec));
2051 : 227452 : else if (rel == VREL_NE)
2052 : 90724 : rel_range = int_range<2> (type, wi::zero (prec), wi::zero (prec),
2053 : 45362 : VR_ANTI_RANGE);
2054 : 182090 : else if (TYPE_OVERFLOW_WRAPS (type))
2055 : : {
2056 : 119952 : switch (rel)
2057 : : {
2058 : : // For wrapping signed values and unsigned, if op1 > op2 or
2059 : : // op1 < op2, then op1 - op2 can be restricted to ~[0, 0].
2060 : 45307 : case VREL_GT:
2061 : 45307 : case VREL_LT:
2062 : 90614 : rel_range = int_range<2> (type, wi::zero (prec), wi::zero (prec),
2063 : 45307 : VR_ANTI_RANGE);
2064 : 45307 : break;
2065 : : default:
2066 : : return false;
2067 : : }
2068 : : }
2069 : : else
2070 : : {
2071 : 62138 : switch (rel)
2072 : : {
2073 : : // op1 > op2, op1 - op2 can be restricted to [1, +INF]
2074 : 21341 : case VREL_GT:
2075 : 42682 : rel_range = int_range<2> (type, wi::one (prec),
2076 : 42682 : wi::max_value (prec, sgn));
2077 : 21341 : break;
2078 : : // op1 >= op2, op1 - op2 can be restricted to [0, +INF]
2079 : 40116 : case VREL_GE:
2080 : 80232 : rel_range = int_range<2> (type, wi::zero (prec),
2081 : 80232 : wi::max_value (prec, sgn));
2082 : 40116 : break;
2083 : : // op1 < op2, op1 - op2 can be restricted to [-INF, -1]
2084 : 286 : case VREL_LT:
2085 : 572 : rel_range = int_range<2> (type, wi::min_value (prec, sgn),
2086 : 286 : wi::minus_one (prec));
2087 : 286 : break;
2088 : : // op1 <= op2, op1 - op2 can be restricted to [-INF, 0]
2089 : 244 : case VREL_LE:
2090 : 488 : rel_range = int_range<2> (type, wi::min_value (prec, sgn),
2091 : 244 : wi::zero (prec));
2092 : 244 : break;
2093 : : default:
2094 : : return false;
2095 : : }
2096 : : }
2097 : 160096 : lhs_range.intersect (rel_range);
2098 : 160096 : return true;
2099 : 234892 : }
2100 : :
2101 : : bool
2102 : 15169193 : operator_minus::op1_op2_relation_effect (irange &lhs_range, tree type,
2103 : : const irange &op1_range,
2104 : : const irange &op2_range,
2105 : : relation_kind rel) const
2106 : : {
2107 : 15169193 : return minus_op1_op2_relation_effect (lhs_range, type, op1_range, op2_range,
2108 : 15169193 : rel);
2109 : : }
2110 : :
2111 : : bool
2112 : 877771 : operator_minus::op1_range (irange &r, tree type,
2113 : : const irange &lhs,
2114 : : const irange &op2,
2115 : : relation_trio trio) const
2116 : : {
2117 : 877771 : if (lhs.undefined_p ())
2118 : : return false;
2119 : : // Start with the default operation.
2120 : 877771 : range_op_handler minus (PLUS_EXPR);
2121 : 877771 : if (!minus)
2122 : : return false;
2123 : 877771 : bool res = minus.fold_range (r, type, lhs, op2);
2124 : 877771 : relation_kind rel = trio.lhs_op1 ();
2125 : 877771 : if (res)
2126 : 877771 : adjust_op1_for_overflow (r, op2, rel, false /* PLUS_EXPR */);
2127 : : return res;
2128 : :
2129 : : }
2130 : :
2131 : : bool
2132 : 1285932 : operator_minus::op2_range (irange &r, tree type,
2133 : : const irange &lhs,
2134 : : const irange &op1,
2135 : : relation_trio) const
2136 : : {
2137 : 1285932 : if (lhs.undefined_p ())
2138 : : return false;
2139 : 1285932 : return fold_range (r, type, op1, lhs);
2140 : : }
2141 : :
2142 : : void
2143 : 697067 : operator_min::update_bitmask (irange &r, const irange &lh,
2144 : : const irange &rh) const
2145 : : {
2146 : 697067 : update_known_bitmask (r, MIN_EXPR, lh, rh);
2147 : 697067 : }
2148 : :
2149 : : void
2150 : 1127337 : operator_min::wi_fold (irange &r, tree type,
2151 : : const wide_int &lh_lb, const wide_int &lh_ub,
2152 : : const wide_int &rh_lb, const wide_int &rh_ub) const
2153 : : {
2154 : 1127337 : signop s = TYPE_SIGN (type);
2155 : 1127337 : wide_int new_lb = wi::min (lh_lb, rh_lb, s);
2156 : 1127337 : wide_int new_ub = wi::min (lh_ub, rh_ub, s);
2157 : 1127337 : value_range_with_overflow (r, type, new_lb, new_ub);
2158 : 1127337 : }
2159 : :
2160 : :
2161 : : void
2162 : 573457 : operator_max::update_bitmask (irange &r, const irange &lh,
2163 : : const irange &rh) const
2164 : : {
2165 : 573457 : update_known_bitmask (r, MAX_EXPR, lh, rh);
2166 : 573457 : }
2167 : :
2168 : : void
2169 : 679780 : operator_max::wi_fold (irange &r, tree type,
2170 : : const wide_int &lh_lb, const wide_int &lh_ub,
2171 : : const wide_int &rh_lb, const wide_int &rh_ub) const
2172 : : {
2173 : 679780 : signop s = TYPE_SIGN (type);
2174 : 679780 : wide_int new_lb = wi::max (lh_lb, rh_lb, s);
2175 : 679780 : wide_int new_ub = wi::max (lh_ub, rh_ub, s);
2176 : 679780 : value_range_with_overflow (r, type, new_lb, new_ub);
2177 : 679780 : }
2178 : :
2179 : :
2180 : : // Calculate the cross product of two sets of ranges and return it.
2181 : : //
2182 : : // Multiplications, divisions and shifts are a bit tricky to handle,
2183 : : // depending on the mix of signs we have in the two ranges, we need to
2184 : : // operate on different values to get the minimum and maximum values
2185 : : // for the new range. One approach is to figure out all the
2186 : : // variations of range combinations and do the operations.
2187 : : //
2188 : : // However, this involves several calls to compare_values and it is
2189 : : // pretty convoluted. It's simpler to do the 4 operations (MIN0 OP
2190 : : // MIN1, MIN0 OP MAX1, MAX0 OP MIN1 and MAX0 OP MAX0 OP MAX1) and then
2191 : : // figure the smallest and largest values to form the new range.
2192 : :
2193 : : void
2194 : 12750129 : cross_product_operator::wi_cross_product (irange &r, tree type,
2195 : : const wide_int &lh_lb,
2196 : : const wide_int &lh_ub,
2197 : : const wide_int &rh_lb,
2198 : : const wide_int &rh_ub) const
2199 : : {
2200 : 12750129 : wide_int cp1, cp2, cp3, cp4;
2201 : : // Default to varying.
2202 : 12750129 : r.set_varying (type);
2203 : :
2204 : : // Compute the 4 cross operations, bailing if we get an overflow we
2205 : : // can't handle.
2206 : 12750129 : if (wi_op_overflows (cp1, type, lh_lb, rh_lb))
2207 : : return;
2208 : 12750127 : if (wi::eq_p (lh_lb, lh_ub))
2209 : 3672401 : cp3 = cp1;
2210 : 9077726 : else if (wi_op_overflows (cp3, type, lh_ub, rh_lb))
2211 : : return;
2212 : 12750127 : if (wi::eq_p (rh_lb, rh_ub))
2213 : 9862830 : cp2 = cp1;
2214 : 2887297 : else if (wi_op_overflows (cp2, type, lh_lb, rh_ub))
2215 : : return;
2216 : 12748069 : if (wi::eq_p (lh_lb, lh_ub))
2217 : 3672367 : cp4 = cp2;
2218 : 9075702 : else if (wi_op_overflows (cp4, type, lh_ub, rh_ub))
2219 : : return;
2220 : :
2221 : : // Order pairs.
2222 : 12748069 : signop sign = TYPE_SIGN (type);
2223 : 12748069 : if (wi::gt_p (cp1, cp2, sign))
2224 : 1279970 : std::swap (cp1, cp2);
2225 : 12748069 : if (wi::gt_p (cp3, cp4, sign))
2226 : 1261388 : std::swap (cp3, cp4);
2227 : :
2228 : : // Choose min and max from the ordered pairs.
2229 : 12748069 : wide_int res_lb = wi::min (cp1, cp3, sign);
2230 : 12748069 : wide_int res_ub = wi::max (cp2, cp4, sign);
2231 : 12748069 : value_range_with_overflow (r, type, res_lb, res_ub);
2232 : 12751559 : }
2233 : :
2234 : :
2235 : : void
2236 : 12390752 : operator_mult::update_bitmask (irange &r, const irange &lh,
2237 : : const irange &rh) const
2238 : : {
2239 : 12390752 : update_known_bitmask (r, MULT_EXPR, lh, rh);
2240 : 12390752 : }
2241 : :
2242 : : bool
2243 : 1023857 : operator_mult::op1_range (irange &r, tree type,
2244 : : const irange &lhs, const irange &op2,
2245 : : relation_trio) const
2246 : : {
2247 : 1023857 : if (lhs.undefined_p ())
2248 : : return false;
2249 : :
2250 : : // We can't solve 0 = OP1 * N by dividing by N with a wrapping type.
2251 : : // For example: For 0 = OP1 * 2, OP1 could be 0, or MAXINT, whereas
2252 : : // for 4 = OP1 * 2, OP1 could be 2 or 130 (unsigned 8-bit)
2253 : 1023857 : if (TYPE_OVERFLOW_WRAPS (type))
2254 : : return false;
2255 : :
2256 : 293730 : wide_int offset;
2257 : 293730 : if (op2.singleton_p (offset) && offset != 0)
2258 : 210265 : return range_op_handler (TRUNC_DIV_EXPR).fold_range (r, type, lhs, op2);
2259 : :
2260 : : // ~[0, 0] = op1 * op2 defines op1 and op2 as non-zero.
2261 : 83465 : if (!lhs.contains_p (wi::zero (TYPE_PRECISION (lhs.type ()))))
2262 : : {
2263 : 20430 : r.set_nonzero (type);
2264 : 20430 : return true;
2265 : : }
2266 : : return false;
2267 : 293730 : }
2268 : :
2269 : : bool
2270 : 104316 : operator_mult::op2_range (irange &r, tree type,
2271 : : const irange &lhs, const irange &op1,
2272 : : relation_trio rel) const
2273 : : {
2274 : 104316 : return operator_mult::op1_range (r, type, lhs, op1, rel.swap_op1_op2 ());
2275 : : }
2276 : :
2277 : : bool
2278 : 12497462 : operator_mult::wi_op_overflows (wide_int &res, tree type,
2279 : : const wide_int &w0, const wide_int &w1) const
2280 : : {
2281 : 12497462 : wi::overflow_type overflow = wi::OVF_NONE;
2282 : 12497462 : signop sign = TYPE_SIGN (type);
2283 : 12497462 : res = wi::mul (w0, w1, sign, &overflow);
2284 : 12497462 : if (overflow && TYPE_OVERFLOW_UNDEFINED (type))
2285 : : {
2286 : : // For multiplication, the sign of the overflow is given
2287 : : // by the comparison of the signs of the operands.
2288 : 5847995 : if (sign == UNSIGNED || w0.sign_mask () == w1.sign_mask ())
2289 : 3223099 : res = wi::max_value (w0.get_precision (), sign);
2290 : : else
2291 : 2625057 : res = wi::min_value (w0.get_precision (), sign);
2292 : 5847995 : return false;
2293 : : }
2294 : 6649467 : return overflow;
2295 : : }
2296 : :
2297 : : void
2298 : 15574359 : operator_mult::wi_fold (irange &r, tree type,
2299 : : const wide_int &lh_lb, const wide_int &lh_ub,
2300 : : const wide_int &rh_lb, const wide_int &rh_ub) const
2301 : : {
2302 : 15574359 : if (TYPE_OVERFLOW_UNDEFINED (type))
2303 : : {
2304 : 5236735 : wi_cross_product (r, type, lh_lb, lh_ub, rh_lb, rh_ub);
2305 : 5236735 : return;
2306 : : }
2307 : :
2308 : : // Multiply the ranges when overflow wraps. This is basically fancy
2309 : : // code so we don't drop to varying with an unsigned
2310 : : // [-3,-1]*[-3,-1].
2311 : : //
2312 : : // This test requires 2*prec bits if both operands are signed and
2313 : : // 2*prec + 2 bits if either is not. Therefore, extend the values
2314 : : // using the sign of the result to PREC2. From here on out,
2315 : : // everything is just signed math no matter what the input types
2316 : : // were.
2317 : :
2318 : 10337624 : signop sign = TYPE_SIGN (type);
2319 : 10337624 : unsigned prec = TYPE_PRECISION (type);
2320 : 10337624 : widest2_int min0 = widest2_int::from (lh_lb, sign);
2321 : 10337624 : widest2_int max0 = widest2_int::from (lh_ub, sign);
2322 : 10337624 : widest2_int min1 = widest2_int::from (rh_lb, sign);
2323 : 10337624 : widest2_int max1 = widest2_int::from (rh_ub, sign);
2324 : 10337624 : widest2_int sizem1 = wi::mask <widest2_int> (prec, false);
2325 : 10337624 : widest2_int size = sizem1 + 1;
2326 : :
2327 : : // Canonicalize the intervals.
2328 : 10337624 : if (sign == UNSIGNED)
2329 : : {
2330 : 9747861 : if (wi::ltu_p (size, min0 + max0))
2331 : : {
2332 : 1406293 : min0 -= size;
2333 : 1406293 : max0 -= size;
2334 : : }
2335 : 9747829 : if (wi::ltu_p (size, min1 + max1))
2336 : : {
2337 : 133605 : min1 -= size;
2338 : 133605 : max1 -= size;
2339 : : }
2340 : : }
2341 : :
2342 : : // Sort the 4 products so that min is in prod0 and max is in
2343 : : // prod3.
2344 : 10337624 : widest2_int prod0 = min0 * min1;
2345 : 10337624 : widest2_int prod1 = min0 * max1;
2346 : 10337624 : widest2_int prod2 = max0 * min1;
2347 : 10337624 : widest2_int prod3 = max0 * max1;
2348 : :
2349 : : // min0min1 > max0max1
2350 : 10337624 : if (prod0 > prod3)
2351 : 164862 : std::swap (prod0, prod3);
2352 : :
2353 : : // min0max1 > max0min1
2354 : 10337624 : if (prod1 > prod2)
2355 : 261280 : std::swap (prod1, prod2);
2356 : :
2357 : 10337624 : if (prod0 > prod1)
2358 : 73302 : std::swap (prod0, prod1);
2359 : :
2360 : 10337624 : if (prod2 > prod3)
2361 : 3372 : std::swap (prod2, prod3);
2362 : :
2363 : : // diff = max - min
2364 : 10337624 : prod2 = prod3 - prod0;
2365 : 10337624 : if (wi::geu_p (prod2, sizem1))
2366 : : {
2367 : : // Multiplying by X, where X is a power of 2 is [0,0][X,+INF].
2368 : 7158705 : if (TYPE_UNSIGNED (type) && rh_lb == rh_ub
2369 : 6638364 : && wi::exact_log2 (rh_lb) != -1 && prec > 1)
2370 : : {
2371 : 2498032 : r.set (type, rh_lb, wi::max_value (prec, sign));
2372 : 2498032 : int_range<2> zero;
2373 : 2498032 : zero.set_zero (type);
2374 : 2498032 : r.union_ (zero);
2375 : 2498032 : }
2376 : : else
2377 : : // The range covers all values.
2378 : 1145299 : r.set_varying (type);
2379 : : }
2380 : : else
2381 : : {
2382 : 6694293 : wide_int new_lb = wide_int::from (prod0, prec, sign);
2383 : 6694293 : wide_int new_ub = wide_int::from (prod3, prec, sign);
2384 : 6694293 : create_possibly_reversed_range (r, type, new_lb, new_ub);
2385 : 6694336 : }
2386 : 10338195 : }
2387 : :
2388 : : class operator_widen_mult_signed : public range_operator
2389 : : {
2390 : : public:
2391 : : virtual void wi_fold (irange &r, tree type,
2392 : : const wide_int &lh_lb,
2393 : : const wide_int &lh_ub,
2394 : : const wide_int &rh_lb,
2395 : : const wide_int &rh_ub)
2396 : : const;
2397 : : } op_widen_mult_signed;
2398 : :
2399 : : void
2400 : 155 : operator_widen_mult_signed::wi_fold (irange &r, tree type,
2401 : : const wide_int &lh_lb,
2402 : : const wide_int &lh_ub,
2403 : : const wide_int &rh_lb,
2404 : : const wide_int &rh_ub) const
2405 : : {
2406 : 155 : signop s = TYPE_SIGN (type);
2407 : :
2408 : 155 : wide_int lh_wlb = wide_int::from (lh_lb, wi::get_precision (lh_lb) * 2, SIGNED);
2409 : 155 : wide_int lh_wub = wide_int::from (lh_ub, wi::get_precision (lh_ub) * 2, SIGNED);
2410 : 155 : wide_int rh_wlb = wide_int::from (rh_lb, wi::get_precision (rh_lb) * 2, s);
2411 : 155 : wide_int rh_wub = wide_int::from (rh_ub, wi::get_precision (rh_ub) * 2, s);
2412 : :
2413 : : /* We don't expect a widening multiplication to be able to overflow but range
2414 : : calculations for multiplications are complicated. After widening the
2415 : : operands lets call the base class. */
2416 : 155 : return op_mult.wi_fold (r, type, lh_wlb, lh_wub, rh_wlb, rh_wub);
2417 : 155 : }
2418 : :
2419 : :
2420 : : class operator_widen_mult_unsigned : public range_operator
2421 : : {
2422 : : public:
2423 : : virtual void 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)
2428 : : const;
2429 : : } op_widen_mult_unsigned;
2430 : :
2431 : : void
2432 : 4266 : operator_widen_mult_unsigned::wi_fold (irange &r, tree type,
2433 : : const wide_int &lh_lb,
2434 : : const wide_int &lh_ub,
2435 : : const wide_int &rh_lb,
2436 : : const wide_int &rh_ub) const
2437 : : {
2438 : 4266 : signop s = TYPE_SIGN (type);
2439 : :
2440 : 4266 : wide_int lh_wlb = wide_int::from (lh_lb, wi::get_precision (lh_lb) * 2, UNSIGNED);
2441 : 4266 : wide_int lh_wub = wide_int::from (lh_ub, wi::get_precision (lh_ub) * 2, UNSIGNED);
2442 : 4266 : wide_int rh_wlb = wide_int::from (rh_lb, wi::get_precision (rh_lb) * 2, s);
2443 : 4266 : wide_int rh_wub = wide_int::from (rh_ub, wi::get_precision (rh_ub) * 2, s);
2444 : :
2445 : : /* We don't expect a widening multiplication to be able to overflow but range
2446 : : calculations for multiplications are complicated. After widening the
2447 : : operands lets call the base class. */
2448 : 4266 : return op_mult.wi_fold (r, type, lh_wlb, lh_wub, rh_wlb, rh_wub);
2449 : 4266 : }
2450 : :
2451 : : class operator_div : public cross_product_operator
2452 : : {
2453 : : using range_operator::update_bitmask;
2454 : : using range_operator::op2_range;
2455 : : public:
2456 : : operator_div (tree_code div_kind) { m_code = div_kind; }
2457 : : bool op2_range (irange &r, tree type, const irange &lhs, const irange &,
2458 : : relation_trio) const final override;
2459 : : virtual void wi_fold (irange &r, tree type,
2460 : : const wide_int &lh_lb,
2461 : : const wide_int &lh_ub,
2462 : : const wide_int &rh_lb,
2463 : : const wide_int &rh_ub) const final override;
2464 : : virtual bool wi_op_overflows (wide_int &res, tree type,
2465 : : const wide_int &, const wide_int &)
2466 : : const final override;
2467 : 2533143 : void update_bitmask (irange &r, const irange &lh, const irange &rh)
2468 : : const final override
2469 : 2533143 : { update_known_bitmask (r, m_code, lh, rh); }
2470 : : protected:
2471 : : tree_code m_code;
2472 : : };
2473 : :
2474 : : static operator_div op_trunc_div (TRUNC_DIV_EXPR);
2475 : : static operator_div op_floor_div (FLOOR_DIV_EXPR);
2476 : : static operator_div op_round_div (ROUND_DIV_EXPR);
2477 : : static operator_div op_ceil_div (CEIL_DIV_EXPR);
2478 : :
2479 : : // Set OP2 to non-zero if the LHS isn't UNDEFINED.
2480 : : bool
2481 : 34113 : operator_div::op2_range (irange &r, tree type, const irange &lhs,
2482 : : const irange &, relation_trio) const
2483 : : {
2484 : 34113 : if (!lhs.undefined_p ())
2485 : : {
2486 : 34113 : r.set_nonzero (type);
2487 : 34113 : return true;
2488 : : }
2489 : : return false;
2490 : : }
2491 : :
2492 : : bool
2493 : 10797847 : operator_div::wi_op_overflows (wide_int &res, tree type,
2494 : : const wide_int &w0, const wide_int &w1) const
2495 : : {
2496 : 10797847 : if (w1 == 0)
2497 : : return true;
2498 : :
2499 : 10797847 : wi::overflow_type overflow = wi::OVF_NONE;
2500 : 10797847 : signop sign = TYPE_SIGN (type);
2501 : :
2502 : 10797847 : switch (m_code)
2503 : : {
2504 : 10699653 : case EXACT_DIV_EXPR:
2505 : 10699653 : case TRUNC_DIV_EXPR:
2506 : 10699653 : res = wi::div_trunc (w0, w1, sign, &overflow);
2507 : 10699653 : break;
2508 : 89021 : case FLOOR_DIV_EXPR:
2509 : 89021 : res = wi::div_floor (w0, w1, sign, &overflow);
2510 : 89021 : break;
2511 : 0 : case ROUND_DIV_EXPR:
2512 : 0 : res = wi::div_round (w0, w1, sign, &overflow);
2513 : 0 : break;
2514 : 9173 : case CEIL_DIV_EXPR:
2515 : 9173 : res = wi::div_ceil (w0, w1, sign, &overflow);
2516 : 9173 : break;
2517 : 0 : default:
2518 : 0 : gcc_unreachable ();
2519 : : }
2520 : :
2521 : 10797847 : if (overflow && TYPE_OVERFLOW_UNDEFINED (type))
2522 : : {
2523 : : // For division, the only case is -INF / -1 = +INF.
2524 : 176239 : res = wi::max_value (w0.get_precision (), sign);
2525 : 176239 : return false;
2526 : : }
2527 : 10621608 : return overflow;
2528 : : }
2529 : :
2530 : : void
2531 : 3421418 : operator_div::wi_fold (irange &r, tree type,
2532 : : const wide_int &lh_lb, const wide_int &lh_ub,
2533 : : const wide_int &rh_lb, const wide_int &rh_ub) const
2534 : : {
2535 : 3421418 : const wide_int dividend_min = lh_lb;
2536 : 3421418 : const wide_int dividend_max = lh_ub;
2537 : 3421418 : const wide_int divisor_min = rh_lb;
2538 : 3421418 : const wide_int divisor_max = rh_ub;
2539 : 3421418 : signop sign = TYPE_SIGN (type);
2540 : 3421418 : unsigned prec = TYPE_PRECISION (type);
2541 : 3421418 : wide_int extra_min, extra_max;
2542 : :
2543 : : // If we know we won't divide by zero, just do the division.
2544 : 3421418 : if (!wi_includes_zero_p (type, divisor_min, divisor_max))
2545 : : {
2546 : 2834727 : wi_cross_product (r, type, dividend_min, dividend_max,
2547 : : divisor_min, divisor_max);
2548 : 2834727 : return;
2549 : : }
2550 : :
2551 : : // If we're definitely dividing by zero, there's nothing to do.
2552 : 586691 : if (wi_zero_p (type, divisor_min, divisor_max))
2553 : : {
2554 : 8195 : r.set_undefined ();
2555 : 8195 : return;
2556 : : }
2557 : :
2558 : : // Perform the division in 2 parts, [LB, -1] and [1, UB], which will
2559 : : // skip any division by zero.
2560 : :
2561 : : // First divide by the negative numbers, if any.
2562 : 578496 : if (wi::neg_p (divisor_min, sign))
2563 : 728446 : wi_cross_product (r, type, dividend_min, dividend_max,
2564 : 728446 : divisor_min, wi::minus_one (prec));
2565 : : else
2566 : 214273 : r.set_undefined ();
2567 : :
2568 : : // Then divide by the non-zero positive numbers, if any.
2569 : 578496 : if (wi::gt_p (divisor_max, wi::zero (prec), sign))
2570 : : {
2571 : 577844 : int_range_max tmp;
2572 : 1155688 : wi_cross_product (tmp, type, dividend_min, dividend_max,
2573 : 577844 : wi::one (prec), divisor_max);
2574 : 577844 : r.union_ (tmp);
2575 : 577844 : }
2576 : : // We shouldn't still have undefined here.
2577 : 578496 : gcc_checking_assert (!r.undefined_p ());
2578 : 3422030 : }
2579 : :
2580 : :
2581 : : class operator_exact_divide : public operator_div
2582 : : {
2583 : : using range_operator::op1_range;
2584 : : public:
2585 : : operator_exact_divide () : operator_div (EXACT_DIV_EXPR) { }
2586 : : virtual bool op1_range (irange &r, tree type,
2587 : : const irange &lhs,
2588 : : const irange &op2,
2589 : : relation_trio) const;
2590 : :
2591 : : } op_exact_div;
2592 : :
2593 : : bool
2594 : 445901 : operator_exact_divide::op1_range (irange &r, tree type,
2595 : : const irange &lhs,
2596 : : const irange &op2,
2597 : : relation_trio) const
2598 : : {
2599 : 445901 : if (lhs.undefined_p ())
2600 : : return false;
2601 : 445901 : wide_int offset;
2602 : : // [2, 4] = op1 / [3,3] since its exact divide, no need to worry about
2603 : : // remainders in the endpoints, so op1 = [2,4] * [3,3] = [6,12].
2604 : : // We wont bother trying to enumerate all the in between stuff :-P
2605 : : // TRUE accuracy is [6,6][9,9][12,12]. This is unlikely to matter most of
2606 : : // the time however.
2607 : : // If op2 is a multiple of 2, we would be able to set some non-zero bits.
2608 : 445901 : if (op2.singleton_p (offset) && offset != 0)
2609 : 445901 : return range_op_handler (MULT_EXPR).fold_range (r, type, lhs, op2);
2610 : : return false;
2611 : 445901 : }
2612 : :
2613 : :
2614 : : class operator_lshift : public cross_product_operator
2615 : : {
2616 : : using range_operator::fold_range;
2617 : : using range_operator::op1_range;
2618 : : using range_operator::update_bitmask;
2619 : : public:
2620 : : virtual bool op1_range (irange &r, tree type, const irange &lhs,
2621 : : const irange &op2, relation_trio rel = TRIO_VARYING)
2622 : : const final override;
2623 : : virtual bool fold_range (irange &r, tree type, const irange &op1,
2624 : : const irange &op2, relation_trio rel = TRIO_VARYING)
2625 : : const final override;
2626 : :
2627 : : virtual void wi_fold (irange &r, tree type,
2628 : : const wide_int &lh_lb, const wide_int &lh_ub,
2629 : : const wide_int &rh_lb,
2630 : : const wide_int &rh_ub) const final override;
2631 : : virtual bool wi_op_overflows (wide_int &res,
2632 : : tree type,
2633 : : const wide_int &,
2634 : : const wide_int &) const final override;
2635 : 444054 : void update_bitmask (irange &r, const irange &lh,
2636 : : const irange &rh) const final override
2637 : 444054 : { update_known_bitmask (r, LSHIFT_EXPR, lh, rh); }
2638 : : // Check compatibility of LHS and op1.
2639 : 1023462 : bool operand_check_p (tree t1, tree t2, tree) const final override
2640 : 1023462 : { return range_compatible_p (t1, t2); }
2641 : : } op_lshift;
2642 : :
2643 : : class operator_rshift : public cross_product_operator
2644 : : {
2645 : : using range_operator::fold_range;
2646 : : using range_operator::op1_range;
2647 : : using range_operator::lhs_op1_relation;
2648 : : using range_operator::update_bitmask;
2649 : : public:
2650 : : virtual bool fold_range (irange &r, tree type, const irange &op1,
2651 : : const irange &op2, relation_trio rel = TRIO_VARYING)
2652 : : const final override;
2653 : : virtual void wi_fold (irange &r, tree type,
2654 : : const wide_int &lh_lb,
2655 : : const wide_int &lh_ub,
2656 : : const wide_int &rh_lb,
2657 : : const wide_int &rh_ub) const final override;
2658 : : virtual bool wi_op_overflows (wide_int &res,
2659 : : tree type,
2660 : : const wide_int &w0,
2661 : : const wide_int &w1) const final override;
2662 : : virtual bool op1_range (irange &, tree type, const irange &lhs,
2663 : : const irange &op2, relation_trio rel = TRIO_VARYING)
2664 : : const final override;
2665 : : virtual relation_kind lhs_op1_relation (const irange &lhs, const irange &op1,
2666 : : const irange &op2, relation_kind rel)
2667 : : const final override;
2668 : 3012414 : void update_bitmask (irange &r, const irange &lh,
2669 : : const irange &rh) const final override
2670 : 3012414 : { update_known_bitmask (r, RSHIFT_EXPR, lh, rh); }
2671 : : // Check compatibility of LHS and op1.
2672 : 3097905 : bool operand_check_p (tree t1, tree t2, tree) const final override
2673 : 3097905 : { return range_compatible_p (t1, t2); }
2674 : : } op_rshift;
2675 : :
2676 : :
2677 : : relation_kind
2678 : 2177548 : operator_rshift::lhs_op1_relation (const irange &lhs ATTRIBUTE_UNUSED,
2679 : : const irange &op1,
2680 : : const irange &op2,
2681 : : relation_kind) const
2682 : : {
2683 : : // If both operands range are >= 0, then the LHS <= op1.
2684 : 2177548 : if (!op1.undefined_p () && !op2.undefined_p ()
2685 : 4354291 : && wi::ge_p (op1.lower_bound (), 0, TYPE_SIGN (op1.type ()))
2686 : 6326645 : && wi::ge_p (op2.lower_bound (), 0, TYPE_SIGN (op2.type ())))
2687 : 1947817 : return VREL_LE;
2688 : : return VREL_VARYING;
2689 : : }
2690 : :
2691 : : bool
2692 : 1500513 : operator_lshift::fold_range (irange &r, tree type,
2693 : : const irange &op1,
2694 : : const irange &op2,
2695 : : relation_trio rel) const
2696 : : {
2697 : 1500513 : int_range_max shift_range;
2698 : 1500513 : if (!get_shift_range (shift_range, type, op2))
2699 : : {
2700 : 521 : if (op2.undefined_p ())
2701 : 228 : r.set_undefined ();
2702 : : else
2703 : 293 : r.set_zero (type);
2704 : 521 : return true;
2705 : : }
2706 : :
2707 : : // Transform left shifts by constants into multiplies.
2708 : 1499992 : if (shift_range.singleton_p ())
2709 : : {
2710 : 1055911 : unsigned shift = shift_range.lower_bound ().to_uhwi ();
2711 : 1055911 : wide_int tmp = wi::set_bit_in_zero (shift, TYPE_PRECISION (type));
2712 : 1055911 : int_range<1> mult (type, tmp, tmp);
2713 : :
2714 : : // Force wrapping multiplication.
2715 : 1055911 : bool saved_flag_wrapv = flag_wrapv;
2716 : 1055911 : bool saved_flag_wrapv_pointer = flag_wrapv_pointer;
2717 : 1055911 : flag_wrapv = 1;
2718 : 1055911 : flag_wrapv_pointer = 1;
2719 : 1055911 : bool b = op_mult.fold_range (r, type, op1, mult);
2720 : 1055911 : flag_wrapv = saved_flag_wrapv;
2721 : 1055911 : flag_wrapv_pointer = saved_flag_wrapv_pointer;
2722 : 1055911 : return b;
2723 : 1055920 : }
2724 : : else
2725 : : // Otherwise, invoke the generic fold routine.
2726 : 444081 : return range_operator::fold_range (r, type, op1, shift_range, rel);
2727 : 1500513 : }
2728 : :
2729 : : void
2730 : 524177 : operator_lshift::wi_fold (irange &r, tree type,
2731 : : const wide_int &lh_lb, const wide_int &lh_ub,
2732 : : const wide_int &rh_lb, const wide_int &rh_ub) const
2733 : : {
2734 : 524177 : signop sign = TYPE_SIGN (type);
2735 : 524177 : unsigned prec = TYPE_PRECISION (type);
2736 : 524177 : int overflow_pos = sign == SIGNED ? prec - 1 : prec;
2737 : 524177 : int bound_shift = overflow_pos - rh_ub.to_shwi ();
2738 : : // If bound_shift == HOST_BITS_PER_WIDE_INT, the llshift can
2739 : : // overflow. However, for that to happen, rh.max needs to be zero,
2740 : : // which means rh is a singleton range of zero, which means we simply return
2741 : : // [lh_lb, lh_ub] as the range.
2742 : 524177 : if (wi::eq_p (rh_ub, rh_lb) && wi::eq_p (rh_ub, 0))
2743 : : {
2744 : 21844 : r = int_range<2> (type, lh_lb, lh_ub);
2745 : 21844 : return;
2746 : : }
2747 : :
2748 : 502333 : wide_int bound = wi::set_bit_in_zero (bound_shift, prec);
2749 : 502333 : wide_int complement = ~(bound - 1);
2750 : 502333 : wide_int low_bound, high_bound;
2751 : 502333 : bool in_bounds = false;
2752 : :
2753 : 502333 : if (sign == UNSIGNED)
2754 : : {
2755 : 246616 : low_bound = bound;
2756 : 246616 : high_bound = complement;
2757 : 246616 : if (wi::ltu_p (lh_ub, low_bound))
2758 : : {
2759 : : // [5, 6] << [1, 2] == [10, 24].
2760 : : // We're shifting out only zeroes, the value increases
2761 : : // monotonically.
2762 : : in_bounds = true;
2763 : : }
2764 : 77757 : else if (wi::ltu_p (high_bound, lh_lb))
2765 : : {
2766 : : // [0xffffff00, 0xffffffff] << [1, 2]
2767 : : // == [0xfffffc00, 0xfffffffe].
2768 : : // We're shifting out only ones, the value decreases
2769 : : // monotonically.
2770 : : in_bounds = true;
2771 : : }
2772 : : }
2773 : : else
2774 : : {
2775 : : // [-1, 1] << [1, 2] == [-4, 4]
2776 : 255717 : low_bound = complement;
2777 : 255717 : high_bound = bound;
2778 : 255717 : if (wi::lts_p (lh_ub, high_bound)
2779 : 255717 : && wi::lts_p (low_bound, lh_lb))
2780 : : {
2781 : : // For non-negative numbers, we're shifting out only zeroes,
2782 : : // the value increases monotonically. For negative numbers,
2783 : : // we're shifting out only ones, the value decreases
2784 : : // monotonically.
2785 : : in_bounds = true;
2786 : : }
2787 : : }
2788 : :
2789 : : if (in_bounds)
2790 : 301916 : wi_cross_product (r, type, lh_lb, lh_ub, rh_lb, rh_ub);
2791 : : else
2792 : 200417 : r.set_varying (type);
2793 : 502342 : }
2794 : :
2795 : : bool
2796 : 583767 : operator_lshift::wi_op_overflows (wide_int &res, tree type,
2797 : : const wide_int &w0, const wide_int &w1) const
2798 : : {
2799 : 583767 : signop sign = TYPE_SIGN (type);
2800 : 583767 : if (wi::neg_p (w1))
2801 : : {
2802 : : // It's unclear from the C standard whether shifts can overflow.
2803 : : // The following code ignores overflow; perhaps a C standard
2804 : : // interpretation ruling is needed.
2805 : 0 : res = wi::rshift (w0, -w1, sign);
2806 : : }
2807 : : else
2808 : 583767 : res = wi::lshift (w0, w1);
2809 : 583767 : return false;
2810 : : }
2811 : :
2812 : : bool
2813 : 43505 : operator_lshift::op1_range (irange &r,
2814 : : tree type,
2815 : : const irange &lhs,
2816 : : const irange &op2,
2817 : : relation_trio) const
2818 : : {
2819 : 43505 : if (lhs.undefined_p ())
2820 : : return false;
2821 : :
2822 : 43505 : if (!contains_zero_p (lhs))
2823 : 21001 : r.set_nonzero (type);
2824 : : else
2825 : 22504 : r.set_varying (type);
2826 : :
2827 : 43505 : wide_int shift;
2828 : 43505 : if (op2.singleton_p (shift))
2829 : : {
2830 : 38555 : if (wi::lt_p (shift, 0, SIGNED))
2831 : : return false;
2832 : 38555 : if (wi::ge_p (shift, wi::uhwi (TYPE_PRECISION (type),
2833 : 38555 : TYPE_PRECISION (op2.type ())),
2834 : : UNSIGNED))
2835 : : return false;
2836 : 38555 : if (shift == 0)
2837 : : {
2838 : 6 : r.intersect (lhs);
2839 : 6 : return true;
2840 : : }
2841 : :
2842 : : // Work completely in unsigned mode to start.
2843 : 38549 : tree utype = type;
2844 : 38549 : int_range_max tmp_range;
2845 : 38549 : if (TYPE_SIGN (type) == SIGNED)
2846 : : {
2847 : 7083 : int_range_max tmp = lhs;
2848 : 7083 : utype = unsigned_type_for (type);
2849 : 7083 : range_cast (tmp, utype);
2850 : 7083 : op_rshift.fold_range (tmp_range, utype, tmp, op2);
2851 : 7083 : }
2852 : : else
2853 : 31466 : op_rshift.fold_range (tmp_range, utype, lhs, op2);
2854 : :
2855 : : // Start with ranges which can produce the LHS by right shifting the
2856 : : // result by the shift amount.
2857 : : // ie [0x08, 0xF0] = op1 << 2 will start with
2858 : : // [00001000, 11110000] = op1 << 2
2859 : : // [0x02, 0x4C] aka [00000010, 00111100]
2860 : :
2861 : : // Then create a range from the LB with the least significant upper bit
2862 : : // set, to the upper bound with all the bits set.
2863 : : // This would be [0x42, 0xFC] aka [01000010, 11111100].
2864 : :
2865 : : // Ideally we do this for each subrange, but just lump them all for now.
2866 : 38549 : unsigned low_bits = TYPE_PRECISION (utype) - shift.to_uhwi ();
2867 : 38549 : wide_int up_mask = wi::mask (low_bits, true, TYPE_PRECISION (utype));
2868 : 38549 : wide_int new_ub = wi::bit_or (up_mask, tmp_range.upper_bound ());
2869 : 38549 : wide_int new_lb = wi::set_bit (tmp_range.lower_bound (), low_bits);
2870 : 38549 : int_range<2> fill_range (utype, new_lb, new_ub);
2871 : 38549 : tmp_range.union_ (fill_range);
2872 : :
2873 : 38549 : if (utype != type)
2874 : 7083 : range_cast (tmp_range, type);
2875 : :
2876 : 38549 : r.intersect (tmp_range);
2877 : 38549 : return true;
2878 : 38549 : }
2879 : :
2880 : 4950 : return !r.varying_p ();
2881 : 43505 : }
2882 : :
2883 : : bool
2884 : 745521 : operator_rshift::op1_range (irange &r,
2885 : : tree type,
2886 : : const irange &lhs,
2887 : : const irange &op2,
2888 : : relation_trio) const
2889 : : {
2890 : 745521 : if (lhs.undefined_p ())
2891 : : return false;
2892 : 745521 : wide_int shift;
2893 : 745521 : if (op2.singleton_p (shift))
2894 : : {
2895 : : // Ignore nonsensical shifts.
2896 : 722707 : unsigned prec = TYPE_PRECISION (type);
2897 : 1445414 : if (wi::ge_p (shift,
2898 : 722707 : wi::uhwi (prec, TYPE_PRECISION (op2.type ())),
2899 : : UNSIGNED))
2900 : : return false;
2901 : 722707 : if (shift == 0)
2902 : : {
2903 : 75 : r = lhs;
2904 : 75 : return true;
2905 : : }
2906 : :
2907 : : // Folding the original operation may discard some impossible
2908 : : // ranges from the LHS.
2909 : 722632 : int_range_max lhs_refined;
2910 : 722632 : op_rshift.fold_range (lhs_refined, type, int_range<1> (type), op2);
2911 : 722632 : lhs_refined.intersect (lhs);
2912 : 722632 : if (lhs_refined.undefined_p ())
2913 : : {
2914 : 4 : r.set_undefined ();
2915 : 4 : return true;
2916 : : }
2917 : 722628 : int_range_max shift_range (op2.type (), shift, shift);
2918 : 722628 : int_range_max lb, ub;
2919 : 722628 : op_lshift.fold_range (lb, type, lhs_refined, shift_range);
2920 : : // LHS
2921 : : // 0000 0111 = OP1 >> 3
2922 : : //
2923 : : // OP1 is anything from 0011 1000 to 0011 1111. That is, a
2924 : : // range from LHS<<3 plus a mask of the 3 bits we shifted on the
2925 : : // right hand side (0x07).
2926 : 722628 : wide_int mask = wi::mask (shift.to_uhwi (), false, prec);
2927 : 722628 : int_range_max mask_range (type,
2928 : 722628 : wi::zero (TYPE_PRECISION (type)),
2929 : 722628 : mask);
2930 : 722628 : op_plus.fold_range (ub, type, lb, mask_range);
2931 : 722628 : r = lb;
2932 : 722628 : r.union_ (ub);
2933 : 722628 : if (!contains_zero_p (lhs_refined))
2934 : : {
2935 : 405223 : mask_range.invert ();
2936 : 405223 : r.intersect (mask_range);
2937 : : }
2938 : 722628 : return true;
2939 : 722632 : }
2940 : : return false;
2941 : 745521 : }
2942 : :
2943 : : bool
2944 : 9911778 : operator_rshift::wi_op_overflows (wide_int &res,
2945 : : tree type,
2946 : : const wide_int &w0,
2947 : : const wide_int &w1) const
2948 : : {
2949 : 9911778 : signop sign = TYPE_SIGN (type);
2950 : 9911778 : if (wi::neg_p (w1))
2951 : 0 : res = wi::lshift (w0, -w1);
2952 : : else
2953 : : {
2954 : : // It's unclear from the C standard whether shifts can overflow.
2955 : : // The following code ignores overflow; perhaps a C standard
2956 : : // interpretation ruling is needed.
2957 : 9911860 : res = wi::rshift (w0, w1, sign);
2958 : : }
2959 : 9911778 : return false;
2960 : : }
2961 : :
2962 : : bool
2963 : 3013623 : operator_rshift::fold_range (irange &r, tree type,
2964 : : const irange &op1,
2965 : : const irange &op2,
2966 : : relation_trio rel) const
2967 : : {
2968 : 3013623 : int_range_max shift;
2969 : 3013623 : if (!get_shift_range (shift, type, op2))
2970 : : {
2971 : 573 : if (op2.undefined_p ())
2972 : 186 : r.set_undefined ();
2973 : : else
2974 : 387 : r.set_zero (type);
2975 : 573 : return true;
2976 : : }
2977 : :
2978 : 3013050 : return range_operator::fold_range (r, type, op1, shift, rel);
2979 : 3013623 : }
2980 : :
2981 : : void
2982 : 3434684 : operator_rshift::wi_fold (irange &r, tree type,
2983 : : const wide_int &lh_lb, const wide_int &lh_ub,
2984 : : const wide_int &rh_lb, const wide_int &rh_ub) const
2985 : : {
2986 : 3434684 : wi_cross_product (r, type, lh_lb, lh_ub, rh_lb, rh_ub);
2987 : 3434684 : }
2988 : :
2989 : :
2990 : : // Add a partial equivalence between the LHS and op1 for casts.
2991 : :
2992 : : relation_kind
2993 : 21487327 : operator_cast::lhs_op1_relation (const irange &lhs,
2994 : : const irange &op1,
2995 : : const irange &op2 ATTRIBUTE_UNUSED,
2996 : : relation_kind) const
2997 : : {
2998 : 21487327 : if (lhs.undefined_p () || op1.undefined_p ())
2999 : : return VREL_VARYING;
3000 : 21468141 : unsigned lhs_prec = TYPE_PRECISION (lhs.type ());
3001 : 21468141 : unsigned op1_prec = TYPE_PRECISION (op1.type ());
3002 : : // If the result gets sign extended into a larger type check first if this
3003 : : // qualifies as a partial equivalence.
3004 : 21468141 : if (TYPE_SIGN (op1.type ()) == SIGNED && lhs_prec > op1_prec)
3005 : : {
3006 : : // If the result is sign extended, and the LHS is larger than op1,
3007 : : // check if op1's range can be negative as the sign extension will
3008 : : // cause the upper bits to be 1 instead of 0, invalidating the PE.
3009 : 3268900 : int_range<3> negs = range_negatives (op1.type ());
3010 : 3268900 : negs.intersect (op1);
3011 : 3268900 : if (!negs.undefined_p ())
3012 : 2263668 : return VREL_VARYING;
3013 : 3268900 : }
3014 : :
3015 : 19204473 : unsigned prec = MIN (lhs_prec, op1_prec);
3016 : 19204473 : return bits_to_pe (prec);
3017 : : }
3018 : :
3019 : : // Return TRUE if casting from INNER to OUTER is a truncating cast.
3020 : :
3021 : : inline bool
3022 : 72047711 : operator_cast::truncating_cast_p (const irange &inner,
3023 : : const irange &outer) const
3024 : : {
3025 : 72047711 : return TYPE_PRECISION (outer.type ()) < TYPE_PRECISION (inner.type ());
3026 : : }
3027 : :
3028 : : // Return TRUE if [MIN,MAX] is inside the domain of RANGE's type.
3029 : :
3030 : : bool
3031 : 62419759 : operator_cast::inside_domain_p (const wide_int &min,
3032 : : const wide_int &max,
3033 : : const irange &range) const
3034 : : {
3035 : 62419759 : wide_int domain_min = irange_val_min (range.type ());
3036 : 62419759 : wide_int domain_max = irange_val_max (range.type ());
3037 : 62419759 : signop domain_sign = TYPE_SIGN (range.type ());
3038 : 62419759 : return (wi::le_p (min, domain_max, domain_sign)
3039 : 62419759 : && wi::le_p (max, domain_max, domain_sign)
3040 : 62419759 : && wi::ge_p (min, domain_min, domain_sign)
3041 : 124839518 : && wi::ge_p (max, domain_min, domain_sign));
3042 : 62419759 : }
3043 : :
3044 : :
3045 : : // Helper for fold_range which work on a pair at a time.
3046 : :
3047 : : void
3048 : 65100026 : operator_cast::fold_pair (irange &r, unsigned index,
3049 : : const irange &inner,
3050 : : const irange &outer) const
3051 : : {
3052 : 65100026 : tree inner_type = inner.type ();
3053 : 65100026 : tree outer_type = outer.type ();
3054 : 65100026 : signop inner_sign = TYPE_SIGN (inner_type);
3055 : 65100026 : unsigned outer_prec = TYPE_PRECISION (outer_type);
3056 : :
3057 : : // check to see if casting from INNER to OUTER is a conversion that
3058 : : // fits in the resulting OUTER type.
3059 : 65100026 : wide_int inner_lb = inner.lower_bound (index);
3060 : 65100026 : wide_int inner_ub = inner.upper_bound (index);
3061 : 65100026 : if (truncating_cast_p (inner, outer))
3062 : : {
3063 : : // We may be able to accommodate a truncating cast if the
3064 : : // resulting range can be represented in the target type...
3065 : 12890686 : if (wi::rshift (wi::sub (inner_ub, inner_lb),
3066 : 6445343 : wi::uhwi (outer_prec, TYPE_PRECISION (inner.type ())),
3067 : 19336029 : inner_sign) != 0)
3068 : : {
3069 : 2680267 : r.set_varying (outer_type);
3070 : 2680267 : return;
3071 : : }
3072 : : }
3073 : : // ...but we must still verify that the final range fits in the
3074 : : // domain. This catches -fstrict-enum restrictions where the domain
3075 : : // range is smaller than what fits in the underlying type.
3076 : 62419759 : wide_int min = wide_int::from (inner_lb, outer_prec, inner_sign);
3077 : 62419759 : wide_int max = wide_int::from (inner_ub, outer_prec, inner_sign);
3078 : 62419759 : if (inside_domain_p (min, max, outer))
3079 : 62419759 : create_possibly_reversed_range (r, outer_type, min, max);
3080 : : else
3081 : 0 : r.set_varying (outer_type);
3082 : 65102385 : }
3083 : :
3084 : :
3085 : : bool
3086 : 52735112 : operator_cast::fold_range (irange &r, tree type ATTRIBUTE_UNUSED,
3087 : : const irange &inner,
3088 : : const irange &outer,
3089 : : relation_trio) const
3090 : : {
3091 : 52735112 : if (empty_range_varying (r, type, inner, outer))
3092 : 28332 : return true;
3093 : :
3094 : 52706780 : gcc_checking_assert (outer.varying_p ());
3095 : 52706780 : gcc_checking_assert (inner.num_pairs () > 0);
3096 : :
3097 : : // Avoid a temporary by folding the first pair directly into the result.
3098 : 52706780 : fold_pair (r, 0, inner, outer);
3099 : :
3100 : : // Then process any additional pairs by unioning with their results.
3101 : 64458470 : for (unsigned x = 1; x < inner.num_pairs (); ++x)
3102 : : {
3103 : 12393246 : int_range_max tmp;
3104 : 12393246 : fold_pair (tmp, x, inner, outer);
3105 : 12393246 : r.union_ (tmp);
3106 : 12393246 : if (r.varying_p ())
3107 : 641556 : return true;
3108 : 12393246 : }
3109 : :
3110 : 52065224 : update_bitmask (r, inner, outer);
3111 : 52065224 : return true;
3112 : : }
3113 : :
3114 : : void
3115 : 52065224 : operator_cast::update_bitmask (irange &r, const irange &lh,
3116 : : const irange &rh) const
3117 : : {
3118 : 52065224 : update_known_bitmask (r, CONVERT_EXPR, lh, rh);
3119 : 52065224 : }
3120 : :
3121 : : bool
3122 : 6947685 : operator_cast::op1_range (irange &r, tree type,
3123 : : const irange &lhs,
3124 : : const irange &op2,
3125 : : relation_trio) const
3126 : : {
3127 : 6947685 : if (lhs.undefined_p ())
3128 : : return false;
3129 : 6947685 : tree lhs_type = lhs.type ();
3130 : 6947685 : gcc_checking_assert (types_compatible_p (op2.type(), type));
3131 : :
3132 : : // If we are calculating a pointer, shortcut to what we really care about.
3133 : 6947685 : if (POINTER_TYPE_P (type))
3134 : : {
3135 : : // Conversion from other pointers or a constant (including 0/NULL)
3136 : : // are straightforward.
3137 : 0 : if (POINTER_TYPE_P (lhs.type ())
3138 : 0 : || (lhs.singleton_p ()
3139 : 0 : && TYPE_PRECISION (lhs.type ()) >= TYPE_PRECISION (type)))
3140 : : {
3141 : 0 : r = lhs;
3142 : 0 : range_cast (r, type);
3143 : : }
3144 : : else
3145 : : {
3146 : : // If the LHS is not a pointer nor a singleton, then it is
3147 : : // either VARYING or non-zero.
3148 : 0 : if (!lhs.undefined_p () && !contains_zero_p (lhs))
3149 : 0 : r.set_nonzero (type);
3150 : : else
3151 : 0 : r.set_varying (type);
3152 : : }
3153 : 0 : r.intersect (op2);
3154 : 0 : return true;
3155 : : }
3156 : :
3157 : 6947685 : if (truncating_cast_p (op2, lhs))
3158 : : {
3159 : 1156943 : if (lhs.varying_p ())
3160 : 154420 : r.set_varying (type);
3161 : : else
3162 : : {
3163 : : // We want to insert the LHS as an unsigned value since it
3164 : : // would not trigger the signed bit of the larger type.
3165 : 1002523 : int_range_max converted_lhs = lhs;
3166 : 1002523 : range_cast (converted_lhs, unsigned_type_for (lhs_type));
3167 : 1002523 : range_cast (converted_lhs, type);
3168 : : // Start by building the positive signed outer range for the type.
3169 : 1002523 : wide_int lim = wi::set_bit_in_zero (TYPE_PRECISION (lhs_type),
3170 : 2005046 : TYPE_PRECISION (type));
3171 : 1002523 : create_possibly_reversed_range (r, type, lim,
3172 : 1002523 : wi::max_value (TYPE_PRECISION (type),
3173 : : SIGNED));
3174 : : // For the signed part, we need to simply union the 2 ranges now.
3175 : 1002523 : r.union_ (converted_lhs);
3176 : :
3177 : : // Create maximal negative number outside of LHS bits.
3178 : 1002523 : lim = wi::mask (TYPE_PRECISION (lhs_type), true,
3179 : 2005046 : TYPE_PRECISION (type));
3180 : : // Add this to the unsigned LHS range(s).
3181 : 1002523 : int_range_max lim_range (type, lim, lim);
3182 : 1002523 : int_range_max lhs_neg;
3183 : 1002523 : range_op_handler (PLUS_EXPR).fold_range (lhs_neg, type,
3184 : : converted_lhs, lim_range);
3185 : : // lhs_neg now has all the negative versions of the LHS.
3186 : : // Now union in all the values from SIGNED MIN (0x80000) to
3187 : : // lim-1 in order to fill in all the ranges with the upper
3188 : : // bits set.
3189 : :
3190 : : // PR 97317. If the lhs has only 1 bit less precision than the rhs,
3191 : : // we don't need to create a range from min to lim-1
3192 : : // calculate neg range traps trying to create [lim, lim - 1].
3193 : 1002523 : wide_int min_val = wi::min_value (TYPE_PRECISION (type), SIGNED);
3194 : 1002523 : if (lim != min_val)
3195 : : {
3196 : 1000720 : int_range_max neg (type,
3197 : 2001440 : wi::min_value (TYPE_PRECISION (type),
3198 : : SIGNED),
3199 : 2001440 : lim - 1);
3200 : 1000720 : lhs_neg.union_ (neg);
3201 : 1000720 : }
3202 : : // And finally, munge the signed and unsigned portions.
3203 : 1002523 : r.union_ (lhs_neg);
3204 : 1002523 : }
3205 : : // And intersect with any known value passed in the extra operand.
3206 : 1156943 : r.intersect (op2);
3207 : 1156943 : return true;
3208 : : }
3209 : :
3210 : 5790742 : int_range_max tmp;
3211 : 5790742 : if (TYPE_PRECISION (lhs_type) == TYPE_PRECISION (type))
3212 : 4248060 : tmp = lhs;
3213 : : else
3214 : : {
3215 : : // The cast is not truncating, and the range is restricted to
3216 : : // the range of the RHS by this assignment.
3217 : : //
3218 : : // Cast the range of the RHS to the type of the LHS.
3219 : 1542682 : fold_range (tmp, lhs_type, int_range<1> (type), int_range<1> (lhs_type));
3220 : : // Intersect this with the LHS range will produce the range,
3221 : : // which will be cast to the RHS type before returning.
3222 : 1542682 : tmp.intersect (lhs);
3223 : : }
3224 : :
3225 : : // Cast the calculated range to the type of the RHS.
3226 : 5790742 : fold_range (r, type, tmp, int_range<1> (type));
3227 : 5790742 : return true;
3228 : 5790742 : }
3229 : :
3230 : :
3231 : : class operator_logical_and : public range_operator
3232 : : {
3233 : : using range_operator::fold_range;
3234 : : using range_operator::op1_range;
3235 : : using range_operator::op2_range;
3236 : : public:
3237 : : bool fold_range (irange &r, tree type,
3238 : : const irange &lh,
3239 : : const irange &rh,
3240 : : relation_trio rel = TRIO_VARYING) const final override;
3241 : : bool op1_range (irange &r, tree type,
3242 : : const irange &lhs,
3243 : : const irange &op2,
3244 : : relation_trio rel = TRIO_VARYING) const final override;
3245 : : bool op2_range (irange &r, tree type,
3246 : : const irange &lhs,
3247 : : const irange &op1,
3248 : : relation_trio rel = TRIO_VARYING) const final override;
3249 : : // Check compatibility of all operands.
3250 : 0 : bool operand_check_p (tree t1, tree t2, tree t3) const final override
3251 : 0 : { return range_compatible_p (t1, t2) && range_compatible_p (t1, t3); }
3252 : : } op_logical_and;
3253 : :
3254 : : bool
3255 : 0 : operator_logical_and::fold_range (irange &r, tree type,
3256 : : const irange &lh,
3257 : : const irange &rh,
3258 : : relation_trio) const
3259 : : {
3260 : 0 : if (empty_range_varying (r, type, lh, rh))
3261 : 0 : return true;
3262 : :
3263 : : // Precision of LHS and both operands must match.
3264 : 0 : if (TYPE_PRECISION (lh.type ()) != TYPE_PRECISION (type)
3265 : 0 : || TYPE_PRECISION (type) != TYPE_PRECISION (rh.type ()))
3266 : 0 : return false;
3267 : :
3268 : : // 0 && anything is 0.
3269 : 0 : if ((wi::eq_p (lh.lower_bound (), 0) && wi::eq_p (lh.upper_bound (), 0))
3270 : 0 : || (wi::eq_p (lh.lower_bound (), 0) && wi::eq_p (rh.upper_bound (), 0)))
3271 : 0 : r = range_false (type);
3272 : 0 : else if (contains_zero_p (lh) || contains_zero_p (rh))
3273 : : // To reach this point, there must be a logical 1 on each side, and
3274 : : // the only remaining question is whether there is a zero or not.
3275 : 0 : r = range_true_and_false (type);
3276 : : else
3277 : 0 : r = range_true (type);
3278 : : return true;
3279 : : }
3280 : :
3281 : : bool
3282 : 844052 : operator_logical_and::op1_range (irange &r, tree type,
3283 : : const irange &lhs,
3284 : : const irange &op2 ATTRIBUTE_UNUSED,
3285 : : relation_trio) const
3286 : : {
3287 : 844052 : switch (get_bool_state (r, lhs, type))
3288 : : {
3289 : 450635 : case BRS_TRUE:
3290 : : // A true result means both sides of the AND must be true.
3291 : 450635 : r = range_true (type);
3292 : 450635 : break;
3293 : 393417 : default:
3294 : : // Any other result means only one side has to be false, the
3295 : : // other side can be anything. So we cannot be sure of any
3296 : : // result here.
3297 : 393417 : r = range_true_and_false (type);
3298 : 393417 : break;
3299 : : }
3300 : 844052 : return true;
3301 : : }
3302 : :
3303 : : bool
3304 : 0 : operator_logical_and::op2_range (irange &r, tree type,
3305 : : const irange &lhs,
3306 : : const irange &op1,
3307 : : relation_trio) const
3308 : : {
3309 : 0 : return operator_logical_and::op1_range (r, type, lhs, op1);
3310 : : }
3311 : :
3312 : :
3313 : : void
3314 : 6628061 : operator_bitwise_and::update_bitmask (irange &r, const irange &lh,
3315 : : const irange &rh) const
3316 : : {
3317 : 6628061 : update_known_bitmask (r, BIT_AND_EXPR, lh, rh);
3318 : 6628061 : }
3319 : :
3320 : : // Optimize BIT_AND_EXPR, BIT_IOR_EXPR and BIT_XOR_EXPR of signed types
3321 : : // by considering the number of leading redundant sign bit copies.
3322 : : // clrsb (X op Y) = min (clrsb (X), clrsb (Y)), so for example
3323 : : // [-1, 0] op [-1, 0] is [-1, 0] (where nonzero_bits doesn't help).
3324 : : static bool
3325 : 231802 : wi_optimize_signed_bitwise_op (irange &r, tree type,
3326 : : const wide_int &lh_lb, const wide_int &lh_ub,
3327 : : const wide_int &rh_lb, const wide_int &rh_ub)
3328 : : {
3329 : 463604 : int lh_clrsb = MIN (wi::clrsb (lh_lb), wi::clrsb (lh_ub));
3330 : 463604 : int rh_clrsb = MIN (wi::clrsb (rh_lb), wi::clrsb (rh_ub));
3331 : 231802 : int new_clrsb = MIN (lh_clrsb, rh_clrsb);
3332 : 231802 : if (new_clrsb == 0)
3333 : : return false;
3334 : 6993 : int type_prec = TYPE_PRECISION (type);
3335 : 6993 : int rprec = (type_prec - new_clrsb) - 1;
3336 : 6993 : value_range_with_overflow (r, type,
3337 : 13986 : wi::mask (rprec, true, type_prec),
3338 : 6993 : wi::mask (rprec, false, type_prec));
3339 : 6993 : return true;
3340 : : }
3341 : :
3342 : : // An AND of 8,16, 32 or 64 bits can produce a partial equivalence between
3343 : : // the LHS and op1.
3344 : :
3345 : : relation_kind
3346 : 6468798 : operator_bitwise_and::lhs_op1_relation (const irange &lhs,
3347 : : const irange &op1,
3348 : : const irange &op2,
3349 : : relation_kind) const
3350 : : {
3351 : 6468798 : if (lhs.undefined_p () || op1.undefined_p () || op2.undefined_p ())
3352 : : return VREL_VARYING;
3353 : 6464714 : if (!op2.singleton_p ())
3354 : : return VREL_VARYING;
3355 : : // if val == 0xff or 0xFFFF OR 0Xffffffff OR 0Xffffffffffffffff, return TRUE
3356 : 3739491 : int prec1 = TYPE_PRECISION (op1.type ());
3357 : 3739491 : int prec2 = TYPE_PRECISION (op2.type ());
3358 : 3739491 : int mask_prec = 0;
3359 : 3739491 : wide_int mask = op2.lower_bound ();
3360 : 3739491 : if (wi::eq_p (mask, wi::mask (8, false, prec2)))
3361 : : mask_prec = 8;
3362 : 3647168 : else if (wi::eq_p (mask, wi::mask (16, false, prec2)))
3363 : : mask_prec = 16;
3364 : 3630941 : else if (wi::eq_p (mask, wi::mask (32, false, prec2)))
3365 : : mask_prec = 32;
3366 : 3459465 : else if (wi::eq_p (mask, wi::mask (64, false, prec2)))
3367 : 686 : mask_prec = 64;
3368 : 3739491 : return bits_to_pe (MIN (prec1, mask_prec));
3369 : 3739491 : }
3370 : :
3371 : : // Optimize BIT_AND_EXPR and BIT_IOR_EXPR in terms of a mask if
3372 : : // possible. Basically, see if we can optimize:
3373 : : //
3374 : : // [LB, UB] op Z
3375 : : // into:
3376 : : // [LB op Z, UB op Z]
3377 : : //
3378 : : // If the optimization was successful, accumulate the range in R and
3379 : : // return TRUE.
3380 : :
3381 : : static bool
3382 : 20140373 : wi_optimize_and_or (irange &r,
3383 : : enum tree_code code,
3384 : : tree type,
3385 : : const wide_int &lh_lb, const wide_int &lh_ub,
3386 : : const wide_int &rh_lb, const wide_int &rh_ub)
3387 : : {
3388 : : // Calculate the singleton mask among the ranges, if any.
3389 : 20140373 : wide_int lower_bound, upper_bound, mask;
3390 : 20140373 : if (wi::eq_p (rh_lb, rh_ub))
3391 : : {
3392 : 18812845 : mask = rh_lb;
3393 : 18812845 : lower_bound = lh_lb;
3394 : 18812845 : upper_bound = lh_ub;
3395 : : }
3396 : 1327528 : else if (wi::eq_p (lh_lb, lh_ub))
3397 : : {
3398 : 249604 : mask = lh_lb;
3399 : 249604 : lower_bound = rh_lb;
3400 : 249604 : upper_bound = rh_ub;
3401 : : }
3402 : : else
3403 : : return false;
3404 : :
3405 : : // If Z is a constant which (for op | its bitwise not) has n
3406 : : // consecutive least significant bits cleared followed by m 1
3407 : : // consecutive bits set immediately above it and either
3408 : : // m + n == precision, or (x >> (m + n)) == (y >> (m + n)).
3409 : : //
3410 : : // The least significant n bits of all the values in the range are
3411 : : // cleared or set, the m bits above it are preserved and any bits
3412 : : // above these are required to be the same for all values in the
3413 : : // range.
3414 : 19062449 : wide_int w = mask;
3415 : 19062449 : int m = 0, n = 0;
3416 : 19062449 : if (code == BIT_IOR_EXPR)
3417 : 5995844 : w = ~w;
3418 : 19062449 : if (wi::eq_p (w, 0))
3419 : 6839036 : n = w.get_precision ();
3420 : : else
3421 : : {
3422 : 12223413 : n = wi::ctz (w);
3423 : 12223419 : w = ~(w | wi::mask (n, false, w.get_precision ()));
3424 : 12223413 : if (wi::eq_p (w, 0))
3425 : 7733864 : m = w.get_precision () - n;
3426 : : else
3427 : 4489549 : m = wi::ctz (w) - n;
3428 : : }
3429 : 19062449 : wide_int new_mask = wi::mask (m + n, true, w.get_precision ());
3430 : 19062455 : if ((new_mask & lower_bound) != (new_mask & upper_bound))
3431 : : return false;
3432 : :
3433 : 15171959 : wide_int res_lb, res_ub;
3434 : 15171959 : if (code == BIT_AND_EXPR)
3435 : : {
3436 : 9366853 : res_lb = wi::bit_and (lower_bound, mask);
3437 : 9366853 : res_ub = wi::bit_and (upper_bound, mask);
3438 : : }
3439 : 5805106 : else if (code == BIT_IOR_EXPR)
3440 : : {
3441 : 5805106 : res_lb = wi::bit_or (lower_bound, mask);
3442 : 5805106 : res_ub = wi::bit_or (upper_bound, mask);
3443 : : }
3444 : : else
3445 : 0 : gcc_unreachable ();
3446 : 15171959 : value_range_with_overflow (r, type, res_lb, res_ub);
3447 : :
3448 : : // Furthermore, if the mask is non-zero, an IOR cannot contain zero.
3449 : 15171959 : if (code == BIT_IOR_EXPR && wi::ne_p (mask, 0))
3450 : : {
3451 : 2919902 : int_range<2> tmp;
3452 : 2919902 : tmp.set_nonzero (type);
3453 : 2919902 : r.intersect (tmp);
3454 : 2919902 : }
3455 : 15171959 : return true;
3456 : 54374787 : }
3457 : :
3458 : : // For range [LB, UB] compute two wide_int bit masks.
3459 : : //
3460 : : // In the MAYBE_NONZERO bit mask, if some bit is unset, it means that
3461 : : // for all numbers in the range the bit is 0, otherwise it might be 0
3462 : : // or 1.
3463 : : //
3464 : : // In the MUSTBE_NONZERO bit mask, if some bit is set, it means that
3465 : : // for all numbers in the range the bit is 1, otherwise it might be 0
3466 : : // or 1.
3467 : :
3468 : : void
3469 : 11517575 : wi_set_zero_nonzero_bits (tree type,
3470 : : const wide_int &lb, const wide_int &ub,
3471 : : wide_int &maybe_nonzero,
3472 : : wide_int &mustbe_nonzero)
3473 : : {
3474 : 11517575 : signop sign = TYPE_SIGN (type);
3475 : :
3476 : 11517575 : if (wi::eq_p (lb, ub))
3477 : 4641116 : maybe_nonzero = mustbe_nonzero = lb;
3478 : 6876459 : else if (wi::ge_p (lb, 0, sign) || wi::lt_p (ub, 0, sign))
3479 : : {
3480 : 5917667 : wide_int xor_mask = lb ^ ub;
3481 : 5917667 : maybe_nonzero = lb | ub;
3482 : 5917667 : mustbe_nonzero = lb & ub;
3483 : 5917667 : if (xor_mask != 0)
3484 : : {
3485 : 5917667 : wide_int mask = wi::mask (wi::floor_log2 (xor_mask), false,
3486 : 11835334 : maybe_nonzero.get_precision ());
3487 : 5917667 : maybe_nonzero = maybe_nonzero | mask;
3488 : 5917675 : mustbe_nonzero = wi::bit_and_not (mustbe_nonzero, mask);
3489 : 5917667 : }
3490 : 5917667 : }
3491 : : else
3492 : : {
3493 : 958792 : maybe_nonzero = wi::minus_one (lb.get_precision ());
3494 : 958792 : mustbe_nonzero = wi::zero (lb.get_precision ());
3495 : : }
3496 : 11517575 : }
3497 : :
3498 : : void
3499 : 13576106 : operator_bitwise_and::wi_fold (irange &r, tree type,
3500 : : const wide_int &lh_lb,
3501 : : const wide_int &lh_ub,
3502 : : const wide_int &rh_lb,
3503 : : const wide_int &rh_ub) const
3504 : : {
3505 : 13576106 : if (wi_optimize_and_or (r, BIT_AND_EXPR, type, lh_lb, lh_ub, rh_lb, rh_ub))
3506 : 9367512 : return;
3507 : :
3508 : 4209253 : wide_int maybe_nonzero_lh, mustbe_nonzero_lh;
3509 : 4209253 : wide_int maybe_nonzero_rh, mustbe_nonzero_rh;
3510 : 4209253 : wi_set_zero_nonzero_bits (type, lh_lb, lh_ub,
3511 : : maybe_nonzero_lh, mustbe_nonzero_lh);
3512 : 4209253 : wi_set_zero_nonzero_bits (type, rh_lb, rh_ub,
3513 : : maybe_nonzero_rh, mustbe_nonzero_rh);
3514 : :
3515 : 4209253 : wide_int new_lb = mustbe_nonzero_lh & mustbe_nonzero_rh;
3516 : 4209253 : wide_int new_ub = maybe_nonzero_lh & maybe_nonzero_rh;
3517 : 4209253 : signop sign = TYPE_SIGN (type);
3518 : 4209253 : unsigned prec = TYPE_PRECISION (type);
3519 : : // If both input ranges contain only negative values, we can
3520 : : // truncate the result range maximum to the minimum of the
3521 : : // input range maxima.
3522 : 4209253 : if (wi::lt_p (lh_ub, 0, sign) && wi::lt_p (rh_ub, 0, sign))
3523 : : {
3524 : 6367 : new_ub = wi::min (new_ub, lh_ub, sign);
3525 : 6367 : new_ub = wi::min (new_ub, rh_ub, sign);
3526 : : }
3527 : : // If either input range contains only non-negative values
3528 : : // we can truncate the result range maximum to the respective
3529 : : // maximum of the input range.
3530 : 4209253 : if (wi::ge_p (lh_lb, 0, sign))
3531 : 3536404 : new_ub = wi::min (new_ub, lh_ub, sign);
3532 : 4209253 : if (wi::ge_p (rh_lb, 0, sign))
3533 : 4096218 : new_ub = wi::min (new_ub, rh_ub, sign);
3534 : : // PR68217: In case of signed & sign-bit-CST should
3535 : : // result in [-INF, 0] instead of [-INF, INF].
3536 : 4209253 : if (wi::gt_p (new_lb, new_ub, sign))
3537 : : {
3538 : 79791 : wide_int sign_bit = wi::set_bit_in_zero (prec - 1, prec);
3539 : 79791 : if (sign == SIGNED
3540 : 79791 : && ((wi::eq_p (lh_lb, lh_ub)
3541 : 58 : && !wi::cmps (lh_lb, sign_bit))
3542 : 79791 : || (wi::eq_p (rh_lb, rh_ub)
3543 : 21833 : && !wi::cmps (rh_lb, sign_bit))))
3544 : : {
3545 : 0 : new_lb = wi::min_value (prec, sign);
3546 : 0 : new_ub = wi::zero (prec);
3547 : : }
3548 : 79791 : }
3549 : : // If the limits got swapped around, return varying.
3550 : 4209253 : if (wi::gt_p (new_lb, new_ub,sign))
3551 : : {
3552 : 79791 : if (sign == SIGNED
3553 : 79791 : && wi_optimize_signed_bitwise_op (r, type,
3554 : : lh_lb, lh_ub,
3555 : : rh_lb, rh_ub))
3556 : 659 : return;
3557 : 79132 : r.set_varying (type);
3558 : : }
3559 : : else
3560 : 4129462 : value_range_with_overflow (r, type, new_lb, new_ub);
3561 : 4209253 : }
3562 : :
3563 : : static void
3564 : 478096 : set_nonzero_range_from_mask (irange &r, tree type, const irange &lhs)
3565 : : {
3566 : 478096 : if (lhs.undefined_p () || contains_zero_p (lhs))
3567 : 256042 : r.set_varying (type);
3568 : : else
3569 : 222054 : r.set_nonzero (type);
3570 : 478096 : }
3571 : :
3572 : : /* Find out smallest RES where RES > VAL && (RES & MASK) == RES, if any
3573 : : (otherwise return VAL). VAL and MASK must be zero-extended for
3574 : : precision PREC. If SGNBIT is non-zero, first xor VAL with SGNBIT
3575 : : (to transform signed values into unsigned) and at the end xor
3576 : : SGNBIT back. */
3577 : :
3578 : : wide_int
3579 : 48084 : masked_increment (const wide_int &val_in, const wide_int &mask,
3580 : : const wide_int &sgnbit, unsigned int prec)
3581 : : {
3582 : 48084 : wide_int bit = wi::one (prec), res;
3583 : 48084 : unsigned int i;
3584 : :
3585 : 48084 : wide_int val = val_in ^ sgnbit;
3586 : 848548 : for (i = 0; i < prec; i++, bit += bit)
3587 : : {
3588 : 785163 : res = mask;
3589 : 785163 : if ((res & bit) == 0)
3590 : 456195 : continue;
3591 : 328968 : res = bit - 1;
3592 : 328968 : res = wi::bit_and_not (val + bit, res);
3593 : 328968 : res &= mask;
3594 : 328968 : if (wi::gtu_p (res, val))
3595 : 32783 : return res ^ sgnbit;
3596 : : }
3597 : 15301 : return val ^ sgnbit;
3598 : 48084 : }
3599 : :
3600 : : // This was shamelessly stolen from register_edge_assert_for_2 and
3601 : : // adjusted to work with iranges.
3602 : :
3603 : : void
3604 : 2782648 : operator_bitwise_and::simple_op1_range_solver (irange &r, tree type,
3605 : : const irange &lhs,
3606 : : const irange &op2) const
3607 : : {
3608 : 2782648 : if (!op2.singleton_p ())
3609 : : {
3610 : 478070 : set_nonzero_range_from_mask (r, type, lhs);
3611 : 969271 : return;
3612 : : }
3613 : 2304578 : unsigned int nprec = TYPE_PRECISION (type);
3614 : 2304578 : wide_int cst2v = op2.lower_bound ();
3615 : 2304578 : bool cst2n = wi::neg_p (cst2v, TYPE_SIGN (type));
3616 : 2304578 : wide_int sgnbit;
3617 : 2304578 : if (cst2n)
3618 : 367749 : sgnbit = wi::set_bit_in_zero (nprec - 1, nprec);
3619 : : else
3620 : 1936829 : sgnbit = wi::zero (nprec);
3621 : :
3622 : : // Solve [lhs.lower_bound (), +INF] = x & MASK.
3623 : : //
3624 : : // Minimum unsigned value for >= if (VAL & CST2) == VAL is VAL and
3625 : : // maximum unsigned value is ~0. For signed comparison, if CST2
3626 : : // doesn't have the most significant bit set, handle it similarly. If
3627 : : // CST2 has MSB set, the minimum is the same, and maximum is ~0U/2.
3628 : 2304578 : wide_int valv = lhs.lower_bound ();
3629 : 2304578 : wide_int minv = valv & cst2v, maxv;
3630 : 2304578 : bool we_know_nothing = false;
3631 : 2304578 : if (minv != valv)
3632 : : {
3633 : : // If (VAL & CST2) != VAL, X & CST2 can't be equal to VAL.
3634 : 9229 : minv = masked_increment (valv, cst2v, sgnbit, nprec);
3635 : 9229 : if (minv == valv)
3636 : : {
3637 : : // If we can't determine anything on this bound, fall
3638 : : // through and conservatively solve for the other end point.
3639 : 2304578 : we_know_nothing = true;
3640 : : }
3641 : : }
3642 : 4241407 : maxv = wi::mask (nprec - (cst2n ? 1 : 0), false, nprec);
3643 : 2304578 : if (we_know_nothing)
3644 : 2170 : r.set_varying (type);
3645 : : else
3646 : 2302408 : create_possibly_reversed_range (r, type, minv, maxv);
3647 : :
3648 : : // Solve [-INF, lhs.upper_bound ()] = x & MASK.
3649 : : //
3650 : : // Minimum unsigned value for <= is 0 and maximum unsigned value is
3651 : : // VAL | ~CST2 if (VAL & CST2) == VAL. Otherwise, find smallest
3652 : : // VAL2 where
3653 : : // VAL2 > VAL && (VAL2 & CST2) == VAL2 and use (VAL2 - 1) | ~CST2
3654 : : // as maximum.
3655 : : // For signed comparison, if CST2 doesn't have most significant bit
3656 : : // set, handle it similarly. If CST2 has MSB set, the maximum is
3657 : : // the same and minimum is INT_MIN.
3658 : 2304578 : valv = lhs.upper_bound ();
3659 : 2304578 : minv = valv & cst2v;
3660 : 2304578 : if (minv == valv)
3661 : 2265723 : maxv = valv;
3662 : : else
3663 : : {
3664 : 38855 : maxv = masked_increment (valv, cst2v, sgnbit, nprec);
3665 : 38855 : if (maxv == valv)
3666 : : {
3667 : : // If we couldn't determine anything on either bound, return
3668 : : // undefined.
3669 : 13131 : if (we_know_nothing)
3670 : 1807 : r.set_undefined ();
3671 : 13131 : return;
3672 : : }
3673 : 25724 : maxv -= 1;
3674 : : }
3675 : 2291447 : maxv |= ~cst2v;
3676 : 2291447 : minv = sgnbit;
3677 : 2291447 : int_range<2> upper_bits;
3678 : 2291447 : create_possibly_reversed_range (upper_bits, type, minv, maxv);
3679 : 2291447 : r.intersect (upper_bits);
3680 : 2304578 : }
3681 : :
3682 : : bool
3683 : 3161005 : operator_bitwise_and::op1_range (irange &r, tree type,
3684 : : const irange &lhs,
3685 : : const irange &op2,
3686 : : relation_trio) const
3687 : : {
3688 : 3161005 : if (lhs.undefined_p ())
3689 : : return false;
3690 : 3161005 : if (types_compatible_p (type, boolean_type_node))
3691 : 844052 : return op_logical_and.op1_range (r, type, lhs, op2);
3692 : :
3693 : 2316953 : r.set_undefined ();
3694 : 5099601 : for (unsigned i = 0; i < lhs.num_pairs (); ++i)
3695 : : {
3696 : 5565296 : int_range_max chunk (lhs.type (),
3697 : 5565296 : lhs.lower_bound (i),
3698 : 5565296 : lhs.upper_bound (i));
3699 : 2782648 : int_range_max res;
3700 : 2782648 : simple_op1_range_solver (res, type, chunk, op2);
3701 : 2782648 : r.union_ (res);
3702 : 2782648 : }
3703 : 2316953 : if (r.undefined_p ())
3704 : 26 : set_nonzero_range_from_mask (r, type, lhs);
3705 : :
3706 : : // For MASK == op1 & MASK, all the bits in MASK must be set in op1.
3707 : 2316953 : wide_int mask;
3708 : 2316953 : if (lhs == op2 && lhs.singleton_p (mask))
3709 : : {
3710 : 320406 : r.update_bitmask (irange_bitmask (mask, ~mask));
3711 : 320406 : return true;
3712 : : }
3713 : :
3714 : 1996547 : if (!op2.singleton_p (mask))
3715 : : return true;
3716 : :
3717 : : // For 0 = op1 & MASK, op1 is ~MASK.
3718 : 1567648 : if (lhs.zero_p ())
3719 : : {
3720 : 611143 : wide_int nz = wi::bit_not (op2.get_nonzero_bits ());
3721 : 611143 : int_range<2> tmp (type);
3722 : 611143 : tmp.set_nonzero_bits (nz);
3723 : 611143 : r.intersect (tmp);
3724 : 611143 : }
3725 : :
3726 : 1567648 : irange_bitmask lhs_bm = lhs.get_bitmask ();
3727 : : // given [5,7] mask 0x3 value 0x4 = N & [7, 7] mask 0x0 value 0x7
3728 : : // Nothing is known about the bits not specified in the mask value (op2),
3729 : : // Start with the mask, 1's will occur where values were masked.
3730 : 1567648 : wide_int op1_mask = ~mask;
3731 : : // Any bits that are unknown on the LHS are also unknown in op1,
3732 : : // so union the current mask with the LHS mask.
3733 : 1567648 : op1_mask |= lhs_bm.mask ();
3734 : : // The resulting zeros correspond to known bits in the LHS mask, and
3735 : : // the LHS value should tell us what they are. Mask off any
3736 : : // extraneous values thats are not convered by the mask.
3737 : 1567648 : wide_int op1_value = lhs_bm.value () & ~op1_mask;
3738 : 1567648 : irange_bitmask op1_bm (op1_value, op1_mask);
3739 : : // INtersect this mask with anything already known about the value.
3740 : 1567648 : op1_bm.intersect (r.get_bitmask ());
3741 : 1567648 : r.update_bitmask (op1_bm);
3742 : 1567648 : return true;
3743 : 3884601 : }
3744 : :
3745 : : bool
3746 : 727806 : operator_bitwise_and::op2_range (irange &r, tree type,
3747 : : const irange &lhs,
3748 : : const irange &op1,
3749 : : relation_trio) const
3750 : : {
3751 : 727806 : return operator_bitwise_and::op1_range (r, type, lhs, op1);
3752 : : }
3753 : :
3754 : :
3755 : : class operator_logical_or : public range_operator
3756 : : {
3757 : : using range_operator::fold_range;
3758 : : using range_operator::op1_range;
3759 : : using range_operator::op2_range;
3760 : : public:
3761 : : bool fold_range (irange &r, tree type,
3762 : : const irange &lh,
3763 : : const irange &rh,
3764 : : relation_trio rel = TRIO_VARYING) const final override;
3765 : : bool op1_range (irange &r, tree type,
3766 : : const irange &lhs,
3767 : : const irange &op2,
3768 : : relation_trio rel = TRIO_VARYING) const final override;
3769 : : bool op2_range (irange &r, tree type,
3770 : : const irange &lhs,
3771 : : const irange &op1,
3772 : : relation_trio rel = TRIO_VARYING) const final override;
3773 : : // Check compatibility of all operands.
3774 : 0 : bool operand_check_p (tree t1, tree t2, tree t3) const final override
3775 : 0 : { return range_compatible_p (t1, t2) && range_compatible_p (t1, t3); }
3776 : : } op_logical_or;
3777 : :
3778 : : bool
3779 : 0 : operator_logical_or::fold_range (irange &r, tree type ATTRIBUTE_UNUSED,
3780 : : const irange &lh,
3781 : : const irange &rh,
3782 : : relation_trio) const
3783 : : {
3784 : 0 : if (empty_range_varying (r, type, lh, rh))
3785 : 0 : return true;
3786 : :
3787 : 0 : r = lh;
3788 : 0 : r.union_ (rh);
3789 : 0 : return true;
3790 : : }
3791 : :
3792 : : bool
3793 : 378227 : operator_logical_or::op1_range (irange &r, tree type,
3794 : : const irange &lhs,
3795 : : const irange &op2 ATTRIBUTE_UNUSED,
3796 : : relation_trio) const
3797 : : {
3798 : 378227 : switch (get_bool_state (r, lhs, type))
3799 : : {
3800 : 234362 : case BRS_FALSE:
3801 : : // A false result means both sides of the OR must be false.
3802 : 234362 : r = range_false (type);
3803 : 234362 : break;
3804 : 143865 : default:
3805 : : // Any other result means only one side has to be true, the
3806 : : // other side can be anything. so we can't be sure of any result
3807 : : // here.
3808 : 143865 : r = range_true_and_false (type);
3809 : 143865 : break;
3810 : : }
3811 : 378227 : return true;
3812 : : }
3813 : :
3814 : : bool
3815 : 0 : operator_logical_or::op2_range (irange &r, tree type,
3816 : : const irange &lhs,
3817 : : const irange &op1,
3818 : : relation_trio) const
3819 : : {
3820 : 0 : return operator_logical_or::op1_range (r, type, lhs, op1);
3821 : : }
3822 : :
3823 : :
3824 : : void
3825 : 2249658 : operator_bitwise_or::update_bitmask (irange &r, const irange &lh,
3826 : : const irange &rh) const
3827 : : {
3828 : 2249658 : update_known_bitmask (r, BIT_IOR_EXPR, lh, rh);
3829 : 2249658 : }
3830 : :
3831 : : void
3832 : 6564267 : operator_bitwise_or::wi_fold (irange &r, tree type,
3833 : : const wide_int &lh_lb,
3834 : : const wide_int &lh_ub,
3835 : : const wide_int &rh_lb,
3836 : : const wide_int &rh_ub) const
3837 : : {
3838 : 6564267 : if (wi_optimize_and_or (r, BIT_IOR_EXPR, type, lh_lb, lh_ub, rh_lb, rh_ub))
3839 : 5977187 : return;
3840 : :
3841 : 759161 : wide_int maybe_nonzero_lh, mustbe_nonzero_lh;
3842 : 759161 : wide_int maybe_nonzero_rh, mustbe_nonzero_rh;
3843 : 759161 : wi_set_zero_nonzero_bits (type, lh_lb, lh_ub,
3844 : : maybe_nonzero_lh, mustbe_nonzero_lh);
3845 : 759161 : wi_set_zero_nonzero_bits (type, rh_lb, rh_ub,
3846 : : maybe_nonzero_rh, mustbe_nonzero_rh);
3847 : 759161 : wide_int new_lb = mustbe_nonzero_lh | mustbe_nonzero_rh;
3848 : 759161 : wide_int new_ub = maybe_nonzero_lh | maybe_nonzero_rh;
3849 : 759161 : signop sign = TYPE_SIGN (type);
3850 : : // If the input ranges contain only positive values we can
3851 : : // truncate the minimum of the result range to the maximum
3852 : : // of the input range minima.
3853 : 759161 : if (wi::ge_p (lh_lb, 0, sign)
3854 : 759161 : && wi::ge_p (rh_lb, 0, sign))
3855 : : {
3856 : 568771 : new_lb = wi::max (new_lb, lh_lb, sign);
3857 : 568771 : new_lb = wi::max (new_lb, rh_lb, sign);
3858 : : }
3859 : : // If either input range contains only negative values
3860 : : // we can truncate the minimum of the result range to the
3861 : : // respective minimum range.
3862 : 759161 : if (wi::lt_p (lh_ub, 0, sign))
3863 : 10306 : new_lb = wi::max (new_lb, lh_lb, sign);
3864 : 759161 : if (wi::lt_p (rh_ub, 0, sign))
3865 : 8279 : new_lb = wi::max (new_lb, rh_lb, sign);
3866 : : // If the limits got swapped around, return a conservative range.
3867 : 759161 : if (wi::gt_p (new_lb, new_ub, sign))
3868 : : {
3869 : : // Make sure that nonzero|X is nonzero.
3870 : 172081 : if (wi::gt_p (lh_lb, 0, sign)
3871 : 167241 : || wi::gt_p (rh_lb, 0, sign)
3872 : 108787 : || wi::lt_p (lh_ub, 0, sign)
3873 : 280868 : || wi::lt_p (rh_ub, 0, sign))
3874 : 63294 : r.set_nonzero (type);
3875 : 108787 : else if (sign == SIGNED
3876 : 108787 : && wi_optimize_signed_bitwise_op (r, type,
3877 : : lh_lb, lh_ub,
3878 : : rh_lb, rh_ub))
3879 : : return;
3880 : : else
3881 : 108071 : r.set_varying (type);
3882 : 171365 : return;
3883 : : }
3884 : 587080 : value_range_with_overflow (r, type, new_lb, new_ub);
3885 : 759191 : }
3886 : :
3887 : : bool
3888 : 611954 : operator_bitwise_or::op1_range (irange &r, tree type,
3889 : : const irange &lhs,
3890 : : const irange &op2,
3891 : : relation_trio) const
3892 : : {
3893 : 611954 : if (lhs.undefined_p ())
3894 : : return false;
3895 : : // If this is really a logical wi_fold, call that.
3896 : 611954 : if (types_compatible_p (type, boolean_type_node))
3897 : 378227 : return op_logical_or.op1_range (r, type, lhs, op2);
3898 : :
3899 : 233727 : if (lhs.zero_p ())
3900 : : {
3901 : 76271 : r.set_zero (type);
3902 : 76271 : return true;
3903 : : }
3904 : :
3905 : : // if (A < 0 && B < 0)
3906 : : // Sometimes gets translated to
3907 : : // _1 = A | B
3908 : : // if (_1 < 0))
3909 : : // It is useful for ranger to recognize a positive LHS means the RHS
3910 : : // operands are also positive when dealing with the ELSE range..
3911 : 224822 : if (TYPE_SIGN (type) == SIGNED && wi::ge_p (lhs.lower_bound (), 0, SIGNED))
3912 : : {
3913 : 23876 : unsigned prec = TYPE_PRECISION (type);
3914 : 23876 : r.set (type, wi::zero (prec), wi::max_value (prec, SIGNED));
3915 : 23876 : return true;
3916 : : }
3917 : 133580 : r.set_varying (type);
3918 : 133580 : return true;
3919 : : }
3920 : :
3921 : : bool
3922 : 301613 : operator_bitwise_or::op2_range (irange &r, tree type,
3923 : : const irange &lhs,
3924 : : const irange &op1,
3925 : : relation_trio) const
3926 : : {
3927 : 301613 : return operator_bitwise_or::op1_range (r, type, lhs, op1);
3928 : : }
3929 : :
3930 : : void
3931 : 268958 : operator_bitwise_xor::update_bitmask (irange &r, const irange &lh,
3932 : : const irange &rh) const
3933 : : {
3934 : 268958 : update_known_bitmask (r, BIT_XOR_EXPR, lh, rh);
3935 : 268958 : }
3936 : :
3937 : : void
3938 : 443430 : operator_bitwise_xor::wi_fold (irange &r, tree type,
3939 : : const wide_int &lh_lb,
3940 : : const wide_int &lh_ub,
3941 : : const wide_int &rh_lb,
3942 : : const wide_int &rh_ub) const
3943 : : {
3944 : 443430 : signop sign = TYPE_SIGN (type);
3945 : 443430 : wide_int maybe_nonzero_lh, mustbe_nonzero_lh;
3946 : 443430 : wide_int maybe_nonzero_rh, mustbe_nonzero_rh;
3947 : 443430 : wi_set_zero_nonzero_bits (type, lh_lb, lh_ub,
3948 : : maybe_nonzero_lh, mustbe_nonzero_lh);
3949 : 443430 : wi_set_zero_nonzero_bits (type, rh_lb, rh_ub,
3950 : : maybe_nonzero_rh, mustbe_nonzero_rh);
3951 : :
3952 : 1330290 : wide_int result_zero_bits = ((mustbe_nonzero_lh & mustbe_nonzero_rh)
3953 : 1330290 : | ~(maybe_nonzero_lh | maybe_nonzero_rh));
3954 : 443430 : wide_int result_one_bits
3955 : 886860 : = (wi::bit_and_not (mustbe_nonzero_lh, maybe_nonzero_rh)
3956 : 886860 : | wi::bit_and_not (mustbe_nonzero_rh, maybe_nonzero_lh));
3957 : 443430 : wide_int new_ub = ~result_zero_bits;
3958 : 443430 : wide_int new_lb = result_one_bits;
3959 : :
3960 : : // If the range has all positive or all negative values, the result
3961 : : // is better than VARYING.
3962 : 443430 : if (wi::lt_p (new_lb, 0, sign) || wi::ge_p (new_ub, 0, sign))
3963 : 400206 : value_range_with_overflow (r, type, new_lb, new_ub);
3964 : 43224 : else if (sign == SIGNED
3965 : 43224 : && wi_optimize_signed_bitwise_op (r, type,
3966 : : lh_lb, lh_ub,
3967 : : rh_lb, rh_ub))
3968 : : ; /* Do nothing. */
3969 : : else
3970 : 37606 : r.set_varying (type);
3971 : :
3972 : : /* Furthermore, XOR is non-zero if its arguments can't be equal. */
3973 : 443430 : if (wi::lt_p (lh_ub, rh_lb, sign)
3974 : 355141 : || wi::lt_p (rh_ub, lh_lb, sign)
3975 : 750618 : || wi::ne_p (result_one_bits, 0))
3976 : : {
3977 : 136242 : int_range<2> tmp;
3978 : 136242 : tmp.set_nonzero (type);
3979 : 136242 : r.intersect (tmp);
3980 : 136242 : }
3981 : 443448 : }
3982 : :
3983 : : bool
3984 : 268958 : operator_bitwise_xor::op1_op2_relation_effect (irange &lhs_range,
3985 : : tree type,
3986 : : const irange &,
3987 : : const irange &,
3988 : : relation_kind rel) const
3989 : : {
3990 : 268958 : if (rel == VREL_VARYING)
3991 : : return false;
3992 : :
3993 : 12674 : int_range<2> rel_range;
3994 : :
3995 : 12674 : switch (rel)
3996 : : {
3997 : 40 : case VREL_EQ:
3998 : 40 : rel_range.set_zero (type);
3999 : 40 : break;
4000 : 1361 : case VREL_NE:
4001 : 1361 : rel_range.set_nonzero (type);
4002 : 1361 : break;
4003 : : default:
4004 : : return false;
4005 : : }
4006 : :
4007 : 1401 : lhs_range.intersect (rel_range);
4008 : 1401 : return true;
4009 : 12674 : }
4010 : :
4011 : : bool
4012 : 59908 : operator_bitwise_xor::op1_range (irange &r, tree type,
4013 : : const irange &lhs,
4014 : : const irange &op2,
4015 : : relation_trio) const
4016 : : {
4017 : 59908 : if (lhs.undefined_p () || lhs.varying_p ())
4018 : : {
4019 : 7883 : r = lhs;
4020 : 7883 : return true;
4021 : : }
4022 : 52025 : if (types_compatible_p (type, boolean_type_node))
4023 : : {
4024 : 2063 : switch (get_bool_state (r, lhs, type))
4025 : : {
4026 : 991 : case BRS_TRUE:
4027 : 991 : if (op2.varying_p ())
4028 : 927 : r.set_varying (type);
4029 : 64 : else if (op2.zero_p ())
4030 : 48 : r = range_true (type);
4031 : : // See get_bool_state for the rationale
4032 : 16 : else if (op2.undefined_p () || contains_zero_p (op2))
4033 : 0 : r = range_true_and_false (type);
4034 : : else
4035 : 16 : r = range_false (type);
4036 : : break;
4037 : 1072 : case BRS_FALSE:
4038 : 1072 : r = op2;
4039 : 1072 : break;
4040 : : default:
4041 : : break;
4042 : : }
4043 : 2063 : return true;
4044 : : }
4045 : 49962 : r.set_varying (type);
4046 : 49962 : return true;
4047 : : }
4048 : :
4049 : : bool
4050 : 25484 : operator_bitwise_xor::op2_range (irange &r, tree type,
4051 : : const irange &lhs,
4052 : : const irange &op1,
4053 : : relation_trio) const
4054 : : {
4055 : 25484 : return operator_bitwise_xor::op1_range (r, type, lhs, op1);
4056 : : }
4057 : :
4058 : : class operator_trunc_mod : public range_operator
4059 : : {
4060 : : using range_operator::op1_range;
4061 : : using range_operator::op2_range;
4062 : : using range_operator::update_bitmask;
4063 : : public:
4064 : : virtual void wi_fold (irange &r, tree type,
4065 : : const wide_int &lh_lb,
4066 : : const wide_int &lh_ub,
4067 : : const wide_int &rh_lb,
4068 : : const wide_int &rh_ub) const;
4069 : : virtual bool op1_range (irange &r, tree type,
4070 : : const irange &lhs,
4071 : : const irange &op2,
4072 : : relation_trio) const;
4073 : : virtual bool op2_range (irange &r, tree type,
4074 : : const irange &lhs,
4075 : : const irange &op1,
4076 : : relation_trio) const;
4077 : 924346 : void update_bitmask (irange &r, const irange &lh, const irange &rh) const
4078 : 924346 : { update_known_bitmask (r, TRUNC_MOD_EXPR, lh, rh); }
4079 : : } op_trunc_mod;
4080 : :
4081 : : void
4082 : 1156701 : operator_trunc_mod::wi_fold (irange &r, tree type,
4083 : : const wide_int &lh_lb,
4084 : : const wide_int &lh_ub,
4085 : : const wide_int &rh_lb,
4086 : : const wide_int &rh_ub) const
4087 : : {
4088 : 1156701 : wide_int new_lb, new_ub, tmp;
4089 : 1156701 : signop sign = TYPE_SIGN (type);
4090 : 1156701 : unsigned prec = TYPE_PRECISION (type);
4091 : :
4092 : : // Mod 0 is undefined.
4093 : 1156701 : if (wi_zero_p (type, rh_lb, rh_ub))
4094 : : {
4095 : 6997 : r.set_undefined ();
4096 : 6997 : return;
4097 : : }
4098 : :
4099 : : // Check for constant and try to fold.
4100 : 1313202 : if (lh_lb == lh_ub && rh_lb == rh_ub)
4101 : : {
4102 : 16685 : wi::overflow_type ov = wi::OVF_NONE;
4103 : 16685 : tmp = wi::mod_trunc (lh_lb, rh_lb, sign, &ov);
4104 : 16685 : if (ov == wi::OVF_NONE)
4105 : : {
4106 : 16685 : r = int_range<2> (type, tmp, tmp);
4107 : 16685 : return;
4108 : : }
4109 : : }
4110 : :
4111 : : // ABS (A % B) < ABS (B) and either 0 <= A % B <= A or A <= A % B <= 0.
4112 : 1133019 : new_ub = rh_ub - 1;
4113 : 1133019 : if (sign == SIGNED)
4114 : : {
4115 : 463889 : tmp = -1 - rh_lb;
4116 : 463889 : new_ub = wi::smax (new_ub, tmp);
4117 : : }
4118 : :
4119 : 1133019 : if (sign == UNSIGNED)
4120 : 669130 : new_lb = wi::zero (prec);
4121 : : else
4122 : : {
4123 : 463889 : new_lb = -new_ub;
4124 : 463889 : tmp = lh_lb;
4125 : 463889 : if (wi::gts_p (tmp, 0))
4126 : 108461 : tmp = wi::zero (prec);
4127 : 463913 : new_lb = wi::smax (new_lb, tmp);
4128 : : }
4129 : 1133019 : tmp = lh_ub;
4130 : 1133019 : if (sign == SIGNED && wi::neg_p (tmp))
4131 : 26524 : tmp = wi::zero (prec);
4132 : 1133019 : new_ub = wi::min (new_ub, tmp, sign);
4133 : :
4134 : 1133019 : value_range_with_overflow (r, type, new_lb, new_ub);
4135 : 1156815 : }
4136 : :
4137 : : bool
4138 : 486013 : operator_trunc_mod::op1_range (irange &r, tree type,
4139 : : const irange &lhs,
4140 : : const irange &,
4141 : : relation_trio) const
4142 : : {
4143 : 486013 : if (lhs.undefined_p ())
4144 : : return false;
4145 : : // PR 91029.
4146 : 486013 : signop sign = TYPE_SIGN (type);
4147 : 486013 : unsigned prec = TYPE_PRECISION (type);
4148 : : // (a % b) >= x && x > 0 , then a >= x.
4149 : 486095 : if (wi::gt_p (lhs.lower_bound (), 0, sign))
4150 : : {
4151 : 121210 : r.set (type, lhs.lower_bound (), wi::max_value (prec, sign));
4152 : 121183 : return true;
4153 : : }
4154 : : // (a % b) <= x && x < 0 , then a <= x.
4155 : 364885 : if (wi::lt_p (lhs.upper_bound (), 0, sign))
4156 : : {
4157 : 5717 : r.set (type, wi::min_value (prec, sign), lhs.upper_bound ());
4158 : 5717 : return true;
4159 : : }
4160 : : return false;
4161 : : }
4162 : :
4163 : : bool
4164 : 296598 : operator_trunc_mod::op2_range (irange &r, tree type,
4165 : : const irange &lhs,
4166 : : const irange &,
4167 : : relation_trio) const
4168 : : {
4169 : 296598 : if (lhs.undefined_p ())
4170 : : return false;
4171 : : // PR 91029.
4172 : 296598 : signop sign = TYPE_SIGN (type);
4173 : 296598 : unsigned prec = TYPE_PRECISION (type);
4174 : : // (a % b) >= x && x > 0 , then b is in ~[-x, x] for signed
4175 : : // or b > x for unsigned.
4176 : 296629 : if (wi::gt_p (lhs.lower_bound (), 0, sign))
4177 : : {
4178 : 47618 : if (sign == SIGNED)
4179 : 2005 : r.set (type, wi::neg (lhs.lower_bound ()),
4180 : 4010 : lhs.lower_bound (), VR_ANTI_RANGE);
4181 : 45625 : else if (wi::lt_p (lhs.lower_bound (), wi::max_value (prec, sign),
4182 : : sign))
4183 : 45631 : r.set (type, lhs.lower_bound () + 1, wi::max_value (prec, sign));
4184 : : else
4185 : : return false;
4186 : 47618 : return true;
4187 : : }
4188 : : // (a % b) <= x && x < 0 , then b is in ~[x, -x].
4189 : 249005 : if (wi::lt_p (lhs.upper_bound (), 0, sign))
4190 : : {
4191 : 4043 : if (wi::gt_p (lhs.upper_bound (), wi::min_value (prec, sign), sign))
4192 : 4043 : r.set (type, lhs.upper_bound (),
4193 : 8086 : wi::neg (lhs.upper_bound ()), VR_ANTI_RANGE);
4194 : : else
4195 : : return false;
4196 : 4043 : return true;
4197 : : }
4198 : : return false;
4199 : : }
4200 : :
4201 : :
4202 : : class operator_logical_not : public range_operator
4203 : : {
4204 : : using range_operator::fold_range;
4205 : : using range_operator::op1_range;
4206 : : public:
4207 : : bool fold_range (irange &r, tree type,
4208 : : const irange &lh,
4209 : : const irange &rh,
4210 : : relation_trio rel = TRIO_VARYING) const final override;
4211 : : bool op1_range (irange &r, tree type,
4212 : : const irange &lhs,
4213 : : const irange &op2,
4214 : : relation_trio rel = TRIO_VARYING) const final override;
4215 : : // Check compatibility of LHS and op1.
4216 : 0 : bool operand_check_p (tree t1, tree t2, tree) const final override
4217 : 0 : { return range_compatible_p (t1, t2); }
4218 : : } op_logical_not;
4219 : :
4220 : : // Folding a logical NOT, oddly enough, involves doing nothing on the
4221 : : // forward pass through. During the initial walk backwards, the
4222 : : // logical NOT reversed the desired outcome on the way back, so on the
4223 : : // way forward all we do is pass the range forward.
4224 : : //
4225 : : // b_2 = x_1 < 20
4226 : : // b_3 = !b_2
4227 : : // if (b_3)
4228 : : // to determine the TRUE branch, walking backward
4229 : : // if (b_3) if ([1,1])
4230 : : // b_3 = !b_2 [1,1] = ![0,0]
4231 : : // b_2 = x_1 < 20 [0,0] = x_1 < 20, false, so x_1 == [20, 255]
4232 : : // which is the result we are looking for.. so.. pass it through.
4233 : :
4234 : : bool
4235 : 241885 : operator_logical_not::fold_range (irange &r, tree type,
4236 : : const irange &lh,
4237 : : const irange &rh ATTRIBUTE_UNUSED,
4238 : : relation_trio) const
4239 : : {
4240 : 241885 : if (empty_range_varying (r, type, lh, rh))
4241 : 0 : return true;
4242 : :
4243 : 241885 : r = lh;
4244 : 241885 : if (!lh.varying_p () && !lh.undefined_p ())
4245 : 48869 : r.invert ();
4246 : :
4247 : : return true;
4248 : : }
4249 : :
4250 : : bool
4251 : 25850 : operator_logical_not::op1_range (irange &r,
4252 : : tree type,
4253 : : const irange &lhs,
4254 : : const irange &op2,
4255 : : relation_trio) const
4256 : : {
4257 : : // Logical NOT is involutary...do it again.
4258 : 25850 : return fold_range (r, type, lhs, op2);
4259 : : }
4260 : :
4261 : : bool
4262 : 493438 : operator_bitwise_not::fold_range (irange &r, tree type,
4263 : : const irange &lh,
4264 : : const irange &rh,
4265 : : relation_trio) const
4266 : : {
4267 : 493438 : if (empty_range_varying (r, type, lh, rh))
4268 : 119 : return true;
4269 : :
4270 : 493319 : if (types_compatible_p (type, boolean_type_node))
4271 : 216035 : return op_logical_not.fold_range (r, type, lh, rh);
4272 : :
4273 : : // ~X is simply -1 - X.
4274 : 554568 : int_range<1> minusone (type, wi::minus_one (TYPE_PRECISION (type)),
4275 : 554568 : wi::minus_one (TYPE_PRECISION (type)));
4276 : 277284 : return range_op_handler (MINUS_EXPR).fold_range (r, type, minusone, lh);
4277 : 277284 : }
4278 : :
4279 : : bool
4280 : 48040 : operator_bitwise_not::op1_range (irange &r, tree type,
4281 : : const irange &lhs,
4282 : : const irange &op2,
4283 : : relation_trio) const
4284 : : {
4285 : 48040 : if (lhs.undefined_p ())
4286 : : return false;
4287 : 48040 : if (types_compatible_p (type, boolean_type_node))
4288 : 25850 : return op_logical_not.op1_range (r, type, lhs, op2);
4289 : :
4290 : : // ~X is -1 - X and since bitwise NOT is involutary...do it again.
4291 : 22190 : return fold_range (r, type, lhs, op2);
4292 : : }
4293 : :
4294 : : void
4295 : 0 : operator_bitwise_not::update_bitmask (irange &r, const irange &lh,
4296 : : const irange &rh) const
4297 : : {
4298 : 0 : update_known_bitmask (r, BIT_NOT_EXPR, lh, rh);
4299 : 0 : }
4300 : :
4301 : :
4302 : : bool
4303 : 260712 : operator_cst::fold_range (irange &r, tree type ATTRIBUTE_UNUSED,
4304 : : const irange &lh,
4305 : : const irange &rh ATTRIBUTE_UNUSED,
4306 : : relation_trio) const
4307 : : {
4308 : 260712 : r = lh;
4309 : 260712 : return true;
4310 : : }
4311 : :
4312 : :
4313 : : // Determine if there is a relationship between LHS and OP1.
4314 : :
4315 : : relation_kind
4316 : 796608 : operator_identity::lhs_op1_relation (const irange &lhs,
4317 : : const irange &op1 ATTRIBUTE_UNUSED,
4318 : : const irange &op2 ATTRIBUTE_UNUSED,
4319 : : relation_kind) const
4320 : : {
4321 : 796608 : if (lhs.undefined_p ())
4322 : 389 : return VREL_VARYING;
4323 : : // Simply a copy, so they are equivalent.
4324 : : return VREL_EQ;
4325 : : }
4326 : :
4327 : : bool
4328 : 797172 : operator_identity::fold_range (irange &r, tree type ATTRIBUTE_UNUSED,
4329 : : const irange &lh,
4330 : : const irange &rh ATTRIBUTE_UNUSED,
4331 : : relation_trio) const
4332 : : {
4333 : 797172 : r = lh;
4334 : 797172 : return true;
4335 : : }
4336 : :
4337 : : bool
4338 : 267889 : operator_identity::op1_range (irange &r, tree type ATTRIBUTE_UNUSED,
4339 : : const irange &lhs,
4340 : : const irange &op2 ATTRIBUTE_UNUSED,
4341 : : relation_trio) const
4342 : : {
4343 : 267889 : r = lhs;
4344 : 267889 : return true;
4345 : : }
4346 : :
4347 : :
4348 : : class operator_unknown : public range_operator
4349 : : {
4350 : : using range_operator::fold_range;
4351 : : public:
4352 : : virtual bool fold_range (irange &r, tree type,
4353 : : const irange &op1,
4354 : : const irange &op2,
4355 : : relation_trio rel = TRIO_VARYING) const;
4356 : : } op_unknown;
4357 : :
4358 : : bool
4359 : 793881 : operator_unknown::fold_range (irange &r, tree type,
4360 : : const irange &lh ATTRIBUTE_UNUSED,
4361 : : const irange &rh ATTRIBUTE_UNUSED,
4362 : : relation_trio) const
4363 : : {
4364 : 793881 : r.set_varying (type);
4365 : 793881 : return true;
4366 : : }
4367 : :
4368 : :
4369 : : void
4370 : 71618 : operator_abs::wi_fold (irange &r, tree type,
4371 : : const wide_int &lh_lb, const wide_int &lh_ub,
4372 : : const wide_int &rh_lb ATTRIBUTE_UNUSED,
4373 : : const wide_int &rh_ub ATTRIBUTE_UNUSED) const
4374 : : {
4375 : 71618 : wide_int min, max;
4376 : 71618 : signop sign = TYPE_SIGN (type);
4377 : 71618 : unsigned prec = TYPE_PRECISION (type);
4378 : :
4379 : : // Pass through LH for the easy cases.
4380 : 71618 : if (sign == UNSIGNED || wi::ge_p (lh_lb, 0, sign))
4381 : : {
4382 : 10932 : r = int_range<1> (type, lh_lb, lh_ub);
4383 : 10932 : return;
4384 : : }
4385 : :
4386 : : // -TYPE_MIN_VALUE = TYPE_MIN_VALUE with flag_wrapv so we can't get
4387 : : // a useful range.
4388 : 60686 : wide_int min_value = wi::min_value (prec, sign);
4389 : 60686 : wide_int max_value = wi::max_value (prec, sign);
4390 : 60686 : if (!TYPE_OVERFLOW_UNDEFINED (type) && wi::eq_p (lh_lb, min_value))
4391 : : {
4392 : 637 : r.set_varying (type);
4393 : 637 : return;
4394 : : }
4395 : :
4396 : : // ABS_EXPR may flip the range around, if the original range
4397 : : // included negative values.
4398 : 60049 : if (wi::eq_p (lh_lb, min_value))
4399 : : {
4400 : : // ABS ([-MIN, -MIN]) isn't representable, but we have traditionally
4401 : : // returned [-MIN,-MIN] so this preserves that behavior. PR37078
4402 : 33134 : if (wi::eq_p (lh_ub, min_value))
4403 : : {
4404 : 221 : r = int_range<1> (type, min_value, min_value);
4405 : 221 : return;
4406 : : }
4407 : 32913 : min = max_value;
4408 : : }
4409 : : else
4410 : 26915 : min = wi::abs (lh_lb);
4411 : :
4412 : 59828 : if (wi::eq_p (lh_ub, min_value))
4413 : 0 : max = max_value;
4414 : : else
4415 : 59828 : max = wi::abs (lh_ub);
4416 : :
4417 : : // If the range contains zero then we know that the minimum value in the
4418 : : // range will be zero.
4419 : 59828 : if (wi::le_p (lh_lb, 0, sign) && wi::ge_p (lh_ub, 0, sign))
4420 : : {
4421 : 51110 : if (wi::gt_p (min, max, sign))
4422 : 19790 : max = min;
4423 : 51110 : min = wi::zero (prec);
4424 : : }
4425 : : else
4426 : : {
4427 : : // If the range was reversed, swap MIN and MAX.
4428 : 8718 : if (wi::gt_p (min, max, sign))
4429 : 8643 : std::swap (min, max);
4430 : : }
4431 : :
4432 : : // If the new range has its limits swapped around (MIN > MAX), then
4433 : : // the operation caused one of them to wrap around. The only thing
4434 : : // we know is that the result is positive.
4435 : 59828 : if (wi::gt_p (min, max, sign))
4436 : : {
4437 : 0 : min = wi::zero (prec);
4438 : 0 : max = max_value;
4439 : : }
4440 : 59828 : r = int_range<1> (type, min, max);
4441 : 72476 : }
4442 : :
4443 : : bool
4444 : 44587 : operator_abs::op1_range (irange &r, tree type,
4445 : : const irange &lhs,
4446 : : const irange &op2,
4447 : : relation_trio) const
4448 : : {
4449 : 44587 : if (empty_range_varying (r, type, lhs, op2))
4450 : 0 : return true;
4451 : 44587 : if (TYPE_UNSIGNED (type))
4452 : : {
4453 : 0 : r = lhs;
4454 : 0 : return true;
4455 : : }
4456 : : // Start with the positives because negatives are an impossible result.
4457 : 44587 : int_range_max positives = range_positives (type);
4458 : 44587 : positives.intersect (lhs);
4459 : 44587 : r = positives;
4460 : : // Then add the negative of each pair:
4461 : : // ABS(op1) = [5,20] would yield op1 => [-20,-5][5,20].
4462 : 89873 : for (unsigned i = 0; i < positives.num_pairs (); ++i)
4463 : 45286 : r.union_ (int_range<1> (type,
4464 : 90572 : -positives.upper_bound (i),
4465 : 135858 : -positives.lower_bound (i)));
4466 : : // With flag_wrapv, -TYPE_MIN_VALUE = TYPE_MIN_VALUE which is
4467 : : // unrepresentable. Add -TYPE_MIN_VALUE in this case.
4468 : 44587 : wide_int min_value = wi::min_value (TYPE_PRECISION (type), TYPE_SIGN (type));
4469 : 44587 : wide_int lb = lhs.lower_bound ();
4470 : 44587 : if (!TYPE_OVERFLOW_UNDEFINED (type) && wi::eq_p (lb, min_value))
4471 : 193 : r.union_ (int_range<2> (type, lb, lb));
4472 : 44587 : return true;
4473 : 44587 : }
4474 : :
4475 : : void
4476 : 65801 : operator_abs::update_bitmask (irange &r, const irange &lh,
4477 : : const irange &rh) const
4478 : : {
4479 : 65801 : update_known_bitmask (r, ABS_EXPR, lh, rh);
4480 : 65801 : }
4481 : :
4482 : : class operator_absu : public range_operator
4483 : : {
4484 : : using range_operator::update_bitmask;
4485 : : public:
4486 : : virtual void wi_fold (irange &r, tree type,
4487 : : const wide_int &lh_lb, const wide_int &lh_ub,
4488 : : const wide_int &rh_lb, const wide_int &rh_ub)
4489 : : const final override;
4490 : : virtual void update_bitmask (irange &r, const irange &lh,
4491 : : const irange &rh) const final override;
4492 : : } op_absu;
4493 : :
4494 : : void
4495 : 16022 : operator_absu::wi_fold (irange &r, tree type,
4496 : : const wide_int &lh_lb, const wide_int &lh_ub,
4497 : : const wide_int &rh_lb ATTRIBUTE_UNUSED,
4498 : : const wide_int &rh_ub ATTRIBUTE_UNUSED) const
4499 : : {
4500 : 16022 : wide_int new_lb, new_ub;
4501 : :
4502 : : // Pass through VR0 the easy cases.
4503 : 16022 : if (wi::ges_p (lh_lb, 0))
4504 : : {
4505 : 2347 : new_lb = lh_lb;
4506 : 2347 : new_ub = lh_ub;
4507 : : }
4508 : : else
4509 : : {
4510 : 13675 : new_lb = wi::abs (lh_lb);
4511 : 13675 : new_ub = wi::abs (lh_ub);
4512 : :
4513 : : // If the range contains zero then we know that the minimum
4514 : : // value in the range will be zero.
4515 : 13675 : if (wi::ges_p (lh_ub, 0))
4516 : : {
4517 : 10660 : if (wi::gtu_p (new_lb, new_ub))
4518 : 9408 : new_ub = new_lb;
4519 : 10660 : new_lb = wi::zero (TYPE_PRECISION (type));
4520 : : }
4521 : : else
4522 : 3015 : std::swap (new_lb, new_ub);
4523 : : }
4524 : :
4525 : 16022 : gcc_checking_assert (TYPE_UNSIGNED (type));
4526 : 16022 : r = int_range<1> (type, new_lb, new_ub);
4527 : 16022 : }
4528 : :
4529 : : void
4530 : 14720 : operator_absu::update_bitmask (irange &r, const irange &lh,
4531 : : const irange &rh) const
4532 : : {
4533 : 14720 : update_known_bitmask (r, ABSU_EXPR, lh, rh);
4534 : 14720 : }
4535 : :
4536 : :
4537 : : bool
4538 : 536218 : operator_negate::fold_range (irange &r, tree type,
4539 : : const irange &lh,
4540 : : const irange &rh,
4541 : : relation_trio) const
4542 : : {
4543 : 536218 : if (empty_range_varying (r, type, lh, rh))
4544 : 932 : return true;
4545 : :
4546 : : // -X is simply 0 - X.
4547 : 535286 : int_range<1> zero;
4548 : 535286 : zero.set_zero (type);
4549 : 535286 : return range_op_handler (MINUS_EXPR).fold_range (r, type, zero, lh);
4550 : 535286 : }
4551 : :
4552 : : bool
4553 : 67127 : operator_negate::op1_range (irange &r, tree type,
4554 : : const irange &lhs,
4555 : : const irange &op2,
4556 : : relation_trio) const
4557 : : {
4558 : : // NEGATE is involutory.
4559 : 67127 : return fold_range (r, type, lhs, op2);
4560 : : }
4561 : :
4562 : :
4563 : : bool
4564 : 0 : operator_addr_expr::fold_range (irange &r, tree type,
4565 : : const irange &lh,
4566 : : const irange &rh,
4567 : : relation_trio) const
4568 : : {
4569 : 0 : if (empty_range_varying (r, type, lh, rh))
4570 : 0 : return true;
4571 : :
4572 : : // Return a non-null pointer of the LHS type (passed in op2).
4573 : 0 : if (lh.zero_p ())
4574 : 0 : r.set_zero (type);
4575 : 0 : else if (lh.undefined_p () || contains_zero_p (lh))
4576 : 0 : r.set_varying (type);
4577 : : else
4578 : 0 : r.set_nonzero (type);
4579 : : return true;
4580 : : }
4581 : :
4582 : : bool
4583 : 0 : operator_addr_expr::op1_range (irange &r, tree type,
4584 : : const irange &lhs,
4585 : : const irange &op2,
4586 : : relation_trio) const
4587 : : {
4588 : 0 : if (empty_range_varying (r, type, lhs, op2))
4589 : 0 : return true;
4590 : :
4591 : : // Return a non-null pointer of the LHS type (passed in op2), but only
4592 : : // if we cant overflow, eitherwise a no-zero offset could wrap to zero.
4593 : : // See PR 111009.
4594 : 0 : if (!lhs.undefined_p () && !contains_zero_p (lhs) && TYPE_OVERFLOW_UNDEFINED (type))
4595 : 0 : r.set_nonzero (type);
4596 : : else
4597 : 0 : r.set_varying (type);
4598 : : return true;
4599 : : }
4600 : :
4601 : : // Initialize any integral operators to the primary table
4602 : :
4603 : : void
4604 : 285621 : range_op_table::initialize_integral_ops ()
4605 : : {
4606 : 285621 : set (TRUNC_DIV_EXPR, op_trunc_div);
4607 : 285621 : set (FLOOR_DIV_EXPR, op_floor_div);
4608 : 285621 : set (ROUND_DIV_EXPR, op_round_div);
4609 : 285621 : set (CEIL_DIV_EXPR, op_ceil_div);
4610 : 285621 : set (EXACT_DIV_EXPR, op_exact_div);
4611 : 285621 : set (LSHIFT_EXPR, op_lshift);
4612 : 285621 : set (RSHIFT_EXPR, op_rshift);
4613 : 285621 : set (TRUTH_AND_EXPR, op_logical_and);
4614 : 285621 : set (TRUTH_OR_EXPR, op_logical_or);
4615 : 285621 : set (TRUNC_MOD_EXPR, op_trunc_mod);
4616 : 285621 : set (TRUTH_NOT_EXPR, op_logical_not);
4617 : 285621 : set (IMAGPART_EXPR, op_unknown);
4618 : 285621 : set (REALPART_EXPR, op_unknown);
4619 : 285621 : set (ABSU_EXPR, op_absu);
4620 : 285621 : set (OP_WIDEN_MULT_SIGNED, op_widen_mult_signed);
4621 : 285621 : set (OP_WIDEN_MULT_UNSIGNED, op_widen_mult_unsigned);
4622 : 285621 : set (OP_WIDEN_PLUS_SIGNED, op_widen_plus_signed);
4623 : 285621 : set (OP_WIDEN_PLUS_UNSIGNED, op_widen_plus_unsigned);
4624 : :
4625 : 285621 : }
4626 : :
4627 : : bool
4628 : 41930 : operator_plus::overflow_free_p (const irange &lh, const irange &rh,
4629 : : relation_trio) const
4630 : : {
4631 : 41930 : if (lh.undefined_p () || rh.undefined_p ())
4632 : : return false;
4633 : :
4634 : 41926 : tree type = lh.type ();
4635 : 41926 : if (TYPE_OVERFLOW_UNDEFINED (type))
4636 : : return true;
4637 : :
4638 : 10642 : wi::overflow_type ovf;
4639 : 10642 : signop sgn = TYPE_SIGN (type);
4640 : 10642 : wide_int wmax0 = lh.upper_bound ();
4641 : 10642 : wide_int wmax1 = rh.upper_bound ();
4642 : 10642 : wi::add (wmax0, wmax1, sgn, &ovf);
4643 : 10642 : if (ovf != wi::OVF_NONE)
4644 : : return false;
4645 : :
4646 : 1236 : if (TYPE_UNSIGNED (type))
4647 : : return true;
4648 : :
4649 : 372 : wide_int wmin0 = lh.lower_bound ();
4650 : 372 : wide_int wmin1 = rh.lower_bound ();
4651 : 372 : wi::add (wmin0, wmin1, sgn, &ovf);
4652 : 372 : if (ovf != wi::OVF_NONE)
4653 : 261 : return false;
4654 : :
4655 : : return true;
4656 : 11014 : }
4657 : :
4658 : : bool
4659 : 31 : operator_minus::overflow_free_p (const irange &lh, const irange &rh,
4660 : : relation_trio) const
4661 : : {
4662 : 31 : if (lh.undefined_p () || rh.undefined_p ())
4663 : : return false;
4664 : :
4665 : 31 : tree type = lh.type ();
4666 : 31 : if (TYPE_OVERFLOW_UNDEFINED (type))
4667 : : return true;
4668 : :
4669 : 10 : wi::overflow_type ovf;
4670 : 10 : signop sgn = TYPE_SIGN (type);
4671 : 10 : wide_int wmin0 = lh.lower_bound ();
4672 : 10 : wide_int wmax1 = rh.upper_bound ();
4673 : 10 : wi::sub (wmin0, wmax1, sgn, &ovf);
4674 : 10 : if (ovf != wi::OVF_NONE)
4675 : : return false;
4676 : :
4677 : 7 : if (TYPE_UNSIGNED (type))
4678 : : return true;
4679 : :
4680 : 6 : wide_int wmax0 = lh.upper_bound ();
4681 : 6 : wide_int wmin1 = rh.lower_bound ();
4682 : 6 : wi::sub (wmax0, wmin1, sgn, &ovf);
4683 : 6 : if (ovf != wi::OVF_NONE)
4684 : 0 : return false;
4685 : :
4686 : : return true;
4687 : 16 : }
4688 : :
4689 : : bool
4690 : 3403 : operator_mult::overflow_free_p (const irange &lh, const irange &rh,
4691 : : relation_trio) const
4692 : : {
4693 : 3403 : if (lh.undefined_p () || rh.undefined_p ())
4694 : : return false;
4695 : :
4696 : 3403 : tree type = lh.type ();
4697 : 3403 : if (TYPE_OVERFLOW_UNDEFINED (type))
4698 : : return true;
4699 : :
4700 : 2900 : wi::overflow_type ovf;
4701 : 2900 : signop sgn = TYPE_SIGN (type);
4702 : 2900 : wide_int wmax0 = lh.upper_bound ();
4703 : 2900 : wide_int wmax1 = rh.upper_bound ();
4704 : 2900 : wi::mul (wmax0, wmax1, sgn, &ovf);
4705 : 2900 : if (ovf != wi::OVF_NONE)
4706 : : return false;
4707 : :
4708 : 111 : if (TYPE_UNSIGNED (type))
4709 : : return true;
4710 : :
4711 : 22 : wide_int wmin0 = lh.lower_bound ();
4712 : 22 : wide_int wmin1 = rh.lower_bound ();
4713 : 22 : wi::mul (wmin0, wmin1, sgn, &ovf);
4714 : 22 : if (ovf != wi::OVF_NONE)
4715 : : return false;
4716 : :
4717 : 22 : wi::mul (wmin0, wmax1, sgn, &ovf);
4718 : 22 : if (ovf != wi::OVF_NONE)
4719 : : return false;
4720 : :
4721 : 22 : wi::mul (wmax0, wmin1, sgn, &ovf);
4722 : 22 : if (ovf != wi::OVF_NONE)
4723 : : return false;
4724 : :
4725 : : return true;
4726 : 2922 : }
4727 : :
4728 : : #if CHECKING_P
4729 : : #include "selftest.h"
4730 : :
4731 : : namespace selftest
4732 : : {
4733 : : #define INT(x) wi::shwi ((x), TYPE_PRECISION (integer_type_node))
4734 : : #define UINT(x) wi::uhwi ((x), TYPE_PRECISION (unsigned_type_node))
4735 : : #define INT16(x) wi::shwi ((x), TYPE_PRECISION (short_integer_type_node))
4736 : : #define UINT16(x) wi::uhwi ((x), TYPE_PRECISION (short_unsigned_type_node))
4737 : : #define SCHAR(x) wi::shwi ((x), TYPE_PRECISION (signed_char_type_node))
4738 : : #define UCHAR(x) wi::uhwi ((x), TYPE_PRECISION (unsigned_char_type_node))
4739 : :
4740 : : static void
4741 : 4 : range_op_cast_tests ()
4742 : : {
4743 : 4 : int_range<2> r0, r1, r2, rold;
4744 : 4 : r0.set_varying (integer_type_node);
4745 : 4 : wide_int maxint = r0.upper_bound ();
4746 : :
4747 : : // If a range is in any way outside of the range for the converted
4748 : : // to range, default to the range for the new type.
4749 : 4 : r0.set_varying (short_integer_type_node);
4750 : 4 : wide_int minshort = r0.lower_bound ();
4751 : 4 : wide_int maxshort = r0.upper_bound ();
4752 : 4 : if (TYPE_PRECISION (integer_type_node)
4753 : 4 : > TYPE_PRECISION (short_integer_type_node))
4754 : : {
4755 : 8 : r1 = int_range<1> (integer_type_node,
4756 : 4 : wi::zero (TYPE_PRECISION (integer_type_node)),
4757 : 8 : maxint);
4758 : 4 : range_cast (r1, short_integer_type_node);
4759 : 4 : ASSERT_TRUE (r1.lower_bound () == minshort
4760 : : && r1.upper_bound() == maxshort);
4761 : : }
4762 : :
4763 : : // (unsigned char)[-5,-1] => [251,255].
4764 : 4 : r0 = rold = int_range<1> (signed_char_type_node, SCHAR (-5), SCHAR (-1));
4765 : 4 : range_cast (r0, unsigned_char_type_node);
4766 : 4 : ASSERT_TRUE (r0 == int_range<1> (unsigned_char_type_node,
4767 : : UCHAR (251), UCHAR (255)));
4768 : 4 : range_cast (r0, signed_char_type_node);
4769 : 4 : ASSERT_TRUE (r0 == rold);
4770 : :
4771 : : // (signed char)[15, 150] => [-128,-106][15,127].
4772 : 4 : r0 = rold = int_range<1> (unsigned_char_type_node, UCHAR (15), UCHAR (150));
4773 : 4 : range_cast (r0, signed_char_type_node);
4774 : 4 : r1 = int_range<1> (signed_char_type_node, SCHAR (15), SCHAR (127));
4775 : 4 : r2 = int_range<1> (signed_char_type_node, SCHAR (-128), SCHAR (-106));
4776 : 4 : r1.union_ (r2);
4777 : 4 : ASSERT_TRUE (r1 == r0);
4778 : 4 : range_cast (r0, unsigned_char_type_node);
4779 : 4 : ASSERT_TRUE (r0 == rold);
4780 : :
4781 : : // (unsigned char)[-5, 5] => [0,5][251,255].
4782 : 4 : r0 = rold = int_range<1> (signed_char_type_node, SCHAR (-5), SCHAR (5));
4783 : 4 : range_cast (r0, unsigned_char_type_node);
4784 : 4 : r1 = int_range<1> (unsigned_char_type_node, UCHAR (251), UCHAR (255));
4785 : 4 : r2 = int_range<1> (unsigned_char_type_node, UCHAR (0), UCHAR (5));
4786 : 4 : r1.union_ (r2);
4787 : 4 : ASSERT_TRUE (r0 == r1);
4788 : 4 : range_cast (r0, signed_char_type_node);
4789 : 4 : ASSERT_TRUE (r0 == rold);
4790 : :
4791 : : // (unsigned char)[-5,5] => [0,5][251,255].
4792 : 4 : r0 = int_range<1> (integer_type_node, INT (-5), INT (5));
4793 : 4 : range_cast (r0, unsigned_char_type_node);
4794 : 4 : r1 = int_range<1> (unsigned_char_type_node, UCHAR (0), UCHAR (5));
4795 : 4 : r1.union_ (int_range<1> (unsigned_char_type_node, UCHAR (251), UCHAR (255)));
4796 : 4 : ASSERT_TRUE (r0 == r1);
4797 : :
4798 : : // (unsigned char)[5U,1974U] => [0,255].
4799 : 4 : r0 = int_range<1> (unsigned_type_node, UINT (5), UINT (1974));
4800 : 4 : range_cast (r0, unsigned_char_type_node);
4801 : 4 : ASSERT_TRUE (r0 == int_range<1> (unsigned_char_type_node, UCHAR (0), UCHAR (255)));
4802 : 4 : range_cast (r0, integer_type_node);
4803 : : // Going to a wider range should not sign extend.
4804 : 4 : ASSERT_TRUE (r0 == int_range<1> (integer_type_node, INT (0), INT (255)));
4805 : :
4806 : : // (unsigned char)[-350,15] => [0,255].
4807 : 4 : r0 = int_range<1> (integer_type_node, INT (-350), INT (15));
4808 : 4 : range_cast (r0, unsigned_char_type_node);
4809 : 4 : ASSERT_TRUE (r0 == (int_range<1>
4810 : : (unsigned_char_type_node,
4811 : : min_limit (unsigned_char_type_node),
4812 : : max_limit (unsigned_char_type_node))));
4813 : :
4814 : : // Casting [-120,20] from signed char to unsigned short.
4815 : : // => [0, 20][0xff88, 0xffff].
4816 : 4 : r0 = int_range<1> (signed_char_type_node, SCHAR (-120), SCHAR (20));
4817 : 4 : range_cast (r0, short_unsigned_type_node);
4818 : 4 : r1 = int_range<1> (short_unsigned_type_node, UINT16 (0), UINT16 (20));
4819 : 8 : r2 = int_range<1> (short_unsigned_type_node,
4820 : 12 : UINT16 (0xff88), UINT16 (0xffff));
4821 : 4 : r1.union_ (r2);
4822 : 4 : ASSERT_TRUE (r0 == r1);
4823 : : // A truncating cast back to signed char will work because [-120, 20]
4824 : : // is representable in signed char.
4825 : 4 : range_cast (r0, signed_char_type_node);
4826 : 4 : ASSERT_TRUE (r0 == int_range<1> (signed_char_type_node,
4827 : : SCHAR (-120), SCHAR (20)));
4828 : :
4829 : : // unsigned char -> signed short
4830 : : // (signed short)[(unsigned char)25, (unsigned char)250]
4831 : : // => [(signed short)25, (signed short)250]
4832 : 4 : r0 = rold = int_range<1> (unsigned_char_type_node, UCHAR (25), UCHAR (250));
4833 : 4 : range_cast (r0, short_integer_type_node);
4834 : 4 : r1 = int_range<1> (short_integer_type_node, INT16 (25), INT16 (250));
4835 : 4 : ASSERT_TRUE (r0 == r1);
4836 : 4 : range_cast (r0, unsigned_char_type_node);
4837 : 4 : ASSERT_TRUE (r0 == rold);
4838 : :
4839 : : // Test casting a wider signed [-MIN,MAX] to a narrower unsigned.
4840 : 8 : r0 = int_range<1> (long_long_integer_type_node,
4841 : 4 : min_limit (long_long_integer_type_node),
4842 : 8 : max_limit (long_long_integer_type_node));
4843 : 4 : range_cast (r0, short_unsigned_type_node);
4844 : 8 : r1 = int_range<1> (short_unsigned_type_node,
4845 : 4 : min_limit (short_unsigned_type_node),
4846 : 8 : max_limit (short_unsigned_type_node));
4847 : 4 : ASSERT_TRUE (r0 == r1);
4848 : :
4849 : : // Casting NONZERO to a narrower type will wrap/overflow so
4850 : : // it's just the entire range for the narrower type.
4851 : : //
4852 : : // "NOT 0 at signed 32-bits" ==> [-MIN_32,-1][1, +MAX_32]. This is
4853 : : // is outside of the range of a smaller range, return the full
4854 : : // smaller range.
4855 : 4 : if (TYPE_PRECISION (integer_type_node)
4856 : 4 : > TYPE_PRECISION (short_integer_type_node))
4857 : : {
4858 : 4 : r0.set_nonzero (integer_type_node);
4859 : 4 : range_cast (r0, short_integer_type_node);
4860 : 8 : r1 = int_range<1> (short_integer_type_node,
4861 : 4 : min_limit (short_integer_type_node),
4862 : 8 : max_limit (short_integer_type_node));
4863 : 4 : ASSERT_TRUE (r0 == r1);
4864 : : }
4865 : :
4866 : : // Casting NONZERO from a narrower signed to a wider signed.
4867 : : //
4868 : : // NONZERO signed 16-bits is [-MIN_16,-1][1, +MAX_16].
4869 : : // Converting this to 32-bits signed is [-MIN_16,-1][1, +MAX_16].
4870 : 4 : r0.set_nonzero (short_integer_type_node);
4871 : 4 : range_cast (r0, integer_type_node);
4872 : 4 : r1 = int_range<1> (integer_type_node, INT (-32768), INT (-1));
4873 : 4 : r2 = int_range<1> (integer_type_node, INT (1), INT (32767));
4874 : 4 : r1.union_ (r2);
4875 : 4 : ASSERT_TRUE (r0 == r1);
4876 : 4 : }
4877 : :
4878 : : static void
4879 : 4 : range_op_lshift_tests ()
4880 : : {
4881 : : // Test that 0x808.... & 0x8.... still contains 0x8....
4882 : : // for a large set of numbers.
4883 : 4 : {
4884 : 4 : int_range_max res;
4885 : 4 : tree big_type = long_long_unsigned_type_node;
4886 : 4 : unsigned big_prec = TYPE_PRECISION (big_type);
4887 : : // big_num = 0x808,0000,0000,0000
4888 : 4 : wide_int big_num = wi::lshift (wi::uhwi (0x808, big_prec),
4889 : 8 : wi::uhwi (48, big_prec));
4890 : 8 : op_bitwise_and.fold_range (res, big_type,
4891 : 8 : int_range <1> (big_type),
4892 : 8 : int_range <1> (big_type, big_num, big_num));
4893 : : // val = 0x8,0000,0000,0000
4894 : 4 : wide_int val = wi::lshift (wi::uhwi (8, big_prec),
4895 : 8 : wi::uhwi (48, big_prec));
4896 : 4 : ASSERT_TRUE (res.contains_p (val));
4897 : 4 : }
4898 : :
4899 : 4 : if (TYPE_PRECISION (unsigned_type_node) > 31)
4900 : : {
4901 : : // unsigned VARYING = op1 << 1 should be VARYING.
4902 : 4 : int_range<2> lhs (unsigned_type_node);
4903 : 4 : int_range<2> shift (unsigned_type_node, INT (1), INT (1));
4904 : 4 : int_range_max op1;
4905 : 4 : op_lshift.op1_range (op1, unsigned_type_node, lhs, shift);
4906 : 4 : ASSERT_TRUE (op1.varying_p ());
4907 : :
4908 : : // 0 = op1 << 1 should be [0,0], [0x8000000, 0x8000000].
4909 : 4 : int_range<2> zero (unsigned_type_node, UINT (0), UINT (0));
4910 : 4 : op_lshift.op1_range (op1, unsigned_type_node, zero, shift);
4911 : 4 : ASSERT_TRUE (op1.num_pairs () == 2);
4912 : : // Remove the [0,0] range.
4913 : 4 : op1.intersect (zero);
4914 : 4 : ASSERT_TRUE (op1.num_pairs () == 1);
4915 : : // op1 << 1 should be [0x8000,0x8000] << 1,
4916 : : // which should result in [0,0].
4917 : 4 : int_range_max result;
4918 : 4 : op_lshift.fold_range (result, unsigned_type_node, op1, shift);
4919 : 4 : ASSERT_TRUE (result == zero);
4920 : 4 : }
4921 : : // signed VARYING = op1 << 1 should be VARYING.
4922 : 4 : if (TYPE_PRECISION (integer_type_node) > 31)
4923 : : {
4924 : : // unsigned VARYING = op1 << 1 should be VARYING.
4925 : 4 : int_range<2> lhs (integer_type_node);
4926 : 4 : int_range<2> shift (integer_type_node, INT (1), INT (1));
4927 : 4 : int_range_max op1;
4928 : 4 : op_lshift.op1_range (op1, integer_type_node, lhs, shift);
4929 : 4 : ASSERT_TRUE (op1.varying_p ());
4930 : :
4931 : : // 0 = op1 << 1 should be [0,0], [0x8000000, 0x8000000].
4932 : 4 : int_range<2> zero (integer_type_node, INT (0), INT (0));
4933 : 4 : op_lshift.op1_range (op1, integer_type_node, zero, shift);
4934 : 4 : ASSERT_TRUE (op1.num_pairs () == 2);
4935 : : // Remove the [0,0] range.
4936 : 4 : op1.intersect (zero);
4937 : 4 : ASSERT_TRUE (op1.num_pairs () == 1);
4938 : : // op1 << 1 should be [0x8000,0x8000] << 1,
4939 : : // which should result in [0,0].
4940 : 4 : int_range_max result;
4941 : 4 : op_lshift.fold_range (result, unsigned_type_node, op1, shift);
4942 : 4 : ASSERT_TRUE (result == zero);
4943 : 4 : }
4944 : 4 : }
4945 : :
4946 : : static void
4947 : 4 : range_op_rshift_tests ()
4948 : : {
4949 : : // unsigned: [3, MAX] = OP1 >> 1
4950 : 4 : {
4951 : 4 : int_range_max lhs (unsigned_type_node,
4952 : 4 : UINT (3), max_limit (unsigned_type_node));
4953 : 4 : int_range_max one (unsigned_type_node,
4954 : 8 : wi::one (TYPE_PRECISION (unsigned_type_node)),
4955 : 8 : wi::one (TYPE_PRECISION (unsigned_type_node)));
4956 : 4 : int_range_max op1;
4957 : 4 : op_rshift.op1_range (op1, unsigned_type_node, lhs, one);
4958 : 4 : ASSERT_FALSE (op1.contains_p (UINT (3)));
4959 : 4 : }
4960 : :
4961 : : // signed: [3, MAX] = OP1 >> 1
4962 : 4 : {
4963 : 4 : int_range_max lhs (integer_type_node,
4964 : 4 : INT (3), max_limit (integer_type_node));
4965 : 4 : int_range_max one (integer_type_node, INT (1), INT (1));
4966 : 4 : int_range_max op1;
4967 : 4 : op_rshift.op1_range (op1, integer_type_node, lhs, one);
4968 : 4 : ASSERT_FALSE (op1.contains_p (INT (-2)));
4969 : 4 : }
4970 : :
4971 : : // This is impossible, so OP1 should be [].
4972 : : // signed: [MIN, MIN] = OP1 >> 1
4973 : 4 : {
4974 : 4 : int_range_max lhs (integer_type_node,
4975 : 4 : min_limit (integer_type_node),
4976 : 4 : min_limit (integer_type_node));
4977 : 4 : int_range_max one (integer_type_node, INT (1), INT (1));
4978 : 4 : int_range_max op1;
4979 : 4 : op_rshift.op1_range (op1, integer_type_node, lhs, one);
4980 : 4 : ASSERT_TRUE (op1.undefined_p ());
4981 : 4 : }
4982 : :
4983 : : // signed: ~[-1] = OP1 >> 31
4984 : 4 : if (TYPE_PRECISION (integer_type_node) > 31)
4985 : : {
4986 : 4 : int_range_max lhs (integer_type_node, INT (-1), INT (-1), VR_ANTI_RANGE);
4987 : 4 : int_range_max shift (integer_type_node, INT (31), INT (31));
4988 : 4 : int_range_max op1;
4989 : 4 : op_rshift.op1_range (op1, integer_type_node, lhs, shift);
4990 : 4 : int_range_max negatives = range_negatives (integer_type_node);
4991 : 4 : negatives.intersect (op1);
4992 : 4 : ASSERT_TRUE (negatives.undefined_p ());
4993 : 4 : }
4994 : 4 : }
4995 : :
4996 : : static void
4997 : 4 : range_op_bitwise_and_tests ()
4998 : : {
4999 : 4 : int_range_max res;
5000 : 4 : wide_int min = min_limit (integer_type_node);
5001 : 4 : wide_int max = max_limit (integer_type_node);
5002 : 4 : wide_int tiny = wi::add (min, wi::one (TYPE_PRECISION (integer_type_node)));
5003 : 4 : int_range_max i1 (integer_type_node, tiny, max);
5004 : 4 : int_range_max i2 (integer_type_node, INT (255), INT (255));
5005 : :
5006 : : // [MIN+1, MAX] = OP1 & 255: OP1 is VARYING
5007 : 4 : op_bitwise_and.op1_range (res, integer_type_node, i1, i2);
5008 : 4 : ASSERT_TRUE (res == int_range<1> (integer_type_node));
5009 : :
5010 : : // VARYING = OP1 & 255: OP1 is VARYING
5011 : 4 : i1 = int_range<1> (integer_type_node);
5012 : 4 : op_bitwise_and.op1_range (res, integer_type_node, i1, i2);
5013 : 4 : ASSERT_TRUE (res == int_range<1> (integer_type_node));
5014 : :
5015 : : // For 0 = x & MASK, x is ~MASK.
5016 : 4 : {
5017 : 4 : int_range<2> zero (integer_type_node, INT (0), INT (0));
5018 : 4 : int_range<2> mask = int_range<2> (integer_type_node, INT (7), INT (7));
5019 : 4 : op_bitwise_and.op1_range (res, integer_type_node, zero, mask);
5020 : 4 : wide_int inv = wi::shwi (~7U, TYPE_PRECISION (integer_type_node));
5021 : 4 : ASSERT_TRUE (res.get_nonzero_bits () == inv);
5022 : 4 : }
5023 : :
5024 : : // (NONZERO | X) is nonzero.
5025 : 4 : i1.set_nonzero (integer_type_node);
5026 : 4 : i2.set_varying (integer_type_node);
5027 : 4 : op_bitwise_or.fold_range (res, integer_type_node, i1, i2);
5028 : 4 : ASSERT_TRUE (res.nonzero_p ());
5029 : :
5030 : : // (NEGATIVE | X) is nonzero.
5031 : 4 : i1 = int_range<1> (integer_type_node, INT (-5), INT (-3));
5032 : 4 : i2.set_varying (integer_type_node);
5033 : 4 : op_bitwise_or.fold_range (res, integer_type_node, i1, i2);
5034 : 4 : ASSERT_FALSE (res.contains_p (INT (0)));
5035 : 4 : }
5036 : :
5037 : : static void
5038 : 4 : range_relational_tests ()
5039 : : {
5040 : 4 : int_range<2> lhs (unsigned_char_type_node);
5041 : 4 : int_range<2> op1 (unsigned_char_type_node, UCHAR (8), UCHAR (10));
5042 : 4 : int_range<2> op2 (unsigned_char_type_node, UCHAR (20), UCHAR (20));
5043 : :
5044 : : // Never wrapping additions mean LHS > OP1.
5045 : 4 : relation_kind code = op_plus.lhs_op1_relation (lhs, op1, op2, VREL_VARYING);
5046 : 4 : ASSERT_TRUE (code == VREL_GT);
5047 : :
5048 : : // Most wrapping additions mean nothing...
5049 : 4 : op1 = int_range<2> (unsigned_char_type_node, UCHAR (8), UCHAR (10));
5050 : 4 : op2 = int_range<2> (unsigned_char_type_node, UCHAR (0), UCHAR (255));
5051 : 4 : code = op_plus.lhs_op1_relation (lhs, op1, op2, VREL_VARYING);
5052 : 4 : ASSERT_TRUE (code == VREL_VARYING);
5053 : :
5054 : : // However, always wrapping additions mean LHS < OP1.
5055 : 4 : op1 = int_range<2> (unsigned_char_type_node, UCHAR (1), UCHAR (255));
5056 : 4 : op2 = int_range<2> (unsigned_char_type_node, UCHAR (255), UCHAR (255));
5057 : 4 : code = op_plus.lhs_op1_relation (lhs, op1, op2, VREL_VARYING);
5058 : 4 : ASSERT_TRUE (code == VREL_LT);
5059 : 4 : }
5060 : :
5061 : : void
5062 : 4 : range_op_tests ()
5063 : : {
5064 : 4 : range_op_rshift_tests ();
5065 : 4 : range_op_lshift_tests ();
5066 : 4 : range_op_bitwise_and_tests ();
5067 : 4 : range_op_cast_tests ();
5068 : 4 : range_relational_tests ();
5069 : :
5070 : 4 : extern void range_op_float_tests ();
5071 : 4 : range_op_float_tests ();
5072 : 4 : }
5073 : :
5074 : : } // namespace selftest
5075 : :
5076 : : #endif // CHECKING_P
|