gcc/value-range-storage.cc

   1 /* Support routines for vrange storage.
   2    Copyright (C) 2022-2024 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   // Verify that reading back from the cache didn't drop bits.
 170   if (flag_checking
 171       // FIXME: Avoid checking frange, as it currently pessimizes some ranges:
 172       //
 173       // gfortran.dg/pr49472.f90 pessimizes [0.0, 1.0] into [-0.0, 1.0].
 174       && !is_a <frange> (r)
 175       && !r.undefined_p ())
 176     {
 177       Value_Range tmp (r);
 178       get_vrange (tmp, r.type ());
 179       gcc_checking_assert (tmp == r);
 180     }
 181 }
 182
 183 // Restore R from storage.
 184
 185 void
 186 vrange_storage::get_vrange (vrange &r, tree type) const
 187 {
 188   if (is_a <irange> (r))
 189     {
 190       const irange_storage *s = static_cast <const irange_storage *> (this);
 191       s->get_irange (as_a <irange> (r), type);
 192     }
 193   else if (is_a <frange> (r))
 194     {
 195       const frange_storage *s = static_cast <const frange_storage *> (this);
 196       s->get_frange (as_a <frange> (r), type);
 197     }
 198   else
 199     gcc_unreachable ();
 200 }
 201
 202 // Return TRUE if storage can fit R.
 203
 204 bool
 205 vrange_storage::fits_p (const vrange &r) const
 206 {
 207   if (is_a <irange> (r))
 208     {
 209       const irange_storage *s = static_cast <const irange_storage *> (this);
 210       return s->fits_p (as_a <irange> (r));
 211     }
 212   if (is_a <frange> (r))
 213     {
 214       const frange_storage *s = static_cast <const frange_storage *> (this);
 215       return s->fits_p (as_a <frange> (r));
 216     }
 217   gcc_unreachable ();
 218   return false;
 219 }
 220
 221 // Return TRUE if the range in storage is equal to R.  It is the
 222 // caller's responsibility to verify that the type of the range in
 223 // storage matches that of R.
 224
 225 bool
 226 vrange_storage::equal_p (const vrange &r) const
 227 {
 228   if (is_a <irange> (r))
 229     {
 230       const irange_storage *s = static_cast <const irange_storage *> (this);
 231       return s->equal_p (as_a <irange> (r));
 232     }
 233   if (is_a <frange> (r))
 234     {
 235       const frange_storage *s = static_cast <const frange_storage *> (this);
 236       return s->equal_p (as_a <frange> (r));
 237     }
 238   gcc_unreachable ();
 239 }
 240
 241 //============================================================================
 242 // irange_storage implementation
 243 //============================================================================
 244
 245 unsigned short *
 246 irange_storage::write_lengths_address ()
 247 {
 248   return (unsigned short *)&m_val[(m_num_ranges * 2 + 2)
 249                                   * WIDE_INT_MAX_HWIS (m_precision)];
 250 }
 251
 252 const unsigned short *
 253 irange_storage::lengths_address () const
 254 {
 255   return const_cast <irange_storage *> (this)->write_lengths_address ();
 256 }
 257
 258 // Allocate a new irange_storage object initialized to R.
 259
 260 irange_storage *
 261 irange_storage::alloc (vrange_internal_alloc &allocator, const irange &r)
 262 {
 263   size_t size = irange_storage::size (r);
 264   irange_storage *p = static_cast <irange_storage *> (allocator.alloc (size));
 265   new (p) irange_storage (r);
 266   return p;
 267 }
 268
 269 // Initialize the storage with R.
 270
 271 irange_storage::irange_storage (const irange &r)
 272   : m_max_ranges (r.num_pairs ())
 273 {
 274   m_num_ranges = m_max_ranges;
 275   set_irange (r);
 276 }
 277
 278 static inline void
 279 write_wide_int (HOST_WIDE_INT *&val, unsigned short *&len, const wide_int &w)
 280 {
 281   *len = w.get_len ();
 282   for (unsigned i = 0; i < *len; ++i)
 283     *val++ = w.elt (i);
 284   ++len;
 285 }
 286
 287 // Store R into the current storage.
 288
 289 void
 290 irange_storage::set_irange (const irange &r)
 291 {
 292   gcc_checking_assert (fits_p (r));
 293
 294   if (r.undefined_p ())
 295     {
 296       m_kind = VR_UNDEFINED;
 297       return;
 298     }
 299   if (r.varying_p ())
 300     {
 301       m_kind = VR_VARYING;
 302       return;
 303     }
 304
 305   m_precision = TYPE_PRECISION (r.type ());
 306   m_num_ranges = r.num_pairs ();
 307   m_kind = VR_RANGE;
 308
 309   HOST_WIDE_INT *val = &m_val[0];
 310   unsigned short *len = write_lengths_address ();
 311
 312   for (unsigned i = 0; i < r.num_pairs (); ++i)
 313     {
 314       write_wide_int (val, len, r.lower_bound (i));
 315       write_wide_int (val, len, r.upper_bound (i));
 316     }
 317
 318   // TODO: We could avoid streaming out the value if the mask is -1.
 319   irange_bitmask bm = r.m_bitmask;
 320   write_wide_int (val, len, bm.value ());
 321   write_wide_int (val, len, bm.mask ());
 322 }
 323
 324 static inline void
 325 read_wide_int (wide_int &w,
 326                const HOST_WIDE_INT *val, unsigned short len, unsigned prec)
 327 {
 328   trailing_wide_int_storage stow (prec, &len,
 329                                   const_cast <HOST_WIDE_INT *> (val));
 330   w = trailing_wide_int (stow);
 331 }
 332
 333 // Restore a range of TYPE from storage into R.
 334
 335 void
 336 irange_storage::get_irange (irange &r, tree type) const
 337 {
 338   if (m_kind == VR_UNDEFINED)
 339     {
 340       r.set_undefined ();
 341       return;
 342     }
 343   if (m_kind == VR_VARYING)
 344     {
 345       r.set_varying (type);
 346       return;
 347     }
 348
 349   gcc_checking_assert (TYPE_PRECISION (type) == m_precision);
 350   const HOST_WIDE_INT *val = &m_val[0];
 351   const unsigned short *len = lengths_address ();
 352
 353   // Handle the common case where R can fit the new range.
 354   if (r.m_max_ranges >= m_num_ranges)
 355     {
 356       r.m_kind = VR_RANGE;
 357       r.m_num_ranges = m_num_ranges;
 358       r.m_type = type;
 359       for (unsigned i = 0; i < m_num_ranges * 2; ++i)
 360         {
 361           read_wide_int (r.m_base[i], val, *len, m_precision);
 362           val += *len++;
 363         }
 364     }
 365   // Otherwise build the range piecewise.
 366   else
 367     {
 368       r.set_undefined ();
 369       for (unsigned i = 0; i < m_num_ranges; ++i)
 370         {
 371           wide_int lb, ub;
 372           read_wide_int (lb, val, *len, m_precision);
 373           val += *len++;
 374           read_wide_int (ub, val, *len, m_precision);
 375           val += *len++;
 376           int_range<1> tmp (type, lb, ub);
 377           r.union_ (tmp);
 378         }
 379     }
 380
 381   wide_int bits_value, bits_mask;
 382   read_wide_int (bits_value, val, *len, m_precision);
 383   val += *len++;
 384   read_wide_int (bits_mask, val, *len, m_precision);
 385   r.m_bitmask = irange_bitmask (bits_value, bits_mask);
 386   if (r.m_kind == VR_VARYING)
 387     r.m_kind = VR_RANGE;
 388
 389   if (flag_checking)
 390     r.verify_range ();
 391 }
 392
 393 bool
 394 irange_storage::equal_p (const irange &r) const
 395 {
 396   if (m_kind == VR_UNDEFINED || r.undefined_p ())
 397     return m_kind == r.m_kind;
 398   if (m_kind == VR_VARYING || r.varying_p ())
 399     return m_kind == r.m_kind;
 400
 401   // ?? We could make this faster by doing the comparison in place,
 402   // without going through get_irange.
 403   int_range_max tmp;
 404   get_irange (tmp, r.type ());
 405   return tmp == r;
 406 }
 407
 408 // Return the size in bytes to allocate storage that can hold R.
 409
 410 size_t
 411 irange_storage::size (const irange &r)
 412 {
 413   if (r.undefined_p ())
 414     return sizeof (irange_storage);
 415
 416   unsigned prec = TYPE_PRECISION (r.type ());
 417   unsigned n = r.num_pairs () * 2 + 2;
 418   unsigned hwi_size = ((n * WIDE_INT_MAX_HWIS (prec) - 1)
 419                        * sizeof (HOST_WIDE_INT));
 420   unsigned len_size = n * sizeof (unsigned short);
 421   return sizeof (irange_storage) + hwi_size + len_size;
 422 }
 423
 424 // Return TRUE if R fits in the current storage.
 425
 426 bool
 427 irange_storage::fits_p (const irange &r) const
 428 {
 429   return m_max_ranges >= r.num_pairs ();
 430 }
 431
 432 void
 433 irange_storage::dump () const
 434 {
 435   fprintf (stderr, "irange_storage (prec=%d, ranges=%d):\n",
 436            m_precision, m_num_ranges);
 437
 438   if (m_num_ranges == 0)
 439     return;
 440
 441   const HOST_WIDE_INT *val = &m_val[0];
 442   const unsigned short *len = lengths_address ();
 443   int i, j;
 444
 445   fprintf (stderr, "  lengths = [ ");
 446   for (i = 0; i < m_num_ranges * 2 + 2; ++i)
 447     fprintf (stderr, "%d ", len[i]);
 448   fprintf (stderr, "]\n");
 449
 450   for (i = 0; i < m_num_ranges; ++i)
 451     {
 452       for (j = 0; j < *len; ++j)
 453         fprintf (stderr, "  [PAIR %d] LB " HOST_WIDE_INT_PRINT_DEC "\n", i,
 454                  *val++);
 455       ++len;
 456       for (j = 0; j < *len; ++j)
 457         fprintf (stderr, "  [PAIR %d] UB " HOST_WIDE_INT_PRINT_DEC "\n", i,
 458                  *val++);
 459       ++len;
 460     }
 461
 462   // Dump value/mask pair.
 463   for (j = 0; j < *len; ++j)
 464     fprintf (stderr, "  [VALUE] " HOST_WIDE_INT_PRINT_DEC "\n", *val++);
 465   ++len;
 466   for (j = 0; j < *len; ++j)
 467     fprintf (stderr, "  [MASK] " HOST_WIDE_INT_PRINT_DEC "\n", *val++);
 468 }
 469
 470 DEBUG_FUNCTION void
 471 debug (const irange_storage &storage)
 472 {
 473   storage.dump ();
 474   fprintf (stderr, "\n");
 475 }
 476
 477 //============================================================================
 478 // frange_storage implementation
 479 //============================================================================
 480
 481 // Allocate a new frange_storage object initialized to R.
 482
 483 frange_storage *
 484 frange_storage::alloc (vrange_internal_alloc &allocator, const frange &r)
 485 {
 486   size_t size = sizeof (frange_storage);
 487   frange_storage *p = static_cast <frange_storage *> (allocator.alloc (size));
 488   new (p) frange_storage (r);
 489   return p;
 490 }
 491
 492 void
 493 frange_storage::set_frange (const frange &r)
 494 {
 495   gcc_checking_assert (fits_p (r));
 496
 497   m_kind = r.m_kind;
 498   m_min = r.m_min;
 499   m_max = r.m_max;
 500   m_pos_nan = r.m_pos_nan;
 501   m_neg_nan = r.m_neg_nan;
 502 }
 503
 504 void
 505 frange_storage::get_frange (frange &r, tree type) const
 506 {
 507   gcc_checking_assert (r.supports_type_p (type));
 508
 509   // Handle explicit NANs.
 510   if (m_kind == VR_NAN)
 511     {
 512       if (HONOR_NANS (type))
 513         {
 514           if (m_pos_nan && m_neg_nan)
 515             r.set_nan (type);
 516           else
 517             r.set_nan (type, m_neg_nan);
 518         }
 519       else
 520         r.set_undefined ();
 521       return;
 522     }
 523   if (m_kind == VR_UNDEFINED)
 524     {
 525       r.set_undefined ();
 526       return;
 527     }
 528
 529   // We use the constructor to create the new range instead of writing
 530   // out the bits into the frange directly, because the global range
 531   // being read may be being inlined into a function with different
 532   // restrictions as when it was originally written.  We want to make
 533   // sure the resulting range is canonicalized correctly for the new
 534   // consumer.
 535   r = frange (type, m_min, m_max, m_kind);
 536
 537   // The constructor will set the NAN bits for HONOR_NANS, but we must
 538   // make sure to set the NAN sign if known.
 539   if (HONOR_NANS (type) && (m_pos_nan ^ m_neg_nan) == 1)
 540     r.update_nan (m_neg_nan);
 541   else if (!m_pos_nan && !m_neg_nan)
 542     r.clear_nan ();
 543 }
 544
 545 bool
 546 frange_storage::equal_p (const frange &r) const
 547 {
 548   if (r.undefined_p ())
 549     return m_kind == VR_UNDEFINED;
 550
 551   frange tmp;
 552   get_frange (tmp, r.type ());
 553   return tmp == r;
 554 }
 555
 556 bool
 557 frange_storage::fits_p (const frange &) const
 558 {
 559   return true;
 560 }
 561
 562 static vrange_allocator ggc_vrange_allocator (true);
 563
 564 vrange_storage *ggc_alloc_vrange_storage (tree type)
 565 {
 566   return ggc_vrange_allocator.clone_varying (type);
 567 }
 568
 569 vrange_storage *ggc_alloc_vrange_storage (const vrange &r)
 570 {
 571   return ggc_vrange_allocator.clone (r);
 572 }