llvm / llvm/llvm-project

Missing fold triangle+diamond conditional stores to select+store optimization

Open
#207,651 0 comments 0 reactions 1 assignee Claimed by @kartcq View on GitHub
llvm:optimizations missed-optimization
Dominant language
LLVM
Stars
40.5k
Forks
18.7k
PR merge metrics
PR metrics pending

Description

SimplifyCFG does not fold a triangle+diamond CFG pattern where multiple branches unconditionally store to the same address. The pattern arises commonly in loops with cascaded range checks.

Motivating Example:

```
#include
void threshold_range(
const uint8_t* __restrict__ src,
uint8_t* __restrict__ dst,
uint32_t n,
uint8_t lo, uint8_t hi)
{
for (uint32_t i = 0; i < n; ++i)
{
if (src[i] < lo)
dst[i] = 0;
else if (src[i] > hi)
dst[i] = 0;
else
dst[i] = 0xFF;
}
}
```

At -O2, the inner loop compiles to the following CFG structure:

```
HeadBB: br i1 %cmp.lt, label %then, label %else
then: store i8 0, ptr %dst.i → merge
else: br i1 %cmp.gt, label %else.then, label %else.else
else.then: store i8 0, ptr %dst.i → merge
else.else: store i8 0xFF, ptr %dst.i → merge
```

This prevents the loop vectorizer from handling the loop body as a single basic block, resulting in scalar code.
The semantically-equivalent form
`dst[i] = (v >= lo && v <= hi) ? 0xFF : 0 `
produces a single-block loop body that vectorizes cleanly.

Proposed Transform

Fold the triangle+diamond pattern into:
```
HeadBB:
%sel = select i1 %combined.cond, i8 %v1, i8 %v2
store i8 %sel, ptr %dst.i
br label %merge
```

This enables vectorization and eliminates branches in the inner loop.
I am working on a patch for this and will put it up for review shortly.

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.