Suboptimal code generation for vectorized version of llvm.ctlz() for int64 on x86-64

[aneshlya]

LLVM generates suboptimal code for llvm.ctlz() on the int64 type across various x86-64 instruction sets (SSE4–AVX2) before AVX512. Performance measurements indicate that extracting individual 64-bit values from the ymm register and applying lzcnt separately to each yields a 25% improvement on AVX2 and a 124% improvement on SSE4, compared to llvm.ctlz vectorized implementation.

Please see the example here: https://ispc.godbolt.org/z/EEErrednx

[llvmbot]

@llvm/issue-subscribers-backend-x86

Author: None (aneshlya)

LLVM generates suboptimal code for `llvm.ctlz()` on the int64 type across various x86-64 instruction sets (SSE4–AVX2) before AVX512. Performance measurements indicate that extracting individual 64-bit values from the `ymm` register and applying `lzcnt` separately to each yields a 25% improvement on AVX2 and a 124% improvement on SSE4, compared to `llvm.ctlz` vectorized implementation.

Please see the example here: https://ispc.godbolt.org/z/EEErrednx

[RKSimon]

Only AVX2 capable targets should be vectorizing ctlz codegen at this stage, and its a very close thing wrt cost numbers - where are you seeing SSE4/AVX1 vectors being generated?

We try very hard not to make vectorization/scalarization decisions at codegen - so if the middleend has created a vectorized ctlz the DAG will try to respect it.

[aneshlya]

I'm calling llvm.ctlz() intrinsic from ISPC code directly: https://godbolt.org/z/787P8zTcG and comparing with ISPC generic implementation. BTW For int32 types llvm.ctlz performs much better: https://godbolt.org/z/qqzjEcbhG.

We try very hard not to make vectorization/scalarization decisions at codegen - so if the middleend has created a vectorized ctlz the DAG will try to respect it.

This totally makes sense.

[RKSimon]

@aneshlya Is there anything more you're expecting llvm to do here?

[dzaima]

I have no horse in this race, but it looks like whatever opt pipeline llvm IR via clang goes through (same with opt) replaces the manually-scalarized version with the @llvm.ctlz.v8i64 anyways.

If I understand the original report correctly (and it seems plausible given the assembly), the scalarized version is faster even with the overhead of moving from & to vector registers; of course rather pointless if doing just a ctlz, but in a larger program it might be reasonable to do most of it in vector registers, and utilize scalarized ctlz, which the opt pipeline vectorizes to the slower form.

[RKSimon]

Scalars: 
    %extract.i.i.i = extractelement <8 x i64> %v, i64 0
    %extract.i.i.i.1 = extractelement <8 x i64> %v, i64 1
    %extract.i.i.i.2 = extractelement <8 x i64> %v, i64 2
    %extract.i.i.i.3 = extractelement <8 x i64> %v, i64 3
    %extract.i.i.i.4 = extractelement <8 x i64> %v, i64 4
    %extract.i.i.i.5 = extractelement <8 x i64> %v, i64 5
    %extract.i.i.i.6 = extractelement <8 x i64> %v, i64 6
    %extract.i.i.i.7 = extractelement <8 x i64> %v, i64 7
State: Vectorize
MainOp:   %extract.i.i.i = extractelement <8 x i64> %v, i64 0
AltOp:   %extract.i.i.i = extractelement <8 x i64> %v, i64 0
VectorizedValue: NULL
ReuseShuffleIndices: Empty
ReorderIndices: 
UserTreeIndices: {User:1 EdgeIdx:0}, 
SLP: Costs:
SLP:     ReuseShuffleCost = 0
SLP:     VectorCost = 0
SLP:     ScalarCost = 12
SLP:     ReuseShuffleCost + VecCost - ScalarCost = -12
SLP: Adding cost -12 for bundle Idx: 2, n=8 [  %extract.i.i.i = extractelement <8 x i64> %v, i64 0, ..].
SLP: Current total cost = -2

https://zig.godbolt.org/z/T7WaTY1cc - it looks like SLP is costing the extractelements separately (cost=1 for lowest 128-bit, cost=2 for upper elements) instead of using getScalarizationOverhead which should give a cost of 9 (1 per extract + 1 extract_subvector)

CC @alexey-bataev

[alexey-bataev]

Fixed it here #125725

[alexey-bataev]

Landed here 88e7b8b