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ł

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.

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.

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.

No more comments so far, but I have some questions about passes infrastructure.

Can the pass be implemented for the new pass manager? If yes, will it be able to be used by the legacy pass manager?

I think the simplest starting point is basic block pass. Can a basic block pass add new function declarations and/or definitions to the module it runs on?

If basic block is not an option should it be a module pass that trivially iterates over all functions and blocks? From my little experience such passes performed quite badly.

The third option I can think of is some combination of analysis and transform passes.

  • Paweł