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.
Tested on aarch64-linux-gnu, powerpc64le-linux-gnu and
x86_64-linux-gnu. OK to install?
Richard
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/functions.cc (function_info::find_use): Likewise.
---
gcc/rtl-ssa/accesses.cc | 32 ++++++++++++++++++++++++++++++++
gcc/rtl-ssa/accesses.h | 36 ++++++++++++++++++++++++++++++++++++
gcc/rtl-ssa/functions.h | 15 +++++++++++++++
gcc/rtl-ssa/member-fns.inl | 30 ++++++++++++++++++++++++++++++
4 files changed, 113 insertions(+)
diff --git a/gcc/rtl-ssa/accesses.cc b/gcc/rtl-ssa/accesses.cc
index 3d929971f56..0415e976798 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 98403f78b37..b3a31fb78db 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 2e20f5e47d7..27cbc18178a 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 346a1208c84..1049f613776 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),
--
2.43.0
