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

[Roman Lebedev via llvm-dev]

On Sun, Jul 5, 2020 at 11:07 PM Chris Lattner <clattner at nondot.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.
That is what i meant, yes.

> This is all already handled by the existing selection dag infra, my understanding is that it works well in practice.
>
> -Chris
Roman