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]>
0001-aarch64-Use-optimistic-worklist-analysis-for-narrow_.patch
Description: 0001-aarch64-Use-optimistic-worklist-analysis-for-narrow_.patch
