llvm / llvm/llvm-project

[X86][LICM/GVN] Loop-invariant loads not hoisted after full loop unrolling

Open
#205,979 2 comments 0 reactions 0 assignees View on GitHub
llvm:GVN missed-optimization
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

Open the contributing 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.