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.
48 void set (tree
, tree
, value_range_kind
= VR_RANGE
);
49 void set_nonzero (tree
);
51 void set_varying (tree type
);
52 void set_undefined ();
55 static bool supports_type_p (tree
);
58 // Iteration over sub-ranges.
59 unsigned num_pairs () const;
60 wide_int
lower_bound (unsigned = 0) const;
61 wide_int
upper_bound (unsigned) const;
62 wide_int
upper_bound () const;
66 bool nonzero_p () const;
67 bool undefined_p () const;
68 bool varying_p () const;
69 bool singleton_p (tree
*result
= NULL
) const;
70 bool contains_p (tree
) const;
72 // In-place operators.
73 void union_ (const irange
&);
74 void intersect (const irange
&);
77 // Operator overloads.
78 irange
& operator= (const irange
&);
79 bool operator== (const irange
&) const;
80 bool operator!= (const irange
&r
) const { return !(*this == r
); }
83 void dump (FILE * = stderr
) const;
85 // Deprecated legacy public methods.
86 enum value_range_kind
kind () const; // DEPRECATED
87 tree
min () const; // DEPRECATED
88 tree
max () const; // DEPRECATED
89 bool symbolic_p () const; // DEPRECATED
90 bool constant_p () const; // DEPRECATED
91 void normalize_symbolics (); // DEPRECATED
92 void normalize_addresses (); // DEPRECATED
93 bool may_contain_p (tree
) const; // DEPRECATED
94 void set (tree
); // DEPRECATED
95 bool equal_p (const irange
&) const; // DEPRECATED
96 void union_ (const class irange
*); // DEPRECATED
97 void intersect (const irange
*); // DEPRECATED
100 irange (tree
*, unsigned);
101 // potential promotion to public?
102 tree
tree_lower_bound (unsigned = 0) const;
103 tree
tree_upper_bound (unsigned) const;
104 tree
tree_upper_bound () const;
106 // In-place operators.
107 void irange_union (const irange
&);
108 void irange_intersect (const irange
&);
109 void irange_set (tree
, tree
);
110 void irange_set_anti_range (tree
, tree
);
112 bool swap_out_of_order_endpoints (tree
&min
, tree
&max
, value_range_kind
&);
113 bool normalize_min_max (tree type
, tree min
, tree max
, value_range_kind
);
115 bool legacy_mode_p () const;
116 bool legacy_equal_p (const irange
&) const;
117 void legacy_union (irange
*, const irange
*);
118 void legacy_intersect (irange
*, const irange
*);
119 void verify_range ();
120 unsigned legacy_num_pairs () const;
121 wide_int
legacy_lower_bound (unsigned = 0) const;
122 wide_int
legacy_upper_bound (unsigned) const;
123 int value_inside_range (tree
) const;
124 bool maybe_anti_range () const;
125 void copy_legacy_range (const irange
&);
128 unsigned char m_num_ranges
;
129 unsigned char m_max_ranges
;
130 ENUM_BITFIELD(value_range_kind
) m_kind
: 8;
134 // Here we describe an irange with N pairs of ranges. The storage for
135 // the pairs is embedded in the class as an array.
138 class GTY((user
)) int_range
: public irange
142 int_range (tree
, tree
, value_range_kind
= VR_RANGE
);
143 int_range (tree type
, const wide_int
&, const wide_int
&,
144 value_range_kind
= VR_RANGE
);
145 int_range (tree type
);
146 int_range (const int_range
&);
147 int_range (const irange
&);
148 int_range
& operator= (const int_range
&);
150 template <unsigned X
> friend void gt_ggc_mx (int_range
<X
> *);
151 template <unsigned X
> friend void gt_pch_nx (int_range
<X
> *);
152 template <unsigned X
> friend void gt_pch_nx (int_range
<X
> *,
153 gt_pointer_operator
, void *);
154 // ?? hash-traits.h has its own extern for these, which is causing
155 // them to never be picked up by the templates. For now, define
157 //template<unsigned X> friend void gt_ggc_mx (int_range<X> *&);
158 //template<unsigned X> friend void gt_pch_nx (int_range<X> *&);
159 friend void gt_ggc_mx (int_range
<1> *&);
160 friend void gt_pch_nx (int_range
<1> *&);
165 // This is a special int_range<1> with only one pair, plus
166 // VR_ANTI_RANGE magic to describe slightly more than can be described
167 // in one pair. It is described in the code as a "legacy range" (as
168 // opposed to multi-ranges which have multiple sub-ranges). It is
169 // provided for backward compatibility with code that has not been
170 // converted to multi-range irange's.
172 // There are copy operators to seamlessly copy to/fro multi-ranges.
173 typedef int_range
<1> value_range
;
175 // This is an "infinite" precision irange for use in temporary
177 typedef int_range
<255> int_range_max
;
179 // Returns true for an old-school value_range as described above.
181 irange::legacy_mode_p () const
183 return m_max_ranges
== 1;
186 extern bool range_has_numeric_bounds_p (const irange
*);
187 extern bool ranges_from_anti_range (const value_range
*,
188 value_range
*, value_range
*);
189 extern void dump_value_range (FILE *, const irange
*);
190 extern bool vrp_val_is_min (const_tree
);
191 extern bool vrp_val_is_max (const_tree
);
192 extern bool vrp_operand_equal_p (const_tree
, const_tree
);
194 inline value_range_kind
195 irange::kind () const
197 if (legacy_mode_p ())
209 // Number of sub-ranges in a range.
212 irange::num_pairs () const
214 if (!legacy_mode_p ())
217 return legacy_num_pairs ();
221 irange::type () const
223 gcc_checking_assert (!undefined_p ());
224 return TREE_TYPE (m_base
[0]);
227 // Return the lower bound of a sub-range expressed as a tree. PAIR is
228 // the sub-range in question.
231 irange::tree_lower_bound (unsigned pair
) const
233 return m_base
[pair
* 2];
236 // Return the upper bound of a sub-range expressed as a tree. PAIR is
237 // the sub-range in question.
240 irange::tree_upper_bound (unsigned pair
) const
242 return m_base
[pair
* 2 + 1];
245 // Return the highest bound of a range expressed as a tree.
248 irange::tree_upper_bound () const
250 gcc_checking_assert (m_num_ranges
);
251 return tree_upper_bound (m_num_ranges
- 1);
257 return tree_lower_bound (0);
264 return tree_upper_bound ();
270 irange::varying_p () const
272 if (legacy_mode_p ())
273 return m_kind
== VR_VARYING
;
275 if (m_num_ranges
!= 1)
280 tree t
= TREE_TYPE (l
);
281 if (INTEGRAL_TYPE_P (t
))
282 return l
== TYPE_MIN_VALUE (t
) && u
== TYPE_MAX_VALUE (t
);
283 if (POINTER_TYPE_P (t
))
284 return wi::to_wide (l
) == 0
285 && wi::to_wide (u
) == wi::max_value (TYPE_PRECISION (t
),
292 irange::undefined_p () const
294 if (!legacy_mode_p ())
295 return m_num_ranges
== 0;
297 if (CHECKING_P
&& legacy_mode_p ())
299 if (m_kind
== VR_UNDEFINED
)
300 gcc_checking_assert (m_num_ranges
== 0);
302 gcc_checking_assert (m_num_ranges
!= 0);
304 return m_kind
== VR_UNDEFINED
;
308 irange::zero_p () const
310 return (m_kind
== VR_RANGE
&& m_num_ranges
== 1
311 && integer_zerop (tree_lower_bound (0))
312 && integer_zerop (tree_upper_bound (0)));
316 irange::nonzero_p () const
321 tree zero
= build_zero_cst (type ());
322 return *this == int_range
<1> (zero
, zero
, VR_ANTI_RANGE
);
326 irange::supports_type_p (tree type
)
328 if (type
&& (INTEGRAL_TYPE_P (type
) || POINTER_TYPE_P (type
)))
334 range_includes_zero_p (const irange
*vr
)
336 if (vr
->undefined_p ())
339 if (vr
->varying_p ())
342 return vr
->may_contain_p (build_zero_cst (vr
->type ()));
347 gt_ggc_mx (int_range
<N
> *x
)
349 for (unsigned i
= 0; i
< N
; ++i
)
351 gt_ggc_mx (x
->m_ranges
[i
* 2]);
352 gt_ggc_mx (x
->m_ranges
[i
* 2 + 1]);
358 gt_pch_nx (int_range
<N
> *x
)
360 for (unsigned i
= 0; i
< N
; ++i
)
362 gt_pch_nx (x
->m_ranges
[i
* 2]);
363 gt_pch_nx (x
->m_ranges
[i
* 2 + 1]);
369 gt_pch_nx (int_range
<N
> *x
, gt_pointer_operator op
, void *cookie
)
371 for (unsigned i
= 0; i
< N
; ++i
)
373 op (&x
->m_ranges
[i
* 2], cookie
);
374 op (&x
->m_ranges
[i
* 2 + 1], cookie
);
378 // Constructors for irange
381 irange::irange (tree
*base
, unsigned nranges
)
385 m_max_ranges
= nranges
;
386 if (legacy_mode_p ())
387 m_kind
= VR_UNDEFINED
;
392 // Constructors for int_range<>.
396 int_range
<N
>::int_range ()
397 : irange (m_ranges
, N
)
402 int_range
<N
>::int_range (const int_range
&other
)
403 : irange (m_ranges
, N
)
405 irange::operator= (other
);
409 int_range
<N
>::int_range (tree min
, tree max
, value_range_kind kind
)
410 : irange (m_ranges
, N
)
412 irange::set (min
, max
, kind
);
416 int_range
<N
>::int_range (tree type
)
417 : irange (m_ranges
, N
)
423 int_range
<N
>::int_range (tree type
, const wide_int
&wmin
, const wide_int
&wmax
,
424 value_range_kind kind
)
425 : irange (m_ranges
, N
)
427 tree min
= wide_int_to_tree (type
, wmin
);
428 tree max
= wide_int_to_tree (type
, wmax
);
429 set (min
, max
, kind
);
433 int_range
<N
>::int_range (const irange
&other
)
434 : irange (m_ranges
, N
)
436 irange::operator= (other
);
441 int_range
<N
>::operator= (const int_range
&src
)
443 irange::operator= (src
);
448 irange::set (tree val
)
454 irange::set_undefined ()
457 if (legacy_mode_p ())
458 m_kind
= VR_UNDEFINED
;
462 irange::set_varying (tree type
)
464 if (legacy_mode_p ())
468 if (INTEGRAL_TYPE_P (type
))
470 m_base
[0] = TYPE_MIN_VALUE (type
);
471 m_base
[1] = TYPE_MAX_VALUE (type
);
473 else if (POINTER_TYPE_P (type
))
475 m_base
[0] = build_int_cst (type
, 0);
476 m_base
[1] = build_int_cst (type
, -1);
479 m_base
[0] = m_base
[1] = error_mark_node
;
483 irange::operator== (const irange
&r
) const
488 // Return the lower bound of a sub-range. PAIR is the sub-range in
492 irange::lower_bound (unsigned pair
) const
494 if (legacy_mode_p ())
495 return legacy_lower_bound (pair
);
496 gcc_checking_assert (!undefined_p ());
497 gcc_checking_assert (pair
+ 1 <= num_pairs ());
498 return wi::to_wide (tree_lower_bound (pair
));
501 // Return the upper bound of a sub-range. PAIR is the sub-range in
505 irange::upper_bound (unsigned pair
) const
507 if (legacy_mode_p ())
508 return legacy_upper_bound (pair
);
509 gcc_checking_assert (!undefined_p ());
510 gcc_checking_assert (pair
+ 1 <= num_pairs ());
511 return wi::to_wide (tree_upper_bound (pair
));
514 // Return the highest bound of a range.
517 irange::upper_bound () const
519 unsigned pairs
= num_pairs ();
520 gcc_checking_assert (pairs
> 0);
521 return upper_bound (pairs
- 1);
525 irange::union_ (const irange
&r
)
527 dump_flags_t m_flags
= dump_flags
;
528 dump_flags
&= ~TDF_DETAILS
;
530 dump_flags
= m_flags
;
534 irange::intersect (const irange
&r
)
536 dump_flags_t m_flags
= dump_flags
;
537 dump_flags
&= ~TDF_DETAILS
;
538 irange::intersect (&r
);
539 dump_flags
= m_flags
;
542 // Set value range VR to a nonzero range of type TYPE.
545 irange::set_nonzero (tree type
)
547 tree zero
= build_int_cst (type
, 0);
548 if (legacy_mode_p ())
549 set (zero
, zero
, VR_ANTI_RANGE
);
551 irange_set_anti_range (zero
, zero
);
554 // Set value range VR to a ZERO range of type TYPE.
557 irange::set_zero (tree type
)
559 tree z
= build_int_cst (type
, 0);
560 if (legacy_mode_p ())
566 // Normalize [MIN, MAX] into VARYING and ~[MIN, MAX] into UNDEFINED.
568 // Avoid using TYPE_{MIN,MAX}_VALUE because -fstrict-enums can
569 // restrict those to a subset of what actually fits in the type.
570 // Instead use the extremes of the type precision which will allow
571 // compare_range_with_value() to check if a value is inside a range,
572 // whereas if we used TYPE_*_VAL, said function would just punt upon
576 irange::normalize_min_max (tree type
, tree min
, tree max
,
577 value_range_kind kind
)
579 unsigned prec
= TYPE_PRECISION (type
);
580 signop sign
= TYPE_SIGN (type
);
581 if (wi::eq_p (wi::to_wide (min
), wi::min_value (prec
, sign
))
582 && wi::eq_p (wi::to_wide (max
), wi::max_value (prec
, sign
)))
584 if (kind
== VR_RANGE
)
586 else if (kind
== VR_ANTI_RANGE
)
595 // Return the maximum value for TYPE.
598 vrp_val_max (const_tree type
)
600 if (INTEGRAL_TYPE_P (type
))
601 return TYPE_MAX_VALUE (type
);
602 if (POINTER_TYPE_P (type
))
604 wide_int max
= wi::max_value (TYPE_PRECISION (type
), TYPE_SIGN (type
));
605 return wide_int_to_tree (const_cast<tree
> (type
), max
);
610 // Return the minimum value for TYPE.
613 vrp_val_min (const_tree type
)
615 if (INTEGRAL_TYPE_P (type
))
616 return TYPE_MIN_VALUE (type
);
617 if (POINTER_TYPE_P (type
))
618 return build_zero_cst (const_cast<tree
> (type
));
622 #endif // GCC_VALUE_RANGE_H