[CVP] `urem`/`udiv` by a constant is not expanded when the operand's range is only reachable through a splat
- Dominant language
- LLVM
- Stars
- 40.5k
- Forks
- 18.7k
- PR merge metrics
- PR metrics pending
Description
`CorrelatedValuePropagation` expands `urem X, C` into `select (X u< C), X, X - C` and `udiv X, C` into `zext (X u>= C)` once it can prove `X < 2 * C`, for vectors as well as scalars. The range query behind it cannot see through a splat, and InstCombine canonicalizes a masked splat into exactly that shape, so in a normal pipeline the fold never happens for vectors.
One function, two pass pipelines, opposite results:
```llvm
target triple = "x86_64-unknown-linux-gnu"
define <16 x i16> @masked_splat(i16 %a, <16 x i16> %b) {
%ins = insertelement <16 x i16> poison, i16 %a, i64 0
%splat = shufflevector <16 x i16> %ins, <16 x i16> poison, <16 x i32> zeroinitializer
%am = and <16 x i16> %splat, splat (i16 63)
%bm = and <16 x i16> %b, splat (i16 63)
%sum = add nuw nsw <16 x i16> %am, %bm
%rem = urem <16 x i16> %sum, splat (i16 119)
ret <16 x i16> %rem
}
```
```console
$ opt -passes='correlated-propagation' -S canon.ll
%rem.urem = sub nuw <16 x i16> %sum.frozen, splat (i16 119)
%rem.cmp = icmp ult <16 x i16> %sum.frozen, splat (i16 119)
%rem = select <16 x i1> %rem.cmp, <16 x i16> %sum.frozen, <16 x i16> %rem.urem
$ opt -passes='instcombine,correlated-propagation' -S canon.ll
%rem = urem <16 x i16> %sum, splat (i16 119)
```
InstCombine pulls the `and` through the splat shuffle, which is reasonable on its own since it narrows the binop to the pre-splat vector:
```llvm
%ins = insertelement <16 x i16> poison, i16 %a, i64 0
%1 = and <16 x i16> %ins,
%am = shufflevector <16 x i16> %1, <16 x i16> poison, <16 x i32> zeroinitializer
```
but it leaves the operand's bound on the far side of the shuffle, where CVP no longer finds it.
Since this is the canonical form, there is no way to write the source so that the fold survives.
`udiv` behaves identically in the same two pipelines: `zext <16 x i1> (icmp uge %sum, 119)` on its own, `udiv <16 x i16> %sum, splat (i16 119)` after InstCombine.
Interestingly CVP does annotate the unexpanded functions with a return range (`range(i16 0, 119)` for the `urem`, `range(i16 0, 551)` for the `udiv`), so the range of the result is computed while the range of the operand at the divide is not.
The cost, after `llc -mcpu=x86-64-v3`, is that the whole dependency chain becomes a reciprocal multiply:
```asm
opt -O3 opt -passes=correlated-propagation | opt -O3
vmovd %edi, %xmm1 vmovd %edi, %xmm1
vpand .LCPI0_0(%rip), %ymm0, %ymm0 vpbroadcastw %xmm1, %ymm1
vpbroadcastw %xmm1, %ymm1 vpand .LCPI0_0(%rip), %ymm0, %ymm0
vpaddw %ymm0, %ymm1, %ymm0 vpaddw %ymm0, %ymm1, %ymm0
vpmulhuw .LCPI0_1(%rip), %ymm0, %ymm1 vpaddw .LCPI0_1(%rip), %ymm0, %ymm1
vpmullw .LCPI0_2(%rip), %ymm1, %ymm1 vpminuw %ymm1, %ymm0, %ymm0
vpsubw %ymm1, %ymm0, %ymm0 retq
retq
```
`vpmulhuw` → `vpmullw` → `vpsubw` is ~11 cycles of latency on two multiply uops that contend for the same port, against ~2 for `vpaddw` → `vpminuw`.
Reproduced with LLVM 23.1.1 (official Linux-X64 release).
## Where this comes from
Modular arithmetic on `u16x16` lanes, where every operand is a sum of two values below the modulus, so the modulo is a single conditional subtraction:
```rust
fn add_mod(a: Simd, b: Simd, modulus: Simd) -> Simd {
(a + b) % modulus
}
```
The scalar equivalent is folded, because LVI picks the range up from `llvm.assume` or from the enclosing branch. The vector one is not, at any optimization level or target CPU, so the conditional subtraction has to be written out by hand.
## Likely cause (LLM-generated)
`LazyValueInfoImpl::solveBlockValueImpl` has cases for binary operators, casts, selects, PHIs and a few intrinsics, but none for `insertelement`/`shufflevector`, so a splat is overdefined. That fits the behaviour above exactly: before InstCombine runs, `and <16 x i16> %splat, splat (i16 63)` gives LVI a range because the `and` is a binary operator it understands; afterwards the `and` sits on the other side of the shuffle and nothing does.
`computeKnownBits` has no such gap — in the canonicalized shape `(%am + %bm) u>> 7` still folds to a constant zero, so the low-bits fact does survive the splat and only the range query loses it.
A splat looks like the cheapest case to teach LVI about, since the per-lane range is exactly the scalar's range and no element-wise reasoning is involved. The general vector case is a lot harder: there is no way to state "every lane of `%v` is `u< C`" in IR, an `llvm.assume` can only carry the all-lanes reduction of a vector predicate, and nothing decomposes that back into per-lane facts.
Contributor guide
Research direction
Reproduce the difference with the two opt pipelines and inspect LazyValueInfoImpl::solveBlockValueImpl, especially its handling of insertelement and shufflevector. Trace the masked-splat range query for the urem and udiv examples; done means correlated-propagation expands both operations after InstCombine without losing the per-lane bound.
Written by the indexing model from the issue text.
Assessment
- Domain
- compilers
- Issue type
- Bug
- Difficulty
- 4/5
- Estimated time
- 3-5 days
- Activity status
- Active
- Clarity
- Mostly clear
- Newbie friendliness
- 50/100