[LLVMdev] Proposal for new Legalization framework

[Owen Anderson]

Hi Dan,

Others have weighed in on the merits of IR vs MI legalization, I thought I'd chip in on a different area:

+    /// Legal roughly means there's a physical register class on the target
+    /// machine for a type, and there's a reasonable set of instructions
+    /// which operate on registers of this class and interpret their contents
+    /// as instances of the type. For convenience, Legal is also used for
+    /// types which are not legalized by this pass (vectors, floats, etc.)
+    Legal,

I don't think this is the right definition of a legal type.  I know that that's how SelectionDAG currently defines it, and I think that definition is behind a lot of the difficulty in retargeting LLVM to something that doesn't look like the intersection of X86 and ARM.

I think the correct answer (credit to Chris for this description) is that a legal type is one that (more or less) corresponds to a set of physical registers, and which the target is capable of loading, storing, and copying (possibly also inserting/extracting elements, for vector types).

--Owen

On Apr 24, 2013, at 5:01 PM, Dan Gohman <dan433584 at gmail.com> wrote:

> 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
> 
> <legalize-integers.patch>_______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev