llvm / llvm/llvm-project

[InstCombine] Eliminate zexted i1 shuffle trees compared with zero

Open
#219,235 4 comments 0 reactions 0 assignees View on GitHub
llvm:instcombine llvm:transforms llvm:vectorcombine missed-optimization
Dominant language
LLVM
Stars
40.5k
Forks
18.7k
PR merge metrics
PR metrics pending

Description

Disclaimer: this is LLM generated because I am not too familiar with LLVM in general, though I believe the issue is real and it roughly makes sense to me. Happy to close this if there are any issues. Also happy to make a PR with a bit of guidance.

### Summary

LLVM retains an `i1 -> i8 -> i1` round trip after vectorizing a loop that fills and immediately packs a local Boolean array. LLVM removes the physical stack array, but the optimized form still materializes the byte values before converting them back into a mask.

The source came from [`vortex` PR #9626](https://github.com/vortex-data/vortex/pull/9626) and explicitly requests the byte representation:

```rust
let mut bools = [false; 64];
for (index, value) in bools.iter_mut().enumerate() {
*value = predicate(index);
}
let packed = pack(&bools);
```

The array is fixed-size, local, non-escaping, and immediately consumed by an inlined packer. Vortex uses this form to connect a generic Boolean producer to target-specific packing code.

For the AVX-512 `i32` case, LLVM produces:

```text
four <16 x i1> comparisons
-> four <16 x i8> zero extensions
-> one shuffled <64 x i8> value
-> compare with zero
-> one <64 x i1> result
```

The four comparison results already contain the 64 output bits. The expected code combines those masks and stores them directly with `kmovq`.

### Reproduction

Reproduced at LLVM `bd58db975ac08ffa81fe3680d899af5ccd208d6b` (2026-08-27). LLVM 22.1.8 produces the same result.

```console
cmake -G Ninja -S llvm-project/llvm -B llvm-project-build \
-DCMAKE_BUILD_TYPE=Release \
-DLLVM_ENABLE_ASSERTIONS=ON \
-DLLVM_TARGETS_TO_BUILD=X86
ninja -C llvm-project-build opt llc FileCheck

llvm-project-build/bin/opt -S -passes='default' repro.ll -o repro.opt.ll
llvm-project-build/bin/llc -O3 \
-mtriple=x86_64-unknown-linux-gnu \
-mattr=+avx512f,+avx512bw,+avx512vl \
repro.opt.ll -o repro.s
```

Self-contained reproducer and control

```llvm
target triple = "x86_64-unknown-linux-gnu"

define void @bad(ptr noalias %a, ptr noalias %b, ptr noalias %out) #0 {
entry:
%bytes = alloca [64 x i8], align 1
br label %loop

loop:
%index = phi i64 [ 0, %entry ], [ %next, %loop ]
%ap = getelementptr inbounds i32, ptr %a, i64 %index
%av = load i32, ptr %ap, align 4
%bp = getelementptr inbounds i32, ptr %b, i64 %index
%bv = load i32, ptr %bp, align 4
%predicate = icmp slt i32 %av, %bv
%byte = zext i1 %predicate to i8
%bytep = getelementptr inbounds i8, ptr %bytes, i64 %index
store i8 %byte, ptr %bytep, align 1
%next = add nuw nsw i64 %index, 1
%done = icmp eq i64 %next, 64
br i1 %done, label %exit, label %loop

exit:
%packed_bytes = load <64 x i8>, ptr %bytes, align 1
%mask = icmp ne <64 x i8> %packed_bytes, zeroinitializer
store <64 x i1> %mask, ptr %out, align 8
ret void
}

define void @good(ptr %a, ptr %b, ptr %out) #0 {
entry:
%a0 = load <16 x i32>, ptr %a, align 4
%a1p = getelementptr i8, ptr %a, i64 64
%a1 = load <16 x i32>, ptr %a1p, align 4
%a2p = getelementptr i8, ptr %a, i64 128
%a2 = load <16 x i32>, ptr %a2p, align 4
%a3p = getelementptr i8, ptr %a, i64 192
%a3 = load <16 x i32>, ptr %a3p, align 4
%b0 = load <16 x i32>, ptr %b, align 4
%b1p = getelementptr i8, ptr %b, i64 64
%b1 = load <16 x i32>, ptr %b1p, align 4
%b2p = getelementptr i8, ptr %b, i64 128
%b2 = load <16 x i32>, ptr %b2p, align 4
%b3p = getelementptr i8, ptr %b, i64 192
%b3 = load <16 x i32>, ptr %b3p, align 4
%p0 = icmp slt <16 x i32> %a0, %b0
%p1 = icmp slt <16 x i32> %a1, %b1
%p2 = icmp slt <16 x i32> %a2, %b2
%p3 = icmp slt <16 x i32> %a3, %b3
%lo = shufflevector <16 x i1> %p0, <16 x i1> %p1, <32 x i32>
%hi = shufflevector <16 x i1> %p2, <16 x i1> %p3, <32 x i32>
%mask = shufflevector <32 x i1> %lo, <32 x i1> %hi, <64 x i32>
store <64 x i1> %mask, ptr %out, align 8
ret void
}

attributes #0 = { "target-features"="+avx512f,+avx512bw,+avx512vl" }
```

### Result

After `default`, the stack allocation is gone, but the optimized LLVM form still contains:

```llvm
%10 = zext <16 x i1> %6 to <16 x i8>
%11 = zext <16 x i1> %7 to <16 x i8>
%12 = zext <16 x i1> %8 to <16 x i8>
%13 = zext <16 x i1> %9 to <16 x i8>
; Three shuffles concatenate these into <64 x i8>.
%mask = icmp ne <64 x i8> %bytes, zeroinitializer
store <64 x i1> %mask, ptr %out, align 8
```

The generated code has already combined the four comparison masks before it materializes the Boolean bytes:

```asm
# Current tail
kunpckdq %k0, %k1, %k1
vpbroadcastq .LCPI0_0(%rip), %zmm0
vmovdqu8 %zmm0, %zmm0 {%k1} {z}
vptestmb %zmm0, %zmm0, %k0
kmovq %k0, (%rdx)

# Direct <64 x i1> control
kunpckdq %k0, %k1, %k0
kmovq %k0, (%rdx)
```

Full current and control assembly

```asm
bad:
vmovdqu64 (%rsi), %zmm0
vmovdqu64 64(%rsi), %zmm1
vmovdqu64 128(%rsi), %zmm2
vmovdqu64 192(%rsi), %zmm3
vpcmpgtd (%rdi), %zmm0, %k0
vpcmpgtd 64(%rdi), %zmm1, %k1
vpcmpgtd 128(%rdi), %zmm2, %k2
vpcmpgtd 192(%rdi), %zmm3, %k3
kunpckwd %k0, %k1, %k0
kunpckwd %k2, %k3, %k1
kunpckdq %k0, %k1, %k1
vpbroadcastq .LCPI0_0(%rip), %zmm0
vmovdqu8 %zmm0, %zmm0 {%k1} {z}
vptestmb %zmm0, %zmm0, %k0
kmovq %k0, (%rdx)

good:
vmovdqu64 (%rsi), %zmm0
vmovdqu64 64(%rsi), %zmm1
vmovdqu64 128(%rsi), %zmm2
vmovdqu64 192(%rsi), %zmm3
vpcmpgtd (%rdi), %zmm0, %k0
vpcmpgtd 64(%rdi), %zmm1, %k1
kunpckwd %k0, %k1, %k0
vpcmpgtd 128(%rdi), %zmm2, %k1
vpcmpgtd 192(%rdi), %zmm3, %k2
kunpckwd %k1, %k2, %k1
kunpckdq %k0, %k1, %k0
kmovq %k0, (%rdx)
```

### Analysis

Scalar Replacement of Aggregates removes the stack allocation late in the `default` pipeline, after VectorCombine has already run. An additional `vector-combine,instcombine` produces the direct `<64 x i1>` form.

The remaining opportunity is target-independent. The X86 backend already lowers the direct form to mask-unpack instructions followed by `kmovq`.

Contributor guide

Open the contributing guide

Research direction

Start with the self-contained repro.ll and run the provided opt and llc commands for the default O3 pipeline, then compare them with the additional vector-combine and instcombine passes described. Done means the optimized form eliminates the zext and byte shuffle tree for this case and produces the direct <64 x i1> result with the corresponding efficient assembly.

Written by the indexing model from the issue text.

Assessment

Tech stack
rust
Domain
compilers, performance
Issue type
Bug
Difficulty
4/5
Estimated time
3-5 days
Activity status
Active
Clarity
Mostly clear
Newbie friendliness
50/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.