[LLVMdev] Mul & div support for wider-than-legal types

[Paweł Bylica]

I played with legalizing mul instruction. I implemented naive expanding
that requires 8 multiplication of half-size types (
http://reviews.llvm.org/D8770). This, of course, does not scale up very
well, and it probably doable only up to i512. After this exercise, I have
more questions than before.

Is information coming from TargetLowering::getOperationAction() related to
mul type legalization? Where do that come from? Can a target request a
"custom" lowering for that case?

Depending on a target, some muls divs and other operations are lowered to a
call to a function from a "compiler-rt"-like library. The set of this
built-in functions seems to be sealed. If I would like implement a support
for e.g. mul i256, should I attack it in a similar manner? I.e. by adding a
function to such library?

Another solution I think about is to inject a helper function to a module
that requires long multiplication. That function should have a weak linkage
to be possible merged later by a linker.

Any comments very welcome,
Paweł Bylica

On Wed, Apr 1, 2015 at 4:20 PM Paweł Bylica <chfast at gmail.com> wrote:

> Can it be a first step?
> http://reviews.llvm.org/D8770
>
> - Paweł
>
>
> On Sun, Mar 22, 2015 at 5:35 PM Joerg Sonnenberger <
> joerg at britannica.bec.de> wrote:
>
>> On Sun, Mar 22, 2015 at 03:18:14PM +0000, Paweł Bylica wrote:
>> > On Sun, Mar 22, 2015 at 5:57 AM Joerg Sonnenberger <
>> joerg at britannica.bec.de>
>> > wrote:
>> >
>> > > On Fri, Mar 20, 2015 at 08:06:11PM -0700, Tim Northover wrote:
>> > > > > mul can be inlined easily if necessary for arbitrary sizes, but
>> div is
>> > > very expensive.
>> > > >
>> > > > Shall I file a bug for "implement FFT in LLVM"?
>> > >
>> > > I didn't say it is the most efficient algorithm :) That's why I asked
>> > > about the purpose.
>> > >
>> > > Joerg
>> > >
>> >
>> >  Can you suggest an algorithm and implementation then?
>>
>> For short multi-word multiplications, school book approach works fine.
>> For medium sizes problems, Karatsuba or Toom-Cook is better. For truely
>> larger problems, it boils down to FFT. Of course, all this needs careful
>> benchmarking if you want to select a specific one.
>>
>> Joerg
>>
>> _______________________________________________
>> LLVM Developers mailing list
>> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
>> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20150430/b6654ae1/attachment.html>