[PATCH] [GCC 11] tree-optimization/100299 - Cherry picked solution from trunk

[PATCH] [GCC 11] tree-optimization/100299 - Cherry picked solution from trunk

[Andrew MacLeod]

[-- Attachment #1: Type: text/plain, Size: 236 bytes --]

The 2 recent patches, plus the original abstraction patch can be simply 
cherry picked for gcc 11.

I have applied the 3 patches to the current gcc 11 release, and it 
bootstrapped with no regressions on x86_64-pc-linux-gnu.

Andrew




[-- Attachment #2: 0001-Clean-up-and-virtualize-the-on-entry-cache-interface.patch --]
[-- Type: text/x-patch, Size: 10207 bytes --]

From 58289b678064c4b4e1efeb806f78c42d86ae31a4 Mon Sep 17 00:00:00 2001
From: Andrew MacLeod <amacleod@redhat.com>
Date: Fri, 7 May 2021 12:03:01 -0400
Subject: [PATCH 1/4] Clean up and virtualize the on-entry cache interface.

Cleanup/Virtualize the ssa_block_range class, and implement the current
vector approach as a derived class.
Allow memory allocation from the irange allocator obstack for easy freeing.

	* gimple-range-cache.cc (ssa_block_ranges): Virtualize.
	(sbr_vector): Renamed from ssa_block_cache.
	(sbr_vector::sbr_vector): Allocate from obstack abd initialize.
	(ssa_block_ranges::~ssa_block_ranges): Remove.
	(sbr_vector::set_bb_range): Use varying and undefined cached values.
	(ssa_block_ranges::set_bb_varying): Remove.
	(sbr_vector::get_bb_range): Adjust assert.
	(sbr_vector::bb_range_p): Adjust assert.
	(~block_range_cache): No freeing loop required.
	(block_range_cache::get_block_ranges): Remove.
	(block_range_cache::set_bb_range): Inline get_block_ranges.
	(block_range_cache::set_bb_varying): Remove.
	* gimple-range-cache.h (set_bb_varying): Remove prototype.
	* value-range.h (irange_allocator::get_memory): New.

(cherry picked from commit 14b0f37a644d7b59e1737fb275ec4fff044972a8)
---
 gcc/gimple-range-cache.cc | 165 ++++++++++++++++----------------------
 gcc/gimple-range-cache.h  |   1 -
 gcc/value-range.h         |   9 +++
 3 files changed, 80 insertions(+), 95 deletions(-)

diff --git a/gcc/gimple-range-cache.cc b/gcc/gimple-range-cache.cc
index 38e4fe1c7c0..2be83d698ab 100644
--- a/gcc/gimple-range-cache.cc
+++ b/gcc/gimple-range-cache.cc
@@ -107,29 +107,53 @@ non_null_ref::process_name (tree name)
 
 // -------------------------------------------------------------------------
 
-// This class implements a cache of ranges indexed by basic block.  It
-// represents all that is known about an SSA_NAME on entry to each
-// block.  It caches a range-for-type varying range so it doesn't need
-// to be reformed all the time.  If a range is ever always associated
-// with a type, we can use that instead.  Whenever varying is being
-// set for a block, the cache simply points to this cached one rather
-// than create a new one each time.
+// This class represents the API into a cache of ranges for an SSA_NAME.
+// Routines must be implemented to set, get, and query if a value is set.
 
 class ssa_block_ranges
 {
 public:
-  ssa_block_ranges (tree t, irange_allocator *allocator);
-  ~ssa_block_ranges ();
-
-  void set_bb_range (const basic_block bb, const irange &r);
-  void set_bb_varying (const basic_block bb);
-  bool get_bb_range (irange &r, const basic_block bb);
-  bool bb_range_p (const basic_block bb);
+  virtual void set_bb_range (const basic_block bb, const irange &r) = 0;
+  virtual bool get_bb_range (irange &r, const basic_block bb) = 0;
+  virtual bool bb_range_p (const basic_block bb) = 0;
 
   void dump(FILE *f);
-private:
-  vec<irange *> m_tab;
-  irange *m_type_range;
+};
+
+// Print the list of known ranges for file F in a nice format.
+
+void
+ssa_block_ranges::dump (FILE *f)
+{
+  basic_block bb;
+  int_range_max r;
+
+  FOR_EACH_BB_FN (bb, cfun)
+    if (get_bb_range (r, bb))
+      {
+	fprintf (f, "BB%d  -> ", bb->index);
+	r.dump (f);
+	fprintf (f, "\n");
+      }
+}
+
+// This class implements the range cache as a linear vector, indexed by BB.
+// It caches a varying and undefined range which are used instead of
+// allocating new ones each time.
+
+class sbr_vector : public ssa_block_ranges
+{
+public:
+  sbr_vector (tree t, irange_allocator *allocator);
+
+  virtual void set_bb_range (const basic_block bb, const irange &r) OVERRIDE;
+  virtual bool get_bb_range (irange &r, const basic_block bb) OVERRIDE;
+  virtual bool bb_range_p (const basic_block bb) OVERRIDE;
+protected:
+  irange **m_tab;	// Non growing vector.
+  int m_tab_size;
+  int_range<2> m_varying;
+  int_range<2> m_undefined;
   tree m_type;
   irange_allocator *m_irange_allocator;
 };
@@ -137,55 +161,43 @@ private:
 
 // Initialize a block cache for an ssa_name of type T.
 
-ssa_block_ranges::ssa_block_ranges (tree t, irange_allocator *allocator)
+sbr_vector::sbr_vector (tree t, irange_allocator *allocator)
 {
   gcc_checking_assert (TYPE_P (t));
   m_type = t;
   m_irange_allocator = allocator;
-
-  m_tab.create (0);
-  m_tab.safe_grow_cleared (last_basic_block_for_fn (cfun));
+  m_tab_size = last_basic_block_for_fn (cfun) + 1;
+  m_tab = (irange **)allocator->get_memory (m_tab_size * sizeof (irange *));
+  memset (m_tab, 0, m_tab_size * sizeof (irange *));
 
   // Create the cached type range.
-  m_type_range = m_irange_allocator->allocate (2);
-  m_type_range->set_varying (t);
-
-  m_tab[ENTRY_BLOCK_PTR_FOR_FN (cfun)->index] = m_type_range;
-}
-
-// Destruct block range.
-
-ssa_block_ranges::~ssa_block_ranges ()
-{
-  m_tab.release ();
+  m_varying.set_varying (t);
+  m_undefined.set_undefined ();
 }
 
 // Set the range for block BB to be R.
 
 void
-ssa_block_ranges::set_bb_range (const basic_block bb, const irange &r)
+sbr_vector::set_bb_range (const basic_block bb, const irange &r)
 {
-  gcc_checking_assert ((unsigned) bb->index < m_tab.length ());
-  irange *m = m_irange_allocator->allocate (r);
+  irange *m;
+  gcc_checking_assert (bb->index < m_tab_size);
+  if (r.varying_p ())
+    m = &m_varying;
+  else if (r.undefined_p ())
+    m = &m_undefined;
+  else
+    m = m_irange_allocator->allocate (r);
   m_tab[bb->index] = m;
 }
 
-// Set the range for block BB to the range for the type.
-
-void
-ssa_block_ranges::set_bb_varying (const basic_block bb)
-{
-  gcc_checking_assert ((unsigned) bb->index < m_tab.length ());
-  m_tab[bb->index] = m_type_range;
-}
-
 // Return the range associated with block BB in R.  Return false if
 // there is no range.
 
 bool
-ssa_block_ranges::get_bb_range (irange &r, const basic_block bb)
+sbr_vector::get_bb_range (irange &r, const basic_block bb)
 {
-  gcc_checking_assert ((unsigned) bb->index < m_tab.length ());
+  gcc_checking_assert (bb->index < m_tab_size);
   irange *m = m_tab[bb->index];
   if (m)
     {
@@ -198,30 +210,12 @@ ssa_block_ranges::get_bb_range (irange &r, const basic_block bb)
 // Return true if a range is present.
 
 bool
-ssa_block_ranges::bb_range_p (const basic_block bb)
+sbr_vector::bb_range_p (const basic_block bb)
 {
-  gcc_checking_assert ((unsigned) bb->index < m_tab.length ());
+  gcc_checking_assert (bb->index < m_tab_size);
   return m_tab[bb->index] != NULL;
 }
 
-
-// Print the list of known ranges for file F in a nice format.
-
-void
-ssa_block_ranges::dump (FILE *f)
-{
-  basic_block bb;
-  int_range_max r;
-
-  FOR_EACH_BB_FN (bb, cfun)
-    if (get_bb_range (r, bb))
-      {
-	fprintf (f, "BB%d  -> ", bb->index);
-	r.dump (f);
-	fprintf (f, "\n");
-      }
-}
-
 // -------------------------------------------------------------------------
 
 // Initialize the block cache.
@@ -237,38 +231,36 @@ block_range_cache::block_range_cache ()
 
 block_range_cache::~block_range_cache ()
 {
-  unsigned x;
-  for (x = 0; x < m_ssa_ranges.length (); ++x)
-    {
-      if (m_ssa_ranges[x])
-	delete m_ssa_ranges[x];
-    }
   delete m_irange_allocator;
   // Release the vector itself.
   m_ssa_ranges.release ();
 }
 
-// Return a reference to the ssa_block_cache for NAME.  If it has not been
-// accessed yet, allocate it first.
+// Set the range for NAME on entry to block BB to R.
+// If it has not been // accessed yet, allocate it first.
 
-ssa_block_ranges &
-block_range_cache::get_block_ranges (tree name)
+void
+block_range_cache::set_bb_range (tree name, const basic_block bb,
+				 const irange &r)
 {
   unsigned v = SSA_NAME_VERSION (name);
   if (v >= m_ssa_ranges.length ())
     m_ssa_ranges.safe_grow_cleared (num_ssa_names + 1);
 
   if (!m_ssa_ranges[v])
-    m_ssa_ranges[v] = new ssa_block_ranges (TREE_TYPE (name),
+    {
+      void *r = m_irange_allocator->get_memory (sizeof (sbr_vector));
+      m_ssa_ranges[v] = new (r) sbr_vector (TREE_TYPE (name),
 					    m_irange_allocator);
-  return *(m_ssa_ranges[v]);
+    }
+  m_ssa_ranges[v]->set_bb_range (bb, r);
 }
 
 
 // Return a pointer to the ssa_block_cache for NAME.  If it has not been
 // accessed yet, return NULL.
 
-ssa_block_ranges *
+inline ssa_block_ranges *
 block_range_cache::query_block_ranges (tree name)
 {
   unsigned v = SSA_NAME_VERSION (name);
@@ -277,22 +269,7 @@ block_range_cache::query_block_ranges (tree name)
   return m_ssa_ranges[v];
 }
 
-// Set the range for NAME on entry to block BB to R.
 
-void
-block_range_cache::set_bb_range (tree name, const basic_block bb,
-				 const irange &r)
-{
-  return get_block_ranges (name).set_bb_range (bb, r);
-}
-
-// Set the range for NAME on entry to block BB to varying.
-
-void
-block_range_cache::set_bb_varying (tree name, const basic_block bb)
-{
-  return get_block_ranges (name).set_bb_varying (bb);
-}
 
 // Return the range for NAME on entry to BB in R.  Return true if there
 // is one.
diff --git a/gcc/gimple-range-cache.h b/gcc/gimple-range-cache.h
index 2b36a02654b..bccb5cc2442 100644
--- a/gcc/gimple-range-cache.h
+++ b/gcc/gimple-range-cache.h
@@ -51,7 +51,6 @@ public:
   ~block_range_cache ();
 
   void set_bb_range (tree name, const basic_block bb, const irange &r);
-  void set_bb_varying (tree name, const basic_block bb);
   bool get_bb_range (irange &r, tree name, const basic_block bb);
   bool bb_range_p (tree name, const basic_block bb);
 
diff --git a/gcc/value-range.h b/gcc/value-range.h
index bfc54a2473f..54623b97a1f 100644
--- a/gcc/value-range.h
+++ b/gcc/value-range.h
@@ -639,6 +639,7 @@ public:
   // Return a copy of SRC with the minimum amount of sub-ranges needed
   // to represent it.
   irange *allocate (const irange &src);
+  void *get_memory (unsigned num_bytes);
 private:
   DISABLE_COPY_AND_ASSIGN (irange_allocator);
   struct obstack m_obstack;
@@ -656,6 +657,14 @@ irange_allocator::~irange_allocator ()
   obstack_free (&m_obstack, NULL);
 }
 
+// Provide a hunk of memory from the obstack
+inline void *
+irange_allocator::get_memory (unsigned num_bytes)
+{
+  void *r = obstack_alloc (&m_obstack, num_bytes);
+  return r;
+}
+
 // Return a new range with NUM_PAIRS.
 
 inline irange *
-- 
2.25.4


[-- Attachment #3: 0002-Implement-multi-bit-aligned-accessors-for-sparse-bit.patch --]
[-- Type: text/x-patch, Size: 5890 bytes --]

From e65205de9c7302a2a7d903ba8703461009cdacda Mon Sep 17 00:00:00 2001
From: Andrew MacLeod <amacleod@redhat.com>
Date: Mon, 7 Jun 2021 13:12:01 -0400
Subject: [PATCH 2/4] Implement multi-bit aligned accessors for sparse bitmap.

Provide set/get routines to allow sparse bitmaps to be treated as an array
of multiple bit values. Only chunk sizes that are powers of 2 are supported.

	* bitmap.c (bitmap_set_aligned_chunk): New.
	(bitmap_get_aligned_chunk): New.
	(test_aligned_chunk): New.
	(bitmap_c_tests): Call test_aligned_chunk.
	* bitmap.h (bitmap_set_aligned_chunk, bitmap_get_aligned_chunk): New.

(cherry picked from commit 5ad089a3c946aec655436fa3b0b50d6574b78197)
---
 gcc/bitmap.c | 108 +++++++++++++++++++++++++++++++++++++++++++++++++++
 gcc/bitmap.h |   7 ++++
 2 files changed, 115 insertions(+)

diff --git a/gcc/bitmap.c b/gcc/bitmap.c
index 5a650cdfc1d..b915fdfbb54 100644
--- a/gcc/bitmap.c
+++ b/gcc/bitmap.c
@@ -1004,6 +1004,83 @@ bitmap_bit_p (const_bitmap head, int bit)
   return (ptr->bits[word_num] >> bit_num) & 1;
 }
 \f
+/* Set CHUNK_SIZE bits at a time in bitmap HEAD.
+   Store CHUNK_VALUE starting at bits CHUNK * chunk_size.
+   This is the set routine for viewing bitmap as a multi-bit sparse array.  */
+
+void
+bitmap_set_aligned_chunk (bitmap head, unsigned int chunk,
+			  unsigned int chunk_size, BITMAP_WORD chunk_value)
+{
+  // Ensure chunk size is a power of 2 and fits in BITMAP_WORD.
+  gcc_checking_assert (pow2p_hwi (chunk_size));
+  gcc_checking_assert (chunk_size < (sizeof (BITMAP_WORD) * CHAR_BIT));
+
+  // Ensure chunk_value is within range of chunk_size bits.
+  BITMAP_WORD max_value = (1 << chunk_size) - 1;
+  gcc_checking_assert (chunk_value <= max_value);
+
+  unsigned bit = chunk * chunk_size;
+  unsigned indx = bit / BITMAP_ELEMENT_ALL_BITS;
+  bitmap_element *ptr;
+  if (!head->tree_form)
+    ptr = bitmap_list_find_element (head, indx);
+  else
+    ptr = bitmap_tree_find_element (head, indx);
+  unsigned word_num = bit / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS;
+  unsigned bit_num  = bit % BITMAP_WORD_BITS;
+  BITMAP_WORD bit_val = chunk_value << bit_num;
+  BITMAP_WORD mask = ~(max_value << bit_num);
+
+  if (ptr != 0)
+    {
+      ptr->bits[word_num] &= mask;
+      ptr->bits[word_num] |= bit_val;
+      return;
+    }
+
+  ptr = bitmap_element_allocate (head);
+  ptr->indx = bit / BITMAP_ELEMENT_ALL_BITS;
+  ptr->bits[word_num] = bit_val;
+  if (!head->tree_form)
+    bitmap_list_link_element (head, ptr);
+  else
+    bitmap_tree_link_element (head, ptr);
+}
+
+/* This is the get routine for viewing bitmap as a multi-bit sparse array.
+   Return a set of CHUNK_SIZE consecutive bits from HEAD, starting at bit
+   CHUNK * chunk_size.   */
+
+BITMAP_WORD
+bitmap_get_aligned_chunk (const_bitmap head, unsigned int chunk,
+			  unsigned int chunk_size)
+{
+  // Ensure chunk size is a power of 2, fits in BITMAP_WORD and is in range.
+  gcc_checking_assert (pow2p_hwi (chunk_size));
+  gcc_checking_assert (chunk_size < (sizeof (BITMAP_WORD) * CHAR_BIT));
+
+  BITMAP_WORD max_value = (1 << chunk_size) - 1;
+  unsigned bit = chunk * chunk_size;
+  unsigned int indx = bit / BITMAP_ELEMENT_ALL_BITS;
+  const bitmap_element *ptr;
+  unsigned bit_num;
+  unsigned word_num;
+
+  if (!head->tree_form)
+    ptr = bitmap_list_find_element (const_cast<bitmap> (head), indx);
+  else
+    ptr = bitmap_tree_find_element (const_cast<bitmap> (head), indx);
+  if (ptr == 0)
+    return 0;
+
+  bit_num = bit % BITMAP_WORD_BITS;
+  word_num = bit / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS;
+
+  // Return 4 bits.
+  return (ptr->bits[word_num] >> bit_num) & max_value;
+}
+\f
 #if GCC_VERSION < 3400
 /* Table of number of set bits in a character, indexed by value of char.  */
 static const unsigned char popcount_table[] =
@@ -2857,6 +2934,33 @@ test_bitmap_single_bit_set_p ()
   ASSERT_EQ (1066, bitmap_first_set_bit (b));
 }
 
+/* Verify accessing aligned bit chunks works as expected.  */
+
+static void
+test_aligned_chunk (unsigned num_bits)
+{
+  bitmap b = bitmap_gc_alloc ();
+  int limit = 2 ^ num_bits;
+
+  int index = 3;
+  for (int x = 0; x < limit; x++)
+    {
+      bitmap_set_aligned_chunk (b, index, num_bits, (BITMAP_WORD) x);
+      ASSERT_TRUE ((int) bitmap_get_aligned_chunk (b, index, num_bits) == x);
+      ASSERT_TRUE ((int) bitmap_get_aligned_chunk (b, index + 1,
+						   num_bits) == 0);
+      ASSERT_TRUE ((int) bitmap_get_aligned_chunk (b, index - 1,
+						   num_bits) == 0);
+      index += 3;
+    }
+  index = 3;
+  for (int x = 0; x < limit ; x++)
+    {
+      ASSERT_TRUE ((int) bitmap_get_aligned_chunk (b, index, num_bits) == x);
+      index += 3;
+    }
+}
+
 /* Run all of the selftests within this file.  */
 
 void
@@ -2867,6 +2971,10 @@ bitmap_c_tests ()
   test_clear_bit_in_middle ();
   test_copying ();
   test_bitmap_single_bit_set_p ();
+  /* Test 2, 4 and 8 bit aligned chunks.  */
+  test_aligned_chunk (2);
+  test_aligned_chunk (4);
+  test_aligned_chunk (8);
 }
 
 } // namespace selftest
diff --git a/gcc/bitmap.h b/gcc/bitmap.h
index 84632af7009..c9fd8af49d8 100644
--- a/gcc/bitmap.h
+++ b/gcc/bitmap.h
@@ -438,6 +438,13 @@ extern bool bitmap_set_bit (bitmap, int);
 /* Return true if a bit is set in a bitmap.  */
 extern int bitmap_bit_p (const_bitmap, int);
 
+/* Set and get multiple bit values in a sparse bitmap.  This allows a bitmap to
+   function as a sparse array of bit patterns where the patterns are
+   multiples of power of 2. This is more efficient than performing this as
+   multiple individual operations.  */
+void bitmap_set_aligned_chunk (bitmap, unsigned int, unsigned int, BITMAP_WORD);
+BITMAP_WORD bitmap_get_aligned_chunk (const_bitmap, unsigned int, unsigned int);
+
 /* Debug functions to print a bitmap.  */
 extern void debug_bitmap (const_bitmap);
 extern void debug_bitmap_file (FILE *, const_bitmap);
-- 
2.25.4


[-- Attachment #4: 0003-Implement-a-sparse-bitmap-representation-for-Rangers.patch --]
[-- Type: text/x-patch, Size: 8266 bytes --]

From ec7a3bd4136639379666923573108146df024a19 Mon Sep 17 00:00:00 2001
From: Andrew MacLeod <amacleod@redhat.com>
Date: Mon, 7 Jun 2021 13:18:55 -0400
Subject: [PATCH 3/4] Implement a sparse bitmap representation for Rangers
 on-entry cache.

Use a sparse representation for the on entry cache, and utilize it when
the number of basic blocks in the function exceeds param_evrp_sparse_threshold.

	PR tree-optimization/PR100299
	* gimple-range-cache.cc (class sbr_sparse_bitmap): New.
	(sbr_sparse_bitmap::sbr_sparse_bitmap): New.
	(sbr_sparse_bitmap::bitmap_set_quad): New.
	(sbr_sparse_bitmap::bitmap_get_quad): New.
	(sbr_sparse_bitmap::set_bb_range): New.
	(sbr_sparse_bitmap::get_bb_range): New.
	(sbr_sparse_bitmap::bb_range_p): New.
	(block_range_cache::block_range_cache): initialize bitmap obstack.
	(block_range_cache::~block_range_cache): Destruct obstack.
	(block_range_cache::set_bb_range): Decide when to utilze the
	sparse on entry cache.
	* gimple-range-cache.h (block_range_cache): Add bitmap obstack.
	* params.opt (-param=evrp-sparse-threshold): New.

(cherry picked from commit 9858cd1a6827ee7a928318acb5e86389f79b4012)
---
 gcc/gimple-range-cache.cc | 147 +++++++++++++++++++++++++++++++++++++-
 gcc/gimple-range-cache.h  |   1 +
 gcc/params.opt            |   4 ++
 3 files changed, 149 insertions(+), 3 deletions(-)

diff --git a/gcc/gimple-range-cache.cc b/gcc/gimple-range-cache.cc
index 2be83d698ab..bc4b557b493 100644
--- a/gcc/gimple-range-cache.cc
+++ b/gcc/gimple-range-cache.cc
@@ -216,12 +216,140 @@ sbr_vector::bb_range_p (const basic_block bb)
   return m_tab[bb->index] != NULL;
 }
 
+// This class implements the on entry cache via a sparse bitmap.
+// It uses the quad bit routines to access 4 bits at a time.
+// A value of 0 (the default) means there is no entry, and a value of
+// 1 thru SBR_NUM represents an element in the m_range vector.
+// Varying is given the first value (1) and pre-cached.
+// SBR_NUM + 1 represents the value of UNDEFINED, and is never stored.
+// SBR_NUM is the number of values that can be cached.
+// Indexes are 1..SBR_NUM and are stored locally at m_range[0..SBR_NUM-1]
+
+#define SBR_NUM		14
+#define SBR_UNDEF	SBR_NUM + 1
+#define SBR_VARYING	1
+
+class sbr_sparse_bitmap : public ssa_block_ranges
+{
+public:
+  sbr_sparse_bitmap (tree t, irange_allocator *allocator, bitmap_obstack *bm);
+  virtual void set_bb_range (const basic_block bb, const irange &r) OVERRIDE;
+  virtual bool get_bb_range (irange &r, const basic_block bb) OVERRIDE;
+  virtual bool bb_range_p (const basic_block bb) OVERRIDE;
+private:
+  void bitmap_set_quad (bitmap head, int quad, int quad_value);
+  int bitmap_get_quad (const_bitmap head, int quad);
+  irange_allocator *m_irange_allocator;
+  irange *m_range[SBR_NUM];
+  bitmap bitvec;
+  tree m_type;
+};
+
+// Initialize a block cache for an ssa_name of type T.
+
+sbr_sparse_bitmap::sbr_sparse_bitmap (tree t, irange_allocator *allocator,
+				bitmap_obstack *bm)
+{
+  gcc_checking_assert (TYPE_P (t));
+  m_type = t;
+  bitvec = BITMAP_ALLOC (bm);
+  m_irange_allocator = allocator;
+  // Pre-cache varying.
+  m_range[0] = m_irange_allocator->allocate (2);
+  m_range[0]->set_varying (t);
+  // Pre-cache zero and non-zero values for pointers.
+  if (POINTER_TYPE_P (t))
+    {
+      m_range[1] = m_irange_allocator->allocate (2);
+      m_range[1]->set_nonzero (t);
+      m_range[2] = m_irange_allocator->allocate (2);
+      m_range[2]->set_zero (t);
+    }
+  else
+    m_range[1] = m_range[2] = NULL;
+  // Clear SBR_NUM entries.
+  for (int x = 3; x < SBR_NUM; x++)
+    m_range[x] = 0;
+}
+
+// Set 4 bit values in a sparse bitmap. This allows a bitmap to
+// function as a sparse array of 4 bit values.
+// QUAD is the index, QUAD_VALUE is the 4 bit value to set.
+
+inline void
+sbr_sparse_bitmap::bitmap_set_quad (bitmap head, int quad, int quad_value)
+{
+  bitmap_set_aligned_chunk (head, quad, 4, (BITMAP_WORD) quad_value);
+}
+
+// Get a 4 bit value from a sparse bitmap. This allows a bitmap to
+// function as a sparse array of 4 bit values.
+// QUAD is the index.
+inline int
+sbr_sparse_bitmap::bitmap_get_quad (const_bitmap head, int quad)
+{
+  return (int) bitmap_get_aligned_chunk (head, quad, 4);
+}
+
+// Set the range on entry to basic block BB to R.
+
+void
+sbr_sparse_bitmap::set_bb_range (const basic_block bb, const irange &r)
+{
+  if (r.undefined_p ())
+    {
+      bitmap_set_quad (bitvec, bb->index, SBR_UNDEF);
+      return;
+    }
+
+  // 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] = m_irange_allocator->allocate (r);
+	bitmap_set_quad (bitvec, bb->index, x + 1);
+	return;
+      }
+  // All values are taken, default to VARYING.
+  bitmap_set_quad (bitvec, bb->index, SBR_VARYING);
+  return;
+}
+
+// Return the range associated with block BB in R.  Return false if
+// there is no range.
+
+bool
+sbr_sparse_bitmap::get_bb_range (irange &r, const basic_block bb)
+{
+  int value = bitmap_get_quad (bitvec, bb->index);
+
+  if (!value)
+    return false;
+
+  gcc_checking_assert (value <= SBR_UNDEF);
+  if (value == SBR_UNDEF)
+    r.set_undefined ();
+  else
+    r = *(m_range[value - 1]);
+  return true;
+}
+
+// Return true if a range is present.
+
+bool
+sbr_sparse_bitmap::bb_range_p (const basic_block bb)
+{
+  return (bitmap_get_quad (bitvec, bb->index) != 0);
+}
+
 // -------------------------------------------------------------------------
 
 // Initialize the block cache.
 
 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_irange_allocator = new irange_allocator;
@@ -234,6 +362,7 @@ block_range_cache::~block_range_cache ()
   delete m_irange_allocator;
   // Release the vector itself.
   m_ssa_ranges.release ();
+  bitmap_obstack_release (&m_bitmaps);
 }
 
 // Set the range for NAME on entry to block BB to R.
@@ -249,9 +378,21 @@ block_range_cache::set_bb_range (tree name, const basic_block bb,
 
   if (!m_ssa_ranges[v])
     {
-      void *r = m_irange_allocator->get_memory (sizeof (sbr_vector));
-      m_ssa_ranges[v] = new (r) sbr_vector (TREE_TYPE (name),
-					    m_irange_allocator);
+      // Use sparse representation if there are too many basic blocks.
+      if (last_basic_block_for_fn (cfun) > param_evrp_sparse_threshold)
+	{
+	  void *r = m_irange_allocator->get_memory (sizeof (sbr_sparse_bitmap));
+	  m_ssa_ranges[v] = new (r) sbr_sparse_bitmap (TREE_TYPE (name),
+						       m_irange_allocator,
+						       &m_bitmaps);
+	}
+      else
+	{
+	  // Otherwise use the default vector implemntation.
+	  void *r = m_irange_allocator->get_memory (sizeof (sbr_vector));
+	  m_ssa_ranges[v] = new (r) sbr_vector (TREE_TYPE (name),
+						m_irange_allocator);
+	}
     }
   m_ssa_ranges[v]->set_bb_range (bb, r);
 }
diff --git a/gcc/gimple-range-cache.h b/gcc/gimple-range-cache.h
index bccb5cc2442..43e576a51f9 100644
--- a/gcc/gimple-range-cache.h
+++ b/gcc/gimple-range-cache.h
@@ -61,6 +61,7 @@ private:
   ssa_block_ranges &get_block_ranges (tree name);
   ssa_block_ranges *query_block_ranges (tree name);
   irange_allocator *m_irange_allocator;
+  bitmap_obstack m_bitmaps;
 };
 
 // This global cache is used with the range engine as markers for what
diff --git a/gcc/params.opt b/gcc/params.opt
index 2e4cbdd7a71..8ba281b4cfa 100644
--- a/gcc/params.opt
+++ b/gcc/params.opt
@@ -126,6 +126,10 @@ Maximum size (in bytes) of objects tracked bytewise by dead store elimination.
 Common Joined UInteger Var(param_early_inlining_insns) Init(6) Optimization Param
 Maximal estimated growth of function body caused by early inlining of single call.
 
+-param=evrp-sparse-threshold=
+Common Joined UInteger Var(param_evrp_sparse_threshold) Init(800) Optimization Param
+Maximum number of basic blocks before EVRP uses a sparse cache.
+
 -param=evrp-mode=
 Common Joined Var(param_evrp_mode) Enum(evrp_mode) Init(EVRP_MODE_EVRP_FIRST) Param Optimization
 --param=evrp-mode=[legacy|ranger|legacy-first|ranger-first|ranger-trace|ranger-debug|trace|debug] Specifies the mode Early VRP should operate in.
-- 
2.25.4