llvm / llvm/llvm-project

[SCEV][LoopVectorize] Missed vectorization when trip count involves zext

Open
#208,778 0 comments 0 reactions 1 assignee Claimed by @aleks-tmb View on GitHub
llvm:SCEV missed-optimization
Dominant language
LLVM
Stars
40.5k
Forks
18.7k
PR merge metrics
PR metrics pending

Description

Here are 2 reduced examples of missed vectorization because SCEV cannot prove loop deref safety: https://godbolt.org/z/TfKMe7vd8

A required condition for vectorization is proving that the accessed pointers are dereferenceable and properly aligned inside the loop (see `llvm::isDereferenceableAndAlignedInLoop`). When the deref size is known from an `llvm.assume`, the access size must be proven to be `ULE` to the known deref size.

- In the first case

```c
assume(dereferenceable(p, zext(len + 8)));
if (len > 0)
for (u64 i = 0; i <= zext(len - 1); ++i)
if (p[8 + i] == 0) return;
```

LAA needs to prove: `AccessSize <=u KnownDerefSize`. After applying loop guards, the SCEV expressions are:

```
AccessSizeSCEV:
(9 + (zext i32 (-1 + (1 umax %len)) to i64))
KnownSizeSCEV:
(8 + (1 umax (zext i32 %len to i64)))
```

**SCEV doesn't move the -1 outside the zext**, which would allow it to fold with the outer 9 and make AccessSizeSCEV equal to KnownSizeSCEV.
Without this transformation, SCEV can't prove the predicate. After the fold, the predicate becomes trivially true.

- In the second case:

```c
assume(dereferenceable(p, zext(len + 8)));
if (len > 0) {
u64 exit = zext(umin(A, len - 1));
if (exit > 1)
for (u64 i = 0; i <= exit; ++i)
if (p[8 + i] == 0) return;
}
```

After applying loop guards, the SCEV expressions are:

```
AccessSizeSCEV:
(9 + ((2 umax (zext i32 (-1 + %len) to i64)) umin (2 umax (zext i32 %A to i64))))
KnownSizeSCEV:
(8 + (1 umax (zext i32 %len to i64)))
```

This case exposes a second issue in addition to SCEV not moving the -1 outside the zext. **The two SCEV expressions use different inferred ranges for `%len`**, which prevents SCEV from proving the ULE predicate.

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.