Repository navigation
[InstCombine] Eliminate zexted i1 shuffle trees compared with zero #219235
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 and explicitly requests the byte representation:
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:
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.
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<O3>' 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.sSelf-contained reproducer and control
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> <i32 0, i32 1, i32 2, i32 3, i32 4, i32 5, i32 6, i32 7, i32 8, i32 9, i32 10, i32 11, i32 12, i32 13, i32 14, i32 15, i32 16, i32 17, i32 18, i32 19, i32 20, i32 21, i32 22, i32 23, i32 24, i32 25, i32 26, i32 27, i32 28, i32 29, i32 30, i32 31>
%hi = shufflevector <16 x i1> %p2, <16 x i1> %p3, <32 x i32> <i32 0, i32 1, i32 2, i32 3, i32 4, i32 5, i32 6, i32 7, i32 8, i32 9, i32 10, i32 11, i32 12, i32 13, i32 14, i32 15, i32 16, i32 17, i32 18, i32 19, i32 20, i32 21, i32 22, i32 23, i32 24, i32 25, i32 26, i32 27, i32 28, i32 29, i32 30, i32 31>
%mask = shufflevector <32 x i1> %lo, <32 x i1> %hi, <64 x i32> <i32 0, i32 1, i32 2, i32 3, i32 4, i32 5, i32 6, i32 7, i32 8, i32 9, i32 10, i32 11, i32 12, i32 13, i32 14, i32 15, i32 16, i32 17, i32 18, i32 19, i32 20, i32 21, i32 22, i32 23, i32 24, i32 25, i32 26, i32 27, i32 28, i32 29, i32 30, i32 31, i32 32, i32 33, i32 34, i32 35, i32 36, i32 37, i32 38, i32 39, i32 40, i32 41, i32 42, i32 43, i32 44, i32 45, i32 46, i32 47, i32 48, i32 49, i32 50, i32 51, i32 52, i32 53, i32 54, i32 55, i32 56, i32 57, i32 58, i32 59, i32 60, i32 61, i32 62, i32 63>
store <64 x i1> %mask, ptr %out, align 8
ret void
}
attributes #0 = { "target-features"="+avx512f,+avx512bw,+avx512vl" }Result
After default<O3>, the stack allocation is gone, but the optimized LLVM form still contains:
%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 8The generated code has already combined the four comparison masks before it materializes the Boolean bytes:
# 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
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<O3> 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.
Activity
RKSimon commentedon Aug 27, 2026
SROA is folding this very late, otherwise vectorcombine would have handled it for us
[-][InstCombine] Eliminate zexted i1 shuffle trees compared with zero[/-][+][Transforms] Eliminate zexted i1 shuffle trees compared with zero[/+]connortsui20 commentedon Aug 27, 2026
My understanding is that the simplification needed is roughly
concatenate(zero_extend(a), zero_extend(b))->zero_extend(concatenate(a, b)), but the complication is around where this can happen.The LLM told me (could be wrong) that vector-combine already does this optimization, but because scalar replacement happens after vector-combine it won't reapply that optimization without another pass.
Would handling this in
InstCombinebe a reasonable direction? There is already related cast-and-shuffle canonicalization there, and apparently extending it fixes this reproduce. I think I can open a PR that does this small change.Edit: Or I could just add a tree matcher that finds the concat(zext); mask pattern and removes the extra steps?
[-][Transforms] Eliminate zexted i1 shuffle trees compared with zero[/-][+][InstCombine] Eliminate zexted i1 shuffle trees compared with zero[/+]connortsui20 commentedon Aug 27, 2026
I opened #219296, I believe it should solve this.
connortsui20 commentedon Aug 28, 2026
Apparently #184182 also solves this?
Pack Boolean RowFn output directly (#9626)
Clarify Boolean collection code generation (#9676)