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

[Tom Stellard via llvm-dev]

On Thu, Aug 13, 2015 at 05:25:29AM +1200, Dylan McKay via llvm-dev wrote:
> 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.
> 

I think your proposed solution is a bit of overkill for this problem, because
it impacts legalization of all SDNodes, when only a few are actually used
for pointer arithmetic.

Take a look at this thread:

http://comments.gmane.org/gmane.comp.compilers.llvm.devel/87321

It seems like there are some out of tree patches for handling illegal
pointer types.  Maybe you can work with David to get these changes
upstream.

-Tom

> 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
> ​

> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org         http://llvm.cs.uiuc.edu
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev