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

> On Nov 19, 2015, at 4:58 PM, Eric Christopher <echristo at gmail.com>
wrote:
> 
> 
> 
> On Thu, Nov 19, 2015 at 2:26 PM Quentin Colombet <qcolombet at apple.com
<mailto:qcolombet at apple.com>> wrote:
> Hi Eric,
> 
> 
>> On Nov 19, 2015, at 12:46 PM, Eric Christopher <echristo at
gmail.com <mailto: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.
> 
> Excellent.
>  
> 
>>  
>> - 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).
> 
> 
> I'm not sure that this represents the concepts any better. Basically it
means that you have less and easier target independent handling, I'm
unconvinced this is that useful. Perhaps an example might help :)
I don’t have an example off hand, but basically, any time we have to create a
custom SDNode, it is useless.
Another thing, that I didn’t call out before because it is a strong statement
and I don’t want to commit on that for now, is that we can have a better
estimate for register pressure and thing like choosing addressing mode, since we
are at a much lower level and that we can directly emit the proper memory
operation or look at the actual register classes.

Those are the kind of opportunities that I envision by moving to MachineInstr
level.
>  
> 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.
> 
> It'll be interesting to see how this is going to be developed and how
to keep the target independentness of the code generator with this new scheme.
I.e. this is basically turning (in my mind) into "every backend for
themselves" with very little target independent unification. Outside of
special purpose ports I don't see a lot of need for this, but we'll see.
I think it's going to take some discipline to avoid the "every backend
is a large C++ project that defines everything it needs custom”.
At this point, the idea is to have the standard passes shared (i.e.,
IRTranslator, Legalizer, RegBankSelect, and Select) and let the targets create
their own pass if they want to do more stuff. Then, if we see room for
generalization, we can refactor :).

This is what happens right now with the IR passes that are target specific.
Sometimes those get factored out like GlobalMerge.

I believe the same could happen with MachineInstr passes.

Now, regarding the standard passes themselves, I don’t see how the target
independentness will be different than our current selector. If your concern is
about canonicalization, well, yes, if targets start to mess up the generic
opcodes with target specific opcodes, we may lose some of it, but, I would say,
that is the point!
If targets want to mess up with canonicalization, so be it. This is a problem we
have with SDISel: sometime targets fight the canonicalization and this is very
hard. Now, that would be much easier :).

Anyhow, yes, this is something we need to keep an eye on, and at some point in
the prototype, it will be nice to have quick targeting of the framework for
other backends.
>  
> 
>>  
>> - 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.
> 
> Also things like canonicalization, etc. Just something to think about.
Yeah, just mentioned canonicalization in my previous paragraph and the bottom
line is that I don’t think canonicalization should be required for correctness.
>  
> 
>>  
>> *** 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.
> 
> Sure.
>  
> 
>>  
>> 
>> ** 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.
> 
> 
> Hmm, I thought you were avoiding combine? :)
Heh, figured someones may want to try it during the prototype timeframe :),
though, what interests me here is to check how easy it is to propagate this kind
of information, while going for the self contained IR.
>  
>>  
>> 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 :).
> 
> Yeah. First suggestion: Let's leave off the r ;)
Gene.ic :P
>  
> 
>> 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.
> 
> That's reasonable.
The fake target or 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.
> 
> *nod* I'd like to do something about the AsmPrinter anyhow.
>  
> 
>>  
>> - 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 ;)).
> 
> I try. Anyhow, glad to hear about calls.
>  
> 
>> 
>> 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.
> 
> Pretty much agree with this. I didn't file a bug because I wasn't
sure what to say other than "this serialization wasn't useful for
making test cases". Maybe you'll find it more so and we can get some
best practices out of it.
Fingers crossed!

Thanks for the additional feedback, I think it really helps to call all that
out!
Q.
> 
> Thanks!
> 
> -eric
>  
> 
> 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/a9009a5a/attachment-0001.html>

>
>
>>
>>> - 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).
>>
>>
> I'm not sure that this represents the concepts any better. Basically it
> means that you have less and easier target independent handling, I'm
> unconvinced this is that useful. Perhaps an example might help :)
>
>
> I don’t have an example off hand, but basically, any time we have to
> create a custom SDNode, it is useless.
> Another thing, that I didn’t call out before because it is a strong
> statement and I don’t want to commit on that for now, is that we can have a
> better estimate for register pressure and thing like choosing addressing
> mode, since we are at a much lower level and that we can directly emit the
> proper memory operation or look at the actual register classes.
>
> Those are the kind of opportunities that I envision by moving to
> MachineInstr level.
>
I guess it'll depend on how we construct the generic MIR I guess.  I'm
not
seeing it, but I'll hope for some magic :)
>
>
>>
>>
>>
>>> - 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.
>>
>
> Also things like canonicalization, etc. Just something to think about.
>
>
> Yeah, just mentioned canonicalization in my previous paragraph and the
> bottom line is that I don’t think canonicalization should be required for
> correctness.
>
Well, I mean things like "target A wants op * 2, target B wants op <<
2" as
far as canonicalization. I'm meaning it from a "how we look at code
generation level", nothing more. I'm also not too fussed here.
We'll see
how it comes out.
>
>> Suggestion welcome :).
>>
>
> Yeah. First suggestion: Let's leave off the r ;)
>
>
> Gene.ic :P
>
Hahahahahaha.

>
>
>
>>
>> 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.
>>
>
> That's reasonable.
>
>
> The fake target or be bound to one target?
>
Bound to one target if necessary. I like that we have some code generation
tests that are "every target can handle this", but others are
"let's see
what we get on target X with this input". Both are valuable, but I
don't
see a need to construct up a fake target for anything.

-eric

>
>
>>
>>
>>
>>> * 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.
>>
>
> *nod* I'd like to do something about the AsmPrinter anyhow.
>
>
>>
>>
>>
>>> - 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 ;)).
>>
>
> I try. Anyhow, glad to hear about calls.
>
>
>>
>>
>> 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.
>>
>>
>>
>
>
>
>
> * 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.
>
> *nod* I'd like to do something about the AsmPrinter anyhow.
>
>
>
> - 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 ;)).
>
> I try. Anyhow, glad to hear about calls.
>
>
>
> 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.
>
> Pretty much agree with this. I didn't file a bug because I wasn't
sure
> what to say other than "this serialization wasn't useful for
making test
> cases". Maybe you'll find it more so and we can get some best
practices out
> of it.
>
> 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.
>>
>
> Pretty much agree with this. I didn't file a bug because I wasn't
sure
> what to say other than "this serialization wasn't useful for
making test
> cases". Maybe you'll find it more so and we can get some best
practices out
> of it.
>
>
> Fingers crossed!
>
> Thanks for the additional feedback, I think it really helps to call all
> that out!
> Q.
>
>
> Thanks!
>
> -eric
>
>
>>
>> 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/20151120/6c93619d/attachment.html>

On 20 Nov 2015, at 01:43, Quentin Colombet via llvm-dev <llvm-dev at
lists.llvm.org> wrote:
> 
>>> 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.
>> 
>> It'll be interesting to see how this is going to be developed and
how to keep the target independentness of the code generator with this new
scheme. I.e. this is basically turning (in my mind) into "every backend for
themselves" with very little target independent unification. Outside of
special purpose ports I don't see a lot of need for this, but we'll see.
I think it's going to take some discipline to avoid the "every backend
is a large C++ project that defines everything it needs custom”.
> 
> At this point, the idea is to have the standard passes shared (i.e.,
IRTranslator, Legalizer, RegBankSelect, and Select) and let the targets create
their own pass if they want to do more stuff. Then, if we see room for
generalization, we can refactor :).
To give a concrete example of this:

Currently, SelectionDAG has completely generic infrastructure for expanding
unaligned loads and stores into sequences of aligned loads and masks. 
Unfortunately, the interface is entirely push from the generic side, not pull
from the target side.  We hit a problem where we needed different handling of
unaligned loads and stores based on the address space of the base pointer.  We
ended up having to duplicate a load of the SelectionDAG logic in the back end. 
Eventually, extending our CPU to support unaligned loads and stores proved less
effort than trying to get SelectionDAG to place nicely with our constraints.

With the new design, I’d imagine that there’d be a generic ExpandUnalignedLoad
function in the supporting library that any target could simply use for the
places where it makes sense.  On MIPS, for example, the load-word-left and
load-word-right instructions need some special handling and allow you to
generate quite efficient code, but other forms of unaligned load and store may
want to be handled generically.  Being able to have the targets choose at a fine
granularity by explicitly calling into the generic code for the functionality
that they need is likely to be a lot better than having to provide a load of
predicates up-front and hoping that the ones that the generic infrastructure
asks for match the ones that you want (currently, there’s no way to tell
SelectionDAG that you want different handling for things with pointers in
different address spaces and no way to specify Custom for all address spaces and
then call back into the generic behaviour if you want to use it for a subset).

There’s also the issue that, because SelectionDAG is a push model, it’s very
easy to get into a situation (especially with the set_cc / br_cc families) where
you do a transform, SelectionDAG does the inverse transform, then calls back
into the back end, which redoes the transform, which SelectionDAG undoes, and so
on.  I think everyone who has worked on any back end has encountered this at
least once (often identified with ‘why is this one test in the test suite
running forever?’).

A few other things that come to mind as being easier to generalise in this
model:

- Constant island generation (the ARM constant islands pass has been copied
around the place a few times)

- The expansions for ll/sc atomics (we currently do this in LLVM IR, which is
the wrong place, because the right place is MIR, which doesn’t exist yet)

I’m sure that there are others.

David

> On Nov 20, 2015, at 1:39 AM, David Chisnall <David.Chisnall at
cl.cam.ac.uk> wrote:
> 
> On 20 Nov 2015, at 01:43, Quentin Colombet via llvm-dev <llvm-dev at
lists.llvm.org> wrote:
>> 
>>>> 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.
>>> 
>>> It'll be interesting to see how this is going to be developed
and how to keep the target independentness of the code generator with this new
scheme. I.e. this is basically turning (in my mind) into "every backend for
themselves" with very little target independent unification. Outside of
special purpose ports I don't see a lot of need for this, but we'll see.
I think it's going to take some discipline to avoid the "every backend
is a large C++ project that defines everything it needs custom”.
>> 
>> At this point, the idea is to have the standard passes shared (i.e.,
IRTranslator, Legalizer, RegBankSelect, and Select) and let the targets create
their own pass if they want to do more stuff. Then, if we see room for
generalization, we can refactor :).
> 
> To give a concrete example of this:
> 
> Currently, SelectionDAG has completely generic infrastructure for expanding
unaligned loads and stores into sequences of aligned loads and masks. 
Unfortunately, the interface is entirely push from the generic side, not pull
from the target side.  We hit a problem where we needed different handling of
unaligned loads and stores based on the address space of the base pointer.  We
ended up having to duplicate a load of the SelectionDAG logic in the back end. 
Eventually, extending our CPU to support unaligned loads and stores proved less
effort than trying to get SelectionDAG to place nicely with our constraints.
> 
> With the new design, I’d imagine that there’d be a generic
ExpandUnalignedLoad function in the supporting library that any target could
simply use for the places where it makes sense.
That is the idea behind the LegalizationKit.
>  On MIPS, for example, the load-word-left and load-word-right instructions
need some special handling and allow you to generate quite efficient code, but
other forms of unaligned load and store may want to be handled generically. 
Being able to have the targets choose at a fine granularity by explicitly
calling into the generic code for the functionality that they need is likely to
be a lot better than having to provide a load of predicates up-front and hoping
that the ones that the generic infrastructure asks for match the ones that you
want (currently, there’s no way to tell SelectionDAG that you want different
handling for things with pointers in different address spaces and no way to
specify Custom for all address spaces and then call back into the generic
behaviour if you want to use it for a subset).
> 
> There’s also the issue that, because SelectionDAG is a push model, it’s
very easy to get into a situation (especially with the set_cc / br_cc families)
where you do a transform, SelectionDAG does the inverse transform, then calls
back into the back end, which redoes the transform, which SelectionDAG undoes,
and so on.  I think everyone who has worked on any back end has encountered this
at least once (often identified with ‘why is this one test in the test suite
running forever?’).
> 
> A few other things that come to mind as being easier to generalise in this
model:
> 
> - Constant island generation (the ARM constant islands pass has been copied
around the place a few times)
> 
> - The expansions for ll/sc atomics (we currently do this in LLVM IR, which
is the wrong place, because the right place is MIR, which doesn’t exist yet)
> 
> I’m sure that there are others.
Agreed, for instance, we have the load/store optimizers for both ARM and
AArch64.

Thanks for the detailed example.
Q.
> 
> David
> 
>

> On Nov 19, 2015, at 5:57 PM, Eric Christopher <echristo at gmail.com>
wrote:
> 
>>>  
>>> - 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).
>> 
>> 
>> I'm not sure that this represents the concepts any better.
Basically it means that you have less and easier target independent handling,
I'm unconvinced this is that useful. Perhaps an example might help :)
> 
> I don’t have an example off hand, but basically, any time we have to create
a custom SDNode, it is useless.
> Another thing, that I didn’t call out before because it is a strong
statement and I don’t want to commit on that for now, is that we can have a
better estimate for register pressure and thing like choosing addressing mode,
since we are at a much lower level and that we can directly emit the proper
memory operation or look at the actual register classes.
> 
> Those are the kind of opportunities that I envision by moving to
MachineInstr level.
> 
> I guess it'll depend on how we construct the generic MIR I guess. 
I'm not seeing it, but I'll hope for some magic :)
>>  
>> 
>>>  
>>> - 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.
>> 
>> Also things like canonicalization, etc. Just something to think about.
> 
> Yeah, just mentioned canonicalization in my previous paragraph and the
bottom line is that I don’t think canonicalization should be required for
correctness.
> 
> Well, I mean things like "target A wants op * 2, target B wants op
<< 2" as far as canonicalization. I'm meaning it from a "how
we look at code generation level", nothing more. I'm also not too
fussed here. We'll see how it comes out.
>> 
>> Suggestion welcome :).
>> 
>> Yeah. First suggestion: Let's leave off the r ;)
> 
> Gene.ic :P
> 
> Hahahahahaha.
>  
> 
>>  
>> 
>>> 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.
>> 
>> That's reasonable.
> 
> The fake target or be bound to one target?
> 
> Bound to one target if necessary. I like that we have some code generation
tests that are "every target can handle this", but others are
"let's see what we get on target X with this input". Both are
valuable, but I don't see a need to construct up a fake target for anything.
Agreed!

Thanks Eric!
Q.
> 
> -eric 
> 
> 
>>  
>> 
>>>  
>>> * 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.
>> 
>> *nod* I'd like to do something about the AsmPrinter anyhow.
>>  
>> 
>>>  
>>> - 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 ;)).
>> 
>> I try. Anyhow, glad to hear about calls.
>>  
>> 
>>> 
>>> 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.
>> 
> 
> 
>  
> 
>  
> * 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.
> 
> *nod* I'd like to do something about the AsmPrinter anyhow.
>  
> 
>  
> - 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 ;)).
> 
> I try. Anyhow, glad to hear about calls.
>  
> 
> 
> 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.
> 
> Pretty much agree with this. I didn't file a bug because I wasn't
sure what to say other than "this serialization wasn't useful for
making test cases". Maybe you'll find it more so and we can get some
best practices out of it.
> 
>> 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.
>> 
>> Pretty much agree with this. I didn't file a bug because I
wasn't sure what to say other than "this serialization wasn't
useful for making test cases". Maybe you'll find it more so and we can
get some best practices out of it.
> 
> Fingers crossed!
> 
> Thanks for the additional feedback, I think it really helps to call all
that out!
> Q.
> 
>> 
>> Thanks!
>> 
>> -eric
>>  
>> 
>> 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/20151120/962721be/attachment-0001.html>