llvm / llvm/llvm-project

[x86][AVX512] Missed vectorization of std::find_if with reverse iterators (rbegin/rend)

Open
#206,006 3 comments 4 reactions 0 assignees View on GitHub
loopoptim missed-optimization vectorizers
Dominant language
LLVM
Stars
40.5k
Forks
18.7k
PR merge metrics
PR metrics pending

Description

### Description

Clang fails to vectorize `std::find_if` when searching backwards using reverse iterators (`rbegin()` / `rend()`). While GCC generates vectorized AVX-512 code that checks 64 bytes per iteration using mask registers, Clang generates a scalar byte-by-byte comparison loop.

This issue impacts performance in search operations over contiguous memory buffers (e.g., finding trailing non-zero elements or padding in buffers).

---

### Code Example

```cpp
#include
#include

auto find_last_non_zero(const std::vector& input) {
return std::find_if(input.rbegin(), input.rend(), [](const int8_t& in) {
return in != 0;
});
}

```

**Flags:** `-O3 -mavx512bw -mavx512vbmi` (or `-march=znver5`)

**Godbolt:** https://godbolt.org/z/GEs8a1nhc

---

### Assembly Comparison

#### GCC (AVX-512 Vectorized)

GCC processes **64 bytes per iteration** using byte permutation and vector mask tests:

```assembly
.Lloop:
vpermb zmm0, zmm2, ZMMWORD PTR [r8+rax] ; Reverse/permute 64-byte chunk
vpcmpb k0, zmm0, zmm1, 4 ; Compare 64 bytes against 0 into mask register k0
kortestq k0, k0 ; Test if any non-zero element was found
je .L7 ; Continue loop if all zero

```

#### Clang (Scalar Loop)

Clang fails to vectorize the reverse traversal and emits a scalar loop (unrolled x4 due to `libstdc++` internal pragmas):

```assembly
.LBB0_2:
cmp byte ptr [rbp + r12 - 1], 0 ; Compare scalar byte 1
jne .LBB0_found
cmp rdx, rsi
je .LBB0_end
cmp byte ptr [rbp + r12 - 2], 0 ; Compare scalar byte 2
jne .LBB0_found
cmp rcx, rsi
je .LBB0_end
cmp byte ptr [rbp + r12 - 3], 0 ; Compare scalar byte 3
jne .LBB0_found
cmp rax, rsi
je .LBB0_end
cmp byte ptr [rbp + r12 - 4], 0 ; Compare scalar byte 4
jne .LBB0_found

```

With `-Rpass=loop-vectorize -Rpass-missed=loop-vectorize -Rpass-analysis=loop-vectorize`, clang outputs "**remark: loop not vectorized: Cannot vectorize early exit loop with strided fault-only-first load**"

---

### Expected Behavior

Clang's Loop Vectorizer pass should recognize backward pointer arithmetic/reverse iterator patterns and vectorize contiguous memory checks using AVX-512 / AVX2 instructions, matching GCC's throughput.

Contributor guide

Open the contributing guide

Research direction

Reproduce the reverse-iterator std::find_if example with -O3 -mavx512bw -mavx512vbmi, and compare the generated code with the linked Godbolt case. Start with the Loop Vectorizer diagnostics, especially the early-exit and strided fault-only-first load remark. Done means Clang vectorizes the contiguous backward search with suitable AVX-512 or AVX2 code while preserving the result and early-exit behavior.

Written by the indexing model from the issue text.

Assessment

Tech stack
cpp
Domain
compilers, performance
Issue type
Bug
Difficulty
5/5
Estimated time
Over a week
Activity status
Active
Clarity
Mostly clear
Newbie friendliness
45/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.