llvm dev - Oct 2015 - RFC: Pass for lowering "non-linear" arithmetics of illegal types

Hi LLVM,

This is my idea I had some time ago, when I realized that LLVM did not
support legalization of some arithmetic instructions like mul i256. I have
implemented very simple and limited version of that in my project. Is it
something LLVM users would appreciate?

   1. The pass transforms IR and is meant to be run before CodeGen (after
   IR optimizations).
   2. The pass replaces instructions mul, udiv, urem, sdiv, srem that are
   know to be not supported by target's type legalization with a call to a
   function that implements given arithmetic operation.
   3. The pass also injects these functions to the module with a weak
   linkage.
   4. The pass requires a function generator (interface implementation) for
   mul and udivrem algorithms for integer types of sizes being powers of 2
   (i.e. i128, i256, ...). Replacements for other instructions are created
   using these 2 algorithms.
   5. A default implementation of the generator is provided.
   6. A user is able to provide its own implementation of the generator
   with algorithms better suitable for user's cases and/or for other than
   default instructions (e.g. sdiv i256, urem i199).


- Paweł
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20151005/886c325e/attachment.html>

On 5 October 2015 at 15:09, Paweł Bylica <llvm-dev at lists.llvm.org>
wrote:
> The pass replaces instructions mul, udiv, urem, sdiv, srem that are know to
> be not supported by target's type legalization with a call to a
function
> that implements given arithmetic operation.
This seems quite sensible, those functions can get bigger than you'd
want to inline.
> The pass also injects these functions to the module with a weak linkage.
> The pass requires a function generator (interface implementation) for mul
> and udivrem algorithms for integer types of sizes being powers of 2 (i.e.
> i128, i256, ...). Replacements for other instructions are created using
> these 2 algorithms.
This sounds a bit weird though. It seems more natural to make these
part of a runtime support library for your language (like compiler-rt
is for C).

Cheers.

Tim.

On 10/05/2015 03:25 PM, Tim Northover via llvm-dev
wrote:
> This sounds a bit weird though. It seems more natural to make these
> part of a runtime support library for your language (like compiler-rt
> is for C).
This makes sense for GPUs without call support / machine linking 
support. I would like to be able to replace all expand runtime library 
calls with calls to IR functions we can inline.

On Tue, Oct 6, 2015 at 12:25 AM Tim Northover <t.p.northover at gmail.com>
wrote:
> On 5 October 2015 at 15:09, Paweł Bylica <llvm-dev at lists.llvm.org>
wrote:
> > The pass replaces instructions mul, udiv, urem, sdiv, srem that are
know
> to
> > be not supported by target's type legalization with a call to a
function
> > that implements given arithmetic operation.
>
> This seems quite sensible, those functions can get bigger than you'd
> want to inline.
>
> > The pass also injects these functions to the module with a weak
linkage.
> > The pass requires a function generator (interface implementation) for
mul
> > and udivrem algorithms for integer types of sizes being powers of 2
(i.e.
> > i128, i256, ...). Replacements for other instructions are created
using
> > these 2 algorithms.
>
> This sounds a bit weird though. It seems more natural to make these
> part of a runtime support library for your language (like compiler-rt
> is for C).
>
You are probably right. It makes more sense in general case. I was too
focused on mine. However, we can have both easily. The generator can return
either function declaration or function definition.

>
> Cheers.
>
> Tim.
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20151005/6f7e06bf/attachment.html>