[llvm-dev] Splitting 'expand' into 'split' and `expand`.

[Dylan McKay via llvm-dev]

Hello all,

I would like to propose a large change to LLVM that I would be happy to
implement.

The instruction selection legalizer knows of three different ways to
legalize an action (ignoring an already legal action).

   - Expansion
   - Promotion
   - Custom

Expanding a node will lead to one of two things - the operation will be
split into several equivalent smaller operations (i.e. 64-bit mul => two
32-bit multiplications), or it will be expanded into a different
operation(s) (i.e. SDIVREM => SDIV + SREM or a runtime library call).

This can be ambiguous - should a 128-bit SDIVREM be expanded into two
64-bit SDIVREMs or a 128-bit libcall.

It would be useful for LLVM to distinguish between these two operations -
i.e. instead of LegalizeAction::Expand, we have LegalizeAction::Expand and
LegalizeAction::Split.

   -

   Expand should always expand the node into a different pattern (such as
   MULHU expanding to MUL and a copy of the top half).
   -

   Split will always split an operation into several smaller, operations
   (such as 128-bit addition being split into a 64-bit addition and a 64-bit
   addition with carry)

Full disclosure: I’m working on a backend on which the pointer type is
illegal (Atmel AVR : 8-bit microcontroller with 16-bit pointers). The
problem with the ambiguity with expand today is that LLVM implicitly
assumes that as a 16-bit register class exists, then 16-bit
addition/subtraction should exist and there is no point splitting into two
8-bit operations.

Currently we work around this by defining 16-bit pseudo instructions for
every instruction which is not properly supported. This gives us very
sub-optimal code and introduces many bugs. More detail about the problem
can be found in the old mailing list archives
<http://lists.cs.uiuc.edu/pipermail/llvmdev/2015-June/087277.html>.

I’m not sure if this requires an RFC? It would be a very large breaking
change. Perhaps a less drastic solution can be found, like leaving Expand
as it is, but also adding LegalizeAction::Split which must expand only
using smaller operations.

Again, I would be happy to work on this.

Cheers,
Dylan McKay
​
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20150813/ae6d69d4/attachment.html>