rtl-ssa: Add a find_uses function

rtl-ssa already has a find_def function for finding the definition
of a particular resource (register or memory) at a particular point
in the program.  This patch adds a similar function for looking
up uses.  Both functions have amortised logarithmic complexity.

gcc/
	* rtl-ssa/accesses.h (use_lookup): New class.
	* rtl-ssa/functions.h (function_info::find_def): Expand comment.
	(function_info::find_use): Declare.
	* rtl-ssa/member-fns.inl (use_lookup::prev_use, use_lookup::next_use)
	(use_lookup::matching_use, use_lookup::matching_or_prev_use)
	(use_lookup::matching_or_next_use): New member functions.
	* rtl-ssa/accesses.cc (function_info::find_use): Likewise.

4 files changed, 113 insertions, 0 deletions

diff --git a/gcc/rtl-ssa/accesses.cc b/gcc/rtl-ssa/accesses.cc
index 3d92997..0415e97 100644
--- a/gcc/rtl-ssa/accesses.cc
+++ b/gcc/rtl-ssa/accesses.cc
@@ -1087,6 +1087,38 @@ rtl_ssa::lookup_use (splay_tree<use_info *> &tree, insn_info *insn)
   return tree.lookup (compare);
 }
 
+// See the comment above the declaration.
+use_lookup
+function_info::find_use (set_info *def, insn_info *insn)
+{
+  gcc_assert (!insn->is_debug_insn ());
+  use_info *first = def->first_nondebug_insn_use ();
+  if (!first)
+    // There are no uses.  The comparison result is pretty meaningless
+    // in this case.
+    return { nullptr, -1 };
+
+  // See whether the first use matches.
+  if (*insn <= *first->insn ())
+    {
+      int comparison = (insn == first->insn () ? 0 : -1);
+      return { first, comparison };
+    }
+
+  // See whether the last use matches.
+  use_info *last = def->last_nondebug_insn_use ();
+  if (*insn >= *last->insn ())
+    {
+      int comparison = (insn == last->insn () ? 0 : 1);
+      return { last, comparison };
+    }
+
+  // Resort to using a splay tree to search for the result.
+  need_use_splay_tree (def);
+  int comparison = lookup_use (def->m_use_tree, insn);
+  return { def->m_use_tree.root ()->value (), comparison };
+}
+
 // Add USE to USE->def ()'s list of uses. inserting USE immediately before
 // BEFORE.  USE is not currently in the list.
 //
diff --git a/gcc/rtl-ssa/accesses.h b/gcc/rtl-ssa/accesses.h
index 98403f7..b3a31fb 100644
--- a/gcc/rtl-ssa/accesses.h
+++ b/gcc/rtl-ssa/accesses.h
@@ -1044,6 +1044,42 @@ public:
   int comparison;
 };
 
+// This class represents the result of looking for a use of a particular
+// definition at a particular point, here referred to as point P.
+// There are four states:
+//
+// - USE is null if the definition has no uses.
+//
+// - Otherwise, COMPARISON is 0 if we found a definition at P.  USE then
+//   contains this use.
+//
+// - Otherwise, COMPARISON is greater than 0 if we found a use that precedes P.
+//   USE then contains this use.
+//
+// - Otherwise, COMPARISON is less than zero and we found a use that follows P.
+//   USE then contains this use.
+class use_lookup
+{
+public:
+  // If we found a use at P, return that use, otherwise return null.
+  use_info *matching_use () const;
+
+  // If we found a use at P, return that use, otherwise return prev_use ().
+  use_info *matching_or_prev_use () const;
+
+  // If we found a use at P, return that use, otherwise return next_use ().
+  use_info *matching_or_next_use () const;
+
+  // Return the last use that occurs before P, or null if none.
+  use_info *prev_use () const;
+
+  // Return the first use that occurs after P, or null if none.
+  use_info *next_use () const;
+
+  use_info *use;
+  int comparison;
+};
+
 void pp_resource (pretty_printer *, resource_info);
 void pp_access (pretty_printer *, const access_info *,
 		unsigned int flags = PP_ACCESS_DEFAULT);
diff --git a/gcc/rtl-ssa/functions.h b/gcc/rtl-ssa/functions.h
index 2e20f5e..27cbc18 100644
--- a/gcc/rtl-ssa/functions.h
+++ b/gcc/rtl-ssa/functions.h
@@ -131,8 +131,23 @@ public:
 
   // Look for a definition of RESOURCE at INSN.  Return the result of the
   // search as a def_lookup; see the comments there for more details.
+  //
+  // NOTE: This is not the function to use if INSN is known to be a real
+  // instruction (one with an RTL pattern) and if the caller is only
+  // interested in definitions within INSN itself.  In those cases
+  // it is better to use find_access.
   def_lookup find_def (resource_info resource, insn_info *insn);
 
+  // Search for a use of DEF around non-debug instruction INSN and return the
+  // result of the search as a use_lookup.  See the comment above the class
+  // for more details about the result means.
+  //
+  // NOTE: This is not the function to use if INSN is known to be a real
+  // instruction (one with an RTL pattern) and if the caller is only
+  // interested in uses within INSN itself.  In those cases it is better
+  // to use find_access.
+  use_lookup find_use (set_info *def, insn_info *insn);
+
   // Return an RAII object that owns all temporary RTL SSA memory
   // allocated during a change attempt.  The object should remain in
   // scope until the change has been aborted or successfully completed.
diff --git a/gcc/rtl-ssa/member-fns.inl b/gcc/rtl-ssa/member-fns.inl
index 346a120..1049f61 100644
--- a/gcc/rtl-ssa/member-fns.inl
+++ b/gcc/rtl-ssa/member-fns.inl
@@ -478,6 +478,36 @@ def_lookup::matching_set_or_first_def_of_next_group () const
   return first_def_of_next_group ();
 }
 
+inline use_info *
+use_lookup::prev_use () const
+{
+  return !use || comparison > 0 ? use : use->prev_use ();
+}
+
+inline use_info *
+use_lookup::next_use () const
+{
+  return !use || comparison < 0 ? use : use->next_nondebug_insn_use ();
+}
+
+inline use_info *
+use_lookup::matching_use () const
+{
+  return comparison == 0 ? use : nullptr;
+}
+
+inline use_info *
+use_lookup::matching_or_prev_use () const
+{
+  return comparison == 0 ? use : prev_use ();
+}
+
+inline use_info *
+use_lookup::matching_or_next_use () const
+{
+  return comparison == 0 ? use : next_use ();
+}
+
 inline insn_note::insn_note (insn_note_kind kind)
   : m_next_note (nullptr),
     m_kind (kind),