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