gcc/value-range-storage.cc

   1 /* Support routines for vrange storage.
   2    Copyright (C) 2022-2023 Free Software Foundation, Inc.
   3    Contributed by Aldy Hernandez <aldyh@redhat.com>.
   4
   5 This file is part of GCC.
   6
   7 GCC is free software; you can redistribute it and/or modify
   8 it under the terms of the GNU General Public License as published by
   9 the Free Software Foundation; either version 3, or (at your option)
  10 any later version.
  11
  12 GCC is distributed in the hope that it will be useful,
  13 but WITHOUT ANY WARRANTY; without even the implied warranty of
  14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15 GNU General Public License for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GCC; see the file COPYING3.  If not see
  19 <http://www.gnu.org/licenses/>.  */
  20
  21 #include "config.h"
  22 #include "system.h"
  23 #include "coretypes.h"
  24 #include "backend.h"
  25 #include "tree.h"
  26 #include "gimple.h"
  27 #include "ssa.h"
  28 #include "tree-pretty-print.h"
  29 #include "fold-const.h"
  30 #include "gimple-range.h"
  31 #include "value-range-storage.h"
  32
  33 // Generic memory allocator to share one interface between GC and
  34 // obstack allocators.
  35
  36 class vrange_internal_alloc
  37 {
  38 public:
  39   vrange_internal_alloc () { }
  40   virtual ~vrange_internal_alloc () { }
  41   virtual void *alloc (size_t size) = 0;
  42   virtual void free (void *) = 0;
  43 private:
  44   DISABLE_COPY_AND_ASSIGN (vrange_internal_alloc);
  45 };
  46
  47 class vrange_obstack_alloc final: public vrange_internal_alloc
  48 {
  49 public:
  50   vrange_obstack_alloc ()
  51   {
  52     obstack_init (&m_obstack);
  53   }
  54   virtual ~vrange_obstack_alloc () final override
  55   {
  56     obstack_free (&m_obstack, NULL);
  57   }
  58   virtual void *alloc (size_t size) final override
  59   {
  60     return obstack_alloc (&m_obstack, size);
  61   }
  62   virtual void free (void *) final override { }
  63 private:
  64   obstack m_obstack;
  65 };
  66
  67 class vrange_ggc_alloc final: public vrange_internal_alloc
  68 {
  69 public:
  70   vrange_ggc_alloc () { }
  71   virtual ~vrange_ggc_alloc () final override { }
  72   virtual void *alloc (size_t size) final override
  73   {
  74     return ggc_internal_alloc (size);
  75   }
  76   virtual void free (void *p) final override
  77   {
  78     return ggc_free (p);
  79   }
  80 };
  81
  82 vrange_allocator::vrange_allocator (bool gc)
  83 {
  84   if (gc)
  85     m_alloc = new vrange_ggc_alloc;
  86   else
  87     m_alloc = new vrange_obstack_alloc;
  88 }
  89
  90 vrange_allocator::~vrange_allocator ()
  91 {
  92   delete m_alloc;
  93 }
  94
  95 void *
  96 vrange_allocator::alloc (size_t size)
  97 {
  98   return m_alloc->alloc (size);
  99 }
 100
 101 void
 102 vrange_allocator::free (void *p)
 103 {
 104   m_alloc->free (p);
 105 }
 106
 107 // Allocate a new vrange_storage object initialized to R and return
 108 // it.
 109
 110 vrange_storage *
 111 vrange_allocator::clone (const vrange &r)
 112 {
 113   return vrange_storage::alloc (*m_alloc, r);
 114 }
 115
 116 vrange_storage *
 117 vrange_allocator::clone_varying (tree type)
 118 {
 119   if (irange::supports_p (type))
 120     return irange_storage::alloc (*m_alloc, int_range <1> (type));
 121   if (frange::supports_p (type))
 122     return frange_storage::alloc (*m_alloc, frange (type));
 123   return NULL;
 124 }
 125
 126 vrange_storage *
 127 vrange_allocator::clone_undefined (tree type)
 128 {
 129   if (irange::supports_p (type))
 130     return irange_storage::alloc (*m_alloc, int_range<1> ());
 131   if (frange::supports_p (type))
 132     return frange_storage::alloc  (*m_alloc, frange ());
 133   return NULL;
 134 }
 135
 136 // Allocate a new vrange_storage object initialized to R and return
 137 // it.  Return NULL if R is unsupported.
 138
 139 vrange_storage *
 140 vrange_storage::alloc (vrange_internal_alloc &allocator, const vrange &r)
 141 {
 142   if (is_a <irange> (r))
 143     return irange_storage::alloc (allocator, as_a <irange> (r));
 144   if (is_a <frange> (r))
 145     return frange_storage::alloc (allocator, as_a <frange> (r));
 146   return NULL;
 147 }
 148
 149 // Set storage to R.
 150
 151 void
 152 vrange_storage::set_vrange (const vrange &r)
 153 {
 154   if (is_a <irange> (r))
 155     {
 156       irange_storage *s = static_cast <irange_storage *> (this);
 157       gcc_checking_assert (s->fits_p (as_a <irange> (r)));
 158       s->set_irange (as_a <irange> (r));
 159     }
 160   else if (is_a <frange> (r))
 161     {
 162       frange_storage *s = static_cast <frange_storage *> (this);
 163       gcc_checking_assert (s->fits_p (as_a <frange> (r)));
 164       s->set_frange (as_a <frange> (r));
 165     }
 166   else
 167     gcc_unreachable ();
 168 }
 169
 170 // Restore R from storage.
 171
 172 void
 173 vrange_storage::get_vrange (vrange &r, tree type) const
 174 {
 175   if (is_a <irange> (r))
 176     {
 177       const irange_storage *s = static_cast <const irange_storage *> (this);
 178       s->get_irange (as_a <irange> (r), type);
 179     }
 180   else if (is_a <frange> (r))
 181     {
 182       const frange_storage *s = static_cast <const frange_storage *> (this);
 183       s->get_frange (as_a <frange> (r), type);
 184     }
 185   else
 186     gcc_unreachable ();
 187 }
 188
 189 // Return TRUE if storage can fit R.
 190
 191 bool
 192 vrange_storage::fits_p (const vrange &r) const
 193 {
 194   if (is_a <irange> (r))
 195     {
 196       const irange_storage *s = static_cast <const irange_storage *> (this);
 197       return s->fits_p (as_a <irange> (r));
 198     }
 199   if (is_a <frange> (r))
 200     {
 201       const frange_storage *s = static_cast <const frange_storage *> (this);
 202       return s->fits_p (as_a <frange> (r));
 203     }
 204   gcc_unreachable ();
 205   return false;
 206 }
 207
 208 // Return TRUE if the range in storage is equal to R.  It is the
 209 // caller's responsibility to verify that the type of the range in
 210 // storage matches that of R.
 211
 212 bool
 213 vrange_storage::equal_p (const vrange &r) const
 214 {
 215   if (is_a <irange> (r))
 216     {
 217       const irange_storage *s = static_cast <const irange_storage *> (this);
 218       return s->equal_p (as_a <irange> (r));
 219     }
 220   if (is_a <frange> (r))
 221     {
 222       const frange_storage *s = static_cast <const frange_storage *> (this);
 223       return s->equal_p (as_a <frange> (r));
 224     }
 225   gcc_unreachable ();
 226 }
 227
 228 //============================================================================
 229 // irange_storage implementation
 230 //============================================================================
 231
 232 unsigned char *
 233 irange_storage::write_lengths_address ()
 234 {
 235   return (unsigned char *)&m_val[(m_num_ranges * 2 + 1)
 236                                  * WIDE_INT_MAX_HWIS (m_precision)];
 237 }
 238
 239 const unsigned char *
 240 irange_storage::lengths_address () const
 241 {
 242   return const_cast <irange_storage *> (this)->write_lengths_address ();
 243 }
 244
 245 // Allocate a new irange_storage object initialized to R.
 246
 247 irange_storage *
 248 irange_storage::alloc (vrange_internal_alloc &allocator, const irange &r)
 249 {
 250   size_t size = irange_storage::size (r);
 251   irange_storage *p = static_cast <irange_storage *> (allocator.alloc (size));
 252   new (p) irange_storage (r);
 253   return p;
 254 }
 255
 256 // Initialize the storage with R.
 257
 258 irange_storage::irange_storage (const irange &r)
 259   : m_max_ranges (r.num_pairs ())
 260 {
 261   m_num_ranges = m_max_ranges;
 262   set_irange (r);
 263 }
 264
 265 static inline void
 266 write_wide_int (HOST_WIDE_INT *&val, unsigned char *&len, const wide_int &w)
 267 {
 268   *len = w.get_len ();
 269   for (unsigned i = 0; i < *len; ++i)
 270     *val++ = w.elt (i);
 271   ++len;
 272 }
 273
 274 // Store R into the current storage.
 275
 276 void
 277 irange_storage::set_irange (const irange &r)
 278 {
 279   gcc_checking_assert (fits_p (r));
 280
 281   if (r.undefined_p ())
 282     {
 283       m_kind = VR_UNDEFINED;
 284       return;
 285     }
 286   if (r.varying_p ())
 287     {
 288       m_kind = VR_VARYING;
 289       return;
 290     }
 291
 292   m_precision = TYPE_PRECISION (r.type ());
 293   m_num_ranges = r.num_pairs ();
 294   m_kind = VR_RANGE;
 295
 296   HOST_WIDE_INT *val = &m_val[0];
 297   unsigned char *len = write_lengths_address ();
 298
 299   for (unsigned i = 0; i < r.num_pairs (); ++i)
 300     {
 301       write_wide_int (val, len, r.lower_bound (i));
 302       write_wide_int (val, len, r.upper_bound (i));
 303     }
 304   write_wide_int (val, len, r.m_nonzero_mask);
 305
 306   if (flag_checking)
 307     {
 308       int_range_max tmp;
 309       get_irange (tmp, r.type ());
 310       gcc_checking_assert (tmp == r);
 311     }
 312 }
 313
 314 static inline void
 315 read_wide_int (wide_int &w,
 316                const HOST_WIDE_INT *val, unsigned char len, unsigned prec)
 317 {
 318   trailing_wide_int_storage stow (prec, &len,
 319                                   const_cast <HOST_WIDE_INT *> (val));
 320   w = trailing_wide_int (stow);
 321 }
 322
 323 // Restore a range of TYPE from storage into R.
 324
 325 void
 326 irange_storage::get_irange (irange &r, tree type) const
 327 {
 328   if (m_kind == VR_UNDEFINED)
 329     {
 330       r.set_undefined ();
 331       return;
 332     }
 333   if (m_kind == VR_VARYING)
 334     {
 335       r.set_varying (type);
 336       return;
 337     }
 338
 339   gcc_checking_assert (TYPE_PRECISION (type) == m_precision);
 340   const HOST_WIDE_INT *val = &m_val[0];
 341   const unsigned char *len = lengths_address ();
 342
 343   // Handle the common case where R can fit the new range.
 344   if (r.m_max_ranges >= m_num_ranges)
 345     {
 346       r.m_kind = VR_RANGE;
 347       r.m_num_ranges = m_num_ranges;
 348       r.m_type = type;
 349       for (unsigned i = 0; i < m_num_ranges * 2; ++i)
 350         {
 351           read_wide_int (r.m_base[i], val, *len, m_precision);
 352           val += *len++;
 353         }
 354     }
 355   // Otherwise build the range piecewise.
 356   else
 357     {
 358       r.set_undefined ();
 359       for (unsigned i = 0; i < m_num_ranges; ++i)
 360         {
 361           wide_int lb, ub;
 362           read_wide_int (lb, val, *len, m_precision);
 363           val += *len++;
 364           read_wide_int (ub, val, *len, m_precision);
 365           val += *len++;
 366           int_range<1> tmp (type, lb, ub);
 367           r.union_ (tmp);
 368         }
 369     }
 370   read_wide_int (r.m_nonzero_mask, val, *len, m_precision);
 371   if (r.m_kind == VR_VARYING)
 372     r.m_kind = VR_RANGE;
 373
 374   if (flag_checking)
 375     r.verify_range ();
 376 }
 377
 378 bool
 379 irange_storage::equal_p (const irange &r) const
 380 {
 381   if (m_kind == VR_UNDEFINED || r.undefined_p ())
 382     return m_kind == r.m_kind;
 383   if (m_kind == VR_VARYING || r.varying_p ())
 384     return m_kind == r.m_kind;
 385
 386   // ?? We could make this faster by doing the comparison in place,
 387   // without going through get_irange.
 388   int_range_max tmp;
 389   get_irange (tmp, r.type ());
 390   return tmp == r;
 391 }
 392
 393 // Return the size in bytes to allocate storage that can hold R.
 394
 395 size_t
 396 irange_storage::size (const irange &r)
 397 {
 398   if (r.undefined_p ())
 399     return sizeof (irange_storage);
 400
 401   unsigned prec = TYPE_PRECISION (r.type ());
 402   unsigned n = r.num_pairs () * 2 + 1;
 403   unsigned hwi_size = ((n * WIDE_INT_MAX_HWIS (prec) - 1)
 404                        * sizeof (HOST_WIDE_INT));
 405   unsigned len_size = n;
 406   return sizeof (irange_storage) + hwi_size + len_size;
 407 }
 408
 409 // Return TRUE if R fits in the current storage.
 410
 411 bool
 412 irange_storage::fits_p (const irange &r) const
 413 {
 414   return m_max_ranges >= r.num_pairs ();
 415 }
 416
 417 void
 418 irange_storage::dump () const
 419 {
 420   fprintf (stderr, "irange_storage (prec=%d, ranges=%d):\n",
 421            m_precision, m_num_ranges);
 422
 423   if (m_num_ranges == 0)
 424     return;
 425
 426   const HOST_WIDE_INT *val = &m_val[0];
 427   const unsigned char *len = lengths_address ();
 428   int i, j;
 429
 430   fprintf (stderr, "  lengths = [ ");
 431   for (i = 0; i < m_num_ranges * 2 + 1; ++i)
 432     fprintf (stderr, "%d ", len[i]);
 433   fprintf (stderr, "]\n");
 434
 435   for (i = 0; i < m_num_ranges; ++i)
 436     {
 437       for (j = 0; j < *len; ++j)
 438         fprintf (stderr, "  [PAIR %d] LB " HOST_WIDE_INT_PRINT_DEC "\n", i,
 439                  *val++);
 440       ++len;
 441       for (j = 0; j < *len; ++j)
 442         fprintf (stderr, "  [PAIR %d] UB " HOST_WIDE_INT_PRINT_DEC "\n", i,
 443                  *val++);
 444       ++len;
 445     }
 446   for (j = 0; j < *len; ++j)
 447     fprintf (stderr, "  [NZ] " HOST_WIDE_INT_PRINT_DEC "\n", *val++);
 448 }
 449
 450 DEBUG_FUNCTION void
 451 debug (const irange_storage &storage)
 452 {
 453   storage.dump ();
 454   fprintf (stderr, "\n");
 455 }
 456
 457 //============================================================================
 458 // frange_storage implementation
 459 //============================================================================
 460
 461 // Allocate a new frange_storage object initialized to R.
 462
 463 frange_storage *
 464 frange_storage::alloc (vrange_internal_alloc &allocator, const frange &r)
 465 {
 466   size_t size = sizeof (frange_storage);
 467   frange_storage *p = static_cast <frange_storage *> (allocator.alloc (size));
 468   new (p) frange_storage (r);
 469   return p;
 470 }
 471
 472 void
 473 frange_storage::set_frange (const frange &r)
 474 {
 475   gcc_checking_assert (fits_p (r));
 476
 477   m_kind = r.m_kind;
 478   m_min = r.m_min;
 479   m_max = r.m_max;
 480   m_pos_nan = r.m_pos_nan;
 481   m_neg_nan = r.m_neg_nan;
 482 }
 483
 484 void
 485 frange_storage::get_frange (frange &r, tree type) const
 486 {
 487   gcc_checking_assert (r.supports_type_p (type));
 488
 489   // Handle explicit NANs.
 490   if (m_kind == VR_NAN)
 491     {
 492       if (HONOR_NANS (type))
 493         {
 494           if (m_pos_nan && m_neg_nan)
 495             r.set_nan (type);
 496           else
 497             r.set_nan (type, m_neg_nan);
 498         }
 499       else
 500         r.set_undefined ();
 501       return;
 502     }
 503   if (m_kind == VR_UNDEFINED)
 504     {
 505       r.set_undefined ();
 506       return;
 507     }
 508
 509   // We use the constructor to create the new range instead of writing
 510   // out the bits into the frange directly, because the global range
 511   // being read may be being inlined into a function with different
 512   // restrictions as when it was originally written.  We want to make
 513   // sure the resulting range is canonicalized correctly for the new
 514   // consumer.
 515   r = frange (type, m_min, m_max, m_kind);
 516
 517   // The constructor will set the NAN bits for HONOR_NANS, but we must
 518   // make sure to set the NAN sign if known.
 519   if (HONOR_NANS (type) && (m_pos_nan ^ m_neg_nan) == 1)
 520     r.update_nan (m_neg_nan);
 521   else if (!m_pos_nan && !m_neg_nan)
 522     r.clear_nan ();
 523 }
 524
 525 bool
 526 frange_storage::equal_p (const frange &r) const
 527 {
 528   if (r.undefined_p ())
 529     return m_kind == VR_UNDEFINED;
 530
 531   frange tmp;
 532   get_frange (tmp, r.type ());
 533   return tmp == r;
 534 }
 535
 536 bool
 537 frange_storage::fits_p (const frange &) const
 538 {
 539   return true;
 540 }
 541
 542 static vrange_allocator ggc_vrange_allocator (true);
 543
 544 vrange_storage *ggc_alloc_vrange_storage (tree type)
 545 {
 546   return ggc_vrange_allocator.clone_varying (type);
 547 }
 548
 549 vrange_storage *ggc_alloc_vrange_storage (const vrange &r)
 550 {
 551   return ggc_vrange_allocator.clone (r);
 552 }