gcc/value-range.h

   1 /* Support routines for value ranges.
   2    Copyright (C) 2019-2023 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   // Floating point range.
  51   VR_FRANGE,
  52   // Range holds an unsupported type.
  53   VR_UNKNOWN
  54 };
  55
  56 // Abstract class for ranges of any of the supported types.
  57 //
  58 // To query what types ranger and the entire ecosystem can support,
  59 // use Value_Range::supports_type_p(tree type).  This is a static
  60 // method available independently of any vrange object.
  61 //
  62 // To query what a given vrange variant can support, use:
  63 //    irange::supports_p ()
  64 //    frange::supports_p ()
  65 //    etc
  66 //
  67 // To query what a range object can support, use:
  68 //    void foo (vrange &v, irange &i, frange &f)
  69 //    {
  70 //      if (v.supports_type_p (type)) ...
  71 //      if (i.supports_type_p (type)) ...
  72 //      if (f.supports_type_p (type)) ...
  73 //    }
  74
  75 class GTY((user)) vrange
  76 {
  77   template <typename T> friend bool is_a (vrange &);
  78   friend class Value_Range;
  79 public:
  80   virtual void accept (const class vrange_visitor &v) const = 0;
  81   virtual void set (tree, tree, value_range_kind = VR_RANGE);
  82   virtual tree type () const;
  83   virtual bool supports_type_p (const_tree type) const;
  84   virtual void set_varying (tree type);
  85   virtual void set_undefined ();
  86   virtual bool union_ (const vrange &);
  87   virtual bool intersect (const vrange &);
  88   virtual bool singleton_p (tree *result = NULL) const;
  89   virtual bool contains_p (tree cst) const;
  90   virtual bool zero_p () const;
  91   virtual bool nonzero_p () const;
  92   virtual void set_nonzero (tree type);
  93   virtual void set_zero (tree type);
  94   virtual void set_nonnegative (tree type);
  95   virtual bool fits_p (const vrange &r) const;
  96
  97   bool varying_p () const;
  98   bool undefined_p () const;
  99   vrange& operator= (const vrange &);
 100   bool operator== (const vrange &) const;
 101   bool operator!= (const vrange &r) const { return !(*this == r); }
 102   void dump (FILE *) const;
 103
 104   enum value_range_kind kind () const;          // DEPRECATED
 105
 106 protected:
 107   vrange (enum value_range_discriminator d) : m_discriminator (d) { }
 108   ENUM_BITFIELD(value_range_kind) m_kind : 8;
 109   const ENUM_BITFIELD(value_range_discriminator) m_discriminator : 4;
 110 };
 111
 112 namespace inchash
 113 {
 114   extern void add_vrange (const vrange &, hash &, unsigned flags = 0);
 115 }
 116
 117 // An integer range without any storage.
 118
 119 class GTY((user)) irange : public vrange
 120 {
 121   friend value_range_kind get_legacy_range (const irange &, tree &, tree &);
 122   friend class irange_storage;
 123 public:
 124   // In-place setters.
 125   void set (tree type, const wide_int &, const wide_int &,
 126             value_range_kind = VR_RANGE);
 127   virtual void set_nonzero (tree type) override;
 128   virtual void set_zero (tree type) override;
 129   virtual void set_nonnegative (tree type) override;
 130   virtual void set_varying (tree type) override;
 131   virtual void set_undefined () override;
 132
 133   // Range types.
 134   static bool supports_p (const_tree type);
 135   virtual bool supports_type_p (const_tree type) const override;
 136   virtual tree type () const override;
 137
 138   // Iteration over sub-ranges.
 139   unsigned num_pairs () const;
 140   wide_int lower_bound (unsigned = 0) const;
 141   wide_int upper_bound (unsigned) const;
 142   wide_int upper_bound () const;
 143
 144   // Predicates.
 145   virtual bool zero_p () const override;
 146   virtual bool nonzero_p () const override;
 147   virtual bool singleton_p (tree *result = NULL) const override;
 148   bool singleton_p (wide_int &) const;
 149   bool contains_p (const wide_int &) const;
 150
 151   // In-place operators.
 152   virtual bool union_ (const vrange &) override;
 153   virtual bool intersect (const vrange &) override;
 154   void invert ();
 155
 156   // Operator overloads.
 157   irange& operator= (const irange &);
 158   bool operator== (const irange &) const;
 159   bool operator!= (const irange &r) const { return !(*this == r); }
 160
 161   // Misc methods.
 162   virtual bool fits_p (const vrange &r) const override;
 163   virtual void accept (const vrange_visitor &v) const override;
 164
 165   // Nonzero masks.
 166   wide_int get_nonzero_bits () const;
 167   void set_nonzero_bits (const wide_int &bits);
 168
 169 protected:
 170   void maybe_resize (int needed);
 171   virtual void set (tree, tree, value_range_kind = VR_RANGE) override;
 172   virtual bool contains_p (tree cst) const override;
 173   irange (wide_int *, unsigned nranges, bool resizable);
 174
 175    // In-place operators.
 176   bool irange_contains_p (const irange &) const;
 177   bool irange_single_pair_union (const irange &r);
 178
 179   void normalize_kind ();
 180
 181   void verify_range ();
 182
 183   // Hard limit on max ranges allowed.
 184   static const int HARD_MAX_RANGES = 255;
 185 private:
 186   friend void gt_ggc_mx (irange *);
 187   friend void gt_pch_nx (irange *);
 188   friend void gt_pch_nx (irange *, gt_pointer_operator, void *);
 189
 190   bool varying_compatible_p () const;
 191   bool intersect_nonzero_bits (const irange &r);
 192   bool union_nonzero_bits (const irange &r);
 193   wide_int get_nonzero_bits_from_range () const;
 194   bool set_range_from_nonzero_bits ();
 195
 196   bool intersect (const wide_int& lb, const wide_int& ub);
 197   unsigned char m_num_ranges;
 198   bool m_resizable;
 199   unsigned char m_max_ranges;
 200   tree m_type;
 201   wide_int m_nonzero_mask;
 202 protected:
 203   wide_int *m_base;
 204 };
 205
 206 // Here we describe an irange with N pairs of ranges.  The storage for
 207 // the pairs is embedded in the class as an array.
 208 //
 209 // If RESIZABLE is true, the storage will be resized on the heap when
 210 // the number of ranges needed goes past N up to a max of
 211 // HARD_MAX_RANGES.  This new storage is freed upon destruction.
 212
 213 template<unsigned N, bool RESIZABLE = false>
 214 class GTY((user)) int_range : public irange
 215 {
 216 public:
 217   int_range ();
 218   int_range (tree type, const wide_int &, const wide_int &,
 219              value_range_kind = VR_RANGE);
 220   int_range (tree type);
 221   int_range (const int_range &);
 222   int_range (const irange &);
 223   virtual ~int_range ();
 224   int_range& operator= (const int_range &);
 225 protected:
 226   int_range (tree, tree, value_range_kind = VR_RANGE);
 227 private:
 228   wide_int m_ranges[N*2];
 229 };
 230
 231 // Unsupported temporaries may be created by ranger before it's known
 232 // they're unsupported, or by vr_values::get_value_range.
 233
 234 class unsupported_range : public vrange
 235 {
 236 public:
 237   unsupported_range ()
 238     : vrange (VR_UNKNOWN)
 239   {
 240     set_undefined ();
 241   }
 242   virtual void set_undefined () final override
 243   {
 244     m_kind = VR_UNDEFINED;
 245   }
 246   virtual void accept (const vrange_visitor &v) const override;
 247 };
 248
 249 // The NAN state as an opaque object.
 250
 251 class nan_state
 252 {
 253 public:
 254   nan_state (bool);
 255   nan_state (bool pos_nan, bool neg_nan);
 256   bool neg_p () const;
 257   bool pos_p () const;
 258 private:
 259   bool m_pos_nan;
 260   bool m_neg_nan;
 261 };
 262
 263 // Set NAN state to +-NAN if NAN_P is true.  Otherwise set NAN state
 264 // to false.
 265
 266 inline
 267 nan_state::nan_state (bool nan_p)
 268 {
 269   m_pos_nan = nan_p;
 270   m_neg_nan = nan_p;
 271 }
 272
 273 // Constructor initializing the object to +NAN if POS_NAN is set, -NAN
 274 // if NEG_NAN is set, or +-NAN if both are set.  Otherwise POS_NAN and
 275 // NEG_NAN are clear, and the object cannot be a NAN.
 276
 277 inline
 278 nan_state::nan_state (bool pos_nan, bool neg_nan)
 279 {
 280   m_pos_nan = pos_nan;
 281   m_neg_nan = neg_nan;
 282 }
 283
 284 // Return if +NAN is possible.
 285
 286 inline bool
 287 nan_state::pos_p () const
 288 {
 289   return m_pos_nan;
 290 }
 291
 292 // Return if -NAN is possible.
 293
 294 inline bool
 295 nan_state::neg_p () const
 296 {
 297   return m_neg_nan;
 298 }
 299
 300 // A floating point range.
 301 //
 302 // The representation is a type with a couple of endpoints, unioned
 303 // with the set of { -NAN, +Nan }.
 304
 305 class GTY((user)) frange : public vrange
 306 {
 307   friend class frange_storage;
 308   friend class vrange_printer;
 309   friend void gt_ggc_mx (frange *);
 310   friend void gt_pch_nx (frange *);
 311   friend void gt_pch_nx (frange *, gt_pointer_operator, void *);
 312 public:
 313   frange ();
 314   frange (const frange &);
 315   frange (tree, tree, value_range_kind = VR_RANGE);
 316   frange (tree type);
 317   frange (tree type, const REAL_VALUE_TYPE &min, const REAL_VALUE_TYPE &max,
 318           value_range_kind = VR_RANGE);
 319   static bool supports_p (const_tree type)
 320   {
 321     // ?? Decimal floats can have multiple representations for the
 322     // same number.  Supporting them may be as simple as just
 323     // disabling them in singleton_p.  No clue.
 324     return SCALAR_FLOAT_TYPE_P (type) && !DECIMAL_FLOAT_TYPE_P (type);
 325   }
 326   virtual tree type () const override;
 327   void set (tree type, const REAL_VALUE_TYPE &, const REAL_VALUE_TYPE &,
 328             value_range_kind = VR_RANGE);
 329   void set (tree type, const REAL_VALUE_TYPE &, const REAL_VALUE_TYPE &,
 330             const nan_state &, value_range_kind = VR_RANGE);
 331   void set_nan (tree type);
 332   void set_nan (tree type, bool sign);
 333   virtual void set_varying (tree type) override;
 334   virtual void set_undefined () override;
 335   virtual bool union_ (const vrange &) override;
 336   virtual bool intersect (const vrange &) override;
 337   bool contains_p (const REAL_VALUE_TYPE &) const;
 338   virtual bool singleton_p (tree *result = NULL) const override;
 339   bool singleton_p (REAL_VALUE_TYPE &r) const;
 340   virtual bool supports_type_p (const_tree type) const override;
 341   virtual void accept (const vrange_visitor &v) const override;
 342   virtual bool zero_p () const override;
 343   virtual bool nonzero_p () const override;
 344   virtual void set_nonzero (tree type) override;
 345   virtual void set_zero (tree type) override;
 346   virtual void set_nonnegative (tree type) override;
 347   frange& operator= (const frange &);
 348   bool operator== (const frange &) const;
 349   bool operator!= (const frange &r) const { return !(*this == r); }
 350   const REAL_VALUE_TYPE &lower_bound () const;
 351   const REAL_VALUE_TYPE &upper_bound () const;
 352   nan_state get_nan_state () const;
 353   void update_nan ();
 354   void update_nan (bool sign);
 355   void update_nan (tree) = delete; // Disallow silent conversion to bool.
 356   void update_nan (const nan_state &);
 357   void clear_nan ();
 358   void flush_denormals_to_zero ();
 359
 360   // fpclassify like API
 361   bool known_isfinite () const;
 362   bool known_isnan () const;
 363   bool known_isinf () const;
 364   bool maybe_isnan () const;
 365   bool maybe_isnan (bool sign) const;
 366   bool maybe_isinf () const;
 367   bool signbit_p (bool &signbit) const;
 368   bool nan_signbit_p (bool &signbit) const;
 369
 370 protected:
 371   virtual bool contains_p (tree cst) const override;
 372   virtual void set (tree, tree, value_range_kind = VR_RANGE) override;
 373
 374 private:
 375   bool internal_singleton_p (REAL_VALUE_TYPE * = NULL) const;
 376   void verify_range ();
 377   bool normalize_kind ();
 378   bool union_nans (const frange &);
 379   bool intersect_nans (const frange &);
 380   bool combine_zeros (const frange &, bool union_p);
 381
 382   tree m_type;
 383   REAL_VALUE_TYPE m_min;
 384   REAL_VALUE_TYPE m_max;
 385   bool m_pos_nan;
 386   bool m_neg_nan;
 387 };
 388
 389 inline const REAL_VALUE_TYPE &
 390 frange::lower_bound () const
 391 {
 392   gcc_checking_assert (!undefined_p () && !known_isnan ());
 393   return m_min;
 394 }
 395
 396 inline const REAL_VALUE_TYPE &
 397 frange::upper_bound () const
 398 {
 399   gcc_checking_assert (!undefined_p () && !known_isnan ());
 400   return m_max;
 401 }
 402
 403 // Return the NAN state.
 404
 405 inline nan_state
 406 frange::get_nan_state () const
 407 {
 408   return nan_state (m_pos_nan, m_neg_nan);
 409 }
 410
 411 // is_a<> and as_a<> implementation for vrange.
 412
 413 // Anything we haven't specialized is a hard fail.
 414 template <typename T>
 415 inline bool
 416 is_a (vrange &)
 417 {
 418   gcc_unreachable ();
 419   return false;
 420 }
 421
 422 template <typename T>
 423 inline bool
 424 is_a (const vrange &v)
 425 {
 426   // Reuse is_a <vrange> to implement the const version.
 427   const T &derived = static_cast<const T &> (v);
 428   return is_a <T> (const_cast<T &> (derived));
 429 }
 430
 431 template <typename T>
 432 inline T &
 433 as_a (vrange &v)
 434 {
 435   gcc_checking_assert (is_a <T> (v));
 436   return static_cast <T &> (v);
 437 }
 438
 439 template <typename T>
 440 inline const T &
 441 as_a (const vrange &v)
 442 {
 443   gcc_checking_assert (is_a <T> (v));
 444   return static_cast <const T &> (v);
 445 }
 446
 447 // Specializations for the different range types.
 448
 449 template <>
 450 inline bool
 451 is_a <irange> (vrange &v)
 452 {
 453   return v.m_discriminator == VR_IRANGE;
 454 }
 455
 456 template <>
 457 inline bool
 458 is_a <frange> (vrange &v)
 459 {
 460   return v.m_discriminator == VR_FRANGE;
 461 }
 462
 463 template <>
 464 inline bool
 465 is_a <unsupported_range> (vrange &v)
 466 {
 467   return v.m_discriminator == VR_UNKNOWN;
 468 }
 469
 470 // For resizable ranges, resize the range up to HARD_MAX_RANGES if the
 471 // NEEDED pairs is greater than the current capacity of the range.
 472
 473 inline void
 474 irange::maybe_resize (int needed)
 475 {
 476   if (!m_resizable || m_max_ranges == HARD_MAX_RANGES)
 477     return;
 478
 479   if (needed > m_max_ranges)
 480     {
 481       m_max_ranges = HARD_MAX_RANGES;
 482       wide_int *newmem = new wide_int[m_max_ranges * 2];
 483       memcpy (newmem, m_base, sizeof (wide_int) * num_pairs () * 2);
 484       m_base = newmem;
 485     }
 486 }
 487
 488 template<unsigned N, bool RESIZABLE>
 489 inline
 490 int_range<N, RESIZABLE>::~int_range ()
 491 {
 492   if (RESIZABLE && m_base != m_ranges)
 493     delete[] m_base;
 494 }
 495
 496 // This is an "infinite" precision irange for use in temporary
 497 // calculations.  It starts with a sensible default covering 99% of
 498 // uses, and goes up to HARD_MAX_RANGES when needed.  Any allocated
 499 // storage is freed upon destruction.
 500 typedef int_range<3, /*RESIZABLE=*/true> int_range_max;
 501
 502 class vrange_visitor
 503 {
 504 public:
 505   virtual void visit (const irange &) const { }
 506   virtual void visit (const frange &) const { }
 507   virtual void visit (const unsupported_range &) const { }
 508 };
 509
 510 typedef int_range<2> value_range;
 511
 512 // This is an "infinite" precision range object for use in temporary
 513 // calculations for any of the handled types.  The object can be
 514 // transparently used as a vrange.
 515
 516 class Value_Range
 517 {
 518 public:
 519   Value_Range ();
 520   Value_Range (const vrange &r);
 521   Value_Range (tree type);
 522   Value_Range (tree, tree, value_range_kind kind = VR_RANGE);
 523   Value_Range (const Value_Range &);
 524   void set_type (tree type);
 525   vrange& operator= (const vrange &);
 526   Value_Range& operator= (const Value_Range &);
 527   bool operator== (const Value_Range &r) const;
 528   bool operator!= (const Value_Range &r) const;
 529   operator vrange &();
 530   operator const vrange &() const;
 531   void dump (FILE *) const;
 532   static bool supports_type_p (const_tree type);
 533
 534   // Convenience methods for vrange compatibility.
 535   tree type () { return m_vrange->type (); }
 536   bool varying_p () const { return m_vrange->varying_p (); }
 537   bool undefined_p () const { return m_vrange->undefined_p (); }
 538   void set_varying (tree type) { m_vrange->set_varying (type); }
 539   void set_undefined () { m_vrange->set_undefined (); }
 540   bool union_ (const vrange &r) { return m_vrange->union_ (r); }
 541   bool intersect (const vrange &r) { return m_vrange->intersect (r); }
 542   bool contains_p (tree cst) const { return m_vrange->contains_p (cst); }
 543   bool singleton_p (tree *result = NULL) const
 544     { return m_vrange->singleton_p (result); }
 545   void set_zero (tree type) { return m_vrange->set_zero (type); }
 546   void set_nonzero (tree type) { return m_vrange->set_nonzero (type); }
 547   bool nonzero_p () const { return m_vrange->nonzero_p (); }
 548   bool zero_p () const { return m_vrange->zero_p (); }
 549   wide_int lower_bound () const; // For irange/prange comparability.
 550   wide_int upper_bound () const; // For irange/prange comparability.
 551   void accept (const vrange_visitor &v) const { m_vrange->accept (v); }
 552 private:
 553   void init (tree type);
 554   unsupported_range m_unsupported;
 555   vrange *m_vrange;
 556   int_range_max m_irange;
 557   frange m_frange;
 558 };
 559
 560 inline
 561 Value_Range::Value_Range ()
 562 {
 563   m_vrange = &m_unsupported;
 564 }
 565
 566 // Copy constructor from a vrange.
 567
 568 inline
 569 Value_Range::Value_Range (const vrange &r)
 570 {
 571   *this = r;
 572 }
 573
 574 // Copy constructor from a TYPE.  The range of the temporary is set to
 575 // UNDEFINED.
 576
 577 inline
 578 Value_Range::Value_Range (tree type)
 579 {
 580   init (type);
 581 }
 582
 583 inline
 584 Value_Range::Value_Range (tree min, tree max, value_range_kind kind)
 585 {
 586   init (TREE_TYPE (min));
 587   m_vrange->set (min, max, kind);
 588 }
 589
 590 inline
 591 Value_Range::Value_Range (const Value_Range &r)
 592 {
 593   *this = *r.m_vrange;
 594 }
 595
 596 // Initialize object so it is possible to store temporaries of TYPE
 597 // into it.
 598
 599 inline void
 600 Value_Range::init (tree type)
 601 {
 602   gcc_checking_assert (TYPE_P (type));
 603
 604   if (irange::supports_p (type))
 605     m_vrange = &m_irange;
 606   else if (frange::supports_p (type))
 607     m_vrange = &m_frange;
 608   else
 609     m_vrange = &m_unsupported;
 610 }
 611
 612 // Set the temporary to allow storing temporaries of TYPE.  The range
 613 // of the temporary is set to UNDEFINED.
 614
 615 inline void
 616 Value_Range::set_type (tree type)
 617 {
 618   init (type);
 619   m_vrange->set_undefined ();
 620 }
 621
 622 // Assignment operator for temporaries.  Copying incompatible types is
 623 // allowed.
 624
 625 inline vrange &
 626 Value_Range::operator= (const vrange &r)
 627 {
 628   if (is_a <irange> (r))
 629     {
 630       m_irange = as_a <irange> (r);
 631       m_vrange = &m_irange;
 632     }
 633   else if (is_a <frange> (r))
 634     {
 635       m_frange = as_a <frange> (r);
 636       m_vrange = &m_frange;
 637     }
 638   else if (is_a <unsupported_range> (r))
 639     {
 640       m_unsupported = as_a <unsupported_range> (r);
 641       m_vrange = &m_unsupported;
 642     }
 643   else
 644     gcc_unreachable ();
 645
 646   return *m_vrange;
 647 }
 648
 649 inline Value_Range &
 650 Value_Range::operator= (const Value_Range &r)
 651 {
 652   if (r.m_vrange == &r.m_irange)
 653     {
 654       m_irange = r.m_irange;
 655       m_vrange = &m_irange;
 656     }
 657   else if (r.m_vrange == &r.m_frange)
 658     {
 659       m_frange = r.m_frange;
 660       m_vrange = &m_frange;
 661     }
 662   else if (r.m_vrange == &r.m_unsupported)
 663     {
 664       m_unsupported = r.m_unsupported;
 665       m_vrange = &m_unsupported;
 666     }
 667   else
 668     gcc_unreachable ();
 669
 670   return *this;
 671 }
 672
 673 inline bool
 674 Value_Range::operator== (const Value_Range &r) const
 675 {
 676   return *m_vrange == *r.m_vrange;
 677 }
 678
 679 inline bool
 680 Value_Range::operator!= (const Value_Range &r) const
 681 {
 682   return *m_vrange != *r.m_vrange;
 683 }
 684
 685 inline
 686 Value_Range::operator vrange &()
 687 {
 688   return *m_vrange;
 689 }
 690
 691 inline
 692 Value_Range::operator const vrange &() const
 693 {
 694   return *m_vrange;
 695 }
 696
 697 // Return TRUE if TYPE is supported by the vrange infrastructure.
 698
 699 inline bool
 700 Value_Range::supports_type_p (const_tree type)
 701 {
 702   return irange::supports_p (type) || frange::supports_p (type);
 703 }
 704
 705 extern value_range_kind get_legacy_range (const irange &, tree &min, tree &max);
 706 extern void dump_value_range (FILE *, const vrange *);
 707 extern bool vrp_operand_equal_p (const_tree, const_tree);
 708 inline REAL_VALUE_TYPE frange_val_min (const_tree type);
 709 inline REAL_VALUE_TYPE frange_val_max (const_tree type);
 710
 711 // Number of sub-ranges in a range.
 712
 713 inline unsigned
 714 irange::num_pairs () const
 715 {
 716   return m_num_ranges;
 717 }
 718
 719 inline tree
 720 irange::type () const
 721 {
 722   gcc_checking_assert (m_num_ranges > 0);
 723   return m_type;
 724 }
 725
 726 inline bool
 727 irange::varying_compatible_p () const
 728 {
 729   if (m_num_ranges != 1)
 730     return false;
 731
 732   const wide_int &l = m_base[0];
 733   const wide_int &u = m_base[1];
 734   tree t = m_type;
 735
 736   if (m_kind == VR_VARYING && t == error_mark_node)
 737     return true;
 738
 739   unsigned prec = TYPE_PRECISION (t);
 740   signop sign = TYPE_SIGN (t);
 741   if (INTEGRAL_TYPE_P (t) || POINTER_TYPE_P (t))
 742     return (l == wi::min_value (prec, sign)
 743             && u == wi::max_value (prec, sign)
 744             && m_nonzero_mask == -1);
 745   return true;
 746 }
 747
 748 inline bool
 749 vrange::varying_p () const
 750 {
 751   return m_kind == VR_VARYING;
 752 }
 753
 754 inline bool
 755 vrange::undefined_p () const
 756 {
 757   return m_kind == VR_UNDEFINED;
 758 }
 759
 760 inline bool
 761 irange::zero_p () const
 762 {
 763   return (m_kind == VR_RANGE && m_num_ranges == 1
 764           && lower_bound (0) == 0
 765           && upper_bound (0) == 0);
 766 }
 767
 768 inline bool
 769 irange::nonzero_p () const
 770 {
 771   if (undefined_p ())
 772     return false;
 773
 774   wide_int zero = wi::zero (TYPE_PRECISION (type ()));
 775   return *this == int_range<2> (type (), zero, zero, VR_ANTI_RANGE);
 776 }
 777
 778 inline bool
 779 irange::supports_p (const_tree type)
 780 {
 781   return INTEGRAL_TYPE_P (type) || POINTER_TYPE_P (type);
 782 }
 783
 784 inline bool
 785 irange::contains_p (tree cst) const
 786 {
 787   return contains_p (wi::to_wide (cst));
 788 }
 789
 790 inline bool
 791 range_includes_zero_p (const irange *vr)
 792 {
 793   if (vr->undefined_p ())
 794     return false;
 795
 796   if (vr->varying_p ())
 797     return true;
 798
 799   wide_int zero = wi::zero (TYPE_PRECISION (vr->type ()));
 800   return vr->contains_p (zero);
 801 }
 802
 803 extern void gt_ggc_mx (vrange *);
 804 extern void gt_pch_nx (vrange *);
 805 extern void gt_pch_nx (vrange *, gt_pointer_operator, void *);
 806 extern void gt_ggc_mx (irange *);
 807 extern void gt_pch_nx (irange *);
 808 extern void gt_pch_nx (irange *, gt_pointer_operator, void *);
 809 extern void gt_ggc_mx (frange *);
 810 extern void gt_pch_nx (frange *);
 811 extern void gt_pch_nx (frange *, gt_pointer_operator, void *);
 812
 813 template<unsigned N>
 814 inline void
 815 gt_ggc_mx (int_range<N> *x)
 816 {
 817   gt_ggc_mx ((irange *) x);
 818 }
 819
 820 template<unsigned N>
 821 inline void
 822 gt_pch_nx (int_range<N> *x)
 823 {
 824   gt_pch_nx ((irange *) x);
 825 }
 826
 827 template<unsigned N>
 828 inline void
 829 gt_pch_nx (int_range<N> *x, gt_pointer_operator op, void *cookie)
 830 {
 831   gt_pch_nx ((irange *) x, op, cookie);
 832 }
 833
 834 // Constructors for irange
 835
 836 inline
 837 irange::irange (wide_int *base, unsigned nranges, bool resizable)
 838   : vrange (VR_IRANGE),
 839     m_resizable (resizable),
 840     m_max_ranges (nranges)
 841 {
 842   m_base = base;
 843   set_undefined ();
 844 }
 845
 846 // Constructors for int_range<>.
 847
 848 template<unsigned N, bool RESIZABLE>
 849 inline
 850 int_range<N, RESIZABLE>::int_range ()
 851   : irange (m_ranges, N, RESIZABLE)
 852 {
 853 }
 854
 855 template<unsigned N, bool RESIZABLE>
 856 int_range<N, RESIZABLE>::int_range (const int_range &other)
 857   : irange (m_ranges, N, RESIZABLE)
 858 {
 859   irange::operator= (other);
 860 }
 861
 862 template<unsigned N, bool RESIZABLE>
 863 int_range<N, RESIZABLE>::int_range (tree min, tree max, value_range_kind kind)
 864   : irange (m_ranges, N, RESIZABLE)
 865 {
 866   irange::set (min, max, kind);
 867 }
 868
 869 template<unsigned N, bool RESIZABLE>
 870 int_range<N, RESIZABLE>::int_range (tree type)
 871   : irange (m_ranges, N, RESIZABLE)
 872 {
 873   set_varying (type);
 874 }
 875
 876 template<unsigned N, bool RESIZABLE>
 877 int_range<N, RESIZABLE>::int_range (tree type, const wide_int &wmin, const wide_int &wmax,
 878                          value_range_kind kind)
 879   : irange (m_ranges, N, RESIZABLE)
 880 {
 881   set (type, wmin, wmax, kind);
 882 }
 883
 884 template<unsigned N, bool RESIZABLE>
 885 int_range<N, RESIZABLE>::int_range (const irange &other)
 886   : irange (m_ranges, N, RESIZABLE)
 887 {
 888   irange::operator= (other);
 889 }
 890
 891 template<unsigned N, bool RESIZABLE>
 892 int_range<N, RESIZABLE>&
 893 int_range<N, RESIZABLE>::operator= (const int_range &src)
 894 {
 895   irange::operator= (src);
 896   return *this;
 897 }
 898
 899 inline void
 900 irange::set_undefined ()
 901 {
 902   m_kind = VR_UNDEFINED;
 903   m_num_ranges = 0;
 904 }
 905
 906 inline void
 907 irange::set_varying (tree type)
 908 {
 909   m_kind = VR_VARYING;
 910   m_num_ranges = 1;
 911   m_nonzero_mask = wi::minus_one (TYPE_PRECISION (type));
 912
 913   if (INTEGRAL_TYPE_P (type) || POINTER_TYPE_P (type))
 914     {
 915       m_type = type;
 916       // Strict enum's require varying to be not TYPE_MIN/MAX, but rather
 917       // min_value and max_value.
 918       m_base[0] = wi::min_value (TYPE_PRECISION (type), TYPE_SIGN (type));
 919       m_base[1] = wi::max_value (TYPE_PRECISION (type), TYPE_SIGN (type));
 920     }
 921   else
 922     m_type = error_mark_node;
 923 }
 924
 925 // Return the lower bound of a sub-range.  PAIR is the sub-range in
 926 // question.
 927
 928 inline wide_int
 929 irange::lower_bound (unsigned pair) const
 930 {
 931   gcc_checking_assert (m_num_ranges > 0);
 932   gcc_checking_assert (pair + 1 <= num_pairs ());
 933   return m_base[pair * 2];
 934 }
 935
 936 // Return the upper bound of a sub-range.  PAIR is the sub-range in
 937 // question.
 938
 939 inline wide_int
 940 irange::upper_bound (unsigned pair) const
 941 {
 942   gcc_checking_assert (m_num_ranges > 0);
 943   gcc_checking_assert (pair + 1 <= num_pairs ());
 944   return m_base[pair * 2 + 1];
 945 }
 946
 947 // Return the highest bound of a range.
 948
 949 inline wide_int
 950 irange::upper_bound () const
 951 {
 952   unsigned pairs = num_pairs ();
 953   gcc_checking_assert (pairs > 0);
 954   return upper_bound (pairs - 1);
 955 }
 956
 957 // Set value range VR to a nonzero range of type TYPE.
 958
 959 inline void
 960 irange::set_nonzero (tree type)
 961 {
 962   unsigned prec = TYPE_PRECISION (type);
 963
 964   if (TYPE_UNSIGNED (type))
 965     {
 966       m_type = type;
 967       m_kind = VR_RANGE;
 968       m_base[0] = wi::one (prec);
 969       m_base[1] = m_nonzero_mask = wi::minus_one (prec);
 970       m_num_ranges = 1;
 971
 972       if (flag_checking)
 973         verify_range ();
 974     }
 975   else
 976     {
 977       wide_int zero = wi::zero (prec);
 978       set (type, zero, zero, VR_ANTI_RANGE);
 979     }
 980 }
 981
 982 // Set value range VR to a ZERO range of type TYPE.
 983
 984 inline void
 985 irange::set_zero (tree type)
 986 {
 987   wide_int zero = wi::zero (TYPE_PRECISION (type));
 988   set (type, zero, zero);
 989 }
 990
 991 // Normalize a range to VARYING or UNDEFINED if possible.
 992
 993 inline void
 994 irange::normalize_kind ()
 995 {
 996   if (m_num_ranges == 0)
 997     set_undefined ();
 998   else if (varying_compatible_p ())
 999     {
1000       if (m_kind == VR_RANGE)
1001         m_kind = VR_VARYING;
1002       else if (m_kind == VR_ANTI_RANGE)
1003         set_undefined ();
1004     }
1005 }
1006
1007 inline bool
1008 contains_zero_p (const irange &r)
1009 {
1010   if (r.undefined_p ())
1011     return true;
1012
1013   wide_int zero = wi::zero (TYPE_PRECISION (r.type ()));
1014   return r.contains_p (zero);
1015 }
1016
1017 inline wide_int
1018 irange_val_min (const_tree type)
1019 {
1020   gcc_checking_assert (irange::supports_p (type));
1021   return wi::min_value (TYPE_PRECISION (type), TYPE_SIGN (type));
1022 }
1023
1024 inline wide_int
1025 irange_val_max (const_tree type)
1026 {
1027   gcc_checking_assert (irange::supports_p (type));
1028   return wi::max_value (TYPE_PRECISION (type), TYPE_SIGN (type));
1029 }
1030
1031 inline
1032 frange::frange ()
1033   : vrange (VR_FRANGE)
1034 {
1035   set_undefined ();
1036 }
1037
1038 inline
1039 frange::frange (const frange &src)
1040   : vrange (VR_FRANGE)
1041 {
1042   *this = src;
1043 }
1044
1045 inline
1046 frange::frange (tree type)
1047   : vrange (VR_FRANGE)
1048 {
1049   set_varying (type);
1050 }
1051
1052 // frange constructor from REAL_VALUE_TYPE endpoints.
1053
1054 inline
1055 frange::frange (tree type,
1056                 const REAL_VALUE_TYPE &min, const REAL_VALUE_TYPE &max,
1057                 value_range_kind kind)
1058   : vrange (VR_FRANGE)
1059 {
1060   set (type, min, max, kind);
1061 }
1062
1063 // frange constructor from trees.
1064
1065 inline
1066 frange::frange (tree min, tree max, value_range_kind kind)
1067   : vrange (VR_FRANGE)
1068 {
1069   set (min, max, kind);
1070 }
1071
1072 inline tree
1073 frange::type () const
1074 {
1075   gcc_checking_assert (!undefined_p ());
1076   return m_type;
1077 }
1078
1079 inline void
1080 frange::set_varying (tree type)
1081 {
1082   m_kind = VR_VARYING;
1083   m_type = type;
1084   m_min = frange_val_min (type);
1085   m_max = frange_val_max (type);
1086   if (HONOR_NANS (m_type))
1087     {
1088       m_pos_nan = true;
1089       m_neg_nan = true;
1090     }
1091   else
1092     {
1093       m_pos_nan = false;
1094       m_neg_nan = false;
1095     }
1096 }
1097
1098 inline void
1099 frange::set_undefined ()
1100 {
1101   m_kind = VR_UNDEFINED;
1102   m_type = NULL;
1103   m_pos_nan = false;
1104   m_neg_nan = false;
1105   // m_min and m_min are uninitialized as they are REAL_VALUE_TYPE ??.
1106   if (flag_checking)
1107     verify_range ();
1108 }
1109
1110 // Set the NAN bit and adjust the range.
1111
1112 inline void
1113 frange::update_nan ()
1114 {
1115   gcc_checking_assert (!undefined_p ());
1116   if (HONOR_NANS (m_type))
1117     {
1118       m_pos_nan = true;
1119       m_neg_nan = true;
1120       normalize_kind ();
1121       if (flag_checking)
1122         verify_range ();
1123     }
1124 }
1125
1126 // Like above, but set the sign of the NAN.
1127
1128 inline void
1129 frange::update_nan (bool sign)
1130 {
1131   gcc_checking_assert (!undefined_p ());
1132   if (HONOR_NANS (m_type))
1133     {
1134       m_pos_nan = !sign;
1135       m_neg_nan = sign;
1136       normalize_kind ();
1137       if (flag_checking)
1138         verify_range ();
1139     }
1140 }
1141
1142 inline bool
1143 frange::contains_p (tree cst) const
1144 {
1145   return contains_p (*TREE_REAL_CST_PTR (cst));
1146 }
1147
1148 // Clear the NAN bit and adjust the range.
1149
1150 inline void
1151 frange::clear_nan ()
1152 {
1153   gcc_checking_assert (!undefined_p ());
1154   m_pos_nan = false;
1155   m_neg_nan = false;
1156   normalize_kind ();
1157   if (flag_checking)
1158     verify_range ();
1159 }
1160
1161 // Set R to maximum representable value for TYPE.
1162
1163 inline REAL_VALUE_TYPE
1164 real_max_representable (const_tree type)
1165 {
1166   REAL_VALUE_TYPE r;
1167   char buf[128];
1168   get_max_float (REAL_MODE_FORMAT (TYPE_MODE (type)),
1169                  buf, sizeof (buf), false);
1170   int res = real_from_string (&r, buf);
1171   gcc_checking_assert (!res);
1172   return r;
1173 }
1174
1175 // Return the minimum representable value for TYPE.
1176
1177 inline REAL_VALUE_TYPE
1178 real_min_representable (const_tree type)
1179 {
1180   REAL_VALUE_TYPE r = real_max_representable (type);
1181   r = real_value_negate (&r);
1182   return r;
1183 }
1184
1185 // Return the minimum value for TYPE.
1186
1187 inline REAL_VALUE_TYPE
1188 frange_val_min (const_tree type)
1189 {
1190   if (HONOR_INFINITIES (type))
1191     return dconstninf;
1192   else
1193     return real_min_representable (type);
1194 }
1195
1196 // Return the maximum value for TYPE.
1197
1198 inline REAL_VALUE_TYPE
1199 frange_val_max (const_tree type)
1200 {
1201   if (HONOR_INFINITIES (type))
1202     return dconstinf;
1203   else
1204     return real_max_representable (type);
1205 }
1206
1207 // Return TRUE if R is the minimum value for TYPE.
1208
1209 inline bool
1210 frange_val_is_min (const REAL_VALUE_TYPE &r, const_tree type)
1211 {
1212   REAL_VALUE_TYPE min = frange_val_min (type);
1213   return real_identical (&min, &r);
1214 }
1215
1216 // Return TRUE if R is the max value for TYPE.
1217
1218 inline bool
1219 frange_val_is_max (const REAL_VALUE_TYPE &r, const_tree type)
1220 {
1221   REAL_VALUE_TYPE max = frange_val_max (type);
1222   return real_identical (&max, &r);
1223 }
1224
1225 // Build a signless NAN of type TYPE.
1226
1227 inline void
1228 frange::set_nan (tree type)
1229 {
1230   if (HONOR_NANS (type))
1231     {
1232       m_kind = VR_NAN;
1233       m_type = type;
1234       m_pos_nan = true;
1235       m_neg_nan = true;
1236       if (flag_checking)
1237         verify_range ();
1238     }
1239   else
1240     set_undefined ();
1241 }
1242
1243 // Build a NAN of type TYPE with SIGN.
1244
1245 inline void
1246 frange::set_nan (tree type, bool sign)
1247 {
1248   if (HONOR_NANS (type))
1249     {
1250       m_kind = VR_NAN;
1251       m_type = type;
1252       m_neg_nan = sign;
1253       m_pos_nan = !sign;
1254       if (flag_checking)
1255         verify_range ();
1256     }
1257   else
1258     set_undefined ();
1259 }
1260
1261 // Return TRUE if range is known to be finite.
1262
1263 inline bool
1264 frange::known_isfinite () const
1265 {
1266   if (undefined_p () || varying_p () || m_kind == VR_ANTI_RANGE)
1267     return false;
1268   return (!maybe_isnan () && !real_isinf (&m_min) && !real_isinf (&m_max));
1269 }
1270
1271 // Return TRUE if range may be infinite.
1272
1273 inline bool
1274 frange::maybe_isinf () const
1275 {
1276   if (undefined_p () || m_kind == VR_ANTI_RANGE || m_kind == VR_NAN)
1277     return false;
1278   if (varying_p ())
1279     return true;
1280   return real_isinf (&m_min) || real_isinf (&m_max);
1281 }
1282
1283 // Return TRUE if range is known to be the [-INF,-INF] or [+INF,+INF].
1284
1285 inline bool
1286 frange::known_isinf () const
1287 {
1288   return (m_kind == VR_RANGE
1289           && !maybe_isnan ()
1290           && real_identical (&m_min, &m_max)
1291           && real_isinf (&m_min));
1292 }
1293
1294 // Return TRUE if range is possibly a NAN.
1295
1296 inline bool
1297 frange::maybe_isnan () const
1298 {
1299   if (undefined_p ())
1300     return false;
1301   return m_pos_nan || m_neg_nan;
1302 }
1303
1304 // Return TRUE if range is possibly a NAN with SIGN.
1305
1306 inline bool
1307 frange::maybe_isnan (bool sign) const
1308 {
1309   if (undefined_p ())
1310     return false;
1311   if (sign)
1312     return m_neg_nan;
1313   return m_pos_nan;
1314 }
1315
1316 // Return TRUE if range is a +NAN or -NAN.
1317
1318 inline bool
1319 frange::known_isnan () const
1320 {
1321   return m_kind == VR_NAN;
1322 }
1323
1324 // If the signbit for the range is known, set it in SIGNBIT and return
1325 // TRUE.
1326
1327 inline bool
1328 frange::signbit_p (bool &signbit) const
1329 {
1330   if (undefined_p ())
1331     return false;
1332
1333   // NAN with unknown sign.
1334   if (m_pos_nan && m_neg_nan)
1335     return false;
1336   // No NAN.
1337   if (!m_pos_nan && !m_neg_nan)
1338     {
1339       if (m_min.sign == m_max.sign)
1340         {
1341           signbit = m_min.sign;
1342           return true;
1343         }
1344       return false;
1345     }
1346   // NAN with known sign.
1347   bool nan_sign = m_neg_nan;
1348   if (known_isnan ()
1349       || (nan_sign == m_min.sign && nan_sign == m_max.sign))
1350     {
1351       signbit = nan_sign;
1352       return true;
1353     }
1354   return false;
1355 }
1356
1357 // If range has a NAN with a known sign, set it in SIGNBIT and return
1358 // TRUE.
1359
1360 inline bool
1361 frange::nan_signbit_p (bool &signbit) const
1362 {
1363   if (undefined_p ())
1364     return false;
1365
1366   if (m_pos_nan == m_neg_nan)
1367     return false;
1368
1369   signbit = m_neg_nan;
1370   return true;
1371 }
1372
1373 void frange_nextafter (enum machine_mode, REAL_VALUE_TYPE &,
1374                        const REAL_VALUE_TYPE &);
1375 void frange_arithmetic (enum tree_code, tree, REAL_VALUE_TYPE &,
1376                         const REAL_VALUE_TYPE &, const REAL_VALUE_TYPE &,
1377                         const REAL_VALUE_TYPE &);
1378
1379 #endif // GCC_VALUE_RANGE_H