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 public:
  47   // In-place setters.
  48   void set (tree, tree, value_range_kind = VR_RANGE);
  49   void set_nonzero (tree);
  50   void set_zero (tree);
  51   void set_varying (tree type);
  52   void set_undefined ();
  53
  54   // Range types.
  55   static bool supports_type_p (tree);
  56   tree type () const;
  57
  58   // Iteration over sub-ranges.
  59   unsigned num_pairs () const;
  60   wide_int lower_bound (unsigned = 0) const;
  61   wide_int upper_bound (unsigned) const;
  62   wide_int upper_bound () const;
  63
  64   // Predicates.
  65   bool zero_p () const;
  66   bool nonzero_p () const;
  67   bool undefined_p () const;
  68   bool varying_p () const;
  69   bool singleton_p (tree *result = NULL) const;
  70   bool contains_p (tree) const;
  71
  72   // In-place operators.
  73   void union_ (const irange &);
  74   void intersect (const irange &);
  75   void invert ();
  76
  77   // Operator overloads.
  78   irange& operator= (const irange &);
  79   bool operator== (const irange &) const;
  80   bool operator!= (const irange &r) const { return !(*this == r); }
  81
  82   // Misc methods.
  83   void dump (FILE * = stderr) const;
  84
  85   // Deprecated legacy public methods.
  86   enum value_range_kind kind () const;          // DEPRECATED
  87   tree min () const;                            // DEPRECATED
  88   tree max () const;                            // DEPRECATED
  89   bool symbolic_p () const;                     // DEPRECATED
  90   bool constant_p () const;                     // DEPRECATED
  91   void normalize_symbolics ();                  // DEPRECATED
  92   void normalize_addresses ();                  // DEPRECATED
  93   bool may_contain_p (tree) const;              // DEPRECATED
  94   void set (tree);                              // DEPRECATED
  95   bool equal_p (const irange &) const;          // DEPRECATED
  96   void union_ (const class irange *);           // DEPRECATED
  97   void intersect (const irange *);              // DEPRECATED
  98
  99 protected:
 100   irange (tree *, unsigned);
 101   // potential promotion to public?
 102   tree tree_lower_bound (unsigned = 0) const;
 103   tree tree_upper_bound (unsigned) const;
 104   tree tree_upper_bound () const;
 105
 106    // In-place operators.
 107   void irange_union (const irange &);
 108   void irange_intersect (const irange &);
 109   void irange_set (tree, tree);
 110   void irange_set_anti_range (tree, tree);
 111
 112   bool swap_out_of_order_endpoints (tree &min, tree &max, value_range_kind &);
 113   bool normalize_min_max (tree type, tree min, tree max, value_range_kind);
 114
 115   bool legacy_mode_p () const;
 116   bool legacy_equal_p (const irange &) const;
 117   void legacy_union (irange *, const irange *);
 118   void legacy_intersect (irange *, const irange *);
 119   void verify_range ();
 120   unsigned legacy_num_pairs () const;
 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_legacy_range (const irange &);
 126
 127 private:
 128   unsigned char m_num_ranges;
 129   unsigned char m_max_ranges;
 130   ENUM_BITFIELD(value_range_kind) m_kind : 8;
 131   tree *m_base;
 132 };
 133
 134 // Here we describe an irange with N pairs of ranges.  The storage for
 135 // the pairs is embedded in the class as an array.
 136
 137 template<unsigned N>
 138 class GTY((user)) int_range : public irange
 139 {
 140 public:
 141   int_range ();
 142   int_range (tree, tree, value_range_kind = VR_RANGE);
 143   int_range (tree type, const wide_int &, const wide_int &,
 144              value_range_kind = VR_RANGE);
 145   int_range (tree type);
 146   int_range (const int_range &);
 147   int_range (const irange &);
 148   int_range& operator= (const int_range &);
 149 private:
 150   template <unsigned X> friend void gt_ggc_mx (int_range<X> *);
 151   template <unsigned X> friend void gt_pch_nx (int_range<X> *);
 152   template <unsigned X> friend void gt_pch_nx (int_range<X> *,
 153                                                gt_pointer_operator, void *);
 154   // ?? hash-traits.h has its own extern for these, which is causing
 155   // them to never be picked up by the templates.  For now, define
 156   // elsewhere.
 157   //template<unsigned X> friend void gt_ggc_mx (int_range<X> *&);
 158   //template<unsigned X> friend void gt_pch_nx (int_range<X> *&);
 159   friend void gt_ggc_mx (int_range<1> *&);
 160   friend void gt_pch_nx (int_range<1> *&);
 161
 162   tree m_ranges[N*2];
 163 };
 164
 165 // This is a special int_range<1> with only one pair, plus
 166 // VR_ANTI_RANGE magic to describe slightly more than can be described
 167 // in one pair.  It is described in the code as a "legacy range" (as
 168 // opposed to multi-ranges which have multiple sub-ranges).  It is
 169 // provided for backward compatibility with code that has not been
 170 // converted to multi-range irange's.
 171 //
 172 // There are copy operators to seamlessly copy to/fro multi-ranges.
 173 typedef int_range<1> value_range;
 174
 175 // This is an "infinite" precision irange for use in temporary
 176 // calculations.
 177 typedef int_range<255> int_range_max;
 178
 179 // Returns true for an old-school value_range as described above.
 180 inline bool
 181 irange::legacy_mode_p () const
 182 {
 183   return m_max_ranges == 1;
 184 }
 185
 186 extern bool range_has_numeric_bounds_p (const irange *);
 187 extern bool ranges_from_anti_range (const value_range *,
 188                                     value_range *, value_range *);
 189 extern void dump_value_range (FILE *, const irange *);
 190 extern bool vrp_val_is_min (const_tree);
 191 extern bool vrp_val_is_max (const_tree);
 192 extern bool vrp_operand_equal_p (const_tree, const_tree);
 193
 194 inline value_range_kind
 195 irange::kind () const
 196 {
 197   if (legacy_mode_p ())
 198     return m_kind;
 199
 200   if (undefined_p ())
 201     return VR_UNDEFINED;
 202
 203   if (varying_p ())
 204     return VR_VARYING;
 205
 206   return VR_RANGE;
 207 }
 208
 209 // Number of sub-ranges in a range.
 210
 211 inline unsigned
 212 irange::num_pairs () const
 213 {
 214   if (!legacy_mode_p ())
 215     return m_num_ranges;
 216   else
 217     return legacy_num_pairs ();
 218 }
 219
 220 inline tree
 221 irange::type () const
 222 {
 223   gcc_checking_assert (!undefined_p ());
 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_p () const
 271 {
 272   if (legacy_mode_p ())
 273     return m_kind == VR_VARYING;
 274
 275   if (m_num_ranges != 1)
 276     return false;
 277
 278   tree l = m_base[0];
 279   tree u = m_base[1];
 280   tree t = TREE_TYPE (l);
 281   if (INTEGRAL_TYPE_P (t))
 282     return l == TYPE_MIN_VALUE (t) && u == TYPE_MAX_VALUE (t);
 283   if (POINTER_TYPE_P (t))
 284     return wi::to_wide (l) == 0
 285            && wi::to_wide (u) == wi::max_value (TYPE_PRECISION (t),
 286                                                 TYPE_SIGN (t));
 287   return true;
 288
 289 }
 290
 291 inline bool
 292 irange::undefined_p () const
 293 {
 294   if (!legacy_mode_p ())
 295     return m_num_ranges == 0;
 296
 297   if (CHECKING_P && legacy_mode_p ())
 298     {
 299       if (m_kind == VR_UNDEFINED)
 300         gcc_checking_assert (m_num_ranges == 0);
 301       else
 302         gcc_checking_assert (m_num_ranges != 0);
 303     }
 304   return m_kind == VR_UNDEFINED;
 305 }
 306
 307 inline bool
 308 irange::zero_p () const
 309 {
 310   return (m_kind == VR_RANGE && m_num_ranges == 1
 311           && integer_zerop (tree_lower_bound (0))
 312           && integer_zerop (tree_upper_bound (0)));
 313 }
 314
 315 inline bool
 316 irange::nonzero_p () const
 317 {
 318   if (undefined_p ())
 319     return false;
 320
 321   tree zero = build_zero_cst (type ());
 322   return *this == int_range<1> (zero, zero, VR_ANTI_RANGE);
 323 }
 324
 325 inline bool
 326 irange::supports_type_p (tree type)
 327 {
 328   if (type && (INTEGRAL_TYPE_P (type) || POINTER_TYPE_P (type)))
 329     return type;
 330   return false;
 331 }
 332
 333 inline bool
 334 range_includes_zero_p (const irange *vr)
 335 {
 336   if (vr->undefined_p ())
 337     return false;
 338
 339   if (vr->varying_p ())
 340     return true;
 341
 342   return vr->may_contain_p (build_zero_cst (vr->type ()));
 343 }
 344
 345 template<unsigned N>
 346 inline void
 347 gt_ggc_mx (int_range<N> *x)
 348 {
 349   for (unsigned i = 0; i < N; ++i)
 350     {
 351       gt_ggc_mx (x->m_ranges[i * 2]);
 352       gt_ggc_mx (x->m_ranges[i * 2 + 1]);
 353     }
 354 }
 355
 356 template<unsigned N>
 357 inline void
 358 gt_pch_nx (int_range<N> *x)
 359 {
 360   for (unsigned i = 0; i < N; ++i)
 361     {
 362       gt_pch_nx (x->m_ranges[i * 2]);
 363       gt_pch_nx (x->m_ranges[i * 2 + 1]);
 364     }
 365 }
 366
 367 template<unsigned N>
 368 inline void
 369 gt_pch_nx (int_range<N> *x, gt_pointer_operator op, void *cookie)
 370 {
 371   for (unsigned i = 0; i < N; ++i)
 372     {
 373       op (&x->m_ranges[i * 2], cookie);
 374       op (&x->m_ranges[i * 2 + 1], cookie);
 375     }
 376 }
 377
 378 // Constructors for irange
 379
 380 inline
 381 irange::irange (tree *base, unsigned nranges)
 382 {
 383   m_base = base;
 384   m_num_ranges = 0;
 385   m_max_ranges = nranges;
 386   if (legacy_mode_p ())
 387     m_kind = VR_UNDEFINED;
 388   else
 389     m_kind = VR_RANGE;
 390 }
 391
 392 // Constructors for int_range<>.
 393
 394 template<unsigned N>
 395 inline
 396 int_range<N>::int_range ()
 397   : irange (m_ranges, N)
 398 {
 399 }
 400
 401 template<unsigned N>
 402 int_range<N>::int_range (const int_range &other)
 403   : irange (m_ranges, N)
 404 {
 405   irange::operator= (other);
 406 }
 407
 408 template<unsigned N>
 409 int_range<N>::int_range (tree min, tree max, value_range_kind kind)
 410   : irange (m_ranges, N)
 411 {
 412   irange::set (min, max, kind);
 413 }
 414
 415 template<unsigned N>
 416 int_range<N>::int_range (tree type)
 417   : irange (m_ranges, N)
 418 {
 419   set_varying (type);
 420 }
 421
 422 template<unsigned N>
 423 int_range<N>::int_range (tree type, const wide_int &wmin, const wide_int &wmax,
 424                          value_range_kind kind)
 425   : irange (m_ranges, N)
 426 {
 427   tree min = wide_int_to_tree (type, wmin);
 428   tree max = wide_int_to_tree (type, wmax);
 429   set (min, max, kind);
 430 }
 431
 432 template<unsigned N>
 433 int_range<N>::int_range (const irange &other)
 434   : irange (m_ranges, N)
 435 {
 436   irange::operator= (other);
 437 }
 438
 439 template<unsigned N>
 440 int_range<N>&
 441 int_range<N>::operator= (const int_range &src)
 442 {
 443   irange::operator= (src);
 444   return *this;
 445 }
 446
 447 inline void
 448 irange::set (tree val)
 449 {
 450   set (val, val);
 451 }
 452
 453 inline void
 454 irange::set_undefined ()
 455 {
 456   m_num_ranges = 0;
 457   if (legacy_mode_p ())
 458     m_kind = VR_UNDEFINED;
 459 }
 460
 461 inline void
 462 irange::set_varying (tree type)
 463 {
 464   if (legacy_mode_p ())
 465     m_kind = VR_VARYING;
 466
 467   m_num_ranges = 1;
 468   if (INTEGRAL_TYPE_P (type))
 469     {
 470       m_base[0] = TYPE_MIN_VALUE (type);
 471       m_base[1] = TYPE_MAX_VALUE (type);
 472     }
 473   else if (POINTER_TYPE_P (type))
 474     {
 475       m_base[0] = build_int_cst (type, 0);
 476       m_base[1] = build_int_cst (type, -1);
 477     }
 478   else
 479     m_base[0] = m_base[1] = error_mark_node;
 480 }
 481
 482 inline bool
 483 irange::operator== (const irange &r) const
 484 {
 485   return equal_p (r);
 486 }
 487
 488 // Return the lower bound of a sub-range.  PAIR is the sub-range in
 489 // question.
 490
 491 inline wide_int
 492 irange::lower_bound (unsigned pair) const
 493 {
 494   if (legacy_mode_p ())
 495     return legacy_lower_bound (pair);
 496   gcc_checking_assert (!undefined_p ());
 497   gcc_checking_assert (pair + 1 <= num_pairs ());
 498   return wi::to_wide (tree_lower_bound (pair));
 499 }
 500
 501 // Return the upper bound of a sub-range.  PAIR is the sub-range in
 502 // question.
 503
 504 inline wide_int
 505 irange::upper_bound (unsigned pair) const
 506 {
 507   if (legacy_mode_p ())
 508     return legacy_upper_bound (pair);
 509   gcc_checking_assert (!undefined_p ());
 510   gcc_checking_assert (pair + 1 <= num_pairs ());
 511   return wi::to_wide (tree_upper_bound (pair));
 512 }
 513
 514 // Return the highest bound of a range.
 515
 516 inline wide_int
 517 irange::upper_bound () const
 518 {
 519   unsigned pairs = num_pairs ();
 520   gcc_checking_assert (pairs > 0);
 521   return upper_bound (pairs - 1);
 522 }
 523
 524 inline void
 525 irange::union_ (const irange &r)
 526 {
 527   dump_flags_t m_flags = dump_flags;
 528   dump_flags &= ~TDF_DETAILS;
 529   irange::union_ (&r);
 530   dump_flags = m_flags;
 531 }
 532
 533 inline void
 534 irange::intersect (const irange &r)
 535 {
 536   dump_flags_t m_flags = dump_flags;
 537   dump_flags &= ~TDF_DETAILS;
 538   irange::intersect (&r);
 539   dump_flags = m_flags;
 540 }
 541
 542 // Set value range VR to a nonzero range of type TYPE.
 543
 544 inline void
 545 irange::set_nonzero (tree type)
 546 {
 547   tree zero = build_int_cst (type, 0);
 548   if (legacy_mode_p ())
 549     set (zero, zero, VR_ANTI_RANGE);
 550   else
 551     irange_set_anti_range (zero, zero);
 552 }
 553
 554 // Set value range VR to a ZERO range of type TYPE.
 555
 556 inline void
 557 irange::set_zero (tree type)
 558 {
 559   tree z = build_int_cst (type, 0);
 560   if (legacy_mode_p ())
 561     set (z);
 562   else
 563     irange_set (z, z);
 564 }
 565
 566 // Normalize [MIN, MAX] into VARYING and ~[MIN, MAX] into UNDEFINED.
 567 //
 568 // Avoid using TYPE_{MIN,MAX}_VALUE because -fstrict-enums can
 569 // restrict those to a subset of what actually fits in the type.
 570 // Instead use the extremes of the type precision which will allow
 571 // compare_range_with_value() to check if a value is inside a range,
 572 // whereas if we used TYPE_*_VAL, said function would just punt upon
 573 // seeing a VARYING.
 574
 575 inline bool
 576 irange::normalize_min_max (tree type, tree min, tree max,
 577                            value_range_kind kind)
 578 {
 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 (kind == VR_RANGE)
 585         set_varying (type);
 586       else if (kind == VR_ANTI_RANGE)
 587         set_undefined ();
 588       else
 589         gcc_unreachable ();
 590       return true;
 591     }
 592   return false;
 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 #endif // GCC_VALUE_RANGE_H