Daily bump.
[official-gcc.git] / gcc / value-range.h
bloba8adc50b98ef836d47b4bbc46547529cc9bf3caa
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 invert ();
78 // Operator overloads.
79 irange& operator= (const irange &);
80 bool operator== (const irange &) const;
81 bool operator!= (const irange &r) const { return !(*this == r); }
83 // Misc methods.
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
101 protected:
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 void normalize_kind ();
116 bool legacy_mode_p () const;
117 bool legacy_equal_p (const irange &) const;
118 void legacy_union (irange *, const irange *);
119 void legacy_intersect (irange *, const irange *);
120 void verify_range ();
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_to_legacy (const irange &);
126 void copy_legacy_to_multi_range (const irange &);
128 private:
129 friend void gt_ggc_mx (irange *);
130 friend void gt_pch_nx (irange *);
131 friend void gt_pch_nx (irange *, gt_pointer_operator, void *);
133 void irange_set_1bit_anti_range (tree, tree);
134 bool varying_compatible_p () const;
136 unsigned char m_num_ranges;
137 unsigned char m_max_ranges;
138 ENUM_BITFIELD(value_range_kind) m_kind : 8;
139 tree *m_base;
142 // Here we describe an irange with N pairs of ranges. The storage for
143 // the pairs is embedded in the class as an array.
145 template<unsigned N>
146 class GTY((user)) int_range : public irange
148 public:
149 int_range ();
150 int_range (tree, tree, value_range_kind = VR_RANGE);
151 int_range (tree type, const wide_int &, const wide_int &,
152 value_range_kind = VR_RANGE);
153 int_range (tree type);
154 int_range (const int_range &);
155 int_range (const irange &);
156 int_range& operator= (const int_range &);
157 private:
158 template <unsigned X> friend void gt_ggc_mx (int_range<X> *);
159 template <unsigned X> friend void gt_pch_nx (int_range<X> *);
160 template <unsigned X> friend void gt_pch_nx (int_range<X> *,
161 gt_pointer_operator, void *);
163 // ?? These stubs are for ipa-prop.c which use a value_range in a
164 // hash_traits. hash-traits.h defines an extern of gt_ggc_mx (T &)
165 // instead of picking up the gt_ggc_mx (T *) version.
166 friend void gt_ggc_mx (int_range<1> *&);
167 friend void gt_pch_nx (int_range<1> *&);
169 tree m_ranges[N*2];
172 // This is a special int_range<1> with only one pair, plus
173 // VR_ANTI_RANGE magic to describe slightly more than can be described
174 // in one pair. It is described in the code as a "legacy range" (as
175 // opposed to multi-ranges which have multiple sub-ranges). It is
176 // provided for backward compatibility with code that has not been
177 // converted to multi-range irange's.
179 // There are copy operators to seamlessly copy to/fro multi-ranges.
180 typedef int_range<1> value_range;
182 // This is an "infinite" precision irange for use in temporary
183 // calculations.
184 typedef int_range<255> int_range_max;
186 // Returns true for an old-school value_range as described above.
187 inline bool
188 irange::legacy_mode_p () const
190 return m_max_ranges == 1;
193 extern bool range_has_numeric_bounds_p (const irange *);
194 extern bool ranges_from_anti_range (const value_range *,
195 value_range *, value_range *);
196 extern void dump_value_range (FILE *, const irange *);
197 extern bool vrp_val_is_min (const_tree);
198 extern bool vrp_val_is_max (const_tree);
199 extern bool vrp_operand_equal_p (const_tree, const_tree);
201 inline value_range_kind
202 irange::kind () const
204 return m_kind;
207 // Number of sub-ranges in a range.
209 inline unsigned
210 irange::num_pairs () const
212 if (m_kind == VR_ANTI_RANGE)
213 return constant_p () ? 2 : 1;
214 else
215 return m_num_ranges;
218 inline tree
219 irange::type () const
221 gcc_checking_assert (m_num_ranges > 0);
222 return TREE_TYPE (m_base[0]);
225 // Return the lower bound of a sub-range expressed as a tree. PAIR is
226 // the sub-range in question.
228 inline tree
229 irange::tree_lower_bound (unsigned pair) const
231 return m_base[pair * 2];
234 // Return the upper bound of a sub-range expressed as a tree. PAIR is
235 // the sub-range in question.
237 inline tree
238 irange::tree_upper_bound (unsigned pair) const
240 return m_base[pair * 2 + 1];
243 // Return the highest bound of a range expressed as a tree.
245 inline tree
246 irange::tree_upper_bound () const
248 gcc_checking_assert (m_num_ranges);
249 return tree_upper_bound (m_num_ranges - 1);
252 inline tree
253 irange::min () const
255 return tree_lower_bound (0);
258 inline tree
259 irange::max () const
261 if (m_num_ranges)
262 return tree_upper_bound ();
263 else
264 return NULL;
267 inline bool
268 irange::varying_compatible_p () const
270 if (m_num_ranges != 1)
271 return false;
273 tree l = m_base[0];
274 tree u = m_base[1];
275 tree t = TREE_TYPE (l);
277 if (m_kind == VR_VARYING && t == error_mark_node)
278 return true;
280 unsigned prec = TYPE_PRECISION (t);
281 signop sign = TYPE_SIGN (t);
282 if (INTEGRAL_TYPE_P (t))
283 return (wi::to_wide (l) == wi::min_value (prec, sign)
284 && wi::to_wide (u) == wi::max_value (prec, sign));
285 if (POINTER_TYPE_P (t))
286 return (wi::to_wide (l) == 0
287 && wi::to_wide (u) == wi::max_value (prec, sign));
288 return true;
291 inline bool
292 irange::varying_p () const
294 return m_kind == VR_VARYING;
297 inline bool
298 irange::undefined_p () const
300 return m_kind == VR_UNDEFINED;
303 inline bool
304 irange::zero_p () const
306 return (m_kind == VR_RANGE && m_num_ranges == 1
307 && integer_zerop (tree_lower_bound (0))
308 && integer_zerop (tree_upper_bound (0)));
311 inline bool
312 irange::nonzero_p () const
314 if (undefined_p ())
315 return false;
317 tree zero = build_zero_cst (type ());
318 return *this == int_range<1> (zero, zero, VR_ANTI_RANGE);
321 inline bool
322 irange::supports_type_p (tree type)
324 if (type && (INTEGRAL_TYPE_P (type) || POINTER_TYPE_P (type)))
325 return type;
326 return false;
329 inline bool
330 range_includes_zero_p (const irange *vr)
332 if (vr->undefined_p ())
333 return false;
335 if (vr->varying_p ())
336 return true;
338 return vr->may_contain_p (build_zero_cst (vr->type ()));
341 inline void
342 gt_ggc_mx (irange *x)
344 for (unsigned i = 0; i < x->m_num_ranges; ++i)
346 gt_ggc_mx (x->m_base[i * 2]);
347 gt_ggc_mx (x->m_base[i * 2 + 1]);
351 inline void
352 gt_pch_nx (irange *x)
354 for (unsigned i = 0; i < x->m_num_ranges; ++i)
356 gt_pch_nx (x->m_base[i * 2]);
357 gt_pch_nx (x->m_base[i * 2 + 1]);
361 inline void
362 gt_pch_nx (irange *x, gt_pointer_operator op, void *cookie)
364 for (unsigned i = 0; i < x->m_num_ranges; ++i)
366 op (&x->m_base[i * 2], cookie);
367 op (&x->m_base[i * 2 + 1], cookie);
371 template<unsigned N>
372 inline void
373 gt_ggc_mx (int_range<N> *x)
375 gt_ggc_mx ((irange *) x);
378 template<unsigned N>
379 inline void
380 gt_pch_nx (int_range<N> *x)
382 gt_pch_nx ((irange *) x);
385 template<unsigned N>
386 inline void
387 gt_pch_nx (int_range<N> *x, gt_pointer_operator op, void *cookie)
389 gt_pch_nx ((irange *) x, op, cookie);
392 // Constructors for irange
394 inline
395 irange::irange (tree *base, unsigned nranges)
397 m_base = base;
398 m_num_ranges = 0;
399 m_max_ranges = nranges;
400 m_kind = VR_UNDEFINED;
403 // Constructors for int_range<>.
405 template<unsigned N>
406 inline
407 int_range<N>::int_range ()
408 : irange (m_ranges, N)
412 template<unsigned N>
413 int_range<N>::int_range (const int_range &other)
414 : irange (m_ranges, N)
416 irange::operator= (other);
419 template<unsigned N>
420 int_range<N>::int_range (tree min, tree max, value_range_kind kind)
421 : irange (m_ranges, N)
423 irange::set (min, max, kind);
426 template<unsigned N>
427 int_range<N>::int_range (tree type)
428 : irange (m_ranges, N)
430 set_varying (type);
433 template<unsigned N>
434 int_range<N>::int_range (tree type, const wide_int &wmin, const wide_int &wmax,
435 value_range_kind kind)
436 : irange (m_ranges, N)
438 tree min = wide_int_to_tree (type, wmin);
439 tree max = wide_int_to_tree (type, wmax);
440 set (min, max, kind);
443 template<unsigned N>
444 int_range<N>::int_range (const irange &other)
445 : irange (m_ranges, N)
447 irange::operator= (other);
450 template<unsigned N>
451 int_range<N>&
452 int_range<N>::operator= (const int_range &src)
454 irange::operator= (src);
455 return *this;
458 inline void
459 irange::set (tree val)
461 set (val, val);
464 inline void
465 irange::set_undefined ()
467 m_kind = VR_UNDEFINED;
468 m_num_ranges = 0;
471 inline void
472 irange::set_varying (tree type)
474 m_kind = VR_VARYING;
475 m_num_ranges = 1;
477 if (INTEGRAL_TYPE_P (type))
479 wide_int min = wi::min_value (TYPE_PRECISION (type), TYPE_SIGN (type));
480 wide_int max = wi::max_value (TYPE_PRECISION (type), TYPE_SIGN (type));
481 m_base[0] = wide_int_to_tree (type, min);
482 m_base[1] = wide_int_to_tree (type, max);
484 else if (POINTER_TYPE_P (type))
486 m_base[0] = build_int_cst (type, 0);
487 m_base[1] = build_int_cst (type, -1);
489 else
490 m_base[0] = m_base[1] = error_mark_node;
493 inline bool
494 irange::operator== (const irange &r) const
496 return equal_p (r);
499 // Return the lower bound of a sub-range. PAIR is the sub-range in
500 // question.
502 inline wide_int
503 irange::lower_bound (unsigned pair) const
505 if (legacy_mode_p ())
506 return legacy_lower_bound (pair);
507 gcc_checking_assert (m_num_ranges > 0);
508 gcc_checking_assert (pair + 1 <= num_pairs ());
509 return wi::to_wide (tree_lower_bound (pair));
512 // Return the upper bound of a sub-range. PAIR is the sub-range in
513 // question.
515 inline wide_int
516 irange::upper_bound (unsigned pair) const
518 if (legacy_mode_p ())
519 return legacy_upper_bound (pair);
520 gcc_checking_assert (m_num_ranges > 0);
521 gcc_checking_assert (pair + 1 <= num_pairs ());
522 return wi::to_wide (tree_upper_bound (pair));
525 // Return the highest bound of a range.
527 inline wide_int
528 irange::upper_bound () const
530 unsigned pairs = num_pairs ();
531 gcc_checking_assert (pairs > 0);
532 return upper_bound (pairs - 1);
535 inline void
536 irange::union_ (const irange &r)
538 dump_flags_t m_flags = dump_flags;
539 dump_flags &= ~TDF_DETAILS;
540 irange::union_ (&r);
541 dump_flags = m_flags;
544 inline void
545 irange::intersect (const irange &r)
547 dump_flags_t m_flags = dump_flags;
548 dump_flags &= ~TDF_DETAILS;
549 irange::intersect (&r);
550 dump_flags = m_flags;
553 // Set value range VR to a nonzero range of type TYPE.
555 inline void
556 irange::set_nonzero (tree type)
558 tree zero = build_int_cst (type, 0);
559 if (legacy_mode_p ())
560 set (zero, zero, VR_ANTI_RANGE);
561 else
562 irange_set_anti_range (zero, zero);
565 // Set value range VR to a ZERO range of type TYPE.
567 inline void
568 irange::set_zero (tree type)
570 tree z = build_int_cst (type, 0);
571 if (legacy_mode_p ())
572 set (z);
573 else
574 irange_set (z, z);
577 // Normalize a range to VARYING or UNDEFINED if possible.
579 inline void
580 irange::normalize_kind ()
582 if (m_num_ranges == 0)
583 m_kind = VR_UNDEFINED;
584 else if (varying_compatible_p ())
586 if (m_kind == VR_RANGE)
587 m_kind = VR_VARYING;
588 else if (m_kind == VR_ANTI_RANGE)
589 set_undefined ();
590 else
591 gcc_unreachable ();
595 // Return the maximum value for TYPE.
597 inline tree
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);
607 return NULL_TREE;
610 // Return the minimum value for TYPE.
612 inline tree
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));
619 return NULL_TREE;
622 // This is the irange storage class. It is used to allocate the
623 // minimum amount of storage needed for a given irange. Storage is
624 // automatically freed at destruction of the storage class.
626 // It is meant for long term storage, as opposed to int_range_max
627 // which is meant for intermediate temporary results on the stack.
629 // The newly allocated irange is initialized to the empty set
630 // (undefined_p() is true).
632 class irange_allocator
634 public:
635 irange_allocator ();
636 ~irange_allocator ();
637 // Return a new range with NUM_PAIRS.
638 irange *allocate (unsigned num_pairs);
639 // Return a copy of SRC with the minimum amount of sub-ranges needed
640 // to represent it.
641 irange *allocate (const irange &src);
642 void *get_memory (unsigned num_bytes);
643 private:
644 DISABLE_COPY_AND_ASSIGN (irange_allocator);
645 struct obstack m_obstack;
648 inline
649 irange_allocator::irange_allocator ()
651 obstack_init (&m_obstack);
654 inline
655 irange_allocator::~irange_allocator ()
657 obstack_free (&m_obstack, NULL);
660 // Provide a hunk of memory from the obstack.
661 inline void *
662 irange_allocator::get_memory (unsigned num_bytes)
664 void *r = obstack_alloc (&m_obstack, num_bytes);
665 return r;
668 // Return a new range with NUM_PAIRS.
670 inline irange *
671 irange_allocator::allocate (unsigned num_pairs)
673 // Never allocate 0 pairs.
674 // Don't allocate 1 either, or we get legacy value_range's.
675 if (num_pairs < 2)
676 num_pairs = 2;
678 size_t nbytes = sizeof (tree) * 2 * num_pairs;
680 // Allocate the irange and required memory for the vector.
681 void *r = obstack_alloc (&m_obstack, sizeof (irange));
682 tree *mem = (tree *) obstack_alloc (&m_obstack, nbytes);
683 return new (r) irange (mem, num_pairs);
686 inline irange *
687 irange_allocator::allocate (const irange &src)
689 irange *r = allocate (src.num_pairs ());
690 *r = src;
691 return r;
694 #endif // GCC_VALUE_RANGE_H