[LLVMdev] Proposal for new Legalization framework

[Nadav Rotem]

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

Hi Dan, 

Thank you for working on this.  You mentioned that the two alternatives for replacing SelectionDAG is to munch on it from the top (by legalizing the IR) or from the bottom (by removing the scheduler, Isel and finally the legalization and lowering).  You also mentioned some of the disadvantages of the approach that you are proposing. And I agree with you, this approach has many disadvantages. I think that the end goal should be legalization at the MI level. 
The llvm IR is nice and compact but it is not verbose enough to allow lowering. You mentioned ext/load and trunc/store, but this problem is much worse for vectors. For example, we lower shuffle vector to the following ISD nodes: broadcast, insert_subvector, extract_subvector, concat_vectors, permute, blend, extract/insert_element and a few others. Representing all of these nodes in IR would be inefficient and inconvenient. Every optimization that handles these intrinsics would need to to setup std::vectors, etc, and I think that the compile time for this will not be great either. But I don't think that this is the biggest problem. How do you plan to handle constants ? Do you lower them to global variables and loads ? How would you implement FastISEL ? Do you plan on having two instruction selectors (like we have today) or do you plan to lower IR to intrinsics and select that ? I think that one of the goals of getting rid of selection dag is to have one instruction selector.

Thanks,
Nadav 

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20130424/e1370fcf/attachment.html>