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

Dylan McKay via llvm-dev llvm-dev at lists.llvm.org
Wed Aug 12 10:25:29 PDT 2015

Hello all,

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

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


   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

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.

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

More information about the llvm-dev mailing list