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

Hi,

With this email, I would like to kick-off the development for the next
instruction selector that I described during the last LLVM Dev’ Meeting.
For the motivations, see Jakob’s proposal
(http://lists.cs.uiuc.edu/pipermail/llvmdev/2013-August/064727.html
<http://lists.cs.uiuc.edu/pipermail/llvmdev/2013-August/064727.html>) and
for the proposal, see the slides (Keynote:
http://llvm.org/viewvc/llvm-project/www/trunk/devmtg/2015-10/slides/Colombet-GlobalInstructionSelection.key?view=co
<http://llvm.org/viewvc/llvm-project/www/trunk/devmtg/2015-10/slides/Colombet-GlobalInstructionSelection.key?view=co>
or PDF:
http://llvm.org/viewvc/llvm-project/www/trunk/devmtg/2015-10/slides/Colombet-GlobalInstructionSelection.pdf?revision=252430&view=co
<http://llvm.org/viewvc/llvm-project/www/trunk/devmtg/2015-10/slides/Colombet-GlobalInstructionSelection.pdf?revision=252430&view=co>)
or the talk
(https://www.youtube.com/watch?v=F6GGbYtae3g&list=PL_R5A0lGi1AA4Lv2bBFSwhgDaHvvpVU21&index=2
<https://www.youtube.com/watch?v=F6GGbYtae3g&list=PL_R5A0lGi1AA4Lv2bBFSwhgDaHvvpVU21&index=2>).

TL;DR This is happening now, feedbacks invited!

*** Context ***

During the last LLVM Dev’ Meeting, I have presented a proposal for the next
instruction selector, GlobalISel. The proposal is basically summarized in
"High Level Prototype Design” and “Roadmap”. (If you want further details,
feel free to reach me.)

The first step of the development plan is to prototype the new framework on open
source. The idea is to start prototyping now(!) and have the discussion ongoing
in parallel. The reason of such approach is to have code that can be used to
inform those discussions, e.g., by collecting data and trying different designs
approaches. Regarding the discussion, I have listed a few points where your
feedbacks would be particularly appreciated (see Feedback Invite).

Also, as I have mentioned in my talk, some issues are controversial but I expect
them to be resolved during prototype development. Specifically theses concern
aspects of legalization (should parts of it be done at the LLVM IR level or all
at the MI level?) and code re-use for instruction combiner. Please feel free to
bring up your specific concern as I move along with the development plan.

I expect the design to evolve with our experimental findings and your feedbacks
and contributions.
Nonetheless, we expect to nail down some design decisions once and for all as
the prototype progresses. I have highlighted them with the following pattern
[final].



*** Feedback Invite ***

If you follow and support this work you need to be aware of three things and I
am eager to hear your feedback and thoughts about them: the overall goals of
Global ISel, the goals of the prototype, and the impact of the prototype work on
backend design.

In the section “Goals", I defined (repeated for people that saw the talk)
the goals for the Global ISel design.
- Do you see anything missing?
- Do you see something that should not be there? 

The prototype will answer critical design questions (see “Design Questions the
Prototype Addresses at the End of M1" for examples) before the actual
design of Gobal ISel is finalized, but it cannot cover everything.
Specifically we will *not* look into improving TableGen or reuse InstCombine
(see “ Proposed Approach” for the rational). Please let me know if you see any
issue with that.

There is also basic ground work needed to prepare for Global ISel and I need to
extend the core MachineInstr-level APIs as explained during the talk. For this,
I prepared sketches of patches to illustrate them and describe the details in
the “Implications” section below. Please have a look at the patches to have a
better idea of the expected impact.

If there is anything else you want to discuss related to Global ISel feel free
to reach me. In particular, several people expressed their interests during the
LLVM Dev Meeting in contributing to the project. Let me know what is your area
of interest, so that we can coordinate our efforts.
Anyhow, please add [GlobalISel] in the subject line to help categorizing the
emails.



*** Goals ***

The high level goals of the new instruction selector are:
- Global instruction selector.
- Fast instruction selector.
- Shared code path for fast and good instruction selection.
- IR that represents ISA concepts better.
- More flexible instruction selector.
- Easier to maintain/understand framework, in particular legalization.
- Self contained machine representation, no back links to LLVM IR.
- No change to LLVM IR.

Note:  The goals are common to all targets. In particular, we do not intend to
work on target specific feature for the prototype.
The bottom line is please make sure those goals are compatible with what you
want to achieve for your target, even if your requirement does not get listed
here.



*** 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
InstCombine [final]. We will keep in mind however, that some of the C++ code we
write will be table-generated at some point.
The rational is that we do not want to lay down a new TableGen/InstCombine
infrastructure before being able to work on the ISel framework itself.

The prototype vehicle will be AArch64. None of the changes for GlobalISel will
negatively impact the existing ISel.


** High Level Prototype Design **

As shown in the talk, the expected pipeline for the prototype is:
LLVM IR -> IRTranslator -> Generic (G) MachineInstr -> Legalizer ->
RegBankSelect -> Select -> MachineInstr

Where:
- Terms in bold are intermediate representations.
-  Generic MachineInstrs are machine instructions with a generic opcode, e.g.,
ADD, COPY.
- IRTranslator: Translate LLVM IR to (G) MachineInstr.
- Legalizer: Legalize illegal (G) MachineInstr to legal (G) MachineInstr.
- RegBankSelect: Assign virtual register with size to virtual register with
Register Bank.
- Select: Translate the remaining (G) MachineInstr to MachineIntr.



** 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.
  - Need to know the type of each MachineInstr. We don’t want ADD8, ADD16, etc.
  - Extend the MachineRegisterInfo to support size as well as register classes
for virtual registers.

I have sketched the changes in the attached patches to help picturing how the
changes would impact the existing APIs.

Note: I do not intend to commit those changes as they are. They will go the
usual review process in due time.

The patches contain “// ***”-like comment that give a rough explanation on why
those changes are needed w.r.t. the goals.
The order of the patches could be modified since the dependencies between those
are not sequential. Anyhow, here are the patches:
1. Introduce (some of) the generic opcode.
2. Make MachineFunction more independent of LLVM IR to eventually be able to
delete the LLVM IR instance from the memory.
3. Extend MachineInstr to represent additional information attached to generic
opcode.
4. Teach MachineRegisterInfo about size for virtual registers.
5. Introduce a helper class to build MachineInstr related objects.
6. Add new target hooks to lower the ABI directly to MachineInstr.
7. Introduce the IRTranslator pass.


** Roadmap for the Prototype **

We plan to split the prototype in three main milestones:
1. Translation: LLVM IR to (G) MachineInstr translation.
2. Basic selector: Legal LLVM IR to target specific MachineInstr.
3. Simple legalization: Support scalar type legalization and some vector
instructions.

Notes:
- For #1, we will not support any fancy instructions like landing pad or switch.
- Each milestone should take about 3-4 months.
- At the end of #2, we would have a FastISel like selector.

Each milestone will be detailed right before starting it. The rational is that
we want to accommodate what we discovered with the prototype for the next
milestone. In other words, in this email, I only describe the first milestone in
detail and I will give more details on the next milestone shortly before we
start it and so on. For your information, here is the remaining of the intended
roadmap for the full project:
4. Productization: Clean up implementation, stabilize the APIs.
5. Complex legalization: Extend legalization support to everything missing.
6. Completeness: Fill the blanks, e.g., landing pad.
7. Clean-up and performance: Add the necessary bits to be at parity or beat
SelectionDAG generated code.
8. Transition: Document how to switch, provide tools to help.


** Milestone 1 **

The first phase is focused on the IRTranslator pass.

The IRTranslator is responsible for translating the LLVM IR into Generic
MachineInstr. The IRTranslator pass uses some target hooks to perform the ABI
lowering. We can either define a new API for them, e.g., ABILoweringInfo, or
extend the existing TargetLowering.
Moreover, the prototype will focus on simple instruction, i.e., we will not
support switch or landing pad for this iteration.

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.

* 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?
- 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”?

Thanks,
-Quentin






-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20151118/b483435a/attachment-0008.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: 0001-Extend-generic-opcodes-to-be-able-to-represent-the-i.patch
Type: application/octet-stream
Size: 3760 bytes
Desc: not available
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20151118/b483435a/attachment-0007.obj>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20151118/b483435a/attachment-0009.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: 0002-Pull-more-of-the-LLVM-IR-function-representation-int.patch
Type: application/octet-stream
Size: 1853 bytes
Desc: not available
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20151118/b483435a/attachment-0008.obj>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20151118/b483435a/attachment-0010.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: 0003-Extend-MachineInstr-to-supply-more-information-regar.patch
Type: application/octet-stream
Size: 2260 bytes
Desc: not available
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20151118/b483435a/attachment-0009.obj>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20151118/b483435a/attachment-0011.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: 0004-Teach-MachineRegisterInfo-about-size-for-virtual-reg.patch
Type: application/octet-stream
Size: 3128 bytes
Desc: not available
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20151118/b483435a/attachment-0010.obj>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20151118/b483435a/attachment-0012.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: 0005-Introduce-a-MachineIRBuilder-to-gather-all-the-Machi.patch
Type: application/octet-stream
Size: 2598 bytes
Desc: not available
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20151118/b483435a/attachment-0011.obj>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20151118/b483435a/attachment-0013.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: 0006-Add-new-target-hooks-to-be-able-to-lower-the-ABI-rig.patch
Type: application/octet-stream
Size: 2839 bytes
Desc: not available
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20151118/b483435a/attachment-0012.obj>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20151118/b483435a/attachment-0014.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: 0007-Introduce-the-IRtranslator-pass-for-GlobalISel.patch
Type: application/octet-stream
Size: 7852 bytes
Desc: not available
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20151118/b483435a/attachment-0013.obj>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20151118/b483435a/attachment-0015.html>

Hi Quentin,

I'm really excited to see this happening!

My major question is over the testing story for this. How are we going to
write unit tests for GIR? Are you intending to leverage the LIR lowering
that noone is using yet? Will you be using unit/LIT tests right from the
start, or adding them in later?

Cheers,

James

On Wed, 18 Nov 2015 at 19:27 Quentin Colombet via llvm-dev <
llvm-dev at lists.llvm.org> wrote:
> Hi,
>
> With this email, I would like to kick-off the development for the next
> instruction selector that I described during the last LLVM Dev’ Meeting.
> For the motivations, see Jakob’s proposal (
> http://lists.cs.uiuc.edu/pipermail/llvmdev/2013-August/064727.html) and
> for the proposal, see the slides (Keynote:
>
http://llvm.org/viewvc/llvm-project/www/trunk/devmtg/2015-10/slides/Colombet-GlobalInstructionSelection.key?view=co
or
> PDF:
>
http://llvm.org/viewvc/llvm-project/www/trunk/devmtg/2015-10/slides/Colombet-GlobalInstructionSelection.pdf?revision=252430&view=co)
> or the talk (
>
https://www.youtube.com/watch?v=F6GGbYtae3g&list=PL_R5A0lGi1AA4Lv2bBFSwhgDaHvvpVU21&index=2
> ).
>
> TL;DR This is happening now, feedbacks invited!
>
> *** Context ***
>
> During the last LLVM Dev’ Meeting, I have presented a proposal for the
> next instruction selector, GlobalISel. The proposal is basically summarized
> in "High Level Prototype Design” and “Roadmap”. (If you want further
> details, feel free to reach me.)
>
> The first step of the development plan is to prototype the new framework
> on open source. The idea is to *start prototyping now(!)* and have the
> discussion ongoing in parallel. The reason of such approach is to have code
> that can be used to inform those discussions, e.g., by collecting data and
> trying different designs approaches. Regarding the discussion, I have
> listed a few points where your feedbacks would be particularly appreciated
> (see Feedback Invite).
>
> Also, as I have mentioned in my talk, some issues are controversial but I
> expect them to be resolved during prototype development. Specifically
> theses concern aspects of legalization (should parts of it be done at the
> LLVM IR level or all at the MI level?) and code re-use for instruction
> combiner. Please feel free to bring up your specific concern as I move
> along with the development plan.
>
> I expect the design to evolve with our experimental findings and your
> feedbacks and contributions.
> Nonetheless, we expect to nail down some design decisions once and for all
> as the prototype progresses. I have highlighted them with the following
> pattern *[final]*.
>
>
>
> *** Feedback Invite ***
>
> If you follow and support this work you need to be aware of three things
> and I am eager to hear your feedback and thoughts about them: the overall
> goals of Global ISel, the goals of the prototype, and the impact of the
> prototype work on backend design.
>
> In the section “Goals", I defined (repeated for people that saw the
talk)
> the goals for the Global ISel design.
> - Do you see anything missing?
> - Do you see something that should not be there?
>
> The prototype will answer critical design questions (see “Design Questions
> the Prototype Addresses at the End of M1" for examples) before the
actual
> design of Gobal ISel is finalized, but it cannot cover everything.
> Specifically we will **not** look into improving TableGen or reuse
> InstCombine (see “ Proposed Approach” for the rational). Please let me know
> if you see any issue with that.
>
> There is also basic ground work needed to prepare for Global ISel and I
> need to extend the core MachineInstr-level APIs as explained during the
> talk. For this, I prepared sketches of patches to illustrate them and
> describe the details in the “Implications” section below. Please have a
> look at the patches to have a better idea of the expected impact.
>
> If there is anything else you want to discuss related to Global ISel feel
> free to reach me. In particular, several people expressed their interests
> during the LLVM Dev Meeting in contributing to the project. Let me know
> what is your area of interest, so that we can coordinate our efforts.
> Anyhow, please add [GlobalISel] in the subject line to help categorizing
> the emails.
>
>
>
> *** Goals ***
>
> The high level goals of the new instruction selector are:
> - Global instruction selector.
> - Fast instruction selector.
> - Shared code path for fast and good instruction selection.
> - IR that represents ISA concepts better.
> - More flexible instruction selector.
> - Easier to maintain/understand framework, in particular legalization.
> - Self contained machine representation, no back links to LLVM IR.
> - No change to LLVM IR.
>
> Note:  The goals are common to all targets. In particular, we do not
> intend to work on target specific feature for the prototype.
> The bottom line is please make sure those goals are compatible with what
> you want to achieve for your target, even if your requirement does not get
> listed here.
>
>
>
> *** 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 InstCombine *[final].* We will keep in mind however, that
> some of the C++ code we write will be table-generated at some point.
> The rational is that we do not want to lay down a new TableGen/InstCombine
> infrastructure before being able to work on the ISel framework itself.
>
> The prototype vehicle will be *AArch64*. None of the changes for
> GlobalISel will negatively impact the existing ISel.
>
>
> ** High Level Prototype Design **
>
> As shown in the talk, the expected pipeline for the prototype is:
> *LLVM IR *-> IRTranslator -> *Generic (G) MachineInstr* ->
Legalizer ->
> RegBankSelect -> Select -> *MachineInstr*
>
> Where:
> - Terms in *bold* are intermediate representations.
> -  Generic MachineInstrs are machine instructions with a generic opcode,
> e.g., ADD, COPY.
> - IRTranslator: Translate LLVM IR to (G) MachineInstr.
> - Legalizer: Legalize illegal (G) MachineInstr to legal (G) MachineInstr.
> - RegBankSelect: Assign virtual register with size to virtual register
> with Register Bank.
> - Select: Translate the remaining (G) MachineInstr to MachineIntr.
>
>
>
> ** 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.
>   - Need to know the type of each MachineInstr. We don’t want ADD8, ADD16,
> etc.
>   - Extend the MachineRegisterInfo to support size as well as register
> classes for virtual registers.
>
> I have sketched the changes in the attached patches to help picturing how
> the changes would impact the existing APIs.
>
> Note: I do not intend to commit those changes as they are. They will go
> the usual review process in due time.
>
> The patches contain “// ***”-like comment that give a rough explanation on
> why those changes are needed w.r.t. the goals.
> The order of the patches could be modified since the dependencies between
> those are not sequential. Anyhow, here are the patches:
> 1. Introduce (some of) the generic opcode.
> 2. Make MachineFunction more independent of LLVM IR to eventually be able
> to delete the LLVM IR instance from the memory.
> 3. Extend MachineInstr to represent additional information attached to
> generic opcode.
> 4. Teach MachineRegisterInfo about size for virtual registers.
> 5. Introduce a helper class to build MachineInstr related objects.
> 6. Add new target hooks to lower the ABI directly to MachineInstr.
> 7. Introduce the IRTranslator pass.
>
>
> ** Roadmap for the Prototype **
>
> We plan to split the prototype in three main milestones:
> 1. Translation: LLVM IR to (G) MachineInstr translation.
> 2. Basic selector: Legal LLVM IR to target specific MachineInstr.
> 3. Simple legalization: Support scalar type legalization and some vector
> instructions.
>
> Notes:
> - For #1, we will not support any fancy instructions like landing pad or
> switch.
> - Each milestone should take about 3-4 months.
> - At the end of #2, we would have a FastISel like selector.
>
> Each milestone will be detailed right before starting it. The rational is
> that we want to accommodate what we discovered with the prototype for the
> next milestone. In other words, in this email, *I only describe the first
> milestone* in detail and I will give more details on the next milestone
> shortly before we start it and so on. For your information, here is the
> remaining of the intended roadmap for the *full* project:
> 4. Productization: Clean up implementation, stabilize the APIs.
> 5. Complex legalization: Extend legalization support to everything missing.
> 6. Completeness: Fill the blanks, e.g., landing pad.
> 7. Clean-up and performance: Add the necessary bits to be at parity or
> beat SelectionDAG generated code.
> 8. Transition: Document how to switch, provide tools to help.
>
>
> ** Milestone 1 **
>
> The first phase is focused on the IRTranslator pass.
>
> The IRTranslator is responsible for translating the LLVM IR into Generic
> MachineInstr. The IRTranslator pass uses some target hooks to perform the
> ABI lowering. We can either define a new API for them, e.g.,
> ABILoweringInfo, or extend the existing TargetLowering.
> Moreover, the prototype will focus on simple instruction, i.e., we will
> not support switch or landing pad for this iteration.
>
> 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.
>
> * 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?
> - 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”?
>
> Thanks,
> -Quentin
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20151118/5a6d9a8c/attachment.html>

Hi Quentin,

On 18 Nov 2015, at 19:26, Quentin Colombet via llvm-dev <llvm-dev at
lists.llvm.org> wrote:
> 
> In the section “Goals", I defined (repeated for people that saw the
talk) the goals for the Global ISel design.
> - Do you see anything missing?
> - Do you see something that should not be there? 
I really like the design that you outlined.  I have one very small request:

Please maintain pointers as a distinct type from integers for as long as
possible.  We currently have some patches in SelectionDAG to add some
pointer-specific operations, as in our architecture the operations valid on
pointers are not the same as those valid on integers (and pointers are not the
same size as integers).  Your proposed model looks like it would be *much*
easier for us to use as long as that constraint is kept.  Various systems with
different integer and address registers hit the same problem as us.

Given the way that you’re proposing to do legalisation, this seems like it
should be easy (for most architectures, assigning pointers to the same register
bank as integers will be a simple choice and then all of the later selection
should be the same).

On a related note, keeping pointer address spaces around in the machine IR would
make things easier for us and, I think, some of the GPU folks.

David

Hi James,
> On Nov 18, 2015, at 11:53 AM, James Molloy <james at
jamesmolloy.co.uk> wrote:
> 
> Hi Quentin,
> 
> I'm really excited to see this happening!
> 
> My major question is over the testing story for this. How are we going to
write unit tests for GIR?
Thanks for bringing that up!
That is a very good question and also one that will require a lot of work to
address properly.

Ultimately, I’d like we are able to write unit tests directly in the
MachineInstr representation. Part of the goal of making the IR self contained,
i.e., with no back links to LLVM IR, is to make the testing easier.

Now, to answer the question on how we do that, I have a pragmatic answer, though
I am not proud of it:
We are going to write unit tests with LLVM IR as input and check the MI output
of the pass, e.g.,with print-after=IRTranslator.

That’s not great, but at least we can test now!
> Are you intending to leverage the LIR lowering that noone is using yet?
That’s a tricky question because I do not intend to work on this in the
prototype timeframe and I am not fond of the way this testing works.
However, yes, I believe that we need to redevelop or leverage the LIR lowering
for this purpose. Actually, I was looking for volunteers to work on that during
the prototype timeframe, so that we have everything we need when we productize
the new framework.

Interested? :P

Note: My main concern is that is uses a YAML format, i.e., we cannot dump the
output of a machine function and feed into it.
> Will you be using unit/LIT tests right from the start, or adding them in
later?
Definitely right from the start, with the “output” method I mentioned.
The hope is that a "LIR lowering" like mechanism will be developed
along the way and we can migrate tests to the new format when it is ready. If we
carefully design this "LIR lowering” format, we may just have to change the
RUN line :).

Thanks,
-Quentin
> 
> Cheers,
> 
> James
> 
> On Wed, 18 Nov 2015 at 19:27 Quentin Colombet via llvm-dev <llvm-dev at
lists.llvm.org <mailto:llvm-dev at lists.llvm.org>> wrote:
> Hi,
> 
> With this email, I would like to kick-off the development for the next
instruction selector that I described during the last LLVM Dev’ Meeting.
> For the motivations, see Jakob’s proposal
(http://lists.cs.uiuc.edu/pipermail/llvmdev/2013-August/064727.html
<http://lists.cs.uiuc.edu/pipermail/llvmdev/2013-August/064727.html>) and
for the proposal, see the slides (Keynote:
http://llvm.org/viewvc/llvm-project/www/trunk/devmtg/2015-10/slides/Colombet-GlobalInstructionSelection.key?view=co
<http://llvm.org/viewvc/llvm-project/www/trunk/devmtg/2015-10/slides/Colombet-GlobalInstructionSelection.key?view=co>
or PDF:
http://llvm.org/viewvc/llvm-project/www/trunk/devmtg/2015-10/slides/Colombet-GlobalInstructionSelection.pdf?revision=252430&view=co
<http://llvm.org/viewvc/llvm-project/www/trunk/devmtg/2015-10/slides/Colombet-GlobalInstructionSelection.pdf?revision=252430&view=co>)
or the talk
(https://www.youtube.com/watch?v=F6GGbYtae3g&list=PL_R5A0lGi1AA4Lv2bBFSwhgDaHvvpVU21&index=2
<https://www.youtube.com/watch?v=F6GGbYtae3g&list=PL_R5A0lGi1AA4Lv2bBFSwhgDaHvvpVU21&index=2>).
> 
> TL;DR This is happening now, feedbacks invited!
> 
> *** Context ***
> 
> During the last LLVM Dev’ Meeting, I have presented a proposal for the next
instruction selector, GlobalISel. The proposal is basically summarized in
"High Level Prototype Design” and “Roadmap”. (If you want further details,
feel free to reach me.)
> 
> The first step of the development plan is to prototype the new framework on
open source. The idea is to start prototyping now(!) and have the discussion
ongoing in parallel. The reason of such approach is to have code that can be
used to inform those discussions, e.g., by collecting data and trying different
designs approaches. Regarding the discussion, I have listed a few points where
your feedbacks would be particularly appreciated (see Feedback Invite).
> 
> Also, as I have mentioned in my talk, some issues are controversial but I
expect them to be resolved during prototype development. Specifically theses
concern aspects of legalization (should parts of it be done at the LLVM IR level
or all at the MI level?) and code re-use for instruction combiner. Please feel
free to bring up your specific concern as I move along with the development
plan.
> 
> I expect the design to evolve with our experimental findings and your
feedbacks and contributions.
> Nonetheless, we expect to nail down some design decisions once and for all
as the prototype progresses. I have highlighted them with the following pattern
[final].
> 
> 
> 
> *** Feedback Invite ***
> 
> If you follow and support this work you need to be aware of three things
and I am eager to hear your feedback and thoughts about them: the overall goals
of Global ISel, the goals of the prototype, and the impact of the prototype work
on backend design.
> 
> In the section “Goals", I defined (repeated for people that saw the
talk) the goals for the Global ISel design.
> - Do you see anything missing?
> - Do you see something that should not be there? 
> 
> The prototype will answer critical design questions (see “Design Questions
the Prototype Addresses at the End of M1" for examples) before the actual
design of Gobal ISel is finalized, but it cannot cover everything.
> Specifically we will *not* look into improving TableGen or reuse
InstCombine (see “ Proposed Approach” for the rational). Please let me know if
you see any issue with that.
> 
> There is also basic ground work needed to prepare for Global ISel and I
need to extend the core MachineInstr-level APIs as explained during the talk.
For this, I prepared sketches of patches to illustrate them and describe the
details in the “Implications” section below. Please have a look at the patches
to have a better idea of the expected impact.
> 
> If there is anything else you want to discuss related to Global ISel feel
free to reach me. In particular, several people expressed their interests during
the LLVM Dev Meeting in contributing to the project. Let me know what is your
area of interest, so that we can coordinate our efforts.
> Anyhow, please add [GlobalISel] in the subject line to help categorizing
the emails.
> 
> 
> 
> *** Goals ***
> 
> The high level goals of the new instruction selector are:
> - Global instruction selector.
> - Fast instruction selector.
> - Shared code path for fast and good instruction selection.
> - IR that represents ISA concepts better.
> - More flexible instruction selector.
> - Easier to maintain/understand framework, in particular legalization.
> - Self contained machine representation, no back links to LLVM IR.
> - No change to LLVM IR.
> 
> Note:  The goals are common to all targets. In particular, we do not intend
to work on target specific feature for the prototype.
> The bottom line is please make sure those goals are compatible with what
you want to achieve for your target, even if your requirement does not get
listed here.
> 
> 
> 
> *** 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 InstCombine [final]. We will keep in mind however, that some of the
C++ code we write will be table-generated at some point.
> The rational is that we do not want to lay down a new TableGen/InstCombine
infrastructure before being able to work on the ISel framework itself.
> 
> The prototype vehicle will be AArch64. None of the changes for GlobalISel
will negatively impact the existing ISel.
> 
> 
> ** High Level Prototype Design **
> 
> As shown in the talk, the expected pipeline for the prototype is:
> LLVM IR -> IRTranslator -> Generic (G) MachineInstr -> Legalizer
-> RegBankSelect -> Select -> MachineInstr
> 
> Where:
> - Terms in bold are intermediate representations.
> -  Generic MachineInstrs are machine instructions with a generic opcode,
e.g., ADD, COPY.
> - IRTranslator: Translate LLVM IR to (G) MachineInstr.
> - Legalizer: Legalize illegal (G) MachineInstr to legal (G) MachineInstr.
> - RegBankSelect: Assign virtual register with size to virtual register with
Register Bank.
> - Select: Translate the remaining (G) MachineInstr to MachineIntr.
> 
> 
> 
> ** 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.
>   - Need to know the type of each MachineInstr. We don’t want ADD8, ADD16,
etc.
>   - Extend the MachineRegisterInfo to support size as well as register
classes for virtual registers.
> 
> I have sketched the changes in the attached patches to help picturing how
the changes would impact the existing APIs.
> 
> Note: I do not intend to commit those changes as they are. They will go the
usual review process in due time.
> 
> The patches contain “// ***”-like comment that give a rough explanation on
why those changes are needed w.r.t. the goals.
> The order of the patches could be modified since the dependencies between
those are not sequential. Anyhow, here are the patches:
> 1. Introduce (some of) the generic opcode.
> 2. Make MachineFunction more independent of LLVM IR to eventually be able
to delete the LLVM IR instance from the memory.
> 3. Extend MachineInstr to represent additional information attached to
generic opcode.
> 4. Teach MachineRegisterInfo about size for virtual registers.
> 5. Introduce a helper class to build MachineInstr related objects.
> 6. Add new target hooks to lower the ABI directly to MachineInstr.
> 7. Introduce the IRTranslator pass.
> 
> 
> ** Roadmap for the Prototype **
> 
> We plan to split the prototype in three main milestones:
> 1. Translation: LLVM IR to (G) MachineInstr translation.
> 2. Basic selector: Legal LLVM IR to target specific MachineInstr.
> 3. Simple legalization: Support scalar type legalization and some vector
instructions.
> 
> Notes:
> - For #1, we will not support any fancy instructions like landing pad or
switch.
> - Each milestone should take about 3-4 months.
> - At the end of #2, we would have a FastISel like selector.
> 
> Each milestone will be detailed right before starting it. The rational is
that we want to accommodate what we discovered with the prototype for the next
milestone. In other words, in this email, I only describe the first milestone in
detail and I will give more details on the next milestone shortly before we
start it and so on. For your information, here is the remaining of the intended
roadmap for the full project:
> 4. Productization: Clean up implementation, stabilize the APIs.
> 5. Complex legalization: Extend legalization support to everything missing.
> 6. Completeness: Fill the blanks, e.g., landing pad.
> 7. Clean-up and performance: Add the necessary bits to be at parity or beat
SelectionDAG generated code.
> 8. Transition: Document how to switch, provide tools to help.
> 
> 
> ** Milestone 1 **
> 
> The first phase is focused on the IRTranslator pass.
> 
> The IRTranslator is responsible for translating the LLVM IR into Generic
MachineInstr. The IRTranslator pass uses some target hooks to perform the ABI
lowering. We can either define a new API for them, e.g., ABILoweringInfo, or
extend the existing TargetLowering.
> Moreover, the prototype will focus on simple instruction, i.e., we will not
support switch or landing pad for this iteration.
> 
> 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.
> 
> * 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?
> - 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”?
> 
> Thanks,
> -Quentin
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org <mailto:llvm-dev at lists.llvm.org>
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
<http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20151118/7a5aaf08/attachment-0001.html>

Thanks Quentin for the effort in putting this together!!

I’m super excited in seeing this going forward and I’m looking forward in
helping in bringing GlobalISel up as much as I can as it is very promising for
our targets!
It also catched my eye that you mentioned the possibility of having Module level
Machine passes.
Having that would simplify some parts of our pipeline for example I believe as
now we are using some hacks to obtain basically the same result at the very end
of the pipeline.
This would be useful at least for us!

Marcello
> On 18 Nov 2015, at 11:26, Quentin Colombet via llvm-dev <llvm-dev at
lists.llvm.org> wrote:
> 
> Hi,
> 
> With this email, I would like to kick-off the development for the next
instruction selector that I described during the last LLVM Dev’ Meeting.
> For the motivations, see Jakob’s proposal
(http://lists.cs.uiuc.edu/pipermail/llvmdev/2013-August/064727.html
<http://lists.cs.uiuc.edu/pipermail/llvmdev/2013-August/064727.html>) and
for the proposal, see the slides (Keynote:
http://llvm.org/viewvc/llvm-project/www/trunk/devmtg/2015-10/slides/Colombet-GlobalInstructionSelection.key?view=co
<http://llvm.org/viewvc/llvm-project/www/trunk/devmtg/2015-10/slides/Colombet-GlobalInstructionSelection.key?view=co>
or PDF:
http://llvm.org/viewvc/llvm-project/www/trunk/devmtg/2015-10/slides/Colombet-GlobalInstructionSelection.pdf?revision=252430&view=co
<http://llvm.org/viewvc/llvm-project/www/trunk/devmtg/2015-10/slides/Colombet-GlobalInstructionSelection.pdf?revision=252430&view=co>)
or the talk
(https://www.youtube.com/watch?v=F6GGbYtae3g&list=PL_R5A0lGi1AA4Lv2bBFSwhgDaHvvpVU21&index=2
<https://www.youtube.com/watch?v=F6GGbYtae3g&list=PL_R5A0lGi1AA4Lv2bBFSwhgDaHvvpVU21&index=2>).
> 
> TL;DR This is happening now, feedbacks invited!
> 
> *** Context ***
> 
> During the last LLVM Dev’ Meeting, I have presented a proposal for the next
instruction selector, GlobalISel. The proposal is basically summarized in
"High Level Prototype Design” and “Roadmap”. (If you want further details,
feel free to reach me.)
> 
> The first step of the development plan is to prototype the new framework on
open source. The idea is to start prototyping now(!) and have the discussion
ongoing in parallel. The reason of such approach is to have code that can be
used to inform those discussions, e.g., by collecting data and trying different
designs approaches. Regarding the discussion, I have listed a few points where
your feedbacks would be particularly appreciated (see Feedback Invite).
> 
> Also, as I have mentioned in my talk, some issues are controversial but I
expect them to be resolved during prototype development. Specifically theses
concern aspects of legalization (should parts of it be done at the LLVM IR level
or all at the MI level?) and code re-use for instruction combiner. Please feel
free to bring up your specific concern as I move along with the development
plan.
> 
> I expect the design to evolve with our experimental findings and your
feedbacks and contributions.
> Nonetheless, we expect to nail down some design decisions once and for all
as the prototype progresses. I have highlighted them with the following pattern
[final].
> 
> 
> 
> *** Feedback Invite ***
> 
> If you follow and support this work you need to be aware of three things
and I am eager to hear your feedback and thoughts about them: the overall goals
of Global ISel, the goals of the prototype, and the impact of the prototype work
on backend design.
> 
> In the section “Goals", I defined (repeated for people that saw the
talk) the goals for the Global ISel design.
> - Do you see anything missing?
> - Do you see something that should not be there? 
> 
> The prototype will answer critical design questions (see “Design Questions
the Prototype Addresses at the End of M1" for examples) before the actual
design of Gobal ISel is finalized, but it cannot cover everything.
> Specifically we will *not* look into improving TableGen or reuse
InstCombine (see “ Proposed Approach” for the rational). Please let me know if
you see any issue with that.
> 
> There is also basic ground work needed to prepare for Global ISel and I
need to extend the core MachineInstr-level APIs as explained during the talk.
For this, I prepared sketches of patches to illustrate them and describe the
details in the “Implications” section below. Please have a look at the patches
to have a better idea of the expected impact.
> 
> If there is anything else you want to discuss related to Global ISel feel
free to reach me. In particular, several people expressed their interests during
the LLVM Dev Meeting in contributing to the project. Let me know what is your
area of interest, so that we can coordinate our efforts.
> Anyhow, please add [GlobalISel] in the subject line to help categorizing
the emails.
> 
> 
> 
> *** Goals ***
> 
> The high level goals of the new instruction selector are:
> - Global instruction selector.
> - Fast instruction selector.
> - Shared code path for fast and good instruction selection.
> - IR that represents ISA concepts better.
> - More flexible instruction selector.
> - Easier to maintain/understand framework, in particular legalization.
> - Self contained machine representation, no back links to LLVM IR.
> - No change to LLVM IR.
> 
> Note:  The goals are common to all targets. In particular, we do not intend
to work on target specific feature for the prototype.
> The bottom line is please make sure those goals are compatible with what
you want to achieve for your target, even if your requirement does not get
listed here.
> 
> 
> 
> *** 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 InstCombine [final]. We will keep in mind however, that some of the
C++ code we write will be table-generated at some point.
> The rational is that we do not want to lay down a new TableGen/InstCombine
infrastructure before being able to work on the ISel framework itself.
> 
> The prototype vehicle will be AArch64. None of the changes for GlobalISel
will negatively impact the existing ISel.
> 
> 
> ** High Level Prototype Design **
> 
> As shown in the talk, the expected pipeline for the prototype is:
> LLVM IR -> IRTranslator -> Generic (G) MachineInstr -> Legalizer
-> RegBankSelect -> Select -> MachineInstr
> 
> Where:
> - Terms in bold are intermediate representations.
> -  Generic MachineInstrs are machine instructions with a generic opcode,
e.g., ADD, COPY.
> - IRTranslator: Translate LLVM IR to (G) MachineInstr.
> - Legalizer: Legalize illegal (G) MachineInstr to legal (G) MachineInstr.
> - RegBankSelect: Assign virtual register with size to virtual register with
Register Bank.
> - Select: Translate the remaining (G) MachineInstr to MachineIntr.
> 
> 
> 
> ** 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.
>   - Need to know the type of each MachineInstr. We don’t want ADD8, ADD16,
etc.
>   - Extend the MachineRegisterInfo to support size as well as register
classes for virtual registers.
> 
> I have sketched the changes in the attached patches to help picturing how
the changes would impact the existing APIs.
> 
> Note: I do not intend to commit those changes as they are. They will go the
usual review process in due time.
> 
> The patches contain “// ***”-like comment that give a rough explanation on
why those changes are needed w.r.t. the goals.
> The order of the patches could be modified since the dependencies between
those are not sequential. Anyhow, here are the patches:
> 1. Introduce (some of) the generic opcode.
> 2. Make MachineFunction more independent of LLVM IR to eventually be able
to delete the LLVM IR instance from the memory.
> 3. Extend MachineInstr to represent additional information attached to
generic opcode.
> 4. Teach MachineRegisterInfo about size for virtual registers.
> 5. Introduce a helper class to build MachineInstr related objects.
> 6. Add new target hooks to lower the ABI directly to MachineInstr.
> 7. Introduce the IRTranslator pass.
> 
> 
> ** Roadmap for the Prototype **
> 
> We plan to split the prototype in three main milestones:
> 1. Translation: LLVM IR to (G) MachineInstr translation.
> 2. Basic selector: Legal LLVM IR to target specific MachineInstr.
> 3. Simple legalization: Support scalar type legalization and some vector
instructions.
> 
> Notes:
> - For #1, we will not support any fancy instructions like landing pad or
switch.
> - Each milestone should take about 3-4 months.
> - At the end of #2, we would have a FastISel like selector.
> 
> Each milestone will be detailed right before starting it. The rational is
that we want to accommodate what we discovered with the prototype for the next
milestone. In other words, in this email, I only describe the first milestone in
detail and I will give more details on the next milestone shortly before we
start it and so on. For your information, here is the remaining of the intended
roadmap for the full project:
> 4. Productization: Clean up implementation, stabilize the APIs.
> 5. Complex legalization: Extend legalization support to everything missing.
> 6. Completeness: Fill the blanks, e.g., landing pad.
> 7. Clean-up and performance: Add the necessary bits to be at parity or beat
SelectionDAG generated code.
> 8. Transition: Document how to switch, provide tools to help.
> 
> 
> ** Milestone 1 **
> 
> The first phase is focused on the IRTranslator pass.
> 
> The IRTranslator is responsible for translating the LLVM IR into Generic
MachineInstr. The IRTranslator pass uses some target hooks to perform the ABI
lowering. We can either define a new API for them, e.g., ABILoweringInfo, or
extend the existing TargetLowering.
> Moreover, the prototype will focus on simple instruction, i.e., we will not
support switch or landing pad for this iteration.
> 
> 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.
> 
> * 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?
> - 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”?
> 
> Thanks,
> -Quentin
> <0001-Extend-generic-opcodes-to-be-able-to-represent-the-i.patch>
> <0002-Pull-more-of-the-LLVM-IR-function-representation-int.patch>
> <0003-Extend-MachineInstr-to-supply-more-information-regar.patch>
> <0004-Teach-MachineRegisterInfo-about-size-for-virtual-reg.patch>
> <0005-Introduce-a-MachineIRBuilder-to-gather-all-the-Machi.patch>
> <0006-Add-new-target-hooks-to-be-able-to-lower-the-ABI-rig.patch>
> <0007-Introduce-the-IRtranslator-pass-for-GlobalISel.patch>
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20151118/7a72c393/attachment.html>

Hi David,

> On Nov 18, 2015, at 11:55 AM, David Chisnall <David.Chisnall at
cl.cam.ac.uk> wrote:
> 
> Hi Quentin,
> 
> On 18 Nov 2015, at 19:26, Quentin Colombet via llvm-dev <llvm-dev at
lists.llvm.org> wrote:
>> 
>> In the section “Goals", I defined (repeated for people that saw
the talk) the goals for the Global ISel design.
>> - Do you see anything missing?
>> - Do you see something that should not be there? 
> 
> I really like the design that you outlined.  I have one very small request:
> 
> Please maintain pointers as a distinct type from integers for as long as
possible.  We currently have some patches in SelectionDAG to add some
pointer-specific operations, as in our architecture the operations valid on
pointers are not the same as those valid on integers (and pointers are not the
same size as integers).  Your proposed model looks like it would be *much*
easier for us to use as long as that constraint is kept.  Various systems with
different integer and address registers hit the same problem as us.
I understand the problem, but I feel like Jakob back in the day:
http://lists.llvm.org/pipermail/llvm-dev/2013-August/064734.html
http://lists.llvm.org/pipermail/llvm-dev/2013-August/064760.html

To summarize with my own words and feelings that gives:
To me the pointer/integer distinction is a way for you to specify the register
classes you want. This is something the RegBankSelect pass will do for you and
this distinction should not be necessary to produce efficient or correct code.

If that doesn’t work, you should be able to have target specific pass to select
what you want directly after the translation or with a custom translation. One
can envision some kind of IRTranslationKit that has all the generic translation
build into to help you in such case.

Anyway, the good point with the prototype is that we will be able to experiment
these things :).
> 
> Given the way that you’re proposing to do legalisation, this seems like it
should be easy (for most architectures, assigning pointers to the same register
bank as integers will be a simple choice and then all of the later selection
should be the same).
> 
> On a related note, keeping pointer address spaces around in the machine IR
would make things easier for us and, I think, some of the GPU folks.
Good point, this is also something that the MachineInstr should also expose as
part of the make the IR self contained.

Thanks,
-Quentin
> 
> David
>

Hi Marcello,
> On Nov 18, 2015, at 3:06 PM, Marcello Maggioni <mmaggioni at
apple.com> wrote:
> 
> Thanks Quentin for the effort in putting this together!!
> 
> I’m super excited in seeing this going forward and I’m looking forward in
helping in bringing GlobalISel up as much as I can as it is very promising for
our targets!
> It also catched my eye that you mentioned the possibility of having Module
level Machine passes.
> Having that would simplify some parts of our pipeline for example I believe
as now we are using some hacks to obtain basically the same result at the very
end of the pipeline.
> This would be useful at least for us!
Good to know!
Right now, I was considering it for the "LLVM IR -> MachineInstr"
translation because if we want to go all the way down everything in
MachineInstr, we need to lower the global variables as well, and this
conceptually does not fit into a function-like pass.
Knowing that there are other users of that sounds like it would indeed by good
to have it!

Thanks for your feedbacks!

Cheers,
-Quentin
> 
> Marcello
> 
>> On 18 Nov 2015, at 11:26, Quentin Colombet via llvm-dev <llvm-dev at
lists.llvm.org <mailto:llvm-dev at lists.llvm.org>> wrote:
>> 
>> Hi,
>> 
>> With this email, I would like to kick-off the development for the next
instruction selector that I described during the last LLVM Dev’ Meeting.
>> For the motivations, see Jakob’s proposal
(http://lists.cs.uiuc.edu/pipermail/llvmdev/2013-August/064727.html
<http://lists.cs.uiuc.edu/pipermail/llvmdev/2013-August/064727.html>) and
for the proposal, see the slides (Keynote:
http://llvm.org/viewvc/llvm-project/www/trunk/devmtg/2015-10/slides/Colombet-GlobalInstructionSelection.key?view=co
<http://llvm.org/viewvc/llvm-project/www/trunk/devmtg/2015-10/slides/Colombet-GlobalInstructionSelection.key?view=co>
or PDF:
http://llvm.org/viewvc/llvm-project/www/trunk/devmtg/2015-10/slides/Colombet-GlobalInstructionSelection.pdf?revision=252430&view=co
<http://llvm.org/viewvc/llvm-project/www/trunk/devmtg/2015-10/slides/Colombet-GlobalInstructionSelection.pdf?revision=252430&view=co>)
or the talk
(https://www.youtube.com/watch?v=F6GGbYtae3g&list=PL_R5A0lGi1AA4Lv2bBFSwhgDaHvvpVU21&index=2
<https://www.youtube.com/watch?v=F6GGbYtae3g&list=PL_R5A0lGi1AA4Lv2bBFSwhgDaHvvpVU21&index=2>).
>> 
>> TL;DR This is happening now, feedbacks invited!
>> 
>> *** Context ***
>> 
>> During the last LLVM Dev’ Meeting, I have presented a proposal for the
next instruction selector, GlobalISel. The proposal is basically summarized in
"High Level Prototype Design” and “Roadmap”. (If you want further details,
feel free to reach me.)
>> 
>> The first step of the development plan is to prototype the new
framework on open source. The idea is to start prototyping now(!) and have the
discussion ongoing in parallel. The reason of such approach is to have code that
can be used to inform those discussions, e.g., by collecting data and trying
different designs approaches. Regarding the discussion, I have listed a few
points where your feedbacks would be particularly appreciated (see Feedback
Invite).
>> 
>> Also, as I have mentioned in my talk, some issues are controversial but
I expect them to be resolved during prototype development. Specifically theses
concern aspects of legalization (should parts of it be done at the LLVM IR level
or all at the MI level?) and code re-use for instruction combiner. Please feel
free to bring up your specific concern as I move along with the development
plan.
>> 
>> I expect the design to evolve with our experimental findings and your
feedbacks and contributions.
>> Nonetheless, we expect to nail down some design decisions once and for
all as the prototype progresses. I have highlighted them with the following
pattern [final].
>> 
>> 
>> 
>> *** Feedback Invite ***
>> 
>> If you follow and support this work you need to be aware of three
things and I am eager to hear your feedback and thoughts about them: the overall
goals of Global ISel, the goals of the prototype, and the impact of the
prototype work on backend design.
>> 
>> In the section “Goals", I defined (repeated for people that saw
the talk) the goals for the Global ISel design.
>> - Do you see anything missing?
>> - Do you see something that should not be there? 
>> 
>> The prototype will answer critical design questions (see “Design
Questions the Prototype Addresses at the End of M1" for examples) before
the actual design of Gobal ISel is finalized, but it cannot cover everything.
>> Specifically we will *not* look into improving TableGen or reuse
InstCombine (see “ Proposed Approach” for the rational). Please let me know if
you see any issue with that.
>> 
>> There is also basic ground work needed to prepare for Global ISel and I
need to extend the core MachineInstr-level APIs as explained during the talk.
For this, I prepared sketches of patches to illustrate them and describe the
details in the “Implications” section below. Please have a look at the patches
to have a better idea of the expected impact.
>> 
>> If there is anything else you want to discuss related to Global ISel
feel free to reach me. In particular, several people expressed their interests
during the LLVM Dev Meeting in contributing to the project. Let me know what is
your area of interest, so that we can coordinate our efforts.
>> Anyhow, please add [GlobalISel] in the subject line to help
categorizing the emails.
>> 
>> 
>> 
>> *** Goals ***
>> 
>> The high level goals of the new instruction selector are:
>> - Global instruction selector.
>> - Fast instruction selector.
>> - Shared code path for fast and good instruction selection.
>> - IR that represents ISA concepts better.
>> - More flexible instruction selector.
>> - Easier to maintain/understand framework, in particular legalization.
>> - Self contained machine representation, no back links to LLVM IR.
>> - No change to LLVM IR.
>> 
>> Note:  The goals are common to all targets. In particular, we do not
intend to work on target specific feature for the prototype.
>> The bottom line is please make sure those goals are compatible with
what you want to achieve for your target, even if your requirement does not get
listed here.
>> 
>> 
>> 
>> *** 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 InstCombine [final]. We will keep in mind however, that some of the
C++ code we write will be table-generated at some point.
>> The rational is that we do not want to lay down a new
TableGen/InstCombine infrastructure before being able to work on the ISel
framework itself.
>> 
>> The prototype vehicle will be AArch64. None of the changes for
GlobalISel will negatively impact the existing ISel.
>> 
>> 
>> ** High Level Prototype Design **
>> 
>> As shown in the talk, the expected pipeline for the prototype is:
>> LLVM IR -> IRTranslator -> Generic (G) MachineInstr ->
Legalizer -> RegBankSelect -> Select -> MachineInstr
>> 
>> Where:
>> - Terms in bold are intermediate representations.
>> -  Generic MachineInstrs are machine instructions with a generic
opcode, e.g., ADD, COPY.
>> - IRTranslator: Translate LLVM IR to (G) MachineInstr.
>> - Legalizer: Legalize illegal (G) MachineInstr to legal (G)
MachineInstr.
>> - RegBankSelect: Assign virtual register with size to virtual register
with Register Bank.
>> - Select: Translate the remaining (G) MachineInstr to MachineIntr.
>> 
>> 
>> 
>> ** 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.
>>   - Need to know the type of each MachineInstr. We don’t want ADD8,
ADD16, etc.
>>   - Extend the MachineRegisterInfo to support size as well as register
classes for virtual registers.
>> 
>> I have sketched the changes in the attached patches to help picturing
how the changes would impact the existing APIs.
>> 
>> Note: I do not intend to commit those changes as they are. They will go
the usual review process in due time.
>> 
>> The patches contain “// ***”-like comment that give a rough explanation
on why those changes are needed w.r.t. the goals.
>> The order of the patches could be modified since the dependencies
between those are not sequential. Anyhow, here are the patches:
>> 1. Introduce (some of) the generic opcode.
>> 2. Make MachineFunction more independent of LLVM IR to eventually be
able to delete the LLVM IR instance from the memory.
>> 3. Extend MachineInstr to represent additional information attached to
generic opcode.
>> 4. Teach MachineRegisterInfo about size for virtual registers.
>> 5. Introduce a helper class to build MachineInstr related objects.
>> 6. Add new target hooks to lower the ABI directly to MachineInstr.
>> 7. Introduce the IRTranslator pass.
>> 
>> 
>> ** Roadmap for the Prototype **
>> 
>> We plan to split the prototype in three main milestones:
>> 1. Translation: LLVM IR to (G) MachineInstr translation.
>> 2. Basic selector: Legal LLVM IR to target specific MachineInstr.
>> 3. Simple legalization: Support scalar type legalization and some
vector instructions.
>> 
>> Notes:
>> - For #1, we will not support any fancy instructions like landing pad
or switch.
>> - Each milestone should take about 3-4 months.
>> - At the end of #2, we would have a FastISel like selector.
>> 
>> Each milestone will be detailed right before starting it. The rational
is that we want to accommodate what we discovered with the prototype for the
next milestone. In other words, in this email, I only describe the first
milestone in detail and I will give more details on the next milestone shortly
before we start it and so on. For your information, here is the remaining of the
intended roadmap for the full project:
>> 4. Productization: Clean up implementation, stabilize the APIs.
>> 5. Complex legalization: Extend legalization support to everything
missing.
>> 6. Completeness: Fill the blanks, e.g., landing pad.
>> 7. Clean-up and performance: Add the necessary bits to be at parity or
beat SelectionDAG generated code.
>> 8. Transition: Document how to switch, provide tools to help.
>> 
>> 
>> ** Milestone 1 **
>> 
>> The first phase is focused on the IRTranslator pass.
>> 
>> The IRTranslator is responsible for translating the LLVM IR into
Generic MachineInstr. The IRTranslator pass uses some target hooks to perform
the ABI lowering. We can either define a new API for them, e.g.,
ABILoweringInfo, or extend the existing TargetLowering.
>> Moreover, the prototype will focus on simple instruction, i.e., we will
not support switch or landing pad for this iteration.
>> 
>> 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.
>> 
>> * 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?
>> - 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”?
>> 
>> Thanks,
>> -Quentin
>> <0001-Extend-generic-opcodes-to-be-able-to-represent-the-i.patch>
>> <0002-Pull-more-of-the-LLVM-IR-function-representation-int.patch>
>> <0003-Extend-MachineInstr-to-supply-more-information-regar.patch>
>> <0004-Teach-MachineRegisterInfo-about-size-for-virtual-reg.patch>
>> <0005-Introduce-a-MachineIRBuilder-to-gather-all-the-Machi.patch>
>> <0006-Add-new-target-hooks-to-be-able-to-lower-the-ABI-rig.patch>
>> <0007-Introduce-the-IRtranslator-pass-for-GlobalISel.patch>
>> _______________________________________________
>> LLVM Developers mailing list
>> llvm-dev at lists.llvm.org <mailto:llvm-dev at lists.llvm.org>
>> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
> 
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20151118/d1e8c144/attachment.html>

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.

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

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

> *** 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? ;)

>
> ** 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?

> 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? (Better name perhaps?).
Which means that it should be serializable and testable in isolation yes?

> * 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?

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

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.

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/d25675ed/attachment.html>

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>

Hi,

I haven't had chance to read all of this yet, but one minor thing occurred
to me during your presentation that I want to mention. At one point you
mentioned deleting all the bitcast instructions since they're equivalent to
nops but this isn't always true.

The http://llvm.org/docs/LangRef.html definition of the bitcast instruction
includes this sentence:
The conversion is done as if the value had been stored to memory and read back
as type ty2.
For big-endian MSA, this is equivalent to a shuffling of the bits in the
register because endianness only changes the byte order within each element. The
order of the elements is unaffected by endianness. IIRC, big-endian NEON is the
same way.

From: llvm-dev [mailto:llvm-dev-bounces at lists.llvm.org] On Behalf Of Quentin
Colombet via llvm-dev
Sent: 18 November 2015 19:27
To: llvm-dev
Subject: [llvm-dev] [GlobalISel] A Proposal for global instruction selection

Hi,

With this email, I would like to kick-off the development for the next
instruction selector that I described during the last LLVM Dev’ Meeting.
For the motivations, see Jakob’s proposal
(http://lists.cs.uiuc.edu/pipermail/llvmdev/2013-August/064727.html) and for the
proposal, see the slides (Keynote:
http://llvm.org/viewvc/llvm-project/www/trunk/devmtg/2015-10/slides/Colombet-GlobalInstructionSelection.key?view=co
or PDF:
http://llvm.org/viewvc/llvm-project/www/trunk/devmtg/2015-10/slides/Colombet-GlobalInstructionSelection.pdf?revision=252430&view=co)
or the talk
(https://www.youtube.com/watch?v=F6GGbYtae3g&list=PL_R5A0lGi1AA4Lv2bBFSwhgDaHvvpVU21&index=2).

TL;DR This is happening now, feedbacks invited!

*** Context ***

During the last LLVM Dev’ Meeting, I have presented a proposal for the next
instruction selector, GlobalISel. The proposal is basically summarized in
"High Level Prototype Design” and “Roadmap”. (If you want further details,
feel free to reach me.)

The first step of the development plan is to prototype the new framework on open
source. The idea is to start prototyping now(!) and have the discussion ongoing
in parallel. The reason of such approach is to have code that can be used to
inform those discussions, e.g., by collecting data and trying different designs
approaches. Regarding the discussion, I have listed a few points where your
feedbacks would be particularly appreciated (see Feedback Invite).

Also, as I have mentioned in my talk, some issues are controversial but I expect
them to be resolved during prototype development. Specifically theses concern
aspects of legalization (should parts of it be done at the LLVM IR level or all
at the MI level?) and code re-use for instruction combiner. Please feel free to
bring up your specific concern as I move along with the development plan.

I expect the design to evolve with our experimental findings and your feedbacks
and contributions.
Nonetheless, we expect to nail down some design decisions once and for all as
the prototype progresses. I have highlighted them with the following pattern
[final].



*** Feedback Invite ***

If you follow and support this work you need to be aware of three things and I
am eager to hear your feedback and thoughts about them: the overall goals of
Global ISel, the goals of the prototype, and the impact of the prototype work on
backend design.

In the section “Goals", I defined (repeated for people that saw the talk)
the goals for the Global ISel design.
- Do you see anything missing?
- Do you see something that should not be there?

The prototype will answer critical design questions (see “Design Questions the
Prototype Addresses at the End of M1" for examples) before the actual
design of Gobal ISel is finalized, but it cannot cover everything.
Specifically we will *not* look into improving TableGen or reuse InstCombine
(see “ Proposed Approach” for the rational). Please let me know if you see any
issue with that.

There is also basic ground work needed to prepare for Global ISel and I need to
extend the core MachineInstr-level APIs as explained during the talk. For this,
I prepared sketches of patches to illustrate them and describe the details in
the “Implications” section below. Please have a look at the patches to have a
better idea of the expected impact.

If there is anything else you want to discuss related to Global ISel feel free
to reach me. In particular, several people expressed their interests during the
LLVM Dev Meeting in contributing to the project. Let me know what is your area
of interest, so that we can coordinate our efforts.
Anyhow, please add [GlobalISel] in the subject line to help categorizing the
emails.



*** Goals ***

The high level goals of the new instruction selector are:
- Global instruction selector.
- Fast instruction selector.
- Shared code path for fast and good instruction selection.
- IR that represents ISA concepts better.
- More flexible instruction selector.
- Easier to maintain/understand framework, in particular legalization.
- Self contained machine representation, no back links to LLVM IR.
- No change to LLVM IR.

Note:  The goals are common to all targets. In particular, we do not intend to
work on target specific feature for the prototype.
The bottom line is please make sure those goals are compatible with what you
want to achieve for your target, even if your requirement does not get listed
here.



*** 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
InstCombine [final]. We will keep in mind however, that some of the C++ code we
write will be table-generated at some point.
The rational is that we do not want to lay down a new TableGen/InstCombine
infrastructure before being able to work on the ISel framework itself.

The prototype vehicle will be AArch64. None of the changes for GlobalISel will
negatively impact the existing ISel.


** High Level Prototype Design **

As shown in the talk, the expected pipeline for the prototype is:
LLVM IR -> IRTranslator -> Generic (G) MachineInstr -> Legalizer ->
RegBankSelect -> Select -> MachineInstr

Where:
- Terms in bold are intermediate representations.
-  Generic MachineInstrs are machine instructions with a generic opcode, e.g.,
ADD, COPY.
- IRTranslator: Translate LLVM IR to (G) MachineInstr.
- Legalizer: Legalize illegal (G) MachineInstr to legal (G) MachineInstr.
- RegBankSelect: Assign virtual register with size to virtual register with
Register Bank.
- Select: Translate the remaining (G) MachineInstr to MachineIntr.



** 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.
  - Need to know the type of each MachineInstr. We don’t want ADD8, ADD16, etc.
  - Extend the MachineRegisterInfo to support size as well as register classes
for virtual registers.

I have sketched the changes in the attached patches to help picturing how the
changes would impact the existing APIs.

Note: I do not intend to commit those changes as they are. They will go the
usual review process in due time.

The patches contain “// ***”-like comment that give a rough explanation on why
those changes are needed w.r.t. the goals.
The order of the patches could be modified since the dependencies between those
are not sequential. Anyhow, here are the patches:
1. Introduce (some of) the generic opcode.
2. Make MachineFunction more independent of LLVM IR to eventually be able to
delete the LLVM IR instance from the memory.
3. Extend MachineInstr to represent additional information attached to generic
opcode.
4. Teach MachineRegisterInfo about size for virtual registers.
5. Introduce a helper class to build MachineInstr related objects.
6. Add new target hooks to lower the ABI directly to MachineInstr.
7. Introduce the IRTranslator pass.


** Roadmap for the Prototype **

We plan to split the prototype in three main milestones:
1. Translation: LLVM IR to (G) MachineInstr translation.
2. Basic selector: Legal LLVM IR to target specific MachineInstr.
3. Simple legalization: Support scalar type legalization and some vector
instructions.

Notes:
- For #1, we will not support any fancy instructions like landing pad or switch.
- Each milestone should take about 3-4 months.
- At the end of #2, we would have a FastISel like selector.

Each milestone will be detailed right before starting it. The rational is that
we want to accommodate what we discovered with the prototype for the next
milestone. In other words, in this email, I only describe the first milestone in
detail and I will give more details on the next milestone shortly before we
start it and so on. For your information, here is the remaining of the intended
roadmap for the full project:
4. Productization: Clean up implementation, stabilize the APIs.
5. Complex legalization: Extend legalization support to everything missing.
6. Completeness: Fill the blanks, e.g., landing pad.
7. Clean-up and performance: Add the necessary bits to be at parity or beat
SelectionDAG generated code.
8. Transition: Document how to switch, provide tools to help.


** Milestone 1 **

The first phase is focused on the IRTranslator pass.

The IRTranslator is responsible for translating the LLVM IR into Generic
MachineInstr. The IRTranslator pass uses some target hooks to perform the ABI
lowering. We can either define a new API for them, e.g., ABILoweringInfo, or
extend the existing TargetLowering.
Moreover, the prototype will focus on simple instruction, i.e., we will not
support switch or landing pad for this iteration.

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.

* 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?
- 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”?

Thanks,
-Quentin
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20151120/e2959715/attachment.html>

Hi Daniel,

Thanks for pointing that out.

Cheers,
-Quentin
> On Nov 20, 2015, at 6:53 AM, Daniel Sanders <Daniel.Sanders at
imgtec.com> wrote:
> 
> Hi,
>  
> I haven't had chance to read all of this yet, but one minor thing
occurred to me during your presentation that I want to mention. At one point you
mentioned deleting all the bitcast instructions since they're equivalent to
nops but this isn't always true.
>  
> The http://llvm.org/docs/LangRef.html
<http://llvm.org/docs/LangRef.html> definition of the bitcast instruction
includes this sentence:
> The conversion is done as if the value had been stored to memory and read
back as type ty2.
> For big-endian MSA, this is equivalent to a shuffling of the bits in the
register because endianness only changes the byte order within each element. The
order of the elements is unaffected by endianness. IIRC, big-endian NEON is the
same way.
>  
> From: llvm-dev [mailto:llvm-dev-bounces at lists.llvm.org] On Behalf Of
Quentin Colombet via llvm-dev
> Sent: 18 November 2015 19:27
> To: llvm-dev
> Subject: [llvm-dev] [GlobalISel] A Proposal for global instruction
selection
>  
> Hi,
> 
> With this email, I would like to kick-off the development for the next
instruction selector that I described during the last LLVM Dev’ Meeting.
> For the motivations, see Jakob’s proposal
(http://lists.cs.uiuc.edu/pipermail/llvmdev/2013-August/064727.html
<http://lists.cs.uiuc.edu/pipermail/llvmdev/2013-August/064727.html>) and
for the proposal, see the slides (Keynote:
http://llvm.org/viewvc/llvm-project/www/trunk/devmtg/2015-10/slides/Colombet-GlobalInstructionSelection.key?view=co
<http://llvm.org/viewvc/llvm-project/www/trunk/devmtg/2015-10/slides/Colombet-GlobalInstructionSelection.key?view=co>
or PDF:
http://llvm.org/viewvc/llvm-project/www/trunk/devmtg/2015-10/slides/Colombet-GlobalInstructionSelection.pdf?revision=252430&view=co
<http://llvm.org/viewvc/llvm-project/www/trunk/devmtg/2015-10/slides/Colombet-GlobalInstructionSelection.pdf?revision=252430&view=co>)
or the talk
(https://www.youtube.com/watch?v=F6GGbYtae3g&list=PL_R5A0lGi1AA4Lv2bBFSwhgDaHvvpVU21&index=2
<https://www.youtube.com/watch?v=F6GGbYtae3g&list=PL_R5A0lGi1AA4Lv2bBFSwhgDaHvvpVU21&index=2>).
> 
> TL;DR This is happening now, feedbacks invited!
> 
> *** Context ***
> 
> During the last LLVM Dev’ Meeting, I have presented a proposal for the next
instruction selector, GlobalISel. The proposal is basically summarized in
"High Level Prototype Design” and “Roadmap”. (If you want further details,
feel free to reach me.)
> 
> The first step of the development plan is to prototype the new framework on
open source. The idea is to start prototyping now(!) and have the discussion
ongoing in parallel. The reason of such approach is to have code that can be
used to inform those discussions, e.g., by collecting data and trying different
designs approaches. Regarding the discussion, I have listed a few points where
your feedbacks would be particularly appreciated (see Feedback Invite).
> 
> Also, as I have mentioned in my talk, some issues are controversial but I
expect them to be resolved during prototype development. Specifically theses
concern aspects of legalization (should parts of it be done at the LLVM IR level
or all at the MI level?) and code re-use for instruction combiner. Please feel
free to bring up your specific concern as I move along with the development
plan.
> 
> I expect the design to evolve with our experimental findings and your
feedbacks and contributions.
> Nonetheless, we expect to nail down some design decisions once and for all
as the prototype progresses. I have highlighted them with the following pattern
[final].
> 
> 
> 
> *** Feedback Invite ***
> 
> If you follow and support this work you need to be aware of three things
and I am eager to hear your feedback and thoughts about them: the overall goals
of Global ISel, the goals of the prototype, and the impact of the prototype work
on backend design.
> 
> In the section “Goals", I defined (repeated for people that saw the
talk) the goals for the Global ISel design.
> - Do you see anything missing?
> - Do you see something that should not be there? 
> 
> The prototype will answer critical design questions (see “Design Questions
the Prototype Addresses at the End of M1" for examples) before the actual
design of Gobal ISel is finalized, but it cannot cover everything.
> Specifically we will *not* look into improving TableGen or reuse
InstCombine (see “ Proposed Approach” for the rational). Please let me know if
you see any issue with that.
> 
> There is also basic ground work needed to prepare for Global ISel and I
need to extend the core MachineInstr-level APIs as explained during the talk.
For this, I prepared sketches of patches to illustrate them and describe the
details in the “Implications” section below. Please have a look at the patches
to have a better idea of the expected impact.
> 
> If there is anything else you want to discuss related to Global ISel feel
free to reach me. In particular, several people expressed their interests during
the LLVM Dev Meeting in contributing to the project. Let me know what is your
area of interest, so that we can coordinate our efforts.
> Anyhow, please add [GlobalISel] in the subject line to help categorizing
the emails.
> 
> 
> 
> *** Goals ***
> 
> The high level goals of the new instruction selector are:
> - Global instruction selector.
> - Fast instruction selector.
> - Shared code path for fast and good instruction selection.
> - IR that represents ISA concepts better.
> - More flexible instruction selector.
> - Easier to maintain/understand framework, in particular legalization.
> - Self contained machine representation, no back links to LLVM IR.
> - No change to LLVM IR.
> 
> Note:  The goals are common to all targets. In particular, we do not intend
to work on target specific feature for the prototype.
> The bottom line is please make sure those goals are compatible with what
you want to achieve for your target, even if your requirement does not get
listed here.
> 
> 
> 
> *** 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 InstCombine [final]. We will keep in mind however, that some of the
C++ code we write will be table-generated at some point.
> The rational is that we do not want to lay down a new TableGen/InstCombine
infrastructure before being able to work on the ISel framework itself.
> 
> The prototype vehicle will be AArch64. None of the changes for GlobalISel
will negatively impact the existing ISel.
> 
> 
> ** High Level Prototype Design **
> 
> As shown in the talk, the expected pipeline for the prototype is:
> LLVM IR -> IRTranslator -> Generic (G) MachineInstr -> Legalizer
-> RegBankSelect -> Select -> MachineInstr
> 
> Where:
> - Terms in bold are intermediate representations.
> -  Generic MachineInstrs are machine instructions with a generic opcode,
e.g., ADD, COPY.
> - IRTranslator: Translate LLVM IR to (G) MachineInstr.
> - Legalizer: Legalize illegal (G) MachineInstr to legal (G) MachineInstr.
> - RegBankSelect: Assign virtual register with size to virtual register with
Register Bank.
> - Select: Translate the remaining (G) MachineInstr to MachineIntr.
> 
> 
> 
> ** 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.
>   - Need to know the type of each MachineInstr. We don’t want ADD8, ADD16,
etc.
>   - Extend the MachineRegisterInfo to support size as well as register
classes for virtual registers.
> 
> I have sketched the changes in the attached patches to help picturing how
the changes would impact the existing APIs.
>  
> Note: I do not intend to commit those changes as they are. They will go the
usual review process in due time.
> 
> The patches contain “// ***”-like comment that give a rough explanation on
why those changes are needed w.r.t. the goals.
> The order of the patches could be modified since the dependencies between
those are not sequential. Anyhow, here are the patches:
> 1. Introduce (some of) the generic opcode.
> 2. Make MachineFunction more independent of LLVM IR to eventually be able
to delete the LLVM IR instance from the memory.
> 3. Extend MachineInstr to represent additional information attached to
generic opcode.
> 4. Teach MachineRegisterInfo about size for virtual registers.
> 5. Introduce a helper class to build MachineInstr related objects.
> 6. Add new target hooks to lower the ABI directly to MachineInstr.
> 7. Introduce the IRTranslator pass.
> 
> 
> ** Roadmap for the Prototype **
> 
> We plan to split the prototype in three main milestones:
> 1. Translation: LLVM IR to (G) MachineInstr translation.
> 2. Basic selector: Legal LLVM IR to target specific MachineInstr.
> 3. Simple legalization: Support scalar type legalization and some vector
instructions.
> 
> Notes:
> - For #1, we will not support any fancy instructions like landing pad or
switch.
> - Each milestone should take about 3-4 months.
> - At the end of #2, we would have a FastISel like selector.
> 
> Each milestone will be detailed right before starting it. The rational is
that we want to accommodate what we discovered with the prototype for the next
milestone. In other words, in this email, I only describe the first milestone in
detail and I will give more details on the next milestone shortly before we
start it and so on. For your information, here is the remaining of the intended
roadmap for the full project:
> 4. Productization: Clean up implementation, stabilize the APIs.
> 5. Complex legalization: Extend legalization support to everything missing.
> 6. Completeness: Fill the blanks, e.g., landing pad.
> 7. Clean-up and performance: Add the necessary bits to be at parity or beat
SelectionDAG generated code.
> 8. Transition: Document how to switch, provide tools to help.
> 
> 
> ** Milestone 1 **
> 
> The first phase is focused on the IRTranslator pass.
> 
> The IRTranslator is responsible for translating the LLVM IR into Generic
MachineInstr. The IRTranslator pass uses some target hooks to perform the ABI
lowering. We can either define a new API for them, e.g., ABILoweringInfo, or
extend the existing TargetLowering.
> Moreover, the prototype will focus on simple instruction, i.e., we will not
support switch or landing pad for this iteration.
> 
> 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.
> 
> * 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?
> - 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”?
> 
> Thanks,
> -Quentin
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20151120/e7548d20/attachment.html>

Hi Quentin,

First, thanks a lot for working on this! This is obviously a really-important
problem.

One thought:

+  /// *** This is to support:
+  /// *** Self contained machine representation, no back links to LLVM IR.
+  /// Import the attribute from the IR Function.
+  AttributeSet AttributeSets;             ///< Parameter attributes

I fully support better modeling of functions without ties to IR-level functions.
This will allow very-late outlining, multiversioning, etc., and there are good
use cases for these things. That having been said, I think we should have a
narrower scope for severing MI <-> IR ties, because at least one important
link will continue to exist: MMOs used to provide access to IR-level alias
analysis. This is critical to good instruction scheduling, memory-access
merging, etc. and replicating AA at the MI level is not feasible.

 -Hal

----- Original Message ----- 
> From: "Quentin Colombet via llvm-dev" <llvm-dev at
lists.llvm.org>
> To: "llvm-dev" <llvm-dev at lists.llvm.org>
> Sent: Wednesday, November 18, 2015 1:26:37 PM
> Subject: [llvm-dev] [GlobalISel] A Proposal for global instruction
> selection
> Hi,
> With this email, I would like to kick-off the development for the
> next instruction selector that I described during the last LLVM Dev’
> Meeting.
> For the motivations, see Jakob’s proposal (
> http://lists.cs.uiuc.edu/pipermail/llvmdev/2013-August/064727.html )
> and for the proposal, see the slides (Keynote:
>
http://llvm.org/viewvc/llvm-project/www/trunk/devmtg/2015-10/slides/Colombet-GlobalInstructionSelection.key?view=co
> or PDF:
>
http://llvm.org/viewvc/llvm-project/www/trunk/devmtg/2015-10/slides/Colombet-GlobalInstructionSelection.pdf?revision=252430&view=co
> ) or the talk (
>
https://www.youtube.com/watch?v=F6GGbYtae3g&list=PL_R5A0lGi1AA4Lv2bBFSwhgDaHvvpVU21&index=2
> ).
> TL;DR This is happening now, feedbacks invited!
> *** Context ***
> During the last LLVM Dev’ Meeting, I have presented a proposal for
> the next instruction selector, GlobalISel. The proposal is basically
> summarized in "High Level Prototype Design” and “Roadmap”. (If you
> want further details, feel free to reach me.)
> The first step of the development plan is to prototype the new
> framework on open source. The idea is to start prototyping now(!)
> and have the discussion ongoing in parallel. The reason of such
> approach is to have code that can be used to inform those
> discussions, e.g., by collecting data and trying different designs
> approaches. Regarding the discussion, I have listed a few points
> where your feedbacks would be particularly appreciated (see Feedback
> Invite).
> Also, as I have mentioned in my talk, some issues are controversial
> but I expect them to be resolved during prototype development.
> Specifically theses concern aspects of legalization (should parts of
> it be done at the LLVM IR level or all at the MI level?) and code
> re-use for instruction combiner. Please feel free to bring up your
> specific concern as I move along with the development plan.
> I expect the design to evolve with our experimental findings and your
> feedbacks and contributions.
> Nonetheless, we expect to nail down some design decisions once and
> for all as the prototype progresses. I have highlighted them with
> the following pattern [final] .
> *** Feedback Invite ***
> If you follow and support this work you need to be aware of three
> things and I am eager to hear your feedback and thoughts about them:
> the overall goals of Global ISel, the goals of the prototype, and
> the impact of the prototype work on backend design.
> In the section “Goals", I defined (repeated for people that saw the
> talk) the goals for the Global ISel design.
> - Do you see anything missing?
> - Do you see something that should not be there?
> The prototype will answer critical design questions (see “Design
> Questions the Prototype Addresses at the End of M1" for examples)
> before the actual design of Gobal ISel is finalized, but it cannot
> cover everything.
> Specifically we will *not* look into improving TableGen or reuse
> InstCombine (see “ Proposed Approach” for the rational). Please let
> me know if you see any issue with that.
> There is also basic ground work needed to prepare for Global ISel and
> I need to extend the core MachineInstr-level APIs as explained
> during the talk. For this, I prepared sketches of patches to
> illustrate them and describe the details in the “Implications”
> section below. Please have a look at the patches to have a better
> idea of the expected impact.
> If there is anything else you want to discuss related to Global ISel
> feel free to reach me. In particular, several people expressed their
> interests during the LLVM Dev Meeting in contributing to the
> project. Let me know what is your area of interest, so that we can
> coordinate our efforts.
> Anyhow, please add [GlobalISel] in the subject line to help
> categorizing the emails.
> *** Goals ***
> The high level goals of the new instruction selector are:
> - Global instruction selector.
> - Fast instruction selector.
> - Shared code path for fast and good instruction selection.
> - IR that represents ISA concepts better.
> - More flexible instruction selector.
> - Easier to maintain/understand framework, in particular
> legalization.
> - Self contained machine representation, no back links to LLVM IR.
> - No change to LLVM IR.
> Note: The goals are common to all targets. In particular, we do not
> intend to work on target specific feature for the prototype.
> The bottom line is please make sure those goals are compatible with
> what you want to achieve for your target, even if your requirement
> does not get listed here.
> *** 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 InstCombine [final]. We will keep in mind however, that
> some of the C++ code we write will be table-generated at some point.
> The rational is that we do not want to lay down a new
> TableGen/InstCombine infrastructure before being able to work on the
> ISel framework itself.
> The prototype vehicle will be AArch64 . None of the changes for
> GlobalISel will negatively impact the existing ISel.
> ** High Level Prototype Design **
> As shown in the talk, the expected pipeline for the prototype is:
> LLVM IR -> IRTranslator -> Generic (G) MachineInstr -> Legalizer
->
> RegBankSelect -> Select -> MachineInstr
> Where:
> - Terms in bold are intermediate representations.
> - Generic MachineInstrs are machine instructions with a generic
> opcode, e.g., ADD, COPY.
> - IRTranslator: Translate LLVM IR to (G) MachineInstr.
> - Legalizer: Legalize illegal (G) MachineInstr to legal (G)
> MachineInstr.
> - RegBankSelect: Assign virtual register with size to virtual
> register with Register Bank.
> - Select: Translate the remaining (G) MachineInstr to MachineIntr.
> ** 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.
> - Need to know the type of each MachineInstr. We don’t want ADD8,
> ADD16, etc.
> - Extend the MachineRegisterInfo to support size as well as register
> classes for virtual registers.
> I have sketched the changes in the attached patches to help picturing
> how the changes would impact the existing APIs.
> Note: I do not intend to commit those changes as they are. They will
> go the usual review process in due time.
> The patches contain “// ***”-like comment that give a rough
> explanation on why those changes are needed w.r.t. the goals.
> The order of the patches could be modified since the dependencies
> between those are not sequential. Anyhow, here are the patches:
> 1. Introduce (some of) the generic opcode.
> 2. Make MachineFunction more independent of LLVM IR to eventually be
> able to delete the LLVM IR instance from the memory.
> 3. Extend MachineInstr to represent additional information attached
> to generic opcode.
> 4. Teach MachineRegisterInfo about size for virtual registers.
> 5. Introduce a helper class to build MachineInstr related objects.
> 6. Add new target hooks to lower the ABI directly to MachineInstr.
> 7. Introduce the IRTranslator pass.
> ** Roadmap for the Prototype **
> We plan to split the prototype in three main milestones:
> 1. Translation: LLVM IR to (G) MachineInstr translation.
> 2. Basic selector: Legal LLVM IR to target specific MachineInstr.
> 3. Simple legalization: Support scalar type legalization and some
> vector instructions.
> Notes:
> - For #1, we will not support any fancy instructions like landing pad
> or switch.
> - Each milestone should take about 3-4 months.
> - At the end of #2, we would have a FastISel like selector.
> Each milestone will be detailed right before starting it. The
> rational is that we want to accommodate what we discovered with the
> prototype for the next milestone. In other words, in this email, I
> only describe the first milestone in detail and I will give more
> details on the next milestone shortly before we start it and so on.
> For your information, here is the remaining of the intended roadmap
> for the full project:
> 4. Productization: Clean up implementation, stabilize the APIs.
> 5. Complex legalization: Extend legalization support to everything
> missing.
> 6. Completeness: Fill the blanks, e.g., landing pad.
> 7. Clean-up and performance: Add the necessary bits to be at parity
> or beat SelectionDAG generated code.
> 8. Transition: Document how to switch, provide tools to help.
> ** Milestone 1 **
> The first phase is focused on the IRTranslator pass.
> The IRTranslator is responsible for translating the LLVM IR into
> Generic MachineInstr. The IRTranslator pass uses some target hooks
> to perform the ABI lowering. We can either define a new API for
> them, e.g., ABILoweringInfo, or extend the existing TargetLowering.
> Moreover, the prototype will focus on simple instruction, i.e., we
> will not support switch or landing pad for this iteration.
> 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.
> * 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?
> - 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”?
> Thanks,
> -Quentin
> --
Hal Finkel 
Assistant Computational Scientist 
Leadership Computing Facility 
Argonne National Laboratory

Hi Hal,

The alias information is a good example of the MI to IR back links, thanks for
pointing that out.
> On Nov 26, 2015, at 12:58 PM, Hal Finkel <hfinkel at anl.gov> wrote:
> 
> Hi Quentin,
> 
> First, thanks a lot for working on this! This is obviously a
really-important problem.
> 
> One thought:
> 
> +  /// *** This is to support:
> +  /// *** Self contained machine representation, no back links to LLVM IR.
> +  /// Import the attribute from the IR Function.
> +  AttributeSet AttributeSets;             ///< Parameter attributes
> 
> I fully support better modeling of functions without ties to IR-level
functions. This will allow very-late outlining, multiversioning, etc., and there
are good use cases for these things. That having been said, I think we should
have a narrower scope for severing MI <-> IR ties, because at least one
important link will continue to exist: MMOs used to provide access to IR-level
alias analysis. This is critical to good instruction scheduling, memory-access
merging, etc. and replicating AA at the MI level is not feasible.
Honestly, although I understand why we have the MMOs right now, I don’t think
this is a clean design and I would rather have an AA working at MI level or,
better, a different way of passing the information to MI.
I don’t have something in mind on how to pass the information if we choose that
path, but I think it would be important to get rid of the MI -> IR link for
aliases purposes, because we end up with, IMHO, ugly code where a Machine pass
patches the IR to fix the alias information. E.g., in the stack coloring pass:
    // AA might be used later for instruction scheduling, and we need it to be
    // able to deduce the correct aliasing releationships between pointers
    // derived from the alloca being remapped and the target of that remapping.
    // The only safe way, without directly informing AA about the remapping
    // somehow, is to directly update the IR to reflect the change being made
    // here.
    Instruction *Inst = const_cast<AllocaInst *>(To);
    if (From->getType() != To->getType()) {
      BitCastInst *Cast = new BitCastInst(Inst, From->getType());
      Cast->insertAfter(Inst);
      Inst = Cast;
    }

Therefore, I would prefer having the alias information expressed as something
decoupled from the IR and that could be updated.

What do you think?

Cheers,
-Quentin
> 
> -Hal
> 
> ----- Original Message ----- 
> 
>> From: "Quentin Colombet via llvm-dev" <llvm-dev at
lists.llvm.org <mailto:llvm-dev at lists.llvm.org>>
>> To: "llvm-dev" <llvm-dev at lists.llvm.org
<mailto:llvm-dev at lists.llvm.org>>
>> Sent: Wednesday, November 18, 2015 1:26:37 PM
>> Subject: [llvm-dev] [GlobalISel] A Proposal for global instruction
>> selection
> 
>> Hi,
> 
>> With this email, I would like to kick-off the development for the
>> next instruction selector that I described during the last LLVM Dev’
>> Meeting.
>> For the motivations, see Jakob’s proposal (
>> http://lists.cs.uiuc.edu/pipermail/llvmdev/2013-August/064727.html )
>> and for the proposal, see the slides (Keynote:
>>
http://llvm.org/viewvc/llvm-project/www/trunk/devmtg/2015-10/slides/Colombet-GlobalInstructionSelection.key?view=co
>> or PDF:
>>
http://llvm.org/viewvc/llvm-project/www/trunk/devmtg/2015-10/slides/Colombet-GlobalInstructionSelection.pdf?revision=252430&view=co
>> ) or the talk (
>>
https://www.youtube.com/watch?v=F6GGbYtae3g&list=PL_R5A0lGi1AA4Lv2bBFSwhgDaHvvpVU21&index=2
>> ).
> 
>> TL;DR This is happening now, feedbacks invited!
> 
>> *** Context ***
> 
>> During the last LLVM Dev’ Meeting, I have presented a proposal for
>> the next instruction selector, GlobalISel. The proposal is basically
>> summarized in "High Level Prototype Design” and “Roadmap”. (If you
>> want further details, feel free to reach me.)
> 
>> The first step of the development plan is to prototype the new
>> framework on open source. The idea is to start prototyping now(!)
>> and have the discussion ongoing in parallel. The reason of such
>> approach is to have code that can be used to inform those
>> discussions, e.g., by collecting data and trying different designs
>> approaches. Regarding the discussion, I have listed a few points
>> where your feedbacks would be particularly appreciated (see Feedback
>> Invite).
> 
>> Also, as I have mentioned in my talk, some issues are controversial
>> but I expect them to be resolved during prototype development.
>> Specifically theses concern aspects of legalization (should parts of
>> it be done at the LLVM IR level or all at the MI level?) and code
>> re-use for instruction combiner. Please feel free to bring up your
>> specific concern as I move along with the development plan.
> 
>> I expect the design to evolve with our experimental findings and your
>> feedbacks and contributions.
>> Nonetheless, we expect to nail down some design decisions once and
>> for all as the prototype progresses. I have highlighted them with
>> the following pattern [final] .
> 
>> *** Feedback Invite ***
> 
>> If you follow and support this work you need to be aware of three
>> things and I am eager to hear your feedback and thoughts about them:
>> the overall goals of Global ISel, the goals of the prototype, and
>> the impact of the prototype work on backend design.
> 
>> In the section “Goals", I defined (repeated for people that saw
the
>> talk) the goals for the Global ISel design.
>> - Do you see anything missing?
>> - Do you see something that should not be there?
> 
>> The prototype will answer critical design questions (see “Design
>> Questions the Prototype Addresses at the End of M1" for examples)
>> before the actual design of Gobal ISel is finalized, but it cannot
>> cover everything.
>> Specifically we will *not* look into improving TableGen or reuse
>> InstCombine (see “ Proposed Approach” for the rational). Please let
>> me know if you see any issue with that.
> 
>> There is also basic ground work needed to prepare for Global ISel and
>> I need to extend the core MachineInstr-level APIs as explained
>> during the talk. For this, I prepared sketches of patches to
>> illustrate them and describe the details in the “Implications”
>> section below. Please have a look at the patches to have a better
>> idea of the expected impact.
> 
>> If there is anything else you want to discuss related to Global ISel
>> feel free to reach me. In particular, several people expressed their
>> interests during the LLVM Dev Meeting in contributing to the
>> project. Let me know what is your area of interest, so that we can
>> coordinate our efforts.
>> Anyhow, please add [GlobalISel] in the subject line to help
>> categorizing the emails.
> 
>> *** Goals ***
> 
>> The high level goals of the new instruction selector are:
>> - Global instruction selector.
>> - Fast instruction selector.
>> - Shared code path for fast and good instruction selection.
>> - IR that represents ISA concepts better.
>> - More flexible instruction selector.
>> - Easier to maintain/understand framework, in particular
>> legalization.
>> - Self contained machine representation, no back links to LLVM IR.
>> - No change to LLVM IR.
> 
>> Note: The goals are common to all targets. In particular, we do not
>> intend to work on target specific feature for the prototype.
>> The bottom line is please make sure those goals are compatible with
>> what you want to achieve for your target, even if your requirement
>> does not get listed here.
> 
>> *** 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 InstCombine [final]. We will keep in mind however, that
>> some of the C++ code we write will be table-generated at some point.
>> The rational is that we do not want to lay down a new
>> TableGen/InstCombine infrastructure before being able to work on the
>> ISel framework itself.
> 
>> The prototype vehicle will be AArch64 . None of the changes for
>> GlobalISel will negatively impact the existing ISel.
> 
>> ** High Level Prototype Design **
> 
>> As shown in the talk, the expected pipeline for the prototype is:
>> LLVM IR -> IRTranslator -> Generic (G) MachineInstr ->
Legalizer ->
>> RegBankSelect -> Select -> MachineInstr
> 
>> Where:
>> - Terms in bold are intermediate representations.
>> - Generic MachineInstrs are machine instructions with a generic
>> opcode, e.g., ADD, COPY.
>> - IRTranslator: Translate LLVM IR to (G) MachineInstr.
>> - Legalizer: Legalize illegal (G) MachineInstr to legal (G)
>> MachineInstr.
>> - RegBankSelect: Assign virtual register with size to virtual
>> register with Register Bank.
>> - Select: Translate the remaining (G) MachineInstr to MachineIntr.
> 
>> ** 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.
>> - Need to know the type of each MachineInstr. We don’t want ADD8,
>> ADD16, etc.
>> - Extend the MachineRegisterInfo to support size as well as register
>> classes for virtual registers.
> 
>> I have sketched the changes in the attached patches to help picturing
>> how the changes would impact the existing APIs.
> 
>> Note: I do not intend to commit those changes as they are. They will
>> go the usual review process in due time.
> 
>> The patches contain “// ***”-like comment that give a rough
>> explanation on why those changes are needed w.r.t. the goals.
>> The order of the patches could be modified since the dependencies
>> between those are not sequential. Anyhow, here are the patches:
>> 1. Introduce (some of) the generic opcode.
>> 2. Make MachineFunction more independent of LLVM IR to eventually be
>> able to delete the LLVM IR instance from the memory.
>> 3. Extend MachineInstr to represent additional information attached
>> to generic opcode.
>> 4. Teach MachineRegisterInfo about size for virtual registers.
>> 5. Introduce a helper class to build MachineInstr related objects.
>> 6. Add new target hooks to lower the ABI directly to MachineInstr.
>> 7. Introduce the IRTranslator pass.
> 
>> ** Roadmap for the Prototype **
> 
>> We plan to split the prototype in three main milestones:
>> 1. Translation: LLVM IR to (G) MachineInstr translation.
>> 2. Basic selector: Legal LLVM IR to target specific MachineInstr.
>> 3. Simple legalization: Support scalar type legalization and some
>> vector instructions.
> 
>> Notes:
>> - For #1, we will not support any fancy instructions like landing pad
>> or switch.
>> - Each milestone should take about 3-4 months.
>> - At the end of #2, we would have a FastISel like selector.
> 
>> Each milestone will be detailed right before starting it. The
>> rational is that we want to accommodate what we discovered with the
>> prototype for the next milestone. In other words, in this email, I
>> only describe the first milestone in detail and I will give more
>> details on the next milestone shortly before we start it and so on.
>> For your information, here is the remaining of the intended roadmap
>> for the full project:
>> 4. Productization: Clean up implementation, stabilize the APIs.
>> 5. Complex legalization: Extend legalization support to everything
>> missing.
>> 6. Completeness: Fill the blanks, e.g., landing pad.
>> 7. Clean-up and performance: Add the necessary bits to be at parity
>> or beat SelectionDAG generated code.
>> 8. Transition: Document how to switch, provide tools to help.
> 
>> ** Milestone 1 **
> 
>> The first phase is focused on the IRTranslator pass.
> 
>> The IRTranslator is responsible for translating the LLVM IR into
>> Generic MachineInstr. The IRTranslator pass uses some target hooks
>> to perform the ABI lowering. We can either define a new API for
>> them, e.g., ABILoweringInfo, or extend the existing TargetLowering.
>> Moreover, the prototype will focus on simple instruction, i.e., we
>> will not support switch or landing pad for this iteration.
> 
>> 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.
> 
>> * 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?
>> - 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”?
> 
>> Thanks,
> 
>> -Quentin
> 
>> --
> Hal Finkel 
> Assistant Computational Scientist 
> Leadership Computing Facility 
> Argonne National Laboratory 
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20151130/61abb267/attachment-0001.html>

Hi Daniel,

I had a quick look at the language reference for bitcast and I have a different
reading than what you were pointing out.
Indeed, my take away is:
"It is always a no-op cast because no bits change with this
conversion."

In other words, deleting all bitcast instructions should be fine.

My understanding of the quote you’ve highlighted is that it tells C programmers
that this is like a memcpy, not a cast :).

Cheers,
-Quentin
> On Nov 20, 2015, at 6:53 AM, Daniel Sanders <Daniel.Sanders at
imgtec.com> wrote:
> 
> Hi,
>  
> I haven't had chance to read all of this yet, but one minor thing
occurred to me during your presentation that I want to mention. At one point you
mentioned deleting all the bitcast instructions since they're equivalent to
nops but this isn't always true.
>  
> The http://llvm.org/docs/LangRef.html
<http://llvm.org/docs/LangRef.html> definition of the bitcast instruction
includes this sentence:
> The conversion is done as if the value had been stored to memory and read
back as type ty2.
> For big-endian MSA, this is equivalent to a shuffling of the bits in the
register because endianness only changes the byte order within each element. The
order of the elements is unaffected by endianness. IIRC, big-endian NEON is the
same way.
>  
> From: llvm-dev [mailto:llvm-dev-bounces at lists.llvm.org] On Behalf Of
Quentin Colombet via llvm-dev
> Sent: 18 November 2015 19:27
> To: llvm-dev
> Subject: [llvm-dev] [GlobalISel] A Proposal for global instruction
selection
>  
> Hi,
> 
> With this email, I would like to kick-off the development for the next
instruction selector that I described during the last LLVM Dev’ Meeting.
> For the motivations, see Jakob’s proposal
(http://lists.cs.uiuc.edu/pipermail/llvmdev/2013-August/064727.html
<http://lists.cs.uiuc.edu/pipermail/llvmdev/2013-August/064727.html>) and
for the proposal, see the slides (Keynote:
http://llvm.org/viewvc/llvm-project/www/trunk/devmtg/2015-10/slides/Colombet-GlobalInstructionSelection.key?view=co
<http://llvm.org/viewvc/llvm-project/www/trunk/devmtg/2015-10/slides/Colombet-GlobalInstructionSelection.key?view=co>
or PDF:
http://llvm.org/viewvc/llvm-project/www/trunk/devmtg/2015-10/slides/Colombet-GlobalInstructionSelection.pdf?revision=252430&view=co
<http://llvm.org/viewvc/llvm-project/www/trunk/devmtg/2015-10/slides/Colombet-GlobalInstructionSelection.pdf?revision=252430&view=co>)
or the talk
(https://www.youtube.com/watch?v=F6GGbYtae3g&list=PL_R5A0lGi1AA4Lv2bBFSwhgDaHvvpVU21&index=2
<https://www.youtube.com/watch?v=F6GGbYtae3g&list=PL_R5A0lGi1AA4Lv2bBFSwhgDaHvvpVU21&index=2>).
> 
> TL;DR This is happening now, feedbacks invited!
> 
> *** Context ***
> 
> During the last LLVM Dev’ Meeting, I have presented a proposal for the next
instruction selector, GlobalISel. The proposal is basically summarized in
"High Level Prototype Design” and “Roadmap”. (If you want further details,
feel free to reach me.)
> 
> The first step of the development plan is to prototype the new framework on
open source. The idea is to start prototyping now(!) and have the discussion
ongoing in parallel. The reason of such approach is to have code that can be
used to inform those discussions, e.g., by collecting data and trying different
designs approaches. Regarding the discussion, I have listed a few points where
your feedbacks would be particularly appreciated (see Feedback Invite).
> 
> Also, as I have mentioned in my talk, some issues are controversial but I
expect them to be resolved during prototype development. Specifically theses
concern aspects of legalization (should parts of it be done at the LLVM IR level
or all at the MI level?) and code re-use for instruction combiner. Please feel
free to bring up your specific concern as I move along with the development
plan.
> 
> I expect the design to evolve with our experimental findings and your
feedbacks and contributions.
> Nonetheless, we expect to nail down some design decisions once and for all
as the prototype progresses. I have highlighted them with the following pattern
[final].
> 
> 
> 
> *** Feedback Invite ***
> 
> If you follow and support this work you need to be aware of three things
and I am eager to hear your feedback and thoughts about them: the overall goals
of Global ISel, the goals of the prototype, and the impact of the prototype work
on backend design.
> 
> In the section “Goals", I defined (repeated for people that saw the
talk) the goals for the Global ISel design.
> - Do you see anything missing?
> - Do you see something that should not be there? 
> 
> The prototype will answer critical design questions (see “Design Questions
the Prototype Addresses at the End of M1" for examples) before the actual
design of Gobal ISel is finalized, but it cannot cover everything.
> Specifically we will *not* look into improving TableGen or reuse
InstCombine (see “ Proposed Approach” for the rational). Please let me know if
you see any issue with that.
> 
> There is also basic ground work needed to prepare for Global ISel and I
need to extend the core MachineInstr-level APIs as explained during the talk.
For this, I prepared sketches of patches to illustrate them and describe the
details in the “Implications” section below. Please have a look at the patches
to have a better idea of the expected impact.
> 
> If there is anything else you want to discuss related to Global ISel feel
free to reach me. In particular, several people expressed their interests during
the LLVM Dev Meeting in contributing to the project. Let me know what is your
area of interest, so that we can coordinate our efforts.
> Anyhow, please add [GlobalISel] in the subject line to help categorizing
the emails.
> 
> 
> 
> *** Goals ***
> 
> The high level goals of the new instruction selector are:
> - Global instruction selector.
> - Fast instruction selector.
> - Shared code path for fast and good instruction selection.
> - IR that represents ISA concepts better.
> - More flexible instruction selector.
> - Easier to maintain/understand framework, in particular legalization.
> - Self contained machine representation, no back links to LLVM IR.
> - No change to LLVM IR.
> 
> Note:  The goals are common to all targets. In particular, we do not intend
to work on target specific feature for the prototype.
> The bottom line is please make sure those goals are compatible with what
you want to achieve for your target, even if your requirement does not get
listed here.
> 
> 
> 
> *** 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 InstCombine [final]. We will keep in mind however, that some of the
C++ code we write will be table-generated at some point.
> The rational is that we do not want to lay down a new TableGen/InstCombine
infrastructure before being able to work on the ISel framework itself.
> 
> The prototype vehicle will be AArch64. None of the changes for GlobalISel
will negatively impact the existing ISel.
> 
> 
> ** High Level Prototype Design **
> 
> As shown in the talk, the expected pipeline for the prototype is:
> LLVM IR -> IRTranslator -> Generic (G) MachineInstr -> Legalizer
-> RegBankSelect -> Select -> MachineInstr
> 
> Where:
> - Terms in bold are intermediate representations.
> -  Generic MachineInstrs are machine instructions with a generic opcode,
e.g., ADD, COPY.
> - IRTranslator: Translate LLVM IR to (G) MachineInstr.
> - Legalizer: Legalize illegal (G) MachineInstr to legal (G) MachineInstr.
> - RegBankSelect: Assign virtual register with size to virtual register with
Register Bank.
> - Select: Translate the remaining (G) MachineInstr to MachineIntr.
> 
> 
> 
> ** 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.
>   - Need to know the type of each MachineInstr. We don’t want ADD8, ADD16,
etc.
>   - Extend the MachineRegisterInfo to support size as well as register
classes for virtual registers.
> 
> I have sketched the changes in the attached patches to help picturing how
the changes would impact the existing APIs.
>  
> Note: I do not intend to commit those changes as they are. They will go the
usual review process in due time.
> 
> The patches contain “// ***”-like comment that give a rough explanation on
why those changes are needed w.r.t. the goals.
> The order of the patches could be modified since the dependencies between
those are not sequential. Anyhow, here are the patches:
> 1. Introduce (some of) the generic opcode.
> 2. Make MachineFunction more independent of LLVM IR to eventually be able
to delete the LLVM IR instance from the memory.
> 3. Extend MachineInstr to represent additional information attached to
generic opcode.
> 4. Teach MachineRegisterInfo about size for virtual registers.
> 5. Introduce a helper class to build MachineInstr related objects.
> 6. Add new target hooks to lower the ABI directly to MachineInstr.
> 7. Introduce the IRTranslator pass.
> 
> 
> ** Roadmap for the Prototype **
> 
> We plan to split the prototype in three main milestones:
> 1. Translation: LLVM IR to (G) MachineInstr translation.
> 2. Basic selector: Legal LLVM IR to target specific MachineInstr.
> 3. Simple legalization: Support scalar type legalization and some vector
instructions.
> 
> Notes:
> - For #1, we will not support any fancy instructions like landing pad or
switch.
> - Each milestone should take about 3-4 months.
> - At the end of #2, we would have a FastISel like selector.
> 
> Each milestone will be detailed right before starting it. The rational is
that we want to accommodate what we discovered with the prototype for the next
milestone. In other words, in this email, I only describe the first milestone in
detail and I will give more details on the next milestone shortly before we
start it and so on. For your information, here is the remaining of the intended
roadmap for the full project:
> 4. Productization: Clean up implementation, stabilize the APIs.
> 5. Complex legalization: Extend legalization support to everything missing.
> 6. Completeness: Fill the blanks, e.g., landing pad.
> 7. Clean-up and performance: Add the necessary bits to be at parity or beat
SelectionDAG generated code.
> 8. Transition: Document how to switch, provide tools to help.
> 
> 
> ** Milestone 1 **
> 
> The first phase is focused on the IRTranslator pass.
> 
> The IRTranslator is responsible for translating the LLVM IR into Generic
MachineInstr. The IRTranslator pass uses some target hooks to perform the ABI
lowering. We can either define a new API for them, e.g., ABILoweringInfo, or
extend the existing TargetLowering.
> Moreover, the prototype will focus on simple instruction, i.e., we will not
support switch or landing pad for this iteration.
> 
> 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.
> 
> * 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?
> - 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”?
> 
> Thanks,
> -Quentin
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160107/9b0389fb/attachment.html>