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 nice guy.  */
  39   VR_LAST
  40 };
  41
  42 // Discriminator between different vrange types.
  43
  44 enum value_range_discriminator
  45 {
  46   // Range holds an integer or pointer.
  47   VR_IRANGE,
  48   // Floating point range.
  49   VR_FRANGE,
  50   // Range holds an unsupported type.
  51   VR_UNKNOWN
  52 };
  53
  54 // Abstract class for ranges of any of the supported types.
  55 //
  56 // To query what types ranger and the entire ecosystem can support,
  57 // use Value_Range::supports_type_p(tree type).  This is a static
  58 // method available independently of any vrange object.
  59 //
  60 // To query what a given vrange variant can support, use:
  61 //    irange::supports_p ()
  62 //    frange::supports_p ()
  63 //    etc
  64 //
  65 // To query what a range object can support, use:
  66 //    void foo (vrange &v, irange &i, frange &f)
  67 //    {
  68 //      if (v.supports_type_p (type)) ...
  69 //      if (i.supports_type_p (type)) ...
  70 //      if (f.supports_type_p (type)) ...
  71 //    }
  72
  73 class vrange
  74 {
  75   template <typename T> friend bool is_a (vrange &);
  76   friend class Value_Range;
  77 public:
  78   virtual void accept (const class vrange_visitor &v) const = 0;
  79   virtual void set (tree, tree, value_range_kind = VR_RANGE);
  80   virtual tree type () const;
  81   virtual bool supports_type_p (const_tree type) const;
  82   virtual void set_varying (tree type);
  83   virtual void set_undefined ();
  84   virtual bool union_ (const vrange &);
  85   virtual bool intersect (const vrange &);
  86   virtual bool singleton_p (tree *result = NULL) const;
  87   virtual bool contains_p (tree cst) const;
  88   virtual bool zero_p () const;
  89   virtual bool nonzero_p () const;
  90   virtual void set_nonzero (tree type);
  91   virtual void set_zero (tree type);
  92   virtual void set_nonnegative (tree type);
  93   virtual bool fits_p (const vrange &r) const;
  94
  95   bool varying_p () const;
  96   bool undefined_p () const;
  97   vrange& operator= (const vrange &);
  98   bool operator== (const vrange &) const;
  99   bool operator!= (const vrange &r) const { return !(*this == r); }
 100   void dump (FILE *) const;
 101
 102   enum value_range_kind kind () const;          // DEPRECATED
 103
 104 protected:
 105   ENUM_BITFIELD(value_range_kind) m_kind : 8;
 106   ENUM_BITFIELD(value_range_discriminator) m_discriminator : 4;
 107 };
 108
 109 // An integer range without any storage.
 110
 111 class GTY((user)) irange : public vrange
 112 {
 113   friend class vrange_allocator;
 114   friend class irange_storage_slot; // For legacy_mode_p checks.
 115 public:
 116   // In-place setters.
 117   virtual void set (tree, tree, value_range_kind = VR_RANGE) override;
 118   virtual void set_nonzero (tree type) override;
 119   virtual void set_zero (tree type) override;
 120   virtual void set_nonnegative (tree type) override;
 121   virtual void set_varying (tree type) override;
 122   virtual void set_undefined () override;
 123
 124   // Range types.
 125   static bool supports_p (const_tree type);
 126   virtual bool supports_type_p (const_tree type) const override;
 127   virtual tree type () const override;
 128
 129   // Iteration over sub-ranges.
 130   unsigned num_pairs () const;
 131   wide_int lower_bound (unsigned = 0) const;
 132   wide_int upper_bound (unsigned) const;
 133   wide_int upper_bound () const;
 134
 135   // Predicates.
 136   virtual bool zero_p () const override;
 137   virtual bool nonzero_p () const override;
 138   virtual bool singleton_p (tree *result = NULL) const override;
 139   virtual bool contains_p (tree cst) const override;
 140
 141   // In-place operators.
 142   virtual bool union_ (const vrange &) override;
 143   virtual bool intersect (const vrange &) override;
 144   void invert ();
 145
 146   // Operator overloads.
 147   irange& operator= (const irange &);
 148   bool operator== (const irange &) const;
 149   bool operator!= (const irange &r) const { return !(*this == r); }
 150
 151   // Misc methods.
 152   virtual bool fits_p (const vrange &r) const override;
 153   virtual void accept (const vrange_visitor &v) const override;
 154
 155   // Nonzero masks.
 156   wide_int get_nonzero_bits () const;
 157   void set_nonzero_bits (const wide_int_ref &bits);
 158
 159   // Deprecated legacy public methods.
 160   tree min () const;                            // DEPRECATED
 161   tree max () const;                            // DEPRECATED
 162   bool symbolic_p () const;                     // DEPRECATED
 163   bool constant_p () const;                     // DEPRECATED
 164   void normalize_symbolics ();                  // DEPRECATED
 165   void normalize_addresses ();                  // DEPRECATED
 166   bool may_contain_p (tree) const;              // DEPRECATED
 167   bool legacy_verbose_union_ (const class irange *);    // DEPRECATED
 168   bool legacy_verbose_intersect (const irange *);       // DEPRECATED
 169
 170 protected:
 171   irange (tree *, unsigned);
 172   // potential promotion to public?
 173   tree tree_lower_bound (unsigned = 0) const;
 174   tree tree_upper_bound (unsigned) const;
 175   tree tree_upper_bound () const;
 176
 177    // In-place operators.
 178   bool irange_union (const irange &);
 179   bool irange_intersect (const irange &);
 180   void irange_set (tree, tree);
 181   void irange_set_anti_range (tree, tree);
 182   bool irange_contains_p (const irange &) const;
 183   bool irange_single_pair_union (const irange &r);
 184
 185   void normalize_kind ();
 186
 187   bool legacy_mode_p () const;
 188   bool legacy_equal_p (const irange &) const;
 189   void legacy_union (irange *, const irange *);
 190   void legacy_intersect (irange *, const irange *);
 191   void verify_range ();
 192   wide_int legacy_lower_bound (unsigned = 0) const;
 193   wide_int legacy_upper_bound (unsigned) const;
 194   int value_inside_range (tree) const;
 195   bool maybe_anti_range () const;
 196   void copy_to_legacy (const irange &);
 197   void copy_legacy_to_multi_range (const irange &);
 198
 199 private:
 200   friend void gt_ggc_mx (irange *);
 201   friend void gt_pch_nx (irange *);
 202   friend void gt_pch_nx (irange *, gt_pointer_operator, void *);
 203
 204   void irange_set_1bit_anti_range (tree, tree);
 205   bool varying_compatible_p () const;
 206   void set_nonzero_bits (tree mask);
 207   bool intersect_nonzero_bits (const irange &r);
 208   bool union_nonzero_bits (const irange &r);
 209
 210   bool intersect (const wide_int& lb, const wide_int& ub);
 211   unsigned char m_num_ranges;
 212   unsigned char m_max_ranges;
 213   tree m_nonzero_mask;
 214   tree *m_base;
 215 };
 216
 217 // Here we describe an irange with N pairs of ranges.  The storage for
 218 // the pairs is embedded in the class as an array.
 219
 220 template<unsigned N>
 221 class GTY((user)) int_range : public irange
 222 {
 223 public:
 224   int_range ();
 225   int_range (tree, tree, value_range_kind = VR_RANGE);
 226   int_range (tree type, const wide_int &, const wide_int &,
 227              value_range_kind = VR_RANGE);
 228   int_range (tree type);
 229   int_range (const int_range &);
 230   int_range (const irange &);
 231   virtual ~int_range () = default;
 232   int_range& operator= (const int_range &);
 233 private:
 234   template <unsigned X> friend void gt_ggc_mx (int_range<X> *);
 235   template <unsigned X> friend void gt_pch_nx (int_range<X> *);
 236   template <unsigned X> friend void gt_pch_nx (int_range<X> *,
 237                                                gt_pointer_operator, void *);
 238
 239   // ?? These stubs are for ipa-prop.cc which use a value_range in a
 240   // hash_traits.  hash-traits.h defines an extern of gt_ggc_mx (T &)
 241   // instead of picking up the gt_ggc_mx (T *) version.
 242   friend void gt_ggc_mx (int_range<1> *&);
 243   friend void gt_pch_nx (int_range<1> *&);
 244
 245   tree m_ranges[N*2];
 246 };
 247
 248 // Unsupported temporaries may be created by ranger before it's known
 249 // they're unsupported, or by vr_values::get_value_range.
 250
 251 class unsupported_range : public vrange
 252 {
 253 public:
 254   unsupported_range ()
 255   {
 256     m_discriminator = VR_UNKNOWN;
 257     set_undefined ();
 258   }
 259   virtual void set_undefined () final override
 260   {
 261     m_kind = VR_UNDEFINED;
 262   }
 263   virtual void accept (const vrange_visitor &v) const override;
 264 };
 265
 266 // Floating point property to represent possible values of a NAN, INF, etc.
 267
 268 class fp_prop
 269 {
 270 public:
 271   enum kind {
 272     UNDEFINED   = 0x0,          // Prop is impossible.
 273     YES         = 0x1,          // Prop is definitely set.
 274     NO          = 0x2,          // Prop is definitely not set.
 275     VARYING     = (YES | NO)    // Prop may hold.
 276   };
 277   fp_prop (kind f) : m_kind (f) { }
 278   bool varying_p () const { return m_kind == VARYING; }
 279   bool undefined_p () const { return m_kind == UNDEFINED; }
 280   bool yes_p () const { return m_kind == YES; }
 281   bool no_p () const { return m_kind == NO; }
 282 private:
 283   unsigned char m_kind : 2;
 284 };
 285
 286 // Accessors for individual FP properties.
 287
 288 #define FP_PROP_ACCESSOR(NAME) \
 289   void NAME##_set_varying () { u.bits.NAME = fp_prop::VARYING; }        \
 290   void NAME##_set_yes () { u.bits.NAME = fp_prop::YES; }        \
 291   void NAME##_set_no () { u.bits.NAME = fp_prop::NO; }  \
 292   bool NAME##_varying_p () const { return u.bits.NAME == fp_prop::VARYING; } \
 293   bool NAME##_undefined_p () const { return u.bits.NAME == fp_prop::UNDEFINED; } \
 294   bool NAME##_yes_p () const { return u.bits.NAME == fp_prop::YES; }    \
 295   bool NAME##_no_p () const { return u.bits.NAME == fp_prop::NO; } \
 296   fp_prop get_##NAME () const                              \
 297   { return fp_prop ((fp_prop::kind) u.bits.NAME); } \
 298   void set_##NAME (fp_prop::kind f) { u.bits.NAME = f; }
 299
 300 // Aggregate of all the FP properties in an frange packed into one
 301 // structure to save space.  Using explicit fp_prop's in the frange,
 302 // would take one byte per property because of padding.  Instead, we
 303 // can save all properties into one byte.
 304
 305 class frange_props
 306 {
 307 public:
 308   frange_props () { set_varying (); }
 309   void set_varying () { u.bytes = 0xff; }
 310   void set_undefined () { u.bytes = 0; }
 311   bool varying_p () { return u.bytes == 0xff; }
 312   bool undefined_p () { return u.bytes == 0; }
 313   bool union_ (const frange_props &other);
 314   bool intersect (const frange_props &other);
 315   bool operator== (const frange_props &other) const;
 316   FP_PROP_ACCESSOR(nan)
 317   FP_PROP_ACCESSOR(inf)
 318   FP_PROP_ACCESSOR(ninf)
 319 private:
 320   union {
 321     struct {
 322       unsigned char nan : 2;
 323       unsigned char inf : 2;
 324       unsigned char ninf : 2;
 325     } bits;
 326     unsigned char bytes;
 327   } u;
 328 };
 329
 330 // Accessors for getting/setting all FP properties at once.
 331
 332 #define FRANGE_PROP_ACCESSOR(NAME)                              \
 333   fp_prop get_##NAME () const { return m_props.get_##NAME (); } \
 334   void set_##NAME (fp_prop::kind f)                             \
 335   {                                                             \
 336     m_props.set_##NAME (f);                                     \
 337     normalize_kind ();                                          \
 338   }
 339
 340 // A floating point range.
 341
 342 class frange : public vrange
 343 {
 344   friend class frange_storage_slot;
 345 public:
 346   frange ();
 347   frange (const frange &);
 348   static bool supports_p (const_tree type)
 349   {
 350     return SCALAR_FLOAT_TYPE_P (type);
 351   }
 352   virtual tree type () const override;
 353   virtual void set (tree, tree, value_range_kind = VR_RANGE) override;
 354   virtual void set_varying (tree type) override;
 355   virtual void set_undefined () override;
 356   virtual bool union_ (const vrange &) override;
 357   virtual bool intersect (const vrange &) override;
 358   virtual bool supports_type_p (const_tree type) const override;
 359   virtual void accept (const vrange_visitor &v) const override;
 360   frange& operator= (const frange &);
 361   bool operator== (const frange &) const;
 362   bool operator!= (const frange &r) const { return !(*this == r); }
 363
 364   // Each fp_prop can be accessed with get_PROP() and set_PROP().
 365   FRANGE_PROP_ACCESSOR(nan)
 366   FRANGE_PROP_ACCESSOR(inf)
 367   FRANGE_PROP_ACCESSOR(ninf)
 368 private:
 369   void verify_range ();
 370   bool normalize_kind ();
 371
 372   frange_props m_props;
 373   tree m_type;
 374 };
 375
 376 // is_a<> and as_a<> implementation for vrange.
 377
 378 // Anything we haven't specialized is a hard fail.
 379 template <typename T>
 380 inline bool
 381 is_a (vrange &)
 382 {
 383   gcc_unreachable ();
 384   return false;
 385 }
 386
 387 template <typename T>
 388 inline bool
 389 is_a (const vrange &v)
 390 {
 391   // Reuse is_a <vrange> to implement the const version.
 392   const T &derived = static_cast<const T &> (v);
 393   return is_a <T> (const_cast<T &> (derived));
 394 }
 395
 396 template <typename T>
 397 inline T &
 398 as_a (vrange &v)
 399 {
 400   gcc_checking_assert (is_a <T> (v));
 401   return static_cast <T &> (v);
 402 }
 403
 404 template <typename T>
 405 inline const T &
 406 as_a (const vrange &v)
 407 {
 408   gcc_checking_assert (is_a <T> (v));
 409   return static_cast <const T &> (v);
 410 }
 411
 412 // Specializations for the different range types.
 413
 414 template <>
 415 inline bool
 416 is_a <irange> (vrange &v)
 417 {
 418   return v.m_discriminator == VR_IRANGE;
 419 }
 420
 421 template <>
 422 inline bool
 423 is_a <frange> (vrange &v)
 424 {
 425   return v.m_discriminator == VR_FRANGE;
 426 }
 427
 428 class vrange_visitor
 429 {
 430 public:
 431   virtual void visit (const irange &) const { }
 432   virtual void visit (const frange &) const { }
 433   virtual void visit (const unsupported_range &) const { }
 434 };
 435
 436 // This is a special int_range<1> with only one pair, plus
 437 // VR_ANTI_RANGE magic to describe slightly more than can be described
 438 // in one pair.  It is described in the code as a "legacy range" (as
 439 // opposed to multi-ranges which have multiple sub-ranges).  It is
 440 // provided for backward compatibility with code that has not been
 441 // converted to multi-range irange's.
 442 //
 443 // There are copy operators to seamlessly copy to/fro multi-ranges.
 444 typedef int_range<1> value_range;
 445
 446 // This is an "infinite" precision irange for use in temporary
 447 // calculations.
 448 typedef int_range<255> int_range_max;
 449
 450 // This is an "infinite" precision range object for use in temporary
 451 // calculations for any of the handled types.  The object can be
 452 // transparently used as a vrange.
 453
 454 class Value_Range
 455 {
 456 public:
 457   Value_Range ();
 458   Value_Range (const vrange &r);
 459   Value_Range (tree type);
 460   Value_Range (const Value_Range &);
 461   void set_type (tree type);
 462   vrange& operator= (const vrange &);
 463   bool operator== (const Value_Range &r) const;
 464   bool operator!= (const Value_Range &r) const;
 465   operator vrange &();
 466   operator const vrange &() const;
 467   void dump (FILE *) const;
 468   static bool supports_type_p (const_tree type);
 469
 470   // Convenience methods for vrange compatability.
 471   void set (tree min, tree max, value_range_kind kind = VR_RANGE)
 472     { return m_vrange->set (min, max, kind); }
 473   tree type () { return m_vrange->type (); }
 474   enum value_range_kind kind () { return m_vrange->kind (); }
 475   bool varying_p () const { return m_vrange->varying_p (); }
 476   bool undefined_p () const { return m_vrange->undefined_p (); }
 477   void set_varying (tree type) { m_vrange->set_varying (type); }
 478   void set_undefined () { m_vrange->set_undefined (); }
 479   bool union_ (const vrange &r) { return m_vrange->union_ (r); }
 480   bool intersect (const vrange &r) { return m_vrange->intersect (r); }
 481   bool singleton_p (tree *result = NULL) const
 482     { return m_vrange->singleton_p (result); }
 483   bool zero_p () const { return m_vrange->zero_p (); }
 484   wide_int lower_bound () const; // For irange/prange compatability.
 485   wide_int upper_bound () const; // For irange/prange compatability.
 486   void accept (const vrange_visitor &v) const { m_vrange->accept (v); }
 487 private:
 488   void init (tree type);
 489   unsupported_range m_unsupported;
 490   vrange *m_vrange;
 491   int_range_max m_irange;
 492   frange m_frange;
 493 };
 494
 495 inline
 496 Value_Range::Value_Range ()
 497 {
 498   m_vrange = &m_unsupported;
 499 }
 500
 501 // Copy constructor from a vrange.
 502
 503 inline
 504 Value_Range::Value_Range (const vrange &r)
 505 {
 506   *this = r;
 507 }
 508
 509 // Copy constructor from a TYPE.  The range of the temporary is set to
 510 // UNDEFINED.
 511
 512 inline
 513 Value_Range::Value_Range (tree type)
 514 {
 515   init (type);
 516 }
 517
 518 inline
 519 Value_Range::Value_Range (const Value_Range &r)
 520 {
 521   m_vrange = r.m_vrange;
 522 }
 523
 524 // Initialize object so it is possible to store temporaries of TYPE
 525 // into it.
 526
 527 inline void
 528 Value_Range::init (tree type)
 529 {
 530   gcc_checking_assert (TYPE_P (type));
 531
 532   if (irange::supports_p (type))
 533     m_vrange = &m_irange;
 534   else if (frange::supports_p (type))
 535     m_vrange = &m_frange;
 536   else
 537     m_vrange = &m_unsupported;
 538 }
 539
 540 // Set the temporary to allow storing temporaries of TYPE.  The range
 541 // of the temporary is set to UNDEFINED.
 542
 543 inline void
 544 Value_Range::set_type (tree type)
 545 {
 546   init (type);
 547   m_vrange->set_undefined ();
 548 }
 549
 550 // Assignment operator for temporaries.  Copying incompatible types is
 551 // allowed.
 552
 553 inline vrange &
 554 Value_Range::operator= (const vrange &r)
 555 {
 556   if (is_a <irange> (r))
 557     {
 558       m_irange = as_a <irange> (r);
 559       m_vrange = &m_irange;
 560     }
 561   else if (is_a <frange> (r))
 562     {
 563       m_frange = as_a <frange> (r);
 564       m_vrange = &m_frange;
 565     }
 566   else
 567     gcc_unreachable ();
 568
 569   return *m_vrange;
 570 }
 571
 572 inline bool
 573 Value_Range::operator== (const Value_Range &r) const
 574 {
 575   return *m_vrange == *r.m_vrange;
 576 }
 577
 578 inline bool
 579 Value_Range::operator!= (const Value_Range &r) const
 580 {
 581   return *m_vrange != *r.m_vrange;
 582 }
 583
 584 inline
 585 Value_Range::operator vrange &()
 586 {
 587   return *m_vrange;
 588 }
 589
 590 inline
 591 Value_Range::operator const vrange &() const
 592 {
 593   return *m_vrange;
 594 }
 595
 596 // Return TRUE if TYPE is supported by the vrange infrastructure.
 597
 598 inline bool
 599 Value_Range::supports_type_p (const_tree type)
 600 {
 601   return irange::supports_p (type) || frange::supports_p (type);
 602 }
 603
 604 // Returns true for an old-school value_range as described above.
 605 inline bool
 606 irange::legacy_mode_p () const
 607 {
 608   return m_max_ranges == 1;
 609 }
 610
 611 extern bool range_has_numeric_bounds_p (const irange *);
 612 extern bool ranges_from_anti_range (const value_range *,
 613                                     value_range *, value_range *);
 614 extern void dump_value_range (FILE *, const vrange *);
 615 extern bool vrp_val_is_min (const_tree);
 616 extern bool vrp_val_is_max (const_tree);
 617 extern bool vrp_operand_equal_p (const_tree, const_tree);
 618
 619 inline value_range_kind
 620 vrange::kind () const
 621 {
 622   return m_kind;
 623 }
 624
 625 // Number of sub-ranges in a range.
 626
 627 inline unsigned
 628 irange::num_pairs () const
 629 {
 630   if (m_kind == VR_ANTI_RANGE)
 631     return constant_p () ? 2 : 1;
 632   else
 633     return m_num_ranges;
 634 }
 635
 636 inline tree
 637 irange::type () const
 638 {
 639   gcc_checking_assert (m_num_ranges > 0);
 640   return TREE_TYPE (m_base[0]);
 641 }
 642
 643 // Return the lower bound of a sub-range expressed as a tree.  PAIR is
 644 // the sub-range in question.
 645
 646 inline tree
 647 irange::tree_lower_bound (unsigned pair) const
 648 {
 649   return m_base[pair * 2];
 650 }
 651
 652 // Return the upper bound of a sub-range expressed as a tree.  PAIR is
 653 // the sub-range in question.
 654
 655 inline tree
 656 irange::tree_upper_bound (unsigned pair) const
 657 {
 658   return m_base[pair * 2 + 1];
 659 }
 660
 661 // Return the highest bound of a range expressed as a tree.
 662
 663 inline tree
 664 irange::tree_upper_bound () const
 665 {
 666   gcc_checking_assert (m_num_ranges);
 667   return tree_upper_bound (m_num_ranges - 1);
 668 }
 669
 670 inline tree
 671 irange::min () const
 672 {
 673   return tree_lower_bound (0);
 674 }
 675
 676 inline tree
 677 irange::max () const
 678 {
 679   if (m_num_ranges)
 680     return tree_upper_bound ();
 681   else
 682     return NULL;
 683 }
 684
 685 inline bool
 686 irange::varying_compatible_p () const
 687 {
 688   if (m_num_ranges != 1)
 689     return false;
 690
 691   tree l = m_base[0];
 692   tree u = m_base[1];
 693   tree t = TREE_TYPE (l);
 694
 695   if (m_kind == VR_VARYING && t == error_mark_node)
 696     return true;
 697
 698   unsigned prec = TYPE_PRECISION (t);
 699   signop sign = TYPE_SIGN (t);
 700   if (INTEGRAL_TYPE_P (t))
 701     return (wi::to_wide (l) == wi::min_value (prec, sign)
 702             && wi::to_wide (u) == wi::max_value (prec, sign)
 703             && !m_nonzero_mask);
 704   if (POINTER_TYPE_P (t))
 705     return (wi::to_wide (l) == 0
 706             && wi::to_wide (u) == wi::max_value (prec, sign));
 707   return true;
 708 }
 709
 710 inline bool
 711 vrange::varying_p () const
 712 {
 713   return m_kind == VR_VARYING;
 714 }
 715
 716 inline bool
 717 vrange::undefined_p () const
 718 {
 719   return m_kind == VR_UNDEFINED;
 720 }
 721
 722 inline bool
 723 irange::zero_p () const
 724 {
 725   return (m_kind == VR_RANGE && m_num_ranges == 1
 726           && integer_zerop (tree_lower_bound (0))
 727           && integer_zerop (tree_upper_bound (0)));
 728 }
 729
 730 inline bool
 731 irange::nonzero_p () const
 732 {
 733   if (undefined_p ())
 734     return false;
 735
 736   tree zero = build_zero_cst (type ());
 737   return *this == int_range<1> (zero, zero, VR_ANTI_RANGE);
 738 }
 739
 740 inline bool
 741 irange::supports_p (const_tree type)
 742 {
 743   return INTEGRAL_TYPE_P (type) || POINTER_TYPE_P (type);
 744 }
 745
 746 inline bool
 747 range_includes_zero_p (const irange *vr)
 748 {
 749   if (vr->undefined_p ())
 750     return false;
 751
 752   if (vr->varying_p ())
 753     return true;
 754
 755   return vr->may_contain_p (build_zero_cst (vr->type ()));
 756 }
 757
 758 inline void
 759 gt_ggc_mx (irange *x)
 760 {
 761   for (unsigned i = 0; i < x->m_num_ranges; ++i)
 762     {
 763       gt_ggc_mx (x->m_base[i * 2]);
 764       gt_ggc_mx (x->m_base[i * 2 + 1]);
 765     }
 766   if (x->m_nonzero_mask)
 767     gt_ggc_mx (x->m_nonzero_mask);
 768 }
 769
 770 inline void
 771 gt_pch_nx (irange *x)
 772 {
 773   for (unsigned i = 0; i < x->m_num_ranges; ++i)
 774     {
 775       gt_pch_nx (x->m_base[i * 2]);
 776       gt_pch_nx (x->m_base[i * 2 + 1]);
 777     }
 778   if (x->m_nonzero_mask)
 779     gt_pch_nx (x->m_nonzero_mask);
 780 }
 781
 782 inline void
 783 gt_pch_nx (irange *x, gt_pointer_operator op, void *cookie)
 784 {
 785   for (unsigned i = 0; i < x->m_num_ranges; ++i)
 786     {
 787       op (&x->m_base[i * 2], NULL, cookie);
 788       op (&x->m_base[i * 2 + 1], NULL, cookie);
 789     }
 790   if (x->m_nonzero_mask)
 791     op (&x->m_nonzero_mask, NULL, cookie);
 792 }
 793
 794 template<unsigned N>
 795 inline void
 796 gt_ggc_mx (int_range<N> *x)
 797 {
 798   gt_ggc_mx ((irange *) x);
 799 }
 800
 801 template<unsigned N>
 802 inline void
 803 gt_pch_nx (int_range<N> *x)
 804 {
 805   gt_pch_nx ((irange *) x);
 806 }
 807
 808 template<unsigned N>
 809 inline void
 810 gt_pch_nx (int_range<N> *x, gt_pointer_operator op, void *cookie)
 811 {
 812   gt_pch_nx ((irange *) x, op, cookie);
 813 }
 814
 815 // Constructors for irange
 816
 817 inline
 818 irange::irange (tree *base, unsigned nranges)
 819 {
 820   m_discriminator = VR_IRANGE;
 821   m_base = base;
 822   m_max_ranges = nranges;
 823   set_undefined ();
 824 }
 825
 826 // Constructors for int_range<>.
 827
 828 template<unsigned N>
 829 inline
 830 int_range<N>::int_range ()
 831   : irange (m_ranges, N)
 832 {
 833 }
 834
 835 template<unsigned N>
 836 int_range<N>::int_range (const int_range &other)
 837   : irange (m_ranges, N)
 838 {
 839   irange::operator= (other);
 840 }
 841
 842 template<unsigned N>
 843 int_range<N>::int_range (tree min, tree max, value_range_kind kind)
 844   : irange (m_ranges, N)
 845 {
 846   irange::set (min, max, kind);
 847 }
 848
 849 template<unsigned N>
 850 int_range<N>::int_range (tree type)
 851   : irange (m_ranges, N)
 852 {
 853   set_varying (type);
 854 }
 855
 856 template<unsigned N>
 857 int_range<N>::int_range (tree type, const wide_int &wmin, const wide_int &wmax,
 858                          value_range_kind kind)
 859   : irange (m_ranges, N)
 860 {
 861   tree min = wide_int_to_tree (type, wmin);
 862   tree max = wide_int_to_tree (type, wmax);
 863   set (min, max, kind);
 864 }
 865
 866 template<unsigned N>
 867 int_range<N>::int_range (const irange &other)
 868   : irange (m_ranges, N)
 869 {
 870   irange::operator= (other);
 871 }
 872
 873 template<unsigned N>
 874 int_range<N>&
 875 int_range<N>::operator= (const int_range &src)
 876 {
 877   irange::operator= (src);
 878   return *this;
 879 }
 880
 881 inline void
 882 irange::set_undefined ()
 883 {
 884   m_kind = VR_UNDEFINED;
 885   m_num_ranges = 0;
 886   m_nonzero_mask = NULL;
 887 }
 888
 889 inline void
 890 irange::set_varying (tree type)
 891 {
 892   m_kind = VR_VARYING;
 893   m_num_ranges = 1;
 894   m_nonzero_mask = NULL;
 895
 896   if (INTEGRAL_TYPE_P (type))
 897     {
 898       // Strict enum's require varying to be not TYPE_MIN/MAX, but rather
 899       // min_value and max_value.
 900       wide_int min = wi::min_value (TYPE_PRECISION (type), TYPE_SIGN (type));
 901       wide_int max = wi::max_value (TYPE_PRECISION (type), TYPE_SIGN (type));
 902       if (wi::eq_p (max, wi::to_wide (TYPE_MAX_VALUE (type)))
 903           && wi::eq_p (min, wi::to_wide (TYPE_MIN_VALUE (type))))
 904         {
 905           m_base[0] = TYPE_MIN_VALUE (type);
 906           m_base[1] = TYPE_MAX_VALUE (type);
 907         }
 908       else
 909         {
 910           m_base[0] = wide_int_to_tree (type, min);
 911           m_base[1] = wide_int_to_tree (type, max);
 912         }
 913     }
 914   else if (POINTER_TYPE_P (type))
 915     {
 916       m_base[0] = build_int_cst (type, 0);
 917       m_base[1] = build_int_cst (type, -1);
 918     }
 919   else
 920     m_base[0] = m_base[1] = error_mark_node;
 921 }
 922
 923 // Return the lower bound of a sub-range.  PAIR is the sub-range in
 924 // question.
 925
 926 inline wide_int
 927 irange::lower_bound (unsigned pair) const
 928 {
 929   if (legacy_mode_p ())
 930     return legacy_lower_bound (pair);
 931   gcc_checking_assert (m_num_ranges > 0);
 932   gcc_checking_assert (pair + 1 <= num_pairs ());
 933   return wi::to_wide (tree_lower_bound (pair));
 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   if (legacy_mode_p ())
 943     return legacy_upper_bound (pair);
 944   gcc_checking_assert (m_num_ranges > 0);
 945   gcc_checking_assert (pair + 1 <= num_pairs ());
 946   return wi::to_wide (tree_upper_bound (pair));
 947 }
 948
 949 // Return the highest bound of a range.
 950
 951 inline wide_int
 952 irange::upper_bound () const
 953 {
 954   unsigned pairs = num_pairs ();
 955   gcc_checking_assert (pairs > 0);
 956   return upper_bound (pairs - 1);
 957 }
 958
 959 inline bool
 960 irange::union_ (const vrange &r)
 961 {
 962   dump_flags_t m_flags = dump_flags;
 963   dump_flags &= ~TDF_DETAILS;
 964   bool ret = irange::legacy_verbose_union_ (&as_a <irange> (r));
 965   dump_flags = m_flags;
 966   return ret;
 967 }
 968
 969 inline bool
 970 irange::intersect (const vrange &r)
 971 {
 972   dump_flags_t m_flags = dump_flags;
 973   dump_flags &= ~TDF_DETAILS;
 974   bool ret = irange::legacy_verbose_intersect (&as_a <irange> (r));
 975   dump_flags = m_flags;
 976   return ret;
 977 }
 978
 979 // Set value range VR to a nonzero range of type TYPE.
 980
 981 inline void
 982 irange::set_nonzero (tree type)
 983 {
 984   tree zero = build_int_cst (type, 0);
 985   if (legacy_mode_p ())
 986     set (zero, zero, VR_ANTI_RANGE);
 987   else
 988     irange_set_anti_range (zero, zero);
 989 }
 990
 991 // Set value range VR to a ZERO range of type TYPE.
 992
 993 inline void
 994 irange::set_zero (tree type)
 995 {
 996   tree z = build_int_cst (type, 0);
 997   if (legacy_mode_p ())
 998     set (z, z);
 999   else
1000     irange_set (z, z);
1001 }
1002
1003 // Normalize a range to VARYING or UNDEFINED if possible.
1004
1005 inline void
1006 irange::normalize_kind ()
1007 {
1008   if (m_num_ranges == 0)
1009     set_undefined ();
1010   else if (varying_compatible_p ())
1011     {
1012       if (m_kind == VR_RANGE)
1013         m_kind = VR_VARYING;
1014       else if (m_kind == VR_ANTI_RANGE)
1015         set_undefined ();
1016       else
1017         gcc_unreachable ();
1018     }
1019 }
1020
1021 // Return the maximum value for TYPE.
1022
1023 inline tree
1024 vrp_val_max (const_tree type)
1025 {
1026   if (INTEGRAL_TYPE_P (type))
1027     return TYPE_MAX_VALUE (type);
1028   if (POINTER_TYPE_P (type))
1029     {
1030       wide_int max = wi::max_value (TYPE_PRECISION (type), TYPE_SIGN (type));
1031       return wide_int_to_tree (const_cast<tree> (type), max);
1032     }
1033   if (frange::supports_p (type))
1034     {
1035       REAL_VALUE_TYPE real;
1036       real_inf (&real);
1037       return build_real (const_cast <tree> (type), real);
1038     }
1039   return NULL_TREE;
1040 }
1041
1042 // Return the minimum value for TYPE.
1043
1044 inline tree
1045 vrp_val_min (const_tree type)
1046 {
1047   if (INTEGRAL_TYPE_P (type))
1048     return TYPE_MIN_VALUE (type);
1049   if (POINTER_TYPE_P (type))
1050     return build_zero_cst (const_cast<tree> (type));
1051   if (frange::supports_p (type))
1052     {
1053       REAL_VALUE_TYPE real, real_ninf;
1054       real_inf (&real);
1055       real_ninf = real_value_negate (&real);
1056       return build_real (const_cast <tree> (type), real_ninf);
1057     }
1058   return NULL_TREE;
1059 }
1060
1061 // Supporting methods for frange.
1062
1063 inline bool
1064 frange_props::operator== (const frange_props &other) const
1065 {
1066   return u.bytes == other.u.bytes;
1067 }
1068
1069 inline bool
1070 frange_props::union_ (const frange_props &other)
1071 {
1072   unsigned char saved = u.bytes;
1073   u.bytes |= other.u.bytes;
1074   return u.bytes != saved;
1075 }
1076
1077 inline bool
1078 frange_props::intersect (const frange_props &other)
1079 {
1080   unsigned char saved = u.bytes;
1081   u.bytes &= other.u.bytes;
1082   return u.bytes != saved;
1083 }
1084
1085 inline
1086 frange::frange ()
1087 {
1088   m_discriminator = VR_FRANGE;
1089   set_undefined ();
1090 }
1091
1092 inline
1093 frange::frange (const frange &src)
1094 {
1095   m_discriminator = VR_FRANGE;
1096   *this = src;
1097 }
1098
1099 inline tree
1100 frange::type () const
1101 {
1102   return m_type;
1103 }
1104
1105 inline void
1106 frange::set_varying (tree type)
1107 {
1108   m_kind = VR_VARYING;
1109   m_type = type;
1110   m_props.set_varying ();
1111 }
1112
1113 inline void
1114 frange::set_undefined ()
1115 {
1116   m_kind = VR_UNDEFINED;
1117   m_type = NULL;
1118   m_props.set_undefined ();
1119 }
1120
1121 #endif // GCC_VALUE_RANGE_H