[X86] 8-bit vector multiplication should use shift and add method for more constants

[WalterKruger]

Vector multiplication by most 8-bit constants is currently implemented by a width extension to 16-bits:

multiplyBy10_clang:
        movdqa  xmm1, xmm0
        punpckhbw       xmm1, xmm1
        movdqa  xmm2, xmmword ptr [rip + .LCPI0_0]
        pmullw  xmm1, xmm2
        movdqa  xmm3, xmmword ptr [rip + .LCPI0_1]
        pand    xmm1, xmm3
        punpcklbw       xmm0, xmm0
        pmullw  xmm0, xmm2
        pand    xmm0, xmm3
        packuswb        xmm0, xmm1
        ret

However, it is often more efficient to instead perform a short sequence of shift-and-adds both in terms of size and dependency length. For example, x * 10 = (x << 3) + (x << 1):

multiplyBy10_shiftAndAdd:
        movdqa  xmm1, xmm0
        paddb   xmm0, xmm0
        psllw   xmm1, 3
        pand    xmm1, xmmword ptr [rip + .LCPI0_0]
        paddb   xmm0, xmm1
        ret

This method is currently implemented, but only for constants that are almost powers of two. Notably, gcc always use this method (although its sequences are often non-optimal).

https://godbolt.org/z/naKxr6z6a

[llvmbot]

@llvm/issue-subscribers-backend-x86

Author: Walter (WalterKruger)

Vector multiplication by most 8-bit constants is currently implemented by a width extension to 16-bits: ```asm multiplyBy10_clang: movdqa xmm1, xmm0 punpckhbw xmm1, xmm1 movdqa xmm2, xmmword ptr [rip + .LCPI0_0] pmullw xmm1, xmm2 movdqa xmm3, xmmword ptr [rip + .LCPI0_1] pand xmm1, xmm3 punpcklbw xmm0, xmm0 pmullw xmm0, xmm2 pand xmm0, xmm3 packuswb xmm0, xmm1 ret ```

However, it is often more efficient to instead perform a short sequence of shift-and-adds both in terms of size and dependency length. For example, x * 10 = (x << 3) + (x << 1):

multiplyBy10_shiftAndAdd:
        movdqa  xmm1, xmm0
        paddb   xmm0, xmm0
        psllw   xmm1, 3
        pand    xmm1, xmmword ptr [rip + .LCPI0_0]
        paddb   xmm0, xmm1
        ret

This method is currently implemented, but only for constants that are almost powers of two. Notably, gcc always use this method (although its sequences are often non-optimal).

https://godbolt.org/z/naKxr6z6a

[llvmbot]

Hi!

This issue may be a good introductory issue for people new to working on LLVM. If you would like to work on this issue, your first steps are:

1. Check that no other contributor is working on this issue. If someone is assigned to the issue or claimed to be working on it, ping the person. After one week without a response, the assignee may be changed.
2. Leave a comment indicating that you are working on the issue, or just create a pull request after following the steps below. Mention this issue in the description of the pull request.
3. Fix the issue locally.
4. Run the test suite locally. Remember that the subdirectories under test/ create fine-grained testing targets, so you can e.g. use make check-clang-ast to only run Clang's AST tests.
5. Create a Git commit.
6. Run git clang-format HEAD~1 to format your changes.
7. Open a pull request to the upstream repository on GitHub. Detailed instructions can be found in GitHub's documentation. Mention this issue in the description of the pull request.

If you have any further questions about this issue, don't hesitate to ask via a comment in the thread below.

[llvmbot]

@llvm/issue-subscribers-good-first-issue

Author: Walter (WalterKruger)

Vector multiplication by most 8-bit constants is currently implemented by a width extension to 16-bits: ```asm multiplyBy10_clang: movdqa xmm1, xmm0 punpckhbw xmm1, xmm1 movdqa xmm2, xmmword ptr [rip + .LCPI0_0] pmullw xmm1, xmm2 movdqa xmm3, xmmword ptr [rip + .LCPI0_1] pand xmm1, xmm3 punpcklbw xmm0, xmm0 pmullw xmm0, xmm2 pand xmm0, xmm3 packuswb xmm0, xmm1 ret ```

However, it is often more efficient to instead perform a short sequence of shift-and-adds both in terms of size and dependency length. For example, x * 10 = (x << 3) + (x << 1):

multiplyBy10_shiftAndAdd:
        movdqa  xmm1, xmm0
        paddb   xmm0, xmm0
        psllw   xmm1, 3
        pand    xmm1, xmmword ptr [rip + .LCPI0_0]
        paddb   xmm0, xmm1
        ret

This method is currently implemented, but only for constants that are almost powers of two. Notably, gcc always use this method (although its sequences are often non-optimal).

https://godbolt.org/z/naKxr6z6a

[RKSimon]

We can probably profitably relax this to include splat multiplies of vXi8 types by any splat constant decomposable into a max of TWO pow2 constants.

This involves minor adjustments to X86TargetLowering::decomposeMulByConstant to special case vXi8 vector types along with any additional test cases we need.

[zheguang]

Hi! I'd like to work on this issue.

[grodranlorth]

Hi @zheguang , are you working on this issue? If not I'd like to take a crack at it. Thanks!

[zheguang]

@grodranlorth sure, go for it! :) (I've been side-tracked quite a bit this month. Hope to get back to LLVM next month or so.)

[grodranlorth]

Hello. After some investigation, I want to make sure I understand the task so I do the right thing. I understand that this is an optimization for x86 microarchitectures from roughly 2015 to 2018 -- is that correct?

LLVM already has the optimization to use shift+add/sub instead of pmull for vXi8 splat multiplies (prior PR) implemented which I see in the asm of my benchmark (though I understand it doesn't support negative constants of the form $x = 2^a \pm 2^b$)). At that time, we decided to enable this optimization only for microarchitectures that have the the TuningFastImmVectorShift tuning flag, i.e. those since about 2015. Additionally, LLVM has an optimization to prefer GFNI for these multiplies (roughly microarchitectures since 2018), which is even faster than shift+add/sub according to my benchmark.

Thus I want to clarify, what is the ask in this PR?

• Enabling the shift+add/sub optimization regardless of TuningFastImmVectorShift?
• Adding more constants (negative, at least) to the existing shift+add/sub optimization?
• Something else?

cc: @WalterKruger @RKSimon

[WalterKruger]

The assembly snippet is for a baseline x86-64-v1 target but it seems like it is beneficial for all targets, at least without avx512, due to how long the chain is (splat => mul16 => pand => packuswb), even if both halves can be calculated at once with a wider vector.

though I understand it doesn't support negative constants of the form $x = 2^a ± 2^b$

I have only seen shift+add/sub be emitted for constants the are either exact powers of 2 or one off (i.e. $x = 2^n ± 1$). For example, the "negative" constant 7 is implemented as (x << 3) - x.

Additionally, LLVM has an optimization to prefer GFNI for these multiplies... which is even faster than shift+add/sub according to my benchmark.

vgf2p8affineqb is useful only as a more efficient way to implement bitshifts, as prior targets have emulate them using a 16-bit shift + AND to mask bits that cross a 8-bit lane.