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

Wed Aug 12 19:01:06 PDT 2015

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.

I agree with you. I do however think that it has its advantages.

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.

There are a few out of tree patches, but they all work around the problem
at hand.
The mailing list posting you linked was in fact made by a contributor of
AVR-LLVM :)

The solutions described in the posting:

   -

   Convoluted lowering code (with custom lowering for 16-bit operations)

   it lowers loads and stores during combine1 (before legalization), which
   is way less than ideal. It also uses 32-bit frameindexes
   (it treats the stack as 32-bit despite global pointers being 64-bit), so
   I don’t think that provides a>> usable template for a solution here,
   unfortunately.

   -

   Considering pointers to be of different types

   If it would help, one of the changes that we’ve made is to add separate
   PTRADD, INTTOPTR and PTRTOINT nodes to SelectionDAG, which makes it
   possible to keep pointer types distinct. We currently have
   a iFATPTR type, which is not ideal - we’d like to replace this with a
   set of PTR32 to PTR256 types. I’d be happy to prioritise extracting these
   patches for upstreaming if that would be useful to others.

This may not help in our situation, as 16-bit is not a native type but
there are still several other operations that can be performed on 16-bit
values (not just loads/stores).

This is a problem that has been encountered by several different backends,
none of which have
found satisfactory solutions. The proposed fix would simply give a bit more
power to backend
maintainers (although admittedly this is necessary for most targets).

Back to your previous point

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.

The case you make is very strong, as the change proposed would break
dozens of backends.

We could however not cause this problem - a LegalizeAction::Split could be
added
with the meaning described earlier - split an operation into several
smaller operations.
Expand would continue to have its current meaning and operation - it would
either split
or expand into different operations.

The advantage of this is that all backends could specify Expand for illegal
operations, but
targets which need to be specifically split could then use Split instead.

This would:

   - Add the micro-optimization of decreasing code paths for ISel on each
   node. As the number of
   nodes can be in the tens or hundreds of thousands for a compilation,
   this could be fairly beneficial
   - Current backend maintainers would have the option to change their uses
   of Expand to Split where
   appropriate in order to be more explicit
   - In the future, if Split became widespread, it would be much easier to
   change the meaning of Expand if it were to be wanted
   - Cause no breakage

What do you think?

On Thu, Aug 13, 2015 at 5:51 AM, Tom Stellard <tom at stellard.net> wrote:

> 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
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20150813/9afa2b7c/attachment.html>