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