[LLVMdev] Proposal for new Legalization framework

Chris Lattner clattner at apple.com
Fri Apr 26 11:43:13 PDT 2013


On Apr 25, 2013, at 1:50 AM, David Chisnall <David.Chisnall at cl.cam.ac.uk> wrote:

> Hi Dan,
> 
> On 25 Apr 2013, at 01:01, Dan Gohman <dan433584 at gmail.com> wrote:
> 
>> 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 approach taken in WHIRL, which has a lot of advantages, is exactly to lower the IR.  It seems strange that in the back end we have Machine* classes that correspond very closely to IR equivalents, but which don't share any code and often have subtly different interfaces.  The approach taken in WHIRL is to progressively replace machine-independent bits of the IR with machine-dependent ones, with abstract instructions being replaced with machine instructions, abstract registers with machine registers, and so on.  
> 
> I would be interested to know the rationale behind the design choice to avoid this, as it seems the obvious way of designing a compiler.  The down side would be that you couldn't take any random pass that expected target-independent IR and run it, but you never actually want to do this once you've handed off to the codegen infrastructure anyway.

There definitely are strong advantages to using one datastructure to represent multiple levels of IR: you have less code in the compiler, more shared concepts, etc.  I have seen and work with several compilers that tried to do this.  Even GCC does this (in the opposite direction) with "treessa" which repurposes some front-end data structures for their mid-level IR.

While there are advantages, it also means that you get fewer invariants, and that the data structures are a worse fit for each level.  To give you one simple example: LLVM IR is simplified greatly based on the assumption that it is always in SSA and that each instruction produces one result value, and exceptions to that rule (like some intrinsics) can easily be modeled with extract value operations.

This doesn't work for MachineInstrs which have the following additional complexity:
- Not everything is in SSA, you have to model physical registers, even very early.
- Lots of things return N values, and extract-value doesn't work.

I consider it unacceptable to project complexity from MachineInstrs into LLVM IR.  There are wins, but there are also unacceptably high costs.  Some of those include:
 - LLVM IR is our stable IR format, MachineInstr is not.  The later *needs* to evolve rapidly, where the former has settled down (mostly).  
 - The reasons people like to work with LLVM IR is often directly because of the simplifications we get from having a simple model.

Jeopardizing stability in the IR and making LLVM IR works to work with is not acceptable to me.

-Chris



More information about the llvm-dev mailing list