[X86][LICM/GVN] Loop-invariant loads not hoisted after full loop unrolling
- Dominant language
- LLVM
- Stars
- 40.5k
- Forks
- 18.7k
- PR merge metrics
- PR metrics pending
Description
**Clang:** Ubuntu clang version 22.1.8 · reproduced on Godbolt 22.1.0
**Target:** x86_64-pc-linux-gnu · **Compile:** `clang -O3`
**Labels:** `missed-optimization` `backend:X86`
## Summary
With `-O3`, Clang fully unrolls a 16-iteration loop but then **fails to recognize
that the loop-body loads are invariant**. `g[19]` and `g[18]` are never written
inside the loop, yet the optimizer generates 16 separate `movl g+76(%rip)` and
16 separate `movl g+72(%rip)` instructions — one redundant reload per unrolled
iteration.
`LICM` should hoist these two loads to before the loop, and `GVN` should then
eliminate the 30 remaining reloads, reducing 32 memory reads to 2.
## Reproducer
```c
unsigned g[20];
void f(int *p) {
for (int i = 22; i <= 37; ++i) {
if (g[19]) {
if (g[18]) {
*p = 5;
}
}
}
}
```
## Actual output (`-O3`)
```asm
f:
movl g+76(%rip), %eax ; g[19] ← iteration 1
testl %eax, %eax
setne %dl
movl g+72(%rip), %ecx ; g[18] ← iteration 1
testl %ecx, %ecx
...
movl g+76(%rip), %eax ; g[19] ← iteration 2 (REDUNDANT)
movl g+72(%rip), %ecx ; g[18] ← iteration 2 (REDUNDANT)
...
;; Repeated 16 times total for each of g[19] and g[18]
```
Both `g[19]` (`g+76`) and `g[18]` (`g+72`) are loaded **16 times** — once per
unrolled iteration — despite no write to `g` occurring anywhere in the loop body.
## Expected output
```asm
f:
movl g+76(%rip), %eax ; g[19] ← hoisted: load ONCE
testl %eax, %eax
je .done ; short-circuit if g[19] == 0
movl g+72(%rip), %ecx ; g[18] ← hoisted: load ONCE
testl %ecx, %ecx
je .done ; short-circuit if g[18] == 0
movl $5, (%rdi) ; *p = 5
.done:
retq
```
(The loop body is `*p = 5` when both conditions hold. Since neither `g[18]` nor
`g[19]` changes, the result is identical across all 16 iterations — so at most
one write is needed.)
## Godbolt
https://godbolt.org/z/673hae5xP
## Root cause
The loop runs exactly 16 iterations (22 ≤ i ≤ 37), a power-of-two count that
triggers **complete loop unrolling** (`LoopUnrollPass`). After unrolling, each
copy of the loop body contains fresh `movl g+76` / `movl g+72` instructions.
`LICM` should have hoisted these invariant loads **before** unrolling, or
`GVN`/`EarlyCSE` should eliminate the redundant copies **after** unrolling.
Neither pass fires, leaving 16× the required memory traffic.
Note: the bug reproduces at **both `-O2` and `-O3`** (both produce 16 static
loads for `g[19]` and `g[18]`). At `-O0`, there is only 1 static `movl g+76`
instruction (the loop is not unrolled, the load executes 16× dynamically but
is a single instruction). This confirms the regression is triggered by loop
unrolling at any optimization level that performs it, combined with LICM/GVN
failing to clean up the invariant loads post-unroll.
Contributor guide
Research direction
Start by compiling the provided C reproducer with Clang at -O2 and -O3 and inspect the generated x86 assembly. Trace LoopUnrollPass, then inspect LICM and GVN/EarlyCSE behavior before or after unrolling. Done means the redundant loads are eliminated, with the assembly showing no repeated invariant loads for g[19] and g[18].
Written by the indexing model from the issue text.
Assessment
- Tech stack
- c
- Domain
- compilers, performance
- Issue type
- Bug
- Difficulty
- 4/5
- Estimated time
- 3-5 days
- Activity status
- Quiet
- Clarity
- Mostly clear
- Newbie friendliness
- 48/100