[llvm-dev] [RFC] carry-less multiplication instruction

[James Y Knight via llvm-dev]

"Carry-less multiplication" isn't a wider bit width multiplication, it's an
entirely different operation. (See the Wikipedia page linked in the
proposal).

On Sun, Jul 5, 2020, 4:07 PM Chris Lattner via llvm-dev <
llvm-dev at lists.llvm.org> wrote:

>
>
> On Jul 5, 2020, at 5:12 AM, Nicolai Hähnle via llvm-dev <
> llvm-dev at lists.llvm.org> wrote:
>
> [1] https://en.wikipedia.org/wiki/Carry-less_product
> [2] (page 30)
> https://raw.githubusercontent.com/riscv/riscv-bitmanip/master/bitmanip-0.92.pdf
> [3] https://www.bearssl.org/constanttime.html
>
> What benefit would this intrinsic would bring to the middle-end IR,
> over it's current naive expanded form?
>
>
> Isn't a "naive" expansion of NxN carryless multiply extremely involved?
> I'd expect something like 2N shifts, N truncs, N selects, and N xors.
>
> That link mentions an alternative that is more efficient, but I wouldn't
> exactly call it naive…
>
>
> No, the typical expansion (used by the existing LLVM code generator) uses
> “grade school math” to decompose large multiplications into smaller ones.
>
> Wide multiplications (e.g. those on X86) are pretty easy to pattern match
> from “sign/zero extend operands from 64 bits to 128 bits, then do a
> 128x128=128 multiply” for example.  This is all already handled by the
> existing selection dag infra, my understanding is that it works well in
> practice.
>
> -Chris
>
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20200705/2cb09fd3/attachment.html>