[COMMITTED] Move import population from threader to path solver.

Aldy Hernandez aldyh@redhat.com
Thu Nov 11 14:41:18 GMT 2021


Imports are our nomenclature for external SSA names to a block that
are used to calculate the outgoing edges for said block.  For example,
in the following snippet:

    <bb 2> :
    _1 = b_10 == block_11;
    _2 = b_10 != -1;
    _3 = _1 & _2;
    if (_3 != 0)
      goto <bb 3>; [INV]
    else
      goto <bb 5>; [INV]

...the imports to the block are b_10 and block_11 since they are both
needed to calculate _3.

The path solver takes a bitmap of imports in addition to the path
itself.  This sets up the number of SSA names to be on the lookout
for, while resolving the final conditional.

Calculating these imports was initially done in the threader, since it
was the only user of the path solver.  With new clients, it has become
obvious that populating the imports should be a task for the path
solver, so it can be shared among the clients.

This patch moves the import code to the solver, making both the solver
and the threader simpler in the process.  This is because intent is
clearer and some duplicate code was removed.

This reshuffling had the net effect of giving us a handful of new
threads through my suite of .ii files (125).  This was unexpected, but
welcome nevertheless.  There is no performance difference in callgrind
over the same suite.

Regstrapped on x86-64 Linux.

gcc/ChangeLog:

	* gimple-range-path.cc (path_range_query::add_copies_to_imports):
	Rename to...
	(path_range_query::compute_imports): ...this.  Adapt it so it can
	be passed the imports bitmap instead of working on m_imports.
	(path_range_query::compute_ranges): Call compute_imports in all
	cases unless an imports bitmap is passed.
	* gimple-range-path.h (path_range_query::compute_imports): New.
	(path_range_query::add_copies_to_imports): Remove.
	* tree-ssa-threadbackward.c (back_threader::resolve_def): Remove.
	(back_threader::find_paths_to_names): Inline resolve_def.
	(back_threader::find_paths): Call compute_imports.
	(back_threader::resolve_phi): Adjust comment.
---
 gcc/gimple-range-path.cc      | 45 ++++++++++++++++-----------------
 gcc/gimple-range-path.h       |  2 +-
 gcc/tree-ssa-threadbackward.c | 47 ++++++-----------------------------
 3 files changed, 30 insertions(+), 64 deletions(-)

diff --git a/gcc/gimple-range-path.cc b/gcc/gimple-range-path.cc
index 6da01c7067f..4843c133e62 100644
--- a/gcc/gimple-range-path.cc
+++ b/gcc/gimple-range-path.cc
@@ -439,26 +439,32 @@ path_range_query::add_to_imports (tree name, bitmap imports)
   return false;
 }
 
-// Add the copies of any SSA names in IMPORTS to IMPORTS.
+// Compute the imports to the path ending in EXIT.  These are
+// essentially the SSA names used to calculate the final conditional
+// along the path.
 //
-// These are hints for the solver.  Adding more elements (within
-// reason) doesn't slow us down, because we don't solve anything that
-// doesn't appear in the path.  On the other hand, not having enough
-// imports will limit what we can solve.
+// They are hints for the solver.  Adding more elements doesn't slow
+// us down, because we don't solve anything that doesn't appear in the
+// path.  On the other hand, not having enough imports will limit what
+// we can solve.
 
 void
-path_range_query::add_copies_to_imports ()
+path_range_query::compute_imports (bitmap imports, basic_block exit)
 {
-  auto_vec<tree> worklist (bitmap_count_bits (m_imports));
+  // Start with the imports from the exit block...
+  bitmap r_imports = m_ranger.gori ().imports (exit);
+  bitmap_copy (imports, r_imports);
+
+  auto_vec<tree> worklist (bitmap_count_bits (imports));
   bitmap_iterator bi;
   unsigned i;
-
-  EXECUTE_IF_SET_IN_BITMAP (m_imports, 0, i, bi)
+  EXECUTE_IF_SET_IN_BITMAP (imports, 0, i, bi)
     {
       tree name = ssa_name (i);
       worklist.quick_push (name);
     }
 
+  // ...and add any operands used to define these imports.
   while (!worklist.is_empty ())
     {
       tree name = worklist.pop ();
@@ -466,15 +472,12 @@ path_range_query::add_copies_to_imports ()
 
       if (is_gimple_assign (def_stmt))
 	{
-	  // ?? Adding assignment copies doesn't get us much.  At the
-	  // time of writing, we got 63 more threaded paths across the
-	  // .ii files from a bootstrap.
-	  add_to_imports (gimple_assign_rhs1 (def_stmt), m_imports);
+	  add_to_imports (gimple_assign_rhs1 (def_stmt), imports);
 	  tree rhs = gimple_assign_rhs2 (def_stmt);
-	  if (rhs && add_to_imports (rhs, m_imports))
+	  if (rhs && add_to_imports (rhs, imports))
 	    worklist.safe_push (rhs);
 	  rhs = gimple_assign_rhs3 (def_stmt);
-	  if (rhs && add_to_imports (rhs, m_imports))
+	  if (rhs && add_to_imports (rhs, imports))
 	    worklist.safe_push (rhs);
 	}
       else if (gphi *phi = dyn_cast <gphi *> (def_stmt))
@@ -486,7 +489,7 @@ path_range_query::add_copies_to_imports ()
 
 	      if (TREE_CODE (arg) == SSA_NAME
 		  && m_path.contains (e->src)
-		  && bitmap_set_bit (m_imports, SSA_NAME_VERSION (arg)))
+		  && bitmap_set_bit (imports, SSA_NAME_VERSION (arg)))
 		worklist.safe_push (arg);
 	    }
 	}
@@ -512,16 +515,10 @@ path_range_query::compute_ranges (const vec<basic_block> &path,
   if (imports)
     bitmap_copy (m_imports, imports);
   else
-    {
-      bitmap imports = m_ranger.gori ().imports (exit_bb ());
-      bitmap_copy (m_imports, imports);
-    }
+    compute_imports (m_imports, exit_bb ());
 
   if (m_resolve)
-    {
-      add_copies_to_imports ();
-      get_path_oracle ()->reset_path ();
-    }
+    get_path_oracle ()->reset_path ();
 
   if (DEBUG_SOLVER)
     {
diff --git a/gcc/gimple-range-path.h b/gcc/gimple-range-path.h
index b73549f01a5..b5a054359ad 100644
--- a/gcc/gimple-range-path.h
+++ b/gcc/gimple-range-path.h
@@ -36,6 +36,7 @@ public:
   virtual ~path_range_query ();
   void compute_ranges (const vec<basic_block> &, const bitmap_head *imports = NULL);
   void compute_ranges (edge e);
+  void compute_imports (bitmap imports, basic_block exit);
   bool range_of_expr (irange &r, tree name, gimple * = NULL) override;
   bool range_of_stmt (irange &r, gimple *, tree name = NULL) override;
   bool unreachable_path_p ();
@@ -61,7 +62,6 @@ private:
   void compute_outgoing_relations (basic_block bb, basic_block next);
   void compute_phi_relations (basic_block bb, basic_block prev);
   void maybe_register_phi_relation (gphi *, tree arg);
-  void add_copies_to_imports ();
   bool add_to_imports (tree name, bitmap imports);
   inline bool import_p (tree name);
 
diff --git a/gcc/tree-ssa-threadbackward.c b/gcc/tree-ssa-threadbackward.c
index 0f7b4a732eb..d067c470c38 100644
--- a/gcc/tree-ssa-threadbackward.c
+++ b/gcc/tree-ssa-threadbackward.c
@@ -91,7 +91,6 @@ private:
   edge maybe_register_path ();
   void maybe_register_path_dump (edge taken_edge);
   void find_paths_to_names (basic_block bb, bitmap imports);
-  bool resolve_def (tree name, bitmap interesting, vec<tree> &worklist);
   void resolve_phi (gphi *phi, bitmap imports);
   edge find_taken_edge (const vec<basic_block> &path);
   edge find_taken_edge_cond (const vec<basic_block> &path, gcond *);
@@ -363,12 +362,8 @@ back_threader::resolve_phi (gphi *phi, bitmap interesting)
       edge e = gimple_phi_arg_edge (phi, i);
 
       // This is like path_crosses_loops in profitable_path_p but more
-      // restrictive, since profitable_path_p allows threading the
-      // first block because it would be redirected anyhow.
-      //
-      // If we loosened the restriction and used profitable_path_p()
-      // here instead, we would peel off the first iterations of loops
-      // in places like tree-ssa/pr14341.c.
+      // restrictive to avoid peeling off loop iterations (see
+      // tree-ssa/pr14341.c for an example).
       bool profitable_p = m_path[0]->loop_father == e->src->loop_father;
       if (!profitable_p)
 	{
@@ -404,33 +399,6 @@ back_threader::resolve_phi (gphi *phi, bitmap interesting)
     }
 }
 
-// If the definition of NAME causes the final conditional of the
-// current path to be constant, register the path, and return TRUE.
-
-bool
-back_threader::resolve_def (tree name, bitmap interesting, vec<tree> &worklist)
-{
-  gimple *def_stmt = SSA_NAME_DEF_STMT (name);
-
-  // Handle PHIs.
-  if (is_a<gphi *> (def_stmt))
-    {
-      resolve_phi (as_a<gphi *> (def_stmt), interesting);
-      return true;
-    }
-
-  // Defer copies of SSAs by adding the source to the worklist.
-  if (gimple_assign_single_p (def_stmt)
-      && TREE_CODE (gimple_assign_rhs1 (def_stmt)) == SSA_NAME)
-    {
-      tree rhs = gimple_assign_rhs1 (def_stmt);
-      bitmap_set_bit (m_imports, SSA_NAME_VERSION (rhs));
-      bitmap_set_bit (interesting, SSA_NAME_VERSION (rhs));
-      worklist.safe_push (rhs);
-    }
-  return false;
-}
-
 // Find jump threading paths to any of the SSA names in the
 // INTERESTING bitmap, and register any such paths.
 //
@@ -464,13 +432,15 @@ back_threader::find_paths_to_names (basic_block bb, bitmap interesting)
     {
       tree name = worklist.pop ();
       unsigned i = SSA_NAME_VERSION (name);
-      basic_block def_bb = gimple_bb (SSA_NAME_DEF_STMT (name));
+      gimple *def_stmt = SSA_NAME_DEF_STMT (name);
+      basic_block def_bb = gimple_bb (def_stmt);
 
-      // Process any names defined in this block.
+      // Process any PHIs defined in this block.
       if (def_bb == bb
 	  && bitmap_set_bit (processed, i)
-	  && resolve_def (name, interesting, worklist))
+	  && gimple_code (def_stmt) == GIMPLE_PHI)
 	{
+	  resolve_phi (as_a<gphi *> (def_stmt), interesting);
 	  done = true;
 	  break;
 	}
@@ -515,10 +485,9 @@ back_threader::find_paths (basic_block bb, tree name)
       m_visited_bbs.empty ();
       m_path.truncate (0);
       m_name = name;
-      bitmap_clear (m_imports);
+      m_solver->compute_imports (m_imports, bb);
 
       auto_bitmap interesting;
-      bitmap_copy (m_imports, m_ranger->gori ().imports (bb));
       bitmap_copy (interesting, m_imports);
       find_paths_to_names (bb, interesting);
     }
-- 
2.31.1



More information about the Gcc-patches mailing list