[COMMITTED] PR tree-optimization/106514 - Loop over intersected bitmaps.

[COMMITTED] PR tree-optimization/106514 - Loop over intersected bitmaps.

[Andrew MacLeod]

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

compute_ranges_in_block loops over all the imports, and checks to see if 
each one is exported, then calculated an outgoing range for those that are.

The outer loop loops over the import list, whereas the export list is 
usually smaller, and empty half the time.  This means we were doing a 
lot of busy work looping over the imports for no reason.

The export list was extracted on each iteration of the loop, and because 
its a self sizing thing with a call, It doesn't get hauled out of the 
loop.  More extra work.

This patch changes the loop to use EXECUTE_IF_AND_IN_BITMAP to only look 
at the intersection of imports and exports, ths only doing the work it 
needs to do.

With a performance build, running with --param 
max-jump-thread-duplication-stmts=50 for good measure:

before patch:

backwards jump threading           :   5.91 ( 90%)   0.01 ( 20%)   5.93 
( 89%)    72  (  0%)
TOTAL                           :   6.58          0.05 6.66           47M

after patch:

backwards jump threading           :   4.67 ( 88%)   0.01 ( 14%)   4.67 
( 86%)    72  (  0%)
TOTAL                           :   5.31          0.07 5.42           47M

bootstrapped on 86_64-pc-linux-gnu  with no regressions, and no change 
in the thread count.  pushed.

Andrew

[-- Attachment #2: forand.diff --]
[-- Type: text/x-patch, Size: 2351 bytes --]

commit 8e34d92ef29a175b84cc7f5185db43656ae762bb
Author: Andrew MacLeod <amacleod@redhat.com>
Date:   Thu Aug 4 12:22:59 2022 -0400

    Loop over intersected bitmaps.
    
    compute_ranges_in_block loops over the import list and then checks the
    same bit in exports.  It is nmore efficent to loop over the intersection
    of the 2 bitmaps.
    
            PR tree-optimization/106514
            * gimple-range-path.cc (path_range_query::compute_ranges_in_block):
            Use EXECUTE_IF_AND_IN_BITMAP to loop over 2 bitmaps.

diff --git a/gcc/gimple-range-path.cc b/gcc/gimple-range-path.cc
index e1b9683c1e4..43e7526b6fc 100644
--- a/gcc/gimple-range-path.cc
+++ b/gcc/gimple-range-path.cc
@@ -479,32 +479,28 @@ path_range_query::compute_ranges_in_block (basic_block bb)
       p->set_root_oracle (nullptr);
     }
 
-  EXECUTE_IF_SET_IN_BITMAP (m_imports, 0, i, bi)
+  gori_compute &g = m_ranger->gori ();
+  bitmap exports = g.exports (bb);
+  EXECUTE_IF_AND_IN_BITMAP (m_imports, exports, 0, i, bi)
     {
       tree name = ssa_name (i);
-      gori_compute &g = m_ranger->gori ();
-      bitmap exports = g.exports (bb);
-
-      if (bitmap_bit_p (exports, i))
+      Value_Range r (TREE_TYPE (name));
+      if (g.outgoing_edge_range_p (r, e, name, *this))
 	{
-	  Value_Range r (TREE_TYPE (name));
-	  if (g.outgoing_edge_range_p (r, e, name, *this))
+	  Value_Range cached_range (TREE_TYPE (name));
+	  if (get_cache (cached_range, name))
+	    r.intersect (cached_range);
+
+	  set_cache (r, name);
+	  if (DEBUG_SOLVER)
 	    {
-	      Value_Range cached_range (TREE_TYPE (name));
-	      if (get_cache (cached_range, name))
-		r.intersect (cached_range);
-
-	      set_cache (r, name);
-	      if (DEBUG_SOLVER)
-		{
-		  fprintf (dump_file, "outgoing_edge_range_p for ");
-		  print_generic_expr (dump_file, name, TDF_SLIM);
-		  fprintf (dump_file, " on edge %d->%d ",
-			   e->src->index, e->dest->index);
-		  fprintf (dump_file, "is ");
-		  r.dump (dump_file);
-		  fprintf (dump_file, "\n");
-		}
+	      fprintf (dump_file, "outgoing_edge_range_p for ");
+	      print_generic_expr (dump_file, name, TDF_SLIM);
+	      fprintf (dump_file, " on edge %d->%d ",
+		       e->src->index, e->dest->index);
+	      fprintf (dump_file, "is ");
+	      r.dump (dump_file);
+	      fprintf (dump_file, "\n");
 	    }
 	}
     }