gcc/value-range.h

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