<html><head><meta http-equiv="Content-Type" content="text/html charset=utf-8"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class=""><div class="">Hi,<br class=""><font color="#12c00e" class=""><br class=""></font>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.<br class="">For the motivations, see Jakob’s proposal (<a href="http://lists.cs.uiuc.edu/pipermail/llvmdev/2013-August/064727.html" class="">http://lists.cs.uiuc.edu/pipermail/llvmdev/2013-August/064727.html</a>) and for the proposal, see the slides (Keynote: <a href="http://llvm.org/viewvc/llvm-project/www/trunk/devmtg/2015-10/slides/Colombet-GlobalInstructionSelection.key?view=co" class="">http://llvm.org/viewvc/llvm-project/www/trunk/devmtg/2015-10/slides/Colombet-GlobalInstructionSelection.key?view=co</a> or PDF: <a href="http://llvm.org/viewvc/llvm-project/www/trunk/devmtg/2015-10/slides/Colombet-GlobalInstructionSelection.pdf?revision=252430&view=co" class="">http://llvm.org/viewvc/llvm-project/www/trunk/devmtg/2015-10/slides/Colombet-GlobalInstructionSelection.pdf?revision=252430&view=co</a>) or the talk (<a href="https://www.youtube.com/watch?v=F6GGbYtae3g&list=PL_R5A0lGi1AA4Lv2bBFSwhgDaHvvpVU21&index=2" class="">https://www.youtube.com/watch?v=F6GGbYtae3g&list=PL_R5A0lGi1AA4Lv2bBFSwhgDaHvvpVU21&index=2</a>).</div><div class=""><font class=""><br class="">TL;DR This is happening now, feedbacks invited!<br class=""><br class=""></font>*** Context ***<br class=""><font color="#12c00e" class=""><br class=""></font>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.)<br class=""><font color="#00afcd" class=""><br class=""></font>The first step of the development plan is to prototype the new framework on open source. The idea is to <b class="">start prototyping now(!)</b> 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).</div><div class=""><font color="#00afcd" class=""><br class=""></font>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.<br class=""><font color="#00afcd" class=""><br class=""></font>I expect the design to evolve with our experimental findings and your feedbacks and contributions.<br class="">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 <b class="">[final]</b>.<br class=""><font color="#12c00e" class=""><br class=""><br class=""><br class=""></font>*** Feedback Invite ***<br class=""><font color="#00afcd" class=""><br class=""></font>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. <br class=""><font color="#00afcd" class=""><br class=""></font>In the section “Goals", I defined (repeated for people that saw the talk) the goals for the Global ISel design.<br class="">- Do you see anything missing?<br class="">- Do you see something that should not be there? <br class=""><font color="#00afcd" class=""><br class=""></font>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.<br class="">Specifically we will <b class="">*not*</b> look into improving TableGen or reuse InstCombine (see “ Proposed Approach” for the rational). Please let me know if you see any issue with that.<br class=""><font color="#00afcd" class=""><br class=""></font>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.<br class=""><font color="#00afcd" class=""><br class=""></font>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.<br class="">Anyhow, please add [GlobalISel] in the subject line to help categorizing the emails.<br class=""><font color="#00afcd" class=""><br class=""><br class=""><br class=""></font>*** Goals ***<br class=""><font color="#12c00e" class=""><br class=""></font>The high level goals of the new instruction selector are:<br class="">- Global instruction selector.<br class="">- Fast instruction selector.<br class="">- Shared code path for fast and good instruction selection.<br class="">- IR that represents ISA concepts better.<br class="">- More flexible instruction selector.<br class="">- Easier to maintain/understand framework, in particular legalization.<br class="">- Self contained machine representation, no back links to LLVM IR.<br class="">- No change to LLVM IR.<br class=""><font color="#5856d6" class=""><br class=""></font>Note: The goals are common to all targets. In particular, we do not intend to work on target specific feature for the prototype.<br class="">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.<br class=""><br class=""><font color="#12c00e" class=""><br class=""><br class=""></font>*** Proposed Approach ***<br class=""><font color="#12c00e" class=""><br class=""></font>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.<br class=""><font color="#12c00e" class=""><br class=""></font>For this prototype, we purposely exclude any work to improve or use TableGen or InstCombine <b class="">[final].</b> We will keep in mind however, that some of the C++ code we write will be table-generated at some point.<br class="">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.<br class=""><font color="#12c00e" class=""><br class=""></font>The prototype vehicle will be <b class="">AArch64</b>. None of the changes for GlobalISel will negatively impact the existing ISel.<br class=""><font color="#12c00e" class=""><br class=""><br class=""></font>** High Level Prototype Design **<br class=""><font color="#12c00e" class=""><br class=""></font>As shown in the talk, the expected pipeline for the prototype is:<br class=""><b class="">LLVM IR </b>-> IRTranslator -> <b class="">Generic (G) MachineInstr</b> -> Legalizer -> RegBankSelect -> Select -> <b class="">MachineInstr</b><br class=""><font color="#12c00e" class=""><br class=""></font>Where:<br class="">- Terms in <b class="">bold</b> are intermediate representations.<br class="">- Generic MachineInstrs are machine instructions with a generic opcode, e.g., ADD, COPY.</div><div class="">- IRTranslator: Translate LLVM IR to (G) MachineInstr.<br class="">- Legalizer: Legalize illegal (G) MachineInstr to legal (G) MachineInstr.<br class="">- RegBankSelect: Assign virtual register with size to virtual register with Register Bank.<br class="">- Select: Translate the remaining (G) MachineInstr to MachineIntr.<br class=""><br class=""><font color="#00afcd" class=""><br class=""><br class=""></font>** Implications **<br class=""><font color="#00afcd" class=""><br class=""></font>As part of the bring-up of the prototype, we need to extend some of the core MachineInstr-level APIs:<br class=""> - Need to remember FastMath flags for each MachineInstr.<br class=""> - Need to know the type of each MachineInstr. We don’t want ADD8, ADD16, etc.<br class=""> - Extend the MachineRegisterInfo to support size as well as register classes for virtual registers.<br class=""><font color="#00afcd" class=""><br class=""></font>I have sketched the changes in the attached patches to help picturing how the changes would impact the existing APIs.</div><div class=""><br class=""></div><div class="">Note: I do not intend to commit those changes as they are. They will go the usual review process in due time.</div><div class=""><br class="">The patches contain “// ***”-like comment that give a rough explanation on why those changes are needed w.r.t. the goals.<br class="">The order of the patches could be modified since the dependencies between those are not sequential. Anyhow, here are the patches:<br class="">1. Introduce (some of) the generic opcode.<br class="">2. Make MachineFunction more independent of LLVM IR to eventually be able to delete the LLVM IR instance from the memory.<br class="">3. Extend MachineInstr to represent additional information attached to generic opcode.<br class="">4. Teach MachineRegisterInfo about size for virtual registers.<br class="">5. Introduce a helper class to build MachineInstr related objects.<br class="">6. Add new target hooks to lower the ABI directly to MachineInstr.<br class="">7. Introduce the IRTranslator pass.<br class=""><br class=""><font color="#12c00e" class=""><br class=""></font>** Roadmap for the Prototype **<br class=""><font color="#00afcd" class=""><br class=""></font>We plan to split the prototype in three main milestones:<br class="">1. Translation: LLVM IR to (G) MachineInstr translation.<br class="">2. Basic selector: Legal LLVM IR to target specific MachineInstr.<br class="">3. Simple legalization: Support scalar type legalization and some vector instructions.<br class=""><font color="#00afcd" class=""><br class=""></font>Notes:<br class="">- For #1, we will not support any fancy instructions like landing pad or switch.<br class="">- Each milestone should take about 3-4 months.</div><div class="">- At the end of #2, we would have a FastISel like selector.<br class=""><font color="#00afcd" class=""><br class=""></font>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, <b class="">I only describe the first milestone</b> 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 <b class="">full</b> project:<br class="">4. Productization: Clean up implementation, stabilize the APIs.<br class="">5. Complex legalization: Extend legalization support to everything missing.<br class="">6. Completeness: Fill the blanks, e.g., landing pad.<br class="">7. Clean-up and performance: Add the necessary bits to be at parity or beat SelectionDAG generated code.<br class="">8. Transition: Document how to switch, provide tools to help.<br class=""><font color="#00afcd" class=""><br class=""><br class=""></font>** Milestone 1 **<br class=""><font color="#12c00e" class=""><br class=""></font>The first phase is focused on the IRTranslator pass.<br class=""><font color="#12c00e" class=""><br class=""></font>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.<br class="">Moreover, the prototype will focus on simple instruction, i.e., we will not support switch or landing pad for this iteration.<br class=""><font color="#12c00e" class=""><br class=""></font>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.<br class=""><font color="#12c00e" class=""><br class=""></font>* Design Decisions *<br class=""><font color="#12c00e" class=""><br class=""></font>- The IRTranslator is a final class. Its purpose is to move away from LLVM IR to MachineInstr world <b class="">[final]</b>.<br class="">- Lower the ABI as part of the translation process <b class="">[final]</b>.<br class=""><font color="#12c00e" class=""><br class=""></font>* Design Questions the Prototype Addresses at the End of M1 *<br class=""><font color="#12c00e" class=""><br class=""></font>- Handling of aggregate types during the translation.<br class="">- Lowering of switches.<br class="">- What about Module pass for Machine pass?<br class="">- Introduce new APIs to have a clearer separation between:<br class=""> - Legalization (setOperationAction, etc.)<br class=""> - Cost/Combine related (isXXXFree, etc.)<br class=""> - Lowering related (LowerFormal, etc.)<br class="">- What is the contract with the backends? Is it still “should be able to select any valid LLVM IR”?<br class=""><font color="#00afcd" class=""><br class=""></font>Thanks,<br class=""><div class="" style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;"><div class=""><div class=""><div class=""><div class=""><div class=""><div class=""><div class="" style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;"><div class=""><div class=""><div class="" style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;"><div class=""><div class=""><div class=""><div class=""><div class="" style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;"><div class=""><div class=""><div class="" style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;"><div class=""><div class=""><div class="" style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;"><div class=""><div class=""><div class=""><div class=""><div class="" style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;"><div class=""><div class=""><div class=""><div class="">-Quentin</div><div class=""></div></div></div></div></div></div></div></div></div></div></div></div></div></div></div></div></div></div></div></div></div></div></div></div></div></div></div></div></div></div></div></div></body></html>