<div dir="ltr">Hey Graham,<div> I worked on pretty much this exact thing last year. I did something similar to what you described, I traversed the CFG and built potentially profitable regions from any given valid start node. At that point there were several road blocks that prevented it from really going anywhere( like the inliner not preserving pgo data) but those problems should be gone by now.</div><div>Some thoughts:</div><div><br></div><div>: In terms of cost modeling, you will want to consider the interaction with loops:</div><div> - Whats the impact of outlining from inside of a loop.</div><div> - What if the hot region does not include the entry/exit, i.e hot loop.</div><div><br></div><div>: Something that would also benefit, but would require more tuning, is the relationship between size and "hotness". If for example you have a function that looks like this:</div><div><br></div><div>foo(bool B) {</div><div>... // Code that prevents early return.</div><div><br></div><div>if(B) // RegionA : Taken 50% of the time.</div><div> ... Very large amount of code.</div><div><br></div><div>else // RegionB : Taken 50% of the time.</div><div> ... Very small amount of code.</div><div>}</div><div><br></div><div>In the above you have two regions that aren't exactly cold. Outlining RegionA will make foo profitable to inline, but only if you take into account its large size. Using profile data as the sole cutoff will miss this opportunity.<br></div><div><br></div><div><br></div><div>: You may also want to look into hot switch statement splitting, though I don't know if it should really go into the partial inliner. This is splitting a switch statement into multiple switch statements if there are only a few cases that are actually hot.</div><div><br></div><div>SWITCH1:</div><div>switch(val) {</div><div> HOT: ...</div><div> COLD1: ...</div><div> COLD2: ...</div><div> ....</div><div> COLDN: ...</div><div> default: ...</div><div>}</div><div><br></div><div>would get transformed into:</div><div><br class="gmail-Apple-interchange-newline">SWITCH1:<br></div><div>switch(val) {</div><div> HOT: ...</div><div> default:</div><div> br SWITCH2:</div><div>}</div><div><br class="gmail-Apple-interchange-newline">SWITCH2:<br></div><div>switch(val) {</div><div> COLD1: ...</div><div> COLD2: ...</div><div> ....</div><div> COLDN: ...</div><div> default: ...</div><div>}</div><div><br></div><div><div class="gmail_extra"><br><div class="gmail_quote">On Tue, Aug 15, 2017 at 1:14 PM, Graham Yiu via llvm-dev <span dir="ltr"><<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div><p><font size="2">Hi Jessica,</font><br><br><font size="2">Thanks for the feedback. </font><br><br><font size="2">I believe the existing partial inliner pass does use some common utilities like the code extractor to do outlining. </font></p></div></blockquote><div>AFAIK, Code extractor is the only IR level utility for outlining, but it's not the best and definitely needs some improvement. It currently returns outputs via live out pointer parameters, which means that outlined functions can't be tagged with attributes like readonly. </div><div><br></div><div>There were also some known problems with extracting in the presence of critical edges, but I don't know if thats still the case.</div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div><p><font size="2"> Is that what you're referring to? I don't recall seeing any other passes that has outlining other than the machine outliner, but I may have missed something.</font><br><br><font size="2">I briefly looked at River's RFC and it seems he's mainly utilizing outlining as a tool to reduce code size while maintaining code performance.</font></p></div></blockquote><div> </div><div>The main point of the outliner I proposed in that RFC is benefiting code size. The use of PGO data is to simply avoid detrimenting runtime performance. </div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div><p><font size="2"> Our proposal is to improve on the existing outlining scheme of the partial inliner to give us more opportunities to inline hot code. We will only do this type of general outlining with the presence of profiling or user data (such as builtin_expect).</font> </p></div></blockquote><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div><p><font size="2"> With that said, I am interested in how River plans to handle live ranges</font></p></div></blockquote><div> </div><div> It's a pretty difficult problem. I have estimation for register usage within an outlined region, using something similar to the register cost calculation in the loop vectorizer. I don't currently have anything for the actual call to the function itself. I haven't found a nice enough solution that can work for a large number of candidates.</div><div><br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div><p><font size="2"> and heuristics he will use with profiling data available.</font></p></div></blockquote><div>As I said above, the use of profile data, currently, is to avoid regressing execution time. So the heuristics are basically "Is this too hot to outline from". That outliner also has a completely different goal/cost model, which makes applying it to this problem difficult.</div><div><br></div><div>Thanks,</div><div> River Riddle </div><div><br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div><p><br><br><font size="2">I haven't looked at the machine outliner yet, but my understanding is it also prioritizes code size reduction over performance gains. Is my assumption correct? Do you think there's some tuning we can do in the machine outliner to tailor for performance improvements?</font><span class="gmail-"><br><br><font size="2">Graham Yiu<br>LLVM Compiler Development<br>IBM Toronto Software Lab<br>Office: <a href="tel:(905)%20413-4077" value="+19054134077" target="_blank">(905) 413-4077</a> C2-407/8200/Markham<br>Email: <a href="mailto:gyiu@ca.ibm.com" target="_blank">gyiu@ca.ibm.com</a></font><br><br></span><img width="16" height="16" src="cid:1__=8FBB0BEEDFFBC5938f9e8a93df938690918c8FB@" border="0" alt="Inactive hide details for Jessica Paquette ---08/15/2017 02:45:06 PM---Hi Graham, Have you looked at using the existing outline"><font size="2" color="#424282">Jessica Paquette ---08/15/2017 02:45:06 PM---Hi Graham, Have you looked at using the existing outliner framework to implement partial inlining? I</font><br><br><font size="2" color="#5F5F5F">From: </font><font size="2">Jessica Paquette <<a href="mailto:jpaquette@apple.com" target="_blank">jpaquette@apple.com</a>></font><br><font size="2" color="#5F5F5F">To: </font><font size="2">Graham Yiu <<a href="mailto:gyiu@ca.ibm.com" target="_blank">gyiu@ca.ibm.com</a>></font><br><font size="2" color="#5F5F5F">Cc: </font><font size="2"><a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a></font><br><font size="2" color="#5F5F5F">Date: </font><font size="2">08/15/2017 02:45 PM</font><br><font size="2" color="#5F5F5F">Subject: </font><font size="2">Re: [llvm-dev] [RFC] Enhance Partial Inliner by using a general outlining scheme for cold blocks</font><br><font size="2" color="#5F5F5F">Sent by: </font><font size="2"><a href="mailto:jpaquette@apple.com" target="_blank">jpaquette@apple.com</a></font><br></p><hr width="100%" size="2" align="left" noshade style="color:rgb(128,145,165)"><div><div class="gmail-h5"><br><br><br>Hi Graham,<br><br>Have you looked at using the existing outliner framework to implement partial inlining? In the past, people have combined outlining + inlining to get partial inlining “for free” (see "Function outlining and partial inlining” by Zhao and Amaral).<br><br>There is the MachineOutliner. River Riddle has been working on an IR-level outliner as well. The MachineOutliner doesn’t currently consider the heat of a block, but might be worth experimenting with. It might be good to experiment with River’s work and the existing outlining pass to see if this functionality can effectively fall out of what we have already.<br><br>Here’s the recent IR-level outlining thread for reference wrt River’s work: <a href="http://lists.llvm.org/pipermail/llvm-dev/2017-July/115666.html" target="_blank"><u><font color="#0000FF">http://lists.llvm.org/<wbr>pipermail/llvm-dev/2017-July/<wbr>115666.html</font></u></a><br><br>- Jessica<br>
<ul><ul>On Aug 15, 2017, at 11:22 AM, Graham Yiu via llvm-dev <<a href="mailto:llvm-dev@lists.llvm.org" target="_blank"><u><font color="#0000FF">llvm-dev@lists.llvm.org</font></u></a>> wrote:<br>
<p><font size="2" face="Arial">Hello,</font><br><font size="2" face="Arial"><br>My team and I are looking to do some enhancements in the partial inliner in opt. Would appreciate any feedback that folks might have.</font><br><font size="2" face="Arial"><br># Partial Inlining in LLVM opt<br><br>## Summary<br><br>### Background<br><br>Currently, the partial inliner searches the first few blocks of the callee and looks for a branch to the return block (ie. early return). If found, it attempts to outline the rest of the slow (or heavy) code so the inliner will be able to inline the fast (or light) code. If no early returns are found, the partial inliner will give up. As far as I can tell, BlockFrequency and BranchProbability information is only used when attempting to inline the early return code, and not used to determine whether to outline the slow code.<br><br>### Proposed changes<br><br>In addition to looking for early returns, we should utilize profile information to outline blocks that are considered cold. If we can sufficiently reduce the size of the original function via this type of outlining, inlining should be able to inline the rest of the hot code. <br><br>## Details<br><br>With the presence of profile information, we have a view of what code is infrequently executed and make better decisions on what to outline. Early return blocks that are infrequently executed should still be included as candidates for outlining, but will be treated just like any other cold blocks. Without profiling information, however, we should remain conservative and only partial inline in the presence of an early return in the first few blocks of a function (ie. peel the early return out of the function).<br><br>To find cold regions to outline, we will traverse the CFG to find edges deemed 'cold' and look at the blocks dominated by the successor node. If, for some reason, that block has more than one predecessor, then we will skip this candidate as there should be a node that dominates this successor that has a single entry point. The last node in the dominance vector should also have a single successor. If it does not, then further investigation of the CFG is necessary to see when/how this situation occurs.<br><br>We will need several heuristics to make sure we only outline in cases where we are confident it will result in a performance gain. Things such as threshold on when a branch is considered cold, the minimum number of times the predecessor node has to be executed in order for an edge to be considered (confidence factor), and the minimum size of the region to be outlined (can use inlining cost analysis like we currently do) will require some level of tuning.<br><br>Similar to the current implementation, we will attempt to inline the leftover (hot) parts of the code, and if for some reason we cannot then we discard the modified function and its outlined code.<br><br>### Code changes<br><br>The current Partial Inlining code first clones the function of interest and looks for a single set of blocks to outline. It then creates a function with the set the blocks, and saves the outlined function and outline callsite information as part of the function cloning container. In order to outline multiple regions of the function, we will need to change these containers to keep track of a list of regions to outline. We will also need to update the cost analysis to take into account multiple outlined functions. <br><br>When a ProfileSummary is available, then we should skip the code that looks for early returns and go into new code that looks for cold regions to outline. When ProfileSummary is not available, then we can fall back to the existing code and look for early returns only.<br><br>### Tuning<br><br>- The outlining heuristics will need to determine if a set of cold blocks is large enough to warrant the overhead of a function call. We also don't want the inliner to attempt to inline the outlined code later.<br>- The threshold for determining whether a block is cold will also need to be tuned. In the case that profiling information is not accurate, we will pay the price of the additional call overhead for executing cold code.<br>- The confidence factor, which can be viewed as the minimum number of times the predecessor has to be executed in order for an edge to be considered cold, should also be taken into account to avoid outlining code paths we have little information on.</font><br><font size="2"><br>Graham Yiu<br>LLVM Compiler Development<br>IBM Toronto Software Lab<br>Office: <a href="tel:(905)%20413-4077" value="+19054134077" target="_blank">(905) 413-4077</a> C2-407/8200/Markham</font><u><font size="2" color="#0000FF"><br></font></u><a href="mailto:gyiu@ca.ibm.com" target="_blank"><u><font size="2" color="#0000FF">Email: gyiu@ca.ibm.com</font></u></a></p><p>______________________________<wbr>_________________<br>LLVM Developers mailing list<u><font color="#0000FF"><br></font></u><a href="mailto:llvm-dev@lists.llvm.org" target="_blank"><u><font color="#0000FF">llvm-dev@lists.llvm.org</font></u></a><br><a href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" target="_blank">http://lists.llvm.org/cgi-bin/<wbr>mailman/listinfo/llvm-dev</a></p><p></p></ul></ul><br><br><br>
</div></div><p></p></div>
<br>______________________________<wbr>_________________<br>
LLVM Developers mailing list<br>
<a href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a><br>
<a href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" rel="noreferrer" target="_blank">http://lists.llvm.org/cgi-bin/<wbr>mailman/listinfo/llvm-dev</a><br>
<br></blockquote></div><br></div></div></div>