1 /* Support routines for value ranges.
2 Copyright (C) 2019-2020 Free Software Foundation, Inc.
3 Contributed by Aldy Hernandez <aldyh@redhat.com> and
4 Andrew Macleod <amacleod@redhat.com>.
6 This file is part of GCC.
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)
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.
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/>. */
22 #ifndef GCC_VALUE_RANGE_H
23 #define GCC_VALUE_RANGE_H
25 // Types of value ranges.
30 /* Range spans the entire domain. */
32 /* Range is [MIN, MAX]. */
34 /* Range is ~[MIN, MAX]. */
36 /* Range is a nice guy. */
40 // Range of values that can be associated with an SSA_NAME.
42 // This is the base class without any storage.
46 friend class irange_allocator
;
49 void set (tree
, tree
, value_range_kind
= VR_RANGE
);
50 void set_nonzero (tree
);
52 void set_varying (tree type
);
53 void set_undefined ();
56 static bool supports_type_p (tree
);
59 // Iteration over sub-ranges.
60 unsigned num_pairs () const;
61 wide_int
lower_bound (unsigned = 0) const;
62 wide_int
upper_bound (unsigned) const;
63 wide_int
upper_bound () const;
67 bool nonzero_p () const;
68 bool undefined_p () const;
69 bool varying_p () const;
70 bool singleton_p (tree
*result
= NULL
) const;
71 bool contains_p (tree
) const;
73 // In-place operators.
74 void union_ (const irange
&);
75 void intersect (const irange
&);
78 // Operator overloads.
79 irange
& operator= (const irange
&);
80 bool operator== (const irange
&) const;
81 bool operator!= (const irange
&r
) const { return !(*this == r
); }
84 bool fits_p (const irange
&r
) { return m_max_ranges
>= r
.num_pairs (); }
85 void dump (FILE * = stderr
) const;
87 // Deprecated legacy public methods.
88 enum value_range_kind
kind () const; // DEPRECATED
89 tree
min () const; // DEPRECATED
90 tree
max () const; // DEPRECATED
91 bool symbolic_p () const; // DEPRECATED
92 bool constant_p () const; // DEPRECATED
93 void normalize_symbolics (); // DEPRECATED
94 void normalize_addresses (); // DEPRECATED
95 bool may_contain_p (tree
) const; // DEPRECATED
96 void set (tree
); // DEPRECATED
97 bool equal_p (const irange
&) const; // DEPRECATED
98 void union_ (const class irange
*); // DEPRECATED
99 void intersect (const irange
*); // DEPRECATED
102 irange (tree
*, unsigned);
103 // potential promotion to public?
104 tree
tree_lower_bound (unsigned = 0) const;
105 tree
tree_upper_bound (unsigned) const;
106 tree
tree_upper_bound () const;
108 // In-place operators.
109 void irange_union (const irange
&);
110 void irange_intersect (const irange
&);
111 void irange_set (tree
, tree
);
112 void irange_set_anti_range (tree
, tree
);
114 bool swap_out_of_order_endpoints (tree
&min
, tree
&max
, value_range_kind
&);
115 bool normalize_min_max (tree type
, tree min
, tree max
, value_range_kind
);
117 bool legacy_mode_p () const;
118 bool legacy_equal_p (const irange
&) const;
119 void legacy_union (irange
*, const irange
*);
120 void legacy_intersect (irange
*, const irange
*);
121 void verify_range ();
122 unsigned legacy_num_pairs () const;
123 wide_int
legacy_lower_bound (unsigned = 0) const;
124 wide_int
legacy_upper_bound (unsigned) const;
125 int value_inside_range (tree
) const;
126 bool maybe_anti_range () const;
127 void copy_to_legacy (const irange
&);
128 void copy_legacy_to_multi_range (const irange
&);
131 unsigned char m_num_ranges
;
132 unsigned char m_max_ranges
;
133 ENUM_BITFIELD(value_range_kind
) m_kind
: 8;
137 // Here we describe an irange with N pairs of ranges. The storage for
138 // the pairs is embedded in the class as an array.
141 class GTY((user
)) int_range
: public irange
145 int_range (tree
, tree
, value_range_kind
= VR_RANGE
);
146 int_range (tree type
, const wide_int
&, const wide_int
&,
147 value_range_kind
= VR_RANGE
);
148 int_range (tree type
);
149 int_range (const int_range
&);
150 int_range (const irange
&);
151 int_range
& operator= (const int_range
&);
153 template <unsigned X
> friend void gt_ggc_mx (int_range
<X
> *);
154 template <unsigned X
> friend void gt_pch_nx (int_range
<X
> *);
155 template <unsigned X
> friend void gt_pch_nx (int_range
<X
> *,
156 gt_pointer_operator
, void *);
157 // ?? hash-traits.h has its own extern for these, which is causing
158 // them to never be picked up by the templates. For now, define
160 //template<unsigned X> friend void gt_ggc_mx (int_range<X> *&);
161 //template<unsigned X> friend void gt_pch_nx (int_range<X> *&);
162 friend void gt_ggc_mx (int_range
<1> *&);
163 friend void gt_pch_nx (int_range
<1> *&);
168 // This is a special int_range<1> with only one pair, plus
169 // VR_ANTI_RANGE magic to describe slightly more than can be described
170 // in one pair. It is described in the code as a "legacy range" (as
171 // opposed to multi-ranges which have multiple sub-ranges). It is
172 // provided for backward compatibility with code that has not been
173 // converted to multi-range irange's.
175 // There are copy operators to seamlessly copy to/fro multi-ranges.
176 typedef int_range
<1> value_range
;
178 // This is an "infinite" precision irange for use in temporary
180 typedef int_range
<255> int_range_max
;
182 // Returns true for an old-school value_range as described above.
184 irange::legacy_mode_p () const
186 return m_max_ranges
== 1;
189 extern bool range_has_numeric_bounds_p (const irange
*);
190 extern bool ranges_from_anti_range (const value_range
*,
191 value_range
*, value_range
*);
192 extern void dump_value_range (FILE *, const irange
*);
193 extern bool vrp_val_is_min (const_tree
);
194 extern bool vrp_val_is_max (const_tree
);
195 extern bool vrp_operand_equal_p (const_tree
, const_tree
);
197 inline value_range_kind
198 irange::kind () const
200 if (legacy_mode_p ())
212 // Number of sub-ranges in a range.
215 irange::num_pairs () const
217 if (!legacy_mode_p ())
220 return legacy_num_pairs ();
224 irange::type () const
226 gcc_checking_assert (!undefined_p ());
227 return TREE_TYPE (m_base
[0]);
230 // Return the lower bound of a sub-range expressed as a tree. PAIR is
231 // the sub-range in question.
234 irange::tree_lower_bound (unsigned pair
) const
236 return m_base
[pair
* 2];
239 // Return the upper bound of a sub-range expressed as a tree. PAIR is
240 // the sub-range in question.
243 irange::tree_upper_bound (unsigned pair
) const
245 return m_base
[pair
* 2 + 1];
248 // Return the highest bound of a range expressed as a tree.
251 irange::tree_upper_bound () const
253 gcc_checking_assert (m_num_ranges
);
254 return tree_upper_bound (m_num_ranges
- 1);
260 return tree_lower_bound (0);
267 return tree_upper_bound ();
273 irange::varying_p () const
275 if (legacy_mode_p ())
276 return m_kind
== VR_VARYING
;
278 if (m_num_ranges
!= 1)
283 tree t
= TREE_TYPE (l
);
284 if (INTEGRAL_TYPE_P (t
))
285 return l
== TYPE_MIN_VALUE (t
) && u
== TYPE_MAX_VALUE (t
);
286 if (POINTER_TYPE_P (t
))
287 return wi::to_wide (l
) == 0
288 && wi::to_wide (u
) == wi::max_value (TYPE_PRECISION (t
),
295 irange::undefined_p () const
297 if (!legacy_mode_p ())
298 return m_num_ranges
== 0;
300 if (CHECKING_P
&& legacy_mode_p ())
302 if (m_kind
== VR_UNDEFINED
)
303 gcc_checking_assert (m_num_ranges
== 0);
305 gcc_checking_assert (m_num_ranges
!= 0);
307 return m_kind
== VR_UNDEFINED
;
311 irange::zero_p () const
313 return (m_kind
== VR_RANGE
&& m_num_ranges
== 1
314 && integer_zerop (tree_lower_bound (0))
315 && integer_zerop (tree_upper_bound (0)));
319 irange::nonzero_p () const
324 tree zero
= build_zero_cst (type ());
325 return *this == int_range
<1> (zero
, zero
, VR_ANTI_RANGE
);
329 irange::supports_type_p (tree type
)
331 if (type
&& (INTEGRAL_TYPE_P (type
) || POINTER_TYPE_P (type
)))
337 range_includes_zero_p (const irange
*vr
)
339 if (vr
->undefined_p ())
342 if (vr
->varying_p ())
345 return vr
->may_contain_p (build_zero_cst (vr
->type ()));
350 gt_ggc_mx (int_range
<N
> *x
)
352 for (unsigned i
= 0; i
< N
; ++i
)
354 gt_ggc_mx (x
->m_ranges
[i
* 2]);
355 gt_ggc_mx (x
->m_ranges
[i
* 2 + 1]);
361 gt_pch_nx (int_range
<N
> *x
)
363 for (unsigned i
= 0; i
< N
; ++i
)
365 gt_pch_nx (x
->m_ranges
[i
* 2]);
366 gt_pch_nx (x
->m_ranges
[i
* 2 + 1]);
372 gt_pch_nx (int_range
<N
> *x
, gt_pointer_operator op
, void *cookie
)
374 for (unsigned i
= 0; i
< N
; ++i
)
376 op (&x
->m_ranges
[i
* 2], cookie
);
377 op (&x
->m_ranges
[i
* 2 + 1], cookie
);
381 // Constructors for irange
384 irange::irange (tree
*base
, unsigned nranges
)
388 m_max_ranges
= nranges
;
389 if (legacy_mode_p ())
390 m_kind
= VR_UNDEFINED
;
395 // Constructors for int_range<>.
399 int_range
<N
>::int_range ()
400 : irange (m_ranges
, N
)
405 int_range
<N
>::int_range (const int_range
&other
)
406 : irange (m_ranges
, N
)
408 irange::operator= (other
);
412 int_range
<N
>::int_range (tree min
, tree max
, value_range_kind kind
)
413 : irange (m_ranges
, N
)
415 irange::set (min
, max
, kind
);
419 int_range
<N
>::int_range (tree type
)
420 : irange (m_ranges
, N
)
426 int_range
<N
>::int_range (tree type
, const wide_int
&wmin
, const wide_int
&wmax
,
427 value_range_kind kind
)
428 : irange (m_ranges
, N
)
430 tree min
= wide_int_to_tree (type
, wmin
);
431 tree max
= wide_int_to_tree (type
, wmax
);
432 set (min
, max
, kind
);
436 int_range
<N
>::int_range (const irange
&other
)
437 : irange (m_ranges
, N
)
439 irange::operator= (other
);
444 int_range
<N
>::operator= (const int_range
&src
)
446 irange::operator= (src
);
451 irange::set (tree val
)
457 irange::set_undefined ()
460 if (legacy_mode_p ())
461 m_kind
= VR_UNDEFINED
;
465 irange::set_varying (tree type
)
467 if (legacy_mode_p ())
471 if (INTEGRAL_TYPE_P (type
))
473 m_base
[0] = TYPE_MIN_VALUE (type
);
474 m_base
[1] = TYPE_MAX_VALUE (type
);
476 else if (POINTER_TYPE_P (type
))
478 m_base
[0] = build_int_cst (type
, 0);
479 m_base
[1] = build_int_cst (type
, -1);
482 m_base
[0] = m_base
[1] = error_mark_node
;
486 irange::operator== (const irange
&r
) const
491 // Return the lower bound of a sub-range. PAIR is the sub-range in
495 irange::lower_bound (unsigned pair
) const
497 if (legacy_mode_p ())
498 return legacy_lower_bound (pair
);
499 gcc_checking_assert (!undefined_p ());
500 gcc_checking_assert (pair
+ 1 <= num_pairs ());
501 return wi::to_wide (tree_lower_bound (pair
));
504 // Return the upper bound of a sub-range. PAIR is the sub-range in
508 irange::upper_bound (unsigned pair
) const
510 if (legacy_mode_p ())
511 return legacy_upper_bound (pair
);
512 gcc_checking_assert (!undefined_p ());
513 gcc_checking_assert (pair
+ 1 <= num_pairs ());
514 return wi::to_wide (tree_upper_bound (pair
));
517 // Return the highest bound of a range.
520 irange::upper_bound () const
522 unsigned pairs
= num_pairs ();
523 gcc_checking_assert (pairs
> 0);
524 return upper_bound (pairs
- 1);
528 irange::union_ (const irange
&r
)
530 dump_flags_t m_flags
= dump_flags
;
531 dump_flags
&= ~TDF_DETAILS
;
533 dump_flags
= m_flags
;
537 irange::intersect (const irange
&r
)
539 dump_flags_t m_flags
= dump_flags
;
540 dump_flags
&= ~TDF_DETAILS
;
541 irange::intersect (&r
);
542 dump_flags
= m_flags
;
545 // Set value range VR to a nonzero range of type TYPE.
548 irange::set_nonzero (tree type
)
550 tree zero
= build_int_cst (type
, 0);
551 if (legacy_mode_p ())
552 set (zero
, zero
, VR_ANTI_RANGE
);
554 irange_set_anti_range (zero
, zero
);
557 // Set value range VR to a ZERO range of type TYPE.
560 irange::set_zero (tree type
)
562 tree z
= build_int_cst (type
, 0);
563 if (legacy_mode_p ())
569 // Normalize [MIN, MAX] into VARYING and ~[MIN, MAX] into UNDEFINED.
571 // Avoid using TYPE_{MIN,MAX}_VALUE because -fstrict-enums can
572 // restrict those to a subset of what actually fits in the type.
573 // Instead use the extremes of the type precision which will allow
574 // compare_range_with_value() to check if a value is inside a range,
575 // whereas if we used TYPE_*_VAL, said function would just punt upon
579 irange::normalize_min_max (tree type
, tree min
, tree max
,
580 value_range_kind kind
)
582 unsigned prec
= TYPE_PRECISION (type
);
583 signop sign
= TYPE_SIGN (type
);
584 if (wi::eq_p (wi::to_wide (min
), wi::min_value (prec
, sign
))
585 && wi::eq_p (wi::to_wide (max
), wi::max_value (prec
, sign
)))
587 if (kind
== VR_RANGE
)
589 else if (kind
== VR_ANTI_RANGE
)
598 // Return the maximum value for TYPE.
601 vrp_val_max (const_tree type
)
603 if (INTEGRAL_TYPE_P (type
))
604 return TYPE_MAX_VALUE (type
);
605 if (POINTER_TYPE_P (type
))
607 wide_int max
= wi::max_value (TYPE_PRECISION (type
), TYPE_SIGN (type
));
608 return wide_int_to_tree (const_cast<tree
> (type
), max
);
613 // Return the minimum value for TYPE.
616 vrp_val_min (const_tree type
)
618 if (INTEGRAL_TYPE_P (type
))
619 return TYPE_MIN_VALUE (type
);
620 if (POINTER_TYPE_P (type
))
621 return build_zero_cst (const_cast<tree
> (type
));
625 // This is the irange storage class. It is used to allocate the
626 // minimum amount of storage needed for a given irange. Storage is
627 // automatically freed at destruction of the storage class.
629 // It is meant for long term storage, as opposed to int_range_max
630 // which is meant for intermediate temporary results on the stack.
632 // The newly allocated irange is initialized to the empty set
633 // (undefined_p() is true).
635 class irange_allocator
639 ~irange_allocator ();
640 // Return a new range with NUM_PAIRS.
641 irange
*allocate (unsigned num_pairs
);
642 // Return a copy of SRC with the minimum amount of sub-ranges needed
644 irange
*allocate (const irange
&src
);
646 DISABLE_COPY_AND_ASSIGN (irange_allocator
);
647 struct obstack m_obstack
;
651 irange_allocator::irange_allocator ()
653 obstack_init (&m_obstack
);
657 irange_allocator::~irange_allocator ()
659 obstack_free (&m_obstack
, NULL
);
662 // Return a new range with NUM_PAIRS.
665 irange_allocator::allocate (unsigned num_pairs
)
667 // Never allocate 0 pairs.
668 // Don't allocate 1 either, or we get legacy value_range's.
672 size_t nbytes
= sizeof (tree
) * 2 * num_pairs
;
674 // Allocate the irange and required memory for the vector.
675 void *r
= obstack_alloc (&m_obstack
, sizeof (irange
));
676 tree
*mem
= (tree
*) obstack_alloc (&m_obstack
, nbytes
);
677 return new (r
) irange (mem
, num_pairs
);
681 irange_allocator::allocate (const irange
&src
)
683 irange
*r
= allocate (src
.num_pairs ());
688 #endif // GCC_VALUE_RANGE_H