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