<html><head><meta http-equiv="Content-Type" content="text/html; charset=utf-8"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; line-break: after-white-space;" class="">Hi Gabriel,<div class=""><br class=""></div><div class="">Such approach matches what I had in mind for a “global” cost model which would have been a higher tier than greedy and fast.</div><div class="">Actually, the idea was that “global" would only be a variant of greedy where the window for the computed costs would have been infinitely large (right now the only available window is 1 instruction).</div><div class=""><br class=""></div><div class="">If we decide to go with such approach, I think we need to keep it as a possible variant, as opposed to the uniquely available approach because I suspect the compile time implications are high.</div><div class=""><br class=""></div><div class="">Cheers,<br class=""><div>-Quentin</div><div><br class=""></div><div><blockquote type="cite" class=""><div class="">On Oct 13, 2020, at 8:44 AM, Gabriel Hjort Åkerlund <<a href="mailto:gabriel.hjort.akerlund@ericsson.com" class="">gabriel.hjort.akerlund@ericsson.com</a>> wrote:</div><br class="Apple-interchange-newline"><div class=""><div class="WordSection1" style="page: WordSection1; caret-color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration: none;"><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class=""><span style="font-family: "Ericsson Hilda", serif;" class="">Hi all,<o:p class=""></o:p></span></div><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class=""><span style="font-family: "Ericsson Hilda", serif;" class=""><o:p class=""> </o:p></span></div><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class=""><span lang="EN-US" style="font-family: "Ericsson Hilda", serif;" class="">I was pondering on how regbank-select could find the optimal assignment, and came up with the following algorithm:<o:p class=""></o:p></span></div><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class=""><span lang="EN-US" style="font-family: "Ericsson Hilda", serif;" class=""><o:p class=""> </o:p></span></div><ol start="1" type="1" style="margin-bottom: 0cm; margin-top: 0cm;" class=""><li class="MsoListParagraph" style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;"><span lang="EN-US" style="font-family: "Ericsson Hilda", serif;" class="">Traverse top-down and compute cost of putting the given result in a particular register bank. The cost equals the cost of the InstructionMapping itself plus the cost of putting each operand in the register bank as required by the operand’s ValueMapping. Hence the cost definition is recursive and increases monotonically. If some operand does not have an InstructionMapping that puts it in the required register bank, add such an option and compute the cost as before plus the cost of converting the register bank. Hence such options would only be computed on demand.<o:p class=""></o:p></span></li><li class="MsoListParagraph" style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;"><span lang="EN-US" style="font-family: "Ericsson Hilda", serif;" class="">Traverse bottom-up and mark the InstructionMapping that puts the result in the appropriate register bank at lowest cost.<o:p class=""></o:p></span></li><li class="MsoListParagraph" style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;"><span lang="EN-US" style="font-family: "Ericsson Hilda", serif;" class="">Traverse top-down and select the register banks, also emitting repair code if needed.<o:p class=""></o:p></span></li></ol><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class=""><span lang="EN-US" style="font-family: "Ericsson Hilda", serif;" class=""><o:p class=""> </o:p></span></div><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class=""><span lang="EN-US" style="font-family: "Ericsson Hilda", serif;" class="">I started to implement this to see whether it would work, but I encountered problems with AMDGPU in the sense that its RegisterBankInfo seems to assume that the register banks are assigned progressively, meaning that when regbankselect queries AMDGPU’s RegisterBankInfo for the possible InstructionMappings for a given MachineInstr, then it only returns the smallest set necessary instead of all possible combinations. Meaning, for a MachineInstr where its input operands have not been assigned, it does not return the whole set of interesting InstructionMappings which are needed for the algorithm above.<o:p class=""></o:p></span></div><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class=""><span lang="EN-US" style="font-family: "Ericsson Hilda", serif;" class=""><o:p class=""> </o:p></span></div><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class=""><span lang="EN-US" style="font-family: "Ericsson Hilda", serif;" class="">I might finish the implementation just for fun and learning, but I would appreciate if anyone had some comments on whether this is a viable approach or will lead to naught.<o:p class=""></o:p></span></div><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class=""><span lang="EN-US" style="font-family: "Ericsson Hilda", serif;" class=""><o:p class=""> </o:p></span></div><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class=""><span lang="EN-US" style="font-family: "Ericsson Hilda", serif;" class="">Cheers,<o:p class=""></o:p></span></div><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class=""><span lang="EN-US" style="font-family: "Ericsson Hilda", serif;" class="">Gabriel<sup class=""><o:p class=""></o:p></sup></span></div><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class=""><span lang="EN-US" style="font-family: "Ericsson Hilda", serif;" class=""><o:p class=""> </o:p></span></div><div class=""><div style="border-style: solid none none; border-top-width: 1pt; border-top-color: rgb(225, 225, 225); padding: 3pt 0cm 0cm;" class=""><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class=""><b class=""><span lang="EN-US" class="">From:</span></b><span lang="EN-US" class=""><span class="Apple-converted-space"> </span>llvm-dev <<a href="mailto:llvm-dev-bounces@lists.llvm.org" class="">llvm-dev-bounces@lists.llvm.org</a>><span class="Apple-converted-space"> </span><b class="">On Behalf Of<span class="Apple-converted-space"> </span></b>Quentin Colombet via llvm-dev<br class=""><b class="">Sent:</b><span class="Apple-converted-space"> </span>den 9 oktober 2020 19:16<br class=""><b class="">To:</b><span class="Apple-converted-space"> </span>Dominik Montada <<a href="mailto:dominik.montada@hightec-rt.com" class="">dominik.montada@hightec-rt.com</a>><br class=""><b class="">Cc:</b><span class="Apple-converted-space"> </span>llvm-de >> LLVM Developers' List <<a href="mailto:llvm-dev@lists.llvm.org" class="">llvm-dev@lists.llvm.org</a>><br class=""><b class="">Subject:</b><span class="Apple-converted-space"> </span>Re: [llvm-dev] GlobalISel round table follow up: register bank select<o:p class=""></o:p></span></div></div></div><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class=""><o:p class=""> </o:p></div><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class=""><o:p class=""> </o:p></div><div class=""><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class=""><br class=""><br class=""><o:p class=""></o:p></div><blockquote style="margin-top: 5pt; margin-bottom: 5pt;" class=""><div class=""><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class="">On Oct 9, 2020, at 12:07 AM, Dominik Montada <<a href="mailto:dominik.montada@hightec-rt.com" style="color: blue; text-decoration: underline;" class="">dominik.montada@hightec-rt.com</a>> wrote:<o:p class=""></o:p></div></div><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class=""><o:p class=""> </o:p></div><div class=""><div class=""><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class="">Hi Quentin,<o:p class=""></o:p></div><div class=""><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class="">Am 08.10.20 um 21:17 schrieb Quentin Colombet:<o:p class=""></o:p></div></div><blockquote style="margin-top: 5pt; margin-bottom: 5pt;" class=""><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class="">Hi Dominik,<o:p class=""></o:p></div><div class=""><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class=""><br class=""><br class=""><o:p class=""></o:p></div><blockquote style="margin-top: 5pt; margin-bottom: 5pt;" class=""><div class=""><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class="">On Oct 8, 2020, at 5:03 AM, Dominik Montada <<a href="mailto:dominik.montada@hightec-rt.com" style="color: blue; text-decoration: underline;" class="">dominik.montada@hightec-rt.com</a>> wrote:<o:p class=""></o:p></div></div><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class=""><o:p class=""> </o:p></div><div class=""><div class=""><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class="">Hi Quentin,<o:p class=""></o:p></div><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class="">thanks for picking up the conversation!<o:p class=""></o:p></div><div class=""><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class="">> I think we should step back and check what we want before investing any time in some rewrite.<o:p class=""></o:p></div><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class="">That is a very fair point and I might have been getting ahead of myself in my last email.<br class="">What I would like to see from RegBankSelect is to produce the mapping with the overall lowest cost. Keeping track of all different combinations of mappings will certainly be non-trivial however, so I wonder if there is a smart way to do this without spending too much compilation time.<span class="Apple-converted-space"> </span><o:p class=""></o:p></div><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class="">Ideally for instructions with no operands (like G_CONSTANT) it could also check whether a cross-bank copy is actually worth it or if it would be more beneficial to simply rematerialize the instruction on the required bank. For such instructions this information should already be available as part of the cost-modelling in RegBankSelect: we could simply compare the cost of a mapping on the required bank vs. the cost of a cross-bank copy.<o:p class=""></o:p></div><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class="">Would you see this as a valid direction for RegBankSelect?<o:p class=""></o:p></div></div></div></div></blockquote><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class="">Yes, I think this is a valid direction. I actually think we shouldn’t restrict ourselves to instructions with no operands. We could always duplicate next to the original instruction, i.e., we wouldn’t have any issue materializing the arguments.<o:p class=""></o:p></div></div></blockquote><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class="">Sure, I guess that would also work as long we don't have to introduce copies for the operands. Theoretically this could even try to duplicate the operands if overall it's still cheaper than a cross-bank copy but that is probably some pandoras box just waiting to be opened :)<span class="Apple-converted-space"> </span><o:p class=""></o:p></div></div></div></blockquote><div class=""><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class=""><o:p class=""> </o:p></div></div><div class=""><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class="">Hehe!<o:p class=""></o:p></div></div><div class=""><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class="">Ideally we would compute the costs globally and do the code transformation only once. But I am guessing this is wishful thinking.<o:p class=""></o:p></div></div><div class=""><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class=""><o:p class=""> </o:p></div></div><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class=""><br class=""><br class=""><o:p class=""></o:p></div><blockquote style="margin-top: 5pt; margin-bottom: 5pt;" class=""><div class=""><div class=""><blockquote style="margin-top: 5pt; margin-bottom: 5pt;" class=""><div class=""><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class="">The one thing that needs work is the cost model.<o:p class=""></o:p></div></div></blockquote><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class="">What would you say does the cost model need in its current state?<o:p class=""></o:p></div><div class=""><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class=""><o:p class=""> </o:p></div></div></div></div></blockquote><div class=""><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class=""><o:p class=""> </o:p></div></div><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class="">I don’t remember how everything works so take it with a grain of salt.<o:p class=""></o:p></div></div><div class=""><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class="">I’d say we would need to take into account how much it would cost to duplicate the definitions and compute the repairing cost with those duplications.<o:p class=""></o:p></div></div><div class=""><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class="">The thing is it may become compile time intensive pretty quickly if we want to consider all the possibilities.<o:p class=""></o:p></div></div><div class=""><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class=""><o:p class=""> </o:p></div></div><div class=""><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class="">As a starter we could focus on the best mapping for the current instruction and try to match the desired regbanks from each operand and only evaluate that cost against just plain repairing.<o:p class=""></o:p></div></div><div class=""><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class=""><o:p class=""> </o:p></div></div><div class=""><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class="">In any case, I think it would require a non-trivial amount of work.<o:p class=""></o:p></div></div><div class=""><blockquote style="margin-top: 5pt; margin-bottom: 5pt;" class=""><div class=""><div class=""><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class="">By the way, does this have anything to do with what Matt was talking about during the round table? Unfortunately I don't remember exactly what his issues with RegBankSelect were but I'd be interested to know whether what we talked about would also benefit him.<o:p class=""></o:p></div><div class=""><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class=""><o:p class=""> </o:p></div></div></div></div></blockquote><div class=""><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class=""><o:p class=""> </o:p></div></div><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class="">Partially. IIRC Matt’s problem was also how we apply the mapping and how, right now, we have to abuse the observer mechanism to do what we want.<br class=""><br class=""><br class=""><o:p class=""></o:p></div><blockquote style="margin-top: 5pt; margin-bottom: 5pt;" class=""><div class=""><div class=""><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class="">I do remember that AMDGPU is apparently doing something very different compared to AArch64 for example and I'd be interested to know the reasoning behind the different approaches.<o:p class=""></o:p></div><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class="">Cheers,<o:p class=""></o:p></div><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class="">Dominik<o:p class=""></o:p></div><blockquote style="margin-top: 5pt; margin-bottom: 5pt;" class=""><div class=""><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class=""><o:p class=""> </o:p></div></div><div class=""><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class="">Cheers,<o:p class=""></o:p></div></div><div class=""><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class="">-Quentin<o:p class=""></o:p></div></div><div class=""><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class=""><br class=""><br class=""><o:p class=""></o:p></div><blockquote style="margin-top: 5pt; margin-bottom: 5pt;" class=""><div class=""><div class=""><div class=""><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class="">Best regards,<o:p class=""></o:p></div><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class="">Dominik<o:p class=""></o:p></div></div><div class=""><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class=""><o:p class=""> </o:p></div></div><div class=""><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class="">Am 07.10.20 um 19:47 schrieb Quentin Colombet:<o:p class=""></o:p></div></div><blockquote style="margin-top: 5pt; margin-bottom: 5pt;" class=""><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class="">Hi Dominik,<span class="Apple-converted-space"> </span><o:p class=""></o:p></div><div class=""><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class=""><o:p class=""> </o:p></div></div><div class=""><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class="">Thanks for sending this!<o:p class=""></o:p></div><div class=""><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class=""><br class=""><br class=""><o:p class=""></o:p></div><blockquote style="margin-top: 5pt; margin-bottom: 5pt;" class=""><div class=""><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class="">On Oct 7, 2020, at 5:21 AM, Dominik Montada via llvm-dev <<a href="mailto:llvm-dev@lists.llvm.org" style="color: blue; text-decoration: underline;" class="">llvm-dev@lists.llvm.org</a>> wrote:<o:p class=""></o:p></div></div><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class=""><o:p class=""> </o:p></div><div class=""><div class=""><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class="">Hi all,<br class=""><br class="">this is the second email for the round table follow-up, this time regarding the issues around the greedy RegBankSelect and alternative mappings.<br class=""><br class="">The issue I brought up was that because RegBankSelect goes top-down, it never looks at all available mappings for the operands when considering which of the mappings to apply to the current instruction. In our architecture we have one register bank dedicated to pointers and another one for anything else. We often see code where we have a G_PTR_ADD with a constant. Since the constant is not a pointer, we put it on the other register bank. We could put it on the address regbank and do provide alternative mappings for that, but since the greedy algorithm doesn't actually check the usage of the constant, it is always put on the other bank.<o:p class=""></o:p></div></div></div></blockquote><div class=""><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class=""><o:p class=""> </o:p></div></div><div class=""><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class="">The intent behind the greedy algorithm was for the mapping to look at X instructions ahead, depending on the optimization level, when assigning one instruction.<o:p class=""></o:p></div></div><div class=""><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class="">Right now the window is simply 1 instruction and the code is not structured to allow to have more than one.<o:p class=""></o:p></div></div><div class=""><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class=""><o:p class=""> </o:p></div></div><div class=""><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class="">As we gain more insights on what we want RegBankSelect to do, it makes sense to redesign it. <o:p class=""></o:p></div></div><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class=""><br class=""><br class=""><o:p class=""></o:p></div><blockquote style="margin-top: 5pt; margin-bottom: 5pt;" class=""><div class=""><div class=""><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class=""><br class="">When RegBankSelect then sees the G_PTR_ADD and sees that one of its inputs is on the other register bank already, it then inserts a costly cross-bank copy instead of checking if that operand has any alternative mappings which would make the overall mapping for the current instruction cheaper.<o:p class=""></o:p></div></div></div></blockquote><div class=""><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class=""><o:p class=""> </o:p></div></div><div class=""><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class="">The idea is when a mapping is done, that means it was the best one at the time of the decision (greedy), thus we don’t challenge that.<o:p class=""></o:p></div></div><div class=""><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class="">“Reverting” an already set mapping is not that simple because yes for this particular use we are inserting costly cross copies, but there are no guarantees that replacing the mapping of the definition will not insert even more costly copies for the other uses.<o:p class=""></o:p></div></div><div class=""><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class=""><o:p class=""> </o:p></div></div><div class=""><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class="">E.g., consider:<o:p class=""></o:p></div></div><div class=""><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class="">```<o:p class=""></o:p></div></div><div class=""><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class=""><span style="font-family: Menlo, serif;" class="">A = def <— RBS starts here</span><o:p class=""></o:p></div></div><div class=""><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class=""><span style="font-family: Menlo, serif;" class="">= useFP A</span><o:p class=""></o:p></div></div><div class=""><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class=""><span style="font-family: Menlo, serif;" class="">= useInt A</span><o:p class=""></o:p></div></div><div class=""><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class=""><span style="font-family: Menlo, serif;" class="">= useInt A</span><o:p class=""></o:p></div></div><div class=""><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class="">```<o:p class=""></o:p></div></div><div class=""><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class=""><o:p class=""> </o:p></div></div><div class=""><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class="">Let’s assume that greedy works the way it is intended. I.e., it assigns A to the int register bank because there are 2 such uses vs. only 1 fp bank use:<o:p class=""></o:p></div></div><div class=""><div class=""><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class="">```<o:p class=""></o:p></div></div><div class=""><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class=""><span style="font-family: Menlo, serif;" class="">A<int> = def</span><o:p class=""></o:p></div></div><div class=""><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class=""><span style="font-family: Menlo, serif;" class="">= useFP A<int> <— Next, RBS looks at this one</span><o:p class=""></o:p></div></div><div class=""><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class=""><span style="font-family: Menlo, serif;" class="">= useInt A<int></span><o:p class=""></o:p></div></div><div class=""><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class=""><span style="font-family: Menlo, serif;" class="">= useInt A<int></span><o:p class=""></o:p></div></div><div class=""><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class="">```<o:p class=""></o:p></div></div></div><div class=""><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class=""><o:p class=""> </o:p></div></div><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class="">Now the regbank for useFP is not right and has to be repaired. Right now, we will insert the costly cross copy for that use:<o:p class=""></o:p></div></div><div class=""><div class=""><div class=""><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class="">```<o:p class=""></o:p></div></div><div class=""><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class=""><span style="font-family: Menlo, serif;" class="">A<int> = def</span><o:p class=""></o:p></div></div><div class=""><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class=""><span style="font-family: Menlo, serif;" class="">AFP<fp> = cross_copy A<int></span><o:p class=""></o:p></div></div><div class=""><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class=""><span style="font-family: Menlo, serif;" class="">= useFP AFP<fp></span><o:p class=""></o:p></div></div><div class=""><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class=""><span style="font-family: Menlo, serif;" class="">= useInt A<int></span><o:p class=""></o:p></div></div><div class=""><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class=""><span style="font-family: Menlo, serif;" class="">= useInt A<int></span><o:p class=""></o:p></div></div><div class=""><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class="">```<o:p class=""></o:p></div></div><div class=""><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class=""><o:p class=""> </o:p></div></div><div class=""><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class="">Now, if we were to change the definition of A to avoid this copy we would create two costly copy for the useInt. Actually, another question is what would we do when we look at the first useInt? Is this use allowed to change the definition of the instruction again? Do we duplicate the definition? Etc..<o:p class=""></o:p></div></div><div class=""><div class=""><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class="">```<o:p class=""></o:p></div></div><div class=""><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class=""><span style="font-family: Menlo, serif;" class="">A<fp> = def <— reassign</span><o:p class=""></o:p></div></div><div class=""><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class=""><span style="font-family: Menlo, serif;" class="">= useFP AFP<fp></span><o:p class=""></o:p></div></div><div class=""><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class=""><span style="font-family: Menlo, serif;" class="">AInt1<int> = cross_copy A<fp></span><o:p class=""></o:p></div></div><div class=""><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class=""><span style="font-family: Menlo, serif;" class="">= useInt AInt1<int></span><o:p class=""></o:p></div></div><div class=""><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class=""><span style="font-family: Menlo, serif;" class="">AInt2<int> = cross_copy A<fp></span><o:p class=""></o:p></div></div><div class=""><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class=""><span style="font-family: Menlo, serif;" class="">= useInt AInt2<int></span><o:p class=""></o:p></div></div><div class=""><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class="">```<o:p class=""></o:p></div></div></div><div class=""><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class=""><o:p class=""> </o:p></div></div><div class=""><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class="">Bottom line, if we allow to modify the assignments of the definition, the decision making is not local anymore and in particular may require to add repairing code all over the place. As a result the cost model becomes much more complicated.<o:p class=""></o:p></div></div><div class=""><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class=""><o:p class=""> </o:p></div></div></div><blockquote style="margin-top: 5pt; margin-bottom: 5pt;" class=""><div class=""><div class=""><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class=""><br class="">Matt suggested that RegBankSelect should probably go bottom-up instead and I agree with him. I don't think there is a particular reason why RegBankSelect necessarily has to go top-down.<o:p class=""></o:p></div></div></div></blockquote><div class=""><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class=""><o:p class=""> </o:p></div></div><div class=""><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class="">The rationale for going top-down is that when you reach an instruction, all the operands are assigned so you know what would be the cost of repairing.<o:p class=""></o:p></div></div><div class=""><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class="">You could said that the problem is the same for definitions when going bottom-up. However, this is likely to be more problematic because usually you have fewer definitions than arguments on each individual instruction, therefore there is more guess work going on (e.g., top-down, you assume a cost for 1 definition, going bottom-up you have to assume a cost for 2 arguments or more precisely you would have to track a window of X instructions for 2 arguments instead of 1 definition.)<o:p class=""></o:p></div></div><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class=""><br class=""><br class=""><o:p class=""></o:p></div><blockquote style="margin-top: 5pt; margin-bottom: 5pt;" class=""><div class=""><div class=""><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class=""><br class="">I'm not too familiar with the implementation of RegBankSelect. Would it be a big effort to make it work bottom-up instead? I'm guessing one of the biggest areas would be the check whether a cross-bank copy is needed as well as calculating the overall cost for alternative mappings as now all usages of the current instruction would have to be checked instead of the much more limited operands. How big of an impact would this have?<o:p class=""></o:p></div></div></div></blockquote><div class=""><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class=""><o:p class=""> </o:p></div></div><div class=""><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class="">It’s been a while since I looked at the implementation but I would expect this to be significant.<o:p class=""></o:p></div></div><div class=""><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class=""><o:p class=""> </o:p></div></div><div class=""><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class="">I think we should step back and check what we want before investing any time in some rewrite. For instance, I don’t see what bottom-up fundamentally gives us. It seems like a workaround to me.<o:p class=""></o:p></div></div><div class=""><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class="">That said, it would work either way!<o:p class=""></o:p></div></div><div class=""><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class=""><o:p class=""> </o:p></div></div><div class=""><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class="">Cheers,<o:p class=""></o:p></div></div><div class=""><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class="">-Quentin<o:p class=""></o:p></div></div><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class=""><br class=""><br class=""><o:p class=""></o:p></div><blockquote style="margin-top: 5pt; margin-bottom: 5pt;" class=""><div class=""><div class=""><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class=""><br class="">Cheers,<br class=""><br class="">Dominik<br class=""><br class="">_______________________________________________<br class="">LLVM Developers mailing list<br class=""><a href="mailto:llvm-dev@lists.llvm.org" style="color: blue; text-decoration: underline;" class="">llvm-dev@lists.llvm.org</a><br class=""><a href="https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" style="color: blue; text-decoration: underline;" class="">https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a><o:p class=""></o:p></div></div></div></blockquote></div><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class=""><o:p class=""> </o:p></div></div></blockquote><pre style="margin: 0cm 0cm 0.0001pt; font-size: 10pt; font-family: "Courier New";" class="">-- <o:p class=""></o:p></pre><pre style="margin: 0cm 0cm 0.0001pt; font-size: 10pt; font-family: "Courier New";" class="">----------------------------------------------------------------------<o:p class=""></o:p></pre><pre style="margin: 0cm 0cm 0.0001pt; font-size: 10pt; font-family: "Courier New";" class="">Dominik Montada Email: <a href="mailto:dominik.montada@hightec-rt.com" style="color: blue; text-decoration: underline;" class="">dominik.montada@hightec-rt.com</a><o:p class=""></o:p></pre><pre style="margin: 0cm 0cm 0.0001pt; font-size: 10pt; font-family: "Courier New";" class="">HighTec EDV-Systeme GmbH Phone: +49 681 92613 19<o:p class=""></o:p></pre><pre style="margin: 0cm 0cm 0.0001pt; font-size: 10pt; font-family: "Courier New";" class="">Europaallee 19 Fax: +49-681-92613-26<o:p class=""></o:p></pre><pre style="margin: 0cm 0cm 0.0001pt; font-size: 10pt; font-family: "Courier New";" class="">D-66113 Saarbrücken WWW: <a href="https://protect2.fireeye.com/v1/url?k=10181272-4eb8bcbf-101852e9-86073b36ea28-3b408a428d93631b&q=1&e=a2c4ed0a-0e5c-4bef-9460-752197daba21&u=http%3A%2F%2Fwww.hightec-rt.com%2F" style="color: blue; text-decoration: underline;" class="">http://www.hightec-rt.com</a><o:p class=""></o:p></pre><pre style="margin: 0cm 0cm 0.0001pt; font-size: 10pt; font-family: "Courier New";" class=""><o:p class=""> </o:p></pre><pre style="margin: 0cm 0cm 0.0001pt; font-size: 10pt; font-family: "Courier New";" class="">Managing Director: Vera Strothmann<o:p class=""></o:p></pre><pre style="margin: 0cm 0cm 0.0001pt; font-size: 10pt; font-family: "Courier New";" class="">Register Court: Saarbrücken, HRB 10445, VAT ID: DE 138344222<o:p class=""></o:p></pre><pre style="margin: 0cm 0cm 0.0001pt; font-size: 10pt; font-family: "Courier New";" class=""><o:p class=""> </o:p></pre><pre style="margin: 0cm 0cm 0.0001pt; font-size: 10pt; font-family: "Courier New";" class="">This e-mail may contain confidential and/or privileged information. If<o:p class=""></o:p></pre><pre style="margin: 0cm 0cm 0.0001pt; font-size: 10pt; font-family: "Courier New";" class="">you are not the intended recipient please notify the sender immediately<o:p class=""></o:p></pre><pre style="margin: 0cm 0cm 0.0001pt; font-size: 10pt; font-family: "Courier New";" class="">and destroy this e-mail. Any unauthorised copying, disclosure or<o:p class=""></o:p></pre><pre style="margin: 0cm 0cm 0.0001pt; font-size: 10pt; font-family: "Courier New";" class="">distribution of the material in this e-mail is strictly forbidden.<o:p class=""></o:p></pre><pre style="margin: 0cm 0cm 0.0001pt; font-size: 10pt; font-family: "Courier New";" class="">--- <o:p class=""></o:p></pre></div></div></blockquote></div><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class=""><o:p class=""> </o:p></div></blockquote><pre style="margin: 0cm 0cm 0.0001pt; font-size: 10pt; font-family: "Courier New";" class="">-- <o:p class=""></o:p></pre><pre style="margin: 0cm 0cm 0.0001pt; font-size: 10pt; font-family: "Courier New";" class="">----------------------------------------------------------------------<o:p class=""></o:p></pre><pre style="margin: 0cm 0cm 0.0001pt; font-size: 10pt; font-family: "Courier New";" class="">Dominik Montada Email: <a href="mailto:dominik.montada@hightec-rt.com" style="color: blue; text-decoration: underline;" class="">dominik.montada@hightec-rt.com</a><o:p class=""></o:p></pre><pre style="margin: 0cm 0cm 0.0001pt; font-size: 10pt; font-family: "Courier New";" class="">HighTec EDV-Systeme GmbH Phone: +49 681 92613 19<o:p class=""></o:p></pre><pre style="margin: 0cm 0cm 0.0001pt; font-size: 10pt; font-family: "Courier New";" class="">Europaallee 19 Fax: +49-681-92613-26<o:p class=""></o:p></pre><pre style="margin: 0cm 0cm 0.0001pt; font-size: 10pt; font-family: "Courier New";" class="">D-66113 Saarbrücken WWW: <a href="https://protect2.fireeye.com/v1/url?k=09ae2d90-570e835d-09ae6d0b-86073b36ea28-251999af69af6c7f&q=1&e=a2c4ed0a-0e5c-4bef-9460-752197daba21&u=http%3A%2F%2Fwww.hightec-rt.com%2F" style="color: blue; text-decoration: underline;" class="">http://www.hightec-rt.com</a><o:p class=""></o:p></pre><pre style="margin: 0cm 0cm 0.0001pt; font-size: 10pt; font-family: "Courier New";" class=""><o:p class=""> </o:p></pre><pre style="margin: 0cm 0cm 0.0001pt; font-size: 10pt; font-family: "Courier New";" class="">Managing Director: Vera Strothmann<o:p class=""></o:p></pre><pre style="margin: 0cm 0cm 0.0001pt; font-size: 10pt; font-family: "Courier New";" class="">Register Court: Saarbrücken, HRB 10445, VAT ID: DE 138344222<o:p class=""></o:p></pre><pre style="margin: 0cm 0cm 0.0001pt; font-size: 10pt; font-family: "Courier New";" class=""><o:p class=""> </o:p></pre><pre style="margin: 0cm 0cm 0.0001pt; font-size: 10pt; font-family: "Courier New";" class="">This e-mail may contain confidential and/or privileged information. If<o:p class=""></o:p></pre><pre style="margin: 0cm 0cm 0.0001pt; font-size: 10pt; font-family: "Courier New";" class="">you are not the intended recipient please notify the sender immediately<o:p class=""></o:p></pre><pre style="margin: 0cm 0cm 0.0001pt; font-size: 10pt; font-family: "Courier New";" class="">and destroy this e-mail. Any unauthorised copying, disclosure or<o:p class=""></o:p></pre><pre style="margin: 0cm 0cm 0.0001pt; font-size: 10pt; font-family: "Courier New";" class="">distribution of the material in this e-mail is strictly forbidden.<o:p class=""></o:p></pre><pre style="margin: 0cm 0cm 0.0001pt; font-size: 10pt; font-family: "Courier New";" class="">--- </pre></div></div></blockquote></div></div></div></blockquote></div><br class=""></div></body></html>