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