https://gcc.gnu.org/bugzilla/show_bug.cgi?id=127737
Bug ID: 127737
Summary: IRA regional allocation emits redundant spill stores
for loop-invariant values across nested loops
Product: gcc
Version: 16.2.1
Status: UNCONFIRMED
Severity: normal
Priority: P3
Component: rtl-optimization
Assignee: unassigned at gcc dot gnu.org
Reporter: stefan at franke dot ms
Target Milestone: ---
Created attachment 65753
--> https://gcc.gnu.org/bugzilla/attachment.cgi?id=65753&action=edit
testcase for arm
With default flags on ARM (-O2) and m68k (-O2 -m68020-40), and
presumably on any target where IRA's regional allocation decides to
spill a loop-invariant value, IRA's regional register
allocation splits at nested loop boundaries and treats loop-invariant
values as if they were redefined inside the inner region. LRA then
emits a store of the value to its spill slot on every exit from the
region, even though the value was not modified. The store is redundant
and the value is reloaded unchanged on the next iteration.
The pattern is most visible with a value that is defined once before a
nested loop, read on every iteration of the inner loop, and only
redefined in a rarely-taken branch. IRA's regional split forces the
value into memory at the region boundary, and LRA's spill code places
the store at the boundary rather than at the actual redefinition point.
-fira-region=one avoids the problem by treating the whole function as a
single region: the value is then live across the entire function with a
single definition and a single update point, and LRA places stores only
at those two points. The reloads remain, because the register file is
genuinely too small to hold all the values, but the redundant stores
are gone.
Reproduces on ARM (Cortex-A9, -O2) and m68k (-O2, m68020-40).
Also seen in zlib's longest_match on m68k; -fira-region=one
improves the benchmark geomean by 4.5% and dhrystone by 21%.
Testcase for ARM GCC:
/* Testcase: eight loop-invariant byte values read on every iteration
of a nested loop. With the default -O2 flags (IRA_REGION_MIXED),
IRA splits the function into regions at the loop boundaries and
treats the invariant values as if they were redefined inside the
inner region. LRA then emits a store of each value to its spill
slot on every exit from the region, even though the value was not
modified. The store is redundant: the value is reloaded unchanged
on the next iteration.
Confirmed reproducers:
- ARM Cortex-A9, -O2, default flags
- m68k (68020-40), -O2, default flags (also in zlib longest_match)
Non-reproducer:
- x86_64, -O2: 15 GPRs are enough to hold all eight bytes, so
no spill occurs and the pattern does not appear.
Expected bug: a store of scan_endN to a stack slot at the loop
boundary, and a reload of that slot at each use inside the loop,
even though scan_endN is not modified between uses.
Workaround: -fira-region=one. This treats the whole function as a
single region, so the value has a single definition point and a
single update point, and LRA places stores only at those points.
The reloads remain (the register file is genuinely too small), but
the redundant stores are gone. -fira-region=mixed reproduces the
bug identically to the default. */
typedef unsigned char u8;
typedef unsigned int u32;
struct state {
u8 *window;
u32 strstart;
u32 lookahead;
u32 w_size;
u32 w_mask;
u32 *prev;
u32 max_chain;
u32 nice_match;
};
__attribute__((noinline))
u32 longest_match(struct state *s, u32 cur_match)
{
u32 chain_length = s->max_chain;
u8 *scan = s->window + s->strstart;
u8 *match;
int len;
int best_len = 0;
int nice_match = s->nice_match;
u32 limit = s->strstart > (s->w_size - 262) ? s->strstart - (s->w_size - 262)
: 0;
u32 *prev = s->prev;
u32 wmask = s->w_mask;
u8 *strend = s->window + s->strstart + 258;
/* Eight loop-invariant byte values. All are read on every iteration
of the outer do-loop. On a register-starved target the allocator
cannot keep all eight in registers and must spill at least one. */
u8 scan_end0 = scan[best_len];
u8 scan_end1 = scan[best_len - 1];
u8 scan_end2 = scan[best_len - 2];
u8 scan_end3 = scan[best_len - 3];
u8 scan_end4 = scan[best_len - 4];
u8 scan_end5 = scan[best_len - 5];
u8 scan_end6 = scan[best_len - 6];
u8 scan_end7 = scan[best_len - 7];
if (s->lookahead < 262)
nice_match = s->lookahead;
do {
match = s->window + cur_match;
/* All eight scan_end values are used here, on every iteration. */
if (match[best_len] != scan_end0 ||
match[best_len - 1] != scan_end1 ||
match[best_len - 2] != scan_end2 ||
match[best_len - 3] != scan_end3 ||
match[best_len - 4] != scan_end4 ||
match[best_len - 5] != scan_end5 ||
match[best_len - 6] != scan_end6 ||
match[best_len - 7] != scan_end7 ||
*match != *scan ||
*++match != scan[1])
continue;
scan += 2;
match++;
do {
} while (*++scan == *++match && *++scan == *++match &&
*++scan == *++match && *++scan == *++match &&
*++scan == *++match && *++scan == *++match &&
*++scan == *++match && *++scan == *++match &&
scan < strend);
len = 258 - (int)(strend - scan);
scan = strend - 258;
if (len > best_len) {
s->strstart = cur_match;
best_len = len;
if (len >= nice_match)
break;
/* Update all eight values; this branch is rarely taken, so the
values are effectively invariants of the hot path. */
scan_end0 = scan[best_len];
scan_end1 = scan[best_len - 1];
scan_end2 = scan[best_len - 2];
scan_end3 = scan[best_len - 3];
scan_end4 = scan[best_len - 4];
scan_end5 = scan[best_len - 5];
scan_end6 = scan[best_len - 6];
scan_end7 = scan[best_len - 7];
}
} while ((cur_match = prev[cur_match & wmask]) > limit
&& --chain_length != 0);
return best_len;
}
