1 /* Support routines for value ranges.
2 Copyright (C) 2019-2024 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
27 // Types of value ranges.
32 /* Range spans the entire domain. */
34 /* Range is [MIN, MAX]. */
36 /* Range is ~[MIN, MAX]. */
40 /* Range is a nice guy. */
44 // Discriminator between different vrange types.
46 enum value_range_discriminator
48 // Range holds an integer or pointer.
52 // Floating point range.
54 // Range holds an unsupported type.
58 // Abstract class for ranges of any of the supported types.
60 // To query what types ranger and the entire ecosystem can support,
61 // use Value_Range::supports_type_p(tree type). This is a static
62 // method available independently of any vrange object.
64 // To query what a given vrange variant can support, use:
65 // irange::supports_p ()
66 // frange::supports_p ()
69 // To query what a range object can support, use:
70 // void foo (vrange &v, irange &i, frange &f)
72 // if (v.supports_type_p (type)) ...
73 // if (i.supports_type_p (type)) ...
74 // if (f.supports_type_p (type)) ...
79 template <typename T
> friend bool is_a (vrange
&);
80 friend class Value_Range
;
81 friend void streamer_write_vrange (struct output_block
*, const vrange
&);
82 friend class range_op_handler
;
84 virtual void accept (const class vrange_visitor
&v
) const = 0;
85 virtual void set (tree
, tree
, value_range_kind
= VR_RANGE
) = 0;
86 virtual tree
type () const = 0;
87 virtual bool supports_type_p (const_tree type
) const = 0;
88 virtual void set_varying (tree type
) = 0;
89 virtual void set_undefined () = 0;
90 virtual bool union_ (const vrange
&) = 0;
91 virtual bool intersect (const vrange
&) = 0;
92 virtual bool singleton_p (tree
*result
= NULL
) const = 0;
93 virtual bool contains_p (tree cst
) const = 0;
94 virtual bool zero_p () const = 0;
95 virtual bool nonzero_p () const = 0;
96 virtual void set_nonzero (tree type
) = 0;
97 virtual void set_zero (tree type
) = 0;
98 virtual void set_nonnegative (tree type
) = 0;
99 virtual bool fits_p (const vrange
&r
) const = 0;
100 virtual ~vrange () { }
101 virtual tree
lbound () const = 0;
102 virtual tree
ubound () const = 0;
103 virtual void update_bitmask (const class irange_bitmask
&);
104 virtual irange_bitmask
get_bitmask () const;
105 wide_int
get_nonzero_bits () const;
106 void set_nonzero_bits (const wide_int
&bits
);
108 bool varying_p () const;
109 bool undefined_p () const;
110 vrange
& operator= (const vrange
&);
111 bool operator== (const vrange
&) const;
112 bool operator!= (const vrange
&r
) const { return !(*this == r
); }
113 void dump (FILE *) const;
115 vrange (enum value_range_discriminator d
) : m_discriminator (d
) { }
116 ENUM_BITFIELD(value_range_kind
) m_kind
: 8;
117 const ENUM_BITFIELD(value_range_discriminator
) m_discriminator
: 4;
122 extern void add_vrange (const vrange
&, hash
&, unsigned flags
= 0);
125 // A pair of values representing the known bits in a range. Zero bits
126 // in MASK cover constant values. Set bits in MASK cover unknown
127 // values. VALUE are the known bits.
129 // Set bits in MASK (no meaningful information) must have their
130 // corresponding bits in VALUE cleared, as this speeds up union and
136 irange_bitmask () { /* uninitialized */ }
137 irange_bitmask (unsigned prec
) { set_unknown (prec
); }
138 irange_bitmask (const wide_int
&value
, const wide_int
&mask
);
139 wide_int
value () const { return m_value
; }
140 wide_int
mask () const { return m_mask
; }
141 void set_unknown (unsigned prec
);
142 bool unknown_p () const;
143 unsigned get_precision () const;
144 void union_ (const irange_bitmask
&src
);
145 void intersect (const irange_bitmask
&src
);
146 bool operator== (const irange_bitmask
&src
) const;
147 bool operator!= (const irange_bitmask
&src
) const { return !(*this == src
); }
148 void verify_mask () const;
149 void dump (FILE *) const;
151 bool member_p (const wide_int
&val
) const;
152 void adjust_range (irange
&r
) const;
154 // Convenience functions for nonzero bitmask compatibility.
155 wide_int
get_nonzero_bits () const;
156 void set_nonzero_bits (const wide_int
&bits
);
163 irange_bitmask::set_unknown (unsigned prec
)
165 m_value
= wi::zero (prec
);
166 m_mask
= wi::minus_one (prec
);
171 // Return TRUE if THIS does not have any meaningful information.
174 irange_bitmask::unknown_p () const
180 irange_bitmask::irange_bitmask (const wide_int
&value
, const wide_int
&mask
)
189 irange_bitmask::get_precision () const
191 return m_mask
.get_precision ();
194 // The following two functions are meant for backwards compatability
195 // with the nonzero bitmask. A cleared bit means the value must be 0.
196 // A set bit means we have no information for the bit.
198 // Return the nonzero bits.
200 irange_bitmask::get_nonzero_bits () const
202 return m_value
| m_mask
;
205 // Set the bitmask to the nonzero bits in BITS.
207 irange_bitmask::set_nonzero_bits (const wide_int
&bits
)
209 m_value
= wi::zero (bits
.get_precision ());
215 // Return TRUE if val could be a valid value with this bitmask.
218 irange_bitmask::member_p (const wide_int
&val
) const
222 wide_int res
= m_mask
& val
;
224 res
|= ~m_mask
& m_value
;
229 irange_bitmask::operator== (const irange_bitmask
&src
) const
231 bool unknown1
= unknown_p ();
232 bool unknown2
= src
.unknown_p ();
233 if (unknown1
|| unknown2
)
234 return unknown1
== unknown2
;
235 return m_value
== src
.m_value
&& m_mask
== src
.m_mask
;
239 irange_bitmask::union_ (const irange_bitmask
&src
)
241 m_mask
= (m_mask
| src
.m_mask
) | (m_value
^ src
.m_value
);
242 m_value
= m_value
& src
.m_value
;
248 irange_bitmask::intersect (const irange_bitmask
&src
)
250 // If we have two known bits that are incompatible, the resulting
251 // bit is undefined. It is unclear whether we should set the entire
252 // range to UNDEFINED, or just a subset of it. For now, set the
253 // entire bitmask to unknown (VARYING).
254 if (wi::bit_and (~(m_mask
| src
.m_mask
),
255 m_value
^ src
.m_value
) != 0)
257 unsigned prec
= m_mask
.get_precision ();
258 m_mask
= wi::minus_one (prec
);
259 m_value
= wi::zero (prec
);
263 m_mask
= m_mask
& src
.m_mask
;
264 m_value
= m_value
| src
.m_value
;
270 // An integer range without any storage.
272 class irange
: public vrange
274 friend class irange_storage
;
275 friend class vrange_printer
;
278 void set (tree type
, const wide_int
&, const wide_int
&,
279 value_range_kind
= VR_RANGE
);
280 virtual void set_nonzero (tree type
) override
;
281 virtual void set_zero (tree type
) override
;
282 virtual void set_nonnegative (tree type
) override
;
283 virtual void set_varying (tree type
) override
;
284 virtual void set_undefined () override
;
287 static bool supports_p (const_tree type
);
288 virtual bool supports_type_p (const_tree type
) const override
;
289 virtual tree
type () const override
;
291 // Iteration over sub-ranges.
292 unsigned num_pairs () const;
293 wide_int
lower_bound (unsigned = 0) const;
294 wide_int
upper_bound (unsigned) const;
295 wide_int
upper_bound () const;
296 virtual tree
lbound () const override
;
297 virtual tree
ubound () const override
;
300 virtual bool zero_p () const override
;
301 virtual bool nonzero_p () const override
;
302 virtual bool singleton_p (tree
*result
= NULL
) const override
;
303 bool singleton_p (wide_int
&) const;
304 bool contains_p (const wide_int
&) const;
305 bool nonnegative_p () const;
306 bool nonpositive_p () const;
308 // In-place operators.
309 virtual bool union_ (const vrange
&) override
;
310 virtual bool intersect (const vrange
&) override
;
313 // Operator overloads.
314 irange
& operator= (const irange
&);
315 bool operator== (const irange
&) const;
316 bool operator!= (const irange
&r
) const { return !(*this == r
); }
319 virtual bool fits_p (const vrange
&r
) const override
;
320 virtual void accept (const vrange_visitor
&v
) const override
;
322 virtual void update_bitmask (const class irange_bitmask
&) override
;
323 virtual irange_bitmask
get_bitmask () const override
;
326 void maybe_resize (int needed
);
327 virtual void set (tree
, tree
, value_range_kind
= VR_RANGE
) override
;
328 virtual bool contains_p (tree cst
) const override
;
329 irange (wide_int
*, unsigned nranges
, bool resizable
);
331 // In-place operators.
332 bool irange_contains_p (const irange
&) const;
333 bool irange_single_pair_union (const irange
&r
);
335 void normalize_kind ();
337 void verify_range ();
339 // Hard limit on max ranges allowed.
340 static const int HARD_MAX_RANGES
= 255;
342 bool varying_compatible_p () const;
343 bool intersect_bitmask (const irange
&r
);
344 bool union_bitmask (const irange
&r
);
345 bool set_range_from_bitmask ();
347 bool intersect (const wide_int
& lb
, const wide_int
& ub
);
348 bool union_append (const irange
&r
);
349 unsigned char m_num_ranges
;
351 unsigned char m_max_ranges
;
353 irange_bitmask m_bitmask
;
358 // Here we describe an irange with N pairs of ranges. The storage for
359 // the pairs is embedded in the class as an array.
361 // If RESIZABLE is true, the storage will be resized on the heap when
362 // the number of ranges needed goes past N up to a max of
363 // HARD_MAX_RANGES. This new storage is freed upon destruction.
365 template<unsigned N
, bool RESIZABLE
= false>
366 class int_range
: public irange
370 int_range (tree type
, const wide_int
&, const wide_int
&,
371 value_range_kind
= VR_RANGE
);
372 int_range (tree type
);
373 int_range (const int_range
&);
374 int_range (const irange
&);
375 ~int_range () final override
;
376 int_range
& operator= (const int_range
&);
378 int_range (tree
, tree
, value_range_kind
= VR_RANGE
);
380 wide_int m_ranges
[N
*2];
383 class prange
: public vrange
385 friend class prange_storage
;
386 friend class vrange_printer
;
389 prange (const prange
&);
391 prange (tree type
, const wide_int
&, const wide_int
&,
392 value_range_kind
= VR_RANGE
);
393 static bool supports_p (const_tree type
);
394 virtual bool supports_type_p (const_tree type
) const final override
;
395 virtual void accept (const vrange_visitor
&v
) const final override
;
396 virtual void set_undefined () final override
;
397 virtual void set_varying (tree type
) final override
;
398 virtual void set_nonzero (tree type
) final override
;
399 virtual void set_zero (tree type
) final override
;
400 virtual void set_nonnegative (tree type
) final override
;
401 virtual bool contains_p (tree cst
) const final override
;
402 virtual bool fits_p (const vrange
&v
) const final override
;
403 virtual bool singleton_p (tree
*result
= NULL
) const final override
;
404 virtual bool zero_p () const final override
;
405 virtual bool nonzero_p () const final override
;
406 virtual void set (tree
, tree
, value_range_kind
= VR_RANGE
) final override
;
407 virtual tree
type () const final override
;
408 virtual bool union_ (const vrange
&v
) final override
;
409 virtual bool intersect (const vrange
&v
) final override
;
410 virtual tree
lbound () const final override
;
411 virtual tree
ubound () const final override
;
413 prange
& operator= (const prange
&);
414 bool operator== (const prange
&) const;
415 void set (tree type
, const wide_int
&, const wide_int
&,
416 value_range_kind
= VR_RANGE
);
418 bool contains_p (const wide_int
&) const;
419 wide_int
lower_bound () const;
420 wide_int
upper_bound () const;
421 void verify_range () const;
422 irange_bitmask
get_bitmask () const final override
;
423 void update_bitmask (const irange_bitmask
&) final override
;
425 bool varying_compatible_p () const;
430 irange_bitmask m_bitmask
;
433 // Unsupported temporaries may be created by ranger before it's known
434 // they're unsupported, or by vr_values::get_value_range.
436 class unsupported_range
: public vrange
440 : vrange (VR_UNKNOWN
)
444 unsupported_range (const unsupported_range
&src
)
445 : vrange (VR_UNKNOWN
)
447 unsupported_range::operator= (src
);
449 void set (tree min
, tree
, value_range_kind
= VR_RANGE
) final override
;
450 tree
type () const final override
;
451 bool supports_type_p (const_tree
) const final override
;
452 void set_varying (tree
) final override
;
453 void set_undefined () final override
;
454 void accept (const vrange_visitor
&v
) const final override
;
455 bool union_ (const vrange
&r
) final override
;
456 bool intersect (const vrange
&r
) final override
;
457 bool singleton_p (tree
* = NULL
) const final override
;
458 bool contains_p (tree
) const final override
;
459 bool zero_p () const final override
;
460 bool nonzero_p () const final override
;
461 void set_nonzero (tree type
) final override
;
462 void set_zero (tree type
) final override
;
463 void set_nonnegative (tree type
) final override
;
464 bool fits_p (const vrange
&) const final override
;
465 unsupported_range
& operator= (const unsupported_range
&r
);
466 tree
lbound () const final override
;
467 tree
ubound () const final override
;
470 // The NAN state as an opaque object.
476 nan_state (bool pos_nan
, bool neg_nan
);
484 // Set NAN state to +-NAN if NAN_P is true. Otherwise set NAN state
488 nan_state::nan_state (bool nan_p
)
494 // Constructor initializing the object to +NAN if POS_NAN is set, -NAN
495 // if NEG_NAN is set, or +-NAN if both are set. Otherwise POS_NAN and
496 // NEG_NAN are clear, and the object cannot be a NAN.
499 nan_state::nan_state (bool pos_nan
, bool neg_nan
)
505 // Return if +NAN is possible.
508 nan_state::pos_p () const
513 // Return if -NAN is possible.
516 nan_state::neg_p () const
521 // A floating point range.
523 // The representation is a type with a couple of endpoints, unioned
524 // with the set of { -NAN, +Nan }.
526 class frange
: public vrange
528 friend class frange_storage
;
529 friend class vrange_printer
;
532 frange (const frange
&);
533 frange (tree
, tree
, value_range_kind
= VR_RANGE
);
535 frange (tree type
, const REAL_VALUE_TYPE
&min
, const REAL_VALUE_TYPE
&max
,
536 value_range_kind
= VR_RANGE
);
537 static bool supports_p (const_tree type
)
539 // ?? Decimal floats can have multiple representations for the
540 // same number. Supporting them may be as simple as just
541 // disabling them in singleton_p. No clue.
542 return SCALAR_FLOAT_TYPE_P (type
) && !DECIMAL_FLOAT_TYPE_P (type
);
544 virtual tree
type () const override
;
545 void set (tree type
, const REAL_VALUE_TYPE
&, const REAL_VALUE_TYPE
&,
546 value_range_kind
= VR_RANGE
);
547 void set (tree type
, const REAL_VALUE_TYPE
&, const REAL_VALUE_TYPE
&,
548 const nan_state
&, value_range_kind
= VR_RANGE
);
549 void set_nan (tree type
);
550 void set_nan (tree type
, bool sign
);
551 void set_nan (tree type
, const nan_state
&);
552 virtual void set_varying (tree type
) override
;
553 virtual void set_undefined () override
;
554 virtual bool union_ (const vrange
&) override
;
555 virtual bool intersect (const vrange
&) override
;
556 bool contains_p (const REAL_VALUE_TYPE
&) const;
557 virtual bool singleton_p (tree
*result
= NULL
) const override
;
558 bool singleton_p (REAL_VALUE_TYPE
&r
) const;
559 virtual bool supports_type_p (const_tree type
) const override
;
560 virtual void accept (const vrange_visitor
&v
) const override
;
561 virtual bool zero_p () const override
;
562 virtual bool nonzero_p () const override
;
563 virtual void set_nonzero (tree type
) override
;
564 virtual void set_zero (tree type
) override
;
565 virtual void set_nonnegative (tree type
) override
;
566 virtual bool fits_p (const vrange
&) const override
;
567 frange
& operator= (const frange
&);
568 bool operator== (const frange
&) const;
569 bool operator!= (const frange
&r
) const { return !(*this == r
); }
570 const REAL_VALUE_TYPE
&lower_bound () const;
571 const REAL_VALUE_TYPE
&upper_bound () const;
572 virtual tree
lbound () const override
;
573 virtual tree
ubound () const override
;
574 nan_state
get_nan_state () const;
576 void update_nan (bool sign
);
577 void update_nan (tree
) = delete; // Disallow silent conversion to bool.
578 void update_nan (const nan_state
&);
580 void flush_denormals_to_zero ();
582 // fpclassify like API
583 bool known_isfinite () const;
584 bool known_isnan () const;
585 bool known_isinf () const;
586 bool maybe_isnan () const;
587 bool maybe_isnan (bool sign
) const;
588 bool maybe_isinf () const;
589 bool signbit_p (bool &signbit
) const;
590 bool nan_signbit_p (bool &signbit
) const;
593 virtual bool contains_p (tree cst
) const override
;
594 virtual void set (tree
, tree
, value_range_kind
= VR_RANGE
) override
;
597 bool internal_singleton_p (REAL_VALUE_TYPE
* = NULL
) const;
598 void verify_range ();
599 bool normalize_kind ();
600 bool union_nans (const frange
&);
601 bool intersect_nans (const frange
&);
602 bool combine_zeros (const frange
&, bool union_p
);
605 REAL_VALUE_TYPE m_min
;
606 REAL_VALUE_TYPE m_max
;
611 inline const REAL_VALUE_TYPE
&
612 frange::lower_bound () const
614 gcc_checking_assert (!undefined_p () && !known_isnan ());
618 inline const REAL_VALUE_TYPE
&
619 frange::upper_bound () const
621 gcc_checking_assert (!undefined_p () && !known_isnan ());
625 // Return the NAN state.
628 frange::get_nan_state () const
630 return nan_state (m_pos_nan
, m_neg_nan
);
633 // is_a<> and as_a<> implementation for vrange.
635 // Anything we haven't specialized is a hard fail.
636 template <typename T
>
644 template <typename T
>
646 is_a (const vrange
&v
)
648 // Reuse is_a <vrange> to implement the const version.
649 const T
&derived
= static_cast<const T
&> (v
);
650 return is_a
<T
> (const_cast<T
&> (derived
));
653 template <typename T
>
657 gcc_checking_assert (is_a
<T
> (v
));
658 return static_cast <T
&> (v
);
661 template <typename T
>
663 as_a (const vrange
&v
)
665 gcc_checking_assert (is_a
<T
> (v
));
666 return static_cast <const T
&> (v
);
669 // Specializations for the different range types.
673 is_a
<irange
> (vrange
&v
)
675 return v
.m_discriminator
== VR_IRANGE
;
680 is_a
<prange
> (vrange
&v
)
682 return v
.m_discriminator
== VR_PRANGE
;
687 is_a
<frange
> (vrange
&v
)
689 return v
.m_discriminator
== VR_FRANGE
;
694 is_a
<unsupported_range
> (vrange
&v
)
696 return v
.m_discriminator
== VR_UNKNOWN
;
699 // For resizable ranges, resize the range up to HARD_MAX_RANGES if the
700 // NEEDED pairs is greater than the current capacity of the range.
703 irange::maybe_resize (int needed
)
705 if (!m_resizable
|| m_max_ranges
== HARD_MAX_RANGES
)
708 if (needed
> m_max_ranges
)
710 m_max_ranges
= HARD_MAX_RANGES
;
711 wide_int
*newmem
= new wide_int
[m_max_ranges
* 2];
712 unsigned n
= num_pairs () * 2;
713 for (unsigned i
= 0; i
< n
; ++i
)
714 newmem
[i
] = m_base
[i
];
719 template<unsigned N
, bool RESIZABLE
>
721 int_range
<N
, RESIZABLE
>::~int_range ()
723 if (RESIZABLE
&& m_base
!= m_ranges
)
727 // This is an "infinite" precision irange for use in temporary
728 // calculations. It starts with a sensible default covering 99% of
729 // uses, and goes up to HARD_MAX_RANGES when needed. Any allocated
730 // storage is freed upon destruction.
731 typedef int_range
<3, /*RESIZABLE=*/true> int_range_max
;
736 virtual void visit (const irange
&) const { }
737 virtual void visit (const prange
&) const { }
738 virtual void visit (const frange
&) const { }
739 virtual void visit (const unsupported_range
&) const { }
742 typedef int_range
<2> value_range
;
744 // This is an "infinite" precision range object for use in temporary
745 // calculations for any of the handled types. The object can be
746 // transparently used as a vrange.
748 // Using any of the various constructors initializes the object
749 // appropriately, but the default constructor is uninitialized and
750 // must be initialized either with set_type() or by assigning into it.
752 // Assigning between incompatible types is allowed. For example if a
753 // temporary holds an irange, you can assign an frange into it, and
754 // all the right things will happen. However, before passing this
755 // object to a function accepting a vrange, the correct type must be
756 // set. If it isn't, you can do so with set_type().
762 Value_Range (const vrange
&r
);
763 Value_Range (tree type
);
764 Value_Range (tree
, tree
, value_range_kind kind
= VR_RANGE
);
765 Value_Range (const Value_Range
&);
767 void set_type (tree type
);
768 vrange
& operator= (const vrange
&);
769 Value_Range
& operator= (const Value_Range
&);
770 bool operator== (const Value_Range
&r
) const;
771 bool operator!= (const Value_Range
&r
) const;
773 operator const vrange
&() const;
774 void dump (FILE *) const;
775 static bool supports_type_p (const_tree type
);
777 tree
type () { return m_vrange
->type (); }
778 bool varying_p () const { return m_vrange
->varying_p (); }
779 bool undefined_p () const { return m_vrange
->undefined_p (); }
780 void set_varying (tree type
) { init (type
); m_vrange
->set_varying (type
); }
781 void set_undefined () { m_vrange
->set_undefined (); }
782 bool union_ (const vrange
&r
) { return m_vrange
->union_ (r
); }
783 bool intersect (const vrange
&r
) { return m_vrange
->intersect (r
); }
784 bool contains_p (tree cst
) const { return m_vrange
->contains_p (cst
); }
785 bool singleton_p (tree
*result
= NULL
) const
786 { return m_vrange
->singleton_p (result
); }
787 void set_zero (tree type
) { init (type
); return m_vrange
->set_zero (type
); }
788 void set_nonzero (tree type
)
789 { init (type
); return m_vrange
->set_nonzero (type
); }
790 bool nonzero_p () const { return m_vrange
->nonzero_p (); }
791 bool zero_p () const { return m_vrange
->zero_p (); }
792 tree
lbound () const { return m_vrange
->lbound (); }
793 tree
ubound () const { return m_vrange
->ubound (); }
794 irange_bitmask
get_bitmask () const { return m_vrange
->get_bitmask (); }
795 void update_bitmask (const class irange_bitmask
&bm
)
796 { return m_vrange
->update_bitmask (bm
); }
797 void accept (const vrange_visitor
&v
) const { m_vrange
->accept (v
); }
799 void init (tree type
);
800 void init (const vrange
&);
803 // The buffer must be at least the size of the largest range.
804 static_assert (sizeof (int_range_max
) > sizeof (frange
), "");
805 static_assert (sizeof (int_range_max
) > sizeof (prange
), "");
806 char m_buffer
[sizeof (int_range_max
)];
809 // The default constructor is uninitialized and must be initialized
810 // with either set_type() or with an assignment into it.
813 Value_Range::Value_Range ()
821 Value_Range::Value_Range (const Value_Range
&r
)
826 // Copy constructor from a vrange.
829 Value_Range::Value_Range (const vrange
&r
)
834 // Construct an UNDEFINED range that can hold ranges of TYPE. If TYPE
835 // is not supported, default to unsupported_range.
838 Value_Range::Value_Range (tree type
)
843 // Construct a range that can hold a range of [MIN, MAX], where MIN
844 // and MAX are trees.
847 Value_Range::Value_Range (tree min
, tree max
, value_range_kind kind
)
849 init (TREE_TYPE (min
));
850 m_vrange
->set (min
, max
, kind
);
854 Value_Range::~Value_Range ()
857 m_vrange
->~vrange ();
860 // Initialize object to an UNDEFINED range that can hold ranges of
861 // TYPE. Clean-up memory if there was a previous object.
864 Value_Range::set_type (tree type
)
867 m_vrange
->~vrange ();
871 // Initialize object to an UNDEFINED range that can hold ranges of
875 Value_Range::init (tree type
)
877 gcc_checking_assert (TYPE_P (type
));
879 if (irange::supports_p (type
))
880 m_vrange
= new (&m_buffer
) int_range_max ();
881 else if (prange::supports_p (type
))
882 m_vrange
= new (&m_buffer
) prange ();
883 else if (frange::supports_p (type
))
884 m_vrange
= new (&m_buffer
) frange ();
886 m_vrange
= new (&m_buffer
) unsupported_range ();
889 // Initialize object with a copy of R.
892 Value_Range::init (const vrange
&r
)
894 if (is_a
<irange
> (r
))
895 m_vrange
= new (&m_buffer
) int_range_max (as_a
<irange
> (r
));
896 else if (is_a
<prange
> (r
))
897 m_vrange
= new (&m_buffer
) prange (as_a
<prange
> (r
));
898 else if (is_a
<frange
> (r
))
899 m_vrange
= new (&m_buffer
) frange (as_a
<frange
> (r
));
901 m_vrange
= new (&m_buffer
) unsupported_range (as_a
<unsupported_range
> (r
));
904 // Assignment operator. Copying incompatible types is allowed. That
905 // is, assigning an frange to an object holding an irange does the
909 Value_Range::operator= (const vrange
&r
)
912 m_vrange
->~vrange ();
918 Value_Range::operator= (const Value_Range
&r
)
920 // No need to call the m_vrange destructor here, as we will do so in
921 // the assignment below.
927 Value_Range::operator== (const Value_Range
&r
) const
929 return *m_vrange
== *r
.m_vrange
;
933 Value_Range::operator!= (const Value_Range
&r
) const
935 return *m_vrange
!= *r
.m_vrange
;
939 Value_Range::operator vrange
&()
945 Value_Range::operator const vrange
&() const
950 // Return TRUE if TYPE is supported by the vrange infrastructure.
953 Value_Range::supports_type_p (const_tree type
)
955 return irange::supports_p (type
)
956 || prange::supports_p (type
)
957 || frange::supports_p (type
);
960 extern value_range_kind
get_legacy_range (const vrange
&, tree
&min
, tree
&max
);
961 extern void dump_value_range (FILE *, const vrange
*);
962 extern bool vrp_operand_equal_p (const_tree
, const_tree
);
963 inline REAL_VALUE_TYPE
frange_val_min (const_tree type
);
964 inline REAL_VALUE_TYPE
frange_val_max (const_tree type
);
966 // Number of sub-ranges in a range.
969 irange::num_pairs () const
975 irange::type () const
977 gcc_checking_assert (m_num_ranges
> 0);
982 irange::varying_compatible_p () const
984 if (m_num_ranges
!= 1)
987 const wide_int
&l
= m_base
[0];
988 const wide_int
&u
= m_base
[1];
991 if (m_kind
== VR_VARYING
&& t
== error_mark_node
)
994 unsigned prec
= TYPE_PRECISION (t
);
995 signop sign
= TYPE_SIGN (t
);
996 if (INTEGRAL_TYPE_P (t
) || POINTER_TYPE_P (t
))
997 return (l
== wi::min_value (prec
, sign
)
998 && u
== wi::max_value (prec
, sign
)
999 && m_bitmask
.unknown_p ());
1004 vrange::varying_p () const
1006 return m_kind
== VR_VARYING
;
1010 vrange::undefined_p () const
1012 return m_kind
== VR_UNDEFINED
;
1016 irange::zero_p () const
1018 return (m_kind
== VR_RANGE
&& m_num_ranges
== 1
1019 && lower_bound (0) == 0
1020 && upper_bound (0) == 0);
1024 irange::nonzero_p () const
1029 wide_int zero
= wi::zero (TYPE_PRECISION (type ()));
1030 return *this == int_range
<2> (type (), zero
, zero
, VR_ANTI_RANGE
);
1034 irange::supports_p (const_tree type
)
1036 return INTEGRAL_TYPE_P (type
) || POINTER_TYPE_P (type
);
1040 irange::contains_p (tree cst
) const
1042 return contains_p (wi::to_wide (cst
));
1046 range_includes_zero_p (const vrange
&vr
)
1048 if (vr
.undefined_p ())
1051 if (vr
.varying_p ())
1054 return vr
.contains_p (build_zero_cst (vr
.type ()));
1057 // Constructors for irange
1060 irange::irange (wide_int
*base
, unsigned nranges
, bool resizable
)
1061 : vrange (VR_IRANGE
),
1062 m_resizable (resizable
),
1063 m_max_ranges (nranges
)
1069 // Constructors for int_range<>.
1071 template<unsigned N
, bool RESIZABLE
>
1073 int_range
<N
, RESIZABLE
>::int_range ()
1074 : irange (m_ranges
, N
, RESIZABLE
)
1078 template<unsigned N
, bool RESIZABLE
>
1079 int_range
<N
, RESIZABLE
>::int_range (const int_range
&other
)
1080 : irange (m_ranges
, N
, RESIZABLE
)
1082 irange::operator= (other
);
1085 template<unsigned N
, bool RESIZABLE
>
1086 int_range
<N
, RESIZABLE
>::int_range (tree min
, tree max
, value_range_kind kind
)
1087 : irange (m_ranges
, N
, RESIZABLE
)
1089 irange::set (min
, max
, kind
);
1092 template<unsigned N
, bool RESIZABLE
>
1093 int_range
<N
, RESIZABLE
>::int_range (tree type
)
1094 : irange (m_ranges
, N
, RESIZABLE
)
1099 template<unsigned N
, bool RESIZABLE
>
1100 int_range
<N
, RESIZABLE
>::int_range (tree type
, const wide_int
&wmin
, const wide_int
&wmax
,
1101 value_range_kind kind
)
1102 : irange (m_ranges
, N
, RESIZABLE
)
1104 set (type
, wmin
, wmax
, kind
);
1107 template<unsigned N
, bool RESIZABLE
>
1108 int_range
<N
, RESIZABLE
>::int_range (const irange
&other
)
1109 : irange (m_ranges
, N
, RESIZABLE
)
1111 irange::operator= (other
);
1114 template<unsigned N
, bool RESIZABLE
>
1115 int_range
<N
, RESIZABLE
>&
1116 int_range
<N
, RESIZABLE
>::operator= (const int_range
&src
)
1118 irange::operator= (src
);
1123 irange::set_undefined ()
1125 m_kind
= VR_UNDEFINED
;
1130 irange::set_varying (tree type
)
1132 m_kind
= VR_VARYING
;
1134 m_bitmask
.set_unknown (TYPE_PRECISION (type
));
1136 if (INTEGRAL_TYPE_P (type
) || POINTER_TYPE_P (type
))
1139 // Strict enum's require varying to be not TYPE_MIN/MAX, but rather
1140 // min_value and max_value.
1141 m_base
[0] = wi::min_value (TYPE_PRECISION (type
), TYPE_SIGN (type
));
1142 m_base
[1] = wi::max_value (TYPE_PRECISION (type
), TYPE_SIGN (type
));
1145 m_type
= error_mark_node
;
1148 // Return the lower bound of a sub-range. PAIR is the sub-range in
1152 irange::lower_bound (unsigned pair
) const
1154 gcc_checking_assert (m_num_ranges
> 0);
1155 gcc_checking_assert (pair
+ 1 <= num_pairs ());
1156 return m_base
[pair
* 2];
1159 // Return the upper bound of a sub-range. PAIR is the sub-range in
1163 irange::upper_bound (unsigned pair
) const
1165 gcc_checking_assert (m_num_ranges
> 0);
1166 gcc_checking_assert (pair
+ 1 <= num_pairs ());
1167 return m_base
[pair
* 2 + 1];
1170 // Return the highest bound of a range.
1173 irange::upper_bound () const
1175 unsigned pairs
= num_pairs ();
1176 gcc_checking_assert (pairs
> 0);
1177 return upper_bound (pairs
- 1);
1180 // Set value range VR to a nonzero range of type TYPE.
1183 irange::set_nonzero (tree type
)
1185 unsigned prec
= TYPE_PRECISION (type
);
1187 if (TYPE_UNSIGNED (type
))
1191 m_base
[0] = wi::one (prec
);
1192 m_base
[1] = wi::minus_one (prec
);
1193 m_bitmask
.set_unknown (prec
);
1201 wide_int zero
= wi::zero (prec
);
1202 set (type
, zero
, zero
, VR_ANTI_RANGE
);
1206 // Set value range VR to a ZERO range of type TYPE.
1209 irange::set_zero (tree type
)
1211 wide_int zero
= wi::zero (TYPE_PRECISION (type
));
1212 set (type
, zero
, zero
);
1215 // Normalize a range to VARYING or UNDEFINED if possible.
1218 irange::normalize_kind ()
1220 if (m_num_ranges
== 0)
1222 else if (varying_compatible_p ())
1224 if (m_kind
== VR_RANGE
)
1225 m_kind
= VR_VARYING
;
1226 else if (m_kind
== VR_ANTI_RANGE
)
1234 contains_zero_p (const irange
&r
)
1236 if (r
.undefined_p ())
1239 wide_int zero
= wi::zero (TYPE_PRECISION (r
.type ()));
1240 return r
.contains_p (zero
);
1244 irange_val_min (const_tree type
)
1246 gcc_checking_assert (irange::supports_p (type
));
1247 return wi::min_value (TYPE_PRECISION (type
), TYPE_SIGN (type
));
1251 irange_val_max (const_tree type
)
1253 gcc_checking_assert (irange::supports_p (type
));
1254 return wi::max_value (TYPE_PRECISION (type
), TYPE_SIGN (type
));
1259 : vrange (VR_PRANGE
)
1265 prange::prange (const prange
&r
)
1266 : vrange (VR_PRANGE
)
1272 prange::prange (tree type
)
1273 : vrange (VR_PRANGE
)
1279 prange::prange (tree type
, const wide_int
&lb
, const wide_int
&ub
,
1280 value_range_kind kind
)
1281 : vrange (VR_PRANGE
)
1283 set (type
, lb
, ub
, kind
);
1287 prange::supports_p (const_tree type
)
1289 return POINTER_TYPE_P (type
);
1293 prange::supports_type_p (const_tree type
) const
1295 return POINTER_TYPE_P (type
);
1299 prange::set_undefined ()
1301 m_kind
= VR_UNDEFINED
;
1305 prange::set_varying (tree type
)
1307 m_kind
= VR_VARYING
;
1309 m_min
= wi::zero (TYPE_PRECISION (type
));
1310 m_max
= wi::max_value (TYPE_PRECISION (type
), UNSIGNED
);
1311 m_bitmask
.set_unknown (TYPE_PRECISION (type
));
1318 prange::set_nonzero (tree type
)
1322 m_min
= wi::one (TYPE_PRECISION (type
));
1323 m_max
= wi::max_value (TYPE_PRECISION (type
), UNSIGNED
);
1324 m_bitmask
.set_unknown (TYPE_PRECISION (type
));
1331 prange::set_zero (tree type
)
1335 wide_int zero
= wi::zero (TYPE_PRECISION (type
));
1336 m_min
= m_max
= zero
;
1337 m_bitmask
= irange_bitmask (zero
, zero
);
1344 prange::contains_p (tree cst
) const
1346 return contains_p (wi::to_wide (cst
));
1350 prange::zero_p () const
1352 return m_kind
== VR_RANGE
&& m_min
== 0 && m_max
== 0;
1356 prange::nonzero_p () const
1358 return m_kind
== VR_RANGE
&& m_min
== 1 && m_max
== -1;
1362 prange::type () const
1364 gcc_checking_assert (!undefined_p ());
1369 prange::lower_bound () const
1371 gcc_checking_assert (!undefined_p ());
1376 prange::upper_bound () const
1378 gcc_checking_assert (!undefined_p ());
1383 prange::varying_compatible_p () const
1385 return (!undefined_p ()
1386 && m_min
== 0 && m_max
== -1 && get_bitmask ().unknown_p ());
1389 inline irange_bitmask
1390 prange::get_bitmask () const
1396 prange::fits_p (const vrange
&) const
1404 : vrange (VR_FRANGE
)
1410 frange::frange (const frange
&src
)
1411 : vrange (VR_FRANGE
)
1417 frange::frange (tree type
)
1418 : vrange (VR_FRANGE
)
1423 // frange constructor from REAL_VALUE_TYPE endpoints.
1426 frange::frange (tree type
,
1427 const REAL_VALUE_TYPE
&min
, const REAL_VALUE_TYPE
&max
,
1428 value_range_kind kind
)
1429 : vrange (VR_FRANGE
)
1431 set (type
, min
, max
, kind
);
1434 // frange constructor from trees.
1437 frange::frange (tree min
, tree max
, value_range_kind kind
)
1438 : vrange (VR_FRANGE
)
1440 set (min
, max
, kind
);
1444 frange::type () const
1446 gcc_checking_assert (!undefined_p ());
1451 frange::set_varying (tree type
)
1453 m_kind
= VR_VARYING
;
1455 m_min
= frange_val_min (type
);
1456 m_max
= frange_val_max (type
);
1457 if (HONOR_NANS (m_type
))
1470 frange::set_undefined ()
1472 m_kind
= VR_UNDEFINED
;
1476 // m_min and m_min are uninitialized as they are REAL_VALUE_TYPE ??.
1481 // Set the NAN bits to NAN and adjust the range.
1484 frange::update_nan (const nan_state
&nan
)
1486 gcc_checking_assert (!undefined_p ());
1487 if (HONOR_NANS (m_type
))
1489 m_pos_nan
= nan
.pos_p ();
1490 m_neg_nan
= nan
.neg_p ();
1497 // Set the NAN bit to +-NAN.
1500 frange::update_nan ()
1502 gcc_checking_assert (!undefined_p ());
1503 nan_state
nan (true);
1507 // Like above, but set the sign of the NAN.
1510 frange::update_nan (bool sign
)
1512 gcc_checking_assert (!undefined_p ());
1513 nan_state
nan (/*pos=*/!sign
, /*neg=*/sign
);
1518 frange::contains_p (tree cst
) const
1520 return contains_p (*TREE_REAL_CST_PTR (cst
));
1523 // Clear the NAN bit and adjust the range.
1526 frange::clear_nan ()
1528 gcc_checking_assert (!undefined_p ());
1536 // Set R to maximum representable value for TYPE.
1538 inline REAL_VALUE_TYPE
1539 real_max_representable (const_tree type
)
1543 get_max_float (REAL_MODE_FORMAT (TYPE_MODE (type
)),
1544 buf
, sizeof (buf
), false);
1545 int res
= real_from_string (&r
, buf
);
1546 gcc_checking_assert (!res
);
1550 // Return the minimum representable value for TYPE.
1552 inline REAL_VALUE_TYPE
1553 real_min_representable (const_tree type
)
1555 REAL_VALUE_TYPE r
= real_max_representable (type
);
1556 r
= real_value_negate (&r
);
1560 // Return the minimum value for TYPE.
1562 inline REAL_VALUE_TYPE
1563 frange_val_min (const_tree type
)
1565 if (HONOR_INFINITIES (type
))
1568 return real_min_representable (type
);
1571 // Return the maximum value for TYPE.
1573 inline REAL_VALUE_TYPE
1574 frange_val_max (const_tree type
)
1576 if (HONOR_INFINITIES (type
))
1579 return real_max_representable (type
);
1582 // Return TRUE if R is the minimum value for TYPE.
1585 frange_val_is_min (const REAL_VALUE_TYPE
&r
, const_tree type
)
1587 REAL_VALUE_TYPE min
= frange_val_min (type
);
1588 return real_identical (&min
, &r
);
1591 // Return TRUE if R is the max value for TYPE.
1594 frange_val_is_max (const REAL_VALUE_TYPE
&r
, const_tree type
)
1596 REAL_VALUE_TYPE max
= frange_val_max (type
);
1597 return real_identical (&max
, &r
);
1600 // Build a NAN with a state of NAN.
1603 frange::set_nan (tree type
, const nan_state
&nan
)
1605 gcc_checking_assert (nan
.pos_p () || nan
.neg_p ());
1606 if (HONOR_NANS (type
))
1610 m_neg_nan
= nan
.neg_p ();
1611 m_pos_nan
= nan
.pos_p ();
1619 // Build a signless NAN of type TYPE.
1622 frange::set_nan (tree type
)
1624 nan_state
nan (true);
1625 set_nan (type
, nan
);
1628 // Build a NAN of type TYPE with SIGN.
1631 frange::set_nan (tree type
, bool sign
)
1633 nan_state
nan (/*pos=*/!sign
, /*neg=*/sign
);
1634 set_nan (type
, nan
);
1637 // Return TRUE if range is known to be finite.
1640 frange::known_isfinite () const
1642 if (undefined_p () || varying_p () || m_kind
== VR_ANTI_RANGE
)
1644 return (!maybe_isnan () && !real_isinf (&m_min
) && !real_isinf (&m_max
));
1647 // Return TRUE if range may be infinite.
1650 frange::maybe_isinf () const
1652 if (undefined_p () || m_kind
== VR_ANTI_RANGE
|| m_kind
== VR_NAN
)
1656 return real_isinf (&m_min
) || real_isinf (&m_max
);
1659 // Return TRUE if range is known to be the [-INF,-INF] or [+INF,+INF].
1662 frange::known_isinf () const
1664 return (m_kind
== VR_RANGE
1666 && real_identical (&m_min
, &m_max
)
1667 && real_isinf (&m_min
));
1670 // Return TRUE if range is possibly a NAN.
1673 frange::maybe_isnan () const
1677 return m_pos_nan
|| m_neg_nan
;
1680 // Return TRUE if range is possibly a NAN with SIGN.
1683 frange::maybe_isnan (bool sign
) const
1692 // Return TRUE if range is a +NAN or -NAN.
1695 frange::known_isnan () const
1697 return m_kind
== VR_NAN
;
1700 // If the signbit for the range is known, set it in SIGNBIT and return
1704 frange::signbit_p (bool &signbit
) const
1709 // NAN with unknown sign.
1710 if (m_pos_nan
&& m_neg_nan
)
1713 if (!m_pos_nan
&& !m_neg_nan
)
1715 if (m_min
.sign
== m_max
.sign
)
1717 signbit
= m_min
.sign
;
1722 // NAN with known sign.
1723 bool nan_sign
= m_neg_nan
;
1725 || (nan_sign
== m_min
.sign
&& nan_sign
== m_max
.sign
))
1733 // If range has a NAN with a known sign, set it in SIGNBIT and return
1737 frange::nan_signbit_p (bool &signbit
) const
1742 if (m_pos_nan
== m_neg_nan
)
1745 signbit
= m_neg_nan
;
1749 void frange_nextafter (enum machine_mode
, REAL_VALUE_TYPE
&,
1750 const REAL_VALUE_TYPE
&);
1751 void frange_arithmetic (enum tree_code
, tree
, REAL_VALUE_TYPE
&,
1752 const REAL_VALUE_TYPE
&, const REAL_VALUE_TYPE
&,
1753 const REAL_VALUE_TYPE
&);
1755 // Return true if TYPE1 and TYPE2 are compatible range types.
1758 range_compatible_p (tree type1
, tree type2
)
1760 // types_compatible_p requires conversion in both directions to be useless.
1761 // GIMPLE only requires a cast one way in order to be compatible.
1762 // Ranges really only need the sign and precision to be the same.
1763 return TYPE_SIGN (type1
) == TYPE_SIGN (type2
)
1764 && (TYPE_PRECISION (type1
) == TYPE_PRECISION (type2
)
1765 // FIXME: As PR112788 shows, for now on rs6000 _Float128 has
1766 // type precision 128 while long double has type precision 127
1767 // but both have the same mode so their precision is actually
1768 // the same, workaround it temporarily.
1769 || (SCALAR_FLOAT_TYPE_P (type1
)
1770 && TYPE_MODE (type1
) == TYPE_MODE (type2
)));
1772 #endif // GCC_VALUE_RANGE_H