sdcc/support/cpp/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 #if 0 // sdcpp ndef GCC_VALUE_RANGE_H
  23 #define GCC_VALUE_RANGE_H
  24
  25 // Types of value ranges.
  26 enum value_range_kind
  27 {
  28   /* Empty range.  */
  29   VR_UNDEFINED,
  30   /* Range spans the entire domain.  */
  31   VR_VARYING,
  32   /* Range is [MIN, MAX].  */
  33   VR_RANGE,
  34   /* Range is ~[MIN, MAX].  */
  35   VR_ANTI_RANGE,
  36   /* Range is a nice guy.  */
  37   VR_LAST
  38 };
  39
  40 // Range of values that can be associated with an SSA_NAME.
  41 //
  42 // This is the base class without any storage.
  43
  44 class GTY((user)) irange
  45 {
  46   friend class irange_allocator;
  47 public:
  48   // In-place setters.
  49   void set (tree, tree, value_range_kind = VR_RANGE);
  50   void set_nonzero (tree);
  51   void set_zero (tree);
  52   void set_varying (tree type);
  53   void set_undefined ();
  54
  55   // Range types.
  56   static bool supports_type_p (tree);
  57   tree type () const;
  58
  59   // Iteration over sub-ranges.
  60   unsigned num_pairs () const;
  61   wide_int lower_bound (unsigned = 0) const;
  62   wide_int upper_bound (unsigned) const;
  63   wide_int upper_bound () const;
  64
  65   // Predicates.
  66   bool zero_p () const;
  67   bool nonzero_p () const;
  68   bool undefined_p () const;
  69   bool varying_p () const;
  70   bool singleton_p (tree *result = NULL) const;
  71   bool contains_p (tree) const;
  72
  73   // In-place operators.
  74   void union_ (const irange &);
  75   void intersect (const irange &);
  76   void intersect (const wide_int& lb, const wide_int& ub);
  77   void invert ();
  78
  79   // Operator overloads.
  80   irange& operator= (const irange &);
  81   bool operator== (const irange &) const;
  82   bool operator!= (const irange &r) const { return !(*this == r); }
  83
  84   // Misc methods.
  85   bool fits_p (const irange &r) { return m_max_ranges >= r.num_pairs (); }
  86   void dump (FILE * = stderr) const;
  87   void debug () const;
  88
  89   // Deprecated legacy public methods.
  90   enum value_range_kind kind () const;          // DEPRECATED
  91   tree min () const;                            // DEPRECATED
  92   tree max () const;                            // DEPRECATED
  93   bool symbolic_p () const;                     // DEPRECATED
  94   bool constant_p () const;                     // DEPRECATED
  95   void normalize_symbolics ();                  // DEPRECATED
  96   void normalize_addresses ();                  // DEPRECATED
  97   bool may_contain_p (tree) const;              // DEPRECATED
  98   void set (tree);                              // DEPRECATED
  99   bool equal_p (const irange &) const;          // DEPRECATED
 100   void union_ (const class irange *);           // DEPRECATED
 101   void intersect (const irange *);              // DEPRECATED
 102
 103 protected:
 104   irange (tree *, unsigned);
 105   // potential promotion to public?
 106   tree tree_lower_bound (unsigned = 0) const;
 107   tree tree_upper_bound (unsigned) const;
 108   tree tree_upper_bound () const;
 109
 110    // In-place operators.
 111   void irange_union (const irange &);
 112   void irange_intersect (const irange &);
 113   void irange_set (tree, tree);
 114   void irange_set_anti_range (tree, tree);
 115
 116   void normalize_kind ();
 117
 118   bool legacy_mode_p () const;
 119   bool legacy_equal_p (const irange &) const;
 120   void legacy_union (irange *, const irange *);
 121   void legacy_intersect (irange *, const irange *);
 122   void verify_range ();
 123   wide_int legacy_lower_bound (unsigned = 0) const;
 124   wide_int legacy_upper_bound (unsigned) const;
 125   int value_inside_range (tree) const;
 126   bool maybe_anti_range () const;
 127   void copy_to_legacy (const irange &);
 128   void copy_legacy_to_multi_range (const irange &);
 129
 130 private:
 131   friend void gt_ggc_mx (irange *);
 132   friend void gt_pch_nx (irange *);
 133   friend void gt_pch_nx (irange *, gt_pointer_operator, void *);
 134
 135   void irange_set_1bit_anti_range (tree, tree);
 136   bool varying_compatible_p () const;
 137
 138   unsigned char m_num_ranges;
 139   unsigned char m_max_ranges;
 140   ENUM_BITFIELD(value_range_kind) m_kind : 8;
 141   tree *m_base;
 142 };
 143
 144 // Here we describe an irange with N pairs of ranges.  The storage for
 145 // the pairs is embedded in the class as an array.
 146
 147 template<unsigned N>
 148 class GTY((user)) int_range : public irange
 149 {
 150 public:
 151   int_range ();
 152   int_range (tree, tree, value_range_kind = VR_RANGE);
 153   int_range (tree type, const wide_int &, const wide_int &,
 154              value_range_kind = VR_RANGE);
 155   int_range (tree type);
 156   int_range (const int_range &);
 157   int_range (const irange &);
 158   int_range& operator= (const int_range &);
 159 private:
 160   template <unsigned X> friend void gt_ggc_mx (int_range<X> *);
 161   template <unsigned X> friend void gt_pch_nx (int_range<X> *);
 162   template <unsigned X> friend void gt_pch_nx (int_range<X> *,
 163                                                gt_pointer_operator, void *);
 164
 165   // ?? These stubs are for ipa-prop.cc which use a value_range in a
 166   // hash_traits.  hash-traits.h defines an extern of gt_ggc_mx (T &)
 167   // instead of picking up the gt_ggc_mx (T *) version.
 168   friend void gt_ggc_mx (int_range<1> *&);
 169   friend void gt_pch_nx (int_range<1> *&);
 170
 171   tree m_ranges[N*2];
 172 };
 173
 174 // This is a special int_range<1> with only one pair, plus
 175 // VR_ANTI_RANGE magic to describe slightly more than can be described
 176 // in one pair.  It is described in the code as a "legacy range" (as
 177 // opposed to multi-ranges which have multiple sub-ranges).  It is
 178 // provided for backward compatibility with code that has not been
 179 // converted to multi-range irange's.
 180 //
 181 // There are copy operators to seamlessly copy to/fro multi-ranges.
 182 typedef int_range<1> value_range;
 183
 184 // This is an "infinite" precision irange for use in temporary
 185 // calculations.
 186 typedef int_range<255> int_range_max;
 187
 188 // Returns true for an old-school value_range as described above.
 189 inline bool
 190 irange::legacy_mode_p () const
 191 {
 192   return m_max_ranges == 1;
 193 }
 194
 195 extern bool range_has_numeric_bounds_p (const irange *);
 196 extern bool ranges_from_anti_range (const value_range *,
 197                                     value_range *, value_range *);
 198 extern void dump_value_range (FILE *, const irange *);
 199 extern bool vrp_val_is_min (const_tree);
 200 extern bool vrp_val_is_max (const_tree);
 201 extern bool vrp_operand_equal_p (const_tree, const_tree);
 202
 203 inline value_range_kind
 204 irange::kind () const
 205 {
 206   return m_kind;
 207 }
 208
 209 // Number of sub-ranges in a range.
 210
 211 inline unsigned
 212 irange::num_pairs () const
 213 {
 214   if (m_kind == VR_ANTI_RANGE)
 215     return constant_p () ? 2 : 1;
 216   else
 217     return m_num_ranges;
 218 }
 219
 220 inline tree
 221 irange::type () const
 222 {
 223   gcc_checking_assert (m_num_ranges > 0);
 224   return TREE_TYPE (m_base[0]);
 225 }
 226
 227 // Return the lower bound of a sub-range expressed as a tree.  PAIR is
 228 // the sub-range in question.
 229
 230 inline tree
 231 irange::tree_lower_bound (unsigned pair) const
 232 {
 233   return m_base[pair * 2];
 234 }
 235
 236 // Return the upper bound of a sub-range expressed as a tree.  PAIR is
 237 // the sub-range in question.
 238
 239 inline tree
 240 irange::tree_upper_bound (unsigned pair) const
 241 {
 242   return m_base[pair * 2 + 1];
 243 }
 244
 245 // Return the highest bound of a range expressed as a tree.
 246
 247 inline tree
 248 irange::tree_upper_bound () const
 249 {
 250   gcc_checking_assert (m_num_ranges);
 251   return tree_upper_bound (m_num_ranges - 1);
 252 }
 253
 254 inline tree
 255 irange::min () const
 256 {
 257   return tree_lower_bound (0);
 258 }
 259
 260 inline tree
 261 irange::max () const
 262 {
 263   if (m_num_ranges)
 264     return tree_upper_bound ();
 265   else
 266     return NULL;
 267 }
 268
 269 inline bool
 270 irange::varying_compatible_p () const
 271 {
 272   if (m_num_ranges != 1)
 273     return false;
 274
 275   tree l = m_base[0];
 276   tree u = m_base[1];
 277   tree t = TREE_TYPE (l);
 278
 279   if (m_kind == VR_VARYING && t == error_mark_node)
 280     return true;
 281
 282   unsigned prec = TYPE_PRECISION (t);
 283   signop sign = TYPE_SIGN (t);
 284   if (INTEGRAL_TYPE_P (t))
 285     return (wi::to_wide (l) == wi::min_value (prec, sign)
 286             && wi::to_wide (u) == wi::max_value (prec, sign));
 287   if (POINTER_TYPE_P (t))
 288     return (wi::to_wide (l) == 0
 289             && wi::to_wide (u) == wi::max_value (prec, sign));
 290   return true;
 291 }
 292
 293 inline bool
 294 irange::varying_p () const
 295 {
 296   return m_kind == VR_VARYING;
 297 }
 298
 299 inline bool
 300 irange::undefined_p () const
 301 {
 302   return m_kind == VR_UNDEFINED;
 303 }
 304
 305 inline bool
 306 irange::zero_p () const
 307 {
 308   return (m_kind == VR_RANGE && m_num_ranges == 1
 309           && integer_zerop (tree_lower_bound (0))
 310           && integer_zerop (tree_upper_bound (0)));
 311 }
 312
 313 inline bool
 314 irange::nonzero_p () const
 315 {
 316   if (undefined_p ())
 317     return false;
 318
 319   tree zero = build_zero_cst (type ());
 320   return *this == int_range<1> (zero, zero, VR_ANTI_RANGE);
 321 }
 322
 323 inline bool
 324 irange::supports_type_p (tree type)
 325 {
 326   if (type && (INTEGRAL_TYPE_P (type) || POINTER_TYPE_P (type)))
 327     return type;
 328   return false;
 329 }
 330
 331 inline bool
 332 range_includes_zero_p (const irange *vr)
 333 {
 334   if (vr->undefined_p ())
 335     return false;
 336
 337   if (vr->varying_p ())
 338     return true;
 339
 340   return vr->may_contain_p (build_zero_cst (vr->type ()));
 341 }
 342
 343 inline void
 344 gt_ggc_mx (irange *x)
 345 {
 346   for (unsigned i = 0; i < x->m_num_ranges; ++i)
 347     {
 348       gt_ggc_mx (x->m_base[i * 2]);
 349       gt_ggc_mx (x->m_base[i * 2 + 1]);
 350     }
 351 }
 352
 353 inline void
 354 gt_pch_nx (irange *x)
 355 {
 356   for (unsigned i = 0; i < x->m_num_ranges; ++i)
 357     {
 358       gt_pch_nx (x->m_base[i * 2]);
 359       gt_pch_nx (x->m_base[i * 2 + 1]);
 360     }
 361 }
 362
 363 inline void
 364 gt_pch_nx (irange *x, gt_pointer_operator op, void *cookie)
 365 {
 366   for (unsigned i = 0; i < x->m_num_ranges; ++i)
 367     {
 368       op (&x->m_base[i * 2], NULL, cookie);
 369       op (&x->m_base[i * 2 + 1], NULL, cookie);
 370     }
 371 }
 372
 373 template<unsigned N>
 374 inline void
 375 gt_ggc_mx (int_range<N> *x)
 376 {
 377   gt_ggc_mx ((irange *) x);
 378 }
 379
 380 template<unsigned N>
 381 inline void
 382 gt_pch_nx (int_range<N> *x)
 383 {
 384   gt_pch_nx ((irange *) x);
 385 }
 386
 387 template<unsigned N>
 388 inline void
 389 gt_pch_nx (int_range<N> *x, gt_pointer_operator op, void *cookie)
 390 {
 391   gt_pch_nx ((irange *) x, op, cookie);
 392 }
 393
 394 // Constructors for irange
 395
 396 inline
 397 irange::irange (tree *base, unsigned nranges)
 398 {
 399   m_base = base;
 400   m_num_ranges = 0;
 401   m_max_ranges = nranges;
 402   m_kind = VR_UNDEFINED;
 403 }
 404
 405 // Constructors for int_range<>.
 406
 407 template<unsigned N>
 408 inline
 409 int_range<N>::int_range ()
 410   : irange (m_ranges, N)
 411 {
 412 }
 413
 414 template<unsigned N>
 415 int_range<N>::int_range (const int_range &other)
 416   : irange (m_ranges, N)
 417 {
 418   irange::operator= (other);
 419 }
 420
 421 template<unsigned N>
 422 int_range<N>::int_range (tree min, tree max, value_range_kind kind)
 423   : irange (m_ranges, N)
 424 {
 425   irange::set (min, max, kind);
 426 }
 427
 428 template<unsigned N>
 429 int_range<N>::int_range (tree type)
 430   : irange (m_ranges, N)
 431 {
 432   set_varying (type);
 433 }
 434
 435 #if 0 // sdcpp
 436 template<unsigned N>
 437 int_range<N>::int_range (tree type, const wide_int &wmin, const wide_int &wmax,
 438                          value_range_kind kind)
 439   : irange (m_ranges, N)
 440 {
 441   tree min = wide_int_to_tree (type, wmin);
 442   tree max = wide_int_to_tree (type, wmax);
 443   set (min, max, kind);
 444 }
 445 #endif // sdcpp
 446
 447 template<unsigned N>
 448 int_range<N>::int_range (const irange &other)
 449   : irange (m_ranges, N)
 450 {
 451   irange::operator= (other);
 452 }
 453
 454 template<unsigned N>
 455 int_range<N>&
 456 int_range<N>::operator= (const int_range &src)
 457 {
 458   irange::operator= (src);
 459   return *this;
 460 }
 461
 462 inline void
 463 irange::set (tree val)
 464 {
 465   set (val, val);
 466 }
 467
 468 inline void
 469 irange::set_undefined ()
 470 {
 471   m_kind = VR_UNDEFINED;
 472   m_num_ranges = 0;
 473 }
 474
 475 #if 0 // sdcpp
 476 inline void
 477 irange::set_varying (tree type)
 478 {
 479   m_kind = VR_VARYING;
 480   m_num_ranges = 1;
 481
 482   if (INTEGRAL_TYPE_P (type))
 483     {
 484       // Strict enum's require varying to be not TYPE_MIN/MAX, but rather
 485       // min_value and max_value.
 486       wide_int min = wi::min_value (TYPE_PRECISION (type), TYPE_SIGN (type));
 487       wide_int max = wi::max_value (TYPE_PRECISION (type), TYPE_SIGN (type));
 488       if (wi::eq_p (max, wi::to_wide (TYPE_MAX_VALUE (type)))
 489           && wi::eq_p (min, wi::to_wide (TYPE_MIN_VALUE (type))))
 490         {
 491           m_base[0] = TYPE_MIN_VALUE (type);
 492           m_base[1] = TYPE_MAX_VALUE (type);
 493         }
 494       else
 495         {
 496           m_base[0] = wide_int_to_tree (type, min);
 497           m_base[1] = wide_int_to_tree (type, max);
 498         }
 499     }
 500   else if (POINTER_TYPE_P (type))
 501     {
 502       m_base[0] = build_int_cst (type, 0);
 503       m_base[1] = build_int_cst (type, -1);
 504     }
 505   else
 506     m_base[0] = m_base[1] = error_mark_node;
 507 }
 508 #endif // sdcpp
 509
 510 inline bool
 511 irange::operator== (const irange &r) const
 512 {
 513   return equal_p (r);
 514 }
 515
 516 // Return the lower bound of a sub-range.  PAIR is the sub-range in
 517 // question.
 518
 519 inline wide_int
 520 irange::lower_bound (unsigned pair) const
 521 {
 522   if (legacy_mode_p ())
 523     return legacy_lower_bound (pair);
 524   gcc_checking_assert (m_num_ranges > 0);
 525   gcc_checking_assert (pair + 1 <= num_pairs ());
 526   return wi::to_wide (tree_lower_bound (pair));
 527 }
 528
 529 // Return the upper bound of a sub-range.  PAIR is the sub-range in
 530 // question.
 531
 532 inline wide_int
 533 irange::upper_bound (unsigned pair) const
 534 {
 535   if (legacy_mode_p ())
 536     return legacy_upper_bound (pair);
 537   gcc_checking_assert (m_num_ranges > 0);
 538   gcc_checking_assert (pair + 1 <= num_pairs ());
 539   return wi::to_wide (tree_upper_bound (pair));
 540 }
 541
 542 // Return the highest bound of a range.
 543
 544 inline wide_int
 545 irange::upper_bound () const
 546 {
 547   unsigned pairs = num_pairs ();
 548   gcc_checking_assert (pairs > 0);
 549   return upper_bound (pairs - 1);
 550 }
 551
 552 inline void
 553 irange::union_ (const irange &r)
 554 {
 555   dump_flags_t m_flags = dump_flags;
 556   dump_flags &= ~TDF_DETAILS;
 557   irange::union_ (&r);
 558   dump_flags = m_flags;
 559 }
 560
 561 inline void
 562 irange::intersect (const irange &r)
 563 {
 564   dump_flags_t m_flags = dump_flags;
 565   dump_flags &= ~TDF_DETAILS;
 566   irange::intersect (&r);
 567   dump_flags = m_flags;
 568 }
 569
 570 // Set value range VR to a nonzero range of type TYPE.
 571
 572 #if 0 // sdcpp
 573 inline void
 574 irange::set_nonzero (tree type)
 575 {
 576   tree zero = build_int_cst (type, 0);
 577   if (legacy_mode_p ())
 578     set (zero, zero, VR_ANTI_RANGE);
 579   else
 580     irange_set_anti_range (zero, zero);
 581 }
 582
 583 // Set value range VR to a ZERO range of type TYPE.
 584
 585 inline void
 586 irange::set_zero (tree type)
 587 {
 588   tree z = build_int_cst (type, 0);
 589   if (legacy_mode_p ())
 590     set (z);
 591   else
 592     irange_set (z, z);
 593 }
 594 #endif // sdcpp
 595
 596 // Normalize a range to VARYING or UNDEFINED if possible.
 597
 598 inline void
 599 irange::normalize_kind ()
 600 {
 601   if (m_num_ranges == 0)
 602     m_kind = VR_UNDEFINED;
 603   else if (varying_compatible_p ())
 604     {
 605       if (m_kind == VR_RANGE)
 606         m_kind = VR_VARYING;
 607       else if (m_kind == VR_ANTI_RANGE)
 608         set_undefined ();
 609       else
 610         gcc_unreachable ();
 611     }
 612 }
 613
 614 // Return the maximum value for TYPE.
 615
 616 #if 0 // sdcpp
 617 inline tree
 618 vrp_val_max (const_tree type)
 619 {
 620   if (INTEGRAL_TYPE_P (type))
 621     return TYPE_MAX_VALUE (type);
 622   if (POINTER_TYPE_P (type))
 623     {
 624       wide_int max = wi::max_value (TYPE_PRECISION (type), TYPE_SIGN (type));
 625       return wide_int_to_tree (const_cast<tree> (type), max);
 626     }
 627   return NULL_TREE;
 628 }
 629 #endif // sdcpp
 630
 631 // Return the minimum value for TYPE.
 632
 633 inline tree
 634 vrp_val_min (const_tree type)
 635 {
 636   if (INTEGRAL_TYPE_P (type))
 637     return TYPE_MIN_VALUE (type);
 638   if (POINTER_TYPE_P (type))
 639     return build_zero_cst (const_cast<tree> (type));
 640   return NULL_TREE;
 641 }
 642
 643 // This is the irange storage class.  It is used to allocate the
 644 // minimum amount of storage needed for a given irange.  Storage is
 645 // automatically freed at destruction of the storage class.
 646 //
 647 // It is meant for long term storage, as opposed to int_range_max
 648 // which is meant for intermediate temporary results on the stack.
 649 //
 650 // The newly allocated irange is initialized to the empty set
 651 // (undefined_p() is true).
 652
 653 class irange_allocator
 654 {
 655 public:
 656   irange_allocator ();
 657   ~irange_allocator ();
 658   // Return a new range with NUM_PAIRS.
 659   irange *allocate (unsigned num_pairs);
 660   // Return a copy of SRC with the minimum amount of sub-ranges needed
 661   // to represent it.
 662   irange *allocate (const irange &src);
 663   void *get_memory (unsigned num_bytes);
 664 private:
 665   DISABLE_COPY_AND_ASSIGN (irange_allocator);
 666   struct obstack m_obstack;
 667 };
 668
 669 inline
 670 irange_allocator::irange_allocator ()
 671 {
 672   obstack_init (&m_obstack);
 673 }
 674
 675 inline
 676 irange_allocator::~irange_allocator ()
 677 {
 678   obstack_free (&m_obstack, NULL);
 679 }
 680
 681 // Provide a hunk of memory from the obstack.
 682 inline void *
 683 irange_allocator::get_memory (unsigned num_bytes)
 684 {
 685   void *r = obstack_alloc (&m_obstack, num_bytes);
 686   return r;
 687 }
 688
 689 // Return a new range with NUM_PAIRS.
 690
 691 inline irange *
 692 irange_allocator::allocate (unsigned num_pairs)
 693 {
 694   // Never allocate 0 pairs.
 695   // Don't allocate 1 either, or we get legacy value_range's.
 696   if (num_pairs < 2)
 697     num_pairs = 2;
 698
 699   size_t nbytes = sizeof (tree) * 2 * num_pairs;
 700
 701   // Allocate the irange and required memory for the vector.
 702   void *r = obstack_alloc (&m_obstack, sizeof (irange));
 703   tree *mem = (tree *) obstack_alloc (&m_obstack, nbytes);
 704   return new (r) irange (mem, num_pairs);
 705 }
 706
 707 inline irange *
 708 irange_allocator::allocate (const irange &src)
 709 {
 710   irange *r = allocate (src.num_pairs ());
 711   *r = src;
 712   return r;
 713 }
 714
 715 #endif // GCC_VALUE_RANGE_H