1 /* Support routines for value ranges.
2 Copyright (C) 2019-2020 Free Software Foundation, Inc.
3
4 This file is part of GCC.
5
6 GCC is free software; you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 3, or (at your option)
9 any later version.
10
11 GCC is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
15
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING3. If not see
18 <http://www.gnu.org/licenses/>. */
19
20 #include "config.h"
21 #include "system.h"
22 #include "coretypes.h"
23 #include "backend.h"
24 #include "tree.h"
25 #include "gimple.h"
26 #include "ssa.h"
27 #include "tree-pretty-print.h"
28 #include "fold-const.h"
29
value_range(tree min,tree max,value_range_kind kind)30 value_range::value_range (tree min, tree max, value_range_kind kind)
31 {
32 set (min, max, kind);
33 }
34
value_range(tree type)35 value_range::value_range (tree type)
36 {
37 set_varying (type);
38 }
39
value_range(tree type,const wide_int & wmin,const wide_int & wmax,enum value_range_kind kind)40 value_range::value_range (tree type,
41 const wide_int &wmin, const wide_int &wmax,
42 enum value_range_kind kind)
43 {
44 tree min = wide_int_to_tree (type, wmin);
45 tree max = wide_int_to_tree (type, wmax);
46 gcc_checking_assert (kind == VR_RANGE || kind == VR_ANTI_RANGE);
47 set (min, max, kind);
48 }
49
50 void
set_undefined()51 value_range::set_undefined ()
52 {
53 m_kind = VR_UNDEFINED;
54 m_min = m_max = NULL;
55 }
56
57 void
set_varying(tree type)58 value_range::set_varying (tree type)
59 {
60 m_kind = VR_VARYING;
61 if (supports_type_p (type))
62 {
63 m_min = vrp_val_min (type);
64 m_max = vrp_val_max (type);
65 }
66 else
67 /* We can't do anything range-wise with these types. */
68 m_min = m_max = error_mark_node;
69 }
70
71 /* Set value range to the canonical form of {VRTYPE, MIN, MAX, EQUIV}.
72 This means adjusting VRTYPE, MIN and MAX representing the case of a
73 wrapping range with MAX < MIN covering [MIN, type_max] U [type_min, MAX]
74 as anti-rage ~[MAX+1, MIN-1]. Likewise for wrapping anti-ranges.
75 In corner cases where MAX+1 or MIN-1 wraps this will fall back
76 to varying.
77 This routine exists to ease canonicalization in the case where we
78 extract ranges from var + CST op limit. */
79
80 void
set(tree min,tree max,value_range_kind kind)81 value_range::set (tree min, tree max, value_range_kind kind)
82 {
83 /* Use the canonical setters for VR_UNDEFINED and VR_VARYING. */
84 if (kind == VR_UNDEFINED)
85 {
86 set_undefined ();
87 return;
88 }
89
90 if (kind != VR_VARYING
91 && (POLY_INT_CST_P (min) || POLY_INT_CST_P (max)))
92 {
93 tree typ = TREE_TYPE (min);
94 gcc_checking_assert (useless_type_conversion_p (typ, TREE_TYPE (max)));
95 set_varying (typ);
96 return;
97 }
98
99 if (kind == VR_VARYING)
100 {
101 gcc_assert (TREE_TYPE (min) == TREE_TYPE (max));
102 tree typ = TREE_TYPE (min);
103 if (supports_type_p (typ))
104 {
105 gcc_assert (vrp_val_min (typ));
106 gcc_assert (vrp_val_max (typ));
107 }
108 set_varying (typ);
109 return;
110 }
111
112 /* Nothing to canonicalize for symbolic ranges. */
113 if (TREE_CODE (min) != INTEGER_CST
114 || TREE_CODE (max) != INTEGER_CST)
115 {
116 m_kind = kind;
117 m_min = min;
118 m_max = max;
119 return;
120 }
121
122 /* Wrong order for min and max, to swap them and the VR type we need
123 to adjust them. */
124 if (tree_int_cst_lt (max, min))
125 {
126 tree one, tmp;
127
128 /* For one bit precision if max < min, then the swapped
129 range covers all values, so for VR_RANGE it is varying and
130 for VR_ANTI_RANGE empty range, so drop to varying as well. */
131 if (TYPE_PRECISION (TREE_TYPE (min)) == 1)
132 {
133 set_varying (TREE_TYPE (min));
134 return;
135 }
136
137 one = build_int_cst (TREE_TYPE (min), 1);
138 tmp = int_const_binop (PLUS_EXPR, max, one);
139 max = int_const_binop (MINUS_EXPR, min, one);
140 min = tmp;
141
142 /* There's one corner case, if we had [C+1, C] before we now have
143 that again. But this represents an empty value range, so drop
144 to varying in this case. */
145 if (tree_int_cst_lt (max, min))
146 {
147 set_varying (TREE_TYPE (min));
148 return;
149 }
150
151 kind = kind == VR_RANGE ? VR_ANTI_RANGE : VR_RANGE;
152 }
153
154 tree type = TREE_TYPE (min);
155
156 /* Anti-ranges that can be represented as ranges should be so. */
157 if (kind == VR_ANTI_RANGE)
158 {
159 /* For -fstrict-enums we may receive out-of-range ranges so consider
160 values < -INF and values > INF as -INF/INF as well. */
161 bool is_min = vrp_val_is_min (min);
162 bool is_max = vrp_val_is_max (max);
163
164 if (is_min && is_max)
165 {
166 /* We cannot deal with empty ranges, drop to varying.
167 ??? This could be VR_UNDEFINED instead. */
168 set_varying (type);
169 return;
170 }
171 else if (TYPE_PRECISION (TREE_TYPE (min)) == 1
172 && (is_min || is_max))
173 {
174 /* Non-empty boolean ranges can always be represented
175 as a singleton range. */
176 if (is_min)
177 min = max = vrp_val_max (TREE_TYPE (min));
178 else
179 min = max = vrp_val_min (TREE_TYPE (min));
180 kind = VR_RANGE;
181 }
182 else if (is_min)
183 {
184 tree one = build_int_cst (TREE_TYPE (max), 1);
185 min = int_const_binop (PLUS_EXPR, max, one);
186 max = vrp_val_max (TREE_TYPE (max));
187 kind = VR_RANGE;
188 }
189 else if (is_max)
190 {
191 tree one = build_int_cst (TREE_TYPE (min), 1);
192 max = int_const_binop (MINUS_EXPR, min, one);
193 min = vrp_val_min (TREE_TYPE (min));
194 kind = VR_RANGE;
195 }
196 }
197
198 /* Normalize [MIN, MAX] into VARYING and ~[MIN, MAX] into UNDEFINED.
199
200 Avoid using TYPE_{MIN,MAX}_VALUE because -fstrict-enums can
201 restrict those to a subset of what actually fits in the type.
202 Instead use the extremes of the type precision which will allow
203 compare_range_with_value() to check if a value is inside a range,
204 whereas if we used TYPE_*_VAL, said function would just punt
205 upon seeing a VARYING. */
206 unsigned prec = TYPE_PRECISION (type);
207 signop sign = TYPE_SIGN (type);
208 if (wi::eq_p (wi::to_wide (min), wi::min_value (prec, sign))
209 && wi::eq_p (wi::to_wide (max), wi::max_value (prec, sign)))
210 {
211 if (kind == VR_RANGE)
212 set_varying (type);
213 else if (kind == VR_ANTI_RANGE)
214 set_undefined ();
215 else
216 gcc_unreachable ();
217 return;
218 }
219
220 /* Do not drop [-INF(OVF), +INF(OVF)] to varying. (OVF) has to be sticky
221 to make sure VRP iteration terminates, otherwise we can get into
222 oscillations. */
223
224 m_kind = kind;
225 m_min = min;
226 m_max = max;
227 if (flag_checking)
228 check ();
229 }
230
231 void
set(tree val)232 value_range::set (tree val)
233 {
234 gcc_assert (TREE_CODE (val) == SSA_NAME || is_gimple_min_invariant (val));
235 if (TREE_OVERFLOW_P (val))
236 val = drop_tree_overflow (val);
237 set (val, val);
238 }
239
240 /* Set value range VR to a nonzero range of type TYPE. */
241
242 void
set_nonzero(tree type)243 value_range::set_nonzero (tree type)
244 {
245 tree zero = build_int_cst (type, 0);
246 set (zero, zero, VR_ANTI_RANGE);
247 }
248
249 /* Set value range VR to a ZERO range of type TYPE. */
250
251 void
set_zero(tree type)252 value_range::set_zero (tree type)
253 {
254 set (build_int_cst (type, 0));
255 }
256
257 /* Check the validity of the range. */
258
259 void
check()260 value_range::check ()
261 {
262 switch (m_kind)
263 {
264 case VR_RANGE:
265 case VR_ANTI_RANGE:
266 {
267 gcc_assert (m_min && m_max);
268 gcc_assert (!TREE_OVERFLOW_P (m_min) && !TREE_OVERFLOW_P (m_max));
269
270 /* Creating ~[-MIN, +MAX] is stupid because that would be
271 the empty set. */
272 if (INTEGRAL_TYPE_P (TREE_TYPE (m_min)) && m_kind == VR_ANTI_RANGE)
273 gcc_assert (!vrp_val_is_min (m_min) || !vrp_val_is_max (m_max));
274
275 int cmp = compare_values (m_min, m_max);
276 gcc_assert (cmp == 0 || cmp == -1 || cmp == -2);
277 break;
278 }
279 case VR_UNDEFINED:
280 gcc_assert (!min () && !max ());
281 break;
282 case VR_VARYING:
283 gcc_assert (m_min && m_max);
284 break;
285 default:
286 gcc_unreachable ();
287 }
288 }
289
290 /* Return the number of sub-ranges in a range. */
291
292 unsigned
num_pairs() const293 value_range::num_pairs () const
294 {
295 if (undefined_p ())
296 return 0;
297 if (varying_p ())
298 return 1;
299 if (symbolic_p ())
300 {
301 value_range numeric_range (*this);
302 numeric_range.normalize_symbolics ();
303 return numeric_range.num_pairs ();
304 }
305 if (m_kind == VR_ANTI_RANGE)
306 {
307 // ~[MIN, X] has one sub-range of [X+1, MAX], and
308 // ~[X, MAX] has one sub-range of [MIN, X-1].
309 if (vrp_val_is_min (m_min) || vrp_val_is_max (m_max))
310 return 1;
311 return 2;
312 }
313 return 1;
314 }
315
316 /* Return the lower bound for a sub-range. PAIR is the sub-range in
317 question. */
318
319 wide_int
lower_bound(unsigned pair) const320 value_range::lower_bound (unsigned pair) const
321 {
322 if (symbolic_p ())
323 {
324 value_range numeric_range (*this);
325 numeric_range.normalize_symbolics ();
326 return numeric_range.lower_bound (pair);
327 }
328
329 gcc_checking_assert (!undefined_p ());
330 gcc_checking_assert (pair + 1 <= num_pairs ());
331 tree t = NULL;
332 if (m_kind == VR_ANTI_RANGE)
333 {
334 tree typ = type ();
335 if (pair == 1 || vrp_val_is_min (m_min))
336 t = wide_int_to_tree (typ, wi::to_wide (m_max) + 1);
337 else
338 t = vrp_val_min (typ);
339 }
340 else
341 t = m_min;
342 return wi::to_wide (t);
343 }
344
345 /* Return the upper bound for a sub-range. PAIR is the sub-range in
346 question. */
347
348 wide_int
upper_bound(unsigned pair) const349 value_range::upper_bound (unsigned pair) const
350 {
351 if (symbolic_p ())
352 {
353 value_range numeric_range (*this);
354 numeric_range.normalize_symbolics ();
355 return numeric_range.upper_bound (pair);
356 }
357
358 gcc_checking_assert (!undefined_p ());
359 gcc_checking_assert (pair + 1 <= num_pairs ());
360 tree t = NULL;
361 if (m_kind == VR_ANTI_RANGE)
362 {
363 tree typ = type ();
364 if (pair == 1 || vrp_val_is_min (m_min))
365 t = vrp_val_max (typ);
366 else
367 t = wide_int_to_tree (typ, wi::to_wide (m_min) - 1);
368 }
369 else
370 t = m_max;
371 return wi::to_wide (t);
372 }
373
374 /* Return the highest bound in a range. */
375
376 wide_int
upper_bound() const377 value_range::upper_bound () const
378 {
379 unsigned pairs = num_pairs ();
380 gcc_checking_assert (pairs > 0);
381 return upper_bound (pairs - 1);
382 }
383
384 bool
equal_p(const value_range & other) const385 value_range::equal_p (const value_range &other) const
386 {
387 /* Ignore types for undefined. All undefines are equal. */
388 if (undefined_p ())
389 return m_kind == other.m_kind;
390
391 return (m_kind == other.m_kind
392 && vrp_operand_equal_p (m_min, other.m_min)
393 && vrp_operand_equal_p (m_max, other.m_max));
394 }
395
396 bool
operator ==(const value_range & r) const397 value_range::operator== (const value_range &r) const
398 {
399 return equal_p (r);
400 }
401
402 /* If range is a singleton, place it in RESULT and return TRUE.
403 Note: A singleton can be any gimple invariant, not just constants.
404 So, [&x, &x] counts as a singleton. */
405 /* Return TRUE if this is a symbolic range. */
406
407 bool
symbolic_p() const408 value_range::symbolic_p () const
409 {
410 return (!varying_p ()
411 && !undefined_p ()
412 && (!is_gimple_min_invariant (m_min)
413 || !is_gimple_min_invariant (m_max)));
414 }
415
416 /* NOTE: This is not the inverse of symbolic_p because the range
417 could also be varying or undefined. Ideally they should be inverse
418 of each other, with varying only applying to symbolics. Varying of
419 constants would be represented as [-MIN, +MAX]. */
420
421 bool
constant_p() const422 value_range::constant_p () const
423 {
424 return (!varying_p ()
425 && !undefined_p ()
426 && TREE_CODE (m_min) == INTEGER_CST
427 && TREE_CODE (m_max) == INTEGER_CST);
428 }
429
430 bool
singleton_p(tree * result) const431 value_range::singleton_p (tree *result) const
432 {
433 if (m_kind == VR_ANTI_RANGE)
434 {
435 if (nonzero_p ())
436 {
437 if (TYPE_PRECISION (type ()) == 1)
438 {
439 if (result)
440 *result = m_max;
441 return true;
442 }
443 return false;
444 }
445 if (num_pairs () == 1)
446 {
447 value_range vr0, vr1;
448 ranges_from_anti_range (this, &vr0, &vr1);
449 return vr0.singleton_p (result);
450 }
451 }
452 if (m_kind == VR_RANGE
453 && vrp_operand_equal_p (min (), max ())
454 && is_gimple_min_invariant (min ()))
455 {
456 if (result)
457 *result = min ();
458 return true;
459 }
460 return false;
461 }
462
463 /* Return 1 if VAL is inside value range.
464 0 if VAL is not inside value range.
465 -2 if we cannot tell either way.
466
467 Benchmark compile/20001226-1.c compilation time after changing this
468 function. */
469
470 int
value_inside_range(tree val) const471 value_range::value_inside_range (tree val) const
472 {
473 int cmp1, cmp2;
474
475 if (varying_p ())
476 return 1;
477
478 if (undefined_p ())
479 return 0;
480
481 cmp1 = operand_less_p (val, m_min);
482 if (cmp1 == -2)
483 return -2;
484 if (cmp1 == 1)
485 return m_kind != VR_RANGE;
486
487 cmp2 = operand_less_p (m_max, val);
488 if (cmp2 == -2)
489 return -2;
490
491 if (m_kind == VR_RANGE)
492 return !cmp2;
493 else
494 return !!cmp2;
495 }
496
497 /* Return TRUE if it is possible that range contains VAL. */
498
499 bool
may_contain_p(tree val) const500 value_range::may_contain_p (tree val) const
501 {
502 return value_inside_range (val) != 0;
503 }
504
505 /* Return TRUE if range contains INTEGER_CST. */
506
507 bool
contains_p(tree cst) const508 value_range::contains_p (tree cst) const
509 {
510 gcc_checking_assert (TREE_CODE (cst) == INTEGER_CST);
511 if (symbolic_p ())
512 {
513 value_range numeric_range (*this);
514 numeric_range.normalize_symbolics ();
515 return numeric_range.contains_p (cst);
516 }
517 return value_inside_range (cst) == 1;
518 }
519
520 /* Normalize addresses into constants. */
521
522 void
normalize_addresses()523 value_range::normalize_addresses ()
524 {
525 if (undefined_p ())
526 return;
527
528 if (!POINTER_TYPE_P (type ()) || range_has_numeric_bounds_p (this))
529 return;
530
531 if (!range_includes_zero_p (this))
532 {
533 gcc_checking_assert (TREE_CODE (m_min) == ADDR_EXPR
534 || TREE_CODE (m_max) == ADDR_EXPR);
535 set_nonzero (type ());
536 return;
537 }
538 set_varying (type ());
539 }
540
541 /* Normalize symbolics and addresses into constants. */
542
543 void
normalize_symbolics()544 value_range::normalize_symbolics ()
545 {
546 if (varying_p () || undefined_p ())
547 return;
548
549 tree ttype = type ();
550 bool min_symbolic = !is_gimple_min_invariant (min ());
551 bool max_symbolic = !is_gimple_min_invariant (max ());
552 if (!min_symbolic && !max_symbolic)
553 {
554 normalize_addresses ();
555 return;
556 }
557
558 // [SYM, SYM] -> VARYING
559 if (min_symbolic && max_symbolic)
560 {
561 set_varying (ttype);
562 return;
563 }
564 if (kind () == VR_RANGE)
565 {
566 // [SYM, NUM] -> [-MIN, NUM]
567 if (min_symbolic)
568 {
569 set (vrp_val_min (ttype), max ());
570 return;
571 }
572 // [NUM, SYM] -> [NUM, +MAX]
573 set (min (), vrp_val_max (ttype));
574 return;
575 }
576 gcc_checking_assert (kind () == VR_ANTI_RANGE);
577 // ~[SYM, NUM] -> [NUM + 1, +MAX]
578 if (min_symbolic)
579 {
580 if (!vrp_val_is_max (max ()))
581 {
582 tree n = wide_int_to_tree (ttype, wi::to_wide (max ()) + 1);
583 set (n, vrp_val_max (ttype));
584 return;
585 }
586 set_varying (ttype);
587 return;
588 }
589 // ~[NUM, SYM] -> [-MIN, NUM - 1]
590 if (!vrp_val_is_min (min ()))
591 {
592 tree n = wide_int_to_tree (ttype, wi::to_wide (min ()) - 1);
593 set (vrp_val_min (ttype), n);
594 return;
595 }
596 set_varying (ttype);
597 }
598
599 /* Intersect the two value-ranges { *VR0TYPE, *VR0MIN, *VR0MAX } and
600 { VR1TYPE, VR0MIN, VR0MAX } and store the result
601 in { *VR0TYPE, *VR0MIN, *VR0MAX }. This may not be the smallest
602 possible such range. The resulting range is not canonicalized. */
603
604 static void
intersect_ranges(enum value_range_kind * vr0type,tree * vr0min,tree * vr0max,enum value_range_kind vr1type,tree vr1min,tree vr1max)605 intersect_ranges (enum value_range_kind *vr0type,
606 tree *vr0min, tree *vr0max,
607 enum value_range_kind vr1type,
608 tree vr1min, tree vr1max)
609 {
610 bool mineq = vrp_operand_equal_p (*vr0min, vr1min);
611 bool maxeq = vrp_operand_equal_p (*vr0max, vr1max);
612
613 /* [] is vr0, () is vr1 in the following classification comments. */
614 if (mineq && maxeq)
615 {
616 /* [( )] */
617 if (*vr0type == vr1type)
618 /* Nothing to do for equal ranges. */
619 ;
620 else if ((*vr0type == VR_RANGE
621 && vr1type == VR_ANTI_RANGE)
622 || (*vr0type == VR_ANTI_RANGE
623 && vr1type == VR_RANGE))
624 {
625 /* For anti-range with range intersection the result is empty. */
626 *vr0type = VR_UNDEFINED;
627 *vr0min = NULL_TREE;
628 *vr0max = NULL_TREE;
629 }
630 else
631 gcc_unreachable ();
632 }
633 else if (operand_less_p (*vr0max, vr1min) == 1
634 || operand_less_p (vr1max, *vr0min) == 1)
635 {
636 /* [ ] ( ) or ( ) [ ]
637 If the ranges have an empty intersection, the result of the
638 intersect operation is the range for intersecting an
639 anti-range with a range or empty when intersecting two ranges. */
640 if (*vr0type == VR_RANGE
641 && vr1type == VR_ANTI_RANGE)
642 ;
643 else if (*vr0type == VR_ANTI_RANGE
644 && vr1type == VR_RANGE)
645 {
646 *vr0type = vr1type;
647 *vr0min = vr1min;
648 *vr0max = vr1max;
649 }
650 else if (*vr0type == VR_RANGE
651 && vr1type == VR_RANGE)
652 {
653 *vr0type = VR_UNDEFINED;
654 *vr0min = NULL_TREE;
655 *vr0max = NULL_TREE;
656 }
657 else if (*vr0type == VR_ANTI_RANGE
658 && vr1type == VR_ANTI_RANGE)
659 {
660 /* If the anti-ranges are adjacent to each other merge them. */
661 if (TREE_CODE (*vr0max) == INTEGER_CST
662 && TREE_CODE (vr1min) == INTEGER_CST
663 && operand_less_p (*vr0max, vr1min) == 1
664 && integer_onep (int_const_binop (MINUS_EXPR,
665 vr1min, *vr0max)))
666 *vr0max = vr1max;
667 else if (TREE_CODE (vr1max) == INTEGER_CST
668 && TREE_CODE (*vr0min) == INTEGER_CST
669 && operand_less_p (vr1max, *vr0min) == 1
670 && integer_onep (int_const_binop (MINUS_EXPR,
671 *vr0min, vr1max)))
672 *vr0min = vr1min;
673 /* Else arbitrarily take VR0. */
674 }
675 }
676 else if ((maxeq || operand_less_p (vr1max, *vr0max) == 1)
677 && (mineq || operand_less_p (*vr0min, vr1min) == 1))
678 {
679 /* [ ( ) ] or [( ) ] or [ ( )] */
680 if (*vr0type == VR_RANGE
681 && vr1type == VR_RANGE)
682 {
683 /* If both are ranges the result is the inner one. */
684 *vr0type = vr1type;
685 *vr0min = vr1min;
686 *vr0max = vr1max;
687 }
688 else if (*vr0type == VR_RANGE
689 && vr1type == VR_ANTI_RANGE)
690 {
691 /* Choose the right gap if the left one is empty. */
692 if (mineq)
693 {
694 if (TREE_CODE (vr1max) != INTEGER_CST)
695 *vr0min = vr1max;
696 else if (TYPE_PRECISION (TREE_TYPE (vr1max)) == 1
697 && !TYPE_UNSIGNED (TREE_TYPE (vr1max)))
698 *vr0min
699 = int_const_binop (MINUS_EXPR, vr1max,
700 build_int_cst (TREE_TYPE (vr1max), -1));
701 else
702 *vr0min
703 = int_const_binop (PLUS_EXPR, vr1max,
704 build_int_cst (TREE_TYPE (vr1max), 1));
705 }
706 /* Choose the left gap if the right one is empty. */
707 else if (maxeq)
708 {
709 if (TREE_CODE (vr1min) != INTEGER_CST)
710 *vr0max = vr1min;
711 else if (TYPE_PRECISION (TREE_TYPE (vr1min)) == 1
712 && !TYPE_UNSIGNED (TREE_TYPE (vr1min)))
713 *vr0max
714 = int_const_binop (PLUS_EXPR, vr1min,
715 build_int_cst (TREE_TYPE (vr1min), -1));
716 else
717 *vr0max
718 = int_const_binop (MINUS_EXPR, vr1min,
719 build_int_cst (TREE_TYPE (vr1min), 1));
720 }
721 /* Choose the anti-range if the range is effectively varying. */
722 else if (vrp_val_is_min (*vr0min)
723 && vrp_val_is_max (*vr0max))
724 {
725 *vr0type = vr1type;
726 *vr0min = vr1min;
727 *vr0max = vr1max;
728 }
729 /* Else choose the range. */
730 }
731 else if (*vr0type == VR_ANTI_RANGE
732 && vr1type == VR_ANTI_RANGE)
733 /* If both are anti-ranges the result is the outer one. */
734 ;
735 else if (*vr0type == VR_ANTI_RANGE
736 && vr1type == VR_RANGE)
737 {
738 /* The intersection is empty. */
739 *vr0type = VR_UNDEFINED;
740 *vr0min = NULL_TREE;
741 *vr0max = NULL_TREE;
742 }
743 else
744 gcc_unreachable ();
745 }
746 else if ((maxeq || operand_less_p (*vr0max, vr1max) == 1)
747 && (mineq || operand_less_p (vr1min, *vr0min) == 1))
748 {
749 /* ( [ ] ) or ([ ] ) or ( [ ]) */
750 if (*vr0type == VR_RANGE
751 && vr1type == VR_RANGE)
752 /* Choose the inner range. */
753 ;
754 else if (*vr0type == VR_ANTI_RANGE
755 && vr1type == VR_RANGE)
756 {
757 /* Choose the right gap if the left is empty. */
758 if (mineq)
759 {
760 *vr0type = VR_RANGE;
761 if (TREE_CODE (*vr0max) != INTEGER_CST)
762 *vr0min = *vr0max;
763 else if (TYPE_PRECISION (TREE_TYPE (*vr0max)) == 1
764 && !TYPE_UNSIGNED (TREE_TYPE (*vr0max)))
765 *vr0min
766 = int_const_binop (MINUS_EXPR, *vr0max,
767 build_int_cst (TREE_TYPE (*vr0max), -1));
768 else
769 *vr0min
770 = int_const_binop (PLUS_EXPR, *vr0max,
771 build_int_cst (TREE_TYPE (*vr0max), 1));
772 *vr0max = vr1max;
773 }
774 /* Choose the left gap if the right is empty. */
775 else if (maxeq)
776 {
777 *vr0type = VR_RANGE;
778 if (TREE_CODE (*vr0min) != INTEGER_CST)
779 *vr0max = *vr0min;
780 else if (TYPE_PRECISION (TREE_TYPE (*vr0min)) == 1
781 && !TYPE_UNSIGNED (TREE_TYPE (*vr0min)))
782 *vr0max
783 = int_const_binop (PLUS_EXPR, *vr0min,
784 build_int_cst (TREE_TYPE (*vr0min), -1));
785 else
786 *vr0max
787 = int_const_binop (MINUS_EXPR, *vr0min,
788 build_int_cst (TREE_TYPE (*vr0min), 1));
789 *vr0min = vr1min;
790 }
791 /* Choose the anti-range if the range is effectively varying. */
792 else if (vrp_val_is_min (vr1min)
793 && vrp_val_is_max (vr1max))
794 ;
795 /* Choose the anti-range if it is ~[0,0], that range is special
796 enough to special case when vr1's range is relatively wide.
797 At least for types bigger than int - this covers pointers
798 and arguments to functions like ctz. */
799 else if (*vr0min == *vr0max
800 && integer_zerop (*vr0min)
801 && ((TYPE_PRECISION (TREE_TYPE (*vr0min))
802 >= TYPE_PRECISION (integer_type_node))
803 || POINTER_TYPE_P (TREE_TYPE (*vr0min)))
804 && TREE_CODE (vr1max) == INTEGER_CST
805 && TREE_CODE (vr1min) == INTEGER_CST
806 && (wi::clz (wi::to_wide (vr1max) - wi::to_wide (vr1min))
807 < TYPE_PRECISION (TREE_TYPE (*vr0min)) / 2))
808 ;
809 /* Else choose the range. */
810 else
811 {
812 *vr0type = vr1type;
813 *vr0min = vr1min;
814 *vr0max = vr1max;
815 }
816 }
817 else if (*vr0type == VR_ANTI_RANGE
818 && vr1type == VR_ANTI_RANGE)
819 {
820 /* If both are anti-ranges the result is the outer one. */
821 *vr0type = vr1type;
822 *vr0min = vr1min;
823 *vr0max = vr1max;
824 }
825 else if (vr1type == VR_ANTI_RANGE
826 && *vr0type == VR_RANGE)
827 {
828 /* The intersection is empty. */
829 *vr0type = VR_UNDEFINED;
830 *vr0min = NULL_TREE;
831 *vr0max = NULL_TREE;
832 }
833 else
834 gcc_unreachable ();
835 }
836 else if ((operand_less_p (vr1min, *vr0max) == 1
837 || operand_equal_p (vr1min, *vr0max, 0))
838 && operand_less_p (*vr0min, vr1min) == 1
839 && operand_less_p (*vr0max, vr1max) == 1)
840 {
841 /* [ ( ] ) or [ ]( ) */
842 if (*vr0type == VR_ANTI_RANGE
843 && vr1type == VR_ANTI_RANGE)
844 *vr0max = vr1max;
845 else if (*vr0type == VR_RANGE
846 && vr1type == VR_RANGE)
847 *vr0min = vr1min;
848 else if (*vr0type == VR_RANGE
849 && vr1type == VR_ANTI_RANGE)
850 {
851 if (TREE_CODE (vr1min) == INTEGER_CST)
852 *vr0max = int_const_binop (MINUS_EXPR, vr1min,
853 build_int_cst (TREE_TYPE (vr1min), 1));
854 else
855 *vr0max = vr1min;
856 }
857 else if (*vr0type == VR_ANTI_RANGE
858 && vr1type == VR_RANGE)
859 {
860 *vr0type = VR_RANGE;
861 if (TREE_CODE (*vr0max) == INTEGER_CST)
862 *vr0min = int_const_binop (PLUS_EXPR, *vr0max,
863 build_int_cst (TREE_TYPE (*vr0max), 1));
864 else
865 *vr0min = *vr0max;
866 *vr0max = vr1max;
867 }
868 else
869 gcc_unreachable ();
870 }
871 else if ((operand_less_p (*vr0min, vr1max) == 1
872 || operand_equal_p (*vr0min, vr1max, 0))
873 && operand_less_p (vr1min, *vr0min) == 1
874 && operand_less_p (vr1max, *vr0max) == 1)
875 {
876 /* ( [ ) ] or ( )[ ] */
877 if (*vr0type == VR_ANTI_RANGE
878 && vr1type == VR_ANTI_RANGE)
879 *vr0min = vr1min;
880 else if (*vr0type == VR_RANGE
881 && vr1type == VR_RANGE)
882 *vr0max = vr1max;
883 else if (*vr0type == VR_RANGE
884 && vr1type == VR_ANTI_RANGE)
885 {
886 if (TREE_CODE (vr1max) == INTEGER_CST)
887 *vr0min = int_const_binop (PLUS_EXPR, vr1max,
888 build_int_cst (TREE_TYPE (vr1max), 1));
889 else
890 *vr0min = vr1max;
891 }
892 else if (*vr0type == VR_ANTI_RANGE
893 && vr1type == VR_RANGE)
894 {
895 *vr0type = VR_RANGE;
896 if (TREE_CODE (*vr0min) == INTEGER_CST)
897 *vr0max = int_const_binop (MINUS_EXPR, *vr0min,
898 build_int_cst (TREE_TYPE (*vr0min), 1));
899 else
900 *vr0max = *vr0min;
901 *vr0min = vr1min;
902 }
903 else
904 gcc_unreachable ();
905 }
906
907 /* If we know the intersection is empty, there's no need to
908 conservatively add anything else to the set. */
909 if (*vr0type == VR_UNDEFINED)
910 return;
911
912 /* As a fallback simply use { *VRTYPE, *VR0MIN, *VR0MAX } as
913 result for the intersection. That's always a conservative
914 correct estimate unless VR1 is a constant singleton range
915 in which case we choose that. */
916 if (vr1type == VR_RANGE
917 && is_gimple_min_invariant (vr1min)
918 && vrp_operand_equal_p (vr1min, vr1max))
919 {
920 *vr0type = vr1type;
921 *vr0min = vr1min;
922 *vr0max = vr1max;
923 }
924 }
925
926 /* Helper for the intersection operation for value ranges. Given two
927 value ranges VR0 and VR1, return the intersection of the two
928 ranges. This may not be the smallest possible such range. */
929
930 value_range
intersect_helper(const value_range * vr0,const value_range * vr1)931 value_range::intersect_helper (const value_range *vr0, const value_range *vr1)
932 {
933 /* If either range is VR_VARYING the other one wins. */
934 if (vr1->varying_p ())
935 return *vr0;
936 if (vr0->varying_p ())
937 return *vr1;
938
939 /* When either range is VR_UNDEFINED the resulting range is
940 VR_UNDEFINED, too. */
941 if (vr0->undefined_p ())
942 return *vr0;
943 if (vr1->undefined_p ())
944 return *vr1;
945
946 value_range_kind vr0kind = vr0->kind ();
947 tree vr0min = vr0->min ();
948 tree vr0max = vr0->max ();
949 intersect_ranges (&vr0kind, &vr0min, &vr0max,
950 vr1->kind (), vr1->min (), vr1->max ());
951 /* Make sure to canonicalize the result though as the inversion of a
952 VR_RANGE can still be a VR_RANGE. Work on a temporary so we can
953 fall back to vr0 when this turns things to varying. */
954 value_range tem;
955 if (vr0kind == VR_UNDEFINED)
956 tem.set_undefined ();
957 else if (vr0kind == VR_VARYING)
958 tem.set_varying (vr0->type ());
959 else
960 tem.set (vr0min, vr0max, vr0kind);
961 /* If that failed, use the saved original VR0. */
962 if (tem.varying_p ())
963 return *vr0;
964
965 return tem;
966 }
967
968 /* Union the two value-ranges { *VR0TYPE, *VR0MIN, *VR0MAX } and
969 { VR1TYPE, VR0MIN, VR0MAX } and store the result
970 in { *VR0TYPE, *VR0MIN, *VR0MAX }. This may not be the smallest
971 possible such range. The resulting range is not canonicalized. */
972
973 static void
union_ranges(enum value_range_kind * vr0type,tree * vr0min,tree * vr0max,enum value_range_kind vr1type,tree vr1min,tree vr1max)974 union_ranges (enum value_range_kind *vr0type,
975 tree *vr0min, tree *vr0max,
976 enum value_range_kind vr1type,
977 tree vr1min, tree vr1max)
978 {
979 int cmpmin = compare_values (*vr0min, vr1min);
980 int cmpmax = compare_values (*vr0max, vr1max);
981 bool mineq = cmpmin == 0;
982 bool maxeq = cmpmax == 0;
983
984 /* [] is vr0, () is vr1 in the following classification comments. */
985 if (mineq && maxeq)
986 {
987 /* [( )] */
988 if (*vr0type == vr1type)
989 /* Nothing to do for equal ranges. */
990 ;
991 else if ((*vr0type == VR_RANGE
992 && vr1type == VR_ANTI_RANGE)
993 || (*vr0type == VR_ANTI_RANGE
994 && vr1type == VR_RANGE))
995 {
996 /* For anti-range with range union the result is varying. */
997 goto give_up;
998 }
999 else
1000 gcc_unreachable ();
1001 }
1002 else if (operand_less_p (*vr0max, vr1min) == 1
1003 || operand_less_p (vr1max, *vr0min) == 1)
1004 {
1005 /* [ ] ( ) or ( ) [ ]
1006 If the ranges have an empty intersection, result of the union
1007 operation is the anti-range or if both are anti-ranges
1008 it covers all. */
1009 if (*vr0type == VR_ANTI_RANGE
1010 && vr1type == VR_ANTI_RANGE)
1011 goto give_up;
1012 else if (*vr0type == VR_ANTI_RANGE
1013 && vr1type == VR_RANGE)
1014 ;
1015 else if (*vr0type == VR_RANGE
1016 && vr1type == VR_ANTI_RANGE)
1017 {
1018 *vr0type = vr1type;
1019 *vr0min = vr1min;
1020 *vr0max = vr1max;
1021 }
1022 else if (*vr0type == VR_RANGE
1023 && vr1type == VR_RANGE)
1024 {
1025 /* The result is the convex hull of both ranges. */
1026 if (operand_less_p (*vr0max, vr1min) == 1)
1027 {
1028 /* If the result can be an anti-range, create one. */
1029 if (TREE_CODE (*vr0max) == INTEGER_CST
1030 && TREE_CODE (vr1min) == INTEGER_CST
1031 && vrp_val_is_min (*vr0min)
1032 && vrp_val_is_max (vr1max))
1033 {
1034 tree min = int_const_binop (PLUS_EXPR,
1035 *vr0max,
1036 build_int_cst (TREE_TYPE (*vr0max), 1));
1037 tree max = int_const_binop (MINUS_EXPR,
1038 vr1min,
1039 build_int_cst (TREE_TYPE (vr1min), 1));
1040 if (!operand_less_p (max, min))
1041 {
1042 *vr0type = VR_ANTI_RANGE;
1043 *vr0min = min;
1044 *vr0max = max;
1045 }
1046 else
1047 *vr0max = vr1max;
1048 }
1049 else
1050 *vr0max = vr1max;
1051 }
1052 else
1053 {
1054 /* If the result can be an anti-range, create one. */
1055 if (TREE_CODE (vr1max) == INTEGER_CST
1056 && TREE_CODE (*vr0min) == INTEGER_CST
1057 && vrp_val_is_min (vr1min)
1058 && vrp_val_is_max (*vr0max))
1059 {
1060 tree min = int_const_binop (PLUS_EXPR,
1061 vr1max,
1062 build_int_cst (TREE_TYPE (vr1max), 1));
1063 tree max = int_const_binop (MINUS_EXPR,
1064 *vr0min,
1065 build_int_cst (TREE_TYPE (*vr0min), 1));
1066 if (!operand_less_p (max, min))
1067 {
1068 *vr0type = VR_ANTI_RANGE;
1069 *vr0min = min;
1070 *vr0max = max;
1071 }
1072 else
1073 *vr0min = vr1min;
1074 }
1075 else
1076 *vr0min = vr1min;
1077 }
1078 }
1079 else
1080 gcc_unreachable ();
1081 }
1082 else if ((maxeq || cmpmax == 1)
1083 && (mineq || cmpmin == -1))
1084 {
1085 /* [ ( ) ] or [( ) ] or [ ( )] */
1086 if (*vr0type == VR_RANGE
1087 && vr1type == VR_RANGE)
1088 ;
1089 else if (*vr0type == VR_ANTI_RANGE
1090 && vr1type == VR_ANTI_RANGE)
1091 {
1092 *vr0type = vr1type;
1093 *vr0min = vr1min;
1094 *vr0max = vr1max;
1095 }
1096 else if (*vr0type == VR_ANTI_RANGE
1097 && vr1type == VR_RANGE)
1098 {
1099 /* Arbitrarily choose the right or left gap. */
1100 if (!mineq && TREE_CODE (vr1min) == INTEGER_CST)
1101 *vr0max = int_const_binop (MINUS_EXPR, vr1min,
1102 build_int_cst (TREE_TYPE (vr1min), 1));
1103 else if (!maxeq && TREE_CODE (vr1max) == INTEGER_CST)
1104 *vr0min = int_const_binop (PLUS_EXPR, vr1max,
1105 build_int_cst (TREE_TYPE (vr1max), 1));
1106 else
1107 goto give_up;
1108 }
1109 else if (*vr0type == VR_RANGE
1110 && vr1type == VR_ANTI_RANGE)
1111 /* The result covers everything. */
1112 goto give_up;
1113 else
1114 gcc_unreachable ();
1115 }
1116 else if ((maxeq || cmpmax == -1)
1117 && (mineq || cmpmin == 1))
1118 {
1119 /* ( [ ] ) or ([ ] ) or ( [ ]) */
1120 if (*vr0type == VR_RANGE
1121 && vr1type == VR_RANGE)
1122 {
1123 *vr0type = vr1type;
1124 *vr0min = vr1min;
1125 *vr0max = vr1max;
1126 }
1127 else if (*vr0type == VR_ANTI_RANGE
1128 && vr1type == VR_ANTI_RANGE)
1129 ;
1130 else if (*vr0type == VR_RANGE
1131 && vr1type == VR_ANTI_RANGE)
1132 {
1133 *vr0type = VR_ANTI_RANGE;
1134 if (!mineq && TREE_CODE (*vr0min) == INTEGER_CST)
1135 {
1136 *vr0max = int_const_binop (MINUS_EXPR, *vr0min,
1137 build_int_cst (TREE_TYPE (*vr0min), 1));
1138 *vr0min = vr1min;
1139 }
1140 else if (!maxeq && TREE_CODE (*vr0max) == INTEGER_CST)
1141 {
1142 *vr0min = int_const_binop (PLUS_EXPR, *vr0max,
1143 build_int_cst (TREE_TYPE (*vr0max), 1));
1144 *vr0max = vr1max;
1145 }
1146 else
1147 goto give_up;
1148 }
1149 else if (*vr0type == VR_ANTI_RANGE
1150 && vr1type == VR_RANGE)
1151 /* The result covers everything. */
1152 goto give_up;
1153 else
1154 gcc_unreachable ();
1155 }
1156 else if (cmpmin == -1
1157 && cmpmax == -1
1158 && (operand_less_p (vr1min, *vr0max) == 1
1159 || operand_equal_p (vr1min, *vr0max, 0)))
1160 {
1161 /* [ ( ] ) or [ ]( ) */
1162 if (*vr0type == VR_RANGE
1163 && vr1type == VR_RANGE)
1164 *vr0max = vr1max;
1165 else if (*vr0type == VR_ANTI_RANGE
1166 && vr1type == VR_ANTI_RANGE)
1167 *vr0min = vr1min;
1168 else if (*vr0type == VR_ANTI_RANGE
1169 && vr1type == VR_RANGE)
1170 {
1171 if (TREE_CODE (vr1min) == INTEGER_CST)
1172 *vr0max = int_const_binop (MINUS_EXPR, vr1min,
1173 build_int_cst (TREE_TYPE (vr1min), 1));
1174 else
1175 goto give_up;
1176 }
1177 else if (*vr0type == VR_RANGE
1178 && vr1type == VR_ANTI_RANGE)
1179 {
1180 if (TREE_CODE (*vr0max) == INTEGER_CST)
1181 {
1182 *vr0type = vr1type;
1183 *vr0min = int_const_binop (PLUS_EXPR, *vr0max,
1184 build_int_cst (TREE_TYPE (*vr0max), 1));
1185 *vr0max = vr1max;
1186 }
1187 else
1188 goto give_up;
1189 }
1190 else
1191 gcc_unreachable ();
1192 }
1193 else if (cmpmin == 1
1194 && cmpmax == 1
1195 && (operand_less_p (*vr0min, vr1max) == 1
1196 || operand_equal_p (*vr0min, vr1max, 0)))
1197 {
1198 /* ( [ ) ] or ( )[ ] */
1199 if (*vr0type == VR_RANGE
1200 && vr1type == VR_RANGE)
1201 *vr0min = vr1min;
1202 else if (*vr0type == VR_ANTI_RANGE
1203 && vr1type == VR_ANTI_RANGE)
1204 *vr0max = vr1max;
1205 else if (*vr0type == VR_ANTI_RANGE
1206 && vr1type == VR_RANGE)
1207 {
1208 if (TREE_CODE (vr1max) == INTEGER_CST)
1209 *vr0min = int_const_binop (PLUS_EXPR, vr1max,
1210 build_int_cst (TREE_TYPE (vr1max), 1));
1211 else
1212 goto give_up;
1213 }
1214 else if (*vr0type == VR_RANGE
1215 && vr1type == VR_ANTI_RANGE)
1216 {
1217 if (TREE_CODE (*vr0min) == INTEGER_CST)
1218 {
1219 *vr0type = vr1type;
1220 *vr0max = int_const_binop (MINUS_EXPR, *vr0min,
1221 build_int_cst (TREE_TYPE (*vr0min), 1));
1222 *vr0min = vr1min;
1223 }
1224 else
1225 goto give_up;
1226 }
1227 else
1228 gcc_unreachable ();
1229 }
1230 else
1231 goto give_up;
1232
1233 return;
1234
1235 give_up:
1236 *vr0type = VR_VARYING;
1237 *vr0min = NULL_TREE;
1238 *vr0max = NULL_TREE;
1239 }
1240
1241 /* Helper for meet operation for value ranges. Given two value ranges VR0 and
1242 VR1, return a range that contains both VR0 and VR1. This may not be the
1243 smallest possible such range. */
1244
1245 value_range
union_helper(const value_range * vr0,const value_range * vr1)1246 value_range::union_helper (const value_range *vr0, const value_range *vr1)
1247 {
1248 /* VR0 has the resulting range if VR1 is undefined or VR0 is varying. */
1249 if (vr1->undefined_p ()
1250 || vr0->varying_p ())
1251 return *vr0;
1252
1253 /* VR1 has the resulting range if VR0 is undefined or VR1 is varying. */
1254 if (vr0->undefined_p ()
1255 || vr1->varying_p ())
1256 return *vr1;
1257
1258 value_range_kind vr0kind = vr0->kind ();
1259 tree vr0min = vr0->min ();
1260 tree vr0max = vr0->max ();
1261 union_ranges (&vr0kind, &vr0min, &vr0max,
1262 vr1->kind (), vr1->min (), vr1->max ());
1263
1264 /* Work on a temporary so we can still use vr0 when union returns varying. */
1265 value_range tem;
1266 if (vr0kind == VR_UNDEFINED)
1267 tem.set_undefined ();
1268 else if (vr0kind == VR_VARYING)
1269 tem.set_varying (vr0->type ());
1270 else
1271 tem.set (vr0min, vr0max, vr0kind);
1272
1273 /* Failed to find an efficient meet. Before giving up and setting
1274 the result to VARYING, see if we can at least derive a useful
1275 anti-range. */
1276 if (tem.varying_p ()
1277 && range_includes_zero_p (vr0) == 0
1278 && range_includes_zero_p (vr1) == 0)
1279 {
1280 tem.set_nonzero (vr0->type ());
1281 return tem;
1282 }
1283
1284 return tem;
1285 }
1286
1287 /* Meet operation for value ranges. Given two value ranges VR0 and
1288 VR1, store in VR0 a range that contains both VR0 and VR1. This
1289 may not be the smallest possible such range. */
1290
1291 void
union_(const value_range * other)1292 value_range::union_ (const value_range *other)
1293 {
1294 if (dump_file && (dump_flags & TDF_DETAILS))
1295 {
1296 fprintf (dump_file, "Meeting\n ");
1297 dump_value_range (dump_file, this);
1298 fprintf (dump_file, "\nand\n ");
1299 dump_value_range (dump_file, other);
1300 fprintf (dump_file, "\n");
1301 }
1302
1303 *this = union_helper (this, other);
1304
1305 if (dump_file && (dump_flags & TDF_DETAILS))
1306 {
1307 fprintf (dump_file, "to\n ");
1308 dump_value_range (dump_file, this);
1309 fprintf (dump_file, "\n");
1310 }
1311 }
1312
1313 /* Range union, but for references. */
1314
1315 void
union_(const value_range & r)1316 value_range::union_ (const value_range &r)
1317 {
1318 /* Disable details for now, because it makes the ranger dump
1319 unnecessarily verbose. */
1320 bool details = dump_flags & TDF_DETAILS;
1321 if (details)
1322 dump_flags &= ~TDF_DETAILS;
1323 union_ (&r);
1324 if (details)
1325 dump_flags |= TDF_DETAILS;
1326 }
1327
1328 void
intersect(const value_range * other)1329 value_range::intersect (const value_range *other)
1330 {
1331 if (dump_file && (dump_flags & TDF_DETAILS))
1332 {
1333 fprintf (dump_file, "Intersecting\n ");
1334 dump_value_range (dump_file, this);
1335 fprintf (dump_file, "\nand\n ");
1336 dump_value_range (dump_file, other);
1337 fprintf (dump_file, "\n");
1338 }
1339
1340 *this = intersect_helper (this, other);
1341
1342 if (dump_file && (dump_flags & TDF_DETAILS))
1343 {
1344 fprintf (dump_file, "to\n ");
1345 dump_value_range (dump_file, this);
1346 fprintf (dump_file, "\n");
1347 }
1348 }
1349
1350 /* Range intersect, but for references. */
1351
1352 void
intersect(const value_range & r)1353 value_range::intersect (const value_range &r)
1354 {
1355 /* Disable details for now, because it makes the ranger dump
1356 unnecessarily verbose. */
1357 bool details = dump_flags & TDF_DETAILS;
1358 if (details)
1359 dump_flags &= ~TDF_DETAILS;
1360 intersect (&r);
1361 if (details)
1362 dump_flags |= TDF_DETAILS;
1363 }
1364
1365 /* Return the inverse of a range. */
1366
1367 void
invert()1368 value_range::invert ()
1369 {
1370 /* We can't just invert VR_RANGE and VR_ANTI_RANGE because we may
1371 create non-canonical ranges. Use the constructors instead. */
1372 if (m_kind == VR_RANGE)
1373 *this = value_range (m_min, m_max, VR_ANTI_RANGE);
1374 else if (m_kind == VR_ANTI_RANGE)
1375 *this = value_range (m_min, m_max);
1376 else
1377 gcc_unreachable ();
1378 }
1379
1380 void
dump(FILE * file) const1381 value_range::dump (FILE *file) const
1382 {
1383 if (undefined_p ())
1384 fprintf (file, "UNDEFINED");
1385 else if (m_kind == VR_RANGE || m_kind == VR_ANTI_RANGE)
1386 {
1387 tree ttype = type ();
1388
1389 print_generic_expr (file, ttype);
1390 fprintf (file, " ");
1391
1392 fprintf (file, "%s[", (m_kind == VR_ANTI_RANGE) ? "~" : "");
1393
1394 if (INTEGRAL_TYPE_P (ttype)
1395 && !TYPE_UNSIGNED (ttype)
1396 && vrp_val_is_min (min ())
1397 && TYPE_PRECISION (ttype) != 1)
1398 fprintf (file, "-INF");
1399 else
1400 print_generic_expr (file, min ());
1401
1402 fprintf (file, ", ");
1403
1404 if (supports_type_p (ttype)
1405 && vrp_val_is_max (max ())
1406 && TYPE_PRECISION (ttype) != 1)
1407 fprintf (file, "+INF");
1408 else
1409 print_generic_expr (file, max ());
1410
1411 fprintf (file, "]");
1412 }
1413 else if (varying_p ())
1414 {
1415 print_generic_expr (file, type ());
1416 fprintf (file, " VARYING");
1417 }
1418 else
1419 gcc_unreachable ();
1420 }
1421
1422 void
dump() const1423 value_range::dump () const
1424 {
1425 dump (stderr);
1426 }
1427
1428 void
dump_value_range(FILE * file,const value_range * vr)1429 dump_value_range (FILE *file, const value_range *vr)
1430 {
1431 if (!vr)
1432 fprintf (file, "[]");
1433 else
1434 vr->dump (file);
1435 }
1436
1437 DEBUG_FUNCTION void
debug(const value_range * vr)1438 debug (const value_range *vr)
1439 {
1440 dump_value_range (stderr, vr);
1441 }
1442
1443 DEBUG_FUNCTION void
debug(const value_range & vr)1444 debug (const value_range &vr)
1445 {
1446 dump_value_range (stderr, &vr);
1447 }
1448
1449 /* Create two value-ranges in *VR0 and *VR1 from the anti-range *AR
1450 so that *VR0 U *VR1 == *AR. Returns true if that is possible,
1451 false otherwise. If *AR can be represented with a single range
1452 *VR1 will be VR_UNDEFINED. */
1453
1454 bool
ranges_from_anti_range(const value_range * ar,value_range * vr0,value_range * vr1)1455 ranges_from_anti_range (const value_range *ar,
1456 value_range *vr0, value_range *vr1)
1457 {
1458 tree type = ar->type ();
1459
1460 vr0->set_undefined ();
1461 vr1->set_undefined ();
1462
1463 /* As a future improvement, we could handle ~[0, A] as: [-INF, -1] U
1464 [A+1, +INF]. Not sure if this helps in practice, though. */
1465
1466 if (ar->kind () != VR_ANTI_RANGE
1467 || TREE_CODE (ar->min ()) != INTEGER_CST
1468 || TREE_CODE (ar->max ()) != INTEGER_CST
1469 || !vrp_val_min (type)
1470 || !vrp_val_max (type))
1471 return false;
1472
1473 if (tree_int_cst_lt (vrp_val_min (type), ar->min ()))
1474 vr0->set (vrp_val_min (type),
1475 wide_int_to_tree (type, wi::to_wide (ar->min ()) - 1));
1476 if (tree_int_cst_lt (ar->max (), vrp_val_max (type)))
1477 vr1->set (wide_int_to_tree (type, wi::to_wide (ar->max ()) + 1),
1478 vrp_val_max (type));
1479 if (vr0->undefined_p ())
1480 {
1481 *vr0 = *vr1;
1482 vr1->set_undefined ();
1483 }
1484
1485 return !vr0->undefined_p ();
1486 }
1487
1488 bool
range_has_numeric_bounds_p(const value_range * vr)1489 range_has_numeric_bounds_p (const value_range *vr)
1490 {
1491 return (vr->min ()
1492 && TREE_CODE (vr->min ()) == INTEGER_CST
1493 && TREE_CODE (vr->max ()) == INTEGER_CST);
1494 }
1495
1496 /* Return the maximum value for TYPE. */
1497
1498 tree
vrp_val_max(const_tree type)1499 vrp_val_max (const_tree type)
1500 {
1501 if (INTEGRAL_TYPE_P (type))
1502 return TYPE_MAX_VALUE (type);
1503 if (POINTER_TYPE_P (type))
1504 {
1505 wide_int max = wi::max_value (TYPE_PRECISION (type), TYPE_SIGN (type));
1506 return wide_int_to_tree (const_cast<tree> (type), max);
1507 }
1508 return NULL_TREE;
1509 }
1510
1511 /* Return the minimum value for TYPE. */
1512
1513 tree
vrp_val_min(const_tree type)1514 vrp_val_min (const_tree type)
1515 {
1516 if (INTEGRAL_TYPE_P (type))
1517 return TYPE_MIN_VALUE (type);
1518 if (POINTER_TYPE_P (type))
1519 return build_zero_cst (const_cast<tree> (type));
1520 return NULL_TREE;
1521 }
1522
1523 /* Return whether VAL is equal to the maximum value of its type.
1524 We can't do a simple equality comparison with TYPE_MAX_VALUE because
1525 C typedefs and Ada subtypes can produce types whose TYPE_MAX_VALUE
1526 is not == to the integer constant with the same value in the type. */
1527
1528 bool
vrp_val_is_max(const_tree val)1529 vrp_val_is_max (const_tree val)
1530 {
1531 tree type_max = vrp_val_max (TREE_TYPE (val));
1532 return (val == type_max
1533 || (type_max != NULL_TREE
1534 && operand_equal_p (val, type_max, 0)));
1535 }
1536
1537 /* Return whether VAL is equal to the minimum value of its type. */
1538
1539 bool
vrp_val_is_min(const_tree val)1540 vrp_val_is_min (const_tree val)
1541 {
1542 tree type_min = vrp_val_min (TREE_TYPE (val));
1543 return (val == type_min
1544 || (type_min != NULL_TREE
1545 && operand_equal_p (val, type_min, 0)));
1546 }
1547
1548 /* Return true, if VAL1 and VAL2 are equal values for VRP purposes. */
1549
1550 bool
vrp_operand_equal_p(const_tree val1,const_tree val2)1551 vrp_operand_equal_p (const_tree val1, const_tree val2)
1552 {
1553 if (val1 == val2)
1554 return true;
1555 if (!val1 || !val2 || !operand_equal_p (val1, val2, 0))
1556 return false;
1557 return true;
1558 }
1559