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 5127422411 : 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 13957148 : bool operator!= (const vrange &r) const { return !(*this == r); }
123 : void dump (FILE *) const;
124 0 : virtual void verify_range () const { }
125 : protected:
126 6457604024 : 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 6221536091 : 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 1505654826 : wide_int value () const { return m_value; }
158 1817680739 : 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 7598455 : 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 3387559150 : irange_bitmask::set_unknown (unsigned prec)
182 : {
183 3387559150 : m_value = wi::zero (prec);
184 3387559150 : m_mask = wi::minus_one (prec);
185 3387559150 : if (flag_checking)
186 3387545972 : verify_mask ();
187 3387559150 : }
188 :
189 : // Return TRUE if THIS does not have any meaningful information.
190 :
191 : inline bool
192 4967827973 : irange_bitmask::unknown_p () const
193 : {
194 2299527685 : return m_mask == -1;
195 : }
196 :
197 : inline
198 1122731918 : irange_bitmask::irange_bitmask (const wide_int &value, const wide_int &mask)
199 : {
200 1122731918 : m_value = value;
201 1122731918 : m_mask = mask;
202 1122731918 : if (flag_checking)
203 1122728228 : verify_mask ();
204 1122731918 : }
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 4031 : irange_bitmask::get_nonzero_bits () const
219 : {
220 4031 : 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 246648818 : irange_bitmask::member_p (const wide_int &val) const
237 : {
238 246648818 : if (unknown_p ())
239 : return true;
240 29404786 : wide_int res = m_mask & val;
241 29404786 : if (m_value != 0)
242 828522 : res |= ~m_mask & m_value;
243 29404786 : return res == val;
244 29404786 : }
245 :
246 : inline bool
247 1190342999 : irange_bitmask::operator== (const irange_bitmask &src) const
248 : {
249 1190342999 : bool unknown1 = unknown_p ();
250 1190342999 : bool unknown2 = src.unknown_p ();
251 1190342999 : if (unknown1 || unknown2)
252 906829852 : return unknown1 == unknown2;
253 283513147 : return m_value == src.m_value && m_mask == src.m_mask;
254 : }
255 :
256 : inline void
257 18404313 : irange_bitmask::union_ (const irange_bitmask &src)
258 : {
259 18404369 : m_mask = (m_mask | src.m_mask) | (m_value ^ src.m_value);
260 18404313 : m_value = m_value & src.m_value;
261 18404313 : if (flag_checking)
262 18404313 : verify_mask ();
263 18404313 : }
264 :
265 : // Return FALSE if the bitmask intersection is undefined.
266 :
267 : inline bool
268 786501934 : 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 1573008058 : if (wi::bit_and (~(m_mask | src.m_mask),
273 2359505802 : m_value ^ src.m_value) != 0)
274 : return false;
275 : else
276 : {
277 786458011 : m_mask = m_mask & src.m_mask;
278 786458011 : m_value = m_value | src.m_value;
279 : }
280 786458011 : if (flag_checking)
281 786455510 : 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 10148371920 : 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 70808008 : unsupported_range ()
504 70808008 : : vrange (VR_UNKNOWN)
505 : {
506 70808008 : set_undefined ();
507 : }
508 741474 : unsupported_range (const unsupported_range &src)
509 741474 : : vrange (VR_UNKNOWN)
510 : {
511 741474 : 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 65880265 : nan_state::nan_state (bool nan_p)
555 : {
556 65880265 : m_pos_nan = nan_p;
557 61482317 : 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 3931976 : nan_state::nan_state (bool pos_nan, bool neg_nan)
566 : {
567 3931976 : m_pos_nan = pos_nan;
568 3922211 : m_neg_nan = neg_nan;
569 : }
570 :
571 : // Return if +NAN is possible.
572 :
573 : inline bool
574 36439682 : nan_state::pos_p () const
575 : {
576 36439658 : return m_pos_nan;
577 : }
578 :
579 : // Return if -NAN is possible.
580 :
581 : inline bool
582 36271517 : nan_state::neg_p () const
583 : {
584 36271493 : 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 51176156 : 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 500008178 : 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 500008178 : 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 21180372 : frange::lower_bound () const
680 : {
681 21180372 : gcc_checking_assert (!undefined_p () && !known_isnan ());
682 21180372 : return m_min;
683 : }
684 :
685 : inline const REAL_VALUE_TYPE &
686 19763442 : frange::upper_bound () const
687 : {
688 19763442 : gcc_checking_assert (!undefined_p () && !known_isnan ());
689 19763442 : return m_max;
690 : }
691 :
692 : // Return the NAN state.
693 :
694 : inline nan_state
695 1781050 : frange::get_nan_state () const
696 : {
697 1781050 : 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 4254647185 : is_a (const vrange &v)
714 : {
715 : // Reuse is_a <vrange> to implement the const version.
716 4452924219 : const T &derived = static_cast<const T &> (v);
717 1934619975 : return is_a <T> (const_cast<T &> (derived));
718 : }
719 :
720 : template <typename T>
721 : inline T &
722 2534420239 : as_a (vrange &v)
723 : {
724 0 : gcc_checking_assert (is_a <T> (v));
725 2534420239 : return static_cast <T &> (v);
726 : }
727 :
728 : template <typename T>
729 : inline const T &
730 3645540555 : as_a (const vrange &v)
731 : {
732 0 : gcc_checking_assert (is_a <T> (v));
733 3645540555 : return static_cast <const T &> (v);
734 : }
735 :
736 : // Specializations for the different range types.
737 :
738 : template <>
739 : inline bool
740 7262989916 : is_a <irange> (vrange &v)
741 : {
742 7140006639 : return v.m_discriminator == VR_IRANGE;
743 : }
744 :
745 : template <>
746 : inline bool
747 1426926151 : is_a <prange> (vrange &v)
748 : {
749 1288401296 : return v.m_discriminator == VR_PRANGE;
750 : }
751 :
752 : template <>
753 : inline bool
754 192689828 : is_a <frange> (vrange &v)
755 : {
756 192689828 : return v.m_discriminator == VR_FRANGE;
757 : }
758 :
759 : template <>
760 : inline bool
761 741474 : is_a <unsupported_range> (vrange &v)
762 : {
763 741474 : 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 1312847437 : irange::maybe_resize (int needed)
771 : {
772 1312847437 : if (!m_resizable || m_max_ranges == HARD_MAX_RANGES)
773 : return;
774 :
775 854428388 : if (needed > m_max_ranges)
776 : {
777 63639403 : m_max_ranges = HARD_MAX_RANGES;
778 32519734933 : wide_int *newmem = new wide_int[m_max_ranges * 2];
779 63639403 : unsigned n = num_pairs () * 2;
780 364017835 : for (unsigned i = 0; i < n; ++i)
781 300378432 : newmem[i] = m_base[i];
782 63639403 : m_base = newmem;
783 : }
784 : }
785 :
786 : template<unsigned N, bool RESIZABLE>
787 : inline
788 5074185960 : int_range<N, RESIZABLE>::~int_range ()
789 : {
790 3800340165 : if (RESIZABLE && m_base != m_ranges)
791 32519734933 : delete[] m_base;
792 31579072053 : }
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 40630 : 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 3331468 : tree type () { return m_vrange->type (); }
844 153204100 : bool varying_p () const { return m_vrange->varying_p (); }
845 130378316 : bool undefined_p () const { return m_vrange->undefined_p (); }
846 305359013 : void set_varying (tree type) { init (type); m_vrange->set_varying (type); }
847 22881067 : void set_undefined () { m_vrange->set_undefined (); }
848 18503969 : bool union_ (const vrange &r) { return m_vrange->union_ (r); }
849 95434680 : bool intersect (const vrange &r) { return m_vrange->intersect (r); }
850 1371789 : bool contains_p (tree cst) const { return m_vrange->contains_p (cst); }
851 332382804 : bool singleton_p (tree *result = NULL) const
852 332382804 : { 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 248550 : bool nonzero_p () const { return m_vrange->nonzero_p (); }
857 4456 : bool zero_p () const { return m_vrange->zero_p (); }
858 10829931 : tree lbound () const { return m_vrange->lbound (); }
859 344428 : tree ubound () const { return m_vrange->ubound (); }
860 509442 : irange_bitmask get_bitmask () const { return m_vrange->get_bitmask (); }
861 1351516 : void update_bitmask (const class irange_bitmask &bm)
862 1351516 : { 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 6640061889 : buffer_type () { }
876 6758950627 : ~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 3713985422 : value_range::value_range ()
885 3713985422 : : m_buffer ()
886 : {
887 3713985422 : m_vrange = NULL;
888 : }
889 :
890 : // Copy constructor.
891 :
892 : inline
893 11938843 : value_range::value_range (const value_range &r)
894 : {
895 11938843 : init (*r.m_vrange);
896 : }
897 :
898 : // Copy constructor from a vrange.
899 :
900 : inline
901 77653942 : value_range::value_range (const vrange &r)
902 : {
903 77653942 : 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 2836430274 : value_range::value_range (tree type)
911 : {
912 2658023822 : init (type);
913 5867262 : }
914 :
915 : // Construct a range that can hold a range of [MIN, MAX], where MIN
916 : // and MAX are trees.
917 :
918 : inline
919 53408 : value_range::value_range (tree min, tree max, value_range_kind kind)
920 : {
921 53408 : init (TREE_TYPE (min));
922 53408 : m_vrange->set (min, max, kind);
923 53408 : }
924 :
925 : inline
926 6758950627 : value_range::~value_range ()
927 : {
928 6758950627 : if (m_vrange)
929 3185538464 : m_vrange->~vrange ();
930 6758950627 : }
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 99478298 : value_range::set_range_class (tree type)
938 : {
939 99478298 : if (m_vrange)
940 8706175 : m_vrange->~vrange ();
941 99478298 : init (type);
942 99478298 : }
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 3241320993 : value_range::init (tree type)
950 : {
951 3241320993 : gcc_checking_assert (TYPE_P (type));
952 :
953 3241320993 : if (irange::supports_p (type))
954 2310304175 : m_vrange = new (&m_buffer.ints) int_range_max ();
955 931016818 : else if (prange::supports_p (type))
956 749433681 : m_vrange = new (&m_buffer.pointers) prange ();
957 181583137 : else if (frange::supports_p (type))
958 110775129 : m_vrange = new (&m_buffer.floats) frange ();
959 : else
960 70808008 : m_vrange = new (&m_buffer.unsupported) unsupported_range ();
961 3241320993 : }
962 :
963 : // Initialize object with a copy of R.
964 :
965 : inline void
966 122545306 : value_range::init (const vrange &r)
967 : {
968 122545306 : if (is_a <irange> (r))
969 72510656 : m_vrange = new (&m_buffer.ints) int_range_max (as_a <irange> (r));
970 50034650 : else if (is_a <prange> (r))
971 98215494 : m_vrange = new (&m_buffer.pointers) prange (as_a <prange> (r));
972 926903 : else if (is_a <frange> (r))
973 370858 : m_vrange = new (&m_buffer.floats) frange (as_a <frange> (r));
974 : else
975 1482948 : m_vrange = new (&m_buffer.unsupported)
976 741474 : unsupported_range (as_a <unsupported_range> (r));
977 122545306 : }
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 32952521 : value_range::operator= (const vrange &r)
985 : {
986 32952521 : if (m_vrange)
987 9250019 : m_vrange->~vrange ();
988 32952521 : init (r);
989 32952521 : return *m_vrange;
990 : }
991 :
992 : inline value_range &
993 9303395 : 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 1166911 : *this = *r.m_vrange;
998 9303395 : return *this;
999 : }
1000 :
1001 : inline bool
1002 23945743 : value_range::operator== (const value_range &r) const
1003 : {
1004 23945743 : return *m_vrange == *r.m_vrange;
1005 : }
1006 :
1007 : inline bool
1008 13465801 : value_range::operator!= (const value_range &r) const
1009 : {
1010 13465801 : return *m_vrange != *r.m_vrange;
1011 : }
1012 :
1013 : inline
1014 4662837872 : value_range::operator vrange &()
1015 : {
1016 4368027149 : return *m_vrange;
1017 : }
1018 :
1019 : inline
1020 43521936 : value_range::operator const vrange &() const
1021 : {
1022 43521936 : return *m_vrange;
1023 : }
1024 :
1025 : // Return TRUE if TYPE is supported by the vrange infrastructure.
1026 :
1027 : inline bool
1028 5848416226 : value_range::supports_type_p (const_tree type)
1029 : {
1030 5848416226 : return irange::supports_p (type)
1031 1481971378 : || prange::supports_p (type)
1032 234013646 : || 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 33224008828 : irange::num_pairs () const
1045 : {
1046 10139344614 : return m_num_ranges;
1047 : }
1048 :
1049 : inline tree
1050 11639174142 : irange::type () const
1051 : {
1052 11639174142 : gcc_checking_assert (m_num_ranges > 0);
1053 11639174142 : return m_type;
1054 : }
1055 :
1056 : inline bool
1057 4979497486 : irange::varying_compatible_p () const
1058 : {
1059 4979497486 : if (m_num_ranges != 1)
1060 : return false;
1061 :
1062 3690427201 : const wide_int &l = m_base[0];
1063 3690427201 : const wide_int &u = m_base[1];
1064 3690427201 : tree t = m_type;
1065 :
1066 3690427201 : if (m_kind == VR_VARYING)
1067 : return true;
1068 :
1069 3441921471 : unsigned prec = TYPE_PRECISION (t);
1070 3441921471 : signop sign = TYPE_SIGN (t);
1071 3441921471 : if (INTEGRAL_TYPE_P (t) || POINTER_TYPE_P (t))
1072 6883842942 : return (l == wi::min_value (prec, sign)
1073 4483032197 : && u == wi::max_value (prec, sign)
1074 3448641486 : && m_bitmask.unknown_p ());
1075 : return true;
1076 : }
1077 :
1078 : inline bool
1079 1012365647 : vrange::varying_p () const
1080 : {
1081 1009081854 : return m_kind == VR_VARYING;
1082 : }
1083 :
1084 : inline bool
1085 19688632575 : vrange::undefined_p () const
1086 : {
1087 11354993449 : return m_kind == VR_UNDEFINED;
1088 : }
1089 :
1090 : inline bool
1091 210019264 : irange::zero_p () const
1092 : {
1093 198125518 : return (m_kind == VR_RANGE && m_num_ranges == 1
1094 384650662 : && lower_bound (0) == 0
1095 408144801 : && upper_bound (0) == 0);
1096 : }
1097 :
1098 : inline bool
1099 45673 : irange::nonzero_p () const
1100 : {
1101 45673 : if (undefined_p ())
1102 : return false;
1103 :
1104 45673 : wide_int zero = wi::zero (TYPE_PRECISION (type ()));
1105 45673 : return *this == int_range<2> (type (), zero, zero, VR_ANTI_RANGE);
1106 45673 : }
1107 :
1108 : inline bool
1109 15012636050 : irange::supports_p (const_tree type)
1110 : {
1111 14193128704 : return INTEGRAL_TYPE_P (type);
1112 : }
1113 :
1114 : inline bool
1115 67813699 : irange::contains_p (tree cst) const
1116 : {
1117 67813699 : return contains_p (wi::to_wide (cst));
1118 : }
1119 :
1120 : inline bool
1121 35370050 : range_includes_zero_p (const vrange &vr)
1122 : {
1123 35370050 : if (vr.undefined_p ())
1124 : return false;
1125 :
1126 35370050 : if (vr.varying_p ())
1127 : return true;
1128 :
1129 26483083 : return vr.contains_p (build_zero_cst (vr.type ()));
1130 : }
1131 :
1132 : // Constructors for irange
1133 :
1134 : inline
1135 5189267760 : irange::irange (wide_int *base, unsigned nranges, bool resizable)
1136 : : vrange (VR_IRANGE),
1137 5189267760 : m_resizable (resizable),
1138 5189267760 : m_max_ranges (nranges)
1139 : {
1140 5189267760 : m_base = base;
1141 5189267760 : set_undefined ();
1142 : }
1143 :
1144 : // Constructors for int_range<>.
1145 :
1146 : template<unsigned N, bool RESIZABLE>
1147 : inline
1148 3901381974 : int_range<N, RESIZABLE>::int_range ()
1149 26640751134 : : irange (m_ranges, N, RESIZABLE)
1150 : {
1151 3901381974 : }
1152 :
1153 : template<unsigned N, bool RESIZABLE>
1154 409555 : int_range<N, RESIZABLE>::int_range (const int_range &other)
1155 2866877 : : irange (m_ranges, N, RESIZABLE)
1156 : {
1157 409555 : irange::operator= (other);
1158 409555 : }
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 156073547 : int_range<N, RESIZABLE>::int_range (tree type)
1169 623668769 : : irange (m_ranges, N, RESIZABLE)
1170 : {
1171 156073547 : set_varying (type);
1172 156073547 : }
1173 :
1174 : template<unsigned N, bool RESIZABLE>
1175 755793578 : int_range<N, RESIZABLE>::int_range (tree type, const wide_int &wmin, const wide_int &wmax,
1176 : value_range_kind kind)
1177 2636278768 : : irange (m_ranges, N, RESIZABLE)
1178 : {
1179 755793578 : set (type, wmin, wmax, kind);
1180 755793578 : }
1181 :
1182 : template<unsigned N, bool RESIZABLE>
1183 375609106 : int_range<N, RESIZABLE>::int_range (const irange &other)
1184 2417439694 : : irange (m_ranges, N, RESIZABLE)
1185 : {
1186 375609106 : irange::operator= (other);
1187 375609106 : }
1188 :
1189 : template<unsigned N, bool RESIZABLE>
1190 : int_range<N, RESIZABLE>&
1191 63689740 : int_range<N, RESIZABLE>::operator= (const int_range &src)
1192 : {
1193 63682098 : irange::operator= (src);
1194 384 : return *this;
1195 : }
1196 :
1197 : inline void
1198 5558744029 : irange::set_undefined ()
1199 : {
1200 5558744029 : m_kind = VR_UNDEFINED;
1201 5193954895 : m_num_ranges = 0;
1202 369476265 : }
1203 :
1204 : inline void
1205 1192057783 : irange::set_varying (tree type)
1206 : {
1207 1192057783 : m_kind = VR_VARYING;
1208 1192057783 : m_num_ranges = 1;
1209 1192057783 : m_bitmask.set_unknown (TYPE_PRECISION (type));
1210 :
1211 1192057783 : if (INTEGRAL_TYPE_P (type) || POINTER_TYPE_P (type))
1212 : {
1213 1192057783 : m_type = type;
1214 : // Strict enum's require varying to be not TYPE_MIN/MAX, but rather
1215 : // min_value and max_value.
1216 1192057783 : m_base[0] = wi::min_value (TYPE_PRECISION (type), TYPE_SIGN (type));
1217 1192071107 : m_base[1] = wi::max_value (TYPE_PRECISION (type), TYPE_SIGN (type));
1218 : }
1219 : else
1220 0 : m_type = error_mark_node;
1221 1192057783 : }
1222 :
1223 : // Return the lower bound of a sub-range. PAIR is the sub-range in
1224 : // question.
1225 :
1226 : inline wide_int
1227 11431690128 : irange::lower_bound (unsigned pair) const
1228 : {
1229 11431690128 : gcc_checking_assert (m_num_ranges > 0);
1230 11431690128 : gcc_checking_assert (pair + 1 <= num_pairs ());
1231 11431690128 : 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 13098048433 : irange::upper_bound (unsigned pair) const
1239 : {
1240 13098048433 : gcc_checking_assert (m_num_ranges > 0);
1241 13098048433 : gcc_checking_assert (pair + 1 <= num_pairs ());
1242 13098048433 : return m_base[pair * 2 + 1];
1243 : }
1244 :
1245 : // Return the highest bound of a range.
1246 :
1247 : inline wide_int
1248 3533555239 : irange::upper_bound () const
1249 : {
1250 3533555239 : unsigned pairs = num_pairs ();
1251 3533555239 : gcc_checking_assert (pairs > 0);
1252 3533555239 : return upper_bound (pairs - 1);
1253 : }
1254 :
1255 : // Set value range VR to a nonzero range of type TYPE.
1256 :
1257 : inline void
1258 3580757 : irange::set_nonzero (tree type)
1259 : {
1260 3580757 : unsigned prec = TYPE_PRECISION (type);
1261 :
1262 3580757 : if (TYPE_UNSIGNED (type))
1263 : {
1264 3178870 : m_type = type;
1265 3178870 : m_kind = VR_RANGE;
1266 3178870 : m_base[0] = wi::one (prec);
1267 3178870 : m_base[1] = wi::minus_one (prec);
1268 3178870 : m_bitmask.set_unknown (prec);
1269 3178870 : m_num_ranges = 1;
1270 :
1271 3178870 : if (flag_checking)
1272 3178870 : verify_range ();
1273 : }
1274 : else
1275 : {
1276 401887 : wide_int zero = wi::zero (prec);
1277 401887 : set (type, zero, zero, VR_ANTI_RANGE);
1278 401887 : }
1279 3580757 : }
1280 :
1281 : // Set value range VR to a ZERO range of type TYPE.
1282 :
1283 : inline void
1284 3454191 : irange::set_zero (tree type)
1285 : {
1286 3454191 : wide_int zero = wi::zero (TYPE_PRECISION (type));
1287 3454191 : set (type, zero, zero);
1288 3454191 : }
1289 :
1290 : // Normalize a range to VARYING or UNDEFINED if possible.
1291 :
1292 : inline void
1293 559981568 : irange::normalize_kind ()
1294 : {
1295 559981568 : if (m_num_ranges == 0)
1296 18888 : set_undefined ();
1297 559962680 : else if (varying_compatible_p ())
1298 : {
1299 26802809 : if (m_kind == VR_RANGE)
1300 6569777 : m_kind = VR_VARYING;
1301 20233032 : else if (m_kind == VR_ANTI_RANGE)
1302 0 : set_undefined ();
1303 : }
1304 559981568 : if (flag_checking)
1305 559980772 : verify_range ();
1306 559981568 : }
1307 :
1308 : inline bool
1309 25775516 : contains_zero_p (const irange &r)
1310 : {
1311 25775516 : if (r.undefined_p ())
1312 : return false;
1313 :
1314 25775516 : wide_int zero = wi::zero (TYPE_PRECISION (r.type ()));
1315 25775516 : return r.contains_p (zero);
1316 25775516 : }
1317 :
1318 : inline wide_int
1319 90604925 : irange_val_min (const_tree type)
1320 : {
1321 90604925 : gcc_checking_assert (irange::supports_p (type));
1322 90604925 : return wi::min_value (TYPE_PRECISION (type), TYPE_SIGN (type));
1323 : }
1324 :
1325 : inline wide_int
1326 88181942 : irange_val_max (const_tree type)
1327 : {
1328 88181942 : gcc_checking_assert (irange::supports_p (type));
1329 88181942 : return wi::max_value (TYPE_PRECISION (type), TYPE_SIGN (type));
1330 : }
1331 :
1332 : inline
1333 897585828 : prange::prange ()
1334 897585828 : : vrange (VR_PRANGE)
1335 : {
1336 897585828 : set_undefined ();
1337 : }
1338 :
1339 : inline
1340 118849415 : prange::prange (const prange &r)
1341 118849415 : : vrange (VR_PRANGE)
1342 : {
1343 118849415 : *this = r;
1344 : }
1345 :
1346 : inline
1347 12781709 : prange::prange (tree type)
1348 12781709 : : vrange (VR_PRANGE)
1349 : {
1350 12781709 : set_varying (type);
1351 : }
1352 :
1353 : inline
1354 2967816 : prange::prange (tree type, const wide_int &lb, const wide_int &ub,
1355 2967816 : value_range_kind kind)
1356 2967816 : : vrange (VR_PRANGE)
1357 : {
1358 2967816 : set (type, lb, ub, kind);
1359 : }
1360 :
1361 : inline bool
1362 3639415296 : prange::supports_p (const_tree type)
1363 : {
1364 3639415296 : return POINTER_TYPE_P (type);
1365 : }
1366 :
1367 : inline bool
1368 443966483 : prange::supports_type_p (const_tree type) const
1369 : {
1370 443966483 : return POINTER_TYPE_P (type);
1371 : }
1372 :
1373 : inline void
1374 1024569465 : prange::set_undefined ()
1375 : {
1376 1024569465 : m_kind = VR_UNDEFINED;
1377 1024569465 : set_pt_unknown ();
1378 126583004 : }
1379 :
1380 : inline void
1381 456812537 : prange::set_varying (tree type)
1382 : {
1383 456812537 : m_kind = VR_VARYING;
1384 456812537 : m_type = type;
1385 456812537 : m_min = wi::zero (TYPE_PRECISION (type));
1386 456812537 : m_max = wi::max_value (TYPE_PRECISION (type), UNSIGNED);
1387 456812537 : m_bitmask.set_unknown (TYPE_PRECISION (type));
1388 456812537 : set_pt_unknown ();
1389 :
1390 456812537 : if (flag_checking)
1391 456812513 : verify_range ();
1392 456812537 : }
1393 :
1394 : inline void
1395 215199440 : prange::set_nonzero (tree type)
1396 : {
1397 215199440 : m_kind = VR_RANGE;
1398 215199440 : m_type = type;
1399 215199440 : m_min = wi::one (TYPE_PRECISION (type));
1400 215199440 : m_max = wi::max_value (TYPE_PRECISION (type), UNSIGNED);
1401 215199440 : m_bitmask.set_unknown (TYPE_PRECISION (type));
1402 215199440 : set_pt_unknown ();
1403 :
1404 215199440 : if (flag_checking)
1405 215199182 : verify_range ();
1406 215199440 : }
1407 :
1408 : inline void
1409 658698 : prange::set_zero (tree type)
1410 : {
1411 658698 : m_kind = VR_RANGE;
1412 658698 : m_type = type;
1413 658698 : wide_int zero = wi::zero (TYPE_PRECISION (type));
1414 658698 : m_min = m_max = zero;
1415 658698 : m_bitmask = irange_bitmask (zero, zero);
1416 658698 : set_pt_unknown ();
1417 :
1418 658698 : if (flag_checking)
1419 658698 : verify_range ();
1420 658698 : }
1421 :
1422 : inline bool
1423 550712 : prange::contains_p (tree cst) const
1424 : {
1425 550712 : return contains_p (wi::to_wide (cst));
1426 : }
1427 :
1428 : inline bool
1429 126750758 : prange::zero_p () const
1430 : {
1431 126750758 : bool ret = m_kind == VR_RANGE && m_min == 0 && m_max == 0;
1432 : // if zero_p is true, there should be no points to info.
1433 123750627 : gcc_checking_assert (!ret || pt_unknown_p ());
1434 126750758 : return ret;
1435 : }
1436 :
1437 : inline bool
1438 184223937 : prange::nonzero_p () const
1439 : {
1440 184223937 : return m_kind == VR_RANGE && m_min == 1 && m_max == -1;
1441 : }
1442 :
1443 : inline tree
1444 1973231528 : prange::type () const
1445 : {
1446 1973231528 : gcc_checking_assert (!undefined_p ());
1447 1973231528 : return m_type;
1448 : }
1449 :
1450 : inline wide_int
1451 310965785 : prange::lower_bound () const
1452 : {
1453 310965785 : gcc_checking_assert (!undefined_p ());
1454 310965785 : return m_min;
1455 : }
1456 :
1457 : inline wide_int
1458 298893101 : prange::upper_bound () const
1459 : {
1460 298893101 : gcc_checking_assert (!undefined_p ());
1461 298893101 : return m_max;
1462 : }
1463 :
1464 : inline bool
1465 1442233476 : prange::varying_compatible_p () const
1466 : {
1467 1442233460 : return (!undefined_p () && m_min == 0 && m_max == -1
1468 2505583252 : && get_bitmask ().unknown_p () && pt_unknown_p ());
1469 : }
1470 :
1471 : inline irange_bitmask
1472 816005541 : prange::get_bitmask () const
1473 : {
1474 816005541 : return m_bitmask;
1475 : }
1476 :
1477 : inline bool
1478 0 : prange::fits_p (const vrange &) const
1479 : {
1480 0 : return true;
1481 : }
1482 :
1483 : // Set this range's point-to object to PTR, and POINTS_TO_P is TRUE if it
1484 : // does point to it, and FALSE if it does not point to it.
1485 :
1486 : inline void
1487 199654956 : prange::set_pt (const prange &r)
1488 : {
1489 199654956 : m_pt = r.m_pt;
1490 199654956 : m_points_to_p = r.m_points_to_p;
1491 :
1492 199654956 : if (r.undefined_p ())
1493 : return;
1494 : // Check whether this is now VARYING or not.
1495 199590904 : if (varying_compatible_p ())
1496 26003304 : set_varying (type ());
1497 : else
1498 173587600 : m_kind = VR_RANGE;
1499 : }
1500 :
1501 : // prange_pt methods.
1502 : // ------------------------------------------------------------------
1503 :
1504 : inline void
1505 1739074908 : prange::set_pt_unknown ()
1506 : {
1507 1739074908 : m_pt = NULL_TREE;
1508 1613415979 : m_points_to_p = false;
1509 : }
1510 :
1511 : inline bool
1512 670162384 : prange::pt_unknown_p () const
1513 : {
1514 615000937 : return (m_pt == NULL_TREE);
1515 : }
1516 :
1517 : inline bool
1518 63991239 : prange::pt_equal_p (const prange &p) const
1519 : {
1520 63991239 : return (m_points_to_p == p.m_points_to_p && m_pt == p.m_pt);
1521 : }
1522 :
1523 : inline bool
1524 70146963 : prange::pt_inverted_p (const prange &r) const
1525 : {
1526 410262 : return m_pt && vrp_operand_equal_p (m_pt, r.m_pt)
1527 70236742 : && m_points_to_p != r.m_points_to_p;
1528 : }
1529 :
1530 : inline bool
1531 2584763 : prange::pt_invert ()
1532 : {
1533 2584763 : if (m_pt)
1534 : {
1535 0 : m_points_to_p = !m_points_to_p;
1536 0 : return true;
1537 : }
1538 : return false;
1539 : }
1540 :
1541 : inline tree
1542 79071673 : prange::pt_invariant () const
1543 : {
1544 79071673 : if (m_pt && m_points_to_p)
1545 6888 : return m_pt;
1546 : return NULL_TREE;
1547 : }
1548 :
1549 : inline tree
1550 1571544 : prange::pt_invariant_away () const
1551 : {
1552 1571544 : if (m_pt && !m_points_to_p)
1553 0 : return m_pt;
1554 : return NULL_TREE;
1555 : }
1556 :
1557 : inline bool
1558 17073302 : prange::pt_invariant_p (const prange &r) const
1559 : {
1560 183409 : if (m_pt && m_points_to_p && vrp_operand_equal_p (r.m_pt, m_pt)
1561 17087180 : && m_points_to_p == r.m_points_to_p)
1562 : return true;
1563 : return false;
1564 : }
1565 :
1566 : inline bool
1567 : prange::pt_invariant_away_p (const prange &r) const
1568 : {
1569 : if (m_pt && !m_points_to_p && vrp_operand_equal_p (r.m_pt, m_pt)
1570 : && m_points_to_p == r.m_points_to_p)
1571 : return true;
1572 : return false;
1573 : }
1574 :
1575 :
1576 : // -----------------------------------------------------------------------
1577 :
1578 : inline
1579 113256190 : frange::frange ()
1580 113256190 : : vrange (VR_FRANGE)
1581 : {
1582 113256154 : set_undefined ();
1583 : }
1584 :
1585 : inline
1586 2862418 : frange::frange (const frange &src)
1587 2862418 : : vrange (VR_FRANGE)
1588 : {
1589 2457453 : *this = src;
1590 : }
1591 :
1592 : inline
1593 770815 : frange::frange (tree type)
1594 770815 : : vrange (VR_FRANGE)
1595 : {
1596 770815 : set_varying (type);
1597 : }
1598 :
1599 : // frange constructor from REAL_VALUE_TYPE endpoints.
1600 :
1601 : inline
1602 47712591 : frange::frange (tree type,
1603 : const REAL_VALUE_TYPE &min, const REAL_VALUE_TYPE &max,
1604 47712083 : value_range_kind kind)
1605 47712591 : : vrange (VR_FRANGE)
1606 : {
1607 47712591 : set (type, min, max, kind);
1608 : }
1609 :
1610 : // frange constructor from trees.
1611 :
1612 : inline
1613 : frange::frange (tree min, tree max, value_range_kind kind)
1614 : : vrange (VR_FRANGE)
1615 : {
1616 : set (min, max, kind);
1617 : }
1618 :
1619 : inline tree
1620 74173812 : frange::type () const
1621 : {
1622 74173812 : gcc_checking_assert (!undefined_p ());
1623 74173812 : return m_type;
1624 : }
1625 :
1626 : inline void
1627 68992404 : frange::set_varying (tree type)
1628 : {
1629 68992404 : m_kind = VR_VARYING;
1630 68992404 : m_type = type;
1631 68992404 : m_min = frange_val_min (type);
1632 68992404 : m_max = frange_val_max (type);
1633 68992404 : if (HONOR_NANS (m_type))
1634 : {
1635 65029653 : m_pos_nan = true;
1636 65029653 : m_neg_nan = true;
1637 : }
1638 : else
1639 : {
1640 3962751 : m_pos_nan = false;
1641 3962751 : m_neg_nan = false;
1642 : }
1643 68992404 : }
1644 :
1645 : inline void
1646 131036651 : frange::set_undefined ()
1647 : {
1648 131036651 : m_kind = VR_UNDEFINED;
1649 131036651 : m_type = NULL;
1650 131036651 : m_pos_nan = false;
1651 131036651 : m_neg_nan = false;
1652 : // m_min and m_min are uninitialized as they are REAL_VALUE_TYPE ??.
1653 131036651 : if (flag_checking)
1654 131036651 : verify_range ();
1655 131036651 : }
1656 :
1657 : // Set the NAN bits to NAN and adjust the range.
1658 :
1659 : inline void
1660 6321563 : frange::update_nan (const nan_state &nan)
1661 : {
1662 6321563 : gcc_checking_assert (!undefined_p ());
1663 6321563 : if (HONOR_NANS (m_type))
1664 : {
1665 6321059 : m_pos_nan = nan.pos_p ();
1666 6321059 : m_neg_nan = nan.neg_p ();
1667 6321059 : normalize_kind ();
1668 6321059 : if (flag_checking)
1669 6321059 : verify_range ();
1670 : }
1671 6321563 : }
1672 :
1673 : // Set the NAN bit to +-NAN.
1674 :
1675 : inline void
1676 4351091 : frange::update_nan ()
1677 : {
1678 4351091 : gcc_checking_assert (!undefined_p ());
1679 4351091 : nan_state nan (true);
1680 4351091 : update_nan (nan);
1681 4351091 : }
1682 :
1683 : // Like above, but set the sign of the NAN.
1684 :
1685 : inline void
1686 1970472 : frange::update_nan (bool sign)
1687 : {
1688 1970472 : gcc_checking_assert (!undefined_p ());
1689 1970472 : nan_state nan (/*pos=*/!sign, /*neg=*/sign);
1690 1970472 : update_nan (nan);
1691 1970472 : }
1692 :
1693 : inline bool
1694 0 : frange::contains_p (tree cst) const
1695 : {
1696 0 : return contains_p (*TREE_REAL_CST_PTR (cst));
1697 : }
1698 :
1699 : // Clear the NAN bit and adjust the range.
1700 :
1701 : inline void
1702 14526337 : frange::clear_nan ()
1703 : {
1704 14526337 : gcc_checking_assert (!undefined_p ());
1705 14526337 : m_pos_nan = false;
1706 14526337 : m_neg_nan = false;
1707 14526337 : normalize_kind ();
1708 14526337 : if (flag_checking)
1709 14526337 : verify_range ();
1710 14526337 : }
1711 :
1712 : // Set R to maximum representable value for TYPE.
1713 :
1714 : inline REAL_VALUE_TYPE
1715 23404920 : real_max_representable (const_tree type)
1716 : {
1717 23404920 : REAL_VALUE_TYPE r;
1718 23404920 : char buf[128];
1719 23404920 : get_max_float (REAL_MODE_FORMAT (TYPE_MODE (type)),
1720 : buf, sizeof (buf), false);
1721 23404920 : int res = real_from_string (&r, buf);
1722 23404920 : gcc_checking_assert (!res);
1723 23404920 : return r;
1724 : }
1725 :
1726 : // Return the minimum representable value for TYPE.
1727 :
1728 : inline REAL_VALUE_TYPE
1729 12092537 : real_min_representable (const_tree type)
1730 : {
1731 12092537 : REAL_VALUE_TYPE r = real_max_representable (type);
1732 12092537 : r = real_value_negate (&r);
1733 12092537 : return r;
1734 : }
1735 :
1736 : // Return the minimum value for TYPE.
1737 :
1738 : inline REAL_VALUE_TYPE
1739 179985573 : frange_val_min (const_tree type)
1740 : {
1741 179985573 : if (HONOR_INFINITIES (type))
1742 169290450 : return dconstninf;
1743 : else
1744 10695123 : return real_min_representable (type);
1745 : }
1746 :
1747 : // Return the maximum value for TYPE.
1748 :
1749 : inline REAL_VALUE_TYPE
1750 127446335 : frange_val_max (const_tree type)
1751 : {
1752 127446335 : if (HONOR_INFINITIES (type))
1753 117613489 : return dconstinf;
1754 : else
1755 9832846 : return real_max_representable (type);
1756 : }
1757 :
1758 : // Return TRUE if R is the minimum value for TYPE.
1759 :
1760 : inline bool
1761 107570047 : frange_val_is_min (const REAL_VALUE_TYPE &r, const_tree type)
1762 : {
1763 107570047 : REAL_VALUE_TYPE min = frange_val_min (type);
1764 107570047 : return real_identical (&min, &r);
1765 : }
1766 :
1767 : // Return TRUE if R is the max value for TYPE.
1768 :
1769 : inline bool
1770 54647479 : frange_val_is_max (const REAL_VALUE_TYPE &r, const_tree type)
1771 : {
1772 54647479 : REAL_VALUE_TYPE max = frange_val_max (type);
1773 54647479 : return real_identical (&max, &r);
1774 : }
1775 :
1776 : // Build a NAN with a state of NAN.
1777 :
1778 : inline void
1779 325195 : frange::set_nan (tree type, const nan_state &nan)
1780 : {
1781 325195 : gcc_checking_assert (nan.pos_p () || nan.neg_p ());
1782 325195 : if (HONOR_NANS (type))
1783 : {
1784 325194 : m_kind = VR_NAN;
1785 325194 : m_type = type;
1786 325194 : m_neg_nan = nan.neg_p ();
1787 325194 : m_pos_nan = nan.pos_p ();
1788 325194 : if (flag_checking)
1789 325194 : verify_range ();
1790 : }
1791 : else
1792 1 : set_undefined ();
1793 325195 : }
1794 :
1795 : // Build a signless NAN of type TYPE.
1796 :
1797 : inline void
1798 146528 : frange::set_nan (tree type)
1799 : {
1800 146528 : nan_state nan (true);
1801 146516 : set_nan (type, nan);
1802 124554 : }
1803 :
1804 : // Build a NAN of type TYPE with SIGN.
1805 :
1806 : inline void
1807 178664 : frange::set_nan (tree type, bool sign)
1808 : {
1809 178664 : nan_state nan (/*pos=*/!sign, /*neg=*/sign);
1810 178660 : set_nan (type, nan);
1811 21667 : }
1812 :
1813 : // Return TRUE if range is known to be finite.
1814 :
1815 : inline bool
1816 0 : frange::known_isfinite () const
1817 : {
1818 0 : if (undefined_p () || varying_p () || m_kind == VR_ANTI_RANGE)
1819 : return false;
1820 0 : return (!maybe_isnan () && !real_isinf (&m_min) && !real_isinf (&m_max));
1821 : }
1822 :
1823 : // Return TRUE if range is known to be normal.
1824 :
1825 : inline bool
1826 0 : frange::known_isnormal () const
1827 : {
1828 0 : if (!known_isfinite ())
1829 : return false;
1830 :
1831 0 : machine_mode mode = TYPE_MODE (type ());
1832 0 : return (!real_isdenormal (&m_min, mode) && !real_isdenormal (&m_max, mode)
1833 0 : && !real_iszero (&m_min) && !real_iszero (&m_max)
1834 0 : && (!real_isneg (&m_min) || real_isneg (&m_max)));
1835 : }
1836 :
1837 : // Return TRUE if range is known to be denormal.
1838 :
1839 : inline bool
1840 0 : frange::known_isdenormal_or_zero () const
1841 : {
1842 0 : if (!known_isfinite ())
1843 : return false;
1844 :
1845 0 : machine_mode mode = TYPE_MODE (type ());
1846 0 : return ((real_isdenormal (&m_min, mode) || real_iszero (&m_min))
1847 0 : && (real_isdenormal (&m_max, mode) || real_iszero (&m_max)));
1848 : }
1849 :
1850 : // Return TRUE if range may be infinite.
1851 :
1852 : inline bool
1853 33997 : frange::maybe_isinf () const
1854 : {
1855 33997 : if (undefined_p () || m_kind == VR_ANTI_RANGE || m_kind == VR_NAN)
1856 : return false;
1857 33997 : if (varying_p ())
1858 : return true;
1859 31934 : return real_isinf (&m_min) || real_isinf (&m_max);
1860 : }
1861 :
1862 : // Return TRUE if range is known to be the [-INF,-INF] or [+INF,+INF].
1863 :
1864 : inline bool
1865 6064326 : frange::known_isinf () const
1866 : {
1867 6064326 : return (m_kind == VR_RANGE
1868 8527918 : && !maybe_isnan ()
1869 1231787 : && real_identical (&m_min, &m_max)
1870 6082078 : && real_isinf (&m_min));
1871 : }
1872 :
1873 : // Return TRUE if range is possibly a NAN.
1874 :
1875 : inline bool
1876 23201106 : frange::maybe_isnan () const
1877 : {
1878 21512668 : if (undefined_p ())
1879 : return false;
1880 23197202 : return m_pos_nan || m_neg_nan;
1881 : }
1882 :
1883 : // Return TRUE if range is possibly a NAN with SIGN.
1884 :
1885 : inline bool
1886 157193 : frange::maybe_isnan (bool sign) const
1887 : {
1888 157193 : if (undefined_p ())
1889 : return false;
1890 157193 : if (sign)
1891 157193 : return m_neg_nan;
1892 : return m_pos_nan;
1893 : }
1894 :
1895 : // Return TRUE if range is a +NAN or -NAN.
1896 :
1897 : inline bool
1898 17218138 : frange::known_isnan () const
1899 : {
1900 13242213 : return m_kind == VR_NAN;
1901 : }
1902 :
1903 : // If the signbit for the range is known, set it in SIGNBIT and return
1904 : // TRUE.
1905 :
1906 : inline bool
1907 1653558 : frange::signbit_p (bool &signbit) const
1908 : {
1909 1653558 : if (undefined_p ())
1910 : return false;
1911 :
1912 : // NAN with unknown sign.
1913 1653540 : if (m_pos_nan && m_neg_nan)
1914 : return false;
1915 : // No NAN.
1916 103360 : if (!m_pos_nan && !m_neg_nan)
1917 : {
1918 85867 : if (m_min.sign == m_max.sign)
1919 : {
1920 11705 : signbit = m_min.sign;
1921 11705 : return true;
1922 : }
1923 : return false;
1924 : }
1925 : // NAN with known sign.
1926 17493 : bool nan_sign = m_neg_nan;
1927 17493 : if (known_isnan ()
1928 17493 : || (nan_sign == m_min.sign && nan_sign == m_max.sign))
1929 : {
1930 16167 : signbit = nan_sign;
1931 16167 : return true;
1932 : }
1933 : return false;
1934 : }
1935 :
1936 : // If range has a NAN with a known sign, set it in SIGNBIT and return
1937 : // TRUE.
1938 :
1939 : inline bool
1940 51229 : frange::nan_signbit_p (bool &signbit) const
1941 : {
1942 51229 : if (undefined_p ())
1943 : return false;
1944 :
1945 51229 : if (m_pos_nan == m_neg_nan)
1946 : return false;
1947 :
1948 2404 : signbit = m_neg_nan;
1949 2404 : return true;
1950 : }
1951 :
1952 : void frange_nextafter (enum machine_mode, REAL_VALUE_TYPE &,
1953 : const REAL_VALUE_TYPE &);
1954 : void frange_arithmetic (enum tree_code, tree, REAL_VALUE_TYPE &,
1955 : const REAL_VALUE_TYPE &, const REAL_VALUE_TYPE &,
1956 : const REAL_VALUE_TYPE &);
1957 :
1958 : // Return true if TYPE1 and TYPE2 are compatible range types.
1959 :
1960 : inline bool
1961 1599334597 : range_compatible_p (tree type1, tree type2)
1962 : {
1963 : // types_compatible_p requires conversion in both directions to be useless.
1964 : // GIMPLE only requires a cast one way in order to be compatible.
1965 : // Ranges really only need the sign and precision to be the same.
1966 1599334597 : return (TYPE_PRECISION (type1) == TYPE_PRECISION (type2)
1967 1599334597 : && TYPE_SIGN (type1) == TYPE_SIGN (type2));
1968 : }
1969 : #endif // GCC_VALUE_RANGE_H
|
