[llvm-dev] [GlobalISel] A Proposal for global instruction selection

[Quentin Colombet via llvm-dev]

Hi Eric,


> On Nov 19, 2015, at 12:46 PM, Eric Christopher <echristo at gmail.com> wrote:
> 
> Hi Quentin,
> 
> 
> *** Goals ***
> 
> The high level goals of the new instruction selector are:
> - Global instruction selector.
> - Fast instruction selector.
> 
> Are these separate or the same? It reads like two instruction selectors at the moment.

They are the same, sorry for the confusion. This reads, we want a global and fast instruction selector where producing the code fast and producing good code quality exercise the same basic path in the framework. I.e., producing code fast is a trimmed down version of producing good code. E.g., for fast, analysis are less precise, fewer passes are run, etc.

>  
> - Shared code path for fast and good instruction selection.
> 
> But then I'm not sure starting here.
>  
> - IR that represents ISA concepts better.
> - More flexible instruction selector.
> 
> Some definitions here would be good.

For IR that represents ISA concepts better, this is in opposition to SDISel or LLVM IR. In other words, the target should be able to insert target specific code (e.g., instruction, physical register) at anytime without needing some extra crust to express that (e.g., intrinsic or custom SDNode).

By more flexible we mean that targets should be able to inject target specific passes between the generic passes or replace those passes by their own.

>  
> - Easier to maintain/understand framework, in particular legalization.
> - Self contained machine representation, no back links to LLVM IR.
> - No change to LLVM IR.
> 
> 
> These sound great. Would be good to get the assumptions of the legalization pass written down more explicitly as you go through this.

Agree.
For now, the assumptions are there are no illegal types, just illegal pair of operation and type. But yeah, we may need to refine when we get to the legalization.

>  
> *** Proposed Approach ***
> 
> In this section, I describe the approach I plan to pursue in the prototype and the roadmap to get there. The final design will flow out of it.
> 
> For this prototype, we purposely exclude any work to improve or use TableGen or
> 
> I'm getting the idea that you really don't want to work on TableGen? ;)

Heh, that’s more a pragmatic approach. I don’t want we spend months improving TableGen before we start working on GlobalISel.
That being said, I think we should push as much thing as possible in tablegen when we are done with prototyping.

>  
> 
> ** Implications **
> 
> As part of the bring-up of the prototype, we need to extend some of the core MachineInstr-level APIs:
>   - Need to remember FastMath flags for each MachineInstr.
> 
> Not orthogonal to this proposal? I don't mind lumping it in as being able to do this is probably a good goal for the prototype at least, but it seems like being able to do this is something that could be done incrementally as a separate project?

That’s a good point and yes, it could be done as a separate project. The reason why this is here is because if we want to experiment with combine and such in the prototype, this is the kind of information we would need.

>  
> At the end of M1, the prototype will not be able to produce code, since we would only have the beginning of the Global ISel pipeline. Instead, we will test the IRTranslator on the generic output that is produced from the tested IR.
> 
> 
> So this would be targeting Generic MachineInstr?

Yes.

> (Better name perhaps?).

Suggestion welcome :).

> Which means that it should be serializable and testable in isolation yes?

Partly. The lowering of the body of the function will be generic, but the ABI lowering will be target specific and unless we create some kind of fake target, the tests need to be bound to one target.

>  
> * Design Decisions *
> 
> - The IRTranslator is a final class. Its purpose is to move away from LLVM IR to MachineInstr world [final].
> - Lower the ABI as part of the translation process [final].
> 
> * Design Questions the Prototype Addresses at the End of M1 *
> 
> - Handling of aggregate types during the translation.
> - Lowering of switches.
> - What about Module pass for Machine pass?
> 
> Could you elaborate a bit more here?

I have quickly mentioned in my reply to Marcello why this may be interesting. Let me rephrase my answer here.
Basically, we would like to have the MachineInstr to be self contained, i.e., get rid of those back links to LLVM IR. This implies that we would need to lower globals (maybe directly to MC) as part of the translation process. Globals are not attached to function but module, therefore it seems to make sense to introduce a concept of MachineModulePass.

>  
> - Introduce new APIs to have a clearer separation between:
>   - Legalization (setOperationAction, etc.)
>   - Cost/Combine related (isXXXFree, etc.)
>   - Lowering related (LowerFormal, etc.)
> - What is the contract with the backends? Is it still “should be able to select any valid LLVM IR”?
> 
> Probably :) 
> 
> As far as the prototype I think you also need to address a few additional things:
> 
> a) Calls
>  Calls are probably the most important part of any new instruction selector and lowering machinery and I think that the design of the call lowering infrastructure is going to be a critical part of evaluating the prototype. You might have meant this earlier when you said Lowering related, but I wanted to make sure to call it out explicitly.

Yes, lowering of calls is definitely going to be evaluated in the prototype for this first milestone and the "lowering related” stuff was about that :).
(You’re good at deciphering messages ;)).

> 
> b) Testing
>  It's been covered a bit before, but being able to serialize and use for testing the various IR constructs is important. In particular, I worry about the existing MIR code as I and a few others have tried to use it for testcases and failed. I'm very interested in whatever ideas you have here, all of mine are much more invasive than I think we'd like.

Honestly I haven’t used the MIR testing infrastructure yet, but yes my impression was it is not really… mature. I would love to have some serialization mechanism for the MI that really work so that we can write those testcases more easily.
As for now, I haven’t looked into it, so I cannot share any ideas. I’ve discussed a bit with Matthias and he thinks that we might not be that far away from having MIR testing useable modulo bug fixes.

It would be helpful if you could file PR on the cases where MIR was not working for you so that we can look into it at some point.

My hope is that someone could look into it before we actually need a proper MI testing in place.

(Hidden message: If you are willing to work on the MIR testing or any other mechanism that would allow us to do MI serialization deserialization, please come forward, we need you!! :D)

Indeed, for the translation part the MIR testing is not critical since we do have the LLVM IR around.
Then, if we get rid of the LLVM IR back links, serialization should become easier and maybe MIR testing could be leverage. That being said, it may be possible that we need to start that from scratch, while taking into account what we learnt from the MIR testing.

Thanks for the feedbacks,
-Quentin

> 
> Thanks for tackling this project and being willing to put this out there for discussion and feedback. I'm looking forward to the code and future design.
> 
> -eric
>  

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