diff mbox series

[COMMITTED] Make range_from_dom more effective.

Message ID 5f41caee-47cd-2599-b5b7-63e9d459c730@redhat.com
State New
Headers show
Series [COMMITTED] Make range_from_dom more effective. | expand

Commit Message

Andrew MacLeod May 13, 2022, 1:48 p.m. UTC
This patch enhances  how ranger's cache picks up ranges from dominators.

The previous version was pretty basic, simply walking the DOM tree back 
until it ran into a "complicated" situation.. (for instance when the 
dominator has multiple successors)  then falling back to the 
non-dominator based propagator.

This patch makes it re-entrant, and allows it to deal with multiple 
successors and more precisely updates the cache for future queries. It 
also handles other situations which enable it to always resolve a query.

It also adds query modes which enable the cache to more precisely 
control when updates happen making it more usable in read-only contexts.

Bootstraps on x86_64-pc-linux-gnu with no regression. Pushed.

Andrew
diff mbox series

Patch

commit 6b156044c12bc4582511fe270b10450c943476dd
Author: Andrew MacLeod <amacleod@redhat.com>
Date:   Thu Mar 24 15:28:43 2022 -0400

    Make range_from_dom more effective.
    
    Add modes to range_from_dom such that we can simply query, or adjust the
    cache and deal with multiple predecessor blocks.
    
            * gimple-range-cache.cc (ranger_cache::ranger_cache): Start with
            worlist truncated.
            (ranger_cache::entry_range): Add rfd_mode parameter.
            (ranger_cache::exit_range): Ditto.
            (ranger_cache::edge_range): New.  Incorporate from range_on_edge.
            (ranger_cache::range_of_expr): Adjust call to entry_range.
            (ranger_cache::range_on_edge): Split to edge_range and call.
            (ranger_cache::fill_block_cache): Always invoke range_from_dom.
            (ranger_cache::range_from_dom): Make reentrant, add search mode, handle
            mutiple predecessors.
            (ranger_cache::update_to_nonnull): Adjust call to exit_range.
            * gimple-range-cache.h (ranger_cache): Add enum rfd_mode.  Adjust
            prototypes.

diff --git a/gcc/gimple-range-cache.cc b/gcc/gimple-range-cache.cc
index 421ea1a20ef..bdb30460345 100644
--- a/gcc/gimple-range-cache.cc
+++ b/gcc/gimple-range-cache.cc
@@ -864,6 +864,7 @@  ranger_cache::ranger_cache (int not_executable_flag)
 {
   m_workback.create (0);
   m_workback.safe_grow_cleared (last_basic_block_for_fn (cfun));
+  m_workback.truncate (0);
   m_temporal = new temporal_cache;
   // If DOM info is available, spawn an oracle as well.
   if (dom_info_available_p (CDI_DOMINATORS))
@@ -1008,10 +1009,12 @@  ranger_cache::range_of_def (irange &r, tree name, basic_block bb)
     }
 }
 
-// Get the range of NAME as it occurs on entry to block BB.
+// Get the range of NAME as it occurs on entry to block BB.  Use MODE for
+// lookups.
 
 void
-ranger_cache::entry_range (irange &r, tree name, basic_block bb)
+ranger_cache::entry_range (irange &r, tree name, basic_block bb,
+			   enum rfd_mode mode)
 {
   if (bb == ENTRY_BLOCK_PTR_FOR_FN (cfun))
     {
@@ -1022,13 +1025,16 @@  ranger_cache::entry_range (irange &r, tree name, basic_block bb)
   // Look for the on-entry value of name in BB from the cache.
   // Otherwise pick up the best available global value.
   if (!m_on_entry.get_bb_range (r, name, bb))
-    range_of_def (r, name);
+    if (!range_from_dom (r, name, bb, mode))
+      range_of_def (r, name);
 }
 
-// Get the range of NAME as it occurs on exit from block BB.
+// Get the range of NAME as it occurs on exit from block BB.  Use MODE for
+// lookups.
 
 void
-ranger_cache::exit_range (irange &r, tree name, basic_block bb)
+ranger_cache::exit_range (irange &r, tree name, basic_block bb,
+			  enum rfd_mode mode)
 {
   if (bb == ENTRY_BLOCK_PTR_FOR_FN (cfun))
     {
@@ -1041,8 +1047,25 @@  ranger_cache::exit_range (irange &r, tree name, basic_block bb)
   if (def_bb == bb)
     range_of_def (r, name, bb);
   else
-    entry_range (r, name, bb);
- }
+    entry_range (r, name, bb, mode);
+}
+
+// Get the range of NAME on edge E using MODE, return the result in R.
+// Always returns a range and true.
+
+bool
+ranger_cache::edge_range (irange &r, edge e, tree name, enum rfd_mode mode)
+{
+  exit_range (r, name, e->src, mode);
+  // If this is not an abnormal edge, check for a non-null exit.
+  if ((e->flags & (EDGE_EH | EDGE_ABNORMAL)) == 0)
+    m_non_null.adjust_range (r, name, e->src, false);
+  int_range_max er;
+  if (m_gori.outgoing_edge_range_p (er, e, name, *this))
+    r.intersect (er);
+  return true;
+}
+
 
 
 // Implement range_of_expr.
@@ -1063,32 +1086,22 @@  ranger_cache::range_of_expr (irange &r, tree name, gimple *stmt)
   if (bb == def_bb)
     range_of_def (r, name, bb);
   else
-    entry_range (r, name, bb);
+    entry_range (r, name, bb, RFD_NONE);
   return true;
 }
 
 
-// Implement range_on_edge.  Always return the best available range.
-
- bool
- ranger_cache::range_on_edge (irange &r, edge e, tree expr)
- {
-   if (gimple_range_ssa_p (expr))
-    {
-      exit_range (r, expr, e->src);
-      // If this is not an abnormal edge, check for a non-null exit.
-      if ((e->flags & (EDGE_EH | EDGE_ABNORMAL)) == 0)
-	m_non_null.adjust_range (r, expr, e->src, false);
-      int_range_max edge_range;
-      if (m_gori.outgoing_edge_range_p (edge_range, e, expr, *this))
-	r.intersect (edge_range);
-      return true;
-    }
+// Implement range_on_edge.  Always return the best available range using
+// the current cache values.
 
+bool
+ranger_cache::range_on_edge (irange &r, edge e, tree expr)
+{
+  if (gimple_range_ssa_p (expr))
+    return edge_range (r, e, expr, RFD_NONE);
   return get_tree_range (r, expr, NULL);
 }
 
-
 // Return a static range for NAME on entry to basic block BB in R.  If
 // calc is true, fill any cache entries required between BB and the
 // def block for NAME.  Otherwise, return false if the cache is empty.
@@ -1281,20 +1294,12 @@  ranger_cache::fill_block_cache (tree name, basic_block bb, basic_block def_bb)
   // At this point we shouldn't be looking at the def, entry or exit block.
   gcc_checking_assert (bb != def_bb && bb != ENTRY_BLOCK_PTR_FOR_FN (cfun) &&
 		       bb != EXIT_BLOCK_PTR_FOR_FN (cfun));
+  gcc_checking_assert (m_workback.length () == 0);
 
   // If the block cache is set, then we've already visited this block.
   if (m_on_entry.bb_range_p (name, bb))
     return;
 
-  // Visit each block back to the DEF.  Initialize each one to UNDEFINED.
-  // m_visited at the end will contain all the blocks that we needed to set
-  // the range_on_entry cache for.
-  m_workback.truncate (0);
-  m_workback.quick_push (bb);
-  undefined.set_undefined ();
-  m_on_entry.set_bb_range (name, bb, undefined);
-  gcc_checking_assert (m_update->empty_p ());
-
   if (DEBUG_RANGE_CACHE)
     {
       fprintf (dump_file, "\n");
@@ -1302,9 +1307,8 @@  ranger_cache::fill_block_cache (tree name, basic_block bb, basic_block def_bb)
       fprintf (dump_file, " : ");
     }
 
-  // If there are dominators, check if a dominators can supply the range.
-  if (dom_info_available_p (CDI_DOMINATORS)
-      && range_from_dom (block_result, name, bb))
+  // Check if a dominators can supply the range.
+  if (range_from_dom (block_result, name, bb, RFD_FILL))
     {
       m_on_entry.set_bb_range (name, bb, block_result);
       if (DEBUG_RANGE_CACHE)
@@ -1313,9 +1317,18 @@  ranger_cache::fill_block_cache (tree name, basic_block bb, basic_block def_bb)
 	  block_result.dump (dump_file);
 	  fprintf (dump_file, "\n");
 	}
+      gcc_checking_assert (m_workback.length () == 0);
       return;
     }
 
+  // Visit each block back to the DEF.  Initialize each one to UNDEFINED.
+  // m_visited at the end will contain all the blocks that we needed to set
+  // the range_on_entry cache for.
+  m_workback.quick_push (bb);
+  undefined.set_undefined ();
+  m_on_entry.set_bb_range (name, bb, undefined);
+  gcc_checking_assert (m_update->empty_p ());
+
   while (m_workback.length () > 0)
     {
       basic_block node = m_workback.pop ();
@@ -1399,12 +1412,14 @@  ranger_cache::fill_block_cache (tree name, basic_block bb, basic_block def_bb)
 }
 
 
-// Get the range of NAME from dominators of BB and return it in R.
+// Get the range of NAME from dominators of BB and return it in R.  Search the
+// dominator tree based on MODE.
 
 bool
-ranger_cache::range_from_dom (irange &r, tree name, basic_block start_bb)
+ranger_cache::range_from_dom (irange &r, tree name, basic_block start_bb,
+			      enum rfd_mode mode)
 {
-  if (!dom_info_available_p (CDI_DOMINATORS))
+  if (mode == RFD_NONE || !dom_info_available_p (CDI_DOMINATORS))
     return false;
 
   // Search back to the definition block or entry block.
@@ -1419,7 +1434,7 @@  ranger_cache::range_from_dom (irange &r, tree name, basic_block start_bb)
 
   // Range on entry to the DEF block should not be queried.
   gcc_checking_assert (start_bb != def_bb);
-  m_workback.truncate (0);
+  unsigned start_limit = m_workback.length ();
 
   // Default value is global range.
   get_global_range (r, name);
@@ -1436,10 +1451,36 @@  ranger_cache::range_from_dom (irange &r, tree name, basic_block start_bb)
       if (m_gori.has_edge_range_p (name, bb))
 	{
 	  // Only outgoing ranges to single_pred blocks are dominated by
-	  // outgoing edge ranges, so only those need to be considered.
+	  // outgoing edge ranges, so those can be simply adjusted on the fly.
 	  edge e = find_edge (bb, prev_bb);
 	  if (e && single_pred_p (prev_bb))
 	    m_workback.quick_push (prev_bb);
+	  else if (mode == RFD_FILL)
+	    {
+	      // Multiple incoming edges, so recursively satisfy this block,
+	      // store the range, then calculate the incoming range for PREV_BB.
+	      if (def_bb != bb)
+		{
+		  range_from_dom (r, name, bb, RFD_FILL);
+		  // If the range can't be store, don't try to accumulate
+		  // the range in PREV_BB due to excessive recalculations.
+		  if (!m_on_entry.set_bb_range (name, bb, r))
+		    break;
+		}
+	      // With the dominator set, we should be able to cheaply query
+	      // each incoming edge now and accumulate the results.
+	      r.set_undefined ();
+	      edge_iterator ei;
+	      int_range_max er;
+	      FOR_EACH_EDGE (e, ei, prev_bb->preds)
+		{
+		  edge_range (er, e, name, RFD_READ_ONLY);
+		  r.union_ (er);
+		}
+	      // Set the cache in PREV_BB so it is not calculated again.
+	      m_on_entry.set_bb_range (name, prev_bb, r);
+	      break;
+	    }
 	}
 
       if (def_bb == bb)
@@ -1460,16 +1501,16 @@  ranger_cache::range_from_dom (irange &r, tree name, basic_block start_bb)
     }
 
   // Now process any outgoing edges that we seen along the way.
-  while (m_workback.length () > 0)
+  while (m_workback.length () > start_limit)
     {
-      int_range_max edge_range;
+      int_range_max er;
       prev_bb = m_workback.pop ();
       edge e = single_pred_edge (prev_bb);
       bb = e->src;
 
-      if (m_gori.outgoing_edge_range_p (edge_range, e, name, *this))
+      if (m_gori.outgoing_edge_range_p (er, e, name, *this))
 	{
-	  r.intersect (edge_range);
+	  r.intersect (er);
 	  if (r.varying_p () && ((e->flags & (EDGE_EH | EDGE_ABNORMAL)) == 0))
 	    {
 	      if (m_non_null.non_null_deref_p (name, bb, false))
@@ -1518,7 +1559,7 @@  ranger_cache::update_to_nonnull (basic_block bb, tree name)
       // Update the on-entry cache for BB to be non-zero.  Note this can set
       // the on entry value in the DEF block, which can override the def.
       int_range_max r;
-      exit_range (r, name, bb);
+      exit_range (r, name, bb, RFD_READ_ONLY);
       if (r.varying_p ())
 	{
 	  r.set_nonzero (type);
diff --git a/gcc/gimple-range-cache.h b/gcc/gimple-range-cache.h
index a0244e4f6a4..560403b534e 100644
--- a/gcc/gimple-range-cache.h
+++ b/gcc/gimple-range-cache.h
@@ -129,7 +129,6 @@  public:
   virtual bool range_of_expr (irange &r, tree name, gimple *stmt);
   virtual bool range_on_edge (irange &r, edge e, tree expr);
   bool block_range (irange &r, basic_block bb, tree name, bool calc = true);
-  bool range_from_dom (irange &r, tree name, basic_block bb);
 
   bool get_global_range (irange &r, tree name) const;
   bool get_global_range (irange &r, tree name, bool &current_p);
@@ -151,9 +150,17 @@  private:
   void fill_block_cache (tree name, basic_block bb, basic_block def_bb);
   void propagate_cache (tree name);
 
+  enum rfd_mode
+    {
+      RFD_NONE,		// Only look at current block cache.
+      RFD_READ_ONLY,	// Scan DOM tree, do not write to cache.
+      RFD_FILL		// Scan DOM tree, updating important nodes.
+    };
+  bool range_from_dom (irange &r, tree name, basic_block bb, enum rfd_mode);
   void range_of_def (irange &r, tree name, basic_block bb = NULL);
-  void entry_range (irange &r, tree expr, basic_block bb);
-  void exit_range (irange &r, tree expr, basic_block bb);
+  void entry_range (irange &r, tree expr, basic_block bb, enum rfd_mode);
+  void exit_range (irange &r, tree expr, basic_block bb, enum rfd_mode);
+  bool edge_range (irange &r, edge e, tree name, enum rfd_mode);
 
   vec<basic_block> m_workback;
   class update_list *m_update;