Missing fold triangle+diamond conditional stores to select+store 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
Assessment
This issue has not been assessed yet.