Daily bump.
[official-gcc.git] / gcc / value-range.h
blob32200ff890f18b2c3bd657d2a40fe0a02061275e
1 /* Support routines for value ranges.
2 Copyright (C) 2019-2021 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)
11 any later version.
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.
26 enum value_range_kind
28 /* Empty range. */
29 VR_UNDEFINED,
30 /* Range spans the entire domain. */
31 VR_VARYING,
32 /* Range is [MIN, MAX]. */
33 VR_RANGE,
34 /* Range is ~[MIN, MAX]. */
35 VR_ANTI_RANGE,
36 /* Range is a nice guy. */
37 VR_LAST
40 // Range of values that can be associated with an SSA_NAME.
42 // This is the base class without any storage.
44 class GTY((user)) irange
46 friend class irange_allocator;
47 public:
48 // In-place setters.
49 void set (tree, tree, value_range_kind = VR_RANGE);
50 void set_nonzero (tree);
51 void set_zero (tree);
52 void set_varying (tree type);
53 void set_undefined ();
55 // Range types.
56 static bool supports_type_p (tree);
57 tree type () const;
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;
65 // Predicates.
66 bool zero_p () 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 &);
76 void intersect (const wide_int& lb, const wide_int& ub);
77 void invert ();
79 // Operator overloads.
80 irange& operator= (const irange &);
81 bool operator== (const irange &) const;
82 bool operator!= (const irange &r) const { return !(*this == r); }
84 // Misc methods.
85 bool fits_p (const irange &r) { return m_max_ranges >= r.num_pairs (); }
86 void dump (FILE * = stderr) const;
87 void debug () const;
89 // Deprecated legacy public methods.
90 enum value_range_kind kind () const; // DEPRECATED
91 tree min () const; // DEPRECATED
92 tree max () const; // DEPRECATED
93 bool symbolic_p () const; // DEPRECATED
94 bool constant_p () const; // DEPRECATED
95 void normalize_symbolics (); // DEPRECATED
96 void normalize_addresses (); // DEPRECATED
97 bool may_contain_p (tree) const; // DEPRECATED
98 void set (tree); // DEPRECATED
99 bool equal_p (const irange &) const; // DEPRECATED
100 void union_ (const class irange *); // DEPRECATED
101 void intersect (const irange *); // DEPRECATED
103 protected:
104 irange (tree *, unsigned);
105 // potential promotion to public?
106 tree tree_lower_bound (unsigned = 0) const;
107 tree tree_upper_bound (unsigned) const;
108 tree tree_upper_bound () const;
110 // In-place operators.
111 void irange_union (const irange &);
112 void irange_intersect (const irange &);
113 void irange_set (tree, tree);
114 void irange_set_anti_range (tree, tree);
116 void normalize_kind ();
118 bool legacy_mode_p () const;
119 bool legacy_equal_p (const irange &) const;
120 void legacy_union (irange *, const irange *);
121 void legacy_intersect (irange *, const irange *);
122 void verify_range ();
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 &);
130 private:
131 friend void gt_ggc_mx (irange *);
132 friend void gt_pch_nx (irange *);
133 friend void gt_pch_nx (irange *, gt_pointer_operator, void *);
135 void irange_set_1bit_anti_range (tree, tree);
136 bool varying_compatible_p () const;
138 unsigned char m_num_ranges;
139 unsigned char m_max_ranges;
140 ENUM_BITFIELD(value_range_kind) m_kind : 8;
141 tree *m_base;
144 // Here we describe an irange with N pairs of ranges. The storage for
145 // the pairs is embedded in the class as an array.
147 template<unsigned N>
148 class GTY((user)) int_range : public irange
150 public:
151 int_range ();
152 int_range (tree, tree, value_range_kind = VR_RANGE);
153 int_range (tree type, const wide_int &, const wide_int &,
154 value_range_kind = VR_RANGE);
155 int_range (tree type);
156 int_range (const int_range &);
157 int_range (const irange &);
158 int_range& operator= (const int_range &);
159 private:
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 template <unsigned X> friend void gt_pch_nx (int_range<X> *,
163 gt_pointer_operator, void *);
165 // ?? These stubs are for ipa-prop.c which use a value_range in a
166 // hash_traits. hash-traits.h defines an extern of gt_ggc_mx (T &)
167 // instead of picking up the gt_ggc_mx (T *) version.
168 friend void gt_ggc_mx (int_range<1> *&);
169 friend void gt_pch_nx (int_range<1> *&);
171 tree m_ranges[N*2];
174 // This is a special int_range<1> with only one pair, plus
175 // VR_ANTI_RANGE magic to describe slightly more than can be described
176 // in one pair. It is described in the code as a "legacy range" (as
177 // opposed to multi-ranges which have multiple sub-ranges). It is
178 // provided for backward compatibility with code that has not been
179 // converted to multi-range irange's.
181 // There are copy operators to seamlessly copy to/fro multi-ranges.
182 typedef int_range<1> value_range;
184 // This is an "infinite" precision irange for use in temporary
185 // calculations.
186 typedef int_range<255> int_range_max;
188 // Returns true for an old-school value_range as described above.
189 inline bool
190 irange::legacy_mode_p () const
192 return m_max_ranges == 1;
195 extern bool range_has_numeric_bounds_p (const irange *);
196 extern bool ranges_from_anti_range (const value_range *,
197 value_range *, value_range *);
198 extern void dump_value_range (FILE *, const irange *);
199 extern bool vrp_val_is_min (const_tree);
200 extern bool vrp_val_is_max (const_tree);
201 extern bool vrp_operand_equal_p (const_tree, const_tree);
203 inline value_range_kind
204 irange::kind () const
206 return m_kind;
209 // Number of sub-ranges in a range.
211 inline unsigned
212 irange::num_pairs () const
214 if (m_kind == VR_ANTI_RANGE)
215 return constant_p () ? 2 : 1;
216 else
217 return m_num_ranges;
220 inline tree
221 irange::type () const
223 gcc_checking_assert (m_num_ranges > 0);
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.
230 inline tree
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.
239 inline tree
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.
247 inline tree
248 irange::tree_upper_bound () const
250 gcc_checking_assert (m_num_ranges);
251 return tree_upper_bound (m_num_ranges - 1);
254 inline tree
255 irange::min () const
257 return tree_lower_bound (0);
260 inline tree
261 irange::max () const
263 if (m_num_ranges)
264 return tree_upper_bound ();
265 else
266 return NULL;
269 inline bool
270 irange::varying_compatible_p () const
272 if (m_num_ranges != 1)
273 return false;
275 tree l = m_base[0];
276 tree u = m_base[1];
277 tree t = TREE_TYPE (l);
279 if (m_kind == VR_VARYING && t == error_mark_node)
280 return true;
282 unsigned prec = TYPE_PRECISION (t);
283 signop sign = TYPE_SIGN (t);
284 if (INTEGRAL_TYPE_P (t))
285 return (wi::to_wide (l) == wi::min_value (prec, sign)
286 && wi::to_wide (u) == wi::max_value (prec, sign));
287 if (POINTER_TYPE_P (t))
288 return (wi::to_wide (l) == 0
289 && wi::to_wide (u) == wi::max_value (prec, sign));
290 return true;
293 inline bool
294 irange::varying_p () const
296 return m_kind == VR_VARYING;
299 inline bool
300 irange::undefined_p () const
302 return m_kind == VR_UNDEFINED;
305 inline bool
306 irange::zero_p () const
308 return (m_kind == VR_RANGE && m_num_ranges == 1
309 && integer_zerop (tree_lower_bound (0))
310 && integer_zerop (tree_upper_bound (0)));
313 inline bool
314 irange::nonzero_p () const
316 if (undefined_p ())
317 return false;
319 tree zero = build_zero_cst (type ());
320 return *this == int_range<1> (zero, zero, VR_ANTI_RANGE);
323 inline bool
324 irange::supports_type_p (tree type)
326 if (type && (INTEGRAL_TYPE_P (type) || POINTER_TYPE_P (type)))
327 return type;
328 return false;
331 inline bool
332 range_includes_zero_p (const irange *vr)
334 if (vr->undefined_p ())
335 return false;
337 if (vr->varying_p ())
338 return true;
340 return vr->may_contain_p (build_zero_cst (vr->type ()));
343 inline void
344 gt_ggc_mx (irange *x)
346 for (unsigned i = 0; i < x->m_num_ranges; ++i)
348 gt_ggc_mx (x->m_base[i * 2]);
349 gt_ggc_mx (x->m_base[i * 2 + 1]);
353 inline void
354 gt_pch_nx (irange *x)
356 for (unsigned i = 0; i < x->m_num_ranges; ++i)
358 gt_pch_nx (x->m_base[i * 2]);
359 gt_pch_nx (x->m_base[i * 2 + 1]);
363 inline void
364 gt_pch_nx (irange *x, gt_pointer_operator op, void *cookie)
366 for (unsigned i = 0; i < x->m_num_ranges; ++i)
368 op (&x->m_base[i * 2], cookie);
369 op (&x->m_base[i * 2 + 1], cookie);
373 template<unsigned N>
374 inline void
375 gt_ggc_mx (int_range<N> *x)
377 gt_ggc_mx ((irange *) x);
380 template<unsigned N>
381 inline void
382 gt_pch_nx (int_range<N> *x)
384 gt_pch_nx ((irange *) x);
387 template<unsigned N>
388 inline void
389 gt_pch_nx (int_range<N> *x, gt_pointer_operator op, void *cookie)
391 gt_pch_nx ((irange *) x, op, cookie);
394 // Constructors for irange
396 inline
397 irange::irange (tree *base, unsigned nranges)
399 m_base = base;
400 m_num_ranges = 0;
401 m_max_ranges = nranges;
402 m_kind = VR_UNDEFINED;
405 // Constructors for int_range<>.
407 template<unsigned N>
408 inline
409 int_range<N>::int_range ()
410 : irange (m_ranges, N)
414 template<unsigned N>
415 int_range<N>::int_range (const int_range &other)
416 : irange (m_ranges, N)
418 irange::operator= (other);
421 template<unsigned N>
422 int_range<N>::int_range (tree min, tree max, value_range_kind kind)
423 : irange (m_ranges, N)
425 irange::set (min, max, kind);
428 template<unsigned N>
429 int_range<N>::int_range (tree type)
430 : irange (m_ranges, N)
432 set_varying (type);
435 template<unsigned N>
436 int_range<N>::int_range (tree type, const wide_int &wmin, const wide_int &wmax,
437 value_range_kind kind)
438 : irange (m_ranges, N)
440 tree min = wide_int_to_tree (type, wmin);
441 tree max = wide_int_to_tree (type, wmax);
442 set (min, max, kind);
445 template<unsigned N>
446 int_range<N>::int_range (const irange &other)
447 : irange (m_ranges, N)
449 irange::operator= (other);
452 template<unsigned N>
453 int_range<N>&
454 int_range<N>::operator= (const int_range &src)
456 irange::operator= (src);
457 return *this;
460 inline void
461 irange::set (tree val)
463 set (val, val);
466 inline void
467 irange::set_undefined ()
469 m_kind = VR_UNDEFINED;
470 m_num_ranges = 0;
473 inline void
474 irange::set_varying (tree type)
476 m_kind = VR_VARYING;
477 m_num_ranges = 1;
479 if (INTEGRAL_TYPE_P (type))
481 // Strict enum's require varying to be not TYPE_MIN/MAX, but rather
482 // min_value and max_value.
483 wide_int min = wi::min_value (TYPE_PRECISION (type), TYPE_SIGN (type));
484 wide_int max = wi::max_value (TYPE_PRECISION (type), TYPE_SIGN (type));
485 if (wi::eq_p (max, wi::to_wide (TYPE_MAX_VALUE (type)))
486 && wi::eq_p (min, wi::to_wide (TYPE_MIN_VALUE (type))))
488 m_base[0] = TYPE_MIN_VALUE (type);
489 m_base[1] = TYPE_MAX_VALUE (type);
491 else
493 m_base[0] = wide_int_to_tree (type, min);
494 m_base[1] = wide_int_to_tree (type, max);
497 else if (POINTER_TYPE_P (type))
499 m_base[0] = build_int_cst (type, 0);
500 m_base[1] = build_int_cst (type, -1);
502 else
503 m_base[0] = m_base[1] = error_mark_node;
506 inline bool
507 irange::operator== (const irange &r) const
509 return equal_p (r);
512 // Return the lower bound of a sub-range. PAIR is the sub-range in
513 // question.
515 inline wide_int
516 irange::lower_bound (unsigned pair) const
518 if (legacy_mode_p ())
519 return legacy_lower_bound (pair);
520 gcc_checking_assert (m_num_ranges > 0);
521 gcc_checking_assert (pair + 1 <= num_pairs ());
522 return wi::to_wide (tree_lower_bound (pair));
525 // Return the upper bound of a sub-range. PAIR is the sub-range in
526 // question.
528 inline wide_int
529 irange::upper_bound (unsigned pair) const
531 if (legacy_mode_p ())
532 return legacy_upper_bound (pair);
533 gcc_checking_assert (m_num_ranges > 0);
534 gcc_checking_assert (pair + 1 <= num_pairs ());
535 return wi::to_wide (tree_upper_bound (pair));
538 // Return the highest bound of a range.
540 inline wide_int
541 irange::upper_bound () const
543 unsigned pairs = num_pairs ();
544 gcc_checking_assert (pairs > 0);
545 return upper_bound (pairs - 1);
548 inline void
549 irange::union_ (const irange &r)
551 dump_flags_t m_flags = dump_flags;
552 dump_flags &= ~TDF_DETAILS;
553 irange::union_ (&r);
554 dump_flags = m_flags;
557 inline void
558 irange::intersect (const irange &r)
560 dump_flags_t m_flags = dump_flags;
561 dump_flags &= ~TDF_DETAILS;
562 irange::intersect (&r);
563 dump_flags = m_flags;
566 // Set value range VR to a nonzero range of type TYPE.
568 inline void
569 irange::set_nonzero (tree type)
571 tree zero = build_int_cst (type, 0);
572 if (legacy_mode_p ())
573 set (zero, zero, VR_ANTI_RANGE);
574 else
575 irange_set_anti_range (zero, zero);
578 // Set value range VR to a ZERO range of type TYPE.
580 inline void
581 irange::set_zero (tree type)
583 tree z = build_int_cst (type, 0);
584 if (legacy_mode_p ())
585 set (z);
586 else
587 irange_set (z, z);
590 // Normalize a range to VARYING or UNDEFINED if possible.
592 inline void
593 irange::normalize_kind ()
595 if (m_num_ranges == 0)
596 m_kind = VR_UNDEFINED;
597 else if (varying_compatible_p ())
599 if (m_kind == VR_RANGE)
600 m_kind = VR_VARYING;
601 else if (m_kind == VR_ANTI_RANGE)
602 set_undefined ();
603 else
604 gcc_unreachable ();
608 // Return the maximum value for TYPE.
610 inline tree
611 vrp_val_max (const_tree type)
613 if (INTEGRAL_TYPE_P (type))
614 return TYPE_MAX_VALUE (type);
615 if (POINTER_TYPE_P (type))
617 wide_int max = wi::max_value (TYPE_PRECISION (type), TYPE_SIGN (type));
618 return wide_int_to_tree (const_cast<tree> (type), max);
620 return NULL_TREE;
623 // Return the minimum value for TYPE.
625 inline tree
626 vrp_val_min (const_tree type)
628 if (INTEGRAL_TYPE_P (type))
629 return TYPE_MIN_VALUE (type);
630 if (POINTER_TYPE_P (type))
631 return build_zero_cst (const_cast<tree> (type));
632 return NULL_TREE;
635 // This is the irange storage class. It is used to allocate the
636 // minimum amount of storage needed for a given irange. Storage is
637 // automatically freed at destruction of the storage class.
639 // It is meant for long term storage, as opposed to int_range_max
640 // which is meant for intermediate temporary results on the stack.
642 // The newly allocated irange is initialized to the empty set
643 // (undefined_p() is true).
645 class irange_allocator
647 public:
648 irange_allocator ();
649 ~irange_allocator ();
650 // Return a new range with NUM_PAIRS.
651 irange *allocate (unsigned num_pairs);
652 // Return a copy of SRC with the minimum amount of sub-ranges needed
653 // to represent it.
654 irange *allocate (const irange &src);
655 void *get_memory (unsigned num_bytes);
656 private:
657 DISABLE_COPY_AND_ASSIGN (irange_allocator);
658 struct obstack m_obstack;
661 inline
662 irange_allocator::irange_allocator ()
664 obstack_init (&m_obstack);
667 inline
668 irange_allocator::~irange_allocator ()
670 obstack_free (&m_obstack, NULL);
673 // Provide a hunk of memory from the obstack.
674 inline void *
675 irange_allocator::get_memory (unsigned num_bytes)
677 void *r = obstack_alloc (&m_obstack, num_bytes);
678 return r;
681 // Return a new range with NUM_PAIRS.
683 inline irange *
684 irange_allocator::allocate (unsigned num_pairs)
686 // Never allocate 0 pairs.
687 // Don't allocate 1 either, or we get legacy value_range's.
688 if (num_pairs < 2)
689 num_pairs = 2;
691 size_t nbytes = sizeof (tree) * 2 * num_pairs;
693 // Allocate the irange and required memory for the vector.
694 void *r = obstack_alloc (&m_obstack, sizeof (irange));
695 tree *mem = (tree *) obstack_alloc (&m_obstack, nbytes);
696 return new (r) irange (mem, num_pairs);
699 inline irange *
700 irange_allocator::allocate (const irange &src)
702 irange *r = allocate (src.num_pairs ());
703 *r = src;
704 return r;
707 #endif // GCC_VALUE_RANGE_H