https://gcc.gnu.org/bugzilla/show_bug.cgi?id=127314
Bug ID: 127314
Summary: [middle-end] do-while entry test re-reads a byte that
a PRE-hoisted lut lookup already loaded — one more
memory access than the source performs (all targets,
-O2/-O3)
Product: gcc
Version: 16.2.0
Status: UNCONFIRMED
Severity: normal
Priority: P3
Component: c
Assignee: unassigned at gcc dot gnu.org
Reporter: 220255624 at seu dot edu.cn
CC: jianhao.xu at seu dot edu.cn
Target Milestone: ---
Environment:
gcc 16.2.0, x86-64 (x86-64 Linux host), default -O2 (same at -O3). Also
present in 15.2.0 and 14.2.0 (x86-64). With 16.1.0 the pattern is present
when compiling for x86-64, aarch64, loongarch64, mips64, powerpc64le,
riscv64 and s390x (7/7 targets) at -O2 and -O3, and the extra read was
confirmed by byte-granular dynamic load counting on all 7 targets (QEMU).
Version window (x86-64): -O3 back to 7.2; -O2 from 12.2 on.
Clean: -O0, -O1, -fno-tree-pre. -fno-ivopts changes nothing.
Testcase(https://gcc.godbolt.org/z/YWbWeenPq):
unsigned char g_lut[256];
char g_buf[64];
void func_test(char *str, const unsigned char *keep_lut)
{
if (keep_lut[(unsigned char)*str]) str++;
char *out = str;
unsigned char c;
do {
c = *str++;
unsigned char inc = keep_lut[c];
*out = c;
out += inc;
} while (c);
}
Build: gcc -O2 -c t.c && objdump -d t.o
Live on Compiler Explorer (same testcase, gcc 16.2, -O2, Intel syntax):
Observed (gcc 16.2.0 -O2, x86-64):
func_test:
movzx eax, BYTE PTR [rdi] # read buf[0] (the if-scan step)
movzx eax, BYTE PTR [rsi+rax] # lut[buf[0]]
test al, al
je .L2
movzx eax, BYTE PTR [rdi+1] # <-- 1st read of buf[1]: the PRE-
add rdi, 1 # hoisted load of the first
movzx eax, BYTE PTR [rsi+rax] # iteration's lut input; this lut
# load clobbers the only register
# copy of the byte
.L2:
cmp BYTE PTR [rdi], 0 # <-- 2nd read of buf[1]: the
do-while
je .L1 # entry test re-reads the same byte
mov rcx, rdi
.L4:
add rdi, 1
add rcx, rax
movzx eax, BYTE PTR [rdi] # (the loop body itself keeps a copy
mov rdx, rax # of the byte in rdx and tests the
movzx eax, BYTE PTR [rsi+rax] # register: test dl,dl)
mov BYTE PTR [rcx], dl
test dl, dl
jne .L4
.L1:
ret
After `add rdi,1`, the byte read by `[rdi]` at .L2 is exactly the byte read
by `[rdi+1]` before it, and between the two reads there is only an `add` and
a load (the lut lookup) — no store. On the path where the if-scan step is
taken (keep_lut[buf[0]] != 0), the C code reads that byte exactly once:
`c = *str++` loads it, and `while (c)` tests the local variable c.
Byte-granular dynamic load counting (QEMU TCG plugin; cross-checked with an
independent Intel Pin observer and with GDB breakpoint counts) gives
expected 1 / observed 2 for that byte, identically on all 7 targets at -O2
and -O3.
Expected:
The first iteration's do-while exit test should reuse the value the
PRE-hoisted load already fetched — i.e. a reg->reg copy, exactly what this
function's own loop body does in the same compile — or the two loads should
be CSE'd into one. (The hoisted load itself must stay: it feeds
keep_lut[c] for the first iteration. -fno-tree-pre only serves as an
attribution test here, it is not the proposed fix.)
Analysis (from -fdump-tree-all, gcc 16.1.0 -O2, same shape as 16.2):
- 158t.pre hoists the first iteration's `inc = keep_lut[c]` into the
if-taken branch:
bb3: _59 = str + 1;
pretmp_42 = MEM[(char *)str + 1B];
pretmp_50 = keep_lut[pretmp_42];
- The first iteration's own `c = *str` load stays in the join block
(273t.optimized):
bb4: _38 = *str_10; str_10 = PHI <str, _59>,
where it is used only by the exit test.
- FRE/DOM do not CSE the two MEMs because one address is the loop-rotation
PHI SSA name and the other is the folded form (str + 1B) — the same
limitation diagnosed in PR100922 comment #4: "Which is fine except FRE
(and DOM), don't recognize the MEM[(char *)str_16 + -1B] and
MEM[(char *)str_41] being the same. For FRE, it almost looks like
TARGET_MEM_REF is not handled ...."
- At RTL the entry load's only user is the exit test, so it becomes
`cmp byte ptr [rdi],0`.
Data point for the fix: at -O2, gcc 9.4/10.5 lower this same shape with a
register copy for the entry test, and 12.2+ switch to the memory compare,
i.e. forwarding the hoisted value is enough — disabling PRE is not needed.
Related:
- PR100922 (RESOLVED FIXED) is the same family: its fix converts the
loop-body instance into a reg->reg copy (visible in .L4 above), but the
entry-test instance is not covered — the while-scan form of this template
is clean on 16.x while this if-scan form is not.
- PR114173 (NEW) is a related open report (memory compare + load of the same
byte) with a different shape and pass.
- PR21485 is the opposite direction (missed load PRE).
Classification:
missed optimization (one redundant memory access), not a miscompile: output
and exit code are identical at -O0/-O1/-O2/-O3, with -fno-tree-pre, across
the versions listed above.
