1 /* Support routines for value ranges.
2 Copyright (C) 2019-2021 Free Software Foundation, Inc.
3 Major hacks by Aldy Hernandez <aldyh@redhat.com> and
4 Andrew MacLeod <amacleod@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 "tree.h"
27 #include "gimple.h"
28 #include "ssa.h"
29 #include "tree-pretty-print.h"
30 #include "fold-const.h"
31
32 // Here we copy between any two irange's. The ranges can be legacy or
33 // multi-ranges, and copying between any combination works correctly.
34
35 irange &
operator =(const irange & src)36 irange::operator= (const irange &src)
37 {
38 if (legacy_mode_p ())
39 {
40 copy_to_legacy (src);
41 return *this;
42 }
43 if (src.legacy_mode_p ())
44 {
45 copy_legacy_to_multi_range (src);
46 return *this;
47 }
48
49 unsigned x;
50 unsigned lim = src.m_num_ranges;
51 if (lim > m_max_ranges)
52 lim = m_max_ranges;
53
54 for (x = 0; x < lim * 2; ++x)
55 m_base[x] = src.m_base[x];
56
57 // If the range didn't fit, the last range should cover the rest.
58 if (lim != src.m_num_ranges)
59 m_base[x - 1] = src.m_base[src.m_num_ranges * 2 - 1];
60
61 m_num_ranges = lim;
62 return *this;
63 }
64
65 // Return TRUE if range is a multi-range that can be represented as a
66 // VR_ANTI_RANGE.
67
68 bool
maybe_anti_range() const69 irange::maybe_anti_range () const
70 {
71 tree ttype = type ();
72 unsigned int precision = TYPE_PRECISION (ttype);
73 signop sign = TYPE_SIGN (ttype);
74 return (num_pairs () > 1
75 && precision > 1
76 && lower_bound () == wi::min_value (precision, sign)
77 && upper_bound () == wi::max_value (precision, sign));
78 }
79
80 void
copy_legacy_to_multi_range(const irange & src)81 irange::copy_legacy_to_multi_range (const irange &src)
82 {
83 gcc_checking_assert (src.legacy_mode_p ());
84 gcc_checking_assert (!legacy_mode_p ());
85 if (src.undefined_p ())
86 set_undefined ();
87 else if (src.varying_p ())
88 set_varying (src.type ());
89 else
90 {
91 if (range_has_numeric_bounds_p (&src))
92 set (src.min (), src.max (), src.kind ());
93 else
94 {
95 value_range cst (src);
96 cst.normalize_symbolics ();
97 gcc_checking_assert (cst.varying_p () || cst.kind () == VR_RANGE);
98 set (cst.min (), cst.max ());
99 }
100 }
101 }
102
103 // Copy any type of irange into a legacy.
104
105 void
copy_to_legacy(const irange & src)106 irange::copy_to_legacy (const irange &src)
107 {
108 gcc_checking_assert (legacy_mode_p ());
109 // Copy legacy to legacy.
110 if (src.legacy_mode_p ())
111 {
112 m_num_ranges = src.m_num_ranges;
113 m_base[0] = src.m_base[0];
114 m_base[1] = src.m_base[1];
115 m_kind = src.m_kind;
116 return;
117 }
118 // Copy multi-range to legacy.
119 if (src.undefined_p ())
120 set_undefined ();
121 else if (src.varying_p ())
122 set_varying (src.type ());
123 else if (src.maybe_anti_range ())
124 {
125 int_range<3> r (src);
126 r.invert ();
127 // Use tree variants to save on tree -> wi -> tree conversions.
128 set (r.tree_lower_bound (0), r.tree_upper_bound (0), VR_ANTI_RANGE);
129 }
130 else
131 set (src.tree_lower_bound (), src.tree_upper_bound ());
132 }
133
134 // Swap MIN/MAX if they are out of order and adjust KIND appropriately.
135
136 static void
swap_out_of_order_endpoints(tree & min,tree & max,value_range_kind & kind)137 swap_out_of_order_endpoints (tree &min, tree &max, value_range_kind &kind)
138 {
139 gcc_checking_assert (kind != VR_UNDEFINED);
140 if (kind == VR_VARYING)
141 return;
142 /* Wrong order for min and max, to swap them and the VR type we need
143 to adjust them. */
144 if (tree_int_cst_lt (max, min))
145 {
146 tree one, tmp;
147
148 /* For one bit precision if max < min, then the swapped
149 range covers all values, so for VR_RANGE it is varying and
150 for VR_ANTI_RANGE empty range, so drop to varying as well. */
151 if (TYPE_PRECISION (TREE_TYPE (min)) == 1)
152 {
153 kind = VR_VARYING;
154 return;
155 }
156
157 one = build_int_cst (TREE_TYPE (min), 1);
158 tmp = int_const_binop (PLUS_EXPR, max, one);
159 max = int_const_binop (MINUS_EXPR, min, one);
160 min = tmp;
161
162 /* There's one corner case, if we had [C+1, C] before we now have
163 that again. But this represents an empty value range, so drop
164 to varying in this case. */
165 if (tree_int_cst_lt (max, min))
166 {
167 kind = VR_VARYING;
168 return;
169 }
170 kind = kind == VR_RANGE ? VR_ANTI_RANGE : VR_RANGE;
171 }
172 }
173
174 void
irange_set(tree min,tree max)175 irange::irange_set (tree min, tree max)
176 {
177 gcc_checking_assert (!POLY_INT_CST_P (min));
178 gcc_checking_assert (!POLY_INT_CST_P (max));
179
180 m_base[0] = min;
181 m_base[1] = max;
182 m_num_ranges = 1;
183 if (flag_checking)
184 verify_range ();
185 }
186
187 void
irange_set_1bit_anti_range(tree min,tree max)188 irange::irange_set_1bit_anti_range (tree min, tree max)
189 {
190 tree type = TREE_TYPE (min);
191 gcc_checking_assert (TYPE_PRECISION (type) == 1);
192
193 if (operand_equal_p (min, max))
194 {
195 // Since these are 1-bit quantities, they can only be [MIN,MIN]
196 // or [MAX,MAX].
197 if (vrp_val_is_min (min))
198 min = max = vrp_val_max (type);
199 else
200 min = max = vrp_val_min (type);
201 set (min, max);
202 }
203 else
204 {
205 // The only alternative is [MIN,MAX], which is the empty range.
206 set_undefined ();
207 }
208 if (flag_checking)
209 verify_range ();
210 }
211
212 void
irange_set_anti_range(tree min,tree max)213 irange::irange_set_anti_range (tree min, tree max)
214 {
215 gcc_checking_assert (!POLY_INT_CST_P (min));
216 gcc_checking_assert (!POLY_INT_CST_P (max));
217
218 if (TYPE_PRECISION (TREE_TYPE (min)) == 1)
219 {
220 irange_set_1bit_anti_range (min, max);
221 return;
222 }
223
224 // set an anti-range
225 tree type = TREE_TYPE (min);
226 signop sign = TYPE_SIGN (type);
227 int_range<2> type_range (type);
228 // Calculate INVERSE([I,J]) as [-MIN, I-1][J+1, +MAX].
229 m_num_ranges = 0;
230 wi::overflow_type ovf;
231
232 wide_int w_min = wi::to_wide (min);
233 if (wi::ne_p (w_min, type_range.lower_bound ()))
234 {
235 wide_int lim1 = wi::sub (w_min, 1, sign, &ovf);
236 gcc_checking_assert (ovf != wi::OVF_OVERFLOW);
237 m_base[0] = type_range.tree_lower_bound (0);
238 m_base[1] = wide_int_to_tree (type, lim1);
239 m_num_ranges = 1;
240 }
241 wide_int w_max = wi::to_wide (max);
242 if (wi::ne_p (w_max, type_range.upper_bound ()))
243 {
244 wide_int lim2 = wi::add (w_max, 1, sign, &ovf);
245 gcc_checking_assert (ovf != wi::OVF_OVERFLOW);
246 m_base[m_num_ranges * 2] = wide_int_to_tree (type, lim2);
247 m_base[m_num_ranges * 2 + 1] = type_range.tree_upper_bound (0);
248 ++m_num_ranges;
249 }
250 if (flag_checking)
251 verify_range ();
252 }
253
254 /* Set value range to the canonical form of {VRTYPE, MIN, MAX, EQUIV}.
255 This means adjusting VRTYPE, MIN and MAX representing the case of a
256 wrapping range with MAX < MIN covering [MIN, type_max] U [type_min, MAX]
257 as anti-rage ~[MAX+1, MIN-1]. Likewise for wrapping anti-ranges.
258 In corner cases where MAX+1 or MIN-1 wraps this will fall back
259 to varying.
260 This routine exists to ease canonicalization in the case where we
261 extract ranges from var + CST op limit. */
262
263 void
set(tree min,tree max,value_range_kind kind)264 irange::set (tree min, tree max, value_range_kind kind)
265 {
266 if (!legacy_mode_p ())
267 {
268 if (kind == VR_RANGE)
269 irange_set (min, max);
270 else
271 {
272 gcc_checking_assert (kind == VR_ANTI_RANGE);
273 irange_set_anti_range (min, max);
274 }
275 return;
276 }
277 if (kind == VR_UNDEFINED)
278 {
279 set_undefined ();
280 return;
281 }
282
283 if (kind == VR_VARYING
284 || POLY_INT_CST_P (min)
285 || POLY_INT_CST_P (max))
286 {
287 set_varying (TREE_TYPE (min));
288 return;
289 }
290
291 // Nothing to canonicalize for symbolic ranges.
292 if (TREE_CODE (min) != INTEGER_CST
293 || TREE_CODE (max) != INTEGER_CST)
294 {
295 m_kind = kind;
296 m_base[0] = min;
297 m_base[1] = max;
298 m_num_ranges = 1;
299 return;
300 }
301
302 swap_out_of_order_endpoints (min, max, kind);
303 if (kind == VR_VARYING)
304 {
305 set_varying (TREE_TYPE (min));
306 return;
307 }
308
309 // Anti-ranges that can be represented as ranges should be so.
310 if (kind == VR_ANTI_RANGE)
311 {
312 /* For -fstrict-enums we may receive out-of-range ranges so consider
313 values < -INF and values > INF as -INF/INF as well. */
314 bool is_min = vrp_val_is_min (min);
315 bool is_max = vrp_val_is_max (max);
316 tree type = TREE_TYPE (min);
317
318 if (is_min && is_max)
319 {
320 /* We cannot deal with empty ranges, drop to varying.
321 ??? This could be VR_UNDEFINED instead. */
322 set_varying (type);
323 return;
324 }
325 else if (TYPE_PRECISION (TREE_TYPE (min)) == 1
326 && (is_min || is_max))
327 {
328 /* Non-empty boolean ranges can always be represented
329 as a singleton range. */
330 if (is_min)
331 min = max = vrp_val_max (TREE_TYPE (min));
332 else
333 min = max = vrp_val_min (TREE_TYPE (min));
334 kind = VR_RANGE;
335 }
336 else if (is_min)
337 {
338 tree one = build_int_cst (TREE_TYPE (max), 1);
339 min = int_const_binop (PLUS_EXPR, max, one);
340 max = vrp_val_max (TREE_TYPE (max));
341 kind = VR_RANGE;
342 }
343 else if (is_max)
344 {
345 tree one = build_int_cst (TREE_TYPE (min), 1);
346 max = int_const_binop (MINUS_EXPR, min, one);
347 min = vrp_val_min (TREE_TYPE (min));
348 kind = VR_RANGE;
349 }
350 }
351
352 m_kind = kind;
353 m_base[0] = min;
354 m_base[1] = max;
355 m_num_ranges = 1;
356 normalize_min_max ();
357 if (flag_checking)
358 verify_range ();
359 }
360
361 // Check the validity of the range.
362
363 void
verify_range()364 irange::verify_range ()
365 {
366 if (!legacy_mode_p ())
367 {
368 gcc_checking_assert (m_kind == VR_RANGE);
369 for (unsigned i = 0; i < m_num_ranges; ++i)
370 {
371 tree lb = tree_lower_bound (i);
372 tree ub = tree_upper_bound (i);
373 int c = compare_values (lb, ub);
374 gcc_assert (c == 0 || c == -1);
375 }
376 return;
377 }
378
379 switch (m_kind)
380 {
381 case VR_UNDEFINED:
382 gcc_assert (m_num_ranges == 0);
383 break;
384
385 case VR_VARYING:
386 gcc_assert (m_num_ranges == 1);
387 break;
388
389 case VR_ANTI_RANGE:
390 case VR_RANGE:
391 {
392 gcc_assert (m_num_ranges == 1);
393 int cmp = compare_values (tree_lower_bound (0), tree_upper_bound (0));
394 gcc_assert (cmp == 0 || cmp == -1 || cmp == -2);
395 return;
396 }
397
398 default:
399 gcc_unreachable ();
400 }
401 }
402
403 unsigned
legacy_num_pairs() const404 irange::legacy_num_pairs () const
405 {
406 gcc_checking_assert (legacy_mode_p ());
407
408 if (undefined_p ())
409 return 0;
410 if (varying_p ())
411 return 1;
412 // Inlined symbolic_p for performance:
413 if (!is_gimple_min_invariant (min ()) || !is_gimple_min_invariant (max ()))
414 {
415 value_range numeric_range (*this);
416 numeric_range.normalize_symbolics ();
417 return numeric_range.num_pairs ();
418 }
419 if (m_kind == VR_ANTI_RANGE)
420 {
421 // ~[MIN, X] has one sub-range of [X+1, MAX], and
422 // ~[X, MAX] has one sub-range of [MIN, X-1].
423 if (vrp_val_is_min (min ()) || vrp_val_is_max (max ()))
424 return 1;
425 return 2;
426 }
427 gcc_checking_assert (m_num_ranges == 1);
428 return 1;
429 }
430
431 // Return the lower bound for a sub-range. PAIR is the sub-range in
432 // question.
433
434 wide_int
legacy_lower_bound(unsigned pair) const435 irange::legacy_lower_bound (unsigned pair) const
436 {
437 gcc_checking_assert (legacy_mode_p ());
438 if (symbolic_p ())
439 {
440 value_range numeric_range (*this);
441 numeric_range.normalize_symbolics ();
442 return numeric_range.legacy_lower_bound (pair);
443 }
444 gcc_checking_assert (!undefined_p ());
445 gcc_checking_assert (pair + 1 <= num_pairs ());
446 if (m_kind == VR_ANTI_RANGE)
447 {
448 tree typ = type (), t;
449 if (pair == 1 || vrp_val_is_min (min ()))
450 t = wide_int_to_tree (typ, wi::to_wide (max ()) + 1);
451 else
452 t = vrp_val_min (typ);
453 return wi::to_wide (t);
454 }
455 return wi::to_wide (tree_lower_bound (pair));
456 }
457
458 // Return the upper bound for a sub-range. PAIR is the sub-range in
459 // question.
460
461 wide_int
legacy_upper_bound(unsigned pair) const462 irange::legacy_upper_bound (unsigned pair) const
463 {
464 gcc_checking_assert (legacy_mode_p ());
465 if (symbolic_p ())
466 {
467 value_range numeric_range (*this);
468 numeric_range.normalize_symbolics ();
469 return numeric_range.legacy_upper_bound (pair);
470 }
471 gcc_checking_assert (!undefined_p ());
472 gcc_checking_assert (pair + 1 <= num_pairs ());
473 if (m_kind == VR_ANTI_RANGE)
474 {
475 tree typ = type (), t;
476 if (pair == 1 || vrp_val_is_min (min ()))
477 t = vrp_val_max (typ);
478 else
479 t = wide_int_to_tree (typ, wi::to_wide (min ()) - 1);
480 return wi::to_wide (t);
481 }
482 return wi::to_wide (tree_upper_bound (pair));
483 }
484
485 bool
legacy_equal_p(const irange & other) const486 irange::legacy_equal_p (const irange &other) const
487 {
488 gcc_checking_assert (legacy_mode_p () && other.legacy_mode_p ());
489
490 if (m_kind != other.m_kind)
491 return false;
492 if (m_kind == VR_UNDEFINED || m_kind == VR_VARYING)
493 return true;
494 return (vrp_operand_equal_p (tree_lower_bound (0),
495 other.tree_lower_bound (0))
496 && vrp_operand_equal_p (tree_upper_bound (0),
497 other.tree_upper_bound (0)));
498 }
499
500 bool
equal_p(const irange & other) const501 irange::equal_p (const irange &other) const
502 {
503 if (legacy_mode_p ())
504 {
505 if (other.legacy_mode_p ())
506 return legacy_equal_p (other);
507 value_range tmp (other);
508 return legacy_equal_p (tmp);
509 }
510 if (other.legacy_mode_p ())
511 {
512 value_range tmp2 (*this);
513 return tmp2.legacy_equal_p (other);
514 }
515
516 if (m_num_ranges != other.m_num_ranges)
517 return false;
518
519 for (unsigned i = 0; i < m_num_ranges; ++i)
520 {
521 tree lb = tree_lower_bound (i);
522 tree ub = tree_upper_bound (i);
523 tree lb_other = other.tree_lower_bound (i);
524 tree ub_other = other.tree_upper_bound (i);
525 if (!operand_equal_p (lb, lb_other, 0)
526 || !operand_equal_p (ub, ub_other, 0))
527 return false;
528 }
529 return true;
530 }
531
532 /* Return TRUE if this is a symbolic range. */
533
534 bool
symbolic_p() const535 irange::symbolic_p () const
536 {
537 return (!varying_p ()
538 && !undefined_p ()
539 && (!is_gimple_min_invariant (min ())
540 || !is_gimple_min_invariant (max ())));
541 }
542
543 /* NOTE: This is not the inverse of symbolic_p because the range
544 could also be varying or undefined. Ideally they should be inverse
545 of each other, with varying only applying to symbolics. Varying of
546 constants would be represented as [-MIN, +MAX]. */
547
548 bool
constant_p() const549 irange::constant_p () const
550 {
551 return (!varying_p ()
552 && !undefined_p ()
553 && TREE_CODE (min ()) == INTEGER_CST
554 && TREE_CODE (max ()) == INTEGER_CST);
555 }
556
557 /* If range is a singleton, place it in RESULT and return TRUE.
558 Note: A singleton can be any gimple invariant, not just constants.
559 So, [&x, &x] counts as a singleton. */
560
561 bool
singleton_p(tree * result) const562 irange::singleton_p (tree *result) const
563 {
564 if (!legacy_mode_p ())
565 {
566 if (num_pairs () == 1 && (wi::to_wide (tree_lower_bound ())
567 == wi::to_wide (tree_upper_bound ())))
568 {
569 if (result)
570 *result = tree_lower_bound ();
571 return true;
572 }
573 return false;
574 }
575 if (m_kind == VR_ANTI_RANGE)
576 {
577 if (nonzero_p ())
578 {
579 if (TYPE_PRECISION (type ()) == 1)
580 {
581 if (result)
582 *result = max ();
583 return true;
584 }
585 return false;
586 }
587 if (num_pairs () == 1)
588 {
589 value_range vr0, vr1;
590 ranges_from_anti_range ((const value_range *) this, &vr0, &vr1);
591 return vr0.singleton_p (result);
592 }
593 }
594 // Catches non-numeric extremes as well.
595 if (m_kind == VR_RANGE
596 && vrp_operand_equal_p (min (), max ())
597 && is_gimple_min_invariant (min ()))
598 {
599 if (result)
600 *result = min ();
601 return true;
602 }
603 return false;
604 }
605
606 /* Return 1 if VAL is inside value range.
607 0 if VAL is not inside value range.
608 -2 if we cannot tell either way.
609
610 Benchmark compile/20001226-1.c compilation time after changing this
611 function. */
612
613 int
value_inside_range(tree val) const614 irange::value_inside_range (tree val) const
615 {
616 if (varying_p ())
617 return 1;
618
619 if (undefined_p ())
620 return 0;
621
622 if (!legacy_mode_p () && TREE_CODE (val) == INTEGER_CST)
623 return contains_p (val);
624
625 int cmp1 = operand_less_p (val, min ());
626 if (cmp1 == -2)
627 return -2;
628 if (cmp1 == 1)
629 return m_kind != VR_RANGE;
630
631 int cmp2 = operand_less_p (max (), val);
632 if (cmp2 == -2)
633 return -2;
634
635 if (m_kind == VR_RANGE)
636 return !cmp2;
637 else
638 return !!cmp2;
639 }
640
641 /* Return TRUE if it is possible that range contains VAL. */
642
643 bool
may_contain_p(tree val) const644 irange::may_contain_p (tree val) const
645 {
646 return value_inside_range (val) != 0;
647 }
648
649 /* Return TRUE if range contains INTEGER_CST. */
650 /* Return 1 if VAL is inside value range.
651 0 if VAL is not inside value range.
652
653 Benchmark compile/20001226-1.c compilation time after changing this
654 function. */
655
656
657 bool
contains_p(tree cst) const658 irange::contains_p (tree cst) const
659 {
660 if (undefined_p ())
661 return false;
662
663 if (legacy_mode_p ())
664 {
665 gcc_checking_assert (TREE_CODE (cst) == INTEGER_CST);
666 if (symbolic_p ())
667 {
668 value_range numeric_range (*this);
669 numeric_range.normalize_symbolics ();
670 return numeric_range.contains_p (cst);
671 }
672 return value_inside_range (cst) == 1;
673 }
674
675 gcc_checking_assert (TREE_CODE (cst) == INTEGER_CST);
676 signop sign = TYPE_SIGN (TREE_TYPE (cst));
677 wide_int v = wi::to_wide (cst);
678 for (unsigned r = 0; r < m_num_ranges; ++r)
679 {
680 if (wi::lt_p (v, lower_bound (r), sign))
681 return false;
682 if (wi::le_p (v, upper_bound (r), sign))
683 return true;
684 }
685
686 return false;
687 }
688
689
690 /* Normalize addresses into constants. */
691
692 void
normalize_addresses()693 irange::normalize_addresses ()
694 {
695 if (undefined_p ())
696 return;
697
698 if (!POINTER_TYPE_P (type ()) || range_has_numeric_bounds_p (this))
699 return;
700
701 if (!range_includes_zero_p (this))
702 {
703 gcc_checking_assert (TREE_CODE (min ()) == ADDR_EXPR
704 || TREE_CODE (max ()) == ADDR_EXPR);
705 set_nonzero (type ());
706 return;
707 }
708 set_varying (type ());
709 }
710
711 /* Normalize symbolics and addresses into constants. */
712
713 void
normalize_symbolics()714 irange::normalize_symbolics ()
715 {
716 if (varying_p () || undefined_p ())
717 return;
718
719 tree ttype = type ();
720 bool min_symbolic = !is_gimple_min_invariant (min ());
721 bool max_symbolic = !is_gimple_min_invariant (max ());
722 if (!min_symbolic && !max_symbolic)
723 {
724 normalize_addresses ();
725 return;
726 }
727
728 // [SYM, SYM] -> VARYING
729 if (min_symbolic && max_symbolic)
730 {
731 set_varying (ttype);
732 return;
733 }
734 if (kind () == VR_RANGE)
735 {
736 // [SYM, NUM] -> [-MIN, NUM]
737 if (min_symbolic)
738 {
739 set (vrp_val_min (ttype), max ());
740 return;
741 }
742 // [NUM, SYM] -> [NUM, +MAX]
743 set (min (), vrp_val_max (ttype));
744 return;
745 }
746 gcc_checking_assert (kind () == VR_ANTI_RANGE);
747 // ~[SYM, NUM] -> [NUM + 1, +MAX]
748 if (min_symbolic)
749 {
750 if (!vrp_val_is_max (max ()))
751 {
752 tree n = wide_int_to_tree (ttype, wi::to_wide (max ()) + 1);
753 set (n, vrp_val_max (ttype));
754 return;
755 }
756 set_varying (ttype);
757 return;
758 }
759 // ~[NUM, SYM] -> [-MIN, NUM - 1]
760 if (!vrp_val_is_min (min ()))
761 {
762 tree n = wide_int_to_tree (ttype, wi::to_wide (min ()) - 1);
763 set (vrp_val_min (ttype), n);
764 return;
765 }
766 set_varying (ttype);
767 }
768
769 /* Intersect the two value-ranges { *VR0TYPE, *VR0MIN, *VR0MAX } and
770 { VR1TYPE, VR0MIN, VR0MAX } and store the result
771 in { *VR0TYPE, *VR0MIN, *VR0MAX }. This may not be the smallest
772 possible such range. The resulting range is not canonicalized. */
773
774 static void
intersect_ranges(enum value_range_kind * vr0type,tree * vr0min,tree * vr0max,enum value_range_kind vr1type,tree vr1min,tree vr1max)775 intersect_ranges (enum value_range_kind *vr0type,
776 tree *vr0min, tree *vr0max,
777 enum value_range_kind vr1type,
778 tree vr1min, tree vr1max)
779 {
780 bool mineq = vrp_operand_equal_p (*vr0min, vr1min);
781 bool maxeq = vrp_operand_equal_p (*vr0max, vr1max);
782
783 /* [] is vr0, () is vr1 in the following classification comments. */
784 if (mineq && maxeq)
785 {
786 /* [( )] */
787 if (*vr0type == vr1type)
788 /* Nothing to do for equal ranges. */
789 ;
790 else if ((*vr0type == VR_RANGE
791 && vr1type == VR_ANTI_RANGE)
792 || (*vr0type == VR_ANTI_RANGE
793 && vr1type == VR_RANGE))
794 {
795 /* For anti-range with range intersection the result is empty. */
796 *vr0type = VR_UNDEFINED;
797 *vr0min = NULL_TREE;
798 *vr0max = NULL_TREE;
799 }
800 else
801 gcc_unreachable ();
802 }
803 else if (operand_less_p (*vr0max, vr1min) == 1
804 || operand_less_p (vr1max, *vr0min) == 1)
805 {
806 /* [ ] ( ) or ( ) [ ]
807 If the ranges have an empty intersection, the result of the
808 intersect operation is the range for intersecting an
809 anti-range with a range or empty when intersecting two ranges. */
810 if (*vr0type == VR_RANGE
811 && vr1type == VR_ANTI_RANGE)
812 ;
813 else if (*vr0type == VR_ANTI_RANGE
814 && vr1type == VR_RANGE)
815 {
816 *vr0type = vr1type;
817 *vr0min = vr1min;
818 *vr0max = vr1max;
819 }
820 else if (*vr0type == VR_RANGE
821 && vr1type == VR_RANGE)
822 {
823 *vr0type = VR_UNDEFINED;
824 *vr0min = NULL_TREE;
825 *vr0max = NULL_TREE;
826 }
827 else if (*vr0type == VR_ANTI_RANGE
828 && vr1type == VR_ANTI_RANGE)
829 {
830 /* If the anti-ranges are adjacent to each other merge them. */
831 if (TREE_CODE (*vr0max) == INTEGER_CST
832 && TREE_CODE (vr1min) == INTEGER_CST
833 && operand_less_p (*vr0max, vr1min) == 1
834 && integer_onep (int_const_binop (MINUS_EXPR,
835 vr1min, *vr0max)))
836 *vr0max = vr1max;
837 else if (TREE_CODE (vr1max) == INTEGER_CST
838 && TREE_CODE (*vr0min) == INTEGER_CST
839 && operand_less_p (vr1max, *vr0min) == 1
840 && integer_onep (int_const_binop (MINUS_EXPR,
841 *vr0min, vr1max)))
842 *vr0min = vr1min;
843 /* Else arbitrarily take VR0. */
844 }
845 }
846 else if ((maxeq || operand_less_p (vr1max, *vr0max) == 1)
847 && (mineq || operand_less_p (*vr0min, vr1min) == 1))
848 {
849 /* [ ( ) ] or [( ) ] or [ ( )] */
850 if (*vr0type == VR_RANGE
851 && vr1type == VR_RANGE)
852 {
853 /* If both are ranges the result is the inner one. */
854 *vr0type = vr1type;
855 *vr0min = vr1min;
856 *vr0max = vr1max;
857 }
858 else if (*vr0type == VR_RANGE
859 && vr1type == VR_ANTI_RANGE)
860 {
861 /* Choose the right gap if the left one is empty. */
862 if (mineq)
863 {
864 if (TREE_CODE (vr1max) != INTEGER_CST)
865 *vr0min = vr1max;
866 else if (TYPE_PRECISION (TREE_TYPE (vr1max)) == 1
867 && !TYPE_UNSIGNED (TREE_TYPE (vr1max)))
868 *vr0min
869 = int_const_binop (MINUS_EXPR, vr1max,
870 build_int_cst (TREE_TYPE (vr1max), -1));
871 else
872 *vr0min
873 = int_const_binop (PLUS_EXPR, vr1max,
874 build_int_cst (TREE_TYPE (vr1max), 1));
875 }
876 /* Choose the left gap if the right one is empty. */
877 else if (maxeq)
878 {
879 if (TREE_CODE (vr1min) != INTEGER_CST)
880 *vr0max = vr1min;
881 else if (TYPE_PRECISION (TREE_TYPE (vr1min)) == 1
882 && !TYPE_UNSIGNED (TREE_TYPE (vr1min)))
883 *vr0max
884 = int_const_binop (PLUS_EXPR, vr1min,
885 build_int_cst (TREE_TYPE (vr1min), -1));
886 else
887 *vr0max
888 = int_const_binop (MINUS_EXPR, vr1min,
889 build_int_cst (TREE_TYPE (vr1min), 1));
890 }
891 /* Choose the anti-range if the range is effectively varying. */
892 else if (vrp_val_is_min (*vr0min)
893 && vrp_val_is_max (*vr0max))
894 {
895 *vr0type = vr1type;
896 *vr0min = vr1min;
897 *vr0max = vr1max;
898 }
899 /* Else choose the range. */
900 }
901 else if (*vr0type == VR_ANTI_RANGE
902 && vr1type == VR_ANTI_RANGE)
903 /* If both are anti-ranges the result is the outer one. */
904 ;
905 else if (*vr0type == VR_ANTI_RANGE
906 && vr1type == VR_RANGE)
907 {
908 /* The intersection is empty. */
909 *vr0type = VR_UNDEFINED;
910 *vr0min = NULL_TREE;
911 *vr0max = NULL_TREE;
912 }
913 else
914 gcc_unreachable ();
915 }
916 else if ((maxeq || operand_less_p (*vr0max, vr1max) == 1)
917 && (mineq || operand_less_p (vr1min, *vr0min) == 1))
918 {
919 /* ( [ ] ) or ([ ] ) or ( [ ]) */
920 if (*vr0type == VR_RANGE
921 && vr1type == VR_RANGE)
922 /* Choose the inner range. */
923 ;
924 else if (*vr0type == VR_ANTI_RANGE
925 && vr1type == VR_RANGE)
926 {
927 /* Choose the right gap if the left is empty. */
928 if (mineq)
929 {
930 *vr0type = VR_RANGE;
931 if (TREE_CODE (*vr0max) != INTEGER_CST)
932 *vr0min = *vr0max;
933 else if (TYPE_PRECISION (TREE_TYPE (*vr0max)) == 1
934 && !TYPE_UNSIGNED (TREE_TYPE (*vr0max)))
935 *vr0min
936 = int_const_binop (MINUS_EXPR, *vr0max,
937 build_int_cst (TREE_TYPE (*vr0max), -1));
938 else
939 *vr0min
940 = int_const_binop (PLUS_EXPR, *vr0max,
941 build_int_cst (TREE_TYPE (*vr0max), 1));
942 *vr0max = vr1max;
943 }
944 /* Choose the left gap if the right is empty. */
945 else if (maxeq)
946 {
947 *vr0type = VR_RANGE;
948 if (TREE_CODE (*vr0min) != INTEGER_CST)
949 *vr0max = *vr0min;
950 else if (TYPE_PRECISION (TREE_TYPE (*vr0min)) == 1
951 && !TYPE_UNSIGNED (TREE_TYPE (*vr0min)))
952 *vr0max
953 = int_const_binop (PLUS_EXPR, *vr0min,
954 build_int_cst (TREE_TYPE (*vr0min), -1));
955 else
956 *vr0max
957 = int_const_binop (MINUS_EXPR, *vr0min,
958 build_int_cst (TREE_TYPE (*vr0min), 1));
959 *vr0min = vr1min;
960 }
961 /* Choose the anti-range if the range is effectively varying. */
962 else if (vrp_val_is_min (vr1min)
963 && vrp_val_is_max (vr1max))
964 ;
965 /* Choose the anti-range if it is ~[0,0], that range is special
966 enough to special case when vr1's range is relatively wide.
967 At least for types bigger than int - this covers pointers
968 and arguments to functions like ctz. */
969 else if (*vr0min == *vr0max
970 && integer_zerop (*vr0min)
971 && ((TYPE_PRECISION (TREE_TYPE (*vr0min))
972 >= TYPE_PRECISION (integer_type_node))
973 || POINTER_TYPE_P (TREE_TYPE (*vr0min)))
974 && TREE_CODE (vr1max) == INTEGER_CST
975 && TREE_CODE (vr1min) == INTEGER_CST
976 && (wi::clz (wi::to_wide (vr1max) - wi::to_wide (vr1min))
977 < TYPE_PRECISION (TREE_TYPE (*vr0min)) / 2))
978 ;
979 /* Else choose the range. */
980 else
981 {
982 *vr0type = vr1type;
983 *vr0min = vr1min;
984 *vr0max = vr1max;
985 }
986 }
987 else if (*vr0type == VR_ANTI_RANGE
988 && vr1type == VR_ANTI_RANGE)
989 {
990 /* If both are anti-ranges the result is the outer one. */
991 *vr0type = vr1type;
992 *vr0min = vr1min;
993 *vr0max = vr1max;
994 }
995 else if (vr1type == VR_ANTI_RANGE
996 && *vr0type == VR_RANGE)
997 {
998 /* The intersection is empty. */
999 *vr0type = VR_UNDEFINED;
1000 *vr0min = NULL_TREE;
1001 *vr0max = NULL_TREE;
1002 }
1003 else
1004 gcc_unreachable ();
1005 }
1006 else if ((operand_less_p (vr1min, *vr0max) == 1
1007 || operand_equal_p (vr1min, *vr0max, 0))
1008 && operand_less_p (*vr0min, vr1min) == 1
1009 && operand_less_p (*vr0max, vr1max) == 1)
1010 {
1011 /* [ ( ] ) or [ ]( ) */
1012 if (*vr0type == VR_ANTI_RANGE
1013 && vr1type == VR_ANTI_RANGE)
1014 *vr0max = vr1max;
1015 else if (*vr0type == VR_RANGE
1016 && vr1type == VR_RANGE)
1017 *vr0min = vr1min;
1018 else if (*vr0type == VR_RANGE
1019 && vr1type == VR_ANTI_RANGE)
1020 {
1021 if (TREE_CODE (vr1min) == INTEGER_CST)
1022 *vr0max = int_const_binop (MINUS_EXPR, vr1min,
1023 build_int_cst (TREE_TYPE (vr1min), 1));
1024 else
1025 *vr0max = vr1min;
1026 }
1027 else if (*vr0type == VR_ANTI_RANGE
1028 && vr1type == VR_RANGE)
1029 {
1030 *vr0type = VR_RANGE;
1031 if (TREE_CODE (*vr0max) == INTEGER_CST)
1032 *vr0min = int_const_binop (PLUS_EXPR, *vr0max,
1033 build_int_cst (TREE_TYPE (*vr0max), 1));
1034 else
1035 *vr0min = *vr0max;
1036 *vr0max = vr1max;
1037 }
1038 else
1039 gcc_unreachable ();
1040 }
1041 else if ((operand_less_p (*vr0min, vr1max) == 1
1042 || operand_equal_p (*vr0min, vr1max, 0))
1043 && operand_less_p (vr1min, *vr0min) == 1
1044 && operand_less_p (vr1max, *vr0max) == 1)
1045 {
1046 /* ( [ ) ] or ( )[ ] */
1047 if (*vr0type == VR_ANTI_RANGE
1048 && vr1type == VR_ANTI_RANGE)
1049 *vr0min = vr1min;
1050 else if (*vr0type == VR_RANGE
1051 && vr1type == VR_RANGE)
1052 *vr0max = vr1max;
1053 else if (*vr0type == VR_RANGE
1054 && vr1type == VR_ANTI_RANGE)
1055 {
1056 if (TREE_CODE (vr1max) == INTEGER_CST)
1057 *vr0min = int_const_binop (PLUS_EXPR, vr1max,
1058 build_int_cst (TREE_TYPE (vr1max), 1));
1059 else
1060 *vr0min = vr1max;
1061 }
1062 else if (*vr0type == VR_ANTI_RANGE
1063 && vr1type == VR_RANGE)
1064 {
1065 *vr0type = VR_RANGE;
1066 if (TREE_CODE (*vr0min) == INTEGER_CST)
1067 *vr0max = int_const_binop (MINUS_EXPR, *vr0min,
1068 build_int_cst (TREE_TYPE (*vr0min), 1));
1069 else
1070 *vr0max = *vr0min;
1071 *vr0min = vr1min;
1072 }
1073 else
1074 gcc_unreachable ();
1075 }
1076
1077 /* If we know the intersection is empty, there's no need to
1078 conservatively add anything else to the set. */
1079 if (*vr0type == VR_UNDEFINED)
1080 return;
1081
1082 /* As a fallback simply use { *VRTYPE, *VR0MIN, *VR0MAX } as
1083 result for the intersection. That's always a conservative
1084 correct estimate unless VR1 is a constant singleton range
1085 in which case we choose that. */
1086 if (vr1type == VR_RANGE
1087 && is_gimple_min_invariant (vr1min)
1088 && vrp_operand_equal_p (vr1min, vr1max))
1089 {
1090 *vr0type = vr1type;
1091 *vr0min = vr1min;
1092 *vr0max = vr1max;
1093 }
1094 }
1095
1096 /* Helper for the intersection operation for value ranges. Given two
1097 ranges VR0 and VR1, set VR0 to the intersection of both ranges.
1098 This may not be the smallest possible such range. */
1099
1100 void
legacy_intersect(irange * vr0,const irange * vr1)1101 irange::legacy_intersect (irange *vr0, const irange *vr1)
1102 {
1103 gcc_checking_assert (vr0->legacy_mode_p ());
1104 gcc_checking_assert (vr1->legacy_mode_p ());
1105 /* If either range is VR_VARYING the other one wins. */
1106 if (vr1->varying_p ())
1107 return;
1108 if (vr0->varying_p ())
1109 {
1110 vr0->set (vr1->min (), vr1->max (), vr1->kind ());
1111 return;
1112 }
1113
1114 /* When either range is VR_UNDEFINED the resulting range is
1115 VR_UNDEFINED, too. */
1116 if (vr0->undefined_p ())
1117 return;
1118 if (vr1->undefined_p ())
1119 {
1120 vr0->set_undefined ();
1121 return;
1122 }
1123
1124 value_range_kind vr0kind = vr0->kind ();
1125 tree vr0min = vr0->min ();
1126 tree vr0max = vr0->max ();
1127
1128 intersect_ranges (&vr0kind, &vr0min, &vr0max,
1129 vr1->kind (), vr1->min (), vr1->max ());
1130
1131 /* Make sure to canonicalize the result though as the inversion of a
1132 VR_RANGE can still be a VR_RANGE. */
1133 if (vr0kind == VR_UNDEFINED)
1134 vr0->set_undefined ();
1135 else if (vr0kind == VR_VARYING)
1136 {
1137 /* If we failed, use the original VR0. */
1138 return;
1139 }
1140 else
1141 vr0->set (vr0min, vr0max, vr0kind);
1142 }
1143
1144 /* Union the two value-ranges { *VR0TYPE, *VR0MIN, *VR0MAX } and
1145 { VR1TYPE, VR0MIN, VR0MAX } and store the result
1146 in { *VR0TYPE, *VR0MIN, *VR0MAX }. This may not be the smallest
1147 possible such range. The resulting range is not canonicalized. */
1148
1149 static void
union_ranges(enum value_range_kind * vr0type,tree * vr0min,tree * vr0max,enum value_range_kind vr1type,tree vr1min,tree vr1max)1150 union_ranges (enum value_range_kind *vr0type,
1151 tree *vr0min, tree *vr0max,
1152 enum value_range_kind vr1type,
1153 tree vr1min, tree vr1max)
1154 {
1155 int cmpmin = compare_values (*vr0min, vr1min);
1156 int cmpmax = compare_values (*vr0max, vr1max);
1157 bool mineq = cmpmin == 0;
1158 bool maxeq = cmpmax == 0;
1159
1160 /* [] is vr0, () is vr1 in the following classification comments. */
1161 if (mineq && maxeq)
1162 {
1163 /* [( )] */
1164 if (*vr0type == vr1type)
1165 /* Nothing to do for equal ranges. */
1166 ;
1167 else if ((*vr0type == VR_RANGE
1168 && vr1type == VR_ANTI_RANGE)
1169 || (*vr0type == VR_ANTI_RANGE
1170 && vr1type == VR_RANGE))
1171 {
1172 /* For anti-range with range union the result is varying. */
1173 goto give_up;
1174 }
1175 else
1176 gcc_unreachable ();
1177 }
1178 else if (operand_less_p (*vr0max, vr1min) == 1
1179 || operand_less_p (vr1max, *vr0min) == 1)
1180 {
1181 /* [ ] ( ) or ( ) [ ]
1182 If the ranges have an empty intersection, result of the union
1183 operation is the anti-range or if both are anti-ranges
1184 it covers all. */
1185 if (*vr0type == VR_ANTI_RANGE
1186 && vr1type == VR_ANTI_RANGE)
1187 goto give_up;
1188 else if (*vr0type == VR_ANTI_RANGE
1189 && vr1type == VR_RANGE)
1190 ;
1191 else if (*vr0type == VR_RANGE
1192 && vr1type == VR_ANTI_RANGE)
1193 {
1194 *vr0type = vr1type;
1195 *vr0min = vr1min;
1196 *vr0max = vr1max;
1197 }
1198 else if (*vr0type == VR_RANGE
1199 && vr1type == VR_RANGE)
1200 {
1201 /* The result is the convex hull of both ranges. */
1202 if (operand_less_p (*vr0max, vr1min) == 1)
1203 {
1204 /* If the result can be an anti-range, create one. */
1205 if (TREE_CODE (*vr0max) == INTEGER_CST
1206 && TREE_CODE (vr1min) == INTEGER_CST
1207 && vrp_val_is_min (*vr0min)
1208 && vrp_val_is_max (vr1max))
1209 {
1210 tree min = int_const_binop (PLUS_EXPR,
1211 *vr0max,
1212 build_int_cst (TREE_TYPE (*vr0max), 1));
1213 tree max = int_const_binop (MINUS_EXPR,
1214 vr1min,
1215 build_int_cst (TREE_TYPE (vr1min), 1));
1216 if (!operand_less_p (max, min))
1217 {
1218 *vr0type = VR_ANTI_RANGE;
1219 *vr0min = min;
1220 *vr0max = max;
1221 }
1222 else
1223 *vr0max = vr1max;
1224 }
1225 else
1226 *vr0max = vr1max;
1227 }
1228 else
1229 {
1230 /* If the result can be an anti-range, create one. */
1231 if (TREE_CODE (vr1max) == INTEGER_CST
1232 && TREE_CODE (*vr0min) == INTEGER_CST
1233 && vrp_val_is_min (vr1min)
1234 && vrp_val_is_max (*vr0max))
1235 {
1236 tree min = int_const_binop (PLUS_EXPR,
1237 vr1max,
1238 build_int_cst (TREE_TYPE (vr1max), 1));
1239 tree max = int_const_binop (MINUS_EXPR,
1240 *vr0min,
1241 build_int_cst (TREE_TYPE (*vr0min), 1));
1242 if (!operand_less_p (max, min))
1243 {
1244 *vr0type = VR_ANTI_RANGE;
1245 *vr0min = min;
1246 *vr0max = max;
1247 }
1248 else
1249 *vr0min = vr1min;
1250 }
1251 else
1252 *vr0min = vr1min;
1253 }
1254 }
1255 else
1256 gcc_unreachable ();
1257 }
1258 else if ((maxeq || cmpmax == 1)
1259 && (mineq || cmpmin == -1))
1260 {
1261 /* [ ( ) ] or [( ) ] or [ ( )] */
1262 if (*vr0type == VR_RANGE
1263 && vr1type == VR_RANGE)
1264 ;
1265 else if (*vr0type == VR_ANTI_RANGE
1266 && vr1type == VR_ANTI_RANGE)
1267 {
1268 *vr0type = vr1type;
1269 *vr0min = vr1min;
1270 *vr0max = vr1max;
1271 }
1272 else if (*vr0type == VR_ANTI_RANGE
1273 && vr1type == VR_RANGE)
1274 {
1275 /* Arbitrarily choose the right or left gap. */
1276 if (!mineq && TREE_CODE (vr1min) == INTEGER_CST)
1277 *vr0max = int_const_binop (MINUS_EXPR, vr1min,
1278 build_int_cst (TREE_TYPE (vr1min), 1));
1279 else if (!maxeq && TREE_CODE (vr1max) == INTEGER_CST)
1280 *vr0min = int_const_binop (PLUS_EXPR, vr1max,
1281 build_int_cst (TREE_TYPE (vr1max), 1));
1282 else
1283 goto give_up;
1284 }
1285 else if (*vr0type == VR_RANGE
1286 && vr1type == VR_ANTI_RANGE)
1287 /* The result covers everything. */
1288 goto give_up;
1289 else
1290 gcc_unreachable ();
1291 }
1292 else if ((maxeq || cmpmax == -1)
1293 && (mineq || cmpmin == 1))
1294 {
1295 /* ( [ ] ) or ([ ] ) or ( [ ]) */
1296 if (*vr0type == VR_RANGE
1297 && vr1type == VR_RANGE)
1298 {
1299 *vr0type = vr1type;
1300 *vr0min = vr1min;
1301 *vr0max = vr1max;
1302 }
1303 else if (*vr0type == VR_ANTI_RANGE
1304 && vr1type == VR_ANTI_RANGE)
1305 ;
1306 else if (*vr0type == VR_RANGE
1307 && vr1type == VR_ANTI_RANGE)
1308 {
1309 *vr0type = VR_ANTI_RANGE;
1310 if (!mineq && TREE_CODE (*vr0min) == INTEGER_CST)
1311 {
1312 *vr0max = int_const_binop (MINUS_EXPR, *vr0min,
1313 build_int_cst (TREE_TYPE (*vr0min), 1));
1314 *vr0min = vr1min;
1315 }
1316 else if (!maxeq && TREE_CODE (*vr0max) == INTEGER_CST)
1317 {
1318 *vr0min = int_const_binop (PLUS_EXPR, *vr0max,
1319 build_int_cst (TREE_TYPE (*vr0max), 1));
1320 *vr0max = vr1max;
1321 }
1322 else
1323 goto give_up;
1324 }
1325 else if (*vr0type == VR_ANTI_RANGE
1326 && vr1type == VR_RANGE)
1327 /* The result covers everything. */
1328 goto give_up;
1329 else
1330 gcc_unreachable ();
1331 }
1332 else if (cmpmin == -1
1333 && cmpmax == -1
1334 && (operand_less_p (vr1min, *vr0max) == 1
1335 || operand_equal_p (vr1min, *vr0max, 0)))
1336 {
1337 /* [ ( ] ) or [ ]( ) */
1338 if (*vr0type == VR_RANGE
1339 && vr1type == VR_RANGE)
1340 *vr0max = vr1max;
1341 else if (*vr0type == VR_ANTI_RANGE
1342 && vr1type == VR_ANTI_RANGE)
1343 *vr0min = vr1min;
1344 else if (*vr0type == VR_ANTI_RANGE
1345 && vr1type == VR_RANGE)
1346 {
1347 if (TREE_CODE (vr1min) == INTEGER_CST)
1348 *vr0max = int_const_binop (MINUS_EXPR, vr1min,
1349 build_int_cst (TREE_TYPE (vr1min), 1));
1350 else
1351 goto give_up;
1352 }
1353 else if (*vr0type == VR_RANGE
1354 && vr1type == VR_ANTI_RANGE)
1355 {
1356 if (TREE_CODE (*vr0max) == INTEGER_CST)
1357 {
1358 *vr0type = vr1type;
1359 *vr0min = int_const_binop (PLUS_EXPR, *vr0max,
1360 build_int_cst (TREE_TYPE (*vr0max), 1));
1361 *vr0max = vr1max;
1362 }
1363 else
1364 goto give_up;
1365 }
1366 else
1367 gcc_unreachable ();
1368 }
1369 else if (cmpmin == 1
1370 && cmpmax == 1
1371 && (operand_less_p (*vr0min, vr1max) == 1
1372 || operand_equal_p (*vr0min, vr1max, 0)))
1373 {
1374 /* ( [ ) ] or ( )[ ] */
1375 if (*vr0type == VR_RANGE
1376 && vr1type == VR_RANGE)
1377 *vr0min = vr1min;
1378 else if (*vr0type == VR_ANTI_RANGE
1379 && vr1type == VR_ANTI_RANGE)
1380 *vr0max = vr1max;
1381 else if (*vr0type == VR_ANTI_RANGE
1382 && vr1type == VR_RANGE)
1383 {
1384 if (TREE_CODE (vr1max) == INTEGER_CST)
1385 *vr0min = int_const_binop (PLUS_EXPR, vr1max,
1386 build_int_cst (TREE_TYPE (vr1max), 1));
1387 else
1388 goto give_up;
1389 }
1390 else if (*vr0type == VR_RANGE
1391 && vr1type == VR_ANTI_RANGE)
1392 {
1393 if (TREE_CODE (*vr0min) == INTEGER_CST)
1394 {
1395 *vr0type = vr1type;
1396 *vr0max = int_const_binop (MINUS_EXPR, *vr0min,
1397 build_int_cst (TREE_TYPE (*vr0min), 1));
1398 *vr0min = vr1min;
1399 }
1400 else
1401 goto give_up;
1402 }
1403 else
1404 gcc_unreachable ();
1405 }
1406 else
1407 goto give_up;
1408
1409 return;
1410
1411 give_up:
1412 *vr0type = VR_VARYING;
1413 *vr0min = NULL_TREE;
1414 *vr0max = NULL_TREE;
1415 }
1416
1417 /* Helper for meet operation for value ranges. Given two ranges VR0
1418 and VR1, set VR0 to the union of both ranges. This may not be the
1419 smallest possible such range. */
1420
1421 void
legacy_union(irange * vr0,const irange * vr1)1422 irange::legacy_union (irange *vr0, const irange *vr1)
1423 {
1424 gcc_checking_assert (vr0->legacy_mode_p ());
1425 gcc_checking_assert (vr1->legacy_mode_p ());
1426
1427 /* VR0 has the resulting range if VR1 is undefined or VR0 is varying. */
1428 if (vr1->undefined_p ()
1429 || vr0->varying_p ())
1430 return;
1431
1432 /* VR1 has the resulting range if VR0 is undefined or VR1 is varying. */
1433 if (vr0->undefined_p ())
1434 {
1435 vr0->set (vr1->min (), vr1->max (), vr1->kind ());
1436 return;
1437 }
1438
1439 if (vr1->varying_p ())
1440 {
1441 vr0->set_varying (vr1->type ());
1442 return;
1443 }
1444
1445 value_range_kind vr0kind = vr0->kind ();
1446 tree vr0min = vr0->min ();
1447 tree vr0max = vr0->max ();
1448
1449 union_ranges (&vr0kind, &vr0min, &vr0max,
1450 vr1->kind (), vr1->min (), vr1->max ());
1451
1452 if (vr0kind == VR_UNDEFINED)
1453 vr0->set_undefined ();
1454 else if (vr0kind == VR_VARYING)
1455 {
1456 /* Failed to find an efficient meet. Before giving up and
1457 setting the result to VARYING, see if we can at least derive
1458 a non-zero range. */
1459 if (range_includes_zero_p (vr0) == 0
1460 && range_includes_zero_p (vr1) == 0)
1461 vr0->set_nonzero (vr0->type ());
1462 else
1463 vr0->set_varying (vr0->type ());
1464 }
1465 else
1466 vr0->set (vr0min, vr0max, vr0kind);
1467 }
1468
1469 /* Meet operation for value ranges. Given two value ranges VR0 and
1470 VR1, store in VR0 a range that contains both VR0 and VR1. This
1471 may not be the smallest possible such range. */
1472
1473 void
union_(const irange * other)1474 irange::union_ (const irange *other)
1475 {
1476 if (legacy_mode_p ())
1477 {
1478 if (!other->legacy_mode_p ())
1479 {
1480 int_range<1> tmp = *other;
1481 legacy_union (this, &tmp);
1482 return;
1483 }
1484 if (dump_file && (dump_flags & TDF_DETAILS))
1485 {
1486 fprintf (dump_file, "Meeting\n ");
1487 dump_value_range (dump_file, this);
1488 fprintf (dump_file, "\nand\n ");
1489 dump_value_range (dump_file, other);
1490 fprintf (dump_file, "\n");
1491 }
1492
1493 legacy_union (this, other);
1494
1495 if (dump_file && (dump_flags & TDF_DETAILS))
1496 {
1497 fprintf (dump_file, "to\n ");
1498 dump_value_range (dump_file, this);
1499 fprintf (dump_file, "\n");
1500 }
1501 return;
1502 }
1503
1504 if (other->legacy_mode_p ())
1505 {
1506 int_range<2> wider = *other;
1507 irange_union (wider);
1508 }
1509 else
1510 irange_union (*other);
1511 }
1512
1513 void
intersect(const irange * other)1514 irange::intersect (const irange *other)
1515 {
1516 if (legacy_mode_p ())
1517 {
1518 if (!other->legacy_mode_p ())
1519 {
1520 int_range<1> tmp = *other;
1521 legacy_intersect (this, &tmp);
1522 return;
1523 }
1524 if (dump_file && (dump_flags & TDF_DETAILS))
1525 {
1526 fprintf (dump_file, "Intersecting\n ");
1527 dump_value_range (dump_file, this);
1528 fprintf (dump_file, "\nand\n ");
1529 dump_value_range (dump_file, other);
1530 fprintf (dump_file, "\n");
1531 }
1532
1533 legacy_intersect (this, other);
1534
1535 if (dump_file && (dump_flags & TDF_DETAILS))
1536 {
1537 fprintf (dump_file, "to\n ");
1538 dump_value_range (dump_file, this);
1539 fprintf (dump_file, "\n");
1540 }
1541 return;
1542 }
1543
1544 if (other->legacy_mode_p ())
1545 {
1546 int_range<2> wider;
1547 wider = *other;
1548 irange_intersect (wider);
1549 }
1550 else
1551 irange_intersect (*other);
1552 }
1553
1554 // union_ for multi-ranges.
1555
1556 void
irange_union(const irange & r)1557 irange::irange_union (const irange &r)
1558 {
1559 gcc_checking_assert (!legacy_mode_p () && !r.legacy_mode_p ());
1560
1561 if (r.undefined_p () || varying_p ())
1562 return;
1563
1564 if (undefined_p () || r.varying_p ())
1565 {
1566 operator= (r);
1567 return;
1568 }
1569
1570 // Do not worry about merging and such by reserving twice as many
1571 // pairs as needed, and then simply sort the 2 ranges into this
1572 // intermediate form.
1573 //
1574 // The intermediate result will have the property that the beginning
1575 // of each range is <= the beginning of the next range. There may
1576 // be overlapping ranges at this point. I.e. this would be valid
1577 // [-20, 10], [-10, 0], [0, 20], [40, 90] as it satisfies this
1578 // contraint : -20 < -10 < 0 < 40. When the range is rebuilt into r,
1579 // the merge is performed.
1580 //
1581 // [Xi,Yi]..[Xn,Yn] U [Xj,Yj]..[Xm,Ym] --> [Xk,Yk]..[Xp,Yp]
1582 tree ttype = r.type ();
1583 signop sign = TYPE_SIGN (ttype);
1584
1585 auto_vec<tree, 20> res;
1586 wide_int u1 ;
1587 wi::overflow_type ovf;
1588 unsigned i = 0, j = 0, k = 0;
1589
1590 while (i < m_num_ranges * 2 && j < r.m_num_ranges * 2)
1591 {
1592 // lower of Xi and Xj is the lowest point.
1593 if (wi::le_p (wi::to_wide (m_base[i]), wi::to_wide (r.m_base[j]), sign))
1594 {
1595 res.safe_push (m_base[i]);
1596 res.safe_push (m_base[i + 1]);
1597 k += 2;
1598 i += 2;
1599 }
1600 else
1601 {
1602 res.safe_push (r.m_base[j]);
1603 res.safe_push (r.m_base[j + 1]);
1604 k += 2;
1605 j += 2;
1606 }
1607 }
1608 for ( ; i < m_num_ranges * 2; i += 2)
1609 {
1610 res.safe_push (m_base[i]);
1611 res.safe_push (m_base[i + 1]);
1612 k += 2;
1613 }
1614 for ( ; j < r.m_num_ranges * 2; j += 2)
1615 {
1616 res.safe_push (r.m_base[j]);
1617 res.safe_push (r.m_base[j + 1]);
1618 k += 2;
1619 }
1620
1621 // Now normalize the vector removing any overlaps.
1622 i = 2;
1623 int prec = TYPE_PRECISION (ttype);
1624 wide_int max_val = wi::max_value (prec, sign);
1625 for (j = 2; j < k ; j += 2)
1626 {
1627 wide_int val_im1 = wi::to_wide (res[i - 1]);
1628 if (val_im1 == max_val)
1629 break;
1630 u1 = wi::add (val_im1, 1, sign, &ovf);
1631
1632 // Overflow indicates we are at MAX already.
1633 // A wide int bug requires the previous max_val check
1634 // trigger: gcc.c-torture/compile/pr80443.c with -O3
1635 if (ovf == wi::OVF_OVERFLOW)
1636 break;
1637
1638 wide_int val_j = wi::to_wide (res[j]);
1639 wide_int val_jp1 = wi::to_wide (res[j+1]);
1640 // Current upper+1 is >= lower bound next pair, then we merge ranges.
1641 if (wi::ge_p (u1, val_j, sign))
1642 {
1643 // New upper bounds is greater of current or the next one.
1644 if (wi::gt_p (val_jp1, val_im1, sign))
1645 res [i - 1] = res[j + 1];
1646 }
1647 else
1648 {
1649 // This is a new distinct range, but no point in copying it
1650 // if it is already in the right place.
1651 if (i != j)
1652 {
1653 res[i++] = res[j];
1654 res[i++] = res[j + 1];
1655 }
1656 else
1657 i += 2;
1658 }
1659 }
1660
1661 // At this point, the vector should have i ranges, none overlapping.
1662 // Now it simply needs to be copied, and if there are too many
1663 // ranges, merge some. We wont do any analysis as to what the
1664 // "best" merges are, simply combine the final ranges into one.
1665 if (i > m_max_ranges * 2)
1666 {
1667 res[m_max_ranges * 2 - 1] = res[i - 1];
1668 i = m_max_ranges * 2;
1669 }
1670
1671 for (j = 0; j < i ; j++)
1672 m_base[j] = res [j];
1673 m_num_ranges = i / 2;
1674
1675 if (flag_checking)
1676 verify_range ();
1677 }
1678
1679 // intersect for multi-ranges.
1680
1681 void
irange_intersect(const irange & r)1682 irange::irange_intersect (const irange &r)
1683 {
1684 gcc_checking_assert (!legacy_mode_p () && !r.legacy_mode_p ());
1685
1686 if (undefined_p () || r.varying_p ())
1687 return;
1688 if (r.undefined_p ())
1689 {
1690 set_undefined ();
1691 return;
1692 }
1693 if (varying_p ())
1694 {
1695 operator= (r);
1696 return;
1697 }
1698
1699 signop sign = TYPE_SIGN (TREE_TYPE(m_base[0]));
1700 unsigned bld_pair = 0;
1701 unsigned bld_lim = m_max_ranges;
1702 int_range_max r2 (*this);
1703 unsigned r2_lim = r2.num_pairs ();
1704 unsigned i2 = 0;
1705 for (unsigned i = 0; i < r.num_pairs (); )
1706 {
1707 // If r1's upper is < r2's lower, we can skip r1's pair.
1708 tree ru = r.m_base[i * 2 + 1];
1709 tree r2l = r2.m_base[i2 * 2];
1710 if (wi::lt_p (wi::to_wide (ru), wi::to_wide (r2l), sign))
1711 {
1712 i++;
1713 continue;
1714 }
1715 // Likewise, skip r2's pair if its excluded.
1716 tree r2u = r2.m_base[i2 * 2 + 1];
1717 tree rl = r.m_base[i * 2];
1718 if (wi::lt_p (wi::to_wide (r2u), wi::to_wide (rl), sign))
1719 {
1720 i2++;
1721 if (i2 < r2_lim)
1722 continue;
1723 // No more r2, break.
1724 break;
1725 }
1726
1727 // Must be some overlap. Find the highest of the lower bounds,
1728 // and set it, unless the build limits lower bounds is already
1729 // set.
1730 if (bld_pair < bld_lim)
1731 {
1732 if (wi::ge_p (wi::to_wide (rl), wi::to_wide (r2l), sign))
1733 m_base[bld_pair * 2] = rl;
1734 else
1735 m_base[bld_pair * 2] = r2l;
1736 }
1737 else
1738 // Decrease and set a new upper.
1739 bld_pair--;
1740
1741 // ...and choose the lower of the upper bounds.
1742 if (wi::le_p (wi::to_wide (ru), wi::to_wide (r2u), sign))
1743 {
1744 m_base[bld_pair * 2 + 1] = ru;
1745 bld_pair++;
1746 // Move past the r1 pair and keep trying.
1747 i++;
1748 continue;
1749 }
1750 else
1751 {
1752 m_base[bld_pair * 2 + 1] = r2u;
1753 bld_pair++;
1754 i2++;
1755 if (i2 < r2_lim)
1756 continue;
1757 // No more r2, break.
1758 break;
1759 }
1760 // r2 has the higher lower bound.
1761 }
1762
1763 // At the exit of this loop, it is one of 2 things:
1764 // ran out of r1, or r2, but either means we are done.
1765 m_num_ranges = bld_pair;
1766 if (flag_checking)
1767 verify_range ();
1768 }
1769
1770 // Signed 1-bits are strange. You can't subtract 1, because you can't
1771 // represent the number 1. This works around that for the invert routine.
1772
1773 static wide_int inline
subtract_one(const wide_int & x,tree type,wi::overflow_type & overflow)1774 subtract_one (const wide_int &x, tree type, wi::overflow_type &overflow)
1775 {
1776 if (TYPE_SIGN (type) == SIGNED)
1777 return wi::add (x, -1, SIGNED, &overflow);
1778 else
1779 return wi::sub (x, 1, UNSIGNED, &overflow);
1780 }
1781
1782 // The analogous function for adding 1.
1783
1784 static wide_int inline
add_one(const wide_int & x,tree type,wi::overflow_type & overflow)1785 add_one (const wide_int &x, tree type, wi::overflow_type &overflow)
1786 {
1787 if (TYPE_SIGN (type) == SIGNED)
1788 return wi::sub (x, -1, SIGNED, &overflow);
1789 else
1790 return wi::add (x, 1, UNSIGNED, &overflow);
1791 }
1792
1793 // Return the inverse of a range.
1794
1795 void
invert()1796 irange::invert ()
1797 {
1798 if (legacy_mode_p ())
1799 {
1800 // We can't just invert VR_RANGE and VR_ANTI_RANGE because we may
1801 // create non-canonical ranges. Use the constructors instead.
1802 if (m_kind == VR_RANGE)
1803 *this = value_range (min (), max (), VR_ANTI_RANGE);
1804 else if (m_kind == VR_ANTI_RANGE)
1805 *this = value_range (min (), max ());
1806 else
1807 gcc_unreachable ();
1808 return;
1809 }
1810
1811 gcc_assert (!undefined_p () && !varying_p ());
1812
1813 // We always need one more set of bounds to represent an inverse, so
1814 // if we're at the limit, we can't properly represent things.
1815 //
1816 // For instance, to represent the inverse of a 2 sub-range set
1817 // [5, 10][20, 30], we would need a 3 sub-range set
1818 // [-MIN, 4][11, 19][31, MAX].
1819 //
1820 // In this case, return the most conservative thing.
1821 //
1822 // However, if any of the extremes of the range are -MIN/+MAX, we
1823 // know we will not need an extra bound. For example:
1824 //
1825 // INVERT([-MIN,20][30,40]) => [21,29][41,+MAX]
1826 // INVERT([-MIN,20][30,MAX]) => [21,29]
1827 tree ttype = type ();
1828 unsigned prec = TYPE_PRECISION (ttype);
1829 signop sign = TYPE_SIGN (ttype);
1830 wide_int type_min = wi::min_value (prec, sign);
1831 wide_int type_max = wi::max_value (prec, sign);
1832 if (m_num_ranges == m_max_ranges
1833 && lower_bound () != type_min
1834 && upper_bound () != type_max)
1835 {
1836 m_base[1] = wide_int_to_tree (ttype, type_max);
1837 m_num_ranges = 1;
1838 return;
1839 }
1840 // The algorithm is as follows. To calculate INVERT ([a,b][c,d]), we
1841 // generate [-MIN, a-1][b+1, c-1][d+1, MAX].
1842 //
1843 // If there is an over/underflow in the calculation for any
1844 // sub-range, we eliminate that subrange. This allows us to easily
1845 // calculate INVERT([-MIN, 5]) with: [-MIN, -MIN-1][6, MAX]. And since
1846 // we eliminate the underflow, only [6, MAX] remains.
1847 unsigned i = 0;
1848 wi::overflow_type ovf;
1849 // Construct leftmost range.
1850 int_range_max orig_range (*this);
1851 unsigned nitems = 0;
1852 wide_int tmp;
1853 // If this is going to underflow on the MINUS 1, don't even bother
1854 // checking. This also handles subtracting one from an unsigned 0,
1855 // which doesn't set the underflow bit.
1856 if (type_min != orig_range.lower_bound ())
1857 {
1858 m_base[nitems++] = wide_int_to_tree (ttype, type_min);
1859 tmp = subtract_one (orig_range.lower_bound (), ttype, ovf);
1860 m_base[nitems++] = wide_int_to_tree (ttype, tmp);
1861 if (ovf)
1862 nitems = 0;
1863 }
1864 i++;
1865 // Construct middle ranges if applicable.
1866 if (orig_range.num_pairs () > 1)
1867 {
1868 unsigned j = i;
1869 for (; j < (orig_range.num_pairs () * 2) - 1; j += 2)
1870 {
1871 // The middle ranges cannot have MAX/MIN, so there's no need
1872 // to check for unsigned overflow on the +1 and -1 here.
1873 tmp = wi::add (wi::to_wide (orig_range.m_base[j]), 1, sign, &ovf);
1874 m_base[nitems++] = wide_int_to_tree (ttype, tmp);
1875 tmp = subtract_one (wi::to_wide (orig_range.m_base[j + 1]),
1876 ttype, ovf);
1877 m_base[nitems++] = wide_int_to_tree (ttype, tmp);
1878 if (ovf)
1879 nitems -= 2;
1880 }
1881 i = j;
1882 }
1883 // Construct rightmost range.
1884 //
1885 // However, if this will overflow on the PLUS 1, don't even bother.
1886 // This also handles adding one to an unsigned MAX, which doesn't
1887 // set the overflow bit.
1888 if (type_max != wi::to_wide (orig_range.m_base[i]))
1889 {
1890 tmp = add_one (wi::to_wide (orig_range.m_base[i]), ttype, ovf);
1891 m_base[nitems++] = wide_int_to_tree (ttype, tmp);
1892 m_base[nitems++] = wide_int_to_tree (ttype, type_max);
1893 if (ovf)
1894 nitems -= 2;
1895 }
1896 m_num_ranges = nitems / 2;
1897
1898 if (flag_checking)
1899 verify_range ();
1900 }
1901
1902 static void
dump_bound_with_infinite_markers(FILE * file,tree bound)1903 dump_bound_with_infinite_markers (FILE *file, tree bound)
1904 {
1905 tree type = TREE_TYPE (bound);
1906 wide_int type_min = wi::min_value (TYPE_PRECISION (type), TYPE_SIGN (type));
1907 wide_int type_max = wi::max_value (TYPE_PRECISION (type), TYPE_SIGN (type));
1908
1909 if (INTEGRAL_TYPE_P (type)
1910 && !TYPE_UNSIGNED (type)
1911 && TREE_CODE (bound) == INTEGER_CST
1912 && wi::to_wide (bound) == type_min
1913 && TYPE_PRECISION (type) != 1)
1914 fprintf (file, "-INF");
1915 else if (TREE_CODE (bound) == INTEGER_CST
1916 && wi::to_wide (bound) == type_max
1917 && TYPE_PRECISION (type) != 1)
1918 fprintf (file, "+INF");
1919 else
1920 print_generic_expr (file, bound);
1921 }
1922
1923 void
dump(FILE * file) const1924 irange::dump (FILE *file) const
1925 {
1926 if (undefined_p ())
1927 {
1928 fprintf (file, "UNDEFINED");
1929 return;
1930 }
1931 print_generic_expr (file, type ());
1932 fprintf (file, " ");
1933 if (varying_p ())
1934 {
1935 fprintf (file, "VARYING");
1936 return;
1937 }
1938 if (legacy_mode_p ())
1939 {
1940 fprintf (file, "%s[", (m_kind == VR_ANTI_RANGE) ? "~" : "");
1941 dump_bound_with_infinite_markers (file, min ());
1942 fprintf (file, ", ");
1943 dump_bound_with_infinite_markers (file, max ());
1944 fprintf (file, "]");
1945 return;
1946 }
1947 for (unsigned i = 0; i < m_num_ranges; ++i)
1948 {
1949 tree lb = m_base[i * 2];
1950 tree ub = m_base[i * 2 + 1];
1951 fprintf (file, "[");
1952 dump_bound_with_infinite_markers (file, lb);
1953 fprintf (file, ", ");
1954 dump_bound_with_infinite_markers (file, ub);
1955 fprintf (file, "]");
1956 }
1957 }
1958
1959 void
dump_value_range(FILE * file,const irange * vr)1960 dump_value_range (FILE *file, const irange *vr)
1961 {
1962 vr->dump (file);
1963 }
1964
1965 DEBUG_FUNCTION void
debug(const irange * vr)1966 debug (const irange *vr)
1967 {
1968 dump_value_range (stderr, vr);
1969 fprintf (stderr, "\n");
1970 }
1971
1972 DEBUG_FUNCTION void
debug(const irange & vr)1973 debug (const irange &vr)
1974 {
1975 debug (&vr);
1976 }
1977
1978 DEBUG_FUNCTION void
debug(const value_range * vr)1979 debug (const value_range *vr)
1980 {
1981 dump_value_range (stderr, vr);
1982 fprintf (stderr, "\n");
1983 }
1984
1985 DEBUG_FUNCTION void
debug(const value_range & vr)1986 debug (const value_range &vr)
1987 {
1988 dump_value_range (stderr, &vr);
1989 fprintf (stderr, "\n");
1990 }
1991
1992 /* Create two value-ranges in *VR0 and *VR1 from the anti-range *AR
1993 so that *VR0 U *VR1 == *AR. Returns true if that is possible,
1994 false otherwise. If *AR can be represented with a single range
1995 *VR1 will be VR_UNDEFINED. */
1996
1997 bool
ranges_from_anti_range(const value_range * ar,value_range * vr0,value_range * vr1)1998 ranges_from_anti_range (const value_range *ar,
1999 value_range *vr0, value_range *vr1)
2000 {
2001 tree type = ar->type ();
2002
2003 vr0->set_undefined ();
2004 vr1->set_undefined ();
2005
2006 /* As a future improvement, we could handle ~[0, A] as: [-INF, -1] U
2007 [A+1, +INF]. Not sure if this helps in practice, though. */
2008
2009 if (ar->kind () != VR_ANTI_RANGE
2010 || TREE_CODE (ar->min ()) != INTEGER_CST
2011 || TREE_CODE (ar->max ()) != INTEGER_CST
2012 || !vrp_val_min (type)
2013 || !vrp_val_max (type))
2014 return false;
2015
2016 if (tree_int_cst_lt (vrp_val_min (type), ar->min ()))
2017 vr0->set (vrp_val_min (type),
2018 wide_int_to_tree (type, wi::to_wide (ar->min ()) - 1));
2019 if (tree_int_cst_lt (ar->max (), vrp_val_max (type)))
2020 vr1->set (wide_int_to_tree (type, wi::to_wide (ar->max ()) + 1),
2021 vrp_val_max (type));
2022 if (vr0->undefined_p ())
2023 {
2024 *vr0 = *vr1;
2025 vr1->set_undefined ();
2026 }
2027
2028 return !vr0->undefined_p ();
2029 }
2030
2031 bool
range_has_numeric_bounds_p(const irange * vr)2032 range_has_numeric_bounds_p (const irange *vr)
2033 {
2034 return (!vr->undefined_p ()
2035 && TREE_CODE (vr->min ()) == INTEGER_CST
2036 && TREE_CODE (vr->max ()) == INTEGER_CST);
2037 }
2038
2039 /* Return whether VAL is equal to the maximum value of its type.
2040 We can't do a simple equality comparison with TYPE_MAX_VALUE because
2041 C typedefs and Ada subtypes can produce types whose TYPE_MAX_VALUE
2042 is not == to the integer constant with the same value in the type. */
2043
2044 bool
vrp_val_is_max(const_tree val)2045 vrp_val_is_max (const_tree val)
2046 {
2047 tree type_max = vrp_val_max (TREE_TYPE (val));
2048 return (val == type_max
2049 || (type_max != NULL_TREE
2050 && operand_equal_p (val, type_max, 0)));
2051 }
2052
2053 /* Return whether VAL is equal to the minimum value of its type. */
2054
2055 bool
vrp_val_is_min(const_tree val)2056 vrp_val_is_min (const_tree val)
2057 {
2058 tree type_min = vrp_val_min (TREE_TYPE (val));
2059 return (val == type_min
2060 || (type_min != NULL_TREE
2061 && operand_equal_p (val, type_min, 0)));
2062 }
2063
2064 /* Return true, if VAL1 and VAL2 are equal values for VRP purposes. */
2065
2066 bool
vrp_operand_equal_p(const_tree val1,const_tree val2)2067 vrp_operand_equal_p (const_tree val1, const_tree val2)
2068 {
2069 if (val1 == val2)
2070 return true;
2071 if (!val1 || !val2 || !operand_equal_p (val1, val2, 0))
2072 return false;
2073 return true;
2074 }
2075
2076 #define DEFINE_INT_RANGE_GC_STUBS(N) \
2077 void \
2078 gt_pch_nx (int_range<N> *&x) \
2079 { \
2080 for (unsigned i = 0; i < N; ++i) \
2081 { \
2082 gt_pch_nx (x->m_ranges[i * 2]); \
2083 gt_pch_nx (x->m_ranges[i * 2 + 1]); \
2084 } \
2085 } \
2086 \
2087 void \
2088 gt_ggc_mx (int_range<N> *&x) \
2089 { \
2090 for (unsigned i = 0; i < N; ++i) \
2091 { \
2092 gt_ggc_mx (x->m_ranges[i * 2]); \
2093 gt_ggc_mx (x->m_ranges[i * 2 + 1]); \
2094 } \
2095 }
2096
2097 #define DEFINE_INT_RANGE_INSTANCE(N) \
2098 template int_range<N>::int_range(tree, tree, value_range_kind); \
2099 template int_range<N>::int_range(tree_node *, \
2100 const wide_int &, \
2101 const wide_int &, \
2102 value_range_kind); \
2103 template int_range<N>::int_range(tree); \
2104 template int_range<N>::int_range(const irange &); \
2105 template int_range<N>::int_range(const int_range &); \
2106 template int_range<N>& int_range<N>::operator= (const int_range &);
2107
2108 DEFINE_INT_RANGE_INSTANCE(1)
2109 DEFINE_INT_RANGE_INSTANCE(2)
2110 DEFINE_INT_RANGE_INSTANCE(3)
2111 DEFINE_INT_RANGE_INSTANCE(255)
2112 DEFINE_INT_RANGE_GC_STUBS(1)
2113
2114 #if CHECKING_P
2115 #include "selftest.h"
2116
2117 namespace selftest
2118 {
2119 #define INT(N) build_int_cst (integer_type_node, (N))
2120 #define UINT(N) build_int_cstu (unsigned_type_node, (N))
2121 #define UINT128(N) build_int_cstu (u128_type, (N))
2122 #define UCHAR(N) build_int_cstu (unsigned_char_type_node, (N))
2123 #define SCHAR(N) build_int_cst (signed_char_type_node, (N))
2124
2125 static int_range<3>
build_range3(int a,int b,int c,int d,int e,int f)2126 build_range3 (int a, int b, int c, int d, int e, int f)
2127 {
2128 int_range<3> i1 (INT (a), INT (b));
2129 int_range<3> i2 (INT (c), INT (d));
2130 int_range<3> i3 (INT (e), INT (f));
2131 i1.union_ (i2);
2132 i1.union_ (i3);
2133 return i1;
2134 }
2135
2136 static void
range_tests_irange3()2137 range_tests_irange3 ()
2138 {
2139 typedef int_range<3> int_range3;
2140 int_range3 r0, r1, r2;
2141 int_range3 i1, i2, i3;
2142
2143 // ([10,20] U [5,8]) U [1,3] ==> [1,3][5,8][10,20].
2144 r0 = int_range3 (INT (10), INT (20));
2145 r1 = int_range3 (INT (5), INT (8));
2146 r0.union_ (r1);
2147 r1 = int_range3 (INT (1), INT (3));
2148 r0.union_ (r1);
2149 ASSERT_TRUE (r0 == build_range3 (1, 3, 5, 8, 10, 20));
2150
2151 // [1,3][5,8][10,20] U [-5,0] => [-5,3][5,8][10,20].
2152 r1 = int_range3 (INT (-5), INT (0));
2153 r0.union_ (r1);
2154 ASSERT_TRUE (r0 == build_range3 (-5, 3, 5, 8, 10, 20));
2155
2156 // [10,20][30,40] U [50,60] ==> [10,20][30,40][50,60].
2157 r1 = int_range3 (INT (50), INT (60));
2158 r0 = int_range3 (INT (10), INT (20));
2159 r0.union_ (int_range3 (INT (30), INT (40)));
2160 r0.union_ (r1);
2161 ASSERT_TRUE (r0 == build_range3 (10, 20, 30, 40, 50, 60));
2162 // [10,20][30,40][50,60] U [70, 80] ==> [10,20][30,40][50,60][70,80].
2163 r1 = int_range3 (INT (70), INT (80));
2164 r0.union_ (r1);
2165
2166 r2 = build_range3 (10, 20, 30, 40, 50, 60);
2167 r2.union_ (int_range3 (INT (70), INT (80)));
2168 ASSERT_TRUE (r0 == r2);
2169
2170 // [10,20][30,40][50,60] U [6,35] => [6,40][50,60].
2171 r0 = build_range3 (10, 20, 30, 40, 50, 60);
2172 r1 = int_range3 (INT (6), INT (35));
2173 r0.union_ (r1);
2174 r1 = int_range3 (INT (6), INT (40));
2175 r1.union_ (int_range3 (INT (50), INT (60)));
2176 ASSERT_TRUE (r0 == r1);
2177
2178 // [10,20][30,40][50,60] U [6,60] => [6,60].
2179 r0 = build_range3 (10, 20, 30, 40, 50, 60);
2180 r1 = int_range3 (INT (6), INT (60));
2181 r0.union_ (r1);
2182 ASSERT_TRUE (r0 == int_range3 (INT (6), INT (60)));
2183
2184 // [10,20][30,40][50,60] U [6,70] => [6,70].
2185 r0 = build_range3 (10, 20, 30, 40, 50, 60);
2186 r1 = int_range3 (INT (6), INT (70));
2187 r0.union_ (r1);
2188 ASSERT_TRUE (r0 == int_range3 (INT (6), INT (70)));
2189
2190 // [10,20][30,40][50,60] U [35,70] => [10,20][30,70].
2191 r0 = build_range3 (10, 20, 30, 40, 50, 60);
2192 r1 = int_range3 (INT (35), INT (70));
2193 r0.union_ (r1);
2194 r1 = int_range3 (INT (10), INT (20));
2195 r1.union_ (int_range3 (INT (30), INT (70)));
2196 ASSERT_TRUE (r0 == r1);
2197
2198 // [10,20][30,40][50,60] U [15,35] => [10,40][50,60].
2199 r0 = build_range3 (10, 20, 30, 40, 50, 60);
2200 r1 = int_range3 (INT (15), INT (35));
2201 r0.union_ (r1);
2202 r1 = int_range3 (INT (10), INT (40));
2203 r1.union_ (int_range3 (INT (50), INT (60)));
2204 ASSERT_TRUE (r0 == r1);
2205
2206 // [10,20][30,40][50,60] U [35,35] => [10,20][30,40][50,60].
2207 r0 = build_range3 (10, 20, 30, 40, 50, 60);
2208 r1 = int_range3 (INT (35), INT (35));
2209 r0.union_ (r1);
2210 ASSERT_TRUE (r0 == build_range3 (10, 20, 30, 40, 50, 60));
2211 }
2212
2213 static void
range_tests_int_range_max()2214 range_tests_int_range_max ()
2215 {
2216 int_range_max big;
2217 unsigned int nrange;
2218
2219 // Build a huge multi-range range.
2220 for (nrange = 0; nrange < 50; ++nrange)
2221 {
2222 int_range<1> tmp (INT (nrange*10), INT (nrange*10 + 5));
2223 big.union_ (tmp);
2224 }
2225 ASSERT_TRUE (big.num_pairs () == nrange);
2226
2227 // Verify that we can copy it without loosing precision.
2228 int_range_max copy (big);
2229 ASSERT_TRUE (copy.num_pairs () == nrange);
2230
2231 // Inverting it should produce one more sub-range.
2232 big.invert ();
2233 ASSERT_TRUE (big.num_pairs () == nrange + 1);
2234
2235 int_range<1> tmp (INT (5), INT (37));
2236 big.intersect (tmp);
2237 ASSERT_TRUE (big.num_pairs () == 4);
2238
2239 // Test that [10,10][20,20] does NOT contain 15.
2240 {
2241 int_range_max i1 (build_int_cst (integer_type_node, 10),
2242 build_int_cst (integer_type_node, 10));
2243 int_range_max i2 (build_int_cst (integer_type_node, 20),
2244 build_int_cst (integer_type_node, 20));
2245 i1.union_ (i2);
2246 ASSERT_FALSE (i1.contains_p (build_int_cst (integer_type_node, 15)));
2247 }
2248 }
2249
2250 static void
range_tests_legacy()2251 range_tests_legacy ()
2252 {
2253 // Test truncating copy to int_range<1>.
2254 int_range<3> big = build_range3 (10, 20, 30, 40, 50, 60);
2255 int_range<1> small = big;
2256 ASSERT_TRUE (small == int_range<1> (INT (10), INT (60)));
2257
2258 // Test truncating copy to int_range<2>.
2259 int_range<2> medium = big;
2260 ASSERT_TRUE (!medium.undefined_p ());
2261
2262 // Test that a truncating copy of [MIN,20][22,40][80,MAX]
2263 // ends up as a conservative anti-range of ~[21,21].
2264 big = int_range<3> (vrp_val_min (integer_type_node), INT (20));
2265 big.union_ (int_range<1> (INT (22), INT (40)));
2266 big.union_ (int_range<1> (INT (80), vrp_val_max (integer_type_node)));
2267 small = big;
2268 ASSERT_TRUE (small == int_range<1> (INT (21), INT (21), VR_ANTI_RANGE));
2269
2270 // Copying a legacy symbolic to an int_range should normalize the
2271 // symbolic at copy time.
2272 {
2273 tree ssa = make_ssa_name (integer_type_node);
2274 value_range legacy_range (ssa, INT (25));
2275 int_range<2> copy = legacy_range;
2276 ASSERT_TRUE (copy == int_range<2> (vrp_val_min (integer_type_node),
2277 INT (25)));
2278
2279 // Test that copying ~[abc_23, abc_23] to a multi-range yields varying.
2280 legacy_range = value_range (ssa, ssa, VR_ANTI_RANGE);
2281 copy = legacy_range;
2282 ASSERT_TRUE (copy.varying_p ());
2283 }
2284 }
2285
2286 // Simulate -fstrict-enums where the domain of a type is less than the
2287 // underlying type.
2288
2289 static void
range_tests_strict_enum()2290 range_tests_strict_enum ()
2291 {
2292 // The enum can only hold [0, 3].
2293 tree rtype = copy_node (unsigned_type_node);
2294 TYPE_MIN_VALUE (rtype) = build_int_cstu (rtype, 0);
2295 TYPE_MAX_VALUE (rtype) = build_int_cstu (rtype, 3);
2296
2297 // Test that even though vr1 covers the strict enum domain ([0, 3]),
2298 // it does not cover the domain of the underlying type.
2299 int_range<1> vr1 (build_int_cstu (rtype, 0), build_int_cstu (rtype, 1));
2300 int_range<1> vr2 (build_int_cstu (rtype, 2), build_int_cstu (rtype, 3));
2301 vr1.union_ (vr2);
2302 ASSERT_TRUE (vr1 == int_range<1> (build_int_cstu (rtype, 0),
2303 build_int_cstu (rtype, 3)));
2304 ASSERT_FALSE (vr1.varying_p ());
2305
2306 // Test that copying to a multi-range does not change things.
2307 int_range<2> ir1 (vr1);
2308 ASSERT_TRUE (ir1 == vr1);
2309 ASSERT_FALSE (ir1.varying_p ());
2310
2311 // The same test as above, but using TYPE_{MIN,MAX}_VALUE instead of [0,3].
2312 vr1 = int_range<1> (TYPE_MIN_VALUE (rtype), TYPE_MAX_VALUE (rtype));
2313 ir1 = vr1;
2314 ASSERT_TRUE (ir1 == vr1);
2315 ASSERT_FALSE (ir1.varying_p ());
2316 }
2317
2318 static void
range_tests_misc()2319 range_tests_misc ()
2320 {
2321 tree u128_type = build_nonstandard_integer_type (128, /*unsigned=*/1);
2322 int_range<1> i1, i2, i3;
2323 int_range<1> r0, r1, rold;
2324
2325 // Test 1-bit signed integer union.
2326 // [-1,-1] U [0,0] = VARYING.
2327 tree one_bit_type = build_nonstandard_integer_type (1, 0);
2328 tree one_bit_min = vrp_val_min (one_bit_type);
2329 tree one_bit_max = vrp_val_max (one_bit_type);
2330 {
2331 int_range<2> min (one_bit_min, one_bit_min);
2332 int_range<2> max (one_bit_max, one_bit_max);
2333 max.union_ (min);
2334 ASSERT_TRUE (max.varying_p ());
2335 }
2336
2337 // Test inversion of 1-bit signed integers.
2338 {
2339 int_range<2> min (one_bit_min, one_bit_min);
2340 int_range<2> max (one_bit_max, one_bit_max);
2341 int_range<2> t;
2342 t = min;
2343 t.invert ();
2344 ASSERT_TRUE (t == max);
2345 t = max;
2346 t.invert ();
2347 ASSERT_TRUE (t == min);
2348 }
2349
2350 // Test that NOT(255) is [0..254] in 8-bit land.
2351 int_range<1> not_255 (UCHAR (255), UCHAR (255), VR_ANTI_RANGE);
2352 ASSERT_TRUE (not_255 == int_range<1> (UCHAR (0), UCHAR (254)));
2353
2354 // Test that NOT(0) is [1..255] in 8-bit land.
2355 int_range<1> not_zero = range_nonzero (unsigned_char_type_node);
2356 ASSERT_TRUE (not_zero == int_range<1> (UCHAR (1), UCHAR (255)));
2357
2358 // Check that [0,127][0x..ffffff80,0x..ffffff]
2359 // => ~[128, 0x..ffffff7f].
2360 r0 = int_range<1> (UINT128 (0), UINT128 (127));
2361 tree high = build_minus_one_cst (u128_type);
2362 // low = -1 - 127 => 0x..ffffff80.
2363 tree low = fold_build2 (MINUS_EXPR, u128_type, high, UINT128(127));
2364 r1 = int_range<1> (low, high); // [0x..ffffff80, 0x..ffffffff]
2365 // r0 = [0,127][0x..ffffff80,0x..fffffff].
2366 r0.union_ (r1);
2367 // r1 = [128, 0x..ffffff7f].
2368 r1 = int_range<1> (UINT128(128),
2369 fold_build2 (MINUS_EXPR, u128_type,
2370 build_minus_one_cst (u128_type),
2371 UINT128(128)));
2372 r0.invert ();
2373 ASSERT_TRUE (r0 == r1);
2374
2375 r0.set_varying (integer_type_node);
2376 tree minint = wide_int_to_tree (integer_type_node, r0.lower_bound ());
2377 tree maxint = wide_int_to_tree (integer_type_node, r0.upper_bound ());
2378
2379 r0.set_varying (short_integer_type_node);
2380
2381 r0.set_varying (unsigned_type_node);
2382 tree maxuint = wide_int_to_tree (unsigned_type_node, r0.upper_bound ());
2383
2384 // Check that ~[0,5] => [6,MAX] for unsigned int.
2385 r0 = int_range<1> (UINT (0), UINT (5));
2386 r0.invert ();
2387 ASSERT_TRUE (r0 == int_range<1> (UINT(6), maxuint));
2388
2389 // Check that ~[10,MAX] => [0,9] for unsigned int.
2390 r0 = int_range<1> (UINT(10), maxuint);
2391 r0.invert ();
2392 ASSERT_TRUE (r0 == int_range<1> (UINT (0), UINT (9)));
2393
2394 // Check that ~[0,5] => [6,MAX] for unsigned 128-bit numbers.
2395 r0 = int_range<1> (UINT128 (0), UINT128 (5), VR_ANTI_RANGE);
2396 r1 = int_range<1> (UINT128(6), build_minus_one_cst (u128_type));
2397 ASSERT_TRUE (r0 == r1);
2398
2399 // Check that [~5] is really [-MIN,4][6,MAX].
2400 r0 = int_range<1> (INT (5), INT (5), VR_ANTI_RANGE);
2401 r1 = int_range<1> (minint, INT (4));
2402 r1.union_ (int_range<1> (INT (6), maxint));
2403 ASSERT_FALSE (r1.undefined_p ());
2404 ASSERT_TRUE (r0 == r1);
2405
2406 r1 = int_range<1> (INT (5), INT (5));
2407 int_range<1> r2 (r1);
2408 ASSERT_TRUE (r1 == r2);
2409
2410 r1 = int_range<1> (INT (5), INT (10));
2411
2412 r1 = int_range<1> (integer_type_node,
2413 wi::to_wide (INT (5)), wi::to_wide (INT (10)));
2414 ASSERT_TRUE (r1.contains_p (INT (7)));
2415
2416 r1 = int_range<1> (SCHAR (0), SCHAR (20));
2417 ASSERT_TRUE (r1.contains_p (SCHAR(15)));
2418 ASSERT_FALSE (r1.contains_p (SCHAR(300)));
2419
2420 // NOT([10,20]) ==> [-MIN,9][21,MAX].
2421 r0 = r1 = int_range<1> (INT (10), INT (20));
2422 r2 = int_range<1> (minint, INT(9));
2423 r2.union_ (int_range<1> (INT(21), maxint));
2424 ASSERT_FALSE (r2.undefined_p ());
2425 r1.invert ();
2426 ASSERT_TRUE (r1 == r2);
2427 // Test that NOT(NOT(x)) == x.
2428 r2.invert ();
2429 ASSERT_TRUE (r0 == r2);
2430
2431 // Test that booleans and their inverse work as expected.
2432 r0 = range_zero (boolean_type_node);
2433 ASSERT_TRUE (r0 == int_range<1> (build_zero_cst (boolean_type_node),
2434 build_zero_cst (boolean_type_node)));
2435 r0.invert ();
2436 ASSERT_TRUE (r0 == int_range<1> (build_one_cst (boolean_type_node),
2437 build_one_cst (boolean_type_node)));
2438
2439 // Make sure NULL and non-NULL of pointer types work, and that
2440 // inverses of them are consistent.
2441 tree voidp = build_pointer_type (void_type_node);
2442 r0 = range_zero (voidp);
2443 r1 = r0;
2444 r0.invert ();
2445 r0.invert ();
2446 ASSERT_TRUE (r0 == r1);
2447
2448 // [10,20] U [15, 30] => [10, 30].
2449 r0 = int_range<1> (INT (10), INT (20));
2450 r1 = int_range<1> (INT (15), INT (30));
2451 r0.union_ (r1);
2452 ASSERT_TRUE (r0 == int_range<1> (INT (10), INT (30)));
2453
2454 // [15,40] U [] => [15,40].
2455 r0 = int_range<1> (INT (15), INT (40));
2456 r1.set_undefined ();
2457 r0.union_ (r1);
2458 ASSERT_TRUE (r0 == int_range<1> (INT (15), INT (40)));
2459
2460 // [10,20] U [10,10] => [10,20].
2461 r0 = int_range<1> (INT (10), INT (20));
2462 r1 = int_range<1> (INT (10), INT (10));
2463 r0.union_ (r1);
2464 ASSERT_TRUE (r0 == int_range<1> (INT (10), INT (20)));
2465
2466 // [10,20] U [9,9] => [9,20].
2467 r0 = int_range<1> (INT (10), INT (20));
2468 r1 = int_range<1> (INT (9), INT (9));
2469 r0.union_ (r1);
2470 ASSERT_TRUE (r0 == int_range<1> (INT (9), INT (20)));
2471
2472 // [10,20] ^ [15,30] => [15,20].
2473 r0 = int_range<1> (INT (10), INT (20));
2474 r1 = int_range<1> (INT (15), INT (30));
2475 r0.intersect (r1);
2476 ASSERT_TRUE (r0 == int_range<1> (INT (15), INT (20)));
2477
2478 // Test the internal sanity of wide_int's wrt HWIs.
2479 ASSERT_TRUE (wi::max_value (TYPE_PRECISION (boolean_type_node),
2480 TYPE_SIGN (boolean_type_node))
2481 == wi::uhwi (1, TYPE_PRECISION (boolean_type_node)));
2482
2483 // Test zero_p().
2484 r0 = int_range<1> (INT (0), INT (0));
2485 ASSERT_TRUE (r0.zero_p ());
2486
2487 // Test nonzero_p().
2488 r0 = int_range<1> (INT (0), INT (0));
2489 r0.invert ();
2490 ASSERT_TRUE (r0.nonzero_p ());
2491
2492 // test legacy interaction
2493 // r0 = ~[1,1]
2494 r0 = int_range<1> (UINT (1), UINT (1), VR_ANTI_RANGE);
2495 // r1 = ~[3,3]
2496 r1 = int_range<1> (UINT (3), UINT (3), VR_ANTI_RANGE);
2497
2498 // vv = [0,0][2,2][4, MAX]
2499 int_range<3> vv = r0;
2500 vv.intersect (r1);
2501
2502 ASSERT_TRUE (vv.contains_p (UINT (2)));
2503 ASSERT_TRUE (vv.num_pairs () == 3);
2504
2505 // create r0 as legacy [1,1]
2506 r0 = int_range<1> (UINT (1), UINT (1));
2507 // And union it with [0,0][2,2][4,MAX] multi range
2508 r0.union_ (vv);
2509 // The result should be [0,2][4,MAX], or ~[3,3] but it must contain 2
2510 ASSERT_TRUE (r0.contains_p (UINT (2)));
2511 }
2512
2513 void
range_tests()2514 range_tests ()
2515 {
2516 range_tests_legacy ();
2517 range_tests_irange3 ();
2518 range_tests_int_range_max ();
2519 range_tests_strict_enum ();
2520 range_tests_misc ();
2521 }
2522
2523 } // namespace selftest
2524
2525 #endif // CHECKING_P
2526