<div dir="ltr"><div><div>I played with legalizing mul instruction. I implemented naive expanding that requires 8 multiplication of half-size types (<a href="http://reviews.llvm.org/D8770">http://reviews.llvm.org/D8770</a>). 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.</div><div><br></div><div>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?</div><div><br></div><div>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?</div><div><br></div><div>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.</div><div><br></div><div>Any comments very welcome,</div><div>Paweł Bylica</div><br><div class="gmail_quote">On Wed, Apr 1, 2015 at 4:20 PM Paweł Bylica <<a href="mailto:chfast@gmail.com" target="_blank">chfast@gmail.com</a>> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr">Can it be a first step?<div><a href="http://reviews.llvm.org/D8770" target="_blank">http://reviews.llvm.org/D8770</a></div><div><br></div><div></div></div><div dir="ltr"><div>- Paweł</div></div><div dir="ltr"><div><br><br><div class="gmail_quote">On Sun, Mar 22, 2015 at 5:35 PM Joerg Sonnenberger <<a href="mailto:joerg@britannica.bec.de" target="_blank">joerg@britannica.bec.de</a>> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">On Sun, Mar 22, 2015 at 03:18:14PM +0000, Paweł Bylica wrote:<br>
> On Sun, Mar 22, 2015 at 5:57 AM Joerg Sonnenberger <<a href="mailto:joerg@britannica.bec.de" target="_blank">joerg@britannica.bec.de</a>><br>
> wrote:<br>
><br>
> > On Fri, Mar 20, 2015 at 08:06:11PM -0700, Tim Northover wrote:<br>
> > > > mul can be inlined easily if necessary for arbitrary sizes, but div is<br>
> > very expensive.<br>
> > ><br>
> > > Shall I file a bug for "implement FFT in LLVM"?<br>
> ><br>
> > I didn't say it is the most efficient algorithm :) That's why I asked<br>
> > about the purpose.<br>
> ><br>
> > Joerg<br>
> ><br>
><br>
>  Can you suggest an algorithm and implementation then?<br>
<br>
For short multi-word multiplications, school book approach works fine.<br>
For medium sizes problems, Karatsuba or Toom-Cook is better. For truely<br>
larger problems, it boils down to FFT. Of course, all this needs careful<br>
benchmarking if you want to select a specific one.<br>
<br>
Joerg<br>
<br>
______________________________<u></u>_________________<br>
LLVM Developers mailing list<br>
<a href="mailto:LLVMdev@cs.uiuc.edu" target="_blank">LLVMdev@cs.uiuc.edu</a>         <a href="http://llvm.cs.uiuc.edu" target="_blank">http://llvm.cs.uiuc.edu</a><br>
<a href="http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev" target="_blank">http://lists.cs.uiuc.edu/<u></u>mailman/listinfo/llvmdev</a><br>
</blockquote></div></div></div></blockquote></div></div></div>