[gcc r12-3762] path solver: Add related SSAs to solvable set.

[gcc r12-3762] path solver: Add related SSAs to solvable set.

[Aldy Hernandez]

https://gcc.gnu.org/g:e4249b10038bd906f50c00759b37807dd2fffede

commit r12-3762-ge4249b10038bd906f50c00759b37807dd2fffede
Author: Aldy Hernandez <aldyh@redhat.com>
Date:   Tue Sep 21 09:21:55 2021 +0200

    path solver: Add related SSAs to solvable set.
    
    The path solver takes an initial set of SSA names which are deemed
    interesting.  These are then solved along the path.  Adding any copies
    of said SSA names to the list of interesting names yields significantly
    better results.  This patch adds said copies to the already provided
    list.
    
    Currently this code is guarded by "m_resolve", which is the more
    expensive mode, but it would be reasonable to make it available always,
    especially since adding more imports usually has minimal impact on the
    processing time.  I will investigate and make it universally available
    if this is indeed the case.
    
    gcc/ChangeLog:
    
            * gimple-range-path.cc (path_range_query::add_to_imports): New.
            (path_range_query::add_copies_to_imports): New.
            (path_range_query::precompute_ranges): Call
            add_copies_to_imports.
            * gimple-range-path.h (class path_range_query): Add prototypes
            for add_copies_to_imports and add_to_imports.

Diff:
---
 gcc/gimple-range-path.cc | 80 +++++++++++++++++++++++++++++++++++++++++++++++-
 gcc/gimple-range-path.h  |  4 ++-
 2 files changed, 82 insertions(+), 2 deletions(-)

diff --git a/gcc/gimple-range-path.cc b/gcc/gimple-range-path.cc
index b86a76fa74b..a8ead3da4dc 100644
--- a/gcc/gimple-range-path.cc
+++ b/gcc/gimple-range-path.cc
@@ -343,6 +343,71 @@ path_range_query::adjust_for_non_null_uses (basic_block bb)
     }
 }
 
+// If NAME is a supported SSA_NAME, add it the bitmap in IMPORTS.
+
+bool
+path_range_query::add_to_imports (tree name, bitmap imports)
+{
+  if (TREE_CODE (name) == SSA_NAME
+      && irange::supports_type_p (TREE_TYPE (name)))
+    return bitmap_set_bit (imports, SSA_NAME_VERSION (name));
+  return false;
+}
+
+// Add the copies of any SSA names in IMPORTS to IMPORTS.
+//
+// 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.
+
+void
+path_range_query::add_copies_to_imports ()
+{
+  auto_vec<tree> worklist (bitmap_count_bits (m_imports));
+  bitmap_iterator bi;
+  unsigned i;
+
+  EXECUTE_IF_SET_IN_BITMAP (m_imports, 0, i, bi)
+    {
+      tree name = ssa_name (i);
+      worklist.quick_push (name);
+    }
+
+  while (!worklist.is_empty ())
+    {
+      tree name = worklist.pop ();
+      gimple *def_stmt = SSA_NAME_DEF_STMT (name);
+
+      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);
+	  tree rhs = gimple_assign_rhs2 (def_stmt);
+	  if (rhs && add_to_imports (rhs, m_imports))
+	    worklist.safe_push (rhs);
+	  rhs = gimple_assign_rhs3 (def_stmt);
+	  if (rhs && add_to_imports (rhs, m_imports))
+	    worklist.safe_push (rhs);
+	}
+      else if (gphi *phi = dyn_cast <gphi *> (def_stmt))
+	{
+	  for (size_t i = 0; i < gimple_phi_num_args (phi); ++i)
+	    {
+	      edge e = gimple_phi_arg_edge (phi, i);
+	      tree arg = gimple_phi_arg (phi, i)->def;
+
+	      if (TREE_CODE (arg) == SSA_NAME
+		  && m_path->contains (e->src)
+		  && bitmap_set_bit (m_imports, SSA_NAME_VERSION (arg)))
+		worklist.safe_push (arg);
+	    }
+	}
+    }
+}
+
 // Precompute the ranges for IMPORTS along PATH.
 //
 // IMPORTS are the set of SSA names, any of which could potentially
@@ -353,11 +418,12 @@ path_range_query::precompute_ranges (const vec<basic_block> &path,
 				     const bitmap_head *imports)
 {
   set_path (path);
-  m_imports = imports;
+  bitmap_copy (m_imports, imports);
   m_undefined_path = false;
 
   if (m_resolve)
     {
+      add_copies_to_imports ();
       m_oracle->reset_path ();
       precompute_relations (path);
     }
@@ -379,6 +445,18 @@ path_range_query::precompute_ranges (const vec<basic_block> &path,
     {
       basic_block bb = curr_bb ();
 
+      if (m_resolve)
+	{
+	  gori_compute &gori = m_ranger.gori ();
+	  tree name;
+
+	  // Exported booleans along the path, may help conditionals.
+	  // Add them as interesting imports.
+	  FOR_EACH_GORI_EXPORT_NAME (gori, bb, name)
+	    if (TREE_CODE (TREE_TYPE (name)) == BOOLEAN_TYPE)
+	      bitmap_set_bit (m_imports, SSA_NAME_VERSION (name));
+	}
+
       precompute_ranges_in_block (bb);
       adjust_for_non_null_uses (bb);
 
diff --git a/gcc/gimple-range-path.h b/gcc/gimple-range-path.h
index d12fd7743ca..f23cce18391 100644
--- a/gcc/gimple-range-path.h
+++ b/gcc/gimple-range-path.h
@@ -61,6 +61,8 @@ private:
   void ssa_range_in_phi (irange &r, gphi *phi);
   void precompute_relations (const vec<basic_block> &);
   void precompute_phi_relations (basic_block bb, basic_block prev);
+  void add_copies_to_imports ();
+  bool add_to_imports (tree name, bitmap imports);
 
   // Path navigation.
   void set_path (const vec<basic_block> &);
@@ -82,7 +84,7 @@ private:
   // Path being analyzed.
   const vec<basic_block> *m_path;
 
-  const bitmap_head *m_imports;
+  auto_bitmap m_imports;
   gimple_ranger &m_ranger;
   non_null_ref m_non_null;
   path_oracle *m_oracle;