vrange_storage overhaul

[tl;dr: This is a rewrite of value-range-storage.* such that global
ranges and the internal ranger cache can use the same efficient
storage mechanism.  It is optimized such that when wide_ints are
dropped into irange, the copying back and forth from storage will be
very fast, while being able to hold any number of sub-ranges
dynamically allocated at run-time.  This replaces the global storage
mechanism which was limited to 6-subranges.]

Previously we had a vrange allocator for use in the ranger cache.  It
worked with trees and could be used in place (fast), but it was not
memory efficient.  With the upcoming switch to wide_ints for irange,
we can't afford to allocate ranges that can be used in place, because
an irange will be significantly larger, as it will hold full
wide_ints.  We need a trailing_wide_int mechanism similar to what we
use for global ranges, but fast enough to use in the ranger's cache.

The global ranges had another allocation mechanism that was
trailing_wide_int based.  It was memory efficient but slow given the
constant conversions from trees to wide_ints.

This patch gets us the best of both worlds by providing a storage
mechanism with a custom trailing wide int interface, while at the same
time being fast enough to use in the ranger cache.

We use a custom trailing wide_int mechanism but more flexible than
trailing_wide_int, since the latter has compile-time fixed-sized
wide_ints.  The original TWI structure has the current length of each
wide_int in a static portion preceeding the variable length:

template <int N>
struct GTY((user)) trailing_wide_ints
{
...
...
  /* The current length of each number.
     that will, in turn, turn off TBAA on gimple, trees and RTL.  */
  struct {unsigned char len;} m_len[N];

  /* The variable-length part of the structure, which always contains
     at least one HWI.  Element I starts at index I * M_MAX_LEN.  */
  HOST_WIDE_INT m_val[1];
};

We need both m_len[] and m_val[] to be variable-length at run-time.
In the previous incarnation of the storage mechanism the limitation of
m_len[] being static meant that we were limited to whatever [N] could
use up the unused bits in the TWI control world.  In practice this
meant we were limited to 6 sub-ranges.  This worked fine for global
ranges, but is a no go for our internal cache, where we must represent
things exactly (ranges for switches, etc).

The new implementation removes this restriction by making both m_len[]
and m_val[] variable length.  Also, rolling our own allows future
optimization be using some of the leftover bits in the control world.

Also, in preparation for the wide_int conversion, vrange_storage is
now optimized to blast the bits directly into the ultimate irange
instead of going through the irange API.  So ultimately copying back
and forth between the ranger cache and the storage mechanism is just a
matter of copying a few bits for the control word, and copying an
array of HOST_WIDE_INTs.  These changes were heavily profiled, and
yielded a good chunk of the overall speedup for the wide_int
conversion.

Finally, vrange_storage is now a first class structure with GTY
markers and all, thus alleviating the void * hack in struct
tree_ssa_name and friends.  This removes a few warts in the API and
looks cleaner overall.

gcc/ChangeLog:

	* gimple-fold.cc (maybe_fold_comparisons_from_match_pd): Adjust
	for vrange_storage.
	* gimple-range-cache.cc (sbr_vector::sbr_vector): Same.
	(sbr_vector::grow): Same.
	(sbr_vector::set_bb_range): Same.
	(sbr_vector::get_bb_range): Same.
	(sbr_sparse_bitmap::sbr_sparse_bitmap): Same.
	(sbr_sparse_bitmap::set_bb_range): Same.
	(sbr_sparse_bitmap::get_bb_range): Same.
	(block_range_cache::block_range_cache): Same.
	(ssa_global_cache::ssa_global_cache): Same.
	(ssa_global_cache::get_global_range): Same.
	(ssa_global_cache::set_global_range): Same.
	* gimple-range-cache.h: Same.
	* gimple-range-edge.cc
	(gimple_outgoing_range::gimple_outgoing_range): Same.
	(gimple_outgoing_range::switch_edge_range): Same.
	(gimple_outgoing_range::calc_switch_ranges): Same.
	* gimple-range-edge.h: Same.
	* gimple-range-infer.cc
	(infer_range_manager::infer_range_manager): Same.
	(infer_range_manager::get_nonzero): Same.
	(infer_range_manager::maybe_adjust_range): Same.
	(infer_range_manager::add_range): Same.
	* gimple-range-infer.h: Rename obstack_vrange_allocator to
	vrange_allocator.
	* tree-core.h (struct irange_storage_slot): Remove.
	(struct tree_ssa_name): Remove irange_info and frange_info.  Make
	range_info a pointer to vrange_storage.
	* tree-ssanames.cc (range_info_fits_p): Adjust for vrange_storage.
	(range_info_alloc): Same.
	(range_info_free): Same.
	(range_info_get_range): Same.
	(range_info_set_range): Same.
	(get_nonzero_bits): Same.
	* value-query.cc (get_ssa_name_range_info): Same.
	* value-range-storage.cc (class vrange_internal_alloc): New.
	(class vrange_obstack_alloc): New.
	(class vrange_ggc_alloc): New.
	(vrange_allocator::vrange_allocator): New.
	(vrange_allocator::~vrange_allocator): New.
	(vrange_storage::alloc_slot): New.
	(vrange_allocator::alloc): New.
	(vrange_allocator::free): New.
	(vrange_allocator::clone): New.
	(vrange_allocator::clone_varying): New.
	(vrange_allocator::clone_undefined): New.
	(vrange_storage::alloc): New.
	(vrange_storage::set_vrange): Remove slot argument.
	(vrange_storage::get_vrange): Same.
	(vrange_storage::fits_p): Same.
	(vrange_storage::equal_p): New.
	(irange_storage::write_lengths_address): New.
	(irange_storage::lengths_address): New.
	(irange_storage_slot::alloc_slot): Remove.
	(irange_storage::alloc): New.
	(irange_storage_slot::irange_storage_slot): Remove.
	(irange_storage::irange_storage): New.
	(write_wide_int): New.
	(irange_storage_slot::set_irange): Remove.
	(irange_storage::set_irange): New.
	(read_wide_int): New.
	(irange_storage_slot::get_irange): Remove.
	(irange_storage::get_irange): New.
	(irange_storage_slot::size): Remove.
	(irange_storage::equal_p): New.
	(irange_storage_slot::num_wide_ints_needed): Remove.
	(irange_storage::size): New.
	(irange_storage_slot::fits_p): Remove.
	(irange_storage::fits_p): New.
	(irange_storage_slot::dump): Remove.
	(irange_storage::dump): New.
	(frange_storage_slot::alloc_slot): Remove.
	(frange_storage::alloc): New.
	(frange_storage_slot::set_frange): Remove.
	(frange_storage::set_frange): New.
	(frange_storage_slot::get_frange): Remove.
	(frange_storage::get_frange): New.
	(frange_storage_slot::fits_p): Remove.
	(frange_storage::equal_p): New.
	(frange_storage::fits_p): New.
	(ggc_vrange_allocator): New.
	(ggc_alloc_vrange_storage): New.
	* value-range-storage.h (class vrange_storage): Rewrite.
	(class irange_storage): Rewrite.
	(class frange_storage): Rewrite.
	(class obstack_vrange_allocator): Remove.
	(class ggc_vrange_allocator): Remove.
	(vrange_allocator::alloc_vrange): Remove.
	(vrange_allocator::alloc_irange): Remove.
	(vrange_allocator::alloc_frange): Remove.
	(ggc_alloc_vrange_storage): New.
	* value-range.h (class irange): Rename vrange_allocator to
	irange_storage.
	(class frange): Same.

1 files changed, 30 insertions, 31 deletions

diff --git a/gcc/gimple-range-cache.cc b/gcc/gimple-range-cache.cc
index 5510efb..92622fc 100644
--- a/gcc/gimple-range-cache.cc
+++ b/gcc/gimple-range-cache.cc
@@ -85,10 +85,10 @@ public:
   virtual bool get_bb_range (vrange &r, const_basic_block bb) override;
   virtual bool bb_range_p (const_basic_block bb) override;
 protected:
-  vrange **m_tab;	// Non growing vector.
+  vrange_storage **m_tab;	// Non growing vector.
   int m_tab_size;
-  vrange *m_varying;
-  vrange *m_undefined;
+  vrange_storage *m_varying;
+  vrange_storage *m_undefined;
   tree m_type;
   vrange_allocator *m_range_allocator;
   bool m_zero_p;
@@ -106,16 +106,14 @@ sbr_vector::sbr_vector (tree t, vrange_allocator *allocator, bool zero_p)
   m_zero_p = zero_p;
   m_range_allocator = allocator;
   m_tab_size = last_basic_block_for_fn (cfun) + 1;
-  m_tab = static_cast <vrange **>
-    (allocator->alloc (m_tab_size * sizeof (vrange *)));
+  m_tab = static_cast <vrange_storage **>
+    (allocator->alloc (m_tab_size * sizeof (vrange_storage *)));
   if (zero_p)
     memset (m_tab, 0, m_tab_size * sizeof (vrange *));
 
   // Create the cached type range.
-  m_varying = m_range_allocator->alloc_vrange (t);
-  m_undefined = m_range_allocator->alloc_vrange (t);
-  m_varying->set_varying (t);
-  m_undefined->set_undefined ();
+  m_varying = m_range_allocator->clone_varying (t);
+  m_undefined = m_range_allocator->clone_undefined (t);
 }
 
 // Grow the vector when the CFG has increased in size.
@@ -132,11 +130,11 @@ sbr_vector::grow ()
   int new_size = inc + curr_bb_size;
 
   // Allocate new memory, copy the old vector and clear the new space.
-  vrange **t = static_cast <vrange **>
-    (m_range_allocator->alloc (new_size * sizeof (vrange *)));
-  memcpy (t, m_tab, m_tab_size * sizeof (vrange *));
+  vrange_storage **t = static_cast <vrange_storage **>
+    (m_range_allocator->alloc (new_size * sizeof (vrange_storage *)));
+  memcpy (t, m_tab, m_tab_size * sizeof (vrange_storage *));
   if (m_zero_p)
-    memset (t + m_tab_size, 0, (new_size - m_tab_size) * sizeof (vrange *));
+    memset (t + m_tab_size, 0, (new_size - m_tab_size) * sizeof (vrange_storage *));
 
   m_tab = t;
   m_tab_size = new_size;
@@ -147,7 +145,7 @@ sbr_vector::grow ()
 bool
 sbr_vector::set_bb_range (const_basic_block bb, const vrange &r)
 {
-  vrange *m;
+  vrange_storage *m;
   if (bb->index >= m_tab_size)
     grow ();
   if (r.varying_p ())
@@ -168,10 +166,10 @@ sbr_vector::get_bb_range (vrange &r, const_basic_block bb)
 {
   if (bb->index >= m_tab_size)
     return false;
-  vrange *m = m_tab[bb->index];
+  vrange_storage *m = m_tab[bb->index];
   if (m)
     {
-      r = *m;
+      m->get_vrange (r, m_type);
       return true;
     }
   return false;
@@ -255,7 +253,7 @@ private:
   void bitmap_set_quad (bitmap head, int quad, int quad_value);
   int bitmap_get_quad (const_bitmap head, int quad);
   vrange_allocator *m_range_allocator;
-  vrange *m_range[SBR_NUM];
+  vrange_storage *m_range[SBR_NUM];
   bitmap_head bitvec;
   tree m_type;
 };
@@ -272,15 +270,16 @@ sbr_sparse_bitmap::sbr_sparse_bitmap (tree t, vrange_allocator *allocator,
   bitmap_tree_view (&bitvec);
   m_range_allocator = allocator;
   // Pre-cache varying.
-  m_range[0] = m_range_allocator->alloc_vrange (t);
-  m_range[0]->set_varying (t);
+  m_range[0] = m_range_allocator->clone_varying (t);
   // Pre-cache zero and non-zero values for pointers.
   if (POINTER_TYPE_P (t))
     {
-      m_range[1] = m_range_allocator->alloc_vrange (t);
-      m_range[1]->set_nonzero (t);
-      m_range[2] = m_range_allocator->alloc_vrange (t);
-      m_range[2]->set_zero (t);
+      int_range<2> nonzero;
+      nonzero.set_nonzero (t);
+      m_range[1] = m_range_allocator->clone (nonzero);
+      int_range<2> zero;
+      zero.set_zero (t);
+      m_range[2] = m_range_allocator->clone (zero);
     }
   else
     m_range[1] = m_range[2] = NULL;
@@ -321,7 +320,7 @@ sbr_sparse_bitmap::set_bb_range (const_basic_block bb, const vrange &r)
 
   // Loop thru the values to see if R is already present.
   for (int x = 0; x < SBR_NUM; x++)
-    if (!m_range[x] || r == *(m_range[x]))
+    if (!m_range[x] || m_range[x]->equal_p (r, m_type))
       {
 	if (!m_range[x])
 	  m_range[x] = m_range_allocator->clone (r);
@@ -348,7 +347,7 @@ sbr_sparse_bitmap::get_bb_range (vrange &r, const_basic_block bb)
   if (value == SBR_UNDEF)
     r.set_undefined ();
   else
-    r = *(m_range[value - 1]);
+    m_range[value - 1]->get_vrange (r, m_type);
   return true;
 }
 
@@ -369,7 +368,7 @@ block_range_cache::block_range_cache ()
   bitmap_obstack_initialize (&m_bitmaps);
   m_ssa_ranges.create (0);
   m_ssa_ranges.safe_grow_cleared (num_ssa_names);
-  m_range_allocator = new obstack_vrange_allocator;
+  m_range_allocator = new vrange_allocator;
 }
 
 // Remove any m_block_caches which have been created.
@@ -535,7 +534,7 @@ block_range_cache::dump (FILE *f, basic_block bb, bool print_varying)
 ssa_cache::ssa_cache ()
 {
   m_tab.create (0);
-  m_range_allocator = new obstack_vrange_allocator;
+  m_range_allocator = new vrange_allocator;
 }
 
 // Deconstruct an ssa cache.
@@ -567,10 +566,10 @@ ssa_cache::get_range (vrange &r, tree name) const
   if (v >= m_tab.length ())
     return false;
 
-  vrange *stow = m_tab[v];
+  vrange_storage *stow = m_tab[v];
   if (!stow)
     return false;
-  r = *stow;
+  stow->get_vrange (r, TREE_TYPE (name));
   return true;
 }
 
@@ -584,9 +583,9 @@ ssa_cache::set_range (tree name, const vrange &r)
   if (v >= m_tab.length ())
     m_tab.safe_grow_cleared (num_ssa_names + 1);
 
-  vrange *m = m_tab[v];
+  vrange_storage *m = m_tab[v];
   if (m && m->fits_p (r))
-    *m = r;
+    m->set_vrange (r);
   else
     m_tab[v] = m_range_allocator->clone (r);
   return m != NULL;