On Wed, Aug 20, 2025 at 1:03 PM Richard Sandiford
<richard.sandif...@arm.com> wrote:
>
> 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?
OK.
> 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
>
