1 /* Support routines for value ranges.
2 Copyright (C) 2019-2022 Free Software Foundation, Inc.
3 Contributed by Aldy Hernandez <aldyh@redhat.com> and
4 Andrew Macleod <amacleod@redhat.com>.
5
6 This file is part of GCC.
7
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.
12
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.
17
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/>. */
21
22 #ifndef GCC_VALUE_RANGE_H
23 #define GCC_VALUE_RANGE_H
24
25 // Types of value ranges.
26 enum value_range_kind
27 {
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
38 };
39
40 // Range of values that can be associated with an SSA_NAME.
41 //
42 // This is the base class without any storage.
43
class(user)44 class GTY((user)) irange
45 {
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 ();
54
55 // Range types.
56 static bool supports_type_p (tree);
57 tree type () const;
58
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;
64
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;
72
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 ();
78
79 // Operator overloads.
80 irange& operator= (const irange &);
81 bool operator== (const irange &) const;
82 bool operator!= (const irange &r) const { return !(*this == r); }
83
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;
88
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
102
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;
109
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);
115
116 void normalize_kind ();
117
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 &);
129
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 *);
134
135 void irange_set_1bit_anti_range (tree, tree);
136 bool varying_compatible_p () const;
137
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;
142 };
143
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.
146
147 template<unsigned N>
class(user)148 class GTY((user)) int_range : public irange
149 {
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 *);
164
165 // ?? These stubs are for ipa-prop.cc 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> *&);
170
171 tree m_ranges[N*2];
172 };
173
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.
180 //
181 // There are copy operators to seamlessly copy to/fro multi-ranges.
182 typedef int_range<1> value_range;
183
184 // This is an "infinite" precision irange for use in temporary
185 // calculations.
186 typedef int_range<255> int_range_max;
187
188 // Returns true for an old-school value_range as described above.
189 inline bool
legacy_mode_p()190 irange::legacy_mode_p () const
191 {
192 return m_max_ranges == 1;
193 }
194
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);
202
203 inline value_range_kind
kind()204 irange::kind () const
205 {
206 return m_kind;
207 }
208
209 // Number of sub-ranges in a range.
210
211 inline unsigned
num_pairs()212 irange::num_pairs () const
213 {
214 if (m_kind == VR_ANTI_RANGE)
215 return constant_p () ? 2 : 1;
216 else
217 return m_num_ranges;
218 }
219
220 inline tree
type()221 irange::type () const
222 {
223 gcc_checking_assert (m_num_ranges > 0);
224 return TREE_TYPE (m_base[0]);
225 }
226
227 // Return the lower bound of a sub-range expressed as a tree. PAIR is
228 // the sub-range in question.
229
230 inline tree
tree_lower_bound(unsigned pair)231 irange::tree_lower_bound (unsigned pair) const
232 {
233 return m_base[pair * 2];
234 }
235
236 // Return the upper bound of a sub-range expressed as a tree. PAIR is
237 // the sub-range in question.
238
239 inline tree
tree_upper_bound(unsigned pair)240 irange::tree_upper_bound (unsigned pair) const
241 {
242 return m_base[pair * 2 + 1];
243 }
244
245 // Return the highest bound of a range expressed as a tree.
246
247 inline tree
tree_upper_bound()248 irange::tree_upper_bound () const
249 {
250 gcc_checking_assert (m_num_ranges);
251 return tree_upper_bound (m_num_ranges - 1);
252 }
253
254 inline tree
min()255 irange::min () const
256 {
257 return tree_lower_bound (0);
258 }
259
260 inline tree
max()261 irange::max () const
262 {
263 if (m_num_ranges)
264 return tree_upper_bound ();
265 else
266 return NULL;
267 }
268
269 inline bool
varying_compatible_p()270 irange::varying_compatible_p () const
271 {
272 if (m_num_ranges != 1)
273 return false;
274
275 tree l = m_base[0];
276 tree u = m_base[1];
277 tree t = TREE_TYPE (l);
278
279 if (m_kind == VR_VARYING && t == error_mark_node)
280 return true;
281
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;
291 }
292
293 inline bool
varying_p()294 irange::varying_p () const
295 {
296 return m_kind == VR_VARYING;
297 }
298
299 inline bool
undefined_p()300 irange::undefined_p () const
301 {
302 return m_kind == VR_UNDEFINED;
303 }
304
305 inline bool
zero_p()306 irange::zero_p () const
307 {
308 return (m_kind == VR_RANGE && m_num_ranges == 1
309 && integer_zerop (tree_lower_bound (0))
310 && integer_zerop (tree_upper_bound (0)));
311 }
312
313 inline bool
nonzero_p()314 irange::nonzero_p () const
315 {
316 if (undefined_p ())
317 return false;
318
319 tree zero = build_zero_cst (type ());
320 return *this == int_range<1> (zero, zero, VR_ANTI_RANGE);
321 }
322
323 inline bool
supports_type_p(tree type)324 irange::supports_type_p (tree type)
325 {
326 if (type && (INTEGRAL_TYPE_P (type) || POINTER_TYPE_P (type)))
327 return type;
328 return false;
329 }
330
331 inline bool
range_includes_zero_p(const irange * vr)332 range_includes_zero_p (const irange *vr)
333 {
334 if (vr->undefined_p ())
335 return false;
336
337 if (vr->varying_p ())
338 return true;
339
340 return vr->may_contain_p (build_zero_cst (vr->type ()));
341 }
342
343 inline void
gt_ggc_mx(irange * x)344 gt_ggc_mx (irange *x)
345 {
346 for (unsigned i = 0; i < x->m_num_ranges; ++i)
347 {
348 gt_ggc_mx (x->m_base[i * 2]);
349 gt_ggc_mx (x->m_base[i * 2 + 1]);
350 }
351 }
352
353 inline void
gt_pch_nx(irange * x)354 gt_pch_nx (irange *x)
355 {
356 for (unsigned i = 0; i < x->m_num_ranges; ++i)
357 {
358 gt_pch_nx (x->m_base[i * 2]);
359 gt_pch_nx (x->m_base[i * 2 + 1]);
360 }
361 }
362
363 inline void
gt_pch_nx(irange * x,gt_pointer_operator op,void * cookie)364 gt_pch_nx (irange *x, gt_pointer_operator op, void *cookie)
365 {
366 for (unsigned i = 0; i < x->m_num_ranges; ++i)
367 {
368 op (&x->m_base[i * 2], NULL, cookie);
369 op (&x->m_base[i * 2 + 1], NULL, cookie);
370 }
371 }
372
373 template<unsigned N>
374 inline void
gt_ggc_mx(int_range<N> * x)375 gt_ggc_mx (int_range<N> *x)
376 {
377 gt_ggc_mx ((irange *) x);
378 }
379
380 template<unsigned N>
381 inline void
gt_pch_nx(int_range<N> * x)382 gt_pch_nx (int_range<N> *x)
383 {
384 gt_pch_nx ((irange *) x);
385 }
386
387 template<unsigned N>
388 inline void
gt_pch_nx(int_range<N> * x,gt_pointer_operator op,void * cookie)389 gt_pch_nx (int_range<N> *x, gt_pointer_operator op, void *cookie)
390 {
391 gt_pch_nx ((irange *) x, op, cookie);
392 }
393
394 // Constructors for irange
395
396 inline
irange(tree * base,unsigned nranges)397 irange::irange (tree *base, unsigned nranges)
398 {
399 m_base = base;
400 m_num_ranges = 0;
401 m_max_ranges = nranges;
402 m_kind = VR_UNDEFINED;
403 }
404
405 // Constructors for int_range<>.
406
407 template<unsigned N>
408 inline
int_range()409 int_range<N>::int_range ()
410 : irange (m_ranges, N)
411 {
412 }
413
414 template<unsigned N>
int_range(const int_range & other)415 int_range<N>::int_range (const int_range &other)
416 : irange (m_ranges, N)
417 {
418 irange::operator= (other);
419 }
420
421 template<unsigned N>
int_range(tree min,tree max,value_range_kind kind)422 int_range<N>::int_range (tree min, tree max, value_range_kind kind)
423 : irange (m_ranges, N)
424 {
425 irange::set (min, max, kind);
426 }
427
428 template<unsigned N>
int_range(tree type)429 int_range<N>::int_range (tree type)
430 : irange (m_ranges, N)
431 {
432 set_varying (type);
433 }
434
435 template<unsigned N>
int_range(tree type,const wide_int & wmin,const wide_int & wmax,value_range_kind kind)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)
439 {
440 tree min = wide_int_to_tree (type, wmin);
441 tree max = wide_int_to_tree (type, wmax);
442 set (min, max, kind);
443 }
444
445 template<unsigned N>
int_range(const irange & other)446 int_range<N>::int_range (const irange &other)
447 : irange (m_ranges, N)
448 {
449 irange::operator= (other);
450 }
451
452 template<unsigned N>
453 int_range<N>&
454 int_range<N>::operator= (const int_range &src)
455 {
456 irange::operator= (src);
457 return *this;
458 }
459
460 inline void
set(tree val)461 irange::set (tree val)
462 {
463 set (val, val);
464 }
465
466 inline void
set_undefined()467 irange::set_undefined ()
468 {
469 m_kind = VR_UNDEFINED;
470 m_num_ranges = 0;
471 }
472
473 inline void
set_varying(tree type)474 irange::set_varying (tree type)
475 {
476 m_kind = VR_VARYING;
477 m_num_ranges = 1;
478
479 if (INTEGRAL_TYPE_P (type))
480 {
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))))
487 {
488 m_base[0] = TYPE_MIN_VALUE (type);
489 m_base[1] = TYPE_MAX_VALUE (type);
490 }
491 else
492 {
493 m_base[0] = wide_int_to_tree (type, min);
494 m_base[1] = wide_int_to_tree (type, max);
495 }
496 }
497 else if (POINTER_TYPE_P (type))
498 {
499 m_base[0] = build_int_cst (type, 0);
500 m_base[1] = build_int_cst (type, -1);
501 }
502 else
503 m_base[0] = m_base[1] = error_mark_node;
504 }
505
506 inline bool
507 irange::operator== (const irange &r) const
508 {
509 return equal_p (r);
510 }
511
512 // Return the lower bound of a sub-range. PAIR is the sub-range in
513 // question.
514
515 inline wide_int
lower_bound(unsigned pair)516 irange::lower_bound (unsigned pair) const
517 {
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));
523 }
524
525 // Return the upper bound of a sub-range. PAIR is the sub-range in
526 // question.
527
528 inline wide_int
upper_bound(unsigned pair)529 irange::upper_bound (unsigned pair) const
530 {
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));
536 }
537
538 // Return the highest bound of a range.
539
540 inline wide_int
upper_bound()541 irange::upper_bound () const
542 {
543 unsigned pairs = num_pairs ();
544 gcc_checking_assert (pairs > 0);
545 return upper_bound (pairs - 1);
546 }
547
548 inline void
union_(const irange & r)549 irange::union_ (const irange &r)
550 {
551 dump_flags_t m_flags = dump_flags;
552 dump_flags &= ~TDF_DETAILS;
553 irange::union_ (&r);
554 dump_flags = m_flags;
555 }
556
557 inline void
intersect(const irange & r)558 irange::intersect (const irange &r)
559 {
560 dump_flags_t m_flags = dump_flags;
561 dump_flags &= ~TDF_DETAILS;
562 irange::intersect (&r);
563 dump_flags = m_flags;
564 }
565
566 // Set value range VR to a nonzero range of type TYPE.
567
568 inline void
set_nonzero(tree type)569 irange::set_nonzero (tree type)
570 {
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);
576 }
577
578 // Set value range VR to a ZERO range of type TYPE.
579
580 inline void
set_zero(tree type)581 irange::set_zero (tree type)
582 {
583 tree z = build_int_cst (type, 0);
584 if (legacy_mode_p ())
585 set (z);
586 else
587 irange_set (z, z);
588 }
589
590 // Normalize a range to VARYING or UNDEFINED if possible.
591
592 inline void
normalize_kind()593 irange::normalize_kind ()
594 {
595 if (m_num_ranges == 0)
596 m_kind = VR_UNDEFINED;
597 else if (varying_compatible_p ())
598 {
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 ();
605 }
606 }
607
608 inline bool
contains_zero_p(const irange & r)609 contains_zero_p (const irange &r)
610 {
611 if (r.undefined_p ())
612 return false;
613
614 tree zero = build_zero_cst (r.type ());
615 return r.contains_p (zero);
616 }
617
618 // Return the maximum value for TYPE.
619
620 inline tree
vrp_val_max(const_tree type)621 vrp_val_max (const_tree type)
622 {
623 if (INTEGRAL_TYPE_P (type))
624 return TYPE_MAX_VALUE (type);
625 if (POINTER_TYPE_P (type))
626 {
627 wide_int max = wi::max_value (TYPE_PRECISION (type), TYPE_SIGN (type));
628 return wide_int_to_tree (const_cast<tree> (type), max);
629 }
630 return NULL_TREE;
631 }
632
633 // Return the minimum value for TYPE.
634
635 inline tree
vrp_val_min(const_tree type)636 vrp_val_min (const_tree type)
637 {
638 if (INTEGRAL_TYPE_P (type))
639 return TYPE_MIN_VALUE (type);
640 if (POINTER_TYPE_P (type))
641 return build_zero_cst (const_cast<tree> (type));
642 return NULL_TREE;
643 }
644
645 // This is the irange storage class. It is used to allocate the
646 // minimum amount of storage needed for a given irange. Storage is
647 // automatically freed at destruction of the storage class.
648 //
649 // It is meant for long term storage, as opposed to int_range_max
650 // which is meant for intermediate temporary results on the stack.
651 //
652 // The newly allocated irange is initialized to the empty set
653 // (undefined_p() is true).
654
655 class irange_allocator
656 {
657 public:
658 irange_allocator ();
659 ~irange_allocator ();
660 // Return a new range with NUM_PAIRS.
661 irange *allocate (unsigned num_pairs);
662 // Return a copy of SRC with the minimum amount of sub-ranges needed
663 // to represent it.
664 irange *allocate (const irange &src);
665 void *get_memory (unsigned num_bytes);
666 private:
667 DISABLE_COPY_AND_ASSIGN (irange_allocator);
668 struct obstack m_obstack;
669 };
670
671 inline
irange_allocator()672 irange_allocator::irange_allocator ()
673 {
674 obstack_init (&m_obstack);
675 }
676
677 inline
~irange_allocator()678 irange_allocator::~irange_allocator ()
679 {
680 obstack_free (&m_obstack, NULL);
681 }
682
683 // Provide a hunk of memory from the obstack.
684 inline void *
get_memory(unsigned num_bytes)685 irange_allocator::get_memory (unsigned num_bytes)
686 {
687 void *r = obstack_alloc (&m_obstack, num_bytes);
688 return r;
689 }
690
691 // Return a new range with NUM_PAIRS.
692
693 inline irange *
allocate(unsigned num_pairs)694 irange_allocator::allocate (unsigned num_pairs)
695 {
696 // Never allocate 0 pairs.
697 // Don't allocate 1 either, or we get legacy value_range's.
698 if (num_pairs < 2)
699 num_pairs = 2;
700
701 size_t nbytes = sizeof (tree) * 2 * num_pairs;
702
703 // Allocate the irange and required memory for the vector.
704 void *r = obstack_alloc (&m_obstack, sizeof (irange));
705 tree *mem = (tree *) obstack_alloc (&m_obstack, nbytes);
706 return new (r) irange (mem, num_pairs);
707 }
708
709 inline irange *
allocate(const irange & src)710 irange_allocator::allocate (const irange &src)
711 {
712 irange *r = allocate (src.num_pairs ());
713 *r = src;
714 return r;
715 }
716
717 #endif // GCC_VALUE_RANGE_H
718