[x86][AVX512] Missed vectorization of std::find_if with reverse iterators (rbegin/rend)
- 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
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