Soumya AR <[email protected]> writes:
> The current narrow_gp_writes pass makes a single sweep over a function in RPO,
> and makes conservative assumptions about definitions that have not yet been
> processed (eg. from backedges).
>
> Following the suggestions on the original pass at
> gcc.gnu.org/pipermail/gcc-patches/2026-February/709227.html, this pass has
> been
> rewritten to use an iterative worklist analysis, which uses an optimistic
> approach to find more narrowing opportunities.
>
> With this update, we observe around 1600 more narrowings (+3.35%) with
> SPEC2026
> INT benchmarks.
>
> ----
>
> Consider the following reduced example from 706.stockfish_r:
>
> unsigned long long sum = 0;
> x &= 255;
>
> while (x)
> {
> sum += x;
> x &= x - 1;
> }
>
> At the loop header, a PHI merges the initial value of x with its value
> from the backedge. The phi's nonzero-bit mask is the bitwise OR of the masks
> of all its incoming definitions.
>
> The initial value has mask 0xff, but the old pass assumes a full-width
> mask for the unprocessed backedge, making the PHI mask full-width too.
>
> With a zero starting mask for the backedge, the PHI mask is
> 0xff | 0 = 0xff. The loop's AND preserves this bound, giving the backedge
> a mask of 0xff. Revisiting the PHI gives 0xff | 0xff = 0xff, so the masks
> are stable and the AND can be narrowed to 32 bits.
>
> ----
>
> We separate the worklist analysis into a generic RTL-SSA helper that is used
> by the aarch64 narrowing pass. This generic framework works using two
> callbacks
> supplied by the client (caller):
> - can_process_def_p (def) returns true if the client wants this def
> processed (ie. added to the worklist)
> - process_def (def) performs a client-specific computation on def and
> returns true if definitions that depend on def need to be processed
> again.
>
> Each selected definition starts with an optimistic zero mask, stored in
> m_nonzero_masks.
>
> These definitions are added to a worklist and processed one at a time.
> Instruction masks are computed using nonzero_bits, while PHI masks are
> computed
> as the bitwise OR of their input masks. Whenever a mask changes, its entry in
> the map is updated, and selected definitions that depend on it are enqueued
> for
> further processing.
>
> We continue until the worklist is empty. At this point, processing the
> definitions again would not change any mask since the analysis has reached a
> fixed point. We then use these masks to narrow instructions.
>
> ----
>
> Bootstrapped and regtested on aarch64-linux-gnu, no regressions. OK for trunk?
>
> gcc/ChangeLog:
>
> * Makefile.in: Add rtl-ssa/def-propagation.h.
> * config/aarch64/aarch64-narrow-gp-writes.cc: Update to use worklist
> algorithm.
> * rtl-ssa.h: Include def-propagation.h
> * rtl-ssa/def-propagation.h: New file.
>
> gcc/testsuite/ChangeLog:
>
> * gcc.target/aarch64/narrow-gp-writes-9.c: New test.
>
> Signed-off-by: Soumya AR <[email protected]>
>
> From 580249f4a6668d4eaf8e173d2629d7e629425f86 Mon Sep 17 00:00:00 2001
> From: Soumya AR <[email protected]>
> Date: Tue, 8 Sep 2026 09:43:38 +0000
> Subject: [PATCH] aarch64: Use optimistic worklist analysis for
> narrow_gp_writes
>
> The current narrow_gp_writes pass makes a single sweep over a function in RPO,
> and makes conservative assumptions about definitions that have not yet been
> processed (eg. from backedges).
>
> Following the suggestions on the original pass at
> gcc.gnu.org/pipermail/gcc-patches/2026-February/709227.html, this pass has
> been
> rewritten to use an iterative worklist analysis, which uses an optimistic
> approach to find more narrowing opportunities.
>
> With this update, we observe around 1600 more narrowings (+3.35%) with
> SPEC2026
> INT benchmarks.
>
> ----
>
> Consider the following reduced example from 706.stockfish_r:
>
> unsigned long long sum = 0;
> x &= 255;
>
> while (x)
> {
> sum += x;
> x &= x - 1;
> }
>
> At the loop header, a PHI merges the initial value of x with its value
> from the backedge. The phi's nonzero-bit mask is the bitwise OR of the masks
> of all its incoming definitions.
>
> The initial value has mask 0xff, but the old pass assumes a full-width
> mask for the unprocessed backedge, making the PHI mask full-width too.
>
> With a zero starting mask for the backedge, the PHI mask is
> 0xff | 0 = 0xff. The loop's AND preserves this bound, giving the backedge
> a mask of 0xff. Revisiting the PHI gives 0xff | 0xff = 0xff, so the masks
> are stable and the AND can be narrowed to 32 bits.
>
> ----
>
> We separate the worklist analysis into a generic RTL-SSA helper that is used
> by the aarch64 narrowing pass. This generic framework works using two
> callbacks
> supplied by the client (caller):
> - can_process_def_p (def) returns true if the client wants this def
> processed (ie. added to the worklist)
> - process_def (def) performs a client-specific computation on def and
> returns true if definitions that depend on def need to be processed
> again.
>
> Each selected definition starts with an optimistic zero mask, stored in
> m_nonzero_masks.
>
> These definitions are added to a worklist and processed one at a time.
> Instruction masks are computed using nonzero_bits, while PHI masks are
> computed
> as the bitwise OR of their input masks. Whenever a mask changes, its entry in
> the map is updated, and selected definitions that depend on it are enqueued
> for
> further processing.
>
> We continue until the worklist is empty. At this point, processing the
> definitions again would not change any mask since the analysis has reached a
> fixed point. We then use these masks to narrow instructions.
>
> ----
>
> Bootstrapped and regtested on aarch64-linux-gnu, no regressions. OK for trunk?
>
> gcc/ChangeLog:
>
> * Makefile.in: Add rtl-ssa/def-propagation.h.
> * config/aarch64/aarch64-narrow-gp-writes.cc: Update to use worklist
> algorithm.
> * rtl-ssa.h: Include def-propagation.h
> * rtl-ssa/def-propagation.h: New file.
>
> gcc/testsuite/ChangeLog:
>
> * gcc.target/aarch64/narrow-gp-writes-9.c: New test.
>
> Signed-off-by: Soumya AR <[email protected]>
Thanks for doing this. It mostly looks good to me, but a couple of
comments below:
> [...]
> +/* RTL hooks callback for computing nonzero bits of registers.
> + Updates NONZERO with the tracked nonzero bits for register X. */
> +rtx
> +reg_nonzero_bits_for_narrow_gp_writes (const_rtx x, scalar_int_mode xmode,
> + scalar_int_mode, mask_t *nonzero)
> +{
> + narrow_gp_writes *pass = narrow_gp_writes::get_instance ();
> + insn_info *insn = pass->m_current_insn;
> + if (!insn)
> + return NULL_RTX;
> +
> + use_info *use = find_access (insn->uses (), REGNO (x));
> + if (!use)
> + return NULL_RTX;
> + /* find_access searches by register number, not mode. Ignore the result if
> + its mode does not match XMODE. */
> + if (use->mode () != xmode)
> + return NULL_RTX;
> + set_info *reaching_def = use->def ();
> + if (!reaching_def)
> + return NULL_RTX;
> +
> + mask_t def_mask = pass->lookup_nonzero_mask (reaching_def);
> + /* If the def is in a narrower mode than the use, RTL semantics say the
> upper
> + bits are undefined. Treat them conservatively as potentially nonzero.
> */
> + if (known_lt (GET_MODE_SIZE (reaching_def->mode ()),
> + GET_MODE_SIZE (use->mode ())))
This is pre-existing, but it should use maybe_lt rather than known_lt.
> + def_mask |= ~GET_MODE_MASK (reaching_def->mode ());
> + *nonzero &= def_mask;
> + return NULL_RTX;
> +}
> +
> +/* Return true if DEF is a GP register definition that can be analyzed. */
> +bool
> +narrow_gp_writes::can_track_def_p (set_info *def) const
> +{
> + if (!GP_REGNUM_P (def->regno ()))
> + return false;
>
> - The caller is expected to call this once per phi and store the result;
> - calling it on demand would re-walk all phi inputs for every use, giving
> - O(in-degree * num-uses) cost. */
> + insn_info *insn = def->insn ();
> + if (insn->is_phi ())
> + return true;
>
> + return can_track_nonzero_bits_p (insn);
> +}
> +
> +/* Collect the definitions to analyze and initialize each definition's
> nonzero
> + mask to zero. This is an optimistic assumption that will be refined as we
> + process more information. */
> +void
> +narrow_gp_writes::collect_initial_defs (auto_vec<set_info *> &initial_defs)
> +{
> + for (ebb_info *ebb : crtl->ssa->ebbs ())
> + {
> + for (phi_info *phi : ebb->phis ())
> + if (can_track_def_p (phi))
> + {
> + m_nonzero_masks.put (phi, 0);
> + initial_defs.safe_push (phi);
> + }
> +
> + for (insn_info *insn : ebb->nondebug_insns ())
> + for (def_info *def : insn->defs ())
> + if (set_info *set = dyn_cast<set_info *> (def))
> + if (can_track_def_p (set))
> + {
> + m_nonzero_masks.put (set, 0);
> + initial_defs.safe_push (set);
> + }
> + }
This seems broader than it needs to be. We should only need to make
a conservative assumption for backedges.
How about handling this as follows:
(1) Remove the initial_defs argument from def_propagation::propagate.
(2) Instead, make the first pass of def_propagation::propagate
iterate over all definitions itself. Like the existing loop,
this would involve calling process_def, but it would only enqueue
uses that occur earlier than the current instruction. (Later uses
will be processed later in the first pass.)
(3) Expose can_track_nonzero_bits_p to def_propagation with an
appropriate abstraction (e.g. can_process_insn_p, but better
names welcome). Use it to skip processing of instructions in (2).
(4) Add a new parameter to process_def that indicates whether it is
being called during the first pass.
(5) Treat backedges optimistically on the first pass. This would only
affect calculate_phi_mask.
(6) Similarly, make process_def assume that the definition's current
mask is 0 rather than GET_MODE_MASK during the first pass.
Perhaps a helper would be good, given that (5) and (6) need
the same thing.
(7) Make process_def remove items from m_nonzero_masks rather than
storing a superset of GET_MODE_MASK.
This should be more efficient in two ways: it saves one pass over the
IL and it avoids creating m_nonzero_masks entries for definitions that
never have useful information.
Thanks,
Richard
