<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=""><br class=""><div><br class=""><blockquote type="cite" class=""><div class="">On Nov 21, 2017, at 7:59 AM, <a href="mailto:junbuml@codeaurora.org" class="">junbuml@codeaurora.org</a> wrote:</div><br class="Apple-interchange-newline"><div class=""><span style="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; float: none; display: inline !important;" class="">On 2017-11-17 23:50, Quentin Colombet wrote:</span><br style="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;" class=""><blockquote type="cite" style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px;" class=""><blockquote type="cite" class="">On Nov 17, 2017, at 11:15 AM, <a href="mailto:junbuml@codeaurora.org" class="">junbuml@codeaurora.org</a> wrote:<br class="">On 2017-11-17 13:10, Quentin Colombet wrote:<br class="">On Nov 16, 2017, at 2:31 PM, <a href="mailto:junbuml@codeaurora.org" class="">junbuml@codeaurora.org</a> wrote:<br class="">On 2017-11-14 17:22, Quentin Colombet wrote:<br class="">Hi,<br class="">I think it is kind of artificial to tie the CSRCost with the<br class="">presence<br class="">of calls.<br class="">I think I’ve already mentioned it in one of the review, but I<br class="">believe it would be better to differentiate when we want to use a<br class="">CSR<br class="">to avoid spilling or to avoid splitting. CSR instead of spilling<br class="">is<br class="">good, CSR instead of splitting, not so good :).<br class="">About this, I can see your previous comment in D27366 (I copied it<br class="">below) :<br class="">Also, that's possible that the right fix/simple fix is to have one<br class="">CSRCost for split and one for spill.<br class="">Indeed, IIRC, right now the returned cost for both spilling and<br class="">splitting is going to be the sum of the frequencies where the<br class="">split/spill happen and given the spill and copy have different cost,<br class="">we may want to have different comparison.<br class="">E.g., CSRCostForSpill = 5 (ok to trade against more than 5 executed<br class="">spill/reload) but CSRCostForSpilt = 20 (ok to trade against more<br class="">than 20 executed copies)<br class="">If this is what you meant here, is the CSRCostForSpilt the actual<br class="">cost directly comparable with the split cost?<br class="">Or, it should be multiplied with the entry frequency to be<br class="">comparable with the split cost, considering that the CSRCost is the<br class="">cost of spilling CSR in the entry?<br class=""></blockquote>I believe it should be compared directly with the split cost. I.e.,<br class="">CSRCostXXX against CostOfTheOtherChoiceWithFrequency.<br class="">As far as I know the spill/split cost which is compared with CSRCost<br class="">is the sum of the frequencies of spots where spill/split happen, and<br class="">the CSRCost is the cost of spilling CSR at the entry. If we say, for<br class="">example, 20 copies from pre-split are okay to trade against 1 csr<br class="">spill at the entry, then shouldn't we multiply FreqOfEntry with the 20<br class="">(number of tradable copies)?<br class="">Yes, you’re right with FreqOfEntry. I assumed this was 1.<br class=""></blockquote><br style="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;" class=""><br style="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;" class=""><span style="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; float: none; display: inline !important;" class="">Considering current implementation in initializeCSRCost() where the CSRCost is scaled by the FixedEntry(1 << 14), if we want to set 20 for CSRCostForSplit (20 copies are tradable with one CSR spill in the entry), then I think the initial raw value for CSRCostForSplit should be 20 * (1 << 14) to allow us to multiply 20 with the actual frequency of the entry. Do you agree with it?</span><br style="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;" class=""></div></blockquote><div><br class=""></div><div>Agreed.</div><br class=""><blockquote type="cite" class=""><div class=""><br style="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;" class=""><br style="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;" class=""><blockquote type="cite" style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px;" class=""><blockquote type="cite" class="">Please me know if I miss something here?<br class="">By doing this, I would expect we mechanically get the desired<br class="">behavior<br class="">that CSRs get used for live-ranges that go through calls (otherwise<br class="">we<br class="">would have spilled).<br class="">My 2c.<br class="">Cheers,<br class="">-Quentin<br class="">On Nov 10, 2017, at 12:34 PM, <a href="mailto:junbuml@codeaurora.org" class="">junbuml@codeaurora.org</a> wrote:<br class="">On 2017-11-10 07:47, Nemanja Ivanovic wrote:<br class="">One thing I thought about doing a while back and never really<br class="">wrote a<br class="">POC for is the following:<br class="">- Make FirstCSRCost a property of the MachineBasicBlock (or create<br class="">a<br class="">map of MBB* -> FirstCSRCost)<br class="">- Implement a pre-RA pass that will populate the map as follows:<br class="">- Identify all blocks with calls<br class="">- Find the nearest common dominator (NCD) to all those blocks<br class="">(not<br class="">strict so that a block with a call might be that NCD)<br class="">- If the NCD is the entry block, CSR allocation is cheap in all<br class="">blocks<br class="">- Make CSR allocation cheap in blocks that are in the dominator<br class="">tree<br class="">rooted at NCD<br class="">The idea would be to favour CSR allocation in blocks that might be<br class="">eligible for the prologue and favour splitting in blocks that we'd<br class="">prefer not to have a prologue in (or before).<br class="">Then a CFG such as this:<br class="">A<br class="">/ \<br class="">B C<br class="">| / \<br class="">| D E<br class="">| | /<br class="">| | /<br class="">| |/<br class="">| /<br class="">|/<br class="">F<br class="">- Assume calls are in B and ANY_OF(C,D,E): CSR allocation is cheap<br class="">everywhere<br class="">- Assume calls are in C or ALL_OF(D,E): CSR allocation is cheap in<br class="">ALL_OF(C,D,E); CSR allocation is expensive in ALL_OF(A,B,F)<br class="">- Assume only call is in ANY_OF(B,D,E): CSR allocation is cheap<br class="">only<br class="">in that block, expensive everywhere else<br class="">I think this construction would give us what we want, but there<br class="">may be<br class="">[obvious] counter-examples I haven't thought of.<br class="">Thanks Nemanja for sharing your idea. I think this might cover the<br class="">case I was targeting, and we may not need to be limited only in the<br class="">entry block.<br class="">However, I bit worry if this cause RegAllc to slow in allocating<br class="">CSRs. What if we have a call-site in the early exit path and no<br class="">call-site in all other blocks. Then, conservative allocation of CSRs<br class="">might not be a good choice if the reg pressure is high in the all<br class="">other blocks. As our first step, would it make sense to limit this<br class="">only when we detect an early exit? I guess Quentin may have some<br class="">comment.<br class="">thanks,<br class="">Jun<br class="">On Tue, Oct 31, 2017 at 8:38 PM, via llvm-dev<br class=""><<a href="mailto:llvm-dev@lists.llvm.org" class="">llvm-dev@lists.llvm.org</a>> wrote:<br class="">On 2017-10-30 21:20, Hal Finkel wrote:<br class="">On 10/30/2017 12:20 PM, <a href="mailto:junbuml@codeaurora.org" class="">junbuml@codeaurora.org</a> wrote:<br class="">On 2017-10-27 19:50, Hal Finkel wrote:<br class="">On 10/27/2017 03:32 PM, Jun Lim via llvm-dev wrote:<br class="">When compiling C code below for AArach64, I saw that<br class="">shrink-wrapping<br class="">didn't happen due to the very early uses of CSRs in the entry block.<br class="">So CSR spills/reloads are executed even when the early exit block is<br class="">taken.<br class="">int getI(int i);<br class="">int foo(int *P, int i) {<br class="">if (i>0)<br class="">return P[i];<br class="">i = getI(i);<br class="">return P[i];<br class="">}<br class="">It's not that hard to find such cases where RegAllocGreedy<br class="">aggressively allocates a CSRs when a live range expands across a<br class="">call-site. That's because of the conservatively initialized<br class="">CSRCost, causing RegAllocGreedy to strongly favour allocating a CSR<br class="">over splitting a region. Since allocation of CSRs requires the cost<br class="">of spilling CSRs, allocating CSRs is not always beneficial. Like the<br class="">case above, if a function has an early exit code, we may want to be<br class="">less aggressive on the first allocation of CSR in the entry block by<br class="">increasing the CSRCost.<br class="">Previously, I proposed <a href="https://reviews.llvm.org/D34608" class="">https://reviews.llvm.org/D34608</a> [1] in this<br class="">matter, but the way I detect the profitable cases and the way I<br class="">increase the CRSCost was somewhat unclear. Now, I'm thinking to less<br class="">aggressive on the first allocation of CSR in the entry block in case<br class="">where the function has an early exit so that encourage more<br class="">shrink-wrapping and avoid executing CSR spill/recover when the early<br class="">exit is taken. By sending this out, I just want to get any high<br class="">level feedback early. Please let me know if anyone has any opinion<br class="">about this.<br class="">So the heuristic will have nothing to do with the presence of calls?<br class="">Might this increase spilling in loops?<br class="">-Hal<br class="">Before allowing the first allocation from CSRs, I will check if the<br class="">virtual register is really live across a call in other blocks. If<br class="">the<br class="">function have a call in entry or exit, we don't need to increase the<br class="">CSRCost. This heuristic will be applied only for the very first<br class="">allocation from CSRs only in the entry block when the function has<br class="">an<br class="">early exit; if a CSR is already allocated in the function, we will<br class="">use<br class="">the current default global CSRCost.<br class="">Even after increasing the CSRCost, we should end up allocating the<br class="">first CSR if the cost of splitting the live-range is still higher<br class="">than<br class="">the increased CSRCost. I believe the amount we want to increase the<br class="">CSRCost must be target-dependent, but it must be conservative enough<br class="">to avoid too many copies in the related spots.<br class="">Thanks for explaining.<br class="">I suppose you'll want to make sure that the call(s) in question come<br class="">after the early exit (i.e., that there aren't calls before the early<br class="">exit)?<br class="">I will check if a virtual register is live across only calls which<br class="">will be executed when the early exit is not taken. By increasing<br class="">CSRcost for such case, we increase chances to avoid executing CSR<br class="">spill/recover when the early exit is taken.<br class="">When you say "only in the entry block" you mean that the live range<br class="">starts in the entry block, right (i.e., that it is a function<br class="">parameter or a vreg defined by some instruction in the entry block)?<br class="">Yes.<br class="">Does it matter that it is in the entry block, or do you only need it<br class="">to come before the early exit and have an execution frequency <= to<br class="">the entry block's execution frequency?<br class="">The reason I specifically check the entry block is because for now I<br class="">see the early exit happen only in entry block; limiting that the<br class="">early<br class="">exit condition is checked in the entry block and branch to the exit<br class="">block directly from the entry block if hitting the condition. If<br class="">overall approach is reasonable, we can certainly extend it.<br class="">-Hal<br class="">Thanks,<br class="">Jun<br class="">_______________________________________________<br class="">LLVM Developers mailing list<br class=""><a href="mailto:llvm-dev@lists.llvm.org" class="">llvm-dev@lists.llvm.org</a><br class="">http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev [2]<br class="">-- Hal Finkel<br class="">Lead, Compiler Technology and Programming Languages<br class="">Leadership Computing Facility<br class="">Argonne National Laboratory<br class="">--<br class="">Qualcomm Datacenter Technologies, Inc. as an affiliate of Qualcomm<br class="">Technologies, Inc.<br class="">Qualcomm Technologies, Inc. is a member of the Code Aurora Forum, a<br class="">Linux Foundation Collaborative Project.<br class="">_______________________________________________<br class="">LLVM Developers mailing list<br class="">llvm-dev@lists.llvm.org<br class="">http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev [2]<br class="">Links:<br class="">------<br class="">[1] https://reviews.llvm.org/D34608<br class="">[2] http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev<br class="">--<br class="">Qualcomm Datacenter Technologies, Inc. as an affiliate of Qualcomm<br class="">Technologies, Inc.<br class="">Qualcomm Technologies, Inc. is a member of the Code Aurora Forum, a<br class="">Linux Foundation Collaborative Project.<br class="">--<br class="">Qualcomm Datacenter Technologies, Inc. as an affiliate of Qualcomm<br class="">Technologies, Inc.<br class="">Qualcomm Technologies, Inc. is a member of the Code Aurora Forum, a<br class="">Linux Foundation Collaborative Project.<br class=""></blockquote>--<br class="">Qualcomm Datacenter Technologies, Inc. as an affiliate of Qualcomm<br class="">Technologies, Inc.<br class="">Qualcomm Technologies, Inc. is a member of the Code Aurora Forum, a<br class="">Linux Foundation Collaborative Project.<br class=""></blockquote><br style="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;" class=""><span style="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; float: none; display: inline !important;" class="">--<span class="Apple-converted-space"> </span></span><br style="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;" class=""><span style="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; float: none; display: inline !important;" class="">Qualcomm Datacenter Technologies, Inc. as an affiliate of Qualcomm Technologies, Inc.</span><br style="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;" class=""><span style="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; float: none; display: inline !important;" class="">Qualcomm Technologies, Inc. is a member of the Code Aurora Forum, a Linux Foundation Collaborative Project.</span></div></blockquote></div><br class=""></body></html>