Issue 241477
Summary [LoopVectorize] `or` reduction of abs(sub(sext, sext)) vectorized as `partial.reduce.add` on x86 AVX2
Labels new issue
Assignees
Reporter arie2026
    On x86-64 with AVX2, LoopVectorize turns an **`or`** reduction whose operand is `abs(sub(sext a, sext b))` into
`llvm.vector.partial.reduce.add`, i.e. it adds the values instead of or-ing them. The middle block then or-reduces
the partial sums. The result is wrong, also at `-O2`.

Reproducer (`opt -mtriple=x86_64-unknown-linux-gnu -mattr=+avx2 -passes=loop-vectorize -S f.ll`, tested on 9dce18f0e; also reproduces on 5e457cda8d5a):
```llvm
define i64 @f(ptr %x, ptr %y) {
entry:
  br label %for.body
for.body:
  %iv = phi i64 [ 0, %entry ], [ %iv.next, %for.body ]
  %sum.0 = phi i64 [ 0, %entry ], [ %sum.1, %for.body ]
  %gx = getelementptr i32, ptr %x, i64 %iv
  %gy = getelementptr i32, ptr %y, i64 %iv
  %lx = load i32, ptr %gx
  %ly = load i32, ptr %gy
  %ext.x = sext i32 %lx to i64
  %ext.y = sext i32 %ly to i64
  %sub = sub i64 %ext.x, %ext.y
  %abs.diff = tail call i64 @llvm.abs.i64(i64 %sub, i1 false)
 %sum.1 = or i64 %abs.diff, %sum.0
  %iv.next = add i64 %iv, 1
 %exitcond.not = icmp eq i64 %iv, 8000
  br i1 %exitcond.not, label %exit, label %for.body
exit:
  ret i64 %sum.1
}
declare i64 @llvm.abs.i64(i64, i1 immarg)
```

```
$ opt -mtriple=x86_64-unknown-linux-gnu -mattr=+avx2 -passes=loop-vectorize -S f.ll
vector.body:  ; 4 interleaved parts like this one
  %partial.reduce = call <2 x i64> @llvm.vector.partial.reduce.add.v2i64.v4i64(<2 x i64> %vec.phi, <4 x i64> %28)
middle.block:
  %33 = call i64 @llvm.vector.reduce.or.v2i64(<2 x i64> %bin.rdx15)   ; after `or` of the 4 parts
```

Why this is wrong: with `x[i] = 1` and `y[i] = 0` for all 8001 iterations, every `%abs.diff` is 1, so the `or`
reduction is `1`. The vectorized loop adds the 1s per lane (1000 per lane) and then ORs the lanes and the scalar
tail, which gives `0x3e9`. Driver (`main.ll`):
```llvm
@X = global [8001 x i32] zeroinitializer
@Y = global [8001 x i32] zeroinitializer
@fmt = private constant [6 x i8] c"%llx\0A\00"
declare i64 @f(ptr, ptr)
declare i32 @printf(ptr, ...)
define i32 @main() {
entry:
  br label %l
l:
  %i = phi i64 [0, %entry], [%in, %l]
  %px = getelementptr i32, ptr @X, i64 %i
  %py = getelementptr i32, ptr @Y, i64 %i
  store i32 1, ptr %px
  store i32 0, ptr %py
  %in = add i64 %i, 1
  %c = icmp eq i64 %in, 8001
  br i1 %c, label %d, label %l
d:
  %r = call i64 @f(ptr @X, ptr @Y)
  call i32 (ptr, ...) @printf(ptr @fmt, i64 %r)
  ret i32 0
}
```
```
$ llvm-link f.ll main.ll -S -o s.ll && lli s.ll                       # 1
$ opt -mtriple=x86_64-unknown-linux-gnu -mattr=+avx2 -passes=loop-vectorize -S f.ll -o v.ll
$ llvm-link v.ll main.ll -S -o t.ll && lli t.ll # 3e9
$ opt -mtriple=x86_64-unknown-linux-gnu -mattr=+avx2 -passes='default<O2>' -S f.ll -o o2.ll
$ llvm-link o2.ll main.ll -S -o t2.ll && lli t2.ll                    # 3e9
```

Expected: `1` (an `or` reduction is never turned into an add-based partial reduction).

Notes (hedged): `getScaledReductionChain` (VPlanTransforms.cpp) doesn't seem to reject non-add recurrence kinds, and
the partial reduction is always built as an add. AArch64's `getPartialReductionCost` rejects such opcodes, but the
x86/BasicTTI cost hook accepts them. `xor`/`and` reductions are also converted, though this input gives equal
results for them.

Found by hand while minimizing a crash reported by a mutation-based IR fuzzer. Triage, test-case minimization and parts of this write-up were
assisted by an LLM; verified the reproducer on 9dce18f0e.

Assisted-by: Claude (Anthropic)
_______________________________________________
llvm-bugs mailing list
[email protected]
https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-bugs

Reply via email to