gcc/value-range.h

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