Line data Source code
1 : /* Support routines for value ranges.
2 : Copyright (C) 2019-2026 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 : class irange;
26 :
27 : // Types of value ranges.
28 : enum value_range_kind
29 : {
30 : /* Empty range. */
31 : VR_UNDEFINED,
32 : /* Range spans the entire domain. */
33 : VR_VARYING,
34 : /* Range is [MIN, MAX]. */
35 : VR_RANGE,
36 : /* Range is ~[MIN, MAX]. */
37 : VR_ANTI_RANGE,
38 : /* Range is a NAN. */
39 : VR_NAN,
40 : /* Range is a nice guy. */
41 : VR_LAST
42 : };
43 :
44 : // Discriminator between different vrange types.
45 :
46 : enum value_range_discriminator
47 : {
48 : // Range holds an integer or pointer.
49 : VR_IRANGE,
50 : // Pointer range.
51 : VR_PRANGE,
52 : // Floating point range.
53 : VR_FRANGE,
54 : // Range holds an unsupported type.
55 : VR_UNKNOWN
56 : };
57 :
58 : // Abstract class for representing subsets of values for various
59 : // supported types, such as the possible values of a variable.
60 : //
61 : // There are subclasses for each of integer, floating point, and pointer
62 : // types, each with their own strategies for efficiently representing
63 : // subsets of values.
64 : //
65 : // For efficiency, we can't precisely represent any arbitrary subset
66 : // of values of a type (which could require 2^N bits for a type of size N)
67 : // Hence operations on the subclasses may introduce imprecision
68 : // due to over-approximating the possible subsets.
69 : //
70 : // To query what types ranger and the entire ecosystem can support,
71 : // use value_range::supports_type_p(tree type). This is a static
72 : // method available independently of any vrange object.
73 : //
74 : // To query what a given vrange variant can support, use:
75 : // irange::supports_p ()
76 : // frange::supports_p ()
77 : // etc
78 : //
79 : // To query what a range object can support, use:
80 : // void foo (vrange &v, irange &i, frange &f)
81 : // {
82 : // if (v.supports_type_p (type)) ...
83 : // if (i.supports_type_p (type)) ...
84 : // if (f.supports_type_p (type)) ...
85 : // }
86 :
87 : class vrange
88 : {
89 : template <typename T> friend bool is_a (vrange &);
90 : friend class value_range;
91 : friend void streamer_write_vrange (struct output_block *, const vrange &);
92 : friend class range_op_handler;
93 : public:
94 : virtual void accept (const class vrange_visitor &v) const = 0;
95 : virtual void set (tree, tree, value_range_kind = VR_RANGE) = 0;
96 : virtual tree type () const = 0;
97 : virtual bool supports_type_p (const_tree type) const = 0;
98 : virtual void set_varying (tree type) = 0;
99 : virtual void set_undefined () = 0;
100 : virtual bool union_ (const vrange &) = 0;
101 : virtual bool intersect (const vrange &) = 0;
102 : virtual bool singleton_p (tree *result = NULL) const = 0;
103 : virtual bool contains_p (tree cst) const = 0;
104 : virtual bool zero_p () const = 0;
105 : virtual bool nonzero_p () const = 0;
106 : virtual void set_nonzero (tree type) = 0;
107 : virtual void set_zero (tree type) = 0;
108 : virtual void set_nonnegative (tree type) = 0;
109 : virtual bool fits_p (const vrange &r) const = 0;
110 5155728340 : virtual ~vrange () { }
111 : virtual tree lbound () const = 0;
112 : virtual tree ubound () const = 0;
113 : virtual void update_bitmask (const class irange_bitmask &);
114 : virtual irange_bitmask get_bitmask () const;
115 : wide_int get_nonzero_bits () const;
116 : void set_nonzero_bits (const wide_int &bits);
117 :
118 : bool varying_p () const;
119 : bool undefined_p () const;
120 : vrange& operator= (const vrange &);
121 : bool operator== (const vrange &) const;
122 13976494 : bool operator!= (const vrange &r) const { return !(*this == r); }
123 : void dump (FILE *) const;
124 0 : virtual void verify_range () const { }
125 : protected:
126 6516237788 : vrange (enum value_range_discriminator d) : m_discriminator (d) { }
127 : ENUM_BITFIELD(value_range_kind) m_kind : 8;
128 : const ENUM_BITFIELD(value_range_discriminator) m_discriminator : 4;
129 : };
130 :
131 : namespace inchash
132 : {
133 : extern void add_vrange (const vrange &, hash &, unsigned flags = 0);
134 : }
135 :
136 : // A pair of values representing the known bits of a value. Zero bits
137 : // in MASK cover constant values. Set bits in MASK cover unknown
138 : // values. VALUE are the known bits for the bits where MASK is zero,
139 : // and must be zero for the unknown bits where MASK is set (needed as an
140 : // optimization of union and intersect)
141 : // For example:
142 : // VALUE: [..., 0, 1, 0]
143 : // MASK: [..., 1, 0, 0]
144 : // ^ ^ ^
145 : // | | known bit: {0}
146 : // | known bit: {1}
147 : // unknown bit: {0, 1}
148 :
149 : class irange_bitmask
150 : {
151 : public:
152 6282652263 : irange_bitmask () { /* uninitialized */ }
153 0 : irange_bitmask (unsigned prec) { set_unknown (prec); }
154 : irange_bitmask (const wide_int &value, const wide_int &mask);
155 : irange_bitmask (tree type, const wide_int &min, const wide_int &max);
156 :
157 1523577820 : wide_int value () const { return m_value; }
158 1839590801 : wide_int mask () const { return m_mask; }
159 : void set_unknown (unsigned prec);
160 : bool unknown_p () const;
161 : unsigned get_precision () const;
162 : void union_ (const irange_bitmask &src);
163 : bool intersect (const irange_bitmask &src);
164 : bool operator== (const irange_bitmask &src) const;
165 8207393 : bool operator!= (const irange_bitmask &src) const { return !(*this == src); }
166 : void verify_mask () const;
167 : void dump (FILE *) const;
168 : bool range_from_mask (irange &r, tree type) const;
169 :
170 : bool member_p (const wide_int &val) const;
171 :
172 : // Convenience functions for nonzero bitmask compatibility.
173 : wide_int get_nonzero_bits () const;
174 : void set_nonzero_bits (const wide_int &bits);
175 : private:
176 : wide_int m_value;
177 : wide_int m_mask;
178 : };
179 :
180 : inline void
181 3451798191 : irange_bitmask::set_unknown (unsigned prec)
182 : {
183 3451798191 : m_value = wi::zero (prec);
184 3451798191 : m_mask = wi::minus_one (prec);
185 3451798191 : if (flag_checking)
186 3451786020 : verify_mask ();
187 3451798191 : }
188 :
189 : // Return TRUE if THIS does not have any meaningful information.
190 :
191 : inline bool
192 5048606889 : irange_bitmask::unknown_p () const
193 : {
194 2345234199 : return m_mask == -1;
195 : }
196 :
197 : inline
198 1134635412 : irange_bitmask::irange_bitmask (const wide_int &value, const wide_int &mask)
199 : {
200 1134635412 : m_value = value;
201 1134635412 : m_mask = mask;
202 1134635412 : if (flag_checking)
203 1134631812 : verify_mask ();
204 1134635412 : }
205 :
206 : inline unsigned
207 : irange_bitmask::get_precision () const
208 : {
209 : return m_mask.get_precision ();
210 : }
211 :
212 : // The following two functions are meant for backwards compatibility
213 : // with the nonzero bitmask. A cleared bit means the value must be 0.
214 : // A set bit means we have no information for the bit.
215 :
216 : // Return the nonzero bits.
217 : inline wide_int
218 4645 : irange_bitmask::get_nonzero_bits () const
219 : {
220 4645 : return m_value | m_mask;
221 : }
222 :
223 : // Set the bitmask to the nonzero bits in BITS.
224 : inline void
225 : irange_bitmask::set_nonzero_bits (const wide_int &bits)
226 : {
227 : m_value = wi::zero (bits.get_precision ());
228 : m_mask = bits;
229 : if (flag_checking)
230 : verify_mask ();
231 : }
232 :
233 : // Return TRUE if val could be a valid value with this bitmask.
234 :
235 : inline bool
236 253860781 : irange_bitmask::member_p (const wide_int &val) const
237 : {
238 253860781 : if (unknown_p ())
239 : return true;
240 30265471 : wide_int res = m_mask & val;
241 30265471 : if (m_value != 0)
242 908379 : res |= ~m_mask & m_value;
243 30265471 : return res == val;
244 30265471 : }
245 :
246 : inline bool
247 1201839449 : irange_bitmask::operator== (const irange_bitmask &src) const
248 : {
249 1201839449 : bool unknown1 = unknown_p ();
250 1201839449 : bool unknown2 = src.unknown_p ();
251 1201839449 : if (unknown1 || unknown2)
252 916792252 : return unknown1 == unknown2;
253 285047197 : return m_value == src.m_value && m_mask == src.m_mask;
254 : }
255 :
256 : inline void
257 18107640 : irange_bitmask::union_ (const irange_bitmask &src)
258 : {
259 18107696 : m_mask = (m_mask | src.m_mask) | (m_value ^ src.m_value);
260 18107640 : m_value = m_value & src.m_value;
261 18107640 : if (flag_checking)
262 18107640 : verify_mask ();
263 18107640 : }
264 :
265 : // Return FALSE if the bitmask intersection is undefined.
266 :
267 : inline bool
268 799985923 : irange_bitmask::intersect (const irange_bitmask &src)
269 : {
270 : // If we have two known bits that are incompatible, the resulting
271 : // bit and therefore entire range is undefined. Return FALSE.
272 1599975980 : if (wi::bit_and (~(m_mask | src.m_mask),
273 2399957769 : m_value ^ src.m_value) != 0)
274 : return false;
275 : else
276 : {
277 799937221 : m_mask = m_mask & src.m_mask;
278 799937221 : m_value = m_value | src.m_value;
279 : }
280 799937221 : if (flag_checking)
281 799934720 : verify_mask ();
282 : return true;
283 : }
284 :
285 : // A subset of possible values for an integer type, leaving
286 : // allocation of storage to subclasses.
287 :
288 10206972206 : class irange : public vrange
289 : {
290 : friend class irange_storage;
291 : friend class vrange_printer;
292 : public:
293 : // In-place setters.
294 : void set (tree type, const wide_int &, const wide_int &,
295 : value_range_kind = VR_RANGE);
296 : virtual void set_nonzero (tree type) override;
297 : virtual void set_zero (tree type) override;
298 : virtual void set_nonnegative (tree type) override;
299 : virtual void set_varying (tree type) override;
300 : virtual void set_undefined () override;
301 :
302 : // Range types.
303 : static bool supports_p (const_tree type);
304 : virtual bool supports_type_p (const_tree type) const override;
305 : virtual tree type () const override;
306 :
307 : // Iteration over sub-ranges.
308 : unsigned num_pairs () const;
309 : wide_int lower_bound (unsigned = 0) const;
310 : wide_int upper_bound (unsigned) const;
311 : wide_int upper_bound () const;
312 : virtual tree lbound () const override;
313 : virtual tree ubound () const override;
314 :
315 : // Predicates.
316 : virtual bool zero_p () const override;
317 : virtual bool nonzero_p () const override;
318 : virtual bool singleton_p (tree *result = NULL) const override;
319 : bool singleton_p (wide_int &) const;
320 : bool contains_p (const wide_int &) const;
321 : bool nonnegative_p () const;
322 : bool nonpositive_p () const;
323 :
324 : // In-place operators.
325 : virtual bool union_ (const vrange &) override;
326 : virtual bool intersect (const vrange &) override;
327 : void invert ();
328 :
329 : // Operator overloads.
330 : irange& operator= (const irange &);
331 : bool operator== (const irange &) const;
332 : bool operator!= (const irange &r) const { return !(*this == r); }
333 :
334 : // Misc methods.
335 : virtual bool fits_p (const vrange &r) const override;
336 : virtual void accept (const vrange_visitor &v) const override;
337 :
338 : virtual void update_bitmask (const class irange_bitmask &) override;
339 : virtual irange_bitmask get_bitmask () const override;
340 :
341 : virtual void verify_range () const override;
342 : protected:
343 : void maybe_resize (int needed);
344 : virtual void set (tree, tree, value_range_kind = VR_RANGE) override;
345 : virtual bool contains_p (tree cst) const override;
346 : irange (wide_int *, unsigned nranges, bool resizable);
347 :
348 : // In-place operators.
349 : bool irange_contains_p (const irange &) const;
350 : bool irange_single_pair_union (const irange &r);
351 :
352 : void normalize_kind ();
353 :
354 :
355 : // Hard limit on max ranges allowed.
356 : static const int HARD_MAX_RANGES = 255;
357 : private:
358 : bool varying_compatible_p () const;
359 : bool intersect_bitmask (const irange &r);
360 : bool union_bitmask (const irange &r);
361 : bool set_range_from_bitmask ();
362 : bool snap_subranges ();
363 : bool snap (const wide_int &, const wide_int &, wide_int &, wide_int &,
364 : bool &);
365 :
366 : bool intersect (const wide_int& lb, const wide_int& ub);
367 : bool union_append (const irange &r);
368 : unsigned char m_num_ranges;
369 : bool m_resizable;
370 : unsigned char m_max_ranges;
371 : tree m_type;
372 : irange_bitmask m_bitmask;
373 : protected:
374 : wide_int *m_base;
375 : };
376 :
377 : // Here we describe an irange with N pairs of ranges. The storage for
378 : // the pairs is embedded in the class as an array.
379 : //
380 : // If RESIZABLE is true, the storage will be resized on the heap when
381 : // the number of ranges needed goes past N up to a max of
382 : // HARD_MAX_RANGES. This new storage is freed upon destruction.
383 :
384 : template<unsigned N, bool RESIZABLE = false>
385 : class int_range final : public irange
386 : {
387 : public:
388 : int_range ();
389 : int_range (tree type, const wide_int &, const wide_int &,
390 : value_range_kind = VR_RANGE);
391 : int_range (tree type);
392 : int_range (const int_range &);
393 : int_range (const irange &);
394 : ~int_range () final override;
395 : int_range& operator= (const int_range &);
396 : protected:
397 : int_range (tree, tree, value_range_kind = VR_RANGE);
398 : private:
399 : wide_int m_ranges[N*2];
400 : };
401 :
402 : class prange final : public vrange
403 : {
404 : friend class prange_storage;
405 : friend class vrange_printer;
406 : public:
407 : prange ();
408 : prange (const prange &);
409 : prange (tree type);
410 : prange (tree type, const wide_int &, const wide_int &,
411 : value_range_kind = VR_RANGE);
412 : static bool supports_p (const_tree type);
413 : virtual bool supports_type_p (const_tree type) const final override;
414 : virtual void accept (const vrange_visitor &v) const final override;
415 : virtual void set_undefined () final override;
416 : virtual void set_varying (tree type) final override;
417 : virtual void set_nonzero (tree type) final override;
418 : virtual void set_zero (tree type) final override;
419 : virtual void set_nonnegative (tree type) final override;
420 : virtual bool contains_p (tree cst) const final override;
421 : virtual bool fits_p (const vrange &v) const final override;
422 : virtual bool singleton_p (tree *result = NULL) const final override;
423 : virtual bool zero_p () const final override;
424 : virtual bool nonzero_p () const final override;
425 : virtual void set (tree, tree, value_range_kind = VR_RANGE) final override;
426 : virtual tree type () const final override;
427 : virtual bool union_ (const vrange &v) final override;
428 : virtual bool intersect (const vrange &v) final override;
429 : virtual tree lbound () const final override;
430 : virtual tree ubound () const final override;
431 :
432 : prange& operator= (const prange &);
433 : bool operator== (const prange &) const;
434 : void set (tree type, const wide_int &, const wide_int &,
435 : value_range_kind = VR_RANGE);
436 : void invert ();
437 : bool contains_p (const wide_int &) const;
438 : wide_int lower_bound () const;
439 : wide_int upper_bound () const;
440 : virtual void verify_range () const final override;
441 : irange_bitmask get_bitmask () const final override;
442 : void update_bitmask (const irange_bitmask &) final override;
443 :
444 : // prange interface to points to information.
445 : // It can point_to or point_away from an object. This represents both
446 : // sides of a conditional. ie:
447 : // if (p == &foo)
448 : // // p points to foo.
449 : // else
450 : // // p points away from foo.
451 : // pt_invariant () and pt_invariant_away () - Return pt if this is invariant.
452 : void set_pt (const prange &r);
453 : void set_pt (tree ptr, bool points_to_p = true);
454 :
455 : // unknown_p () is true if no object is pointed to.
456 : void set_pt_unknown ();
457 : bool pt_unknown_p () const;
458 :
459 : // Invariant points-to are is_gimple_min_invariant_p ().
460 : // Return expression or NULL_TREE for points-to or away
461 : tree pt_invariant () const;
462 : tree pt_invariant_away () const;
463 :
464 : // Return true if THIS and R both point to the same object.
465 : bool pt_invariant_p (const prange &r) const;
466 : // Return true if THIS and R both point away from the same object.
467 : bool pt_invariant_away_p (const prange &r) const;
468 : // Return true if THIS and R refer to the same object, and one is inverted
469 : // from the other, Ie, both to and away.
470 : bool pt_inverted_p (const prange &r) const;
471 :
472 : // Invert THIS if it points either to or away from an object.
473 : bool pt_invert ();
474 :
475 : // pt_base () - object/allocation the pointer refers into.
476 : tree pt_base () const;
477 : // pt_offset () - possible byte offset range from BASE.
478 : void pt_offset (irange &) const;
479 : // pt_size () - possible size range of the referenced object.
480 : void pt_size (irange &) const;
481 :
482 : protected:
483 : bool varying_compatible_p () const;
484 :
485 : tree m_type;
486 : wide_int m_min;
487 : wide_int m_max;
488 : irange_bitmask m_bitmask;
489 :
490 : // A prange can point to an object, or NOT point to an object.
491 : tree m_pt; // object points-to refers to.
492 : bool m_points_to_p; // Does it point to it (TRUE), or not (FALSE).
493 : // If P has the same points to fields as THIS.
494 : bool pt_equal_p (const class prange &p) const;
495 : };
496 :
497 : // Unsupported temporaries may be created by ranger before it's known
498 : // they're unsupported, or by vr_values::get_value_range.
499 :
500 0 : class unsupported_range : public vrange
501 : {
502 : public:
503 74185119 : unsupported_range ()
504 74185119 : : vrange (VR_UNKNOWN)
505 : {
506 74185119 : set_undefined ();
507 : }
508 641913 : unsupported_range (const unsupported_range &src)
509 641913 : : vrange (VR_UNKNOWN)
510 : {
511 641913 : unsupported_range::operator= (src);
512 : }
513 : void set (tree min, tree, value_range_kind = VR_RANGE) final override;
514 : tree type () const final override;
515 : bool supports_type_p (const_tree) const final override;
516 : void set_varying (tree) final override;
517 : void set_undefined () final override;
518 : void accept (const vrange_visitor &v) const final override;
519 : bool union_ (const vrange &r) final override;
520 : bool intersect (const vrange &r) final override;
521 : bool singleton_p (tree * = NULL) const final override;
522 : bool contains_p (tree) const final override;
523 : bool zero_p () const final override;
524 : bool nonzero_p () const final override;
525 : void set_nonzero (tree type) final override;
526 : void set_zero (tree type) final override;
527 : void set_nonnegative (tree type) final override;
528 : bool fits_p (const vrange &) const final override;
529 : unsupported_range& operator= (const unsupported_range &r);
530 : tree lbound () const final override;
531 : tree ubound () const final override;
532 : };
533 :
534 : // The possible NAN state of a floating point value as an opaque object.
535 : // This represents one of the four subsets of { -NaN, +NaN },
536 : // i.e. one of {}, { -NaN }, { +NaN}, or { -NaN, +NaN }.
537 :
538 : class nan_state
539 : {
540 : public:
541 : nan_state (bool);
542 : nan_state (bool pos_nan, bool neg_nan);
543 : bool neg_p () const;
544 : bool pos_p () const;
545 : private:
546 : bool m_pos_nan;
547 : bool m_neg_nan;
548 : };
549 :
550 : // Set NAN state to +-NAN if NAN_P is true. Otherwise set NAN state
551 : // to false.
552 :
553 : inline
554 64150054 : nan_state::nan_state (bool nan_p)
555 : {
556 64150054 : m_pos_nan = nan_p;
557 60038205 : m_neg_nan = nan_p;
558 : }
559 :
560 : // Constructor initializing the object to +NAN if POS_NAN is set, -NAN
561 : // if NEG_NAN is set, or +-NAN if both are set. Otherwise POS_NAN and
562 : // NEG_NAN are clear, and the object cannot be a NAN.
563 :
564 : inline
565 4077248 : nan_state::nan_state (bool pos_nan, bool neg_nan)
566 : {
567 4077248 : m_pos_nan = pos_nan;
568 4068062 : m_neg_nan = neg_nan;
569 : }
570 :
571 : // Return if +NAN is possible.
572 :
573 : inline bool
574 36187534 : nan_state::pos_p () const
575 : {
576 36187510 : return m_pos_nan;
577 : }
578 :
579 : // Return if -NAN is possible.
580 :
581 : inline bool
582 36016809 : nan_state::neg_p () const
583 : {
584 36016785 : return m_neg_nan;
585 : }
586 :
587 : // A subset of possible values for a floating point type.
588 : //
589 : // The representation is a type with a couple of endpoints, unioned
590 : // with a subset of { -NaN, +NaN }.
591 :
592 50146408 : class frange final : public vrange
593 : {
594 : friend class frange_storage;
595 : friend class vrange_printer;
596 : public:
597 : frange ();
598 : frange (const frange &);
599 : frange (tree, tree, value_range_kind = VR_RANGE);
600 : frange (tree type);
601 : frange (tree type, const REAL_VALUE_TYPE &min, const REAL_VALUE_TYPE &max,
602 : value_range_kind = VR_RANGE);
603 494595091 : static bool supports_p (const_tree type)
604 : {
605 : // ?? Decimal floats can have multiple representations for the
606 : // same number. Supporting them may be as simple as just
607 : // disabling them in singleton_p. No clue.
608 494595091 : return SCALAR_FLOAT_TYPE_P (type) && !DECIMAL_FLOAT_TYPE_P (type);
609 : }
610 : virtual tree type () const override;
611 : void set (tree type, const REAL_VALUE_TYPE &, const REAL_VALUE_TYPE &,
612 : value_range_kind = VR_RANGE);
613 : void set (tree type, const REAL_VALUE_TYPE &, const REAL_VALUE_TYPE &,
614 : const nan_state &, value_range_kind = VR_RANGE);
615 : void set_nan (tree type);
616 : void set_nan (tree type, bool sign);
617 : void set_nan (tree type, const nan_state &);
618 : virtual void set_varying (tree type) override;
619 : virtual void set_undefined () override;
620 : virtual bool union_ (const vrange &) override;
621 : virtual bool intersect (const vrange &) override;
622 : bool contains_p (const REAL_VALUE_TYPE &) const;
623 : virtual bool singleton_p (tree *result = NULL) const override;
624 : bool singleton_p (REAL_VALUE_TYPE &r) const;
625 : virtual bool supports_type_p (const_tree type) const override;
626 : virtual void accept (const vrange_visitor &v) const override;
627 : virtual bool zero_p () const override;
628 : virtual bool nonzero_p () const override;
629 : virtual void set_nonzero (tree type) override;
630 : virtual void set_zero (tree type) override;
631 : virtual void set_nonnegative (tree type) override;
632 : virtual bool fits_p (const vrange &) const override;
633 : frange& operator= (const frange &);
634 : bool operator== (const frange &) const;
635 12 : bool operator!= (const frange &r) const { return !(*this == r); }
636 : const REAL_VALUE_TYPE &lower_bound () const;
637 : const REAL_VALUE_TYPE &upper_bound () const;
638 : virtual tree lbound () const override;
639 : virtual tree ubound () const override;
640 : nan_state get_nan_state () const;
641 : void update_nan ();
642 : void update_nan (bool sign);
643 : void update_nan (tree) = delete; // Disallow silent conversion to bool.
644 : void update_nan (const nan_state &);
645 : void clear_nan ();
646 : void flush_denormals_to_zero ();
647 :
648 : // fpclassify like API
649 : bool known_isfinite () const;
650 : bool known_isnan () const;
651 : bool known_isinf () const;
652 : bool maybe_isnan () const;
653 : bool maybe_isnan (bool sign) const;
654 : bool maybe_isinf () const;
655 : bool signbit_p (bool &signbit) const;
656 : bool nan_signbit_p (bool &signbit) const;
657 : bool known_isnormal () const;
658 : bool known_isdenormal_or_zero () const;
659 : virtual void verify_range () const override;
660 : protected:
661 : virtual bool contains_p (tree cst) const override;
662 : virtual void set (tree, tree, value_range_kind = VR_RANGE) override;
663 :
664 : private:
665 : bool internal_singleton_p (REAL_VALUE_TYPE * = NULL) const;
666 : bool normalize_kind ();
667 : bool union_nans (const frange &);
668 : bool intersect_nans (const frange &);
669 : bool combine_zeros (const frange &, bool union_p);
670 :
671 : tree m_type;
672 : REAL_VALUE_TYPE m_min;
673 : REAL_VALUE_TYPE m_max;
674 : bool m_pos_nan;
675 : bool m_neg_nan;
676 : };
677 :
678 : inline const REAL_VALUE_TYPE &
679 20785807 : frange::lower_bound () const
680 : {
681 20785807 : gcc_checking_assert (!undefined_p () && !known_isnan ());
682 20785807 : return m_min;
683 : }
684 :
685 : inline const REAL_VALUE_TYPE &
686 19331937 : frange::upper_bound () const
687 : {
688 19331937 : gcc_checking_assert (!undefined_p () && !known_isnan ());
689 19331937 : return m_max;
690 : }
691 :
692 : // Return the NAN state.
693 :
694 : inline nan_state
695 1816262 : frange::get_nan_state () const
696 : {
697 1816262 : return nan_state (m_pos_nan, m_neg_nan);
698 : }
699 :
700 : // is_a<> and as_a<> implementation for vrange.
701 :
702 : // Anything we haven't specialized is a hard fail.
703 : template <typename T>
704 : inline bool
705 : is_a (vrange &)
706 : {
707 : gcc_unreachable ();
708 : return false;
709 : }
710 :
711 : template <typename T>
712 : inline bool
713 4328104878 : is_a (const vrange &v)
714 : {
715 : // Reuse is_a <vrange> to implement the const version.
716 4535431671 : const T &derived = static_cast<const T &> (v);
717 1973763120 : return is_a <T> (const_cast<T &> (derived));
718 : }
719 :
720 : template <typename T>
721 : inline T &
722 2568786789 : as_a (vrange &v)
723 : {
724 0 : gcc_checking_assert (is_a <T> (v));
725 2568786789 : return static_cast <T &> (v);
726 : }
727 :
728 : template <typename T>
729 : inline const T &
730 3699479743 : as_a (const vrange &v)
731 : {
732 0 : gcc_checking_assert (is_a <T> (v));
733 3699479743 : return static_cast <const T &> (v);
734 : }
735 :
736 : // Specializations for the different range types.
737 :
738 : template <>
739 : inline bool
740 7352870267 : is_a <irange> (vrange &v)
741 : {
742 7225409995 : return v.m_discriminator == VR_IRANGE;
743 : }
744 :
745 : template <>
746 : inline bool
747 1472158068 : is_a <prange> (vrange &v)
748 : {
749 1328068420 : return v.m_discriminator == VR_PRANGE;
750 : }
751 :
752 : template <>
753 : inline bool
754 189362674 : is_a <frange> (vrange &v)
755 : {
756 189362674 : return v.m_discriminator == VR_FRANGE;
757 : }
758 :
759 : template <>
760 : inline bool
761 641913 : is_a <unsupported_range> (vrange &v)
762 : {
763 641913 : return v.m_discriminator == VR_UNKNOWN;
764 : }
765 :
766 : // For resizable ranges, resize the range up to HARD_MAX_RANGES if the
767 : // NEEDED pairs is greater than the current capacity of the range.
768 :
769 : inline void
770 1336100755 : irange::maybe_resize (int needed)
771 : {
772 1336100755 : if (!m_resizable || m_max_ranges == HARD_MAX_RANGES)
773 : return;
774 :
775 868554848 : if (needed > m_max_ranges)
776 : {
777 64134936 : m_max_ranges = HARD_MAX_RANGES;
778 32772952296 : wide_int *newmem = new wide_int[m_max_ranges * 2];
779 64134936 : unsigned n = num_pairs () * 2;
780 367020600 : for (unsigned i = 0; i < n; ++i)
781 302885664 : newmem[i] = m_base[i];
782 64134936 : m_base = newmem;
783 : }
784 : }
785 :
786 : template<unsigned N, bool RESIZABLE>
787 : inline
788 5103486103 : int_range<N, RESIZABLE>::~int_range ()
789 : {
790 3801231091 : if (RESIZABLE && m_base != m_ranges)
791 32772952296 : delete[] m_base;
792 31687260385 : }
793 :
794 : // This is an "infinite" precision irange for use in temporary
795 : // calculations. It starts with a sensible default covering 99% of
796 : // uses, and goes up to HARD_MAX_RANGES when needed. Any allocated
797 : // storage is freed upon destruction.
798 : typedef int_range<3, /*RESIZABLE=*/true> int_range_max;
799 :
800 40532 : class vrange_visitor
801 : {
802 : public:
803 0 : virtual void visit (const irange &) const { }
804 0 : virtual void visit (const prange &) const { }
805 0 : virtual void visit (const frange &) const { }
806 0 : virtual void visit (const unsupported_range &) const { }
807 : };
808 :
809 : // This is an "infinite" precision range object for use in temporary
810 : // calculations for any of the handled types. The object can be
811 : // transparently used as a vrange.
812 : //
813 : // Using any of the various constructors initializes the object
814 : // appropriately, but the default constructor is uninitialized and
815 : // must be initialized either with set_range_class() or by assigning into it.
816 : //
817 : // Assigning between incompatible types is allowed. For example if a
818 : // temporary holds an irange, you can assign an frange into it, and
819 : // all the right things will happen. However, before passing this
820 : // object to a function accepting a vrange, the correct type must be
821 : // set. If it isn't, you can do so with set_range_class().
822 :
823 : class value_range
824 : {
825 : public:
826 : value_range ();
827 : value_range (const vrange &r);
828 : value_range (tree type);
829 : value_range (tree, tree, value_range_kind kind = VR_RANGE);
830 : value_range (const value_range &);
831 : ~value_range ();
832 : void set_range_class (tree type);
833 : vrange& operator= (const vrange &);
834 : value_range& operator= (const value_range &);
835 : bool operator== (const value_range &r) const;
836 : bool operator!= (const value_range &r) const;
837 : operator vrange &();
838 : operator const vrange &() const;
839 : void dump (FILE *) const;
840 : void print (pretty_printer *) const;
841 : static bool supports_type_p (const_tree type);
842 :
843 3486661 : tree type () { return m_vrange->type (); }
844 155777430 : bool varying_p () const { return m_vrange->varying_p (); }
845 122914354 : bool undefined_p () const { return m_vrange->undefined_p (); }
846 314303129 : void set_varying (tree type) { init (type); m_vrange->set_varying (type); }
847 23124283 : void set_undefined () { m_vrange->set_undefined (); }
848 18497756 : bool union_ (const vrange &r) { return m_vrange->union_ (r); }
849 99066889 : bool intersect (const vrange &r) { return m_vrange->intersect (r); }
850 1511415 : bool contains_p (tree cst) const { return m_vrange->contains_p (cst); }
851 340173413 : bool singleton_p (tree *result = NULL) const
852 340173413 : { return m_vrange->singleton_p (result); }
853 : void set_zero (tree type) { init (type); return m_vrange->set_zero (type); }
854 0 : void set_nonzero (tree type)
855 0 : { init (type); return m_vrange->set_nonzero (type); }
856 269277 : bool nonzero_p () const { return m_vrange->nonzero_p (); }
857 4354 : bool zero_p () const { return m_vrange->zero_p (); }
858 10955094 : tree lbound () const { return m_vrange->lbound (); }
859 351082 : tree ubound () const { return m_vrange->ubound (); }
860 512567 : irange_bitmask get_bitmask () const { return m_vrange->get_bitmask (); }
861 1433484 : void update_bitmask (const class irange_bitmask &bm)
862 1433484 : { return m_vrange->update_bitmask (bm); }
863 2813 : void accept (const vrange_visitor &v) const { m_vrange->accept (v); }
864 : void verify_range () const { m_vrange->verify_range (); }
865 : private:
866 : void init (tree type);
867 : void init (const vrange &);
868 :
869 : vrange *m_vrange;
870 : union buffer_type {
871 : int_range_max ints;
872 : frange floats;
873 : unsupported_range unsupported;
874 : prange pointers;
875 6854236174 : buffer_type () { }
876 6976657576 : ~buffer_type () { }
877 : } m_buffer;
878 : };
879 :
880 : // The default constructor is uninitialized and must be initialized
881 : // with either set_range_class() or with an assignment into it.
882 :
883 : inline
884 3940828724 : value_range::value_range ()
885 3940828724 : : m_buffer ()
886 : {
887 3940828724 : m_vrange = NULL;
888 : }
889 :
890 : // Copy constructor.
891 :
892 : inline
893 12212538 : value_range::value_range (const value_range &r)
894 : {
895 12212538 : init (*r.m_vrange);
896 : }
897 :
898 : // Copy constructor from a vrange.
899 :
900 : inline
901 80060356 : value_range::value_range (const vrange &r)
902 : {
903 80060356 : init (r);
904 : }
905 :
906 : // Construct an UNDEFINED range that can hold ranges of TYPE. If TYPE
907 : // is not supported, default to unsupported_range.
908 :
909 : inline
910 2821081252 : value_range::value_range (tree type)
911 : {
912 2645167450 : init (type);
913 5907433 : }
914 :
915 : // Construct a range that can hold a range of [MIN, MAX], where MIN
916 : // and MAX are trees.
917 :
918 : inline
919 53304 : value_range::value_range (tree min, tree max, value_range_kind kind)
920 : {
921 53304 : init (TREE_TYPE (min));
922 53304 : m_vrange->set (min, max, kind);
923 53304 : }
924 :
925 : inline
926 6976657576 : value_range::~value_range ()
927 : {
928 6976657576 : if (m_vrange)
929 3182155602 : m_vrange->~vrange ();
930 6976657576 : }
931 :
932 : // Initialize object to an UNDEFINED range that can hold ranges of
933 : // TYPE. Clean-up memory if there was a previous object.
934 : // Note that this does *not* set the type of the underlying vrange.
935 :
936 : inline void
937 104423012 : value_range::set_range_class (tree type)
938 : {
939 104423012 : if (m_vrange)
940 8975995 : m_vrange->~vrange ();
941 104423012 : init (type);
942 104423012 : }
943 :
944 : // Initialize object to an UNDEFINED range that can hold ranges of
945 : // TYPE.
946 : // Note that this does *not* set the type of the underlying vrange.
947 :
948 : inline void
949 3239860697 : value_range::init (tree type)
950 : {
951 3239860697 : gcc_checking_assert (TYPE_P (type));
952 :
953 3239860697 : if (irange::supports_p (type))
954 2292912534 : m_vrange = new (&m_buffer.ints) int_range_max ();
955 946948163 : else if (prange::supports_p (type))
956 766790706 : m_vrange = new (&m_buffer.pointers) prange ();
957 180157457 : else if (frange::supports_p (type))
958 105972338 : m_vrange = new (&m_buffer.floats) frange ();
959 : else
960 74185119 : m_vrange = new (&m_buffer.unsupported) unsupported_range ();
961 3239860697 : }
962 :
963 : // Initialize object with a copy of R.
964 :
965 : inline void
966 127022086 : value_range::init (const vrange &r)
967 : {
968 127022086 : if (is_a <irange> (r))
969 74394841 : m_vrange = new (&m_buffer.ints) int_range_max (as_a <irange> (r));
970 52627245 : else if (is_a <prange> (r))
971 103549840 : m_vrange = new (&m_buffer.pointers) prange (as_a <prange> (r));
972 852325 : else if (is_a <frange> (r))
973 420824 : m_vrange = new (&m_buffer.floats) frange (as_a <frange> (r));
974 : else
975 1283826 : m_vrange = new (&m_buffer.unsupported)
976 641913 : unsupported_range (as_a <unsupported_range> (r));
977 127022086 : }
978 :
979 : // Assignment operator. Copying incompatible types is allowed. That
980 : // is, assigning an frange to an object holding an irange does the
981 : // right thing.
982 :
983 : inline vrange &
984 34749192 : value_range::operator= (const vrange &r)
985 : {
986 34749192 : if (m_vrange)
987 9926990 : m_vrange->~vrange ();
988 34749192 : init (r);
989 34749192 : return *m_vrange;
990 : }
991 :
992 : inline value_range &
993 9980265 : value_range::operator= (const value_range &r)
994 : {
995 : // No need to call the m_vrange destructor here, as we will do so in
996 : // the assignment below.
997 1219354 : *this = *r.m_vrange;
998 9980265 : return *this;
999 : }
1000 :
1001 : inline bool
1002 24502920 : value_range::operator== (const value_range &r) const
1003 : {
1004 24502920 : return *m_vrange == *r.m_vrange;
1005 : }
1006 :
1007 : inline bool
1008 13483266 : value_range::operator!= (const value_range &r) const
1009 : {
1010 13483266 : return *m_vrange != *r.m_vrange;
1011 : }
1012 :
1013 : inline
1014 4703303908 : value_range::operator vrange &()
1015 : {
1016 4408241880 : return *m_vrange;
1017 : }
1018 :
1019 : inline
1020 45494907 : value_range::operator const vrange &() const
1021 : {
1022 45494907 : return *m_vrange;
1023 : }
1024 :
1025 : // Return TRUE if TYPE is supported by the vrange infrastructure.
1026 :
1027 : inline bool
1028 5955043640 : value_range::supports_type_p (const_tree type)
1029 : {
1030 5955043640 : return irange::supports_p (type)
1031 1518015501 : || prange::supports_p (type)
1032 231287789 : || frange::supports_p (type);
1033 : }
1034 :
1035 : extern value_range_kind get_legacy_range (const vrange &, tree &min, tree &max);
1036 : extern void dump_value_range (FILE *, const vrange *);
1037 : extern bool vrp_operand_equal_p (const_tree, const_tree);
1038 : inline REAL_VALUE_TYPE frange_val_min (const_tree type);
1039 : inline REAL_VALUE_TYPE frange_val_max (const_tree type);
1040 :
1041 : // Number of sub-ranges in a range.
1042 :
1043 : inline unsigned
1044 33568369879 : irange::num_pairs () const
1045 : {
1046 10233975672 : return m_num_ranges;
1047 : }
1048 :
1049 : inline tree
1050 11790979002 : irange::type () const
1051 : {
1052 11790979002 : gcc_checking_assert (m_num_ranges > 0);
1053 11790979002 : return m_type;
1054 : }
1055 :
1056 : inline bool
1057 5043580825 : irange::varying_compatible_p () const
1058 : {
1059 5043580825 : if (m_num_ranges != 1)
1060 : return false;
1061 :
1062 3745584508 : const wide_int &l = m_base[0];
1063 3745584508 : const wide_int &u = m_base[1];
1064 3745584508 : tree t = m_type;
1065 :
1066 3745584508 : if (m_kind == VR_VARYING)
1067 : return true;
1068 :
1069 3493399454 : unsigned prec = TYPE_PRECISION (t);
1070 3493399454 : signop sign = TYPE_SIGN (t);
1071 3493399454 : if (INTEGRAL_TYPE_P (t) || POINTER_TYPE_P (t))
1072 6986798908 : return (l == wi::min_value (prec, sign)
1073 4561856369 : && u == wi::max_value (prec, sign)
1074 3500329421 : && m_bitmask.unknown_p ());
1075 : return true;
1076 : }
1077 :
1078 : inline bool
1079 1021047441 : vrange::varying_p () const
1080 : {
1081 1017515659 : return m_kind == VR_VARYING;
1082 : }
1083 :
1084 : inline bool
1085 20030779604 : vrange::undefined_p () const
1086 : {
1087 11503943726 : return m_kind == VR_UNDEFINED;
1088 : }
1089 :
1090 : inline bool
1091 213372997 : irange::zero_p () const
1092 : {
1093 201733649 : return (m_kind == VR_RANGE && m_num_ranges == 1
1094 392185038 : && lower_bound (0) == 0
1095 415106663 : && upper_bound (0) == 0);
1096 : }
1097 :
1098 : inline bool
1099 45649 : irange::nonzero_p () const
1100 : {
1101 45649 : if (undefined_p ())
1102 : return false;
1103 :
1104 45649 : wide_int zero = wi::zero (TYPE_PRECISION (type ()));
1105 45649 : return *this == int_range<2> (type (), zero, zero, VR_ANTI_RANGE);
1106 45649 : }
1107 :
1108 : inline bool
1109 15195085466 : irange::supports_p (const_tree type)
1110 : {
1111 14367115970 : return INTEGRAL_TYPE_P (type);
1112 : }
1113 :
1114 : inline bool
1115 69369453 : irange::contains_p (tree cst) const
1116 : {
1117 69369453 : return contains_p (wi::to_wide (cst));
1118 : }
1119 :
1120 : inline bool
1121 35329306 : range_includes_zero_p (const vrange &vr)
1122 : {
1123 35329306 : if (vr.undefined_p ())
1124 : return false;
1125 :
1126 35329306 : if (vr.varying_p ())
1127 : return true;
1128 :
1129 26732366 : return vr.contains_p (build_zero_cst (vr.type ()));
1130 : }
1131 :
1132 : // Constructors for irange
1133 :
1134 : inline
1135 5221565634 : irange::irange (wide_int *base, unsigned nranges, bool resizable)
1136 : : vrange (VR_IRANGE),
1137 5221565634 : m_resizable (resizable),
1138 5221565634 : m_max_ranges (nranges)
1139 : {
1140 5221565634 : m_base = base;
1141 5221565634 : set_undefined ();
1142 : }
1143 :
1144 : // Constructors for int_range<>.
1145 :
1146 : template<unsigned N, bool RESIZABLE>
1147 : inline
1148 3908744900 : int_range<N, RESIZABLE>::int_range ()
1149 26673237410 : : irange (m_ranges, N, RESIZABLE)
1150 : {
1151 3908744900 : }
1152 :
1153 : template<unsigned N, bool RESIZABLE>
1154 418931 : int_range<N, RESIZABLE>::int_range (const int_range &other)
1155 2932509 : : irange (m_ranges, N, RESIZABLE)
1156 : {
1157 418931 : irange::operator= (other);
1158 418931 : }
1159 :
1160 : template<unsigned N, bool RESIZABLE>
1161 : int_range<N, RESIZABLE>::int_range (tree min, tree max, value_range_kind kind)
1162 : : irange (m_ranges, N, RESIZABLE)
1163 : {
1164 : irange::set (min, max, kind);
1165 : }
1166 :
1167 : template<unsigned N, bool RESIZABLE>
1168 159498888 : int_range<N, RESIZABLE>::int_range (tree type)
1169 631444268 : : irange (m_ranges, N, RESIZABLE)
1170 : {
1171 159498888 : set_varying (type);
1172 159498888 : }
1173 :
1174 : template<unsigned N, bool RESIZABLE>
1175 770137165 : int_range<N, RESIZABLE>::int_range (tree type, const wide_int &wmin, const wide_int &wmax,
1176 : value_range_kind kind)
1177 2679707521 : : irange (m_ranges, N, RESIZABLE)
1178 : {
1179 770137165 : set (type, wmin, wmax, kind);
1180 770137165 : }
1181 :
1182 : template<unsigned N, bool RESIZABLE>
1183 382765750 : int_range<N, RESIZABLE>::int_range (const irange &other)
1184 2462360458 : : irange (m_ranges, N, RESIZABLE)
1185 : {
1186 382765750 : irange::operator= (other);
1187 382765750 : }
1188 :
1189 : template<unsigned N, bool RESIZABLE>
1190 : int_range<N, RESIZABLE>&
1191 64479560 : int_range<N, RESIZABLE>::operator= (const int_range &src)
1192 : {
1193 64472216 : irange::operator= (src);
1194 384 : return *this;
1195 : }
1196 :
1197 : inline void
1198 5591292273 : irange::set_undefined ()
1199 : {
1200 5591292273 : m_kind = VR_UNDEFINED;
1201 5226380922 : m_num_ranges = 0;
1202 369726635 : }
1203 :
1204 : inline void
1205 1206622628 : irange::set_varying (tree type)
1206 : {
1207 1206622628 : m_kind = VR_VARYING;
1208 1206622628 : m_num_ranges = 1;
1209 1206622628 : m_bitmask.set_unknown (TYPE_PRECISION (type));
1210 :
1211 1206622628 : if (INTEGRAL_TYPE_P (type) || POINTER_TYPE_P (type))
1212 : {
1213 1206622628 : m_type = type;
1214 : // Strict enum's require varying to be not TYPE_MIN/MAX, but rather
1215 : // min_value and max_value.
1216 1206622628 : m_base[0] = wi::min_value (TYPE_PRECISION (type), TYPE_SIGN (type));
1217 1206635945 : m_base[1] = wi::max_value (TYPE_PRECISION (type), TYPE_SIGN (type));
1218 : }
1219 : else
1220 0 : m_type = error_mark_node;
1221 1206622628 : }
1222 :
1223 : // Return the lower bound of a sub-range. PAIR is the sub-range in
1224 : // question.
1225 :
1226 : inline wide_int
1227 11553960534 : irange::lower_bound (unsigned pair) const
1228 : {
1229 11553960534 : gcc_checking_assert (m_num_ranges > 0);
1230 11553960534 : gcc_checking_assert (pair + 1 <= num_pairs ());
1231 11553960534 : return m_base[pair * 2];
1232 : }
1233 :
1234 : // Return the upper bound of a sub-range. PAIR is the sub-range in
1235 : // question.
1236 :
1237 : inline wide_int
1238 13223314053 : irange::upper_bound (unsigned pair) const
1239 : {
1240 13223314053 : gcc_checking_assert (m_num_ranges > 0);
1241 13223314053 : gcc_checking_assert (pair + 1 <= num_pairs ());
1242 13223314053 : return m_base[pair * 2 + 1];
1243 : }
1244 :
1245 : // Return the highest bound of a range.
1246 :
1247 : inline wide_int
1248 3560403041 : irange::upper_bound () const
1249 : {
1250 3560403041 : unsigned pairs = num_pairs ();
1251 3560403041 : gcc_checking_assert (pairs > 0);
1252 3560403041 : return upper_bound (pairs - 1);
1253 : }
1254 :
1255 : // Set value range VR to a nonzero range of type TYPE.
1256 :
1257 : inline void
1258 3675358 : irange::set_nonzero (tree type)
1259 : {
1260 3675358 : unsigned prec = TYPE_PRECISION (type);
1261 :
1262 3675358 : if (TYPE_UNSIGNED (type))
1263 : {
1264 3271182 : m_type = type;
1265 3271182 : m_kind = VR_RANGE;
1266 3271182 : m_base[0] = wi::one (prec);
1267 3271182 : m_base[1] = wi::minus_one (prec);
1268 3271182 : m_bitmask.set_unknown (prec);
1269 3271182 : m_num_ranges = 1;
1270 :
1271 3271182 : if (flag_checking)
1272 3271182 : verify_range ();
1273 : }
1274 : else
1275 : {
1276 404176 : wide_int zero = wi::zero (prec);
1277 404176 : set (type, zero, zero, VR_ANTI_RANGE);
1278 404176 : }
1279 3675358 : }
1280 :
1281 : // Set value range VR to a ZERO range of type TYPE.
1282 :
1283 : inline void
1284 3457678 : irange::set_zero (tree type)
1285 : {
1286 3457678 : wide_int zero = wi::zero (TYPE_PRECISION (type));
1287 3457678 : set (type, zero, zero);
1288 3457678 : }
1289 :
1290 : // Normalize a range to VARYING or UNDEFINED if possible.
1291 :
1292 : inline void
1293 567071477 : irange::normalize_kind ()
1294 : {
1295 567071477 : if (m_num_ranges == 0)
1296 18761 : set_undefined ();
1297 567052716 : else if (varying_compatible_p ())
1298 : {
1299 27688711 : if (m_kind == VR_RANGE)
1300 6778233 : m_kind = VR_VARYING;
1301 20910478 : else if (m_kind == VR_ANTI_RANGE)
1302 0 : set_undefined ();
1303 : }
1304 567071477 : if (flag_checking)
1305 567070686 : verify_range ();
1306 567071477 : }
1307 :
1308 : inline bool
1309 26104208 : contains_zero_p (const irange &r)
1310 : {
1311 26104208 : if (r.undefined_p ())
1312 : return false;
1313 :
1314 26104208 : wide_int zero = wi::zero (TYPE_PRECISION (r.type ()));
1315 26104208 : return r.contains_p (zero);
1316 26104208 : }
1317 :
1318 : inline wide_int
1319 93023469 : irange_val_min (const_tree type)
1320 : {
1321 93023469 : gcc_checking_assert (irange::supports_p (type));
1322 93023469 : return wi::min_value (TYPE_PRECISION (type), TYPE_SIGN (type));
1323 : }
1324 :
1325 : inline wide_int
1326 90866486 : irange_val_max (const_tree type)
1327 : {
1328 90866486 : gcc_checking_assert (irange::supports_p (type));
1329 90866486 : return wi::max_value (TYPE_PRECISION (type), TYPE_SIGN (type));
1330 : }
1331 :
1332 : inline
1333 920823619 : prange::prange ()
1334 920823619 : : vrange (VR_PRANGE)
1335 : {
1336 920823619 : set_undefined ();
1337 : }
1338 :
1339 : inline
1340 123938299 : prange::prange (const prange &r)
1341 123938299 : : vrange (VR_PRANGE)
1342 : {
1343 123938299 : *this = r;
1344 : }
1345 :
1346 : inline
1347 13225577 : prange::prange (tree type)
1348 13225577 : : vrange (VR_PRANGE)
1349 : {
1350 13225577 : set_varying (type);
1351 : }
1352 :
1353 : inline
1354 3015619 : prange::prange (tree type, const wide_int &lb, const wide_int &ub,
1355 3015619 : value_range_kind kind)
1356 3015619 : : vrange (VR_PRANGE)
1357 : {
1358 3015619 : set (type, lb, ub, kind);
1359 : }
1360 :
1361 : inline bool
1362 3737813948 : prange::supports_p (const_tree type)
1363 : {
1364 3737813948 : return POINTER_TYPE_P (type);
1365 : }
1366 :
1367 : inline bool
1368 458285418 : prange::supports_type_p (const_tree type) const
1369 : {
1370 458285418 : return POINTER_TYPE_P (type);
1371 : }
1372 :
1373 : inline void
1374 1050063833 : prange::set_undefined ()
1375 : {
1376 1050063833 : m_kind = VR_UNDEFINED;
1377 1050063833 : set_pt_unknown ();
1378 128833963 : }
1379 :
1380 : inline void
1381 474072768 : prange::set_varying (tree type)
1382 : {
1383 474072768 : m_kind = VR_VARYING;
1384 474072768 : m_type = type;
1385 474072768 : m_min = wi::zero (TYPE_PRECISION (type));
1386 474072768 : m_max = wi::max_value (TYPE_PRECISION (type), UNSIGNED);
1387 474072768 : m_bitmask.set_unknown (TYPE_PRECISION (type));
1388 474072768 : set_pt_unknown ();
1389 :
1390 474072768 : if (flag_checking)
1391 474072744 : verify_range ();
1392 474072768 : }
1393 :
1394 : inline void
1395 224188320 : prange::set_nonzero (tree type)
1396 : {
1397 224188320 : m_kind = VR_RANGE;
1398 224188320 : m_type = type;
1399 224188320 : m_min = wi::one (TYPE_PRECISION (type));
1400 224188320 : m_max = wi::max_value (TYPE_PRECISION (type), UNSIGNED);
1401 224188320 : m_bitmask.set_unknown (TYPE_PRECISION (type));
1402 224188320 : set_pt_unknown ();
1403 :
1404 224188320 : if (flag_checking)
1405 224188062 : verify_range ();
1406 224188320 : }
1407 :
1408 : inline void
1409 684165 : prange::set_zero (tree type)
1410 : {
1411 684165 : m_kind = VR_RANGE;
1412 684165 : m_type = type;
1413 684165 : wide_int zero = wi::zero (TYPE_PRECISION (type));
1414 684165 : m_min = m_max = zero;
1415 684165 : m_bitmask = irange_bitmask (zero, zero);
1416 684165 : set_pt_unknown ();
1417 :
1418 684165 : if (flag_checking)
1419 684165 : verify_range ();
1420 684165 : }
1421 :
1422 : inline bool
1423 655269 : prange::contains_p (tree cst) const
1424 : {
1425 655269 : return contains_p (wi::to_wide (cst));
1426 : }
1427 :
1428 : inline bool
1429 259915287 : prange::zero_p () const
1430 : {
1431 259915287 : bool ret = m_kind == VR_RANGE && m_min == 0 && m_max == 0;
1432 259915287 : return ret;
1433 : }
1434 :
1435 : inline bool
1436 193970576 : prange::nonzero_p () const
1437 : {
1438 193970576 : return m_kind == VR_RANGE && m_min == 1 && m_max == -1;
1439 : }
1440 :
1441 : inline tree
1442 2040017204 : prange::type () const
1443 : {
1444 2040017204 : gcc_checking_assert (!undefined_p ());
1445 2040017204 : return m_type;
1446 : }
1447 :
1448 : inline wide_int
1449 322020848 : prange::lower_bound () const
1450 : {
1451 322020848 : gcc_checking_assert (!undefined_p ());
1452 322020848 : return m_min;
1453 : }
1454 :
1455 : inline wide_int
1456 309393072 : prange::upper_bound () const
1457 : {
1458 309393072 : gcc_checking_assert (!undefined_p ());
1459 309393072 : return m_max;
1460 : }
1461 :
1462 : inline bool
1463 1497303047 : prange::varying_compatible_p () const
1464 : {
1465 1497303031 : return (!undefined_p () && m_min == 0 && m_max == -1
1466 2599023595 : && get_bitmask ().unknown_p () && pt_unknown_p ());
1467 : }
1468 :
1469 : inline irange_bitmask
1470 848898500 : prange::get_bitmask () const
1471 : {
1472 848898500 : return m_bitmask;
1473 : }
1474 :
1475 : inline bool
1476 0 : prange::fits_p (const vrange &) const
1477 : {
1478 0 : return true;
1479 : }
1480 :
1481 : // Set this range's point-to object to PTR, and POINTS_TO_P is TRUE if it
1482 : // does point to it, and FALSE if it does not point to it.
1483 :
1484 : inline void
1485 207643271 : prange::set_pt (const prange &r)
1486 : {
1487 : // Do not set points-to info if this is zero or undefined.
1488 14351103 : if (!r.pt_unknown_p () && (undefined_p () || zero_p()))
1489 : return;
1490 :
1491 207643269 : m_pt = r.m_pt;
1492 207643269 : m_points_to_p = r.m_points_to_p;
1493 :
1494 207643269 : if (r.undefined_p ())
1495 : return;
1496 : // Check whether this is now VARYING or not.
1497 207579140 : if (varying_compatible_p ())
1498 26846382 : set_varying (type ());
1499 : else
1500 180732758 : m_kind = VR_RANGE;
1501 : }
1502 :
1503 : // prange_pt methods.
1504 : // ------------------------------------------------------------------
1505 :
1506 : inline void
1507 1792833620 : prange::set_pt_unknown ()
1508 : {
1509 1792833620 : m_pt = NULL_TREE;
1510 1664989201 : m_points_to_p = false;
1511 5909 : }
1512 :
1513 : inline bool
1514 1568065799 : prange::pt_unknown_p () const
1515 : {
1516 1511218429 : return (m_pt == NULL_TREE);
1517 : }
1518 :
1519 : inline bool
1520 65918504 : prange::pt_equal_p (const prange &p) const
1521 : {
1522 65918504 : return (m_points_to_p == p.m_points_to_p && m_pt == p.m_pt);
1523 : }
1524 :
1525 : inline bool
1526 72573669 : prange::pt_inverted_p (const prange &r) const
1527 : {
1528 431960 : return m_pt && vrp_operand_equal_p (m_pt, r.m_pt)
1529 72675511 : && m_points_to_p != r.m_points_to_p;
1530 : }
1531 :
1532 : inline bool
1533 2694343 : prange::pt_invert ()
1534 : {
1535 2694343 : if (m_pt)
1536 : {
1537 0 : m_points_to_p = !m_points_to_p;
1538 0 : return true;
1539 : }
1540 : return false;
1541 : }
1542 :
1543 : inline tree
1544 83282118 : prange::pt_invariant () const
1545 : {
1546 83282118 : if (m_pt && m_points_to_p)
1547 7088 : return m_pt;
1548 : return NULL_TREE;
1549 : }
1550 :
1551 : inline tree
1552 1654098 : prange::pt_invariant_away () const
1553 : {
1554 1654098 : if (m_pt && !m_points_to_p)
1555 0 : return m_pt;
1556 : return NULL_TREE;
1557 : }
1558 :
1559 : inline bool
1560 17940805 : prange::pt_invariant_p (const prange &r) const
1561 : {
1562 185124 : if (m_pt && m_points_to_p && vrp_operand_equal_p (r.m_pt, m_pt)
1563 17955680 : && m_points_to_p == r.m_points_to_p)
1564 : return true;
1565 : return false;
1566 : }
1567 :
1568 : inline bool
1569 : prange::pt_invariant_away_p (const prange &r) const
1570 : {
1571 : if (m_pt && !m_points_to_p && vrp_operand_equal_p (r.m_pt, m_pt)
1572 : && m_points_to_p == r.m_points_to_p)
1573 : return true;
1574 : return false;
1575 : }
1576 :
1577 :
1578 : // -----------------------------------------------------------------------
1579 :
1580 : inline
1581 108525314 : frange::frange ()
1582 108525314 : : vrange (VR_FRANGE)
1583 : {
1584 108525278 : set_undefined ();
1585 : }
1586 :
1587 : inline
1588 2956792 : frange::frange (const frange &src)
1589 2956792 : : vrange (VR_FRANGE)
1590 : {
1591 2539811 : *this = src;
1592 : }
1593 :
1594 : inline
1595 784112 : frange::frange (tree type)
1596 784112 : : vrange (VR_FRANGE)
1597 : {
1598 784112 : set_varying (type);
1599 : }
1600 :
1601 : // frange constructor from REAL_VALUE_TYPE endpoints.
1602 :
1603 : inline
1604 46575790 : frange::frange (tree type,
1605 : const REAL_VALUE_TYPE &min, const REAL_VALUE_TYPE &max,
1606 46575282 : value_range_kind kind)
1607 46575790 : : vrange (VR_FRANGE)
1608 : {
1609 46575790 : set (type, min, max, kind);
1610 : }
1611 :
1612 : // frange constructor from trees.
1613 :
1614 : inline
1615 : frange::frange (tree min, tree max, value_range_kind kind)
1616 : : vrange (VR_FRANGE)
1617 : {
1618 : set (min, max, kind);
1619 : }
1620 :
1621 : inline tree
1622 70620962 : frange::type () const
1623 : {
1624 70620962 : gcc_checking_assert (!undefined_p ());
1625 70620962 : return m_type;
1626 : }
1627 :
1628 : inline void
1629 67747046 : frange::set_varying (tree type)
1630 : {
1631 67747046 : m_kind = VR_VARYING;
1632 67747046 : m_type = type;
1633 67747046 : m_min = frange_val_min (type);
1634 67747046 : m_max = frange_val_max (type);
1635 67747046 : if (HONOR_NANS (m_type))
1636 : {
1637 63904163 : m_pos_nan = true;
1638 63904163 : m_neg_nan = true;
1639 : }
1640 : else
1641 : {
1642 3842883 : m_pos_nan = false;
1643 3842883 : m_neg_nan = false;
1644 : }
1645 67747046 : }
1646 :
1647 : inline void
1648 125980473 : frange::set_undefined ()
1649 : {
1650 125980473 : m_kind = VR_UNDEFINED;
1651 125980473 : m_type = NULL;
1652 125980473 : m_pos_nan = false;
1653 125980473 : m_neg_nan = false;
1654 : // m_min and m_min are uninitialized as they are REAL_VALUE_TYPE ??.
1655 125980473 : if (flag_checking)
1656 125980473 : verify_range ();
1657 125980473 : }
1658 :
1659 : // Set the NAN bits to NAN and adjust the range.
1660 :
1661 : inline void
1662 6138610 : frange::update_nan (const nan_state &nan)
1663 : {
1664 6138610 : gcc_checking_assert (!undefined_p ());
1665 6138610 : if (HONOR_NANS (m_type))
1666 : {
1667 6138108 : m_pos_nan = nan.pos_p ();
1668 6138108 : m_neg_nan = nan.neg_p ();
1669 6138108 : normalize_kind ();
1670 6138108 : if (flag_checking)
1671 6138108 : verify_range ();
1672 : }
1673 6138610 : }
1674 :
1675 : // Set the NAN bit to +-NAN.
1676 :
1677 : inline void
1678 4063839 : frange::update_nan ()
1679 : {
1680 4063839 : gcc_checking_assert (!undefined_p ());
1681 4063839 : nan_state nan (true);
1682 4063839 : update_nan (nan);
1683 4063839 : }
1684 :
1685 : // Like above, but set the sign of the NAN.
1686 :
1687 : inline void
1688 2074771 : frange::update_nan (bool sign)
1689 : {
1690 2074771 : gcc_checking_assert (!undefined_p ());
1691 2074771 : nan_state nan (/*pos=*/!sign, /*neg=*/sign);
1692 2074771 : update_nan (nan);
1693 2074771 : }
1694 :
1695 : inline bool
1696 0 : frange::contains_p (tree cst) const
1697 : {
1698 0 : return contains_p (*TREE_REAL_CST_PTR (cst));
1699 : }
1700 :
1701 : // Clear the NAN bit and adjust the range.
1702 :
1703 : inline void
1704 14530496 : frange::clear_nan ()
1705 : {
1706 14530496 : gcc_checking_assert (!undefined_p ());
1707 14530496 : m_pos_nan = false;
1708 14530496 : m_neg_nan = false;
1709 14530496 : normalize_kind ();
1710 14530496 : if (flag_checking)
1711 14530496 : verify_range ();
1712 14530496 : }
1713 :
1714 : // Set R to maximum representable value for TYPE.
1715 :
1716 : inline REAL_VALUE_TYPE
1717 22721200 : real_max_representable (const_tree type)
1718 : {
1719 22721200 : REAL_VALUE_TYPE r;
1720 22721200 : char buf[128];
1721 22721200 : get_max_float (REAL_MODE_FORMAT (TYPE_MODE (type)),
1722 : buf, sizeof (buf), false);
1723 22721200 : int res = real_from_string (&r, buf);
1724 22721200 : gcc_checking_assert (!res);
1725 22721200 : return r;
1726 : }
1727 :
1728 : // Return the minimum representable value for TYPE.
1729 :
1730 : inline REAL_VALUE_TYPE
1731 11742439 : real_min_representable (const_tree type)
1732 : {
1733 11742439 : REAL_VALUE_TYPE r = real_max_representable (type);
1734 11742439 : r = real_value_negate (&r);
1735 11742439 : return r;
1736 : }
1737 :
1738 : // Return the minimum value for TYPE.
1739 :
1740 : inline REAL_VALUE_TYPE
1741 177245601 : frange_val_min (const_tree type)
1742 : {
1743 177245601 : if (HONOR_INFINITIES (type))
1744 166918947 : return dconstninf;
1745 : else
1746 10326654 : return real_min_representable (type);
1747 : }
1748 :
1749 : // Return the maximum value for TYPE.
1750 :
1751 : inline REAL_VALUE_TYPE
1752 124180147 : frange_val_max (const_tree type)
1753 : {
1754 124180147 : if (HONOR_INFINITIES (type))
1755 114704242 : return dconstinf;
1756 : else
1757 9475905 : return real_max_representable (type);
1758 : }
1759 :
1760 : // Return TRUE if R is the minimum value for TYPE.
1761 :
1762 : inline bool
1763 106074880 : frange_val_is_min (const REAL_VALUE_TYPE &r, const_tree type)
1764 : {
1765 106074880 : REAL_VALUE_TYPE min = frange_val_min (type);
1766 106074880 : return real_identical (&min, &r);
1767 : }
1768 :
1769 : // Return TRUE if R is the max value for TYPE.
1770 :
1771 : inline bool
1772 52615227 : frange_val_is_max (const REAL_VALUE_TYPE &r, const_tree type)
1773 : {
1774 52615227 : REAL_VALUE_TYPE max = frange_val_max (type);
1775 52615227 : return real_identical (&max, &r);
1776 : }
1777 :
1778 : // Build a NAN with a state of NAN.
1779 :
1780 : inline void
1781 333492 : frange::set_nan (tree type, const nan_state &nan)
1782 : {
1783 333492 : gcc_checking_assert (nan.pos_p () || nan.neg_p ());
1784 333492 : if (HONOR_NANS (type))
1785 : {
1786 333491 : m_kind = VR_NAN;
1787 333491 : m_type = type;
1788 333491 : m_neg_nan = nan.neg_p ();
1789 333491 : m_pos_nan = nan.pos_p ();
1790 333491 : if (flag_checking)
1791 333491 : verify_range ();
1792 : }
1793 : else
1794 1 : set_undefined ();
1795 333492 : }
1796 :
1797 : // Build a signless NAN of type TYPE.
1798 :
1799 : inline void
1800 149061 : frange::set_nan (tree type)
1801 : {
1802 149061 : nan_state nan (true);
1803 149049 : set_nan (type, nan);
1804 127848 : }
1805 :
1806 : // Build a NAN of type TYPE with SIGN.
1807 :
1808 : inline void
1809 184428 : frange::set_nan (tree type, bool sign)
1810 : {
1811 184428 : nan_state nan (/*pos=*/!sign, /*neg=*/sign);
1812 184424 : set_nan (type, nan);
1813 21692 : }
1814 :
1815 : // Return TRUE if range is known to be finite.
1816 :
1817 : inline bool
1818 0 : frange::known_isfinite () const
1819 : {
1820 0 : if (undefined_p () || varying_p () || m_kind == VR_ANTI_RANGE)
1821 : return false;
1822 0 : return (!maybe_isnan () && !real_isinf (&m_min) && !real_isinf (&m_max));
1823 : }
1824 :
1825 : // Return TRUE if range is known to be normal.
1826 :
1827 : inline bool
1828 0 : frange::known_isnormal () const
1829 : {
1830 0 : if (!known_isfinite ())
1831 : return false;
1832 :
1833 0 : machine_mode mode = TYPE_MODE (type ());
1834 0 : return (!real_isdenormal (&m_min, mode) && !real_isdenormal (&m_max, mode)
1835 0 : && !real_iszero (&m_min) && !real_iszero (&m_max)
1836 0 : && (!real_isneg (&m_min) || real_isneg (&m_max)));
1837 : }
1838 :
1839 : // Return TRUE if range is known to be denormal.
1840 :
1841 : inline bool
1842 0 : frange::known_isdenormal_or_zero () const
1843 : {
1844 0 : if (!known_isfinite ())
1845 : return false;
1846 :
1847 0 : machine_mode mode = TYPE_MODE (type ());
1848 0 : return ((real_isdenormal (&m_min, mode) || real_iszero (&m_min))
1849 0 : && (real_isdenormal (&m_max, mode) || real_iszero (&m_max)));
1850 : }
1851 :
1852 : // Return TRUE if range may be infinite.
1853 :
1854 : inline bool
1855 34171 : frange::maybe_isinf () const
1856 : {
1857 34171 : if (undefined_p () || m_kind == VR_ANTI_RANGE || m_kind == VR_NAN)
1858 : return false;
1859 34171 : if (varying_p ())
1860 : return true;
1861 32133 : return real_isinf (&m_min) || real_isinf (&m_max);
1862 : }
1863 :
1864 : // Return TRUE if range is known to be the [-INF,-INF] or [+INF,+INF].
1865 :
1866 : inline bool
1867 5790532 : frange::known_isinf () const
1868 : {
1869 5790532 : return (m_kind == VR_RANGE
1870 8272158 : && !maybe_isnan ()
1871 1240804 : && real_identical (&m_min, &m_max)
1872 5808942 : && real_isinf (&m_min));
1873 : }
1874 :
1875 : // Return TRUE if range is possibly a NAN.
1876 :
1877 : inline bool
1878 22926471 : frange::maybe_isnan () const
1879 : {
1880 21219749 : if (undefined_p ())
1881 : return false;
1882 22921956 : return m_pos_nan || m_neg_nan;
1883 : }
1884 :
1885 : // Return TRUE if range is possibly a NAN with SIGN.
1886 :
1887 : inline bool
1888 157293 : frange::maybe_isnan (bool sign) const
1889 : {
1890 157293 : if (undefined_p ())
1891 : return false;
1892 157293 : if (sign)
1893 157293 : return m_neg_nan;
1894 : return m_pos_nan;
1895 : }
1896 :
1897 : // Return TRUE if range is a +NAN or -NAN.
1898 :
1899 : inline bool
1900 17199081 : frange::known_isnan () const
1901 : {
1902 13119468 : return m_kind == VR_NAN;
1903 : }
1904 :
1905 : // If the signbit for the range is known, set it in SIGNBIT and return
1906 : // TRUE.
1907 :
1908 : inline bool
1909 1709075 : frange::signbit_p (bool &signbit) const
1910 : {
1911 1709075 : if (undefined_p ())
1912 : return false;
1913 :
1914 : // NAN with unknown sign.
1915 1709057 : if (m_pos_nan && m_neg_nan)
1916 : return false;
1917 : // No NAN.
1918 106515 : if (!m_pos_nan && !m_neg_nan)
1919 : {
1920 86230 : if (m_min.sign == m_max.sign)
1921 : {
1922 11711 : signbit = m_min.sign;
1923 11711 : return true;
1924 : }
1925 : return false;
1926 : }
1927 : // NAN with known sign.
1928 20285 : bool nan_sign = m_neg_nan;
1929 20285 : if (known_isnan ()
1930 20285 : || (nan_sign == m_min.sign && nan_sign == m_max.sign))
1931 : {
1932 18959 : signbit = nan_sign;
1933 18959 : return true;
1934 : }
1935 : return false;
1936 : }
1937 :
1938 : // If range has a NAN with a known sign, set it in SIGNBIT and return
1939 : // TRUE.
1940 :
1941 : inline bool
1942 53779 : frange::nan_signbit_p (bool &signbit) const
1943 : {
1944 53779 : if (undefined_p ())
1945 : return false;
1946 :
1947 53779 : if (m_pos_nan == m_neg_nan)
1948 : return false;
1949 :
1950 2528 : signbit = m_neg_nan;
1951 2528 : return true;
1952 : }
1953 :
1954 : void frange_nextafter (enum machine_mode, REAL_VALUE_TYPE &,
1955 : const REAL_VALUE_TYPE &);
1956 : void frange_arithmetic (enum tree_code, tree, REAL_VALUE_TYPE &,
1957 : const REAL_VALUE_TYPE &, const REAL_VALUE_TYPE &,
1958 : const REAL_VALUE_TYPE &);
1959 :
1960 : // Return true if TYPE1 and TYPE2 are compatible range types.
1961 :
1962 : inline bool
1963 1608458607 : range_compatible_p (tree type1, tree type2)
1964 : {
1965 : // types_compatible_p requires conversion in both directions to be useless.
1966 : // GIMPLE only requires a cast one way in order to be compatible.
1967 : // Ranges really only need the sign and precision to be the same.
1968 1608458607 : return (TYPE_PRECISION (type1) == TYPE_PRECISION (type2)
1969 1608458607 : && TYPE_SIGN (type1) == TYPE_SIGN (type2));
1970 : }
1971 : #endif // GCC_VALUE_RANGE_H
|
