[LLVMdev] Proposal for new Legalization framework

[Dan Gohman]

In the spirit of the (long-term) intent to migrate away from the
SelectionDAG framework, it is desirable to implement legalization passes as
discrete passes. Attached is a patch which implements the beginning of a
new type legalization pass, to help motivate discussion.

Is LLVM IR the right level for this? The main alternative approach that's
been discussed is to do FastISel to a target-independent opcode set on
MachineInstrs, and then do legalization and ultimately the last phase off
instruction selection proper after that. The most obvious advantage of
using LLVM IR for legalization is that it's (currently) more
developer-friendly. The most obvious advantage of using MachineInstrs is
that they would make it easier to do low-level manipulations. Also, doing
legalization on MachineInstrs would mean avoiding having LLVM-IR-level
optimization passes which lower the IR, which has historically been a
design goal of LLVM.

The attached pass operates on LLVM IR, and it's been educational to develop
it this way, but I'm ok with rewriting it in MachineInstrs if that's the
consensus.

Given that the code I wrote operates on LLVM IR, it raises the following
interesting issues:

The code I wrote in the attached patch operates on LLVM IR, so for example
it expands adds into llvm.uadd_with_overflow intrinsics. The intrinsics
available in LLVM IR today aren't as expressive as the ISD operator set in
SelectionDAG, so the generated code is quite a bit more verbose in some
cases. Should we instead add new intrinsics, for add and for a bunch of
other things? People I've talked to so far were hesitant to add new
intrinsics unless they're really prohibitive to do in other ways.

How should we legalize function argument and return types? Because of LLVM
IR rules, one can't just change the signature of a function without
changing all its callsites, so as a consequence the code I wrote is a
ModulePass. This is unfortunate, since it's a goal that most of the codegen
passes be FunctionPasses. Modifying the Function types may also be
incompatible with the ABI coordination dance between front-ends and
backends on some targets. One alternative, which is also implemented, is to
leave function signatures alone and simply insert conversions to and from
legal types. In this case, instruction selection would need to know how to
handle illegal types in these special circumstances, but presumably it
would be easy enough to special-case them. However, if this pass is
followed by an optimization pass analogous to DAGCombine, it may be tricky
to keep the optimization pass from creating patterns which codegen isn't
prepared to handle. Another alternative, which is not implemented yet, is
have the legalization pass create new Functions, and make the original
Functions simply call the legalized functions, and then have a late pass
clean everything up.

We may already need some amount of special-casing for things like bitfield
loads and stores. To implement the C++ memory model, some bitfield loads
and stores actually need to load and store a precise number of bits, even
if that number of bits doesn't correspond to a legal integer (register)
size on the target machine. This isn't implemented yet, but I expect this
will be handled by leaving those loads and stores alone, and simply putting
the burden on subsequent passes to lower them properly. An alternative to
this is to add new truncating-store and sign/zero-extending load intrinsics.

Another complication due to using LLVM IR is the interaction with
DebugInfo. If AllocaInsts for illegal types are expanded, or if values for
llvm.dbg.value intrinsics are expanded, there's currently no way to
describe this (DWARF can describe it, but LLVM IR can't currently). I
assume this could be fixed by extending LLVM IR's DebugInfo intrinsics, but
I haven't investigated it yet.

Dan
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20130424/51f958c6/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: legalize-integers.patch
Type: application/octet-stream
Size: 49922 bytes
Desc: not available
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20130424/51f958c6/attachment.obj>