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>.
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
44 class 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 invert ();
77
78 // Operator overloads.
79 irange& operator= (const irange &);
80 bool operator== (const irange &) const;
81 bool operator!= (const irange &r) const { return !(*this == r); }
82
83 // Misc methods.
fits_p(const irange & r)84 bool fits_p (const irange &r) { return m_max_ranges >= r.num_pairs (); }
85 void dump (FILE * = stderr) const;
86
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
100
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;
107
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);
113
114 void normalize_min_max ();
115
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 unsigned legacy_num_pairs () const;
122 wide_int legacy_lower_bound (unsigned = 0) const;
123 wide_int legacy_upper_bound (unsigned) const;
124 int value_inside_range (tree) const;
125 bool maybe_anti_range () const;
126 void copy_to_legacy (const irange &);
127 void copy_legacy_to_multi_range (const irange &);
128
129 private:
130 void irange_set_1bit_anti_range (tree, tree);
131
132 unsigned char m_num_ranges;
133 unsigned char m_max_ranges;
134 ENUM_BITFIELD(value_range_kind) m_kind : 8;
135 tree *m_base;
136 };
137
138 // Here we describe an irange with N pairs of ranges. The storage for
139 // the pairs is embedded in the class as an array.
140
141 template<unsigned N>
class(user)142 class GTY((user)) int_range : public irange
143 {
144 public:
145 int_range ();
146 int_range (tree, tree, value_range_kind = VR_RANGE);
147 int_range (tree type, const wide_int &, const wide_int &,
148 value_range_kind = VR_RANGE);
149 int_range (tree type);
150 int_range (const int_range &);
151 int_range (const irange &);
152 int_range& operator= (const int_range &);
153 private:
154 template <unsigned X> friend void gt_ggc_mx (int_range<X> *);
155 template <unsigned X> friend void gt_pch_nx (int_range<X> *);
156 template <unsigned X> friend void gt_pch_nx (int_range<X> *,
157 gt_pointer_operator, void *);
158 // ?? hash-traits.h has its own extern for these, which is causing
159 // them to never be picked up by the templates. For now, define
160 // elsewhere.
161 //template<unsigned X> friend void gt_ggc_mx (int_range<X> *&);
162 //template<unsigned X> friend void gt_pch_nx (int_range<X> *&);
163 friend void gt_ggc_mx (int_range<1> *&);
164 friend void gt_pch_nx (int_range<1> *&);
165
166 tree m_ranges[N*2];
167 };
168
169 // This is a special int_range<1> with only one pair, plus
170 // VR_ANTI_RANGE magic to describe slightly more than can be described
171 // in one pair. It is described in the code as a "legacy range" (as
172 // opposed to multi-ranges which have multiple sub-ranges). It is
173 // provided for backward compatibility with code that has not been
174 // converted to multi-range irange's.
175 //
176 // There are copy operators to seamlessly copy to/fro multi-ranges.
177 typedef int_range<1> value_range;
178
179 // This is an "infinite" precision irange for use in temporary
180 // calculations.
181 typedef int_range<255> int_range_max;
182
183 // Returns true for an old-school value_range as described above.
184 inline bool
legacy_mode_p()185 irange::legacy_mode_p () const
186 {
187 return m_max_ranges == 1;
188 }
189
190 extern bool range_has_numeric_bounds_p (const irange *);
191 extern bool ranges_from_anti_range (const value_range *,
192 value_range *, value_range *);
193 extern void dump_value_range (FILE *, const irange *);
194 extern bool vrp_val_is_min (const_tree);
195 extern bool vrp_val_is_max (const_tree);
196 extern bool vrp_operand_equal_p (const_tree, const_tree);
197
198 inline value_range_kind
kind()199 irange::kind () const
200 {
201 if (legacy_mode_p ())
202 return m_kind;
203
204 if (undefined_p ())
205 return VR_UNDEFINED;
206
207 if (varying_p ())
208 return VR_VARYING;
209
210 return VR_RANGE;
211 }
212
213 // Number of sub-ranges in a range.
214
215 inline unsigned
num_pairs()216 irange::num_pairs () const
217 {
218 if (!legacy_mode_p ())
219 return m_num_ranges;
220 else
221 return legacy_num_pairs ();
222 }
223
224 inline tree
type()225 irange::type () const
226 {
227 gcc_checking_assert (!undefined_p ());
228 return TREE_TYPE (m_base[0]);
229 }
230
231 // Return the lower bound of a sub-range expressed as a tree. PAIR is
232 // the sub-range in question.
233
234 inline tree
tree_lower_bound(unsigned pair)235 irange::tree_lower_bound (unsigned pair) const
236 {
237 return m_base[pair * 2];
238 }
239
240 // Return the upper bound of a sub-range expressed as a tree. PAIR is
241 // the sub-range in question.
242
243 inline tree
tree_upper_bound(unsigned pair)244 irange::tree_upper_bound (unsigned pair) const
245 {
246 return m_base[pair * 2 + 1];
247 }
248
249 // Return the highest bound of a range expressed as a tree.
250
251 inline tree
tree_upper_bound()252 irange::tree_upper_bound () const
253 {
254 gcc_checking_assert (m_num_ranges);
255 return tree_upper_bound (m_num_ranges - 1);
256 }
257
258 inline tree
min()259 irange::min () const
260 {
261 return tree_lower_bound (0);
262 }
263
264 inline tree
max()265 irange::max () const
266 {
267 if (m_num_ranges)
268 return tree_upper_bound ();
269 else
270 return NULL;
271 }
272
273 inline bool
varying_p()274 irange::varying_p () const
275 {
276 if (legacy_mode_p ())
277 return m_kind == VR_VARYING;
278
279 if (m_num_ranges != 1)
280 return false;
281
282 tree l = m_base[0];
283 tree u = m_base[1];
284 tree t = TREE_TYPE (l);
285 unsigned prec = TYPE_PRECISION (t);
286 signop sign = TYPE_SIGN (t);
287 if (INTEGRAL_TYPE_P (t))
288 return (wi::to_wide (l) == wi::min_value (prec, sign)
289 && wi::to_wide (u) == wi::max_value (prec, sign));
290 if (POINTER_TYPE_P (t))
291 return (wi::to_wide (l) == 0
292 && wi::to_wide (u) == wi::max_value (prec, sign));
293 return true;
294
295 }
296
297 inline bool
undefined_p()298 irange::undefined_p () const
299 {
300 if (!legacy_mode_p ())
301 return m_num_ranges == 0;
302
303 if (CHECKING_P && legacy_mode_p ())
304 {
305 if (m_kind == VR_UNDEFINED)
306 gcc_checking_assert (m_num_ranges == 0);
307 else
308 gcc_checking_assert (m_num_ranges != 0);
309 }
310 return m_kind == VR_UNDEFINED;
311 }
312
313 inline bool
zero_p()314 irange::zero_p () const
315 {
316 return (m_kind == VR_RANGE && m_num_ranges == 1
317 && integer_zerop (tree_lower_bound (0))
318 && integer_zerop (tree_upper_bound (0)));
319 }
320
321 inline bool
nonzero_p()322 irange::nonzero_p () const
323 {
324 if (undefined_p ())
325 return false;
326
327 tree zero = build_zero_cst (type ());
328 return *this == int_range<1> (zero, zero, VR_ANTI_RANGE);
329 }
330
331 inline bool
supports_type_p(tree type)332 irange::supports_type_p (tree type)
333 {
334 if (type && (INTEGRAL_TYPE_P (type) || POINTER_TYPE_P (type)))
335 return type;
336 return false;
337 }
338
339 inline bool
range_includes_zero_p(const irange * vr)340 range_includes_zero_p (const irange *vr)
341 {
342 if (vr->undefined_p ())
343 return false;
344
345 if (vr->varying_p ())
346 return true;
347
348 return vr->may_contain_p (build_zero_cst (vr->type ()));
349 }
350
351 template<unsigned N>
352 inline void
gt_ggc_mx(int_range<N> * x)353 gt_ggc_mx (int_range<N> *x)
354 {
355 for (unsigned i = 0; i < N; ++i)
356 {
357 gt_ggc_mx (x->m_ranges[i * 2]);
358 gt_ggc_mx (x->m_ranges[i * 2 + 1]);
359 }
360 }
361
362 template<unsigned N>
363 inline void
gt_pch_nx(int_range<N> * x)364 gt_pch_nx (int_range<N> *x)
365 {
366 for (unsigned i = 0; i < N; ++i)
367 {
368 gt_pch_nx (x->m_ranges[i * 2]);
369 gt_pch_nx (x->m_ranges[i * 2 + 1]);
370 }
371 }
372
373 template<unsigned N>
374 inline void
gt_pch_nx(int_range<N> * x,gt_pointer_operator op,void * cookie)375 gt_pch_nx (int_range<N> *x, gt_pointer_operator op, void *cookie)
376 {
377 for (unsigned i = 0; i < N; ++i)
378 {
379 op (&x->m_ranges[i * 2], cookie);
380 op (&x->m_ranges[i * 2 + 1], cookie);
381 }
382 }
383
384 // Constructors for irange
385
386 inline
irange(tree * base,unsigned nranges)387 irange::irange (tree *base, unsigned nranges)
388 {
389 m_base = base;
390 m_num_ranges = 0;
391 m_max_ranges = nranges;
392 if (legacy_mode_p ())
393 m_kind = VR_UNDEFINED;
394 else
395 m_kind = VR_RANGE;
396 }
397
398 // Constructors for int_range<>.
399
400 template<unsigned N>
401 inline
int_range()402 int_range<N>::int_range ()
403 : irange (m_ranges, N)
404 {
405 }
406
407 template<unsigned N>
int_range(const int_range & other)408 int_range<N>::int_range (const int_range &other)
409 : irange (m_ranges, N)
410 {
411 irange::operator= (other);
412 }
413
414 template<unsigned N>
int_range(tree min,tree max,value_range_kind kind)415 int_range<N>::int_range (tree min, tree max, value_range_kind kind)
416 : irange (m_ranges, N)
417 {
418 irange::set (min, max, kind);
419 }
420
421 template<unsigned N>
int_range(tree type)422 int_range<N>::int_range (tree type)
423 : irange (m_ranges, N)
424 {
425 set_varying (type);
426 }
427
428 template<unsigned N>
int_range(tree type,const wide_int & wmin,const wide_int & wmax,value_range_kind kind)429 int_range<N>::int_range (tree type, const wide_int &wmin, const wide_int &wmax,
430 value_range_kind kind)
431 : irange (m_ranges, N)
432 {
433 tree min = wide_int_to_tree (type, wmin);
434 tree max = wide_int_to_tree (type, wmax);
435 set (min, max, kind);
436 }
437
438 template<unsigned N>
int_range(const irange & other)439 int_range<N>::int_range (const irange &other)
440 : irange (m_ranges, N)
441 {
442 irange::operator= (other);
443 }
444
445 template<unsigned N>
446 int_range<N>&
447 int_range<N>::operator= (const int_range &src)
448 {
449 irange::operator= (src);
450 return *this;
451 }
452
453 inline void
set(tree val)454 irange::set (tree val)
455 {
456 set (val, val);
457 }
458
459 inline void
set_undefined()460 irange::set_undefined ()
461 {
462 m_num_ranges = 0;
463 if (legacy_mode_p ())
464 m_kind = VR_UNDEFINED;
465 }
466
467 inline void
set_varying(tree type)468 irange::set_varying (tree type)
469 {
470 if (legacy_mode_p ())
471 m_kind = VR_VARYING;
472
473 m_num_ranges = 1;
474 if (INTEGRAL_TYPE_P (type))
475 {
476 wide_int min = wi::min_value (TYPE_PRECISION (type), TYPE_SIGN (type));
477 wide_int max = wi::max_value (TYPE_PRECISION (type), TYPE_SIGN (type));
478 m_base[0] = wide_int_to_tree (type, min);
479 m_base[1] = wide_int_to_tree (type, max);
480 }
481 else if (POINTER_TYPE_P (type))
482 {
483 m_base[0] = build_int_cst (type, 0);
484 m_base[1] = build_int_cst (type, -1);
485 }
486 else
487 m_base[0] = m_base[1] = error_mark_node;
488 }
489
490 inline bool
491 irange::operator== (const irange &r) const
492 {
493 return equal_p (r);
494 }
495
496 // Return the lower bound of a sub-range. PAIR is the sub-range in
497 // question.
498
499 inline wide_int
lower_bound(unsigned pair)500 irange::lower_bound (unsigned pair) const
501 {
502 if (legacy_mode_p ())
503 return legacy_lower_bound (pair);
504 gcc_checking_assert (!undefined_p ());
505 gcc_checking_assert (pair + 1 <= num_pairs ());
506 return wi::to_wide (tree_lower_bound (pair));
507 }
508
509 // Return the upper bound of a sub-range. PAIR is the sub-range in
510 // question.
511
512 inline wide_int
upper_bound(unsigned pair)513 irange::upper_bound (unsigned pair) const
514 {
515 if (legacy_mode_p ())
516 return legacy_upper_bound (pair);
517 gcc_checking_assert (!undefined_p ());
518 gcc_checking_assert (pair + 1 <= num_pairs ());
519 return wi::to_wide (tree_upper_bound (pair));
520 }
521
522 // Return the highest bound of a range.
523
524 inline wide_int
upper_bound()525 irange::upper_bound () const
526 {
527 unsigned pairs = num_pairs ();
528 gcc_checking_assert (pairs > 0);
529 return upper_bound (pairs - 1);
530 }
531
532 inline void
union_(const irange & r)533 irange::union_ (const irange &r)
534 {
535 dump_flags_t m_flags = dump_flags;
536 dump_flags &= ~TDF_DETAILS;
537 irange::union_ (&r);
538 dump_flags = m_flags;
539 }
540
541 inline void
intersect(const irange & r)542 irange::intersect (const irange &r)
543 {
544 dump_flags_t m_flags = dump_flags;
545 dump_flags &= ~TDF_DETAILS;
546 irange::intersect (&r);
547 dump_flags = m_flags;
548 }
549
550 // Set value range VR to a nonzero range of type TYPE.
551
552 inline void
set_nonzero(tree type)553 irange::set_nonzero (tree type)
554 {
555 tree zero = build_int_cst (type, 0);
556 if (legacy_mode_p ())
557 set (zero, zero, VR_ANTI_RANGE);
558 else
559 irange_set_anti_range (zero, zero);
560 }
561
562 // Set value range VR to a ZERO range of type TYPE.
563
564 inline void
set_zero(tree type)565 irange::set_zero (tree type)
566 {
567 tree z = build_int_cst (type, 0);
568 if (legacy_mode_p ())
569 set (z);
570 else
571 irange_set (z, z);
572 }
573
574 // Normalize a range to VARYING or UNDEFINED if possible.
575
576 inline void
normalize_min_max()577 irange::normalize_min_max ()
578 {
579 gcc_checking_assert (legacy_mode_p ());
580 gcc_checking_assert (!undefined_p ());
581 unsigned prec = TYPE_PRECISION (type ());
582 signop sign = TYPE_SIGN (type ());
583 if (wi::eq_p (wi::to_wide (min ()), wi::min_value (prec, sign))
584 && wi::eq_p (wi::to_wide (max ()), wi::max_value (prec, sign)))
585 {
586 if (m_kind == VR_RANGE)
587 set_varying (type ());
588 else if (m_kind == VR_ANTI_RANGE)
589 set_undefined ();
590 else
591 gcc_unreachable ();
592 }
593 }
594
595 // Return the maximum value for TYPE.
596
597 inline tree
vrp_val_max(const_tree type)598 vrp_val_max (const_tree type)
599 {
600 if (INTEGRAL_TYPE_P (type))
601 return TYPE_MAX_VALUE (type);
602 if (POINTER_TYPE_P (type))
603 {
604 wide_int max = wi::max_value (TYPE_PRECISION (type), TYPE_SIGN (type));
605 return wide_int_to_tree (const_cast<tree> (type), max);
606 }
607 return NULL_TREE;
608 }
609
610 // Return the minimum value for TYPE.
611
612 inline tree
vrp_val_min(const_tree type)613 vrp_val_min (const_tree type)
614 {
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;
620 }
621
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.
625 //
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.
628 //
629 // The newly allocated irange is initialized to the empty set
630 // (undefined_p() is true).
631
632 class irange_allocator
633 {
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;
646 };
647
648 inline
irange_allocator()649 irange_allocator::irange_allocator ()
650 {
651 obstack_init (&m_obstack);
652 }
653
654 inline
~irange_allocator()655 irange_allocator::~irange_allocator ()
656 {
657 obstack_free (&m_obstack, NULL);
658 }
659
660 // Provide a hunk of memory from the obstack
661 inline void *
get_memory(unsigned num_bytes)662 irange_allocator::get_memory (unsigned num_bytes)
663 {
664 void *r = obstack_alloc (&m_obstack, num_bytes);
665 return r;
666 }
667
668 // Return a new range with NUM_PAIRS.
669
670 inline irange *
allocate(unsigned num_pairs)671 irange_allocator::allocate (unsigned num_pairs)
672 {
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;
677
678 size_t nbytes = sizeof (tree) * 2 * num_pairs;
679
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);
684 }
685
686 inline irange *
allocate(const irange & src)687 irange_allocator::allocate (const irange &src)
688 {
689 irange *r = allocate (src.num_pairs ());
690 *r = src;
691 return r;
692 }
693
694 #endif // GCC_VALUE_RANGE_H
695