[PATCH 1/4] tree-optimization/104288 - Change non-null tracking from one bit to a pair.

[PATCH 1/4] tree-optimization/104288 - Change non-null tracking from one bit to a pair.

[Andrew MacLeod]

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

This patch changes the non-null tracking in ranger to use 2 bits in order
to distinguish between blocks which contain uses of NAME in:
   1) non-null generating statements,  (1 bit)
   2) statements which are not non-null generating (the other bit),  
THis is the new bit.
   3) and the existence of both.  (both bits)

It utilizes the aligned_chunk sparse bitmap code to track these states 
for each name, and has zero impact on functionality otherwise as the 
nonnull_deref_p routine still keys off a non-null access anywhere in the 
block.   This ensure we add the new capabilities without affected code 
generation or anything else.

There is a get/set routines, but internally i usually defer directly to 
the get/set_aligned_chunk routine for efficiency.  The overall impact is 
under .5% of EVRP/VRP compile time.  Most of the additional time is due 
to now setting a bit for all uses, even if the non-null property isnt set.

Bootstraps with no regressions.  OK for trunk?

Andrew

[-- Attachment #2: 0001-Change-non-null-tracking-from-one-bit-to-a-pair.patch --]
[-- Type: text/x-patch, Size: 6026 bytes --]

From 6cd863984a6bf49dc5d6ff00a510003679842e74 Mon Sep 17 00:00:00 2001
From: Andrew MacLeod <amacleod@redhat.com>
Date: Wed, 2 Feb 2022 14:43:29 -0500
Subject: [PATCH 1/3] Change non-null tracking from one bit to a pair.

This patch changes the non-null tracking in ranger to use 2 bits in order
to distinguish between blocks which contain uses of NAME in:
  1) non-null generating statements,
  2) statements which are not non-null,
  3) and the existance of both.

	* gimple-range-cache.cc (non_null_ref::get_bb_state): New.
	(non_null_ref::set_bb_state): New.
	(non_null_ref::non_null_deref_p): Use new 2 bit values.
	(non_null_ref::process_name): Use new 2 bit values.
	* gimple-range-cache.h (class non_null_ref): New prototypes.
---
 gcc/gimple-range-cache.cc | 82 ++++++++++++++++++++++++++++-----------
 gcc/gimple-range-cache.h  |  2 +
 2 files changed, 62 insertions(+), 22 deletions(-)

diff --git a/gcc/gimple-range-cache.cc b/gcc/gimple-range-cache.cc
index 16c881b13e1..52094f0bc6a 100644
--- a/gcc/gimple-range-cache.cc
+++ b/gcc/gimple-range-cache.cc
@@ -33,6 +33,13 @@ along with GCC; see the file COPYING3.  If not see
 #define DEBUG_RANGE_CACHE (dump_file					\
 			   && (param_ranger_debug & RANGER_DEBUG_CACHE))
 
+// 2 bits represent whether a non_zero or varying use were seen in a block.
+
+#define NN_NONE		0
+#define NN_VARYING	1
+#define NN_NON_ZERO	2
+#define NN_BOTH		(NN_VARYING | NN_NON_ZERO)
+
 // During contructor, allocate the vector of ssa_names.
 
 non_null_ref::non_null_ref ()
@@ -50,16 +57,26 @@ non_null_ref::~non_null_ref ()
   m_nn.release ();
 }
 
-// Return true if NAME has a non-null dereference in block bb.  If this is the
-// first query for NAME, calculate the summary first.
-// If SEARCH_DOM is true, the search the dominator tree as well.
+// Return the non-null state of NAME in block BB.
 
-bool
-non_null_ref::non_null_deref_p (tree name, basic_block bb, bool search_dom)
+unsigned long
+non_null_ref::get_bb_state (tree name, basic_block bb)
 {
-  if (!POINTER_TYPE_P (TREE_TYPE (name)))
-    return false;
+  unsigned v = SSA_NAME_VERSION (name);
+  if (v >= m_nn.length ())
+    m_nn.safe_grow_cleared (num_ssa_names + 1);
+
+  if (!m_nn[v])
+    process_name (name);
+
+  return bitmap_get_aligned_chunk (m_nn[v], bb->index, 2);
+}
 
+// Set the non-null state of NAME in block BB to VAL.
+
+void
+non_null_ref::set_bb_state (tree name, basic_block bb, unsigned long val)
+{
   unsigned v = SSA_NAME_VERSION (name);
   if (v >= m_nn.length ())
     m_nn.safe_grow_cleared (num_ssa_names + 1);
@@ -67,7 +84,22 @@ non_null_ref::non_null_deref_p (tree name, basic_block bb, bool search_dom)
   if (!m_nn[v])
     process_name (name);
 
-  if (bitmap_bit_p (m_nn[v], bb->index))
+  gcc_checking_assert (val <= NN_BOTH);
+  bitmap_set_aligned_chunk (m_nn[v], bb->index, 2, val);
+}
+
+// Return true if NAME has a non-null dereference in block bb.  If this is the
+// first query for NAME, calculate the summary first.
+// If SEARCH_DOM is true, the search the dominator tree as well.
+
+bool
+non_null_ref::non_null_deref_p (tree name, basic_block bb, bool search_dom)
+{
+  unsigned v = SSA_NAME_VERSION (name);
+  if (!POINTER_TYPE_P (TREE_TYPE (name)))
+    return false;
+
+  if (get_bb_state (name, bb) >= NN_NON_ZERO)
     return true;
 
   // See if any dominator has set non-zero.
@@ -81,7 +113,7 @@ non_null_ref::non_null_deref_p (tree name, basic_block bb, bool search_dom)
       for ( ;
 	    bb && bb != def_dom;
 	    bb = get_immediate_dominator (CDI_DOMINATORS, bb))
-	if (bitmap_bit_p (m_nn[v], bb->index))
+	if (bitmap_get_aligned_chunk (m_nn[v], bb->index, 2) >= NN_NON_ZERO)
 	  return true;
     }
   return false;
@@ -116,9 +148,8 @@ non_null_ref::adjust_range (irange &r, tree name, basic_block bb,
   return false;
 }
 
-// Allocate an populate the bitmap for NAME.  An ON bit for a block
-// index indicates there is a non-null reference in that block.  In
-// order to populate the bitmap, a quick run of all the immediate uses
+// Allocate and populate the non-null state map for NAME.
+// In order to populate the bitmap, a quick run of all the immediate uses
 // are made and the statement checked to see if a non-null dereference
 // is made on that statement.
 
@@ -139,24 +170,31 @@ non_null_ref::process_name (tree name)
     return;
 
   b = BITMAP_ALLOC (&m_bitmaps);
+  m_nn[v] = b;
+
+  if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (name))
+    return;
 
   // Loop over each immediate use and see if it implies a non-null value.
   FOR_EACH_IMM_USE_FAST (use_p, iter, name)
     {
       gimple *s = USE_STMT (use_p);
-      unsigned index = gimple_bb (s)->index;
-
-      // If bit is already set for this block, dont bother looking again.
-      if (bitmap_bit_p (b, index))
+      if (is_a <gphi *> (s))
 	continue;
+      basic_block bb = gimple_bb (s);
+      // If bit is already set for this block, dont bother looking again.
+      unsigned long val = bitmap_get_aligned_chunk (b, bb->index, 2);
+      unsigned long new_val;
 
-      // If we can infer a nonnull range, then set the bit for this BB
-      if (!SSA_NAME_OCCURS_IN_ABNORMAL_PHI (name)
-	  && infer_nonnull_range (s, name))
-	bitmap_set_bit (b, index);
-    }
+      // If we can infer a nonnull range, then set the bit for this BB.
+      if (infer_nonnull_range (s, name))
+	new_val = val | NN_NON_ZERO;
+      else
+	new_val = val | NN_VARYING;
 
-  m_nn[v] = b;
+      if (val != new_val)
+	bitmap_set_aligned_chunk (b, bb->index, 2, new_val);
+    }
 }
 
 // -------------------------------------------------------------------------
diff --git a/gcc/gimple-range-cache.h b/gcc/gimple-range-cache.h
index b54b6882aa8..2e61824593e 100644
--- a/gcc/gimple-range-cache.h
+++ b/gcc/gimple-range-cache.h
@@ -39,6 +39,8 @@ public:
 private:
   vec <bitmap> m_nn;
   void process_name (tree name);
+  unsigned long get_bb_state (tree name, basic_block bb);
+  void set_bb_state (tree name, basic_block bb, unsigned long);
   bitmap_obstack m_bitmaps;
 };
 
-- 
2.17.2