gcc/value-range.h

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