<html><head><style type='text/css'>p { margin: 0; }</style></head><body><div style='font-family: arial,helvetica,sans-serif; font-size: 10pt; color: #000000'><br><hr id="zwchr"><blockquote style="border-left: 2px solid rgb(16, 16, 255); margin-left: 5px; padding-left: 5px; color: rgb(0, 0, 0); font-weight: normal; font-style: normal; text-decoration: none; font-family: Helvetica,Arial,sans-serif; font-size: 12pt;"><b>From: </b>"Quentin Colombet" <qcolombet@apple.com><br><b>To: </b>"Hal Finkel" <hfinkel@anl.gov><br><b>Cc: </b>"llvm-dev" <llvm-dev@lists.llvm.org><br><b>Sent: </b>Monday, November 30, 2015 1:34:20 PM<br><b>Subject: </b>Re: [llvm-dev] [GlobalISel] A Proposal for global instruction selection<br><br>
Hi Hal,<div class=""><br class=""></div><div class="">The alias information is a good example of the MI to IR back links, thanks for pointing that out.</div><div class=""><br class=""><div><blockquote class=""><div class="">On Nov 26, 2015, at 12:58 PM, Hal Finkel <<a href="mailto:hfinkel@anl.gov" class="" target="_blank">hfinkel@anl.gov</a>> wrote:</div><br class="Apple-interchange-newline"><div class=""><span style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; float: none; display: inline ! important;" class="">Hi Quentin,</span><br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class=""><br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class=""><span style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; float: none; display: inline ! important;" class="">First, thanks a lot for working on this! This is obviously a really-important problem.</span><br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class=""><br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class=""><span style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; float: none; display: inline ! important;" class="">One thought:</span><br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class=""><br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class=""><span style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; float: none; display: inline ! important;" class="">+ /// *** This is to support:</span><br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class=""><span style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; float: none; display: inline ! important;" class="">+ /// *** Self contained machine representation, no back links to LLVM IR.</span><br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class=""><span style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; float: none; display: inline ! important;" class="">+ /// Import the attribute from the IR Function.</span><br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class=""><span style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; float: none; display: inline ! important;" class="">+ AttributeSet AttributeSets; ///< Parameter attributes</span><br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class=""><br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class=""><span style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; float: none; display: inline ! important;" class="">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.</span><br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class=""></div></blockquote><div><br class=""></div><div>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.</div><div>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:</div><div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class=""> // AA might be used later for instruction scheduling, and we need it to be</div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class=""> // able to deduce the correct aliasing releationships between pointers</div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class=""> // derived from the alloca being remapped and the target of that remapping.</div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class=""> // The only safe way, without directly informing AA about the remapping</div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class=""> // somehow, is to directly update the IR to reflect the change being made</div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class=""> // here.</div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class=""> Instruction *Inst = const_cast<AllocaInst *>(To);</div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class=""> if (From->getType() != To->getType()) {</div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class=""> BitCastInst *Cast = new BitCastInst(Inst, From->getType());</div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class=""> Cast->insertAfter(Inst);</div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class=""> Inst = Cast;</div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class=""> }</div><div class=""><br class=""></div><div class="">Therefore, I would prefer having the alias information expressed as something decoupled from the IR and that could be updated.</div><div class=""><br class=""></div><div id="DWT2328" class="">What do you think?</div></div></div></div></blockquote>I certainly agree that it is ugly, and as the author of the comment you've highlighted above, I would love to have a better solution. The only problem is that I don't have a good idea how such a solution might work; prerecording all N^2 possible aliasing queries is impractical. I don't think that rewriting our current AA to work on MI, or even refactoring the current AA logic to work in terms of abstractions over both IR and MI is really possible, because we need it to function even after MI has dropped out of SSA form and PHI elimination has happened.<br><br>That having been said, prerecording query results still seems like the best solution, but it can't be naive (N^2). We have to understand the constraints that the query results will only be used to disambiguate otherwise-undecidable aliasing queries for the purpose of doing merging, scheduling, etc., and maybe within those use cases, we can constrain the problem enough to make prerecording the query results practical.<br><br>The bad news, however, is that prerecording the query results does not remove the comment in stack coloring, but just changes it to discuss operating on some MI-level data structure that is not the IR.<br><br>Thanks again,<br>Hal<br><blockquote style="border-left: 2px solid rgb(16, 16, 255); margin-left: 5px; padding-left: 5px; color: rgb(0, 0, 0); font-weight: normal; font-style: normal; text-decoration: none; font-family: Helvetica,Arial,sans-serif; font-size: 12pt;"><div class=""><div><div><div class=""></div><div class=""><br class=""></div><div class="">Cheers,</div><div class="">-Quentin</div></div><br class=""><blockquote class=""><div class=""><br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class=""><span style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; float: none; display: inline ! important;" class="">-Hal</span><br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class=""><br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class=""><span style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; float: none; display: inline ! important;" class=""><hr id="zwchr"><span class="Apple-converted-space"> </span></span><br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class=""><br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class=""><blockquote style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class="">From: "Quentin Colombet via llvm-dev" <<a href="mailto:llvm-dev@lists.llvm.org" class="" target="_blank">llvm-dev@lists.llvm.org</a>><br class="">To: "llvm-dev" <<a href="mailto:llvm-dev@lists.llvm.org" class="" target="_blank">llvm-dev@lists.llvm.org</a>><br class="">Sent: Wednesday, November 18, 2015 1:26:37 PM<br class="">Subject: [llvm-dev] [GlobalISel] A Proposal for global instruction<br class="">selection<br class=""></blockquote><br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class=""><blockquote style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class="">Hi,<br class=""></blockquote><br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class=""><blockquote style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class="">With this email, I would like to kick-off the development for the<br class="">next instruction selector that I described during the last LLVM Dev’<br class="">Meeting.<br class="">For the motivations, see Jakob’s proposal (<br class=""><a href="http://lists.cs.uiuc.edu/pipermail/llvmdev/2013-August/064727.html" class="" target="_blank">http://lists.cs.uiuc.edu/pipermail/llvmdev/2013-August/064727.html</a> )<br class="">and for the proposal, see the slides (Keynote:<br class=""><a href="http://llvm.org/viewvc/llvm-project/www/trunk/devmtg/2015-10/slides/Colombet-GlobalInstructionSelection.key?view=co" class="" target="_blank">http://llvm.org/viewvc/llvm-project/www/trunk/devmtg/2015-10/slides/Colombet-GlobalInstructionSelection.key?view=co</a><br class="">or PDF:<br class="">http://llvm.org/viewvc/llvm-project/www/trunk/devmtg/2015-10/slides/Colombet-GlobalInstructionSelection.pdf?revision=252430&view=co<br class="">) or the talk (<br class="">https://www.youtube.com/watch?v=F6GGbYtae3g&list=PL_R5A0lGi1AA4Lv2bBFSwhgDaHvvpVU21&index=2<br class="">).<br class=""></blockquote><br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class=""><blockquote style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class="">TL;DR This is happening now, feedbacks invited!<br class=""></blockquote><br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class=""><blockquote style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class="">*** Context ***<br class=""></blockquote><br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class=""><blockquote style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class="">During the last LLVM Dev’ Meeting, I have presented a proposal for<br class="">the next instruction selector, GlobalISel. The proposal is basically<br class="">summarized in "High Level Prototype Design” and “Roadmap”. (If you<br class="">want further details, feel free to reach me.)<br class=""></blockquote><br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class=""><blockquote style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class="">The first step of the development plan is to prototype the new<br class="">framework on open source. The idea is to start prototyping now(!)<br class="">and have the discussion ongoing in parallel. The reason of such<br class="">approach is to have code that can be used to inform those<br class="">discussions, e.g., by collecting data and trying different designs<br class="">approaches. Regarding the discussion, I have listed a few points<br class="">where your feedbacks would be particularly appreciated (see Feedback<br class="">Invite).<br class=""></blockquote><br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class=""><blockquote style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class="">Also, as I have mentioned in my talk, some issues are controversial<br class="">but I expect them to be resolved during prototype development.<br class="">Specifically theses concern aspects of legalization (should parts of<br class="">it be done at the LLVM IR level or all at the MI level?) and code<br class="">re-use for instruction combiner. Please feel free to bring up your<br class="">specific concern as I move along with the development plan.<br class=""></blockquote><br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class=""><blockquote style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class="">I expect the design to evolve with our experimental findings and your<br class="">feedbacks and contributions.<br class="">Nonetheless, we expect to nail down some design decisions once and<br class="">for all as the prototype progresses. I have highlighted them with<br class="">the following pattern [final] .<br class=""></blockquote><br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class=""><blockquote style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class="">*** Feedback Invite ***<br class=""></blockquote><br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class=""><blockquote style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class="">If you follow and support this work you need to be aware of three<br class="">things and I am eager to hear your feedback and thoughts about them:<br class="">the overall goals of Global ISel, the goals of the prototype, and<br class="">the impact of the prototype work on backend design.<br class=""></blockquote><br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class=""><blockquote style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class="">In the section “Goals", I defined (repeated for people that saw the<br class="">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=""></blockquote><br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class=""><blockquote style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class="">The prototype will answer critical design questions (see “Design<br class="">Questions the Prototype Addresses at the End of M1" for examples)<br class="">before the actual design of Gobal ISel is finalized, but it cannot<br class="">cover everything.<br class="">Specifically we will *not* look into improving TableGen or reuse<br class="">InstCombine (see “ Proposed Approach” for the rational). Please let<br class="">me know if you see any issue with that.<br class=""></blockquote><br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class=""><blockquote style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class="">There is also basic ground work needed to prepare for Global ISel and<br class="">I need to extend the core MachineInstr-level APIs as explained<br class="">during the talk. For this, I prepared sketches of patches to<br class="">illustrate them and describe the details in the “Implications”<br class="">section below. Please have a look at the patches to have a better<br class="">idea of the expected impact.<br class=""></blockquote><br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class=""><blockquote style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class="">If there is anything else you want to discuss related to Global ISel<br class="">feel free to reach me. In particular, several people expressed their<br class="">interests during the LLVM Dev Meeting in contributing to the<br class="">project. Let me know what is your area of interest, so that we can<br class="">coordinate our efforts.<br class="">Anyhow, please add [GlobalISel] in the subject line to help<br class="">categorizing the emails.<br class=""></blockquote><br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class=""><blockquote style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class="">*** Goals ***<br class=""></blockquote><br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class=""><blockquote style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class="">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<br class="">legalization.<br class="">- Self contained machine representation, no back links to LLVM IR.<br class="">- No change to LLVM IR.<br class=""></blockquote><br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class=""><blockquote style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class="">Note: The goals are common to all targets. In particular, we do not<br class="">intend to work on target specific feature for the prototype.<br class="">The bottom line is please make sure those goals are compatible with<br class="">what you want to achieve for your target, even if your requirement<br class="">does not get listed here.<br class=""></blockquote><br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class=""><blockquote style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class="">*** Proposed Approach ***<br class=""></blockquote><br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class=""><blockquote style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class="">In this section, I describe the approach I plan to pursue in the<br class="">prototype and the roadmap to get there. The final design will flow<br class="">out of it.<br class=""></blockquote><br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class=""><blockquote style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class="">For this prototype, we purposely exclude any work to improve or use<br class="">TableGen or InstCombine [final]. We will keep in mind however, that<br class="">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<br class="">TableGen/InstCombine infrastructure before being able to work on the<br class="">ISel framework itself.<br class=""></blockquote><br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class=""><blockquote style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class="">The prototype vehicle will be AArch64 . None of the changes for<br class="">GlobalISel will negatively impact the existing ISel.<br class=""></blockquote><br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class=""><blockquote style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class="">** High Level Prototype Design **<br class=""></blockquote><br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class=""><blockquote style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class="">As shown in the talk, the expected pipeline for the prototype is:<br class="">LLVM IR -> IRTranslator -> Generic (G) MachineInstr -> Legalizer -><br class="">RegBankSelect -> Select -> MachineInstr<br class=""></blockquote><br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class=""><blockquote style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class="">Where:<br class="">- Terms in bold are intermediate representations.<br class="">- Generic MachineInstrs are machine instructions with a generic<br class="">opcode, e.g., ADD, COPY.<br class="">- IRTranslator: Translate LLVM IR to (G) MachineInstr.<br class="">- Legalizer: Legalize illegal (G) MachineInstr to legal (G)<br class="">MachineInstr.<br class="">- RegBankSelect: Assign virtual register with size to virtual<br class="">register with Register Bank.<br class="">- Select: Translate the remaining (G) MachineInstr to MachineIntr.<br class=""></blockquote><br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class=""><blockquote style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class="">** Implications **<br class=""></blockquote><br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class=""><blockquote style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class="">As part of the bring-up of the prototype, we need to extend some of<br class="">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,<br class="">ADD16, etc.<br class="">- Extend the MachineRegisterInfo to support size as well as register<br class="">classes for virtual registers.<br class=""></blockquote><br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class=""><blockquote style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class="">I have sketched the changes in the attached patches to help picturing<br class="">how the changes would impact the existing APIs.<br class=""></blockquote><br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class=""><blockquote style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class="">Note: I do not intend to commit those changes as they are. They will<br class="">go the usual review process in due time.<br class=""></blockquote><br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class=""><blockquote style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class="">The patches contain “// ***”-like comment that give a rough<br class="">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<br class="">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<br class="">able to delete the LLVM IR instance from the memory.<br class="">3. Extend MachineInstr to represent additional information attached<br class="">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=""></blockquote><br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class=""><blockquote style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class="">** Roadmap for the Prototype **<br class=""></blockquote><br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class=""><blockquote style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class="">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<br class="">vector instructions.<br class=""></blockquote><br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class=""><blockquote style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class="">Notes:<br class="">- For #1, we will not support any fancy instructions like landing pad<br class="">or switch.<br class="">- Each milestone should take about 3-4 months.<br class="">- At the end of #2, we would have a FastISel like selector.<br class=""></blockquote><br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class=""><blockquote style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class="">Each milestone will be detailed right before starting it. The<br class="">rational is that we want to accommodate what we discovered with the<br class="">prototype for the next milestone. In other words, in this email, I<br class="">only describe the first milestone in detail and I will give more<br class="">details on the next milestone shortly before we start it and so on.<br class="">For your information, here is the remaining of the intended roadmap<br class="">for the full project:<br class="">4. Productization: Clean up implementation, stabilize the APIs.<br class="">5. Complex legalization: Extend legalization support to everything<br class="">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<br class="">or beat SelectionDAG generated code.<br class="">8. Transition: Document how to switch, provide tools to help.<br class=""></blockquote><br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class=""><blockquote style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class="">** Milestone 1 **<br class=""></blockquote><br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class=""><blockquote style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class="">The first phase is focused on the IRTranslator pass.<br class=""></blockquote><br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class=""><blockquote style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class="">The IRTranslator is responsible for translating the LLVM IR into<br class="">Generic MachineInstr. The IRTranslator pass uses some target hooks<br class="">to perform the ABI lowering. We can either define a new API for<br class="">them, e.g., ABILoweringInfo, or extend the existing TargetLowering.<br class="">Moreover, the prototype will focus on simple instruction, i.e., we<br class="">will not support switch or landing pad for this iteration.<br class=""></blockquote><br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class=""><blockquote style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class="">At the end of M1, the prototype will not be able to produce code,<br class="">since we would only have the beginning of the Global ISel pipeline.<br class="">Instead, we will test the IRTranslator on the generic output that is<br class="">produced from the tested IR.<br class=""></blockquote><br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class=""><blockquote style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class="">* Design Decisions *<br class=""></blockquote><br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class=""><blockquote style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class="">- The IRTranslator is a final class. Its purpose is to move away from<br class="">LLVM IR to MachineInstr world [final] .<br class="">- Lower the ABI as part of the translation process [final] .<br class=""></blockquote><br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class=""><blockquote style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class="">* Design Questions the Prototype Addresses at the End of M1 *<br class=""></blockquote><br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class=""><blockquote style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class="">- 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<br class="">to select any valid LLVM IR”?<br class=""></blockquote><br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class=""><blockquote style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class="">Thanks,<br class=""></blockquote><br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class=""><blockquote style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class="">-Quentin<br class=""></blockquote><br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class=""><blockquote style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class="">--<br class=""></blockquote><span style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; float: none; display: inline ! important;" class="">Hal Finkel<span class="Apple-converted-space"> </span></span><br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class=""><span style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; float: none; display: inline ! important;" class="">Assistant Computational Scientist<span class="Apple-converted-space"> </span></span><br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class=""><span style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; float: none; display: inline ! important;" class="">Leadership Computing Facility<span class="Apple-converted-space"> </span></span><br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class=""><span style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; float: none; display: inline ! important;" class="">Argonne National Laboratory<span class="Apple-converted-space"> </span></span></div></blockquote></div><br class=""></div></blockquote><br><br><br>-- <br><div><span name="x"></span>Hal Finkel<br>Assistant Computational Scientist<br>Leadership Computing Facility<br>Argonne National Laboratory<span name="x"></span><br></div></div></body></html>