On on Sat, 10 Oct 2026 10:42:38 +0100, Richard Sandiford <[email protected]> wrote: > 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:
Hi Richard,
Thank you for your feedback! I've adjusted the patch now to follow the
approach you suggested.
>
>> [...]
>> +/* 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.
Fixed.
>
>> + 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.)
Done. propagate now takes just the client and walks the EBBs in RPO
itself.
I think this should also mean that we only need to look at phi uses
during the first pass since all regular nondebug insn uses for a def
would occur after it anyway. I've written it that way in the updated
patch.
>
> (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).
>
Ended up with can_process_insn_p. I assume we still need
can_process_def_p though, so there are three callbacks now.
> (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.
Done. The map now only holds useful masks and a missing entry (for defs
that have already been visited) implies the full mode mask.
Thanks,
Soumya
>
> 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
v2-0001-aarch64-Use-optimistic-worklist-analysis-for-narr.patch
Description: v2-0001-aarch64-Use-optimistic-worklist-analysis-for-narr.patch
