Re: [PATCH] Tame path_range_query::compute_imports

[Aldy Hernandez <aldyh@redhat.com>]

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

On Mon, Aug 15, 2022 at 11:53 AM Richard Biener <rguenther@suse.de> wrote:
>
> On Thu, 11 Aug 2022, Aldy Hernandez wrote:
>
> > On Thu, Aug 11, 2022 at 3:59 PM Andrew MacLeod <amacleod@redhat.com> wrote:
> > >
> > >
> > > On 8/11/22 07:42, Richard Biener wrote:
> > > > This avoids going BBs outside of the path when adding def chains
> > > > to the set of imports.  It also syncs the code with
> > > > range_def_chain::get_def_chain to not miss out on some imports
> > > > this function would identify.
> > > >
> > > > Bootstrap / regtest pending on x86_64-unknown-linux-gnu.
> > > >
> > > > The question still stands on what the path_range_query::compute_ranges
> > > > actually needs in its m_imports - at least I don't easily see how
> > > > the range-folds will use the path range cache or be path sensitive
> > > > at all.
> > >
> > > All the range folding code is in gimple_range_fold.{h,cc}, and its
> > > driven by the mystical FUR_source classes.  fur_source stands for
> > > Fold_Using_Range source, and its basically just an API class which all
> > > the folding routines use to make queries. it is used by all the fold
> > > routines to ask any questions about valueizing relations,  ssa name,
> > > etc..   but abstracts the actual source of the information. Its the
> > > distillation from previous incarnations where I use to pass an edge, a
> > > stmt and other stuff to each routine that it might need, and decided to
> > > abstract since it was very unwieldy.  The base class requires only a
> > > range_query which is then used for all queries.
> >
> > Note that not only is ranger and path_query a range_query, so is
> > vr_values from legacy land.  It all shares the same API.  And the
> > simplify_using_ranges class takes a range_query, so it can work with
> > legacy or ranger, or even (untested) the path_query class.
> >
> > >
> > > Then I derive fur_stmt which is instantiated additionally with the stmt
> > > you wish to fold at, and it will perform queries using that stmt as the
> > > context source..   Any requests for ranges/relations/etc will occur as
> > > if that stmt location is the source.  If folding a particular stmt, you
> > > use that stmt as the fur_stmt source.  This is also how I do
> > > recalculations..  when we see
> > > bb4:
> > >    a_32 = f_16 + 10
> > > <...>
> > > bb88:
> > >    if (f_16 < 20)
> > >       b_8 = a_32 + 8
> > > and there is sufficient reason to think that a_32 would have a different
> > > value , we can invoke a re-fold of a_32's defintion stmt at the use
> > > point in b_8..  using that stmt as the fur_source. Ranger will take into
> > > account the range of f_16 being [0,19] at that spot, and recalculate
> > > a_32 as [10,29].  Its expensive to do this at every use point, so we
> > > only do it if we think there is a good reason at this point.
> > >
> > > The point is that the fur_source mechanism is how we provide a context,
> > > and that class talkes care of the details of what the source actually is.
> > >
> > > There are other fur_sources.. fur_edge allows all the same questions to
> > > be answered, but using an edge as the source. Meaning we can calculate
> > > an arbitrary stmt/expressions as if it occurs on an edge.
> > >
> > > There are also a couple of specialized fur_sources.. there is an
> > > internal one in ranger which communicates some other information called
> > > fur_depend which acts like range_of_stmt, but with additional
> > > functionality to register dependencies in GORI as they are seen.
> >
> > This is a really good explanation.  I think you should save it and
> > included it in the documentation when you/we get around to writing it
> > ;-).
> >
> > >
> > > Aldy overloads the fur_depend class (called jt_fur_source--  Im not sure
> > > the origination of the name) to work with the values in the path_query
> > > class.   You will note that the path_range_query class inherits from a
> > > range_query, so it supports all the range_of_expr, range_of_stmt, and
> > > range_on_edge aspect of rangers API.
> >
> > The name comes from "jump thread" fur_source.  I should probably
> > rename that to path_fur_source.  Note that even though the full
> > range_query API is available in path_range_query, only range_of_expr
> > and range_of_stmt are supported (or tested).  As I mention in the
> > comment for the class:
> >
> > // This class is a basic block path solver.  Given a set of BBs
> > // indicating a path through the CFG, range_of_expr and range_of_stmt
> > // will calculate the range of an SSA or STMT as if the BBs in the
> > // path would have been executed in order.
> >
> > So using range_on_edge would probably give unexpected results, using
> > stuff in the cache as it would appear at the end of the path, or some
> > such.  We could definitely harden this class and make it work solidly
> > across the entire API, but we've had no uses so far for anything but
> > range_of_expr and range_of_stmt-- and even those are only supported
> > for a range as it would appear at the end of the path.  So if you call
> > range_of_expr with a statement anywhere but the end of the path,
> > you're asking for trouble.
> >
> > >
> > > I believe all attempts are first made to pick up the value from the path
> > > cache, and failing that, a query is made from ranger at the start of the
> > > path.  So as the walk thru the path happens, and edges are taken/chosen,
> > > all the context information local to the path should be placed into the
> > > path cache, and used in any future queries using the path_range_query.
> > > Ranger will only be invoked if there is no entry in the path query, and
> > > it would provide the range as it would appear at entry to the path.
> > >
> > > Thats my high level understanding of how the path_query class provides
> > > context.
> >
> > That's actually a really good explanation of how it all works (or at
> > least how it's supposed to work ;-)).  Thanks.
>
> Yes, thanks - that was helpful (and the general back threader stuff
> confirms what I reverse engineered).
>
> > >
> > > So I think to answer the other question, the m_imports list Is probably
> > > the list of ssa-names that may have relevant context information which
> > > the path_query would provide ranges during the walk instead of ranger?
> > > I think Aldy pre-calculates all those during the walk, and then uses
> > > this pre-filled cache to answer questions at the thread exit?   Thats my
> > > guess
> >
> > Yeah, though I should probably sit down and do some testing, making
> > sure we're not adding more imports than we need to.  Richi has found a
> > whole bunch of imports that ended up in the list that were ultimately
> > not needed.  My original comment that adding more imports to the
> > bitmap had no penalty should be nuked-- it obviously has a performance
> > effect, especially for pathological cases.
> >
> > Regarding the name "imports".  I think it's confusing all of us,
> > because GORI has a very clear definition of what imports are.  OTOH,
> > the path solver starts with the imports from GORI land, but ends up
> > adding more SSA names that would be useful to solve, to provide
> > context as Andrew says.  Maybe, we should call the "imports" in the
> > path solver something else to avoid confusion.  Interesting names?
> > Must-be-solved?  Context-SSA?  Suggestions?
>
> I understand them to be path exit dependences, the 'interesting names'
> thing is already used.  So maybe
> s/compute_imports/compute_exit_dependences/, this name clash did
> confuse me a bit.  Though we do stop at the path entry and have
> the "path imports" in the list of dependences as well (but not
> the dependences of those imports).

Yeah, I much prefer the exit dependencies name as it avoids confusion
and makes things clearer.

This is what I have in mind.  Do you agree?  Is it clearer now?

Aldy

[-- Attachment #2: 0001-Rename-imports-nomenclature-in-path_range_query-to-e.patch --]
[-- Type: text/x-patch, Size: 11247 bytes --]

From 48e97240a5255ffd72dca8d2c23937029aff882b Mon Sep 17 00:00:00 2001
From: Aldy Hernandez <aldyh@redhat.com>
Date: Tue, 16 Aug 2022 10:52:37 +0200
Subject: [PATCH] Rename imports nomenclature in path_range_query to
 exit_dependencies.

The purpose of this change is to disambiguate the imports name with
its use in GORI.

gcc/ChangeLog:

	* gimple-range-path.cc (path_range_query::import_p): Rename to...
	(path_range_query::exit_dependency_p): ...this.
	(path_range_query::dump): Rename imports to exit dependencies.
	(path_range_query::compute_ranges_in_phis): Same.
	(path_range_query::compute_ranges_in_block): Same.
	(path_range_query::adjust_for_non_null_uses): Same.
	(path_range_query::compute_ranges): Same.
	(path_range_query::compute_phi_relations): Same.
	(path_range_query::add_to_imports): Rename to...
	(path_range_query::add_to_exit_dependencies): ...this.
	(path_range_query::compute_imports): Rename to...
	(path_range_query::compute_exit_dependencies): ...this.
	* gimple-range-path.h (class path_range_query): Rename imports to
	exit dependencies.
---
 gcc/gimple-range-path.cc | 79 +++++++++++++++++++---------------------
 gcc/gimple-range-path.h  | 19 +++++++---
 2 files changed, 51 insertions(+), 47 deletions(-)

diff --git a/gcc/gimple-range-path.cc b/gcc/gimple-range-path.cc
index 78146f5683e..c99d77dd340 100644
--- a/gcc/gimple-range-path.cc
+++ b/gcc/gimple-range-path.cc
@@ -62,13 +62,13 @@ path_range_query::~path_range_query ()
   delete m_cache;
 }
 
-// Return TRUE if NAME is in the import bitmap.
+// Return TRUE if NAME is an exit depenency for the path.
 
 bool
-path_range_query::import_p (tree name)
+path_range_query::exit_dependency_p (tree name)
 {
   return (TREE_CODE (name) == SSA_NAME
-	  && bitmap_bit_p (m_imports, SSA_NAME_VERSION (name)));
+	  && bitmap_bit_p (m_exit_dependencies, SSA_NAME_VERSION (name)));
 }
 
 // Mark cache entry for NAME as unused.
@@ -118,8 +118,8 @@ path_range_query::dump (FILE *dump_file)
 
   dump_ranger (dump_file, m_path);
 
-  fprintf (dump_file, "Imports:\n");
-  EXECUTE_IF_SET_IN_BITMAP (m_imports, 0, i, bi)
+  fprintf (dump_file, "Exit dependencies:\n");
+  EXECUTE_IF_SET_IN_BITMAP (m_exit_dependencies, 0, i, bi)
     {
       tree name = ssa_name (i);
       print_generic_expr (dump_file, name, TDF_SLIM);
@@ -356,7 +356,7 @@ path_range_query::compute_ranges_in_phis (basic_block bb)
       gphi *phi = iter.phi ();
       tree name = gimple_phi_result (phi);
 
-      if (!import_p (name))
+      if (!exit_dependency_p (name))
 	continue;
 
       Value_Range r (TREE_TYPE (name));
@@ -400,17 +400,17 @@ path_range_query::compute_ranges_in_block (basic_block bb)
 
   // Force recalculation of any names in the cache that are defined in
   // this block.  This can happen on interdependent SSA/phis in loops.
-  EXECUTE_IF_SET_IN_BITMAP (m_imports, 0, i, bi)
+  EXECUTE_IF_SET_IN_BITMAP (m_exit_dependencies, 0, i, bi)
     {
       tree name = ssa_name (i);
       if (ssa_defined_in_bb (name, bb))
 	clear_cache (name);
     }
 
-  // Solve imports defined in this block, starting with the PHIs...
+  // Solve dependencies defined in this block, starting with the PHIs...
   compute_ranges_in_phis (bb);
-  // ...and then the rest of the imports.
-  EXECUTE_IF_SET_IN_BITMAP (m_imports, 0, i, bi)
+  // ...and then the rest of the dependencies.
+  EXECUTE_IF_SET_IN_BITMAP (m_exit_dependencies, 0, i, bi)
     {
       tree name = ssa_name (i);
       Value_Range r (TREE_TYPE (name));
@@ -423,7 +423,7 @@ path_range_query::compute_ranges_in_block (basic_block bb)
   if (at_exit ())
     return;
 
-  // Solve imports that are exported to the next block.
+  // Solve dependencies that are exported to the next block.
   basic_block next = next_bb ();
   edge e = find_edge (bb, next);
 
@@ -444,7 +444,7 @@ path_range_query::compute_ranges_in_block (basic_block bb)
 
   gori_compute &g = m_ranger->gori ();
   bitmap exports = g.exports (bb);
-  EXECUTE_IF_AND_IN_BITMAP (m_imports, exports, 0, i, bi)
+  EXECUTE_IF_AND_IN_BITMAP (m_exit_dependencies, exports, 0, i, bi)
     {
       tree name = ssa_name (i);
       Value_Range r (TREE_TYPE (name));
@@ -472,7 +472,7 @@ path_range_query::compute_ranges_in_block (basic_block bb)
     compute_outgoing_relations (bb, next);
 }
 
-// Adjust all pointer imports in BB with non-null information.
+// Adjust all pointer exit dependencies in BB with non-null information.
 
 void
 path_range_query::adjust_for_non_null_uses (basic_block bb)
@@ -481,7 +481,7 @@ path_range_query::adjust_for_non_null_uses (basic_block bb)
   bitmap_iterator bi;
   unsigned i;
 
-  EXECUTE_IF_SET_IN_BITMAP (m_imports, 0, i, bi)
+  EXECUTE_IF_SET_IN_BITMAP (m_exit_dependencies, 0, i, bi)
     {
       tree name = ssa_name (i);
 
@@ -501,39 +501,33 @@ path_range_query::adjust_for_non_null_uses (basic_block bb)
     }
 }
 
-// If NAME is a supported SSA_NAME, add it the bitmap in IMPORTS.
+// If NAME is a supported SSA_NAME, add it to the bitmap in dependencies.
 
 bool
-path_range_query::add_to_imports (tree name, bitmap imports)
+path_range_query::add_to_exit_dependencies (tree name, bitmap dependencies)
 {
   if (TREE_CODE (name) == SSA_NAME
       && Value_Range::supports_type_p (TREE_TYPE (name)))
-    return bitmap_set_bit (imports, SSA_NAME_VERSION (name));
+    return bitmap_set_bit (dependencies, SSA_NAME_VERSION (name));
   return false;
 }
 
-// Compute the imports to PATH.  These are
-// essentially the SSA names used to calculate the final conditional
-// along the path.
-//
-// 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.
+// Compute the exit dependencies to PATH.  These are essentially the
+// SSA names used to calculate the final conditional along the path.
 
 void
-path_range_query::compute_imports (bitmap imports, const vec<basic_block> &path)
+path_range_query::compute_exit_dependencies (bitmap dependencies,
+					     const vec<basic_block> &path)
 {
   // Start with the imports from the exit block...
   basic_block exit = path[0];
   gori_compute &gori = m_ranger->gori ();
-  bitmap r_imports = gori.imports (exit);
-  bitmap_copy (imports, r_imports);
+  bitmap_copy (dependencies, gori.imports (exit));
 
-  auto_vec<tree> worklist (bitmap_count_bits (imports));
+  auto_vec<tree> worklist (bitmap_count_bits (dependencies));
   bitmap_iterator bi;
   unsigned i;
-  EXECUTE_IF_SET_IN_BITMAP (imports, 0, i, bi)
+  EXECUTE_IF_SET_IN_BITMAP (dependencies, 0, i, bi)
     {
       tree name = ssa_name (i);
       worklist.quick_push (name);
@@ -557,7 +551,7 @@ path_range_query::compute_imports (bitmap imports, const vec<basic_block> &path)
 
 	      if (TREE_CODE (arg) == SSA_NAME
 		  && path.contains (e->src)
-		  && bitmap_set_bit (imports, SSA_NAME_VERSION (arg)))
+		  && bitmap_set_bit (dependencies, SSA_NAME_VERSION (arg)))
 		worklist.safe_push (arg);
 	    }
 	}
@@ -581,7 +575,7 @@ path_range_query::compute_imports (bitmap imports, const vec<basic_block> &path)
 	  for (unsigned j = 0; j < 3; ++j)
 	    {
 	      tree rhs = ssa[j];
-	      if (rhs && add_to_imports (rhs, imports))
+	      if (rhs && add_to_exit_dependencies (rhs, dependencies))
 		worklist.safe_push (rhs);
 	    }
 	}
@@ -594,19 +588,20 @@ path_range_query::compute_imports (bitmap imports, const vec<basic_block> &path)
 	tree name;
 	FOR_EACH_GORI_EXPORT_NAME (gori, bb, name)
 	  if (TREE_CODE (TREE_TYPE (name)) == BOOLEAN_TYPE)
-	    bitmap_set_bit (imports, SSA_NAME_VERSION (name));
+	    bitmap_set_bit (dependencies, SSA_NAME_VERSION (name));
       }
 }
 
-// Compute the ranges for IMPORTS along PATH.
+// Compute the ranges for DEPENDENCIES along PATH.
 //
-// IMPORTS are the set of SSA names, any of which could potentially
-// change the value of the final conditional in PATH.  Default to the
-// imports of the last block in the path if none is given.
+// DEPENDENCIES are path exit dependencies.  They are the set of SSA
+// names, any of which could potentially change the value of the final
+// conditional in PATH.  If none is given, the exit dependencies are
+// calculated from the final conditional in the path.
 
 void
 path_range_query::compute_ranges (const vec<basic_block> &path,
-				  const bitmap_head *imports)
+				  const bitmap_head *dependencies)
 {
   if (DEBUG_SOLVER)
     fprintf (dump_file, "\n==============================================\n");
@@ -614,10 +609,10 @@ path_range_query::compute_ranges (const vec<basic_block> &path,
   set_path (path);
   m_undefined_path = false;
 
-  if (imports)
-    bitmap_copy (m_imports, imports);
+  if (dependencies)
+    bitmap_copy (m_exit_dependencies, dependencies);
   else
-    compute_imports (m_imports, m_path);
+    compute_exit_dependencies (m_exit_dependencies, m_path);
 
   if (m_resolve)
     get_path_oracle ()->reset_path ();
@@ -809,7 +804,7 @@ path_range_query::compute_phi_relations (basic_block bb, basic_block prev)
       tree result = gimple_phi_result (phi);
       unsigned nargs = gimple_phi_num_args (phi);
 
-      if (!import_p (result))
+      if (!exit_dependency_p (result))
 	continue;
 
       for (size_t i = 0; i < nargs; ++i)
diff --git a/gcc/gimple-range-path.h b/gcc/gimple-range-path.h
index e783e00b2f5..3cb794e34a9 100644
--- a/gcc/gimple-range-path.h
+++ b/gcc/gimple-range-path.h
@@ -35,9 +35,10 @@ public:
   path_range_query (bool resolve = true, class gimple_ranger *ranger = NULL);
   virtual ~path_range_query ();
   void compute_ranges (const vec<basic_block> &,
-		       const bitmap_head *imports = NULL);
+		       const bitmap_head *dependencies = NULL);
   void compute_ranges (edge e);
-  void compute_imports (bitmap imports, const vec<basic_block> &);
+  void compute_exit_dependencies (bitmap dependencies,
+				  const vec<basic_block> &);
   bool range_of_expr (vrange &r, tree name, gimple * = NULL) override;
   bool range_of_stmt (vrange &r, gimple *, tree name = NULL) override;
   bool unreachable_path_p ();
@@ -64,8 +65,8 @@ 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 *, edge e);
-  bool add_to_imports (tree name, bitmap imports);
-  bool import_p (tree name);
+  bool add_to_exit_dependencies (tree name, bitmap dependencies);
+  bool exit_dependency_p (tree name);
   bool ssa_defined_in_bb (tree name, basic_block bb);
   bool relations_may_be_invalidated (edge);
 
@@ -89,7 +90,15 @@ private:
   // Path being analyzed.
   auto_vec<basic_block> m_path;
 
-  auto_bitmap m_imports;
+  // This is a list of SSA names that may have relevant context
+  // information for solving the final conditional along the path.
+  // Ranges for these SSA names are pre-calculated and cached during a
+  // top-down traversal of the path, and are then used to answer
+  // questions at the path exit.
+  auto_bitmap m_exit_dependencies;
+
+  // A ranger used to resolve ranges for SSA names whose values come
+  // from outside the path.
   gimple_ranger *m_ranger;
 
   // Current path position.
-- 
2.37.1